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