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: Michael Powell (mwpowellhtx_at_[hidden])
Date: 2018-12-10 20:14:01

On Mon, Dec 10, 2018 at 3:00 PM Steven Watanabe via Boost-users
<boost-users_at_[hidden]> wrote:
>
> 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.

It is; I actually have a similar pattern in a "string rendering
visitor" in which I have internally specialized template methods for
the particular nodes of visitation. One might call that a unary
visitor, given a single operand.

In this case, I rinse and repeat given the binary case, two operands:

template<typename T>
bool equals(const T& x, const T& y) const {
    const auto message = "Comparator type '" +
std::string(typeid(T).name()) + "' unsupported";
    throw std::exception(message.c_str());
}

template<>
bool equals<ast::TopLevelType>(const ast::TopLevelType& x, const
ast::TopLevelType& y) const {
    // ...
}

And so on... Which also guarantees that I am also walking both tree's
at the same moment and in like fashion.

> > 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users