runtime/ObjC/Framework/ANTLRTreeWizard.m

//
//  ANTLRTreeWizard.m
//  ANTLR
//
//  Created by Alan Condit on 6/18/10.
// [The "BSD licence"]
// Copyright (c) 2010 Alan Condit
// 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.

#import "ANTLRTreeWizard.h"
#import "ANTLRTreePatternLexer.h"
#import "ANTLRTreePatternParser.h"
#import "ANTLRIntArray.h"

@implementation ANTLRVisitor

+ (ANTLRVisitor *)newANTLRVisitor:(NSInteger)anAction Actor:(id)anActor Object:(id)anObject1 Object:(id)anObject2
{
    return [[ANTLRVisitor alloc] initWithAction:anAction Actor:(id)anActor Object:(id)anObject1 Object:(id)anObject2];
}

- (id) initWithAction:(NSInteger)anAction Actor:(id)anActor Object:(id)anObject1 Object:(id)anObject2
{
    if ((self = [super init]) != nil) {
        action = anAction;
        actor = anActor;
        if ( actor ) [actor retain];
        object1 = anObject1;
        if ( object1 ) [object1 retain];
        object2 = anObject2;
        if ( object2 ) [object2 retain];
    }
    return self;
}

- (void) dealloc
{
#ifdef DEBUG_DEALLOC
    NSLog( @"called dealloc in ANTLRVisitor" );
#endif
    if ( actor ) [actor release];
    if ( object1 ) [object1 release];
    if ( object2 ) [object2 release];
    [super dealloc];
}

- (void) visit:(ANTLRCommonTree *)t Parent:(ANTLRCommonTree *)parent ChildIndex:(NSInteger)childIndex Map:(ANTLRMap *)labels
{
    switch (action) {
        case 0:
            [(ANTLRMap *)object2 /* labels */ clear];
            if ( [(ANTLRTreeWizard *)actor _parse:t Pattern:object1/* tpattern */ Map:object2 /* labels */] ) {
                [self visit:t Parent:parent ChildIndex:childIndex Map:object2 /* labels */];
            }
            break;
        case 1:
            if ( [(ANTLRTreeWizard *)actor _parse:t Pattern:object1/* tpattern */ Map:nil] ) {
                [(AMutableArray *)object2/* subtrees */ addObject:t];
            }
            break;
    }
    // [self visit:t];
    return;
}

- (void) visit:(ANTLRCommonTree *)t
{
    [object1 addObject:t];
    return;
}

@synthesize action;
@synthesize actor;
@synthesize object1;
@synthesize object2;
@end

/** When using %label:TOKENNAME in a tree for parse(), we must
 *  track the label.
 */
@implementation ANTLRTreePattern

@synthesize label;
@synthesize hasTextArg;

+ (ANTLRCommonTree *)newANTLRTreePattern:(id<ANTLRToken>)payload
{
    return (ANTLRCommonTree *)[[ANTLRTreePattern alloc] initWithToken:payload];
}

- (id) initWithToken:(id<ANTLRToken>)payload
{
    self = [super initWithToken:payload];
    if ( self != nil ) {
    }
    return (ANTLRCommonTree *)self;
}

- (void) dealloc
{
#ifdef DEBUG_DEALLOC
    NSLog( @"called dealloc in ANTLRTreePattern" );
#endif
    if ( label ) [label release];
    [super dealloc];
}

- (NSString *)toString
{
    if ( label != nil ) {
        return [NSString stringWithFormat:@"\% %@ : %@", label, [super toString]];
    }
    else {
        return [super toString];				
    }
}

@end

@implementation ANTLRWildcardTreePattern

+ (ANTLRWildcardTreePattern *)newANTLRWildcardTreePattern:(id<ANTLRToken>)payload
{
    return(ANTLRWildcardTreePattern *)[[ANTLRWildcardTreePattern alloc] initWithToken:(id<ANTLRToken>)payload];
}

- (id) initWithToken:(id<ANTLRToken>)payload
{
    self = [super initWithToken:payload];
    if ( self != nil ) {
    }
    return self;
}

@end

/** This adaptor creates TreePattern objects for use during scan() */
@implementation ANTLRTreePatternTreeAdaptor

+ (ANTLRTreePatternTreeAdaptor *)newTreeAdaptor
{
    return [[ANTLRTreePatternTreeAdaptor alloc] init];
}

- (id) init
{
    self = [super init];
    if ( self != nil ) {
    }
    return self;
}

- (ANTLRCommonTree *)createTreePattern:(id<ANTLRToken>)payload
{
    return (ANTLRCommonTree *)[super create:payload];
}
          
@end

@implementation ANTLRTreeWizard

// TODO: build indexes for the wizard

/** 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.
 protected Map tokenTypeToStreamIndexesMap;
 
 ** If tokenTypesToReverseIndex set to INDEX_ALL then indexing
 *  occurs for all token types.
 public static final Set INDEX_ALL = new HashSet();
 
 ** 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 nil,
 *  then none are indexed.
 protected Set tokenTypesToReverseIndex = nil;
 */

+ (ANTLRTreeWizard *) newANTLRTreeWizard:(id<ANTLRTreeAdaptor>)anAdaptor
{
    return [[ANTLRTreeWizard alloc] initWithAdaptor:anAdaptor];
}

+ (ANTLRTreeWizard *)newANTLRTreeWizard:(id<ANTLRTreeAdaptor>)anAdaptor Map:(ANTLRMap *)aTokenNameToTypeMap
{
    return [[ANTLRTreeWizard alloc] initWithAdaptor:anAdaptor Map:aTokenNameToTypeMap];
}

+ (ANTLRTreeWizard *)newANTLRTreeWizard:(id<ANTLRTreeAdaptor>)anAdaptor TokenNames:(NSArray *)theTokNams
{
    return [[ANTLRTreeWizard alloc] initWithTokenNames:anAdaptor TokenNames:theTokNams];
}

+ (ANTLRTreeWizard *)newANTLRTreeWizardWithTokenNames:(NSArray *)theTokNams
{
    return [[ANTLRTreeWizard alloc] initWithTokenNames:theTokNams];
}

- (id) init
{
    if ((self = [super init]) != nil) {
    }
    return self;
}

- (id) initWithAdaptor:(id<ANTLRTreeAdaptor>)anAdaptor
{
    if ((self = [super init]) != nil) {
        adaptor = anAdaptor;
        if ( adaptor ) [adaptor retain];
    }
    return self;
}
            
- (id) initWithAdaptor:(id<ANTLRTreeAdaptor>)anAdaptor Map:(ANTLRMap *)aTokenNameToTypeMap
{
    if ((self = [super init]) != nil) {
        adaptor = anAdaptor;
        if ( adaptor ) [adaptor retain];
        tokenNameToTypeMap = aTokenNameToTypeMap;
   }
    return self;
}

- (id) initWithTokenNames:(NSArray *)theTokNams
{
    if ((self = [super init]) != nil) {
#pragma warning Fix initWithTokenNames.
        // adaptor = anAdaptor;
        //tokenNameToTypeMap = aTokenNameToTypeMap;
        tokenNameToTypeMap = [[self computeTokenTypes:theTokNams] retain];
    }
    return self;
}
             
- (id) initWithTokenNames:(id<ANTLRTreeAdaptor>)anAdaptor TokenNames:(NSArray *)theTokNams
{
    if ((self = [super init]) != nil) {
        adaptor = anAdaptor;
        if ( adaptor ) [adaptor retain];
        // tokenNameToTypeMap = aTokenNameToTypeMap;
        tokenNameToTypeMap = [[self computeTokenTypes:theTokNams] retain];
    }
    return self;
}
            
- (void) dealloc
{
#ifdef DEBUG_DEALLOC
    NSLog( @"called dealloc in ANTLRTreePatternTreeAdaptor" );
#endif
    if ( adaptor ) [adaptor release];
    if ( tokenNameToTypeMap ) [tokenNameToTypeMap release];
    [super dealloc];
}

/** Compute a Map<String, Integer> that is an inverted index of
 *  tokenNames (which maps int token types to names).
 */
- (ANTLRMap *)computeTokenTypes:(NSArray *)theTokNams
{
    ANTLRMap *m = [ANTLRMap newANTLRMap];
    if ( theTokNams == nil ) {
        return m;
    }
    for (int ttype = ANTLRTokenTypeMIN; ttype < [theTokNams count]; ttype++) {
        NSString *name = (NSString *) [theTokNams objectAtIndex:ttype];
        [m putName:name TType:ttype];
    }
    return m;
}

/** Using the map of token names to token types, return the type. */
- (NSInteger)getTokenType:(NSString *)tokenName
{
    if ( tokenNameToTypeMap == nil ) {
        return ANTLRTokenTypeInvalid;
    }
    NSInteger aTType = (NSInteger)[tokenNameToTypeMap getTType:tokenName];
    if ( aTType != -1 ) {
        return aTType;
    }
    return ANTLRTokenTypeInvalid;
}

/** 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.
 *
 *  TODO: save this index so that find and visit are faster
 */
- (ANTLRMap *)index:(ANTLRCommonTree *)t
{
    ANTLRMap *m = [ANTLRMap newANTLRMap];
    [self _index:t Map:m];
    return m;
}

/** Do the work for index */
- (void) _index:(ANTLRCommonTree *)t Map:(ANTLRMap *)m
{
    if ( t==nil ) {
        return;
    }
#pragma warning Fix _index use of ANTLRMap.
    NSInteger ttype = [adaptor getType:t];
    ANTLRMap *elements = (ANTLRMap *)[m getName:ttype];
    if ( elements == nil ) {
        elements = [ANTLRMap newANTLRMapWithLen:100];
        [m putNode:ttype Node:elements];
    }
    [elements addObject:t];
    int n = [adaptor getChildCount:t];
    for (int i=0; i<n; i++) {
        ANTLRCommonTree * child = [adaptor getChild:t At:i];
        [self _index:child Map:m];
    }
}

/** Return a List of tree nodes with token type ttype */
- (AMutableArray *)find:(ANTLRCommonTree *)t Type:(NSInteger)ttype
{
#ifdef DONTUSENOMO
    final List nodes = new ArrayList();
    visit(t, ttype, new TreeWizard.Visitor() {
        public void visit(Object t) {
            [nodes addObject t];
        }
    } );
#endif
    AMutableArray *nodes = [AMutableArray arrayWithCapacity:100];
    ANTLRVisitor *contextVisitor = [ANTLRVisitor newANTLRVisitor:3 Actor:self Object:(id)nodes Object:nil];
    [self visit:t Type:ttype Visitor:contextVisitor];
    return nodes;
}

/** Return a List of subtrees matching pattern. */
- (AMutableArray *)find:(ANTLRCommonTree *)t Pattern:(NSString *)pattern
{
    AMutableArray *subtrees = [AMutableArray arrayWithCapacity:100];
    // Create a TreePattern from the pattern
    ANTLRTreePatternLexer *tokenizer = [ANTLRTreePatternLexer newANTLRTreePatternLexer:pattern];
    ANTLRTreePatternParser *parser = [ANTLRTreePatternParser newANTLRTreePatternParser:tokenizer
                                                                                     Wizard:self
                                                                                    Adaptor:[ANTLRTreePatternTreeAdaptor newTreeAdaptor]];
    ANTLRCommonTree *tpattern = (ANTLRCommonTree *)[parser pattern];
    // don't allow invalid patterns
    if ( tpattern == nil ||
        [tpattern isNil] ||
        [tpattern class] == [ANTLRWildcardTreePattern class] )
    {
        return nil;
    }
    int rootTokenType = [tpattern type];
#ifdef DONTUSENOMO
    visit(t, rootTokenType, new TreeWizard.ContextVisitor() {
        public void visit(Object t, Object parent, int childIndex, Map labels) {
            if ( _parse(t, tpattern, null) ) {
                subtrees.add(t);
            }
        }
    } );
#endif
    ANTLRVisitor *contextVisitor = [ANTLRVisitor newANTLRVisitor:1 Actor:self Object:tpattern Object:subtrees];
    [self visit:t Type:rootTokenType Visitor:contextVisitor];
    return subtrees;
}

- (ANTLRTreeWizard *)findFirst:(ANTLRCommonTree *) t Type:(NSInteger)ttype
{
    return nil;
}

- (ANTLRTreeWizard *)findFirst:(ANTLRCommonTree *) t Pattern:(NSString *)pattern
{
    return nil;
}

/** 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 nil) since using
 *  a token type rather than a pattern doesn't let us set a label.
 */
- (void) visit:(ANTLRCommonTree *)t Type:(NSInteger)ttype Visitor:(ANTLRVisitor *)visitor
{
    [self _visit:t Parent:nil ChildIndex:0 Type:ttype Visitor:visitor];
}

/** Do the recursive work for visit */
- (void) _visit:(ANTLRCommonTree *)t
         Parent:(ANTLRCommonTree *)parent
     ChildIndex:(NSInteger)childIndex
           Type:(NSInteger)ttype
        Visitor:(ANTLRVisitor *)visitor
{
    if ( t == nil ) {
        return;
    }
    if ( [adaptor getType:t] == ttype ) {
        [visitor visit:t Parent:parent ChildIndex:childIndex Map:nil];
    }
    int n = [adaptor getChildCount:t];
    for (int i=0; i<n; i++) {
        ANTLRCommonTree * child = [adaptor getChild:t At:i];
        [self _visit:child Parent:t ChildIndex:i Type:ttype Visitor:visitor];
    }
}

/** 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.
 */
- (void)visit:(ANTLRCommonTree *)t Pattern:(NSString *)pattern Visitor:(ANTLRVisitor *)visitor
{
    // Create a TreePattern from the pattern
    ANTLRTreePatternLexer *tokenizer = [ANTLRTreePatternLexer newANTLRTreePatternLexer:pattern];
    ANTLRTreePatternParser *parser =
    [ANTLRTreePatternParser newANTLRTreePatternParser:tokenizer Wizard:self Adaptor:[ANTLRTreePatternTreeAdaptor newTreeAdaptor]];
    ANTLRCommonTree *tpattern = [parser pattern];
    // don't allow invalid patterns
    if ( tpattern == nil ||
        [tpattern isNil] ||
        [tpattern class] == [ANTLRWildcardTreePattern class] )
    {
        return;
    }
    ANTLRMapElement *labels = [ANTLRMap newANTLRMap]; // reused for each _parse
    int rootTokenType = [tpattern type];
#pragma warning This is another one of those screwy nested constructs that I have to figure out
#ifdef DONTUSENOMO
    visit(t, rootTokenType, new TreeWizard.ContextVisitor() {
        public void visit(Object t, Object parent, int childIndex, Map unusedlabels) {
            // the unusedlabels arg is null as visit on token type doesn't set.
            labels.clear();
            if ( _parse(t, tpattern, labels) ) {
                visitor.visit(t, parent, childIndex, labels);
            }
        }
    });
#endif
    ANTLRVisitor *contextVisitor = [ANTLRVisitor newANTLRVisitor:0 Actor:self Object:tpattern Object:labels];
    [self visit:t Type:rootTokenType Visitor:contextVisitor];
}

/** 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.
 *
 *  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 
 */
- (BOOL)parse:(ANTLRCommonTree *)t Pattern:(NSString *)pattern Map:(ANTLRMap *)labels
{
#ifdef DONTUSENOMO
    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());
     */
    boolean matched = _parse(t, tpattern, labels);
    return matched;
#endif
    ANTLRTreePatternLexer *tokenizer = [ANTLRTreePatternLexer newANTLRTreePatternLexer:pattern];
    ANTLRTreePatternParser *parser = [ANTLRTreePatternParser newANTLRTreePatternParser:tokenizer
                                                                                Wizard:self
                                                                               Adaptor:[ANTLRTreePatternTreeAdaptor newTreeAdaptor]];
    ANTLRCommonTree *tpattern = [parser pattern];
    /*
     System.out.println("t="+((Tree)t).toStringTree());
     System.out.println("scant="+tpattern.toStringTree());
     */
    //BOOL matched = [self _parse:t Pattern:tpattern Map:labels];
    //return matched;
    return [self _parse:t Pattern:tpattern Map:labels];
}

- (BOOL) parse:(ANTLRCommonTree *)t Pattern:(NSString *)pattern
{
    return [self parse:t Pattern:pattern Map:nil];
}

/** 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.
 */
- (BOOL) _parse:(ANTLRCommonTree *)t1 Pattern:(ANTLRCommonTree *)aTPattern Map:(ANTLRMap *)labels
{
    ANTLRTreePattern *tpattern;
    // make sure both are non-nil
    if ( t1 == nil || aTPattern == nil ) {
        return NO;
    }
    if ( [aTPattern isKindOfClass:[ANTLRWildcardTreePattern class]] ) {
        tpattern = (ANTLRTreePattern *)aTPattern;
    }
    // check roots (wildcard matches anything)
    if ( [tpattern class] != [ANTLRWildcardTreePattern class] ) {
        if ( [adaptor getType:t1] != [tpattern type] )
            return NO;
        // if pattern has text, check node text
        if ( tpattern.hasTextArg && ![[adaptor getText:t1] isEqualToString:[tpattern text]] ) {
            return NO;
        }
    }
    if ( tpattern.label != nil && labels!=nil ) {
        // map label in pattern to node in t1
        [labels putName:tpattern.label Node:t1];
    }
    // check children
    int n1 = [adaptor getChildCount:t1];
    int n2 = [tpattern getChildCount];
    if ( n1 != n2 ) {
        return NO;
    }
    for (int i=0; i<n1; i++) {
        ANTLRCommonTree * child1 = [adaptor getChild:t1 At:i];
        ANTLRCommonTree *child2 = (ANTLRCommonTree *)[tpattern getChild:i];
        if ( ![self _parse:child1 Pattern:child2 Map:labels] ) {
            return NO;
        }
    }
    return YES;
}

/** Create a tree or node from the indicated tree pattern that closely
 *  follows ANTLR tree grammar tree element syntax:
 *
 * 		(root child1 ... child2).
 *
 *  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.
 */
- (ANTLRCommonTree *) createTree:(NSString *)pattern
{
    ANTLRTreePatternLexer *tokenizer = [ANTLRTreePatternLexer newANTLRTreePatternLexer:pattern];
    ANTLRTreePatternParser *parser = [ANTLRTreePatternParser newANTLRTreePatternParser:tokenizer Wizard:self Adaptor:adaptor];
    ANTLRCommonTree * t = [parser pattern];
    return t;
}

/** 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)). 
 // 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... 
 */
- (BOOL)equals:(id)t1 O2:(id)t2 Adaptor:(id<ANTLRTreeAdaptor>)anAdaptor
{
    return [self _equals:t1 O2:t2 Adaptor:anAdaptor];
}

/** Compare type, structure, and text of two trees, assuming adaptor in
 *  this instance of a TreeWizard.
 */
- (BOOL)equals:(id)t1 O2:(id)t2
{
    return [self _equals:t1 O2:t2 Adaptor:adaptor];
}

- (BOOL) _equals:(id)t1 O2:(id)t2 Adaptor:(id<ANTLRTreeAdaptor>)anAdaptor
{
    // make sure both are non-nil
    if ( t1==nil || t2==nil ) {
        return NO;
    }
    // check roots
    if ( [anAdaptor getType:t1] != [anAdaptor getType:t2] ) {
        return NO;
    }
    if ( ![[anAdaptor getText:t1] isEqualTo:[anAdaptor getText:t2]] ) {
        return NO;
    }
    // check children
    NSInteger n1 = [anAdaptor getChildCount:t1];
    NSInteger n2 = [anAdaptor getChildCount:t2];
    if ( n1 != n2 ) {
        return NO;
    }
    for (int i=0; i<n1; i++) {
        ANTLRCommonTree * child1 = [anAdaptor getChild:t1 At:i];
        ANTLRCommonTree * child2 = [anAdaptor getChild:t2 At:i];
        if ( ![self _equals:child1 O2:child2 Adaptor:anAdaptor] ) {
            return NO;
        }
    }
    return YES;
}

// TODO: next stuff taken from CommonTreeNodeStream

/** 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>>
 *
 *  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.
- (void)fillReverseIndex:(ANTLRCommonTree *)node Index:(NSInteger)streamIndex
{
    //System.out.println("revIndex "+node+"@"+streamIndex);
    if ( tokenTypesToReverseIndex == nil ) {
        return; // no indexing if this is empty (nothing of interest)
    }
    if ( tokenTypeToStreamIndexesMap == nil ) {
        tokenTypeToStreamIndexesMap = [ANTLRMap newANTLRMap]; // first indexing op
    }
    int tokenType = [adaptor getType:node];
    Integer tokenTypeI = new Integer(tokenType);
    if ( !(tokenTypesToReverseIndex == INDEX_ALL ||
            [tokenTypesToReverseIndex contains:tokenTypeI]) ) {
        return; // tokenType not of interest
    }
    NSInteger streamIndexI = streamIndex;
    AMutableArray *indexes = (AMutableArray *)[tokenTypeToStreamIndexesMap objectAtIndex:tokenTypeI];
    if ( indexes==nil ) {
        indexes = [AMutableArray arrayWithCapacity:100]; // no list yet for this token type
        indexes.add(streamIndexI); // not there yet, add
        [tokenTypeToStreamIndexesMap put:tokenTypeI Idexes:indexes];
    }
    else {
        if ( ![indexes contains:streamIndexI] ) {
            [indexes add:streamIndexI]; // not there yet, add
        }
    }
}
 
 ** 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.
 * @param tokenType
public void reverseIndex:(NSInteger)tokenType
{
    if ( tokenTypesToReverseIndex == nil ) {
        tokenTypesToReverseIndex = [ANTLRMap newANTLRMap];
    }
    else if ( tokenTypesToReverseIndex == INDEX_ALL ) {
        return;
    }
    tokenTypesToReverseIndex.add(new Integer(tokenType));
}
 
** Track the indicated token types in the reverse index. Set
 *  to INDEX_ALL to track all token types.
public void reverseIndex(Set tokenTypes) {
    tokenTypesToReverseIndex = tokenTypes;
}
 
 ** 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.
 *
 *  Return -1 if exact node pointer not in stream.
public int getNodeIndex(Object node) {
    //System.out.println("get "+node);
    if ( tokenTypeToStreamIndexesMap==nil ) {
        return getNodeIndexLinearly(node);
    }
    int tokenType = adaptor.getType(node);
    Integer tokenTypeI = new Integer(tokenType);
    ArrayList indexes = (ArrayList)tokenTypeToStreamIndexesMap.get(tokenTypeI);
    if ( indexes==nil ) {
        //System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node));
        return getNodeIndexLinearly(node);
    }
    for (int i = 0; i < indexes.size(); i++) {
        Integer streamIndexI = (Integer)indexes.get(i);
        Object n = get(streamIndexI.intValue());
        if ( n==node ) {
            //System.out.println("found in index; stream index = "+streamIndexI);
            return streamIndexI.intValue(); // found it!
        }
    }
    return -1;
}
 
*/

@synthesize adaptor;
@synthesize tokenNameToTypeMap;
@end