Intermediate changes

20 files changed, 875 insertions, 0 deletions

diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.cpp
new file mode 100644
index 0000000000..c0398962ec
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.cpp
@@ -0,0 +1,154 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "XPathLexer.h"
+#include "XPathLexerErrorListener.h"
+#include "XPathElement.h"
+#include "XPathWildcardAnywhereElement.h"
+#include "XPathWildcardElement.h"
+#include "XPathTokenAnywhereElement.h"
+#include "XPathTokenElement.h"
+#include "XPathRuleAnywhereElement.h"
+#include "XPathRuleElement.h"
+
+#include "XPath.h"
+
+using namespace antlr4;
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+const std::string XPath::WILDCARD = "*";
+const std::string XPath::NOT = "!";
+
+XPath::XPath(Parser *parser, const std::string &path) {
+  _parser = parser;
+  _path = path;
+}
+
+std::vector<std::unique_ptr<XPathElement>> XPath::split(const std::string &path) {
+  ANTLRInputStream in(path);
+  XPathLexer lexer(&in);
+  lexer.removeErrorListeners();
+  XPathLexerErrorListener listener;
+  lexer.addErrorListener(&listener);
+  CommonTokenStream tokenStream(&lexer);
+  try {
+    tokenStream.fill();
+  } catch (LexerNoViableAltException &) {
+    size_t pos = lexer.getCharPositionInLine();
+    std::string msg = "Invalid tokens or characters at index " + std::to_string(pos) + " in path '" + path + "'";
+    throw IllegalArgumentException(msg);
+  }
+
+  std::vector<Token *> tokens = tokenStream.getTokens();
+  std::vector<std::unique_ptr<XPathElement>> elements;
+  size_t n = tokens.size();
+  size_t i = 0;
+  bool done = false;
+  while (!done && i < n) {
+    Token *el = tokens[i];
+    Token *next = nullptr;
+    switch (el->getType()) {
+      case XPathLexer::ROOT:
+      case XPathLexer::ANYWHERE: {
+        bool anywhere = el->getType() == XPathLexer::ANYWHERE;
+        i++;
+        next = tokens[i];
+        bool invert = next->getType() == XPathLexer::BANG;
+        if (invert) {
+          i++;
+          next = tokens[i];
+        }
+        std::unique_ptr<XPathElement> pathElement = getXPathElement(next, anywhere);
+        pathElement->setInvert(invert);
+        elements.push_back(std::move(pathElement));
+        i++;
+        break;
+
+      }
+      case XPathLexer::TOKEN_REF:
+      case XPathLexer::RULE_REF:
+      case XPathLexer::WILDCARD:
+        elements.push_back(getXPathElement(el, false));
+        i++;
+        break;
+
+      case Token::EOF:
+        done = true;
+        break;
+
+      default :
+        throw IllegalArgumentException("Unknown path element " + el->toString());
+    }
+  }
+
+  return elements;
+}
+
+std::unique_ptr<XPathElement> XPath::getXPathElement(Token *wordToken, bool anywhere) {
+  if (wordToken->getType() == Token::EOF) {
+    throw IllegalArgumentException("Missing path element at end of path");
+  }
+
+  std::string word = wordToken->getText();
+  size_t ttype = _parser->getTokenType(word);
+  ssize_t ruleIndex = _parser->getRuleIndex(word);
+  switch (wordToken->getType()) {
+    case XPathLexer::WILDCARD :
+      if (anywhere)
+        return std::unique_ptr<XPathWildcardAnywhereElement>(new XPathWildcardAnywhereElement());
+      return std::unique_ptr<XPathWildcardElement>(new XPathWildcardElement());
+
+    case XPathLexer::TOKEN_REF:
+    case XPathLexer::STRING :
+      if (ttype == Token::INVALID_TYPE) {
+        throw IllegalArgumentException(word + " at index " + std::to_string(wordToken->getStartIndex()) + " isn't a valid token name");
+      }
+      if (anywhere)
+        return std::unique_ptr<XPathTokenAnywhereElement>(new XPathTokenAnywhereElement(word, (int)ttype));
+      return std::unique_ptr<XPathTokenElement>(new XPathTokenElement(word, (int)ttype));
+
+    default :
+      if (ruleIndex == -1) {
+        throw IllegalArgumentException(word + " at index " + std::to_string(wordToken->getStartIndex()) + " isn't a valid rule name");
+      }
+      if (anywhere)
+        return std::unique_ptr<XPathRuleAnywhereElement>(new XPathRuleAnywhereElement(word, (int)ruleIndex));
+      return std::unique_ptr<XPathRuleElement>(new XPathRuleElement(word, (int)ruleIndex));
+  }
+}
+
+static ParserRuleContext dummyRoot;
+
+std::vector<ParseTree *> XPath::findAll(ParseTree *tree, std::string const& xpath, Parser *parser) {
+  XPath p(parser, xpath);
+  return p.evaluate(tree);
+}
+
+std::vector<ParseTree *> XPath::evaluate(ParseTree *t) {
+  dummyRoot.children = { t }; // don't set t's parent.
+
+  std::vector<ParseTree *> work = { &dummyRoot };
+
+  size_t i = 0;
+  std::vector<std::unique_ptr<XPathElement>> elements = split(_path);
+
+  while (i < elements.size()) {
+    std::vector<ParseTree *> next;
+    for (auto *node : work) {
+      if (!node->children.empty()) {
+        // only try to match next element if it has children
+        // e.g., //func/*/stat might have a token node for which
+        // we can't go looking for stat nodes.
+        auto matching = elements[i]->evaluate(node);
+        next.insert(next.end(), matching.begin(), matching.end());
+      }
+    }
+    i++;
+    work = next;
+  }
+
+  return work;
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.h
new file mode 100644
index 0000000000..e38d482d58
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPath.h
@@ -0,0 +1,86 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "antlr4-common.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  /// Represent a subset of XPath XML path syntax for use in identifying nodes in
+  /// parse trees.
+  ///
+  /// <para>
+  /// Split path into words and separators {@code /} and {@code //} via ANTLR
+  /// itself then walk path elements from left to right. At each separator-word
+  /// pair, find set of nodes. Next stage uses those as work list.</para>
+  ///
+  /// <para>
+  /// The basic interface is
+  /// <seealso cref="XPath#findAll ParseTree.findAll"/>{@code (tree, pathString, parser)}.
+  /// But that is just shorthand for:</para>
+  ///
+  /// <pre>
+  /// <seealso cref="XPath"/> p = new <seealso cref="XPath#XPath XPath"/>(parser, pathString);
+  /// return p.<seealso cref="#evaluate evaluate"/>(tree);
+  /// </pre>
+  ///
+  /// <para>
+  /// See {@code org.antlr.v4.test.TestXPath} for descriptions. In short, this
+  /// allows operators:</para>
+  ///
+  /// <dl>
+  /// <dt>/</dt> <dd>root</dd>
+  /// <dt>//</dt> <dd>anywhere</dd>
+  /// <dt>!</dt> <dd>invert; this must appear directly after root or anywhere
+  /// operator</dd>
+  /// </dl>
+  ///
+  /// <para>
+  /// and path elements:</para>
+  ///
+  /// <dl>
+  /// <dt>ID</dt> <dd>token name</dd>
+  /// <dt>'string'</dt> <dd>any string literal token from the grammar</dd>
+  /// <dt>expr</dt> <dd>rule name</dd>
+  /// <dt>*</dt> <dd>wildcard matching any node</dd>
+  /// </dl>
+  ///
+  /// <para>
+  /// Whitespace is not allowed.</para>
+
+  class ANTLR4CPP_PUBLIC XPath {
+  public:
+    static const std::string WILDCARD; // word not operator/separator
+    static const std::string NOT; // word for invert operator
+
+    XPath(Parser *parser, const std::string &path);
+    virtual ~XPath() {}
+
+    // TODO: check for invalid token/rule names, bad syntax
+    virtual std::vector<std::unique_ptr<XPathElement>> split(const std::string &path);
+
+    static std::vector<ParseTree *> findAll(ParseTree *tree, std::string const& xpath, Parser *parser);
+
+    /// Return a list of all nodes starting at {@code t} as root that satisfy the
+    /// path. The root {@code /} is relative to the node passed to
+    /// <seealso cref="#evaluate"/>.
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t);
+
+  protected:
+    std::string _path;
+    Parser *_parser;
+
+    /// Convert word like {@code *} or {@code ID} or {@code expr} to a path
+    /// element. {@code anywhere} is {@code true} if {@code //} precedes the
+    /// word.
+    virtual std::unique_ptr<XPathElement> getXPathElement(Token *wordToken, bool anywhere);
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.cpp
new file mode 100644
index 0000000000..64b122df13
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.cpp
@@ -0,0 +1,31 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "support/CPPUtils.h"
+
+#include "XPathElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathElement::XPathElement(const std::string &nodeName) {
+  _nodeName = nodeName;
+}
+
+XPathElement::~XPathElement() {
+}
+
+std::vector<ParseTree *> XPathElement::evaluate(ParseTree * /*t*/) {
+  return {};
+}
+
+std::string XPathElement::toString() const {
+  std::string inv = _invert ? "!" : "";
+  return antlrcpp::toString(*this) + "[" + inv + _nodeName + "]";
+}
+
+void XPathElement::setInvert(bool value) {
+  _invert = value;
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.h
new file mode 100644
index 0000000000..f339117d7f
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathElement.h
@@ -0,0 +1,40 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "antlr4-common.h"
+
+namespace antlr4 {
+namespace tree {
+  class ParseTree;
+
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathElement {
+  public:
+    /// Construct element like {@code /ID} or {@code ID} or {@code /*} etc...
+    ///  op is null if just node
+    XPathElement(const std::string &nodeName);
+    XPathElement(XPathElement const&) = default;
+    virtual ~XPathElement();
+
+    XPathElement& operator=(XPathElement const&) = default;
+
+    /// Given tree rooted at {@code t} return all nodes matched by this path
+    /// element.
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t);
+    virtual std::string toString() const;
+
+    void setInvert(bool value);
+
+  protected:
+    std::string _nodeName;
+    bool _invert = false;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.cpp
new file mode 100644
index 0000000000..506d2e1179
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.cpp
@@ -0,0 +1,182 @@
+
+// Generated from XPathLexer.g4 by ANTLR 4.9.3
+
+
+#include "XPathLexer.h"
+
+
+using namespace antlr4;
+
+namespace {
+
+struct XPathLexerStaticData final {
+  XPathLexerStaticData(std::vector<std::string> ruleNames,
+                        std::vector<std::string> channelNames,
+                        std::vector<std::string> modeNames,
+                        std::vector<std::string> literalNames,
+                        std::vector<std::string> symbolicNames)
+      : ruleNames(std::move(ruleNames)), channelNames(std::move(channelNames)),
+        modeNames(std::move(modeNames)), literalNames(std::move(literalNames)),
+        symbolicNames(std::move(symbolicNames)),
+        vocabulary(this->literalNames, this->symbolicNames) {}
+
+  XPathLexerStaticData(const XPathLexerStaticData&) = delete;
+  XPathLexerStaticData(XPathLexerStaticData&&) = delete;
+  XPathLexerStaticData& operator=(const XPathLexerStaticData&) = delete;
+  XPathLexerStaticData& operator=(XPathLexerStaticData&&) = delete;
+
+  std::vector<antlr4::dfa::DFA> decisionToDFA;
+  antlr4::atn::PredictionContextCache sharedContextCache;
+  const std::vector<std::string> ruleNames;
+  const std::vector<std::string> channelNames;
+  const std::vector<std::string> modeNames;
+  const std::vector<std::string> literalNames;
+  const std::vector<std::string> symbolicNames;
+  const antlr4::dfa::Vocabulary vocabulary;
+  antlr4::atn::SerializedATNView serializedATN;
+  std::unique_ptr<antlr4::atn::ATN> atn;
+};
+
+::antlr4::internal::OnceFlag xpathLexerOnceFlag;
+XPathLexerStaticData *xpathLexerStaticData = nullptr;
+
+void xpathLexerInitialize() {
+  assert(xpathLexerStaticData == nullptr);
+  auto staticData = std::make_unique<XPathLexerStaticData>(
+    std::vector<std::string>{
+      "ANYWHERE", "ROOT", "WILDCARD", "BANG", "ID", "NameChar", "NameStartChar",
+      "STRING"
+    },
+    std::vector<std::string>{
+      "DEFAULT_TOKEN_CHANNEL", "HIDDEN"
+    },
+    std::vector<std::string>{
+      "DEFAULT_MODE"
+    },
+    std::vector<std::string>{
+      "", "", "", "'//'", "'/'", "'*'", "'!'"
+    },
+    std::vector<std::string>{
+      "", "TOKEN_REF", "RULE_REF", "ANYWHERE", "ROOT", "WILDCARD", "BANG", "ID",
+      "STRING"
+    }
+  );
+  static const int32_t serializedATNSegment[] = {
+    0x4, 0x0, 0x8, 0x32, 0x6, -1, 0x2, 0x0, 0x7, 0x0, 0x2, 0x1, 0x7,
+       0x1, 0x2, 0x2, 0x7, 0x2, 0x2, 0x3, 0x7, 0x3, 0x2, 0x4, 0x7, 0x4,
+       0x2, 0x5, 0x7, 0x5, 0x2, 0x6, 0x7, 0x6, 0x2, 0x7, 0x7, 0x7, 0x1,
+       0x0, 0x1, 0x0, 0x1, 0x0, 0x1, 0x1, 0x1, 0x1, 0x1, 0x2, 0x1, 0x2,
+       0x1, 0x3, 0x1, 0x3, 0x1, 0x4, 0x1, 0x4, 0x5, 0x4, 0x1d, 0x8, 0x4,
+       0xa, 0x4, 0xc, 0x4, 0x20, 0x9, 0x4, 0x1, 0x4, 0x1, 0x4, 0x1, 0x5,
+       0x1, 0x5, 0x3, 0x5, 0x26, 0x8, 0x5, 0x1, 0x6, 0x1, 0x6, 0x1, 0x7,
+       0x1, 0x7, 0x5, 0x7, 0x2c, 0x8, 0x7, 0xa, 0x7, 0xc, 0x7, 0x2f, 0x9,
+       0x7, 0x1, 0x7, 0x1, 0x7, 0x1, 0x2d, 0x0, 0x8, 0x1, 0x3, 0x3, 0x4,
+       0x5, 0x5, 0x7, 0x6, 0x9, 0x7, 0xb, 0x0, 0xd, 0x0, 0xf, 0x8, 0x1,
+       0x0, 0x2, 0x5, 0x0, 0x30, 0x39, 0x5f, 0x5f, 0xb7, 0xb7, 0x300, 0x36f,
+       0x203f, 0x2040, 0xd, 0x0, 0x41, 0x5a, 0x61, 0x7a, 0xc0, 0xd6, 0xd8,
+       0xf6, 0xf8, 0x2ff, 0x370, 0x37d, 0x37f, 0x1fff, 0x200c, 0x200d, 0x2070,
+       0x218f, 0x2c00, 0x2fef, 0x3001, 0xd7ff, 0xf900, 0xfdcf, 0xfdf0, -1,
+       0x0, 0x32, 0x0, 0x1, 0x1, 0x0, 0x0, 0x0, 0x0, 0x3, 0x1, 0x0, 0x0,
+       0x0, 0x0, 0x5, 0x1, 0x0, 0x0, 0x0, 0x0, 0x7, 0x1, 0x0, 0x0, 0x0,
+       0x0, 0x9, 0x1, 0x0, 0x0, 0x0, 0x0, 0xf, 0x1, 0x0, 0x0, 0x0, 0x1,
+       0x11, 0x1, 0x0, 0x0, 0x0, 0x3, 0x14, 0x1, 0x0, 0x0, 0x0, 0x5, 0x16,
+       0x1, 0x0, 0x0, 0x0, 0x7, 0x18, 0x1, 0x0, 0x0, 0x0, 0x9, 0x1a, 0x1,
+       0x0, 0x0, 0x0, 0xb, 0x25, 0x1, 0x0, 0x0, 0x0, 0xd, 0x27, 0x1, 0x0,
+       0x0, 0x0, 0xf, 0x29, 0x1, 0x0, 0x0, 0x0, 0x11, 0x12, 0x5, 0x2f, 0x0,
+       0x0, 0x12, 0x13, 0x5, 0x2f, 0x0, 0x0, 0x13, 0x2, 0x1, 0x0, 0x0, 0x0,
+       0x14, 0x15, 0x5, 0x2f, 0x0, 0x0, 0x15, 0x4, 0x1, 0x0, 0x0, 0x0, 0x16,
+       0x17, 0x5, 0x2a, 0x0, 0x0, 0x17, 0x6, 0x1, 0x0, 0x0, 0x0, 0x18, 0x19,
+       0x5, 0x21, 0x0, 0x0, 0x19, 0x8, 0x1, 0x0, 0x0, 0x0, 0x1a, 0x1e, 0x3,
+       0xd, 0x6, 0x0, 0x1b, 0x1d, 0x3, 0xb, 0x5, 0x0, 0x1c, 0x1b, 0x1, 0x0,
+       0x0, 0x0, 0x1d, 0x20, 0x1, 0x0, 0x0, 0x0, 0x1e, 0x1c, 0x1, 0x0, 0x0,
+       0x0, 0x1e, 0x1f, 0x1, 0x0, 0x0, 0x0, 0x1f, 0x21, 0x1, 0x0, 0x0, 0x0,
+       0x20, 0x1e, 0x1, 0x0, 0x0, 0x0, 0x21, 0x22, 0x6, 0x4, 0x0, 0x0, 0x22,
+       0xa, 0x1, 0x0, 0x0, 0x0, 0x23, 0x26, 0x3, 0xd, 0x6, 0x0, 0x24, 0x26,
+       0x7, 0x0, 0x0, 0x0, 0x25, 0x23, 0x1, 0x0, 0x0, 0x0, 0x25, 0x24, 0x1,
+       0x0, 0x0, 0x0, 0x26, 0xc, 0x1, 0x0, 0x0, 0x0, 0x27, 0x28, 0x7, 0x1,
+       0x0, 0x0, 0x28, 0xe, 0x1, 0x0, 0x0, 0x0, 0x29, 0x2d, 0x5, 0x27, 0x0,
+       0x0, 0x2a, 0x2c, 0x9, 0x0, 0x0, 0x0, 0x2b, 0x2a, 0x1, 0x0, 0x0, 0x0,
+       0x2c, 0x2f, 0x1, 0x0, 0x0, 0x0, 0x2d, 0x2e, 0x1, 0x0, 0x0, 0x0, 0x2d,
+       0x2b, 0x1, 0x0, 0x0, 0x0, 0x2e, 0x30, 0x1, 0x0, 0x0, 0x0, 0x2f, 0x2d,
+       0x1, 0x0, 0x0, 0x0, 0x30, 0x31, 0x5, 0x27, 0x0, 0x0, 0x31, 0x10,
+       0x1, 0x0, 0x0, 0x0, 0x4, 0x0, 0x1e, 0x25, 0x2d, 0x1, 0x1, 0x4, 0x0,
+  };
+
+  staticData->serializedATN = antlr4::atn::SerializedATNView(serializedATNSegment, sizeof(serializedATNSegment) / sizeof(serializedATNSegment[0]));
+
+  atn::ATNDeserializer deserializer;
+  staticData->atn = deserializer.deserialize(staticData->serializedATN);
+
+  size_t count = staticData->atn->getNumberOfDecisions();
+  staticData->decisionToDFA.reserve(count);
+  for (size_t i = 0; i < count; i++) {
+    staticData->decisionToDFA.emplace_back(staticData->atn->getDecisionState(i), i);
+  }
+  xpathLexerStaticData = staticData.release();
+}
+
+}
+
+XPathLexer::XPathLexer(CharStream *input) : Lexer(input) {
+  XPathLexer::initialize();
+  _interpreter = new atn::LexerATNSimulator(this, *xpathLexerStaticData->atn, xpathLexerStaticData->decisionToDFA, xpathLexerStaticData->sharedContextCache);
+}
+
+XPathLexer::~XPathLexer() {
+  delete _interpreter;
+}
+
+std::string XPathLexer::getGrammarFileName() const {
+  return "XPathLexer.g4";
+}
+
+const std::vector<std::string>& XPathLexer::getRuleNames() const {
+  return xpathLexerStaticData->ruleNames;
+}
+
+const std::vector<std::string>& XPathLexer::getChannelNames() const {
+  return xpathLexerStaticData->channelNames;
+}
+
+const std::vector<std::string>& XPathLexer::getModeNames() const {
+  return xpathLexerStaticData->modeNames;
+}
+
+const dfa::Vocabulary& XPathLexer::getVocabulary() const {
+  return xpathLexerStaticData->vocabulary;
+}
+
+antlr4::atn::SerializedATNView XPathLexer::getSerializedATN() const {
+  return xpathLexerStaticData->serializedATN;
+}
+
+const atn::ATN& XPathLexer::getATN() const {
+  return *xpathLexerStaticData->atn;
+}
+
+void XPathLexer::action(RuleContext *context, size_t ruleIndex, size_t actionIndex) {
+  switch (ruleIndex) {
+    case 4: IDAction(antlrcpp::downCast<antlr4::RuleContext *>(context), actionIndex); break;
+
+  default:
+    break;
+  }
+}
+
+void XPathLexer::IDAction(antlr4::RuleContext *context, size_t actionIndex) {
+  switch (actionIndex) {
+    case 0:
+    				if (isupper(getText()[0]))
+    				  setType(TOKEN_REF);
+    				else
+    				  setType(RULE_REF);
+    				 break;
+
+  default:
+    break;
+  }
+}
+
+void XPathLexer::initialize() {
+  ::antlr4::internal::call_once(xpathLexerOnceFlag, xpathLexerInitialize);
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.h
new file mode 100644
index 0000000000..6926d2161e
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexer.h
@@ -0,0 +1,47 @@
+
+// Generated from XPathLexer.g4 by ANTLR 4.9.3
+
+#pragma once
+
+
+#include "antlr4-runtime.h"
+
+
+class  XPathLexer : public antlr4::Lexer {
+public:
+  enum {
+    TOKEN_REF = 1, RULE_REF = 2, ANYWHERE = 3, ROOT = 4, WILDCARD = 5, BANG = 6,
+    ID = 7, STRING = 8
+  };
+
+  explicit XPathLexer(antlr4::CharStream *input);
+
+  ~XPathLexer() override;
+
+  virtual std::string getGrammarFileName() const override;
+
+  virtual const std::vector<std::string>& getRuleNames() const override;
+
+  virtual const std::vector<std::string>& getChannelNames() const override;
+
+  virtual const std::vector<std::string>& getModeNames() const override;
+
+  virtual const antlr4::dfa::Vocabulary& getVocabulary() const override;
+
+  virtual antlr4::atn::SerializedATNView getSerializedATN() const override;
+
+  virtual const antlr4::atn::ATN& getATN() const override;
+
+  virtual void action(antlr4::RuleContext *context, size_t ruleIndex, size_t actionIndex) override;
+
+  // By default the static state used to implement the lexer is lazily initialized during the first
+  // call to the constructor. You can call this function if you wish to initialize the static state
+  // ahead of time.
+  static void initialize();
+private:
+  // Individual action functions triggered by action() above.
+  void IDAction(antlr4::RuleContext *context, size_t actionIndex);
+
+  // Individual semantic predicate functions triggered by sempred() above.
+};
+
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.cpp
new file mode 100644
index 0000000000..2804c8ee3d
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.cpp
@@ -0,0 +1,13 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "XPathLexerErrorListener.h"
+
+using namespace antlr4;
+using namespace antlr4::tree::xpath;
+
+void XPathLexerErrorListener::syntaxError(Recognizer * /*recognizer*/, Token * /*offendingSymbol*/,
+  size_t /*line*/, size_t /*charPositionInLine*/, const std::string &/*msg*/, std::exception_ptr /*e*/) {
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.h
new file mode 100644
index 0000000000..c0c3eaaca7
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathLexerErrorListener.h
@@ -0,0 +1,22 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "BaseErrorListener.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathLexerErrorListener : public BaseErrorListener {
+  public:
+    virtual void syntaxError(Recognizer *recognizer, Token *offendingSymbol, size_t line,
+      size_t charPositionInLine, const std::string &msg, std::exception_ptr e) override;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.cpp
new file mode 100644
index 0000000000..9ca910df2e
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.cpp
@@ -0,0 +1,20 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+
+#include "tree/xpath/XPathRuleAnywhereElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathRuleAnywhereElement::XPathRuleAnywhereElement(const std::string &ruleName, int ruleIndex) : XPathElement(ruleName) {
+  _ruleIndex = ruleIndex;
+}
+
+std::vector<ParseTree *> XPathRuleAnywhereElement::evaluate(ParseTree *t) {
+  return Trees::findAllRuleNodes(t, _ruleIndex);
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.h
new file mode 100644
index 0000000000..2ceb75ceed
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleAnywhereElement.h
@@ -0,0 +1,27 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  /// Either {@code ID} at start of path or {@code ...//ID} in middle of path.
+  class ANTLR4CPP_PUBLIC XPathRuleAnywhereElement : public XPathElement {
+  public:
+    XPathRuleAnywhereElement(const std::string &ruleName, int ruleIndex);
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+
+  protected:
+    int _ruleIndex = 0;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.cpp
new file mode 100644
index 0000000000..1d145fb575
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.cpp
@@ -0,0 +1,30 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+
+#include "XPathRuleElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathRuleElement::XPathRuleElement(const std::string &ruleName, size_t ruleIndex) : XPathElement(ruleName) {
+  _ruleIndex = ruleIndex;
+}
+
+std::vector<ParseTree *> XPathRuleElement::evaluate(ParseTree *t) {
+  // return all children of t that match nodeName
+  std::vector<ParseTree *> nodes;
+  for (auto *c : t->children) {
+    if (antlrcpp::is<ParserRuleContext *>(c)) {
+      ParserRuleContext *ctx = dynamic_cast<ParserRuleContext *>(c);
+      if ((ctx->getRuleIndex() == _ruleIndex && !_invert) || (ctx->getRuleIndex() != _ruleIndex && _invert)) {
+        nodes.push_back(ctx);
+      }
+    }
+  }
+  return nodes;
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.h
new file mode 100644
index 0000000000..b57276f033
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathRuleElement.h
@@ -0,0 +1,26 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathRuleElement : public XPathElement {
+  public:
+    XPathRuleElement(const std::string &ruleName, size_t ruleIndex);
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+
+  protected:
+    size_t _ruleIndex = 0;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.cpp
new file mode 100644
index 0000000000..c557c9d675
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.cpp
@@ -0,0 +1,20 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+
+#include "XPathTokenAnywhereElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathTokenAnywhereElement::XPathTokenAnywhereElement(const std::string &tokenName, int tokenType) : XPathElement(tokenName) {
+  this->tokenType = tokenType;
+}
+
+std::vector<ParseTree *> XPathTokenAnywhereElement::evaluate(ParseTree *t) {
+  return Trees::findAllTokenNodes(t, tokenType);
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.h
new file mode 100644
index 0000000000..2045d91b32
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenAnywhereElement.h
@@ -0,0 +1,25 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathTokenAnywhereElement : public XPathElement {
+  protected:
+    int tokenType = 0;
+  public:
+    XPathTokenAnywhereElement(const std::string &tokenName, int tokenType);
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.cpp
new file mode 100644
index 0000000000..d52fc26afd
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.cpp
@@ -0,0 +1,33 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+#include "support/CPPUtils.h"
+#include "Token.h"
+
+#include "XPathTokenElement.h"
+
+using namespace antlr4;
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathTokenElement::XPathTokenElement(const std::string &tokenName, size_t tokenType) : XPathElement(tokenName) {
+  _tokenType = tokenType;
+}
+
+std::vector<ParseTree *> XPathTokenElement::evaluate(ParseTree *t) {
+  // return all children of t that match nodeName
+  std::vector<ParseTree *> nodes;
+  for (auto *c : t->children) {
+    if (antlrcpp::is<TerminalNode *>(c)) {
+      TerminalNode *tnode = dynamic_cast<TerminalNode *>(c);
+      if ((tnode->getSymbol()->getType() == _tokenType && !_invert) || (tnode->getSymbol()->getType() != _tokenType && _invert)) {
+        nodes.push_back(tnode);
+      }
+    }
+  }
+  return nodes;
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.h
new file mode 100644
index 0000000000..7221530ce6
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathTokenElement.h
@@ -0,0 +1,26 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathTokenElement : public XPathElement {
+  public:
+    XPathTokenElement(const std::string &tokenName, size_t tokenType);
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+
+  protected:
+    size_t _tokenType = 0;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.cpp
new file mode 100644
index 0000000000..4ff424f056
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.cpp
@@ -0,0 +1,23 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "XPath.h"
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+
+#include "XPathWildcardAnywhereElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathWildcardAnywhereElement::XPathWildcardAnywhereElement() : XPathElement(XPath::WILDCARD) {
+}
+
+std::vector<ParseTree *> XPathWildcardAnywhereElement::evaluate(ParseTree *t) {
+  if (_invert) {
+    return {}; // !* is weird but valid (empty)
+  }
+  return Trees::getDescendants(t);
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.h
new file mode 100644
index 0000000000..dc5d1e5a29
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardAnywhereElement.h
@@ -0,0 +1,23 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathWildcardAnywhereElement : public XPathElement {
+  public:
+    XPathWildcardAnywhereElement();
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.cpp b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.cpp
new file mode 100644
index 0000000000..aabda5a9be
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.cpp
@@ -0,0 +1,24 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#include "XPath.h"
+#include "tree/ParseTree.h"
+#include "tree/Trees.h"
+
+#include "XPathWildcardElement.h"
+
+using namespace antlr4::tree;
+using namespace antlr4::tree::xpath;
+
+XPathWildcardElement::XPathWildcardElement() : XPathElement(XPath::WILDCARD) {
+}
+
+std::vector<ParseTree *> XPathWildcardElement::evaluate(ParseTree *t) {
+  if (_invert) {
+    return {}; // !* is weird but valid (empty)
+  }
+
+  return t->children;
+}
diff --git a/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.h b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.h
new file mode 100644
index 0000000000..accb461de2
--- /dev/null
+++ b/contrib/libs/antlr4_cpp_runtime/src/tree/xpath/XPathWildcardElement.h
@@ -0,0 +1,23 @@
+/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
+ * Use of this file is governed by the BSD 3-clause license that
+ * can be found in the LICENSE.txt file in the project root.
+ */
+
+#pragma once
+
+#include "XPathElement.h"
+
+namespace antlr4 {
+namespace tree {
+namespace xpath {
+
+  class ANTLR4CPP_PUBLIC XPathWildcardElement : public XPathElement {
+  public:
+    XPathWildcardElement();
+
+    virtual std::vector<ParseTree *> evaluate(ParseTree *t) override;
+  };
+
+} // namespace xpath
+} // namespace tree
+} // namespace antlr4