YQ Connector: support managed ClickHouse

Со стороны dqrun можно обратиться к инстансу коннектора, который работает на streaming стенде, и извлечь данные из облачного CH.

4 files changed, 3049 insertions, 0 deletions

diff --git a/contrib/libs/clang16/lib/ASTMatchers/ASTMatchFinder.cpp b/contrib/libs/clang16/lib/ASTMatchers/ASTMatchFinder.cpp
new file mode 100644
index 00000000000..a27fac62bde
--- /dev/null
+++ b/contrib/libs/clang16/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -0,0 +1,1694 @@
+//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  Implements an algorithm to efficiently search for matches on AST nodes.
+//  Uses memoization to support recursive matches like HasDescendant.
+//
+//  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
+//  calling the Matches(...) method of each matcher we are running on each
+//  AST node. The matcher can recurse via the ASTMatchFinder interface.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Timer.h"
+#include <deque>
+#include <memory>
+#include <set>
+
+namespace clang {
+namespace ast_matchers {
+namespace internal {
+namespace {
+
+typedef MatchFinder::MatchCallback MatchCallback;
+
+// The maximum number of memoization entries to store.
+// 10k has been experimentally found to give a good trade-off
+// of performance vs. memory consumption by running matcher
+// that match on every statement over a very large codebase.
+//
+// FIXME: Do some performance optimization in general and
+// revisit this number; also, put up micro-benchmarks that we can
+// optimize this on.
+static const unsigned MaxMemoizationEntries = 10000;
+
+enum class MatchType {
+  Ancestors,
+
+  Descendants,
+  Child,
+};
+
+// We use memoization to avoid running the same matcher on the same
+// AST node twice.  This struct is the key for looking up match
+// result.  It consists of an ID of the MatcherInterface (for
+// identifying the matcher), a pointer to the AST node and the
+// bound nodes before the matcher was executed.
+//
+// We currently only memoize on nodes whose pointers identify the
+// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
+// For \c QualType and \c TypeLoc it is possible to implement
+// generation of keys for each type.
+// FIXME: Benchmark whether memoization of non-pointer typed nodes
+// provides enough benefit for the additional amount of code.
+struct MatchKey {
+  DynTypedMatcher::MatcherIDType MatcherID;
+  DynTypedNode Node;
+  BoundNodesTreeBuilder BoundNodes;
+  TraversalKind Traversal = TK_AsIs;
+  MatchType Type;
+
+  bool operator<(const MatchKey &Other) const {
+    return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
+           std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
+                    Other.BoundNodes);
+  }
+};
+
+// Used to store the result of a match and possibly bound nodes.
+struct MemoizedMatchResult {
+  bool ResultOfMatch;
+  BoundNodesTreeBuilder Nodes;
+};
+
+// A RecursiveASTVisitor that traverses all children or all descendants of
+// a node.
+class MatchChildASTVisitor
+    : public RecursiveASTVisitor<MatchChildASTVisitor> {
+public:
+  typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
+
+  // Creates an AST visitor that matches 'matcher' on all children or
+  // descendants of a traversed node. max_depth is the maximum depth
+  // to traverse: use 1 for matching the children and INT_MAX for
+  // matching the descendants.
+  MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
+                       BoundNodesTreeBuilder *Builder, int MaxDepth,
+                       bool IgnoreImplicitChildren,
+                       ASTMatchFinder::BindKind Bind)
+      : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
+        MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
+        Bind(Bind), Matches(false) {}
+
+  // Returns true if a match is found in the subtree rooted at the
+  // given AST node. This is done via a set of mutually recursive
+  // functions. Here's how the recursion is done (the  *wildcard can
+  // actually be Decl, Stmt, or Type):
+  //
+  //   - Traverse(node) calls BaseTraverse(node) when it needs
+  //     to visit the descendants of node.
+  //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
+  //     Traverse*(c) for each child c of 'node'.
+  //   - Traverse*(c) in turn calls Traverse(c), completing the
+  //     recursion.
+  bool findMatch(const DynTypedNode &DynNode) {
+    reset();
+    if (const Decl *D = DynNode.get<Decl>())
+      traverse(*D);
+    else if (const Stmt *S = DynNode.get<Stmt>())
+      traverse(*S);
+    else if (const NestedNameSpecifier *NNS =
+             DynNode.get<NestedNameSpecifier>())
+      traverse(*NNS);
+    else if (const NestedNameSpecifierLoc *NNSLoc =
+             DynNode.get<NestedNameSpecifierLoc>())
+      traverse(*NNSLoc);
+    else if (const QualType *Q = DynNode.get<QualType>())
+      traverse(*Q);
+    else if (const TypeLoc *T = DynNode.get<TypeLoc>())
+      traverse(*T);
+    else if (const auto *C = DynNode.get<CXXCtorInitializer>())
+      traverse(*C);
+    else if (const TemplateArgumentLoc *TALoc =
+                 DynNode.get<TemplateArgumentLoc>())
+      traverse(*TALoc);
+    else if (const Attr *A = DynNode.get<Attr>())
+      traverse(*A);
+    // FIXME: Add other base types after adding tests.
+
+    // It's OK to always overwrite the bound nodes, as if there was
+    // no match in this recursive branch, the result set is empty
+    // anyway.
+    *Builder = ResultBindings;
+
+    return Matches;
+  }
+
+  // The following are overriding methods from the base visitor class.
+  // They are public only to allow CRTP to work. They are *not *part
+  // of the public API of this class.
+  bool TraverseDecl(Decl *DeclNode) {
+
+    if (DeclNode && DeclNode->isImplicit() &&
+        Finder->isTraversalIgnoringImplicitNodes())
+      return baseTraverse(*DeclNode);
+
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return (DeclNode == nullptr) || traverse(*DeclNode);
+  }
+
+  Stmt *getStmtToTraverse(Stmt *StmtNode) {
+    Stmt *StmtToTraverse = StmtNode;
+    if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
+      auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
+      if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
+        StmtToTraverse = LambdaNode;
+      else
+        StmtToTraverse =
+            Finder->getASTContext().getParentMapContext().traverseIgnored(
+                ExprNode);
+    }
+    return StmtToTraverse;
+  }
+
+  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
+    // If we need to keep track of the depth, we can't perform data recursion.
+    if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
+      Queue = nullptr;
+
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
+    if (!StmtToTraverse)
+      return true;
+
+    if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
+      return true;
+
+    if (!match(*StmtToTraverse))
+      return false;
+    return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
+  }
+  // We assume that the QualType and the contained type are on the same
+  // hierarchy level. Thus, we try to match either of them.
+  bool TraverseType(QualType TypeNode) {
+    if (TypeNode.isNull())
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    // Match the Type.
+    if (!match(*TypeNode))
+      return false;
+    // The QualType is matched inside traverse.
+    return traverse(TypeNode);
+  }
+  // We assume that the TypeLoc, contained QualType and contained Type all are
+  // on the same hierarchy level. Thus, we try to match all of them.
+  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+    if (TypeLocNode.isNull())
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    // Match the Type.
+    if (!match(*TypeLocNode.getType()))
+      return false;
+    // Match the QualType.
+    if (!match(TypeLocNode.getType()))
+      return false;
+    // The TypeLoc is matched inside traverse.
+    return traverse(TypeLocNode);
+  }
+  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return (NNS == nullptr) || traverse(*NNS);
+  }
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
+    if (!NNS)
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    if (!match(*NNS.getNestedNameSpecifier()))
+      return false;
+    return traverse(NNS);
+  }
+  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
+    if (!CtorInit)
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return traverse(*CtorInit);
+  }
+  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return traverse(TAL);
+  }
+  bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
+    if (!Finder->isTraversalIgnoringImplicitNodes())
+      return VisitorBase::TraverseCXXForRangeStmt(Node);
+    if (!Node)
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    if (auto *Init = Node->getInit())
+      if (!traverse(*Init))
+        return false;
+    if (!match(*Node->getLoopVariable()))
+      return false;
+    if (match(*Node->getRangeInit()))
+      if (!VisitorBase::TraverseStmt(Node->getRangeInit()))
+        return false;
+    if (!match(*Node->getBody()))
+      return false;
+    return VisitorBase::TraverseStmt(Node->getBody());
+  }
+  bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
+    if (!Finder->isTraversalIgnoringImplicitNodes())
+      return VisitorBase::TraverseCXXRewrittenBinaryOperator(Node);
+    if (!Node)
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+
+    return match(*Node->getLHS()) && match(*Node->getRHS());
+  }
+  bool TraverseAttr(Attr *A) {
+    if (A == nullptr ||
+        (A->isImplicit() &&
+         Finder->getASTContext().getParentMapContext().getTraversalKind() ==
+             TK_IgnoreUnlessSpelledInSource))
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return traverse(*A);
+  }
+  bool TraverseLambdaExpr(LambdaExpr *Node) {
+    if (!Finder->isTraversalIgnoringImplicitNodes())
+      return VisitorBase::TraverseLambdaExpr(Node);
+    if (!Node)
+      return true;
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+
+    for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
+      const auto *C = Node->capture_begin() + I;
+      if (!C->isExplicit())
+        continue;
+      if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))
+        return false;
+      if (!match(*Node->capture_init_begin()[I]))
+        return false;
+    }
+
+    if (const auto *TPL = Node->getTemplateParameterList()) {
+      for (const auto *TP : *TPL) {
+        if (!match(*TP))
+          return false;
+      }
+    }
+
+    for (const auto *P : Node->getCallOperator()->parameters()) {
+      if (!match(*P))
+        return false;
+    }
+
+    if (!match(*Node->getBody()))
+      return false;
+
+    return VisitorBase::TraverseStmt(Node->getBody());
+  }
+
+  bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
+
+private:
+  // Used for updating the depth during traversal.
+  struct ScopedIncrement {
+    explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
+    ~ScopedIncrement() { --(*Depth); }
+
+   private:
+    int *Depth;
+  };
+
+  // Resets the state of this object.
+  void reset() {
+    Matches = false;
+    CurrentDepth = 0;
+  }
+
+  // Forwards the call to the corresponding Traverse*() method in the
+  // base visitor class.
+  bool baseTraverse(const Decl &DeclNode) {
+    return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
+  }
+  bool baseTraverse(const Stmt &StmtNode) {
+    return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
+  }
+  bool baseTraverse(QualType TypeNode) {
+    return VisitorBase::TraverseType(TypeNode);
+  }
+  bool baseTraverse(TypeLoc TypeLocNode) {
+    return VisitorBase::TraverseTypeLoc(TypeLocNode);
+  }
+  bool baseTraverse(const NestedNameSpecifier &NNS) {
+    return VisitorBase::TraverseNestedNameSpecifier(
+        const_cast<NestedNameSpecifier*>(&NNS));
+  }
+  bool baseTraverse(NestedNameSpecifierLoc NNS) {
+    return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
+  }
+  bool baseTraverse(const CXXCtorInitializer &CtorInit) {
+    return VisitorBase::TraverseConstructorInitializer(
+        const_cast<CXXCtorInitializer *>(&CtorInit));
+  }
+  bool baseTraverse(TemplateArgumentLoc TAL) {
+    return VisitorBase::TraverseTemplateArgumentLoc(TAL);
+  }
+  bool baseTraverse(const Attr &AttrNode) {
+    return VisitorBase::TraverseAttr(const_cast<Attr *>(&AttrNode));
+  }
+
+  // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
+  //   0 < CurrentDepth <= MaxDepth.
+  //
+  // Returns 'true' if traversal should continue after this function
+  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
+  template <typename T>
+  bool match(const T &Node) {
+    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
+      return true;
+    }
+    if (Bind != ASTMatchFinder::BK_All) {
+      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
+      if (Matcher->matches(DynTypedNode::create(Node), Finder,
+                           &RecursiveBuilder)) {
+        Matches = true;
+        ResultBindings.addMatch(RecursiveBuilder);
+        return false; // Abort as soon as a match is found.
+      }
+    } else {
+      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
+      if (Matcher->matches(DynTypedNode::create(Node), Finder,
+                           &RecursiveBuilder)) {
+        // After the first match the matcher succeeds.
+        Matches = true;
+        ResultBindings.addMatch(RecursiveBuilder);
+      }
+    }
+    return true;
+  }
+
+  // Traverses the subtree rooted at 'Node'; returns true if the
+  // traversal should continue after this function returns.
+  template <typename T>
+  bool traverse(const T &Node) {
+    static_assert(IsBaseType<T>::value,
+                  "traverse can only be instantiated with base type");
+    if (!match(Node))
+      return false;
+    return baseTraverse(Node);
+  }
+
+  const DynTypedMatcher *const Matcher;
+  ASTMatchFinder *const Finder;
+  BoundNodesTreeBuilder *const Builder;
+  BoundNodesTreeBuilder ResultBindings;
+  int CurrentDepth;
+  const int MaxDepth;
+  const bool IgnoreImplicitChildren;
+  const ASTMatchFinder::BindKind Bind;
+  bool Matches;
+};
+
+// Controls the outermost traversal of the AST and allows to match multiple
+// matchers.
+class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
+                        public ASTMatchFinder {
+public:
+  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
+                  const MatchFinder::MatchFinderOptions &Options)
+      : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
+
+  ~MatchASTVisitor() override {
+    if (Options.CheckProfiling) {
+      Options.CheckProfiling->Records = std::move(TimeByBucket);
+    }
+  }
+
+  void onStartOfTranslationUnit() {
+    const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
+    TimeBucketRegion Timer;
+    for (MatchCallback *MC : Matchers->AllCallbacks) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MC->getID()]);
+      MC->onStartOfTranslationUnit();
+    }
+  }
+
+  void onEndOfTranslationUnit() {
+    const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
+    TimeBucketRegion Timer;
+    for (MatchCallback *MC : Matchers->AllCallbacks) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MC->getID()]);
+      MC->onEndOfTranslationUnit();
+    }
+  }
+
+  void set_active_ast_context(ASTContext *NewActiveASTContext) {
+    ActiveASTContext = NewActiveASTContext;
+  }
+
+  // The following Visit*() and Traverse*() functions "override"
+  // methods in RecursiveASTVisitor.
+
+  bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
+    // When we see 'typedef A B', we add name 'B' to the set of names
+    // A's canonical type maps to.  This is necessary for implementing
+    // isDerivedFrom(x) properly, where x can be the name of the base
+    // class or any of its aliases.
+    //
+    // In general, the is-alias-of (as defined by typedefs) relation
+    // is tree-shaped, as you can typedef a type more than once.  For
+    // example,
+    //
+    //   typedef A B;
+    //   typedef A C;
+    //   typedef C D;
+    //   typedef C E;
+    //
+    // gives you
+    //
+    //   A
+    //   |- B
+    //   `- C
+    //      |- D
+    //      `- E
+    //
+    // It is wrong to assume that the relation is a chain.  A correct
+    // implementation of isDerivedFrom() needs to recognize that B and
+    // E are aliases, even though neither is a typedef of the other.
+    // Therefore, we cannot simply walk through one typedef chain to
+    // find out whether the type name matches.
+    const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
+    const Type *CanonicalType =  // root of the typedef tree
+        ActiveASTContext->getCanonicalType(TypeNode);
+    TypeAliases[CanonicalType].insert(DeclNode);
+    return true;
+  }
+
+  bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
+    const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
+    CompatibleAliases[InterfaceDecl].insert(CAD);
+    return true;
+  }
+
+  bool TraverseDecl(Decl *DeclNode);
+  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
+  bool TraverseType(QualType TypeNode);
+  bool TraverseTypeLoc(TypeLoc TypeNode);
+  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
+  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
+  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
+  bool TraverseAttr(Attr *AttrNode);
+
+  bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
+    if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
+      {
+        ASTNodeNotAsIsSourceScope RAII(this, true);
+        TraverseStmt(RF->getInit());
+        // Don't traverse under the loop variable
+        match(*RF->getLoopVariable());
+        TraverseStmt(RF->getRangeInit());
+      }
+      {
+        ASTNodeNotSpelledInSourceScope RAII(this, true);
+        for (auto *SubStmt : RF->children()) {
+          if (SubStmt != RF->getBody())
+            TraverseStmt(SubStmt);
+        }
+      }
+      TraverseStmt(RF->getBody());
+      return true;
+    } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
+      {
+        ASTNodeNotAsIsSourceScope RAII(this, true);
+        TraverseStmt(const_cast<Expr *>(RBO->getLHS()));
+        TraverseStmt(const_cast<Expr *>(RBO->getRHS()));
+      }
+      {
+        ASTNodeNotSpelledInSourceScope RAII(this, true);
+        for (auto *SubStmt : RBO->children()) {
+          TraverseStmt(SubStmt);
+        }
+      }
+      return true;
+    } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {
+      for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {
+        auto C = std::get<0>(I);
+        ASTNodeNotSpelledInSourceScope RAII(
+            this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
+        TraverseLambdaCapture(LE, &C, std::get<1>(I));
+      }
+
+      {
+        ASTNodeNotSpelledInSourceScope RAII(this, true);
+        TraverseDecl(LE->getLambdaClass());
+      }
+      {
+        ASTNodeNotAsIsSourceScope RAII(this, true);
+
+        // We need to poke around to find the bits that might be explicitly
+        // written.
+        TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
+        FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
+
+        if (auto *TPL = LE->getTemplateParameterList()) {
+          for (NamedDecl *D : *TPL) {
+            TraverseDecl(D);
+          }
+          if (Expr *RequiresClause = TPL->getRequiresClause()) {
+            TraverseStmt(RequiresClause);
+          }
+        }
+
+        if (LE->hasExplicitParameters()) {
+          // Visit parameters.
+          for (ParmVarDecl *Param : Proto.getParams())
+            TraverseDecl(Param);
+        }
+
+        const auto *T = Proto.getTypePtr();
+        for (const auto &E : T->exceptions())
+          TraverseType(E);
+
+        if (Expr *NE = T->getNoexceptExpr())
+          TraverseStmt(NE, Queue);
+
+        if (LE->hasExplicitResultType())
+          TraverseTypeLoc(Proto.getReturnLoc());
+        TraverseStmt(LE->getTrailingRequiresClause());
+      }
+
+      TraverseStmt(LE->getBody());
+      return true;
+    }
+    return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);
+  }
+
+  // Matches children or descendants of 'Node' with 'BaseMatcher'.
+  bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
+                                  const DynTypedMatcher &Matcher,
+                                  BoundNodesTreeBuilder *Builder, int MaxDepth,
+                                  BindKind Bind) {
+    // For AST-nodes that don't have an identity, we can't memoize.
+    if (!Node.getMemoizationData() || !Builder->isComparable())
+      return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
+
+    MatchKey Key;
+    Key.MatcherID = Matcher.getID();
+    Key.Node = Node;
+    // Note that we key on the bindings *before* the match.
+    Key.BoundNodes = *Builder;
+    Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
+    // Memoize result even doing a single-level match, it might be expensive.
+    Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
+    MemoizationMap::iterator I = ResultCache.find(Key);
+    if (I != ResultCache.end()) {
+      *Builder = I->second.Nodes;
+      return I->second.ResultOfMatch;
+    }
+
+    MemoizedMatchResult Result;
+    Result.Nodes = *Builder;
+    Result.ResultOfMatch =
+        matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);
+
+    MemoizedMatchResult &CachedResult = ResultCache[Key];
+    CachedResult = std::move(Result);
+
+    *Builder = CachedResult.Nodes;
+    return CachedResult.ResultOfMatch;
+  }
+
+  // Matches children or descendants of 'Node' with 'BaseMatcher'.
+  bool matchesRecursively(const DynTypedNode &Node,
+                          const DynTypedMatcher &Matcher,
+                          BoundNodesTreeBuilder *Builder, int MaxDepth,
+                          BindKind Bind) {
+    bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
+                           TraversingASTChildrenNotSpelledInSource;
+
+    bool IgnoreImplicitChildren = false;
+
+    if (isTraversalIgnoringImplicitNodes()) {
+      IgnoreImplicitChildren = true;
+    }
+
+    ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
+
+    MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
+                                 IgnoreImplicitChildren, Bind);
+    return Visitor.findMatch(Node);
+  }
+
+  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
+                          const Matcher<NamedDecl> &Base,
+                          BoundNodesTreeBuilder *Builder,
+                          bool Directly) override;
+
+  bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
+                              const Matcher<NamedDecl> &Base,
+                              BoundNodesTreeBuilder *Builder,
+                              bool Directly) override;
+
+  // Implements ASTMatchFinder::matchesChildOf.
+  bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
+                      const DynTypedMatcher &Matcher,
+                      BoundNodesTreeBuilder *Builder, BindKind Bind) override {
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);
+  }
+  // Implements ASTMatchFinder::matchesDescendantOf.
+  bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
+                           const DynTypedMatcher &Matcher,
+                           BoundNodesTreeBuilder *Builder,
+                           BindKind Bind) override {
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
+                                      Bind);
+  }
+  // Implements ASTMatchFinder::matchesAncestorOf.
+  bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
+                         const DynTypedMatcher &Matcher,
+                         BoundNodesTreeBuilder *Builder,
+                         AncestorMatchMode MatchMode) override {
+    // Reset the cache outside of the recursive call to make sure we
+    // don't invalidate any iterators.
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
+      return matchesParentOf(Node, Matcher, Builder);
+    return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
+  }
+
+  // Matches all registered matchers on the given node and calls the
+  // result callback for every node that matches.
+  void match(const DynTypedNode &Node) {
+    // FIXME: Improve this with a switch or a visitor pattern.
+    if (auto *N = Node.get<Decl>()) {
+      match(*N);
+    } else if (auto *N = Node.get<Stmt>()) {
+      match(*N);
+    } else if (auto *N = Node.get<Type>()) {
+      match(*N);
+    } else if (auto *N = Node.get<QualType>()) {
+      match(*N);
+    } else if (auto *N = Node.get<NestedNameSpecifier>()) {
+      match(*N);
+    } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
+      match(*N);
+    } else if (auto *N = Node.get<TypeLoc>()) {
+      match(*N);
+    } else if (auto *N = Node.get<CXXCtorInitializer>()) {
+      match(*N);
+    } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
+      match(*N);
+    } else if (auto *N = Node.get<Attr>()) {
+      match(*N);
+    }
+  }
+
+  template <typename T> void match(const T &Node) {
+    matchDispatch(&Node);
+  }
+
+  // Implements ASTMatchFinder::getASTContext.
+  ASTContext &getASTContext() const override { return *ActiveASTContext; }
+
+  bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return true; }
+
+  // We visit the lambda body explicitly, so instruct the RAV
+  // to not visit it on our behalf too.
+  bool shouldVisitLambdaBody() const { return false; }
+
+  bool IsMatchingInASTNodeNotSpelledInSource() const override {
+    return TraversingASTNodeNotSpelledInSource;
+  }
+  bool isMatchingChildrenNotSpelledInSource() const override {
+    return TraversingASTChildrenNotSpelledInSource;
+  }
+  void setMatchingChildrenNotSpelledInSource(bool Set) override {
+    TraversingASTChildrenNotSpelledInSource = Set;
+  }
+
+  bool IsMatchingInASTNodeNotAsIs() const override {
+    return TraversingASTNodeNotAsIs;
+  }
+
+  bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
+    ASTNodeNotSpelledInSourceScope RAII(this, true);
+    return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
+        D);
+  }
+
+  bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
+    ASTNodeNotSpelledInSourceScope RAII(this, true);
+    return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
+        D);
+  }
+
+  bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
+    ASTNodeNotSpelledInSourceScope RAII(this, true);
+    return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
+        D);
+  }
+
+private:
+  bool TraversingASTNodeNotSpelledInSource = false;
+  bool TraversingASTNodeNotAsIs = false;
+  bool TraversingASTChildrenNotSpelledInSource = false;
+
+  class CurMatchData {
+// We don't have enough free low bits in 32bit builds to discriminate 8 pointer
+// types in PointerUnion. so split the union in 2 using a free bit from the
+// callback pointer.
+#define CMD_TYPES_0                                                            \
+  const QualType *, const TypeLoc *, const NestedNameSpecifier *,              \
+      const NestedNameSpecifierLoc *
+#define CMD_TYPES_1                                                            \
+  const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *,       \
+      const DynTypedNode *
+
+#define IMPL(Index)                                                            \
+  template <typename NodeType>                                                 \
+  std::enable_if_t<                                                            \
+      llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value>             \
+  SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) {          \
+    assertEmpty();                                                             \
+    Callback.setPointerAndInt(CB, Index);                                      \
+    Node##Index = &N;                                                          \
+  }                                                                            \
+                                                                               \
+  template <typename T>                                                        \
+  std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value,       \
+                   const T *>                                                  \
+  getNode() const {                                                            \
+    assertHoldsState();                                                        \
+    return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>()    \
+                                        : nullptr;                             \
+  }
+
+  public:
+    CurMatchData() : Node0(nullptr) {}
+
+    IMPL(0)
+    IMPL(1)
+
+    const MatchCallback *getCallback() const { return Callback.getPointer(); }
+
+    void SetBoundNodes(const BoundNodes &BN) {
+      assertHoldsState();
+      BNodes = &BN;
+    }
+
+    void clearBoundNodes() {
+      assertHoldsState();
+      BNodes = nullptr;
+    }
+
+    const BoundNodes *getBoundNodes() const {
+      assertHoldsState();
+      return BNodes;
+    }
+
+    void reset() {
+      assertHoldsState();
+      Callback.setPointerAndInt(nullptr, 0);
+      Node0 = nullptr;
+    }
+
+  private:
+    void assertHoldsState() const {
+      assert(Callback.getPointer() != nullptr && !Node0.isNull());
+    }
+
+    void assertEmpty() const {
+      assert(Callback.getPointer() == nullptr && Node0.isNull() &&
+             BNodes == nullptr);
+    }
+
+    llvm::PointerIntPair<const MatchCallback *, 1> Callback;
+    union {
+      llvm::PointerUnion<CMD_TYPES_0> Node0;
+      llvm::PointerUnion<CMD_TYPES_1> Node1;
+    };
+    const BoundNodes *BNodes = nullptr;
+
+#undef CMD_TYPES_0
+#undef CMD_TYPES_1
+#undef IMPL
+  } CurMatchState;
+
+  struct CurMatchRAII {
+    template <typename NodeType>
+    CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,
+                 const NodeType &NT)
+        : MV(MV) {
+      MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
+    }
+
+    ~CurMatchRAII() { MV.CurMatchState.reset(); }
+
+  private:
+    MatchASTVisitor &MV;
+  };
+
+public:
+  class TraceReporter : llvm::PrettyStackTraceEntry {
+    static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,
+                         raw_ostream &OS) {
+      if (const auto *D = Node.get<Decl>()) {
+        OS << D->getDeclKindName() << "Decl ";
+        if (const auto *ND = dyn_cast<NamedDecl>(D)) {
+          ND->printQualifiedName(OS);
+          OS << " : ";
+        } else
+          OS << ": ";
+        D->getSourceRange().print(OS, Ctx.getSourceManager());
+      } else if (const auto *S = Node.get<Stmt>()) {
+        OS << S->getStmtClassName() << " : ";
+        S->getSourceRange().print(OS, Ctx.getSourceManager());
+      } else if (const auto *T = Node.get<Type>()) {
+        OS << T->getTypeClassName() << "Type : ";
+        QualType(T, 0).print(OS, Ctx.getPrintingPolicy());
+      } else if (const auto *QT = Node.get<QualType>()) {
+        OS << "QualType : ";
+        QT->print(OS, Ctx.getPrintingPolicy());
+      } else {
+        OS << Node.getNodeKind().asStringRef() << " : ";
+        Node.getSourceRange().print(OS, Ctx.getSourceManager());
+      }
+    }
+
+    static void dumpNodeFromState(const ASTContext &Ctx,
+                                  const CurMatchData &State, raw_ostream &OS) {
+      if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {
+        dumpNode(Ctx, *MatchNode, OS);
+      } else if (const auto *QT = State.getNode<QualType>()) {
+        dumpNode(Ctx, DynTypedNode::create(*QT), OS);
+      } else if (const auto *TL = State.getNode<TypeLoc>()) {
+        dumpNode(Ctx, DynTypedNode::create(*TL), OS);
+      } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {
+        dumpNode(Ctx, DynTypedNode::create(*NNS), OS);
+      } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {
+        dumpNode(Ctx, DynTypedNode::create(*NNSL), OS);
+      } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {
+        dumpNode(Ctx, DynTypedNode::create(*CtorInit), OS);
+      } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {
+        dumpNode(Ctx, DynTypedNode::create(*TAL), OS);
+      } else if (const auto *At = State.getNode<Attr>()) {
+        dumpNode(Ctx, DynTypedNode::create(*At), OS);
+      }
+    }
+
+  public:
+    TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}
+    void print(raw_ostream &OS) const override {
+      const CurMatchData &State = MV.CurMatchState;
+      const MatchCallback *CB = State.getCallback();
+      if (!CB) {
+        OS << "ASTMatcher: Not currently matching\n";
+        return;
+      }
+
+      assert(MV.ActiveASTContext &&
+             "ActiveASTContext should be set if there is a matched callback");
+
+      ASTContext &Ctx = MV.getASTContext();
+
+      if (const BoundNodes *Nodes = State.getBoundNodes()) {
+        OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";
+        dumpNodeFromState(Ctx, State, OS);
+        const BoundNodes::IDToNodeMap &Map = Nodes->getMap();
+        if (Map.empty()) {
+          OS << "\nNo bound nodes\n";
+          return;
+        }
+        OS << "\n--- Bound Nodes Begin ---\n";
+        for (const auto &Item : Map) {
+          OS << "    " << Item.first << " - { ";
+          dumpNode(Ctx, Item.second, OS);
+          OS << " }\n";
+        }
+        OS << "--- Bound Nodes End ---\n";
+      } else {
+        OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";
+        dumpNodeFromState(Ctx, State, OS);
+        OS << '\n';
+      }
+    }
+
+  private:
+    const MatchASTVisitor &MV;
+  };
+
+private:
+  struct ASTNodeNotSpelledInSourceScope {
+    ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
+        : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
+      V->TraversingASTNodeNotSpelledInSource = B;
+    }
+    ~ASTNodeNotSpelledInSourceScope() {
+      MV->TraversingASTNodeNotSpelledInSource = MB;
+    }
+
+  private:
+    MatchASTVisitor *MV;
+    bool MB;
+  };
+
+  struct ASTNodeNotAsIsSourceScope {
+    ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
+        : MV(V), MB(V->TraversingASTNodeNotAsIs) {
+      V->TraversingASTNodeNotAsIs = B;
+    }
+    ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
+
+  private:
+    MatchASTVisitor *MV;
+    bool MB;
+  };
+
+  class TimeBucketRegion {
+  public:
+    TimeBucketRegion() : Bucket(nullptr) {}
+    ~TimeBucketRegion() { setBucket(nullptr); }
+
+    /// Start timing for \p NewBucket.
+    ///
+    /// If there was a bucket already set, it will finish the timing for that
+    /// other bucket.
+    /// \p NewBucket will be timed until the next call to \c setBucket() or
+    /// until the \c TimeBucketRegion is destroyed.
+    /// If \p NewBucket is the same as the currently timed bucket, this call
+    /// does nothing.
+    void setBucket(llvm::TimeRecord *NewBucket) {
+      if (Bucket != NewBucket) {
+        auto Now = llvm::TimeRecord::getCurrentTime(true);
+        if (Bucket)
+          *Bucket += Now;
+        if (NewBucket)
+          *NewBucket -= Now;
+        Bucket = NewBucket;
+      }
+    }
+
+  private:
+    llvm::TimeRecord *Bucket;
+  };
+
+  /// Runs all the \p Matchers on \p Node.
+  ///
+  /// Used by \c matchDispatch() below.
+  template <typename T, typename MC>
+  void matchWithoutFilter(const T &Node, const MC &Matchers) {
+    const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
+    TimeBucketRegion Timer;
+    for (const auto &MP : Matchers) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+      BoundNodesTreeBuilder Builder;
+      CurMatchRAII RAII(*this, MP.second, Node);
+      if (MP.first.matches(Node, this, &Builder)) {
+        MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  void matchWithFilter(const DynTypedNode &DynNode) {
+    auto Kind = DynNode.getNodeKind();
+    auto it = MatcherFiltersMap.find(Kind);
+    const auto &Filter =
+        it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
+
+    if (Filter.empty())
+      return;
+
+    const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
+    TimeBucketRegion Timer;
+    auto &Matchers = this->Matchers->DeclOrStmt;
+    for (unsigned short I : Filter) {
+      auto &MP = Matchers[I];
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+      BoundNodesTreeBuilder Builder;
+
+      {
+        TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
+        if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
+            DynNode)
+          continue;
+      }
+
+      CurMatchRAII RAII(*this, MP.second, DynNode);
+      if (MP.first.matches(DynNode, this, &Builder)) {
+        MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
+    auto &Filter = MatcherFiltersMap[Kind];
+    auto &Matchers = this->Matchers->DeclOrStmt;
+    assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
+    for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
+      if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
+        Filter.push_back(I);
+      }
+    }
+    return Filter;
+  }
+
+  /// @{
+  /// Overloads to pair the different node types to their matchers.
+  void matchDispatch(const Decl *Node) {
+    return matchWithFilter(DynTypedNode::create(*Node));
+  }
+  void matchDispatch(const Stmt *Node) {
+    return matchWithFilter(DynTypedNode::create(*Node));
+  }
+
+  void matchDispatch(const Type *Node) {
+    matchWithoutFilter(QualType(Node, 0), Matchers->Type);
+  }
+  void matchDispatch(const TypeLoc *Node) {
+    matchWithoutFilter(*Node, Matchers->TypeLoc);
+  }
+  void matchDispatch(const QualType *Node) {
+    matchWithoutFilter(*Node, Matchers->Type);
+  }
+  void matchDispatch(const NestedNameSpecifier *Node) {
+    matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
+  }
+  void matchDispatch(const NestedNameSpecifierLoc *Node) {
+    matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
+  }
+  void matchDispatch(const CXXCtorInitializer *Node) {
+    matchWithoutFilter(*Node, Matchers->CtorInit);
+  }
+  void matchDispatch(const TemplateArgumentLoc *Node) {
+    matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);
+  }
+  void matchDispatch(const Attr *Node) {
+    matchWithoutFilter(*Node, Matchers->Attr);
+  }
+  void matchDispatch(const void *) { /* Do nothing. */ }
+  /// @}
+
+  // Returns whether a direct parent of \p Node matches \p Matcher.
+  // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
+  bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
+                       BoundNodesTreeBuilder *Builder) {
+    for (const auto &Parent : ActiveASTContext->getParents(Node)) {
+      BoundNodesTreeBuilder BuilderCopy = *Builder;
+      if (Matcher.matches(Parent, this, &BuilderCopy)) {
+        *Builder = std::move(BuilderCopy);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  // Returns whether an ancestor of \p Node matches \p Matcher.
+  //
+  // The order of matching (which can lead to different nodes being bound in
+  // case there are multiple matches) is breadth first search.
+  //
+  // To allow memoization in the very common case of having deeply nested
+  // expressions inside a template function, we first walk up the AST, memoizing
+  // the result of the match along the way, as long as there is only a single
+  // parent.
+  //
+  // Once there are multiple parents, the breadth first search order does not
+  // allow simple memoization on the ancestors. Thus, we only memoize as long
+  // as there is a single parent.
+  //
+  // We avoid a recursive implementation to prevent excessive stack use on
+  // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
+  bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
+                            const DynTypedMatcher &Matcher,
+                            BoundNodesTreeBuilder *Builder) {
+
+    // Memoization keys that can be updated with the result.
+    // These are the memoizable nodes in the chain of unique parents, which
+    // terminates when a node has multiple parents, or matches, or is the root.
+    std::vector<MatchKey> Keys;
+    // When returning, update the memoization cache.
+    auto Finish = [&](bool Matched) {
+      for (const auto &Key : Keys) {
+        MemoizedMatchResult &CachedResult = ResultCache[Key];
+        CachedResult.ResultOfMatch = Matched;
+        CachedResult.Nodes = *Builder;
+      }
+      return Matched;
+    };
+
+    // Loop while there's a single parent and we want to attempt memoization.
+    DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
+    for (;;) {
+      // A cache key only makes sense if memoization is possible.
+      if (Builder->isComparable()) {
+        Keys.emplace_back();
+        Keys.back().MatcherID = Matcher.getID();
+        Keys.back().Node = Node;
+        Keys.back().BoundNodes = *Builder;
+        Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
+        Keys.back().Type = MatchType::Ancestors;
+
+        // Check the cache.
+        MemoizationMap::iterator I = ResultCache.find(Keys.back());
+        if (I != ResultCache.end()) {
+          Keys.pop_back(); // Don't populate the cache for the matching node!
+          *Builder = I->second.Nodes;
+          return Finish(I->second.ResultOfMatch);
+        }
+      }
+
+      Parents = ActiveASTContext->getParents(Node);
+      // Either no parents or multiple parents: leave chain+memoize mode and
+      // enter bfs+forgetful mode.
+      if (Parents.size() != 1)
+        break;
+
+      // Check the next parent.
+      Node = *Parents.begin();
+      BoundNodesTreeBuilder BuilderCopy = *Builder;
+      if (Matcher.matches(Node, this, &BuilderCopy)) {
+        *Builder = std::move(BuilderCopy);
+        return Finish(true);
+      }
+    }
+    // We reached the end of the chain.
+
+    if (Parents.empty()) {
+      // Nodes may have no parents if:
+      //  a) the node is the TranslationUnitDecl
+      //  b) we have a limited traversal scope that excludes the parent edges
+      //  c) there is a bug in the AST, and the node is not reachable
+      // Usually the traversal scope is the whole AST, which precludes b.
+      // Bugs are common enough that it's worthwhile asserting when we can.
+#ifndef NDEBUG
+      if (!Node.get<TranslationUnitDecl>() &&
+          /* Traversal scope is full AST if any of the bounds are the TU */
+          llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
+            return D->getKind() == Decl::TranslationUnit;
+          })) {
+        llvm::errs() << "Tried to match orphan node:\n";
+        Node.dump(llvm::errs(), *ActiveASTContext);
+        llvm_unreachable("Parent map should be complete!");
+      }
+#endif
+    } else {
+      assert(Parents.size() > 1);
+      // BFS starting from the parents not yet considered.
+      // Memoization of newly visited nodes is not possible (but we still update
+      // results for the elements in the chain we found above).
+      std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
+      llvm::DenseSet<const void *> Visited;
+      while (!Queue.empty()) {
+        BoundNodesTreeBuilder BuilderCopy = *Builder;
+        if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
+          *Builder = std::move(BuilderCopy);
+          return Finish(true);
+        }
+        for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {
+          // Make sure we do not visit the same node twice.
+          // Otherwise, we'll visit the common ancestors as often as there
+          // are splits on the way down.
+          if (Visited.insert(Parent.getMemoizationData()).second)
+            Queue.push_back(Parent);
+        }
+        Queue.pop_front();
+      }
+    }
+    return Finish(false);
+  }
+
+  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
+  // the aggregated bound nodes for each match.
+  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
+    struct CurBoundScope {
+      CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)
+          : State(State) {
+        State.SetBoundNodes(BN);
+      }
+
+      ~CurBoundScope() { State.clearBoundNodes(); }
+
+    private:
+      MatchASTVisitor::CurMatchData &State;
+    };
+
+  public:
+    MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
+                 MatchFinder::MatchCallback *Callback)
+        : State(MV.CurMatchState), Context(Context), Callback(Callback) {}
+
+    void visitMatch(const BoundNodes& BoundNodesView) override {
+      TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
+      CurBoundScope RAII2(State, BoundNodesView);
+      Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
+    }
+
+  private:
+    MatchASTVisitor::CurMatchData &State;
+    ASTContext* Context;
+    MatchFinder::MatchCallback* Callback;
+  };
+
+  // Returns true if 'TypeNode' has an alias that matches the given matcher.
+  bool typeHasMatchingAlias(const Type *TypeNode,
+                            const Matcher<NamedDecl> &Matcher,
+                            BoundNodesTreeBuilder *Builder) {
+    const Type *const CanonicalType =
+      ActiveASTContext->getCanonicalType(TypeNode);
+    auto Aliases = TypeAliases.find(CanonicalType);
+    if (Aliases == TypeAliases.end())
+      return false;
+    for (const TypedefNameDecl *Alias : Aliases->second) {
+      BoundNodesTreeBuilder Result(*Builder);
+      if (Matcher.matches(*Alias, this, &Result)) {
+        *Builder = std::move(Result);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool
+  objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
+                                         const Matcher<NamedDecl> &Matcher,
+                                         BoundNodesTreeBuilder *Builder) {
+    auto Aliases = CompatibleAliases.find(InterfaceDecl);
+    if (Aliases == CompatibleAliases.end())
+      return false;
+    for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
+      BoundNodesTreeBuilder Result(*Builder);
+      if (Matcher.matches(*Alias, this, &Result)) {
+        *Builder = std::move(Result);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /// Bucket to record map.
+  ///
+  /// Used to get the appropriate bucket for each matcher.
+  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
+
+  const MatchFinder::MatchersByType *Matchers;
+
+  /// Filtered list of matcher indices for each matcher kind.
+  ///
+  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
+  /// kind (and derived kinds) so it is a waste to try every matcher on every
+  /// node.
+  /// We precalculate a list of matchers that pass the toplevel restrict check.
+  llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
+
+  const MatchFinder::MatchFinderOptions &Options;
+  ASTContext *ActiveASTContext;
+
+  // Maps a canonical type to its TypedefDecls.
+  llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
+
+  // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
+  llvm::DenseMap<const ObjCInterfaceDecl *,
+                 llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
+      CompatibleAliases;
+
+  // Maps (matcher, node) -> the match result for memoization.
+  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
+  MemoizationMap ResultCache;
+};
+
+static CXXRecordDecl *
+getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
+  if (auto *RD = TypeNode->getAsCXXRecordDecl())
+    return RD;
+
+  // Find the innermost TemplateSpecializationType that isn't an alias template.
+  auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
+  while (TemplateType && TemplateType->isTypeAlias())
+    TemplateType =
+        TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
+
+  // If this is the name of a (dependent) template specialization, use the
+  // definition of the template, even though it might be specialized later.
+  if (TemplateType)
+    if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
+          TemplateType->getTemplateName().getAsTemplateDecl()))
+      return ClassTemplate->getTemplatedDecl();
+
+  return nullptr;
+}
+
+// Returns true if the given C++ class is directly or indirectly derived
+// from a base type with the given name.  A class is not considered to be
+// derived from itself.
+bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
+                                         const Matcher<NamedDecl> &Base,
+                                         BoundNodesTreeBuilder *Builder,
+                                         bool Directly) {
+  if (!Declaration->hasDefinition())
+    return false;
+  for (const auto &It : Declaration->bases()) {
+    const Type *TypeNode = It.getType().getTypePtr();
+
+    if (typeHasMatchingAlias(TypeNode, Base, Builder))
+      return true;
+
+    // FIXME: Going to the primary template here isn't really correct, but
+    // unfortunately we accept a Decl matcher for the base class not a Type
+    // matcher, so it's the best thing we can do with our current interface.
+    CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
+    if (!ClassDecl)
+      continue;
+    if (ClassDecl == Declaration) {
+      // This can happen for recursive template definitions.
+      continue;
+    }
+    BoundNodesTreeBuilder Result(*Builder);
+    if (Base.matches(*ClassDecl, this, &Result)) {
+      *Builder = std::move(Result);
+      return true;
+    }
+    if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
+      return true;
+  }
+  return false;
+}
+
+// Returns true if the given Objective-C class is directly or indirectly
+// derived from a matching base class. A class is not considered to be derived
+// from itself.
+bool MatchASTVisitor::objcClassIsDerivedFrom(
+    const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
+    BoundNodesTreeBuilder *Builder, bool Directly) {
+  // Check if any of the superclasses of the class match.
+  for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
+       ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
+    // Check if there are any matching compatibility aliases.
+    if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
+      return true;
+
+    // Check if there are any matching type aliases.
+    const Type *TypeNode = ClassDecl->getTypeForDecl();
+    if (typeHasMatchingAlias(TypeNode, Base, Builder))
+      return true;
+
+    if (Base.matches(*ClassDecl, this, Builder))
+      return true;
+
+    // Not `return false` as a temporary workaround for PR43879.
+    if (Directly)
+      break;
+  }
+
+  return false;
+}
+
+bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
+  if (!DeclNode) {
+    return true;
+  }
+
+  bool ScopedTraversal =
+      TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
+  bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
+
+  if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
+    auto SK = CTSD->getSpecializationKind();
+    if (SK == TSK_ExplicitInstantiationDeclaration ||
+        SK == TSK_ExplicitInstantiationDefinition)
+      ScopedChildren = true;
+  } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
+    if (FD->isDefaulted())
+      ScopedChildren = true;
+    if (FD->isTemplateInstantiation())
+      ScopedTraversal = true;
+  } else if (isa<BindingDecl>(DeclNode)) {
+    ScopedChildren = true;
+  }
+
+  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
+  ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
+
+  match(*DeclNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
+}
+
+bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
+  if (!StmtNode) {
+    return true;
+  }
+  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
+                         TraversingASTChildrenNotSpelledInSource;
+
+  ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
+  match(*StmtNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue);
+}
+
+bool MatchASTVisitor::TraverseType(QualType TypeNode) {
+  match(TypeNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
+}
+
+bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
+  // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
+  // We still want to find those types via matchers, so we match them here. Note
+  // that the TypeLocs are structurally a shadow-hierarchy to the expressed
+  // type, so we visit all involved parts of a compound type when matching on
+  // each TypeLoc.
+  match(TypeLocNode);
+  match(TypeLocNode.getType());
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
+}
+
+bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
+  match(*NNS);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
+}
+
+bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
+    NestedNameSpecifierLoc NNS) {
+  if (!NNS)
+    return true;
+
+  match(NNS);
+
+  // We only match the nested name specifier here (as opposed to traversing it)
+  // because the traversal is already done in the parallel "Loc"-hierarchy.
+  if (NNS.hasQualifier())
+    match(*NNS.getNestedNameSpecifier());
+  return
+      RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
+}
+
+bool MatchASTVisitor::TraverseConstructorInitializer(
+    CXXCtorInitializer *CtorInit) {
+  if (!CtorInit)
+    return true;
+
+  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
+                         TraversingASTChildrenNotSpelledInSource;
+
+  if (!CtorInit->isWritten())
+    ScopedTraversal = true;
+
+  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
+
+  match(*CtorInit);
+
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
+      CtorInit);
+}
+
+bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
+  match(Loc);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(Loc);
+}
+
+bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
+  match(*AttrNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(AttrNode);
+}
+
+class MatchASTConsumer : public ASTConsumer {
+public:
+  MatchASTConsumer(MatchFinder *Finder,
+                   MatchFinder::ParsingDoneTestCallback *ParsingDone)
+      : Finder(Finder), ParsingDone(ParsingDone) {}
+
+private:
+  void HandleTranslationUnit(ASTContext &Context) override {
+    if (ParsingDone != nullptr) {
+      ParsingDone->run();
+    }
+    Finder->matchAST(Context);
+  }
+
+  MatchFinder *Finder;
+  MatchFinder::ParsingDoneTestCallback *ParsingDone;
+};
+
+} // end namespace
+} // end namespace internal
+
+MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
+                                      ASTContext *Context)
+  : Nodes(Nodes), Context(Context),
+    SourceManager(&Context->getSourceManager()) {}
+
+MatchFinder::MatchCallback::~MatchCallback() {}
+MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
+
+MatchFinder::MatchFinder(MatchFinderOptions Options)
+    : Options(std::move(Options)), ParsingDone(nullptr) {}
+
+MatchFinder::~MatchFinder() {}
+
+void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  std::optional<TraversalKind> TK;
+  if (Action)
+    TK = Action->getCheckTraversalKind();
+  if (TK)
+    Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
+  else
+    Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.Type.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  std::optional<TraversalKind> TK;
+  if (Action)
+    TK = Action->getCheckTraversalKind();
+  if (TK)
+    Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
+  else
+    Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.CtorInit.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
+                             MatchCallback *Action) {
+  Matchers.Attr.emplace_back(AttrMatch, Action);
+  Matchers.AllCallbacks.insert(Action);
+}
+
+bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
+                                    MatchCallback *Action) {
+  if (NodeMatch.canConvertTo<Decl>()) {
+    addMatcher(NodeMatch.convertTo<Decl>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<QualType>()) {
+    addMatcher(NodeMatch.convertTo<QualType>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<Stmt>()) {
+    addMatcher(NodeMatch.convertTo<Stmt>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
+    addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
+    addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<TypeLoc>()) {
+    addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
+    addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
+    addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
+    return true;
+  } else if (NodeMatch.canConvertTo<Attr>()) {
+    addMatcher(NodeMatch.convertTo<Attr>(), Action);
+    return true;
+  }
+  return false;
+}
+
+std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
+  return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
+}
+
+void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
+  internal::MatchASTVisitor Visitor(&Matchers, Options);
+  Visitor.set_active_ast_context(&Context);
+  Visitor.match(Node);
+}
+
+void MatchFinder::matchAST(ASTContext &Context) {
+  internal::MatchASTVisitor Visitor(&Matchers, Options);
+  internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
+  Visitor.set_active_ast_context(&Context);
+  Visitor.onStartOfTranslationUnit();
+  Visitor.TraverseAST(Context);
+  Visitor.onEndOfTranslationUnit();
+}
+
+void MatchFinder::registerTestCallbackAfterParsing(
+    MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
+  ParsingDone = NewParsingDone;
+}
+
+StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
+
+std::optional<TraversalKind>
+MatchFinder::MatchCallback::getCheckTraversalKind() const {
+  return std::nullopt;
+}
+
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/contrib/libs/clang16/lib/ASTMatchers/ASTMatchersInternal.cpp b/contrib/libs/clang16/lib/ASTMatchers/ASTMatchersInternal.cpp
new file mode 100644
index 00000000000..f1f73fc4207
--- /dev/null
+++ b/contrib/libs/clang16/lib/ASTMatchers/ASTMatchersInternal.cpp
@@ -0,0 +1,1087 @@
+//===- ASTMatchersInternal.cpp - Structural query framework ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  Implements the base layer of the matcher framework.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/ASTMatchersInternal.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/ParentMapContext.h"
+#include "clang/AST/PrettyPrinter.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Lex/Lexer.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Regex.h"
+#include "llvm/Support/WithColor.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <optional>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace clang {
+namespace ast_matchers {
+
+AST_MATCHER_P(ObjCMessageExpr, hasAnySelectorMatcher, std::vector<std::string>,
+              Matches) {
+  return llvm::is_contained(Matches, Node.getSelector().getAsString());
+}
+
+namespace internal {
+
+static bool notUnaryOperator(const DynTypedNode &DynNode,
+                             ASTMatchFinder *Finder,
+                             BoundNodesTreeBuilder *Builder,
+                             ArrayRef<DynTypedMatcher> InnerMatchers);
+
+static bool allOfVariadicOperator(const DynTypedNode &DynNode,
+                                  ASTMatchFinder *Finder,
+                                  BoundNodesTreeBuilder *Builder,
+                                  ArrayRef<DynTypedMatcher> InnerMatchers);
+
+static bool eachOfVariadicOperator(const DynTypedNode &DynNode,
+                                   ASTMatchFinder *Finder,
+                                   BoundNodesTreeBuilder *Builder,
+                                   ArrayRef<DynTypedMatcher> InnerMatchers);
+
+static bool anyOfVariadicOperator(const DynTypedNode &DynNode,
+                                  ASTMatchFinder *Finder,
+                                  BoundNodesTreeBuilder *Builder,
+                                  ArrayRef<DynTypedMatcher> InnerMatchers);
+
+static bool optionallyVariadicOperator(const DynTypedNode &DynNode,
+                                       ASTMatchFinder *Finder,
+                                       BoundNodesTreeBuilder *Builder,
+                                       ArrayRef<DynTypedMatcher> InnerMatchers);
+
+bool matchesAnyBase(const CXXRecordDecl &Node,
+                    const Matcher<CXXBaseSpecifier> &BaseSpecMatcher,
+                    ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) {
+  if (!Node.hasDefinition())
+    return false;
+
+  CXXBasePaths Paths;
+  Paths.setOrigin(&Node);
+
+  const auto basePredicate =
+      [Finder, Builder, &BaseSpecMatcher](const CXXBaseSpecifier *BaseSpec,
+                                          CXXBasePath &IgnoredParam) {
+        BoundNodesTreeBuilder Result(*Builder);
+        if (BaseSpecMatcher.matches(*BaseSpec, Finder, Builder)) {
+          *Builder = std::move(Result);
+          return true;
+        }
+        return false;
+      };
+
+  return Node.lookupInBases(basePredicate, Paths,
+                            /*LookupInDependent =*/true);
+}
+
+void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
+  if (Bindings.empty())
+    Bindings.push_back(BoundNodesMap());
+  for (BoundNodesMap &Binding : Bindings) {
+    ResultVisitor->visitMatch(BoundNodes(Binding));
+  }
+}
+
+namespace {
+
+using VariadicOperatorFunction = bool (*)(
+    const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+    BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
+
+template <VariadicOperatorFunction Func>
+class VariadicMatcher : public DynMatcherInterface {
+public:
+  VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
+      : InnerMatchers(std::move(InnerMatchers)) {}
+
+  bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    return Func(DynNode, Finder, Builder, InnerMatchers);
+  }
+
+private:
+  std::vector<DynTypedMatcher> InnerMatchers;
+};
+
+class IdDynMatcher : public DynMatcherInterface {
+public:
+  IdDynMatcher(StringRef ID,
+               IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher)
+      : ID(ID), InnerMatcher(std::move(InnerMatcher)) {}
+
+  bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
+    if (Result) Builder->setBinding(ID, DynNode);
+    return Result;
+  }
+
+  std::optional<clang::TraversalKind> TraversalKind() const override {
+    return InnerMatcher->TraversalKind();
+  }
+
+private:
+  const std::string ID;
+  const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
+};
+
+/// A matcher that always returns true.
+class TrueMatcherImpl : public DynMatcherInterface {
+public:
+  TrueMatcherImpl() = default;
+
+  bool dynMatches(const DynTypedNode &, ASTMatchFinder *,
+                  BoundNodesTreeBuilder *) const override {
+    return true;
+  }
+};
+
+/// A matcher that specifies a particular \c TraversalKind.
+///
+/// The kind provided to the constructor overrides any kind that may be
+/// specified by the `InnerMatcher`.
+class DynTraversalMatcherImpl : public DynMatcherInterface {
+public:
+  explicit DynTraversalMatcherImpl(
+      clang::TraversalKind TK,
+      IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher)
+      : TK(TK), InnerMatcher(std::move(InnerMatcher)) {}
+
+  bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    return this->InnerMatcher->dynMatches(DynNode, Finder, Builder);
+  }
+
+  std::optional<clang::TraversalKind> TraversalKind() const override {
+    return TK;
+  }
+
+private:
+  clang::TraversalKind TK;
+  IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
+};
+
+} // namespace
+
+bool ASTMatchFinder::isTraversalIgnoringImplicitNodes() const {
+  return getASTContext().getParentMapContext().getTraversalKind() ==
+         TK_IgnoreUnlessSpelledInSource;
+}
+
+DynTypedMatcher
+DynTypedMatcher::constructVariadic(DynTypedMatcher::VariadicOperator Op,
+                                   ASTNodeKind SupportedKind,
+                                   std::vector<DynTypedMatcher> InnerMatchers) {
+  assert(!InnerMatchers.empty() && "Array must not be empty.");
+  assert(llvm::all_of(InnerMatchers,
+                      [SupportedKind](const DynTypedMatcher &M) {
+                        return M.canConvertTo(SupportedKind);
+                      }) &&
+         "InnerMatchers must be convertible to SupportedKind!");
+
+  // We must relax the restrict kind here.
+  // The different operators might deal differently with a mismatch.
+  // Make it the same as SupportedKind, since that is the broadest type we are
+  // allowed to accept.
+  auto RestrictKind = SupportedKind;
+
+  switch (Op) {
+  case VO_AllOf:
+    // In the case of allOf() we must pass all the checks, so making
+    // RestrictKind the most restrictive can save us time. This way we reject
+    // invalid types earlier and we can elide the kind checks inside the
+    // matcher.
+    for (auto &IM : InnerMatchers) {
+      RestrictKind =
+          ASTNodeKind::getMostDerivedType(RestrictKind, IM.RestrictKind);
+    }
+    return DynTypedMatcher(
+        SupportedKind, RestrictKind,
+        new VariadicMatcher<allOfVariadicOperator>(std::move(InnerMatchers)));
+
+  case VO_AnyOf:
+    return DynTypedMatcher(
+        SupportedKind, RestrictKind,
+        new VariadicMatcher<anyOfVariadicOperator>(std::move(InnerMatchers)));
+
+  case VO_EachOf:
+    return DynTypedMatcher(
+        SupportedKind, RestrictKind,
+        new VariadicMatcher<eachOfVariadicOperator>(std::move(InnerMatchers)));
+
+  case VO_Optionally:
+    return DynTypedMatcher(SupportedKind, RestrictKind,
+                           new VariadicMatcher<optionallyVariadicOperator>(
+                               std::move(InnerMatchers)));
+
+  case VO_UnaryNot:
+    // FIXME: Implement the Not operator to take a single matcher instead of a
+    // vector.
+    return DynTypedMatcher(
+        SupportedKind, RestrictKind,
+        new VariadicMatcher<notUnaryOperator>(std::move(InnerMatchers)));
+  }
+  llvm_unreachable("Invalid Op value.");
+}
+
+DynTypedMatcher
+DynTypedMatcher::constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,
+                                            ASTNodeKind RestrictKind) {
+  DynTypedMatcher Copy = InnerMatcher;
+  Copy.RestrictKind = RestrictKind;
+  return Copy;
+}
+
+DynTypedMatcher DynTypedMatcher::withTraversalKind(TraversalKind TK) {
+  auto Copy = *this;
+  Copy.Implementation =
+      new DynTraversalMatcherImpl(TK, std::move(Copy.Implementation));
+  return Copy;
+}
+
+DynTypedMatcher DynTypedMatcher::trueMatcher(ASTNodeKind NodeKind) {
+  // We only ever need one instance of TrueMatcherImpl, so we create a static
+  // instance and reuse it to reduce the overhead of the matcher and increase
+  // the chance of cache hits.
+  static const llvm::IntrusiveRefCntPtr<TrueMatcherImpl> Instance =
+      new TrueMatcherImpl();
+  return DynTypedMatcher(NodeKind, NodeKind, Instance);
+}
+
+bool DynTypedMatcher::canMatchNodesOfKind(ASTNodeKind Kind) const {
+  return RestrictKind.isBaseOf(Kind);
+}
+
+DynTypedMatcher DynTypedMatcher::dynCastTo(const ASTNodeKind Kind) const {
+  auto Copy = *this;
+  Copy.SupportedKind = Kind;
+  Copy.RestrictKind = ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
+  return Copy;
+}
+
+bool DynTypedMatcher::matches(const DynTypedNode &DynNode,
+                              ASTMatchFinder *Finder,
+                              BoundNodesTreeBuilder *Builder) const {
+  TraversalKindScope RAII(Finder->getASTContext(),
+                          Implementation->TraversalKind());
+
+  if (Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotSpelledInSource())
+    return false;
+
+  if (!Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotAsIs())
+    return false;
+
+  auto N =
+      Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
+
+  if (RestrictKind.isBaseOf(N.getNodeKind()) &&
+      Implementation->dynMatches(N, Finder, Builder)) {
+    return true;
+  }
+  // Delete all bindings when a matcher does not match.
+  // This prevents unexpected exposure of bound nodes in unmatches
+  // branches of the match tree.
+  Builder->removeBindings([](const BoundNodesMap &) { return true; });
+  return false;
+}
+
+bool DynTypedMatcher::matchesNoKindCheck(const DynTypedNode &DynNode,
+                                         ASTMatchFinder *Finder,
+                                         BoundNodesTreeBuilder *Builder) const {
+  TraversalKindScope raii(Finder->getASTContext(),
+                          Implementation->TraversalKind());
+
+  if (Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotSpelledInSource())
+    return false;
+
+  if (!Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotAsIs())
+    return false;
+
+  auto N =
+      Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
+
+  assert(RestrictKind.isBaseOf(N.getNodeKind()));
+  if (Implementation->dynMatches(N, Finder, Builder)) {
+    return true;
+  }
+  // Delete all bindings when a matcher does not match.
+  // This prevents unexpected exposure of bound nodes in unmatches
+  // branches of the match tree.
+  Builder->removeBindings([](const BoundNodesMap &) { return true; });
+  return false;
+}
+
+std::optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
+  if (!AllowBind)
+    return std::nullopt;
+  auto Result = *this;
+  Result.Implementation =
+      new IdDynMatcher(ID, std::move(Result.Implementation));
+  return std::move(Result);
+}
+
+bool DynTypedMatcher::canConvertTo(ASTNodeKind To) const {
+  const auto From = getSupportedKind();
+  auto QualKind = ASTNodeKind::getFromNodeKind<QualType>();
+  auto TypeKind = ASTNodeKind::getFromNodeKind<Type>();
+  /// Mimic the implicit conversions of Matcher<>.
+  /// - From Matcher<Type> to Matcher<QualType>
+  if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
+  /// - From Matcher<Base> to Matcher<Derived>
+  return From.isBaseOf(To);
+}
+
+void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
+  Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
+}
+
+static bool notUnaryOperator(const DynTypedNode &DynNode,
+                             ASTMatchFinder *Finder,
+                             BoundNodesTreeBuilder *Builder,
+                             ArrayRef<DynTypedMatcher> InnerMatchers) {
+  if (InnerMatchers.size() != 1)
+    return false;
+
+  // The 'unless' matcher will always discard the result:
+  // If the inner matcher doesn't match, unless returns true,
+  // but the inner matcher cannot have bound anything.
+  // If the inner matcher matches, the result is false, and
+  // any possible binding will be discarded.
+  // We still need to hand in all the bound nodes up to this
+  // point so the inner matcher can depend on bound nodes,
+  // and we need to actively discard the bound nodes, otherwise
+  // the inner matcher will reset the bound nodes if it doesn't
+  // match, but this would be inversed by 'unless'.
+  BoundNodesTreeBuilder Discard(*Builder);
+  return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
+}
+
+static bool allOfVariadicOperator(const DynTypedNode &DynNode,
+                                  ASTMatchFinder *Finder,
+                                  BoundNodesTreeBuilder *Builder,
+                                  ArrayRef<DynTypedMatcher> InnerMatchers) {
+  // allOf leads to one matcher for each alternative in the first
+  // matcher combined with each alternative in the second matcher.
+  // Thus, we can reuse the same Builder.
+  return llvm::all_of(InnerMatchers, [&](const DynTypedMatcher &InnerMatcher) {
+    return InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder);
+  });
+}
+
+static bool eachOfVariadicOperator(const DynTypedNode &DynNode,
+                                   ASTMatchFinder *Finder,
+                                   BoundNodesTreeBuilder *Builder,
+                                   ArrayRef<DynTypedMatcher> InnerMatchers) {
+  BoundNodesTreeBuilder Result;
+  bool Matched = false;
+  for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
+    BoundNodesTreeBuilder BuilderInner(*Builder);
+    if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
+      Matched = true;
+      Result.addMatch(BuilderInner);
+    }
+  }
+  *Builder = std::move(Result);
+  return Matched;
+}
+
+static bool anyOfVariadicOperator(const DynTypedNode &DynNode,
+                                  ASTMatchFinder *Finder,
+                                  BoundNodesTreeBuilder *Builder,
+                                  ArrayRef<DynTypedMatcher> InnerMatchers) {
+  for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
+    BoundNodesTreeBuilder Result = *Builder;
+    if (InnerMatcher.matches(DynNode, Finder, &Result)) {
+      *Builder = std::move(Result);
+      return true;
+    }
+  }
+  return false;
+}
+
+static bool
+optionallyVariadicOperator(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+                           BoundNodesTreeBuilder *Builder,
+                           ArrayRef<DynTypedMatcher> InnerMatchers) {
+  if (InnerMatchers.size() != 1)
+    return false;
+
+  BoundNodesTreeBuilder Result(*Builder);
+  if (InnerMatchers[0].matches(DynNode, Finder, &Result))
+    *Builder = std::move(Result);
+  return true;
+}
+
+inline static
+std::vector<std::string> vectorFromRefs(ArrayRef<const StringRef *> NameRefs) {
+  std::vector<std::string> Names;
+  Names.reserve(NameRefs.size());
+  for (auto *Name : NameRefs)
+    Names.emplace_back(*Name);
+  return Names;
+}
+
+Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs) {
+  return internal::Matcher<NamedDecl>(
+      new internal::HasNameMatcher(vectorFromRefs(NameRefs)));
+}
+
+Matcher<ObjCMessageExpr> hasAnySelectorFunc(
+    ArrayRef<const StringRef *> NameRefs) {
+  return hasAnySelectorMatcher(vectorFromRefs(NameRefs));
+}
+
+HasOpNameMatcher hasAnyOperatorNameFunc(ArrayRef<const StringRef *> NameRefs) {
+  return HasOpNameMatcher(vectorFromRefs(NameRefs));
+}
+
+HasOverloadOpNameMatcher
+hasAnyOverloadedOperatorNameFunc(ArrayRef<const StringRef *> NameRefs) {
+  return HasOverloadOpNameMatcher(vectorFromRefs(NameRefs));
+}
+
+HasNameMatcher::HasNameMatcher(std::vector<std::string> N)
+    : UseUnqualifiedMatch(
+          llvm::all_of(N, [](StringRef Name) { return !Name.contains("::"); })),
+      Names(std::move(N)) {
+#ifndef NDEBUG
+  for (StringRef Name : Names)
+    assert(!Name.empty());
+#endif
+}
+
+static bool consumeNameSuffix(StringRef &FullName, StringRef Suffix) {
+  StringRef Name = FullName;
+  if (!Name.endswith(Suffix))
+    return false;
+  Name = Name.drop_back(Suffix.size());
+  if (!Name.empty()) {
+    if (!Name.endswith("::"))
+      return false;
+    Name = Name.drop_back(2);
+  }
+  FullName = Name;
+  return true;
+}
+
+static StringRef getNodeName(const NamedDecl &Node,
+                             llvm::SmallString<128> &Scratch) {
+  // Simple name.
+  if (Node.getIdentifier())
+    return Node.getName();
+
+  if (Node.getDeclName()) {
+    // Name needs to be constructed.
+    Scratch.clear();
+    llvm::raw_svector_ostream OS(Scratch);
+    Node.printName(OS);
+    return OS.str();
+  }
+
+  return "(anonymous)";
+}
+
+static StringRef getNodeName(const RecordDecl &Node,
+                             llvm::SmallString<128> &Scratch) {
+  if (Node.getIdentifier()) {
+    return Node.getName();
+  }
+  Scratch.clear();
+  return ("(anonymous " + Node.getKindName() + ")").toStringRef(Scratch);
+}
+
+static StringRef getNodeName(const NamespaceDecl &Node,
+                             llvm::SmallString<128> &Scratch) {
+  return Node.isAnonymousNamespace() ? "(anonymous namespace)" : Node.getName();
+}
+
+namespace {
+
+class PatternSet {
+public:
+  PatternSet(ArrayRef<std::string> Names) {
+    Patterns.reserve(Names.size());
+    for (StringRef Name : Names)
+      Patterns.push_back({Name, Name.startswith("::")});
+  }
+
+  /// Consumes the name suffix from each pattern in the set and removes the ones
+  /// that didn't match.
+  /// Return true if there are still any patterns left.
+  bool consumeNameSuffix(StringRef NodeName, bool CanSkip) {
+    for (size_t I = 0; I < Patterns.size();) {
+      if (::clang::ast_matchers::internal::consumeNameSuffix(Patterns[I].P,
+                                                             NodeName) ||
+          CanSkip) {
+        ++I;
+      } else {
+        Patterns.erase(Patterns.begin() + I);
+      }
+    }
+    return !Patterns.empty();
+  }
+
+  /// Check if any of the patterns are a match.
+  /// A match will be a pattern that was fully consumed, that also matches the
+  /// 'fully qualified' requirement.
+  bool foundMatch(bool AllowFullyQualified) const {
+    return llvm::any_of(Patterns, [&](const Pattern &Pattern) {
+      return Pattern.P.empty() &&
+             (AllowFullyQualified || !Pattern.IsFullyQualified);
+    });
+  }
+
+private:
+  struct Pattern {
+    StringRef P;
+    bool IsFullyQualified;
+  };
+
+  llvm::SmallVector<Pattern, 8> Patterns;
+};
+
+} // namespace
+
+bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
+  assert(UseUnqualifiedMatch);
+  llvm::SmallString<128> Scratch;
+  StringRef NodeName = getNodeName(Node, Scratch);
+  return llvm::any_of(Names, [&](StringRef Name) {
+    return consumeNameSuffix(Name, NodeName) && Name.empty();
+  });
+}
+
+bool HasNameMatcher::matchesNodeFullFast(const NamedDecl &Node) const {
+  PatternSet Patterns(Names);
+  llvm::SmallString<128> Scratch;
+
+  // This function is copied and adapted from NamedDecl::printQualifiedName()
+  // By matching each part individually we optimize in a couple of ways:
+  //  - We can exit early on the first failure.
+  //  - We can skip inline/anonymous namespaces without another pass.
+  //  - We print one name at a time, reducing the chance of overflowing the
+  //    inlined space of the SmallString.
+
+  // First, match the name.
+  if (!Patterns.consumeNameSuffix(getNodeName(Node, Scratch),
+                                  /*CanSkip=*/false))
+    return false;
+
+  // Try to match each declaration context.
+  // We are allowed to skip anonymous and inline namespaces if they don't match.
+  const DeclContext *Ctx = Node.getDeclContext();
+
+  if (Ctx->isFunctionOrMethod())
+    return Patterns.foundMatch(/*AllowFullyQualified=*/false);
+
+  for (; Ctx; Ctx = Ctx->getParent()) {
+    // Linkage Spec can just be ignored
+    // FIXME: Any other DeclContext kinds that can be safely disregarded
+    if (isa<LinkageSpecDecl>(Ctx))
+      continue;
+    if (!isa<NamedDecl>(Ctx))
+      break;
+    if (Patterns.foundMatch(/*AllowFullyQualified=*/false))
+      return true;
+
+    if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
+      // If it matches (or we can skip it), continue.
+      if (Patterns.consumeNameSuffix(getNodeName(*ND, Scratch),
+                                     /*CanSkip=*/ND->isAnonymousNamespace() ||
+                                         ND->isInline()))
+        continue;
+      return false;
+    }
+    if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
+      if (!isa<ClassTemplateSpecializationDecl>(Ctx)) {
+        if (Patterns.consumeNameSuffix(getNodeName(*RD, Scratch),
+                                       /*CanSkip=*/false))
+          continue;
+
+        return false;
+      }
+    }
+
+    // We don't know how to deal with this DeclContext.
+    // Fallback to the slow version of the code.
+    return matchesNodeFullSlow(Node);
+  }
+
+  return Patterns.foundMatch(/*AllowFullyQualified=*/true);
+}
+
+bool HasNameMatcher::matchesNodeFullSlow(const NamedDecl &Node) const {
+  const bool SkipUnwrittenCases[] = {false, true};
+  for (bool SkipUnwritten : SkipUnwrittenCases) {
+    llvm::SmallString<128> NodeName = StringRef("::");
+    llvm::raw_svector_ostream OS(NodeName);
+
+    PrintingPolicy Policy = Node.getASTContext().getPrintingPolicy();
+    Policy.SuppressUnwrittenScope = SkipUnwritten;
+    Policy.SuppressInlineNamespace = SkipUnwritten;
+    Node.printQualifiedName(OS, Policy);
+
+    const StringRef FullName = OS.str();
+
+    for (const StringRef Pattern : Names) {
+      if (Pattern.startswith("::")) {
+        if (FullName == Pattern)
+          return true;
+      } else if (FullName.endswith(Pattern) &&
+                 FullName.drop_back(Pattern.size()).endswith("::")) {
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
+  assert(matchesNodeFullFast(Node) == matchesNodeFullSlow(Node));
+  if (UseUnqualifiedMatch) {
+    assert(matchesNodeUnqualified(Node) == matchesNodeFullFast(Node));
+    return matchesNodeUnqualified(Node);
+  }
+  return matchesNodeFullFast(Node);
+}
+
+// Checks whether \p Loc points to a token with source text of \p TokenText.
+static bool isTokenAtLoc(const SourceManager &SM, const LangOptions &LangOpts,
+                         StringRef Text, SourceLocation Loc) {
+  llvm::SmallString<16> Buffer;
+  bool Invalid = false;
+  // Since `Loc` may point into an expansion buffer, which has no corresponding
+  // source, we need to look at the spelling location to read the actual source.
+  StringRef TokenText = Lexer::getSpelling(SM.getSpellingLoc(Loc), Buffer, SM,
+                                           LangOpts, &Invalid);
+  return !Invalid && Text == TokenText;
+}
+
+std::optional<SourceLocation>
+getExpansionLocOfMacro(StringRef MacroName, SourceLocation Loc,
+                       const ASTContext &Context) {
+  auto &SM = Context.getSourceManager();
+  const LangOptions &LangOpts = Context.getLangOpts();
+  while (Loc.isMacroID()) {
+    SrcMgr::ExpansionInfo Expansion =
+        SM.getSLocEntry(SM.getFileID(Loc)).getExpansion();
+    if (Expansion.isMacroArgExpansion())
+      // Check macro argument for an expansion of the given macro. For example,
+      // `F(G(3))`, where `MacroName` is `G`.
+      if (std::optional<SourceLocation> ArgLoc = getExpansionLocOfMacro(
+              MacroName, Expansion.getSpellingLoc(), Context))
+        return ArgLoc;
+    Loc = Expansion.getExpansionLocStart();
+    if (isTokenAtLoc(SM, LangOpts, MacroName, Loc))
+      return Loc;
+  }
+  return std::nullopt;
+}
+
+std::shared_ptr<llvm::Regex> createAndVerifyRegex(StringRef Regex,
+                                                  llvm::Regex::RegexFlags Flags,
+                                                  StringRef MatcherID) {
+  assert(!Regex.empty() && "Empty regex string");
+  auto SharedRegex = std::make_shared<llvm::Regex>(Regex, Flags);
+  std::string Error;
+  if (!SharedRegex->isValid(Error)) {
+    llvm::WithColor::error()
+        << "building matcher '" << MatcherID << "': " << Error << "\n";
+    llvm::WithColor::note() << " input was '" << Regex << "'\n";
+  }
+  return SharedRegex;
+}
+} // end namespace internal
+
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAutoreleasePoolStmt>
+    autoreleasePoolStmt;
+const internal::VariadicDynCastAllOfMatcher<Decl, TranslationUnitDecl>
+    translationUnitDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TypedefDecl> typedefDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TypedefNameDecl>
+    typedefNameDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TypeAliasDecl> typeAliasDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TypeAliasTemplateDecl>
+    typeAliasTemplateDecl;
+const internal::VariadicAllOfMatcher<Decl> decl;
+const internal::VariadicDynCastAllOfMatcher<Decl, DecompositionDecl> decompositionDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, BindingDecl> bindingDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, LinkageSpecDecl>
+    linkageSpecDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, NamedDecl> namedDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, LabelDecl> labelDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, NamespaceDecl> namespaceDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, NamespaceAliasDecl>
+    namespaceAliasDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, RecordDecl> recordDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXRecordDecl> cxxRecordDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ClassTemplateDecl>
+    classTemplateDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl,
+                                            ClassTemplateSpecializationDecl>
+    classTemplateSpecializationDecl;
+const internal::VariadicDynCastAllOfMatcher<
+    Decl, ClassTemplatePartialSpecializationDecl>
+    classTemplatePartialSpecializationDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, DeclaratorDecl>
+    declaratorDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ParmVarDecl> parmVarDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, AccessSpecDecl>
+    accessSpecDecl;
+const internal::VariadicAllOfMatcher<CXXBaseSpecifier> cxxBaseSpecifier;
+const internal::VariadicAllOfMatcher<CXXCtorInitializer> cxxCtorInitializer;
+const internal::VariadicAllOfMatcher<TemplateArgument> templateArgument;
+const internal::VariadicAllOfMatcher<TemplateArgumentLoc> templateArgumentLoc;
+const internal::VariadicAllOfMatcher<TemplateName> templateName;
+const internal::VariadicDynCastAllOfMatcher<Decl, NonTypeTemplateParmDecl>
+    nonTypeTemplateParmDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TemplateTypeParmDecl>
+    templateTypeParmDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TemplateTemplateParmDecl>
+    templateTemplateParmDecl;
+
+const internal::VariadicAllOfMatcher<LambdaCapture> lambdaCapture;
+const internal::VariadicAllOfMatcher<QualType> qualType;
+const internal::VariadicAllOfMatcher<Type> type;
+const internal::VariadicAllOfMatcher<TypeLoc> typeLoc;
+
+const internal::VariadicDynCastAllOfMatcher<TypeLoc, QualifiedTypeLoc>
+    qualifiedTypeLoc;
+const internal::VariadicDynCastAllOfMatcher<TypeLoc, PointerTypeLoc>
+    pointerTypeLoc;
+const internal::VariadicDynCastAllOfMatcher<TypeLoc, ReferenceTypeLoc>
+    referenceTypeLoc;
+const internal::VariadicDynCastAllOfMatcher<TypeLoc,
+                                            TemplateSpecializationTypeLoc>
+    templateSpecializationTypeLoc;
+const internal::VariadicDynCastAllOfMatcher<TypeLoc, ElaboratedTypeLoc>
+    elaboratedTypeLoc;
+
+const internal::VariadicDynCastAllOfMatcher<Stmt, UnaryExprOrTypeTraitExpr>
+    unaryExprOrTypeTraitExpr;
+const internal::VariadicDynCastAllOfMatcher<Decl, ValueDecl> valueDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXConstructorDecl>
+    cxxConstructorDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXDestructorDecl>
+    cxxDestructorDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, EnumDecl> enumDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, EnumConstantDecl>
+    enumConstantDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, TagDecl> tagDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXMethodDecl> cxxMethodDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXConversionDecl>
+    cxxConversionDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, VarDecl> varDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, FieldDecl> fieldDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, IndirectFieldDecl>
+    indirectFieldDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, FunctionDecl> functionDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, FunctionTemplateDecl>
+    functionTemplateDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, FriendDecl> friendDecl;
+const internal::VariadicAllOfMatcher<Stmt> stmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DeclStmt> declStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, MemberExpr> memberExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, UnresolvedMemberExpr>
+    unresolvedMemberExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDependentScopeMemberExpr>
+    cxxDependentScopeMemberExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CallExpr> callExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, LambdaExpr> lambdaExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXMemberCallExpr>
+    cxxMemberCallExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCMessageExpr>
+    objcMessageExpr;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCInterfaceDecl>
+    objcInterfaceDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCImplementationDecl>
+    objcImplementationDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCProtocolDecl>
+    objcProtocolDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCCategoryDecl>
+    objcCategoryDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCCategoryImplDecl>
+    objcCategoryImplDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCMethodDecl>
+    objcMethodDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, BlockDecl>
+    blockDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCIvarDecl> objcIvarDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, ObjCPropertyDecl>
+    objcPropertyDecl;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtThrowStmt>
+    objcThrowStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtTryStmt> objcTryStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtCatchStmt>
+    objcCatchStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtFinallyStmt>
+    objcFinallyStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ExprWithCleanups>
+    exprWithCleanups;
+const internal::VariadicDynCastAllOfMatcher<Stmt, InitListExpr> initListExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXStdInitializerListExpr>
+    cxxStdInitializerListExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ImplicitValueInitExpr>
+    implicitValueInitExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ParenListExpr> parenListExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, SubstNonTypeTemplateParmExpr>
+    substNonTypeTemplateParmExpr;
+const internal::VariadicDynCastAllOfMatcher<Decl, UsingDecl> usingDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, UsingEnumDecl> usingEnumDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, UsingDirectiveDecl>
+    usingDirectiveDecl;
+const internal::VariadicDynCastAllOfMatcher<Stmt, UnresolvedLookupExpr>
+    unresolvedLookupExpr;
+const internal::VariadicDynCastAllOfMatcher<Decl, UnresolvedUsingValueDecl>
+    unresolvedUsingValueDecl;
+const internal::VariadicDynCastAllOfMatcher<Decl, UnresolvedUsingTypenameDecl>
+    unresolvedUsingTypenameDecl;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ConstantExpr> constantExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ParenExpr> parenExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXConstructExpr>
+    cxxConstructExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXUnresolvedConstructExpr>
+    cxxUnresolvedConstructExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThisExpr> cxxThisExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXBindTemporaryExpr>
+    cxxBindTemporaryExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, MaterializeTemporaryExpr>
+    materializeTemporaryExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNewExpr> cxxNewExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDeleteExpr> cxxDeleteExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
+    cxxNoexceptExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ArraySubscriptExpr>
+    arraySubscriptExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDefaultArgExpr>
+    cxxDefaultArgExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXOperatorCallExpr>
+    cxxOperatorCallExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXRewrittenBinaryOperator>
+    cxxRewrittenBinaryOperator;
+const internal::VariadicDynCastAllOfMatcher<Stmt, Expr> expr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DeclRefExpr> declRefExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCIvarRefExpr> objcIvarRefExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, BlockExpr> blockExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, IfStmt> ifStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ForStmt> forStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXForRangeStmt>
+    cxxForRangeStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, WhileStmt> whileStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DoStmt> doStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, BreakStmt> breakStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ContinueStmt> continueStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CoreturnStmt> coreturnStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ReturnStmt> returnStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, GotoStmt> gotoStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, LabelStmt> labelStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, AddrLabelExpr> addrLabelExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchStmt> switchStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchCase> switchCase;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CaseStmt> caseStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DefaultStmt> defaultStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundStmt> compoundStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXCatchStmt> cxxCatchStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXTryStmt> cxxTryStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThrowExpr> cxxThrowExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, NullStmt> nullStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, AsmStmt> asmStmt;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXBoolLiteralExpr>
+    cxxBoolLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, StringLiteral> stringLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCStringLiteral> objcStringLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CharacterLiteral>
+    characterLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, IntegerLiteral>
+    integerLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, FloatingLiteral> floatLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ImaginaryLiteral> imaginaryLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, FixedPointLiteral>
+    fixedPointLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, UserDefinedLiteral>
+    userDefinedLiteral;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundLiteralExpr>
+    compoundLiteralExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNullPtrLiteralExpr>
+    cxxNullPtrLiteralExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ChooseExpr> chooseExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CoawaitExpr>
+    coawaitExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DependentCoawaitExpr>
+    dependentCoawaitExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CoyieldExpr>
+    coyieldExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, GNUNullExpr> gnuNullExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, GenericSelectionExpr>
+    genericSelectionExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, AtomicExpr> atomicExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, StmtExpr> stmtExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, BinaryOperator>
+    binaryOperator;
+const internal::MapAnyOfMatcher<BinaryOperator, CXXOperatorCallExpr,
+                                CXXRewrittenBinaryOperator>
+    binaryOperation;
+const internal::MapAnyOfMatcher<CallExpr, CXXConstructExpr> invocation;
+const internal::VariadicDynCastAllOfMatcher<Stmt, UnaryOperator> unaryOperator;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ConditionalOperator>
+    conditionalOperator;
+const internal::VariadicDynCastAllOfMatcher<Stmt, BinaryConditionalOperator>
+    binaryConditionalOperator;
+const internal::VariadicDynCastAllOfMatcher<Stmt, OpaqueValueExpr>
+    opaqueValueExpr;
+const internal::VariadicDynCastAllOfMatcher<Decl, StaticAssertDecl>
+    staticAssertDecl;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXReinterpretCastExpr>
+    cxxReinterpretCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXStaticCastExpr>
+    cxxStaticCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDynamicCastExpr>
+    cxxDynamicCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXConstCastExpr>
+    cxxConstCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CStyleCastExpr>
+    cStyleCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ExplicitCastExpr>
+    explicitCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ImplicitCastExpr>
+    implicitCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CastExpr> castExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXFunctionalCastExpr>
+    cxxFunctionalCastExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CXXTemporaryObjectExpr>
+    cxxTemporaryObjectExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, PredefinedExpr>
+    predefinedExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, DesignatedInitExpr>
+    designatedInitExpr;
+const internal::VariadicOperatorMatcherFunc<
+    2, std::numeric_limits<unsigned>::max()>
+    eachOf = {internal::DynTypedMatcher::VO_EachOf};
+const internal::VariadicOperatorMatcherFunc<
+    2, std::numeric_limits<unsigned>::max()>
+    anyOf = {internal::DynTypedMatcher::VO_AnyOf};
+const internal::VariadicOperatorMatcherFunc<
+    2, std::numeric_limits<unsigned>::max()>
+    allOf = {internal::DynTypedMatcher::VO_AllOf};
+const internal::VariadicOperatorMatcherFunc<1, 1> optionally = {
+    internal::DynTypedMatcher::VO_Optionally};
+const internal::VariadicFunction<internal::Matcher<NamedDecl>, StringRef,
+                                 internal::hasAnyNameFunc>
+    hasAnyName = {};
+
+const internal::VariadicFunction<internal::HasOpNameMatcher, StringRef,
+                                 internal::hasAnyOperatorNameFunc>
+    hasAnyOperatorName = {};
+const internal::VariadicFunction<internal::HasOverloadOpNameMatcher, StringRef,
+                                 internal::hasAnyOverloadedOperatorNameFunc>
+    hasAnyOverloadedOperatorName = {};
+const internal::VariadicFunction<internal::Matcher<ObjCMessageExpr>, StringRef,
+                                 internal::hasAnySelectorFunc>
+    hasAnySelector = {};
+const internal::ArgumentAdaptingMatcherFunc<internal::HasMatcher> has = {};
+const internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher>
+    hasDescendant = {};
+const internal::ArgumentAdaptingMatcherFunc<internal::ForEachMatcher> forEach =
+    {};
+const internal::ArgumentAdaptingMatcherFunc<internal::ForEachDescendantMatcher>
+    forEachDescendant = {};
+const internal::ArgumentAdaptingMatcherFunc<
+    internal::HasParentMatcher,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc, Attr>,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc, Attr>>
+    hasParent = {};
+const internal::ArgumentAdaptingMatcherFunc<
+    internal::HasAncestorMatcher,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc, Attr>,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc, Attr>>
+    hasAncestor = {};
+const internal::VariadicOperatorMatcherFunc<1, 1> unless = {
+    internal::DynTypedMatcher::VO_UnaryNot};
+const internal::VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
+const internal::VariadicAllOfMatcher<NestedNameSpecifierLoc>
+    nestedNameSpecifierLoc;
+const internal::VariadicAllOfMatcher<Attr> attr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, CUDAKernelCallExpr>
+    cudaKernelCallExpr;
+const AstTypeMatcher<BuiltinType> builtinType;
+const AstTypeMatcher<ArrayType> arrayType;
+const AstTypeMatcher<ComplexType> complexType;
+const AstTypeMatcher<ConstantArrayType> constantArrayType;
+const AstTypeMatcher<DeducedTemplateSpecializationType>
+    deducedTemplateSpecializationType;
+const AstTypeMatcher<DependentSizedArrayType> dependentSizedArrayType;
+const AstTypeMatcher<IncompleteArrayType> incompleteArrayType;
+const AstTypeMatcher<VariableArrayType> variableArrayType;
+const AstTypeMatcher<AtomicType> atomicType;
+const AstTypeMatcher<AutoType> autoType;
+const AstTypeMatcher<DecltypeType> decltypeType;
+const AstTypeMatcher<FunctionType> functionType;
+const AstTypeMatcher<FunctionProtoType> functionProtoType;
+const AstTypeMatcher<ParenType> parenType;
+const AstTypeMatcher<BlockPointerType> blockPointerType;
+const AstTypeMatcher<MemberPointerType> memberPointerType;
+const AstTypeMatcher<PointerType> pointerType;
+const AstTypeMatcher<ObjCObjectPointerType> objcObjectPointerType;
+const AstTypeMatcher<ReferenceType> referenceType;
+const AstTypeMatcher<LValueReferenceType> lValueReferenceType;
+const AstTypeMatcher<RValueReferenceType> rValueReferenceType;
+const AstTypeMatcher<TypedefType> typedefType;
+const AstTypeMatcher<EnumType> enumType;
+const AstTypeMatcher<TemplateSpecializationType> templateSpecializationType;
+const AstTypeMatcher<UnaryTransformType> unaryTransformType;
+const AstTypeMatcher<RecordType> recordType;
+const AstTypeMatcher<TagType> tagType;
+const AstTypeMatcher<ElaboratedType> elaboratedType;
+const AstTypeMatcher<UsingType> usingType;
+const AstTypeMatcher<SubstTemplateTypeParmType> substTemplateTypeParmType;
+const AstTypeMatcher<TemplateTypeParmType> templateTypeParmType;
+const AstTypeMatcher<InjectedClassNameType> injectedClassNameType;
+const AstTypeMatcher<DecayedType> decayedType;
+AST_TYPELOC_TRAVERSE_MATCHER_DEF(hasElementType,
+                                 AST_POLYMORPHIC_SUPPORTED_TYPES(ArrayType,
+                                                                 ComplexType));
+AST_TYPELOC_TRAVERSE_MATCHER_DEF(hasValueType,
+                                 AST_POLYMORPHIC_SUPPORTED_TYPES(AtomicType));
+AST_TYPELOC_TRAVERSE_MATCHER_DEF(
+    pointee,
+    AST_POLYMORPHIC_SUPPORTED_TYPES(BlockPointerType, MemberPointerType,
+                                    PointerType, ReferenceType));
+
+const internal::VariadicDynCastAllOfMatcher<Stmt, OMPExecutableDirective>
+    ompExecutableDirective;
+const internal::VariadicDynCastAllOfMatcher<OMPClause, OMPDefaultClause>
+    ompDefaultClause;
+const internal::VariadicDynCastAllOfMatcher<Decl, CXXDeductionGuideDecl>
+    cxxDeductionGuideDecl;
+
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/contrib/libs/clang16/lib/ASTMatchers/GtestMatchers.cpp b/contrib/libs/clang16/lib/ASTMatchers/GtestMatchers.cpp
new file mode 100644
index 00000000000..6e4c12f3196
--- /dev/null
+++ b/contrib/libs/clang16/lib/ASTMatchers/GtestMatchers.cpp
@@ -0,0 +1,234 @@
+//===- GtestMatchers.cpp - AST Matchers for Gtest ---------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements several matchers for popular gtest macros. In general,
+// AST matchers cannot match calls to macros. However, we can simulate such
+// matches if the macro definition has identifiable elements that themselves can
+// be matched. In that case, we can match on those elements and then check that
+// the match occurs within an expansion of the desired macro. The more uncommon
+// the identified elements, the more efficient this process will be.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/GtestMatchers.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace {
+
+enum class MacroType {
+  Expect,
+  Assert,
+  On,
+};
+
+} // namespace
+
+static DeclarationMatcher getComparisonDecl(GtestCmp Cmp) {
+  switch (Cmp) {
+  case GtestCmp::Eq:
+    return cxxMethodDecl(hasName("Compare"),
+                         ofClass(cxxRecordDecl(isSameOrDerivedFrom(
+                             hasName("::testing::internal::EqHelper")))));
+  case GtestCmp::Ne:
+    return functionDecl(hasName("::testing::internal::CmpHelperNE"));
+  case GtestCmp::Ge:
+    return functionDecl(hasName("::testing::internal::CmpHelperGE"));
+  case GtestCmp::Gt:
+    return functionDecl(hasName("::testing::internal::CmpHelperGT"));
+  case GtestCmp::Le:
+    return functionDecl(hasName("::testing::internal::CmpHelperLE"));
+  case GtestCmp::Lt:
+    return functionDecl(hasName("::testing::internal::CmpHelperLT"));
+  }
+  llvm_unreachable("Unhandled GtestCmp enum");
+}
+
+static llvm::StringRef getMacroTypeName(MacroType Macro) {
+  switch (Macro) {
+  case MacroType::Expect:
+    return "EXPECT";
+  case MacroType::Assert:
+    return "ASSERT";
+  case MacroType::On:
+    return "ON";
+  }
+  llvm_unreachable("Unhandled MacroType enum");
+}
+
+static llvm::StringRef getComparisonTypeName(GtestCmp Cmp) {
+  switch (Cmp) {
+  case GtestCmp::Eq:
+    return "EQ";
+  case GtestCmp::Ne:
+    return "NE";
+  case GtestCmp::Ge:
+    return "GE";
+  case GtestCmp::Gt:
+    return "GT";
+  case GtestCmp::Le:
+    return "LE";
+  case GtestCmp::Lt:
+    return "LT";
+  }
+  llvm_unreachable("Unhandled GtestCmp enum");
+}
+
+static std::string getMacroName(MacroType Macro, GtestCmp Cmp) {
+  return (getMacroTypeName(Macro) + "_" + getComparisonTypeName(Cmp)).str();
+}
+
+static std::string getMacroName(MacroType Macro, llvm::StringRef Operation) {
+  return (getMacroTypeName(Macro) + "_" + Operation).str();
+}
+
+// Under the hood, ON_CALL is expanded to a call to `InternalDefaultActionSetAt`
+// to set a default action spec to the underlying function mocker, while
+// EXPECT_CALL is expanded to a call to `InternalExpectedAt` to set a new
+// expectation spec.
+static llvm::StringRef getSpecSetterName(MacroType Macro) {
+  switch (Macro) {
+  case MacroType::On:
+    return "InternalDefaultActionSetAt";
+  case MacroType::Expect:
+    return "InternalExpectedAt";
+  default:
+    llvm_unreachable("Unhandled MacroType enum");
+  }
+  llvm_unreachable("Unhandled MacroType enum");
+}
+
+// In general, AST matchers cannot match calls to macros. However, we can
+// simulate such matches if the macro definition has identifiable elements that
+// themselves can be matched. In that case, we can match on those elements and
+// then check that the match occurs within an expansion of the desired
+// macro. The more uncommon the identified elements, the more efficient this
+// process will be.
+//
+// We use this approach to implement the derived matchers gtestAssert and
+// gtestExpect.
+static internal::BindableMatcher<Stmt>
+gtestComparisonInternal(MacroType Macro, GtestCmp Cmp, StatementMatcher Left,
+                        StatementMatcher Right) {
+  return callExpr(isExpandedFromMacro(getMacroName(Macro, Cmp)),
+                  callee(getComparisonDecl(Cmp)), hasArgument(2, Left),
+                  hasArgument(3, Right));
+}
+
+static internal::BindableMatcher<Stmt>
+gtestThatInternal(MacroType Macro, StatementMatcher Actual,
+                  StatementMatcher Matcher) {
+  return cxxOperatorCallExpr(
+      isExpandedFromMacro(getMacroName(Macro, "THAT")),
+      hasOverloadedOperatorName("()"), hasArgument(2, Actual),
+      hasArgument(
+          0, expr(hasType(classTemplateSpecializationDecl(hasName(
+                      "::testing::internal::PredicateFormatterFromMatcher"))),
+                  ignoringImplicit(
+                      callExpr(callee(functionDecl(hasName(
+                                   "::testing::internal::"
+                                   "MakePredicateFormatterFromMatcher"))),
+                               hasArgument(0, ignoringImplicit(Matcher)))))));
+}
+
+static internal::BindableMatcher<Stmt>
+gtestCallInternal(MacroType Macro, StatementMatcher MockCall, MockArgs Args) {
+  // A ON_CALL or EXPECT_CALL macro expands to different AST structures
+  // depending on whether the mock method has arguments or not.
+  switch (Args) {
+  // For example,
+  // `ON_CALL(mock, TwoParamMethod)` is expanded to
+  // `mock.gmock_TwoArgsMethod(WithoutMatchers(),
+  // nullptr).InternalDefaultActionSetAt(...)`.
+  // EXPECT_CALL is the same except
+  // that it calls `InternalExpectedAt` instead of `InternalDefaultActionSetAt`
+  // in the end.
+  case MockArgs::None:
+    return cxxMemberCallExpr(
+        isExpandedFromMacro(getMacroName(Macro, "CALL")),
+        callee(functionDecl(hasName(getSpecSetterName(Macro)))),
+        onImplicitObjectArgument(ignoringImplicit(MockCall)));
+  // For example,
+  // `ON_CALL(mock, TwoParamMethod(m1, m2))` is expanded to
+  // `mock.gmock_TwoParamMethod(m1,m2)(WithoutMatchers(),
+  // nullptr).InternalDefaultActionSetAt(...)`.
+  // EXPECT_CALL is the same except that it calls `InternalExpectedAt` instead
+  // of `InternalDefaultActionSetAt` in the end.
+  case MockArgs::Some:
+    return cxxMemberCallExpr(
+        isExpandedFromMacro(getMacroName(Macro, "CALL")),
+        callee(functionDecl(hasName(getSpecSetterName(Macro)))),
+        onImplicitObjectArgument(ignoringImplicit(cxxOperatorCallExpr(
+            hasOverloadedOperatorName("()"), argumentCountIs(3),
+            hasArgument(0, ignoringImplicit(MockCall))))));
+  }
+  llvm_unreachable("Unhandled MockArgs enum");
+}
+
+static internal::BindableMatcher<Stmt>
+gtestCallInternal(MacroType Macro, StatementMatcher MockObject,
+                  llvm::StringRef MockMethodName, MockArgs Args) {
+  return gtestCallInternal(
+      Macro,
+      cxxMemberCallExpr(
+          onImplicitObjectArgument(MockObject),
+          callee(functionDecl(hasName(("gmock_" + MockMethodName).str())))),
+      Args);
+}
+
+internal::BindableMatcher<Stmt> gtestAssert(GtestCmp Cmp, StatementMatcher Left,
+                                            StatementMatcher Right) {
+  return gtestComparisonInternal(MacroType::Assert, Cmp, Left, Right);
+}
+
+internal::BindableMatcher<Stmt> gtestExpect(GtestCmp Cmp, StatementMatcher Left,
+                                            StatementMatcher Right) {
+  return gtestComparisonInternal(MacroType::Expect, Cmp, Left, Right);
+}
+
+internal::BindableMatcher<Stmt> gtestAssertThat(StatementMatcher Actual,
+                                                StatementMatcher Matcher) {
+  return gtestThatInternal(MacroType::Assert, Actual, Matcher);
+}
+
+internal::BindableMatcher<Stmt> gtestExpectThat(StatementMatcher Actual,
+                                                StatementMatcher Matcher) {
+  return gtestThatInternal(MacroType::Expect, Actual, Matcher);
+}
+
+internal::BindableMatcher<Stmt> gtestOnCall(StatementMatcher MockObject,
+                                            llvm::StringRef MockMethodName,
+                                            MockArgs Args) {
+  return gtestCallInternal(MacroType::On, MockObject, MockMethodName, Args);
+}
+
+internal::BindableMatcher<Stmt> gtestOnCall(StatementMatcher MockCall,
+                                            MockArgs Args) {
+  return gtestCallInternal(MacroType::On, MockCall, Args);
+}
+
+internal::BindableMatcher<Stmt> gtestExpectCall(StatementMatcher MockObject,
+                                                llvm::StringRef MockMethodName,
+                                                MockArgs Args) {
+  return gtestCallInternal(MacroType::Expect, MockObject, MockMethodName, Args);
+}
+
+internal::BindableMatcher<Stmt> gtestExpectCall(StatementMatcher MockCall,
+                                                MockArgs Args) {
+  return gtestCallInternal(MacroType::Expect, MockCall, Args);
+}
+
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/contrib/libs/clang16/lib/ASTMatchers/ya.make b/contrib/libs/clang16/lib/ASTMatchers/ya.make
new file mode 100644
index 00000000000..17d12f38acb
--- /dev/null
+++ b/contrib/libs/clang16/lib/ASTMatchers/ya.make
@@ -0,0 +1,34 @@
+# Generated by devtools/yamaker.
+
+LIBRARY()
+
+LICENSE(Apache-2.0 WITH LLVM-exception)
+
+LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
+
+PEERDIR(
+    contrib/libs/clang16
+    contrib/libs/clang16/include
+    contrib/libs/clang16/lib/AST
+    contrib/libs/clang16/lib/Basic
+    contrib/libs/clang16/lib/Lex
+    contrib/libs/llvm16
+    contrib/libs/llvm16/lib/Frontend/OpenMP
+    contrib/libs/llvm16/lib/Support
+)
+
+ADDINCL(
+    contrib/libs/clang16/lib/ASTMatchers
+)
+
+NO_COMPILER_WARNINGS()
+
+NO_UTIL()
+
+SRCS(
+    ASTMatchFinder.cpp
+    ASTMatchersInternal.cpp
+    GtestMatchers.cpp
+)
+
+END()