contrib/llvm/tools/clang/lib/Format/Format.cpp

   1 //===--- Format.cpp - Format C++ code -------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief This file implements functions declared in Format.h. This will be
  12 /// split into separate files as we go.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "format-formatter"
  17
  18 #include "BreakableToken.h"
  19 #include "TokenAnnotator.h"
  20 #include "UnwrappedLineParser.h"
  21 #include "WhitespaceManager.h"
  22 #include "clang/Basic/Diagnostic.h"
  23 #include "clang/Basic/OperatorPrecedence.h"
  24 #include "clang/Basic/SourceManager.h"
  25 #include "clang/Format/Format.h"
  26 #include "clang/Frontend/TextDiagnosticPrinter.h"
  27 #include "clang/Lex/Lexer.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 #include "llvm/Support/Allocator.h"
  30 #include "llvm/Support/Debug.h"
  31 #include <queue>
  32 #include <string>
  33
  34 namespace clang {
  35 namespace format {
  36
  37 FormatStyle getLLVMStyle() {
  38   FormatStyle LLVMStyle;
  39   LLVMStyle.AccessModifierOffset = -2;
  40   LLVMStyle.AlignEscapedNewlinesLeft = false;
  41   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
  42   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
  43   LLVMStyle.BinPackParameters = true;
  44   LLVMStyle.ColumnLimit = 80;
  45   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
  46   LLVMStyle.DerivePointerBinding = false;
  47   LLVMStyle.IndentCaseLabels = false;
  48   LLVMStyle.MaxEmptyLinesToKeep = 1;
  49   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
  50   LLVMStyle.PenaltyExcessCharacter = 1000000;
  51   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 75;
  52   LLVMStyle.PointerBindsToType = false;
  53   LLVMStyle.SpacesBeforeTrailingComments = 1;
  54   LLVMStyle.Standard = FormatStyle::LS_Cpp03;
  55   return LLVMStyle;
  56 }
  57
  58 FormatStyle getGoogleStyle() {
  59   FormatStyle GoogleStyle;
  60   GoogleStyle.AccessModifierOffset = -1;
  61   GoogleStyle.AlignEscapedNewlinesLeft = true;
  62   GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
  63   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
  64   GoogleStyle.BinPackParameters = true;
  65   GoogleStyle.ColumnLimit = 80;
  66   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
  67   GoogleStyle.DerivePointerBinding = true;
  68   GoogleStyle.IndentCaseLabels = true;
  69   GoogleStyle.MaxEmptyLinesToKeep = 1;
  70   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
  71   GoogleStyle.PenaltyExcessCharacter = 1000000;
  72   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
  73   GoogleStyle.PointerBindsToType = true;
  74   GoogleStyle.SpacesBeforeTrailingComments = 2;
  75   GoogleStyle.Standard = FormatStyle::LS_Auto;
  76   return GoogleStyle;
  77 }
  78
  79 FormatStyle getChromiumStyle() {
  80   FormatStyle ChromiumStyle = getGoogleStyle();
  81   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
  82   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
  83   ChromiumStyle.BinPackParameters = false;
  84   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
  85   ChromiumStyle.DerivePointerBinding = false;
  86   return ChromiumStyle;
  87 }
  88
  89 FormatStyle getMozillaStyle() {
  90   FormatStyle MozillaStyle = getLLVMStyle();
  91   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
  92   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
  93   MozillaStyle.DerivePointerBinding = true;
  94   MozillaStyle.IndentCaseLabels = true;
  95   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
  96   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
  97   MozillaStyle.PointerBindsToType = true;
  98   return MozillaStyle;
  99 }
 100
 101 // Returns the length of everything up to the first possible line break after
 102 // the ), ], } or > matching \c Tok.
 103 static unsigned getLengthToMatchingParen(const AnnotatedToken &Tok) {
 104   if (Tok.MatchingParen == NULL)
 105     return 0;
 106   AnnotatedToken *End = Tok.MatchingParen;
 107   while (!End->Children.empty() && !End->Children[0].CanBreakBefore) {
 108     End = &End->Children[0];
 109   }
 110   return End->TotalLength - Tok.TotalLength + 1;
 111 }
 112
 113 class UnwrappedLineFormatter {
 114 public:
 115   UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
 116                          const AnnotatedLine &Line, unsigned FirstIndent,
 117                          const AnnotatedToken &RootToken,
 118                          WhitespaceManager &Whitespaces)
 119       : Style(Style), SourceMgr(SourceMgr), Line(Line),
 120         FirstIndent(FirstIndent), RootToken(RootToken),
 121         Whitespaces(Whitespaces), Count(0) {}
 122
 123   /// \brief Formats an \c UnwrappedLine.
 124   ///
 125   /// \returns The column after the last token in the last line of the
 126   /// \c UnwrappedLine.
 127   unsigned format(const AnnotatedLine *NextLine) {
 128     // Initialize state dependent on indent.
 129     LineState State;
 130     State.Column = FirstIndent;
 131     State.NextToken = &RootToken;
 132     State.Stack.push_back(
 133         ParenState(FirstIndent, FirstIndent, !Style.BinPackParameters,
 134                    /*NoLineBreak=*/ false));
 135     State.LineContainsContinuedForLoopSection = false;
 136     State.ParenLevel = 0;
 137     State.StartOfStringLiteral = 0;
 138     State.StartOfLineLevel = State.ParenLevel;
 139
 140     // The first token has already been indented and thus consumed.
 141     moveStateToNextToken(State, /*DryRun=*/ false);
 142
 143     // If everything fits on a single line, just put it there.
 144     unsigned ColumnLimit = Style.ColumnLimit;
 145     if (NextLine && NextLine->InPPDirective &&
 146         !NextLine->First.FormatTok.HasUnescapedNewline)
 147       ColumnLimit = getColumnLimit();
 148     if (Line.Last->TotalLength <= ColumnLimit - FirstIndent) {
 149       while (State.NextToken != NULL) {
 150         addTokenToState(false, false, State);
 151       }
 152       return State.Column;
 153     }
 154
 155     // If the ObjC method declaration does not fit on a line, we should format
 156     // it with one arg per line.
 157     if (Line.Type == LT_ObjCMethodDecl)
 158       State.Stack.back().BreakBeforeParameter = true;
 159
 160     // Find best solution in solution space.
 161     return analyzeSolutionSpace(State);
 162   }
 163
 164 private:
 165   void DebugTokenState(const AnnotatedToken &AnnotatedTok) {
 166     const Token &Tok = AnnotatedTok.FormatTok.Tok;
 167     llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
 168                               Tok.getLength());
 169     llvm::errs();
 170   }
 171
 172   struct ParenState {
 173     ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking,
 174                bool NoLineBreak)
 175         : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0),
 176           BreakBeforeClosingBrace(false), QuestionColumn(0),
 177           AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false),
 178           NoLineBreak(NoLineBreak), ColonPos(0), StartOfFunctionCall(0),
 179           NestedNameSpecifierContinuation(0), CallContinuation(0),
 180           VariablePos(0) {}
 181
 182     /// \brief The position to which a specific parenthesis level needs to be
 183     /// indented.
 184     unsigned Indent;
 185
 186     /// \brief The position of the last space on each level.
 187     ///
 188     /// Used e.g. to break like:
 189     /// functionCall(Parameter, otherCall(
 190     ///                             OtherParameter));
 191     unsigned LastSpace;
 192
 193     /// \brief The position the first "<<" operator encountered on each level.
 194     ///
 195     /// Used to align "<<" operators. 0 if no such operator has been encountered
 196     /// on a level.
 197     unsigned FirstLessLess;
 198
 199     /// \brief Whether a newline needs to be inserted before the block's closing
 200     /// brace.
 201     ///
 202     /// We only want to insert a newline before the closing brace if there also
 203     /// was a newline after the beginning left brace.
 204     bool BreakBeforeClosingBrace;
 205
 206     /// \brief The column of a \c ? in a conditional expression;
 207     unsigned QuestionColumn;
 208
 209     /// \brief Avoid bin packing, i.e. multiple parameters/elements on multiple
 210     /// lines, in this context.
 211     bool AvoidBinPacking;
 212
 213     /// \brief Break after the next comma (or all the commas in this context if
 214     /// \c AvoidBinPacking is \c true).
 215     bool BreakBeforeParameter;
 216
 217     /// \brief Line breaking in this context would break a formatting rule.
 218     bool NoLineBreak;
 219
 220     /// \brief The position of the colon in an ObjC method declaration/call.
 221     unsigned ColonPos;
 222
 223     /// \brief The start of the most recent function in a builder-type call.
 224     unsigned StartOfFunctionCall;
 225
 226     /// \brief If a nested name specifier was broken over multiple lines, this
 227     /// contains the start column of the second line. Otherwise 0.
 228     unsigned NestedNameSpecifierContinuation;
 229
 230     /// \brief If a call expression was broken over multiple lines, this
 231     /// contains the start column of the second line. Otherwise 0.
 232     unsigned CallContinuation;
 233
 234     /// \brief The column of the first variable name in a variable declaration.
 235     ///
 236     /// Used to align further variables if necessary.
 237     unsigned VariablePos;
 238
 239     bool operator<(const ParenState &Other) const {
 240       if (Indent != Other.Indent)
 241         return Indent < Other.Indent;
 242       if (LastSpace != Other.LastSpace)
 243         return LastSpace < Other.LastSpace;
 244       if (FirstLessLess != Other.FirstLessLess)
 245         return FirstLessLess < Other.FirstLessLess;
 246       if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
 247         return BreakBeforeClosingBrace;
 248       if (QuestionColumn != Other.QuestionColumn)
 249         return QuestionColumn < Other.QuestionColumn;
 250       if (AvoidBinPacking != Other.AvoidBinPacking)
 251         return AvoidBinPacking;
 252       if (BreakBeforeParameter != Other.BreakBeforeParameter)
 253         return BreakBeforeParameter;
 254       if (NoLineBreak != Other.NoLineBreak)
 255         return NoLineBreak;
 256       if (ColonPos != Other.ColonPos)
 257         return ColonPos < Other.ColonPos;
 258       if (StartOfFunctionCall != Other.StartOfFunctionCall)
 259         return StartOfFunctionCall < Other.StartOfFunctionCall;
 260       if (NestedNameSpecifierContinuation !=
 261           Other.NestedNameSpecifierContinuation)
 262         return NestedNameSpecifierContinuation <
 263                Other.NestedNameSpecifierContinuation;
 264       if (CallContinuation != Other.CallContinuation)
 265         return CallContinuation < Other.CallContinuation;
 266       if (VariablePos != Other.VariablePos)
 267         return VariablePos < Other.VariablePos;
 268       return false;
 269     }
 270   };
 271
 272   /// \brief The current state when indenting a unwrapped line.
 273   ///
 274   /// As the indenting tries different combinations this is copied by value.
 275   struct LineState {
 276     /// \brief The number of used columns in the current line.
 277     unsigned Column;
 278
 279     /// \brief The token that needs to be next formatted.
 280     const AnnotatedToken *NextToken;
 281
 282     /// \brief \c true if this line contains a continued for-loop section.
 283     bool LineContainsContinuedForLoopSection;
 284
 285     /// \brief The level of nesting inside (), [], <> and {}.
 286     unsigned ParenLevel;
 287
 288     /// \brief The \c ParenLevel at the start of this line.
 289     unsigned StartOfLineLevel;
 290
 291     /// \brief The start column of the string literal, if we're in a string
 292     /// literal sequence, 0 otherwise.
 293     unsigned StartOfStringLiteral;
 294
 295     /// \brief A stack keeping track of properties applying to parenthesis
 296     /// levels.
 297     std::vector<ParenState> Stack;
 298
 299     /// \brief Comparison operator to be able to used \c LineState in \c map.
 300     bool operator<(const LineState &Other) const {
 301       if (NextToken != Other.NextToken)
 302         return NextToken < Other.NextToken;
 303       if (Column != Other.Column)
 304         return Column < Other.Column;
 305       if (LineContainsContinuedForLoopSection !=
 306           Other.LineContainsContinuedForLoopSection)
 307         return LineContainsContinuedForLoopSection;
 308       if (ParenLevel != Other.ParenLevel)
 309         return ParenLevel < Other.ParenLevel;
 310       if (StartOfLineLevel != Other.StartOfLineLevel)
 311         return StartOfLineLevel < Other.StartOfLineLevel;
 312       if (StartOfStringLiteral != Other.StartOfStringLiteral)
 313         return StartOfStringLiteral < Other.StartOfStringLiteral;
 314       return Stack < Other.Stack;
 315     }
 316   };
 317
 318   /// \brief Appends the next token to \p State and updates information
 319   /// necessary for indentation.
 320   ///
 321   /// Puts the token on the current line if \p Newline is \c true and adds a
 322   /// line break and necessary indentation otherwise.
 323   ///
 324   /// If \p DryRun is \c false, also creates and stores the required
 325   /// \c Replacement.
 326   unsigned addTokenToState(bool Newline, bool DryRun, LineState &State) {
 327     const AnnotatedToken &Current = *State.NextToken;
 328     const AnnotatedToken &Previous = *State.NextToken->Parent;
 329
 330     if (State.Stack.size() == 0 || Current.Type == TT_ImplicitStringLiteral) {
 331       State.Column += State.NextToken->FormatTok.WhiteSpaceLength +
 332                       State.NextToken->FormatTok.TokenLength;
 333       if (State.NextToken->Children.empty())
 334         State.NextToken = NULL;
 335       else
 336         State.NextToken = &State.NextToken->Children[0];
 337       return 0;
 338     }
 339
 340     // If we are continuing an expression, we want to indent an extra 4 spaces.
 341     unsigned ContinuationIndent =
 342         std::max(State.Stack.back().LastSpace, State.Stack.back().Indent) + 4;
 343     if (Newline) {
 344       unsigned WhitespaceStartColumn = State.Column;
 345       if (Current.is(tok::r_brace)) {
 346         State.Column = Line.Level * 2;
 347       } else if (Current.is(tok::string_literal) &&
 348                  State.StartOfStringLiteral != 0) {
 349         State.Column = State.StartOfStringLiteral;
 350         State.Stack.back().BreakBeforeParameter = true;
 351       } else if (Current.is(tok::lessless) &&
 352                  State.Stack.back().FirstLessLess != 0) {
 353         State.Column = State.Stack.back().FirstLessLess;
 354       } else if (Previous.is(tok::coloncolon)) {
 355         if (State.Stack.back().NestedNameSpecifierContinuation == 0) {
 356           State.Column = ContinuationIndent;
 357           State.Stack.back().NestedNameSpecifierContinuation = State.Column;
 358         } else {
 359           State.Column = State.Stack.back().NestedNameSpecifierContinuation;
 360         }
 361       } else if (Current.isOneOf(tok::period, tok::arrow)) {
 362         if (State.Stack.back().CallContinuation == 0) {
 363           State.Column = ContinuationIndent;
 364           State.Stack.back().CallContinuation = State.Column;
 365         } else {
 366           State.Column = State.Stack.back().CallContinuation;
 367         }
 368       } else if (Current.Type == TT_ConditionalExpr) {
 369         State.Column = State.Stack.back().QuestionColumn;
 370       } else if (Previous.is(tok::comma) &&
 371                  State.Stack.back().VariablePos != 0) {
 372         State.Column = State.Stack.back().VariablePos;
 373       } else if (Previous.ClosesTemplateDeclaration ||
 374                  (Current.Type == TT_StartOfName && State.ParenLevel == 0 &&
 375                   Line.StartsDefinition)) {
 376         State.Column = State.Stack.back().Indent;
 377       } else if (Current.Type == TT_ObjCSelectorName) {
 378         if (State.Stack.back().ColonPos > Current.FormatTok.TokenLength) {
 379           State.Column =
 380               State.Stack.back().ColonPos - Current.FormatTok.TokenLength;
 381         } else {
 382           State.Column = State.Stack.back().Indent;
 383           State.Stack.back().ColonPos =
 384               State.Column + Current.FormatTok.TokenLength;
 385         }
 386       } else if (Current.Type == TT_StartOfName || Previous.is(tok::equal) ||
 387                  Previous.Type == TT_ObjCMethodExpr) {
 388         State.Column = ContinuationIndent;
 389       } else {
 390         State.Column = State.Stack.back().Indent;
 391         // Ensure that we fall back to indenting 4 spaces instead of just
 392         // flushing continuations left.
 393         if (State.Column == FirstIndent)
 394           State.Column += 4;
 395       }
 396
 397       if (Current.is(tok::question))
 398         State.Stack.back().BreakBeforeParameter = true;
 399       if (Previous.isOneOf(tok::comma, tok::semi) &&
 400           !State.Stack.back().AvoidBinPacking)
 401         State.Stack.back().BreakBeforeParameter = false;
 402
 403       if (!DryRun) {
 404         unsigned NewLines = 1;
 405         if (Current.Type == TT_LineComment)
 406           NewLines =
 407               std::max(NewLines, std::min(Current.FormatTok.NewlinesBefore,
 408                                           Style.MaxEmptyLinesToKeep + 1));
 409         if (!Line.InPPDirective)
 410           Whitespaces.replaceWhitespace(Current, NewLines, State.Column,
 411                                         WhitespaceStartColumn);
 412         else
 413           Whitespaces.replacePPWhitespace(Current, NewLines, State.Column,
 414                                           WhitespaceStartColumn);
 415       }
 416
 417       State.Stack.back().LastSpace = State.Column;
 418       State.StartOfLineLevel = State.ParenLevel;
 419
 420       // Any break on this level means that the parent level has been broken
 421       // and we need to avoid bin packing there.
 422       for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) {
 423         State.Stack[i].BreakBeforeParameter = true;
 424       }
 425       const AnnotatedToken *TokenBefore = Current.getPreviousNoneComment();
 426       if (TokenBefore && !TokenBefore->isOneOf(tok::comma, tok::semi) &&
 427           !TokenBefore->opensScope())
 428         State.Stack.back().BreakBeforeParameter = true;
 429
 430       // If we break after {, we should also break before the corresponding }.
 431       if (Previous.is(tok::l_brace))
 432         State.Stack.back().BreakBeforeClosingBrace = true;
 433
 434       if (State.Stack.back().AvoidBinPacking) {
 435         // If we are breaking after '(', '{', '<', this is not bin packing
 436         // unless AllowAllParametersOfDeclarationOnNextLine is false.
 437         if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace)) ||
 438             (!Style.AllowAllParametersOfDeclarationOnNextLine &&
 439              Line.MustBeDeclaration))
 440           State.Stack.back().BreakBeforeParameter = true;
 441       }
 442     } else {
 443       if (Current.is(tok::equal) &&
 444           (RootToken.is(tok::kw_for) || State.ParenLevel == 0) &&
 445           State.Stack.back().VariablePos == 0) {
 446         State.Stack.back().VariablePos = State.Column;
 447         // Move over * and & if they are bound to the variable name.
 448         const AnnotatedToken *Tok = &Previous;
 449         while (Tok &&
 450                State.Stack.back().VariablePos >= Tok->FormatTok.TokenLength) {
 451           State.Stack.back().VariablePos -= Tok->FormatTok.TokenLength;
 452           if (Tok->SpacesRequiredBefore != 0)
 453             break;
 454           Tok = Tok->Parent;
 455         }
 456         if (Previous.PartOfMultiVariableDeclStmt)
 457           State.Stack.back().LastSpace = State.Stack.back().VariablePos;
 458       }
 459
 460       unsigned Spaces = State.NextToken->SpacesRequiredBefore;
 461
 462       if (!DryRun)
 463         Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column);
 464
 465       if (Current.Type == TT_ObjCSelectorName &&
 466           State.Stack.back().ColonPos == 0) {
 467         if (State.Stack.back().Indent + Current.LongestObjCSelectorName >
 468             State.Column + Spaces + Current.FormatTok.TokenLength)
 469           State.Stack.back().ColonPos =
 470               State.Stack.back().Indent + Current.LongestObjCSelectorName;
 471         else
 472           State.Stack.back().ColonPos =
 473               State.Column + Spaces + Current.FormatTok.TokenLength;
 474       }
 475
 476       if (Previous.opensScope() && Previous.Type != TT_ObjCMethodExpr &&
 477           Current.Type != TT_LineComment)
 478         State.Stack.back().Indent = State.Column + Spaces;
 479       if (Previous.is(tok::comma) && !Current.isTrailingComment() &&
 480           State.Stack.back().AvoidBinPacking)
 481         State.Stack.back().NoLineBreak = true;
 482
 483       State.Column += Spaces;
 484       if (Current.is(tok::l_paren) && Previous.isOneOf(tok::kw_if, tok::kw_for))
 485         // Treat the condition inside an if as if it was a second function
 486         // parameter, i.e. let nested calls have an indent of 4.
 487         State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(".
 488       else if (Previous.is(tok::comma))
 489         State.Stack.back().LastSpace = State.Column;
 490       else if ((Previous.Type == TT_BinaryOperator ||
 491                 Previous.Type == TT_ConditionalExpr ||
 492                 Previous.Type == TT_CtorInitializerColon) &&
 493                getPrecedence(Previous) != prec::Assignment)
 494         State.Stack.back().LastSpace = State.Column;
 495       else if (Previous.Type == TT_InheritanceColon)
 496         State.Stack.back().Indent = State.Column;
 497       else if (Previous.opensScope() && Previous.ParameterCount > 1)
 498         // If this function has multiple parameters, indent nested calls from
 499         // the start of the first parameter.
 500         State.Stack.back().LastSpace = State.Column;
 501     }
 502
 503     return moveStateToNextToken(State, DryRun);
 504   }
 505
 506   /// \brief Mark the next token as consumed in \p State and modify its stacks
 507   /// accordingly.
 508   unsigned moveStateToNextToken(LineState &State, bool DryRun) {
 509     const AnnotatedToken &Current = *State.NextToken;
 510     assert(State.Stack.size());
 511
 512     if (Current.Type == TT_InheritanceColon)
 513       State.Stack.back().AvoidBinPacking = true;
 514     if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
 515       State.Stack.back().FirstLessLess = State.Column;
 516     if (Current.is(tok::question))
 517       State.Stack.back().QuestionColumn = State.Column;
 518     if (Current.isOneOf(tok::period, tok::arrow) &&
 519         Line.Type == LT_BuilderTypeCall && State.ParenLevel == 0)
 520       State.Stack.back().StartOfFunctionCall =
 521           Current.LastInChainOfCalls ? 0 : State.Column;
 522     if (Current.Type == TT_CtorInitializerColon) {
 523       State.Stack.back().Indent = State.Column + 2;
 524       if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
 525         State.Stack.back().AvoidBinPacking = true;
 526       State.Stack.back().BreakBeforeParameter = false;
 527     }
 528
 529     // If return returns a binary expression, align after it.
 530     if (Current.is(tok::kw_return) && !Current.FakeLParens.empty())
 531       State.Stack.back().LastSpace = State.Column + 7;
 532
 533     // In ObjC method declaration we align on the ":" of parameters, but we need
 534     // to ensure that we indent parameters on subsequent lines by at least 4.
 535     if (Current.Type == TT_ObjCMethodSpecifier)
 536       State.Stack.back().Indent += 4;
 537
 538     // Insert scopes created by fake parenthesis.
 539     const AnnotatedToken *Previous = Current.getPreviousNoneComment();
 540     // Don't add extra indentation for the first fake parenthesis after
 541     // 'return', assignements or opening <({[. The indentation for these cases
 542     // is special cased.
 543     bool SkipFirstExtraIndent =
 544         Current.is(tok::kw_return) ||
 545         (Previous && (Previous->opensScope() ||
 546                       getPrecedence(*Previous) == prec::Assignment));
 547     for (SmallVector<prec::Level, 4>::const_reverse_iterator
 548              I = Current.FakeLParens.rbegin(),
 549              E = Current.FakeLParens.rend();
 550          I != E; ++I) {
 551       ParenState NewParenState = State.Stack.back();
 552       NewParenState.Indent =
 553           std::max(std::max(State.Column, NewParenState.Indent),
 554                    State.Stack.back().LastSpace);
 555
 556       // Always indent conditional expressions. Never indent expression where
 557       // the 'operator' is ',', ';' or an assignment (i.e. *I <=
 558       // prec::Assignment) as those have different indentation rules. Indent
 559       // other expression, unless the indentation needs to be skipped.
 560       if (*I == prec::Conditional ||
 561           (!SkipFirstExtraIndent && *I > prec::Assignment))
 562         NewParenState.Indent += 4;
 563       if (Previous && !Previous->opensScope())
 564         NewParenState.BreakBeforeParameter = false;
 565       State.Stack.push_back(NewParenState);
 566       SkipFirstExtraIndent = false;
 567     }
 568
 569     // If we encounter an opening (, [, { or <, we add a level to our stacks to
 570     // prepare for the following tokens.
 571     if (Current.opensScope()) {
 572       unsigned NewIndent;
 573       bool AvoidBinPacking;
 574       if (Current.is(tok::l_brace)) {
 575         NewIndent = 2 + State.Stack.back().LastSpace;
 576         AvoidBinPacking = false;
 577       } else {
 578         NewIndent = 4 + std::max(State.Stack.back().LastSpace,
 579                                  State.Stack.back().StartOfFunctionCall);
 580         AvoidBinPacking = !Style.BinPackParameters;
 581       }
 582       State.Stack.push_back(
 583           ParenState(NewIndent, State.Stack.back().LastSpace, AvoidBinPacking,
 584                      State.Stack.back().NoLineBreak));
 585
 586       if (Current.NoMoreTokensOnLevel && Current.FakeLParens.empty()) {
 587         // This parenthesis was the last token possibly making use of Indent and
 588         // LastSpace of the next higher ParenLevel. Thus, erase them to acieve
 589         // better memoization results.
 590         State.Stack[State.Stack.size() - 2].Indent = 0;
 591         State.Stack[State.Stack.size() - 2].LastSpace = 0;
 592       }
 593
 594       ++State.ParenLevel;
 595     }
 596
 597     // If this '[' opens an ObjC call, determine whether all parameters fit into
 598     // one line and put one per line if they don't.
 599     if (Current.is(tok::l_square) && Current.Type == TT_ObjCMethodExpr &&
 600         Current.MatchingParen != NULL) {
 601       if (getLengthToMatchingParen(Current) + State.Column > getColumnLimit())
 602         State.Stack.back().BreakBeforeParameter = true;
 603     }
 604
 605     // If we encounter a closing ), ], } or >, we can remove a level from our
 606     // stacks.
 607     if (Current.isOneOf(tok::r_paren, tok::r_square) ||
 608         (Current.is(tok::r_brace) && State.NextToken != &RootToken) ||
 609         State.NextToken->Type == TT_TemplateCloser) {
 610       State.Stack.pop_back();
 611       --State.ParenLevel;
 612     }
 613
 614     // Remove scopes created by fake parenthesis.
 615     for (unsigned i = 0, e = Current.FakeRParens; i != e; ++i) {
 616       unsigned VariablePos = State.Stack.back().VariablePos;
 617       State.Stack.pop_back();
 618       State.Stack.back().VariablePos = VariablePos;
 619     }
 620
 621     if (Current.is(tok::string_literal)) {
 622       State.StartOfStringLiteral = State.Column;
 623     } else if (Current.isNot(tok::comment)) {
 624       State.StartOfStringLiteral = 0;
 625     }
 626
 627     State.Column += Current.FormatTok.TokenLength;
 628
 629     if (State.NextToken->Children.empty())
 630       State.NextToken = NULL;
 631     else
 632       State.NextToken = &State.NextToken->Children[0];
 633
 634     return breakProtrudingToken(Current, State, DryRun);
 635   }
 636
 637   /// \brief If the current token sticks out over the end of the line, break
 638   /// it if possible.
 639   unsigned breakProtrudingToken(const AnnotatedToken &Current, LineState &State,
 640                                 bool DryRun) {
 641     llvm::OwningPtr<BreakableToken> Token;
 642     unsigned StartColumn = State.Column - Current.FormatTok.TokenLength;
 643     if (Current.is(tok::string_literal)) {
 644       // Only break up default narrow strings.
 645       const char *LiteralData = SourceMgr.getCharacterData(
 646           Current.FormatTok.getStartOfNonWhitespace());
 647       if (!LiteralData || *LiteralData != '"')
 648         return 0;
 649
 650       Token.reset(new BreakableStringLiteral(SourceMgr, Current.FormatTok,
 651                                              StartColumn));
 652     } else if (Current.Type == TT_BlockComment) {
 653       BreakableBlockComment *BBC =
 654           new BreakableBlockComment(SourceMgr, Current, StartColumn);
 655       if (!DryRun)
 656         BBC->alignLines(Whitespaces);
 657       Token.reset(BBC);
 658     } else if (Current.Type == TT_LineComment &&
 659                (Current.Parent == NULL ||
 660                 Current.Parent->Type != TT_ImplicitStringLiteral)) {
 661       Token.reset(new BreakableLineComment(SourceMgr, Current, StartColumn));
 662     } else {
 663       return 0;
 664     }
 665
 666     bool BreakInserted = false;
 667     unsigned Penalty = 0;
 668     for (unsigned LineIndex = 0; LineIndex < Token->getLineCount();
 669          ++LineIndex) {
 670       unsigned TailOffset = 0;
 671       unsigned RemainingLength =
 672           Token->getLineLengthAfterSplit(LineIndex, TailOffset);
 673       while (RemainingLength > getColumnLimit()) {
 674         BreakableToken::Split Split =
 675             Token->getSplit(LineIndex, TailOffset, getColumnLimit());
 676         if (Split.first == StringRef::npos)
 677           break;
 678         assert(Split.first != 0);
 679         unsigned NewRemainingLength = Token->getLineLengthAfterSplit(
 680             LineIndex, TailOffset + Split.first + Split.second);
 681         if (NewRemainingLength >= RemainingLength)
 682           break;
 683         if (!DryRun) {
 684           Token->insertBreak(LineIndex, TailOffset, Split, Line.InPPDirective,
 685                              Whitespaces);
 686         }
 687         TailOffset += Split.first + Split.second;
 688         RemainingLength = NewRemainingLength;
 689         Penalty += Style.PenaltyExcessCharacter;
 690         BreakInserted = true;
 691       }
 692       State.Column = RemainingLength;
 693       if (!DryRun) {
 694         Token->trimLine(LineIndex, TailOffset, Line.InPPDirective, Whitespaces);
 695       }
 696     }
 697
 698     if (BreakInserted) {
 699       for (unsigned i = 0, e = State.Stack.size(); i != e; ++i)
 700         State.Stack[i].BreakBeforeParameter = true;
 701       State.Stack.back().LastSpace = StartColumn;
 702     }
 703     return Penalty;
 704   }
 705
 706   unsigned getColumnLimit() {
 707     // In preprocessor directives reserve two chars for trailing " \"
 708     return Style.ColumnLimit - (Line.InPPDirective ? 2 : 0);
 709   }
 710
 711   /// \brief An edge in the solution space from \c Previous->State to \c State,
 712   /// inserting a newline dependent on the \c NewLine.
 713   struct StateNode {
 714     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
 715         : State(State), NewLine(NewLine), Previous(Previous) {}
 716     LineState State;
 717     bool NewLine;
 718     StateNode *Previous;
 719   };
 720
 721   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
 722   ///
 723   /// In case of equal penalties, we want to prefer states that were inserted
 724   /// first. During state generation we make sure that we insert states first
 725   /// that break the line as late as possible.
 726   typedef std::pair<unsigned, unsigned> OrderedPenalty;
 727
 728   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
 729   /// \c State has the given \c OrderedPenalty.
 730   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
 731
 732   /// \brief The BFS queue type.
 733   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
 734                               std::greater<QueueItem> > QueueType;
 735
 736   /// \brief Analyze the entire solution space starting from \p InitialState.
 737   ///
 738   /// This implements a variant of Dijkstra's algorithm on the graph that spans
 739   /// the solution space (\c LineStates are the nodes). The algorithm tries to
 740   /// find the shortest path (the one with lowest penalty) from \p InitialState
 741   /// to a state where all tokens are placed.
 742   unsigned analyzeSolutionSpace(LineState &InitialState) {
 743     std::set<LineState> Seen;
 744
 745     // Insert start element into queue.
 746     StateNode *Node =
 747         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
 748     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
 749     ++Count;
 750
 751     // While not empty, take first element and follow edges.
 752     while (!Queue.empty()) {
 753       unsigned Penalty = Queue.top().first.first;
 754       StateNode *Node = Queue.top().second;
 755       if (Node->State.NextToken == NULL) {
 756         DEBUG(llvm::errs() << "\n---\nPenalty for line: " << Penalty << "\n");
 757         break;
 758       }
 759       Queue.pop();
 760
 761       if (!Seen.insert(Node->State).second)
 762         // State already examined with lower penalty.
 763         continue;
 764
 765       addNextStateToQueue(Penalty, Node, /*NewLine=*/ false);
 766       addNextStateToQueue(Penalty, Node, /*NewLine=*/ true);
 767     }
 768
 769     if (Queue.empty())
 770       // We were unable to find a solution, do nothing.
 771       // FIXME: Add diagnostic?
 772       return 0;
 773
 774     // Reconstruct the solution.
 775     reconstructPath(InitialState, Queue.top().second);
 776     DEBUG(llvm::errs() << "---\n");
 777
 778     // Return the column after the last token of the solution.
 779     return Queue.top().second->State.Column;
 780   }
 781
 782   void reconstructPath(LineState &State, StateNode *Current) {
 783     // FIXME: This recursive implementation limits the possible number
 784     // of tokens per line if compiled into a binary with small stack space.
 785     // To become more independent of stack frame limitations we would need
 786     // to also change the TokenAnnotator.
 787     if (Current->Previous == NULL)
 788       return;
 789     reconstructPath(State, Current->Previous);
 790     DEBUG({
 791       if (Current->NewLine) {
 792         llvm::errs()
 793             << "Penalty for splitting before "
 794             << Current->Previous->State.NextToken->FormatTok.Tok.getName()
 795             << ": " << Current->Previous->State.NextToken->SplitPenalty << "\n";
 796       }
 797     });
 798     addTokenToState(Current->NewLine, false, State);
 799   }
 800
 801   /// \brief Add the following state to the analysis queue \c Queue.
 802   ///
 803   /// Assume the current state is \p PreviousNode and has been reached with a
 804   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
 805   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
 806                            bool NewLine) {
 807     if (NewLine && !canBreak(PreviousNode->State))
 808       return;
 809     if (!NewLine && mustBreak(PreviousNode->State))
 810       return;
 811     if (NewLine)
 812       Penalty += PreviousNode->State.NextToken->SplitPenalty;
 813
 814     StateNode *Node = new (Allocator.Allocate())
 815         StateNode(PreviousNode->State, NewLine, PreviousNode);
 816     Penalty += addTokenToState(NewLine, true, Node->State);
 817     if (Node->State.Column > getColumnLimit()) {
 818       unsigned ExcessCharacters = Node->State.Column - getColumnLimit();
 819       Penalty += Style.PenaltyExcessCharacter * ExcessCharacters;
 820     }
 821
 822     Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
 823     ++Count;
 824   }
 825
 826   /// \brief Returns \c true, if a line break after \p State is allowed.
 827   bool canBreak(const LineState &State) {
 828     if (!State.NextToken->CanBreakBefore &&
 829         !(State.NextToken->is(tok::r_brace) &&
 830           State.Stack.back().BreakBeforeClosingBrace))
 831       return false;
 832     return !State.Stack.back().NoLineBreak;
 833   }
 834
 835   /// \brief Returns \c true, if a line break after \p State is mandatory.
 836   bool mustBreak(const LineState &State) {
 837     if (State.NextToken->MustBreakBefore)
 838       return true;
 839     if (State.NextToken->is(tok::r_brace) &&
 840         State.Stack.back().BreakBeforeClosingBrace)
 841       return true;
 842     if (State.NextToken->Parent->is(tok::semi) &&
 843         State.LineContainsContinuedForLoopSection)
 844       return true;
 845     if ((State.NextToken->Parent->isOneOf(tok::comma, tok::semi) ||
 846          State.NextToken->is(tok::question) ||
 847          State.NextToken->Type == TT_ConditionalExpr) &&
 848         State.Stack.back().BreakBeforeParameter &&
 849         !State.NextToken->isTrailingComment() &&
 850         State.NextToken->isNot(tok::r_paren) &&
 851         State.NextToken->isNot(tok::r_brace))
 852       return true;
 853     // FIXME: Comparing LongestObjCSelectorName to 0 is a hacky way of finding
 854     // out whether it is the first parameter. Clean this up.
 855     if (State.NextToken->Type == TT_ObjCSelectorName &&
 856         State.NextToken->LongestObjCSelectorName == 0 &&
 857         State.Stack.back().BreakBeforeParameter)
 858       return true;
 859     if ((State.NextToken->Type == TT_CtorInitializerColon ||
 860          (State.NextToken->Parent->ClosesTemplateDeclaration &&
 861           State.ParenLevel == 0)))
 862       return true;
 863     if (State.NextToken->Type == TT_InlineASMColon)
 864       return true;
 865     // This prevents breaks like:
 866     //   ...
 867     //   SomeParameter, OtherParameter).DoSomething(
 868     //   ...
 869     // As they hide "DoSomething" and generally bad for readability.
 870     if (State.NextToken->isOneOf(tok::period, tok::arrow) &&
 871         getRemainingLength(State) + State.Column > getColumnLimit() &&
 872         State.ParenLevel < State.StartOfLineLevel)
 873       return true;
 874     return false;
 875   }
 876
 877   // Returns the total number of columns required for the remaining tokens.
 878   unsigned getRemainingLength(const LineState &State) {
 879     if (State.NextToken && State.NextToken->Parent)
 880       return Line.Last->TotalLength - State.NextToken->Parent->TotalLength;
 881     return 0;
 882   }
 883
 884   FormatStyle Style;
 885   SourceManager &SourceMgr;
 886   const AnnotatedLine &Line;
 887   const unsigned FirstIndent;
 888   const AnnotatedToken &RootToken;
 889   WhitespaceManager &Whitespaces;
 890
 891   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
 892   QueueType Queue;
 893   // Increasing count of \c StateNode items we have created. This is used
 894   // to create a deterministic order independent of the container.
 895   unsigned Count;
 896 };
 897
 898 class LexerBasedFormatTokenSource : public FormatTokenSource {
 899 public:
 900   LexerBasedFormatTokenSource(Lexer &Lex, SourceManager &SourceMgr)
 901       : GreaterStashed(false), Lex(Lex), SourceMgr(SourceMgr),
 902         IdentTable(Lex.getLangOpts()) {
 903     Lex.SetKeepWhitespaceMode(true);
 904   }
 905
 906   virtual FormatToken getNextToken() {
 907     if (GreaterStashed) {
 908       FormatTok.NewlinesBefore = 0;
 909       FormatTok.WhiteSpaceStart =
 910           FormatTok.Tok.getLocation().getLocWithOffset(1);
 911       FormatTok.WhiteSpaceLength = 0;
 912       GreaterStashed = false;
 913       return FormatTok;
 914     }
 915
 916     FormatTok = FormatToken();
 917     Lex.LexFromRawLexer(FormatTok.Tok);
 918     StringRef Text = rawTokenText(FormatTok.Tok);
 919     FormatTok.WhiteSpaceStart = FormatTok.Tok.getLocation();
 920     if (SourceMgr.getFileOffset(FormatTok.WhiteSpaceStart) == 0)
 921       FormatTok.IsFirst = true;
 922
 923     // Consume and record whitespace until we find a significant token.
 924     while (FormatTok.Tok.is(tok::unknown)) {
 925       unsigned Newlines = Text.count('\n');
 926       if (Newlines > 0)
 927         FormatTok.LastNewlineOffset =
 928             FormatTok.WhiteSpaceLength + Text.rfind('\n') + 1;
 929       unsigned EscapedNewlines = Text.count("\\\n");
 930       FormatTok.NewlinesBefore += Newlines;
 931       FormatTok.HasUnescapedNewline |= EscapedNewlines != Newlines;
 932       FormatTok.WhiteSpaceLength += FormatTok.Tok.getLength();
 933
 934       if (FormatTok.Tok.is(tok::eof))
 935         return FormatTok;
 936       Lex.LexFromRawLexer(FormatTok.Tok);
 937       Text = rawTokenText(FormatTok.Tok);
 938     }
 939
 940     // Now FormatTok is the next non-whitespace token.
 941     FormatTok.TokenLength = Text.size();
 942
 943     if (FormatTok.Tok.is(tok::comment)) {
 944       FormatTok.TrailingWhiteSpaceLength = Text.size() - Text.rtrim().size();
 945       FormatTok.TokenLength -= FormatTok.TrailingWhiteSpaceLength;
 946     }
 947
 948     // In case the token starts with escaped newlines, we want to
 949     // take them into account as whitespace - this pattern is quite frequent
 950     // in macro definitions.
 951     // FIXME: What do we want to do with other escaped spaces, and escaped
 952     // spaces or newlines in the middle of tokens?
 953     // FIXME: Add a more explicit test.
 954     unsigned i = 0;
 955     while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') {
 956       // FIXME: ++FormatTok.NewlinesBefore is missing...
 957       FormatTok.WhiteSpaceLength += 2;
 958       FormatTok.TokenLength -= 2;
 959       i += 2;
 960     }
 961
 962     if (FormatTok.Tok.is(tok::raw_identifier)) {
 963       IdentifierInfo &Info = IdentTable.get(Text);
 964       FormatTok.Tok.setIdentifierInfo(&Info);
 965       FormatTok.Tok.setKind(Info.getTokenID());
 966     }
 967
 968     if (FormatTok.Tok.is(tok::greatergreater)) {
 969       FormatTok.Tok.setKind(tok::greater);
 970       FormatTok.TokenLength = 1;
 971       GreaterStashed = true;
 972     }
 973
 974     return FormatTok;
 975   }
 976
 977   IdentifierTable &getIdentTable() { return IdentTable; }
 978
 979 private:
 980   FormatToken FormatTok;
 981   bool GreaterStashed;
 982   Lexer &Lex;
 983   SourceManager &SourceMgr;
 984   IdentifierTable IdentTable;
 985
 986   /// Returns the text of \c FormatTok.
 987   StringRef rawTokenText(Token &Tok) {
 988     return StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
 989                      Tok.getLength());
 990   }
 991 };
 992
 993 class Formatter : public UnwrappedLineConsumer {
 994 public:
 995   Formatter(DiagnosticsEngine &Diag, const FormatStyle &Style, Lexer &Lex,
 996             SourceManager &SourceMgr,
 997             const std::vector<CharSourceRange> &Ranges)
 998       : Diag(Diag), Style(Style), Lex(Lex), SourceMgr(SourceMgr),
 999         Whitespaces(SourceMgr, Style), Ranges(Ranges) {}
1000
1001   virtual ~Formatter() {}
1002
1003   tooling::Replacements format() {
1004     LexerBasedFormatTokenSource Tokens(Lex, SourceMgr);
1005     UnwrappedLineParser Parser(Diag, Style, Tokens, *this);
1006     bool StructuralError = Parser.parse();
1007     unsigned PreviousEndOfLineColumn = 0;
1008     TokenAnnotator Annotator(Style, SourceMgr, Lex,
1009                              Tokens.getIdentTable().get("in"));
1010     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1011       Annotator.annotate(AnnotatedLines[i]);
1012     }
1013     deriveLocalStyle();
1014     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1015       Annotator.calculateFormattingInformation(AnnotatedLines[i]);
1016     }
1017
1018     // Adapt level to the next line if this is a comment.
1019     // FIXME: Can/should this be done in the UnwrappedLineParser?
1020     const AnnotatedLine *NextNoneCommentLine = NULL;
1021     for (unsigned i = AnnotatedLines.size() - 1; i > 0; --i) {
1022       if (NextNoneCommentLine && AnnotatedLines[i].First.is(tok::comment) &&
1023           AnnotatedLines[i].First.Children.empty())
1024         AnnotatedLines[i].Level = NextNoneCommentLine->Level;
1025       else
1026         NextNoneCommentLine =
1027             AnnotatedLines[i].First.isNot(tok::r_brace) ? &AnnotatedLines[i]
1028                                                         : NULL;
1029     }
1030
1031     std::vector<int> IndentForLevel;
1032     bool PreviousLineWasTouched = false;
1033     const AnnotatedToken *PreviousLineLastToken = 0;
1034     for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(),
1035                                               E = AnnotatedLines.end();
1036          I != E; ++I) {
1037       const AnnotatedLine &TheLine = *I;
1038       const FormatToken &FirstTok = TheLine.First.FormatTok;
1039       int Offset = getIndentOffset(TheLine.First);
1040       while (IndentForLevel.size() <= TheLine.Level)
1041         IndentForLevel.push_back(-1);
1042       IndentForLevel.resize(TheLine.Level + 1);
1043       bool WasMoved = PreviousLineWasTouched && FirstTok.NewlinesBefore == 0;
1044       if (TheLine.First.is(tok::eof)) {
1045         if (PreviousLineWasTouched) {
1046           unsigned NewLines = std::min(FirstTok.NewlinesBefore, 1u);
1047           Whitespaces.replaceWhitespace(TheLine.First, NewLines, /*Indent*/ 0,
1048                                         /*WhitespaceStartColumn*/ 0);
1049         }
1050       } else if (TheLine.Type != LT_Invalid &&
1051                  (WasMoved || touchesLine(TheLine))) {
1052         unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
1053         unsigned Indent = LevelIndent;
1054         if (static_cast<int>(Indent) + Offset >= 0)
1055           Indent += Offset;
1056         if (FirstTok.WhiteSpaceStart.isValid() &&
1057             // Insert a break even if there is a structural error in case where
1058             // we break apart a line consisting of multiple unwrapped lines.
1059             (FirstTok.NewlinesBefore == 0 || !StructuralError)) {
1060           formatFirstToken(TheLine.First, PreviousLineLastToken, Indent,
1061                            TheLine.InPPDirective, PreviousEndOfLineColumn);
1062         } else {
1063           Indent = LevelIndent =
1064               SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1;
1065         }
1066         tryFitMultipleLinesInOne(Indent, I, E);
1067         UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent,
1068                                          TheLine.First, Whitespaces);
1069         PreviousEndOfLineColumn =
1070             Formatter.format(I + 1 != E ? &*(I + 1) : NULL);
1071         IndentForLevel[TheLine.Level] = LevelIndent;
1072         PreviousLineWasTouched = true;
1073       } else {
1074         if (FirstTok.NewlinesBefore > 0 || FirstTok.IsFirst) {
1075           unsigned Indent =
1076               SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1;
1077           unsigned LevelIndent = Indent;
1078           if (static_cast<int>(LevelIndent) - Offset >= 0)
1079             LevelIndent -= Offset;
1080           if (TheLine.First.isNot(tok::comment))
1081             IndentForLevel[TheLine.Level] = LevelIndent;
1082
1083           // Remove trailing whitespace of the previous line if it was touched.
1084           if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine))
1085             formatFirstToken(TheLine.First, PreviousLineLastToken, Indent,
1086                              TheLine.InPPDirective, PreviousEndOfLineColumn);
1087         }
1088         // If we did not reformat this unwrapped line, the column at the end of
1089         // the last token is unchanged - thus, we can calculate the end of the
1090         // last token.
1091         SourceLocation LastLoc = TheLine.Last->FormatTok.Tok.getLocation();
1092         PreviousEndOfLineColumn =
1093             SourceMgr.getSpellingColumnNumber(LastLoc) +
1094             Lex.MeasureTokenLength(LastLoc, SourceMgr, Lex.getLangOpts()) - 1;
1095         PreviousLineWasTouched = false;
1096         if (TheLine.Last->is(tok::comment))
1097           Whitespaces.addUntouchableComment(SourceMgr.getSpellingColumnNumber(
1098               TheLine.Last->FormatTok.Tok.getLocation()) - 1);
1099         else
1100           Whitespaces.alignComments();
1101       }
1102       PreviousLineLastToken = I->Last;
1103     }
1104     return Whitespaces.generateReplacements();
1105   }
1106
1107 private:
1108   void deriveLocalStyle() {
1109     unsigned CountBoundToVariable = 0;
1110     unsigned CountBoundToType = 0;
1111     bool HasCpp03IncompatibleFormat = false;
1112     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1113       if (AnnotatedLines[i].First.Children.empty())
1114         continue;
1115       AnnotatedToken *Tok = &AnnotatedLines[i].First.Children[0];
1116       while (!Tok->Children.empty()) {
1117         if (Tok->Type == TT_PointerOrReference) {
1118           bool SpacesBefore = Tok->FormatTok.WhiteSpaceLength > 0;
1119           bool SpacesAfter = Tok->Children[0].FormatTok.WhiteSpaceLength > 0;
1120           if (SpacesBefore && !SpacesAfter)
1121             ++CountBoundToVariable;
1122           else if (!SpacesBefore && SpacesAfter)
1123             ++CountBoundToType;
1124         }
1125
1126         if (Tok->Type == TT_TemplateCloser &&
1127             Tok->Parent->Type == TT_TemplateCloser &&
1128             Tok->FormatTok.WhiteSpaceLength == 0)
1129           HasCpp03IncompatibleFormat = true;
1130         Tok = &Tok->Children[0];
1131       }
1132     }
1133     if (Style.DerivePointerBinding) {
1134       if (CountBoundToType > CountBoundToVariable)
1135         Style.PointerBindsToType = true;
1136       else if (CountBoundToType < CountBoundToVariable)
1137         Style.PointerBindsToType = false;
1138     }
1139     if (Style.Standard == FormatStyle::LS_Auto) {
1140       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1141                                                   : FormatStyle::LS_Cpp03;
1142     }
1143   }
1144
1145   /// \brief Get the indent of \p Level from \p IndentForLevel.
1146   ///
1147   /// \p IndentForLevel must contain the indent for the level \c l
1148   /// at \p IndentForLevel[l], or a value < 0 if the indent for
1149   /// that level is unknown.
1150   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1151     if (IndentForLevel[Level] != -1)
1152       return IndentForLevel[Level];
1153     if (Level == 0)
1154       return 0;
1155     return getIndent(IndentForLevel, Level - 1) + 2;
1156   }
1157
1158   /// \brief Get the offset of the line relatively to the level.
1159   ///
1160   /// For example, 'public:' labels in classes are offset by 1 or 2
1161   /// characters to the left from their level.
1162   int getIndentOffset(const AnnotatedToken &RootToken) {
1163     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
1164       return Style.AccessModifierOffset;
1165     return 0;
1166   }
1167
1168   /// \brief Tries to merge lines into one.
1169   ///
1170   /// This will change \c Line and \c AnnotatedLine to contain the merged line,
1171   /// if possible; note that \c I will be incremented when lines are merged.
1172   ///
1173   /// Returns whether the resulting \c Line can fit in a single line.
1174   void tryFitMultipleLinesInOne(unsigned Indent,
1175                                 std::vector<AnnotatedLine>::iterator &I,
1176                                 std::vector<AnnotatedLine>::iterator E) {
1177     // We can never merge stuff if there are trailing line comments.
1178     if (I->Last->Type == TT_LineComment)
1179       return;
1180
1181     unsigned Limit = Style.ColumnLimit - Indent;
1182     // If we already exceed the column limit, we set 'Limit' to 0. The different
1183     // tryMerge..() functions can then decide whether to still do merging.
1184     Limit = I->Last->TotalLength > Limit ? 0 : Limit - I->Last->TotalLength;
1185
1186     if (I + 1 == E || (I + 1)->Type == LT_Invalid)
1187       return;
1188
1189     if (I->Last->is(tok::l_brace)) {
1190       tryMergeSimpleBlock(I, E, Limit);
1191     } else if (I->First.is(tok::kw_if)) {
1192       tryMergeSimpleIf(I, E, Limit);
1193     } else if (I->InPPDirective && (I->First.FormatTok.HasUnescapedNewline ||
1194                                     I->First.FormatTok.IsFirst)) {
1195       tryMergeSimplePPDirective(I, E, Limit);
1196     }
1197     return;
1198   }
1199
1200   void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I,
1201                                  std::vector<AnnotatedLine>::iterator E,
1202                                  unsigned Limit) {
1203     if (Limit == 0)
1204       return;
1205     AnnotatedLine &Line = *I;
1206     if (!(I + 1)->InPPDirective || (I + 1)->First.FormatTok.HasUnescapedNewline)
1207       return;
1208     if (I + 2 != E && (I + 2)->InPPDirective &&
1209         !(I + 2)->First.FormatTok.HasUnescapedNewline)
1210       return;
1211     if (1 + (I + 1)->Last->TotalLength > Limit)
1212       return;
1213     join(Line, *(++I));
1214   }
1215
1216   void tryMergeSimpleIf(std::vector<AnnotatedLine>::iterator &I,
1217                         std::vector<AnnotatedLine>::iterator E,
1218                         unsigned Limit) {
1219     if (Limit == 0)
1220       return;
1221     if (!Style.AllowShortIfStatementsOnASingleLine)
1222       return;
1223     if ((I + 1)->InPPDirective != I->InPPDirective ||
1224         ((I + 1)->InPPDirective &&
1225          (I + 1)->First.FormatTok.HasUnescapedNewline))
1226       return;
1227     AnnotatedLine &Line = *I;
1228     if (Line.Last->isNot(tok::r_paren))
1229       return;
1230     if (1 + (I + 1)->Last->TotalLength > Limit)
1231       return;
1232     if ((I + 1)->First.is(tok::kw_if) || (I + 1)->First.Type == TT_LineComment)
1233       return;
1234     // Only inline simple if's (no nested if or else).
1235     if (I + 2 != E && (I + 2)->First.is(tok::kw_else))
1236       return;
1237     join(Line, *(++I));
1238   }
1239
1240   void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I,
1241                            std::vector<AnnotatedLine>::iterator E,
1242                            unsigned Limit) {
1243     // First, check that the current line allows merging. This is the case if
1244     // we're not in a control flow statement and the last token is an opening
1245     // brace.
1246     AnnotatedLine &Line = *I;
1247     if (Line.First.isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1248                            tok::kw_else, tok::kw_try, tok::kw_catch,
1249                            tok::kw_for,
1250                            // This gets rid of all ObjC @ keywords and methods.
1251                            tok::at, tok::minus, tok::plus))
1252       return;
1253
1254     AnnotatedToken *Tok = &(I + 1)->First;
1255     if (Tok->Children.empty() && Tok->is(tok::r_brace) &&
1256         !Tok->MustBreakBefore) {
1257       // We merge empty blocks even if the line exceeds the column limit.
1258       Tok->SpacesRequiredBefore = 0;
1259       Tok->CanBreakBefore = true;
1260       join(Line, *(I + 1));
1261       I += 1;
1262     } else if (Limit != 0) {
1263       // Check that we still have three lines and they fit into the limit.
1264       if (I + 2 == E || (I + 2)->Type == LT_Invalid ||
1265           !nextTwoLinesFitInto(I, Limit))
1266         return;
1267
1268       // Second, check that the next line does not contain any braces - if it
1269       // does, readability declines when putting it into a single line.
1270       if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1271         return;
1272       do {
1273         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1274           return;
1275         Tok = Tok->Children.empty() ? NULL : &Tok->Children.back();
1276       } while (Tok != NULL);
1277
1278       // Last, check that the third line contains a single closing brace.
1279       Tok = &(I + 2)->First;
1280       if (!Tok->Children.empty() || Tok->isNot(tok::r_brace) ||
1281           Tok->MustBreakBefore)
1282         return;
1283
1284       join(Line, *(I + 1));
1285       join(Line, *(I + 2));
1286       I += 2;
1287     }
1288   }
1289
1290   bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I,
1291                            unsigned Limit) {
1292     return 1 + (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <=
1293            Limit;
1294   }
1295
1296   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1297     unsigned LengthA = A.Last->TotalLength + B.First.SpacesRequiredBefore;
1298     A.Last->Children.push_back(B.First);
1299     while (!A.Last->Children.empty()) {
1300       A.Last->Children[0].Parent = A.Last;
1301       A.Last->Children[0].TotalLength += LengthA;
1302       A.Last = &A.Last->Children[0];
1303     }
1304   }
1305
1306   bool touchesRanges(const CharSourceRange &Range) {
1307     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1308       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1309                                                Ranges[i].getBegin()) &&
1310           !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1311                                                Range.getBegin()))
1312         return true;
1313     }
1314     return false;
1315   }
1316
1317   bool touchesLine(const AnnotatedLine &TheLine) {
1318     const FormatToken *First = &TheLine.First.FormatTok;
1319     const FormatToken *Last = &TheLine.Last->FormatTok;
1320     CharSourceRange LineRange = CharSourceRange::getTokenRange(
1321         First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset),
1322         Last->Tok.getLocation());
1323     return touchesRanges(LineRange);
1324   }
1325
1326   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1327     const FormatToken *First = &TheLine.First.FormatTok;
1328     CharSourceRange LineRange = CharSourceRange::getCharRange(
1329         First->WhiteSpaceStart,
1330         First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset));
1331     return touchesRanges(LineRange);
1332   }
1333
1334   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1335     AnnotatedLines.push_back(AnnotatedLine(TheLine));
1336   }
1337
1338   /// \brief Add a new line and the required indent before the first Token
1339   /// of the \c UnwrappedLine if there was no structural parsing error.
1340   /// Returns the indent level of the \c UnwrappedLine.
1341   void formatFirstToken(const AnnotatedToken &RootToken,
1342                         const AnnotatedToken *PreviousToken, unsigned Indent,
1343                         bool InPPDirective, unsigned PreviousEndOfLineColumn) {
1344     const FormatToken &Tok = RootToken.FormatTok;
1345
1346     unsigned Newlines =
1347         std::min(Tok.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1348     if (Newlines == 0 && !Tok.IsFirst)
1349       Newlines = 1;
1350
1351     if (!InPPDirective || Tok.HasUnescapedNewline) {
1352       // Insert extra new line before access specifiers.
1353       if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1354           RootToken.isAccessSpecifier() && Tok.NewlinesBefore == 1)
1355         ++Newlines;
1356
1357       Whitespaces.replaceWhitespace(RootToken, Newlines, Indent, 0);
1358     } else {
1359       Whitespaces.replacePPWhitespace(RootToken, Newlines, Indent,
1360                                       PreviousEndOfLineColumn);
1361     }
1362   }
1363
1364   DiagnosticsEngine &Diag;
1365   FormatStyle Style;
1366   Lexer &Lex;
1367   SourceManager &SourceMgr;
1368   WhitespaceManager Whitespaces;
1369   std::vector<CharSourceRange> Ranges;
1370   std::vector<AnnotatedLine> AnnotatedLines;
1371 };
1372
1373 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1374                                SourceManager &SourceMgr,
1375                                std::vector<CharSourceRange> Ranges,
1376                                DiagnosticConsumer *DiagClient) {
1377   IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
1378   OwningPtr<DiagnosticConsumer> DiagPrinter;
1379   if (DiagClient == 0) {
1380     DiagPrinter.reset(new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts));
1381     DiagPrinter->BeginSourceFile(Lex.getLangOpts(), Lex.getPP());
1382     DiagClient = DiagPrinter.get();
1383   }
1384   DiagnosticsEngine Diagnostics(
1385       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()), &*DiagOpts,
1386       DiagClient, false);
1387   Diagnostics.setSourceManager(&SourceMgr);
1388   Formatter formatter(Diagnostics, Style, Lex, SourceMgr, Ranges);
1389   return formatter.format();
1390 }
1391
1392 LangOptions getFormattingLangOpts() {
1393   LangOptions LangOpts;
1394   LangOpts.CPlusPlus = 1;
1395   LangOpts.CPlusPlus11 = 1;
1396   LangOpts.LineComment = 1;
1397   LangOpts.Bool = 1;
1398   LangOpts.ObjC1 = 1;
1399   LangOpts.ObjC2 = 1;
1400   return LangOpts;
1401 }
1402
1403 } // namespace format
1404 } // namespace clang