1100 lines · cpp
1//===----------------------------------------------------------------------===//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#include "LoopConvertCheck.h"10#include "clang/AST/ASTContext.h"11#include "clang/ASTMatchers/ASTMatchFinder.h"12#include "clang/Basic/LLVM.h"13#include "clang/Basic/LangOptions.h"14#include "clang/Basic/SourceLocation.h"15#include "clang/Basic/SourceManager.h"16#include "clang/Lex/Lexer.h"17#include "llvm/ADT/ArrayRef.h"18#include "llvm/ADT/SmallVector.h"19#include "llvm/ADT/StringRef.h"20#include "llvm/ADT/StringSet.h"21#include "llvm/Support/raw_ostream.h"22#include <cassert>23#include <cstring>24#include <optional>25#include <utility>26 27using namespace clang::ast_matchers;28using namespace llvm;29 30namespace clang::tidy {31 32template <> struct OptionEnumMapping<modernize::Confidence::Level> {33 static llvm::ArrayRef<std::pair<modernize::Confidence::Level, StringRef>>34 getEnumMapping() {35 static constexpr std::pair<modernize::Confidence::Level, StringRef>36 Mapping[] = {{modernize::Confidence::CL_Reasonable, "reasonable"},37 {modernize::Confidence::CL_Safe, "safe"},38 {modernize::Confidence::CL_Risky, "risky"}};39 return {Mapping};40 }41};42 43template <> struct OptionEnumMapping<modernize::VariableNamer::NamingStyle> {44 static llvm::ArrayRef<45 std::pair<modernize::VariableNamer::NamingStyle, StringRef>>46 getEnumMapping() {47 static constexpr std::pair<modernize::VariableNamer::NamingStyle, StringRef>48 Mapping[] = {{modernize::VariableNamer::NS_CamelCase, "CamelCase"},49 {modernize::VariableNamer::NS_CamelBack, "camelBack"},50 {modernize::VariableNamer::NS_LowerCase, "lower_case"},51 {modernize::VariableNamer::NS_UpperCase, "UPPER_CASE"}};52 return {Mapping};53 }54};55 56namespace modernize {57 58static const char LoopNameArray[] = "forLoopArray";59static const char LoopNameIterator[] = "forLoopIterator";60static const char LoopNameReverseIterator[] = "forLoopReverseIterator";61static const char LoopNamePseudoArray[] = "forLoopPseudoArray";62static const char ConditionBoundName[] = "conditionBound";63static const char InitVarName[] = "initVar";64static const char BeginCallName[] = "beginCall";65static const char EndCallName[] = "endCall";66static const char EndVarName[] = "endVar";67static const char DerefByValueResultName[] = "derefByValueResult";68static const char DerefByRefResultName[] = "derefByRefResult";69static const llvm::StringSet<> MemberNames{"begin", "cbegin", "rbegin",70 "crbegin", "end", "cend",71 "rend", "crend", "size"};72static const llvm::StringSet<> ADLNames{"begin", "cbegin", "rbegin",73 "crbegin", "end", "cend",74 "rend", "crend", "size"};75static const llvm::StringSet<> StdNames{76 "std::begin", "std::cbegin", "std::rbegin", "std::crbegin", "std::end",77 "std::cend", "std::rend", "std::crend", "std::size"};78 79static StatementMatcher integerComparisonMatcher() {80 return expr(ignoringParenImpCasts(81 declRefExpr(to(varDecl(equalsBoundNode(InitVarName))))));82}83 84static DeclarationMatcher initToZeroMatcher() {85 return varDecl(86 hasInitializer(ignoringParenImpCasts(integerLiteral(equals(0)))))87 .bind(InitVarName);88}89 90static StatementMatcher incrementVarMatcher() {91 return declRefExpr(to(varDecl(equalsBoundNode(InitVarName))));92}93 94static StatementMatcher95arrayConditionMatcher(const internal::Matcher<Expr> &LimitExpr) {96 return binaryOperator(97 anyOf(allOf(hasOperatorName("<"), hasLHS(integerComparisonMatcher()),98 hasRHS(LimitExpr)),99 allOf(hasOperatorName(">"), hasLHS(LimitExpr),100 hasRHS(integerComparisonMatcher())),101 allOf(hasOperatorName("!="),102 hasOperands(integerComparisonMatcher(), LimitExpr))));103}104 105/// The matcher for loops over arrays.106/// \code107/// for (int i = 0; i < 3 + 2; ++i) { ... }108/// \endcode109/// The following string identifiers are bound to these parts of the AST:110/// ConditionBoundName: '3 + 2' (as an Expr)111/// InitVarName: 'i' (as a VarDecl)112/// LoopName: The entire for loop (as a ForStmt)113///114/// Client code will need to make sure that:115/// - The index variable is only used as an array index.116/// - All arrays indexed by the loop are the same.117static StatementMatcher makeArrayLoopMatcher() {118 const StatementMatcher ArrayBoundMatcher =119 expr(hasType(isInteger())).bind(ConditionBoundName);120 121 return forStmt(unless(isInTemplateInstantiation()),122 hasLoopInit(declStmt(hasSingleDecl(initToZeroMatcher()))),123 hasCondition(arrayConditionMatcher(ArrayBoundMatcher)),124 hasIncrement(125 unaryOperator(hasOperatorName("++"),126 hasUnaryOperand(incrementVarMatcher()))))127 .bind(LoopNameArray);128}129 130/// The matcher used for iterator-based for loops.131///132/// This matcher is more flexible than array-based loops. It will match133/// catch loops of the following textual forms (regardless of whether the134/// iterator type is actually a pointer type or a class type):135///136/// \code137/// for (containerType::iterator it = container.begin(),138/// e = createIterator(); it != e; ++it) { ... }139/// for (containerType::iterator it = container.begin();140/// it != anotherContainer.end(); ++it) { ... }141/// for (containerType::iterator it = begin(container),142/// e = end(container); it != e; ++it) { ... }143/// for (containerType::iterator it = std::begin(container),144/// e = std::end(container); it != e; ++it) { ... }145/// \endcode146/// The following string identifiers are bound to the parts of the AST:147/// InitVarName: 'it' (as a VarDecl)148/// LoopName: The entire for loop (as a ForStmt)149/// In the first example only:150/// EndVarName: 'e' (as a VarDecl)151/// In the second example only:152/// EndCallName: 'container.end()' (as a CXXMemberCallExpr)153/// In the third/fourth examples:154/// 'end(container)' or 'std::end(container)' (as a CallExpr)155///156/// Client code will need to make sure that:157/// - The two containers on which 'begin' and 'end' are called are the same.158static StatementMatcher makeIteratorLoopMatcher(bool IsReverse) {159 auto BeginNameMatcher = IsReverse ? hasAnyName("rbegin", "crbegin")160 : hasAnyName("begin", "cbegin");161 auto BeginNameMatcherStd = IsReverse162 ? hasAnyName("::std::rbegin", "::std::crbegin")163 : hasAnyName("::std::begin", "::std::cbegin");164 165 auto EndNameMatcher =166 IsReverse ? hasAnyName("rend", "crend") : hasAnyName("end", "cend");167 auto EndNameMatcherStd = IsReverse ? hasAnyName("::std::rend", "::std::crend")168 : hasAnyName("::std::end", "::std::cend");169 170 const StatementMatcher BeginCallMatcher =171 expr(anyOf(cxxMemberCallExpr(argumentCountIs(0),172 callee(cxxMethodDecl(BeginNameMatcher))),173 callExpr(argumentCountIs(1),174 callee(functionDecl(BeginNameMatcher)), usesADL()),175 callExpr(argumentCountIs(1),176 callee(functionDecl(BeginNameMatcherStd)))))177 .bind(BeginCallName);178 179 const DeclarationMatcher InitDeclMatcher =180 varDecl(hasInitializer(anyOf(ignoringParenImpCasts(BeginCallMatcher),181 materializeTemporaryExpr(182 ignoringParenImpCasts(BeginCallMatcher)),183 hasDescendant(BeginCallMatcher))))184 .bind(InitVarName);185 186 const DeclarationMatcher EndDeclMatcher =187 varDecl(hasInitializer(anything())).bind(EndVarName);188 189 const StatementMatcher EndCallMatcher = expr(anyOf(190 cxxMemberCallExpr(argumentCountIs(0),191 callee(cxxMethodDecl(EndNameMatcher))),192 callExpr(argumentCountIs(1), callee(functionDecl(EndNameMatcher)),193 usesADL()),194 callExpr(argumentCountIs(1), callee(functionDecl(EndNameMatcherStd)))));195 196 const StatementMatcher IteratorBoundMatcher =197 expr(anyOf(ignoringParenImpCasts(198 declRefExpr(to(varDecl(equalsBoundNode(EndVarName))))),199 ignoringParenImpCasts(expr(EndCallMatcher).bind(EndCallName)),200 materializeTemporaryExpr(ignoringParenImpCasts(201 expr(EndCallMatcher).bind(EndCallName)))));202 203 const StatementMatcher IteratorComparisonMatcher = expr(ignoringParenImpCasts(204 declRefExpr(to(varDecl(equalsBoundNode(InitVarName))))));205 206 // This matcher tests that a declaration is a CXXRecordDecl that has an207 // overloaded operator*(). If the operator*() returns by value instead of by208 // reference then the return type is tagged with DerefByValueResultName.209 const internal::Matcher<VarDecl> TestDerefReturnsByValue =210 hasType(hasUnqualifiedDesugaredType(211 recordType(hasDeclaration(cxxRecordDecl(hasMethod(cxxMethodDecl(212 hasOverloadedOperatorName("*"),213 anyOf(214 // Tag the return type if it's by value.215 returns(qualType(unless(hasCanonicalType(referenceType())))216 .bind(DerefByValueResultName)),217 returns(218 // Skip loops where the iterator's operator* returns an219 // rvalue reference. This is just weird.220 qualType(unless(hasCanonicalType(rValueReferenceType())))221 .bind(DerefByRefResultName))))))))));222 223 return forStmt(224 unless(isInTemplateInstantiation()),225 hasLoopInit(anyOf(declStmt(declCountIs(2),226 containsDeclaration(0, InitDeclMatcher),227 containsDeclaration(1, EndDeclMatcher)),228 declStmt(hasSingleDecl(InitDeclMatcher)))),229 hasCondition(ignoringImplicit(binaryOperation(230 hasOperatorName("!="), hasOperands(IteratorComparisonMatcher,231 IteratorBoundMatcher)))),232 hasIncrement(anyOf(233 unaryOperator(hasOperatorName("++"),234 hasUnaryOperand(declRefExpr(235 to(varDecl(equalsBoundNode(InitVarName)))))),236 cxxOperatorCallExpr(237 hasOverloadedOperatorName("++"),238 hasArgument(0, declRefExpr(to(239 varDecl(equalsBoundNode(InitVarName),240 TestDerefReturnsByValue))))))))241 .bind(IsReverse ? LoopNameReverseIterator : LoopNameIterator);242}243 244/// The matcher used for array-like containers (pseudoarrays).245///246/// This matcher is more flexible than array-based loops. It will match247/// loops of the following textual forms (regardless of whether the248/// iterator type is actually a pointer type or a class type):249///250/// \code251/// for (int i = 0, j = container.size(); i < j; ++i) { ... }252/// for (int i = 0; i < container.size(); ++i) { ... }253/// for (int i = 0; i < size(container); ++i) { ... }254/// \endcode255/// The following string identifiers are bound to the parts of the AST:256/// InitVarName: 'i' (as a VarDecl)257/// LoopName: The entire for loop (as a ForStmt)258/// In the first example only:259/// EndVarName: 'j' (as a VarDecl)260/// In the second example only:261/// EndCallName: 'container.size()' (as a CXXMemberCallExpr) or262/// 'size(container)' (as a CallExpr)263///264/// Client code will need to make sure that:265/// - The containers on which 'size()' is called is the container indexed.266/// - The index variable is only used in overloaded operator[] or267/// container.at().268/// - The container's iterators would not be invalidated during the loop.269static StatementMatcher makePseudoArrayLoopMatcher() {270 // Test that the incoming type has a record declaration that has methods271 // called 'begin' and 'end'. If the incoming type is const, then make sure272 // these methods are also marked const.273 //274 // FIXME: To be completely thorough this matcher should also ensure the275 // return type of begin/end is an iterator that dereferences to the same as276 // what operator[] or at() returns. Such a test isn't likely to fail except277 // for pathological cases.278 //279 // FIXME: Also, a record doesn't necessarily need begin() and end(). Free280 // functions called begin() and end() taking the container as an argument281 // are also allowed.282 const TypeMatcher RecordWithBeginEnd = qualType(anyOf(283 qualType(isConstQualified(),284 hasUnqualifiedDesugaredType(recordType(hasDeclaration(285 cxxRecordDecl(isSameOrDerivedFrom(cxxRecordDecl(286 hasMethod(cxxMethodDecl(hasName("begin"), isConst())),287 hasMethod(cxxMethodDecl(hasName("end"),288 isConst())))))) // hasDeclaration289 ))), // qualType290 qualType(unless(isConstQualified()),291 hasUnqualifiedDesugaredType(recordType(hasDeclaration(292 cxxRecordDecl(isSameOrDerivedFrom(cxxRecordDecl(293 hasMethod(hasName("begin")),294 hasMethod(hasName("end"))))))))) // qualType295 ));296 297 const StatementMatcher SizeCallMatcher = expr(anyOf(298 cxxMemberCallExpr(argumentCountIs(0),299 callee(cxxMethodDecl(hasAnyName("size", "length"))),300 on(anyOf(hasType(pointsTo(RecordWithBeginEnd)),301 hasType(RecordWithBeginEnd)))),302 callExpr(argumentCountIs(1), callee(functionDecl(hasName("size"))),303 usesADL()),304 callExpr(argumentCountIs(1),305 callee(functionDecl(hasName("::std::size"))))));306 307 StatementMatcher EndInitMatcher =308 expr(anyOf(ignoringParenImpCasts(expr(SizeCallMatcher).bind(EndCallName)),309 explicitCastExpr(hasSourceExpression(ignoringParenImpCasts(310 expr(SizeCallMatcher).bind(EndCallName))))));311 312 const DeclarationMatcher EndDeclMatcher =313 varDecl(hasInitializer(EndInitMatcher)).bind(EndVarName);314 315 const StatementMatcher IndexBoundMatcher =316 expr(anyOf(ignoringParenImpCasts(317 declRefExpr(to(varDecl(equalsBoundNode(EndVarName))))),318 EndInitMatcher));319 320 return forStmt(unless(isInTemplateInstantiation()),321 hasLoopInit(322 anyOf(declStmt(declCountIs(2),323 containsDeclaration(0, initToZeroMatcher()),324 containsDeclaration(1, EndDeclMatcher)),325 declStmt(hasSingleDecl(initToZeroMatcher())))),326 hasCondition(arrayConditionMatcher(IndexBoundMatcher)),327 hasIncrement(328 unaryOperator(hasOperatorName("++"),329 hasUnaryOperand(incrementVarMatcher()))))330 .bind(LoopNamePseudoArray);331}332 333enum class IteratorCallKind {334 ICK_Member,335 ICK_ADL,336 ICK_Std,337};338 339struct ContainerCall {340 const Expr *Container;341 StringRef Name;342 bool IsArrow;343 IteratorCallKind CallKind;344};345 346// Find the Expr likely initializing an iterator.347//348// Call is either a CXXMemberCallExpr ('c.begin()') or CallExpr of a free349// function with the first argument as a container ('begin(c)'), or nullptr.350// Returns at a 3-tuple with the container expr, function name (begin/end/etc),351// and whether the call is made through an arrow (->) for CXXMemberCallExprs.352// The returned Expr* is nullptr if any of the assumptions are not met.353// static std::tuple<const Expr *, StringRef, bool, IteratorCallKind>354static std::optional<ContainerCall> getContainerExpr(const Expr *Call) {355 const Expr *Dug = digThroughConstructorsConversions(Call);356 357 IteratorCallKind CallKind = IteratorCallKind::ICK_Member;358 359 if (const auto *TheCall = dyn_cast_or_null<CXXMemberCallExpr>(Dug)) {360 CallKind = IteratorCallKind::ICK_Member;361 if (const auto *Member = dyn_cast<MemberExpr>(TheCall->getCallee())) {362 if (Member->getMemberDecl() == nullptr ||363 !MemberNames.contains(Member->getMemberDecl()->getName()))364 return std::nullopt;365 return ContainerCall{TheCall->getImplicitObjectArgument(),366 Member->getMemberDecl()->getName(),367 Member->isArrow(), CallKind};368 }369 if (TheCall->getDirectCallee() == nullptr ||370 !MemberNames.contains(TheCall->getDirectCallee()->getName()))371 return std::nullopt;372 return ContainerCall{TheCall->getArg(0),373 TheCall->getDirectCallee()->getName(), false,374 CallKind};375 }376 if (const auto *TheCall = dyn_cast_or_null<CallExpr>(Dug)) {377 if (TheCall->getNumArgs() != 1)378 return std::nullopt;379 380 if (TheCall->usesADL()) {381 if (TheCall->getDirectCallee() == nullptr ||382 !ADLNames.contains(TheCall->getDirectCallee()->getName()))383 return std::nullopt;384 CallKind = IteratorCallKind::ICK_ADL;385 } else {386 if (!StdNames.contains(387 TheCall->getDirectCallee()->getQualifiedNameAsString()))388 return std::nullopt;389 CallKind = IteratorCallKind::ICK_Std;390 }391 392 if (TheCall->getDirectCallee() == nullptr)393 return std::nullopt;394 395 return ContainerCall{TheCall->getArg(0),396 TheCall->getDirectCallee()->getName(), false,397 CallKind};398 }399 return std::nullopt;400}401 402/// Determine whether Init appears to be an initializing an iterator.403///404/// If it is, returns the object whose begin() or end() method is called, and405/// the output parameter isArrow is set to indicate whether the initialization406/// is called via . or ->.407static std::pair<const Expr *, IteratorCallKind>408getContainerFromBeginEndCall(const Expr *Init, bool IsBegin, bool *IsArrow,409 bool IsReverse) {410 // FIXME: Maybe allow declaration/initialization outside of the for loop.411 412 std::optional<ContainerCall> Call = getContainerExpr(Init);413 if (!Call)414 return {};415 416 *IsArrow = Call->IsArrow;417 if (!Call->Name.consume_back(IsBegin ? "begin" : "end"))418 return {};419 if (IsReverse && !Call->Name.consume_back("r"))420 return {};421 if (!Call->Name.empty() && Call->Name != "c")422 return {};423 return std::make_pair(Call->Container, Call->CallKind);424}425 426/// Determines the container whose begin() and end() functions are called427/// for an iterator-based loop.428///429/// BeginExpr must be a member call to a function named "begin()", and EndExpr430/// must be a member.431static const Expr *findContainer(ASTContext *Context, const Expr *BeginExpr,432 const Expr *EndExpr,433 bool *ContainerNeedsDereference,434 bool IsReverse) {435 // Now that we know the loop variable and test expression, make sure they are436 // valid.437 bool BeginIsArrow = false;438 bool EndIsArrow = false;439 auto [BeginContainerExpr, BeginCallKind] = getContainerFromBeginEndCall(440 BeginExpr, /*IsBegin=*/true, &BeginIsArrow, IsReverse);441 if (!BeginContainerExpr)442 return nullptr;443 444 auto [EndContainerExpr, EndCallKind] = getContainerFromBeginEndCall(445 EndExpr, /*IsBegin=*/false, &EndIsArrow, IsReverse);446 if (BeginCallKind != EndCallKind)447 return nullptr;448 449 // Disallow loops that try evil things like this (note the dot and arrow):450 // for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }451 if (!EndContainerExpr || BeginIsArrow != EndIsArrow ||452 !areSameExpr(Context, EndContainerExpr, BeginContainerExpr))453 return nullptr;454 455 *ContainerNeedsDereference = BeginIsArrow;456 return BeginContainerExpr;457}458 459/// Obtain the original source code text from a SourceRange.460static StringRef getStringFromRange(SourceManager &SourceMgr,461 const LangOptions &LangOpts,462 SourceRange Range) {463 if (SourceMgr.getFileID(Range.getBegin()) !=464 SourceMgr.getFileID(Range.getEnd())) {465 return {}; // Empty string.466 }467 468 return Lexer::getSourceText(CharSourceRange(Range, true), SourceMgr,469 LangOpts);470}471 472/// If the given expression is actually a DeclRefExpr or a MemberExpr,473/// find and return the underlying ValueDecl; otherwise, return NULL.474static const ValueDecl *getReferencedVariable(const Expr *E) {475 if (const DeclRefExpr *DRE = getDeclRef(E))476 return dyn_cast<VarDecl>(DRE->getDecl());477 if (const auto *Mem = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))478 return dyn_cast<FieldDecl>(Mem->getMemberDecl());479 return nullptr;480}481 482/// Returns true when the given expression is a member expression483/// whose base is `this` (implicitly or not).484static bool isDirectMemberExpr(const Expr *E) {485 if (const auto *Member = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))486 return isa<CXXThisExpr>(Member->getBase()->IgnoreParenImpCasts());487 return false;488}489 490/// Given an expression that represents an usage of an element from the491/// container that we are iterating over, returns false when it can be492/// guaranteed this element cannot be modified as a result of this usage.493static bool canBeModified(ASTContext *Context, const Expr *E) {494 if (E->getType().isConstQualified())495 return false;496 auto Parents = Context->getParents(*E);497 if (Parents.size() != 1)498 return true;499 if (const auto *Cast = Parents[0].get<ImplicitCastExpr>()) {500 if ((Cast->getCastKind() == CK_NoOp &&501 ASTContext::hasSameType(Cast->getType(), E->getType().withConst())) ||502 (Cast->getCastKind() == CK_LValueToRValue &&503 !Cast->getType().isNull() && Cast->getType()->isFundamentalType()))504 return false;505 }506 // FIXME: Make this function more generic.507 return true;508}509 510/// Returns true when it can be guaranteed that the elements of the511/// container are not being modified.512static bool usagesAreConst(ASTContext *Context, const UsageResult &Usages) {513 for (const Usage &U : Usages) {514 // Lambda captures are just redeclarations (VarDecl) of the same variable,515 // not expressions. If we want to know if a variable that is captured by516 // reference can be modified in an usage inside the lambda's body, we need517 // to find the expression corresponding to that particular usage, later in518 // this loop.519 if (U.Kind != Usage::UK_CaptureByCopy && U.Kind != Usage::UK_CaptureByRef &&520 canBeModified(Context, U.Expression))521 return false;522 }523 return true;524}525 526/// Returns true if the elements of the container are never accessed527/// by reference.528static bool usagesReturnRValues(const UsageResult &Usages) {529 for (const auto &U : Usages) {530 if (U.Expression && !U.Expression->isPRValue())531 return false;532 }533 return true;534}535 536/// Returns true if the container is const-qualified.537static bool containerIsConst(const Expr *ContainerExpr, bool Dereference) {538 if (const auto *VDec = getReferencedVariable(ContainerExpr)) {539 QualType CType = VDec->getType();540 if (Dereference) {541 if (!CType->isPointerType())542 return false;543 CType = CType->getPointeeType();544 }545 // If VDec is a reference to a container, Dereference is false,546 // but we still need to check the const-ness of the underlying container547 // type.548 CType = CType.getNonReferenceType();549 return CType.isConstQualified();550 }551 return false;552}553 554LoopConvertCheck::LoopConvertCheck(StringRef Name, ClangTidyContext *Context)555 : ClangTidyCheck(Name, Context), TUInfo(new TUTrackingInfo),556 MaxCopySize(Options.get("MaxCopySize", 16ULL)),557 MinConfidence(Options.get("MinConfidence", Confidence::CL_Reasonable)),558 NamingStyle(Options.get("NamingStyle", VariableNamer::NS_CamelCase)),559 Inserter(Options.getLocalOrGlobal("IncludeStyle",560 utils::IncludeSorter::IS_LLVM),561 areDiagsSelfContained()),562 UseCxx20IfAvailable(Options.get("UseCxx20ReverseRanges", true)),563 ReverseFunction(Options.get("MakeReverseRangeFunction", "")),564 ReverseHeader(Options.get("MakeReverseRangeHeader", "")) {565 if (ReverseFunction.empty() && !ReverseHeader.empty()) {566 configurationDiag(567 "modernize-loop-convert: 'MakeReverseRangeHeader' is set but "568 "'MakeReverseRangeFunction' is not, disabling reverse loop "569 "transformation");570 UseReverseRanges = false;571 } else if (ReverseFunction.empty()) {572 UseReverseRanges = UseCxx20IfAvailable && getLangOpts().CPlusPlus20;573 } else {574 UseReverseRanges = true;575 }576}577 578void LoopConvertCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {579 Options.store(Opts, "MaxCopySize", MaxCopySize);580 Options.store(Opts, "MinConfidence", MinConfidence);581 Options.store(Opts, "NamingStyle", NamingStyle);582 Options.store(Opts, "IncludeStyle", Inserter.getStyle());583 Options.store(Opts, "UseCxx20ReverseRanges", UseCxx20IfAvailable);584 Options.store(Opts, "MakeReverseRangeFunction", ReverseFunction);585 Options.store(Opts, "MakeReverseRangeHeader", ReverseHeader);586}587 588void LoopConvertCheck::registerPPCallbacks(const SourceManager &SM,589 Preprocessor *PP,590 Preprocessor *ModuleExpanderPP) {591 Inserter.registerPreprocessor(PP);592}593 594void LoopConvertCheck::registerMatchers(MatchFinder *Finder) {595 Finder->addMatcher(traverse(TK_AsIs, makeArrayLoopMatcher()), this);596 Finder->addMatcher(traverse(TK_AsIs, makeIteratorLoopMatcher(false)), this);597 Finder->addMatcher(traverse(TK_AsIs, makePseudoArrayLoopMatcher()), this);598 if (UseReverseRanges)599 Finder->addMatcher(traverse(TK_AsIs, makeIteratorLoopMatcher(true)), this);600}601 602/// Given the range of a single declaration, such as:603/// \code604/// unsigned &ThisIsADeclarationThatCanSpanSeveralLinesOfCode =605/// InitializationValues[I];606/// next_instruction;607/// \endcode608/// Finds the range that has to be erased to remove this declaration without609/// leaving empty lines, by extending the range until the beginning of the610/// next instruction.611///612/// We need to delete a potential newline after the deleted alias, as613/// clang-format will leave empty lines untouched. For all other formatting we614/// rely on clang-format to fix it.615void LoopConvertCheck::getAliasRange(SourceManager &SM, SourceRange &Range) {616 bool Invalid = false;617 const char *TextAfter =618 SM.getCharacterData(Range.getEnd().getLocWithOffset(1), &Invalid);619 if (Invalid)620 return;621 const unsigned Offset = std::strspn(TextAfter, " \t\r\n");622 Range =623 SourceRange(Range.getBegin(), Range.getEnd().getLocWithOffset(Offset));624}625 626/// Computes the changes needed to convert a given for loop, and627/// applies them.628void LoopConvertCheck::doConversion(629 ASTContext *Context, const VarDecl *IndexVar,630 const ValueDecl *MaybeContainer, const UsageResult &Usages,631 const DeclStmt *AliasDecl, bool AliasUseRequired, bool AliasFromForInit,632 const ForStmt *Loop, RangeDescriptor Descriptor) {633 std::string VarNameOrStructuredBinding;634 const bool VarNameFromAlias = (Usages.size() == 1) && AliasDecl;635 bool AliasVarIsRef = false;636 bool CanCopy = true;637 std::vector<FixItHint> FixIts;638 if (VarNameFromAlias) {639 const auto *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());640 641 // Handle structured bindings642 if (const auto *AliasDecompositionDecl =643 dyn_cast<DecompositionDecl>(AliasDecl->getSingleDecl())) {644 VarNameOrStructuredBinding = "[";645 646 assert(!AliasDecompositionDecl->bindings().empty() && "No bindings");647 for (const BindingDecl *Binding : AliasDecompositionDecl->bindings()) {648 VarNameOrStructuredBinding += Binding->getName().str() + ", ";649 }650 651 VarNameOrStructuredBinding.erase(VarNameOrStructuredBinding.size() - 2,652 2);653 VarNameOrStructuredBinding += "]";654 } else {655 VarNameOrStructuredBinding = AliasVar->getName().str();656 657 // Use the type of the alias if it's not the same658 QualType AliasVarType = AliasVar->getType();659 assert(!AliasVarType.isNull() && "Type in VarDecl is null");660 if (AliasVarType->isReferenceType()) {661 AliasVarType = AliasVarType.getNonReferenceType();662 AliasVarIsRef = true;663 }664 if (Descriptor.ElemType.isNull() ||665 !ASTContext::hasSameUnqualifiedType(AliasVarType,666 Descriptor.ElemType))667 Descriptor.ElemType = AliasVarType;668 }669 670 // We keep along the entire DeclStmt to keep the correct range here.671 SourceRange ReplaceRange = AliasDecl->getSourceRange();672 673 std::string ReplacementText;674 if (AliasUseRequired) {675 ReplacementText = VarNameOrStructuredBinding;676 } else if (AliasFromForInit) {677 // FIXME: Clang includes the location of the ';' but only for DeclStmt's678 // in a for loop's init clause. Need to put this ';' back while removing679 // the declaration of the alias variable. This is probably a bug.680 ReplacementText = ";";681 } else {682 // Avoid leaving empty lines or trailing whitespaces.683 getAliasRange(Context->getSourceManager(), ReplaceRange);684 }685 686 FixIts.push_back(FixItHint::CreateReplacement(687 CharSourceRange::getTokenRange(ReplaceRange), ReplacementText));688 // No further replacements are made to the loop, since the iterator or index689 // was used exactly once - in the initialization of AliasVar.690 } else {691 VariableNamer Namer(&TUInfo->getGeneratedDecls(),692 &TUInfo->getParentFinder().getStmtToParentStmtMap(),693 Loop, IndexVar, MaybeContainer, Context, NamingStyle);694 VarNameOrStructuredBinding = Namer.createIndexName();695 // First, replace all usages of the array subscript expression with our new696 // variable.697 for (const auto &Usage : Usages) {698 std::string ReplaceText;699 SourceRange Range = Usage.Range;700 if (Usage.Expression) {701 // If this is an access to a member through the arrow operator, after702 // the replacement it must be accessed through the '.' operator.703 ReplaceText = Usage.Kind == Usage::UK_MemberThroughArrow704 ? VarNameOrStructuredBinding + "."705 : VarNameOrStructuredBinding;706 const DynTypedNodeList Parents = Context->getParents(*Usage.Expression);707 if (Parents.size() == 1) {708 if (const auto *Paren = Parents[0].get<ParenExpr>()) {709 // Usage.Expression will be replaced with the new index variable,710 // and parenthesis around a simple DeclRefExpr can always be711 // removed except in case of a `sizeof` operator call.712 const DynTypedNodeList GrandParents = Context->getParents(*Paren);713 if (GrandParents.size() != 1 ||714 GrandParents[0].get<UnaryExprOrTypeTraitExpr>() == nullptr) {715 Range = Paren->getSourceRange();716 }717 } else if (const auto *UOP = Parents[0].get<UnaryOperator>()) {718 // If we are taking the address of the loop variable, then we must719 // not use a copy, as it would mean taking the address of the loop's720 // local index instead.721 // FIXME: This won't catch cases where the address is taken outside722 // of the loop's body (for instance, in a function that got the723 // loop's index as a const reference parameter), or where we take724 // the address of a member (like "&Arr[i].A.B.C").725 if (UOP->getOpcode() == UO_AddrOf)726 CanCopy = false;727 }728 }729 } else {730 // The Usage expression is only null in case of lambda captures (which731 // are VarDecl). If the index is captured by value, add '&' to capture732 // by reference instead.733 ReplaceText = Usage.Kind == Usage::UK_CaptureByCopy734 ? "&" + VarNameOrStructuredBinding735 : VarNameOrStructuredBinding;736 }737 TUInfo->getReplacedVars().insert(std::make_pair(Loop, IndexVar));738 FixIts.push_back(FixItHint::CreateReplacement(739 CharSourceRange::getTokenRange(Range), ReplaceText));740 }741 }742 743 // Now, we need to construct the new range expression.744 const SourceRange ParenRange(Loop->getLParenLoc(), Loop->getRParenLoc());745 746 QualType Type = Context->getAutoDeductType();747 if (!Descriptor.ElemType.isNull() && Descriptor.ElemType->isFundamentalType())748 Type = Descriptor.ElemType.getUnqualifiedType();749 Type = Type.getDesugaredType(*Context);750 751 // If the new variable name is from the aliased variable, then the reference752 // type for the new variable should only be used if the aliased variable was753 // declared as a reference.754 const bool IsCheapToCopy =755 !Descriptor.ElemType.isNull() &&756 Descriptor.ElemType.isTriviallyCopyableType(*Context) &&757 !Descriptor.ElemType->isDependentSizedArrayType() &&758 // TypeInfo::Width is in bits.759 Context->getTypeInfo(Descriptor.ElemType).Width <= 8 * MaxCopySize;760 const bool UseCopy =761 CanCopy && ((VarNameFromAlias && !AliasVarIsRef) ||762 (Descriptor.DerefByConstRef && IsCheapToCopy));763 764 if (!UseCopy) {765 if (Descriptor.DerefByConstRef) {766 Type = Context->getLValueReferenceType(Context->getConstType(Type));767 } else if (Descriptor.DerefByValue) {768 if (!IsCheapToCopy)769 Type = Context->getRValueReferenceType(Type);770 } else {771 Type = Context->getLValueReferenceType(Type);772 }773 }774 775 SmallString<128> Range;776 llvm::raw_svector_ostream Output(Range);777 Output << '(';778 Type.print(Output, getLangOpts());779 Output << ' ' << VarNameOrStructuredBinding << " : ";780 if (Descriptor.NeedsReverseCall)781 Output << getReverseFunction() << '(';782 if (Descriptor.ContainerNeedsDereference)783 Output << '*';784 Output << Descriptor.ContainerString;785 if (Descriptor.NeedsReverseCall)786 Output << "))";787 else788 Output << ')';789 FixIts.push_back(FixItHint::CreateReplacement(790 CharSourceRange::getTokenRange(ParenRange), Range));791 792 if (Descriptor.NeedsReverseCall && !getReverseHeader().empty()) {793 if (std::optional<FixItHint> Insertion = Inserter.createIncludeInsertion(794 Context->getSourceManager().getFileID(Loop->getBeginLoc()),795 getReverseHeader()))796 FixIts.push_back(*Insertion);797 }798 diag(Loop->getForLoc(), "use range-based for loop instead") << FixIts;799 TUInfo->getGeneratedDecls().insert(800 make_pair(Loop, VarNameOrStructuredBinding));801}802 803/// Returns a string which refers to the container iterated over.804StringRef LoopConvertCheck::getContainerString(ASTContext *Context,805 const ForStmt *Loop,806 const Expr *ContainerExpr) {807 StringRef ContainerString;808 ContainerExpr = ContainerExpr->IgnoreParenImpCasts();809 if (isa<CXXThisExpr>(ContainerExpr)) {810 ContainerString = "this";811 } else {812 // For CXXOperatorCallExpr such as vector_ptr->size() we want the class813 // object vector_ptr, but for vector[2] we need the whole expression.814 if (const auto *E = dyn_cast<CXXOperatorCallExpr>(ContainerExpr))815 if (E->getOperator() != OO_Subscript)816 ContainerExpr = E->getArg(0);817 ContainerString =818 getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),819 ContainerExpr->getSourceRange());820 }821 822 return ContainerString;823}824 825/// Determines what kind of 'auto' must be used after converting a for826/// loop that iterates over an array or pseudoarray.827void LoopConvertCheck::getArrayLoopQualifiers(ASTContext *Context,828 const BoundNodes &Nodes,829 const Expr *ContainerExpr,830 const UsageResult &Usages,831 RangeDescriptor &Descriptor) {832 // On arrays and pseudoarrays, we must figure out the qualifiers from the833 // usages.834 if (usagesAreConst(Context, Usages) ||835 containerIsConst(ContainerExpr, Descriptor.ContainerNeedsDereference)) {836 Descriptor.DerefByConstRef = true;837 }838 if (usagesReturnRValues(Usages)) {839 // If the index usages (dereference, subscript, at, ...) return rvalues,840 // then we should not use a reference, because we need to keep the code841 // correct if it mutates the returned objects.842 Descriptor.DerefByValue = true;843 }844 // Try to find the type of the elements on the container, to check if845 // they are trivially copyable.846 for (const Usage &U : Usages) {847 if (!U.Expression || U.Expression->getType().isNull())848 continue;849 QualType Type = U.Expression->getType().getCanonicalType();850 if (U.Kind == Usage::UK_MemberThroughArrow) {851 if (!Type->isPointerType()) {852 continue;853 }854 Type = Type->getPointeeType();855 }856 Descriptor.ElemType = Type;857 }858}859 860/// Determines what kind of 'auto' must be used after converting an861/// iterator based for loop.862void LoopConvertCheck::getIteratorLoopQualifiers(ASTContext *Context,863 const BoundNodes &Nodes,864 RangeDescriptor &Descriptor) {865 // The matchers for iterator loops provide bound nodes to obtain this866 // information.867 const auto *InitVar = Nodes.getNodeAs<VarDecl>(InitVarName);868 const QualType CanonicalInitVarType = InitVar->getType().getCanonicalType();869 const auto *DerefByValueType =870 Nodes.getNodeAs<QualType>(DerefByValueResultName);871 Descriptor.DerefByValue = DerefByValueType;872 873 if (Descriptor.DerefByValue) {874 // If the dereference operator returns by value then test for the875 // canonical const qualification of the init variable type.876 Descriptor.DerefByConstRef = CanonicalInitVarType.isConstQualified();877 Descriptor.ElemType = *DerefByValueType;878 } else {879 if (const auto *DerefType =880 Nodes.getNodeAs<QualType>(DerefByRefResultName)) {881 // A node will only be bound with DerefByRefResultName if we're dealing882 // with a user-defined iterator type. Test the const qualification of883 // the reference type.884 auto ValueType = DerefType->getNonReferenceType();885 886 Descriptor.DerefByConstRef = ValueType.isConstQualified();887 Descriptor.ElemType = ValueType;888 } else {889 // By nature of the matcher this case is triggered only for built-in890 // iterator types (i.e. pointers).891 assert(isa<PointerType>(CanonicalInitVarType) &&892 "Non-class iterator type is not a pointer type");893 894 // We test for const qualification of the pointed-at type.895 Descriptor.DerefByConstRef =896 CanonicalInitVarType->getPointeeType().isConstQualified();897 Descriptor.ElemType = CanonicalInitVarType->getPointeeType();898 }899 }900}901 902/// Determines the parameters needed to build the range replacement.903void LoopConvertCheck::determineRangeDescriptor(904 ASTContext *Context, const BoundNodes &Nodes, const ForStmt *Loop,905 LoopFixerKind FixerKind, const Expr *ContainerExpr,906 const UsageResult &Usages, RangeDescriptor &Descriptor) {907 Descriptor.ContainerString =908 std::string(getContainerString(Context, Loop, ContainerExpr));909 Descriptor.NeedsReverseCall = (FixerKind == LFK_ReverseIterator);910 911 if (FixerKind == LFK_Iterator || FixerKind == LFK_ReverseIterator)912 getIteratorLoopQualifiers(Context, Nodes, Descriptor);913 else914 getArrayLoopQualifiers(Context, Nodes, ContainerExpr, Usages, Descriptor);915}916 917/// Check some of the conditions that must be met for the loop to be918/// convertible.919bool LoopConvertCheck::isConvertible(ASTContext *Context,920 const ast_matchers::BoundNodes &Nodes,921 const ForStmt *Loop,922 LoopFixerKind FixerKind) {923 // In self contained diagnostic mode we don't want dependencies on other924 // loops, otherwise, If we already modified the range of this for loop, don't925 // do any further updates on this iteration.926 if (areDiagsSelfContained())927 TUInfo = std::make_unique<TUTrackingInfo>();928 else if (TUInfo->getReplacedVars().contains(Loop))929 return false;930 931 // Check that we have exactly one index variable and at most one end variable.932 const auto *InitVar = Nodes.getNodeAs<VarDecl>(InitVarName);933 934 // FIXME: Try to put most of this logic inside a matcher.935 if (FixerKind == LFK_Iterator || FixerKind == LFK_ReverseIterator) {936 const QualType InitVarType = InitVar->getType();937 const QualType CanonicalInitVarType = InitVarType.getCanonicalType();938 939 const auto *BeginCall = Nodes.getNodeAs<CallExpr>(BeginCallName);940 assert(BeginCall && "Bad Callback. No begin call expression");941 const QualType CanonicalBeginType =942 BeginCall->getDirectCallee()->getReturnType().getCanonicalType();943 if (CanonicalBeginType->isPointerType() &&944 CanonicalInitVarType->isPointerType()) {945 // If the initializer and the variable are both pointers check if the946 // un-qualified pointee types match, otherwise we don't use auto.947 return ASTContext::hasSameUnqualifiedType(948 CanonicalBeginType->getPointeeType(),949 CanonicalInitVarType->getPointeeType());950 }951 952 if (CanonicalBeginType->isBuiltinType() ||953 CanonicalInitVarType->isBuiltinType())954 return false;955 956 } else if (FixerKind == LFK_PseudoArray) {957 if (const auto *EndCall = Nodes.getNodeAs<CXXMemberCallExpr>(EndCallName)) {958 // This call is required to obtain the container.959 if (!isa<MemberExpr>(EndCall->getCallee()))960 return false;961 }962 return Nodes.getNodeAs<CallExpr>(EndCallName) != nullptr;963 }964 return true;965}966 967void LoopConvertCheck::check(const MatchFinder::MatchResult &Result) {968 const BoundNodes &Nodes = Result.Nodes;969 Confidence ConfidenceLevel(Confidence::CL_Safe);970 ASTContext *Context = Result.Context;971 972 const ForStmt *Loop = nullptr;973 LoopFixerKind FixerKind{};974 RangeDescriptor Descriptor;975 976 if ((Loop = Nodes.getNodeAs<ForStmt>(LoopNameArray))) {977 FixerKind = LFK_Array;978 } else if ((Loop = Nodes.getNodeAs<ForStmt>(LoopNameIterator))) {979 FixerKind = LFK_Iterator;980 } else if ((Loop = Nodes.getNodeAs<ForStmt>(LoopNameReverseIterator))) {981 FixerKind = LFK_ReverseIterator;982 } else {983 Loop = Nodes.getNodeAs<ForStmt>(LoopNamePseudoArray);984 assert(Loop && "Bad Callback. No for statement");985 FixerKind = LFK_PseudoArray;986 }987 988 if (!isConvertible(Context, Nodes, Loop, FixerKind))989 return;990 991 const auto *LoopVar = Nodes.getNodeAs<VarDecl>(InitVarName);992 const auto *EndVar = Nodes.getNodeAs<VarDecl>(EndVarName);993 994 // If the loop calls end()/size() after each iteration, lower our confidence995 // level.996 if (FixerKind != LFK_Array && !EndVar)997 ConfidenceLevel.lowerTo(Confidence::CL_Reasonable);998 999 // If the end comparison isn't a variable, we can try to work with the1000 // expression the loop variable is being tested against instead.1001 const auto *EndCall = Nodes.getNodeAs<Expr>(EndCallName);1002 const auto *BoundExpr = Nodes.getNodeAs<Expr>(ConditionBoundName);1003 1004 // Find container expression of iterators and pseudoarrays, and determine if1005 // this expression needs to be dereferenced to obtain the container.1006 // With array loops, the container is often discovered during the1007 // ForLoopIndexUseVisitor traversal.1008 const Expr *ContainerExpr = nullptr;1009 if (FixerKind == LFK_Iterator || FixerKind == LFK_ReverseIterator) {1010 ContainerExpr = findContainer(1011 Context, LoopVar->getInit(), EndVar ? EndVar->getInit() : EndCall,1012 &Descriptor.ContainerNeedsDereference,1013 /*IsReverse=*/FixerKind == LFK_ReverseIterator);1014 } else if (FixerKind == LFK_PseudoArray) {1015 std::optional<ContainerCall> Call = getContainerExpr(EndCall);1016 if (Call) {1017 ContainerExpr = Call->Container;1018 Descriptor.ContainerNeedsDereference = Call->IsArrow;1019 }1020 }1021 1022 // We must know the container or an array length bound.1023 if (!ContainerExpr && !BoundExpr)1024 return;1025 1026 ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,1027 BoundExpr,1028 Descriptor.ContainerNeedsDereference);1029 1030 // Find expressions and variables on which the container depends.1031 if (ContainerExpr) {1032 ComponentFinderASTVisitor ComponentFinder;1033 ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());1034 Finder.addComponents(ComponentFinder.getComponents());1035 }1036 1037 // Find usages of the loop index. If they are not used in a convertible way,1038 // stop here.1039 if (!Finder.findAndVerifyUsages(Loop->getBody()))1040 return;1041 ConfidenceLevel.lowerTo(Finder.getConfidenceLevel());1042 1043 // Obtain the container expression, if we don't have it yet.1044 if (FixerKind == LFK_Array) {1045 ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();1046 1047 // Very few loops are over expressions that generate arrays rather than1048 // array variables. Consider loops over arrays that aren't just represented1049 // by a variable to be risky conversions.1050 if (!getReferencedVariable(ContainerExpr) &&1051 !isDirectMemberExpr(ContainerExpr))1052 ConfidenceLevel.lowerTo(Confidence::CL_Risky);1053 }1054 1055 // Find out which qualifiers we have to use in the loop range.1056 const TraversalKindScope RAII(*Context, TK_AsIs);1057 const UsageResult &Usages = Finder.getUsages();1058 determineRangeDescriptor(Context, Nodes, Loop, FixerKind, ContainerExpr,1059 Usages, Descriptor);1060 1061 // Ensure that we do not try to move an expression dependent on a local1062 // variable declared inside the loop outside of it.1063 // FIXME: Determine when the external dependency isn't an expression converted1064 // by another loop.1065 TUInfo->getParentFinder().gatherAncestors(*Context);1066 DependencyFinderASTVisitor DependencyFinder(1067 &TUInfo->getParentFinder().getStmtToParentStmtMap(),1068 &TUInfo->getParentFinder().getDeclToParentStmtMap(),1069 &TUInfo->getReplacedVars(), Loop);1070 1071 if (DependencyFinder.dependsOnInsideVariable(ContainerExpr) ||1072 Descriptor.ContainerString.empty() || Usages.empty() ||1073 ConfidenceLevel.getLevel() < MinConfidence)1074 return;1075 1076 doConversion(Context, LoopVar, getReferencedVariable(ContainerExpr), Usages,1077 Finder.getAliasDecl(), Finder.aliasUseRequired(),1078 Finder.aliasFromForInit(), Loop, Descriptor);1079}1080 1081llvm::StringRef LoopConvertCheck::getReverseFunction() const {1082 if (!ReverseFunction.empty())1083 return ReverseFunction;1084 if (UseReverseRanges)1085 return "std::ranges::reverse_view";1086 return "";1087}1088 1089llvm::StringRef LoopConvertCheck::getReverseHeader() const {1090 if (!ReverseHeader.empty())1091 return ReverseHeader;1092 if (UseReverseRanges && ReverseFunction.empty()) {1093 return "<ranges>";1094 }1095 return "";1096}1097 1098} // namespace modernize1099} // namespace clang::tidy1100