使用boost::hana Y-combinator时出现的Clang编译器错误

Question

我有一个AST的实现，它使用C++17的std::variant类型构建，我想在它上递归地应用一个访问者。我在Boost的Hana库的一些实用程序的帮助下完成了这一工作。

#include <iostream>
#include <memory>
#include <variant>

#include <boost/hana.hpp>

namespace hana = boost::hana;


struct AddExpr;
struct SubExpr;
struct MulExpr;
struct DivExpr;

using Expr = std::variant<int, AddExpr, SubExpr, MulExpr, DivExpr>;

struct BinaryExpr
{
    BinaryExpr(std::unique_ptr<Expr> lhs, std::unique_ptr<Expr> rhs) noexcept
        : lhs{ std::move(lhs) }, rhs{ std::move(rhs) } { }

    std::unique_ptr<Expr> lhs;
    std::unique_ptr<Expr> rhs;
};

struct AddExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct SubExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct MulExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct DivExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };


int main()
{
    Expr root {
        MulExpr{
            std::make_unique<Expr>(AddExpr{
                std::make_unique<Expr>(1),
                std::make_unique<Expr>(2),
            }),
            std::make_unique<Expr>(SubExpr{
                std::make_unique<Expr>(3),
                std::make_unique<Expr>(4),
            }),
        }
    };

    constexpr auto printer = hana::fix([](auto visitor, auto const& arg) -> void {
        hana::overload(
            [&](int val) {
                std::cout << val;
            },
            [&](AddExpr const& exp) {
                std::cout << "(";
                std::visit(visitor, *exp.lhs);
                std::cout << "+";
                std::visit(visitor, *exp.rhs);
                std::cout << ")";
            },
            [&](SubExpr const& exp) {
                std::cout << "(";
                std::visit(visitor, *exp.lhs);
                std::cout << "-";
                std::visit(visitor, *exp.rhs);
                std::cout << ")";
            },
            [&](MulExpr const& exp) {
                std::cout << "(";
                std::visit(visitor, *exp.lhs);
                std::cout << "*";
                std::visit(visitor, *exp.rhs);
                std::cout << ")";
            },
            [&](DivExpr const& exp) {
                std::cout << "(";
                std::visit(visitor, *exp.lhs);
                std::cout << "/";
                std::visit(visitor, *exp.rhs);
                std::cout << ")";
            }
        )(arg);
    });

    std::visit(printer, root);

    std::cout << "\n";

    return 0;
}

当使用GCC 7.1+时，代码在没有任何警告的情况下编译，但是Clang似乎无法编译它，而是发出以下错误。

<source>:54:22: error: function 'visit<boost::hana::fix_t<(lambda at <source>:47:40)> &, std::variant<int, AddExpr, SubExpr, MulExpr, DivExpr> &>' with deduced return type cannot be used before it is defined
                std::visit(visitor, *exp.lhs);
...

这是Clang的窃听器吗？或者我做错了什么，如果是的话，为什么这对GCC有用？

还有，有没有一种优雅的方式来做我想做的事？特别是，我更希望能够从一些重载的lambda中创建printer访问者，而不是为每个类型创建一个带有operator()重载的PrinterVisitor类。然而，如果这是不可能的，我愿意接受其他建议。

Answer 1

您的确切代码在GCC主干上也不能工作：编译器Explorero，这很有趣，因为发行版确实起作用了：编译器资源管理器。

我当地的信息非常相似: GCC。

/home/sehe/custom/boost_1_75_0/boost/hana/functional/fix.hpp|74 col 19| error: use of ‘main()::<lambda(auto:39, const auto:40&)> [with auto:39 = boost::hana::fix_t<main()::<lambda(auto:39, const auto:40&)> >; auto:40 = int]’ before deduction of ‘auto’
||    74 |         { return f(fix(f), static_cast<X&&>(x)...); }

嘎吱声：

/home/sehe/custom/boost_1_75_0/boost/hana/functional/fix.hpp|74 col 18| error: function 'operator()<boost::hana::fix_t<(lambda at /home/sehe/Projects/stackoverflow/test.cpp:44:40)>, int>' with deduced return type cannot be used before it is defined
||         { return f(fix(f), static_cast<X&&>(x)...); }

我还记得，当我编写自己的组合器时，我找不到一个实现助手，比如：

struct F {
    template <typename Self, typename T>
    void operator()(Self const& self, T const& arg) const {
        auto bin = [&](char op, BinaryExpr const& exp) {
            std::cout << "("; std::visit(self, *exp.lhs); std::cout << op; std::visit(self, *exp.rhs); std::cout << ")"; 
        };
        hana::overload(
            [&](int val) { std::cout << val; },
            [&](AddExpr const& exp) { bin('+', exp); },
            [&](SubExpr const& exp) { bin('-', exp); },
            [&](MulExpr const& exp) { bin('*', exp); },
            [&](DivExpr const& exp) { bin('/', exp); }
        )(arg);
    }
};

看吧，在编译器资源管理器上直播

解释

我认为它只是需要默认的可构造lambda，这对于C++20：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0624r2.pdf来说是新的。

来源：https://www.bfilipek.com/2019/03/lambdas-story-part2.html

使用C++20，我们将获得以下特性：

• ，这是一个lambda捕获- P0409R2，并被弃用隐式捕获的via = - P0806。
• lambda init捕获中的包扩展：...args = std::move(args)](){} - P0780
• 用于结构化绑定的静态、thread_local和lambda捕获- P1091
• 模板lambdas (也包含概念)- P0428R2
• 简化隐式lambda捕获- P0588R1
• 默认的可构造和可分配的无状态lambdas - P0624R2
• 未评估上下文中的Lambdas - P0315R4

这使我相信它可以在c++20中工作。

还盘

对于递归访问者，我有一些简化和我喜欢的模式。有一些好处，比如

• 封装递归访问
• 使绑定额外参数更容易(本例中为std::cout)

我发现可维护性超过了在调用站点上声明访问者的方便性。

编辑我找到了一个更有说服力的解决方案，所以我会在这里添加一个链接，以防您感兴趣：在编译器资源管理器上直播

吃你的蛋糕，吃吧，不加刺激。

我意识到你可以把蛋糕吃了，而不需要任何提振：

template <typename... F>
struct RecursiveVisitor : F... {
    template <typename... Ts>
    void operator()(std::variant<Ts...> const& v) const {
        std::visit( std::bind(*this, std::cref(*this), std::placeholders::_1), v );
    } 

    using F::operator()...;
};

template <typename... F>
    RecursiveVisitor(F...) -> RecursiveVisitor<F...>;

现在你可以完成你的任务了，例如：

RecursiveVisitor const printer {
    [](auto const&, int const& v) { std::cout << v; },
    [](auto const& self, AddExpr const& exp) { self(self, '+', exp); },
    [](auto const& self, SubExpr const& exp) { self(self, '-', exp); }, 
    [](auto const& self, MulExpr const& exp) { self(self, '*', exp); },
    [](auto const& self, DivExpr const& exp) { self(self, '/', exp); },
    [](auto const& self, char op, BinaryExpr const& exp) {
        std::cout << "(";
        self(*exp.lhs);
        std::cout << op;
        self(*exp.rhs);
        std::cout << ")"; 
    }
};

它确实能全面发挥作用：

在编译器资源管理器上直播

#include <iostream>
#include <memory>
#include <variant>
#include <functional>

struct AddExpr;
struct SubExpr;
struct MulExpr;
struct DivExpr;

using Expr = std::variant<int, AddExpr, SubExpr, MulExpr, DivExpr>;

struct BinaryExpr
{
    BinaryExpr(Expr l, Expr r);
    BinaryExpr(BinaryExpr const& o);
    std::unique_ptr<Expr> lhs, rhs;
};

struct AddExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct SubExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct MulExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct DivExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };

BinaryExpr::BinaryExpr(Expr l, Expr r)
: lhs{ std::make_unique<Expr>(l) }, rhs{ std::make_unique<Expr>(r) } { }

BinaryExpr::BinaryExpr(BinaryExpr const& o)
: lhs{ std::make_unique<Expr>(*o.lhs) }, rhs{ std::make_unique<Expr>(*o.rhs) } { }

template <typename... F>
struct RecursiveVisitor : F... {
    template <typename... Ts>
    void operator()(std::variant<Ts...> const& v) const {
        std::visit( std::bind(*this, std::cref(*this), std::placeholders::_1), v );
    } 

    using F::operator()...;
};

template <typename... F>
    RecursiveVisitor(F...) -> RecursiveVisitor<F...>;

int main()
{
    RecursiveVisitor const printer {
        [](auto const&, int const& v) { std::cout << v; },
        [](auto const& self, AddExpr const& exp) { self(self, '+', exp); },
        [](auto const& self, SubExpr const& exp) { self(self, '-', exp); }, 
        [](auto const& self, MulExpr const& exp) { self(self, '*', exp); },
        [](auto const& self, DivExpr const& exp) { self(self, '/', exp); },
        [](auto const& self, char op, BinaryExpr const& exp) {
            std::cout << "(";
            self(*exp.lhs);
            std::cout << op;
            self(*exp.rhs);
            std::cout << ")"; 
        }
    };

    for (Expr root : { Expr
            { MulExpr{ AddExpr{ 1, 2 }, SubExpr{ 3, 4 } } },
            { DivExpr{ 1, MulExpr{ 7, SubExpr{ 3, 4 } } } },
        }) 
    {
        printer(root);
        std::cout << "\n";
    }
}

打印

((1+2)*(3-4))
(1/(7*(3-4)))

我意识到这会手工复制Y-组合器模式，但至少它消除了所有瓶颈。另外，共享的char, BinExpr&重载是如何优雅地“只是另一个重载”的。

Answer 2

@sehe发布的解决方案中的最后一个例子几乎是完美的，只是内存分配的数量随着表达式树的深度呈指数增长。这是因为复制构造函数称为2^l + 2^r时间，其中l和r分别是传递给BinaryExpr构造函数的左表达式树和右表达式树的深度。

因此，为了构造下面的表达式树，我发现它需要68次分配。

Expr root {
    AddExpr {
        MulExpr{ AddExpr{ 1, 2 }, SubExpr{ 3, 4 } },
        DivExpr{ SubExpr{ 5, 6 }, AddExpr{ 7, 8 } },
    }
};

但是，我们可以很容易地通过移动(而不是复制)像这样的表达式树来避免这些内存分配。

struct AddExpr;
struct SubExpr;
struct MulExpr;
struct DivExpr;

using Expr = std::variant<int, AddExpr, SubExpr, MulExpr, DivExpr>;

struct BinaryExpr
{
    BinaryExpr(Expr lhs, Expr rhs) noexcept;
    BinaryExpr(BinaryExpr&&) = default; // Require the default move-constructor.
    BinaryExpr(BinaryExpr const&);

    std::unique_ptr<Expr> lhs;
    std::unique_ptr<Expr> rhs;
};

struct AddExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct SubExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct MulExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };
struct DivExpr : BinaryExpr { using BinaryExpr::BinaryExpr; };

BinaryExpr::BinaryExpr(Expr lhs, Expr rhs) noexcept
    : lhs{ std::make_unique<Expr>(std::move(lhs)) }, // Call std::move() here.
      rhs{ std::make_unique<Expr>(std::move(rhs)) }  // Call std::move() here.
{ }

BinaryExpr::BinaryExpr(BinaryExpr const& exp)
    : lhs{ std::make_unique<Expr>(*exp.lhs) },
      rhs{ std::make_unique<Expr>(*exp.rhs) }
{ }

通过这种修改，构建上面所示的示例表达式树只需要14次分配，而不是68次。