Бесконечная компиляция с шаблонами

Question

Этот вопрос просто из любопытства. В рекурсивных шаблонах, если мы забываем указать одну конкретную специализацию, компилятор выполнит большое количество итераций, а затем остановится и выдаст ошибку, такую ​​как,

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

В некоторых случаях компиляция идет бесконечно. Например, смотрите код ниже (только для иллюстрации; скомпилирован с 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;
}

Разве компилятор не должен быть достаточно умным, чтобы в какой-то момент остановиться?

Редактировать: ошибка компиляции, показанная выше, относится к другому коду. Для примера кода компиляция никогда не останавливается (однако, я получаю увидеть такие ошибки между)

Answer 1

Если я правильно понимаю ваш вопрос, вы хотите, чтобы компилятор распознал, что он никогда не перестанет выполнять итерации. Помимо простой остановки после фиксированного количества типов вложений, то, что вы хотите, доказуемо невозможно: если я правильно понимаю, вы можете выразить любую машину Тьюринга таким образом (по крайней мере, шаблоны в D ленты завершены).

Поэтому, если вы можете создать компилятор, который распознает, что он будет вкладывать типы навсегда перед тем, как на самом деле пытаться это сделать, вы решаете проблему остановки, которая неразрешима для машин Тьюринга.

Тем не менее, я вполне могу ошибиться, что вы можете поместить любое вычисление в список параметров (но моделирование машины регистра представляется возможным, поскольку мы можем кодировать все регистры в отдельном целочисленном параметре шаблона (да, int конечно, но довольно большой, что делает его практически неограниченным)).

Answer 2

Ввод парсера в бесконечный цикл с использованием шаблона не нов.

// 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;

Answer 3

Разве компилятор не должен быть достаточно умным, чтобы в какой-то момент остановиться?

Как вы определяете фразу "в какое-то время"? Как бы компилятор узнал ваше определение "когда-нибудь"? Как он узнает, когда это должно прекратиться, если вы не скажете это явно? Сначала вы должны сказать об этом, определив специализацию (и) шаблона класса без остановки (который вы написали, это шаблон класса без остановки).

В вашем случае вы должны иметь две специализации шаблона класса, по одной в каждом направлении (увеличивая и уменьшая). Что-то вроде этого:

template<>
struct Infinite<100> //this is to stop template with <I+1> argument
{
  enum { value = 678678 }; //see, it doesn't use Infinite<> any further!
};

template<>
struct Infinite<-100> //this is to stop template with <I-1> argument
{
  enum { value = -67878 }; //see, it too doesn't use Infinite<> any further!
};

Answer 4

Компилятор делает то, что вы просите. Вы попросили его участвовать в бесконечной рекурсии - он сделал именно это. Если вы хотите, чтобы он "остановился в какое-то время", вы должны попросить его остановиться в "некоторое время" и сказать, какое именно "определенное время" вы имеете в виду.

Шаблонная рекурсия не отличается от любой другой рекурсии в программе на C++: вы обязаны указать, где заканчивается рекурсия.