Make it possible control matcher traversal kind with ASTContext

[steveire]

Summary

This will eventually allow traversal of an AST while ignoring invisible
AST nodes. Currently it depends on the available enum values for
TraversalKinds. That can be extended to ignore all invisible nodes in
the future.

[steveire]

@klimek This includes a test for the memoization case you were interested in at EuroLLVM.

In this iteration of the API, the traversal kind is changed by using a new traverse matcher, which gives the user control over whether invisible/implicit nodes are skipped or not.

[steveire]

Format

[steveire]

Format

[aaron.ballman]

Thanks for this -- it looks like really interesting functionality! I've mostly found nits thus far, but did have a question about clang-query support for it.

include/clang/AST/ASTContext.h

562–563

This doesn't match our coding guidelines. Should be getTraversalKind(), etc. Same below.

565–568

Is there a reason we don't want these functions to be marked const?

include/clang/AST/ASTNodeTraverser.h

79

setTraversalKind()

107

Let's not make underscores important like this -- how about Node or something generic instead?

115–116

What an unfortunate name for this. IgnoreParenImpCasts() ignores parens, implicit casts, full expressions, temporary materialization, and non-type template substitutions, and those extra nodes have surprised people in the past.

Not much to be done about it here, just loudly lamenting the existing name of the trait.

include/clang/ASTMatchers/ASTMatchers.h

701

Missing a full stop at the end of the comment.

716

Copy pasta?

718

Is this an API we should be exposing to clang-query as well? Will those users be able to use a string literal for the traversal kind, like they already do for attribute kinds (etc)?

include/clang/ASTMatchers/ASTMatchersInternal.h

286

traversalKind()

287

return llvm::None;

lib/AST/ASTContext.cpp

120

auto *

10358

Stmt *

lib/ASTMatchers/ASTMatchFinder.cpp

155

auto *

lib/ASTMatchers/ASTMatchersInternal.cpp

214–219

Please do not use auto here.

218–219

Or here...

231–236

Or here...

234

Add an assertion message?

[steveire]

Update

include/clang/AST/ASTContext.h

562–563

I think clang still uses uppercase names everywhere. Can you be more specific?

565–568

It looks like they can be const.

include/clang/ASTMatchers/ASTMatchers.h

718

Yes, I thought about that, but in a follow-up patch. First, I aim to extend the TraversalKind enum with TK_IgnoreInvisble.

[aaron.ballman]

include/clang/AST/ASTContext.h

562–563

No, Clang doesn't use uppercase names everywhere -- we're consistently inconsistent and it depends mostly on the age of when the code was introduced and what the surrounding code looks like. We still follow the usual coding style guidelines for naming conventions -- stick with the convention used by nearby code if it's already consistent, otherwise follow the coding style rules.

include/clang/ASTMatchers/ASTMatchers.h

716

You dropped the interesting bit from the documentation here -- you should add in what the matcher is matching (which makes the preceding "The matcher \code ... \endcode" grammatical again).

718

This is new functionality, so why do you want to wait for a follow-up patch (is it somehow more involved)? We typically add support for dynamic matchers at the same time we add support for the static matchers because otherwise the two get frustratingly out of sync.

[steveire]

include/clang/ASTMatchers/ASTMatchers.h

718

Perhaps I can add the support in DynamicASTMatchers. Can you give some direction on that? I don't recall where the attr strings are handled.

A corresponding change to clang-query will be in another patch anyway because it's a different repo.

[steveire]

Update

[aaron.ballman]

include/clang/ASTMatchers/ASTMatchers.h

718

Perhaps I can add the support in DynamicASTMatchers. Can you give some direction on that? I don't recall where the attr strings are handled.

I always wind up having to use svn blame to figure it out, so you're not alone in your recollections. ;-) You add a new specialization of ArgTypeTraits to Marshallers.h for the enumeration type. See around line 123 or so for how it's done for attr::Kind.

A corresponding change to clang-query will be in another patch anyway because it's a different repo.

Once you have the enumeration being marshaled, I believe all you have to do is expose the new API via Registry.cpp like any other matcher, though I'd also request tests be added to Dynamic/RegistryTest.cpp since this is adding a small amount of new marshaling code.

[steveire]

lib/ASTMatchers/ASTMatchersInternal.cpp

234

Saying what? The original code doesn't have one. Let's avoid round trips in review comments :).

[aaron.ballman]

lib/AST/ASTContext.cpp

120

The formatting is wrong here -- be sure to run the patch through clang-format before committing.

lib/ASTMatchers/ASTMatchersInternal.cpp

234

This isn't a "round trip"; it's not unreasonable to ask people to NFC improve the code they're touching (it's akin to saying "Because you figured out this complex piece of code does X, can you add a comment to it so others don't have to do that work next time.").

As best I can tell, this assertion exists because this function is meant to mirror matches() without this base check in release mode. You've lost that mirroring with your refactoring, which looks suspicious. Is there a reason this function deviates from matches() now?

As for the assertion message itself, how about "matched a node of an unexpected derived kind"?

[steveire]

lib/ASTMatchers/ASTMatchersInternal.cpp

234

Hmm, maybe that was a misunderstanding. Your note about an assertion message was not clear, so I asked you what you suggest the message should be. No need for offense :)

[steveire]

Rebase and update

[aaron.ballman]

LGTM with a few minor nits.

clang/include/clang/AST/ASTContext.h

3009 ↗

(On Diff #230678)

Do we need to use std::map here, or could we use an IndexedMap or DenseMap?

(std::map tends to perform poorly under some circumstances and the keys in this case look like they should be small and dense, but if we can't use one of the more specialized containers for some reason, it's fine to stick with std::map.)

clang/lib/AST/ASTContext.cpp

120 ↗

(On Diff #230678)

Because N is const, does its get<> method return a const pointer? If so, switch to const auto * for clarity.

clang/lib/ASTMatchers/ASTMatchersInternal.cpp

222 ↗

(On Diff #230678)

raii -> RAII per naming conventions.

[steveire]

I tried using DenseMap, but couldn't make it compile. I stuck with std::map for now.

[ymandel]

include/clang/ASTMatchers/ASTMatchersInternal.h

286

Stephen -- What was the resolution on this comment? I came across this when writing my recent fixes and it stood out for going against the style guide and the surrounding style. Is this intentional or an oversight?

Thanks!

include/clang/AST/ASTContext.h

private:
   /// Address space map mangling must be used with language specific
   /// address spaces (e.g. OpenCL/CUDA)
   bool AddrSpaceMapMangling;
 
   const TargetInfo *Target = nullptr;
   const TargetInfo *AuxTarget = nullptr;
   clang::PrintingPolicy PrintingPolicy;
 
+  ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
+
 public:
+
+  ast_type_traits::TraversalKind GetTraversalKind() const { return Traversal; }
+  void SetTraversalKind(ast_type_traits::TraversalKind TK) { Traversal = TK; }
+
+  const Expr *TraverseIgnored(const Expr *E);
+  Expr *TraverseIgnored(Expr *E);
+  ast_type_traits::DynTypedNode
+  TraverseIgnored(const ast_type_traits::DynTypedNode &N);
+
   IdentifierTable &Idents;
   SelectorTable &Selectors;
   Builtin::Context &BuiltinInfo;
   mutable DeclarationNameTable DeclarationNames;
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener = nullptr;
 
   /// Container for either a single DynTypedNode or for an ArrayRef to
private:
 
   // FIXME: This currently contains the set of StoredDeclMaps used
   // by DeclContext objects.  This probably should not be in ASTContext,
   // but we include it here so that ASTContext can quickly deallocate them.
   llvm::PointerIntPair<StoredDeclsMap *, 1> LastSDM;
 
   std::vector<Decl *> TraversalScope;
   class ParentMap;
-  std::unique_ptr<ParentMap> Parents;
+  std::map<ast_type_traits::TraversalKind, std::unique_ptr<ParentMap>> Parents;
 
   std::unique_ptr<VTableContextBase> VTContext;
 
   void ReleaseDeclContextMaps();
 
 public:
   enum PragmaSectionFlag : unsigned {
     PSF_None = 0,

include/clang/AST/ASTNodeTraverser.h

: public ConstDeclVisitor<Derived>,
       public TypeVisitor<Derived>,
       public ConstAttrVisitor<Derived>,
       public ConstTemplateArgumentVisitor<Derived> {
 
   /// Indicates whether we should trigger deserialization of nodes that had
   /// not already been loaded.
   bool Deserialize = false;
 
+  ast_type_traits::TraversalKind Traversal = ast_type_traits::TraversalKind::TK_AsIs;
+
   NodeDelegateType &getNodeDelegate() {
     return getDerived().doGetNodeDelegate();
   }
   Derived &getDerived() { return *static_cast<Derived *>(this); }
 
 public:
   void setDeserialize(bool D) { Deserialize = D; }
   bool getDeserialize() const { return Deserialize; }
 
+  void SetTraversalKind(ast_type_traits::TraversalKind TK)
+  {
+    Traversal = TK;
+  }
+
   void Visit(const Decl *D) {
     getNodeDelegate().AddChild([=] {
       getNodeDelegate().Visit(D);
       if (!D)
         return;
 
       ConstDeclVisitor<Derived>::Visit(D);
 
       for (const auto &A : D->attrs())
         Visit(A);
 
       if (const comments::FullComment *Comment =
               D->getASTContext().getLocalCommentForDeclUncached(D))
         Visit(Comment, Comment);
 
       // Decls within functions are visited by the body.
       if (!isa<FunctionDecl>(*D) && !isa<ObjCMethodDecl>(*D)) {
         if (const auto *DC = dyn_cast<DeclContext>(D))
           dumpDeclContext(DC);
       }
     });
   }
 
-  void Visit(const Stmt *S, StringRef Label = {}) {
+  void Visit(const Stmt *S_, StringRef Label = {}) {
     getNodeDelegate().AddChild(Label, [=] {
+
+      const Stmt *S = S_;
+
+      if (auto* E = dyn_cast_or_null<Expr>(S))
+      {
+        switch (Traversal)
+        {
+          case ast_type_traits::TK_AsIs:
+            break;
+          case ast_type_traits::TK_IgnoreImplicitCastsAndParentheses:
+            S = E->IgnoreParenImpCasts();
+            break;
+        }
+      }
+
       getNodeDelegate().Visit(S);
 
       if (!S) {
         return;
       }
 
       ConstStmtVisitor<Derived>::Visit(S);
 

include/clang/ASTMatchers/ASTMatchers.h

AST_POLYMORPHIC_SUPPORTED_TYPES(ClassTemplateSpecializationDecl,
                                     FunctionDecl),
     internal::Matcher<TemplateArgument>, InnerMatcher) {
   ArrayRef<TemplateArgument> List =
       internal::getTemplateSpecializationArgs(Node);
   return matchesFirstInRange(InnerMatcher, List.begin(), List.end(), Finder,
                              Builder);
 }
 
+/// Causes all nested matchers to be matched with the specified traversal kind
+///
+/// Given
+/// \code
+///   void foo()
+///   {
+///       int i = 3.0;
+///   }
+/// \endcode
+/// The matcher
+/// \code
+///   traverse(ast_type_traits::TK_IgnoreImplicitCastsAndParentheses,
+///     varDecl(hasInitializer(floatLiteral()))
+///   )
+/// \endcode
+/// matches the return statement with "ret" bound to "a".
+template<typename T>
+internal::Matcher<T>
+traverse(ast_type_traits::TraversalKind TK,
+    const internal::Matcher<T>& InnerMatcher) {
+  return internal::Matcher<T>(new internal::TraversalMatcher<T>(TK, InnerMatcher));
+}
+
 /// Matches expressions that match InnerMatcher after any implicit AST
 /// nodes are stripped off.
 ///
 /// Parentheses and explicit casts are not discarded.
 /// Given
 /// \code
 ///   class C {};
 ///   C a = C();

include/clang/ASTMatchers/ASTMatchersInternal.h

public:
   /// Returns true if \p DynNode can be matched.
   ///
   /// May bind \p DynNode to an ID via \p Builder, or recurse into
   /// the AST via \p Finder.
   virtual bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
                           ASTMatchFinder *Finder,
                           BoundNodesTreeBuilder *Builder) const = 0;
 };
 
 /// 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 DynMatcherInterface {
bool matchesChildOf(const T &Node,
     static_assert(std::is_base_of<Decl, T>::value ||
                   std::is_base_of<Stmt, T>::value ||
                   std::is_base_of<NestedNameSpecifier, T>::value ||
                   std::is_base_of<NestedNameSpecifierLoc, T>::value ||
                   std::is_base_of<TypeLoc, T>::value ||
                   std::is_base_of<QualType, T>::value,
                   "unsupported type for recursive matching");
     return matchesChildOf(ast_type_traits::DynTypedNode::create(Node),
+                          getASTContext(),
                           Matcher, Builder, Traverse, Bind);
   }
 
   template <typename T>
   bool matchesDescendantOf(const T &Node,
                            const DynTypedMatcher &Matcher,
                            BoundNodesTreeBuilder *Builder,
                            BindKind Bind) {
     static_assert(std::is_base_of<Decl, T>::value ||
                   std::is_base_of<Stmt, T>::value ||
                   std::is_base_of<NestedNameSpecifier, T>::value ||
                   std::is_base_of<NestedNameSpecifierLoc, T>::value ||
                   std::is_base_of<TypeLoc, T>::value ||
                   std::is_base_of<QualType, T>::value,
                   "unsupported type for recursive matching");
     return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node),
+                               getASTContext(),
                                Matcher, Builder, Bind);
   }
 
   // FIXME: Implement support for BindKind.
   template <typename T>
   bool matchesAncestorOf(const T &Node,
                          const DynTypedMatcher &Matcher,
                          BoundNodesTreeBuilder *Builder,
                          AncestorMatchMode MatchMode) {
     static_assert(std::is_base_of<Decl, T>::value ||
                       std::is_base_of<NestedNameSpecifierLoc, T>::value ||
                       std::is_base_of<Stmt, T>::value ||
                       std::is_base_of<TypeLoc, T>::value,
                   "type not allowed for recursive matching");
     return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node),
+                             getASTContext(),
                              Matcher, Builder, MatchMode);
   }
 
   virtual ASTContext &getASTContext() const = 0;
 
 protected:
   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
+                              ASTContext& Ctx,
                               const DynTypedMatcher &Matcher,
                               BoundNodesTreeBuilder *Builder,
                               ast_type_traits::TraversalKind Traverse,
                               BindKind Bind) = 0;
 
   virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
+                              ASTContext& Ctx,
                                    const DynTypedMatcher &Matcher,
                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) = 0;
 
   virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
+                              ASTContext& Ctx,
                                  const DynTypedMatcher &Matcher,
                                  BoundNodesTreeBuilder *Builder,
                                  AncestorMatchMode MatchMode) = 0;
 };
 
 /// A type-list implementation.
 ///
 /// A "linked list" of types, accessible by using the ::head and ::tail
struct ArgumentAdaptingMatcherFunc {
   }
 
   template <typename T>
   Adaptor<T> operator()(const Matcher<T> &InnerMatcher) const {
     return create(InnerMatcher);
   }
 };
 
+template <typename T>
+class TraversalMatcher : public WrapperMatcherInterface<T> {
+  ast_type_traits::TraversalKind Traversal;
+public:
+  explicit TraversalMatcher(
+    ast_type_traits::TraversalKind TK,
+    const Matcher<T> &ChildMatcher)
+      : TraversalMatcher::WrapperMatcherInterface(ChildMatcher),
+        Traversal(TK) {}
+
+  bool matches(const T &Node, ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const override {
+    auto PrevTK = Finder->getASTContext().GetTraversalKind();
+    Finder->getASTContext().SetTraversalKind(Traversal);
+    auto Result = this->InnerMatcher.matches(
+      ast_type_traits::DynTypedNode::create(Node),
+      Finder, Builder);
+    Finder->getASTContext().SetTraversalKind(PrevTK);
+    return Result;
+  }
+};
+
 /// A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be
 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and
 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN)
 /// can be constructed.
 ///
 /// For example:
 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>()
 ///   creates an object that can be used as a Matcher<T> for any type T

lib/AST/ASTContext.cpp

 #include <utility>
 
 using namespace clang;
 
 enum FloatingRank {
   Float16Rank, HalfRank, FloatRank, DoubleRank, LongDoubleRank, Float128Rank
 };
 
+const Expr *ASTContext::TraverseIgnored(const Expr *E) {
+  return TraverseIgnored(const_cast<Expr*>(E));
+}
+
+Expr *ASTContext::TraverseIgnored(Expr *E) {
+  if (!E)
+    return nullptr;
+
+  switch(Traversal) {
+  case ast_type_traits::TK_AsIs:
+    return E;
+  case ast_type_traits::TK_IgnoreImplicitCastsAndParentheses:
+    return E->IgnoreParenImpCasts();
+  }
+  llvm_unreachable("Invalid Traversal type!");
+}
+
+ast_type_traits::DynTypedNode
+ASTContext::TraverseIgnored(const ast_type_traits::DynTypedNode &N) {
+  if (auto E = N.get<Expr>()) {
+    return ast_type_traits::DynTypedNode::create(*TraverseIgnored(E));
+  }
+  return N;
+}
+
 RawComment *ASTContext::getRawCommentForDeclNoCache(const Decl *D) const {
   assert(D);
 
   // If we already tried to load comments but there are none,
   // we won't find anything.
   if (CommentsLoaded && Comments.getComments().empty())
     return nullptr;
 
DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node) {
     if (Node.getNodeKind().hasPointerIdentity())
       return getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
     return getDynNodeFromMap(Node, OtherParents);
   }
 };
 
 void ASTContext::setTraversalScope(const std::vector<Decl *> &TopLevelDecls) {
   TraversalScope = TopLevelDecls;
-  Parents.reset();
+  Parents.clear();
 }
 
 void ASTContext::AddDeallocation(void (*Callback)(void*), void *Data) {
   Deallocations.push_back({Callback, Data});
 }
 
 void
 ASTContext::setExternalSource(IntrusiveRefCntPtr<ExternalASTSource> Source) {

 /// Note that the relationship described here is purely in terms of AST
 /// traversal - there are other relationships (for example declaration context)
 /// in the AST that are better modeled by special matchers.
 ///
 /// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes.
 class ASTContext::ParentMap::ASTVisitor
     : public RecursiveASTVisitor<ASTVisitor> {
 public:
-  ASTVisitor(ParentMap &Map) : Map(Map) {}
+  ASTVisitor(ParentMap &Map, ASTContext& Context)
+      : Map(Map), Context(Context) {}
 
 private:
   friend class RecursiveASTVisitor<ASTVisitor>;
 
   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
 
   bool shouldVisitTemplateInstantiations() const { return true; }
 
private:
 
   bool TraverseDecl(Decl *DeclNode) {
     return TraverseNode(
         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
         &Map.PointerParents);
   }
 
   bool TraverseStmt(Stmt *StmtNode) {
-    return TraverseNode(
-        StmtNode, StmtNode, [&] { return VisitorBase::TraverseStmt(StmtNode); },
+    auto FilteredNode = StmtNode;
+    if (auto* ExprNode = dyn_cast_or_null<Expr>(FilteredNode))
+      FilteredNode = Context.TraverseIgnored(ExprNode);
+    return TraverseNode(FilteredNode, FilteredNode,
+                        [&] { return VisitorBase::TraverseStmt(FilteredNode); },
                         &Map.PointerParents);
   }
 
   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
     return TraverseNode(
         TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode),
         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
         &Map.OtherParents);
   }
 
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
     return TraverseNode(
         NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode),
         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
         &Map.OtherParents);
   }
 
   ParentMap &Map;
+  ASTContext& Context;
   llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
 };
 
 ASTContext::ParentMap::ParentMap(ASTContext &Ctx) {
-  ASTVisitor(*this).TraverseAST(Ctx);
+  ASTVisitor(*this, Ctx).TraverseAST(Ctx);
 }
 
 ASTContext::DynTypedNodeList
 ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
-  if (!Parents)
+  std::unique_ptr<ParentMap>& P = Parents[Traversal];
+  if (!P)
     // We build the parent map for the traversal scope (usually whole TU), as
     // hasAncestor can escape any subtree.
-    Parents = llvm::make_unique<ParentMap>(*this);
-  return Parents->getParents(Node);
+    P = llvm::make_unique<ParentMap>(*this);
+  return P->getParents(Node);
 }
 
 bool
 ASTContext::ObjCMethodsAreEqual(const ObjCMethodDecl *MethodDecl,
                                 const ObjCMethodDecl *MethodImpl) {
   // No point trying to match an unavailable/deprecated mothod.
   if (MethodDecl->hasAttr<UnavailableAttr>()
       || MethodDecl->hasAttr<DeprecatedAttr>())

lib/ASTMatchers/ASTMatchFinder.cpp

 // For \c QualType and \c TypeLoc it is possible to implement
 // generation of keys for each type.
 // FIXME: Benchmark whether memoization of non-pointer typed nodes
 // provides enough benefit for the additional amount of code.
 struct MatchKey {
   DynTypedMatcher::MatcherIDType MatcherID;
   ast_type_traits::DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
+  ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
 
   bool operator<(const MatchKey &Other) const {
-    return std::tie(MatcherID, Node, BoundNodes) <
-           std::tie(Other.MatcherID, Other.Node, Other.BoundNodes);
+    return std::tie(MatcherID, Node, BoundNodes, Traversal) <
+           std::tie(Other.MatcherID, Other.Node, Other.BoundNodes, Other.Traversal);
   }
 };
 
 // Used to store the result of a match and possibly bound nodes.
 struct MemoizedMatchResult {
   bool ResultOfMatch;
   BoundNodesTreeBuilder Nodes;
 };
public:
   }
   bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
     // If we need to keep track of the depth, we can't perform data recursion.
     if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
       Queue = nullptr;
 
     ScopedIncrement ScopedDepth(&CurrentDepth);
     Stmt *StmtToTraverse = StmtNode;
+    if (Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode))
+      StmtToTraverse = Finder->getASTContext().TraverseIgnored(ExprNode);
     if (Traversal == ast_type_traits::TraversalKind::TK_IgnoreImplicitCastsAndParentheses) {
       if (Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode))
         StmtToTraverse = ExprNode->IgnoreParenImpCasts();
     }
     if (!StmtToTraverse)
       return true;
     if (!match(*StmtToTraverse))
       return false;
public:
   bool TraverseType(QualType TypeNode);
   bool TraverseTypeLoc(TypeLoc TypeNode);
   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
+                                  ASTContext& Ctx,
                                   const DynTypedMatcher &Matcher,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   ast_type_traits::TraversalKind Traversal, BindKind Bind) {
     // For AST-nodes that don't have an identity, we can't memoize.
     if (!Node.getMemoizationData() || !Builder->isComparable())
       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
                                 Bind);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     // Note that we key on the bindings *before* the match.
     Key.BoundNodes = *Builder;
+    Key.Traversal = Ctx.GetTraversalKind();
 
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
public:
   }
 
   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
                           const Matcher<NamedDecl> &Base,
                           BoundNodesTreeBuilder *Builder) override;
 
   // Implements ASTMatchFinder::matchesChildOf.
   bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
+                      ASTContext& Ctx,
                       const DynTypedMatcher &Matcher,
                       BoundNodesTreeBuilder *Builder,
                       ast_type_traits::TraversalKind Traversal,
                       BindKind Bind) override {
     if (ResultCache.size() > MaxMemoizationEntries)
       ResultCache.clear();
-    return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
+    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Traversal,
                                       Bind);
   }
   // Implements ASTMatchFinder::matchesDescendantOf.
   bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
+                           ASTContext& Ctx,
                            const DynTypedMatcher &Matcher,
                            BoundNodesTreeBuilder *Builder,
                            BindKind Bind) override {
     if (ResultCache.size() > MaxMemoizationEntries)
       ResultCache.clear();
-    return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
+    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
                                       ast_type_traits::TraversalKind::TK_AsIs, Bind);
   }
   // Implements ASTMatchFinder::matchesAncestorOf.
   bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
+                         ASTContext& Ctx,
                          const DynTypedMatcher &Matcher,
                          BoundNodesTreeBuilder *Builder,
                          AncestorMatchMode MatchMode) override {
     // Reset the cache outside of the recursive call to make sure we
     // don't invalidate any iterators.
     if (ResultCache.size() > MaxMemoizationEntries)
       ResultCache.clear();
-    return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
+    return memoizedMatchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
                                                 MatchMode);
   }
 
   // Matches all registered matchers on the given node and calls the
   // result callback for every node that matches.
   void match(const ast_type_traits::DynTypedNode &Node) {
     // FIXME: Improve this with a switch or a visitor pattern.
     if (auto *N = Node.get<Decl>()) {
private:
   // expressions inside a template function, we first walk up the AST, memoizing
   // the result of the match along the way, as long as there is only a single
   // parent.
   //
   // Once there are multiple parents, the breadth first search order does not
   // allow simple memoization on the ancestors. Thus, we only memoize as long
   // as there is a single parent.
   bool memoizedMatchesAncestorOfRecursively(
-      const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
+      const ast_type_traits::DynTypedNode &Node,
+      ASTContext& Ctx,
+      const DynTypedMatcher &Matcher,
       BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
     // For AST-nodes that don't have an identity, we can't memoize.
     if (!Builder->isComparable())
-      return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
+      return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder, MatchMode);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
+    Key.Traversal = Ctx.GetTraversalKind();
 
     // Note that we cannot use insert and reuse the iterator, as recursive
     // calls to match might invalidate the result cache iterators.
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
     Result.Nodes = *Builder;
     Result.ResultOfMatch =
-        matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode);
+        matchesAncestorOfRecursively(Node, Ctx, Matcher, &Result.Nodes, MatchMode);
 
     MemoizedMatchResult &CachedResult = ResultCache[Key];
     CachedResult = std::move(Result);
 
     *Builder = CachedResult.Nodes;
     return CachedResult.ResultOfMatch;
   }
 
   bool matchesAncestorOfRecursively(const ast_type_traits::DynTypedNode &Node,
+                                    ASTContext& Ctx,
                                     const DynTypedMatcher &Matcher,
                                     BoundNodesTreeBuilder *Builder,
                                     AncestorMatchMode MatchMode) {
     const auto &Parents = ActiveASTContext->getParents(Node);
     if (Parents.empty()) {
       // Nodes may have no parents if:
       //  a) the node is the TranslationUnitDecl
       //  b) we have a limited traversal scope that excludes the parent edges
if (Parents.size() == 1) {
       // Only one parent - do recursive memoization.
       const ast_type_traits::DynTypedNode Parent = Parents[0];
       BoundNodesTreeBuilder BuilderCopy = *Builder;
       if (Matcher.matches(Parent, this, &BuilderCopy)) {
         *Builder = std::move(BuilderCopy);
         return true;
       }
       if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
-        return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder,
+        return memoizedMatchesAncestorOfRecursively(Parent, Ctx, Matcher, Builder,
                                                     MatchMode);
         // Once we get back from the recursive call, the result will be the
         // same as the parent's result.
       }
     } else {
       // Multiple parents - BFS over the rest of the nodes.
       llvm::DenseSet<const void *> Visited;
       std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),

lib/ASTMatchers/ASTMatchersInternal.cpp

DynTypedMatcher DynTypedMatcher::dynCastTo(
   Copy.RestrictKind =
       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
   return Copy;
 }
 
 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
                               ASTMatchFinder *Finder,
                               BoundNodesTreeBuilder *Builder) const {
-  if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
-      Implementation->dynMatches(DynNode, Finder, Builder)) {
+  auto N = Finder->getASTContext().TraverseIgnored(DynNode);
+  auto NodeKind = N.getNodeKind();
+
+  if (RestrictKind.isBaseOf(NodeKind) &&
+      Implementation->dynMatches(N, Finder, Builder)) {
     return true;
   }
   // Delete all bindings when a matcher does not match.
   // This prevents unexpected exposure of bound nodes in unmatches
   // branches of the match tree.
   Builder->removeBindings([](const BoundNodesMap &) { return true; });
   return false;
 }
 
 bool DynTypedMatcher::matchesNoKindCheck(
     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
     BoundNodesTreeBuilder *Builder) const {
-  assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
-  if (Implementation->dynMatches(DynNode, Finder, Builder)) {
+  auto N = Finder->getASTContext().TraverseIgnored(DynNode);
+  auto NodeKind = N.getNodeKind();
+
+  assert(RestrictKind.isBaseOf(NodeKind));
+  if (Implementation->dynMatches(N, Finder, Builder)) {
     return true;
   }
   // Delete all bindings when a matcher does not match.
   // This prevents unexpected exposure of bound nodes in unmatches
   // branches of the match tree.
   Builder->removeBindings([](const BoundNodesMap &) { return true; });
   return false;
 }
 

unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

)";
   ));
 }
 
 TEST(IgnoringImplicit, DoesNotMatchIncorrectly) {
   EXPECT_TRUE(
       notMatches("class C {}; C a = C();", varDecl(has(cxxConstructExpr()))));
 }
 
+TEST(Traversal, traverseMatcher) {
+
+  StringRef VarDeclCode = R"cpp(
+void foo()
+{
+  int i = 3.0;
+}
+)cpp";
+
+  auto Matcher = varDecl(hasInitializer(floatLiteral()));
+
+  EXPECT_TRUE(notMatches(
+    VarDeclCode,
+    traverse(ast_type_traits::TK_AsIs,
+      Matcher
+      )
+  ));
+  EXPECT_TRUE(matches(
+    VarDeclCode,
+    traverse(ast_type_traits::TK_IgnoreImplicitCastsAndParentheses,
+      Matcher
+      )
+  ));
+}
+
+TEST(Traversal, traverseMatcherNesting) {
+
+  StringRef Code = R"cpp(
+float bar(int i)
+{
+  return i;
+}
+
+void foo()
+{
+  bar(bar(3.0));
+}
+)cpp";
+
+  EXPECT_TRUE(matches(
+    Code,
+    traverse(ast_type_traits::TK_IgnoreImplicitCastsAndParentheses,
+      callExpr(has(
+        callExpr(
+          traverse(ast_type_traits::TK_AsIs,
+            callExpr(has(implicitCastExpr(has(floatLiteral()))))
+            )
+          )
+        ))
+      )
+  ));
+}
+
+TEST(Traversal, traverseMatcherThroughMemoization) {
+
+  StringRef Code = R"cpp(
+void foo()
+{
+  int i = 3.0;
+}
+  )cpp";
+
+  auto Matcher = varDecl(hasInitializer(floatLiteral()));
+
+  // Matchers such as hasDescendant memoize their result regarding AST
+  // nodes. In the matcher below, the first use of hasDescendant(Matcher)
+  // fails, and the use of it inside the traverse() matcher should pass
+  // causing the overall matcher to be a true match.
+  // This test verifies that the first false result is not re-used, which
+  // would cause the overall matcher to be incorrectly false.
+
+  EXPECT_TRUE(
+    matches(
+    Code,
+    functionDecl(anyOf(
+      hasDescendant(
+        Matcher
+        ),
+      traverse(ast_type_traits::TK_IgnoreImplicitCastsAndParentheses,
+        functionDecl(
+          hasDescendant(
+            Matcher
+            )
+          )
+        )
+      ))
+    )
+  );
+}
+
 TEST(IgnoringImpCasts, MatchesImpCasts) {
   // This test checks that ignoringImpCasts matches when implicit casts are
   // present and its inner matcher alone does not match.
   // Note that this test creates an implicit const cast.
   EXPECT_TRUE(matches("int x = 0; const int y = x;",
                       varDecl(hasInitializer(ignoringImpCasts(
                         declRefExpr(to(varDecl(hasName("x")))))))));
   // This test creates an implict cast from int to char.