12 #include "llvm/Support/Debug.h"
15 #define DEBUG_TYPE "format-formatter"
22 bool startsExternCBlock(
const AnnotatedLine &
Line) {
24 const FormatToken *NextNext = Next ? Next->getNextNonComment() :
nullptr;
25 return Line.
startsWith(tok::kw_extern) && Next && Next->isStringLiteral() &&
26 NextNext && NextNext->is(tok::l_brace);
29 bool isRecordLBrace(
const FormatToken &Tok) {
30 return Tok.isOneOf(TT_ClassLBrace, TT_EnumLBrace, TT_RecordLBrace,
31 TT_StructLBrace, TT_UnionLBrace);
43 class LevelIndentTracker {
45 LevelIndentTracker(
const FormatStyle &Style,
46 const AdditionalKeywords &Keywords,
unsigned StartLevel,
48 : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {
49 for (
unsigned i = 0; i != StartLevel; ++i)
50 IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
54 unsigned getIndent()
const {
return Indent; }
58 void nextLine(
const AnnotatedLine &
Line) {
64 (
Line.InPPDirective ||
67 unsigned PPIndentWidth =
68 (Style.PPIndentWidth >= 0) ? Style.PPIndentWidth : Style.IndentWidth;
70 ?
Line.PPLevel * PPIndentWidth +
71 (
Line.Level -
Line.PPLevel) * Style.IndentWidth
72 :
Line.Level * PPIndentWidth;
73 Indent += AdditionalIndent;
79 if (
Line.IsContinuation)
80 Indent =
Line.Level * Style.IndentWidth + Style.ContinuationIndentWidth;
85 void skipLine(
const AnnotatedLine &
Line,
bool UnknownIndent =
false) {
86 if (
Line.Level >= IndentForLevel.size())
87 IndentForLevel.resize(
Line.Level + 1, UnknownIndent ? -1 :
Indent);
95 void adjustToUnmodifiedLine(
const AnnotatedLine &
Line) {
96 unsigned LevelIndent =
Line.First->OriginalColumn;
97 if (
static_cast<int>(LevelIndent) -
Offset >= 0)
99 assert(
Line.Level < IndentForLevel.size());
100 if ((!
Line.First->is(tok::comment) || IndentForLevel[
Line.Level] == -1) &&
101 !
Line.InPPDirective) {
102 IndentForLevel[
Line.Level] = LevelIndent;
111 int getIndentOffset(
const FormatToken &RootToken) {
117 auto IsAccessModifier = [
this, &RootToken]() {
118 if (RootToken.isAccessSpecifier(Style.isCpp())) {
120 }
else if (RootToken.isObjCAccessSpecifier()) {
124 else if ((RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals) &&
125 RootToken.Next && RootToken.Next->is(tok::colon))) {
127 }
else if (RootToken.Next &&
128 RootToken.Next->isOneOf(Keywords.kw_slots,
129 Keywords.kw_qslots) &&
130 RootToken.Next->Next && RootToken.Next->Next->is(tok::colon)) {
134 else if (!RootToken.Next && RootToken.isAccessSpecifier(
false)) {
140 if (IsAccessModifier()) {
144 return Style.IndentAccessModifiers ? -Style.IndentWidth
145 : Style.AccessModifierOffset;
155 unsigned getIndent(
unsigned Level)
const {
156 if (IndentForLevel[
Level] != -1)
157 return IndentForLevel[
Level];
160 return getIndent(
Level - 1) + Style.IndentWidth;
163 const FormatStyle &Style;
164 const AdditionalKeywords &Keywords;
165 const unsigned AdditionalIndent;
168 SmallVector<int> IndentForLevel;
180 const FormatToken *getMatchingNamespaceToken(
181 const AnnotatedLine *
Line,
182 const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
188 assert(StartLineIndex < AnnotatedLines.size());
189 return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();
194 return NamespaceToken ? NamespaceToken->
TokenText : StringRef();
197 StringRef getMatchingNamespaceTokenText(
198 const AnnotatedLine *
Line,
199 const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
200 const FormatToken *NamespaceToken =
201 getMatchingNamespaceToken(
Line, AnnotatedLines);
202 return NamespaceToken ? NamespaceToken->TokenText : StringRef();
207 LineJoiner(
const FormatStyle &Style,
const AdditionalKeywords &Keywords,
208 const SmallVectorImpl<AnnotatedLine *> &Lines)
209 : Style(Style), Keywords(Keywords),
End(Lines.end()), Next(Lines.begin()),
210 AnnotatedLines(Lines) {}
213 const AnnotatedLine *getNextMergedLine(
bool DryRun,
214 LevelIndentTracker &IndentTracker) {
217 const AnnotatedLine *Current = *Next;
218 IndentTracker.nextLine(*Current);
219 unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next,
End);
220 if (MergedLines > 0 && Style.ColumnLimit == 0) {
223 for (
unsigned i = 0; i < MergedLines; ++i)
224 if (Next[i + 1]->First->NewlinesBefore > 0)
228 for (
unsigned i = 0; i < MergedLines; ++i)
229 join(*Next[0], *Next[i + 1]);
230 Next = Next + MergedLines + 1;
237 tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,
238 SmallVectorImpl<AnnotatedLine *>::const_iterator I,
239 SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
240 const unsigned Indent = IndentTracker.getIndent();
246 const AnnotatedLine *TheLine = *I;
247 if (TheLine->Last->is(TT_LineComment))
249 const auto &NextLine = *I[1];
250 if (NextLine.Type ==
LT_Invalid || NextLine.First->MustBreakBefore)
252 if (TheLine->InPPDirective &&
253 (!NextLine.InPPDirective || NextLine.First->HasUnescapedNewline)) {
257 if (Style.ColumnLimit > 0 &&
Indent > Style.ColumnLimit)
264 Limit = TheLine->Last->TotalLength > Limit
266 : Limit - TheLine->Last->TotalLength;
268 if (TheLine->Last->is(TT_FunctionLBrace) &&
269 TheLine->First == TheLine->Last &&
270 !Style.BraceWrapping.SplitEmptyFunction &&
271 NextLine.First->is(tok::r_brace)) {
272 return tryMergeSimpleBlock(I, E, Limit);
275 const auto *PreviousLine = I != AnnotatedLines.begin() ? I[-1] :
nullptr;
277 if (PreviousLine && TheLine->Last->is(tok::l_brace) &&
278 TheLine->First == TheLine->Last) {
279 bool EmptyBlock = NextLine.First->is(tok::r_brace);
281 const FormatToken *Tok = PreviousLine->First;
282 if (Tok && Tok->is(tok::comment))
283 Tok = Tok->getNextNonComment();
285 if (Tok && Tok->getNamespaceToken()) {
286 return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock
287 ? tryMergeSimpleBlock(I, E, Limit)
291 if (Tok && Tok->is(tok::kw_typedef))
292 Tok = Tok->getNextNonComment();
293 if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union,
294 tok::kw_extern, Keywords.kw_interface)) {
295 return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock
296 ? tryMergeSimpleBlock(I, E, Limit)
300 if (Tok && Tok->is(tok::kw_template) &&
301 Style.BraceWrapping.SplitEmptyRecord && EmptyBlock) {
306 auto ShouldMergeShortFunctions = [
this, &I, &NextLine, PreviousLine,
311 NextLine.First->is(tok::r_brace)) {
315 if (Style.AllowShortFunctionsOnASingleLine &
319 if (Style.isJavaScript() && TheLine->Last->is(TT_FunctionLBrace))
322 if (TheLine->Level != 0) {
328 const AnnotatedLine *
Line =
nullptr;
329 for (
auto J = I - 1; J >= AnnotatedLines.begin(); --J) {
331 if (!(*J)->InPPDirective && !(*J)->isComment() &&
332 (*J)->Level < TheLine->Level) {
342 const FormatToken *LastNonComment =
Line->Last;
343 assert(LastNonComment);
344 if (LastNonComment->is(tok::comment)) {
345 LastNonComment = LastNonComment->getPreviousNonComment();
348 assert(LastNonComment);
350 return isRecordLBrace(*LastNonComment);
357 bool MergeShortFunctions = ShouldMergeShortFunctions();
359 const FormatToken *FirstNonComment = TheLine->First;
360 if (FirstNonComment->is(tok::comment)) {
361 FirstNonComment = FirstNonComment->getNextNonComment();
362 if (!FirstNonComment)
368 if (Style.CompactNamespaces) {
369 if (
auto nsToken = TheLine->First->getNamespaceToken()) {
371 unsigned closingLine = TheLine->MatchingClosingBlockLineIndex - 1;
372 for (; I + 1 + i != E &&
374 closingLine == I[i + 1]->MatchingClosingBlockLineIndex &&
375 I[i + 1]->Last->TotalLength < Limit;
376 i++, --closingLine) {
378 IndentTracker.skipLine(*I[i + 1]);
380 Limit -= I[i + 1]->Last->TotalLength;
385 if (
auto nsToken = getMatchingNamespaceToken(TheLine, AnnotatedLines)) {
387 unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;
388 for (; I + 1 + i != E &&
389 nsToken->TokenText ==
390 getMatchingNamespaceTokenText(I[i + 1], AnnotatedLines) &&
391 openingLine == I[i + 1]->MatchingOpeningBlockLineIndex;
392 i++, --openingLine) {
394 I[i + 1]->First->SpacesRequiredBefore = !I[i]->Last->is(tok::r_brace);
397 IndentTracker.nextLine(*I[i + 1]);
404 if (TheLine->Last->is(TT_FunctionLBrace) && TheLine->First != TheLine->Last)
405 return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
407 if (TheLine->Last->is(tok::l_brace) && FirstNonComment != TheLine->Last &&
408 FirstNonComment->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for,
411 ? tryMergeSimpleBlock(I, E, Limit)
415 if (NextLine.First->is(tok::l_brace)) {
416 if ((TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
417 tok::kw_for, tok::kw_switch, tok::kw_try,
418 tok::kw_do, TT_ForEachMacro) ||
419 (TheLine->First->is(tok::r_brace) && TheLine->First->Next &&
420 TheLine->First->Next->isOneOf(tok::kw_else, tok::kw_catch))) &&
421 Style.BraceWrapping.AfterControlStatement ==
426 return (Style.ColumnLimit == 0 || TheLine->Level * Style.IndentWidth +
427 TheLine->Last->TotalLength <=
432 if (TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
433 tok::kw_for, TT_ForEachMacro)) {
434 return (Style.BraceWrapping.AfterControlStatement ==
436 ? tryMergeSimpleBlock(I, E, Limit)
439 if (TheLine->First->isOneOf(tok::kw_else, tok::kw_catch) &&
440 Style.BraceWrapping.AfterControlStatement ==
447 return (Style.ColumnLimit == 0 ||
448 TheLine->Last->TotalLength <= Style.ColumnLimit)
453 if (PreviousLine && TheLine->First->is(tok::l_brace)) {
454 switch (PreviousLine->First->Tok.getKind()) {
457 if (PreviousLine->First->Next) {
459 PreviousLine->First->Next->Tok.getObjCKeywordID();
460 if (kwId == tok::objc_autoreleasepool ||
461 kwId == tok::objc_synchronized) {
468 case tok::kw_default:
479 if (PreviousLine && Style.BraceWrapping.SplitEmptyRecord &&
480 TheLine->Last->is(tok::l_brace) && PreviousLine->Last) {
481 const FormatToken *
Previous = PreviousLine->Last;
486 if (
Previous->is(tok::greater) && !PreviousLine->InPPDirective)
488 if (
Previous->is(tok::identifier)) {
489 const FormatToken *PreviousPrevious =
491 if (PreviousPrevious &&
492 PreviousPrevious->isOneOf(tok::kw_class, tok::kw_struct)) {
500 if (TheLine->Last->is(tok::l_brace)) {
501 bool ShouldMerge =
false;
503 if (TheLine->Last->is(TT_EnumLBrace)) {
504 ShouldMerge = Style.AllowShortEnumsOnASingleLine;
505 }
else if (TheLine->Last->isOneOf(TT_ClassLBrace, TT_StructLBrace)) {
509 ShouldMerge = !Style.BraceWrapping.AfterClass ||
510 (NextLine.First->is(tok::r_brace) &&
511 !Style.BraceWrapping.SplitEmptyRecord);
515 assert(TheLine->InPPDirective ||
516 !TheLine->First->isOneOf(tok::kw_class, tok::kw_enum,
518 ShouldMerge = !Style.BraceWrapping.AfterFunction ||
519 (NextLine.First->is(tok::r_brace) &&
520 !Style.BraceWrapping.SplitEmptyFunction);
522 return ShouldMerge ? tryMergeSimpleBlock(I, E, Limit) : 0;
526 if (NextLine.First->is(TT_FunctionLBrace) &&
527 Style.BraceWrapping.AfterFunction) {
528 if (NextLine.Last->is(TT_LineComment))
532 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
536 unsigned MergedLines = 0;
537 if (MergeShortFunctions ||
539 NextLine.First == NextLine.Last && I + 2 != E &&
540 I[2]->First->is(tok::r_brace))) {
541 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
549 auto IsElseLine = [&TheLine]() ->
bool {
550 const FormatToken *First = TheLine->First;
551 if (First->is(tok::kw_else))
554 return First->is(tok::r_brace) && First->Next &&
555 First->Next->is(tok::kw_else);
557 if (TheLine->First->is(tok::kw_if) ||
558 (IsElseLine() && (Style.AllowShortIfStatementsOnASingleLine ==
560 return Style.AllowShortIfStatementsOnASingleLine
561 ? tryMergeSimpleControlStatement(I, E, Limit)
564 if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while, tok::kw_do,
566 return Style.AllowShortLoopsOnASingleLine
567 ? tryMergeSimpleControlStatement(I, E, Limit)
570 if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
571 return Style.AllowShortCaseLabelsOnASingleLine
572 ? tryMergeShortCaseLabels(I, E, Limit)
575 if (TheLine->InPPDirective &&
576 (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
577 return tryMergeSimplePPDirective(I, E, Limit);
583 tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
584 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
588 if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
590 if (1 + I[1]->Last->TotalLength > Limit)
595 unsigned tryMergeSimpleControlStatement(
596 SmallVectorImpl<AnnotatedLine *>::const_iterator I,
597 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
unsigned Limit) {
600 if (Style.BraceWrapping.AfterControlStatement ==
602 I[1]->First->is(tok::l_brace) &&
606 if (I[1]->InPPDirective != (*I)->InPPDirective ||
607 (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) {
610 Limit = limitConsideringMacros(I + 1, E, Limit);
611 AnnotatedLine &
Line = **I;
612 if (!
Line.First->is(tok::kw_do) && !
Line.First->is(tok::kw_else) &&
613 !
Line.Last->is(tok::kw_else) &&
Line.Last->isNot(tok::r_paren)) {
617 if (
Line.First->is(tok::kw_do) && !
Line.Last->is(tok::kw_do))
619 if (1 + I[1]->Last->TotalLength > Limit)
622 if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,
623 TT_ForEachMacro, TT_LineComment)) {
627 if (Style.AllowShortIfStatementsOnASingleLine ==
629 if (I + 2 != E &&
Line.startsWith(tok::kw_if) &&
630 I[2]->First->is(tok::kw_else)) {
638 tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
639 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
641 if (Limit == 0 || I + 1 == E ||
642 I[1]->First->isOneOf(tok::kw_case, tok::kw_default)) {
645 if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))
647 unsigned NumStmts = 0;
649 bool EndsWithComment =
false;
650 bool InPPDirective = I[0]->InPPDirective;
651 bool InMacroBody = I[0]->InMacroBody;
652 const unsigned Level = I[0]->Level;
653 for (; NumStmts < 3; ++NumStmts) {
654 if (I + 1 + NumStmts == E)
656 const AnnotatedLine *
Line = I[1 + NumStmts];
657 if (
Line->InPPDirective != InPPDirective)
659 if (
Line->InMacroBody != InMacroBody)
661 if (
Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
663 if (
Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
668 if (
Line->First->is(tok::comment)) {
671 SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
672 for (; J != E; ++J) {
674 if (
Line->InPPDirective != InPPDirective)
676 if (
Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
678 if (
Line->First->isNot(tok::comment) ||
Level !=
Line->Level)
683 if (
Line->Last->is(tok::comment))
684 EndsWithComment =
true;
685 Length += I[1 + NumStmts]->Last->TotalLength + 1;
687 if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
693 tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
694 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
700 AnnotatedLine &
Line = **I;
706 Line.First->isOneOf(tok::at, tok::minus, tok::plus)) {
712 if (
Line.First->is(tok::kw_case) ||
713 (
Line.First->Next &&
Line.First->Next->is(tok::kw_else))) {
717 if (
Line.First->is(tok::kw_default)) {
718 const FormatToken *Tok =
Line.First->getNextNonComment();
719 if (Tok && Tok->is(tok::colon))
723 auto IsCtrlStmt = [](
const auto &
Line) {
724 return Line.First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
725 tok::kw_do, tok::kw_for, TT_ForEachMacro);
728 const bool IsSplitBlock =
731 I[1]->First->isNot(tok::r_brace));
733 if (IsCtrlStmt(
Line) ||
734 Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
735 tok::kw___finally, tok::r_brace,
736 Keywords.kw___except)) {
741 if (!Style.AllowShortIfStatementsOnASingleLine &&
742 Line.First->isOneOf(tok::kw_if, tok::kw_else) &&
743 !Style.BraceWrapping.AfterControlStatement &&
744 !I[1]->First->is(tok::r_brace)) {
747 if (!Style.AllowShortIfStatementsOnASingleLine &&
748 Line.First->isOneOf(tok::kw_if, tok::kw_else) &&
749 Style.BraceWrapping.AfterControlStatement ==
751 I + 2 != E && !I[2]->First->is(tok::r_brace)) {
754 if (!Style.AllowShortLoopsOnASingleLine &&
755 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,
757 !Style.BraceWrapping.AfterControlStatement &&
758 !I[1]->First->is(tok::r_brace)) {
761 if (!Style.AllowShortLoopsOnASingleLine &&
762 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,
764 Style.BraceWrapping.AfterControlStatement ==
766 I + 2 != E && !I[2]->First->is(tok::r_brace)) {
774 if (
Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
775 Keywords.kw___except, tok::kw___finally)) {
780 if (
Line.Last->is(tok::l_brace)) {
781 if (IsSplitBlock &&
Line.First ==
Line.Last &&
782 I > AnnotatedLines.begin() &&
783 (I[-1]->endsWith(tok::kw_else) || IsCtrlStmt(*I[-1]))) {
786 FormatToken *Tok = I[1]->First;
787 auto ShouldMerge = [Tok]() {
788 if (Tok->isNot(tok::r_brace) || Tok->MustBreakBefore)
790 const FormatToken *Next = Tok->getNextNonComment();
791 return !Next || Next->is(tok::semi);
796 Tok->SpacesRequiredBefore = Style.SpaceInEmptyBlock ? 1 : 0;
797 Tok->CanBreakBefore =
true;
799 }
else if (Limit != 0 && !
Line.startsWithNamespace() &&
800 !startsExternCBlock(
Line)) {
802 if (isRecordLBrace(*
Line.Last))
808 Limit = limitConsideringMacros(I + 2, E, Limit);
810 if (!nextTwoLinesFitInto(I, Limit))
815 if (I[1]->Last->is(TT_LineComment))
825 if (Tok->isNot(tok::r_brace))
829 if (Tok->Next && Tok->Next->is(tok::kw_else))
838 if (
Line.First ==
Line.Last &&
Line.First->isNot(TT_FunctionLBrace) &&
839 Style.BraceWrapping.AfterControlStatement ==
846 }
else if (I[1]->First->is(tok::l_brace)) {
847 if (I[1]->Last->is(TT_LineComment))
851 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))
854 unsigned MergedLines = 0;
856 (I[1]->First == I[1]->Last && I + 2 != E &&
857 I[2]->First->is(tok::r_brace))) {
858 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
872 limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
873 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
875 if (I[0]->InPPDirective && I + 1 != E &&
876 !I[1]->First->HasUnescapedNewline && !I[1]->First->is(
tok::eof)) {
877 return Limit < 2 ? 0 : Limit - 2;
882 bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
884 if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
886 return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
889 bool containsMustBreak(
const AnnotatedLine *
Line) {
890 for (
const FormatToken *Tok =
Line->First; Tok; Tok = Tok->Next)
891 if (Tok->MustBreakBefore)
896 void join(AnnotatedLine &A,
const AnnotatedLine &B) {
897 assert(!A.Last->Next);
898 assert(!B.First->Previous);
901 A.Last->Next = B.First;
902 B.First->Previous = A.Last;
903 B.First->CanBreakBefore =
true;
904 unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
905 for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
906 Tok->TotalLength += LengthA;
911 const FormatStyle &Style;
912 const AdditionalKeywords &Keywords;
913 const SmallVectorImpl<AnnotatedLine *>::const_iterator
End;
915 SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
916 const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
919 static void markFinalized(FormatToken *Tok) {
920 for (; Tok; Tok = Tok->Next) {
921 Tok->Finalized =
true;
922 for (AnnotatedLine *Child : Tok->Children)
923 markFinalized(Child->First);
928 static void printLineState(
const LineState &
State) {
929 llvm::dbgs() <<
"State: ";
931 llvm::dbgs() << (
P.Tok ?
P.Tok->TokenText :
"F") <<
"|" <<
P.Indent <<
"|"
932 <<
P.LastSpace <<
"|" <<
P.NestedBlockIndent <<
" ";
939 class LineFormatter {
941 LineFormatter(ContinuationIndenter *
Indenter, WhitespaceManager *Whitespaces,
942 const FormatStyle &Style,
943 UnwrappedLineFormatter *BlockFormatter)
945 BlockFormatter(BlockFormatter) {}
946 virtual ~LineFormatter() {}
951 virtual unsigned formatLine(
const AnnotatedLine &
Line,
unsigned FirstIndent,
952 unsigned FirstStartColumn,
bool DryRun) = 0;
975 bool formatChildren(LineState &
State,
bool NewLine,
bool DryRun,
977 const FormatToken *LBrace =
State.NextToken->getPreviousNonComment();
979 if (!LBrace || LBrace->isNot(tok::l_brace) || LBrace->isNot(
BK_Block) ||
987 const ParenState &
P =
State.Stack.back();
989 int AdditionalIndent =
990 P.Indent -
Previous.Children[0]->Level * Style.IndentWidth;
993 P.NestedBlockIndent ==
P.LastSpace) {
994 if (
State.NextToken->MatchingParen &&
995 State.NextToken->MatchingParen->is(TT_LambdaLBrace)) {
996 State.Stack.pop_back();
998 if (LBrace->is(TT_LambdaLBrace))
999 AdditionalIndent = 0;
1003 BlockFormatter->format(
Previous.Children, DryRun, AdditionalIndent,
1008 if (
Previous.Children[0]->First->MustBreakBefore)
1019 const AnnotatedLine *Child =
Previous.Children[0];
1021 if (Child->Last->isTrailingComment())
1026 if (Style.ColumnLimit > 0 &&
1027 Child->Last->TotalLength +
State.Column + 2 > Style.ColumnLimit) {
1032 Whitespaces->replaceWhitespace(
1033 *Child->First, 0, 1,
1034 State.Column,
false,
1035 State.Line->InPPDirective);
1038 formatLine(*Child,
State.Column + 1, 0, DryRun);
1040 State.Column += 1 + Child->Last->TotalLength;
1047 WhitespaceManager *Whitespaces;
1048 const FormatStyle &Style;
1049 UnwrappedLineFormatter *BlockFormatter;
1053 class NoColumnLimitLineFormatter :
public LineFormatter {
1055 NoColumnLimitLineFormatter(ContinuationIndenter *
Indenter,
1056 WhitespaceManager *Whitespaces,
1057 const FormatStyle &Style,
1058 UnwrappedLineFormatter *BlockFormatter)
1059 : LineFormatter(
Indenter, Whitespaces, Style, BlockFormatter) {}
1063 unsigned formatLine(
const AnnotatedLine &
Line,
unsigned FirstIndent,
1064 unsigned FirstStartColumn,
bool DryRun)
override {
1066 LineState
State =
Indenter->getInitialState(FirstIndent, FirstStartColumn,
1068 while (
State.NextToken) {
1072 unsigned Penalty = 0;
1073 formatChildren(
State, Newline,
false, Penalty);
1081 class NoLineBreakFormatter :
public LineFormatter {
1083 NoLineBreakFormatter(ContinuationIndenter *
Indenter,
1084 WhitespaceManager *Whitespaces,
const FormatStyle &Style,
1085 UnwrappedLineFormatter *BlockFormatter)
1086 : LineFormatter(
Indenter, Whitespaces, Style, BlockFormatter) {}
1089 unsigned formatLine(
const AnnotatedLine &
Line,
unsigned FirstIndent,
1090 unsigned FirstStartColumn,
bool DryRun)
override {
1091 unsigned Penalty = 0;
1093 Indenter->getInitialState(FirstIndent, FirstStartColumn, &
Line, DryRun);
1094 while (
State.NextToken) {
1095 formatChildren(
State,
false, DryRun, Penalty);
1097 State,
State.NextToken->MustBreakBefore, DryRun);
1104 class OptimizingLineFormatter :
public LineFormatter {
1106 OptimizingLineFormatter(ContinuationIndenter *
Indenter,
1107 WhitespaceManager *Whitespaces,
1108 const FormatStyle &Style,
1109 UnwrappedLineFormatter *BlockFormatter)
1110 : LineFormatter(
Indenter, Whitespaces, Style, BlockFormatter) {}
1114 unsigned formatLine(
const AnnotatedLine &
Line,
unsigned FirstIndent,
1115 unsigned FirstStartColumn,
bool DryRun)
override {
1117 Indenter->getInitialState(FirstIndent, FirstStartColumn, &
Line, DryRun);
1122 State.Stack.back().BreakBeforeParameter =
true;
1125 return analyzeSolutionSpace(
State, DryRun);
1129 struct CompareLineStatePointers {
1130 bool operator()(LineState *obj1, LineState *obj2)
const {
1131 return *obj1 < *obj2;
1140 typedef std::pair<unsigned, unsigned> OrderedPenalty;
1154 typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
1157 typedef std::priority_queue<QueueItem, SmallVector<QueueItem>,
1158 std::greater<QueueItem>>
1169 unsigned analyzeSolutionSpace(LineState &InitialState,
bool DryRun) {
1170 std::set<LineState *, CompareLineStatePointers> Seen;
1178 StateNode *RootNode =
1179 new (Allocator.Allocate()) StateNode(InitialState,
false,
nullptr);
1180 Queue.push(QueueItem(OrderedPenalty(0, Count), RootNode));
1183 unsigned Penalty = 0;
1186 while (!Queue.empty()) {
1188 if (Count > 25000000)
1191 Penalty = Queue.top().first.first;
1192 StateNode *
Node = Queue.top().second;
1193 if (!
Node->State.NextToken) {
1194 LLVM_DEBUG(llvm::dbgs()
1195 <<
"\n---\nPenalty for line: " << Penalty <<
"\n");
1203 Node->State.IgnoreStackForComparison =
true;
1205 if (!Seen.insert(&
Node->State).second) {
1212 addNextStateToQueue(Penalty,
Node,
false, &Count, &Queue);
1214 addNextStateToQueue(Penalty,
Node,
true, &Count, &Queue);
1217 if (Queue.empty()) {
1220 LLVM_DEBUG(llvm::dbgs() <<
"Could not find a solution.\n");
1226 reconstructPath(InitialState, Queue.top().second);
1228 LLVM_DEBUG(llvm::dbgs()
1229 <<
"Total number of analyzed states: " << Count <<
"\n");
1230 LLVM_DEBUG(llvm::dbgs() <<
"---\n");
1239 void addNextStateToQueue(
unsigned Penalty, StateNode *PreviousNode,
1240 bool NewLine,
unsigned *Count, QueueType *Queue) {
1246 StateNode *
Node =
new (Allocator.Allocate())
1247 StateNode(PreviousNode->State,
NewLine, PreviousNode);
1248 if (!formatChildren(
Node->State,
NewLine,
true, Penalty))
1253 Queue->push(QueueItem(OrderedPenalty(Penalty, *Count),
Node));
1259 void reconstructPath(LineState &
State, StateNode *Best) {
1262 while (Best->Previous) {
1263 Path.push_back(Best);
1264 Best = Best->Previous;
1266 for (
const auto &
Node : llvm::reverse(Path)) {
1267 unsigned Penalty = 0;
1268 formatChildren(
State,
Node->NewLine,
false, Penalty);
1272 printLineState(
Node->Previous->State);
1273 if (
Node->NewLine) {
1274 llvm::dbgs() <<
"Penalty for placing "
1275 <<
Node->Previous->State.NextToken->Tok.getName()
1276 <<
" on a new line: " << Penalty <<
"\n";
1282 llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1289 int AdditionalIndent,
bool FixBadIndentation,
unsigned FirstStartColumn,
1290 unsigned NextStartColumn,
unsigned LastStartColumn) {
1291 LineJoiner Joiner(Style, Keywords, Lines);
1294 std::pair<const SmallVectorImpl<AnnotatedLine *> *,
unsigned> CacheKey(
1295 &Lines, AdditionalIndent);
1296 auto CacheIt = PenaltyCache.find(CacheKey);
1297 if (DryRun && CacheIt != PenaltyCache.end())
1298 return CacheIt->second;
1300 assert(!Lines.empty());
1301 unsigned Penalty = 0;
1302 LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->
Level,
1311 bool FirstLine =
true;
1313 Joiner.getNextMergedLine(DryRun, IndentTracker);
1314 Line; PrevPrevLine = PreviousLine, PreviousLine =
Line,
Line = NextLine,
1315 FirstLine =
false) {
1316 assert(
Line->First);
1318 unsigned Indent = IndentTracker.getIndent();
1324 bool PreviousRBrace =
1325 PreviousLine && PreviousLine->
startsWith(tok::r_brace);
1326 bool ContinueFormatting =
1327 TheLine.
Level > RangeMinLevel ||
1328 (TheLine.
Level == RangeMinLevel && !PreviousRBrace &&
1331 bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&
1333 bool ShouldFormat = TheLine.
Affected || FixIndentation;
1345 formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines,
Indent,
1346 LastLine ? LastStartColumn : NextStartColumn +
Indent);
1349 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1350 unsigned ColumnLimit = getColumnLimit(TheLine.
InPPDirective, NextLine);
1351 bool FitsIntoOneLine =
1354 (!Style.isJavaScript() || !Style.JavaScriptWrapImports)) ||
1355 (Style.isCSharp() &&
1357 if (Style.ColumnLimit == 0) {
1358 NoColumnLimitLineFormatter(
Indenter, Whitespaces, Style,
this)
1359 .formatLine(TheLine, NextStartColumn +
Indent,
1360 FirstLine ? FirstStartColumn : 0, DryRun);
1361 }
else if (FitsIntoOneLine) {
1362 Penalty += NoLineBreakFormatter(
Indenter, Whitespaces, Style,
this)
1363 .formatLine(TheLine, NextStartColumn +
Indent,
1364 FirstLine ? FirstStartColumn : 0, DryRun);
1366 Penalty += OptimizingLineFormatter(
Indenter, Whitespaces, Style,
this)
1367 .formatLine(TheLine, NextStartColumn +
Indent,
1368 FirstLine ? FirstStartColumn : 0, DryRun);
1376 if (!Tok->Children.empty())
1377 format(Tok->Children, DryRun);
1382 bool StartsNewLine =
1385 IndentTracker.adjustToUnmodifiedLine(TheLine);
1387 bool ReformatLeadingWhitespace =
1388 StartsNewLine && ((PreviousLine && PreviousLine->
Affected) ||
1391 if (ReformatLeadingWhitespace) {
1392 formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines,
1396 Whitespaces->addUntouchableToken(*TheLine.
First,
1402 Whitespaces->addUntouchableToken(*Tok, TheLine.
InPPDirective);
1404 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1408 markFinalized(TheLine.
First);
1410 PenaltyCache[CacheKey] = Penalty;
1414 void UnwrappedLineFormatter::formatFirstToken(
1418 unsigned NewlineIndent) {
1422 unsigned TokenIndent = Newlines ? NewlineIndent : 0;
1423 Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,
1430 if (RootToken.
is(tok::r_brace) &&
1438 if (PreviousLine ==
nullptr &&
Line.Level > 0)
1440 if (Newlines == 0 && !RootToken.
IsFirst)
1446 if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1447 PreviousLine->
Last->
is(tok::l_brace) &&
1451 !startsExternCBlock(*PreviousLine)) {
1457 switch (Style.EmptyLineBeforeAccessModifier) {
1466 if (PreviousLine->
Last->
isOneOf(tok::semi, tok::r_brace) && Newlines <= 1)
1472 const FormatToken *previousToken;
1473 if (PreviousLine->
Last->
is(tok::comment))
1476 previousToken = PreviousLine->
Last;
1477 if ((!previousToken || !previousToken->is(tok::l_brace)) && Newlines <= 1)
1489 switch (Style.EmptyLineAfterAccessModifier) {
1497 if (RootToken.
is(tok::r_brace))
1511 if (!Style.isJavaScript() &&
1518 Whitespaces->replaceWhitespace(RootToken, Newlines,
Indent,
Indent,
1520 Line.InPPDirective &&
1525 UnwrappedLineFormatter::getColumnLimit(
bool InPPDirective,
1526 const AnnotatedLine *NextLine)
const {
1529 bool ContinuesPPDirective =
1534 (NextLine->InPPDirective &&
1537 !NextLine->First->HasUnescapedNewline));
1538 return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);