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