<commit_before>//===--- Format.cpp - Format C++ code -------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief This file implements functions declared in Format.h. This will be
/// split into separate files as we go.
///
/// This is EXPERIMENTAL code under heavy development. It is not in a state yet,
/// where it can be used to format real code.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "format-formatter"

#include "UnwrappedLineParser.h"
#include "clang/Basic/Diagnostic.h"
#include "clang/Basic/OperatorPrecedence.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Format/Format.h"
#include "clang/Frontend/TextDiagnosticPrinter.h"
#include "clang/Lex/Lexer.h"
#include "llvm/Support/Debug.h"
#include <string>

// Uncomment to get debug output from tests:
// #define DEBUG_WITH_TYPE(T, X) do { X; } while(0)

namespace clang {
namespace format {

enum TokenType {
  TT_BinaryOperator,
  TT_BlockComment,
  TT_CastRParen,
  TT_ConditionalExpr,
  TT_CtorInitializerColon,
  TT_ImplicitStringLiteral,
  TT_LineComment,
  TT_ObjCBlockLParen,
  TT_ObjCDecl,
  TT_ObjCMethodSpecifier,
  TT_ObjCMethodExpr,
  TT_ObjCProperty,
  TT_OverloadedOperator,
  TT_PointerOrReference,
  TT_PureVirtualSpecifier,
  TT_RangeBasedForLoopColon,
  TT_StartOfName,
  TT_TemplateCloser,
  TT_TemplateOpener,
  TT_TrailingUnaryOperator,
  TT_UnaryOperator,
  TT_Unknown
};

enum LineType {
  LT_Invalid,
  LT_Other,
  LT_BuilderTypeCall,
  LT_PreprocessorDirective,
  LT_VirtualFunctionDecl,
  LT_ObjCDecl, // An @interface, @implementation, or @protocol line.
  LT_ObjCMethodDecl,
  LT_ObjCProperty // An @property line.
};

class AnnotatedToken {
public:
  explicit AnnotatedToken(const FormatToken &FormatTok)
      : FormatTok(FormatTok), Type(TT_Unknown), SpaceRequiredBefore(false),
        CanBreakBefore(false), MustBreakBefore(false),
        ClosesTemplateDeclaration(false), MatchingParen(NULL),
        ParameterCount(1), Parent(NULL) {
  }

  bool is(tok::TokenKind Kind) const { return FormatTok.Tok.is(Kind); }
  bool isNot(tok::TokenKind Kind) const { return FormatTok.Tok.isNot(Kind); }

  bool isObjCAtKeyword(tok::ObjCKeywordKind Kind) const {
    return FormatTok.Tok.isObjCAtKeyword(Kind);
  }

  FormatToken FormatTok;

  TokenType Type;

  bool SpaceRequiredBefore;
  bool CanBreakBefore;
  bool MustBreakBefore;

  bool ClosesTemplateDeclaration;

  AnnotatedToken *MatchingParen;

  /// \brief Number of parameters, if this is "(", "[" or "<".
  ///
  /// This is initialized to 1 as we don't need to distinguish functions with
  /// 0 parameters from functions with 1 parameter. Thus, we can simply count
  /// the number of commas.
  unsigned ParameterCount;

  /// \brief The total length of the line up to and including this token.
  unsigned TotalLength;

  std::vector<AnnotatedToken> Children;
  AnnotatedToken *Parent;

  const AnnotatedToken *getPreviousNoneComment() const {
    AnnotatedToken *Tok = Parent;
    while (Tok != NULL && Tok->is(tok::comment))
      Tok = Tok->Parent;
    return Tok;
  }
};

class AnnotatedLine {
public:
  AnnotatedLine(const UnwrappedLine &Line)
      : First(Line.Tokens.front()), Level(Line.Level),
        InPPDirective(Line.InPPDirective),
        MustBeDeclaration(Line.MustBeDeclaration) {
    assert(!Line.Tokens.empty());
    AnnotatedToken *Current = &First;
    for (std::list<FormatToken>::const_iterator I = ++Line.Tokens.begin(),
                                                E = Line.Tokens.end();
         I != E; ++I) {
      Current->Children.push_back(AnnotatedToken(*I));
      Current->Children[0].Parent = Current;
      Current = &Current->Children[0];
    }
    Last = Current;
  }
  AnnotatedLine(const AnnotatedLine &Other)
      : First(Other.First), Type(Other.Type), Level(Other.Level),
        InPPDirective(Other.InPPDirective),
        MustBeDeclaration(Other.MustBeDeclaration) {
    Last = &First;
    while (!Last->Children.empty()) {
      Last->Children[0].Parent = Last;
      Last = &Last->Children[0];
    }
  }

  AnnotatedToken First;
  AnnotatedToken *Last;

  LineType Type;
  unsigned Level;
  bool InPPDirective;
  bool MustBeDeclaration;
};

static prec::Level getPrecedence(const AnnotatedToken &Tok) {
  return getBinOpPrecedence(Tok.FormatTok.Tok.getKind(), true, true);
}

bool isBinaryOperator(const AnnotatedToken &Tok) {
  // Comma is a binary operator, but does not behave as such wrt. formatting.
  return getPrecedence(Tok) > prec::Comma;
}

FormatStyle getLLVMStyle() {
  FormatStyle LLVMStyle;
  LLVMStyle.ColumnLimit = 80;
  LLVMStyle.MaxEmptyLinesToKeep = 1;
  LLVMStyle.PointerAndReferenceBindToType = false;
  LLVMStyle.AccessModifierOffset = -2;
  LLVMStyle.SplitTemplateClosingGreater = true;
  LLVMStyle.IndentCaseLabels = false;
  LLVMStyle.SpacesBeforeTrailingComments = 1;
  LLVMStyle.BinPackParameters = true;
  LLVMStyle.AllowAllParametersOnNextLine = true;
  LLVMStyle.AllowReturnTypeOnItsOwnLine = true;
  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
  return LLVMStyle;
}

FormatStyle getGoogleStyle() {
  FormatStyle GoogleStyle;
  GoogleStyle.ColumnLimit = 80;
  GoogleStyle.MaxEmptyLinesToKeep = 1;
  GoogleStyle.PointerAndReferenceBindToType = true;
  GoogleStyle.AccessModifierOffset = -1;
  GoogleStyle.SplitTemplateClosingGreater = false;
  GoogleStyle.IndentCaseLabels = true;
  GoogleStyle.SpacesBeforeTrailingComments = 2;
  GoogleStyle.BinPackParameters = false;
  GoogleStyle.AllowAllParametersOnNextLine = true;
  GoogleStyle.AllowReturnTypeOnItsOwnLine = false;
  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
  GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
  return GoogleStyle;
}

FormatStyle getChromiumStyle() {
  FormatStyle ChromiumStyle = getGoogleStyle();
  ChromiumStyle.AllowAllParametersOnNextLine = false;
  return ChromiumStyle;
}

struct OptimizationParameters {
  unsigned PenaltyIndentLevel;
  unsigned PenaltyExcessCharacter;
};

/// \brief Manages the whitespaces around tokens and their replacements.
///
/// This includes special handling for certain constructs, e.g. the alignment of
/// trailing line comments.
class WhitespaceManager {
public:
  WhitespaceManager(SourceManager &SourceMgr) : SourceMgr(SourceMgr) {}

  /// \brief Replaces the whitespace in front of \p Tok. Only call once for
  /// each \c AnnotatedToken.
  void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
                         unsigned Spaces, unsigned WhitespaceStartColumn,
                         const FormatStyle &Style) {
    // 2+ newlines mean an empty line separating logic scopes.
    if (NewLines >= 2)
      alignComments();

    // Align line comments if they are trailing or if they continue other
    // trailing comments.
    if (Tok.Type == TT_LineComment &&
        (Tok.Parent != NULL || !Comments.empty())) {
      if (Style.ColumnLimit >=
          Spaces + WhitespaceStartColumn + Tok.FormatTok.TokenLength) {
        Comments.push_back(StoredComment());
        Comments.back().Tok = Tok.FormatTok;
        Comments.back().Spaces = Spaces;
        Comments.back().NewLines = NewLines;
        Comments.back().MinColumn = WhitespaceStartColumn + Spaces;
        Comments.back().MaxColumn =
            Style.ColumnLimit - Spaces - Tok.FormatTok.TokenLength;
        return;
      }
    }

    // If this line does not have a trailing comment, align the stored comments.
    if (Tok.Children.empty() && Tok.Type != TT_LineComment)
      alignComments();
    storeReplacement(Tok.FormatTok,
                     std::string(NewLines, '\n') + std::string(Spaces, ' '));
  }

  /// \brief Like \c replaceWhitespace, but additionally adds right-aligned
  /// backslashes to escape newlines inside a preprocessor directive.
  ///
  /// This function and \c replaceWhitespace have the same behavior if
  /// \c Newlines == 0.
  void replacePPWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
                           unsigned Spaces, unsigned WhitespaceStartColumn,
                           const FormatStyle &Style) {
    std::string NewLineText;
    if (NewLines > 0) {
      unsigned Offset =
          std::min<int>(Style.ColumnLimit - 1, WhitespaceStartColumn);
      for (unsigned i = 0; i < NewLines; ++i) {
        NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' ');
        NewLineText += "\\\n";
        Offset = 0;
      }
    }
    storeReplacement(Tok.FormatTok, NewLineText + std::string(Spaces, ' '));
  }

  /// \brief Returns all the \c Replacements created during formatting.
  const tooling::Replacements &generateReplacements() {
    alignComments();
    return Replaces;
  }

private:
  /// \brief Structure to store a comment for later layout and alignment.
  struct StoredComment {
    FormatToken Tok;
    unsigned MinColumn;
    unsigned MaxColumn;
    unsigned NewLines;
    unsigned Spaces;
  };
  SmallVector<StoredComment, 16> Comments;
  typedef SmallVector<StoredComment, 16>::iterator comment_iterator;

  /// \brief Try to align all stashed comments.
  void alignComments() {
    unsigned MinColumn = 0;
    unsigned MaxColumn = UINT_MAX;
    comment_iterator Start = Comments.begin();
    for (comment_iterator I = Comments.begin(), E = Comments.end(); I != E;
         ++I) {
      if (I->MinColumn > MaxColumn || I->MaxColumn < MinColumn) {
        alignComments(Start, I, MinColumn);
        MinColumn = I->MinColumn;
        MaxColumn = I->MaxColumn;
        Start = I;
      } else {
        MinColumn = std::max(MinColumn, I->MinColumn);
        MaxColumn = std::min(MaxColumn, I->MaxColumn);
      }
    }
    alignComments(Start, Comments.end(), MinColumn);
    Comments.clear();
  }

  /// \brief Put all the comments between \p I and \p E into \p Column.
  void alignComments(comment_iterator I, comment_iterator E, unsigned Column) {
    while (I != E) {
      unsigned Spaces = I->Spaces + Column - I->MinColumn;
      storeReplacement(I->Tok, std::string(I->NewLines, '\n') +
                       std::string(Spaces, ' '));
      ++I;
    }
  }

  /// \brief Stores \p Text as the replacement for the whitespace in front of
  /// \p Tok.
  void storeReplacement(const FormatToken &Tok, const std::string Text) {
    Replaces.insert(tooling::Replacement(SourceMgr, Tok.WhiteSpaceStart,
                                         Tok.WhiteSpaceLength, Text));
  }

  SourceManager &SourceMgr;
  tooling::Replacements Replaces;
};

/// \brief Returns if a token is an Objective-C selector name.
///
/// For example, "bar" is a selector name in [foo bar:(4 + 5)].
static bool isObjCSelectorName(const AnnotatedToken &Tok) {
  return Tok.is(tok::identifier) && !Tok.Children.empty() &&
         Tok.Children[0].is(tok::colon) &&
         Tok.Children[0].Type == TT_ObjCMethodExpr;
}

class UnwrappedLineFormatter {
public:
  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
                         const AnnotatedLine &Line, unsigned FirstIndent,
                         const AnnotatedToken &RootToken,
                         WhitespaceManager &Whitespaces, bool StructuralError)
      : Style(Style), SourceMgr(SourceMgr), Line(Line),
        FirstIndent(FirstIndent), RootToken(RootToken),
        Whitespaces(Whitespaces) {
    Parameters.PenaltyIndentLevel = 20;
    Parameters.PenaltyExcessCharacter = 1000000;
  }

  /// \brief Formats an \c UnwrappedLine.
  ///
  /// \returns The column after the last token in the last line of the
  /// \c UnwrappedLine.
  unsigned format() {
    // Initialize state dependent on indent.
    LineState State;
    State.Column = FirstIndent;
    State.NextToken = &RootToken;
    State.Stack.push_back(ParenState(FirstIndent + 4, FirstIndent));
    State.VariablePos = 0;
    State.LineContainsContinuedForLoopSection = false;

    DEBUG({
      DebugTokenState(*State.NextToken);
    });

    // The first token has already been indented and thus consumed.
    moveStateToNextToken(State);

    // Start iterating at 1 as we have correctly formatted of Token #0 above.
    while (State.NextToken != NULL) {
      if (State.NextToken->Type == TT_ImplicitStringLiteral) {
        // Calculating the column is important for aligning trailing comments.
        // FIXME: This does not seem to happen in conjunction with escaped
        // newlines. If it does, fix!
        State.Column += State.NextToken->FormatTok.WhiteSpaceLength +
                        State.NextToken->FormatTok.TokenLength;
        State.NextToken = State.NextToken->Children.empty()
            ? NULL : &State.NextToken->Children[0];
      } else if (Line.Last->TotalLength <= getColumnLimit() - FirstIndent) {
        addTokenToState(false, false, State);
      } else {
        unsigned NoBreak = calcPenalty(State, false, UINT_MAX);
        unsigned Break = calcPenalty(State, true, NoBreak);
        DEBUG({
          if (Break < NoBreak)
            llvm::errs() << "\n";
          else
            llvm::errs() << " ";
          llvm::errs() << "<";
          DebugPenalty(Break, Break < NoBreak);
          llvm::errs() << "/";
          DebugPenalty(NoBreak, !(Break < NoBreak));
          llvm::errs() << "> ";
          DebugTokenState(*State.NextToken);
        });
        addTokenToState(Break < NoBreak, false, State);
        if (State.NextToken != NULL &&
            State.NextToken->Parent->Type == TT_CtorInitializerColon) {
          if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine &&
              Line.Last->TotalLength > getColumnLimit() - State.Column - 1)
            State.Stack.back().BreakAfterComma = true;
        }
      }
    }
    DEBUG(llvm::errs() << "\n");
    return State.Column;
  }

private:
  void DebugTokenState(const AnnotatedToken &AnnotatedTok) {
    const Token &Tok = AnnotatedTok.FormatTok.Tok;
    llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
                              Tok.getLength());
    llvm::errs();
  }

  void DebugPenalty(unsigned Penalty, bool Winner) {
    llvm::errs().changeColor(Winner ? raw_ostream::GREEN : raw_ostream::RED);
    if (Penalty == UINT_MAX)
      llvm::errs() << "MAX";
    else
      llvm::errs() << Penalty;
    llvm::errs().resetColor();
  }

  struct ParenState {
    ParenState(unsigned Indent, unsigned LastSpace)
        : Indent(Indent), LastSpace(LastSpace), AssignmentColumn(0),
          FirstLessLess(0), BreakBeforeClosingBrace(false), QuestionColumn(0),
          BreakAfterComma(false), HasMultiParameterLine(false) {
    }

    /// \brief The position to which a specific parenthesis level needs to be
    /// indented.
    unsigned Indent;

    /// \brief The position of the last space on each level.
    ///
    /// Used e.g. to break like:
    /// functionCall(Parameter, otherCall(
    ///                             OtherParameter));
    unsigned LastSpace;

    /// \brief This is the column of the first token after an assignment.
    unsigned AssignmentColumn;

    /// \brief The position the first "<<" operator encountered on each level.
    ///
    /// Used to align "<<" operators. 0 if no such operator has been encountered
    /// on a level.
    unsigned FirstLessLess;

    /// \brief Whether a newline needs to be inserted before the block's closing
    /// brace.
    ///
    /// We only want to insert a newline before the closing brace if there also
    /// was a newline after the beginning left brace.
    bool BreakBeforeClosingBrace;

    /// \brief The column of a \c ? in a conditional expression;
    unsigned QuestionColumn;

    bool BreakAfterComma;
    bool HasMultiParameterLine;

    bool operator<(const ParenState &Other) const {
      if (Indent != Other.Indent)
        return Indent < Other.Indent;
      if (LastSpace != Other.LastSpace)
        return LastSpace < Other.LastSpace;
      if (AssignmentColumn != Other.AssignmentColumn)
        return AssignmentColumn < Other.AssignmentColumn;
      if (FirstLessLess != Other.FirstLessLess)
        return FirstLessLess < Other.FirstLessLess;
      if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
        return BreakBeforeClosingBrace;
      if (QuestionColumn != Other.QuestionColumn)
        return QuestionColumn < Other.QuestionColumn;
      if (BreakAfterComma != Other.BreakAfterComma)
        return BreakAfterComma;
      if (HasMultiParameterLine != Other.HasMultiParameterLine)
        return HasMultiParameterLine;
      return false;
    }
  };

  /// \brief The current state when indenting a unwrapped line.
  ///
  /// As the indenting tries different combinations this is copied by value.
  struct LineState {
    /// \brief The number of used columns in the current line.
    unsigned Column;

    /// \brief The token that needs to be next formatted.
    const AnnotatedToken *NextToken;

    /// \brief The column of the first variable name in a variable declaration.
    ///
    /// Used to align further variables if necessary.
    unsigned VariablePos;

    /// \brief \c true if this line contains a continued for-loop section.
    bool LineContainsContinuedForLoopSection;

    /// \brief A stack keeping track of properties applying to parenthesis
    /// levels.
    std::vector<ParenState> Stack;

    /// \brief Comparison operator to be able to used \c LineState in \c map.
    bool operator<(const LineState &Other) const {
      if (Other.NextToken != NextToken)
        return Other.NextToken > NextToken;
      if (Other.Column != Column)
        return Other.Column > Column;
      if (Other.VariablePos != VariablePos)
        return Other.VariablePos < VariablePos;
      if (Other.LineContainsContinuedForLoopSection !=
          LineContainsContinuedForLoopSection)
        return LineContainsContinuedForLoopSection;
      return Other.Stack < Stack;
    }
  };

  /// \brief Appends the next token to \p State and updates information
  /// necessary for indentation.
  ///
  /// Puts the token on the current line if \p Newline is \c true and adds a
  /// line break and necessary indentation otherwise.
  ///
  /// If \p DryRun is \c false, also creates and stores the required
  /// \c Replacement.
  void addTokenToState(bool Newline, bool DryRun, LineState &State) {
    const AnnotatedToken &Current = *State.NextToken;
    const AnnotatedToken &Previous = *State.NextToken->Parent;
    assert(State.Stack.size());
    unsigned ParenLevel = State.Stack.size() - 1;

    if (Newline) {
      unsigned WhitespaceStartColumn = State.Column;
      if (Current.is(tok::r_brace)) {
        State.Column = Line.Level * 2;
      } else if (Current.is(tok::string_literal) &&
                 Previous.is(tok::string_literal)) {
        State.Column = State.Column - Previous.FormatTok.TokenLength;
      } else if (Current.is(tok::lessless) &&
                 State.Stack[ParenLevel].FirstLessLess != 0) {
        State.Column = State.Stack[ParenLevel].FirstLessLess;
      } else if (ParenLevel != 0 &&
                 (Previous.is(tok::equal) || Previous.is(tok::coloncolon) ||
                  Current.is(tok::period) || Current.is(tok::arrow) ||
                  Current.is(tok::question))) {
        // Indent and extra 4 spaces after if we know the current expression is
        // continued.  Don't do that on the top level, as we already indent 4
        // there.
        State.Column = std::max(State.Stack.back().LastSpace,
                                State.Stack.back().Indent) + 4;
      } else if (Current.Type == TT_ConditionalExpr) {
        State.Column = State.Stack.back().QuestionColumn;
      } else if (Previous.is(tok::comma) && State.VariablePos != 0 &&
                 ((RootToken.is(tok::kw_for) && ParenLevel == 1) ||
                  ParenLevel == 0)) {
        State.Column = State.VariablePos;
      } else if (State.NextToken->Parent->ClosesTemplateDeclaration ||
                 Current.Type == TT_StartOfName) {
        State.Column = State.Stack[ParenLevel].Indent - 4;
      } else if (Previous.Type == TT_BinaryOperator &&
                 State.Stack.back().AssignmentColumn != 0) {
        State.Column = State.Stack.back().AssignmentColumn;
      } else {
        State.Column = State.Stack[ParenLevel].Indent;
      }

      if (RootToken.is(tok::kw_for))
        State.LineContainsContinuedForLoopSection = Previous.isNot(tok::semi);

      if (!DryRun) {
        if (!Line.InPPDirective)
          Whitespaces.replaceWhitespace(Current, 1, State.Column,
                                        WhitespaceStartColumn, Style);
        else
          Whitespaces.replacePPWhitespace(Current, 1, State.Column,
                                          WhitespaceStartColumn, Style);
      }

      State.Stack[ParenLevel].LastSpace = State.Column;
      if (Current.is(tok::colon) && Current.Type != TT_ConditionalExpr)
        State.Stack[ParenLevel].Indent += 2;
    } else {
      if (Current.is(tok::equal) &&
          (RootToken.is(tok::kw_for) || ParenLevel == 0))
        State.VariablePos = State.Column - Previous.FormatTok.TokenLength;

      unsigned Spaces = State.NextToken->SpaceRequiredBefore ? 1 : 0;
      if (State.NextToken->Type == TT_LineComment)
        Spaces = Style.SpacesBeforeTrailingComments;

      if (!DryRun)
        Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column, Style);

      // FIXME: Do we need to do this for assignments nested in other
      // expressions?
      if (RootToken.isNot(tok::kw_for) && ParenLevel == 0 &&
          (getPrecedence(Previous) == prec::Assignment ||
           Previous.is(tok::kw_return)))
        State.Stack.back().AssignmentColumn = State.Column + Spaces;
      if (Previous.is(tok::l_paren) || Previous.is(tok::l_brace) ||
          State.NextToken->Parent->Type == TT_TemplateOpener)
        State.Stack[ParenLevel].Indent = State.Column + Spaces;
      if (Current.getPreviousNoneComment() != NULL &&
          Current.getPreviousNoneComment()->is(tok::comma) &&
          Current.isNot(tok::comment))
        State.Stack[ParenLevel].HasMultiParameterLine = true;

      State.Column += Spaces;
      if (Current.is(tok::l_paren) && Previous.is(tok::kw_if))
        // Treat the condition inside an if as if it was a second function
        // parameter, i.e. let nested calls have an indent of 4.
        State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(".
      else if (Previous.is(tok::comma) && ParenLevel != 0)
        // Top-level spaces are exempt as that mostly leads to better results.
        State.Stack.back().LastSpace = State.Column;
      else if ((Previous.Type == TT_BinaryOperator ||
                Previous.Type == TT_ConditionalExpr ||
                Previous.Type == TT_CtorInitializerColon) &&
               getPrecedence(Previous) != prec::Assignment)
        State.Stack.back().LastSpace = State.Column;
      else if (Previous.ParameterCount > 1 &&
               (Previous.is(tok::l_paren) || Previous.is(tok::l_square) ||
                Previous.Type == TT_TemplateOpener))
        // If this function has multiple parameters, indent nested calls from
        // the start of the first parameter.
        State.Stack.back().LastSpace = State.Column;
    }

    // If we break after an {, we should also break before the corresponding }.
    if (Newline && Previous.is(tok::l_brace))
      State.Stack.back().BreakBeforeClosingBrace = true;

    if (!Style.BinPackParameters && Newline) {
      // If we are breaking after '(', '{', '<', this is not bin packing unless
      // AllowAllParametersOnNextLine is false.
      if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace) &&
           Previous.Type != TT_TemplateOpener) ||
          !Style.AllowAllParametersOnNextLine)
        State.Stack.back().BreakAfterComma = true;

      // Any break on this level means that the parent level has been broken
      // and we need to avoid bin packing there.
      for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) {
        State.Stack[i].BreakAfterComma = true;
      }
    }

    moveStateToNextToken(State);
  }

  /// \brief Mark the next token as consumed in \p State and modify its stacks
  /// accordingly.
  void moveStateToNextToken(LineState &State) {
    const AnnotatedToken &Current = *State.NextToken;
    assert(State.Stack.size());

    if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
      State.Stack.back().FirstLessLess = State.Column;
    if (Current.is(tok::question))
      State.Stack.back().QuestionColumn = State.Column;

    // If we encounter an opening (, [, { or <, we add a level to our stacks to
    // prepare for the following tokens.
    if (Current.is(tok::l_paren) || Current.is(tok::l_square) ||
        Current.is(tok::l_brace) ||
        State.NextToken->Type == TT_TemplateOpener) {
      unsigned NewIndent;
      if (Current.is(tok::l_brace)) {
        // FIXME: This does not work with nested static initializers.
        // Implement a better handling for static initializers and similar
        // constructs.
        NewIndent = Line.Level * 2 + 2;
      } else {
        NewIndent = 4 + State.Stack.back().LastSpace;
      }
      State.Stack.push_back(ParenState(NewIndent,
                                       State.Stack.back().LastSpace));
    }

    // If we encounter a closing ), ], } or >, we can remove a level from our
    // stacks.
    if (Current.is(tok::r_paren) || Current.is(tok::r_square) ||
        (Current.is(tok::r_brace) && State.NextToken != &RootToken) ||
        State.NextToken->Type == TT_TemplateCloser) {
      State.Stack.pop_back();
    }

    if (State.NextToken->Children.empty())
      State.NextToken = NULL;
    else
      State.NextToken = &State.NextToken->Children[0];

    State.Column += Current.FormatTok.TokenLength;
  }

  /// \brief Calculate the penalty for splitting after the token at \p Index.
  unsigned splitPenalty(const AnnotatedToken &Tok) {
    const AnnotatedToken &Left = Tok;
    const AnnotatedToken &Right = Tok.Children[0];

    if (Left.is(tok::l_brace) && Right.isNot(tok::l_brace))
      return 50;
    if (Left.is(tok::equal) && Right.is(tok::l_brace))
      return 150;
    if (Left.is(tok::coloncolon))
      return 500;

    if (Left.Type == TT_RangeBasedForLoopColon)
      return 5;

    if (Right.is(tok::arrow) || Right.is(tok::period)) {
      if (Left.is(tok::r_paren) && Line.Type == LT_BuilderTypeCall)
        return 5; // Should be smaller than breaking at a nested comma.
      return 150;
    }

    // In for-loops, prefer breaking at ',' and ';'.
    if (RootToken.is(tok::kw_for) &&
        (Left.isNot(tok::comma) && Left.isNot(tok::semi)))
      return 20;

    if (Left.is(tok::semi) || Left.is(tok::comma))
      return 0;

    // In Objective-C method expressions, prefer breaking before "param:" over
    // breaking after it.
    if (isObjCSelectorName(Right))
      return 0;
    if (Right.is(tok::colon) && Right.Type == TT_ObjCMethodExpr)
      return 20;

    if (Left.is(tok::l_paren))
      return 20;
    // FIXME: The penalty for a trailing "<" or "[" being higher than the
    // penalty for a trainling "(" is a temporary workaround until we can
    // properly avoid breaking in array subscripts or template parameters.
    if (Left.is(tok::l_square) || Left.Type == TT_TemplateOpener)
      return 50;

    if (Left.Type == TT_ConditionalExpr)
      return prec::Assignment;
    prec::Level Level = getPrecedence(Left);

    if (Level != prec::Unknown)
      return Level;

    return 3;
  }

  unsigned getColumnLimit() {
    return Style.ColumnLimit - (Line.InPPDirective ? 1 : 0);
  }

  /// \brief Calculate the number of lines needed to format the remaining part
  /// of the unwrapped line.
  ///
  /// Assumes the formatting so far has led to
  /// the \c LineSta \p State. If \p NewLine is set, a new line will be
  /// added after the previous token.
  ///
  /// \param StopAt is used for optimization. If we can determine that we'll
  /// definitely need at least \p StopAt additional lines, we already know of a
  /// better solution.
  unsigned calcPenalty(LineState State, bool NewLine, unsigned StopAt) {
    // We are at the end of the unwrapped line, so we don't need any more lines.
    if (State.NextToken == NULL)
      return 0;

    if (!NewLine && State.NextToken->MustBreakBefore)
      return UINT_MAX;
    if (NewLine && !State.NextToken->CanBreakBefore &&
        !(State.NextToken->is(tok::r_brace) &&
          State.Stack.back().BreakBeforeClosingBrace))
      return UINT_MAX;
    if (!NewLine && State.NextToken->is(tok::r_brace) &&
        State.Stack.back().BreakBeforeClosingBrace)
      return UINT_MAX;
    if (!NewLine && State.NextToken->Parent->is(tok::semi) &&
        State.LineContainsContinuedForLoopSection)
      return UINT_MAX;
    if (!NewLine && State.NextToken->Parent->is(tok::comma) &&
        State.NextToken->isNot(tok::comment) &&
        State.Stack.back().BreakAfterComma)
      return UINT_MAX;
    // Trying to insert a parameter on a new line if there are already more than
    // one parameter on the current line is bin packing.
    if (NewLine && State.NextToken->Parent->is(tok::comma) &&
        State.Stack.back().HasMultiParameterLine && !Style.BinPackParameters)
      return UINT_MAX;
    if (!NewLine && (State.NextToken->Type == TT_CtorInitializerColon ||
                     (State.NextToken->Parent->ClosesTemplateDeclaration &&
                      State.Stack.size() == 1)))
      return UINT_MAX;

    unsigned CurrentPenalty = 0;
    if (NewLine)
      CurrentPenalty += Parameters.PenaltyIndentLevel * State.Stack.size() +
                        splitPenalty(*State.NextToken->Parent);

    addTokenToState(NewLine, true, State);

    // Exceeding column limit is bad, assign penalty.
    if (State.Column > getColumnLimit()) {
      unsigned ExcessCharacters = State.Column - getColumnLimit();
      CurrentPenalty += Parameters.PenaltyExcessCharacter * ExcessCharacters;
    }

    if (StopAt <= CurrentPenalty)
      return UINT_MAX;
    StopAt -= CurrentPenalty;
    StateMap::iterator I = Memory.find(State);
    if (I != Memory.end()) {
      // If this state has already been examined, we can safely return the
      // previous result if we
      // - have not hit the optimatization (and thus returned UINT_MAX) OR
      // - are now computing for a smaller or equal StopAt.
      unsigned SavedResult = I->second.first;
      unsigned SavedStopAt = I->second.second;
      if (SavedResult != UINT_MAX)
        return SavedResult + CurrentPenalty;
      else if (StopAt <= SavedStopAt)
        return UINT_MAX;
    }

    unsigned NoBreak = calcPenalty(State, false, StopAt);
    unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, NoBreak));
    unsigned Result = std::min(NoBreak, WithBreak);

    // We have to store 'Result' without adding 'CurrentPenalty' as the latter
    // can depend on 'NewLine'.
    Memory[State] = std::pair<unsigned, unsigned>(Result, StopAt);

    return Result == UINT_MAX ? UINT_MAX : Result + CurrentPenalty;
  }

  FormatStyle Style;
  SourceManager &SourceMgr;
  const AnnotatedLine &Line;
  const unsigned FirstIndent;
  const AnnotatedToken &RootToken;
  WhitespaceManager &Whitespaces;

  // A map from an indent state to a pair (Result, Used-StopAt).
  typedef std::map<LineState, std::pair<unsigned, unsigned> > StateMap;
  StateMap Memory;

  OptimizationParameters Parameters;
};

/// \brief Determines extra information about the tokens comprising an
/// \c UnwrappedLine.
class TokenAnnotator {
public:
  TokenAnnotator(const FormatStyle &Style, SourceManager &SourceMgr, Lexer &Lex,
                 AnnotatedLine &Line)
      : Style(Style), SourceMgr(SourceMgr), Lex(Lex), Line(Line) {
  }

  /// \brief A parser that gathers additional information about tokens.
  ///
  /// The \c TokenAnnotator tries to matches parenthesis and square brakets and
  /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
  /// into template parameter lists.
  class AnnotatingParser {
  public:
    AnnotatingParser(AnnotatedToken &RootToken)
        : CurrentToken(&RootToken), KeywordVirtualFound(false),
          ColonIsObjCMethodExpr(false), ColonIsForRangeExpr(false) {
    }

    /// \brief A helper class to manage AnnotatingParser::ColonIsObjCMethodExpr.
    struct ObjCSelectorRAII {
      AnnotatingParser &P;
      bool ColonWasObjCMethodExpr;

      ObjCSelectorRAII(AnnotatingParser &P)
          : P(P), ColonWasObjCMethodExpr(P.ColonIsObjCMethodExpr) {
      }

      ~ObjCSelectorRAII() { P.ColonIsObjCMethodExpr = ColonWasObjCMethodExpr; }

      void markStart(AnnotatedToken &Left) {
        P.ColonIsObjCMethodExpr = true;
        Left.Type = TT_ObjCMethodExpr;
      }

      void markEnd(AnnotatedToken &Right) { Right.Type = TT_ObjCMethodExpr; }
    };

    bool parseAngle() {
      if (CurrentToken == NULL)
        return false;
      AnnotatedToken *Left = CurrentToken->Parent;
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::greater)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          CurrentToken->Type = TT_TemplateCloser;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square) ||
            CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::pipepipe) || CurrentToken->is(tok::ampamp) ||
            CurrentToken->is(tok::question) || CurrentToken->is(tok::colon))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseParens(bool LookForDecls = false) {
      if (CurrentToken == NULL)
        return false;
      bool StartsObjCMethodExpr = false;
      AnnotatedToken *Left = CurrentToken->Parent;
      if (CurrentToken->is(tok::caret)) {
        // ^( starts a block.
        Left->Type = TT_ObjCBlockLParen;
      } else if (AnnotatedToken *MaybeSel = Left->Parent) {
        // @selector( starts a selector.
        if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Parent &&
            MaybeSel->Parent->is(tok::at)) {
          StartsObjCMethodExpr = true;
        }
      }

      ObjCSelectorRAII objCSelector(*this);
      if (StartsObjCMethodExpr)
        objCSelector.markStart(*Left);

      while (CurrentToken != NULL) {
        // LookForDecls is set when "if (" has been seen. Check for
        // 'identifier' '*' 'identifier' followed by not '=' -- this
        // '*' has to be a binary operator but determineStarAmpUsage() will
        // categorize it as an unary operator, so set the right type here.
        if (LookForDecls && !CurrentToken->Children.empty()) {
          AnnotatedToken &Prev = *CurrentToken->Parent;
          AnnotatedToken &Next = CurrentToken->Children[0];
          if (Prev.Parent->is(tok::identifier) &&
              (Prev.is(tok::star) || Prev.is(tok::amp)) &&
              CurrentToken->is(tok::identifier) && Next.isNot(tok::equal)) {
            Prev.Type = TT_BinaryOperator;
            LookForDecls = false;
          }
        }

        if (CurrentToken->is(tok::r_paren)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;

          if (StartsObjCMethodExpr)
            objCSelector.markEnd(*CurrentToken);

          next();
          return true;
        }
        if (CurrentToken->is(tok::r_square) || CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseSquare() {
      if (!CurrentToken)
        return false;

      // A '[' could be an index subscript (after an indentifier or after
      // ')' or ']'), or it could be the start of an Objective-C method
      // expression.
      AnnotatedToken *Left = CurrentToken->Parent;
      bool StartsObjCMethodExpr =
          !Left->Parent || Left->Parent->is(tok::colon) ||
          Left->Parent->is(tok::l_square) || Left->Parent->is(tok::l_paren) ||
          Left->Parent->is(tok::kw_return) || Left->Parent->is(tok::kw_throw) ||
          getBinOpPrecedence(Left->Parent->FormatTok.Tok.getKind(), true,
                             true) > prec::Unknown;

      ObjCSelectorRAII objCSelector(*this);
      if (StartsObjCMethodExpr)
        objCSelector.markStart(*Left);

      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::r_square)) {
          if (!CurrentToken->Children.empty() &&
              CurrentToken->Children[0].is(tok::l_paren)) {
            // An ObjC method call can't be followed by an open parenthesis.
            // FIXME: Do we incorrectly label ":" with this?
            StartsObjCMethodExpr = false;
            Left->Type = TT_Unknown;
          }
          if (StartsObjCMethodExpr)
            objCSelector.markEnd(*CurrentToken);
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseBrace() {
      // Lines are fine to end with '{'.
      if (CurrentToken == NULL)
        return true;
      AnnotatedToken *Left = CurrentToken->Parent;
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::r_brace)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square))
          return false;
        if (!consumeToken())
          return false;
      }
      return true;
    }

    bool parseConditional() {
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::colon)) {
          CurrentToken->Type = TT_ConditionalExpr;
          next();
          return true;
        }
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseTemplateDeclaration() {
      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
        CurrentToken->Type = TT_TemplateOpener;
        next();
        if (!parseAngle())
          return false;
        CurrentToken->Parent->ClosesTemplateDeclaration = true;
        return true;
      }
      return false;
    }

    bool consumeToken() {
      AnnotatedToken *Tok = CurrentToken;
      next();
      switch (Tok->FormatTok.Tok.getKind()) {
      case tok::plus:
      case tok::minus:
        // At the start of the line, +/- specific ObjectiveC method
        // declarations.
        if (Tok->Parent == NULL)
          Tok->Type = TT_ObjCMethodSpecifier;
        break;
      case tok::colon:
        // Colons from ?: are handled in parseConditional().
        if (Tok->Parent->is(tok::r_paren))
          Tok->Type = TT_CtorInitializerColon;
        else if (ColonIsObjCMethodExpr)
          Tok->Type = TT_ObjCMethodExpr;
        else if (ColonIsForRangeExpr)
          Tok->Type = TT_RangeBasedForLoopColon;
        break;
      case tok::kw_if:
      case tok::kw_while:
        if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
          next();
          if (!parseParens(/*LookForDecls=*/ true))
            return false;
        }
        break;
      case tok::kw_for:
        ColonIsForRangeExpr = true;
        next();
        if (!parseParens())
          return false;
        break;
      case tok::l_paren:
        if (!parseParens())
          return false;
        break;
      case tok::l_square:
        if (!parseSquare())
          return false;
        break;
      case tok::l_brace:
        if (!parseBrace())
          return false;
        break;
      case tok::less:
        if (parseAngle())
          Tok->Type = TT_TemplateOpener;
        else {
          Tok->Type = TT_BinaryOperator;
          CurrentToken = Tok;
          next();
        }
        break;
      case tok::r_paren:
      case tok::r_square:
        return false;
      case tok::r_brace:
        // Lines can start with '}'.
        if (Tok->Parent != NULL)
          return false;
        break;
      case tok::greater:
        Tok->Type = TT_BinaryOperator;
        break;
      case tok::kw_operator:
        if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
          CurrentToken->Type = TT_OverloadedOperator;
          next();
          if (CurrentToken != NULL && CurrentToken->is(tok::r_paren)) {
            CurrentToken->Type = TT_OverloadedOperator;
            next();
          }
        } else {
          while (CurrentToken != NULL && CurrentToken->isNot(tok::l_paren)) {
            CurrentToken->Type = TT_OverloadedOperator;
            next();
          }
        }
        break;
      case tok::question:
        parseConditional();
        break;
      case tok::kw_template:
        parseTemplateDeclaration();
        break;
      default:
        break;
      }
      return true;
    }

    void parseIncludeDirective() {
      next();
      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
        next();
        while (CurrentToken != NULL) {
          if (CurrentToken->isNot(tok::comment) ||
              !CurrentToken->Children.empty())
            CurrentToken->Type = TT_ImplicitStringLiteral;
          next();
        }
      } else {
        while (CurrentToken != NULL) {
          next();
        }
      }
    }

    void parseWarningOrError() {
      next();
      // We still want to format the whitespace left of the first token of the
      // warning or error.
      next();
      while (CurrentToken != NULL) {
        CurrentToken->Type = TT_ImplicitStringLiteral;
        next();
      }
    }

    void parsePreprocessorDirective() {
      next();
      if (CurrentToken == NULL)
        return;
      // Hashes in the middle of a line can lead to any strange token
      // sequence.
      if (CurrentToken->FormatTok.Tok.getIdentifierInfo() == NULL)
        return;
      switch (
          CurrentToken->FormatTok.Tok.getIdentifierInfo()->getPPKeywordID()) {
      case tok::pp_include:
      case tok::pp_import:
        parseIncludeDirective();
        break;
      case tok::pp_error:
      case tok::pp_warning:
        parseWarningOrError();
        break;
      default:
        break;
      }
    }

    LineType parseLine() {
      int PeriodsAndArrows = 0;
      bool CanBeBuilderTypeStmt = true;
      if (CurrentToken->is(tok::hash)) {
        parsePreprocessorDirective();
        return LT_PreprocessorDirective;
      }
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::kw_virtual))
          KeywordVirtualFound = true;
        if (CurrentToken->is(tok::period) || CurrentToken->is(tok::arrow))
          ++PeriodsAndArrows;
        if (getPrecedence(*CurrentToken) > prec::Assignment &&
            CurrentToken->isNot(tok::less) && CurrentToken->isNot(tok::greater))
          CanBeBuilderTypeStmt = false;
        if (!consumeToken())
          return LT_Invalid;
      }
      if (KeywordVirtualFound)
        return LT_VirtualFunctionDecl;

      // Assume a builder-type call if there are 2 or more "." and "->".
      if (PeriodsAndArrows >= 2 && CanBeBuilderTypeStmt)
        return LT_BuilderTypeCall;

      return LT_Other;
    }

    void next() {
      if (CurrentToken != NULL && !CurrentToken->Children.empty())
        CurrentToken = &CurrentToken->Children[0];
      else
        CurrentToken = NULL;
    }

  private:
    AnnotatedToken *CurrentToken;
    bool KeywordVirtualFound;
    bool ColonIsObjCMethodExpr;
    bool ColonIsForRangeExpr;
  };

  void calculateExtraInformation(AnnotatedToken &Current) {
    Current.SpaceRequiredBefore = spaceRequiredBefore(Current);

    if (Current.FormatTok.MustBreakBefore) {
      Current.MustBreakBefore = true;
    } else {
      if (Current.Type == TT_LineComment) {
        Current.MustBreakBefore = Current.FormatTok.NewlinesBefore > 0;
      } else if ((Current.Parent->is(tok::comment) &&
                  Current.FormatTok.NewlinesBefore > 0) ||
                 (Current.is(tok::string_literal) &&
                  Current.Parent->is(tok::string_literal))) {
        Current.MustBreakBefore = true;
      } else {
        Current.MustBreakBefore = false;
      }
    }
    Current.CanBreakBefore = Current.MustBreakBefore || canBreakBefore(Current);
    if (Current.MustBreakBefore)
      Current.TotalLength = Current.Parent->TotalLength + Style.ColumnLimit;
    else
      Current.TotalLength =
          Current.Parent->TotalLength + Current.FormatTok.TokenLength +
          (Current.SpaceRequiredBefore ? 1 : 0);
    if (!Current.Children.empty())
      calculateExtraInformation(Current.Children[0]);
  }

  void annotate() {
    AnnotatingParser Parser(Line.First);
    Line.Type = Parser.parseLine();
    if (Line.Type == LT_Invalid)
      return;

    bool LookForFunctionName = Line.MustBeDeclaration;
    determineTokenTypes(Line.First, /*IsExpression=*/ false,
                        LookForFunctionName);

    if (Line.First.Type == TT_ObjCMethodSpecifier)
      Line.Type = LT_ObjCMethodDecl;
    else if (Line.First.Type == TT_ObjCDecl)
      Line.Type = LT_ObjCDecl;
    else if (Line.First.Type == TT_ObjCProperty)
      Line.Type = LT_ObjCProperty;

    Line.First.SpaceRequiredBefore = true;
    Line.First.MustBreakBefore = Line.First.FormatTok.MustBreakBefore;
    Line.First.CanBreakBefore = Line.First.MustBreakBefore;

    Line.First.TotalLength = Line.First.FormatTok.TokenLength;
    if (!Line.First.Children.empty())
      calculateExtraInformation(Line.First.Children[0]);
  }

private:
  void determineTokenTypes(AnnotatedToken &Current, bool IsExpression,
                           bool LookForFunctionName) {
    if (getPrecedence(Current) == prec::Assignment) {
      IsExpression = true;
      AnnotatedToken *Previous = Current.Parent;
      while (Previous != NULL) {
        if (Previous->Type == TT_BinaryOperator &&
            (Previous->is(tok::star) || Previous->is(tok::amp))) {
          Previous->Type = TT_PointerOrReference;
        }
        Previous = Previous->Parent;
      }
    }
    if (Current.is(tok::kw_return) || Current.is(tok::kw_throw) ||
        (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
         (Current.Parent == NULL || Current.Parent->isNot(tok::kw_for))))
      IsExpression = true;

    if (Current.Type == TT_Unknown) {
      if (LookForFunctionName && Current.is(tok::l_paren)) {
        findFunctionName(&Current);
        LookForFunctionName = false;<commit_msg>Calculate the split penalty upfront.<commit_after>//===--- Format.cpp - Format C++ code -------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief This file implements functions declared in Format.h. This will be
/// split into separate files as we go.
///
/// This is EXPERIMENTAL code under heavy development. It is not in a state yet,
/// where it can be used to format real code.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "format-formatter"

#include "UnwrappedLineParser.h"
#include "clang/Basic/Diagnostic.h"
#include "clang/Basic/OperatorPrecedence.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Format/Format.h"
#include "clang/Frontend/TextDiagnosticPrinter.h"
#include "clang/Lex/Lexer.h"
#include "llvm/Support/Debug.h"
#include <string>

// Uncomment to get debug output from tests:
// #define DEBUG_WITH_TYPE(T, X) do { X; } while(0)

namespace clang {
namespace format {

enum TokenType {
  TT_BinaryOperator,
  TT_BlockComment,
  TT_CastRParen,
  TT_ConditionalExpr,
  TT_CtorInitializerColon,
  TT_ImplicitStringLiteral,
  TT_LineComment,
  TT_ObjCBlockLParen,
  TT_ObjCDecl,
  TT_ObjCMethodSpecifier,
  TT_ObjCMethodExpr,
  TT_ObjCProperty,
  TT_OverloadedOperator,
  TT_PointerOrReference,
  TT_PureVirtualSpecifier,
  TT_RangeBasedForLoopColon,
  TT_StartOfName,
  TT_TemplateCloser,
  TT_TemplateOpener,
  TT_TrailingUnaryOperator,
  TT_UnaryOperator,
  TT_Unknown
};

enum LineType {
  LT_Invalid,
  LT_Other,
  LT_BuilderTypeCall,
  LT_PreprocessorDirective,
  LT_VirtualFunctionDecl,
  LT_ObjCDecl, // An @interface, @implementation, or @protocol line.
  LT_ObjCMethodDecl,
  LT_ObjCProperty // An @property line.
};

class AnnotatedToken {
public:
  explicit AnnotatedToken(const FormatToken &FormatTok)
      : FormatTok(FormatTok), Type(TT_Unknown), SpaceRequiredBefore(false),
        CanBreakBefore(false), MustBreakBefore(false),
        ClosesTemplateDeclaration(false), MatchingParen(NULL),
        ParameterCount(1), Parent(NULL) {
  }

  bool is(tok::TokenKind Kind) const { return FormatTok.Tok.is(Kind); }
  bool isNot(tok::TokenKind Kind) const { return FormatTok.Tok.isNot(Kind); }

  bool isObjCAtKeyword(tok::ObjCKeywordKind Kind) const {
    return FormatTok.Tok.isObjCAtKeyword(Kind);
  }

  FormatToken FormatTok;

  TokenType Type;

  bool SpaceRequiredBefore;
  bool CanBreakBefore;
  bool MustBreakBefore;

  bool ClosesTemplateDeclaration;

  AnnotatedToken *MatchingParen;

  /// \brief Number of parameters, if this is "(", "[" or "<".
  ///
  /// This is initialized to 1 as we don't need to distinguish functions with
  /// 0 parameters from functions with 1 parameter. Thus, we can simply count
  /// the number of commas.
  unsigned ParameterCount;

  /// \brief The total length of the line up to and including this token.
  unsigned TotalLength;

  /// \brief Penalty for inserting a line break before this token.
  unsigned SplitPenalty;

  std::vector<AnnotatedToken> Children;
  AnnotatedToken *Parent;

  const AnnotatedToken *getPreviousNoneComment() const {
    AnnotatedToken *Tok = Parent;
    while (Tok != NULL && Tok->is(tok::comment))
      Tok = Tok->Parent;
    return Tok;
  }
};

class AnnotatedLine {
public:
  AnnotatedLine(const UnwrappedLine &Line)
      : First(Line.Tokens.front()), Level(Line.Level),
        InPPDirective(Line.InPPDirective),
        MustBeDeclaration(Line.MustBeDeclaration) {
    assert(!Line.Tokens.empty());
    AnnotatedToken *Current = &First;
    for (std::list<FormatToken>::const_iterator I = ++Line.Tokens.begin(),
                                                E = Line.Tokens.end();
         I != E; ++I) {
      Current->Children.push_back(AnnotatedToken(*I));
      Current->Children[0].Parent = Current;
      Current = &Current->Children[0];
    }
    Last = Current;
  }
  AnnotatedLine(const AnnotatedLine &Other)
      : First(Other.First), Type(Other.Type), Level(Other.Level),
        InPPDirective(Other.InPPDirective),
        MustBeDeclaration(Other.MustBeDeclaration) {
    Last = &First;
    while (!Last->Children.empty()) {
      Last->Children[0].Parent = Last;
      Last = &Last->Children[0];
    }
  }

  AnnotatedToken First;
  AnnotatedToken *Last;

  LineType Type;
  unsigned Level;
  bool InPPDirective;
  bool MustBeDeclaration;
};

static prec::Level getPrecedence(const AnnotatedToken &Tok) {
  return getBinOpPrecedence(Tok.FormatTok.Tok.getKind(), true, true);
}

bool isBinaryOperator(const AnnotatedToken &Tok) {
  // Comma is a binary operator, but does not behave as such wrt. formatting.
  return getPrecedence(Tok) > prec::Comma;
}

FormatStyle getLLVMStyle() {
  FormatStyle LLVMStyle;
  LLVMStyle.ColumnLimit = 80;
  LLVMStyle.MaxEmptyLinesToKeep = 1;
  LLVMStyle.PointerAndReferenceBindToType = false;
  LLVMStyle.AccessModifierOffset = -2;
  LLVMStyle.SplitTemplateClosingGreater = true;
  LLVMStyle.IndentCaseLabels = false;
  LLVMStyle.SpacesBeforeTrailingComments = 1;
  LLVMStyle.BinPackParameters = true;
  LLVMStyle.AllowAllParametersOnNextLine = true;
  LLVMStyle.AllowReturnTypeOnItsOwnLine = true;
  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
  return LLVMStyle;
}

FormatStyle getGoogleStyle() {
  FormatStyle GoogleStyle;
  GoogleStyle.ColumnLimit = 80;
  GoogleStyle.MaxEmptyLinesToKeep = 1;
  GoogleStyle.PointerAndReferenceBindToType = true;
  GoogleStyle.AccessModifierOffset = -1;
  GoogleStyle.SplitTemplateClosingGreater = false;
  GoogleStyle.IndentCaseLabels = true;
  GoogleStyle.SpacesBeforeTrailingComments = 2;
  GoogleStyle.BinPackParameters = false;
  GoogleStyle.AllowAllParametersOnNextLine = true;
  GoogleStyle.AllowReturnTypeOnItsOwnLine = false;
  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
  GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
  return GoogleStyle;
}

FormatStyle getChromiumStyle() {
  FormatStyle ChromiumStyle = getGoogleStyle();
  ChromiumStyle.AllowAllParametersOnNextLine = false;
  return ChromiumStyle;
}

struct OptimizationParameters {
  unsigned PenaltyIndentLevel;
  unsigned PenaltyExcessCharacter;
};

/// \brief Manages the whitespaces around tokens and their replacements.
///
/// This includes special handling for certain constructs, e.g. the alignment of
/// trailing line comments.
class WhitespaceManager {
public:
  WhitespaceManager(SourceManager &SourceMgr) : SourceMgr(SourceMgr) {}

  /// \brief Replaces the whitespace in front of \p Tok. Only call once for
  /// each \c AnnotatedToken.
  void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
                         unsigned Spaces, unsigned WhitespaceStartColumn,
                         const FormatStyle &Style) {
    // 2+ newlines mean an empty line separating logic scopes.
    if (NewLines >= 2)
      alignComments();

    // Align line comments if they are trailing or if they continue other
    // trailing comments.
    if (Tok.Type == TT_LineComment &&
        (Tok.Parent != NULL || !Comments.empty())) {
      if (Style.ColumnLimit >=
          Spaces + WhitespaceStartColumn + Tok.FormatTok.TokenLength) {
        Comments.push_back(StoredComment());
        Comments.back().Tok = Tok.FormatTok;
        Comments.back().Spaces = Spaces;
        Comments.back().NewLines = NewLines;
        Comments.back().MinColumn = WhitespaceStartColumn + Spaces;
        Comments.back().MaxColumn =
            Style.ColumnLimit - Spaces - Tok.FormatTok.TokenLength;
        return;
      }
    }

    // If this line does not have a trailing comment, align the stored comments.
    if (Tok.Children.empty() && Tok.Type != TT_LineComment)
      alignComments();
    storeReplacement(Tok.FormatTok,
                     std::string(NewLines, '\n') + std::string(Spaces, ' '));
  }

  /// \brief Like \c replaceWhitespace, but additionally adds right-aligned
  /// backslashes to escape newlines inside a preprocessor directive.
  ///
  /// This function and \c replaceWhitespace have the same behavior if
  /// \c Newlines == 0.
  void replacePPWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
                           unsigned Spaces, unsigned WhitespaceStartColumn,
                           const FormatStyle &Style) {
    std::string NewLineText;
    if (NewLines > 0) {
      unsigned Offset =
          std::min<int>(Style.ColumnLimit - 1, WhitespaceStartColumn);
      for (unsigned i = 0; i < NewLines; ++i) {
        NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' ');
        NewLineText += "\\\n";
        Offset = 0;
      }
    }
    storeReplacement(Tok.FormatTok, NewLineText + std::string(Spaces, ' '));
  }

  /// \brief Returns all the \c Replacements created during formatting.
  const tooling::Replacements &generateReplacements() {
    alignComments();
    return Replaces;
  }

private:
  /// \brief Structure to store a comment for later layout and alignment.
  struct StoredComment {
    FormatToken Tok;
    unsigned MinColumn;
    unsigned MaxColumn;
    unsigned NewLines;
    unsigned Spaces;
  };
  SmallVector<StoredComment, 16> Comments;
  typedef SmallVector<StoredComment, 16>::iterator comment_iterator;

  /// \brief Try to align all stashed comments.
  void alignComments() {
    unsigned MinColumn = 0;
    unsigned MaxColumn = UINT_MAX;
    comment_iterator Start = Comments.begin();
    for (comment_iterator I = Comments.begin(), E = Comments.end(); I != E;
         ++I) {
      if (I->MinColumn > MaxColumn || I->MaxColumn < MinColumn) {
        alignComments(Start, I, MinColumn);
        MinColumn = I->MinColumn;
        MaxColumn = I->MaxColumn;
        Start = I;
      } else {
        MinColumn = std::max(MinColumn, I->MinColumn);
        MaxColumn = std::min(MaxColumn, I->MaxColumn);
      }
    }
    alignComments(Start, Comments.end(), MinColumn);
    Comments.clear();
  }

  /// \brief Put all the comments between \p I and \p E into \p Column.
  void alignComments(comment_iterator I, comment_iterator E, unsigned Column) {
    while (I != E) {
      unsigned Spaces = I->Spaces + Column - I->MinColumn;
      storeReplacement(I->Tok, std::string(I->NewLines, '\n') +
                       std::string(Spaces, ' '));
      ++I;
    }
  }

  /// \brief Stores \p Text as the replacement for the whitespace in front of
  /// \p Tok.
  void storeReplacement(const FormatToken &Tok, const std::string Text) {
    Replaces.insert(tooling::Replacement(SourceMgr, Tok.WhiteSpaceStart,
                                         Tok.WhiteSpaceLength, Text));
  }

  SourceManager &SourceMgr;
  tooling::Replacements Replaces;
};

/// \brief Returns if a token is an Objective-C selector name.
///
/// For example, "bar" is a selector name in [foo bar:(4 + 5)].
static bool isObjCSelectorName(const AnnotatedToken &Tok) {
  return Tok.is(tok::identifier) && !Tok.Children.empty() &&
         Tok.Children[0].is(tok::colon) &&
         Tok.Children[0].Type == TT_ObjCMethodExpr;
}

class UnwrappedLineFormatter {
public:
  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
                         const AnnotatedLine &Line, unsigned FirstIndent,
                         const AnnotatedToken &RootToken,
                         WhitespaceManager &Whitespaces, bool StructuralError)
      : Style(Style), SourceMgr(SourceMgr), Line(Line),
        FirstIndent(FirstIndent), RootToken(RootToken),
        Whitespaces(Whitespaces) {
    Parameters.PenaltyIndentLevel = 20;
    Parameters.PenaltyExcessCharacter = 1000000;
  }

  /// \brief Formats an \c UnwrappedLine.
  ///
  /// \returns The column after the last token in the last line of the
  /// \c UnwrappedLine.
  unsigned format() {
    // Initialize state dependent on indent.
    LineState State;
    State.Column = FirstIndent;
    State.NextToken = &RootToken;
    State.Stack.push_back(ParenState(FirstIndent + 4, FirstIndent));
    State.VariablePos = 0;
    State.LineContainsContinuedForLoopSection = false;

    DEBUG({
      DebugTokenState(*State.NextToken);
    });

    // The first token has already been indented and thus consumed.
    moveStateToNextToken(State);

    // Start iterating at 1 as we have correctly formatted of Token #0 above.
    while (State.NextToken != NULL) {
      if (State.NextToken->Type == TT_ImplicitStringLiteral) {
        // Calculating the column is important for aligning trailing comments.
        // FIXME: This does not seem to happen in conjunction with escaped
        // newlines. If it does, fix!
        State.Column += State.NextToken->FormatTok.WhiteSpaceLength +
                        State.NextToken->FormatTok.TokenLength;
        State.NextToken = State.NextToken->Children.empty()
            ? NULL : &State.NextToken->Children[0];
      } else if (Line.Last->TotalLength <= getColumnLimit() - FirstIndent) {
        addTokenToState(false, false, State);
      } else {
        unsigned NoBreak = calcPenalty(State, false, UINT_MAX);
        unsigned Break = calcPenalty(State, true, NoBreak);
        DEBUG({
          if (Break < NoBreak)
            llvm::errs() << "\n";
          else
            llvm::errs() << " ";
          llvm::errs() << "<";
          DebugPenalty(Break, Break < NoBreak);
          llvm::errs() << "/";
          DebugPenalty(NoBreak, !(Break < NoBreak));
          llvm::errs() << "> ";
          DebugTokenState(*State.NextToken);
        });
        addTokenToState(Break < NoBreak, false, State);
        if (State.NextToken != NULL &&
            State.NextToken->Parent->Type == TT_CtorInitializerColon) {
          if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine &&
              Line.Last->TotalLength > getColumnLimit() - State.Column - 1)
            State.Stack.back().BreakAfterComma = true;
        }
      }
    }
    DEBUG(llvm::errs() << "\n");
    return State.Column;
  }

private:
  void DebugTokenState(const AnnotatedToken &AnnotatedTok) {
    const Token &Tok = AnnotatedTok.FormatTok.Tok;
    llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
                              Tok.getLength());
    llvm::errs();
  }

  void DebugPenalty(unsigned Penalty, bool Winner) {
    llvm::errs().changeColor(Winner ? raw_ostream::GREEN : raw_ostream::RED);
    if (Penalty == UINT_MAX)
      llvm::errs() << "MAX";
    else
      llvm::errs() << Penalty;
    llvm::errs().resetColor();
  }

  struct ParenState {
    ParenState(unsigned Indent, unsigned LastSpace)
        : Indent(Indent), LastSpace(LastSpace), AssignmentColumn(0),
          FirstLessLess(0), BreakBeforeClosingBrace(false), QuestionColumn(0),
          BreakAfterComma(false), HasMultiParameterLine(false) {
    }

    /// \brief The position to which a specific parenthesis level needs to be
    /// indented.
    unsigned Indent;

    /// \brief The position of the last space on each level.
    ///
    /// Used e.g. to break like:
    /// functionCall(Parameter, otherCall(
    ///                             OtherParameter));
    unsigned LastSpace;

    /// \brief This is the column of the first token after an assignment.
    unsigned AssignmentColumn;

    /// \brief The position the first "<<" operator encountered on each level.
    ///
    /// Used to align "<<" operators. 0 if no such operator has been encountered
    /// on a level.
    unsigned FirstLessLess;

    /// \brief Whether a newline needs to be inserted before the block's closing
    /// brace.
    ///
    /// We only want to insert a newline before the closing brace if there also
    /// was a newline after the beginning left brace.
    bool BreakBeforeClosingBrace;

    /// \brief The column of a \c ? in a conditional expression;
    unsigned QuestionColumn;

    bool BreakAfterComma;
    bool HasMultiParameterLine;

    bool operator<(const ParenState &Other) const {
      if (Indent != Other.Indent)
        return Indent < Other.Indent;
      if (LastSpace != Other.LastSpace)
        return LastSpace < Other.LastSpace;
      if (AssignmentColumn != Other.AssignmentColumn)
        return AssignmentColumn < Other.AssignmentColumn;
      if (FirstLessLess != Other.FirstLessLess)
        return FirstLessLess < Other.FirstLessLess;
      if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
        return BreakBeforeClosingBrace;
      if (QuestionColumn != Other.QuestionColumn)
        return QuestionColumn < Other.QuestionColumn;
      if (BreakAfterComma != Other.BreakAfterComma)
        return BreakAfterComma;
      if (HasMultiParameterLine != Other.HasMultiParameterLine)
        return HasMultiParameterLine;
      return false;
    }
  };

  /// \brief The current state when indenting a unwrapped line.
  ///
  /// As the indenting tries different combinations this is copied by value.
  struct LineState {
    /// \brief The number of used columns in the current line.
    unsigned Column;

    /// \brief The token that needs to be next formatted.
    const AnnotatedToken *NextToken;

    /// \brief The column of the first variable name in a variable declaration.
    ///
    /// Used to align further variables if necessary.
    unsigned VariablePos;

    /// \brief \c true if this line contains a continued for-loop section.
    bool LineContainsContinuedForLoopSection;

    /// \brief A stack keeping track of properties applying to parenthesis
    /// levels.
    std::vector<ParenState> Stack;

    /// \brief Comparison operator to be able to used \c LineState in \c map.
    bool operator<(const LineState &Other) const {
      if (Other.NextToken != NextToken)
        return Other.NextToken > NextToken;
      if (Other.Column != Column)
        return Other.Column > Column;
      if (Other.VariablePos != VariablePos)
        return Other.VariablePos < VariablePos;
      if (Other.LineContainsContinuedForLoopSection !=
          LineContainsContinuedForLoopSection)
        return LineContainsContinuedForLoopSection;
      return Other.Stack < Stack;
    }
  };

  /// \brief Appends the next token to \p State and updates information
  /// necessary for indentation.
  ///
  /// Puts the token on the current line if \p Newline is \c true and adds a
  /// line break and necessary indentation otherwise.
  ///
  /// If \p DryRun is \c false, also creates and stores the required
  /// \c Replacement.
  void addTokenToState(bool Newline, bool DryRun, LineState &State) {
    const AnnotatedToken &Current = *State.NextToken;
    const AnnotatedToken &Previous = *State.NextToken->Parent;
    assert(State.Stack.size());
    unsigned ParenLevel = State.Stack.size() - 1;

    if (Newline) {
      unsigned WhitespaceStartColumn = State.Column;
      if (Current.is(tok::r_brace)) {
        State.Column = Line.Level * 2;
      } else if (Current.is(tok::string_literal) &&
                 Previous.is(tok::string_literal)) {
        State.Column = State.Column - Previous.FormatTok.TokenLength;
      } else if (Current.is(tok::lessless) &&
                 State.Stack[ParenLevel].FirstLessLess != 0) {
        State.Column = State.Stack[ParenLevel].FirstLessLess;
      } else if (ParenLevel != 0 &&
                 (Previous.is(tok::equal) || Previous.is(tok::coloncolon) ||
                  Current.is(tok::period) || Current.is(tok::arrow) ||
                  Current.is(tok::question))) {
        // Indent and extra 4 spaces after if we know the current expression is
        // continued.  Don't do that on the top level, as we already indent 4
        // there.
        State.Column = std::max(State.Stack.back().LastSpace,
                                State.Stack.back().Indent) + 4;
      } else if (Current.Type == TT_ConditionalExpr) {
        State.Column = State.Stack.back().QuestionColumn;
      } else if (Previous.is(tok::comma) && State.VariablePos != 0 &&
                 ((RootToken.is(tok::kw_for) && ParenLevel == 1) ||
                  ParenLevel == 0)) {
        State.Column = State.VariablePos;
      } else if (State.NextToken->Parent->ClosesTemplateDeclaration ||
                 Current.Type == TT_StartOfName) {
        State.Column = State.Stack[ParenLevel].Indent - 4;
      } else if (Previous.Type == TT_BinaryOperator &&
                 State.Stack.back().AssignmentColumn != 0) {
        State.Column = State.Stack.back().AssignmentColumn;
      } else {
        State.Column = State.Stack[ParenLevel].Indent;
      }

      if (RootToken.is(tok::kw_for))
        State.LineContainsContinuedForLoopSection = Previous.isNot(tok::semi);

      if (!DryRun) {
        if (!Line.InPPDirective)
          Whitespaces.replaceWhitespace(Current, 1, State.Column,
                                        WhitespaceStartColumn, Style);
        else
          Whitespaces.replacePPWhitespace(Current, 1, State.Column,
                                          WhitespaceStartColumn, Style);
      }

      State.Stack[ParenLevel].LastSpace = State.Column;
      if (Current.is(tok::colon) && Current.Type != TT_ConditionalExpr)
        State.Stack[ParenLevel].Indent += 2;
    } else {
      if (Current.is(tok::equal) &&
          (RootToken.is(tok::kw_for) || ParenLevel == 0))
        State.VariablePos = State.Column - Previous.FormatTok.TokenLength;

      unsigned Spaces = State.NextToken->SpaceRequiredBefore ? 1 : 0;
      if (State.NextToken->Type == TT_LineComment)
        Spaces = Style.SpacesBeforeTrailingComments;

      if (!DryRun)
        Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column, Style);

      // FIXME: Do we need to do this for assignments nested in other
      // expressions?
      if (RootToken.isNot(tok::kw_for) && ParenLevel == 0 &&
          (getPrecedence(Previous) == prec::Assignment ||
           Previous.is(tok::kw_return)))
        State.Stack.back().AssignmentColumn = State.Column + Spaces;
      if (Previous.is(tok::l_paren) || Previous.is(tok::l_brace) ||
          State.NextToken->Parent->Type == TT_TemplateOpener)
        State.Stack[ParenLevel].Indent = State.Column + Spaces;
      if (Current.getPreviousNoneComment() != NULL &&
          Current.getPreviousNoneComment()->is(tok::comma) &&
          Current.isNot(tok::comment))
        State.Stack[ParenLevel].HasMultiParameterLine = true;

      State.Column += Spaces;
      if (Current.is(tok::l_paren) && Previous.is(tok::kw_if))
        // Treat the condition inside an if as if it was a second function
        // parameter, i.e. let nested calls have an indent of 4.
        State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(".
      else if (Previous.is(tok::comma) && ParenLevel != 0)
        // Top-level spaces are exempt as that mostly leads to better results.
        State.Stack.back().LastSpace = State.Column;
      else if ((Previous.Type == TT_BinaryOperator ||
                Previous.Type == TT_ConditionalExpr ||
                Previous.Type == TT_CtorInitializerColon) &&
               getPrecedence(Previous) != prec::Assignment)
        State.Stack.back().LastSpace = State.Column;
      else if (Previous.ParameterCount > 1 &&
               (Previous.is(tok::l_paren) || Previous.is(tok::l_square) ||
                Previous.Type == TT_TemplateOpener))
        // If this function has multiple parameters, indent nested calls from
        // the start of the first parameter.
        State.Stack.back().LastSpace = State.Column;
    }

    // If we break after an {, we should also break before the corresponding }.
    if (Newline && Previous.is(tok::l_brace))
      State.Stack.back().BreakBeforeClosingBrace = true;

    if (!Style.BinPackParameters && Newline) {
      // If we are breaking after '(', '{', '<', this is not bin packing unless
      // AllowAllParametersOnNextLine is false.
      if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace) &&
           Previous.Type != TT_TemplateOpener) ||
          !Style.AllowAllParametersOnNextLine)
        State.Stack.back().BreakAfterComma = true;

      // Any break on this level means that the parent level has been broken
      // and we need to avoid bin packing there.
      for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) {
        State.Stack[i].BreakAfterComma = true;
      }
    }

    moveStateToNextToken(State);
  }

  /// \brief Mark the next token as consumed in \p State and modify its stacks
  /// accordingly.
  void moveStateToNextToken(LineState &State) {
    const AnnotatedToken &Current = *State.NextToken;
    assert(State.Stack.size());

    if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
      State.Stack.back().FirstLessLess = State.Column;
    if (Current.is(tok::question))
      State.Stack.back().QuestionColumn = State.Column;

    // If we encounter an opening (, [, { or <, we add a level to our stacks to
    // prepare for the following tokens.
    if (Current.is(tok::l_paren) || Current.is(tok::l_square) ||
        Current.is(tok::l_brace) ||
        State.NextToken->Type == TT_TemplateOpener) {
      unsigned NewIndent;
      if (Current.is(tok::l_brace)) {
        // FIXME: This does not work with nested static initializers.
        // Implement a better handling for static initializers and similar
        // constructs.
        NewIndent = Line.Level * 2 + 2;
      } else {
        NewIndent = 4 + State.Stack.back().LastSpace;
      }
      State.Stack.push_back(ParenState(NewIndent,
                                       State.Stack.back().LastSpace));
    }

    // If we encounter a closing ), ], } or >, we can remove a level from our
    // stacks.
    if (Current.is(tok::r_paren) || Current.is(tok::r_square) ||
        (Current.is(tok::r_brace) && State.NextToken != &RootToken) ||
        State.NextToken->Type == TT_TemplateCloser) {
      State.Stack.pop_back();
    }

    if (State.NextToken->Children.empty())
      State.NextToken = NULL;
    else
      State.NextToken = &State.NextToken->Children[0];

    State.Column += Current.FormatTok.TokenLength;
  }

  unsigned getColumnLimit() {
    return Style.ColumnLimit - (Line.InPPDirective ? 1 : 0);
  }

  /// \brief Calculate the number of lines needed to format the remaining part
  /// of the unwrapped line.
  ///
  /// Assumes the formatting so far has led to
  /// the \c LineSta \p State. If \p NewLine is set, a new line will be
  /// added after the previous token.
  ///
  /// \param StopAt is used for optimization. If we can determine that we'll
  /// definitely need at least \p StopAt additional lines, we already know of a
  /// better solution.
  unsigned calcPenalty(LineState State, bool NewLine, unsigned StopAt) {
    // We are at the end of the unwrapped line, so we don't need any more lines.
    if (State.NextToken == NULL)
      return 0;

    if (!NewLine && State.NextToken->MustBreakBefore)
      return UINT_MAX;
    if (NewLine && !State.NextToken->CanBreakBefore &&
        !(State.NextToken->is(tok::r_brace) &&
          State.Stack.back().BreakBeforeClosingBrace))
      return UINT_MAX;
    if (!NewLine && State.NextToken->is(tok::r_brace) &&
        State.Stack.back().BreakBeforeClosingBrace)
      return UINT_MAX;
    if (!NewLine && State.NextToken->Parent->is(tok::semi) &&
        State.LineContainsContinuedForLoopSection)
      return UINT_MAX;
    if (!NewLine && State.NextToken->Parent->is(tok::comma) &&
        State.NextToken->isNot(tok::comment) &&
        State.Stack.back().BreakAfterComma)
      return UINT_MAX;
    // Trying to insert a parameter on a new line if there are already more than
    // one parameter on the current line is bin packing.
    if (NewLine && State.NextToken->Parent->is(tok::comma) &&
        State.Stack.back().HasMultiParameterLine && !Style.BinPackParameters)
      return UINT_MAX;
    if (!NewLine && (State.NextToken->Type == TT_CtorInitializerColon ||
                     (State.NextToken->Parent->ClosesTemplateDeclaration &&
                      State.Stack.size() == 1)))
      return UINT_MAX;

    unsigned CurrentPenalty = 0;
    if (NewLine)
      CurrentPenalty += Parameters.PenaltyIndentLevel * State.Stack.size() +
                        State.NextToken->SplitPenalty;

    addTokenToState(NewLine, true, State);

    // Exceeding column limit is bad, assign penalty.
    if (State.Column > getColumnLimit()) {
      unsigned ExcessCharacters = State.Column - getColumnLimit();
      CurrentPenalty += Parameters.PenaltyExcessCharacter * ExcessCharacters;
    }

    if (StopAt <= CurrentPenalty)
      return UINT_MAX;
    StopAt -= CurrentPenalty;
    StateMap::iterator I = Memory.find(State);
    if (I != Memory.end()) {
      // If this state has already been examined, we can safely return the
      // previous result if we
      // - have not hit the optimatization (and thus returned UINT_MAX) OR
      // - are now computing for a smaller or equal StopAt.
      unsigned SavedResult = I->second.first;
      unsigned SavedStopAt = I->second.second;
      if (SavedResult != UINT_MAX)
        return SavedResult + CurrentPenalty;
      else if (StopAt <= SavedStopAt)
        return UINT_MAX;
    }

    unsigned NoBreak = calcPenalty(State, false, StopAt);
    unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, NoBreak));
    unsigned Result = std::min(NoBreak, WithBreak);

    // We have to store 'Result' without adding 'CurrentPenalty' as the latter
    // can depend on 'NewLine'.
    Memory[State] = std::pair<unsigned, unsigned>(Result, StopAt);

    return Result == UINT_MAX ? UINT_MAX : Result + CurrentPenalty;
  }

  FormatStyle Style;
  SourceManager &SourceMgr;
  const AnnotatedLine &Line;
  const unsigned FirstIndent;
  const AnnotatedToken &RootToken;
  WhitespaceManager &Whitespaces;

  // A map from an indent state to a pair (Result, Used-StopAt).
  typedef std::map<LineState, std::pair<unsigned, unsigned> > StateMap;
  StateMap Memory;

  OptimizationParameters Parameters;
};

/// \brief Determines extra information about the tokens comprising an
/// \c UnwrappedLine.
class TokenAnnotator {
public:
  TokenAnnotator(const FormatStyle &Style, SourceManager &SourceMgr, Lexer &Lex,
                 AnnotatedLine &Line)
      : Style(Style), SourceMgr(SourceMgr), Lex(Lex), Line(Line) {
  }

  /// \brief A parser that gathers additional information about tokens.
  ///
  /// The \c TokenAnnotator tries to matches parenthesis and square brakets and
  /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
  /// into template parameter lists.
  class AnnotatingParser {
  public:
    AnnotatingParser(AnnotatedToken &RootToken)
        : CurrentToken(&RootToken), KeywordVirtualFound(false),
          ColonIsObjCMethodExpr(false), ColonIsForRangeExpr(false) {
    }

    /// \brief A helper class to manage AnnotatingParser::ColonIsObjCMethodExpr.
    struct ObjCSelectorRAII {
      AnnotatingParser &P;
      bool ColonWasObjCMethodExpr;

      ObjCSelectorRAII(AnnotatingParser &P)
          : P(P), ColonWasObjCMethodExpr(P.ColonIsObjCMethodExpr) {
      }

      ~ObjCSelectorRAII() { P.ColonIsObjCMethodExpr = ColonWasObjCMethodExpr; }

      void markStart(AnnotatedToken &Left) {
        P.ColonIsObjCMethodExpr = true;
        Left.Type = TT_ObjCMethodExpr;
      }

      void markEnd(AnnotatedToken &Right) { Right.Type = TT_ObjCMethodExpr; }
    };

    bool parseAngle() {
      if (CurrentToken == NULL)
        return false;
      AnnotatedToken *Left = CurrentToken->Parent;
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::greater)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          CurrentToken->Type = TT_TemplateCloser;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square) ||
            CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::pipepipe) || CurrentToken->is(tok::ampamp) ||
            CurrentToken->is(tok::question) || CurrentToken->is(tok::colon))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseParens(bool LookForDecls = false) {
      if (CurrentToken == NULL)
        return false;
      bool StartsObjCMethodExpr = false;
      AnnotatedToken *Left = CurrentToken->Parent;
      if (CurrentToken->is(tok::caret)) {
        // ^( starts a block.
        Left->Type = TT_ObjCBlockLParen;
      } else if (AnnotatedToken *MaybeSel = Left->Parent) {
        // @selector( starts a selector.
        if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Parent &&
            MaybeSel->Parent->is(tok::at)) {
          StartsObjCMethodExpr = true;
        }
      }

      ObjCSelectorRAII objCSelector(*this);
      if (StartsObjCMethodExpr)
        objCSelector.markStart(*Left);

      while (CurrentToken != NULL) {
        // LookForDecls is set when "if (" has been seen. Check for
        // 'identifier' '*' 'identifier' followed by not '=' -- this
        // '*' has to be a binary operator but determineStarAmpUsage() will
        // categorize it as an unary operator, so set the right type here.
        if (LookForDecls && !CurrentToken->Children.empty()) {
          AnnotatedToken &Prev = *CurrentToken->Parent;
          AnnotatedToken &Next = CurrentToken->Children[0];
          if (Prev.Parent->is(tok::identifier) &&
              (Prev.is(tok::star) || Prev.is(tok::amp)) &&
              CurrentToken->is(tok::identifier) && Next.isNot(tok::equal)) {
            Prev.Type = TT_BinaryOperator;
            LookForDecls = false;
          }
        }

        if (CurrentToken->is(tok::r_paren)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;

          if (StartsObjCMethodExpr)
            objCSelector.markEnd(*CurrentToken);

          next();
          return true;
        }
        if (CurrentToken->is(tok::r_square) || CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseSquare() {
      if (!CurrentToken)
        return false;

      // A '[' could be an index subscript (after an indentifier or after
      // ')' or ']'), or it could be the start of an Objective-C method
      // expression.
      AnnotatedToken *Left = CurrentToken->Parent;
      bool StartsObjCMethodExpr =
          !Left->Parent || Left->Parent->is(tok::colon) ||
          Left->Parent->is(tok::l_square) || Left->Parent->is(tok::l_paren) ||
          Left->Parent->is(tok::kw_return) || Left->Parent->is(tok::kw_throw) ||
          getBinOpPrecedence(Left->Parent->FormatTok.Tok.getKind(), true,
                             true) > prec::Unknown;

      ObjCSelectorRAII objCSelector(*this);
      if (StartsObjCMethodExpr)
        objCSelector.markStart(*Left);

      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::r_square)) {
          if (!CurrentToken->Children.empty() &&
              CurrentToken->Children[0].is(tok::l_paren)) {
            // An ObjC method call can't be followed by an open parenthesis.
            // FIXME: Do we incorrectly label ":" with this?
            StartsObjCMethodExpr = false;
            Left->Type = TT_Unknown;
          }
          if (StartsObjCMethodExpr)
            objCSelector.markEnd(*CurrentToken);
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_brace))
          return false;
        if (CurrentToken->is(tok::comma))
          ++Left->ParameterCount;
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseBrace() {
      // Lines are fine to end with '{'.
      if (CurrentToken == NULL)
        return true;
      AnnotatedToken *Left = CurrentToken->Parent;
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::r_brace)) {
          Left->MatchingParen = CurrentToken;
          CurrentToken->MatchingParen = Left;
          next();
          return true;
        }
        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square))
          return false;
        if (!consumeToken())
          return false;
      }
      return true;
    }

    bool parseConditional() {
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::colon)) {
          CurrentToken->Type = TT_ConditionalExpr;
          next();
          return true;
        }
        if (!consumeToken())
          return false;
      }
      return false;
    }

    bool parseTemplateDeclaration() {
      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
        CurrentToken->Type = TT_TemplateOpener;
        next();
        if (!parseAngle())
          return false;
        CurrentToken->Parent->ClosesTemplateDeclaration = true;
        return true;
      }
      return false;
    }

    bool consumeToken() {
      AnnotatedToken *Tok = CurrentToken;
      next();
      switch (Tok->FormatTok.Tok.getKind()) {
      case tok::plus:
      case tok::minus:
        // At the start of the line, +/- specific ObjectiveC method
        // declarations.
        if (Tok->Parent == NULL)
          Tok->Type = TT_ObjCMethodSpecifier;
        break;
      case tok::colon:
        // Colons from ?: are handled in parseConditional().
        if (Tok->Parent->is(tok::r_paren))
          Tok->Type = TT_CtorInitializerColon;
        else if (ColonIsObjCMethodExpr)
          Tok->Type = TT_ObjCMethodExpr;
        else if (ColonIsForRangeExpr)
          Tok->Type = TT_RangeBasedForLoopColon;
        break;
      case tok::kw_if:
      case tok::kw_while:
        if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
          next();
          if (!parseParens(/*LookForDecls=*/ true))
            return false;
        }
        break;
      case tok::kw_for:
        ColonIsForRangeExpr = true;
        next();
        if (!parseParens())
          return false;
        break;
      case tok::l_paren:
        if (!parseParens())
          return false;
        break;
      case tok::l_square:
        if (!parseSquare())
          return false;
        break;
      case tok::l_brace:
        if (!parseBrace())
          return false;
        break;
      case tok::less:
        if (parseAngle())
          Tok->Type = TT_TemplateOpener;
        else {
          Tok->Type = TT_BinaryOperator;
          CurrentToken = Tok;
          next();
        }
        break;
      case tok::r_paren:
      case tok::r_square:
        return false;
      case tok::r_brace:
        // Lines can start with '}'.
        if (Tok->Parent != NULL)
          return false;
        break;
      case tok::greater:
        Tok->Type = TT_BinaryOperator;
        break;
      case tok::kw_operator:
        if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
          CurrentToken->Type = TT_OverloadedOperator;
          next();
          if (CurrentToken != NULL && CurrentToken->is(tok::r_paren)) {
            CurrentToken->Type = TT_OverloadedOperator;
            next();
          }
        } else {
          while (CurrentToken != NULL && CurrentToken->isNot(tok::l_paren)) {
            CurrentToken->Type = TT_OverloadedOperator;
            next();
          }
        }
        break;
      case tok::question:
        parseConditional();
        break;
      case tok::kw_template:
        parseTemplateDeclaration();
        break;
      default:
        break;
      }
      return true;
    }

    void parseIncludeDirective() {
      next();
      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
        next();
        while (CurrentToken != NULL) {
          if (CurrentToken->isNot(tok::comment) ||
              !CurrentToken->Children.empty())
            CurrentToken->Type = TT_ImplicitStringLiteral;
          next();
        }
      } else {
        while (CurrentToken != NULL) {
          next();
        }
      }
    }

    void parseWarningOrError() {
      next();
      // We still want to format the whitespace left of the first token of the
      // warning or error.
      next();
      while (CurrentToken != NULL) {
        CurrentToken->Type = TT_ImplicitStringLiteral;
        next();
      }
    }

    void parsePreprocessorDirective() {
      next();
      if (CurrentToken == NULL)
        return;
      // Hashes in the middle of a line can lead to any strange token
      // sequence.
      if (CurrentToken->FormatTok.Tok.getIdentifierInfo() == NULL)
        return;
      switch (
          CurrentToken->FormatTok.Tok.getIdentifierInfo()->getPPKeywordID()) {
      case tok::pp_include:
      case tok::pp_import:
        parseIncludeDirective();
        break;
      case tok::pp_error:
      case tok::pp_warning:
        parseWarningOrError();
        break;
      default:
        break;
      }
    }

    LineType parseLine() {
      int PeriodsAndArrows = 0;
      bool CanBeBuilderTypeStmt = true;
      if (CurrentToken->is(tok::hash)) {
        parsePreprocessorDirective();
        return LT_PreprocessorDirective;
      }
      while (CurrentToken != NULL) {
        if (CurrentToken->is(tok::kw_virtual))
          KeywordVirtualFound = true;
        if (CurrentToken->is(tok::period) || CurrentToken->is(tok::arrow))
          ++PeriodsAndArrows;
        if (getPrecedence(*CurrentToken) > prec::Assignment &&
            CurrentToken->isNot(tok::less) && CurrentToken->isNot(tok::greater))
          CanBeBuilderTypeStmt = false;
        if (!consumeToken())
          return LT_Invalid;
      }
      if (KeywordVirtualFound)
        return LT_VirtualFunctionDecl;

      // Assume a builder-type call if there are 2 or more "." and "->".
      if (PeriodsAndArrows >= 2 && CanBeBuilderTypeStmt)
        return LT_BuilderTypeCall;

      return LT_Other;
    }

    void next() {
      if (CurrentToken != NULL && !CurrentToken->Children.empty())
        CurrentToken = &CurrentToken->Children[0];
      else
        CurrentToken = NULL;
    }

  private:
    AnnotatedToken *CurrentToken;
    bool KeywordVirtualFound;
    bool ColonIsObjCMethodExpr;
    bool ColonIsForRangeExpr;
  };

  void calculateExtraInformation(AnnotatedToken &Current) {
    Current.SpaceRequiredBefore = spaceRequiredBefore(Current);

    if (Current.FormatTok.MustBreakBefore) {
      Current.MustBreakBefore = true;
    } else {
      if (Current.Type == TT_LineComment) {
        Current.MustBreakBefore = Current.FormatTok.NewlinesBefore > 0;
      } else if ((Current.Parent->is(tok::comment) &&
                  Current.FormatTok.NewlinesBefore > 0) ||
                 (Current.is(tok::string_literal) &&
                  Current.Parent->is(tok::string_literal))) {
        Current.MustBreakBefore = true;
      } else {
        Current.MustBreakBefore = false;
      }
    }
    Current.CanBreakBefore = Current.MustBreakBefore || canBreakBefore(Current);
    if (Current.MustBreakBefore)
      Current.TotalLength = Current.Parent->TotalLength + Style.ColumnLimit;
    else
      Current.TotalLength =
          Current.Parent->TotalLength + Current.FormatTok.TokenLength +
          (Current.SpaceRequiredBefore ? 1 : 0);
    if (Current.CanBreakBefore)
      Current.SplitPenalty = splitPenalty(Current);
    if (!Current.Children.empty())
      calculateExtraInformation(Current.Children[0]);
  }

  void annotate() {
    AnnotatingParser Parser(Line.First);
    Line.Type = Parser.parseLine();
    if (Line.Type == LT_Invalid)
      return;

    bool LookForFunctionName = Line.MustBeDeclaration;
    determineTokenTypes(Line.First, /*IsExpression=*/ false,
                        LookForFunctionName);

    if (Line.First.Type == TT_ObjCMethodSpecifier)
      Line.Type = LT_ObjCMethodDecl;
    else if (Line.First.Type == TT_ObjCDecl)
      Line.Type = LT_ObjCDecl;
    else if (Line.First.Type == TT_ObjCProperty)
      Line.Type = LT_ObjCProperty;

    Line.First.SpaceRequiredBefore = true;
    Line.First.MustBreakBefore = Line.First.FormatTok.MustBreakBefore;
    Line.First.CanBreakBefore = Line.First.MustBreakBefore;

    Line.First.TotalLength = Line.First.FormatTok.TokenLength;
    if (!Line.First.Children.empty())
      calculateExtraInformation(Line.First.Children[0]);
  }

private:
  /// \brief Calculate the penalty for splitting before \c Tok.
  unsigned splitPenalty(const AnnotatedToken &Tok) {
    const AnnotatedToken &Left = *Tok.Parent;
    const AnnotatedToken &Right = Tok;

    if (Left.is(tok::l_brace) && Right.isNot(tok::l_brace))
      return 50;
    if (Left.is(tok::equal) && Right.is(tok::l_brace))
      return 150;
    if (Left.is(tok::coloncolon))
      return 500;

    if (Left.Type == TT_RangeBasedForLoopColon)
      return 5;

    if (Right.is(tok::arrow) || Right.is(tok::period)) {
      if (Left.is(tok::r_paren) && Line.Type == LT_BuilderTypeCall)
        return 5; // Should be smaller than breaking at a nested comma.
      return 150;
    }

    // In for-loops, prefer breaking at ',' and ';'.
    if (Line.First.is(tok::kw_for) &&
        (Left.isNot(tok::comma) && Left.isNot(tok::semi)))
      return 20;

    if (Left.is(tok::semi) || Left.is(tok::comma))
      return 0;

    // In Objective-C method expressions, prefer breaking before "param:" over
    // breaking after it.
    if (isObjCSelectorName(Right))
      return 0;
    if (Right.is(tok::colon) && Right.Type == TT_ObjCMethodExpr)
      return 20;

    if (Left.is(tok::l_paren))
      return 20;
    // FIXME: The penalty for a trailing "<" or "[" being higher than the
    // penalty for a trainling "(" is a temporary workaround until we can
    // properly avoid breaking in array subscripts or template parameters.
    if (Left.is(tok::l_square) || Left.Type == TT_TemplateOpener)
      return 50;

    if (Left.Type == TT_ConditionalExpr)
      return prec::Assignment;
    prec::Level Level = getPrecedence(Left);

    if (Level != prec::Unknown)
      return Level;

    return 3;
  }

  void determineTokenTypes(AnnotatedToken &Current, bool IsExpression,
                           bool LookForFunctionName) {
    if (getPrecedence(Current) == prec::Assignment) {
      IsExpression = true;
      AnnotatedToken *Previous = Current.Parent;
      while (Previous != NULL) {
        if (Previous->Type == TT_BinaryOperator &&
            (Previous->is(tok::star) || Previous->is(tok::amp))) {
          Previous->Type = TT_PointerOrReference;
        }
        Previous = Previous->Parent;
      }
    }
    if (Current.is(tok::kw_return) || Current.is(tok::kw_throw) ||
        (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
         (Current.Parent == NULL || Current.Parent->isNot(tok::kw_for))))
      IsExpression = true;

    if (Current.Type == TT_Unknown) {
      if (LookForFunctionName && Current.is(tok::l_paren)) {
        findFunctionName(&Current);
        LookForFunctionName = false;
{'fraction_non_alphanumeric': 0.11885478679765235, 'fraction_numerical': 0.0027031575404421818, 'mean_word_length': 2.5412321215733016, 'pattern_counts': {'":': 2, '<': 115, '<?xml version=': 0, '>': 403, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1032439', 'n_tokens_mistral': 28072, 'n_tokens_neox': 27248, 'n_words': 6764}