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

   1 //===--- WhitespaceManager.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 WhitespaceManager class.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "WhitespaceManager.h"
  16 #include "llvm/ADT/STLExtras.h"
  17
  18 namespace clang {
  19 namespace format {
  20
  21 bool WhitespaceManager::Change::IsBeforeInFile::
  22 operator()(const Change &C1, const Change &C2) const {
  23   return SourceMgr.isBeforeInTranslationUnit(
  24       C1.OriginalWhitespaceRange.getBegin(),
  25       C2.OriginalWhitespaceRange.getBegin());
  26 }
  27
  28 WhitespaceManager::Change::Change(const FormatToken &Tok,
  29                                   bool CreateReplacement,
  30                                   SourceRange OriginalWhitespaceRange,
  31                                   int Spaces, unsigned StartOfTokenColumn,
  32                                   unsigned NewlinesBefore,
  33                                   StringRef PreviousLinePostfix,
  34                                   StringRef CurrentLinePrefix,
  35                                   bool ContinuesPPDirective, bool IsInsideToken)
  36     : Tok(&Tok), CreateReplacement(CreateReplacement),
  37       OriginalWhitespaceRange(OriginalWhitespaceRange),
  38       StartOfTokenColumn(StartOfTokenColumn), NewlinesBefore(NewlinesBefore),
  39       PreviousLinePostfix(PreviousLinePostfix),
  40       CurrentLinePrefix(CurrentLinePrefix),
  41       ContinuesPPDirective(ContinuesPPDirective), Spaces(Spaces),
  42       IsInsideToken(IsInsideToken), IsTrailingComment(false), TokenLength(0),
  43       PreviousEndOfTokenColumn(0), EscapedNewlineColumn(0),
  44       StartOfBlockComment(nullptr), IndentationOffset(0) {}
  45
  46 void WhitespaceManager::replaceWhitespace(FormatToken &Tok, unsigned Newlines,
  47                                           unsigned Spaces,
  48                                           unsigned StartOfTokenColumn,
  49                                           bool InPPDirective) {
  50   if (Tok.Finalized)
  51     return;
  52   Tok.Decision = (Newlines > 0) ? FD_Break : FD_Continue;
  53   Changes.push_back(Change(Tok, /*CreateReplacement=*/true, Tok.WhitespaceRange,
  54                            Spaces, StartOfTokenColumn, Newlines, "", "",
  55                            InPPDirective && !Tok.IsFirst,
  56                            /*IsInsideToken=*/false));
  57 }
  58
  59 void WhitespaceManager::addUntouchableToken(const FormatToken &Tok,
  60                                             bool InPPDirective) {
  61   if (Tok.Finalized)
  62     return;
  63   Changes.push_back(Change(Tok, /*CreateReplacement=*/false,
  64                            Tok.WhitespaceRange, /*Spaces=*/0,
  65                            Tok.OriginalColumn, Tok.NewlinesBefore, "", "",
  66                            InPPDirective && !Tok.IsFirst,
  67                            /*IsInsideToken=*/false));
  68 }
  69
  70 void WhitespaceManager::replaceWhitespaceInToken(
  71     const FormatToken &Tok, unsigned Offset, unsigned ReplaceChars,
  72     StringRef PreviousPostfix, StringRef CurrentPrefix, bool InPPDirective,
  73     unsigned Newlines, int Spaces) {
  74   if (Tok.Finalized)
  75     return;
  76   SourceLocation Start = Tok.getStartOfNonWhitespace().getLocWithOffset(Offset);
  77   Changes.push_back(
  78       Change(Tok, /*CreateReplacement=*/true,
  79              SourceRange(Start, Start.getLocWithOffset(ReplaceChars)), Spaces,
  80              std::max(0, Spaces), Newlines, PreviousPostfix, CurrentPrefix,
  81              InPPDirective && !Tok.IsFirst, /*IsInsideToken=*/true));
  82 }
  83
  84 const tooling::Replacements &WhitespaceManager::generateReplacements() {
  85   if (Changes.empty())
  86     return Replaces;
  87
  88   std::sort(Changes.begin(), Changes.end(), Change::IsBeforeInFile(SourceMgr));
  89   calculateLineBreakInformation();
  90   alignConsecutiveDeclarations();
  91   alignConsecutiveAssignments();
  92   alignTrailingComments();
  93   alignEscapedNewlines();
  94   generateChanges();
  95
  96   return Replaces;
  97 }
  98
  99 void WhitespaceManager::calculateLineBreakInformation() {
 100   Changes[0].PreviousEndOfTokenColumn = 0;
 101   Change *LastOutsideTokenChange = &Changes[0];
 102   for (unsigned i = 1, e = Changes.size(); i != e; ++i) {
 103     SourceLocation OriginalWhitespaceStart =
 104         Changes[i].OriginalWhitespaceRange.getBegin();
 105     SourceLocation PreviousOriginalWhitespaceEnd =
 106         Changes[i - 1].OriginalWhitespaceRange.getEnd();
 107     unsigned OriginalWhitespaceStartOffset =
 108         SourceMgr.getFileOffset(OriginalWhitespaceStart);
 109     unsigned PreviousOriginalWhitespaceEndOffset =
 110         SourceMgr.getFileOffset(PreviousOriginalWhitespaceEnd);
 111     assert(PreviousOriginalWhitespaceEndOffset <=
 112            OriginalWhitespaceStartOffset);
 113     const char *const PreviousOriginalWhitespaceEndData =
 114         SourceMgr.getCharacterData(PreviousOriginalWhitespaceEnd);
 115     StringRef Text(PreviousOriginalWhitespaceEndData,
 116                    SourceMgr.getCharacterData(OriginalWhitespaceStart) -
 117                        PreviousOriginalWhitespaceEndData);
 118     // Usually consecutive changes would occur in consecutive tokens. This is
 119     // not the case however when analyzing some preprocessor runs of the
 120     // annotated lines. For example, in this code:
 121     //
 122     // #if A // line 1
 123     // int i = 1;
 124     // #else B // line 2
 125     // int i = 2;
 126     // #endif // line 3
 127     //
 128     // one of the runs will produce the sequence of lines marked with line 1, 2
 129     // and 3. So the two consecutive whitespace changes just before '// line 2'
 130     // and before '#endif // line 3' span multiple lines and tokens:
 131     //
 132     // #else B{change X}[// line 2
 133     // int i = 2;
 134     // ]{change Y}#endif // line 3
 135     //
 136     // For this reason, if the text between consecutive changes spans multiple
 137     // newlines, the token length must be adjusted to the end of the original
 138     // line of the token.
 139     auto NewlinePos = Text.find_first_of('\n');
 140     if (NewlinePos == StringRef::npos) {
 141       Changes[i - 1].TokenLength = OriginalWhitespaceStartOffset -
 142                                    PreviousOriginalWhitespaceEndOffset +
 143                                    Changes[i].PreviousLinePostfix.size() +
 144                                    Changes[i - 1].CurrentLinePrefix.size();
 145     } else {
 146       Changes[i - 1].TokenLength =
 147           NewlinePos + Changes[i - 1].CurrentLinePrefix.size();
 148     }
 149
 150     // If there are multiple changes in this token, sum up all the changes until
 151     // the end of the line.
 152     if (Changes[i - 1].IsInsideToken && Changes[i - 1].NewlinesBefore == 0)
 153       LastOutsideTokenChange->TokenLength +=
 154           Changes[i - 1].TokenLength + Changes[i - 1].Spaces;
 155     else
 156       LastOutsideTokenChange = &Changes[i - 1];
 157
 158     Changes[i].PreviousEndOfTokenColumn =
 159         Changes[i - 1].StartOfTokenColumn + Changes[i - 1].TokenLength;
 160
 161     Changes[i - 1].IsTrailingComment =
 162         (Changes[i].NewlinesBefore > 0 || Changes[i].Tok->is(tok::eof) ||
 163          (Changes[i].IsInsideToken && Changes[i].Tok->is(tok::comment))) &&
 164         Changes[i - 1].Tok->is(tok::comment) &&
 165         // FIXME: This is a dirty hack. The problem is that
 166         // BreakableLineCommentSection does comment reflow changes and here is
 167         // the aligning of trailing comments. Consider the case where we reflow
 168         // the second line up in this example:
 169         //
 170         // // line 1
 171         // // line 2
 172         //
 173         // That amounts to 2 changes by BreakableLineCommentSection:
 174         //  - the first, delimited by (), for the whitespace between the tokens,
 175         //  - and second, delimited by [], for the whitespace at the beginning
 176         //  of the second token:
 177         //
 178         // // line 1(
 179         // )[// ]line 2
 180         //
 181         // So in the end we have two changes like this:
 182         //
 183         // // line1()[ ]line 2
 184         //
 185         // Note that the OriginalWhitespaceStart of the second change is the
 186         // same as the PreviousOriginalWhitespaceEnd of the first change.
 187         // In this case, the below check ensures that the second change doesn't
 188         // get treated as a trailing comment change here, since this might
 189         // trigger additional whitespace to be wrongly inserted before "line 2"
 190         // by the comment aligner here.
 191         //
 192         // For a proper solution we need a mechanism to say to WhitespaceManager
 193         // that a particular change breaks the current sequence of trailing
 194         // comments.
 195         OriginalWhitespaceStart != PreviousOriginalWhitespaceEnd;
 196   }
 197   // FIXME: The last token is currently not always an eof token; in those
 198   // cases, setting TokenLength of the last token to 0 is wrong.
 199   Changes.back().TokenLength = 0;
 200   Changes.back().IsTrailingComment = Changes.back().Tok->is(tok::comment);
 201
 202   const WhitespaceManager::Change *LastBlockComment = nullptr;
 203   for (auto &Change : Changes) {
 204     // Reset the IsTrailingComment flag for changes inside of trailing comments
 205     // so they don't get realigned later. Comment line breaks however still need
 206     // to be aligned.
 207     if (Change.IsInsideToken && Change.NewlinesBefore == 0)
 208       Change.IsTrailingComment = false;
 209     Change.StartOfBlockComment = nullptr;
 210     Change.IndentationOffset = 0;
 211     if (Change.Tok->is(tok::comment)) {
 212       if (Change.Tok->is(TT_LineComment) || !Change.IsInsideToken)
 213         LastBlockComment = &Change;
 214       else {
 215         if ((Change.StartOfBlockComment = LastBlockComment))
 216           Change.IndentationOffset =
 217               Change.StartOfTokenColumn -
 218               Change.StartOfBlockComment->StartOfTokenColumn;
 219       }
 220     } else {
 221       LastBlockComment = nullptr;
 222     }
 223   }
 224 }
 225
 226 // Align a single sequence of tokens, see AlignTokens below.
 227 template <typename F>
 228 static void
 229 AlignTokenSequence(unsigned Start, unsigned End, unsigned Column, F &&Matches,
 230                    SmallVector<WhitespaceManager::Change, 16> &Changes) {
 231   bool FoundMatchOnLine = false;
 232   int Shift = 0;
 233
 234   // ScopeStack keeps track of the current scope depth. It contains indices of
 235   // the first token on each scope.
 236   // We only run the "Matches" function on tokens from the outer-most scope.
 237   // However, we do need to pay special attention to one class of tokens
 238   // that are not in the outer-most scope, and that is function parameters
 239   // which are split across multiple lines, as illustrated by this example:
 240   //   double a(int x);
 241   //   int    b(int  y,
 242   //          double z);
 243   // In the above example, we need to take special care to ensure that
 244   // 'double z' is indented along with it's owning function 'b'.
 245   SmallVector<unsigned, 16> ScopeStack;
 246
 247   for (unsigned i = Start; i != End; ++i) {
 248     if (ScopeStack.size() != 0 &&
 249         Changes[i].nestingAndIndentLevel() <
 250             Changes[ScopeStack.back()].nestingAndIndentLevel())
 251       ScopeStack.pop_back();
 252
 253     if (i != Start && Changes[i].nestingAndIndentLevel() >
 254                           Changes[i - 1].nestingAndIndentLevel())
 255       ScopeStack.push_back(i);
 256
 257     bool InsideNestedScope = ScopeStack.size() != 0;
 258
 259     if (Changes[i].NewlinesBefore > 0 && !InsideNestedScope) {
 260       Shift = 0;
 261       FoundMatchOnLine = false;
 262     }
 263
 264     // If this is the first matching token to be aligned, remember by how many
 265     // spaces it has to be shifted, so the rest of the changes on the line are
 266     // shifted by the same amount
 267     if (!FoundMatchOnLine && !InsideNestedScope && Matches(Changes[i])) {
 268       FoundMatchOnLine = true;
 269       Shift = Column - Changes[i].StartOfTokenColumn;
 270       Changes[i].Spaces += Shift;
 271     }
 272
 273     // This is for function parameters that are split across multiple lines,
 274     // as mentioned in the ScopeStack comment.
 275     if (InsideNestedScope && Changes[i].NewlinesBefore > 0) {
 276       unsigned ScopeStart = ScopeStack.back();
 277       if (Changes[ScopeStart - 1].Tok->is(TT_FunctionDeclarationName) ||
 278           (ScopeStart > Start + 1 &&
 279            Changes[ScopeStart - 2].Tok->is(TT_FunctionDeclarationName)))
 280         Changes[i].Spaces += Shift;
 281     }
 282
 283     assert(Shift >= 0);
 284     Changes[i].StartOfTokenColumn += Shift;
 285     if (i + 1 != Changes.size())
 286       Changes[i + 1].PreviousEndOfTokenColumn += Shift;
 287   }
 288 }
 289
 290 // Walk through a subset of the changes, starting at StartAt, and find
 291 // sequences of matching tokens to align. To do so, keep track of the lines and
 292 // whether or not a matching token was found on a line. If a matching token is
 293 // found, extend the current sequence. If the current line cannot be part of a
 294 // sequence, e.g. because there is an empty line before it or it contains only
 295 // non-matching tokens, finalize the previous sequence.
 296 // The value returned is the token on which we stopped, either because we
 297 // exhausted all items inside Changes, or because we hit a scope level higher
 298 // than our initial scope.
 299 // This function is recursive. Each invocation processes only the scope level
 300 // equal to the initial level, which is the level of Changes[StartAt].
 301 // If we encounter a scope level greater than the initial level, then we call
 302 // ourselves recursively, thereby avoiding the pollution of the current state
 303 // with the alignment requirements of the nested sub-level. This recursive
 304 // behavior is necessary for aligning function prototypes that have one or more
 305 // arguments.
 306 // If this function encounters a scope level less than the initial level,
 307 // it returns the current position.
 308 // There is a non-obvious subtlety in the recursive behavior: Even though we
 309 // defer processing of nested levels to recursive invocations of this
 310 // function, when it comes time to align a sequence of tokens, we run the
 311 // alignment on the entire sequence, including the nested levels.
 312 // When doing so, most of the nested tokens are skipped, because their
 313 // alignment was already handled by the recursive invocations of this function.
 314 // However, the special exception is that we do NOT skip function parameters
 315 // that are split across multiple lines. See the test case in FormatTest.cpp
 316 // that mentions "split function parameter alignment" for an example of this.
 317 template <typename F>
 318 static unsigned AlignTokens(const FormatStyle &Style, F &&Matches,
 319                             SmallVector<WhitespaceManager::Change, 16> &Changes,
 320                             unsigned StartAt) {
 321   unsigned MinColumn = 0;
 322   unsigned MaxColumn = UINT_MAX;
 323
 324   // Line number of the start and the end of the current token sequence.
 325   unsigned StartOfSequence = 0;
 326   unsigned EndOfSequence = 0;
 327
 328   // Measure the scope level (i.e. depth of (), [], {}) of the first token, and
 329   // abort when we hit any token in a higher scope than the starting one.
 330   auto NestingAndIndentLevel = StartAt < Changes.size()
 331                                    ? Changes[StartAt].nestingAndIndentLevel()
 332                                    : std::pair<unsigned, unsigned>(0, 0);
 333
 334   // Keep track of the number of commas before the matching tokens, we will only
 335   // align a sequence of matching tokens if they are preceded by the same number
 336   // of commas.
 337   unsigned CommasBeforeLastMatch = 0;
 338   unsigned CommasBeforeMatch = 0;
 339
 340   // Whether a matching token has been found on the current line.
 341   bool FoundMatchOnLine = false;
 342
 343   // Aligns a sequence of matching tokens, on the MinColumn column.
 344   //
 345   // Sequences start from the first matching token to align, and end at the
 346   // first token of the first line that doesn't need to be aligned.
 347   //
 348   // We need to adjust the StartOfTokenColumn of each Change that is on a line
 349   // containing any matching token to be aligned and located after such token.
 350   auto AlignCurrentSequence = [&] {
 351     if (StartOfSequence > 0 && StartOfSequence < EndOfSequence)
 352       AlignTokenSequence(StartOfSequence, EndOfSequence, MinColumn, Matches,
 353                          Changes);
 354     MinColumn = 0;
 355     MaxColumn = UINT_MAX;
 356     StartOfSequence = 0;
 357     EndOfSequence = 0;
 358   };
 359
 360   unsigned i = StartAt;
 361   for (unsigned e = Changes.size(); i != e; ++i) {
 362     if (Changes[i].nestingAndIndentLevel() < NestingAndIndentLevel)
 363       break;
 364
 365     if (Changes[i].NewlinesBefore != 0) {
 366       CommasBeforeMatch = 0;
 367       EndOfSequence = i;
 368       // If there is a blank line, or if the last line didn't contain any
 369       // matching token, the sequence ends here.
 370       if (Changes[i].NewlinesBefore > 1 || !FoundMatchOnLine)
 371         AlignCurrentSequence();
 372
 373       FoundMatchOnLine = false;
 374     }
 375
 376     if (Changes[i].Tok->is(tok::comma)) {
 377       ++CommasBeforeMatch;
 378     } else if (Changes[i].nestingAndIndentLevel() > NestingAndIndentLevel) {
 379       // Call AlignTokens recursively, skipping over this scope block.
 380       unsigned StoppedAt = AlignTokens(Style, Matches, Changes, i);
 381       i = StoppedAt - 1;
 382       continue;
 383     }
 384
 385     if (!Matches(Changes[i]))
 386       continue;
 387
 388     // If there is more than one matching token per line, or if the number of
 389     // preceding commas, do not match anymore, end the sequence.
 390     if (FoundMatchOnLine || CommasBeforeMatch != CommasBeforeLastMatch)
 391       AlignCurrentSequence();
 392
 393     CommasBeforeLastMatch = CommasBeforeMatch;
 394     FoundMatchOnLine = true;
 395
 396     if (StartOfSequence == 0)
 397       StartOfSequence = i;
 398
 399     unsigned ChangeMinColumn = Changes[i].StartOfTokenColumn;
 400     int LineLengthAfter = -Changes[i].Spaces;
 401     for (unsigned j = i; j != e && Changes[j].NewlinesBefore == 0; ++j)
 402       LineLengthAfter += Changes[j].Spaces + Changes[j].TokenLength;
 403     unsigned ChangeMaxColumn = Style.ColumnLimit - LineLengthAfter;
 404
 405     // If we are restricted by the maximum column width, end the sequence.
 406     if (ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn ||
 407         CommasBeforeLastMatch != CommasBeforeMatch) {
 408       AlignCurrentSequence();
 409       StartOfSequence = i;
 410     }
 411
 412     MinColumn = std::max(MinColumn, ChangeMinColumn);
 413     MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
 414   }
 415
 416   EndOfSequence = i;
 417   AlignCurrentSequence();
 418   return i;
 419 }
 420
 421 void WhitespaceManager::alignConsecutiveAssignments() {
 422   if (!Style.AlignConsecutiveAssignments)
 423     return;
 424
 425   AlignTokens(Style,
 426               [&](const Change &C) {
 427                 // Do not align on equal signs that are first on a line.
 428                 if (C.NewlinesBefore > 0)
 429                   return false;
 430
 431                 // Do not align on equal signs that are last on a line.
 432                 if (&C != &Changes.back() && (&C + 1)->NewlinesBefore > 0)
 433                   return false;
 434
 435                 return C.Tok->is(tok::equal);
 436               },
 437               Changes, /*StartAt=*/0);
 438 }
 439
 440 void WhitespaceManager::alignConsecutiveDeclarations() {
 441   if (!Style.AlignConsecutiveDeclarations)
 442     return;
 443
 444   // FIXME: Currently we don't handle properly the PointerAlignment: Right
 445   // The * and & are not aligned and are left dangling. Something has to be done
 446   // about it, but it raises the question of alignment of code like:
 447   //   const char* const* v1;
 448   //   float const* v2;
 449   //   SomeVeryLongType const& v3;
 450   AlignTokens(Style,
 451               [](Change const &C) {
 452                 // tok::kw_operator is necessary for aligning operator overload
 453                 // definitions.
 454                 return C.Tok->is(TT_StartOfName) ||
 455                        C.Tok->is(TT_FunctionDeclarationName) ||
 456                        C.Tok->is(tok::kw_operator);
 457               },
 458               Changes, /*StartAt=*/0);
 459 }
 460
 461 void WhitespaceManager::alignTrailingComments() {
 462   unsigned MinColumn = 0;
 463   unsigned MaxColumn = UINT_MAX;
 464   unsigned StartOfSequence = 0;
 465   bool BreakBeforeNext = false;
 466   unsigned Newlines = 0;
 467   for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
 468     if (Changes[i].StartOfBlockComment)
 469       continue;
 470     Newlines += Changes[i].NewlinesBefore;
 471     if (!Changes[i].IsTrailingComment)
 472       continue;
 473
 474     unsigned ChangeMinColumn = Changes[i].StartOfTokenColumn;
 475     unsigned ChangeMaxColumn = Style.ColumnLimit >= Changes[i].TokenLength
 476                                    ? Style.ColumnLimit - Changes[i].TokenLength
 477                                    : ChangeMinColumn;
 478
 479     // If we don't create a replacement for this change, we have to consider
 480     // it to be immovable.
 481     if (!Changes[i].CreateReplacement)
 482       ChangeMaxColumn = ChangeMinColumn;
 483
 484     if (i + 1 != e && Changes[i + 1].ContinuesPPDirective)
 485       ChangeMaxColumn -= 2;
 486     // If this comment follows an } in column 0, it probably documents the
 487     // closing of a namespace and we don't want to align it.
 488     bool FollowsRBraceInColumn0 = i > 0 && Changes[i].NewlinesBefore == 0 &&
 489                                   Changes[i - 1].Tok->is(tok::r_brace) &&
 490                                   Changes[i - 1].StartOfTokenColumn == 0;
 491     bool WasAlignedWithStartOfNextLine = false;
 492     if (Changes[i].NewlinesBefore == 1) { // A comment on its own line.
 493       unsigned CommentColumn = SourceMgr.getSpellingColumnNumber(
 494           Changes[i].OriginalWhitespaceRange.getEnd());
 495       for (unsigned j = i + 1; j != e; ++j) {
 496         if (Changes[j].Tok->is(tok::comment))
 497           continue;
 498
 499         unsigned NextColumn = SourceMgr.getSpellingColumnNumber(
 500             Changes[j].OriginalWhitespaceRange.getEnd());
 501         // The start of the next token was previously aligned with the
 502         // start of this comment.
 503         WasAlignedWithStartOfNextLine =
 504             CommentColumn == NextColumn ||
 505             CommentColumn == NextColumn + Style.IndentWidth;
 506         break;
 507       }
 508     }
 509     if (!Style.AlignTrailingComments || FollowsRBraceInColumn0) {
 510       alignTrailingComments(StartOfSequence, i, MinColumn);
 511       MinColumn = ChangeMinColumn;
 512       MaxColumn = ChangeMinColumn;
 513       StartOfSequence = i;
 514     } else if (BreakBeforeNext || Newlines > 1 ||
 515                (ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn) ||
 516                // Break the comment sequence if the previous line did not end
 517                // in a trailing comment.
 518                (Changes[i].NewlinesBefore == 1 && i > 0 &&
 519                 !Changes[i - 1].IsTrailingComment) ||
 520                WasAlignedWithStartOfNextLine) {
 521       alignTrailingComments(StartOfSequence, i, MinColumn);
 522       MinColumn = ChangeMinColumn;
 523       MaxColumn = ChangeMaxColumn;
 524       StartOfSequence = i;
 525     } else {
 526       MinColumn = std::max(MinColumn, ChangeMinColumn);
 527       MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
 528     }
 529     BreakBeforeNext =
 530         (i == 0) || (Changes[i].NewlinesBefore > 1) ||
 531         // Never start a sequence with a comment at the beginning of
 532         // the line.
 533         (Changes[i].NewlinesBefore == 1 && StartOfSequence == i);
 534     Newlines = 0;
 535   }
 536   alignTrailingComments(StartOfSequence, Changes.size(), MinColumn);
 537 }
 538
 539 void WhitespaceManager::alignTrailingComments(unsigned Start, unsigned End,
 540                                               unsigned Column) {
 541   for (unsigned i = Start; i != End; ++i) {
 542     int Shift = 0;
 543     if (Changes[i].IsTrailingComment) {
 544       Shift = Column - Changes[i].StartOfTokenColumn;
 545     }
 546     if (Changes[i].StartOfBlockComment) {
 547       Shift = Changes[i].IndentationOffset +
 548               Changes[i].StartOfBlockComment->StartOfTokenColumn -
 549               Changes[i].StartOfTokenColumn;
 550     }
 551     assert(Shift >= 0);
 552     Changes[i].Spaces += Shift;
 553     if (i + 1 != Changes.size())
 554       Changes[i + 1].PreviousEndOfTokenColumn += Shift;
 555     Changes[i].StartOfTokenColumn += Shift;
 556   }
 557 }
 558
 559 void WhitespaceManager::alignEscapedNewlines() {
 560   if (Style.AlignEscapedNewlines == FormatStyle::ENAS_DontAlign)
 561     return;
 562
 563   bool AlignLeft = Style.AlignEscapedNewlines == FormatStyle::ENAS_Left;
 564   unsigned MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
 565   unsigned StartOfMacro = 0;
 566   for (unsigned i = 1, e = Changes.size(); i < e; ++i) {
 567     Change &C = Changes[i];
 568     if (C.NewlinesBefore > 0) {
 569       if (C.ContinuesPPDirective) {
 570         MaxEndOfLine = std::max(C.PreviousEndOfTokenColumn + 2, MaxEndOfLine);
 571       } else {
 572         alignEscapedNewlines(StartOfMacro + 1, i, MaxEndOfLine);
 573         MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
 574         StartOfMacro = i;
 575       }
 576     }
 577   }
 578   alignEscapedNewlines(StartOfMacro + 1, Changes.size(), MaxEndOfLine);
 579 }
 580
 581 void WhitespaceManager::alignEscapedNewlines(unsigned Start, unsigned End,
 582                                              unsigned Column) {
 583   for (unsigned i = Start; i < End; ++i) {
 584     Change &C = Changes[i];
 585     if (C.NewlinesBefore > 0) {
 586       assert(C.ContinuesPPDirective);
 587       if (C.PreviousEndOfTokenColumn + 1 > Column)
 588         C.EscapedNewlineColumn = 0;
 589       else
 590         C.EscapedNewlineColumn = Column;
 591     }
 592   }
 593 }
 594
 595 void WhitespaceManager::generateChanges() {
 596   for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
 597     const Change &C = Changes[i];
 598     if (i > 0) {
 599       assert(Changes[i - 1].OriginalWhitespaceRange.getBegin() !=
 600                  C.OriginalWhitespaceRange.getBegin() &&
 601              "Generating two replacements for the same location");
 602     }
 603     if (C.CreateReplacement) {
 604       std::string ReplacementText = C.PreviousLinePostfix;
 605       if (C.ContinuesPPDirective)
 606         appendNewlineText(ReplacementText, C.NewlinesBefore,
 607                           C.PreviousEndOfTokenColumn, C.EscapedNewlineColumn);
 608       else
 609         appendNewlineText(ReplacementText, C.NewlinesBefore);
 610       appendIndentText(ReplacementText, C.Tok->IndentLevel,
 611                        std::max(0, C.Spaces),
 612                        C.StartOfTokenColumn - std::max(0, C.Spaces));
 613       ReplacementText.append(C.CurrentLinePrefix);
 614       storeReplacement(C.OriginalWhitespaceRange, ReplacementText);
 615     }
 616   }
 617 }
 618
 619 void WhitespaceManager::storeReplacement(SourceRange Range,
 620                                          StringRef Text) {
 621   unsigned WhitespaceLength = SourceMgr.getFileOffset(Range.getEnd()) -
 622                               SourceMgr.getFileOffset(Range.getBegin());
 623   // Don't create a replacement, if it does not change anything.
 624   if (StringRef(SourceMgr.getCharacterData(Range.getBegin()),
 625                 WhitespaceLength) == Text)
 626     return;
 627   auto Err = Replaces.add(tooling::Replacement(
 628       SourceMgr, CharSourceRange::getCharRange(Range), Text));
 629   // FIXME: better error handling. For now, just print an error message in the
 630   // release version.
 631   if (Err) {
 632     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
 633     assert(false);
 634   }
 635 }
 636
 637 void WhitespaceManager::appendNewlineText(std::string &Text,
 638                                           unsigned Newlines) {
 639   for (unsigned i = 0; i < Newlines; ++i)
 640     Text.append(UseCRLF ? "\r\n" : "\n");
 641 }
 642
 643 void WhitespaceManager::appendNewlineText(std::string &Text, unsigned Newlines,
 644                                           unsigned PreviousEndOfTokenColumn,
 645                                           unsigned EscapedNewlineColumn) {
 646   if (Newlines > 0) {
 647     unsigned Offset =
 648         std::min<int>(EscapedNewlineColumn - 2, PreviousEndOfTokenColumn);
 649     for (unsigned i = 0; i < Newlines; ++i) {
 650       Text.append(EscapedNewlineColumn - Offset - 1, ' ');
 651       Text.append(UseCRLF ? "\\\r\n" : "\\\n");
 652       Offset = 0;
 653     }
 654   }
 655 }
 656
 657 void WhitespaceManager::appendIndentText(std::string &Text,
 658                                          unsigned IndentLevel, unsigned Spaces,
 659                                          unsigned WhitespaceStartColumn) {
 660   switch (Style.UseTab) {
 661   case FormatStyle::UT_Never:
 662     Text.append(Spaces, ' ');
 663     break;
 664   case FormatStyle::UT_Always: {
 665     unsigned FirstTabWidth =
 666         Style.TabWidth - WhitespaceStartColumn % Style.TabWidth;
 667     // Indent with tabs only when there's at least one full tab.
 668     if (FirstTabWidth + Style.TabWidth <= Spaces) {
 669       Spaces -= FirstTabWidth;
 670       Text.append("\t");
 671     }
 672     Text.append(Spaces / Style.TabWidth, '\t');
 673     Text.append(Spaces % Style.TabWidth, ' ');
 674     break;
 675   }
 676   case FormatStyle::UT_ForIndentation:
 677     if (WhitespaceStartColumn == 0) {
 678       unsigned Indentation = IndentLevel * Style.IndentWidth;
 679       // This happens, e.g. when a line in a block comment is indented less than
 680       // the first one.
 681       if (Indentation > Spaces)
 682         Indentation = Spaces;
 683       unsigned Tabs = Indentation / Style.TabWidth;
 684       Text.append(Tabs, '\t');
 685       Spaces -= Tabs * Style.TabWidth;
 686     }
 687     Text.append(Spaces, ' ');
 688     break;
 689   case FormatStyle::UT_ForContinuationAndIndentation:
 690     if (WhitespaceStartColumn == 0) {
 691       unsigned Tabs = Spaces / Style.TabWidth;
 692       Text.append(Tabs, '\t');
 693       Spaces -= Tabs * Style.TabWidth;
 694     }
 695     Text.append(Spaces, ' ');
 696     break;
 697   }
 698 }
 699
 700 } // namespace format
 701 } // namespace clang