为递归变体编写 boost::variant 访问者

Question

我有一个应用程序包含多个 boost::variants，它们共享许多字段。我希望能够将这些访问者组合成“更大”变体的访问者，而无需复制和粘贴一堆代码。对于非递归变体这样做似乎很简单，但是一旦你有了递归变体，访问者中的自引用（当然）会指向错误的 class。为了使这个具体（并抄袭 boost::variant 文档）：

#include "boost/variant.hpp"
#include <iostream>

struct add;
struct sub;
template <typename OpTag> struct binop;

typedef boost::variant<
  int
  , boost::recursive_wrapper< binop<add> >
  , boost::recursive_wrapper< binop<sub> >
  > expression;

template <typename OpTag>
struct binop
{
  expression left;
  expression right;

  binop( const expression & lhs, const expression & rhs )
    : left(lhs), right(rhs)
  {
  }

};

// Add multiplication
struct mult;
typedef boost::variant<
  int
  , boost::recursive_wrapper< binop<add> >
  , boost::recursive_wrapper< binop<sub> >
  , boost::recursive_wrapper< binop<mult> >
  > mult_expression;

class calculator : public boost::static_visitor<int>
{
public:

  int operator()(int value) const
  {
    return value;
  }

  int operator()(const binop<add> & binary) const
  {
    return boost::apply_visitor( *this, binary.left )
      + boost::apply_visitor( *this, binary.right );
  }

  int operator()(const binop<sub> & binary) const
  {
    return boost::apply_visitor( *this, binary.left )
      - boost::apply_visitor( *this, binary.right );
  }

};

class mult_calculator : public boost::static_visitor<int>
{
public:

  int operator()(int value) const
  {
    return value;
  }

  int operator()(const binop<add> & binary) const
  {
    return boost::apply_visitor( *this, binary.left )
      + boost::apply_visitor( *this, binary.right );
  }

  int operator()(const binop<sub> & binary) const
  {
    return boost::apply_visitor( *this, binary.left )
      - boost::apply_visitor( *this, binary.right );
  }

  int operator()(const binop<mult> & binary) const
  {
    return boost::apply_visitor( *this, binary.left )
      * boost::apply_visitor( *this, binary.right );
  }

};

// I'd like something like this to compile
// class better_mult_calculator : public calculator
// {
// public:

//   int operator()(const binop<mult> & binary) const
//   {
//     return boost::apply_visitor( *this, binary.left )
//       * boost::apply_visitor( *this, binary.right );
//   }

// };


int main(int argc, char **argv)
{
  // result = ((7-3)+8) = 12
  expression result(binop<add>(binop<sub>(7,3), 8));

  assert( boost::apply_visitor(calculator(),result) == 12 );

  std::cout << "Success add" << std::endl;

  // result2 = ((7-3)+8)*2 = 12
  mult_expression result2(binop<mult>(binop<add>(binop<sub>(7,3), 8),2));
  assert( boost::apply_visitor(mult_calculator(),result2) == 24 );

  std::cout << "Success mult" << std::endl;
}

我真的很想像注释掉 better_mult_expression 的东西来编译（和工作），但它没有——因为基本计算器访问者中的 this 指针不引用 mult_expression, 但表达式.

有没有人有克服这个问题的建议，或者我是不是找错了树？

Answer 1

首先，我建议变体包括所有可能的节点类型，而不区分 mult 和 expression。这种区别在 AST 级别没有意义，仅在解析器阶段（如果您以 recursive/PEG 方式实现运算符优先级）。

除此之外，还有一些观察结果：

如果将 apply_visitor 调度封装到求值函子中，可以大大减少代码重复

你真正的问题似乎不是关于组合变体，而是组合访问者，更具体地说，是通过继承。

您可以使用 using 将继承的重载拉入范围以进行重载解析，因此这可能是最直接的答案：

Live On Coliru

 struct better_mult_calculator : calculator {
     using calculator::operator();

     auto operator()(const binop<mult>& binary) const
     {
         return boost::apply_visitor(*this, binary.left) *
             boost::apply_visitor(*this, binary.right);
     }
 };

正在改进！

从 that listing 开始，让我们去除一些噪音！

去除不必要的AST区分(-40 lines, down to 55 lines of code)

概括操作； <functional> header 标配这些：

namespace AST {
    template <typename> struct binop;
    using add  = binop<std::plus<>>;
    using sub  = binop<std::minus<>>;
    using mult = binop<std::multiplies<>>;
    using expr = boost::variant<int,
        recursive_wrapper<add>,
        recursive_wrapper<sub>,
        recursive_wrapper<mult>>;

    template <typename> struct binop { expr left, right; };
} // namespace AST

现在整个calculator可以是：

struct calculator : boost::static_visitor<int> {
    int operator()(int value) const { return value; }

    template <typename Op> 
    int operator()(AST::binop<Op> const& binary) const {
        return Op{}(boost::apply_visitor(*this, binary.left),
                    boost::apply_visitor(*this, binary.right));
    }
};

在这里，您的变体可以添加任意操作，甚至不需要触摸计算器。

Live Demo, 43行代码

就像我提到的开始，封装访问！

struct Calculator {
    template <typename... T> int operator()(boost::variant<T...> const& v) const {
        return boost::apply_visitor(*this, v);
    }

    template <typename T> 
    int operator()(T const& lit) const { return lit; }

    template <typename Op> 
    int operator()(AST::binop<Op> const& bin) const {
        return Op{}(operator()(bin.left), operator()(bin.right));
    }
};

现在您可以像预期的那样调用您的计算器了：

Calculator calc;
auto result1 = calc(e1);

当您使用运算符或什至其他文字类型（例如 double）扩展变体时，它将起作用。它甚至可以工作，无论您是否向它传递一个包含节点类型子集的不兼容变体类型。

为了完成 maintainability/readability，我建议将 operator() 设为仅调度函数：

完整演示

Live On Coliru

#include <boost/variant.hpp>
#include <iostream>

namespace AST {
    using boost::recursive_wrapper;

    template <typename> struct binop;
    using add  = binop<std::plus<>>;
    using sub  = binop<std::minus<>>;
    using mult = binop<std::multiplies<>>;
    using expr = boost::variant<int,
        recursive_wrapper<add>,
        recursive_wrapper<sub>,
        recursive_wrapper<mult>>;

    template <typename> struct binop { expr left, right; };
} // namespace AST

struct Calculator {
    auto operator()(auto const& v) const { return call(v); }

  private:
    template <typename... T> int call(boost::variant<T...> const& v) const {
        return boost::apply_visitor(*this, v);
    }

    template <typename T> 
    int call(T const& lit) const { return lit; }

    template <typename Op> 
    int call(AST::binop<Op> const& bin) const {
        return Op{}(call(bin.left), call(bin.right));
    }
};

int main()
{
    using namespace AST;
    std::cout << std::boolalpha;
    auto sub_expr = add{sub{7, 3}, 8};
    expr e1       = sub_expr;
    expr e2       = mult{sub_expr, 2};

    Calculator calc;

    auto result1 = calc(e1);
    std::cout << "result1:  " << result1 << " Success? " << (12 == result1) << "\n";

    // result2 = ((7-3)+8)*2 = 12
    auto result2 = calc(e2);
    std::cout << "result2:  " << result2 << " Success? " << (24 == result2) << "\n";
}

仍然打印

result1:  12 Success? true
result2:  24 Success? true

为递归变体编写 boost::variant 访问者

Composing boost::variant visitors for recursive variants

boost

boost-variant

正在改进！

完整演示