The Boa Programming Guide - Visitors

Boa provides a custom syntax for easily performing mining tasks on source code. This syntax is inspired by the object-oriented visitor pattern. Users may declare a visitor:

id := visitor { visitClause* };

Visitors are typically assigned to a variable and provide one or more visit clauses. A visit is started using a call to the visit function. This function takes two arguments: the starting node n and a visitor v:

visit(n, v);

This call then starts a visit at the node n using the specified visitor v. By default, a depth-first search (DFS) traversal strategy is used. The visitor defines visit clauses, which execute either before or after visiting a node's children.

Visit Clauses

There are two different kinds of visit clauses: before and after clauses:

before id: T -> body; after id: T -> body;

Visit clauses specify an identifier and a node type. When the visitor visits any node matching the specified node type, the clause's body executes (with the node bound to the specified identifier). A before visit clause runs before the node's children are visited and an after visit clause runs after all of the node's children were visited.

Visit clauses may also specify a list of node types:

before T1, T2, .. -> body; after T1, T2, .. -> body;

When specifying a list of node types, no identifier is given and the node is not accessible from the clause's body.

Each node type may appear in at most 1 before clause and at most 1 after clause.

Wildcards

Visitors may also contain a visit clause with a wildcard:

before _ -> body; after _ -> body;

A wildcard visit clause will match any node type that does not already have a visit clause. This allows providing a default behavior for the visitor, with custom node-specific behavior overriding the default. Note that unlike pattern matching in functional languages, the order of the clauses does not matter as each node type will have exactly 0 or 1 matching visit clause.

Custom Traversal Strategies

By default visitors use a depth-first traversal strategy. If your analysis requires a different strategy you may specify it. Before visit clauses allow a special statement, called a stop statement:

stop;

This statement tells the visitor to stop the depth-first traversal and return to the parent node. This is useful when you know you don't need to visit the sub-tree rooted at the current node or if you need to visit the sub-tree with a custom traversal strategy. Note that if a stop statement executes, the after clause (if any) for that node will not execute.

You may also specify to visit a specific child node, by using the single-argument form of the visit function:

visit(child);

This states to visit the child node, using the current visitor. A combination of stop statements and visit calls can be used to implement a custom traversal strategy.

Inherited Attributes @since 2019-10

Visitors provide for a limited form of passing down attributes in the tree, also known as inherited attributes. This allows nodes further down in the AST to access the attributes of ancestors above them. It allows accessing only the nearest ancestor of a given type, and then provides all attributes for that node. This is accomplished using the current() function. This function expects an AST node type as an argument. The compiler will properly manage the stack for you and ensure you always get the nearest ancestor that matches that node type.

For example, this code:

visit(input, visitor {
before e: Expression -> {
name := current(Method).name;
.. # use name here
}
});

This code essentially becomes something similar to the following:

s: stack of string;

visit(input, visitor {
before m: Method -> push(s, m.name);
after m: Method -> pop(s);

before e: Expression -> {
name := peek(s);
.. # use name here
}
});