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