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 "UnbufferedCommonTreeNodeStream.h" 29#import "UnbufferedCommonTreeNodeStreamState.h" 30#import "BaseTree.h" 31#import "Token.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:(CommonTree *)theTree 52{ 53 return [self initWithTree:theTree treeAdaptor:nil]; 54} 55 56- (id) initWithTree:(CommonTree *)theTree treeAdaptor:(CommonTreeAdaptor *)theAdaptor 57{ 58 if ((self = [super init]) != nil) { 59 [self setRoot:theTree]; 60 if ( theAdaptor == nil ) 61 [self setTreeAdaptor:[CommonTreeAdaptor newTreeAdaptor]]; 62 else 63 [self setTreeAdaptor:theAdaptor]; 64 nodeStack = [[NSMutableArray arrayWithCapacity:5] retain]; 65 indexStack = [[NSMutableArray arrayWithCapacity:5] retain]; 66 markers = [[PtrBuffer newPtrBufferWithLen: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 BaseTree.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<TreeAdaptor>) getTreeAdaptor; 127{ 128 return treeAdaptor; 129} 130 131- (void)setTreeAdaptor:(id<TreeAdaptor>)aTreeAdaptor 132{ 133 if (treeAdaptor != aTreeAdaptor) { 134 [aTreeAdaptor retain]; 135 [treeAdaptor release]; 136 treeAdaptor = aTreeAdaptor; 137 } 138} 139 140- (id<TokenStream>) getTokenStream 141{ 142 return tokenStream; 143} 144 145- (void) setTokenStream:(id<TokenStream>)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 CommonTree *node = [self LT:i]; 192 if (!node) 193 return TokenTypeInvalid; 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<BaseTree>)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 = [[TreeNavigationNodeEOF 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- (CommonTree *) handleRootNode 343{ 344 CommonTree *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- (CommonTree *) visitChild:(NSInteger)childNumber 358{ 359 CommonTree *node = nil; 360 361 [nodeStack addObject:currentNode]; 362 [indexStack addObject:[NSNumber numberWithInt:childNumber]]; 363 if (childNumber == 0 && ![currentNode isNil]) 364 [self addNavigationNodeWithType:TokenTypeDOWN]; 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 = (CommonTree *)[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:TokenTypeUP]; 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 TokenTypeDOWN: { 400 if (navigationNodeDown == nil) { 401 navigationNodeDown = [[TreeNavigationNodeDown alloc] init]; 402 } 403 [self addLookahead:navigationNodeDown]; 404 break; 405 } 406 case TokenTypeUP: { 407 if (navigationNodeUp == nil) { 408 navigationNodeUp = [[TreeNavigationNodeUp alloc] init]; 409 } 410 [self addLookahead:navigationNodeUp]; 411 break; 412 } 413 } 414} 415 416#pragma mark Accessors 417- (CommonTree *) root 418{ 419 return root; 420} 421 422- (void) setRoot: (CommonTree *) aRoot 423{ 424 if (root != aRoot) { 425 [aRoot retain]; 426 [root release]; 427 root = aRoot; 428 } 429} 430 431@end 432 433