From c3014c9312dc8eafe7e27a2d47457c62e8146de8 Mon Sep 17 00:00:00 2001 From: Daniel Jasper Date: Mon, 31 Oct 2016 13:23:00 +0000 Subject: [PATCH] Skip over AnnotatedLines with >50 levels of nesting; don't format them. Reasoning: - ExpressionParser uses a lot of stack for these, bad in some environments. - Our formatting algorithm is N^3 and gets really slow. - The resulting formatting is unlikely to be any good. - This is probably generated code we're formatting by accident. We treat these as unparseable, and signal incomplete formatting. 50 is an arbitrary number, I've only seen real problems from ~150 levels. Patch by Sam McCall. Thank you. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@285570 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Format/TokenAnnotator.cpp | 15 +++++++++++++++ unittests/Format/FormatTest.cpp | 24 ++++++++++++++++++++++++ 2 files changed, 39 insertions(+) diff --git a/lib/Format/TokenAnnotator.cpp b/lib/Format/TokenAnnotator.cpp index 9237fc6ec5..1253e56c98 100644 --- a/lib/Format/TokenAnnotator.cpp +++ b/lib/Format/TokenAnnotator.cpp @@ -1566,6 +1566,13 @@ void TokenAnnotator::setCommentLineLevels( } } +static unsigned maxNestingDepth(const AnnotatedLine &Line) { + unsigned Result = 0; + for (const auto* Tok = Line.First; Tok != nullptr; Tok = Tok->Next) + Result = std::max(Result, Tok->NestingLevel); + return Result; +} + void TokenAnnotator::annotate(AnnotatedLine &Line) { for (SmallVectorImpl::iterator I = Line.Children.begin(), E = Line.Children.end(); @@ -1574,6 +1581,14 @@ void TokenAnnotator::annotate(AnnotatedLine &Line) { } AnnotatingParser Parser(Style, Line, Keywords); Line.Type = Parser.parseLine(); + + // With very deep nesting, ExpressionParser uses lots of stack and the + // formatting algorithm is very slow. We're not going to do a good job here + // anyway - it's probably generated code being formatted by mistake. + // Just skip the whole line. + if (maxNestingDepth(Line) > 50) + Line.Type = LT_Invalid; + if (Line.Type == LT_Invalid) return; diff --git a/unittests/Format/FormatTest.cpp b/unittests/Format/FormatTest.cpp index ee08121c5a..b95a29f781 100644 --- a/unittests/Format/FormatTest.cpp +++ b/unittests/Format/FormatTest.cpp @@ -7179,6 +7179,30 @@ TEST_F(FormatTest, SpecialTokensAtEndOfLine) { verifyFormat("operator"); } +TEST_F(FormatTest, SkipsDeeplyNestedLines) { + // This code would be painfully slow to format if we didn't skip it. + std::string Code("A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(\n" // 20x + "A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(\n" + "A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(\n" + "A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(\n" + "A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(\n" + "A(1, 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" // 10x + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1)\n" + ", 1), 1), 1), 1), 1), 1), 1), 1), 1), 1);\n"); + // Deeply nested part is untouched, rest is formatted. + EXPECT_EQ(std::string("int i;\n") + Code + "int j;\n", + format(std::string("int i;\n") + Code + "int j;\n", + getLLVMStyle(), IC_ExpectIncomplete)); +} + //===----------------------------------------------------------------------===// // Objective-C tests. //===----------------------------------------------------------------------===// -- 2.40.0