909 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 "LoopConvertUtils.h"10#include "../utils/ASTUtils.h"11#include "clang/Basic/IdentifierTable.h"12#include "clang/Basic/LLVM.h"13#include "clang/Basic/Lambda.h"14#include "clang/Basic/SourceLocation.h"15#include "clang/Basic/SourceManager.h"16#include "clang/Basic/TokenKinds.h"17#include "clang/Lex/Lexer.h"18#include "llvm/ADT/APSInt.h"19#include "llvm/ADT/FoldingSet.h"20#include "llvm/ADT/StringRef.h"21#include <cassert>22#include <cstddef>23#include <optional>24#include <string>25#include <utility>26 27using namespace clang::ast_matchers;28 29namespace clang::tidy::modernize {30 31/// Tracks a stack of parent statements during traversal.32///33/// All this really does is inject push_back() before running34/// RecursiveASTVisitor::TraverseStmt() and pop_back() afterwards. The Stmt atop35/// the stack is the parent of the current statement (NULL for the topmost36/// statement).37bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) {38 StmtAncestors.insert(std::make_pair(Statement, StmtStack.back()));39 StmtStack.push_back(Statement);40 RecursiveASTVisitor<StmtAncestorASTVisitor>::TraverseStmt(Statement);41 StmtStack.pop_back();42 return true;43}44 45/// Keep track of the DeclStmt associated with each VarDecl.46///47/// Combined with StmtAncestors, this provides roughly the same information as48/// Scope, as we can map a VarDecl to its DeclStmt, then walk up the parent tree49/// using StmtAncestors.50bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Statement) {51 for (const auto *Decl : Statement->decls()) {52 if (const auto *V = dyn_cast<VarDecl>(Decl))53 DeclParents.insert(std::make_pair(V, Statement));54 }55 return true;56}57 58/// record the DeclRefExpr as part of the parent expression.59bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) {60 Components.push_back(E);61 return true;62}63 64/// record the MemberExpr as part of the parent expression.65bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) {66 Components.push_back(Member);67 return true;68}69 70/// Forward any DeclRefExprs to a check on the referenced variable71/// declaration.72bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {73 if (auto *V = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))74 return VisitVarDecl(V);75 return true;76}77 78/// Determine if any this variable is declared inside the ContainingStmt.79bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) {80 const Stmt *Curr = DeclParents->lookup(V);81 // First, see if the variable was declared within an inner scope of the loop.82 while (Curr != nullptr) {83 if (Curr == ContainingStmt) {84 DependsOnInsideVariable = true;85 return false;86 }87 Curr = StmtParents->lookup(Curr);88 }89 90 // Next, check if the variable was removed from existence by an earlier91 // iteration.92 for (const auto &I : *ReplacedVars) {93 if (I.second == V) {94 DependsOnInsideVariable = true;95 return false;96 }97 }98 return true;99}100 101/// If we already created a variable for TheLoop, check to make sure102/// that the name was not already taken.103bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) {104 const StmtGeneratedVarNameMap::const_iterator I =105 GeneratedDecls->find(TheLoop);106 if (I != GeneratedDecls->end() && I->second == Name) {107 Found = true;108 return false;109 }110 return true;111}112 113/// If any named declaration within the AST subtree has the same name,114/// then consider Name already taken.115bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) {116 const IdentifierInfo *Ident = D->getIdentifier();117 if (Ident && Ident->getName() == Name) {118 Found = true;119 return false;120 }121 return true;122}123 124/// Forward any declaration references to the actual check on the125/// referenced declaration.126bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {127 if (auto *D = dyn_cast<NamedDecl>(DeclRef->getDecl()))128 return VisitNamedDecl(D);129 return true;130}131 132/// If the new variable name conflicts with any type used in the loop,133/// then we mark that variable name as taken.134bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) {135 const QualType QType = TL.getType();136 137 // Check if our name conflicts with a type, to handle for typedefs.138 if (QType.getAsString() == Name) {139 Found = true;140 return false;141 }142 // Check for base type conflicts. For example, when a struct is being143 // referenced in the body of the loop, the above getAsString() will return the144 // whole type (ex. "struct s"), but will be caught here.145 if (const IdentifierInfo *Ident = QType.getBaseTypeIdentifier()) {146 if (Ident->getName() == Name) {147 Found = true;148 return false;149 }150 }151 return true;152}153 154/// Look through conversion/copy constructors and member functions to find the155/// explicit initialization expression, returning it is found.156///157/// The main idea is that given158/// vector<int> v;159/// we consider either of these initializations160/// vector<int>::iterator it = v.begin();161/// vector<int>::iterator it(v.begin());162/// vector<int>::const_iterator it(v.begin());163/// and retrieve `v.begin()` as the expression used to initialize `it` but do164/// not include165/// vector<int>::iterator it;166/// vector<int>::iterator it(v.begin(), 0); // if this constructor existed167/// as being initialized from `v.begin()`168const Expr *digThroughConstructorsConversions(const Expr *E) {169 if (!E)170 return nullptr;171 E = E->IgnoreImplicit();172 if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {173 // The initial constructor must take exactly one parameter, but base class174 // and deferred constructors can take more.175 if (ConstructExpr->getNumArgs() != 1 ||176 ConstructExpr->getConstructionKind() != CXXConstructionKind::Complete)177 return nullptr;178 E = ConstructExpr->getArg(0);179 if (const auto *Temp = dyn_cast<MaterializeTemporaryExpr>(E))180 E = Temp->getSubExpr();181 return digThroughConstructorsConversions(E);182 }183 // If this is a conversion (as iterators commonly convert into their const184 // iterator counterparts), dig through that as well.185 if (const auto *ME = dyn_cast<CXXMemberCallExpr>(E))186 if (isa<CXXConversionDecl>(ME->getMethodDecl()))187 return digThroughConstructorsConversions(ME->getImplicitObjectArgument());188 return E;189}190 191/// Returns true when two Exprs are equivalent.192bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second) {193 return utils::areStatementsIdentical(First, Second, *Context, true);194}195 196/// Returns the DeclRefExpr represented by E, or NULL if there isn't one.197const DeclRefExpr *getDeclRef(const Expr *E) {198 return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());199}200 201/// Returns true when two ValueDecls are the same variable.202bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) {203 return First && Second &&204 First->getCanonicalDecl() == Second->getCanonicalDecl();205}206 207/// Determines if an expression is a declaration reference to a208/// particular variable.209static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) {210 if (!Target || !E)211 return false;212 const DeclRefExpr *Decl = getDeclRef(E);213 return Decl && areSameVariable(Target, Decl->getDecl());214}215 216/// If the expression is a dereference or call to operator*(), return the217/// operand. Otherwise, return NULL.218static const Expr *getDereferenceOperand(const Expr *E) {219 if (const auto *Uop = dyn_cast<UnaryOperator>(E))220 return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : nullptr;221 222 if (const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(E)) {223 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1224 ? OpCall->getArg(0)225 : nullptr;226 }227 228 return nullptr;229}230 231/// Returns true when the Container contains an Expr equivalent to E.232template <typename ContainerT>233static bool containsExpr(ASTContext *Context, const ContainerT *Container,234 const Expr *E) {235 llvm::FoldingSetNodeID ID;236 E->Profile(ID, *Context, true);237 for (const auto &I : *Container) {238 if (ID == I.second)239 return true;240 }241 return false;242}243 244/// Returns true when the index expression is a declaration reference to245/// IndexVar.246///247/// If the index variable is `index`, this function returns true on248/// arrayExpression[index];249/// containerExpression[index];250/// but not251/// containerExpression[notIndex];252static bool isIndexInSubscriptExpr(const Expr *IndexExpr,253 const VarDecl *IndexVar) {254 const DeclRefExpr *Idx = getDeclRef(IndexExpr);255 return Idx && Idx->getType()->isIntegerType() &&256 areSameVariable(IndexVar, Idx->getDecl());257}258 259/// Returns true when the index expression is a declaration reference to260/// IndexVar, Obj is the same expression as SourceExpr after all parens and261/// implicit casts are stripped off.262///263/// If PermitDeref is true, IndexExpression may264/// be a dereference (overloaded or builtin operator*).265///266/// This function is intended for array-like containers, as it makes sure that267/// both the container and the index match.268/// If the loop has index variable `index` and iterates over `container`, then269/// isIndexInSubscriptExpr returns true for270/// \code271/// container[index]272/// container.at(index)273/// container->at(index)274/// \endcode275/// but not for276/// \code277/// container[notIndex]278/// notContainer[index]279/// \endcode280/// If PermitDeref is true, then isIndexInSubscriptExpr additionally returns281/// true on these expressions:282/// \code283/// (*container)[index]284/// (*container).at(index)285/// \endcode286static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,287 const VarDecl *IndexVar, const Expr *Obj,288 const Expr *SourceExpr, bool PermitDeref) {289 if (!SourceExpr || !Obj || !isIndexInSubscriptExpr(IndexExpr, IndexVar))290 return false;291 292 if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),293 Obj->IgnoreParenImpCasts()))294 return true;295 296 if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))297 if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),298 InnerObj->IgnoreParenImpCasts()))299 return true;300 301 return false;302}303 304/// Returns true when Opcall is a call a one-parameter dereference of305/// IndexVar.306///307/// For example, if the index variable is `index`, returns true for308/// *index309/// but not310/// index311/// *notIndex312static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall,313 const VarDecl *IndexVar) {314 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&315 exprReferencesVariable(IndexVar, OpCall->getArg(0));316}317 318/// Returns true when Uop is a dereference of IndexVar.319///320/// For example, if the index variable is `index`, returns true for321/// *index322/// but not323/// index324/// *notIndex325static bool isDereferenceOfUop(const UnaryOperator *Uop,326 const VarDecl *IndexVar) {327 return Uop->getOpcode() == UO_Deref &&328 exprReferencesVariable(IndexVar, Uop->getSubExpr());329}330 331/// Determines whether the given Decl defines a variable initialized to332/// the loop object.333///334/// This is intended to find cases such as335/// \code336/// for (int i = 0; i < arraySize(arr); ++i) {337/// T t = arr[i];338/// // use t, do not use i339/// }340/// \endcode341/// and342/// \code343/// for (iterator i = container.begin(), e = container.end(); i != e; ++i) {344/// T t = *i;345/// // use t, do not use i346/// }347/// \endcode348static bool isAliasDecl(ASTContext *Context, const Decl *TheDecl,349 const VarDecl *IndexVar) {350 const auto *VDecl = dyn_cast<VarDecl>(TheDecl);351 if (!VDecl)352 return false;353 if (!VDecl->hasInit())354 return false;355 356 bool OnlyCasts = true;357 const Expr *Init = VDecl->getInit()->IgnoreParenImpCasts();358 if (isa_and_nonnull<CXXConstructExpr>(Init)) {359 Init = digThroughConstructorsConversions(Init);360 OnlyCasts = false;361 }362 if (!Init)363 return false;364 365 // Check that the declared type is the same as (or a reference to) the366 // container type.367 if (!OnlyCasts) {368 const QualType InitType = Init->getType();369 QualType DeclarationType = VDecl->getType();370 if (!DeclarationType.isNull() && DeclarationType->isReferenceType())371 DeclarationType = DeclarationType.getNonReferenceType();372 373 if (InitType.isNull() || DeclarationType.isNull() ||374 !ASTContext::hasSameUnqualifiedType(DeclarationType, InitType))375 return false;376 }377 378 switch (Init->getStmtClass()) {379 case Stmt::ArraySubscriptExprClass: {380 const auto *E = cast<ArraySubscriptExpr>(Init);381 // We don't really care which array is used here. We check to make sure382 // it was the correct one later, since the AST will traverse it next.383 return isIndexInSubscriptExpr(E->getIdx(), IndexVar);384 }385 386 case Stmt::UnaryOperatorClass:387 return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar);388 389 case Stmt::CXXOperatorCallExprClass: {390 const auto *OpCall = cast<CXXOperatorCallExpr>(Init);391 if (OpCall->getOperator() == OO_Star)392 return isDereferenceOfOpCall(OpCall, IndexVar);393 if (OpCall->getOperator() == OO_Subscript) {394 return OpCall->getNumArgs() == 2 &&395 isIndexInSubscriptExpr(OpCall->getArg(1), IndexVar);396 }397 break;398 }399 400 case Stmt::CXXMemberCallExprClass: {401 const auto *MemCall = cast<CXXMemberCallExpr>(Init);402 // This check is needed because getMethodDecl can return nullptr if the403 // callee is a member function pointer.404 const auto *MDecl = MemCall->getMethodDecl();405 if (MDecl && !isa<CXXConversionDecl>(MDecl) &&406 MDecl->getNameAsString() == "at" && MemCall->getNumArgs() == 1) {407 return isIndexInSubscriptExpr(MemCall->getArg(0), IndexVar);408 }409 return false;410 }411 412 default:413 break;414 }415 return false;416}417 418/// Determines whether the bound of a for loop condition expression is419/// the same as the statically computable size of ArrayType.420///421/// Given422/// \code423/// const int N = 5;424/// int arr[N];425/// \endcode426/// This is intended to permit427/// \code428/// for (int i = 0; i < N; ++i) { /* use arr[i] */ }429/// for (int i = 0; i < arraysize(arr); ++i) { /* use arr[i] */ }430/// \endcode431static bool arrayMatchesBoundExpr(ASTContext *Context,432 const QualType &ArrayType,433 const Expr *ConditionExpr) {434 if (!ConditionExpr || ConditionExpr->isValueDependent())435 return false;436 const ConstantArrayType *ConstType =437 Context->getAsConstantArrayType(ArrayType);438 if (!ConstType)439 return false;440 std::optional<llvm::APSInt> ConditionSize =441 ConditionExpr->getIntegerConstantExpr(*Context);442 if (!ConditionSize)443 return false;444 const llvm::APSInt ArraySize(ConstType->getSize());445 return llvm::APSInt::isSameValue(*ConditionSize, ArraySize);446}447 448ForLoopIndexUseVisitor::ForLoopIndexUseVisitor(ASTContext *Context,449 const VarDecl *IndexVar,450 const VarDecl *EndVar,451 const Expr *ContainerExpr,452 const Expr *ArrayBoundExpr,453 bool ContainerNeedsDereference)454 : Context(Context), IndexVar(IndexVar), EndVar(EndVar),455 ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),456 ContainerNeedsDereference(ContainerNeedsDereference),457 458 ConfidenceLevel(Confidence::CL_Safe) {459 if (ContainerExpr)460 addComponent(ContainerExpr);461}462 463bool ForLoopIndexUseVisitor::findAndVerifyUsages(const Stmt *Body) {464 TraverseStmt(const_cast<Stmt *>(Body));465 return OnlyUsedAsIndex && ContainerExpr;466}467 468void ForLoopIndexUseVisitor::addComponents(const ComponentVector &Components) {469 // FIXME: add sort(on ID)+unique to avoid extra work.470 for (const auto &I : Components)471 addComponent(I);472}473 474void ForLoopIndexUseVisitor::addComponent(const Expr *E) {475 llvm::FoldingSetNodeID ID;476 const Expr *Node = E->IgnoreParenImpCasts();477 Node->Profile(ID, *Context, true);478 DependentExprs.push_back(std::make_pair(Node, ID));479}480 481void ForLoopIndexUseVisitor::addUsage(const Usage &U) {482 SourceLocation Begin = U.Range.getBegin();483 if (Begin.isMacroID())484 Begin = Context->getSourceManager().getSpellingLoc(Begin);485 486 if (UsageLocations.insert(Begin).second)487 Usages.push_back(U);488}489 490/// If the unary operator is a dereference of IndexVar, include it491/// as a valid usage and prune the traversal.492///493/// For example, if container.begin() and container.end() both return pointers494/// to int, this makes sure that the initialization for `k` is not counted as an495/// unconvertible use of the iterator `i`.496/// \code497/// for (int *i = container.begin(), *e = container.end(); i != e; ++i) {498/// int k = *i + 2;499/// }500/// \endcode501bool ForLoopIndexUseVisitor::TraverseUnaryOperator(UnaryOperator *Uop) {502 // If we dereference an iterator that's actually a pointer, count the503 // occurrence.504 if (isDereferenceOfUop(Uop, IndexVar)) {505 addUsage(Usage(Uop));506 return true;507 }508 509 return VisitorBase::TraverseUnaryOperator(Uop);510}511 512/// If the member expression is operator-> (overloaded or not) on513/// IndexVar, include it as a valid usage and prune the traversal.514///515/// For example, given516/// \code517/// struct Foo { int bar(); int x; };518/// vector<Foo> v;519/// \endcode520/// the following uses will be considered convertible:521/// \code522/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {523/// int b = i->bar();524/// int k = i->x + 1;525/// }526/// \endcode527/// though528/// \code529/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {530/// int k = i.insert(1);531/// }532/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {533/// int b = e->bar();534/// }535/// \endcode536/// will not.537bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {538 const Expr *Base = Member->getBase();539 const DeclRefExpr *Obj = getDeclRef(Base);540 const Expr *ResultExpr = Member;541 QualType ExprType;542 if (const auto *Call =543 dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {544 // If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then545 // the MemberExpr does not have the expression we want. We therefore catch546 // that instance here.547 // For example, if vector<Foo>::iterator defines operator->(), then the548 // example `i->bar()` at the top of this function is a CXXMemberCallExpr549 // referring to `i->` as the member function called. We want just `i`, so550 // we take the argument to operator->() as the base object.551 if (Call->getOperator() == OO_Arrow) {552 assert(Call->getNumArgs() == 1 &&553 "Operator-> takes more than one argument");554 Obj = getDeclRef(Call->getArg(0));555 ResultExpr = Obj;556 ExprType = Call->getCallReturnType(*Context);557 }558 }559 560 if (Obj && exprReferencesVariable(IndexVar, Obj)) {561 // Member calls on the iterator with '.' are not allowed.562 if (!Member->isArrow()) {563 OnlyUsedAsIndex = false;564 return true;565 }566 567 if (ExprType.isNull())568 ExprType = Obj->getType();569 570 if (!ExprType->isPointerType())571 return false;572 573 // FIXME: This works around not having the location of the arrow operator.574 // Consider adding OperatorLoc to MemberExpr?575 const SourceLocation ArrowLoc = Lexer::getLocForEndOfToken(576 Base->getExprLoc(), 0, Context->getSourceManager(),577 Context->getLangOpts());578 // If something complicated is happening (i.e. the next token isn't an579 // arrow), give up on making this work.580 if (ArrowLoc.isValid()) {581 addUsage(Usage(ResultExpr, Usage::UK_MemberThroughArrow,582 SourceRange(Base->getExprLoc(), ArrowLoc)));583 return true;584 }585 }586 return VisitorBase::TraverseMemberExpr(Member);587}588 589/// If a member function call is the at() accessor on the container with590/// IndexVar as the single argument, include it as a valid usage and prune591/// the traversal.592///593/// Member calls on other objects will not be permitted.594/// Calls on the iterator object are not permitted, unless done through595/// operator->(). The one exception is allowing vector::at() for pseudoarrays.596bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(597 CXXMemberCallExpr *MemberCall) {598 auto *Member =599 dyn_cast<MemberExpr>(MemberCall->getCallee()->IgnoreParenImpCasts());600 if (!Member)601 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);602 603 // We specifically allow an accessor named "at" to let STL in, though604 // this is restricted to pseudo-arrays by requiring a single, integer605 // argument.606 const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();607 if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) {608 if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar,609 Member->getBase(), ContainerExpr,610 ContainerNeedsDereference)) {611 addUsage(Usage(MemberCall));612 return true;613 }614 }615 616 if (containsExpr(Context, &DependentExprs, Member->getBase()))617 ConfidenceLevel.lowerTo(Confidence::CL_Risky);618 619 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);620}621 622/// If an overloaded operator call is a dereference of IndexVar or623/// a subscript of the container with IndexVar as the single argument,624/// include it as a valid usage and prune the traversal.625///626/// For example, given627/// \code628/// struct Foo { int bar(); int x; };629/// vector<Foo> v;630/// void f(Foo);631/// \endcode632/// the following uses will be considered convertible:633/// \code634/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {635/// f(*i);636/// }637/// for (int i = 0; i < v.size(); ++i) {638/// int i = v[i] + 1;639/// }640/// \endcode641bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(642 CXXOperatorCallExpr *OpCall) {643 switch (OpCall->getOperator()) {644 case OO_Star:645 if (isDereferenceOfOpCall(OpCall, IndexVar)) {646 addUsage(Usage(OpCall));647 return true;648 }649 break;650 651 case OO_Subscript:652 if (OpCall->getNumArgs() != 2)653 break;654 if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,655 OpCall->getArg(0), ContainerExpr,656 ContainerNeedsDereference)) {657 addUsage(Usage(OpCall));658 return true;659 }660 break;661 662 default:663 break;664 }665 return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);666}667 668/// If we encounter an array with IndexVar as the index of an669/// ArraySubscriptExpression, note it as a consistent usage and prune the670/// AST traversal.671///672/// For example, given673/// \code674/// const int N = 5;675/// int arr[N];676/// \endcode677/// This is intended to permit678/// \code679/// for (int i = 0; i < N; ++i) { /* use arr[i] */ }680/// \endcode681/// but not682/// \code683/// for (int i = 0; i < N; ++i) { /* use notArr[i] */ }684/// \endcode685/// and further checking needs to be done later to ensure that exactly one array686/// is referenced.687bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(ArraySubscriptExpr *E) {688 Expr *Arr = E->getBase();689 if (!isIndexInSubscriptExpr(E->getIdx(), IndexVar))690 return VisitorBase::TraverseArraySubscriptExpr(E);691 692 if ((ContainerExpr && !areSameExpr(Context, Arr->IgnoreParenImpCasts(),693 ContainerExpr->IgnoreParenImpCasts())) ||694 !arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(),695 ArrayBoundExpr)) {696 // If we have already discovered the array being indexed and this isn't it697 // or this array doesn't match, mark this loop as unconvertible.698 OnlyUsedAsIndex = false;699 return VisitorBase::TraverseArraySubscriptExpr(E);700 }701 702 if (!ContainerExpr)703 ContainerExpr = Arr;704 705 addUsage(Usage(E));706 return true;707}708 709/// If we encounter a reference to IndexVar in an unpruned branch of the710/// traversal, mark this loop as unconvertible.711///712/// This determines the set of convertible loops: any usages of IndexVar713/// not explicitly considered convertible by this traversal will be caught by714/// this function.715///716/// Additionally, if the container expression is more complex than just a717/// DeclRefExpr, and some part of it is appears elsewhere in the loop, lower718/// our confidence in the transformation.719///720/// For example, these are not permitted:721/// \code722/// for (int i = 0; i < N; ++i) { printf("arr[%d] = %d", i, arr[i]); }723/// for (vector<int>::iterator i = container.begin(), e = container.end();724/// i != e; ++i)725/// i.insert(0);726/// for (vector<int>::iterator i = container.begin(), e = container.end();727/// i != e; ++i)728/// if (i + 1 != e)729/// printf("%d", *i);730/// \endcode731///732/// And these will raise the risk level:733/// \code734/// int arr[10][20];735/// int l = 5;736/// for (int j = 0; j < 20; ++j)737/// int k = arr[l][j] + l; // using l outside arr[l] is considered risky738/// for (int i = 0; i < obj.getVector().size(); ++i)739/// obj.foo(10); // using `obj` is considered risky740/// \endcode741bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *E) {742 const ValueDecl *TheDecl = E->getDecl();743 if (areSameVariable(IndexVar, TheDecl) ||744 exprReferencesVariable(IndexVar, E) || areSameVariable(EndVar, TheDecl) ||745 exprReferencesVariable(EndVar, E))746 OnlyUsedAsIndex = false;747 if (containsExpr(Context, &DependentExprs, E))748 ConfidenceLevel.lowerTo(Confidence::CL_Risky);749 return true;750}751 752/// If the loop index is captured by a lambda, replace this capture753/// by the range-for loop variable.754///755/// For example:756/// \code757/// for (int i = 0; i < N; ++i) {758/// auto f = [v, i](int k) {759/// printf("%d\n", v[i] + k);760/// };761/// f(v[i]);762/// }763/// \endcode764///765/// Will be replaced by:766/// \code767/// for (auto & elem : v) {768/// auto f = [v, elem](int k) {769/// printf("%d\n", elem + k);770/// };771/// f(elem);772/// }773/// \endcode774bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE,775 const LambdaCapture *C,776 Expr *Init) {777 if (C->capturesVariable()) {778 ValueDecl *VDecl = C->getCapturedVar();779 if (areSameVariable(IndexVar, VDecl)) {780 // FIXME: if the index is captured, it will count as an usage and the781 // alias (if any) won't work, because it is only used in case of having782 // exactly one usage.783 addUsage(Usage(nullptr,784 C->getCaptureKind() == LCK_ByCopy ? Usage::UK_CaptureByCopy785 : Usage::UK_CaptureByRef,786 C->getLocation()));787 }788 if (VDecl->isInitCapture())789 traverseStmtImpl(cast<VarDecl>(VDecl)->getInit());790 }791 return VisitorBase::TraverseLambdaCapture(LE, C, Init);792}793 794/// If we find that another variable is created just to refer to the loop795/// element, note it for reuse as the loop variable.796///797/// See the comments for isAliasDecl.798bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *S) {799 if (!AliasDecl && S->isSingleDecl() &&800 isAliasDecl(Context, S->getSingleDecl(), IndexVar)) {801 AliasDecl = S;802 if (CurrStmtParent) {803 if (isa<IfStmt>(CurrStmtParent) || isa<WhileStmt>(CurrStmtParent) ||804 isa<SwitchStmt>(CurrStmtParent))805 ReplaceWithAliasUse = true;806 else if (isa<ForStmt>(CurrStmtParent)) {807 if (cast<ForStmt>(CurrStmtParent)->getConditionVariableDeclStmt() == S)808 ReplaceWithAliasUse = true;809 else810 // It's assumed S came the for loop's init clause.811 AliasFromForInit = true;812 }813 }814 }815 816 return true;817}818 819bool ForLoopIndexUseVisitor::traverseStmtImpl(Stmt *S) {820 // All this pointer swapping is a mechanism for tracking immediate parentage821 // of Stmts.822 const Stmt *OldNextParent = NextStmtParent;823 CurrStmtParent = NextStmtParent;824 NextStmtParent = S;825 const bool Result = VisitorBase::TraverseStmt(S);826 NextStmtParent = OldNextParent;827 return Result;828}829 830bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) {831 // If this is an initialization expression for a lambda capture, prune the832 // traversal so that we don't end up diagnosing the contained DeclRefExpr as833 // inconsistent usage. No need to record the usage here -- this is done in834 // TraverseLambdaCapture().835 if (const auto *LE = dyn_cast_or_null<LambdaExpr>(NextStmtParent)) {836 // Any child of a LambdaExpr that isn't the body is an initialization837 // expression.838 if (S != LE->getBody()) {839 return true;840 }841 }842 return traverseStmtImpl(S);843}844 845std::string VariableNamer::createIndexName() {846 // FIXME: Add in naming conventions to handle:847 // - How to handle conflicts.848 // - An interactive process for naming.849 std::string IteratorName;850 StringRef ContainerName;851 if (TheContainer)852 ContainerName = TheContainer->getName();853 854 const size_t Len = ContainerName.size();855 if (Len > 1 && ContainerName.ends_with(Style == NS_UpperCase ? "S" : "s")) {856 IteratorName = std::string(ContainerName.substr(0, Len - 1));857 // E.g.: (auto thing : things)858 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())859 return IteratorName;860 }861 862 if (Len > 2 && ContainerName.ends_with(Style == NS_UpperCase ? "S_" : "s_")) {863 IteratorName = std::string(ContainerName.substr(0, Len - 2));864 // E.g.: (auto thing : things_)865 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())866 return IteratorName;867 }868 869 return std::string(OldIndex->getName());870}871 872/// Determines whether or not the name \a Symbol conflicts with873/// language keywords or defined macros. Also checks if the name exists in874/// LoopContext, any of its parent contexts, or any of its child statements.875///876/// We also check to see if the same identifier was generated by this loop877/// converter in a loop nested within SourceStmt.878bool VariableNamer::declarationExists(StringRef Symbol) {879 assert(Context != nullptr && "Expected an ASTContext");880 const IdentifierInfo &Ident = Context->Idents.get(Symbol);881 882 // Check if the symbol is not an identifier (ie. is a keyword or alias).883 if (!isAnyIdentifier(Ident.getTokenID()))884 return true;885 886 // Check for conflicting macro definitions.887 if (Ident.hasMacroDefinition())888 return true;889 890 // Determine if the symbol was generated in a parent context.891 for (const Stmt *S = SourceStmt; S != nullptr; S = ReverseAST->lookup(S)) {892 const StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S);893 if (I != GeneratedDecls->end() && I->second == Symbol)894 return true;895 }896 897 // FIXME: Rather than detecting conflicts at their usages, we should check the898 // parent context.899 // For some reason, lookup() always returns the pair (NULL, NULL) because its900 // StoredDeclsMap is not initialized (i.e. LookupPtr.getInt() is false inside901 // of DeclContext::lookup()). Why is this?902 903 // Finally, determine if the symbol was used in the loop or a child context.904 DeclFinderASTVisitor DeclFinder(std::string(Symbol), GeneratedDecls);905 return DeclFinder.findUsages(SourceStmt);906}907 908} // namespace clang::tidy::modernize909