0
# Tree Construction and Manipulation
1

2
Abstract Syntax Tree (AST) construction, traversal, and manipulation utilities. The tree package provides comprehensive support for building parse trees, ASTs, tree rewriting, and tree pattern matching.
3

4
## Capabilities
5

6
### Tree Interface
7

8
Base interface for all tree nodes providing hierarchical structure operations.
9

10
```java { .api }
11
/**
12
 * Basic tree node interface
13
 */
14
public interface Tree {
15
    /** Get a child at index i. */
16
    public Tree getChild(int i);
17
    
18
    /** How many children are there? If there is none, return 0. */
19
    public int getChildCount();
20
    
21
    /** Get the parent for this node; if null, implies node is root */
22
    public Tree getParent();
23
    
24
    /** Set the parent and child index; implies node does not yet have parent */
25
    public void setParent(Tree t);
26
    
27
    /** Is there an ancestor with this token type? */
28
    public boolean hasAncestor(int ttype);
29
    
30
    /** Walk up and get list of this node's ancestors.  First node of
31
     *  list is the root and the last is the parent of this node.
32
     */
33
    public List<Tree> getAncestors();
34
    
35
    /** This node is what child index? 0..n-1 */
36
    public int getChildIndex();
37
    
38
    /** Set the child index. */
39
    public void setChildIndex(int index);
40
    
41
    /** Walk tree and visit each node, setting parent and child index. */
42
    public void freshenParentAndChildIndexes();
43
    
44
    /** Add t as child of this node.  Warning: if t has no children, but
45
     *  child does and child isNil then this routine moves children to t via
46
     *  t.replaceChildren(child.children).
47
     */
48
    public void addChild(Tree t);
49
    
50
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
51
    public void setChild(int i, Tree t);
52
    
53
    /** Delete the child at index i (0..n-1) and return it; null if no such child */
54
    public Object deleteChild(int i);
55
    
56
    /** Delete children from start to stop and replace with t even if t is
57
     *  a list (nil-root tree). Num of children can increase or decrease.
58
     *  For huge child lists, inserting children can force walking rest of
59
     *  children to set their childindex; could be slow.
60
     */
61
    public void replaceChildren(int startChildIndex, int stopChildIndex, Object t);
62
    
63
    /** Indicates the node is a nil node but may still have children, meaning
64
     *  the tree is a flat list.
65
     */
66
    public boolean isNil();
67
    
68
    /** What is the smallest token index (indexing from 0) for this node
69
     *  and its children?
70
     */
71
    public int getTokenStartIndex();
72
    
73
    /** What is the largest token index (indexing from 0) for this node
74
     *  and its children?
75
     */
76
    public int getTokenStopIndex();
77
    
78
    public Tree dupNode();
79
    
80
    /** Return a token type; needed for tree parsing */
81
    public int getType();
82
    
83
    public String getText();
84
    
85
    /** In case we don't have a token payload, what is the line for errors? */
86
    public int getLine();
87
    
88
    public int getCharPositionInLine();
89
    
90
    public String toString();
91
    
92
    /** Print out a whole tree in LISP form. {@link #getType} is used on the
93
     *  node payloads to get the text for the nodes.  Detect
94
     *  parse trees and extract data appropriately.
95
     */
96
    public String toStringTree();
97
}
98
```
99

100
### Base Tree Implementation
101

102
Abstract base implementation of the Tree interface providing common functionality.
103

104
```java { .api }
105
/**
106
 * Base implementation of Tree interface
107
 */
108
public abstract class BaseTree implements Tree {
109
    /** Child nodes if any */
110
    protected List<Tree> children;
111
    
112
    public BaseTree();
113
    public BaseTree(Tree node);
114
    
115
    /** Get a child at index i; null if index out of range */
116
    public Tree getChild(int i);
117
    
118
    /** How many children are there? If there is none, return 0. */
119
    public int getChildCount();
120
    
121
    /** Add t as child of this node.  Warning: if t has no children, but
122
     *  child does and child isNil then this routine moves children to t via
123
     *  t.replaceChildren(child.children).
124
     */
125
    public void addChild(Tree t);
126
    
127
    /** Add all elements of kids list as children of this node */
128
    public void addChildren(List<Tree> kids);
129
    
130
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
131
    public void setChild(int i, Tree t);
132
    
133
    /** Delete the child at index i (0..n-1) and return it; null if no such child */
134
    public Object deleteChild(int i);
135
    
136
    /** Delete children from start to stop and replace with t even if t is
137
     *  a list (nil-root tree). Num of children can increase or decrease.
138
     *  For huge child lists, inserting children can force walking rest of
139
     *  children to set their childindex; could be slow.
140
     */
141
    public void replaceChildren(int startChildIndex, int stopChildIndex, Object t);
142
    
143
    /** Override in a subclass to change the impl of children list */
144
    protected List<Tree> createChildrenList();
145
    
146
    /** Indicates the node is a nil node but may still have children, meaning
147
     *  the tree is a flat list.
148
     */
149
    public boolean isNil();
150
    
151
    /** Walk tree and visit each node, setting parent and child index. */
152
    public void freshenParentAndChildIndexes();
153
    
154
    public void freshenParentAndChildIndexesDeeply();
155
    
156
    protected void freshenParentAndChildIndexes(int offset);
157
    
158
    public void sanityCheckParentAndChildIndexes();
159
    public void sanityCheckParentAndChildIndexes(Tree parent, int i);
160
    
161
    /** What is the smallest token index (indexing from 0) for this node
162
     *  and its children?
163
     */
164
    public int getTokenStartIndex();
165
    
166
    /** What is the largest token index (indexing from 0) for this node
167
     *  and its children?
168
     */
169
    public int getTokenStopIndex();
170
    
171
    public abstract Tree dupNode();
172
    public abstract int getType();
173
    public abstract String getText();
174
    
175
    /** In case we don't have a token payload, what is the line for errors? */
176
    public int getLine();
177
    public int getCharPositionInLine();
178
    
179
    public String toString();
180
    
181
    /** Print out a whole tree in LISP form. {@link #getType} is used on the
182
     *  node payloads to get the text for the nodes.  Detect
183
     *  parse trees and extract data appropriately.
184
     */
185
    public String toStringTree();
186
    
187
    public List<Tree> getAncestors();
188
    
189
    /** Walk up and get first ancestor with this token type. */
190
    public Tree getAncestor(int ttype);
191
    
192
    /** Return a list of all ancestors of this node.  The first node of
193
     *  list is the root and the last is the parent of this node.
194
     */
195
    public List<Tree> getAncestors();
196
    
197
    /** Is there an ancestor with this token type? */
198
    public boolean hasAncestor(int ttype);
199
    
200
    /** Walk up and get first ancestor with this token type. */
201
    public Tree getAncestor(int ttype);
202
    
203
    /** Return a list of all ancestors of this node.  The first node of
204
     *  list is the root and the last is the parent of this node.
205
     */
206
    public List<Tree> getAncestors();
207
    
208
    public Tree getParent();
209
    public void setParent(Tree t);
210
    public int getChildIndex();
211
    public void setChildIndex(int index);
212
}
213
```
214

215
### Common Tree
216

217
Standard tree node implementation using tokens as payloads.
218

219
```java { .api }
220
/**
221
 * Default tree node implementation
222
 */
223
public class CommonTree extends BaseTree {
224
    /** A single token is the payload */
225
    public Token token;
226
    
227
    /** What token indexes bracket all tokens associated with this node
228
     *  and below?
229
     */
230
    protected int startIndex = -1, stopIndex = -1;
231
    
232
    /** Who is the parent node of this node; if null, implies node is root */
233
    public CommonTree parent;
234
    
235
    /** What index is this node in the child list? Range: 0..n-1 */
236
    public int childIndex = -1;
237
    
238
    public CommonTree();
239
    public CommonTree(CommonTree node);
240
    public CommonTree(Token t);
241
    
242
    public Token getToken();
243
    
244
    public Tree dupNode();
245
    
246
    /** Return a token type; needed for tree parsing */
247
    public int getType();
248
    
249
    public String getText();
250
    
251
    /** In case we don't have a token payload, what is the line for errors? */
252
    public int getLine();
253
    
254
    public int getCharPositionInLine();
255
    
256
    public int getTokenStartIndex();
257
    public void setTokenStartIndex(int index);
258
    
259
    public int getTokenStopIndex();
260
    public void setTokenStopIndex(int index);
261
    
262
    /** For every node in this subtree, make sure children[i] points to
263
     *  a child i.  Walk depth first, visit bottom up.  That way, all the
264
     *  children of a node are fixed first.
265
     */
266
    public void setChildIndex(int index);
267
    
268
    public Tree getParent();
269
    public void setParent(Tree t);
270
    
271
    public int getChildIndex();
272
    
273
    /** Indicates the node is a nil node but may still have children, meaning
274
     *  the tree is a flat list.
275
     */
276
    public boolean isNil();
277
    
278
    public String toString();
279
}
280
```
281

282
**Usage Examples:**
283

284
```java
285
import org.antlr.runtime.tree.*;
286
import org.antlr.runtime.*;
287

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

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

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

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

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

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

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

315
### Tree Adaptor
316

317
Interface for tree manipulation operations and customizable tree construction.
318

319
```java { .api }
320
/**
321
 * Interface for tree manipulation operations
322
 */
323
public interface TreeAdaptor {
324
    /** Create a tree node from Token object; for CommonTree type trees,
325
     *  no need to specify a Token object.  The token payload should
326
     *  contain the appropriate type and text info.
327
     */
328
    public Object create(Token payload);
329
    
330
    /** Duplicate a tree, assuming this is a root node of a tree--
331
     *  duplicate everything underneath.  This is done via the adaptor
332
     *  rather than the tree itself to handle different types of trees.
333
     */
334
    public Object dupTree(Object tree);
335
    
336
    /** Duplicate a single tree node, but not its children; single node dup. */
337
    public Object dupNode(Object t);
338
    
339
    /** Return the type; allow for later extension via subclassing. */
340
    public int getType(Object t);
341
    
342
    /** In some applications, it would be useful to track parent pointers
343
     *  or the index of a child.  Tree and Tree adaptor interfaces are
344
     *  intended to be as minimal as possible.
345
     */
346
    public void setText(Object t, String text);
347
    
348
    public String getText(Object t);
349
    
350
    /** Get the token associated with this node; if you are not using
351
     *  CommonTree, then you must override this in your own adaptor.
352
     */
353
    public Token getToken(Object t);
354
    
355
    /** Where are token start/stop boundaries for subtree rooted at t?
356
     *  The token information is not set unless you are using
357
     *  TokenRewriteStream to construct and emit the original or
358
     *  modified token stream.  The adaptor is responsible for setting
359
     *  these values.  Many implementations will use the CommonTree
360
     *  that tracks start/stop token indexes.  If you are mixing up tree
361
     *  formats, then the easiest thing to do is make sure this method
362
     *  on your TreeAdaptor returns something that cooresponds to Token.getTokenIndex().
363
     *  Return -1 if you don't use tokens/tokenstream.
364
     */
365
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
366
    
367
    public int getTokenStartIndex(Object t);
368
    public int getTokenStopIndex(Object t);
369
    
370
    /** Get a child 0..n-1 node */
371
    public Object getChild(Object t, int i);
372
    
373
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
374
    public void setChild(Object t, int i, Object child);
375
    
376
    /** Remove ith child and shift children down from right. */
377
    public Object deleteChild(Object t, int i);
378
    
379
    /** How many children?  If 0, then this is a leaf node */
380
    public int getChildCount(Object t);
381
    
382
    /** Return an ID for this node, which is unique within the life of
383
     *  this TreeAdaptor.  Usually it's the memory address of the node.
384
     *  If we're building trees from a stream, then ID should be the
385
     *  index in the stream.
386
     */
387
    public int getUniqueID(Object node);
388
    
389
    // REWRITE SUPPORT
390
    
391
    /** Tell me how to create a token for use with imaginary token nodes.
392
     *  For example, there is probably no input symbol associated with decl
393
     *  node types.  This method is executed when you type create(type).
394
     */
395
    public Object create(int tokenType, Token fromToken);
396
    public Object create(int tokenType, Token fromToken, String text);
397
    public Object create(int tokenType, String text);
398
    
399
    /** Make tree t the new root of oldRoot; oldRoot is a lost child of t. */
400
    public Object becomeRoot(Object newRoot, Object oldRoot);
401
    
402
    /** If oldRoot is a nil root, just copy or move the children to newRoot.
403
     *  If not a nil root, make oldRoot a child of newRoot.
404
     *
405
     *     old=^(nil a b c), new=r yields ^(r a b c)
406
     *     old=^(a b c), new=r yields ^(r ^(a b c))
407
     *
408
     *  If newRoot is a nil-rooted single child tree, use the single
409
     *  child as the new root node.
410
     *
411
     *     old=^(nil a b c), new=^(nil r) yields ^(r a b c)
412
     *     old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
413
     *
414
     *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
415
     *
416
     *     old=null, new=r yields r
417
     *     old=null, new=^(nil r) yields ^(nil r)
418
     *
419
     *  Return newRoot.  Throw an exception if newRoot is not a nil node
420
     *  and has children.  This would mean that the new root has both
421
     *  the oldRoot and its own children.  The definition of ^(...) is that
422
     *  it is make the ^(a b c) the root and make the ^(a b c) a child of ^(r ...)
423
     */
424
    public Object rulePostProcessing(Object root);
425
    
426
    /** Add a child to the tree t.  If child is a flat tree (a list), make all
427
     *  in list children of t.  Warning: if t has no children, but child does
428
     *  and child isNil then this routine moves children to t via
429
     *  t.replaceChildren(child.children).
430
     */
431
    public void addChild(Object t, Object child);
432
    
433
    /** If oldRoot is a nil root, just copy or move the children to newRoot.
434
     *  If not a nil root, make oldRoot a child of newRoot.
435
     *
436
     *   old=^(nil a b c), new=r yields ^(r a b c)
437
     *   old=^(a b c), new=r yields ^(r ^(a b c))
438
     *
439
     *  If newRoot is a nil-rooted single child tree, use the single
440
     *  child as the new root node.
441
     *
442
     *   old=^(nil a b c), new=^(nil r) yields ^(r a b c)
443
     *   old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
444
     *
445
     *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
446
     *
447
     *   old=null, new=r yields r
448
     *   old=null, new=^(nil r) yields ^(nil r)
449
     *
450
     *  Return newRoot.  Throw an exception if newRoot is not a nil node
451
     *  and has children.  This would mean that the new root has both
452
     *  the oldRoot and its own children.  The definition of ^(...) is that
453
     *  it is make the ^(a b c) the root and make the ^(a b c) a child of ^(r ...)
454
     */
455
    public Object becomeRoot(Token newRoot, Object oldRoot);
456
    
457
    /** Create a node for newRoot make it a root of oldRoot.
458
     *  If oldRoot is a nil root, just copy or move the children to newRoot.
459
     *  If not a nil root, make oldRoot a child of newRoot.
460
     *  Return node newRoot.
461
     */
462
    public Object create(int tokenType, Token fromToken);
463
    public Object create(int tokenType, Token fromToken, String text);
464
    public Object create(int tokenType, String text);
465
    
466
    /** For identifying trees.
467
     *
468
     *  How to identify nodes so we can say "add node to a prior node"?
469
     *  Even becomeRoot is an issue.  Use System.identityHashCode(node)
470
     *  usually.
471
     */
472
    public int getUniqueID(Object node);
473
    
474
    
475
    // TREE PARSING
476
    
477
    /** For tree parsing, I need to know the token type of a node */
478
    public int getType(Object t);
479
    
480
    /** Node constructors can set the type of a node */
481
    public void setType(Object t, int type);
482
    
483
    public String getText(Object t);
484
    
485
    /** Node constructors can set the text of a node */
486
    public void setText(Object t, String text);
487
    
488
    /** Return the token object from which this node was created.
489
     *  Currently used only for printing an error message.
490
     *  The error display routine in BaseRecognizer needs to
491
     *  display where the input the error occurred. If your
492
     *  tree of limitation does not store information that can
493
     *  lead you to the token, you can create a token filled with
494
     *  the appropriate information and pass that back.  See
495
     *  BaseRecognizer.getErrorMessage().
496
     */
497
    public Token getToken(Object t);
498
    
499
    /** Where are token start/stop boundaries for subtree rooted at t?
500
     *  For rules that create AST nodes, this method is called on
501
     *  the returned AST node from every rule invocation.  The result
502
     *  is the collapse of all child boundaries to that of the parent.
503
     */
504
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
505
    
506
    /** Return the first token associated with this node.  If this node
507
     *  is associated with Token objects, you can access this start
508
     *  token, and from there you can access the start token's input
509
     *  stream.  Return null if no such token.
510
     */
511
    public int getTokenStartIndex(Object t);
512
    public int getTokenStopIndex(Object t);
513
    
514
    /** Get a child 0..n-1 node */
515
    public Object getChild(Object t, int i);
516
    
517
    /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */
518
    public void setChild(Object t, int i, Object child);
519
    
520
    /** Remove ith child and shift children down from right. */
521
    public Object deleteChild(Object t, int i);
522
    
523
    /** How many children?  If 0, then this is a leaf node */
524
    public int getChildCount(Object t);
525
    
526
    /** Is the tree node considered a nil node used to make lists
527
     *  of child nodes?
528
     */
529
    public boolean isNil(Object tree);
530
    
531
    /** Return something analogous to the usual debug string for
532
     *  a parse tree such as: (+ 1 2).
533
     */
534
    public String toString(Object t);
535
    
536
    /** Return a string for an entire tree not just a node */
537
    public String toString(Object t, String[] ruleNames);
538
    
539
    /** Return a string for a range of nodes encompassed in rule r at
540
     *  positions begin to end (not end+1!).  For example,
541
     *  toString(t, "expr", 2, 5) can print the tokens from
542
     *  expr rule invocations 2 through 5.
543
     */
544
    public String toString(Object t, int begin, int end);
545
    
546
    /** Track start/stop token for subtree root created for a rule.
547
     *  Only works with Tree nodes.  For rules that match nothing,
548
     *  seems like this will yield start=i and stop=i-1 in a nil node.
549
     *  Might be useful info so I'll not force to be i..i.
550
     */
551
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
552
    
553
    /** Get the token start index for this subtree; return -1 if no such index */
554
    public int getTokenStartIndex(Object t);
555
    
556
    /** Get the token stop index for this subtree; return -1 if no such index */
557
    public int getTokenStopIndex(Object t);
558
    
559
    /** Replace any child at index i (0..n-1) with t; t must be non-null and non-nil. */
560
    public void setChild(Object t, int i, Object child);
561
    
562
    /** Delete child at index i (0..n-1) and return it; null if not found. */
563
    public Object deleteChild(Object t, int i);
564
    
565
    /** Is the tree t considered a nil node used to make lists
566
     *  of child nodes?
567
     */
568
    public boolean isNil(Object tree);
569
    
570
    /** Return something analogous to the usual debug string for
571
     *  a parse tree such as: (+ 1 2).
572
     */
573
    public String toString(Object t);
574
    
575
    /** Create a new node derived from a token, with a new token type.
576
     *  This is invoked from an imaginary node ref on right side of a
577
     *  tree grammar rule, for example:
578
     *
579
     *     This reference to NEW in tree parser...
580
     *     ^(NEW type identifier)
581
     *
582
     *     must create a new node of token type NEW with text "NEW".
583
     *     If you are creating a string-based AST with UniversalTree for
584
     *     example, then a 'new' UniversalTree(NEW, "NEW") would be
585
     *     returned from this method.
586
     *
587
     *     This method should be overridden.  If you care about the
588
     *     Token object from which this node to be created is associated,
589
     *     override this method.  Otherwise, override the String version.
590
     *     NOTE: the Rule.ctor(Token, String) is called by the default
591
     *     implementation.
592
     *
593
     *     If you are building trees for a language like C that has
594
     *     no explicit list structure to represent a function call,
595
     *     but you would like to overlay some nodes to represent
596
     *     the various parts such as argument list, return value,
597
     *     function name, etc..., then you would return a node
598
     *     representing that construct.
599
     */
600
    public Object create(int tokenType, Token fromToken);
601
    
602
    /** Same as create(tokenType,fromToken) except set the text too.
603
     *  This is useful for converting GENERIC['"<"] to GENERIC["<";] for
604
     *  example, where the GENERIC node is associated with the original
605
     *  token from the input stream.
606
     */
607
    public Object create(int tokenType, Token fromToken, String text);
608
    
609
    /** Create a new node derived from a token, with a new token type
610
     *  and new text.  This is invoked from an imaginary node ref on right
611
     *  side of a tree grammar rule, for example:
612
     *
613
     *     This reference to NEW in tree parser...
614
     *     ^(NEW["foo"] type identifier)
615
     *
616
     *     must create a new node of token type NEW with text "foo".
617
     *     If you are creating a string-based AST with UniversalTree for
618
     *     example, then a 'new' UniversalTree(NEW, "foo") would be
619
     *     returned from this method.
620
     */
621
    public Object create(int tokenType, String text);
622
    
623
    /** Does the tree adpator support unique IDs? how to implement adapt()
624
     *  depends on this. buildTree() calls adaptor.getUniqueID(node).
625
     *  Override if you're using your own BaseTree-derived objects.
626
     */
627
    public boolean hasUniqueID(Object node);
628
    
629
    /** For tree parsing, return the token type of a node */
630
    public int getType(Object t);
631
    
632
    public void setType(Object t, int type);
633
    
634
    public String getText(Object t);
635
    
636
    public void setText(Object t, String text);
637
    
638
    /** For tree parsing, return the token object associated with node t.
639
     *  For BasicTree, this is just the token.  For CommonTree, this is
640
     *  the token.  For your AST nodes, this method must return the
641
     *  Token object from which this node was created.  This is used for
642
     *  printing out error messages that include line/column info.
643
     *
644
     *  Essentially, the error message is trying to figure out what Token
645
     *  object was associated with the erroneous AST node.  One could
646
     *  also use a hash table to map AST nodes to tokens but I think
647
     *  that's overkill.
648
     */
649
    public Token getToken(Object t);
650
    
651
    /** Set the token boundaries for subtree root t.  The boundaries are
652
     *  stored on the node as start/stop token indexes.  This is done
653
     *  automatically when parsing with output=AST but the boundaries
654
     *  must be set when invoking actions manually such as tree construction
655
     *  in actions, building adapters, etc...  When using ^(...) make syntax
656
     *  in actions, the form ^(root child1 ... childN) causes ANTLR to invoke
657
     *  the adaptor methods:
658
     *
659
     *    r = create(type);
660
     *    addChild(r, child1);
661
     *    ...
662
     *    addChild(r, childN);
663
     *    setTokenBoundaries(r, firstToken, lastToken);
664
     *
665
     *  If you are building ASTs manually in a translating tree parser,
666
     *  then you need to be careful to set the token boundaries explicitly.
667
     *  Look at the examples in the tree/ dir for how to do this.  This
668
     *  method is the final method called in the ^(root ...) action so it
669
     *  is really where the tree knows its token boundaries.
670
     *
671
     *  NOTE: if this is a nil root (children list then nil, start/stop
672
     *  are computed from start of first child and stop of last child.
673
     *  The nil root points into the children list, which should still
674
     *  point to the original tokens from your original AST.
675
     *
676
     *  Called automatically when constructing ASTs.
677
     */
678
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
679
    
680
    public int getTokenStartIndex(Object t);
681
    public int getTokenStopIndex(Object t);
682
    
683
    /** Replace child at position i (0..n-1) with t; t must be non-null and non-nil node. */
684
    public void setChild(Object t, int i, Object child);
685
    
686
    /** Delete child at position i (0..n-1) and shift children down from right. */
687
    public Object deleteChild(Object t, int i);
688
    
689
    /** Is the tree node t considered a nil node used to make lists
690
     *  of child nodes?
691
     */
692
    public boolean isNil(Object tree);
693
    
694
    /** Duplicate single node, but not its children; single node dup. */
695
    public Object dupNode(Object t);
696
    
697
    /** This method returns whatever object represents the data at this node. For
698
     *  example, for CommonTree, it returns the token.  For your AST nodes,
699
     *  it could return the AST node.  The only requirement is that it have a
700
     *  toString() method and you can print it out.  This is used to print
701
     *  out lists of AST nodes (so that toString() is invoked on the node
702
     *  repeatedly).
703
     *
704
     *  Essentially toString() is used on the returned object.
705
     *
706
     *  Default is just toString() on whatever the node is.
707
     *
708
     *  Override if you are using your own ast nodes.
709
     */
710
    public Object getNodePayload(Object node);
711
    
712
    /** Return something analogous to the usual debug string for a parse tree
713
     *  such as: (+ 1 2).  Print it like a binary tree in LISP form.
714
     *  Return "nil" if the tree is a nil node.  Do not print any parens for a
715
     *  nil node.  The AST node type or token type is printed followed by
716
     *  the children.
717
     *
718
     *  Return "nil" if t==null
719
     */
720
    public String toString(Object t);
721
    
722
    /** Return a string for an entire tree not just a node */
723
    public String toString(Object t, String[] ruleNames);
724
    
725
    /** A more verbose AST toString.  Pass in a rule name vector for use with
726
     *  generated parsers.  I computed these as integers and then constructed
727
     *  a String vector, but a String[] is more efficient.  Null if you don't
728
     *  have a String[] to pass in.
729
     */
730
    public String toString(Object t, String[] ruleNames);
731
}
732
```
733

734
### Common Tree Adaptor
735

736
Standard tree adaptor implementation for CommonTree nodes.
737

738
```java { .api }
739
/**
740
 * Default tree adaptor implementation
741
 */
742
public class CommonTreeAdaptor extends BaseTreeAdaptor {
743
    /** Duplicate a single tree node.
744
     *  Override if you want another kind of node to be built.
745
     */
746
    public Object dupNode(Object t);
747
    
748
    public Object create(Token payload);
749
    
750
    /** Tell me how to create a token for use with imaginary token nodes.
751
     *  For example, there is probably no input symbol associated with decl
752
     *  node types.  This method is executed when you type create(type).
753
     */
754
    public Token createToken(int tokenType, String text);
755
    
756
    /** Tell me how to create a token for use with imaginary token nodes.
757
     *  For example, there is probably no input symbol associated with decl
758
     *  node types.  This method is executed when you type create int).
759
     */
760
    public Token createToken(Token fromToken);
761
    
762
    /** Track start/stop token for subtree root created for a rule.
763
     *  Only works with Tree nodes.  For rules that match nothing,
764
     *  seems like this will yield start=i and stop=i-1 in a nil node.
765
     *  Might be useful info so I'll not force to be i..i.
766
     */
767
    public void setTokenBoundaries(Object t, Token startToken, Token stopToken);
768
    
769
    public int getTokenStartIndex(Object t);
770
    
771
    public int getTokenStopIndex(Object t);
772
    
773
    public String getText(Object t);
774
    
775
    /** Tell the adaptor the type of the child token of root token t.
776
     *  Don't specify an invalid index i.
777
     */
778
    public void setType(Object t, int type);
779
    
780
    public int getType(Object t);
781
    
782
    /** For tree parsing, return the token object associated with node t.
783
     *  This is used mainly for error reporting.
784
     */
785
    public Token getToken(Object t);
786
    
787
    /** Where are token start/stop boundaries for subtree rooted at t?
788
     *  This is not a method in any interface; I think the parser calls
789
     *  this method during AST construction.  This method is also called
790
     *  when setting token boundaries manually such as with tree rewrite
791
     *  operations.
792
     */
793
    public void setChild(Object t, int i, Object child);
794
    
795
    public Object deleteChild(Object t, int i);
796
    
797
    /** Is the tree node t considered a nil node used to make lists
798
     *  of child nodes?
799
     */
800
    public boolean isNil(Object tree);
801
    
802
    /** For tree parsing, I need to know the token type of a node */
803
    public void setText(Object t, String text);
804
    
805
    /** For tree parsing, I need to know the token type of a node */
806
    public String getText(Object t);
807
    
808
    /** For tree parsing, I need to know the token type of a node */
809
    public void setType(Object t, int type);
810
    
811
    public int getType(Object t);
812
    
813
    /** For tree parsing, return the token object associated with node t.
814
     *  This is used mainly for error reporting.
815
     */
816
    public Token getToken(Object t);
817
    
818
    public String toString(Object t);
819
    
820
    public String toString(Object t, String[] ruleNames);
821
}
822
```
823

824
**Usage Examples:**
825

826
```java
827
import org.antlr.runtime.tree.*;
828
import org.antlr.runtime.*;
829

830
// Create tree adaptor
831
TreeAdaptor adaptor = new CommonTreeAdaptor();
832

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

838
// Build tree
839
adaptor.addChild(root, left);
840
adaptor.addChild(root, right);
841

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

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

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

854
// Create tree with token boundaries
855
Token startToken = new CommonToken(MyParser.IDENTIFIER, "x");
856
Token stopToken = new CommonToken(MyParser.NUMBER, "42"); 
857
adaptor.setTokenBoundaries(root, startToken, stopToken);
858
```
859

860
## Types
861

862
### Tree Node Types
863

864
```java { .api }
865
public class CommonErrorNode extends CommonTree {
866
    public IntStream input;
867
    public Token start;
868
    public Token stop;
869
    public RecognitionException trappedException;
870
    
871
    public CommonErrorNode(TokenStream input, Token start, Token stop, RecognitionException e);
872
    
873
    public boolean isNil();
874
    public int getType();
875
    public String getText();
876
    public String toString();
877
}
878

879
public class ParseTree extends BaseTree {
880
    public Object payload;
881
    public List<Token> hiddenTokens;
882
    
883
    public ParseTree(Object payload);
884
    
885
    public Tree dupNode();
886
    public int getType();
887
    public String getText();
888
    public int getTokenStartIndex();
889
    public int getTokenStopIndex();
890
    public String toString();
891
    public String toStringWithHiddenTokens();
892
    public String toInputString();
893
}
894
```
895

896
## Common Patterns
897

898
### Manual Tree Construction
899

900
```java
901
// Create tree manually: ^(PLUS ^(MULT x 2) y)
902
TreeAdaptor adaptor = new CommonTreeAdaptor();
903

904
Object plus = adaptor.create(PLUS, "+");
905
Object mult = adaptor.create(MULT, "*");
906
Object x = adaptor.create(IDENTIFIER, "x");
907
Object two = adaptor.create(NUMBER, "2");
908
Object y = adaptor.create(IDENTIFIER, "y");
909

910
// Build multiplication subtree
911
adaptor.addChild(mult, x);
912
adaptor.addChild(mult, two);
913

914
// Build addition tree
915
adaptor.addChild(plus, mult);
916
adaptor.addChild(plus, y);
917

918
System.out.println("Tree: " + adaptor.toString(plus));
919
```
920

921
### Tree Traversal
922

923
```java
924
public void walkTree(Object tree, TreeAdaptor adaptor) {
925
    if (tree == null) return;
926
    
927
    // Process current node
928
    System.out.println("Node: " + adaptor.getText(tree) + 
929
                      " Type: " + adaptor.getType(tree));
930
    
931
    // Visit all children
932
    int childCount = adaptor.getChildCount(tree);
933
    for (int i = 0; i < childCount; i++) {
934
        Object child = adaptor.getChild(tree, i);
935
        walkTree(child, adaptor);
936
    }
937
}
938
```
939

940
### Tree Copying
941

942
```java
943
public Object copyTree(Object tree, TreeAdaptor adaptor) {
944
    if (tree == null) return null;
945
    
946
    // Duplicate root node
947
    Object copy = adaptor.dupNode(tree);
948
    
949
    // Copy all children recursively
950
    int childCount = adaptor.getChildCount(tree);
951
    for (int i = 0; i < childCount; i++) {
952
        Object child = adaptor.getChild(tree, i);
953
        Object childCopy = copyTree(child, adaptor);
954
        adaptor.addChild(copy, childCopy);
955
    }
956
    
957
    return copy;
958
}
959
```
960

961
### Token Boundary Management
962

963
```java
964
// Set boundaries for manually constructed trees
965
Token startToken = /* first token */;
966
Token stopToken = /* last token */;
967

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

971
adaptor.setTokenBoundaries(tree, startToken, stopToken);
972

973
// Get boundaries later
974
int start = adaptor.getTokenStartIndex(tree);
975
int stop = adaptor.getTokenStopIndex(tree);
976
```
977

978
## Tree Utilities
979

980
### TreeWizard
981

982
Utility class for building and navigating trees using string patterns and queries.
983

984
```java { .api }
985
/**
986
 * Build and navigate trees with string patterns and queries
987
 */
988
public class TreeWizard {
989
    protected TreeAdaptor adaptor;
990
    protected Map<String, Integer> tokenNameToTypeMap;
991
    
992
    public interface ContextVisitor {
993
        public void visit(Object t, Object parent, int childIndex, Map<String, Object> labels);
994
    }
995
    
996
    public static abstract class Visitor implements ContextVisitor {
997
        public void visit(Object t, Object parent, int childIndex, Map<String, Object> labels);
998
        public abstract void visit(Object t);
999
    }
1000
    
1001
    public static class TreePattern extends CommonTree {
1002
        public String label;
1003
        public boolean hasTextArg;
1004
        public TreePattern(Token payload);
1005
    }
1006
    
1007
    public TreeWizard(TreeAdaptor adaptor);
1008
    public TreeWizard(TreeAdaptor adaptor, Map<String, Integer> tokenNameToTypeMap);
1009
    public TreeWizard(TreeAdaptor adaptor, String[] tokenNames);
1010
    public TreeWizard(String[] tokenNames);
1011
    
1012
    /** Compute a Map<String, Integer> that is an inverted index of
1013
     *  tokenNames (which maps int token types to names).
1014
     */
1015
    public Map<String, Integer> computeTokenTypes(String[] tokenNames);
1016
    
1017
    /** Using the map of token names to token types, return the type */
1018
    public int getTokenType(String tokenName);
1019
    
1020
    /** Walk entire tree and make a node name to nodes mapping.
1021
     *  For now, use recursion but later nonrecursive version may be
1022
     *  more efficient.  This method can be used to prep for a way to
1023
     *  search a tree.
1024
     */
1025
    public Map<Integer, List> index(Object t);
1026
    
1027
    /** Return a List of tree nodes with token type ttype */
1028
    public List find(Object t, int ttype);
1029
    
1030
    /** Return a List of subtrees matching pattern */
1031
    public List find(Object t, String pattern);
1032
    
1033
    public Object findFirst(Object t, int ttype);
1034
    public Object findFirst(Object t, String pattern);
1035
    
1036
    /** Visit every ttype node in t, invoking the visitor.  This is a quicker
1037
     *  version of the general visit(t, pattern) method.  The labels arg
1038
     *  of the visitor action method is never set (it's null) since using
1039
     *  a token type rather than a pattern doesn't let us set a label.
1040
     */
1041
    public void visit(Object t, int ttype, ContextVisitor visitor);
1042
    
1043
    /** For all subtrees that match the pattern, execute the visit action.
1044
     *  The implementation uses the root node of the pattern in combination
1045
     *  with visit(t, ttype, visitor) so nil-rooted patterns are not allowed.
1046
     *  Patterns with wildcard roots are also not allowed.
1047
     */
1048
    public void visit(Object t, String pattern, ContextVisitor visitor);
1049
    
1050
    /** Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels
1051
     *  on the various nodes and '.' (dot) as the node/subtree wildcard,
1052
     *  return true if the pattern matches and fill the labels Map with
1053
     *  the labels pointing at the appropriate nodes.  Return false if
1054
     *  the pattern is malformed or the tree does not match.
1055
     *
1056
     *  If a node specifies a text arg in pattern, that must match.
1057
     *  For example, (ASSIGN ID["x"] .) means the ID node must have
1058
     *  text "x" and structure (ASSIGN ID *).  The second ID means that
1059
     *  the ID must have the text "x".
1060
     *
1061
     *  TODO: what if we want to assign a node to a label?  If #foo is
1062
     *  always root node, then %foo is the node w/o making it the root.
1063
     *  This is like return label and input/output arg.
1064
     *
1065
     *  The general form is (#label:)? name[text]? ('(' child+ ')')?
1066
     *  where '.' is text and name is same as '.' except text.
1067
     */
1068
    public boolean parse(Object t, String pattern, Map<String, Object> labels);
1069
    public boolean parse(Object t, String pattern);
1070
    
1071
    /** Create a tree or node from the indicated tree pattern that has
1072
     *  token names and label references
1073
     */
1074
    public Object create(String pattern);
1075
    
1076
    /** Compare t1 and t2; return true if token types/text, structure match exactly.
1077
     *  The trees are examined in their entirety so that (A B) does not match
1078
     *  (A B C) nor (A (B C)). 
1079
     */
1080
    public boolean equals(Object t1, Object t2, TreeAdaptor adaptor);
1081
    public boolean equals(Object t1, Object t2);
1082
}
1083
```
1084

1085
### TreeVisitor
1086

1087
Utility for traversing trees with visitor pattern support.
1088

1089
```java { .api }
1090
/**
1091
 * Tree traversal with visitor pattern
1092
 */
1093
public class TreeVisitor {
1094
    protected TreeAdaptor adaptor;
1095
    
1096
    public TreeVisitor(TreeAdaptor adaptor);
1097
    public TreeVisitor();
1098
    
1099
    /** Visit every node in tree t and trigger an action for each node
1100
     *  before/after having visited all of its children.  Bottom up walk.
1101
     *  Execute an action for every node in the tree using a bottom/up walk.
1102
     *  Return same or modified tree structure.
1103
     *
1104
     *  It returns Object because the user may change the root and even
1105
     *  the tree type.  The invariant is that the return value is the new tree,
1106
     *  if any, that should take the place of this node.
1107
     *
1108
     *  Note that the child list is altered by this method as it does its
1109
     *  work.  Do not rely on the children list to be unmodified after this call.
1110
     *  Additionally, upon entry the current node's parent should be correct
1111
     *  in that this visitor may call setParent().  Make sure to call
1112
     *  freshenParentAndChildIndexes() before calling this method.
1113
     */
1114
    public Object visit(Object t, TreeVisitorAction action);
1115
}
1116
```
1117

1118
### TreeVisitorAction
1119

1120
Interface for tree visitor actions.
1121

1122
```java { .api }
1123
/**
1124
 * Interface for tree visitor actions
1125
 */
1126
public interface TreeVisitorAction {
1127
    /** Execute an action before visiting children of t.  Return t or
1128
     *  a rewritten t.  It is up to the visitor to decide what to do
1129
     *  with the return value.  Children of returned value will be
1130
     *  visited if using TreeVisitor.visit().
1131
     */
1132
    public Object pre(Object t);
1133
    
1134
    /** Execute an action after visiting children of t.  Return t or
1135
     *  a rewritten t.  It is up to the visitor to decide what to do
1136
     *  with the return value.
1137
     */
1138
    public Object post(Object t);
1139
}
1140
```
1141

1142
### TreeIterator
1143

1144
Iterator for traversing tree nodes in document order.
1145

1146
```java { .api }
1147
/**
1148
 * Iterator for tree traversal
1149
 */
1150
public class TreeIterator implements Iterator<Object> {
1151
    protected TreeAdaptor adaptor;
1152
    protected Object root;
1153
    protected Object tree;
1154
    protected boolean firstTime;
1155
    
1156
    public TreeIterator(CommonTree tree);
1157
    public TreeIterator(TreeAdaptor adaptor, Object tree);
1158
    
1159
    public void reset();
1160
    public boolean hasNext();
1161
    public Object next();
1162
    public void remove() throws UnsupportedOperationException;
1163
}
1164
```
1165

1166
**Tree Utility Usage Examples:**
1167

1168
```java
1169
import org.antlr.runtime.tree.*;
1170
import org.antlr.runtime.*;
1171

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

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

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

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

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

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

1200
// TreeVisitor examples
1201
TreeVisitor visitor = new TreeVisitor(adaptor);
1202

1203
// Visit tree with custom action
1204
Object newTree = visitor.visit(tree, new TreeVisitorAction() {
1205
    public Object pre(Object t) {
1206
        System.out.println("Entering: " + adaptor.getText(t));
1207
        return t; // Continue with original node
1208
    }
1209
    
1210
    public Object post(Object t) {
1211
        System.out.println("Leaving: " + adaptor.getText(t));
1212
        
1213
        // Example: replace all ID nodes with IDENTIFIER nodes
1214
        if (adaptor.getType(t) == MyParser.ID) {
1215
            Object newNode = adaptor.create(MyParser.IDENTIFIER, adaptor.getText(t));
1216
            return newNode;
1217
        }
1218
        return t;
1219
    }
1220
});
1221

1222
// TreeIterator examples
1223
TreeIterator iter = new TreeIterator(adaptor, tree);
1224
while (iter.hasNext()) {
1225
    Object node = iter.next();
1226
    System.out.println("Node: " + adaptor.getText(node));
1227
}
1228
```