Esempio di istogramma ricorsivo infinito quando si usa Clang mentre GCC funziona correttamente?

Question

l'intenzione del seguente codice C++ è di avvolgere l'operatore ternario (?:) in una funzione separata, che in seguito aiuterà a costruire un albero di sintassi.

Prima di guardare reale C++ frammento diamo un rapido sguardo a ciò che fa in pseudo-codice:

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

Purtroppo Clang ha problemi con che chiude la ricorsione quando l'operatore ternario (?:) è avvolto all'interno di un modello funzione:

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

risultati Corporatura:

• g ++ con reg. funzione (-DWORKS): OK

• g ++ con tmpl. funzione: OK

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

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

GCC (4.9.2) compila entrambe le varianti senza errori, ma Clang (da 3.5 a 3.8) non riesce con il seguente messaggio di errore:

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. 

Ma perché? Come può essere riscritto questo codice in modo che Clang non si lamenti più?

Grazie mille in anticipo.

EDIT 1:

• Ho un corto il messaggio del compilatore, si spera aumentando la sua leggibilità. Per un backtrace completo, si prega di dare un'occhiata a quei collegamenti Coliru forniti sopra.

• La rimozione dello specificatore constexpr funzionerà attorno a questo errore Clang. Ma questo riduce anche la funzionalità e quindi non è un'opzione.

Answer 1

Una soluzione è quella di limitare la ricorsione te stesso con l'aggiunta di un contatore per gli argomenti di template dei costrutti che partecipano a ricorsione, l'aggiornamento del contatore sul chiamata ricorsiva, e utilizzando la specializzazione parziale di interrompere la ricorsione.

ho fatto queste modifiche al programma:

• Cambiato IfCase e ElseCase (IfCase solo per simmetria) alle classi template invece di classi regolari con una funzione di membro template. Questo consente una specializzazione parziale.

• Aggiunto un argomento del contatore contatore intero a ElseCase e recursive().

• Il contatore è stato incrementato quando si chiama recursive() in ElseCase.

• Creata una specializzazione parziale di ElseCase a una profondità di ricorsione arbitraria che non effettua una chiamata ricorsiva. La profondità massima dovrebbe essere regolata per evitare il limite clang ++.

Ecco il codice:

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

Funziona at CoLiRu.

---

Inizialmente ero preoccupato per come rilevare un errore effettivo profondità di ricorsione, come la mia classe parzialmente specializzata originale sarebbe in silenzio restituire la risposta sbagliata. Dal momento che stai usando -std=c++14, assertions in constexpr functions are valid, che era una novità per me. Ho aggiornato il codice per fare uso di questo.

Answer 2

Utilizzando percorsi di codice differenti per runtime e compilare il tempo ricorsione sono stato in grado di lavorare in giro senza fine ricorsione:

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