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