10b57cec5SDimitry Andric //===--- UnwrappedLineFormatter.cpp - Format C++ code ---------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric
90b57cec5SDimitry Andric #include "UnwrappedLineFormatter.h"
1006c3fb27SDimitry Andric #include "FormatToken.h"
110b57cec5SDimitry Andric #include "NamespaceEndCommentsFixer.h"
120b57cec5SDimitry Andric #include "WhitespaceManager.h"
130b57cec5SDimitry Andric #include "llvm/Support/Debug.h"
140b57cec5SDimitry Andric #include <queue>
150b57cec5SDimitry Andric
160b57cec5SDimitry Andric #define DEBUG_TYPE "format-formatter"
170b57cec5SDimitry Andric
180b57cec5SDimitry Andric namespace clang {
190b57cec5SDimitry Andric namespace format {
200b57cec5SDimitry Andric
210b57cec5SDimitry Andric namespace {
220b57cec5SDimitry Andric
startsExternCBlock(const AnnotatedLine & Line)230b57cec5SDimitry Andric bool startsExternCBlock(const AnnotatedLine &Line) {
240b57cec5SDimitry Andric const FormatToken *Next = Line.First->getNextNonComment();
250b57cec5SDimitry Andric const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;
260b57cec5SDimitry Andric return Line.startsWith(tok::kw_extern) && Next && Next->isStringLiteral() &&
270b57cec5SDimitry Andric NextNext && NextNext->is(tok::l_brace);
280b57cec5SDimitry Andric }
290b57cec5SDimitry Andric
isRecordLBrace(const FormatToken & Tok)3081ad6265SDimitry Andric bool isRecordLBrace(const FormatToken &Tok) {
3181ad6265SDimitry Andric return Tok.isOneOf(TT_ClassLBrace, TT_EnumLBrace, TT_RecordLBrace,
3281ad6265SDimitry Andric TT_StructLBrace, TT_UnionLBrace);
3381ad6265SDimitry Andric }
3481ad6265SDimitry Andric
350b57cec5SDimitry Andric /// Tracks the indent level of \c AnnotatedLines across levels.
360b57cec5SDimitry Andric ///
370b57cec5SDimitry Andric /// \c nextLine must be called for each \c AnnotatedLine, after which \c
380b57cec5SDimitry Andric /// getIndent() will return the indent for the last line \c nextLine was called
390b57cec5SDimitry Andric /// with.
400b57cec5SDimitry Andric /// If the line is not formatted (and thus the indent does not change), calling
410b57cec5SDimitry Andric /// \c adjustToUnmodifiedLine after the call to \c nextLine will cause
420b57cec5SDimitry Andric /// subsequent lines on the same level to be indented at the same level as the
430b57cec5SDimitry Andric /// given line.
440b57cec5SDimitry Andric class LevelIndentTracker {
450b57cec5SDimitry Andric public:
LevelIndentTracker(const FormatStyle & Style,const AdditionalKeywords & Keywords,unsigned StartLevel,int AdditionalIndent)460b57cec5SDimitry Andric LevelIndentTracker(const FormatStyle &Style,
470b57cec5SDimitry Andric const AdditionalKeywords &Keywords, unsigned StartLevel,
480b57cec5SDimitry Andric int AdditionalIndent)
490b57cec5SDimitry Andric : Style(Style), Keywords(Keywords), AdditionalIndent(AdditionalIndent) {
500b57cec5SDimitry Andric for (unsigned i = 0; i != StartLevel; ++i)
510b57cec5SDimitry Andric IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
520b57cec5SDimitry Andric }
530b57cec5SDimitry Andric
540b57cec5SDimitry Andric /// Returns the indent for the current line.
getIndent() const550b57cec5SDimitry Andric unsigned getIndent() const { return Indent; }
560b57cec5SDimitry Andric
570b57cec5SDimitry Andric /// Update the indent state given that \p Line is going to be formatted
580b57cec5SDimitry Andric /// next.
nextLine(const AnnotatedLine & Line)590b57cec5SDimitry Andric void nextLine(const AnnotatedLine &Line) {
600b57cec5SDimitry Andric Offset = getIndentOffset(*Line.First);
610b57cec5SDimitry Andric // Update the indent level cache size so that we can rely on it
620b57cec5SDimitry Andric // having the right size in adjustToUnmodifiedline.
6306c3fb27SDimitry Andric if (Line.Level >= IndentForLevel.size())
6406c3fb27SDimitry Andric IndentForLevel.resize(Line.Level + 1, -1);
65bdd1243dSDimitry Andric if (Style.IndentPPDirectives != FormatStyle::PPDIS_None &&
66bdd1243dSDimitry Andric (Line.InPPDirective ||
67bdd1243dSDimitry Andric (Style.IndentPPDirectives == FormatStyle::PPDIS_BeforeHash &&
68bdd1243dSDimitry Andric Line.Type == LT_CommentAbovePPDirective))) {
69bdd1243dSDimitry Andric unsigned PPIndentWidth =
70fe6060f1SDimitry Andric (Style.PPIndentWidth >= 0) ? Style.PPIndentWidth : Style.IndentWidth;
71bdd1243dSDimitry Andric Indent = Line.InMacroBody
72bdd1243dSDimitry Andric ? Line.PPLevel * PPIndentWidth +
73bdd1243dSDimitry Andric (Line.Level - Line.PPLevel) * Style.IndentWidth
74bdd1243dSDimitry Andric : Line.Level * PPIndentWidth;
75bdd1243dSDimitry Andric Indent += AdditionalIndent;
760b57cec5SDimitry Andric } else {
7706c3fb27SDimitry Andric // When going to lower levels, forget previous higher levels so that we
7806c3fb27SDimitry Andric // recompute future higher levels. But don't forget them if we enter a PP
7906c3fb27SDimitry Andric // directive, since these do not terminate a C++ code block.
8006c3fb27SDimitry Andric if (!Line.InPPDirective) {
8106c3fb27SDimitry Andric assert(Line.Level <= IndentForLevel.size());
8206c3fb27SDimitry Andric IndentForLevel.resize(Line.Level + 1);
8306c3fb27SDimitry Andric }
840eae32dcSDimitry Andric Indent = getIndent(Line.Level);
850b57cec5SDimitry Andric }
860b57cec5SDimitry Andric if (static_cast<int>(Indent) + Offset >= 0)
870b57cec5SDimitry Andric Indent += Offset;
88bdd1243dSDimitry Andric if (Line.IsContinuation)
895ffd83dbSDimitry Andric Indent = Line.Level * Style.IndentWidth + Style.ContinuationIndentWidth;
900b57cec5SDimitry Andric }
910b57cec5SDimitry Andric
920b57cec5SDimitry Andric /// Update the level indent to adapt to the given \p Line.
930b57cec5SDimitry Andric ///
940b57cec5SDimitry Andric /// When a line is not formatted, we move the subsequent lines on the same
950b57cec5SDimitry Andric /// level to the same indent.
960b57cec5SDimitry Andric /// Note that \c nextLine must have been called before this method.
adjustToUnmodifiedLine(const AnnotatedLine & Line)970b57cec5SDimitry Andric void adjustToUnmodifiedLine(const AnnotatedLine &Line) {
987a6dacacSDimitry Andric if (Line.InPPDirective || Line.IsContinuation)
9906c3fb27SDimitry Andric return;
10006c3fb27SDimitry Andric assert(Line.Level < IndentForLevel.size());
10106c3fb27SDimitry Andric if (Line.First->is(tok::comment) && IndentForLevel[Line.Level] != -1)
10206c3fb27SDimitry Andric return;
1030b57cec5SDimitry Andric unsigned LevelIndent = Line.First->OriginalColumn;
1040b57cec5SDimitry Andric if (static_cast<int>(LevelIndent) - Offset >= 0)
1050b57cec5SDimitry Andric LevelIndent -= Offset;
1060b57cec5SDimitry Andric IndentForLevel[Line.Level] = LevelIndent;
1070b57cec5SDimitry Andric }
1080b57cec5SDimitry Andric
1090b57cec5SDimitry Andric private:
1100b57cec5SDimitry Andric /// Get the offset of the line relatively to the level.
1110b57cec5SDimitry Andric ///
1120b57cec5SDimitry Andric /// For example, 'public:' labels in classes are offset by 1 or 2
1130b57cec5SDimitry Andric /// characters to the left from their level.
getIndentOffset(const FormatToken & RootToken)1140b57cec5SDimitry Andric int getIndentOffset(const FormatToken &RootToken) {
1150eae32dcSDimitry Andric if (Style.Language == FormatStyle::LK_Java || Style.isJavaScript() ||
11681ad6265SDimitry Andric Style.isCSharp()) {
1170b57cec5SDimitry Andric return 0;
11881ad6265SDimitry Andric }
1191fd87a68SDimitry Andric
1201fd87a68SDimitry Andric auto IsAccessModifier = [this, &RootToken]() {
12181ad6265SDimitry Andric if (RootToken.isAccessSpecifier(Style.isCpp())) {
1221fd87a68SDimitry Andric return true;
12381ad6265SDimitry Andric } else if (RootToken.isObjCAccessSpecifier()) {
1241fd87a68SDimitry Andric return true;
12581ad6265SDimitry Andric }
1261fd87a68SDimitry Andric // Handle Qt signals.
12706c3fb27SDimitry Andric else if (RootToken.isOneOf(Keywords.kw_signals, Keywords.kw_qsignals) &&
12806c3fb27SDimitry Andric RootToken.Next && RootToken.Next->is(tok::colon)) {
1291fd87a68SDimitry Andric return true;
13081ad6265SDimitry Andric } else if (RootToken.Next &&
13181ad6265SDimitry Andric RootToken.Next->isOneOf(Keywords.kw_slots,
13281ad6265SDimitry Andric Keywords.kw_qslots) &&
13381ad6265SDimitry Andric RootToken.Next->Next && RootToken.Next->Next->is(tok::colon)) {
1341fd87a68SDimitry Andric return true;
13581ad6265SDimitry Andric }
1361fd87a68SDimitry Andric // Handle malformed access specifier e.g. 'private' without trailing ':'.
13781ad6265SDimitry Andric else if (!RootToken.Next && RootToken.isAccessSpecifier(false)) {
1381fd87a68SDimitry Andric return true;
13981ad6265SDimitry Andric }
1401fd87a68SDimitry Andric return false;
1411fd87a68SDimitry Andric };
1421fd87a68SDimitry Andric
1431fd87a68SDimitry Andric if (IsAccessModifier()) {
144349cc55cSDimitry Andric // The AccessModifierOffset may be overridden by IndentAccessModifiers,
145fe6060f1SDimitry Andric // in which case we take a negative value of the IndentWidth to simulate
146fe6060f1SDimitry Andric // the upper indent level.
147fe6060f1SDimitry Andric return Style.IndentAccessModifiers ? -Style.IndentWidth
148fe6060f1SDimitry Andric : Style.AccessModifierOffset;
149fe6060f1SDimitry Andric }
1500b57cec5SDimitry Andric return 0;
1510b57cec5SDimitry Andric }
1520b57cec5SDimitry Andric
1530b57cec5SDimitry Andric /// Get the indent of \p Level from \p IndentForLevel.
1540b57cec5SDimitry Andric ///
1550b57cec5SDimitry Andric /// \p IndentForLevel must contain the indent for the level \c l
1560b57cec5SDimitry Andric /// at \p IndentForLevel[l], or a value < 0 if the indent for
1570b57cec5SDimitry Andric /// that level is unknown.
getIndent(unsigned Level) const1580eae32dcSDimitry Andric unsigned getIndent(unsigned Level) const {
15906c3fb27SDimitry Andric assert(Level < IndentForLevel.size());
1600b57cec5SDimitry Andric if (IndentForLevel[Level] != -1)
1610b57cec5SDimitry Andric return IndentForLevel[Level];
1620b57cec5SDimitry Andric if (Level == 0)
1630b57cec5SDimitry Andric return 0;
1640eae32dcSDimitry Andric return getIndent(Level - 1) + Style.IndentWidth;
1650b57cec5SDimitry Andric }
1660b57cec5SDimitry Andric
1670b57cec5SDimitry Andric const FormatStyle &Style;
1680b57cec5SDimitry Andric const AdditionalKeywords &Keywords;
1690b57cec5SDimitry Andric const unsigned AdditionalIndent;
1700b57cec5SDimitry Andric
17106c3fb27SDimitry Andric /// The indent in characters for each level. It remembers the indent of
17206c3fb27SDimitry Andric /// previous lines (that are not PP directives) of equal or lower levels. This
17306c3fb27SDimitry Andric /// is used to align formatted lines to the indent of previous non-formatted
17406c3fb27SDimitry Andric /// lines. Think about the --lines parameter of clang-format.
175753f127fSDimitry Andric SmallVector<int> IndentForLevel;
1760b57cec5SDimitry Andric
1770b57cec5SDimitry Andric /// Offset of the current line relative to the indent level.
1780b57cec5SDimitry Andric ///
1790b57cec5SDimitry Andric /// For example, the 'public' keywords is often indented with a negative
1800b57cec5SDimitry Andric /// offset.
1810b57cec5SDimitry Andric int Offset = 0;
1820b57cec5SDimitry Andric
1830b57cec5SDimitry Andric /// The current line's indent.
1840b57cec5SDimitry Andric unsigned Indent = 0;
1850b57cec5SDimitry Andric };
1860b57cec5SDimitry Andric
getMatchingNamespaceToken(const AnnotatedLine * Line,const SmallVectorImpl<AnnotatedLine * > & AnnotatedLines)1870b57cec5SDimitry Andric const FormatToken *getMatchingNamespaceToken(
1880b57cec5SDimitry Andric const AnnotatedLine *Line,
1890b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1900b57cec5SDimitry Andric if (!Line->startsWith(tok::r_brace))
1910b57cec5SDimitry Andric return nullptr;
1920b57cec5SDimitry Andric size_t StartLineIndex = Line->MatchingOpeningBlockLineIndex;
1930b57cec5SDimitry Andric if (StartLineIndex == UnwrappedLine::kInvalidIndex)
1940b57cec5SDimitry Andric return nullptr;
1950b57cec5SDimitry Andric assert(StartLineIndex < AnnotatedLines.size());
1960b57cec5SDimitry Andric return AnnotatedLines[StartLineIndex]->First->getNamespaceToken();
1970b57cec5SDimitry Andric }
1980b57cec5SDimitry Andric
getNamespaceTokenText(const AnnotatedLine * Line)1990b57cec5SDimitry Andric StringRef getNamespaceTokenText(const AnnotatedLine *Line) {
2000b57cec5SDimitry Andric const FormatToken *NamespaceToken = Line->First->getNamespaceToken();
2010b57cec5SDimitry Andric return NamespaceToken ? NamespaceToken->TokenText : StringRef();
2020b57cec5SDimitry Andric }
2030b57cec5SDimitry Andric
getMatchingNamespaceTokenText(const AnnotatedLine * Line,const SmallVectorImpl<AnnotatedLine * > & AnnotatedLines)2040b57cec5SDimitry Andric StringRef getMatchingNamespaceTokenText(
2050b57cec5SDimitry Andric const AnnotatedLine *Line,
2060b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
2070b57cec5SDimitry Andric const FormatToken *NamespaceToken =
2080b57cec5SDimitry Andric getMatchingNamespaceToken(Line, AnnotatedLines);
2090b57cec5SDimitry Andric return NamespaceToken ? NamespaceToken->TokenText : StringRef();
2100b57cec5SDimitry Andric }
2110b57cec5SDimitry Andric
2120b57cec5SDimitry Andric class LineJoiner {
2130b57cec5SDimitry Andric public:
LineJoiner(const FormatStyle & Style,const AdditionalKeywords & Keywords,const SmallVectorImpl<AnnotatedLine * > & Lines)2140b57cec5SDimitry Andric LineJoiner(const FormatStyle &Style, const AdditionalKeywords &Keywords,
2150b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &Lines)
2160b57cec5SDimitry Andric : Style(Style), Keywords(Keywords), End(Lines.end()), Next(Lines.begin()),
2170b57cec5SDimitry Andric AnnotatedLines(Lines) {}
2180b57cec5SDimitry Andric
2190b57cec5SDimitry Andric /// Returns the next line, merging multiple lines into one if possible.
getNextMergedLine(bool DryRun,LevelIndentTracker & IndentTracker)2200b57cec5SDimitry Andric const AnnotatedLine *getNextMergedLine(bool DryRun,
2210b57cec5SDimitry Andric LevelIndentTracker &IndentTracker) {
2220b57cec5SDimitry Andric if (Next == End)
2230b57cec5SDimitry Andric return nullptr;
2240b57cec5SDimitry Andric const AnnotatedLine *Current = *Next;
2250b57cec5SDimitry Andric IndentTracker.nextLine(*Current);
2260b57cec5SDimitry Andric unsigned MergedLines = tryFitMultipleLinesInOne(IndentTracker, Next, End);
22781ad6265SDimitry Andric if (MergedLines > 0 && Style.ColumnLimit == 0) {
2280b57cec5SDimitry Andric // Disallow line merging if there is a break at the start of one of the
2290b57cec5SDimitry Andric // input lines.
2300b57cec5SDimitry Andric for (unsigned i = 0; i < MergedLines; ++i)
2310b57cec5SDimitry Andric if (Next[i + 1]->First->NewlinesBefore > 0)
2320b57cec5SDimitry Andric MergedLines = 0;
23381ad6265SDimitry Andric }
2340b57cec5SDimitry Andric if (!DryRun)
2350b57cec5SDimitry Andric for (unsigned i = 0; i < MergedLines; ++i)
2360b57cec5SDimitry Andric join(*Next[0], *Next[i + 1]);
2370b57cec5SDimitry Andric Next = Next + MergedLines + 1;
2380b57cec5SDimitry Andric return Current;
2390b57cec5SDimitry Andric }
2400b57cec5SDimitry Andric
2410b57cec5SDimitry Andric private:
2420b57cec5SDimitry Andric /// Calculates how many lines can be merged into 1 starting at \p I.
2430b57cec5SDimitry Andric unsigned
tryFitMultipleLinesInOne(LevelIndentTracker & IndentTracker,SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E)2440b57cec5SDimitry Andric tryFitMultipleLinesInOne(LevelIndentTracker &IndentTracker,
2450b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator I,
2460b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
2470b57cec5SDimitry Andric const unsigned Indent = IndentTracker.getIndent();
2480b57cec5SDimitry Andric
2490b57cec5SDimitry Andric // Can't join the last line with anything.
2500b57cec5SDimitry Andric if (I + 1 == E)
2510b57cec5SDimitry Andric return 0;
2520b57cec5SDimitry Andric // We can never merge stuff if there are trailing line comments.
2530b57cec5SDimitry Andric const AnnotatedLine *TheLine = *I;
2540b57cec5SDimitry Andric if (TheLine->Last->is(TT_LineComment))
2550b57cec5SDimitry Andric return 0;
25681ad6265SDimitry Andric const auto &NextLine = *I[1];
25781ad6265SDimitry Andric if (NextLine.Type == LT_Invalid || NextLine.First->MustBreakBefore)
2580b57cec5SDimitry Andric return 0;
2590b57cec5SDimitry Andric if (TheLine->InPPDirective &&
26081ad6265SDimitry Andric (!NextLine.InPPDirective || NextLine.First->HasUnescapedNewline)) {
2610b57cec5SDimitry Andric return 0;
26281ad6265SDimitry Andric }
2630b57cec5SDimitry Andric
2640b57cec5SDimitry Andric if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
2650b57cec5SDimitry Andric return 0;
2660b57cec5SDimitry Andric
2670b57cec5SDimitry Andric unsigned Limit =
2680b57cec5SDimitry Andric Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
2690b57cec5SDimitry Andric // If we already exceed the column limit, we set 'Limit' to 0. The different
2700b57cec5SDimitry Andric // tryMerge..() functions can then decide whether to still do merging.
2710b57cec5SDimitry Andric Limit = TheLine->Last->TotalLength > Limit
2720b57cec5SDimitry Andric ? 0
2730b57cec5SDimitry Andric : Limit - TheLine->Last->TotalLength;
2740b57cec5SDimitry Andric
2750b57cec5SDimitry Andric if (TheLine->Last->is(TT_FunctionLBrace) &&
2760b57cec5SDimitry Andric TheLine->First == TheLine->Last &&
2770b57cec5SDimitry Andric !Style.BraceWrapping.SplitEmptyFunction &&
27881ad6265SDimitry Andric NextLine.First->is(tok::r_brace)) {
2790b57cec5SDimitry Andric return tryMergeSimpleBlock(I, E, Limit);
28081ad6265SDimitry Andric }
2810b57cec5SDimitry Andric
28281ad6265SDimitry Andric const auto *PreviousLine = I != AnnotatedLines.begin() ? I[-1] : nullptr;
28381ad6265SDimitry Andric // Handle empty record blocks where the brace has already been wrapped.
28481ad6265SDimitry Andric if (PreviousLine && TheLine->Last->is(tok::l_brace) &&
28581ad6265SDimitry Andric TheLine->First == TheLine->Last) {
28681ad6265SDimitry Andric bool EmptyBlock = NextLine.First->is(tok::r_brace);
2870b57cec5SDimitry Andric
28881ad6265SDimitry Andric const FormatToken *Tok = PreviousLine->First;
2890b57cec5SDimitry Andric if (Tok && Tok->is(tok::comment))
2900b57cec5SDimitry Andric Tok = Tok->getNextNonComment();
2910b57cec5SDimitry Andric
29281ad6265SDimitry Andric if (Tok && Tok->getNamespaceToken()) {
2930b57cec5SDimitry Andric return !Style.BraceWrapping.SplitEmptyNamespace && EmptyBlock
2940b57cec5SDimitry Andric ? tryMergeSimpleBlock(I, E, Limit)
2950b57cec5SDimitry Andric : 0;
29681ad6265SDimitry Andric }
2970b57cec5SDimitry Andric
2980b57cec5SDimitry Andric if (Tok && Tok->is(tok::kw_typedef))
2990b57cec5SDimitry Andric Tok = Tok->getNextNonComment();
3000b57cec5SDimitry Andric if (Tok && Tok->isOneOf(tok::kw_class, tok::kw_struct, tok::kw_union,
30181ad6265SDimitry Andric tok::kw_extern, Keywords.kw_interface)) {
3020b57cec5SDimitry Andric return !Style.BraceWrapping.SplitEmptyRecord && EmptyBlock
3030b57cec5SDimitry Andric ? tryMergeSimpleBlock(I, E, Limit)
3040b57cec5SDimitry Andric : 0;
30581ad6265SDimitry Andric }
306e8d8bef9SDimitry Andric
307e8d8bef9SDimitry Andric if (Tok && Tok->is(tok::kw_template) &&
308e8d8bef9SDimitry Andric Style.BraceWrapping.SplitEmptyRecord && EmptyBlock) {
309e8d8bef9SDimitry Andric return 0;
310e8d8bef9SDimitry Andric }
3110b57cec5SDimitry Andric }
3120b57cec5SDimitry Andric
31381ad6265SDimitry Andric auto ShouldMergeShortFunctions = [this, &I, &NextLine, PreviousLine,
31481ad6265SDimitry Andric TheLine]() {
31504eeddc0SDimitry Andric if (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All)
31604eeddc0SDimitry Andric return true;
31781ad6265SDimitry Andric if (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
31881ad6265SDimitry Andric NextLine.First->is(tok::r_brace)) {
31904eeddc0SDimitry Andric return true;
32081ad6265SDimitry Andric }
32104eeddc0SDimitry Andric
32204eeddc0SDimitry Andric if (Style.AllowShortFunctionsOnASingleLine &
32304eeddc0SDimitry Andric FormatStyle::SFS_InlineOnly) {
32404eeddc0SDimitry Andric // Just checking TheLine->Level != 0 is not enough, because it
32504eeddc0SDimitry Andric // provokes treating functions inside indented namespaces as short.
32681ad6265SDimitry Andric if (Style.isJavaScript() && TheLine->Last->is(TT_FunctionLBrace))
32704eeddc0SDimitry Andric return true;
32804eeddc0SDimitry Andric
32981ad6265SDimitry Andric if (TheLine->Level != 0) {
33081ad6265SDimitry Andric if (!PreviousLine)
33104eeddc0SDimitry Andric return false;
33204eeddc0SDimitry Andric
33304eeddc0SDimitry Andric // TODO: Use IndentTracker to avoid loop?
33404eeddc0SDimitry Andric // Find the last line with lower level.
33581ad6265SDimitry Andric const AnnotatedLine *Line = nullptr;
33681ad6265SDimitry Andric for (auto J = I - 1; J >= AnnotatedLines.begin(); --J) {
33781ad6265SDimitry Andric assert(*J);
33881ad6265SDimitry Andric if (!(*J)->InPPDirective && !(*J)->isComment() &&
33981ad6265SDimitry Andric (*J)->Level < TheLine->Level) {
34081ad6265SDimitry Andric Line = *J;
34104eeddc0SDimitry Andric break;
34281ad6265SDimitry Andric }
34381ad6265SDimitry Andric }
34481ad6265SDimitry Andric
34581ad6265SDimitry Andric if (!Line)
34681ad6265SDimitry Andric return false;
34704eeddc0SDimitry Andric
34804eeddc0SDimitry Andric // Check if the found line starts a record.
3495f757f3fSDimitry Andric const auto *LastNonComment = Line->getLastNonComment();
35081ad6265SDimitry Andric // There must be another token (usually `{`), because we chose a
35181ad6265SDimitry Andric // non-PPDirective and non-comment line that has a smaller level.
35281ad6265SDimitry Andric assert(LastNonComment);
35381ad6265SDimitry Andric return isRecordLBrace(*LastNonComment);
35404eeddc0SDimitry Andric }
35504eeddc0SDimitry Andric }
35604eeddc0SDimitry Andric
35704eeddc0SDimitry Andric return false;
35804eeddc0SDimitry Andric };
35904eeddc0SDimitry Andric
36081ad6265SDimitry Andric bool MergeShortFunctions = ShouldMergeShortFunctions();
36181ad6265SDimitry Andric
3625f757f3fSDimitry Andric const auto *FirstNonComment = TheLine->getFirstNonComment();
36381ad6265SDimitry Andric if (!FirstNonComment)
36481ad6265SDimitry Andric return 0;
36581ad6265SDimitry Andric // FIXME: There are probably cases where we should use FirstNonComment
36681ad6265SDimitry Andric // instead of TheLine->First.
3670b57cec5SDimitry Andric
3680b57cec5SDimitry Andric if (Style.CompactNamespaces) {
36906c3fb27SDimitry Andric if (const auto *NSToken = TheLine->First->getNamespaceToken()) {
37006c3fb27SDimitry Andric int J = 1;
37106c3fb27SDimitry Andric assert(TheLine->MatchingClosingBlockLineIndex > 0);
37206c3fb27SDimitry Andric for (auto ClosingLineIndex = TheLine->MatchingClosingBlockLineIndex - 1;
37306c3fb27SDimitry Andric I + J != E && NSToken->TokenText == getNamespaceTokenText(I[J]) &&
37406c3fb27SDimitry Andric ClosingLineIndex == I[J]->MatchingClosingBlockLineIndex &&
37506c3fb27SDimitry Andric I[J]->Last->TotalLength < Limit;
37606c3fb27SDimitry Andric ++J, --ClosingLineIndex) {
37706c3fb27SDimitry Andric Limit -= I[J]->Last->TotalLength;
3780b57cec5SDimitry Andric
37906c3fb27SDimitry Andric // Reduce indent level for bodies of namespaces which were compacted,
38006c3fb27SDimitry Andric // but only if their content was indented in the first place.
38106c3fb27SDimitry Andric auto *ClosingLine = AnnotatedLines.begin() + ClosingLineIndex + 1;
3825f757f3fSDimitry Andric const int OutdentBy = I[J]->Level - TheLine->Level;
3835f757f3fSDimitry Andric assert(OutdentBy >= 0);
38406c3fb27SDimitry Andric for (auto *CompactedLine = I + J; CompactedLine <= ClosingLine;
38506c3fb27SDimitry Andric ++CompactedLine) {
3865f757f3fSDimitry Andric if (!(*CompactedLine)->InPPDirective) {
3875f757f3fSDimitry Andric const int Level = (*CompactedLine)->Level;
3885f757f3fSDimitry Andric (*CompactedLine)->Level = std::max(Level - OutdentBy, 0);
3895f757f3fSDimitry Andric }
3900b57cec5SDimitry Andric }
39106c3fb27SDimitry Andric }
39206c3fb27SDimitry Andric return J - 1;
3930b57cec5SDimitry Andric }
3940b57cec5SDimitry Andric
3950b57cec5SDimitry Andric if (auto nsToken = getMatchingNamespaceToken(TheLine, AnnotatedLines)) {
3960b57cec5SDimitry Andric int i = 0;
3970b57cec5SDimitry Andric unsigned openingLine = TheLine->MatchingOpeningBlockLineIndex - 1;
3980b57cec5SDimitry Andric for (; I + 1 + i != E &&
3990b57cec5SDimitry Andric nsToken->TokenText ==
4000b57cec5SDimitry Andric getMatchingNamespaceTokenText(I[i + 1], AnnotatedLines) &&
4010b57cec5SDimitry Andric openingLine == I[i + 1]->MatchingOpeningBlockLineIndex;
40281ad6265SDimitry Andric i++, --openingLine) {
40381ad6265SDimitry Andric // No space between consecutive braces.
4045f757f3fSDimitry Andric I[i + 1]->First->SpacesRequiredBefore =
4055f757f3fSDimitry Andric I[i]->Last->isNot(tok::r_brace);
4060b57cec5SDimitry Andric
40781ad6265SDimitry Andric // Indent like the outer-most namespace.
4080b57cec5SDimitry Andric IndentTracker.nextLine(*I[i + 1]);
4090b57cec5SDimitry Andric }
4100b57cec5SDimitry Andric return i;
4110b57cec5SDimitry Andric }
4120b57cec5SDimitry Andric }
4130b57cec5SDimitry Andric
4145f757f3fSDimitry Andric const auto *LastNonComment = TheLine->getLastNonComment();
4155f757f3fSDimitry Andric assert(LastNonComment);
4165f757f3fSDimitry Andric // FIXME: There are probably cases where we should use LastNonComment
4175f757f3fSDimitry Andric // instead of TheLine->Last.
4185f757f3fSDimitry Andric
41981ad6265SDimitry Andric // Try to merge a function block with left brace unwrapped.
4205f757f3fSDimitry Andric if (LastNonComment->is(TT_FunctionLBrace) &&
4215f757f3fSDimitry Andric TheLine->First != LastNonComment) {
4220b57cec5SDimitry Andric return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
4235f757f3fSDimitry Andric }
42481ad6265SDimitry Andric // Try to merge a control statement block with left brace unwrapped.
42581ad6265SDimitry Andric if (TheLine->Last->is(tok::l_brace) && FirstNonComment != TheLine->Last &&
42681ad6265SDimitry Andric FirstNonComment->isOneOf(tok::kw_if, tok::kw_while, tok::kw_for,
42704eeddc0SDimitry Andric TT_ForEachMacro)) {
428a7dea167SDimitry Andric return Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never
4290b57cec5SDimitry Andric ? tryMergeSimpleBlock(I, E, Limit)
4300b57cec5SDimitry Andric : 0;
4310b57cec5SDimitry Andric }
43281ad6265SDimitry Andric // Try to merge a control statement block with left brace wrapped.
43381ad6265SDimitry Andric if (NextLine.First->is(tok::l_brace)) {
43481ad6265SDimitry Andric if ((TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
4354824e7fdSDimitry Andric tok::kw_for, tok::kw_switch, tok::kw_try,
4364824e7fdSDimitry Andric tok::kw_do, TT_ForEachMacro) ||
437a7dea167SDimitry Andric (TheLine->First->is(tok::r_brace) && TheLine->First->Next &&
438a7dea167SDimitry Andric TheLine->First->Next->isOneOf(tok::kw_else, tok::kw_catch))) &&
439a7dea167SDimitry Andric Style.BraceWrapping.AfterControlStatement ==
440a7dea167SDimitry Andric FormatStyle::BWACS_MultiLine) {
44181ad6265SDimitry Andric // If possible, merge the next line's wrapped left brace with the
44281ad6265SDimitry Andric // current line. Otherwise, leave it on the next line, as this is a
44381ad6265SDimitry Andric // multi-line control statement.
44481ad6265SDimitry Andric return (Style.ColumnLimit == 0 || TheLine->Level * Style.IndentWidth +
44581ad6265SDimitry Andric TheLine->Last->TotalLength <=
44681ad6265SDimitry Andric Style.ColumnLimit)
447a7dea167SDimitry Andric ? 1
448a7dea167SDimitry Andric : 0;
44981ad6265SDimitry Andric }
45081ad6265SDimitry Andric if (TheLine->First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
45104eeddc0SDimitry Andric tok::kw_for, TT_ForEachMacro)) {
452a7dea167SDimitry Andric return (Style.BraceWrapping.AfterControlStatement ==
453a7dea167SDimitry Andric FormatStyle::BWACS_Always)
4540b57cec5SDimitry Andric ? tryMergeSimpleBlock(I, E, Limit)
4550b57cec5SDimitry Andric : 0;
45681ad6265SDimitry Andric }
45781ad6265SDimitry Andric if (TheLine->First->isOneOf(tok::kw_else, tok::kw_catch) &&
458480093f4SDimitry Andric Style.BraceWrapping.AfterControlStatement ==
459480093f4SDimitry Andric FormatStyle::BWACS_MultiLine) {
460480093f4SDimitry Andric // This case if different from the upper BWACS_MultiLine processing
461480093f4SDimitry Andric // in that a preceding r_brace is not on the same line as else/catch
462480093f4SDimitry Andric // most likely because of BeforeElse/BeforeCatch set to true.
463480093f4SDimitry Andric // If the line length doesn't fit ColumnLimit, leave l_brace on the
464480093f4SDimitry Andric // next line to respect the BWACS_MultiLine.
465480093f4SDimitry Andric return (Style.ColumnLimit == 0 ||
466480093f4SDimitry Andric TheLine->Last->TotalLength <= Style.ColumnLimit)
467480093f4SDimitry Andric ? 1
468480093f4SDimitry Andric : 0;
4690b57cec5SDimitry Andric }
47081ad6265SDimitry Andric }
47181ad6265SDimitry Andric if (PreviousLine && TheLine->First->is(tok::l_brace)) {
47281ad6265SDimitry Andric switch (PreviousLine->First->Tok.getKind()) {
47381ad6265SDimitry Andric case tok::at:
47481ad6265SDimitry Andric // Don't merge block with left brace wrapped after ObjC special blocks.
47581ad6265SDimitry Andric if (PreviousLine->First->Next) {
47681ad6265SDimitry Andric tok::ObjCKeywordKind kwId =
47781ad6265SDimitry Andric PreviousLine->First->Next->Tok.getObjCKeywordID();
47881ad6265SDimitry Andric if (kwId == tok::objc_autoreleasepool ||
47981ad6265SDimitry Andric kwId == tok::objc_synchronized) {
4800b57cec5SDimitry Andric return 0;
4810b57cec5SDimitry Andric }
48281ad6265SDimitry Andric }
48381ad6265SDimitry Andric break;
48481ad6265SDimitry Andric
48581ad6265SDimitry Andric case tok::kw_case:
48681ad6265SDimitry Andric case tok::kw_default:
48781ad6265SDimitry Andric // Don't merge block with left brace wrapped after case labels.
4880b57cec5SDimitry Andric return 0;
489e8d8bef9SDimitry Andric
49081ad6265SDimitry Andric default:
49181ad6265SDimitry Andric break;
49281ad6265SDimitry Andric }
49381ad6265SDimitry Andric }
49481ad6265SDimitry Andric
495e8d8bef9SDimitry Andric // Don't merge an empty template class or struct if SplitEmptyRecords
496e8d8bef9SDimitry Andric // is defined.
49781ad6265SDimitry Andric if (PreviousLine && Style.BraceWrapping.SplitEmptyRecord &&
49881ad6265SDimitry Andric TheLine->Last->is(tok::l_brace) && PreviousLine->Last) {
49981ad6265SDimitry Andric const FormatToken *Previous = PreviousLine->Last;
500e8d8bef9SDimitry Andric if (Previous) {
501e8d8bef9SDimitry Andric if (Previous->is(tok::comment))
502e8d8bef9SDimitry Andric Previous = Previous->getPreviousNonComment();
503e8d8bef9SDimitry Andric if (Previous) {
50481ad6265SDimitry Andric if (Previous->is(tok::greater) && !PreviousLine->InPPDirective)
505e8d8bef9SDimitry Andric return 0;
506e8d8bef9SDimitry Andric if (Previous->is(tok::identifier)) {
507e8d8bef9SDimitry Andric const FormatToken *PreviousPrevious =
508e8d8bef9SDimitry Andric Previous->getPreviousNonComment();
509e8d8bef9SDimitry Andric if (PreviousPrevious &&
51081ad6265SDimitry Andric PreviousPrevious->isOneOf(tok::kw_class, tok::kw_struct)) {
511e8d8bef9SDimitry Andric return 0;
512e8d8bef9SDimitry Andric }
513e8d8bef9SDimitry Andric }
514e8d8bef9SDimitry Andric }
515e8d8bef9SDimitry Andric }
5160eae32dcSDimitry Andric }
51781ad6265SDimitry Andric
51881ad6265SDimitry Andric if (TheLine->Last->is(tok::l_brace)) {
51981ad6265SDimitry Andric bool ShouldMerge = false;
52081ad6265SDimitry Andric // Try to merge records.
52181ad6265SDimitry Andric if (TheLine->Last->is(TT_EnumLBrace)) {
5220eae32dcSDimitry Andric ShouldMerge = Style.AllowShortEnumsOnASingleLine;
5235f757f3fSDimitry Andric } else if (TheLine->Last->is(TT_RequiresExpressionLBrace)) {
5245f757f3fSDimitry Andric ShouldMerge = Style.AllowShortCompoundRequirementOnASingleLine;
52581ad6265SDimitry Andric } else if (TheLine->Last->isOneOf(TT_ClassLBrace, TT_StructLBrace)) {
52681ad6265SDimitry Andric // NOTE: We use AfterClass (whereas AfterStruct exists) for both classes
52781ad6265SDimitry Andric // and structs, but it seems that wrapping is still handled correctly
52881ad6265SDimitry Andric // elsewhere.
52981ad6265SDimitry Andric ShouldMerge = !Style.BraceWrapping.AfterClass ||
53081ad6265SDimitry Andric (NextLine.First->is(tok::r_brace) &&
53181ad6265SDimitry Andric !Style.BraceWrapping.SplitEmptyRecord);
53206c3fb27SDimitry Andric } else if (TheLine->InPPDirective ||
53306c3fb27SDimitry Andric !TheLine->First->isOneOf(tok::kw_class, tok::kw_enum,
53406c3fb27SDimitry Andric tok::kw_struct)) {
53581ad6265SDimitry Andric // Try to merge a block with left brace unwrapped that wasn't yet
53681ad6265SDimitry Andric // covered.
5370eae32dcSDimitry Andric ShouldMerge = !Style.BraceWrapping.AfterFunction ||
53881ad6265SDimitry Andric (NextLine.First->is(tok::r_brace) &&
5390eae32dcSDimitry Andric !Style.BraceWrapping.SplitEmptyFunction);
5400eae32dcSDimitry Andric }
5410eae32dcSDimitry Andric return ShouldMerge ? tryMergeSimpleBlock(I, E, Limit) : 0;
5420b57cec5SDimitry Andric }
54381ad6265SDimitry Andric
54481ad6265SDimitry Andric // Try to merge a function block with left brace wrapped.
54581ad6265SDimitry Andric if (NextLine.First->is(TT_FunctionLBrace) &&
5460b57cec5SDimitry Andric Style.BraceWrapping.AfterFunction) {
54781ad6265SDimitry Andric if (NextLine.Last->is(TT_LineComment))
5480b57cec5SDimitry Andric return 0;
5490b57cec5SDimitry Andric
5500b57cec5SDimitry Andric // Check for Limit <= 2 to account for the " {".
5510b57cec5SDimitry Andric if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
5520b57cec5SDimitry Andric return 0;
5530b57cec5SDimitry Andric Limit -= 2;
5540b57cec5SDimitry Andric
5550b57cec5SDimitry Andric unsigned MergedLines = 0;
5560b57cec5SDimitry Andric if (MergeShortFunctions ||
5570b57cec5SDimitry Andric (Style.AllowShortFunctionsOnASingleLine >= FormatStyle::SFS_Empty &&
55881ad6265SDimitry Andric NextLine.First == NextLine.Last && I + 2 != E &&
5590b57cec5SDimitry Andric I[2]->First->is(tok::r_brace))) {
5600b57cec5SDimitry Andric MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
5610b57cec5SDimitry Andric // If we managed to merge the block, count the function header, which is
5620b57cec5SDimitry Andric // on a separate line.
5630b57cec5SDimitry Andric if (MergedLines > 0)
5640b57cec5SDimitry Andric ++MergedLines;
5650b57cec5SDimitry Andric }
5660b57cec5SDimitry Andric return MergedLines;
5670b57cec5SDimitry Andric }
568fe6060f1SDimitry Andric auto IsElseLine = [&TheLine]() -> bool {
569fe6060f1SDimitry Andric const FormatToken *First = TheLine->First;
570fe6060f1SDimitry Andric if (First->is(tok::kw_else))
571fe6060f1SDimitry Andric return true;
572fe6060f1SDimitry Andric
573fe6060f1SDimitry Andric return First->is(tok::r_brace) && First->Next &&
574fe6060f1SDimitry Andric First->Next->is(tok::kw_else);
575fe6060f1SDimitry Andric };
576fe6060f1SDimitry Andric if (TheLine->First->is(tok::kw_if) ||
577fe6060f1SDimitry Andric (IsElseLine() && (Style.AllowShortIfStatementsOnASingleLine ==
578fe6060f1SDimitry Andric FormatStyle::SIS_AllIfsAndElse))) {
5790b57cec5SDimitry Andric return Style.AllowShortIfStatementsOnASingleLine
5800b57cec5SDimitry Andric ? tryMergeSimpleControlStatement(I, E, Limit)
5810b57cec5SDimitry Andric : 0;
5820b57cec5SDimitry Andric }
58304eeddc0SDimitry Andric if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while, tok::kw_do,
58404eeddc0SDimitry Andric TT_ForEachMacro)) {
5850b57cec5SDimitry Andric return Style.AllowShortLoopsOnASingleLine
5860b57cec5SDimitry Andric ? tryMergeSimpleControlStatement(I, E, Limit)
5870b57cec5SDimitry Andric : 0;
5880b57cec5SDimitry Andric }
5890b57cec5SDimitry Andric if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
5900b57cec5SDimitry Andric return Style.AllowShortCaseLabelsOnASingleLine
5910b57cec5SDimitry Andric ? tryMergeShortCaseLabels(I, E, Limit)
5920b57cec5SDimitry Andric : 0;
5930b57cec5SDimitry Andric }
5940b57cec5SDimitry Andric if (TheLine->InPPDirective &&
5950b57cec5SDimitry Andric (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
5960b57cec5SDimitry Andric return tryMergeSimplePPDirective(I, E, Limit);
5970b57cec5SDimitry Andric }
5980b57cec5SDimitry Andric return 0;
5990b57cec5SDimitry Andric }
6000b57cec5SDimitry Andric
6010b57cec5SDimitry Andric unsigned
tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E,unsigned Limit)6020b57cec5SDimitry Andric tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
6030b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E,
6040b57cec5SDimitry Andric unsigned Limit) {
6050b57cec5SDimitry Andric if (Limit == 0)
6060b57cec5SDimitry Andric return 0;
6070b57cec5SDimitry Andric if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
6080b57cec5SDimitry Andric return 0;
6090b57cec5SDimitry Andric if (1 + I[1]->Last->TotalLength > Limit)
6100b57cec5SDimitry Andric return 0;
6110b57cec5SDimitry Andric return 1;
6120b57cec5SDimitry Andric }
6130b57cec5SDimitry Andric
tryMergeSimpleControlStatement(SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E,unsigned Limit)6140b57cec5SDimitry Andric unsigned tryMergeSimpleControlStatement(
6150b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator I,
6160b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
6170b57cec5SDimitry Andric if (Limit == 0)
6180b57cec5SDimitry Andric return 0;
619a7dea167SDimitry Andric if (Style.BraceWrapping.AfterControlStatement ==
620a7dea167SDimitry Andric FormatStyle::BWACS_Always &&
621a7dea167SDimitry Andric I[1]->First->is(tok::l_brace) &&
62281ad6265SDimitry Andric Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never) {
6230b57cec5SDimitry Andric return 0;
62481ad6265SDimitry Andric }
6250b57cec5SDimitry Andric if (I[1]->InPPDirective != (*I)->InPPDirective ||
62681ad6265SDimitry Andric (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) {
6270b57cec5SDimitry Andric return 0;
62881ad6265SDimitry Andric }
6290b57cec5SDimitry Andric Limit = limitConsideringMacros(I + 1, E, Limit);
6300b57cec5SDimitry Andric AnnotatedLine &Line = **I;
6315f757f3fSDimitry Andric if (Line.First->isNot(tok::kw_do) && Line.First->isNot(tok::kw_else) &&
6325f757f3fSDimitry Andric Line.Last->isNot(tok::kw_else) && Line.Last->isNot(tok::r_paren)) {
6335ffd83dbSDimitry Andric return 0;
63481ad6265SDimitry Andric }
63504eeddc0SDimitry Andric // Only merge `do while` if `do` is the only statement on the line.
6365f757f3fSDimitry Andric if (Line.First->is(tok::kw_do) && Line.Last->isNot(tok::kw_do))
6370b57cec5SDimitry Andric return 0;
6380b57cec5SDimitry Andric if (1 + I[1]->Last->TotalLength > Limit)
6390b57cec5SDimitry Andric return 0;
64004eeddc0SDimitry Andric // Don't merge with loops, ifs, a single semicolon or a line comment.
6410b57cec5SDimitry Andric if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, tok::kw_while,
64281ad6265SDimitry Andric TT_ForEachMacro, TT_LineComment)) {
6430b57cec5SDimitry Andric return 0;
64481ad6265SDimitry Andric }
6450b57cec5SDimitry Andric // Only inline simple if's (no nested if or else), unless specified
646fe6060f1SDimitry Andric if (Style.AllowShortIfStatementsOnASingleLine ==
647fe6060f1SDimitry Andric FormatStyle::SIS_WithoutElse) {
6480b57cec5SDimitry Andric if (I + 2 != E && Line.startsWith(tok::kw_if) &&
64981ad6265SDimitry Andric I[2]->First->is(tok::kw_else)) {
6500b57cec5SDimitry Andric return 0;
6510b57cec5SDimitry Andric }
65281ad6265SDimitry Andric }
6530b57cec5SDimitry Andric return 1;
6540b57cec5SDimitry Andric }
6550b57cec5SDimitry Andric
6560b57cec5SDimitry Andric unsigned
tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E,unsigned Limit)6570b57cec5SDimitry Andric tryMergeShortCaseLabels(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
6580b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E,
6590b57cec5SDimitry Andric unsigned Limit) {
6600b57cec5SDimitry Andric if (Limit == 0 || I + 1 == E ||
66181ad6265SDimitry Andric I[1]->First->isOneOf(tok::kw_case, tok::kw_default)) {
6620b57cec5SDimitry Andric return 0;
66381ad6265SDimitry Andric }
6640b57cec5SDimitry Andric if (I[0]->Last->is(tok::l_brace) || I[1]->First->is(tok::l_brace))
6650b57cec5SDimitry Andric return 0;
6660b57cec5SDimitry Andric unsigned NumStmts = 0;
6670b57cec5SDimitry Andric unsigned Length = 0;
6680b57cec5SDimitry Andric bool EndsWithComment = false;
6690b57cec5SDimitry Andric bool InPPDirective = I[0]->InPPDirective;
670bdd1243dSDimitry Andric bool InMacroBody = I[0]->InMacroBody;
6710b57cec5SDimitry Andric const unsigned Level = I[0]->Level;
6720b57cec5SDimitry Andric for (; NumStmts < 3; ++NumStmts) {
6730b57cec5SDimitry Andric if (I + 1 + NumStmts == E)
6740b57cec5SDimitry Andric break;
6750b57cec5SDimitry Andric const AnnotatedLine *Line = I[1 + NumStmts];
6760b57cec5SDimitry Andric if (Line->InPPDirective != InPPDirective)
6770b57cec5SDimitry Andric break;
678bdd1243dSDimitry Andric if (Line->InMacroBody != InMacroBody)
679bdd1243dSDimitry Andric break;
6800b57cec5SDimitry Andric if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
6810b57cec5SDimitry Andric break;
6820b57cec5SDimitry Andric if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
6830b57cec5SDimitry Andric tok::kw_while) ||
68481ad6265SDimitry Andric EndsWithComment) {
6850b57cec5SDimitry Andric return 0;
68681ad6265SDimitry Andric }
6870b57cec5SDimitry Andric if (Line->First->is(tok::comment)) {
6880b57cec5SDimitry Andric if (Level != Line->Level)
6890b57cec5SDimitry Andric return 0;
6900b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator J = I + 2 + NumStmts;
6910b57cec5SDimitry Andric for (; J != E; ++J) {
6920b57cec5SDimitry Andric Line = *J;
6930b57cec5SDimitry Andric if (Line->InPPDirective != InPPDirective)
6940b57cec5SDimitry Andric break;
6950b57cec5SDimitry Andric if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
6960b57cec5SDimitry Andric break;
6970b57cec5SDimitry Andric if (Line->First->isNot(tok::comment) || Level != Line->Level)
6980b57cec5SDimitry Andric return 0;
6990b57cec5SDimitry Andric }
7000b57cec5SDimitry Andric break;
7010b57cec5SDimitry Andric }
7020b57cec5SDimitry Andric if (Line->Last->is(tok::comment))
7030b57cec5SDimitry Andric EndsWithComment = true;
7040b57cec5SDimitry Andric Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
7050b57cec5SDimitry Andric }
7060b57cec5SDimitry Andric if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
7070b57cec5SDimitry Andric return 0;
7080b57cec5SDimitry Andric return NumStmts;
7090b57cec5SDimitry Andric }
7100b57cec5SDimitry Andric
7110b57cec5SDimitry Andric unsigned
tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E,unsigned Limit)7120b57cec5SDimitry Andric tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
7130b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E,
7140b57cec5SDimitry Andric unsigned Limit) {
71581ad6265SDimitry Andric // Don't merge with a preprocessor directive.
71681ad6265SDimitry Andric if (I[1]->Type == LT_PreprocessorDirective)
71781ad6265SDimitry Andric return 0;
71881ad6265SDimitry Andric
7190b57cec5SDimitry Andric AnnotatedLine &Line = **I;
7200b57cec5SDimitry Andric
7210b57cec5SDimitry Andric // Don't merge ObjC @ keywords and methods.
7220b57cec5SDimitry Andric // FIXME: If an option to allow short exception handling clauses on a single
7230b57cec5SDimitry Andric // line is added, change this to not return for @try and friends.
7240b57cec5SDimitry Andric if (Style.Language != FormatStyle::LK_Java &&
72581ad6265SDimitry Andric Line.First->isOneOf(tok::at, tok::minus, tok::plus)) {
7260b57cec5SDimitry Andric return 0;
72781ad6265SDimitry Andric }
7280b57cec5SDimitry Andric
7290b57cec5SDimitry Andric // Check that the current line allows merging. This depends on whether we
7300b57cec5SDimitry Andric // are in a control flow statements as well as several style flags.
7314824e7fdSDimitry Andric if (Line.First->is(tok::kw_case) ||
73281ad6265SDimitry Andric (Line.First->Next && Line.First->Next->is(tok::kw_else))) {
7330b57cec5SDimitry Andric return 0;
73481ad6265SDimitry Andric }
7350b57cec5SDimitry Andric // default: in switch statement
7360b57cec5SDimitry Andric if (Line.First->is(tok::kw_default)) {
7370b57cec5SDimitry Andric const FormatToken *Tok = Line.First->getNextNonComment();
7380b57cec5SDimitry Andric if (Tok && Tok->is(tok::colon))
7390b57cec5SDimitry Andric return 0;
7400b57cec5SDimitry Andric }
741bdd1243dSDimitry Andric
742bdd1243dSDimitry Andric auto IsCtrlStmt = [](const auto &Line) {
743bdd1243dSDimitry Andric return Line.First->isOneOf(tok::kw_if, tok::kw_else, tok::kw_while,
744bdd1243dSDimitry Andric tok::kw_do, tok::kw_for, TT_ForEachMacro);
745bdd1243dSDimitry Andric };
746bdd1243dSDimitry Andric
747bdd1243dSDimitry Andric const bool IsSplitBlock =
748bdd1243dSDimitry Andric Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never ||
749bdd1243dSDimitry Andric (Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Empty &&
750bdd1243dSDimitry Andric I[1]->First->isNot(tok::r_brace));
751bdd1243dSDimitry Andric
752bdd1243dSDimitry Andric if (IsCtrlStmt(Line) ||
753bdd1243dSDimitry Andric Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
754bdd1243dSDimitry Andric tok::kw___finally, tok::r_brace,
755bdd1243dSDimitry Andric Keywords.kw___except)) {
756bdd1243dSDimitry Andric if (IsSplitBlock)
7570b57cec5SDimitry Andric return 0;
7580b57cec5SDimitry Andric // Don't merge when we can't except the case when
7590b57cec5SDimitry Andric // the control statement block is empty
7600b57cec5SDimitry Andric if (!Style.AllowShortIfStatementsOnASingleLine &&
7614824e7fdSDimitry Andric Line.First->isOneOf(tok::kw_if, tok::kw_else) &&
7620b57cec5SDimitry Andric !Style.BraceWrapping.AfterControlStatement &&
7635f757f3fSDimitry Andric I[1]->First->isNot(tok::r_brace)) {
7640b57cec5SDimitry Andric return 0;
76581ad6265SDimitry Andric }
7660b57cec5SDimitry Andric if (!Style.AllowShortIfStatementsOnASingleLine &&
7674824e7fdSDimitry Andric Line.First->isOneOf(tok::kw_if, tok::kw_else) &&
768a7dea167SDimitry Andric Style.BraceWrapping.AfterControlStatement ==
769a7dea167SDimitry Andric FormatStyle::BWACS_Always &&
7705f757f3fSDimitry Andric I + 2 != E && I[2]->First->isNot(tok::r_brace)) {
7710b57cec5SDimitry Andric return 0;
77281ad6265SDimitry Andric }
7730b57cec5SDimitry Andric if (!Style.AllowShortLoopsOnASingleLine &&
77404eeddc0SDimitry Andric Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,
77504eeddc0SDimitry Andric TT_ForEachMacro) &&
7760b57cec5SDimitry Andric !Style.BraceWrapping.AfterControlStatement &&
7775f757f3fSDimitry Andric I[1]->First->isNot(tok::r_brace)) {
7780b57cec5SDimitry Andric return 0;
77981ad6265SDimitry Andric }
7800b57cec5SDimitry Andric if (!Style.AllowShortLoopsOnASingleLine &&
78104eeddc0SDimitry Andric Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for,
78204eeddc0SDimitry Andric TT_ForEachMacro) &&
783a7dea167SDimitry Andric Style.BraceWrapping.AfterControlStatement ==
784a7dea167SDimitry Andric FormatStyle::BWACS_Always &&
7855f757f3fSDimitry Andric I + 2 != E && I[2]->First->isNot(tok::r_brace)) {
7860b57cec5SDimitry Andric return 0;
78781ad6265SDimitry Andric }
7880b57cec5SDimitry Andric // FIXME: Consider an option to allow short exception handling clauses on
7890b57cec5SDimitry Andric // a single line.
7900b57cec5SDimitry Andric // FIXME: This isn't covered by tests.
7910b57cec5SDimitry Andric // FIXME: For catch, __except, __finally the first token on the line
7920b57cec5SDimitry Andric // is '}', so this isn't correct here.
7930b57cec5SDimitry Andric if (Line.First->isOneOf(tok::kw_try, tok::kw___try, tok::kw_catch,
79481ad6265SDimitry Andric Keywords.kw___except, tok::kw___finally)) {
7950b57cec5SDimitry Andric return 0;
7960b57cec5SDimitry Andric }
79781ad6265SDimitry Andric }
7980b57cec5SDimitry Andric
7995f757f3fSDimitry Andric if (const auto *LastNonComment = Line.getLastNonComment();
8005f757f3fSDimitry Andric LastNonComment && LastNonComment->is(tok::l_brace)) {
801bdd1243dSDimitry Andric if (IsSplitBlock && Line.First == Line.Last &&
802bdd1243dSDimitry Andric I > AnnotatedLines.begin() &&
803bdd1243dSDimitry Andric (I[-1]->endsWith(tok::kw_else) || IsCtrlStmt(*I[-1]))) {
804bdd1243dSDimitry Andric return 0;
805bdd1243dSDimitry Andric }
8060b57cec5SDimitry Andric FormatToken *Tok = I[1]->First;
80781ad6265SDimitry Andric auto ShouldMerge = [Tok]() {
80881ad6265SDimitry Andric if (Tok->isNot(tok::r_brace) || Tok->MustBreakBefore)
80981ad6265SDimitry Andric return false;
81081ad6265SDimitry Andric const FormatToken *Next = Tok->getNextNonComment();
81181ad6265SDimitry Andric return !Next || Next->is(tok::semi);
81281ad6265SDimitry Andric };
81381ad6265SDimitry Andric
81481ad6265SDimitry Andric if (ShouldMerge()) {
8150b57cec5SDimitry Andric // We merge empty blocks even if the line exceeds the column limit.
8165f757f3fSDimitry Andric Tok->SpacesRequiredBefore =
8175f757f3fSDimitry Andric (Style.SpaceInEmptyBlock || Line.Last->is(tok::comment)) ? 1 : 0;
8180b57cec5SDimitry Andric Tok->CanBreakBefore = true;
8190b57cec5SDimitry Andric return 1;
8200b57cec5SDimitry Andric } else if (Limit != 0 && !Line.startsWithNamespace() &&
8210b57cec5SDimitry Andric !startsExternCBlock(Line)) {
8220b57cec5SDimitry Andric // We don't merge short records.
82381ad6265SDimitry Andric if (isRecordLBrace(*Line.Last))
8240b57cec5SDimitry Andric return 0;
8250b57cec5SDimitry Andric
8260b57cec5SDimitry Andric // Check that we still have three lines and they fit into the limit.
8270b57cec5SDimitry Andric if (I + 2 == E || I[2]->Type == LT_Invalid)
8280b57cec5SDimitry Andric return 0;
8290b57cec5SDimitry Andric Limit = limitConsideringMacros(I + 2, E, Limit);
8300b57cec5SDimitry Andric
8310b57cec5SDimitry Andric if (!nextTwoLinesFitInto(I, Limit))
8320b57cec5SDimitry Andric return 0;
8330b57cec5SDimitry Andric
8340b57cec5SDimitry Andric // Second, check that the next line does not contain any braces - if it
8350b57cec5SDimitry Andric // does, readability declines when putting it into a single line.
8360b57cec5SDimitry Andric if (I[1]->Last->is(TT_LineComment))
8370b57cec5SDimitry Andric return 0;
8380b57cec5SDimitry Andric do {
839e8d8bef9SDimitry Andric if (Tok->is(tok::l_brace) && Tok->isNot(BK_BracedInit))
8400b57cec5SDimitry Andric return 0;
8410b57cec5SDimitry Andric Tok = Tok->Next;
8420b57cec5SDimitry Andric } while (Tok);
8430b57cec5SDimitry Andric
8440b57cec5SDimitry Andric // Last, check that the third line starts with a closing brace.
8450b57cec5SDimitry Andric Tok = I[2]->First;
8460b57cec5SDimitry Andric if (Tok->isNot(tok::r_brace))
8470b57cec5SDimitry Andric return 0;
8480b57cec5SDimitry Andric
8490b57cec5SDimitry Andric // Don't merge "if (a) { .. } else {".
8500b57cec5SDimitry Andric if (Tok->Next && Tok->Next->is(tok::kw_else))
8510b57cec5SDimitry Andric return 0;
8520b57cec5SDimitry Andric
853a7dea167SDimitry Andric // Don't merge a trailing multi-line control statement block like:
854a7dea167SDimitry Andric // } else if (foo &&
855a7dea167SDimitry Andric // bar)
856a7dea167SDimitry Andric // { <-- current Line
857a7dea167SDimitry Andric // baz();
858a7dea167SDimitry Andric // }
8594824e7fdSDimitry Andric if (Line.First == Line.Last && Line.First->isNot(TT_FunctionLBrace) &&
860a7dea167SDimitry Andric Style.BraceWrapping.AfterControlStatement ==
86181ad6265SDimitry Andric FormatStyle::BWACS_MultiLine) {
862a7dea167SDimitry Andric return 0;
86381ad6265SDimitry Andric }
864a7dea167SDimitry Andric
8650b57cec5SDimitry Andric return 2;
8660b57cec5SDimitry Andric }
8670b57cec5SDimitry Andric } else if (I[1]->First->is(tok::l_brace)) {
8680b57cec5SDimitry Andric if (I[1]->Last->is(TT_LineComment))
8690b57cec5SDimitry Andric return 0;
8700b57cec5SDimitry Andric
8710b57cec5SDimitry Andric // Check for Limit <= 2 to account for the " {".
8720b57cec5SDimitry Andric if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(*I)))
8730b57cec5SDimitry Andric return 0;
8740b57cec5SDimitry Andric Limit -= 2;
8750b57cec5SDimitry Andric unsigned MergedLines = 0;
876a7dea167SDimitry Andric if (Style.AllowShortBlocksOnASingleLine != FormatStyle::SBS_Never ||
8770b57cec5SDimitry Andric (I[1]->First == I[1]->Last && I + 2 != E &&
8780b57cec5SDimitry Andric I[2]->First->is(tok::r_brace))) {
8790b57cec5SDimitry Andric MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
8800b57cec5SDimitry Andric // If we managed to merge the block, count the statement header, which
8810b57cec5SDimitry Andric // is on a separate line.
8820b57cec5SDimitry Andric if (MergedLines > 0)
8830b57cec5SDimitry Andric ++MergedLines;
8840b57cec5SDimitry Andric }
8850b57cec5SDimitry Andric return MergedLines;
8860b57cec5SDimitry Andric }
8870b57cec5SDimitry Andric return 0;
8880b57cec5SDimitry Andric }
8890b57cec5SDimitry Andric
8900b57cec5SDimitry Andric /// Returns the modified column limit for \p I if it is inside a macro and
8910b57cec5SDimitry Andric /// needs a trailing '\'.
8920b57cec5SDimitry Andric unsigned
limitConsideringMacros(SmallVectorImpl<AnnotatedLine * >::const_iterator I,SmallVectorImpl<AnnotatedLine * >::const_iterator E,unsigned Limit)8930b57cec5SDimitry Andric limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
8940b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator E,
8950b57cec5SDimitry Andric unsigned Limit) {
8960b57cec5SDimitry Andric if (I[0]->InPPDirective && I + 1 != E &&
8975f757f3fSDimitry Andric !I[1]->First->HasUnescapedNewline && I[1]->First->isNot(tok::eof)) {
8980b57cec5SDimitry Andric return Limit < 2 ? 0 : Limit - 2;
8990b57cec5SDimitry Andric }
9000b57cec5SDimitry Andric return Limit;
9010b57cec5SDimitry Andric }
9020b57cec5SDimitry Andric
nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine * >::const_iterator I,unsigned Limit)9030b57cec5SDimitry Andric bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
9040b57cec5SDimitry Andric unsigned Limit) {
9050b57cec5SDimitry Andric if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
9060b57cec5SDimitry Andric return false;
9070b57cec5SDimitry Andric return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
9080b57cec5SDimitry Andric }
9090b57cec5SDimitry Andric
containsMustBreak(const AnnotatedLine * Line)9100b57cec5SDimitry Andric bool containsMustBreak(const AnnotatedLine *Line) {
91106c3fb27SDimitry Andric assert(Line->First);
91206c3fb27SDimitry Andric // Ignore the first token, because in this situation, it applies more to the
91306c3fb27SDimitry Andric // last token of the previous line.
91406c3fb27SDimitry Andric for (const FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next)
9150b57cec5SDimitry Andric if (Tok->MustBreakBefore)
9160b57cec5SDimitry Andric return true;
9170b57cec5SDimitry Andric return false;
9180b57cec5SDimitry Andric }
9190b57cec5SDimitry Andric
join(AnnotatedLine & A,const AnnotatedLine & B)9200b57cec5SDimitry Andric void join(AnnotatedLine &A, const AnnotatedLine &B) {
9210b57cec5SDimitry Andric assert(!A.Last->Next);
9220b57cec5SDimitry Andric assert(!B.First->Previous);
9230b57cec5SDimitry Andric if (B.Affected)
9240b57cec5SDimitry Andric A.Affected = true;
9250b57cec5SDimitry Andric A.Last->Next = B.First;
9260b57cec5SDimitry Andric B.First->Previous = A.Last;
9270b57cec5SDimitry Andric B.First->CanBreakBefore = true;
9280b57cec5SDimitry Andric unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
9290b57cec5SDimitry Andric for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
9300b57cec5SDimitry Andric Tok->TotalLength += LengthA;
9310b57cec5SDimitry Andric A.Last = Tok;
9320b57cec5SDimitry Andric }
9330b57cec5SDimitry Andric }
9340b57cec5SDimitry Andric
9350b57cec5SDimitry Andric const FormatStyle &Style;
9360b57cec5SDimitry Andric const AdditionalKeywords &Keywords;
9370b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *>::const_iterator End;
9380b57cec5SDimitry Andric
9390b57cec5SDimitry Andric SmallVectorImpl<AnnotatedLine *>::const_iterator Next;
9400b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines;
9410b57cec5SDimitry Andric };
9420b57cec5SDimitry Andric
markFinalized(FormatToken * Tok)9430b57cec5SDimitry Andric static void markFinalized(FormatToken *Tok) {
9445f757f3fSDimitry Andric if (Tok->is(tok::hash) && !Tok->Previous && Tok->Next &&
9455f757f3fSDimitry Andric Tok->Next->isOneOf(tok::pp_if, tok::pp_ifdef, tok::pp_ifndef,
9465f757f3fSDimitry Andric tok::pp_elif, tok::pp_elifdef, tok::pp_elifndef,
9475f757f3fSDimitry Andric tok::pp_else, tok::pp_endif)) {
9485f757f3fSDimitry Andric Tok = Tok->Next;
9495f757f3fSDimitry Andric }
9500b57cec5SDimitry Andric for (; Tok; Tok = Tok->Next) {
95106c3fb27SDimitry Andric if (Tok->MacroCtx && Tok->MacroCtx->Role == MR_ExpandedArg) {
95206c3fb27SDimitry Andric // In the first pass we format all macro arguments in the expanded token
95306c3fb27SDimitry Andric // stream. Instead of finalizing the macro arguments, we mark that they
95406c3fb27SDimitry Andric // will be modified as unexpanded arguments (as part of the macro call
95506c3fb27SDimitry Andric // formatting) in the next pass.
95606c3fb27SDimitry Andric Tok->MacroCtx->Role = MR_UnexpandedArg;
957297eecfbSDimitry Andric // Reset whether spaces or a line break are required before this token, as
958297eecfbSDimitry Andric // that is context dependent, and that context may change when formatting
959297eecfbSDimitry Andric // the macro call. For example, given M(x) -> 2 * x, and the macro call
960297eecfbSDimitry Andric // M(var), the token 'var' will have SpacesRequiredBefore = 1 after being
96106c3fb27SDimitry Andric // formatted as part of the expanded macro, but SpacesRequiredBefore = 0
96206c3fb27SDimitry Andric // for its position within the macro call.
96306c3fb27SDimitry Andric Tok->SpacesRequiredBefore = 0;
964297eecfbSDimitry Andric if (!Tok->MustBreakBeforeFinalized)
965297eecfbSDimitry Andric Tok->MustBreakBefore = 0;
96606c3fb27SDimitry Andric } else {
9670b57cec5SDimitry Andric Tok->Finalized = true;
96806c3fb27SDimitry Andric }
9690b57cec5SDimitry Andric }
9700b57cec5SDimitry Andric }
9710b57cec5SDimitry Andric
9720b57cec5SDimitry Andric #ifndef NDEBUG
printLineState(const LineState & State)9730b57cec5SDimitry Andric static void printLineState(const LineState &State) {
9740b57cec5SDimitry Andric llvm::dbgs() << "State: ";
9750b57cec5SDimitry Andric for (const ParenState &P : State.Stack) {
9760b57cec5SDimitry Andric llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
9770b57cec5SDimitry Andric << P.LastSpace << "|" << P.NestedBlockIndent << " ";
9780b57cec5SDimitry Andric }
9790b57cec5SDimitry Andric llvm::dbgs() << State.NextToken->TokenText << "\n";
9800b57cec5SDimitry Andric }
9810b57cec5SDimitry Andric #endif
9820b57cec5SDimitry Andric
9830b57cec5SDimitry Andric /// Base class for classes that format one \c AnnotatedLine.
9840b57cec5SDimitry Andric class LineFormatter {
9850b57cec5SDimitry Andric public:
LineFormatter(ContinuationIndenter * Indenter,WhitespaceManager * Whitespaces,const FormatStyle & Style,UnwrappedLineFormatter * BlockFormatter)9860b57cec5SDimitry Andric LineFormatter(ContinuationIndenter *Indenter, WhitespaceManager *Whitespaces,
9870b57cec5SDimitry Andric const FormatStyle &Style,
9880b57cec5SDimitry Andric UnwrappedLineFormatter *BlockFormatter)
9890b57cec5SDimitry Andric : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
9900b57cec5SDimitry Andric BlockFormatter(BlockFormatter) {}
~LineFormatter()9910b57cec5SDimitry Andric virtual ~LineFormatter() {}
9920b57cec5SDimitry Andric
9930b57cec5SDimitry Andric /// Formats an \c AnnotatedLine and returns the penalty.
9940b57cec5SDimitry Andric ///
9950b57cec5SDimitry Andric /// If \p DryRun is \c false, directly applies the changes.
9960b57cec5SDimitry Andric virtual unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
9970b57cec5SDimitry Andric unsigned FirstStartColumn, bool DryRun) = 0;
9980b57cec5SDimitry Andric
9990b57cec5SDimitry Andric protected:
10000b57cec5SDimitry Andric /// If the \p State's next token is an r_brace closing a nested block,
10010b57cec5SDimitry Andric /// format the nested block before it.
10020b57cec5SDimitry Andric ///
10030b57cec5SDimitry Andric /// Returns \c true if all children could be placed successfully and adapts
10040b57cec5SDimitry Andric /// \p Penalty as well as \p State. If \p DryRun is false, also directly
10050b57cec5SDimitry Andric /// creates changes using \c Whitespaces.
10060b57cec5SDimitry Andric ///
10070b57cec5SDimitry Andric /// The crucial idea here is that children always get formatted upon
10080b57cec5SDimitry Andric /// encountering the closing brace right after the nested block. Now, if we
10090b57cec5SDimitry Andric /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
10100b57cec5SDimitry Andric /// \c false), the entire block has to be kept on the same line (which is only
10110b57cec5SDimitry Andric /// possible if it fits on the line, only contains a single statement, etc.
10120b57cec5SDimitry Andric ///
10130b57cec5SDimitry Andric /// If \p NewLine is true, we format the nested block on separate lines, i.e.
10140b57cec5SDimitry Andric /// break after the "{", format all lines with correct indentation and the put
10150b57cec5SDimitry Andric /// the closing "}" on yet another new line.
10160b57cec5SDimitry Andric ///
10170b57cec5SDimitry Andric /// This enables us to keep the simple structure of the
10180b57cec5SDimitry Andric /// \c UnwrappedLineFormatter, where we only have two options for each token:
10190b57cec5SDimitry Andric /// break or don't break.
formatChildren(LineState & State,bool NewLine,bool DryRun,unsigned & Penalty)10200b57cec5SDimitry Andric bool formatChildren(LineState &State, bool NewLine, bool DryRun,
10210b57cec5SDimitry Andric unsigned &Penalty) {
10220b57cec5SDimitry Andric const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
102306c3fb27SDimitry Andric bool HasLBrace = LBrace && LBrace->is(tok::l_brace) && LBrace->is(BK_Block);
10240b57cec5SDimitry Andric FormatToken &Previous = *State.NextToken->Previous;
102506c3fb27SDimitry Andric if (Previous.Children.size() == 0 || (!HasLBrace && !LBrace->MacroParent)) {
10260b57cec5SDimitry Andric // The previous token does not open a block. Nothing to do. We don't
10270b57cec5SDimitry Andric // assert so that we can simply call this function for all tokens.
10280b57cec5SDimitry Andric return true;
102981ad6265SDimitry Andric }
10300b57cec5SDimitry Andric
103106c3fb27SDimitry Andric if (NewLine || Previous.MacroParent) {
1032fe6060f1SDimitry Andric const ParenState &P = State.Stack.back();
1033fe6060f1SDimitry Andric
1034fe6060f1SDimitry Andric int AdditionalIndent =
1035fe6060f1SDimitry Andric P.Indent - Previous.Children[0]->Level * Style.IndentWidth;
10360b57cec5SDimitry Andric Penalty +=
10370b57cec5SDimitry Andric BlockFormatter->format(Previous.Children, DryRun, AdditionalIndent,
10380b57cec5SDimitry Andric /*FixBadIndentation=*/true);
10390b57cec5SDimitry Andric return true;
10400b57cec5SDimitry Andric }
10410b57cec5SDimitry Andric
10420b57cec5SDimitry Andric if (Previous.Children[0]->First->MustBreakBefore)
10430b57cec5SDimitry Andric return false;
10440b57cec5SDimitry Andric
10450b57cec5SDimitry Andric // Cannot merge into one line if this line ends on a comment.
10460b57cec5SDimitry Andric if (Previous.is(tok::comment))
10470b57cec5SDimitry Andric return false;
10480b57cec5SDimitry Andric
10490b57cec5SDimitry Andric // Cannot merge multiple statements into a single line.
10500b57cec5SDimitry Andric if (Previous.Children.size() > 1)
10510b57cec5SDimitry Andric return false;
10520b57cec5SDimitry Andric
10530b57cec5SDimitry Andric const AnnotatedLine *Child = Previous.Children[0];
10540b57cec5SDimitry Andric // We can't put the closing "}" on a line with a trailing comment.
10550b57cec5SDimitry Andric if (Child->Last->isTrailingComment())
10560b57cec5SDimitry Andric return false;
10570b57cec5SDimitry Andric
10580b57cec5SDimitry Andric // If the child line exceeds the column limit, we wouldn't want to merge it.
10590b57cec5SDimitry Andric // We add +2 for the trailing " }".
10600b57cec5SDimitry Andric if (Style.ColumnLimit > 0 &&
106181ad6265SDimitry Andric Child->Last->TotalLength + State.Column + 2 > Style.ColumnLimit) {
10620b57cec5SDimitry Andric return false;
106381ad6265SDimitry Andric }
10640b57cec5SDimitry Andric
10650b57cec5SDimitry Andric if (!DryRun) {
10660b57cec5SDimitry Andric Whitespaces->replaceWhitespace(
10670b57cec5SDimitry Andric *Child->First, /*Newlines=*/0, /*Spaces=*/1,
10685ffd83dbSDimitry Andric /*StartOfTokenColumn=*/State.Column, /*IsAligned=*/false,
10695ffd83dbSDimitry Andric State.Line->InPPDirective);
10700b57cec5SDimitry Andric }
10710b57cec5SDimitry Andric Penalty +=
10720b57cec5SDimitry Andric formatLine(*Child, State.Column + 1, /*FirstStartColumn=*/0, DryRun);
10735f757f3fSDimitry Andric if (!DryRun)
10745f757f3fSDimitry Andric markFinalized(Child->First);
10750b57cec5SDimitry Andric
10760b57cec5SDimitry Andric State.Column += 1 + Child->Last->TotalLength;
10770b57cec5SDimitry Andric return true;
10780b57cec5SDimitry Andric }
10790b57cec5SDimitry Andric
10800b57cec5SDimitry Andric ContinuationIndenter *Indenter;
10810b57cec5SDimitry Andric
10820b57cec5SDimitry Andric private:
10830b57cec5SDimitry Andric WhitespaceManager *Whitespaces;
10840b57cec5SDimitry Andric const FormatStyle &Style;
10850b57cec5SDimitry Andric UnwrappedLineFormatter *BlockFormatter;
10860b57cec5SDimitry Andric };
10870b57cec5SDimitry Andric
10880b57cec5SDimitry Andric /// Formatter that keeps the existing line breaks.
10890b57cec5SDimitry Andric class NoColumnLimitLineFormatter : public LineFormatter {
10900b57cec5SDimitry Andric public:
NoColumnLimitLineFormatter(ContinuationIndenter * Indenter,WhitespaceManager * Whitespaces,const FormatStyle & Style,UnwrappedLineFormatter * BlockFormatter)10910b57cec5SDimitry Andric NoColumnLimitLineFormatter(ContinuationIndenter *Indenter,
10920b57cec5SDimitry Andric WhitespaceManager *Whitespaces,
10930b57cec5SDimitry Andric const FormatStyle &Style,
10940b57cec5SDimitry Andric UnwrappedLineFormatter *BlockFormatter)
10950b57cec5SDimitry Andric : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
10960b57cec5SDimitry Andric
10970b57cec5SDimitry Andric /// Formats the line, simply keeping all of the input's line breaking
10980b57cec5SDimitry Andric /// decisions.
formatLine(const AnnotatedLine & Line,unsigned FirstIndent,unsigned FirstStartColumn,bool DryRun)10990b57cec5SDimitry Andric unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
11000b57cec5SDimitry Andric unsigned FirstStartColumn, bool DryRun) override {
11010b57cec5SDimitry Andric assert(!DryRun);
11020b57cec5SDimitry Andric LineState State = Indenter->getInitialState(FirstIndent, FirstStartColumn,
11030b57cec5SDimitry Andric &Line, /*DryRun=*/false);
11040b57cec5SDimitry Andric while (State.NextToken) {
11050b57cec5SDimitry Andric bool Newline =
11060b57cec5SDimitry Andric Indenter->mustBreak(State) ||
11070b57cec5SDimitry Andric (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
11080b57cec5SDimitry Andric unsigned Penalty = 0;
11090b57cec5SDimitry Andric formatChildren(State, Newline, /*DryRun=*/false, Penalty);
11100b57cec5SDimitry Andric Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
11110b57cec5SDimitry Andric }
11120b57cec5SDimitry Andric return 0;
11130b57cec5SDimitry Andric }
11140b57cec5SDimitry Andric };
11150b57cec5SDimitry Andric
11160b57cec5SDimitry Andric /// Formatter that puts all tokens into a single line without breaks.
11170b57cec5SDimitry Andric class NoLineBreakFormatter : public LineFormatter {
11180b57cec5SDimitry Andric public:
NoLineBreakFormatter(ContinuationIndenter * Indenter,WhitespaceManager * Whitespaces,const FormatStyle & Style,UnwrappedLineFormatter * BlockFormatter)11190b57cec5SDimitry Andric NoLineBreakFormatter(ContinuationIndenter *Indenter,
11200b57cec5SDimitry Andric WhitespaceManager *Whitespaces, const FormatStyle &Style,
11210b57cec5SDimitry Andric UnwrappedLineFormatter *BlockFormatter)
11220b57cec5SDimitry Andric : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
11230b57cec5SDimitry Andric
11240b57cec5SDimitry Andric /// Puts all tokens into a single line.
formatLine(const AnnotatedLine & Line,unsigned FirstIndent,unsigned FirstStartColumn,bool DryRun)11250b57cec5SDimitry Andric unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
11260b57cec5SDimitry Andric unsigned FirstStartColumn, bool DryRun) override {
11270b57cec5SDimitry Andric unsigned Penalty = 0;
11280b57cec5SDimitry Andric LineState State =
11290b57cec5SDimitry Andric Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
11300b57cec5SDimitry Andric while (State.NextToken) {
11310b57cec5SDimitry Andric formatChildren(State, /*NewLine=*/false, DryRun, Penalty);
11320b57cec5SDimitry Andric Indenter->addTokenToState(
11330b57cec5SDimitry Andric State, /*Newline=*/State.NextToken->MustBreakBefore, DryRun);
11340b57cec5SDimitry Andric }
11350b57cec5SDimitry Andric return Penalty;
11360b57cec5SDimitry Andric }
11370b57cec5SDimitry Andric };
11380b57cec5SDimitry Andric
11390b57cec5SDimitry Andric /// Finds the best way to break lines.
11400b57cec5SDimitry Andric class OptimizingLineFormatter : public LineFormatter {
11410b57cec5SDimitry Andric public:
OptimizingLineFormatter(ContinuationIndenter * Indenter,WhitespaceManager * Whitespaces,const FormatStyle & Style,UnwrappedLineFormatter * BlockFormatter)11420b57cec5SDimitry Andric OptimizingLineFormatter(ContinuationIndenter *Indenter,
11430b57cec5SDimitry Andric WhitespaceManager *Whitespaces,
11440b57cec5SDimitry Andric const FormatStyle &Style,
11450b57cec5SDimitry Andric UnwrappedLineFormatter *BlockFormatter)
11460b57cec5SDimitry Andric : LineFormatter(Indenter, Whitespaces, Style, BlockFormatter) {}
11470b57cec5SDimitry Andric
11480b57cec5SDimitry Andric /// Formats the line by finding the best line breaks with line lengths
11490b57cec5SDimitry Andric /// below the column limit.
formatLine(const AnnotatedLine & Line,unsigned FirstIndent,unsigned FirstStartColumn,bool DryRun)11500b57cec5SDimitry Andric unsigned formatLine(const AnnotatedLine &Line, unsigned FirstIndent,
11510b57cec5SDimitry Andric unsigned FirstStartColumn, bool DryRun) override {
11520b57cec5SDimitry Andric LineState State =
11530b57cec5SDimitry Andric Indenter->getInitialState(FirstIndent, FirstStartColumn, &Line, DryRun);
11540b57cec5SDimitry Andric
11550b57cec5SDimitry Andric // If the ObjC method declaration does not fit on a line, we should format
11560b57cec5SDimitry Andric // it with one arg per line.
11570b57cec5SDimitry Andric if (State.Line->Type == LT_ObjCMethodDecl)
11580b57cec5SDimitry Andric State.Stack.back().BreakBeforeParameter = true;
11590b57cec5SDimitry Andric
11600b57cec5SDimitry Andric // Find best solution in solution space.
11610b57cec5SDimitry Andric return analyzeSolutionSpace(State, DryRun);
11620b57cec5SDimitry Andric }
11630b57cec5SDimitry Andric
11640b57cec5SDimitry Andric private:
11650b57cec5SDimitry Andric struct CompareLineStatePointers {
operator ()clang::format::__anon1029540c0111::OptimizingLineFormatter::CompareLineStatePointers11660b57cec5SDimitry Andric bool operator()(LineState *obj1, LineState *obj2) const {
11670b57cec5SDimitry Andric return *obj1 < *obj2;
11680b57cec5SDimitry Andric }
11690b57cec5SDimitry Andric };
11700b57cec5SDimitry Andric
11710b57cec5SDimitry Andric /// A pair of <penalty, count> that is used to prioritize the BFS on.
11720b57cec5SDimitry Andric ///
11730b57cec5SDimitry Andric /// In case of equal penalties, we want to prefer states that were inserted
11740b57cec5SDimitry Andric /// first. During state generation we make sure that we insert states first
11750b57cec5SDimitry Andric /// that break the line as late as possible.
11760b57cec5SDimitry Andric typedef std::pair<unsigned, unsigned> OrderedPenalty;
11770b57cec5SDimitry Andric
11780b57cec5SDimitry Andric /// An edge in the solution space from \c Previous->State to \c State,
11790b57cec5SDimitry Andric /// inserting a newline dependent on the \c NewLine.
11800b57cec5SDimitry Andric struct StateNode {
StateNodeclang::format::__anon1029540c0111::OptimizingLineFormatter::StateNode11810b57cec5SDimitry Andric StateNode(const LineState &State, bool NewLine, StateNode *Previous)
11820b57cec5SDimitry Andric : State(State), NewLine(NewLine), Previous(Previous) {}
11830b57cec5SDimitry Andric LineState State;
11840b57cec5SDimitry Andric bool NewLine;
11850b57cec5SDimitry Andric StateNode *Previous;
11860b57cec5SDimitry Andric };
11870b57cec5SDimitry Andric
11880b57cec5SDimitry Andric /// An item in the prioritized BFS search queue. The \c StateNode's
11890b57cec5SDimitry Andric /// \c State has the given \c OrderedPenalty.
11900b57cec5SDimitry Andric typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
11910b57cec5SDimitry Andric
11920b57cec5SDimitry Andric /// The BFS queue type.
1193753f127fSDimitry Andric typedef std::priority_queue<QueueItem, SmallVector<QueueItem>,
11940b57cec5SDimitry Andric std::greater<QueueItem>>
11950b57cec5SDimitry Andric QueueType;
11960b57cec5SDimitry Andric
11970b57cec5SDimitry Andric /// Analyze the entire solution space starting from \p InitialState.
11980b57cec5SDimitry Andric ///
11990b57cec5SDimitry Andric /// This implements a variant of Dijkstra's algorithm on the graph that spans
12000b57cec5SDimitry Andric /// the solution space (\c LineStates are the nodes). The algorithm tries to
12010b57cec5SDimitry Andric /// find the shortest path (the one with lowest penalty) from \p InitialState
12020b57cec5SDimitry Andric /// to a state where all tokens are placed. Returns the penalty.
12030b57cec5SDimitry Andric ///
12040b57cec5SDimitry Andric /// If \p DryRun is \c false, directly applies the changes.
analyzeSolutionSpace(LineState & InitialState,bool DryRun)12050b57cec5SDimitry Andric unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun) {
12060b57cec5SDimitry Andric std::set<LineState *, CompareLineStatePointers> Seen;
12070b57cec5SDimitry Andric
12080b57cec5SDimitry Andric // Increasing count of \c StateNode items we have created. This is used to
12090b57cec5SDimitry Andric // create a deterministic order independent of the container.
12100b57cec5SDimitry Andric unsigned Count = 0;
12110b57cec5SDimitry Andric QueueType Queue;
12120b57cec5SDimitry Andric
12130b57cec5SDimitry Andric // Insert start element into queue.
12140eae32dcSDimitry Andric StateNode *RootNode =
12150b57cec5SDimitry Andric new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
12160eae32dcSDimitry Andric Queue.push(QueueItem(OrderedPenalty(0, Count), RootNode));
12170b57cec5SDimitry Andric ++Count;
12180b57cec5SDimitry Andric
12190b57cec5SDimitry Andric unsigned Penalty = 0;
12200b57cec5SDimitry Andric
12210b57cec5SDimitry Andric // While not empty, take first element and follow edges.
12220b57cec5SDimitry Andric while (!Queue.empty()) {
122381ad6265SDimitry Andric // Quit if we still haven't found a solution by now.
122481ad6265SDimitry Andric if (Count > 25000000)
122581ad6265SDimitry Andric return 0;
122681ad6265SDimitry Andric
12270b57cec5SDimitry Andric Penalty = Queue.top().first.first;
12280b57cec5SDimitry Andric StateNode *Node = Queue.top().second;
12290b57cec5SDimitry Andric if (!Node->State.NextToken) {
12300b57cec5SDimitry Andric LLVM_DEBUG(llvm::dbgs()
12310b57cec5SDimitry Andric << "\n---\nPenalty for line: " << Penalty << "\n");
12320b57cec5SDimitry Andric break;
12330b57cec5SDimitry Andric }
12340b57cec5SDimitry Andric Queue.pop();
12350b57cec5SDimitry Andric
12360b57cec5SDimitry Andric // Cut off the analysis of certain solutions if the analysis gets too
12370b57cec5SDimitry Andric // complex. See description of IgnoreStackForComparison.
12380b57cec5SDimitry Andric if (Count > 50000)
12390b57cec5SDimitry Andric Node->State.IgnoreStackForComparison = true;
12400b57cec5SDimitry Andric
124181ad6265SDimitry Andric if (!Seen.insert(&Node->State).second) {
12420b57cec5SDimitry Andric // State already examined with lower penalty.
12430b57cec5SDimitry Andric continue;
124481ad6265SDimitry Andric }
12450b57cec5SDimitry Andric
1246e8d8bef9SDimitry Andric FormatDecision LastFormat = Node->State.NextToken->getDecision();
12470b57cec5SDimitry Andric if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
124804eeddc0SDimitry Andric addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
12490b57cec5SDimitry Andric if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
125004eeddc0SDimitry Andric addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
12510b57cec5SDimitry Andric }
12520b57cec5SDimitry Andric
12530b57cec5SDimitry Andric if (Queue.empty()) {
12540b57cec5SDimitry Andric // We were unable to find a solution, do nothing.
12550b57cec5SDimitry Andric // FIXME: Add diagnostic?
12560b57cec5SDimitry Andric LLVM_DEBUG(llvm::dbgs() << "Could not find a solution.\n");
12570b57cec5SDimitry Andric return 0;
12580b57cec5SDimitry Andric }
12590b57cec5SDimitry Andric
12600b57cec5SDimitry Andric // Reconstruct the solution.
12610b57cec5SDimitry Andric if (!DryRun)
12620b57cec5SDimitry Andric reconstructPath(InitialState, Queue.top().second);
12630b57cec5SDimitry Andric
12640b57cec5SDimitry Andric LLVM_DEBUG(llvm::dbgs()
12650b57cec5SDimitry Andric << "Total number of analyzed states: " << Count << "\n");
12660b57cec5SDimitry Andric LLVM_DEBUG(llvm::dbgs() << "---\n");
12670b57cec5SDimitry Andric
12680b57cec5SDimitry Andric return Penalty;
12690b57cec5SDimitry Andric }
12700b57cec5SDimitry Andric
12710b57cec5SDimitry Andric /// Add the following state to the analysis queue \c Queue.
12720b57cec5SDimitry Andric ///
12730b57cec5SDimitry Andric /// Assume the current state is \p PreviousNode and has been reached with a
12740b57cec5SDimitry Andric /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
addNextStateToQueue(unsigned Penalty,StateNode * PreviousNode,bool NewLine,unsigned * Count,QueueType * Queue)12750b57cec5SDimitry Andric void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
127604eeddc0SDimitry Andric bool NewLine, unsigned *Count, QueueType *Queue) {
12770b57cec5SDimitry Andric if (NewLine && !Indenter->canBreak(PreviousNode->State))
12780b57cec5SDimitry Andric return;
12790b57cec5SDimitry Andric if (!NewLine && Indenter->mustBreak(PreviousNode->State))
12800b57cec5SDimitry Andric return;
12810b57cec5SDimitry Andric
12820b57cec5SDimitry Andric StateNode *Node = new (Allocator.Allocate())
12830b57cec5SDimitry Andric StateNode(PreviousNode->State, NewLine, PreviousNode);
12840b57cec5SDimitry Andric if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
12850b57cec5SDimitry Andric return;
12860b57cec5SDimitry Andric
12870b57cec5SDimitry Andric Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
12880b57cec5SDimitry Andric
128904eeddc0SDimitry Andric Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
129004eeddc0SDimitry Andric ++(*Count);
12910b57cec5SDimitry Andric }
12920b57cec5SDimitry Andric
12930b57cec5SDimitry Andric /// Applies the best formatting by reconstructing the path in the
12940b57cec5SDimitry Andric /// solution space that leads to \c Best.
reconstructPath(LineState & State,StateNode * Best)12950b57cec5SDimitry Andric void reconstructPath(LineState &State, StateNode *Best) {
129604eeddc0SDimitry Andric llvm::SmallVector<StateNode *> Path;
12970b57cec5SDimitry Andric // We do not need a break before the initial token.
12980b57cec5SDimitry Andric while (Best->Previous) {
129904eeddc0SDimitry Andric Path.push_back(Best);
13000b57cec5SDimitry Andric Best = Best->Previous;
13010b57cec5SDimitry Andric }
130204eeddc0SDimitry Andric for (const auto &Node : llvm::reverse(Path)) {
13030b57cec5SDimitry Andric unsigned Penalty = 0;
130404eeddc0SDimitry Andric formatChildren(State, Node->NewLine, /*DryRun=*/false, Penalty);
130504eeddc0SDimitry Andric Penalty += Indenter->addTokenToState(State, Node->NewLine, false);
13060b57cec5SDimitry Andric
13070b57cec5SDimitry Andric LLVM_DEBUG({
130804eeddc0SDimitry Andric printLineState(Node->Previous->State);
130904eeddc0SDimitry Andric if (Node->NewLine) {
13100b57cec5SDimitry Andric llvm::dbgs() << "Penalty for placing "
131104eeddc0SDimitry Andric << Node->Previous->State.NextToken->Tok.getName()
13120b57cec5SDimitry Andric << " on a new line: " << Penalty << "\n";
13130b57cec5SDimitry Andric }
13140b57cec5SDimitry Andric });
13150b57cec5SDimitry Andric }
13160b57cec5SDimitry Andric }
13170b57cec5SDimitry Andric
13180b57cec5SDimitry Andric llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
13190b57cec5SDimitry Andric };
13200b57cec5SDimitry Andric
13210b57cec5SDimitry Andric } // anonymous namespace
13220b57cec5SDimitry Andric
format(const SmallVectorImpl<AnnotatedLine * > & Lines,bool DryRun,int AdditionalIndent,bool FixBadIndentation,unsigned FirstStartColumn,unsigned NextStartColumn,unsigned LastStartColumn)13230b57cec5SDimitry Andric unsigned UnwrappedLineFormatter::format(
13240b57cec5SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
13250b57cec5SDimitry Andric int AdditionalIndent, bool FixBadIndentation, unsigned FirstStartColumn,
13260b57cec5SDimitry Andric unsigned NextStartColumn, unsigned LastStartColumn) {
13270b57cec5SDimitry Andric LineJoiner Joiner(Style, Keywords, Lines);
13280b57cec5SDimitry Andric
13290b57cec5SDimitry Andric // Try to look up already computed penalty in DryRun-mode.
13300b57cec5SDimitry Andric std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
13310b57cec5SDimitry Andric &Lines, AdditionalIndent);
13320b57cec5SDimitry Andric auto CacheIt = PenaltyCache.find(CacheKey);
13330b57cec5SDimitry Andric if (DryRun && CacheIt != PenaltyCache.end())
13340b57cec5SDimitry Andric return CacheIt->second;
13350b57cec5SDimitry Andric
13360b57cec5SDimitry Andric assert(!Lines.empty());
13370b57cec5SDimitry Andric unsigned Penalty = 0;
13380b57cec5SDimitry Andric LevelIndentTracker IndentTracker(Style, Keywords, Lines[0]->Level,
13390b57cec5SDimitry Andric AdditionalIndent);
1340fe6060f1SDimitry Andric const AnnotatedLine *PrevPrevLine = nullptr;
13410b57cec5SDimitry Andric const AnnotatedLine *PreviousLine = nullptr;
13420b57cec5SDimitry Andric const AnnotatedLine *NextLine = nullptr;
13430b57cec5SDimitry Andric
13440b57cec5SDimitry Andric // The minimum level of consecutive lines that have been formatted.
13450b57cec5SDimitry Andric unsigned RangeMinLevel = UINT_MAX;
13460b57cec5SDimitry Andric
13470b57cec5SDimitry Andric bool FirstLine = true;
13480b57cec5SDimitry Andric for (const AnnotatedLine *Line =
13490b57cec5SDimitry Andric Joiner.getNextMergedLine(DryRun, IndentTracker);
135004eeddc0SDimitry Andric Line; PrevPrevLine = PreviousLine, PreviousLine = Line, Line = NextLine,
135104eeddc0SDimitry Andric FirstLine = false) {
135204eeddc0SDimitry Andric assert(Line->First);
13530b57cec5SDimitry Andric const AnnotatedLine &TheLine = *Line;
13540b57cec5SDimitry Andric unsigned Indent = IndentTracker.getIndent();
13550b57cec5SDimitry Andric
13560b57cec5SDimitry Andric // We continue formatting unchanged lines to adjust their indent, e.g. if a
13570b57cec5SDimitry Andric // scope was added. However, we need to carefully stop doing this when we
1358bdd1243dSDimitry Andric // exit the scope of affected lines to prevent indenting the entire
13590b57cec5SDimitry Andric // remaining file if it currently missing a closing brace.
13600b57cec5SDimitry Andric bool PreviousRBrace =
13610b57cec5SDimitry Andric PreviousLine && PreviousLine->startsWith(tok::r_brace);
13620b57cec5SDimitry Andric bool ContinueFormatting =
13630b57cec5SDimitry Andric TheLine.Level > RangeMinLevel ||
13640b57cec5SDimitry Andric (TheLine.Level == RangeMinLevel && !PreviousRBrace &&
13650b57cec5SDimitry Andric !TheLine.startsWith(tok::r_brace));
13660b57cec5SDimitry Andric
13670b57cec5SDimitry Andric bool FixIndentation = (FixBadIndentation || ContinueFormatting) &&
13680b57cec5SDimitry Andric Indent != TheLine.First->OriginalColumn;
13690b57cec5SDimitry Andric bool ShouldFormat = TheLine.Affected || FixIndentation;
13700b57cec5SDimitry Andric // We cannot format this line; if the reason is that the line had a
13710b57cec5SDimitry Andric // parsing error, remember that.
13720b57cec5SDimitry Andric if (ShouldFormat && TheLine.Type == LT_Invalid && Status) {
13730b57cec5SDimitry Andric Status->FormatComplete = false;
13740b57cec5SDimitry Andric Status->Line =
13750b57cec5SDimitry Andric SourceMgr.getSpellingLineNumber(TheLine.First->Tok.getLocation());
13760b57cec5SDimitry Andric }
13770b57cec5SDimitry Andric
13780b57cec5SDimitry Andric if (ShouldFormat && TheLine.Type != LT_Invalid) {
13790b57cec5SDimitry Andric if (!DryRun) {
138004eeddc0SDimitry Andric bool LastLine = TheLine.First->is(tok::eof);
1381fe6060f1SDimitry Andric formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines, Indent,
13820b57cec5SDimitry Andric LastLine ? LastStartColumn : NextStartColumn + Indent);
13830b57cec5SDimitry Andric }
13840b57cec5SDimitry Andric
13850b57cec5SDimitry Andric NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
13860b57cec5SDimitry Andric unsigned ColumnLimit = getColumnLimit(TheLine.InPPDirective, NextLine);
13870b57cec5SDimitry Andric bool FitsIntoOneLine =
138806c3fb27SDimitry Andric !TheLine.ContainsMacroCall &&
138906c3fb27SDimitry Andric (TheLine.Last->TotalLength + Indent <= ColumnLimit ||
13900b57cec5SDimitry Andric (TheLine.Type == LT_ImportStatement &&
13910eae32dcSDimitry Andric (!Style.isJavaScript() || !Style.JavaScriptWrapImports)) ||
13920b57cec5SDimitry Andric (Style.isCSharp() &&
139306c3fb27SDimitry Andric TheLine.InPPDirective)); // don't split #regions in C#
139481ad6265SDimitry Andric if (Style.ColumnLimit == 0) {
13950b57cec5SDimitry Andric NoColumnLimitLineFormatter(Indenter, Whitespaces, Style, this)
13960b57cec5SDimitry Andric .formatLine(TheLine, NextStartColumn + Indent,
13970b57cec5SDimitry Andric FirstLine ? FirstStartColumn : 0, DryRun);
139881ad6265SDimitry Andric } else if (FitsIntoOneLine) {
13990b57cec5SDimitry Andric Penalty += NoLineBreakFormatter(Indenter, Whitespaces, Style, this)
14000b57cec5SDimitry Andric .formatLine(TheLine, NextStartColumn + Indent,
14010b57cec5SDimitry Andric FirstLine ? FirstStartColumn : 0, DryRun);
140281ad6265SDimitry Andric } else {
14030b57cec5SDimitry Andric Penalty += OptimizingLineFormatter(Indenter, Whitespaces, Style, this)
14040b57cec5SDimitry Andric .formatLine(TheLine, NextStartColumn + Indent,
14050b57cec5SDimitry Andric FirstLine ? FirstStartColumn : 0, DryRun);
140681ad6265SDimitry Andric }
14070b57cec5SDimitry Andric RangeMinLevel = std::min(RangeMinLevel, TheLine.Level);
14080b57cec5SDimitry Andric } else {
14090b57cec5SDimitry Andric // If no token in the current line is affected, we still need to format
14100b57cec5SDimitry Andric // affected children.
141181ad6265SDimitry Andric if (TheLine.ChildrenAffected) {
14120b57cec5SDimitry Andric for (const FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next)
14130b57cec5SDimitry Andric if (!Tok->Children.empty())
14140b57cec5SDimitry Andric format(Tok->Children, DryRun);
141581ad6265SDimitry Andric }
14160b57cec5SDimitry Andric
14170b57cec5SDimitry Andric // Adapt following lines on the current indent level to the same level
14180b57cec5SDimitry Andric // unless the current \c AnnotatedLine is not at the beginning of a line.
14190b57cec5SDimitry Andric bool StartsNewLine =
14200b57cec5SDimitry Andric TheLine.First->NewlinesBefore > 0 || TheLine.First->IsFirst;
14210b57cec5SDimitry Andric if (StartsNewLine)
14220b57cec5SDimitry Andric IndentTracker.adjustToUnmodifiedLine(TheLine);
14230b57cec5SDimitry Andric if (!DryRun) {
14240b57cec5SDimitry Andric bool ReformatLeadingWhitespace =
14250b57cec5SDimitry Andric StartsNewLine && ((PreviousLine && PreviousLine->Affected) ||
14260b57cec5SDimitry Andric TheLine.LeadingEmptyLinesAffected);
14270b57cec5SDimitry Andric // Format the first token.
142881ad6265SDimitry Andric if (ReformatLeadingWhitespace) {
1429fe6060f1SDimitry Andric formatFirstToken(TheLine, PreviousLine, PrevPrevLine, Lines,
14300b57cec5SDimitry Andric TheLine.First->OriginalColumn,
14310b57cec5SDimitry Andric TheLine.First->OriginalColumn);
143281ad6265SDimitry Andric } else {
14330b57cec5SDimitry Andric Whitespaces->addUntouchableToken(*TheLine.First,
14340b57cec5SDimitry Andric TheLine.InPPDirective);
143581ad6265SDimitry Andric }
14360b57cec5SDimitry Andric
14370b57cec5SDimitry Andric // Notify the WhitespaceManager about the unchanged whitespace.
14380b57cec5SDimitry Andric for (FormatToken *Tok = TheLine.First->Next; Tok; Tok = Tok->Next)
14390b57cec5SDimitry Andric Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
14400b57cec5SDimitry Andric }
14410b57cec5SDimitry Andric NextLine = Joiner.getNextMergedLine(DryRun, IndentTracker);
14420b57cec5SDimitry Andric RangeMinLevel = UINT_MAX;
14430b57cec5SDimitry Andric }
14445f757f3fSDimitry Andric if (!DryRun)
14455f757f3fSDimitry Andric markFinalized(TheLine.First);
14460b57cec5SDimitry Andric }
14470b57cec5SDimitry Andric PenaltyCache[CacheKey] = Penalty;
14480b57cec5SDimitry Andric return Penalty;
14490b57cec5SDimitry Andric }
14500b57cec5SDimitry Andric
computeNewlines(const AnnotatedLine & Line,const AnnotatedLine * PreviousLine,const AnnotatedLine * PrevPrevLine,const SmallVectorImpl<AnnotatedLine * > & Lines,const FormatStyle & Style)145106c3fb27SDimitry Andric static auto computeNewlines(const AnnotatedLine &Line,
145206c3fb27SDimitry Andric const AnnotatedLine *PreviousLine,
1453fe6060f1SDimitry Andric const AnnotatedLine *PrevPrevLine,
145406c3fb27SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &Lines,
145506c3fb27SDimitry Andric const FormatStyle &Style) {
145606c3fb27SDimitry Andric const auto &RootToken = *Line.First;
145706c3fb27SDimitry Andric auto Newlines =
14580b57cec5SDimitry Andric std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
14590b57cec5SDimitry Andric // Remove empty lines before "}" where applicable.
14600b57cec5SDimitry Andric if (RootToken.is(tok::r_brace) &&
14610b57cec5SDimitry Andric (!RootToken.Next ||
14620b57cec5SDimitry Andric (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)) &&
14630b57cec5SDimitry Andric // Do not remove empty lines before namespace closing "}".
146481ad6265SDimitry Andric !getNamespaceToken(&Line, Lines)) {
14650b57cec5SDimitry Andric Newlines = std::min(Newlines, 1u);
146681ad6265SDimitry Andric }
14670b57cec5SDimitry Andric // Remove empty lines at the start of nested blocks (lambdas/arrow functions)
146806c3fb27SDimitry Andric if (!PreviousLine && Line.Level > 0)
14690b57cec5SDimitry Andric Newlines = std::min(Newlines, 1u);
14700b57cec5SDimitry Andric if (Newlines == 0 && !RootToken.IsFirst)
14710b57cec5SDimitry Andric Newlines = 1;
14720b57cec5SDimitry Andric if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
14730b57cec5SDimitry Andric Newlines = 0;
14740b57cec5SDimitry Andric
14750b57cec5SDimitry Andric // Remove empty lines after "{".
14760b57cec5SDimitry Andric if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
14770b57cec5SDimitry Andric PreviousLine->Last->is(tok::l_brace) &&
14780b57cec5SDimitry Andric !PreviousLine->startsWithNamespace() &&
1479fe6060f1SDimitry Andric !(PrevPrevLine && PrevPrevLine->startsWithNamespace() &&
1480fe6060f1SDimitry Andric PreviousLine->startsWith(tok::l_brace)) &&
148181ad6265SDimitry Andric !startsExternCBlock(*PreviousLine)) {
14820b57cec5SDimitry Andric Newlines = 1;
148381ad6265SDimitry Andric }
14840b57cec5SDimitry Andric
1485e8d8bef9SDimitry Andric // Insert or remove empty line before access specifiers.
1486e8d8bef9SDimitry Andric if (PreviousLine && RootToken.isAccessSpecifier()) {
1487e8d8bef9SDimitry Andric switch (Style.EmptyLineBeforeAccessModifier) {
1488e8d8bef9SDimitry Andric case FormatStyle::ELBAMS_Never:
1489fe6060f1SDimitry Andric if (Newlines > 1)
1490e8d8bef9SDimitry Andric Newlines = 1;
1491e8d8bef9SDimitry Andric break;
1492e8d8bef9SDimitry Andric case FormatStyle::ELBAMS_Leave:
1493e8d8bef9SDimitry Andric Newlines = std::max(RootToken.NewlinesBefore, 1u);
1494e8d8bef9SDimitry Andric break;
1495e8d8bef9SDimitry Andric case FormatStyle::ELBAMS_LogicalBlock:
1496fe6060f1SDimitry Andric if (PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) && Newlines <= 1)
1497e8d8bef9SDimitry Andric Newlines = 2;
1498fe6060f1SDimitry Andric if (PreviousLine->First->isAccessSpecifier())
1499fe6060f1SDimitry Andric Newlines = 1; // Previous is an access modifier remove all new lines.
1500e8d8bef9SDimitry Andric break;
1501e8d8bef9SDimitry Andric case FormatStyle::ELBAMS_Always: {
1502e8d8bef9SDimitry Andric const FormatToken *previousToken;
1503e8d8bef9SDimitry Andric if (PreviousLine->Last->is(tok::comment))
1504e8d8bef9SDimitry Andric previousToken = PreviousLine->Last->getPreviousNonComment();
1505e8d8bef9SDimitry Andric else
1506e8d8bef9SDimitry Andric previousToken = PreviousLine->Last;
15075f757f3fSDimitry Andric if ((!previousToken || previousToken->isNot(tok::l_brace)) &&
15085f757f3fSDimitry Andric Newlines <= 1) {
1509e8d8bef9SDimitry Andric Newlines = 2;
15105f757f3fSDimitry Andric }
1511e8d8bef9SDimitry Andric } break;
1512e8d8bef9SDimitry Andric }
1513e8d8bef9SDimitry Andric }
15140b57cec5SDimitry Andric
1515fe6060f1SDimitry Andric // Insert or remove empty line after access specifiers.
15160b57cec5SDimitry Andric if (PreviousLine && PreviousLine->First->isAccessSpecifier() &&
1517fe6060f1SDimitry Andric (!PreviousLine->InPPDirective || !RootToken.HasUnescapedNewline)) {
1518fe6060f1SDimitry Andric // EmptyLineBeforeAccessModifier is handling the case when two access
1519fe6060f1SDimitry Andric // modifiers follow each other.
1520fe6060f1SDimitry Andric if (!RootToken.isAccessSpecifier()) {
1521fe6060f1SDimitry Andric switch (Style.EmptyLineAfterAccessModifier) {
1522fe6060f1SDimitry Andric case FormatStyle::ELAAMS_Never:
1523fe6060f1SDimitry Andric Newlines = 1;
1524fe6060f1SDimitry Andric break;
1525fe6060f1SDimitry Andric case FormatStyle::ELAAMS_Leave:
1526fe6060f1SDimitry Andric Newlines = std::max(Newlines, 1u);
1527fe6060f1SDimitry Andric break;
1528fe6060f1SDimitry Andric case FormatStyle::ELAAMS_Always:
1529fe6060f1SDimitry Andric if (RootToken.is(tok::r_brace)) // Do not add at end of class.
1530fe6060f1SDimitry Andric Newlines = 1u;
1531fe6060f1SDimitry Andric else
1532fe6060f1SDimitry Andric Newlines = std::max(Newlines, 2u);
1533fe6060f1SDimitry Andric break;
1534fe6060f1SDimitry Andric }
1535fe6060f1SDimitry Andric }
1536fe6060f1SDimitry Andric }
15370b57cec5SDimitry Andric
153806c3fb27SDimitry Andric return Newlines;
153906c3fb27SDimitry Andric }
154006c3fb27SDimitry Andric
formatFirstToken(const AnnotatedLine & Line,const AnnotatedLine * PreviousLine,const AnnotatedLine * PrevPrevLine,const SmallVectorImpl<AnnotatedLine * > & Lines,unsigned Indent,unsigned NewlineIndent)154106c3fb27SDimitry Andric void UnwrappedLineFormatter::formatFirstToken(
154206c3fb27SDimitry Andric const AnnotatedLine &Line, const AnnotatedLine *PreviousLine,
154306c3fb27SDimitry Andric const AnnotatedLine *PrevPrevLine,
154406c3fb27SDimitry Andric const SmallVectorImpl<AnnotatedLine *> &Lines, unsigned Indent,
154506c3fb27SDimitry Andric unsigned NewlineIndent) {
154606c3fb27SDimitry Andric FormatToken &RootToken = *Line.First;
154706c3fb27SDimitry Andric if (RootToken.is(tok::eof)) {
154806c3fb27SDimitry Andric unsigned Newlines =
154906c3fb27SDimitry Andric std::min(RootToken.NewlinesBefore,
155006c3fb27SDimitry Andric Style.KeepEmptyLinesAtEOF ? Style.MaxEmptyLinesToKeep + 1 : 1);
155106c3fb27SDimitry Andric unsigned TokenIndent = Newlines ? NewlineIndent : 0;
155206c3fb27SDimitry Andric Whitespaces->replaceWhitespace(RootToken, Newlines, TokenIndent,
155306c3fb27SDimitry Andric TokenIndent);
155406c3fb27SDimitry Andric return;
155506c3fb27SDimitry Andric }
155606c3fb27SDimitry Andric
155706c3fb27SDimitry Andric if (RootToken.Newlines < 0) {
155806c3fb27SDimitry Andric RootToken.Newlines =
155906c3fb27SDimitry Andric computeNewlines(Line, PreviousLine, PrevPrevLine, Lines, Style);
156006c3fb27SDimitry Andric assert(RootToken.Newlines >= 0);
156106c3fb27SDimitry Andric }
156206c3fb27SDimitry Andric
156306c3fb27SDimitry Andric if (RootToken.Newlines > 0)
15640b57cec5SDimitry Andric Indent = NewlineIndent;
15650b57cec5SDimitry Andric
156681ad6265SDimitry Andric // Preprocessor directives get indented before the hash only if specified. In
156781ad6265SDimitry Andric // Javascript import statements are indented like normal statements.
156881ad6265SDimitry Andric if (!Style.isJavaScript() &&
156981ad6265SDimitry Andric Style.IndentPPDirectives != FormatStyle::PPDIS_BeforeHash &&
15700b57cec5SDimitry Andric (Line.Type == LT_PreprocessorDirective ||
157181ad6265SDimitry Andric Line.Type == LT_ImportStatement)) {
15720b57cec5SDimitry Andric Indent = 0;
157381ad6265SDimitry Andric }
15740b57cec5SDimitry Andric
157506c3fb27SDimitry Andric Whitespaces->replaceWhitespace(RootToken, RootToken.Newlines, Indent, Indent,
15765ffd83dbSDimitry Andric /*IsAligned=*/false,
15770b57cec5SDimitry Andric Line.InPPDirective &&
15780b57cec5SDimitry Andric !RootToken.HasUnescapedNewline);
15790b57cec5SDimitry Andric }
15800b57cec5SDimitry Andric
15810b57cec5SDimitry Andric unsigned
getColumnLimit(bool InPPDirective,const AnnotatedLine * NextLine) const15820b57cec5SDimitry Andric UnwrappedLineFormatter::getColumnLimit(bool InPPDirective,
15830b57cec5SDimitry Andric const AnnotatedLine *NextLine) const {
15840b57cec5SDimitry Andric // In preprocessor directives reserve two chars for trailing " \" if the
15850b57cec5SDimitry Andric // next line continues the preprocessor directive.
15860b57cec5SDimitry Andric bool ContinuesPPDirective =
15870b57cec5SDimitry Andric InPPDirective &&
15880b57cec5SDimitry Andric // If there is no next line, this is likely a child line and the parent
15890b57cec5SDimitry Andric // continues the preprocessor directive.
15900b57cec5SDimitry Andric (!NextLine ||
15910b57cec5SDimitry Andric (NextLine->InPPDirective &&
15920b57cec5SDimitry Andric // If there is an unescaped newline between this line and the next, the
15930b57cec5SDimitry Andric // next line starts a new preprocessor directive.
15940b57cec5SDimitry Andric !NextLine->First->HasUnescapedNewline));
15950b57cec5SDimitry Andric return Style.ColumnLimit - (ContinuesPPDirective ? 2 : 0);
15960b57cec5SDimitry Andric }
15970b57cec5SDimitry Andric
15980b57cec5SDimitry Andric } // namespace format
15990b57cec5SDimitry Andric } // namespace clang
1600