1 #include <antlr3basetree.h>
\r
3 #ifdef ANTLR3_WINDOWS
\r
4 #pragma warning( disable : 4100 )
\r
7 // [The "BSD licence"]
\r
8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
\r
9 // http://www.temporal-wave.com
\r
10 // http://www.linkedin.com/in/jimidle
\r
12 // All rights reserved.
\r
14 // Redistribution and use in source and binary forms, with or without
\r
15 // modification, are permitted provided that the following conditions
\r
17 // 1. Redistributions of source code must retain the above copyright
\r
18 // notice, this list of conditions and the following disclaimer.
\r
19 // 2. Redistributions in binary form must reproduce the above copyright
\r
20 // notice, this list of conditions and the following disclaimer in the
\r
21 // documentation and/or other materials provided with the distribution.
\r
22 // 3. The name of the author may not be used to endorse or promote products
\r
23 // derived from this software without specific prior written permission.
\r
25 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
\r
26 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
27 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
\r
28 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
\r
29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
\r
30 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
\r
31 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
\r
32 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
\r
33 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
\r
34 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\r
36 static void * getChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
\r
37 static ANTLR3_UINT32 getChildCount (pANTLR3_BASE_TREE tree);
\r
38 static ANTLR3_UINT32 getCharPositionInLine
\r
39 (pANTLR3_BASE_TREE tree);
\r
40 static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree);
\r
41 static pANTLR3_BASE_TREE
\r
42 getFirstChildWithType
\r
43 (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type);
\r
44 static void addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child);
\r
45 static void addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids);
\r
46 static void replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);
\r
48 static void freshenPACIndexesAll(pANTLR3_BASE_TREE tree);
\r
49 static void freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset);
\r
51 static void setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child);
\r
52 static void * deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
\r
53 static void * dupTree (pANTLR3_BASE_TREE tree);
\r
54 static pANTLR3_STRING toStringTree (pANTLR3_BASE_TREE tree);
\r
57 ANTLR3_API pANTLR3_BASE_TREE
\r
58 antlr3BaseTreeNew(pANTLR3_BASE_TREE tree)
\r
61 tree->getChild = getChild;
\r
62 tree->getChildCount = getChildCount;
\r
63 tree->addChild = (void (*)(pANTLR3_BASE_TREE, void *))(addChild);
\r
64 tree->addChildren = addChildren;
\r
65 tree->setChild = setChild;
\r
66 tree->deleteChild = deleteChild;
\r
67 tree->dupTree = dupTree;
\r
68 tree->toStringTree = toStringTree;
\r
69 tree->getCharPositionInLine = getCharPositionInLine;
\r
70 tree->getLine = getLine;
\r
71 tree->replaceChildren = replaceChildren;
\r
72 tree->freshenPACIndexesAll = freshenPACIndexesAll;
\r
73 tree->freshenPACIndexes = freshenPACIndexes;
\r
74 tree->getFirstChildWithType = (void *(*)(pANTLR3_BASE_TREE, ANTLR3_UINT32))(getFirstChildWithType);
\r
75 tree->children = NULL;
\r
76 tree->strFactory = NULL;
\r
78 /* Rest must be filled in by caller.
\r
83 static ANTLR3_UINT32
\r
84 getCharPositionInLine (pANTLR3_BASE_TREE tree)
\r
89 static ANTLR3_UINT32
\r
90 getLine (pANTLR3_BASE_TREE tree)
\r
94 static pANTLR3_BASE_TREE
\r
95 getFirstChildWithType (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type)
\r
100 pANTLR3_BASE_TREE t;
\r
101 if (tree->children != NULL)
\r
103 cs = tree->children->size(tree->children);
\r
104 for (i = 0; i < cs; i++)
\r
106 t = (pANTLR3_BASE_TREE) (tree->children->get(tree->children, i));
\r
107 if (tree->getType(t) == type)
\r
109 return (pANTLR3_BASE_TREE)t;
\r
119 getChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
\r
121 if ( tree->children == NULL
\r
122 || i >= tree->children->size(tree->children))
\r
126 return tree->children->get(tree->children, i);
\r
130 static ANTLR3_UINT32
\r
131 getChildCount (pANTLR3_BASE_TREE tree)
\r
133 if (tree->children == NULL)
\r
139 return tree->children->size(tree->children);
\r
144 addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child)
\r
154 if (child->isNilNode(child) == ANTLR3_TRUE)
\r
156 if (child->children != NULL && child->children == tree->children)
\r
158 // TODO: Change to exception rather than ANTLR3_FPRINTF?
\r
160 ANTLR3_FPRINTF(stderr, "ANTLR3: An attempt was made to add a child list to itself!\n");
\r
164 // Add all of the children's children to this list
\r
166 if (child->children != NULL)
\r
168 if (tree->children == NULL)
\r
170 // We are build ing the tree structure here, so we need not
\r
171 // worry about duplication of pointers as the tree node
\r
172 // factory will only clean up each node once. So we just
\r
173 // copy in the child's children pointer as the child is
\r
174 // a nil node (has not root itself).
\r
176 tree->children = child->children;
\r
177 child->children = NULL;
\r
178 freshenPACIndexesAll(tree);
\r
183 // Need to copy the children
\r
185 n = child->children->size(child->children);
\r
187 for (i = 0; i < n; i++)
\r
189 pANTLR3_BASE_TREE entry;
\r
190 entry = child->children->get(child->children, i);
\r
192 // ANTLR3 lists can be sparse, unlike Array Lists
\r
196 tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free);
\r
204 // Tree we are adding is not a Nil and might have children to copy
\r
206 if (tree->children == NULL)
\r
208 // No children in the tree we are adding to, so create a new list on
\r
209 // the fly to hold them.
\r
211 tree->createChildrenList(tree);
\r
214 tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free);
\r
219 /// Add all elements of the supplied list as children of this node
\r
222 addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids)
\r
227 s = kids->size(kids);
\r
228 for (i = 0; i<s; i++)
\r
230 tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1)));
\r
236 setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child)
\r
238 if (tree->children == NULL)
\r
240 tree->createChildrenList(tree);
\r
242 tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE);
\r
246 deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
\r
248 if ( tree->children == NULL)
\r
253 return tree->children->remove(tree->children, i);
\r
257 dupTree (pANTLR3_BASE_TREE tree)
\r
259 pANTLR3_BASE_TREE newTree;
\r
263 newTree = tree->dupNode (tree);
\r
265 if (tree->children != NULL)
\r
267 s = tree->children->size (tree->children);
\r
269 for (i = 0; i < s; i++)
\r
271 pANTLR3_BASE_TREE t;
\r
272 pANTLR3_BASE_TREE newNode;
\r
274 t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
\r
278 newNode = t->dupTree(t);
\r
279 newTree->addChild(newTree, newNode);
\r
287 static pANTLR3_STRING
\r
288 toStringTree (pANTLR3_BASE_TREE tree)
\r
290 pANTLR3_STRING string;
\r
293 pANTLR3_BASE_TREE t;
\r
295 if (tree->children == NULL || tree->children->size(tree->children) == 0)
\r
297 return tree->toString(tree);
\r
300 /* Need a new string with nothing at all in it.
\r
302 string = tree->strFactory->newRaw(tree->strFactory);
\r
304 if (tree->isNilNode(tree) == ANTLR3_FALSE)
\r
306 string->append8 (string, "(");
\r
307 string->appendS (string, tree->toString(tree));
\r
308 string->append8 (string, " ");
\r
310 if (tree->children != NULL)
\r
312 n = tree->children->size(tree->children);
\r
314 for (i = 0; i < n; i++)
\r
316 t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
\r
320 string->append8(string, " ");
\r
322 string->appendS(string, t->toStringTree(t));
\r
325 if (tree->isNilNode(tree) == ANTLR3_FALSE)
\r
327 string->append8(string,")");
\r
333 /// Delete children from start to stop and replace with t even if t is
\r
334 /// a list (nil-root tree). Num of children can increase or decrease.
\r
335 /// For huge child lists, inserting children can force walking rest of
\r
336 /// children to set their child index; could be slow.
\r
339 replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree)
\r
341 ANTLR3_INT32 replacingHowMany; // How many nodes will go away
\r
342 ANTLR3_INT32 replacingWithHowMany; // How many nodes will replace them
\r
343 ANTLR3_INT32 numNewChildren; // Tracking variable
\r
344 ANTLR3_INT32 delta; // Difference in new vs existing count
\r
349 pANTLR3_VECTOR newChildren; // Iterator for whatever we are going to add in
\r
350 ANTLR3_BOOLEAN freeNewChildren; // Whether we created the iterator locally or reused it
\r
352 if (parent->children == NULL)
\r
354 ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars);
\r
358 // Either use the existing list of children in the supplied nil node, or build a vector of the
\r
359 // tree we were given if it is not a nil node, then we treat both situations exactly the same
\r
361 if (newTree->isNilNode(newTree))
\r
363 newChildren = newTree->children;
\r
364 freeNewChildren = ANTLR3_FALSE; // We must NO free this memory
\r
368 newChildren = antlr3VectorNew(1);
\r
369 if (newChildren == NULL)
\r
371 ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!");
\r
374 newChildren->add(newChildren, (void *)newTree, NULL);
\r
376 freeNewChildren = ANTLR3_TRUE; // We must free this memory
\r
381 replacingHowMany = stopChildIndex - startChildIndex + 1;
\r
382 replacingWithHowMany = newChildren->size(newChildren);
\r
383 delta = replacingHowMany - replacingWithHowMany;
\r
384 numNewChildren = newChildren->size(newChildren);
\r
386 // If it is the same number of nodes, then do a direct replacement
\r
390 pANTLR3_BASE_TREE child;
\r
392 // Same number of nodes
\r
395 for (i = startChildIndex; i <= stopChildIndex; i++)
\r
397 child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j);
\r
398 parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE);
\r
399 child->setParent(child, parent);
\r
400 child->setChildIndex(child, i);
\r
403 else if (delta > 0)
\r
405 ANTLR3_UINT32 indexToDelete;
\r
407 // Less nodes than there were before
\r
408 // reuse what we have then delete the rest
\r
410 for (j = 0; j < numNewChildren; j++)
\r
412 parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
\r
415 // We just delete the same index position until done
\r
417 indexToDelete = startChildIndex + numNewChildren;
\r
419 for (j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++)
\r
421 parent->children->remove(parent->children, indexToDelete);
\r
424 parent->freshenPACIndexes(parent, startChildIndex);
\r
428 ANTLR3_UINT32 numToInsert;
\r
430 // More nodes than there were before
\r
431 // Use what we can, then start adding
\r
433 for (j = 0; j < replacingHowMany; j++)
\r
435 parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
\r
438 numToInsert = replacingWithHowMany - replacingHowMany;
\r
440 for (j = replacingHowMany; j < replacingWithHowMany; j++)
\r
442 parent->children->add(parent->children, newChildren->get(newChildren, j), NULL);
\r
445 parent->freshenPACIndexes(parent, startChildIndex);
\r
448 if (freeNewChildren == ANTLR3_TRUE)
\r
450 ANTLR3_FREE(newChildren->elements);
\r
451 newChildren->elements = NULL;
\r
452 newChildren->size = 0;
\r
453 ANTLR3_FREE(newChildren); // Will not free the nodes
\r
457 /// Set the parent and child indexes for all children of the
\r
461 freshenPACIndexesAll(pANTLR3_BASE_TREE tree)
\r
463 tree->freshenPACIndexes(tree, 0);
\r
466 /// Set the parent and child indexes for some of the children of the
\r
467 /// supplied tree, starting with the child at the supplied index.
\r
470 freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset)
\r
472 ANTLR3_UINT32 count;
\r
475 count = tree->getChildCount(tree); // How many children do we have
\r
477 // Loop from the supplied index and set the indexes and parent
\r
479 for (c = offset; c < count; c++)
\r
481 pANTLR3_BASE_TREE child;
\r
483 child = tree->getChild(tree, c);
\r
485 child->setChildIndex(child, c);
\r
486 child->setParent(child, tree);
\r