1	//===--- UnwrappedLineFormatter.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	#include "UnwrappedLineFormatter.h"
10	#include "FormatToken.h"
11	#include "NamespaceEndCommentsFixer.h"
12	#include "WhitespaceManager.h"
13	#include "llvm/Support/Debug.h"
14	#include <queue>
15
16	#define DEBUG_TYPE "format-formatter"
17
18	namespace clang {
19	namespace format {
20
21	namespace {
22
23	bool startsExternCBlock(const AnnotatedLine &Line) {
24	const FormatToken *Next = Line.First->getNextNonComment();
25	const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;
26	return Line.startsWith(Tokens: tok::kw_extern) && Next && Next->isStringLiteral() &&
27	NextNext && NextNext->is(Kind: tok::l_brace);
28	}
29
30	bool isRecordLBrace(const FormatToken &Tok) {
31	return Tok.isOneOf(K1: TT_ClassLBrace, K2: TT_EnumLBrace, Ks: TT_RecordLBrace,
32	Ks: TT_StructLBrace, Ks: TT_UnionLBrace);
33	}
34
35	/// Tracks the indent level of \c AnnotatedLines across levels.
36	///
37	/// \c nextLine must be called for each \c AnnotatedLine, after which \c
38	/// getIndent() will return the indent for the last line \c nextLine was called
39	/// with.
40	/// If the line is not formatted (and thus the indent does not change), calling
41	/// \c adjustToUnmodifiedLine after the call to \c nextLine will cause
42	/// subsequent lines on the same level to be indented at the same level as the
43	/// given line.
44	class LevelIndentTracker {
45	public:
46	LevelIndentTracker(const FormatStyle &Style,
47	const AdditionalKeywords &Keywords, unsigned StartLevel,
48	int AdditionalIndent)
49	: Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {
50	for (unsigned i = 0; i != StartLevel; ++i)
51	IndentForLevel.push_back(Elt: Style.IndentWidth * i + AdditionalIndent);
52	}
53
54	/// Returns the indent for the current line.
55	unsigned getIndent() const { return Indent; }
56
57	/// Update the indent state given that \p Line is going to be formatted
58	/// next.
59	void nextLine(const AnnotatedLine &Line) {
60	Offset = getIndentOffset(RootToken: *Line.First);
61	// Update the indent level cache size so that we can rely on it
62	// having the right size in adjustToUnmodifiedline.
63	if (Line.Level >= IndentForLevel.size())
64	IndentForLevel.resize(N: Line.Level + 1, NV: -1);
65	if (Style.IndentPPDirectives != FormatStyle::PPDIS_None &&
66	(Line.InPPDirective ||
67	(Style.IndentPPDirectives == FormatStyle::PPDIS_BeforeHash &&
68	Line.Type == LT_CommentAbovePPDirective))) {
69	unsigned PPIndentWidth =
70	(Style.PPIndentWidth >= 0) ? Style.PPIndentWidth : Style.IndentWidth;
71	Indent = Line.InMacroBody
72	? Line.PPLevel * PPIndentWidth +
73	(Line.Level - Line.PPLevel) * Style.IndentWidth
74	: Line.Level * PPIndentWidth;
75	Indent += AdditionalIndent;
76	} else {
77	// When going to lower levels, forget previous higher levels so that we
78	// recompute future higher levels. But don't forget them if we enter a PP
79	// directive, since these do not terminate a C++ code block.
80	if (!Line.InPPDirective) {
81	assert(Line.Level <= IndentForLevel.size());
82	IndentForLevel.resize(N: Line.Level + 1);
83	}
84	Indent = getIndent(Level: Line.Level);
85	}
86	if (static_cast<int>(Indent) + Offset >= 0)
87	Indent += Offset;
88	if (Line.IsContinuation)
89	Indent = Line.Level * Style.IndentWidth + Style.ContinuationIndentWidth;
90	}
91
92	/// Update the level indent to adapt to the given \p Line.
93	///
94	/// When a line is not formatted, we move the subsequent lines on the same
95	/// level to the same indent.
96	/// Note that \c nextLine must have been called before this method.
97	void adjustToUnmodifiedLine(const AnnotatedLine &Line) {
98	if (Line.InPPDirective || Line.IsContinuation)
99	return;
100	assert(Line.Level < IndentForLevel.size());
101	if (Line.First->is(Kind: tok::comment) && IndentForLevel[Line.Level] != -1)
102	return;
103	unsigned LevelIndent = Line.First->OriginalColumn;
104	if (static_cast<int>(LevelIndent) - Offset >= 0)
105	LevelIndent -= Offset;
106	IndentForLevel[Line.Level] = LevelIndent;
107	}
108
109	private:
110	/// Get the offset of the line relatively to the level.
111	///
112	/// For example, 'public:' labels in classes are offset by 1 or 2
113	/// characters to the left from their level.
114	int getIndentOffset(const FormatToken &RootToken) {
115	if (Style.Language == FormatStyle::LK_Java || Style.isJavaScript() ||
116	Style.isCSharp()) {
117	return 0;
118	}
119
120	auto IsAccessModifier = [this, &RootToken]() {
121	if (RootToken.isAccessSpecifier(ColonRequired: Style.isCpp())) {
122	return true;
123	} else if (RootToken.isObjCAccessSpecifier()) {
124	return true;
125	}
126	// Handle Qt signals.
127	else if (RootToken.isOneOf(K1: Keywords.kw_signals, K2: Keywords.kw_qsignals) &&
128	RootToken.Next && RootToken.Next->is(Kind: tok::colon)) {
129	return true;
130	} else if (RootToken.Next &&
131	RootToken.Next->isOneOf(K1: Keywords.kw_slots,
132	K2: Keywords.kw_qslots) &&
133	RootToken.Next->Next && RootToken.Next->Next->is(Kind: tok::colon)) {
134	return true;
135	}
136	// Handle malformed access specifier e.g. 'private' without trailing ':'.
137	else if (!RootToken.Next && RootToken.isAccessSpecifier(ColonRequired: false)) {
138	return true;
139	}
140	return false;
141	};
142
143	if (IsAccessModifier()) {
144	// The AccessModifierOffset may be overridden by IndentAccessModifiers,
145	// in which case we take a negative value of the IndentWidth to simulate
146	// the upper indent level.
147	return Style.IndentAccessModifiers ? -Style.IndentWidth
148	: Style.AccessModifierOffset;
149	}
150	return 0;
151	}
152
153	/// Get the indent of \p Level from \p IndentForLevel.
154	///
155	/// \p IndentForLevel must contain the indent for the level \c l
156	/// at \p IndentForLevel[l], or a value < 0 if the indent for
157	/// that level is unknown.
158	unsigned getIndent(unsigned Level) const {
159	assert(Level < IndentForLevel.size());
160	if (IndentForLevel[Level] != -1)
161	return IndentForLevel[Level];
162	if (Level == 0)
163	return 0;
164	return getIndent(Level: Level - 1) + Style.IndentWidth;
165	}
166
167	const FormatStyle &Style;
168	const AdditionalKeywords &Keywords;
169	const unsigned AdditionalIndent;
170
171	/// The indent in characters for each level. It remembers the indent of
172	/// previous lines (that are not PP directives) of equal or lower levels. This
173	/// is used to align formatted lines to the indent of previous non-formatted
174	/// lines. Think about the --lines parameter of clang-format.
175	SmallVector<int> IndentForLevel;
176
177	/// Offset of the current line relative to the indent level.
178	///
179	/// For example, the 'public' keywords is often indented with a negative
180	/// offset.
181	int Offset = 0;
182
183	/// The current line's indent.
184	unsigned Indent = 0;
185	};
186
187	const FormatToken *getMatchingNamespaceToken(
188	const AnnotatedLine *Line,
189	const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
190	if (!Line->startsWith(Tokens: tok::r_brace))
191	return nullptr;
192	size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex;
193	if (StartLineIndex == UnwrappedLine::kInvalidIndex)
194	return nullptr;
195	assert(StartLineIndex < AnnotatedLines.size());
196	return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();
197	}
198
199	StringRef getNamespaceTokenText(const AnnotatedLine *Line) {
200	const FormatToken *NamespaceToken = Line->First->getNamespaceToken();
201	return NamespaceToken ? NamespaceToken->TokenText : StringRef();
202	}
203
204	StringRef getMatchingNamespaceTokenText(
205	const AnnotatedLine *Line,
206	const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
207	const FormatToken *NamespaceToken =
208	getMatchingNamespaceToken(Line, AnnotatedLines);
209	return NamespaceToken ? NamespaceToken->TokenText : StringRef();
210	}
211
212	class LineJoiner {
213	public:
214	LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords,
215	const SmallVectorImpl<AnnotatedLine *> &Lines)
216	: Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()),
217	AnnotatedLines(Lines) {}
218
219	/// Returns the next line, merging multiple lines into one if possible.
220	const AnnotatedLine *getNextMergedLine(bool DryRun,
221	LevelIndentTracker &IndentTracker) {
222	if (Next == End)
223	return nullptr;
224	const AnnotatedLine *Current = *Next;
225	IndentTracker.nextLine(Line: *Current);
226	unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, I: Next, E: End);
227	if (MergedLines > 0 && Style.ColumnLimit == 0) {
228	// Disallow line merging if there is a break at the start of one of the
229	// input lines.
230	for (unsigned i = 0; i < MergedLines; ++i)
231	if (Next[i + 1]->First->NewlinesBefore > 0)
232	MergedLines = 0;
233	}
234	if (!DryRun)
235	for (unsigned i = 0; i < MergedLines; ++i)
236	join(A&: *Next[0], B: *Next[i + 1]);
237	Next = Next + MergedLines + 1;
238	return Current;
239	}
240
241	private:
242	/// Calculates how many lines can be merged into 1 starting at \p I.
243	unsigned
244	tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,
245	SmallVectorImpl<AnnotatedLine *>::const_iterator I,
246	SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
247	const unsigned Indent = IndentTracker.getIndent();
248
249	// Can't join the last line with anything.
250	if (I + 1 == E)
251	return 0;
252	// We can never merge stuff if there are trailing line comments.
253	const AnnotatedLine *TheLine = *I;
254	if (TheLine->Last->is(TT: TT_LineComment))
255	return 0;
256	const auto &NextLine = *I[1];
257	if (NextLine.Type == LT_Invalid || NextLine.First->MustBreakBefore)
258	return 0;
259	if (TheLine->InPPDirective &&
260	(!NextLine.InPPDirective || NextLine.First->HasUnescapedNewline)) {
261	return 0;
262	}
263
264	if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
265	return 0;
266
267	unsigned Limit =
268	Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
269	// If we already exceed the column limit, we set 'Limit' to 0. The different
270	// tryMerge..() functions can then decide whether to still do merging.
271	Limit = TheLine->Last->TotalLength > Limit
272	? 0
273	: Limit - TheLine->Last->TotalLength;
274
275	if (TheLine->Last->is(TT: TT_FunctionLBrace) &&
276	TheLine->First == TheLine->Last &&
277	!Style.BraceWrapping.SplitEmptyFunction &&
278	NextLine.First->is(Kind: tok::r_brace)) {
279	return tryMergeSimpleBlock(I, E, Limit);
280	}
281
282	const auto *PreviousLine = I != AnnotatedLines.begin() ? I[-1] : nullptr;
283	// Handle empty record blocks where the brace has already been wrapped.
284	if (PreviousLine && TheLine->Last->is(Kind: tok::l_brace) &&
285	TheLine->First == TheLine->Last) {
286	bool EmptyBlock = NextLine.First->is(Kind: tok::r_brace);
287
288	const FormatToken *Tok = PreviousLine->First;
289	if (Tok && Tok->is(Kind: tok::comment))
290	Tok = Tok->getNextNonComment();
291
292	if (Tok && Tok->getNamespaceToken()) {
293	return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock
294	? tryMergeSimpleBlock(I, E, Limit)
295	: 0;
296	}
297
298	if (Tok && Tok->is(Kind: tok::kw_typedef))
299	Tok = Tok->getNextNonComment();
300	if (Tok && Tok->isOneOf(K1: tok::kw_class, K2: tok::kw_struct, Ks: tok::kw_union,
301	Ks: tok::kw_extern, Ks: Keywords.kw_interface)) {
302	return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock
303	? tryMergeSimpleBlock(I, E, Limit)
304	: 0;
305	}
306
307	if (Tok && Tok->is(Kind: tok::kw_template) &&
308	Style.BraceWrapping.SplitEmptyRecord && EmptyBlock) {
309	return 0;
310	}
311	}
312
313	auto ShouldMergeShortFunctions = [this, &I, &NextLine, PreviousLine,
314	TheLine]() {
315	if (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All)
316	return true;
317	if (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
318	NextLine.First->is(Kind: tok::r_brace)) {
319	return true;
320	}
321
322	if (Style.AllowShortFunctionsOnASingleLine &
323	FormatStyle::SFS_InlineOnly) {
324	// Just checking TheLine->Level != 0 is not enough, because it
325	// provokes treating functions inside indented namespaces as short.
326	if (Style.isJavaScript() && TheLine->Last->is(TT: TT_FunctionLBrace))
327	return true;
328
329	if (TheLine->Level != 0) {
330	if (!PreviousLine)
331	return false;
332
333	// TODO: Use IndentTracker to avoid loop?
334	// Find the last line with lower level.
335	const AnnotatedLine *Line = nullptr;
336	for (auto J = I - 1; J >= AnnotatedLines.begin(); --J) {
337	assert(*J);
338	if (!(*J)->InPPDirective && !(*J)->isComment() &&
339	(*J)->Level < TheLine->Level) {
340	Line = *J;
341	break;
342	}
343	}
344
345	if (!Line)
346	return false;
347
348	// Check if the found line starts a record.
349	const auto *LastNonComment = Line->getLastNonComment();
350	// There must be another token (usually `{`), because we chose a
351	// non-PPDirective and non-comment line that has a smaller level.
352	assert(LastNonComment);
353	return isRecordLBrace(Tok: *LastNonComment);
354	}
355	}
356
357	return false;
358	};
359
360	bool MergeShortFunctions = ShouldMergeShortFunctions();
361
362	const auto *FirstNonComment = TheLine->getFirstNonComment();
363	if (!FirstNonComment)
364	return 0;
365	// FIXME: There are probably cases where we should use FirstNonComment
366	// instead of TheLine->First.
367
368	if (Style.CompactNamespaces) {
369	if (const auto *NSToken = TheLine->First->getNamespaceToken()) {
370	int J = 1;
371	assert(TheLine->MatchingClosingBlockLineIndex > 0);
372	for (auto ClosingLineIndex = TheLine->MatchingClosingBlockLineIndex - 1;
373	I + J != E && NSToken->TokenText == getNamespaceTokenText(Line: I[J]) &&
374	ClosingLineIndex == I[J]->MatchingClosingBlockLineIndex &&
375	I[J]->Last->TotalLength < Limit;
376	++J, --ClosingLineIndex) {
377	Limit -= I[J]->Last->TotalLength;
378
379	// Reduce indent level for bodies of namespaces which were compacted,
380	// but only if their content was indented in the first place.
381	auto *ClosingLine = AnnotatedLines.begin() + ClosingLineIndex + 1;
382	const int OutdentBy = I[J]->Level - TheLine->Level;
383	assert(OutdentBy >= 0);
384	for (auto *CompactedLine = I + J; CompactedLine <= ClosingLine;
385	++CompactedLine) {
386	if (!(*CompactedLine)->InPPDirective) {
387	const int Level = (*CompactedLine)->Level;
388	(*CompactedLine)->Level = std::max(a: Level - OutdentBy, b: 0);
389	}
390	}
391	}
392	return J - 1;
393	}
394
395	if (auto nsToken = getMatchingNamespaceToken(Line: TheLine, AnnotatedLines)) {
396	int i = 0;
397	unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;
398	for (; I + 1 + i != E &&
399	nsToken->TokenText ==
400	getMatchingNamespaceTokenText(Line: I[i + 1], AnnotatedLines) &&
401	openingLine == I[i + 1]->MatchingOpeningBlockLineIndex;
402	i++, --openingLine) {
403	// No space between consecutive braces.
404	I[i + 1]->First->SpacesRequiredBefore =
405	I[i]->Last->isNot(Kind: tok::r_brace);
406
407	// Indent like the outer-most namespace.
408	IndentTracker.nextLine(Line: *I[i + 1]);
409	}
410	return i;
411	}
412	}
413
414	const auto *LastNonComment = TheLine->getLastNonComment();
415	assert(LastNonComment);
416	// FIXME: There are probably cases where we should use LastNonComment
417	// instead of TheLine->Last.
418
419	// Try to merge a function block with left brace unwrapped.
420	if (LastNonComment->is(TT: TT_FunctionLBrace) &&
421	TheLine->First != LastNonComment) {
422	return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
423	}
424	// Try to merge a control statement block with left brace unwrapped.
425	if (TheLine->Last->is(Kind: tok::l_brace) && FirstNonComment != TheLine->Last &&
426	FirstNonComment->isOneOf(K1: tok::kw_if, K2: tok::kw_while, Ks: tok::kw_for,
427	Ks: TT_ForEachMacro)) {
428	return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never
429	? tryMergeSimpleBlock(I, E, Limit)
430	: 0;
431	}
432	// Try to merge a control statement block with left brace wrapped.
433	if (NextLine.First->is(Kind: tok::l_brace)) {
434	if ((TheLine->First->isOneOf(K1: tok::kw_if, K2: tok::kw_else, Ks: tok::kw_while,
435	Ks: tok::kw_for, Ks: tok::kw_switch, Ks: tok::kw_try,
436	Ks: tok::kw_do, Ks: TT_ForEachMacro) ||
437	(TheLine->First->is(Kind: tok::r_brace) && TheLine->First->Next &&
438	TheLine->First->Next->isOneOf(K1: tok::kw_else, K2: tok::kw_catch))) &&
439	Style.BraceWrapping.AfterControlStatement ==
440	FormatStyle::BWACS_MultiLine) {
441	// If possible, merge the next line's wrapped left brace with the
442	// current line. Otherwise, leave it on the next line, as this is a
443	// multi-line control statement.
444	return (Style.ColumnLimit == 0 || TheLine->Level * Style.IndentWidth +
445	TheLine->Last->TotalLength <=
446	Style.ColumnLimit)
447	? 1
448	: 0;
449	}
450	if (TheLine->First->isOneOf(K1: tok::kw_if, K2: tok::kw_else, Ks: tok::kw_while,
451	Ks: tok::kw_for, Ks: TT_ForEachMacro)) {
452	return (Style.BraceWrapping.AfterControlStatement ==
453	FormatStyle::BWACS_Always)
454	? tryMergeSimpleBlock(I, E, Limit)
455	: 0;
456	}
457	if (TheLine->First->isOneOf(K1: tok::kw_else, K2: tok::kw_catch) &&
458	Style.BraceWrapping.AfterControlStatement ==
459	FormatStyle::BWACS_MultiLine) {
460	// This case if different from the upper BWACS_MultiLine processing
461	// in that a preceding r_brace is not on the same line as else/catch
462	// most likely because of BeforeElse/BeforeCatch set to true.
463	// If the line length doesn't fit ColumnLimit, leave l_brace on the
464	// next line to respect the BWACS_MultiLine.
465	return (Style.ColumnLimit == 0 ||
466	TheLine->Last->TotalLength <= Style.ColumnLimit)
467	? 1
468	: 0;
469	}
470	}
471	if (PreviousLine && TheLine->First->is(Kind: tok::l_brace)) {
472	switch (PreviousLine->First->Tok.getKind()) {
473	case tok::at:
474	// Don't merge block with left brace wrapped after ObjC special blocks.
475	if (PreviousLine->First->Next) {
476	tok::ObjCKeywordKind kwId =
477	PreviousLine->First->Next->Tok.getObjCKeywordID();
478	if (kwId == tok::objc_autoreleasepool ||
479	kwId == tok::objc_synchronized) {
480	return 0;
481	}
482	}
483	break;
484
485	case tok::kw_case:
486	case tok::kw_default:
487	// Don't merge block with left brace wrapped after case labels.
488	return 0;
489
490	default:
491	break;
492	}
493	}
494
495	// Don't merge an empty template class or struct if SplitEmptyRecords
496	// is defined.
497	if (PreviousLine && Style.BraceWrapping.SplitEmptyRecord &&
498	TheLine->Last->is(Kind: tok::l_brace) && PreviousLine->Last) {
499	const FormatToken *Previous = PreviousLine->Last;
500	if (Previous) {
501	if (Previous->is(Kind: tok::comment))
502	Previous = Previous->getPreviousNonComment();
503	if (Previous) {
504	if (Previous->is(Kind: tok::greater) && !PreviousLine->InPPDirective)
505	return 0;
506	if (Previous->is(Kind: tok::identifier)) {
507	const FormatToken *PreviousPrevious =
508	Previous->getPreviousNonComment();
509	if (PreviousPrevious &&
510	PreviousPrevious->isOneOf(K1: tok::kw_class, K2: tok::kw_struct)) {
511	return 0;
512	}
513	}
514	}
515	}
516	}
517
518	if (TheLine->Last->is(Kind: tok::l_brace)) {
519	bool ShouldMerge = false;
520	// Try to merge records.
521	if (TheLine->Last->is(TT: TT_EnumLBrace)) {
522	ShouldMerge = Style.AllowShortEnumsOnASingleLine;
523	} else if (TheLine->Last->is(TT: TT_RequiresExpressionLBrace)) {
524	ShouldMerge = Style.AllowShortCompoundRequirementOnASingleLine;
525	} else if (TheLine->Last->isOneOf(K1: TT_ClassLBrace, K2: TT_StructLBrace)) {
526	// NOTE: We use AfterClass (whereas AfterStruct exists) for both classes
527	// and structs, but it seems that wrapping is still handled correctly
528	// elsewhere.
529	ShouldMerge = !Style.BraceWrapping.AfterClass ||
530	(NextLine.First->is(Kind: tok::r_brace) &&
531	!Style.BraceWrapping.SplitEmptyRecord);
532	} else if (TheLine->InPPDirective ||
533	!TheLine->First->isOneOf(K1: tok::kw_class, K2: tok::kw_enum,
534	Ks: tok::kw_struct)) {
535	// Try to merge a block with left brace unwrapped that wasn't yet
536	// covered.
537	ShouldMerge = !Style.BraceWrapping.AfterFunction ||
538	(NextLine.First->is(Kind: tok::r_brace) &&
539	!Style.BraceWrapping.SplitEmptyFunction);
540	}
541	return ShouldMerge ? tryMergeSimpleBlock(I, E, Limit) : 0;
542	}
543
544	// Try to merge a function block with left brace wrapped.
545	if (NextLine.First->is(TT: TT_FunctionLBrace) &&
546	Style.BraceWrapping.AfterFunction) {
547	if (NextLine.Last->is(TT: TT_LineComment))
548	return 0;
549
550	// Check for Limit <= 2 to account for the " {".
551	if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(Line: TheLine)))
552	return 0;
553	Limit -= 2;
554
555	unsigned MergedLines = 0;
556	if (MergeShortFunctions ||
557	(Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
558	NextLine.First == NextLine.Last && I + 2 != E &&
559	I[2]->First->is(Kind: tok::r_brace))) {
560	MergedLines = tryMergeSimpleBlock(I: I + 1, E, Limit);
561	// If we managed to merge the block, count the function header, which is
562	// on a separate line.
563	if (MergedLines > 0)
564	++MergedLines;
565	}
566	return MergedLines;
567	}
568	auto IsElseLine = [&TheLine]() -> bool {
569	const FormatToken *First = TheLine->First;
570	if (First->is(Kind: tok::kw_else))
571	return true;
572
573	return First->is(Kind: tok::r_brace) && First->Next &&
574	First->Next->is(Kind: tok::kw_else);
575	};
576	if (TheLine->First->is(Kind: tok::kw_if) ||
577	(IsElseLine() && (Style.AllowShortIfStatementsOnASingleLine ==
578	FormatStyle::SIS_AllIfsAndElse))) {
579	return Style.AllowShortIfStatementsOnASingleLine
580	? tryMergeSimpleControlStatement(I, E, Limit)
581	: 0;
582	}
583	if (TheLine->First->isOneOf(K1: tok::kw_for, K2: tok::kw_while, Ks: tok::kw_do,
584	Ks: TT_ForEachMacro)) {
585	return Style.AllowShortLoopsOnASingleLine
586	? tryMergeSimpleControlStatement(I, E, Limit)
587	: 0;
588	}
589	if (TheLine->First->isOneOf(K1: tok::kw_case, K2: tok::kw_default)) {
590	return Style.AllowShortCaseLabelsOnASingleLine
591	? tryMergeShortCaseLabels(I, E, Limit)
592	: 0;
593	}
594	if (TheLine->InPPDirective &&
595	(TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
596	return tryMergeSimplePPDirective(I, E, Limit);
597	}
598	return 0;
599	}
600
601	unsigned
602	tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
603	SmallVectorImpl<AnnotatedLine *>::const_iterator E,
604	unsigned Limit) {
605	if (Limit == 0)
606	return 0;
607	if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
608	return 0;
609	if (1 + I[1]->Last->TotalLength > Limit)
610	return 0;
611	return 1;
612	}
613
614	unsigned tryMergeSimpleControlStatement(
615	SmallVectorImpl<AnnotatedLine *>::const_iterator I,
616	SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
617	if (Limit == 0)
618	return 0;
619	if (Style.BraceWrapping.AfterControlStatement ==
620	FormatStyle::BWACS_Always &&
621	I[1]->First->is(Kind: tok::l_brace) &&
622	Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never) {
623	return 0;
624	}
625	if (I[1]->InPPDirective != (*I)->InPPDirective ||
626	(I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) {
627	return 0;
628	}
629	Limit = limitConsideringMacros(I: I + 1, E, Limit);
630	AnnotatedLine &Line = **I;
631	if (Line.First->isNot(Kind: tok::kw_do) && Line.First->isNot(Kind: tok::kw_else) &&
632	Line.Last->isNot(Kind: tok::kw_else) && Line.Last->isNot(Kind: tok::r_paren)) {
633	return 0;
634	}
635	// Only merge `do while` if `do` is the only statement on the line.
636	if (Line.First->is(Kind: tok::kw_do) && Line.Last->isNot(Kind: tok::kw_do))
637	return 0;
638	if (1 + I[1]->Last->TotalLength > Limit)
639	return 0;
640	// Don't merge with loops, ifs, a single semicolon or a line comment.
641	if (I[1]->First->isOneOf(K1: tok::semi, K2: tok::kw_if, Ks: tok::kw_for, Ks: tok::kw_while,
642	Ks: TT_ForEachMacro, Ks: TT_LineComment)) {
643	return 0;
644	}
645	// Only inline simple if's (no nested if or else), unless specified
646	if (Style.AllowShortIfStatementsOnASingleLine ==
647	FormatStyle::SIS_WithoutElse) {
648	if (I + 2 != E && Line.startsWith(Tokens: tok::kw_if) &&
649	I[2]->First->is(Kind: tok::kw_else)) {
650	return 0;
651	}
652	}
653	return 1;
654	}
655
656	unsigned
657	tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
658	SmallVectorImpl<AnnotatedLine *>::const_iterator E,
659	unsigned Limit) {
660	if (Limit == 0 || I + 1 == E ||
661	I[1]->First->isOneOf(K1: tok::kw_case, K2: tok::kw_default)) {
662	return 0;
663	}
664	if (I[0]->Last->is(Kind: tok::l_brace) || I[1]->First->is(Kind: tok::l_brace))
665	return 0;
666	unsigned NumStmts = 0;
667	unsigned Length = 0;
668	bool EndsWithComment = false;
669	bool InPPDirective = I[0]->InPPDirective;
670	bool InMacroBody = I[0]->InMacroBody;
671	const unsigned Level = I[0]->Level;
672	for (; NumStmts < 3; ++NumStmts) {
673	if (I + 1 + NumStmts == E)
674	break;
675	const AnnotatedLine *Line = I[1 + NumStmts];
676	if (Line->InPPDirective != InPPDirective)
677	break;
678	if (Line->InMacroBody != InMacroBody)
679	break;
680	if (Line->First->isOneOf(K1: tok::kw_case, K2: tok::kw_default, Ks: tok::r_brace))
681	break;
682	if (Line->First->isOneOf(K1: tok::kw_if, K2: tok::kw_for, Ks: tok::kw_switch,
683	Ks: tok::kw_while) ||
684	EndsWithComment) {
685	return 0;
686	}
687	if (Line->First->is(Kind: tok::comment)) {
688	if (Level != Line->Level)
689	return 0;
690	SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
691	for (; J != E; ++J) {
692	Line = *J;
693	if (Line->InPPDirective != InPPDirective)
694	break;
695	if (Line->First->isOneOf(K1: tok::kw_case, K2: tok::kw_default, Ks: tok::r_brace))
696	break;
697	if (Line->First->isNot(Kind: tok::comment) || Level != Line->Level)
698	return 0;
699	}
700	break;
701	}
702	if (Line->Last->is(Kind: tok::comment))
703	EndsWithComment = true;
704	Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
705	}
706	if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
707	return 0;
708	return NumStmts;
709	}
710
711	unsigned
712	tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
713	SmallVectorImpl<AnnotatedLine *>::const_iterator E,
714	unsigned Limit) {
715	// Don't merge with a preprocessor directive.
716	if (I[1]->Type == LT_PreprocessorDirective)
717	return 0;
718
719	AnnotatedLine &Line = **I;
720
721	// Don't merge ObjC @ keywords and methods.
722	// FIXME: If an option to allow short exception handling clauses on a single
723	// line is added, change this to not return for @try and friends.
724	if (Style.Language != FormatStyle::LK_Java &&
725	Line.First->isOneOf(K1: tok::at, K2: tok::minus, Ks: tok::plus)) {
726	return 0;
727	}
728
729	// Check that the current line allows merging. This depends on whether we
730	// are in a control flow statements as well as several style flags.
731	if (Line.First->is(Kind: tok::kw_case) ||
732	(Line.First->Next && Line.First->Next->is(Kind: tok::kw_else))) {
733	return 0;
734	}
735	// default: in switch statement
736	if (Line.First->is(Kind: tok::kw_default)) {
737	const FormatToken *Tok = Line.First->getNextNonComment();
738	if (Tok && Tok->is(Kind: tok::colon))
739	return 0;
740	}
741
742	auto IsCtrlStmt = [](const auto &Line) {
743	return Line.First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
744	tok::kw_do, tok::kw_for, TT_ForEachMacro);
745	};
746
747	const bool IsSplitBlock =
748	Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never ||
749	(Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Empty &&
750	I[1]->First->isNot(Kind: tok::r_brace));
751
752	if (IsCtrlStmt(Line) ||
753	Line.First->isOneOf(K1: tok::kw_try, K2: tok::kw___try, Ks: tok::kw_catch,
754	Ks: tok::kw___finally, Ks: tok::r_brace,
755	Ks: Keywords.kw___except)) {
756	if (IsSplitBlock)
757	return 0;
758	// Don't merge when we can't except the case when
759	// the control statement block is empty
760	if (!Style.AllowShortIfStatementsOnASingleLine &&
761	Line.First->isOneOf(K1: tok::kw_if, K2: tok::kw_else) &&
762	!Style.BraceWrapping.AfterControlStatement &&
763	I[1]->First->isNot(Kind: tok::r_brace)) {
764	return 0;
765	}
766	if (!Style.AllowShortIfStatementsOnASingleLine &&
767	Line.First->isOneOf(K1: tok::kw_if, K2: tok::kw_else) &&
768	Style.BraceWrapping.AfterControlStatement ==
769	FormatStyle::BWACS_Always &&
770	I + 2 != E && I[2]->First->isNot(Kind: tok::r_brace)) {
771	return 0;
772	}
773	if (!Style.AllowShortLoopsOnASingleLine &&
774	Line.First->isOneOf(K1: tok::kw_while, K2: tok::kw_do, Ks: tok::kw_for,
775	Ks: TT_ForEachMacro) &&
776	!Style.BraceWrapping.AfterControlStatement &&
777	I[1]->First->isNot(Kind: tok::r_brace)) {
778	return 0;
779	}
780	if (!Style.AllowShortLoopsOnASingleLine &&
781	Line.First->isOneOf(K1: tok::kw_while, K2: tok::kw_do, Ks: tok::kw_for,
782	Ks: TT_ForEachMacro) &&
783	Style.BraceWrapping.AfterControlStatement ==
784	FormatStyle::BWACS_Always &&
785	I + 2 != E && I[2]->First->isNot(Kind: tok::r_brace)) {
786	return 0;
787	}
788	// FIXME: Consider an option to allow short exception handling clauses on
789	// a single line.
790	// FIXME: This isn't covered by tests.
791	// FIXME: For catch, __except, __finally the first token on the line
792	// is '}', so this isn't correct here.
793	if (Line.First->isOneOf(K1: tok::kw_try, K2: tok::kw___try, Ks: tok::kw_catch,
794	Ks: Keywords.kw___except, Ks: tok::kw___finally)) {
795	return 0;
796	}
797	}
798
799	if (Line.endsWith(Tokens: tok::l_brace)) {
800	if (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never &&
801	Line.First->is(TT: TT_BlockLBrace)) {
802	return 0;
803	}
804
805	if (IsSplitBlock && Line.First == Line.Last &&
806	I > AnnotatedLines.begin() &&
807	(I[-1]->endsWith(Tokens: tok::kw_else) || IsCtrlStmt(*I[-1]))) {
808	return 0;
809	}
810	FormatToken *Tok = I[1]->First;
811	auto ShouldMerge = [Tok]() {
812	if (Tok->isNot(Kind: tok::r_brace) || Tok->MustBreakBefore)
813	return false;
814	const FormatToken *Next = Tok->getNextNonComment();
815	return !Next || Next->is(Kind: tok::semi);
816	};
817
818	if (ShouldMerge()) {
819	// We merge empty blocks even if the line exceeds the column limit.
820	Tok->SpacesRequiredBefore =
821	(Style.SpaceInEmptyBlock || Line.Last->is(Kind: tok::comment)) ? 1 : 0;
822	Tok->CanBreakBefore = true;
823	return 1;
824	} else if (Limit != 0 && !Line.startsWithNamespace() &&
825	!startsExternCBlock(Line)) {
826	// We don't merge short records.
827	if (isRecordLBrace(Tok: *Line.Last))
828	return 0;
829
830	// Check that we still have three lines and they fit into the limit.
831	if (I + 2 == E || I[2]->Type == LT_Invalid)
832	return 0;
833	Limit = limitConsideringMacros(I: I + 2, E, Limit);
834
835	if (!nextTwoLinesFitInto(I, Limit))
836	return 0;
837
838	// Second, check that the next line does not contain any braces - if it
839	// does, readability declines when putting it into a single line.
840	if (I[1]->Last->is(TT: TT_LineComment))
841	return 0;
842	do {
843	if (Tok->is(Kind: tok::l_brace) && Tok->isNot(Kind: BK_BracedInit))
844	return 0;
845	Tok = Tok->Next;
846	} while (Tok);
847
848	// Last, check that the third line starts with a closing brace.
849	Tok = I[2]->First;
850	if (Tok->isNot(Kind: tok::r_brace))
851	return 0;
852
853	// Don't merge "if (a) { .. } else {".
854	if (Tok->Next && Tok->Next->is(Kind: tok::kw_else))
855	return 0;
856
857	// Don't merge a trailing multi-line control statement block like:
858	// } else if (foo &&
859	// bar)
860	// { <-- current Line
861	// baz();
862	// }
863	if (Line.First == Line.Last && Line.First->isNot(Kind: TT_FunctionLBrace) &&
864	Style.BraceWrapping.AfterControlStatement ==
865	FormatStyle::BWACS_MultiLine) {
866	return 0;
867	}
868
869	return 2;
870	}
871	} else if (I[1]->First->is(Kind: tok::l_brace)) {
872	if (I[1]->Last->is(TT: TT_LineComment))
873	return 0;
874
875	// Check for Limit <= 2 to account for the " {".
876	if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(Line: *I)))
877	return 0;
878	Limit -= 2;
879	unsigned MergedLines = 0;
880	if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never ||
881	(I[1]->First == I[1]->Last && I + 2 != E &&
882	I[2]->First->is(Kind: tok::r_brace))) {
883	MergedLines = tryMergeSimpleBlock(I: I + 1, E, Limit);
884	// If we managed to merge the block, count the statement header, which
885	// is on a separate line.
886	if (MergedLines > 0)
887	++MergedLines;
888	}
889	return MergedLines;
890	}
891	return 0;
892	}
893
894	/// Returns the modified column limit for \p I if it is inside a macro and
895	/// needs a trailing '\'.
896	unsigned
897	limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
898	SmallVectorImpl<AnnotatedLine *>::const_iterator E,
899	unsigned Limit) {
900	if (I[0]->InPPDirective && I + 1 != E &&
901	!I[1]->First->HasUnescapedNewline && I[1]->First->isNot(Kind: tok::eof)) {
902	return Limit < 2 ? 0 : Limit - 2;
903	}
904	return Limit;
905	}
906
907	bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
908	unsigned Limit) {
909	if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
910	return false;
911	return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
912	}
913
914	bool containsMustBreak(const AnnotatedLine *Line) {
915	assert(Line->First);
916	// Ignore the first token, because in this situation, it applies more to the
917	// last token of the previous line.
918	for (const FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next)
919	if (Tok->MustBreakBefore)
920	return true;
921	return false;
922	}
923
924	void join(AnnotatedLine &A, const AnnotatedLine &B) {
925	assert(!A.Last->Next);
926	assert(!B.First->Previous);
927	if (B.Affected)
928	A.Affected = true;
929	A.Last->Next = B.First;
930	B.First->Previous = A.Last;
931	B.First->CanBreakBefore = true;
932	unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
933	for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
934	Tok->TotalLength += LengthA;
935	A.Last = Tok;
936	}
937	}
938
939	const FormatStyle &Style;
940	const AdditionalKeywords &Keywords;
941	const SmallVectorImpl<AnnotatedLine *>::const_iterator End;
942
943	SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
944	const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
945	};
946
947	static void markFinalized(FormatToken *Tok) {
948	if (Tok->is(Kind: tok::hash) && !Tok->Previous && Tok->Next &&
949	Tok->Next->isOneOf(K1: tok::pp_if, K2: tok::pp_ifdef, Ks: tok::pp_ifndef,
950	Ks: tok::pp_elif, Ks: tok::pp_elifdef, Ks: tok::pp_elifndef,
951	Ks: tok::pp_else, Ks: tok::pp_endif)) {
952	Tok = Tok->Next;
953	}
954	for (; Tok; Tok = Tok->Next) {
955	if (Tok->MacroCtx && Tok->MacroCtx->Role == MR_ExpandedArg) {
956	// In the first pass we format all macro arguments in the expanded token
957	// stream. Instead of finalizing the macro arguments, we mark that they
958	// will be modified as unexpanded arguments (as part of the macro call
959	// formatting) in the next pass.
960	Tok->MacroCtx->Role = MR_UnexpandedArg;
961	// Reset whether spaces or a line break are required before this token, as
962	// that is context dependent, and that context may change when formatting
963	// the macro call. For example, given M(x) -> 2 * x, and the macro call
964	// M(var), the token 'var' will have SpacesRequiredBefore = 1 after being
965	// formatted as part of the expanded macro, but SpacesRequiredBefore = 0
966	// for its position within the macro call.
967	Tok->SpacesRequiredBefore = 0;
968	if (!Tok->MustBreakBeforeFinalized)
969	Tok->MustBreakBefore = 0;
970	} else {
971	Tok->Finalized = true;
972	}
973	}
974	}
975
976	#ifndef NDEBUG
977	static void printLineState(const LineState &State) {
978	llvm::dbgs() << "State: ";
979	for (const ParenState &P : State.Stack) {
980	llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
981	<< P.LastSpace << "|" << P.NestedBlockIndent << " ";
982	}
983	llvm::dbgs() << State.NextToken->TokenText << "\n";
984	}
985	#endif
986
987	/// Base class for classes that format one \c AnnotatedLine.
988	class LineFormatter {
989	public:
990	LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,
991	const FormatStyle &Style,
992	UnwrappedLineFormatter *BlockFormatter)
993	: Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
994	BlockFormatter(BlockFormatter) {}
995	virtual ~LineFormatter() {}
996
997	/// Formats an \c AnnotatedLine and returns the penalty.
998	///
999	/// If \p DryRun is \c false, directly applies the changes.
1000	virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
1001	unsigned FirstStartColumn, bool DryRun) = 0;
1002
1003	protected:
1004	/// If the \p State's next token is an r_brace closing a nested block,
1005	/// format the nested block before it.
1006	///
1007	/// Returns \c true if all children could be placed successfully and adapts
1008	/// \p Penalty as well as \p State. If \p DryRun is false, also directly
1009	/// creates changes using \c Whitespaces.
1010	///
1011	/// The crucial idea here is that children always get formatted upon
1012	/// encountering the closing brace right after the nested block. Now, if we
1013	/// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
1014	/// \c false), the entire block has to be kept on the same line (which is only
1015	/// possible if it fits on the line, only contains a single statement, etc.
1016	///
1017	/// If \p NewLine is true, we format the nested block on separate lines, i.e.
1018	/// break after the "{", format all lines with correct indentation and the put
1019	/// the closing "}" on yet another new line.
1020	///
1021	/// This enables us to keep the simple structure of the
1022	/// \c UnwrappedLineFormatter, where we only have two options for each token:
1023	/// break or don't break.
1024	bool formatChildren(LineState &State, bool NewLine, bool DryRun,
1025	unsigned &Penalty) {
1026	const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
1027	bool HasLBrace = LBrace && LBrace->is(Kind: tok::l_brace) && LBrace->is(BBK: BK_Block);
1028	FormatToken &Previous = *State.NextToken->Previous;
1029	if (Previous.Children.size() == 0 || (!HasLBrace && !LBrace->MacroParent)) {
1030	// The previous token does not open a block. Nothing to do. We don't
1031	// assert so that we can simply call this function for all tokens.
1032	return true;
1033	}
1034
1035	if (NewLine || Previous.MacroParent) {
1036	const ParenState &P = State.Stack.back();
1037
1038	int AdditionalIndent =
1039	P.Indent - Previous.Children[0]->Level * Style.IndentWidth;
1040	Penalty +=
1041	BlockFormatter->format(Lines: Previous.Children, DryRun, AdditionalIndent,
1042	/*FixBadIndentation=*/true);
1043	return true;
1044	}
1045
1046	if (Previous.Children[0]->First->MustBreakBefore)
1047	return false;
1048
1049	// Cannot merge into one line if this line ends on a comment.
1050	if (Previous.is(Kind: tok::comment))
1051	return false;
1052
1053	// Cannot merge multiple statements into a single line.
1054	if (Previous.Children.size() > 1)
1055	return false;
1056
1057	const AnnotatedLine *Child = Previous.Children[0];
1058	// We can't put the closing "}" on a line with a trailing comment.
1059	if (Child->Last->isTrailingComment())
1060	return false;
1061
1062	// If the child line exceeds the column limit, we wouldn't want to merge it.
1063	// We add +2 for the trailing " }".
1064	if (Style.ColumnLimit > 0 &&
1065	Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit) {
1066	return false;
1067	}
1068
1069	if (!DryRun) {
1070	Whitespaces->replaceWhitespace(
1071	Tok&: *Child->First, /*Newlines=*/0, /*Spaces=*/1,
1072	/*StartOfTokenColumn=*/State.Column, /*IsAligned=*/false,
1073	InPPDirective: State.Line->InPPDirective);
1074	}
1075	Penalty +=
1076	formatLine(Line: *Child, FirstIndent: State.Column + 1, /*FirstStartColumn=*/0, DryRun);
1077	if (!DryRun)
1078	markFinalized(Tok: Child->First);
1079
1080	State.Column += 1 + Child->Last->TotalLength;
1081	return true;
1082	}
1083
1084	ContinuationIndenter *Indenter;
1085
1086	private:
1087	WhitespaceManager *Whitespaces;
1088	const FormatStyle &Style;
1089	UnwrappedLineFormatter *BlockFormatter;
1090	};
1091
1092	/// Formatter that keeps the existing line breaks.
1093	class NoColumnLimitLineFormatter : public LineFormatter {
1094	public:
1095	NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,
1096	WhitespaceManager *Whitespaces,
1097	const FormatStyle &Style,
1098	UnwrappedLineFormatter *BlockFormatter)
1099	: LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
1100
1101	/// Formats the line, simply keeping all of the input's line breaking
1102	/// decisions.
1103	unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
1104	unsigned FirstStartColumn, bool DryRun) override {
1105	assert(!DryRun);
1106	LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,
1107	Line: &Line, /*DryRun=*/false);
1108	while (State.NextToken) {
1109	bool Newline =
1110	Indenter->mustBreak(State) ||
1111	(Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
1112	unsigned Penalty = 0;
1113	formatChildren(State, NewLine: Newline, /*DryRun=*/false, Penalty);
1114	Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
1115	}
1116	return 0;
1117	}
1118	};
1119
1120	/// Formatter that puts all tokens into a single line without breaks.
1121	class NoLineBreakFormatter : public LineFormatter {
1122	public:
1123	NoLineBreakFormatter(ContinuationIndenter *Indenter,
1124	WhitespaceManager *Whitespaces, const FormatStyle &Style,
1125	UnwrappedLineFormatter *BlockFormatter)
1126	: LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
1127
1128	/// Puts all tokens into a single line.
1129	unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
1130	unsigned FirstStartColumn, bool DryRun) override {
1131	unsigned Penalty = 0;
1132	LineState State =
1133	Indenter->getInitialState(FirstIndent, FirstStartColumn, Line: &Line, DryRun);
1134	while (State.NextToken) {
1135	formatChildren(State, /*NewLine=*/false, DryRun, Penalty);
1136	Indenter->addTokenToState(
1137	State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);
1138	}
1139	return Penalty;
1140	}
1141	};
1142
1143	/// Finds the best way to break lines.
1144	class OptimizingLineFormatter : public LineFormatter {
1145	public:
1146	OptimizingLineFormatter(ContinuationIndenter *Indenter,
1147	WhitespaceManager *Whitespaces,
1148	const FormatStyle &Style,
1149	UnwrappedLineFormatter *BlockFormatter)
1150	: LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
1151
1152	/// Formats the line by finding the best line breaks with line lengths
1153	/// below the column limit.
1154	unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
1155	unsigned FirstStartColumn, bool DryRun) override {
1156	LineState State =
1157	Indenter->getInitialState(FirstIndent, FirstStartColumn, Line: &Line, DryRun);
1158
1159	// If the ObjC method declaration does not fit on a line, we should format
1160	// it with one arg per line.
1161	if (State.Line->Type == LT_ObjCMethodDecl)
1162	State.Stack.back().BreakBeforeParameter = true;
1163
1164	// Find best solution in solution space.
1165	return analyzeSolutionSpace(InitialState&: State, DryRun);
1166	}
1167
1168	private:
1169	struct CompareLineStatePointers {
1170	bool operator()(LineState *obj1, LineState *obj2) const {
1171	return *obj1 < *obj2;
1172	}
1173	};
1174
1175	/// A pair of <penalty, count> that is used to prioritize the BFS on.
1176	///
1177	/// In case of equal penalties, we want to prefer states that were inserted
1178	/// first. During state generation we make sure that we insert states first
1179	/// that break the line as late as possible.
1180	typedef std::pair<unsigned, unsigned> OrderedPenalty;
1181
1182	/// An edge in the solution space from \c Previous->State to \c State,
1183	/// inserting a newline dependent on the \c NewLine.
1184	struct StateNode {
1185	StateNode(const LineState &State, bool NewLine, StateNode *Previous)
1186	: State(State), NewLine(NewLine), Previous(Previous) {}
1187	LineState State;
1188	bool NewLine;
1189	StateNode *Previous;
1190	};
1191
1192	/// An item in the prioritized BFS search queue. The \c StateNode's
1193	/// \c State has the given \c OrderedPenalty.
1194	typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
1195
1196	/// The BFS queue type.
1197	typedef std::priority_queue<QueueItem, SmallVector<QueueItem>,
1198	std::greater<QueueItem>>
1199	QueueType;
1200
1201	/// Analyze the entire solution space starting from \p InitialState.
1202	///
1203	/// This implements a variant of Dijkstra's algorithm on the graph that spans
1204	/// the solution space (\c LineStates are the nodes). The algorithm tries to
1205	/// find the shortest path (the one with lowest penalty) from \p InitialState
1206	/// to a state where all tokens are placed. Returns the penalty.
1207	///
1208	/// If \p DryRun is \c false, directly applies the changes.
1209	unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {
1210	std::set<LineState *, CompareLineStatePointers> Seen;
1211
1212	// Increasing count of \c StateNode items we have created. This is used to
1213	// create a deterministic order independent of the container.
1214	unsigned Count = 0;
1215	QueueType Queue;
1216
1217	// Insert start element into queue.
1218	StateNode *RootNode =
1219	new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
1220	Queue.push(x: QueueItem(OrderedPenalty(0, Count), RootNode));
1221	++Count;
1222
1223	unsigned Penalty = 0;
1224
1225	// While not empty, take first element and follow edges.
1226	while (!Queue.empty()) {
1227	// Quit if we still haven't found a solution by now.
1228	if (Count > 25'000'000)
1229	return 0;
1230
1231	Penalty = Queue.top().first.first;
1232	StateNode *Node = Queue.top().second;
1233	if (!Node->State.NextToken) {
1234	LLVM_DEBUG(llvm::dbgs()
1235	<< "\n---\nPenalty for line: " << Penalty << "\n");
1236	break;
1237	}
1238	Queue.pop();
1239
1240	// Cut off the analysis of certain solutions if the analysis gets too
1241	// complex. See description of IgnoreStackForComparison.
1242	if (Count > 50'000)
1243	Node->State.IgnoreStackForComparison = true;
1244
1245	if (!Seen.insert(x: &Node->State).second) {
1246	// State already examined with lower penalty.
1247	continue;
1248	}
1249
1250	FormatDecision LastFormat = Node->State.NextToken->getDecision();
1251	if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
1252	addNextStateToQueue(Penalty, PreviousNode: Node, /*NewLine=*/false, Count: &Count, Queue: &Queue);
1253	if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
1254	addNextStateToQueue(Penalty, PreviousNode: Node, /*NewLine=*/true, Count: &Count, Queue: &Queue);
1255	}
1256
1257	if (Queue.empty()) {
1258	// We were unable to find a solution, do nothing.
1259	// FIXME: Add diagnostic?
1260	LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");
1261	return 0;
1262	}
1263
1264	// Reconstruct the solution.
1265	if (!DryRun)
1266	reconstructPath(State&: InitialState, Best: Queue.top().second);
1267
1268	LLVM_DEBUG(llvm::dbgs()
1269	<< "Total number of analyzed states: " << Count << "\n");
1270	LLVM_DEBUG(llvm::dbgs() << "---\n");
1271
1272	return Penalty;
1273	}
1274
1275	/// Add the following state to the analysis queue \c Queue.
1276	///
1277	/// Assume the current state is \p PreviousNode and has been reached with a
1278	/// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1279	void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1280	bool NewLine, unsigned *Count, QueueType *Queue) {
1281	if (NewLine && !Indenter->canBreak(State: PreviousNode->State))
1282	return;
1283	if (!NewLine && Indenter->mustBreak(State: PreviousNode->State))
1284	return;
1285
1286	StateNode *Node = new (Allocator.Allocate())
1287	StateNode(PreviousNode->State, NewLine, PreviousNode);
1288	if (!formatChildren(State&: Node->State, NewLine, /*DryRun=*/true, Penalty))
1289	return;
1290
1291	Penalty += Indenter->addTokenToState(State&: Node->State, Newline: NewLine, DryRun: true);
1292
1293	Queue->push(x: QueueItem(OrderedPenalty(Penalty, *Count), Node));
1294	++(*Count);
1295	}
1296
1297	/// Applies the best formatting by reconstructing the path in the
1298	/// solution space that leads to \c Best.
1299	void reconstructPath(LineState &State, StateNode *Best) {
1300	llvm::SmallVector<StateNode *> Path;
1301	// We do not need a break before the initial token.
1302	while (Best->Previous) {
1303	Path.push_back(Elt: Best);
1304	Best = Best->Previous;
1305	}
1306	for (const auto &Node : llvm::reverse(C&: Path)) {
1307	unsigned Penalty = 0;
1308	formatChildren(State, NewLine: Node->NewLine, /*DryRun=*/false, Penalty);
1309	Penalty += Indenter->addTokenToState(State, Newline: Node->NewLine, DryRun: false);
1310
1311	LLVM_DEBUG({
1312	printLineState(Node->Previous->State);
1313	if (Node->NewLine) {
1314	llvm::dbgs() << "Penalty for placing "
1315	<< Node->Previous->State.NextToken->Tok.getName()
1316	<< " on a new line: " << Penalty << "\n";
1317	}
1318	});
1319	}
1320	}
1321
1322	llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1323	};
1324
1325	} // anonymous namespace
1326
1327	unsigned UnwrappedLineFormatter::format(
1328	const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
1329	int AdditionalIndent, bool FixBadIndentation, unsigned FirstStartColumn,
1330	unsigned NextStartColumn, unsigned LastStartColumn) {
1331	LineJoiner Joiner(Style, Keywords, Lines);
1332
1333	// Try to look up already computed penalty in DryRun-mode.
1334	std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
1335	&Lines, AdditionalIndent);
1336	auto CacheIt = PenaltyCache.find(x: CacheKey);
1337	if (DryRun && CacheIt != PenaltyCache.end())
1338	return CacheIt->second;
1339
1340	assert(!Lines.empty());
1341	unsigned Penalty = 0;
1342	LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,
1343	AdditionalIndent);
1344	const AnnotatedLine *PrevPrevLine = nullptr;
1345	const AnnotatedLine *PreviousLine = nullptr;
1346	const AnnotatedLine *NextLine = nullptr;
1347
1348	// The minimum level of consecutive lines that have been formatted.
1349	unsigned RangeMinLevel = UINT_MAX;
1350
1351	bool FirstLine = true;
1352	for (const AnnotatedLine *Line =
1353	Joiner.getNextMergedLine(DryRun, IndentTracker);
1354	Line; PrevPrevLine = PreviousLine, PreviousLine = Line, Line = NextLine,
1355	FirstLine = false) {
1356	assert(Line->First);
1357	const AnnotatedLine &TheLine = *Line;
1358	unsigned Indent = IndentTracker.getIndent();
1359
1360	// We continue formatting unchanged lines to adjust their indent, e.g. if a
1361	// scope was added. However, we need to carefully stop doing this when we
1362	// exit the scope of affected lines to prevent indenting the entire
1363	// remaining file if it currently missing a closing brace.
1364	bool PreviousRBrace =
1365	PreviousLine && PreviousLine->startsWith(Tokens: tok::r_brace);
1366	bool ContinueFormatting =
1367	TheLine.Level > RangeMinLevel ||
1368	(TheLine.Level == RangeMinLevel && !PreviousRBrace &&
1369	!TheLine.startsWith(Tokens: tok::r_brace));
1370
1371	bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&
1372	Indent != TheLine.First->OriginalColumn;
1373	bool ShouldFormat = TheLine.Affected || FixIndentation;
1374	// We cannot format this line; if the reason is that the line had a
1375	// parsing error, remember that.
1376	if (ShouldFormat && TheLine.Type == LT_Invalid && Status) {
1377	Status->FormatComplete = false;
1378	Status->Line =
1379	SourceMgr.getSpellingLineNumber(Loc: TheLine.First->Tok.getLocation());
1380	}
1381
1382	if (ShouldFormat && TheLine.Type != LT_Invalid) {
1383	if (!DryRun) {
1384	bool LastLine = TheLine.First->is(Kind: tok::eof);
1385	formatFirstToken(Line: TheLine, PreviousLine, PrevPrevLine, Lines, Indent,
1386	NewlineIndent: LastLine ? LastStartColumn : NextStartColumn + Indent);
1387	}
1388
1389	NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1390	unsigned ColumnLimit = getColumnLimit(InPPDirective: TheLine.InPPDirective, NextLine);
1391	bool FitsIntoOneLine =
1392	!TheLine.ContainsMacroCall &&
1393	(TheLine.Last->TotalLength + Indent <= ColumnLimit ||
1394	(TheLine.Type == LT_ImportStatement &&
1395	(!Style.isJavaScript() || !Style.JavaScriptWrapImports)) ||
1396	(Style.isCSharp() &&
1397	TheLine.InPPDirective)); // don't split #regions in C#
1398	if (Style.ColumnLimit == 0) {
1399	NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)
1400	.formatLine(Line: TheLine, FirstIndent: NextStartColumn + Indent,
1401	FirstStartColumn: FirstLine ? FirstStartColumn : 0, DryRun);
1402	} else if (FitsIntoOneLine) {
1403	Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)
1404	.formatLine(Line: TheLine, FirstIndent: NextStartColumn + Indent,
1405	FirstStartColumn: FirstLine ? FirstStartColumn : 0, DryRun);
1406	} else {
1407	Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)
1408	.formatLine(Line: TheLine, FirstIndent: NextStartColumn + Indent,
1409	FirstStartColumn: FirstLine ? FirstStartColumn : 0, DryRun);
1410	}
1411	RangeMinLevel = std::min(a: RangeMinLevel, b: TheLine.Level);
1412	} else {
1413	// If no token in the current line is affected, we still need to format
1414	// affected children.
1415	if (TheLine.ChildrenAffected) {
1416	for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)
1417	if (!Tok->Children.empty())
1418	format(Lines: Tok->Children, DryRun);
1419	}
1420
1421	// Adapt following lines on the current indent level to the same level
1422	// unless the current \c AnnotatedLine is not at the beginning of a line.
1423	bool StartsNewLine =
1424	TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;
1425	if (StartsNewLine)
1426	IndentTracker.adjustToUnmodifiedLine(Line: TheLine);
1427	if (!DryRun) {
1428	bool ReformatLeadingWhitespace =
1429	StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||
1430	TheLine.LeadingEmptyLinesAffected);
1431	// Format the first token.
1432	if (ReformatLeadingWhitespace) {
1433	formatFirstToken(Line: TheLine, PreviousLine, PrevPrevLine, Lines,
1434	Indent: TheLine.First->OriginalColumn,
1435	NewlineIndent: TheLine.First->OriginalColumn);
1436	} else {
1437	Whitespaces->addUntouchableToken(Tok: *TheLine.First,
1438	InPPDirective: TheLine.InPPDirective);
1439	}
1440
1441	// Notify the WhitespaceManager about the unchanged whitespace.
1442	for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)
1443	Whitespaces->addUntouchableToken(Tok: *Tok, InPPDirective: TheLine.InPPDirective);
1444	}
1445	NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1446	RangeMinLevel = UINT_MAX;
1447	}
1448	if (!DryRun)
1449	markFinalized(Tok: TheLine.First);
1450	}
1451	PenaltyCache[CacheKey] = Penalty;
1452	return Penalty;
1453	}
1454
1455	static auto computeNewlines(const AnnotatedLine &Line,
1456	const AnnotatedLine *PreviousLine,
1457	const AnnotatedLine *PrevPrevLine,
1458	const SmallVectorImpl<AnnotatedLine *> &Lines,
1459	const FormatStyle &Style) {
1460	const auto &RootToken = *Line.First;
1461	auto Newlines =
1462	std::min(a: RootToken.NewlinesBefore, b: Style.MaxEmptyLinesToKeep + 1);
1463	// Remove empty lines before "}" where applicable.
1464	if (RootToken.is(Kind: tok::r_brace) &&
1465	(!RootToken.Next ||
1466	(RootToken.Next->is(Kind: tok::semi) && !RootToken.Next->Next)) &&
1467	// Do not remove empty lines before namespace closing "}".
1468	!getNamespaceToken(Line: &Line, AnnotatedLines: Lines)) {
1469	Newlines = std::min(a: Newlines, b: 1u);
1470	}
1471	// Remove empty lines at the start of nested blocks (lambdas/arrow functions)
1472	if (!PreviousLine && Line.Level > 0)
1473	Newlines = std::min(a: Newlines, b: 1u);
1474	if (Newlines == 0 && !RootToken.IsFirst)
1475	Newlines = 1;
1476	if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1477	Newlines = 0;
1478
1479	// Remove empty lines after "{".
1480	if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1481	PreviousLine->Last->is(Kind: tok::l_brace) &&
1482	!PreviousLine->startsWithNamespace() &&
1483	!(PrevPrevLine && PrevPrevLine->startsWithNamespace() &&
1484	PreviousLine->startsWith(Tokens: tok::l_brace)) &&
1485	!startsExternCBlock(Line: *PreviousLine)) {
1486	Newlines = 1;
1487	}
1488
1489	// Insert or remove empty line before access specifiers.
1490	if (PreviousLine && RootToken.isAccessSpecifier()) {
1491	switch (Style.EmptyLineBeforeAccessModifier) {
1492	case FormatStyle::ELBAMS_Never:
1493	if (Newlines > 1)
1494	Newlines = 1;
1495	break;
1496	case FormatStyle::ELBAMS_Leave:
1497	Newlines = std::max(a: RootToken.NewlinesBefore, b: 1u);
1498	break;
1499	case FormatStyle::ELBAMS_LogicalBlock:
1500	if (PreviousLine->Last->isOneOf(K1: tok::semi, K2: tok::r_brace) && Newlines <= 1)
1501	Newlines = 2;
1502	if (PreviousLine->First->isAccessSpecifier())
1503	Newlines = 1; // Previous is an access modifier remove all new lines.
1504	break;
1505	case FormatStyle::ELBAMS_Always: {
1506	const FormatToken *previousToken;
1507	if (PreviousLine->Last->is(Kind: tok::comment))
1508	previousToken = PreviousLine->Last->getPreviousNonComment();
1509	else
1510	previousToken = PreviousLine->Last;
1511	if ((!previousToken || previousToken->isNot(Kind: tok::l_brace)) &&
1512	Newlines <= 1) {
1513	Newlines = 2;
1514	}
1515	} break;
1516	}
1517	}
1518
1519	// Insert or remove empty line after access specifiers.
1520	if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
1521	(!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline)) {
1522	// EmptyLineBeforeAccessModifier is handling the case when two access
1523	// modifiers follow each other.
1524	if (!RootToken.isAccessSpecifier()) {
1525	switch (Style.EmptyLineAfterAccessModifier) {
1526	case FormatStyle::ELAAMS_Never:
1527	Newlines = 1;
1528	break;
1529	case FormatStyle::ELAAMS_Leave:
1530	Newlines = std::max(a: Newlines, b: 1u);
1531	break;
1532	case FormatStyle::ELAAMS_Always:
1533	if (RootToken.is(Kind: tok::r_brace)) // Do not add at end of class.
1534	Newlines = 1u;
1535	else
1536	Newlines = std::max(a: Newlines, b: 2u);
1537	break;
1538	}
1539	}
1540	}
1541
1542	return Newlines;
1543	}
1544
1545	void UnwrappedLineFormatter::formatFirstToken(
1546	const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,
1547	const AnnotatedLine *PrevPrevLine,
1548	const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,
1549	unsigned NewlineIndent) {
1550	FormatToken &RootToken = *Line.First;
1551	if (RootToken.is(Kind: tok::eof)) {
1552	unsigned Newlines =
1553	std::min(a: RootToken.NewlinesBefore,
1554	b: Style.KeepEmptyLinesAtEOF ? Style.MaxEmptyLinesToKeep + 1 : 1);
1555	unsigned TokenIndent = Newlines ? NewlineIndent : 0;
1556	Whitespaces->replaceWhitespace(Tok&: RootToken, Newlines, Spaces: TokenIndent,
1557	StartOfTokenColumn: TokenIndent);
1558	return;
1559	}
1560
1561	if (RootToken.Newlines < 0) {
1562	RootToken.Newlines =
1563	computeNewlines(Line, PreviousLine, PrevPrevLine, Lines, Style);
1564	assert(RootToken.Newlines >= 0);
1565	}
1566
1567	if (RootToken.Newlines > 0)
1568	Indent = NewlineIndent;
1569
1570	// Preprocessor directives get indented before the hash only if specified. In
1571	// Javascript import statements are indented like normal statements.
1572	if (!Style.isJavaScript() &&
1573	Style.IndentPPDirectives != FormatStyle::PPDIS_BeforeHash &&
1574	(Line.Type == LT_PreprocessorDirective ||
1575	Line.Type == LT_ImportStatement)) {
1576	Indent = 0;
1577	}
1578
1579	Whitespaces->replaceWhitespace(Tok&: RootToken, Newlines: RootToken.Newlines, Spaces: Indent, StartOfTokenColumn: Indent,
1580	/*IsAligned=*/false,
1581	InPPDirective: Line.InPPDirective &&
1582	!RootToken.HasUnescapedNewline);
1583	}
1584
1585	unsigned
1586	UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,
1587	const AnnotatedLine *NextLine) const {
1588	// In preprocessor directives reserve two chars for trailing " \" if the
1589	// next line continues the preprocessor directive.
1590	bool ContinuesPPDirective =
1591	InPPDirective &&
1592	// If there is no next line, this is likely a child line and the parent
1593	// continues the preprocessor directive.
1594	(!NextLine ||
1595	(NextLine->InPPDirective &&
1596	// If there is an unescaped newline between this line and the next, the
1597	// next line starts a new preprocessor directive.
1598	!NextLine->First->HasUnescapedNewline));
1599	return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);
1600	}
1601
1602	} // namespace format
1603	} // namespace clang
1604