Index: cfe/trunk/include/clang/AST/ASTTypeTraits.h
===================================================================
--- cfe/trunk/include/clang/AST/ASTTypeTraits.h
+++ cfe/trunk/include/clang/AST/ASTTypeTraits.h
@@ -191,6 +191,8 @@
     return BaseConverter<T>::get(NodeKind, Storage.buffer);
   }
 
+  ASTNodeKind getNodeKind() const { return NodeKind; }
+
   /// \brief Returns a pointer that identifies the stored AST node.
   ///
   /// Note that this is not supported by all AST nodes. For AST nodes
Index: cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h
===================================================================
--- cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h
+++ cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -61,9 +61,8 @@
   /// \brief Adds \c Node to the map with key \c ID.
   ///
   /// The node's base type should be in NodeBaseType or it will be unaccessible.
-  template <typename T>
-  void addNode(StringRef ID, const T* Node) {
-    NodeMap[ID] = ast_type_traits::DynTypedNode::create(*Node);
+  void addNode(StringRef ID, const ast_type_traits::DynTypedNode& DynNode) {
+    NodeMap[ID] = DynNode;
   }
 
   /// \brief Returns the AST node bound to \c ID.
@@ -136,11 +135,12 @@
   };
 
   /// \brief Add a binding from an id to a node.
-  template <typename T> void setBinding(const std::string &Id, const T *Node) {
+  void setBinding(const std::string &Id,
+                  const ast_type_traits::DynTypedNode &DynNode) {
     if (Bindings.empty())
       Bindings.push_back(BoundNodesMap());
     for (unsigned i = 0, e = Bindings.size(); i != e; ++i)
-      Bindings[i].addNode(Id, Node);
+      Bindings[i].addNode(Id, DynNode);
   }
 
   /// \brief Adds a branch in the tree.
@@ -179,6 +179,22 @@
 
 class ASTMatchFinder;
 
+/// \brief Generic interface for all matchers.
+///
+/// Used by the implementation of Matcher<T> and DynTypedMatcher.
+/// In general, implement MatcherInterface<T> or SingleNodeMatcherInterface<T>
+/// instead.
+class DynMatcherInterface : public RefCountedBaseVPTR {
+public:
+  /// \brief Returns true if \p DynNode can be matched.
+  ///
+  /// May bind \p DynNode to an ID via \p Builder, or recurse into
+  /// the AST via \p Finder.
+  virtual bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
+                          ASTMatchFinder *Finder,
+                          BoundNodesTreeBuilder *Builder) const = 0;
+};
+
 /// \brief Generic interface for matchers on an AST node of type T.
 ///
 /// Implement this if your matcher may need to inspect the children or
@@ -187,7 +203,7 @@
 /// current node and doesn't care about its children or descendants,
 /// implement SingleNodeMatcherInterface instead.
 template <typename T>
-class MatcherInterface : public RefCountedBaseVPTR {
+class MatcherInterface : public DynMatcherInterface {
 public:
   virtual ~MatcherInterface() {}
 
@@ -198,6 +214,15 @@
   virtual bool matches(const T &Node,
                        ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder) const = 0;
+
+  bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
+                  ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    if (const T *Node = DynNode.get<T>()) {
+      return matches(*Node, Finder, Builder);
+    }
+    return false;
+  }
 };
 
 /// \brief Interface for matchers that only evaluate properties on a single
@@ -219,111 +244,7 @@
   }
 };
 
-/// \brief Wrapper of a MatcherInterface<T> *that allows copying.
-///
-/// A Matcher<Base> can be used anywhere a Matcher<Derived> is
-/// required. This establishes an is-a relationship which is reverse
-/// to the AST hierarchy. In other words, Matcher<T> is contravariant
-/// with respect to T. The relationship is built via a type conversion
-/// operator rather than a type hierarchy to be able to templatize the
-/// type hierarchy instead of spelling it out.
-template <typename T>
-class Matcher {
-public:
-  /// \brief Takes ownership of the provided implementation pointer.
-  explicit Matcher(MatcherInterface<T> *Implementation)
-      : Implementation(Implementation) {}
-
-  /// \brief Implicitly converts \c Other to a Matcher<T>.
-  ///
-  /// Requires \c T to be derived from \c From.
-  template <typename From>
-  Matcher(const Matcher<From> &Other,
-          typename std::enable_if<std::is_base_of<From, T>::value &&
-                                  !std::is_same<From, T>::value>::type * = 0)
-      : Implementation(new ImplicitCastMatcher<From>(Other)) {}
-
-  /// \brief Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.
-  ///
-  /// The resulting matcher is not strict, i.e. ignores qualifiers.
-  template <typename TypeT>
-  Matcher(const Matcher<TypeT> &Other,
-          typename std::enable_if<
-            std::is_same<T, QualType>::value &&
-            std::is_same<TypeT, Type>::value>::type* = 0)
-      : Implementation(new TypeToQualType<TypeT>(Other)) {}
-
-  /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
-  bool matches(const T &Node,
-               ASTMatchFinder *Finder,
-               BoundNodesTreeBuilder *Builder) const {
-    if (Implementation->matches(Node, 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;
-  }
-
-  /// \brief Returns an ID that uniquely identifies the matcher.
-  uint64_t getID() const {
-    /// FIXME: Document the requirements this imposes on matcher
-    /// implementations (no new() implementation_ during a Matches()).
-    return reinterpret_cast<uint64_t>(Implementation.get());
-  }
-
-  /// \brief Allows the conversion of a \c Matcher<Type> to a \c
-  /// Matcher<QualType>.
-  ///
-  /// Depending on the constructor argument, the matcher is either strict, i.e.
-  /// does only matches in the absence of qualifiers, or not, i.e. simply
-  /// ignores any qualifiers.
-  template <typename TypeT>
-  class TypeToQualType : public MatcherInterface<QualType> {
-   public:
-    TypeToQualType(const Matcher<TypeT> &InnerMatcher)
-        : InnerMatcher(InnerMatcher) {}
-
-    bool matches(const QualType &Node, ASTMatchFinder *Finder,
-                 BoundNodesTreeBuilder *Builder) const override {
-      if (Node.isNull())
-        return false;
-      return InnerMatcher.matches(*Node, Finder, Builder);
-    }
-   private:
-    const Matcher<TypeT> InnerMatcher;
-  };
-
-private:
-  /// \brief Allows conversion from Matcher<Base> to Matcher<T> if T
-  /// is derived from Base.
-  template <typename Base>
-  class ImplicitCastMatcher : public MatcherInterface<T> {
-  public:
-    explicit ImplicitCastMatcher(const Matcher<Base> &From)
-        : From(From) {}
-
-    bool matches(const T &Node, ASTMatchFinder *Finder,
-                 BoundNodesTreeBuilder *Builder) const override {
-      return From.matches(Node, Finder, Builder);
-    }
-
-  private:
-    const Matcher<Base> From;
-  };
-
-  IntrusiveRefCntPtr< MatcherInterface<T> > Implementation;
-};  // class Matcher
-
-/// \brief A convenient helper for creating a Matcher<T> without specifying
-/// the template type argument.
-template <typename T>
-inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {
-  return Matcher<T>(Implementation);
-}
-
-template <typename T> class BindableMatcher;
+template <typename> class Matcher;
 
 /// \brief Matcher that works on a \c DynTypedNode.
 ///
@@ -334,13 +255,12 @@
 /// return false if it is not convertible.
 class DynTypedMatcher {
 public:
-  /// \brief Construct from a \c Matcher<T>. Copies the matcher.
-  template <typename T> inline DynTypedMatcher(const Matcher<T> &M);
-
-  /// \brief Construct from a bindable \c Matcher<T>. Copies the matcher.
-  ///
-  /// This version enables \c tryBind() on the \c DynTypedMatcher.
-  template <typename T> inline DynTypedMatcher(const BindableMatcher<T> &M);
+  /// \brief Takes ownership of the provided implementation pointer.
+  template <typename T>
+  DynTypedMatcher(MatcherInterface<T> *Implementation)
+      : AllowBind(false),
+        SupportedKind(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()),
+        RestrictKind(SupportedKind), Implementation(Implementation) {}
 
   /// \brief Construct from a variadic function.
   typedef bool (*VariadicOperatorFunction)(
@@ -348,33 +268,44 @@
       BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
   static DynTypedMatcher
   constructVariadic(VariadicOperatorFunction Func,
-                    ArrayRef<DynTypedMatcher> InnerMatchers) {
-    assert(InnerMatchers.size() > 0 && "Array must not be empty.");
-    return DynTypedMatcher(new VariadicStorage(Func, InnerMatchers));
-  }
+                    std::vector<DynTypedMatcher> InnerMatchers);
+
+  void setAllowBind(bool AB) { AllowBind = AB; }
+
+  /// \brief Return a matcher that points to the same implementation, but
+  ///   restricts the node types for \p Kind.
+  DynTypedMatcher dynCastTo(const ast_type_traits::ASTNodeKind Kind) const;
 
   /// \brief Returns true if the matcher matches the given \c DynNode.
-  bool matches(const ast_type_traits::DynTypedNode DynNode,
-               ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const {
-    return Storage->matches(DynNode, Finder, Builder);
-  }
+  bool matches(const ast_type_traits::DynTypedNode &DynNode,
+               ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const;
 
   /// \brief Bind the specified \p ID to the matcher.
   /// \return A new matcher with the \p ID bound to it if this matcher supports
   ///   binding. Otherwise, returns an empty \c Optional<>.
-  llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const {
-    return Storage->tryBind(ID);
-  }
+  llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const;
 
   /// \brief Returns a unique \p ID for the matcher.
-  uint64_t getID() const { return Storage->getID(); }
+  ///
+  /// Casting a Matcher<T> to Matcher<U> creates a matcher that has the
+  /// same \c Implementation pointer, but different \c RestrictKind. We need to
+  /// include both in the ID to make it unique.
+  ///
+  /// \c MatcherIDType supports operator< and provides strict weak ordering.
+  typedef std::pair<ast_type_traits::ASTNodeKind, uint64_t> MatcherIDType;
+  MatcherIDType getID() const {
+    /// FIXME: Document the requirements this imposes on matcher
+    /// implementations (no new() implementation_ during a Matches()).
+    return std::make_pair(RestrictKind,
+                          reinterpret_cast<uint64_t>(Implementation.get()));
+  }
 
   /// \brief Returns the type this matcher works on.
   ///
   /// \c matches() will always return false unless the node passed is of this
   /// or a derived type.
   ast_type_traits::ASTNodeKind getSupportedKind() const {
-    return Storage->getSupportedKind();
+    return SupportedKind;
   }
 
   /// \brief Returns \c true if the passed \c DynTypedMatcher can be converted
@@ -404,96 +335,119 @@
   template <typename T> Matcher<T> unconditionalConvertTo() const;
 
 private:
-  class MatcherStorage : public RefCountedBaseVPTR {
-  public:
-    MatcherStorage(ast_type_traits::ASTNodeKind SupportedKind, uint64_t ID)
-        : SupportedKind(SupportedKind), ID(ID) {}
-    virtual ~MatcherStorage();
-
-    virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
-                         ASTMatchFinder *Finder,
-                         BoundNodesTreeBuilder *Builder) const = 0;
-
-    virtual llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const = 0;
-
-    ast_type_traits::ASTNodeKind getSupportedKind() const {
-      return SupportedKind;
-    }
-
-    uint64_t getID() const { return ID; }
-
-  private:
-    const ast_type_traits::ASTNodeKind SupportedKind;
-    const uint64_t ID;
-  };
+  bool AllowBind;
+  ast_type_traits::ASTNodeKind SupportedKind;
+  /// \brief A potentially stricter node kind.
+  ///
+  /// It allows to perform implicit and dynamic cast of matchers without
+  /// needing to change \c Implementation.
+  ast_type_traits::ASTNodeKind RestrictKind;
+  IntrusiveRefCntPtr<DynMatcherInterface> Implementation;
+};
 
-  class VariadicStorage : public MatcherStorage {
-  public:
-    VariadicStorage(VariadicOperatorFunction Func,
-                    ArrayRef<DynTypedMatcher> InnerMatchers)
-        : MatcherStorage(InnerMatchers[0].getSupportedKind(),
-                         reinterpret_cast<uint64_t>(this)),
-          Func(Func), InnerMatchers(InnerMatchers) {}
+/// \brief Wrapper of a MatcherInterface<T> *that allows copying.
+///
+/// A Matcher<Base> can be used anywhere a Matcher<Derived> is
+/// required. This establishes an is-a relationship which is reverse
+/// to the AST hierarchy. In other words, Matcher<T> is contravariant
+/// with respect to T. The relationship is built via a type conversion
+/// operator rather than a type hierarchy to be able to templatize the
+/// type hierarchy instead of spelling it out.
+template <typename T>
+class Matcher {
+public:
+  /// \brief Takes ownership of the provided implementation pointer.
+  explicit Matcher(MatcherInterface<T> *Implementation)
+      : Implementation(Implementation) {}
 
-    bool matches(const ast_type_traits::DynTypedNode DynNode,
-                 ASTMatchFinder *Finder,
-                 BoundNodesTreeBuilder *Builder) const override {
-      return Func(DynNode, Finder, Builder, InnerMatchers);
-    }
+  /// \brief Implicitly converts \c Other to a Matcher<T>.
+  ///
+  /// Requires \c T to be derived from \c From.
+  template <typename From>
+  Matcher(const Matcher<From> &Other,
+          typename std::enable_if<std::is_base_of<From, T>::value &&
+                                  !std::is_same<From, T>::value>::type * = 0)
+      : Matcher(Other.Implementation) {}
 
-    llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const override {
-      return llvm::None;
-    }
+  /// \brief Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.
+  ///
+  /// The resulting matcher is not strict, i.e. ignores qualifiers.
+  template <typename TypeT>
+  Matcher(const Matcher<TypeT> &Other,
+          typename std::enable_if<
+            std::is_same<T, QualType>::value &&
+            std::is_same<TypeT, Type>::value>::type* = 0)
+      : Implementation(new TypeToQualType<TypeT>(Other)) {}
 
-  private:
-    VariadicOperatorFunction Func;
-    std::vector<DynTypedMatcher> InnerMatchers;
-  };
+  /// \brief Convert \c this into a \c Matcher<T> by applying dyn_cast<> to the
+  /// argument.
+  /// \c To must be a base class of \c T.
+  template <typename To>
+  Matcher<To> dynCastTo() const {
+    static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call.");
+    return Matcher<To>(Implementation);
+  }
 
-  /// \brief Typed implementation of \c MatcherStorage.
-  template <typename T> class TypedMatcherStorage;
+  /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
+  bool matches(const T &Node,
+               ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const {
+    return Implementation.matches(ast_type_traits::DynTypedNode::create(Node),
+                                  Finder, Builder);
+  }
 
-  /// \brief Internal constructor for \c constructVariadic.
-  DynTypedMatcher(MatcherStorage *Storage) : Storage(Storage) {}
+  /// \brief Returns an ID that uniquely identifies the matcher.
+  DynTypedMatcher::MatcherIDType getID() const {
+    return Implementation.getID();
+  }
 
-  IntrusiveRefCntPtr<const MatcherStorage> Storage;
-};
+  /// \brief Extract the dynamic matcher.
+  ///
+  /// The returned matcher keeps the same restrictions as \c this and remembers
+  /// that it is meant to support nodes of type \c T.
+  operator DynTypedMatcher() const { return Implementation; }
 
-template <typename T>
-class DynTypedMatcher::TypedMatcherStorage : public MatcherStorage {
-public:
-  TypedMatcherStorage(const Matcher<T> &Other, bool AllowBind)
-      : MatcherStorage(ast_type_traits::ASTNodeKind::getFromNodeKind<T>(),
-                       Other.getID()),
-        InnerMatcher(Other), AllowBind(AllowBind) {}
+  /// \brief Allows the conversion of a \c Matcher<Type> to a \c
+  /// Matcher<QualType>.
+  ///
+  /// Depending on the constructor argument, the matcher is either strict, i.e.
+  /// does only matches in the absence of qualifiers, or not, i.e. simply
+  /// ignores any qualifiers.
+  template <typename TypeT>
+  class TypeToQualType : public MatcherInterface<QualType> {
+   public:
+    TypeToQualType(const Matcher<TypeT> &InnerMatcher)
+        : InnerMatcher(InnerMatcher) {}
 
-  bool matches(const ast_type_traits::DynTypedNode DynNode,
-               ASTMatchFinder *Finder,
-               BoundNodesTreeBuilder *Builder) const override {
-    if (const T *Node = DynNode.get<T>()) {
+    bool matches(const QualType &Node, ASTMatchFinder *Finder,
+                 BoundNodesTreeBuilder *Builder) const override {
+      if (Node.isNull())
+        return false;
       return InnerMatcher.matches(*Node, Finder, Builder);
     }
-    return false;
-  }
-
-  llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const override {
-    if (!AllowBind)
-      return llvm::Optional<DynTypedMatcher>();
-    return DynTypedMatcher(BindableMatcher<T>(InnerMatcher).bind(ID));
-  }
+   private:
+    const Matcher<TypeT> InnerMatcher;
+  };
 
 private:
-  const Matcher<T> InnerMatcher;
-  const bool AllowBind;
-};
+  template <typename U> friend class Matcher;
 
-template <typename T>
-inline DynTypedMatcher::DynTypedMatcher(const Matcher<T> &M)
-    : Storage(new TypedMatcherStorage<T>(M, false)) {}
+  explicit Matcher(const DynTypedMatcher &Implementation)
+      : Implementation(Implementation.dynCastTo(
+            ast_type_traits::ASTNodeKind::getFromNodeKind<T>())) {
+    assert(this->Implementation.getSupportedKind()
+               .isSame(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()));
+  }
 
+  DynTypedMatcher Implementation;
+};  // class Matcher
+
+/// \brief A convenient helper for creating a Matcher<T> without specifying
+/// the template type argument.
 template <typename T>
-inline DynTypedMatcher::DynTypedMatcher(const BindableMatcher<T> &M)
-    : Storage(new TypedMatcherStorage<T>(M, true)) {}
+inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {
+  return Matcher<T>(Implementation);
+}
 
 /// \brief Specialization of the conversion functions for QualType.
 ///
@@ -1054,7 +1008,7 @@
                BoundNodesTreeBuilder *Builder) const override {
     bool Result = InnerMatcher.matches(Node, Finder, Builder);
     if (Result) {
-      Builder->setBinding(ID, &Node);
+      Builder->setBinding(ID, ast_type_traits::DynTypedNode::create(Node));
     }
     return Result;
   }
@@ -1080,8 +1034,18 @@
   /// The returned matcher is equivalent to this matcher, but will
   /// bind the matched node on a match.
   Matcher<T> bind(StringRef ID) const {
+    // FIXME: Use DynTypedMatcher's IdMatcher instead. No need for a template
+    // version anymore.
     return Matcher<T>(new IdMatcher<T>(ID, *this));
   }
+
+  /// \brief Same as Matcher<T>'s conversion operator, but enables binding on
+  /// the returned matcher.
+  operator DynTypedMatcher() const {
+    DynTypedMatcher Result = static_cast<const Matcher<T>&>(*this);
+    Result.setAllowBind(true);
+    return Result;
+  }
 };
 
 /// \brief Matches nodes of type T that have child nodes of type ChildT for
@@ -1206,6 +1170,7 @@
     addMatcher<T>(Param7, Matchers);
     addMatcher<T>(Param8, Matchers);
     addMatcher<T>(Param9, Matchers);
+    // FIXME: Use DynTypedMatcher::constructVariadic() instead.
     return Matcher<T>(
         new VariadicOperatorMatcherInterface<T>(Func, std::move(Matchers)));
   }
@@ -1344,6 +1309,7 @@
 
 template <typename T>
 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const {
+  // FIXME: Remove this extra indirection and connect directly to Matcher<T>().
   return Matcher<T>(new VariadicOperatorMatcherInterface<T>(
       AllOfVariadicOperator, llvm::makeArrayRef(*this)));
 }
@@ -1352,10 +1318,12 @@
 template<typename T>
 BindableMatcher<T> makeAllOfComposite(
     ArrayRef<const Matcher<T> *> InnerMatchers) {
+  // FIXME: Optimize for the cases of size()==0 and size()==1
   std::vector<DynTypedMatcher> DynMatchers;
   for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
     DynMatchers.push_back(*InnerMatchers[i]);
   }
+  // FIXME: Use DynTypedMatcher::constructVariadic() instead.
   return BindableMatcher<T>(new VariadicOperatorMatcherInterface<T>(
       AllOfVariadicOperator, std::move(DynMatchers)));
 }
@@ -1369,8 +1337,8 @@
 template<typename T, typename InnerT>
 BindableMatcher<T> makeDynCastAllOfComposite(
     ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
-  return BindableMatcher<T>(DynTypedMatcher(makeAllOfComposite(InnerMatchers))
-                                .unconditionalConvertTo<T>());
+  return BindableMatcher<T>(
+      makeAllOfComposite(InnerMatchers).template dynCastTo<T>());
 }
 
 /// \brief Matches nodes of type T that have at least one descendant node of
Index: cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp
+++ cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -53,7 +53,7 @@
 // FIXME: Benchmark whether memoization of non-pointer typed nodes
 // provides enough benefit for the additional amount of code.
 struct MatchKey {
-  uint64_t MatcherID;
+  DynTypedMatcher::MatcherIDType MatcherID;
   ast_type_traits::DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
 
Index: cfe/trunk/lib/ASTMatchers/ASTMatchersInternal.cpp
===================================================================
--- cfe/trunk/lib/ASTMatchers/ASTMatchersInternal.cpp
+++ cfe/trunk/lib/ASTMatchers/ASTMatchersInternal.cpp
@@ -26,6 +26,113 @@
   }
 }
 
+namespace {
+
+class VariadicMatcher : public DynMatcherInterface {
+ public:
+  VariadicMatcher(VariadicOperatorFunction Func,
+                  std::vector<DynTypedMatcher> InnerMatchers)
+      : Func(Func), 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:
+  VariadicOperatorFunction Func;
+  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 Return the most derived type between \p Kind1 and \p Kind2.
+///
+/// Return the null type if they are not related.
+ast_type_traits::ASTNodeKind getMostDerivedType(
+    const ast_type_traits::ASTNodeKind Kind1,
+    const ast_type_traits::ASTNodeKind Kind2) {
+  if (Kind1.isBaseOf(Kind2)) return Kind2;
+  if (Kind2.isBaseOf(Kind1)) return Kind1;
+  return ast_type_traits::ASTNodeKind();
+}
+
+/// \brief Return the least derived type between \p Kind1 and \p Kind2.
+///
+/// Return the null type if they are not related.
+static ast_type_traits::ASTNodeKind getLeastDerivedType(
+    const ast_type_traits::ASTNodeKind Kind1,
+    const ast_type_traits::ASTNodeKind Kind2) {
+  if (Kind1.isBaseOf(Kind2)) return Kind1;
+  if (Kind2.isBaseOf(Kind1)) return Kind2;
+  return ast_type_traits::ASTNodeKind();
+}
+
+}  // namespace
+
+DynTypedMatcher DynTypedMatcher::constructVariadic(
+    VariadicOperatorFunction Func, std::vector<DynTypedMatcher> InnerMatchers) {
+  assert(InnerMatchers.size() > 0 && "Array must not be empty.");
+  DynTypedMatcher Result = InnerMatchers[0];
+  // Use the least derived type as the restriction for the wrapper.
+  // This allows mismatches to be resolved on the inner matchers.
+  for (const DynTypedMatcher &M : InnerMatchers) {
+    assert(Result.SupportedKind.isSame(M.SupportedKind) &&
+           "SupportedKind must match!");
+    Result.RestrictKind =
+        getLeastDerivedType(Result.RestrictKind, M.RestrictKind);
+  }
+  Result.Implementation = new VariadicMatcher(Func, std::move(InnerMatchers));
+  return Result;
+}
+
+DynTypedMatcher DynTypedMatcher::dynCastTo(
+    const ast_type_traits::ASTNodeKind Kind) const {
+  auto Copy = *this;
+  Copy.SupportedKind = Kind;
+  Copy.RestrictKind = 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;
+}
+
+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>();
@@ -37,8 +144,6 @@
   return From.isBaseOf(To);
 }
 
-DynTypedMatcher::MatcherStorage::~MatcherStorage() {}
-
 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
   for (unsigned i = 0, e = Other.Bindings.size(); i != e; ++i) {
     Bindings.push_back(Other.Bindings[i]);
Index: cfe/trunk/unittests/ASTMatchers/ASTMatchersTest.cpp
===================================================================
--- cfe/trunk/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ cfe/trunk/unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -654,6 +654,20 @@
   EXPECT_TRUE(matches("void f() { int i; }", CannotMemoize));
 }
 
+TEST(DeclarationMatcher, HasDescendantMemoizationUsesRestrictKind) {
+  auto Name = hasName("i");
+  auto VD = internal::Matcher<VarDecl>(Name).dynCastTo<Decl>();
+  auto RD = internal::Matcher<RecordDecl>(Name).dynCastTo<Decl>();
+  // Matching VD first should not make a cache hit for RD.
+  EXPECT_TRUE(notMatches("void f() { int i; }",
+                         decl(hasDescendant(VD), hasDescendant(RD))));
+  EXPECT_TRUE(notMatches("void f() { int i; }",
+                         decl(hasDescendant(RD), hasDescendant(VD))));
+  // Not matching RD first should not make a cache hit for VD either.
+  EXPECT_TRUE(matches("void f() { int i; }",
+                      decl(anyOf(hasDescendant(RD), hasDescendant(VD)))));
+}
+
 TEST(DeclarationMatcher, HasAttr) {
   EXPECT_TRUE(matches("struct __attribute__((warn_unused)) X {};",
                       decl(hasAttr(clang::attr::WarnUnused))));
Index: cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp
===================================================================
--- cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp
+++ cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp
@@ -28,7 +28,7 @@
   uint64_t expectMatcher(StringRef MatcherName) {
     ast_matchers::internal::Matcher<Stmt> M = stmt();
     ExpectedMatchers.insert(std::make_pair(MatcherName, M));
-    return M.getID();
+    return M.getID().second;
   }
 
   void parse(StringRef Code) {
@@ -125,8 +125,12 @@
     EXPECT_EQ("", Sema.Errors[i]);
   }
 
+  EXPECT_NE(ExpectedFoo, ExpectedBar);
+  EXPECT_NE(ExpectedFoo, ExpectedBaz);
+  EXPECT_NE(ExpectedBar, ExpectedBaz);
+
   EXPECT_EQ(1ULL, Sema.Values.size());
-  EXPECT_EQ(ExpectedFoo, getSingleMatcher(Sema.Values[0])->getID());
+  EXPECT_EQ(ExpectedFoo, getSingleMatcher(Sema.Values[0])->getID().second);
 
   EXPECT_EQ(3ULL, Sema.Matchers.size());
   const MockSema::MatcherInfo Bar = Sema.Matchers[0];
@@ -145,8 +149,8 @@
   EXPECT_EQ("Foo", Foo.MatcherName);
   EXPECT_TRUE(matchesRange(Foo.NameRange, 1, 2, 2, 12));
   EXPECT_EQ(2ULL, Foo.Args.size());
-  EXPECT_EQ(ExpectedBar, getSingleMatcher(Foo.Args[0].Value)->getID());
-  EXPECT_EQ(ExpectedBaz, getSingleMatcher(Foo.Args[1].Value)->getID());
+  EXPECT_EQ(ExpectedBar, getSingleMatcher(Foo.Args[0].Value)->getID().second);
+  EXPECT_EQ(ExpectedBaz, getSingleMatcher(Foo.Args[1].Value)->getID().second);
   EXPECT_EQ("Yo!", Foo.BoundID);
 }