Tree Construction and Manipulation

/**
 * Basic tree node interface
 */
public interface Tree {
    /** Get a child at index i. */
    public Tree getChild(int i);
    
    /** How many children are there? If there is none, return 0. */
    public int getChildCount();
    
    /** Get the parent for this node; if null, implies node is root */
    public Tree getParent();
    
    /** Set the parent and child index; implies node does not yet have parent */
    public void setParent(Tree t);
    
    /** Is there an ancestor with this token type? */
    public boolean hasAncestor(int ttype);
    
    /** Walk up and get list of this node's ancestors.  First node of
     *  list is the root and the last is the parent of this node.
     */
    public List<Tree> getAncestors();
    
    /** This node is what child index? 0..n-1 */
    public int getChildIndex();
    
    /** Set the child index. */
    public void setChildIndex(int index);
    
    /** Walk tree and visit each node, setting parent and child index. */
    public void freshenParentAndChildIndexes();
    
    /** Add t as child of this node.  Warning: if t has no children, but
     *  child does and child isNil then this routine moves children to t via
     *  t.replaceChildren(child.children).
     */
    public void addChild(Tree t);
    
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
    public void setChild(int i, Tree t);
    
    /** Delete the child at index i (0..n-1) and return it; null if no such child */
    public Object deleteChild(int i);
    
    /** Delete children from start to stop and replace with t even if t is
     *  a list (nil-root tree). Num of children can increase or decrease.
     *  For huge child lists, inserting children can force walking rest of
     *  children to set their childindex; could be slow.
     */
    public void replaceChildren(int startChildIndex, int stopChildIndex, Object t);
    
    /** Indicates the node is a nil node but may still have children, meaning
     *  the tree is a flat list.
     */
    public boolean isNil();
    
    /** What is the smallest token index (indexing from 0) for this node
     *  and its children?
     */
    public int getTokenStartIndex();
    
    /** What is the largest token index (indexing from 0) for this node
     *  and its children?
     */
    public int getTokenStopIndex();
    
    public Tree dupNode();
    
    /** Return a token type; needed for tree parsing */
    public int getType();
    
    public String getText();
    
    /** In case we don't have a token payload, what is the line for errors? */
    public int getLine();
    
    public int getCharPositionInLine();
    
    public String toString();
    
    /** Print out a whole tree in LISP form. {@link #getType} is used on the
     *  node payloads to get the text for the nodes.  Detect
     *  parse trees and extract data appropriately.
     */
    public String toStringTree();
}

/**
 * Base implementation of Tree interface
 */
public abstract class BaseTree implements Tree {
    /** Child nodes if any */
    protected List<Tree> children;
    
    public BaseTree();
    public BaseTree(Tree node);
    
    /** Get a child at index i; null if index out of range */
    public Tree getChild(int i);
    
    /** How many children are there? If there is none, return 0. */
    public int getChildCount();
    
    /** Add t as child of this node.  Warning: if t has no children, but
     *  child does and child isNil then this routine moves children to t via
     *  t.replaceChildren(child.children).
     */
    public void addChild(Tree t);
    
    /** Add all elements of kids list as children of this node */
    public void addChildren(List<Tree> kids);
    
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
    public void setChild(int i, Tree t);
    
    /** Delete the child at index i (0..n-1) and return it; null if no such child */
    public Object deleteChild(int i);
    
    /** Delete children from start to stop and replace with t even if t is
     *  a list (nil-root tree). Num of children can increase or decrease.
     *  For huge child lists, inserting children can force walking rest of
     *  children to set their childindex; could be slow.
     */
    public void replaceChildren(int startChildIndex, int stopChildIndex, Object t);
    
    /** Override in a subclass to change the impl of children list */
    protected List<Tree> createChildrenList();
    
    /** Indicates the node is a nil node but may still have children, meaning
     *  the tree is a flat list.
     */
    public boolean isNil();
    
    /** Walk tree and visit each node, setting parent and child index. */
    public void freshenParentAndChildIndexes();
    
    public void freshenParentAndChildIndexesDeeply();
    
    protected void freshenParentAndChildIndexes(int offset);
    
    public void sanityCheckParentAndChildIndexes();
    public void sanityCheckParentAndChildIndexes(Tree parent, int i);
    
    /** What is the smallest token index (indexing from 0) for this node
     *  and its children?
     */
    public int getTokenStartIndex();
    
    /** What is the largest token index (indexing from 0) for this node
     *  and its children?
     */
    public int getTokenStopIndex();
    
    public abstract Tree dupNode();
    public abstract int getType();
    public abstract String getText();
    
    /** In case we don't have a token payload, what is the line for errors? */
    public int getLine();
    public int getCharPositionInLine();
    
    public String toString();
    
    /** Print out a whole tree in LISP form. {@link #getType} is used on the
     *  node payloads to get the text for the nodes.  Detect
     *  parse trees and extract data appropriately.
     */
    public String toStringTree();
    
    public List<Tree> getAncestors();
    
    /** Walk up and get first ancestor with this token type. */
    public Tree getAncestor(int ttype);
    
    /** Return a list of all ancestors of this node.  The first node of
     *  list is the root and the last is the parent of this node.
     */
    public List<Tree> getAncestors();
    
    /** Is there an ancestor with this token type? */
    public boolean hasAncestor(int ttype);
    
    /** Walk up and get first ancestor with this token type. */
    public Tree getAncestor(int ttype);
    
    /** Return a list of all ancestors of this node.  The first node of
     *  list is the root and the last is the parent of this node.
     */
    public List<Tree> getAncestors();
    
    public Tree getParent();
    public void setParent(Tree t);
    public int getChildIndex();
    public void setChildIndex(int index);
}

/**
 * Default tree node implementation
 */
public class CommonTree extends BaseTree {
    /** A single token is the payload */
    public Token token;
    
    /** What token indexes bracket all tokens associated with this node
     *  and below?
     */
    protected int startIndex = -1, stopIndex = -1;
    
    /** Who is the parent node of this node; if null, implies node is root */
    public CommonTree parent;
    
    /** What index is this node in the child list? Range: 0..n-1 */
    public int childIndex = -1;
    
    public CommonTree();
    public CommonTree(CommonTree node);
    public CommonTree(Token t);
    
    public Token getToken();
    
    public Tree dupNode();
    
    /** Return a token type; needed for tree parsing */
    public int getType();
    
    public String getText();
    
    /** In case we don't have a token payload, what is the line for errors? */
    public int getLine();
    
    public int getCharPositionInLine();
    
    public int getTokenStartIndex();
    public void setTokenStartIndex(int index);
    
    public int getTokenStopIndex();
    public void setTokenStopIndex(int index);
    
    /** For every node in this subtree, make sure children[i] points to
     *  a child i.  Walk depth first, visit bottom up.  That way, all the
     *  children of a node are fixed first.
     */
    public void setChildIndex(int index);
    
    public Tree getParent();
    public void setParent(Tree t);
    
    public int getChildIndex();
    
    /** Indicates the node is a nil node but may still have children, meaning
     *  the tree is a flat list.
     */
    public boolean isNil();
    
    public String toString();
}

import org.antlr.runtime.tree.*;
import org.antlr.runtime.*;

// Create tree nodes
Token plusToken = new CommonToken(MyParser.PLUS, "+");
CommonTree plusNode = new CommonTree(plusToken);

Token xToken = new CommonToken(MyParser.IDENTIFIER, "x");
CommonTree xNode = new CommonTree(xToken);

Token yToken = new CommonToken(MyParser.IDENTIFIER, "y"); 
CommonTree yNode = new CommonTree(yToken);

// Build tree structure: + (x, y)
plusNode.addChild(xNode);
plusNode.addChild(yNode);

// Navigate tree
System.out.println("Root: " + plusNode.getText());
System.out.println("Child 0: " + plusNode.getChild(0).getText());
System.out.println("Child 1: " + plusNode.getChild(1).getText());

// Print tree in LISP format
System.out.println("Tree: " + plusNode.toStringTree());

// Check relationships
System.out.println("Parent of x: " + xNode.getParent().getText());
System.out.println("Child index of y: " + yNode.getChildIndex());

/**
 * Interface for tree manipulation operations
 */
public interface TreeAdaptor {
    /** Create a tree node from Token object; for CommonTree type trees,
     *  no need to specify a Token object.  The token payload should
     *  contain the appropriate type and text info.
     */
    public Object create(Token payload);
    
    /** Duplicate a tree, assuming this is a root node of a tree--
     *  duplicate everything underneath.  This is done via the adaptor
     *  rather than the tree itself to handle different types of trees.
     */
    public Object dupTree(Object tree);
    
    /** Duplicate a single tree node, but not its children; single node dup. */
    public Object dupNode(Object t);
    
    /** Return the type; allow for later extension via subclassing. */
    public int getType(Object t);
    
    /** In some applications, it would be useful to track parent pointers
     *  or the index of a child.  Tree and Tree adaptor interfaces are
     *  intended to be as minimal as possible.
     */
    public void setText(Object t, String text);
    
    public String getText(Object t);
    
    /** Get the token associated with this node; if you are not using
     *  CommonTree, then you must override this in your own adaptor.
     */
    public Token getToken(Object t);
    
    /** Where are token start/stop boundaries for subtree rooted at t?
     *  The token information is not set unless you are using
     *  TokenRewriteStream to construct and emit the original or
     *  modified token stream.  The adaptor is responsible for setting
     *  these values.  Many implementations will use the CommonTree
     *  that tracks start/stop token indexes.  If you are mixing up tree
     *  formats, then the easiest thing to do is make sure this method
     *  on your TreeAdaptor returns something that cooresponds to Token.getTokenIndex().
     *  Return -1 if you don't use tokens/tokenstream.
     */
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
    
    public int getTokenStartIndex(Object t);
    public int getTokenStopIndex(Object t);
    
    /** Get a child 0..n-1 node */
    public Object getChild(Object t, int i);
    
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
    public void setChild(Object t, int i, Object child);
    
    /** Remove ith child and shift children down from right. */
    public Object deleteChild(Object t, int i);
    
    /** How many children?  If 0, then this is a leaf node */
    public int getChildCount(Object t);
    
    /** Return an ID for this node, which is unique within the life of
     *  this TreeAdaptor.  Usually it's the memory address of the node.
     *  If we're building trees from a stream, then ID should be the
     *  index in the stream.
     */
    public int getUniqueID(Object node);
    
    // REWRITE SUPPORT
    
    /** Tell me how to create a token for use with imaginary token nodes.
     *  For example, there is probably no input symbol associated with decl
     *  node types.  This method is executed when you type create(type).
     */
    public Object create(int tokenType, Token fromToken);
    public Object create(int tokenType, Token fromToken, String text);
    public Object create(int tokenType, String text);
    
    /** Make tree t the new root of oldRoot; oldRoot is a lost child of t. */
    public Object becomeRoot(Object newRoot, Object oldRoot);
    
    /** If oldRoot is a nil root, just copy or move the children to newRoot.
     *  If not a nil root, make oldRoot a child of newRoot.
     *
     *     old=^(nil a b c), new=r yields ^(r a b c)
     *     old=^(a b c), new=r yields ^(r ^(a b c))
     *
     *  If newRoot is a nil-rooted single child tree, use the single
     *  child as the new root node.
     *
     *     old=^(nil a b c), new=^(nil r) yields ^(r a b c)
     *     old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
     *
     *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
     *
     *     old=null, new=r yields r
     *     old=null, new=^(nil r) yields ^(nil r)
     *
     *  Return newRoot.  Throw an exception if newRoot is not a nil node
     *  and has children.  This would mean that the new root has both
     *  the oldRoot and its own children.  The definition of ^(...) is that
     *  it is make the ^(a b c) the root and make the ^(a b c) a child of ^(r ...)
     */
    public Object rulePostProcessing(Object root);
    
    /** Add a child to the tree t.  If child is a flat tree (a list), make all
     *  in list children of t.  Warning: if t has no children, but child does
     *  and child isNil then this routine moves children to t via
     *  t.replaceChildren(child.children).
     */
    public void addChild(Object t, Object child);
    
    /** If oldRoot is a nil root, just copy or move the children to newRoot.
     *  If not a nil root, make oldRoot a child of newRoot.
     *
     *   old=^(nil a b c), new=r yields ^(r a b c)
     *   old=^(a b c), new=r yields ^(r ^(a b c))
     *
     *  If newRoot is a nil-rooted single child tree, use the single
     *  child as the new root node.
     *
     *   old=^(nil a b c), new=^(nil r) yields ^(r a b c)
     *   old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
     *
     *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
     *
     *   old=null, new=r yields r
     *   old=null, new=^(nil r) yields ^(nil r)
     *
     *  Return newRoot.  Throw an exception if newRoot is not a nil node
     *  and has children.  This would mean that the new root has both
     *  the oldRoot and its own children.  The definition of ^(...) is that
     *  it is make the ^(a b c) the root and make the ^(a b c) a child of ^(r ...)
     */
    public Object becomeRoot(Token newRoot, Object oldRoot);
    
    /** Create a node for newRoot make it a root of oldRoot.
     *  If oldRoot is a nil root, just copy or move the children to newRoot.
     *  If not a nil root, make oldRoot a child of newRoot.
     *  Return node newRoot.
     */
    public Object create(int tokenType, Token fromToken);
    public Object create(int tokenType, Token fromToken, String text);
    public Object create(int tokenType, String text);
    
    /** For identifying trees.
     *
     *  How to identify nodes so we can say "add node to a prior node"?
     *  Even becomeRoot is an issue.  Use System.identityHashCode(node)
     *  usually.
     */
    public int getUniqueID(Object node);
    
    
    // TREE PARSING
    
    /** For tree parsing, I need to know the token type of a node */
    public int getType(Object t);
    
    /** Node constructors can set the type of a node */
    public void setType(Object t, int type);
    
    public String getText(Object t);
    
    /** Node constructors can set the text of a node */
    public void setText(Object t, String text);
    
    /** Return the token object from which this node was created.
     *  Currently used only for printing an error message.
     *  The error display routine in BaseRecognizer needs to
     *  display where the input the error occurred. If your
     *  tree of limitation does not store information that can
     *  lead you to the token, you can create a token filled with
     *  the appropriate information and pass that back.  See
     *  BaseRecognizer.getErrorMessage().
     */
    public Token getToken(Object t);
    
    /** Where are token start/stop boundaries for subtree rooted at t?
     *  For rules that create AST nodes, this method is called on
     *  the returned AST node from every rule invocation.  The result
     *  is the collapse of all child boundaries to that of the parent.
     */
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
    
    /** Return the first token associated with this node.  If this node
     *  is associated with Token objects, you can access this start
     *  token, and from there you can access the start token's input
     *  stream.  Return null if no such token.
     */
    public int getTokenStartIndex(Object t);
    public int getTokenStopIndex(Object t);
    
    /** Get a child 0..n-1 node */
    public Object getChild(Object t, int i);
    
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
    public void setChild(Object t, int i, Object child);
    
    /** Remove ith child and shift children down from right. */
    public Object deleteChild(Object t, int i);
    
    /** How many children?  If 0, then this is a leaf node */
    public int getChildCount(Object t);
    
    /** Is the tree node considered a nil node used to make lists
     *  of child nodes?
     */
    public boolean isNil(Object tree);
    
    /** Return something analogous to the usual debug string for
     *  a parse tree such as: (+ 1 2).
     */
    public String toString(Object t);
    
    /** Return a string for an entire tree not just a node */
    public String toString(Object t, String[] ruleNames);
    
    /** Return a string for a range of nodes encompassed in rule r at
     *  positions begin to end (not end+1!).  For example,
     *  toString(t, "expr", 2, 5) can print the tokens from
     *  expr rule invocations 2 through 5.
     */
    public String toString(Object t, int begin, int end);
    
    /** Track start/stop token for subtree root created for a rule.
     *  Only works with Tree nodes.  For rules that match nothing,
     *  seems like this will yield start=i and stop=i-1 in a nil node.
     *  Might be useful info so I'll not force to be i..i.
     */
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
    
    /** Get the token start index for this subtree; return -1 if no such index */
    public int getTokenStartIndex(Object t);
    
    /** Get the token stop index for this subtree; return -1 if no such index */
    public int getTokenStopIndex(Object t);
    
    /** Replace any child at index i (0..n-1) with t; t must be non-null and non-nil. */
    public void setChild(Object t, int i, Object child);
    
    /** Delete child at index i (0..n-1) and return it; null if not found. */
    public Object deleteChild(Object t, int i);
    
    /** Is the tree t considered a nil node used to make lists
     *  of child nodes?
     */
    public boolean isNil(Object tree);
    
    /** Return something analogous to the usual debug string for
     *  a parse tree such as: (+ 1 2).
     */
    public String toString(Object t);
    
    /** Create a new node derived from a token, with a new token type.
     *  This is invoked from an imaginary node ref on right side of a
     *  tree grammar rule, for example:
     *
     *     This reference to NEW in tree parser...
     *     ^(NEW type identifier)
     *
     *     must create a new node of token type NEW with text "NEW".
     *     If you are creating a string-based AST with UniversalTree for
     *     example, then a 'new' UniversalTree(NEW, "NEW") would be
     *     returned from this method.
     *
     *     This method should be overridden.  If you care about the
     *     Token object from which this node to be created is associated,
     *     override this method.  Otherwise, override the String version.
     *     NOTE: the Rule.ctor(Token, String) is called by the default
     *     implementation.
     *
     *     If you are building trees for a language like C that has
     *     no explicit list structure to represent a function call,
     *     but you would like to overlay some nodes to represent
     *     the various parts such as argument list, return value,
     *     function name, etc..., then you would return a node
     *     representing that construct.
     */
    public Object create(int tokenType, Token fromToken);
    
    /** Same as create(tokenType,fromToken) except set the text too.
     *  This is useful for converting GENERIC['"<"] to GENERIC["<";] for
     *  example, where the GENERIC node is associated with the original
     *  token from the input stream.
     */
    public Object create(int tokenType, Token fromToken, String text);
    
    /** Create a new node derived from a token, with a new token type
     *  and new text.  This is invoked from an imaginary node ref on right
     *  side of a tree grammar rule, for example:
     *
     *     This reference to NEW in tree parser...
     *     ^(NEW["foo"] type identifier)
     *
     *     must create a new node of token type NEW with text "foo".
     *     If you are creating a string-based AST with UniversalTree for
     *     example, then a 'new' UniversalTree(NEW, "foo") would be
     *     returned from this method.
     */
    public Object create(int tokenType, String text);
    
    /** Does the tree adpator support unique IDs? how to implement adapt()
     *  depends on this. buildTree() calls adaptor.getUniqueID(node).
     *  Override if you're using your own BaseTree-derived objects.
     */
    public boolean hasUniqueID(Object node);
    
    /** For tree parsing, return the token type of a node */
    public int getType(Object t);
    
    public void setType(Object t, int type);
    
    public String getText(Object t);
    
    public void setText(Object t, String text);
    
    /** For tree parsing, return the token object associated with node t.
     *  For BasicTree, this is just the token.  For CommonTree, this is
     *  the token.  For your AST nodes, this method must return the
     *  Token object from which this node was created.  This is used for
     *  printing out error messages that include line/column info.
     *
     *  Essentially, the error message is trying to figure out what Token
     *  object was associated with the erroneous AST node.  One could
     *  also use a hash table to map AST nodes to tokens but I think
     *  that's overkill.
     */
    public Token getToken(Object t);
    
    /** Set the token boundaries for subtree root t.  The boundaries are
     *  stored on the node as start/stop token indexes.  This is done
     *  automatically when parsing with output=AST but the boundaries
     *  must be set when invoking actions manually such as tree construction
     *  in actions, building adapters, etc...  When using ^(...) make syntax
     *  in actions, the form ^(root child1 ... childN) causes ANTLR to invoke
     *  the adaptor methods:
     *
     *    r = create(type);
     *    addChild(r, child1);
     *    ...
     *    addChild(r, childN);
     *    setTokenBoundaries(r, firstToken, lastToken);
     *
     *  If you are building ASTs manually in a translating tree parser,
     *  then you need to be careful to set the token boundaries explicitly.
     *  Look at the examples in the tree/ dir for how to do this.  This
     *  method is the final method called in the ^(root ...) action so it
     *  is really where the tree knows its token boundaries.
     *
     *  NOTE: if this is a nil root (children list then nil, start/stop
     *  are computed from start of first child and stop of last child.
     *  The nil root points into the children list, which should still
     *  point to the original tokens from your original AST.
     *
     *  Called automatically when constructing ASTs.
     */
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
    
    public int getTokenStartIndex(Object t);
    public int getTokenStopIndex(Object t);
    
    /** Replace child at position i (0..n-1) with t; t must be non-null and non-nil node. */
    public void setChild(Object t, int i, Object child);
    
    /** Delete child at position i (0..n-1) and shift children down from right. */
    public Object deleteChild(Object t, int i);
    
    /** Is the tree node t considered a nil node used to make lists
     *  of child nodes?
     */
    public boolean isNil(Object tree);
    
    /** Duplicate single node, but not its children; single node dup. */
    public Object dupNode(Object t);
    
    /** This method returns whatever object represents the data at this node. For
     *  example, for CommonTree, it returns the token.  For your AST nodes,
     *  it could return the AST node.  The only requirement is that it have a
     *  toString() method and you can print it out.  This is used to print
     *  out lists of AST nodes (so that toString() is invoked on the node
     *  repeatedly).
     *
     *  Essentially toString() is used on the returned object.
     *
     *  Default is just toString() on whatever the node is.
     *
     *  Override if you are using your own ast nodes.
     */
    public Object getNodePayload(Object node);
    
    /** Return something analogous to the usual debug string for a parse tree
     *  such as: (+ 1 2).  Print it like a binary tree in LISP form.
     *  Return "nil" if the tree is a nil node.  Do not print any parens for a
     *  nil node.  The AST node type or token type is printed followed by
     *  the children.
     *
     *  Return "nil" if t==null
     */
    public String toString(Object t);
    
    /** Return a string for an entire tree not just a node */
    public String toString(Object t, String[] ruleNames);
    
    /** A more verbose AST toString.  Pass in a rule name vector for use with
     *  generated parsers.  I computed these as integers and then constructed
     *  a String vector, but a String[] is more efficient.  Null if you don't
     *  have a String[] to pass in.
     */
    public String toString(Object t, String[] ruleNames);
}

/**
 * Default tree adaptor implementation
 */
public class CommonTreeAdaptor extends BaseTreeAdaptor {
    /** Duplicate a single tree node.
     *  Override if you want another kind of node to be built.
     */
    public Object dupNode(Object t);
    
    public Object create(Token payload);
    
    /** Tell me how to create a token for use with imaginary token nodes.
     *  For example, there is probably no input symbol associated with decl
     *  node types.  This method is executed when you type create(type).
     */
    public Token createToken(int tokenType, String text);
    
    /** Tell me how to create a token for use with imaginary token nodes.
     *  For example, there is probably no input symbol associated with decl
     *  node types.  This method is executed when you type create int).
     */
    public Token createToken(Token fromToken);
    
    /** Track start/stop token for subtree root created for a rule.
     *  Only works with Tree nodes.  For rules that match nothing,
     *  seems like this will yield start=i and stop=i-1 in a nil node.
     *  Might be useful info so I'll not force to be i..i.
     */
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
    
    public int getTokenStartIndex(Object t);
    
    public int getTokenStopIndex(Object t);
    
    public String getText(Object t);
    
    /** Tell the adaptor the type of the child token of root token t.
     *  Don't specify an invalid index i.
     */
    public void setType(Object t, int type);
    
    public int getType(Object t);
    
    /** For tree parsing, return the token object associated with node t.
     *  This is used mainly for error reporting.
     */
    public Token getToken(Object t);
    
    /** Where are token start/stop boundaries for subtree rooted at t?
     *  This is not a method in any interface; I think the parser calls
     *  this method during AST construction.  This method is also called
     *  when setting token boundaries manually such as with tree rewrite
     *  operations.
     */
    public void setChild(Object t, int i, Object child);
    
    public Object deleteChild(Object t, int i);
    
    /** Is the tree node t considered a nil node used to make lists
     *  of child nodes?
     */
    public boolean isNil(Object tree);
    
    /** For tree parsing, I need to know the token type of a node */
    public void setText(Object t, String text);
    
    /** For tree parsing, I need to know the token type of a node */
    public String getText(Object t);
    
    /** For tree parsing, I need to know the token type of a node */
    public void setType(Object t, int type);
    
    public int getType(Object t);
    
    /** For tree parsing, return the token object associated with node t.
     *  This is used mainly for error reporting.
     */
    public Token getToken(Object t);
    
    public String toString(Object t);
    
    public String toString(Object t, String[] ruleNames);
}

import org.antlr.runtime.tree.*;
import org.antlr.runtime.*;

// Create tree adaptor
TreeAdaptor adaptor = new CommonTreeAdaptor();

// Create nodes
Object root = adaptor.create(MyParser.PLUS, "+");
Object left = adaptor.create(MyParser.IDENTIFIER, "x");
Object right = adaptor.create(MyParser.NUMBER, "42");

// Build tree
adaptor.addChild(root, left);
adaptor.addChild(root, right);

// Make tree: ^(PLUS x 42)
System.out.println("Tree: " + adaptor.toString(root));

// Navigation
int childCount = adaptor.getChildCount(root);
Object firstChild = adaptor.getChild(root, 0);
String firstChildText = adaptor.getText(firstChild);

// Tree manipulation
Object newChild = adaptor.create(MyParser.IDENTIFIER, "y");
adaptor.setChild(root, 1, newChild); // Replace second child

// Create tree with token boundaries
Token startToken = new CommonToken(MyParser.IDENTIFIER, "x");
Token stopToken = new CommonToken(MyParser.NUMBER, "42"); 
adaptor.setTokenBoundaries(root, startToken, stopToken);

public class CommonErrorNode extends CommonTree {
    public IntStream input;
    public Token start;
    public Token stop;
    public RecognitionException trappedException;
    
    public CommonErrorNode(TokenStream input, Token start, Token stop, RecognitionException e);
    
    public boolean isNil();
    public int getType();
    public String getText();
    public String toString();
}

public class ParseTree extends BaseTree {
    public Object payload;
    public List<Token> hiddenTokens;
    
    public ParseTree(Object payload);
    
    public Tree dupNode();
    public int getType();
    public String getText();
    public int getTokenStartIndex();
    public int getTokenStopIndex();
    public String toString();
    public String toStringWithHiddenTokens();
    public String toInputString();
}

// Create tree manually: ^(PLUS ^(MULT x 2) y)
TreeAdaptor adaptor = new CommonTreeAdaptor();

Object plus = adaptor.create(PLUS, "+");
Object mult = adaptor.create(MULT, "*");
Object x = adaptor.create(IDENTIFIER, "x");
Object two = adaptor.create(NUMBER, "2");
Object y = adaptor.create(IDENTIFIER, "y");

// Build multiplication subtree
adaptor.addChild(mult, x);
adaptor.addChild(mult, two);

// Build addition tree
adaptor.addChild(plus, mult);
adaptor.addChild(plus, y);

System.out.println("Tree: " + adaptor.toString(plus));

public void walkTree(Object tree, TreeAdaptor adaptor) {
    if (tree == null) return;
    
    // Process current node
    System.out.println("Node: " + adaptor.getText(tree) + 
                      " Type: " + adaptor.getType(tree));
    
    // Visit all children
    int childCount = adaptor.getChildCount(tree);
    for (int i = 0; i < childCount; i++) {
        Object child = adaptor.getChild(tree, i);
        walkTree(child, adaptor);
    }
}

public Object copyTree(Object tree, TreeAdaptor adaptor) {
    if (tree == null) return null;
    
    // Duplicate root node
    Object copy = adaptor.dupNode(tree);
    
    // Copy all children recursively
    int childCount = adaptor.getChildCount(tree);
    for (int i = 0; i < childCount; i++) {
        Object child = adaptor.getChild(tree, i);
        Object childCopy = copyTree(child, adaptor);
        adaptor.addChild(copy, childCopy);
    }
    
    return copy;
}

// Set boundaries for manually constructed trees
Token startToken = /* first token */;
Token stopToken = /* last token */;

Object tree = adaptor.create(EXPRESSION);
// ... add children ...

adaptor.setTokenBoundaries(tree, startToken, stopToken);

// Get boundaries later
int start = adaptor.getTokenStartIndex(tree);
int stop = adaptor.getTokenStopIndex(tree);

/**
 * Build and navigate trees with string patterns and queries
 */
public class TreeWizard {
    protected TreeAdaptor adaptor;
    protected Map<String, Integer> tokenNameToTypeMap;
    
    public interface ContextVisitor {
        public void visit(Object t, Object parent, int childIndex, Map<String, Object> labels);
    }
    
    public static abstract class Visitor implements ContextVisitor {
        public void visit(Object t, Object parent, int childIndex, Map<String, Object> labels);
        public abstract void visit(Object t);
    }
    
    public static class TreePattern extends CommonTree {
        public String label;
        public boolean hasTextArg;
        public TreePattern(Token payload);
    }
    
    public TreeWizard(TreeAdaptor adaptor);
    public TreeWizard(TreeAdaptor adaptor, Map<String, Integer> tokenNameToTypeMap);
    public TreeWizard(TreeAdaptor adaptor, String[] tokenNames);
    public TreeWizard(String[] tokenNames);
    
    /** Compute a Map<String, Integer> that is an inverted index of
     *  tokenNames (which maps int token types to names).
     */
    public Map<String, Integer> computeTokenTypes(String[] tokenNames);
    
    /** Using the map of token names to token types, return the type */
    public int getTokenType(String tokenName);
    
    /** Walk entire tree and make a node name to nodes mapping.
     *  For now, use recursion but later nonrecursive version may be
     *  more efficient.  This method can be used to prep for a way to
     *  search a tree.
     */
    public Map<Integer, List> index(Object t);
    
    /** Return a List of tree nodes with token type ttype */
    public List find(Object t, int ttype);
    
    /** Return a List of subtrees matching pattern */
    public List find(Object t, String pattern);
    
    public Object findFirst(Object t, int ttype);
    public Object findFirst(Object t, String pattern);
    
    /** Visit every ttype node in t, invoking the visitor.  This is a quicker
     *  version of the general visit(t, pattern) method.  The labels arg
     *  of the visitor action method is never set (it's null) since using
     *  a token type rather than a pattern doesn't let us set a label.
     */
    public void visit(Object t, int ttype, ContextVisitor visitor);
    
    /** For all subtrees that match the pattern, execute the visit action.
     *  The implementation uses the root node of the pattern in combination
     *  with visit(t, ttype, visitor) so nil-rooted patterns are not allowed.
     *  Patterns with wildcard roots are also not allowed.
     */
    public void visit(Object t, String pattern, ContextVisitor visitor);
    
    /** Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels
     *  on the various nodes and '.' (dot) as the node/subtree wildcard,
     *  return true if the pattern matches and fill the labels Map with
     *  the labels pointing at the appropriate nodes.  Return false if
     *  the pattern is malformed or the tree does not match.
     *
     *  If a node specifies a text arg in pattern, that must match.
     *  For example, (ASSIGN ID["x"] .) means the ID node must have
     *  text "x" and structure (ASSIGN ID *).  The second ID means that
     *  the ID must have the text "x".
     *
     *  TODO: what if we want to assign a node to a label?  If #foo is
     *  always root node, then %foo is the node w/o making it the root.
     *  This is like return label and input/output arg.
     *
     *  The general form is (#label:)? name[text]? ('(' child+ ')')?
     *  where '.' is text and name is same as '.' except text.
     */
    public boolean parse(Object t, String pattern, Map<String, Object> labels);
    public boolean parse(Object t, String pattern);
    
    /** Create a tree or node from the indicated tree pattern that has
     *  token names and label references
     */
    public Object create(String pattern);
    
    /** Compare t1 and t2; return true if token types/text, structure match exactly.
     *  The trees are examined in their entirety so that (A B) does not match
     *  (A B C) nor (A (B C)). 
     */
    public boolean equals(Object t1, Object t2, TreeAdaptor adaptor);
    public boolean equals(Object t1, Object t2);
}

/**
 * Tree traversal with visitor pattern
 */
public class TreeVisitor {
    protected TreeAdaptor adaptor;
    
    public TreeVisitor(TreeAdaptor adaptor);
    public TreeVisitor();
    
    /** Visit every node in tree t and trigger an action for each node
     *  before/after having visited all of its children.  Bottom up walk.
     *  Execute an action for every node in the tree using a bottom/up walk.
     *  Return same or modified tree structure.
     *
     *  It returns Object because the user may change the root and even
     *  the tree type.  The invariant is that the return value is the new tree,
     *  if any, that should take the place of this node.
     *
     *  Note that the child list is altered by this method as it does its
     *  work.  Do not rely on the children list to be unmodified after this call.
     *  Additionally, upon entry the current node's parent should be correct
     *  in that this visitor may call setParent().  Make sure to call
     *  freshenParentAndChildIndexes() before calling this method.
     */
    public Object visit(Object t, TreeVisitorAction action);
}

/**
 * Interface for tree visitor actions
 */
public interface TreeVisitorAction {
    /** Execute an action before visiting children of t.  Return t or
     *  a rewritten t.  It is up to the visitor to decide what to do
     *  with the return value.  Children of returned value will be
     *  visited if using TreeVisitor.visit().
     */
    public Object pre(Object t);
    
    /** Execute an action after visiting children of t.  Return t or
     *  a rewritten t.  It is up to the visitor to decide what to do
     *  with the return value.
     */
    public Object post(Object t);
}

/**
 * Iterator for tree traversal
 */
public class TreeIterator implements Iterator<Object> {
    protected TreeAdaptor adaptor;
    protected Object root;
    protected Object tree;
    protected boolean firstTime;
    
    public TreeIterator(CommonTree tree);
    public TreeIterator(TreeAdaptor adaptor, Object tree);
    
    public void reset();
    public boolean hasNext();
    public Object next();
    public void remove() throws UnsupportedOperationException;
}

import org.antlr.runtime.tree.*;
import org.antlr.runtime.*;

// TreeWizard examples
String[] tokenNames = {"PLUS", "MULT", "ID", "INT"};
TreeWizard wiz = new TreeWizard(adaptor, tokenNames);

// Find all nodes of a specific type
List<Object> plusNodes = wiz.find(tree, wiz.getTokenType("PLUS"));

// Find nodes matching a pattern
List<Object> assignments = wiz.find(tree, "(ASSIGN %lhs:ID %rhs:.)");

// Parse and extract labeled nodes
Map<String, Object> labels = new HashMap<String, Object>();
if (wiz.parse(tree, "(ASSIGN %lhs:ID %rhs:.)", labels)) {
    Object lhs = labels.get("lhs");
    Object rhs = labels.get("rhs");
    System.out.println("Assignment: " + adaptor.getText(lhs) + " = " + adaptor.getText(rhs));
}

// Create tree from pattern
Object newTree = wiz.create("(PLUS ID[\"x\"] INT[\"42\"])");

// Visit all nodes of a type
wiz.visit(tree, wiz.getTokenType("ID"), new TreeWizard.Visitor() {
    public void visit(Object t) {
        System.out.println("Found identifier: " + adaptor.getText(t));
    }
});

// TreeVisitor examples
TreeVisitor visitor = new TreeVisitor(adaptor);

// Visit tree with custom action
Object newTree = visitor.visit(tree, new TreeVisitorAction() {
    public Object pre(Object t) {
        System.out.println("Entering: " + adaptor.getText(t));
        return t; // Continue with original node
    }
    
    public Object post(Object t) {
        System.out.println("Leaving: " + adaptor.getText(t));
        
        // Example: replace all ID nodes with IDENTIFIER nodes
        if (adaptor.getType(t) == MyParser.ID) {
            Object newNode = adaptor.create(MyParser.IDENTIFIER, adaptor.getText(t));
            return newNode;
        }
        return t;
    }
});

// TreeIterator examples
TreeIterator iter = new TreeIterator(adaptor, tree);
while (iter.hasNext()) {
    Object node = iter.next();
    System.out.println("Node: " + adaptor.getText(node));
}