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	#include "llvm/ADT/SmallVector.h"
17	#include <algorithm>
18
19	namespace clang {
20	namespace format {
21
22	bool WhitespaceManager::Change::IsBeforeInFile::operator()(
23	const Change &C1, const Change &C2) const {
24	return SourceMgr.isBeforeInTranslationUnit(
25	LHS: C1.OriginalWhitespaceRange.getBegin(),
26	RHS: C2.OriginalWhitespaceRange.getBegin()) ||
27	(C1.OriginalWhitespaceRange.getBegin() ==
28	C2.OriginalWhitespaceRange.getBegin() &&
29	SourceMgr.isBeforeInTranslationUnit(
30	LHS: C1.OriginalWhitespaceRange.getEnd(),
31	RHS: C2.OriginalWhitespaceRange.getEnd()));
32	}
33
34	WhitespaceManager::Change::Change(const FormatToken &Tok,
35	bool CreateReplacement,
36	SourceRange OriginalWhitespaceRange,
37	int Spaces, unsigned StartOfTokenColumn,
38	unsigned NewlinesBefore,
39	StringRef PreviousLinePostfix,
40	StringRef CurrentLinePrefix, bool IsAligned,
41	bool ContinuesPPDirective, bool IsInsideToken)
42	: Tok(&Tok), CreateReplacement(CreateReplacement),
43	OriginalWhitespaceRange(OriginalWhitespaceRange),
44	StartOfTokenColumn(StartOfTokenColumn), NewlinesBefore(NewlinesBefore),
45	PreviousLinePostfix(PreviousLinePostfix),
46	CurrentLinePrefix(CurrentLinePrefix), IsAligned(IsAligned),
47	ContinuesPPDirective(ContinuesPPDirective), Spaces(Spaces),
48	IsInsideToken(IsInsideToken), IsTrailingComment(false), TokenLength(0),
49	PreviousEndOfTokenColumn(0), EscapedNewlineColumn(0),
50	StartOfBlockComment(nullptr), IndentationOffset(0), ConditionalsLevel(0) {
51	}
52
53	void WhitespaceManager::replaceWhitespace(FormatToken &Tok, unsigned Newlines,
54	unsigned Spaces,
55	unsigned StartOfTokenColumn,
56	bool IsAligned, bool InPPDirective) {
57	if (Tok.Finalized || (Tok.MacroCtx && Tok.MacroCtx->Role == MR_ExpandedArg))
58	return;
59	Tok.setDecision((Newlines > 0) ? FD_Break : FD_Continue);
60	Changes.push_back(Elt: Change(Tok, /*CreateReplacement=*/true, Tok.WhitespaceRange,
61	Spaces, StartOfTokenColumn, Newlines, "", "",
62	IsAligned, InPPDirective && !Tok.IsFirst,
63	/*IsInsideToken=*/false));
64	}
65
66	void WhitespaceManager::addUntouchableToken(const FormatToken &Tok,
67	bool InPPDirective) {
68	if (Tok.Finalized || (Tok.MacroCtx && Tok.MacroCtx->Role == MR_ExpandedArg))
69	return;
70	Changes.push_back(Elt: Change(Tok, /*CreateReplacement=*/false,
71	Tok.WhitespaceRange, /*Spaces=*/0,
72	Tok.OriginalColumn, Tok.NewlinesBefore, "", "",
73	/*IsAligned=*/false, InPPDirective && !Tok.IsFirst,
74	/*IsInsideToken=*/false));
75	}
76
77	llvm::Error
78	WhitespaceManager::addReplacement(const tooling::Replacement &Replacement) {
79	return Replaces.add(R: Replacement);
80	}
81
82	bool WhitespaceManager::inputUsesCRLF(StringRef Text, bool DefaultToCRLF) {
83	size_t LF = Text.count(C: '\n');
84	size_t CR = Text.count(C: '\r') * 2;
85	return LF == CR ? DefaultToCRLF : CR > LF;
86	}
87
88	void WhitespaceManager::replaceWhitespaceInToken(
89	const FormatToken &Tok, unsigned Offset, unsigned ReplaceChars,
90	StringRef PreviousPostfix, StringRef CurrentPrefix, bool InPPDirective,
91	unsigned Newlines, int Spaces) {
92	if (Tok.Finalized || (Tok.MacroCtx && Tok.MacroCtx->Role == MR_ExpandedArg))
93	return;
94	SourceLocation Start = Tok.getStartOfNonWhitespace().getLocWithOffset(Offset);
95	Changes.push_back(
96	Elt: Change(Tok, /*CreateReplacement=*/true,
97	SourceRange(Start, Start.getLocWithOffset(Offset: ReplaceChars)), Spaces,
98	std::max(a: 0, b: Spaces), Newlines, PreviousPostfix, CurrentPrefix,
99	/*IsAligned=*/true, InPPDirective && !Tok.IsFirst,
100	/*IsInsideToken=*/true));
101	}
102
103	const tooling::Replacements &WhitespaceManager::generateReplacements() {
104	if (Changes.empty())
105	return Replaces;
106
107	llvm::sort(C&: Changes, Comp: Change::IsBeforeInFile(SourceMgr));
108	calculateLineBreakInformation();
109	alignConsecutiveMacros();
110	alignConsecutiveShortCaseStatements();
111	alignConsecutiveDeclarations();
112	alignConsecutiveBitFields();
113	alignConsecutiveAssignments();
114	if (Style.isTableGen()) {
115	alignConsecutiveTableGenBreakingDAGArgColons();
116	alignConsecutiveTableGenCondOperatorColons();
117	alignConsecutiveTableGenDefinitions();
118	}
119	alignChainedConditionals();
120	alignTrailingComments();
121	alignEscapedNewlines();
122	alignArrayInitializers();
123	generateChanges();
124
125	return Replaces;
126	}
127
128	void WhitespaceManager::calculateLineBreakInformation() {
129	Changes[0].PreviousEndOfTokenColumn = 0;
130	Change *LastOutsideTokenChange = &Changes[0];
131	for (unsigned i = 1, e = Changes.size(); i != e; ++i) {
132	SourceLocation OriginalWhitespaceStart =
133	Changes[i].OriginalWhitespaceRange.getBegin();
134	SourceLocation PreviousOriginalWhitespaceEnd =
135	Changes[i - 1].OriginalWhitespaceRange.getEnd();
136	unsigned OriginalWhitespaceStartOffset =
137	SourceMgr.getFileOffset(SpellingLoc: OriginalWhitespaceStart);
138	unsigned PreviousOriginalWhitespaceEndOffset =
139	SourceMgr.getFileOffset(SpellingLoc: PreviousOriginalWhitespaceEnd);
140	assert(PreviousOriginalWhitespaceEndOffset <=
141	OriginalWhitespaceStartOffset);
142	const char *const PreviousOriginalWhitespaceEndData =
143	SourceMgr.getCharacterData(SL: PreviousOriginalWhitespaceEnd);
144	StringRef Text(PreviousOriginalWhitespaceEndData,
145	SourceMgr.getCharacterData(SL: OriginalWhitespaceStart) -
146	PreviousOriginalWhitespaceEndData);
147	// Usually consecutive changes would occur in consecutive tokens. This is
148	// not the case however when analyzing some preprocessor runs of the
149	// annotated lines. For example, in this code:
150	//
151	// #if A // line 1
152	// int i = 1;
153	// #else B // line 2
154	// int i = 2;
155	// #endif // line 3
156	//
157	// one of the runs will produce the sequence of lines marked with line 1, 2
158	// and 3. So the two consecutive whitespace changes just before '// line 2'
159	// and before '#endif // line 3' span multiple lines and tokens:
160	//
161	// #else B{change X}[// line 2
162	// int i = 2;
163	// ]{change Y}#endif // line 3
164	//
165	// For this reason, if the text between consecutive changes spans multiple
166	// newlines, the token length must be adjusted to the end of the original
167	// line of the token.
168	auto NewlinePos = Text.find_first_of(C: '\n');
169	if (NewlinePos == StringRef::npos) {
170	Changes[i - 1].TokenLength = OriginalWhitespaceStartOffset -
171	PreviousOriginalWhitespaceEndOffset +
172	Changes[i].PreviousLinePostfix.size() +
173	Changes[i - 1].CurrentLinePrefix.size();
174	} else {
175	Changes[i - 1].TokenLength =
176	NewlinePos + Changes[i - 1].CurrentLinePrefix.size();
177	}
178
179	// If there are multiple changes in this token, sum up all the changes until
180	// the end of the line.
181	if (Changes[i - 1].IsInsideToken && Changes[i - 1].NewlinesBefore == 0) {
182	LastOutsideTokenChange->TokenLength +=
183	Changes[i - 1].TokenLength + Changes[i - 1].Spaces;
184	} else {
185	LastOutsideTokenChange = &Changes[i - 1];
186	}
187
188	Changes[i].PreviousEndOfTokenColumn =
189	Changes[i - 1].StartOfTokenColumn + Changes[i - 1].TokenLength;
190
191	Changes[i - 1].IsTrailingComment =
192	(Changes[i].NewlinesBefore > 0 || Changes[i].Tok->is(Kind: tok::eof) ||
193	(Changes[i].IsInsideToken && Changes[i].Tok->is(Kind: tok::comment))) &&
194	Changes[i - 1].Tok->is(Kind: tok::comment) &&
195	// FIXME: This is a dirty hack. The problem is that
196	// BreakableLineCommentSection does comment reflow changes and here is
197	// the aligning of trailing comments. Consider the case where we reflow
198	// the second line up in this example:
199	//
200	// // line 1
201	// // line 2
202	//
203	// That amounts to 2 changes by BreakableLineCommentSection:
204	// - the first, delimited by (), for the whitespace between the tokens,
205	// - and second, delimited by [], for the whitespace at the beginning
206	// of the second token:
207	//
208	// // line 1(
209	// )[// ]line 2
210	//
211	// So in the end we have two changes like this:
212	//
213	// // line1()[ ]line 2
214	//
215	// Note that the OriginalWhitespaceStart of the second change is the
216	// same as the PreviousOriginalWhitespaceEnd of the first change.
217	// In this case, the below check ensures that the second change doesn't
218	// get treated as a trailing comment change here, since this might
219	// trigger additional whitespace to be wrongly inserted before "line 2"
220	// by the comment aligner here.
221	//
222	// For a proper solution we need a mechanism to say to WhitespaceManager
223	// that a particular change breaks the current sequence of trailing
224	// comments.
225	OriginalWhitespaceStart != PreviousOriginalWhitespaceEnd;
226	}
227	// FIXME: The last token is currently not always an eof token; in those
228	// cases, setting TokenLength of the last token to 0 is wrong.
229	Changes.back().TokenLength = 0;
230	Changes.back().IsTrailingComment = Changes.back().Tok->is(Kind: tok::comment);
231
232	const WhitespaceManager::Change *LastBlockComment = nullptr;
233	for (auto &Change : Changes) {
234	// Reset the IsTrailingComment flag for changes inside of trailing comments
235	// so they don't get realigned later. Comment line breaks however still need
236	// to be aligned.
237	if (Change.IsInsideToken && Change.NewlinesBefore == 0)
238	Change.IsTrailingComment = false;
239	Change.StartOfBlockComment = nullptr;
240	Change.IndentationOffset = 0;
241	if (Change.Tok->is(Kind: tok::comment)) {
242	if (Change.Tok->is(TT: TT_LineComment) || !Change.IsInsideToken) {
243	LastBlockComment = &Change;
244	} else if ((Change.StartOfBlockComment = LastBlockComment)) {
245	Change.IndentationOffset =
246	Change.StartOfTokenColumn -
247	Change.StartOfBlockComment->StartOfTokenColumn;
248	}
249	} else {
250	LastBlockComment = nullptr;
251	}
252	}
253
254	// Compute conditional nesting level
255	// Level is increased for each conditional, unless this conditional continues
256	// a chain of conditional, i.e. starts immediately after the colon of another
257	// conditional.
258	SmallVector<bool, 16> ScopeStack;
259	int ConditionalsLevel = 0;
260	for (auto &Change : Changes) {
261	for (unsigned i = 0, e = Change.Tok->FakeLParens.size(); i != e; ++i) {
262	bool isNestedConditional =
263	Change.Tok->FakeLParens[e - 1 - i] == prec::Conditional &&
264	!(i == 0 && Change.Tok->Previous &&
265	Change.Tok->Previous->is(TT: TT_ConditionalExpr) &&
266	Change.Tok->Previous->is(Kind: tok::colon));
267	if (isNestedConditional)
268	++ConditionalsLevel;
269	ScopeStack.push_back(Elt: isNestedConditional);
270	}
271
272	Change.ConditionalsLevel = ConditionalsLevel;
273
274	for (unsigned i = Change.Tok->FakeRParens; i > 0 && ScopeStack.size(); --i)
275	if (ScopeStack.pop_back_val())
276	--ConditionalsLevel;
277	}
278	}
279
280	// Align a single sequence of tokens, see AlignTokens below.
281	// Column - The token for which Matches returns true is moved to this column.
282	// RightJustify - Whether it is the token's right end or left end that gets
283	// moved to that column.
284	template <typename F>
285	static void
286	AlignTokenSequence(const FormatStyle &Style, unsigned Start, unsigned End,
287	unsigned Column, bool RightJustify, F &&Matches,
288	SmallVector<WhitespaceManager::Change, 16> &Changes) {
289	bool FoundMatchOnLine = false;
290	int Shift = 0;
291
292	// ScopeStack keeps track of the current scope depth. It contains indices of
293	// the first token on each scope.
294	// We only run the "Matches" function on tokens from the outer-most scope.
295	// However, we do need to pay special attention to one class of tokens
296	// that are not in the outer-most scope, and that is function parameters
297	// which are split across multiple lines, as illustrated by this example:
298	// double a(int x);
299	// int b(int y,
300	// double z);
301	// In the above example, we need to take special care to ensure that
302	// 'double z' is indented along with it's owning function 'b'.
303	// The same holds for calling a function:
304	// double a = foo(x);
305	// int b = bar(foo(y),
306	// foor(z));
307	// Similar for broken string literals:
308	// double x = 3.14;
309	// auto s = "Hello"
310	// "World";
311	// Special handling is required for 'nested' ternary operators.
312	SmallVector<unsigned, 16> ScopeStack;
313
314	for (unsigned i = Start; i != End; ++i) {
315	auto &CurrentChange = Changes[i];
316	if (ScopeStack.size() != 0 &&
317	CurrentChange.indentAndNestingLevel() <
318	Changes[ScopeStack.back()].indentAndNestingLevel()) {
319	ScopeStack.pop_back();
320	}
321
322	// Compare current token to previous non-comment token to ensure whether
323	// it is in a deeper scope or not.
324	unsigned PreviousNonComment = i - 1;
325	while (PreviousNonComment > Start &&
326	Changes[PreviousNonComment].Tok->is(Kind: tok::comment)) {
327	--PreviousNonComment;
328	}
329	if (i != Start && CurrentChange.indentAndNestingLevel() >
330	Changes[PreviousNonComment].indentAndNestingLevel()) {
331	ScopeStack.push_back(Elt: i);
332	}
333
334	bool InsideNestedScope = ScopeStack.size() != 0;
335	bool ContinuedStringLiteral = i > Start &&
336	CurrentChange.Tok->is(Kind: tok::string_literal) &&
337	Changes[i - 1].Tok->is(Kind: tok::string_literal);
338	bool SkipMatchCheck = InsideNestedScope || ContinuedStringLiteral;
339
340	if (CurrentChange.NewlinesBefore > 0 && !SkipMatchCheck) {
341	Shift = 0;
342	FoundMatchOnLine = false;
343	}
344
345	// If this is the first matching token to be aligned, remember by how many
346	// spaces it has to be shifted, so the rest of the changes on the line are
347	// shifted by the same amount
348	if (!FoundMatchOnLine && !SkipMatchCheck && Matches(CurrentChange)) {
349	FoundMatchOnLine = true;
350	Shift = Column - (RightJustify ? CurrentChange.TokenLength : 0) -
351	CurrentChange.StartOfTokenColumn;
352	CurrentChange.Spaces += Shift;
353	// FIXME: This is a workaround that should be removed when we fix
354	// http://llvm.org/PR53699. An assertion later below verifies this.
355	if (CurrentChange.NewlinesBefore == 0) {
356	CurrentChange.Spaces =
357	std::max(a: CurrentChange.Spaces,
358	b: static_cast<int>(CurrentChange.Tok->SpacesRequiredBefore));
359	}
360	}
361
362	if (Shift == 0)
363	continue;
364
365	// This is for function parameters that are split across multiple lines,
366	// as mentioned in the ScopeStack comment.
367	if (InsideNestedScope && CurrentChange.NewlinesBefore > 0) {
368	unsigned ScopeStart = ScopeStack.back();
369	auto ShouldShiftBeAdded = [&] {
370	// Function declaration
371	if (Changes[ScopeStart - 1].Tok->is(TT: TT_FunctionDeclarationName))
372	return true;
373
374	// Lambda.
375	if (Changes[ScopeStart - 1].Tok->is(TT: TT_LambdaLBrace))
376	return false;
377
378	// Continued function declaration
379	if (ScopeStart > Start + 1 &&
380	Changes[ScopeStart - 2].Tok->is(TT: TT_FunctionDeclarationName)) {
381	return true;
382	}
383
384	// Continued (template) function call.
385	if (ScopeStart > Start + 1 &&
386	Changes[ScopeStart - 2].Tok->isOneOf(K1: tok::identifier,
387	K2: TT_TemplateCloser) &&
388	Changes[ScopeStart - 1].Tok->is(Kind: tok::l_paren) &&
389	Changes[ScopeStart].Tok->isNot(Kind: TT_LambdaLSquare)) {
390	if (CurrentChange.Tok->MatchingParen &&
391	CurrentChange.Tok->MatchingParen->is(TT: TT_LambdaLBrace)) {
392	return false;
393	}
394	if (Changes[ScopeStart].NewlinesBefore > 0)
395	return false;
396	if (CurrentChange.Tok->is(Kind: tok::l_brace) &&
397	CurrentChange.Tok->is(BBK: BK_BracedInit)) {
398	return true;
399	}
400	return Style.BinPackArguments;
401	}
402
403	// Ternary operator
404	if (CurrentChange.Tok->is(TT: TT_ConditionalExpr))
405	return true;
406
407	// Period Initializer .XXX = 1.
408	if (CurrentChange.Tok->is(TT: TT_DesignatedInitializerPeriod))
409	return true;
410
411	// Continued ternary operator
412	if (CurrentChange.Tok->Previous &&
413	CurrentChange.Tok->Previous->is(TT: TT_ConditionalExpr)) {
414	return true;
415	}
416
417	// Continued direct-list-initialization using braced list.
418	if (ScopeStart > Start + 1 &&
419	Changes[ScopeStart - 2].Tok->is(Kind: tok::identifier) &&
420	Changes[ScopeStart - 1].Tok->is(Kind: tok::l_brace) &&
421	CurrentChange.Tok->is(Kind: tok::l_brace) &&
422	CurrentChange.Tok->is(BBK: BK_BracedInit)) {
423	return true;
424	}
425
426	// Continued braced list.
427	if (ScopeStart > Start + 1 &&
428	Changes[ScopeStart - 2].Tok->isNot(Kind: tok::identifier) &&
429	Changes[ScopeStart - 1].Tok->is(Kind: tok::l_brace) &&
430	CurrentChange.Tok->isNot(Kind: tok::r_brace)) {
431	for (unsigned OuterScopeStart : llvm::reverse(C&: ScopeStack)) {
432	// Lambda.
433	if (OuterScopeStart > Start &&
434	Changes[OuterScopeStart - 1].Tok->is(TT: TT_LambdaLBrace)) {
435	return false;
436	}
437	}
438	if (Changes[ScopeStart].NewlinesBefore > 0)
439	return false;
440	return true;
441	}
442
443	// Continued template parameter.
444	if (Changes[ScopeStart - 1].Tok->is(TT: TT_TemplateOpener))
445	return true;
446
447	return false;
448	};
449
450	if (ShouldShiftBeAdded())
451	CurrentChange.Spaces += Shift;
452	}
453
454	if (ContinuedStringLiteral)
455	CurrentChange.Spaces += Shift;
456
457	// We should not remove required spaces unless we break the line before.
458	assert(Shift > 0 || Changes[i].NewlinesBefore > 0 ||
459	CurrentChange.Spaces >=
460	static_cast<int>(Changes[i].Tok->SpacesRequiredBefore) ||
461	CurrentChange.Tok->is(tok::eof));
462
463	CurrentChange.StartOfTokenColumn += Shift;
464	if (i + 1 != Changes.size())
465	Changes[i + 1].PreviousEndOfTokenColumn += Shift;
466
467	// If PointerAlignment is PAS_Right, keep *s or &s next to the token,
468	// except if the token is equal, then a space is needed.
469	if ((Style.PointerAlignment == FormatStyle::PAS_Right ||
470	Style.ReferenceAlignment == FormatStyle::RAS_Right) &&
471	CurrentChange.Spaces != 0 && CurrentChange.Tok->isNot(Kind: tok::equal)) {
472	const bool ReferenceNotRightAligned =
473	Style.ReferenceAlignment != FormatStyle::RAS_Right &&
474	Style.ReferenceAlignment != FormatStyle::RAS_Pointer;
475	for (int Previous = i - 1;
476	Previous >= 0 && Changes[Previous].Tok->is(TT: TT_PointerOrReference);
477	--Previous) {
478	assert(Changes[Previous].Tok->isPointerOrReference());
479	if (Changes[Previous].Tok->isNot(Kind: tok::star)) {
480	if (ReferenceNotRightAligned)
481	continue;
482	} else if (Style.PointerAlignment != FormatStyle::PAS_Right) {
483	continue;
484	}
485	Changes[Previous + 1].Spaces -= Shift;
486	Changes[Previous].Spaces += Shift;
487	Changes[Previous].StartOfTokenColumn += Shift;
488	}
489	}
490	}
491	}
492
493	// Walk through a subset of the changes, starting at StartAt, and find
494	// sequences of matching tokens to align. To do so, keep track of the lines and
495	// whether or not a matching token was found on a line. If a matching token is
496	// found, extend the current sequence. If the current line cannot be part of a
497	// sequence, e.g. because there is an empty line before it or it contains only
498	// non-matching tokens, finalize the previous sequence.
499	// The value returned is the token on which we stopped, either because we
500	// exhausted all items inside Changes, or because we hit a scope level higher
501	// than our initial scope.
502	// This function is recursive. Each invocation processes only the scope level
503	// equal to the initial level, which is the level of Changes[StartAt].
504	// If we encounter a scope level greater than the initial level, then we call
505	// ourselves recursively, thereby avoiding the pollution of the current state
506	// with the alignment requirements of the nested sub-level. This recursive
507	// behavior is necessary for aligning function prototypes that have one or more
508	// arguments.
509	// If this function encounters a scope level less than the initial level,
510	// it returns the current position.
511	// There is a non-obvious subtlety in the recursive behavior: Even though we
512	// defer processing of nested levels to recursive invocations of this
513	// function, when it comes time to align a sequence of tokens, we run the
514	// alignment on the entire sequence, including the nested levels.
515	// When doing so, most of the nested tokens are skipped, because their
516	// alignment was already handled by the recursive invocations of this function.
517	// However, the special exception is that we do NOT skip function parameters
518	// that are split across multiple lines. See the test case in FormatTest.cpp
519	// that mentions "split function parameter alignment" for an example of this.
520	// When the parameter RightJustify is true, the operator will be
521	// right-justified. It is used to align compound assignments like `+=` and `=`.
522	// When RightJustify and ACS.PadOperators are true, operators in each block to
523	// be aligned will be padded on the left to the same length before aligning.
524	template <typename F>
525	static unsigned AlignTokens(const FormatStyle &Style, F &&Matches,
526	SmallVector<WhitespaceManager::Change, 16> &Changes,
527	unsigned StartAt,
528	const FormatStyle::AlignConsecutiveStyle &ACS = {},
529	bool RightJustify = false) {
530	// We arrange each line in 3 parts. The operator to be aligned (the anchor),
531	// and text to its left and right. In the aligned text the width of each part
532	// will be the maximum of that over the block that has been aligned. Maximum
533	// widths of each part so far. When RightJustify is true and ACS.PadOperators
534	// is false, the part from start of line to the right end of the anchor.
535	// Otherwise, only the part to the left of the anchor. Including the space
536	// that exists on its left from the start. Not including the padding added on
537	// the left to right-justify the anchor.
538	unsigned WidthLeft = 0;
539	// The operator to be aligned when RightJustify is true and ACS.PadOperators
540	// is false. 0 otherwise.
541	unsigned WidthAnchor = 0;
542	// Width to the right of the anchor. Plus width of the anchor when
543	// RightJustify is false.
544	unsigned WidthRight = 0;
545
546	// Line number of the start and the end of the current token sequence.
547	unsigned StartOfSequence = 0;
548	unsigned EndOfSequence = 0;
549
550	// Measure the scope level (i.e. depth of (), [], {}) of the first token, and
551	// abort when we hit any token in a higher scope than the starting one.
552	auto IndentAndNestingLevel = StartAt < Changes.size()
553	? Changes[StartAt].indentAndNestingLevel()
554	: std::tuple<unsigned, unsigned, unsigned>();
555
556	// Keep track of the number of commas before the matching tokens, we will only
557	// align a sequence of matching tokens if they are preceded by the same number
558	// of commas.
559	unsigned CommasBeforeLastMatch = 0;
560	unsigned CommasBeforeMatch = 0;
561
562	// Whether a matching token has been found on the current line.
563	bool FoundMatchOnLine = false;
564
565	// Whether the current line consists purely of comments.
566	bool LineIsComment = true;
567
568	// Aligns a sequence of matching tokens, on the MinColumn column.
569	//
570	// Sequences start from the first matching token to align, and end at the
571	// first token of the first line that doesn't need to be aligned.
572	//
573	// We need to adjust the StartOfTokenColumn of each Change that is on a line
574	// containing any matching token to be aligned and located after such token.
575	auto AlignCurrentSequence = [&] {
576	if (StartOfSequence > 0 && StartOfSequence < EndOfSequence) {
577	AlignTokenSequence(Style, StartOfSequence, EndOfSequence,
578	WidthLeft + WidthAnchor, RightJustify, Matches,
579	Changes);
580	}
581	WidthLeft = 0;
582	WidthAnchor = 0;
583	WidthRight = 0;
584	StartOfSequence = 0;
585	EndOfSequence = 0;
586	};
587
588	unsigned i = StartAt;
589	for (unsigned e = Changes.size(); i != e; ++i) {
590	auto &CurrentChange = Changes[i];
591	if (CurrentChange.indentAndNestingLevel() < IndentAndNestingLevel)
592	break;
593
594	if (CurrentChange.NewlinesBefore != 0) {
595	CommasBeforeMatch = 0;
596	EndOfSequence = i;
597
598	// Whether to break the alignment sequence because of an empty line.
599	bool EmptyLineBreak =
600	(CurrentChange.NewlinesBefore > 1) && !ACS.AcrossEmptyLines;
601
602	// Whether to break the alignment sequence because of a line without a
603	// match.
604	bool NoMatchBreak =
605	!FoundMatchOnLine && !(LineIsComment && ACS.AcrossComments);
606
607	if (EmptyLineBreak || NoMatchBreak)
608	AlignCurrentSequence();
609
610	// A new line starts, re-initialize line status tracking bools.
611	// Keep the match state if a string literal is continued on this line.
612	if (i == 0 || CurrentChange.Tok->isNot(Kind: tok::string_literal) ||
613	Changes[i - 1].Tok->isNot(Kind: tok::string_literal)) {
614	FoundMatchOnLine = false;
615	}
616	LineIsComment = true;
617	}
618
619	if (CurrentChange.Tok->isNot(Kind: tok::comment))
620	LineIsComment = false;
621
622	if (CurrentChange.Tok->is(Kind: tok::comma)) {
623	++CommasBeforeMatch;
624	} else if (CurrentChange.indentAndNestingLevel() > IndentAndNestingLevel) {
625	// Call AlignTokens recursively, skipping over this scope block.
626	unsigned StoppedAt =
627	AlignTokens(Style, Matches, Changes, i, ACS, RightJustify);
628	i = StoppedAt - 1;
629	continue;
630	}
631
632	if (!Matches(CurrentChange))
633	continue;
634
635	// If there is more than one matching token per line, or if the number of
636	// preceding commas, do not match anymore, end the sequence.
637	if (FoundMatchOnLine || CommasBeforeMatch != CommasBeforeLastMatch)
638	AlignCurrentSequence();
639
640	CommasBeforeLastMatch = CommasBeforeMatch;
641	FoundMatchOnLine = true;
642
643	if (StartOfSequence == 0)
644	StartOfSequence = i;
645
646	unsigned ChangeWidthLeft = CurrentChange.StartOfTokenColumn;
647	unsigned ChangeWidthAnchor = 0;
648	unsigned ChangeWidthRight = 0;
649	if (RightJustify)
650	if (ACS.PadOperators)
651	ChangeWidthAnchor = CurrentChange.TokenLength;
652	else
653	ChangeWidthLeft += CurrentChange.TokenLength;
654	else
655	ChangeWidthRight = CurrentChange.TokenLength;
656	for (unsigned j = i + 1; j != e && Changes[j].NewlinesBefore == 0; ++j) {
657	ChangeWidthRight += Changes[j].Spaces;
658	// Changes are generally 1:1 with the tokens, but a change could also be
659	// inside of a token, in which case it's counted more than once: once for
660	// the whitespace surrounding the token (!IsInsideToken) and once for
661	// each whitespace change within it (IsInsideToken).
662	// Therefore, changes inside of a token should only count the space.
663	if (!Changes[j].IsInsideToken)
664	ChangeWidthRight += Changes[j].TokenLength;
665	}
666
667	// If we are restricted by the maximum column width, end the sequence.
668	unsigned NewLeft = std::max(a: ChangeWidthLeft, b: WidthLeft);
669	unsigned NewAnchor = std::max(a: ChangeWidthAnchor, b: WidthAnchor);
670	unsigned NewRight = std::max(a: ChangeWidthRight, b: WidthRight);
671	// `ColumnLimit == 0` means there is no column limit.
672	if (Style.ColumnLimit != 0 &&
673	Style.ColumnLimit < NewLeft + NewAnchor + NewRight) {
674	AlignCurrentSequence();
675	StartOfSequence = i;
676	WidthLeft = ChangeWidthLeft;
677	WidthAnchor = ChangeWidthAnchor;
678	WidthRight = ChangeWidthRight;
679	} else {
680	WidthLeft = NewLeft;
681	WidthAnchor = NewAnchor;
682	WidthRight = NewRight;
683	}
684	}
685
686	EndOfSequence = i;
687	AlignCurrentSequence();
688	return i;
689	}
690
691	// Aligns a sequence of matching tokens, on the MinColumn column.
692	//
693	// Sequences start from the first matching token to align, and end at the
694	// first token of the first line that doesn't need to be aligned.
695	//
696	// We need to adjust the StartOfTokenColumn of each Change that is on a line
697	// containing any matching token to be aligned and located after such token.
698	static void AlignMatchingTokenSequence(
699	unsigned &StartOfSequence, unsigned &EndOfSequence, unsigned &MinColumn,
700	std::function<bool(const WhitespaceManager::Change &C)> Matches,
701	SmallVector<WhitespaceManager::Change, 16> &Changes) {
702	if (StartOfSequence > 0 && StartOfSequence < EndOfSequence) {
703	bool FoundMatchOnLine = false;
704	int Shift = 0;
705
706	for (unsigned I = StartOfSequence; I != EndOfSequence; ++I) {
707	if (Changes[I].NewlinesBefore > 0) {
708	Shift = 0;
709	FoundMatchOnLine = false;
710	}
711
712	// If this is the first matching token to be aligned, remember by how many
713	// spaces it has to be shifted, so the rest of the changes on the line are
714	// shifted by the same amount.
715	if (!FoundMatchOnLine && Matches(Changes[I])) {
716	FoundMatchOnLine = true;
717	Shift = MinColumn - Changes[I].StartOfTokenColumn;
718	Changes[I].Spaces += Shift;
719	}
720
721	assert(Shift >= 0);
722	Changes[I].StartOfTokenColumn += Shift;
723	if (I + 1 != Changes.size())
724	Changes[I + 1].PreviousEndOfTokenColumn += Shift;
725	}
726	}
727
728	MinColumn = 0;
729	StartOfSequence = 0;
730	EndOfSequence = 0;
731	}
732
733	void WhitespaceManager::alignConsecutiveMacros() {
734	if (!Style.AlignConsecutiveMacros.Enabled)
735	return;
736
737	auto AlignMacrosMatches = [](const Change &C) {
738	const FormatToken *Current = C.Tok;
739	unsigned SpacesRequiredBefore = 1;
740
741	if (Current->SpacesRequiredBefore == 0 || !Current->Previous)
742	return false;
743
744	Current = Current->Previous;
745
746	// If token is a ")", skip over the parameter list, to the
747	// token that precedes the "("
748	if (Current->is(Kind: tok::r_paren) && Current->MatchingParen) {
749	Current = Current->MatchingParen->Previous;
750	SpacesRequiredBefore = 0;
751	}
752
753	if (!Current || Current->isNot(Kind: tok::identifier))
754	return false;
755
756	if (!Current->Previous || Current->Previous->isNot(Kind: tok::pp_define))
757	return false;
758
759	// For a macro function, 0 spaces are required between the
760	// identifier and the lparen that opens the parameter list.
761	// For a simple macro, 1 space is required between the
762	// identifier and the first token of the defined value.
763	return Current->Next->SpacesRequiredBefore == SpacesRequiredBefore;
764	};
765
766	unsigned MinColumn = 0;
767
768	// Start and end of the token sequence we're processing.
769	unsigned StartOfSequence = 0;
770	unsigned EndOfSequence = 0;
771
772	// Whether a matching token has been found on the current line.
773	bool FoundMatchOnLine = false;
774
775	// Whether the current line consists only of comments
776	bool LineIsComment = true;
777
778	unsigned I = 0;
779	for (unsigned E = Changes.size(); I != E; ++I) {
780	if (Changes[I].NewlinesBefore != 0) {
781	EndOfSequence = I;
782
783	// Whether to break the alignment sequence because of an empty line.
784	bool EmptyLineBreak = (Changes[I].NewlinesBefore > 1) &&
785	!Style.AlignConsecutiveMacros.AcrossEmptyLines;
786
787	// Whether to break the alignment sequence because of a line without a
788	// match.
789	bool NoMatchBreak =
790	!FoundMatchOnLine &&
791	!(LineIsComment && Style.AlignConsecutiveMacros.AcrossComments);
792
793	if (EmptyLineBreak || NoMatchBreak) {
794	AlignMatchingTokenSequence(StartOfSequence, EndOfSequence, MinColumn,
795	Matches: AlignMacrosMatches, Changes);
796	}
797
798	// A new line starts, re-initialize line status tracking bools.
799	FoundMatchOnLine = false;
800	LineIsComment = true;
801	}
802
803	if (Changes[I].Tok->isNot(Kind: tok::comment))
804	LineIsComment = false;
805
806	if (!AlignMacrosMatches(Changes[I]))
807	continue;
808
809	FoundMatchOnLine = true;
810
811	if (StartOfSequence == 0)
812	StartOfSequence = I;
813
814	unsigned ChangeMinColumn = Changes[I].StartOfTokenColumn;
815	MinColumn = std::max(a: MinColumn, b: ChangeMinColumn);
816	}
817
818	EndOfSequence = I;
819	AlignMatchingTokenSequence(StartOfSequence, EndOfSequence, MinColumn,
820	Matches: AlignMacrosMatches, Changes);
821	}
822
823	void WhitespaceManager::alignConsecutiveAssignments() {
824	if (!Style.AlignConsecutiveAssignments.Enabled)
825	return;
826
827	AlignTokens(
828	Style,
829	Matches: [&](const Change &C) {
830	// Do not align on equal signs that are first on a line.
831	if (C.NewlinesBefore > 0)
832	return false;
833
834	// Do not align on equal signs that are last on a line.
835	if (&C != &Changes.back() && (&C + 1)->NewlinesBefore > 0)
836	return false;
837
838	// Do not align operator= overloads.
839	FormatToken *Previous = C.Tok->getPreviousNonComment();
840	if (Previous && Previous->is(Kind: tok::kw_operator))
841	return false;
842
843	return Style.AlignConsecutiveAssignments.AlignCompound
844	? C.Tok->getPrecedence() == prec::Assignment
845	: (C.Tok->is(Kind: tok::equal) ||
846	// In Verilog the '<=' is not a compound assignment, thus
847	// it is aligned even when the AlignCompound option is not
848	// set.
849	(Style.isVerilog() && C.Tok->is(Kind: tok::lessequal) &&
850	C.Tok->getPrecedence() == prec::Assignment));
851	},
852	Changes, /*StartAt=*/0, ACS: Style.AlignConsecutiveAssignments,
853	/*RightJustify=*/true);
854	}
855
856	void WhitespaceManager::alignConsecutiveBitFields() {
857	alignConsecutiveColons(AlignStyle: Style.AlignConsecutiveBitFields, Type: TT_BitFieldColon);
858	}
859
860	void WhitespaceManager::alignConsecutiveColons(
861	const FormatStyle::AlignConsecutiveStyle &AlignStyle, TokenType Type) {
862	if (!AlignStyle.Enabled)
863	return;
864
865	AlignTokens(
866	Style,
867	Matches: [&](Change const &C) {
868	// Do not align on ':' that is first on a line.
869	if (C.NewlinesBefore > 0)
870	return false;
871
872	// Do not align on ':' that is last on a line.
873	if (&C != &Changes.back() && (&C + 1)->NewlinesBefore > 0)
874	return false;
875
876	return C.Tok->is(TT: Type);
877	},
878	Changes, /*StartAt=*/0, ACS: AlignStyle);
879	}
880
881	void WhitespaceManager::alignConsecutiveShortCaseStatements() {
882	if (!Style.AlignConsecutiveShortCaseStatements.Enabled ||
883	!Style.AllowShortCaseLabelsOnASingleLine) {
884	return;
885	}
886
887	auto Matches = [&](const Change &C) {
888	if (Style.AlignConsecutiveShortCaseStatements.AlignCaseColons)
889	return C.Tok->is(TT: TT_CaseLabelColon);
890
891	// Ignore 'IsInsideToken' to allow matching trailing comments which
892	// need to be reflowed as that causes the token to appear in two
893	// different changes, which will cause incorrect alignment as we'll
894	// reflow early due to detecting multiple aligning tokens per line.
895	return !C.IsInsideToken && C.Tok->Previous &&
896	C.Tok->Previous->is(TT: TT_CaseLabelColon);
897	};
898
899	unsigned MinColumn = 0;
900
901	// Empty case statements don't break the alignment, but don't necessarily
902	// match our predicate, so we need to track their column so they can push out
903	// our alignment.
904	unsigned MinEmptyCaseColumn = 0;
905
906	// Start and end of the token sequence we're processing.
907	unsigned StartOfSequence = 0;
908	unsigned EndOfSequence = 0;
909
910	// Whether a matching token has been found on the current line.
911	bool FoundMatchOnLine = false;
912
913	bool LineIsComment = true;
914	bool LineIsEmptyCase = false;
915
916	unsigned I = 0;
917	for (unsigned E = Changes.size(); I != E; ++I) {
918	if (Changes[I].NewlinesBefore != 0) {
919	// Whether to break the alignment sequence because of an empty line.
920	bool EmptyLineBreak =
921	(Changes[I].NewlinesBefore > 1) &&
922	!Style.AlignConsecutiveShortCaseStatements.AcrossEmptyLines;
923
924	// Whether to break the alignment sequence because of a line without a
925	// match.
926	bool NoMatchBreak =
927	!FoundMatchOnLine &&
928	!(LineIsComment &&
929	Style.AlignConsecutiveShortCaseStatements.AcrossComments) &&
930	!LineIsEmptyCase;
931
932	if (EmptyLineBreak || NoMatchBreak) {
933	AlignMatchingTokenSequence(StartOfSequence, EndOfSequence, MinColumn,
934	Matches, Changes);
935	MinEmptyCaseColumn = 0;
936	}
937
938	// A new line starts, re-initialize line status tracking bools.
939	FoundMatchOnLine = false;
940	LineIsComment = true;
941	LineIsEmptyCase = false;
942	}
943
944	if (Changes[I].Tok->isNot(Kind: tok::comment))
945	LineIsComment = false;
946
947	if (Changes[I].Tok->is(TT: TT_CaseLabelColon)) {
948	LineIsEmptyCase =
949	!Changes[I].Tok->Next || Changes[I].Tok->Next->isTrailingComment();
950
951	if (LineIsEmptyCase) {
952	if (Style.AlignConsecutiveShortCaseStatements.AlignCaseColons) {
953	MinEmptyCaseColumn =
954	std::max(a: MinEmptyCaseColumn, b: Changes[I].StartOfTokenColumn);
955	} else {
956	MinEmptyCaseColumn =
957	std::max(a: MinEmptyCaseColumn, b: Changes[I].StartOfTokenColumn + 2);
958	}
959	}
960	}
961
962	if (!Matches(Changes[I]))
963	continue;
964
965	if (LineIsEmptyCase)
966	continue;
967
968	FoundMatchOnLine = true;
969
970	if (StartOfSequence == 0)
971	StartOfSequence = I;
972
973	EndOfSequence = I + 1;
974
975	MinColumn = std::max(a: MinColumn, b: Changes[I].StartOfTokenColumn);
976
977	// Allow empty case statements to push out our alignment.
978	MinColumn = std::max(a: MinColumn, b: MinEmptyCaseColumn);
979	}
980
981	AlignMatchingTokenSequence(StartOfSequence, EndOfSequence, MinColumn, Matches,
982	Changes);
983	}
984
985	void WhitespaceManager::alignConsecutiveTableGenBreakingDAGArgColons() {
986	alignConsecutiveColons(AlignStyle: Style.AlignConsecutiveTableGenBreakingDAGArgColons,
987	Type: TT_TableGenDAGArgListColonToAlign);
988	}
989
990	void WhitespaceManager::alignConsecutiveTableGenCondOperatorColons() {
991	alignConsecutiveColons(AlignStyle: Style.AlignConsecutiveTableGenCondOperatorColons,
992	Type: TT_TableGenCondOperatorColon);
993	}
994
995	void WhitespaceManager::alignConsecutiveTableGenDefinitions() {
996	alignConsecutiveColons(AlignStyle: Style.AlignConsecutiveTableGenDefinitionColons,
997	Type: TT_InheritanceColon);
998	}
999
1000	void WhitespaceManager::alignConsecutiveDeclarations() {
1001	if (!Style.AlignConsecutiveDeclarations.Enabled)
1002	return;
1003
1004	AlignTokens(
1005	Style,
1006	Matches: [&](Change const &C) {
1007	if (Style.AlignConsecutiveDeclarations.AlignFunctionPointers) {
1008	for (const auto *Prev = C.Tok->Previous; Prev; Prev = Prev->Previous)
1009	if (Prev->is(Kind: tok::equal))
1010	return false;
1011	if (C.Tok->is(TT: TT_FunctionTypeLParen))
1012	return true;
1013	}
1014	if (C.Tok->is(TT: TT_FunctionDeclarationName))
1015	return true;
1016	if (C.Tok->isNot(Kind: TT_StartOfName))
1017	return false;
1018	if (C.Tok->Previous &&
1019	C.Tok->Previous->is(TT: TT_StatementAttributeLikeMacro))
1020	return false;
1021	// Check if there is a subsequent name that starts the same declaration.
1022	for (FormatToken *Next = C.Tok->Next; Next; Next = Next->Next) {
1023	if (Next->is(Kind: tok::comment))
1024	continue;
1025	if (Next->is(TT: TT_PointerOrReference))
1026	return false;
1027	if (!Next->Tok.getIdentifierInfo())
1028	break;
1029	if (Next->isOneOf(K1: TT_StartOfName, K2: TT_FunctionDeclarationName,
1030	Ks: tok::kw_operator)) {
1031	return false;
1032	}
1033	}
1034	return true;
1035	},
1036	Changes, /*StartAt=*/0, ACS: Style.AlignConsecutiveDeclarations);
1037	}
1038
1039	void WhitespaceManager::alignChainedConditionals() {
1040	if (Style.BreakBeforeTernaryOperators) {
1041	AlignTokens(
1042	Style,
1043	Matches: [](Change const &C) {
1044	// Align question operators and last colon
1045	return C.Tok->is(TT: TT_ConditionalExpr) &&
1046	((C.Tok->is(Kind: tok::question) && !C.NewlinesBefore) ||
1047	(C.Tok->is(Kind: tok::colon) && C.Tok->Next &&
1048	(C.Tok->Next->FakeLParens.size() == 0 ||
1049	C.Tok->Next->FakeLParens.back() != prec::Conditional)));
1050	},
1051	Changes, /*StartAt=*/0);
1052	} else {
1053	static auto AlignWrappedOperand = [](Change const &C) {
1054	FormatToken *Previous = C.Tok->getPreviousNonComment();
1055	return C.NewlinesBefore && Previous && Previous->is(TT: TT_ConditionalExpr) &&
1056	(Previous->is(Kind: tok::colon) &&
1057	(C.Tok->FakeLParens.size() == 0 ||
1058	C.Tok->FakeLParens.back() != prec::Conditional));
1059	};
1060	// Ensure we keep alignment of wrapped operands with non-wrapped operands
1061	// Since we actually align the operators, the wrapped operands need the
1062	// extra offset to be properly aligned.
1063	for (Change &C : Changes)
1064	if (AlignWrappedOperand(C))
1065	C.StartOfTokenColumn -= 2;
1066	AlignTokens(
1067	Style,
1068	Matches: [this](Change const &C) {
1069	// Align question operators if next operand is not wrapped, as
1070	// well as wrapped operands after question operator or last
1071	// colon in conditional sequence
1072	return (C.Tok->is(TT: TT_ConditionalExpr) && C.Tok->is(Kind: tok::question) &&
1073	&C != &Changes.back() && (&C + 1)->NewlinesBefore == 0 &&
1074	!(&C + 1)->IsTrailingComment) ||
1075	AlignWrappedOperand(C);
1076	},
1077	Changes, /*StartAt=*/0);
1078	}
1079	}
1080
1081	void WhitespaceManager::alignTrailingComments() {
1082	if (Style.AlignTrailingComments.Kind == FormatStyle::TCAS_Never)
1083	return;
1084
1085	const int Size = Changes.size();
1086	int MinColumn = 0;
1087	int StartOfSequence = 0;
1088	bool BreakBeforeNext = false;
1089	int NewLineThreshold = 1;
1090	if (Style.AlignTrailingComments.Kind == FormatStyle::TCAS_Always)
1091	NewLineThreshold = Style.AlignTrailingComments.OverEmptyLines + 1;
1092
1093	for (int I = 0, MaxColumn = INT_MAX, Newlines = 0; I < Size; ++I) {
1094	auto &C = Changes[I];
1095	if (C.StartOfBlockComment)
1096	continue;
1097	Newlines += C.NewlinesBefore;
1098	if (!C.IsTrailingComment)
1099	continue;
1100
1101	if (Style.AlignTrailingComments.Kind == FormatStyle::TCAS_Leave) {
1102	const int OriginalSpaces =
1103	C.OriginalWhitespaceRange.getEnd().getRawEncoding() -
1104	C.OriginalWhitespaceRange.getBegin().getRawEncoding() -
1105	C.Tok->LastNewlineOffset;
1106	assert(OriginalSpaces >= 0);
1107	const auto RestoredLineLength =
1108	C.StartOfTokenColumn + C.TokenLength + OriginalSpaces;
1109	// If leaving comments makes the line exceed the column limit, give up to
1110	// leave the comments.
1111	if (RestoredLineLength >= Style.ColumnLimit && Style.ColumnLimit > 0)
1112	break;
1113	C.Spaces = OriginalSpaces;
1114	continue;
1115	}
1116
1117	const int ChangeMinColumn = C.StartOfTokenColumn;
1118	int ChangeMaxColumn;
1119
1120	// If we don't create a replacement for this change, we have to consider
1121	// it to be immovable.
1122	if (!C.CreateReplacement)
1123	ChangeMaxColumn = ChangeMinColumn;
1124	else if (Style.ColumnLimit == 0)
1125	ChangeMaxColumn = INT_MAX;
1126	else if (Style.ColumnLimit >= C.TokenLength)
1127	ChangeMaxColumn = Style.ColumnLimit - C.TokenLength;
1128	else
1129	ChangeMaxColumn = ChangeMinColumn;
1130
1131	if (I + 1 < Size && Changes[I + 1].ContinuesPPDirective &&
1132	ChangeMaxColumn >= 2) {
1133	ChangeMaxColumn -= 2;
1134	}
1135
1136	bool WasAlignedWithStartOfNextLine = false;
1137	if (C.NewlinesBefore >= 1) { // A comment on its own line.
1138	const auto CommentColumn =
1139	SourceMgr.getSpellingColumnNumber(Loc: C.OriginalWhitespaceRange.getEnd());
1140	for (int J = I + 1; J < Size; ++J) {
1141	if (Changes[J].Tok->is(Kind: tok::comment))
1142	continue;
1143
1144	const auto NextColumn = SourceMgr.getSpellingColumnNumber(
1145	Loc: Changes[J].OriginalWhitespaceRange.getEnd());
1146	// The start of the next token was previously aligned with the
1147	// start of this comment.
1148	WasAlignedWithStartOfNextLine =
1149	CommentColumn == NextColumn ||
1150	CommentColumn == NextColumn + Style.IndentWidth;
1151	break;
1152	}
1153	}
1154
1155	// We don't want to align comments which end a scope, which are here
1156	// identified by most closing braces.
1157	auto DontAlignThisComment = [](const auto *Tok) {
1158	if (Tok->is(tok::semi)) {
1159	Tok = Tok->getPreviousNonComment();
1160	if (!Tok)
1161	return false;
1162	}
1163	if (Tok->is(tok::r_paren)) {
1164	// Back up past the parentheses and a `TT_DoWhile` that may precede.
1165	Tok = Tok->MatchingParen;
1166	if (!Tok)
1167	return false;
1168	Tok = Tok->getPreviousNonComment();
1169	if (!Tok)
1170	return false;
1171	if (Tok->is(TT_DoWhile)) {
1172	const auto *Prev = Tok->getPreviousNonComment();
1173	if (!Prev) {
1174	// A do-while-loop without braces.
1175	return true;
1176	}
1177	Tok = Prev;
1178	}
1179	}
1180
1181	if (Tok->isNot(tok::r_brace))
1182	return false;
1183
1184	while (Tok->Previous && Tok->Previous->is(tok::r_brace))
1185	Tok = Tok->Previous;
1186	return Tok->NewlinesBefore > 0;
1187	};
1188
1189	if (I > 0 && C.NewlinesBefore == 0 &&
1190	DontAlignThisComment(Changes[I - 1].Tok)) {
1191	alignTrailingComments(Start: StartOfSequence, End: I, Column: MinColumn);
1192	// Reset to initial values, but skip this change for the next alignment
1193	// pass.
1194	MinColumn = 0;
1195	MaxColumn = INT_MAX;
1196	StartOfSequence = I + 1;
1197	} else if (BreakBeforeNext || Newlines > NewLineThreshold ||
1198	(ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn) ||
1199	// Break the comment sequence if the previous line did not end
1200	// in a trailing comment.
1201	(C.NewlinesBefore == 1 && I > 0 &&
1202	!Changes[I - 1].IsTrailingComment) ||
1203	WasAlignedWithStartOfNextLine) {
1204	alignTrailingComments(Start: StartOfSequence, End: I, Column: MinColumn);
1205	MinColumn = ChangeMinColumn;
1206	MaxColumn = ChangeMaxColumn;
1207	StartOfSequence = I;
1208	} else {
1209	MinColumn = std::max(a: MinColumn, b: ChangeMinColumn);
1210	MaxColumn = std::min(a: MaxColumn, b: ChangeMaxColumn);
1211	}
1212	BreakBeforeNext = (I == 0) || (C.NewlinesBefore > 1) ||
1213	// Never start a sequence with a comment at the beginning
1214	// of the line.
1215	(C.NewlinesBefore == 1 && StartOfSequence == I);
1216	Newlines = 0;
1217	}
1218	alignTrailingComments(Start: StartOfSequence, End: Size, Column: MinColumn);
1219	}
1220
1221	void WhitespaceManager::alignTrailingComments(unsigned Start, unsigned End,
1222	unsigned Column) {
1223	for (unsigned i = Start; i != End; ++i) {
1224	int Shift = 0;
1225	if (Changes[i].IsTrailingComment)
1226	Shift = Column - Changes[i].StartOfTokenColumn;
1227	if (Changes[i].StartOfBlockComment) {
1228	Shift = Changes[i].IndentationOffset +
1229	Changes[i].StartOfBlockComment->StartOfTokenColumn -
1230	Changes[i].StartOfTokenColumn;
1231	}
1232	if (Shift <= 0)
1233	continue;
1234	Changes[i].Spaces += Shift;
1235	if (i + 1 != Changes.size())
1236	Changes[i + 1].PreviousEndOfTokenColumn += Shift;
1237	Changes[i].StartOfTokenColumn += Shift;
1238	}
1239	}
1240
1241	void WhitespaceManager::alignEscapedNewlines() {
1242	if (Style.AlignEscapedNewlines == FormatStyle::ENAS_DontAlign)
1243	return;
1244
1245	bool AlignLeft = Style.AlignEscapedNewlines == FormatStyle::ENAS_Left;
1246	unsigned MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
1247	unsigned StartOfMacro = 0;
1248	for (unsigned i = 1, e = Changes.size(); i < e; ++i) {
1249	Change &C = Changes[i];
1250	if (C.NewlinesBefore > 0) {
1251	if (C.ContinuesPPDirective) {
1252	MaxEndOfLine = std::max(a: C.PreviousEndOfTokenColumn + 2, b: MaxEndOfLine);
1253	} else {
1254	alignEscapedNewlines(Start: StartOfMacro + 1, End: i, Column: MaxEndOfLine);
1255	MaxEndOfLine = AlignLeft ? 0 : Style.ColumnLimit;
1256	StartOfMacro = i;
1257	}
1258	}
1259	}
1260	alignEscapedNewlines(Start: StartOfMacro + 1, End: Changes.size(), Column: MaxEndOfLine);
1261	}
1262
1263	void WhitespaceManager::alignEscapedNewlines(unsigned Start, unsigned End,
1264	unsigned Column) {
1265	for (unsigned i = Start; i < End; ++i) {
1266	Change &C = Changes[i];
1267	if (C.NewlinesBefore > 0) {
1268	assert(C.ContinuesPPDirective);
1269	if (C.PreviousEndOfTokenColumn + 1 > Column)
1270	C.EscapedNewlineColumn = 0;
1271	else
1272	C.EscapedNewlineColumn = Column;
1273	}
1274	}
1275	}
1276
1277	void WhitespaceManager::alignArrayInitializers() {
1278	if (Style.AlignArrayOfStructures == FormatStyle::AIAS_None)
1279	return;
1280
1281	for (unsigned ChangeIndex = 1U, ChangeEnd = Changes.size();
1282	ChangeIndex < ChangeEnd; ++ChangeIndex) {
1283	auto &C = Changes[ChangeIndex];
1284	if (C.Tok->IsArrayInitializer) {
1285	bool FoundComplete = false;
1286	for (unsigned InsideIndex = ChangeIndex + 1; InsideIndex < ChangeEnd;
1287	++InsideIndex) {
1288	if (Changes[InsideIndex].Tok == C.Tok->MatchingParen) {
1289	alignArrayInitializers(Start: ChangeIndex, End: InsideIndex + 1);
1290	ChangeIndex = InsideIndex + 1;
1291	FoundComplete = true;
1292	break;
1293	}
1294	}
1295	if (!FoundComplete)
1296	ChangeIndex = ChangeEnd;
1297	}
1298	}
1299	}
1300
1301	void WhitespaceManager::alignArrayInitializers(unsigned Start, unsigned End) {
1302
1303	if (Style.AlignArrayOfStructures == FormatStyle::AIAS_Right)
1304	alignArrayInitializersRightJustified(CellDescs: getCells(Start, End));
1305	else if (Style.AlignArrayOfStructures == FormatStyle::AIAS_Left)
1306	alignArrayInitializersLeftJustified(CellDescs: getCells(Start, End));
1307	}
1308
1309	void WhitespaceManager::alignArrayInitializersRightJustified(
1310	CellDescriptions &&CellDescs) {
1311	if (!CellDescs.isRectangular())
1312	return;
1313
1314	const int BracePadding = Style.Cpp11BracedListStyle ? 0 : 1;
1315	auto &Cells = CellDescs.Cells;
1316	// Now go through and fixup the spaces.
1317	auto *CellIter = Cells.begin();
1318	for (auto i = 0U; i < CellDescs.CellCounts[0]; ++i, ++CellIter) {
1319	unsigned NetWidth = 0U;
1320	if (isSplitCell(Cell: *CellIter))
1321	NetWidth = getNetWidth(Start: Cells.begin(), End: CellIter, InitialSpaces: CellDescs.InitialSpaces);
1322	auto CellWidth = getMaximumCellWidth(CellIter, NetWidth);
1323
1324	if (Changes[CellIter->Index].Tok->is(Kind: tok::r_brace)) {
1325	// So in here we want to see if there is a brace that falls
1326	// on a line that was split. If so on that line we make sure that
1327	// the spaces in front of the brace are enough.
1328	const auto *Next = CellIter;
1329	do {
1330	const FormatToken *Previous = Changes[Next->Index].Tok->Previous;
1331	if (Previous && Previous->isNot(Kind: TT_LineComment)) {
1332	Changes[Next->Index].Spaces = BracePadding;
1333	Changes[Next->Index].NewlinesBefore = 0;
1334	}
1335	Next = Next->NextColumnElement;
1336	} while (Next);
1337	// Unless the array is empty, we need the position of all the
1338	// immediately adjacent cells
1339	if (CellIter != Cells.begin()) {
1340	auto ThisNetWidth =
1341	getNetWidth(Start: Cells.begin(), End: CellIter, InitialSpaces: CellDescs.InitialSpaces);
1342	auto MaxNetWidth = getMaximumNetWidth(
1343	CellStart: Cells.begin(), CellStop: CellIter, InitialSpaces: CellDescs.InitialSpaces,
1344	CellCount: CellDescs.CellCounts[0], MaxRowCount: CellDescs.CellCounts.size());
1345	if (ThisNetWidth < MaxNetWidth)
1346	Changes[CellIter->Index].Spaces = (MaxNetWidth - ThisNetWidth);
1347	auto RowCount = 1U;
1348	auto Offset = std::distance(first: Cells.begin(), last: CellIter);
1349	for (const auto *Next = CellIter->NextColumnElement; Next;
1350	Next = Next->NextColumnElement) {
1351	if (RowCount >= CellDescs.CellCounts.size())
1352	break;
1353	auto *Start = (Cells.begin() + RowCount * CellDescs.CellCounts[0]);
1354	auto *End = Start + Offset;
1355	ThisNetWidth = getNetWidth(Start, End, InitialSpaces: CellDescs.InitialSpaces);
1356	if (ThisNetWidth < MaxNetWidth)
1357	Changes[Next->Index].Spaces = (MaxNetWidth - ThisNetWidth);
1358	++RowCount;
1359	}
1360	}
1361	} else {
1362	auto ThisWidth =
1363	calculateCellWidth(Start: CellIter->Index, End: CellIter->EndIndex, WithSpaces: true) +
1364	NetWidth;
1365	if (Changes[CellIter->Index].NewlinesBefore == 0) {
1366	Changes[CellIter->Index].Spaces = (CellWidth - (ThisWidth + NetWidth));
1367	Changes[CellIter->Index].Spaces += (i > 0) ? 1 : BracePadding;
1368	}
1369	alignToStartOfCell(Start: CellIter->Index, End: CellIter->EndIndex);
1370	for (const auto *Next = CellIter->NextColumnElement; Next;
1371	Next = Next->NextColumnElement) {
1372	ThisWidth =
1373	calculateCellWidth(Start: Next->Index, End: Next->EndIndex, WithSpaces: true) + NetWidth;
1374	if (Changes[Next->Index].NewlinesBefore == 0) {
1375	Changes[Next->Index].Spaces = (CellWidth - ThisWidth);
1376	Changes[Next->Index].Spaces += (i > 0) ? 1 : BracePadding;
1377	}
1378	alignToStartOfCell(Start: Next->Index, End: Next->EndIndex);
1379	}
1380	}
1381	}
1382	}
1383
1384	void WhitespaceManager::alignArrayInitializersLeftJustified(
1385	CellDescriptions &&CellDescs) {
1386
1387	if (!CellDescs.isRectangular())
1388	return;
1389
1390	const int BracePadding = Style.Cpp11BracedListStyle ? 0 : 1;
1391	auto &Cells = CellDescs.Cells;
1392	// Now go through and fixup the spaces.
1393	auto *CellIter = Cells.begin();
1394	// The first cell of every row needs to be against the left brace.
1395	for (const auto *Next = CellIter; Next; Next = Next->NextColumnElement) {
1396	auto &Change = Changes[Next->Index];
1397	Change.Spaces =
1398	Change.NewlinesBefore == 0 ? BracePadding : CellDescs.InitialSpaces;
1399	}
1400	++CellIter;
1401	for (auto i = 1U; i < CellDescs.CellCounts[0]; i++, ++CellIter) {
1402	auto MaxNetWidth = getMaximumNetWidth(
1403	CellStart: Cells.begin(), CellStop: CellIter, InitialSpaces: CellDescs.InitialSpaces,
1404	CellCount: CellDescs.CellCounts[0], MaxRowCount: CellDescs.CellCounts.size());
1405	auto ThisNetWidth =
1406	getNetWidth(Start: Cells.begin(), End: CellIter, InitialSpaces: CellDescs.InitialSpaces);
1407	if (Changes[CellIter->Index].NewlinesBefore == 0) {
1408	Changes[CellIter->Index].Spaces =
1409	MaxNetWidth - ThisNetWidth +
1410	(Changes[CellIter->Index].Tok->isNot(Kind: tok::r_brace) ? 1
1411	: BracePadding);
1412	}
1413	auto RowCount = 1U;
1414	auto Offset = std::distance(first: Cells.begin(), last: CellIter);
1415	for (const auto *Next = CellIter->NextColumnElement; Next;
1416	Next = Next->NextColumnElement) {
1417	if (RowCount >= CellDescs.CellCounts.size())
1418	break;
1419	auto *Start = (Cells.begin() + RowCount * CellDescs.CellCounts[0]);
1420	auto *End = Start + Offset;
1421	auto ThisNetWidth = getNetWidth(Start, End, InitialSpaces: CellDescs.InitialSpaces);
1422	if (Changes[Next->Index].NewlinesBefore == 0) {
1423	Changes[Next->Index].Spaces =
1424	MaxNetWidth - ThisNetWidth +
1425	(Changes[Next->Index].Tok->isNot(Kind: tok::r_brace) ? 1 : BracePadding);
1426	}
1427	++RowCount;
1428	}
1429	}
1430	}
1431
1432	bool WhitespaceManager::isSplitCell(const CellDescription &Cell) {
1433	if (Cell.HasSplit)
1434	return true;
1435	for (const auto *Next = Cell.NextColumnElement; Next;
1436	Next = Next->NextColumnElement) {
1437	if (Next->HasSplit)
1438	return true;
1439	}
1440	return false;
1441	}
1442
1443	WhitespaceManager::CellDescriptions WhitespaceManager::getCells(unsigned Start,
1444	unsigned End) {
1445
1446	unsigned Depth = 0;
1447	unsigned Cell = 0;
1448	SmallVector<unsigned> CellCounts;
1449	unsigned InitialSpaces = 0;
1450	unsigned InitialTokenLength = 0;
1451	unsigned EndSpaces = 0;
1452	SmallVector<CellDescription> Cells;
1453	const FormatToken *MatchingParen = nullptr;
1454	for (unsigned i = Start; i < End; ++i) {
1455	auto &C = Changes[i];
1456	if (C.Tok->is(Kind: tok::l_brace))
1457	++Depth;
1458	else if (C.Tok->is(Kind: tok::r_brace))
1459	--Depth;
1460	if (Depth == 2) {
1461	if (C.Tok->is(Kind: tok::l_brace)) {
1462	Cell = 0;
1463	MatchingParen = C.Tok->MatchingParen;
1464	if (InitialSpaces == 0) {
1465	InitialSpaces = C.Spaces + C.TokenLength;
1466	InitialTokenLength = C.TokenLength;
1467	auto j = i - 1;
1468	for (; Changes[j].NewlinesBefore == 0 && j > Start; --j) {
1469	InitialSpaces += Changes[j].Spaces + Changes[j].TokenLength;
1470	InitialTokenLength += Changes[j].TokenLength;
1471	}
1472	if (C.NewlinesBefore == 0) {
1473	InitialSpaces += Changes[j].Spaces + Changes[j].TokenLength;
1474	InitialTokenLength += Changes[j].TokenLength;
1475	}
1476	}
1477	} else if (C.Tok->is(Kind: tok::comma)) {
1478	if (!Cells.empty())
1479	Cells.back().EndIndex = i;
1480	if (const auto *Next = C.Tok->getNextNonComment();
1481	Next && Next->isNot(Kind: tok::r_brace)) { // dangling comma
1482	++Cell;
1483	}
1484	}
1485	} else if (Depth == 1) {
1486	if (C.Tok == MatchingParen) {
1487	if (!Cells.empty())
1488	Cells.back().EndIndex = i;
1489	Cells.push_back(Elt: CellDescription{.Index: i, .Cell: ++Cell, .EndIndex: i + 1, .HasSplit: false, .NextColumnElement: nullptr});
1490	CellCounts.push_back(Elt: C.Tok->Previous->isNot(Kind: tok::comma) ? Cell + 1
1491	: Cell);
1492	// Go to the next non-comment and ensure there is a break in front
1493	const auto *NextNonComment = C.Tok->getNextNonComment();
1494	while (NextNonComment && NextNonComment->is(Kind: tok::comma))
1495	NextNonComment = NextNonComment->getNextNonComment();
1496	auto j = i;
1497	while (j < End && Changes[j].Tok != NextNonComment)
1498	++j;
1499	if (j < End && Changes[j].NewlinesBefore == 0 &&
1500	Changes[j].Tok->isNot(Kind: tok::r_brace)) {
1501	Changes[j].NewlinesBefore = 1;
1502	// Account for the added token lengths
1503	Changes[j].Spaces = InitialSpaces - InitialTokenLength;
1504	}
1505	} else if (C.Tok->is(Kind: tok::comment) && C.Tok->NewlinesBefore == 0) {
1506	// Trailing comments stay at a space past the last token
1507	C.Spaces = Changes[i - 1].Tok->is(Kind: tok::comma) ? 1 : 2;
1508	} else if (C.Tok->is(Kind: tok::l_brace)) {
1509	// We need to make sure that the ending braces is aligned to the
1510	// start of our initializer
1511	auto j = i - 1;
1512	for (; j > 0 && !Changes[j].Tok->ArrayInitializerLineStart; --j)
1513	; // Nothing the loop does the work
1514	EndSpaces = Changes[j].Spaces;
1515	}
1516	} else if (Depth == 0 && C.Tok->is(Kind: tok::r_brace)) {
1517	C.NewlinesBefore = 1;
1518	C.Spaces = EndSpaces;
1519	}
1520	if (C.Tok->StartsColumn) {
1521	// This gets us past tokens that have been split over multiple
1522	// lines
1523	bool HasSplit = false;
1524	if (Changes[i].NewlinesBefore > 0) {
1525	// So if we split a line previously and the tail line + this token is
1526	// less then the column limit we remove the split here and just put
1527	// the column start at a space past the comma
1528	//
1529	// FIXME This if branch covers the cases where the column is not
1530	// the first column. This leads to weird pathologies like the formatting
1531	// auto foo = Items{
1532	// Section{
1533	// 0, bar(),
1534	// }
1535	// };
1536	// Well if it doesn't lead to that it's indicative that the line
1537	// breaking should be revisited. Unfortunately alot of other options
1538	// interact with this
1539	auto j = i - 1;
1540	if ((j - 1) > Start && Changes[j].Tok->is(Kind: tok::comma) &&
1541	Changes[j - 1].NewlinesBefore > 0) {
1542	--j;
1543	auto LineLimit = Changes[j].Spaces + Changes[j].TokenLength;
1544	if (LineLimit < Style.ColumnLimit) {
1545	Changes[i].NewlinesBefore = 0;
1546	Changes[i].Spaces = 1;
1547	}
1548	}
1549	}
1550	while (Changes[i].NewlinesBefore > 0 && Changes[i].Tok == C.Tok) {
1551	Changes[i].Spaces = InitialSpaces;
1552	++i;
1553	HasSplit = true;
1554	}
1555	if (Changes[i].Tok != C.Tok)
1556	--i;
1557	Cells.push_back(Elt: CellDescription{.Index: i, .Cell: Cell, .EndIndex: i, .HasSplit: HasSplit, .NextColumnElement: nullptr});
1558	}
1559	}
1560
1561	return linkCells(CellDesc: {.Cells: Cells, .CellCounts: CellCounts, .InitialSpaces: InitialSpaces});
1562	}
1563
1564	unsigned WhitespaceManager::calculateCellWidth(unsigned Start, unsigned End,
1565	bool WithSpaces) const {
1566	unsigned CellWidth = 0;
1567	for (auto i = Start; i < End; i++) {
1568	if (Changes[i].NewlinesBefore > 0)
1569	CellWidth = 0;
1570	CellWidth += Changes[i].TokenLength;
1571	CellWidth += (WithSpaces ? Changes[i].Spaces : 0);
1572	}
1573	return CellWidth;
1574	}
1575
1576	void WhitespaceManager::alignToStartOfCell(unsigned Start, unsigned End) {
1577	if ((End - Start) <= 1)
1578	return;
1579	// If the line is broken anywhere in there make sure everything
1580	// is aligned to the parent
1581	for (auto i = Start + 1; i < End; i++)
1582	if (Changes[i].NewlinesBefore > 0)
1583	Changes[i].Spaces = Changes[Start].Spaces;
1584	}
1585
1586	WhitespaceManager::CellDescriptions
1587	WhitespaceManager::linkCells(CellDescriptions &&CellDesc) {
1588	auto &Cells = CellDesc.Cells;
1589	for (auto *CellIter = Cells.begin(); CellIter != Cells.end(); ++CellIter) {
1590	if (!CellIter->NextColumnElement && (CellIter + 1) != Cells.end()) {
1591	for (auto *NextIter = CellIter + 1; NextIter != Cells.end(); ++NextIter) {
1592	if (NextIter->Cell == CellIter->Cell) {
1593	CellIter->NextColumnElement = &(*NextIter);
1594	break;
1595	}
1596	}
1597	}
1598	}
1599	return std::move(CellDesc);
1600	}
1601
1602	void WhitespaceManager::generateChanges() {
1603	for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
1604	const Change &C = Changes[i];
1605	if (i > 0) {
1606	auto Last = Changes[i - 1].OriginalWhitespaceRange;
1607	auto New = Changes[i].OriginalWhitespaceRange;
1608	// Do not generate two replacements for the same location. As a special
1609	// case, it is allowed if there is a replacement for the empty range
1610	// between 2 tokens and another non-empty range at the start of the second
1611	// token. We didn't implement logic to combine replacements for 2
1612	// consecutive source ranges into a single replacement, because the
1613	// program works fine without it.
1614	//
1615	// We can't eliminate empty original whitespace ranges. They appear when
1616	// 2 tokens have no whitespace in between in the input. It does not
1617	// matter whether whitespace is to be added. If no whitespace is to be
1618	// added, the replacement will be empty, and it gets eliminated after this
1619	// step in storeReplacement. For example, if the input is `foo();`,
1620	// there will be a replacement for the range between every consecutive
1621	// pair of tokens.
1622	//
1623	// A replacement at the start of a token can be added by
1624	// BreakableStringLiteralUsingOperators::insertBreak when it adds braces
1625	// around the string literal. Say Verilog code is being formatted and the
1626	// first line is to become the next 2 lines.
1627	// x("long string");
1628	// x({"long ",
1629	// "string"});
1630	// There will be a replacement for the empty range between the parenthesis
1631	// and the string and another replacement for the quote character. The
1632	// replacement for the empty range between the parenthesis and the quote
1633	// comes from ContinuationIndenter::addTokenOnCurrentLine when it changes
1634	// the original empty range between the parenthesis and the string to
1635	// another empty one. The replacement for the quote character comes from
1636	// BreakableStringLiteralUsingOperators::insertBreak when it adds the
1637	// brace. In the example, the replacement for the empty range is the same
1638	// as the original text. However, eliminating replacements that are same
1639	// as the original does not help in general. For example, a newline can
1640	// be inserted, causing the first line to become the next 3 lines.
1641	// xxxxxxxxxxx("long string");
1642	// xxxxxxxxxxx(
1643	// {"long ",
1644	// "string"});
1645	// In that case, the empty range between the parenthesis and the string
1646	// will be replaced by a newline and 4 spaces. So we will still have to
1647	// deal with a replacement for an empty source range followed by a
1648	// replacement for a non-empty source range.
1649	if (Last.getBegin() == New.getBegin() &&
1650	(Last.getEnd() != Last.getBegin() ||
1651	New.getEnd() == New.getBegin())) {
1652	continue;
1653	}
1654	}
1655	if (C.CreateReplacement) {
1656	std::string ReplacementText = C.PreviousLinePostfix;
1657	if (C.ContinuesPPDirective) {
1658	appendEscapedNewlineText(Text&: ReplacementText, Newlines: C.NewlinesBefore,
1659	PreviousEndOfTokenColumn: C.PreviousEndOfTokenColumn,
1660	EscapedNewlineColumn: C.EscapedNewlineColumn);
1661	} else {
1662	appendNewlineText(Text&: ReplacementText, Newlines: C.NewlinesBefore);
1663	}
1664	// FIXME: This assert should hold if we computed the column correctly.
1665	// assert((int)C.StartOfTokenColumn >= C.Spaces);
1666	appendIndentText(
1667	Text&: ReplacementText, IndentLevel: C.Tok->IndentLevel, Spaces: std::max(a: 0, b: C.Spaces),
1668	WhitespaceStartColumn: std::max(a: (int)C.StartOfTokenColumn, b: C.Spaces) - std::max(a: 0, b: C.Spaces),
1669	IsAligned: C.IsAligned);
1670	ReplacementText.append(str: C.CurrentLinePrefix);
1671	storeReplacement(Range: C.OriginalWhitespaceRange, Text: ReplacementText);
1672	}
1673	}
1674	}
1675
1676	void WhitespaceManager::storeReplacement(SourceRange Range, StringRef Text) {
1677	unsigned WhitespaceLength = SourceMgr.getFileOffset(SpellingLoc: Range.getEnd()) -
1678	SourceMgr.getFileOffset(SpellingLoc: Range.getBegin());
1679	// Don't create a replacement, if it does not change anything.
1680	if (StringRef(SourceMgr.getCharacterData(SL: Range.getBegin()),
1681	WhitespaceLength) == Text) {
1682	return;
1683	}
1684	auto Err = Replaces.add(R: tooling::Replacement(
1685	SourceMgr, CharSourceRange::getCharRange(R: Range), Text));
1686	// FIXME: better error handling. For now, just print an error message in the
1687	// release version.
1688	if (Err) {
1689	llvm::errs() << llvm::toString(E: std::move(Err)) << "\n";
1690	assert(false);
1691	}
1692	}
1693
1694	void WhitespaceManager::appendNewlineText(std::string &Text,
1695	unsigned Newlines) {
1696	if (UseCRLF) {
1697	Text.reserve(res: Text.size() + 2 * Newlines);
1698	for (unsigned i = 0; i < Newlines; ++i)
1699	Text.append(s: "\r\n");
1700	} else {
1701	Text.append(n: Newlines, c: '\n');
1702	}
1703	}
1704
1705	void WhitespaceManager::appendEscapedNewlineText(
1706	std::string &Text, unsigned Newlines, unsigned PreviousEndOfTokenColumn,
1707	unsigned EscapedNewlineColumn) {
1708	if (Newlines > 0) {
1709	unsigned Spaces =
1710	std::max<int>(a: 1, b: EscapedNewlineColumn - PreviousEndOfTokenColumn - 1);
1711	for (unsigned i = 0; i < Newlines; ++i) {
1712	Text.append(n: Spaces, c: ' ');
1713	Text.append(s: UseCRLF ? "\\\r\n" : "\\\n");
1714	Spaces = std::max<int>(a: 0, b: EscapedNewlineColumn - 1);
1715	}
1716	}
1717	}
1718
1719	void WhitespaceManager::appendIndentText(std::string &Text,
1720	unsigned IndentLevel, unsigned Spaces,
1721	unsigned WhitespaceStartColumn,
1722	bool IsAligned) {
1723	switch (Style.UseTab) {
1724	case FormatStyle::UT_Never:
1725	Text.append(n: Spaces, c: ' ');
1726	break;
1727	case FormatStyle::UT_Always: {
1728	if (Style.TabWidth) {
1729	unsigned FirstTabWidth =
1730	Style.TabWidth - WhitespaceStartColumn % Style.TabWidth;
1731
1732	// Insert only spaces when we want to end up before the next tab.
1733	if (Spaces < FirstTabWidth || Spaces == 1) {
1734	Text.append(n: Spaces, c: ' ');
1735	break;
1736	}
1737	// Align to the next tab.
1738	Spaces -= FirstTabWidth;
1739	Text.append(s: "\t");
1740
1741	Text.append(n: Spaces / Style.TabWidth, c: '\t');
1742	Text.append(n: Spaces % Style.TabWidth, c: ' ');
1743	} else if (Spaces == 1) {
1744	Text.append(n: Spaces, c: ' ');
1745	}
1746	break;
1747	}
1748	case FormatStyle::UT_ForIndentation:
1749	if (WhitespaceStartColumn == 0) {
1750	unsigned Indentation = IndentLevel * Style.IndentWidth;
1751	Spaces = appendTabIndent(Text, Spaces, Indentation);
1752	}
1753	Text.append(n: Spaces, c: ' ');
1754	break;
1755	case FormatStyle::UT_ForContinuationAndIndentation:
1756	if (WhitespaceStartColumn == 0)
1757	Spaces = appendTabIndent(Text, Spaces, Indentation: Spaces);
1758	Text.append(n: Spaces, c: ' ');
1759	break;
1760	case FormatStyle::UT_AlignWithSpaces:
1761	if (WhitespaceStartColumn == 0) {
1762	unsigned Indentation =
1763	IsAligned ? IndentLevel * Style.IndentWidth : Spaces;
1764	Spaces = appendTabIndent(Text, Spaces, Indentation);
1765	}
1766	Text.append(n: Spaces, c: ' ');
1767	break;
1768	}
1769	}
1770
1771	unsigned WhitespaceManager::appendTabIndent(std::string &Text, unsigned Spaces,
1772	unsigned Indentation) {
1773	// This happens, e.g. when a line in a block comment is indented less than the
1774	// first one.
1775	if (Indentation > Spaces)
1776	Indentation = Spaces;
1777	if (Style.TabWidth) {
1778	unsigned Tabs = Indentation / Style.TabWidth;
1779	Text.append(n: Tabs, c: '\t');
1780	Spaces -= Tabs * Style.TabWidth;
1781	}
1782	return Spaces;
1783	}
1784
1785	} // namespace format
1786	} // namespace clang
1787