| 1 | //===--- FormatToken.cpp - Format C++ code --------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// This file implements specific functions of \c FormatTokens and their |
| 11 | /// roles. |
| 12 | /// |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "FormatToken.h" |
| 16 | #include "ContinuationIndenter.h" |
| 17 | #include "llvm/ADT/SmallVector.h" |
| 18 | #include <climits> |
| 19 | |
| 20 | namespace clang { |
| 21 | namespace format { |
| 22 | |
| 23 | const char *getTokenTypeName(TokenType Type) { |
| 24 | static const char *const TokNames[] = { |
| 25 | #define TYPE(X) #X, |
| 26 | LIST_TOKEN_TYPES |
| 27 | #undef TYPE |
| 28 | nullptr}; |
| 29 | |
| 30 | if (Type < NUM_TOKEN_TYPES) |
| 31 | return TokNames[Type]; |
| 32 | llvm_unreachable("unknown TokenType" ); |
| 33 | return nullptr; |
| 34 | } |
| 35 | |
| 36 | static constexpr std::array<StringRef, 16> QtPropertyKeywords = { |
| 37 | "BINDABLE" , "CONSTANT" , "DESIGNABLE" , "FINAL" , "MEMBER" , "NOTIFY" , |
| 38 | "OVERRIDE" , "READ" , "REQUIRED" , "RESET" , "REVISION" , "SCRIPTABLE" , |
| 39 | "STORED" , "USER" , "VIRTUAL" , "WRITE" , |
| 40 | }; |
| 41 | |
| 42 | bool FormatToken::isQtProperty() const { |
| 43 | assert(llvm::is_sorted(QtPropertyKeywords)); |
| 44 | return llvm::binary_search(Range: QtPropertyKeywords, Value: TokenText); |
| 45 | } |
| 46 | |
| 47 | // Sorted common C++ non-keyword types. |
| 48 | static constexpr std::array<StringRef, 14> CppNonKeywordTypes = { |
| 49 | "clock_t" , "int16_t" , "int32_t" , "int64_t" , "int8_t" , |
| 50 | "intptr_t" , "ptrdiff_t" , "size_t" , "time_t" , "uint16_t" , |
| 51 | "uint32_t" , "uint64_t" , "uint8_t" , "uintptr_t" , |
| 52 | }; |
| 53 | |
| 54 | bool FormatToken::isTypeName(const LangOptions &LangOpts) const { |
| 55 | if (is(TT: TT_TypeName) || Tok.isSimpleTypeSpecifier(LangOpts)) |
| 56 | return true; |
| 57 | assert(llvm::is_sorted(CppNonKeywordTypes)); |
| 58 | return (LangOpts.CXXOperatorNames || LangOpts.C11) && is(Kind: tok::identifier) && |
| 59 | llvm::binary_search(Range: CppNonKeywordTypes, Value: TokenText); |
| 60 | } |
| 61 | |
| 62 | bool FormatToken::isTypeOrIdentifier(const LangOptions &LangOpts) const { |
| 63 | return isTypeName(LangOpts) || isOneOf(K1: tok::kw_auto, K2: tok::identifier); |
| 64 | } |
| 65 | |
| 66 | bool FormatToken::isBlockIndentedInitRBrace(const FormatStyle &Style) const { |
| 67 | assert(is(tok::r_brace)); |
| 68 | assert(MatchingParen); |
| 69 | assert(MatchingParen->is(tok::l_brace)); |
| 70 | if (Style.Cpp11BracedListStyle == FormatStyle::BLS_Block || |
| 71 | !Style.BreakBeforeCloseBracketBracedList) { |
| 72 | return false; |
| 73 | } |
| 74 | const auto *LBrace = MatchingParen; |
| 75 | if (LBrace->is(BBK: BK_BracedInit)) |
| 76 | return true; |
| 77 | if (LBrace->Previous && LBrace->Previous->is(Kind: tok::equal)) |
| 78 | return true; |
| 79 | return false; |
| 80 | } |
| 81 | |
| 82 | bool FormatToken::mustBreakAfterAttributes(const FormatStyle &Style) const { |
| 83 | switch (Style.BreakAfterAttributes) { |
| 84 | case FormatStyle::ABS_Always: |
| 85 | return true; |
| 86 | case FormatStyle::ABS_Never: |
| 87 | return false; |
| 88 | default: // ABS_Leave and ABS_LeaveAll |
| 89 | return NewlinesBefore > 0; |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | bool FormatToken::opensBlockOrBlockTypeList(const FormatStyle &Style) const { |
| 94 | // C# Does not indent object initialisers as continuations. |
| 95 | if (is(Kind: tok::l_brace) && getBlockKind() == BK_BracedInit && Style.isCSharp()) |
| 96 | return true; |
| 97 | if (is(TT: TT_TemplateString) && opensScope()) |
| 98 | return true; |
| 99 | return is(TT: TT_ArrayInitializerLSquare) || is(TT: TT_ProtoExtensionLSquare) || |
| 100 | (is(Kind: tok::l_brace) && |
| 101 | (getBlockKind() == BK_Block || is(TT: TT_DictLiteral) || |
| 102 | (Style.Cpp11BracedListStyle == FormatStyle::BLS_Block && |
| 103 | NestingLevel == 0))) || |
| 104 | (is(Kind: tok::less) && Style.isProto()); |
| 105 | } |
| 106 | |
| 107 | TokenRole::~TokenRole() {} |
| 108 | |
| 109 | void TokenRole::precomputeFormattingInfos(const FormatToken *Token) {} |
| 110 | |
| 111 | unsigned CommaSeparatedList::formatAfterToken(LineState &State, |
| 112 | ContinuationIndenter *Indenter, |
| 113 | bool DryRun) { |
| 114 | if (!State.NextToken || !State.NextToken->Previous) |
| 115 | return 0; |
| 116 | |
| 117 | if (Formats.size() <= 1) |
| 118 | return 0; // Handled by formatFromToken (1) or avoid severe penalty (0). |
| 119 | |
| 120 | // Ensure that we start on the opening brace. |
| 121 | const FormatToken *LBrace = |
| 122 | State.NextToken->Previous->getPreviousNonComment(); |
| 123 | if (!LBrace || LBrace->isNoneOf(Ks: tok::l_brace, Ks: TT_ArrayInitializerLSquare) || |
| 124 | LBrace->is(BBK: BK_Block) || LBrace->is(TT: TT_DictLiteral) || |
| 125 | LBrace->Next->is(TT: TT_DesignatedInitializerPeriod)) { |
| 126 | return 0; |
| 127 | } |
| 128 | |
| 129 | // Calculate the number of code points we have to format this list. As the |
| 130 | // first token is already placed, we have to subtract it. |
| 131 | unsigned RemainingCodePoints = |
| 132 | Style.ColumnLimit - State.Column + State.NextToken->Previous->ColumnWidth; |
| 133 | |
| 134 | // Find the best ColumnFormat, i.e. the best number of columns to use. |
| 135 | const ColumnFormat *Format = getColumnFormat(RemainingCharacters: RemainingCodePoints); |
| 136 | |
| 137 | // If no ColumnFormat can be used, the braced list would generally be |
| 138 | // bin-packed. Add a severe penalty to this so that column layouts are |
| 139 | // preferred if possible. |
| 140 | if (!Format) |
| 141 | return 10'000; |
| 142 | |
| 143 | // Format the entire list. |
| 144 | unsigned Penalty = 0; |
| 145 | unsigned Column = 0; |
| 146 | unsigned Item = 0; |
| 147 | while (State.NextToken != LBrace->MatchingParen) { |
| 148 | bool NewLine = false; |
| 149 | unsigned = 0; |
| 150 | |
| 151 | // If the previous token was one of our commas, we are now on the next item. |
| 152 | if (Item < Commas.size() && State.NextToken->Previous == Commas[Item]) { |
| 153 | if (!State.NextToken->isTrailingComment()) { |
| 154 | ExtraSpaces += Format->ColumnSizes[Column] - ItemLengths[Item]; |
| 155 | ++Column; |
| 156 | } |
| 157 | ++Item; |
| 158 | } |
| 159 | |
| 160 | if (Column == Format->Columns || State.NextToken->MustBreakBefore) { |
| 161 | Column = 0; |
| 162 | NewLine = true; |
| 163 | } |
| 164 | |
| 165 | // Place token using the continuation indenter and store the penalty. |
| 166 | Penalty += Indenter->addTokenToState(State, Newline: NewLine, DryRun, ExtraSpaces); |
| 167 | } |
| 168 | return Penalty; |
| 169 | } |
| 170 | |
| 171 | unsigned CommaSeparatedList::formatFromToken(LineState &State, |
| 172 | ContinuationIndenter *Indenter, |
| 173 | bool DryRun) { |
| 174 | // Formatting with 1 Column isn't really a column layout, so we don't need the |
| 175 | // special logic here. We can just avoid bin packing any of the parameters. |
| 176 | if (Formats.size() == 1 || HasNestedBracedList) |
| 177 | State.Stack.back().AvoidBinPacking = true; |
| 178 | return 0; |
| 179 | } |
| 180 | |
| 181 | // Returns the lengths in code points between Begin and End (both included), |
| 182 | // assuming that the entire sequence is put on a single line. |
| 183 | static unsigned CodePointsBetween(const FormatToken *Begin, |
| 184 | const FormatToken *End) { |
| 185 | assert(End->TotalLength >= Begin->TotalLength); |
| 186 | return End->TotalLength - Begin->TotalLength + Begin->ColumnWidth; |
| 187 | } |
| 188 | |
| 189 | void CommaSeparatedList::precomputeFormattingInfos(const FormatToken *Token) { |
| 190 | // FIXME: At some point we might want to do this for other lists, too. |
| 191 | if (!Token->MatchingParen || |
| 192 | Token->isNoneOf(Ks: tok::l_brace, Ks: TT_ArrayInitializerLSquare)) { |
| 193 | return; |
| 194 | } |
| 195 | |
| 196 | // In C++11 braced list style, we should not format in columns unless they |
| 197 | // have many items (20 or more) or we allow bin-packing of function call |
| 198 | // arguments. |
| 199 | if (Style.Cpp11BracedListStyle != FormatStyle::BLS_Block && |
| 200 | Style.PackArguments.BinPack == FormatStyle::BPAS_OnePerLine && |
| 201 | (Commas.size() < 19 || !Style.BinPackLongBracedList)) { |
| 202 | return; |
| 203 | } |
| 204 | |
| 205 | // Limit column layout for JavaScript array initializers to 20 or more items |
| 206 | // for now to introduce it carefully. We can become more aggressive if this |
| 207 | // necessary. |
| 208 | if (Token->is(TT: TT_ArrayInitializerLSquare) && Commas.size() < 19) |
| 209 | return; |
| 210 | |
| 211 | // Column format doesn't really make sense if we don't align after brackets. |
| 212 | if (!Style.AlignAfterOpenBracket) |
| 213 | return; |
| 214 | |
| 215 | FormatToken *ItemBegin = Token->Next; |
| 216 | while (ItemBegin->isTrailingComment()) |
| 217 | ItemBegin = ItemBegin->Next; |
| 218 | SmallVector<bool, 8> MustBreakBeforeItem; |
| 219 | |
| 220 | // The lengths of an item if it is put at the end of the line. This includes |
| 221 | // trailing comments which are otherwise ignored for column alignment. |
| 222 | SmallVector<unsigned, 8> EndOfLineItemLength; |
| 223 | MustBreakBeforeItem.reserve(N: Commas.size() + 1); |
| 224 | EndOfLineItemLength.reserve(N: Commas.size() + 1); |
| 225 | ItemLengths.reserve(N: Commas.size() + 1); |
| 226 | |
| 227 | bool = false; |
| 228 | for (unsigned i = 0, e = Commas.size() + 1; i != e; ++i) { |
| 229 | assert(ItemBegin); |
| 230 | // Skip comments on their own line. |
| 231 | while (ItemBegin->HasUnescapedNewline && ItemBegin->isTrailingComment()) { |
| 232 | ItemBegin = ItemBegin->Next; |
| 233 | HasSeparatingComment = i > 0; |
| 234 | } |
| 235 | |
| 236 | MustBreakBeforeItem.push_back(Elt: ItemBegin->MustBreakBefore); |
| 237 | if (ItemBegin->is(Kind: tok::l_brace)) |
| 238 | HasNestedBracedList = true; |
| 239 | const FormatToken *ItemEnd = nullptr; |
| 240 | if (i == Commas.size()) { |
| 241 | ItemEnd = Token->MatchingParen; |
| 242 | const FormatToken * = ItemEnd->getPreviousNonComment(); |
| 243 | ItemLengths.push_back(Elt: CodePointsBetween(Begin: ItemBegin, End: NonCommentEnd)); |
| 244 | if (Style.Cpp11BracedListStyle != FormatStyle::BLS_Block && |
| 245 | !ItemEnd->Previous->isTrailingComment()) { |
| 246 | // In Cpp11 braced list style, the } and possibly other subsequent |
| 247 | // tokens will need to stay on a line with the last element. |
| 248 | while (ItemEnd->Next && !ItemEnd->Next->CanBreakBefore) |
| 249 | ItemEnd = ItemEnd->Next; |
| 250 | } else { |
| 251 | // In other braced lists styles, the "}" can be wrapped to the new line. |
| 252 | ItemEnd = Token->MatchingParen->Previous; |
| 253 | } |
| 254 | } else { |
| 255 | ItemEnd = Commas[i]; |
| 256 | // The comma is counted as part of the item when calculating the length. |
| 257 | ItemLengths.push_back(Elt: CodePointsBetween(Begin: ItemBegin, End: ItemEnd)); |
| 258 | |
| 259 | // Consume trailing comments so the are included in EndOfLineItemLength. |
| 260 | if (ItemEnd->Next && !ItemEnd->Next->HasUnescapedNewline && |
| 261 | ItemEnd->Next->isTrailingComment()) { |
| 262 | ItemEnd = ItemEnd->Next; |
| 263 | } |
| 264 | } |
| 265 | EndOfLineItemLength.push_back(Elt: CodePointsBetween(Begin: ItemBegin, End: ItemEnd)); |
| 266 | // If there is a trailing comma in the list, the next item will start at the |
| 267 | // closing brace. Don't create an extra item for this. |
| 268 | if (ItemEnd->getNextNonComment() == Token->MatchingParen) |
| 269 | break; |
| 270 | ItemBegin = ItemEnd->Next; |
| 271 | } |
| 272 | |
| 273 | // Don't use column layout for lists with few elements and in presence of |
| 274 | // separating comments. |
| 275 | if (Commas.size() < 5 || HasSeparatingComment) |
| 276 | return; |
| 277 | |
| 278 | if (Token->NestingLevel != 0 && Token->is(Kind: tok::l_brace) && Commas.size() < 19) |
| 279 | return; |
| 280 | |
| 281 | // We can never place more than ColumnLimit / 3 items in a row (because of the |
| 282 | // spaces and the comma). |
| 283 | unsigned MaxItems = Style.ColumnLimit / 3; |
| 284 | SmallVector<unsigned> MinSizeInColumn; |
| 285 | MinSizeInColumn.reserve(N: MaxItems); |
| 286 | for (unsigned Columns = 1; Columns <= MaxItems; ++Columns) { |
| 287 | ColumnFormat Format; |
| 288 | Format.Columns = Columns; |
| 289 | Format.ColumnSizes.resize(N: Columns); |
| 290 | MinSizeInColumn.assign(NumElts: Columns, UINT_MAX); |
| 291 | Format.LineCount = 1; |
| 292 | bool HasRowWithSufficientColumns = false; |
| 293 | unsigned Column = 0; |
| 294 | for (unsigned i = 0, e = ItemLengths.size(); i != e; ++i) { |
| 295 | assert(i < MustBreakBeforeItem.size()); |
| 296 | if (MustBreakBeforeItem[i] || Column == Columns) { |
| 297 | ++Format.LineCount; |
| 298 | Column = 0; |
| 299 | } |
| 300 | if (Column == Columns - 1) |
| 301 | HasRowWithSufficientColumns = true; |
| 302 | unsigned Length = |
| 303 | (Column == Columns - 1) ? EndOfLineItemLength[i] : ItemLengths[i]; |
| 304 | Format.ColumnSizes[Column] = std::max(a: Format.ColumnSizes[Column], b: Length); |
| 305 | MinSizeInColumn[Column] = std::min(a: MinSizeInColumn[Column], b: Length); |
| 306 | ++Column; |
| 307 | } |
| 308 | // If all rows are terminated early (e.g. by trailing comments), we don't |
| 309 | // need to look further. |
| 310 | if (!HasRowWithSufficientColumns) |
| 311 | break; |
| 312 | Format.TotalWidth = Columns - 1; // Width of the N-1 spaces. |
| 313 | |
| 314 | for (unsigned i = 0; i < Columns; ++i) |
| 315 | Format.TotalWidth += Format.ColumnSizes[i]; |
| 316 | |
| 317 | // Don't use this Format, if the difference between the longest and shortest |
| 318 | // element in a column exceeds a threshold to avoid excessive spaces. |
| 319 | if ([&] { |
| 320 | for (unsigned i = 0; i < Columns - 1; ++i) |
| 321 | if (Format.ColumnSizes[i] - MinSizeInColumn[i] > 10) |
| 322 | return true; |
| 323 | return false; |
| 324 | }()) { |
| 325 | continue; |
| 326 | } |
| 327 | |
| 328 | // Ignore layouts that are bound to violate the column limit. |
| 329 | if (Format.TotalWidth > Style.ColumnLimit && Columns > 1) |
| 330 | continue; |
| 331 | |
| 332 | Formats.push_back(Elt: Format); |
| 333 | } |
| 334 | } |
| 335 | |
| 336 | const CommaSeparatedList::ColumnFormat * |
| 337 | CommaSeparatedList::getColumnFormat(unsigned RemainingCharacters) const { |
| 338 | const ColumnFormat *BestFormat = nullptr; |
| 339 | for (const ColumnFormat &Format : llvm::reverse(C: Formats)) { |
| 340 | if (Format.TotalWidth <= RemainingCharacters || Format.Columns == 1) { |
| 341 | if (BestFormat && Format.LineCount > BestFormat->LineCount) |
| 342 | break; |
| 343 | BestFormat = &Format; |
| 344 | } |
| 345 | } |
| 346 | return BestFormat; |
| 347 | } |
| 348 | |
| 349 | bool startsNextParameter(const FormatToken &Current, const FormatStyle &Style) { |
| 350 | assert(Current.Previous); |
| 351 | const auto &Previous = *Current.Previous; |
| 352 | if (Current.is(TT: TT_CtorInitializerComma) && |
| 353 | Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeComma) { |
| 354 | return true; |
| 355 | } |
| 356 | if (Style.Language == FormatStyle::LK_Proto && Current.is(TT: TT_SelectorName)) |
| 357 | return true; |
| 358 | if (Current.is(TT: TT_QtProperty)) |
| 359 | return true; |
| 360 | if (Current.is(TT: TT_TrailingCommaVaOptRParen)) |
| 361 | return false; |
| 362 | if (Previous.is(TT: TT_TrailingCommaVaOptRParen)) |
| 363 | return !Current.closesScope() && !Current.isTrailingComment(); |
| 364 | return Previous.is(Kind: tok::comma) && !Current.isTrailingComment() && |
| 365 | ((Previous.isNot(Kind: TT_CtorInitializerComma) || |
| 366 | Style.BreakConstructorInitializers != |
| 367 | FormatStyle::BCIS_BeforeComma) && |
| 368 | (Previous.isNot(Kind: TT_InheritanceComma) || |
| 369 | Style.BreakInheritanceList != FormatStyle::BILS_BeforeComma)); |
| 370 | } |
| 371 | |
| 372 | } // namespace format |
| 373 | } // namespace clang |
| 374 | |