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