C++ code example that makes the compile loop forever

Question

Given that the C++ template system is not context-free and it's also Turing-Complete, can anyone provide me a non-trivial example of a program that makes the g++ compiler loop forever?

For more context, I imagine that if the C++ template system is Turing-complete, it can recognize all recursively enumerable languages and decide over all recursive ones. So, it made me think about the acceptance problem, and its more famous brother, the halting problem. I also imagine that g++ must decide if the input belongs in the C++ language (as it belongs in the decidability problem) in the syntactic analysis. But it also must resolve all templates, and since templates are recursively enumerable, there must be a C++ program that makes the g++ syntactic analysis run forever, since it can't decide if it belongs in the C++ grammar or not.

I would also like to know how g++ deals with such things?

In "forever" situations, g++ will typically detect this and error out. — Drew Dormann, Oct 04 '22 at 16:30
The standard specifies that implementations can set limits on the compile time loop unrolling need to be done by templates. Though most compilers exceed the minimum requirements they all have limits. — Martin York, Oct 04 '22 at 16:38
@DrewDormann but for g++ detect this situations, it must recognize the situation and that itself is not decidable. Or so I think... — Otávio Augusto Silva, Oct 04 '22 at 16:55

user17732522 · Accepted Answer · 2022-10-04T16:41:56.403

While this is true in theory for the unlimited language, compilers in practice have implementation limits for recursive behavior (e.g. how deep template instantiations can be nested or how many instructions can be evaluated in a constant expression), so that it is probably not straight-forward to find such a case, even if we somehow ignore obvious problems of bounded memory. The standard specifically permits such limits, so if you want to be pedantic I am not even sure that any given implementation has to satisfy these theoretical concepts.

And also infinitely recursive template instantiation specifically is forbidden by the language. A program with such a construct has undefined behavior and the compiler can just refuse to compile if it is detected (although of course it cannot be detected in general).

score 1 · Answer 2 · answered Oct 04 '22 at 18:00

This shows the limits for clang: Apple clang version 13.1.6 (clang-1316.0.21.2.5)

#include <iostream>

template<int V>
struct Count
{
    static constexpr int value = Count<V-1>::value + 1;
};

template<>
struct Count<1>
{
    static constexpr int value = 1;
};

int main()
{
#ifdef WORK
    int v = Count<1026>::value;  // This works.
#else
    int v = Count<1027>::value;  // This will fail to compile.
#endif
    std::cout << "V: " << v << "\n";
}

Tried that with g++ and the limit is 900. – Otávio Augusto Silva Oct 06 '22 at 22:06 — Otávio Augusto Silva, Oct 06 '22 at 22:06

C++ code example that makes the compile loop forever

2 Answers2