From 90226acd0b9be2964343cd63ae604bf0a656d33b Mon Sep 17 00:00:00 2001 From: Argyrios Kyrtzidis Date: Thu, 15 Mar 2012 18:07:19 +0000 Subject: [PATCH] Make RecursiveASTVisitor to traverse certain statements using data recursion to avoid a stack overflow with extreme cases. Part of rdar://10941790. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@152820 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/RecursiveASTVisitor.h | 103 ++ test/Index/index-many-logical-ops.c | 2011 +++++++++++++++++++++++ 2 files changed, 2114 insertions(+) create mode 100644 test/Index/index-many-logical-ops.c diff --git a/include/clang/AST/RecursiveASTVisitor.h b/include/clang/AST/RecursiveASTVisitor.h index f3dcf71f5f..a4ad525701 100644 --- a/include/clang/AST/RecursiveASTVisitor.h +++ b/include/clang/AST/RecursiveASTVisitor.h @@ -148,6 +148,12 @@ 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(S) || isa(S) || isa(S); + } + /// \brief Recursively visit a statement or expression, by /// dispatching to Traverse*() based on the argument's dynamic type. /// @@ -397,8 +403,102 @@ private: bool TraverseDeclContextHelper(DeclContext *DC); 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(S)) + S = E->IgnoreParens(); + } + }; + bool dataTraverse(Stmt *S); }; +template +bool RecursiveASTVisitor::dataTraverse(Stmt *S) { + + SmallVector Queue; + Queue.push_back(S); + + while (!Queue.empty()) { + EnqueueJob &job = Queue.back(); + Stmt *CurrS = job.S; + if (!CurrS) { + Queue.pop_back(); + continue; + } + + 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; + } + + Queue.pop_back(); + TRY_TO(TraverseStmt(CurrS)); + } + + return true; +} + +template +bool RecursiveASTVisitor::Walk(Stmt *S) { + +#define DISPATCH_WALK(NAME, CLASS, VAR) \ + return getDerived().WalkUpFrom##NAME(static_cast(VAR)); + + if (BinaryOperator *BinOp = dyn_cast(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(S)) { + switch (UnOp->getOpcode()) { +#define OPERATOR(NAME) \ + case UO_##NAME: DISPATCH_WALK(Unary##NAME, UnaryOperator, S); + + UNARYOP_LIST() +#undef OPERATOR + } + } + + // 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(VAR)) @@ -407,6 +507,9 @@ bool RecursiveASTVisitor::TraverseStmt(Stmt *S) { if (!S) return true; + if (getDerived().shouldUseDataRecursionFor(S)) + return dataTraverse(S); + // 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. diff --git a/test/Index/index-many-logical-ops.c b/test/Index/index-many-logical-ops.c new file mode 100644 index 0000000000..67017decb7 --- /dev/null +++ b/test/Index/index-many-logical-ops.c @@ -0,0 +1,2011 @@ +// RUN: c-index-test -index-file %s | FileCheck %s + +// rdar://10941790 +// Check that we don't get stack overflow trying to index a huge number of +// logical operators. + +// CHECK: [indexDeclaration]: kind: function | name: foo +int foo(int x) { + return + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x && + x; +} -- 2.40.0