xref: /freebsd/contrib/llvm-project/clang/lib/Format/UnwrappedLineFormatter.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
1 //===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "UnwrappedLineFormatter.h"
10 #include "NamespaceEndCommentsFixer.h"
11 #include "WhitespaceManager.h"
12 #include "llvm/Support/Debug.h"
13 #include <queue>
14 
15 #define DEBUG_TYPE "format-formatter"
16 
17 namespace clang {
18 namespace format {
19 
20 namespace {
21 
22 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 
1023 unsigned UnwrappedLineFormatter::format(
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
1225