1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Conversion to C#: 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// TODO: build indexes for wizard 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//#define BUILD_INDEXES 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernamespace Antlr.Runtime.Tree { 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using System.Collections.Generic; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using IList = System.Collections.IList; 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#if BUILD_INDEXES 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using IDictionary = System.Collections.IDictionary; 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Build and navigate trees with this object. Must know about the names 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of tokens so you have to pass in a map or array of token names (from which 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this class can build the map). I.e., Token DECL means nothing unless the 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * class can translate it to a token type. 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * In order to create nodes and navigate, this class needs a TreeAdaptor. 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This class can build a token type -> node index for repeated use or for 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * iterating over the various nodes with a particular type. 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This class works in conjunction with the TreeAdaptor rather than moving 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * all this functionality into the adaptor. An adaptor helps build and 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * navigate trees using methods. This class helps you do it with string 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * patterns like "(A B C)". You can create a tree from that pattern or 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * match subtrees against it. 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class TreeWizard { 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected ITreeAdaptor adaptor; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected IDictionary<string, int> tokenNameToTypeMap; 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public interface IContextVisitor { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: should this be called visit or something else? 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels); 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract class Visitor : IContextVisitor { 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels) { 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Visit(t); 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract void Visit(object t); 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver class ActionVisitor : Visitor { 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.Action<object> _action; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public ActionVisitor(System.Action<object> action) { 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _action = action; 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override void Visit(object t) { 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _action(t); 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * When using %label:TOKENNAME in a tree for parse(), we must 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * track the label. 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class TreePattern : CommonTree { 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public string label; 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public bool hasTextArg; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreePattern(IToken payload) : 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver base(payload) { 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override string ToString() { 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (label != null) { 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return "%" + label + ":"; //+ base.ToString(); 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return base.ToString(); 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class WildcardTreePattern : TreePattern { 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public WildcardTreePattern(IToken payload) : 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver base(payload) { 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>This adaptor creates TreePattern objects for use during scan()</summary> */ 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class TreePatternTreeAdaptor : CommonTreeAdaptor { 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override object Create(IToken payload) { 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new TreePattern(payload); 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#if BUILD_INDEXES 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: build indexes for the wizard 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * During fillBuffer(), we can make a reverse index from a set 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of token types of interest to the list of indexes into the 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * node stream. This lets us convert a node pointer to a 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stream index semi-efficiently for a list of interesting 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nodes such as function definition nodes (you'll want to seek 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to their bodies for an interpreter). Also useful for doing 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * dynamic searches; i.e., go find me all PLUS nodes. 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected IDictionary<int, IList<int>> tokenTypeToStreamIndexesMap; 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If tokenTypesToReverseIndex set to INDEX_ALL then indexing 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * occurs for all token types. 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static readonly HashSet<int> INDEX_ALL = new HashSet<int>(); 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A set of token types user would like to index for faster lookup. 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If this is INDEX_ALL, then all token types are tracked. If null, 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * then none are indexed. 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected HashSet<int> tokenTypesToReverseIndex = null; 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeWizard(ITreeAdaptor adaptor) { 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.adaptor = adaptor; 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeWizard(ITreeAdaptor adaptor, IDictionary<string, int> tokenNameToTypeMap) { 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.adaptor = adaptor; 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.tokenNameToTypeMap = tokenNameToTypeMap; 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeWizard(ITreeAdaptor adaptor, string[] tokenNames) { 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.adaptor = adaptor; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.tokenNameToTypeMap = ComputeTokenTypes(tokenNames); 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeWizard(string[] tokenNames) : 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this(null, tokenNames) { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Compute a Map<String, Integer> that is an inverted index of 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * tokenNames (which maps int token types to names). 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual IDictionary<string, int> ComputeTokenTypes(string[] tokenNames) { 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IDictionary<string, int> m = new Dictionary<string, int>(); 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tokenNames == null) { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return m; 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int ttype = TokenTypes.Min; ttype < tokenNames.Length; ttype++) { 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver string name = tokenNames[ttype]; 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m[name] = ttype; 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return m; 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Using the map of token names to token types, return the type.</summary> */ 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int GetTokenType(string tokenName) { 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tokenNameToTypeMap == null) { 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TokenTypes.Invalid; 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int value; 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tokenNameToTypeMap.TryGetValue(tokenName, out value)) 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return value; 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TokenTypes.Invalid; 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Walk the entire tree and make a node name to nodes mapping. 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For now, use recursion but later nonrecursive version may be 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * more efficient. Returns Map<Integer, List> where the List is 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of your AST node type. The Integer is the token type of the node. 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: save this index so that find and visit are faster 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IDictionary<int, IList> Index(object t) { 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IDictionary<int, IList> m = new Dictionary<int, IList>(); 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IndexCore(t, m); 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return m; 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Do the work for index</summary> */ 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual void IndexCore(object t, IDictionary<int, IList> m) { 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == null) { 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int ttype = adaptor.GetType(t); 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList elements; 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!m.TryGetValue(ttype, out elements) || elements == null) { 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements = new List<object>(); 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m[ttype] = elements; 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements.Add(t); 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = adaptor.GetChildCount(t); 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object child = adaptor.GetChild(t, i); 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IndexCore(child, m); 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver class FindTreeWizardVisitor : TreeWizard.Visitor { 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList _nodes; 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public FindTreeWizardVisitor(IList nodes) { 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _nodes = nodes; 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override void Visit(object t) { 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _nodes.Add(t); 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver class FindTreeWizardContextVisitor : TreeWizard.IContextVisitor { 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreeWizard _outer; 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern _tpattern; 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList _subtrees; 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public FindTreeWizardContextVisitor(TreeWizard outer, TreePattern tpattern, IList subtrees) { 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _outer = outer; 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _tpattern = tpattern; 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _subtrees = subtrees; 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Visit(object t, object parent, int childIndex, IDictionary<string, object> labels) { 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_outer.ParseCore(t, _tpattern, null)) { 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _subtrees.Add(t); 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Return a List of tree nodes with token type ttype</summary> */ 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual IList Find(object t, int ttype) { 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList nodes = new List<object>(); 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Visit(t, ttype, new FindTreeWizardVisitor(nodes)); 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return nodes; 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Return a List of subtrees matching pattern.</summary> */ 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual IList Find(object t, string pattern) { 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList subtrees = new List<object>(); 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Create a TreePattern from the pattern 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternLexer tokenizer = new TreePatternLexer(pattern); 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternParser parser = 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern tpattern = (TreePattern)parser.Pattern(); 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't allow invalid patterns 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern == null || 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern.IsNil || 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern.GetType() == typeof(WildcardTreePattern)) { 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int rootTokenType = tpattern.Type; 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Visit(t, rootTokenType, new FindTreeWizardContextVisitor(this, tpattern, subtrees)); 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return subtrees; 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual object FindFirst(object t, int ttype) { 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual object FindFirst(object t, string pattern) { 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Visit every ttype node in t, invoking the visitor. This is a quicker 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * version of the general visit(t, pattern) method. The labels arg 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the visitor action method is never set (it's null) since using 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a token type rather than a pattern doesn't let us set a label. 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Visit(object t, int ttype, IContextVisitor visitor) { 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver VisitCore(t, null, 0, ttype, visitor); 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Visit(object t, int ttype, System.Action<object> action) { 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Visit(t, ttype, new ActionVisitor(action)); 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Do the recursive work for visit</summary> */ 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual void VisitCore(object t, object parent, int childIndex, int ttype, IContextVisitor visitor) { 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == null) { 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (adaptor.GetType(t) == ttype) { 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver visitor.Visit(t, parent, childIndex, null); 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = adaptor.GetChildCount(t); 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object child = adaptor.GetChild(t, i); 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver VisitCore(child, t, i, ttype, visitor); 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver class VisitTreeWizardContextVisitor : TreeWizard.IContextVisitor { 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreeWizard _outer; 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IContextVisitor _visitor; 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IDictionary<string, object> _labels; 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern _tpattern; 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public VisitTreeWizardContextVisitor(TreeWizard outer, IContextVisitor visitor, IDictionary<string, object> labels, TreePattern tpattern) { 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _outer = outer; 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _visitor = visitor; 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _labels = labels; 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _tpattern = tpattern; 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Visit(object t, object parent, int childIndex, IDictionary<string, object> unusedlabels) { 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the unusedlabels arg is null as visit on token type doesn't set. 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _labels.Clear(); 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_outer.ParseCore(t, _tpattern, _labels)) { 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _visitor.Visit(t, parent, childIndex, _labels); 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For all subtrees that match the pattern, execute the visit action. 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The implementation uses the root node of the pattern in combination 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with visit(t, ttype, visitor) so nil-rooted patterns are not allowed. 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Patterns with wildcard roots are also not allowed. 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Visit(object t, string pattern, IContextVisitor visitor) { 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Create a TreePattern from the pattern 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternLexer tokenizer = new TreePatternLexer(pattern); 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternParser parser = 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern tpattern = (TreePattern)parser.Pattern(); 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't allow invalid patterns 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern == null || 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern.IsNil || 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern.GetType() == typeof(WildcardTreePattern)) { 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IDictionary<string, object> labels = new Dictionary<string, object>(); // reused for each _parse 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int rootTokenType = tpattern.Type; 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Visit(t, rootTokenType, new VisitTreeWizardContextVisitor(this, visitor, labels, tpattern)); 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * on the various nodes and '.' (dot) as the node/subtree wildcard, 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * return true if the pattern matches and fill the labels Map with 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the labels pointing at the appropriate nodes. Return false if 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the pattern is malformed or the tree does not match. 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If a node specifies a text arg in pattern, then that must match 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for that node in t. 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: what's a better way to indicate bad pattern? Exceptions are a hassle 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public bool Parse(object t, string pattern, IDictionary<string, object> labels) { 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternLexer tokenizer = new TreePatternLexer(pattern); 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternParser parser = 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new TreePatternParser(tokenizer, this, new TreePatternTreeAdaptor()); 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern tpattern = (TreePattern)parser.Pattern(); 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("t="+((Tree)t).toStringTree()); 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("scant="+tpattern.toStringTree()); 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bool matched = ParseCore(t, tpattern, labels); 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return matched; 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public bool Parse(object t, string pattern) { 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Parse(t, pattern, null); 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Do the work for parse. Check to see if the t2 pattern fits the 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * structure and token types in t1. Check text if the pattern has 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * text arguments on nodes. Fill labels map with pointers to nodes 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in tree matched against nodes in pattern with labels. 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual bool ParseCore(object t1, TreePattern tpattern, IDictionary<string, object> labels) { 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure both are non-null 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t1 == null || tpattern == null) { 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // check roots (wildcard matches anything) 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern.GetType() != typeof(WildcardTreePattern)) { 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (adaptor.GetType(t1) != tpattern.Type) { 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if pattern has text, check node text 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern.hasTextArg && !adaptor.GetText(t1).Equals(tpattern.Text)) { 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern.label != null && labels != null) { 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // map label in pattern to node in t1 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels[tpattern.label] = t1; 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // check children 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n1 = adaptor.GetChildCount(t1); 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n2 = tpattern.ChildCount; 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n1 != n2) { 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n1; i++) { 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object child1 = adaptor.GetChild(t1, i); 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePattern child2 = (TreePattern)tpattern.GetChild(i); 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!ParseCore(child1, child2, labels)) { 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Create a tree or node from the indicated tree pattern that closely 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * follows ANTLR tree grammar tree element syntax: 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (root child1 ... child2). 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * You can also just pass in a node: ID 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Any node can have a text argument: ID[foo] 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (notice there are no quotes around foo--it's clear it's a string). 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nil is a special name meaning "give me a nil node". Useful for 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * making lists: (nil A B C) is a list of A B C. 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual object Create(string pattern) { 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternLexer tokenizer = new TreePatternLexer(pattern); 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreePatternParser parser = new TreePatternParser(tokenizer, this, adaptor); 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object t = parser.Pattern(); 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return t; 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Compare t1 and t2; return true if token types/text, structure match exactly. 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The trees are examined in their entirety so that (A B) does not match 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (A B C) nor (A (B C)). 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: allow them to pass in a comparator 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: have a version that is nonstatic so it can use instance adaptor 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I cannot rely on the tree node's equals() implementation as I make 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * no constraints at all on the node types nor interface etc... 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static bool Equals(object t1, object t2, ITreeAdaptor adaptor) { 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return EqualsCore(t1, t2, adaptor); 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Compare type, structure, and text of two trees, assuming adaptor in 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this instance of a TreeWizard. 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public new bool Equals(object t1, object t2) { 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return EqualsCore(t1, t2, adaptor); 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected static bool EqualsCore(object t1, object t2, ITreeAdaptor adaptor) { 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure both are non-null 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t1 == null || t2 == null) { 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // check roots 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (adaptor.GetType(t1) != adaptor.GetType(t2)) { 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!adaptor.GetText(t1).Equals(adaptor.GetText(t2))) { 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // check children 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n1 = adaptor.GetChildCount(t1); 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n2 = adaptor.GetChildCount(t2); 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n1 != n2) { 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n1; i++) { 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object child1 = adaptor.GetChild(t1, i); 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object child2 = adaptor.GetChild(t2, i); 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!EqualsCore(child1, child2, adaptor)) { 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#if BUILD_INDEXES 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: next stuff taken from CommonTreeNodeStream 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Given a node, add this to the reverse index tokenTypeToStreamIndexesMap. 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * You can override this method to alter how indexing occurs. The 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * default is to create a 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Map<Integer token type,ArrayList<Integer stream index>> 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This data structure allows you to find all nodes with type INT in order. 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If you really need to find a node of type, say, FUNC quickly then perhaps 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Map<Integertoken type,Map<Object tree node,Integer stream index>> 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * would be better for you. The interior maps map a tree node to 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the index so you don't have to search linearly for a specific node. 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If you change this method, you will likely need to change 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * getNodeIndex(), which extracts information. 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void fillReverseIndex( object node, int streamIndex ) 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("revIndex "+node+"@"+streamIndex); 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tokenTypesToReverseIndex == null ) 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // no indexing if this is empty (nothing of interest) 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tokenTypeToStreamIndexesMap == null ) 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypeToStreamIndexesMap = new Dictionary<int, IList<int>>(); // first indexing op 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int tokenType = adaptor.getType( node ); 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !( tokenTypesToReverseIndex == INDEX_ALL || 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypesToReverseIndex.Contains( tokenType ) ) ) 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // tokenType not of interest 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList<int> indexes; 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !tokenTypeToStreamIndexesMap.TryGetValue( tokenType, out indexes ) || indexes == null ) 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver indexes = new List<int>(); // no list yet for this token type 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver indexes.Add( streamIndex ); // not there yet, add 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypeToStreamIndexesMap[tokenType] = indexes; 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !indexes.Contains( streamIndex ) ) 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver indexes.Add( streamIndex ); // not there yet, add 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Track the indicated token type in the reverse index. Call this 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * repeatedly for each type or use variant with Set argument to 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * set all at once. 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <param name="tokenType" /> 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reverseIndex( int tokenType ) 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tokenTypesToReverseIndex == null ) 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypesToReverseIndex = new HashSet<int>(); 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( tokenTypesToReverseIndex == INDEX_ALL ) 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypesToReverseIndex.add( tokenType ); 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Track the indicated token types in the reverse index. Set 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to INDEX_ALL to track all token types. 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reverseIndex( HashSet<int> tokenTypes ) 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenTypesToReverseIndex = tokenTypes; 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Given a node pointer, return its index into the node stream. 621324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This is not its Token stream index. If there is no reverse map 622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from node to stream index or the map does not contain entries 623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for node's token type, a linear search of entire stream is used. 624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 627324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return -1 if exact node pointer not in stream. 628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getNodeIndex( object node ) 631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("get "+node); 633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tokenTypeToStreamIndexesMap == null ) 634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return getNodeIndexLinearly( node ); 636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int tokenType = adaptor.getType( node ); 638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IList<int> indexes; 639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !tokenTypeToStreamIndexesMap.TryGetValue( tokenType, out indexes ) || indexes == null ) 640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node)); 642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return getNodeIndexLinearly( node ); 643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for ( int i = 0; i < indexes.size(); i++ ) 645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int streamIndex = indexes[i]; 647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object n = get( streamIndex ); 648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( n == node ) 649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("found in index; stream index = "+streamIndexI); 651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return streamIndex; // found it! 652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return -1; 655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 660