1 //===--- WhitespaceManager.cpp - Format C++ code --------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements WhitespaceManager class.
11 ///
12 //===----------------------------------------------------------------------===//
13
14 #include "WhitespaceManager.h"
15 #include "llvm/ADT/STLExtras.h"
16
17 namespace clang {
18 namespace format {
19
operator ()(const Change & C1,const Change & C2) const20 bool WhitespaceManager::Change::IsBeforeInFile::operator()(
21 const Change &C1, const Change &C2) const {
22 return SourceMgr.isBeforeInTranslationUnit(
23 C1.OriginalWhitespaceRange.getBegin(),
24 C2.OriginalWhitespaceRange.getBegin());
25 }
26
Change(const FormatToken & Tok,bool CreateReplacement,SourceRange OriginalWhitespaceRange,int Spaces,unsigned StartOfTokenColumn,unsigned NewlinesBefore,StringRef PreviousLinePostfix,StringRef CurrentLinePrefix,bool IsAligned,bool ContinuesPPDirective,bool IsInsideToken)27 WhitespaceManager::Change::Change(const FormatToken &Tok,
28 bool CreateReplacement,
29 SourceRange OriginalWhitespaceRange,
30 int Spaces, unsigned StartOfTokenColumn,
31 unsigned NewlinesBefore,
32 StringRef PreviousLinePostfix,
33 StringRef CurrentLinePrefix, bool IsAligned,
34 bool ContinuesPPDirective, bool IsInsideToken)
35 : Tok(&Tok), CreateReplacement(CreateReplacement),
36 OriginalWhitespaceRange(OriginalWhitespaceRange),
37 StartOfTokenColumn(StartOfTokenColumn), NewlinesBefore(NewlinesBefore),
38 PreviousLinePostfix(PreviousLinePostfix),
39 CurrentLinePrefix(CurrentLinePrefix), IsAligned(IsAligned),
40 ContinuesPPDirective(ContinuesPPDirective), Spaces(Spaces),
41 IsInsideToken(IsInsideToken), IsTrailingComment(false), TokenLength(0),
42 PreviousEndOfTokenColumn(0), EscapedNewlineColumn(0),
43 StartOfBlockComment(nullptr), IndentationOffset(0), ConditionalsLevel(0) {
44 }
45
replaceWhitespace(FormatToken & Tok,unsigned Newlines,unsigned Spaces,unsigned StartOfTokenColumn,bool IsAligned,bool InPPDirective)46 void WhitespaceManager::replaceWhitespace(FormatToken &Tok, unsigned Newlines,
47 unsigned Spaces,
48 unsigned StartOfTokenColumn,
49 bool IsAligned, bool InPPDirective) {
50 if (Tok.Finalized)
51 return;
52 Tok.setDecision((Newlines > 0) ? FD_Break : FD_Continue);
53 Changes.push_back(Change(Tok, /*CreateReplacement=*/true, Tok.WhitespaceRange,
54 Spaces, StartOfTokenColumn, Newlines, "", "",
55 IsAligned, InPPDirective && !Tok.IsFirst,
56 /*IsInsideToken=*/false));
57 }
58
addUntouchableToken(const FormatToken & Tok,bool InPPDirective)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 /*IsAligned=*/false, InPPDirective && !Tok.IsFirst,
67 /*IsInsideToken=*/false));
68 }
69
70 llvm::Error
addReplacement(const tooling::Replacement & Replacement)71 WhitespaceManager::addReplacement(const tooling::Replacement &Replacement) {
72 return Replaces.add(Replacement);
73 }
74
replaceWhitespaceInToken(const FormatToken & Tok,unsigned Offset,unsigned ReplaceChars,StringRef PreviousPostfix,StringRef CurrentPrefix,bool InPPDirective,unsigned Newlines,int Spaces)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 /*IsAligned=*/true, InPPDirective && !Tok.IsFirst,
87 /*IsInsideToken=*/true));
88 }
89
generateReplacements()90 const tooling::Replacements &WhitespaceManager::generateReplacements() {
91 if (Changes.empty())
92 return Replaces;
93
94 llvm::sort(Changes, Change::IsBeforeInFile(SourceMgr));
95 calculateLineBreakInformation();
96 alignConsecutiveMacros();
97 alignConsecutiveDeclarations();
98 alignConsecutiveBitFields();
99 alignConsecutiveAssignments();
100 alignChainedConditionals();
101 alignTrailingComments();
102 alignEscapedNewlines();
103 generateChanges();
104
105 return Replaces;
106 }
107
calculateLineBreakInformation()108 void WhitespaceManager::calculateLineBreakInformation() {
109 Changes[0].PreviousEndOfTokenColumn = 0;
110 Change *LastOutsideTokenChange = &Changes[0];
111 for (unsigned i = 1, e = Changes.size(); i != e; ++i) {
112 SourceLocation OriginalWhitespaceStart =
113 Changes[i].OriginalWhitespaceRange.getBegin();
114 SourceLocation PreviousOriginalWhitespaceEnd =
115 Changes[i - 1].OriginalWhitespaceRange.getEnd();
116 unsigned OriginalWhitespaceStartOffset =
117 SourceMgr.getFileOffset(OriginalWhitespaceStart);
118 unsigned PreviousOriginalWhitespaceEndOffset =
119 SourceMgr.getFileOffset(PreviousOriginalWhitespaceEnd);
120 assert(PreviousOriginalWhitespaceEndOffset <=
121 OriginalWhitespaceStartOffset);
122 const char *const PreviousOriginalWhitespaceEndData =
123 SourceMgr.getCharacterData(PreviousOriginalWhitespaceEnd);
124 StringRef Text(PreviousOriginalWhitespaceEndData,
125 SourceMgr.getCharacterData(OriginalWhitespaceStart) -
126 PreviousOriginalWhitespaceEndData);
127 // Usually consecutive changes would occur in consecutive tokens. This is
128 // not the case however when analyzing some preprocessor runs of the
129 // annotated lines. For example, in this code:
130 //
131 // #if A // line 1
132 // int i = 1;
133 // #else B // line 2
134 // int i = 2;
135 // #endif // line 3
136 //
137 // one of the runs will produce the sequence of lines marked with line 1, 2
138 // and 3. So the two consecutive whitespace changes just before '// line 2'
139 // and before '#endif // line 3' span multiple lines and tokens:
140 //
141 // #else B{change X}[// line 2
142 // int i = 2;
143 // ]{change Y}#endif // line 3
144 //
145 // For this reason, if the text between consecutive changes spans multiple
146 // newlines, the token length must be adjusted to the end of the original
147 // line of the token.
148 auto NewlinePos = Text.find_first_of('\n');
149 if (NewlinePos == StringRef::npos) {
150 Changes[i - 1].TokenLength = OriginalWhitespaceStartOffset -
151 PreviousOriginalWhitespaceEndOffset +
152 Changes[i].PreviousLinePostfix.size() +
153 Changes[i - 1].CurrentLinePrefix.size();
154 } else {
155 Changes[i - 1].TokenLength =
156 NewlinePos + Changes[i - 1].CurrentLinePrefix.size();
157 }
158
159 // If there are multiple changes in this token, sum up all the changes until
160 // the end of the line.
161 if (Changes[i - 1].IsInsideToken && Changes[i - 1].NewlinesBefore == 0)
162 LastOutsideTokenChange->TokenLength +=
163 Changes[i - 1].TokenLength + Changes[i - 1].Spaces;
164 else
165 LastOutsideTokenChange = &Changes[i - 1];
166
167 Changes[i].PreviousEndOfTokenColumn =
168 Changes[i - 1].StartOfTokenColumn + Changes[i - 1].TokenLength;
169
170 Changes[i - 1].IsTrailingComment =
171 (Changes[i].NewlinesBefore > 0 || Changes[i].Tok->is(tok::eof) ||
172 (Changes[i].IsInsideToken && Changes[i].Tok->is(tok::comment))) &&
173 Changes[i - 1].Tok->is(tok::comment) &&
174 // FIXME: This is a dirty hack. The problem is that
175 // BreakableLineCommentSection does comment reflow changes and here is
176 // the aligning of trailing comments. Consider the case where we reflow
177 // the second line up in this example:
178 //
179 // // line 1
180 // // line 2
181 //
182 // That amounts to 2 changes by BreakableLineCommentSection:
183 // - the first, delimited by (), for the whitespace between the tokens,
184 // - and second, delimited by [], for the whitespace at the beginning
185 // of the second token:
186 //
187 // // line 1(
188 // )[// ]line 2
189 //
190 // So in the end we have two changes like this:
191 //
192 // // line1()[ ]line 2
193 //
194 // Note that the OriginalWhitespaceStart of the second change is the
195 // same as the PreviousOriginalWhitespaceEnd of the first change.
196 // In this case, the below check ensures that the second change doesn't
197 // get treated as a trailing comment change here, since this might
198 // trigger additional whitespace to be wrongly inserted before "line 2"
199 // by the comment aligner here.
200 //
201 // For a proper solution we need a mechanism to say to WhitespaceManager
202 // that a particular change breaks the current sequence of trailing
203 // comments.
204 OriginalWhitespaceStart != PreviousOriginalWhitespaceEnd;
205 }
206 // FIXME: The last token is currently not always an eof token; in those
207 // cases, setting TokenLength of the last token to 0 is wrong.
208 Changes.back().TokenLength = 0;
209 Changes.back().IsTrailingComment = Changes.back().Tok->is(tok::comment);
210
211 const WhitespaceManager::Change *LastBlockComment = nullptr;
212 for (auto &Change : Changes) {
213 // Reset the IsTrailingComment flag for changes inside of trailing comments
214 // so they don't get realigned later. Comment line breaks however still need
215 // to be aligned.
216 if (Change.IsInsideToken && Change.NewlinesBefore == 0)
217 Change.IsTrailingComment = false;
218 Change.StartOfBlockComment = nullptr;
219 Change.IndentationOffset = 0;
220 if (Change.Tok->is(tok::comment)) {
221 if (Change.Tok->is(TT_LineComment) || !Change.IsInsideToken)
222 LastBlockComment = &Change;
223 else {
224 if ((Change.StartOfBlockComment = LastBlockComment))
225 Change.IndentationOffset =
226 Change.StartOfTokenColumn -
227 Change.StartOfBlockComment->StartOfTokenColumn;
228 }
229 } else {
230 LastBlockComment = nullptr;
231 }
232 }
233
234 // Compute conditional nesting level
235 // Level is increased for each conditional, unless this conditional continues
236 // a chain of conditional, i.e. starts immediately after the colon of another
237 // conditional.
238 SmallVector<bool, 16> ScopeStack;
239 int ConditionalsLevel = 0;
240 for (auto &Change : Changes) {
241 for (unsigned i = 0, e = Change.Tok->FakeLParens.size(); i != e; ++i) {
242 bool isNestedConditional =
243 Change.Tok->FakeLParens[e - 1 - i] == prec::Conditional &&
244 !(i == 0 && Change.Tok->Previous &&
245 Change.Tok->Previous->is(TT_ConditionalExpr) &&
246 Change.Tok->Previous->is(tok::colon));
247 if (isNestedConditional)
248 ++ConditionalsLevel;
249 ScopeStack.push_back(isNestedConditional);
250 }
251
252 Change.ConditionalsLevel = ConditionalsLevel;
253
254 for (unsigned i = Change.Tok->FakeRParens; i > 0 && ScopeStack.size();
255 --i) {
256 if (ScopeStack.pop_back_val())
257 --ConditionalsLevel;
258 }
259 }
260 }
261
262 // Align a single sequence of tokens, see AlignTokens below.
263 template <typename F>
264 static void
AlignTokenSequence(unsigned Start,unsigned End,unsigned Column,F && Matches,SmallVector<WhitespaceManager::Change,16> & Changes)265 AlignTokenSequence(unsigned Start, unsigned End, unsigned Column, F &&Matches,
266 SmallVector<WhitespaceManager::Change, 16> &Changes) {
267 bool FoundMatchOnLine = false;
268 int Shift = 0;
269
270 // ScopeStack keeps track of the current scope depth. It contains indices of
271 // the first token on each scope.
272 // We only run the "Matches" function on tokens from the outer-most scope.
273 // However, we do need to pay special attention to one class of tokens
274 // that are not in the outer-most scope, and that is function parameters
275 // which are split across multiple lines, as illustrated by this example:
276 // double a(int x);
277 // int b(int y,
278 // double z);
279 // In the above example, we need to take special care to ensure that
280 // 'double z' is indented along with it's owning function 'b'.
281 // The same holds for calling a function:
282 // double a = foo(x);
283 // int b = bar(foo(y),
284 // foor(z));
285 // Similar for broken string literals:
286 // double x = 3.14;
287 // auto s = "Hello"
288 // "World";
289 // Special handling is required for 'nested' ternary operators.
290 SmallVector<unsigned, 16> ScopeStack;
291
292 for (unsigned i = Start; i != End; ++i) {
293 if (ScopeStack.size() != 0 &&
294 Changes[i].indentAndNestingLevel() <
295 Changes[ScopeStack.back()].indentAndNestingLevel())
296 ScopeStack.pop_back();
297
298 // Compare current token to previous non-comment token to ensure whether
299 // it is in a deeper scope or not.
300 unsigned PreviousNonComment = i - 1;
301 while (PreviousNonComment > Start &&
302 Changes[PreviousNonComment].Tok->is(tok::comment))
303 PreviousNonComment--;
304 if (i != Start && Changes[i].indentAndNestingLevel() >
305 Changes[PreviousNonComment].indentAndNestingLevel())
306 ScopeStack.push_back(i);
307
308 bool InsideNestedScope = ScopeStack.size() != 0;
309 bool ContinuedStringLiteral = i > Start &&
310 Changes[i].Tok->is(tok::string_literal) &&
311 Changes[i - 1].Tok->is(tok::string_literal);
312 bool SkipMatchCheck = InsideNestedScope || ContinuedStringLiteral;
313
314 if (Changes[i].NewlinesBefore > 0 && !SkipMatchCheck) {
315 Shift = 0;
316 FoundMatchOnLine = false;
317 }
318
319 // If this is the first matching token to be aligned, remember by how many
320 // spaces it has to be shifted, so the rest of the changes on the line are
321 // shifted by the same amount
322 if (!FoundMatchOnLine && !SkipMatchCheck && Matches(Changes[i])) {
323 FoundMatchOnLine = true;
324 Shift = Column - Changes[i].StartOfTokenColumn;
325 Changes[i].Spaces += Shift;
326 }
327
328 // This is for function parameters that are split across multiple lines,
329 // as mentioned in the ScopeStack comment.
330 if (InsideNestedScope && Changes[i].NewlinesBefore > 0) {
331 unsigned ScopeStart = ScopeStack.back();
332 auto ShouldShiftBeAdded = [&] {
333 // Function declaration
334 if (Changes[ScopeStart - 1].Tok->is(TT_FunctionDeclarationName))
335 return true;
336
337 // Continued function declaration
338 if (ScopeStart > Start + 1 &&
339 Changes[ScopeStart - 2].Tok->is(TT_FunctionDeclarationName))
340 return true;
341
342 // Continued function call
343 if (ScopeStart > Start + 1 &&
344 Changes[ScopeStart - 2].Tok->is(tok::identifier) &&
345 Changes[ScopeStart - 1].Tok->is(tok::l_paren))
346 return true;
347
348 // Ternary operator
349 if (Changes[i].Tok->is(TT_ConditionalExpr))
350 return true;
351
352 // Continued ternary operator
353 if (Changes[i].Tok->Previous &&
354 Changes[i].Tok->Previous->is(TT_ConditionalExpr))
355 return true;
356
357 return false;
358 };
359
360 if (ShouldShiftBeAdded())
361 Changes[i].Spaces += Shift;
362 }
363
364 if (ContinuedStringLiteral)
365 Changes[i].Spaces += Shift;
366
367 assert(Shift >= 0);
368 Changes[i].StartOfTokenColumn += Shift;
369 if (i + 1 != Changes.size())
370 Changes[i + 1].PreviousEndOfTokenColumn += Shift;
371 }
372 }
373
374 // Walk through a subset of the changes, starting at StartAt, and find
375 // sequences of matching tokens to align. To do so, keep track of the lines and
376 // whether or not a matching token was found on a line. If a matching token is
377 // found, extend the current sequence. If the current line cannot be part of a
378 // sequence, e.g. because there is an empty line before it or it contains only
379 // non-matching tokens, finalize the previous sequence.
380 // The value returned is the token on which we stopped, either because we
381 // exhausted all items inside Changes, or because we hit a scope level higher
382 // than our initial scope.
383 // This function is recursive. Each invocation processes only the scope level
384 // equal to the initial level, which is the level of Changes[StartAt].
385 // If we encounter a scope level greater than the initial level, then we call
386 // ourselves recursively, thereby avoiding the pollution of the current state
387 // with the alignment requirements of the nested sub-level. This recursive
388 // behavior is necessary for aligning function prototypes that have one or more
389 // arguments.
390 // If this function encounters a scope level less than the initial level,
391 // it returns the current position.
392 // There is a non-obvious subtlety in the recursive behavior: Even though we
393 // defer processing of nested levels to recursive invocations of this
394 // function, when it comes time to align a sequence of tokens, we run the
395 // alignment on the entire sequence, including the nested levels.
396 // When doing so, most of the nested tokens are skipped, because their
397 // alignment was already handled by the recursive invocations of this function.
398 // However, the special exception is that we do NOT skip function parameters
399 // that are split across multiple lines. See the test case in FormatTest.cpp
400 // that mentions "split function parameter alignment" for an example of this.
401 template <typename F>
AlignTokens(const FormatStyle & Style,F && Matches,SmallVector<WhitespaceManager::Change,16> & Changes,unsigned StartAt,const FormatStyle::AlignConsecutiveStyle & ACS=FormatStyle::ACS_None)402 static unsigned AlignTokens(
403 const FormatStyle &Style, F &&Matches,
404 SmallVector<WhitespaceManager::Change, 16> &Changes, unsigned StartAt,
405 const FormatStyle::AlignConsecutiveStyle &ACS = FormatStyle::ACS_None) {
406 unsigned MinColumn = 0;
407 unsigned MaxColumn = UINT_MAX;
408
409 // Line number of the start and the end of the current token sequence.
410 unsigned StartOfSequence = 0;
411 unsigned EndOfSequence = 0;
412
413 // Measure the scope level (i.e. depth of (), [], {}) of the first token, and
414 // abort when we hit any token in a higher scope than the starting one.
415 auto IndentAndNestingLevel = StartAt < Changes.size()
416 ? Changes[StartAt].indentAndNestingLevel()
417 : std::tuple<unsigned, unsigned, unsigned>();
418
419 // Keep track of the number of commas before the matching tokens, we will only
420 // align a sequence of matching tokens if they are preceded by the same number
421 // of commas.
422 unsigned CommasBeforeLastMatch = 0;
423 unsigned CommasBeforeMatch = 0;
424
425 // Whether a matching token has been found on the current line.
426 bool FoundMatchOnLine = false;
427
428 // Whether the current line consists purely of comments.
429 bool LineIsComment = true;
430
431 // Aligns a sequence of matching tokens, on the MinColumn column.
432 //
433 // Sequences start from the first matching token to align, and end at the
434 // first token of the first line that doesn't need to be aligned.
435 //
436 // We need to adjust the StartOfTokenColumn of each Change that is on a line
437 // containing any matching token to be aligned and located after such token.
438 auto AlignCurrentSequence = [&] {
439 if (StartOfSequence > 0 && StartOfSequence < EndOfSequence)
440 AlignTokenSequence(StartOfSequence, EndOfSequence, MinColumn, Matches,
441 Changes);
442 MinColumn = 0;
443 MaxColumn = UINT_MAX;
444 StartOfSequence = 0;
445 EndOfSequence = 0;
446 };
447
448 unsigned i = StartAt;
449 for (unsigned e = Changes.size(); i != e; ++i) {
450 if (Changes[i].indentAndNestingLevel() < IndentAndNestingLevel)
451 break;
452
453 if (Changes[i].NewlinesBefore != 0) {
454 CommasBeforeMatch = 0;
455 EndOfSequence = i;
456
457 // Whether to break the alignment sequence because of an empty line.
458 bool EmptyLineBreak =
459 (Changes[i].NewlinesBefore > 1) &&
460 (ACS != FormatStyle::ACS_AcrossEmptyLines) &&
461 (ACS != FormatStyle::ACS_AcrossEmptyLinesAndComments);
462
463 // Whether to break the alignment sequence because of a line without a
464 // match.
465 bool NoMatchBreak =
466 !FoundMatchOnLine &&
467 !(LineIsComment &&
468 ((ACS == FormatStyle::ACS_AcrossComments) ||
469 (ACS == FormatStyle::ACS_AcrossEmptyLinesAndComments)));
470
471 if (EmptyLineBreak || NoMatchBreak)
472 AlignCurrentSequence();
473
474 // A new line starts, re-initialize line status tracking bools.
475 // Keep the match state if a string literal is continued on this line.
476 if (i == 0 || !Changes[i].Tok->is(tok::string_literal) ||
477 !Changes[i - 1].Tok->is(tok::string_literal))
478 FoundMatchOnLine = false;
479 LineIsComment = true;
480 }
481
482 if (!Changes[i].Tok->is(tok::comment)) {
483 LineIsComment = false;
484 }
485
486 if (Changes[i].Tok->is(tok::comma)) {
487 ++CommasBeforeMatch;
488 } else if (Changes[i].indentAndNestingLevel() > IndentAndNestingLevel) {
489 // Call AlignTokens recursively, skipping over this scope block.
490 unsigned StoppedAt = AlignTokens(Style, Matches, Changes, i, ACS);
491 i = StoppedAt - 1;
492 continue;
493 }
494
495 if (!Matches(Changes[i]))
496 continue;
497
498 // If there is more than one matching token per line, or if the number of
499 // preceding commas, do not match anymore, end the sequence.
500 if (FoundMatchOnLine || CommasBeforeMatch != CommasBeforeLastMatch)
501 AlignCurrentSequence();
502
503 CommasBeforeLastMatch = CommasBeforeMatch;
504 FoundMatchOnLine = true;
505
506 if (StartOfSequence == 0)
507 StartOfSequence = i;
508
509 unsigned ChangeMinColumn = Changes[i].StartOfTokenColumn;
510 int LineLengthAfter = Changes[i].TokenLength;
511 for (unsigned j = i + 1; j != e && Changes[j].NewlinesBefore == 0; ++j) {
512 LineLengthAfter += Changes[j].Spaces;
513 // Changes are generally 1:1 with the tokens, but a change could also be
514 // inside of a token, in which case it's counted more than once: once for
515 // the whitespace surrounding the token (!IsInsideToken) and once for
516 // each whitespace change within it (IsInsideToken).
517 // Therefore, changes inside of a token should only count the space.
518 if (!Changes[j].IsInsideToken)
519 LineLengthAfter += Changes[j].TokenLength;
520 }
521 unsigned ChangeMaxColumn = Style.ColumnLimit - LineLengthAfter;
522
523 // If we are restricted by the maximum column width, end the sequence.
524 if (ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn ||
525 CommasBeforeLastMatch != CommasBeforeMatch) {
526 AlignCurrentSequence();
527 StartOfSequence = i;
528 }
529
530 MinColumn = std::max(MinColumn, ChangeMinColumn);
531 MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
532 }
533
534 EndOfSequence = i;
535 AlignCurrentSequence();
536 return i;
537 }
538
539 // Aligns a sequence of matching tokens, on the MinColumn column.
540 //
541 // Sequences start from the first matching token to align, and end at the
542 // first token of the first line that doesn't need to be aligned.
543 //
544 // We need to adjust the StartOfTokenColumn of each Change that is on a line
545 // containing any matching token to be aligned and located after such token.
AlignMacroSequence(unsigned & StartOfSequence,unsigned & EndOfSequence,unsigned & MinColumn,unsigned & MaxColumn,bool & FoundMatchOnLine,std::function<bool (const WhitespaceManager::Change & C)> AlignMacrosMatches,SmallVector<WhitespaceManager::Change,16> & Changes)546 static void AlignMacroSequence(
547 unsigned &StartOfSequence, unsigned &EndOfSequence, unsigned &MinColumn,
548 unsigned &MaxColumn, bool &FoundMatchOnLine,
549 std::function<bool(const WhitespaceManager::Change &C)> AlignMacrosMatches,
550 SmallVector<WhitespaceManager::Change, 16> &Changes) {
551 if (StartOfSequence > 0 && StartOfSequence < EndOfSequence) {
552
553 FoundMatchOnLine = false;
554 int Shift = 0;
555
556 for (unsigned I = StartOfSequence; I != EndOfSequence; ++I) {
557 if (Changes[I].NewlinesBefore > 0) {
558 Shift = 0;
559 FoundMatchOnLine = false;
560 }
561
562 // If this is the first matching token to be aligned, remember by how many
563 // spaces it has to be shifted, so the rest of the changes on the line are
564 // shifted by the same amount
565 if (!FoundMatchOnLine && AlignMacrosMatches(Changes[I])) {
566 FoundMatchOnLine = true;
567 Shift = MinColumn - Changes[I].StartOfTokenColumn;
568 Changes[I].Spaces += Shift;
569 }
570
571 assert(Shift >= 0);
572 Changes[I].StartOfTokenColumn += Shift;
573 if (I + 1 != Changes.size())
574 Changes[I + 1].PreviousEndOfTokenColumn += Shift;
575 }
576 }
577
578 MinColumn = 0;
579 MaxColumn = UINT_MAX;
580 StartOfSequence = 0;
581 EndOfSequence = 0;
582 }
583
alignConsecutiveMacros()584 void WhitespaceManager::alignConsecutiveMacros() {
585 if (Style.AlignConsecutiveMacros == FormatStyle::ACS_None)
586 return;
587
588 auto AlignMacrosMatches = [](const Change &C) {
589 const FormatToken *Current = C.Tok;
590 unsigned SpacesRequiredBefore = 1;
591
592 if (Current->SpacesRequiredBefore == 0 || !Current->Previous)
593 return false;
594
595 Current = Current->Previous;
596
597 // If token is a ")", skip over the parameter list, to the
598 // token that precedes the "("
599 if (Current->is(tok::r_paren) && Current->MatchingParen) {
600 Current = Current->MatchingParen->Previous;
601 SpacesRequiredBefore = 0;
602 }
603
604 if (!Current || !Current->is(tok::identifier))
605 return false;
606
607 if (!Current->Previous || !Current->Previous->is(tok::pp_define))
608 return false;
609
610 // For a macro function, 0 spaces are required between the
611 // identifier and the lparen that opens the parameter list.
612 // For a simple macro, 1 space is required between the
613 // identifier and the first token of the defined value.
614 return Current->Next->SpacesRequiredBefore == SpacesRequiredBefore;
615 };
616
617 unsigned MinColumn = 0;
618 unsigned MaxColumn = UINT_MAX;
619
620 // Start and end of the token sequence we're processing.
621 unsigned StartOfSequence = 0;
622 unsigned EndOfSequence = 0;
623
624 // Whether a matching token has been found on the current line.
625 bool FoundMatchOnLine = false;
626
627 // Whether the current line consists only of comments
628 bool LineIsComment = true;
629
630 unsigned I = 0;
631 for (unsigned E = Changes.size(); I != E; ++I) {
632 if (Changes[I].NewlinesBefore != 0) {
633 EndOfSequence = I;
634
635 // Whether to break the alignment sequence because of an empty line.
636 bool EmptyLineBreak =
637 (Changes[I].NewlinesBefore > 1) &&
638 (Style.AlignConsecutiveMacros != FormatStyle::ACS_AcrossEmptyLines) &&
639 (Style.AlignConsecutiveMacros !=
640 FormatStyle::ACS_AcrossEmptyLinesAndComments);
641
642 // Whether to break the alignment sequence because of a line without a
643 // match.
644 bool NoMatchBreak =
645 !FoundMatchOnLine &&
646 !(LineIsComment && ((Style.AlignConsecutiveMacros ==
647 FormatStyle::ACS_AcrossComments) ||
648 (Style.AlignConsecutiveMacros ==
649 FormatStyle::ACS_AcrossEmptyLinesAndComments)));
650
651 if (EmptyLineBreak || NoMatchBreak)
652 AlignMacroSequence(StartOfSequence, EndOfSequence, MinColumn, MaxColumn,
653 FoundMatchOnLine, AlignMacrosMatches, Changes);
654
655 // A new line starts, re-initialize line status tracking bools.
656 FoundMatchOnLine = false;
657 LineIsComment = true;
658 }
659
660 if (!Changes[I].Tok->is(tok::comment)) {
661 LineIsComment = false;
662 }
663
664 if (!AlignMacrosMatches(Changes[I]))
665 continue;
666
667 FoundMatchOnLine = true;
668
669 if (StartOfSequence == 0)
670 StartOfSequence = I;
671
672 unsigned ChangeMinColumn = Changes[I].StartOfTokenColumn;
673 int LineLengthAfter = -Changes[I].Spaces;
674 for (unsigned j = I; j != E && Changes[j].NewlinesBefore == 0; ++j)
675 LineLengthAfter += Changes[j].Spaces + Changes[j].TokenLength;
676 unsigned ChangeMaxColumn = Style.ColumnLimit - LineLengthAfter;
677
678 MinColumn = std::max(MinColumn, ChangeMinColumn);
679 MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
680 }
681
682 EndOfSequence = I;
683 AlignMacroSequence(StartOfSequence, EndOfSequence, MinColumn, MaxColumn,
684 FoundMatchOnLine, AlignMacrosMatches, Changes);
685 }
686
alignConsecutiveAssignments()687 void WhitespaceManager::alignConsecutiveAssignments() {
688 if (Style.AlignConsecutiveAssignments == FormatStyle::ACS_None)
689 return;
690
691 AlignTokens(
692 Style,
693 [&](const Change &C) {
694 // Do not align on equal signs that are first on a line.
695 if (C.NewlinesBefore > 0)
696 return false;
697
698 // Do not align on equal signs that are last on a line.
699 if (&C != &Changes.back() && (&C + 1)->NewlinesBefore > 0)
700 return false;
701
702 return C.Tok->is(tok::equal);
703 },
704 Changes, /*StartAt=*/0, Style.AlignConsecutiveAssignments);
705 }
706
alignConsecutiveBitFields()707 void WhitespaceManager::alignConsecutiveBitFields() {
708 if (Style.AlignConsecutiveBitFields == FormatStyle::ACS_None)
709 return;
710
711 AlignTokens(
712 Style,
713 [&](Change const &C) {
714 // Do not align on ':' that is first on a line.
715 if (C.NewlinesBefore > 0)
716 return false;
717
718 // Do not align on ':' that is last on a line.
719 if (&C != &Changes.back() && (&C + 1)->NewlinesBefore > 0)
720 return false;
721
722 return C.Tok->is(TT_BitFieldColon);
723 },
724 Changes, /*StartAt=*/0, Style.AlignConsecutiveBitFields);
725 }
726
alignConsecutiveDeclarations()727 void WhitespaceManager::alignConsecutiveDeclarations() {
728 if (Style.AlignConsecutiveDeclarations == FormatStyle::ACS_None)
729 return;
730
731 // FIXME: Currently we don't handle properly the PointerAlignment: Right
732 // The * and & are not aligned and are left dangling. Something has to be done
733 // about it, but it raises the question of alignment of code like:
734 // const char* const* v1;
735 // float const* v2;
736 // SomeVeryLongType const& v3;
737 AlignTokens(
738 Style,
739 [](Change const &C) {
740 // tok::kw_operator is necessary for aligning operator overload
741 // definitions.
742 if (C.Tok->isOneOf(TT_FunctionDeclarationName, tok::kw_operator))
743 return true;
744 if (C.Tok->isNot(TT_StartOfName))
745 return false;
746 if (C.Tok->Previous &&
747 C.Tok->Previous->is(TT_StatementAttributeLikeMacro))
748 return false;
749 // Check if there is a subsequent name that starts the same declaration.
750 for (FormatToken *Next = C.Tok->Next; Next; Next = Next->Next) {
751 if (Next->is(tok::comment))
752 continue;
753 if (Next->is(TT_PointerOrReference))
754 return false;
755 if (!Next->Tok.getIdentifierInfo())
756 break;
757 if (Next->isOneOf(TT_StartOfName, TT_FunctionDeclarationName,
758 tok::kw_operator))
759 return false;
760 }
761 return true;
762 },
763 Changes, /*StartAt=*/0, Style.AlignConsecutiveDeclarations);
764 }
765
alignChainedConditionals()766 void WhitespaceManager::alignChainedConditionals() {
767 if (Style.BreakBeforeTernaryOperators) {
768 AlignTokens(
769 Style,
770 [](Change const &C) {
771 // Align question operators and last colon
772 return C.Tok->is(TT_ConditionalExpr) &&
773 ((C.Tok->is(tok::question) && !C.NewlinesBefore) ||
774 (C.Tok->is(tok::colon) && C.Tok->Next &&
775 (C.Tok->Next->FakeLParens.size() == 0 ||
776 C.Tok->Next->FakeLParens.back() != prec::Conditional)));
777 },
778 Changes, /*StartAt=*/0);
779 } else {
780 static auto AlignWrappedOperand = [](Change const &C) {
781 FormatToken *Previous = C.Tok->getPreviousNonComment();
782 return C.NewlinesBefore && Previous && Previous->is(TT_ConditionalExpr) &&
783 (Previous->is(tok::colon) &&
784 (C.Tok->FakeLParens.size() == 0 ||
785 C.Tok->FakeLParens.back() != prec::Conditional));
786 };
787 // Ensure we keep alignment of wrapped operands with non-wrapped operands
788 // Since we actually align the operators, the wrapped operands need the
789 // extra offset to be properly aligned.
790 for (Change &C : Changes) {
791 if (AlignWrappedOperand(C))
792 C.StartOfTokenColumn -= 2;
793 }
794 AlignTokens(
795 Style,
796 [this](Change const &C) {
797 // Align question operators if next operand is not wrapped, as
798 // well as wrapped operands after question operator or last
799 // colon in conditional sequence
800 return (C.Tok->is(TT_ConditionalExpr) && C.Tok->is(tok::question) &&
801 &C != &Changes.back() && (&C + 1)->NewlinesBefore == 0 &&
802 !(&C + 1)->IsTrailingComment) ||
803 AlignWrappedOperand(C);
804 },
805 Changes, /*StartAt=*/0);
806 }
807 }
808
alignTrailingComments()809 void WhitespaceManager::alignTrailingComments() {
810 unsigned MinColumn = 0;
811 unsigned MaxColumn = UINT_MAX;
812 unsigned StartOfSequence = 0;
813 bool BreakBeforeNext = false;
814 unsigned Newlines = 0;
815 for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
816 if (Changes[i].StartOfBlockComment)
817 continue;
818 Newlines += Changes[i].NewlinesBefore;
819 if (!Changes[i].IsTrailingComment)
820 continue;
821
822 unsigned ChangeMinColumn = Changes[i].StartOfTokenColumn;
823 unsigned ChangeMaxColumn;
824
825 if (Style.ColumnLimit == 0)
826 ChangeMaxColumn = UINT_MAX;
827 else if (Style.ColumnLimit >= Changes[i].TokenLength)
828 ChangeMaxColumn = Style.ColumnLimit - Changes[i].TokenLength;
829 else
830 ChangeMaxColumn = ChangeMinColumn;
831
832 // If we don't create a replacement for this change, we have to consider
833 // it to be immovable.
834 if (!Changes[i].CreateReplacement)
835 ChangeMaxColumn = ChangeMinColumn;
836
837 if (i + 1 != e && Changes[i + 1].ContinuesPPDirective)
838 ChangeMaxColumn -= 2;
839 // If this comment follows an } in column 0, it probably documents the
840 // closing of a namespace and we don't want to align it.
841 bool FollowsRBraceInColumn0 = i > 0 && Changes[i].NewlinesBefore == 0 &&
842 Changes[i - 1].Tok->is(tok::r_brace) &&
843 Changes[i - 1].StartOfTokenColumn == 0;
844 bool WasAlignedWithStartOfNextLine = false;
845 if (Changes[i].NewlinesBefore == 1) { // A comment on its own line.
846 unsigned CommentColumn = SourceMgr.getSpellingColumnNumber(
847 Changes[i].OriginalWhitespaceRange.getEnd());
848 for (unsigned j = i + 1; j != e; ++j) {
849 if (Changes[j].Tok->is(tok::comment))
850 continue;
851
852 unsigned NextColumn = SourceMgr.getSpellingColumnNumber(
853 Changes[j].OriginalWhitespaceRange.getEnd());
854 // The start of the next token was previously aligned with the
855 // start of this comment.
856 WasAlignedWithStartOfNextLine =
857 CommentColumn == NextColumn ||
858 CommentColumn == NextColumn + Style.IndentWidth;
859 break;
860 }
861 }
862 if (!Style.AlignTrailingComments || FollowsRBraceInColumn0) {
863 alignTrailingComments(StartOfSequence, i, MinColumn);
864 MinColumn = ChangeMinColumn;
865 MaxColumn = ChangeMinColumn;
866 StartOfSequence = i;
867 } else if (BreakBeforeNext || Newlines > 1 ||
868 (ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn) ||
869 // Break the comment sequence if the previous line did not end
870 // in a trailing comment.
871 (Changes[i].NewlinesBefore == 1 && i > 0 &&
872 !Changes[i - 1].IsTrailingComment) ||
873 WasAlignedWithStartOfNextLine) {
874 alignTrailingComments(StartOfSequence, i, MinColumn);
875 MinColumn = ChangeMinColumn;
876 MaxColumn = ChangeMaxColumn;
877 StartOfSequence = i;
878 } else {
879 MinColumn = std::max(MinColumn, ChangeMinColumn);
880 MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
881 }
882 BreakBeforeNext = (i == 0) || (Changes[i].NewlinesBefore > 1) ||
883 // Never start a sequence with a comment at the beginning
884 // of the line.
885 (Changes[i].NewlinesBefore == 1 && StartOfSequence == i);
886 Newlines = 0;
887 }
888 alignTrailingComments(StartOfSequence, Changes.size(), MinColumn);
889 }
890
alignTrailingComments(unsigned Start,unsigned End,unsigned Column)891 void WhitespaceManager::alignTrailingComments(unsigned Start, unsigned End,
892 unsigned Column) {
893 for (unsigned i = Start; i != End; ++i) {
894 int Shift = 0;
895 if (Changes[i].IsTrailingComment) {
896 Shift = Column - Changes[i].StartOfTokenColumn;
897 }
898 if (Changes[i].StartOfBlockComment) {
899 Shift = Changes[i].IndentationOffset +
900 Changes[i].StartOfBlockComment->StartOfTokenColumn -
901 Changes[i].StartOfTokenColumn;
902 }
903 assert(Shift >= 0);
904 Changes[i].Spaces += Shift;
905 if (i + 1 != Changes.size())
906 Changes[i + 1].PreviousEndOfTokenColumn += Shift;
907 Changes[i].StartOfTokenColumn += Shift;
908 }
909 }
910
alignEscapedNewlines()911 void WhitespaceManager::alignEscapedNewlines() {
912 if (Style.AlignEscapedNewlines == FormatStyle::ENAS_DontAlign)
913 return;
914
915 bool AlignLeft = Style.AlignEscapedNewlines == FormatStyle::ENAS_Left;
916 unsigned MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
917 unsigned StartOfMacro = 0;
918 for (unsigned i = 1, e = Changes.size(); i < e; ++i) {
919 Change &C = Changes[i];
920 if (C.NewlinesBefore > 0) {
921 if (C.ContinuesPPDirective) {
922 MaxEndOfLine = std::max(C.PreviousEndOfTokenColumn + 2, MaxEndOfLine);
923 } else {
924 alignEscapedNewlines(StartOfMacro + 1, i, MaxEndOfLine);
925 MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
926 StartOfMacro = i;
927 }
928 }
929 }
930 alignEscapedNewlines(StartOfMacro + 1, Changes.size(), MaxEndOfLine);
931 }
932
alignEscapedNewlines(unsigned Start,unsigned End,unsigned Column)933 void WhitespaceManager::alignEscapedNewlines(unsigned Start, unsigned End,
934 unsigned Column) {
935 for (unsigned i = Start; i < End; ++i) {
936 Change &C = Changes[i];
937 if (C.NewlinesBefore > 0) {
938 assert(C.ContinuesPPDirective);
939 if (C.PreviousEndOfTokenColumn + 1 > Column)
940 C.EscapedNewlineColumn = 0;
941 else
942 C.EscapedNewlineColumn = Column;
943 }
944 }
945 }
946
generateChanges()947 void WhitespaceManager::generateChanges() {
948 for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
949 const Change &C = Changes[i];
950 if (i > 0) {
951 assert(Changes[i - 1].OriginalWhitespaceRange.getBegin() !=
952 C.OriginalWhitespaceRange.getBegin() &&
953 "Generating two replacements for the same location");
954 }
955 if (C.CreateReplacement) {
956 std::string ReplacementText = C.PreviousLinePostfix;
957 if (C.ContinuesPPDirective)
958 appendEscapedNewlineText(ReplacementText, C.NewlinesBefore,
959 C.PreviousEndOfTokenColumn,
960 C.EscapedNewlineColumn);
961 else
962 appendNewlineText(ReplacementText, C.NewlinesBefore);
963 appendIndentText(
964 ReplacementText, C.Tok->IndentLevel, std::max(0, C.Spaces),
965 C.StartOfTokenColumn - std::max(0, C.Spaces), C.IsAligned);
966 ReplacementText.append(C.CurrentLinePrefix);
967 storeReplacement(C.OriginalWhitespaceRange, ReplacementText);
968 }
969 }
970 }
971
storeReplacement(SourceRange Range,StringRef Text)972 void WhitespaceManager::storeReplacement(SourceRange Range, StringRef Text) {
973 unsigned WhitespaceLength = SourceMgr.getFileOffset(Range.getEnd()) -
974 SourceMgr.getFileOffset(Range.getBegin());
975 // Don't create a replacement, if it does not change anything.
976 if (StringRef(SourceMgr.getCharacterData(Range.getBegin()),
977 WhitespaceLength) == Text)
978 return;
979 auto Err = Replaces.add(tooling::Replacement(
980 SourceMgr, CharSourceRange::getCharRange(Range), Text));
981 // FIXME: better error handling. For now, just print an error message in the
982 // release version.
983 if (Err) {
984 llvm::errs() << llvm::toString(std::move(Err)) << "\n";
985 assert(false);
986 }
987 }
988
appendNewlineText(std::string & Text,unsigned Newlines)989 void WhitespaceManager::appendNewlineText(std::string &Text,
990 unsigned Newlines) {
991 for (unsigned i = 0; i < Newlines; ++i)
992 Text.append(UseCRLF ? "\r\n" : "\n");
993 }
994
appendEscapedNewlineText(std::string & Text,unsigned Newlines,unsigned PreviousEndOfTokenColumn,unsigned EscapedNewlineColumn)995 void WhitespaceManager::appendEscapedNewlineText(
996 std::string &Text, unsigned Newlines, unsigned PreviousEndOfTokenColumn,
997 unsigned EscapedNewlineColumn) {
998 if (Newlines > 0) {
999 unsigned Spaces =
1000 std::max<int>(1, EscapedNewlineColumn - PreviousEndOfTokenColumn - 1);
1001 for (unsigned i = 0; i < Newlines; ++i) {
1002 Text.append(Spaces, ' ');
1003 Text.append(UseCRLF ? "\\\r\n" : "\\\n");
1004 Spaces = std::max<int>(0, EscapedNewlineColumn - 1);
1005 }
1006 }
1007 }
1008
appendIndentText(std::string & Text,unsigned IndentLevel,unsigned Spaces,unsigned WhitespaceStartColumn,bool IsAligned)1009 void WhitespaceManager::appendIndentText(std::string &Text,
1010 unsigned IndentLevel, unsigned Spaces,
1011 unsigned WhitespaceStartColumn,
1012 bool IsAligned) {
1013 switch (Style.UseTab) {
1014 case FormatStyle::UT_Never:
1015 Text.append(Spaces, ' ');
1016 break;
1017 case FormatStyle::UT_Always: {
1018 if (Style.TabWidth) {
1019 unsigned FirstTabWidth =
1020 Style.TabWidth - WhitespaceStartColumn % Style.TabWidth;
1021
1022 // Insert only spaces when we want to end up before the next tab.
1023 if (Spaces < FirstTabWidth || Spaces == 1) {
1024 Text.append(Spaces, ' ');
1025 break;
1026 }
1027 // Align to the next tab.
1028 Spaces -= FirstTabWidth;
1029 Text.append("\t");
1030
1031 Text.append(Spaces / Style.TabWidth, '\t');
1032 Text.append(Spaces % Style.TabWidth, ' ');
1033 } else if (Spaces == 1) {
1034 Text.append(Spaces, ' ');
1035 }
1036 break;
1037 }
1038 case FormatStyle::UT_ForIndentation:
1039 if (WhitespaceStartColumn == 0) {
1040 unsigned Indentation = IndentLevel * Style.IndentWidth;
1041 Spaces = appendTabIndent(Text, Spaces, Indentation);
1042 }
1043 Text.append(Spaces, ' ');
1044 break;
1045 case FormatStyle::UT_ForContinuationAndIndentation:
1046 if (WhitespaceStartColumn == 0)
1047 Spaces = appendTabIndent(Text, Spaces, Spaces);
1048 Text.append(Spaces, ' ');
1049 break;
1050 case FormatStyle::UT_AlignWithSpaces:
1051 if (WhitespaceStartColumn == 0) {
1052 unsigned Indentation =
1053 IsAligned ? IndentLevel * Style.IndentWidth : Spaces;
1054 Spaces = appendTabIndent(Text, Spaces, Indentation);
1055 }
1056 Text.append(Spaces, ' ');
1057 break;
1058 }
1059 }
1060
appendTabIndent(std::string & Text,unsigned Spaces,unsigned Indentation)1061 unsigned WhitespaceManager::appendTabIndent(std::string &Text, unsigned Spaces,
1062 unsigned Indentation) {
1063 // This happens, e.g. when a line in a block comment is indented less than the
1064 // first one.
1065 if (Indentation > Spaces)
1066 Indentation = Spaces;
1067 if (Style.TabWidth) {
1068 unsigned Tabs = Indentation / Style.TabWidth;
1069 Text.append(Tabs, '\t');
1070 Spaces -= Tabs * Style.TabWidth;
1071 }
1072 return Spaces;
1073 }
1074
1075 } // namespace format
1076 } // namespace clang
1077