Home | History | Annotate | Download | only in Framework 
      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 
     28 #import "ANTLRUnbufferedCommonTreeNodeStream.h"
     29 #import "ANTLRUnbufferedCommonTreeNodeStreamState.h"
     30 #import "ANTLRBaseTree.h"
     31 #import "ANTLRToken.h"
     32 
     33 #define INITIAL_LOOKAHEAD_BUFFER_SIZE 5
     34 @implementation ANTLRUnbufferedCommonTreeNodeStream
     35 
     36 @synthesize root;
     37 @synthesize currentNode;
     38 @synthesize previousNode;
     39 @synthesize treeAdaptor;
     40 @synthesize tokenStream;
     41 @synthesize nodeStack;
     42 @synthesize indexStack;
     43 @synthesize markers;
     44 @synthesize lastMarker;
     45 @synthesize currentChildIndex;
     46 @synthesize absoluteNodeIndex;
     47 @synthesize lookahead;
     48 @synthesize head;
     49 @synthesize tail;
     50 
     51 - (id) initWithTree:(ANTLRCommonTree *)theTree
     52 {
     53 	return [self initWithTree:theTree treeAdaptor:nil];
     54 }
     55 
     56 - (id) initWithTree:(ANTLRCommonTree *)theTree treeAdaptor:(ANTLRCommonTreeAdaptor *)theAdaptor
     57 {
     58 	if ((self = [super init]) != nil) {
     59 		[self setRoot:theTree];
     60 		if ( theAdaptor == nil ) 
     61 			[self setTreeAdaptor:[ANTLRCommonTreeAdaptor newTreeAdaptor]];
     62 		else
     63 			[self setTreeAdaptor:theAdaptor];
     64 		nodeStack = [[NSMutableArray arrayWithCapacity:5] retain];
     65 		indexStack = [[NSMutableArray arrayWithCapacity:5] retain];
     66 		markers = [[ANTLRPtrBuffer newANTLRPtrBufferWithLen:100] retain];
     67         // [markers insertObject:[NSNull null] atIndex:0];	// markers is one based - maybe fix this later
     68 		lookahead = [NSMutableArray arrayWithCapacity:INITIAL_LOOKAHEAD_BUFFER_SIZE];	// lookahead is filled with [NSNull null] in -reset
     69         [lookahead retain];
     70 		[self reset];
     71 	}
     72 	return self;
     73 }
     74 
     75 - (void) dealloc
     76 {
     77 	[self setRoot:nil];
     78 	[self setTreeAdaptor:nil];
     79 	
     80 	[nodeStack release];	nodeStack = nil;
     81 	[indexStack release];	indexStack = nil;
     82 	[markers release];		markers = nil;
     83 	[lookahead release];	lookahead = nil;
     84 	
     85 	[super dealloc];
     86 }
     87 
     88 - (void) reset
     89 {
     90 	currentNode = root;
     91 	previousNode = nil;
     92 	currentChildIndex = -1;
     93 	absoluteNodeIndex = -1;
     94 	head = tail = 0;
     95 	[nodeStack removeAllObjects];
     96 	[indexStack removeAllObjects];
     97 	[markers removeAllObjects];
     98     // [markers insertObject:[NSNull null] atIndex:0];	// markers is one based - maybe fix this later
     99 	[lookahead removeAllObjects];
    100 	// TODO: this is not ideal, but works for now. optimize later
    101 	int i;
    102 	for (i = 0; i < INITIAL_LOOKAHEAD_BUFFER_SIZE; i++)
    103 		[lookahead addObject:[NSNull null]];
    104 }
    105 
    106 
    107 #pragma mark ANTLRTreeNodeStream conformance
    108 
    109 - (id) LT:(NSInteger)k
    110 {
    111 	if (k == -1)
    112 		return previousNode;
    113 	if (k < 0)
    114 		@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-LT: looking back more than one node unsupported for unbuffered streams" userInfo:nil];
    115 	if (k == 0)
    116 		return ANTLRBaseTree.INVALID_NODE;
    117 	[self fillBufferWithLookahead:k];
    118 	return [lookahead objectAtIndex:(head+k-1) % [lookahead count]];
    119 }
    120 
    121 - (id) treeSource
    122 {
    123 	return [self root];
    124 }
    125 
    126 - (id<ANTLRTreeAdaptor>) getTreeAdaptor;
    127 {
    128 	return treeAdaptor;
    129 }
    130 
    131 - (void)setTreeAdaptor:(id<ANTLRTreeAdaptor>)aTreeAdaptor
    132 {
    133     if (treeAdaptor != aTreeAdaptor) {
    134         [aTreeAdaptor retain];
    135         [treeAdaptor release];
    136         treeAdaptor = aTreeAdaptor;
    137     }
    138 }
    139 
    140 - (id<ANTLRTokenStream>) getTokenStream
    141 {
    142 	return tokenStream;
    143 }
    144 
    145 - (void) setTokenStream:(id<ANTLRTokenStream>)aTokenStream
    146 {
    147 	if (tokenStream != aTokenStream) {
    148 		[tokenStream release];
    149 		[aTokenStream retain];
    150 		tokenStream = aTokenStream;
    151 	}
    152 }
    153 
    154 - (void) setUsesUniqueNavigationNodes:(BOOL)flag
    155 {
    156 	shouldUseUniqueNavigationNodes = flag;
    157 }
    158 
    159 - (id) nodeAtIndex:(NSUInteger) idx
    160 {
    161 	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-nodeAtIndex: unsupported for unbuffered streams" userInfo:nil];
    162 }
    163 
    164 - (NSString *) toString
    165 {
    166 	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toString unsupported for unbuffered streams" userInfo:nil];
    167 }
    168 
    169 - (NSString *) toStringWithRange:(NSRange) aRange
    170 {
    171 	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toString: unsupported for unbuffered streams" userInfo:nil];
    172 }
    173 
    174 - (NSString *) toStringFromNode:(id)startNode ToNode:(id)stopNode
    175 {
    176 	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toStringFromNode:toNode: unsupported for unbuffered streams" userInfo:nil];
    177 }
    178 
    179 #pragma mark ANTLRIntStream conformance
    180 
    181 - (void) consume
    182 {
    183 	[self fillBufferWithLookahead:1];
    184 	absoluteNodeIndex++;
    185 	previousNode = [lookahead objectAtIndex:head];
    186 	head = (head+1) % [lookahead count];
    187 }
    188 
    189 - (NSInteger) LA:(NSUInteger) i
    190 {
    191 	ANTLRCommonTree *node = [self LT:i];
    192 	if (!node) 
    193 		return ANTLRTokenTypeInvalid;
    194 	int ttype = [node getType];
    195 	return ttype;
    196 }
    197 
    198 - (NSUInteger) mark
    199 {
    200 	ANTLRUnbufferedCommonTreeNodeStreamState *state = [[[ANTLRUnbufferedCommonTreeNodeStreamState alloc] init] retain];
    201 	[state setCurrentNode:currentNode];
    202 	[state setPreviousNode:previousNode];
    203 	[state setIndexStackSize:[indexStack count]];
    204 	[state setNodeStackSize:[nodeStack count]];
    205 	[state setCurrentChildIndex:currentChildIndex];
    206 	[state setAbsoluteNodeIndex:absoluteNodeIndex];
    207 	unsigned int lookaheadSize = [self lookaheadSize];
    208 	unsigned int k;
    209 	for ( k = 0; k < lookaheadSize; k++) {
    210 		[state addToLookahead:[self LT:k+1]];
    211 	}
    212 	[markers addObject:state];
    213 	//[state release];
    214 	return [markers count];
    215 }
    216 
    217 - (NSUInteger) getIndex
    218 {
    219 	return absoluteNodeIndex + 1;
    220 }
    221 
    222 - (void) rewind:(NSUInteger) marker
    223 {
    224 	if ( [markers count] < marker ) {
    225 		return;
    226 	}
    227 	ANTLRUnbufferedCommonTreeNodeStreamState *state = [markers objectAtIndex:marker];
    228 	[markers removeObjectAtIndex:marker];
    229 
    230 	absoluteNodeIndex = [state absoluteNodeIndex];
    231 	currentChildIndex = [state currentChildIndex];
    232 	currentNode = [state currentNode];
    233 	previousNode = [state previousNode];
    234 	// drop node and index stacks back to old size
    235 	[nodeStack removeObjectsInRange:NSMakeRange([state nodeStackSize], [nodeStack count]-[state nodeStackSize])];
    236 	[indexStack removeObjectsInRange:NSMakeRange([state indexStackSize], [indexStack count]-[state indexStackSize])];
    237 	
    238 	head = tail = 0; // wack lookahead buffer and then refill
    239 	[lookahead release];
    240 	lookahead = [[NSMutableArray alloc] initWithArray:[state lookahead]];
    241 	tail = [lookahead count];
    242 	// make some room after the restored lookahead, so that the above line is not a bug ;)
    243 	// this also ensures that a subsequent -addLookahead: will not immediately need to resize the buffer
    244 	[lookahead addObjectsFromArray:[NSArray arrayWithObjects:[NSNull null], [NSNull null], [NSNull null], [NSNull null], [NSNull null], nil]];
    245 }
    246 
    247 - (void) rewind
    248 {
    249 	[self rewind:[markers count]];
    250 }
    251 
    252 - (void) release:(NSUInteger) marker
    253 {
    254 	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-release: unsupported for unbuffered streams" userInfo:nil];
    255 }
    256 
    257 - (void) seek:(NSUInteger) anIndex
    258 {
    259 	if ( anIndex < (NSUInteger) index )
    260 		@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-seek: backwards unsupported for unbuffered streams" userInfo:nil];
    261 	while ( (NSUInteger) index < anIndex ) {
    262 		[self consume];
    263 	}
    264 }
    265 
    266 - (NSUInteger) size;
    267 {
    268 	return absoluteNodeIndex + 1;	// not entirely correct, but cheap.
    269 }
    270 
    271 
    272 #pragma mark Lookahead Handling
    273 - (void) addLookahead:(id<ANTLRBaseTree>)aNode
    274 {
    275 	[lookahead replaceObjectAtIndex:tail withObject:aNode];
    276 	tail = (tail+1) % [lookahead count];
    277 	
    278 	if ( tail == head ) {
    279 		NSMutableArray *newLookahead = [[[NSMutableArray alloc] initWithCapacity:[lookahead count]*2] retain];
    280 		
    281 		NSRange headRange = NSMakeRange(head, [lookahead count]-head);
    282 		NSRange tailRange = NSMakeRange(0, tail);
    283 		
    284 		[newLookahead addObjectsFromArray:[lookahead objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:headRange]]];
    285 		[newLookahead addObjectsFromArray:[lookahead objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:tailRange]]];
    286 		
    287 		unsigned int i;
    288 		unsigned int lookaheadCount = [newLookahead count];
    289 		for (i = 0; i < lookaheadCount; i++)
    290 			[newLookahead addObject:[NSNull null]];
    291 		[lookahead release];
    292 		lookahead = newLookahead;
    293 		
    294 		head = 0;
    295 		tail = lookaheadCount;	// tail is the location the _next_ lookahead node will end up in, not the last element's idx itself!
    296 	}
    297 	
    298 }
    299 
    300 - (NSUInteger) lookaheadSize
    301 {
    302 	return tail < head
    303 		? ([lookahead count] - head + tail) 
    304 		: (tail - head);
    305 }
    306 
    307 - (void) fillBufferWithLookahead:(NSInteger)k
    308 {
    309 	unsigned int n = [self lookaheadSize];
    310 	unsigned int i;
    311 	id lookaheadObject = self; // any valid object would do.
    312 	for (i=1; i <= k-n && lookaheadObject != nil; i++) {
    313 		lookaheadObject = [self nextObject];
    314 	}
    315 }
    316 
    317 - (id) nextObject
    318 {
    319 	// NOTE: this could/should go into an NSEnumerator subclass for treenode streams.
    320 	if (currentNode == nil) {
    321         if ( navigationNodeEOF == nil ) {
    322             navigationNodeEOF = [[ANTLRTreeNavigationNodeEOF alloc] init];
    323         }
    324 		[self addLookahead:navigationNodeEOF];
    325 		return nil;
    326 	}
    327 	if (currentChildIndex == -1) {
    328 		return [self handleRootNode];
    329 	}
    330 	if (currentChildIndex < (NSInteger)[currentNode getChildCount]) {
    331 		return [self visitChild:currentChildIndex];
    332 	}
    333 	[self walkBackToMostRecentNodeWithUnvisitedChildren];
    334 	if (currentNode != nil) {
    335 		return [self visitChild:currentChildIndex];
    336 	}
    337 	
    338 	return nil;
    339 }	
    340 
    341 #pragma mark Node visiting
    342 - (ANTLRCommonTree *) handleRootNode
    343 {
    344 	ANTLRCommonTree *node = currentNode;
    345 	currentChildIndex = 0;
    346 	if ([node isNil]) {
    347 		node = [self visitChild:currentChildIndex];
    348 	} else {
    349 		[self addLookahead:node];
    350 		if ([currentNode getChildCount] == 0) {
    351 			currentNode = nil;
    352 		}
    353 	}
    354 	return node;
    355 }
    356 
    357 - (ANTLRCommonTree *) visitChild:(NSInteger)childNumber
    358 {
    359 	ANTLRCommonTree *node = nil;
    360 	
    361 	[nodeStack addObject:currentNode];
    362 	[indexStack addObject:[NSNumber numberWithInt:childNumber]];
    363 	if (childNumber == 0 && ![currentNode isNil])
    364 		[self addNavigationNodeWithType:ANTLRTokenTypeDOWN];
    365 
    366 	currentNode = [currentNode getChild:childNumber];
    367 	currentChildIndex = 0;
    368 	node = currentNode;  // record node to return
    369 	[self addLookahead:node];
    370 	[self walkBackToMostRecentNodeWithUnvisitedChildren];
    371 	return node;
    372 }
    373 
    374 - (void) walkBackToMostRecentNodeWithUnvisitedChildren
    375 {
    376 	while (currentNode != nil && currentChildIndex >= (NSInteger)[currentNode getChildCount])
    377 	{
    378 		currentNode = (ANTLRCommonTree *)[nodeStack lastObject];
    379 		[nodeStack removeLastObject];
    380 		currentChildIndex = [(NSNumber *)[indexStack lastObject] intValue];
    381 		[indexStack removeLastObject];
    382 		currentChildIndex++; // move to next child
    383 		if (currentChildIndex >= (NSInteger)[currentNode getChildCount]) {
    384 			if (![currentNode isNil]) {
    385 				[self addNavigationNodeWithType:ANTLRTokenTypeUP];
    386 			}
    387 			if (currentNode == root) { // we done yet?
    388 				currentNode = nil;
    389 			}
    390 		}
    391 	}
    392 	
    393 }
    394 
    395 - (void) addNavigationNodeWithType:(NSInteger)tokenType
    396 {
    397 	// TODO: this currently ignores shouldUseUniqueNavigationNodes.
    398 	switch (tokenType) {
    399 		case ANTLRTokenTypeDOWN: {
    400             if (navigationNodeDown == nil) {
    401                 navigationNodeDown = [[ANTLRTreeNavigationNodeDown alloc] init];
    402             }
    403 			[self addLookahead:navigationNodeDown];
    404 			break;
    405 		}
    406 		case ANTLRTokenTypeUP: {
    407             if (navigationNodeUp == nil) {
    408                 navigationNodeUp = [[ANTLRTreeNavigationNodeUp alloc] init];
    409             }
    410 			[self addLookahead:navigationNodeUp];
    411 			break;
    412 		}
    413 	}
    414 }
    415 
    416 #pragma mark Accessors
    417 - (ANTLRCommonTree *) root
    418 {
    419     return root; 
    420 }
    421 
    422 - (void) setRoot: (ANTLRCommonTree *) aRoot
    423 {
    424     if (root != aRoot) {
    425         [aRoot retain];
    426         [root release];
    427         root = aRoot;
    428     }
    429 }
    430 
    431 @end
    432 
    433