I have the following implementation of an AST, built using C++17's std::variant type, on which I would like to apply a visitor recursively. I have done this with the help of some utilities from Boost's Hana library.
#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;
}
The code compiles without any warnings when using GCC 7.1+, but Clang does not seem to be able to compile it, issuing the following error instead.
<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);
...
Is this a bug in Clang? Or am I doing something wrong, and, if so, why does this work for GCC?
Also, is there an elegant way to do what I want in Clang? Particularly, I would prefer to be able to create the printer visitor from some overloaded lambdas, rather than having to create a PrinterVisitor class with operator() overloaded for each type. However, if that's not possible, I am open to other suggestions.
Your exact code doesn't work on GCC trunk either: Compiler Explorero, which is funny since the releases did work: Compiler Explorer.
My local messages are very similar: 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)...); }
Clang:
/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)...); }
I remember when I wrote my own combinators that I couldn't get around having an implementation helper, like:
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);
}
};
See it Live On Compiler Explorer
I think it merely requires default constructible lambdas, which are new to C++20: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0624r2.pdf
Source: https://www.bfilipek.com/2019/03/lambdas-story-part2.html
With C++20 we’ll get the following features:
- Allow [=, this] as a lambda capture - P0409R2 and Deprecate implicit capture of this via [=] - P0806
- Pack expansion in lambda init-capture: ...args = std::move(args)](){} - P0780
- static, thread_local, and lambda capture for structured bindings - P1091
- template lambdas (also with concepts) - P0428R2
- Simplifying implicit lambda capture - P0588R1
- Default constructible and assignable stateless lambdas - P0624R2
- Lambdas in unevaluated contexts - P0315R4
This leads me to believe that it can work in c++20.
I have some simplifications and my preferred pattern for recursive visitors. with some benefits like
std::cout in this example)I find the maintainabiliity outweighs the convenience of declaring the visitor on the call site.
EDIT I found a more compelling solution so I'll just put a link to this in case you're interested: Live On Compiler Explorer
I realized you can have your cake and eat it, without requiring any Boost at all:
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...>;
Now you can pull off your mission with e.g.:
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 << ")";
}
};
Which does work across the board:
#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";
}
}
Printing
((1+2)*(3-4))
(1/(7*(3-4)))
I realize this puts duplicates the Y-combinator pattern manually, but at least it removes all bottlenecks. Also, not how the shared char, BinExpr& overload is elegantly "just another overload".