13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.tree; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.Token; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.ArrayList; 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.HashMap; 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.List; 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.Map; 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** Build and navigate trees with this object. Must know about the names 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * of tokens so you have to pass in a map or array of token names (from which 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * this class can build the map). I.e., Token DECL means nothing unless the 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * class can translate it to a token type. 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * In order to create nodes and navigate, this class needs a TreeAdaptor. 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This class can build a token type -> node index for repeated use or for 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * iterating over the various nodes with a particular type. 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This class works in conjunction with the TreeAdaptor rather than moving 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * all this functionality into the adaptor. An adaptor helps build and 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * navigate trees using methods. This class helps you do it with string 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * patterns like "(A B C)". You can create a tree from that pattern or 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * match subtrees against it. 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class TreeWizard { 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected TreeAdaptor adaptor; 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Map tokenNameToTypeMap; 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public interface ContextVisitor { 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // TODO: should this be called visit or something else? 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, Object parent, int childIndex, Map labels); 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static abstract class Visitor implements ContextVisitor { 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, Object parent, int childIndex, Map labels) { 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visit(t); 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public abstract void visit(Object t); 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** When using %label:TOKENNAME in a tree for parse(), we must 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * track the label. 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static class TreePattern extends CommonTree { 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String label; 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean hasTextArg; 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreePattern(Token payload) { 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein super(payload); 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String toString() { 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( label!=null ) { 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return "%"+label+":"+super.toString(); 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else { 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return super.toString(); 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static class WildcardTreePattern extends TreePattern { 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public WildcardTreePattern(Token payload) { 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein super(payload); 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** This adaptor creates TreePattern objects for use during scan() */ 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static class TreePatternTreeAdaptor extends CommonTreeAdaptor { 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object create(Token payload) { 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return new TreePattern(payload); 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // TODO: build indexes for the wizard 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** During fillBuffer(), we can make a reverse index from a set 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * of token types of interest to the list of indexes into the 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * node stream. This lets us convert a node pointer to a 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * stream index semi-efficiently for a list of interesting 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * nodes such as function definition nodes (you'll want to seek 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * to their bodies for an interpreter). Also useful for doing 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * dynamic searches; i.e., go find me all PLUS nodes. 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Map tokenTypeToStreamIndexesMap; 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** If tokenTypesToReverseIndex set to INDEX_ALL then indexing 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * occurs for all token types. 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final Set INDEX_ALL = new HashSet(); 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** A set of token types user would like to index for faster lookup. 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If this is INDEX_ALL, then all token types are tracked. If null, 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * then none are indexed. 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Set tokenTypesToReverseIndex = null; 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeWizard(TreeAdaptor adaptor) { 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeWizard(TreeAdaptor adaptor, Map tokenNameToTypeMap) { 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 1283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.tokenNameToTypeMap = tokenNameToTypeMap; 1293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeWizard(TreeAdaptor adaptor, String[] tokenNames) { 1323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 1333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.tokenNameToTypeMap = computeTokenTypes(tokenNames); 1343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeWizard(String[] tokenNames) { 1373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this(new CommonTreeAdaptor(), tokenNames); 1383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Compute a Map<String, Integer> that is an inverted index of 1413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * tokenNames (which maps int token types to names). 1423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Map computeTokenTypes(String[] tokenNames) { 1443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Map m = new HashMap(); 1453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenNames==null ) { 1463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return m; 1473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int ttype = Token.MIN_TOKEN_TYPE; ttype < tokenNames.length; ttype++) { 1493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein String name = tokenNames[ttype]; 1503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein m.put(name, new Integer(ttype)); 1513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return m; 1533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Using the map of token names to token types, return the type. */ 1563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int getTokenType(String tokenName) { 1573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenNameToTypeMap==null ) { 1583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return Token.INVALID_TOKEN_TYPE; 1593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer ttypeI = (Integer)tokenNameToTypeMap.get(tokenName); 1613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( ttypeI!=null ) { 1623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return ttypeI.intValue(); 1633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return Token.INVALID_TOKEN_TYPE; 1653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Walk the entire tree and make a node name to nodes mapping. 1683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * For now, use recursion but later nonrecursive version may be 1693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * more efficient. Returns Map<Integer, List> where the List is 1703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * of your AST node type. The Integer is the token type of the node. 1713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 1723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * TODO: save this index so that find and visit are faster 1733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Map index(Object t) { 1753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Map m = new HashMap(); 1763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein _index(t, m); 1773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return m; 1783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Do the work for index */ 1813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected void _index(Object t, Map m) { 1823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( t==null ) { 1833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; 1843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int ttype = adaptor.getType(t); 1863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein List elements = (List)m.get(new Integer(ttype)); 1873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( elements==null ) { 1883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein elements = new ArrayList(); 1893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein m.put(new Integer(ttype), elements); 1903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein elements.add(t); 1923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = adaptor.getChildCount(t); 1933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<n; i++) { 1943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child = adaptor.getChild(t, i); 1953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein _index(child, m); 1963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Return a List of tree nodes with token type ttype */ 2003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public List find(Object t, int ttype) { 2013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein final List nodes = new ArrayList(); 2023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visit(t, ttype, new TreeWizard.Visitor() { 2033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t) { 2043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(t); 2053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein }); 2073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return nodes; 2083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Return a List of subtrees matching pattern. */ 2113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public List find(Object t, String pattern) { 2123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein final List subtrees = new ArrayList(); 2133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // Create a TreePattern from the pattern 2143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternLexer tokenizer = new TreePatternLexer(pattern); 2153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternParser parser = 2163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 2173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein final TreePattern tpattern = (TreePattern)parser.pattern(); 2183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // don't allow invalid patterns 2193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tpattern==null || 2203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tpattern.isNil() || 2213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tpattern.getClass()==WildcardTreePattern.class ) 2223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein { 2233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return null; 2243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int rootTokenType = tpattern.getType(); 2263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visit(t, rootTokenType, new TreeWizard.ContextVisitor() { 2273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, Object parent, int childIndex, Map labels) { 2283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( _parse(t, tpattern, null) ) { 2293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein subtrees.add(t); 2303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein }); 2333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return subtrees; 2343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object findFirst(Object t, int ttype) { 2373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return null; 2383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object findFirst(Object t, String pattern) { 2413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return null; 2423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Visit every ttype node in t, invoking the visitor. This is a quicker 2453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * version of the general visit(t, pattern) method. The labels arg 2463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * of the visitor action method is never set (it's null) since using 2473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * a token type rather than a pattern doesn't let us set a label. 2483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 2493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, int ttype, ContextVisitor visitor) { 2503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein _visit(t, null, 0, ttype, visitor); 2513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Do the recursive work for visit */ 2543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected void _visit(Object t, Object parent, int childIndex, int ttype, ContextVisitor visitor) { 2553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( t==null ) { 2563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; 2573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getType(t)==ttype ) { 2593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visitor.visit(t, parent, childIndex, null); 2603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = adaptor.getChildCount(t); 2623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<n; i++) { 2633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child = adaptor.getChild(t, i); 2643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein _visit(child, t, i, ttype, visitor); 2653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** For all subtrees that match the pattern, execute the visit action. 2693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * The implementation uses the root node of the pattern in combination 2703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * with visit(t, ttype, visitor) so nil-rooted patterns are not allowed. 2713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Patterns with wildcard roots are also not allowed. 2723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 2733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, final String pattern, final ContextVisitor visitor) { 2743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // Create a TreePattern from the pattern 2753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternLexer tokenizer = new TreePatternLexer(pattern); 2763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternParser parser = 2773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 2783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein final TreePattern tpattern = (TreePattern)parser.pattern(); 2793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // don't allow invalid patterns 2803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tpattern==null || 2813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tpattern.isNil() || 2823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tpattern.getClass()==WildcardTreePattern.class ) 2833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein { 2843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; 2853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein final Map labels = new HashMap(); // reused for each _parse 2873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int rootTokenType = tpattern.getType(); 2883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visit(t, rootTokenType, new TreeWizard.ContextVisitor() { 2893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void visit(Object t, Object parent, int childIndex, Map unusedlabels) { 2903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // the unusedlabels arg is null as visit on token type doesn't set. 2913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein labels.clear(); 2923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( _parse(t, tpattern, labels) ) { 2933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein visitor.visit(t, parent, childIndex, labels); 2943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein }); 2973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels 3003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * on the various nodes and '.' (dot) as the node/subtree wildcard, 3013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * return true if the pattern matches and fill the labels Map with 3023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * the labels pointing at the appropriate nodes. Return false if 3033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * the pattern is malformed or the tree does not match. 3043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If a node specifies a text arg in pattern, then that must match 3063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * for that node in t. 3073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * TODO: what's a better way to indicate bad pattern? Exceptions are a hassle 3093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 3103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean parse(Object t, String pattern, Map labels) { 3113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternLexer tokenizer = new TreePatternLexer(pattern); 3123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternParser parser = 3133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 3143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePattern tpattern = (TreePattern)parser.pattern(); 3153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /* 3163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.out.println("t="+((Tree)t).toStringTree()); 3173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.out.println("scant="+tpattern.toStringTree()); 3183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 3193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein boolean matched = _parse(t, tpattern, labels); 3203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return matched; 3213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean parse(Object t, String pattern) { 3243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return parse(t, pattern, null); 3253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Do the work for parse. Check to see if the t2 pattern fits the 3283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * structure and token types in t1. Check text if the pattern has 3293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * text arguments on nodes. Fill labels map with pointers to nodes 3303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * in tree matched against nodes in pattern with labels. 3313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 3323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected boolean _parse(Object t1, TreePattern tpattern, Map labels) { 3333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // make sure both are non-null 3343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( t1==null || tpattern==null ) { 3353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 3363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // check roots (wildcard matches anything) 3383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tpattern.getClass() != WildcardTreePattern.class ) { 3393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getType(t1) != tpattern.getType() ) return false; 3403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // if pattern has text, check node text 3413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tpattern.hasTextArg && !adaptor.getText(t1).equals(tpattern.getText()) ) { 3423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 3433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tpattern.label!=null && labels!=null ) { 3463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // map label in pattern to node in t1 3473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein labels.put(tpattern.label, t1); 3483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // check children 3503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n1 = adaptor.getChildCount(t1); 3513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n2 = tpattern.getChildCount(); 3523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( n1 != n2 ) { 3533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 3543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<n1; i++) { 3563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child1 = adaptor.getChild(t1, i); 3573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePattern child2 = (TreePattern)tpattern.getChild(i); 3583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( !_parse(child1, child2, labels) ) { 3593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 3603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return true; 3633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Create a tree or node from the indicated tree pattern that closely 3663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * follows ANTLR tree grammar tree element syntax: 3673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * (root child1 ... child2). 3693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * You can also just pass in a node: ID 3713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Any node can have a text argument: ID[foo] 3733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * (notice there are no quotes around foo--it's clear it's a string). 3743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * nil is a special name meaning "give me a nil node". Useful for 3763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * making lists: (nil A B C) is a list of A B C. 3773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 3783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object create(String pattern) { 3793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternLexer tokenizer = new TreePatternLexer(pattern); 3803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreePatternParser parser = new TreePatternParser(tokenizer, this, adaptor); 3813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object t = parser.pattern(); 3823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return t; 3833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Compare t1 and t2; return true if token types/text, structure match exactly. 3863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * The trees are examined in their entirety so that (A B) does not match 3873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * (A B C) nor (A (B C)). 3883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // TODO: allow them to pass in a comparator 3893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * TODO: have a version that is nonstatic so it can use instance adaptor 3903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 3913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * I cannot rely on the tree node's equals() implementation as I make 3923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * no constraints at all on the node types nor interface etc... 3933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 3943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static boolean equals(Object t1, Object t2, TreeAdaptor adaptor) { 3953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return _equals(t1, t2, adaptor); 3963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Compare type, structure, and text of two trees, assuming adaptor in 3993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * this instance of a TreeWizard. 4003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 4013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean equals(Object t1, Object t2) { 4023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return _equals(t1, t2, adaptor); 4033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 4053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected static boolean _equals(Object t1, Object t2, TreeAdaptor adaptor) { 4063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // make sure both are non-null 4073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( t1==null || t2==null ) { 4083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 4093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // check roots 4113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getType(t1) != adaptor.getType(t2) ) { 4123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 4133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( !adaptor.getText(t1).equals(adaptor.getText(t2)) ) { 4153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 4163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // check children 4183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n1 = adaptor.getChildCount(t1); 4193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n2 = adaptor.getChildCount(t2); 4203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( n1 != n2 ) { 4213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 4223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<n1; i++) { 4243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child1 = adaptor.getChild(t1, i); 4253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child2 = adaptor.getChild(t2, i); 4263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( !_equals(child1, child2, adaptor) ) { 4273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 4283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return true; 4313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 4333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // TODO: next stuff taken from CommonTreeNodeStream 4343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 4353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Given a node, add this to the reverse index tokenTypeToStreamIndexesMap. 4363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * You can override this method to alter how indexing occurs. The 4373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * default is to create a 4383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Map<Integer token type,ArrayList<Integer stream index>> 4403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This data structure allows you to find all nodes with type INT in order. 4423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If you really need to find a node of type, say, FUNC quickly then perhaps 4443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Map<Integertoken type,Map<Object tree node,Integer stream index>> 4463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * would be better for you. The interior maps map a tree node to 4483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * the index so you don't have to search linearly for a specific node. 4493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 4503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If you change this method, you will likely need to change 4513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * getNodeIndex(), which extracts information. 4523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected void fillReverseIndex(Object node, int streamIndex) { 4533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.println("revIndex "+node+"@"+streamIndex); 4543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenTypesToReverseIndex==null ) { 4553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; // no indexing if this is empty (nothing of interest) 4563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenTypeToStreamIndexesMap==null ) { 4583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypeToStreamIndexesMap = new HashMap(); // first indexing op 4593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int tokenType = adaptor.getType(node); 4613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer tokenTypeI = new Integer(tokenType); 4623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( !(tokenTypesToReverseIndex==INDEX_ALL || 4633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypesToReverseIndex.contains(tokenTypeI)) ) 4643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein { 4653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; // tokenType not of interest 4663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer streamIndexI = new Integer(streamIndex); 4683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein ArrayList indexes = (ArrayList)tokenTypeToStreamIndexesMap.get(tokenTypeI); 4693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( indexes==null ) { 4703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein indexes = new ArrayList(); // no list yet for this token type 4713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein indexes.add(streamIndexI); // not there yet, add 4723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypeToStreamIndexesMap.put(tokenTypeI, indexes); 4733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else { 4753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( !indexes.contains(streamIndexI) ) { 4763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein indexes.add(streamIndexI); // not there yet, add 4773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 4813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Track the indicated token type in the reverse index. Call this 4823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * repeatedly for each type or use variant with Set argument to 4833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * set all at once. 4843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * @param tokenType 4853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void reverseIndex(int tokenType) { 4863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenTypesToReverseIndex==null ) { 4873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypesToReverseIndex = new HashSet(); 4883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else if ( tokenTypesToReverseIndex==INDEX_ALL ) { 4903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; 4913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypesToReverseIndex.add(new Integer(tokenType)); 4933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 4943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 4953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Track the indicated token types in the reverse index. Set 4963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * to INDEX_ALL to track all token types. 4973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void reverseIndex(Set tokenTypes) { 4983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tokenTypesToReverseIndex = tokenTypes; 4993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 5013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Given a node pointer, return its index into the node stream. 5023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This is not its Token stream index. If there is no reverse map 5033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * from node to stream index or the map does not contain entries 5043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * for node's token type, a linear search of entire stream is used. 5053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 5063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Return -1 if exact node pointer not in stream. 5073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int getNodeIndex(Object node) { 5083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.println("get "+node); 5093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenTypeToStreamIndexesMap==null ) { 5103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return getNodeIndexLinearly(node); 5113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int tokenType = adaptor.getType(node); 5133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer tokenTypeI = new Integer(tokenType); 5143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein ArrayList indexes = (ArrayList)tokenTypeToStreamIndexesMap.get(tokenTypeI); 5153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( indexes==null ) { 5163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node)); 5173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return getNodeIndexLinearly(node); 5183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = 0; i < indexes.size(); i++) { 5203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer streamIndexI = (Integer)indexes.get(i); 5213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object n = get(streamIndexI.intValue()); 5223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( n==node ) { 5233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.println("found in index; stream index = "+streamIndexI); 5243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return streamIndexI.intValue(); // found it! 5253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return -1; 5283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 5293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 5303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 5313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 532