Nieskończona rekurencyjna instancja szablonu podczas używania Clanga, podczas gdy GCC działa dobrze?

Question

zamiarem następującego kodu C++ jest owinięcie trójskładnikowego operatora (?:) w oddzielną funkcję, która później pomoże w budowaniu drzewa składni.

Przed patrząc na realne C++ fragment rzućmy okiem na to, co robi w pseudo kod:

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

Niestety Clang ma problemy z zakończenia rekurencji gdy operator trójskładnikowych (?:) jest owinięty w szablonie funkcja:

/****************** 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); 
} 

wyniki produkcji:

• g ++ z reg. funkcja (-DWORKS): OK

• g ++ z tmpl. funkcja: OK

• clang ++ z reg. funkcja (-DWORKS): OK (Find code & results also at Coliru)

• clang ++ z tmpl. Funkcja: FAIL (Find code & results also at Coliru)

GCC (4.9.2) zestawia oba warianty bez błędu, ale Clang (3,5 do 3,8) nie powiedzie się z następującym komunikatem o błędzie:

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. 

ale dlaczego? W jaki sposób można przepisać ten kod, aby Clang już nie narzekał?

Dziękuję bardzo z góry.

EDIT 1:

• Mam zwarte komunikat kompilatora, mam nadzieję, że zwiększenie jego czytelności. Aby uzyskać pełny ślad, proszę spojrzeć na powyższe linki Coliru.

• Usunięcie specyfikatora constexpr spowoduje obejście tego błędu Clang. Ale to również zmniejsza funkcjonalność, a zatem nie jest opcją.

Answer 1

Jednym rozwiązaniem jest ograniczenie rekursji dopisując licznik do argumentów szablonu konstruktów uczestniczących w rekursji, aktualizując licznik na wywołanie rekurencyjne, i za pomocą częściowej specjalizacji wypowiedzieć rekursji.

Zrobiłem te zmiany do swojego programu:

• Zmieniono IfCase i ElseCase (IfCase tylko dla symetrii) do klas szablonu zamiast regularnych zajęć z funkcji członka szablon. To pozwala na częściową specjalizację.

• Dodano argument o numerze licznika całkowitoliczbowego do ElseCase i recursive().

• Zwiększono licznik podczas wywoływania recursive() w ElseCase.

• Utworzono częściową specjalizację ElseCase na arbitralnej głębokości rekursji, która nie wywołuje rekursywnego połączenia. Maksymalna głębokość powinna być dostrojona, aby uniknąć limitu ++ klang.

Oto kod:

#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); 
} 

Działa at CoLiRu.

---

początkowo byłem zaniepokojony, jak wykrywać rzeczywisty błąd głębokość rekurencji, jak mój oryginalny częściowo wyspecjalizowana klasa będzie cicho zwróci błędną odpowiedź. Ponieważ używasz -std=c++14, assertions in constexpr functions are valid, co było dla mnie nowością. Zaktualizowałem kod, aby to wykorzystać.

Answer 2

Stosując różne ścieżki kodu do wykonywania i kompilacji rekursji udało mi się obejść nieskończoną rekurencję:

#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 
    ); 
}