1

I recently wrote a fairly complex C++ meta function that boils down to:

template <size_t N, typename val>
struct Rec {
    using type = typename std::conditional<N == 0,
        val,
        typename Rec<N - 1, val>::type>::type;
};

Both Clang and G++ barf on this type of recession, stating that, "Template instantiation depth exceeds maximum of X". I quickly rewrote the program and fixed the problem, but it got me thinking about the evaluation strategy of C++ template parameters.

Is there anything in the C++ standard that would prevent templates from using call by need evaluation of template parameters, or is this limitation purely an implementation defect?

  • @ChrisF it turns out Bart van Ingen Schenau has written an answer that explains OP's question - what is the compiler's "need" that triggers the infinite loop even though the compiler already adopts a "call by need evaluation" strategy. In contrast, a layman's response would just be "don't do that, do this instead", which would get the work done but the question unanswered. I think P.SE is a suitable place for fostering this type of questions, for a grace period, after which it might have to be cleaned up if nobody answered. – rwong Jan 24 '15 at 16:35
  • @rwong - Yeah - I had to close the question as something so I could reopen, but then forgot to clean up after myself. – ChrisF Jan 24 '15 at 17:27
5

To instantiate std::conditional<N==0, val, typename Rec<N-1, val>::type>, the compiler needs to prove that both val and Rec<N-1, val>::type evaluate to a type and that N==0 evaluates to a constant expression that can be used in a boolean context.
If those conditions are not met, then the program is not well-formed and requires a diagnostic.

It is also only after evaluating the template arguments that the compiler can start looking for specializations that match, because for all the compiler knows, there might be a specialization of std::conditional for the parameters true,val,Rec<-1,val>::type that is more specialized than the default one for std::conditional<true, T, F>.
This is also why you need a specialization of Rec to stop the recursion: The condition used in std::conditional is only checked after the recursion has run its course and hit a terminating condition.

The compiler would be perfectly happy if you added the specialization

template <class val>
class Rec<-42, val> {
  typedef void type;
};

and give you the expected results (even if val != void).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.