Coverage Report

Created: 2021-01-23 06:44

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