Format.cpp revision 251662
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 34namespace clang { 35namespace format { 36 37FormatStyle 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 58FormatStyle 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 79FormatStyle 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 89FormatStyle 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. 103static 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 113class UnwrappedLineFormatter { 114public: 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 164private: 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 898class LexerBasedFormatTokenSource : public FormatTokenSource { 899public: 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 979private: 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 993class Formatter : public UnwrappedLineConsumer { 994public: 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 1107private: 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 1373tooling::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 1392LangOptions 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 1405