Format.cpp revision 249261
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 "TokenAnnotator.h" 19#include "UnwrappedLineParser.h" 20#include "clang/Basic/Diagnostic.h" 21#include "clang/Basic/OperatorPrecedence.h" 22#include "clang/Basic/SourceManager.h" 23#include "clang/Format/Format.h" 24#include "clang/Frontend/TextDiagnosticPrinter.h" 25#include "clang/Lex/Lexer.h" 26#include "llvm/ADT/STLExtras.h" 27#include "llvm/Support/Allocator.h" 28#include "llvm/Support/Debug.h" 29#include <queue> 30#include <string> 31 32namespace clang { 33namespace format { 34 35FormatStyle getLLVMStyle() { 36 FormatStyle LLVMStyle; 37 LLVMStyle.ColumnLimit = 80; 38 LLVMStyle.MaxEmptyLinesToKeep = 1; 39 LLVMStyle.PointerBindsToType = false; 40 LLVMStyle.DerivePointerBinding = false; 41 LLVMStyle.AccessModifierOffset = -2; 42 LLVMStyle.Standard = FormatStyle::LS_Cpp03; 43 LLVMStyle.IndentCaseLabels = false; 44 LLVMStyle.SpacesBeforeTrailingComments = 1; 45 LLVMStyle.BinPackParameters = true; 46 LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true; 47 LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false; 48 LLVMStyle.AllowShortIfStatementsOnASingleLine = false; 49 LLVMStyle.ObjCSpaceBeforeProtocolList = true; 50 LLVMStyle.PenaltyExcessCharacter = 1000000; 51 LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 5; 52 return LLVMStyle; 53} 54 55FormatStyle getGoogleStyle() { 56 FormatStyle GoogleStyle; 57 GoogleStyle.ColumnLimit = 80; 58 GoogleStyle.MaxEmptyLinesToKeep = 1; 59 GoogleStyle.PointerBindsToType = true; 60 GoogleStyle.DerivePointerBinding = true; 61 GoogleStyle.AccessModifierOffset = -1; 62 GoogleStyle.Standard = FormatStyle::LS_Auto; 63 GoogleStyle.IndentCaseLabels = true; 64 GoogleStyle.SpacesBeforeTrailingComments = 2; 65 GoogleStyle.BinPackParameters = true; 66 GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true; 67 GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true; 68 GoogleStyle.AllowShortIfStatementsOnASingleLine = false; 69 GoogleStyle.ObjCSpaceBeforeProtocolList = false; 70 GoogleStyle.PenaltyExcessCharacter = 1000000; 71 GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 100; 72 return GoogleStyle; 73} 74 75FormatStyle getChromiumStyle() { 76 FormatStyle ChromiumStyle = getGoogleStyle(); 77 ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false; 78 ChromiumStyle.BinPackParameters = false; 79 ChromiumStyle.Standard = FormatStyle::LS_Cpp03; 80 ChromiumStyle.DerivePointerBinding = false; 81 return ChromiumStyle; 82} 83 84static bool isTrailingComment(const AnnotatedToken &Tok) { 85 return Tok.is(tok::comment) && 86 (Tok.Children.empty() || Tok.Children[0].MustBreakBefore); 87} 88 89static bool isComparison(const AnnotatedToken &Tok) { 90 prec::Level Precedence = getPrecedence(Tok); 91 return Tok.Type == TT_BinaryOperator && 92 (Precedence == prec::Equality || Precedence == prec::Relational); 93} 94 95// Returns the length of everything up to the first possible line break after 96// the ), ], } or > matching \c Tok. 97static unsigned getLengthToMatchingParen(const AnnotatedToken &Tok) { 98 if (Tok.MatchingParen == NULL) 99 return 0; 100 AnnotatedToken *End = Tok.MatchingParen; 101 while (!End->Children.empty() && !End->Children[0].CanBreakBefore) { 102 End = &End->Children[0]; 103 } 104 return End->TotalLength - Tok.TotalLength + 1; 105} 106 107static size_t 108calculateColumnLimit(const FormatStyle &Style, bool InPPDirective) { 109 // In preprocessor directives reserve two chars for trailing " \" 110 return Style.ColumnLimit - (InPPDirective ? 2 : 0); 111} 112 113/// \brief Manages the whitespaces around tokens and their replacements. 114/// 115/// This includes special handling for certain constructs, e.g. the alignment of 116/// trailing line comments. 117class WhitespaceManager { 118public: 119 WhitespaceManager(SourceManager &SourceMgr, const FormatStyle &Style) 120 : SourceMgr(SourceMgr), Style(Style) {} 121 122 /// \brief Replaces the whitespace in front of \p Tok. Only call once for 123 /// each \c AnnotatedToken. 124 void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines, 125 unsigned Spaces, unsigned WhitespaceStartColumn) { 126 // 2+ newlines mean an empty line separating logic scopes. 127 if (NewLines >= 2) 128 alignComments(); 129 130 SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation(); 131 bool LineExceedsColumnLimit = Spaces + WhitespaceStartColumn + 132 Tok.FormatTok.TokenLength > Style.ColumnLimit; 133 134 // Align line comments if they are trailing or if they continue other 135 // trailing comments. 136 if (isTrailingComment(Tok)) { 137 // Remove the comment's trailing whitespace. 138 if (Tok.FormatTok.Tok.getLength() != Tok.FormatTok.TokenLength) 139 Replaces.insert(tooling::Replacement( 140 SourceMgr, TokenLoc.getLocWithOffset(Tok.FormatTok.TokenLength), 141 Tok.FormatTok.Tok.getLength() - Tok.FormatTok.TokenLength, "")); 142 143 // Align comment with other comments. 144 if ((Tok.Parent != NULL || !Comments.empty()) && 145 !LineExceedsColumnLimit) { 146 StoredComment Comment; 147 Comment.Tok = Tok.FormatTok; 148 Comment.Spaces = Spaces; 149 Comment.NewLines = NewLines; 150 Comment.MinColumn = 151 NewLines > 0 ? Spaces : WhitespaceStartColumn + Spaces; 152 Comment.MaxColumn = Style.ColumnLimit - Tok.FormatTok.TokenLength; 153 Comment.Untouchable = false; 154 Comments.push_back(Comment); 155 return; 156 } 157 } 158 159 // If this line does not have a trailing comment, align the stored comments. 160 if (Tok.Children.empty() && !isTrailingComment(Tok)) 161 alignComments(); 162 163 if (Tok.Type == TT_BlockComment) { 164 indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, false); 165 } else if (Tok.Type == TT_LineComment && LineExceedsColumnLimit) { 166 StringRef Line(SourceMgr.getCharacterData(TokenLoc), 167 Tok.FormatTok.TokenLength); 168 int StartColumn = Spaces + (NewLines == 0 ? WhitespaceStartColumn : 0); 169 StringRef Prefix = getLineCommentPrefix(Line); 170 std::string NewPrefix = std::string(StartColumn, ' ') + Prefix.str(); 171 splitLineInComment(Tok.FormatTok, Line.substr(Prefix.size()), 172 StartColumn + Prefix.size(), NewPrefix, 173 /*InPPDirective=*/ false, 174 /*CommentHasMoreLines=*/ false); 175 } 176 177 storeReplacement(Tok.FormatTok, getNewLineText(NewLines, Spaces)); 178 } 179 180 /// \brief Like \c replaceWhitespace, but additionally adds right-aligned 181 /// backslashes to escape newlines inside a preprocessor directive. 182 /// 183 /// This function and \c replaceWhitespace have the same behavior if 184 /// \c Newlines == 0. 185 void replacePPWhitespace(const AnnotatedToken &Tok, unsigned NewLines, 186 unsigned Spaces, unsigned WhitespaceStartColumn) { 187 if (Tok.Type == TT_BlockComment) 188 indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, true); 189 190 storeReplacement(Tok.FormatTok, 191 getNewLineText(NewLines, Spaces, WhitespaceStartColumn)); 192 } 193 194 /// \brief Inserts a line break into the middle of a token. 195 /// 196 /// Will break at \p Offset inside \p Tok, putting \p Prefix before the line 197 /// break and \p Postfix before the rest of the token starts in the next line. 198 /// 199 /// \p InPPDirective, \p Spaces, \p WhitespaceStartColumn and \p Style are 200 /// used to generate the correct line break. 201 void breakToken(const FormatToken &Tok, unsigned Offset, 202 unsigned ReplaceChars, StringRef Prefix, StringRef Postfix, 203 bool InPPDirective, unsigned Spaces, 204 unsigned WhitespaceStartColumn) { 205 std::string NewLineText; 206 if (!InPPDirective) 207 NewLineText = getNewLineText(1, Spaces); 208 else 209 NewLineText = getNewLineText(1, Spaces, WhitespaceStartColumn); 210 std::string ReplacementText = (Prefix + NewLineText + Postfix).str(); 211 SourceLocation Location = Tok.Tok.getLocation().getLocWithOffset(Offset); 212 Replaces.insert(tooling::Replacement(SourceMgr, Location, ReplaceChars, 213 ReplacementText)); 214 } 215 216 /// \brief Returns all the \c Replacements created during formatting. 217 const tooling::Replacements &generateReplacements() { 218 alignComments(); 219 return Replaces; 220 } 221 222 void addUntouchableComment(unsigned Column) { 223 StoredComment Comment; 224 Comment.MinColumn = Column; 225 Comment.MaxColumn = Column; 226 Comment.Untouchable = true; 227 Comments.push_back(Comment); 228 } 229 230private: 231 static StringRef getLineCommentPrefix(StringRef Comment) { 232 const char *KnownPrefixes[] = { "/// ", "///", "// ", "//" }; 233 for (size_t i = 0; i < llvm::array_lengthof(KnownPrefixes); ++i) 234 if (Comment.startswith(KnownPrefixes[i])) 235 return KnownPrefixes[i]; 236 return ""; 237 } 238 239 /// \brief Finds a common prefix of lines of a block comment to properly 240 /// indent (and possibly decorate with '*'s) added lines. 241 /// 242 /// The first line is ignored (it's special and starts with /*). The number of 243 /// lines should be more than one. 244 static StringRef findCommentLinesPrefix(ArrayRef<StringRef> Lines, 245 const char *PrefixChars = " *") { 246 assert(Lines.size() > 1); 247 StringRef Prefix(Lines[1].data(), Lines[1].find_first_not_of(PrefixChars)); 248 for (size_t i = 2; i < Lines.size(); ++i) { 249 for (size_t j = 0; j < Prefix.size() && j < Lines[i].size(); ++j) { 250 if (Prefix[j] != Lines[i][j]) { 251 Prefix = Prefix.substr(0, j); 252 break; 253 } 254 } 255 } 256 return Prefix; 257 } 258 259 /// \brief Splits one line in a line or block comment, if it doesn't fit to 260 /// provided column limit. Removes trailing whitespace in each line. 261 /// 262 /// \param Line points to the line contents without leading // or /*. 263 /// 264 /// \param StartColumn is the column where the first character of Line will be 265 /// located after formatting. 266 /// 267 /// \param LinePrefix is inserted after each line break. 268 /// 269 /// When \param InPPDirective is true, each line break will be preceded by a 270 /// backslash in the last column to make line breaks inside the comment 271 /// visually consistent with line breaks outside the comment. This only makes 272 /// sense for block comments. 273 /// 274 /// When \param CommentHasMoreLines is false, no line breaks/trailing 275 /// backslashes will be inserted after it. 276 void splitLineInComment(const FormatToken &Tok, StringRef Line, 277 size_t StartColumn, StringRef LinePrefix, 278 bool InPPDirective, bool CommentHasMoreLines, 279 const char *WhiteSpaceChars = " ") { 280 size_t ColumnLimit = calculateColumnLimit(Style, InPPDirective); 281 const char *TokenStart = SourceMgr.getCharacterData(Tok.Tok.getLocation()); 282 283 StringRef TrimmedLine = Line.rtrim(); 284 int TrailingSpaceLength = Line.size() - TrimmedLine.size(); 285 286 // Don't touch leading whitespace. 287 Line = TrimmedLine.ltrim(); 288 StartColumn += TrimmedLine.size() - Line.size(); 289 290 while (Line.size() + StartColumn > ColumnLimit) { 291 // Try to break at the last whitespace before the column limit. 292 size_t SpacePos = 293 Line.find_last_of(WhiteSpaceChars, ColumnLimit - StartColumn + 1); 294 if (SpacePos == StringRef::npos) { 295 // Try to find any whitespace in the line. 296 SpacePos = Line.find_first_of(WhiteSpaceChars); 297 if (SpacePos == StringRef::npos) // No whitespace found, give up. 298 break; 299 } 300 301 StringRef NextCut = Line.substr(0, SpacePos).rtrim(); 302 StringRef RemainingLine = Line.substr(SpacePos).ltrim(); 303 if (RemainingLine.empty()) 304 break; 305 306 if (RemainingLine == "*/" && LinePrefix.endswith("* ")) 307 LinePrefix = LinePrefix.substr(0, LinePrefix.size() - 2); 308 309 Line = RemainingLine; 310 311 size_t ReplaceChars = Line.begin() - NextCut.end(); 312 breakToken(Tok, NextCut.end() - TokenStart, ReplaceChars, "", LinePrefix, 313 InPPDirective, 0, NextCut.size() + StartColumn); 314 StartColumn = LinePrefix.size(); 315 } 316 317 if (TrailingSpaceLength > 0 || (InPPDirective && CommentHasMoreLines)) { 318 // Remove trailing whitespace/insert backslash. + 1 is for \n 319 breakToken(Tok, Line.end() - TokenStart, TrailingSpaceLength + 1, "", "", 320 InPPDirective, 0, Line.size() + StartColumn); 321 } 322 } 323 324 /// \brief Changes indentation of all lines in a block comment by Indent, 325 /// removes trailing whitespace from each line, splits lines that end up 326 /// exceeding the column limit. 327 void indentBlockComment(const AnnotatedToken &Tok, int Indent, 328 int WhitespaceStartColumn, int NewLines, 329 bool InPPDirective) { 330 assert(Tok.Type == TT_BlockComment); 331 int StartColumn = Indent + (NewLines == 0 ? WhitespaceStartColumn : 0); 332 const SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation(); 333 const int CurrentIndent = SourceMgr.getSpellingColumnNumber(TokenLoc) - 1; 334 const int IndentDelta = Indent - CurrentIndent; 335 const StringRef Text(SourceMgr.getCharacterData(TokenLoc), 336 Tok.FormatTok.TokenLength); 337 assert(Text.startswith("/*") && Text.endswith("*/")); 338 339 SmallVector<StringRef, 16> Lines; 340 Text.split(Lines, "\n"); 341 342 if (IndentDelta > 0) { 343 std::string WhiteSpace(IndentDelta, ' '); 344 for (size_t i = 1; i < Lines.size(); ++i) { 345 Replaces.insert(tooling::Replacement( 346 SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()), 347 0, WhiteSpace)); 348 } 349 } else if (IndentDelta < 0) { 350 std::string WhiteSpace(-IndentDelta, ' '); 351 // Check that the line is indented enough. 352 for (size_t i = 1; i < Lines.size(); ++i) { 353 if (!Lines[i].startswith(WhiteSpace)) 354 return; 355 } 356 for (size_t i = 1; i < Lines.size(); ++i) { 357 Replaces.insert(tooling::Replacement( 358 SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()), 359 -IndentDelta, "")); 360 } 361 } 362 363 // Split long lines in comments. 364 size_t OldPrefixSize = 0; 365 std::string NewPrefix; 366 if (Lines.size() > 1) { 367 StringRef CurrentPrefix = findCommentLinesPrefix(Lines); 368 OldPrefixSize = CurrentPrefix.size(); 369 NewPrefix = (IndentDelta < 0) 370 ? CurrentPrefix.substr(-IndentDelta).str() 371 : std::string(IndentDelta, ' ') + CurrentPrefix.str(); 372 if (CurrentPrefix.endswith("*")) { 373 NewPrefix += " "; 374 ++OldPrefixSize; 375 } 376 } else if (Tok.Parent == 0) { 377 NewPrefix = std::string(StartColumn, ' ') + " * "; 378 } 379 380 StartColumn += 2; 381 for (size_t i = 0; i < Lines.size(); ++i) { 382 StringRef Line = Lines[i].substr(i == 0 ? 2 : OldPrefixSize); 383 splitLineInComment(Tok.FormatTok, Line, StartColumn, NewPrefix, 384 InPPDirective, i != Lines.size() - 1); 385 StartColumn = NewPrefix.size(); 386 } 387 } 388 389 std::string getNewLineText(unsigned NewLines, unsigned Spaces) { 390 return std::string(NewLines, '\n') + std::string(Spaces, ' '); 391 } 392 393 std::string getNewLineText(unsigned NewLines, unsigned Spaces, 394 unsigned WhitespaceStartColumn) { 395 std::string NewLineText; 396 if (NewLines > 0) { 397 unsigned Offset = 398 std::min<int>(Style.ColumnLimit - 1, WhitespaceStartColumn); 399 for (unsigned i = 0; i < NewLines; ++i) { 400 NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' '); 401 NewLineText += "\\\n"; 402 Offset = 0; 403 } 404 } 405 return NewLineText + std::string(Spaces, ' '); 406 } 407 408 /// \brief Structure to store a comment for later layout and alignment. 409 struct StoredComment { 410 FormatToken Tok; 411 unsigned MinColumn; 412 unsigned MaxColumn; 413 unsigned NewLines; 414 unsigned Spaces; 415 bool Untouchable; 416 }; 417 SmallVector<StoredComment, 16> Comments; 418 typedef SmallVector<StoredComment, 16>::iterator comment_iterator; 419 420 /// \brief Try to align all stashed comments. 421 void alignComments() { 422 unsigned MinColumn = 0; 423 unsigned MaxColumn = UINT_MAX; 424 comment_iterator Start = Comments.begin(); 425 for (comment_iterator I = Start, E = Comments.end(); I != E; ++I) { 426 if (I->MinColumn > MaxColumn || I->MaxColumn < MinColumn) { 427 alignComments(Start, I, MinColumn); 428 MinColumn = I->MinColumn; 429 MaxColumn = I->MaxColumn; 430 Start = I; 431 } else { 432 MinColumn = std::max(MinColumn, I->MinColumn); 433 MaxColumn = std::min(MaxColumn, I->MaxColumn); 434 } 435 } 436 alignComments(Start, Comments.end(), MinColumn); 437 Comments.clear(); 438 } 439 440 /// \brief Put all the comments between \p I and \p E into \p Column. 441 void alignComments(comment_iterator I, comment_iterator E, unsigned Column) { 442 while (I != E) { 443 if (!I->Untouchable) { 444 unsigned Spaces = I->Spaces + Column - I->MinColumn; 445 storeReplacement(I->Tok, getNewLineText(I->NewLines, Spaces)); 446 } 447 ++I; 448 } 449 } 450 451 /// \brief Stores \p Text as the replacement for the whitespace in front of 452 /// \p Tok. 453 void storeReplacement(const FormatToken &Tok, const std::string Text) { 454 // Don't create a replacement, if it does not change anything. 455 if (StringRef(SourceMgr.getCharacterData(Tok.WhiteSpaceStart), 456 Tok.WhiteSpaceLength) == Text) 457 return; 458 459 Replaces.insert(tooling::Replacement(SourceMgr, Tok.WhiteSpaceStart, 460 Tok.WhiteSpaceLength, Text)); 461 } 462 463 SourceManager &SourceMgr; 464 tooling::Replacements Replaces; 465 const FormatStyle &Style; 466}; 467 468class UnwrappedLineFormatter { 469public: 470 UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr, 471 const AnnotatedLine &Line, unsigned FirstIndent, 472 const AnnotatedToken &RootToken, 473 WhitespaceManager &Whitespaces, bool StructuralError) 474 : Style(Style), SourceMgr(SourceMgr), Line(Line), 475 FirstIndent(FirstIndent), RootToken(RootToken), 476 Whitespaces(Whitespaces), Count(0) {} 477 478 /// \brief Formats an \c UnwrappedLine. 479 /// 480 /// \returns The column after the last token in the last line of the 481 /// \c UnwrappedLine. 482 unsigned format(const AnnotatedLine *NextLine) { 483 // Initialize state dependent on indent. 484 LineState State; 485 State.Column = FirstIndent; 486 State.NextToken = &RootToken; 487 State.Stack.push_back( 488 ParenState(FirstIndent, FirstIndent, !Style.BinPackParameters, 489 /*HasMultiParameterLine=*/ false)); 490 State.LineContainsContinuedForLoopSection = false; 491 State.ParenLevel = 0; 492 State.StartOfStringLiteral = 0; 493 State.StartOfLineLevel = State.ParenLevel; 494 495 DEBUG({ 496 DebugTokenState(*State.NextToken); 497 }); 498 499 // The first token has already been indented and thus consumed. 500 moveStateToNextToken(State, /*DryRun=*/ false); 501 502 // If everything fits on a single line, just put it there. 503 unsigned ColumnLimit = Style.ColumnLimit; 504 if (NextLine && NextLine->InPPDirective && 505 !NextLine->First.FormatTok.HasUnescapedNewline) 506 ColumnLimit = getColumnLimit(); 507 if (Line.Last->TotalLength <= ColumnLimit - FirstIndent) { 508 while (State.NextToken != NULL) { 509 addTokenToState(false, false, State); 510 } 511 return State.Column; 512 } 513 514 // If the ObjC method declaration does not fit on a line, we should format 515 // it with one arg per line. 516 if (Line.Type == LT_ObjCMethodDecl) 517 State.Stack.back().BreakBeforeParameter = true; 518 519 // Find best solution in solution space. 520 return analyzeSolutionSpace(State); 521 } 522 523private: 524 void DebugTokenState(const AnnotatedToken &AnnotatedTok) { 525 const Token &Tok = AnnotatedTok.FormatTok.Tok; 526 llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()), 527 Tok.getLength()); 528 llvm::errs(); 529 } 530 531 struct ParenState { 532 ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking, 533 bool HasMultiParameterLine) 534 : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0), 535 BreakBeforeClosingBrace(false), QuestionColumn(0), 536 AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false), 537 HasMultiParameterLine(HasMultiParameterLine), ColonPos(0), 538 StartOfFunctionCall(0), NestedNameSpecifierContinuation(0), 539 CallContinuation(0), VariablePos(0) {} 540 541 /// \brief The position to which a specific parenthesis level needs to be 542 /// indented. 543 unsigned Indent; 544 545 /// \brief The position of the last space on each level. 546 /// 547 /// Used e.g. to break like: 548 /// functionCall(Parameter, otherCall( 549 /// OtherParameter)); 550 unsigned LastSpace; 551 552 /// \brief The position the first "<<" operator encountered on each level. 553 /// 554 /// Used to align "<<" operators. 0 if no such operator has been encountered 555 /// on a level. 556 unsigned FirstLessLess; 557 558 /// \brief Whether a newline needs to be inserted before the block's closing 559 /// brace. 560 /// 561 /// We only want to insert a newline before the closing brace if there also 562 /// was a newline after the beginning left brace. 563 bool BreakBeforeClosingBrace; 564 565 /// \brief The column of a \c ? in a conditional expression; 566 unsigned QuestionColumn; 567 568 /// \brief Avoid bin packing, i.e. multiple parameters/elements on multiple 569 /// lines, in this context. 570 bool AvoidBinPacking; 571 572 /// \brief Break after the next comma (or all the commas in this context if 573 /// \c AvoidBinPacking is \c true). 574 bool BreakBeforeParameter; 575 576 /// \brief This context already has a line with more than one parameter. 577 bool HasMultiParameterLine; 578 579 /// \brief The position of the colon in an ObjC method declaration/call. 580 unsigned ColonPos; 581 582 /// \brief The start of the most recent function in a builder-type call. 583 unsigned StartOfFunctionCall; 584 585 /// \brief If a nested name specifier was broken over multiple lines, this 586 /// contains the start column of the second line. Otherwise 0. 587 unsigned NestedNameSpecifierContinuation; 588 589 /// \brief If a call expression was broken over multiple lines, this 590 /// contains the start column of the second line. Otherwise 0. 591 unsigned CallContinuation; 592 593 /// \brief The column of the first variable name in a variable declaration. 594 /// 595 /// Used to align further variables if necessary. 596 unsigned VariablePos; 597 598 bool operator<(const ParenState &Other) const { 599 if (Indent != Other.Indent) 600 return Indent < Other.Indent; 601 if (LastSpace != Other.LastSpace) 602 return LastSpace < Other.LastSpace; 603 if (FirstLessLess != Other.FirstLessLess) 604 return FirstLessLess < Other.FirstLessLess; 605 if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace) 606 return BreakBeforeClosingBrace; 607 if (QuestionColumn != Other.QuestionColumn) 608 return QuestionColumn < Other.QuestionColumn; 609 if (AvoidBinPacking != Other.AvoidBinPacking) 610 return AvoidBinPacking; 611 if (BreakBeforeParameter != Other.BreakBeforeParameter) 612 return BreakBeforeParameter; 613 if (HasMultiParameterLine != Other.HasMultiParameterLine) 614 return HasMultiParameterLine; 615 if (ColonPos != Other.ColonPos) 616 return ColonPos < Other.ColonPos; 617 if (StartOfFunctionCall != Other.StartOfFunctionCall) 618 return StartOfFunctionCall < Other.StartOfFunctionCall; 619 if (NestedNameSpecifierContinuation != 620 Other.NestedNameSpecifierContinuation) 621 return NestedNameSpecifierContinuation < 622 Other.NestedNameSpecifierContinuation; 623 if (CallContinuation != Other.CallContinuation) 624 return CallContinuation < Other.CallContinuation; 625 if (VariablePos != Other.VariablePos) 626 return VariablePos < Other.VariablePos; 627 return false; 628 } 629 }; 630 631 /// \brief The current state when indenting a unwrapped line. 632 /// 633 /// As the indenting tries different combinations this is copied by value. 634 struct LineState { 635 /// \brief The number of used columns in the current line. 636 unsigned Column; 637 638 /// \brief The token that needs to be next formatted. 639 const AnnotatedToken *NextToken; 640 641 /// \brief \c true if this line contains a continued for-loop section. 642 bool LineContainsContinuedForLoopSection; 643 644 /// \brief The level of nesting inside (), [], <> and {}. 645 unsigned ParenLevel; 646 647 /// \brief The \c ParenLevel at the start of this line. 648 unsigned StartOfLineLevel; 649 650 /// \brief The start column of the string literal, if we're in a string 651 /// literal sequence, 0 otherwise. 652 unsigned StartOfStringLiteral; 653 654 /// \brief A stack keeping track of properties applying to parenthesis 655 /// levels. 656 std::vector<ParenState> Stack; 657 658 /// \brief Comparison operator to be able to used \c LineState in \c map. 659 bool operator<(const LineState &Other) const { 660 if (NextToken != Other.NextToken) 661 return NextToken < Other.NextToken; 662 if (Column != Other.Column) 663 return Column < Other.Column; 664 if (LineContainsContinuedForLoopSection != 665 Other.LineContainsContinuedForLoopSection) 666 return LineContainsContinuedForLoopSection; 667 if (ParenLevel != Other.ParenLevel) 668 return ParenLevel < Other.ParenLevel; 669 if (StartOfLineLevel != Other.StartOfLineLevel) 670 return StartOfLineLevel < Other.StartOfLineLevel; 671 if (StartOfStringLiteral != Other.StartOfStringLiteral) 672 return StartOfStringLiteral < Other.StartOfStringLiteral; 673 return Stack < Other.Stack; 674 } 675 }; 676 677 /// \brief Appends the next token to \p State and updates information 678 /// necessary for indentation. 679 /// 680 /// Puts the token on the current line if \p Newline is \c true and adds a 681 /// line break and necessary indentation otherwise. 682 /// 683 /// If \p DryRun is \c false, also creates and stores the required 684 /// \c Replacement. 685 unsigned addTokenToState(bool Newline, bool DryRun, LineState &State) { 686 const AnnotatedToken &Current = *State.NextToken; 687 const AnnotatedToken &Previous = *State.NextToken->Parent; 688 689 if (State.Stack.size() == 0 || Current.Type == TT_ImplicitStringLiteral) { 690 State.Column += State.NextToken->FormatTok.WhiteSpaceLength + 691 State.NextToken->FormatTok.TokenLength; 692 if (State.NextToken->Children.empty()) 693 State.NextToken = NULL; 694 else 695 State.NextToken = &State.NextToken->Children[0]; 696 return 0; 697 } 698 699 // If we are continuing an expression, we want to indent an extra 4 spaces. 700 unsigned ContinuationIndent = 701 std::max(State.Stack.back().LastSpace, State.Stack.back().Indent) + 4; 702 if (Newline) { 703 unsigned WhitespaceStartColumn = State.Column; 704 if (Current.is(tok::r_brace)) { 705 State.Column = Line.Level * 2; 706 } else if (Current.is(tok::string_literal) && 707 State.StartOfStringLiteral != 0) { 708 State.Column = State.StartOfStringLiteral; 709 State.Stack.back().BreakBeforeParameter = true; 710 } else if (Current.is(tok::lessless) && 711 State.Stack.back().FirstLessLess != 0) { 712 State.Column = State.Stack.back().FirstLessLess; 713 } else if (Previous.is(tok::coloncolon)) { 714 if (State.Stack.back().NestedNameSpecifierContinuation == 0) { 715 State.Column = ContinuationIndent; 716 State.Stack.back().NestedNameSpecifierContinuation = State.Column; 717 } else { 718 State.Column = State.Stack.back().NestedNameSpecifierContinuation; 719 } 720 } else if (Current.isOneOf(tok::period, tok::arrow)) { 721 if (State.Stack.back().CallContinuation == 0) { 722 State.Column = ContinuationIndent; 723 State.Stack.back().CallContinuation = State.Column; 724 } else { 725 State.Column = State.Stack.back().CallContinuation; 726 } 727 } else if (Current.Type == TT_ConditionalExpr) { 728 State.Column = State.Stack.back().QuestionColumn; 729 } else if (Previous.is(tok::comma) && 730 State.Stack.back().VariablePos != 0) { 731 State.Column = State.Stack.back().VariablePos; 732 } else if (Previous.ClosesTemplateDeclaration || 733 (Current.Type == TT_StartOfName && State.ParenLevel == 0)) { 734 State.Column = State.Stack.back().Indent; 735 } else if (Current.Type == TT_ObjCSelectorName) { 736 if (State.Stack.back().ColonPos > Current.FormatTok.TokenLength) { 737 State.Column = 738 State.Stack.back().ColonPos - Current.FormatTok.TokenLength; 739 } else { 740 State.Column = State.Stack.back().Indent; 741 State.Stack.back().ColonPos = 742 State.Column + Current.FormatTok.TokenLength; 743 } 744 } else if (Current.Type == TT_StartOfName || Current.is(tok::question) || 745 Previous.is(tok::equal) || isComparison(Previous) || 746 Previous.Type == TT_ObjCMethodExpr) { 747 State.Column = ContinuationIndent; 748 } else { 749 State.Column = State.Stack.back().Indent; 750 // Ensure that we fall back to indenting 4 spaces instead of just 751 // flushing continuations left. 752 if (State.Column == FirstIndent) 753 State.Column += 4; 754 } 755 756 if (Current.is(tok::question)) 757 State.Stack.back().BreakBeforeParameter = true; 758 if (Previous.isOneOf(tok::comma, tok::semi) && 759 !State.Stack.back().AvoidBinPacking) 760 State.Stack.back().BreakBeforeParameter = false; 761 762 if (!DryRun) { 763 unsigned NewLines = 1; 764 if (Current.Type == TT_LineComment) 765 NewLines = 766 std::max(NewLines, std::min(Current.FormatTok.NewlinesBefore, 767 Style.MaxEmptyLinesToKeep + 1)); 768 if (!Line.InPPDirective) 769 Whitespaces.replaceWhitespace(Current, NewLines, State.Column, 770 WhitespaceStartColumn); 771 else 772 Whitespaces.replacePPWhitespace(Current, NewLines, State.Column, 773 WhitespaceStartColumn); 774 } 775 776 State.Stack.back().LastSpace = State.Column; 777 State.StartOfLineLevel = State.ParenLevel; 778 779 // Any break on this level means that the parent level has been broken 780 // and we need to avoid bin packing there. 781 for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) { 782 State.Stack[i].BreakBeforeParameter = true; 783 } 784 if (Current.isOneOf(tok::period, tok::arrow)) 785 State.Stack.back().BreakBeforeParameter = true; 786 787 // If we break after {, we should also break before the corresponding }. 788 if (Previous.is(tok::l_brace)) 789 State.Stack.back().BreakBeforeClosingBrace = true; 790 791 if (State.Stack.back().AvoidBinPacking) { 792 // If we are breaking after '(', '{', '<', this is not bin packing 793 // unless AllowAllParametersOfDeclarationOnNextLine is false. 794 if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace)) || 795 (!Style.AllowAllParametersOfDeclarationOnNextLine && 796 Line.MustBeDeclaration)) 797 State.Stack.back().BreakBeforeParameter = true; 798 } 799 } else { 800 if (Current.is(tok::equal) && 801 (RootToken.is(tok::kw_for) || State.ParenLevel == 0) && 802 State.Stack.back().VariablePos == 0) { 803 State.Stack.back().VariablePos = State.Column; 804 // Move over * and & if they are bound to the variable name. 805 const AnnotatedToken *Tok = &Previous; 806 while (Tok && 807 State.Stack.back().VariablePos >= Tok->FormatTok.TokenLength) { 808 State.Stack.back().VariablePos -= Tok->FormatTok.TokenLength; 809 if (Tok->SpacesRequiredBefore != 0) 810 break; 811 Tok = Tok->Parent; 812 } 813 if (Previous.PartOfMultiVariableDeclStmt) 814 State.Stack.back().LastSpace = State.Stack.back().VariablePos; 815 } 816 817 unsigned Spaces = State.NextToken->SpacesRequiredBefore; 818 819 if (!DryRun) 820 Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column); 821 822 if (Current.Type == TT_ObjCSelectorName && 823 State.Stack.back().ColonPos == 0) { 824 if (State.Stack.back().Indent + Current.LongestObjCSelectorName > 825 State.Column + Spaces + Current.FormatTok.TokenLength) 826 State.Stack.back().ColonPos = 827 State.Stack.back().Indent + Current.LongestObjCSelectorName; 828 else 829 State.Stack.back().ColonPos = 830 State.Column + Spaces + Current.FormatTok.TokenLength; 831 } 832 833 if (Current.Type != TT_LineComment && 834 (Previous.isOneOf(tok::l_paren, tok::l_brace) || 835 State.NextToken->Parent->Type == TT_TemplateOpener)) 836 State.Stack.back().Indent = State.Column + Spaces; 837 if (Previous.is(tok::comma) && !isTrailingComment(Current)) 838 State.Stack.back().HasMultiParameterLine = true; 839 840 State.Column += Spaces; 841 if (Current.is(tok::l_paren) && Previous.isOneOf(tok::kw_if, tok::kw_for)) 842 // Treat the condition inside an if as if it was a second function 843 // parameter, i.e. let nested calls have an indent of 4. 844 State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(". 845 else if (Previous.is(tok::comma)) 846 State.Stack.back().LastSpace = State.Column; 847 else if ((Previous.Type == TT_BinaryOperator || 848 Previous.Type == TT_ConditionalExpr || 849 Previous.Type == TT_CtorInitializerColon) && 850 getPrecedence(Previous) != prec::Assignment) 851 State.Stack.back().LastSpace = State.Column; 852 else if (Previous.Type == TT_InheritanceColon) 853 State.Stack.back().Indent = State.Column; 854 else if (Previous.ParameterCount > 1 && 855 (Previous.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) || 856 Previous.Type == TT_TemplateOpener)) 857 // If this function has multiple parameters, indent nested calls from 858 // the start of the first parameter. 859 State.Stack.back().LastSpace = State.Column; 860 } 861 862 return moveStateToNextToken(State, DryRun); 863 } 864 865 /// \brief Mark the next token as consumed in \p State and modify its stacks 866 /// accordingly. 867 unsigned moveStateToNextToken(LineState &State, bool DryRun) { 868 const AnnotatedToken &Current = *State.NextToken; 869 assert(State.Stack.size()); 870 871 if (Current.Type == TT_InheritanceColon) 872 State.Stack.back().AvoidBinPacking = true; 873 if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0) 874 State.Stack.back().FirstLessLess = State.Column; 875 if (Current.is(tok::question)) 876 State.Stack.back().QuestionColumn = State.Column; 877 if (Current.isOneOf(tok::period, tok::arrow) && 878 Line.Type == LT_BuilderTypeCall && State.ParenLevel == 0) 879 State.Stack.back().StartOfFunctionCall = 880 Current.LastInChainOfCalls ? 0 : State.Column; 881 if (Current.Type == TT_CtorInitializerColon) { 882 if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine) 883 State.Stack.back().AvoidBinPacking = true; 884 State.Stack.back().BreakBeforeParameter = false; 885 } 886 887 // In ObjC method declaration we align on the ":" of parameters, but we need 888 // to ensure that we indent parameters on subsequent lines by at least 4. 889 if (Current.Type == TT_ObjCMethodSpecifier) 890 State.Stack.back().Indent += 4; 891 892 // Insert scopes created by fake parenthesis. 893 for (unsigned i = 0, e = Current.FakeLParens; i != e; ++i) { 894 ParenState NewParenState = State.Stack.back(); 895 NewParenState.Indent = std::max(State.Column, State.Stack.back().Indent); 896 NewParenState.BreakBeforeParameter = false; 897 State.Stack.push_back(NewParenState); 898 } 899 900 // If we encounter an opening (, [, { or <, we add a level to our stacks to 901 // prepare for the following tokens. 902 if (Current.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) || 903 State.NextToken->Type == TT_TemplateOpener) { 904 unsigned NewIndent; 905 bool AvoidBinPacking; 906 if (Current.is(tok::l_brace)) { 907 NewIndent = 2 + State.Stack.back().LastSpace; 908 AvoidBinPacking = false; 909 } else { 910 NewIndent = 4 + std::max(State.Stack.back().LastSpace, 911 State.Stack.back().StartOfFunctionCall); 912 AvoidBinPacking = 913 !Style.BinPackParameters || State.Stack.back().AvoidBinPacking; 914 } 915 State.Stack.push_back( 916 ParenState(NewIndent, State.Stack.back().LastSpace, AvoidBinPacking, 917 State.Stack.back().HasMultiParameterLine)); 918 ++State.ParenLevel; 919 } 920 921 // If this '[' opens an ObjC call, determine whether all parameters fit into 922 // one line and put one per line if they don't. 923 if (Current.is(tok::l_square) && Current.Type == TT_ObjCMethodExpr && 924 Current.MatchingParen != NULL) { 925 if (getLengthToMatchingParen(Current) + State.Column > getColumnLimit()) 926 State.Stack.back().BreakBeforeParameter = true; 927 } 928 929 // If we encounter a closing ), ], } or >, we can remove a level from our 930 // stacks. 931 if (Current.isOneOf(tok::r_paren, tok::r_square) || 932 (Current.is(tok::r_brace) && State.NextToken != &RootToken) || 933 State.NextToken->Type == TT_TemplateCloser) { 934 State.Stack.pop_back(); 935 --State.ParenLevel; 936 } 937 938 // Remove scopes created by fake parenthesis. 939 for (unsigned i = 0, e = Current.FakeRParens; i != e; ++i) { 940 unsigned VariablePos = State.Stack.back().VariablePos; 941 State.Stack.pop_back(); 942 State.Stack.back().VariablePos = VariablePos; 943 } 944 945 if (Current.is(tok::string_literal)) { 946 State.StartOfStringLiteral = State.Column; 947 } else if (Current.isNot(tok::comment)) { 948 State.StartOfStringLiteral = 0; 949 } 950 951 State.Column += Current.FormatTok.TokenLength; 952 953 if (State.NextToken->Children.empty()) 954 State.NextToken = NULL; 955 else 956 State.NextToken = &State.NextToken->Children[0]; 957 958 return breakProtrudingToken(Current, State, DryRun); 959 } 960 961 /// \brief If the current token sticks out over the end of the line, break 962 /// it if possible. 963 unsigned breakProtrudingToken(const AnnotatedToken &Current, LineState &State, 964 bool DryRun) { 965 if (Current.isNot(tok::string_literal)) 966 return 0; 967 // Only break up default narrow strings. 968 const char *LiteralData = Current.FormatTok.Tok.getLiteralData(); 969 if (!LiteralData || *LiteralData != '"') 970 return 0; 971 972 unsigned Penalty = 0; 973 unsigned TailOffset = 0; 974 unsigned TailLength = Current.FormatTok.TokenLength; 975 unsigned StartColumn = State.Column - Current.FormatTok.TokenLength; 976 unsigned OffsetFromStart = 0; 977 while (StartColumn + TailLength > getColumnLimit()) { 978 StringRef Text = StringRef(LiteralData + TailOffset, TailLength); 979 if (StartColumn + OffsetFromStart + 1 > getColumnLimit()) 980 break; 981 StringRef::size_type SplitPoint = getSplitPoint( 982 Text, getColumnLimit() - StartColumn - OffsetFromStart - 1); 983 if (SplitPoint == StringRef::npos) 984 break; 985 assert(SplitPoint != 0); 986 // +2, because 'Text' starts after the opening quotes, and does not 987 // include the closing quote we need to insert. 988 unsigned WhitespaceStartColumn = 989 StartColumn + OffsetFromStart + SplitPoint + 2; 990 State.Stack.back().LastSpace = StartColumn; 991 if (!DryRun) { 992 Whitespaces.breakToken(Current.FormatTok, TailOffset + SplitPoint + 1, 993 0, "\"", "\"", Line.InPPDirective, StartColumn, 994 WhitespaceStartColumn); 995 } 996 TailOffset += SplitPoint + 1; 997 TailLength -= SplitPoint + 1; 998 OffsetFromStart = 1; 999 Penalty += Style.PenaltyExcessCharacter; 1000 for (unsigned i = 0, e = State.Stack.size(); i != e; ++i) 1001 State.Stack[i].BreakBeforeParameter = true; 1002 } 1003 State.Column = StartColumn + TailLength; 1004 return Penalty; 1005 } 1006 1007 StringRef::size_type 1008 getSplitPoint(StringRef Text, StringRef::size_type Offset) { 1009 StringRef::size_type SpaceOffset = Text.rfind(' ', Offset); 1010 if (SpaceOffset != StringRef::npos && SpaceOffset != 0) 1011 return SpaceOffset; 1012 StringRef::size_type SlashOffset = Text.rfind('/', Offset); 1013 if (SlashOffset != StringRef::npos && SlashOffset != 0) 1014 return SlashOffset; 1015 StringRef::size_type Split = getStartOfCharacter(Text, Offset); 1016 if (Split != StringRef::npos && Split > 1) 1017 // Do not split at 0. 1018 return Split - 1; 1019 return StringRef::npos; 1020 } 1021 1022 StringRef::size_type 1023 getStartOfCharacter(StringRef Text, StringRef::size_type Offset) { 1024 StringRef::size_type NextEscape = Text.find('\\'); 1025 while (NextEscape != StringRef::npos && NextEscape < Offset) { 1026 StringRef::size_type SequenceLength = 1027 getEscapeSequenceLength(Text.substr(NextEscape)); 1028 if (Offset < NextEscape + SequenceLength) 1029 return NextEscape; 1030 NextEscape = Text.find('\\', NextEscape + SequenceLength); 1031 } 1032 return Offset; 1033 } 1034 1035 unsigned getEscapeSequenceLength(StringRef Text) { 1036 assert(Text[0] == '\\'); 1037 if (Text.size() < 2) 1038 return 1; 1039 1040 switch (Text[1]) { 1041 case 'u': 1042 return 6; 1043 case 'U': 1044 return 10; 1045 case 'x': 1046 return getHexLength(Text); 1047 default: 1048 if (Text[1] >= '0' && Text[1] <= '7') 1049 return getOctalLength(Text); 1050 return 2; 1051 } 1052 } 1053 1054 unsigned getHexLength(StringRef Text) { 1055 unsigned I = 2; // Point after '\x'. 1056 while (I < Text.size() && ((Text[I] >= '0' && Text[I] <= '9') || 1057 (Text[I] >= 'a' && Text[I] <= 'f') || 1058 (Text[I] >= 'A' && Text[I] <= 'F'))) { 1059 ++I; 1060 } 1061 return I; 1062 } 1063 1064 unsigned getOctalLength(StringRef Text) { 1065 unsigned I = 1; 1066 while (I < Text.size() && I < 4 && (Text[I] >= '0' && Text[I] <= '7')) { 1067 ++I; 1068 } 1069 return I; 1070 } 1071 1072 unsigned getColumnLimit() { 1073 return calculateColumnLimit(Style, Line.InPPDirective); 1074 } 1075 1076 /// \brief An edge in the solution space from \c Previous->State to \c State, 1077 /// inserting a newline dependent on the \c NewLine. 1078 struct StateNode { 1079 StateNode(const LineState &State, bool NewLine, StateNode *Previous) 1080 : State(State), NewLine(NewLine), Previous(Previous) {} 1081 LineState State; 1082 bool NewLine; 1083 StateNode *Previous; 1084 }; 1085 1086 /// \brief A pair of <penalty, count> that is used to prioritize the BFS on. 1087 /// 1088 /// In case of equal penalties, we want to prefer states that were inserted 1089 /// first. During state generation we make sure that we insert states first 1090 /// that break the line as late as possible. 1091 typedef std::pair<unsigned, unsigned> OrderedPenalty; 1092 1093 /// \brief An item in the prioritized BFS search queue. The \c StateNode's 1094 /// \c State has the given \c OrderedPenalty. 1095 typedef std::pair<OrderedPenalty, StateNode *> QueueItem; 1096 1097 /// \brief The BFS queue type. 1098 typedef std::priority_queue<QueueItem, std::vector<QueueItem>, 1099 std::greater<QueueItem> > QueueType; 1100 1101 /// \brief Analyze the entire solution space starting from \p InitialState. 1102 /// 1103 /// This implements a variant of Dijkstra's algorithm on the graph that spans 1104 /// the solution space (\c LineStates are the nodes). The algorithm tries to 1105 /// find the shortest path (the one with lowest penalty) from \p InitialState 1106 /// to a state where all tokens are placed. 1107 unsigned analyzeSolutionSpace(LineState &InitialState) { 1108 std::set<LineState> Seen; 1109 1110 // Insert start element into queue. 1111 StateNode *Node = 1112 new (Allocator.Allocate()) StateNode(InitialState, false, NULL); 1113 Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); 1114 ++Count; 1115 1116 // While not empty, take first element and follow edges. 1117 while (!Queue.empty()) { 1118 unsigned Penalty = Queue.top().first.first; 1119 StateNode *Node = Queue.top().second; 1120 if (Node->State.NextToken == NULL) { 1121 DEBUG(llvm::errs() << "\n---\nPenalty for line: " << Penalty << "\n"); 1122 break; 1123 } 1124 Queue.pop(); 1125 1126 if (!Seen.insert(Node->State).second) 1127 // State already examined with lower penalty. 1128 continue; 1129 1130 addNextStateToQueue(Penalty, Node, /*NewLine=*/ false); 1131 addNextStateToQueue(Penalty, Node, /*NewLine=*/ true); 1132 } 1133 1134 if (Queue.empty()) 1135 // We were unable to find a solution, do nothing. 1136 // FIXME: Add diagnostic? 1137 return 0; 1138 1139 // Reconstruct the solution. 1140 reconstructPath(InitialState, Queue.top().second); 1141 DEBUG(llvm::errs() << "---\n"); 1142 1143 // Return the column after the last token of the solution. 1144 return Queue.top().second->State.Column; 1145 } 1146 1147 void reconstructPath(LineState &State, StateNode *Current) { 1148 // FIXME: This recursive implementation limits the possible number 1149 // of tokens per line if compiled into a binary with small stack space. 1150 // To become more independent of stack frame limitations we would need 1151 // to also change the TokenAnnotator. 1152 if (Current->Previous == NULL) 1153 return; 1154 reconstructPath(State, Current->Previous); 1155 DEBUG({ 1156 if (Current->NewLine) { 1157 llvm::errs() 1158 << "Penalty for splitting before " 1159 << Current->Previous->State.NextToken->FormatTok.Tok.getName() 1160 << ": " << Current->Previous->State.NextToken->SplitPenalty << "\n"; 1161 } 1162 }); 1163 addTokenToState(Current->NewLine, false, State); 1164 } 1165 1166 /// \brief Add the following state to the analysis queue \c Queue. 1167 /// 1168 /// Assume the current state is \p PreviousNode and has been reached with a 1169 /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. 1170 void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, 1171 bool NewLine) { 1172 if (NewLine && !canBreak(PreviousNode->State)) 1173 return; 1174 if (!NewLine && mustBreak(PreviousNode->State)) 1175 return; 1176 if (NewLine) 1177 Penalty += PreviousNode->State.NextToken->SplitPenalty; 1178 1179 StateNode *Node = new (Allocator.Allocate()) 1180 StateNode(PreviousNode->State, NewLine, PreviousNode); 1181 Penalty += addTokenToState(NewLine, true, Node->State); 1182 if (Node->State.Column > getColumnLimit()) { 1183 unsigned ExcessCharacters = Node->State.Column - getColumnLimit(); 1184 Penalty += Style.PenaltyExcessCharacter * ExcessCharacters; 1185 } 1186 1187 Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node)); 1188 ++Count; 1189 } 1190 1191 /// \brief Returns \c true, if a line break after \p State is allowed. 1192 bool canBreak(const LineState &State) { 1193 if (!State.NextToken->CanBreakBefore && 1194 !(State.NextToken->is(tok::r_brace) && 1195 State.Stack.back().BreakBeforeClosingBrace)) 1196 return false; 1197 // Trying to insert a parameter on a new line if there are already more than 1198 // one parameter on the current line is bin packing. 1199 if (State.Stack.back().HasMultiParameterLine && 1200 State.Stack.back().AvoidBinPacking) 1201 return false; 1202 return true; 1203 } 1204 1205 /// \brief Returns \c true, if a line break after \p State is mandatory. 1206 bool mustBreak(const LineState &State) { 1207 if (State.NextToken->MustBreakBefore) 1208 return true; 1209 if (State.NextToken->is(tok::r_brace) && 1210 State.Stack.back().BreakBeforeClosingBrace) 1211 return true; 1212 if (State.NextToken->Parent->is(tok::semi) && 1213 State.LineContainsContinuedForLoopSection) 1214 return true; 1215 if ((State.NextToken->Parent->isOneOf(tok::comma, tok::semi) || 1216 State.NextToken->is(tok::question) || 1217 State.NextToken->Type == TT_ConditionalExpr) && 1218 State.Stack.back().BreakBeforeParameter && 1219 !isTrailingComment(*State.NextToken) && 1220 State.NextToken->isNot(tok::r_paren) && 1221 State.NextToken->isNot(tok::r_brace)) 1222 return true; 1223 // FIXME: Comparing LongestObjCSelectorName to 0 is a hacky way of finding 1224 // out whether it is the first parameter. Clean this up. 1225 if (State.NextToken->Type == TT_ObjCSelectorName && 1226 State.NextToken->LongestObjCSelectorName == 0 && 1227 State.Stack.back().BreakBeforeParameter) 1228 return true; 1229 if ((State.NextToken->Type == TT_CtorInitializerColon || 1230 (State.NextToken->Parent->ClosesTemplateDeclaration && 1231 State.ParenLevel == 0))) 1232 return true; 1233 if (State.NextToken->Type == TT_InlineASMColon) 1234 return true; 1235 // This prevents breaks like: 1236 // ... 1237 // SomeParameter, OtherParameter).DoSomething( 1238 // ... 1239 // As they hide "DoSomething" and generally bad for readability. 1240 if (State.NextToken->isOneOf(tok::period, tok::arrow) && 1241 getRemainingLength(State) + State.Column > getColumnLimit() && 1242 State.ParenLevel < State.StartOfLineLevel) 1243 return true; 1244 return false; 1245 } 1246 1247 // Returns the total number of columns required for the remaining tokens. 1248 unsigned getRemainingLength(const LineState &State) { 1249 if (State.NextToken && State.NextToken->Parent) 1250 return Line.Last->TotalLength - State.NextToken->Parent->TotalLength; 1251 return 0; 1252 } 1253 1254 FormatStyle Style; 1255 SourceManager &SourceMgr; 1256 const AnnotatedLine &Line; 1257 const unsigned FirstIndent; 1258 const AnnotatedToken &RootToken; 1259 WhitespaceManager &Whitespaces; 1260 1261 llvm::SpecificBumpPtrAllocator<StateNode> Allocator; 1262 QueueType Queue; 1263 // Increasing count of \c StateNode items we have created. This is used 1264 // to create a deterministic order independent of the container. 1265 unsigned Count; 1266}; 1267 1268class LexerBasedFormatTokenSource : public FormatTokenSource { 1269public: 1270 LexerBasedFormatTokenSource(Lexer &Lex, SourceManager &SourceMgr) 1271 : GreaterStashed(false), Lex(Lex), SourceMgr(SourceMgr), 1272 IdentTable(Lex.getLangOpts()) { 1273 Lex.SetKeepWhitespaceMode(true); 1274 } 1275 1276 virtual FormatToken getNextToken() { 1277 if (GreaterStashed) { 1278 FormatTok.NewlinesBefore = 0; 1279 FormatTok.WhiteSpaceStart = 1280 FormatTok.Tok.getLocation().getLocWithOffset(1); 1281 FormatTok.WhiteSpaceLength = 0; 1282 GreaterStashed = false; 1283 return FormatTok; 1284 } 1285 1286 FormatTok = FormatToken(); 1287 Lex.LexFromRawLexer(FormatTok.Tok); 1288 StringRef Text = rawTokenText(FormatTok.Tok); 1289 FormatTok.WhiteSpaceStart = FormatTok.Tok.getLocation(); 1290 if (SourceMgr.getFileOffset(FormatTok.WhiteSpaceStart) == 0) 1291 FormatTok.IsFirst = true; 1292 1293 // Consume and record whitespace until we find a significant token. 1294 while (FormatTok.Tok.is(tok::unknown)) { 1295 unsigned Newlines = Text.count('\n'); 1296 if (Newlines > 0) 1297 FormatTok.LastNewlineOffset = 1298 FormatTok.WhiteSpaceLength + Text.rfind('\n') + 1; 1299 unsigned EscapedNewlines = Text.count("\\\n"); 1300 FormatTok.NewlinesBefore += Newlines; 1301 FormatTok.HasUnescapedNewline |= EscapedNewlines != Newlines; 1302 FormatTok.WhiteSpaceLength += FormatTok.Tok.getLength(); 1303 1304 if (FormatTok.Tok.is(tok::eof)) 1305 return FormatTok; 1306 Lex.LexFromRawLexer(FormatTok.Tok); 1307 Text = rawTokenText(FormatTok.Tok); 1308 } 1309 1310 // Now FormatTok is the next non-whitespace token. 1311 FormatTok.TokenLength = Text.size(); 1312 1313 // In case the token starts with escaped newlines, we want to 1314 // take them into account as whitespace - this pattern is quite frequent 1315 // in macro definitions. 1316 // FIXME: What do we want to do with other escaped spaces, and escaped 1317 // spaces or newlines in the middle of tokens? 1318 // FIXME: Add a more explicit test. 1319 unsigned i = 0; 1320 while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') { 1321 // FIXME: ++FormatTok.NewlinesBefore is missing... 1322 FormatTok.WhiteSpaceLength += 2; 1323 FormatTok.TokenLength -= 2; 1324 i += 2; 1325 } 1326 1327 if (FormatTok.Tok.is(tok::raw_identifier)) { 1328 IdentifierInfo &Info = IdentTable.get(Text); 1329 FormatTok.Tok.setIdentifierInfo(&Info); 1330 FormatTok.Tok.setKind(Info.getTokenID()); 1331 } 1332 1333 if (FormatTok.Tok.is(tok::greatergreater)) { 1334 FormatTok.Tok.setKind(tok::greater); 1335 FormatTok.TokenLength = 1; 1336 GreaterStashed = true; 1337 } 1338 1339 // If we reformat comments, we remove trailing whitespace. Update the length 1340 // accordingly. 1341 if (FormatTok.Tok.is(tok::comment)) 1342 FormatTok.TokenLength = Text.rtrim().size(); 1343 1344 return FormatTok; 1345 } 1346 1347 IdentifierTable &getIdentTable() { return IdentTable; } 1348 1349private: 1350 FormatToken FormatTok; 1351 bool GreaterStashed; 1352 Lexer &Lex; 1353 SourceManager &SourceMgr; 1354 IdentifierTable IdentTable; 1355 1356 /// Returns the text of \c FormatTok. 1357 StringRef rawTokenText(Token &Tok) { 1358 return StringRef(SourceMgr.getCharacterData(Tok.getLocation()), 1359 Tok.getLength()); 1360 } 1361}; 1362 1363class Formatter : public UnwrappedLineConsumer { 1364public: 1365 Formatter(DiagnosticsEngine &Diag, const FormatStyle &Style, Lexer &Lex, 1366 SourceManager &SourceMgr, 1367 const std::vector<CharSourceRange> &Ranges) 1368 : Diag(Diag), Style(Style), Lex(Lex), SourceMgr(SourceMgr), 1369 Whitespaces(SourceMgr, Style), Ranges(Ranges) {} 1370 1371 virtual ~Formatter() {} 1372 1373 tooling::Replacements format() { 1374 LexerBasedFormatTokenSource Tokens(Lex, SourceMgr); 1375 UnwrappedLineParser Parser(Diag, Style, Tokens, *this); 1376 StructuralError = Parser.parse(); 1377 unsigned PreviousEndOfLineColumn = 0; 1378 TokenAnnotator Annotator(Style, SourceMgr, Lex, 1379 Tokens.getIdentTable().get("in")); 1380 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1381 Annotator.annotate(AnnotatedLines[i]); 1382 } 1383 deriveLocalStyle(); 1384 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1385 Annotator.calculateFormattingInformation(AnnotatedLines[i]); 1386 1387 // Adapt level to the next line if this is a comment. 1388 // FIXME: Can/should this be done in the UnwrappedLineParser? 1389 if (i + 1 != e && AnnotatedLines[i].First.is(tok::comment) && 1390 AnnotatedLines[i].First.Children.empty() && 1391 AnnotatedLines[i + 1].First.isNot(tok::r_brace)) 1392 AnnotatedLines[i].Level = AnnotatedLines[i + 1].Level; 1393 } 1394 std::vector<int> IndentForLevel; 1395 bool PreviousLineWasTouched = false; 1396 const AnnotatedToken *PreviousLineLastToken = 0; 1397 for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(), 1398 E = AnnotatedLines.end(); 1399 I != E; ++I) { 1400 const AnnotatedLine &TheLine = *I; 1401 const FormatToken &FirstTok = TheLine.First.FormatTok; 1402 int Offset = getIndentOffset(TheLine.First); 1403 while (IndentForLevel.size() <= TheLine.Level) 1404 IndentForLevel.push_back(-1); 1405 IndentForLevel.resize(TheLine.Level + 1); 1406 bool WasMoved = PreviousLineWasTouched && FirstTok.NewlinesBefore == 0; 1407 if (TheLine.First.is(tok::eof)) { 1408 if (PreviousLineWasTouched) { 1409 unsigned NewLines = std::min(FirstTok.NewlinesBefore, 1u); 1410 Whitespaces.replaceWhitespace(TheLine.First, NewLines, /*Indent*/ 0, 1411 /*WhitespaceStartColumn*/ 0); 1412 } 1413 } else if (TheLine.Type != LT_Invalid && 1414 (WasMoved || touchesLine(TheLine))) { 1415 unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level); 1416 unsigned Indent = LevelIndent; 1417 if (static_cast<int>(Indent) + Offset >= 0) 1418 Indent += Offset; 1419 if (!FirstTok.WhiteSpaceStart.isValid() || StructuralError) { 1420 Indent = LevelIndent = 1421 SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1; 1422 } else { 1423 formatFirstToken(TheLine.First, PreviousLineLastToken, Indent, 1424 TheLine.InPPDirective, PreviousEndOfLineColumn); 1425 } 1426 tryFitMultipleLinesInOne(Indent, I, E); 1427 UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent, 1428 TheLine.First, Whitespaces, 1429 StructuralError); 1430 PreviousEndOfLineColumn = 1431 Formatter.format(I + 1 != E ? &*(I + 1) : NULL); 1432 IndentForLevel[TheLine.Level] = LevelIndent; 1433 PreviousLineWasTouched = true; 1434 } else { 1435 if (FirstTok.NewlinesBefore > 0 || FirstTok.IsFirst) { 1436 unsigned Indent = 1437 SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1; 1438 unsigned LevelIndent = Indent; 1439 if (static_cast<int>(LevelIndent) - Offset >= 0) 1440 LevelIndent -= Offset; 1441 if (TheLine.First.isNot(tok::comment)) 1442 IndentForLevel[TheLine.Level] = LevelIndent; 1443 1444 // Remove trailing whitespace of the previous line if it was touched. 1445 if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) 1446 formatFirstToken(TheLine.First, PreviousLineLastToken, Indent, 1447 TheLine.InPPDirective, PreviousEndOfLineColumn); 1448 } 1449 // If we did not reformat this unwrapped line, the column at the end of 1450 // the last token is unchanged - thus, we can calculate the end of the 1451 // last token. 1452 SourceLocation LastLoc = TheLine.Last->FormatTok.Tok.getLocation(); 1453 PreviousEndOfLineColumn = 1454 SourceMgr.getSpellingColumnNumber(LastLoc) + 1455 Lex.MeasureTokenLength(LastLoc, SourceMgr, Lex.getLangOpts()) - 1; 1456 PreviousLineWasTouched = false; 1457 if (TheLine.Last->is(tok::comment)) 1458 Whitespaces.addUntouchableComment(SourceMgr.getSpellingColumnNumber( 1459 TheLine.Last->FormatTok.Tok.getLocation()) - 1); 1460 } 1461 PreviousLineLastToken = I->Last; 1462 } 1463 return Whitespaces.generateReplacements(); 1464 } 1465 1466private: 1467 void deriveLocalStyle() { 1468 unsigned CountBoundToVariable = 0; 1469 unsigned CountBoundToType = 0; 1470 bool HasCpp03IncompatibleFormat = false; 1471 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1472 if (AnnotatedLines[i].First.Children.empty()) 1473 continue; 1474 AnnotatedToken *Tok = &AnnotatedLines[i].First.Children[0]; 1475 while (!Tok->Children.empty()) { 1476 if (Tok->Type == TT_PointerOrReference) { 1477 bool SpacesBefore = Tok->FormatTok.WhiteSpaceLength > 0; 1478 bool SpacesAfter = Tok->Children[0].FormatTok.WhiteSpaceLength > 0; 1479 if (SpacesBefore && !SpacesAfter) 1480 ++CountBoundToVariable; 1481 else if (!SpacesBefore && SpacesAfter) 1482 ++CountBoundToType; 1483 } 1484 1485 if (Tok->Type == TT_TemplateCloser && 1486 Tok->Parent->Type == TT_TemplateCloser && 1487 Tok->FormatTok.WhiteSpaceLength == 0) 1488 HasCpp03IncompatibleFormat = true; 1489 Tok = &Tok->Children[0]; 1490 } 1491 } 1492 if (Style.DerivePointerBinding) { 1493 if (CountBoundToType > CountBoundToVariable) 1494 Style.PointerBindsToType = true; 1495 else if (CountBoundToType < CountBoundToVariable) 1496 Style.PointerBindsToType = false; 1497 } 1498 if (Style.Standard == FormatStyle::LS_Auto) { 1499 Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11 1500 : FormatStyle::LS_Cpp03; 1501 } 1502 } 1503 1504 /// \brief Get the indent of \p Level from \p IndentForLevel. 1505 /// 1506 /// \p IndentForLevel must contain the indent for the level \c l 1507 /// at \p IndentForLevel[l], or a value < 0 if the indent for 1508 /// that level is unknown. 1509 unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) { 1510 if (IndentForLevel[Level] != -1) 1511 return IndentForLevel[Level]; 1512 if (Level == 0) 1513 return 0; 1514 return getIndent(IndentForLevel, Level - 1) + 2; 1515 } 1516 1517 /// \brief Get the offset of the line relatively to the level. 1518 /// 1519 /// For example, 'public:' labels in classes are offset by 1 or 2 1520 /// characters to the left from their level. 1521 int getIndentOffset(const AnnotatedToken &RootToken) { 1522 if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier()) 1523 return Style.AccessModifierOffset; 1524 return 0; 1525 } 1526 1527 /// \brief Tries to merge lines into one. 1528 /// 1529 /// This will change \c Line and \c AnnotatedLine to contain the merged line, 1530 /// if possible; note that \c I will be incremented when lines are merged. 1531 /// 1532 /// Returns whether the resulting \c Line can fit in a single line. 1533 void tryFitMultipleLinesInOne(unsigned Indent, 1534 std::vector<AnnotatedLine>::iterator &I, 1535 std::vector<AnnotatedLine>::iterator E) { 1536 // We can never merge stuff if there are trailing line comments. 1537 if (I->Last->Type == TT_LineComment) 1538 return; 1539 1540 unsigned Limit = Style.ColumnLimit - Indent; 1541 // If we already exceed the column limit, we set 'Limit' to 0. The different 1542 // tryMerge..() functions can then decide whether to still do merging. 1543 Limit = I->Last->TotalLength > Limit ? 0 : Limit - I->Last->TotalLength; 1544 1545 if (I + 1 == E || (I + 1)->Type == LT_Invalid) 1546 return; 1547 1548 if (I->Last->is(tok::l_brace)) { 1549 tryMergeSimpleBlock(I, E, Limit); 1550 } else if (I->First.is(tok::kw_if)) { 1551 tryMergeSimpleIf(I, E, Limit); 1552 } else if (I->InPPDirective && (I->First.FormatTok.HasUnescapedNewline || 1553 I->First.FormatTok.IsFirst)) { 1554 tryMergeSimplePPDirective(I, E, Limit); 1555 } 1556 return; 1557 } 1558 1559 void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I, 1560 std::vector<AnnotatedLine>::iterator E, 1561 unsigned Limit) { 1562 if (Limit == 0) 1563 return; 1564 AnnotatedLine &Line = *I; 1565 if (!(I + 1)->InPPDirective || (I + 1)->First.FormatTok.HasUnescapedNewline) 1566 return; 1567 if (I + 2 != E && (I + 2)->InPPDirective && 1568 !(I + 2)->First.FormatTok.HasUnescapedNewline) 1569 return; 1570 if (1 + (I + 1)->Last->TotalLength > Limit) 1571 return; 1572 join(Line, *(++I)); 1573 } 1574 1575 void tryMergeSimpleIf(std::vector<AnnotatedLine>::iterator &I, 1576 std::vector<AnnotatedLine>::iterator E, 1577 unsigned Limit) { 1578 if (Limit == 0) 1579 return; 1580 if (!Style.AllowShortIfStatementsOnASingleLine) 1581 return; 1582 if ((I + 1)->InPPDirective != I->InPPDirective || 1583 ((I + 1)->InPPDirective && 1584 (I + 1)->First.FormatTok.HasUnescapedNewline)) 1585 return; 1586 AnnotatedLine &Line = *I; 1587 if (Line.Last->isNot(tok::r_paren)) 1588 return; 1589 if (1 + (I + 1)->Last->TotalLength > Limit) 1590 return; 1591 if ((I + 1)->First.is(tok::kw_if) || (I + 1)->First.Type == TT_LineComment) 1592 return; 1593 // Only inline simple if's (no nested if or else). 1594 if (I + 2 != E && (I + 2)->First.is(tok::kw_else)) 1595 return; 1596 join(Line, *(++I)); 1597 } 1598 1599 void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I, 1600 std::vector<AnnotatedLine>::iterator E, 1601 unsigned Limit) { 1602 // First, check that the current line allows merging. This is the case if 1603 // we're not in a control flow statement and the last token is an opening 1604 // brace. 1605 AnnotatedLine &Line = *I; 1606 if (Line.First.isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace, 1607 tok::kw_else, tok::kw_try, tok::kw_catch, 1608 tok::kw_for, 1609 // This gets rid of all ObjC @ keywords and methods. 1610 tok::at, tok::minus, tok::plus)) 1611 return; 1612 1613 AnnotatedToken *Tok = &(I + 1)->First; 1614 if (Tok->Children.empty() && Tok->is(tok::r_brace) && 1615 !Tok->MustBreakBefore) { 1616 // We merge empty blocks even if the line exceeds the column limit. 1617 Tok->SpacesRequiredBefore = 0; 1618 Tok->CanBreakBefore = true; 1619 join(Line, *(I + 1)); 1620 I += 1; 1621 } else if (Limit != 0) { 1622 // Check that we still have three lines and they fit into the limit. 1623 if (I + 2 == E || (I + 2)->Type == LT_Invalid || 1624 !nextTwoLinesFitInto(I, Limit)) 1625 return; 1626 1627 // Second, check that the next line does not contain any braces - if it 1628 // does, readability declines when putting it into a single line. 1629 if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore) 1630 return; 1631 do { 1632 if (Tok->isOneOf(tok::l_brace, tok::r_brace)) 1633 return; 1634 Tok = Tok->Children.empty() ? NULL : &Tok->Children.back(); 1635 } while (Tok != NULL); 1636 1637 // Last, check that the third line contains a single closing brace. 1638 Tok = &(I + 2)->First; 1639 if (!Tok->Children.empty() || Tok->isNot(tok::r_brace) || 1640 Tok->MustBreakBefore) 1641 return; 1642 1643 join(Line, *(I + 1)); 1644 join(Line, *(I + 2)); 1645 I += 2; 1646 } 1647 } 1648 1649 bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I, 1650 unsigned Limit) { 1651 return 1 + (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <= 1652 Limit; 1653 } 1654 1655 void join(AnnotatedLine &A, const AnnotatedLine &B) { 1656 unsigned LengthA = A.Last->TotalLength + B.First.SpacesRequiredBefore; 1657 A.Last->Children.push_back(B.First); 1658 while (!A.Last->Children.empty()) { 1659 A.Last->Children[0].Parent = A.Last; 1660 A.Last->Children[0].TotalLength += LengthA; 1661 A.Last = &A.Last->Children[0]; 1662 } 1663 } 1664 1665 bool touchesRanges(const CharSourceRange &Range) { 1666 for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { 1667 if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), 1668 Ranges[i].getBegin()) && 1669 !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(), 1670 Range.getBegin())) 1671 return true; 1672 } 1673 return false; 1674 } 1675 1676 bool touchesLine(const AnnotatedLine &TheLine) { 1677 const FormatToken *First = &TheLine.First.FormatTok; 1678 const FormatToken *Last = &TheLine.Last->FormatTok; 1679 CharSourceRange LineRange = CharSourceRange::getTokenRange( 1680 First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset), 1681 Last->Tok.getLocation()); 1682 return touchesRanges(LineRange); 1683 } 1684 1685 bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) { 1686 const FormatToken *First = &TheLine.First.FormatTok; 1687 CharSourceRange LineRange = CharSourceRange::getCharRange( 1688 First->WhiteSpaceStart, 1689 First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset)); 1690 return touchesRanges(LineRange); 1691 } 1692 1693 virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) { 1694 AnnotatedLines.push_back(AnnotatedLine(TheLine)); 1695 } 1696 1697 /// \brief Add a new line and the required indent before the first Token 1698 /// of the \c UnwrappedLine if there was no structural parsing error. 1699 /// Returns the indent level of the \c UnwrappedLine. 1700 void formatFirstToken(const AnnotatedToken &RootToken, 1701 const AnnotatedToken *PreviousToken, unsigned Indent, 1702 bool InPPDirective, unsigned PreviousEndOfLineColumn) { 1703 const FormatToken &Tok = RootToken.FormatTok; 1704 1705 unsigned Newlines = 1706 std::min(Tok.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1); 1707 if (Newlines == 0 && !Tok.IsFirst) 1708 Newlines = 1; 1709 1710 if (!InPPDirective || Tok.HasUnescapedNewline) { 1711 // Insert extra new line before access specifiers. 1712 if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) && 1713 RootToken.isAccessSpecifier() && Tok.NewlinesBefore == 1) 1714 ++Newlines; 1715 1716 Whitespaces.replaceWhitespace(RootToken, Newlines, Indent, 0); 1717 } else { 1718 Whitespaces.replacePPWhitespace(RootToken, Newlines, Indent, 1719 PreviousEndOfLineColumn); 1720 } 1721 } 1722 1723 DiagnosticsEngine &Diag; 1724 FormatStyle Style; 1725 Lexer &Lex; 1726 SourceManager &SourceMgr; 1727 WhitespaceManager Whitespaces; 1728 std::vector<CharSourceRange> Ranges; 1729 std::vector<AnnotatedLine> AnnotatedLines; 1730 bool StructuralError; 1731}; 1732 1733tooling::Replacements 1734reformat(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr, 1735 std::vector<CharSourceRange> Ranges, DiagnosticConsumer *DiagClient) { 1736 IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions(); 1737 OwningPtr<DiagnosticConsumer> DiagPrinter; 1738 if (DiagClient == 0) { 1739 DiagPrinter.reset(new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts)); 1740 DiagPrinter->BeginSourceFile(Lex.getLangOpts(), Lex.getPP()); 1741 DiagClient = DiagPrinter.get(); 1742 } 1743 DiagnosticsEngine Diagnostics( 1744 IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()), &*DiagOpts, 1745 DiagClient, false); 1746 Diagnostics.setSourceManager(&SourceMgr); 1747 Formatter formatter(Diagnostics, Style, Lex, SourceMgr, Ranges); 1748 return formatter.format(); 1749} 1750 1751LangOptions getFormattingLangOpts() { 1752 LangOptions LangOpts; 1753 LangOpts.CPlusPlus = 1; 1754 LangOpts.CPlusPlus11 = 1; 1755 LangOpts.LineComment = 1; 1756 LangOpts.Bool = 1; 1757 LangOpts.ObjC1 = 1; 1758 LangOpts.ObjC2 = 1; 1759 return LangOpts; 1760} 1761 1762} // namespace format 1763} // namespace clang 1764