Why is && strict in compile time?

Question

I am experimenting with basic template metaprogramming. I tried implementing structure templates which help us establish whether their template argument is prime or not. I.e.:

template<int N, int D>
struct IsPrime_Descend {
    const static bool val = (N % D != 0) && IsPrime_Descend<N, D - 1>::val;
};

template<int N>
struct IsPrime_Descend<N, 1> {
    const static bool val = true;
};

template <int N>
struct IsPrime {
    const static bool val = IsPrime_Descend<N, N - 1>::val; 
};

But the implementation above takes linear time. I wanted to boost it up to O(sqrt(n)). Of course, there is the long way of introducing a structure template for calculating the square root and descending from it:

template<int N, int D>
struct Sqrt_Descend {
    const static int val = D * D > N ? Sqrt_Descend<N, D - 1>::val : D;
};

template<int N>
struct Sqrt_Descend<N, 1> {
    const static int val = 1;
};

template<int N>
struct Sqrt {
    const static int val = Sqrt_Descend<N, N>::val;
};

template<int N, int D>
struct IsPrime_Descend {
    const static bool val = (N % D != 0) && IsPrime_Descend<N, D - 1>::val;
};

template<int N>
struct IsPrime_Descend<N, 1> {
    const static bool val = true;
};

template <int N>
struct IsPrime {
    const static bool val = IsPrime_Descend<N, Sqrt<N>::val>::val;
};

But there's something else I tried:

template <int N, int D>
struct IsPrime_Ascend {
    const static bool val = (N % D != 0) && (D * D <= N) && IsPrime_Ascend<N, D + 1>::val;
};

template <int N>
struct IsPrime {
    const static bool val = IsPrime_Ascend<N, 1>::val; 
};

I reckoned this snippet to instantiate IsPrime_Ascend<N, D> as long as the two preceding conditions ((N % D != 0) && (D * D <= N)) are true due to the laziness of &&. But, apparently, it does not stop when one of them breaks and exceeds template instantiation maximum depth.

So, why is && strict (as in not lazy) in compile-time?

Answer 1

Short-circuit evaluation deals with evaluation of expressions. The expression is still there in the text of the C++ file, and it therefore must be compiled. If that expression contains a template instantiation, then that template must be instantiated. That's how compilation works (unless you use if constexpr, which you can't within that context).

If you want to prevent further instantiation, you have to do so via the rules of templates, not the rules of expression evaluation. So you need to use a partial specialization of the template, one which probably uses SFINAE techniques that is active when the condition is true. C++20 makes this easier with a requires clause.

Better still, turn IsPrime_Descend into a constexpr function.