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.

llvm-svn: 285570

1 files changed, 15 insertions, 0 deletions

diff --git a/clang/lib/Format/TokenAnnotator.cpp b/clang/lib/Format/TokenAnnotator.cpp
index 9237fc6ec53..1253e56c986 100644
--- a/clang/lib/Format/TokenAnnotator.cpp
+++ b/clang/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<AnnotatedLine *>::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;