[AST] Re-add TypeLocs and NestedNameSpecifierLocs to the ParentMap.

[bkramer]

Summary

This relands r250831 after some fixes to shrink the ParentMap overall
with one addtional tweak: nodes with pointer identity (e.g. Decl* and
friends) can be store more efficiently so I put them in a separate map.
All other nodes (so far only TypeLoc and NNSLoc) go in a different map
keyed on DynTypedNode. This further uglifies the code but significantly
reduces memory overhead.

Overall this change still make ParentMap significantly larger but it's
nowhere as bad as before. I see about 25 MB over baseline (pre-r251008)
on X86ISelLowering.cpp. If this becomes an issue we could consider
splitting the maps further as DynTypedNode is still larger (32 bytes)
than a single TypeLoc (16 bytes) but I didn't want to introduce even
more complexity now.

[klimek]

lg; let's see whether it sticks this time :)

include/clang/AST/ASTContext.h

456

s/an/a/ (like user, unique begins with a 'y' sound)

include/clang/AST/ASTContext.h

public:
   Builtin::Context &BuiltinInfo;
   mutable DeclarationNameTable DeclarationNames;
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener;
 
   /// \brief Contains parents of a node.
   typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 2> ParentVector;
 
-  /// \brief Maps from a node to its parents.
+  /// \brief 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 an unique pointer to them.
   typedef llvm::DenseMap<const void *,
                          llvm::PointerUnion4<const Decl *, const Stmt *,
                                              ast_type_traits::DynTypedNode *,
-                                             ParentVector *>> ParentMap;
+                                             ParentVector *>> ParentMapPointers;
+
+  /// Parent map for nodes without pointer identity. We store a full
+  /// DynTypedNode for all keys.
+  typedef llvm::DenseMap<
+      ast_type_traits::DynTypedNode,
+      llvm::PointerUnion4<const Decl *, const Stmt *,
+                          ast_type_traits::DynTypedNode *, ParentVector *>>
+      ParentMapOtherNodes;
 
   /// Container for either a single DynTypedNode or for an ArrayRef to
   /// DynTypedNode. For use with ParentMap.
   class DynTypedNodeList {
     typedef ast_type_traits::DynTypedNode DynTypedNode;
     llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
                                 ArrayRef<DynTypedNode>> Storage;
     bool IsSingleNode;
private:
   // but we include it here so that ASTContext can quickly deallocate them.
   llvm::PointerIntPair<StoredDeclsMap*,1> LastSDM;
 
   friend class DeclContext;
   friend class DeclarationNameTable;
   void ReleaseDeclContextMaps();
   void ReleaseParentMapEntries();
 
-  std::unique_ptr<ParentMap> AllParents;
+  std::unique_ptr<ParentMapPointers> PointerParents;
+  std::unique_ptr<ParentMapOtherNodes> OtherParents;
 
   std::unique_ptr<VTableContextBase> VTContext;
 
 public:
   enum PragmaSectionFlag : unsigned {
     PSF_None = 0,
     PSF_Read = 0x1,
     PSF_Write = 0x2,

include/clang/AST/ASTTypeTraits.h

public:
 
   /// @{
   /// \brief Imposes an order on \c DynTypedNode.
   ///
   /// Supports comparison of nodes that support memoization.
   /// FIXME: Implement comparsion for other node types (currently
   /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
   bool operator<(const DynTypedNode &Other) const {
+    if (!NodeKind.isSame(Other.NodeKind))
+      return NodeKind < Other.NodeKind;
+
+    if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind)) {
+      auto TLA = getUnchecked<TypeLoc>();
+      auto TLB = Other.getUnchecked<TypeLoc>();
+      return std::make_pair(TLA.getType().getAsOpaquePtr(),
+                            TLA.getOpaqueData()) <
+             std::make_pair(TLB.getType().getAsOpaquePtr(),
+                            TLB.getOpaqueData());
+    }
+
+    if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
+            NodeKind)) {
+      auto NNSLA = getUnchecked<NestedNameSpecifierLoc>();
+      auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>();
+      return std::make_pair(NNSLA.getNestedNameSpecifier(),
+                            NNSLA.getOpaqueData()) <
+             std::make_pair(NNSLB.getNestedNameSpecifier(),
+                            NNSLB.getOpaqueData());
+    }
+
     assert(getMemoizationData() && Other.getMemoizationData());
     return getMemoizationData() < Other.getMemoizationData();
   }
   bool operator==(const DynTypedNode &Other) const {
     // DynTypedNode::create() stores the exact kind of the node in NodeKind.
     // If they contain the same node, their NodeKind must be the same.
     if (!NodeKind.isSame(Other.NodeKind))
       return false;
 
     // FIXME: Implement for other types.
     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
       return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
 
+    if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind))
+      return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
+
+    if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
+      return getUnchecked<NestedNameSpecifierLoc>() ==
+             Other.getUnchecked<NestedNameSpecifierLoc>();
+
     assert(getMemoizationData() && Other.getMemoizationData());
     return getMemoizationData() == Other.getMemoizationData();
   }
   bool operator!=(const DynTypedNode &Other) const {
     return !operator==(Other);
   }
   /// @}
 
+  /// \brief Hooks for using DynTypedNode as a key in a DenseMap.
+  struct DenseMapInfo {
+    static inline DynTypedNode getEmptyKey() {
+      DynTypedNode Node;
+      Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey();
+      return Node;
+    }
+    static inline DynTypedNode getTombstoneKey() {
+      DynTypedNode Node;
+      Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey();
+      return Node;
+    }
+    static unsigned getHashValue(const DynTypedNode &Val) {
+      // FIXME: Add hashing support for the remaining types.
+      if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(Val.NodeKind)) {
+        auto TL = Val.getUnchecked<TypeLoc>();
+        return llvm::hash_combine(TL.getType().getAsOpaquePtr(),
+                                  TL.getOpaqueData());
+      }
+
+      if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
+              Val.NodeKind)) {
+        auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>();
+        return llvm::hash_combine(NNSL.getNestedNameSpecifier(),
+                                  NNSL.getOpaqueData());
+      }
+
+      assert(Val.getMemoizationData());
+      return llvm::hash_value(Val.getMemoizationData());
+    }
+    static bool isEqual(const DynTypedNode &LHS, const DynTypedNode &RHS) {
+      auto Empty = ASTNodeKind::DenseMapInfo::getEmptyKey();
+      auto TombStone = ASTNodeKind::DenseMapInfo::getTombstoneKey();
+      return (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, Empty) &&
+              ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, Empty)) ||
+             (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, TombStone) &&
+              ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, TombStone)) ||
+             LHS == RHS;
+    }
+  };
+
 private:
   /// \brief Takes care of converting from and to \c T.
   template <typename T, typename EnablerT = void> struct BaseConverter;
 
   /// \brief Converter that uses dyn_cast<T> from a stored BaseT*.
   template <typename T, typename BaseT> struct DynCastPtrConverter {
     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
       if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))

 } // end namespace clang
 
 namespace llvm {
 
 template <>
 struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
     : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
 
+template <>
+struct DenseMapInfo<clang::ast_type_traits::DynTypedNode>
+    : clang::ast_type_traits::DynTypedNode::DenseMapInfo {};
+
 }  // end namespace llvm
 
 #endif

include/clang/ASTMatchers/ASTMatchers.h

 /// Given
 /// \code
 /// void f() { for (;;) { int x = 42; if (true) { int x = 43; } } }
 /// \endcode
 /// \c compoundStmt(hasParent(ifStmt())) matches "{ int x = 43; }".
 ///
 /// Usable as: Any Matcher
 const internal::ArgumentAdaptingMatcherFunc<
-    internal::HasParentMatcher, internal::TypeList<Decl, Stmt>,
-    internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasParent = {};
+    internal::HasParentMatcher,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
+    LLVM_ATTRIBUTE_UNUSED hasParent = {};
 
 /// \brief Matches AST nodes that have an ancestor that matches the provided
 /// matcher.
 ///
 /// Given
 /// \code
 /// void f() { if (true) { int x = 42; } }
 /// void g() { for (;;) { int x = 43; } }
 /// \endcode
 /// \c expr(integerLiteral(hasAncestor(ifStmt()))) matches \c 42, but not 43.
 ///
 /// Usable as: Any Matcher
 const internal::ArgumentAdaptingMatcherFunc<
-    internal::HasAncestorMatcher, internal::TypeList<Decl, Stmt>,
-    internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasAncestor = {};
+    internal::HasAncestorMatcher,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
+    internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
+    LLVM_ATTRIBUTE_UNUSED hasAncestor = {};
 
 /// \brief Matches if the provided matcher does not match.
 ///
 /// Example matches Y (matcher = cxxRecordDecl(unless(hasName("X"))))
 /// \code
 ///   class X {};
 ///   class Y {};
 /// \endcode

include/clang/ASTMatchers/ASTMatchersInternal.h

public:
 
   // 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<Stmt, T>::value,
-                  "only Decl or Stmt allowed for recursive matching");
+                      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);
   }
 
   virtual ASTContext &getASTContext() const = 0;
 
 protected:
   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,

lib/AST/ASTContext.cpp

ASTContext::~ASTContext() {
   for (std::pair<const MaterializeTemporaryExpr *, APValue *> &MTVPair :
        MaterializedTemporaryValues)
     MTVPair.second->~APValue();
 
   llvm::DeleteContainerSeconds(MangleNumberingContexts);
 }
 
 void ASTContext::ReleaseParentMapEntries() {
-  if (!AllParents) return;
-  for (const auto &Entry : *AllParents) {
+  if (!PointerParents) return;
+  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 *>();
     }
   }
 }
 
bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const {
   CharUnits alignChars = getTypeAlignInChars(AtomicTy);
   unsigned Align = alignChars.getQuantity();
   unsigned MaxInlineWidthInBits = getTargetInfo().getMaxAtomicInlineWidth();
   return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits);
 }
 
 namespace {
 
-ast_type_traits::DynTypedNode
-getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) {
+ast_type_traits::DynTypedNode getSingleDynTypedNodeFromParentMap(
+    ASTContext::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 specializations to abstract away from pointers and TypeLocs.
+/// @{
+template <typename T>
+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);
+}
+/// @}
+
   /// \brief 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 ParentMapASTVisitor : public RecursiveASTVisitor<ParentMapASTVisitor> {
 
   public:
     /// \brief Builds and returns the translation unit's parent map.
     ///
     ///  The caller takes ownership of the returned \c ParentMap.
-    static ASTContext::ParentMap *buildMap(TranslationUnitDecl &TU) {
-      ParentMapASTVisitor Visitor(new ASTContext::ParentMap);
+    static std::pair<ASTContext::ParentMapPointers *,
+                     ASTContext::ParentMapOtherNodes *>
+    buildMap(TranslationUnitDecl &TU) {
+      ParentMapASTVisitor Visitor(new ASTContext::ParentMapPointers,
+                                  new ASTContext::ParentMapOtherNodes);
       Visitor.TraverseDecl(&TU);
-      return Visitor.Parents;
+      return std::make_pair(Visitor.Parents, Visitor.OtherParents);
     }
 
   private:
     typedef RecursiveASTVisitor<ParentMapASTVisitor> VisitorBase;
 
-    ParentMapASTVisitor(ASTContext::ParentMap *Parents) : Parents(Parents) {
-    }
+    ParentMapASTVisitor(ASTContext::ParentMapPointers *Parents,
+                        ASTContext::ParentMapOtherNodes *OtherParents)
+        : Parents(Parents), OtherParents(OtherParents) {}
 
     bool shouldVisitTemplateInstantiations() const {
       return true;
     }
     bool shouldVisitImplicitCode() const {
       return true;
     }
     // Disables data recursion. We intercept Traverse* methods in the RAV, which
     // are not triggered during data recursion.
     bool shouldUseDataRecursionFor(clang::Stmt *S) const {
       return false;
     }
 
-    template <typename T>
-    bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) {
+    template <typename T, typename MapNodeTy, typename MapTy>
+    bool TraverseNode(T Node, MapNodeTy MapNode,
+                      bool (VisitorBase::*traverse)(T), 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)[Node];
+        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());
bool TraverseNode(T Node, MapNodeTy MapNode,
           // 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(ast_type_traits::DynTypedNode::create(*Node));
+      ParentStack.push_back(createDynTypedNode(Node));
       bool Result = (this ->* traverse) (Node);
       ParentStack.pop_back();
       return Result;
     }
 
     bool TraverseDecl(Decl *DeclNode) {
-      return TraverseNode(DeclNode, &VisitorBase::TraverseDecl);
+      return TraverseNode(DeclNode, DeclNode, &VisitorBase::TraverseDecl,
+                          Parents);
     }
 
     bool TraverseStmt(Stmt *StmtNode) {
-      return TraverseNode(StmtNode, &VisitorBase::TraverseStmt);
+      return TraverseNode(StmtNode, StmtNode, &VisitorBase::TraverseStmt,
+                          Parents);
     }
 
-    ASTContext::ParentMap *Parents;
+    bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+      return TraverseNode(TypeLocNode,
+                          ast_type_traits::DynTypedNode::create(TypeLocNode),
+                          &VisitorBase::TraverseTypeLoc, OtherParents);
+    }
+
+    bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
+      return TraverseNode(
+          NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode),
+          &VisitorBase::TraverseNestedNameSpecifierLoc, OtherParents);
+    }
+
+    ASTContext::ParentMapPointers *Parents;
+    ASTContext::ParentMapOtherNodes *OtherParents;
     llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
 
     friend class RecursiveASTVisitor<ParentMapASTVisitor>;
   };
 
 } // end namespace
 
-ASTContext::DynTypedNodeList
-ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
-  assert(Node.getMemoizationData() &&
-         "Invariant broken: only nodes that support memoization may be "
-         "used in the parent map.");
-  if (!AllParents) {
-    // We always need to run over the whole translation unit, as
-    // hasAncestor can escape any subtree.
-    AllParents.reset(
-        ParentMapASTVisitor::buildMap(*getTranslationUnitDecl()));
-  }
-  ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData());
-  if (I == AllParents->end()) {
+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 (auto *V = I->second.dyn_cast<ParentVector *>()) {
+  if (auto *V = I->second.template dyn_cast<ASTContext::ParentVector *>()) {
     return llvm::makeArrayRef(*V);
   }
   return getSingleDynTypedNodeFromParentMap(I->second);
 }
 
+ASTContext::DynTypedNodeList
+ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
+  if (!PointerParents) {
+    // We always need to run over the whole translation unit, as
+    // hasAncestor can escape any subtree.
+    auto Maps = ParentMapASTVisitor::buildMap(*getTranslationUnitDecl());
+    PointerParents.reset(Maps.first);
+    OtherParents.reset(Maps.second);
+  }
+  if (Node.getNodeKind().hasPointerIdentity())
+    return getDynNodeFromMap(Node.getMemoizationData(), *PointerParents);
+  return getDynNodeFromMap(Node, *OtherParents);
+}
+
 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() !=

lib/ASTMatchers/ASTMatchFinder.cpp

private:
   // 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) {
     if (Node.get<TranslationUnitDecl>() ==
         ActiveASTContext->getTranslationUnitDecl())
       return false;
-    assert(Node.getMemoizationData() &&
-           "Invariant broken: only nodes that support memoization may be "
-           "used in the parent map.");
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
 
     // Note that we cannot use insert and reuse the iterator, as recursive
     // calls to match might invalidate the result cache iterators.

 
 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
   match(*NNS);
   return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
 }
 
 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
     NestedNameSpecifierLoc NNS) {
+  if (!NNS)
+    return true;
+
   match(NNS);
+
   // We only match the nested name specifier here (as opposed to traversing it)
   // because the traversal is already done in the parallel "Loc"-hierarchy.
   if (NNS.hasQualifier())
     match(*NNS.getNestedNameSpecifier());
   return
       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
 }
 

unittests/AST/ASTContextParentMapTest.cpp

 }
 
 TEST(GetParents, ReturnsParentForStmt) {
   MatchVerifier<Stmt> Verifier;
   EXPECT_TRUE(Verifier.match("class C { void f() { if (true) {} } };",
                              ifStmt(hasParent(compoundStmt()))));
 }
 
+TEST(GetParents, ReturnsParentForTypeLoc) {
+  MatchVerifier<TypeLoc> Verifier;
+  EXPECT_TRUE(
+      Verifier.match("namespace a { class b {}; } void f(a::b) {}",
+                     typeLoc(hasParent(typeLoc(hasParent(functionDecl()))))));
+}
+
+TEST(GetParents, ReturnsParentForNestedNameSpecifierLoc) {
+  MatchVerifier<NestedNameSpecifierLoc> Verifier;
+  EXPECT_TRUE(Verifier.match("namespace a { class b {}; } void f(a::b) {}",
+                             nestedNameSpecifierLoc(hasParent(typeLoc()))));
+}
+
 TEST(GetParents, ReturnsParentInsideTemplateInstantiations) {
   MatchVerifier<Decl> DeclVerifier;
   EXPECT_TRUE(DeclVerifier.match(
       "template<typename T> struct C { void f() {} };"
       "void g() { C<int> c; c.f(); }",
       cxxMethodDecl(hasName("f"),
                  hasParent(cxxRecordDecl(isTemplateInstantiation())))));
   EXPECT_TRUE(DeclVerifier.match(

unittests/ASTMatchers/Dynamic/ParserTest.cpp

TEST(ParserTest, CompletionNamedValues) {
   EXPECT_EQ("Matcher<FunctionDecl> hasParamA", Comps[0].MatcherDecl);
 
   EXPECT_EQ("arameter(", Comps[1].TypedText);
   EXPECT_EQ(
       "Matcher<FunctionDecl> hasParameter(unsigned, Matcher<ParmVarDecl>)",
       Comps[1].MatcherDecl);
 
   EXPECT_EQ("arent(", Comps[2].TypedText);
-  EXPECT_EQ("Matcher<Decl> hasParent(Matcher<Decl|Stmt>)",
-            Comps[2].MatcherDecl);
+  EXPECT_EQ(
+      "Matcher<Decl> "
+      "hasParent(Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...>)",
 }
 
 }  // end anonymous namespace
 }  // end namespace dynamic
 }  // end namespace ast_matchers
 }  // end namespace clang

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

EXPECT_EQ("Incorrect type for arg 1. "
             "(Actual = Matcher<CXXRecordDecl>&Matcher<MemberExpr>)",
             Error->toString());
 }
 
 TEST_F(RegistryTest, Completion) {
   CompVector Comps = getCompletions();
   // Overloaded
   EXPECT_TRUE(hasCompletion(
-      Comps, "hasParent(", "Matcher<Decl|Stmt> hasParent(Matcher<Decl|Stmt>)"));
+      Comps, "hasParent(",
+      "Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...> "
+      "hasParent(Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...>)"));
   // Variadic.
   EXPECT_TRUE(hasCompletion(Comps, "whileStmt(",
                             "Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)"));
   // Polymorphic.
   EXPECT_TRUE(hasCompletion(
       Comps, "hasDescendant(",
       "Matcher<TemplateArgument|NestedNameSpecifier|NestedNameSpecifierLoc|...>"
       " hasDescendant(Matcher<TemplateArgument|NestedNameSpecifier|"
       "NestedNameSpecifierLoc|...>)"));
 
   CompVector WhileComps = getCompletions("whileStmt", 0);
 
   EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(",
                             "Matcher<WhileStmt> hasBody(Matcher<Stmt>)"));
   EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(",
-                            "Matcher<Stmt> hasParent(Matcher<Decl|Stmt>)"));
+                            "Matcher<Stmt> "
+                            "hasParent(Matcher<TemplateArgument|"
+                            "NestedNameSpecifierLoc|Decl|...>)"));
   EXPECT_TRUE(
       hasCompletion(WhileComps, "allOf(", "Matcher<T> allOf(Matcher<T>...)"));
 
   EXPECT_FALSE(hasCompletion(WhileComps, "whileStmt("));
   EXPECT_FALSE(hasCompletion(WhileComps, "ifStmt("));
 
   CompVector AllOfWhileComps =
       getCompletions("allOf", 0, "whileStmt", 0);