c++recursionmetaprogrammingtemplate-specializationtemplate-variables

Why do I have to specialize recursive template variables?


So I wrote an answer here: https://stackoverflow.com/a/56569397/2642059 which strives to compute log2 at compile time like so:

template <unsigned int x>
constexpr enable_if_t<x != 0U, int> log2 = 1 + log2<x / 2U>;

template <>
constexpr int log2<1U> = 0;

This works fine but I didn't feel like I should have had to specialize:

template <unsigned int x>
constexpr enable_if_t<x != 0U, int> log2 = x < 4U ? 1 : 1 + log2<x / 2U>;

But this gives me the error:

In substitution of template<bool _Cond, class _Tp> using enable_if_t = typename std::enable_if::type [with bool _Cond = (0u != 0u); _Tp = int]:
prog.cpp:7:61: recursively required from constexpr std::enable_if_t<true, int> log2<4u>
prog.cpp:7:61: required from constexpr std::enable_if_t<true, int> log2<8u>
prog.cpp:10:11: required from here /usr/include/c++/6/type_traits:2523:61: error: no type named type in struct std::enable_if<false, int>

Is there a way I can prevent the compiler from unrolling the recursion too far?


Solution

  • You use recursion to calculate log2. Each and every recursive operation in our life needs the leaf case.

    In case of recursive leaf functions, the leaf case can be provided with non-recursive returns. However, with template variables the only way to provide the leaf case would be with specialization, there is no other way at all.

    I believe, that you can achieve the very same goals with constexpr function and no TMP:

    #include <type_traits>
    
    constexpr int log2(int arg) {
        if (arg == 0) return 0;
        if (arg == 1) return 0;
        return 1 + log2(arg / 2u);
    }
    
    constexpr std::integral_constant<int, log2(16)> z; // z.value == 4
    

    This works with both run-time and compile-time arguments and generally should be preferred over pure TMP solution, except for educational purposes.

    For educational or other undisclosed purposes, you can use exclusive compile-time like that:

    #include <type_traits>
    
    template<int arg>
    constexpr int log2(std::integral_constant<int, arg> ) {
        static_assert(arg > 0, "Bad arg to log2!");
        if constexpr (arg == 1) {
            return 0;
        } else {
            return 1 + log2(std::integral_constant<int, arg / 2> {});
        }
    }
    
    int k = log2(std::integral_constant<int, 16>{});