Refactor Matcher<T> and DynTypedMatcher to reduce overhead of casts.

[sbenza]

Summary

This change introduces DynMatcherInterface and changes the internal
representation of DynTypedMatcher and Matcher<T> to use a generic
interface instead.
It removes unnecessary indirections and virtual function calls when
converting matchers by implicit and dynamic casts.
DynTypedMatcher now remembers the stricter type in the chain of casts
and checks it before calling into DynMatcherInterface.
This change improves our clang-tidy related benchmark by ~14%.
Also, it opens the door for more optimizations of this kind that are
coming in future changes.

As a side effect of removing these template instantiations, it also
speeds up compilation of Dynamic/Registry.cpp by ~17% and reduces the number of
symbols generated by ~30%.

[sbenza]

fyi, this change moves the DynTypedMatcher class from below Matcher<> to above it, so the diff is a little confusing.

[klimek]

Wizardry! Nice benchmark numbers :)

lib/ASTMatchers/ASTMatchersInternal.cpp

54–60 ↗

(On Diff #14051)

Can we somehow put this implementation and the IdMatcher implementation closer together? I'm concerned if somebody changes one and the other breaks.

95–96 ↗

(On Diff #14051)

"mismatches" or "a mismatch"?

[sbenza]

fyi, I think this breaks memoization. The ID is now not enough to uniquely identify a matcher. The RestrictKind should also be part of it.
I will investigate before submitting this change.

lib/ASTMatchers/ASTMatchersInternal.cpp

54–60 ↗

(On Diff #14051)

My plan is to refector all template matcher that do not need the type into DynMatcherInterface. That includes IdMatcher, TrueMatcher, VariadicOperator, etc.
I did not do it on this change to limit the scope. Added some FIXME for them, though.

[klimek]

lib/ASTMatchers/ASTMatchersInternal.cpp

54–60 ↗

(On Diff #14051)

sg

[sbenza]

Added the RestrictKind to the matcher ID.
Also added a regression test to make sure memoization works with the new changes.
Verified that the test failed before the fix and passed afterwards.

[sbenza]

Minor fixes

lib/ASTMatchers/ASTMatchersInternal.cpp

95–96 ↗

(On Diff #14051)

Fixed.

[klimek]

include/clang/ASTMatchers/ASTMatchersInternal.h

288 ↗

(On Diff #14076)

Can you expand the comment on why we need to return a pair, so we remember 2 weeks from now :)

[sbenza]

Added comment

include/clang/ASTMatchers/ASTMatchersInternal.h

288 ↗

(On Diff #14076)

Done.

[klimek]

include/clang/ASTMatchers/ASTMatchersInternal.h

290–292 ↗

(On Diff #14175)

Can you give an example in the comment? I find it not trivial to reason about the actual cases this affects.

[sbenza]

Comment

include/clang/ASTMatchers/ASTMatchersInternal.h

290–292 ↗

(On Diff #14175)

How about now?

[klimek]

Perfect. Thanks. LG

[sbenza]

Closed by commit rL218616 (authored by @sbenza).

[chapuni]

Excuse me, I reverted it in r218648, for now.

• MSC17 doesn't compile it.
  
  clang/include/clang/ASTMatchers/ASTMatchersInternal.h(387) : error C4519: default template arguments are only allowed on a class template

• g++-4.7.2 reported so many warnings. See also http://bb.pgr.jp/builders/clang-3stage-x86_64-linux/builds/7720/steps/stage1_build

cfe/trunk/include/clang/AST/ASTTypeTraits.h

public:
   /// in the \c DynTypedNode, and the returned pointer points at
   /// the storage inside DynTypedNode. For those nodes, do not
   /// use the pointer outside the scope of the DynTypedNode.
   template <typename T>
   const T *get() const {
     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
   /// that don't have a pointer-defined identity inside the AST, this
   /// method returns NULL.
   const void *getMemoizationData() const { return MemoizationData; }
 
   /// \brief Prints the node to the given output stream.

cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h

 namespace internal {
 
 /// \brief Internal version of BoundNodes. Holds all the bound nodes.
 class BoundNodesMap {
 public:
   /// \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.
   ///
   /// Returns NULL if there was no node bound to \c ID or if there is a node but
   /// it cannot be converted to the specified type.
   template <typename T>
   const T *getNodeAs(StringRef ID) const {
public:
 
     /// \brief Called multiple times during a single call to VisitMatches(...).
     ///
     /// 'BoundNodesView' contains the bound nodes for a single match.
     virtual void visitMatch(const BoundNodes& BoundNodesView) = 0;
   };
 
   /// \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.
   void addMatch(const BoundNodesTreeBuilder &Bindings);
 
   /// \brief Visits all matches that this BoundNodesTree represents.
   ///
   /// The ownership of 'ResultVisitor' remains at the caller.
public:
   }
 
 private:
   SmallVector<BoundNodesMap, 16> Bindings;
 };
 
 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 matches(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
 /// descendants of the node or bind matched nodes to names. If you are
 /// writing a simple matcher that only inspects properties of the
 /// 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() {}
 
   /// \brief Returns true if 'Node' can be matched.
   ///
   /// May bind 'Node' to an ID via 'Builder', or recurse into
   /// the AST via 'Finder'.
   virtual bool matches(const T &Node,
                        ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder) const = 0;
+
+  bool matches(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
 /// node.
 template <typename T>
 class SingleNodeMatcherInterface : public MatcherInterface<T> {
 public:
   /// \brief Returns true if the matcher matches the provided node.
   ///
   /// A subclass must implement this instead of Matches().
   virtual bool matchesNode(const T &Node) const = 0;
 
 private:
   /// Implements MatcherInterface::Matches.
   bool matches(const T &Node,
                ASTMatchFinder * /* Finder */,
                BoundNodesTreeBuilder * /*  Builder */) const override {
     return matchesNode(Node);
   }
 };
 
-/// \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.
 ///
 /// It is constructed from a \c Matcher<T> object and redirects most calls to
 /// underlying matcher.
 /// It checks whether the \c DynTypedNode is convertible into the type of the
 /// underlying matcher and then do the actual match on the actual node, or
 /// 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)(
       const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
       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);
-  }
+               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
   ///   to a \c Matcher<T>.
   ///
   /// This method verifies that the underlying matcher in \c Other can process
   /// nodes of types T.
   template <typename T> bool canConvertTo() const {
public:
 
   /// \brief Same as \c convertTo(), but does not check that the underlying
   ///   matcher can handle a value of T.
   ///
   /// If it is not compatible, then this matcher will never match anything.
   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();
+  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;
+};
+
+/// \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 {
+  /// \brief Takes ownership of the provided implementation pointer.
+  explicit Matcher(MatcherInterface<T> *Implementation)
+      : Implementation(Implementation) {}
 
-    virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
-                         ASTMatchFinder *Finder,
-                         BoundNodesTreeBuilder *Builder) const = 0;
+  /// \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) {}
 
-    virtual llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const = 0;
+  /// \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)) {}
 
-    ast_type_traits::ASTNodeKind getSupportedKind() const {
-      return SupportedKind;
-    }
+  /// \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, typename std::enable_if<
+                             std::is_base_of<To, T>::value>::type * = nullptr>
+  Matcher<To> dynCastTo() const {
+    return Matcher<To>(Implementation);
 
-    uint64_t getID() const { return ID; }
-
-  private:
-    const ast_type_traits::ASTNodeKind SupportedKind;
-    const uint64_t ID;
-  };
-
-  class VariadicStorage : public MatcherStorage {
-  public:
-    VariadicStorage(VariadicOperatorFunction Func,
-                    ArrayRef<DynTypedMatcher> InnerMatchers)
-        : MatcherStorage(InnerMatchers[0].getSupportedKind(),
-                         reinterpret_cast<uint64_t>(this)),
-          Func(Func), InnerMatchers(InnerMatchers) {}
-
-    bool matches(const ast_type_traits::DynTypedNode DynNode,
-                 ASTMatchFinder *Finder,
-                 BoundNodesTreeBuilder *Builder) const override {
-      return Func(DynNode, Finder, Builder, InnerMatchers);
-    }
+  /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
+  bool matches(const T &Node,
+               BoundNodesTreeBuilder *Builder) const {
+    return Implementation.matches(ast_type_traits::DynTypedNode::create(Node),
+                                  Finder, Builder);
 
-    llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const override {
-      return llvm::None;
-    }
+  /// \brief Returns an ID that uniquely identifies the matcher.
+  DynTypedMatcher::MatcherIDType getID() const {
+    return Implementation.getID();
 
-  private:
-    VariadicOperatorFunction Func;
-    std::vector<DynTypedMatcher> InnerMatchers;
-  };
-
-  /// \brief Typed implementation of \c MatcherStorage.
-  template <typename T> class TypedMatcherStorage;
-
-  /// \brief Internal constructor for \c constructVariadic.
-  DynTypedMatcher(MatcherStorage *Storage) : Storage(Storage) {}
-
-  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 {
+  /// \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:
-  TypedMatcherStorage(const Matcher<T> &Other, bool AllowBind)
-      : MatcherStorage(ast_type_traits::ASTNodeKind::getFromNodeKind<T>(),
-                       Other.getID()),
-        InnerMatcher(Other), AllowBind(AllowBind) {}
+    TypeToQualType(const Matcher<TypeT> &InnerMatcher)
+        : InnerMatcher(InnerMatcher) {}
 
-  bool matches(const ast_type_traits::DynTypedNode DynNode,
-               ASTMatchFinder *Finder,
+    bool matches(const QualType &Node, ASTMatchFinder *Finder,
                  BoundNodesTreeBuilder *Builder) const override {
-    if (const T *Node = DynNode.get<T>()) {
-      return InnerMatcher.matches(*Node, Finder, Builder);
-    }
+      if (Node.isNull())
         return false;
+      return InnerMatcher.matches(*Node, Finder, Builder);
     }
-
-  llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const override {
-    if (!AllowBind)
-      return llvm::Optional<DynTypedMatcher>();
-    return DynTypedMatcher(BindableMatcher<T>(InnerMatcher).bind(ID));
-  }
-
    private:
-  const Matcher<T> InnerMatcher;
-  const bool AllowBind;
+    const Matcher<TypeT> InnerMatcher;
   };
 
-template <typename T>
-inline DynTypedMatcher::DynTypedMatcher(const Matcher<T> &M)
-    : Storage(new TypedMatcherStorage<T>(M, false)) {}
+private:
+  template <typename U> friend class Matcher;
+
+  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.
 ///
 /// This specialization provides the Matcher<Type>->Matcher<QualType>
 /// conversion that the static API does.
 template <>
 inline Matcher<QualType> DynTypedMatcher::convertTo<QualType>() const {
   assert(canConvertTo<QualType>());
public:
   /// the node.
   IdMatcher(StringRef ID, const Matcher<T> &InnerMatcher)
       : ID(ID), InnerMatcher(InnerMatcher) {}
 
   bool matches(const T &Node, ASTMatchFinder *Finder,
                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;
   }
 
 private:
   const std::string ID;
   const Matcher<T> InnerMatcher;
 };
public:
   explicit BindableMatcher(MatcherInterface<T> *Implementation)
     : Matcher<T>(Implementation) {}
 
   /// \brief Returns a matcher that will bind the matched node on a match.
   ///
   /// 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
 /// which a specified child matcher matches.
 ///
 /// ChildT must be an AST base type.
 template <typename T, typename ChildT>
 class HasMatcher : public MatcherInterface<T> {
template <typename T> operator Matcher<T>() const {
     addMatcher<T>(Param2, Matchers);
     addMatcher<T>(Param3, Matchers);
     addMatcher<T>(Param4, Matchers);
     addMatcher<T>(Param5, Matchers);
     addMatcher<T>(Param6, Matchers);
     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)));
   }
 
 private:
   template <typename T>
   static void addMatcher(const Matcher<T> &M,
                          std::vector<DynTypedMatcher> &Matchers) {

 /// matches.
 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
                            ASTMatchFinder *Finder,
                            BoundNodesTreeBuilder *Builder,
                            ArrayRef<DynTypedMatcher> InnerMatchers);
 
 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)));
 }
 
 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
 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)));
 }
 
 /// \brief Creates a Matcher<T> that matches if
 /// T is dyn_cast'able into InnerT and all inner matchers match.
 ///
 /// Returns BindableMatcher, as matchers that use dyn_cast have
 /// the same object both to match on and to run submatchers on,
 /// so there is no ambiguity with what gets bound.
 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
 /// type DescendantT for which the given inner matcher matches.
 ///
 /// DescendantT must be an AST base type.
 template <typename T, typename DescendantT>
 class HasDescendantMatcher : public MatcherInterface<T> {

cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp

 //
 // 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 {
-  uint64_t MatcherID;
+  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);
   }
 };

cfe/trunk/lib/ASTMatchers/ASTMatchersInternal.cpp

 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
   if (Bindings.empty())
     Bindings.push_back(BoundNodesMap());
   for (unsigned i = 0, e = Bindings.size(); i != e; ++i) {
     ResultVisitor->visitMatch(BoundNodes(Bindings[i]));
   }
 }
 
+namespace {
+
+class VariadicMatcher : public DynMatcherInterface {
+ public:
+  VariadicMatcher(VariadicOperatorFunction Func,
+                  std::vector<DynTypedMatcher> InnerMatchers)
+      : Func(Func), InnerMatchers(std::move(InnerMatchers)) {}
+
+  bool matches(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 matches(const ast_type_traits::DynTypedNode &DynNode,
+               ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const override {
+    bool Result = InnerMatcher->matches(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->matches(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);
 }
 
-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]);
   }
 }
 
 bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,

cfe/trunk/unittests/ASTMatchers/ASTMatchersTest.cpp

 }
 
 TEST(DeclarationMatcher, HasDescendantMemoization) {
   DeclarationMatcher CannotMemoize =
       decl(hasDescendant(typeLoc().bind("x")), has(decl()));
   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))));
   EXPECT_FALSE(matches("struct X {};",
                        decl(hasAttr(clang::attr::WarnUnused))));
 }
 
 TEST(DeclarationMatcher, MatchCudaDecl) {

cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp

 
 class MockSema : public Parser::Sema {
 public:
   virtual ~MockSema() {}
 
   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) {
     Diagnostics Error;
     VariantValue Value;
     Parser::parseExpression(Code, this, &Value, &Error);
     Values.push_back(Value);
     Errors.push_back(Error.toStringFull());
TEST(ParserTest, ParseMatcher) {
   const uint64_t ExpectedFoo = Sema.expectMatcher("Foo");
   const uint64_t ExpectedBar = Sema.expectMatcher("Bar");
   const uint64_t ExpectedBaz = Sema.expectMatcher("Baz");
   Sema.parse(" Foo ( Bar ( 17), Baz( \n \"B A,Z\") ) .bind( \"Yo!\") ");
   for (size_t i = 0, e = Sema.Errors.size(); i != e; ++i) {
     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];
   EXPECT_EQ("Bar", Bar.MatcherName);
   EXPECT_TRUE(matchesRange(Bar.NameRange, 1, 1, 8, 17));
   EXPECT_EQ(1ULL, Bar.Args.size());
   EXPECT_EQ(17U, Bar.Args[0].Value.getUnsigned());
 
   const MockSema::MatcherInfo Baz = Sema.Matchers[1];
   EXPECT_EQ("Baz", Baz.MatcherName);
   EXPECT_TRUE(matchesRange(Baz.NameRange, 1, 2, 19, 10));
   EXPECT_EQ(1ULL, Baz.Args.size());
   EXPECT_EQ("B A,Z", Baz.Args[0].Value.getString());
 
   const MockSema::MatcherInfo Foo = Sema.Matchers[2];
   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);
 }
 
 using ast_matchers::internal::Matcher;
 
 Parser::NamedValueMap getTestNamedValues() {
   Parser::NamedValueMap Values;
   Values["nameX"] = std::string("x");