Jakob Jakob - 1 year ago 130
C++ Question

Infinite recursive template instantiation when using Clang while GCC works fine?

the intention of the following c++ code is to wrap the ternary operator (

?:
) in a separate function, which later on will help with building a syntax tree.

Before looking at real c++ snippet let's take a quick look at what it does in pseudo code:

bool recursive(bool v) {
return v ? v : recursive(v);
}
int main() {
bool r = recursive(true)
}


Unfortunatly Clang has problems with terminating the recursion when the ternary operator (
?:
) is wrapped within a template function:

/****************** DECLARATIONS ******************/
template<typename T>
constexpr T
recursive(T t);

struct IfCase {
template<typename T>
constexpr T
operator()(T t) const;
};

struct ElseCase {
template<typename T>
constexpr T
operator()(T t) const;
};

#if defined(WORKS)
static constexpr bool
if_then_else_return(bool b, IfCase const& ic, ElseCase const& ec, bool x);
#else
template<typename T, typename IfFunctor, typename ElseFunctor>
static constexpr T
if_then_else_return(T b, IfFunctor const& ic, ElseFunctor const& ec, T x);
#endif

/****************** DEFINITIONS ******************/
template<typename T>
constexpr T
IfCase::operator()(T t) const {
return t;
}

template<typename T>
constexpr T
recursive(T t) {
return if_then_else_return(t, IfCase{}, ElseCase{}, t);
}

template<typename T>
constexpr T
ElseCase::operator()(T t) const {
return recursive(t);
}

#if defined(WORKS)
constexpr bool
if_then_else_return(bool b, IfCase const& ic, ElseCase const& ec, bool x) {
return b ? ic(x) : ec(x);
}
#else
template<typename T, typename IfFunctor, typename ElseFunctor>
constexpr T
if_then_else_return(T b, IfFunctor const& ic, ElseFunctor const& ec, T x) {
return b ? ic(x) : ec(x);
}
#endif


/****************** CALL ******************/

int main() {
constexpr auto r = recursive(true);
}


Build results:



GCC (4.9.2) compiles both variants without an error, but Clang (3.5 to 3.8) fails with the following error message:

main.cpp:56:14: fatal error: recursive template instantiation exceeded maximum depth of 256
return b ? ic(x) : ec(x);
^
/*** the next error messages for lines 64, 38 and 56 are repeated several times ***/

main.cpp:56:22: note: in instantiation of function template specialization 'ElseCase::operator()<bool>' requested here
return b ? ic(x) : ec(x);
^
main.cpp:38:9: note: in instantiation of function template specialization 'if_then_else_return<bool, IfCase, ElseCase>' requested here
return if_then_else_return(t, IfCase{}, ElseCase{}, t);
^
main.cpp:64:21: note: in instantiation of function template specialization 'recursive<bool>' requested here
constexpr auto r = recursive(true);
^
1 error generated.


But why? How can this code be rewritten so that Clang does not complain anymore?

Thank you very much in advance.

EDIT 1:


  • I've shorted the compiler message, hopefully increasing its readability. For a full backtrace, please take a look at those Coliru links provided above.

  • Removing the
    constexpr
    specifier will work around this Clang error. But this also reduces functionality and thus is not an option.


Answer Source

One workaround is to limit recursion yourself by adding a counter to the template arguments of the constructs participating in recursion, updating the counter on the recursive call, and using partial specialization to terminate recursion.

I made these changes to your program:

  • Changed IfCase and ElseCase (IfCase only for symmetry) to template classes instead of regular classes with a template member function. This allows partial specialization.

  • Added an integer counter template argument to ElseCase and recursive().

  • Incremented the counter when calling recursive() in ElseCase.

  • Created a partial specialization of ElseCase at an arbitrary recursion depth that does not make a recursive call. The maximum depth should be tuned to avoid the clang++ limit.

Here's the code:

#include <cassert>

/****************** DECLARATIONS ******************/
template<typename T, int N = 0>
constexpr T
recursive(T t);

template<typename T>
struct IfCase;

template<typename T, int N>
struct ElseCase;

#if defined(WORKS)
    static constexpr bool
    if_then_else_return(bool b, IfCase<bool> const& ic, ElseCase<bool> const& ec, bool x);
#else
    template<typename T, typename IfFunctor, typename ElseFunctor>
    static constexpr T
    if_then_else_return(T b, IfFunctor const& ic, ElseFunctor const& ec, T x);
#endif

/****************** DEFINITIONS ******************/
template<typename T>
struct IfCase {
    constexpr T
    operator()(T t) const {
       return t;
    }
};

template<typename T, int N>
constexpr T
recursive(T t) {
   return if_then_else_return(t, IfCase<T>{}, ElseCase<T, N>{}, t);
}

template<typename T, int N>
struct ElseCase {
    constexpr T
    operator()(T t) const {
       return recursive<T, N + 1>(t);
    }
};

static constexpr int MaxRecursionDepth = 10;

template<typename T>
struct ElseCase<T, MaxRecursionDepth> {
    constexpr T
    operator()(T t) const {
       assert(false); // OK in C++14!
       return t;
    }
};

#if defined(WORKS)
    constexpr bool
    if_then_else_return(bool b, IfCase<bool> const& ic, ElseCase<bool> const& ec, bool x) {
        return b ? ic(x) : ec(x);
    }
#else
    template<typename T, typename IfFunctor, typename ElseFunctor>
    constexpr T
    if_then_else_return(T b, IfFunctor const& ic, ElseFunctor const& ec, T x) {
        return b ? ic(x) : ec(x);
    }
#endif


/****************** CALL ******************/

int main() {
    constexpr auto r = recursive(true);
}

It works at CoLiRu.


I was initially worried about how to detect an actual recursion depth error, as my original partially specialized class would silently return the wrong answer. Since you are using -std=c++14, assertions in constexpr functions are valid, which was news to me. I have updated the code to make use of this.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download