Generic way of lazily evaluating (short-circuiting) template conditional types

Question

While playing around with compile-time string (variadic lists of char) manipulation, I needed to implement a way of checking if a compile-time string contained another (smaller) compile-time string.

This was my first attempt:

template<int I1, int I2, typename, typename> struct Contains;

template<int I1, int I2, char... Cs1, char... Cs2> 
struct Contains<I1, I2, CharList<Cs1...>, CharList<Cs2...>>
{
    using L1 = CharList<Cs1...>;
    using L2 = CharList<Cs2...>;
    static constexpr int sz1{L1::size};
    static constexpr int sz2{L2::size};

    using Type = std::conditional
    <
        (I1 >= sz1),
        std::false_type,
        std::conditional
        <
            (L1::template at<I1>() != L2::template at<I2>()),
            typename Contains<I1 + 1, 0, L1, L2>::Type,
            std::conditional
            <
                (I2 == sz2 - 1),
                std::true_type,
                typename Contains<I1 + 1, I2 + 1, L1, L2>::Type
            >
        >
    >;
};

I find this solution extremely easy to read and reason about. Unfortunately, it doesn't work.

The compiler always tries to instantiate every single branch of std::conditional, even those which are not taken. To put it in another way, short-circuiting isn't happening.

This causes Contains to be instantiated infinitely.

I've solved my original problem by separating every std::conditional block in a separate template class where the condition results are handled as partial specializations.

It works, but unfortunately I find it very hard to read/modify.

---

Is there a way to lazily instantiate a template type and be close to my original solution?

This is an example of what the code could look like:

using Type = std::conditional
<
    (I1 >= sz1),
    std::false_type,
    std::conditional
    <
        (L1::template at<I1>() != L2::template at<I2>()),
        DeferInstantiation<typename Contains<I1 + 1, 0, L1, L2>::Type>,
        std::conditional
        <
            (I2 == sz2 - 1),
            std::true_type,
            DeferInstantiation<typename Contains<I1 + 1, I2 + 1, L1, L2>::Type>
        >
    >
>;

Is it somehow possible to implement DeferInstantiation<T>?

Answer 1

The compiler always tries to instantiate every single branch of std::conditional, even those which are not taken. To put it in another way, short-circuiting isn't happening.

std::conditional<B,T,F> is provided for the purpose of executing a compiletime choice between given types T and F, depending on the boolean B. The choice is effected by specialization. When B is true, the instantiated specialization is:

std::conditional<true,T,F>
{
    typedef T type;
};

And when B is false, the the instantiated specialization is:

std::conditional<false,T,F>
{
    typedef F type;
};

Note that to instantiate either specialization, both T and F must be instantiated. There are no "branches". The notion of "short-circuiting" the instantiation of either std::conditional<true,T,F> or std::conditional<false,T,F> could only mean not doing it.

So no, it is not possible to implement DeferInstantiation<U>, for type parameter U, such that an instantiation of

std::conditional<{true|false},DeferInstantiation<T>,DeferInstantiation<F>>

will not entail instantiation of DeferInstantiation<T> and DeferInstantiation<F>>, and therefore of T, and of F.

For executing a compiletime choice as to which or two or more templates shall be instantiated, the language provides specialization (as just illustrated by the definition of std::conditional<B,T,F> itself); it provides function template overload resolution, and it provides SFINAE. Specialization and overload resolution can each be synergetically leveraged with SFINAE, via the library support of std::enable_if<B,T>

The problem that has obstructed you in crafting the particular recursive meta-function that you want is not one of choosing between given types but of choosing the template into which recursive instantiation shall be directed.std::conditional is not to the purpose. @Pradhan's answer demonstrates that a template different from std::conditional can well be written to effect a compiletime choice between two templates, without entailing that both of them shall be instantiated. He applies specialization to do it.

As you say, you have already figured out a specialization solution to the problem. This is in principle the right way to recursively control template selection in recursive meta-functions. However, with the advent of constexpr, recursive meta-functions do not command anything like the market share of problems that they formerly did, and most of the brain-ache they occasioned is a thing of the past.

The particular problem here - determining at compiletime whether one string is a substring of another - can be solved without grappling with template meta-programming, and without representing compiletime strings otherwise than as traditional string literals:

#include <cstddef>

constexpr std::size_t str_len(char const *s)
{
    return *s ? 1 + str_len(s + 1) : 0;
}

constexpr bool 
is_substr(char const * src, char const *targ, 
            std::size_t si = 0, std::size_t ti = 0)
{
    return  !targ[ti] ? true :
                str_len(src + si) < str_len(targ + ti) ? false :
                    src[si] == targ[ti] ? 
                        is_substr(src,targ,si + 1, ti + 1) :
                            is_substr(src,targ,si + 1, 0);
}

// Compiletime tests...

static_assert(is_substr("",""),"");
static_assert(is_substr("qwerty",""),"");
static_assert(is_substr("qwerty","qwerty"),"");
static_assert(is_substr("qwerty","qwert"),"");
static_assert(is_substr("qwerty","werty"),"");
static_assert(is_substr("qwerty","wert"),"");
static_assert(is_substr("qwerty","er"),"");
static_assert(!is_substr("qwerty","qy"),"");
static_assert(!is_substr("qwerty","et"),"");
static_assert(!is_substr("qwerty","qwertyz"),"");
static_assert(!is_substr("qwerty","pqwerty"),"");
static_assert(!is_substr("","qwerty"),"");

int main()
{
    return 0;
}

This will compile as C++11 or better.

You may well have reasons for wishing to represent compiletime strings as CharList<char ...> other than thus rendering them amenable to TMP compiletime queries such as this. We can see that CharList<char ...Cs> has a static constant size member evaluating to sizeof...(Cs) and has a static at<N>() member function evaluating to the Nth of the ...Cs. In that case (assuming that at<N>() is debugged), you might adapt is_substr to be a template function expecting CharList<char ...> parameters on roughly the following lines:

#include <type_traits>

template<
    class SrcList, class TargList, std::size_t SrcI = 0, std::size_t TargI = 0>
constexpr typename 
std::enable_if<(TargI == TargList::size && SrcI <= SrcList::size),bool>::type 
is_substr()
{
    return true;
}

template<
    class SrcList, class TargList, std::size_t SrcI = 0, std::size_t TargI = 0>
constexpr typename 
std::enable_if<(TargI < TargList::size && SrcI == SrcList::size),bool>::type 
is_substr()
{
    return false;
}

template<
    class SrcList, class TargList, std::size_t SrcI = 0, std::size_t TargI = 0>
constexpr typename 
std::enable_if<(TargI < TargList::size && SrcI < SrcList::size),bool>::type 
is_substr()
{
    return  SrcList::template at<SrcI>() == TargList::template at<TargI>() ? 
                is_substr<SrcList,TargList,SrcI + 1,TargI + 1>() :
                is_substr<SrcList,TargList,SrcI + 1,0>();
}

which illustrates the application of SFINAE, leveraged by std::enable_if

Finally, you could also be interested in this program:

#include <iostream>

template<char const * Arr>
struct string_lit_type 
{
    static constexpr const char * str = Arr;
    static constexpr std::size_t size = str_len(str);
    static constexpr char at(std::size_t i) {
        return str[i];
    }
};

constexpr char arr[] = "Hello World\n";

int main()
{
    std::cout << string_lit_type<arr>::str;
    std::cout << string_lit_type<arr>::size << std::endl;
    std::cout << string_lit_type<arr>::at(0) << std::endl;
    return 0;
}

which prints:

Hello World
12
H

(Code compiled with g++ 4.9, clang 3.5)

Answer 2

Here's a generic template to allow deferred instantiation by simply not instantiating :)

template <bool B, template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ArgsTuple>
struct LazyConditional;

template <template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ... Args>
struct LazyConditional<true, TrueTemplate, FalseTemplate, std::tuple<Args...>>
{
  using type = TrueTemplate<Args...>;
};

template <template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ... Args>
struct LazyConditional<false, TrueTemplate, FalseTemplate, std::tuple<Args...>>
{
  using type = FalseTemplate<Args...>;
};

For completeness, a simple example demonstrating its use:

#include <iostream>
#include <type_traits>
#include <tuple>

template <typename T>
struct OneParam
{
  void foo(){std::cout << "OneParam" << std::endl;}
};

template <typename T, typename U>
struct TwoParam
{
  void foo(){std::cout << "TwoParam" << std::endl;}
};

template <bool B, template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ArgsTuple>
struct LazyConditional;

template <template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ... Args>
struct LazyConditional<true, TrueTemplate, FalseTemplate, std::tuple<Args...>>
{
  using type = TrueTemplate<Args...>;
};

template <template <typename...> class TrueTemplate, template <typename...> class FalseTemplate, typename ... Args>
struct LazyConditional<false, TrueTemplate, FalseTemplate, std::tuple<Args...>>
{
  using type = FalseTemplate<Args...>;
};

template <typename ... Args>
struct OneOrTwoParam
{
  using type = typename LazyConditional<sizeof...(Args)==1, OneParam, TwoParam, std::tuple<Args...> >::type;
};

int main()
{
  OneOrTwoParam<int>::type().foo();
  OneOrTwoParam<int, int>::type().foo();
  return 0;
}

This prints:

OneParam
TwoParam

Answer 3

I agree with the OP that it is unfortunate to not have short-circuiting in std::conditional (or call it SFINAE in the unentered branch, so that incorrect types do not lead to an error).

I had the same problem in my code and could solve it by using if constexpr in a constexpr lambda. So, instead of

using type = std::conditional_t<logical, A, B>;

use

auto get_type = []()
{
    if constexpr(logical)
    {
        return std::declval<A>();
    }
    else
    {
        return std::declval<B>();
    }
};
using type = decltype(get_type());

which, however, is by far less readable.