使用Clang时GCC工作正常的无限递归模板实例化？

Question

以下c ++代码的目的是将三元运算符(?:)包装在一个单独的函数中,稍后将帮助构建语法树.

在查看真正的c ++代码段之前,让我们快速了解它在伪代码中的作用:

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

不幸的是,当三元运算符(?:)包含在模板函数中时,Clang有终止递归的问题:

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

建立结果:

• g ++与reg.功能(-DWORKS):好的

• g ++与tmpl.功能:好的

• clang ++ with reg.功能(-DWORKS):OK(在Coliru上查找代码和结果)

• clang ++ with tmpl.功能:失败(在Coliru查找代码和结果)

GCC(4.9.2)编译两个变种没有错误,但Clang(3.5到3.8)失败,出现以下错误消息:

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.

但为什么？如何重写这段代码,以便Clang不再抱怨？

非常感谢你提前.

编辑1:

• 我已经缩短了编译器消息,希望增加它的可读性.如需完整的回溯,请查看上面提供的Coliru链接.

• 删除说明constexpr符将解决此Clang错误.但这也会降低功能,因此不是一种选择.

Answer 1

一种解决方法是通过向参与递归的构造的模板参数添加计数器、更新递归调用上的计数器以及使用部分特化来终止递归来自行限制递归。

我对你的程序做了这些更改：

• 将IfCase和ElseCase（IfCase仅出于对称性）更改为模板类，而不是具有模板成员函数的常规类。这允许部分专业化。

• ElseCase向和添加了整数计数器模板参数recursive()。

• recursive()调用时增加计数器ElseCase。

• ElseCase创建了不进行递归调用的任意递归深度的部分特化。应调整最大深度以避免 clang++ 限制。

这是代码：

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

它在 CoLiRu工作。

我最初担心如何检测实际的递归深度错误，因为我原来的部分专业类会默默地返回错误的答案。由于您正在使用-std=c++14，constexpr 函数中的断言是有效的，这对我来说是新闻。我已经更新了代码以利用它。