1/// \file 2/// Defines the implementation of the common node stream the default 3/// tree node stream used by ANTLR. 4/// 5 6// [The "BSD licence"] 7// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC 8// http://www.temporal-wave.com 9// http://www.linkedin.com/in/jimidle 10// 11// All rights reserved. 12// 13// Redistribution and use in source and binary forms, with or without 14// modification, are permitted provided that the following conditions 15// are met: 16// 1. Redistributions of source code must retain the above copyright 17// notice, this list of conditions and the following disclaimer. 18// 2. Redistributions in binary form must reproduce the above copyright 19// notice, this list of conditions and the following disclaimer in the 20// documentation and/or other materials provided with the distribution. 21// 3. The name of the author may not be used to endorse or promote products 22// derived from this software without specific prior written permission. 23// 24// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 25// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 26// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 27// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 28// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 29// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 30// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 31// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 33// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 35#include <antlr3commontreenodestream.h> 36 37#ifdef ANTLR3_WINDOWS 38#pragma warning( disable : 4100 ) 39#endif 40 41// COMMON TREE STREAM API 42// 43static void addNavigationNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT32 ttype); 44static ANTLR3_BOOLEAN hasUniqueNavigationNodes (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 45static pANTLR3_BASE_TREE newDownNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 46static pANTLR3_BASE_TREE newUpNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 47static void reset (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 48static void push (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_INT32 index); 49static ANTLR3_INT32 pop (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 50//static ANTLR3_INT32 index (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 51static ANTLR3_UINT32 getLookaheadSize (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 52// TREE NODE STREAM API 53// 54static pANTLR3_BASE_TREE_ADAPTOR getTreeAdaptor (pANTLR3_TREE_NODE_STREAM tns); 55static pANTLR3_BASE_TREE getTreeSource (pANTLR3_TREE_NODE_STREAM tns); 56static pANTLR3_BASE_TREE _LT (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k); 57static pANTLR3_BASE_TREE get (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k); 58static void setUniqueNavigationNodes (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_BOOLEAN uniqueNavigationNodes); 59static pANTLR3_STRING toString (pANTLR3_TREE_NODE_STREAM tns); 60static pANTLR3_STRING toStringSS (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop); 61static void toStringWork (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf); 62static void replaceChildren (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t); 63 64// INT STREAM API 65// 66static void consume (pANTLR3_INT_STREAM is); 67static ANTLR3_MARKER tindex (pANTLR3_INT_STREAM is); 68static ANTLR3_UINT32 _LA (pANTLR3_INT_STREAM is, ANTLR3_INT32 i); 69static ANTLR3_MARKER mark (pANTLR3_INT_STREAM is); 70static void release (pANTLR3_INT_STREAM is, ANTLR3_MARKER marker); 71static void rewindMark (pANTLR3_INT_STREAM is, ANTLR3_MARKER marker); 72static void rewindLast (pANTLR3_INT_STREAM is); 73static void seek (pANTLR3_INT_STREAM is, ANTLR3_MARKER index); 74static ANTLR3_UINT32 size (pANTLR3_INT_STREAM is); 75 76 77// Helper functions 78// 79static void fillBuffer (pANTLR3_COMMON_TREE_NODE_STREAM ctns, pANTLR3_BASE_TREE t); 80static void fillBufferRoot (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 81 82// Constructors 83// 84static void antlr3TreeNodeStreamFree (pANTLR3_TREE_NODE_STREAM tns); 85static void antlr3CommonTreeNodeStreamFree (pANTLR3_COMMON_TREE_NODE_STREAM ctns); 86 87ANTLR3_API pANTLR3_TREE_NODE_STREAM 88antlr3TreeNodeStreamNew() 89{ 90 pANTLR3_TREE_NODE_STREAM stream; 91 92 // Memory for the interface structure 93 // 94 stream = (pANTLR3_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_TREE_NODE_STREAM)); 95 96 if (stream == NULL) 97 { 98 return NULL; 99 } 100 101 // Install basic API 102 // 103 stream->replaceChildren = replaceChildren; 104 stream->free = antlr3TreeNodeStreamFree; 105 106 return stream; 107} 108 109static void 110antlr3TreeNodeStreamFree(pANTLR3_TREE_NODE_STREAM stream) 111{ 112 ANTLR3_FREE(stream); 113} 114 115ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM 116antlr3CommonTreeNodeStreamNewTree(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 hint) 117{ 118 pANTLR3_COMMON_TREE_NODE_STREAM stream; 119 120 stream = antlr3CommonTreeNodeStreamNew(tree->strFactory, hint); 121 122 if (stream == NULL) 123 { 124 return NULL; 125 } 126 stream->root = tree; 127 128 return stream; 129} 130 131ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM 132antlr3CommonTreeNodeStreamNewStream(pANTLR3_COMMON_TREE_NODE_STREAM inStream) 133{ 134 pANTLR3_COMMON_TREE_NODE_STREAM stream; 135 136 // Memory for the interface structure 137 // 138 stream = (pANTLR3_COMMON_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE_NODE_STREAM)); 139 140 if (stream == NULL) 141 { 142 return NULL; 143 } 144 145 // Copy in all the reusable parts of the originating stream and create new 146 // pieces where necessary. 147 // 148 149 // String factory for tree walker 150 // 151 stream->stringFactory = inStream->stringFactory; 152 153 // Create an adaptor for the common tree node stream 154 // 155 stream->adaptor = inStream->adaptor; 156 157 // Create space for the tree node stream interface 158 // 159 stream->tnstream = antlr3TreeNodeStreamNew(); 160 161 if (stream->tnstream == NULL) 162 { 163 stream->free (stream); 164 165 return NULL; 166 } 167 168 // Create space for the INT_STREAM interface 169 // 170 stream->tnstream->istream = antlr3IntStreamNew(); 171 172 if (stream->tnstream->istream == NULL) 173 { 174 stream->tnstream->free (stream->tnstream); 175 stream->free (stream); 176 177 return NULL; 178 } 179 180 // Install the common tree node stream API 181 // 182 stream->addNavigationNode = addNavigationNode; 183 stream->hasUniqueNavigationNodes = hasUniqueNavigationNodes; 184 stream->newDownNode = newDownNode; 185 stream->newUpNode = newUpNode; 186 stream->reset = reset; 187 stream->push = push; 188 stream->pop = pop; 189 stream->getLookaheadSize = getLookaheadSize; 190 191 stream->free = antlr3CommonTreeNodeStreamFree; 192 193 // Install the tree node stream API 194 // 195 stream->tnstream->getTreeAdaptor = getTreeAdaptor; 196 stream->tnstream->getTreeSource = getTreeSource; 197 stream->tnstream->_LT = _LT; 198 stream->tnstream->setUniqueNavigationNodes = setUniqueNavigationNodes; 199 stream->tnstream->toString = toString; 200 stream->tnstream->toStringSS = toStringSS; 201 stream->tnstream->toStringWork = toStringWork; 202 stream->tnstream->get = get; 203 204 // Install INT_STREAM interface 205 // 206 stream->tnstream->istream->consume = consume; 207 stream->tnstream->istream->index = tindex; 208 stream->tnstream->istream->_LA = _LA; 209 stream->tnstream->istream->mark = mark; 210 stream->tnstream->istream->release = release; 211 stream->tnstream->istream->rewind = rewindMark; 212 stream->tnstream->istream->rewindLast = rewindLast; 213 stream->tnstream->istream->seek = seek; 214 stream->tnstream->istream->size = size; 215 216 // Initialize data elements of INT stream 217 // 218 stream->tnstream->istream->type = ANTLR3_COMMONTREENODE; 219 stream->tnstream->istream->super = (stream->tnstream); 220 221 // Initialize data elements of TREE stream 222 // 223 stream->tnstream->ctns = stream; 224 225 // Initialize data elements of the COMMON TREE NODE stream 226 // 227 stream->super = NULL; 228 stream->uniqueNavigationNodes = ANTLR3_FALSE; 229 stream->markers = NULL; 230 stream->nodeStack = inStream->nodeStack; 231 232 // Create the node list map 233 // 234 stream->nodes = antlr3VectorNew(DEFAULT_INITIAL_BUFFER_SIZE); 235 stream->p = -1; 236 237 // Install the navigation nodes 238 // 239 240 // Install the navigation nodes 241 // 242 antlr3SetCTAPI(&(stream->UP)); 243 antlr3SetCTAPI(&(stream->DOWN)); 244 antlr3SetCTAPI(&(stream->EOF_NODE)); 245 antlr3SetCTAPI(&(stream->INVALID_NODE)); 246 247 stream->UP.token = inStream->UP.token; 248 inStream->UP.token->strFactory = stream->stringFactory; 249 stream->DOWN.token = inStream->DOWN.token; 250 inStream->DOWN.token->strFactory = stream->stringFactory; 251 stream->EOF_NODE.token = inStream->EOF_NODE.token; 252 inStream->EOF_NODE.token->strFactory = stream->stringFactory; 253 stream->INVALID_NODE.token = inStream->INVALID_NODE.token; 254 inStream->INVALID_NODE.token->strFactory= stream->stringFactory; 255 256 // Reuse the root tree of the originating stream 257 // 258 stream->root = inStream->root; 259 260 // Signal that this is a rewriting stream so we don't 261 // free the originating tree. Anything that we rewrite or 262 // duplicate here will be done through the adaptor or 263 // the original tree factory. 264 // 265 stream->isRewriter = ANTLR3_TRUE; 266 return stream; 267} 268 269ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM 270antlr3CommonTreeNodeStreamNew(pANTLR3_STRING_FACTORY strFactory, ANTLR3_UINT32 hint) 271{ 272 pANTLR3_COMMON_TREE_NODE_STREAM stream; 273 pANTLR3_COMMON_TOKEN token; 274 275 // Memory for the interface structure 276 // 277 stream = (pANTLR3_COMMON_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE_NODE_STREAM)); 278 279 if (stream == NULL) 280 { 281 return NULL; 282 } 283 284 // String factory for tree walker 285 // 286 stream->stringFactory = strFactory; 287 288 // Create an adaptor for the common tree node stream 289 // 290 stream->adaptor = ANTLR3_TREE_ADAPTORNew(strFactory); 291 292 if (stream->adaptor == NULL) 293 { 294 stream->free(stream); 295 return NULL; 296 } 297 298 // Create space for the tree node stream interface 299 // 300 stream->tnstream = antlr3TreeNodeStreamNew(); 301 302 if (stream->tnstream == NULL) 303 { 304 stream->adaptor->free (stream->adaptor); 305 stream->free (stream); 306 307 return NULL; 308 } 309 310 // Create space for the INT_STREAM interface 311 // 312 stream->tnstream->istream = antlr3IntStreamNew(); 313 314 if (stream->tnstream->istream == NULL) 315 { 316 stream->adaptor->free (stream->adaptor); 317 stream->tnstream->free (stream->tnstream); 318 stream->free (stream); 319 320 return NULL; 321 } 322 323 // Install the common tree node stream API 324 // 325 stream->addNavigationNode = addNavigationNode; 326 stream->hasUniqueNavigationNodes = hasUniqueNavigationNodes; 327 stream->newDownNode = newDownNode; 328 stream->newUpNode = newUpNode; 329 stream->reset = reset; 330 stream->push = push; 331 stream->pop = pop; 332 333 stream->free = antlr3CommonTreeNodeStreamFree; 334 335 // Install the tree node stream API 336 // 337 stream->tnstream->getTreeAdaptor = getTreeAdaptor; 338 stream->tnstream->getTreeSource = getTreeSource; 339 stream->tnstream->_LT = _LT; 340 stream->tnstream->setUniqueNavigationNodes = setUniqueNavigationNodes; 341 stream->tnstream->toString = toString; 342 stream->tnstream->toStringSS = toStringSS; 343 stream->tnstream->toStringWork = toStringWork; 344 stream->tnstream->get = get; 345 346 // Install INT_STREAM interface 347 // 348 stream->tnstream->istream->consume = consume; 349 stream->tnstream->istream->index = tindex; 350 stream->tnstream->istream->_LA = _LA; 351 stream->tnstream->istream->mark = mark; 352 stream->tnstream->istream->release = release; 353 stream->tnstream->istream->rewind = rewindMark; 354 stream->tnstream->istream->rewindLast = rewindLast; 355 stream->tnstream->istream->seek = seek; 356 stream->tnstream->istream->size = size; 357 358 // Initialize data elements of INT stream 359 // 360 stream->tnstream->istream->type = ANTLR3_COMMONTREENODE; 361 stream->tnstream->istream->super = (stream->tnstream); 362 363 // Initialize data elements of TREE stream 364 // 365 stream->tnstream->ctns = stream; 366 367 // Initialize data elements of the COMMON TREE NODE stream 368 // 369 stream->super = NULL; 370 stream->uniqueNavigationNodes = ANTLR3_FALSE; 371 stream->markers = NULL; 372 stream->nodeStack = antlr3StackNew(INITIAL_CALL_STACK_SIZE); 373 374 // Create the node list map 375 // 376 if (hint == 0) 377 { 378 hint = DEFAULT_INITIAL_BUFFER_SIZE; 379 } 380 stream->nodes = antlr3VectorNew(hint); 381 stream->p = -1; 382 383 // Install the navigation nodes 384 // 385 antlr3SetCTAPI(&(stream->UP)); 386 antlr3SetCTAPI(&(stream->DOWN)); 387 antlr3SetCTAPI(&(stream->EOF_NODE)); 388 antlr3SetCTAPI(&(stream->INVALID_NODE)); 389 390 token = antlr3CommonTokenNew(ANTLR3_TOKEN_UP); 391 token->strFactory = strFactory; 392 token->textState = ANTLR3_TEXT_CHARP; 393 token->tokText.chars = (pANTLR3_UCHAR)"UP"; 394 stream->UP.token = token; 395 396 token = antlr3CommonTokenNew(ANTLR3_TOKEN_DOWN); 397 token->strFactory = strFactory; 398 token->textState = ANTLR3_TEXT_CHARP; 399 token->tokText.chars = (pANTLR3_UCHAR)"DOWN"; 400 stream->DOWN.token = token; 401 402 token = antlr3CommonTokenNew(ANTLR3_TOKEN_EOF); 403 token->strFactory = strFactory; 404 token->textState = ANTLR3_TEXT_CHARP; 405 token->tokText.chars = (pANTLR3_UCHAR)"EOF"; 406 stream->EOF_NODE.token = token; 407 408 token = antlr3CommonTokenNew(ANTLR3_TOKEN_INVALID); 409 token->strFactory = strFactory; 410 token->textState = ANTLR3_TEXT_CHARP; 411 token->tokText.chars = (pANTLR3_UCHAR)"INVALID"; 412 stream->INVALID_NODE.token = token; 413 414 415 return stream; 416} 417 418/// Free up any resources that belong to this common tree node stream. 419/// 420static void antlr3CommonTreeNodeStreamFree (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 421{ 422 423 // If this is a rewrting stream, then certain resources 424 // belong to the originating node stream and we do not 425 // free them here. 426 // 427 if (ctns->isRewriter != ANTLR3_TRUE) 428 { 429 ctns->adaptor ->free (ctns->adaptor); 430 431 if (ctns->nodeStack != NULL) 432 { 433 ctns->nodeStack->free(ctns->nodeStack); 434 } 435 436 ANTLR3_FREE(ctns->INVALID_NODE.token); 437 ANTLR3_FREE(ctns->EOF_NODE.token); 438 ANTLR3_FREE(ctns->DOWN.token); 439 ANTLR3_FREE(ctns->UP.token); 440 } 441 442 if (ctns->nodes != NULL) 443 { 444 ctns->nodes ->free (ctns->nodes); 445 } 446 ctns->tnstream->istream ->free (ctns->tnstream->istream); 447 ctns->tnstream ->free (ctns->tnstream); 448 449 450 ANTLR3_FREE(ctns); 451} 452 453// ------------------------------------------------------------------------------ 454// Local helpers 455// 456 457/// Walk and fill the tree node buffer from the root tree 458/// 459static void 460fillBufferRoot(pANTLR3_COMMON_TREE_NODE_STREAM ctns) 461{ 462 // Call the generic buffer routine with the root as the 463 // argument 464 // 465 fillBuffer(ctns, ctns->root); 466 ctns->p = 0; // Indicate we are at buffer start 467} 468 469/// Walk tree with depth-first-search and fill nodes buffer. 470/// Don't add in DOWN, UP nodes if the supplied tree is a list (t is isNilNode) 471// such as the root tree is. 472/// 473static void 474fillBuffer(pANTLR3_COMMON_TREE_NODE_STREAM ctns, pANTLR3_BASE_TREE t) 475{ 476 ANTLR3_BOOLEAN nilNode; 477 ANTLR3_UINT32 nCount; 478 ANTLR3_UINT32 c; 479 480 nilNode = ctns->adaptor->isNilNode(ctns->adaptor, t); 481 482 // If the supplied node is not a nil (list) node then we 483 // add in the node itself to the vector 484 // 485 if (nilNode == ANTLR3_FALSE) 486 { 487 ctns->nodes->add(ctns->nodes, t, NULL); 488 } 489 490 // Only add a DOWN node if the tree is not a nil tree and 491 // the tree does have children. 492 // 493 nCount = t->getChildCount(t); 494 495 if (nilNode == ANTLR3_FALSE && nCount>0) 496 { 497 ctns->addNavigationNode(ctns, ANTLR3_TOKEN_DOWN); 498 } 499 500 // We always add any children the tree contains, which is 501 // a recursive call to this function, which will cause similar 502 // recursion and implement a depth first addition 503 // 504 for (c = 0; c < nCount; c++) 505 { 506 fillBuffer(ctns, ctns->adaptor->getChild(ctns->adaptor, t, c)); 507 } 508 509 // If the tree had children and was not a nil (list) node, then we 510 // we need to add an UP node here to match the DOWN node 511 // 512 if (nilNode == ANTLR3_FALSE && nCount > 0) 513 { 514 ctns->addNavigationNode(ctns, ANTLR3_TOKEN_UP); 515 } 516} 517 518 519// ------------------------------------------------------------------------------ 520// Interface functions 521// 522 523/// Reset the input stream to the start of the input nodes. 524/// 525static void 526reset (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 527{ 528 if (ctns->p != -1) 529 { 530 ctns->p = 0; 531 } 532 ctns->tnstream->istream->lastMarker = 0; 533 534 535 // Free and reset the node stack only if this is not 536 // a rewriter, which is going to reuse the originating 537 // node streams node stack 538 // 539 if (ctns->isRewriter != ANTLR3_TRUE) 540 { 541 if (ctns->nodeStack != NULL) 542 { 543 ctns->nodeStack->free(ctns->nodeStack); 544 ctns->nodeStack = antlr3StackNew(INITIAL_CALL_STACK_SIZE); 545 } 546 } 547} 548 549 550static pANTLR3_BASE_TREE 551LB(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k) 552{ 553 if ( k==0) 554 { 555 return &(tns->ctns->INVALID_NODE.baseTree); 556 } 557 558 if ( (tns->ctns->p - k) < 0) 559 { 560 return &(tns->ctns->INVALID_NODE.baseTree); 561 } 562 563 return tns->ctns->nodes->get(tns->ctns->nodes, tns->ctns->p - k); 564} 565 566/// Get tree node at current input pointer + i ahead where i=1 is next node. 567/// i<0 indicates nodes in the past. So -1 is previous node and -2 is 568/// two nodes ago. LT(0) is undefined. For i>=n, return null. 569/// Return null for LT(0) and any index that results in an absolute address 570/// that is negative. 571/// 572/// This is analogous to the _LT() method of the TokenStream, but this 573/// returns a tree node instead of a token. Makes code gen identical 574/// for both parser and tree grammars. :) 575/// 576static pANTLR3_BASE_TREE 577_LT (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k) 578{ 579 if (tns->ctns->p == -1) 580 { 581 fillBufferRoot(tns->ctns); 582 } 583 584 if (k < 0) 585 { 586 return LB(tns, -k); 587 } 588 else if (k == 0) 589 { 590 return &(tns->ctns->INVALID_NODE.baseTree); 591 } 592 593 // k was a legitimate request, 594 // 595 if (( tns->ctns->p + k - 1) >= (ANTLR3_INT32)(tns->ctns->nodes->count)) 596 { 597 return &(tns->ctns->EOF_NODE.baseTree); 598 } 599 600 return tns->ctns->nodes->get(tns->ctns->nodes, tns->ctns->p + k - 1); 601} 602 603/// Where is this stream pulling nodes from? This is not the name, but 604/// the object that provides node objects. 605/// 606static pANTLR3_BASE_TREE 607getTreeSource (pANTLR3_TREE_NODE_STREAM tns) 608{ 609 return tns->ctns->root; 610} 611 612/// Consume the next node from the input stream 613/// 614static void 615consume (pANTLR3_INT_STREAM is) 616{ 617 pANTLR3_TREE_NODE_STREAM tns; 618 pANTLR3_COMMON_TREE_NODE_STREAM ctns; 619 620 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 621 ctns = tns->ctns; 622 623 if (ctns->p == -1) 624 { 625 fillBufferRoot(ctns); 626 } 627 ctns->p++; 628} 629 630static ANTLR3_UINT32 631_LA (pANTLR3_INT_STREAM is, ANTLR3_INT32 i) 632{ 633 pANTLR3_TREE_NODE_STREAM tns; 634 pANTLR3_BASE_TREE t; 635 636 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 637 638 // Ask LT for the 'token' at that position 639 // 640 t = tns->_LT(tns, i); 641 642 if (t == NULL) 643 { 644 return ANTLR3_TOKEN_INVALID; 645 } 646 647 // Token node was there so return the type of it 648 // 649 return t->getType(t); 650} 651 652/// Mark the state of the input stream so that we can come back to it 653/// after a syntactic predicate and so on. 654/// 655static ANTLR3_MARKER 656mark (pANTLR3_INT_STREAM is) 657{ 658 pANTLR3_TREE_NODE_STREAM tns; 659 pANTLR3_COMMON_TREE_NODE_STREAM ctns; 660 661 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 662 ctns = tns->ctns; 663 664 if (tns->ctns->p == -1) 665 { 666 fillBufferRoot(tns->ctns); 667 } 668 669 // Return the current mark point 670 // 671 ctns->tnstream->istream->lastMarker = ctns->tnstream->istream->index(ctns->tnstream->istream); 672 673 return ctns->tnstream->istream->lastMarker; 674} 675 676static void 677release (pANTLR3_INT_STREAM is, ANTLR3_MARKER marker) 678{ 679} 680 681/// Rewind the current state of the tree walk to the state it 682/// was in when mark() was called and it returned marker. Also, 683/// wipe out the lookahead which will force reloading a few nodes 684/// but it is better than making a copy of the lookahead buffer 685/// upon mark(). 686/// 687static void 688rewindMark (pANTLR3_INT_STREAM is, ANTLR3_MARKER marker) 689{ 690 is->seek(is, marker); 691} 692 693static void 694rewindLast (pANTLR3_INT_STREAM is) 695{ 696 is->seek(is, is->lastMarker); 697} 698 699/// consume() ahead until we hit index. Can't just jump ahead--must 700/// spit out the navigation nodes. 701/// 702static void 703seek (pANTLR3_INT_STREAM is, ANTLR3_MARKER index) 704{ 705 pANTLR3_TREE_NODE_STREAM tns; 706 pANTLR3_COMMON_TREE_NODE_STREAM ctns; 707 708 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 709 ctns = tns->ctns; 710 711 ctns->p = ANTLR3_UINT32_CAST(index); 712} 713 714static ANTLR3_MARKER 715tindex (pANTLR3_INT_STREAM is) 716{ 717 pANTLR3_TREE_NODE_STREAM tns; 718 pANTLR3_COMMON_TREE_NODE_STREAM ctns; 719 720 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 721 ctns = tns->ctns; 722 723 return (ANTLR3_MARKER)(ctns->p); 724} 725 726/// Expensive to compute the size of the whole tree while parsing. 727/// This method only returns how much input has been seen so far. So 728/// after parsing it returns true size. 729/// 730static ANTLR3_UINT32 731size (pANTLR3_INT_STREAM is) 732{ 733 pANTLR3_TREE_NODE_STREAM tns; 734 pANTLR3_COMMON_TREE_NODE_STREAM ctns; 735 736 tns = (pANTLR3_TREE_NODE_STREAM)(is->super); 737 ctns = tns->ctns; 738 739 if (ctns->p == -1) 740 { 741 fillBufferRoot(ctns); 742 } 743 744 return ctns->nodes->size(ctns->nodes); 745} 746 747/// As we flatten the tree, we use UP, DOWN nodes to represent 748/// the tree structure. When debugging we need unique nodes 749/// so instantiate new ones when uniqueNavigationNodes is true. 750/// 751static void 752addNavigationNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT32 ttype) 753{ 754 pANTLR3_BASE_TREE node; 755 756 node = NULL; 757 758 if (ttype == ANTLR3_TOKEN_DOWN) 759 { 760 if (ctns->hasUniqueNavigationNodes(ctns) == ANTLR3_TRUE) 761 { 762 node = ctns->newDownNode(ctns); 763 } 764 else 765 { 766 node = &(ctns->DOWN.baseTree); 767 } 768 } 769 else 770 { 771 if (ctns->hasUniqueNavigationNodes(ctns) == ANTLR3_TRUE) 772 { 773 node = ctns->newUpNode(ctns); 774 } 775 else 776 { 777 node = &(ctns->UP.baseTree); 778 } 779 } 780 781 // Now add the node we decided upon. 782 // 783 ctns->nodes->add(ctns->nodes, node, NULL); 784} 785 786 787static pANTLR3_BASE_TREE_ADAPTOR 788getTreeAdaptor (pANTLR3_TREE_NODE_STREAM tns) 789{ 790 return tns->ctns->adaptor; 791} 792 793static ANTLR3_BOOLEAN 794hasUniqueNavigationNodes (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 795{ 796 return ctns->uniqueNavigationNodes; 797} 798 799static void 800setUniqueNavigationNodes (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_BOOLEAN uniqueNavigationNodes) 801{ 802 tns->ctns->uniqueNavigationNodes = uniqueNavigationNodes; 803} 804 805 806/// Print out the entire tree including DOWN/UP nodes. Uses 807/// a recursive walk. Mostly useful for testing as it yields 808/// the token types not text. 809/// 810static pANTLR3_STRING 811toString (pANTLR3_TREE_NODE_STREAM tns) 812{ 813 814 return tns->toStringSS(tns, tns->ctns->root, NULL); 815} 816 817static pANTLR3_STRING 818toStringSS (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop) 819{ 820 pANTLR3_STRING buf; 821 822 buf = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory); 823 824 tns->toStringWork(tns, start, stop, buf); 825 826 return buf; 827} 828 829static void 830toStringWork (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE p, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf) 831{ 832 833 ANTLR3_UINT32 n; 834 ANTLR3_UINT32 c; 835 836 if (!p->isNilNode(p) ) 837 { 838 pANTLR3_STRING text; 839 840 text = p->toString(p); 841 842 if (text == NULL) 843 { 844 text = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory); 845 846 text->addc (text, ' '); 847 text->addi (text, p->getType(p)); 848 } 849 850 buf->appendS(buf, text); 851 } 852 853 if (p == stop) 854 { 855 return; /* Finished */ 856 } 857 858 n = p->getChildCount(p); 859 860 if (n > 0 && ! p->isNilNode(p) ) 861 { 862 buf->addc (buf, ' '); 863 buf->addi (buf, ANTLR3_TOKEN_DOWN); 864 } 865 866 for (c = 0; c<n ; c++) 867 { 868 pANTLR3_BASE_TREE child; 869 870 child = p->getChild(p, c); 871 tns->toStringWork(tns, child, stop, buf); 872 } 873 874 if (n > 0 && ! p->isNilNode(p) ) 875 { 876 buf->addc (buf, ' '); 877 buf->addi (buf, ANTLR3_TOKEN_UP); 878 } 879} 880 881static ANTLR3_UINT32 882getLookaheadSize (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 883{ 884 return ctns->tail < ctns->head 885 ? (ctns->lookAheadLength - ctns->head + ctns->tail) 886 : (ctns->tail - ctns->head); 887} 888 889static pANTLR3_BASE_TREE 890newDownNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 891{ 892 pANTLR3_COMMON_TREE dNode; 893 pANTLR3_COMMON_TOKEN token; 894 895 token = antlr3CommonTokenNew(ANTLR3_TOKEN_DOWN); 896 token->textState = ANTLR3_TEXT_CHARP; 897 token->tokText.chars = (pANTLR3_UCHAR)"DOWN"; 898 dNode = antlr3CommonTreeNewFromToken(token); 899 900 return &(dNode->baseTree); 901} 902 903static pANTLR3_BASE_TREE 904newUpNode (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 905{ 906 pANTLR3_COMMON_TREE uNode; 907 pANTLR3_COMMON_TOKEN token; 908 909 token = antlr3CommonTokenNew(ANTLR3_TOKEN_UP); 910 token->textState = ANTLR3_TEXT_CHARP; 911 token->tokText.chars = (pANTLR3_UCHAR)"UP"; 912 uNode = antlr3CommonTreeNewFromToken(token); 913 914 return &(uNode->baseTree); 915} 916 917/// Replace from start to stop child index of parent with t, which might 918/// be a list. Number of children may be different 919/// after this call. The stream is notified because it is walking the 920/// tree and might need to know you are monkey-ing with the underlying 921/// tree. Also, it might be able to modify the node stream to avoid 922/// re-streaming for future phases. 923/// 924/// If parent is null, don't do anything; must be at root of overall tree. 925/// Can't replace whatever points to the parent externally. Do nothing. 926/// 927static void 928replaceChildren (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t) 929{ 930 if (parent != NULL) 931 { 932 pANTLR3_BASE_TREE_ADAPTOR adaptor; 933 pANTLR3_COMMON_TREE_ADAPTOR cta; 934 935 adaptor = tns->getTreeAdaptor(tns); 936 cta = (pANTLR3_COMMON_TREE_ADAPTOR)(adaptor->super); 937 938 adaptor->replaceChildren(adaptor, parent, startChildIndex, stopChildIndex, t); 939 } 940} 941 942static pANTLR3_BASE_TREE 943get (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k) 944{ 945 if (tns->ctns->p == -1) 946 { 947 fillBufferRoot(tns->ctns); 948 } 949 950 return tns->ctns->nodes->get(tns->ctns->nodes, k); 951} 952 953static void 954push (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_INT32 index) 955{ 956 ctns->nodeStack->push(ctns->nodeStack, ANTLR3_FUNC_PTR(ctns->p), NULL); // Save current index 957 ctns->tnstream->istream->seek(ctns->tnstream->istream, index); 958} 959 960static ANTLR3_INT32 961pop (pANTLR3_COMMON_TREE_NODE_STREAM ctns) 962{ 963 ANTLR3_INT32 retVal; 964 965 retVal = ANTLR3_UINT32_CAST(ctns->nodeStack->pop(ctns->nodeStack)); 966 ctns->tnstream->istream->seek(ctns->tnstream->istream, retVal); 967 return retVal; 968} 969