Re: [Boost-users] How to implement a visitor pattern over an AST

Subject: Re: [Boost-users] How to implement a visitor pattern over an AST
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2018-12-10 20:00:14

AMDG

On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:
> 
> I have an AST successfully building, generating text file, and
> subsequently Spirit Qi parsing for verification purposes.
> 
> Now I want to implement a visitor pattern over that AST, somehow...
> For "calculators" and such, "evaluating" those expressions is one
> thing; however, this AST is not that. It is closer akin to a parsed
> Xml or Json model/tree.
> 
> In other words, I'd like for it to feel sort of like an iterator if
> that's even possible. It should have contextual awareness where it is
> at all times, etc, perhaps "incrementing" is a depth first analysis.
> 

It's possible to do this, but making an iterator
over a tree is quite a bit more complex than just
using a depth-first visitation whenever you need
to process the tree.

> In particular I have in mind to iterate the expected and actual AST
> results in order to perform the verification.

For this case, the simplest method is a binary
visitor.

For example, variant equality looks something like this:

struct equal_to_visitor
{
  using result_type = void;
  template<class T>
  bool operator()(const T& lhs, const T& rhs)
  {
    return lhs == rhs;
  }
  template<class T, class U>
  bool operator()(const T&, const U&)
  {
    return false;
  }
};
...
bool operator==(const variant<...>& lhs, const variant<...> rhs)
{
  return boost::apply_visitor(equal_to_visitor{}, lhs, rhs);
}

Note that since we always return false if the types
are different, a slight variation can make this
work with a unary visitor.

> In other words, I might
> do something like this:
> 
> auto expected_it = ast_visitor{&expected};
> auto actual_it = ast_visitor{&actual};
> 
> REQUIRE(expected_it);
> REQUIRE(actual_it);
> 
> REQUIRE(*expected_it == *actual_it);
> 
> // Rinse and repeat
> ++expected_it;
> ++actual_it;
> REQUIRE(*expected_it == *actual_it);
> 
> I wonder if something like this is even possible from the Boost
> libraries? Or interested to hear any insights on the subject.
> 
> For that matter, I wonder it is more appropriate to simply implement
> the logical operators.
> 

In Christ,
Steven Watanabe