Home | History | Annotate | Download | only in Format 
      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 "UnwrappedLineFormatter.h"
     11 #include "WhitespaceManager.h"
     12 #include "llvm/Support/Debug.h"
     13 
     14 #define DEBUG_TYPE "format-formatter"
     15 
     16 namespace clang {
     17 namespace format {
     18 
     19 namespace {
     20 
     21 bool startsExternCBlock(const AnnotatedLine &Line) {
     22   const FormatToken *Next = Line.First->getNextNonComment();
     23   const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;
     24   return Line.First->is(tok::kw_extern) && Next && Next->isStringLiteral() &&
     25          NextNext && NextNext->is(tok::l_brace);
     26 }
     27 
     28 class LineJoiner {
     29 public:
     30   LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords)
     31       : Style(Style), Keywords(Keywords) {}
     32 
     33   /// \brief Calculates how many lines can be merged into 1 starting at \p I.
     34   unsigned
     35   tryFitMultipleLinesInOne(unsigned Indent,
     36                            SmallVectorImpl<AnnotatedLine *>::const_iterator I,
     37                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
     38     // Can't join the last line with anything.
     39     if (I + 1 == E)
     40       return 0;
     41     // We can never merge stuff if there are trailing line comments.
     42     const AnnotatedLine *TheLine = *I;
     43     if (TheLine->Last->is(TT_LineComment))
     44       return 0;
     45     if (I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
     46       return 0;
     47     if (TheLine->InPPDirective &&
     48         (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline))
     49       return 0;
     50 
     51     if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
     52       return 0;
     53 
     54     unsigned Limit =
     55         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
     56     // If we already exceed the column limit, we set 'Limit' to 0. The different
     57     // tryMerge..() functions can then decide whether to still do merging.
     58     Limit = TheLine->Last->TotalLength > Limit
     59                 ? 0
     60                 : Limit - TheLine->Last->TotalLength;
     61 
     62     // FIXME: TheLine->Level != 0 might or might not be the right check to do.
     63     // If necessary, change to something smarter.
     64     bool MergeShortFunctions =
     65         Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
     66         (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Empty &&
     67          I[1]->First->is(tok::r_brace)) ||
     68         (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Inline &&
     69          TheLine->Level != 0);
     70 
     71     if (TheLine->Last->is(TT_FunctionLBrace) &&
     72         TheLine->First != TheLine->Last) {
     73       return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
     74     }
     75     if (TheLine->Last->is(tok::l_brace)) {
     76       return Style.BreakBeforeBraces == FormatStyle::BS_Attach
     77                  ? tryMergeSimpleBlock(I, E, Limit)
     78                  : 0;
     79     }
     80     if (I[1]->First->is(TT_FunctionLBrace) &&
     81         Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
     82       if (I[1]->Last->is(TT_LineComment))
     83         return 0;
     84 
     85       // Check for Limit <= 2 to account for the " {".
     86       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
     87         return 0;
     88       Limit -= 2;
     89 
     90       unsigned MergedLines = 0;
     91       if (MergeShortFunctions) {
     92         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
     93         // If we managed to merge the block, count the function header, which is
     94         // on a separate line.
     95         if (MergedLines > 0)
     96           ++MergedLines;
     97       }
     98       return MergedLines;
     99     }
    100     if (TheLine->First->is(tok::kw_if)) {
    101       return Style.AllowShortIfStatementsOnASingleLine
    102                  ? tryMergeSimpleControlStatement(I, E, Limit)
    103                  : 0;
    104     }
    105     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
    106       return Style.AllowShortLoopsOnASingleLine
    107                  ? tryMergeSimpleControlStatement(I, E, Limit)
    108                  : 0;
    109     }
    110     if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
    111       return Style.AllowShortCaseLabelsOnASingleLine
    112                  ? tryMergeShortCaseLabels(I, E, Limit)
    113                  : 0;
    114     }
    115     if (TheLine->InPPDirective &&
    116         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
    117       return tryMergeSimplePPDirective(I, E, Limit);
    118     }
    119     return 0;
    120   }
    121 
    122 private:
    123   unsigned
    124   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    125                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
    126                             unsigned Limit) {
    127     if (Limit == 0)
    128       return 0;
    129     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
    130       return 0;
    131     if (1 + I[1]->Last->TotalLength > Limit)
    132       return 0;
    133     return 1;
    134   }
    135 
    136   unsigned tryMergeSimpleControlStatement(
    137       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    138       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
    139     if (Limit == 0)
    140       return 0;
    141     if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
    142          Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
    143         (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
    144       return 0;
    145     if (I[1]->InPPDirective != (*I)->InPPDirective ||
    146         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
    147       return 0;
    148     Limit = limitConsideringMacros(I + 1, E, Limit);
    149     AnnotatedLine &Line = **I;
    150     if (Line.Last->isNot(tok::r_paren))
    151       return 0;
    152     if (1 + I[1]->Last->TotalLength > Limit)
    153       return 0;
    154     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
    155                              tok::kw_while, TT_LineComment))
    156       return 0;
    157     // Only inline simple if's (no nested if or else).
    158     if (I + 2 != E && Line.First->is(tok::kw_if) &&
    159         I[2]->First->is(tok::kw_else))
    160       return 0;
    161     return 1;
    162   }
    163 
    164   unsigned tryMergeShortCaseLabels(
    165       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    166       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
    167     if (Limit == 0 || I + 1 == E ||
    168         I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
    169       return 0;
    170     unsigned NumStmts = 0;
    171     unsigned Length = 0;
    172     bool InPPDirective = I[0]->InPPDirective;
    173     for (; NumStmts < 3; ++NumStmts) {
    174       if (I + 1 + NumStmts == E)
    175         break;
    176       const AnnotatedLine *Line = I[1 + NumStmts];
    177       if (Line->InPPDirective != InPPDirective)
    178         break;
    179       if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
    180         break;
    181       if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
    182                                tok::kw_while, tok::comment))
    183         return 0;
    184       Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
    185     }
    186     if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
    187       return 0;
    188     return NumStmts;
    189   }
    190 
    191   unsigned
    192   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    193                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
    194                       unsigned Limit) {
    195     AnnotatedLine &Line = **I;
    196 
    197     // Don't merge ObjC @ keywords and methods.
    198     // FIXME: If an option to allow short exception handling clauses on a single
    199     // line is added, change this to not return for @try and friends.
    200     if (Style.Language != FormatStyle::LK_Java &&
    201         Line.First->isOneOf(tok::at, tok::minus, tok::plus))
    202       return 0;
    203 
    204     // Check that the current line allows merging. This depends on whether we
    205     // are in a control flow statements as well as several style flags.
    206     if (Line.First->isOneOf(tok::kw_else, tok::kw_case))
    207       return 0;
    208     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
    209                             tok::kw___try, tok::kw_catch, tok::kw___finally,
    210                             tok::kw_for, tok::r_brace) ||
    211         Line.First->is(Keywords.kw___except)) {
    212       if (!Style.AllowShortBlocksOnASingleLine)
    213         return 0;
    214       if (!Style.AllowShortIfStatementsOnASingleLine &&
    215           Line.First->is(tok::kw_if))
    216         return 0;
    217       if (!Style.AllowShortLoopsOnASingleLine &&
    218           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for))
    219         return 0;
    220       // FIXME: Consider an option to allow short exception handling clauses on
    221       // a single line.
    222       // FIXME: This isn't covered by tests.
    223       // FIXME: For catch, __except, __finally the first token on the line
    224       // is '}', so this isn't correct here.
    225       if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
    226                               Keywords.kw___except, tok::kw___finally))
    227         return 0;
    228     }
    229 
    230     FormatToken *Tok = I[1]->First;
    231     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
    232         (Tok->getNextNonComment() == nullptr ||
    233          Tok->getNextNonComment()->is(tok::semi))) {
    234       // We merge empty blocks even if the line exceeds the column limit.
    235       Tok->SpacesRequiredBefore = 0;
    236       Tok->CanBreakBefore = true;
    237       return 1;
    238     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace) &&
    239                !startsExternCBlock(Line)) {
    240       // We don't merge short records.
    241       if (Line.First->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct))
    242         return 0;
    243 
    244       // Check that we still have three lines and they fit into the limit.
    245       if (I + 2 == E || I[2]->Type == LT_Invalid)
    246         return 0;
    247       Limit = limitConsideringMacros(I + 2, E, Limit);
    248 
    249       if (!nextTwoLinesFitInto(I, Limit))
    250         return 0;
    251 
    252       // Second, check that the next line does not contain any braces - if it
    253       // does, readability declines when putting it into a single line.
    254       if (I[1]->Last->is(TT_LineComment))
    255         return 0;
    256       do {
    257         if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
    258           return 0;
    259         Tok = Tok->Next;
    260       } while (Tok);
    261 
    262       // Last, check that the third line starts with a closing brace.
    263       Tok = I[2]->First;
    264       if (Tok->isNot(tok::r_brace))
    265         return 0;
    266 
    267       return 2;
    268     }
    269     return 0;
    270   }
    271 
    272   /// Returns the modified column limit for \p I if it is inside a macro and
    273   /// needs a trailing '\'.
    274   unsigned
    275   limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    276                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,
    277                          unsigned Limit) {
    278     if (I[0]->InPPDirective && I + 1 != E &&
    279         !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
    280       return Limit < 2 ? 0 : Limit - 2;
    281     }
    282     return Limit;
    283   }
    284 
    285   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
    286                            unsigned Limit) {
    287     if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
    288       return false;
    289     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
    290   }
    291 
    292   bool containsMustBreak(const AnnotatedLine *Line) {
    293     for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
    294       if (Tok->MustBreakBefore)
    295         return true;
    296     }
    297     return false;
    298   }
    299 
    300   const FormatStyle &Style;
    301   const AdditionalKeywords &Keywords;
    302 };
    303 
    304 class NoColumnLimitFormatter {
    305 public:
    306   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
    307 
    308   /// \brief Formats the line starting at \p State, simply keeping all of the
    309   /// input's line breaking decisions.
    310   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
    311     LineState State =
    312         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
    313     while (State.NextToken) {
    314       bool Newline =
    315           Indenter->mustBreak(State) ||
    316           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
    317       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
    318     }
    319   }
    320 
    321 private:
    322   ContinuationIndenter *Indenter;
    323 };
    324 
    325 
    326 static void markFinalized(FormatToken *Tok) {
    327   for (; Tok; Tok = Tok->Next) {
    328     Tok->Finalized = true;
    329     for (AnnotatedLine *Child : Tok->Children)
    330       markFinalized(Child->First);
    331   }
    332 }
    333 
    334 } // namespace
    335 
    336 unsigned
    337 UnwrappedLineFormatter::format(const SmallVectorImpl<AnnotatedLine *> &Lines,
    338                                bool DryRun, int AdditionalIndent,
    339                                bool FixBadIndentation) {
    340   LineJoiner Joiner(Style, Keywords);
    341 
    342   // Try to look up already computed penalty in DryRun-mode.
    343   std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
    344       &Lines, AdditionalIndent);
    345   auto CacheIt = PenaltyCache.find(CacheKey);
    346   if (DryRun && CacheIt != PenaltyCache.end())
    347     return CacheIt->second;
    348 
    349   assert(!Lines.empty());
    350   unsigned Penalty = 0;
    351   std::vector<int> IndentForLevel;
    352   for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
    353     IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
    354   const AnnotatedLine *PreviousLine = nullptr;
    355   for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
    356                                                         E = Lines.end();
    357        I != E; ++I) {
    358     const AnnotatedLine &TheLine = **I;
    359     const FormatToken *FirstTok = TheLine.First;
    360     int Offset = getIndentOffset(*FirstTok);
    361 
    362     // Determine indent and try to merge multiple unwrapped lines.
    363     unsigned Indent;
    364     if (TheLine.InPPDirective) {
    365       Indent = TheLine.Level * Style.IndentWidth;
    366     } else {
    367       while (IndentForLevel.size() <= TheLine.Level)
    368         IndentForLevel.push_back(-1);
    369       IndentForLevel.resize(TheLine.Level + 1);
    370       Indent = getIndent(IndentForLevel, TheLine.Level);
    371     }
    372     unsigned LevelIndent = Indent;
    373     if (static_cast<int>(Indent) + Offset >= 0)
    374       Indent += Offset;
    375 
    376     // Merge multiple lines if possible.
    377     unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
    378     if (MergedLines > 0 && Style.ColumnLimit == 0) {
    379       // Disallow line merging if there is a break at the start of one of the
    380       // input lines.
    381       for (unsigned i = 0; i < MergedLines; ++i) {
    382         if (I[i + 1]->First->NewlinesBefore > 0)
    383           MergedLines = 0;
    384       }
    385     }
    386     if (!DryRun) {
    387       for (unsigned i = 0; i < MergedLines; ++i) {
    388         join(*I[i], *I[i + 1]);
    389       }
    390     }
    391     I += MergedLines;
    392 
    393     bool FixIndentation =
    394         FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
    395     if (TheLine.First->is(tok::eof)) {
    396       if (PreviousLine && PreviousLine->Affected && !DryRun) {
    397         // Remove the file's trailing whitespace.
    398         unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
    399         Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
    400                                        /*IndentLevel=*/0, /*Spaces=*/0,
    401                                        /*TargetColumn=*/0);
    402       }
    403     } else if (TheLine.Type != LT_Invalid &&
    404                (TheLine.Affected || FixIndentation)) {
    405       if (FirstTok->WhitespaceRange.isValid()) {
    406         if (!DryRun)
    407           formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level, Indent,
    408                            TheLine.InPPDirective);
    409       } else {
    410         Indent = LevelIndent = FirstTok->OriginalColumn;
    411       }
    412 
    413       // If everything fits on a single line, just put it there.
    414       unsigned ColumnLimit = Style.ColumnLimit;
    415       if (I + 1 != E) {
    416         AnnotatedLine *NextLine = I[1];
    417         if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
    418           ColumnLimit = getColumnLimit(TheLine.InPPDirective);
    419       }
    420 
    421       if (TheLine.Last->TotalLength + Indent <= ColumnLimit ||
    422           TheLine.Type == LT_ImportStatement) {
    423         LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
    424         while (State.NextToken) {
    425           formatChildren(State, /*Newline=*/false, DryRun, Penalty);
    426           Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
    427         }
    428       } else if (Style.ColumnLimit == 0) {
    429         // FIXME: Implement nested blocks for ColumnLimit = 0.
    430         NoColumnLimitFormatter Formatter(Indenter);
    431         if (!DryRun)
    432           Formatter.format(Indent, &TheLine);
    433       } else {
    434         Penalty += format(TheLine, Indent, DryRun);
    435       }
    436 
    437       if (!TheLine.InPPDirective)
    438         IndentForLevel[TheLine.Level] = LevelIndent;
    439     } else if (TheLine.ChildrenAffected) {
    440       format(TheLine.Children, DryRun);
    441     } else {
    442       // Format the first token if necessary, and notify the WhitespaceManager
    443       // about the unchanged whitespace.
    444       for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
    445         if (Tok == TheLine.First && (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
    446           unsigned LevelIndent = Tok->OriginalColumn;
    447           if (!DryRun) {
    448             // Remove trailing whitespace of the previous line.
    449             if ((PreviousLine && PreviousLine->Affected) ||
    450                 TheLine.LeadingEmptyLinesAffected) {
    451               formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
    452                                TheLine.InPPDirective);
    453             } else {
    454               Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
    455             }
    456           }
    457 
    458           if (static_cast<int>(LevelIndent) - Offset >= 0)
    459             LevelIndent -= Offset;
    460           if (Tok->isNot(tok::comment) && !TheLine.InPPDirective)
    461             IndentForLevel[TheLine.Level] = LevelIndent;
    462         } else if (!DryRun) {
    463           Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
    464         }
    465       }
    466     }
    467     if (!DryRun)
    468       markFinalized(TheLine.First);
    469     PreviousLine = *I;
    470   }
    471   PenaltyCache[CacheKey] = Penalty;
    472   return Penalty;
    473 }
    474 
    475 unsigned UnwrappedLineFormatter::format(const AnnotatedLine &Line,
    476                                         unsigned FirstIndent, bool DryRun) {
    477   LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
    478 
    479   // If the ObjC method declaration does not fit on a line, we should format
    480   // it with one arg per line.
    481   if (State.Line->Type == LT_ObjCMethodDecl)
    482     State.Stack.back().BreakBeforeParameter = true;
    483 
    484   // Find best solution in solution space.
    485   return analyzeSolutionSpace(State, DryRun);
    486 }
    487 
    488 void UnwrappedLineFormatter::formatFirstToken(FormatToken &RootToken,
    489                                               const AnnotatedLine *PreviousLine,
    490                                               unsigned IndentLevel,
    491                                               unsigned Indent,
    492                                               bool InPPDirective) {
    493   unsigned Newlines =
    494       std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
    495   // Remove empty lines before "}" where applicable.
    496   if (RootToken.is(tok::r_brace) &&
    497       (!RootToken.Next ||
    498        (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
    499     Newlines = std::min(Newlines, 1u);
    500   if (Newlines == 0 && !RootToken.IsFirst)
    501     Newlines = 1;
    502   if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
    503     Newlines = 0;
    504 
    505   // Remove empty lines after "{".
    506   if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
    507       PreviousLine->Last->is(tok::l_brace) &&
    508       PreviousLine->First->isNot(tok::kw_namespace) &&
    509       !startsExternCBlock(*PreviousLine))
    510     Newlines = 1;
    511 
    512   // Insert extra new line before access specifiers.
    513   if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
    514       RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
    515     ++Newlines;
    516 
    517   // Remove empty lines after access specifiers.
    518   if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
    519       (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline))
    520     Newlines = std::min(1u, Newlines);
    521 
    522   Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
    523                                  Indent, InPPDirective &&
    524                                              !RootToken.HasUnescapedNewline);
    525 }
    526 
    527 /// \brief Get the indent of \p Level from \p IndentForLevel.
    528 ///
    529 /// \p IndentForLevel must contain the indent for the level \c l
    530 /// at \p IndentForLevel[l], or a value < 0 if the indent for
    531 /// that level is unknown.
    532 unsigned UnwrappedLineFormatter::getIndent(ArrayRef<int> IndentForLevel,
    533                                            unsigned Level) {
    534   if (IndentForLevel[Level] != -1)
    535     return IndentForLevel[Level];
    536   if (Level == 0)
    537     return 0;
    538   return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
    539 }
    540 
    541 void UnwrappedLineFormatter::join(AnnotatedLine &A, const AnnotatedLine &B) {
    542   assert(!A.Last->Next);
    543   assert(!B.First->Previous);
    544   if (B.Affected)
    545     A.Affected = true;
    546   A.Last->Next = B.First;
    547   B.First->Previous = A.Last;
    548   B.First->CanBreakBefore = true;
    549   unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
    550   for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
    551     Tok->TotalLength += LengthA;
    552     A.Last = Tok;
    553   }
    554 }
    555 
    556 unsigned UnwrappedLineFormatter::analyzeSolutionSpace(LineState &InitialState,
    557                                                       bool DryRun) {
    558   std::set<LineState *, CompareLineStatePointers> Seen;
    559 
    560   // Increasing count of \c StateNode items we have created. This is used to
    561   // create a deterministic order independent of the container.
    562   unsigned Count = 0;
    563   QueueType Queue;
    564 
    565   // Insert start element into queue.
    566   StateNode *Node =
    567       new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
    568   Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
    569   ++Count;
    570 
    571   unsigned Penalty = 0;
    572 
    573   // While not empty, take first element and follow edges.
    574   while (!Queue.empty()) {
    575     Penalty = Queue.top().first.first;
    576     StateNode *Node = Queue.top().second;
    577     if (!Node->State.NextToken) {
    578       DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
    579       break;
    580     }
    581     Queue.pop();
    582 
    583     // Cut off the analysis of certain solutions if the analysis gets too
    584     // complex. See description of IgnoreStackForComparison.
    585     if (Count > 10000)
    586       Node->State.IgnoreStackForComparison = true;
    587 
    588     if (!Seen.insert(&Node->State).second)
    589       // State already examined with lower penalty.
    590       continue;
    591 
    592     FormatDecision LastFormat = Node->State.NextToken->Decision;
    593     if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
    594       addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
    595     if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
    596       addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
    597   }
    598 
    599   if (Queue.empty()) {
    600     // We were unable to find a solution, do nothing.
    601     // FIXME: Add diagnostic?
    602     DEBUG(llvm::dbgs() << "Could not find a solution.\n");
    603     return 0;
    604   }
    605 
    606   // Reconstruct the solution.
    607   if (!DryRun)
    608     reconstructPath(InitialState, Queue.top().second);
    609 
    610   DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
    611   DEBUG(llvm::dbgs() << "---\n");
    612 
    613   return Penalty;
    614 }
    615 
    616 #ifndef NDEBUG
    617 static void printLineState(const LineState &State) {
    618   llvm::dbgs() << "State: ";
    619   for (const ParenState &P : State.Stack) {
    620     llvm::dbgs() << P.Indent << "|" << P.LastSpace << "|" << P.NestedBlockIndent
    621                  << " ";
    622   }
    623   llvm::dbgs() << State.NextToken->TokenText << "\n";
    624 }
    625 #endif
    626 
    627 void UnwrappedLineFormatter::reconstructPath(LineState &State,
    628                                              StateNode *Current) {
    629   std::deque<StateNode *> Path;
    630   // We do not need a break before the initial token.
    631   while (Current->Previous) {
    632     Path.push_front(Current);
    633     Current = Current->Previous;
    634   }
    635   for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
    636        I != E; ++I) {
    637     unsigned Penalty = 0;
    638     formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
    639     Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
    640 
    641     DEBUG({
    642       printLineState((*I)->Previous->State);
    643       if ((*I)->NewLine) {
    644         llvm::dbgs() << "Penalty for placing "
    645                      << (*I)->Previous->State.NextToken->Tok.getName() << ": "
    646                      << Penalty << "\n";
    647       }
    648     });
    649   }
    650 }
    651 
    652 void UnwrappedLineFormatter::addNextStateToQueue(unsigned Penalty,
    653                                                  StateNode *PreviousNode,
    654                                                  bool NewLine, unsigned *Count,
    655                                                  QueueType *Queue) {
    656   if (NewLine && !Indenter->canBreak(PreviousNode->State))
    657     return;
    658   if (!NewLine && Indenter->mustBreak(PreviousNode->State))
    659     return;
    660 
    661   StateNode *Node = new (Allocator.Allocate())
    662       StateNode(PreviousNode->State, NewLine, PreviousNode);
    663   if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
    664     return;
    665 
    666   Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
    667 
    668   Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
    669   ++(*Count);
    670 }
    671 
    672 bool UnwrappedLineFormatter::formatChildren(LineState &State, bool NewLine,
    673                                             bool DryRun, unsigned &Penalty) {
    674   const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
    675   FormatToken &Previous = *State.NextToken->Previous;
    676   if (!LBrace || LBrace->isNot(tok::l_brace) || LBrace->BlockKind != BK_Block ||
    677       Previous.Children.size() == 0)
    678     // The previous token does not open a block. Nothing to do. We don't
    679     // assert so that we can simply call this function for all tokens.
    680     return true;
    681 
    682   if (NewLine) {
    683     int AdditionalIndent = State.Stack.back().Indent -
    684                            Previous.Children[0]->Level * Style.IndentWidth;
    685 
    686     Penalty += format(Previous.Children, DryRun, AdditionalIndent,
    687                       /*FixBadIndentation=*/true);
    688     return true;
    689   }
    690 
    691   if (Previous.Children[0]->First->MustBreakBefore)
    692     return false;
    693 
    694   // Cannot merge multiple statements into a single line.
    695   if (Previous.Children.size() > 1)
    696     return false;
    697 
    698   // Cannot merge into one line if this line ends on a comment.
    699   if (Previous.is(tok::comment))
    700     return false;
    701 
    702   // We can't put the closing "}" on a line with a trailing comment.
    703   if (Previous.Children[0]->Last->isTrailingComment())
    704     return false;
    705 
    706   // If the child line exceeds the column limit, we wouldn't want to merge it.
    707   // We add +2 for the trailing " }".
    708   if (Style.ColumnLimit > 0 &&
    709       Previous.Children[0]->Last->TotalLength + State.Column + 2 >
    710           Style.ColumnLimit)
    711     return false;
    712 
    713   if (!DryRun) {
    714     Whitespaces->replaceWhitespace(
    715         *Previous.Children[0]->First,
    716         /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
    717         /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
    718   }
    719   Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
    720 
    721   State.Column += 1 + Previous.Children[0]->Last->TotalLength;
    722   return true;
    723 }
    724 
    725 } // namespace format
    726 } // namespace clang
    727