[AST] Use data-recursion when building ParentMap, avoid stack overflow.

[sammccall]

Summary

The following crashes on my system before this patch, but not after:

void foo(int i) {
  switch (i) {
    case 1:
    case 2:
    ... 100000 cases ...
      ;
  }
}

clang-query -c="match stmt(hasAncestor(stmt()))" deep.c

I'm not sure it's actually a sane testcase to run though, it's pretty slow :-)

[hokein]

Thanks for fixing this!

clang/lib/AST/ParentMapContext.cpp

229

can we make some comments explaining what this method does? I think I have a vague understanding, but would be helpful to have some documentation.

[sammccall]

Address comments.

Also remove a stale fixme, and simplify a little.

clang/lib/AST/ParentMapContext.cpp

 /// @}
 
 /// 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) : Map(Map) {}
 
 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 DynTypedNode(ParentStack.back());
-      } else {
-        if (!NodeOrVector.template is<ParentVector *>()) {
-          auto *Vector = new ParentVector(
-              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
-          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
-          NodeOrVector = Vector;
-        }
+  /// Record the parent of the node we're visiting.
+  /// MapNode is the child, the parent is on top of ParentStack.
+  /// Parents is the parent storage (either PointerParents or OtherParents).
+  template <typename MapNodeTy, typename MapTy>
+  void addParent(MapNodeTy MapNode, MapTy *Parents) {
+    if (ParentStack.empty())
+      return;
+
 
-        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());
-      }
-    }
+
+  template <typename T, typename MapNodeTy, typename BaseTraverseFn,
+            typename MapTy>
+  bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
+                    MapTy *Parents) {
+    if (!Node)
+      return true;
+    addParent(MapNode, Parents);
     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) {
-    return TraverseNode(StmtNode, StmtNode,
-                        [&] { return VisitorBase::TraverseStmt(StmtNode); },
-                        &Map.PointerParents);
-  }
-
   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
     return TraverseNode(
         TypeLocNode, DynTypedNode::create(TypeLocNode),
         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
         &Map.OtherParents);
   }
-
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
     return TraverseNode(
         NNSLocNode, DynTypedNode::create(NNSLocNode),
         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
         &Map.OtherParents);
   }
 
+  // Using generic TraverseNode for Stmt would prevent data-recursion.
+  bool dataTraverseStmtPre(Stmt *StmtNode) {
+    addParent(StmtNode, &Map.PointerParents);
+    ParentStack.push_back(DynTypedNode::create(*StmtNode));
+    return true;
+  }
+  bool dataTraverseStmtPost(Stmt *StmtNode) {
+    ParentStack.pop_back();
+    return true;
+  }
+
   ParentMap &Map;
   llvm::SmallVector<DynTypedNode, 16> ParentStack;
 };
 
 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
   ASTVisitor(*this).TraverseAST(Ctx);
 }
 
 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
   if (!Parents)
     // We build the parent map for the traversal scope (usually whole TU), as
     // hasAncestor can escape any subtree.
     Parents = std::make_unique<ParentMap>(ASTCtx);
   return Parents->getParents(getTraversalKind(), Node);
 }