AST Cursors

An AST cursor is an object that is used to traverse an AST one node at a time. Cursors are instances of the AstCursor class. Using cursors, one can search an AST for a selected node and replace, delete, update, or detach it.

Traversing ASTs

Traversing Lists

Deleting Trees

Updating Trees

Skipping Trees

Cursor Methods

Traversing ASTs

A standard loop idiom is used to traverse an AST whose root node is r:

AstCursor c = new AstCursor();

for (c.First(r); c.More(); c.PlusPlus()) {
    // c.node references a node of the tree to search
}

The following Jak program creates an AST for the expression "7*x" and uses a cursor to traverse the tree. At each node, the number of children and the class name of the node is printed.

import j2j.*;	// translate this program with jak2java

class t2 {
    public static void main( String[] args ) {
        AST_Exp e;
        AstCursor c = new AstCursor();

        e = exp{ 7*x }exp;

        System.out.println("# children  Classname");
        System.out.println("-----------------------");
        for (c.First(e); c.More(); c.PlusPlus()) {
            System.out.println( c.node.arg.length + "\t\t" +
                                c.node.className());
      }
   }
}

The output of this program is:

# children  Classname
-----------------------
2               MultExpr
1               IntLit
1               MoreMultExpr
2               MEBod
1               Mult
1               PPQualName
1               AST_QualifiedName
1               NameId

Traversing Lists

A special case of traversing an AST is to traverse the nodes of a list. Given a node e (which is of type AstList), the following idiom is used to examine each element of a list:

AstCursor c = new AstCursor();
for (c.FirstElement(e); c.MoreElement(); c.NextElement() ) {
    AstNode node = c.node ;
}

Deleting Trees

As one traverses an AST, it is possible to replace, update, and delete nodes or subtrees. Consider the following program which is based on the Java.b grammar file. This program generates an AST that contains a list of class and interface declarations. A cursor is used to walk the tree; when an interface node is found, it (or really the subtree rooted at that node) is deleted:

import jak2java.*;	// translate this program with jak2java

class t3 {
    public static void main( String[] args ) {
        AST_Class k;
        AstProperties  p;
        AstCursor c = new AstCursor();

        // Step 1: create an AST that is a list of 
        //         interface and class definitions

        k = cls{ 
                interface foo {}
                class bar { int xx; }
                interface biff {}
                class baz { int xx; }
        }cls;

        // Step 2: delete each interface declaration - look at
        //         AHEAD/languages/Jak.b to see that interface decls
        //         are instances of UnmodifiedInterfaceDeclarations;
        //         we want to delete the parent of this node

        for (c.First(k); c.More(); c.PlusPlus()) {
            if (c.node instanceof ModTypeDecl && 
                c.node.arg[1] instanceof UnmodifiedInterfaceDeclaration)
                c.Delete();
        }
        // Step 3: now print the resulting AST

        System.out.println(k);
    }
}

The output of this program is:

class bar { int xx; }
class baz { int xx; }

Note: deleting a node is possible only if the node is an element of a list. In this example, interfaces are not elements of a list; rather, instances of ModTypeDecl are instances, and their arg[1] node is an UnmodifiedInterfaceDeclaration object. (See the Java.b grammar file). Note also as this examples shows that it is possible to delete a node during a search; the next node that will be examined is the node that immediately follows the node that had been deleted. In the case of a replacement, the next node to examine is the root of the newly replaced tree.

Updating Trees

It is possible (although not recommended) that when translating domain-specific extensions to a language, one walks an AST searching for tree nodes that are instances of the new language constructs. (The normal way is to do so recursively, without the use of cursors. However, we'll show in this section how it could be done with cursors). When such a node is found, a pure (Java) AST is constructed that defines the host-language implementation of that construct. The following program shows how cursors can be used to locate a particular node, how a replacement tree is created, and the constructed tree replaces the identified node. In general, if a tree is to be used in multiple replacements then the tree must be cloned. There is no concept of shared subtrees in AHEAD; trees must be cloned (copied) before they can be linked into an AST. See the description of normalize method.

import jak2java.*;  // translate this program with jak2java

class t4 {
    public static void main( String[] args ) {
        AST_Stmt s;
        AST_Exp e, copy;
        AstProperties  p;
        AstCursor c = new AstCursor();

        // Step 1: create an AST that is an if statement and 
        //         an expression replacement

        s = stm{ 
                if (boo()) { x = 5; }
                else { x = 7; }
        }stm;
        e = exp{ y < 87 }exp;

        // Step 2: walk tree s and replace boo() (the lone instance
        //         of node type PrimExpr with its first argument
        //         as an PPQualName) with a clone
        //         of e.  (Cloning may not be strictly necessary
        //         for this example, but is dangerous not to do so in
        //         the general case).

        for (c.First(s); c.More(); c.PlusPlus()) {
            if (c.node instanceof PrimExpr && 
                c.node.arg[0] instanceof PPQualName) {
                copy = (AST_Exp) e.clone();
                c.Replace(copy);
            }
        }

        // Step 3: now print the resulting AST

        System.out.print(s);
    }
}

The output of this program is:

if ( y < 87) { x = 5; }
else { x = 7; }

Skipping Trees

Consider the following problem: we want to identify the names of all top-level classes in an AST that represents a program. There is no need to search trees that are interior to class and interface declarations; all we want to do is to search that part of the AST that is the list of (top-level) class and interface declarations. Subtrees can be skipped using the Sibling() method. An invocation of Sibling() tells the tree traversal methods that the subtrees of a given node are to be skipped and the next node to examine is the sibling of the current node. The following program illustrates this idea:

import jak2java.*;  // translate this program with jak2java

class t5 {
    public static void main( String[] args ) {
        AST_Class k;
        AstProperties  p;
        AstCursor c = new AstCursor();

        // Step 1: create an AST that is a list 
        //         of interface and class definitions

        k = cls{ 
                interface foo { interface innerfoo{} }
                class bar { class innerbar { } }
                interface biff { interface innerbiff {} }
                class baz { class innerbaz{ } }
        }cls;

        // Step 2: use Sibling to skip subtrees internal 
        //         to interface and class declarations.

        for (c.First(k); c.More(); c.PlusPlus()) {
            if (c.node instanceof UmodClassDecl) {
                System.out.println("high-level class:     " + 
                c.node.arg[0].tok[0].tokenName());
                c.Sibling(); 
            }
            if (c.node instanceof UmInterDecl) {
                System.out.println("high-level interface: " +
                c.node.arg[0].tok[0].tokenName());
                c.Sibling();
            }
        }

        // Step 3: now print the resulting AST

        System.out.print(k);
    }
}

The output of this program is:

high-level interface: foo
high-level class:     bar
high-level interface: biff
high-level class:     baz

          interface foo { interface innerfoo{} }
          class bar { class innerbar { } }
          interface biff { interface innerbiff {} }
          class baz { class innerbaz{ } }

Cursor Methods

The following are methods that can be applied to AST cursors:

Cursor Method or Member	Meaning	Notes
void First( AstNode root )	position cursor on root of tree	1
boolean More( )	true if more nodes to examine in tree
void PlusPlus( )	advance cursor to next node of tree	1
void Sibling( )	skip the search of subtrees of the current node	2
void Up( )	reposition to the node "above" the current node	3
void Delete( )	delete subtree rooted at the current node	4
void Replace( AstNode tree )	replace the current node with tree	5
void AddAfter( AstList list )	add list after the current node	6
void AddBefore( AstList list )	add list before the current node	6
void print( AstProperties p )	unparse the tree rooted at the current node using AstProperties p	7

Notes:

ASTs are searched in preorder (self then children from left to right) order. One cannot advance past the root of the tree to search, where the root was set in the First( root ) call.
See Section 4.
Up( ) fails if the current node is already positioned on the root. Note also that there are "hidden" nodes in an AST that are present only for implementation reasons. Up( ) repositions a cursor on the first ancestor node that is not one of these "hidden" nodes. Thus, the Up( ) node of a current node need not be the immediate parent of the current node.
Only AST nodes that are elements of lists can be deleted.
Substitution is possible only if the replacement tree is of the same type as the current node. This ensures that all trees will be syntactically correct upon editing.
The current node must be a list node.
See section on printing ASTs.

AHEAD Home Page