01: package antlr;
02:
03: /* ANTLR Translator Generator
04: * Project led by Terence Parr at http://www.cs.usfca.edu
05: * Software rights: http://www.antlr.org/license.html
06: */
07:
08: import antlr.collections.AST;
09:
10: public class ASTIterator {
11: protected AST cursor = null;
12: protected AST original = null;
13:
14: public ASTIterator(AST t) {
15: original = cursor = t;
16: }
17:
18: /** Is 'sub' a subtree of 't' beginning at the root? */
19: public boolean isSubtree(AST t, AST sub) {
20: AST sibling;
21:
22: // the empty tree is always a subset of any tree.
23: if (sub == null) {
24: return true;
25: }
26:
27: // if the tree is empty, return true if the subtree template is too.
28: if (t == null) {
29: if (sub != null)
30: return false;
31: return true;
32: }
33:
34: // Otherwise, start walking sibling lists. First mismatch, return false.
35: for (sibling = t; sibling != null && sub != null; sibling = sibling
36: .getNextSibling(), sub = sub.getNextSibling()) {
37: // as a quick optimization, check roots first.
38: if (sibling.getType() != sub.getType())
39: return false;
40: // if roots match, do full match test on children.
41: if (sibling.getFirstChild() != null) {
42: if (!isSubtree(sibling.getFirstChild(), sub
43: .getFirstChild()))
44: return false;
45: }
46: }
47: return true;
48: }
49:
50: /** Find the next subtree with structure and token types equal to
51: * those of 'template'.
52: */
53: public AST next(AST template) {
54: AST t = null;
55: AST sibling = null;
56:
57: if (cursor == null) { // do nothing if no tree to work on
58: return null;
59: }
60:
61: // Start walking sibling list looking for subtree matches.
62: for (; cursor != null; cursor = cursor.getNextSibling()) {
63: // as a quick optimization, check roots first.
64: if (cursor.getType() == template.getType()) {
65: // if roots match, do full match test on children.
66: if (cursor.getFirstChild() != null) {
67: if (isSubtree(cursor.getFirstChild(), template
68: .getFirstChild())) {
69: return cursor;
70: }
71: }
72: }
73: }
74: return t;
75: }
76: }
|