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