Introduces DynTypedMatcher as a new concept that replaces the UntypedBaseMatcher and TypedMatcher. Due to DynTypedNode the basic dynamically typed matcher interface can now be simplified.

[klimek]

Summary

Also switches the traversal interfaces to use DynTypedNode;
this is in preperation for the hasAncestor implementation, and
also allows us to need fewer changes when we want to add new
nodes to traverse, thus making the code a little more decoupled.

Main design concerns: I went back towards the original design
of getNodeAs to return a pointer, and switched DynTypedNode::get
to always return a pointer (in case of value types like QualType
the pointer points into the storage of DynTypedNode, thus allowing
us to treat all the nodes the same from the point of view of a
user of the DynTypedNodes.

Adding the QualType implementation for DynTypedNode was needed
for the recursive traversal interface changes.

[silvas]

Looking pretty good!

include/clang/ASTMatchers/ASTMatchFinder.h

98–100

The name "Trigger" here isn't really speaking to me (and the comment isn't helping much either).

After looking a bit more into what this is used for, I honestly don't know why the comment didn't come along as clear, since it describe it pretty well.

I think it has to do with the 's in MatchCallback*'s, which masks the clear 1-1 correspondence going on here. I think it would be better to phrase this as "A DynTypedMatcher and the MatchCallback to be invoked when it matches".

Sorry, idk why this comment threw me off, but for whatever reason I truly had to dive all the way into the source to get a clue about what this is even for.

Also, putting this right above the Triggers vector would increase locality.

128–132

Since "trigger" is just a plain pair, it's not really clear at all what "executed against the AST means" for a trigger without some supporting documentation. Also as I mentioned above, putting the definition of Trigger nearby would help too.

(in general, a more self-documenting name than "trigger" would be good ("MatcherWithAction"?)).

include/clang/ASTMatchers/ASTTypeTraits.h

88–144

It seems like all of these traits classes are basically the same boilerplate with NT_* used for the tag and the actual stored type used as the type of the placement new and some reinterpret casting.

The only one that seems to differ between them is get which for Decl and Stmt has a dyn_cast, while QualType doesn't.

It would be nice if this duplication could be reduced, for example by having the traits class explicitly encode the constant (e.g. in an enum), and implementing as must as possible generically. I not, then at least a comment explaining the duplication situation would be good.

lib/ASTMatchers/ASTMatchFinder.cpp

90–95

A switch on the kind, with an "unreachable" default would allow clang to warn on incomplete coverage of the enum during future maintenance.

267–268

Maybe put a // FIXME near this to keep things grep'able.

364–366

I know this isn't directly related to this patch, but this is really the nerve-center of the matching process, and deserves to be better explained (or cross-referenced to where it is explained).

[klimek]

include/clang/ASTMatchers/ASTMatchFinder.h

128–132

Yea, I didn't really like the name either, and the more I think about it, the worse "Trigger" sounds.

How about MatchAction?

include/clang/ASTMatchers/ASTTypeTraits.h

88–144

The problem is that the QualType one is sufficiently different (using the storage for storage of the actual object).

The other two are similar enough, but on the other hand I'm not sure whether pulling out yet another abstraction is a good idea already.

lib/ASTMatchers/ASTMatchFinder.cpp

90–95

I actually don't want to expose the kind enum. Perhaps I'm a little too cautious, but I like my interfaces as small as possible.

I'm more thinking about having something built into RAV that would make sure all types are handled, but that would make RAV depend on the DynTypedNodes. I guess we'll see how it goes...

[silvas]

include/clang/ASTMatchers/ASTMatchFinder.h

128–132

To me, MatchAction sounds like "the action corresponding to a match", which is what MatchCallback is.

lib/ASTMatchers/ASTMatchFinder.cpp

90–95

Ok, no biggie.

My impression is that DynTypedNode will eventually graduate to be a public interface for general AST manipulation, and that the NodeTypeTag enum will naturally be part of the interface to allow users to switch on it. Only time will tell though. It's not a big deal at the moment though.

[klimek]

include/clang/ASTMatchers/ASTMatchFinder.h

128–132

Ok, couldn't come up with a better name and reverted the pull-out of the abstraction for now. Instead did a tyepdef of MatchCallback in the .cpp file for brevity of the type.

lib/ASTMatchers/ASTMatchFinder.cpp

267–268

There is actually no FIXME here - this code will not need to be adapted. The assert() is just there for the case where getMemoizationData() is out of sync with the rest of the DynTypedNode (which hopefully will not happen ;)

364–366

Hm, which parts need more explanations? Anything specific?

[klimek]

Updated in response to Sean's comments.

[silvas]

Comment at: lib/ASTMatchers/ASTMatchFinder.cpp:353-355
@@ -367,4 +352,5 @@
+ this, &Builder)) {

  BoundNodesTree BoundNodes = Builder.build();
  MatchVisitor Visitor(ActiveASTContext, It->second);
  BoundNodes.visitMatches(&Visitor);
}

---

Sean Silva wrote:

I know this isn't directly related to this patch, but this is really the nerve-center of the matching process, and deserves to be better explained (or cross-referenced to where it is explained).

Hm, which parts need more explanations? Anything specific?

It's not that it's that hard to understand, but that it's hard to
find. So, for example, I think it would be good to mention it in the
comment at the top of the file. Also, I think a comment on match()
should definitely say "this is the core of the matching process", or
something like that. In other words, in order to understand the code,
this is the best place to start at (AFAIK), and the reader should be
aware of that so that they don't waste their time.

If there is another place which is a better place to start, then that
should be the thing called out in the comment at the top of the file
of course.

--Sean Silva

[silvas]

Comment at: lib/ASTMatchers/ASTMatchFinder.cpp:353-355
@@ -367,4 +352,5 @@
+ this, &Builder)) {

  BoundNodesTree BoundNodes = Builder.build();
  MatchVisitor Visitor(ActiveASTContext, It->second);
  BoundNodes.visitMatches(&Visitor);
}

---

Sean Silva wrote:

I know this isn't directly related to this patch, but this is really the nerve-center of the matching process, and deserves to be better explained (or cross-referenced to where it is explained).

Hm, which parts need more explanations? Anything specific?

It's not that it's that hard to understand, but that it's hard to
find. So, for example, I think it would be good to mention it in the
comment at the top of the file. Also, I think a comment on match()
should definitely say "this is the core of the matching process", or
something like that. In other words, in order to understand the code,
this is the best place to start at (AFAIK), and the reader should be
aware of that so that they don't waste their time.

If there is another place which is a better place to start, then that
should be the thing called out in the comment at the top of the file
of course.

--Sean Silva

[djasper]

Mostly nits and comment changes ..

include/clang/ASTMatchers/ASTMatchers.h

67–68

Blank line after \brief unless this is intentional.

include/clang/ASTMatchers/ASTTypeTraits.h

28

.. kinds of AST nodes ..

51

maybe: (like \c Stmt and \c Decl)

53

\c QualType here and \c DynTypedNode below

83

Some more documentation (or a reference) to what a QualType actually is (Type-pointer + 3Bits) might help understanding this easier.

92

I'd be consistent with getMemoizationData (spacing around * and using Storage.buffer).

Actually, how about:
return dyn_cast<T>(getMemoizationData());
?

106

same as above

lib/ASTMatchers/ASTMatchFinder.cpp

43

Add a comment why we don't want memoization on QualTypes (e.g. might be incorrect together with the coming hasAncestor matchers or unnecessary as there are no big QualType hierarchies).

Also, maybe add FIXME to add memoization to for TypeLocs, once we match those (TypeLocs form bigger trees and presumably memoization is worth it). Also then it might make sense to store DynTypedNodes instead of void*!?

267

Why couldn't you reach this with a DynTypedNode representing a QualType? If you can, add test.

356–357

As you are here anyway, you could rename this to use the standard I and E, but up to you.

[klimek]

Updated according to comments.

include/clang/ASTMatchers/ASTMatchers.h

67–68

Done.

include/clang/ASTMatchers/ASTTypeTraits.h

28

Done.

51

Done.

53

Done.

83

I don't think we currently rely on that - for this implementation, all you need to know is that QualType doesn't have pointer identity and thus we need to store it by-value.

92

I dislike using getMemoizationData here. The other way around makes sense.

Storage.buffer is different, because we get 'Storage' as a const char[] in this method. Perhaps I should rename it to Buffer to be more consistent?

106

Same answer :P

lib/ASTMatchers/ASTMatchFinder.cpp

43

Tried to clarify in the comments.

Every TypeLoc has a QualType, so I don't see why the second argument holds - we'll either want to add memoization for both TypeLoc and QualType, or for neither.

Using DynTypedNode in the key doesn't make sense at all - we'll never want to get the original value back, we just need a one-way function that is unique.

267

Because matchesDescendantOf (ASTMatchersInternal:444) only works for Decl and Stmt currently...

356–357

Done.

[djasper]

include/clang/ASTMatchers/ASTTypeTraits.h

83

.. which I would find easier to understand than what the comment currently says.

How about:

/ Note that we can store \c Decls and \c Stmts by pointer as they are
/ guaranteed be unique pointers pointing to dedicated storage in the
/ AST. \c QualTypes on the other hand do not have storage or unique
/ pointers and thus need to be stored by value.
/// Further info: <reference to QualType>

(with the "Further info" completely optional).

92

Yes, the other way around makes more sense. I definitely like having only one reinterpret_cast :-).

'Storage' is fine, I just did not read carefully enough, sorry!

lib/ASTMatchers/ASTMatchFinder.cpp

43

Yes, exactly, every TypeLoc has a QualType, so it is sufficient to memoize the TypeLoc (memoizing the QualTypes, too, would at best lead to an improvement by a small constant factor). However, TypeLocs can form longer chains and we don't want to match whole subchains repeatedly for hasDescendant()..

"We just need a one-way function that is unique".. This is sort of what DynTypedNode provides (it already knows that for Decls and Stmts the pointer is unique and for QualTypes it has to use the value). Would be good to store information like that in only one class (even though we will never need the retrieval-logic). On the other hand, if you disagree on the first point and say that we will only ever want to memoize Stmts and Decls, this is a mute point ;-).

[silvas]

/ Note that we can store \c Decls and \c Stmts by pointer as they are
/ guaranteed be unique pointers pointing to dedicated storage in the
/ AST. \c QualTypes on the other hand do not have storage or unique
/ pointers and thus need to be stored by value.
/// Further info: <reference to QualType>

This sounds more like it should be in Clang AST 101, not in the depths
of the AST matcher implementation. Someone who doesn't know what a
QualType is isn't going to make it this far into the file; as in all
writing, considering your audience is important. As such, IMO this
comment isn't necessary. I think that Manuel's original comment very
nicely summarizes the status quo as far as "why we're storing the
QualType by value"; namely, that this is what the AST gives us.

However, an explanation is needed here:

/// \brief Supported base node types.

enum NodeTypeTag {	
  NT_Decl,	
  NT_Stmt,	
  NT_QualType	
} Tag;

, because QualType isn't really a "base node". Since Type/TypeLoc
_are_ actually bases, an explanation for why and in what sense
QualType is being used as a "base" here and not Type* or TypeLoc would
be highly desirable. Or maybe "base" is subtly off from being the
right concept here, which I think is more along the lines of "a handle
for a distinct kind of entity in the AST"; it may be easier to just
say "base" though :P.

--Sean Silva

[silvas]

/ Note that we can store \c Decls and \c Stmts by pointer as they are
/ guaranteed be unique pointers pointing to dedicated storage in the
/ AST. \c QualTypes on the other hand do not have storage or unique
/ pointers and thus need to be stored by value.
/// Further info: <reference to QualType>

This sounds more like it should be in Clang AST 101, not in the depths
of the AST matcher implementation. Someone who doesn't know what a
QualType is isn't going to make it this far into the file; as in all
writing, considering your audience is important. As such, IMO this
comment isn't necessary. I think that Manuel's original comment very
nicely summarizes the status quo as far as "why we're storing the
QualType by value"; namely, that this is what the AST gives us.

However, an explanation is needed here:

/// \brief Supported base node types.

enum NodeTypeTag {	
  NT_Decl,	
  NT_Stmt,	
  NT_QualType	
} Tag;

, because QualType isn't really a "base node". Since Type/TypeLoc
_are_ actually bases, an explanation for why and in what sense
QualType is being used as a "base" here and not Type* or TypeLoc would
be highly desirable. Or maybe "base" is subtly off from being the
right concept here, which I think is more along the lines of "a handle
for a distinct kind of entity in the AST"; it may be easier to just
say "base" though :P.

--Sean Silva

[klimek]

Changed comment.

include/clang/ASTMatchers/ASTTypeTraits.h

83

Done.

lib/ASTMatchers/ASTMatchFinder.cpp

43

Why can TypeLocs form longer chains than QualTypes?

I also think the notion of a key for a node is sufficiently different from a pointer to the node. I'd rather pull out a NodeKey class or something at one point. For now, I'd rather keep it simple.

[djasper]

LGTM

lib/ASTMatchers/ASTMatchFinder.cpp

43

I think that is just what TypeLocs do ;-).

I still think there is a lot of similarity between what we wnat to store here and what DynTypedNode currently does. However, I am perfectly happy keeping this simple (and a void*) in this CL.

[mdiamond]

Generally looks good. A few comments:

include/clang/ASTMatchers/ASTMatchFinder.h

131

I would prefer a clearer name, even if it is on the wordy side. Trigger doesn't really fit. Some possibilities:
MatcherMatchActionPair
MatcherMatchCallbackPair
MatcherAndActionPair

include/clang/ASTMatchers/ASTMatchersInternal.h

375

This comment is stale; might as well fix it while we're nearby. The comment doesn't include CXXCtorInitializer.

include/clang/ASTMatchers/ASTTypeTraits.h

83

typo: "guaranteed be" -> "guaranteed to be"

86

I think it would be better to use boost::any here. Then you don't have to explicitly specify all the types. You will still be able to store the QualType by value, but you won't have to worry about it in the declaration of Storage.

92

Why the change to reinterpret_cast? It seems a fair bit messier. This would also be cleaner using boost::any.

[djasper]

include/clang/ASTMatchers/ASTMatchFinder.h

131

Maybe: CallbackForMatcher?

include/clang/ASTMatchers/ASTTypeTraits.h

86

LLVM and Boost don't mix ;-).... Boost is quite massive and would create a significant burden on clang. The specialized abstractions provided by LLVM are quite sufficient for most use cases.

The best data structure would probably by a union, however until we can use C++11, unions don't support members with non-trivial constructors. That is why we use this helper structure for the time being.

92

As said above, no boost in LLVM. However, I agree that we could probably continue passing in a void* here, right? Even for the QualType we are passing a pointer to the storage inside DynTypedNode, which should work.

[klimek]

include/clang/ASTMatchers/ASTMatchFinder.h

131

Renamed to MatcherCallbackPairs. I dislike pretty much all of the names, but that seems to be most straight forward.

include/clang/ASTMatchers/ASTMatchersInternal.h

375

Done.

include/clang/ASTMatchers/ASTTypeTraits.h

83

Done.

92

The change from void* is because now we have an actual storage (the character array), and I think funneling this through a void* will make it less explicit that we're doing something fishy here.

[klimek]

Implements review comments.

[mdiamond]

LGTM.

include/clang/ASTMatchers/ASTTypeTraits.h

86

Hrmm... I talked briefly with Manuel about adding the Any abstraction to llvm/Support and I tried to broach the idea on the IRC channel but didn't get any response. I think that's the way to go in the future, but in the short term, I don't think it should hold up this CL.

include/clang/ASTMatchers/ASTMatchFinder.h

public:
 
   /// \brief Called when parsing is finished. Intended for testing only.
   class ParsingDoneTestCallback {
   public:
     virtual ~ParsingDoneTestCallback();
     virtual void run() = 0;
   };
 
   MatchFinder();
   ~MatchFinder();
 
   /// \brief Adds a matcher to execute when running over the AST.
   ///
   /// Calls 'Action' with the BoundNodes on every match.
   /// Adding more than one 'NodeMatch' allows finding different matches in a
   /// single pass over the AST.
   ///
   /// Does not take ownership of 'Action'.
   /// @{
public:
   /// \brief Registers a callback to notify the end of parsing.
   ///
   /// The provided closure is called after parsing is done, before the AST is
   /// traversed. Useful for benchmarking.
   /// Each call to FindAll(...) will call the closure once.
   void registerTestCallbackAfterParsing(ParsingDoneTestCallback *ParsingDone);
 
 private:
-  /// \brief The MatchCallback*'s will be called every time the
-  /// UntypedBaseMatcher matches on the AST.
-  std::vector< std::pair<
-    const internal::UntypedBaseMatcher*,
-    MatchCallback*> > Triggers;
+  /// \brief For each \c DynTypedMatcher a \c MatchCallback that will be called
+  /// when it matches.
+  std::vector<std::pair<const internal::DynTypedMatcher*, MatchCallback*> >
+    Triggers;
 
   /// \brief Called when parsing is done.
   ParsingDoneTestCallback *ParsingDone;
 };
 
 } // end namespace ast_matchers
 } // end namespace clang
 
 #endif // LLVM_CLANG_AST_MATCHERS_AST_MATCH_FINDER_H

include/clang/ASTMatchers/ASTMatchers.h

 ///
 /// The bound nodes are generated by calling \c bind("id") on the node matchers
 /// of the nodes we want to access later.
 ///
 /// The instances of BoundNodes are created by \c MatchFinder when the user's
 /// callbacks are executed every time a match is found.
 class BoundNodes {
 public:
   /// \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 {
+  const T *getNodeAs(StringRef ID) const {
     return MyBoundNodes.getNodeAs<T>(ID);
   }
 
   /// \brief Deprecated. Please use \c getNodeAs instead.
   /// @{
   template <typename T>
   const T *getDeclAs(StringRef ID) const {
-    return getNodeAs<T*>(ID);
+    return getNodeAs<T>(ID);
   }
   template <typename T>
   const T *getStmtAs(StringRef ID) const {
-    return getNodeAs<T*>(ID);
+    return getNodeAs<T>(ID);
   }
   /// @}
 
 private:
   /// \brief Create BoundNodes from a pre-filled map of bindings.
   BoundNodes(internal::BoundNodesMap &MyBoundNodes)
       : MyBoundNodes(MyBoundNodes) {}
 

include/clang/ASTMatchers/ASTMatchersInternal.h

 /// \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<const T*>(Node);
+    NodeMap[ID] = ast_type_traits::DynTypedNode::create(*Node);
   }
   void addNode(StringRef ID, ast_type_traits::DynTypedNode Node) {
     NodeMap[ID] = Node;
   }
 
   /// \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 {
+  const T *getNodeAs(StringRef ID) const {
     IDToNodeMap::const_iterator It = NodeMap.find(ID);
     if (It == NodeMap.end()) {
       return NULL;
     }
     return It->second.get<T>();
   }
 
   /// \brief Copies all ID/Node pairs to BoundNodesTreeBuilder \c Builder.
public:
   ///
   /// 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;
 };
 
-/// \brief Interface for matchers that only evaluate properties on a single node.
+/// \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.
   virtual bool matches(const T &Node,
                        ASTMatchFinder * /* Finder */,
                        BoundNodesTreeBuilder * /*  Builder */) const {
     return matchesNode(Node);
   }
 };
 
+/// \brief Base class for all matchers that works on a \c DynTypedNode.
+///
+/// Matcher implementations will check whether the \c DynTypedNode is
+/// convertible into the respecitve types and then do the actual match
+/// on the actual node, or return false if it is not convertible.
+class DynTypedMatcher {
+public:
+  virtual ~DynTypedMatcher() {}
+
+  /// \brief Returns true if the matcher matches the given \c DynNode.
+  virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
+                       ASTMatchFinder *Finder,
+                       BoundNodesTreeBuilder *Builder) const = 0;
+
+  /// \brief Returns a unique ID for the matcher.
+  virtual uint64_t getID() const = 0;
+};
+
 /// \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 {
+class Matcher : public DynTypedMatcher {
 public:
   /// \brief Takes ownership of the provided implementation pointer.
   explicit Matcher(MatcherInterface<T> *Implementation)
       : Implementation(Implementation) {}
 
   /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
   bool matches(const T &Node,
                ASTMatchFinder *Finder,
public:
 
   /// \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.getPtr());
   }
 
+  /// \brief Returns whether the matcher matches on the given \c DynNode.
+  virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
+                       ASTMatchFinder *Finder,
+                       BoundNodesTreeBuilder *Builder) const {
+    const T *Node = DynNode.get<T>();
+    if (!Node) return false;
+    return matches(*Node, Finder, Builder);
+  }
+
 private:
   /// \brief Allows conversion from Matcher<T> to Matcher<Derived> if Derived
   /// is derived from T.
   template <typename Derived>
   class ImplicitCastMatcher : public MatcherInterface<Derived> {
   public:
     explicit ImplicitCastMatcher(const Matcher<T> &From)
         : From(From) {}
bool matchesSpecialized(const CXXConstructExpr &Node,
     return NodeAsDecl != NULL &&
       InnerMatcher.matches(*NodeAsDecl, Finder, Builder);
   }
 
   const Matcher<Decl> InnerMatcher;
 };
 
 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST
 /// node class hierarchies (i.e. if T is Decl, Stmt, or QualType).
 template <typename T>
 struct IsBaseType {
   static const bool value =
       (llvm::is_same<T, Decl>::value ||
        llvm::is_same<T, Stmt>::value ||
        llvm::is_same<T, QualType>::value ||
        llvm::is_same<T, CXXCtorInitializer>::value);
 };
 template <typename T>
 const bool IsBaseType<T>::value;
 
-/// \brief Interface that can match any AST base node type and contains default
-/// implementations returning false.
-class UntypedBaseMatcher : public llvm::RefCountedBaseVPTR {
-public:
-  virtual ~UntypedBaseMatcher() {}
-
-  virtual bool matches(const Decl &DeclNode, ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    return false;
-  }
-  virtual bool matches(const QualType &TypeNode, ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    return false;
-  }
-  virtual bool matches(const Stmt &StmtNode, ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    return false;
-  }
-  virtual bool matches(const CXXCtorInitializer &CtorInitNode,
-                       ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    return false;
-  }
-
-  /// \brief Returns a unique ID for the matcher.
-  virtual uint64_t getID() const = 0;
-};
-
-/// \brief An UntypedBaseMatcher that overwrites the Matches(...) method for
-/// node type T. T must be an AST base type.
-template <typename T>
-class TypedBaseMatcher : public UntypedBaseMatcher {
-  TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
-                         typed_base_matcher_can_only_be_used_with_base_type);
-public:
-  explicit TypedBaseMatcher(const Matcher<T> &InnerMatcher)
-      : InnerMatcher(InnerMatcher) {}
-
-  using UntypedBaseMatcher::matches;
-  /// \brief Implements UntypedBaseMatcher::Matches.
-  ///
-  /// Since T is guaranteed to be a "base" AST node type, this method is
-  /// guaranteed to override one of the matches() methods from
-  /// UntypedBaseMatcher.
-  virtual bool matches(const T &Node,
-                       ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    return InnerMatcher.matches(Node, Finder, Builder);
-  }
-
-  /// \brief Implements UntypedBaseMatcher::getID.
-  virtual uint64_t getID() const {
-    return InnerMatcher.getID();
-  }
-
-private:
-  Matcher<T> InnerMatcher;
-};
-
 /// \brief Interface that allows matchers to traverse the AST.
 /// FIXME: Find a better name.
 ///
 /// This provides two entry methods for each base node type in the AST:
 /// - matchesChildOf:
 ///   Matches a matcher on every child node of the given node. Returns true
 ///   if at least one child node could be matched.
 /// - matchesDescendantOf:
public:
   /// \brief Returns true if the given class is directly or indirectly derived
   /// from a base type matching \c base.
   ///
   /// A class is considered to be also derived from itself.
   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
                                   const Matcher<NamedDecl> &Base,
                                   BoundNodesTreeBuilder *Builder) = 0;
 
-  // FIXME: Implement for other base nodes.
-  virtual bool matchesChildOf(const Decl &DeclNode,
-                              const UntypedBaseMatcher &BaseMatcher,
-                              BoundNodesTreeBuilder *Builder,
-                              TraversalKind Traverse,
-                              BindKind Bind) = 0;
-  virtual bool matchesChildOf(const Stmt &StmtNode,
-                              const UntypedBaseMatcher &BaseMatcher,
-                              BoundNodesTreeBuilder *Builder,
-                              TraversalKind Traverse,
-                              BindKind Bind) = 0;
+  template <typename T>
+  bool matchesChildOf(const T &Node,
+                      const DynTypedMatcher &Matcher,
+                      BindKind Bind) {
+    TOOLING_COMPILE_ASSERT((llvm::is_base_of<Decl, T>::value ||
+                            llvm::is_base_of<Stmt, T>::value),
+                           only_Decl_or_Stmt_allowed_for_recursive_matching);
+    return matchesChildOf(ast_type_traits::DynTypedNode::create(Node),
+                          Matcher, Builder, Traverse, Bind);
+  }
+
+  template <typename T>
+  bool matchesDescendantOf(const T &Node,
+                           const DynTypedMatcher &Matcher,
+                           BindKind Bind) {
+    TOOLING_COMPILE_ASSERT((llvm::is_base_of<Decl, T>::value ||
+                            llvm::is_base_of<Stmt, T>::value),
+                           only_Decl_or_Stmt_allowed_for_recursive_matching);
+    return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node),
+                               Matcher, Builder, Bind);
+  }
 
-  virtual bool matchesDescendantOf(const Decl &DeclNode,
-                                   const UntypedBaseMatcher &BaseMatcher,
-                                   BoundNodesTreeBuilder *Builder,
-                                   BindKind Bind) = 0;
-  virtual bool matchesDescendantOf(const Stmt &StmtNode,
-                                   const UntypedBaseMatcher &BaseMatcher,
+protected:
+  // FIXME: Implement for other base nodes.
+  virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
+                              const DynTypedMatcher &Matcher,
+                              TraversalKind Traverse,
+
+  virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
+                                   const DynTypedMatcher &Matcher,
                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) = 0;
 };
 
 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by
 /// "adapting" a \c To into a \c T.
 ///
 /// The \c ArgumentAdapterT argument specifies how the adaptation is done.
virtual bool matches(const T &Node,
                        BoundNodesTreeBuilder *Builder) const {
     return Finder->matchesChildOf(
         Node, ChildMatcher, Builder,
         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
         ASTMatchFinder::BK_First);
   }
 
  private:
-  const TypedBaseMatcher<ChildT> ChildMatcher;
+  const Matcher<ChildT> ChildMatcher;
 };
 
 /// \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.
 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match
 /// for each child that matches.
 template <typename T, typename ChildT>
virtual bool matches(const T& Node,
                        BoundNodesTreeBuilder* Builder) const {
     return Finder->matchesChildOf(
       Node, ChildMatcher, Builder,
       ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
       ASTMatchFinder::BK_All);
   }
 
 private:
-  const TypedBaseMatcher<ChildT> ChildMatcher;
+  const Matcher<ChildT> ChildMatcher;
 };
 
 /// \brief Matches nodes of type T if the given Matcher<T> does not match.
 ///
 /// Type argument MatcherT is required by PolymorphicMatcherWithParam1
 /// but not actually used. It will always be instantiated with a type
 /// convertible to Matcher<T>.
 template <typename T, typename MatcherT>
public:
   virtual bool matches(const T &Node,
                        ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder) const {
     return Finder->matchesDescendantOf(
         Node, DescendantMatcher, Builder, ASTMatchFinder::BK_First);
   }
 
  private:
-  const TypedBaseMatcher<DescendantT> DescendantMatcher;
+  const Matcher<DescendantT> DescendantMatcher;
 };
 
 /// \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.
 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match
 /// for each descendant node that matches instead of only for the first.
public:
   virtual bool matches(const T& Node,
                        ASTMatchFinder* Finder,
                        BoundNodesTreeBuilder* Builder) const {
     return Finder->matchesDescendantOf(Node, DescendantMatcher, Builder,
                                        ASTMatchFinder::BK_All);
   }
 
 private:
-  const TypedBaseMatcher<DescendantT> DescendantMatcher;
+  const Matcher<DescendantT> DescendantMatcher;
 };
 
 /// \brief Matches on nodes that have a getValue() method if getValue() equals
 /// the value the ValueEqualsMatcher was constructed with.
 template <typename T, typename ValueT>
 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> {
   TOOLING_COMPILE_ASSERT((llvm::is_base_of<CharacterLiteral, T>::value ||
                          llvm::is_base_of<CXXBoolLiteralExpr,

include/clang/ASTMatchers/ASTTypeTraits.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H
 #define LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Stmt.h"
+#include "llvm/Support/AlignOf.h"
 
 namespace clang {
 namespace ast_type_traits {
 
 /// \brief A dynamically typed AST node container.
 ///
-/// Stores an AST node in a type safe way.
+/// Stores an AST node in a type safe way. This allows writing code that
+/// works with different kinds of AST nodes, despite the fact that they don't
+/// have a common base class.
+///
 /// Use \c create(Node) to create a \c DynTypedNode from an AST node,
 /// and \c get<T>() to retrieve the node as type T if the types match.
+///
+/// See \c NodeTypeTag for which node base types are currently supported;
+/// You can create DynTypedNodes for all nodes in the inheritance hierarchy of
+/// the supported base types.
 class DynTypedNode {
 public:
-  /// \brief Creates a NULL-node, which is needed to be able to use
-  /// \c DynTypedNodes in STL data structures.
-  DynTypedNode() : Tag(), Node(NULL) {}
-
   /// \brief Creates a \c DynTypedNode from \c Node.
   template <typename T>
-  static DynTypedNode create(T Node) {
+  static DynTypedNode create(const T &Node) {
     return BaseConverter<T>::create(Node);
   }
 
   /// \brief Retrieve the stored node as type \c T.
   ///
   /// Returns NULL if the stored node does not have a type that is
   /// convertible to \c T.
+  ///
+  /// For types that have identity via their pointer in the AST
+  /// (like \c Stmt and \c Decl) the returned pointer points to the
+  /// referenced AST node.
+  /// For other types (like \c QualType) the value is stored directly
+  /// 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>
-  T get() const {
-    return llvm::dyn_cast<typename llvm::remove_pointer<T>::type>(
-      BaseConverter<T>::get(Tag, Node));
+  const T *get() const {
+    return BaseConverter<T>::get(Tag, Storage.buffer);
   }
 
+  /// \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;
+
 private:
   /// \brief Takes care of converting from and to \c T.
   template <typename T, typename EnablerT = void> struct BaseConverter;
 
   /// \brief Supported base node types.
   enum NodeTypeTag {
     NT_Decl,
-    NT_Stmt
+    NT_Stmt,
+    NT_QualType
   } Tag;
 
   /// \brief Stores the data of the node.
-  // FIXME: We really want to store a union, as we want to support
-  // storing TypeLoc nodes by-value.
-  // FIXME: Add QualType storage: we'll want to use QualType::getAsOpaquePtr()
-  // and getFromOpaquePtr(...) to convert to and from void*, but return the
-  // QualType objects by value.
-  void *Node;
-
-  DynTypedNode(NodeTypeTag Tag, const void *Node)
-    : Tag(Tag), Node(const_cast<void*>(Node)) {}
+  ///
+  /// Note that we can store \c Decls and \c Stmts by pointer as they are
+  /// guaranteed be unique pointers pointing to dedicated storage in the
+  /// AST. \c QualTypes on the other hand do not have storage or unique
+  /// pointers and thus need to be stored by value.
+  llvm::AlignedCharArrayUnion<Decl*, Stmt*, QualType> Storage;
 };
 template<typename T> struct DynTypedNode::BaseConverter<T,
-    typename llvm::enable_if<llvm::is_base_of<
-      Decl, typename llvm::remove_pointer<T>::type > >::type > {
-  static Decl *get(NodeTypeTag Tag, void *Node) {
-    if (Tag == NT_Decl) return static_cast<Decl*>(Node);
+    typename llvm::enable_if<llvm::is_base_of<Decl, T> >::type> {
+  static const T *get(NodeTypeTag Tag, const char Storage[]) {
+    if (Tag == NT_Decl)
+      return dyn_cast<T>(*reinterpret_cast<Decl*const*>(Storage));
     return NULL;
   }
-  static DynTypedNode create(const Decl *Node) {
-    return DynTypedNode(NT_Decl, Node);
+  static DynTypedNode create(const Decl &Node) {
+    DynTypedNode Result;
+    Result.Tag = NT_Decl;
+    new (Result.Storage.buffer) const Decl*(&Node);
+    return Result;
   }
 };
 template<typename T> struct DynTypedNode::BaseConverter<T,
-    typename llvm::enable_if<llvm::is_base_of<
-      Stmt, typename llvm::remove_pointer<T>::type > >::type > {
-  static Stmt *get(NodeTypeTag Tag, void *Node) {
-    if (Tag == NT_Stmt) return static_cast<Stmt*>(Node);
+    typename llvm::enable_if<llvm::is_base_of<Stmt, T> >::type> {
+  static const T *get(NodeTypeTag Tag, const char Storage[]) {
+    if (Tag == NT_Stmt)
+      return dyn_cast<T>(*reinterpret_cast<Stmt*const*>(Storage));
     return NULL;
   }
-  static DynTypedNode create(const Stmt *Node) {
-    return DynTypedNode(NT_Stmt, Node);
+  static DynTypedNode create(const Stmt &Node) {
+    DynTypedNode Result;
+    Result.Tag = NT_Stmt;
+    new (Result.Storage.buffer) const Stmt*(&Node);
+    return Result;
   }
 };
+template<> struct DynTypedNode::BaseConverter<QualType, void> {
+  static const QualType *get(NodeTypeTag Tag, const char Storage[]) {
+    if (Tag == NT_QualType)
+      return reinterpret_cast<const QualType*>(Storage);
+    return NULL;
+  }
+  static DynTypedNode create(const QualType &Node) {
+    DynTypedNode Result;
+    Result.Tag = NT_QualType;
+    new (Result.Storage.buffer) QualType(Node);
+    return Result;
+  }
+};
+// The only operation we allow on unsupported types is \c get.
+// This allows to conveniently use \c DynTypedNode when having an arbitrary
+// AST node that is not supported, but prevents misuse - a user cannot create
+// a DynTypedNode from arbitrary types.
+template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
+  static const T *get(NodeTypeTag Tag, const char Storage[]) { return NULL; }
+};
+
+inline const void *DynTypedNode::getMemoizationData() const {
+  switch (Tag) {
+    case NT_Decl: return BaseConverter<Decl>::get(Tag, Storage.buffer);
+    case NT_Stmt: return BaseConverter<Stmt>::get(Tag, Storage.buffer);
+    default: return NULL;
+  };
+}
 
 } // end namespace ast_type_traits
 } // end namespace clang
 
 #endif // LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H
 

lib/ASTMatchers/ASTMatchFinder.cpp

 #include "clang/AST/RecursiveASTVisitor.h"
 #include <set>
 
 namespace clang {
 namespace ast_matchers {
 namespace internal {
 namespace {
 
+typedef MatchFinder::MatchCallback MatchCallback;
+
 // We use memoization to avoid running the same matcher on the same
 // AST node twice.  This pair is the key for looking up match
 // result.  It consists of an ID of the MatcherInterface (for
 // identifying the matcher) and a pointer to the AST node.
+//
+// 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.
 typedef std::pair<uint64_t, const void*> UntypedMatchInput;
 
 // Used to store the result of a match and possibly bound nodes.
 struct MemoizedMatchResult {
   bool ResultOfMatch;
   BoundNodesTree 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 UntypedBaseMatcher *BaseMatcher,
+  MatchChildASTVisitor(const DynTypedMatcher *Matcher,
                        ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder,
                        int MaxDepth,
                        ASTMatchFinder::TraversalKind Traversal,
                        ASTMatchFinder::BindKind Bind)
-      : BaseMatcher(BaseMatcher),
+      : Matcher(Matcher),
         Finder(Finder),
         Builder(Builder),
         CurrentDepth(-1),
         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.
-  template <typename T>
-  bool findMatch(const T &Node) {
+  bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
     reset();
-    traverse(Node);
+    if (const Decl *D = DynNode.get<Decl>())
+      traverse(*D);
+    else if (const Stmt *S = DynNode.get<Stmt>())
+      traverse(*S);
+    // FIXME: Add other base types after adding tests.
     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) {
     return (DeclNode == NULL) || traverse(*DeclNode);
   }
bool traverse(const T &Node) {
     TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
                            traverse_can_only_be_instantiated_with_base_type);
     ScopedIncrement ScopedDepth(&CurrentDepth);
     if (CurrentDepth == 0) {
       // We don't want to match the root node, so just recurse.
       return baseTraverse(Node);
     }
     if (Bind != ASTMatchFinder::BK_All) {
-      if (BaseMatcher->matches(Node, Finder, Builder)) {
+      if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node),
+                           Finder, Builder)) {
         Matches = true;
         return false;  // Abort as soon as a match is found.
       }
       if (CurrentDepth < MaxDepth) {
         // The current node doesn't match, and we haven't reached the
         // maximum depth yet, so recurse.
         return baseTraverse(Node);
       }
       // The current node doesn't match, and we have reached the
       // maximum depth, so don't recurse (but continue the traversal
       // such that other nodes at the current level can be visited).
       return true;
     } else {
       BoundNodesTreeBuilder RecursiveBuilder;
-      if (BaseMatcher->matches(Node, Finder, &RecursiveBuilder)) {
+      if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node),
+                           Finder, &RecursiveBuilder)) {
         // After the first match the matcher succeeds.
         Matches = true;
         Builder->addMatch(RecursiveBuilder.build());
       }
       if (CurrentDepth < MaxDepth) {
         baseTraverse(Node);
       }
       // In kBindAll mode we always search for more matches.
       return true;
     }
   }
 
-  const UntypedBaseMatcher *const BaseMatcher;
+  const DynTypedMatcher *const Matcher;
   ASTMatchFinder *const Finder;
   BoundNodesTreeBuilder *const Builder;
   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(std::vector< std::pair<const UntypedBaseMatcher*,
-                               MatchFinder::MatchCallback*> > *Triggers)
+  MatchASTVisitor(std::vector<std::pair<const internal::DynTypedMatcher*,
+                                        MatchCallback*> > *Triggers)
      : Triggers(Triggers),
        ActiveASTContext(NULL) {
   }
 
   void set_active_ast_context(ASTContext *NewActiveASTContext) {
     ActiveASTContext = NewActiveASTContext;
   }
 
public:
   }
 
   bool TraverseDecl(Decl *DeclNode);
   bool TraverseStmt(Stmt *StmtNode);
   bool TraverseType(QualType TypeNode);
   bool TraverseTypeLoc(TypeLoc TypeNode);
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
-  template <typename T>
-  bool memoizedMatchesRecursively(const T &Node,
-                                  const UntypedBaseMatcher &BaseMatcher,
+  bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
+                                  const DynTypedMatcher &Matcher,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   TraversalKind Traversal, BindKind Bind) {
-    TOOLING_COMPILE_ASSERT((llvm::is_same<T, Decl>::value) ||
-                           (llvm::is_same<T, Stmt>::value),
-                           type_does_not_support_memoization);
-    const UntypedMatchInput input(BaseMatcher.getID(), &Node);
+    const UntypedMatchInput input(Matcher.getID(), Node.getMemoizationData());
+    assert(input.second &&
+           "Fix getMemoizationData once more types allow recursive matching.");
     std::pair<MemoizationMap::iterator, bool> InsertResult
       = ResultCache.insert(std::make_pair(input, MemoizedMatchResult()));
     if (InsertResult.second) {
       BoundNodesTreeBuilder DescendantBoundNodesBuilder;
       InsertResult.first->second.ResultOfMatch =
-        matchesRecursively(Node, BaseMatcher, &DescendantBoundNodesBuilder,
+        matchesRecursively(Node, Matcher, &DescendantBoundNodesBuilder,
                            MaxDepth, Traversal, Bind);
       InsertResult.first->second.Nodes =
         DescendantBoundNodesBuilder.build();
     }
     InsertResult.first->second.Nodes.copyTo(Builder);
     return InsertResult.first->second.ResultOfMatch;
   }
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
-  template <typename T>
-  bool matchesRecursively(const T &Node, const UntypedBaseMatcher &BaseMatcher,
+  bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
+                          const DynTypedMatcher &Matcher,
                           BoundNodesTreeBuilder *Builder, int MaxDepth,
                           TraversalKind Traversal, BindKind Bind) {
     MatchChildASTVisitor Visitor(
-      &BaseMatcher, this, Builder, MaxDepth, Traversal, Bind);
+      &Matcher, this, Builder, MaxDepth, Traversal, Bind);
     return Visitor.findMatch(Node);
   }
 
   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
                                   const Matcher<NamedDecl> &Base,
                                   BoundNodesTreeBuilder *Builder);
 
   // Implements ASTMatchFinder::MatchesChildOf.
-  virtual bool matchesChildOf(const Decl &DeclNode,
-                              const UntypedBaseMatcher &BaseMatcher,
-                              BoundNodesTreeBuilder *Builder,
-                              TraversalKind Traversal,
-                              BindKind Bind) {
-    return matchesRecursively(DeclNode, BaseMatcher, Builder, 1, Traversal,
-                              Bind);
-  }
-  virtual bool matchesChildOf(const Stmt &StmtNode,
-                              const UntypedBaseMatcher &BaseMatcher,
+  virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
+                              const DynTypedMatcher &Matcher,
                               BoundNodesTreeBuilder *Builder,
                               TraversalKind Traversal,
                               BindKind Bind) {
-    return matchesRecursively(StmtNode, BaseMatcher, Builder, 1, Traversal,
+    return matchesRecursively(Node, Matcher, Builder, 1, Traversal,
                               Bind);
   }
-
   // Implements ASTMatchFinder::MatchesDescendantOf.
-  virtual bool matchesDescendantOf(const Decl &DeclNode,
-                                   const UntypedBaseMatcher &BaseMatcher,
-                                   BoundNodesTreeBuilder *Builder,
-                                   BindKind Bind) {
-    return memoizedMatchesRecursively(DeclNode, BaseMatcher, Builder, INT_MAX,
-                                      TK_AsIs, Bind);
-  }
-  virtual bool matchesDescendantOf(const Stmt &StmtNode,
-                                   const UntypedBaseMatcher &BaseMatcher,
+  virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
+                                   const DynTypedMatcher &Matcher,
                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) {
-    return memoizedMatchesRecursively(StmtNode, BaseMatcher, Builder, INT_MAX,
+    return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
                                       TK_AsIs, Bind);
   }
 
   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }
 
 private:
   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
for (std::set<const TypedefDecl*>::const_iterator
         return true;
     }
     return false;
   }
 
   // Matches all registered matchers on the given node and calls the
   // result callback for every node that matches.
   template <typename T>
   void match(const T &node) {
-    for (std::vector< std::pair<const UntypedBaseMatcher*,
-                      MatchFinder::MatchCallback*> >::const_iterator
-             It = Triggers->begin(), End = Triggers->end();
-         It != End; ++It) {
+    for (std::vector<std::pair<const internal::DynTypedMatcher*,
+                               MatchCallback*> >::const_iterator
+             I = Triggers->begin(), E = Triggers->end();
+         I != E; ++I) {
       BoundNodesTreeBuilder Builder;
-      if (It->first->matches(node, this, &Builder)) {
+      if (I->first->matches(ast_type_traits::DynTypedNode::create(node),
+                            this, &Builder)) {
         BoundNodesTree BoundNodes = Builder.build();
-        MatchVisitor Visitor(ActiveASTContext, It->second);
+        MatchVisitor Visitor(ActiveASTContext, I->second);
         BoundNodes.visitMatches(&Visitor);
       }
     }
   }
 
-  std::vector< std::pair<const UntypedBaseMatcher*,
-               MatchFinder::MatchCallback*> > *const Triggers;
+  std::vector<std::pair<const internal::DynTypedMatcher*,
+                        MatchCallback*> > *const Triggers;
   ASTContext *ActiveASTContext;
 
   // Maps a canonical type to its TypedefDecls.
   llvm::DenseMap<const Type*, std::set<const TypedefDecl*> > TypeAliases;
 
   // Maps (matcher, node) -> the match result for memoization.
   typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
   MemoizationMap ResultCache;

 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLoc) {
   match(TypeLoc.getType());
   return RecursiveASTVisitor<MatchASTVisitor>::
       TraverseTypeLoc(TypeLoc);
 }
 
 class MatchASTConsumer : public ASTConsumer {
 public:
-  MatchASTConsumer(std::vector< std::pair<const UntypedBaseMatcher*,
-                                MatchFinder::MatchCallback*> > *Triggers,
+  MatchASTConsumer(std::vector<std::pair<const internal::DynTypedMatcher*,
+                                         MatchCallback*> > *Triggers,
                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
       : Visitor(Triggers),
         ParsingDone(ParsingDone) {}
 
 private:
   virtual void HandleTranslationUnit(ASTContext &Context) {
     if (ParsingDone != NULL) {
       ParsingDone->run();
: Nodes(Nodes), Context(Context),
     SourceManager(&Context->getSourceManager()) {}
 
 MatchFinder::MatchCallback::~MatchCallback() {}
 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
 
 MatchFinder::MatchFinder() : ParsingDone(NULL) {}
 
 MatchFinder::~MatchFinder() {
-  for (std::vector< std::pair<const internal::UntypedBaseMatcher*,
-                    MatchFinder::MatchCallback*> >::const_iterator
+  for (std::vector<std::pair<const internal::DynTypedMatcher*,
+                             MatchCallback*> >::const_iterator
            It = Triggers.begin(), End = Triggers.end();
        It != End; ++It) {
     delete It->first;
   }
 }
 
 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
-    new internal::TypedBaseMatcher<Decl>(NodeMatch), Action));
+    new internal::Matcher<Decl>(NodeMatch), Action));
 }
 
 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
-    new internal::TypedBaseMatcher<QualType>(NodeMatch), Action));
+    new internal::Matcher<QualType>(NodeMatch), Action));
 }
 
 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
-    new internal::TypedBaseMatcher<Stmt>(NodeMatch), Action));
+    new internal::Matcher<Stmt>(NodeMatch), Action));
 }
 
 ASTConsumer *MatchFinder::newASTConsumer() {
   return new internal::MatchASTConsumer(&Triggers, ParsingDone);
 }
 
 void MatchFinder::registerTestCallbackAfterParsing(
     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
   ParsingDone = NewParsingDone;
 }
 
 } // end namespace ast_matchers
 } // end namespace clang

unittests/ASTMatchers/ASTMatchersTest.cpp

EXPECT_TRUE(matchAndVerifyResultFalse("class A { class C {}; };",
       HasClassB, new VerifyIdIsBoundToDecl<Decl>("b")));
 }
 
 AST_POLYMORPHIC_MATCHER_P(
     polymorphicHas, internal::Matcher<Decl>, AMatcher) {
   TOOLING_COMPILE_ASSERT((llvm::is_same<NodeType, Decl>::value) ||
                          (llvm::is_same<NodeType, Stmt>::value),
                          assert_node_type_is_accessible);
-  internal::TypedBaseMatcher<Decl> ChildMatcher(AMatcher);
   return Finder->matchesChildOf(
-      Node, ChildMatcher, Builder,
+      Node, AMatcher, Builder,
       ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
       ASTMatchFinder::BK_First);
 }
 
 TEST(AstPolymorphicMatcherPMacro, Works) {
   DeclarationMatcher HasClassB =
       polymorphicHas(recordDecl(hasName("B")).bind("b"));