How to abuse a C++ compiler?

Templates were originally introduced in C++ in order to support generic programming, i.e. implementing algorithms and data structures with generic types. It was discovered by an accident that C++’s template system happens to be Turing-complete, i.e. anything theoretically computable “should” be computable on a C++ compiler during compilation.

One important corollary is that, since Turing completeness allows the definition of non-terminating computations, it is possible to write “C++ programs” whose compilation is non-terminating, which also implies that the compiler produces neither error messages nor object code. (In practice, compilers have a limit on template instantiation depth to avoid non-termination.)

In the following I am going to demonstrate a couple of code snippets containing non-terminating template computations, and how GCC (g++ 4.8.2) and Clang (clang++ 3.3) handle them.

Expanding recursion

In this example, in order to evaluate InfRec<T>::value, we need InfRec< InfRec<T> >::value, to evaluate that, we need InfRec< InfRec< InfRec<T> > >::value, and so on…

#include <iostream>
 
template<typename T>
struct InfRec {
    static const int value = InfRec< InfRec<T> >::value;
};
 
int main() {
    std::cout << InfRec<int>::value << std::endl;
    return 0;
}

Both clang and GCC terminate with error(s) when reaching their maximum template instantiation depth.

Self-recursion

In this example, in order to evaluate SelfRec<T>::value, we need SelfRec<T>::value, i.e. its definition refers to itself.

#include <iostream>
 
template<typename T>
struct SelfRec {
    static const int value = SelfRec<T>::value;
};
 
int main() {
    std::cout << SelfRec<int>::value << std::endl;
    return 0;
}

GCC produces a few error messages, but nevertheless fails to terminate… 🙂

selfrec.cpp:5:22: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘SelfRec<int>::value’
     static const int value = SelfRec<T>::value;
                      ^
selfrec.cpp:5:22:   recursively required from ‘const int SelfRec<int>::value’
selfrec.cpp:5:22:   required from ‘const int SelfRec<int>::value’
selfrec.cpp:9:32:   required from here

selfrec.cpp:5:22: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘SelfRec<int>::value’
selfrec.cpp:5:22:   recursively required from ‘const int SelfRec<int>::value’
selfrec.cpp:5:22:   required from ‘const int SelfRec<int>::value’
selfrec.cpp:9:32:   required from here

selfrec.cpp:5:22: error: initializer invalid for static member with constructor
selfrec.cpp:5:22: error: (an out of class initialization is required)
selfrec.cpp:5:22: error: ‘SelfRec<int>::value’ cannot be initialized by a non-constant expression when being declared

Clang, on the other hand, compiles it without any complaints, and the program prints 0. I actually wonder whether clang is right here, i.e. whether the above code snippet is in fact equivalent to:

#include <iostream>
 
const int var = var;
 
int main() {
    std::cout << var << std::endl;
    return 0;
}

Mutual recursion

Here, to evaluate MutualRec<A, B>::value, we need MutualRec<B, A>::value, which in turn needs MutualRec<A, B>::value.

#include <iostream>

template<typename A, typename B>
struct MutualRec {
    static const bool value = MutualRec<B, A>::value;
};

int main() {
    std::cout << MutualRec<float,int>::value << std::endl;
    return 0;
}

GCC produces similar error messages as previously, and again fails to terminate. 🙂
Clang, however, thinks that the initializer is not a constant expression, and rejects the code. The initializer looks pretty constant to me, since it is declared as static const.

mutualrec.cpp:5:44: error: in-class initializer for static data member is not a constant expression
        static const bool value = MutualRec<B,A>::value;
                                  ~~~~~~~~~~~~~~~~^~~~~
mutualrec.cpp:5:28: note: in instantiation of template class 'MutualRec<int, float>' requested here
        static const bool value = MutualRec<B,A>::value;
                                  ^
mutualrec.cpp:9:15: note: in instantiation of template class 'MutualRec<float, int>' requested here
        std::cout << MutualRec<float,int>::value << std::endl;
                     ^
1 error generated.

Self-contradiction

In general, the definition of this example is not contradicting, except when the two template parameters are identical. In that case, Contra<T, T>::value is defined as not Contra<T, T>::value.

#include <iostream>

template<typename U, typename V>
struct Contra {
    static const bool value = not Contra<V,U>::value;
};

int main() {
    std::cout << Contra<int,int>::value << std::endl;
    return 0;
}

GCC again produces a few error messages, considers the initializer a non-constant expression, but then it gets confused, asks for a bug report, and quits.

contradict.cpp:5:28: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘Contra<int, int>::value’
  static const bool value = not Contra<V,U>::value;
                            ^
contradict.cpp:5:28:   recursively required from ‘const bool Contra<int, int>::value’
contradict.cpp:5:28:   required from ‘const bool Contra<int, int>::value’
contradict.cpp:9:32:   required from here

contradict.cpp:5:28: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘Contra<int, int>::value’
contradict.cpp:5:28:   recursively required from ‘const bool Contra<int, int>::value’
contradict.cpp:5:28:   required from ‘const bool Contra<int, int>::value’
contradict.cpp:9:32:   required from here

contradict.cpp:5:20: error: initializer invalid for static member with constructor
  static const bool value = not Contra<V,U>::value;
                    ^
contradict.cpp:5:20: error: (an out of class initialization is required)
contradict.cpp:5:20: error: ‘Contra<int, int>::value’ cannot be initialized by a non-constant expression when being declared
contradict.cpp:11: confused by earlier errors, bailing out
Preprocessed source stored into /tmp/ccAf1N1I.out file, please attach this to your bugreport.

Clang compiles the code, and the program prints 1.

Russell’s paradox

M is a set of all sets, which do not contain themselves as elements. Does M contain itself?

#include <iostream>

template<typename U, typename V>
struct HasElement {
    static const bool value = false;
};

class M {};

template<typename T>
struct HasElement<M,T> {
    static const bool value = not HasElement<T,T>::value;
};

int main() {
    std::cout << HasElement<M,M>::value << std::endl;
    return 0;
}

GCC behaves pretty much like with the previous code snippet: error messages, confusion, asking for bug report.
Clang’s answer is a definite YES. 😀

Advertisements