1//===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "UnwrappedLineFormatter.h"
11#include "WhitespaceManager.h"
12#include "llvm/Support/Debug.h"
13
14#define DEBUG_TYPE "format-formatter"
15
16namespace clang {
17namespace format {
18
19namespace {
20
21bool startsExternCBlock(const AnnotatedLine &Line) {
22  const FormatToken *Next = Line.First->getNextNonComment();
23  const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;
24  return Line.First->is(tok::kw_extern) && Next && Next->isStringLiteral() &&
25         NextNext && NextNext->is(tok::l_brace);
26}
27
28class LineJoiner {
29public:
30  LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords)
31      : Style(Style), Keywords(Keywords) {}
32
33  /// \brief Calculates how many lines can be merged into 1 starting at \p I.
34  unsigned
35  tryFitMultipleLinesInOne(unsigned Indent,
36                           SmallVectorImpl<AnnotatedLine *>::const_iterator I,
37                           SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
38    // Can't join the last line with anything.
39    if (I + 1 == E)
40      return 0;
41    // We can never merge stuff if there are trailing line comments.
42    const AnnotatedLine *TheLine = *I;
43    if (TheLine->Last->is(TT_LineComment))
44      return 0;
45    if (I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
46      return 0;
47    if (TheLine->InPPDirective &&
48        (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline))
49      return 0;
50
51    if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
52      return 0;
53
54    unsigned Limit =
55        Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
56    // If we already exceed the column limit, we set 'Limit' to 0. The different
57    // tryMerge..() functions can then decide whether to still do merging.
58    Limit = TheLine->Last->TotalLength > Limit
59                ? 0
60                : Limit - TheLine->Last->TotalLength;
61
62    // FIXME: TheLine->Level != 0 might or might not be the right check to do.
63    // If necessary, change to something smarter.
64    bool MergeShortFunctions =
65        Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
66        (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Empty &&
67         I[1]->First->is(tok::r_brace)) ||
68        (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Inline &&
69         TheLine->Level != 0);
70
71    if (TheLine->Last->is(TT_FunctionLBrace) &&
72        TheLine->First != TheLine->Last) {
73      return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
74    }
75    if (TheLine->Last->is(tok::l_brace)) {
76      return Style.BreakBeforeBraces == FormatStyle::BS_Attach
77                 ? tryMergeSimpleBlock(I, E, Limit)
78                 : 0;
79    }
80    if (I[1]->First->is(TT_FunctionLBrace) &&
81        Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
82      if (I[1]->Last->is(TT_LineComment))
83        return 0;
84
85      // Check for Limit <= 2 to account for the " {".
86      if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
87        return 0;
88      Limit -= 2;
89
90      unsigned MergedLines = 0;
91      if (MergeShortFunctions) {
92        MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
93        // If we managed to merge the block, count the function header, which is
94        // on a separate line.
95        if (MergedLines > 0)
96          ++MergedLines;
97      }
98      return MergedLines;
99    }
100    if (TheLine->First->is(tok::kw_if)) {
101      return Style.AllowShortIfStatementsOnASingleLine
102                 ? tryMergeSimpleControlStatement(I, E, Limit)
103                 : 0;
104    }
105    if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
106      return Style.AllowShortLoopsOnASingleLine
107                 ? tryMergeSimpleControlStatement(I, E, Limit)
108                 : 0;
109    }
110    if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
111      return Style.AllowShortCaseLabelsOnASingleLine
112                 ? tryMergeShortCaseLabels(I, E, Limit)
113                 : 0;
114    }
115    if (TheLine->InPPDirective &&
116        (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
117      return tryMergeSimplePPDirective(I, E, Limit);
118    }
119    return 0;
120  }
121
122private:
123  unsigned
124  tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
125                            SmallVectorImpl<AnnotatedLine *>::const_iterator E,
126                            unsigned Limit) {
127    if (Limit == 0)
128      return 0;
129    if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
130      return 0;
131    if (1 + I[1]->Last->TotalLength > Limit)
132      return 0;
133    return 1;
134  }
135
136  unsigned tryMergeSimpleControlStatement(
137      SmallVectorImpl<AnnotatedLine *>::const_iterator I,
138      SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
139    if (Limit == 0)
140      return 0;
141    if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
142         Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
143        (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
144      return 0;
145    if (I[1]->InPPDirective != (*I)->InPPDirective ||
146        (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
147      return 0;
148    Limit = limitConsideringMacros(I + 1, E, Limit);
149    AnnotatedLine &Line = **I;
150    if (Line.Last->isNot(tok::r_paren))
151      return 0;
152    if (1 + I[1]->Last->TotalLength > Limit)
153      return 0;
154    if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
155                             tok::kw_while, TT_LineComment))
156      return 0;
157    // Only inline simple if's (no nested if or else).
158    if (I + 2 != E && Line.First->is(tok::kw_if) &&
159        I[2]->First->is(tok::kw_else))
160      return 0;
161    return 1;
162  }
163
164  unsigned tryMergeShortCaseLabels(
165      SmallVectorImpl<AnnotatedLine *>::const_iterator I,
166      SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
167    if (Limit == 0 || I + 1 == E ||
168        I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
169      return 0;
170    unsigned NumStmts = 0;
171    unsigned Length = 0;
172    bool InPPDirective = I[0]->InPPDirective;
173    for (; NumStmts < 3; ++NumStmts) {
174      if (I + 1 + NumStmts == E)
175        break;
176      const AnnotatedLine *Line = I[1 + NumStmts];
177      if (Line->InPPDirective != InPPDirective)
178        break;
179      if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
180        break;
181      if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
182                               tok::kw_while, tok::comment))
183        return 0;
184      Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
185    }
186    if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
187      return 0;
188    return NumStmts;
189  }
190
191  unsigned
192  tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
193                      SmallVectorImpl<AnnotatedLine *>::const_iterator E,
194                      unsigned Limit) {
195    AnnotatedLine &Line = **I;
196
197    // Don't merge ObjC @ keywords and methods.
198    // FIXME: If an option to allow short exception handling clauses on a single
199    // line is added, change this to not return for @try and friends.
200    if (Style.Language != FormatStyle::LK_Java &&
201        Line.First->isOneOf(tok::at, tok::minus, tok::plus))
202      return 0;
203
204    // Check that the current line allows merging. This depends on whether we
205    // are in a control flow statements as well as several style flags.
206    if (Line.First->isOneOf(tok::kw_else, tok::kw_case))
207      return 0;
208    if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
209                            tok::kw___try, tok::kw_catch, tok::kw___finally,
210                            tok::kw_for, tok::r_brace) ||
211        Line.First->is(Keywords.kw___except)) {
212      if (!Style.AllowShortBlocksOnASingleLine)
213        return 0;
214      if (!Style.AllowShortIfStatementsOnASingleLine &&
215          Line.First->is(tok::kw_if))
216        return 0;
217      if (!Style.AllowShortLoopsOnASingleLine &&
218          Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for))
219        return 0;
220      // FIXME: Consider an option to allow short exception handling clauses on
221      // a single line.
222      // FIXME: This isn't covered by tests.
223      // FIXME: For catch, __except, __finally the first token on the line
224      // is '}', so this isn't correct here.
225      if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
226                              Keywords.kw___except, tok::kw___finally))
227        return 0;
228    }
229
230    FormatToken *Tok = I[1]->First;
231    if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
232        (Tok->getNextNonComment() == nullptr ||
233         Tok->getNextNonComment()->is(tok::semi))) {
234      // We merge empty blocks even if the line exceeds the column limit.
235      Tok->SpacesRequiredBefore = 0;
236      Tok->CanBreakBefore = true;
237      return 1;
238    } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace) &&
239               !startsExternCBlock(Line)) {
240      // We don't merge short records.
241      if (Line.First->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct))
242        return 0;
243
244      // Check that we still have three lines and they fit into the limit.
245      if (I + 2 == E || I[2]->Type == LT_Invalid)
246        return 0;
247      Limit = limitConsideringMacros(I + 2, E, Limit);
248
249      if (!nextTwoLinesFitInto(I, Limit))
250        return 0;
251
252      // Second, check that the next line does not contain any braces - if it
253      // does, readability declines when putting it into a single line.
254      if (I[1]->Last->is(TT_LineComment))
255        return 0;
256      do {
257        if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
258          return 0;
259        Tok = Tok->Next;
260      } while (Tok);
261
262      // Last, check that the third line starts with a closing brace.
263      Tok = I[2]->First;
264      if (Tok->isNot(tok::r_brace))
265        return 0;
266
267      return 2;
268    }
269    return 0;
270  }
271
272  /// Returns the modified column limit for \p I if it is inside a macro and
273  /// needs a trailing '\'.
274  unsigned
275  limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
276                         SmallVectorImpl<AnnotatedLine *>::const_iterator E,
277                         unsigned Limit) {
278    if (I[0]->InPPDirective && I + 1 != E &&
279        !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
280      return Limit < 2 ? 0 : Limit - 2;
281    }
282    return Limit;
283  }
284
285  bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
286                           unsigned Limit) {
287    if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
288      return false;
289    return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
290  }
291
292  bool containsMustBreak(const AnnotatedLine *Line) {
293    for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
294      if (Tok->MustBreakBefore)
295        return true;
296    }
297    return false;
298  }
299
300  const FormatStyle &Style;
301  const AdditionalKeywords &Keywords;
302};
303
304class NoColumnLimitFormatter {
305public:
306  NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
307
308  /// \brief Formats the line starting at \p State, simply keeping all of the
309  /// input's line breaking decisions.
310  void format(unsigned FirstIndent, const AnnotatedLine *Line) {
311    LineState State =
312        Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
313    while (State.NextToken) {
314      bool Newline =
315          Indenter->mustBreak(State) ||
316          (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
317      Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
318    }
319  }
320
321private:
322  ContinuationIndenter *Indenter;
323};
324
325
326static void markFinalized(FormatToken *Tok) {
327  for (; Tok; Tok = Tok->Next) {
328    Tok->Finalized = true;
329    for (AnnotatedLine *Child : Tok->Children)
330      markFinalized(Child->First);
331  }
332}
333
334} // namespace
335
336unsigned
337UnwrappedLineFormatter::format(const SmallVectorImpl<AnnotatedLine *> &Lines,
338                               bool DryRun, int AdditionalIndent,
339                               bool FixBadIndentation) {
340  LineJoiner Joiner(Style, Keywords);
341
342  // Try to look up already computed penalty in DryRun-mode.
343  std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
344      &Lines, AdditionalIndent);
345  auto CacheIt = PenaltyCache.find(CacheKey);
346  if (DryRun && CacheIt != PenaltyCache.end())
347    return CacheIt->second;
348
349  assert(!Lines.empty());
350  unsigned Penalty = 0;
351  std::vector<int> IndentForLevel;
352  for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
353    IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
354  const AnnotatedLine *PreviousLine = nullptr;
355  for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
356                                                        E = Lines.end();
357       I != E; ++I) {
358    const AnnotatedLine &TheLine = **I;
359    const FormatToken *FirstTok = TheLine.First;
360    int Offset = getIndentOffset(*FirstTok);
361
362    // Determine indent and try to merge multiple unwrapped lines.
363    unsigned Indent;
364    if (TheLine.InPPDirective) {
365      Indent = TheLine.Level * Style.IndentWidth;
366    } else {
367      while (IndentForLevel.size() <= TheLine.Level)
368        IndentForLevel.push_back(-1);
369      IndentForLevel.resize(TheLine.Level + 1);
370      Indent = getIndent(IndentForLevel, TheLine.Level);
371    }
372    unsigned LevelIndent = Indent;
373    if (static_cast<int>(Indent) + Offset >= 0)
374      Indent += Offset;
375
376    // Merge multiple lines if possible.
377    unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
378    if (MergedLines > 0 && Style.ColumnLimit == 0) {
379      // Disallow line merging if there is a break at the start of one of the
380      // input lines.
381      for (unsigned i = 0; i < MergedLines; ++i) {
382        if (I[i + 1]->First->NewlinesBefore > 0)
383          MergedLines = 0;
384      }
385    }
386    if (!DryRun) {
387      for (unsigned i = 0; i < MergedLines; ++i) {
388        join(*I[i], *I[i + 1]);
389      }
390    }
391    I += MergedLines;
392
393    bool FixIndentation =
394        FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
395    if (TheLine.First->is(tok::eof)) {
396      if (PreviousLine && PreviousLine->Affected && !DryRun) {
397        // Remove the file's trailing whitespace.
398        unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
399        Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
400                                       /*IndentLevel=*/0, /*Spaces=*/0,
401                                       /*TargetColumn=*/0);
402      }
403    } else if (TheLine.Type != LT_Invalid &&
404               (TheLine.Affected || FixIndentation)) {
405      if (FirstTok->WhitespaceRange.isValid()) {
406        if (!DryRun)
407          formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level, Indent,
408                           TheLine.InPPDirective);
409      } else {
410        Indent = LevelIndent = FirstTok->OriginalColumn;
411      }
412
413      // If everything fits on a single line, just put it there.
414      unsigned ColumnLimit = Style.ColumnLimit;
415      if (I + 1 != E) {
416        AnnotatedLine *NextLine = I[1];
417        if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
418          ColumnLimit = getColumnLimit(TheLine.InPPDirective);
419      }
420
421      if (TheLine.Last->TotalLength + Indent <= ColumnLimit ||
422          TheLine.Type == LT_ImportStatement) {
423        LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
424        while (State.NextToken) {
425          formatChildren(State, /*Newline=*/false, DryRun, Penalty);
426          Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
427        }
428      } else if (Style.ColumnLimit == 0) {
429        // FIXME: Implement nested blocks for ColumnLimit = 0.
430        NoColumnLimitFormatter Formatter(Indenter);
431        if (!DryRun)
432          Formatter.format(Indent, &TheLine);
433      } else {
434        Penalty += format(TheLine, Indent, DryRun);
435      }
436
437      if (!TheLine.InPPDirective)
438        IndentForLevel[TheLine.Level] = LevelIndent;
439    } else if (TheLine.ChildrenAffected) {
440      format(TheLine.Children, DryRun);
441    } else {
442      // Format the first token if necessary, and notify the WhitespaceManager
443      // about the unchanged whitespace.
444      for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
445        if (Tok == TheLine.First && (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
446          unsigned LevelIndent = Tok->OriginalColumn;
447          if (!DryRun) {
448            // Remove trailing whitespace of the previous line.
449            if ((PreviousLine && PreviousLine->Affected) ||
450                TheLine.LeadingEmptyLinesAffected) {
451              formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
452                               TheLine.InPPDirective);
453            } else {
454              Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
455            }
456          }
457
458          if (static_cast<int>(LevelIndent) - Offset >= 0)
459            LevelIndent -= Offset;
460          if (Tok->isNot(tok::comment) && !TheLine.InPPDirective)
461            IndentForLevel[TheLine.Level] = LevelIndent;
462        } else if (!DryRun) {
463          Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
464        }
465      }
466    }
467    if (!DryRun)
468      markFinalized(TheLine.First);
469    PreviousLine = *I;
470  }
471  PenaltyCache[CacheKey] = Penalty;
472  return Penalty;
473}
474
475unsigned UnwrappedLineFormatter::format(const AnnotatedLine &Line,
476                                        unsigned FirstIndent, bool DryRun) {
477  LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
478
479  // If the ObjC method declaration does not fit on a line, we should format
480  // it with one arg per line.
481  if (State.Line->Type == LT_ObjCMethodDecl)
482    State.Stack.back().BreakBeforeParameter = true;
483
484  // Find best solution in solution space.
485  return analyzeSolutionSpace(State, DryRun);
486}
487
488void UnwrappedLineFormatter::formatFirstToken(FormatToken &RootToken,
489                                              const AnnotatedLine *PreviousLine,
490                                              unsigned IndentLevel,
491                                              unsigned Indent,
492                                              bool InPPDirective) {
493  unsigned Newlines =
494      std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
495  // Remove empty lines before "}" where applicable.
496  if (RootToken.is(tok::r_brace) &&
497      (!RootToken.Next ||
498       (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
499    Newlines = std::min(Newlines, 1u);
500  if (Newlines == 0 && !RootToken.IsFirst)
501    Newlines = 1;
502  if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
503    Newlines = 0;
504
505  // Remove empty lines after "{".
506  if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
507      PreviousLine->Last->is(tok::l_brace) &&
508      PreviousLine->First->isNot(tok::kw_namespace) &&
509      !startsExternCBlock(*PreviousLine))
510    Newlines = 1;
511
512  // Insert extra new line before access specifiers.
513  if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
514      RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
515    ++Newlines;
516
517  // Remove empty lines after access specifiers.
518  if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
519      (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline))
520    Newlines = std::min(1u, Newlines);
521
522  Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
523                                 Indent, InPPDirective &&
524                                             !RootToken.HasUnescapedNewline);
525}
526
527/// \brief Get the indent of \p Level from \p IndentForLevel.
528///
529/// \p IndentForLevel must contain the indent for the level \c l
530/// at \p IndentForLevel[l], or a value < 0 if the indent for
531/// that level is unknown.
532unsigned UnwrappedLineFormatter::getIndent(ArrayRef<int> IndentForLevel,
533                                           unsigned Level) {
534  if (IndentForLevel[Level] != -1)
535    return IndentForLevel[Level];
536  if (Level == 0)
537    return 0;
538  return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
539}
540
541void UnwrappedLineFormatter::join(AnnotatedLine &A, const AnnotatedLine &B) {
542  assert(!A.Last->Next);
543  assert(!B.First->Previous);
544  if (B.Affected)
545    A.Affected = true;
546  A.Last->Next = B.First;
547  B.First->Previous = A.Last;
548  B.First->CanBreakBefore = true;
549  unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
550  for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
551    Tok->TotalLength += LengthA;
552    A.Last = Tok;
553  }
554}
555
556unsigned UnwrappedLineFormatter::analyzeSolutionSpace(LineState &InitialState,
557                                                      bool DryRun) {
558  std::set<LineState *, CompareLineStatePointers> Seen;
559
560  // Increasing count of \c StateNode items we have created. This is used to
561  // create a deterministic order independent of the container.
562  unsigned Count = 0;
563  QueueType Queue;
564
565  // Insert start element into queue.
566  StateNode *Node =
567      new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
568  Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
569  ++Count;
570
571  unsigned Penalty = 0;
572
573  // While not empty, take first element and follow edges.
574  while (!Queue.empty()) {
575    Penalty = Queue.top().first.first;
576    StateNode *Node = Queue.top().second;
577    if (!Node->State.NextToken) {
578      DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
579      break;
580    }
581    Queue.pop();
582
583    // Cut off the analysis of certain solutions if the analysis gets too
584    // complex. See description of IgnoreStackForComparison.
585    if (Count > 10000)
586      Node->State.IgnoreStackForComparison = true;
587
588    if (!Seen.insert(&Node->State).second)
589      // State already examined with lower penalty.
590      continue;
591
592    FormatDecision LastFormat = Node->State.NextToken->Decision;
593    if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
594      addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
595    if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
596      addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
597  }
598
599  if (Queue.empty()) {
600    // We were unable to find a solution, do nothing.
601    // FIXME: Add diagnostic?
602    DEBUG(llvm::dbgs() << "Could not find a solution.\n");
603    return 0;
604  }
605
606  // Reconstruct the solution.
607  if (!DryRun)
608    reconstructPath(InitialState, Queue.top().second);
609
610  DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
611  DEBUG(llvm::dbgs() << "---\n");
612
613  return Penalty;
614}
615
616#ifndef NDEBUG
617static void printLineState(const LineState &State) {
618  llvm::dbgs() << "State: ";
619  for (const ParenState &P : State.Stack) {
620    llvm::dbgs() << P.Indent << "|" << P.LastSpace << "|" << P.NestedBlockIndent
621                 << " ";
622  }
623  llvm::dbgs() << State.NextToken->TokenText << "\n";
624}
625#endif
626
627void UnwrappedLineFormatter::reconstructPath(LineState &State,
628                                             StateNode *Current) {
629  std::deque<StateNode *> Path;
630  // We do not need a break before the initial token.
631  while (Current->Previous) {
632    Path.push_front(Current);
633    Current = Current->Previous;
634  }
635  for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
636       I != E; ++I) {
637    unsigned Penalty = 0;
638    formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
639    Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
640
641    DEBUG({
642      printLineState((*I)->Previous->State);
643      if ((*I)->NewLine) {
644        llvm::dbgs() << "Penalty for placing "
645                     << (*I)->Previous->State.NextToken->Tok.getName() << ": "
646                     << Penalty << "\n";
647      }
648    });
649  }
650}
651
652void UnwrappedLineFormatter::addNextStateToQueue(unsigned Penalty,
653                                                 StateNode *PreviousNode,
654                                                 bool NewLine, unsigned *Count,
655                                                 QueueType *Queue) {
656  if (NewLine && !Indenter->canBreak(PreviousNode->State))
657    return;
658  if (!NewLine && Indenter->mustBreak(PreviousNode->State))
659    return;
660
661  StateNode *Node = new (Allocator.Allocate())
662      StateNode(PreviousNode->State, NewLine, PreviousNode);
663  if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
664    return;
665
666  Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
667
668  Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
669  ++(*Count);
670}
671
672bool UnwrappedLineFormatter::formatChildren(LineState &State, bool NewLine,
673                                            bool DryRun, unsigned &Penalty) {
674  const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
675  FormatToken &Previous = *State.NextToken->Previous;
676  if (!LBrace || LBrace->isNot(tok::l_brace) || LBrace->BlockKind != BK_Block ||
677      Previous.Children.size() == 0)
678    // The previous token does not open a block. Nothing to do. We don't
679    // assert so that we can simply call this function for all tokens.
680    return true;
681
682  if (NewLine) {
683    int AdditionalIndent = State.Stack.back().Indent -
684                           Previous.Children[0]->Level * Style.IndentWidth;
685
686    Penalty += format(Previous.Children, DryRun, AdditionalIndent,
687                      /*FixBadIndentation=*/true);
688    return true;
689  }
690
691  if (Previous.Children[0]->First->MustBreakBefore)
692    return false;
693
694  // Cannot merge multiple statements into a single line.
695  if (Previous.Children.size() > 1)
696    return false;
697
698  // Cannot merge into one line if this line ends on a comment.
699  if (Previous.is(tok::comment))
700    return false;
701
702  // We can't put the closing "}" on a line with a trailing comment.
703  if (Previous.Children[0]->Last->isTrailingComment())
704    return false;
705
706  // If the child line exceeds the column limit, we wouldn't want to merge it.
707  // We add +2 for the trailing " }".
708  if (Style.ColumnLimit > 0 &&
709      Previous.Children[0]->Last->TotalLength + State.Column + 2 >
710          Style.ColumnLimit)
711    return false;
712
713  if (!DryRun) {
714    Whitespaces->replaceWhitespace(
715        *Previous.Children[0]->First,
716        /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
717        /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
718  }
719  Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
720
721  State.Column += 1 + Previous.Children[0]->Last->TotalLength;
722  return true;
723}
724
725} // namespace format
726} // namespace clang
727