//===--- 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() : 
nullptr389
;

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

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

}

/// 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; 
++i1.65k
)

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

      Indent = Line.Level * Style.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.InPPDirective)

      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_JavaScript || 
Style.isCSharp()51.0k
)

      return 0;

    if (RootToken.isAccessSpecifier(false) ||

        RootToken.isObjCAccessSpecifier() ||

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

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

      return Style.AccessModifierOffset;

    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->TokenText : 
StringRef()25
;

}

StringRef getMatchingNamespaceTokenText(

    const AnnotatedLine *Line,

    const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {

  const FormatToken *NamespaceToken =

      getMatchingNamespaceToken(Line, AnnotatedLines);

  return NamespaceToken ? NamespaceToken->TokenText : 
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 == 04.41k
)

      // 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; 54.6k
i < MergedLines; 
++i5.77k
)

        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->MustBreakBefore36.3k
)

      return 0;

    if (TheLine->InPPDirective &&

        (!I[1]->InPPDirective || 
I[1]->First->HasUnescapedNewline1.62k
))

      return 0;

    if (Style.ColumnLimit > 0 && 
Indent > Style.ColumnLimit32.8k
)

      return 0;

    unsigned Limit =

        Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;

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

                ? 0

                : Limit - TheLine->Last->TotalLength;

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

        TheLine->First == TheLine->Last &&

        !Style.BraceWrapping.SplitEmptyFunction &&

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

      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->Last8.95k
 &&

        I != AnnotatedLines.begin()) {

      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()792
)

        return !Style.BraceWrapping.SplitEmptyNamespace && 
EmptyBlock18

                   ? tryMergeSimpleBlock(I, E, Limit)

                   : 0;

      if (Tok && 
Tok->is(tok::kw_typedef)756
)

        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)

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

        (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&

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

        (Style.AllowShortFunctionsOnASingleLine & FormatStyle::SFS_InlineOnly &&

         TheLine->Level != 0);

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

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

             i++, closingLine--) {

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

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

      return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 
0224
;

    }

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

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

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

      return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never

                 ? tryMergeSimpleBlock(I, E, Limit)

                 : 0;

    }

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

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

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

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

                                 TT_ForEachMacro) ||

         (TheLine->First->is(tok::r_brace) && 
TheLine->First->Next16
 &&

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

        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)

                 ? 1

                 : 0;

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

                 : 0;

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

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

               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

                 : 0;

    }

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

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

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

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

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

          kwId == clang::tok::objc_synchronized)

        return 0;

    }

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

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

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

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

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

                      !Style.BraceWrapping.SplitEmptyRecord)

                 ? tryMergeSimpleBlock(I, E, Limit)

                 : 0;

    }

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

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

        Style.BraceWrapping.AfterFunction) {

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

        return 0;

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

      if (Limit <= 2 || 
(342
Style.ColumnLimit == 0342
 && 
containsMustBreak(TheLine)79
))

        return 0;

      Limit -= 2;

      unsigned MergedLines = 0;

      if (MergeShortFunctions ||

          (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&

           I[1]->First == I[1]->Last && I + 2 != E &&

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

        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;

    }

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

      return Style.AllowShortIfStatementsOnASingleLine

                 ? tryMergeSimpleControlStatement(I, E, Limit)

                 : 0;

    }

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

      return Style.AllowShortLoopsOnASingleLine

                 ? tryMergeSimpleControlStatement(I, E, Limit)

                 : 0;

    }

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

      return Style.AllowShortCaseLabelsOnASingleLine

                 ? tryMergeShortCaseLabels(I, E, Limit)

                 : 0;

    }

    if (TheLine->InPPDirective &&

        (TheLine->First->HasUnescapedNewline || 
TheLine->First->IsFirst501
)) {

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

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

        Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never)

      return 0;

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

        (I[1]->InPPDirective && 
I[1]->First->HasUnescapedNewline21
))

      return 0;

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

    AnnotatedLine &Line = **I;

    if (!Line.First->is(tok::kw_do) && 
Line.Last->isNot(tok::r_paren)167
)

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

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

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

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

          EndsWithComment)

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

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

        (Line.First->Next && 
Line.First->Next->is(tok::kw_else)6.97k
))

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

          !Style.BraceWrapping.AfterControlStatement &&

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

        return 0;

      if (!Style.AllowShortIfStatementsOnASingleLine &&

          Line.startsWith(tok::kw_if) &&

          Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always &&

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

        return 0;

      if (!Style.AllowShortLoopsOnASingleLine &&

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

          !Style.BraceWrapping.AfterControlStatement &&

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

        return 0;

      if (!Style.AllowShortLoopsOnASingleLine &&

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

          Style.BraceWrapping.AfterControlStatement ==

              FormatStyle::BWACS_Always &&

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

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

          (Tok->getNextNonComment() == nullptr ||

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

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

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

        Tok->CanBreakBefore = true;

        return 1;

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

                 !startsExternCBlock(Line)) {

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

          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 1.87k
{

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

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

          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 (I[1]->First->is(tok::l_brace)) {

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

          (I[1]->First == I[1]->Last && I + 2 != E &&

           
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->HasUnescapedNewline && 
!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->Next353
) {

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

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

    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)880k
 || 
LBrace->isNot(BK_Block)16.9k
 ||

        Previous.Children.size() == 0)

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

      int AdditionalIndent = State.Stack.back().Indent -

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

      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.ColumnLimit)

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

          (Indenter->canBreak(State) && 
State.NextToken->NewlinesBefore > 0845
);

      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.

  typedef std::pair<OrderedPenalty, StateNode *> QueueItem;

  /// The BFS queue type.

  typedef std::priority_queue<QueueItem, std::vector<QueueItem>,

                              std::greater<QueueItem>>

      QueueType;

  /// Analyze the entire solution space starting from \p InitialState.

  ///

  /// This implements a variant of Dijkstra's algorithm on the graph that spans

  /// the solution space (\c LineStates are the nodes). The algorithm tries to

  /// find the shortest path (the one with lowest penalty) from \p InitialState

  /// to a state where all tokens are placed. Returns the penalty.

  ///

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

  unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {

    std::set<LineState *, CompareLineStatePointers> Seen;

    // Increasing count of \c StateNode items we have created. This is used to

    // create a deterministic order independent of the container.

    unsigned Count = 0;

    QueueType Queue;

    // Insert start element into queue.

    StateNode *Node =

        new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);

    Queue.push(QueueItem(OrderedPenalty(0, Count), Node));

    ++Count;

    unsigned Penalty = 0;

    // While not empty, take first element and follow edges.

    while (!Queue.empty()) {

      Penalty = Queue.top().first.first;

      StateNode *Node = Queue.top().second;

      if (!Node->State.NextToken) {

        LLVM_DEBUG(llvm::dbgs()

                   << "\n---\nPenalty for line: " << Penalty << "\n");

        break;

      }

      Queue.pop();

      // Cut off the analysis of certain solutions if the analysis gets too

      // complex. See description of IgnoreStackForComparison.

      if (Count > 50000)

        Node->State.IgnoreStackForComparison = true;

      if (!Seen.insert(&Node->State).second)

        // State already examined with lower penalty.

        continue;

      FormatDecision LastFormat = Node->State.NextToken->getDecision();

      if (LastFormat == FD_Unformatted || 
LastFormat == FD_Continue351
)

        addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);

      if (LastFormat == FD_Unformatted || 
LastFormat == FD_Break351
)

        addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);

    }

    if (Queue.empty()) {

      // We were unable to find a solution, do nothing.

      // FIXME: Add diagnostic?

      LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");

      return 0;

    }

    // Reconstruct the solution.

    if (!DryRun)

      reconstructPath(InitialState, Queue.top().second);

    LLVM_DEBUG(llvm::dbgs()

               << "Total number of analyzed states: " << Count << "\n");

    LLVM_DEBUG(llvm::dbgs() << "---\n");

    return Penalty;

  }

  /// Add the following state to the analysis queue \c Queue.

  ///

  /// Assume the current state is \p PreviousNode and has been reached with a

  /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.

  void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,

                           bool NewLine, unsigned *Count, QueueType *Queue) {

    if (NewLine && 
!Indenter->canBreak(PreviousNode->State)495k
)

      return;

    if (!NewLine && 
Indenter->mustBreak(PreviousNode->State)495k
)

      return;

    StateNode *Node = new (Allocator.Allocate())

        StateNode(PreviousNode->State, NewLine, PreviousNode);

    if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))

      return;

    Penalty += Indenter->addTokenToState(Node->State, NewLine, true);