sammccall created this revision.
sammccall added a reviewer: djasper.
sammccall added a subscriber: cfe-commits.
Herald added a subscriber: klimek.
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.
https://reviews.llvm.org/D26132
Files:
lib/Format/TokenAnnotator.cpp
unittests/Format/FormatTest.cpp
Index: unittests/Format/FormatTest.cpp
===================================================================
--- unittests/Format/FormatTest.cpp
+++ unittests/Format/FormatTest.cpp
@@ -7179,6 +7179,30 @@
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.
//===----------------------------------------------------------------------===//
Index: lib/Format/TokenAnnotator.cpp
===================================================================
--- lib/Format/TokenAnnotator.cpp
+++ lib/Format/TokenAnnotator.cpp
@@ -1566,14 +1566,29 @@
}
}
+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<AnnotatedLine *>::iterator I = Line.Children.begin(),
E = Line.Children.end();
I != E; ++I) {
annotate(**I);
}
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;
Index: unittests/Format/FormatTest.cpp
===================================================================
--- unittests/Format/FormatTest.cpp
+++ unittests/Format/FormatTest.cpp
@@ -7179,6 +7179,30 @@
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.
//===----------------------------------------------------------------------===//
Index: lib/Format/TokenAnnotator.cpp
===================================================================
--- lib/Format/TokenAnnotator.cpp
+++ lib/Format/TokenAnnotator.cpp
@@ -1566,14 +1566,29 @@
}
}
+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<AnnotatedLine *>::iterator I = Line.Children.begin(),
E = Line.Children.end();
I != E; ++I) {
annotate(**I);
}
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;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
