[AST] Split parent map traversal logic into ParentMapContext.h

[rnk]

Summary

The only part of ASTContext.h that requires most AST types to be
complete is the parent map. Nothing in Clang proper uses the ParentMap,
so split it out into its own class. Make ASTContext own the
ParentMapContext so there is still a one-to-one relationship.

After this change, 562 fewer files depend on ASTTypeTraits.h, and 66
fewer depend on TypeLoc.h:

$ diff -u deps-before.txt deps-after.txt | \
  grep '^[-+] ' | sort | uniq -c | sort -nr | less
    562 -    ../clang/include/clang/AST/ASTTypeTraits.h
    340 +    ../clang/include/clang/AST/ParentMapContext.h
     66 -    ../clang/include/clang/AST/TypeLocNodes.def
     66 -    ../clang/include/clang/AST/TypeLoc.h
     15 -    ../clang/include/clang/AST/TemplateBase.h
...

I computed deps-before.txt and deps-after.txt with ninja -t deps.

This removes a common and key dependency on TemplateBase.h and
TypeLoc.h.

This also has the effect of breaking the ParentMap RecursiveASTVisitor
instantiation into its own file, which roughly halves the compilation
time of ASTContext.cpp (29.75s -> 17.66s). The new file takes 13.8s to
compile.

I left behind forwarding methods for getParents(), but clients will need
to include a new header to make them work:

#include "clang/AST/ParentMapContext.h"

I noticed that this parent map functionality is unfortunately duplicated
in ParentMap.h, which only works for Stmt nodes.

[rnk]

clang/include/clang/AST/ASTContext.h

666

Turns out this only worked for me locally because of delayed template parsing. I will have to think harder about how to preserve the API while not requiring complete types here. I could make an overload set, but I worry it will be inconveniently large.

[rnk]

• Move things around while retaining API compatibility for getParents

[rnk]

I think I can land this version, but I'll wait until tomorrow so I'll be around to debug fallout.

[steveire]

Should this new class have some tests?

clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp

 //===--- ProBoundsArrayToPointerDecayCheck.cpp - clang-tidy----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ProBoundsArrayToPointerDecayCheck.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace cppcoreguidelines {
 
return stmt(hasAncestor(cxxForRangeStmt(
                   hasRangeBeginEndStmt(hasDescendant(equalsNode(&Node))))))
       .matches(Node, Finder, Builder);
 }
 
 AST_MATCHER_P(Expr, hasParentIgnoringImpCasts,
               ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
   const Expr *E = &Node;
   do {
-    ASTContext::DynTypedNodeList Parents =
-        Finder->getASTContext().getParents(*E);
+    DynTypedNodeList Parents = Finder->getASTContext().getParents(*E);
     if (Parents.size() != 1)
       return false;
     E = Parents[0].get<Expr>();
     if (!E)
       return false;
   } while (isa<ImplicitCastExpr>(E));
 
   return InnerMatcher.matches(*E, Finder, Builder);

clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp

 //===--- MakeMemberFunctionConstCheck.cpp - clang-tidy --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "MakeMemberFunctionConstCheck.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace readability {

 class FindUsageOfThis : public RecursiveASTVisitor<FindUsageOfThis> {
   ASTContext &Ctxt;
 
 public:
   FindUsageOfThis(ASTContext &Ctxt) : Ctxt(Ctxt) {}
   UsageKind Usage = Unused;
 
   template <class T> const T *getParent(const Expr *E) {
-    ASTContext::DynTypedNodeList Parents = Ctxt.getParents(*E);
+    DynTypedNodeList Parents = Ctxt.getParents(*E);
     if (Parents.size() != 1)
       return nullptr;
 
     return Parents.begin()->get<T>();
   }
 
   bool VisitUnresolvedMemberExpr(const UnresolvedMemberExpr *) {
     // An UnresolvedMemberExpr might resolve to a non-const non-static

clang-tools-extra/clang-tidy/utils/ExprSequence.cpp

 // nodes cause ASTContext::getParent() to return multiple parents for certain
 // nodes in their subtree because RecursiveASTVisitor visits both the syntactic
 // and semantic forms of InitListExpr, and the parent-child relationships are
 // different between the two forms.
 static SmallVector<const Stmt *, 1> getParentStmts(const Stmt *S,
                                                    ASTContext *Context) {
   SmallVector<const Stmt *, 1> Result;
 
-  ASTContext::DynTypedNodeList Parents = Context->getParents(*S);
+  DynTypedNodeList Parents = Context->getParents(*S);
 
   SmallVector<ast_type_traits::DynTypedNode, 1> NodesToProcess(Parents.begin(),
                                                                Parents.end());
 
   while (!NodesToProcess.empty()) {
     ast_type_traits::DynTypedNode Node = NodesToProcess.back();
     NodesToProcess.pop_back();
 

clang/include/clang/AST/ASTContext.h

 /// Defines the clang::ASTContext interface.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_ASTCONTEXT_H
 #define LLVM_CLANG_AST_ASTCONTEXT_H
 
 #include "clang/AST/ASTContextAllocate.h"
-#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/CanonicalType.h"
 #include "clang/AST/CommentCommandTraits.h"
 #include "clang/AST/ComparisonCategories.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/ExternalASTSource.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/RawCommentList.h"
-#include "clang/AST/TemplateBase.h"
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/AddressSpaces.h"
 #include "clang/Basic/AttrKinds.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/Linkage.h"

 class BuiltinTemplateDecl;
 class CharUnits;
 class ConceptDecl;
 class CXXABI;
 class CXXConstructorDecl;
 class CXXMethodDecl;
 class CXXRecordDecl;
 class DiagnosticsEngine;
+class ParentMapContext;
+class DynTypedNodeList;
 class Expr;
 class FixedPointSemantics;
 class GlobalDecl;
 class MangleContext;
 class MangleNumberingContext;
 class MaterializeTemporaryExpr;
 class MemberSpecializationInfo;
 class Module;

 class TemplateTemplateParmDecl;
 class TemplateTypeParmDecl;
 class UnresolvedSetIterator;
 class UsingShadowDecl;
 class VarTemplateDecl;
 class VTableContextBase;
 struct BlockVarCopyInit;
 
+namespace ast_type_traits {
+class DynTypedNode;
+}
+
 namespace Builtin {
 
 class Context;
 
 } // namespace Builtin
 
 enum BuiltinTemplateKind : int;
 
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;
   std::unique_ptr<interp::Context> InterpContext;
-
-  ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
+  std::unique_ptr<ParentMapContext> ParentMapCtx;
 
 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.
   interp::Context &getInterpContext();
 
-  /// Container for either a single DynTypedNode or for an ArrayRef to
-  /// DynTypedNode. For use with ParentMap.
-  class DynTypedNodeList {
-    using DynTypedNode = ast_type_traits::DynTypedNode;
-
-    llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
-                                ArrayRef<DynTypedNode>> Storage;
-    bool IsSingleNode;
-
-  public:
-    DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
-      new (Storage.buffer) DynTypedNode(N);
-    }
-
-    DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
-      new (Storage.buffer) ArrayRef<DynTypedNode>(A);
-    }
-
-    const ast_type_traits::DynTypedNode *begin() const {
-      if (!IsSingleNode)
-        return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
-            ->begin();
-      return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
-    }
-
-    const ast_type_traits::DynTypedNode *end() const {
-      if (!IsSingleNode)
-        return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
-            ->end();
-      return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
-    }
-
-    size_t size() const { return end() - begin(); }
-    bool empty() const { return begin() == end(); }
-
-    const DynTypedNode &operator[](size_t N) const {
-      assert(N < size() && "Out of bounds!");
-      return *(begin() + N);
-    }
-  };
+  /// Returns the dynamic AST node parent map context.
+  ParentMapContext &getParentMapContext();
 
   // A traversal scope limits the parts of the AST visible to certain analyses.
   // RecursiveASTVisitor::TraverseAST will only visit reachable nodes, and
   // getParents() will only observe reachable parent edges.
   //
   // The scope is defined by a set of "top-level" declarations.
   // Initially, it is the entire TU: {getTranslationUnitDecl()}.
   // Changing the scope clears the parent cache, which is expensive to rebuild.
   std::vector<Decl *> getTraversalScope() const { return TraversalScope; }
   void setTraversalScope(const std::vector<Decl *> &);
 
-  /// Returns the parents of the given node (within the traversal scope).
-  ///
-  /// Note that this will lazily compute the parents of all nodes
-  /// and store them for later retrieval. Thus, the first call is O(n)
-  /// in the number of AST nodes.
-  ///
-  /// Caveats and FIXMEs:
-  /// Calculating the parent map over all AST nodes will need to load the
-  /// full AST. This can be undesirable in the case where the full AST is
-  /// expensive to create (for example, when using precompiled header
-  /// preambles). Thus, there are good opportunities for optimization here.
-  /// One idea is to walk the given node downwards, looking for references
-  /// to declaration contexts - once a declaration context is found, compute
-  /// the parent map for the declaration context; if that can satisfy the
-  /// request, loading the whole AST can be avoided. Note that this is made
-  /// more complex by statements in templates having multiple parents - those
-  /// problems can be solved by building closure over the templated parts of
-  /// the AST, which also avoids touching large parts of the AST.
-  /// Additionally, we will want to add an interface to already give a hint
-  /// where to search for the parents, for example when looking at a statement
-  /// inside a certain function.
-  ///
-  /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
-  /// NestedNameSpecifier or NestedNameSpecifierLoc.
-  template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node) {
-    return getParents(ast_type_traits::DynTypedNode::create(Node));
-  }
-
-  DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
+  /// Forwards to get node parents from the ParentMapContext. New callers should
+  /// use ParentMapContext::getParents() directly.
+  template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
 
   const clang::PrintingPolicy &getPrintingPolicy() const {
     return PrintingPolicy;
   }
 
   void setPrintingPolicy(const clang::PrintingPolicy &Policy) {
     PrintingPolicy = Policy;
   }
private:
   mutable DeallocationFunctionsAndArguments Deallocations;
 
   // 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::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

 // of this class may make use of the same traversal logic by inheriting it,
 // similar to RecursiveASTVisitor.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_ASTNODETRAVERSER_H
 #define LLVM_CLANG_AST_ASTNODETRAVERSER_H
 
+#include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/AttrVisitor.h"
 #include "clang/AST/CommentVisitor.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/AST/LocInfoType.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/TemplateArgumentVisitor.h"
 #include "clang/AST/TypeVisitor.h"
 

clang/include/clang/AST/ParentMapContext.h

+//===- ParentMapContext.h - Map of parents using DynTypedNode -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have
+// multiple parents.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H
+#define LLVM_CLANG_AST_PARENTMAPCONTEXT_H
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+
+namespace clang {
+class DynTypedNodeList;
+
+class ParentMapContext {
+public:
+  ParentMapContext(ASTContext &Ctx);
+
+  ~ParentMapContext();
+
+  /// Returns the parents of the given node (within the traversal scope).
+  ///
+  /// Note that this will lazily compute the parents of all nodes
+  /// and store them for later retrieval. Thus, the first call is O(n)
+  /// in the number of AST nodes.
+  ///
+  /// Caveats and FIXMEs:
+  /// Calculating the parent map over all AST nodes will need to load the
+  /// full AST. This can be undesirable in the case where the full AST is
+  /// expensive to create (for example, when using precompiled header
+  /// preambles). Thus, there are good opportunities for optimization here.
+  /// One idea is to walk the given node downwards, looking for references
+  /// to declaration contexts - once a declaration context is found, compute
+  /// the parent map for the declaration context; if that can satisfy the
+  /// request, loading the whole AST can be avoided. Note that this is made
+  /// more complex by statements in templates having multiple parents - those
+  /// problems can be solved by building closure over the templated parts of
+  /// the AST, which also avoids touching large parts of the AST.
+  /// Additionally, we will want to add an interface to already give a hint
+  /// where to search for the parents, for example when looking at a statement
+  /// inside a certain function.
+  ///
+  /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
+  /// NestedNameSpecifier or NestedNameSpecifierLoc.
+  template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
+
+  DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
+
+  /// Clear parent maps.
+  void clear();
+
+  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;
+
+private:
+  ASTContext &ASTCtx;
+  class ParentMap;
+  ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
+  std::map<ast_type_traits::TraversalKind, std::unique_ptr<ParentMap>> Parents;
+};
+
+class TraversalKindScope {
+  ParentMapContext &Ctx;
+  ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs;
+
+public:
+  TraversalKindScope(ASTContext &ASTCtx,
+                     llvm::Optional<ast_type_traits::TraversalKind> ScopeTK)
+      : Ctx(ASTCtx.getParentMapContext()) {
+    TK = Ctx.getTraversalKind();
+    if (ScopeTK)
+      Ctx.setTraversalKind(*ScopeTK);
+  }
+
+  ~TraversalKindScope() { Ctx.setTraversalKind(TK); }
+};
+
+/// Container for either a single DynTypedNode or for an ArrayRef to
+/// DynTypedNode. For use with ParentMap.
+class DynTypedNodeList {
+  using DynTypedNode = ast_type_traits::DynTypedNode;
+
+  llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
+                              ArrayRef<DynTypedNode>> Storage;
+  bool IsSingleNode;
+
+public:
+  DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
+    new (Storage.buffer) DynTypedNode(N);
+  }
+
+  DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
+    new (Storage.buffer) ArrayRef<DynTypedNode>(A);
+  }
+
+  const ast_type_traits::DynTypedNode *begin() const {
+    if (!IsSingleNode)
+      return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
+          ->begin();
+    return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
+  }
+
+  const ast_type_traits::DynTypedNode *end() const {
+    if (!IsSingleNode)
+      return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
+          ->end();
+    return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
+  }
+
+  size_t size() const { return end() - begin(); }
+  bool empty() const { return begin() == end(); }
+
+  const DynTypedNode &operator[](size_t N) const {
+    assert(N < size() && "Out of bounds!");
+    return *(begin() + N);
+  }
+};
+
+template <typename NodeT>
+inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) {
+  return getParents(ast_type_traits::DynTypedNode::create(Node));
+}
+
+template <typename NodeT>
+inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) {
+  return getParentMapContext().getParents(Node);
+}
+
+template <>
+inline DynTypedNodeList
+ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
+  return getParentMapContext().getParents(Node);
+}
+
+} // namespace clang
+
+#endif

clang/include/clang/ASTMatchers/ASTMatchers.h

 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclFriend.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclTemplate.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ExprObjC.h"
 #include "clang/AST/LambdaCapture.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/OpenMPClause.h"
 #include "clang/AST/OperationKinds.h"
 #include "clang/AST/Stmt.h"

clang/include/clang/Sema/Sema.h

 // builds ASTs.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SEMA_SEMA_H
 #define LLVM_CLANG_SEMA_SEMA_H
 
 #include "clang/AST/ASTConcept.h"
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/Availability.h"
 #include "clang/AST/ComparisonCategories.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprConcepts.h"
 #include "clang/AST/ExprCXX.h"

clang/lib/AST/ASTContext.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclContextInternals.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclOpenMP.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/AST/ExprConcepts.h"
 #include "clang/AST/ExternalASTSource.h"
 #include "clang/AST/Mangle.h"
 #include "clang/AST/MangleNumberingContext.h"
 #include "clang/AST/NestedNameSpecifier.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/RawCommentList.h"
 #include "clang/AST/RecordLayout.h"
-#include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/TemplateBase.h"
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/AST/UnresolvedSet.h"
 #include "clang/AST/VTableBuilder.h"
 #include "clang/Basic/AddressSpaces.h"

 #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();
-  case ast_type_traits::TK_IgnoreUnlessSpelledInSource:
-    return E->IgnoreUnlessSpelledInSource();
-  }
-  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.

 
 interp::Context &ASTContext::getInterpContext() {
   if (!InterpContext) {
     InterpContext.reset(new interp::Context(*this));
   }
   return *InterpContext.get();
 }
 
+ParentMapContext &ASTContext::getParentMapContext() {
+  if (!ParentMapCtx)
+    ParentMapCtx.reset(new ParentMapContext(*this));
+  return *ParentMapCtx.get();
+}
+
 static const LangASMap *getAddressSpaceMap(const TargetInfo &T,
                                            const LangOptions &LOpts) {
   if (LOpts.FakeAddressSpaceMap) {
     // The fake address space map must have a distinct entry for each
     // language-specific address space.
     static const unsigned FakeAddrSpaceMap[] = {
         0, // Default
         1, // opencl_global
: ConstantArrayTypes(this_()), FunctionProtoTypes(this_()),
       XRayFilter(new XRayFunctionFilter(LangOpts.XRayAlwaysInstrumentFiles,
                                         LangOpts.XRayNeverInstrumentFiles,
                                         LangOpts.XRayAttrListFiles, SM)),
       PrintingPolicy(LOpts), Idents(idents), Selectors(sels),
       BuiltinInfo(builtins), DeclarationNames(*this), Comments(SM),
       CommentCommandTraits(BumpAlloc, LOpts.CommentOpts),
       CompCategories(this_()), LastSDM(nullptr, 0) {
   TUDecl = TranslationUnitDecl::Create(*this);
-  TraversalScope = {TUDecl};
 }
 
 ASTContext::~ASTContext() {
   // Release the DenseMaps associated with DeclContext objects.
   // FIXME: Is this the ideal solution?
   ReleaseDeclContextMaps();
 
   // Call all of the deallocation functions on all of their targets.
ASTContext::~ASTContext() {
 
   for (const auto &Value : ModuleInitializers)
     Value.second->~PerModuleInitializers();
 
   for (APValue *Value : APValueCleanups)
     Value->~APValue();
 }
 
-class ASTContext::ParentMap {
-  /// Contains parents of a node.
-  using ParentVector = llvm::SmallVector<ast_type_traits::DynTypedNode, 2>;
-
-  /// Maps from a node to its parents. This is used for nodes that have
-  /// pointer identity only, which are more common and we can save space by
-  /// only storing a unique pointer to them.
-  using ParentMapPointers = llvm::DenseMap<
-      const void *,
-      llvm::PointerUnion<const Decl *, const Stmt *,
-                         ast_type_traits::DynTypedNode *, ParentVector *>>;
-
-  /// Parent map for nodes without pointer identity. We store a full
-  /// DynTypedNode for all keys.
-  using ParentMapOtherNodes = llvm::DenseMap<
-      ast_type_traits::DynTypedNode,
-      llvm::PointerUnion<const Decl *, const Stmt *,
-                         ast_type_traits::DynTypedNode *, ParentVector *>>;
-
-  ParentMapPointers PointerParents;
-  ParentMapOtherNodes OtherParents;
-  class ASTVisitor;
-
-  static ast_type_traits::DynTypedNode
-  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
-    if (const auto *D = U.dyn_cast<const Decl *>())
-      return ast_type_traits::DynTypedNode::create(*D);
-    if (const auto *S = U.dyn_cast<const Stmt *>())
-      return ast_type_traits::DynTypedNode::create(*S);
-    return *U.get<ast_type_traits::DynTypedNode *>();
-  }
-
-  template <typename NodeTy, typename MapTy>
-  static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
-                                                        const MapTy &Map) {
-    auto I = Map.find(Node);
-    if (I == Map.end()) {
-      return llvm::ArrayRef<ast_type_traits::DynTypedNode>();
-    }
-    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
-      return llvm::makeArrayRef(*V);
-    }
-    return getSingleDynTypedNodeFromParentMap(I->second);
-  }
-
-public:
-  ParentMap(ASTContext &Ctx);
-  ~ParentMap() {
-    for (const auto &Entry : PointerParents) {
-      if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
-        delete Entry.second.get<ast_type_traits::DynTypedNode *>();
-      } else if (Entry.second.is<ParentVector *>()) {
-        delete Entry.second.get<ParentVector *>();
-      }
-    }
-    for (const auto &Entry : OtherParents) {
-      if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
-        delete Entry.second.get<ast_type_traits::DynTypedNode *>();
-      } else if (Entry.second.is<ParentVector *>()) {
-        delete Entry.second.get<ParentVector *>();
-      }
-    }
-  }
-
-  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.clear();
+  getParentMapContext().clear();
 }
 
 void ASTContext::AddDeallocation(void (*Callback)(void *), void *Data) const {
   Deallocations.push_back({Callback, Data});
 }
 
 void
 ASTContext::setExternalSource(IntrusiveRefCntPtr<ExternalASTSource> Source) {
bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const {
   CharUnits sizeChars = getTypeSizeInChars(AtomicTy);
   uint64_t Size = sizeChars.getQuantity();
   CharUnits alignChars = getTypeAlignInChars(AtomicTy);
   unsigned Align = alignChars.getQuantity();
   unsigned MaxInlineWidthInBits = getTargetInfo().getMaxAtomicInlineWidth();
   return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits);
 }
 
-/// Template specializations to abstract away from pointers and TypeLocs.
-/// @{
-template <typename T>
-static ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) {
-  return ast_type_traits::DynTypedNode::create(*Node);
-}
-template <>
-ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) {
-  return ast_type_traits::DynTypedNode::create(Node);
-}
-template <>
-ast_type_traits::DynTypedNode
-createDynTypedNode(const NestedNameSpecifierLoc &Node) {
-  return ast_type_traits::DynTypedNode::create(Node);
-}
-/// @}
-
-/// A \c RecursiveASTVisitor that builds a map from nodes to their
-/// parents as defined by the \c RecursiveASTVisitor.
-///
-/// 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, ASTContext &Context)
-      : Map(Map), Context(Context) {}
-
-private:
-  friend class RecursiveASTVisitor<ASTVisitor>;
-
-  using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
-
-  bool shouldVisitTemplateInstantiations() const { return true; }
-
-  bool shouldVisitImplicitCode() const { return true; }
-
-  template <typename T, typename MapNodeTy, typename BaseTraverseFn,
-            typename MapTy>
-  bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
-                    MapTy *Parents) {
-    if (!Node)
-      return true;
-    if (ParentStack.size() > 0) {
-      // FIXME: Currently we add the same parent multiple times, but only
-      // when no memoization data is available for the type.
-      // For example when we visit all subexpressions of template
-      // instantiations; this is suboptimal, but benign: the only way to
-      // visit those is with hasAncestor / hasParent, and those do not create
-      // new matches.
-      // The plan is to enable DynTypedNode to be storable in a map or hash
-      // map. The main problem there is to implement hash functions /
-      // comparison operators for all types that DynTypedNode supports that
-      // do not have pointer identity.
-      auto &NodeOrVector = (*Parents)[MapNode];
-      if (NodeOrVector.isNull()) {
-        if (const auto *D = ParentStack.back().get<Decl>())
-          NodeOrVector = D;
-        else if (const auto *S = ParentStack.back().get<Stmt>())
-          NodeOrVector = S;
-        else
-          NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
-      } else {
-        if (!NodeOrVector.template is<ParentVector *>()) {
-          auto *Vector = new ParentVector(
-              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
-          delete NodeOrVector
-              .template dyn_cast<ast_type_traits::DynTypedNode *>();
-          NodeOrVector = Vector;
-        }
-
-        auto *Vector = NodeOrVector.template get<ParentVector *>();
-        // Skip duplicates for types that have memoization data.
-        // We must check that the type has memoization data before calling
-        // std::find() because DynTypedNode::operator== can't compare all
-        // types.
-        bool Found = ParentStack.back().getMemoizationData() &&
-                     std::find(Vector->begin(), Vector->end(),
-                               ParentStack.back()) != Vector->end();
-        if (!Found)
-          Vector->push_back(ParentStack.back());
-      }
-    }
-    ParentStack.push_back(createDynTypedNode(Node));
-    bool Result = BaseTraverse();
-    ParentStack.pop_back();
-    return Result;
-  }
-
-  bool TraverseDecl(Decl *DeclNode) {
-    return TraverseNode(
-        DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
-        &Map.PointerParents);
-  }
-
-  bool TraverseStmt(Stmt *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, Ctx).TraverseAST(Ctx);
-}
-
-ASTContext::DynTypedNodeList
-ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
-  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.
-    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>())
     return false;
   if (MethodDecl->getObjCDeclQualifier() !=

clang/lib/AST/CMakeLists.txt

add_clang_library(clangAST
   DeclBase.cpp
   DeclCXX.cpp
   DeclFriend.cpp
   DeclGroup.cpp
   DeclObjC.cpp
   DeclOpenMP.cpp
   DeclPrinter.cpp
   DeclTemplate.cpp
+  ParentMapContext.cpp
   Expr.cpp
   ExprClassification.cpp
   ExprConcepts.cpp
   ExprConstant.cpp
   ExprCXX.cpp
   ExprObjC.cpp
   ExternalASTMerger.cpp
   ExternalASTSource.cpp

clang/lib/AST/Linkage.h

 //===----- Linkage.h - Linkage calculation-related utilities ----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file provides AST-internal utilities for linkage and visibility
 // calculation.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_AST_LINKAGE_H
 #define LLVM_CLANG_LIB_AST_LINKAGE_H
 
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Type.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerIntPair.h"
 
 namespace clang {

clang/lib/AST/ParentMapContext.cpp

+//===- ParentMapContext.cpp - Map of parents using DynTypedNode -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Similar to ParentMap.cpp, but generalizes to non-Stmt nodes, which can have
+// multiple parents.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/ParentMapContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/TemplateBase.h"
+
+using namespace clang;
+
+ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
+
+ParentMapContext::~ParentMapContext() = default;
+
+void ParentMapContext::clear() { Parents.clear(); }
+
+const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
+  return traverseIgnored(const_cast<Expr *>(E));
+}
+
+Expr *ParentMapContext::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();
+  case ast_type_traits::TK_IgnoreUnlessSpelledInSource:
+    return E->IgnoreUnlessSpelledInSource();
+  }
+  llvm_unreachable("Invalid Traversal type!");
+}
+
+ast_type_traits::DynTypedNode
+ParentMapContext::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;
+}
+
+class ParentMapContext::ParentMap {
+  /// Contains parents of a node.
+  using ParentVector = llvm::SmallVector<ast_type_traits::DynTypedNode, 2>;
+
+  /// Maps from a node to its parents. This is used for nodes that have
+  /// pointer identity only, which are more common and we can save space by
+  /// only storing a unique pointer to them.
+  using ParentMapPointers = llvm::DenseMap<
+      const void *,
+      llvm::PointerUnion<const Decl *, const Stmt *,
+                         ast_type_traits::DynTypedNode *, ParentVector *>>;
+
+  /// Parent map for nodes without pointer identity. We store a full
+  /// DynTypedNode for all keys.
+  using ParentMapOtherNodes = llvm::DenseMap<
+      ast_type_traits::DynTypedNode,
+      llvm::PointerUnion<const Decl *, const Stmt *,
+                         ast_type_traits::DynTypedNode *, ParentVector *>>;
+
+  ParentMapPointers PointerParents;
+  ParentMapOtherNodes OtherParents;
+  class ASTVisitor;
+
+  static ast_type_traits::DynTypedNode
+  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
+    if (const auto *D = U.dyn_cast<const Decl *>())
+      return ast_type_traits::DynTypedNode::create(*D);
+    if (const auto *S = U.dyn_cast<const Stmt *>())
+      return ast_type_traits::DynTypedNode::create(*S);
+    return *U.get<ast_type_traits::DynTypedNode *>();
+  }
+
+  template <typename NodeTy, typename MapTy>
+  static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
+                                                        const MapTy &Map) {
+    auto I = Map.find(Node);
+    if (I == Map.end()) {
+      return llvm::ArrayRef<ast_type_traits::DynTypedNode>();
+    }
+    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
+      return llvm::makeArrayRef(*V);
+    }
+    return getSingleDynTypedNodeFromParentMap(I->second);
+  }
+
+public:
+  ParentMap(ASTContext &Ctx);
+  ~ParentMap() {
+    for (const auto &Entry : PointerParents) {
+      if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
+        delete Entry.second.get<ast_type_traits::DynTypedNode *>();
+      } else if (Entry.second.is<ParentVector *>()) {
+        delete Entry.second.get<ParentVector *>();
+      }
+    }
+    for (const auto &Entry : OtherParents) {
+      if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
+        delete Entry.second.get<ast_type_traits::DynTypedNode *>();
+      } else if (Entry.second.is<ParentVector *>()) {
+        delete Entry.second.get<ParentVector *>();
+      }
+    }
+  }
+
+  DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node) {
+    if (Node.getNodeKind().hasPointerIdentity())
+      return getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
+    return getDynNodeFromMap(Node, OtherParents);
+  }
+};
+
+/// Template specializations to abstract away from pointers and TypeLocs.
+/// @{
+template <typename T>
+static ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) {
+  return ast_type_traits::DynTypedNode::create(*Node);
+}
+template <>
+ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) {
+  return ast_type_traits::DynTypedNode::create(Node);
+}
+template <>
+ast_type_traits::DynTypedNode
+createDynTypedNode(const NestedNameSpecifierLoc &Node) {
+  return ast_type_traits::DynTypedNode::create(Node);
+}
+/// @}
+
+/// A \c RecursiveASTVisitor that builds a map from nodes to their
+/// parents as defined by the \c RecursiveASTVisitor.
+///
+/// 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 ParentMapContext::ParentMap::ASTVisitor
+    : public RecursiveASTVisitor<ASTVisitor> {
+public:
+  ASTVisitor(ParentMap &Map, ParentMapContext &MapCtx)
+      : Map(Map), MapCtx(MapCtx) {}
+
+private:
+  friend class RecursiveASTVisitor<ASTVisitor>;
+
+  using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
+
+  bool shouldVisitTemplateInstantiations() const { return true; }
+
+  bool shouldVisitImplicitCode() const { return true; }
+
+  template <typename T, typename MapNodeTy, typename BaseTraverseFn,
+            typename MapTy>
+  bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
+                    MapTy *Parents) {
+    if (!Node)
+      return true;
+    if (ParentStack.size() > 0) {
+      // FIXME: Currently we add the same parent multiple times, but only
+      // when no memoization data is available for the type.
+      // For example when we visit all subexpressions of template
+      // instantiations; this is suboptimal, but benign: the only way to
+      // visit those is with hasAncestor / hasParent, and those do not create
+      // new matches.
+      // The plan is to enable DynTypedNode to be storable in a map or hash
+      // map. The main problem there is to implement hash functions /
+      // comparison operators for all types that DynTypedNode supports that
+      // do not have pointer identity.
+      auto &NodeOrVector = (*Parents)[MapNode];
+      if (NodeOrVector.isNull()) {
+        if (const auto *D = ParentStack.back().get<Decl>())
+          NodeOrVector = D;
+        else if (const auto *S = ParentStack.back().get<Stmt>())
+          NodeOrVector = S;
+        else
+          NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
+      } else {
+        if (!NodeOrVector.template is<ParentVector *>()) {
+          auto *Vector = new ParentVector(
+              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
+          delete NodeOrVector
+              .template dyn_cast<ast_type_traits::DynTypedNode *>();
+          NodeOrVector = Vector;
+        }
+
+        auto *Vector = NodeOrVector.template get<ParentVector *>();
+        // Skip duplicates for types that have memoization data.
+        // We must check that the type has memoization data before calling
+        // std::find() because DynTypedNode::operator== can't compare all
+        // types.
+        bool Found = ParentStack.back().getMemoizationData() &&
+                     std::find(Vector->begin(), Vector->end(),
+                               ParentStack.back()) != Vector->end();
+        if (!Found)
+          Vector->push_back(ParentStack.back());
+      }
+    }
+    ParentStack.push_back(createDynTypedNode(Node));
+    bool Result = BaseTraverse();
+    ParentStack.pop_back();
+    return Result;
+  }
+
+  bool TraverseDecl(Decl *DeclNode) {
+    return TraverseNode(
+        DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
+        &Map.PointerParents);
+  }
+
+  bool TraverseStmt(Stmt *StmtNode) {
+    Stmt *FilteredNode = StmtNode;
+    if (auto *ExprNode = dyn_cast_or_null<Expr>(FilteredNode))
+      FilteredNode = MapCtx.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;
+  ParentMapContext &MapCtx;
+  llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
+};
+
+ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
+  ASTVisitor(*this, Ctx.getParentMapContext()).TraverseAST(Ctx);
+}
+
+DynTypedNodeList
+ParentMapContext::getParents(const ast_type_traits::DynTypedNode &Node) {
+  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.
+    P = std::make_unique<ParentMap>(ASTCtx);
+  return P->getParents(Node);
+}
+

clang/lib/ASTMatchers/ASTMatchFinder.cpp

bool TraverseDecl(Decl *DeclNode) {
     ScopedIncrement ScopedDepth(&CurrentDepth);
     return (DeclNode == nullptr) || traverse(*DeclNode);
   }
 
   Stmt *getStmtToTraverse(Stmt *StmtNode) {
     Stmt *StmtToTraverse = StmtNode;
     if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
       auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
-      if (LambdaNode && Finder->getASTContext().getTraversalKind() ==
-                          ast_type_traits::TK_IgnoreUnlessSpelledInSource)
+      if (LambdaNode &&
+          Finder->getASTContext().getParentMapContext().getTraversalKind() ==
         StmtToTraverse = LambdaNode;
       else
-        StmtToTraverse = Finder->getASTContext().traverseIgnored(ExprNode);
+        StmtToTraverse =
+            Finder->getASTContext().getParentMapContext().traverseIgnored(
+                ExprNode);
     }
     if (Traversal ==
         ast_type_traits::TraversalKind::TK_IgnoreImplicitCastsAndParentheses) {
       if (Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode))
         StmtToTraverse = ExprNode->IgnoreParenImpCasts();
     }
     return StmtToTraverse;
   }
public:
   }
   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
     if (!CtorInit)
       return true;
     ScopedIncrement ScopedDepth(&CurrentDepth);
     return traverse(*CtorInit);
   }
   bool TraverseLambdaExpr(LambdaExpr *Node) {
-    if (Finder->getASTContext().getTraversalKind() !=
+    if (Finder->getASTContext().getParentMapContext().getTraversalKind() !=
         ast_type_traits::TK_IgnoreUnlessSpelledInSource)
       return VisitorBase::TraverseLambdaExpr(Node);
     if (!Node)
       return true;
     ScopedIncrement ScopedDepth(&CurrentDepth);
 
     for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
       const auto *C = Node->capture_begin() + I;
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();
+    Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
 
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
bool memoizedMatchesAncestorOfRecursively(
     if (!Builder->isComparable())
       return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
                                           MatchMode);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
-    Key.Traversal = Ctx.getTraversalKind();
+    Key.Traversal = Ctx.getParentMapContext().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;
     }

clang/lib/ASTMatchers/ASTMatchersInternal.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/ASTMatchersInternal.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclTemplate.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"

 }
 
 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
                               ASTMatchFinder *Finder,
                               BoundNodesTreeBuilder *Builder) const {
   TraversalKindScope RAII(Finder->getASTContext(),
                           Implementation->TraversalKind());
 
-  auto N = Finder->getASTContext().traverseIgnored(DynNode);
+  auto N =
+      Finder->getASTContext().getParentMapContext().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 {
   TraversalKindScope raii(Finder->getASTContext(),
                           Implementation->TraversalKind());
 
-  auto N = Finder->getASTContext().traverseIgnored(DynNode);
+  auto N =
+      Finder->getASTContext().getParentMapContext().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.

clang/lib/CodeGen/CGCall.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_CODEGEN_CGCALL_H
 #define LLVM_CLANG_LIB_CODEGEN_CGCALL_H
 
 #include "CGValue.h"
 #include "EHScopeStack.h"
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/CanonicalType.h"
 #include "clang/AST/GlobalDecl.h"
 #include "clang/AST/Type.h"
 #include "llvm/IR/Value.h"
 
 // FIXME: Restructure so we don't have to expose so much stuff.
 #include "ABIInfo.h"
 

clang/lib/Tooling/ASTDiff/ASTDiff.cpp

 //===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains definitons for the AST differencing interface.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/ASTDiff/ASTDiff.h"
 
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/PriorityQueue.h"
 
 #include <limits>
 #include <memory>
 #include <unordered_set>
 

clang/lib/Tooling/Refactoring/Rename/USRLocFinder.cpp

 /// Methods for finding all instances of a USR. Our strategy is very
 /// simple; we just compare the USR at every relevant AST node with the one
 /// provided.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/Refactoring/Rename/USRLocFinder.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/ParentMapContext.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Core/Lookup.h"
 #include "clang/Tooling/Refactoring/RecursiveSymbolVisitor.h"
 #include "clang/Tooling/Refactoring/Rename/SymbolName.h"

lldb/include/lldb/Symbol/TypeSystemClang.h

 #include <map>
 #include <memory>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/TemplateBase.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/SmallVector.h"
 
 #include "lldb/Core/ClangForward.h"
 #include "lldb/Expression/ExpressionVariable.h"
 #include "lldb/Symbol/CompilerType.h"
 #include "lldb/Symbol/TypeSystem.h"