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
10 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
11 // http://www.temporal-wave.com
12 // http://www.linkedin.com/in/jimidle
14 // All rights reserved.
16 // Redistribution and use in source and binary forms, with or without
17 // modification, are permitted provided that the following conditions
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.
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.
38 #include <antlr3commontree.h>
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);
56 // Factory functions for the Arboretum
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);
64 ANTLR3_API pANTLR3_ARBORETUM
65 antlr3ArboretumNew(pANTLR3_STRING_FACTORY strFactory)
67 pANTLR3_ARBORETUM factory;
71 factory = (pANTLR3_ARBORETUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_ARBORETUM));
77 // Install a vector factory to create, track and free() any child
80 factory->vFactory = antlr3VectorFactoryNew(0);
81 if (factory->vFactory == NULL)
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.
93 factory->nilStack = antlr3StackNew(0);
95 // Install factory API
97 factory->newTree = newPoolTree;
98 factory->newFromTree = newFromTree;
99 factory->newFromToken = newFromToken;
100 factory->close = factoryClose;
102 // Allocate the initial pool
104 factory->thisPool = -1;
105 factory->pools = NULL;
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
111 antlr3SetCTAPI(&factory->unTruc);
113 // Set some initial variables for future copying, including a string factory
114 // that we can use later for converting trees to strings.
116 factory->unTruc.factory = factory;
117 factory->unTruc.baseTree.strFactory = strFactory;
124 newPool(pANTLR3_ARBORETUM factory)
126 // Increment factory count
130 // Ensure we have enough pointers allocated
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
137 // Allocate a new pool for the factory
139 factory->pools[factory->thisPool] =
140 (pANTLR3_COMMON_TREE)
141 ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_COMMON_TREE) * ANTLR3_FACTORY_POOL_SIZE));
144 // Reset the counters
146 factory->nextTree = 0;
153 static pANTLR3_BASE_TREE
154 newPoolTree (pANTLR3_ARBORETUM factory)
156 pANTLR3_COMMON_TREE tree;
158 // If we have anything on the re claim stack, reuse that sucker first
160 tree = factory->nilStack->peek(factory->nilStack);
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
169 factory->nilStack->pop(factory->nilStack);
170 return (pANTLR3_BASE_TREE)tree;
173 // See if we need a new tree pool before allocating a new tree
175 if (factory->nextTree >= ANTLR3_FACTORY_POOL_SIZE)
177 // We ran out of tokens in the current pool, so we need a new pool
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.
185 tree = factory->pools[factory->thisPool] + factory->nextTree;
188 // We have our token pointer now, so we can initialize it to the predefined model.
190 antlr3SetCTAPI(tree);
192 // Set some initial variables for future copying, including a string factory
193 // that we can use later for converting trees to strings.
195 tree->factory = factory;
196 tree->baseTree.strFactory = factory->unTruc.baseTree.strFactory;
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! :-(
203 tree->baseTree.super = tree;
207 return &(tree->baseTree);
211 static pANTLR3_BASE_TREE
212 newFromTree(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree)
214 pANTLR3_BASE_TREE newTree;
216 newTree = factory->newTree(factory);
223 // Pick up the payload we had in the supplied tree
225 ((pANTLR3_COMMON_TREE)(newTree->super))->token = tree->token;
226 newTree->u = tree->baseTree.u; // Copy any user pointer
231 static pANTLR3_BASE_TREE
232 newFromToken(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token)
234 pANTLR3_BASE_TREE newTree;
236 newTree = factory->newTree(factory);
243 // Pick up the payload we had in the supplied tree
245 ((pANTLR3_COMMON_TREE)(newTree->super))->token = token;
251 factoryClose (pANTLR3_ARBORETUM factory)
253 ANTLR3_INT32 poolCount;
255 // First close the vector factory that supplied all the child pointer
258 factory->vFactory->close(factory->vFactory);
260 if (factory->nilStack != NULL)
262 factory->nilStack->free(factory->nilStack);
265 // We now JUST free the pools because the C runtime CommonToken based tree
266 // cannot contain anything that was not made by this factory.
268 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
270 // We can now free this pool allocation
272 ANTLR3_FREE(factory->pools[poolCount]);
273 factory->pools[poolCount] = NULL;
276 // All the pools are deallocated we can free the pointers to the pools
279 ANTLR3_FREE(factory->pools);
281 // Finally, we can free the space for the factory itself
283 ANTLR3_FREE(factory);
288 antlr3SetCTAPI(pANTLR3_COMMON_TREE tree)
292 antlr3BaseTreeNew(&(tree->baseTree));
294 // We need a pointer to ourselves for
295 // the payload and few functions that we
298 tree->baseTree.super = tree;
300 // Common tree overrides
302 tree->baseTree.isNilNode = isNilNode;
303 tree->baseTree.toString = toString;
304 tree->baseTree.dupNode = (void *(*)(pANTLR3_BASE_TREE))(dupNode);
305 tree->baseTree.getLine = getLine;
306 tree->baseTree.getCharPositionInLine = getCharPositionInLine;
307 tree->baseTree.toString = toString;
308 tree->baseTree.getType = getType;
309 tree->baseTree.getText = getText;
310 tree->baseTree.getToken = getToken;
311 tree->baseTree.getParent = getParent;
312 tree->baseTree.setParent = setParent;
313 tree->baseTree.setChildIndex = setChildIndex;
314 tree->baseTree.getChildIndex = getChildIndex;
315 tree->baseTree.createChildrenList = createChildrenList;
316 tree->baseTree.reuse = reuse;
317 tree->baseTree.free = NULL; // Factory trees have no free function
319 tree->baseTree.children = NULL;
321 tree->token = NULL; // No token as yet
322 tree->startIndex = 0;
324 tree->parent = NULL; // No parent yet
325 tree->childIndex = -1;
330 // --------------------------------------
331 // Non factory node constructors.
334 ANTLR3_API pANTLR3_COMMON_TREE
335 antlr3CommonTreeNew()
337 pANTLR3_COMMON_TREE tree;
338 tree = ANTLR3_MALLOC(sizeof(ANTLR3_COMMON_TREE));
345 antlr3SetCTAPI(tree);
350 ANTLR3_API pANTLR3_COMMON_TREE
351 antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token)
353 pANTLR3_COMMON_TREE newTree;
355 newTree = antlr3CommonTreeNew();
362 //Pick up the payload we had in the supplied tree
364 newTree->token = token;
368 /// Create a new vector for holding child nodes using the inbuilt
372 createChildrenList (pANTLR3_BASE_TREE tree)
374 tree->children = ((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory->newVector(((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory);
378 static pANTLR3_COMMON_TOKEN
379 getToken (pANTLR3_BASE_TREE tree)
381 // The token is the payload of the common tree or other implementor
382 // so it is stored within ourselves, which is the super pointer.Note
383 // that whatever the actual token is, it is passed around by its pointer
384 // to the common token implementation, which it may of course surround
385 // with its own super structure.
387 return ((pANTLR3_COMMON_TREE)(tree->super))->token;
390 static pANTLR3_BASE_TREE
391 dupNode (pANTLR3_BASE_TREE tree)
393 // The node we are duplicating is in fact the common tree (that's why we are here)
394 // so we use the super pointer to duplicate.
396 pANTLR3_COMMON_TREE theOld;
398 theOld = (pANTLR3_COMMON_TREE)(tree->super);
400 // The pointer we return is the base implementation of course
402 return theOld->factory->newFromTree(theOld->factory, theOld);
405 static ANTLR3_BOOLEAN
406 isNilNode (pANTLR3_BASE_TREE tree)
408 // This is a Nil tree if it has no payload (Token in our case)
410 if (((pANTLR3_COMMON_TREE)(tree->super))->token == NULL)
421 getType (pANTLR3_BASE_TREE tree)
423 pANTLR3_COMMON_TREE theTree;
425 theTree = (pANTLR3_COMMON_TREE)(tree->super);
427 if (theTree->token == NULL)
433 return theTree->token->getType(theTree->token);
437 static pANTLR3_STRING
438 getText (pANTLR3_BASE_TREE tree)
440 return tree->toString(tree);
443 static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree)
445 pANTLR3_COMMON_TREE cTree;
446 pANTLR3_COMMON_TOKEN token;
448 cTree = (pANTLR3_COMMON_TREE)(tree->super);
450 token = cTree->token;
452 if (token == NULL || token->getLine(token) == 0)
454 if (tree->getChildCount(tree) > 0)
456 pANTLR3_BASE_TREE child;
458 child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
459 return child->getLine(child);
463 return token->getLine(token);
466 static ANTLR3_UINT32 getCharPositionInLine (pANTLR3_BASE_TREE tree)
468 pANTLR3_COMMON_TOKEN token;
470 token = ((pANTLR3_COMMON_TREE)(tree->super))->token;
472 if (token == NULL || token->getCharPositionInLine(token) == -1)
474 if (tree->getChildCount(tree) > 0)
476 pANTLR3_BASE_TREE child;
478 child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0);
480 return child->getCharPositionInLine(child);
484 return token->getCharPositionInLine(token);
487 static pANTLR3_STRING toString (pANTLR3_BASE_TREE tree)
489 if (tree->isNilNode(tree) == ANTLR3_TRUE)
491 pANTLR3_STRING nilNode;
493 nilNode = tree->strFactory->newPtr(tree->strFactory, (pANTLR3_UINT8)"nil", 3);
498 return ((pANTLR3_COMMON_TREE)(tree->super))->token->getText(((pANTLR3_COMMON_TREE)(tree->super))->token);
501 static pANTLR3_BASE_TREE
502 getParent (pANTLR3_BASE_TREE tree)
504 return & (((pANTLR3_COMMON_TREE)(tree->super))->parent->baseTree);
508 setParent (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent)
510 ((pANTLR3_COMMON_TREE)(tree->super))->parent = parent == NULL ? NULL : ((pANTLR3_COMMON_TREE)(parent->super))->parent;
514 setChildIndex (pANTLR3_BASE_TREE tree, ANTLR3_INT32 i)
516 ((pANTLR3_COMMON_TREE)(tree->super))->childIndex = i;
519 getChildIndex (pANTLR3_BASE_TREE tree )
521 return ((pANTLR3_COMMON_TREE)(tree->super))->childIndex;
524 /** Clean up any child vector that the tree might have, so it can be reused,
525 * then add it into the reuse stack.
528 reuse (pANTLR3_BASE_TREE tree)
530 pANTLR3_COMMON_TREE cTree;
532 cTree = (pANTLR3_COMMON_TREE)(tree->super);
534 if (cTree->factory != NULL)
537 if (cTree->baseTree.children != NULL)
540 cTree->baseTree.children->clear(cTree->baseTree.children);
542 cTree->factory->nilStack->push(cTree->factory->nilStack, tree, NULL);