How to improve the template recursion depth required for this pattern?

Question

I have been using a pattern described in this SO question in my code, to make Compile-time registration lists of various kinds: C++ type registration at compile time trick

For instance if you have a bunch of lua callback functions and you don't want to forget to register them with some lua state, you might declare them using a macro that puts a template type which knows their name and function pointer into a list, and then later you have a one-liner which registers all the functions.

A limitation of this technique (as described in the SO answer) is that if you have n items in the list, it requires template recursion depth O(n) to evaluate. This is not ideal, I actually have quite a few lua callback functions already...

I had believed that the O(n) recursion depth is unavoidable for various reasons, however as I recently learned from Yakk in this (unreleated) answer, some fundamental things which I naively thought required O(n) can actually be done in O(log n) depth. Switch statement variadic template expansion

In particular there's no reason anymore that the datastructures involved should require O(log n) template depth for their operations.

The part I'm not sure about is the Rank trick. From the referenced code, this template

template <int N>
struct Rank : Rank<N - 1> {};

template <>
struct Rank<0> {};

is a key ingredient. It is expensive in terms of template depth though -- instantiating Rank<N> requires template depth N. The important property that it has though, is that if a function f is defined which is overloaded using many different rank types, overload resolution always selects the overload of largest rank, because that is the "most derived instance". E.g. if we have this code:

bool f(Rank<0>) { return false; }
int f(Rank<1>) { return 0; }
float f(Rank<2>) { return 0; }
double f(Rank<3>) { return 0; }

then it's always the case that at any point in the code, decltype(f(Rank<100>{})) has type equal to the return value of the most recently defined overload. I.e. these assertions pass

bool f(Rank<0>) { return false; }
static_assert(std::is_same<bool, decltype(f(Rank<100>{}))>::value, "D:");
int f(Rank<1>) { return 0; }
static_assert(std::is_same<int, decltype(f(Rank<100>{}))>::value, "D:");
float f(Rank<2>) { return 0; }
static_assert(std::is_same<float, decltype(f(Rank<100>{}))>::value, "D:");
double f(Rank<3>) { return 0; }
static_assert(std::is_same<double, decltype(f(Rank<100>{}))>::value, "D:");

Is there a way to do this which does not require template recursion depth O(n)?

Perhaps using more, carefully chosen parameters for the function overloads (?)

Answer 1

To avoid error of the type:

template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating 'struct Rank<1148u>'

without increasing globally maximum template depth, you may instantiate intermediate templates:

// To allow instantiation of Rank<1000> with template-depth at 256
template struct Rank<250>;
template struct Rank<500>;
template struct Rank<750>;
template struct Rank<1000>;

You may also have an helper:

namespace detail
{

    template <template <std::size_t> class C,
              typename Seq,
              std::size_t BlockSize>
    struct Instantiate_Impl;

    template <template <std::size_t> class C,
              std::size_t... Is,
              std::size_t BlockSize>
    struct Instantiate_Impl<C, std::index_sequence<Is...>, BlockSize>
    {
        std::tuple<C<(Is * BlockSize)>...> dummy;
    };
}

template <template <std::size_t> class C,
          std::size_t N,
          std::size_t BlockSize = 250>
struct Instantiate :
    detail::Instantiate_Impl<C,
                             std::make_index_sequence<1 + N / BlockSize>,
                             BlockSize>
{};

And then

template struct Instantiate<Rank, 2000, 250>; // Rank<2000> is now instantiated.