Bug Summary

File:clang/lib/Format/UnwrappedLineFormatter.cpp
Warning:line 1214, column 11
Access to field 'NewlinesBefore' results in a dereference of a null pointer (loaded from field 'First')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name UnwrappedLineFormatter.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -relaxed-aliasing -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D CLANG_ROUND_TRIP_CC1_ARGS=ON -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/clang/lib/Format -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/include -I tools/clang/include -I include -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -ferror-limit 19 -fvisibility-inlines-hidden -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-26-234817-15343-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp
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
17namespace clang {
18namespace format {
19
20namespace {
21
22bool 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.
38class LevelIndentTracker {
39public:
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
94private:
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 overridden 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
146const 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 <bool> (StartLineIndex < AnnotatedLines
.size()) ? void (0) : __assert_fail ("StartLineIndex < AnnotatedLines.size()"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 154, __extension__ __PRETTY_FUNCTION__))
;
155 return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();
156}
157
158StringRef getNamespaceTokenText(const AnnotatedLine *Line) {
159 const FormatToken *NamespaceToken = Line->First->getNamespaceToken();
160 return NamespaceToken ? NamespaceToken->TokenText : StringRef();
161}
162
163StringRef 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
171class LineJoiner {
172public:
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)
22
Assuming field 'Next' is not equal to field 'End'
23
Taking false branch
40
Assuming field 'Next' is not equal to field 'End'
41
Taking false branch
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)
24
Assuming 'MergedLines' is <= 0
42
Assuming 'MergedLines' is <= 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
24.1
'DryRun' is false
42.1
'DryRun' is false
)
25
Taking true branch
43
Taking true branch
193 for (unsigned i = 0; i < MergedLines; ++i)
26
Loop condition is false. Execution continues on line 195
44
Loop condition is false. Execution continues on line 195
194 join(*Next[0], *Next[i + 1]);
195 Next = Next + MergedLines + 1;
196 return Current;
27
Returning pointer (loaded from 'Current'), which participates in a condition later
45
Returning pointer (loaded from 'Current'), which participates in a condition later
197 }
198
199private:
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 <bool> (!A.Last->Next) ? void (0) : __assert_fail
("!A.Last->Next", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 738, __extension__ __PRETTY_FUNCTION__))
;
739 assert(!B.First->Previous)(static_cast <bool> (!B.First->Previous) ? void (0) :
__assert_fail ("!B.First->Previous", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 739, __extension__ __PRETTY_FUNCTION__))
;
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
760static 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 NDEBUG
769static 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.
780class LineFormatter {
781public:
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
795protected:
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
0.1
'LBrace' is non-null
|| LBrace->isNot(tok::l_brace) || LBrace->isNot(BK_Block) ||
2
Taking false branch
821 Previous.Children.size() == 0)
1
Assuming the condition is false
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) {
3
Assuming 'NewLine' is true
4
Taking true branch
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 &&
5
Assuming field 'LambdaBodyIndentation' is not equal to 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,
6
Calling 'UnwrappedLineFormatter::format'
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
885private:
886 WhitespaceManager *Whitespaces;
887 const FormatStyle &Style;
888 UnwrappedLineFormatter *BlockFormatter;
889};
890
891/// Formatter that keeps the existing line breaks.
892class NoColumnLimitLineFormatter : public LineFormatter {
893public:
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 <bool> (!DryRun) ? void (0) : __assert_fail
("!DryRun", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 904, __extension__ __PRETTY_FUNCTION__))
;
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.
920class NoLineBreakFormatter : public LineFormatter {
921public:
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.
943class OptimizingLineFormatter : public LineFormatter {
944public:
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
967private:
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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "\n---\nPenalty for line: "
<< Penalty << "\n"; } } while (false)
1030 << "\n---\nPenalty for line: " << Penalty << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "\n---\nPenalty for line: "
<< Penalty << "\n"; } } 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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "Could not find a solution.\n"
; } } 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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "Total number of analyzed states: "
<< Count << "\n"; } } while (false)
1063 << "Total number of analyzed states: " << Count << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "Total number of analyzed states: "
<< Count << "\n"; } } while (false)
;
1064 LLVM_DEBUG(llvm::dbgs() << "---\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "---\n"; } } 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);
1104
1105 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1106 printLineState((*I)->Previous->State);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1107 if ((*I)->NewLine) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1108 llvm::dbgs() << "Penalty for placing "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1109 << (*I)->Previous->State.NextToken->Tok.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1110 << " on a new line: " << Penalty << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1111 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
1112 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { { printLineState((*I)->Previous->
State); if ((*I)->NewLine) { llvm::dbgs() << "Penalty for placing "
<< (*I)->Previous->State.NextToken->Tok.getName
() << " on a new line: " << Penalty << "\n"
; } }; } } while (false)
;
1113 }
1114 }
1115
1116 llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1117};
1118
1119} // anonymous namespace
1120
1121unsigned 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
18.1
'DryRun' is false
36.1
'DryRun' is false
&& CacheIt != PenaltyCache.end())
7
Assuming 'DryRun' is false
8
Taking false branch
19
Taking false branch
37
Taking false branch
1132 return CacheIt->second;
1133
1134 assert(!Lines.empty())(static_cast <bool> (!Lines.empty()) ? void (0) : __assert_fail
("!Lines.empty()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 1134, __extension__ __PRETTY_FUNCTION__))
;
9
'?' condition is true
20
'?' condition is true
38
'?' condition is true
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 =
10
Loop condition is true. Entering loop body
29
Loop condition is true. Entering loop body
47
Loop condition is true. Entering loop body
1147 Joiner.getNextMergedLine(DryRun, IndentTracker);
21
Calling 'LineJoiner::getNextMergedLine'
28
Returning from 'LineJoiner::getNextMergedLine'
39
Calling 'LineJoiner::getNextMergedLine'
46
Returning from 'LineJoiner::getNextMergedLine'
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
10.1
'PreviousLine' is null
29.1
'PreviousLine' is null
47.1
'PreviousLine' is null
&& PreviousLine->startsWith(tok::r_brace);
1158 bool ContinueFormatting =
1159 TheLine.Level > RangeMinLevel
10.2
'RangeMinLevel' is >= field 'Level'
29.2
'RangeMinLevel' is >= field 'Level'
47.2
'RangeMinLevel' is >= field 'Level'
||
1160 (TheLine.Level == RangeMinLevel && !PreviousRBrace &&
11
Assuming 'RangeMinLevel' is not equal to field 'Level'
30
Assuming 'RangeMinLevel' is not equal to field 'Level'
48
Assuming 'RangeMinLevel' is not equal to field 'Level'
1161 !TheLine.startsWith(tok::r_brace));
1162
1163 bool FixIndentation = (FixBadIndentation
11.1
'FixBadIndentation' is true
30.1
'FixBadIndentation' is false
48.1
'FixBadIndentation' is false
|| ContinueFormatting
30.2
'ContinueFormatting' is false
48.2
'ContinueFormatting' is false
) &&
1164 Indent != TheLine.First->OriginalColumn;
12
Assuming 'Indent' is equal to field 'OriginalColumn'
1165 bool ShouldFormat = TheLine.Affected || FixIndentation;
13
Assuming field 'Affected' is false
31
Assuming field 'Affected' is false
49
Assuming field 'Affected' is false
1166 // We cannot format this line; if the reason is that the line had a
1167 // parsing error, remember that.
1168 if (ShouldFormat
13.1
'ShouldFormat' is false
31.1
'ShouldFormat' is false
49.1
'ShouldFormat' is false
&& TheLine.Type == LT_Invalid && Status) {
1169 Status->FormatComplete = false;
1170 Status->Line =
1171 SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());
1172 }
1173
1174 if (ShouldFormat
13.2
'ShouldFormat' is false
31.2
'ShouldFormat' is false
49.2
'ShouldFormat' is false
&& 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)
14
Assuming field 'ChildrenAffected' is true
15
Taking true branch
32
Assuming field 'ChildrenAffected' is true
33
Taking true branch
50
Assuming field 'ChildrenAffected' is true
51
Taking true branch
1207 for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)
16
Loop condition is true. Entering loop body
34
Loop condition is true. Entering loop body
52
Assuming pointer value is null
1208 if (!Tok->Children.empty())
17
Taking true branch
35
Taking true branch
1209 format(Tok->Children, DryRun);
18
Calling 'UnwrappedLineFormatter::format'
36
Calling 'UnwrappedLineFormatter::format'
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;
53
Access to field 'NewlinesBefore' results in a dereference of a null pointer (loaded from field 'First')
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
1246void 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
1351unsigned
1352UnwrappedLineFormatter::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