001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2007 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.tree;
029:
030: import org.antlr.runtime.Token;
031:
032: import java.util.Map;
033: import java.util.HashMap;
034: import java.util.List;
035: import java.util.ArrayList;
036:
037: /** Build and navigate trees with this object. Must know about the names
038: * of tokens so you have to pass in a map or array of token names (from which
039: * this class can build the map). I.e., Token DECL means nothing unless the
040: * class can translate it to a token type.
041: *
042: * In order to create nodes and navigate, this class needs a TreeAdaptor.
043: *
044: * This class can build a token type -> node index for repeated use or for
045: * iterating over the various nodes with a particular type.
046: *
047: * This class works in conjunction with the TreeAdaptor rather than moving
048: * all this functionality into the adaptor. An adaptor helps build and
049: * navigate trees using methods. This class helps you do it with string
050: * patterns like "(A B C)". You can create a tree from that pattern or
051: * match subtrees against it.
052: */
053: public class TreeWizard {
054: protected TreeAdaptor adaptor;
055: protected Map tokenNameToTypeMap;
056:
057: public interface ContextVisitor {
058: // TODO: should this be called visit or something else?
059: public void visit(Object t, Object parent, int childIndex,
060: Map labels);
061: }
062:
063: public static abstract class Visitor implements ContextVisitor {
064: public void visit(Object t, Object parent, int childIndex,
065: Map labels) {
066: visit(t);
067: }
068:
069: public abstract void visit(Object t);
070: }
071:
072: /** When using %label:TOKENNAME in a tree for parse(), we must
073: * track the label.
074: */
075: public static class TreePattern extends CommonTree {
076: public String label;
077: public boolean hasTextArg;
078:
079: public TreePattern(Token payload) {
080: super (payload);
081: }
082:
083: public String toString() {
084: if (label != null) {
085: return "%" + label + ":" + super .toString();
086: } else {
087: return super .toString();
088: }
089: }
090: }
091:
092: public static class WildcardTreePattern extends TreePattern {
093: public WildcardTreePattern(Token payload) {
094: super (payload);
095: }
096: }
097:
098: /** This adaptor creates TreePattern objects for use during scan() */
099: public static class TreePatternTreeAdaptor extends
100: CommonTreeAdaptor {
101: public Object create(Token payload) {
102: return new TreePattern(payload);
103: }
104: }
105:
106: public TreeWizard(TreeAdaptor adaptor) {
107: this .adaptor = adaptor;
108: }
109:
110: public TreeWizard(TreeAdaptor adaptor, Map tokenNameToTypeMap) {
111: this .adaptor = adaptor;
112: this .tokenNameToTypeMap = tokenNameToTypeMap;
113: }
114:
115: public TreeWizard(TreeAdaptor adaptor, String[] tokenNames) {
116: this .adaptor = adaptor;
117: this .tokenNameToTypeMap = computeTokenTypes(tokenNames);
118: }
119:
120: public TreeWizard(String[] tokenNames) {
121: this (null, tokenNames);
122: }
123:
124: /** Compute a Map<String, Integer> that is an inverted index of
125: * tokenNames (which maps int token types to names).
126: */
127: public Map computeTokenTypes(String[] tokenNames) {
128: Map m = new HashMap();
129: for (int ttype = Token.MIN_TOKEN_TYPE; ttype < tokenNames.length; ttype++) {
130: String name = tokenNames[ttype];
131: m.put(name, new Integer(ttype));
132: }
133: return m;
134: }
135:
136: /** Using the map of token names to token types, return the type. */
137: public int getTokenType(String tokenName) {
138: if (tokenNameToTypeMap == null) {
139: return Token.INVALID_TOKEN_TYPE;
140: }
141: Integer ttypeI = (Integer) tokenNameToTypeMap.get(tokenName);
142: if (ttypeI != null) {
143: return ttypeI.intValue();
144: }
145: return Token.INVALID_TOKEN_TYPE;
146: }
147:
148: /** Walk the entire tree and make a node name to nodes mapping.
149: * For now, use recursion but later nonrecursive version may be
150: * more efficient. Returns Map<Integer, List> where the List is
151: * of your AST node type. The Integer is the token type of the node.
152: *
153: * TODO: save this index so that find and visit are faster
154: */
155: public Map index(Object t) {
156: Map m = new HashMap();
157: _index(t, m);
158: return m;
159: }
160:
161: /** Do the work for index */
162: protected void _index(Object t, Map m) {
163: if (t == null) {
164: return;
165: }
166: int ttype = adaptor.getType(t);
167: List elements = (List) m.get(ttype);
168: if (elements == null) {
169: elements = new ArrayList();
170: m.put(new Integer(ttype), elements);
171: }
172: elements.add(t);
173: int n = adaptor.getChildCount(t);
174: for (int i = 0; i < n; i++) {
175: Object child = adaptor.getChild(t, i);
176: _index(child, m);
177: }
178: }
179:
180: /** Return a List of tree nodes with token type ttype */
181: public List find(Object t, int ttype) {
182: final List nodes = new ArrayList();
183: visit(t, ttype, new TreeWizard.Visitor() {
184: public void visit(Object t) {
185: nodes.add(t);
186: }
187: });
188: return nodes;
189: }
190:
191: /** Return a List of subtrees matching pattern. */
192: public List find(Object t, String pattern) {
193: final List subtrees = new ArrayList();
194: // Create a TreePattern from the pattern
195: TreePatternLexer tokenizer = new TreePatternLexer(pattern);
196: TreePatternParser parser = new TreePatternParser(tokenizer,
197: this , new TreePatternTreeAdaptor());
198: final TreePattern tpattern = (TreePattern) parser.pattern();
199: // don't allow invalid patterns
200: if (tpattern == null || tpattern.isNil()
201: || tpattern.getClass() == WildcardTreePattern.class) {
202: return null;
203: }
204: int rootTokenType = tpattern.getType();
205: visit(t, rootTokenType, new TreeWizard.ContextVisitor() {
206: public void visit(Object t, Object parent, int childIndex,
207: Map labels) {
208: if (_parse(t, tpattern, null)) {
209: subtrees.add(t);
210: }
211: }
212: });
213: return subtrees;
214: }
215:
216: public Object findFirst(Object t, int ttype) {
217: return null;
218: }
219:
220: public Object findFirst(Object t, String pattern) {
221: return null;
222: }
223:
224: /** Visit every ttype node in t, invoking the visitor. This is a quicker
225: * version of the general visit(t, pattern) method. The labels arg
226: * of the visitor action method is never set (it's null) since using
227: * a token type rather than a pattern doesn't let us set a label.
228: */
229: public void visit(Object t, int ttype, ContextVisitor visitor) {
230: _visit(t, null, 0, ttype, visitor);
231: }
232:
233: /** Do the recursive work for visit */
234: protected void _visit(Object t, Object parent, int childIndex,
235: int ttype, ContextVisitor visitor) {
236: if (t == null) {
237: return;
238: }
239: if (adaptor.getType(t) == ttype) {
240: visitor.visit(t, parent, childIndex, null);
241: }
242: int n = adaptor.getChildCount(t);
243: for (int i = 0; i < n; i++) {
244: Object child = adaptor.getChild(t, i);
245: _visit(child, t, i, ttype, visitor);
246: }
247: }
248:
249: /** For all subtrees that match the pattern, execute the visit action.
250: * The implementation uses the root node of the pattern in combination
251: * with visit(t, ttype, visitor) so nil-rooted patterns are not allowed.
252: * Patterns with wildcard roots are also not allowed.
253: */
254: public void visit(Object t, final String pattern,
255: final ContextVisitor visitor) {
256: // Create a TreePattern from the pattern
257: TreePatternLexer tokenizer = new TreePatternLexer(pattern);
258: TreePatternParser parser = new TreePatternParser(tokenizer,
259: this , new TreePatternTreeAdaptor());
260: final TreePattern tpattern = (TreePattern) parser.pattern();
261: // don't allow invalid patterns
262: if (tpattern == null || tpattern.isNil()
263: || tpattern.getClass() == WildcardTreePattern.class) {
264: return;
265: }
266: final Map labels = new HashMap(); // reused for each _parse
267: int rootTokenType = tpattern.getType();
268: visit(t, rootTokenType, new TreeWizard.ContextVisitor() {
269: public void visit(Object t, Object parent, int childIndex,
270: Map unusedlabels) {
271: // the unusedlabels arg is null as visit on token type doesn't set.
272: labels.clear();
273: if (_parse(t, tpattern, labels)) {
274: visitor.visit(t, parent, childIndex, labels);
275: }
276: }
277: });
278: }
279:
280: /** Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels
281: * on the various nodes and '.' (dot) as the node/subtree wildcard,
282: * return true if the pattern matches and fill the labels Map with
283: * the labels pointing at the appropriate nodes. Return false if
284: * the pattern is malformed or the tree does not match.
285: *
286: * If a node specifies a text arg in pattern, then that must match
287: * for that node in t.
288: *
289: * TODO: what's a better way to indicate bad pattern? Exceptions are a hassle
290: */
291: public boolean parse(Object t, String pattern, Map labels) {
292: TreePatternLexer tokenizer = new TreePatternLexer(pattern);
293: TreePatternParser parser = new TreePatternParser(tokenizer,
294: this , new TreePatternTreeAdaptor());
295: TreePattern tpattern = (TreePattern) parser.pattern();
296: /*
297: System.out.println("t="+((Tree)t).toStringTree());
298: System.out.println("scant="+tpattern.toStringTree());
299: */
300: boolean matched = _parse(t, tpattern, labels);
301: return matched;
302: }
303:
304: public boolean parse(Object t, String pattern) {
305: return parse(t, pattern, null);
306: }
307:
308: /** Do the work for parse. Check to see if the t2 pattern fits the
309: * structure and token types in t1. Check text if the pattern has
310: * text arguments on nodes. Fill labels map with pointers to nodes
311: * in tree matched against nodes in pattern with labels.
312: */
313: protected boolean _parse(Object t1, TreePattern t2, Map labels) {
314: // make sure both are non-null
315: if (t1 == null || t2 == null) {
316: return false;
317: }
318: // check roots (wildcard matches anything)
319: if (t2.getClass() != WildcardTreePattern.class) {
320: if (adaptor.getType(t1) != t2.getType()) {
321: return false;
322: }
323: if (t2.hasTextArg
324: && !adaptor.getText(t1).equals(t2.getText())) {
325: return false;
326: }
327: }
328: if (t2.label != null && labels != null) {
329: // map label in pattern to node in t1
330: labels.put(t2.label, t1);
331: }
332: // check children
333: int n1 = adaptor.getChildCount(t1);
334: int n2 = t2.getChildCount();
335: if (n1 != n2) {
336: return false;
337: }
338: for (int i = 0; i < n1; i++) {
339: Object child1 = adaptor.getChild(t1, i);
340: TreePattern child2 = (TreePattern) t2.getChild(i);
341: if (!_parse(child1, child2, labels)) {
342: return false;
343: }
344: }
345: return true;
346: }
347:
348: /** Create a tree or node from the indicated tree pattern that closely
349: * follows ANTLR tree grammar tree element syntax:
350: *
351: * (root child1 ... child2).
352: *
353: * You can also just pass in a node: ID
354: *
355: * Any node can have a text argument: ID[foo]
356: * (notice there are no quotes around foo--it's clear it's a string).
357: *
358: * nil is a special name meaning "give me a nil node". Useful for
359: * making lists: (nil A B C) is a list of A B C.
360: */
361: public Object create(String pattern) {
362: TreePatternLexer tokenizer = new TreePatternLexer(pattern);
363: TreePatternParser parser = new TreePatternParser(tokenizer,
364: this , adaptor);
365: Object t = parser.pattern();
366: return t;
367: }
368:
369: /** Compare t1 and t2; return true if token types/text, structure match exactly.
370: * The trees are examined in their entirety so that (A B) does not match
371: * (A B C) nor (A (B C)).
372: // TODO: allow them to pass in a comparator
373: * TODO: have a version that is nonstatic so it can use instance adaptor
374: *
375: * I cannot rely on the tree node's equals() implementation as I make
376: * no constraints at all on the node types nor interface etc...
377: */
378: public static boolean equals(Object t1, Object t2,
379: TreeAdaptor adaptor) {
380: return _equals(t1, t2, adaptor);
381: }
382:
383: /** Compare type, structure, and text of two trees, assuming adaptor in
384: * this instance of a TreeWizard.
385: */
386: public boolean equals(Object t1, Object t2) {
387: return _equals(t1, t2, adaptor);
388: }
389:
390: protected static boolean _equals(Object t1, Object t2,
391: TreeAdaptor adaptor) {
392: // make sure both are non-null
393: if (t1 == null || t2 == null) {
394: return false;
395: }
396: // check roots
397: if (adaptor.getType(t1) != adaptor.getType(t2)) {
398: return false;
399: }
400: if (!adaptor.getText(t1).equals(adaptor.getText(t2))) {
401: return false;
402: }
403: // check children
404: int n1 = adaptor.getChildCount(t1);
405: int n2 = adaptor.getChildCount(t2);
406: if (n1 != n2) {
407: return false;
408: }
409: for (int i = 0; i < n1; i++) {
410: Object child1 = adaptor.getChild(t1, i);
411: Object child2 = adaptor.getChild(t2, i);
412: if (!_equals(child1, child2, adaptor)) {
413: return false;
414: }
415: }
416: return true;
417: }
418: }
|