Index: lib/Format/Format.cpp =================================================================== --- lib/Format/Format.cpp +++ lib/Format/Format.cpp @@ -1269,9 +1269,10 @@ ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr, Whitespaces, Encoding, BinPackInconclusiveFunctions); - UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style, - Tokens.getKeywords(), IncompleteFormat); - Formatter.format(AnnotatedLines, /*DryRun=*/false); + UnwrappedLineFormatter Formatter(AnnotatedLines, + {&Indenter, &Whitespaces, Style, + Tokens.getKeywords(), IncompleteFormat}); + Formatter.format(); return Whitespaces.generateReplacements(); } Index: lib/Format/UnwrappedLineFormatter.h =================================================================== --- lib/Format/UnwrappedLineFormatter.h +++ lib/Format/UnwrappedLineFormatter.h @@ -28,88 +28,41 @@ class ContinuationIndenter; class WhitespaceManager; +/// \brief Context needed throughout different parts of the formatter. +struct FormattingContext { + ContinuationIndenter *Indenter; + WhitespaceManager *Whitespaces; + const FormatStyle &Style; + const AdditionalKeywords &Keywords; + bool *IncompleteFormat; +}; + class UnwrappedLineFormatter { public: - UnwrappedLineFormatter(ContinuationIndenter *Indenter, - WhitespaceManager *Whitespaces, - const FormatStyle &Style, - const AdditionalKeywords &Keywords, - bool *IncompleteFormat) - : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style), - Keywords(Keywords), IncompleteFormat(IncompleteFormat) {} - - unsigned format(const SmallVectorImpl &Lines, bool DryRun, - int AdditionalIndent = 0, bool FixBadIndentation = false); + UnwrappedLineFormatter(const SmallVectorImpl &Lines, + FormattingContext Context, bool DryRun = false, + int AdditionalIndent = 0, + bool FixBadIndentation = false) + : Lines(Lines), Context(Context), AdditionalIndent(AdditionalIndent), + DryRun(DryRun), FixBadIndentation(FixBadIndentation) {} - - /// \brief If the \p State's next token is an r_brace closing a nested block, - /// format the nested block before it. - /// - /// Returns \c true if all children could be placed successfully and adapts - /// \p Penalty as well as \p State. If \p DryRun is false, also directly - /// creates changes using \c Whitespaces. - /// - /// The crucial idea here is that children always get formatted upon - /// encountering the closing brace right after the nested block. Now, if we - /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is - /// \c false), the entire block has to be kept on the same line (which is only - /// possible if it fits on the line, only contains a single statement, etc. - /// - /// If \p NewLine is true, we format the nested block on separate lines, i.e. - /// break after the "{", format all lines with correct indentation and the put - /// the closing "}" on yet another new line. - /// - /// This enables us to keep the simple structure of the - /// \c UnwrappedLineFormatter, where we only have two options for each token: - /// break or don't break. - bool formatChildren(LineState &State, bool NewLine, bool DryRun, - unsigned &Penalty); + /// \brief Format the current block and return the penalty. + unsigned format(); private: - /// \brief Formats an \c AnnotatedLine and returns the penalty. - /// - /// If \p DryRun is \c false, directly applies the changes. - unsigned format(const AnnotatedLine &Line, unsigned FirstIndent, - bool DryRun); - - /// \brief An edge in the solution space from \c Previous->State to \c State, - /// inserting a newline dependent on the \c NewLine. - struct StateNode { - StateNode(const LineState &State, bool NewLine, StateNode *Previous) - : State(State), NewLine(NewLine), Previous(Previous) {} - LineState State; - bool NewLine; - StateNode *Previous; - }; - - /// \brief A pair of that is used to prioritize the BFS on. - /// - /// In case of equal penalties, we want to prefer states that were inserted - /// first. During state generation we make sure that we insert states first - /// that break the line as late as possible. - typedef std::pair OrderedPenalty; - - /// \brief An item in the prioritized BFS search queue. The \c StateNode's - /// \c State has the given \c OrderedPenalty. - typedef std::pair QueueItem; - - /// \brief The BFS queue type. - typedef std::priority_queue, - std::greater > QueueType; - /// \brief Get the offset of the line relatively to the level. /// /// For example, 'public:' labels in classes are offset by 1 or 2 /// characters to the left from their level. int getIndentOffset(const FormatToken &RootToken) { - if (Style.Language == FormatStyle::LK_Java || - Style.Language == FormatStyle::LK_JavaScript) + if (Context.Style.Language == FormatStyle::LK_Java || + Context.Style.Language == FormatStyle::LK_JavaScript) return 0; if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier() || - (RootToken.is(Keywords.kw_signals) && RootToken.Next && + (RootToken.is(Context.Keywords.kw_signals) && RootToken.Next && RootToken.Next->is(tok::colon))) - return Style.AccessModifierOffset; + return Context.Style.AccessModifierOffset; return 0; } @@ -130,48 +83,22 @@ unsigned getColumnLimit(bool InPPDirective) const { // In preprocessor directives reserve two chars for trailing " \" - return Style.ColumnLimit - (InPPDirective ? 2 : 0); + return Context.Style.ColumnLimit - (InPPDirective ? 2 : 0); } - struct CompareLineStatePointers { - bool operator()(LineState *obj1, LineState *obj2) const { - return *obj1 < *obj2; - } - }; - - /// \brief Analyze the entire solution space starting from \p InitialState. - /// - /// 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. Returns the penalty. - /// - /// If \p DryRun is \c false, directly applies the changes. - unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false); - - void reconstructPath(LineState &State, StateNode *Current); + const SmallVectorImpl &Lines; - /// \brief Add the following state to the analysis queue \c Queue. - /// - /// Assume the current state is \p PreviousNode and has been reached with a - /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. - void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, - bool NewLine, unsigned *Count, QueueType *Queue); + FormattingContext Context; - ContinuationIndenter *Indenter; - WhitespaceManager *Whitespaces; - FormatStyle Style; - const AdditionalKeywords &Keywords; - - llvm::SpecificBumpPtrAllocator Allocator; + const int AdditionalIndent; + const bool DryRun; + const bool FixBadIndentation; // Cache to store the penalty of formatting a vector of AnnotatedLines // starting from a specific additional offset. Improves performance if there // are many nested blocks. std::map *, unsigned>, unsigned> PenaltyCache; - - bool *IncompleteFormat; }; } // end namespace format } // end namespace clang Index: lib/Format/UnwrappedLineFormatter.cpp =================================================================== --- lib/Format/UnwrappedLineFormatter.cpp +++ lib/Format/UnwrappedLineFormatter.cpp @@ -151,8 +151,8 @@ return 0; if (1 + I[1]->Last->TotalLength > Limit) return 0; - if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, - tok::kw_while, TT_LineComment)) + if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while, + TT_LineComment)) return 0; // Only inline simple if's (no nested if or else). if (I + 2 != E && Line.First->is(tok::kw_if) && @@ -161,9 +161,10 @@ return 1; } - unsigned tryMergeShortCaseLabels( - SmallVectorImpl::const_iterator I, - SmallVectorImpl::const_iterator E, unsigned Limit) { + unsigned + tryMergeShortCaseLabels(SmallVectorImpl::const_iterator I, + SmallVectorImpl::const_iterator E, + unsigned Limit) { if (Limit == 0 || I + 1 == E || I[1]->First->isOneOf(tok::kw_case, tok::kw_default)) return 0; @@ -307,48 +308,336 @@ const AdditionalKeywords &Keywords; }; -class NoColumnLimitFormatter { +static void markFinalized(FormatToken *Tok) { + for (; Tok; Tok = Tok->Next) { + Tok->Finalized = true; + for (AnnotatedLine *Child : Tok->Children) + markFinalized(Child->First); + } +} + +#ifndef NDEBUG +static void printLineState(const LineState &State) { + llvm::dbgs() << "State: "; + for (const ParenState &P : State.Stack) { + llvm::dbgs() << P.Indent << "|" << P.LastSpace << "|" << P.NestedBlockIndent + << " "; + } + llvm::dbgs() << State.NextToken->TokenText << "\n"; +} +#endif + +/// \brief Base class for classes that format one \c AnnotatedLine. +class LineFormatter { public: - NoColumnLimitFormatter(ContinuationIndenter *Indenter, - UnwrappedLineFormatter *Formatter) - : Indenter(Indenter), Formatter(Formatter) {} + LineFormatter(FormattingContext Context) : Context(Context) {} + virtual ~LineFormatter() {} + + /// \brief Formats an \c AnnotatedLine and returns the penalty. + /// + /// If \p DryRun is \c false, directly applies the changes. + virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, + bool DryRun) = 0; + +protected: + /// \brief If the \p State's next token is an r_brace closing a nested block, + /// format the nested block before it. + /// + /// Returns \c true if all children could be placed successfully and adapts + /// \p Penalty as well as \p State. If \p DryRun is false, also directly + /// creates changes using \c Whitespaces. + /// + /// The crucial idea here is that children always get formatted upon + /// encountering the closing brace right after the nested block. Now, if we + /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is + /// \c false), the entire block has to be kept on the same line (which is only + /// possible if it fits on the line, only contains a single statement, etc. + /// + /// If \p NewLine is true, we format the nested block on separate lines, i.e. + /// break after the "{", format all lines with correct indentation and the put + /// the closing "}" on yet another new line. + /// + /// This enables us to keep the simple structure of the + /// \c UnwrappedLineFormatter, where we only have two options for each token: + /// break or don't break. + bool formatChildren(LineState &State, bool NewLine, bool DryRun, + unsigned &Penalty) { + const FormatToken *LBrace = State.NextToken->getPreviousNonComment(); + FormatToken &Previous = *State.NextToken->Previous; + if (!LBrace || LBrace->isNot(tok::l_brace) || + LBrace->BlockKind != BK_Block || Previous.Children.size() == 0) + // The previous token does not open a block. Nothing to do. We don't + // assert so that we can simply call this function for all tokens. + return true; + + if (NewLine) { + int AdditionalIndent = + State.Stack.back().Indent - + Previous.Children[0]->Level * Context.Style.IndentWidth; + + UnwrappedLineFormatter ChildFormatter(Previous.Children, Context, DryRun, + AdditionalIndent, + /*FixBadIndentation=*/true); + Penalty += ChildFormatter.format(); + return true; + } + + if (Previous.Children[0]->First->MustBreakBefore) + return false; + + // Cannot merge multiple statements into a single line. + if (Previous.Children.size() > 1) + return false; + + // Cannot merge into one line if this line ends on a comment. + if (Previous.is(tok::comment)) + return false; + + // We can't put the closing "}" on a line with a trailing comment. + if (Previous.Children[0]->Last->isTrailingComment()) + return false; + + // If the child line exceeds the column limit, we wouldn't want to merge it. + // We add +2 for the trailing " }". + if (Context.Style.ColumnLimit > 0 && + Previous.Children[0]->Last->TotalLength + State.Column + 2 > + Context.Style.ColumnLimit) + return false; + + if (!DryRun) { + Context.Whitespaces->replaceWhitespace( + *Previous.Children[0]->First, + /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1, + /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective); + } + Penalty += formatLine(*Previous.Children[0], State.Column + 1, DryRun); + + State.Column += 1 + Previous.Children[0]->Last->TotalLength; + return true; + } - /// \brief Formats the line starting at \p State, simply keeping all of the - /// input's line breaking decisions. - void format(unsigned FirstIndent, const AnnotatedLine *Line) { + FormattingContext Context; +}; + +/// \brief Formatter that keeps the existing line breaks. +class NoColumnLimitLineFormatter : public LineFormatter { +public: + NoColumnLimitLineFormatter(FormattingContext Context) + : LineFormatter(Context) {} + + /// \brief Formats the line, simply keeping all of the input's line breaking + /// decisions. + unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, + bool DryRun) override { + assert(!DryRun); LineState State = - Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false); + Context.Indenter->getInitialState(FirstIndent, &Line, /*DryRun=*/false); while (State.NextToken) { - bool Newline = - Indenter->mustBreak(State) || - (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0); + bool Newline = Context.Indenter->mustBreak(State) || + (Context.Indenter->canBreak(State) && + State.NextToken->NewlinesBefore > 0); unsigned Penalty = 0; - Formatter->formatChildren(State, Newline, /*DryRun=*/false, Penalty); - Indenter->addTokenToState(State, Newline, /*DryRun=*/false); + formatChildren(State, Newline, /*DryRun=*/false, Penalty); + Context.Indenter->addTokenToState(State, Newline, /*DryRun=*/false); } + return 0; } +}; -private: - ContinuationIndenter *Indenter; - UnwrappedLineFormatter *Formatter; +/// \brief Formatter that puts all tokens into a single line without breaks. +class FitInOneLineFormatter : public LineFormatter { +public: + FitInOneLineFormatter(FormattingContext Context) : LineFormatter(Context) {} + + /// \brief Puts all tokens into a single line. + unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, + bool DryRun) { + unsigned Penalty = 0; + LineState State = + Context.Indenter->getInitialState(FirstIndent, &Line, DryRun); + while (State.NextToken) { + formatChildren(State, /*Newline=*/false, DryRun, Penalty); + Context.Indenter->addTokenToState(State, /*Newline=*/false, DryRun); + } + return Penalty; + } }; +/// \brief Finds the best way to break lines. +class OptimizingLineFormatter : public LineFormatter { +public: + OptimizingLineFormatter(FormattingContext Context) : LineFormatter(Context) {} -static void markFinalized(FormatToken *Tok) { - for (; Tok; Tok = Tok->Next) { - Tok->Finalized = true; - for (AnnotatedLine *Child : Tok->Children) - markFinalized(Child->First); + /// \brief Formats the line by finding the best line breaks with line lengths + /// below the column limit. + unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, + bool DryRun) { + LineState State = + Context.Indenter->getInitialState(FirstIndent, &Line, DryRun); + + // If the ObjC method declaration does not fit on a line, we should format + // it with one arg per line. + if (State.Line->Type == LT_ObjCMethodDecl) + State.Stack.back().BreakBeforeParameter = true; + + // Find best solution in solution space. + return analyzeSolutionSpace(State, DryRun); } -} + +private: + struct CompareLineStatePointers { + bool operator()(LineState *obj1, LineState *obj2) const { + return *obj1 < *obj2; + } + }; + + /// \brief A pair of that is used to prioritize the BFS on. + /// + /// In case of equal penalties, we want to prefer states that were inserted + /// first. During state generation we make sure that we insert states first + /// that break the line as late as possible. + typedef std::pair OrderedPenalty; + + /// \brief An edge in the solution space from \c Previous->State to \c State, + /// inserting a newline dependent on the \c NewLine. + struct StateNode { + StateNode(const LineState &State, bool NewLine, StateNode *Previous) + : State(State), NewLine(NewLine), Previous(Previous) {} + LineState State; + bool NewLine; + StateNode *Previous; + }; + + /// \brief An item in the prioritized BFS search queue. The \c StateNode's + /// \c State has the given \c OrderedPenalty. + typedef std::pair QueueItem; + + /// \brief The BFS queue type. + typedef std::priority_queue, + std::greater> QueueType; + + /// \brief Analyze the entire solution space starting from \p InitialState. + /// + /// 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. Returns the penalty. + /// + /// If \p DryRun is \c false, directly applies the changes. + unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) { + std::set Seen; + + // Increasing count of \c StateNode items we have created. This is used to + // create a deterministic order independent of the container. + unsigned Count = 0; + QueueType Queue; + + // Insert start element into queue. + StateNode *Node = + new (Allocator.Allocate()) StateNode(InitialState, false, nullptr); + Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); + ++Count; + + unsigned Penalty = 0; + + // While not empty, take first element and follow edges. + while (!Queue.empty()) { + Penalty = Queue.top().first.first; + StateNode *Node = Queue.top().second; + if (!Node->State.NextToken) { + DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n"); + break; + } + Queue.pop(); + + // Cut off the analysis of certain solutions if the analysis gets too + // complex. See description of IgnoreStackForComparison. + if (Count > 10000) + Node->State.IgnoreStackForComparison = true; + + if (!Seen.insert(&Node->State).second) + // State already examined with lower penalty. + continue; + + FormatDecision LastFormat = Node->State.NextToken->Decision; + if (LastFormat == FD_Unformatted || LastFormat == FD_Continue) + addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue); + if (LastFormat == FD_Unformatted || LastFormat == FD_Break) + addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue); + } + + if (Queue.empty()) { + // We were unable to find a solution, do nothing. + // FIXME: Add diagnostic? + DEBUG(llvm::dbgs() << "Could not find a solution.\n"); + return 0; + } + + // Reconstruct the solution. + if (!DryRun) + reconstructPath(InitialState, Queue.top().second); + + DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n"); + DEBUG(llvm::dbgs() << "---\n"); + + return Penalty; + } + + /// \brief Add the following state to the analysis queue \c Queue. + /// + /// Assume the current state is \p PreviousNode and has been reached with a + /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. + void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, + bool NewLine, unsigned *Count, QueueType *Queue) { + if (NewLine && !Context.Indenter->canBreak(PreviousNode->State)) + return; + if (!NewLine && Context.Indenter->mustBreak(PreviousNode->State)) + return; + + StateNode *Node = new (Allocator.Allocate()) + StateNode(PreviousNode->State, NewLine, PreviousNode); + if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty)) + return; + + Penalty += Context.Indenter->addTokenToState(Node->State, NewLine, true); + + Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node)); + ++(*Count); + } + + /// \brief Applies the best formatting by reconstructing the path in the + /// solution space that leads to \c Best. + void reconstructPath(LineState &State, StateNode *Best) { + std::deque Path; + // We do not need a break before the initial token. + while (Best->Previous) { + Path.push_front(Best); + Best = Best->Previous; + } + for (std::deque::iterator I = Path.begin(), E = Path.end(); + I != E; ++I) { + unsigned Penalty = 0; + formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty); + Penalty += Context.Indenter->addTokenToState(State, (*I)->NewLine, false); + + DEBUG({ + printLineState((*I)->Previous->State); + if ((*I)->NewLine) { + llvm::dbgs() << "Penalty for placing " + << (*I)->Previous->State.NextToken->Tok.getName() << ": " + << Penalty << "\n"; + } + }); + } + } + + llvm::SpecificBumpPtrAllocator Allocator; +}; } // namespace -unsigned -UnwrappedLineFormatter::format(const SmallVectorImpl &Lines, - bool DryRun, int AdditionalIndent, - bool FixBadIndentation) { - LineJoiner Joiner(Style, Keywords); +unsigned UnwrappedLineFormatter::format() { + LineJoiner Joiner(Context.Style, Context.Keywords); // Try to look up already computed penalty in DryRun-mode. std::pair *, unsigned> CacheKey( @@ -361,7 +650,7 @@ unsigned Penalty = 0; std::vector IndentForLevel; for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i) - IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent); + IndentForLevel.push_back(Context.Style.IndentWidth * i + AdditionalIndent); const AnnotatedLine *PreviousLine = nullptr; for (SmallVectorImpl::const_iterator I = Lines.begin(), E = Lines.end(); @@ -373,7 +662,7 @@ // Determine indent and try to merge multiple unwrapped lines. unsigned Indent; if (TheLine.InPPDirective) { - Indent = TheLine.Level * Style.IndentWidth; + Indent = TheLine.Level * Context.Style.IndentWidth; } else { while (IndentForLevel.size() <= TheLine.Level) IndentForLevel.push_back(-1); @@ -386,7 +675,7 @@ // Merge multiple lines if possible. unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E); - if (MergedLines > 0 && Style.ColumnLimit == 0) { + if (MergedLines > 0 && Context.Style.ColumnLimit == 0) { // Disallow line merging if there is a break at the start of one of the // input lines. for (unsigned i = 0; i < MergedLines; ++i) { @@ -408,9 +697,9 @@ if (PreviousLine && PreviousLine->Affected && !DryRun) { // Remove the file's trailing whitespace. unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u); - Whitespaces->replaceWhitespace(*TheLine.First, Newlines, - /*IndentLevel=*/0, /*Spaces=*/0, - /*TargetColumn=*/0); + Context.Whitespaces->replaceWhitespace(*TheLine.First, Newlines, + /*IndentLevel=*/0, /*Spaces=*/0, + /*TargetColumn=*/0); } } else if (TheLine.Type != LT_Invalid && ShouldFormat) { if (FirstTok->WhitespaceRange.isValid()) { @@ -422,7 +711,7 @@ } // If everything fits on a single line, just put it there. - unsigned ColumnLimit = Style.ColumnLimit; + unsigned ColumnLimit = Context.Style.ColumnLimit; if (I + 1 != E) { AnnotatedLine *NextLine = I[1]; if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline) @@ -431,23 +720,21 @@ if (TheLine.Last->TotalLength + Indent <= ColumnLimit || TheLine.Type == LT_ImportStatement) { - LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun); - while (State.NextToken) { - formatChildren(State, /*Newline=*/false, DryRun, Penalty); - Indenter->addTokenToState(State, /*Newline=*/false, DryRun); - } - } else if (Style.ColumnLimit == 0) { - NoColumnLimitFormatter Formatter(Indenter, this); - if (!DryRun) - Formatter.format(Indent, &TheLine); + FitInOneLineFormatter LineFormatter(Context); + Penalty += LineFormatter.formatLine(TheLine, Indent, DryRun); + } else if (Context.Style.ColumnLimit == 0) { + NoColumnLimitLineFormatter LineFormatter(Context); + LineFormatter.formatLine(TheLine, Indent, DryRun); } else { - Penalty += format(TheLine, Indent, DryRun); + OptimizingLineFormatter LineFormatter(Context); + Penalty += LineFormatter.formatLine(TheLine, Indent, DryRun); } if (!TheLine.InPPDirective) IndentForLevel[TheLine.Level] = LevelIndent; } else if (TheLine.ChildrenAffected) { - format(TheLine.Children, DryRun); + UnwrappedLineFormatter ChildFormatter(TheLine.Children, Context, DryRun); + ChildFormatter.format(); } else { // Format the first token if necessary, and notify the WhitespaceManager // about the unchanged whitespace. @@ -461,7 +748,8 @@ formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent, TheLine.InPPDirective); } else { - Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); + Context.Whitespaces->addUntouchableToken(*Tok, + TheLine.InPPDirective); } } @@ -472,12 +760,12 @@ !TheLine.InPPDirective) IndentForLevel[TheLine.Level] = LevelIndent; } else if (!DryRun) { - Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); + Context.Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); } } } - if (TheLine.Type == LT_Invalid && ShouldFormat && IncompleteFormat) - *IncompleteFormat = true; + if (TheLine.Type == LT_Invalid && ShouldFormat && Context.IncompleteFormat) + *Context.IncompleteFormat = true; if (!DryRun) markFinalized(TheLine.First); PreviousLine = *I; @@ -486,26 +774,13 @@ return Penalty; } -unsigned UnwrappedLineFormatter::format(const AnnotatedLine &Line, - unsigned FirstIndent, bool DryRun) { - LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun); - - // If the ObjC method declaration does not fit on a line, we should format - // it with one arg per line. - if (State.Line->Type == LT_ObjCMethodDecl) - State.Stack.back().BreakBeforeParameter = true; - - // Find best solution in solution space. - return analyzeSolutionSpace(State, DryRun); -} - void UnwrappedLineFormatter::formatFirstToken(FormatToken &RootToken, const AnnotatedLine *PreviousLine, unsigned IndentLevel, unsigned Indent, bool InPPDirective) { unsigned Newlines = - std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1); + std::min(RootToken.NewlinesBefore, Context.Style.MaxEmptyLinesToKeep + 1); // Remove empty lines before "}" where applicable. if (RootToken.is(tok::r_brace) && (!RootToken.Next || @@ -517,7 +792,7 @@ Newlines = 0; // Remove empty lines after "{". - if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine && + if (!Context.Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine && PreviousLine->Last->is(tok::l_brace) && PreviousLine->First->isNot(tok::kw_namespace) && !startsExternCBlock(*PreviousLine)) @@ -533,9 +808,9 @@ (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline)) Newlines = std::min(1u, Newlines); - Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent, - Indent, InPPDirective && - !RootToken.HasUnescapedNewline); + Context.Whitespaces->replaceWhitespace( + RootToken, Newlines, IndentLevel, Indent, Indent, + InPPDirective && !RootToken.HasUnescapedNewline); } /// \brief Get the indent of \p Level from \p IndentForLevel. @@ -549,7 +824,7 @@ return IndentForLevel[Level]; if (Level == 0) return 0; - return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth; + return getIndent(IndentForLevel, Level - 1) + Context.Style.IndentWidth; } void UnwrappedLineFormatter::join(AnnotatedLine &A, const AnnotatedLine &B) { @@ -567,174 +842,5 @@ } } -unsigned UnwrappedLineFormatter::analyzeSolutionSpace(LineState &InitialState, - bool DryRun) { - std::set Seen; - - // Increasing count of \c StateNode items we have created. This is used to - // create a deterministic order independent of the container. - unsigned Count = 0; - QueueType Queue; - - // Insert start element into queue. - StateNode *Node = - new (Allocator.Allocate()) StateNode(InitialState, false, nullptr); - Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); - ++Count; - - unsigned Penalty = 0; - - // While not empty, take first element and follow edges. - while (!Queue.empty()) { - Penalty = Queue.top().first.first; - StateNode *Node = Queue.top().second; - if (!Node->State.NextToken) { - DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n"); - break; - } - Queue.pop(); - - // Cut off the analysis of certain solutions if the analysis gets too - // complex. See description of IgnoreStackForComparison. - if (Count > 10000) - Node->State.IgnoreStackForComparison = true; - - if (!Seen.insert(&Node->State).second) - // State already examined with lower penalty. - continue; - - FormatDecision LastFormat = Node->State.NextToken->Decision; - if (LastFormat == FD_Unformatted || LastFormat == FD_Continue) - addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue); - if (LastFormat == FD_Unformatted || LastFormat == FD_Break) - addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue); - } - - if (Queue.empty()) { - // We were unable to find a solution, do nothing. - // FIXME: Add diagnostic? - DEBUG(llvm::dbgs() << "Could not find a solution.\n"); - return 0; - } - - // Reconstruct the solution. - if (!DryRun) - reconstructPath(InitialState, Queue.top().second); - - DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n"); - DEBUG(llvm::dbgs() << "---\n"); - - return Penalty; -} - -#ifndef NDEBUG -static void printLineState(const LineState &State) { - llvm::dbgs() << "State: "; - for (const ParenState &P : State.Stack) { - llvm::dbgs() << P.Indent << "|" << P.LastSpace << "|" << P.NestedBlockIndent - << " "; - } - llvm::dbgs() << State.NextToken->TokenText << "\n"; -} -#endif - -void UnwrappedLineFormatter::reconstructPath(LineState &State, - StateNode *Current) { - std::deque Path; - // We do not need a break before the initial token. - while (Current->Previous) { - Path.push_front(Current); - Current = Current->Previous; - } - for (std::deque::iterator I = Path.begin(), E = Path.end(); - I != E; ++I) { - unsigned Penalty = 0; - formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty); - Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false); - - DEBUG({ - printLineState((*I)->Previous->State); - if ((*I)->NewLine) { - llvm::dbgs() << "Penalty for placing " - << (*I)->Previous->State.NextToken->Tok.getName() << ": " - << Penalty << "\n"; - } - }); - } -} - -void UnwrappedLineFormatter::addNextStateToQueue(unsigned Penalty, - StateNode *PreviousNode, - bool NewLine, unsigned *Count, - QueueType *Queue) { - if (NewLine && !Indenter->canBreak(PreviousNode->State)) - return; - if (!NewLine && Indenter->mustBreak(PreviousNode->State)) - return; - - StateNode *Node = new (Allocator.Allocate()) - StateNode(PreviousNode->State, NewLine, PreviousNode); - if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty)) - return; - - Penalty += Indenter->addTokenToState(Node->State, NewLine, true); - - Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node)); - ++(*Count); -} - -bool UnwrappedLineFormatter::formatChildren(LineState &State, bool NewLine, - bool DryRun, unsigned &Penalty) { - const FormatToken *LBrace = State.NextToken->getPreviousNonComment(); - FormatToken &Previous = *State.NextToken->Previous; - if (!LBrace || LBrace->isNot(tok::l_brace) || LBrace->BlockKind != BK_Block || - Previous.Children.size() == 0) - // The previous token does not open a block. Nothing to do. We don't - // assert so that we can simply call this function for all tokens. - return true; - - if (NewLine) { - int AdditionalIndent = State.Stack.back().Indent - - Previous.Children[0]->Level * Style.IndentWidth; - - Penalty += format(Previous.Children, DryRun, AdditionalIndent, - /*FixBadIndentation=*/true); - return true; - } - - if (Previous.Children[0]->First->MustBreakBefore) - return false; - - // Cannot merge multiple statements into a single line. - if (Previous.Children.size() > 1) - return false; - - // Cannot merge into one line if this line ends on a comment. - if (Previous.is(tok::comment)) - return false; - - // We can't put the closing "}" on a line with a trailing comment. - if (Previous.Children[0]->Last->isTrailingComment()) - return false; - - // If the child line exceeds the column limit, we wouldn't want to merge it. - // We add +2 for the trailing " }". - if (Style.ColumnLimit > 0 && - Previous.Children[0]->Last->TotalLength + State.Column + 2 > - Style.ColumnLimit) - return false; - - if (!DryRun) { - Whitespaces->replaceWhitespace( - *Previous.Children[0]->First, - /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1, - /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective); - } - Penalty += format(*Previous.Children[0], State.Column + 1, DryRun); - - State.Column += 1 + Previous.Children[0]->Last->TotalLength; - return true; -} - } // namespace format } // namespace clang