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