Geek Answers Handbook

An infinitely recursive template instance when using Clang while GCC is working fine?

The goal of the following C ++ code is to port the ternary operator ( ?: into a separate function that will later help create a syntax tree.

Before looking at a real C ++ snippet, you can quickly look at what it does in pseudocode:

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

Unfortunately, the Clan has problems completing the recursion when the ternary operator ( ?: wrapped inside the 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 options without errors, 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 Klang no longer complains?

Thank you in advance.

EDIT 1:

  • I shortened the compiler message, hopefully increasing its readability. For a full back trace, please take a look at the Coliru links above.

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

+5
source share
2 answers

One way is to limit recursion yourself by adding an argument counter to the structure template involved in the recursion, updating the counter on a recursive call, and using partial specialization to complete the recursion.

I made changes to your program:

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

  • Added argument to the integer argument template in ElseCase and recursive() .

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

  • Created a partial specialization of ElseCase at an arbitrary depth of recursion that does not make a recursive call. The maximum depth must be configured to avoid clang ++ limitation.

Here is 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); }

He works for CoLiRu .

At first, I was worried about how to detect the actual error of the recursion depth, since my initial partially specialized class silently returned the wrong answer. Since you use -std=c++14 , the statements in constexpr functions are valid , which was news to me. I updated the code to use this.

0
source

Using different code paths for compile-time runtime and replication, I was able to bypass infinite recursion:

 #include <boost/hana/integral_constant.hpp> #include <boost/hana/unpack.hpp> #include <boost/hana/equal.hpp> #include <type_traits> #include <tuple> #include <cassert> namespace hana = boost::hana; namespace detail { /* std::forward_as_tuple(views...) is not constexpr */ template<typename... Xs> static constexpr auto forward_as_tuple(Xs&&... xs) { return std::tuple<Xs...>{ std::forward<Xs>(xs)... }; } /* namespace detail */ } template<typename Condition, typename LastStep, typename RecursionStep> struct functor_t { constexpr functor_t(Condition const c, LastStep ls, RecursionStep rs) : c{c}, ls{ls}, rs{rs} {}; template <typename Args> constexpr decltype(auto) eval(std::true_type, Args const& args) const { return hana::unpack(args, ls); } template <typename Args> constexpr decltype(auto) eval(std::false_type, Args const& args) const { auto vt = hana::unpack(args, rs); return eval( hana::unpack(vt, c), vt); } template <typename Args> constexpr decltype(auto) eval(hana::true_, Args const& args) const { return hana::unpack(args, ls); } template <typename Args> constexpr decltype(auto) eval(hana::false_, Args const& args) const { auto vt = hana::unpack(args, rs); return eval( hana::unpack(vt, c), vt); } template <typename Args> decltype(auto) eval(bool const& b, Args const& args) const { if (b) { return hana::unpack(args, ls); } auto vt = hana::unpack(args, rs); return eval(hana::unpack(vt, c), vt); } template <typename... Args> constexpr decltype(auto) operator()(Args&& ...args) const { return eval( c(std::forward<Args>(args)...), detail::forward_as_tuple(args...) ); } Condition const c; LastStep ls; RecursionStep rs; }; struct recurse_t { template <typename Condition, typename LastStep, typename RecursionStep> constexpr decltype(auto) operator()(Condition && c, LastStep && ls, RecursionStep && rs) const { return functor_t<Condition, LastStep, RecursionStep>{c, ls, rs}; } }; constexpr recurse_t recurse{}; /****************** TEST ******************/ #include <boost/hana/plus.hpp> #include <boost/hana/minus.hpp> #include <boost/hana/equal.hpp> #include <boost/hana/ext/std/tuple.hpp> #include <tuple> struct Condition { template<typename I, typename S, typename J> constexpr decltype(auto) operator()(I const& i, S const& s, J const& j) const{ return (j == hana::int_c<1>); } }; struct LastStep { template<typename I, typename S, typename J> constexpr decltype(auto) operator()(I const& i, S const& s, J const& j) const { return hana::plus(s, i); } }; struct RecursionStep { template<typename I, typename S, typename J> constexpr decltype(auto) operator()(I const& i, S const& s, J const& j) const { return std::make_tuple(i, hana::plus(s,i), j-hana::int_c<1>); } }; int main() { /* compute: 2*10 == 20 */ assert(recurse(Condition{}, LastStep{}, RecursionStep{})(2,0,10) == 20); static_assert(recurse(Condition{}, LastStep{}, RecursionStep{})(hana::int_c<2>, hana::int_c<0>, hana::int_c<10>) == hana::int_c<20>, ""); assert( recurse( [](auto a, auto b, auto c) { return (a == 1); }, [](auto a, auto b, auto c) { return a+b; }, [](auto a, auto b, auto c) { return std::make_tuple(a, a+b, c-1); } )(2,0,10) == 20 ); }
0
source

More articles:


All Articles