Skip to content

Visitor Guide

Jump to bottom Edit New page
Luis Diogo Couto edited this page Feb 6, 2015 · 3 revisions

Note: This guide assumes basic knowledge of the structure of the Overture AST. Head over to the AST Guide for an intro to the topic.

TOC

  1. Introduction

Introduction

Visitors are one of the most important concepts in Overture development. This guide will teach you the basic ideas of the visitor implementation in Overture and how to use it to implement functionalities. For more general information about the visitor pattern, Wikipedia is a nice place to start.

Code stubs and validation tests for the exercises in this guide are available in the dev tutorials repository. To use them, clone the repository then build and import the visitor project. You will get test failures in the beginning but they will go away once you solve the exercises.

Visitor basics

The basic idea behind the visitor pattern is to detach an algorithm from the data it runs on. To put it another way, we replace method invocation with visitor application. For example: node.typecheck() becomes node.apply(typecheckVisitor).

This pattern of application holds pretty much every time you need to interact with the AST.

A visitor is developed in a separate class from the AST and this class must be marked as a visitor in order for the AST classes to accept it. The easiest way to do this is to subclass the AnalysisAdaptor class in the org.overture.ast.analysis package of the AST module.*

* : There are various mechanisms for declaring visitors and we will discuss them later. For now, the basic one suffices.

Cases

Once we have subclassed the AnalysisAdaptor, we can apply the visitor right away but nothing will happen. We need to add some behavior to the visitor and we do this by implementing cases. Cases are implemented by overriding the existing methods in the AnalysisAdaptor. Take a look at it now and see how many cases we have!

A visitor has a specific case method for each kind of node in the AST. When the visitor is applied to an AST node, the corresponding case method is executed. For example, the caseASetEnumSetExp method is executed when the visitor is applied to a ASetEnumSetExp node. The case method has a ASetEnumSetExp argument and that corresponds to the node that it was applied to. The node can then be analyzed in whatever way is necessary. For example, the code below checks if a sequence enumeration is empty.

public class EmptySeqVisitor extends AnalysisAdaptor {

  boolean isEmpty;
  
  @Override
  public void caseASeqEnumSeqExp(ASeqEnumSeqExp node)
      throws AnalysisException {
  
    isEmpty = node.getMembers().isEmpty();
    
  }
  
}

Exercise 1: Write a visitor that counts the number of elements in a set enumeration. Store the result in an instance variable and make it accessible via getter method. If you are using the exercise project, add the cases to Exercise01Visitor in the exercises123 package. Check your work with the tests in Exercise01Test in the exercises123 package.

Click here for solutions.

More on cases

In addition to the specific cases for each kind of node, there are lots of situations where you want to process several related nodes in the same way. For example, all binary expression nodes.

The visitor framework provides you with a mechanism for doing this: the default cases. Just as the AST is divided in various families of nodes, the default cases can be applied to any member of a node family. There are 3 types of default cases:

  • defaultINode: this applies to any node in the AST;
  • defaultP*: these apply to a family of nodes. Ex: defaultPExp applies to any PExp node;
  • defaultS*: these apply to a sub-family of nodes. Ex: defaultSFunctionDefinition applies to any SFunctionDefinition node.

There is a default case method for every root node in the AST so it is possible to figure out which one you need to use by looking for the common ancestor.

Note that the default cases only have the root superclass as argument so attributes that are only present in the subclasses are not visible. For example, the defaultSSetExp cannot see the members in ASetCompSetExp node. If you need access to attributes in the specific node class, use the specific case method. Don't do instanceof checks and casts on nodes inside default case methods!

Finally, it is very important to note that if a visitor has multiple cases that can be applied to a node, the most specific one is applied. So, for APlusNumericBinaryExp it would go:

caseAPlusNumericBinaryExp > defaultSNumericBinaryExp > defaultSBinaryExp > defaultPExp > defaultINode

There is a direct correspondence between case priority and node class hierarchy. For reference, here is the class hierarchy for APlusNumericBinaryExp:

APlusNumericBinaryExp > SNumericBinaryExp > SBinaryExp > PExp > INode

If you're getting some unexpected behaviour, check to make sure there isn't a narrower case method being applied.

Exercise 2: Write a visitor that computes the name of any definition. This can be done with 1 case. Store and provide access to the result in the same way as you did for exercise 1. If you are using the exercise project, add the cases to Exercise02Visitor in the exercises123 package. Check your work with the tests in Exercise02Test in the exercises123 package.

Click here for solutions.

Cross-case dispatching

So far, the visitor uses we have discussed were single case. In other words, apply once and you're done. Most of the time, you will not be so lucky and after visiting the initial node, you will have to visit additional sub-nodes. While you can do this by direct invocation of the case method, it's better to just reapply the visitor, like this:

caseAPlusNumericBinaryExp(APlusNumericBinaryExp node) throws AnalysisException {
// do stuff...
node.getLeft().apply(this);
}

Exercise 3: Write a visitor that, for any arithmetic expression, calculates how many terms the expression has. Handle the result as before. If you are using the exercise project, add the cases to Exercise03Visitor in the exercises123 package. Check your work with the tests in Exercise03Test in the exercises123 package.

Click here for solutions.

Additional types of visitors

All the visitors we have used until now have stored their results in an instance variable that must be attained via getter method. Likewise, we need instance variables to hold any auxiliary data the visitor requires. While this approach works for simple functionalities, it can get out of hand and we have a better solution this in the form of question and answer visitors. There are 3 versions that can be subclasses in the org.overture.ast.analysis package:

  • QuestionAdaptor<Q> is the parameterizable question visitor. Q can be of any class you wish, though it must be the same for all cases in a given visitor. In this visitor, the question Q is passed as a second argument to each case method. This allows you to pass additional information to the case.
  • AnswerAdaptor<A> is the parameterizable answer visitor. A can be of any class you wish, though it must be the same for all cases in a given visitor. In this visitor, each case must return an object of class A. Also, this visitor has two additional methods that must be implemented: createNewReturnValue(INode node) and createNewReturnValue(Object node). These methods are invoked when no other case can be matched because something must be returned.
  • QuestionAnswerAdaptor this visitor combines the functionalities of the two previous ones. Q and A can any two classes you wish. This visitor also needs the two createNewReturnValue methods. The Overture type checker is implemented as a QuestionAnswerAdaptor where the question is the environment for the definition being type checked and the answer is the of the definition.

Exercise 4: Rewrite all previous exercises to use question and answers visitors. If you've implemented all exercises in a single class, you will need to separate them now. If you are using the exercise project, add the cases to Exercise4{1,2,3}Visitor in the exercise4 package. Check your work with the tests in Exercise4{1,2,3}Test in the exercise4 package.

Click here for solutions.

Final Notes

There is another way to declare visitors, in addition to subclassing the adaptors. You can also implement the various interfaces in org.overture.ast.analysis.intf. These provide the same set of case methods but because they are interfaces you must implement all of them. Generally, you're better off subclassing the adaptors but the interfaces are necessary for some advanced cases.

You may have seen a DepthFirstAdaptor in the analysis package. This is a special visitor that, in addition to any behaviour you implement, performs an automatic depth-first traversal of the entire tree it is applied to. There is no need to do case dispatching with this visitor. We'll learn how and when to use it in an upcoming tutorial.

Add a custom footer

Developer Documentation

Set Up

  1. Prerequisites

Main

  1. AST Guide
Clone this wiki locally