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