• 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 void					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 void
newPool(pANTLR3_ARBORETUM factory)124 newPool(pANTLR3_ARBORETUM factory)
125 {
126     // Increment factory count
127     //
128     factory->thisPool++;
129 
130     // Ensure we have enough pointers allocated
131     //
132     factory->pools = (pANTLR3_COMMON_TREE *)
133 					ANTLR3_REALLOC(	(void *)factory->pools,										// Current pools pointer (starts at NULL)
134 					(ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_COMMON_TREE *))	// Memory for new pool pointers
135 					);
136 
137     // Allocate a new pool for the factory
138     //
139     factory->pools[factory->thisPool]	=
140 			    (pANTLR3_COMMON_TREE)
141 				ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_COMMON_TREE) * ANTLR3_FACTORY_POOL_SIZE));
142 
143 
144     // Reset the counters
145     //
146     factory->nextTree	= 0;
147 
148     // Done
149     //
150     return;
151 }
152 
153 static	pANTLR3_BASE_TREE
newPoolTree(pANTLR3_ARBORETUM factory)154 newPoolTree	    (pANTLR3_ARBORETUM factory)
155 {
156 	pANTLR3_COMMON_TREE    tree;
157 
158     // If we have anything on the re claim stack, reuse that sucker first
159     //
160     tree = factory->nilStack->peek(factory->nilStack);
161 
162     if  (tree != NULL)
163     {
164         // Cool we got something we could reuse, it will have been cleaned up by
165         // whatever put it back on the stack (for instance if it had a child vector,
166         // that will have been cleared to hold zero entries and that vector will get reused too.
167         // It is the basetree pointer that is placed on the stack of course
168         //
169         factory->nilStack->pop(factory->nilStack);
170         return (pANTLR3_BASE_TREE)tree;
171 
172     }
173 	// See if we need a new tree pool before allocating a new tree
174 	//
175 	if	(factory->nextTree >= ANTLR3_FACTORY_POOL_SIZE)
176 	{
177 		// We ran out of tokens in the current pool, so we need a new pool
178 		//
179 		newPool(factory);
180 	}
181 
182 	// Assuming everything went well - we are trying for performance here so doing minimal
183 	// error checking - then we can work out what the pointer is to the next commontree.
184 	//
185 	tree   = factory->pools[factory->thisPool] + factory->nextTree;
186 	factory->nextTree++;
187 
188 	// We have our token pointer now, so we can initialize it to the predefined model.
189 	//
190     antlr3SetCTAPI(tree);
191 
192     // Set some initial variables for future copying, including a string factory
193     // that we can use later for converting trees to strings.
194     //
195 	tree->factory				= factory;
196     tree->baseTree.strFactory	= factory->unTruc.baseTree.strFactory;
197 
198 	// The super points to the common tree so we must override the one used by
199 	// by the pre-built tree as otherwise we will always poitn to the same initial
200 	// common tree and we might spend 3 hours trying to debug why - this would never
201 	// happen to me of course! :-(
202 	//
203 	tree->baseTree.super	= tree;
204 
205 
206 	// And we are done
207 	//
208 	return  &(tree->baseTree);
209 }
210 
211 
212 static pANTLR3_BASE_TREE
newFromTree(pANTLR3_ARBORETUM factory,pANTLR3_COMMON_TREE tree)213 newFromTree(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree)
214 {
215 	pANTLR3_BASE_TREE	newTree;
216 
217 	newTree = factory->newTree(factory);
218 
219 	if	(newTree == NULL)
220 	{
221 		return	NULL;
222 	}
223 
224 	// Pick up the payload we had in the supplied tree
225 	//
226 	((pANTLR3_COMMON_TREE)(newTree->super))->token   = tree->token;
227 	newTree->u		    = tree->baseTree.u;							// Copy any user pointer
228 
229 	return  newTree;
230 }
231 
232 static pANTLR3_BASE_TREE
newFromToken(pANTLR3_ARBORETUM factory,pANTLR3_COMMON_TOKEN token)233 newFromToken(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token)
234 {
235 	pANTLR3_BASE_TREE	newTree;
236 
237 	newTree = factory->newTree(factory);
238 
239 	if	(newTree == NULL)
240 	{
241 		return	NULL;
242 	}
243 
244 	// Pick up the payload we had in the supplied tree
245 	//
246 	((pANTLR3_COMMON_TREE)(newTree->super))->token = token;
247 
248 	return newTree;
249 }
250 
251 static	void
factoryClose(pANTLR3_ARBORETUM factory)252 factoryClose	    (pANTLR3_ARBORETUM factory)
253 {
254 	ANTLR3_INT32	    poolCount;
255 
256 	// First close the vector factory that supplied all the child pointer
257 	// vectors.
258 	//
259 	factory->vFactory->close(factory->vFactory);
260 
261     if  (factory->nilStack !=  NULL)
262     {
263         factory->nilStack->free(factory->nilStack);
264     }
265 
266 	// We now JUST free the pools because the C runtime CommonToken based tree
267 	// cannot contain anything that was not made by this factory.
268 	//
269 	for	(poolCount = 0; poolCount <= factory->thisPool; poolCount++)
270 	{
271 		// We can now free this pool allocation
272 		//
273 		ANTLR3_FREE(factory->pools[poolCount]);
274 		factory->pools[poolCount] = NULL;
275 	}
276 
277 	// All the pools are deallocated we can free the pointers to the pools
278 	// now.
279 	//
280 	ANTLR3_FREE(factory->pools);
281 
282 	// Finally, we can free the space for the factory itself
283 	//
284 	ANTLR3_FREE(factory);
285 }
286 
287 
288 ANTLR3_API void
antlr3SetCTAPI(pANTLR3_COMMON_TREE tree)289 antlr3SetCTAPI(pANTLR3_COMMON_TREE tree)
290 {
291     // Init base tree
292     //
293     antlr3BaseTreeNew(&(tree->baseTree));
294 
295     // We need a pointer to ourselves for
296     // the payload and few functions that we
297     // provide.
298     //
299     tree->baseTree.super    =  tree;
300 
301     // Common tree overrides
302 
303     tree->baseTree.isNilNode                = isNilNode;
304     tree->baseTree.toString					= toString;
305     tree->baseTree.dupNode					= (void *(*)(pANTLR3_BASE_TREE))(dupNode);
306     tree->baseTree.getLine					= getLine;
307     tree->baseTree.getCharPositionInLine	= getCharPositionInLine;
308     tree->baseTree.toString					= toString;
309     tree->baseTree.getType					= getType;
310     tree->baseTree.getText					= getText;
311     tree->baseTree.getToken					= getToken;
312 	tree->baseTree.getParent				= getParent;
313 	tree->baseTree.setParent				= setParent;
314 	tree->baseTree.setChildIndex			= setChildIndex;
315 	tree->baseTree.getChildIndex			= getChildIndex;
316 	tree->baseTree.createChildrenList		= createChildrenList;
317     tree->baseTree.reuse                    = reuse;
318 	tree->baseTree.free						= NULL;	    // Factory trees have no free function
319     tree->baseTree.u                        = NULL;     // Initialize user pointer
320 
321 	tree->baseTree.children	= NULL;
322 
323     tree->token				= NULL;	// No token as yet
324     tree->startIndex		= 0;
325     tree->stopIndex			= 0;
326 	tree->parent			= NULL;	// No parent yet
327 	tree->childIndex		= -1;
328 
329     return;
330 }
331 
332 // --------------------------------------
333 // Non factory node constructors.
334 //
335 
336 ANTLR3_API pANTLR3_COMMON_TREE
antlr3CommonTreeNew()337 antlr3CommonTreeNew()
338 {
339 	pANTLR3_COMMON_TREE	tree;
340 	tree    = ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE));
341 
342 	if	(tree == NULL)
343 	{
344 		return NULL;
345 	}
346 
347 	antlr3SetCTAPI(tree);
348 
349 	return tree;
350 }
351 
352 ANTLR3_API pANTLR3_COMMON_TREE
antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token)353 antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token)
354 {
355 	pANTLR3_COMMON_TREE	newTree;
356 
357 	newTree = antlr3CommonTreeNew();
358 
359 	if	(newTree == NULL)
360 	{
361 		return	NULL;
362 	}
363 
364 	//Pick up the payload we had in the supplied tree
365 	//
366 	newTree->token = token;
367 	return newTree;
368 }
369 
370 /// Create a new vector for holding child nodes using the inbuilt
371 /// vector factory.
372 ///
373 static void
createChildrenList(pANTLR3_BASE_TREE tree)374 createChildrenList  (pANTLR3_BASE_TREE tree)
375 {
376 	tree->children = ((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory->newVector(((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory);
377 }
378 
379 
380 static pANTLR3_COMMON_TOKEN
getToken(pANTLR3_BASE_TREE tree)381 getToken			(pANTLR3_BASE_TREE tree)
382 {
383     // The token is the payload of the common tree or other implementor
384     // so it is stored within ourselves, which is the super pointer.Note
385 	// that whatever the actual token is, it is passed around by its pointer
386 	// to the common token implementation, which it may of course surround
387 	// with its own super structure.
388     //
389     return  ((pANTLR3_COMMON_TREE)(tree->super))->token;
390 }
391 
392 static pANTLR3_BASE_TREE
dupNode(pANTLR3_BASE_TREE tree)393 dupNode			(pANTLR3_BASE_TREE tree)
394 {
395     // The node we are duplicating is in fact the common tree (that's why we are here)
396     // so we use the super pointer to duplicate.
397     //
398     pANTLR3_COMMON_TREE	    theOld;
399 
400 	theOld	= (pANTLR3_COMMON_TREE)(tree->super);
401 
402 	// The pointer we return is the base implementation of course
403     //
404 	return  theOld->factory->newFromTree(theOld->factory, theOld);
405 }
406 
407 static ANTLR3_BOOLEAN
isNilNode(pANTLR3_BASE_TREE tree)408 isNilNode			(pANTLR3_BASE_TREE tree)
409 {
410 	// This is a Nil tree if it has no payload (Token in our case)
411 	//
412 	if	(((pANTLR3_COMMON_TREE)(tree->super))->token == NULL)
413 	{
414 		return ANTLR3_TRUE;
415 	}
416 	else
417 	{
418 		return ANTLR3_FALSE;
419 	}
420 }
421 
422 static ANTLR3_UINT32
getType(pANTLR3_BASE_TREE tree)423 getType			(pANTLR3_BASE_TREE tree)
424 {
425 	pANTLR3_COMMON_TREE    theTree;
426 
427 	theTree = (pANTLR3_COMMON_TREE)(tree->super);
428 
429 	if	(theTree->token == NULL)
430 	{
431 		return	0;
432 	}
433 	else
434 	{
435 		return	theTree->token->getType(theTree->token);
436 	}
437 }
438 
439 static pANTLR3_STRING
getText(pANTLR3_BASE_TREE tree)440 getText			(pANTLR3_BASE_TREE tree)
441 {
442 	return	tree->toString(tree);
443 }
444 
getLine(pANTLR3_BASE_TREE tree)445 static ANTLR3_UINT32	    getLine			(pANTLR3_BASE_TREE tree)
446 {
447 	pANTLR3_COMMON_TREE	    cTree;
448 	pANTLR3_COMMON_TOKEN    token;
449 
450 	cTree   = (pANTLR3_COMMON_TREE)(tree->super);
451 
452 	token   = cTree->token;
453 
454 	if	(token == NULL || token->getLine(token) == 0)
455 	{
456 		if  (tree->getChildCount(tree) > 0)
457 		{
458 			pANTLR3_BASE_TREE	child;
459 
460 			child   = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
461 			return child->getLine(child);
462 		}
463 		return 0;
464 	}
465 	return  token->getLine(token);
466 }
467 
getCharPositionInLine(pANTLR3_BASE_TREE tree)468 static ANTLR3_UINT32	    getCharPositionInLine	(pANTLR3_BASE_TREE tree)
469 {
470 	pANTLR3_COMMON_TOKEN    token;
471 
472 	token   = ((pANTLR3_COMMON_TREE)(tree->super))->token;
473 
474 	if	(token == NULL || token->getCharPositionInLine(token) == -1)
475 	{
476 		if  (tree->getChildCount(tree) > 0)
477 		{
478 			pANTLR3_BASE_TREE	child;
479 
480 			child   = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
481 
482 			return child->getCharPositionInLine(child);
483 		}
484 		return 0;
485 	}
486 	return  token->getCharPositionInLine(token);
487 }
488 
toString(pANTLR3_BASE_TREE tree)489 static pANTLR3_STRING	    toString			(pANTLR3_BASE_TREE tree)
490 {
491 	if  (tree->isNilNode(tree) == ANTLR3_TRUE)
492 	{
493 		pANTLR3_STRING  nilNode;
494 
495 		nilNode	= tree->strFactory->newPtr(tree->strFactory, (pANTLR3_UINT8)"nil", 3);
496 
497 		return nilNode;
498 	}
499 
500 	return	((pANTLR3_COMMON_TREE)(tree->super))->token->getText(((pANTLR3_COMMON_TREE)(tree->super))->token);
501 }
502 
503 static pANTLR3_BASE_TREE
getParent(pANTLR3_BASE_TREE tree)504 getParent				(pANTLR3_BASE_TREE tree)
505 {
506 	return & (((pANTLR3_COMMON_TREE)(tree->super))->parent->baseTree);
507 }
508 
509 static void
setParent(pANTLR3_BASE_TREE tree,pANTLR3_BASE_TREE parent)510 setParent				(pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent)
511 {
512 	((pANTLR3_COMMON_TREE)(tree->super))->parent = parent == NULL ? NULL : ((pANTLR3_COMMON_TREE)(parent->super))->parent;
513 }
514 
515 static void
setChildIndex(pANTLR3_BASE_TREE tree,ANTLR3_INT32 i)516 setChildIndex			(pANTLR3_BASE_TREE tree, ANTLR3_INT32 i)
517 {
518 	((pANTLR3_COMMON_TREE)(tree->super))->childIndex = i;
519 }
520 static	ANTLR3_INT32
getChildIndex(pANTLR3_BASE_TREE tree)521 getChildIndex			(pANTLR3_BASE_TREE tree )
522 {
523 	return ((pANTLR3_COMMON_TREE)(tree->super))->childIndex;
524 }
525 
526 /** Clean up any child vector that the tree might have, so it can be reused,
527  *  then add it into the reuse stack.
528  */
529 static void
reuse(pANTLR3_BASE_TREE tree)530 reuse                   (pANTLR3_BASE_TREE tree)
531 {
532     pANTLR3_COMMON_TREE	    cTree;
533 
534 	cTree   = (pANTLR3_COMMON_TREE)(tree->super);
535 
536     if  (cTree->factory != NULL)
537     {
538 
539         if  (cTree->baseTree.children != NULL)
540         {
541 
542             cTree->baseTree.children->clear(cTree->baseTree.children);
543         }
544        cTree->factory->nilStack->push(cTree->factory->nilStack, tree, NULL);
545 
546     }
547 }
548