1698 lines · cpp
1//===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "UnwrappedLineFormatter.h"10#include "FormatToken.h"11#include "NamespaceEndCommentsFixer.h"12#include "WhitespaceManager.h"13#include "llvm/Support/Debug.h"14#include <queue>15 16#define DEBUG_TYPE "format-formatter"17 18namespace clang {19namespace format {20 21namespace {22 23bool startsExternCBlock(const AnnotatedLine &Line) {24 const FormatToken *Next = Line.First->getNextNonComment();25 const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;26 return Line.startsWith(tok::kw_extern) && Next && Next->isStringLiteral() &&27 NextNext && NextNext->is(tok::l_brace);28}29 30bool isRecordLBrace(const FormatToken &Tok) {31 return Tok.isOneOf(TT_ClassLBrace, TT_EnumLBrace, TT_RecordLBrace,32 TT_StructLBrace, TT_UnionLBrace);33}34 35/// Tracks the indent level of \c AnnotatedLines across levels.36///37/// \c nextLine must be called for each \c AnnotatedLine, after which \c38/// getIndent() will return the indent for the last line \c nextLine was called39/// with.40/// If the line is not formatted (and thus the indent does not change), calling41/// \c adjustToUnmodifiedLine after the call to \c nextLine will cause42/// subsequent lines on the same level to be indented at the same level as the43/// given line.44class LevelIndentTracker {45public:46 LevelIndentTracker(const FormatStyle &Style,47 const AdditionalKeywords &Keywords, unsigned StartLevel,48 int AdditionalIndent)49 : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {50 for (unsigned i = 0; i != StartLevel; ++i)51 IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);52 }53 54 /// Returns the indent for the current line.55 unsigned getIndent() const { return Indent; }56 57 /// Update the indent state given that \p Line is going to be formatted58 /// next.59 void nextLine(const AnnotatedLine &Line) {60 Offset = getIndentOffset(Line);61 // Update the indent level cache size so that we can rely on it62 // having the right size in adjustToUnmodifiedline.63 if (Line.Level >= IndentForLevel.size())64 IndentForLevel.resize(Line.Level + 1, -1);65 if (Style.IndentPPDirectives == FormatStyle::PPDIS_Leave &&66 (Line.InPPDirective || Line.Type == LT_CommentAbovePPDirective)) {67 Indent = Line.InMacroBody68 ? (Line.Level - Line.PPLevel) * Style.IndentWidth +69 AdditionalIndent70 : Line.First->OriginalColumn;71 } else if (Style.IndentPPDirectives != FormatStyle::PPDIS_None &&72 (Line.InPPDirective ||73 (Style.IndentPPDirectives == FormatStyle::PPDIS_BeforeHash &&74 Line.Type == LT_CommentAbovePPDirective))) {75 unsigned PPIndentWidth =76 (Style.PPIndentWidth >= 0) ? Style.PPIndentWidth : Style.IndentWidth;77 Indent = Line.InMacroBody78 ? Line.PPLevel * PPIndentWidth +79 (Line.Level - Line.PPLevel) * Style.IndentWidth80 : Line.Level * PPIndentWidth;81 Indent += AdditionalIndent;82 } else {83 // When going to lower levels, forget previous higher levels so that we84 // recompute future higher levels. But don't forget them if we enter a PP85 // directive, since these do not terminate a C++ code block.86 if (!Line.InPPDirective) {87 assert(Line.Level <= IndentForLevel.size());88 IndentForLevel.resize(Line.Level + 1);89 }90 Indent = getIndent(Line.Level);91 }92 if (static_cast<int>(Indent) + Offset >= 0)93 Indent += Offset;94 if (Line.IsContinuation)95 Indent = Line.Level * Style.IndentWidth + Style.ContinuationIndentWidth;96 }97 98 /// Update the level indent to adapt to the given \p Line.99 ///100 /// When a line is not formatted, we move the subsequent lines on the same101 /// level to the same indent.102 /// Note that \c nextLine must have been called before this method.103 void adjustToUnmodifiedLine(const AnnotatedLine &Line) {104 if (Line.InPPDirective || Line.IsContinuation)105 return;106 assert(Line.Level < IndentForLevel.size());107 if (Line.First->is(tok::comment) && IndentForLevel[Line.Level] != -1)108 return;109 unsigned LevelIndent = Line.First->OriginalColumn;110 if (static_cast<int>(LevelIndent) - Offset >= 0)111 LevelIndent -= Offset;112 IndentForLevel[Line.Level] = LevelIndent;113 }114 115private:116 /// Get the offset of the line relatively to the level.117 ///118 /// For example, 'public:' labels in classes are offset by 1 or 2119 /// characters to the left from their level.120 int getIndentOffset(const AnnotatedLine &Line) {121 if (Style.isJava() || Style.isJavaScript() || Style.isCSharp())122 return 0;123 const auto &RootToken = *Line.First;124 if (Line.Type == LT_AccessModifier ||125 RootToken.isAccessSpecifier(/*ColonRequired=*/false) ||126 RootToken.isObjCAccessSpecifier() ||127 (RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals) &&128 RootToken.Next && RootToken.Next->is(tok::colon))) {129 // The AccessModifierOffset may be overridden by IndentAccessModifiers,130 // in which case we take a negative value of the IndentWidth to simulate131 // the upper indent level.132 return Style.IndentAccessModifiers ? -Style.IndentWidth133 : Style.AccessModifierOffset;134 }135 return 0;136 }137 138 /// Get the indent of \p Level from \p IndentForLevel.139 ///140 /// \p IndentForLevel must contain the indent for the level \c l141 /// at \p IndentForLevel[l], or a value < 0 if the indent for142 /// that level is unknown.143 unsigned getIndent(unsigned Level) const {144 assert(Level < IndentForLevel.size());145 if (IndentForLevel[Level] != -1)146 return IndentForLevel[Level];147 if (Level == 0)148 return 0;149 return getIndent(Level - 1) + Style.IndentWidth;150 }151 152 const FormatStyle &Style;153 const AdditionalKeywords &Keywords;154 const unsigned AdditionalIndent;155 156 /// The indent in characters for each level. It remembers the indent of157 /// previous lines (that are not PP directives) of equal or lower levels. This158 /// is used to align formatted lines to the indent of previous non-formatted159 /// lines. Think about the --lines parameter of clang-format.160 SmallVector<int> IndentForLevel;161 162 /// Offset of the current line relative to the indent level.163 ///164 /// For example, the 'public' keywords is often indented with a negative165 /// offset.166 int Offset = 0;167 168 /// The current line's indent.169 unsigned Indent = 0;170};171 172const FormatToken *173getMatchingNamespaceToken(const AnnotatedLine *Line,174 const ArrayRef<AnnotatedLine *> &AnnotatedLines) {175 if (!Line->startsWith(tok::r_brace))176 return nullptr;177 size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex;178 if (StartLineIndex == UnwrappedLine::kInvalidIndex)179 return nullptr;180 assert(StartLineIndex < AnnotatedLines.size());181 return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();182}183 184StringRef getNamespaceTokenText(const AnnotatedLine *Line) {185 const FormatToken *NamespaceToken = Line->First->getNamespaceToken();186 return NamespaceToken ? NamespaceToken->TokenText : StringRef();187}188 189StringRef190getMatchingNamespaceTokenText(const AnnotatedLine *Line,191 const ArrayRef<AnnotatedLine *> &AnnotatedLines) {192 const FormatToken *NamespaceToken =193 getMatchingNamespaceToken(Line, AnnotatedLines);194 return NamespaceToken ? NamespaceToken->TokenText : StringRef();195}196 197class LineJoiner {198public:199 LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords,200 const SmallVectorImpl<AnnotatedLine *> &Lines)201 : Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()),202 AnnotatedLines(Lines) {}203 204 /// Returns the next line, merging multiple lines into one if possible.205 const AnnotatedLine *getNextMergedLine(bool DryRun,206 LevelIndentTracker &IndentTracker) {207 if (Next == End)208 return nullptr;209 const AnnotatedLine *Current = *Next;210 IndentTracker.nextLine(*Current);211 unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next, End);212 if (MergedLines > 0 && Style.ColumnLimit == 0) {213 // Disallow line merging if there is a break at the start of one of the214 // input lines.215 for (unsigned i = 0; i < MergedLines; ++i)216 if (Next[i + 1]->First->NewlinesBefore > 0)217 MergedLines = 0;218 }219 if (!DryRun)220 for (unsigned i = 0; i < MergedLines; ++i)221 join(*Next[0], *Next[i + 1]);222 Next = Next + MergedLines + 1;223 return Current;224 }225 226private:227 /// Calculates how many lines can be merged into 1 starting at \p I.228 unsigned229 tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,230 ArrayRef<AnnotatedLine *>::const_iterator I,231 ArrayRef<AnnotatedLine *>::const_iterator E) {232 // Can't join the last line with anything.233 if (I + 1 == E)234 return 0;235 // We can never merge stuff if there are trailing line comments.236 const AnnotatedLine *TheLine = *I;237 if (TheLine->Last->is(TT_LineComment))238 return 0;239 const auto &NextLine = *I[1];240 if (NextLine.Type == LT_Invalid || NextLine.First->MustBreakBefore)241 return 0;242 if (TheLine->InPPDirective &&243 (!NextLine.InPPDirective || NextLine.First->HasUnescapedNewline)) {244 return 0;245 }246 247 const auto Indent = IndentTracker.getIndent();248 if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)249 return 0;250 251 unsigned Limit =252 Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;253 // If we already exceed the column limit, we set 'Limit' to 0. The different254 // tryMerge..() functions can then decide whether to still do merging.255 Limit = TheLine->Last->TotalLength > Limit256 ? 0257 : Limit - TheLine->Last->TotalLength;258 259 if (TheLine->Last->is(TT_FunctionLBrace) &&260 TheLine->First == TheLine->Last) {261 const bool EmptyFunctionBody = NextLine.First->is(tok::r_brace);262 if ((EmptyFunctionBody && !Style.BraceWrapping.SplitEmptyFunction) ||263 (!EmptyFunctionBody &&264 Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Always)) {265 return tryMergeSimpleBlock(I, E, Limit);266 }267 }268 269 const auto *PreviousLine = I != AnnotatedLines.begin() ? I[-1] : nullptr;270 // Handle empty record blocks where the brace has already been wrapped.271 if (PreviousLine && TheLine->Last->is(tok::l_brace) &&272 TheLine->First == TheLine->Last) {273 bool EmptyBlock = NextLine.First->is(tok::r_brace);274 275 const FormatToken *Tok = PreviousLine->First;276 if (Tok && Tok->is(tok::comment))277 Tok = Tok->getNextNonComment();278 279 if (Tok && Tok->getNamespaceToken()) {280 return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock281 ? tryMergeSimpleBlock(I, E, Limit)282 : 0;283 }284 285 if (Tok && Tok->is(tok::kw_typedef))286 Tok = Tok->getNextNonComment();287 if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union,288 tok::kw_extern, Keywords.kw_interface,289 Keywords.kw_record)) {290 return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock291 ? tryMergeSimpleBlock(I, E, Limit)292 : 0;293 }294 295 if (Tok && Tok->is(tok::kw_template) &&296 Style.BraceWrapping.SplitEmptyRecord && EmptyBlock) {297 return 0;298 }299 }300 301 auto ShouldMergeShortFunctions = [this, &I, &NextLine, PreviousLine,302 TheLine]() {303 if (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All)304 return true;305 if (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&306 NextLine.First->is(tok::r_brace)) {307 return true;308 }309 310 if (Style.AllowShortFunctionsOnASingleLine &311 FormatStyle::SFS_InlineOnly) {312 // Just checking TheLine->Level != 0 is not enough, because it313 // provokes treating functions inside indented namespaces as short.314 if (Style.isJavaScript() && TheLine->Last->is(TT_FunctionLBrace))315 return true;316 317 if (TheLine->Level != 0) {318 if (!PreviousLine)319 return false;320 321 // TODO: Use IndentTracker to avoid loop?322 // Find the last line with lower level.323 const AnnotatedLine *Line = nullptr;324 for (auto J = I - 1; J >= AnnotatedLines.begin(); --J) {325 assert(*J);326 if (((*J)->InPPDirective && !(*J)->InMacroBody) ||327 (*J)->isComment() || (*J)->Level > TheLine->Level) {328 continue;329 }330 if ((*J)->Level < TheLine->Level ||331 (Style.BreakBeforeBraces == FormatStyle::BS_Whitesmiths &&332 (*J)->First->is(tok::l_brace))) {333 Line = *J;334 break;335 }336 }337 338 if (!Line)339 return false;340 341 // Check if the found line starts a record.342 const auto *LastNonComment = Line->getLastNonComment();343 // There must be another token (usually `{`), because we chose a344 // non-PPDirective and non-comment line that has a smaller level.345 assert(LastNonComment);346 return isRecordLBrace(*LastNonComment);347 }348 }349 350 return false;351 };352 353 bool MergeShortFunctions = ShouldMergeShortFunctions();354 355 const auto *FirstNonComment = TheLine->getFirstNonComment();356 if (!FirstNonComment)357 return 0;358 359 // FIXME: There are probably cases where we should use FirstNonComment360 // instead of TheLine->First.361 362 if (Style.AllowShortNamespacesOnASingleLine &&363 TheLine->First->is(tok::kw_namespace)) {364 const auto result = tryMergeNamespace(I, E, Limit);365 if (result > 0)366 return result;367 }368 369 if (Style.CompactNamespaces) {370 if (const auto *NSToken = TheLine->First->getNamespaceToken()) {371 int J = 1;372 assert(TheLine->MatchingClosingBlockLineIndex > 0);373 for (auto ClosingLineIndex = TheLine->MatchingClosingBlockLineIndex - 1;374 I + J != E && NSToken->TokenText == getNamespaceTokenText(I[J]) &&375 ClosingLineIndex == I[J]->MatchingClosingBlockLineIndex &&376 I[J]->Last->TotalLength < Limit;377 ++J, --ClosingLineIndex) {378 Limit -= I[J]->Last->TotalLength + 1;379 380 // Reduce indent level for bodies of namespaces which were compacted,381 // but only if their content was indented in the first place.382 auto *ClosingLine = AnnotatedLines.begin() + ClosingLineIndex + 1;383 const int OutdentBy = I[J]->Level - TheLine->Level;384 assert(OutdentBy >= 0);385 for (auto *CompactedLine = I + J; CompactedLine <= ClosingLine;386 ++CompactedLine) {387 if (!(*CompactedLine)->InPPDirective) {388 const int Level = (*CompactedLine)->Level;389 (*CompactedLine)->Level = std::max(Level - OutdentBy, 0);390 }391 }392 }393 return J - 1;394 }395 396 if (auto nsToken = getMatchingNamespaceToken(TheLine, AnnotatedLines)) {397 int i = 0;398 unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;399 for (; I + 1 + i != E &&400 nsToken->TokenText ==401 getMatchingNamespaceTokenText(I[i + 1], AnnotatedLines) &&402 openingLine == I[i + 1]->MatchingOpeningBlockLineIndex;403 i++, --openingLine) {404 // No space between consecutive braces.405 I[i + 1]->First->SpacesRequiredBefore =406 I[i]->Last->isNot(tok::r_brace);407 408 // Indent like the outer-most namespace.409 IndentTracker.nextLine(*I[i + 1]);410 }411 return i;412 }413 }414 415 const auto *LastNonComment = TheLine->getLastNonComment();416 assert(LastNonComment);417 // FIXME: There are probably cases where we should use LastNonComment418 // instead of TheLine->Last.419 420 // Try to merge a function block with left brace unwrapped.421 if (LastNonComment->is(TT_FunctionLBrace) &&422 TheLine->First != LastNonComment) {423 return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;424 }425 426 // Try to merge a control statement block with left brace unwrapped.427 if (TheLine->Last->is(tok::l_brace) && FirstNonComment != TheLine->Last &&428 (FirstNonComment->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for,429 TT_ForEachMacro) ||430 TheLine->startsWithExportBlock())) {431 return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never432 ? tryMergeSimpleBlock(I, E, Limit)433 : 0;434 }435 // Try to merge a control statement block with left brace wrapped.436 if (NextLine.First->is(TT_ControlStatementLBrace)) {437 // If possible, merge the next line's wrapped left brace with the438 // current line. Otherwise, leave it on the next line, as this is a439 // multi-line control statement.440 return Style.BraceWrapping.AfterControlStatement ==441 FormatStyle::BWACS_Always442 ? tryMergeSimpleBlock(I, E, Limit)443 : 0;444 }445 if (PreviousLine && TheLine->First->is(tok::l_brace)) {446 switch (PreviousLine->First->Tok.getKind()) {447 case tok::at:448 // Don't merge block with left brace wrapped after ObjC special blocks.449 if (PreviousLine->First->Next &&450 PreviousLine->First->Next->isOneOf(tok::objc_autoreleasepool,451 tok::objc_synchronized)) {452 return 0;453 }454 break;455 456 case tok::kw_case:457 case tok::kw_default:458 // Don't merge block with left brace wrapped after case labels.459 return 0;460 461 default:462 break;463 }464 }465 466 // Don't merge an empty template class or struct if SplitEmptyRecords467 // is defined.468 if (PreviousLine && Style.BraceWrapping.SplitEmptyRecord &&469 TheLine->Last->is(tok::l_brace) && PreviousLine->Last) {470 const FormatToken *Previous = PreviousLine->Last;471 if (Previous) {472 if (Previous->is(tok::comment))473 Previous = Previous->getPreviousNonComment();474 if (Previous) {475 if (Previous->is(tok::greater) && !PreviousLine->InPPDirective)476 return 0;477 if (Previous->is(tok::identifier)) {478 const FormatToken *PreviousPrevious =479 Previous->getPreviousNonComment();480 if (PreviousPrevious &&481 PreviousPrevious->isOneOf(tok::kw_class, tok::kw_struct)) {482 return 0;483 }484 }485 }486 }487 }488 489 if (TheLine->First->is(TT_SwitchExpressionLabel)) {490 return Style.AllowShortCaseExpressionOnASingleLine491 ? tryMergeShortCaseLabels(I, E, Limit)492 : 0;493 }494 495 if (TheLine->Last->is(tok::l_brace)) {496 bool ShouldMerge = false;497 // Try to merge records.498 if (TheLine->Last->is(TT_EnumLBrace)) {499 ShouldMerge = Style.AllowShortEnumsOnASingleLine;500 } else if (TheLine->Last->is(TT_CompoundRequirementLBrace)) {501 ShouldMerge = Style.AllowShortCompoundRequirementOnASingleLine;502 } else if (TheLine->Last->isOneOf(TT_ClassLBrace, TT_StructLBrace,503 TT_RecordLBrace)) {504 // NOTE: We use AfterClass (whereas AfterStruct exists) for both classes505 // and structs, but it seems that wrapping is still handled correctly506 // elsewhere.507 ShouldMerge = !Style.BraceWrapping.AfterClass ||508 (NextLine.First->is(tok::r_brace) &&509 !Style.BraceWrapping.SplitEmptyRecord);510 } else if (TheLine->InPPDirective ||511 TheLine->First->isNoneOf(tok::kw_class, tok::kw_enum,512 tok::kw_struct, Keywords.kw_record)) {513 // Try to merge a block with left brace unwrapped that wasn't yet514 // covered.515 ShouldMerge = !Style.BraceWrapping.AfterFunction ||516 (NextLine.First->is(tok::r_brace) &&517 !Style.BraceWrapping.SplitEmptyFunction);518 }519 return ShouldMerge ? tryMergeSimpleBlock(I, E, Limit) : 0;520 }521 522 // Try to merge a function block with left brace wrapped.523 if (NextLine.First->is(TT_FunctionLBrace) &&524 Style.BraceWrapping.AfterFunction) {525 if (NextLine.Last->is(TT_LineComment))526 return 0;527 528 // Check for Limit <= 2 to account for the " {".529 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))530 return 0;531 Limit -= 2;532 533 unsigned MergedLines = 0;534 if (MergeShortFunctions ||535 (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&536 NextLine.First == NextLine.Last && I + 2 != E &&537 I[2]->First->is(tok::r_brace))) {538 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);539 // If we managed to merge the block, count the function header, which is540 // on a separate line.541 if (MergedLines > 0)542 ++MergedLines;543 }544 return MergedLines;545 }546 auto IsElseLine = [&TheLine]() -> bool {547 const FormatToken *First = TheLine->First;548 if (First->is(tok::kw_else))549 return true;550 551 return First->is(tok::r_brace) && First->Next &&552 First->Next->is(tok::kw_else);553 };554 if (TheLine->First->is(tok::kw_if) ||555 (IsElseLine() && (Style.AllowShortIfStatementsOnASingleLine ==556 FormatStyle::SIS_AllIfsAndElse))) {557 return Style.AllowShortIfStatementsOnASingleLine558 ? tryMergeSimpleControlStatement(I, E, Limit)559 : 0;560 }561 if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while, tok::kw_do,562 TT_ForEachMacro)) {563 return Style.AllowShortLoopsOnASingleLine564 ? tryMergeSimpleControlStatement(I, E, Limit)565 : 0;566 }567 if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {568 return Style.AllowShortCaseLabelsOnASingleLine569 ? tryMergeShortCaseLabels(I, E, Limit)570 : 0;571 }572 if (TheLine->InPPDirective &&573 (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {574 return tryMergeSimplePPDirective(I, E, Limit);575 }576 return 0;577 }578 579 unsigned580 tryMergeSimplePPDirective(ArrayRef<AnnotatedLine *>::const_iterator I,581 ArrayRef<AnnotatedLine *>::const_iterator E,582 unsigned Limit) {583 if (Limit == 0)584 return 0;585 if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)586 return 0;587 if (1 + I[1]->Last->TotalLength > Limit)588 return 0;589 return 1;590 }591 592 unsigned tryMergeNamespace(ArrayRef<AnnotatedLine *>::const_iterator I,593 ArrayRef<AnnotatedLine *>::const_iterator E,594 unsigned Limit) {595 if (Limit == 0)596 return 0;597 598 // The merging code is relative to the opening namespace brace, which could599 // be either on the first or second line due to the brace wrapping rules.600 const bool OpenBraceWrapped = Style.BraceWrapping.AfterNamespace;601 const auto *BraceOpenLine = I + OpenBraceWrapped;602 603 assert(*BraceOpenLine);604 if (BraceOpenLine[0]->Last->isNot(TT_NamespaceLBrace))605 return 0;606 607 if (std::distance(BraceOpenLine, E) <= 2)608 return 0;609 610 if (BraceOpenLine[0]->Last->is(tok::comment))611 return 0;612 613 assert(BraceOpenLine[1]);614 const auto &L1 = *BraceOpenLine[1];615 if (L1.InPPDirective != (*I)->InPPDirective ||616 (L1.InPPDirective && L1.First->HasUnescapedNewline)) {617 return 0;618 }619 620 assert(BraceOpenLine[2]);621 const auto &L2 = *BraceOpenLine[2];622 if (L2.Type == LT_Invalid)623 return 0;624 625 Limit = limitConsideringMacros(I + 1, E, Limit);626 627 const auto LinesToBeMerged = OpenBraceWrapped + 2;628 if (!nextNLinesFitInto(I, I + LinesToBeMerged, Limit))629 return 0;630 631 // Check if it's a namespace inside a namespace, and call recursively if so.632 // '3' is the sizes of the whitespace and closing brace for " _inner_ }".633 if (L1.First->is(tok::kw_namespace)) {634 if (L1.Last->is(tok::comment) || !Style.CompactNamespaces)635 return 0;636 637 assert(Limit >= L1.Last->TotalLength + 3);638 const auto InnerLimit = Limit - L1.Last->TotalLength - 3;639 const auto MergedLines =640 tryMergeNamespace(BraceOpenLine + 1, E, InnerLimit);641 if (MergedLines == 0)642 return 0;643 const auto N = MergedLines + LinesToBeMerged;644 // Check if there is even a line after the inner result.645 if (std::distance(I, E) <= N)646 return 0;647 // Check that the line after the inner result starts with a closing brace648 // which we are permitted to merge into one line.649 if (I[N]->First->is(TT_NamespaceRBrace) &&650 !I[N]->First->MustBreakBefore &&651 BraceOpenLine[MergedLines + 1]->Last->isNot(tok::comment) &&652 nextNLinesFitInto(I, I + N + 1, Limit)) {653 return N;654 }655 return 0;656 }657 658 // There's no inner namespace, so we are considering to merge at most one659 // line.660 661 // The line which is in the namespace should end with semicolon.662 if (L1.Last->isNot(tok::semi))663 return 0;664 665 // Last, check that the third line starts with a closing brace.666 if (L2.First->isNot(TT_NamespaceRBrace) || L2.First->MustBreakBefore)667 return 0;668 669 // If so, merge all lines.670 return LinesToBeMerged;671 }672 673 unsigned674 tryMergeSimpleControlStatement(ArrayRef<AnnotatedLine *>::const_iterator I,675 ArrayRef<AnnotatedLine *>::const_iterator E,676 unsigned Limit) {677 if (Limit == 0)678 return 0;679 if (Style.BraceWrapping.AfterControlStatement ==680 FormatStyle::BWACS_Always &&681 I[1]->First->is(tok::l_brace) &&682 Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never) {683 return 0;684 }685 if (I[1]->InPPDirective != (*I)->InPPDirective ||686 (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) {687 return 0;688 }689 Limit = limitConsideringMacros(I + 1, E, Limit);690 AnnotatedLine &Line = **I;691 if (Line.First->isNoneOf(tok::kw_do, tok::kw_else) &&692 Line.Last->isNoneOf(tok::kw_else, tok::r_paren)) {693 return 0;694 }695 // Only merge `do while` if `do` is the only statement on the line.696 if (Line.First->is(tok::kw_do) && Line.Last->isNot(tok::kw_do))697 return 0;698 if (1 + I[1]->Last->TotalLength > Limit)699 return 0;700 // Don't merge with loops, ifs, a single semicolon or a line comment.701 if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,702 TT_ForEachMacro, TT_LineComment)) {703 return 0;704 }705 // Only inline simple if's (no nested if or else), unless specified706 if (Style.AllowShortIfStatementsOnASingleLine ==707 FormatStyle::SIS_WithoutElse) {708 if (I + 2 != E && Line.startsWith(tok::kw_if) &&709 I[2]->First->is(tok::kw_else)) {710 return 0;711 }712 }713 return 1;714 }715 716 unsigned tryMergeShortCaseLabels(ArrayRef<AnnotatedLine *>::const_iterator I,717 ArrayRef<AnnotatedLine *>::const_iterator E,718 unsigned Limit) {719 if (Limit == 0 || I + 1 == E ||720 I[1]->First->isOneOf(tok::kw_case, tok::kw_default)) {721 return 0;722 }723 if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))724 return 0;725 unsigned NumStmts = 0;726 unsigned Length = 0;727 bool EndsWithComment = false;728 bool InPPDirective = I[0]->InPPDirective;729 bool InMacroBody = I[0]->InMacroBody;730 const unsigned Level = I[0]->Level;731 for (; NumStmts < 3; ++NumStmts) {732 if (I + 1 + NumStmts == E)733 break;734 const AnnotatedLine *Line = I[1 + NumStmts];735 if (Line->InPPDirective != InPPDirective)736 break;737 if (Line->InMacroBody != InMacroBody)738 break;739 if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))740 break;741 if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,742 tok::kw_while) ||743 EndsWithComment) {744 return 0;745 }746 if (Line->First->is(tok::comment)) {747 if (Level != Line->Level)748 return 0;749 const auto *J = I + 2 + NumStmts;750 for (; J != E; ++J) {751 Line = *J;752 if (Line->InPPDirective != InPPDirective)753 break;754 if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))755 break;756 if (Line->First->isNot(tok::comment) || Level != Line->Level)757 return 0;758 }759 break;760 }761 if (Line->Last->is(tok::comment))762 EndsWithComment = true;763 Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.764 }765 if (NumStmts == 0 || NumStmts == 3 || Length > Limit)766 return 0;767 return NumStmts;768 }769 770 unsigned tryMergeSimpleBlock(ArrayRef<AnnotatedLine *>::const_iterator I,771 ArrayRef<AnnotatedLine *>::const_iterator E,772 unsigned Limit) {773 // Don't merge with a preprocessor directive.774 if (I[1]->Type == LT_PreprocessorDirective)775 return 0;776 777 AnnotatedLine &Line = **I;778 779 // Don't merge ObjC @ keywords and methods.780 // FIXME: If an option to allow short exception handling clauses on a single781 // line is added, change this to not return for @try and friends.782 if (!Style.isJava() && Line.First->isOneOf(tok::at, tok::minus, tok::plus))783 return 0;784 785 // Check that the current line allows merging. This depends on whether we786 // are in a control flow statements as well as several style flags.787 if (Line.First->is(tok::kw_case) ||788 (Line.First->Next && Line.First->Next->is(tok::kw_else))) {789 return 0;790 }791 // default: in switch statement792 if (Line.First->is(tok::kw_default)) {793 const FormatToken *Tok = Line.First->getNextNonComment();794 if (Tok && Tok->is(tok::colon))795 return 0;796 }797 798 auto IsCtrlStmt = [](const auto &Line) {799 return Line.First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,800 tok::kw_do, tok::kw_for, TT_ForEachMacro);801 };802 803 const bool IsSplitBlock =804 Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never ||805 (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Empty &&806 I[1]->First->isNot(tok::r_brace));807 808 if (IsCtrlStmt(Line) ||809 Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,810 tok::kw___finally, tok::r_brace,811 Keywords.kw___except) ||812 Line.startsWithExportBlock()) {813 if (IsSplitBlock)814 return 0;815 // Don't merge when we can't except the case when816 // the control statement block is empty817 if (!Style.AllowShortIfStatementsOnASingleLine &&818 Line.First->isOneOf(tok::kw_if, tok::kw_else) &&819 !Style.BraceWrapping.AfterControlStatement &&820 I[1]->First->isNot(tok::r_brace)) {821 return 0;822 }823 if (!Style.AllowShortIfStatementsOnASingleLine &&824 Line.First->isOneOf(tok::kw_if, tok::kw_else) &&825 Style.BraceWrapping.AfterControlStatement ==826 FormatStyle::BWACS_Always &&827 I + 2 != E && I[2]->First->isNot(tok::r_brace)) {828 return 0;829 }830 if (!Style.AllowShortLoopsOnASingleLine &&831 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,832 TT_ForEachMacro) &&833 !Style.BraceWrapping.AfterControlStatement &&834 I[1]->First->isNot(tok::r_brace)) {835 return 0;836 }837 if (!Style.AllowShortLoopsOnASingleLine &&838 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,839 TT_ForEachMacro) &&840 Style.BraceWrapping.AfterControlStatement ==841 FormatStyle::BWACS_Always &&842 I + 2 != E && I[2]->First->isNot(tok::r_brace)) {843 return 0;844 }845 // FIXME: Consider an option to allow short exception handling clauses on846 // a single line.847 // FIXME: This isn't covered by tests.848 // FIXME: For catch, __except, __finally the first token on the line849 // is '}', so this isn't correct here.850 if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,851 Keywords.kw___except, tok::kw___finally)) {852 return 0;853 }854 }855 856 if (Line.endsWith(tok::l_brace)) {857 if (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never &&858 Line.First->is(TT_BlockLBrace)) {859 return 0;860 }861 862 if (IsSplitBlock && Line.First == Line.Last &&863 I > AnnotatedLines.begin() &&864 (I[-1]->endsWith(tok::kw_else) || IsCtrlStmt(*I[-1]))) {865 return 0;866 }867 FormatToken *Tok = I[1]->First;868 auto ShouldMerge = [Tok]() {869 if (Tok->isNot(tok::r_brace) || Tok->MustBreakBefore)870 return false;871 const FormatToken *Next = Tok->getNextNonComment();872 return !Next || Next->is(tok::semi);873 };874 875 if (ShouldMerge()) {876 // We merge empty blocks even if the line exceeds the column limit.877 Tok->SpacesRequiredBefore =878 Style.SpaceInEmptyBraces != FormatStyle::SIEB_Never ||879 Line.Last->is(tok::comment);880 Tok->CanBreakBefore = true;881 return 1;882 } else if (Limit != 0 && !Line.startsWithNamespace() &&883 !startsExternCBlock(Line)) {884 // We don't merge short records.885 if (isRecordLBrace(*Line.Last))886 return 0;887 888 // Check that we still have three lines and they fit into the limit.889 if (I + 2 == E || I[2]->Type == LT_Invalid)890 return 0;891 Limit = limitConsideringMacros(I + 2, E, Limit);892 893 if (!nextTwoLinesFitInto(I, Limit))894 return 0;895 896 // Second, check that the next line does not contain any braces - if it897 // does, readability declines when putting it into a single line.898 if (I[1]->Last->is(TT_LineComment))899 return 0;900 do {901 if (Tok->is(tok::l_brace) && Tok->isNot(BK_BracedInit))902 return 0;903 Tok = Tok->Next;904 } while (Tok);905 906 // Last, check that the third line starts with a closing brace.907 Tok = I[2]->First;908 if (Tok->isNot(tok::r_brace))909 return 0;910 911 // Don't merge "if (a) { .. } else {".912 if (Tok->Next && Tok->Next->is(tok::kw_else))913 return 0;914 915 // Don't merge a trailing multi-line control statement block like:916 // } else if (foo &&917 // bar)918 // { <-- current Line919 // baz();920 // }921 if (Line.First == Line.Last &&922 Line.First->is(TT_ControlStatementLBrace) &&923 Style.BraceWrapping.AfterControlStatement ==924 FormatStyle::BWACS_MultiLine) {925 return 0;926 }927 928 return 2;929 }930 } else if (I[1]->First->is(tok::l_brace)) {931 if (I[1]->Last->is(TT_LineComment))932 return 0;933 934 // Check for Limit <= 2 to account for the " {".935 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))936 return 0;937 Limit -= 2;938 unsigned MergedLines = 0;939 if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never ||940 (I[1]->First == I[1]->Last && I + 2 != E &&941 I[2]->First->is(tok::r_brace))) {942 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);943 // If we managed to merge the block, count the statement header, which944 // is on a separate line.945 if (MergedLines > 0)946 ++MergedLines;947 }948 return MergedLines;949 }950 return 0;951 }952 953 /// Returns the modified column limit for \p I if it is inside a macro and954 /// needs a trailing '\'.955 unsigned limitConsideringMacros(ArrayRef<AnnotatedLine *>::const_iterator I,956 ArrayRef<AnnotatedLine *>::const_iterator E,957 unsigned Limit) {958 if (I[0]->InPPDirective && I + 1 != E &&959 !I[1]->First->HasUnescapedNewline && I[1]->First->isNot(tok::eof)) {960 return Limit < 2 ? 0 : Limit - 2;961 }962 return Limit;963 }964 965 bool nextTwoLinesFitInto(ArrayRef<AnnotatedLine *>::const_iterator I,966 unsigned Limit) {967 if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)968 return false;969 return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;970 }971 972 bool nextNLinesFitInto(ArrayRef<AnnotatedLine *>::const_iterator I,973 ArrayRef<AnnotatedLine *>::const_iterator E,974 unsigned Limit) {975 unsigned JoinedLength = 0;976 for (const auto *J = I + 1; J != E; ++J) {977 if ((*J)->First->MustBreakBefore)978 return false;979 980 JoinedLength += 1 + (*J)->Last->TotalLength;981 if (JoinedLength > Limit)982 return false;983 }984 return true;985 }986 987 bool containsMustBreak(const AnnotatedLine *Line) {988 assert(Line->First);989 // Ignore the first token, because in this situation, it applies more to the990 // last token of the previous line.991 for (const FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next)992 if (Tok->MustBreakBefore)993 return true;994 return false;995 }996 997 void join(AnnotatedLine &A, const AnnotatedLine &B) {998 assert(!A.Last->Next);999 assert(!B.First->Previous);1000 if (B.Affected || B.LeadingEmptyLinesAffected) {1001 assert(B.Affected || A.Last->Children.empty());1002 A.Affected = true;1003 }1004 A.Last->Next = B.First;1005 B.First->Previous = A.Last;1006 B.First->CanBreakBefore = true;1007 unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;1008 for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {1009 Tok->TotalLength += LengthA;1010 A.Last = Tok;1011 }1012 }1013 1014 const FormatStyle &Style;1015 const AdditionalKeywords &Keywords;1016 const ArrayRef<AnnotatedLine *>::const_iterator End;1017 1018 ArrayRef<AnnotatedLine *>::const_iterator Next;1019 const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;1020};1021 1022static void markFinalized(FormatToken *Tok) {1023 if (Tok->is(tok::hash) && !Tok->Previous && Tok->Next &&1024 Tok->Next->isOneOf(tok::pp_if, tok::pp_ifdef, tok::pp_ifndef,1025 tok::pp_elif, tok::pp_elifdef, tok::pp_elifndef,1026 tok::pp_else, tok::pp_endif)) {1027 Tok = Tok->Next;1028 }1029 for (; Tok; Tok = Tok->Next) {1030 if (Tok->MacroCtx && Tok->MacroCtx->Role == MR_ExpandedArg) {1031 // In the first pass we format all macro arguments in the expanded token1032 // stream. Instead of finalizing the macro arguments, we mark that they1033 // will be modified as unexpanded arguments (as part of the macro call1034 // formatting) in the next pass.1035 Tok->MacroCtx->Role = MR_UnexpandedArg;1036 // Reset whether spaces or a line break are required before this token, as1037 // that is context dependent, and that context may change when formatting1038 // the macro call. For example, given M(x) -> 2 * x, and the macro call1039 // M(var), the token 'var' will have SpacesRequiredBefore = 1 after being1040 // formatted as part of the expanded macro, but SpacesRequiredBefore = 01041 // for its position within the macro call.1042 Tok->SpacesRequiredBefore = 0;1043 if (!Tok->MustBreakBeforeFinalized)1044 Tok->MustBreakBefore = 0;1045 } else {1046 Tok->Finalized = true;1047 }1048 }1049}1050 1051#ifndef NDEBUG1052static void printLineState(const LineState &State) {1053 llvm::dbgs() << "State: ";1054 for (const ParenState &P : State.Stack) {1055 llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"1056 << P.LastSpace << "|" << P.NestedBlockIndent << " ";1057 }1058 llvm::dbgs() << State.NextToken->TokenText << "\n";1059}1060#endif1061 1062/// Base class for classes that format one \c AnnotatedLine.1063class LineFormatter {1064public:1065 LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,1066 const FormatStyle &Style,1067 UnwrappedLineFormatter *BlockFormatter)1068 : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),1069 BlockFormatter(BlockFormatter) {}1070 virtual ~LineFormatter() {}1071 1072 /// Formats an \c AnnotatedLine and returns the penalty.1073 ///1074 /// If \p DryRun is \c false, directly applies the changes.1075 virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,1076 unsigned FirstStartColumn, bool DryRun) = 0;1077 1078protected:1079 /// If the \p State's next token is an r_brace closing a nested block,1080 /// format the nested block before it.1081 ///1082 /// Returns \c true if all children could be placed successfully and adapts1083 /// \p Penalty as well as \p State. If \p DryRun is false, also directly1084 /// creates changes using \c Whitespaces.1085 ///1086 /// The crucial idea here is that children always get formatted upon1087 /// encountering the closing brace right after the nested block. Now, if we1088 /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is1089 /// \c false), the entire block has to be kept on the same line (which is only1090 /// possible if it fits on the line, only contains a single statement, etc.1091 ///1092 /// If \p NewLine is true, we format the nested block on separate lines, i.e.1093 /// break after the "{", format all lines with correct indentation and the put1094 /// the closing "}" on yet another new line.1095 ///1096 /// This enables us to keep the simple structure of the1097 /// \c UnwrappedLineFormatter, where we only have two options for each token:1098 /// break or don't break.1099 bool formatChildren(LineState &State, bool NewLine, bool DryRun,1100 unsigned &Penalty) {1101 const FormatToken *LBrace = State.NextToken->getPreviousNonComment();1102 bool HasLBrace = LBrace && LBrace->is(tok::l_brace) && LBrace->is(BK_Block);1103 FormatToken &Previous = *State.NextToken->Previous;1104 if (Previous.Children.empty() || (!HasLBrace && !LBrace->MacroParent)) {1105 // The previous token does not open a block. Nothing to do. We don't1106 // assert so that we can simply call this function for all tokens.1107 return true;1108 }1109 1110 if (NewLine || Previous.MacroParent) {1111 const ParenState &P = State.Stack.back();1112 1113 int AdditionalIndent =1114 P.Indent - Previous.Children[0]->Level * Style.IndentWidth;1115 Penalty +=1116 BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,1117 /*FixBadIndentation=*/true);1118 return true;1119 }1120 1121 if (Previous.Children[0]->First->MustBreakBefore)1122 return false;1123 1124 // Cannot merge into one line if this line ends on a comment.1125 if (Previous.is(tok::comment))1126 return false;1127 1128 // Cannot merge multiple statements into a single line.1129 if (Previous.Children.size() > 1)1130 return false;1131 1132 const AnnotatedLine *Child = Previous.Children[0];1133 // We can't put the closing "}" on a line with a trailing comment.1134 if (Child->Last->isTrailingComment())1135 return false;1136 1137 // If the child line exceeds the column limit, we wouldn't want to merge it.1138 // We add +2 for the trailing " }".1139 if (Style.ColumnLimit > 0 &&1140 Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit) {1141 return false;1142 }1143 1144 if (!DryRun) {1145 Whitespaces->replaceWhitespace(1146 *Child->First, /*Newlines=*/0, /*Spaces=*/1,1147 /*StartOfTokenColumn=*/State.Column, /*IsAligned=*/false,1148 State.Line->InPPDirective);1149 }1150 Penalty +=1151 formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);1152 if (!DryRun)1153 markFinalized(Child->First);1154 1155 State.Column += 1 + Child->Last->TotalLength;1156 return true;1157 }1158 1159 ContinuationIndenter *Indenter;1160 1161private:1162 WhitespaceManager *Whitespaces;1163 const FormatStyle &Style;1164 UnwrappedLineFormatter *BlockFormatter;1165};1166 1167/// Formatter that keeps the existing line breaks.1168class NoColumnLimitLineFormatter : public LineFormatter {1169public:1170 NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,1171 WhitespaceManager *Whitespaces,1172 const FormatStyle &Style,1173 UnwrappedLineFormatter *BlockFormatter)1174 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}1175 1176 /// Formats the line, simply keeping all of the input's line breaking1177 /// decisions.1178 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,1179 unsigned FirstStartColumn, bool DryRun) override {1180 assert(!DryRun);1181 LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,1182 &Line, /*DryRun=*/false);1183 while (State.NextToken) {1184 bool Newline =1185 Indenter->mustBreak(State) ||1186 (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);1187 unsigned Penalty = 0;1188 formatChildren(State, Newline, /*DryRun=*/false, Penalty);1189 Indenter->addTokenToState(State, Newline, /*DryRun=*/false);1190 }1191 return 0;1192 }1193};1194 1195/// Formatter that puts all tokens into a single line without breaks.1196class NoLineBreakFormatter : public LineFormatter {1197public:1198 NoLineBreakFormatter(ContinuationIndenter *Indenter,1199 WhitespaceManager *Whitespaces, const FormatStyle &Style,1200 UnwrappedLineFormatter *BlockFormatter)1201 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}1202 1203 /// Puts all tokens into a single line.1204 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,1205 unsigned FirstStartColumn, bool DryRun) override {1206 unsigned Penalty = 0;1207 LineState State =1208 Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);1209 while (State.NextToken) {1210 formatChildren(State, /*NewLine=*/false, DryRun, Penalty);1211 Indenter->addTokenToState(1212 State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);1213 }1214 return Penalty;1215 }1216};1217 1218/// Finds the best way to break lines.1219class OptimizingLineFormatter : public LineFormatter {1220public:1221 OptimizingLineFormatter(ContinuationIndenter *Indenter,1222 WhitespaceManager *Whitespaces,1223 const FormatStyle &Style,1224 UnwrappedLineFormatter *BlockFormatter)1225 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}1226 1227 /// Formats the line by finding the best line breaks with line lengths1228 /// below the column limit.1229 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,1230 unsigned FirstStartColumn, bool DryRun) override {1231 LineState State =1232 Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);1233 1234 // If the ObjC method declaration does not fit on a line, we should format1235 // it with one arg per line.1236 if (State.Line->Type == LT_ObjCMethodDecl)1237 State.Stack.back().BreakBeforeParameter = true;1238 1239 // Find best solution in solution space.1240 return analyzeSolutionSpace(State, DryRun);1241 }1242 1243private:1244 struct CompareLineStatePointers {1245 bool operator()(LineState *obj1, LineState *obj2) const {1246 return *obj1 < *obj2;1247 }1248 };1249 1250 /// A pair of <penalty, count> that is used to prioritize the BFS on.1251 ///1252 /// In case of equal penalties, we want to prefer states that were inserted1253 /// first. During state generation we make sure that we insert states first1254 /// that break the line as late as possible.1255 typedef std::pair<unsigned, unsigned> OrderedPenalty;1256 1257 /// An edge in the solution space from \c Previous->State to \c State,1258 /// inserting a newline dependent on the \c NewLine.1259 struct StateNode {1260 StateNode(const LineState &State, bool NewLine, StateNode *Previous)1261 : State(State), NewLine(NewLine), Previous(Previous) {}1262 LineState State;1263 bool NewLine;1264 StateNode *Previous;1265 };1266 1267 /// An item in the prioritized BFS search queue. The \c StateNode's1268 /// \c State has the given \c OrderedPenalty.1269 typedef std::pair<OrderedPenalty, StateNode *> QueueItem;1270 1271 /// The BFS queue type.1272 typedef std::priority_queue<QueueItem, SmallVector<QueueItem>,1273 std::greater<QueueItem>>1274 QueueType;1275 1276 /// Analyze the entire solution space starting from \p InitialState.1277 ///1278 /// This implements a variant of Dijkstra's algorithm on the graph that spans1279 /// the solution space (\c LineStates are the nodes). The algorithm tries to1280 /// find the shortest path (the one with lowest penalty) from \p InitialState1281 /// to a state where all tokens are placed. Returns the penalty.1282 ///1283 /// If \p DryRun is \c false, directly applies the changes.1284 unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {1285 std::set<LineState *, CompareLineStatePointers> Seen;1286 1287 // Increasing count of \c StateNode items we have created. This is used to1288 // create a deterministic order independent of the container.1289 unsigned Count = 0;1290 QueueType Queue;1291 1292 // Insert start element into queue.1293 StateNode *RootNode =1294 new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);1295 Queue.push(QueueItem(OrderedPenalty(0, Count), RootNode));1296 ++Count;1297 1298 unsigned Penalty = 0;1299 1300 // While not empty, take first element and follow edges.1301 while (!Queue.empty()) {1302 // Quit if we still haven't found a solution by now.1303 if (Count > 25'000'000)1304 return 0;1305 1306 Penalty = Queue.top().first.first;1307 StateNode *Node = Queue.top().second;1308 if (!Node->State.NextToken) {1309 LLVM_DEBUG(llvm::dbgs()1310 << "\n---\nPenalty for line: " << Penalty << "\n");1311 break;1312 }1313 Queue.pop();1314 1315 // Cut off the analysis of certain solutions if the analysis gets too1316 // complex. See description of IgnoreStackForComparison.1317 if (Count > 50'000)1318 Node->State.IgnoreStackForComparison = true;1319 1320 if (!Seen.insert(&Node->State).second) {1321 // State already examined with lower penalty.1322 continue;1323 }1324 1325 FormatDecision LastFormat = Node->State.NextToken->getDecision();1326 if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)1327 addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);1328 if (LastFormat == FD_Unformatted || LastFormat == FD_Break)1329 addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);1330 }1331 1332 if (Queue.empty()) {1333 // We were unable to find a solution, do nothing.1334 // FIXME: Add diagnostic?1335 LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");1336 return 0;1337 }1338 1339 // Reconstruct the solution.1340 if (!DryRun)1341 reconstructPath(InitialState, Queue.top().second);1342 1343 LLVM_DEBUG(llvm::dbgs()1344 << "Total number of analyzed states: " << Count << "\n");1345 LLVM_DEBUG(llvm::dbgs() << "---\n");1346 1347 return Penalty;1348 }1349 1350 /// Add the following state to the analysis queue \c Queue.1351 ///1352 /// Assume the current state is \p PreviousNode and has been reached with a1353 /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.1354 void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,1355 bool NewLine, unsigned *Count, QueueType *Queue) {1356 if (NewLine && !Indenter->canBreak(PreviousNode->State))1357 return;1358 if (!NewLine && Indenter->mustBreak(PreviousNode->State))1359 return;1360 1361 StateNode *Node = new (Allocator.Allocate())1362 StateNode(PreviousNode->State, NewLine, PreviousNode);1363 if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))1364 return;1365 1366 Penalty += Indenter->addTokenToState(Node->State, NewLine, true);1367 1368 Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));1369 ++(*Count);1370 }1371 1372 /// Applies the best formatting by reconstructing the path in the1373 /// solution space that leads to \c Best.1374 void reconstructPath(LineState &State, StateNode *Best) {1375 llvm::SmallVector<StateNode *> Path;1376 // We do not need a break before the initial token.1377 while (Best->Previous) {1378 Path.push_back(Best);1379 Best = Best->Previous;1380 }1381 for (const auto &Node : llvm::reverse(Path)) {1382 unsigned Penalty = 0;1383 formatChildren(State, Node->NewLine, /*DryRun=*/false, Penalty);1384 Penalty += Indenter->addTokenToState(State, Node->NewLine, false);1385 1386 LLVM_DEBUG({1387 printLineState(Node->Previous->State);1388 if (Node->NewLine) {1389 llvm::dbgs() << "Penalty for placing "1390 << Node->Previous->State.NextToken->Tok.getName()1391 << " on a new line: " << Penalty << "\n";1392 }1393 });1394 }1395 }1396 1397 llvm::SpecificBumpPtrAllocator<StateNode> Allocator;1398};1399 1400} // anonymous namespace1401 1402unsigned UnwrappedLineFormatter::format(1403 const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,1404 int AdditionalIndent, bool FixBadIndentation, unsigned FirstStartColumn,1405 unsigned NextStartColumn, unsigned LastStartColumn) {1406 LineJoiner Joiner(Style, Keywords, Lines);1407 1408 // Try to look up already computed penalty in DryRun-mode.1409 std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(1410 &Lines, AdditionalIndent);1411 auto CacheIt = PenaltyCache.find(CacheKey);1412 if (DryRun && CacheIt != PenaltyCache.end())1413 return CacheIt->second;1414 1415 assert(!Lines.empty());1416 unsigned Penalty = 0;1417 LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,1418 AdditionalIndent);1419 const AnnotatedLine *PrevPrevLine = nullptr;1420 const AnnotatedLine *PreviousLine = nullptr;1421 const AnnotatedLine *NextLine = nullptr;1422 1423 // The minimum level of consecutive lines that have been formatted.1424 unsigned RangeMinLevel = UINT_MAX;1425 1426 bool FirstLine = true;1427 for (const AnnotatedLine *Line =1428 Joiner.getNextMergedLine(DryRun, IndentTracker);1429 Line; PrevPrevLine = PreviousLine, PreviousLine = Line, Line = NextLine,1430 FirstLine = false) {1431 assert(Line->First);1432 const AnnotatedLine &TheLine = *Line;1433 unsigned Indent = IndentTracker.getIndent();1434 1435 // We continue formatting unchanged lines to adjust their indent, e.g. if a1436 // scope was added. However, we need to carefully stop doing this when we1437 // exit the scope of affected lines to prevent indenting the entire1438 // remaining file if it currently missing a closing brace.1439 bool PreviousRBrace =1440 PreviousLine && PreviousLine->startsWith(tok::r_brace);1441 bool ContinueFormatting =1442 TheLine.Level > RangeMinLevel ||1443 (TheLine.Level == RangeMinLevel && !PreviousRBrace &&1444 !TheLine.startsWith(TT_NamespaceRBrace));1445 1446 bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&1447 Indent != TheLine.First->OriginalColumn;1448 bool ShouldFormat = TheLine.Affected || FixIndentation;1449 // We cannot format this line; if the reason is that the line had a1450 // parsing error, remember that.1451 if (ShouldFormat && TheLine.Type == LT_Invalid && Status) {1452 Status->FormatComplete = false;1453 Status->Line =1454 SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());1455 }1456 1457 if (ShouldFormat && TheLine.Type != LT_Invalid) {1458 if (!DryRun) {1459 bool LastLine = TheLine.First->is(tok::eof);1460 formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines, Indent,1461 LastLine ? LastStartColumn : NextStartColumn + Indent);1462 }1463 1464 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);1465 unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine);1466 bool FitsIntoOneLine =1467 !TheLine.ContainsMacroCall &&1468 (TheLine.Last->TotalLength + Indent <= ColumnLimit ||1469 (TheLine.Type == LT_ImportStatement &&1470 (!Style.isJavaScript() || !Style.JavaScriptWrapImports)) ||1471 (Style.isCSharp() &&1472 TheLine.InPPDirective)); // don't split #regions in C#1473 if (Style.ColumnLimit == 0) {1474 NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)1475 .formatLine(TheLine, NextStartColumn + Indent,1476 FirstLine ? FirstStartColumn : 0, DryRun);1477 } else if (FitsIntoOneLine) {1478 Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)1479 .formatLine(TheLine, NextStartColumn + Indent,1480 FirstLine ? FirstStartColumn : 0, DryRun);1481 } else {1482 Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)1483 .formatLine(TheLine, NextStartColumn + Indent,1484 FirstLine ? FirstStartColumn : 0, DryRun);1485 }1486 RangeMinLevel = std::min(RangeMinLevel, TheLine.Level);1487 } else {1488 // If no token in the current line is affected, we still need to format1489 // affected children.1490 if (TheLine.ChildrenAffected) {1491 for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)1492 if (!Tok->Children.empty())1493 format(Tok->Children, DryRun);1494 }1495 1496 // Adapt following lines on the current indent level to the same level1497 // unless the current \c AnnotatedLine is not at the beginning of a line.1498 bool StartsNewLine =1499 TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;1500 if (StartsNewLine)1501 IndentTracker.adjustToUnmodifiedLine(TheLine);1502 if (!DryRun) {1503 bool ReformatLeadingWhitespace =1504 StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||1505 TheLine.LeadingEmptyLinesAffected);1506 // Format the first token.1507 if (ReformatLeadingWhitespace) {1508 formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines,1509 TheLine.First->OriginalColumn,1510 TheLine.First->OriginalColumn);1511 } else {1512 Whitespaces->addUntouchableToken(*TheLine.First,1513 TheLine.InPPDirective);1514 }1515 1516 // Notify the WhitespaceManager about the unchanged whitespace.1517 for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)1518 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);1519 }1520 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);1521 RangeMinLevel = UINT_MAX;1522 }1523 if (!DryRun)1524 markFinalized(TheLine.First);1525 }1526 PenaltyCache[CacheKey] = Penalty;1527 return Penalty;1528}1529 1530static auto computeNewlines(const AnnotatedLine &Line,1531 const AnnotatedLine *PreviousLine,1532 const AnnotatedLine *PrevPrevLine,1533 const SmallVectorImpl<AnnotatedLine *> &Lines,1534 const FormatStyle &Style) {1535 const auto &RootToken = *Line.First;1536 auto Newlines =1537 std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);1538 // Remove empty lines before "}" where applicable.1539 if (RootToken.is(tok::r_brace) &&1540 (!RootToken.Next ||1541 (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) &&1542 // Do not remove empty lines before namespace closing "}".1543 !getNamespaceToken(&Line, Lines)) {1544 Newlines = std::min(Newlines, 1u);1545 }1546 // Remove empty lines at the start of nested blocks (lambdas/arrow functions)1547 if (!PreviousLine && Line.Level > 0)1548 Newlines = std::min(Newlines, 1u);1549 if (Newlines == 0 && !RootToken.IsFirst)1550 Newlines = 1;1551 if (RootToken.IsFirst &&1552 (!Style.KeepEmptyLines.AtStartOfFile || !RootToken.HasUnescapedNewline)) {1553 Newlines = 0;1554 }1555 1556 // Remove empty lines after "{".1557 if (!Style.KeepEmptyLines.AtStartOfBlock && PreviousLine &&1558 PreviousLine->Last->is(tok::l_brace) &&1559 !PreviousLine->startsWithNamespace() &&1560 !(PrevPrevLine && PrevPrevLine->startsWithNamespace() &&1561 PreviousLine->startsWith(tok::l_brace)) &&1562 !startsExternCBlock(*PreviousLine)) {1563 Newlines = 1;1564 }1565 1566 if (Style.WrapNamespaceBodyWithEmptyLines != FormatStyle::WNBWELS_Leave) {1567 // Modify empty lines after TT_NamespaceLBrace.1568 if (PreviousLine && PreviousLine->endsWith(TT_NamespaceLBrace)) {1569 if (Style.WrapNamespaceBodyWithEmptyLines == FormatStyle::WNBWELS_Never)1570 Newlines = 1;1571 else if (!Line.startsWithNamespace())1572 Newlines = std::max(Newlines, 2u);1573 }1574 // Modify empty lines before TT_NamespaceRBrace.1575 if (Line.startsWith(TT_NamespaceRBrace)) {1576 if (Style.WrapNamespaceBodyWithEmptyLines == FormatStyle::WNBWELS_Never)1577 Newlines = 1;1578 else if (!PreviousLine->startsWith(TT_NamespaceRBrace))1579 Newlines = std::max(Newlines, 2u);1580 }1581 }1582 1583 // Insert or remove empty line before access specifiers.1584 if (PreviousLine && RootToken.isAccessSpecifier()) {1585 switch (Style.EmptyLineBeforeAccessModifier) {1586 case FormatStyle::ELBAMS_Never:1587 if (Newlines > 1)1588 Newlines = 1;1589 break;1590 case FormatStyle::ELBAMS_Leave:1591 Newlines = std::max(RootToken.NewlinesBefore, 1u);1592 break;1593 case FormatStyle::ELBAMS_LogicalBlock:1594 if (PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) && Newlines <= 1)1595 Newlines = 2;1596 if (PreviousLine->First->isAccessSpecifier())1597 Newlines = 1; // Previous is an access modifier remove all new lines.1598 break;1599 case FormatStyle::ELBAMS_Always: {1600 const FormatToken *previousToken;1601 if (PreviousLine->Last->is(tok::comment))1602 previousToken = PreviousLine->Last->getPreviousNonComment();1603 else1604 previousToken = PreviousLine->Last;1605 if ((!previousToken || previousToken->isNot(tok::l_brace)) &&1606 Newlines <= 1) {1607 Newlines = 2;1608 }1609 } break;1610 }1611 }1612 1613 // Insert or remove empty line after access specifiers.1614 if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&1615 (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline)) {1616 // EmptyLineBeforeAccessModifier is handling the case when two access1617 // modifiers follow each other.1618 if (!RootToken.isAccessSpecifier()) {1619 switch (Style.EmptyLineAfterAccessModifier) {1620 case FormatStyle::ELAAMS_Never:1621 Newlines = 1;1622 break;1623 case FormatStyle::ELAAMS_Leave:1624 Newlines = std::max(Newlines, 1u);1625 break;1626 case FormatStyle::ELAAMS_Always:1627 if (RootToken.is(tok::r_brace)) // Do not add at end of class.1628 Newlines = 1u;1629 else1630 Newlines = std::max(Newlines, 2u);1631 break;1632 }1633 }1634 }1635 1636 return Newlines;1637}1638 1639void UnwrappedLineFormatter::formatFirstToken(1640 const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,1641 const AnnotatedLine *PrevPrevLine,1642 const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,1643 unsigned NewlineIndent) {1644 FormatToken &RootToken = *Line.First;1645 if (RootToken.is(tok::eof)) {1646 unsigned Newlines = std::min(1647 RootToken.NewlinesBefore,1648 Style.KeepEmptyLines.AtEndOfFile ? Style.MaxEmptyLinesToKeep + 1 : 1);1649 unsigned TokenIndent = Newlines ? NewlineIndent : 0;1650 Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,1651 TokenIndent);1652 return;1653 }1654 1655 if (RootToken.Newlines < 0) {1656 RootToken.Newlines =1657 computeNewlines(Line, PreviousLine, PrevPrevLine, Lines, Style);1658 assert(RootToken.Newlines >= 0);1659 }1660 1661 if (RootToken.Newlines > 0)1662 Indent = NewlineIndent;1663 1664 // Preprocessor directives get indented before the hash only if specified. In1665 // Javascript import statements are indented like normal statements.1666 if (!Style.isJavaScript() &&1667 Style.IndentPPDirectives < FormatStyle::PPDIS_BeforeHash &&1668 (Line.Type == LT_PreprocessorDirective ||1669 Line.Type == LT_ImportStatement)) {1670 Indent = 0;1671 }1672 1673 Whitespaces->replaceWhitespace(RootToken, RootToken.Newlines, Indent, Indent,1674 /*IsAligned=*/false,1675 Line.InPPDirective &&1676 !RootToken.HasUnescapedNewline);1677}1678 1679unsigned1680UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,1681 const AnnotatedLine *NextLine) const {1682 // In preprocessor directives reserve two chars for trailing " \" if the1683 // next line continues the preprocessor directive.1684 bool ContinuesPPDirective =1685 InPPDirective &&1686 // If there is no next line, this is likely a child line and the parent1687 // continues the preprocessor directive.1688 (!NextLine ||1689 (NextLine->InPPDirective &&1690 // If there is an unescaped newline between this line and the next, the1691 // next line starts a new preprocessor directive.1692 !NextLine->First->HasUnescapedNewline));1693 return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);1694}1695 1696} // namespace format1697} // namespace clang1698