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