From d579dd5cc43e657647f38be5dd47c8974cd43108 Mon Sep 17 00:00:00 2001 From: Argyrios Kyrtzidis Date: Sat, 1 Sep 2012 18:27:30 +0000 Subject: [PATCH] [libclang] The annotation of tokens operation visits statement nodes code-recursively. This can blow the stack with extremely deep hierarchies. Switch it to data-recursive. This is implemented by introducing a post-children visitation callback that the CursorVisitor is calling after child nodes of a cursor have been visited. This is used by the annotate-tokens visitor to do extra work at that point. rdar://11979525. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@163071 91177308-0d34-0410-b5e6-96231b3b80d8 --- test/Index/annotate-deep-statements.cpp | 95 +++++++++++++++++++++++++ tools/libclang/CIndex.cpp | 76 +++++++++++++++++--- tools/libclang/CursorVisitor.h | 17 ++++- 3 files changed, 176 insertions(+), 12 deletions(-) create mode 100644 test/Index/annotate-deep-statements.cpp diff --git a/test/Index/annotate-deep-statements.cpp b/test/Index/annotate-deep-statements.cpp new file mode 100644 index 0000000000..32a48b7d6a --- /dev/null +++ b/test/Index/annotate-deep-statements.cpp @@ -0,0 +1,95 @@ +// RUN: c-index-test -test-annotate-tokens=%s:1:1:1000:1 %s | FileCheck %s + +// rdar://11979525 +// Check that we don't get stack overflow trying to annotate an extremely deep AST. + +struct S { + S &operator()(); +}; + +// CHECK: Identifier: "foo" [11:6 - 11:9] FunctionDecl=foo:11:6 (Definition) +void foo() { + S s; + s()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()() + ; +} diff --git a/tools/libclang/CIndex.cpp b/tools/libclang/CIndex.cpp index 9e261de964..ae488abf39 100644 --- a/tools/libclang/CIndex.cpp +++ b/tools/libclang/CIndex.cpp @@ -182,8 +182,13 @@ bool CursorVisitor::Visit(CXCursor Cursor, bool CheckedRegionOfInterest) { case CXChildVisit_Continue: return false; - case CXChildVisit_Recurse: - return VisitChildren(Cursor); + case CXChildVisit_Recurse: { + bool ret = VisitChildren(Cursor); + if (PostChildrenVisitor) + if (PostChildrenVisitor(Cursor, ClientData)) + return true; + return ret; + } } llvm_unreachable("Invalid CXChildVisitResult!"); @@ -1632,6 +1637,7 @@ DEF_JOB(ExplicitTemplateArgsVisit, ASTTemplateArgumentListInfo, ExplicitTemplateArgsVisitKind) DEF_JOB(SizeOfPackExprParts, SizeOfPackExpr, SizeOfPackExprPartsKind) DEF_JOB(LambdaExprParts, LambdaExpr, LambdaExprPartsKind) +DEF_JOB(PostChildrenVisit, void, PostChildrenVisitKind) #undef DEF_JOB class DeclVisit : public VisitorJob { @@ -2208,6 +2214,8 @@ bool CursorVisitor::RunVisitorWorkList(VisitorWorkList &WL) { case CXChildVisit_Break: return true; case CXChildVisit_Continue: break; case CXChildVisit_Recurse: + if (PostChildrenVisitor) + WL.push_back(PostChildrenVisit(0, Cursor)); EnqueueWorkList(WL, S); break; } @@ -2324,6 +2332,11 @@ bool CursorVisitor::RunVisitorWorkList(VisitorWorkList &WL) { } break; } + + case VisitorJob::PostChildrenVisitKind: + if (PostChildrenVisitor(Parent, ClientData)) + return true; + break; } } return false; @@ -4819,6 +4832,9 @@ typedef llvm::DenseMap AnnotateTokensData; static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor, CXCursor parent, CXClientData client_data); +static bool AnnotateTokensPostChildrenVisitor(CXCursor cursor, + CXClientData client_data); + namespace { class AnnotateTokensWorker { AnnotateTokensData &Annotated; @@ -4830,6 +4846,13 @@ class AnnotateTokensWorker { CursorVisitor AnnotateVis; SourceManager &SrcMgr; bool HasContextSensitiveKeywords; + + struct PostChildrenInfo { + CXCursor Cursor; + SourceRange CursorRange; + unsigned BeforeChildrenTokenIdx; + }; + llvm::SmallVector PostChildrenInfos; bool MoreTokens() const { return TokIdx < NumTokens; } unsigned NextToken() const { return TokIdx; } @@ -4858,12 +4881,15 @@ public: AnnotateTokensVisitor, this, /*VisitPreprocessorLast=*/true, /*VisitIncludedEntities=*/false, - RegionOfInterest), + RegionOfInterest, + /*VisitDeclsOnly=*/false, + AnnotateTokensPostChildrenVisitor), SrcMgr(static_cast(tu->TUData)->getSourceManager()), HasContextSensitiveKeywords(false) { } void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); } enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent); + bool postVisitChildren(CXCursor cursor); void AnnotateTokens(); /// \brief Determine whether the annotator saw any cursors that have @@ -4871,6 +4897,10 @@ public: bool hasContextSensitiveKeywords() const { return HasContextSensitiveKeywords; } + + ~AnnotateTokensWorker() { + assert(PostChildrenInfos.empty()); + } }; } @@ -5131,25 +5161,47 @@ AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) { } } - // Visit children to get their cursor information. - const unsigned BeforeChildren = NextToken(); - VisitChildren(cursor); + // Before recursing into the children keep some state that we are going + // to use in the AnnotateTokensWorker::postVisitChildren callback to do some + // extra work after the child nodes are visited. + // Note that we don't call VisitChildren here to avoid traversing statements + // code-recursively which can blow the stack. + + PostChildrenInfo Info; + Info.Cursor = cursor; + Info.CursorRange = cursorRange; + Info.BeforeChildrenTokenIdx = NextToken(); + PostChildrenInfos.push_back(Info); + + return CXChildVisit_Recurse; +} + +bool AnnotateTokensWorker::postVisitChildren(CXCursor cursor) { + if (PostChildrenInfos.empty()) + return false; + const PostChildrenInfo &Info = PostChildrenInfos.back(); + if (!clang_equalCursors(Info.Cursor, cursor)) + return false; + + const unsigned BeforeChildren = Info.BeforeChildrenTokenIdx; const unsigned AfterChildren = NextToken(); + SourceRange cursorRange = Info.CursorRange; // Scan the tokens that are at the end of the cursor, but are not captured // but the child cursors. annotateAndAdvanceTokens(cursor, RangeOverlap, cursorRange); - + // Scan the tokens that are at the beginning of the cursor, but are not // capture by the child cursors. for (unsigned I = BeforeChildren; I != AfterChildren; ++I) { if (!clang_isInvalid(clang_getCursorKind(Cursors[I]))) break; - + Cursors[I] = cursor; } - return CXChildVisit_Continue; + PostChildrenInfos.pop_back(); + return false; } static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor, @@ -5158,6 +5210,12 @@ static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor, return static_cast(client_data)->Visit(cursor, parent); } +static bool AnnotateTokensPostChildrenVisitor(CXCursor cursor, + CXClientData client_data) { + return static_cast(client_data)-> + postVisitChildren(cursor); +} + namespace { /// \brief Uses the macro expansions in the preprocessing record to find diff --git a/tools/libclang/CursorVisitor.h b/tools/libclang/CursorVisitor.h index 88b70a490e..404af94e2e 100644 --- a/tools/libclang/CursorVisitor.h +++ b/tools/libclang/CursorVisitor.h @@ -32,7 +32,7 @@ public: NestedNameSpecifierLocVisitKind, DeclarationNameInfoVisitKind, MemberRefVisitKind, SizeOfPackExprPartsKind, - LambdaExprPartsKind }; + LambdaExprPartsKind, PostChildrenVisitKind }; protected: void *data[3]; CXCursor parent; @@ -55,6 +55,13 @@ typedef SmallVector VisitorWorkList; class CursorVisitor : public DeclVisitor, public TypeLocVisitor { +public: + /// \brief Callback called after child nodes of a cursor have been visited. + /// Return true to break visitation or false to continue. + typedef bool (*PostChildrenVisitorTy)(CXCursor cursor, + CXClientData client_data); + +private: /// \brief The translation unit we are traversing. CXTranslationUnit TU; ASTUnit *AU; @@ -69,6 +76,8 @@ class CursorVisitor : public DeclVisitor, /// \brief The visitor function. CXCursorVisitor Visitor; + PostChildrenVisitorTy PostChildrenVisitor; + /// \brief The opaque client data, to be passed along to the visitor. CXClientData ClientData; @@ -137,9 +146,11 @@ public: bool VisitPreprocessorLast, bool VisitIncludedPreprocessingEntries = false, SourceRange RegionOfInterest = SourceRange(), - bool VisitDeclsOnly = false) + bool VisitDeclsOnly = false, + PostChildrenVisitorTy PostChildrenVisitor = 0) : TU(TU), AU(static_cast(TU->TUData)), - Visitor(Visitor), ClientData(ClientData), + Visitor(Visitor), PostChildrenVisitor(PostChildrenVisitor), + ClientData(ClientData), VisitPreprocessorLast(VisitPreprocessorLast), VisitIncludedEntities(VisitIncludedPreprocessingEntries), RegionOfInterest(RegionOfInterest), -- 2.40.0