Coverage Report

Created: 2020-02-15 09:57

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