ObjC/Framework/UnbufferedCommonTreeNodeStream.m

// [The "BSD licence"]
// Copyright (c) 2006-2007 Kay Roepke 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 "UnbufferedCommonTreeNodeStream.h"
#import "UnbufferedCommonTreeNodeStreamState.h"
#import "BaseTree.h"
#import "Token.h"

#define INITIAL_LOOKAHEAD_BUFFER_SIZE 5
@implementation ANTLRUnbufferedCommonTreeNodeStream

@synthesize root;
@synthesize currentNode;
@synthesize previousNode;
@synthesize treeAdaptor;
@synthesize tokenStream;
@synthesize nodeStack;
@synthesize indexStack;
@synthesize markers;
@synthesize lastMarker;
@synthesize currentChildIndex;
@synthesize absoluteNodeIndex;
@synthesize lookahead;
@synthesize head;
@synthesize tail;

- (id) initWithTree:(CommonTree *)theTree
{
	return [self initWithTree:theTree treeAdaptor:nil];
}

- (id) initWithTree:(CommonTree *)theTree treeAdaptor:(CommonTreeAdaptor *)theAdaptor
{
	if ((self = [super init]) != nil) {
		[self setRoot:theTree];
		if ( theAdaptor == nil )
			[self setTreeAdaptor:[CommonTreeAdaptor newTreeAdaptor]];
		else
			[self setTreeAdaptor:theAdaptor];
		nodeStack = [[NSMutableArray arrayWithCapacity:5] retain];
		indexStack = [[NSMutableArray arrayWithCapacity:5] retain];
		markers = [[PtrBuffer newPtrBufferWithLen:100] retain];
        // [markers insertObject:[NSNull null] atIndex:0];	// markers is one based - maybe fix this later
		lookahead = [NSMutableArray arrayWithCapacity:INITIAL_LOOKAHEAD_BUFFER_SIZE];	// lookahead is filled with [NSNull null] in -reset
        [lookahead retain];
		[self reset];
	}
	return self;
}

- (void) dealloc
{
	[self setRoot:nil];
	[self setTreeAdaptor:nil];

	[nodeStack release];	nodeStack = nil;
	[indexStack release];	indexStack = nil;
	[markers release];		markers = nil;
	[lookahead release];	lookahead = nil;

	[super dealloc];
}

- (void) reset
{
	currentNode = root;
	previousNode = nil;
	currentChildIndex = -1;
	absoluteNodeIndex = -1;
	head = tail = 0;
	[nodeStack removeAllObjects];
	[indexStack removeAllObjects];
	[markers removeAllObjects];
    // [markers insertObject:[NSNull null] atIndex:0];	// markers is one based - maybe fix this later
	[lookahead removeAllObjects];
	// TODO: this is not ideal, but works for now. optimize later
	int i;
	for (i = 0; i < INITIAL_LOOKAHEAD_BUFFER_SIZE; i++)
		[lookahead addObject:[NSNull null]];
}


#pragma mark ANTLRTreeNodeStream conformance

- (id) LT:(NSInteger)k
{
	if (k == -1)
		return previousNode;
	if (k < 0)
		@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-LT: looking back more than one node unsupported for unbuffered streams" userInfo:nil];
	if (k == 0)
		return BaseTree.INVALID_NODE;
	[self fillBufferWithLookahead:k];
	return [lookahead objectAtIndex:(head+k-1) % [lookahead count]];
}

- (id) treeSource
{
	return [self root];
}

- (id<TreeAdaptor>) getTreeAdaptor;
{
	return treeAdaptor;
}

- (void)setTreeAdaptor:(id<TreeAdaptor>)aTreeAdaptor
{
    if (treeAdaptor != aTreeAdaptor) {
        [aTreeAdaptor retain];
        [treeAdaptor release];
        treeAdaptor = aTreeAdaptor;
    }
}

- (id<TokenStream>) getTokenStream
{
	return tokenStream;
}

- (void) setTokenStream:(id<TokenStream>)aTokenStream
{
	if (tokenStream != aTokenStream) {
		[tokenStream release];
		[aTokenStream retain];
		tokenStream = aTokenStream;
	}
}

- (void) setUsesUniqueNavigationNodes:(BOOL)flag
{
	shouldUseUniqueNavigationNodes = flag;
}

- (id) nodeAtIndex:(NSUInteger) idx
{
	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-nodeAtIndex: unsupported for unbuffered streams" userInfo:nil];
}

- (NSString *) toString
{
	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toString unsupported for unbuffered streams" userInfo:nil];
}

- (NSString *) toStringWithRange:(NSRange) aRange
{
	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toString: unsupported for unbuffered streams" userInfo:nil];
}

- (NSString *) toStringFromNode:(id)startNode ToNode:(id)stopNode
{
	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-toStringFromNode:toNode: unsupported for unbuffered streams" userInfo:nil];
}

#pragma mark ANTLRIntStream conformance

- (void) consume
{
	[self fillBufferWithLookahead:1];
	absoluteNodeIndex++;
	previousNode = [lookahead objectAtIndex:head];
	head = (head+1) % [lookahead count];
}

- (NSInteger) LA:(NSUInteger) i
{
	CommonTree *node = [self LT:i];
	if (!node)
		return TokenTypeInvalid;
	int ttype = [node getType];
	return ttype;
}

- (NSUInteger) mark
{
	ANTLRUnbufferedCommonTreeNodeStreamState *state = [[[ANTLRUnbufferedCommonTreeNodeStreamState alloc] init] retain];
	[state setCurrentNode:currentNode];
	[state setPreviousNode:previousNode];
	[state setIndexStackSize:[indexStack count]];
	[state setNodeStackSize:[nodeStack count]];
	[state setCurrentChildIndex:currentChildIndex];
	[state setAbsoluteNodeIndex:absoluteNodeIndex];
	unsigned int lookaheadSize = [self lookaheadSize];
	unsigned int k;
	for ( k = 0; k < lookaheadSize; k++) {
		[state addToLookahead:[self LT:k+1]];
	}
	[markers addObject:state];
	//[state release];
	return [markers count];
}

- (NSUInteger) getIndex
{
	return absoluteNodeIndex + 1;
}

- (void) rewind:(NSUInteger) marker
{
	if ( [markers count] < marker ) {
		return;
	}
	ANTLRUnbufferedCommonTreeNodeStreamState *state = [markers objectAtIndex:marker];
	[markers removeObjectAtIndex:marker];

	absoluteNodeIndex = [state absoluteNodeIndex];
	currentChildIndex = [state currentChildIndex];
	currentNode = [state currentNode];
	previousNode = [state previousNode];
	// drop node and index stacks back to old size
	[nodeStack removeObjectsInRange:NSMakeRange([state nodeStackSize], [nodeStack count]-[state nodeStackSize])];
	[indexStack removeObjectsInRange:NSMakeRange([state indexStackSize], [indexStack count]-[state indexStackSize])];

	head = tail = 0; // wack lookahead buffer and then refill
	[lookahead release];
	lookahead = [[NSMutableArray alloc] initWithArray:[state lookahead]];
	tail = [lookahead count];
	// make some room after the restored lookahead, so that the above line is not a bug ;)
	// this also ensures that a subsequent -addLookahead: will not immediately need to resize the buffer
	[lookahead addObjectsFromArray:[NSArray arrayWithObjects:[NSNull null], [NSNull null], [NSNull null], [NSNull null], [NSNull null], nil]];
}

- (void) rewind
{
	[self rewind:[markers count]];
}

- (void) release:(NSUInteger) marker
{
	@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-release: unsupported for unbuffered streams" userInfo:nil];
}

- (void) seek:(NSUInteger) anIndex
{
	if ( anIndex < (NSUInteger) index )
		@throw [NSException exceptionWithName:@"ANTLRTreeException" reason:@"-seek: backwards unsupported for unbuffered streams" userInfo:nil];
	while ( (NSUInteger) index < anIndex ) {
		[self consume];
	}
}

- (NSUInteger) size;
{
	return absoluteNodeIndex + 1;	// not entirely correct, but cheap.
}


#pragma mark Lookahead Handling
- (void) addLookahead:(id<BaseTree>)aNode
{
	[lookahead replaceObjectAtIndex:tail withObject:aNode];
	tail = (tail+1) % [lookahead count];

	if ( tail == head ) {
		NSMutableArray *newLookahead = [[[NSMutableArray alloc] initWithCapacity:[lookahead count]*2] retain];

		NSRange headRange = NSMakeRange(head, [lookahead count]-head);
		NSRange tailRange = NSMakeRange(0, tail);

		[newLookahead addObjectsFromArray:[lookahead objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:headRange]]];
		[newLookahead addObjectsFromArray:[lookahead objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:tailRange]]];

		unsigned int i;
		unsigned int lookaheadCount = [newLookahead count];
		for (i = 0; i < lookaheadCount; i++)
			[newLookahead addObject:[NSNull null]];
		[lookahead release];
		lookahead = newLookahead;

		head = 0;
		tail = lookaheadCount;	// tail is the location the _next_ lookahead node will end up in, not the last element's idx itself!
	}

}

- (NSUInteger) lookaheadSize
{
	return tail < head
		? ([lookahead count] - head + tail)
		: (tail - head);
}

- (void) fillBufferWithLookahead:(NSInteger)k
{
	unsigned int n = [self lookaheadSize];
	unsigned int i;
	id lookaheadObject = self; // any valid object would do.
	for (i=1; i <= k-n && lookaheadObject != nil; i++) {
		lookaheadObject = [self nextObject];
	}
}

- (id) nextObject
{
	// NOTE: this could/should go into an NSEnumerator subclass for treenode streams.
	if (currentNode == nil) {
        if ( navigationNodeEOF == nil ) {
            navigationNodeEOF = [[TreeNavigationNodeEOF alloc] init];
        }
		[self addLookahead:navigationNodeEOF];
		return nil;
	}
	if (currentChildIndex == -1) {
		return [self handleRootNode];
	}
	if (currentChildIndex < (NSInteger)[currentNode getChildCount]) {
		return [self visitChild:currentChildIndex];
	}
	[self walkBackToMostRecentNodeWithUnvisitedChildren];
	if (currentNode != nil) {
		return [self visitChild:currentChildIndex];
	}

	return nil;
}

#pragma mark Node visiting
- (CommonTree *) handleRootNode
{
	CommonTree *node = currentNode;
	currentChildIndex = 0;
	if ([node isNil]) {
		node = [self visitChild:currentChildIndex];
	} else {
		[self addLookahead:node];
		if ([currentNode getChildCount] == 0) {
			currentNode = nil;
		}
	}
	return node;
}

- (CommonTree *) visitChild:(NSInteger)childNumber
{
	CommonTree *node = nil;

	[nodeStack addObject:currentNode];
	[indexStack addObject:[NSNumber numberWithInt:childNumber]];
	if (childNumber == 0 && ![currentNode isNil])
		[self addNavigationNodeWithType:TokenTypeDOWN];

	currentNode = [currentNode getChild:childNumber];
	currentChildIndex = 0;
	node = currentNode;  // record node to return
	[self addLookahead:node];
	[self walkBackToMostRecentNodeWithUnvisitedChildren];
	return node;
}

- (void) walkBackToMostRecentNodeWithUnvisitedChildren
{
	while (currentNode != nil && currentChildIndex >= (NSInteger)[currentNode getChildCount])
	{
		currentNode = (CommonTree *)[nodeStack lastObject];
		[nodeStack removeLastObject];
		currentChildIndex = [(NSNumber *)[indexStack lastObject] intValue];
		[indexStack removeLastObject];
		currentChildIndex++; // move to next child
		if (currentChildIndex >= (NSInteger)[currentNode getChildCount]) {
			if (![currentNode isNil]) {
				[self addNavigationNodeWithType:TokenTypeUP];
			}
			if (currentNode == root) { // we done yet?
				currentNode = nil;
			}
		}
	}

}

- (void) addNavigationNodeWithType:(NSInteger)tokenType
{
	// TODO: this currently ignores shouldUseUniqueNavigationNodes.
	switch (tokenType) {
		case TokenTypeDOWN: {
            if (navigationNodeDown == nil) {
                navigationNodeDown = [[TreeNavigationNodeDown alloc] init];
            }
			[self addLookahead:navigationNodeDown];
			break;
		}
		case TokenTypeUP: {
            if (navigationNodeUp == nil) {
                navigationNodeUp = [[TreeNavigationNodeUp alloc] init];
            }
			[self addLookahead:navigationNodeUp];
			break;
		}
	}
}

#pragma mark Accessors
- (CommonTree *) root
{
    return root;
}

- (void) setRoot: (CommonTree *) aRoot
{
    if (root != aRoot) {
        [aRoot retain];
        [root release];
        root = aRoot;
    }
}

@end