• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #include    <antlr3basetree.h>
2 
3 #ifdef	ANTLR3_WINDOWS
4 #pragma warning( disable : 4100 )
5 #endif
6 
7 // [The "BSD licence"]
8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
9 // http://www.temporal-wave.com
10 // http://www.linkedin.com/in/jimidle
11 //
12 // All rights reserved.
13 //
14 // Redistribution and use in source and binary forms, with or without
15 // modification, are permitted provided that the following conditions
16 // are met:
17 // 1. Redistributions of source code must retain the above copyright
18 //    notice, this list of conditions and the following disclaimer.
19 // 2. Redistributions in binary form must reproduce the above copyright
20 //    notice, this list of conditions and the following disclaimer in the
21 //    documentation and/or other materials provided with the distribution.
22 // 3. The name of the author may not be used to endorse or promote products
23 //    derived from this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
26 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
27 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
28 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
30 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
34 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 
36 static void				*	getChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
37 static ANTLR3_UINT32		getChildCount		(pANTLR3_BASE_TREE tree);
38 static ANTLR3_UINT32		getCharPositionInLine
39 (pANTLR3_BASE_TREE tree);
40 static ANTLR3_UINT32		getLine				(pANTLR3_BASE_TREE tree);
41 static pANTLR3_BASE_TREE
42 getFirstChildWithType
43 (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type);
44 static void					addChild			(pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child);
45 static void					addChildren			(pANTLR3_BASE_TREE tree, pANTLR3_LIST kids);
46 static void					replaceChildren		(pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);
47 
48 static	void				freshenPACIndexesAll(pANTLR3_BASE_TREE tree);
49 static	void				freshenPACIndexes	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset);
50 
51 static void					setChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child);
52 static void				*	deleteChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
53 static void				*	dupTree				(pANTLR3_BASE_TREE tree);
54 static pANTLR3_STRING		toStringTree		(pANTLR3_BASE_TREE tree);
55 
56 
57 ANTLR3_API pANTLR3_BASE_TREE
antlr3BaseTreeNew(pANTLR3_BASE_TREE tree)58 antlr3BaseTreeNew(pANTLR3_BASE_TREE  tree)
59 {
60 	/* api */
61 	tree->getChild				= getChild;
62 	tree->getChildCount			= getChildCount;
63 	tree->addChild				= (void (*)(pANTLR3_BASE_TREE, void *))(addChild);
64 	tree->addChildren			= addChildren;
65 	tree->setChild				= setChild;
66 	tree->deleteChild			= deleteChild;
67 	tree->dupTree				= dupTree;
68 	tree->toStringTree			= toStringTree;
69 	tree->getCharPositionInLine	= getCharPositionInLine;
70 	tree->getLine				= getLine;
71 	tree->replaceChildren		= replaceChildren;
72 	tree->freshenPACIndexesAll	= freshenPACIndexesAll;
73 	tree->freshenPACIndexes		= freshenPACIndexes;
74 	tree->getFirstChildWithType	= (void *(*)(pANTLR3_BASE_TREE, ANTLR3_UINT32))(getFirstChildWithType);
75 	tree->children				= NULL;
76 	tree->strFactory			= NULL;
77 
78 	/* Rest must be filled in by caller.
79 	*/
80 	return  tree;
81 }
82 
83 static ANTLR3_UINT32
getCharPositionInLine(pANTLR3_BASE_TREE tree)84 getCharPositionInLine	(pANTLR3_BASE_TREE tree)
85 {
86 	return  0;
87 }
88 
89 static ANTLR3_UINT32
getLine(pANTLR3_BASE_TREE tree)90 getLine	(pANTLR3_BASE_TREE tree)
91 {
92 	return  0;
93 }
94 static pANTLR3_BASE_TREE
getFirstChildWithType(pANTLR3_BASE_TREE tree,ANTLR3_UINT32 type)95 getFirstChildWithType	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type)
96 {
97 	ANTLR3_UINT32   i;
98 	ANTLR3_UINT32   cs;
99 
100 	pANTLR3_BASE_TREE	t;
101 	if	(tree->children != NULL)
102 	{
103 		cs	= tree->children->size(tree->children);
104 		for	(i = 0; i < cs; i++)
105 		{
106 			t = (pANTLR3_BASE_TREE) (tree->children->get(tree->children, i));
107 			if  (tree->getType(t) == type)
108 			{
109 				return  (pANTLR3_BASE_TREE)t;
110 			}
111 		}
112 	}
113 	return  NULL;
114 }
115 
116 
117 
118 static void    *
getChild(pANTLR3_BASE_TREE tree,ANTLR3_UINT32 i)119 getChild		(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
120 {
121 	if	(      tree->children == NULL
122 		|| i >= tree->children->size(tree->children))
123 	{
124 		return NULL;
125 	}
126 	return  tree->children->get(tree->children, i);
127 }
128 
129 
130 static ANTLR3_UINT32
getChildCount(pANTLR3_BASE_TREE tree)131 getChildCount	(pANTLR3_BASE_TREE tree)
132 {
133 	if	(tree->children == NULL)
134 	{
135 		return 0;
136 	}
137 	else
138 	{
139 		return	tree->children->size(tree->children);
140 	}
141 }
142 
143 void
addChild(pANTLR3_BASE_TREE tree,pANTLR3_BASE_TREE child)144 addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child)
145 {
146 	ANTLR3_UINT32   n;
147 	ANTLR3_UINT32   i;
148 
149 	if	(child == NULL)
150 	{
151 		return;
152 	}
153 
154 	if	(child->isNilNode(child) == ANTLR3_TRUE)
155 	{
156 		if  (child->children != NULL && child->children == tree->children)
157 		{
158 			// TODO: Change to exception rather than ANTLR3_FPRINTF?
159 			//
160 			ANTLR3_FPRINTF(stderr, "ANTLR3: An attempt was made to add a child list to itself!\n");
161 			return;
162 		}
163 
164         // Add all of the children's children to this list
165         //
166         if (child->children != NULL)
167         {
168             if (tree->children == NULL)
169             {
170                 // We are build ing the tree structure here, so we need not
171                 // worry about duplication of pointers as the tree node
172                 // factory will only clean up each node once. So we just
173                 // copy in the child's children pointer as the child is
174                 // a nil node (has not root itself).
175                 //
176                 tree->children = child->children;
177                 child->children = NULL;
178                 freshenPACIndexesAll(tree);
179 
180             }
181             else
182             {
183                 // Need to copy the children
184                 //
185                 n = child->children->size(child->children);
186 
187                 for (i = 0; i < n; i++)
188                 {
189                     pANTLR3_BASE_TREE entry;
190                     entry = child->children->get(child->children, i);
191 
192                     // ANTLR3 lists can be sparse, unlike Array Lists
193                     //
194                     if (entry != NULL)
195                     {
196                         tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free);
197                     }
198                 }
199             }
200 		}
201 	}
202 	else
203 	{
204 		// Tree we are adding is not a Nil and might have children to copy
205 		//
206 		if  (tree->children == NULL)
207 		{
208 			// No children in the tree we are adding to, so create a new list on
209 			// the fly to hold them.
210 			//
211 			tree->createChildrenList(tree);
212 		}
213 
214 		tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free);
215 
216 	}
217 }
218 
219 /// Add all elements of the supplied list as children of this node
220 ///
221 static void
addChildren(pANTLR3_BASE_TREE tree,pANTLR3_LIST kids)222 addChildren	(pANTLR3_BASE_TREE tree, pANTLR3_LIST kids)
223 {
224 	ANTLR3_UINT32    i;
225 	ANTLR3_UINT32    s;
226 
227 	s = kids->size(kids);
228 	for	(i = 0; i<s; i++)
229 	{
230 		tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1)));
231 	}
232 }
233 
234 
235 static    void
setChild(pANTLR3_BASE_TREE tree,ANTLR3_UINT32 i,void * child)236 setChild	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child)
237 {
238 	if	(tree->children == NULL)
239 	{
240 		tree->createChildrenList(tree);
241 	}
242 	tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE);
243 }
244 
245 static void    *
deleteChild(pANTLR3_BASE_TREE tree,ANTLR3_UINT32 i)246 deleteChild	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
247 {
248 	if	( tree->children == NULL)
249 	{
250 		return	NULL;
251 	}
252 
253 	return  tree->children->remove(tree->children, i);
254 }
255 
256 static void    *
dupTree(pANTLR3_BASE_TREE tree)257 dupTree		(pANTLR3_BASE_TREE tree)
258 {
259 	pANTLR3_BASE_TREE	newTree;
260 	ANTLR3_UINT32	i;
261 	ANTLR3_UINT32	s;
262 
263 	newTree = tree->dupNode	    (tree);
264 
265 	if	(tree->children != NULL)
266 	{
267 		s	    = tree->children->size  (tree->children);
268 
269 		for	(i = 0; i < s; i++)
270 		{
271 			pANTLR3_BASE_TREE    t;
272 			pANTLR3_BASE_TREE    newNode;
273 
274 			t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
275 
276 			if  (t!= NULL)
277 			{
278 				newNode	    = t->dupTree(t);
279 				newTree->addChild(newTree, newNode);
280 			}
281 		}
282 	}
283 
284 	return newTree;
285 }
286 
287 static pANTLR3_STRING
toStringTree(pANTLR3_BASE_TREE tree)288 toStringTree	(pANTLR3_BASE_TREE tree)
289 {
290 	pANTLR3_STRING  string;
291 	ANTLR3_UINT32   i;
292 	ANTLR3_UINT32   n;
293 	pANTLR3_BASE_TREE   t;
294 
295 	if	(tree->children == NULL || tree->children->size(tree->children) == 0)
296 	{
297 		return	tree->toString(tree);
298 	}
299 
300 	/* Need a new string with nothing at all in it.
301 	*/
302 	string	= tree->strFactory->newRaw(tree->strFactory);
303 
304 	if	(tree->isNilNode(tree) == ANTLR3_FALSE)
305 	{
306 		string->append8	(string, "(");
307 		string->appendS	(string, tree->toString(tree));
308 		string->append8	(string, " ");
309 	}
310 	if	(tree->children != NULL)
311 	{
312 		n = tree->children->size(tree->children);
313 
314 		for	(i = 0; i < n; i++)
315 		{
316 			t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
317 
318 			if  (i > 0)
319 			{
320 				string->append8(string, " ");
321 			}
322 			string->appendS(string, t->toStringTree(t));
323 		}
324 	}
325 	if	(tree->isNilNode(tree) == ANTLR3_FALSE)
326 	{
327 		string->append8(string,")");
328 	}
329 
330 	return  string;
331 }
332 
333 /// Delete children from start to stop and replace with t even if t is
334 /// a list (nil-root tree). Num of children can increase or decrease.
335 /// For huge child lists, inserting children can force walking rest of
336 /// children to set their child index; could be slow.
337 ///
338 static void
replaceChildren(pANTLR3_BASE_TREE parent,ANTLR3_INT32 startChildIndex,ANTLR3_INT32 stopChildIndex,pANTLR3_BASE_TREE newTree)339 replaceChildren		(pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree)
340 {
341 	ANTLR3_INT32	replacingHowMany;		// How many nodes will go away
342 	ANTLR3_INT32	replacingWithHowMany;	// How many nodes will replace them
343 	ANTLR3_INT32	numNewChildren;			// Tracking variable
344 	ANTLR3_INT32	delta;					// Difference in new vs existing count
345 
346 	ANTLR3_INT32	i;
347 	ANTLR3_INT32	j;
348 
349 	pANTLR3_VECTOR	newChildren;			// Iterator for whatever we are going to add in
350 	ANTLR3_BOOLEAN	freeNewChildren;		// Whether we created the iterator locally or reused it
351 
352 	if	(parent->children == NULL)
353 	{
354 		ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars);
355 		return;
356 	}
357 
358 	// Either use the existing list of children in the supplied nil node, or build a vector of the
359 	// tree we were given if it is not a nil node, then we treat both situations exactly the same
360 	//
361 	if	(newTree->isNilNode(newTree))
362 	{
363 		newChildren = newTree->children;
364 		freeNewChildren = ANTLR3_FALSE;		// We must NO free this memory
365 	}
366 	else
367 	{
368 		newChildren = antlr3VectorNew(1);
369 		if	(newChildren == NULL)
370 		{
371 			ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!");
372 			exit(1);
373 		}
374 		newChildren->add(newChildren, (void *)newTree, NULL);
375 
376 		freeNewChildren = ANTLR3_TRUE;		// We must free this memory
377 	}
378 
379 	// Initialize
380 	//
381 	replacingHowMany		= stopChildIndex - startChildIndex + 1;
382 	replacingWithHowMany	= newChildren->size(newChildren);
383 	delta					= replacingHowMany - replacingWithHowMany;
384 	numNewChildren			= newChildren->size(newChildren);
385 
386 	// If it is the same number of nodes, then do a direct replacement
387 	//
388 	if	(delta == 0)
389 	{
390 		pANTLR3_BASE_TREE	child;
391 
392 		// Same number of nodes
393 		//
394 		j	= 0;
395 		for	(i = startChildIndex; i <= stopChildIndex; i++)
396 		{
397 			child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j);
398 			parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE);
399 			child->setParent(child, parent);
400 			child->setChildIndex(child, i);
401 		}
402 	}
403 	else if (delta > 0)
404 	{
405 		ANTLR3_UINT32	indexToDelete;
406 
407 		// Less nodes than there were before
408 		// reuse what we have then delete the rest
409 		//
410 		for	(j = 0; j < numNewChildren; j++)
411 		{
412 			parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
413 		}
414 
415 		// We just delete the same index position until done
416 		//
417 		indexToDelete = startChildIndex + numNewChildren;
418 
419 		for	(j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++)
420 		{
421 			parent->children->remove(parent->children, indexToDelete);
422 		}
423 
424 		parent->freshenPACIndexes(parent, startChildIndex);
425 	}
426 	else
427 	{
428 		ANTLR3_UINT32 numToInsert;
429 
430 		// More nodes than there were before
431 		// Use what we can, then start adding
432 		//
433 		for	(j = 0; j < replacingHowMany; j++)
434 		{
435 			parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
436 		}
437 
438 		numToInsert = replacingWithHowMany - replacingHowMany;
439 
440 		for	(j = replacingHowMany; j < replacingWithHowMany; j++)
441 		{
442 			parent->children->add(parent->children, newChildren->get(newChildren, j), NULL);
443 		}
444 
445 		parent->freshenPACIndexes(parent, startChildIndex);
446 	}
447 
448 	if	(freeNewChildren == ANTLR3_TRUE)
449 	{
450 		ANTLR3_FREE(newChildren->elements);
451 		newChildren->elements = NULL;
452 		newChildren->size = 0;
453 		ANTLR3_FREE(newChildren);		// Will not free the nodes
454 	}
455 }
456 
457 /// Set the parent and child indexes for all children of the
458 /// supplied tree.
459 ///
460 static	void
freshenPACIndexesAll(pANTLR3_BASE_TREE tree)461 freshenPACIndexesAll(pANTLR3_BASE_TREE tree)
462 {
463 	tree->freshenPACIndexes(tree, 0);
464 }
465 
466 /// Set the parent and child indexes for some of the children of the
467 /// supplied tree, starting with the child at the supplied index.
468 ///
469 static	void
freshenPACIndexes(pANTLR3_BASE_TREE tree,ANTLR3_UINT32 offset)470 freshenPACIndexes	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset)
471 {
472 	ANTLR3_UINT32	count;
473 	ANTLR3_UINT32	c;
474 
475 	count	= tree->getChildCount(tree);		// How many children do we have
476 
477 	// Loop from the supplied index and set the indexes and parent
478 	//
479 	for	(c = offset; c < count; c++)
480 	{
481 		pANTLR3_BASE_TREE	child;
482 
483 		child = tree->getChild(tree, c);
484 
485 		child->setChildIndex(child, c);
486 		child->setParent(child, tree);
487 	}
488 }
489 
490