//===--- 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.20k
 : 
nullptr477
;

  return Line.startsWith(tok::kw_extern) && 
Next40
 && 
Next->isStringLiteral()40
 &&

         
NextNext40
 && 
NextNext->is(tok::l_brace)40
;

}

/// 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.03k
)

      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.IndentWidth3.81k
;

      Indent = Line.Level * IndentWidth + AdditionalIndent;

    } else {

      IndentForLevel.resize(Line.Level + 1);

      Indent = getIndent(IndentForLevel, 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.Language == FormatStyle::LK_JavaScript65.5k
 || 
Style.isCSharp()61.2k
)

      return 0;

    if (RootToken.isAccessSpecifier(false) ||

        
RootToken.isObjCAccessSpecifier()58.3k
 ||

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

         
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(ArrayRef<int> IndentForLevel, unsigned Level) {

    if (IndentForLevel[Level] != -1)

      return IndentForLevel[Level];

    if (Level == 0)

      return 0;

    return getIndent(IndentForLevel, 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->TokenText26
 : 
StringRef()25
;

}

StringRef getMatchingNamespaceTokenText(

    const AnnotatedLine *Line,

    const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {

  const FormatToken *NamespaceToken =

      getMatchingNamespaceToken(Line, AnnotatedLines);

  return NamespaceToken ? 
NamespaceToken->TokenText21
 : 
StringRef()18
;

}

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.04k
)

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

      // input lines.

      
for (unsigned i = 0; 39
i < MergedLines; 
++i52
)

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

          MergedLines = 0;

    if (!DryRun)

      
for (unsigned i = 0; 64.5k
i < MergedLines; 
++i6.53k
)

        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->MustBreakBefore43.9k
)

      return 0;

    if (TheLine->InPPDirective &&

        
(3.11k
!I[1]->InPPDirective3.11k
 || 
I[1]->First->HasUnescapedNewline1.76k
))

      return 0;

    if (Style.ColumnLimit > 0 && 
Indent > Style.ColumnLimit39.9k
)

      return 0;

    unsigned Limit =

        Style.ColumnLimit == 0 ? UINT_MAX : 
Style.ColumnLimit - Indent39.9k
;

    // 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.55k

                : 
Limit - TheLine->Last->TotalLength35.6k
;

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

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

        
!Style.BraceWrapping.SplitEmptyFunction430
 &&

        
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->Last10.6k
 &&

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

      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.14k
)

        return !Style.BraceWrapping.SplitEmptyNamespace && 
EmptyBlock18

                   ? 
tryMergeSimpleBlock(I, E, Limit)15

                   : 
048
;

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

        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

                   : 
0123
;

      if (Tok && 
Tok->is(tok::kw_template)926
 &&

          
Style.BraceWrapping.SplitEmptyRecord66
 && 
EmptyBlock60
) {

        return 0;

      }

    }

    // FIXME: TheLine->Level != 0 might or might not be the right check to do.

    // If necessary, change to something smarter.

    bool MergeShortFunctions =

        Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||

        
(6.97k
Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty6.97k
 &&

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

        
(5.89k
Style.AllowShortFunctionsOnASingleLine & FormatStyle::SFS_InlineOnly5.89k
 &&

         
TheLine->Level != 0281
);

    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]->MatchingClosingBlockLineIndex23
 &&

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

             
i++, closingLine--19
) {

          // 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]->MatchingOpeningBlockLineIndex21
;

             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.28k
) {

      return MergeShortFunctions ? 
tryMergeSimpleBlock(I, E, Limit)3.53k
 : 
0338
;

    }

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

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

        
TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)5.44k
) {

      return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never

                 ? 
tryMergeSimpleBlock(I, E, Limit)113

                 : 
0746
;

    }

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

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

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

                                 tok::kw_switch, tok::kw_try, tok::kw_do,

                                 TT_ForEachMacro) ||

         
(993
TheLine->First->is(tok::r_brace)993
 && 
TheLine->First->Next22
 &&

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

        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)

                 ? 
123

                 : 
09
;

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

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

                                       tok::kw_for)) {

      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.03k
 &&

               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)

                 ? 
12

                 : 
01
;

    }

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

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

        
I[-1]->First->is(tok::at)925
 && 
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.04k
 &&

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

      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)35.3k
 && 
I != AnnotatedLines.begin()5.48k
 &&

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

      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)269
)

              return 0;

          }

        }

      }

    }

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

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

      return !Style.BraceWrapping.AfterFunction ||

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

                      
!Style.BraceWrapping.SplitEmptyRecord117
)

                 ? 
tryMergeSimpleBlock(I, E, Limit)4.66k

                 : 
0860
;

    }

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

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

        
Style.BraceWrapping.AfterFunction511
) {

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

        return 0;

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

      if (Limit <= 2 || 
(440
Style.ColumnLimit == 0440
 && 
containsMustBreak(TheLine)97
))

        return 0;

      Limit -= 2;

      unsigned MergedLines = 0;

      if (MergeShortFunctions ||

          
(233
Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty233
 &&

           
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->Next5.58k
 &&

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

    };

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

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

                          FormatStyle::SIS_AllIfsAndElse))) {

      return Style.AllowShortIfStatementsOnASingleLine

                 ? 
tryMergeSimpleControlStatement(I, E, Limit)536

                 : 
0287
;

    }

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

      return Style.AllowShortLoopsOnASingleLine

                 ? 
tryMergeSimpleControlStatement(I, E, Limit)52

                 : 
0138
;

    }

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

      return Style.AllowShortCaseLabelsOnASingleLine

                 ? 
tryMergeShortCaseLabels(I, E, Limit)87

                 : 
0250
;

    }

    if (TheLine->InPPDirective &&

        
(1.03k
TheLine->First->HasUnescapedNewline1.03k
 || 
TheLine->First->IsFirst563
)) {

      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 ||

        
(575
I[1]->InPPDirective575
 && 
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)566
 &&

        
!Line.Last->is(tok::kw_else)476
 && 
Line.Last->isNot(tok::r_paren)449
)

      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;

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

                             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)8.73k
)

      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->isOneOf(tok::kw_else, tok::kw_case) ||

        
(8.49k
Line.First->Next8.49k
 && 
Line.First->Next->is(tok::kw_else)7.88k
))

      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_while, tok::kw_do, tok::kw_try,

                            tok::kw___try, tok::kw_catch, tok::kw___finally,

                            tok::kw_for, tok::r_brace, Keywords.kw___except)) {

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

        return 0;

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

      // the control statement block is empty

      if (!Style.AllowShortIfStatementsOnASingleLine &&

          
Line.startsWith(tok::kw_if)65
 &&

          
!Style.BraceWrapping.AfterControlStatement38
 &&

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

        return 0;

      if (!Style.AllowShortIfStatementsOnASingleLine &&

          
Line.startsWith(tok::kw_if)51
 &&

          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)28
 &&

          
!Style.BraceWrapping.AfterControlStatement27
 &&

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

        return 0;

      if (!Style.AllowShortLoopsOnASingleLine &&

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

          Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always &&

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

        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.72k
 &&

          
(2.72k
Tok->getNextNonComment() == nullptr2.72k
 ||

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

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

        Tok->SpacesRequiredBefore = Style.SpaceInEmptyBlock ? 
14
 : 
02.65k
;

        Tok->CanBreakBefore = true;

        return 1;

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

                 
!startsExternCBlock(Line)4.00k
) {

        // 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.66k
)

          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.07k
{

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

            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 &&

            Style.BraceWrapping.AfterControlStatement ==

                FormatStyle::BWACS_MultiLine)

          return 0;

        return 2;

      }

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

      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->Next16.9k
) {

      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->Next316k
) {

    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.01M
 || 
LBrace->isNot(BK_Block)25.0k
 ||

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

      // 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.ColumnLimit676
)

      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.87k
Indenter->canBreak(State)3.87k
 && 
State.NextToken->NewlinesBefore > 01.09k
);

      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:

  NoLineBreakFormatter(ContinuationIndenter *Indenter,

                       WhitespaceManager *Whitespaces, const FormatStyle &Style,

                       UnwrappedLineFormatter *BlockFormatter)

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

  /// Puts all tokens into a single line.

  unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,

                      unsigned FirstStartColumn, bool DryRun) override {

    unsigned Penalty = 0;

    LineState State =

        Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);

    while (State.NextToken) {

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

      Indenter->addTokenToState(

          State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);

    }

    return Penalty;

  }

};

/// Finds the best way to break lines.

class OptimizingLineFormatter : public LineFormatter {

public:

  OptimizingLineFormatter(ContinuationIndenter *Indenter,

                          WhitespaceManager *Whitespaces,

                          const FormatStyle &Style,

                          UnwrappedLineFormatter *BlockFormatter)

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

  /// Formats the line by finding the best line breaks with line lengths

  /// below the column limit.

  unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,

                      unsigned FirstStartColumn, bool DryRun) override {

    LineState State =

        Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);

    // If the ObjC method declaration does not fit on a line, we should format

    // it with one arg per line.

    if (State.Line->Type == LT_ObjCMethodDecl)

      State.Stack.back().BreakBeforeParameter = true;

    // Find best solution in solution space.

    return analyzeSolutionSpace(State, DryRun);

  }

private:

  struct CompareLineStatePointers {

    bool operator()(LineState *obj1, LineState *obj2) const {

      return *obj1 < *obj2;

    }

  };

  /// A pair of <penalty, count> that is used to prioritize the BFS on.

  ///

  /// In case of equal penalties, we want to prefer states that were inserted

  /// first. During state generation we make sure that we insert states first

  /// that break the line as late as possible.

  typedef std::pair<unsigned, unsigned> OrderedPenalty;

  /// An edge in the solution space from \c Previous->State to \c State,

  /// inserting a newline dependent on the \c NewLine.

  struct StateNode {

    StateNode(const LineState &State, bool NewLine, StateNode *Previous)

        : State(State), NewLine(NewLine), Previous(Previous) {}

    LineState State;

    bool NewLine;

    StateNode *Previous;

  };

  /// An item in the prioritized BFS search queue. The \c StateNode's

  /// \c State has the given \c OrderedPenalty.