commit cbb6c41f3cec4a940201a8e2e65743c9f26c3673
author Daniel Jasper <djasper@google.com> Wed Jan 16 09:10:19 2013 +0000
committer Daniel Jasper <djasper@google.com> Wed Jan 16 09:10:19 2013 +0000
tree 0db68e00f9edf572da749ae9323932160d65cdba
parent 6b825c2e1e691deca41c6f979164b5d20c203593

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

lib/Format/UnwrappedLineParser.cpp

diff --git a/lib/Format/UnwrappedLineParser.cpp b/lib/Format/UnwrappedLineParser.cpp
index fe522ac..9a29ff0 100644
--- a/lib/Format/UnwrappedLineParser.cpp
+++ b/lib/Format/UnwrappedLineParser.cpp
@@ -81,25 +81,17 @@
 public:
   ScopedLineState(UnwrappedLineParser &Parser) : Parser(Parser) {
     PreBlockLine = Parser.Line.take();
-    Parser.Line.reset(new UnwrappedLine(*PreBlockLine));
-    assert(Parser.LastInCurrentLine == NULL ||
-           Parser.LastInCurrentLine->Children.empty());
-    PreBlockLastToken = Parser.LastInCurrentLine;
-    PreBlockRootTokenInitialized = Parser.RootTokenInitialized;
-    Parser.RootTokenInitialized = false;
-    Parser.LastInCurrentLine = NULL;
+    Parser.Line.reset(new UnwrappedLine());
+    Parser.Line->Level = PreBlockLine->Level;
+    Parser.Line->InPPDirective = PreBlockLine->InPPDirective;
   }
 
   ~ScopedLineState() {
-    if (Parser.RootTokenInitialized) {
+    if (!Parser.Line->Tokens.empty()) {
       Parser.addUnwrappedLine();
     }
-    assert(!Parser.RootTokenInitialized);
+    assert(Parser.Line->Tokens.empty());
     Parser.Line.reset(PreBlockLine);
-    Parser.RootTokenInitialized = PreBlockRootTokenInitialized;
-    Parser.LastInCurrentLine = PreBlockLastToken;
-    assert(Parser.LastInCurrentLine == NULL ||
-           Parser.LastInCurrentLine->Children.empty());
     Parser.MustBreakBeforeNextToken = true;
   }
 
@@ -107,15 +99,12 @@
   UnwrappedLineParser &Parser;
 
   UnwrappedLine *PreBlockLine;
-  FormatToken* PreBlockLastToken;
-  bool PreBlockRootTokenInitialized;
 };
 
 UnwrappedLineParser::UnwrappedLineParser(
     clang::DiagnosticsEngine &Diag, const FormatStyle &Style,
     FormatTokenSource &Tokens, UnwrappedLineConsumer &Callback)
-    : Line(new UnwrappedLine), RootTokenInitialized(false),
-      LastInCurrentLine(NULL), MustBreakBeforeNextToken(false), Diag(Diag),
+    : Line(new UnwrappedLine), MustBreakBeforeNextToken(false), Diag(Diag),
       Style(Style), Tokens(&Tokens), Callback(Callback) {
 }
 
@@ -659,7 +648,7 @@
 }
 
 void UnwrappedLineParser::addUnwrappedLine() {
-  if (!RootTokenInitialized)
+  if (Line->Tokens.empty())
     return;
   // Consume trailing comments.
   while (!eof() && FormatTok.NewlinesBefore == 0 &&
@@ -667,17 +656,17 @@
     nextToken();
   }
 #ifdef UNWRAPPED_LINE_PARSER_DEBUG_OUTPUT
-  FormatToken* NextToken = &Line->RootToken;
   llvm::errs() << "Line: ";
-  while (NextToken) {
-    llvm::errs() << NextToken->Tok.getName() << " ";
-    NextToken = NextToken->Children.empty() ? NULL : &NextToken->Children[0];
+  for (std::list<FormatToken>::iterator I = Line->Tokens.begin(),
+                                        E = Line->Tokens.end();
+       I != E; ++I) {
+    llvm::errs() << I->Tok.getName() << " ";
+
   }
   llvm::errs() << "\n";
 #endif
   Callback.consumeUnwrappedLine(*Line);
-  RootTokenInitialized = false;
-  LastInCurrentLine = NULL;
+  Line->Tokens.clear();
 }
 
 bool UnwrappedLineParser::eof() const {
@@ -687,17 +676,9 @@
 void UnwrappedLineParser::nextToken() {
   if (eof())
     return;
-  if (RootTokenInitialized) {
-    assert(LastInCurrentLine->Children.empty());
-    LastInCurrentLine->Children.push_back(FormatTok);
-    LastInCurrentLine = &LastInCurrentLine->Children.back();
-  } else {
-    Line->RootToken = FormatTok;
-    RootTokenInitialized = true;
-    LastInCurrentLine = &Line->RootToken;
-  }
+  Line->Tokens.push_back(FormatTok);
   if (MustBreakBeforeNextToken) {
-    LastInCurrentLine->MustBreakBefore = true;
+    Line->Tokens.back().MustBreakBefore = true;
     MustBreakBeforeNextToken = false;
   }
   readToken();