On Wed, Jan 16, 2013 at 1:10 AM, Daniel Jasper <[email protected]> wrote: > Author: djasper > Date: Wed Jan 16 03:10:19 2013 > New Revision: 172602 > > URL: http://llvm.org/viewvc/llvm-project?rev=172602&view=rev > Log: > 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.
Thanks! Do you think it makes sense to have an automated perf test for libFormat? > > No formatting changes intended. > > Modified: > cfe/trunk/lib/Format/Format.cpp > cfe/trunk/lib/Format/UnwrappedLineParser.cpp > cfe/trunk/lib/Format/UnwrappedLineParser.h > > Modified: cfe/trunk/lib/Format/Format.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Format/Format.cpp?rev=172602&r1=172601&r2=172602&view=diff > ============================================================================== > --- cfe/trunk/lib/Format/Format.cpp (original) > +++ cfe/trunk/lib/Format/Format.cpp Wed Jan 16 03:10:19 2013 > @@ -92,9 +92,30 @@ > > 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 @@ > 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 @@ > } > > 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 @@ > } > > 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 > > Modified: cfe/trunk/lib/Format/UnwrappedLineParser.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Format/UnwrappedLineParser.cpp?rev=172602&r1=172601&r2=172602&view=diff > ============================================================================== > --- cfe/trunk/lib/Format/UnwrappedLineParser.cpp (original) > +++ cfe/trunk/lib/Format/UnwrappedLineParser.cpp Wed Jan 16 03:10:19 2013 > @@ -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(); > > Modified: cfe/trunk/lib/Format/UnwrappedLineParser.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Format/UnwrappedLineParser.h?rev=172602&r1=172601&r2=172602&view=diff > ============================================================================== > --- cfe/trunk/lib/Format/UnwrappedLineParser.h (original) > +++ cfe/trunk/lib/Format/UnwrappedLineParser.h Wed Jan 16 03:10:19 2013 > @@ -24,7 +24,7 @@ > #include "clang/Format/Format.h" > #include "clang/Lex/Lexer.h" > > -#include <vector> > +#include <list> > > namespace clang { > > @@ -76,11 +76,6 @@ > /// This happens for example when a preprocessor directive ended directly > /// before the token. > bool MustBreakBefore; > - > - // FIXME: We currently assume that there is exactly one token in this > vector > - // except for the very last token that does not have any children. > - /// \brief All tokens that logically follow this token. > - std::vector<FormatToken> Children; > }; > > /// \brief An unwrapped line is a sequence of \c Token, that we would like to > @@ -93,8 +88,8 @@ > UnwrappedLine() : Level(0), InPPDirective(false) { > } > > - /// \brief The \c Token comprising this \c UnwrappedLine. > - FormatToken RootToken; > + /// \brief The \c Tokens comprising this \c UnwrappedLine. > + std::list<FormatToken> Tokens; > > /// \brief The indent level of the \c UnwrappedLine. > unsigned Level; > @@ -160,8 +155,6 @@ > // subtracted from beyond 0. Introduce a method to subtract from Line.Level > // and use that everywhere in the Parser. > OwningPtr<UnwrappedLine> Line; > - bool RootTokenInitialized; > - FormatToken *LastInCurrentLine; > FormatToken FormatTok; > bool MustBreakBeforeNextToken; > > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
