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. :D

About these ads

13 thoughts on “How to abuse a C++ compiler?

  1. Microsoft has a message for you..

    fatal error C1001: An internal error has occurred in the compiler.
    (compiler file ‘f:\dd\vctools\compiler\utc\src\p2\main.c’, line 227)
    To work around this problem, try simplifying or changing the program near the l
    ocations listed above.
    INTERNAL COMPILER ERROR in ‘C:\Program Files (x86)\Microsoft Visual Studio 12.0\
    VC\BIN\cl.EXE’
    Please choose the Technical Support command on the Visual C++
    Help menu, or open the Technical Support help file for more information
    NMAKE : fatal error U1077: ‘”C:\Program Files (x86)\Microsoft Visual Studio 12.0
    \VC\BIN\cl.EXE”‘ : return code ‘0x1′

      • I don’t see error above with Microsoft (R) C/C++ Optimizing Compiler Version 18.00.21005.1 for x86:(VS Express 2013)

        cl /EHsc expanding_recursion.cpp

        […]
        expanding_recursion.cpp(5) : see reference to class template instantiation ‘InfRec<InfRec<InfRec>>’ being compiled
        expanding_recursion.cpp(5) : see reference to class template instantiation ‘InfRec<InfRec>’ being compiled
        expanding_recursion.cpp(9) : see reference to class template instantiation ‘InfRec’ being compiled

        cl /EHsc self_recursion.cpp
        Microsoft (R) C/C++ Optimizing Compiler Version 18.00.21005.1 for x86
        Copyright (C) Microsoft Corporation. All rights reserved.

        self_recursion.cpp
        self_recursion.cpp(5) : error C2065: ‘value’ : undeclared identifier
        self_recursion.cpp(9) : see reference to class template instantiation ‘SelfRec’ being compiled
        self_recursion.cpp(5) : error C2057: expected constant expression

        cl /EHsc self_contradiction.cpp
        Microsoft (R) C/C++ Optimizing Compiler Version 18.00.21005.1 for x86
        Copyright (C) Microsoft Corporation. All rights reserved.

        self_contradiction.cpp
        self_contradiction.cpp(5) : error C2065: ‘not’ : undeclared identifier
        self_contradiction.cpp(9) : see reference to class template instantiation ‘Contra’ being compiled
        self_contradiction.cpp(5) : error C2057: expected constant expression
        self_contradiction.cpp(5) : error C2146: syntax error : missing ‘;’ before identifier ‘value’
        self_contradiction.cpp(5) : error C4430: missing type specifier – int assumed. Note: C++ does not support default-int

        cl /EHsc russells_paradox.cpp
        Microsoft (R) C/C++ Optimizing Compiler Version 18.00.21005.1 for x86
        Copyright (C) Microsoft Corporation. All rights reserved.

        russells_paradox.cpp
        russells_paradox.cpp(12) : error C2065: ‘not’ : undeclared identifier
        russells_paradox.cpp(16) : see reference to class template instantiation ‘HasElement’ being compiled
        russells_paradox.cpp(12) : error C2057: expected constant expression
        russells_paradox.cpp(12) : error C2146: syntax error : missing ‘;’ before identifier ‘value’
        russells_paradox.cpp(12) : error C4430: missing type specifier – int assumed. Note: C++ does not support default-int

        Nice article btw

        — mr23

  2. Pingback: In the News: 2014-03-20 | Klaus' Korner

  3. Tested on Visual C++ 2013 Express (November 2013 CTP)

    Expanding recursion
    1>CPP_test.cpp(47): fatal error C1202: recursive type or function dependency context too complex
    1> CPP_test.cpp(47) : see reference to class template instantiation ‘InfRec<InfRec<InfRec<InfRec<InfRecCPP_test.cpp(47): error C2065: ‘value’ : undeclared identifier
    1> CPP_test.cpp(52) : see reference to class template instantiation ‘SelfRec’ being compiled
    1>CPP_test.cpp(47): error C2057: expected constant expression

    Self-contradiction
    1>CPP_test.cpp(47): error C2065: ‘value’ : undeclared identifier
    1> CPP_test.cpp(52) : see reference to class template instantiation ‘Contra’ being compiled
    1>CPP_test.cpp(47): error C2057: expected constant expression

    Russell’s paradox
    1>CPP_test.cpp(55): error C2065: ‘value’ : undeclared identifier
    1> CPP_test.cpp(60) : see reference to class template instantiation ‘HasElement’ being compiled
    1>CPP_test.cpp(55): error C2057: expected constant expression

    • There was an error on html parsing on comment. Here’s the correct first 2 cases:
      Expanding recursion
      1>CPP_test.cpp(47): fatal error C1202: recursive type or function dependency context too complex
      1> CPP_test.cpp(47) : see reference to class template instantiation ‘InfRec (complete template expansion)
      (around 500 more lines with above expansions)

      Self-recursion
      1>CPP_test.cpp(47): error C2065: ‘value’ : undeclared identifier
      1> CPP_test.cpp(52) : see reference to class template instantiation ‘SelfRec’ being compiled
      1>CPP_test.cpp(47): error C2057: expected constant expression

    • I’m not quite sure what you mean by asking about LLVM. Clang uses LLVM as a back-end for optimization and code generation, but all the interesting cases here are decided on the front-end side.

  4. “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.”

    Clang is right: a “static const” variable is not a constant expression. “static const int start_time = time();” is perfectly valid C++ code. The notion of a constant expression is that the expression can be evaluated at compile time. Clang is right that a static const variable is not a constant expression. A “static constexpr” variable is.

    However, clang is wrong when it asks for a constant expression in this case.

    • No, Clang’s right here. A static data member initialized within a class definition is required to be initialized by a constant expression (see section 9.4.2 of the C++ standard).

      Clang’s right in all the other cases too, as far as I can see. In particular, note that:

      static const bool x = not x;

      … initializes x to true, because initialization of static storage duration variables is performed in two stages. First, the variable is zero-initialized (in this case, initialized to false). Then its initializer is evaluated, which initializes ‘x’ to true. (See 3.6.2 for details.) And this doesn’t break any of the rules for a constant expression, so this is constant initialization (see 5.19).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s