Optimizing variadic template pack subsequence matching algorithm

I'm building a small MPL module in one of my utility libraries for fun and learning experience.

One of the problems I'm trying to solve is getting a list of all indices where a sequence of types appears inside another sequence of types.

Example:

static_assert(is_same

        ::IdxsOfSeq,
    ListInt
>());

The above code is valid and works as intended. However, finding out the indices of a subsequence in a long type sequence becomes very slow very fast.

Searching in a list with 20 or 30 elements can take up to 30 seconds of compilation time.

That would rarely be useful, but I'm also experimenting with compile-time strings implemented as character lists.

The current implementation of IdxsOfSeq basically uses std::index_sequence to perform a naive string matching algorithm over the type sequence.

The naive algorithm requires no preprocessing time, but the execution of the type matching requires a lot of computation time.

This is my current implementation of the string matching algorithm.

```
// Matches returns a ListInt is the boolean
// is true, otherwise an empty ListInt<>
template
struct Matches;

template
struct Matches
{
using Type = ListInt;
};

template
struct Matches
{
using Type = ListInt<>;
};

// GetMatch::Type checks if every type
// of TS (the source type sequence) starting from the index TStart
// matches every type in TM (the subsequence to find)
template
struct GetMatch;

template
struct GetMatch>
{
using Type = typename Matches
,
typename TM::template At
>...
>{}(),
TStart
>::Type;
};

// Main helper template
// Finds every occurrence of the list TM inside TS and returns its index
template
struct IdxsOfSeqHlpr;

template
struct IdxsOfSeqHlpr, TMIdxs>
{
// ConcatLists (obviously) concatenates the contents of the
// lists passed as template parameters in a single list
using Type = typename ConcatLists
,
typename GetMatch::Type...

I'm going to throw out a fairly complicated solution here by breaking the problem into lots of smaller parts. The end result is that the compilation of the following:

using T = typelist;

static_assert(std::is_same>,
    intlist
    >::value, "!");

is still almost instantaneous.

The algorithm is actually going to come from an idea in Python's itertools. What we want to do is walk our typelist N at a time (where N is the match length), and just use std::is_same to compare. That is, taking the original problem's list:

using SRC = typelist;

we want to turn it into something that looks like:

using X = typelist,
                   typelist,
                   typelist,
                   ...
                   >;

And then pass that into a metafunction taking an appropriate typelist and std::index_sequence do:

using type = concat::value,
        typelist>,
        typelist<>
        >...>;

That's the basic idea anyway. Plus, the smaller pieces are probably going to be useful in other contexts.

The Small Algorithms

These are very straightforward and I will omit them here for brevity: head, tail, size, concat (variadic!), any_of, and is_empty.

take_by

To generate the X typelist above, we need something like:

template 
using take_by = ???

The implementation of this is to make a typelist that is I copies of TL, each one dropping a steadily larger prefix off the top. Once we have that, we need to zip all the iterators together. So really, I need to start with the smaller pieces...

skip_n

Given a typelist, basically just call tail n times:

template 
struct skip_n_impl : skip_n_impl, I-1> { };

template 
struct skip_n_impl {
    using type = TL;
};

template 
using skip_n = typename skip_n_impl::type;

There may be a better way to do this, but I'm not sure. So, skip_n is typelist.

zip

This is the tricky part. Basically, we have a list of lists of types. If any of those typelists is empty, we're done. Otherwise, we concat all the heads with a recursive call against all the tails. We can't use std::conditional_t here due to eager evaluation of both parts, so I'm introducing two different impl types:

template 
struct zip_impl;

template 
struct zip_impl2;

template 
struct zip_impl2 {
    using type = typelist<>;
};

template 
struct zip_impl2, false> {
    using type = concat...>>,
                        typename zip_impl...>>::type
                        >;
};

template 
struct zip_impl>
    : zip_impl2, any_of::value...>::value>
{ };

template 
using zip = typename zip_impl::type;

This gives us the pieces to get back to take_by:

template >
struct take_by_impl;

template 
struct take_by_impl>
{
    using iters = typelist...>;
    using type = zip;
};

template 
using take_by = typename take_by_impl::type;

Hopefully that makes sense. First, we built up our "iterators" - which are all offset by one from each other. Then we just zip them up. Now we have the X, and all we need is:

matches:

template 
struct matches_impl
{
    template ::value>>
    struct impl;

    template 
    struct impl, std::index_sequence>
    {
        using type = concat::value,
                typelist>,
                typelist<>
                >...>;
    };

    using type = typename impl::value>>::type;
};

template 
using matches = typename matches_impl::type;

Basically, we end up creating a meta-list internally that would look like:

intlist,
typelist<>,
typelist<>,
intlist,
typelist<>,
...

But concat will drop the empties, so when that gets combined, we get what we wanted - intlist.

StackExchange Code Review Q#83178, answer score: 2