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 "llvm/Support/Debug.h" 19 #include <climits> 20 21 namespace clang { 22 namespace format { 23 24 const char *getTokenTypeName(TokenType Type) { 25 static const char *const TokNames[] = { 26 #define TYPE(X) #X, 27 LIST_TOKEN_TYPES 28 #undef TYPE 29 nullptr}; 30 31 if (Type < NUM_TOKEN_TYPES) 32 return TokNames[Type]; 33 llvm_unreachable("unknown TokenType"); 34 return nullptr; 35 } 36 37 // FIXME: This is copy&pasted from Sema. Put it in a common place and remove 38 // duplication. 39 bool FormatToken::isSimpleTypeSpecifier() const { 40 switch (Tok.getKind()) { 41 case tok::kw_short: 42 case tok::kw_long: 43 case tok::kw___int64: 44 case tok::kw___int128: 45 case tok::kw_signed: 46 case tok::kw_unsigned: 47 case tok::kw_void: 48 case tok::kw_char: 49 case tok::kw_int: 50 case tok::kw_half: 51 case tok::kw_float: 52 case tok::kw_double: 53 case tok::kw___bf16: 54 case tok::kw__Float16: 55 case tok::kw___float128: 56 case tok::kw___ibm128: 57 case tok::kw_wchar_t: 58 case tok::kw_bool: 59 case tok::kw___underlying_type: 60 case tok::annot_typename: 61 case tok::kw_char8_t: 62 case tok::kw_char16_t: 63 case tok::kw_char32_t: 64 case tok::kw_typeof: 65 case tok::kw_decltype: 66 case tok::kw__Atomic: 67 return true; 68 default: 69 return false; 70 } 71 } 72 73 bool FormatToken::isTypeOrIdentifier() const { 74 return isSimpleTypeSpecifier() || Tok.isOneOf(tok::kw_auto, tok::identifier); 75 } 76 77 bool FormatToken::opensBlockOrBlockTypeList(const FormatStyle &Style) const { 78 // C# Does not indent object initialisers as continuations. 79 if (is(tok::l_brace) && getBlockKind() == BK_BracedInit && Style.isCSharp()) 80 return true; 81 if (is(TT_TemplateString) && opensScope()) 82 return true; 83 return is(TT_ArrayInitializerLSquare) || is(TT_ProtoExtensionLSquare) || 84 (is(tok::l_brace) && 85 (getBlockKind() == BK_Block || is(TT_DictLiteral) || 86 (!Style.Cpp11BracedListStyle && NestingLevel == 0))) || 87 (is(tok::less) && (Style.Language == FormatStyle::LK_Proto || 88 Style.Language == FormatStyle::LK_TextProto)); 89 } 90 91 TokenRole::~TokenRole() {} 92 93 void TokenRole::precomputeFormattingInfos(const FormatToken *Token) {} 94 95 unsigned CommaSeparatedList::formatAfterToken(LineState &State, 96 ContinuationIndenter *Indenter, 97 bool DryRun) { 98 if (State.NextToken == nullptr || !State.NextToken->Previous) 99 return 0; 100 101 if (Formats.size() == 1) 102 return 0; // Handled by formatFromToken 103 104 // Ensure that we start on the opening brace. 105 const FormatToken *LBrace = 106 State.NextToken->Previous->getPreviousNonComment(); 107 if (!LBrace || !LBrace->isOneOf(tok::l_brace, TT_ArrayInitializerLSquare) || 108 LBrace->is(BK_Block) || LBrace->is(TT_DictLiteral) || 109 LBrace->Next->is(TT_DesignatedInitializerPeriod)) { 110 return 0; 111 } 112 113 // Calculate the number of code points we have to format this list. As the 114 // first token is already placed, we have to subtract it. 115 unsigned RemainingCodePoints = 116 Style.ColumnLimit - State.Column + State.NextToken->Previous->ColumnWidth; 117 118 // Find the best ColumnFormat, i.e. the best number of columns to use. 119 const ColumnFormat *Format = getColumnFormat(RemainingCodePoints); 120 121 // If no ColumnFormat can be used, the braced list would generally be 122 // bin-packed. Add a severe penalty to this so that column layouts are 123 // preferred if possible. 124 if (!Format) 125 return 10000; 126 127 // Format the entire list. 128 unsigned Penalty = 0; 129 unsigned Column = 0; 130 unsigned Item = 0; 131 while (State.NextToken != LBrace->MatchingParen) { 132 bool NewLine = false; 133 unsigned ExtraSpaces = 0; 134 135 // If the previous token was one of our commas, we are now on the next item. 136 if (Item < Commas.size() && State.NextToken->Previous == Commas[Item]) { 137 if (!State.NextToken->isTrailingComment()) { 138 ExtraSpaces += Format->ColumnSizes[Column] - ItemLengths[Item]; 139 ++Column; 140 } 141 ++Item; 142 } 143 144 if (Column == Format->Columns || State.NextToken->MustBreakBefore) { 145 Column = 0; 146 NewLine = true; 147 } 148 149 // Place token using the continuation indenter and store the penalty. 150 Penalty += Indenter->addTokenToState(State, NewLine, DryRun, ExtraSpaces); 151 } 152 return Penalty; 153 } 154 155 unsigned CommaSeparatedList::formatFromToken(LineState &State, 156 ContinuationIndenter *Indenter, 157 bool DryRun) { 158 // Formatting with 1 Column isn't really a column layout, so we don't need the 159 // special logic here. We can just avoid bin packing any of the parameters. 160 if (Formats.size() == 1 || HasNestedBracedList) 161 State.Stack.back().AvoidBinPacking = true; 162 return 0; 163 } 164 165 // Returns the lengths in code points between Begin and End (both included), 166 // assuming that the entire sequence is put on a single line. 167 static unsigned CodePointsBetween(const FormatToken *Begin, 168 const FormatToken *End) { 169 assert(End->TotalLength >= Begin->TotalLength); 170 return End->TotalLength - Begin->TotalLength + Begin->ColumnWidth; 171 } 172 173 void CommaSeparatedList::precomputeFormattingInfos(const FormatToken *Token) { 174 // FIXME: At some point we might want to do this for other lists, too. 175 if (!Token->MatchingParen || 176 !Token->isOneOf(tok::l_brace, TT_ArrayInitializerLSquare)) { 177 return; 178 } 179 180 // In C++11 braced list style, we should not format in columns unless they 181 // have many items (20 or more) or we allow bin-packing of function call 182 // arguments. 183 if (Style.Cpp11BracedListStyle && !Style.BinPackArguments && 184 Commas.size() < 19) { 185 return; 186 } 187 188 // Limit column layout for JavaScript array initializers to 20 or more items 189 // for now to introduce it carefully. We can become more aggressive if this 190 // necessary. 191 if (Token->is(TT_ArrayInitializerLSquare) && Commas.size() < 19) 192 return; 193 194 // Column format doesn't really make sense if we don't align after brackets. 195 if (Style.AlignAfterOpenBracket == FormatStyle::BAS_DontAlign) 196 return; 197 198 FormatToken *ItemBegin = Token->Next; 199 while (ItemBegin->isTrailingComment()) 200 ItemBegin = ItemBegin->Next; 201 SmallVector<bool, 8> MustBreakBeforeItem; 202 203 // The lengths of an item if it is put at the end of the line. This includes 204 // trailing comments which are otherwise ignored for column alignment. 205 SmallVector<unsigned, 8> EndOfLineItemLength; 206 MustBreakBeforeItem.reserve(Commas.size() + 1); 207 EndOfLineItemLength.reserve(Commas.size() + 1); 208 ItemLengths.reserve(Commas.size() + 1); 209 210 bool HasSeparatingComment = false; 211 for (unsigned i = 0, e = Commas.size() + 1; i != e; ++i) { 212 assert(ItemBegin); 213 // Skip comments on their own line. 214 while (ItemBegin->HasUnescapedNewline && ItemBegin->isTrailingComment()) { 215 ItemBegin = ItemBegin->Next; 216 HasSeparatingComment = i > 0; 217 } 218 219 MustBreakBeforeItem.push_back(ItemBegin->MustBreakBefore); 220 if (ItemBegin->is(tok::l_brace)) 221 HasNestedBracedList = true; 222 const FormatToken *ItemEnd = nullptr; 223 if (i == Commas.size()) { 224 ItemEnd = Token->MatchingParen; 225 const FormatToken *NonCommentEnd = ItemEnd->getPreviousNonComment(); 226 ItemLengths.push_back(CodePointsBetween(ItemBegin, NonCommentEnd)); 227 if (Style.Cpp11BracedListStyle && 228 !ItemEnd->Previous->isTrailingComment()) { 229 // In Cpp11 braced list style, the } and possibly other subsequent 230 // tokens will need to stay on a line with the last element. 231 while (ItemEnd->Next && !ItemEnd->Next->CanBreakBefore) 232 ItemEnd = ItemEnd->Next; 233 } else { 234 // In other braced lists styles, the "}" can be wrapped to the new line. 235 ItemEnd = Token->MatchingParen->Previous; 236 } 237 } else { 238 ItemEnd = Commas[i]; 239 // The comma is counted as part of the item when calculating the length. 240 ItemLengths.push_back(CodePointsBetween(ItemBegin, ItemEnd)); 241 242 // Consume trailing comments so the are included in EndOfLineItemLength. 243 if (ItemEnd->Next && !ItemEnd->Next->HasUnescapedNewline && 244 ItemEnd->Next->isTrailingComment()) { 245 ItemEnd = ItemEnd->Next; 246 } 247 } 248 EndOfLineItemLength.push_back(CodePointsBetween(ItemBegin, ItemEnd)); 249 // If there is a trailing comma in the list, the next item will start at the 250 // closing brace. Don't create an extra item for this. 251 if (ItemEnd->getNextNonComment() == Token->MatchingParen) 252 break; 253 ItemBegin = ItemEnd->Next; 254 } 255 256 // Don't use column layout for lists with few elements and in presence of 257 // separating comments. 258 if (Commas.size() < 5 || HasSeparatingComment) 259 return; 260 261 if (Token->NestingLevel != 0 && Token->is(tok::l_brace) && Commas.size() < 19) 262 return; 263 264 // We can never place more than ColumnLimit / 3 items in a row (because of the 265 // spaces and the comma). 266 unsigned MaxItems = Style.ColumnLimit / 3; 267 SmallVector<unsigned> MinSizeInColumn; 268 MinSizeInColumn.reserve(MaxItems); 269 for (unsigned Columns = 1; Columns <= MaxItems; ++Columns) { 270 ColumnFormat Format; 271 Format.Columns = Columns; 272 Format.ColumnSizes.resize(Columns); 273 MinSizeInColumn.assign(Columns, UINT_MAX); 274 Format.LineCount = 1; 275 bool HasRowWithSufficientColumns = false; 276 unsigned Column = 0; 277 for (unsigned i = 0, e = ItemLengths.size(); i != e; ++i) { 278 assert(i < MustBreakBeforeItem.size()); 279 if (MustBreakBeforeItem[i] || Column == Columns) { 280 ++Format.LineCount; 281 Column = 0; 282 } 283 if (Column == Columns - 1) 284 HasRowWithSufficientColumns = true; 285 unsigned Length = 286 (Column == Columns - 1) ? EndOfLineItemLength[i] : ItemLengths[i]; 287 Format.ColumnSizes[Column] = std::max(Format.ColumnSizes[Column], Length); 288 MinSizeInColumn[Column] = std::min(MinSizeInColumn[Column], Length); 289 ++Column; 290 } 291 // If all rows are terminated early (e.g. by trailing comments), we don't 292 // need to look further. 293 if (!HasRowWithSufficientColumns) 294 break; 295 Format.TotalWidth = Columns - 1; // Width of the N-1 spaces. 296 297 for (unsigned i = 0; i < Columns; ++i) 298 Format.TotalWidth += Format.ColumnSizes[i]; 299 300 // Don't use this Format, if the difference between the longest and shortest 301 // element in a column exceeds a threshold to avoid excessive spaces. 302 if ([&] { 303 for (unsigned i = 0; i < Columns - 1; ++i) 304 if (Format.ColumnSizes[i] - MinSizeInColumn[i] > 10) 305 return true; 306 return false; 307 }()) { 308 continue; 309 } 310 311 // Ignore layouts that are bound to violate the column limit. 312 if (Format.TotalWidth > Style.ColumnLimit && Columns > 1) 313 continue; 314 315 Formats.push_back(Format); 316 } 317 } 318 319 const CommaSeparatedList::ColumnFormat * 320 CommaSeparatedList::getColumnFormat(unsigned RemainingCharacters) const { 321 const ColumnFormat *BestFormat = nullptr; 322 for (const ColumnFormat &Format : llvm::reverse(Formats)) { 323 if (Format.TotalWidth <= RemainingCharacters || Format.Columns == 1) { 324 if (BestFormat && Format.LineCount > BestFormat->LineCount) 325 break; 326 BestFormat = &Format; 327 } 328 } 329 return BestFormat; 330 } 331 332 } // namespace format 333 } // namespace clang 334