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