/*
* [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( new CommonTreeAdaptor(), 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
}
}