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 ↗

(On Diff #199185)

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

565–568 ↗

(On Diff #199185)

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

include/clang/AST/ASTNodeTraverser.h

80 ↗

(On Diff #199185)

setTraversalKind()

105 ↗

(On Diff #199185)

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

113–114 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

Missing a full stop at the end of the comment.

716 ↗

(On Diff #199185)

Copy pasta?

718 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

traversalKind()

287 ↗

(On Diff #199185)

return llvm::None;

lib/AST/ASTContext.cpp

120 ↗

(On Diff #199185)

auto *

10358 ↗

(On Diff #199185)

Stmt *

lib/ASTMatchers/ASTMatchFinder.cpp

148 ↗

(On Diff #199185)

auto *

lib/ASTMatchers/ASTMatchersInternal.cpp

214–215 ↗

(On Diff #199185)

Please do not use auto here.

218–219 ↗

(On Diff #199185)

Or here...

237–238 ↗

(On Diff #199185)

Or here...

240 ↗

(On Diff #199185)

Add an assertion message?

[steveire]

Update

include/clang/AST/ASTContext.h

562–563 ↗

(On Diff #199185)

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

565–568 ↗

(On Diff #199185)

It looks like they can be const.

include/clang/ASTMatchers/ASTMatchers.h

718 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

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 ↗

(On Diff #199185)

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

240 ↗

(On Diff #199185)

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

[aaron.ballman]

lib/AST/ASTContext.cpp

120 ↗

(On Diff #199185)

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

lib/ASTMatchers/ASTMatchersInternal.cpp

240 ↗

(On Diff #199185)

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

240 ↗

(On Diff #199185)

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

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

121

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–228

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 ↗

(On Diff #199185)

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!

clang/include/clang/AST/ASTContext.h

private:
   /// address spaces (e.g. OpenCL/CUDA)
   bool AddrSpaceMapMangling;
 
   const TargetInfo *Target = nullptr;
   const TargetInfo *AuxTarget = nullptr;
   clang::PrintingPolicy PrintingPolicy;
   std::unique_ptr<interp::Context> InterpContext;
 
+  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) const;
+  Expr *traverseIgnored(Expr *E) const;
+  ast_type_traits::DynTypedNode
+  traverseIgnored(const ast_type_traits::DynTypedNode &N) const;
+
   IdentifierTable &Idents;
   SelectorTable &Selectors;
   Builtin::Context &BuiltinInfo;
   mutable DeclarationNameTable DeclarationNames;
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener = nullptr;
 
   /// Returns the clang bytecode interpreter context.
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,

 }
 
 /// Utility function for constructing an unary selector.
 inline Selector GetUnarySelector(StringRef name, ASTContext &Ctx) {
   IdentifierInfo* II = &Ctx.Idents.get(name);
   return Ctx.Selectors.getSelector(1, &II);
 }
 
+class TraversalKindScope {
+  ASTContext &Ctx;
+  ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs;
+
+public:
+  TraversalKindScope(ASTContext &Ctx,
+                     llvm::Optional<ast_type_traits::TraversalKind> ScopeTK)
+      : Ctx(Ctx) {
+    TK = Ctx.getTraversalKind();
+    if (ScopeTK)
+      Ctx.setTraversalKind(*ScopeTK);
+  }
+
+  ~TraversalKindScope() { Ctx.setTraversalKind(TK); }
+};
+
 } // namespace clang
 
 // operator new and delete aren't allowed inside namespaces.
 
 /// Placement new for using the ASTContext's allocator.
 ///
 /// This placement form of operator new uses the ASTContext's allocator for
 /// obtaining memory.

clang/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 *Node, StringRef Label = {}) {
     getNodeDelegate().AddChild(Label, [=] {
+      const Stmt *S = Node;
+
+      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);
 

clang/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().bind("init")))
+///   )
+/// \endcode
+/// matches the variable declaration with "init" bound to the "3.0".
+template <typename T>
+internal::Matcher<T> traverse(ast_type_traits::TraversalKind TK,
+                              const internal::Matcher<T> &InnerMatcher) {
+  return internal::DynTypedMatcher::constructRestrictedWrapper(
+             new internal::TraversalMatcher<T>(TK, InnerMatcher),
+             InnerMatcher.getID().first)
+      .template unconditionalConvertTo<T>();
+}
+
 /// 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();

clang/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;
+
+  virtual llvm::Optional<ast_type_traits::TraversalKind> TraversalKind() const {
+    return llvm::None;
+  }
 };
 
 /// 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,
enum VariadicOperator {
     VO_UnaryNot
   };
 
   static DynTypedMatcher
   constructVariadic(VariadicOperator Op,
                     ast_type_traits::ASTNodeKind SupportedKind,
                     std::vector<DynTypedMatcher> InnerMatchers);
 
+  static DynTypedMatcher
+  constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,
+                             ast_type_traits::ASTNodeKind RestrictKind);
+
   /// Get a "true" matcher for \p NodeKind.
   ///
   /// It only checks that the node is of the right kind.
   static DynTypedMatcher trueMatcher(ast_type_traits::ASTNodeKind NodeKind);
 
   void setAllowBind(bool AB) { AllowBind = AB; }
 
   /// Check whether this matcher could ever match a node of kind \p Kind.
bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher,
     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),
-                          Matcher, Builder, Traverse, Bind);
+                          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),
-                               Matcher, Builder, Bind);
+                               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),
-                             Matcher, Builder, MatchMode);
+                             getASTContext(), Matcher, Builder, MatchMode);
   }
 
   virtual ASTContext &getASTContext() const = 0;
 
 protected:
   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
-                              const DynTypedMatcher &Matcher,
+                              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 {
+    return this->InnerMatcher.matches(
+        ast_type_traits::DynTypedNode::create(Node), Finder, Builder);
+  }
+
+  llvm::Optional<ast_type_traits::TraversalKind>
+  TraversalKind() const override {
+    return Traversal;
+  }
+};
+
 /// 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

clang/lib/AST/ASTContext.cpp

 #include <tuple>
 #include <utility>
 
 using namespace clang;
 
 enum FloatingRank {
   Float16Rank, HalfRank, FloatRank, DoubleRank, LongDoubleRank, Float128Rank
 };
+const Expr *ASTContext::traverseIgnored(const Expr *E) const {
+  return traverseIgnored(const_cast<Expr *>(E));
+}
+
+Expr *ASTContext::traverseIgnored(Expr *E) const {
+  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) const {
+  if (const auto *E = N.get<Expr>()) {
+    return ast_type_traits::DynTypedNode::create(*traverseIgnored(E));
+  }
+  return N;
+}
 
 /// \returns location that is relevant when searching for Doc comments related
 /// to \p D.
 static SourceLocation getDeclLocForCommentSearch(const Decl *D,
                                                  SourceManager &SourceMgr) {
   assert(D);
 
   // User can not attach documentation to implicit declarations.
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) const {
   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); },
+    Stmt *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 = std::make_unique<ParentMap>(*this);
-  return Parents->getParents(Node);
+    P = std::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>())

clang/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 (auto *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))
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 objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
                               const Matcher<NamedDecl> &Base,
                               BoundNodesTreeBuilder *Builder,
                               bool Directly) override;
 
   // Implements ASTMatchFinder::matchesChildOf.
   bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
-                      const DynTypedMatcher &Matcher,
+                      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,
-                           const DynTypedMatcher &Matcher,
+                           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,
-                         const DynTypedMatcher &Matcher,
+                         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>()) {
void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
     const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
     TimeBucketRegion Timer;
     auto &Matchers = this->Matchers->DeclOrStmt;
     for (unsigned short I : Filter) {
       auto &MP = Matchers[I];
       if (EnableCheckProfiling)
         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
       BoundNodesTreeBuilder Builder;
-      if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
+      if (MP.first.matches(DynNode, this, &Builder)) {
         MatchVisitor Visitor(ActiveASTContext, MP.second);
         Builder.visitMatches(&Visitor);
       }
     }
   }
 
   const std::vector<unsigned short> &
   getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
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,
-      BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
+      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);
+    Result.ResultOfMatch = 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,
-                                                    MatchMode);
+        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(),
                                                       Parents.end());
#endif
   const MatchFinder::MatchersByType *Matchers;
 
   /// Filtered list of matcher indices for each matcher kind.
   ///
   /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
   /// kind (and derived kinds) so it is a waste to try every matcher on every
   /// node.
   /// We precalculate a list of matchers that pass the toplevel restrict check.
-  /// This also allows us to skip the restrict check at matching time. See
-  /// use \c matchesNoKindCheck() above.
   llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
       MatcherFiltersMap;
 
   const MatchFinder::MatchFinderOptions &Options;
   ASTContext *ActiveASTContext;
 
   // Maps a canonical type to its TypedefDecls.
   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;

clang/lib/ASTMatchers/ASTMatchersInternal.cpp

case VO_UnaryNot:
     // vector.
     return DynTypedMatcher(
         SupportedKind, RestrictKind,
         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
   }
   llvm_unreachable("Invalid Op value.");
 }
 
+DynTypedMatcher DynTypedMatcher::constructRestrictedWrapper(
+    const DynTypedMatcher &InnerMatcher,
+    ast_type_traits::ASTNodeKind RestrictKind) {
+  DynTypedMatcher Copy = InnerMatcher;
+  Copy.RestrictKind = RestrictKind;
+  return Copy;
+}
+
 DynTypedMatcher DynTypedMatcher::trueMatcher(
     ast_type_traits::ASTNodeKind NodeKind) {
   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
 }
 
 bool DynTypedMatcher::canMatchNodesOfKind(
     ast_type_traits::ASTNodeKind Kind) const {
   return RestrictKind.isBaseOf(Kind);
 }
 
 DynTypedMatcher DynTypedMatcher::dynCastTo(
     const ast_type_traits::ASTNodeKind Kind) const {
   auto Copy = *this;
   Copy.SupportedKind = Kind;
   Copy.RestrictKind =
       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
   return Copy;
 }
 
 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
                               ASTMatchFinder *Finder,
                               BoundNodesTreeBuilder *Builder) const {
-  if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
-      Implementation->dynMatches(DynNode, Finder, Builder)) {
+  TraversalKindScope RAII(Finder->getASTContext(),
+                          Implementation->TraversalKind());
+
+  auto N = Finder->getASTContext().traverseIgnored(DynNode);
+
+  if (RestrictKind.isBaseOf(N.getNodeKind()) &&
+      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)) {
+  TraversalKindScope raii(Finder->getASTContext(),
+                          Implementation->TraversalKind());
+
+  auto N = Finder->getASTContext().traverseIgnored(DynNode);
+
+  assert(RestrictKind.isBaseOf(N.getNodeKind()));
+  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;
 }

clang/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, traverseMatcherThroughImplicit) {
+  StringRef Code = R"cpp(
+struct S {
+  S(int x);
+};
+
+void constructImplicit() {
+  int a = 8;
+  S s(a);
+}
+  )cpp";
+
+  auto Matcher = traverse(ast_type_traits::TK_IgnoreImplicitCastsAndParentheses,
+                          implicitCastExpr());
+
+  // Verfiy that it does not segfault
+  EXPECT_FALSE(matches(Code, Matcher));
+}
+
+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.