gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/tree/xpath/XPath.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 "XPathLexer.h"
   7 #include "XPathLexerErrorListener.h"
   8 #include "XPathElement.h"
   9 #include "XPathWildcardAnywhereElement.h"
  10 #include "XPathWildcardElement.h"
  11 #include "XPathTokenAnywhereElement.h"
  12 #include "XPathTokenElement.h"
  13 #include "XPathRuleAnywhereElement.h"
  14 #include "XPathRuleElement.h"
  15
  16 #include "XPath.h"
  17
  18 using namespace antlr4;
  19 using namespace antlr4::tree;
  20 using namespace antlr4::tree::xpath;
  21
  22 const std::string XPath::WILDCARD = "*";
  23 const std::string XPath::NOT = "!";
  24
  25 XPath::XPath(Parser *parser, const std::string &path) {
  26   _parser = parser;
  27   _path = path;
  28 }
  29
  30 std::vector<std::unique_ptr<XPathElement>> XPath::split(const std::string &path) {
  31   ANTLRInputStream in(path);
  32   XPathLexer lexer(&in);
  33   lexer.removeErrorListeners();
  34   XPathLexerErrorListener listener;
  35   lexer.addErrorListener(&listener);
  36   CommonTokenStream tokenStream(&lexer);
  37   try {
  38     tokenStream.fill();
  39   } catch (LexerNoViableAltException &) {
  40     size_t pos = lexer.getCharPositionInLine();
  41     std::string msg = "Invalid tokens or characters at index " + std::to_string(pos) + " in path '" + path + "'";
  42     throw IllegalArgumentException(msg);
  43   }
  44
  45   std::vector<Token *> tokens = tokenStream.getTokens();
  46   std::vector<std::unique_ptr<XPathElement>> elements;
  47   size_t n = tokens.size();
  48   size_t i = 0;
  49   bool done = false;
  50   while (!done && i < n) {
  51     Token *el = tokens[i];
  52     Token *next = nullptr;
  53     switch (el->getType()) {
  54       case XPathLexer::ROOT:
  55       case XPathLexer::ANYWHERE: {
  56         bool anywhere = el->getType() == XPathLexer::ANYWHERE;
  57         i++;
  58         next = tokens[i];
  59         bool invert = next->getType() == XPathLexer::BANG;
  60         if (invert) {
  61           i++;
  62           next = tokens[i];
  63         }
  64         std::unique_ptr<XPathElement> pathElement = getXPathElement(next, anywhere);
  65         pathElement->setInvert(invert);
  66         elements.push_back(std::move(pathElement));
  67         i++;
  68         break;
  69
  70       }
  71       case XPathLexer::TOKEN_REF:
  72       case XPathLexer::RULE_REF:
  73       case XPathLexer::WILDCARD:
  74         elements.push_back(getXPathElement(el, false));
  75         i++;
  76         break;
  77
  78       case Token::EOF:
  79         done = true;
  80         break;
  81
  82       default :
  83         throw IllegalArgumentException("Unknown path element " + el->toString());
  84     }
  85   }
  86
  87   return elements;
  88 }
  89
  90 std::unique_ptr<XPathElement> XPath::getXPathElement(Token *wordToken, bool anywhere) {
  91   if (wordToken->getType() == Token::EOF) {
  92     throw IllegalArgumentException("Missing path element at end of path");
  93   }
  94
  95   std::string word = wordToken->getText();
  96   size_t ttype = _parser->getTokenType(word);
  97   ssize_t ruleIndex = _parser->getRuleIndex(word);
  98   switch (wordToken->getType()) {
  99     case XPathLexer::WILDCARD :
 100       if (anywhere)
 101         return std::unique_ptr<XPathWildcardAnywhereElement>(new XPathWildcardAnywhereElement());
 102       return std::unique_ptr<XPathWildcardElement>(new XPathWildcardElement());
 103
 104     case XPathLexer::TOKEN_REF:
 105     case XPathLexer::STRING :
 106       if (ttype == Token::INVALID_TYPE) {
 107         throw IllegalArgumentException(word + " at index " + std::to_string(wordToken->getStartIndex()) + " isn't a valid token name");
 108       }
 109       if (anywhere)
 110         return std::unique_ptr<XPathTokenAnywhereElement>(new XPathTokenAnywhereElement(word, (int)ttype));
 111       return std::unique_ptr<XPathTokenElement>(new XPathTokenElement(word, (int)ttype));
 112
 113     default :
 114       if (ruleIndex == -1) {
 115         throw IllegalArgumentException(word + " at index " + std::to_string(wordToken->getStartIndex()) + " isn't a valid rule name");
 116       }
 117       if (anywhere)
 118         return std::unique_ptr<XPathRuleAnywhereElement>(new XPathRuleAnywhereElement(word, (int)ruleIndex));
 119       return std::unique_ptr<XPathRuleElement>(new XPathRuleElement(word, (int)ruleIndex));
 120   }
 121 }
 122
 123 static ParserRuleContext dummyRoot;
 124
 125 std::vector<ParseTree *> XPath::findAll(ParseTree *tree, std::string const& xpath, Parser *parser) {
 126   XPath p(parser, xpath);
 127   return p.evaluate(tree);
 128 }
 129
 130 std::vector<ParseTree *> XPath::evaluate(ParseTree *t) {
 131   dummyRoot.children = { t }; // don't set t's parent.
 132
 133   std::vector<ParseTree *> work = { &dummyRoot };
 134
 135   size_t i = 0;
 136   std::vector<std::unique_ptr<XPathElement>> elements = split(_path);
 137
 138   while (i < elements.size()) {
 139     std::vector<ParseTree *> next;
 140     for (auto *node : work) {
 141       if (!node->children.empty()) {
 142         // only try to match next element if it has children
 143         // e.g., //func/*/stat might have a token node for which
 144         // we can't go looking for stat nodes.
 145         auto matching = elements[i]->evaluate(node);
 146         next.insert(next.end(), matching.begin(), matching.end());
 147       }
 148     }
 149     i++;
 150     work = next;
 151   }
 152
 153   return work;
 154 }