[libclang] Actually commit the changes to make libclang's RecursiveASTVisitor

data-recursive for statements.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@156339 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 121 insertions, 190 deletions

diff --git a/tools/libclang/RecursiveASTVisitor.h b/tools/libclang/RecursiveASTVisitor.h
index 8f244f1c98..0bff91ff8e 100644
--- a/tools/libclang/RecursiveASTVisitor.h
+++ b/tools/libclang/RecursiveASTVisitor.h
@@ -115,6 +115,9 @@ namespace cxindex {
 /// node are grouped together.  In other words, Visit*() methods for
 /// different nodes are never interleaved.
 ///
+/// Stmts are traversed internally using a data queue to avoid a stack overflow
+/// with hugely nested ASTs.
+///
 /// Clients of this visitor should subclass the visitor (providing
 /// themselves as the template argument, using the curiously recurring
 /// template pattern) and override any of the Traverse*, WalkUpFrom*,
@@ -149,13 +152,6 @@ public:
   /// TypeLocs.
   bool shouldWalkTypesOfTypeLocs() const { return true; }
 
-  /// \brief Return whether \param S should be traversed using data recursion
-  /// to avoid a stack overflow with extreme cases.
-  bool shouldUseDataRecursionFor(Stmt *S) const {
-    return isa<BinaryOperator>(S) || isa<UnaryOperator>(S) ||
-           isa<CaseStmt>(S) || isa<CXXOperatorCallExpr>(S);
-  }
-
   /// \brief Recursively visit a statement or expression, by
   /// dispatching to Traverse*() based on the argument's dynamic type.
   ///
@@ -268,7 +264,8 @@ public:
 #define OPERATOR(NAME)                                           \
   bool TraverseUnary##NAME(UnaryOperator *S) {                  \
     TRY_TO(WalkUpFromUnary##NAME(S));                           \
-    TRY_TO(TraverseStmt(S->getSubExpr()));                      \
+    StmtQueueAction StmtQueue(*this);                           \
+    StmtQueue.queue(S->getSubExpr());                           \
     return true;                                                \
   }                                                             \
   bool WalkUpFromUnary##NAME(UnaryOperator *S) {                \
@@ -287,8 +284,9 @@ public:
 #define GENERAL_BINOP_FALLBACK(NAME, BINOP_TYPE)                \
   bool TraverseBin##NAME(BINOP_TYPE *S) {                       \
     TRY_TO(WalkUpFromBin##NAME(S));                             \
-    TRY_TO(TraverseStmt(S->getLHS()));                          \
-    TRY_TO(TraverseStmt(S->getRHS()));                          \
+    StmtQueueAction StmtQueue(*this);                           \
+    StmtQueue.queue(S->getLHS());                               \
+    StmtQueue.queue(S->getRHS());                               \
     return true;                                                \
   }                                                             \
   bool WalkUpFromBin##NAME(BINOP_TYPE *S) {                     \
@@ -394,8 +392,8 @@ public:
 private:
   // These are helper methods used by more than one Traverse* method.
   bool TraverseTemplateParameterListHelper(TemplateParameterList *TPL);
-  bool TraverseClassInstantiations(ClassTemplateDecl* D, Decl *Pattern);
-  bool TraverseFunctionInstantiations(FunctionTemplateDecl* D) ;
+  bool TraverseClassInstantiations(ClassTemplateDecl *D);
+  bool TraverseFunctionInstantiations(FunctionTemplateDecl *D) ;
   bool TraverseTemplateArgumentLocsHelper(const TemplateArgumentLoc *TAL,
                                           unsigned Count);
   bool TraverseArrayTypeLocHelper(ArrayTypeLoc TL);
@@ -406,100 +404,39 @@ private:
   bool TraverseFunctionHelper(FunctionDecl *D);
   bool TraverseVarHelper(VarDecl *D);
 
-  bool Walk(Stmt *S);
-
-  struct EnqueueJob {
-    Stmt *S;
-    Stmt::child_iterator StmtIt;
-
-    EnqueueJob(Stmt *S) : S(S), StmtIt() {
-      if (Expr *E = dyn_cast_or_null<Expr>(S))
-        S = E->IgnoreParens();
-    }
-  };
-  bool dataTraverse(Stmt *S);
-};
-
-template<typename Derived>
-bool RecursiveASTVisitor<Derived>::dataTraverse(Stmt *S) {
-
-  SmallVector<EnqueueJob, 16> Queue;
-  Queue.push_back(S);
+  typedef SmallVector<Stmt *, 16> StmtsTy;
+  typedef SmallVector<StmtsTy *, 4> QueuesTy;
+  
+  QueuesTy Queues;
 
-  while (!Queue.empty()) {
-    EnqueueJob &job = Queue.back();
-    Stmt *CurrS = job.S;
-    if (!CurrS) {
-      Queue.pop_back();
-      continue;
+  class NewQueueRAII {
+    RecursiveASTVisitor &RAV;
+  public:
+    NewQueueRAII(StmtsTy &queue, RecursiveASTVisitor &RAV) : RAV(RAV) {
+      RAV.Queues.push_back(&queue);
     }
-
-    if (getDerived().shouldUseDataRecursionFor(CurrS)) {
-      if (job.StmtIt == Stmt::child_iterator()) {
-        if (!Walk(CurrS)) return false;
-        job.StmtIt = CurrS->child_begin();
-      } else {
-        ++job.StmtIt;
-      }
-
-      if (job.StmtIt != CurrS->child_end())
-        Queue.push_back(*job.StmtIt);
-      else
-        Queue.pop_back();
-      continue;
+    ~NewQueueRAII() {
+      RAV.Queues.pop_back();
     }
+  };
 
-    Queue.pop_back();
-    TRY_TO(TraverseStmt(CurrS));
+  StmtsTy &getCurrentQueue() {
+    assert(!Queues.empty() && "base TraverseStmt was never called?");
+    return *Queues.back();
   }
 
-  return true;
-}
-
-template<typename Derived>
-bool RecursiveASTVisitor<Derived>::Walk(Stmt *S) {
-
-#define DISPATCH_WALK(NAME, CLASS, VAR) \
-  return getDerived().WalkUpFrom##NAME(static_cast<CLASS*>(VAR));
-
-  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(S)) {
-    switch (BinOp->getOpcode()) {
-#define OPERATOR(NAME) \
-    case BO_##NAME: DISPATCH_WALK(Bin##NAME, BinaryOperator, S);
-
-    BINOP_LIST()
-#undef OPERATOR
-
-#define OPERATOR(NAME)                                          \
-    case BO_##NAME##Assign:                          \
-    DISPATCH_WALK(Bin##NAME##Assign, CompoundAssignOperator, S);
-
-    CAO_LIST()
-#undef OPERATOR
-    }
-  } else if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S)) {
-    switch (UnOp->getOpcode()) {
-#define OPERATOR(NAME)                                                  \
-    case UO_##NAME: DISPATCH_WALK(Unary##NAME, UnaryOperator, S);
-
-    UNARYOP_LIST()
-#undef OPERATOR
+public:
+  class StmtQueueAction {
+    StmtsTy &CurrQueue;
+  public:
+    explicit StmtQueueAction(RecursiveASTVisitor &RAV)
+      : CurrQueue(RAV.getCurrentQueue()) { }
+
+    void queue(Stmt *S) {
+      CurrQueue.push_back(S);
     }
-  }
-
-  // Top switch stmt: dispatch to TraverseFooStmt for each concrete FooStmt.
-  switch (S->getStmtClass()) {
-  case Stmt::NoStmtClass: break;
-#define ABSTRACT_STMT(STMT)
-#define STMT(CLASS, PARENT) \
-  case Stmt::CLASS##Class: DISPATCH_WALK(CLASS, CLASS, S);
-#include "clang/AST/StmtNodes.inc"
-  }
-
-#undef DISPATCH_WALK
-
-  return true;
-}
+  };
+};
 
 #define DISPATCH(NAME, CLASS, VAR) \
   return getDerived().Traverse##NAME(static_cast<CLASS*>(VAR))
@@ -509,47 +446,65 @@ bool RecursiveASTVisitor<Derived>::TraverseStmt(Stmt *S) {
   if (!S)
     return true;
 
-  if (getDerived().shouldUseDataRecursionFor(S))
-    return dataTraverse(S);
+  StmtsTy Queue, StmtsToEnqueu;
+  Queue.push_back(S);
+  NewQueueRAII NQ(StmtsToEnqueu, *this);
+
+  while (!Queue.empty()) {
+    S = Queue.pop_back_val();
+    if (!S)
+      continue;
+
+    StmtsToEnqueu.clear();
 
-  // If we have a binary expr, dispatch to the subcode of the binop.  A smart
-  // optimizer (e.g. LLVM) will fold this comparison into the switch stmt
-  // below.
-  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(S)) {
-    switch (BinOp->getOpcode()) {
-#define OPERATOR(NAME) \
-    case BO_##NAME: DISPATCH(Bin##NAME, BinaryOperator, S);
+#define DISPATCH_STMT(NAME, CLASS, VAR) \
+    TRY_TO(Traverse##NAME(static_cast<CLASS*>(VAR))); break
 
-    BINOP_LIST()
+    // If we have a binary expr, dispatch to the subcode of the binop.  A smart
+    // optimizer (e.g. LLVM) will fold this comparison into the switch stmt
+    // below.
+    if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(S)) {
+      switch (BinOp->getOpcode()) {
+#define OPERATOR(NAME) \
+      case BO_##NAME: DISPATCH_STMT(Bin##NAME, BinaryOperator, S);
+  
+      BINOP_LIST()
 #undef OPERATOR
 #undef BINOP_LIST
-
+  
 #define OPERATOR(NAME)                                          \
-    case BO_##NAME##Assign:                          \
-      DISPATCH(Bin##NAME##Assign, CompoundAssignOperator, S);
-
-    CAO_LIST()
+      case BO_##NAME##Assign:                          \
+        DISPATCH_STMT(Bin##NAME##Assign, CompoundAssignOperator, S);
+  
+      CAO_LIST()
 #undef OPERATOR
 #undef CAO_LIST
-    }
-  } else if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S)) {
-    switch (UnOp->getOpcode()) {
+      }
+    } else if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S)) {
+      switch (UnOp->getOpcode()) {
 #define OPERATOR(NAME)                                                  \
-    case UO_##NAME: DISPATCH(Unary##NAME, UnaryOperator, S);
-
-    UNARYOP_LIST()
+      case UO_##NAME: DISPATCH_STMT(Unary##NAME, UnaryOperator, S);
+  
+      UNARYOP_LIST()
 #undef OPERATOR
 #undef UNARYOP_LIST
-    }
-  }
-
-  // Top switch stmt: dispatch to TraverseFooStmt for each concrete FooStmt.
-  switch (S->getStmtClass()) {
-  case Stmt::NoStmtClass: break;
+      }
+    } else {
+  
+      // Top switch stmt: dispatch to TraverseFooStmt for each concrete FooStmt.
+      switch (S->getStmtClass()) {
+      case Stmt::NoStmtClass: break;
 #define ABSTRACT_STMT(STMT)
 #define STMT(CLASS, PARENT) \
-  case Stmt::CLASS##Class: DISPATCH(CLASS, CLASS, S);
+      case Stmt::CLASS##Class: DISPATCH_STMT(CLASS, CLASS, S);
 #include "clang/AST/StmtNodes.inc"
+      }
+    }
+
+    for (SmallVector<Stmt *, 8>::reverse_iterator
+           RI = StmtsToEnqueu.rbegin(),
+           RE = StmtsToEnqueu.rend(); RI != RE; ++RI)
+      Queue.push_back(*RI);
   }
 
   return true;
@@ -1379,35 +1334,20 @@ bool RecursiveASTVisitor<Derived>::TraverseTemplateParameterListHelper(
 }
 
 // A helper method for traversing the implicit instantiations of a
-// class.
+// class template.
 template<typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseClassInstantiations(
-  ClassTemplateDecl* D, Decl *Pattern) {
-  assert(isa<ClassTemplateDecl>(Pattern) ||
-         isa<ClassTemplatePartialSpecializationDecl>(Pattern));
-
+    ClassTemplateDecl *D) {
   ClassTemplateDecl::spec_iterator end = D->spec_end();
   for (ClassTemplateDecl::spec_iterator it = D->spec_begin(); it != end; ++it) {
     ClassTemplateSpecializationDecl* SD = *it;
 
     switch (SD->getSpecializationKind()) {
     // Visit the implicit instantiations with the requested pattern.
-    case TSK_ImplicitInstantiation: {
-      llvm::PointerUnion<ClassTemplateDecl *,
-                         ClassTemplatePartialSpecializationDecl *> U
-        = SD->getInstantiatedFrom();
-
-      bool ShouldVisit;
-      if (U.is<ClassTemplateDecl*>())
-        ShouldVisit = (U.get<ClassTemplateDecl*>() == Pattern);
-      else
-        ShouldVisit
-          = (U.get<ClassTemplatePartialSpecializationDecl*>() == Pattern);
-
-      if (ShouldVisit)
-        TRY_TO(TraverseDecl(SD));
+    case TSK_Undeclared:
+    case TSK_ImplicitInstantiation:
+      TRY_TO(TraverseDecl(SD));
       break;
-    }
 
     // We don't need to do anything on an explicit instantiation
     // or explicit specialization because there will be an explicit
@@ -1416,11 +1356,6 @@ bool RecursiveASTVisitor<Derived>::TraverseClassInstantiations(
     case TSK_ExplicitInstantiationDefinition:
     case TSK_ExplicitSpecialization:
       break;
-
-    // We don't need to do anything for an uninstantiated
-    // specialization.
-    case TSK_Undeclared:
-      break;
     }
   }
 
@@ -1435,12 +1370,12 @@ DEF_TRAVERSE_DECL(ClassTemplateDecl, {
     // By default, we do not traverse the instantiations of
     // class templates since they do not appear in the user code. The
     // following code optionally traverses them.
-    if (getDerived().shouldVisitTemplateInstantiations()) {
-      // If this is the definition of the primary template, visit
-      // instantiations which were formed from this pattern.
-      if (D->isThisDeclarationADefinition())
-        TRY_TO(TraverseClassInstantiations(D, D));
-    }
+    //
+    // We only traverse the class instantiations when we see the canonical
+    // declaration of the template, to ensure we only visit them once.
+    if (getDerived().shouldVisitTemplateInstantiations() &&
+        D == D->getCanonicalDecl())
+      TRY_TO(TraverseClassInstantiations(D));
 
     // Note that getInstantiatedFromMemberTemplate() is just a link
     // from a template instantiation back to the template from which
@@ -1451,12 +1386,13 @@ DEF_TRAVERSE_DECL(ClassTemplateDecl, {
 // function while skipping its specializations.
 template<typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseFunctionInstantiations(
-  FunctionTemplateDecl* D) {
+    FunctionTemplateDecl *D) {
   FunctionTemplateDecl::spec_iterator end = D->spec_end();
   for (FunctionTemplateDecl::spec_iterator it = D->spec_begin(); it != end;
        ++it) {
     FunctionDecl* FD = *it;
     switch (FD->getTemplateSpecializationKind()) {
+    case TSK_Undeclared:
     case TSK_ImplicitInstantiation:
       // We don't know what kind of FunctionDecl this is.
       TRY_TO(TraverseDecl(FD));
@@ -1468,7 +1404,6 @@ bool RecursiveASTVisitor<Derived>::TraverseFunctionInstantiations(
     case TSK_ExplicitInstantiationDefinition:
       break;
 
-    case TSK_Undeclared:           // Declaration of the template definition.
     case TSK_ExplicitSpecialization:
       break;
     }
@@ -1482,19 +1417,14 @@ DEF_TRAVERSE_DECL(FunctionTemplateDecl, {
     TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));
 
     // By default, we do not traverse the instantiations of
-    // function templates since they do not apprear in the user code. The
+    // function templates since they do not appear in the user code. The
     // following code optionally traverses them.
-    if (getDerived().shouldVisitTemplateInstantiations()) {
-      // Explicit function specializations will be traversed from the
-      // context of their declaration. There is therefore no need to
-      // traverse them for here.
-      //
-      // In addition, we only traverse the function instantiations when
-      // the function template is a function template definition.
-      if (D->isThisDeclarationADefinition()) {
-        TRY_TO(TraverseFunctionInstantiations(D));
-      }
-    }
+    //
+    // We only traverse the function instantiations when we see the canonical
+    // declaration of the template, to ensure we only visit them once.
+    if (getDerived().shouldVisitTemplateInstantiations() &&
+        D == D->getCanonicalDecl())
+      TRY_TO(TraverseFunctionInstantiations(D));
   })
 
 DEF_TRAVERSE_DECL(TemplateTemplateParmDecl, {
@@ -1569,7 +1499,7 @@ bool RecursiveASTVisitor<Derived>::TraverseCXXRecordHelper(
     CXXRecordDecl *D) {
   if (!TraverseRecordHelper(D))
     return false;
-  if (D->hasDefinition()) {
+  if (D->isCompleteDefinition()) {
     for (CXXRecordDecl::base_class_iterator I = D->bases_begin(),
                                             E = D->bases_end();
          I != E; ++I) {
@@ -1636,11 +1566,7 @@ DEF_TRAVERSE_DECL(ClassTemplatePartialSpecializationDecl, {
     // template args here.
     TRY_TO(TraverseCXXRecordHelper(D));
 
-    // If we're visiting instantiations, visit the instantiations of
-    // this template now.
-    if (getDerived().shouldVisitTemplateInstantiations() &&
-        D->isThisDeclarationADefinition())
-      TRY_TO(TraverseClassInstantiations(D->getSpecializedTemplate(), D));
+    // Instantiations will have been visited with the primary template.
   })
 
 DEF_TRAVERSE_DECL(EnumConstantDecl, {
@@ -1818,23 +1744,24 @@ DEF_TRAVERSE_DECL(ParmVarDecl, {
 template<typename Derived>                                              \
 bool RecursiveASTVisitor<Derived>::Traverse##STMT (STMT *S) {           \
   TRY_TO(WalkUpFrom##STMT(S));                                          \
+  StmtQueueAction StmtQueue(*this);                                     \
   { CODE; }                                                             \
   for (Stmt::child_range range = S->children(); range; ++range) {       \
-    TRY_TO(TraverseStmt(*range));                                       \
+    StmtQueue.queue(*range);                                            \
   }                                                                     \
   return true;                                                          \
 }
 
 DEF_TRAVERSE_STMT(AsmStmt, {
-    TRY_TO(TraverseStmt(S->getAsmString()));
+    StmtQueue.queue(S->getAsmString());
     for (unsigned I = 0, E = S->getNumInputs(); I < E; ++I) {
-      TRY_TO(TraverseStmt(S->getInputConstraintLiteral(I)));
+      StmtQueue.queue(S->getInputConstraintLiteral(I));
     }
     for (unsigned I = 0, E = S->getNumOutputs(); I < E; ++I) {
-      TRY_TO(TraverseStmt(S->getOutputConstraintLiteral(I)));
+      StmtQueue.queue(S->getOutputConstraintLiteral(I));
     }
     for (unsigned I = 0, E = S->getNumClobbers(); I < E; ++I) {
-      TRY_TO(TraverseStmt(S->getClobber(I)));
+      StmtQueue.queue(S->getClobber(I));
     }
     // children() iterates over inputExpr and outputExpr.
   })
@@ -1963,9 +1890,10 @@ bool RecursiveASTVisitor<Derived>::TraverseInitListExpr(InitListExpr *S) {
   if (InitListExpr *Syn = S->getSyntacticForm())
     S = Syn;
   TRY_TO(WalkUpFromInitListExpr(S));
+  StmtQueueAction StmtQueue(*this);
   // All we need are the default actions.  FIXME: use a helper function.
   for (Stmt::child_range range = S->children(); range; ++range) {
-    TRY_TO(TraverseStmt(*range));
+    StmtQueue.queue(*range);
   }
   return true;
 }
@@ -1977,11 +1905,12 @@ template<typename Derived>
 bool RecursiveASTVisitor<Derived>::
 TraverseGenericSelectionExpr(GenericSelectionExpr *S) {
   TRY_TO(WalkUpFromGenericSelectionExpr(S));
-  TRY_TO(TraverseStmt(S->getControllingExpr()));
+  StmtQueueAction StmtQueue(*this);
+  StmtQueue.queue(S->getControllingExpr());
   for (unsigned i = 0; i != S->getNumAssocs(); ++i) {
     if (TypeSourceInfo *TS = S->getAssocTypeSourceInfo(i))
       TRY_TO(TraverseTypeLoc(TS->getTypeLoc()));
-    TRY_TO(TraverseStmt(S->getAssocExpr(i)));
+    StmtQueue.queue(S->getAssocExpr(i));
   }
   return true;
 }
@@ -1992,13 +1921,14 @@ template<typename Derived>
 bool RecursiveASTVisitor<Derived>::
 TraversePseudoObjectExpr(PseudoObjectExpr *S) {
   TRY_TO(WalkUpFromPseudoObjectExpr(S));
-  TRY_TO(TraverseStmt(S->getSyntacticForm()));
+  StmtQueueAction StmtQueue(*this);
+  StmtQueue.queue(S->getSyntacticForm());
   for (PseudoObjectExpr::semantics_iterator
          i = S->semantics_begin(), e = S->semantics_end(); i != e; ++i) {
     Expr *sub = *i;
     if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(sub))
       sub = OVE->getSourceExpr();
-    TRY_TO(TraverseStmt(sub));
+    StmtQueue.queue(sub);
   }
   return true;
 }
@@ -2062,7 +1992,7 @@ DEF_TRAVERSE_STMT(ArrayTypeTraitExpr, {
   })
 
 DEF_TRAVERSE_STMT(ExpressionTraitExpr, {
-    TRY_TO(TraverseStmt(S->getQueriedExpression()));
+    StmtQueue.queue(S->getQueriedExpression());
   })
 
 DEF_TRAVERSE_STMT(VAArgExpr, {
@@ -2102,7 +2032,8 @@ bool RecursiveASTVisitor<Derived>::TraverseLambdaExpr(LambdaExpr *S) {
     }
   }
 
-  TRY_TO(TraverseStmt(S->getBody()));
+  StmtQueueAction StmtQueue(*this);
+  StmtQueue.queue(S->getBody());
   return true;
 }