7 files changed, 3816 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchFinder.cpp
new file mode 100644
index 0000000..c5f3063
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -0,0 +1,1000 @@
+//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  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/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;
+
+// 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;
+  ast_type_traits::DynTypedNode Node;
+  BoundNodesTreeBuilder BoundNodes;
+
+  bool operator<(const MatchKey &Other) const {
+    return std::tie(MatcherID, Node, BoundNodes) <
+           std::tie(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,
+                       ASTMatchFinder::TraversalKind Traversal,
+                       ASTMatchFinder::BindKind Bind)
+      : Matcher(Matcher),
+        Finder(Finder),
+        Builder(Builder),
+        CurrentDepth(0),
+        MaxDepth(MaxDepth),
+        Traversal(Traversal),
+        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 ast_type_traits::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);
+    // 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) {
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    return (DeclNode == nullptr) || traverse(*DeclNode);
+  }
+  bool TraverseStmt(Stmt *StmtNode) {
+    ScopedIncrement ScopedDepth(&CurrentDepth);
+    const Stmt *StmtToTraverse = StmtNode;
+    if (Traversal ==
+        ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
+      const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
+      if (ExprNode) {
+        StmtToTraverse = ExprNode->IgnoreParenImpCasts();
+      }
+    }
+    return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse);
+  }
+  // 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 shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return true; }
+  // Disables data recursion. We intercept Traverse* methods in the RAV, which
+  // are not triggered during data recursion.
+  bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
+
+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);
+  }
+
+  // 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(ast_type_traits::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(ast_type_traits::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 ASTMatchFinder::TraversalKind Traversal;
+  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.hasValue();
+    TimeBucketRegion Timer;
+    for (MatchCallback *MC : Matchers->AllCallbacks) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MC->getID()]);
+      MC->onStartOfTranslationUnit();
+    }
+  }
+
+  void onEndOfTranslationUnit() {
+    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+    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 TraverseDecl(Decl *DeclNode);
+  bool TraverseStmt(Stmt *StmtNode);
+  bool TraverseType(QualType TypeNode);
+  bool TraverseTypeLoc(TypeLoc TypeNode);
+  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
+
+  // Matches children or descendants of 'Node' with 'BaseMatcher'.
+  bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
+                                  const DynTypedMatcher &Matcher,
+                                  BoundNodesTreeBuilder *Builder, int MaxDepth,
+                                  TraversalKind Traversal, 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, Traversal,
+                                Bind);
+
+    MatchKey Key;
+    Key.MatcherID = Matcher.getID();
+    Key.Node = Node;
+    // Note that we key on the bindings *before* the match.
+    Key.BoundNodes = *Builder;
+
+    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, Traversal, 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 ast_type_traits::DynTypedNode &Node,
+                          const DynTypedMatcher &Matcher,
+                          BoundNodesTreeBuilder *Builder, int MaxDepth,
+                          TraversalKind Traversal, BindKind Bind) {
+    MatchChildASTVisitor Visitor(
+      &Matcher, this, Builder, MaxDepth, Traversal, Bind);
+    return Visitor.findMatch(Node);
+  }
+
+  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
+                          const Matcher<NamedDecl> &Base,
+                          BoundNodesTreeBuilder *Builder) override;
+
+  // Implements ASTMatchFinder::matchesChildOf.
+  bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
+                      const DynTypedMatcher &Matcher,
+                      BoundNodesTreeBuilder *Builder,
+                      TraversalKind Traversal,
+                      BindKind Bind) override {
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
+                                      Bind);
+  }
+  // Implements ASTMatchFinder::matchesDescendantOf.
+  bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
+                           const DynTypedMatcher &Matcher,
+                           BoundNodesTreeBuilder *Builder,
+                           BindKind Bind) override {
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
+                                      TK_AsIs, Bind);
+  }
+  // Implements ASTMatchFinder::matchesAncestorOf.
+  bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
+                         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();
+    return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
+                                                MatchMode);
+  }
+
+  // Matches all registered matchers on the given node and calls the
+  // result callback for every node that matches.
+  void match(const ast_type_traits::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);
+    }
+  }
+
+  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; }
+  // Disables data recursion. We intercept Traverse* methods in the RAV, which
+  // are not triggered during data recursion.
+  bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
+
+private:
+  class TimeBucketRegion {
+  public:
+    TimeBucketRegion() : Bucket(nullptr) {}
+    ~TimeBucketRegion() { setBucket(nullptr); }
+
+    /// \brief 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;
+  };
+
+  /// \brief 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.hasValue();
+    TimeBucketRegion Timer;
+    for (const auto &MP : Matchers) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+      BoundNodesTreeBuilder Builder;
+      if (MP.first.matches(Node, this, &Builder)) {
+        MatchVisitor Visitor(ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  void matchWithFilter(const ast_type_traits::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.hasValue();
+    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;
+      if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
+        MatchVisitor Visitor(ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  const std::vector<unsigned short> &
+  getFilterForKind(ast_type_traits::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;
+  }
+
+  /// @{
+  /// \brief Overloads to pair the different node types to their matchers.
+  void matchDispatch(const Decl *Node) {
+    return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
+  }
+  void matchDispatch(const Stmt *Node) {
+    return matchWithFilter(ast_type_traits::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 void *) { /* Do nothing. */ }
+  /// @}
+
+  // 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.
+  bool memoizedMatchesAncestorOfRecursively(
+      const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
+      BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
+    if (Node.get<TranslationUnitDecl>() ==
+        ActiveASTContext->getTranslationUnitDecl())
+      return false;
+    assert(Node.getMemoizationData() &&
+           "Invariant broken: only nodes that support memoization may be "
+           "used in the parent map.");
+
+    MatchKey Key;
+    Key.MatcherID = Matcher.getID();
+    Key.Node = Node;
+    Key.BoundNodes = *Builder;
+
+    // Note that we cannot use insert and reuse the iterator, as recursive
+    // calls to match might invalidate the result cache iterators.
+    MemoizationMap::iterator I = ResultCache.find(Key);
+    if (I != ResultCache.end()) {
+      *Builder = I->second.Nodes;
+      return I->second.ResultOfMatch;
+    }
+
+    MemoizedMatchResult Result;
+    Result.ResultOfMatch = false;
+    Result.Nodes = *Builder;
+
+    const auto &Parents = ActiveASTContext->getParents(Node);
+    assert(!Parents.empty() && "Found node that is not in the parent map.");
+    if (Parents.size() == 1) {
+      // Only one parent - do recursive memoization.
+      const ast_type_traits::DynTypedNode Parent = Parents[0];
+      if (Matcher.matches(Parent, this, &Result.Nodes)) {
+        Result.ResultOfMatch = true;
+      } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
+        // Reset the results to not include the bound nodes from the failed
+        // match above.
+        Result.Nodes = *Builder;
+        Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
+            Parent, Matcher, &Result.Nodes, MatchMode);
+        // Once we get back from the recursive call, the result will be the
+        // same as the parent's result.
+      }
+    } else {
+      // Multiple parents - BFS over the rest of the nodes.
+      llvm::DenseSet<const void *> Visited;
+      std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
+                                                      Parents.end());
+      while (!Queue.empty()) {
+        Result.Nodes = *Builder;
+        if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
+          Result.ResultOfMatch = true;
+          break;
+        }
+        if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
+          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();
+      }
+    }
+
+    MemoizedMatchResult &CachedResult = ResultCache[Key];
+    CachedResult = std::move(Result);
+
+    *Builder = CachedResult.Nodes;
+    return CachedResult.ResultOfMatch;
+  }
+
+  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
+  // the aggregated bound nodes for each match.
+  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
+  public:
+    MatchVisitor(ASTContext* Context,
+                 MatchFinder::MatchCallback* Callback)
+      : Context(Context),
+        Callback(Callback) {}
+
+    void visitMatch(const BoundNodes& BoundNodesView) override {
+      Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
+    }
+
+  private:
+    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);
+    for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) {
+      BoundNodesTreeBuilder Result(*Builder);
+      if (Matcher.matches(*Alias, this, &Result)) {
+        *Builder = std::move(Result);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /// \brief Bucket to record map.
+  ///
+  /// Used to get the appropriate bucket for each matcher.
+  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
+
+  const MatchFinder::MatchersByType *Matchers;
+
+  /// \brief 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.
+  /// This also allows us to skip the restrict check at matching time. See
+  /// use \c matchesNoKindCheck() above.
+  llvm::DenseMap<ast_type_traits::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 (matcher, node) -> the match result for memoization.
+  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
+  MemoizationMap ResultCache;
+};
+
+static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
+  // Type::getAs<...>() drills through typedefs.
+  if (TypeNode->getAs<DependentNameType>() != nullptr ||
+      TypeNode->getAs<DependentTemplateSpecializationType>() != nullptr ||
+      TypeNode->getAs<TemplateTypeParmType>() != nullptr)
+    // Dependent names and template TypeNode parameters will be matched when
+    // the template is instantiated.
+    return nullptr;
+  TemplateSpecializationType const *TemplateType =
+      TypeNode->getAs<TemplateSpecializationType>();
+  if (!TemplateType) {
+    return TypeNode->getAsCXXRecordDecl();
+  }
+  if (TemplateType->getTemplateName().isDependent())
+    // Dependent template specializations will be matched when the
+    // template is instantiated.
+    return nullptr;
+
+  // For template specialization types which are specializing a template
+  // declaration which is an explicit or partial specialization of another
+  // template declaration, getAsCXXRecordDecl() returns the corresponding
+  // ClassTemplateSpecializationDecl.
+  //
+  // For template specialization types which are specializing a template
+  // declaration which is neither an explicit nor partial specialization of
+  // another template declaration, getAsCXXRecordDecl() returns NULL and
+  // we get the CXXRecordDecl of the templated declaration.
+  CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
+  if (SpecializationDecl) {
+    return SpecializationDecl;
+  }
+  NamedDecl *Templated =
+      TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
+  if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
+    return TemplatedRecord;
+  }
+  // Now it can still be that we have an alias template.
+  TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
+  assert(AliasDecl);
+  return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
+}
+
+// Returns true if the given 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) {
+  if (!Declaration->hasDefinition())
+    return false;
+  for (const auto &It : Declaration->bases()) {
+    const Type *TypeNode = It.getType().getTypePtr();
+
+    if (typeHasMatchingAlias(TypeNode, Base, Builder))
+      return true;
+
+    CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
+    if (!ClassDecl)
+      continue;
+    if (ClassDecl == Declaration) {
+      // This can happen for recursive template definitions; if the
+      // current declaration did not match, we can safely return false.
+      return false;
+    }
+    BoundNodesTreeBuilder Result(*Builder);
+    if (Base.matches(*ClassDecl, this, &Result)) {
+      *Builder = std::move(Result);
+      return true;
+    }
+    if (classIsDerivedFrom(ClassDecl, Base, Builder))
+      return true;
+  }
+  return false;
+}
+
+bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
+  if (!DeclNode) {
+    return true;
+  }
+  match(*DeclNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
+}
+
+bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
+  if (!StmtNode) {
+    return true;
+  }
+  match(*StmtNode);
+  return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
+}
+
+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) {
+  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);
+}
+
+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) {
+  Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
+}
+
+void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.Type.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
+}
+
+void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
+}
+
+void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.NestedNameSpecifier.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
+}
+
+void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.NestedNameSpecifierLoc.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
+}
+
+void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
+                             MatchCallback *Action) {
+  Matchers.TypeLoc.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(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;
+  }
+  return false;
+}
+
+std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
+  return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
+}
+
+void MatchFinder::match(const clang::ast_type_traits::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);
+  Visitor.set_active_ast_context(&Context);
+  Visitor.onStartOfTranslationUnit();
+  Visitor.TraverseDecl(Context.getTranslationUnitDecl());
+  Visitor.onEndOfTranslationUnit();
+}
+
+void MatchFinder::registerTestCallbackAfterParsing(
+    MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
+  ParsingDone = NewParsingDone;
+}
+
+StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
+
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchersInternal.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
new file mode 100644
index 0000000..2c482e3
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
@@ -0,0 +1,344 @@
+//===--- ASTMatchersInternal.cpp - Structural query framework -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  Implements the base layer of the matcher framework.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchersInternal.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/ManagedStatic.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace internal {
+
+bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
+                      ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
+                      ArrayRef<DynTypedMatcher> InnerMatchers);
+
+bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                           ASTMatchFinder *Finder,
+                           BoundNodesTreeBuilder *Builder,
+                           ArrayRef<DynTypedMatcher> InnerMatchers);
+
+bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                            ASTMatchFinder *Finder,
+                            BoundNodesTreeBuilder *Builder,
+                            ArrayRef<DynTypedMatcher> InnerMatchers);
+
+bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                           ASTMatchFinder *Finder,
+                           BoundNodesTreeBuilder *Builder,
+                           ArrayRef<DynTypedMatcher> InnerMatchers);
+
+
+void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
+  if (Bindings.empty())
+    Bindings.push_back(BoundNodesMap());
+  for (BoundNodesMap &Binding : Bindings) {
+    ResultVisitor->visitMatch(BoundNodes(Binding));
+  }
+}
+
+namespace {
+
+typedef bool (*VariadicOperatorFunction)(
+    const ast_type_traits::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 ast_type_traits::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,
+               const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
+      : ID(ID), InnerMatcher(InnerMatcher) {}
+
+  bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
+                  ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
+    if (Result) Builder->setBinding(ID, DynNode);
+    return Result;
+  }
+
+ private:
+  const std::string ID;
+  const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
+};
+
+/// \brief A matcher that always returns true.
+///
+/// We only ever need one instance of this matcher, so we create a global one
+/// and reuse it to reduce the overhead of the matcher and increase the chance
+/// of cache hits.
+class TrueMatcherImpl : public DynMatcherInterface {
+public:
+  TrueMatcherImpl() {
+    Retain(); // Reference count will never become zero.
+  }
+  bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
+                  BoundNodesTreeBuilder *) const override {
+    return true;
+  }
+};
+static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
+
+}  // namespace
+
+DynTypedMatcher DynTypedMatcher::constructVariadic(
+    DynTypedMatcher::VariadicOperator Op,
+    std::vector<DynTypedMatcher> InnerMatchers) {
+  assert(InnerMatchers.size() > 0 && "Array must not be empty.");
+  assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(),
+                     [&InnerMatchers](const DynTypedMatcher &M) {
+           return InnerMatchers[0].SupportedKind.isSame(M.SupportedKind);
+         }) &&
+         "SupportedKind must match!");
+
+  auto SupportedKind = InnerMatchers[0].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 = ast_type_traits::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_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::trueMatcher(
+    ast_type_traits::ASTNodeKind NodeKind) {
+  return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
+}
+
+bool DynTypedMatcher::canMatchNodesOfKind(
+    ast_type_traits::ASTNodeKind Kind) const {
+  return RestrictKind.isBaseOf(Kind);
+}
+
+DynTypedMatcher DynTypedMatcher::dynCastTo(
+    const ast_type_traits::ASTNodeKind Kind) const {
+  auto Copy = *this;
+  Copy.SupportedKind = Kind;
+  Copy.RestrictKind =
+      ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
+  return Copy;
+}
+
+bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
+                              ASTMatchFinder *Finder,
+                              BoundNodesTreeBuilder *Builder) const {
+  if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
+      Implementation->dynMatches(DynNode, 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 ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
+    BoundNodesTreeBuilder *Builder) const {
+  assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
+  if (Implementation->dynMatches(DynNode, 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;
+}
+
+llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
+  if (!AllowBind) return llvm::None;
+  auto Result = *this;
+  Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
+  return Result;
+}
+
+bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
+  const auto From = getSupportedKind();
+  auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
+  auto TypeKind = ast_type_traits::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());
+}
+
+bool NotUnaryOperator(const ast_type_traits::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);
+}
+
+bool AllOfVariadicOperator(const ast_type_traits::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.
+  for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
+    if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
+      return false;
+  }
+  return true;
+}
+
+bool EachOfVariadicOperator(const ast_type_traits::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;
+}
+
+bool AnyOfVariadicOperator(const ast_type_traits::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;
+}
+
+HasNameMatcher::HasNameMatcher(StringRef NameRef)
+    : UseUnqualifiedMatch(NameRef.find("::") == NameRef.npos), Name(NameRef) {
+  assert(!Name.empty());
+}
+
+bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
+  assert(UseUnqualifiedMatch);
+  if (Node.getIdentifier()) {
+    // Simple name.
+    return Name == Node.getName();
+  }
+  if (Node.getDeclName()) {
+    // Name needs to be constructed.
+    llvm::SmallString<128> NodeName;
+    llvm::raw_svector_ostream OS(NodeName);
+    Node.printName(OS);
+    return Name == OS.str();
+  }
+  return false;
+}
+
+bool HasNameMatcher::matchesNodeFull(const NamedDecl &Node) const {
+  llvm::SmallString<128> NodeName = StringRef("::");
+  llvm::raw_svector_ostream OS(NodeName);
+  Node.printQualifiedName(OS);
+  const StringRef FullName = OS.str();
+  const StringRef Pattern = Name;
+
+  if (Pattern.startswith("::"))
+    return FullName == Pattern;
+
+  return FullName.endswith(Pattern) &&
+         FullName.drop_back(Pattern.size()).endswith("::");
+}
+
+bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
+  // FIXME: There is still room for improvement, but it would require copying a
+  // lot of the logic from NamedDecl::printQualifiedName(). The benchmarks do
+  // not show like that extra complexity is needed right now.
+  if (UseUnqualifiedMatch) {
+    assert(matchesNodeUnqualified(Node) == matchesNodeFull(Node));
+    return matchesNodeUnqualified(Node);
+  }
+  return matchesNodeFull(Node);
+}
+
+} // end namespace internal
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Diagnostics.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Diagnostics.cpp
new file mode 100644
index 0000000..f6d3449
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Diagnostics.cpp
@@ -0,0 +1,222 @@
+//===--- Diagnostics.cpp - Helper class for error diagnostics -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/Dynamic/Diagnostics.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+Diagnostics::ArgStream Diagnostics::pushContextFrame(ContextType Type,
+                                                     SourceRange Range) {
+  ContextStack.push_back(ContextFrame());
+  ContextFrame& data = ContextStack.back();
+  data.Type = Type;
+  data.Range = Range;
+  return ArgStream(&data.Args);
+}
+
+Diagnostics::Context::Context(ConstructMatcherEnum, Diagnostics *Error,
+                              StringRef MatcherName,
+                              const SourceRange &MatcherRange)
+    : Error(Error) {
+  Error->pushContextFrame(CT_MatcherConstruct, MatcherRange) << MatcherName;
+}
+
+Diagnostics::Context::Context(MatcherArgEnum, Diagnostics *Error,
+                              StringRef MatcherName,
+                              const SourceRange &MatcherRange,
+                              unsigned ArgNumber)
+    : Error(Error) {
+  Error->pushContextFrame(CT_MatcherArg, MatcherRange) << ArgNumber
+                                                       << MatcherName;
+}
+
+Diagnostics::Context::~Context() { Error->ContextStack.pop_back(); }
+
+Diagnostics::OverloadContext::OverloadContext(Diagnostics *Error)
+    : Error(Error), BeginIndex(Error->Errors.size()) {}
+
+Diagnostics::OverloadContext::~OverloadContext() {
+  // Merge all errors that happened while in this context.
+  if (BeginIndex < Error->Errors.size()) {
+    Diagnostics::ErrorContent &Dest = Error->Errors[BeginIndex];
+    for (size_t i = BeginIndex + 1, e = Error->Errors.size(); i < e; ++i) {
+      Dest.Messages.push_back(Error->Errors[i].Messages[0]);
+    }
+    Error->Errors.resize(BeginIndex + 1);
+  }
+}
+
+void Diagnostics::OverloadContext::revertErrors() {
+  // Revert the errors.
+  Error->Errors.resize(BeginIndex);
+}
+
+Diagnostics::ArgStream &Diagnostics::ArgStream::operator<<(const Twine &Arg) {
+  Out->push_back(Arg.str());
+  return *this;
+}
+
+Diagnostics::ArgStream Diagnostics::addError(const SourceRange &Range,
+                                             ErrorType Error) {
+  Errors.push_back(ErrorContent());
+  ErrorContent &Last = Errors.back();
+  Last.ContextStack = ContextStack;
+  Last.Messages.push_back(ErrorContent::Message());
+  Last.Messages.back().Range = Range;
+  Last.Messages.back().Type = Error;
+  return ArgStream(&Last.Messages.back().Args);
+}
+
+static StringRef contextTypeToFormatString(Diagnostics::ContextType Type) {
+  switch (Type) {
+    case Diagnostics::CT_MatcherConstruct:
+      return "Error building matcher $0.";
+    case Diagnostics::CT_MatcherArg:
+      return "Error parsing argument $0 for matcher $1.";
+  }
+  llvm_unreachable("Unknown ContextType value.");
+}
+
+static StringRef errorTypeToFormatString(Diagnostics::ErrorType Type) {
+  switch (Type) {
+  case Diagnostics::ET_RegistryMatcherNotFound:
+    return "Matcher not found: $0";
+  case Diagnostics::ET_RegistryWrongArgCount:
+    return "Incorrect argument count. (Expected = $0) != (Actual = $1)";
+  case Diagnostics::ET_RegistryWrongArgType:
+    return "Incorrect type for arg $0. (Expected = $1) != (Actual = $2)";
+  case Diagnostics::ET_RegistryNotBindable:
+    return "Matcher does not support binding.";
+  case Diagnostics::ET_RegistryAmbiguousOverload:
+    // TODO: Add type info about the overload error.
+    return "Ambiguous matcher overload.";
+  case Diagnostics::ET_RegistryValueNotFound:
+    return "Value not found: $0";
+
+  case Diagnostics::ET_ParserStringError:
+    return "Error parsing string token: <$0>";
+  case Diagnostics::ET_ParserNoOpenParen:
+    return "Error parsing matcher. Found token <$0> while looking for '('.";
+  case Diagnostics::ET_ParserNoCloseParen:
+    return "Error parsing matcher. Found end-of-code while looking for ')'.";
+  case Diagnostics::ET_ParserNoComma:
+    return "Error parsing matcher. Found token <$0> while looking for ','.";
+  case Diagnostics::ET_ParserNoCode:
+    return "End of code found while looking for token.";
+  case Diagnostics::ET_ParserNotAMatcher:
+    return "Input value is not a matcher expression.";
+  case Diagnostics::ET_ParserInvalidToken:
+    return "Invalid token <$0> found when looking for a value.";
+  case Diagnostics::ET_ParserMalformedBindExpr:
+    return "Malformed bind() expression.";
+  case Diagnostics::ET_ParserTrailingCode:
+    return "Expected end of code.";
+  case Diagnostics::ET_ParserUnsignedError:
+    return "Error parsing unsigned token: <$0>";
+  case Diagnostics::ET_ParserOverloadedType:
+    return "Input value has unresolved overloaded type: $0";
+
+  case Diagnostics::ET_None:
+    return "<N/A>";
+  }
+  llvm_unreachable("Unknown ErrorType value.");
+}
+
+static void formatErrorString(StringRef FormatString,
+                              ArrayRef<std::string> Args,
+                              llvm::raw_ostream &OS) {
+  while (!FormatString.empty()) {
+    std::pair<StringRef, StringRef> Pieces = FormatString.split("$");
+    OS << Pieces.first.str();
+    if (Pieces.second.empty()) break;
+
+    const char Next = Pieces.second.front();
+    FormatString = Pieces.second.drop_front();
+    if (Next >= '0' && Next <= '9') {
+      const unsigned Index = Next - '0';
+      if (Index < Args.size()) {
+        OS << Args[Index];
+      } else {
+        OS << "<Argument_Not_Provided>";
+      }
+    }
+  }
+}
+
+static void maybeAddLineAndColumn(const SourceRange &Range,
+                                  llvm::raw_ostream &OS) {
+  if (Range.Start.Line > 0 && Range.Start.Column > 0) {
+    OS << Range.Start.Line << ":" << Range.Start.Column << ": ";
+  }
+}
+
+static void printContextFrameToStream(const Diagnostics::ContextFrame &Frame,
+                                      llvm::raw_ostream &OS) {
+  maybeAddLineAndColumn(Frame.Range, OS);
+  formatErrorString(contextTypeToFormatString(Frame.Type), Frame.Args, OS);
+}
+
+static void
+printMessageToStream(const Diagnostics::ErrorContent::Message &Message,
+                     const Twine Prefix, llvm::raw_ostream &OS) {
+  maybeAddLineAndColumn(Message.Range, OS);
+  OS << Prefix;
+  formatErrorString(errorTypeToFormatString(Message.Type), Message.Args, OS);
+}
+
+static void printErrorContentToStream(const Diagnostics::ErrorContent &Content,
+                                      llvm::raw_ostream &OS) {
+  if (Content.Messages.size() == 1) {
+    printMessageToStream(Content.Messages[0], "", OS);
+  } else {
+    for (size_t i = 0, e = Content.Messages.size(); i != e; ++i) {
+      if (i != 0) OS << "\n";
+      printMessageToStream(Content.Messages[i],
+                           "Candidate " + Twine(i + 1) + ": ", OS);
+    }
+  }
+}
+
+void Diagnostics::printToStream(llvm::raw_ostream &OS) const {
+  for (size_t i = 0, e = Errors.size(); i != e; ++i) {
+    if (i != 0) OS << "\n";
+    printErrorContentToStream(Errors[i], OS);
+  }
+}
+
+std::string Diagnostics::toString() const {
+  std::string S;
+  llvm::raw_string_ostream OS(S);
+  printToStream(OS);
+  return OS.str();
+}
+
+void Diagnostics::printToStreamFull(llvm::raw_ostream &OS) const {
+  for (size_t i = 0, e = Errors.size(); i != e; ++i) {
+    if (i != 0) OS << "\n";
+    const ErrorContent &Error = Errors[i];
+    for (size_t i = 0, e = Error.ContextStack.size(); i != e; ++i) {
+      printContextFrameToStream(Error.ContextStack[i], OS);
+      OS << "\n";
+    }
+    printErrorContentToStream(Error, OS);
+  }
+}
+
+std::string Diagnostics::toStringFull() const {
+  std::string S;
+  llvm::raw_string_ostream OS(S);
+  printToStreamFull(OS);
+  return OS.str();
+}
+
+}  // namespace dynamic
+}  // namespace ast_matchers
+}  // namespace clang
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Marshallers.h b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Marshallers.h
new file mode 100644
index 0000000..36a6415
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Marshallers.h
@@ -0,0 +1,716 @@
+//===--- Marshallers.h - Generic matcher function marshallers -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Functions templates and classes to wrap matcher construct functions.
+///
+/// A collection of template function and classes that provide a generic
+/// marshalling layer on top of matcher construct functions.
+/// These are used by the registry to export all marshaller constructors with
+/// the same generic interface.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_ASTMATCHERS_DYNAMIC_MARSHALLERS_H
+#define LLVM_CLANG_LIB_ASTMATCHERS_DYNAMIC_MARSHALLERS_H
+
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/Dynamic/Diagnostics.h"
+#include "clang/ASTMatchers/Dynamic/VariantValue.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/STLExtras.h"
+#include <string>
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+namespace internal {
+
+
+/// \brief Helper template class to just from argument type to the right is/get
+///   functions in VariantValue.
+/// Used to verify and extract the matcher arguments below.
+template <class T> struct ArgTypeTraits;
+template <class T> struct ArgTypeTraits<const T &> : public ArgTypeTraits<T> {
+};
+
+template <> struct ArgTypeTraits<std::string> {
+  static bool is(const VariantValue &Value) { return Value.isString(); }
+  static const std::string &get(const VariantValue &Value) {
+    return Value.getString();
+  }
+  static ArgKind getKind() {
+    return ArgKind(ArgKind::AK_String);
+  }
+};
+
+template <>
+struct ArgTypeTraits<StringRef> : public ArgTypeTraits<std::string> {
+};
+
+template <class T> struct ArgTypeTraits<ast_matchers::internal::Matcher<T> > {
+  static bool is(const VariantValue &Value) {
+    return Value.isMatcher() && Value.getMatcher().hasTypedMatcher<T>();
+  }
+  static ast_matchers::internal::Matcher<T> get(const VariantValue &Value) {
+    return Value.getMatcher().getTypedMatcher<T>();
+  }
+  static ArgKind getKind() {
+    return ArgKind(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
+};
+
+template <> struct ArgTypeTraits<unsigned> {
+  static bool is(const VariantValue &Value) { return Value.isUnsigned(); }
+  static unsigned get(const VariantValue &Value) {
+    return Value.getUnsigned();
+  }
+  static ArgKind getKind() {
+    return ArgKind(ArgKind::AK_Unsigned);
+  }
+};
+
+template <> struct ArgTypeTraits<attr::Kind> {
+private:
+  static attr::Kind getAttrKind(llvm::StringRef AttrKind) {
+    return llvm::StringSwitch<attr::Kind>(AttrKind)
+#define ATTR(X) .Case("attr::" #X, attr:: X)
+#include "clang/Basic/AttrList.inc"
+        .Default(attr::Kind(-1));
+  }
+public:
+  static bool is(const VariantValue &Value) {
+    return Value.isString() &&
+        getAttrKind(Value.getString()) != attr::Kind(-1);
+  }
+  static attr::Kind get(const VariantValue &Value) {
+    return getAttrKind(Value.getString());
+  }
+  static ArgKind getKind() {
+    return ArgKind(ArgKind::AK_String);
+  }
+};
+
+/// \brief Matcher descriptor interface.
+///
+/// Provides a \c create() method that constructs the matcher from the provided
+/// arguments, and various other methods for type introspection.
+class MatcherDescriptor {
+public:
+  virtual ~MatcherDescriptor() {}
+  virtual VariantMatcher create(const SourceRange &NameRange,
+                                ArrayRef<ParserValue> Args,
+                                Diagnostics *Error) const = 0;
+
+  /// Returns whether the matcher is variadic. Variadic matchers can take any
+  /// number of arguments, but they must be of the same type.
+  virtual bool isVariadic() const = 0;
+
+  /// Returns the number of arguments accepted by the matcher if not variadic.
+  virtual unsigned getNumArgs() const = 0;
+
+  /// Given that the matcher is being converted to type \p ThisKind, append the
+  /// set of argument types accepted for argument \p ArgNo to \p ArgKinds.
+  // FIXME: We should provide the ability to constrain the output of this
+  // function based on the types of other matcher arguments.
+  virtual void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                           std::vector<ArgKind> &ArgKinds) const = 0;
+
+  /// Returns whether this matcher is convertible to the given type.  If it is
+  /// so convertible, store in *Specificity a value corresponding to the
+  /// "specificity" of the converted matcher to the given context, and in
+  /// *LeastDerivedKind the least derived matcher kind which would result in the
+  /// same matcher overload.  Zero specificity indicates that this conversion
+  /// would produce a trivial matcher that will either always or never match.
+  /// Such matchers are excluded from code completion results.
+  virtual bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity = nullptr,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind = nullptr) const = 0;
+
+  /// Returns whether the matcher will, given a matcher of any type T, yield a
+  /// matcher of type T.
+  virtual bool isPolymorphic() const { return false; }
+};
+
+inline bool isRetKindConvertibleTo(
+    ArrayRef<ast_type_traits::ASTNodeKind> RetKinds,
+    ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+    ast_type_traits::ASTNodeKind *LeastDerivedKind) {
+  for (const ast_type_traits::ASTNodeKind &NodeKind : RetKinds) {
+    if (ArgKind(NodeKind).isConvertibleTo(Kind, Specificity)) {
+      if (LeastDerivedKind)
+        *LeastDerivedKind = NodeKind;
+      return true;
+    }
+  }
+  return false;
+}
+
+/// \brief Simple callback implementation. Marshaller and function are provided.
+///
+/// This class wraps a function of arbitrary signature and a marshaller
+/// function into a MatcherDescriptor.
+/// The marshaller is in charge of taking the VariantValue arguments, checking
+/// their types, unpacking them and calling the underlying function.
+class FixedArgCountMatcherDescriptor : public MatcherDescriptor {
+public:
+  typedef VariantMatcher (*MarshallerType)(void (*Func)(),
+                                           StringRef MatcherName,
+                                           const SourceRange &NameRange,
+                                           ArrayRef<ParserValue> Args,
+                                           Diagnostics *Error);
+
+  /// \param Marshaller Function to unpack the arguments and call \c Func
+  /// \param Func Matcher construct function. This is the function that
+  ///   compile-time matcher expressions would use to create the matcher.
+  /// \param RetKinds The list of matcher types to which the matcher is
+  ///   convertible.
+  /// \param ArgKinds The types of the arguments this matcher takes.
+  FixedArgCountMatcherDescriptor(
+      MarshallerType Marshaller, void (*Func)(), StringRef MatcherName,
+      ArrayRef<ast_type_traits::ASTNodeKind> RetKinds,
+      ArrayRef<ArgKind> ArgKinds)
+      : Marshaller(Marshaller), Func(Func), MatcherName(MatcherName),
+        RetKinds(RetKinds.begin(), RetKinds.end()),
+        ArgKinds(ArgKinds.begin(), ArgKinds.end()) {}
+
+  VariantMatcher create(const SourceRange &NameRange,
+                        ArrayRef<ParserValue> Args,
+                        Diagnostics *Error) const override {
+    return Marshaller(Func, MatcherName, NameRange, Args, Error);
+  }
+
+  bool isVariadic() const override { return false; }
+  unsigned getNumArgs() const override { return ArgKinds.size(); }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const override {
+    Kinds.push_back(ArgKinds[ArgNo]);
+  }
+  bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    return isRetKindConvertibleTo(RetKinds, Kind, Specificity,
+                                  LeastDerivedKind);
+  }
+
+private:
+  const MarshallerType Marshaller;
+  void (* const Func)();
+  const std::string MatcherName;
+  const std::vector<ast_type_traits::ASTNodeKind> RetKinds;
+  const std::vector<ArgKind> ArgKinds;
+};
+
+/// \brief Helper methods to extract and merge all possible typed matchers
+/// out of the polymorphic object.
+template <class PolyMatcher>
+static void mergePolyMatchers(const PolyMatcher &Poly,
+                              std::vector<DynTypedMatcher> &Out,
+                              ast_matchers::internal::EmptyTypeList) {}
+
+template <class PolyMatcher, class TypeList>
+static void mergePolyMatchers(const PolyMatcher &Poly,
+                              std::vector<DynTypedMatcher> &Out, TypeList) {
+  Out.push_back(ast_matchers::internal::Matcher<typename TypeList::head>(Poly));
+  mergePolyMatchers(Poly, Out, typename TypeList::tail());
+}
+
+/// \brief Convert the return values of the functions into a VariantMatcher.
+///
+/// There are 2 cases right now: The return value is a Matcher<T> or is a
+/// polymorphic matcher. For the former, we just construct the VariantMatcher.
+/// For the latter, we instantiate all the possible Matcher<T> of the poly
+/// matcher.
+static VariantMatcher outvalueToVariantMatcher(const DynTypedMatcher &Matcher) {
+  return VariantMatcher::SingleMatcher(Matcher);
+}
+
+template <typename T>
+static VariantMatcher outvalueToVariantMatcher(const T &PolyMatcher,
+                                               typename T::ReturnTypes * =
+                                                   NULL) {
+  std::vector<DynTypedMatcher> Matchers;
+  mergePolyMatchers(PolyMatcher, Matchers, typename T::ReturnTypes());
+  VariantMatcher Out = VariantMatcher::PolymorphicMatcher(std::move(Matchers));
+  return Out;
+}
+
+template <typename T>
+inline void buildReturnTypeVectorFromTypeList(
+    std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+  RetTypes.push_back(
+      ast_type_traits::ASTNodeKind::getFromNodeKind<typename T::head>());
+  buildReturnTypeVectorFromTypeList<typename T::tail>(RetTypes);
+}
+
+template <>
+inline void
+buildReturnTypeVectorFromTypeList<ast_matchers::internal::EmptyTypeList>(
+    std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {}
+
+template <typename T>
+struct BuildReturnTypeVector {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    buildReturnTypeVectorFromTypeList<typename T::ReturnTypes>(RetTypes);
+  }
+};
+
+template <typename T>
+struct BuildReturnTypeVector<ast_matchers::internal::Matcher<T> > {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    RetTypes.push_back(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
+};
+
+template <typename T>
+struct BuildReturnTypeVector<ast_matchers::internal::BindableMatcher<T> > {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    RetTypes.push_back(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
+};
+
+/// \brief Variadic marshaller function.
+template <typename ResultT, typename ArgT,
+          ResultT (*Func)(ArrayRef<const ArgT *>)>
+VariantMatcher
+variadicMatcherDescriptor(StringRef MatcherName, const SourceRange &NameRange,
+                          ArrayRef<ParserValue> Args, Diagnostics *Error) {
+  ArgT **InnerArgs = new ArgT *[Args.size()]();
+
+  bool HasError = false;
+  for (size_t i = 0, e = Args.size(); i != e; ++i) {
+    typedef ArgTypeTraits<ArgT> ArgTraits;
+    const ParserValue &Arg = Args[i];
+    const VariantValue &Value = Arg.Value;
+    if (!ArgTraits::is(Value)) {
+      Error->addError(Arg.Range, Error->ET_RegistryWrongArgType)
+          << (i + 1) << ArgTraits::getKind().asString() << Value.getTypeAsString();
+      HasError = true;
+      break;
+    }
+    InnerArgs[i] = new ArgT(ArgTraits::get(Value));
+  }
+
+  VariantMatcher Out;
+  if (!HasError) {
+    Out = outvalueToVariantMatcher(Func(llvm::makeArrayRef(InnerArgs,
+                                                           Args.size())));
+  }
+
+  for (size_t i = 0, e = Args.size(); i != e; ++i) {
+    delete InnerArgs[i];
+  }
+  delete[] InnerArgs;
+  return Out;
+}
+
+/// \brief Matcher descriptor for variadic functions.
+///
+/// This class simply wraps a VariadicFunction with the right signature to export
+/// it as a MatcherDescriptor.
+/// This allows us to have one implementation of the interface for as many free
+/// functions as we want, reducing the number of symbols and size of the
+/// object file.
+class VariadicFuncMatcherDescriptor : public MatcherDescriptor {
+public:
+  typedef VariantMatcher (*RunFunc)(StringRef MatcherName,
+                                    const SourceRange &NameRange,
+                                    ArrayRef<ParserValue> Args,
+                                    Diagnostics *Error);
+
+  template <typename ResultT, typename ArgT,
+            ResultT (*F)(ArrayRef<const ArgT *>)>
+  VariadicFuncMatcherDescriptor(llvm::VariadicFunction<ResultT, ArgT, F> Func,
+                          StringRef MatcherName)
+      : Func(&variadicMatcherDescriptor<ResultT, ArgT, F>),
+        MatcherName(MatcherName.str()),
+        ArgsKind(ArgTypeTraits<ArgT>::getKind()) {
+    BuildReturnTypeVector<ResultT>::build(RetKinds);
+  }
+
+  VariantMatcher create(const SourceRange &NameRange,
+                        ArrayRef<ParserValue> Args,
+                        Diagnostics *Error) const override {
+    return Func(MatcherName, NameRange, Args, Error);
+  }
+
+  bool isVariadic() const override { return true; }
+  unsigned getNumArgs() const override { return 0; }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const override {
+    Kinds.push_back(ArgsKind);
+  }
+  bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    return isRetKindConvertibleTo(RetKinds, Kind, Specificity,
+                                  LeastDerivedKind);
+  }
+
+private:
+  const RunFunc Func;
+  const std::string MatcherName;
+  std::vector<ast_type_traits::ASTNodeKind> RetKinds;
+  const ArgKind ArgsKind;
+};
+
+/// \brief Return CK_Trivial when appropriate for VariadicDynCastAllOfMatchers.
+class DynCastAllOfMatcherDescriptor : public VariadicFuncMatcherDescriptor {
+public:
+  template <typename BaseT, typename DerivedT>
+  DynCastAllOfMatcherDescriptor(
+      ast_matchers::internal::VariadicDynCastAllOfMatcher<BaseT, DerivedT> Func,
+      StringRef MatcherName)
+      : VariadicFuncMatcherDescriptor(Func, MatcherName),
+        DerivedKind(ast_type_traits::ASTNodeKind::getFromNodeKind<DerivedT>()) {
+  }
+
+  bool
+  isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    // If Kind is not a base of DerivedKind, either DerivedKind is a base of
+    // Kind (in which case the match will always succeed) or Kind and
+    // DerivedKind are unrelated (in which case it will always fail), so set
+    // Specificity to 0.
+    if (VariadicFuncMatcherDescriptor::isConvertibleTo(Kind, Specificity,
+                                                 LeastDerivedKind)) {
+      if (Kind.isSame(DerivedKind) || !Kind.isBaseOf(DerivedKind)) {
+        if (Specificity)
+          *Specificity = 0;
+      }
+      return true;
+    } else {
+      return false;
+    }
+  }
+
+private:
+  const ast_type_traits::ASTNodeKind DerivedKind;
+};
+
+/// \brief Helper macros to check the arguments on all marshaller functions.
+#define CHECK_ARG_COUNT(count)                                                 \
+  if (Args.size() != count) {                                                  \
+    Error->addError(NameRange, Error->ET_RegistryWrongArgCount)                \
+        << count << Args.size();                                               \
+    return VariantMatcher();                                                   \
+  }
+
+#define CHECK_ARG_TYPE(index, type)                                            \
+  if (!ArgTypeTraits<type>::is(Args[index].Value)) {                           \
+    Error->addError(Args[index].Range, Error->ET_RegistryWrongArgType)         \
+        << (index + 1) << ArgTypeTraits<type>::getKind().asString()            \
+        << Args[index].Value.getTypeAsString();                                \
+    return VariantMatcher();                                                   \
+  }
+
+
+/// \brief 0-arg marshaller function.
+template <typename ReturnType>
+static VariantMatcher matcherMarshall0(void (*Func)(), StringRef MatcherName,
+                                       const SourceRange &NameRange,
+                                       ArrayRef<ParserValue> Args,
+                                       Diagnostics *Error) {
+  typedef ReturnType (*FuncType)();
+  CHECK_ARG_COUNT(0);
+  return outvalueToVariantMatcher(reinterpret_cast<FuncType>(Func)());
+}
+
+/// \brief 1-arg marshaller function.
+template <typename ReturnType, typename ArgType1>
+static VariantMatcher matcherMarshall1(void (*Func)(), StringRef MatcherName,
+                                       const SourceRange &NameRange,
+                                       ArrayRef<ParserValue> Args,
+                                       Diagnostics *Error) {
+  typedef ReturnType (*FuncType)(ArgType1);
+  CHECK_ARG_COUNT(1);
+  CHECK_ARG_TYPE(0, ArgType1);
+  return outvalueToVariantMatcher(reinterpret_cast<FuncType>(Func)(
+      ArgTypeTraits<ArgType1>::get(Args[0].Value)));
+}
+
+/// \brief 2-arg marshaller function.
+template <typename ReturnType, typename ArgType1, typename ArgType2>
+static VariantMatcher matcherMarshall2(void (*Func)(), StringRef MatcherName,
+                                       const SourceRange &NameRange,
+                                       ArrayRef<ParserValue> Args,
+                                       Diagnostics *Error) {
+  typedef ReturnType (*FuncType)(ArgType1, ArgType2);
+  CHECK_ARG_COUNT(2);
+  CHECK_ARG_TYPE(0, ArgType1);
+  CHECK_ARG_TYPE(1, ArgType2);
+  return outvalueToVariantMatcher(reinterpret_cast<FuncType>(Func)(
+      ArgTypeTraits<ArgType1>::get(Args[0].Value),
+      ArgTypeTraits<ArgType2>::get(Args[1].Value)));
+}
+
+#undef CHECK_ARG_COUNT
+#undef CHECK_ARG_TYPE
+
+/// \brief Helper class used to collect all the possible overloads of an
+///   argument adaptative matcher function.
+template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
+          typename FromTypes, typename ToTypes>
+class AdaptativeOverloadCollector {
+public:
+  AdaptativeOverloadCollector(StringRef Name,
+                              std::vector<MatcherDescriptor *> &Out)
+      : Name(Name), Out(Out) {
+    collect(FromTypes());
+  }
+
+private:
+  typedef ast_matchers::internal::ArgumentAdaptingMatcherFunc<
+      ArgumentAdapterT, FromTypes, ToTypes> AdaptativeFunc;
+
+  /// \brief End case for the recursion
+  static void collect(ast_matchers::internal::EmptyTypeList) {}
+
+  /// \brief Recursive case. Get the overload for the head of the list, and
+  ///   recurse to the tail.
+  template <typename FromTypeList>
+  inline void collect(FromTypeList);
+
+  StringRef Name;
+  std::vector<MatcherDescriptor *> &Out;
+};
+
+/// \brief MatcherDescriptor that wraps multiple "overloads" of the same
+///   matcher.
+///
+/// It will try every overload and generate appropriate errors for when none or
+/// more than one overloads match the arguments.
+class OverloadedMatcherDescriptor : public MatcherDescriptor {
+public:
+  OverloadedMatcherDescriptor(ArrayRef<MatcherDescriptor *> Callbacks)
+      : Overloads(Callbacks.begin(), Callbacks.end()) {}
+
+  ~OverloadedMatcherDescriptor() override {}
+
+  VariantMatcher create(const SourceRange &NameRange,
+                        ArrayRef<ParserValue> Args,
+                        Diagnostics *Error) const override {
+    std::vector<VariantMatcher> Constructed;
+    Diagnostics::OverloadContext Ctx(Error);
+    for (const auto &O : Overloads) {
+      VariantMatcher SubMatcher = O->create(NameRange, Args, Error);
+      if (!SubMatcher.isNull()) {
+        Constructed.push_back(SubMatcher);
+      }
+    }
+
+    if (Constructed.empty()) return VariantMatcher(); // No overload matched.
+    // We ignore the errors if any matcher succeeded.
+    Ctx.revertErrors();
+    if (Constructed.size() > 1) {
+      // More than one constructed. It is ambiguous.
+      Error->addError(NameRange, Error->ET_RegistryAmbiguousOverload);
+      return VariantMatcher();
+    }
+    return Constructed[0];
+  }
+
+  bool isVariadic() const override {
+    bool Overload0Variadic = Overloads[0]->isVariadic();
+#ifndef NDEBUG
+    for (const auto &O : Overloads) {
+      assert(Overload0Variadic == O->isVariadic());
+    }
+#endif
+    return Overload0Variadic;
+  }
+
+  unsigned getNumArgs() const override {
+    unsigned Overload0NumArgs = Overloads[0]->getNumArgs();
+#ifndef NDEBUG
+    for (const auto &O : Overloads) {
+      assert(Overload0NumArgs == O->getNumArgs());
+    }
+#endif
+    return Overload0NumArgs;
+  }
+
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const override {
+    for (const auto &O : Overloads) {
+      if (O->isConvertibleTo(ThisKind))
+        O->getArgKinds(ThisKind, ArgNo, Kinds);
+    }
+  }
+
+  bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    for (const auto &O : Overloads) {
+      if (O->isConvertibleTo(Kind, Specificity, LeastDerivedKind))
+        return true;
+    }
+    return false;
+  }
+
+private:
+  std::vector<std::unique_ptr<MatcherDescriptor>> Overloads;
+};
+
+/// \brief Variadic operator marshaller function.
+class VariadicOperatorMatcherDescriptor : public MatcherDescriptor {
+public:
+  typedef DynTypedMatcher::VariadicOperator VarOp;
+  VariadicOperatorMatcherDescriptor(unsigned MinCount, unsigned MaxCount,
+                                    VarOp Op, StringRef MatcherName)
+      : MinCount(MinCount), MaxCount(MaxCount), Op(Op),
+        MatcherName(MatcherName) {}
+
+  VariantMatcher create(const SourceRange &NameRange,
+                        ArrayRef<ParserValue> Args,
+                        Diagnostics *Error) const override {
+    if (Args.size() < MinCount || MaxCount < Args.size()) {
+      const std::string MaxStr =
+          (MaxCount == UINT_MAX ? "" : Twine(MaxCount)).str();
+      Error->addError(NameRange, Error->ET_RegistryWrongArgCount)
+          << ("(" + Twine(MinCount) + ", " + MaxStr + ")") << Args.size();
+      return VariantMatcher();
+    }
+
+    std::vector<VariantMatcher> InnerArgs;
+    for (size_t i = 0, e = Args.size(); i != e; ++i) {
+      const ParserValue &Arg = Args[i];
+      const VariantValue &Value = Arg.Value;
+      if (!Value.isMatcher()) {
+        Error->addError(Arg.Range, Error->ET_RegistryWrongArgType)
+            << (i + 1) << "Matcher<>" << Value.getTypeAsString();
+        return VariantMatcher();
+      }
+      InnerArgs.push_back(Value.getMatcher());
+    }
+    return VariantMatcher::VariadicOperatorMatcher(Op, std::move(InnerArgs));
+  }
+
+  bool isVariadic() const override { return true; }
+  unsigned getNumArgs() const override { return 0; }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const override {
+    Kinds.push_back(ThisKind);
+  }
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    if (Specificity)
+      *Specificity = 1;
+    if (LeastDerivedKind)
+      *LeastDerivedKind = Kind;
+    return true;
+  }
+  bool isPolymorphic() const override { return true; }
+
+private:
+  const unsigned MinCount;
+  const unsigned MaxCount;
+  const VarOp Op;
+  const StringRef MatcherName;
+};
+
+/// Helper functions to select the appropriate marshaller functions.
+/// They detect the number of arguments, arguments types and return type.
+
+/// \brief 0-arg overload
+template <typename ReturnType>
+MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(),
+                                     StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  return new FixedArgCountMatcherDescriptor(
+      matcherMarshall0<ReturnType>, reinterpret_cast<void (*)()>(Func),
+      MatcherName, RetTypes, None);
+}
+
+/// \brief 1-arg overload
+template <typename ReturnType, typename ArgType1>
+MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1),
+                                     StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  ArgKind AK = ArgTypeTraits<ArgType1>::getKind();
+  return new FixedArgCountMatcherDescriptor(
+      matcherMarshall1<ReturnType, ArgType1>,
+      reinterpret_cast<void (*)()>(Func), MatcherName, RetTypes, AK);
+}
+
+/// \brief 2-arg overload
+template <typename ReturnType, typename ArgType1, typename ArgType2>
+MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1, ArgType2),
+                                     StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  ArgKind AKs[] = { ArgTypeTraits<ArgType1>::getKind(),
+                    ArgTypeTraits<ArgType2>::getKind() };
+  return new FixedArgCountMatcherDescriptor(
+      matcherMarshall2<ReturnType, ArgType1, ArgType2>,
+      reinterpret_cast<void (*)()>(Func), MatcherName, RetTypes, AKs);
+}
+
+/// \brief Variadic overload.
+template <typename ResultT, typename ArgT,
+          ResultT (*Func)(ArrayRef<const ArgT *>)>
+MatcherDescriptor *
+makeMatcherAutoMarshall(llvm::VariadicFunction<ResultT, ArgT, Func> VarFunc,
+                        StringRef MatcherName) {
+  return new VariadicFuncMatcherDescriptor(VarFunc, MatcherName);
+}
+
+/// \brief Overload for VariadicDynCastAllOfMatchers.
+///
+/// Not strictly necessary, but DynCastAllOfMatcherDescriptor gives us better
+/// completion results for that type of matcher.
+template <typename BaseT, typename DerivedT>
+MatcherDescriptor *
+makeMatcherAutoMarshall(ast_matchers::internal::VariadicDynCastAllOfMatcher<
+                            BaseT, DerivedT> VarFunc,
+                        StringRef MatcherName) {
+  return new DynCastAllOfMatcherDescriptor(VarFunc, MatcherName);
+}
+
+/// \brief Argument adaptative overload.
+template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
+          typename FromTypes, typename ToTypes>
+MatcherDescriptor *
+makeMatcherAutoMarshall(ast_matchers::internal::ArgumentAdaptingMatcherFunc<
+                            ArgumentAdapterT, FromTypes, ToTypes>,
+                        StringRef MatcherName) {
+  std::vector<MatcherDescriptor *> Overloads;
+  AdaptativeOverloadCollector<ArgumentAdapterT, FromTypes, ToTypes>(MatcherName,
+                                                                    Overloads);
+  return new OverloadedMatcherDescriptor(Overloads);
+}
+
+template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
+          typename FromTypes, typename ToTypes>
+template <typename FromTypeList>
+inline void AdaptativeOverloadCollector<ArgumentAdapterT, FromTypes,
+                                        ToTypes>::collect(FromTypeList) {
+  Out.push_back(makeMatcherAutoMarshall(
+      &AdaptativeFunc::template create<typename FromTypeList::head>, Name));
+  collect(typename FromTypeList::tail());
+}
+
+/// \brief Variadic operator overload.
+template <unsigned MinCount, unsigned MaxCount>
+MatcherDescriptor *
+makeMatcherAutoMarshall(ast_matchers::internal::VariadicOperatorMatcherFunc<
+                            MinCount, MaxCount> Func,
+                        StringRef MatcherName) {
+  return new VariadicOperatorMatcherDescriptor(MinCount, MaxCount, Func.Op,
+                                               MatcherName);
+}
+
+}  // namespace internal
+}  // namespace dynamic
+}  // namespace ast_matchers
+}  // namespace clang
+
+#endif  // LLVM_CLANG_AST_MATCHERS_DYNAMIC_MARSHALLERS_H
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Parser.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Parser.cpp
new file mode 100644
index 0000000..9930c53
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Parser.cpp
@@ -0,0 +1,613 @@
+//===--- Parser.cpp - Matcher expression parser -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Recursive parser implementation for the matcher expression grammar.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/Dynamic/Parser.h"
+#include "clang/ASTMatchers/Dynamic/Registry.h"
+#include "clang/Basic/CharInfo.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+
+/// \brief Simple structure to hold information for one token from the parser.
+struct Parser::TokenInfo {
+  /// \brief Different possible tokens.
+  enum TokenKind {
+    TK_Eof,
+    TK_OpenParen,
+    TK_CloseParen,
+    TK_Comma,
+    TK_Period,
+    TK_Literal,
+    TK_Ident,
+    TK_InvalidChar,
+    TK_Error,
+    TK_CodeCompletion
+  };
+
+  /// \brief Some known identifiers.
+  static const char* const ID_Bind;
+
+  TokenInfo() : Text(), Kind(TK_Eof), Range(), Value() {}
+
+  StringRef Text;
+  TokenKind Kind;
+  SourceRange Range;
+  VariantValue Value;
+};
+
+const char* const Parser::TokenInfo::ID_Bind = "bind";
+
+/// \brief Simple tokenizer for the parser.
+class Parser::CodeTokenizer {
+public:
+  explicit CodeTokenizer(StringRef MatcherCode, Diagnostics *Error)
+      : Code(MatcherCode), StartOfLine(MatcherCode), Line(1), Error(Error),
+        CodeCompletionLocation(nullptr) {
+    NextToken = getNextToken();
+  }
+
+  CodeTokenizer(StringRef MatcherCode, Diagnostics *Error,
+                unsigned CodeCompletionOffset)
+      : Code(MatcherCode), StartOfLine(MatcherCode), Line(1), Error(Error),
+        CodeCompletionLocation(MatcherCode.data() + CodeCompletionOffset) {
+    NextToken = getNextToken();
+  }
+
+  /// \brief Returns but doesn't consume the next token.
+  const TokenInfo &peekNextToken() const { return NextToken; }
+
+  /// \brief Consumes and returns the next token.
+  TokenInfo consumeNextToken() {
+    TokenInfo ThisToken = NextToken;
+    NextToken = getNextToken();
+    return ThisToken;
+  }
+
+  TokenInfo::TokenKind nextTokenKind() const { return NextToken.Kind; }
+
+private:
+  TokenInfo getNextToken() {
+    consumeWhitespace();
+    TokenInfo Result;
+    Result.Range.Start = currentLocation();
+
+    if (CodeCompletionLocation && CodeCompletionLocation <= Code.data()) {
+      Result.Kind = TokenInfo::TK_CodeCompletion;
+      Result.Text = StringRef(CodeCompletionLocation, 0);
+      CodeCompletionLocation = nullptr;
+      return Result;
+    }
+
+    if (Code.empty()) {
+      Result.Kind = TokenInfo::TK_Eof;
+      Result.Text = "";
+      return Result;
+    }
+
+    switch (Code[0]) {
+    case ',':
+      Result.Kind = TokenInfo::TK_Comma;
+      Result.Text = Code.substr(0, 1);
+      Code = Code.drop_front();
+      break;
+    case '.':
+      Result.Kind = TokenInfo::TK_Period;
+      Result.Text = Code.substr(0, 1);
+      Code = Code.drop_front();
+      break;
+    case '(':
+      Result.Kind = TokenInfo::TK_OpenParen;
+      Result.Text = Code.substr(0, 1);
+      Code = Code.drop_front();
+      break;
+    case ')':
+      Result.Kind = TokenInfo::TK_CloseParen;
+      Result.Text = Code.substr(0, 1);
+      Code = Code.drop_front();
+      break;
+
+    case '"':
+    case '\'':
+      // Parse a string literal.
+      consumeStringLiteral(&Result);
+      break;
+
+    case '0': case '1': case '2': case '3': case '4':
+    case '5': case '6': case '7': case '8': case '9':
+      // Parse an unsigned literal.
+      consumeUnsignedLiteral(&Result);
+      break;
+
+    default:
+      if (isAlphanumeric(Code[0])) {
+        // Parse an identifier
+        size_t TokenLength = 1;
+        while (1) {
+          // A code completion location in/immediately after an identifier will
+          // cause the portion of the identifier before the code completion
+          // location to become a code completion token.
+          if (CodeCompletionLocation == Code.data() + TokenLength) {
+            CodeCompletionLocation = nullptr;
+            Result.Kind = TokenInfo::TK_CodeCompletion;
+            Result.Text = Code.substr(0, TokenLength);
+            Code = Code.drop_front(TokenLength);
+            return Result;
+          }
+          if (TokenLength == Code.size() || !isAlphanumeric(Code[TokenLength]))
+            break;
+          ++TokenLength;
+        }
+        Result.Kind = TokenInfo::TK_Ident;
+        Result.Text = Code.substr(0, TokenLength);
+        Code = Code.drop_front(TokenLength);
+      } else {
+        Result.Kind = TokenInfo::TK_InvalidChar;
+        Result.Text = Code.substr(0, 1);
+        Code = Code.drop_front(1);
+      }
+      break;
+    }
+
+    Result.Range.End = currentLocation();
+    return Result;
+  }
+
+  /// \brief Consume an unsigned literal.
+  void consumeUnsignedLiteral(TokenInfo *Result) {
+    unsigned Length = 1;
+    if (Code.size() > 1) {
+      // Consume the 'x' or 'b' radix modifier, if present.
+      switch (toLowercase(Code[1])) {
+      case 'x': case 'b': Length = 2;
+      }
+    }
+    while (Length < Code.size() && isHexDigit(Code[Length]))
+      ++Length;
+
+    Result->Text = Code.substr(0, Length);
+    Code = Code.drop_front(Length);
+
+    unsigned Value;
+    if (!Result->Text.getAsInteger(0, Value)) {
+      Result->Kind = TokenInfo::TK_Literal;
+      Result->Value = Value;
+    } else {
+      SourceRange Range;
+      Range.Start = Result->Range.Start;
+      Range.End = currentLocation();
+      Error->addError(Range, Error->ET_ParserUnsignedError) << Result->Text;
+      Result->Kind = TokenInfo::TK_Error;
+    }
+  }
+
+  /// \brief Consume a string literal.
+  ///
+  /// \c Code must be positioned at the start of the literal (the opening
+  /// quote). Consumed until it finds the same closing quote character.
+  void consumeStringLiteral(TokenInfo *Result) {
+    bool InEscape = false;
+    const char Marker = Code[0];
+    for (size_t Length = 1, Size = Code.size(); Length != Size; ++Length) {
+      if (InEscape) {
+        InEscape = false;
+        continue;
+      }
+      if (Code[Length] == '\\') {
+        InEscape = true;
+        continue;
+      }
+      if (Code[Length] == Marker) {
+        Result->Kind = TokenInfo::TK_Literal;
+        Result->Text = Code.substr(0, Length + 1);
+        Result->Value = Code.substr(1, Length - 1).str();
+        Code = Code.drop_front(Length + 1);
+        return;
+      }
+    }
+
+    StringRef ErrorText = Code;
+    Code = Code.drop_front(Code.size());
+    SourceRange Range;
+    Range.Start = Result->Range.Start;
+    Range.End = currentLocation();
+    Error->addError(Range, Error->ET_ParserStringError) << ErrorText;
+    Result->Kind = TokenInfo::TK_Error;
+  }
+
+  /// \brief Consume all leading whitespace from \c Code.
+  void consumeWhitespace() {
+    while (!Code.empty() && isWhitespace(Code[0])) {
+      if (Code[0] == '\n') {
+        ++Line;
+        StartOfLine = Code.drop_front();
+      }
+      Code = Code.drop_front();
+    }
+  }
+
+  SourceLocation currentLocation() {
+    SourceLocation Location;
+    Location.Line = Line;
+    Location.Column = Code.data() - StartOfLine.data() + 1;
+    return Location;
+  }
+
+  StringRef Code;
+  StringRef StartOfLine;
+  unsigned Line;
+  Diagnostics *Error;
+  TokenInfo NextToken;
+  const char *CodeCompletionLocation;
+};
+
+Parser::Sema::~Sema() {}
+
+std::vector<ArgKind> Parser::Sema::getAcceptedCompletionTypes(
+    llvm::ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
+  return std::vector<ArgKind>();
+}
+
+std::vector<MatcherCompletion>
+Parser::Sema::getMatcherCompletions(llvm::ArrayRef<ArgKind> AcceptedTypes) {
+  return std::vector<MatcherCompletion>();
+}
+
+struct Parser::ScopedContextEntry {
+  Parser *P;
+
+  ScopedContextEntry(Parser *P, MatcherCtor C) : P(P) {
+    P->ContextStack.push_back(std::make_pair(C, 0u));
+  }
+
+  ~ScopedContextEntry() {
+    P->ContextStack.pop_back();
+  }
+
+  void nextArg() {
+    ++P->ContextStack.back().second;
+  }
+};
+
+/// \brief Parse expressions that start with an identifier.
+///
+/// This function can parse named values and matchers.
+/// In case of failure it will try to determine the user's intent to give
+/// an appropriate error message.
+bool Parser::parseIdentifierPrefixImpl(VariantValue *Value) {
+  const TokenInfo NameToken = Tokenizer->consumeNextToken();
+
+  if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
+    // Parse as a named value.
+    if (const VariantValue NamedValue =
+            NamedValues ? NamedValues->lookup(NameToken.Text)
+                        : VariantValue()) {
+      *Value = NamedValue;
+      return true;
+    }
+    // If the syntax is correct and the name is not a matcher either, report
+    // unknown named value.
+    if ((Tokenizer->nextTokenKind() == TokenInfo::TK_Comma ||
+         Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen ||
+         Tokenizer->nextTokenKind() == TokenInfo::TK_Eof) &&
+        !S->lookupMatcherCtor(NameToken.Text)) {
+      Error->addError(NameToken.Range, Error->ET_RegistryValueNotFound)
+          << NameToken.Text;
+      return false;
+    }
+    // Otherwise, fallback to the matcher parser.
+  }
+
+  // Parse as a matcher expression.
+  return parseMatcherExpressionImpl(NameToken, Value);
+}
+
+/// \brief Parse and validate a matcher expression.
+/// \return \c true on success, in which case \c Value has the matcher parsed.
+///   If the input is malformed, or some argument has an error, it
+///   returns \c false.
+bool Parser::parseMatcherExpressionImpl(const TokenInfo &NameToken,
+                                        VariantValue *Value) {
+  assert(NameToken.Kind == TokenInfo::TK_Ident);
+  const TokenInfo OpenToken = Tokenizer->consumeNextToken();
+  if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
+    Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
+        << OpenToken.Text;
+    return false;
+  }
+
+  llvm::Optional<MatcherCtor> Ctor = S->lookupMatcherCtor(NameToken.Text);
+
+  if (!Ctor) {
+    Error->addError(NameToken.Range, Error->ET_RegistryMatcherNotFound)
+        << NameToken.Text;
+    // Do not return here. We need to continue to give completion suggestions.
+  }
+
+  std::vector<ParserValue> Args;
+  TokenInfo EndToken;
+
+  {
+    ScopedContextEntry SCE(this, Ctor ? *Ctor : nullptr);
+
+    while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
+      if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
+        // End of args.
+        EndToken = Tokenizer->consumeNextToken();
+        break;
+      }
+      if (Args.size() > 0) {
+        // We must find a , token to continue.
+        const TokenInfo CommaToken = Tokenizer->consumeNextToken();
+        if (CommaToken.Kind != TokenInfo::TK_Comma) {
+          Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
+              << CommaToken.Text;
+          return false;
+        }
+      }
+
+      Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
+                               NameToken.Text, NameToken.Range,
+                               Args.size() + 1);
+      ParserValue ArgValue;
+      ArgValue.Text = Tokenizer->peekNextToken().Text;
+      ArgValue.Range = Tokenizer->peekNextToken().Range;
+      if (!parseExpressionImpl(&ArgValue.Value)) {
+        return false;
+      }
+
+      Args.push_back(ArgValue);
+      SCE.nextArg();
+    }
+  }
+
+  if (EndToken.Kind == TokenInfo::TK_Eof) {
+    Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
+    return false;
+  }
+
+  std::string BindID;
+  if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
+    // Parse .bind("foo")
+    Tokenizer->consumeNextToken();  // consume the period.
+    const TokenInfo BindToken = Tokenizer->consumeNextToken();
+    if (BindToken.Kind == TokenInfo::TK_CodeCompletion) {
+      addCompletion(BindToken, MatcherCompletion("bind(\"", "bind", 1));
+      return false;
+    }
+
+    const TokenInfo OpenToken = Tokenizer->consumeNextToken();
+    const TokenInfo IDToken = Tokenizer->consumeNextToken();
+    const TokenInfo CloseToken = Tokenizer->consumeNextToken();
+
+    // TODO: We could use different error codes for each/some to be more
+    //       explicit about the syntax error.
+    if (BindToken.Kind != TokenInfo::TK_Ident ||
+        BindToken.Text != TokenInfo::ID_Bind) {
+      Error->addError(BindToken.Range, Error->ET_ParserMalformedBindExpr);
+      return false;
+    }
+    if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
+      Error->addError(OpenToken.Range, Error->ET_ParserMalformedBindExpr);
+      return false;
+    }
+    if (IDToken.Kind != TokenInfo::TK_Literal || !IDToken.Value.isString()) {
+      Error->addError(IDToken.Range, Error->ET_ParserMalformedBindExpr);
+      return false;
+    }
+    if (CloseToken.Kind != TokenInfo::TK_CloseParen) {
+      Error->addError(CloseToken.Range, Error->ET_ParserMalformedBindExpr);
+      return false;
+    }
+    BindID = IDToken.Value.getString();
+  }
+
+  if (!Ctor)
+    return false;
+
+  // Merge the start and end infos.
+  Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
+                           NameToken.Text, NameToken.Range);
+  SourceRange MatcherRange = NameToken.Range;
+  MatcherRange.End = EndToken.Range.End;
+  VariantMatcher Result = S->actOnMatcherExpression(
+      *Ctor, MatcherRange, BindID, Args, Error);
+  if (Result.isNull()) return false;
+
+  *Value = Result;
+  return true;
+}
+
+// If the prefix of this completion matches the completion token, add it to
+// Completions minus the prefix.
+void Parser::addCompletion(const TokenInfo &CompToken,
+                           const MatcherCompletion& Completion) {
+  if (StringRef(Completion.TypedText).startswith(CompToken.Text) &&
+      Completion.Specificity > 0) {
+    Completions.emplace_back(Completion.TypedText.substr(CompToken.Text.size()),
+                             Completion.MatcherDecl, Completion.Specificity);
+  }
+}
+
+std::vector<MatcherCompletion> Parser::getNamedValueCompletions(
+    ArrayRef<ArgKind> AcceptedTypes) {
+  if (!NamedValues) return std::vector<MatcherCompletion>();
+  std::vector<MatcherCompletion> Result;
+  for (const auto &Entry : *NamedValues) {
+    unsigned Specificity;
+    if (Entry.getValue().isConvertibleTo(AcceptedTypes, &Specificity)) {
+      std::string Decl =
+          (Entry.getValue().getTypeAsString() + " " + Entry.getKey()).str();
+      Result.emplace_back(Entry.getKey(), Decl, Specificity);
+    }
+  }
+  return Result;
+}
+
+void Parser::addExpressionCompletions() {
+  const TokenInfo CompToken = Tokenizer->consumeNextToken();
+  assert(CompToken.Kind == TokenInfo::TK_CodeCompletion);
+
+  // We cannot complete code if there is an invalid element on the context
+  // stack.
+  for (ContextStackTy::iterator I = ContextStack.begin(),
+                                E = ContextStack.end();
+       I != E; ++I) {
+    if (!I->first)
+      return;
+  }
+
+  auto AcceptedTypes = S->getAcceptedCompletionTypes(ContextStack);
+  for (const auto &Completion : S->getMatcherCompletions(AcceptedTypes)) {
+    addCompletion(CompToken, Completion);
+  }
+
+  for (const auto &Completion : getNamedValueCompletions(AcceptedTypes)) {
+    addCompletion(CompToken, Completion);
+  }
+}
+
+/// \brief Parse an <Expresssion>
+bool Parser::parseExpressionImpl(VariantValue *Value) {
+  switch (Tokenizer->nextTokenKind()) {
+  case TokenInfo::TK_Literal:
+    *Value = Tokenizer->consumeNextToken().Value;
+    return true;
+
+  case TokenInfo::TK_Ident:
+    return parseIdentifierPrefixImpl(Value);
+
+  case TokenInfo::TK_CodeCompletion:
+    addExpressionCompletions();
+    return false;
+
+  case TokenInfo::TK_Eof:
+    Error->addError(Tokenizer->consumeNextToken().Range,
+                    Error->ET_ParserNoCode);
+    return false;
+
+  case TokenInfo::TK_Error:
+    // This error was already reported by the tokenizer.
+    return false;
+
+  case TokenInfo::TK_OpenParen:
+  case TokenInfo::TK_CloseParen:
+  case TokenInfo::TK_Comma:
+  case TokenInfo::TK_Period:
+  case TokenInfo::TK_InvalidChar:
+    const TokenInfo Token = Tokenizer->consumeNextToken();
+    Error->addError(Token.Range, Error->ET_ParserInvalidToken) << Token.Text;
+    return false;
+  }
+
+  llvm_unreachable("Unknown token kind.");
+}
+
+static llvm::ManagedStatic<Parser::RegistrySema> DefaultRegistrySema;
+
+Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
+               const NamedValueMap *NamedValues, Diagnostics *Error)
+    : Tokenizer(Tokenizer), S(S ? S : &*DefaultRegistrySema),
+      NamedValues(NamedValues), Error(Error) {}
+
+Parser::RegistrySema::~RegistrySema() {}
+
+llvm::Optional<MatcherCtor>
+Parser::RegistrySema::lookupMatcherCtor(StringRef MatcherName) {
+  return Registry::lookupMatcherCtor(MatcherName);
+}
+
+VariantMatcher Parser::RegistrySema::actOnMatcherExpression(
+    MatcherCtor Ctor, const SourceRange &NameRange, StringRef BindID,
+    ArrayRef<ParserValue> Args, Diagnostics *Error) {
+  if (BindID.empty()) {
+    return Registry::constructMatcher(Ctor, NameRange, Args, Error);
+  } else {
+    return Registry::constructBoundMatcher(Ctor, NameRange, BindID, Args,
+                                           Error);
+  }
+}
+
+std::vector<ArgKind> Parser::RegistrySema::getAcceptedCompletionTypes(
+    ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
+  return Registry::getAcceptedCompletionTypes(Context);
+}
+
+std::vector<MatcherCompletion> Parser::RegistrySema::getMatcherCompletions(
+    ArrayRef<ArgKind> AcceptedTypes) {
+  return Registry::getMatcherCompletions(AcceptedTypes);
+}
+
+bool Parser::parseExpression(StringRef Code, Sema *S,
+                             const NamedValueMap *NamedValues,
+                             VariantValue *Value, Diagnostics *Error) {
+  CodeTokenizer Tokenizer(Code, Error);
+  if (!Parser(&Tokenizer, S, NamedValues, Error).parseExpressionImpl(Value))
+    return false;
+  if (Tokenizer.peekNextToken().Kind != TokenInfo::TK_Eof) {
+    Error->addError(Tokenizer.peekNextToken().Range,
+                    Error->ET_ParserTrailingCode);
+    return false;
+  }
+  return true;
+}
+
+std::vector<MatcherCompletion>
+Parser::completeExpression(StringRef Code, unsigned CompletionOffset, Sema *S,
+                           const NamedValueMap *NamedValues) {
+  Diagnostics Error;
+  CodeTokenizer Tokenizer(Code, &Error, CompletionOffset);
+  Parser P(&Tokenizer, S, NamedValues, &Error);
+  VariantValue Dummy;
+  P.parseExpressionImpl(&Dummy);
+
+  // Sort by specificity, then by name.
+  std::sort(P.Completions.begin(), P.Completions.end(),
+            [](const MatcherCompletion &A, const MatcherCompletion &B) {
+    if (A.Specificity != B.Specificity)
+      return A.Specificity > B.Specificity;
+    return A.TypedText < B.TypedText;
+  });
+
+  return P.Completions;
+}
+
+llvm::Optional<DynTypedMatcher>
+Parser::parseMatcherExpression(StringRef Code, Sema *S,
+                               const NamedValueMap *NamedValues,
+                               Diagnostics *Error) {
+  VariantValue Value;
+  if (!parseExpression(Code, S, NamedValues, &Value, Error))
+    return llvm::Optional<DynTypedMatcher>();
+  if (!Value.isMatcher()) {
+    Error->addError(SourceRange(), Error->ET_ParserNotAMatcher);
+    return llvm::Optional<DynTypedMatcher>();
+  }
+  llvm::Optional<DynTypedMatcher> Result =
+      Value.getMatcher().getSingleMatcher();
+  if (!Result.hasValue()) {
+    Error->addError(SourceRange(), Error->ET_ParserOverloadedType)
+        << Value.getTypeAsString();
+  }
+  return Result;
+}
+
+}  // namespace dynamic
+}  // namespace ast_matchers
+}  // namespace clang
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Registry.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Registry.cpp
new file mode 100644
index 0000000..04d3a32
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/Registry.cpp
@@ -0,0 +1,529 @@
+//===--- Registry.cpp - Matcher registry -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===------------------------------------------------------------===//
+///
+/// \file
+/// \brief Registry map populated at static initialization time.
+///
+//===------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/Dynamic/Registry.h"
+#include "Marshallers.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/ManagedStatic.h"
+#include <set>
+#include <utility>
+
+using namespace clang::ast_type_traits;
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+namespace {
+
+using internal::MatcherDescriptor;
+
+typedef llvm::StringMap<const MatcherDescriptor *> ConstructorMap;
+class RegistryMaps {
+public:
+  RegistryMaps();
+  ~RegistryMaps();
+
+  const ConstructorMap &constructors() const { return Constructors; }
+
+private:
+  void registerMatcher(StringRef MatcherName, MatcherDescriptor *Callback);
+  ConstructorMap Constructors;
+};
+
+void RegistryMaps::registerMatcher(StringRef MatcherName,
+                                   MatcherDescriptor *Callback) {
+  assert(Constructors.find(MatcherName) == Constructors.end());
+  Constructors[MatcherName] = Callback;
+}
+
+#define REGISTER_MATCHER(name)                                                 \
+  registerMatcher(#name, internal::makeMatcherAutoMarshall(                    \
+                             ::clang::ast_matchers::name, #name));
+
+#define SPECIFIC_MATCHER_OVERLOAD(name, Id)                                    \
+  static_cast< ::clang::ast_matchers::name##_Type##Id>(                        \
+      ::clang::ast_matchers::name)
+
+#define REGISTER_OVERLOADED_2(name)                                            \
+  do {                                                                         \
+    MatcherDescriptor *Callbacks[] = {                                         \
+      internal::makeMatcherAutoMarshall(SPECIFIC_MATCHER_OVERLOAD(name, 0),    \
+                                        #name),                                \
+      internal::makeMatcherAutoMarshall(SPECIFIC_MATCHER_OVERLOAD(name, 1),    \
+                                        #name)                                 \
+    };                                                                         \
+    registerMatcher(#name,                                                     \
+                    new internal::OverloadedMatcherDescriptor(Callbacks));     \
+  } while (0)
+
+/// \brief Generate a registry map with all the known matchers.
+RegistryMaps::RegistryMaps() {
+  // TODO: Here is the list of the missing matchers, grouped by reason.
+  //
+  // Need Variant/Parser fixes:
+  // ofKind
+  //
+  // Polymorphic + argument overload:
+  // findAll
+  //
+  // Other:
+  // equals
+  // equalsNode
+
+  REGISTER_OVERLOADED_2(callee);
+  REGISTER_OVERLOADED_2(hasPrefix);
+  REGISTER_OVERLOADED_2(hasType);
+  REGISTER_OVERLOADED_2(isDerivedFrom);
+  REGISTER_OVERLOADED_2(isSameOrDerivedFrom);
+  REGISTER_OVERLOADED_2(loc);
+  REGISTER_OVERLOADED_2(pointsTo);
+  REGISTER_OVERLOADED_2(references);
+  REGISTER_OVERLOADED_2(thisPointerType);
+
+  REGISTER_MATCHER(accessSpecDecl);
+  REGISTER_MATCHER(alignOfExpr);
+  REGISTER_MATCHER(allOf);
+  REGISTER_MATCHER(anyOf);
+  REGISTER_MATCHER(anything);
+  REGISTER_MATCHER(argumentCountIs);
+  REGISTER_MATCHER(arraySubscriptExpr);
+  REGISTER_MATCHER(arrayType);
+  REGISTER_MATCHER(asmStmt);
+  REGISTER_MATCHER(asString);
+  REGISTER_MATCHER(atomicType);
+  REGISTER_MATCHER(autoType);
+  REGISTER_MATCHER(binaryOperator);
+  REGISTER_MATCHER(bindTemporaryExpr);
+  REGISTER_MATCHER(blockPointerType);
+  REGISTER_MATCHER(boolLiteral);
+  REGISTER_MATCHER(breakStmt);
+  REGISTER_MATCHER(builtinType);
+  REGISTER_MATCHER(callExpr);
+  REGISTER_MATCHER(caseStmt);
+  REGISTER_MATCHER(castExpr);
+  REGISTER_MATCHER(catchStmt);
+  REGISTER_MATCHER(characterLiteral);
+  REGISTER_MATCHER(classTemplateDecl);
+  REGISTER_MATCHER(classTemplateSpecializationDecl);
+  REGISTER_MATCHER(complexType);
+  REGISTER_MATCHER(compoundLiteralExpr);
+  REGISTER_MATCHER(compoundStmt);
+  REGISTER_MATCHER(conditionalOperator);
+  REGISTER_MATCHER(constantArrayType);
+  REGISTER_MATCHER(constCastExpr);
+  REGISTER_MATCHER(constructExpr);
+  REGISTER_MATCHER(constructorDecl);
+  REGISTER_MATCHER(containsDeclaration);
+  REGISTER_MATCHER(continueStmt);
+  REGISTER_MATCHER(conversionDecl);
+  REGISTER_MATCHER(cStyleCastExpr);
+  REGISTER_MATCHER(ctorInitializer);
+  REGISTER_MATCHER(CUDAKernelCallExpr);
+  REGISTER_MATCHER(decl);
+  REGISTER_MATCHER(declaratorDecl);
+  REGISTER_MATCHER(declCountIs);
+  REGISTER_MATCHER(declRefExpr);
+  REGISTER_MATCHER(declStmt);
+  REGISTER_MATCHER(defaultArgExpr);
+  REGISTER_MATCHER(defaultStmt);
+  REGISTER_MATCHER(deleteExpr);
+  REGISTER_MATCHER(dependentSizedArrayType);
+  REGISTER_MATCHER(destructorDecl);
+  REGISTER_MATCHER(doStmt);
+  REGISTER_MATCHER(dynamicCastExpr);
+  REGISTER_MATCHER(eachOf);
+  REGISTER_MATCHER(elaboratedType);
+  REGISTER_MATCHER(enumConstantDecl);
+  REGISTER_MATCHER(enumDecl);
+  REGISTER_MATCHER(equalsBoundNode);
+  REGISTER_MATCHER(equalsIntegralValue);
+  REGISTER_MATCHER(explicitCastExpr);
+  REGISTER_MATCHER(expr);
+  REGISTER_MATCHER(exprWithCleanups);
+  REGISTER_MATCHER(fieldDecl);
+  REGISTER_MATCHER(floatLiteral);
+  REGISTER_MATCHER(forEach);
+  REGISTER_MATCHER(forEachConstructorInitializer);
+  REGISTER_MATCHER(forEachDescendant);
+  REGISTER_MATCHER(forEachSwitchCase);
+  REGISTER_MATCHER(forField);
+  REGISTER_MATCHER(forRangeStmt);
+  REGISTER_MATCHER(forStmt);
+  REGISTER_MATCHER(friendDecl);
+  REGISTER_MATCHER(functionalCastExpr);
+  REGISTER_MATCHER(functionDecl);
+  REGISTER_MATCHER(functionTemplateDecl);
+  REGISTER_MATCHER(functionType);
+  REGISTER_MATCHER(gotoStmt);
+  REGISTER_MATCHER(has);
+  REGISTER_MATCHER(hasAncestor);
+  REGISTER_MATCHER(hasAnyArgument);
+  REGISTER_MATCHER(hasAnyConstructorInitializer);
+  REGISTER_MATCHER(hasAnyParameter);
+  REGISTER_MATCHER(hasAnySubstatement);
+  REGISTER_MATCHER(hasAnyTemplateArgument);
+  REGISTER_MATCHER(hasAnyUsingShadowDecl);
+  REGISTER_MATCHER(hasArgument);
+  REGISTER_MATCHER(hasArgumentOfType);
+  REGISTER_MATCHER(hasAttr);
+  REGISTER_MATCHER(hasBase);
+  REGISTER_MATCHER(hasBody);
+  REGISTER_MATCHER(hasCanonicalType);
+  REGISTER_MATCHER(hasCaseConstant);
+  REGISTER_MATCHER(hasCondition);
+  REGISTER_MATCHER(hasConditionVariableStatement);
+  REGISTER_MATCHER(hasDeclaration);
+  REGISTER_MATCHER(hasDeclContext);
+  REGISTER_MATCHER(hasDeducedType);
+  REGISTER_MATCHER(hasDescendant);
+  REGISTER_MATCHER(hasDestinationType);
+  REGISTER_MATCHER(hasEitherOperand);
+  REGISTER_MATCHER(hasElementType);
+  REGISTER_MATCHER(hasElse);
+  REGISTER_MATCHER(hasFalseExpression);
+  REGISTER_MATCHER(hasGlobalStorage);
+  REGISTER_MATCHER(hasImplicitDestinationType);
+  REGISTER_MATCHER(hasIncrement);
+  REGISTER_MATCHER(hasIndex);
+  REGISTER_MATCHER(hasInitializer);
+  REGISTER_MATCHER(hasKeywordSelector);
+  REGISTER_MATCHER(hasLHS);
+  REGISTER_MATCHER(hasLocalQualifiers);
+  REGISTER_MATCHER(hasLocalStorage);
+  REGISTER_MATCHER(hasLoopInit);
+  REGISTER_MATCHER(hasLoopVariable);
+  REGISTER_MATCHER(hasMethod);
+  REGISTER_MATCHER(hasName);
+  REGISTER_MATCHER(hasNullSelector);
+  REGISTER_MATCHER(hasObjectExpression);
+  REGISTER_MATCHER(hasOperatorName);
+  REGISTER_MATCHER(hasOverloadedOperatorName);
+  REGISTER_MATCHER(hasParameter);
+  REGISTER_MATCHER(hasParent);
+  REGISTER_MATCHER(hasQualifier);
+  REGISTER_MATCHER(hasRangeInit);
+  REGISTER_MATCHER(hasReceiverType);
+  REGISTER_MATCHER(hasRHS);
+  REGISTER_MATCHER(hasSelector);
+  REGISTER_MATCHER(hasSingleDecl);
+  REGISTER_MATCHER(hasSize);
+  REGISTER_MATCHER(hasSizeExpr);
+  REGISTER_MATCHER(hasSourceExpression);
+  REGISTER_MATCHER(hasTargetDecl);
+  REGISTER_MATCHER(hasTemplateArgument);
+  REGISTER_MATCHER(hasThen);
+  REGISTER_MATCHER(hasTrueExpression);
+  REGISTER_MATCHER(hasTypeLoc);
+  REGISTER_MATCHER(hasUnaryOperand);
+  REGISTER_MATCHER(hasUnarySelector);
+  REGISTER_MATCHER(hasValueType);
+  REGISTER_MATCHER(ifStmt);
+  REGISTER_MATCHER(ignoringImpCasts);
+  REGISTER_MATCHER(ignoringParenCasts);
+  REGISTER_MATCHER(ignoringParenImpCasts);
+  REGISTER_MATCHER(implicitCastExpr);
+  REGISTER_MATCHER(incompleteArrayType);
+  REGISTER_MATCHER(initListExpr);
+  REGISTER_MATCHER(innerType);
+  REGISTER_MATCHER(integerLiteral);
+  REGISTER_MATCHER(isArrow);
+  REGISTER_MATCHER(isConst);
+  REGISTER_MATCHER(isConstQualified);
+  REGISTER_MATCHER(isDefinition);
+  REGISTER_MATCHER(isDeleted);
+  REGISTER_MATCHER(isExplicitTemplateSpecialization);
+  REGISTER_MATCHER(isExpr);
+  REGISTER_MATCHER(isExternC);
+  REGISTER_MATCHER(isImplicit);
+  REGISTER_MATCHER(isExpansionInFileMatching);
+  REGISTER_MATCHER(isExpansionInMainFile);
+  REGISTER_MATCHER(isInstantiated);
+  REGISTER_MATCHER(isExpansionInSystemHeader);
+  REGISTER_MATCHER(isInteger);
+  REGISTER_MATCHER(isIntegral);
+  REGISTER_MATCHER(isInTemplateInstantiation);
+  REGISTER_MATCHER(isListInitialization);
+  REGISTER_MATCHER(isOverride);
+  REGISTER_MATCHER(isPrivate);
+  REGISTER_MATCHER(isProtected);
+  REGISTER_MATCHER(isPublic);
+  REGISTER_MATCHER(isPure);
+  REGISTER_MATCHER(isTemplateInstantiation);
+  REGISTER_MATCHER(isVirtual);
+  REGISTER_MATCHER(isWritten);
+  REGISTER_MATCHER(labelStmt);
+  REGISTER_MATCHER(lambdaExpr);
+  REGISTER_MATCHER(lValueReferenceType);
+  REGISTER_MATCHER(matchesName);
+  REGISTER_MATCHER(matchesSelector);
+  REGISTER_MATCHER(materializeTemporaryExpr);
+  REGISTER_MATCHER(member);
+  REGISTER_MATCHER(memberCallExpr);
+  REGISTER_MATCHER(memberExpr);
+  REGISTER_MATCHER(memberPointerType);
+  REGISTER_MATCHER(methodDecl);
+  REGISTER_MATCHER(namedDecl);
+  REGISTER_MATCHER(namespaceDecl);
+  REGISTER_MATCHER(namesType);
+  REGISTER_MATCHER(nestedNameSpecifier);
+  REGISTER_MATCHER(nestedNameSpecifierLoc);
+  REGISTER_MATCHER(newExpr);
+  REGISTER_MATCHER(nullPtrLiteralExpr);
+  REGISTER_MATCHER(nullStmt);
+  REGISTER_MATCHER(numSelectorArgs);
+  REGISTER_MATCHER(ofClass);
+  REGISTER_MATCHER(objcMessageExpr);
+  REGISTER_MATCHER(on);
+  REGISTER_MATCHER(onImplicitObjectArgument);
+  REGISTER_MATCHER(operatorCallExpr);
+  REGISTER_MATCHER(parameterCountIs);
+  REGISTER_MATCHER(parenType);
+  REGISTER_MATCHER(parmVarDecl);
+  REGISTER_MATCHER(pointee);
+  REGISTER_MATCHER(pointerType);
+  REGISTER_MATCHER(qualType);
+  REGISTER_MATCHER(recordDecl);
+  REGISTER_MATCHER(recordType);
+  REGISTER_MATCHER(referenceType);
+  REGISTER_MATCHER(refersToDeclaration);
+  REGISTER_MATCHER(refersToIntegralType);
+  REGISTER_MATCHER(refersToType);
+  REGISTER_MATCHER(reinterpretCastExpr);
+  REGISTER_MATCHER(returns);
+  REGISTER_MATCHER(returnStmt);
+  REGISTER_MATCHER(rValueReferenceType);
+  REGISTER_MATCHER(sizeOfExpr);
+  REGISTER_MATCHER(specifiesNamespace);
+  REGISTER_MATCHER(specifiesType);
+  REGISTER_MATCHER(specifiesTypeLoc);
+  REGISTER_MATCHER(statementCountIs);
+  REGISTER_MATCHER(staticCastExpr);
+  REGISTER_MATCHER(stmt);
+  REGISTER_MATCHER(stringLiteral);
+  REGISTER_MATCHER(substNonTypeTemplateParmExpr);
+  REGISTER_MATCHER(switchCase);
+  REGISTER_MATCHER(switchStmt);
+  REGISTER_MATCHER(templateArgument);
+  REGISTER_MATCHER(templateArgumentCountIs);
+  REGISTER_MATCHER(templateSpecializationType);
+  REGISTER_MATCHER(temporaryObjectExpr);
+  REGISTER_MATCHER(thisExpr);
+  REGISTER_MATCHER(throughUsingDecl);
+  REGISTER_MATCHER(throwExpr);
+  REGISTER_MATCHER(to);
+  REGISTER_MATCHER(translationUnitDecl);
+  REGISTER_MATCHER(tryStmt);
+  REGISTER_MATCHER(type);
+  REGISTER_MATCHER(typedefDecl);
+  REGISTER_MATCHER(typedefType);
+  REGISTER_MATCHER(typeLoc);
+  REGISTER_MATCHER(unaryExprOrTypeTraitExpr);
+  REGISTER_MATCHER(unaryOperator);
+  REGISTER_MATCHER(unaryTransformType);
+  REGISTER_MATCHER(unless);
+  REGISTER_MATCHER(unresolvedConstructExpr);
+  REGISTER_MATCHER(unresolvedUsingValueDecl);
+  REGISTER_MATCHER(userDefinedLiteral);
+  REGISTER_MATCHER(usingDecl);
+  REGISTER_MATCHER(usingDirectiveDecl);
+  REGISTER_MATCHER(valueDecl);
+  REGISTER_MATCHER(varDecl);
+  REGISTER_MATCHER(variableArrayType);
+  REGISTER_MATCHER(voidType);
+  REGISTER_MATCHER(whileStmt);
+  REGISTER_MATCHER(withInitializer);
+}
+
+RegistryMaps::~RegistryMaps() {
+  for (ConstructorMap::iterator it = Constructors.begin(),
+                                end = Constructors.end();
+       it != end; ++it) {
+    delete it->second;
+  }
+}
+
+static llvm::ManagedStatic<RegistryMaps> RegistryData;
+
+} // anonymous namespace
+
+// static
+llvm::Optional<MatcherCtor> Registry::lookupMatcherCtor(StringRef MatcherName) {
+  ConstructorMap::const_iterator it =
+      RegistryData->constructors().find(MatcherName);
+  return it == RegistryData->constructors().end()
+             ? llvm::Optional<MatcherCtor>()
+             : it->second;
+}
+
+namespace {
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const std::set<ASTNodeKind> &KS) {
+  unsigned Count = 0;
+  for (std::set<ASTNodeKind>::const_iterator I = KS.begin(), E = KS.end();
+       I != E; ++I) {
+    if (I != KS.begin())
+      OS << "|";
+    if (Count++ == 3) {
+      OS << "...";
+      break;
+    }
+    OS << *I;
+  }
+  return OS;
+}
+
+}  // namespace
+
+std::vector<ArgKind> Registry::getAcceptedCompletionTypes(
+    ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
+  ASTNodeKind InitialTypes[] = {
+      ASTNodeKind::getFromNodeKind<Decl>(),
+      ASTNodeKind::getFromNodeKind<QualType>(),
+      ASTNodeKind::getFromNodeKind<Type>(),
+      ASTNodeKind::getFromNodeKind<Stmt>(),
+      ASTNodeKind::getFromNodeKind<NestedNameSpecifier>(),
+      ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>(),
+      ASTNodeKind::getFromNodeKind<TypeLoc>()};
+
+  // Starting with the above seed of acceptable top-level matcher types, compute
+  // the acceptable type set for the argument indicated by each context element.
+  std::set<ArgKind> TypeSet(std::begin(InitialTypes), std::end(InitialTypes));
+  for (const auto &CtxEntry : Context) {
+    MatcherCtor Ctor = CtxEntry.first;
+    unsigned ArgNumber = CtxEntry.second;
+    std::vector<ArgKind> NextTypeSet;
+    for (const ArgKind &Kind : TypeSet) {
+      if (Kind.getArgKind() == Kind.AK_Matcher &&
+          Ctor->isConvertibleTo(Kind.getMatcherKind()) &&
+          (Ctor->isVariadic() || ArgNumber < Ctor->getNumArgs()))
+        Ctor->getArgKinds(Kind.getMatcherKind(), ArgNumber, NextTypeSet);
+    }
+    TypeSet.clear();
+    TypeSet.insert(NextTypeSet.begin(), NextTypeSet.end());
+  }
+  return std::vector<ArgKind>(TypeSet.begin(), TypeSet.end());
+}
+
+std::vector<MatcherCompletion>
+Registry::getMatcherCompletions(ArrayRef<ArgKind> AcceptedTypes) {
+  std::vector<MatcherCompletion> Completions;
+
+  // Search the registry for acceptable matchers.
+  for (ConstructorMap::const_iterator I = RegistryData->constructors().begin(),
+                                      E = RegistryData->constructors().end();
+       I != E; ++I) {
+    std::set<ASTNodeKind> RetKinds;
+    unsigned NumArgs = I->second->isVariadic() ? 1 : I->second->getNumArgs();
+    bool IsPolymorphic = I->second->isPolymorphic();
+    std::vector<std::vector<ArgKind>> ArgsKinds(NumArgs);
+    unsigned MaxSpecificity = 0;
+    for (const ArgKind& Kind : AcceptedTypes) {
+      if (Kind.getArgKind() != Kind.AK_Matcher)
+        continue;
+      unsigned Specificity;
+      ASTNodeKind LeastDerivedKind;
+      if (I->second->isConvertibleTo(Kind.getMatcherKind(), &Specificity,
+                                     &LeastDerivedKind)) {
+        if (MaxSpecificity < Specificity)
+          MaxSpecificity = Specificity;
+        RetKinds.insert(LeastDerivedKind);
+        for (unsigned Arg = 0; Arg != NumArgs; ++Arg)
+          I->second->getArgKinds(Kind.getMatcherKind(), Arg, ArgsKinds[Arg]);
+        if (IsPolymorphic)
+          break;
+      }
+    }
+
+    if (!RetKinds.empty() && MaxSpecificity > 0) {
+      std::string Decl;
+      llvm::raw_string_ostream OS(Decl);
+
+      if (IsPolymorphic) {
+        OS << "Matcher<T> " << I->first() << "(Matcher<T>";
+      } else {
+        OS << "Matcher<" << RetKinds << "> " << I->first() << "(";
+        for (const std::vector<ArgKind> &Arg : ArgsKinds) {
+          if (&Arg != &ArgsKinds[0])
+            OS << ", ";
+
+          bool FirstArgKind = true;
+          std::set<ASTNodeKind> MatcherKinds;
+          // Two steps. First all non-matchers, then matchers only.
+          for (const ArgKind &AK : Arg) {
+            if (AK.getArgKind() == ArgKind::AK_Matcher) {
+              MatcherKinds.insert(AK.getMatcherKind());
+            } else {
+              if (!FirstArgKind) OS << "|";
+              FirstArgKind = false;
+              OS << AK.asString();
+            }
+          }
+          if (!MatcherKinds.empty()) {
+            if (!FirstArgKind) OS << "|";
+            OS << "Matcher<" << MatcherKinds << ">";
+          }
+        }
+      }
+      if (I->second->isVariadic())
+        OS << "...";
+      OS << ")";
+
+      std::string TypedText = I->first();
+      TypedText += "(";
+      if (ArgsKinds.empty())
+        TypedText += ")";
+      else if (ArgsKinds[0][0].getArgKind() == ArgKind::AK_String)
+        TypedText += "\"";
+
+      Completions.emplace_back(TypedText, OS.str(), MaxSpecificity);
+    }
+  }
+
+  return Completions;
+}
+
+// static
+VariantMatcher Registry::constructMatcher(MatcherCtor Ctor,
+                                          const SourceRange &NameRange,
+                                          ArrayRef<ParserValue> Args,
+                                          Diagnostics *Error) {
+  return Ctor->create(NameRange, Args, Error);
+}
+
+// static
+VariantMatcher Registry::constructBoundMatcher(MatcherCtor Ctor,
+                                               const SourceRange &NameRange,
+                                               StringRef BindID,
+                                               ArrayRef<ParserValue> Args,
+                                               Diagnostics *Error) {
+  VariantMatcher Out = constructMatcher(Ctor, NameRange, Args, Error);
+  if (Out.isNull()) return Out;
+
+  llvm::Optional<DynTypedMatcher> Result = Out.getSingleMatcher();
+  if (Result.hasValue()) {
+    llvm::Optional<DynTypedMatcher> Bound = Result->tryBind(BindID);
+    if (Bound.hasValue()) {
+      return VariantMatcher::SingleMatcher(*Bound);
+    }
+  }
+  Error->addError(NameRange, Error->ET_RegistryNotBindable);
+  return VariantMatcher();
+}
+
+}  // namespace dynamic
+}  // namespace ast_matchers
+}  // namespace clang
diff --git a/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/VariantValue.cpp b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/VariantValue.cpp
new file mode 100644
index 0000000..a88b707
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/ASTMatchers/Dynamic/VariantValue.cpp
@@ -0,0 +1,392 @@
+//===--- VariantValue.cpp - Polymorphic value type -*- C++ -*-===/
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Polymorphic value type.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/Dynamic/VariantValue.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/STLExtras.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+
+std::string ArgKind::asString() const {
+  switch (getArgKind()) {
+  case AK_Matcher:
+    return (Twine("Matcher<") + MatcherKind.asStringRef() + ">").str();
+  case AK_Unsigned:
+    return "unsigned";
+  case AK_String:
+    return "string";
+  }
+  llvm_unreachable("unhandled ArgKind");
+}
+
+bool ArgKind::isConvertibleTo(ArgKind To, unsigned *Specificity) const {
+  if (K != To.K)
+    return false;
+  if (K != AK_Matcher) {
+    if (Specificity)
+      *Specificity = 1;
+    return true;
+  }
+  unsigned Distance;
+  if (!MatcherKind.isBaseOf(To.MatcherKind, &Distance))
+    return false;
+
+  if (Specificity)
+    *Specificity = 100 - Distance;
+  return true;
+}
+
+bool
+VariantMatcher::MatcherOps::canConstructFrom(const DynTypedMatcher &Matcher,
+                                             bool &IsExactMatch) const {
+  IsExactMatch = Matcher.getSupportedKind().isSame(NodeKind);
+  return Matcher.canConvertTo(NodeKind);
+}
+
+llvm::Optional<DynTypedMatcher>
+VariantMatcher::MatcherOps::constructVariadicOperator(
+    DynTypedMatcher::VariadicOperator Op,
+    ArrayRef<VariantMatcher> InnerMatchers) const {
+  std::vector<DynTypedMatcher> DynMatchers;
+  for (const auto &InnerMatcher : InnerMatchers) {
+    // Abort if any of the inner matchers can't be converted to
+    // Matcher<T>.
+    if (!InnerMatcher.Value)
+      return llvm::None;
+    llvm::Optional<DynTypedMatcher> Inner =
+        InnerMatcher.Value->getTypedMatcher(*this);
+    if (!Inner)
+      return llvm::None;
+    DynMatchers.push_back(*Inner);
+  }
+  return DynTypedMatcher::constructVariadic(Op, DynMatchers);
+}
+
+VariantMatcher::Payload::~Payload() {}
+
+class VariantMatcher::SinglePayload : public VariantMatcher::Payload {
+public:
+  SinglePayload(const DynTypedMatcher &Matcher) : Matcher(Matcher) {}
+
+  llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
+    return Matcher;
+  }
+
+  std::string getTypeAsString() const override {
+    return (Twine("Matcher<") + Matcher.getSupportedKind().asStringRef() + ">")
+        .str();
+  }
+
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
+    bool Ignore;
+    if (Ops.canConstructFrom(Matcher, Ignore))
+      return Matcher;
+    return llvm::None;
+  }
+
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
+                       unsigned *Specificity) const override {
+    return ArgKind(Matcher.getSupportedKind())
+        .isConvertibleTo(Kind, Specificity);
+  }
+
+private:
+  const DynTypedMatcher Matcher;
+};
+
+class VariantMatcher::PolymorphicPayload : public VariantMatcher::Payload {
+public:
+  PolymorphicPayload(std::vector<DynTypedMatcher> MatchersIn)
+      : Matchers(std::move(MatchersIn)) {}
+
+  ~PolymorphicPayload() override {}
+
+  llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
+    if (Matchers.size() != 1)
+      return llvm::Optional<DynTypedMatcher>();
+    return Matchers[0];
+  }
+
+  std::string getTypeAsString() const override {
+    std::string Inner;
+    for (size_t i = 0, e = Matchers.size(); i != e; ++i) {
+      if (i != 0)
+        Inner += "|";
+      Inner += Matchers[i].getSupportedKind().asStringRef();
+    }
+    return (Twine("Matcher<") + Inner + ">").str();
+  }
+
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
+    bool FoundIsExact = false;
+    const DynTypedMatcher *Found = nullptr;
+    int NumFound = 0;
+    for (size_t i = 0, e = Matchers.size(); i != e; ++i) {
+      bool IsExactMatch;
+      if (Ops.canConstructFrom(Matchers[i], IsExactMatch)) {
+        if (Found) {
+          if (FoundIsExact) {
+            assert(!IsExactMatch && "We should not have two exact matches.");
+            continue;
+          }
+        }
+        Found = &Matchers[i];
+        FoundIsExact = IsExactMatch;
+        ++NumFound;
+      }
+    }
+    // We only succeed if we found exactly one, or if we found an exact match.
+    if (Found && (FoundIsExact || NumFound == 1))
+      return *Found;
+    return llvm::None;
+  }
+
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
+                       unsigned *Specificity) const override {
+    unsigned MaxSpecificity = 0;
+    for (const DynTypedMatcher &Matcher : Matchers) {
+      unsigned ThisSpecificity;
+      if (ArgKind(Matcher.getSupportedKind())
+              .isConvertibleTo(Kind, &ThisSpecificity)) {
+        MaxSpecificity = std::max(MaxSpecificity, ThisSpecificity);
+      }
+    }
+    if (Specificity)
+      *Specificity = MaxSpecificity;
+    return MaxSpecificity > 0;
+  }
+
+  const std::vector<DynTypedMatcher> Matchers;
+};
+
+class VariantMatcher::VariadicOpPayload : public VariantMatcher::Payload {
+public:
+  VariadicOpPayload(DynTypedMatcher::VariadicOperator Op,
+                    std::vector<VariantMatcher> Args)
+      : Op(Op), Args(std::move(Args)) {}
+
+  llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
+    return llvm::Optional<DynTypedMatcher>();
+  }
+
+  std::string getTypeAsString() const override {
+    std::string Inner;
+    for (size_t i = 0, e = Args.size(); i != e; ++i) {
+      if (i != 0)
+        Inner += "&";
+      Inner += Args[i].getTypeAsString();
+    }
+    return Inner;
+  }
+
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
+    return Ops.constructVariadicOperator(Op, Args);
+  }
+
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
+                       unsigned *Specificity) const override {
+    for (const VariantMatcher &Matcher : Args) {
+      if (!Matcher.isConvertibleTo(Kind, Specificity))
+        return false;
+    }
+    return true;
+  }
+
+private:
+  const DynTypedMatcher::VariadicOperator Op;
+  const std::vector<VariantMatcher> Args;
+};
+
+VariantMatcher::VariantMatcher() {}
+
+VariantMatcher VariantMatcher::SingleMatcher(const DynTypedMatcher &Matcher) {
+  return VariantMatcher(new SinglePayload(Matcher));
+}
+
+VariantMatcher
+VariantMatcher::PolymorphicMatcher(std::vector<DynTypedMatcher> Matchers) {
+  return VariantMatcher(new PolymorphicPayload(std::move(Matchers)));
+}
+
+VariantMatcher VariantMatcher::VariadicOperatorMatcher(
+    DynTypedMatcher::VariadicOperator Op,
+    std::vector<VariantMatcher> Args) {
+  return VariantMatcher(new VariadicOpPayload(Op, std::move(Args)));
+}
+
+llvm::Optional<DynTypedMatcher> VariantMatcher::getSingleMatcher() const {
+  return Value ? Value->getSingleMatcher() : llvm::Optional<DynTypedMatcher>();
+}
+
+void VariantMatcher::reset() { Value.reset(); }
+
+std::string VariantMatcher::getTypeAsString() const {
+  if (Value) return Value->getTypeAsString();
+  return "<Nothing>";
+}
+
+VariantValue::VariantValue(const VariantValue &Other) : Type(VT_Nothing) {
+  *this = Other;
+}
+
+VariantValue::VariantValue(unsigned Unsigned) : Type(VT_Nothing) {
+  setUnsigned(Unsigned);
+}
+
+VariantValue::VariantValue(const std::string &String) : Type(VT_Nothing) {
+  setString(String);
+}
+
+VariantValue::VariantValue(const VariantMatcher &Matcher) : Type(VT_Nothing) {
+  setMatcher(Matcher);
+}
+
+VariantValue::~VariantValue() { reset(); }
+
+VariantValue &VariantValue::operator=(const VariantValue &Other) {
+  if (this == &Other) return *this;
+  reset();
+  switch (Other.Type) {
+  case VT_Unsigned:
+    setUnsigned(Other.getUnsigned());
+    break;
+  case VT_String:
+    setString(Other.getString());
+    break;
+  case VT_Matcher:
+    setMatcher(Other.getMatcher());
+    break;
+  case VT_Nothing:
+    Type = VT_Nothing;
+    break;
+  }
+  return *this;
+}
+
+void VariantValue::reset() {
+  switch (Type) {
+  case VT_String:
+    delete Value.String;
+    break;
+  case VT_Matcher:
+    delete Value.Matcher;
+    break;
+  // Cases that do nothing.
+  case VT_Unsigned:
+  case VT_Nothing:
+    break;
+  }
+  Type = VT_Nothing;
+}
+
+bool VariantValue::isUnsigned() const {
+  return Type == VT_Unsigned;
+}
+
+unsigned VariantValue::getUnsigned() const {
+  assert(isUnsigned());
+  return Value.Unsigned;
+}
+
+void VariantValue::setUnsigned(unsigned NewValue) {
+  reset();
+  Type = VT_Unsigned;
+  Value.Unsigned = NewValue;
+}
+
+bool VariantValue::isString() const {
+  return Type == VT_String;
+}
+
+const std::string &VariantValue::getString() const {
+  assert(isString());
+  return *Value.String;
+}
+
+void VariantValue::setString(const std::string &NewValue) {
+  reset();
+  Type = VT_String;
+  Value.String = new std::string(NewValue);
+}
+
+bool VariantValue::isMatcher() const {
+  return Type == VT_Matcher;
+}
+
+const VariantMatcher &VariantValue::getMatcher() const {
+  assert(isMatcher());
+  return *Value.Matcher;
+}
+
+void VariantValue::setMatcher(const VariantMatcher &NewValue) {
+  reset();
+  Type = VT_Matcher;
+  Value.Matcher = new VariantMatcher(NewValue);
+}
+
+bool VariantValue::isConvertibleTo(ArgKind Kind, unsigned *Specificity) const {
+  switch (Kind.getArgKind()) {
+  case ArgKind::AK_Unsigned:
+    if (!isUnsigned())
+      return false;
+    *Specificity = 1;
+    return true;
+
+  case ArgKind::AK_String:
+    if (!isString())
+      return false;
+    *Specificity = 1;
+    return true;
+
+  case ArgKind::AK_Matcher:
+    if (!isMatcher())
+      return false;
+    return getMatcher().isConvertibleTo(Kind.getMatcherKind(), Specificity);
+  }
+  llvm_unreachable("Invalid Type");
+}
+
+bool VariantValue::isConvertibleTo(ArrayRef<ArgKind> Kinds,
+                                   unsigned *Specificity) const {
+  unsigned MaxSpecificity = 0;
+  for (const ArgKind& Kind : Kinds) {
+    unsigned ThisSpecificity;
+    if (!isConvertibleTo(Kind, &ThisSpecificity))
+      continue;
+    MaxSpecificity = std::max(MaxSpecificity, ThisSpecificity);
+  }
+  if (Specificity && MaxSpecificity > 0) {
+    *Specificity = MaxSpecificity;
+  }
+  return MaxSpecificity > 0;
+}
+
+std::string VariantValue::getTypeAsString() const {
+  switch (Type) {
+  case VT_String: return "String";
+  case VT_Matcher: return getMatcher().getTypeAsString();
+  case VT_Unsigned: return "Unsigned";
+  case VT_Nothing: return "Nothing";
+  }
+  llvm_unreachable("Invalid Type");
+}
+
+} // end namespace dynamic
+} // end namespace ast_matchers
+} // end namespace clang