Coverage Report

Created: 2020-09-22 08:39

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