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     // Don't merge block with left brace wrapped after case labels
 327     if (TheLine->First->is(tok::l_brace) && I != AnnotatedLines.begin() &&
 328         I[-1]->First->isOneOf(tok::kw_case, tok::kw_default))
 329       return 0;
 330     // Try to merge a block with left brace wrapped that wasn't yet covered
 331     if (TheLine->Last->is(tok::l_brace)) {
 332       return !Style.BraceWrapping.AfterFunction ||
 333                      (I[1]->First->is(tok::r_brace) &&
 334                       !Style.BraceWrapping.SplitEmptyRecord)
 335                  ? tryMergeSimpleBlock(I, E, Limit)
 336                  : 0;
 337     }
 338     // Try to merge a function block with left brace wrapped
 339     if (I[1]->First->is(TT_FunctionLBrace) &&
 340         Style.BraceWrapping.AfterFunction) {
 341       if (I[1]->Last->is(TT_LineComment))
 342         return 0;
 343
 344       // Check for Limit <= 2 to account for the " {".
 345       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
 346         return 0;
 347       Limit -= 2;
 348
 349       unsigned MergedLines = 0;
 350       if (MergeShortFunctions ||
 351           (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
 352            I[1]->First == I[1]->Last && I + 2 != E &&
 353            I[2]->First->is(tok::r_brace))) {
 354         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
 355         // If we managed to merge the block, count the function header, which is
 356         // on a separate line.
 357         if (MergedLines > 0)
 358           ++MergedLines;
 359       }
 360       return MergedLines;
 361     }
 362     if (TheLine->First->is(tok::kw_if)) {
 363       return Style.AllowShortIfStatementsOnASingleLine
 364                  ? tryMergeSimpleControlStatement(I, E, Limit)
 365                  : 0;
 366     }
 367     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
 368       return Style.AllowShortLoopsOnASingleLine
 369                  ? tryMergeSimpleControlStatement(I, E, Limit)
 370                  : 0;
 371     }
 372     if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
 373       return Style.AllowShortCaseLabelsOnASingleLine
 374                  ? tryMergeShortCaseLabels(I, E, Limit)
 375                  : 0;
 376     }
 377     if (TheLine->InPPDirective &&
 378         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
 379       return tryMergeSimplePPDirective(I, E, Limit);
 380     }
 381     return 0;
 382   }
 383
 384   unsigned
 385   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 386                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 387                             unsigned Limit) {
 388     if (Limit == 0)
 389       return 0;
 390     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
 391       return 0;
 392     if (1 + I[1]->Last->TotalLength > Limit)
 393       return 0;
 394     return 1;
 395   }
 396
 397   unsigned tryMergeSimpleControlStatement(
 398       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 399       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
 400     if (Limit == 0)
 401       return 0;
 402     if (Style.BraceWrapping.AfterControlStatement &&
 403         (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
 404       return 0;
 405     if (I[1]->InPPDirective != (*I)->InPPDirective ||
 406         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
 407       return 0;
 408     Limit = limitConsideringMacros(I + 1, E, Limit);
 409     AnnotatedLine &Line = **I;
 410     if (Line.Last->isNot(tok::r_paren))
 411       return 0;
 412     if (1 + I[1]->Last->TotalLength > Limit)
 413       return 0;
 414     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,
 415                              TT_LineComment))
 416       return 0;
 417     // Only inline simple if's (no nested if or else).
 418     if (I + 2 != E && Line.startsWith(tok::kw_if) &&
 419         I[2]->First->is(tok::kw_else))
 420       return 0;
 421     return 1;
 422   }
 423
 424   unsigned
 425   tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 426                           SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 427                           unsigned Limit) {
 428     if (Limit == 0 || I + 1 == E ||
 429         I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
 430       return 0;
 431     if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))
 432       return 0;
 433     unsigned NumStmts = 0;
 434     unsigned Length = 0;
 435     bool EndsWithComment = false;
 436     bool InPPDirective = I[0]->InPPDirective;
 437     const unsigned Level = I[0]->Level;
 438     for (; NumStmts < 3; ++NumStmts) {
 439       if (I + 1 + NumStmts == E)
 440         break;
 441       const AnnotatedLine *Line = I[1 + NumStmts];
 442       if (Line->InPPDirective != InPPDirective)
 443         break;
 444       if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
 445         break;
 446       if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
 447                                tok::kw_while) ||
 448           EndsWithComment)
 449         return 0;
 450       if (Line->First->is(tok::comment)) {
 451         if (Level != Line->Level)
 452           return 0;
 453         SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
 454         for (; J != E; ++J) {
 455           Line = *J;
 456           if (Line->InPPDirective != InPPDirective)
 457             break;
 458           if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
 459             break;
 460           if (Line->First->isNot(tok::comment) || Level != Line->Level)
 461             return 0;
 462         }
 463         break;
 464       }
 465       if (Line->Last->is(tok::comment))
 466         EndsWithComment = true;
 467       Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
 468     }
 469     if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
 470       return 0;
 471     return NumStmts;
 472   }
 473
 474   unsigned
 475   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 476                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 477                       unsigned Limit) {
 478     AnnotatedLine &Line = **I;
 479
 480     // Don't merge ObjC @ keywords and methods.
 481     // FIXME: If an option to allow short exception handling clauses on a single
 482     // line is added, change this to not return for @try and friends.
 483     if (Style.Language != FormatStyle::LK_Java &&
 484         Line.First->isOneOf(tok::at, tok::minus, tok::plus))
 485       return 0;
 486
 487     // Check that the current line allows merging. This depends on whether we
 488     // are in a control flow statements as well as several style flags.
 489     if (Line.First->isOneOf(tok::kw_else, tok::kw_case) ||
 490         (Line.First->Next && Line.First->Next->is(tok::kw_else)))
 491       return 0;
 492     // default: in switch statement
 493     if (Line.First->is(tok::kw_default)) {
 494       const FormatToken *Tok = Line.First->getNextNonComment();
 495       if (Tok && Tok->is(tok::colon))
 496         return 0;
 497     }
 498     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
 499                             tok::kw___try, tok::kw_catch, tok::kw___finally,
 500                             tok::kw_for, tok::r_brace, Keywords.kw___except)) {
 501       if (!Style.AllowShortBlocksOnASingleLine)
 502         return 0;
 503       // Don't merge when we can't except the case when
 504       // the control statement block is empty
 505       if (!Style.AllowShortIfStatementsOnASingleLine &&
 506           Line.startsWith(tok::kw_if) &&
 507           !Style.BraceWrapping.AfterControlStatement &&
 508           !I[1]->First->is(tok::r_brace))
 509         return 0;
 510       if (!Style.AllowShortIfStatementsOnASingleLine &&
 511           Line.startsWith(tok::kw_if) &&
 512           Style.BraceWrapping.AfterControlStatement && I + 2 != E &&
 513           !I[2]->First->is(tok::r_brace))
 514         return 0;
 515       if (!Style.AllowShortLoopsOnASingleLine &&
 516           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
 517           !Style.BraceWrapping.AfterControlStatement &&
 518           !I[1]->First->is(tok::r_brace))
 519         return 0;
 520       if (!Style.AllowShortLoopsOnASingleLine &&
 521           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
 522           Style.BraceWrapping.AfterControlStatement && I + 2 != E &&
 523           !I[2]->First->is(tok::r_brace))
 524         return 0;
 525       // FIXME: Consider an option to allow short exception handling clauses on
 526       // a single line.
 527       // FIXME: This isn't covered by tests.
 528       // FIXME: For catch, __except, __finally the first token on the line
 529       // is '}', so this isn't correct here.
 530       if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
 531                               Keywords.kw___except, tok::kw___finally))
 532         return 0;
 533     }
 534
 535     if (Line.Last->is(tok::l_brace)) {
 536       FormatToken *Tok = I[1]->First;
 537       if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
 538           (Tok->getNextNonComment() == nullptr ||
 539            Tok->getNextNonComment()->is(tok::semi))) {
 540         // We merge empty blocks even if the line exceeds the column limit.
 541         Tok->SpacesRequiredBefore = 0;
 542         Tok->CanBreakBefore = true;
 543         return 1;
 544       } else if (Limit != 0 && !Line.startsWithNamespace() &&
 545                  !startsExternCBlock(Line)) {
 546         // We don't merge short records.
 547         FormatToken *RecordTok = Line.First;
 548         // Skip record modifiers.
 549         while (RecordTok->Next &&
 550                RecordTok->isOneOf(tok::kw_typedef, tok::kw_export,
 551                                   Keywords.kw_declare, Keywords.kw_abstract,
 552                                   tok::kw_default))
 553           RecordTok = RecordTok->Next;
 554         if (RecordTok &&
 555             RecordTok->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct,
 556                                Keywords.kw_interface))
 557           return 0;
 558
 559         // Check that we still have three lines and they fit into the limit.
 560         if (I + 2 == E || I[2]->Type == LT_Invalid)
 561           return 0;
 562         Limit = limitConsideringMacros(I + 2, E, Limit);
 563
 564         if (!nextTwoLinesFitInto(I, Limit))
 565           return 0;
 566
 567         // Second, check that the next line does not contain any braces - if it
 568         // does, readability declines when putting it into a single line.
 569         if (I[1]->Last->is(TT_LineComment))
 570           return 0;
 571         do {
 572           if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
 573             return 0;
 574           Tok = Tok->Next;
 575         } while (Tok);
 576
 577         // Last, check that the third line starts with a closing brace.
 578         Tok = I[2]->First;
 579         if (Tok->isNot(tok::r_brace))
 580           return 0;
 581
 582         // Don't merge "if (a) { .. } else {".
 583         if (Tok->Next && Tok->Next->is(tok::kw_else))
 584           return 0;
 585
 586         return 2;
 587       }
 588     } else if (I[1]->First->is(tok::l_brace)) {
 589       if (I[1]->Last->is(TT_LineComment))
 590         return 0;
 591
 592       // Check for Limit <= 2 to account for the " {".
 593       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))
 594         return 0;
 595       Limit -= 2;
 596       unsigned MergedLines = 0;
 597       if (Style.AllowShortBlocksOnASingleLine ||
 598           (I[1]->First == I[1]->Last && I + 2 != E &&
 599            I[2]->First->is(tok::r_brace))) {
 600         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
 601         // If we managed to merge the block, count the statement header, which
 602         // is on a separate line.
 603         if (MergedLines > 0)
 604           ++MergedLines;
 605       }
 606       return MergedLines;
 607     }
 608     return 0;
 609   }
 610
 611   /// Returns the modified column limit for \p I if it is inside a macro and
 612   /// needs a trailing '\'.
 613   unsigned
 614   limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 615                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 616                          unsigned Limit) {
 617     if (I[0]->InPPDirective && I + 1 != E &&
 618         !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
 619       return Limit < 2 ? 0 : Limit - 2;
 620     }
 621     return Limit;
 622   }
 623
 624   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 625                            unsigned Limit) {
 626     if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
 627       return false;
 628     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
 629   }
 630
 631   bool containsMustBreak(const AnnotatedLine *Line) {
 632     for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
 633       if (Tok->MustBreakBefore)
 634         return true;
 635     }
 636     return false;
 637   }
 638
 639   void join(AnnotatedLine &A, const AnnotatedLine &B) {
 640     assert(!A.Last->Next);
 641     assert(!B.First->Previous);
 642     if (B.Affected)
 643       A.Affected = true;
 644     A.Last->Next = B.First;
 645     B.First->Previous = A.Last;
 646     B.First->CanBreakBefore = true;
 647     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
 648     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
 649       Tok->TotalLength += LengthA;
 650       A.Last = Tok;
 651     }
 652   }
 653
 654   const FormatStyle &Style;
 655   const AdditionalKeywords &Keywords;
 656   const SmallVectorImpl<AnnotatedLine *>::const_iterator End;
 657
 658   SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
 659   const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
 660 };
 661
 662 static void markFinalized(FormatToken *Tok) {
 663   for (; Tok; Tok = Tok->Next) {
 664     Tok->Finalized = true;
 665     for (AnnotatedLine *Child : Tok->Children)
 666       markFinalized(Child->First);
 667   }
 668 }
 669
 670 #ifndef NDEBUG
 671 static void printLineState(const LineState &State) {
 672   llvm::dbgs() << "State: ";
 673   for (const ParenState &P : State.Stack) {
 674     llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
 675                  << P.LastSpace << "|" << P.NestedBlockIndent << " ";
 676   }
 677   llvm::dbgs() << State.NextToken->TokenText << "\n";
 678 }
 679 #endif
 680
 681 /// Base class for classes that format one \c AnnotatedLine.
 682 class LineFormatter {
 683 public:
 684   LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,
 685                 const FormatStyle &Style,
 686                 UnwrappedLineFormatter *BlockFormatter)
 687       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
 688         BlockFormatter(BlockFormatter) {}
 689   virtual ~LineFormatter() {}
 690
 691   /// Formats an \c AnnotatedLine and returns the penalty.
 692   ///
 693   /// If \p DryRun is \c false, directly applies the changes.
 694   virtual unsigned formatLine(const AnnotatedLine &Line,
 695                               unsigned FirstIndent,
 696                               unsigned FirstStartColumn,
 697                               bool DryRun) = 0;
 698
 699 protected:
 700   /// If the \p State's next token is an r_brace closing a nested block,
 701   /// format the nested block before it.
 702   ///
 703   /// Returns \c true if all children could be placed successfully and adapts
 704   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
 705   /// creates changes using \c Whitespaces.
 706   ///
 707   /// The crucial idea here is that children always get formatted upon
 708   /// encountering the closing brace right after the nested block. Now, if we
 709   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
 710   /// \c false), the entire block has to be kept on the same line (which is only
 711   /// possible if it fits on the line, only contains a single statement, etc.
 712   ///
 713   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
 714   /// break after the "{", format all lines with correct indentation and the put
 715   /// the closing "}" on yet another new line.
 716   ///
 717   /// This enables us to keep the simple structure of the
 718   /// \c UnwrappedLineFormatter, where we only have two options for each token:
 719   /// break or don't break.
 720   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
 721                       unsigned &Penalty) {
 722     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
 723     FormatToken &Previous = *State.NextToken->Previous;
 724     if (!LBrace || LBrace->isNot(tok::l_brace) ||
 725         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
 726       // The previous token does not open a block. Nothing to do. We don't
 727       // assert so that we can simply call this function for all tokens.
 728       return true;
 729
 730     if (NewLine) {
 731       int AdditionalIndent = State.Stack.back().Indent -
 732                              Previous.Children[0]->Level * Style.IndentWidth;
 733
 734       Penalty +=
 735           BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,
 736                                  /*FixBadIndentation=*/true);
 737       return true;
 738     }
 739
 740     if (Previous.Children[0]->First->MustBreakBefore)
 741       return false;
 742
 743     // Cannot merge into one line if this line ends on a comment.
 744     if (Previous.is(tok::comment))
 745       return false;
 746
 747     // Cannot merge multiple statements into a single line.
 748     if (Previous.Children.size() > 1)
 749       return false;
 750
 751     const AnnotatedLine *Child = Previous.Children[0];
 752     // We can't put the closing "}" on a line with a trailing comment.
 753     if (Child->Last->isTrailingComment())
 754       return false;
 755
 756     // If the child line exceeds the column limit, we wouldn't want to merge it.
 757     // We add +2 for the trailing " }".
 758     if (Style.ColumnLimit > 0 &&
 759         Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit)
 760       return false;
 761
 762     if (!DryRun) {
 763       Whitespaces->replaceWhitespace(
 764           *Child->First, /*Newlines=*/0, /*Spaces=*/1,
 765           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
 766     }
 767     Penalty +=
 768         formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);
 769
 770     State.Column += 1 + Child->Last->TotalLength;
 771     return true;
 772   }
 773
 774   ContinuationIndenter *Indenter;
 775
 776 private:
 777   WhitespaceManager *Whitespaces;
 778   const FormatStyle &Style;
 779   UnwrappedLineFormatter *BlockFormatter;
 780 };
 781
 782 /// Formatter that keeps the existing line breaks.
 783 class NoColumnLimitLineFormatter : public LineFormatter {
 784 public:
 785   NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,
 786                              WhitespaceManager *Whitespaces,
 787                              const FormatStyle &Style,
 788                              UnwrappedLineFormatter *BlockFormatter)
 789       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 790
 791   /// Formats the line, simply keeping all of the input's line breaking
 792   /// decisions.
 793   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 794                       unsigned FirstStartColumn, bool DryRun) override {
 795     assert(!DryRun);
 796     LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,
 797                                                 &Line, /*DryRun=*/false);
 798     while (State.NextToken) {
 799       bool Newline =
 800           Indenter->mustBreak(State) ||
 801           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
 802       unsigned Penalty = 0;
 803       formatChildren(State, Newline, /*DryRun=*/false, Penalty);
 804       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
 805     }
 806     return 0;
 807   }
 808 };
 809
 810 /// Formatter that puts all tokens into a single line without breaks.
 811 class NoLineBreakFormatter : public LineFormatter {
 812 public:
 813   NoLineBreakFormatter(ContinuationIndenter *Indenter,
 814                        WhitespaceManager *Whitespaces, const FormatStyle &Style,
 815                        UnwrappedLineFormatter *BlockFormatter)
 816       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 817
 818   /// Puts all tokens into a single line.
 819   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 820                       unsigned FirstStartColumn, bool DryRun) override {
 821     unsigned Penalty = 0;
 822     LineState State =
 823         Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
 824     while (State.NextToken) {
 825       formatChildren(State, /*Newline=*/false, DryRun, Penalty);
 826       Indenter->addTokenToState(
 827           State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);
 828     }
 829     return Penalty;
 830   }
 831 };
 832
 833 /// Finds the best way to break lines.
 834 class OptimizingLineFormatter : public LineFormatter {
 835 public:
 836   OptimizingLineFormatter(ContinuationIndenter *Indenter,
 837                           WhitespaceManager *Whitespaces,
 838                           const FormatStyle &Style,
 839                           UnwrappedLineFormatter *BlockFormatter)
 840       : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
 841
 842   /// Formats the line by finding the best line breaks with line lengths
 843   /// below the column limit.
 844   unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
 845                       unsigned FirstStartColumn, bool DryRun) override {
 846     LineState State =
 847         Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
 848
 849     // If the ObjC method declaration does not fit on a line, we should format
 850     // it with one arg per line.
 851     if (State.Line->Type == LT_ObjCMethodDecl)
 852       State.Stack.back().BreakBeforeParameter = true;
 853
 854     // Find best solution in solution space.
 855     return analyzeSolutionSpace(State, DryRun);
 856   }
 857
 858 private:
 859   struct CompareLineStatePointers {
 860     bool operator()(LineState *obj1, LineState *obj2) const {
 861       return *obj1 < *obj2;
 862     }
 863   };
 864
 865   /// A pair of <penalty, count> that is used to prioritize the BFS on.
 866   ///
 867   /// In case of equal penalties, we want to prefer states that were inserted
 868   /// first. During state generation we make sure that we insert states first
 869   /// that break the line as late as possible.
 870   typedef std::pair<unsigned, unsigned> OrderedPenalty;
 871
 872   /// An edge in the solution space from \c Previous->State to \c State,
 873   /// inserting a newline dependent on the \c NewLine.
 874   struct StateNode {
 875     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
 876         : State(State), NewLine(NewLine), Previous(Previous) {}
 877     LineState State;
 878     bool NewLine;
 879     StateNode *Previous;
 880   };
 881
 882   /// An item in the prioritized BFS search queue. The \c StateNode's
 883   /// \c State has the given \c OrderedPenalty.
 884   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
 885
 886   /// The BFS queue type.
 887   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
 888                               std::greater<QueueItem>>
 889       QueueType;
 890
 891   /// Analyze the entire solution space starting from \p InitialState.
 892   ///
 893   /// This implements a variant of Dijkstra's algorithm on the graph that spans
 894   /// the solution space (\c LineStates are the nodes). The algorithm tries to
 895   /// find the shortest path (the one with lowest penalty) from \p InitialState
 896   /// to a state where all tokens are placed. Returns the penalty.
 897   ///
 898   /// If \p DryRun is \c false, directly applies the changes.
 899   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {
 900     std::set<LineState *, CompareLineStatePointers> Seen;
 901
 902     // Increasing count of \c StateNode items we have created. This is used to
 903     // create a deterministic order independent of the container.
 904     unsigned Count = 0;
 905     QueueType Queue;
 906
 907     // Insert start element into queue.
 908     StateNode *Node =
 909         new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
 910     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
 911     ++Count;
 912
 913     unsigned Penalty = 0;
 914
 915     // While not empty, take first element and follow edges.
 916     while (!Queue.empty()) {
 917       Penalty = Queue.top().first.first;
 918       StateNode *Node = Queue.top().second;
 919       if (!Node->State.NextToken) {
 920         LLVM_DEBUG(llvm::dbgs()
 921                    << "\n---\nPenalty for line: " << Penalty << "\n");
 922         break;
 923       }
 924       Queue.pop();
 925
 926       // Cut off the analysis of certain solutions if the analysis gets too
 927       // complex. See description of IgnoreStackForComparison.
 928       if (Count > 50000)
 929         Node->State.IgnoreStackForComparison = true;
 930
 931       if (!Seen.insert(&Node->State).second)
 932         // State already examined with lower penalty.
 933         continue;
 934
 935       FormatDecision LastFormat = Node->State.NextToken->Decision;
 936       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
 937         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
 938       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
 939         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
 940     }
 941
 942     if (Queue.empty()) {
 943       // We were unable to find a solution, do nothing.
 944       // FIXME: Add diagnostic?
 945       LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");
 946       return 0;
 947     }
 948
 949     // Reconstruct the solution.
 950     if (!DryRun)
 951       reconstructPath(InitialState, Queue.top().second);
 952
 953     LLVM_DEBUG(llvm::dbgs()
 954                << "Total number of analyzed states: " << Count << "\n");
 955     LLVM_DEBUG(llvm::dbgs() << "---\n");
 956
 957     return Penalty;
 958   }
 959
 960   /// Add the following state to the analysis queue \c Queue.
 961   ///
 962   /// Assume the current state is \p PreviousNode and has been reached with a
 963   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
 964   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
 965                            bool NewLine, unsigned *Count, QueueType *Queue) {
 966     if (NewLine && !Indenter->canBreak(PreviousNode->State))
 967       return;
 968     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
 969       return;
 970
 971     StateNode *Node = new (Allocator.Allocate())
 972         StateNode(PreviousNode->State, NewLine, PreviousNode);
 973     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
 974       return;
 975
 976     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
 977
 978     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
 979     ++(*Count);
 980   }
 981
 982   /// Applies the best formatting by reconstructing the path in the
 983   /// solution space that leads to \c Best.
 984   void reconstructPath(LineState &State, StateNode *Best) {
 985     std::deque<StateNode *> Path;
 986     // We do not need a break before the initial token.
 987     while (Best->Previous) {
 988       Path.push_front(Best);
 989       Best = Best->Previous;
 990     }
 991     for (auto I = Path.begin(), E = Path.end(); I != E; ++I) {
 992       unsigned Penalty = 0;
 993       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
 994       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
 995
 996       LLVM_DEBUG({
 997         printLineState((*I)->Previous->State);
 998         if ((*I)->NewLine) {
 999           llvm::dbgs() << "Penalty for placing "
1000                        << (*I)->Previous->State.NextToken->Tok.getName()
1001                        << " on a new line: " << Penalty << "\n";
1002         }
1003       });
1004     }
1005   }
1006
1007   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1008 };
1009
1010 } // anonymous namespace
1011
1012 unsigned
1013 UnwrappedLineFormatter::format(const SmallVectorImpl<AnnotatedLine *> &Lines,
1014                                bool DryRun, int AdditionalIndent,
1015                                bool FixBadIndentation,
1016                                unsigned FirstStartColumn,
1017                                unsigned NextStartColumn,
1018                                unsigned LastStartColumn) {
1019   LineJoiner Joiner(Style, Keywords, Lines);
1020
1021   // Try to look up already computed penalty in DryRun-mode.
1022   std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
1023       &Lines, AdditionalIndent);
1024   auto CacheIt = PenaltyCache.find(CacheKey);
1025   if (DryRun && CacheIt != PenaltyCache.end())
1026     return CacheIt->second;
1027
1028   assert(!Lines.empty());
1029   unsigned Penalty = 0;
1030   LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,
1031                                    AdditionalIndent);
1032   const AnnotatedLine *PreviousLine = nullptr;
1033   const AnnotatedLine *NextLine = nullptr;
1034
1035   // The minimum level of consecutive lines that have been formatted.
1036   unsigned RangeMinLevel = UINT_MAX;
1037
1038   bool FirstLine = true;
1039   for (const AnnotatedLine *Line =
1040            Joiner.getNextMergedLine(DryRun, IndentTracker);
1041        Line; Line = NextLine, FirstLine = false) {
1042     const AnnotatedLine &TheLine = *Line;
1043     unsigned Indent = IndentTracker.getIndent();
1044
1045     // We continue formatting unchanged lines to adjust their indent, e.g. if a
1046     // scope was added. However, we need to carefully stop doing this when we
1047     // exit the scope of affected lines to prevent indenting a the entire
1048     // remaining file if it currently missing a closing brace.
1049     bool PreviousRBrace =
1050         PreviousLine && PreviousLine->startsWith(tok::r_brace);
1051     bool ContinueFormatting =
1052         TheLine.Level > RangeMinLevel ||
1053         (TheLine.Level == RangeMinLevel && !PreviousRBrace &&
1054          !TheLine.startsWith(tok::r_brace));
1055
1056     bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&
1057                           Indent != TheLine.First->OriginalColumn;
1058     bool ShouldFormat = TheLine.Affected || FixIndentation;
1059     // We cannot format this line; if the reason is that the line had a
1060     // parsing error, remember that.
1061     if (ShouldFormat && TheLine.Type == LT_Invalid && Status) {
1062       Status->FormatComplete = false;
1063       Status->Line =
1064           SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());
1065     }
1066
1067     if (ShouldFormat && TheLine.Type != LT_Invalid) {
1068       if (!DryRun) {
1069         bool LastLine = Line->First->is(tok::eof);
1070         formatFirstToken(TheLine, PreviousLine, Lines, Indent,
1071                          LastLine ? LastStartColumn : NextStartColumn + Indent);
1072       }
1073
1074       NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1075       unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine);
1076       bool FitsIntoOneLine =
1077           TheLine.Last->TotalLength + Indent <= ColumnLimit ||
1078           (TheLine.Type == LT_ImportStatement &&
1079            (Style.Language != FormatStyle::LK_JavaScript ||
1080             !Style.JavaScriptWrapImports));
1081       if (Style.ColumnLimit == 0)
1082         NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)
1083             .formatLine(TheLine, NextStartColumn + Indent,
1084                         FirstLine ? FirstStartColumn : 0, DryRun);
1085       else if (FitsIntoOneLine)
1086         Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)
1087                        .formatLine(TheLine, NextStartColumn + Indent,
1088                                    FirstLine ? FirstStartColumn : 0, DryRun);
1089       else
1090         Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)
1091                        .formatLine(TheLine, NextStartColumn + Indent,
1092                                    FirstLine ? FirstStartColumn : 0, DryRun);
1093       RangeMinLevel = std::min(RangeMinLevel, TheLine.Level);
1094     } else {
1095       // If no token in the current line is affected, we still need to format
1096       // affected children.
1097       if (TheLine.ChildrenAffected)
1098         for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)
1099           if (!Tok->Children.empty())
1100             format(Tok->Children, DryRun);
1101
1102       // Adapt following lines on the current indent level to the same level
1103       // unless the current \c AnnotatedLine is not at the beginning of a line.
1104       bool StartsNewLine =
1105           TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;
1106       if (StartsNewLine)
1107         IndentTracker.adjustToUnmodifiedLine(TheLine);
1108       if (!DryRun) {
1109         bool ReformatLeadingWhitespace =
1110             StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||
1111                               TheLine.LeadingEmptyLinesAffected);
1112         // Format the first token.
1113         if (ReformatLeadingWhitespace)
1114           formatFirstToken(TheLine, PreviousLine, Lines,
1115                            TheLine.First->OriginalColumn,
1116                            TheLine.First->OriginalColumn);
1117         else
1118           Whitespaces->addUntouchableToken(*TheLine.First,
1119                                            TheLine.InPPDirective);
1120
1121         // Notify the WhitespaceManager about the unchanged whitespace.
1122         for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)
1123           Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
1124       }
1125       NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1126       RangeMinLevel = UINT_MAX;
1127     }
1128     if (!DryRun)
1129       markFinalized(TheLine.First);
1130     PreviousLine = &TheLine;
1131   }
1132   PenaltyCache[CacheKey] = Penalty;
1133   return Penalty;
1134 }
1135
1136 void UnwrappedLineFormatter::formatFirstToken(
1137     const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,
1138     const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,
1139     unsigned NewlineIndent) {
1140   FormatToken &RootToken = *Line.First;
1141   if (RootToken.is(tok::eof)) {
1142     unsigned Newlines = std::min(RootToken.NewlinesBefore, 1u);
1143     unsigned TokenIndent = Newlines ? NewlineIndent : 0;
1144     Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,
1145                                    TokenIndent);
1146     return;
1147   }
1148   unsigned Newlines =
1149       std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1150   // Remove empty lines before "}" where applicable.
1151   if (RootToken.is(tok::r_brace) &&
1152       (!RootToken.Next ||
1153        (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) &&
1154       // Do not remove empty lines before namespace closing "}".
1155       !getNamespaceToken(&Line, Lines))
1156     Newlines = std::min(Newlines, 1u);
1157   // Remove empty lines at the start of nested blocks (lambdas/arrow functions)
1158   if (PreviousLine == nullptr && Line.Level > 0)
1159     Newlines = std::min(Newlines, 1u);
1160   if (Newlines == 0 && !RootToken.IsFirst)
1161     Newlines = 1;
1162   if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1163     Newlines = 0;
1164
1165   // Remove empty lines after "{".
1166   if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1167       PreviousLine->Last->is(tok::l_brace) &&
1168       !PreviousLine->startsWithNamespace() &&
1169       !startsExternCBlock(*PreviousLine))
1170     Newlines = 1;
1171
1172   // Insert extra new line before access specifiers.
1173   if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1174       RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1175     ++Newlines;
1176
1177   // Remove empty lines after access specifiers.
1178   if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
1179       (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline))
1180     Newlines = std::min(1u, Newlines);
1181
1182   if (Newlines)
1183     Indent = NewlineIndent;
1184
1185   // Preprocessor directives get indented after the hash, if indented.
1186   if (Line.Type == LT_PreprocessorDirective || Line.Type == LT_ImportStatement)
1187     Indent = 0;
1188
1189   Whitespaces->replaceWhitespace(RootToken, Newlines, Indent, Indent,
1190                                  Line.InPPDirective &&
1191                                      !RootToken.HasUnescapedNewline);
1192 }
1193
1194 unsigned
1195 UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,
1196                                        const AnnotatedLine *NextLine) const {
1197   // In preprocessor directives reserve two chars for trailing " \" if the
1198   // next line continues the preprocessor directive.
1199   bool ContinuesPPDirective =
1200       InPPDirective &&
1201       // If there is no next line, this is likely a child line and the parent
1202       // continues the preprocessor directive.
1203       (!NextLine ||
1204        (NextLine->InPPDirective &&
1205         // If there is an unescaped newline between this line and the next, the
1206         // next line starts a new preprocessor directive.
1207         !NextLine->First->HasUnescapedNewline));
1208   return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);
1209 }
1210
1211 } // namespace format
1212 } // namespace clang