[AST] Put TypeLocs and NestedNameSpecifierLocs into the ParentMap.

[bkramer]

Summary

Firstly this changes the type of parent map to be keyed on DynTypedNode to
simplify the following changes. This comes with a DenseMapInfo for
DynTypedNode, which is a bit incomplete still and will probably only work
for parentmap right now.

Then the RecursiveASTVisitor in ASTContext is updated and finally
ASTMatchers hasParent and hasAncestor learn about the new functionality.

Now ParentMap is only missing TemplateArgumentLocs and CXXCtorInitializers.

[klimek]

Yay, another yak shaved!!!! \o/

cfe/trunk/include/clang/AST/ASTContext.h

public:
   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.
-  typedef llvm::DenseMap<const void *,
+  typedef llvm::DenseMap<ast_type_traits::DynTypedNode,
                          llvm::PointerUnion<ast_type_traits::DynTypedNode *,
                                             ParentVector *>> ParentMap;
 
   /// \brief Returns the parents of the given node.
   ///
   /// 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.

cfe/trunk/include/clang/AST/ASTTypeTraits.h

public:
 
   /// \brief For nodes which represent textual entities in the source code,
   /// return their SourceRange.  For all other nodes, return SourceRange().
   SourceRange getSourceRange() const;
 
   /// @{
   /// \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).
+  /// FIXME: Implement comparsion for other node types.
   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

cfe/trunk/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

cfe/trunk/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,

cfe/trunk/lib/AST/ASTContext.cpp

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 {
 
+/// 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.
+/// FIXME: Currently only builds up the map using \c Stmt, \c Decl,
+/// \c NestedNameSpecifierLoc and \c TypeLoc 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);
private:
     }
     // 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 *)) {
+    bool TraverseNode(T Node, bool (VisitorBase::*traverse)(T)) {
       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)[createDynTypedNode(Node)];
         if (NodeOrVector.isNull()) {
           NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
         } else {
           if (NodeOrVector.template is<ast_type_traits::DynTypedNode *>()) {
             auto *Node =
                 NodeOrVector.template get<ast_type_traits::DynTypedNode *>();
             auto *Vector = new ASTContext::ParentVector(1, *Node);
             NodeOrVector = Vector;
bool TraverseNode(T Node, bool (VisitorBase::*traverse)(T)) {
           // 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);
     }
 
     bool TraverseStmt(Stmt *StmtNode) {
       return TraverseNode(StmtNode, &VisitorBase::TraverseStmt);
     }
 
+    bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+      return TraverseNode(TypeLocNode, &VisitorBase::TraverseTypeLoc);
+    }
+
+    bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
+      return TraverseNode(NNSLocNode,
+                          &VisitorBase::TraverseNestedNameSpecifierLoc);
+    }
+
     ASTContext::ParentMap *Parents;
     llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
 
     friend class RecursiveASTVisitor<ParentMapASTVisitor>;
   };
 
 } // end namespace
 
 ArrayRef<ast_type_traits::DynTypedNode>
 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());
+  ParentMap::const_iterator I = AllParents->find(Node);
   if (I == AllParents->end()) {
     return None;
   }
   if (auto *N = I->second.dyn_cast<ast_type_traits::DynTypedNode *>()) {
     return llvm::makeArrayRef(N, 1);
   }
   return *I->second.get<ParentVector *>();
 }

cfe/trunk/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);
 }
 

cfe/trunk/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(

cfe/trunk/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>)",
+  EXPECT_EQ("Matcher<Decl> "
+            "hasParent(Matcher<NestedNameSpecifierLoc|TypeLoc|Decl|...>)",
             Comps[2].MatcherDecl);
 }
 
 }  // end anonymous namespace
 }  // end namespace dynamic
 }  // end namespace ast_matchers
 }  // end namespace clang

cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp

EXPECT_EQ("Incorrect type for arg 1. "
             "(Expected = Matcher<CXXRecordDecl>) != "
             "(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>)"));
+  EXPECT_TRUE(hasCompletion(Comps, "hasParent(",
+                            "Matcher<NestedNameSpecifierLoc|TypeLoc|Decl|...> "
+                            "hasParent(Matcher<NestedNameSpecifierLoc|TypeLoc|"
+                            "Decl|...>)"));
   // Variadic.
   EXPECT_TRUE(hasCompletion(Comps, "whileStmt(",
                             "Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)"));
   // Polymorphic.
   EXPECT_TRUE(hasCompletion(
       Comps, "hasDescendant(",
       "Matcher<NestedNameSpecifier|NestedNameSpecifierLoc|QualType|...> "
       "hasDescendant(Matcher<CXXCtorInitializer|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>)"));
+  EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", "Matcher<Stmt> "
+                                                      "hasParent(Matcher<"
+                                                      "NestedNameSpecifierLoc|"
+                                                      "TypeLoc|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);