//===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

#include "UnwrappedLineFormatter.h"

#include "NamespaceEndCommentsFixer.h"

#include "WhitespaceManager.h"

#include "llvm/Support/Debug.h"

#include <queue>

#define DEBUG_TYPE "format-formatter"

namespace clang {

namespace format {

namespace {

bool startsExternCBlock(const AnnotatedLine &Line) {

  const FormatToken *Next = Line.First->getNextNonComment();

  const FormatToken *NextNext = Next ? 
Next->getNextNonComment()4.55k
 : 
nullptr537
;

  return Line.startsWith(tok::kw_extern) && 
Next46
 && 
Next->isStringLiteral()46
 &&

         
NextNext46
 && 
NextNext->is(tok::l_brace)46
;

}

/// Tracks the indent level of \c AnnotatedLines across levels.

///

/// \c nextLine must be called for each \c AnnotatedLine, after which \c

/// getIndent() will return the indent for the last line \c nextLine was called

/// with.

/// If the line is not formatted (and thus the indent does not change), calling

/// \c adjustToUnmodifiedLine after the call to \c nextLine will cause

/// subsequent lines on the same level to be indented at the same level as the

/// given line.

class LevelIndentTracker {

public:

  LevelIndentTracker(const FormatStyle &Style,

                     const AdditionalKeywords &Keywords, unsigned StartLevel,

                     int AdditionalIndent)

      : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {

    for (unsigned i = 0; i != StartLevel; 
++i2.04k
)

      IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);

  }

  /// Returns the indent for the current line.

  unsigned getIndent() const { return Indent; }

  /// Update the indent state given that \p Line is going to be formatted

  /// next.

  void nextLine(const AnnotatedLine &Line) {

    Offset = getIndentOffset(*Line.First);

    // Update the indent level cache size so that we can rely on it

    // having the right size in adjustToUnmodifiedline.

    while (IndentForLevel.size() <= Line.Level)

      IndentForLevel.push_back(-1);

    if (Line.InPPDirective) {

      unsigned IndentWidth =

          (Style.PPIndentWidth >= 0) ? 
Style.PPIndentWidth27
 : 
Style.IndentWidth4.38k
;

      Indent = Line.Level * IndentWidth + AdditionalIndent;

    } else {

      IndentForLevel.resize(Line.Level + 1);

      Indent = getIndent(Line.Level);

    }

    if (static_cast<int>(Indent) + Offset >= 0)

      Indent += Offset;

    if (Line.First->is(TT_CSharpGenericTypeConstraint))

      Indent = Line.Level * Style.IndentWidth + Style.ContinuationIndentWidth;

  }

  /// Update the indent state given that \p Line indent should be

  /// skipped.

  void skipLine(const AnnotatedLine &Line) {

    while (IndentForLevel.size() <= Line.Level)

      IndentForLevel.push_back(Indent);

  }

  /// Update the level indent to adapt to the given \p Line.

  ///

  /// When a line is not formatted, we move the subsequent lines on the same

  /// level to the same indent.

  /// Note that \c nextLine must have been called before this method.

  void adjustToUnmodifiedLine(const AnnotatedLine &Line) {

    unsigned LevelIndent = Line.First->OriginalColumn;

    if (static_cast<int>(LevelIndent) - Offset >= 0)

      LevelIndent -= Offset;

    if ((!Line.First->is(tok::comment) || 
IndentForLevel[Line.Level] == -19
) &&

        
!Line.InPPDirective5.18k
)

      IndentForLevel[Line.Level] = LevelIndent;

  }

private:

  /// Get the offset of the line relatively to the level.

  ///

  /// For example, 'public:' labels in classes are offset by 1 or 2

  /// characters to the left from their level.

  int getIndentOffset(const FormatToken &RootToken) {

    if (Style.Language == FormatStyle::LK_Java || 
Style.isJavaScript()73.3k
 ||

        
Style.isCSharp()68.7k
)

      return 0;

    if (RootToken.isAccessSpecifier(false) ||

        
RootToken.isObjCAccessSpecifier()65.5k
 ||

        
(65.4k
RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals)65.4k
 &&

         
RootToken.Next15
 && 
RootToken.Next->is(tok::colon)15
)) {

      // The AccessModifierOffset may be overridden by IndentAccessModifiers,

      // in which case we take a negative value of the IndentWidth to simulate

      // the upper indent level.

      return Style.IndentAccessModifiers ? 
-Style.IndentWidth15

                                         : 
Style.AccessModifierOffset705
;

    }

    return 0;

  }

  /// Get the indent of \p Level from \p IndentForLevel.

  ///

  /// \p IndentForLevel must contain the indent for the level \c l

  /// at \p IndentForLevel[l], or a value < 0 if the indent for

  /// that level is unknown.

  unsigned getIndent(unsigned Level) const {

    if (IndentForLevel[Level] != -1)

      return IndentForLevel[Level];

    if (Level == 0)

      return 0;

    return getIndent(Level - 1) + Style.IndentWidth;

  }

  const FormatStyle &Style;

  const AdditionalKeywords &Keywords;

  const unsigned AdditionalIndent;

  /// The indent in characters for each level.

  std::vector<int> IndentForLevel;

  /// Offset of the current line relative to the indent level.

  ///

  /// For example, the 'public' keywords is often indented with a negative

  /// offset.

  int Offset = 0;

  /// The current line's indent.

  unsigned Indent = 0;

};

const FormatToken *getMatchingNamespaceToken(

    const AnnotatedLine *Line,

    const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {

  if (!Line->startsWith(tok::r_brace))

    return nullptr;

  size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex;

  if (StartLineIndex == UnwrappedLine::kInvalidIndex)

    return nullptr;

  assert(StartLineIndex < AnnotatedLines.size());

  return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();

}

StringRef getNamespaceTokenText(const AnnotatedLine *Line) {

  const FormatToken *NamespaceToken = Line->First->getNamespaceToken();

  return NamespaceToken ? 
NamespaceToken->TokenText30
 : 
StringRef()29
;

}

StringRef getMatchingNamespaceTokenText(

    const AnnotatedLine *Line,

    const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {

  const FormatToken *NamespaceToken =

      getMatchingNamespaceToken(Line, AnnotatedLines);

  return NamespaceToken ? 
NamespaceToken->TokenText25
 : 
StringRef()22
;

}

class LineJoiner {

public:

  LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords,

             const SmallVectorImpl<AnnotatedLine *> &Lines)

      : Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()),

        AnnotatedLines(Lines) {}

  /// Returns the next line, merging multiple lines into one if possible.

  const AnnotatedLine *getNextMergedLine(bool DryRun,

                                         LevelIndentTracker &IndentTracker) {

    if (Next == End)

      return nullptr;

    const AnnotatedLine *Current = *Next;

    IndentTracker.nextLine(*Current);

    unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next, End);

    if (MergedLines > 0 && 
Style.ColumnLimit == 05.27k
)

      // Disallow line merging if there is a break at the start of one of the

      // input lines.

      
for (unsigned i = 0; 42
i < MergedLines; 
++i55
)

        if (Next[i + 1]->First->NewlinesBefore > 0)

          MergedLines = 0;

    if (!DryRun)

      
for (unsigned i = 0; 72.3k
i < MergedLines; 
++i6.82k
)

        join(*Next[0], *Next[i + 1]);

    Next = Next + MergedLines + 1;

    return Current;

  }

private:

  /// Calculates how many lines can be merged into 1 starting at \p I.

  unsigned

  tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,

                           SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                           SmallVectorImpl<AnnotatedLine *>::const_iterator E) {

    const unsigned Indent = IndentTracker.getIndent();

    // Can't join the last line with anything.

    if (I + 1 == E)

      return 0;

    // We can never merge stuff if there are trailing line comments.

    const AnnotatedLine *TheLine = *I;

    if (TheLine->Last->is(TT_LineComment))

      return 0;

    if (I[1]->Type == LT_Invalid || 
I[1]->First->MustBreakBefore49.1k
)

      return 0;

    if (TheLine->InPPDirective &&

        
(3.27k
!I[1]->InPPDirective3.27k
 || 
I[1]->First->HasUnescapedNewline1.85k
))

      return 0;

    if (Style.ColumnLimit > 0 && 
Indent > Style.ColumnLimit44.6k
)

      return 0;

    unsigned Limit =

        Style.ColumnLimit == 0 ? UINT_MAX : 
Style.ColumnLimit - Indent44.6k
;

    // If we already exceed the column limit, we set 'Limit' to 0. The different

    // tryMerge..() functions can then decide whether to still do merging.

    Limit = TheLine->Last->TotalLength > Limit

                ? 
05.72k

                : 
Limit - TheLine->Last->TotalLength40.1k
;

    if (TheLine->Last->is(TT_FunctionLBrace) &&

        
TheLine->First == TheLine->Last4.68k
 &&

        
!Style.BraceWrapping.SplitEmptyFunction462
 &&

        
I[1]->First->is(tok::r_brace)27
)

      return tryMergeSimpleBlock(I, E, Limit);

    // Handle empty record blocks where the brace has already been wrapped

    if (TheLine->Last->is(tok::l_brace) && 
TheLine->First == TheLine->Last11.5k
 &&

        
I != AnnotatedLines.begin()1.37k
) {

      bool EmptyBlock = I[1]->First->is(tok::r_brace);

      const FormatToken *Tok = I[-1]->First;

      if (Tok && Tok->is(tok::comment))

        Tok = Tok->getNextNonComment();

      if (Tok && 
Tok->getNamespaceToken()1.24k
)

        return !Style.BraceWrapping.SplitEmptyNamespace && 
EmptyBlock18

                   ? 
tryMergeSimpleBlock(I, E, Limit)15

                   : 
065
;

      if (Tok && 
Tok->is(tok::kw_typedef)1.16k
)

        Tok = Tok->getNextNonComment();

      if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union,

                              tok::kw_extern, Keywords.kw_interface))

        return !Style.BraceWrapping.SplitEmptyRecord && 
EmptyBlock60

                   ? 
tryMergeSimpleBlock(I, E, Limit)30

                   : 
0129
;

      if (Tok && 
Tok->is(tok::kw_template)1.00k
 &&

          
Style.BraceWrapping.SplitEmptyRecord66
 && 
EmptyBlock60
) {

        return 0;

      }

    }

    auto ShouldMergeShortFunctions =

        [this, B = AnnotatedLines.begin()](

            SmallVectorImpl<AnnotatedLine *>::const_iterator I) {

          if (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All)

            return true;

          if (Style.AllowShortFunctionsOnASingleLine >=

                  FormatStyle::SFS_Empty &&

              
I[1]->First->is(tok::r_brace)5.99k
)

            return true;

          if (Style.AllowShortFunctionsOnASingleLine &

              FormatStyle::SFS_InlineOnly) {

            // Just checking TheLine->Level != 0 is not enough, because it

            // provokes treating functions inside indented namespaces as short.

            if ((*I)->Level != 0) {

              if (I == B)

                return false;

              // TODO: Use IndentTracker to avoid loop?

              // Find the last line with lower level.

              auto J = I - 1;

              for (; J != B; 
--J12
)

                if ((*J)->Level < (*I)->Level)

                  break;

              // Check if the found line starts a record.

              auto *RecordTok = (*J)->First;

              while (RecordTok) {

                // TODO: Refactor to isRecord(RecordTok).

                if (RecordTok->isOneOf(tok::kw_class, tok::kw_struct))

                  return true;

                if (Style.isCpp() && 
RecordTok->is(tok::kw_union)126
)

                  return true;

                if (Style.isCSharp() && 
RecordTok->is(Keywords.kw_interface)16
)

                  return true;

                if (Style.Language == FormatStyle::LK_Java &&

                    
RecordTok->is(tok::kw_enum)6
)

                  return true;

                if (Style.isJavaScript() && 
RecordTok->is(Keywords.kw_function)2
)

                  return true;

                RecordTok = RecordTok->Next;

              }

              return false;

            }

          }

          return false;

        };

    bool MergeShortFunctions = ShouldMergeShortFunctions(I);

    if (Style.CompactNamespaces) {

      if (auto nsToken = TheLine->First->getNamespaceToken()) {

        int i = 0;

        unsigned closingLine = TheLine->MatchingClosingBlockLineIndex - 1;

        for (; I + 1 + i != E &&

               nsToken->TokenText == getNamespaceTokenText(I[i + 1]) &&

               
closingLine == I[i + 1]->MatchingClosingBlockLineIndex27
 &&

               
I[i + 1]->Last->TotalLength < Limit25
;

             
i++, closingLine--23
) {

          // No extra indent for compacted namespaces

          IndentTracker.skipLine(*I[i + 1]);

          Limit -= I[i + 1]->Last->TotalLength;

        }

        return i;

      }

      if (auto nsToken = getMatchingNamespaceToken(TheLine, AnnotatedLines)) {

        int i = 0;

        unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;

        for (; I + 1 + i != E &&

               nsToken->TokenText ==

                   getMatchingNamespaceTokenText(I[i + 1], AnnotatedLines) &&

               
openingLine == I[i + 1]->MatchingOpeningBlockLineIndex25
;

             i++, openingLine--) {

          // No space between consecutive braces

          I[i + 1]->First->SpacesRequiredBefore = !I[i]->Last->is(tok::r_brace);

          // Indent like the outer-most namespace

          IndentTracker.nextLine(*I[i + 1]);

        }

        return i;

      }

    }

    // Try to merge a function block with left brace unwrapped

    if (TheLine->Last->is(TT_FunctionLBrace) &&

        
TheLine->First != TheLine->Last4.66k
) {

      return MergeShortFunctions ? 
tryMergeSimpleBlock(I, E, Limit)3.83k
 : 
0387
;

    }

    // Try to merge a control statement block with left brace unwrapped

    if (TheLine->Last->is(tok::l_brace) && 
TheLine->First != TheLine->Last7.02k
 &&

        TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for,

                                TT_ForEachMacro)) {

      return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never

                 ? 
tryMergeSimpleBlock(I, E, Limit)137

                 : 
0909
;

    }

    // Try to merge a control statement block with left brace wrapped

    if (I[1]->First->is(tok::l_brace) &&

        
(1.41k
TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,

                                 tok::kw_for, tok::kw_switch, tok::kw_try,

                                 tok::kw_do, TT_ForEachMacro) ||

         
(1.07k
TheLine->First->is(tok::r_brace)1.07k
 && 
TheLine->First->Next31
 &&

          
TheLine->First->Next->isOneOf(tok::kw_else, tok::kw_catch)31
)) &&

        Style.BraceWrapping.AfterControlStatement ==

            FormatStyle::BWACS_MultiLine) {

      // If possible, merge the next line's wrapped left brace with the current

      // line. Otherwise, leave it on the next line, as this is a multi-line

      // control statement.

      return (Style.ColumnLimit == 0 ||

              TheLine->Last->TotalLength <= Style.ColumnLimit)

                 ? 
124

                 : 
010
;

    } else if (I[1]->First->is(tok::l_brace) &&

               TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,

                                       tok::kw_for, TT_ForEachMacro)) {

      return (Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always)

                 ? tryMergeSimpleBlock(I, E, Limit)

                 : 
00
;

    } else if (I[1]->First->is(tok::l_brace) &&

               
TheLine->First->isOneOf(tok::kw_else, tok::kw_catch)1.12k
 &&

               Style.BraceWrapping.AfterControlStatement ==

                   FormatStyle::BWACS_MultiLine) {

      // This case if different from the upper BWACS_MultiLine processing

      // in that a preceding r_brace is not on the same line as else/catch

      // most likely because of BeforeElse/BeforeCatch set to true.

      // If the line length doesn't fit ColumnLimit, leave l_brace on the

      // next line to respect the BWACS_MultiLine.

      return (Style.ColumnLimit == 0 ||

              TheLine->Last->TotalLength <= Style.ColumnLimit)

                 ? 1

                 : 
00
;

    }

    // Don't merge block with left brace wrapped after ObjC special blocks

    if (TheLine->First->is(tok::l_brace) && 
I != AnnotatedLines.begin()1.14k
 &&

        
I[-1]->First->is(tok::at)1.01k
 && 
I[-1]->First->Next17
) {

      tok::ObjCKeywordKind kwId = I[-1]->First->Next->Tok.getObjCKeywordID();

      if (kwId == clang::tok::objc_autoreleasepool ||

          
kwId == clang::tok::objc_synchronized13
)

        return 0;

    }

    // Don't merge block with left brace wrapped after case labels

    if (TheLine->First->is(tok::l_brace) && 
I != AnnotatedLines.begin()1.13k
 &&

        
I[-1]->First->isOneOf(tok::kw_case, tok::kw_default)1.00k
)

      return 0;

    // Don't merge an empty template class or struct if SplitEmptyRecords

    // is defined.

    if (Style.BraceWrapping.SplitEmptyRecord &&

        
TheLine->Last->is(tok::l_brace)39.3k
 && 
I != AnnotatedLines.begin()5.80k
 &&

        
I[-1]->Last3.82k
) {

      const FormatToken *Previous = I[-1]->Last;

      if (Previous) {

        if (Previous->is(tok::comment))

          Previous = Previous->getPreviousNonComment();

        if (Previous) {

          if (Previous->is(tok::greater) && 
!I[-1]->InPPDirective24
)

            return 0;

          if (Previous->is(tok::identifier)) {

            const FormatToken *PreviousPrevious =

                Previous->getPreviousNonComment();

            if (PreviousPrevious &&

                
PreviousPrevious->isOneOf(tok::kw_class, tok::kw_struct)291
)

              return 0;

          }

        }

      }

    }

    // Try to merge a block with left brace unwrapped that wasn't yet covered

    if (TheLine->Last->is(tok::l_brace)) {

      const FormatToken *Tok = TheLine->First;

      bool ShouldMerge = false;

      if (Tok->is(tok::kw_typedef)) {

        Tok = Tok->getNextNonComment();

        assert(Tok);

      }

      if (Tok->isOneOf(tok::kw_class, tok::kw_struct)) {

        ShouldMerge = !Style.BraceWrapping.AfterClass ||

                      
(6
I[1]->First->is(tok::r_brace)6
 &&

                       
!Style.BraceWrapping.SplitEmptyRecord0
);

      } else if (Tok->is(tok::kw_enum)) {

        ShouldMerge = Style.AllowShortEnumsOnASingleLine;

      } else {

        ShouldMerge = !Style.BraceWrapping.AfterFunction ||

                      
(847
I[1]->First->is(tok::r_brace)847
 &&

                       
!Style.BraceWrapping.SplitEmptyFunction133
);

      }

      return ShouldMerge ? 
tryMergeSimpleBlock(I, E, Limit)4.98k
 : 
0870
;

    }

    // Try to merge a function block with left brace wrapped

    if (I[1]->First->is(TT_FunctionLBrace) &&

        
Style.BraceWrapping.AfterFunction546
) {

      if (I[1]->Last->is(TT_LineComment))

        return 0;

      // Check for Limit <= 2 to account for the " {".

      if (Limit <= 2 || 
(464
Style.ColumnLimit == 0464
 && 
containsMustBreak(TheLine)97
))

        return 0;

      Limit -= 2;

      unsigned MergedLines = 0;

      if (MergeShortFunctions ||

          
(242
Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty242
 &&

           
I[1]->First == I[1]->Last90
 && 
I + 2 != E90
 &&

           
I[2]->First->is(tok::r_brace)90
)) {

        MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);

        // If we managed to merge the block, count the function header, which is

        // on a separate line.

        if (MergedLines > 0)

          ++MergedLines;

      }

      return MergedLines;

    }

    auto IsElseLine = [&TheLine]() -> bool {

      const FormatToken *First = TheLine->First;

      if (First->is(tok::kw_else))

        return true;

      return First->is(tok::r_brace) && 
First->Next6.19k
 &&

             
First->Next->is(tok::kw_else)1.85k
;

    };

    if (TheLine->First->is(tok::kw_if) ||

        
(32.6k
IsElseLine()32.6k
 && (Style.AllowShortIfStatementsOnASingleLine ==

                          FormatStyle::SIS_AllIfsAndElse))) {

      return Style.AllowShortIfStatementsOnASingleLine

                 ? 
tryMergeSimpleControlStatement(I, E, Limit)536

                 : 
0359
;

    }

    if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while, tok::kw_do,

                                TT_ForEachMacro)) {

      return Style.AllowShortLoopsOnASingleLine

                 ? 
tryMergeSimpleControlStatement(I, E, Limit)91

                 : 
0336
;

    }

    if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {

      return Style.AllowShortCaseLabelsOnASingleLine

                 ? 
tryMergeShortCaseLabels(I, E, Limit)87

                 : 
0256
;

    }

    if (TheLine->InPPDirective &&

        
(1.09k
TheLine->First->HasUnescapedNewline1.09k
 || 
TheLine->First->IsFirst621
)) {

      return tryMergeSimplePPDirective(I, E, Limit);

    }

    return 0;

  }

  unsigned

  tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                            SmallVectorImpl<AnnotatedLine *>::const_iterator E,

                            unsigned Limit) {

    if (Limit == 0)

      return 0;

    if (I + 2 != E && I[2]->InPPDirective && 
!I[2]->First->HasUnescapedNewline388
)

      return 0;

    if (1 + I[1]->Last->TotalLength > Limit)

      return 0;

    return 1;

  }

  unsigned tryMergeSimpleControlStatement(

      SmallVectorImpl<AnnotatedLine *>::const_iterator I,

      SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {

    if (Limit == 0)

      return 0;

    if (Style.BraceWrapping.AfterControlStatement ==

            FormatStyle::BWACS_Always &&

        
I[1]->First->is(tok::l_brace)12
 &&

        
Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never0
)

      return 0;

    if (I[1]->InPPDirective != (*I)->InPPDirective ||

        
(614
I[1]->InPPDirective614
 && 
I[1]->First->HasUnescapedNewline21
))

      return 0;

    Limit = limitConsideringMacros(I + 1, E, Limit);

    AnnotatedLine &Line = **I;

    if (!Line.First->is(tok::kw_do) && 
!Line.First->is(tok::kw_else)605
 &&

        
!Line.Last->is(tok::kw_else)515
 && 
Line.Last->isNot(tok::r_paren)488
)

      return 0;

    // Only merge `do while` if `do` is the only statement on the line.

    if (Line.First->is(tok::kw_do) && 
!Line.Last->is(tok::kw_do)9
)

      return 0;

    if (1 + I[1]->Last->TotalLength > Limit)

      return 0;

    // Don't merge with loops, ifs, a single semicolon or a line comment.

    if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,

                             TT_ForEachMacro, TT_LineComment))

      return 0;

    // Only inline simple if's (no nested if or else), unless specified

    if (Style.AllowShortIfStatementsOnASingleLine ==

        FormatStyle::SIS_WithoutElse) {

      if (I + 2 != E && 
Line.startsWith(tok::kw_if)139
 &&

          
I[2]->First->is(tok::kw_else)135
)

        return 0;

    }

    return 1;

  }

  unsigned

  tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,

                          unsigned Limit) {

    if (Limit == 0 || I + 1 == E ||

        I[1]->First->isOneOf(tok::kw_case, tok::kw_default))

      return 0;

    if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))

      return 0;

    unsigned NumStmts = 0;

    unsigned Length = 0;

    bool EndsWithComment = false;

    bool InPPDirective = I[0]->InPPDirective;

    const unsigned Level = I[0]->Level;

    for (; NumStmts < 3; 
++NumStmts82
) {

      if (I + 1 + NumStmts == E)

        break;

      const AnnotatedLine *Line = I[1 + NumStmts];

      if (Line->InPPDirective != InPPDirective)

        break;

      if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))

        break;

      if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,

                               tok::kw_while) ||

          
EndsWithComment105
)

        return 0;

      if (Line->First->is(tok::comment)) {

        if (Level != Line->Level)

          return 0;

        SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;

        for (; J != E; 
++J0
) {

          Line = *J;

          if (Line->InPPDirective != InPPDirective)

            break;

          if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))

            break;

          if (Line->First->isNot(tok::comment) || Level != Line->Level)

            return 0;

        }

        break;

      }

      if (Line->Last->is(tok::comment))

        EndsWithComment = true;

      Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.

    }

    if (NumStmts == 0 || NumStmts == 3 || Length > Limit)

      return 0;

    return NumStmts;

  }

  unsigned

  tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                      SmallVectorImpl<AnnotatedLine *>::const_iterator E,

                      unsigned Limit) {

    AnnotatedLine &Line = **I;

    // Don't merge ObjC @ keywords and methods.

    // FIXME: If an option to allow short exception handling clauses on a single

    // line is added, change this to not return for @try and friends.

    if (Style.Language != FormatStyle::LK_Java &&

        
Line.First->isOneOf(tok::at, tok::minus, tok::plus)9.42k
)

      return 0;

    // Check that the current line allows merging. This depends on whether we

    // are in a control flow statements as well as several style flags.

    if (Line.First->is(tok::kw_case) ||

        
(9.36k
Line.First->Next9.36k
 && 
Line.First->Next->is(tok::kw_else)8.69k
))

      return 0;

    // default: in switch statement

    if (Line.First->is(tok::kw_default)) {

      const FormatToken *Tok = Line.First->getNextNonComment();

      if (Tok && Tok->is(tok::colon))

        return 0;

    }

    if (Line.First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while, tok::kw_do,

                            tok::kw_try, tok::kw___try, tok::kw_catch,

                            tok::kw___finally, tok::kw_for, TT_ForEachMacro,

                            tok::r_brace, Keywords.kw___except)) {

      if (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never)

        return 0;

      if (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Empty &&

          
!I[1]->First->is(tok::r_brace)40
)

        return 0;

      // Don't merge when we can't except the case when

      // the control statement block is empty

      if (!Style.AllowShortIfStatementsOnASingleLine &&

          
Line.First->isOneOf(tok::kw_if, tok::kw_else)103
 &&

          
!Style.BraceWrapping.AfterControlStatement48
 &&

          
!I[1]->First->is(tok::r_brace)30
)

        return 0;

      if (!Style.AllowShortIfStatementsOnASingleLine &&

          
Line.First->isOneOf(tok::kw_if, tok::kw_else)91
 &&

          Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always &&

          
I + 2 != E18
 && 
!I[2]->First->is(tok::r_brace)18
)

        return 0;

      if (!Style.AllowShortLoopsOnASingleLine &&

          Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,

                              TT_ForEachMacro) &&

          
!Style.BraceWrapping.AfterControlStatement44
 &&

          
!I[1]->First->is(tok::r_brace)26
)

        return 0;

      if (!Style.AllowShortLoopsOnASingleLine &&

          Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,

                              TT_ForEachMacro) &&

          Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always &&

          
I + 2 != E18
 && 
!I[2]->First->is(tok::r_brace)18
)

        return 0;

      // FIXME: Consider an option to allow short exception handling clauses on

      // a single line.

      // FIXME: This isn't covered by tests.

      // FIXME: For catch, __except, __finally the first token on the line

      // is '}', so this isn't correct here.

      if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,

                              Keywords.kw___except, tok::kw___finally))

        return 0;

    }

    if (Line.Last->is(tok::l_brace)) {

      FormatToken *Tok = I[1]->First;

      if (Tok->is(tok::r_brace) && 
!Tok->MustBreakBefore2.80k
 &&

          
(2.80k
Tok->getNextNonComment() == nullptr2.80k
 ||

           
Tok->getNextNonComment()->is(tok::semi)702
)) {

        // We merge empty blocks even if the line exceeds the column limit.

        Tok->SpacesRequiredBefore = Style.SpaceInEmptyBlock ? 
116
 : 
02.72k
;

        Tok->CanBreakBefore = true;

        return 1;

      } else if (Limit != 0 && 
!Line.startsWithNamespace()5.53k
 &&

                 
!startsExternCBlock(Line)4.40k
) {

        // We don't merge short records.

        FormatToken *RecordTok = Line.First;

        // Skip record modifiers.

        while (RecordTok->Next &&

               RecordTok->isOneOf(tok::kw_typedef, tok::kw_export,

                                  Keywords.kw_declare, Keywords.kw_abstract,

                                  tok::kw_default, Keywords.kw_override,

                                  tok::kw_public, tok::kw_private,

                                  tok::kw_protected, Keywords.kw_internal))

          RecordTok = RecordTok->Next;

        if (RecordTok &&

            RecordTok->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct,

                               Keywords.kw_interface))

          return 0;

        // Check that we still have three lines and they fit into the limit.

        if (I + 2 == E || 
I[2]->Type == LT_Invalid2.93k
)

          return 0;

        Limit = limitConsideringMacros(I + 2, E, Limit);

        if (!nextTwoLinesFitInto(I, Limit))

          return 0;

        // Second, check that the next line does not contain any braces - if it

        // does, readability declines when putting it into a single line.

        if (I[1]->Last->is(TT_LineComment))

          return 0;

        
do 2.29k
{

          if (Tok->is(tok::l_brace) && 
Tok->isNot(BK_BracedInit)195
)

            return 0;

          Tok = Tok->Next;

        } while (Tok);

        // Last, check that the third line starts with a closing brace.

        Tok = I[2]->First;

        if (Tok->isNot(tok::r_brace))

          return 0;

        // Don't merge "if (a) { .. } else {".

        if (Tok->Next && 
Tok->Next->is(tok::kw_else)166
)

          return 0;

        // Don't merge a trailing multi-line control statement block like:

        // } else if (foo &&

        //            bar)

        // { <-- current Line

        //   baz();

        // }

        if (Line.First == Line.Last && 
Line.First->isNot(TT_FunctionLBrace)174
 &&

            Style.BraceWrapping.AfterControlStatement ==

                FormatStyle::BWACS_MultiLine)

          return 0;

        return 2;

      }

    } else 
if (100
I[1]->First->is(tok::l_brace)100
) {

      if (I[1]->Last->is(TT_LineComment))

        return 0;

      // Check for Limit <= 2 to account for the " {".

      if (Limit <= 2 || (Style.ColumnLimit == 0 && 
containsMustBreak(*I)0
))

        return 0;

      Limit -= 2;

      unsigned MergedLines = 0;

      if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never ||

          
(0
I[1]->First == I[1]->Last0
 && 
I + 2 != E0
 &&

           
I[2]->First->is(tok::r_brace)0
)) {

        MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);

        // If we managed to merge the block, count the statement header, which

        // is on a separate line.

        if (MergedLines > 0)

          ++MergedLines;

      }

      return MergedLines;

    }

    return 0;

  }

  /// Returns the modified column limit for \p I if it is inside a macro and

  /// needs a trailing '\'.

  unsigned

  limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                         SmallVectorImpl<AnnotatedLine *>::const_iterator E,

                         unsigned Limit) {

    if (I[0]->InPPDirective && 
I + 1 != E82
 &&

        
!I[1]->First->HasUnescapedNewline82
 && 
!I[1]->First->is(tok::eof)63
) {

      return Limit < 2 ? 
00
 : Limit - 2;

    }

    return Limit;

  }

  bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,

                           unsigned Limit) {

    if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)

      return false;

    return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;

  }

  bool containsMustBreak(const AnnotatedLine *Line) {

    for (const FormatToken *Tok = Line->First; Tok; 
Tok = Tok->Next425
) {

      if (Tok->MustBreakBefore)

        return true;

    }

    return false;

  }

  void join(AnnotatedLine &A, const AnnotatedLine &B) {

    assert(!A.Last->Next);

    assert(!B.First->Previous);

    if (B.Affected)

      A.Affected = true;

    A.Last->Next = B.First;

    B.First->Previous = A.Last;

    B.First->CanBreakBefore = true;

    unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;

    for (FormatToken *Tok = B.First; Tok; 
Tok = Tok->Next17.8k
) {

      Tok->TotalLength += LengthA;

      A.Last = Tok;

    }

  }

  const FormatStyle &Style;

  const AdditionalKeywords &Keywords;

  const SmallVectorImpl<AnnotatedLine *>::const_iterator End;

  SmallVectorImpl<AnnotatedLine *>::const_iterator Next;

  const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;

};

static void markFinalized(FormatToken *Tok) {

  for (; Tok; 
Tok = Tok->Next352k
) {

    Tok->Finalized = true;

    for (AnnotatedLine *Child : Tok->Children)

      markFinalized(Child->First);

  }

}

#ifndef NDEBUG

static void printLineState(const LineState &State) {

  llvm::dbgs() << "State: ";

  for (const ParenState &P : State.Stack) {

    llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"

                 << P.LastSpace << "|" << P.NestedBlockIndent << " ";

  }

  llvm::dbgs() << State.NextToken->TokenText << "\n";

}

#endif

/// Base class for classes that format one \c AnnotatedLine.

class LineFormatter {

public:

  LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,

                const FormatStyle &Style,

                UnwrappedLineFormatter *BlockFormatter)

      : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),

        BlockFormatter(BlockFormatter) {}

  virtual ~LineFormatter() {}

  /// Formats an \c AnnotatedLine and returns the penalty.

  ///

  /// If \p DryRun is \c false, directly applies the changes.

  virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,

                              unsigned FirstStartColumn, bool DryRun) = 0;

protected:

  /// If the \p State's next token is an r_brace closing a nested block,

  /// format the nested block before it.

  ///

  /// Returns \c true if all children could be placed successfully and adapts

  /// \p Penalty as well as \p State. If \p DryRun is false, also directly

  /// creates changes using \c Whitespaces.

  ///

  /// The crucial idea here is that children always get formatted upon

  /// encountering the closing brace right after the nested block. Now, if we

  /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is

  /// \c false), the entire block has to be kept on the same line (which is only

  /// possible if it fits on the line, only contains a single statement, etc.

  ///

  /// If \p NewLine is true, we format the nested block on separate lines, i.e.

  /// break after the "{", format all lines with correct indentation and the put

  /// the closing "}" on yet another new line.

  ///

  /// This enables us to keep the simple structure of the

  /// \c UnwrappedLineFormatter, where we only have two options for each token:

  /// break or don't break.

  bool formatChildren(LineState &State, bool NewLine, bool DryRun,

                      unsigned &Penalty) {

    const FormatToken *LBrace = State.NextToken->getPreviousNonComment();

    FormatToken &Previous = *State.NextToken->Previous;

    if (!LBrace || 
LBrace->isNot(tok::l_brace)1.04M
 || 
LBrace->isNot(BK_Block)26.0k
 ||

        
Previous.Children.size() == 010.0k
)

      // The previous token does not open a block. Nothing to do. We don't

      // assert so that we can simply call this function for all tokens.

      return true;

    if (NewLine) {

      const ParenState &P = State.Stack.back();

      int AdditionalIndent =

          P.Indent - Previous.Children[0]->Level * Style.IndentWidth;

      if (Style.LambdaBodyIndentation == FormatStyle::LBI_OuterScope &&

          
P.NestedBlockIndent == P.LastSpace76
) {

        if (State.NextToken->MatchingParen &&

            State.NextToken->MatchingParen->is(TT_LambdaLBrace)) {

          State.Stack.pop_back();

        }

        if (LBrace->is(TT_LambdaLBrace))

          AdditionalIndent = 0;

      }

      Penalty +=

          BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,

                                 /*FixBadIndentation=*/true);

      return true;

    }

    if (Previous.Children[0]->First->MustBreakBefore)

      return false;

    // Cannot merge into one line if this line ends on a comment.

    if (Previous.is(tok::comment))

      return false;

    // Cannot merge multiple statements into a single line.

    if (Previous.Children.size() > 1)

      return false;

    const AnnotatedLine *Child = Previous.Children[0];

    // We can't put the closing "}" on a line with a trailing comment.

    if (Child->Last->isTrailingComment())

      return false;

    // If the child line exceeds the column limit, we wouldn't want to merge it.

    // We add +2 for the trailing " }".

    if (Style.ColumnLimit > 0 &&

        
Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit727
)

      return false;

    if (!DryRun) {

      Whitespaces->replaceWhitespace(

          *Child->First, /*Newlines=*/0, /*Spaces=*/1,

          /*StartOfTokenColumn=*/State.Column, /*IsAligned=*/false,

          State.Line->InPPDirective);

    }

    Penalty +=

        formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);

    State.Column += 1 + Child->Last->TotalLength;

    return true;

  }

  ContinuationIndenter *Indenter;

private:

  WhitespaceManager *Whitespaces;

  const FormatStyle &Style;

  UnwrappedLineFormatter *BlockFormatter;

};

/// Formatter that keeps the existing line breaks.

class NoColumnLimitLineFormatter : public LineFormatter {

public:

  NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,

                             WhitespaceManager *Whitespaces,

                             const FormatStyle &Style,

                             UnwrappedLineFormatter *BlockFormatter)

      : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}

  /// Formats the line, simply keeping all of the input's line breaking

  /// decisions.

  unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,

                      unsigned FirstStartColumn, bool DryRun) override {

    assert(!DryRun);

    LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,

                                                &Line, /*DryRun=*/false);

    while (State.NextToken) {

      bool Newline =

          Indenter->mustBreak(State) ||

          
(3.91k
Indenter->canBreak(State)3.91k
 && 
State.NextToken->NewlinesBefore > 01.10k
);

      unsigned Penalty = 0;

      formatChildren(State, Newline, /*DryRun=*/false, Penalty);

      Indenter->addTokenToState(State, Newline, /*DryRun=*/false);

    }

    return 0;

  }

};

/// Formatter that puts all tokens into a single line without breaks.

class NoLineBreakFormatter : public LineFormatter {

public: