gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/tree/IterativeParseTreeWalker.cpp

   1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
   2  * Use of this file is governed by the BSD 3-clause license that
   3  * can be found in the LICENSE.txt file in the project root.
   4  */
   5
   6 #include "support/CPPUtils.h"
   7
   8 #include "tree/ParseTreeListener.h"
   9 #include "tree/ParseTree.h"
  10 #include "tree/ErrorNode.h"
  11
  12 #include "IterativeParseTreeWalker.h"
  13
  14 using namespace antlr4::tree;
  15
  16 void IterativeParseTreeWalker::walk(ParseTreeListener *listener, ParseTree *t) const {
  17
  18   std::vector<ParseTree *> nodeStack;
  19   std::vector<size_t> indexStack;
  20
  21   ParseTree *currentNode = t;
  22   size_t currentIndex = 0;
  23
  24   while (currentNode != nullptr) {
  25     // pre-order visit
  26     if (antlrcpp::is<ErrorNode *>(currentNode)) {
  27       listener->visitErrorNode(dynamic_cast<ErrorNode *>(currentNode));
  28     } else if (antlrcpp::is<TerminalNode *>(currentNode)) {
  29       listener->visitTerminal((TerminalNode *)currentNode);
  30     } else {
  31       enterRule(listener, currentNode);
  32     }
  33
  34     // Move down to first child, if it exists.
  35     if (!currentNode->children.empty()) {
  36       nodeStack.push_back(currentNode);
  37       indexStack.push_back(currentIndex);
  38       currentIndex = 0;
  39       currentNode = currentNode->children[0];
  40       continue;
  41     }
  42
  43     // No child nodes, so walk tree.
  44     do {
  45       // post-order visit
  46       if (!antlrcpp::is<TerminalNode *>(currentNode)) {
  47         exitRule(listener, currentNode);
  48       }
  49
  50       // No parent, so no siblings.
  51       if (nodeStack.empty()) {
  52         currentNode = nullptr;
  53         currentIndex = 0;
  54         break;
  55       }
  56
  57       // Move to next sibling if possible.
  58       if (nodeStack.back()->children.size() > ++currentIndex) {
  59         currentNode = nodeStack.back()->children[currentIndex];
  60         break;
  61       }
  62
  63       // No next sibling, so move up.
  64       currentNode = nodeStack.back();
  65       nodeStack.pop_back();
  66       currentIndex = indexStack.back();
  67       indexStack.pop_back();
  68
  69     } while (currentNode != nullptr);
  70   }
  71 }