| /* |
| * [The "BSD licence"] |
| * Copyright (c) 2005-2008 Terence Parr |
| * All rights reserved. |
| * |
| * Conversion to C#: |
| * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| // TODO: build indexes for wizard |
| //#define BUILD_INDEXES |
| |
| namespace Antlr.Runtime.Tree { |
| using System.Collections.Generic; |
| |
| using IList = System.Collections.IList; |
| #if BUILD_INDEXES |
| using IDictionary = System.Collections.IDictionary; |
| #endif |
| |
| /** <summary> |
| * Build and navigate trees with this object. Must know about the names |
| * of tokens so you have to pass in a map or array of token names (from which |
| * this class can build the map). I.e., Token DECL means nothing unless the |
| * class can translate it to a token type. |
| * </summary> |
| * |
| * <remarks> |
| * In order to create nodes and navigate, this class needs a TreeAdaptor. |
| * |
| * This class can build a token type -> node index for repeated use or for |
| * iterating over the various nodes with a particular type. |
| * |
| * This class works in conjunction with the TreeAdaptor rather than moving |
| * all this functionality into the adaptor. An adaptor helps build and |
| * navigate trees using methods. This class helps you do it with string |
| * patterns like "(A B C)". You can create a tree from that pattern or |
| * match subtrees against it. |
| * </remarks> |
| */ |
| public class TreeWizard { |
| protected ITreeAdaptor adaptor; |
| protected IDictionary<string, int> tokenNameToTypeMap; |
| |
| public interface IContextVisitor { |
| // TODO: should this be called visit or something else? |
| void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels); |
| } |
| |
| public abstract class Visitor : IContextVisitor { |
| public virtual void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels) { |
| Visit(t); |
| } |
| public abstract void Visit(object t); |
| } |
| |
| class ActionVisitor : Visitor { |
| System.Action<object> _action; |
| |
| public ActionVisitor(System.Action<object> action) { |
| _action = action; |
| } |
| |
| public override void Visit(object t) { |
| _action(t); |
| } |
| } |
| |
| /** <summary> |
| * When using %label:TOKENNAME in a tree for parse(), we must |
| * track the label. |
| * </summary> |
| */ |
| public class TreePattern : CommonTree { |
| public string label; |
| public bool hasTextArg; |
| public TreePattern(IToken payload) : |
| base(payload) { |
| } |
| public override string ToString() { |
| if (label != null) { |
| return "%" + label + ":"; //+ base.ToString(); |
| } else { |
| return base.ToString(); |
| } |
| } |
| } |
| |
| public class WildcardTreePattern : TreePattern { |
| public WildcardTreePattern(IToken payload) : |
| base(payload) { |
| } |
| } |
| |
| /** <summary>This adaptor creates TreePattern objects for use during scan()</summary> */ |
| public class TreePatternTreeAdaptor : CommonTreeAdaptor { |
| public override object Create(IToken payload) { |
| return new TreePattern(payload); |
| } |
| } |
| |
| #if BUILD_INDEXES |
| // TODO: build indexes for the wizard |
| |
| /** <summary> |
| * During fillBuffer(), we can make a reverse index from a set |
| * of token types of interest to the list of indexes into the |
| * node stream. This lets us convert a node pointer to a |
| * stream index semi-efficiently for a list of interesting |
| * nodes such as function definition nodes (you'll want to seek |
| * to their bodies for an interpreter). Also useful for doing |
| * dynamic searches; i.e., go find me all PLUS nodes. |
| * </summary> |
| */ |
| protected IDictionary<int, IList<int>> tokenTypeToStreamIndexesMap; |
| |
| /** <summary> |
| * If tokenTypesToReverseIndex set to INDEX_ALL then indexing |
| * occurs for all token types. |
| * </summary> |
| */ |
| public static readonly HashSet<int> INDEX_ALL = new HashSet<int>(); |
| |
| /** <summary> |
| * A set of token types user would like to index for faster lookup. |
| * If this is INDEX_ALL, then all token types are tracked. If null, |
| * then none are indexed. |
| * </summary> |
| */ |
| protected HashSet<int> tokenTypesToReverseIndex = null; |
| #endif |
| |
| public TreeWizard(ITreeAdaptor adaptor) { |
| this.adaptor = adaptor; |
| } |
| |
| public TreeWizard(ITreeAdaptor adaptor, IDictionary<string, int> tokenNameToTypeMap) { |
| this.adaptor = adaptor; |
| this.tokenNameToTypeMap = tokenNameToTypeMap; |
| } |
| |
| public TreeWizard(ITreeAdaptor adaptor, string[] tokenNames) { |
| this.adaptor = adaptor; |
| this.tokenNameToTypeMap = ComputeTokenTypes(tokenNames); |
| } |
| |
| public TreeWizard(string[] tokenNames) : |
| this(null, tokenNames) { |
| } |
| |
| /** <summary> |
| * Compute a Map<String, Integer> that is an inverted index of |
| * tokenNames (which maps int token types to names). |
| * </summary> |
| */ |
| public virtual IDictionary<string, int> ComputeTokenTypes(string[] tokenNames) { |
| IDictionary<string, int> m = new Dictionary<string, int>(); |
| if (tokenNames == null) { |
| return m; |
| } |
| for (int ttype = TokenTypes.Min; ttype < tokenNames.Length; ttype++) { |
| string name = tokenNames[ttype]; |
| m[name] = ttype; |
| } |
| return m; |
| } |
| |
| /** <summary>Using the map of token names to token types, return the type.</summary> */ |
| public virtual int GetTokenType(string tokenName) { |
| if (tokenNameToTypeMap == null) { |
| return TokenTypes.Invalid; |
| } |
| |
| int value; |
| if (tokenNameToTypeMap.TryGetValue(tokenName, out value)) |
| return value; |
| |
| return TokenTypes.Invalid; |
| } |
| |
| /** <summary> |
| * Walk the entire tree and make a node name to nodes mapping. |
| * For now, use recursion but later nonrecursive version may be |
| * more efficient. Returns Map<Integer, List> where the List is |
| * of your AST node type. The Integer is the token type of the node. |
| * </summary> |
| * |
| * <remarks> |
| * TODO: save this index so that find and visit are faster |
| * </remarks> |
| */ |
| public IDictionary<int, IList> Index(object t) { |
| IDictionary<int, IList> m = new Dictionary<int, IList>(); |
| IndexCore(t, m); |
| return m; |
| } |
| |
| /** <summary>Do the work for index</summary> */ |
| protected virtual void IndexCore(object t, IDictionary<int, IList> m) { |
| if (t == null) { |
| return; |
| } |
| int ttype = adaptor.GetType(t); |
| IList elements; |
| if (!m.TryGetValue(ttype, out elements) || elements == null) { |
| elements = new List<object>(); |
| m[ttype] = elements; |
| } |
| elements.Add(t); |
| int n = adaptor.GetChildCount(t); |
| for (int i = 0; i < n; i++) { |
| object child = adaptor.GetChild(t, i); |
| IndexCore(child, m); |
| } |
| } |
| |
| class FindTreeWizardVisitor : TreeWizard.Visitor { |
| IList _nodes; |
| public FindTreeWizardVisitor(IList nodes) { |
| _nodes = nodes; |
| } |
| public override void Visit(object t) { |
| _nodes.Add(t); |
| } |
| } |
| class FindTreeWizardContextVisitor : TreeWizard.IContextVisitor { |
| TreeWizard _outer; |
| TreePattern _tpattern; |
| IList _subtrees; |
| public FindTreeWizardContextVisitor(TreeWizard outer, TreePattern tpattern, IList subtrees) { |
| _outer = outer; |
| _tpattern = tpattern; |
| _subtrees = subtrees; |
| } |
| |
| public void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels) { |
| if (_outer.ParseCore(t, _tpattern, null)) { |
| _subtrees.Add(t); |
| } |
| } |
| } |
| |
| /** <summary>Return a List of tree nodes with token type ttype</summary> */ |
| public virtual IList Find(object t, int ttype) { |
| IList nodes = new List<object>(); |
| Visit(t, ttype, new FindTreeWizardVisitor(nodes)); |
| return nodes; |
| } |
| |
| /** <summary>Return a List of subtrees matching pattern.</summary> */ |
| public virtual IList Find(object t, string pattern) { |
| IList subtrees = new List<object>(); |
| // Create a TreePattern from the pattern |
| TreePatternLexer tokenizer = new TreePatternLexer(pattern); |
| TreePatternParser parser = |
| new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); |
| TreePattern tpattern = (TreePattern)parser.Pattern(); |
| // don't allow invalid patterns |
| if (tpattern == null || |
| tpattern.IsNil || |
| tpattern.GetType() == typeof(WildcardTreePattern)) { |
| return null; |
| } |
| int rootTokenType = tpattern.Type; |
| Visit(t, rootTokenType, new FindTreeWizardContextVisitor(this, tpattern, subtrees)); |
| return subtrees; |
| } |
| |
| public virtual object FindFirst(object t, int ttype) { |
| return null; |
| } |
| |
| public virtual object FindFirst(object t, string pattern) { |
| return null; |
| } |
| |
| /** <summary> |
| * Visit every ttype node in t, invoking the visitor. This is a quicker |
| * version of the general visit(t, pattern) method. The labels arg |
| * of the visitor action method is never set (it's null) since using |
| * a token type rather than a pattern doesn't let us set a label. |
| * </summary> |
| */ |
| public void Visit(object t, int ttype, IContextVisitor visitor) { |
| VisitCore(t, null, 0, ttype, visitor); |
| } |
| |
| public void Visit(object t, int ttype, System.Action<object> action) { |
| Visit(t, ttype, new ActionVisitor(action)); |
| } |
| |
| /** <summary>Do the recursive work for visit</summary> */ |
| protected virtual void VisitCore(object t, object parent, int childIndex, int ttype, IContextVisitor visitor) { |
| if (t == null) { |
| return; |
| } |
| if (adaptor.GetType(t) == ttype) { |
| visitor.Visit(t, parent, childIndex, null); |
| } |
| int n = adaptor.GetChildCount(t); |
| for (int i = 0; i < n; i++) { |
| object child = adaptor.GetChild(t, i); |
| VisitCore(child, t, i, ttype, visitor); |
| } |
| } |
| |
| class VisitTreeWizardContextVisitor : TreeWizard.IContextVisitor { |
| TreeWizard _outer; |
| IContextVisitor _visitor; |
| IDictionary<string, object> _labels; |
| TreePattern _tpattern; |
| |
| public VisitTreeWizardContextVisitor(TreeWizard outer, IContextVisitor visitor, IDictionary<string, object> labels, TreePattern tpattern) { |
| _outer = outer; |
| _visitor = visitor; |
| _labels = labels; |
| _tpattern = tpattern; |
| } |
| |
| public void Visit(object t, object parent, int childIndex, IDictionary<string, object> unusedlabels) { |
| // the unusedlabels arg is null as visit on token type doesn't set. |
| _labels.Clear(); |
| if (_outer.ParseCore(t, _tpattern, _labels)) { |
| _visitor.Visit(t, parent, childIndex, _labels); |
| } |
| } |
| } |
| |
| /** <summary> |
| * For all subtrees that match the pattern, execute the visit action. |
| * The implementation uses the root node of the pattern in combination |
| * with visit(t, ttype, visitor) so nil-rooted patterns are not allowed. |
| * Patterns with wildcard roots are also not allowed. |
| * </summary> |
| */ |
| public void Visit(object t, string pattern, IContextVisitor visitor) { |
| // Create a TreePattern from the pattern |
| TreePatternLexer tokenizer = new TreePatternLexer(pattern); |
| TreePatternParser parser = |
| new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); |
| TreePattern tpattern = (TreePattern)parser.Pattern(); |
| // don't allow invalid patterns |
| if (tpattern == null || |
| tpattern.IsNil || |
| tpattern.GetType() == typeof(WildcardTreePattern)) { |
| return; |
| } |
| IDictionary<string, object> labels = new Dictionary<string, object>(); // reused for each _parse |
| int rootTokenType = tpattern.Type; |
| Visit(t, rootTokenType, new VisitTreeWizardContextVisitor(this, visitor, labels, tpattern)); |
| } |
| |
| /** <summary> |
| * Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels |
| * on the various nodes and '.' (dot) as the node/subtree wildcard, |
| * return true if the pattern matches and fill the labels Map with |
| * the labels pointing at the appropriate nodes. Return false if |
| * the pattern is malformed or the tree does not match. |
| * </summary> |
| * |
| * <remarks> |
| * If a node specifies a text arg in pattern, then that must match |
| * for that node in t. |
| * |
| * TODO: what's a better way to indicate bad pattern? Exceptions are a hassle |
| * </remarks> |
| */ |
| public bool Parse(object t, string pattern, IDictionary<string, object> labels) { |
| TreePatternLexer tokenizer = new TreePatternLexer(pattern); |
| TreePatternParser parser = |
| new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); |
| TreePattern tpattern = (TreePattern)parser.Pattern(); |
| /* |
| System.out.println("t="+((Tree)t).toStringTree()); |
| System.out.println("scant="+tpattern.toStringTree()); |
| */ |
| bool matched = ParseCore(t, tpattern, labels); |
| return matched; |
| } |
| |
| public bool Parse(object t, string pattern) { |
| return Parse(t, pattern, null); |
| } |
| |
| /** <summary> |
| * Do the work for parse. Check to see if the t2 pattern fits the |
| * structure and token types in t1. Check text if the pattern has |
| * text arguments on nodes. Fill labels map with pointers to nodes |
| * in tree matched against nodes in pattern with labels. |
| * </summary> |
| */ |
| protected virtual bool ParseCore(object t1, TreePattern tpattern, IDictionary<string, object> labels) { |
| // make sure both are non-null |
| if (t1 == null || tpattern == null) { |
| return false; |
| } |
| // check roots (wildcard matches anything) |
| if (tpattern.GetType() != typeof(WildcardTreePattern)) { |
| if (adaptor.GetType(t1) != tpattern.Type) { |
| return false; |
| } |
| // if pattern has text, check node text |
| if (tpattern.hasTextArg && !adaptor.GetText(t1).Equals(tpattern.Text)) { |
| return false; |
| } |
| } |
| if (tpattern.label != null && labels != null) { |
| // map label in pattern to node in t1 |
| labels[tpattern.label] = t1; |
| } |
| // check children |
| int n1 = adaptor.GetChildCount(t1); |
| int n2 = tpattern.ChildCount; |
| if (n1 != n2) { |
| return false; |
| } |
| for (int i = 0; i < n1; i++) { |
| object child1 = adaptor.GetChild(t1, i); |
| TreePattern child2 = (TreePattern)tpattern.GetChild(i); |
| if (!ParseCore(child1, child2, labels)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** <summary> |
| * Create a tree or node from the indicated tree pattern that closely |
| * follows ANTLR tree grammar tree element syntax: |
| * |
| * (root child1 ... child2). |
| * </summary> |
| * |
| * <remarks> |
| * You can also just pass in a node: ID |
| * |
| * Any node can have a text argument: ID[foo] |
| * (notice there are no quotes around foo--it's clear it's a string). |
| * |
| * nil is a special name meaning "give me a nil node". Useful for |
| * making lists: (nil A B C) is a list of A B C. |
| * </remarks> |
| */ |
| public virtual object Create(string pattern) { |
| TreePatternLexer tokenizer = new TreePatternLexer(pattern); |
| TreePatternParser parser = new TreePatternParser(tokenizer, this, adaptor); |
| object t = parser.Pattern(); |
| return t; |
| } |
| |
| /** <summary> |
| * Compare t1 and t2; return true if token types/text, structure match exactly. |
| * The trees are examined in their entirety so that (A B) does not match |
| * (A B C) nor (A (B C)). |
| * </summary> |
| * |
| * <remarks> |
| * TODO: allow them to pass in a comparator |
| * TODO: have a version that is nonstatic so it can use instance adaptor |
| * |
| * I cannot rely on the tree node's equals() implementation as I make |
| * no constraints at all on the node types nor interface etc... |
| * </remarks> |
| */ |
| public static bool Equals(object t1, object t2, ITreeAdaptor adaptor) { |
| return EqualsCore(t1, t2, adaptor); |
| } |
| |
| /** <summary> |
| * Compare type, structure, and text of two trees, assuming adaptor in |
| * this instance of a TreeWizard. |
| * </summary> |
| */ |
| public new bool Equals(object t1, object t2) { |
| return EqualsCore(t1, t2, adaptor); |
| } |
| |
| protected static bool EqualsCore(object t1, object t2, ITreeAdaptor adaptor) { |
| // make sure both are non-null |
| if (t1 == null || t2 == null) { |
| return false; |
| } |
| // check roots |
| if (adaptor.GetType(t1) != adaptor.GetType(t2)) { |
| return false; |
| } |
| if (!adaptor.GetText(t1).Equals(adaptor.GetText(t2))) { |
| return false; |
| } |
| // check children |
| int n1 = adaptor.GetChildCount(t1); |
| int n2 = adaptor.GetChildCount(t2); |
| if (n1 != n2) { |
| return false; |
| } |
| for (int i = 0; i < n1; i++) { |
| object child1 = adaptor.GetChild(t1, i); |
| object child2 = adaptor.GetChild(t2, i); |
| if (!EqualsCore(child1, child2, adaptor)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| #if BUILD_INDEXES |
| // TODO: next stuff taken from CommonTreeNodeStream |
| |
| /** <summary> |
| * Given a node, add this to the reverse index tokenTypeToStreamIndexesMap. |
| * You can override this method to alter how indexing occurs. The |
| * default is to create a |
| * |
| * Map<Integer token type,ArrayList<Integer stream index>> |
| * </summary> |
| * |
| * <remarks> |
| * This data structure allows you to find all nodes with type INT in order. |
| * |
| * If you really need to find a node of type, say, FUNC quickly then perhaps |
| * |
| * Map<Integertoken type,Map<Object tree node,Integer stream index>> |
| * |
| * would be better for you. The interior maps map a tree node to |
| * the index so you don't have to search linearly for a specific node. |
| * |
| * If you change this method, you will likely need to change |
| * getNodeIndex(), which extracts information. |
| * </remarks> |
| */ |
| protected void fillReverseIndex( object node, int streamIndex ) |
| { |
| //System.out.println("revIndex "+node+"@"+streamIndex); |
| if ( tokenTypesToReverseIndex == null ) |
| { |
| return; // no indexing if this is empty (nothing of interest) |
| } |
| if ( tokenTypeToStreamIndexesMap == null ) |
| { |
| tokenTypeToStreamIndexesMap = new Dictionary<int, IList<int>>(); // first indexing op |
| } |
| int tokenType = adaptor.getType( node ); |
| if ( !( tokenTypesToReverseIndex == INDEX_ALL || |
| tokenTypesToReverseIndex.Contains( tokenType ) ) ) |
| { |
| return; // tokenType not of interest |
| } |
| IList<int> indexes; |
| |
| if ( !tokenTypeToStreamIndexesMap.TryGetValue( tokenType, out indexes ) || indexes == null ) |
| { |
| indexes = new List<int>(); // no list yet for this token type |
| indexes.Add( streamIndex ); // not there yet, add |
| tokenTypeToStreamIndexesMap[tokenType] = indexes; |
| } |
| else |
| { |
| if ( !indexes.Contains( streamIndex ) ) |
| { |
| indexes.Add( streamIndex ); // not there yet, add |
| } |
| } |
| } |
| |
| /** <summary> |
| * Track the indicated token type in the reverse index. Call this |
| * repeatedly for each type or use variant with Set argument to |
| * set all at once. |
| * </summary> |
| * |
| * <param name="tokenType" /> |
| */ |
| public void reverseIndex( int tokenType ) |
| { |
| if ( tokenTypesToReverseIndex == null ) |
| { |
| tokenTypesToReverseIndex = new HashSet<int>(); |
| } |
| else if ( tokenTypesToReverseIndex == INDEX_ALL ) |
| { |
| return; |
| } |
| tokenTypesToReverseIndex.add( tokenType ); |
| } |
| |
| /** <summary> |
| * Track the indicated token types in the reverse index. Set |
| * to INDEX_ALL to track all token types. |
| * </summary> |
| */ |
| public void reverseIndex( HashSet<int> tokenTypes ) |
| { |
| tokenTypesToReverseIndex = tokenTypes; |
| } |
| |
| /** <summary> |
| * Given a node pointer, return its index into the node stream. |
| * This is not its Token stream index. If there is no reverse map |
| * from node to stream index or the map does not contain entries |
| * for node's token type, a linear search of entire stream is used. |
| * </summary> |
| * |
| * <remarks> |
| * Return -1 if exact node pointer not in stream. |
| * </remarks> |
| */ |
| public int getNodeIndex( object node ) |
| { |
| //System.out.println("get "+node); |
| if ( tokenTypeToStreamIndexesMap == null ) |
| { |
| return getNodeIndexLinearly( node ); |
| } |
| int tokenType = adaptor.getType( node ); |
| IList<int> indexes; |
| if ( !tokenTypeToStreamIndexesMap.TryGetValue( tokenType, out indexes ) || indexes == null ) |
| { |
| //System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node)); |
| return getNodeIndexLinearly( node ); |
| } |
| for ( int i = 0; i < indexes.size(); i++ ) |
| { |
| int streamIndex = indexes[i]; |
| object n = get( streamIndex ); |
| if ( n == node ) |
| { |
| //System.out.println("found in index; stream index = "+streamIndexI); |
| return streamIndex; // found it! |
| } |
| } |
| return -1; |
| } |
| #endif |
| |
| } |
| } |
