Traverse the Tree

The Visitor Pattern is a design pattern that allows operations to be performed on a set of objects without changing the classes of the objects. It enables adding new operations to existing object structures without modifying the structures themselves. This pattern typically involves two hierarchies: one for the objects being visited (elements) and one for the visitors, which define the operations to be performed on the elements.

The tree is immutable. If you want to change parts of the tree you can use a rewriting visitor explained below.

The Visitor

The following C# code demonstrates an implementation of the Visitor Pattern using an abstract class NodeVisitor<TReturn> that returns a value of type TReturn. If you want to have control how you visitor is called you can override the Visit method. An example can be found in the sample project.

public class PrintVisitor : NodeVisitor<string>
{
    public PrintVisitor()
    {
        For<GroupNode>(Visit);
    }

    private string Visit(GroupNode group)
    {
        return $"({Visit(group.Expr)})";
    }
}

Every node you want to visit has to be registered in the visitor. The registration of visitor methods can be automated by adding the Silverfly.Generator package and add the Visitor-Attribute to the Visitor-Class

There is also a non returning variant of the nodevisitor class.

To print the tree you can use the PrintVisitor which builds a string.

A TaggedNodeVisitor can be used to give the visit method additional context information. A good example is the Evaluationvisitor

Rewriting the tree

To make it more comfortable to rewrite certain parts of the tree you can implement a visitor that implements the Rewriter class. The rewriter has implemented methods for all standard node types which you can override.