Change the datastructure for UnwrappedLines.

It was quite convoluted leading to us accidentally introducing O(N^2)
complexity while copying from UnwrappedLine to AnnotatedLine. We might
still want to improve the datastructure in AnnotatedLine (most
importantly not put them in a vector where they need to be copied on
vector resizing but that will be done as a follow-up.

This fixes most of the regression in llvm.org/PR14959.

No formatting changes intended.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@172602 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 25 insertions, 18 deletions

diff --git a/lib/Format/Format.cpp b/lib/Format/Format.cpp
index 939038e2a5..dbed75c3f1 100644
--- a/lib/Format/Format.cpp
+++ b/lib/Format/Format.cpp
@@ -92,9 +92,30 @@ public:
 
 class AnnotatedLine {
 public:
-  AnnotatedLine(const FormatToken &FormatTok, unsigned Level,
-                bool InPPDirective)
-      : First(FormatTok), Level(Level), InPPDirective(InPPDirective) {}
+  AnnotatedLine(const UnwrappedLine &Line)
+      : First(Line.Tokens.front()), Level(Line.Level),
+        InPPDirective(Line.InPPDirective) {
+    assert(!Line.Tokens.empty());
+    AnnotatedToken *Current = &First;
+    for (std::list<FormatToken>::const_iterator I = ++Line.Tokens.begin(),
+                                                E = Line.Tokens.end();
+         I != E; ++I) {
+      Current->Children.push_back(*I);
+      Current->Children[0].Parent = Current;
+      Current = &Current->Children[0];
+    }
+    Last = Current;
+  }
+  AnnotatedLine(const AnnotatedLine &Other)
+      : First(Other.First), Type(Other.Type), Level(Other.Level),
+        InPPDirective(Other.InPPDirective) {
+    Last = &First;
+    while (!Last->Children.empty()) {
+      Last->Children[0].Parent = Last;
+      Last = &Last->Children[0];
+    }
+  }
+
   AnnotatedToken First;
   AnnotatedToken *Last;
 
@@ -945,16 +966,6 @@ public:
     bool ColonIsObjCMethodExpr;
   };
 
-  void createAnnotatedTokens(AnnotatedToken &Current) {
-    if (Current.FormatTok.Children.empty()) {
-      Line.Last = &Current;
-    } else {
-      Current.Children.push_back(AnnotatedToken(Current.FormatTok.Children[0]));
-      Current.Children.back().Parent = &Current;
-      createAnnotatedTokens(Current.Children.back());
-    }
-  }
-
   void calculateExtraInformation(AnnotatedToken &Current) {
     Current.SpaceRequiredBefore = spaceRequiredBefore(Current);
 
@@ -978,9 +989,6 @@ public:
   }
 
   void annotate() {
-    Line.Last = &Line.First;
-    createAnnotatedTokens(Line.First);
-
     AnnotatingParser Parser(Line.First);
     Line.Type = Parser.parseLine();
     if (Line.Type == LT_Invalid)
@@ -1619,8 +1627,7 @@ private:
   }
 
   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
-    AnnotatedLines.push_back(
-        AnnotatedLine(TheLine.RootToken, TheLine.Level, TheLine.InPPDirective));
+    AnnotatedLines.push_back(AnnotatedLine(TheLine));
   }
 
   /// \brief Add a new line and the required indent before the first Token