1// [The "BSD licence"]
2// Copyright (c) 2006-2007 Kay Roepke 2010 Alan Condit
3// All rights reserved.
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions
7// are met:
8// 1. Redistributions of source code must retain the above copyright
9//    notice, this list of conditions and the following disclaimer.
10// 2. Redistributions in binary form must reproduce the above copyright
11//    notice, this list of conditions and the following disclaimer in the
12//    documentation and/or other materials provided with the distribution.
13// 3. The name of the author may not be used to endorse or promote products
14//    derived from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27#import "ANTLRBaseTree.h"
28#import "ANTLRBaseTreeAdaptor.h"
29#import "ANTLRToken.h"
30// TODO: this shouldn't be here...but needed for invalidNode
31#import "AMutableArray.h"
32#import "ANTLRCommonTree.h"
33#import "ANTLRRuntimeException.h"
34#import "ANTLRError.h"
35
36#pragma mark - Navigation Nodes
37ANTLRTreeNavigationNodeDown *navigationNodeDown = nil;
38ANTLRTreeNavigationNodeUp *navigationNodeUp = nil;
39ANTLRTreeNavigationNodeEOF *navigationNodeEOF = nil;
40
41
42@implementation ANTLRBaseTree
43
44static id<ANTLRBaseTree> invalidNode = nil;
45
46#pragma mark ANTLRTree protocol conformance
47
48+ (id<ANTLRBaseTree>) INVALID_NODE
49{
50	if ( invalidNode == nil ) {
51		invalidNode = [[ANTLRCommonTree alloc] initWithTokenType:ANTLRTokenTypeInvalid];
52	}
53	return invalidNode;
54}
55
56+ (id<ANTLRBaseTree>) invalidNode
57{
58	if ( invalidNode == nil ) {
59		invalidNode = [[ANTLRCommonTree alloc] initWithTokenType:ANTLRTokenTypeInvalid];
60	}
61	return invalidNode;
62}
63
64+ newTree
65{
66    return [[ANTLRBaseTree alloc] init];
67}
68
69/** Create a new node from an existing node does nothing for ANTLRBaseTree
70 *  as there are no fields other than the children list, which cannot
71 *  be copied as the children are not considered part of this node.
72 */
73+ newTree:(id<ANTLRBaseTree>) node
74{
75    return [[ANTLRBaseTree alloc] initWith:(id<ANTLRBaseTree>) node];
76}
77
78- (id) init
79{
80    self = [super init];
81    if ( self != nil ) {
82        children = nil;
83        return self;
84    }
85    return nil;
86}
87
88- (id) initWith:(id<ANTLRBaseTree>)node
89{
90    self = [super init];
91    if ( self != nil ) {
92        // children = [[AMutableArray arrayWithCapacity:5] retain];
93        // [children addObject:node];
94        [self addChild:node];
95        return self;
96    }
97    return nil;
98}
99
100- (void) dealloc
101{
102#ifdef DEBUG_DEALLOC
103    NSLog( @"called dealloc in ANTLRBaseTree" );
104#endif
105	if ( children ) [children release];
106	[super dealloc];
107}
108
109- (id<ANTLRBaseTree>) getChild:(NSUInteger)i
110{
111    if ( children == nil || i >= [children count] ) {
112        return nil;
113    }
114    return (id<ANTLRBaseTree>)[children objectAtIndex:i];
115}
116
117/** Get the children internal List; note that if you directly mess with
118 *  the list, do so at your own risk.
119 */
120- (AMutableArray *) children
121{
122    return children;
123}
124
125- (void) setChildren:(AMutableArray *)anArray
126{
127    if ( children != anArray ) {
128        if ( children ) [children release];
129        if ( anArray ) [anArray retain];
130    }
131    children = anArray;
132}
133
134- (id<ANTLRBaseTree>) getFirstChildWithType:(NSInteger) aType
135{
136    for (NSUInteger i = 0; children != nil && i < [children count]; i++) {
137        id<ANTLRBaseTree> t = (id<ANTLRBaseTree>) [children objectAtIndex:i];
138        if ( t.type == aType ) {
139            return t;
140        }
141    }
142    return nil;
143}
144
145- (NSUInteger) getChildCount
146{
147    if ( children == nil ) {
148        return 0;
149    }
150    return [children count];
151}
152
153/** Add t as child of this node.
154 *
155 *  Warning: if t has no children, but child does
156 *  and child isNil then this routine moves children to t via
157 *  t.children = child.children; i.e., without copying the array.
158 */
159- (void) addChild:(id<ANTLRBaseTree>) t
160{
161    //System.out.println("add child "+t.toStringTree()+" "+self.toStringTree());
162    //System.out.println("existing children: "+children);
163    if ( t == nil ) {
164        return; // do nothing upon addChild(nil)
165    }
166    if ( self == (ANTLRBaseTree *)t )
167        @throw [ANTLRIllegalArgumentException newException:@"ANTLRBaseTree Can't add self to self as child"];
168    id<ANTLRBaseTree> childTree = (id<ANTLRBaseTree>) t;
169    if ( [childTree isNil] ) { // t is an empty node possibly with children
170        if ( children != nil && children == childTree.children ) {
171            @throw [ANTLRRuntimeException newException:@"ANTLRBaseTree add child list to itself"];
172        }
173        // just add all of childTree's children to this
174        if ( childTree.children != nil ) {
175            if ( children != nil ) { // must copy, this has children already
176                int n = [childTree.children count];
177                for ( int i = 0; i < n; i++) {
178                    id<ANTLRBaseTree> c = (id<ANTLRBaseTree>)[childTree.children objectAtIndex:i];
179                    [children addObject:c];
180                    // handle double-link stuff for each child of nil root
181                    [c setParent:(id<ANTLRBaseTree>)self];
182                    [c setChildIndex:[children count]-1];
183                }
184            }
185            else {
186                // no children for this but t has children; just set pointer
187                // call general freshener routine
188                children = childTree.children;
189                [self freshenParentAndChildIndexes];
190            }
191        }
192    }
193    else { // child is not nil (don't care about children)
194        if ( children == nil ) {
195            children = [[AMutableArray arrayWithCapacity:5] retain]; // create children list on demand
196        }
197        [children addObject:t];
198        [childTree setParent:(id<ANTLRBaseTree>)self];
199        [childTree setChildIndex:[children count]-1];
200    }
201    // System.out.println("now children are: "+children);
202}
203
204/** Add all elements of kids list as children of this node */
205- (void) addChildren:(AMutableArray *) kids
206{
207    for (NSUInteger i = 0; i < [kids count]; i++) {
208        id<ANTLRBaseTree> t = (id<ANTLRBaseTree>) [kids objectAtIndex:i];
209        [self addChild:t];
210    }
211}
212
213- (void) setChild:(NSUInteger) i With:(id<ANTLRBaseTree>)t
214{
215    if ( t == nil ) {
216        return;
217    }
218    if ( [t isNil] ) {
219        @throw [ANTLRIllegalArgumentException newException:@"ANTLRBaseTree Can't set single child to a list"];
220    }
221    if ( children == nil ) {
222        children = [[AMutableArray arrayWithCapacity:5] retain];
223    }
224    if ([children count] > i ) {
225        [children replaceObjectAtIndex:i withObject:t];
226    }
227    else {
228        [children insertObject:t atIndex:i];
229    }
230    [t setParent:(id<ANTLRBaseTree>)self];
231    [t setChildIndex:i];
232}
233
234- (id) deleteChild:(NSUInteger) idx
235{
236    if ( children == nil ) {
237        return nil;
238    }
239    id<ANTLRBaseTree> killed = (id<ANTLRBaseTree>)[children objectAtIndex:idx];
240    [children removeObjectAtIndex:idx];
241    // walk rest and decrement their child indexes
242    [self freshenParentAndChildIndexes:idx];
243    return killed;
244}
245
246/** Delete children from start to stop and replace with t even if t is
247 *  a list (nil-root ANTLRTree).  num of children can increase or decrease.
248 *  For huge child lists, inserting children can force walking rest of
249 *  children to set their childindex; could be slow.
250 */
251- (void) replaceChildrenFrom:(NSInteger)startChildIndex To:(NSInteger)stopChildIndex With:(id) t
252{
253    /*
254     System.out.println("replaceChildren "+startChildIndex+", "+stopChildIndex+
255     " with "+((ANTLRBaseTree)t).toStringTree());
256     System.out.println("in="+toStringTree());
257     */
258    if ( children == nil ) {
259        @throw [ANTLRIllegalArgumentException newException:@"ANTLRBaseTree Invalid Indexes; no children in list"];
260    }
261    int replacingHowMany = stopChildIndex - startChildIndex + 1;
262    int replacingWithHowMany;
263    id<ANTLRBaseTree> newTree = (id<ANTLRBaseTree>) t;
264    AMutableArray *newChildren = nil;
265    // normalize to a list of children to add: newChildren
266    if ( [newTree isNil] ) {
267        newChildren = newTree.children;
268    }
269    else {
270        newChildren = [AMutableArray arrayWithCapacity:5];
271        [newChildren addObject:newTree];
272    }
273    replacingWithHowMany = [newChildren count];
274    int numNewChildren = [newChildren count];
275    int delta = replacingHowMany - replacingWithHowMany;
276    // if same number of nodes, do direct replace
277    if ( delta == 0 ) {
278        int j = 0; // index into new children
279        for (int i=startChildIndex; i <= stopChildIndex; i++) {
280            id<ANTLRBaseTree> child = (id<ANTLRBaseTree>)[newChildren objectAtIndex:j];
281            [children replaceObjectAtIndex:i withObject:(id)child];
282            [child setParent:(id<ANTLRBaseTree>)self];
283            [child setChildIndex:i];
284            j++;
285        }
286    }
287    else if ( delta > 0 ) { // fewer new nodes than there were
288                            // set children and then delete extra
289        for (int j = 0; j < numNewChildren; j++) {
290            [children replaceObjectAtIndex:startChildIndex+j withObject:[newChildren objectAtIndex:j]];
291        }
292        int indexToDelete = startChildIndex+numNewChildren;
293        for (int c=indexToDelete; c<=stopChildIndex; c++) {
294            // delete same index, shifting everybody down each time
295            [children removeObjectAtIndex:indexToDelete];
296        }
297        [self freshenParentAndChildIndexes:startChildIndex];
298    }
299    else { // more new nodes than were there before
300           // fill in as many children as we can (replacingHowMany) w/o moving data
301        for (int j=0; j<replacingHowMany; j++) {
302            [children replaceObjectAtIndex:startChildIndex+j withObject:[newChildren objectAtIndex:j]];
303        }
304        //        int numToInsert = replacingWithHowMany-replacingHowMany;
305        for (int j=replacingHowMany; j<replacingWithHowMany; j++) {
306            [children insertObject:[newChildren objectAtIndex:j] atIndex:startChildIndex+j];
307        }
308        [self freshenParentAndChildIndexes:startChildIndex];
309    }
310    //System.out.println("out="+toStringTree());
311}
312
313/** Override in a subclass to change the impl of children list */
314- (AMutableArray *) createChildrenList
315{
316    return [AMutableArray arrayWithCapacity:5];
317}
318
319- (BOOL) isNil
320{
321    return NO;
322}
323
324/** Set the parent and child index values for all child of t */
325- (void) freshenParentAndChildIndexes
326{
327    [self freshenParentAndChildIndexes:0];
328}
329
330- (void) freshenParentAndChildIndexes:(NSInteger) offset
331{
332    int n = [self getChildCount];
333    for (int i = offset; i < n; i++) {
334        id<ANTLRBaseTree> child = (id<ANTLRBaseTree>)[self getChild:i];
335        [child setChildIndex:i];
336        [child setParent:(id<ANTLRBaseTree>)self];
337    }
338}
339
340- (void) sanityCheckParentAndChildIndexes
341{
342    [self sanityCheckParentAndChildIndexes:nil At:-1];
343}
344
345- (void) sanityCheckParentAndChildIndexes:(id<ANTLRBaseTree>)aParent At:(NSInteger) i
346{
347    if ( aParent != [self getParent] ) {
348        @throw [ANTLRIllegalStateException newException:[NSString stringWithFormat:@"parents don't match; expected %s found %s", aParent, [self getParent]]];
349    }
350    if ( i != [self getChildIndex] ) {
351        @throw [ANTLRIllegalStateException newException:[NSString stringWithFormat:@"child indexes don't match; expected %d found %d", i, [self getChildIndex]]];
352    }
353    int n = [self getChildCount];
354    for (int c = 0; c < n; c++) {
355        id<ANTLRBaseTree> child = (id<ANTLRBaseTree>)[self getChild:c];
356        [child sanityCheckParentAndChildIndexes:(id<ANTLRBaseTree>)self At:c];
357    }
358}
359
360/**  What is the smallest token index (indexing from 0) for this node
361 *   and its children?
362 */
363- (NSInteger) getTokenStartIndex
364{
365    return 0;
366}
367
368- (void) setTokenStartIndex:(NSInteger) anIndex
369{
370}
371
372/**  What is the largest token index (indexing from 0) for this node
373 *   and its children?
374 */
375- (NSInteger) getTokenStopIndex
376{
377    return 0;
378}
379
380- (void) setTokenStopIndex:(NSInteger) anIndex
381{
382}
383
384- (id<ANTLRBaseTree>) dupNode
385{
386    return nil;
387}
388
389
390/** ANTLRBaseTree doesn't track child indexes. */
391- (NSInteger) getChildIndex
392{
393    return 0;
394}
395
396- (void) setChildIndex:(NSInteger) anIndex
397{
398}
399
400/** ANTLRBaseTree doesn't track parent pointers. */
401- (id<ANTLRBaseTree>) getParent
402{
403    return nil;
404}
405
406- (void) setParent:(id<ANTLRBaseTree>) t
407{
408}
409
410/** Walk upwards looking for ancestor with this token type. */
411- (BOOL) hasAncestor:(NSInteger) ttype
412{
413    return([self getAncestor:ttype] != nil);
414}
415
416/** Walk upwards and get first ancestor with this token type. */
417- (id<ANTLRBaseTree>) getAncestor:(NSInteger) ttype
418{
419    id<ANTLRBaseTree> t = (id<ANTLRBaseTree>)self;
420    t = (id<ANTLRBaseTree>)[t getParent];
421    while ( t != nil ) {
422        if ( t.type == ttype )
423            return t;
424        t = (id<ANTLRBaseTree>)[t getParent];
425    }
426    return nil;
427}
428
429/** Return a list of all ancestors of this node.  The first node of
430 *  list is the root and the last is the parent of this node.
431 */
432- (AMutableArray *)getAncestors
433{
434    if ( [self getParent] == nil )
435        return nil;
436    AMutableArray *ancestors = [AMutableArray arrayWithCapacity:5];
437    id<ANTLRBaseTree> t = (id<ANTLRBaseTree>)self;
438    t = (id<ANTLRBaseTree>)[t getParent];
439    while ( t != nil ) {
440        [ancestors insertObject:t atIndex:0]; // insert at start
441        t = (id<ANTLRBaseTree>)[t getParent];
442    }
443    return ancestors;
444}
445
446- (NSInteger)type
447{
448    return ANTLRTokenTypeInvalid;
449}
450
451- (NSString *)text
452{
453    return nil;
454}
455
456- (NSUInteger)line
457{
458    return 0;
459}
460
461- (NSUInteger)charPositionInLine
462{
463    return 0;
464}
465
466- (void) setCharPositionInLine:(NSUInteger) pos
467{
468}
469
470#pragma mark Copying
471
472     // the children themselves are not copied here!
473- (id) copyWithZone:(NSZone *)aZone
474{
475    id<ANTLRBaseTree> theCopy = [[[self class] allocWithZone:aZone] init];
476    [theCopy addChildren:self.children];
477    return theCopy;
478}
479
480- (id) deepCopy 					// performs a deepCopyWithZone: with the default zone
481{
482    return [self deepCopyWithZone:NULL];
483}
484
485- (id) deepCopyWithZone:(NSZone *)aZone
486{
487    id<ANTLRBaseTree> theCopy = [self copyWithZone:aZone];
488
489    if ( [theCopy.children count] )
490        [theCopy.children removeAllObjects];
491    AMutableArray *childrenCopy = theCopy.children;
492    for (id loopItem in children) {
493        id<ANTLRBaseTree> childCopy = [loopItem deepCopyWithZone:aZone];
494        [theCopy addChild:childCopy];
495    }
496    if ( childrenCopy ) [childrenCopy release];
497    return theCopy;
498}
499
500- (NSString *) treeDescription
501{
502    if ( children == nil || [children count] == 0 ) {
503        return [self description];
504    }
505    NSMutableString *buf = [NSMutableString stringWithCapacity:[children count]];
506    if ( ![self isNil] ) {
507        [buf appendString:@"("];
508        [buf appendString:[self toString]];
509        [buf appendString:@" "];
510    }
511    for (int i = 0; children != nil && i < [children count]; i++) {
512        id<ANTLRBaseTree> t = (id<ANTLRBaseTree>)[children objectAtIndex:i];
513        if ( i > 0 ) {
514            [buf appendString:@" "];
515        }
516        [buf appendString:[(id<ANTLRBaseTree>)t toStringTree]];
517    }
518    if ( ![self isNil] ) {
519        [buf appendString:@")"];
520    }
521    return buf;
522}
523
524/** Print out a whole tree not just a node */
525- (NSString *) toStringTree
526{
527    return [self treeDescription];
528}
529
530- (NSString *) description
531{
532    return nil;
533}
534
535/** Override to say how a node (not a tree) should look as text */
536- (NSString *) toString
537{
538    return nil;
539}
540
541@synthesize children;
542@synthesize anException;
543
544@end
545
546#pragma mark -
547
548@implementation ANTLRTreeNavigationNode
549- (id)init
550{
551    self = (ANTLRTreeNavigationNode *)[super init];
552    return self;
553}
554
555- (id) copyWithZone:(NSZone *)aZone
556{
557	return nil;
558}
559@end
560
561@implementation ANTLRTreeNavigationNodeDown
562+ (ANTLRTreeNavigationNodeDown *) getNavigationNodeDown
563{
564    if ( navigationNodeDown == nil )
565        navigationNodeDown = [[ANTLRTreeNavigationNodeDown alloc] init];
566    return navigationNodeDown;
567}
568
569- (id)init
570{
571    self = [super init];
572    return self;
573}
574
575- (NSInteger) tokenType { return ANTLRTokenTypeDOWN; }
576- (NSString *) description { return @"DOWN"; }
577@end
578
579@implementation ANTLRTreeNavigationNodeUp
580+ (ANTLRTreeNavigationNodeUp *) getNavigationNodeUp
581{
582    if ( navigationNodeUp == nil )
583        navigationNodeUp = [[ANTLRTreeNavigationNodeUp alloc] init];
584    return navigationNodeUp;
585}
586
587
588- (id)init
589{
590    self = [super init];
591    return self;
592}
593
594- (NSInteger) tokenType { return ANTLRTokenTypeUP; }
595- (NSString *) description { return @"UP"; }
596@end
597
598@implementation ANTLRTreeNavigationNodeEOF
599+ (ANTLRTreeNavigationNodeEOF *) getNavigationNodeEOF
600{
601    if ( navigationNodeEOF == nil )
602        navigationNodeEOF = [[ANTLRTreeNavigationNodeEOF alloc] init];
603    return navigationNodeEOF;
604}
605
606- (id)init
607{
608    self = [super init];
609    return self;
610}
611
612- (NSInteger) tokenType { return ANTLRTokenTypeEOF; }
613- (NSString *) description { return @"EOF"; }
614
615@end
616
617