I'd say eventually yes. But for me it is by far not the most pressing thing right now.
On Wed, Jan 16, 2013 at 7:31 PM, Nico Weber <[email protected]> wrote: > 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
