UnwrappedLineFormatter.cpp revision 344779
1277325Sdim//===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===// 2277325Sdim// 3277325Sdim// The LLVM Compiler Infrastructure 4277325Sdim// 5277325Sdim// This file is distributed under the University of Illinois Open Source 6277325Sdim// License. See LICENSE.TXT for details. 7277325Sdim// 8277325Sdim//===----------------------------------------------------------------------===// 9277325Sdim 10341825Sdim#include "NamespaceEndCommentsFixer.h" 11277325Sdim#include "UnwrappedLineFormatter.h" 12277325Sdim#include "WhitespaceManager.h" 13277325Sdim#include "llvm/Support/Debug.h" 14314564Sdim#include <queue> 15277325Sdim 16277325Sdim#define DEBUG_TYPE "format-formatter" 17277325Sdim 18277325Sdimnamespace clang { 19277325Sdimnamespace format { 20277325Sdim 21277325Sdimnamespace { 22277325Sdim 23277325Sdimbool startsExternCBlock(const AnnotatedLine &Line) { 24277325Sdim const FormatToken *Next = Line.First->getNextNonComment(); 25277325Sdim const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr; 26288943Sdim return Line.startsWith(tok::kw_extern) && Next && Next->isStringLiteral() && 27277325Sdim NextNext && NextNext->is(tok::l_brace); 28277325Sdim} 29277325Sdim 30341825Sdim/// Tracks the indent level of \c AnnotatedLines across levels. 31288943Sdim/// 32288943Sdim/// \c nextLine must be called for each \c AnnotatedLine, after which \c 33288943Sdim/// getIndent() will return the indent for the last line \c nextLine was called 34288943Sdim/// with. 35288943Sdim/// If the line is not formatted (and thus the indent does not change), calling 36288943Sdim/// \c adjustToUnmodifiedLine after the call to \c nextLine will cause 37288943Sdim/// subsequent lines on the same level to be indented at the same level as the 38288943Sdim/// given line. 39288943Sdimclass LevelIndentTracker { 40288943Sdimpublic: 41288943Sdim LevelIndentTracker(const FormatStyle &Style, 42288943Sdim const AdditionalKeywords &Keywords, unsigned StartLevel, 43288943Sdim int AdditionalIndent) 44288943Sdim : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) { 45288943Sdim for (unsigned i = 0; i != StartLevel; ++i) 46288943Sdim IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent); 47288943Sdim } 48288943Sdim 49341825Sdim /// Returns the indent for the current line. 50288943Sdim unsigned getIndent() const { return Indent; } 51288943Sdim 52341825Sdim /// Update the indent state given that \p Line is going to be formatted 53288943Sdim /// next. 54288943Sdim void nextLine(const AnnotatedLine &Line) { 55288943Sdim Offset = getIndentOffset(*Line.First); 56288943Sdim // Update the indent level cache size so that we can rely on it 57288943Sdim // having the right size in adjustToUnmodifiedline. 58288943Sdim while (IndentForLevel.size() <= Line.Level) 59288943Sdim IndentForLevel.push_back(-1); 60288943Sdim if (Line.InPPDirective) { 61288943Sdim Indent = Line.Level * Style.IndentWidth + AdditionalIndent; 62288943Sdim } else { 63288943Sdim IndentForLevel.resize(Line.Level + 1); 64288943Sdim Indent = getIndent(IndentForLevel, Line.Level); 65288943Sdim } 66288943Sdim if (static_cast<int>(Indent) + Offset >= 0) 67288943Sdim Indent += Offset; 68288943Sdim } 69288943Sdim 70341825Sdim /// Update the indent state given that \p Line indent should be 71321369Sdim /// skipped. 72321369Sdim void skipLine(const AnnotatedLine &Line) { 73321369Sdim while (IndentForLevel.size() <= Line.Level) 74321369Sdim IndentForLevel.push_back(Indent); 75321369Sdim } 76321369Sdim 77341825Sdim /// Update the level indent to adapt to the given \p Line. 78288943Sdim /// 79288943Sdim /// When a line is not formatted, we move the subsequent lines on the same 80288943Sdim /// level to the same indent. 81288943Sdim /// Note that \c nextLine must have been called before this method. 82288943Sdim void adjustToUnmodifiedLine(const AnnotatedLine &Line) { 83288943Sdim unsigned LevelIndent = Line.First->OriginalColumn; 84288943Sdim if (static_cast<int>(LevelIndent) - Offset >= 0) 85288943Sdim LevelIndent -= Offset; 86288943Sdim if ((!Line.First->is(tok::comment) || IndentForLevel[Line.Level] == -1) && 87288943Sdim !Line.InPPDirective) 88288943Sdim IndentForLevel[Line.Level] = LevelIndent; 89288943Sdim } 90288943Sdim 91288943Sdimprivate: 92341825Sdim /// Get the offset of the line relatively to the level. 93288943Sdim /// 94288943Sdim /// For example, 'public:' labels in classes are offset by 1 or 2 95288943Sdim /// characters to the left from their level. 96288943Sdim int getIndentOffset(const FormatToken &RootToken) { 97288943Sdim if (Style.Language == FormatStyle::LK_Java || 98288943Sdim Style.Language == FormatStyle::LK_JavaScript) 99288943Sdim return 0; 100288943Sdim if (RootToken.isAccessSpecifier(false) || 101288943Sdim RootToken.isObjCAccessSpecifier() || 102296417Sdim (RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals) && 103296417Sdim RootToken.Next && RootToken.Next->is(tok::colon))) 104288943Sdim return Style.AccessModifierOffset; 105288943Sdim return 0; 106288943Sdim } 107288943Sdim 108341825Sdim /// Get the indent of \p Level from \p IndentForLevel. 109288943Sdim /// 110288943Sdim /// \p IndentForLevel must contain the indent for the level \c l 111288943Sdim /// at \p IndentForLevel[l], or a value < 0 if the indent for 112288943Sdim /// that level is unknown. 113288943Sdim unsigned getIndent(ArrayRef<int> IndentForLevel, unsigned Level) { 114288943Sdim if (IndentForLevel[Level] != -1) 115288943Sdim return IndentForLevel[Level]; 116288943Sdim if (Level == 0) 117288943Sdim return 0; 118288943Sdim return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth; 119288943Sdim } 120288943Sdim 121288943Sdim const FormatStyle &Style; 122288943Sdim const AdditionalKeywords &Keywords; 123288943Sdim const unsigned AdditionalIndent; 124288943Sdim 125341825Sdim /// The indent in characters for each level. 126288943Sdim std::vector<int> IndentForLevel; 127288943Sdim 128341825Sdim /// Offset of the current line relative to the indent level. 129288943Sdim /// 130288943Sdim /// For example, the 'public' keywords is often indented with a negative 131288943Sdim /// offset. 132288943Sdim int Offset = 0; 133288943Sdim 134341825Sdim /// The current line's indent. 135288943Sdim unsigned Indent = 0; 136288943Sdim}; 137288943Sdim 138321369Sdimbool isNamespaceDeclaration(const AnnotatedLine *Line) { 139321369Sdim const FormatToken *NamespaceTok = Line->First; 140321369Sdim return NamespaceTok && NamespaceTok->getNamespaceToken(); 141321369Sdim} 142321369Sdim 143321369Sdimbool isEndOfNamespace(const AnnotatedLine *Line, 144321369Sdim const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) { 145321369Sdim if (!Line->startsWith(tok::r_brace)) 146321369Sdim return false; 147321369Sdim size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex; 148321369Sdim if (StartLineIndex == UnwrappedLine::kInvalidIndex) 149321369Sdim return false; 150321369Sdim assert(StartLineIndex < AnnotatedLines.size()); 151321369Sdim return isNamespaceDeclaration(AnnotatedLines[StartLineIndex]); 152321369Sdim} 153321369Sdim 154277325Sdimclass LineJoiner { 155277325Sdimpublic: 156288943Sdim LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords, 157288943Sdim const SmallVectorImpl<AnnotatedLine *> &Lines) 158321369Sdim : Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()), 159321369Sdim AnnotatedLines(Lines) {} 160277325Sdim 161341825Sdim /// Returns the next line, merging multiple lines into one if possible. 162288943Sdim const AnnotatedLine *getNextMergedLine(bool DryRun, 163288943Sdim LevelIndentTracker &IndentTracker) { 164288943Sdim if (Next == End) 165288943Sdim return nullptr; 166288943Sdim const AnnotatedLine *Current = *Next; 167288943Sdim IndentTracker.nextLine(*Current); 168327952Sdim unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next, End); 169288943Sdim if (MergedLines > 0 && Style.ColumnLimit == 0) 170288943Sdim // Disallow line merging if there is a break at the start of one of the 171288943Sdim // input lines. 172288943Sdim for (unsigned i = 0; i < MergedLines; ++i) 173288943Sdim if (Next[i + 1]->First->NewlinesBefore > 0) 174288943Sdim MergedLines = 0; 175288943Sdim if (!DryRun) 176288943Sdim for (unsigned i = 0; i < MergedLines; ++i) 177314564Sdim join(*Next[0], *Next[i + 1]); 178288943Sdim Next = Next + MergedLines + 1; 179288943Sdim return Current; 180288943Sdim } 181288943Sdim 182288943Sdimprivate: 183341825Sdim /// Calculates how many lines can be merged into 1 starting at \p I. 184277325Sdim unsigned 185321369Sdim tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker, 186277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator I, 187277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E) { 188321369Sdim const unsigned Indent = IndentTracker.getIndent(); 189321369Sdim 190288943Sdim // Can't join the last line with anything. 191288943Sdim if (I + 1 == E) 192288943Sdim return 0; 193277325Sdim // We can never merge stuff if there are trailing line comments. 194277325Sdim const AnnotatedLine *TheLine = *I; 195277325Sdim if (TheLine->Last->is(TT_LineComment)) 196277325Sdim return 0; 197288943Sdim if (I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore) 198288943Sdim return 0; 199288943Sdim if (TheLine->InPPDirective && 200288943Sdim (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)) 201288943Sdim return 0; 202277325Sdim 203277325Sdim if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit) 204277325Sdim return 0; 205277325Sdim 206277325Sdim unsigned Limit = 207277325Sdim Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent; 208277325Sdim // If we already exceed the column limit, we set 'Limit' to 0. The different 209277325Sdim // tryMerge..() functions can then decide whether to still do merging. 210277325Sdim Limit = TheLine->Last->TotalLength > Limit 211277325Sdim ? 0 212277325Sdim : Limit - TheLine->Last->TotalLength; 213277325Sdim 214321369Sdim if (TheLine->Last->is(TT_FunctionLBrace) && 215321369Sdim TheLine->First == TheLine->Last && 216321369Sdim !Style.BraceWrapping.SplitEmptyFunction && 217321369Sdim I[1]->First->is(tok::r_brace)) 218321369Sdim return tryMergeSimpleBlock(I, E, Limit); 219321369Sdim 220321369Sdim // Handle empty record blocks where the brace has already been wrapped 221321369Sdim if (TheLine->Last->is(tok::l_brace) && TheLine->First == TheLine->Last && 222321369Sdim I != AnnotatedLines.begin()) { 223321369Sdim bool EmptyBlock = I[1]->First->is(tok::r_brace); 224321369Sdim 225321369Sdim const FormatToken *Tok = I[-1]->First; 226321369Sdim if (Tok && Tok->is(tok::comment)) 227321369Sdim Tok = Tok->getNextNonComment(); 228321369Sdim 229321369Sdim if (Tok && Tok->getNamespaceToken()) 230321369Sdim return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock 231327952Sdim ? tryMergeSimpleBlock(I, E, Limit) 232327952Sdim : 0; 233321369Sdim 234321369Sdim if (Tok && Tok->is(tok::kw_typedef)) 235321369Sdim Tok = Tok->getNextNonComment(); 236321369Sdim if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union, 237327952Sdim tok::kw_extern, Keywords.kw_interface)) 238321369Sdim return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock 239327952Sdim ? tryMergeSimpleBlock(I, E, Limit) 240327952Sdim : 0; 241321369Sdim } 242321369Sdim 243277325Sdim // FIXME: TheLine->Level != 0 might or might not be the right check to do. 244277325Sdim // If necessary, change to something smarter. 245277325Sdim bool MergeShortFunctions = 246277325Sdim Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All || 247288943Sdim (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty && 248277325Sdim I[1]->First->is(tok::r_brace)) || 249321369Sdim (Style.AllowShortFunctionsOnASingleLine & FormatStyle::SFS_InlineOnly && 250277325Sdim TheLine->Level != 0); 251277325Sdim 252321369Sdim if (Style.CompactNamespaces) { 253321369Sdim if (isNamespaceDeclaration(TheLine)) { 254321369Sdim int i = 0; 255341825Sdim unsigned closingLine = TheLine->MatchingClosingBlockLineIndex - 1; 256321369Sdim for (; I + 1 + i != E && isNamespaceDeclaration(I[i + 1]) && 257341825Sdim closingLine == I[i + 1]->MatchingClosingBlockLineIndex && 258321369Sdim I[i + 1]->Last->TotalLength < Limit; 259321369Sdim i++, closingLine--) { 260321369Sdim // No extra indent for compacted namespaces 261321369Sdim IndentTracker.skipLine(*I[i + 1]); 262321369Sdim 263321369Sdim Limit -= I[i + 1]->Last->TotalLength; 264321369Sdim } 265321369Sdim return i; 266321369Sdim } 267321369Sdim 268321369Sdim if (isEndOfNamespace(TheLine, AnnotatedLines)) { 269321369Sdim int i = 0; 270321369Sdim unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1; 271321369Sdim for (; I + 1 + i != E && isEndOfNamespace(I[i + 1], AnnotatedLines) && 272321369Sdim openingLine == I[i + 1]->MatchingOpeningBlockLineIndex; 273321369Sdim i++, openingLine--) { 274321369Sdim // No space between consecutive braces 275321369Sdim I[i + 1]->First->SpacesRequiredBefore = !I[i]->Last->is(tok::r_brace); 276321369Sdim 277321369Sdim // Indent like the outer-most namespace 278321369Sdim IndentTracker.nextLine(*I[i + 1]); 279321369Sdim } 280321369Sdim return i; 281321369Sdim } 282321369Sdim } 283321369Sdim 284327952Sdim // Try to merge a function block with left brace unwrapped 285277325Sdim if (TheLine->Last->is(TT_FunctionLBrace) && 286277325Sdim TheLine->First != TheLine->Last) { 287277325Sdim return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0; 288277325Sdim } 289327952Sdim // Try to merge a control statement block with left brace unwrapped 290327952Sdim if (TheLine->Last->is(tok::l_brace) && TheLine->First != TheLine->Last && 291327952Sdim TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) { 292327952Sdim return Style.AllowShortBlocksOnASingleLine 293327952Sdim ? tryMergeSimpleBlock(I, E, Limit) 294327952Sdim : 0; 295327952Sdim } 296327952Sdim // Try to merge a control statement block with left brace wrapped 297327952Sdim if (I[1]->First->is(tok::l_brace) && 298327952Sdim TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) { 299327952Sdim return Style.BraceWrapping.AfterControlStatement 300327952Sdim ? tryMergeSimpleBlock(I, E, Limit) 301327952Sdim : 0; 302327952Sdim } 303327952Sdim // Try to merge either empty or one-line block if is precedeed by control 304327952Sdim // statement token 305327952Sdim if (TheLine->First->is(tok::l_brace) && TheLine->First == TheLine->Last && 306327952Sdim I != AnnotatedLines.begin() && 307327952Sdim I[-1]->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) { 308341825Sdim unsigned MergedLines = 0; 309341825Sdim if (Style.AllowShortBlocksOnASingleLine) { 310341825Sdim MergedLines = tryMergeSimpleBlock(I - 1, E, Limit); 311341825Sdim // If we managed to merge the block, discard the first merged line 312341825Sdim // since we are merging starting from I. 313341825Sdim if (MergedLines > 0) 314341825Sdim --MergedLines; 315341825Sdim } 316341825Sdim return MergedLines; 317327952Sdim } 318341825Sdim // Don't merge block with left brace wrapped after ObjC special blocks 319341825Sdim if (TheLine->First->is(tok::l_brace) && I != AnnotatedLines.begin() && 320341825Sdim I[-1]->First->is(tok::at) && I[-1]->First->Next) { 321341825Sdim tok::ObjCKeywordKind kwId = I[-1]->First->Next->Tok.getObjCKeywordID(); 322341825Sdim if (kwId == clang::tok::objc_autoreleasepool || 323341825Sdim kwId == clang::tok::objc_synchronized) 324341825Sdim return 0; 325341825Sdim } 326344779Sdim // Don't merge block with left brace wrapped after case labels 327344779Sdim if (TheLine->First->is(tok::l_brace) && I != AnnotatedLines.begin() && 328344779Sdim I[-1]->First->isOneOf(tok::kw_case, tok::kw_default)) 329344779Sdim return 0; 330327952Sdim // Try to merge a block with left brace wrapped that wasn't yet covered 331277325Sdim if (TheLine->Last->is(tok::l_brace)) { 332327952Sdim return !Style.BraceWrapping.AfterFunction || 333327952Sdim (I[1]->First->is(tok::r_brace) && 334327952Sdim !Style.BraceWrapping.SplitEmptyRecord) 335277325Sdim ? tryMergeSimpleBlock(I, E, Limit) 336277325Sdim : 0; 337277325Sdim } 338327952Sdim // Try to merge a function block with left brace wrapped 339277325Sdim if (I[1]->First->is(TT_FunctionLBrace) && 340296417Sdim Style.BraceWrapping.AfterFunction) { 341277325Sdim if (I[1]->Last->is(TT_LineComment)) 342277325Sdim return 0; 343277325Sdim 344277325Sdim // Check for Limit <= 2 to account for the " {". 345277325Sdim if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine))) 346277325Sdim return 0; 347277325Sdim Limit -= 2; 348277325Sdim 349277325Sdim unsigned MergedLines = 0; 350321369Sdim if (MergeShortFunctions || 351321369Sdim (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty && 352321369Sdim I[1]->First == I[1]->Last && I + 2 != E && 353321369Sdim I[2]->First->is(tok::r_brace))) { 354277325Sdim MergedLines = tryMergeSimpleBlock(I + 1, E, Limit); 355277325Sdim // If we managed to merge the block, count the function header, which is 356277325Sdim // on a separate line. 357277325Sdim if (MergedLines > 0) 358277325Sdim ++MergedLines; 359277325Sdim } 360277325Sdim return MergedLines; 361277325Sdim } 362277325Sdim if (TheLine->First->is(tok::kw_if)) { 363277325Sdim return Style.AllowShortIfStatementsOnASingleLine 364277325Sdim ? tryMergeSimpleControlStatement(I, E, Limit) 365277325Sdim : 0; 366277325Sdim } 367277325Sdim if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) { 368277325Sdim return Style.AllowShortLoopsOnASingleLine 369277325Sdim ? tryMergeSimpleControlStatement(I, E, Limit) 370277325Sdim : 0; 371277325Sdim } 372277325Sdim if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) { 373277325Sdim return Style.AllowShortCaseLabelsOnASingleLine 374277325Sdim ? tryMergeShortCaseLabels(I, E, Limit) 375277325Sdim : 0; 376277325Sdim } 377277325Sdim if (TheLine->InPPDirective && 378277325Sdim (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) { 379277325Sdim return tryMergeSimplePPDirective(I, E, Limit); 380277325Sdim } 381277325Sdim return 0; 382277325Sdim } 383277325Sdim 384277325Sdim unsigned 385277325Sdim tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 386277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 387277325Sdim unsigned Limit) { 388277325Sdim if (Limit == 0) 389277325Sdim return 0; 390277325Sdim if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline) 391277325Sdim return 0; 392277325Sdim if (1 + I[1]->Last->TotalLength > Limit) 393277325Sdim return 0; 394277325Sdim return 1; 395277325Sdim } 396277325Sdim 397277325Sdim unsigned tryMergeSimpleControlStatement( 398277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator I, 399277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) { 400277325Sdim if (Limit == 0) 401277325Sdim return 0; 402296417Sdim if (Style.BraceWrapping.AfterControlStatement && 403277325Sdim (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine)) 404277325Sdim return 0; 405277325Sdim if (I[1]->InPPDirective != (*I)->InPPDirective || 406277325Sdim (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) 407277325Sdim return 0; 408277325Sdim Limit = limitConsideringMacros(I + 1, E, Limit); 409277325Sdim AnnotatedLine &Line = **I; 410277325Sdim if (Line.Last->isNot(tok::r_paren)) 411277325Sdim return 0; 412277325Sdim if (1 + I[1]->Last->TotalLength > Limit) 413277325Sdim return 0; 414288943Sdim if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while, 415288943Sdim TT_LineComment)) 416277325Sdim return 0; 417277325Sdim // Only inline simple if's (no nested if or else). 418288943Sdim if (I + 2 != E && Line.startsWith(tok::kw_if) && 419277325Sdim I[2]->First->is(tok::kw_else)) 420277325Sdim return 0; 421277325Sdim return 1; 422277325Sdim } 423277325Sdim 424288943Sdim unsigned 425288943Sdim tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 426288943Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 427288943Sdim unsigned Limit) { 428277325Sdim if (Limit == 0 || I + 1 == E || 429277325Sdim I[1]->First->isOneOf(tok::kw_case, tok::kw_default)) 430277325Sdim return 0; 431344779Sdim if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace)) 432344779Sdim return 0; 433277325Sdim unsigned NumStmts = 0; 434277325Sdim unsigned Length = 0; 435327952Sdim bool EndsWithComment = false; 436277325Sdim bool InPPDirective = I[0]->InPPDirective; 437327952Sdim const unsigned Level = I[0]->Level; 438277325Sdim for (; NumStmts < 3; ++NumStmts) { 439277325Sdim if (I + 1 + NumStmts == E) 440277325Sdim break; 441277325Sdim const AnnotatedLine *Line = I[1 + NumStmts]; 442277325Sdim if (Line->InPPDirective != InPPDirective) 443277325Sdim break; 444277325Sdim if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace)) 445277325Sdim break; 446277325Sdim if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch, 447327952Sdim tok::kw_while) || 448327952Sdim EndsWithComment) 449277325Sdim return 0; 450327952Sdim if (Line->First->is(tok::comment)) { 451327952Sdim if (Level != Line->Level) 452327952Sdim return 0; 453327952Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts; 454327952Sdim for (; J != E; ++J) { 455327952Sdim Line = *J; 456327952Sdim if (Line->InPPDirective != InPPDirective) 457327952Sdim break; 458327952Sdim if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace)) 459327952Sdim break; 460327952Sdim if (Line->First->isNot(tok::comment) || Level != Line->Level) 461327952Sdim return 0; 462327952Sdim } 463327952Sdim break; 464327952Sdim } 465327952Sdim if (Line->Last->is(tok::comment)) 466327952Sdim EndsWithComment = true; 467277325Sdim Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space. 468277325Sdim } 469277325Sdim if (NumStmts == 0 || NumStmts == 3 || Length > Limit) 470277325Sdim return 0; 471277325Sdim return NumStmts; 472277325Sdim } 473277325Sdim 474277325Sdim unsigned 475277325Sdim tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 476277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 477277325Sdim unsigned Limit) { 478277325Sdim AnnotatedLine &Line = **I; 479277325Sdim 480277325Sdim // Don't merge ObjC @ keywords and methods. 481288943Sdim // FIXME: If an option to allow short exception handling clauses on a single 482288943Sdim // line is added, change this to not return for @try and friends. 483277325Sdim if (Style.Language != FormatStyle::LK_Java && 484277325Sdim Line.First->isOneOf(tok::at, tok::minus, tok::plus)) 485277325Sdim return 0; 486277325Sdim 487277325Sdim // Check that the current line allows merging. This depends on whether we 488277325Sdim // are in a control flow statements as well as several style flags. 489288943Sdim if (Line.First->isOneOf(tok::kw_else, tok::kw_case) || 490288943Sdim (Line.First->Next && Line.First->Next->is(tok::kw_else))) 491277325Sdim return 0; 492344779Sdim // default: in switch statement 493344779Sdim if (Line.First->is(tok::kw_default)) { 494344779Sdim const FormatToken *Tok = Line.First->getNextNonComment(); 495344779Sdim if (Tok && Tok->is(tok::colon)) 496344779Sdim return 0; 497344779Sdim } 498277325Sdim if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try, 499288943Sdim tok::kw___try, tok::kw_catch, tok::kw___finally, 500288943Sdim tok::kw_for, tok::r_brace, Keywords.kw___except)) { 501277325Sdim if (!Style.AllowShortBlocksOnASingleLine) 502277325Sdim return 0; 503327952Sdim // Don't merge when we can't except the case when 504327952Sdim // the control statement block is empty 505277325Sdim if (!Style.AllowShortIfStatementsOnASingleLine && 506327952Sdim Line.startsWith(tok::kw_if) && 507327952Sdim !Style.BraceWrapping.AfterControlStatement && 508327952Sdim !I[1]->First->is(tok::r_brace)) 509277325Sdim return 0; 510327952Sdim if (!Style.AllowShortIfStatementsOnASingleLine && 511327952Sdim Line.startsWith(tok::kw_if) && 512327952Sdim Style.BraceWrapping.AfterControlStatement && I + 2 != E && 513327952Sdim !I[2]->First->is(tok::r_brace)) 514327952Sdim return 0; 515277325Sdim if (!Style.AllowShortLoopsOnASingleLine && 516327952Sdim Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) && 517327952Sdim !Style.BraceWrapping.AfterControlStatement && 518327952Sdim !I[1]->First->is(tok::r_brace)) 519277325Sdim return 0; 520327952Sdim if (!Style.AllowShortLoopsOnASingleLine && 521327952Sdim Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) && 522327952Sdim Style.BraceWrapping.AfterControlStatement && I + 2 != E && 523327952Sdim !I[2]->First->is(tok::r_brace)) 524327952Sdim return 0; 525277325Sdim // FIXME: Consider an option to allow short exception handling clauses on 526277325Sdim // a single line. 527288943Sdim // FIXME: This isn't covered by tests. 528288943Sdim // FIXME: For catch, __except, __finally the first token on the line 529288943Sdim // is '}', so this isn't correct here. 530288943Sdim if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch, 531288943Sdim Keywords.kw___except, tok::kw___finally)) 532277325Sdim return 0; 533277325Sdim } 534277325Sdim 535327952Sdim if (Line.Last->is(tok::l_brace)) { 536327952Sdim FormatToken *Tok = I[1]->First; 537327952Sdim if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore && 538327952Sdim (Tok->getNextNonComment() == nullptr || 539327952Sdim Tok->getNextNonComment()->is(tok::semi))) { 540327952Sdim // We merge empty blocks even if the line exceeds the column limit. 541327952Sdim Tok->SpacesRequiredBefore = 0; 542327952Sdim Tok->CanBreakBefore = true; 543327952Sdim return 1; 544344779Sdim } else if (Limit != 0 && !Line.startsWithNamespace() && 545327952Sdim !startsExternCBlock(Line)) { 546327952Sdim // We don't merge short records. 547327952Sdim FormatToken *RecordTok = Line.First; 548327952Sdim // Skip record modifiers. 549327952Sdim while (RecordTok->Next && 550327952Sdim RecordTok->isOneOf(tok::kw_typedef, tok::kw_export, 551327952Sdim Keywords.kw_declare, Keywords.kw_abstract, 552327952Sdim tok::kw_default)) 553327952Sdim RecordTok = RecordTok->Next; 554327952Sdim if (RecordTok && 555327952Sdim RecordTok->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct, 556327952Sdim Keywords.kw_interface)) 557327952Sdim return 0; 558277325Sdim 559327952Sdim // Check that we still have three lines and they fit into the limit. 560327952Sdim if (I + 2 == E || I[2]->Type == LT_Invalid) 561327952Sdim return 0; 562327952Sdim Limit = limitConsideringMacros(I + 2, E, Limit); 563277325Sdim 564327952Sdim if (!nextTwoLinesFitInto(I, Limit)) 565327952Sdim return 0; 566277325Sdim 567327952Sdim // Second, check that the next line does not contain any braces - if it 568327952Sdim // does, readability declines when putting it into a single line. 569327952Sdim if (I[1]->Last->is(TT_LineComment)) 570277325Sdim return 0; 571327952Sdim do { 572327952Sdim if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit) 573327952Sdim return 0; 574327952Sdim Tok = Tok->Next; 575327952Sdim } while (Tok); 576277325Sdim 577327952Sdim // Last, check that the third line starts with a closing brace. 578327952Sdim Tok = I[2]->First; 579327952Sdim if (Tok->isNot(tok::r_brace)) 580327952Sdim return 0; 581327952Sdim 582327952Sdim // Don't merge "if (a) { .. } else {". 583327952Sdim if (Tok->Next && Tok->Next->is(tok::kw_else)) 584327952Sdim return 0; 585327952Sdim 586327952Sdim return 2; 587327952Sdim } 588327952Sdim } else if (I[1]->First->is(tok::l_brace)) { 589327952Sdim if (I[1]->Last->is(TT_LineComment)) 590277325Sdim return 0; 591277325Sdim 592327952Sdim // Check for Limit <= 2 to account for the " {". 593327952Sdim if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I))) 594288943Sdim return 0; 595327952Sdim Limit -= 2; 596327952Sdim unsigned MergedLines = 0; 597327952Sdim if (Style.AllowShortBlocksOnASingleLine || 598327952Sdim (I[1]->First == I[1]->Last && I + 2 != E && 599327952Sdim I[2]->First->is(tok::r_brace))) { 600327952Sdim MergedLines = tryMergeSimpleBlock(I + 1, E, Limit); 601327952Sdim // If we managed to merge the block, count the statement header, which 602327952Sdim // is on a separate line. 603327952Sdim if (MergedLines > 0) 604327952Sdim ++MergedLines; 605327952Sdim } 606327952Sdim return MergedLines; 607277325Sdim } 608277325Sdim return 0; 609277325Sdim } 610277325Sdim 611277325Sdim /// Returns the modified column limit for \p I if it is inside a macro and 612277325Sdim /// needs a trailing '\'. 613277325Sdim unsigned 614277325Sdim limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 615277325Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 616277325Sdim unsigned Limit) { 617277325Sdim if (I[0]->InPPDirective && I + 1 != E && 618277325Sdim !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) { 619277325Sdim return Limit < 2 ? 0 : Limit - 2; 620277325Sdim } 621277325Sdim return Limit; 622277325Sdim } 623277325Sdim 624277325Sdim bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 625277325Sdim unsigned Limit) { 626277325Sdim if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore) 627277325Sdim return false; 628277325Sdim return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit; 629277325Sdim } 630277325Sdim 631277325Sdim bool containsMustBreak(const AnnotatedLine *Line) { 632277325Sdim for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) { 633277325Sdim if (Tok->MustBreakBefore) 634277325Sdim return true; 635277325Sdim } 636277325Sdim return false; 637277325Sdim } 638277325Sdim 639288943Sdim void join(AnnotatedLine &A, const AnnotatedLine &B) { 640288943Sdim assert(!A.Last->Next); 641288943Sdim assert(!B.First->Previous); 642288943Sdim if (B.Affected) 643288943Sdim A.Affected = true; 644288943Sdim A.Last->Next = B.First; 645288943Sdim B.First->Previous = A.Last; 646288943Sdim B.First->CanBreakBefore = true; 647288943Sdim unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore; 648288943Sdim for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) { 649288943Sdim Tok->TotalLength += LengthA; 650288943Sdim A.Last = Tok; 651288943Sdim } 652288943Sdim } 653288943Sdim 654277325Sdim const FormatStyle &Style; 655288943Sdim const AdditionalKeywords &Keywords; 656288943Sdim const SmallVectorImpl<AnnotatedLine *>::const_iterator End; 657288943Sdim 658288943Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator Next; 659321369Sdim const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines; 660277325Sdim}; 661277325Sdim 662288943Sdimstatic void markFinalized(FormatToken *Tok) { 663288943Sdim for (; Tok; Tok = Tok->Next) { 664288943Sdim Tok->Finalized = true; 665288943Sdim for (AnnotatedLine *Child : Tok->Children) 666288943Sdim markFinalized(Child->First); 667288943Sdim } 668288943Sdim} 669288943Sdim 670288943Sdim#ifndef NDEBUG 671288943Sdimstatic void printLineState(const LineState &State) { 672288943Sdim llvm::dbgs() << "State: "; 673288943Sdim for (const ParenState &P : State.Stack) { 674341825Sdim llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|" 675341825Sdim << P.LastSpace << "|" << P.NestedBlockIndent << " "; 676288943Sdim } 677288943Sdim llvm::dbgs() << State.NextToken->TokenText << "\n"; 678288943Sdim} 679288943Sdim#endif 680288943Sdim 681341825Sdim/// Base class for classes that format one \c AnnotatedLine. 682288943Sdimclass LineFormatter { 683277325Sdimpublic: 684288943Sdim LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces, 685288943Sdim const FormatStyle &Style, 686288943Sdim UnwrappedLineFormatter *BlockFormatter) 687288943Sdim : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style), 688288943Sdim BlockFormatter(BlockFormatter) {} 689288943Sdim virtual ~LineFormatter() {} 690277325Sdim 691341825Sdim /// Formats an \c AnnotatedLine and returns the penalty. 692288943Sdim /// 693288943Sdim /// If \p DryRun is \c false, directly applies the changes. 694327952Sdim virtual unsigned formatLine(const AnnotatedLine &Line, 695327952Sdim unsigned FirstIndent, 696327952Sdim unsigned FirstStartColumn, 697288943Sdim bool DryRun) = 0; 698288943Sdim 699288943Sdimprotected: 700341825Sdim /// If the \p State's next token is an r_brace closing a nested block, 701288943Sdim /// format the nested block before it. 702288943Sdim /// 703288943Sdim /// Returns \c true if all children could be placed successfully and adapts 704288943Sdim /// \p Penalty as well as \p State. If \p DryRun is false, also directly 705288943Sdim /// creates changes using \c Whitespaces. 706288943Sdim /// 707288943Sdim /// The crucial idea here is that children always get formatted upon 708288943Sdim /// encountering the closing brace right after the nested block. Now, if we 709288943Sdim /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is 710288943Sdim /// \c false), the entire block has to be kept on the same line (which is only 711288943Sdim /// possible if it fits on the line, only contains a single statement, etc. 712288943Sdim /// 713288943Sdim /// If \p NewLine is true, we format the nested block on separate lines, i.e. 714288943Sdim /// break after the "{", format all lines with correct indentation and the put 715288943Sdim /// the closing "}" on yet another new line. 716288943Sdim /// 717288943Sdim /// This enables us to keep the simple structure of the 718288943Sdim /// \c UnwrappedLineFormatter, where we only have two options for each token: 719288943Sdim /// break or don't break. 720288943Sdim bool formatChildren(LineState &State, bool NewLine, bool DryRun, 721288943Sdim unsigned &Penalty) { 722288943Sdim const FormatToken *LBrace = State.NextToken->getPreviousNonComment(); 723288943Sdim FormatToken &Previous = *State.NextToken->Previous; 724288943Sdim if (!LBrace || LBrace->isNot(tok::l_brace) || 725288943Sdim LBrace->BlockKind != BK_Block || Previous.Children.size() == 0) 726288943Sdim // The previous token does not open a block. Nothing to do. We don't 727288943Sdim // assert so that we can simply call this function for all tokens. 728288943Sdim return true; 729288943Sdim 730288943Sdim if (NewLine) { 731288943Sdim int AdditionalIndent = State.Stack.back().Indent - 732288943Sdim Previous.Children[0]->Level * Style.IndentWidth; 733288943Sdim 734288943Sdim Penalty += 735288943Sdim BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent, 736288943Sdim /*FixBadIndentation=*/true); 737288943Sdim return true; 738288943Sdim } 739288943Sdim 740288943Sdim if (Previous.Children[0]->First->MustBreakBefore) 741288943Sdim return false; 742288943Sdim 743321369Sdim // Cannot merge into one line if this line ends on a comment. 744321369Sdim if (Previous.is(tok::comment)) 745321369Sdim return false; 746321369Sdim 747288943Sdim // Cannot merge multiple statements into a single line. 748288943Sdim if (Previous.Children.size() > 1) 749288943Sdim return false; 750288943Sdim 751321369Sdim const AnnotatedLine *Child = Previous.Children[0]; 752288943Sdim // We can't put the closing "}" on a line with a trailing comment. 753321369Sdim if (Child->Last->isTrailingComment()) 754288943Sdim return false; 755288943Sdim 756288943Sdim // If the child line exceeds the column limit, we wouldn't want to merge it. 757288943Sdim // We add +2 for the trailing " }". 758288943Sdim if (Style.ColumnLimit > 0 && 759321369Sdim Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit) 760288943Sdim return false; 761288943Sdim 762288943Sdim if (!DryRun) { 763288943Sdim Whitespaces->replaceWhitespace( 764321369Sdim *Child->First, /*Newlines=*/0, /*Spaces=*/1, 765288943Sdim /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective); 766288943Sdim } 767327952Sdim Penalty += 768327952Sdim formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun); 769288943Sdim 770321369Sdim State.Column += 1 + Child->Last->TotalLength; 771288943Sdim return true; 772288943Sdim } 773288943Sdim 774288943Sdim ContinuationIndenter *Indenter; 775288943Sdim 776288943Sdimprivate: 777288943Sdim WhitespaceManager *Whitespaces; 778288943Sdim const FormatStyle &Style; 779288943Sdim UnwrappedLineFormatter *BlockFormatter; 780288943Sdim}; 781288943Sdim 782341825Sdim/// Formatter that keeps the existing line breaks. 783288943Sdimclass NoColumnLimitLineFormatter : public LineFormatter { 784288943Sdimpublic: 785288943Sdim NoColumnLimitLineFormatter(ContinuationIndenter *Indenter, 786288943Sdim WhitespaceManager *Whitespaces, 787288943Sdim const FormatStyle &Style, 788288943Sdim UnwrappedLineFormatter *BlockFormatter) 789288943Sdim : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {} 790288943Sdim 791341825Sdim /// Formats the line, simply keeping all of the input's line breaking 792288943Sdim /// decisions. 793288943Sdim unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, 794327952Sdim unsigned FirstStartColumn, bool DryRun) override { 795288943Sdim assert(!DryRun); 796327952Sdim LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn, 797327952Sdim &Line, /*DryRun=*/false); 798277325Sdim while (State.NextToken) { 799277325Sdim bool Newline = 800277325Sdim Indenter->mustBreak(State) || 801277325Sdim (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0); 802288943Sdim unsigned Penalty = 0; 803288943Sdim formatChildren(State, Newline, /*DryRun=*/false, Penalty); 804277325Sdim Indenter->addTokenToState(State, Newline, /*DryRun=*/false); 805277325Sdim } 806288943Sdim return 0; 807277325Sdim } 808288943Sdim}; 809277325Sdim 810341825Sdim/// Formatter that puts all tokens into a single line without breaks. 811288943Sdimclass NoLineBreakFormatter : public LineFormatter { 812288943Sdimpublic: 813288943Sdim NoLineBreakFormatter(ContinuationIndenter *Indenter, 814288943Sdim WhitespaceManager *Whitespaces, const FormatStyle &Style, 815288943Sdim UnwrappedLineFormatter *BlockFormatter) 816288943Sdim : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {} 817288943Sdim 818341825Sdim /// Puts all tokens into a single line. 819288943Sdim unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, 820327952Sdim unsigned FirstStartColumn, bool DryRun) override { 821288943Sdim unsigned Penalty = 0; 822327952Sdim LineState State = 823327952Sdim Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun); 824288943Sdim while (State.NextToken) { 825288943Sdim formatChildren(State, /*Newline=*/false, DryRun, Penalty); 826321369Sdim Indenter->addTokenToState( 827321369Sdim State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun); 828288943Sdim } 829288943Sdim return Penalty; 830288943Sdim } 831288943Sdim}; 832288943Sdim 833341825Sdim/// Finds the best way to break lines. 834288943Sdimclass OptimizingLineFormatter : public LineFormatter { 835288943Sdimpublic: 836288943Sdim OptimizingLineFormatter(ContinuationIndenter *Indenter, 837288943Sdim WhitespaceManager *Whitespaces, 838288943Sdim const FormatStyle &Style, 839288943Sdim UnwrappedLineFormatter *BlockFormatter) 840288943Sdim : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {} 841288943Sdim 842341825Sdim /// Formats the line by finding the best line breaks with line lengths 843288943Sdim /// below the column limit. 844288943Sdim unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent, 845327952Sdim unsigned FirstStartColumn, bool DryRun) override { 846327952Sdim LineState State = 847327952Sdim Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun); 848288943Sdim 849288943Sdim // If the ObjC method declaration does not fit on a line, we should format 850288943Sdim // it with one arg per line. 851288943Sdim if (State.Line->Type == LT_ObjCMethodDecl) 852288943Sdim State.Stack.back().BreakBeforeParameter = true; 853288943Sdim 854288943Sdim // Find best solution in solution space. 855288943Sdim return analyzeSolutionSpace(State, DryRun); 856288943Sdim } 857288943Sdim 858277325Sdimprivate: 859288943Sdim struct CompareLineStatePointers { 860288943Sdim bool operator()(LineState *obj1, LineState *obj2) const { 861288943Sdim return *obj1 < *obj2; 862288943Sdim } 863288943Sdim }; 864288943Sdim 865341825Sdim /// A pair of <penalty, count> that is used to prioritize the BFS on. 866288943Sdim /// 867288943Sdim /// In case of equal penalties, we want to prefer states that were inserted 868288943Sdim /// first. During state generation we make sure that we insert states first 869288943Sdim /// that break the line as late as possible. 870288943Sdim typedef std::pair<unsigned, unsigned> OrderedPenalty; 871288943Sdim 872341825Sdim /// An edge in the solution space from \c Previous->State to \c State, 873288943Sdim /// inserting a newline dependent on the \c NewLine. 874288943Sdim struct StateNode { 875288943Sdim StateNode(const LineState &State, bool NewLine, StateNode *Previous) 876288943Sdim : State(State), NewLine(NewLine), Previous(Previous) {} 877288943Sdim LineState State; 878288943Sdim bool NewLine; 879288943Sdim StateNode *Previous; 880288943Sdim }; 881288943Sdim 882341825Sdim /// An item in the prioritized BFS search queue. The \c StateNode's 883288943Sdim /// \c State has the given \c OrderedPenalty. 884288943Sdim typedef std::pair<OrderedPenalty, StateNode *> QueueItem; 885288943Sdim 886341825Sdim /// The BFS queue type. 887288943Sdim typedef std::priority_queue<QueueItem, std::vector<QueueItem>, 888327952Sdim std::greater<QueueItem>> 889327952Sdim QueueType; 890288943Sdim 891341825Sdim /// Analyze the entire solution space starting from \p InitialState. 892288943Sdim /// 893288943Sdim /// This implements a variant of Dijkstra's algorithm on the graph that spans 894288943Sdim /// the solution space (\c LineStates are the nodes). The algorithm tries to 895288943Sdim /// find the shortest path (the one with lowest penalty) from \p InitialState 896288943Sdim /// to a state where all tokens are placed. Returns the penalty. 897288943Sdim /// 898288943Sdim /// If \p DryRun is \c false, directly applies the changes. 899288943Sdim unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) { 900288943Sdim std::set<LineState *, CompareLineStatePointers> Seen; 901288943Sdim 902288943Sdim // Increasing count of \c StateNode items we have created. This is used to 903288943Sdim // create a deterministic order independent of the container. 904288943Sdim unsigned Count = 0; 905288943Sdim QueueType Queue; 906288943Sdim 907288943Sdim // Insert start element into queue. 908288943Sdim StateNode *Node = 909288943Sdim new (Allocator.Allocate()) StateNode(InitialState, false, nullptr); 910288943Sdim Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); 911288943Sdim ++Count; 912288943Sdim 913288943Sdim unsigned Penalty = 0; 914288943Sdim 915288943Sdim // While not empty, take first element and follow edges. 916288943Sdim while (!Queue.empty()) { 917288943Sdim Penalty = Queue.top().first.first; 918288943Sdim StateNode *Node = Queue.top().second; 919288943Sdim if (!Node->State.NextToken) { 920341825Sdim LLVM_DEBUG(llvm::dbgs() 921341825Sdim << "\n---\nPenalty for line: " << Penalty << "\n"); 922288943Sdim break; 923288943Sdim } 924288943Sdim Queue.pop(); 925288943Sdim 926288943Sdim // Cut off the analysis of certain solutions if the analysis gets too 927288943Sdim // complex. See description of IgnoreStackForComparison. 928296417Sdim if (Count > 50000) 929288943Sdim Node->State.IgnoreStackForComparison = true; 930288943Sdim 931288943Sdim if (!Seen.insert(&Node->State).second) 932288943Sdim // State already examined with lower penalty. 933288943Sdim continue; 934288943Sdim 935288943Sdim FormatDecision LastFormat = Node->State.NextToken->Decision; 936288943Sdim if (LastFormat == FD_Unformatted || LastFormat == FD_Continue) 937288943Sdim addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue); 938288943Sdim if (LastFormat == FD_Unformatted || LastFormat == FD_Break) 939288943Sdim addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue); 940288943Sdim } 941288943Sdim 942288943Sdim if (Queue.empty()) { 943288943Sdim // We were unable to find a solution, do nothing. 944288943Sdim // FIXME: Add diagnostic? 945341825Sdim LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n"); 946288943Sdim return 0; 947288943Sdim } 948288943Sdim 949288943Sdim // Reconstruct the solution. 950288943Sdim if (!DryRun) 951288943Sdim reconstructPath(InitialState, Queue.top().second); 952288943Sdim 953341825Sdim LLVM_DEBUG(llvm::dbgs() 954341825Sdim << "Total number of analyzed states: " << Count << "\n"); 955341825Sdim LLVM_DEBUG(llvm::dbgs() << "---\n"); 956288943Sdim 957288943Sdim return Penalty; 958288943Sdim } 959288943Sdim 960341825Sdim /// Add the following state to the analysis queue \c Queue. 961288943Sdim /// 962288943Sdim /// Assume the current state is \p PreviousNode and has been reached with a 963288943Sdim /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. 964288943Sdim void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, 965288943Sdim bool NewLine, unsigned *Count, QueueType *Queue) { 966288943Sdim if (NewLine && !Indenter->canBreak(PreviousNode->State)) 967288943Sdim return; 968288943Sdim if (!NewLine && Indenter->mustBreak(PreviousNode->State)) 969288943Sdim return; 970288943Sdim 971288943Sdim StateNode *Node = new (Allocator.Allocate()) 972288943Sdim StateNode(PreviousNode->State, NewLine, PreviousNode); 973288943Sdim if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty)) 974288943Sdim return; 975288943Sdim 976288943Sdim Penalty += Indenter->addTokenToState(Node->State, NewLine, true); 977288943Sdim 978288943Sdim Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node)); 979288943Sdim ++(*Count); 980288943Sdim } 981288943Sdim 982341825Sdim /// Applies the best formatting by reconstructing the path in the 983288943Sdim /// solution space that leads to \c Best. 984288943Sdim void reconstructPath(LineState &State, StateNode *Best) { 985288943Sdim std::deque<StateNode *> Path; 986288943Sdim // We do not need a break before the initial token. 987288943Sdim while (Best->Previous) { 988288943Sdim Path.push_front(Best); 989288943Sdim Best = Best->Previous; 990288943Sdim } 991344779Sdim for (auto I = Path.begin(), E = Path.end(); I != E; ++I) { 992288943Sdim unsigned Penalty = 0; 993288943Sdim formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty); 994288943Sdim Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false); 995288943Sdim 996341825Sdim LLVM_DEBUG({ 997288943Sdim printLineState((*I)->Previous->State); 998288943Sdim if ((*I)->NewLine) { 999288943Sdim llvm::dbgs() << "Penalty for placing " 1000344779Sdim << (*I)->Previous->State.NextToken->Tok.getName() 1001344779Sdim << " on a new line: " << Penalty << "\n"; 1002288943Sdim } 1003288943Sdim }); 1004288943Sdim } 1005288943Sdim } 1006288943Sdim 1007288943Sdim llvm::SpecificBumpPtrAllocator<StateNode> Allocator; 1008277325Sdim}; 1009277325Sdim 1010296417Sdim} // anonymous namespace 1011277325Sdim 1012277325Sdimunsigned 1013277325SdimUnwrappedLineFormatter::format(const SmallVectorImpl<AnnotatedLine *> &Lines, 1014277325Sdim bool DryRun, int AdditionalIndent, 1015327952Sdim bool FixBadIndentation, 1016327952Sdim unsigned FirstStartColumn, 1017327952Sdim unsigned NextStartColumn, 1018327952Sdim unsigned LastStartColumn) { 1019288943Sdim LineJoiner Joiner(Style, Keywords, Lines); 1020277325Sdim 1021277325Sdim // Try to look up already computed penalty in DryRun-mode. 1022277325Sdim std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey( 1023277325Sdim &Lines, AdditionalIndent); 1024277325Sdim auto CacheIt = PenaltyCache.find(CacheKey); 1025277325Sdim if (DryRun && CacheIt != PenaltyCache.end()) 1026277325Sdim return CacheIt->second; 1027277325Sdim 1028277325Sdim assert(!Lines.empty()); 1029277325Sdim unsigned Penalty = 0; 1030288943Sdim LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level, 1031288943Sdim AdditionalIndent); 1032277325Sdim const AnnotatedLine *PreviousLine = nullptr; 1033288943Sdim const AnnotatedLine *NextLine = nullptr; 1034296417Sdim 1035296417Sdim // The minimum level of consecutive lines that have been formatted. 1036296417Sdim unsigned RangeMinLevel = UINT_MAX; 1037296417Sdim 1038327952Sdim bool FirstLine = true; 1039288943Sdim for (const AnnotatedLine *Line = 1040288943Sdim Joiner.getNextMergedLine(DryRun, IndentTracker); 1041327952Sdim Line; Line = NextLine, FirstLine = false) { 1042288943Sdim const AnnotatedLine &TheLine = *Line; 1043288943Sdim unsigned Indent = IndentTracker.getIndent(); 1044296417Sdim 1045296417Sdim // We continue formatting unchanged lines to adjust their indent, e.g. if a 1046296417Sdim // scope was added. However, we need to carefully stop doing this when we 1047296417Sdim // exit the scope of affected lines to prevent indenting a the entire 1048296417Sdim // remaining file if it currently missing a closing brace. 1049341825Sdim bool PreviousRBrace = 1050341825Sdim PreviousLine && PreviousLine->startsWith(tok::r_brace); 1051296417Sdim bool ContinueFormatting = 1052296417Sdim TheLine.Level > RangeMinLevel || 1053341825Sdim (TheLine.Level == RangeMinLevel && !PreviousRBrace && 1054341825Sdim !TheLine.startsWith(tok::r_brace)); 1055296417Sdim 1056296417Sdim bool FixIndentation = (FixBadIndentation || ContinueFormatting) && 1057296417Sdim Indent != TheLine.First->OriginalColumn; 1058288943Sdim bool ShouldFormat = TheLine.Affected || FixIndentation; 1059288943Sdim // We cannot format this line; if the reason is that the line had a 1060288943Sdim // parsing error, remember that. 1061321369Sdim if (ShouldFormat && TheLine.Type == LT_Invalid && Status) { 1062321369Sdim Status->FormatComplete = false; 1063321369Sdim Status->Line = 1064321369Sdim SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation()); 1065321369Sdim } 1066277325Sdim 1067288943Sdim if (ShouldFormat && TheLine.Type != LT_Invalid) { 1068327952Sdim if (!DryRun) { 1069327952Sdim bool LastLine = Line->First->is(tok::eof); 1070341825Sdim formatFirstToken(TheLine, PreviousLine, Lines, Indent, 1071327952Sdim LastLine ? LastStartColumn : NextStartColumn + Indent); 1072327952Sdim } 1073277325Sdim 1074288943Sdim NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker); 1075288943Sdim unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine); 1076288943Sdim bool FitsIntoOneLine = 1077288943Sdim TheLine.Last->TotalLength + Indent <= ColumnLimit || 1078309124Sdim (TheLine.Type == LT_ImportStatement && 1079309124Sdim (Style.Language != FormatStyle::LK_JavaScript || 1080309124Sdim !Style.JavaScriptWrapImports)); 1081288943Sdim if (Style.ColumnLimit == 0) 1082288943Sdim NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this) 1083327952Sdim .formatLine(TheLine, NextStartColumn + Indent, 1084327952Sdim FirstLine ? FirstStartColumn : 0, DryRun); 1085288943Sdim else if (FitsIntoOneLine) 1086288943Sdim Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this) 1087327952Sdim .formatLine(TheLine, NextStartColumn + Indent, 1088327952Sdim FirstLine ? FirstStartColumn : 0, DryRun); 1089288943Sdim else 1090288943Sdim Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this) 1091327952Sdim .formatLine(TheLine, NextStartColumn + Indent, 1092327952Sdim FirstLine ? FirstStartColumn : 0, DryRun); 1093296417Sdim RangeMinLevel = std::min(RangeMinLevel, TheLine.Level); 1094277325Sdim } else { 1095288943Sdim // If no token in the current line is affected, we still need to format 1096288943Sdim // affected children. 1097288943Sdim if (TheLine.ChildrenAffected) 1098309124Sdim for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) 1099309124Sdim if (!Tok->Children.empty()) 1100309124Sdim format(Tok->Children, DryRun); 1101277325Sdim 1102288943Sdim // Adapt following lines on the current indent level to the same level 1103288943Sdim // unless the current \c AnnotatedLine is not at the beginning of a line. 1104288943Sdim bool StartsNewLine = 1105288943Sdim TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst; 1106288943Sdim if (StartsNewLine) 1107288943Sdim IndentTracker.adjustToUnmodifiedLine(TheLine); 1108288943Sdim if (!DryRun) { 1109288943Sdim bool ReformatLeadingWhitespace = 1110288943Sdim StartsNewLine && ((PreviousLine && PreviousLine->Affected) || 1111288943Sdim TheLine.LeadingEmptyLinesAffected); 1112288943Sdim // Format the first token. 1113288943Sdim if (ReformatLeadingWhitespace) 1114341825Sdim formatFirstToken(TheLine, PreviousLine, Lines, 1115327952Sdim TheLine.First->OriginalColumn, 1116321369Sdim TheLine.First->OriginalColumn); 1117288943Sdim else 1118288943Sdim Whitespaces->addUntouchableToken(*TheLine.First, 1119288943Sdim TheLine.InPPDirective); 1120288943Sdim 1121288943Sdim // Notify the WhitespaceManager about the unchanged whitespace. 1122288943Sdim for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next) 1123277325Sdim Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); 1124277325Sdim } 1125288943Sdim NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker); 1126296417Sdim RangeMinLevel = UINT_MAX; 1127277325Sdim } 1128288943Sdim if (!DryRun) 1129288943Sdim markFinalized(TheLine.First); 1130288943Sdim PreviousLine = &TheLine; 1131277325Sdim } 1132277325Sdim PenaltyCache[CacheKey] = Penalty; 1133277325Sdim return Penalty; 1134277325Sdim} 1135277325Sdim 1136341825Sdimvoid UnwrappedLineFormatter::formatFirstToken( 1137341825Sdim const AnnotatedLine &Line, const AnnotatedLine *PreviousLine, 1138341825Sdim const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent, 1139341825Sdim unsigned NewlineIndent) { 1140327952Sdim FormatToken &RootToken = *Line.First; 1141288943Sdim if (RootToken.is(tok::eof)) { 1142288943Sdim unsigned Newlines = std::min(RootToken.NewlinesBefore, 1u); 1143327952Sdim unsigned TokenIndent = Newlines ? NewlineIndent : 0; 1144327952Sdim Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent, 1145327952Sdim TokenIndent); 1146288943Sdim return; 1147288943Sdim } 1148277325Sdim unsigned Newlines = 1149277325Sdim std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1); 1150277325Sdim // Remove empty lines before "}" where applicable. 1151277325Sdim if (RootToken.is(tok::r_brace) && 1152277325Sdim (!RootToken.Next || 1153341825Sdim (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) && 1154341825Sdim // Do not remove empty lines before namespace closing "}". 1155341825Sdim !getNamespaceToken(&Line, Lines)) 1156277325Sdim Newlines = std::min(Newlines, 1u); 1157327952Sdim // Remove empty lines at the start of nested blocks (lambdas/arrow functions) 1158327952Sdim if (PreviousLine == nullptr && Line.Level > 0) 1159327952Sdim Newlines = std::min(Newlines, 1u); 1160277325Sdim if (Newlines == 0 && !RootToken.IsFirst) 1161277325Sdim Newlines = 1; 1162277325Sdim if (RootToken.IsFirst && !RootToken.HasUnescapedNewline) 1163277325Sdim Newlines = 0; 1164277325Sdim 1165277325Sdim // Remove empty lines after "{". 1166277325Sdim if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine && 1167277325Sdim PreviousLine->Last->is(tok::l_brace) && 1168344779Sdim !PreviousLine->startsWithNamespace() && 1169277325Sdim !startsExternCBlock(*PreviousLine)) 1170277325Sdim Newlines = 1; 1171277325Sdim 1172277325Sdim // Insert extra new line before access specifiers. 1173277325Sdim if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) && 1174277325Sdim RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1) 1175277325Sdim ++Newlines; 1176277325Sdim 1177277325Sdim // Remove empty lines after access specifiers. 1178288943Sdim if (PreviousLine && PreviousLine->First->isAccessSpecifier() && 1179288943Sdim (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline)) 1180277325Sdim Newlines = std::min(1u, Newlines); 1181277325Sdim 1182327952Sdim if (Newlines) 1183327952Sdim Indent = NewlineIndent; 1184327952Sdim 1185327952Sdim // Preprocessor directives get indented after the hash, if indented. 1186327952Sdim if (Line.Type == LT_PreprocessorDirective || Line.Type == LT_ImportStatement) 1187327952Sdim Indent = 0; 1188327952Sdim 1189321369Sdim Whitespaces->replaceWhitespace(RootToken, Newlines, Indent, Indent, 1190321369Sdim Line.InPPDirective && 1191321369Sdim !RootToken.HasUnescapedNewline); 1192277325Sdim} 1193277325Sdim 1194288943Sdimunsigned 1195288943SdimUnwrappedLineFormatter::getColumnLimit(bool InPPDirective, 1196288943Sdim const AnnotatedLine *NextLine) const { 1197288943Sdim // In preprocessor directives reserve two chars for trailing " \" if the 1198288943Sdim // next line continues the preprocessor directive. 1199288943Sdim bool ContinuesPPDirective = 1200288943Sdim InPPDirective && 1201288943Sdim // If there is no next line, this is likely a child line and the parent 1202288943Sdim // continues the preprocessor directive. 1203288943Sdim (!NextLine || 1204288943Sdim (NextLine->InPPDirective && 1205288943Sdim // If there is an unescaped newline between this line and the next, the 1206288943Sdim // next line starts a new preprocessor directive. 1207288943Sdim !NextLine->First->HasUnescapedNewline)); 1208288943Sdim return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0); 1209277325Sdim} 1210277325Sdim 1211277325Sdim} // namespace format 1212277325Sdim} // namespace clang 1213