Bug Summary

File:clang/lib/Format/UnwrappedLineFormatter.cpp
Warning:line 1159, 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-10/lib/clang/10.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-10~++20200112100611+7fa5290d5bd/build-llvm/tools/clang/lib/Format -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/lib/Format -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10/lib/clang/10.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-10~++20200112100611+7fa5290d5bd/build-llvm/tools/clang/lib/Format -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd=. -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-01-13-084841-49055-1 -x c++ /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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 function block with left brace unwrapped
296 if (TheLine->Last->is(TT_FunctionLBrace) &&
297 TheLine->First != TheLine->Last) {
298 return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
299 }
300 // Try to merge a control statement block with left brace unwrapped
301 if (TheLine->Last->is(tok::l_brace) && TheLine->First != TheLine->Last &&
302 TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) {
303 return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never
304 ? tryMergeSimpleBlock(I, E, Limit)
305 : 0;
306 }
307 // Try to merge a control statement block with left brace wrapped
308 if (I[1]->First->is(tok::l_brace) &&
309 (TheLine->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for,
310 tok::kw_switch, tok::kw_try, tok::kw_do) ||
311 (TheLine->First->is(tok::r_brace) && TheLine->First->Next &&
312 TheLine->First->Next->isOneOf(tok::kw_else, tok::kw_catch))) &&
313 Style.BraceWrapping.AfterControlStatement ==
314 FormatStyle::BWACS_MultiLine) {
315 // If possible, merge the next line's wrapped left brace with the current
316 // line. Otherwise, leave it on the next line, as this is a multi-line
317 // control statement.
318 return (Style.ColumnLimit == 0 ||
319 TheLine->Last->TotalLength <= Style.ColumnLimit)
320 ? 1
321 : 0;
322 } else if (I[1]->First->is(tok::l_brace) &&
323 TheLine->First->isOneOf(tok::kw_if, tok::kw_while,
324 tok::kw_for)) {
325 return (Style.BraceWrapping.AfterControlStatement ==
326 FormatStyle::BWACS_Always)
327 ? tryMergeSimpleBlock(I, E, Limit)
328 : 0;
329 } else if (I[1]->First->is(tok::l_brace) &&
330 TheLine->First->isOneOf(tok::kw_else, tok::kw_catch) &&
331 Style.BraceWrapping.AfterControlStatement ==
332 FormatStyle::BWACS_MultiLine) {
333 // This case if different from the upper BWACS_MultiLine processing
334 // in that a preceding r_brace is not on the same line as else/catch
335 // most likely because of BeforeElse/BeforeCatch set to true.
336 // If the line length doesn't fit ColumnLimit, leave l_brace on the
337 // next line to respect the BWACS_MultiLine.
338 return (Style.ColumnLimit == 0 ||
339 TheLine->Last->TotalLength <= Style.ColumnLimit)
340 ? 1
341 : 0;
342 }
343 // Try to merge either empty or one-line block if is precedeed by control
344 // statement token
345 if (TheLine->First->is(tok::l_brace) && TheLine->First == TheLine->Last &&
346 I != AnnotatedLines.begin() &&
347 I[-1]->First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for)) {
348 unsigned MergedLines = 0;
349 if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never) {
350 MergedLines = tryMergeSimpleBlock(I - 1, E, Limit);
351 // If we managed to merge the block, discard the first merged line
352 // since we are merging starting from I.
353 if (MergedLines > 0)
354 --MergedLines;
355 }
356 return MergedLines;
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 // Try to merge a block with left brace wrapped that wasn't yet covered
371 if (TheLine->Last->is(tok::l_brace)) {
372 return !Style.BraceWrapping.AfterFunction ||
373 (I[1]->First->is(tok::r_brace) &&
374 !Style.BraceWrapping.SplitEmptyRecord)
375 ? tryMergeSimpleBlock(I, E, Limit)
376 : 0;
377 }
378 // Try to merge a function block with left brace wrapped
379 if (I[1]->First->is(TT_FunctionLBrace) &&
380 Style.BraceWrapping.AfterFunction) {
381 if (I[1]->Last->is(TT_LineComment))
382 return 0;
383
384 // Check for Limit <= 2 to account for the " {".
385 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
386 return 0;
387 Limit -= 2;
388
389 unsigned MergedLines = 0;
390 if (MergeShortFunctions ||
391 (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
392 I[1]->First == I[1]->Last && I + 2 != E &&
393 I[2]->First->is(tok::r_brace))) {
394 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
395 // If we managed to merge the block, count the function header, which is
396 // on a separate line.
397 if (MergedLines > 0)
398 ++MergedLines;
399 }
400 return MergedLines;
401 }
402 if (TheLine->First->is(tok::kw_if)) {
403 return Style.AllowShortIfStatementsOnASingleLine
404 ? tryMergeSimpleControlStatement(I, E, Limit)
405 : 0;
406 }
407 if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
408 return Style.AllowShortLoopsOnASingleLine
409 ? tryMergeSimpleControlStatement(I, E, Limit)
410 : 0;
411 }
412 if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
413 return Style.AllowShortCaseLabelsOnASingleLine
414 ? tryMergeShortCaseLabels(I, E, Limit)
415 : 0;
416 }
417 if (TheLine->InPPDirective &&
418 (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
419 return tryMergeSimplePPDirective(I, E, Limit);
420 }
421 return 0;
422 }
423
424 unsigned
425 tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
426 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
427 unsigned Limit) {
428 if (Limit == 0)
429 return 0;
430 if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
431 return 0;
432 if (1 + I[1]->Last->TotalLength > Limit)
433 return 0;
434 return 1;
435 }
436
437 unsigned tryMergeSimpleControlStatement(
438 SmallVectorImpl<AnnotatedLine *>::const_iterator I,
439 SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
440 if (Limit == 0)
441 return 0;
442 if (Style.BraceWrapping.AfterControlStatement ==
443 FormatStyle::BWACS_Always &&
444 I[1]->First->is(tok::l_brace) &&
445 Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never)
446 return 0;
447 if (I[1]->InPPDirective != (*I)->InPPDirective ||
448 (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
449 return 0;
450 Limit = limitConsideringMacros(I + 1, E, Limit);
451 AnnotatedLine &Line = **I;
452 if (Line.Last->isNot(tok::r_paren))
453 return 0;
454 if (1 + I[1]->Last->TotalLength > Limit)
455 return 0;
456 if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,
457 TT_LineComment))
458 return 0;
459 // Only inline simple if's (no nested if or else), unless specified
460 if (Style.AllowShortIfStatementsOnASingleLine != FormatStyle::SIS_Always) {
461 if (I + 2 != E && Line.startsWith(tok::kw_if) &&
462 I[2]->First->is(tok::kw_else))
463 return 0;
464 }
465 return 1;
466 }
467
468 unsigned
469 tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
470 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
471 unsigned Limit) {
472 if (Limit == 0 || I + 1 == E ||
473 I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
474 return 0;
475 if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))
476 return 0;
477 unsigned NumStmts = 0;
478 unsigned Length = 0;
479 bool EndsWithComment = false;
480 bool InPPDirective = I[0]->InPPDirective;
481 const unsigned Level = I[0]->Level;
482 for (; NumStmts < 3; ++NumStmts) {
483 if (I + 1 + NumStmts == E)
484 break;
485 const AnnotatedLine *Line = I[1 + NumStmts];
486 if (Line->InPPDirective != InPPDirective)
487 break;
488 if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
489 break;
490 if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
491 tok::kw_while) ||
492 EndsWithComment)
493 return 0;
494 if (Line->First->is(tok::comment)) {
495 if (Level != Line->Level)
496 return 0;
497 SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
498 for (; J != E; ++J) {
499 Line = *J;
500 if (Line->InPPDirective != InPPDirective)
501 break;
502 if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
503 break;
504 if (Line->First->isNot(tok::comment) || Level != Line->Level)
505 return 0;
506 }
507 break;
508 }
509 if (Line->Last->is(tok::comment))
510 EndsWithComment = true;
511 Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
512 }
513 if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
514 return 0;
515 return NumStmts;
516 }
517
518 unsigned
519 tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
520 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
521 unsigned Limit) {
522 AnnotatedLine &Line = **I;
523
524 // Don't merge ObjC @ keywords and methods.
525 // FIXME: If an option to allow short exception handling clauses on a single
526 // line is added, change this to not return for @try and friends.
527 if (Style.Language != FormatStyle::LK_Java &&
528 Line.First->isOneOf(tok::at, tok::minus, tok::plus))
529 return 0;
530
531 // Check that the current line allows merging. This depends on whether we
532 // are in a control flow statements as well as several style flags.
533 if (Line.First->isOneOf(tok::kw_else, tok::kw_case) ||
534 (Line.First->Next && Line.First->Next->is(tok::kw_else)))
535 return 0;
536 // default: in switch statement
537 if (Line.First->is(tok::kw_default)) {
538 const FormatToken *Tok = Line.First->getNextNonComment();
539 if (Tok && Tok->is(tok::colon))
540 return 0;
541 }
542 if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
543 tok::kw___try, tok::kw_catch, tok::kw___finally,
544 tok::kw_for, tok::r_brace, Keywords.kw___except)) {
545 if (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never)
546 return 0;
547 // Don't merge when we can't except the case when
548 // the control statement block is empty
549 if (!Style.AllowShortIfStatementsOnASingleLine &&
550 Line.startsWith(tok::kw_if) &&
551 !Style.BraceWrapping.AfterControlStatement &&
552 !I[1]->First->is(tok::r_brace))
553 return 0;
554 if (!Style.AllowShortIfStatementsOnASingleLine &&
555 Line.startsWith(tok::kw_if) &&
556 Style.BraceWrapping.AfterControlStatement ==
557 FormatStyle::BWACS_Always &&
558 I + 2 != E && !I[2]->First->is(tok::r_brace))
559 return 0;
560 if (!Style.AllowShortLoopsOnASingleLine &&
561 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
562 !Style.BraceWrapping.AfterControlStatement &&
563 !I[1]->First->is(tok::r_brace))
564 return 0;
565 if (!Style.AllowShortLoopsOnASingleLine &&
566 Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for) &&
567 Style.BraceWrapping.AfterControlStatement ==
568 FormatStyle::BWACS_Always &&
569 I + 2 != E && !I[2]->First->is(tok::r_brace))
570 return 0;
571 // FIXME: Consider an option to allow short exception handling clauses on
572 // a single line.
573 // FIXME: This isn't covered by tests.
574 // FIXME: For catch, __except, __finally the first token on the line
575 // is '}', so this isn't correct here.
576 if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
577 Keywords.kw___except, tok::kw___finally))
578 return 0;
579 }
580
581 if (Line.Last->is(tok::l_brace)) {
582 FormatToken *Tok = I[1]->First;
583 if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
584 (Tok->getNextNonComment() == nullptr ||
585 Tok->getNextNonComment()->is(tok::semi))) {
586 // We merge empty blocks even if the line exceeds the column limit.
587 Tok->SpacesRequiredBefore = Style.SpaceInEmptyBlock ? 1 : 0;
588 Tok->CanBreakBefore = true;
589 return 1;
590 } else if (Limit != 0 && !Line.startsWithNamespace() &&
591 !startsExternCBlock(Line)) {
592 // We don't merge short records.
593 FormatToken *RecordTok = Line.First;
594 // Skip record modifiers.
595 while (RecordTok->Next &&
596 RecordTok->isOneOf(tok::kw_typedef, tok::kw_export,
597 Keywords.kw_declare, Keywords.kw_abstract,
598 tok::kw_default))
599 RecordTok = RecordTok->Next;
600 if (RecordTok &&
601 RecordTok->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct,
602 Keywords.kw_interface))
603 return 0;
604
605 // Check that we still have three lines and they fit into the limit.
606 if (I + 2 == E || I[2]->Type == LT_Invalid)
607 return 0;
608 Limit = limitConsideringMacros(I + 2, E, Limit);
609
610 if (!nextTwoLinesFitInto(I, Limit))
611 return 0;
612
613 // Second, check that the next line does not contain any braces - if it
614 // does, readability declines when putting it into a single line.
615 if (I[1]->Last->is(TT_LineComment))
616 return 0;
617 do {
618 if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
619 return 0;
620 Tok = Tok->Next;
621 } while (Tok);
622
623 // Last, check that the third line starts with a closing brace.
624 Tok = I[2]->First;
625 if (Tok->isNot(tok::r_brace))
626 return 0;
627
628 // Don't merge "if (a) { .. } else {".
629 if (Tok->Next && Tok->Next->is(tok::kw_else))
630 return 0;
631
632 // Don't merge a trailing multi-line control statement block like:
633 // } else if (foo &&
634 // bar)
635 // { <-- current Line
636 // baz();
637 // }
638 if (Line.First == Line.Last &&
639 Style.BraceWrapping.AfterControlStatement ==
640 FormatStyle::BWACS_MultiLine)
641 return 0;
642
643 return 2;
644 }
645 } else if (I[1]->First->is(tok::l_brace)) {
646 if (I[1]->Last->is(TT_LineComment))
647 return 0;
648
649 // Check for Limit <= 2 to account for the " {".
650 if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))
651 return 0;
652 Limit -= 2;
653 unsigned MergedLines = 0;
654 if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never ||
655 (I[1]->First == I[1]->Last && I + 2 != E &&
656 I[2]->First->is(tok::r_brace))) {
657 MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
658 // If we managed to merge the block, count the statement header, which
659 // is on a separate line.
660 if (MergedLines > 0)
661 ++MergedLines;
662 }
663 return MergedLines;
664 }
665 return 0;
666 }
667
668 /// Returns the modified column limit for \p I if it is inside a macro and
669 /// needs a trailing '\'.
670 unsigned
671 limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
672 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
673 unsigned Limit) {
674 if (I[0]->InPPDirective && I + 1 != E &&
675 !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
676 return Limit < 2 ? 0 : Limit - 2;
677 }
678 return Limit;
679 }
680
681 bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
682 unsigned Limit) {
683 if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
684 return false;
685 return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
686 }
687
688 bool containsMustBreak(const AnnotatedLine *Line) {
689 for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
690 if (Tok->MustBreakBefore)
691 return true;
692 }
693 return false;
694 }
695
696 void join(AnnotatedLine &A, const AnnotatedLine &B) {
697 assert(!A.Last->Next)((!A.Last->Next) ? static_cast<void> (0) : __assert_fail
("!A.Last->Next", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 697, __PRETTY_FUNCTION__))
;
698 assert(!B.First->Previous)((!B.First->Previous) ? static_cast<void> (0) : __assert_fail
("!B.First->Previous", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 698, __PRETTY_FUNCTION__))
;
699 if (B.Affected)
700 A.Affected = true;
701 A.Last->Next = B.First;
702 B.First->Previous = A.Last;
703 B.First->CanBreakBefore = true;
704 unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
705 for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
706 Tok->TotalLength += LengthA;
707 A.Last = Tok;
708 }
709 }
710
711 const FormatStyle &Style;
712 const AdditionalKeywords &Keywords;
713 const SmallVectorImpl<AnnotatedLine *>::const_iterator End;
714
715 SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
716 const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
717};
718
719static void markFinalized(FormatToken *Tok) {
720 for (; Tok; Tok = Tok->Next) {
721 Tok->Finalized = true;
722 for (AnnotatedLine *Child : Tok->Children)
723 markFinalized(Child->First);
724 }
725}
726
727#ifndef NDEBUG
728static void printLineState(const LineState &State) {
729 llvm::dbgs() << "State: ";
730 for (const ParenState &P : State.Stack) {
731 llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
732 << P.LastSpace << "|" << P.NestedBlockIndent << " ";
733 }
734 llvm::dbgs() << State.NextToken->TokenText << "\n";
735}
736#endif
737
738/// Base class for classes that format one \c AnnotatedLine.
739class LineFormatter {
740public:
741 LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,
742 const FormatStyle &Style,
743 UnwrappedLineFormatter *BlockFormatter)
744 : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
745 BlockFormatter(BlockFormatter) {}
746 virtual ~LineFormatter() {}
747
748 /// Formats an \c AnnotatedLine and returns the penalty.
749 ///
750 /// If \p DryRun is \c false, directly applies the changes.
751 virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
752 unsigned FirstStartColumn, bool DryRun) = 0;
753
754protected:
755 /// If the \p State's next token is an r_brace closing a nested block,
756 /// format the nested block before it.
757 ///
758 /// Returns \c true if all children could be placed successfully and adapts
759 /// \p Penalty as well as \p State. If \p DryRun is false, also directly
760 /// creates changes using \c Whitespaces.
761 ///
762 /// The crucial idea here is that children always get formatted upon
763 /// encountering the closing brace right after the nested block. Now, if we
764 /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
765 /// \c false), the entire block has to be kept on the same line (which is only
766 /// possible if it fits on the line, only contains a single statement, etc.
767 ///
768 /// If \p NewLine is true, we format the nested block on separate lines, i.e.
769 /// break after the "{", format all lines with correct indentation and the put
770 /// the closing "}" on yet another new line.
771 ///
772 /// This enables us to keep the simple structure of the
773 /// \c UnwrappedLineFormatter, where we only have two options for each token:
774 /// break or don't break.
775 bool formatChildren(LineState &State, bool NewLine, bool DryRun,
776 unsigned &Penalty) {
777 const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
778 FormatToken &Previous = *State.NextToken->Previous;
779 if (!LBrace
0.1
'LBrace' is non-null
|| LBrace->isNot(tok::l_brace) ||
3
Taking false branch
780 LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
1
Assuming field 'BlockKind' is equal to BK_Block
2
Assuming the condition is false
781 // The previous token does not open a block. Nothing to do. We don't
782 // assert so that we can simply call this function for all tokens.
783 return true;
784
785 if (NewLine) {
4
Assuming 'NewLine' is true
5
Taking true branch
786 int AdditionalIndent = State.Stack.back().Indent -
787 Previous.Children[0]->Level * Style.IndentWidth;
788
789 Penalty +=
790 BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,
6
Calling 'UnwrappedLineFormatter::format'
791 /*FixBadIndentation=*/true);
792 return true;
793 }
794
795 if (Previous.Children[0]->First->MustBreakBefore)
796 return false;
797
798 // Cannot merge into one line if this line ends on a comment.
799 if (Previous.is(tok::comment))
800 return false;
801
802 // Cannot merge multiple statements into a single line.
803 if (Previous.Children.size() > 1)
804 return false;
805
806 const AnnotatedLine *Child = Previous.Children[0];
807 // We can't put the closing "}" on a line with a trailing comment.
808 if (Child->Last->isTrailingComment())
809 return false;
810
811 // If the child line exceeds the column limit, we wouldn't want to merge it.
812 // We add +2 for the trailing " }".
813 if (Style.ColumnLimit > 0 &&
814 Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit)
815 return false;
816
817 if (!DryRun) {
818 Whitespaces->replaceWhitespace(
819 *Child->First, /*Newlines=*/0, /*Spaces=*/1,
820 /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
821 }
822 Penalty +=
823 formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);
824
825 State.Column += 1 + Child->Last->TotalLength;
826 return true;
827 }
828
829 ContinuationIndenter *Indenter;
830
831private:
832 WhitespaceManager *Whitespaces;
833 const FormatStyle &Style;
834 UnwrappedLineFormatter *BlockFormatter;
835};
836
837/// Formatter that keeps the existing line breaks.
838class NoColumnLimitLineFormatter : public LineFormatter {
839public:
840 NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,
841 WhitespaceManager *Whitespaces,
842 const FormatStyle &Style,
843 UnwrappedLineFormatter *BlockFormatter)
844 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
845
846 /// Formats the line, simply keeping all of the input's line breaking
847 /// decisions.
848 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
849 unsigned FirstStartColumn, bool DryRun) override {
850 assert(!DryRun)((!DryRun) ? static_cast<void> (0) : __assert_fail ("!DryRun"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 850, __PRETTY_FUNCTION__))
;
851 LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,
852 &Line, /*DryRun=*/false);
853 while (State.NextToken) {
854 bool Newline =
855 Indenter->mustBreak(State) ||
856 (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
857 unsigned Penalty = 0;
858 formatChildren(State, Newline, /*DryRun=*/false, Penalty);
859 Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
860 }
861 return 0;
862 }
863};
864
865/// Formatter that puts all tokens into a single line without breaks.
866class NoLineBreakFormatter : public LineFormatter {
867public:
868 NoLineBreakFormatter(ContinuationIndenter *Indenter,
869 WhitespaceManager *Whitespaces, const FormatStyle &Style,
870 UnwrappedLineFormatter *BlockFormatter)
871 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
872
873 /// Puts all tokens into a single line.
874 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
875 unsigned FirstStartColumn, bool DryRun) override {
876 unsigned Penalty = 0;
877 LineState State =
878 Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
879 while (State.NextToken) {
880 formatChildren(State, /*NewLine=*/false, DryRun, Penalty);
881 Indenter->addTokenToState(
882 State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);
883 }
884 return Penalty;
885 }
886};
887
888/// Finds the best way to break lines.
889class OptimizingLineFormatter : public LineFormatter {
890public:
891 OptimizingLineFormatter(ContinuationIndenter *Indenter,
892 WhitespaceManager *Whitespaces,
893 const FormatStyle &Style,
894 UnwrappedLineFormatter *BlockFormatter)
895 : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
896
897 /// Formats the line by finding the best line breaks with line lengths
898 /// below the column limit.
899 unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
900 unsigned FirstStartColumn, bool DryRun) override {
901 LineState State =
902 Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
903
904 // If the ObjC method declaration does not fit on a line, we should format
905 // it with one arg per line.
906 if (State.Line->Type == LT_ObjCMethodDecl)
907 State.Stack.back().BreakBeforeParameter = true;
908
909 // Find best solution in solution space.
910 return analyzeSolutionSpace(State, DryRun);
911 }
912
913private:
914 struct CompareLineStatePointers {
915 bool operator()(LineState *obj1, LineState *obj2) const {
916 return *obj1 < *obj2;
917 }
918 };
919
920 /// A pair of <penalty, count> that is used to prioritize the BFS on.
921 ///
922 /// In case of equal penalties, we want to prefer states that were inserted
923 /// first. During state generation we make sure that we insert states first
924 /// that break the line as late as possible.
925 typedef std::pair<unsigned, unsigned> OrderedPenalty;
926
927 /// An edge in the solution space from \c Previous->State to \c State,
928 /// inserting a newline dependent on the \c NewLine.
929 struct StateNode {
930 StateNode(const LineState &State, bool NewLine, StateNode *Previous)
931 : State(State), NewLine(NewLine), Previous(Previous) {}
932 LineState State;
933 bool NewLine;
934 StateNode *Previous;
935 };
936
937 /// An item in the prioritized BFS search queue. The \c StateNode's
938 /// \c State has the given \c OrderedPenalty.
939 typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
940
941 /// The BFS queue type.
942 typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
943 std::greater<QueueItem>>
944 QueueType;
945
946 /// Analyze the entire solution space starting from \p InitialState.
947 ///
948 /// This implements a variant of Dijkstra's algorithm on the graph that spans
949 /// the solution space (\c LineStates are the nodes). The algorithm tries to
950 /// find the shortest path (the one with lowest penalty) from \p InitialState
951 /// to a state where all tokens are placed. Returns the penalty.
952 ///
953 /// If \p DryRun is \c false, directly applies the changes.
954 unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {
955 std::set<LineState *, CompareLineStatePointers> Seen;
956
957 // Increasing count of \c StateNode items we have created. This is used to
958 // create a deterministic order independent of the container.
959 unsigned Count = 0;
960 QueueType Queue;
961
962 // Insert start element into queue.
963 StateNode *Node =
964 new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
965 Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
966 ++Count;
967
968 unsigned Penalty = 0;
969
970 // While not empty, take first element and follow edges.
971 while (!Queue.empty()) {
972 Penalty = Queue.top().first.first;
973 StateNode *Node = Queue.top().second;
974 if (!Node->State.NextToken) {
975 LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "\n---\nPenalty for line: "
<< Penalty << "\n"; } } while (false)
976 << "\n---\nPenalty for line: " << Penalty << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "\n---\nPenalty for line: "
<< Penalty << "\n"; } } while (false)
;
977 break;
978 }
979 Queue.pop();
980
981 // Cut off the analysis of certain solutions if the analysis gets too
982 // complex. See description of IgnoreStackForComparison.
983 if (Count > 50000)
984 Node->State.IgnoreStackForComparison = true;
985
986 if (!Seen.insert(&Node->State).second)
987 // State already examined with lower penalty.
988 continue;
989
990 FormatDecision LastFormat = Node->State.NextToken->Decision;
991 if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
992 addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
993 if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
994 addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
995 }
996
997 if (Queue.empty()) {
998 // We were unable to find a solution, do nothing.
999 // FIXME: Add diagnostic?
1000 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)
;
1001 return 0;
1002 }
1003
1004 // Reconstruct the solution.
1005 if (!DryRun)
1006 reconstructPath(InitialState, Queue.top().second);
1007
1008 LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "Total number of analyzed states: "
<< Count << "\n"; } } while (false)
1009 << "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)
;
1010 LLVM_DEBUG(llvm::dbgs() << "---\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("format-formatter")) { llvm::dbgs() << "---\n"; } } while
(false)
;
1011
1012 return Penalty;
1013 }
1014
1015 /// Add the following state to the analysis queue \c Queue.
1016 ///
1017 /// Assume the current state is \p PreviousNode and has been reached with a
1018 /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1019 void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1020 bool NewLine, unsigned *Count, QueueType *Queue) {
1021 if (NewLine && !Indenter->canBreak(PreviousNode->State))
1022 return;
1023 if (!NewLine && Indenter->mustBreak(PreviousNode->State))
1024 return;
1025
1026 StateNode *Node = new (Allocator.Allocate())
1027 StateNode(PreviousNode->State, NewLine, PreviousNode);
1028 if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
1029 return;
1030
1031 Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
1032
1033 Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
1034 ++(*Count);
1035 }
1036
1037 /// Applies the best formatting by reconstructing the path in the
1038 /// solution space that leads to \c Best.
1039 void reconstructPath(LineState &State, StateNode *Best) {
1040 std::deque<StateNode *> Path;
1041 // We do not need a break before the initial token.
1042 while (Best->Previous) {
1043 Path.push_front(Best);
1044 Best = Best->Previous;
1045 }
1046 for (auto I = Path.begin(), E = Path.end(); I != E; ++I) {
1047 unsigned Penalty = 0;
1048 formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
1049 Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
1050
1051 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)
1052 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)
1053 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)
1054 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)
1055 << (*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)
1056 << " 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)
1057 }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)
1058 })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)
;
1059 }
1060 }
1061
1062 llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1063};
1064
1065} // anonymous namespace
1066
1067unsigned UnwrappedLineFormatter::format(
1068 const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
1069 int AdditionalIndent, bool FixBadIndentation, unsigned FirstStartColumn,
1070 unsigned NextStartColumn, unsigned LastStartColumn) {
1071 LineJoiner Joiner(Style, Keywords, Lines);
1072
1073 // Try to look up already computed penalty in DryRun-mode.
1074 std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
1075 &Lines, AdditionalIndent);
1076 auto CacheIt = PenaltyCache.find(CacheKey);
1077 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
1078 return CacheIt->second;
1079
1080 assert(!Lines.empty())((!Lines.empty()) ? static_cast<void> (0) : __assert_fail
("!Lines.empty()", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/clang/lib/Format/UnwrappedLineFormatter.cpp"
, 1080, __PRETTY_FUNCTION__))
;
9
'?' condition is true
20
'?' condition is true
38
'?' condition is true
1081 unsigned Penalty = 0;
1082 LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,
1083 AdditionalIndent);
1084 const AnnotatedLine *PreviousLine = nullptr;
1085 const AnnotatedLine *NextLine = nullptr;
1086
1087 // The minimum level of consecutive lines that have been formatted.
1088 unsigned RangeMinLevel = UINT_MAX(2147483647 *2U +1U);
1089
1090 bool FirstLine = true;
1091 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
1092 Joiner.getNextMergedLine(DryRun, IndentTracker);
21
Calling 'LineJoiner::getNextMergedLine'
28
Returning from 'LineJoiner::getNextMergedLine'
39
Calling 'LineJoiner::getNextMergedLine'
46
Returning from 'LineJoiner::getNextMergedLine'
1093 Line; Line = NextLine, FirstLine = false) {
1094 const AnnotatedLine &TheLine = *Line;
1095 unsigned Indent = IndentTracker.getIndent();
1096
1097 // We continue formatting unchanged lines to adjust their indent, e.g. if a
1098 // scope was added. However, we need to carefully stop doing this when we
1099 // exit the scope of affected lines to prevent indenting a the entire
1100 // remaining file if it currently missing a closing brace.
1101 bool PreviousRBrace =
1102 PreviousLine
10.1
'PreviousLine' is null
29.1
'PreviousLine' is null
47.1
'PreviousLine' is null
&& PreviousLine->startsWith(tok::r_brace);
1103 bool ContinueFormatting =
1104 TheLine.Level > RangeMinLevel
10.2
'RangeMinLevel' is >= field 'Level'
29.2
'RangeMinLevel' is >= field 'Level'
47.2
'RangeMinLevel' is >= field 'Level'
||
1105 (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'
1106 !TheLine.startsWith(tok::r_brace));
1107
1108 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
) &&
1109 Indent != TheLine.First->OriginalColumn;
12
Assuming 'Indent' is equal to field 'OriginalColumn'
1110 bool ShouldFormat = TheLine.Affected || FixIndentation;
13
Assuming field 'Affected' is false
31
Assuming field 'Affected' is false
49
Assuming field 'Affected' is false
1111 // We cannot format this line; if the reason is that the line had a
1112 // parsing error, remember that.
1113 if (ShouldFormat
13.1
'ShouldFormat' is false
31.1
'ShouldFormat' is false
49.1
'ShouldFormat' is false
&& TheLine.Type == LT_Invalid && Status) {
1114 Status->FormatComplete = false;
1115 Status->Line =
1116 SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());
1117 }
1118
1119 if (ShouldFormat
13.2
'ShouldFormat' is false
31.2
'ShouldFormat' is false
49.2
'ShouldFormat' is false
&& TheLine.Type != LT_Invalid) {
1120 if (!DryRun) {
1121 bool LastLine = Line->First->is(tok::eof);
1122 formatFirstToken(TheLine, PreviousLine, Lines, Indent,
1123 LastLine ? LastStartColumn : NextStartColumn + Indent);
1124 }
1125
1126 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1127 unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine);
1128 bool FitsIntoOneLine =
1129 TheLine.Last->TotalLength + Indent <= ColumnLimit ||
1130 (TheLine.Type == LT_ImportStatement &&
1131 (Style.Language != FormatStyle::LK_JavaScript ||
1132 !Style.JavaScriptWrapImports)) ||
1133 (Style.isCSharp() &&
1134 TheLine.InPPDirective); // don't split #regions in C#
1135 if (Style.ColumnLimit == 0)
1136 NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)
1137 .formatLine(TheLine, NextStartColumn + Indent,
1138 FirstLine ? FirstStartColumn : 0, DryRun);
1139 else if (FitsIntoOneLine)
1140 Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)
1141 .formatLine(TheLine, NextStartColumn + Indent,
1142 FirstLine ? FirstStartColumn : 0, DryRun);
1143 else
1144 Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)
1145 .formatLine(TheLine, NextStartColumn + Indent,
1146 FirstLine ? FirstStartColumn : 0, DryRun);
1147 RangeMinLevel = std::min(RangeMinLevel, TheLine.Level);
1148 } else {
1149 // If no token in the current line is affected, we still need to format
1150 // affected children.
1151 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
1152 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 1159
1153 if (!Tok->Children.empty())
17
Taking true branch
35
Taking true branch
1154 format(Tok->Children, DryRun);
18
Calling 'UnwrappedLineFormatter::format'
36
Calling 'UnwrappedLineFormatter::format'
1155
1156 // Adapt following lines on the current indent level to the same level
1157 // unless the current \c AnnotatedLine is not at the beginning of a line.
1158 bool StartsNewLine =
1159 TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;
54
Access to field 'NewlinesBefore' results in a dereference of a null pointer (loaded from field 'First')
1160 if (StartsNewLine)
1161 IndentTracker.adjustToUnmodifiedLine(TheLine);
1162 if (!DryRun) {
1163 bool ReformatLeadingWhitespace =
1164 StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||
1165 TheLine.LeadingEmptyLinesAffected);
1166 // Format the first token.
1167 if (ReformatLeadingWhitespace)
1168 formatFirstToken(TheLine, PreviousLine, Lines,
1169 TheLine.First->OriginalColumn,
1170 TheLine.First->OriginalColumn);
1171 else
1172 Whitespaces->addUntouchableToken(*TheLine.First,
1173 TheLine.InPPDirective);
1174
1175 // Notify the WhitespaceManager about the unchanged whitespace.
1176 for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)
1177 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
1178 }
1179 NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
1180 RangeMinLevel = UINT_MAX(2147483647 *2U +1U);
1181 }
1182 if (!DryRun)
1183 markFinalized(TheLine.First);
1184 PreviousLine = &TheLine;
1185 }
1186 PenaltyCache[CacheKey] = Penalty;
1187 return Penalty;
1188}
1189
1190void UnwrappedLineFormatter::formatFirstToken(
1191 const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,
1192 const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,
1193 unsigned NewlineIndent) {
1194 FormatToken &RootToken = *Line.First;
1195 if (RootToken.is(tok::eof)) {
1196 unsigned Newlines = std::min(RootToken.NewlinesBefore, 1u);
1197 unsigned TokenIndent = Newlines ? NewlineIndent : 0;
1198 Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,
1199 TokenIndent);
1200 return;
1201 }
1202 unsigned Newlines =
1203 std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1204 // Remove empty lines before "}" where applicable.
1205 if (RootToken.is(tok::r_brace) &&
1206 (!RootToken.Next ||
1207 (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) &&
1208 // Do not remove empty lines before namespace closing "}".
1209 !getNamespaceToken(&Line, Lines))
1210 Newlines = std::min(Newlines, 1u);
1211 // Remove empty lines at the start of nested blocks (lambdas/arrow functions)
1212 if (PreviousLine == nullptr && Line.Level > 0)
1213 Newlines = std::min(Newlines, 1u);
1214 if (Newlines == 0 && !RootToken.IsFirst)
1215 Newlines = 1;
1216 if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1217 Newlines = 0;
1218
1219 // Remove empty lines after "{".
1220 if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1221 PreviousLine->Last->is(tok::l_brace) &&
1222 !PreviousLine->startsWithNamespace() &&
1223 !startsExternCBlock(*PreviousLine))
1224 Newlines = 1;
1225
1226 // Insert extra new line before access specifiers.
1227 if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1228 RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1229 ++Newlines;
1230
1231 // Remove empty lines after access specifiers.
1232 if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
1233 (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline))
1234 Newlines = std::min(1u, Newlines);
1235
1236 if (Newlines)
1237 Indent = NewlineIndent;
1238
1239 // If in Whitemsmiths mode, indent start and end of blocks
1240 if (Style.BreakBeforeBraces == FormatStyle::BS_Whitesmiths) {
1241 if (RootToken.isOneOf(tok::l_brace, tok::r_brace, tok::kw_case))
1242 Indent += Style.IndentWidth;
1243 }
1244
1245 // Preprocessor directives get indented before the hash only if specified
1246 if (Style.IndentPPDirectives != FormatStyle::PPDIS_BeforeHash &&
1247 (Line.Type == LT_PreprocessorDirective ||
1248 Line.Type == LT_ImportStatement))
1249 Indent = 0;
1250
1251 Whitespaces->replaceWhitespace(RootToken, Newlines, Indent, Indent,
1252 Line.InPPDirective &&
1253 !RootToken.HasUnescapedNewline);
1254}
1255
1256unsigned
1257UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,
1258 const AnnotatedLine *NextLine) const {
1259 // In preprocessor directives reserve two chars for trailing " \" if the
1260 // next line continues the preprocessor directive.
1261 bool ContinuesPPDirective =
1262 InPPDirective &&
1263 // If there is no next line, this is likely a child line and the parent
1264 // continues the preprocessor directive.
1265 (!NextLine ||
1266 (NextLine->InPPDirective &&
1267 // If there is an unescaped newline between this line and the next, the
1268 // next line starts a new preprocessor directive.
1269 !NextLine->First->HasUnescapedNewline));
1270 return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);
1271}
1272
1273} // namespace format
1274} // namespace clang