gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/tree/Trees.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 "tree/ErrorNode.h"
   7 #include "Parser.h"
   8 #include "ParserRuleContext.h"
   9 #include "support/CPPUtils.h"
  10 #include "tree/TerminalNodeImpl.h"
  11 #include "atn/ATN.h"
  12 #include "misc/Interval.h"
  13 #include "Token.h"
  14 #include "CommonToken.h"
  15 #include "misc/Predicate.h"
  16
  17 #include "tree/Trees.h"
  18
  19 using namespace antlr4;
  20 using namespace antlr4::misc;
  21 using namespace antlr4::tree;
  22
  23 using namespace antlrcpp;
  24
  25 Trees::Trees() {
  26 }
  27
  28 std::string Trees::toStringTree(ParseTree *t, bool pretty) {
  29   return toStringTree(t, nullptr, pretty);
  30 }
  31
  32 std::string Trees::toStringTree(ParseTree *t, Parser *recog, bool pretty) {
  33   if (recog == nullptr)
  34     return toStringTree(t, std::vector<std::string>(), pretty);
  35   return toStringTree(t, recog->getRuleNames(), pretty);
  36 }
  37
  38 std::string Trees::toStringTree(ParseTree *t, const std::vector<std::string> &ruleNames, bool pretty) {
  39   std::string temp = antlrcpp::escapeWhitespace(Trees::getNodeText(t, ruleNames), false);
  40   if (t->children.empty()) {
  41     return temp;
  42   }
  43
  44   std::stringstream ss;
  45   ss << "(" << temp << ' ';
  46
  47   // Implement the recursive walk as iteration to avoid trouble with deep nesting.
  48   std::stack<size_t> stack;
  49   size_t childIndex = 0;
  50   ParseTree *run = t;
  51   size_t indentationLevel = 1;
  52   while (childIndex < run->children.size()) {
  53     if (childIndex > 0) {
  54       ss << ' ';
  55     }
  56     ParseTree *child = run->children[childIndex];
  57     temp = antlrcpp::escapeWhitespace(Trees::getNodeText(child, ruleNames), false);
  58     if (!child->children.empty()) {
  59       // Go deeper one level.
  60       stack.push(childIndex);
  61       run = child;
  62       childIndex = 0;
  63       if (pretty) {
  64         ++indentationLevel;
  65         ss << std::endl;
  66         for (size_t i = 0; i < indentationLevel; ++i) {
  67           ss << "    ";
  68         }
  69       }
  70       ss << "(" << temp << " ";
  71     } else {
  72       ss << temp;
  73       while (++childIndex == run->children.size()) {
  74         if (stack.size() > 0) {
  75           // Reached the end of the current level. See if we can step up from here.
  76           childIndex = stack.top();
  77           stack.pop();
  78           run = run->parent;
  79           if (pretty) {
  80             --indentationLevel;
  81           }
  82           ss << ")";
  83         } else {
  84           break;
  85         }
  86       }
  87     }
  88   }
  89
  90   ss << ")";
  91   return ss.str();
  92 }
  93
  94 std::string Trees::getNodeText(ParseTree *t, Parser *recog) {
  95   return getNodeText(t, recog->getRuleNames());
  96 }
  97
  98 std::string Trees::getNodeText(ParseTree *t, const std::vector<std::string> &ruleNames) {
  99   if (ruleNames.size() > 0) {
 100     if (is<RuleContext *>(t)) {
 101       size_t ruleIndex = dynamic_cast<RuleContext *>(t)->getRuleIndex();
 102       std::string ruleName = ruleNames[ruleIndex];
 103       size_t altNumber = dynamic_cast<RuleContext *>(t)->getAltNumber();
 104       if (altNumber != atn::ATN::INVALID_ALT_NUMBER) {
 105         return ruleName + ":" + std::to_string(altNumber);
 106       }
 107       return ruleName;
 108     } else if (is<ErrorNode *>(t)) {
 109       return t->toString();
 110     } else if (is<TerminalNode *>(t)) {
 111       Token *symbol = dynamic_cast<TerminalNode *>(t)->getSymbol();
 112       if (symbol != nullptr) {
 113         std::string s = symbol->getText();
 114         return s;
 115       }
 116     }
 117   }
 118   // no recog for rule names
 119   if (is<RuleContext *>(t)) {
 120     return dynamic_cast<RuleContext *>(t)->getText();
 121   }
 122
 123   if (is<TerminalNodeImpl *>(t)) {
 124     return dynamic_cast<TerminalNodeImpl *>(t)->getSymbol()->getText();
 125   }
 126
 127   return "";
 128 }
 129
 130 std::vector<ParseTree *> Trees::getAncestors(ParseTree *t) {
 131   std::vector<ParseTree *> ancestors;
 132   ParseTree *parent = t->parent;
 133   while (parent != nullptr) {
 134     ancestors.insert(ancestors.begin(), parent); // insert at start
 135     parent = parent->parent;
 136   }
 137   return ancestors;
 138 }
 139
 140 template<typename T>
 141 static void _findAllNodes(ParseTree *t, size_t index, bool findTokens, std::vector<T> &nodes) {
 142   // check this node (the root) first
 143   if (findTokens && is<TerminalNode *>(t)) {
 144     TerminalNode *tnode = dynamic_cast<TerminalNode *>(t);
 145     if (tnode->getSymbol()->getType() == index) {
 146       nodes.push_back(t);
 147     }
 148   } else if (!findTokens && is<ParserRuleContext *>(t)) {
 149     ParserRuleContext *ctx = dynamic_cast<ParserRuleContext *>(t);
 150     if (ctx->getRuleIndex() == index) {
 151       nodes.push_back(t);
 152     }
 153   }
 154   // check children
 155   for (size_t i = 0; i < t->children.size(); i++) {
 156     _findAllNodes(t->children[i], index, findTokens, nodes);
 157   }
 158 }
 159
 160 bool Trees::isAncestorOf(ParseTree *t, ParseTree *u) {
 161   if (t == nullptr || u == nullptr || t->parent == nullptr) {
 162     return false;
 163   }
 164
 165   ParseTree *p = u->parent;
 166   while (p != nullptr) {
 167     if (t == p) {
 168       return true;
 169     }
 170     p = p->parent;
 171   }
 172   return false;
 173 }
 174
 175 std::vector<ParseTree *> Trees::findAllTokenNodes(ParseTree *t, size_t ttype) {
 176   return findAllNodes(t, ttype, true);
 177 }
 178
 179 std::vector<ParseTree *> Trees::findAllRuleNodes(ParseTree *t, size_t ruleIndex) {
 180   return findAllNodes(t, ruleIndex, false);
 181 }
 182
 183 std::vector<ParseTree *> Trees::findAllNodes(ParseTree *t, size_t index, bool findTokens) {
 184   std::vector<ParseTree *> nodes;
 185   _findAllNodes<ParseTree *>(t, index, findTokens, nodes);
 186   return nodes;
 187 }
 188
 189 std::vector<ParseTree *> Trees::getDescendants(ParseTree *t) {
 190   std::vector<ParseTree *> nodes;
 191   nodes.push_back(t);
 192   std::size_t n = t->children.size();
 193   for (size_t i = 0 ; i < n ; i++) {
 194     auto descentants = getDescendants(t->children[i]);
 195     for (auto *entry: descentants) {
 196       nodes.push_back(entry);
 197     }
 198   }
 199   return nodes;
 200 }
 201
 202 std::vector<ParseTree *> Trees::descendants(ParseTree *t) {
 203   return getDescendants(t);
 204 }
 205
 206 ParserRuleContext* Trees::getRootOfSubtreeEnclosingRegion(ParseTree *t, size_t startTokenIndex, size_t stopTokenIndex) {
 207   size_t n = t->children.size();
 208   for (size_t i = 0; i < n; i++) {
 209     ParserRuleContext *r = getRootOfSubtreeEnclosingRegion(t->children[i], startTokenIndex, stopTokenIndex);
 210     if (r != nullptr) {
 211       return r;
 212     }
 213   }
 214
 215   if (is<ParserRuleContext *>(t)) {
 216     ParserRuleContext *r = dynamic_cast<ParserRuleContext *>(t);
 217     if (startTokenIndex >= r->getStart()->getTokenIndex() && // is range fully contained in t?
 218         (r->getStop() == nullptr || stopTokenIndex <= r->getStop()->getTokenIndex())) {
 219       // note: r.getStop()==null likely implies that we bailed out of parser and there's nothing to the right
 220       return r;
 221     }
 222   }
 223   return nullptr;
 224 }
 225
 226 ParseTree * Trees::findNodeSuchThat(ParseTree *t, Ref<Predicate> const& pred) {
 227   if (pred->test(t)) {
 228     return t;
 229   }
 230
 231   size_t n = t->children.size();
 232   for (size_t i = 0 ; i < n ; ++i) {
 233     ParseTree *u = findNodeSuchThat(t->children[i], pred);
 234     if (u != nullptr) {
 235       return u;
 236     }
 237   }
 238
 239   return nullptr;
 240 }
 241