Bug Summary

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