• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // \file
2 //
3 // Implementation of ANTLR3 CommonTree, which you can use as a
4 // starting point for your own tree. Though it is often easier just to tag things on
5 // to the user pointer in the tree unless you are building a different type
6 // of structure.
7 //
8 
9 // [The "BSD licence"]
10 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
11 // http://www.temporal-wave.com
12 // http://www.linkedin.com/in/jimidle
13 //
14 // All rights reserved.
15 //
16 // Redistribution and use in source and binary forms, with or without
17 // modification, are permitted provided that the following conditions
18 // are met:
19 // 1. Redistributions of source code must retain the above copyright
20 //    notice, this list of conditions and the following disclaimer.
21 // 2. Redistributions in binary form must reproduce the above copyright
22 //    notice, this list of conditions and the following disclaimer in the
23 //    documentation and/or other materials provided with the distribution.
24 // 3. The name of the author may not be used to endorse or promote products
25 //    derived from this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
28 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
29 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
30 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
31 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
32 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
33 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
34 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
35 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
36 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 
38 #include    <antlr3commontree.h>
39 
40 
41 static pANTLR3_COMMON_TOKEN getToken				(pANTLR3_BASE_TREE tree);
42 static pANTLR3_BASE_TREE    dupNode					(pANTLR3_BASE_TREE tree);
43 static ANTLR3_BOOLEAN	    isNilNode					(pANTLR3_BASE_TREE tree);
44 static ANTLR3_UINT32	    getType					(pANTLR3_BASE_TREE tree);
45 static pANTLR3_STRING	    getText					(pANTLR3_BASE_TREE tree);
46 static ANTLR3_UINT32	    getLine					(pANTLR3_BASE_TREE tree);
47 static ANTLR3_UINT32	    getCharPositionInLine	(pANTLR3_BASE_TREE tree);
48 static pANTLR3_STRING	    toString				(pANTLR3_BASE_TREE tree);
49 static pANTLR3_BASE_TREE	getParent				(pANTLR3_BASE_TREE tree);
50 static void					setParent				(pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent);
51 static void    				setChildIndex			(pANTLR3_BASE_TREE tree, ANTLR3_INT32 i);
52 static ANTLR3_INT32			getChildIndex			(pANTLR3_BASE_TREE tree);
53 static void					createChildrenList		(pANTLR3_BASE_TREE tree);
54 static void                 reuse                   (pANTLR3_BASE_TREE tree);
55 
56 // Factory functions for the Arboretum
57 //
58 static ANTLR3_BOOLEAN		newPool				(pANTLR3_ARBORETUM factory);
59 static pANTLR3_BASE_TREE    newPoolTree			(pANTLR3_ARBORETUM factory);
60 static pANTLR3_BASE_TREE    newFromTree			(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree);
61 static pANTLR3_BASE_TREE    newFromToken		(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token);
62 static void					factoryClose		(pANTLR3_ARBORETUM factory);
63 
64 ANTLR3_API pANTLR3_ARBORETUM
antlr3ArboretumNew(pANTLR3_STRING_FACTORY strFactory)65 antlr3ArboretumNew(pANTLR3_STRING_FACTORY strFactory)
66 {
67     pANTLR3_ARBORETUM   factory;
68 
69     // Allocate memory
70     //
71     factory	= (pANTLR3_ARBORETUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_ARBORETUM));
72     if	(factory == NULL)
73     {
74 		return	NULL;
75     }
76 
77 	// Install a vector factory to create, track and free() any child
78 	// node lists.
79 	//
80 	factory->vFactory					= antlr3VectorFactoryNew(0);
81 	if	(factory->vFactory == NULL)
82 	{
83 		free(factory);
84 		return	NULL;
85 	}
86 
87     // We also keep a reclaim stack, so that any Nil nodes that are
88     // orphaned are not just left in the pool but are reused, other wise
89     // we create 6 times as many nilNodes as ordinary nodes and use loads of
90     // memory. Perhaps at some point, the analysis phase will generate better
91     // code and we won't need to do this here.
92     //
93     factory->nilStack       =  antlr3StackNew(0);
94 
95     // Install factory API
96     //
97     factory->newTree	    =  newPoolTree;
98     factory->newFromTree    =  newFromTree;
99     factory->newFromToken   =  newFromToken;
100     factory->close			=  factoryClose;
101 
102     // Allocate the initial pool
103     //
104     factory->thisPool	= -1;
105     factory->pools		= NULL;
106     newPool(factory);
107 
108     // Factory space is good, we now want to initialize our cheating token
109     // which one it is initialized is the model for all tokens we manufacture
110     //
111     antlr3SetCTAPI(&factory->unTruc);
112 
113     // Set some initial variables for future copying, including a string factory
114     // that we can use later for converting trees to strings.
115     //
116 	factory->unTruc.factory				= factory;
117     factory->unTruc.baseTree.strFactory	= strFactory;
118 
119     return  factory;
120 
121 }
122 
123 static ANTLR3_BOOLEAN
newPool(pANTLR3_ARBORETUM factory)124 newPool(pANTLR3_ARBORETUM factory)
125 {
126 	pANTLR3_COMMON_TREE *newPools;
127 
128     // Increment factory count
129     //
130     ++factory->thisPool;
131 
132     // Ensure we have enough pointers allocated
133     //
134     newPools = (pANTLR3_COMMON_TREE *)
135 					ANTLR3_REALLOC(	(void *)factory->pools,										// Current pools pointer (starts at NULL)
136 					(ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_COMMON_TREE *))	// Memory for new pool pointers
137 					);
138 	if (newPools == NULL)
139 	{
140 		// realloc failed, but we still have the old allocation
141 		--factory->thisPool;
142 		return ANTLR3_FALSE;
143 	}
144 	factory->pools = newPools;
145 
146     // Allocate a new pool for the factory
147     //
148     factory->pools[factory->thisPool]	=
149 			    (pANTLR3_COMMON_TREE)
150 				ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_COMMON_TREE) * ANTLR3_FACTORY_POOL_SIZE));
151 	if (factory->pools[factory->thisPool] == NULL)
152 	{
153 		// malloc failed
154 		--factory->thisPool;
155 		return ANTLR3_FALSE;
156 	}
157 
158 
159     // Reset the counters
160     //
161     factory->nextTree	= 0;
162 
163     // Done
164     //
165     return ANTLR3_TRUE;
166 }
167 
168 static	pANTLR3_BASE_TREE
newPoolTree(pANTLR3_ARBORETUM factory)169 newPoolTree	    (pANTLR3_ARBORETUM factory)
170 {
171 	pANTLR3_COMMON_TREE    tree;
172 
173     // If we have anything on the re claim stack, reuse that sucker first
174     //
175     tree = (pANTLR3_COMMON_TREE)factory->nilStack->peek(factory->nilStack);
176 
177     if  (tree != NULL)
178     {
179         // Cool we got something we could reuse, it will have been cleaned up by
180         // whatever put it back on the stack (for instance if it had a child vector,
181         // that will have been cleared to hold zero entries and that vector will get reused too.
182         // It is the basetree pointer that is placed on the stack of course
183         //
184         factory->nilStack->pop(factory->nilStack);
185         return (pANTLR3_BASE_TREE)tree;
186 
187     }
188 	// See if we need a new tree pool before allocating a new tree
189 	//
190 	if	(factory->nextTree >= ANTLR3_FACTORY_POOL_SIZE)
191 	{
192 		// We ran out of tokens in the current pool, so we need a new pool
193 		//
194 		if (!newPool(factory))
195 		{
196 			// new pool creation failed
197 			return NULL;
198 		}
199 	}
200 
201 	// Assuming everything went well - we are trying for performance here so doing minimal
202 	// error checking - then we can work out what the pointer is to the next commontree.
203 	//
204 	tree   = factory->pools[factory->thisPool] + factory->nextTree;
205 	factory->nextTree++;
206 
207 	// We have our token pointer now, so we can initialize it to the predefined model.
208 	//
209     antlr3SetCTAPI(tree);
210 
211     // Set some initial variables for future copying, including a string factory
212     // that we can use later for converting trees to strings.
213     //
214 	tree->factory				= factory;
215     tree->baseTree.strFactory	= factory->unTruc.baseTree.strFactory;
216 
217 	// The super points to the common tree so we must override the one used by
218 	// by the pre-built tree as otherwise we will always poitn to the same initial
219 	// common tree and we might spend 3 hours trying to debug why - this would never
220 	// happen to me of course! :-(
221 	//
222 	tree->baseTree.super	= tree;
223 
224 
225 	// And we are done
226 	//
227 	return  &(tree->baseTree);
228 }
229 
230 
231 static pANTLR3_BASE_TREE
newFromTree(pANTLR3_ARBORETUM factory,pANTLR3_COMMON_TREE tree)232 newFromTree(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree)
233 {
234 	pANTLR3_BASE_TREE	newTree;
235 
236 	newTree = factory->newTree(factory);
237 
238 	if	(newTree == NULL)
239 	{
240 		return	NULL;
241 	}
242 
243 	// Pick up the payload we had in the supplied tree
244 	//
245 	((pANTLR3_COMMON_TREE)(newTree->super))->token   = tree->token;
246 	newTree->u		    = tree->baseTree.u;							// Copy any user pointer
247 
248 	return  newTree;
249 }
250 
251 static pANTLR3_BASE_TREE
newFromToken(pANTLR3_ARBORETUM factory,pANTLR3_COMMON_TOKEN token)252 newFromToken(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token)
253 {
254 	pANTLR3_BASE_TREE	newTree;
255 
256 	newTree = factory->newTree(factory);
257 
258 	if	(newTree == NULL)
259 	{
260 		return	NULL;
261 	}
262 
263 	// Pick up the payload we had in the supplied tree
264 	//
265 	((pANTLR3_COMMON_TREE)(newTree->super))->token = token;
266 
267 	return newTree;
268 }
269 
270 static	void
factoryClose(pANTLR3_ARBORETUM factory)271 factoryClose	    (pANTLR3_ARBORETUM factory)
272 {
273 	ANTLR3_INT32	    poolCount;
274 
275 	// First close the vector factory that supplied all the child pointer
276 	// vectors.
277 	//
278 	factory->vFactory->close(factory->vFactory);
279 
280     if  (factory->nilStack !=  NULL)
281     {
282         factory->nilStack->free(factory->nilStack);
283     }
284 
285 	// We now JUST free the pools because the C runtime CommonToken based tree
286 	// cannot contain anything that was not made by this factory.
287 	//
288 	for	(poolCount = 0; poolCount <= factory->thisPool; poolCount++)
289 	{
290 		// We can now free this pool allocation
291 		//
292 		ANTLR3_FREE(factory->pools[poolCount]);
293 		factory->pools[poolCount] = NULL;
294 	}
295 
296 	// All the pools are deallocated we can free the pointers to the pools
297 	// now.
298 	//
299 	ANTLR3_FREE(factory->pools);
300 
301 	// Finally, we can free the space for the factory itself
302 	//
303 	ANTLR3_FREE(factory);
304 }
305 
306 
307 ANTLR3_API void
antlr3SetCTAPI(pANTLR3_COMMON_TREE tree)308 antlr3SetCTAPI(pANTLR3_COMMON_TREE tree)
309 {
310     // Init base tree
311     //
312     antlr3BaseTreeNew(&(tree->baseTree));
313 
314     // We need a pointer to ourselves for
315     // the payload and few functions that we
316     // provide.
317     //
318     tree->baseTree.super    =  tree;
319 
320     // Common tree overrides
321 
322     tree->baseTree.isNilNode                = isNilNode;
323     tree->baseTree.toString					= toString;
324     tree->baseTree.dupNode					= (void *(*)(pANTLR3_BASE_TREE))(dupNode);
325     tree->baseTree.getLine					= getLine;
326     tree->baseTree.getCharPositionInLine	= getCharPositionInLine;
327     tree->baseTree.toString					= toString;
328     tree->baseTree.getType					= getType;
329     tree->baseTree.getText					= getText;
330     tree->baseTree.getToken					= getToken;
331 	tree->baseTree.getParent				= getParent;
332 	tree->baseTree.setParent				= setParent;
333 	tree->baseTree.setChildIndex			= setChildIndex;
334 	tree->baseTree.getChildIndex			= getChildIndex;
335 	tree->baseTree.createChildrenList		= createChildrenList;
336     tree->baseTree.reuse                    = reuse;
337 	tree->baseTree.free						= NULL;	    // Factory trees have no free function
338     tree->baseTree.u                        = NULL;     // Initialize user pointer
339 
340 	tree->baseTree.children	= NULL;
341 
342     tree->token				= NULL;	// No token as yet
343     tree->startIndex		= 0;
344     tree->stopIndex			= 0;
345 	tree->parent			= NULL;	// No parent yet
346 	tree->childIndex		= -1;
347 
348     return;
349 }
350 
351 // --------------------------------------
352 // Non factory node constructors.
353 //
354 
355 ANTLR3_API pANTLR3_COMMON_TREE
antlr3CommonTreeNew()356 antlr3CommonTreeNew()
357 {
358 	pANTLR3_COMMON_TREE	tree;
359 	tree = (pANTLR3_COMMON_TREE)ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE));
360 
361 	if	(tree == NULL)
362 	{
363 		return NULL;
364 	}
365 
366 	antlr3SetCTAPI(tree);
367 
368 	return tree;
369 }
370 
371 ANTLR3_API pANTLR3_COMMON_TREE
antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token)372 antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token)
373 {
374 	pANTLR3_COMMON_TREE	newTree;
375 
376 	newTree = antlr3CommonTreeNew();
377 
378 	if	(newTree == NULL)
379 	{
380 		return	NULL;
381 	}
382 
383 	//Pick up the payload we had in the supplied tree
384 	//
385 	newTree->token = token;
386 	return newTree;
387 }
388 
389 /// Create a new vector for holding child nodes using the inbuilt
390 /// vector factory.
391 ///
392 static void
createChildrenList(pANTLR3_BASE_TREE tree)393 createChildrenList  (pANTLR3_BASE_TREE tree)
394 {
395 	tree->children = ((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory->newVector(((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory);
396 }
397 
398 
399 static pANTLR3_COMMON_TOKEN
getToken(pANTLR3_BASE_TREE tree)400 getToken			(pANTLR3_BASE_TREE tree)
401 {
402     // The token is the payload of the common tree or other implementor
403     // so it is stored within ourselves, which is the super pointer.Note
404 	// that whatever the actual token is, it is passed around by its pointer
405 	// to the common token implementation, which it may of course surround
406 	// with its own super structure.
407     //
408     return  ((pANTLR3_COMMON_TREE)(tree->super))->token;
409 }
410 
411 static pANTLR3_BASE_TREE
dupNode(pANTLR3_BASE_TREE tree)412 dupNode			(pANTLR3_BASE_TREE tree)
413 {
414     // The node we are duplicating is in fact the common tree (that's why we are here)
415     // so we use the super pointer to duplicate.
416     //
417     pANTLR3_COMMON_TREE	    theOld;
418 
419 	theOld	= (pANTLR3_COMMON_TREE)(tree->super);
420 
421 	// The pointer we return is the base implementation of course
422     //
423 	return  theOld->factory->newFromTree(theOld->factory, theOld);
424 }
425 
426 static ANTLR3_BOOLEAN
isNilNode(pANTLR3_BASE_TREE tree)427 isNilNode			(pANTLR3_BASE_TREE tree)
428 {
429 	// This is a Nil tree if it has no payload (Token in our case)
430 	//
431 	if	(((pANTLR3_COMMON_TREE)(tree->super))->token == NULL)
432 	{
433 		return ANTLR3_TRUE;
434 	}
435 	else
436 	{
437 		return ANTLR3_FALSE;
438 	}
439 }
440 
441 static ANTLR3_UINT32
getType(pANTLR3_BASE_TREE tree)442 getType			(pANTLR3_BASE_TREE tree)
443 {
444 	pANTLR3_COMMON_TREE    theTree;
445 
446 	theTree = (pANTLR3_COMMON_TREE)(tree->super);
447 
448 	if	(theTree->token == NULL)
449 	{
450 		return	0;
451 	}
452 	else
453 	{
454 		return	theTree->token->getType(theTree->token);
455 	}
456 }
457 
458 static pANTLR3_STRING
getText(pANTLR3_BASE_TREE tree)459 getText			(pANTLR3_BASE_TREE tree)
460 {
461 	return	tree->toString(tree);
462 }
463 
getLine(pANTLR3_BASE_TREE tree)464 static ANTLR3_UINT32	    getLine			(pANTLR3_BASE_TREE tree)
465 {
466 	pANTLR3_COMMON_TREE	    cTree;
467 	pANTLR3_COMMON_TOKEN    token;
468 
469 	cTree   = (pANTLR3_COMMON_TREE)(tree->super);
470 
471 	token   = cTree->token;
472 
473 	if	(token == NULL || token->getLine(token) == 0)
474 	{
475 		if  (tree->getChildCount(tree) > 0)
476 		{
477 			pANTLR3_BASE_TREE	child;
478 
479 			child   = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
480 			return child->getLine(child);
481 		}
482 		return 0;
483 	}
484 	return  token->getLine(token);
485 }
486 
getCharPositionInLine(pANTLR3_BASE_TREE tree)487 static ANTLR3_UINT32	    getCharPositionInLine	(pANTLR3_BASE_TREE tree)
488 {
489 	pANTLR3_COMMON_TOKEN    token;
490 
491 	token   = ((pANTLR3_COMMON_TREE)(tree->super))->token;
492 
493 	if	(token == NULL || token->getCharPositionInLine(token) == -1)
494 	{
495 		if  (tree->getChildCount(tree) > 0)
496 		{
497 			pANTLR3_BASE_TREE	child;
498 
499 			child   = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
500 
501 			return child->getCharPositionInLine(child);
502 		}
503 		return 0;
504 	}
505 	return  token->getCharPositionInLine(token);
506 }
507 
toString(pANTLR3_BASE_TREE tree)508 static pANTLR3_STRING	    toString			(pANTLR3_BASE_TREE tree)
509 {
510 	if  (tree->isNilNode(tree) == ANTLR3_TRUE)
511 	{
512 		pANTLR3_STRING  nilNode;
513 
514 		nilNode	= tree->strFactory->newPtr(tree->strFactory, (pANTLR3_UINT8)"nil", 3);
515 
516 		return nilNode;
517 	}
518 
519 	return	((pANTLR3_COMMON_TREE)(tree->super))->token->getText(((pANTLR3_COMMON_TREE)(tree->super))->token);
520 }
521 
522 static pANTLR3_BASE_TREE
getParent(pANTLR3_BASE_TREE tree)523 getParent				(pANTLR3_BASE_TREE tree)
524 {
525 	if (((pANTLR3_COMMON_TREE)(tree->super))->parent == NULL)
526 		return NULL;
527 	return & (((pANTLR3_COMMON_TREE)(tree->super))->parent->baseTree);
528 }
529 
530 static void
setParent(pANTLR3_BASE_TREE tree,pANTLR3_BASE_TREE parent)531 setParent				(pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent)
532 {
533 	((pANTLR3_COMMON_TREE)(tree->super))->parent = parent == NULL ? NULL : ((pANTLR3_COMMON_TREE)(parent->super));
534 }
535 
536 static void
setChildIndex(pANTLR3_BASE_TREE tree,ANTLR3_INT32 i)537 setChildIndex			(pANTLR3_BASE_TREE tree, ANTLR3_INT32 i)
538 {
539 	((pANTLR3_COMMON_TREE)(tree->super))->childIndex = i;
540 }
541 static	ANTLR3_INT32
getChildIndex(pANTLR3_BASE_TREE tree)542 getChildIndex			(pANTLR3_BASE_TREE tree )
543 {
544 	return ((pANTLR3_COMMON_TREE)(tree->super))->childIndex;
545 }
546 
547 /** Clean up any child vector that the tree might have, so it can be reused,
548  *  then add it into the reuse stack.
549  */
550 static void
reuse(pANTLR3_BASE_TREE tree)551 reuse                   (pANTLR3_BASE_TREE tree)
552 {
553     pANTLR3_COMMON_TREE	    cTree;
554 
555 	cTree   = (pANTLR3_COMMON_TREE)(tree->super);
556 
557     if  (cTree->factory != NULL)
558     {
559 
560         if  (cTree->baseTree.children != NULL)
561         {
562 
563             cTree->baseTree.children->clear(cTree->baseTree.children);
564         }
565        cTree->factory->nilStack->push(cTree->factory->nilStack, tree, NULL);
566 
567     }
568 }
569