Infinite compilation with templates

Question

This question is just out of curiosity. In recursive templates if we forget to put one particular specialization, then compiler will do large number of iterations and then stop at sometime and gives error such as,

error: incomplete type ‘X<-0x000000000000001ca>’ used in nested name specifier

In certain cases, the compilation goes infinite. For example, see the below code (just for illustration; compiled with gcc 4.4.1):

template<int I>
struct Infinite
{
  enum { value = (I & 0x1)? Infinite<I+1>::value : Infinite<I-1>::value };
};

int main ()
{
  int i = Infinite<1>::value;
}

Should not be compiler smart enough to stop at some time ?

Edit: The compilation error shown above is for other code. For the sample code, compilation never stops (however, I get to see such errors in between)

Answer 1

If I understand your question correctly, you want the compiler to recognise that it will never stop iterating. Besides just stopping after a fixed number of nesting types, what you want is provably impossible: If I see it correctly you can express any turing-machine in this fashion (at least the templates in D are turing complete).

So if you can build a compiler that recognises that it will nest types forever before actually trying to, you decide the halting problem which is undecidable for turing-machines.

However, I could very well be mistaken that you can put any computation in the parameter-list (but simulating a register-machine appears to be possible, as we can encode all registers in a separate integer template parameter (yes, int is finite, but quite large, which makes it practically unbounded)).

Answer 2

Getting the parser into an infinite loop using template is not new.

// Stresses the compiler infinitely
// from: http://www.fefe.de/c++/c%2b%2b-talk.pdf
template<class T> struct Loop { Loop<T*> operator->(); };
Loop<int> i, j = i->hooray;