contrib/llvm/tools/clang/lib/Format/UnwrappedLineFormatter.cpp

   1 //===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "NamespaceEndCommentsFixer.h"
  11 #include "UnwrappedLineFormatter.h"
  12 #include "WhitespaceManager.h"
  13 #include "llvm/Support/Debug.h"
  14 #include <queue>
  15
  16 #define DEBUG_TYPE "format-formatter"
  17
  18 namespace clang {
  19 namespace format {
  20
  21 namespace {
  22
  23 bool 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
  30 /// Tracks the indent level of \c AnnotatedLines across levels.
  31 ///
  32 /// \c nextLine must be called for each \c AnnotatedLine, after which \c
  33 /// getIndent() will return the indent for the last line \c nextLine was called
  34 /// with.
  35 /// If the line is not formatted (and thus the indent does not change), calling
  36 /// \c adjustToUnmodifiedLine after the call to \c nextLine will cause
  37 /// subsequent lines on the same level to be indented at the same level as the
  38 /// given line.
  39 class LevelIndentTracker {
  40 public:
  41   LevelIndentTracker(const FormatStyle &Style,
  42                      const AdditionalKeywords &Keywords, unsigned StartLevel,
  43                      int AdditionalIndent)
  44       : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {
  45     for (unsigned i = 0; i != StartLevel; ++i)
  46       IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
  47   }
  48
  49   /// Returns the indent for the current line.
  50   unsigned getIndent() const { return Indent; }
  51
  52   /// Update the indent state given that \p Line is going to be formatted
  53   /// next.
  54   void nextLine(const AnnotatedLine &Line) {
  55     Offset = getIndentOffset(*Line.First);
  56     // Update the indent level cache size so that we can rely on it
  57     // having the right size in adjustToUnmodifiedline.
  58     while (IndentForLevel.size() <= Line.Level)
  59       IndentForLevel.push_back(-1);
  60     if (Line.InPPDirective) {
  61       Indent = Line.Level * Style.IndentWidth + AdditionalIndent;
  62     } else {
  63       IndentForLevel.resize(Line.Level + 1);
  64       Indent = getIndent(IndentForLevel, Line.Level);
  65     }
  66     if (static_cast<int>(Indent) + Offset >= 0)
  67       Indent += Offset;
  68   }
  69
  70   /// Update the indent state given that \p Line indent should be
  71   /// skipped.
  72   void skipLine(const AnnotatedLine &Line) {
  73     while (IndentForLevel.size() <= Line.Level)
  74       IndentForLevel.push_back(Indent);
  75   }
  76
  77   /// Update the level indent to adapt to the given \p Line.
  78   ///
  79   /// When a line is not formatted, we move the subsequent lines on the same
  80   /// level to the same indent.
  81   /// Note that \c nextLine must have been called before this method.
  82   void adjustToUnmodifiedLine(const AnnotatedLine &Line) {
  83     unsigned LevelIndent = Line.First->OriginalColumn;
  84     if (static_cast<int>(LevelIndent) - Offset >= 0)
  85       LevelIndent -= Offset;
  86     if ((!Line.First->is(tok::comment) || IndentForLevel[Line.Level] == -1) &&
  87         !Line.InPPDirective)
  88       IndentForLevel[Line.Level] = LevelIndent;
  89   }
  90
  91 private:
  92   /// Get the offset of the line relatively to the level.
  93   ///
  94   /// For example, 'public:' labels in classes are offset by 1 or 2
  95   /// characters to the left from their level.
  96   int getIndentOffset(const FormatToken &RootToken) {
  97     if (Style.Language == FormatStyle::LK_Java ||
  98         Style.Language == FormatStyle::LK_JavaScript)
  99       return 0;
 100     if (RootToken.isAccessSpecifier(false) ||
 101         RootToken.isObjCAccessSpecifier() ||
 102         (RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals) &&
 103          RootToken.Next && RootToken.Next->is(tok::colon)))
 104       return Style.AccessModifierOffset;
 105     return 0;
 106   }
 107
 108   /// Get the indent of \p Level from \p IndentForLevel.
 109   ///
 110   /// \p IndentForLevel must contain the indent for the level \c l
 111   /// at \p IndentForLevel[l], or a value < 0 if the indent for
 112   /// that level is unknown.
 113   unsigned getIndent(ArrayRef<int> IndentForLevel, unsigned Level) {
 114     if (IndentForLevel[Level] != -1)
 115       return IndentForLevel[Level];
 116     if (Level == 0)
 117       return 0;
 118     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
 119   }
 120
 121   const FormatStyle &Style;
 122   const AdditionalKeywords &Keywords;
 123   const unsigned AdditionalIndent;
 124
 125   /// The indent in characters for each level.
 126   std::vector<int> IndentForLevel;
 127
 128   /// Offset of the current line relative to the indent level.
 129   ///
 130   /// For example, the 'public' keywords is often indented with a negative
 131   /// offset.
 132   int Offset = 0;
 133
 134   /// The current line's indent.
 135   unsigned Indent = 0;
 136 };
 137
 138 bool isNamespaceDeclaration(const AnnotatedLine *Line) {
 139   const FormatToken *NamespaceTok = Line->First;
 140   return NamespaceTok && NamespaceTok->getNamespaceToken();
 141 }
 142
 143 bool isEndOfNamespace(const AnnotatedLine *Line,
 144                       const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
 145   if (!Line->startsWith(tok::r_brace))
 146     return false;
 147   size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex;
 148   if (StartLineIndex == UnwrappedLine::kInvalidIndex)
 149     return false;
 150   assert(StartLineIndex < AnnotatedLines.size());
 151   return isNamespaceDeclaration(AnnotatedLines[StartLineIndex]);
 152 }
 153
 154 class LineJoiner {
 155 public:
 156   LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords,
 157              const SmallVectorImpl<AnnotatedLine *> &Lines)
 158       : Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()),
 159         AnnotatedLines(Lines) {}
 160
 161   /// Returns the next line, merging multiple lines into one if possible.
 162   const AnnotatedLine *getNextMergedLine(bool DryRun,
 163                                          LevelIndentTracker &IndentTracker) {
 164     if (Next == End)
 165       return nullptr;
 166     const AnnotatedLine *Current = *Next;
 167     IndentTracker.nextLine(*Current);
 168     unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next, End);
 169     if (MergedLines > 0 && Style.ColumnLimit == 0)
 170       // Disallow line merging if there is a break at the start of one of the
 171       // input lines.
 172       for (unsigned i = 0; i < MergedLines; ++i)
 173         if (Next[i + 1]->First->NewlinesBefore > 0)
 174           MergedLines = 0;
 175     if (!DryRun)
 176       for (unsigned i = 0; i < MergedLines; ++i)
 177         join(*Next[0], *Next[i + 1]);
 178     Next = Next + MergedLines + 1;
 179     return Current;
 180   }
 181
 182 private:
 183   /// Calculates how many lines can be merged into 1 starting at \p I.
 184   unsigned
 185   tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,
 186                            SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 187                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
 188     const unsigned Indent = IndentTracker.getIndent();
 189
 190     // Can't join the last line with anything.
 191     if (I + 1 == E)
 192       return 0;
 193     // We can never merge stuff if there are trailing line comments.
 194     const AnnotatedLine *TheLine = *I;
 195     if (TheLine->Last->is(TT_LineComment))
 196       return 0;
 197     if (I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
 198       return 0;
 199     if (TheLine->InPPDirective &&
 200         (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline))
 201       return 0;
 202
 203     if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
 204       return 0;
 205
 206     unsigned Limit =
 207         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
 208     // If we already exceed the column limit, we set 'Limit' to 0. The different
 209     // tryMerge..() functions can then decide whether to still do merging.
 210     Limit = TheLine->Last->TotalLength > Limit
 211                 ? 0
 212                 : Limit - TheLine->Last->TotalLength;
 213
 214     if (TheLine->Last->is(TT_FunctionLBrace) &&
 215         TheLine->First == TheLine->Last &&
 216         !Style.BraceWrapping.SplitEmptyFunction &&
 217         I[1]->First->is(tok::r_brace))
 218       return tryMergeSimpleBlock(I, E, Limit);
 219
 220     // Handle empty record blocks where the brace has already been wrapped
 221     if (TheLine->Last->is(tok::l_brace) && TheLine->First == TheLine->Last &&
 222         I != AnnotatedLines.begin()) {
 223       bool EmptyBlock = I[1]->First->is(tok::r_brace);
 224
 225       const FormatToken *Tok = I[-1]->First;
 226       if (Tok && Tok->is(tok::comment))
 227         Tok = Tok->getNextNonComment();
 228
 229       if (Tok && Tok->getNamespaceToken())
 230         return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock
 231                    ? tryMergeSimpleBlock(I, E, Limit)
 232                    : 0;
 233
 234       if (Tok && Tok->is(tok::kw_typedef))
 235         Tok = Tok->getNextNonComment();
 236       if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union,
 237                               tok::kw_extern, Keywords.kw_interface))
 238         return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock
 239                    ? tryMergeSimpleBlock(I, E, Limit)
 240                    : 0;
 241     }
 242
 243     // FIXME: TheLine->Level != 0 might or might not be the right check to do.
 244     // If necessary, change to something smarter.
 245     bool MergeShortFunctions =
 246         Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
 247         (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
 248          I[1]->First->is(tok::r_brace)) ||
 249         (Style.AllowShortFunctionsOnASingleLine & FormatStyle::SFS_InlineOnly &&
 250          TheLine->Level != 0);
 251
 252     if (Style.CompactNamespaces) {
 253       if (isNamespaceDeclaration(TheLine)) {
 254         int i = 0;
 255         unsigned closingLine = TheLine->MatchingClosingBlockLineIndex - 1;
 256         for (; I + 1 + i != E && isNamespaceDeclaration(I[i + 1]) &&
 257                closingLine == I[i + 1]->MatchingClosingBlockLineIndex &&
 258                I[i + 1]->Last->TotalLength < Limit;
 259              i++, closingLine--) {
 260           // No extra indent for compacted namespaces
 261           IndentTracker.skipLine(*I[i + 1]);
 262
 263           Limit -= I[i + 1]->Last->TotalLength;
 264         }
 265         return i;
 266       }
 267
 268       if (isEndOfNamespace(TheLine, AnnotatedLines)) {
 269         int i = 0;
 270         unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;
 271         for (; I + 1 + i != E && isEndOfNamespace(I[i + 1], AnnotatedLines) &&
 272                openingLine == I[i + 1]->MatchingOpeningBlockLineIndex;
 273              i++, openingLine--) {
 274           // No space between consecutive braces
 275           I[i + 1]->First->SpacesRequiredBefore = !I[i]->Last->is(tok::r_brace);
 276
 277           // Indent like the outer-most namespace
 278           IndentTracker.nextLine(*I[i + 1]);
 279         }
 280         return i;
 281       }
 282     }
 283
 284     // Try to merge a function block with left brace unwrapped
 285     if (TheLine->Last->is(TT_FunctionLBrace) &&
 286         TheLine->First != TheLine->Last) {
 287       return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
 288     }
 289     // Try to merge a control statement block with left brace unwrapped
 290     if (TheLine->Last->is(tok::l_brace) && TheLine->First != TheLine->Last &&
 291         TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) {
 292       return Style.AllowShortBlocksOnASingleLine
 293                  ? tryMergeSimpleBlock(I, E, Limit)
 294                  : 0;
 295     }
 296     // Try to merge a control statement block with left brace wrapped
 297     if (I[1]->First->is(tok::l_brace) &&
 298         TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) {
 299       return Style.BraceWrapping.AfterControlStatement
 300                  ? tryMergeSimpleBlock(I, E, Limit)
 301                  : 0;
 302     }
 303     // Try to merge either empty or one-line block if is precedeed by control
 304     // statement token
 305     if (TheLine->First->is(tok::l_brace) && TheLine->First == TheLine->Last &&
 306         I != AnnotatedLines.begin() &&
 307         I[-1]->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) {
 308       unsigned MergedLines = 0;
 309       if (Style.AllowShortBlocksOnASingleLine) {
 310         MergedLines = tryMergeSimpleBlock(I - 1, E, Limit);
 311         // If we managed to merge the block, discard the first merged line
 312         // since we are merging starting from I.
 313         if (MergedLines > 0)
 314           --MergedLines;
 315       }
 316       return MergedLines;
 317     }
 318     // Don't merge block with left brace wrapped after ObjC special blocks
 319     if (TheLine->First->is(tok::l_brace) && I != AnnotatedLines.begin() &&
 320         I[-1]->First->is(tok::at) && I[-1]->First->Next) {
 321       tok::ObjCKeywordKind kwId = I[-1]->First->Next->Tok.getObjCKeywordID();
 322       if (kwId == clang::tok::objc_autoreleasepool ||
 323           kwId == clang::tok::objc_synchronized)
 324         return 0;
 325     }
 326     // Try to merge a block with left brace wrapped that wasn't yet covered
 327     if (TheLine->Last->is(tok::l_brace)) {
 328       return !Style.BraceWrapping.AfterFunction ||
 329                      (I[1]->First->is(tok::r_brace) &&
 330                       !Style.BraceWrapping.SplitEmptyRecord)
 331                  ? tryMergeSimpleBlock(I, E, Limit)
 332                  : 0;
 333     }
 334     // Try to merge a function block with left brace wrapped
 335     if (I[1]->First->is(TT_FunctionLBrace) &&
 336         Style.BraceWrapping.AfterFunction) {
 337       if (I[1]->Last->is(TT_LineComment))
 338         return 0;
 339
 340       // Check for Limit <= 2 to account for the " {".
 341       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
 342         return 0;
 343       Limit -= 2;
 344
 345       unsigned MergedLines = 0;
 346       if (MergeShortFunctions ||
 347           (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
 348            I[1]->First == I[1]->Last && I + 2 != E &&
 349            I[2]->First->is(tok::r_brace))) {
 350         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
 351         // If we managed to merge the block, count the function header, which is
 352         // on a separate line.
 353         if (MergedLines > 0)
 354           ++MergedLines;
 355       }
 356       return MergedLines;
 357     }
 358     if (TheLine->First->is(tok::kw_if)) {
 359       return Style.AllowShortIfStatementsOnASingleLine
 360                  ? tryMergeSimpleControlStatement(I, E, Limit)
 361                  : 0;
 362     }
 363     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
 364       return Style.AllowShortLoopsOnASingleLine
 365                  ? tryMergeSimpleControlStatement(I, E, Limit)
 366                  : 0;
 367     }
 368     if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
 369       return Style.AllowShortCaseLabelsOnASingleLine
 370                  ? tryMergeShortCaseLabels(I, E, Limit)
 371                  : 0;
 372     }
 373     if (TheLine->InPPDirective &&
 374         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
 375       return tryMergeSimplePPDirective(I, E, Limit);
 376     }
 377     return 0;
 378   }
 379
 380   unsigned
 381   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 382                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 383                             unsigned Limit) {
 384     if (Limit == 0)
 385       return 0;
 386     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
 387       return 0;
 388     if (1 + I[1]->Last->TotalLength > Limit)
 389       return 0;
 390     return 1;
 391   }
 392
 393   unsigned tryMergeSimpleControlStatement(
 394       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 395       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
 396     if (Limit == 0)
 397       return 0;
 398     if (Style.BraceWrapping.AfterControlStatement &&
 399         (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
 400       return 0;
 401     if (I[1]->InPPDirective != (*I)->InPPDirective ||
 402         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
 403       return 0;
 404     Limit = limitConsideringMacros(I + 1, E, Limit);
 405     AnnotatedLine &Line = **I;
 406     if (Line.Last->isNot(tok::r_paren))
 407       return 0;
 408     if (1 + I[1]->Last->TotalLength > Limit)
 409       return 0;
 410     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,
 411                              TT_LineComment))
 412       return 0;
 413     // Only inline simple if's (no nested if or else).
 414     if (I + 2 != E && Line.startsWith(tok::kw_if) &&
 415         I[2]->First->is(tok::kw_else))
 416       return 0;
 417     return 1;
 418   }
 419
 420   unsigned
 421   tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 422                           SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 423                           unsigned Limit) {
 424     if (Limit == 0 || I + 1 == E ||
 425         I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
 426       return 0;
 427     unsigned NumStmts = 0;
 428     unsigned Length = 0;
 429     bool EndsWithComment = false;
 430     bool InPPDirective = I[0]->InPPDirective;
 431     const unsigned Level = I[0]->Level;
 432     for (; NumStmts < 3; ++NumStmts) {
 433       if (I + 1 + NumStmts == E)
 434         break;
 435       const AnnotatedLine *Line = I[1 + NumStmts];
 436       if (Line->InPPDirective != InPPDirective)
 437         break;
 438       if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
 439         break;
 440       if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
 441                                tok::kw_while) ||
 442           EndsWithComment)
 443         return 0;
 444       if (Line->First->is(tok::comment)) {
 445         if (Level != Line->Level)
 446           return 0;
 447         SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
 448         for (; J != E; ++J) {
 449           Line = *J;
 450           if (Line->InPPDirective != InPPDirective)
 451             break;
 452           if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
 453             break;
 454           if (Line->First->isNot(tok::comment) || Level != Line->Level)
 455             return 0;
 456         }
 457         break;
 458       }
 459       if (Line->Last->is(tok::comment))
 460         EndsWithComment = true;
 461       Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
 462     }
 463     if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
 464       return 0;
 465     return NumStmts;
 466   }
 467
 468   unsigned
 469   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 470                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 471                       unsigned Limit) {
 472     AnnotatedLine &Line = **I;
 473
 474     // Don't merge ObjC @ keywords and methods.
 475     // FIXME: If an option to allow short exception handling clauses on a single
 476     // line is added, change this to not return for @try and friends.
 477     if (Style.Language != FormatStyle::LK_Java &&
 478         Line.First->isOneOf(tok::at, tok::minus, tok::plus))
 479       return 0;
 480
 481     // Check that the current line allows merging. This depends on whether we
 482     // are in a control flow statements as well as several style flags.
 483     if (Line.First->isOneOf(tok::kw_else, tok::kw_case) ||
 484         (Line.First->Next && Line.First->Next->is(tok::kw_else)))
 485       return 0;
 486     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
 487                             tok::kw___try, tok::kw_catch, tok::kw___finally,
 488                             tok::kw_for, tok::r_brace, Keywords.kw___except)) {
 489       if (!Style.AllowShortBlocksOnASingleLine)
 490         return 0;
 491       // Don't merge when we can't except the case when
 492       // the control statement block is empty
 493       if (!Style.AllowShortIfStatementsOnASingleLine &&
 494           Line.startsWith(tok::kw_if) &&
 495           !Style.BraceWrapping.AfterControlStatement &&
 496           !I[1]->First->is(tok::r_brace))
 497         return 0;
 498       if (!Style.AllowShortIfStatementsOnASingleLine &&
 499           Line.startsWith(tok::kw_if) &&
 500           Style.BraceWrapping.AfterControlStatement && I + 2 != E &&
 501           !I[2]->First->is(tok::r_brace))
 502         return 0;
 503       if (!Style.AllowShortLoopsOnASingleLine &&
 504           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
 505           !Style.BraceWrapping.AfterControlStatement &&
 506           !I[1]->First->is(tok::r_brace))
 507         return 0;
 508       if (!Style.AllowShortLoopsOnASingleLine &&
 509           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
 510           Style.BraceWrapping.AfterControlStatement && I + 2 != E &&
 511           !I[2]->First->is(tok::r_brace))
 512         return 0;
 513       // FIXME: Consider an option to allow short exception handling clauses on
 514       // a single line.
 515       // FIXME: This isn't covered by tests.
 516       // FIXME: For catch, __except, __finally the first token on the line
 517       // is '}', so this isn't correct here.
 518       if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
 519                               Keywords.kw___except, tok::kw___finally))
 520         return 0;
 521     }
 522
 523     if (Line.Last->is(tok::l_brace)) {
 524       FormatToken *Tok = I[1]->First;
 525       if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
 526           (Tok->getNextNonComment() == nullptr ||
 527            Tok->getNextNonComment()->is(tok::semi))) {
 528         // We merge empty blocks even if the line exceeds the column limit.
 529         Tok->SpacesRequiredBefore = 0;
 530         Tok->CanBreakBefore = true;
 531         return 1;
 532       } else if (Limit != 0 && !Line.startsWith(tok::kw_namespace) &&
 533                  !startsExternCBlock(Line)) {
 534         // We don't merge short records.
 535         FormatToken *RecordTok = Line.First;
 536         // Skip record modifiers.
 537         while (RecordTok->Next &&
 538                RecordTok->isOneOf(tok::kw_typedef, tok::kw_export,
 539                                   Keywords.kw_declare, Keywords.kw_abstract,
 540                                   tok::kw_default))
 541           RecordTok = RecordTok->Next;
 542         if (RecordTok &&
 543             RecordTok->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct,
 544                                Keywords.kw_interface))
 545           return 0;
 546
 547         // Check that we still have three lines and they fit into the limit.
 548         if (I + 2 == E || I[2]->Type == LT_Invalid)
 549           return 0;
 550         Limit = limitConsideringMacros(I + 2, E, Limit);
 551
 552         if (!nextTwoLinesFitInto(I, Limit))
 553           return 0;
 554
 555         // Second, check that the next line does not contain any braces - if it
 556         // does, readability declines when putting it into a single line.
 557         if (I[1]->Last->is(TT_LineComment))
 558           return 0;
 559         do {
 560           if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
 561             return 0;
 562           Tok = Tok->Next;
 563         } while (Tok);
 564
 565         // Last, check that the third line starts with a closing brace.
 566         Tok = I[2]->First;
 567         if (Tok->isNot(tok::r_brace))
 568           return 0;
 569
 570         // Don't merge "if (a) { .. } else {".
 571         if (Tok->Next && Tok->Next->is(tok::kw_else))
 572           return 0;
 573
 574         return 2;
 575       }
 576     } else if (I[1]->First->is(tok::l_brace)) {
 577       if (I[1]->Last->is(TT_LineComment))
 578         return 0;
 579
 580       // Check for Limit <= 2 to account for the " {".
 581       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))
 582         return 0;
 583       Limit -= 2;
 584       unsigned MergedLines = 0;
 585       if (Style.AllowShortBlocksOnASingleLine ||
 586           (I[1]->First == I[1]->Last && I + 2 != E &&
 587            I[2]->First->is(tok::r_brace))) {
 588         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
 589         // If we managed to merge the block, count the statement header, which
 590         // is on a separate line.
 591         if (MergedLines > 0)
 592           ++MergedLines;
 593       }
 594       return MergedLines;
 595     }
 596     return 0;
 597   }
 598
 599   /// Returns the modified column limit for \p I if it is inside a macro and
 600   /// needs a trailing '\'.
 601   unsigned
 602   limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 603                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 604                          unsigned Limit) {
 605     if (I[0]->InPPDirective && I + 1 != E &&
 606         !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
 607       return Limit < 2 ? 0 : Limit - 2;
 608     }
 609     return Limit;
 610   }
 611
 612   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 613                            unsigned Limit) {
 614     if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
 615       return false;
 616     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
 617   }
 618
 619   bool containsMustBreak(const AnnotatedLine *Line) {
 620     for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
 621       if (Tok->MustBreakBefore)
 622         return true;
 623     }
 624     return false;
 625   }
 626
 627   void join(AnnotatedLine &A, const AnnotatedLine &B) {
 628     assert(!A.Last->Next);
 629     assert(!B.First->Previous);
 630     if (B.Affected)
 631       A.Affected = true;
 632     A.Last->Next = B.First;
 633     B.First->Previous = A.Last;
 634     B.First->CanBreakBefore = true;
 635     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
 636     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
 637       Tok->TotalLength += LengthA;
 638       A.Last = Tok;
 639     }
 640   }
 641
 642   const FormatStyle &Style;
 643   const AdditionalKeywords &Keywords;
 644   const SmallVectorImpl<AnnotatedLine *>::const_iterator End;
 645
 646   SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
 647   const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
 648 };
 649
 650 static void markFinalized(FormatToken *Tok) {
 651   for (; Tok; Tok = Tok->Next) {
 652     Tok->Finalized = true;
 653     for (AnnotatedLine *Child : Tok->Children)
 654       markFinalized(Child->First);
 655   }
 656 }
 657
 658 #ifndef NDEBUG
 659 static void printLineState(const LineState &State) {
 660   llvm::dbgs() << "State: ";
 661   for (const ParenState &P : State.Stack) {
 662     llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
 663                  << P.LastSpace << "|" << P.NestedBlockIndent << " ";
 664   }
 665   llvm::dbgs() << State.NextToken->TokenText << "\n";
 666 }
 667 #endif
 668
 669 /// Base class for classes that format one \c AnnotatedLine.
 670 class LineFormatter {
 671 public:
 672   LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,
 673                 const FormatStyle &Style,
 674                 UnwrappedLineFormatter *BlockFormatter)
 675       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
 676         BlockFormatter(BlockFormatter) {}
 677   virtual ~LineFormatter() {}
 678
 679   /// Formats an \c AnnotatedLine and returns the penalty.
 680   ///
 681   /// If \p DryRun is \c false, directly applies the changes.
 682   virtual unsigned formatLine(const AnnotatedLine &Line,
 683                               unsigned FirstIndent,
 684                               unsigned FirstStartColumn,
 685                               bool DryRun) = 0;
 686
 687 protected:
 688   /// If the \p State's next token is an r_brace closing a nested block,
 689   /// format the nested block before it.
 690   ///
 691   /// Returns \c true if all children could be placed successfully and adapts
 692   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
 693   /// creates changes using \c Whitespaces.
 694   ///
 695   /// The crucial idea here is that children always get formatted upon
 696   /// encountering the closing brace right after the nested block. Now, if we
 697   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
 698   /// \c false), the entire block has to be kept on the same line (which is only
 699   /// possible if it fits on the line, only contains a single statement, etc.
 700   ///
 701   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
 702   /// break after the "{", format all lines with correct indentation and the put
 703   /// the closing "}" on yet another new line.
 704   ///
 705   /// This enables us to keep the simple structure of the
 706   /// \c UnwrappedLineFormatter, where we only have two options for each token:
 707   /// break or don't break.
 708   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
 709                       unsigned &Penalty) {
 710     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
 711     FormatToken &Previous = *State.NextToken->Previous;
 712     if (!LBrace || LBrace->isNot(tok::l_brace) ||
 713         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
 714       // The previous token does not open a block. Nothing to do. We don't
 715       // assert so that we can simply call this function for all tokens.
 716       return true;
 717
 718     if (NewLine) {
 719       int AdditionalIndent = State.Stack.back().Indent -
 720                              Previous.Children[0]->Level * Style.IndentWidth;
 721
 722       Penalty +=
 723           BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,
 724                                  /*FixBadIndentation=*/true);
 725       return true;
 726     }
 727
 728     if (Previous.Children[0]->First->MustBreakBefore)
 729       return false;
 730
 731     // Cannot merge into one line if this line ends on a comment.
 732     if (Previous.is(tok::comment))
 733       return false;
 734
 735     // Cannot merge multiple statements into a single line.
 736     if (Previous.Children.size() > 1)
 737       return false;
 738
 739     const AnnotatedLine *Child = Previous.Children[0];
 740     // We can't put the closing "}" on a line with a trailing comment.
 741     if (Child->Last->isTrailingComment())
 742       return false;
 743
 744     // If the child line exceeds the column limit, we wouldn't want to merge it.
 745     // We add +2 for the trailing " }".
 746     if (Style.ColumnLimit > 0 &&
 747         Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit)
 748       return false;
 749
 750     if (!DryRun) {
 751       Whitespaces->replaceWhitespace(
 752           *Child->First, /*Newlines=*/0, /*Spaces=*/1,
 753           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
 754     }
 755     Penalty +=
 756         formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);
 757
 758     State.Column += 1 + Child->Last->TotalLength;
 759     return true;
 760   }
 761
 762   ContinuationIndenter *Indenter;
 763
 764 private:
 765   WhitespaceManager *Whitespaces;
 766   const FormatStyle &Style;
 767   UnwrappedLineFormatter *BlockFormatter;
 768 };
 769
 770 /// Formatter that keeps the existing line breaks.
 771 class NoColumnLimitLineFormatter : public LineFormatter {
 772 public:
 773   NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,
 774                              WhitespaceManager *Whitespaces,
 775                              const FormatStyle &Style,
 776                              UnwrappedLineFormatter *BlockFormatter)
 777       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 778
 779   /// Formats the line, simply keeping all of the input's line breaking
 780   /// decisions.
 781   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 782                       unsigned FirstStartColumn, bool DryRun) override {
 783     assert(!DryRun);
 784     LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,
 785                                                 &Line, /*DryRun=*/false);
 786     while (State.NextToken) {
 787       bool Newline =
 788           Indenter->mustBreak(State) ||
 789           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
 790       unsigned Penalty = 0;
 791       formatChildren(State, Newline, /*DryRun=*/false, Penalty);
 792       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
 793     }
 794     return 0;
 795   }
 796 };
 797
 798 /// Formatter that puts all tokens into a single line without breaks.
 799 class NoLineBreakFormatter : public LineFormatter {
 800 public:
 801   NoLineBreakFormatter(ContinuationIndenter *Indenter,
 802                        WhitespaceManager *Whitespaces, const FormatStyle &Style,
 803                        UnwrappedLineFormatter *BlockFormatter)
 804       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 805
 806   /// Puts all tokens into a single line.
 807   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 808                       unsigned FirstStartColumn, bool DryRun) override {
 809     unsigned Penalty = 0;
 810     LineState State =
 811         Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
 812     while (State.NextToken) {
 813       formatChildren(State, /*Newline=*/false, DryRun, Penalty);
 814       Indenter->addTokenToState(
 815           State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);
 816     }
 817     return Penalty;
 818   }
 819 };
 820
 821 /// Finds the best way to break lines.
 822 class OptimizingLineFormatter : public LineFormatter {
 823 public:
 824   OptimizingLineFormatter(ContinuationIndenter *Indenter,
 825                           WhitespaceManager *Whitespaces,
 826                           const FormatStyle &Style,
 827                           UnwrappedLineFormatter *BlockFormatter)
 828       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 829
 830   /// Formats the line by finding the best line breaks with line lengths
 831   /// below the column limit.
 832   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 833                       unsigned FirstStartColumn, bool DryRun) override {
 834     LineState State =
 835         Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
 836
 837     // If the ObjC method declaration does not fit on a line, we should format
 838     // it with one arg per line.
 839     if (State.Line->Type == LT_ObjCMethodDecl)
 840       State.Stack.back().BreakBeforeParameter = true;
 841
 842     // Find best solution in solution space.
 843     return analyzeSolutionSpace(State, DryRun);
 844   }
 845
 846 private:
 847   struct CompareLineStatePointers {
 848     bool operator()(LineState *obj1, LineState *obj2) const {
 849       return *obj1 < *obj2;
 850     }
 851   };
 852
 853   /// A pair of <penalty, count> that is used to prioritize the BFS on.
 854   ///
 855   /// In case of equal penalties, we want to prefer states that were inserted
 856   /// first. During state generation we make sure that we insert states first
 857   /// that break the line as late as possible.
 858   typedef std::pair<unsigned, unsigned> OrderedPenalty;
 859
 860   /// An edge in the solution space from \c Previous->State to \c State,
 861   /// inserting a newline dependent on the \c NewLine.
 862   struct StateNode {
 863     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
 864         : State(State), NewLine(NewLine), Previous(Previous) {}
 865     LineState State;
 866     bool NewLine;
 867     StateNode *Previous;
 868   };
 869
 870   /// An item in the prioritized BFS search queue. The \c StateNode's
 871   /// \c State has the given \c OrderedPenalty.
 872   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
 873
 874   /// The BFS queue type.
 875   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
 876                               std::greater<QueueItem>>
 877       QueueType;
 878
 879   /// Analyze the entire solution space starting from \p InitialState.
 880   ///
 881   /// This implements a variant of Dijkstra's algorithm on the graph that spans
 882   /// the solution space (\c LineStates are the nodes). The algorithm tries to
 883   /// find the shortest path (the one with lowest penalty) from \p InitialState
 884   /// to a state where all tokens are placed. Returns the penalty.
 885   ///
 886   /// If \p DryRun is \c false, directly applies the changes.
 887   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {
 888     std::set<LineState *, CompareLineStatePointers> Seen;
 889
 890     // Increasing count of \c StateNode items we have created. This is used to
 891     // create a deterministic order independent of the container.
 892     unsigned Count = 0;
 893     QueueType Queue;
 894
 895     // Insert start element into queue.
 896     StateNode *Node =
 897         new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
 898     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
 899     ++Count;
 900
 901     unsigned Penalty = 0;
 902
 903     // While not empty, take first element and follow edges.
 904     while (!Queue.empty()) {
 905       Penalty = Queue.top().first.first;
 906       StateNode *Node = Queue.top().second;
 907       if (!Node->State.NextToken) {
 908         LLVM_DEBUG(llvm::dbgs()
 909                    << "\n---\nPenalty for line: " << Penalty << "\n");
 910         break;
 911       }
 912       Queue.pop();
 913
 914       // Cut off the analysis of certain solutions if the analysis gets too
 915       // complex. See description of IgnoreStackForComparison.
 916       if (Count > 50000)
 917         Node->State.IgnoreStackForComparison = true;
 918
 919       if (!Seen.insert(&Node->State).second)
 920         // State already examined with lower penalty.
 921         continue;
 922
 923       FormatDecision LastFormat = Node->State.NextToken->Decision;
 924       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
 925         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
 926       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
 927         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
 928     }
 929
 930     if (Queue.empty()) {
 931       // We were unable to find a solution, do nothing.
 932       // FIXME: Add diagnostic?
 933       LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");
 934       return 0;
 935     }
 936
 937     // Reconstruct the solution.
 938     if (!DryRun)
 939       reconstructPath(InitialState, Queue.top().second);
 940
 941     LLVM_DEBUG(llvm::dbgs()
 942                << "Total number of analyzed states: " << Count << "\n");
 943     LLVM_DEBUG(llvm::dbgs() << "---\n");
 944
 945     return Penalty;
 946   }
 947
 948   /// Add the following state to the analysis queue \c Queue.
 949   ///
 950   /// Assume the current state is \p PreviousNode and has been reached with a
 951   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
 952   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
 953                            bool NewLine, unsigned *Count, QueueType *Queue) {
 954     if (NewLine && !Indenter->canBreak(PreviousNode->State))
 955       return;
 956     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
 957       return;
 958
 959     StateNode *Node = new (Allocator.Allocate())
 960         StateNode(PreviousNode->State, NewLine, PreviousNode);
 961     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
 962       return;
 963
 964     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
 965
 966     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
 967     ++(*Count);
 968   }
 969
 970   /// Applies the best formatting by reconstructing the path in the
 971   /// solution space that leads to \c Best.
 972   void reconstructPath(LineState &State, StateNode *Best) {
 973     std::deque<StateNode *> Path;
 974     // We do not need a break before the initial token.
 975     while (Best->Previous) {
 976       Path.push_front(Best);
 977       Best = Best->Previous;
 978     }
 979     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
 980          I != E; ++I) {
 981       unsigned Penalty = 0;
 982       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
 983       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
 984
 985       LLVM_DEBUG({
 986         printLineState((*I)->Previous->State);
 987         if ((*I)->NewLine) {
 988           llvm::dbgs() << "Penalty for placing "
 989                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
 990                        << Penalty << "\n";
 991         }
 992       });
 993     }
 994   }
 995
 996   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
 997 };
 998
 999 } // anonymous namespace
1000
1001 unsigned
1002 UnwrappedLineFormatter::format(const SmallVectorImpl<AnnotatedLine *> &Lines,
1003                                bool DryRun, int AdditionalIndent,
1004                                bool FixBadIndentation,
1005                                unsigned FirstStartColumn,
1006                                unsigned NextStartColumn,
1007                                unsigned LastStartColumn) {
1008   LineJoiner Joiner(Style, Keywords, Lines);
1009
1010   // Try to look up already computed penalty in DryRun-mode.
1011   std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
1012       &Lines, AdditionalIndent);
1013   auto CacheIt = PenaltyCache.find(CacheKey);
1014   if (DryRun && CacheIt != PenaltyCache.end())
1015     return CacheIt->second;
1016
1017   assert(!Lines.empty());
1018   unsigned Penalty = 0;
1019   LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,
1020                                    AdditionalIndent);
1021   const AnnotatedLine *PreviousLine = nullptr;
1022   const AnnotatedLine *NextLine = nullptr;
1023
1024   // The minimum level of consecutive lines that have been formatted.
1025   unsigned RangeMinLevel = UINT_MAX;
1026
1027   bool FirstLine = true;
1028   for (const AnnotatedLine *Line =
1029            Joiner.getNextMergedLine(DryRun, IndentTracker);
1030        Line; Line = NextLine, FirstLine = false) {
1031     const AnnotatedLine &TheLine = *Line;
1032     unsigned Indent = IndentTracker.getIndent();
1033
1034     // We continue formatting unchanged lines to adjust their indent, e.g. if a
1035     // scope was added. However, we need to carefully stop doing this when we
1036     // exit the scope of affected lines to prevent indenting a the entire
1037     // remaining file if it currently missing a closing brace.
1038     bool PreviousRBrace =
1039         PreviousLine && PreviousLine->startsWith(tok::r_brace);
1040     bool ContinueFormatting =
1041         TheLine.Level > RangeMinLevel ||
1042         (TheLine.Level == RangeMinLevel && !PreviousRBrace &&
1043          !TheLine.startsWith(tok::r_brace));
1044
1045     bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&
1046                           Indent != TheLine.First->OriginalColumn;
1047     bool ShouldFormat = TheLine.Affected || FixIndentation;
1048     // We cannot format this line; if the reason is that the line had a
1049     // parsing error, remember that.
1050     if (ShouldFormat && TheLine.Type == LT_Invalid && Status) {
1051       Status->FormatComplete = false;
1052       Status->Line =
1053           SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());
1054     }
1055
1056     if (ShouldFormat && TheLine.Type != LT_Invalid) {
1057       if (!DryRun) {
1058         bool LastLine = Line->First->is(tok::eof);
1059         formatFirstToken(TheLine, PreviousLine, Lines, Indent,
1060                          LastLine ? LastStartColumn : NextStartColumn + Indent);
1061       }
1062
1063       NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1064       unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine);
1065       bool FitsIntoOneLine =
1066           TheLine.Last->TotalLength + Indent <= ColumnLimit ||
1067           (TheLine.Type == LT_ImportStatement &&
1068            (Style.Language != FormatStyle::LK_JavaScript ||
1069             !Style.JavaScriptWrapImports));
1070       if (Style.ColumnLimit == 0)
1071         NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)
1072             .formatLine(TheLine, NextStartColumn + Indent,
1073                         FirstLine ? FirstStartColumn : 0, DryRun);
1074       else if (FitsIntoOneLine)
1075         Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)
1076                        .formatLine(TheLine, NextStartColumn + Indent,
1077                                    FirstLine ? FirstStartColumn : 0, DryRun);
1078       else
1079         Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)
1080                        .formatLine(TheLine, NextStartColumn + Indent,
1081                                    FirstLine ? FirstStartColumn : 0, DryRun);
1082       RangeMinLevel = std::min(RangeMinLevel, TheLine.Level);
1083     } else {
1084       // If no token in the current line is affected, we still need to format
1085       // affected children.
1086       if (TheLine.ChildrenAffected)
1087         for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)
1088           if (!Tok->Children.empty())
1089             format(Tok->Children, DryRun);
1090
1091       // Adapt following lines on the current indent level to the same level
1092       // unless the current \c AnnotatedLine is not at the beginning of a line.
1093       bool StartsNewLine =
1094           TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;
1095       if (StartsNewLine)
1096         IndentTracker.adjustToUnmodifiedLine(TheLine);
1097       if (!DryRun) {
1098         bool ReformatLeadingWhitespace =
1099             StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||
1100                               TheLine.LeadingEmptyLinesAffected);
1101         // Format the first token.
1102         if (ReformatLeadingWhitespace)
1103           formatFirstToken(TheLine, PreviousLine, Lines,
1104                            TheLine.First->OriginalColumn,
1105                            TheLine.First->OriginalColumn);
1106         else
1107           Whitespaces->addUntouchableToken(*TheLine.First,
1108                                            TheLine.InPPDirective);
1109
1110         // Notify the WhitespaceManager about the unchanged whitespace.
1111         for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)
1112           Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
1113       }
1114       NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1115       RangeMinLevel = UINT_MAX;
1116     }
1117     if (!DryRun)
1118       markFinalized(TheLine.First);
1119     PreviousLine = &TheLine;
1120   }
1121   PenaltyCache[CacheKey] = Penalty;
1122   return Penalty;
1123 }
1124
1125 void UnwrappedLineFormatter::formatFirstToken(
1126     const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,
1127     const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,
1128     unsigned NewlineIndent) {
1129   FormatToken &RootToken = *Line.First;
1130   if (RootToken.is(tok::eof)) {
1131     unsigned Newlines = std::min(RootToken.NewlinesBefore, 1u);
1132     unsigned TokenIndent = Newlines ? NewlineIndent : 0;
1133     Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,
1134                                    TokenIndent);
1135     return;
1136   }
1137   unsigned Newlines =
1138       std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1139   // Remove empty lines before "}" where applicable.
1140   if (RootToken.is(tok::r_brace) &&
1141       (!RootToken.Next ||
1142        (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) &&
1143       // Do not remove empty lines before namespace closing "}".
1144       !getNamespaceToken(&Line, Lines))
1145     Newlines = std::min(Newlines, 1u);
1146   // Remove empty lines at the start of nested blocks (lambdas/arrow functions)
1147   if (PreviousLine == nullptr && Line.Level > 0)
1148     Newlines = std::min(Newlines, 1u);
1149   if (Newlines == 0 && !RootToken.IsFirst)
1150     Newlines = 1;
1151   if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1152     Newlines = 0;
1153
1154   // Remove empty lines after "{".
1155   if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1156       PreviousLine->Last->is(tok::l_brace) &&
1157       PreviousLine->First->isNot(tok::kw_namespace) &&
1158       !startsExternCBlock(*PreviousLine))
1159     Newlines = 1;
1160
1161   // Insert extra new line before access specifiers.
1162   if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1163       RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1164     ++Newlines;
1165
1166   // Remove empty lines after access specifiers.
1167   if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
1168       (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline))
1169     Newlines = std::min(1u, Newlines);
1170
1171   if (Newlines)
1172     Indent = NewlineIndent;
1173
1174   // Preprocessor directives get indented after the hash, if indented.
1175   if (Line.Type == LT_PreprocessorDirective || Line.Type == LT_ImportStatement)
1176     Indent = 0;
1177
1178   Whitespaces->replaceWhitespace(RootToken, Newlines, Indent, Indent,
1179                                  Line.InPPDirective &&
1180                                      !RootToken.HasUnescapedNewline);
1181 }
1182
1183 unsigned
1184 UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,
1185                                        const AnnotatedLine *NextLine) const {
1186   // In preprocessor directives reserve two chars for trailing " \" if the
1187   // next line continues the preprocessor directive.
1188   bool ContinuesPPDirective =
1189       InPPDirective &&
1190       // If there is no next line, this is likely a child line and the parent
1191       // continues the preprocessor directive.
1192       (!NextLine ||
1193        (NextLine->InPPDirective &&
1194         // If there is an unescaped newline between this line and the next, the
1195         // next line starts a new preprocessor directive.
1196         !NextLine->First->HasUnescapedNewline));
1197   return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);
1198 }
1199
1200 } // namespace format
1201 } // namespace clang