Index: include/clang/AST/ASTContext.h
===================================================================
--- include/clang/AST/ASTContext.h
+++ include/clang/AST/ASTContext.h
@@ -451,11 +451,21 @@
   /// \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.
@@ -2513,7 +2523,8 @@
   void ReleaseDeclContextMaps();
   void ReleaseParentMapEntries();
 
-  std::unique_ptr<ParentMap> AllParents;
+  std::unique_ptr<ParentMapPointers> PointerParents;
+  std::unique_ptr<ParentMapOtherNodes> OtherParents;
 
   std::unique_ptr<VTableContextBase> VTContext;
 
Index: include/clang/AST/ASTTypeTraits.h
===================================================================
--- include/clang/AST/ASTTypeTraits.h
+++ include/clang/AST/ASTTypeTraits.h
@@ -268,6 +268,28 @@
   /// 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();
   }
@@ -281,6 +303,13 @@
     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();
   }
@@ -289,6 +318,47 @@
   }
   /// @}
 
+  /// \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;
@@ -426,6 +496,10 @@
 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
Index: include/clang/ASTMatchers/ASTMatchers.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchers.h
+++ include/clang/ASTMatchers/ASTMatchers.h
@@ -2068,8 +2068,10 @@
 ///
 /// 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.
@@ -2083,8 +2085,10 @@
 ///
 /// 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.
 ///
Index: include/clang/ASTMatchers/ASTMatchersInternal.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchersInternal.h
+++ include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -848,8 +848,10 @@
                          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);
   }
Index: lib/AST/ASTContext.cpp
===================================================================
--- lib/AST/ASTContext.cpp
+++ lib/AST/ASTContext.cpp
@@ -793,8 +793,15 @@
 }
 
 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 *>()) {
@@ -8670,8 +8677,8 @@
 
 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 *>())
@@ -8679,6 +8686,23 @@
   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.
   ///
@@ -8693,17 +8717,21 @@
     /// \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;
@@ -8717,8 +8745,9 @@
       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) {
@@ -8732,7 +8761,7 @@
         // 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;
@@ -8765,21 +8794,36 @@
             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);
+    }
+
+    bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+      return TraverseNode(TypeLocNode,
+                          ast_type_traits::DynTypedNode::create(TypeLocNode),
+                          &VisitorBase::TraverseTypeLoc, OtherParents);
     }
 
-    ASTContext::ParentMap *Parents;
+    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>;
@@ -8787,27 +8831,33 @@
 
 } // 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) {
Index: lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -621,9 +621,6 @@
     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();
@@ -867,7 +864,11 @@
 
 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())
Index: unittests/AST/ASTContextParentMapTest.cpp
===================================================================
--- unittests/AST/ASTContextParentMapTest.cpp
+++ unittests/AST/ASTContextParentMapTest.cpp
@@ -38,6 +38,19 @@
                              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(
Index: unittests/ASTMatchers/Dynamic/ParserTest.cpp
===================================================================
--- unittests/ASTMatchers/Dynamic/ParserTest.cpp
+++ unittests/ASTMatchers/Dynamic/ParserTest.cpp
@@ -318,8 +318,10 @@
       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|...>)",
+      Comps[2].MatcherDecl);
 }
 
 }  // end anonymous namespace
Index: unittests/ASTMatchers/Dynamic/RegistryTest.cpp
===================================================================
--- unittests/ASTMatchers/Dynamic/RegistryTest.cpp
+++ unittests/ASTMatchers/Dynamic/RegistryTest.cpp
@@ -448,7 +448,9 @@
   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>...)"));
@@ -464,7 +466,9 @@
   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>...)"));