Trying to reduce Big O complexity of compile-time format string parsing

Question

We have a formatting library similar to fmtlib which allows us to format strings like this:

int foo = 1;
double bar = 2.3;
FMT("foo={} bar={}", foo, bar);

We recently added parsing of the format string at compile time, allowing us to specify, eg width, precision etc directly in the format string

// print foo with width=5, pad with 0; print bar with width 6, precision 2
// as decimal floating point
FMT("foo={:05} bar={:6.2f}", foo, bar);

The way we do this is as follows:

We have a struct which I can use to pass the format string as a template parameter

struct FmtString
{
    template
    constexpr FmtString(const char (&s)[N])
        : str(s)
    {}
    const char* const str;
};

Together with this FmtString and the arguments to be formatted, we use the following somewhat convoluted dance to generate a std::tuple of FmtSpecT format specifications.

We use the variadic template parameter pack to generate a std::index_sequence:

// use Ts... to create a tuple of the argument types and an std::index_sequence
template
struct CompiledFmtSpec
{
    using type = decltype(compileFmtSpec>(std::index_sequence_for {}));
};

// pull the indices out of the std::index_sequence
template
consteval auto compileFmtSpec(std::index_sequence)
{
    return typename FmtSpecs::type {};
}

We use the std::index_sequence to generate a variadic std::size_t sequence which we can use to extract each argument from the tuple of arguments, and its respective sequence value

template
struct FmtSpecs
{
    using type = std::tuple, Is>...>;
};

This results in the following tuple:

std::tuple<
    FmtSpecWrapper,
    FmtSpecWrapper,
    FmtSpecWrapper,
    ...
    FmtSpecWrapper>

We can then specialise FmtSpecWrapper for the particular type and parse its supported format spec

Here is the default implementation

template
struct FmtSpecWrapper
{
    using type = decltype(parseFmtString());
};

template
consteval auto parseFmtString()
{
    constexpr const char* pos = findFmtSpec(S, I);
    constexpr FmtSpec fmt = parseFmtSpec(pos);

    return FmtSpecT {};
}

This results in a FmtSpecT specialisation, which has the following NTTPs:

template
struct FmtSpecT
{
    static constexpr char pad = Pad;
    static constexpr bool align_right = AlignRight;
    static constexpr bool sign = Sign;
    static constexpr int width = Width;
    static constexpr int precision = Precision;
    static constexpr char type = Type;
    static constexpr int spec_len = SpecLen;
};

During formatting we can then pull out each FmtSpecT and use the members to format the argument.

The issue I'd like to try and solve is findFmtSpec(S, I).

Its job is to find the I'th format spec from the format string S.

constexpr const char* findFmtSpec(const FmtString& S, std::size_t i)
{
    std::size_t curr = 0;
    const char* next = S.str;
    while (*next)
    {
        const char c = *next++;
        if (c == '{')
        {
            if (c == *next) // found an escaped brace; {{ or }}
            {
                ++next;
            }
            else // found the start of the fmt spec
            {
                if (curr == i)
                    return next;
                ++curr;
                ++next;
            }
        }
    }
    throw std::domain_error("too many arguments for format string");
}

My issue is that it is Big O N^2, as it starts from 0 for every argument.

Ideally I would be able to start from the end of the previous format spec and seek forwards to find the next, turning the complexity into O(N).

Any ideas on how I can modify findFmtSpec so that for each i it starts from the return value of the previouc call?

user_17732522 · Answer

FmtString S is a template parameter, so it is usable in constant expressions.

Therefore all you need to do is write a constexpr function that extracts the specifiers up-front into a suitable container type, for example std::array. You can either enforce directly in the function that the number of specifiers matches sizeof...(Ts), so that N can just be that, or you can write another constexpr function which first counts the number of arguments:

struct FmtString
{
    template
    constexpr FmtString(const char (&s)[N])
        : str(s)
    {}
    const char* const str;

    template
    static constexpr auto findFmtSpec = []{
        constexpr auto N = []{
            // iterate `S.str` here and return number of specifiers
        }();
        std::array result;
        // iterate `S.str` again and store beginning of format specifiers consecutively in `result`.
        return result;
    }();
};

Then parseFmtString can just use FmtString::findFmtSpec[I]. I am using a static member variable template instead of a static function template to make sure that the compiler doesn't keep reevaluating an equivalent function call, although I think the compiler should memoize calls with the same arguments. I used nested lambdas for brevity, but you might want to put these into separate functions. There is also no particular reason to have the variable template be a member. It works outside the class as well.

You can also just generate the whole tuple this way:

template static constexpr auto specs = []{ // number of specifiers, can be `sizeof...(Ts)` // if no specific error handling is required constexpr auto N = []{ // iterate `S.str` here and return number of specifiers }(); if constexpr(sizeof...(Ts) != N) { // handle argument number mismatch } else { // specs as values constexpr auto specs = []{ std::array specs; // iterate `S.str` again and store `FmtSpec` for each specifier consecutively in `specs` return specs; }(); // lift specs into type (template arguments) return [](std::index_sequence){ return std::tuple>...>{}; }(std::make_index_sequence{}); } }();

Trying to reduce Big O complexity of compile-time format string parsing

1 Answers