Sorry, I did not know about that MSVC bug. Workaround submitted in r174169.
On Fri, Feb 1, 2013 at 12:16 PM, Timur Iskhodzhanov <[email protected]>wrote: > Hi Daniel, > > I'm afraid your change breaks the Win build: > > Format.cpp > C:\Program Files (x86)\Microsoft Visual Studio > 10.0\VC\include\utility(163): error C2440: 'initializing' : cannot > convert from 'int' to 'const > clang::format::UnwrappedLineFormatter::LineState *' > [tools\clang\lib\Format\clangFormat.vcxproj] > Conversion from integral type to pointer type requires > reinterpret_cast, C-style cast or function-style cast > C:\Program Files (x86)\Microsoft Visual Studio > 10.0\VC\include\utility(247) : see reference to function template > instantiation 'std::_Pair_base<_Ty1,_Ty2>::_Pair_base<_Ty,int>(_Other1 > &&,_Other2 &&)' being compiled > with > [ > _Ty1=bool, > _Ty2=const clang::format::UnwrappedLineFormatter::LineState > *, > _Ty=bool, > _Other1=bool, > _Other2=int > ] > ..\..\..\..\..\llvm\tools\clang\lib\Format\Format.cpp(598) : > see reference to function template instantiation > 'std::pair<_Ty1,_Ty2>::pair<bool,int>(_Other1 &&,_Other2 &&)' being > compiled > with > [ > _Ty1=bool, > _Ty2=const clang::format::UnwrappedLineFormatter::LineState > *, > _Other1=bool, > _Other2=int > ] > > C:\Program Files (x86)\Microsoft Visual Studio > 10.0\VC\include\utility(163): error C2439: > 'std::_Pair_base<_Ty1,_Ty2>::second' : member could not be initialized > [tools\clang\lib\Format\clangFormat.vcxproj] > with > [ > _Ty1=bool, > _Ty2=const clang::format::UnwrappedLineFormatter::LineState * > ] > C:\Program Files (x86)\Microsoft Visual Studio > 10.0\VC\include\utility(167) : see declaration of > 'std::_Pair_base<_Ty1,_Ty2>::second' > with > [ > _Ty1=bool, > _Ty2=const clang::format::UnwrappedLineFormatter::LineState * > ] > > -- > Timur > > 2013/2/1 Daniel Jasper <[email protected]>: > > Author: djasper > > Date: Fri Feb 1 05:00:45 2013 > > New Revision: 174166 > > > > URL: http://llvm.org/viewvc/llvm-project?rev=174166&view=rev > > Log: > > Revamp of the basic layouting algorithm in clang-format. > > > > In order to end up with good solutions, clang-format needs to try > > "all" combinations of line breaks, evaluate them and select the > > best one. Before, we have done this using a DFS with memoization > > and cut-off conditions. However, this approach is very limited > > as shown by the huge static initializer in the attachment of > > llvm.org/PR14959. > > > > Instead, this new implementation uses a variant of Dijkstra's > > algorithm to do a prioritized BFS over the solution space. > > > > Some numbers: > > lib/Format/TokenAnnotator.cpp: 1.5s -> 0.15s > > Attachment of PR14959: 10min+ (didn't finish) -> 10s > > > > No functional changes intended. > > > > Modified: > > cfe/trunk/lib/Format/Format.cpp > > > > Modified: cfe/trunk/lib/Format/Format.cpp > > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Format/Format.cpp?rev=174166&r1=174165&r2=174166&view=diff > > > ============================================================================== > > --- cfe/trunk/lib/Format/Format.cpp (original) > > +++ cfe/trunk/lib/Format/Format.cpp Fri Feb 1 05:00:45 2013 > > @@ -241,44 +241,16 @@ public: > > // The first token has already been indented and thus consumed. > > moveStateToNextToken(State); > > > > - // Start iterating at 1 as we have correctly formatted of Token #0 > above. > > - while (State.NextToken != NULL) { > > - if (State.NextToken->Type == TT_ImplicitStringLiteral) { > > - // Calculating the column is important for aligning trailing > comments. > > - // FIXME: This does not seem to happen in conjunction with > escaped > > - // newlines. If it does, fix! > > - State.Column += State.NextToken->FormatTok.WhiteSpaceLength + > > - State.NextToken->FormatTok.TokenLength; > > - State.NextToken = State.NextToken->Children.empty() > > - ? NULL : &State.NextToken->Children[0]; > > - } else if (Line.Last->TotalLength <= getColumnLimit() - > FirstIndent) { > > + // If everything fits on a single line, just put it there. > > + if (Line.Last->TotalLength <= getColumnLimit() - FirstIndent) { > > + while (State.NextToken != NULL) { > > addTokenToState(false, false, State); > > - } else { > > - unsigned NoBreak = calcPenalty(State, false, UINT_MAX); > > - unsigned Break = calcPenalty(State, true, NoBreak); > > - DEBUG({ > > - if (Break < NoBreak) > > - llvm::errs() << "\n"; > > - else > > - llvm::errs() << " "; > > - llvm::errs() << "<"; > > - DebugPenalty(Break, Break < NoBreak); > > - llvm::errs() << "/"; > > - DebugPenalty(NoBreak, !(Break < NoBreak)); > > - llvm::errs() << "> "; > > - DebugTokenState(*State.NextToken); > > - }); > > - addTokenToState(Break < NoBreak, false, State); > > - if (State.NextToken != NULL && > > - State.NextToken->Parent->Type == TT_CtorInitializerColon) { > > - if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine && > > - Line.Last->TotalLength > getColumnLimit() - State.Column > - 1) > > - State.Stack.back().BreakAfterComma = true; > > - } > > } > > + return State.Column; > > } > > - DEBUG(llvm::errs() << "\n"); > > - return State.Column; > > + > > + // Find best solution in solution space. > > + return analyzeSolutionSpace(State); > > } > > > > private: > > @@ -289,15 +261,6 @@ private: > > llvm::errs(); > > } > > > > - void DebugPenalty(unsigned Penalty, bool Winner) { > > - llvm::errs().changeColor(Winner ? raw_ostream::GREEN : > raw_ostream::RED); > > - if (Penalty == UINT_MAX) > > - llvm::errs() << "MAX"; > > - else > > - llvm::errs() << Penalty; > > - llvm::errs().resetColor(); > > - } > > - > > struct ParenState { > > ParenState(unsigned Indent, unsigned LastSpace, bool > AvoidBinPacking) > > : Indent(Indent), LastSpace(LastSpace), AssignmentColumn(0), > > @@ -421,6 +384,16 @@ private: > > assert(State.Stack.size()); > > unsigned ParenLevel = State.Stack.size() - 1; > > > > + if (Current.Type == TT_ImplicitStringLiteral) { > > + State.Column += State.NextToken->FormatTok.WhiteSpaceLength + > > + State.NextToken->FormatTok.TokenLength; > > + if (State.NextToken->Children.empty()) > > + State.NextToken = NULL; > > + else > > + State.NextToken = &State.NextToken->Children[0]; > > + return; > > + } > > + > > if (Newline) { > > unsigned WhitespaceStartColumn = State.Column; > > if (Current.is(tok::r_brace)) { > > @@ -604,87 +577,123 @@ private: > > return Style.ColumnLimit - (Line.InPPDirective ? 1 : 0); > > } > > > > - /// \brief Calculate the number of lines needed to format the > remaining part > > - /// of the unwrapped line. > > - /// > > - /// Assumes the formatting so far has led to > > - /// the \c LineSta \p State. If \p NewLine is set, a new line will be > > - /// added after the previous token. > > + /// \brief An edge in the solution space starting from the \c > LineState and > > + /// inserting a newline dependent on the \c bool. > > + typedef std::pair<bool, const LineState *> Edge; > > + > > + /// \brief An item in the prioritized BFS search queue. The \c > LineState was > > + /// reached using the \c Edge. > > + typedef std::pair<LineState, Edge> QueueItem; > > + > > + /// \brief Analyze the entire solution space starting from \p > InitialState. > > /// > > - /// \param StopAt is used for optimization. If we can determine that > we'll > > - /// definitely need at least \p StopAt additional lines, we already > know of a > > - /// better solution. > > - unsigned calcPenalty(LineState State, bool NewLine, unsigned StopAt) { > > - // We are at the end of the unwrapped line, so we don't need any > more lines. > > - if (State.NextToken == NULL) > > + /// This implements a variant of Dijkstra's algorithm on the graph > that spans > > + /// the solution space (\c LineStates are the nodes). The algorithm > tries to > > + /// find the shortest path (the one with lowest penalty) from \p > InitialState > > + /// to a state where all tokens are placed. > > + unsigned analyzeSolutionSpace(const LineState &InitialState) { > > + // Insert start element into queue. > > + std::multimap<unsigned, QueueItem> Queue; > > + Queue.insert(std::pair<unsigned, QueueItem>( > > + 0, QueueItem(InitialState, Edge(false, NULL)))); > > + std::map<LineState, Edge> Seen; > > + > > + // While not empty, take first element and follow edges. > > + while (!Queue.empty()) { > > + unsigned Penalty = Queue.begin()->first; > > + QueueItem Item = Queue.begin()->second; > > + if (Item.first.NextToken == NULL) > > + break; > > + Queue.erase(Queue.begin()); > > + > > + if (Seen.find(Item.first) != Seen.end()) > > + continue; // State already examined with lower penalty. > > + > > + const LineState &SavedState = Seen.insert(std::pair<LineState, > Edge>( > > + Item.first, > > + Edge(Item.second.first, Item.second.second))).first->first; > > + > > + addNextStateToQueue(SavedState, Penalty, /*NewLine=*/ false, > Queue); > > + addNextStateToQueue(SavedState, Penalty, /*NewLine=*/ true, > Queue); > > + } > > + > > + if (Queue.empty()) > > + // We were unable to find a solution, do nothing. > > + // FIXME: Add diagnostic? > > return 0; > > > > - if (!NewLine && State.NextToken->MustBreakBefore) > > - return UINT_MAX; > > - if (NewLine && !State.NextToken->CanBreakBefore && > > - !(State.NextToken->is(tok::r_brace) && > > - State.Stack.back().BreakBeforeClosingBrace)) > > - return UINT_MAX; > > - if (!NewLine && State.NextToken->is(tok::r_brace) && > > - State.Stack.back().BreakBeforeClosingBrace) > > - return UINT_MAX; > > - if (!NewLine && State.NextToken->Parent->is(tok::semi) && > > - State.LineContainsContinuedForLoopSection) > > - return UINT_MAX; > > - if (!NewLine && State.NextToken->Parent->is(tok::comma) && > > - State.NextToken->Type != TT_LineComment && > > - State.Stack.back().BreakAfterComma) > > - return UINT_MAX; > > - // Trying to insert a parameter on a new line if there are already > more than > > - // one parameter on the current line is bin packing. > > - if (NewLine && State.NextToken->Parent->is(tok::comma) && > > - State.Stack.back().HasMultiParameterLine && > > - State.Stack.back().AvoidBinPacking) > > - return UINT_MAX; > > - if (!NewLine && (State.NextToken->Type == TT_CtorInitializerColon || > > - > (State.NextToken->Parent->ClosesTemplateDeclaration && > > - State.Stack.size() == 1))) > > - return UINT_MAX; > > + // Reconstruct the solution. > > + // FIXME: Add debugging output. > > + Edge *CurrentEdge = &Queue.begin()->second.second; > > + while (CurrentEdge->second != NULL) { > > + LineState CurrentState = *CurrentEdge->second; > > + addTokenToState(CurrentEdge->first, false, CurrentState); > > + CurrentEdge = &Seen[*CurrentEdge->second]; > > + } > > > > - unsigned CurrentPenalty = 0; > > - if (NewLine) > > - CurrentPenalty += Parameters.PenaltyIndentLevel * > State.Stack.size() + > > - State.NextToken->SplitPenalty; > > + // Return the column after the last token of the solution. > > + return Queue.begin()->second.first.Column; > > + } > > > > + /// \brief Add the following state to the analysis queue \p Queue. > > + /// > > + /// Assume the current state is \p OldState and has been reached with > a > > + /// penalty of \p Penalty. Insert a line break if \p NewLine is \c > true. > > + void addNextStateToQueue(const LineState &OldState, unsigned Penalty, > > + bool NewLine, > > + std::multimap<unsigned, QueueItem> &Queue) { > > + if (NewLine && !canBreak(OldState)) > > + return; > > + if (!NewLine && mustBreak(OldState)) > > + return; > > + LineState State(OldState); > > + if (NewLine) > > + Penalty += Parameters.PenaltyIndentLevel * State.Stack.size() + > > + State.NextToken->SplitPenalty; > > addTokenToState(NewLine, true, State); > > - > > - // Exceeding column limit is bad, assign penalty. > > if (State.Column > getColumnLimit()) { > > unsigned ExcessCharacters = State.Column - getColumnLimit(); > > - CurrentPenalty += Parameters.PenaltyExcessCharacter * > ExcessCharacters; > > + Penalty += Parameters.PenaltyExcessCharacter * ExcessCharacters; > > } > > + Queue.insert(std::pair<unsigned, QueueItem>( > > + Penalty, QueueItem(State, Edge(NewLine, &OldState)))); > > + } > > + > > + /// \brief Returns \c true, if a line break after \p State is allowed. > > + bool canBreak(const LineState &State) { > > + if (!State.NextToken->CanBreakBefore && > > + !(State.NextToken->is(tok::r_brace) && > > + State.Stack.back().BreakBeforeClosingBrace)) > > + return false; > > + // Trying to insert a parameter on a new line if there are already > more than > > + // one parameter on the current line is bin packing. > > + if (State.NextToken->Parent->is(tok::comma) && > > + State.Stack.back().HasMultiParameterLine && > > + State.Stack.back().AvoidBinPacking) > > + return false; > > + return true; > > + } > > > > - if (StopAt <= CurrentPenalty) > > - return UINT_MAX; > > - StopAt -= CurrentPenalty; > > - StateMap::iterator I = Memory.find(State); > > - if (I != Memory.end()) { > > - // If this state has already been examined, we can safely return > the > > - // previous result if we > > - // - have not hit the optimatization (and thus returned UINT_MAX) > OR > > - // - are now computing for a smaller or equal StopAt. > > - unsigned SavedResult = I->second.first; > > - unsigned SavedStopAt = I->second.second; > > - if (SavedResult != UINT_MAX) > > - return SavedResult + CurrentPenalty; > > - else if (StopAt <= SavedStopAt) > > - return UINT_MAX; > > - } > > - > > - unsigned NoBreak = calcPenalty(State, false, StopAt); > > - unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, > NoBreak)); > > - unsigned Result = std::min(NoBreak, WithBreak); > > - > > - // We have to store 'Result' without adding 'CurrentPenalty' as the > latter > > - // can depend on 'NewLine'. > > - Memory[State] = std::pair<unsigned, unsigned>(Result, StopAt); > > > > - return Result == UINT_MAX ? UINT_MAX : Result + CurrentPenalty; > > + /// \brief Returns \c true, if a line break after \p State is > mandatory. > > + bool mustBreak(const LineState &State) { > > + if (State.NextToken->MustBreakBefore) > > + return true; > > + if (State.NextToken->is(tok::r_brace) && > > + State.Stack.back().BreakBeforeClosingBrace) > > + return true; > > + if (State.NextToken->Parent->is(tok::semi) && > > + State.LineContainsContinuedForLoopSection) > > + return true; > > + if (State.NextToken->Parent->is(tok::comma) && > > + State.Stack.back().BreakAfterComma && > > + State.NextToken->Type != TT_LineComment) > > + return true; > > + if ((State.NextToken->Type == TT_CtorInitializerColon || > > + (State.NextToken->Parent->ClosesTemplateDeclaration && > > + State.Stack.size() == 1))) > > + return true; > > + return false; > > } > > > > FormatStyle Style; > > @@ -694,10 +703,6 @@ private: > > const AnnotatedToken &RootToken; > > WhitespaceManager &Whitespaces; > > > > - // A map from an indent state to a pair (Result, Used-StopAt). > > - typedef std::map<LineState, std::pair<unsigned, unsigned> > StateMap; > > - StateMap Memory; > > - > > OptimizationParameters Parameters; > > }; > > > > > > > > _______________________________________________ > > cfe-commits mailing list > > [email protected] > > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits > > > > -- > Timur Iskhodzhanov, > Google Russia >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
