| 1 |
//===--- LoopConvertUtils.cpp - clang-tidy --------------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "LoopConvertUtils.h" |
| 10 |
#include "clang/Basic/IdentifierTable.h" |
| 11 |
#include "clang/Basic/LLVM.h" |
| 12 |
#include "clang/Basic/Lambda.h" |
| 13 |
#include "clang/Basic/SourceLocation.h" |
| 14 |
#include "clang/Basic/SourceManager.h" |
| 15 |
#include "clang/Basic/TokenKinds.h" |
| 16 |
#include "clang/Lex/Lexer.h" |
| 17 |
#include "llvm/ADT/APSInt.h" |
| 18 |
#include "llvm/ADT/FoldingSet.h" |
| 19 |
#include "llvm/ADT/StringRef.h" |
| 20 |
#include "llvm/Support/Casting.h" |
| 21 |
#include <algorithm> |
| 22 |
#include <cassert> |
| 23 |
#include <cstddef> |
| 24 |
#include <optional> |
| 25 |
#include <string> |
| 26 |
#include <utility> |
| 27 |
|
| 28 |
using namespace clang::ast_matchers; |
| 29 |
|
| 30 |
namespace clang::tidy::modernize { |
| 31 |
|
| 32 |
/// Tracks a stack of parent statements during traversal. |
| 33 |
/// |
| 34 |
/// All this really does is inject push_back() before running |
| 35 |
/// RecursiveASTVisitor::TraverseStmt() and pop_back() afterwards. The Stmt atop |
| 36 |
/// the stack is the parent of the current statement (NULL for the topmost |
| 37 |
/// statement). |
| 38 |
bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) { |
| 39 |
StmtAncestors.insert(std::make_pair(Statement, StmtStack.back())); |
| 40 |
StmtStack.push_back(Statement); |
| 41 |
RecursiveASTVisitor<StmtAncestorASTVisitor>::TraverseStmt(Statement); |
| 42 |
StmtStack.pop_back(); |
| 43 |
return true; |
| 44 |
} |
| 45 |
|
| 46 |
/// Keep track of the DeclStmt associated with each VarDecl. |
| 47 |
/// |
| 48 |
/// Combined with StmtAncestors, this provides roughly the same information as |
| 49 |
/// Scope, as we can map a VarDecl to its DeclStmt, then walk up the parent tree |
| 50 |
/// using StmtAncestors. |
| 51 |
bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Decls) { |
| 52 |
for (const auto *Decl : Decls->decls()) { |
| 53 |
if (const auto *V = dyn_cast<VarDecl>(Decl)) |
| 54 |
DeclParents.insert(std::make_pair(V, Decls)); |
| 55 |
} |
| 56 |
return true; |
| 57 |
} |
| 58 |
|
| 59 |
/// record the DeclRefExpr as part of the parent expression. |
| 60 |
bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) { |
| 61 |
Components.push_back(E); |
| 62 |
return true; |
| 63 |
} |
| 64 |
|
| 65 |
/// record the MemberExpr as part of the parent expression. |
| 66 |
bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) { |
| 67 |
Components.push_back(Member); |
| 68 |
return true; |
| 69 |
} |
| 70 |
|
| 71 |
/// Forward any DeclRefExprs to a check on the referenced variable |
| 72 |
/// declaration. |
| 73 |
bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) { |
| 74 |
if (auto *V = dyn_cast_or_null<VarDecl>(DeclRef->getDecl())) |
| 75 |
return VisitVarDecl(V); |
| 76 |
return true; |
| 77 |
} |
| 78 |
|
| 79 |
/// Determine if any this variable is declared inside the ContainingStmt. |
| 80 |
bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) { |
| 81 |
const Stmt *Curr = DeclParents->lookup(V); |
| 82 |
// First, see if the variable was declared within an inner scope of the loop. |
| 83 |
while (Curr != nullptr) { |
| 84 |
if (Curr == ContainingStmt) { |
| 85 |
DependsOnInsideVariable = true; |
| 86 |
return false; |
| 87 |
} |
| 88 |
Curr = StmtParents->lookup(Curr); |
| 89 |
} |
| 90 |
|
| 91 |
// Next, check if the variable was removed from existence by an earlier |
| 92 |
// iteration. |
| 93 |
for (const auto &I : *ReplacedVars) { |
| 94 |
if (I.second == V) { |
| 95 |
DependsOnInsideVariable = true; |
| 96 |
return false; |
| 97 |
} |
| 98 |
} |
| 99 |
return true; |
| 100 |
} |
| 101 |
|
| 102 |
/// If we already created a variable for TheLoop, check to make sure |
| 103 |
/// that the name was not already taken. |
| 104 |
bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) { |
| 105 |
StmtGeneratedVarNameMap::const_iterator I = 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. |
| 115 |
bool 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 the |
| 125 |
/// referenced declaration. |
| 126 |
bool 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. |
| 134 |
bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) { |
| 135 |
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 being |
| 143 |
// referenced in the body of the loop, the above getAsString() will return the |
| 144 |
// 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 the |
| 155 |
/// explicit initialization expression, returning it is found. |
| 156 |
/// |
| 157 |
/// The main idea is that given |
| 158 |
/// vector<int> v; |
| 159 |
/// we consider either of these initializations |
| 160 |
/// 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 do |
| 164 |
/// not include |
| 165 |
/// vector<int>::iterator it; |
| 166 |
/// vector<int>::iterator it(v.begin(), 0); // if this constructor existed |
| 167 |
/// as being initialized from `v.begin()` |
| 168 |
const 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 class |
| 174 |
// and deferred constructors can take more. |
| 175 |
if (ConstructExpr->getNumArgs() != 1 || |
| 176 |
ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_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 const |
| 184 |
// 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. |
| 192 |
bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second) { |
| 193 |
if (!First || !Second) |
| 194 |
return false; |
| 195 |
|
| 196 |
llvm::FoldingSetNodeID FirstID, SecondID; |
| 197 |
First->Profile(FirstID, *Context, true); |
| 198 |
Second->Profile(SecondID, *Context, true); |
| 199 |
return FirstID == SecondID; |
| 200 |
} |
| 201 |
|
| 202 |
/// Returns the DeclRefExpr represented by E, or NULL if there isn't one. |
| 203 |
const DeclRefExpr *getDeclRef(const Expr *E) { |
| 204 |
return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()); |
| 205 |
} |
| 206 |
|
| 207 |
/// Returns true when two ValueDecls are the same variable. |
| 208 |
bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) { |
| 209 |
return First && Second && |
| 210 |
First->getCanonicalDecl() == Second->getCanonicalDecl(); |
| 211 |
} |
| 212 |
|
| 213 |
/// Determines if an expression is a declaration reference to a |
| 214 |
/// particular variable. |
| 215 |
static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) { |
| 216 |
if (!Target || !E) |
| 217 |
return false; |
| 218 |
const DeclRefExpr *Decl = getDeclRef(E); |
| 219 |
return Decl && areSameVariable(Target, Decl->getDecl()); |
| 220 |
} |
| 221 |
|
| 222 |
/// If the expression is a dereference or call to operator*(), return the |
| 223 |
/// operand. Otherwise, return NULL. |
| 224 |
static const Expr *getDereferenceOperand(const Expr *E) { |
| 225 |
if (const auto *Uop = dyn_cast<UnaryOperator>(E)) |
| 226 |
return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : nullptr; |
| 227 |
|
| 228 |
if (const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(E)) { |
| 229 |
return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 |
| 230 |
? OpCall->getArg(0) |
| 231 |
: nullptr; |
| 232 |
} |
| 233 |
|
| 234 |
return nullptr; |
| 235 |
} |
| 236 |
|
| 237 |
/// Returns true when the Container contains an Expr equivalent to E. |
| 238 |
template <typename ContainerT> |
| 239 |
static bool containsExpr(ASTContext *Context, const ContainerT *Container, |
| 240 |
const Expr *E) { |
| 241 |
llvm::FoldingSetNodeID ID; |
| 242 |
E->Profile(ID, *Context, true); |
| 243 |
for (const auto &I : *Container) { |
| 244 |
if (ID == I.second) |
| 245 |
return true; |
| 246 |
} |
| 247 |
return false; |
| 248 |
} |
| 249 |
|
| 250 |
/// Returns true when the index expression is a declaration reference to |
| 251 |
/// IndexVar. |
| 252 |
/// |
| 253 |
/// If the index variable is `index`, this function returns true on |
| 254 |
/// arrayExpression[index]; |
| 255 |
/// containerExpression[index]; |
| 256 |
/// but not |
| 257 |
/// containerExpression[notIndex]; |
| 258 |
static bool isIndexInSubscriptExpr(const Expr *IndexExpr, |
| 259 |
const VarDecl *IndexVar) { |
| 260 |
const DeclRefExpr *Idx = getDeclRef(IndexExpr); |
| 261 |
return Idx && Idx->getType()->isIntegerType() && |
| 262 |
areSameVariable(IndexVar, Idx->getDecl()); |
| 263 |
} |
| 264 |
|
| 265 |
/// Returns true when the index expression is a declaration reference to |
| 266 |
/// IndexVar, Obj is the same expression as SourceExpr after all parens and |
| 267 |
/// implicit casts are stripped off. |
| 268 |
/// |
| 269 |
/// If PermitDeref is true, IndexExpression may |
| 270 |
/// be a dereference (overloaded or builtin operator*). |
| 271 |
/// |
| 272 |
/// This function is intended for array-like containers, as it makes sure that |
| 273 |
/// both the container and the index match. |
| 274 |
/// If the loop has index variable `index` and iterates over `container`, then |
| 275 |
/// isIndexInSubscriptExpr returns true for |
| 276 |
/// \code |
| 277 |
/// container[index] |
| 278 |
/// container.at(index) |
| 279 |
/// container->at(index) |
| 280 |
/// \endcode |
| 281 |
/// but not for |
| 282 |
/// \code |
| 283 |
/// container[notIndex] |
| 284 |
/// notContainer[index] |
| 285 |
/// \endcode |
| 286 |
/// If PermitDeref is true, then isIndexInSubscriptExpr additionally returns |
| 287 |
/// true on these expressions: |
| 288 |
/// \code |
| 289 |
/// (*container)[index] |
| 290 |
/// (*container).at(index) |
| 291 |
/// \endcode |
| 292 |
static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr, |
| 293 |
const VarDecl *IndexVar, const Expr *Obj, |
| 294 |
const Expr *SourceExpr, bool PermitDeref) { |
| 295 |
if (!SourceExpr || !Obj || !isIndexInSubscriptExpr(IndexExpr, IndexVar)) |
| 296 |
return false; |
| 297 |
|
| 298 |
if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(), |
| 299 |
Obj->IgnoreParenImpCasts())) |
| 300 |
return true; |
| 301 |
|
| 302 |
if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts())) |
| 303 |
if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(), |
| 304 |
InnerObj->IgnoreParenImpCasts())) |
| 305 |
return true; |
| 306 |
|
| 307 |
return false; |
| 308 |
} |
| 309 |
|
| 310 |
/// Returns true when Opcall is a call a one-parameter dereference of |
| 311 |
/// IndexVar. |
| 312 |
/// |
| 313 |
/// For example, if the index variable is `index`, returns true for |
| 314 |
/// *index |
| 315 |
/// but not |
| 316 |
/// index |
| 317 |
/// *notIndex |
| 318 |
static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall, |
| 319 |
const VarDecl *IndexVar) { |
| 320 |
return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 && |
| 321 |
exprReferencesVariable(IndexVar, OpCall->getArg(0)); |
| 322 |
} |
| 323 |
|
| 324 |
/// Returns true when Uop is a dereference of IndexVar. |
| 325 |
/// |
| 326 |
/// For example, if the index variable is `index`, returns true for |
| 327 |
/// *index |
| 328 |
/// but not |
| 329 |
/// index |
| 330 |
/// *notIndex |
| 331 |
static bool isDereferenceOfUop(const UnaryOperator *Uop, |
| 332 |
const VarDecl *IndexVar) { |
| 333 |
return Uop->getOpcode() == UO_Deref && |
| 334 |
exprReferencesVariable(IndexVar, Uop->getSubExpr()); |
| 335 |
} |
| 336 |
|
| 337 |
/// Determines whether the given Decl defines a variable initialized to |
| 338 |
/// the loop object. |
| 339 |
/// |
| 340 |
/// This is intended to find cases such as |
| 341 |
/// \code |
| 342 |
/// for (int i = 0; i < arraySize(arr); ++i) { |
| 343 |
/// T t = arr[i]; |
| 344 |
/// // use t, do not use i |
| 345 |
/// } |
| 346 |
/// \endcode |
| 347 |
/// and |
| 348 |
/// \code |
| 349 |
/// for (iterator i = container.begin(), e = container.end(); i != e; ++i) { |
| 350 |
/// T t = *i; |
| 351 |
/// // use t, do not use i |
| 352 |
/// } |
| 353 |
/// \endcode |
| 354 |
static bool isAliasDecl(ASTContext *Context, const Decl *TheDecl, |
| 355 |
const VarDecl *IndexVar) { |
| 356 |
const auto *VDecl = dyn_cast<VarDecl>(TheDecl); |
| 357 |
if (!VDecl) |
| 358 |
return false; |
| 359 |
if (!VDecl->hasInit()) |
| 360 |
return false; |
| 361 |
|
| 362 |
bool OnlyCasts = true; |
| 363 |
const Expr *Init = VDecl->getInit()->IgnoreParenImpCasts(); |
| 364 |
if (isa_and_nonnull<CXXConstructExpr>(Init)) { |
| 365 |
Init = digThroughConstructorsConversions(Init); |
| 366 |
OnlyCasts = false; |
| 367 |
} |
| 368 |
if (!Init) |
| 369 |
return false; |
| 370 |
|
| 371 |
// Check that the declared type is the same as (or a reference to) the |
| 372 |
// container type. |
| 373 |
if (!OnlyCasts) { |
| 374 |
QualType InitType = Init->getType(); |
| 375 |
QualType DeclarationType = VDecl->getType(); |
| 376 |
if (!DeclarationType.isNull() && DeclarationType->isReferenceType()) |
| 377 |
DeclarationType = DeclarationType.getNonReferenceType(); |
| 378 |
|
| 379 |
if (InitType.isNull() || DeclarationType.isNull() || |
| 380 |
!Context->hasSameUnqualifiedType(DeclarationType, InitType)) |
| 381 |
return false; |
| 382 |
} |
| 383 |
|
| 384 |
switch (Init->getStmtClass()) { |
| 385 |
case Stmt::ArraySubscriptExprClass: { |
| 386 |
const auto *E = cast<ArraySubscriptExpr>(Init); |
| 387 |
// We don't really care which array is used here. We check to make sure |
| 388 |
// it was the correct one later, since the AST will traverse it next. |
| 389 |
return isIndexInSubscriptExpr(E->getIdx(), IndexVar); |
| 390 |
} |
| 391 |
|
| 392 |
case Stmt::UnaryOperatorClass: |
| 393 |
return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar); |
| 394 |
|
| 395 |
case Stmt::CXXOperatorCallExprClass: { |
| 396 |
const auto *OpCall = cast<CXXOperatorCallExpr>(Init); |
| 397 |
if (OpCall->getOperator() == OO_Star) |
| 398 |
return isDereferenceOfOpCall(OpCall, IndexVar); |
| 399 |
if (OpCall->getOperator() == OO_Subscript) { |
| 400 |
return OpCall->getNumArgs() == 2 && |
| 401 |
isIndexInSubscriptExpr(OpCall->getArg(1), IndexVar); |
| 402 |
} |
| 403 |
break; |
| 404 |
} |
| 405 |
|
| 406 |
case Stmt::CXXMemberCallExprClass: { |
| 407 |
const auto *MemCall = cast<CXXMemberCallExpr>(Init); |
| 408 |
// This check is needed because getMethodDecl can return nullptr if the |
| 409 |
// callee is a member function pointer. |
| 410 |
const auto *MDecl = MemCall->getMethodDecl(); |
| 411 |
if (MDecl && !isa<CXXConversionDecl>(MDecl) && |
| 412 |
MDecl->getNameAsString() == "at" && MemCall->getNumArgs() == 1) { |
| 413 |
return isIndexInSubscriptExpr(MemCall->getArg(0), IndexVar); |
| 414 |
} |
| 415 |
return false; |
| 416 |
} |
| 417 |
|
| 418 |
default: |
| 419 |
break; |
| 420 |
} |
| 421 |
return false; |
| 422 |
} |
| 423 |
|
| 424 |
/// Determines whether the bound of a for loop condition expression is |
| 425 |
/// the same as the statically computable size of ArrayType. |
| 426 |
/// |
| 427 |
/// Given |
| 428 |
/// \code |
| 429 |
/// const int N = 5; |
| 430 |
/// int arr[N]; |
| 431 |
/// \endcode |
| 432 |
/// This is intended to permit |
| 433 |
/// \code |
| 434 |
/// for (int i = 0; i < N; ++i) { /* use arr[i] */ } |
| 435 |
/// for (int i = 0; i < arraysize(arr); ++i) { /* use arr[i] */ } |
| 436 |
/// \endcode |
| 437 |
static bool arrayMatchesBoundExpr(ASTContext *Context, |
| 438 |
const QualType &ArrayType, |
| 439 |
const Expr *ConditionExpr) { |
| 440 |
if (!ConditionExpr || ConditionExpr->isValueDependent()) |
| 441 |
return false; |
| 442 |
const ConstantArrayType *ConstType = |
| 443 |
Context->getAsConstantArrayType(ArrayType); |
| 444 |
if (!ConstType) |
| 445 |
return false; |
| 446 |
std::optional<llvm::APSInt> ConditionSize = |
| 447 |
ConditionExpr->getIntegerConstantExpr(*Context); |
| 448 |
if (!ConditionSize) |
| 449 |
return false; |
| 450 |
llvm::APSInt ArraySize(ConstType->getSize()); |
| 451 |
return llvm::APSInt::isSameValue(*ConditionSize, ArraySize); |
| 452 |
} |
| 453 |
|
| 454 |
ForLoopIndexUseVisitor::ForLoopIndexUseVisitor(ASTContext *Context, |
| 455 |
const VarDecl *IndexVar, |
| 456 |
const VarDecl *EndVar, |
| 457 |
const Expr *ContainerExpr, |
| 458 |
const Expr *ArrayBoundExpr, |
| 459 |
bool ContainerNeedsDereference) |
| 460 |
: Context(Context), IndexVar(IndexVar), EndVar(EndVar), |
| 461 |
ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr), |
| 462 |
ContainerNeedsDereference(ContainerNeedsDereference), |
| 463 |
OnlyUsedAsIndex(true), AliasDecl(nullptr), |
| 464 |
ConfidenceLevel(Confidence::CL_Safe), NextStmtParent(nullptr), |
| 465 |
CurrStmtParent(nullptr), ReplaceWithAliasUse(false), |
| 466 |
AliasFromForInit(false) { |
| 467 |
if (ContainerExpr) |
| 468 |
addComponent(ContainerExpr); |
| 469 |
} |
| 470 |
|
| 471 |
bool ForLoopIndexUseVisitor::findAndVerifyUsages(const Stmt *Body) { |
| 472 |
TraverseStmt(const_cast<Stmt *>(Body)); |
| 473 |
return OnlyUsedAsIndex && ContainerExpr; |
| 474 |
} |
| 475 |
|
| 476 |
void ForLoopIndexUseVisitor::addComponents(const ComponentVector &Components) { |
| 477 |
// FIXME: add sort(on ID)+unique to avoid extra work. |
| 478 |
for (const auto &I : Components) |
| 479 |
addComponent(I); |
| 480 |
} |
| 481 |
|
| 482 |
void ForLoopIndexUseVisitor::addComponent(const Expr *E) { |
| 483 |
llvm::FoldingSetNodeID ID; |
| 484 |
const Expr *Node = E->IgnoreParenImpCasts(); |
| 485 |
Node->Profile(ID, *Context, true); |
| 486 |
DependentExprs.push_back(std::make_pair(Node, ID)); |
| 487 |
} |
| 488 |
|
| 489 |
void ForLoopIndexUseVisitor::addUsage(const Usage &U) { |
| 490 |
SourceLocation Begin = U.Range.getBegin(); |
| 491 |
if (Begin.isMacroID()) |
| 492 |
Begin = Context->getSourceManager().getSpellingLoc(Begin); |
| 493 |
|
| 494 |
if (UsageLocations.insert(Begin).second) |
| 495 |
Usages.push_back(U); |
| 496 |
} |
| 497 |
|
| 498 |
/// If the unary operator is a dereference of IndexVar, include it |
| 499 |
/// as a valid usage and prune the traversal. |
| 500 |
/// |
| 501 |
/// For example, if container.begin() and container.end() both return pointers |
| 502 |
/// to int, this makes sure that the initialization for `k` is not counted as an |
| 503 |
/// unconvertible use of the iterator `i`. |
| 504 |
/// \code |
| 505 |
/// for (int *i = container.begin(), *e = container.end(); i != e; ++i) { |
| 506 |
/// int k = *i + 2; |
| 507 |
/// } |
| 508 |
/// \endcode |
| 509 |
bool ForLoopIndexUseVisitor::TraverseUnaryOperator(UnaryOperator *Uop) { |
| 510 |
// If we dereference an iterator that's actually a pointer, count the |
| 511 |
// occurrence. |
| 512 |
if (isDereferenceOfUop(Uop, IndexVar)) { |
| 513 |
addUsage(Usage(Uop)); |
| 514 |
return true; |
| 515 |
} |
| 516 |
|
| 517 |
return VisitorBase::TraverseUnaryOperator(Uop); |
| 518 |
} |
| 519 |
|
| 520 |
/// If the member expression is operator-> (overloaded or not) on |
| 521 |
/// IndexVar, include it as a valid usage and prune the traversal. |
| 522 |
/// |
| 523 |
/// For example, given |
| 524 |
/// \code |
| 525 |
/// struct Foo { int bar(); int x; }; |
| 526 |
/// vector<Foo> v; |
| 527 |
/// \endcode |
| 528 |
/// the following uses will be considered convertible: |
| 529 |
/// \code |
| 530 |
/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) { |
| 531 |
/// int b = i->bar(); |
| 532 |
/// int k = i->x + 1; |
| 533 |
/// } |
| 534 |
/// \endcode |
| 535 |
/// though |
| 536 |
/// \code |
| 537 |
/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) { |
| 538 |
/// int k = i.insert(1); |
| 539 |
/// } |
| 540 |
/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) { |
| 541 |
/// int b = e->bar(); |
| 542 |
/// } |
| 543 |
/// \endcode |
| 544 |
/// will not. |
| 545 |
bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) { |
| 546 |
const Expr *Base = Member->getBase(); |
| 547 |
const DeclRefExpr *Obj = getDeclRef(Base); |
| 548 |
const Expr *ResultExpr = Member; |
| 549 |
QualType ExprType; |
| 550 |
if (const auto *Call = |
| 551 |
dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) { |
| 552 |
// If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then |
| 553 |
// the MemberExpr does not have the expression we want. We therefore catch |
| 554 |
// that instance here. |
| 555 |
// For example, if vector<Foo>::iterator defines operator->(), then the |
| 556 |
// example `i->bar()` at the top of this function is a CXXMemberCallExpr |
| 557 |
// referring to `i->` as the member function called. We want just `i`, so |
| 558 |
// we take the argument to operator->() as the base object. |
| 559 |
if (Call->getOperator() == OO_Arrow) { |
| 560 |
assert(Call->getNumArgs() == 1 && |
| 561 |
"Operator-> takes more than one argument"); |
| 562 |
Obj = getDeclRef(Call->getArg(0)); |
| 563 |
ResultExpr = Obj; |
| 564 |
ExprType = Call->getCallReturnType(*Context); |
| 565 |
} |
| 566 |
} |
| 567 |
|
| 568 |
if (Obj && exprReferencesVariable(IndexVar, Obj)) { |
| 569 |
// Member calls on the iterator with '.' are not allowed. |
| 570 |
if (!Member->isArrow()) { |
| 571 |
OnlyUsedAsIndex = false; |
| 572 |
return true; |
| 573 |
} |
| 574 |
|
| 575 |
if (ExprType.isNull()) |
| 576 |
ExprType = Obj->getType(); |
| 577 |
|
| 578 |
if (!ExprType->isPointerType()) |
| 579 |
return false; |
| 580 |
|
| 581 |
// FIXME: This works around not having the location of the arrow operator. |
| 582 |
// Consider adding OperatorLoc to MemberExpr? |
| 583 |
SourceLocation ArrowLoc = Lexer::getLocForEndOfToken( |
| 584 |
Base->getExprLoc(), 0, Context->getSourceManager(), |
| 585 |
Context->getLangOpts()); |
| 586 |
// If something complicated is happening (i.e. the next token isn't an |
| 587 |
// arrow), give up on making this work. |
| 588 |
if (ArrowLoc.isValid()) { |
| 589 |
addUsage(Usage(ResultExpr, Usage::UK_MemberThroughArrow, |
| 590 |
SourceRange(Base->getExprLoc(), ArrowLoc))); |
| 591 |
return true; |
| 592 |
} |
| 593 |
} |
| 594 |
return VisitorBase::TraverseMemberExpr(Member); |
| 595 |
} |
| 596 |
|
| 597 |
/// If a member function call is the at() accessor on the container with |
| 598 |
/// IndexVar as the single argument, include it as a valid usage and prune |
| 599 |
/// the traversal. |
| 600 |
/// |
| 601 |
/// Member calls on other objects will not be permitted. |
| 602 |
/// Calls on the iterator object are not permitted, unless done through |
| 603 |
/// operator->(). The one exception is allowing vector::at() for pseudoarrays. |
| 604 |
bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr( |
| 605 |
CXXMemberCallExpr *MemberCall) { |
| 606 |
auto *Member = |
| 607 |
dyn_cast<MemberExpr>(MemberCall->getCallee()->IgnoreParenImpCasts()); |
| 608 |
if (!Member) |
| 609 |
return VisitorBase::TraverseCXXMemberCallExpr(MemberCall); |
| 610 |
|
| 611 |
// We specifically allow an accessor named "at" to let STL in, though |
| 612 |
// this is restricted to pseudo-arrays by requiring a single, integer |
| 613 |
// argument. |
| 614 |
const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier(); |
| 615 |
if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) { |
| 616 |
if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar, |
| 617 |
Member->getBase(), ContainerExpr, |
| 618 |
ContainerNeedsDereference)) { |
| 619 |
addUsage(Usage(MemberCall)); |
| 620 |
return true; |
| 621 |
} |
| 622 |
} |
| 623 |
|
| 624 |
if (containsExpr(Context, &DependentExprs, Member->getBase())) |
| 625 |
ConfidenceLevel.lowerTo(Confidence::CL_Risky); |
| 626 |
|
| 627 |
return VisitorBase::TraverseCXXMemberCallExpr(MemberCall); |
| 628 |
} |
| 629 |
|
| 630 |
/// If an overloaded operator call is a dereference of IndexVar or |
| 631 |
/// a subscript of the container with IndexVar as the single argument, |
| 632 |
/// include it as a valid usage and prune the traversal. |
| 633 |
/// |
| 634 |
/// For example, given |
| 635 |
/// \code |
| 636 |
/// struct Foo { int bar(); int x; }; |
| 637 |
/// vector<Foo> v; |
| 638 |
/// void f(Foo); |
| 639 |
/// \endcode |
| 640 |
/// the following uses will be considered convertible: |
| 641 |
/// \code |
| 642 |
/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) { |
| 643 |
/// f(*i); |
| 644 |
/// } |
| 645 |
/// for (int i = 0; i < v.size(); ++i) { |
| 646 |
/// int i = v[i] + 1; |
| 647 |
/// } |
| 648 |
/// \endcode |
| 649 |
bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr( |
| 650 |
CXXOperatorCallExpr *OpCall) { |
| 651 |
switch (OpCall->getOperator()) { |
| 652 |
case OO_Star: |
| 653 |
if (isDereferenceOfOpCall(OpCall, IndexVar)) { |
| 654 |
addUsage(Usage(OpCall)); |
| 655 |
return true; |
| 656 |
} |
| 657 |
break; |
| 658 |
|
| 659 |
case OO_Subscript: |
| 660 |
if (OpCall->getNumArgs() != 2) |
| 661 |
break; |
| 662 |
if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar, |
| 663 |
OpCall->getArg(0), ContainerExpr, |
| 664 |
ContainerNeedsDereference)) { |
| 665 |
addUsage(Usage(OpCall)); |
| 666 |
return true; |
| 667 |
} |
| 668 |
break; |
| 669 |
|
| 670 |
default: |
| 671 |
break; |
| 672 |
} |
| 673 |
return VisitorBase::TraverseCXXOperatorCallExpr(OpCall); |
| 674 |
} |
| 675 |
|
| 676 |
/// If we encounter an array with IndexVar as the index of an |
| 677 |
/// ArraySubscriptExpression, note it as a consistent usage and prune the |
| 678 |
/// AST traversal. |
| 679 |
/// |
| 680 |
/// For example, given |
| 681 |
/// \code |
| 682 |
/// const int N = 5; |
| 683 |
/// int arr[N]; |
| 684 |
/// \endcode |
| 685 |
/// This is intended to permit |
| 686 |
/// \code |
| 687 |
/// for (int i = 0; i < N; ++i) { /* use arr[i] */ } |
| 688 |
/// \endcode |
| 689 |
/// but not |
| 690 |
/// \code |
| 691 |
/// for (int i = 0; i < N; ++i) { /* use notArr[i] */ } |
| 692 |
/// \endcode |
| 693 |
/// and further checking needs to be done later to ensure that exactly one array |
| 694 |
/// is referenced. |
| 695 |
bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(ArraySubscriptExpr *E) { |
| 696 |
Expr *Arr = E->getBase(); |
| 697 |
if (!isIndexInSubscriptExpr(E->getIdx(), IndexVar)) |
| 698 |
return VisitorBase::TraverseArraySubscriptExpr(E); |
| 699 |
|
| 700 |
if ((ContainerExpr && |
| 701 |
!areSameExpr(Context, Arr->IgnoreParenImpCasts(), |
| 702 |
ContainerExpr->IgnoreParenImpCasts())) || |
| 703 |
!arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(), |
| 704 |
ArrayBoundExpr)) { |
| 705 |
// If we have already discovered the array being indexed and this isn't it |
| 706 |
// or this array doesn't match, mark this loop as unconvertible. |
| 707 |
OnlyUsedAsIndex = false; |
| 708 |
return VisitorBase::TraverseArraySubscriptExpr(E); |
| 709 |
} |
| 710 |
|
| 711 |
if (!ContainerExpr) |
| 712 |
ContainerExpr = Arr; |
| 713 |
|
| 714 |
addUsage(Usage(E)); |
| 715 |
return true; |
| 716 |
} |
| 717 |
|
| 718 |
/// If we encounter a reference to IndexVar in an unpruned branch of the |
| 719 |
/// traversal, mark this loop as unconvertible. |
| 720 |
/// |
| 721 |
/// This determines the set of convertible loops: any usages of IndexVar |
| 722 |
/// not explicitly considered convertible by this traversal will be caught by |
| 723 |
/// this function. |
| 724 |
/// |
| 725 |
/// Additionally, if the container expression is more complex than just a |
| 726 |
/// DeclRefExpr, and some part of it is appears elsewhere in the loop, lower |
| 727 |
/// our confidence in the transformation. |
| 728 |
/// |
| 729 |
/// For example, these are not permitted: |
| 730 |
/// \code |
| 731 |
/// for (int i = 0; i < N; ++i) { printf("arr[%d] = %d", i, arr[i]); } |
| 732 |
/// for (vector<int>::iterator i = container.begin(), e = container.end(); |
| 733 |
/// i != e; ++i) |
| 734 |
/// i.insert(0); |
| 735 |
/// for (vector<int>::iterator i = container.begin(), e = container.end(); |
| 736 |
/// i != e; ++i) |
| 737 |
/// if (i + 1 != e) |
| 738 |
/// printf("%d", *i); |
| 739 |
/// \endcode |
| 740 |
/// |
| 741 |
/// And these will raise the risk level: |
| 742 |
/// \code |
| 743 |
/// int arr[10][20]; |
| 744 |
/// int l = 5; |
| 745 |
/// for (int j = 0; j < 20; ++j) |
| 746 |
/// int k = arr[l][j] + l; // using l outside arr[l] is considered risky |
| 747 |
/// for (int i = 0; i < obj.getVector().size(); ++i) |
| 748 |
/// obj.foo(10); // using `obj` is considered risky |
| 749 |
/// \endcode |
| 750 |
bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *E) { |
| 751 |
const ValueDecl *TheDecl = E->getDecl(); |
| 752 |
if (areSameVariable(IndexVar, TheDecl) || |
| 753 |
exprReferencesVariable(IndexVar, E) || areSameVariable(EndVar, TheDecl) || |
| 754 |
exprReferencesVariable(EndVar, E)) |
| 755 |
OnlyUsedAsIndex = false; |
| 756 |
if (containsExpr(Context, &DependentExprs, E)) |
| 757 |
ConfidenceLevel.lowerTo(Confidence::CL_Risky); |
| 758 |
return true; |
| 759 |
} |
| 760 |
|
| 761 |
/// If the loop index is captured by a lambda, replace this capture |
| 762 |
/// by the range-for loop variable. |
| 763 |
/// |
| 764 |
/// For example: |
| 765 |
/// \code |
| 766 |
/// for (int i = 0; i < N; ++i) { |
| 767 |
/// auto f = [v, i](int k) { |
| 768 |
/// printf("%d\n", v[i] + k); |
| 769 |
/// }; |
| 770 |
/// f(v[i]); |
| 771 |
/// } |
| 772 |
/// \endcode |
| 773 |
/// |
| 774 |
/// Will be replaced by: |
| 775 |
/// \code |
| 776 |
/// for (auto & elem : v) { |
| 777 |
/// auto f = [v, elem](int k) { |
| 778 |
/// printf("%d\n", elem + k); |
| 779 |
/// }; |
| 780 |
/// f(elem); |
| 781 |
/// } |
| 782 |
/// \endcode |
| 783 |
bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE, |
| 784 |
const LambdaCapture *C, |
| 785 |
Expr *Init) { |
| 786 |
if (C->capturesVariable()) { |
| 787 |
const ValueDecl *VDecl = C->getCapturedVar(); |
| 788 |
if (areSameVariable(IndexVar, VDecl)) { |
| 789 |
// FIXME: if the index is captured, it will count as an usage and the |
| 790 |
// alias (if any) won't work, because it is only used in case of having |
| 791 |
// exactly one usage. |
| 792 |
addUsage(Usage(nullptr, |
| 793 |
C->getCaptureKind() == LCK_ByCopy ? Usage::UK_CaptureByCopy |
| 794 |
: Usage::UK_CaptureByRef, |
| 795 |
C->getLocation())); |
| 796 |
} |
| 797 |
} |
| 798 |
return VisitorBase::TraverseLambdaCapture(LE, C, Init); |
| 799 |
} |
| 800 |
|
| 801 |
/// If we find that another variable is created just to refer to the loop |
| 802 |
/// element, note it for reuse as the loop variable. |
| 803 |
/// |
| 804 |
/// See the comments for isAliasDecl. |
| 805 |
bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *S) { |
| 806 |
if (!AliasDecl && S->isSingleDecl() && |
| 807 |
isAliasDecl(Context, S->getSingleDecl(), IndexVar)) { |
| 808 |
AliasDecl = S; |
| 809 |
if (CurrStmtParent) { |
| 810 |
if (isa<IfStmt>(CurrStmtParent) || isa<WhileStmt>(CurrStmtParent) || |
| 811 |
isa<SwitchStmt>(CurrStmtParent)) |
| 812 |
ReplaceWithAliasUse = true; |
| 813 |
else if (isa<ForStmt>(CurrStmtParent)) { |
| 814 |
if (cast<ForStmt>(CurrStmtParent)->getConditionVariableDeclStmt() == S) |
| 815 |
ReplaceWithAliasUse = true; |
| 816 |
else |
| 817 |
// It's assumed S came the for loop's init clause. |
| 818 |
AliasFromForInit = true; |
| 819 |
} |
| 820 |
} |
| 821 |
} |
| 822 |
|
| 823 |
return true; |
| 824 |
} |
| 825 |
|
| 826 |
bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) { |
| 827 |
// If this is an initialization expression for a lambda capture, prune the |
| 828 |
// traversal so that we don't end up diagnosing the contained DeclRefExpr as |
| 829 |
// inconsistent usage. No need to record the usage here -- this is done in |
| 830 |
// TraverseLambdaCapture(). |
| 831 |
if (const auto *LE = dyn_cast_or_null<LambdaExpr>(NextStmtParent)) { |
| 832 |
// Any child of a LambdaExpr that isn't the body is an initialization |
| 833 |
// expression. |
| 834 |
if (S != LE->getBody()) { |
| 835 |
return true; |
| 836 |
} |
| 837 |
} |
| 838 |
|
| 839 |
// All this pointer swapping is a mechanism for tracking immediate parentage |
| 840 |
// of Stmts. |
| 841 |
const Stmt *OldNextParent = NextStmtParent; |
| 842 |
CurrStmtParent = NextStmtParent; |
| 843 |
NextStmtParent = S; |
| 844 |
bool Result = VisitorBase::TraverseStmt(S); |
| 845 |
NextStmtParent = OldNextParent; |
| 846 |
return Result; |
| 847 |
} |
| 848 |
|
| 849 |
std::string VariableNamer::createIndexName() { |
| 850 |
// FIXME: Add in naming conventions to handle: |
| 851 |
// - How to handle conflicts. |
| 852 |
// - An interactive process for naming. |
| 853 |
std::string IteratorName; |
| 854 |
StringRef ContainerName; |
| 855 |
if (TheContainer) |
| 856 |
ContainerName = TheContainer->getName(); |
| 857 |
|
| 858 |
size_t Len = ContainerName.size(); |
| 859 |
if (Len > 1 && ContainerName.endswith(Style == NS_UpperCase ? "S" : "s")) { |
| 860 |
IteratorName = std::string(ContainerName.substr(0, Len - 1)); |
| 861 |
// E.g.: (auto thing : things) |
| 862 |
if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName()) |
| 863 |
return IteratorName; |
| 864 |
} |
| 865 |
|
| 866 |
if (Len > 2 && ContainerName.endswith(Style == NS_UpperCase ? "S_" : "s_")) { |
| 867 |
IteratorName = std::string(ContainerName.substr(0, Len - 2)); |
| 868 |
// E.g.: (auto thing : things_) |
| 869 |
if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName()) |
| 870 |
return IteratorName; |
| 871 |
} |
| 872 |
|
| 873 |
return std::string(OldIndex->getName()); |
| 874 |
} |
| 875 |
|
| 876 |
/// Determines whether or not the name \a Symbol conflicts with |
| 877 |
/// language keywords or defined macros. Also checks if the name exists in |
| 878 |
/// LoopContext, any of its parent contexts, or any of its child statements. |
| 879 |
/// |
| 880 |
/// We also check to see if the same identifier was generated by this loop |
| 881 |
/// converter in a loop nested within SourceStmt. |
| 882 |
bool VariableNamer::declarationExists(StringRef Symbol) { |
| 883 |
assert(Context != nullptr && "Expected an ASTContext"); |
| 884 |
IdentifierInfo &Ident = Context->Idents.get(Symbol); |
| 885 |
|
| 886 |
// Check if the symbol is not an identifier (ie. is a keyword or alias). |
| 887 |
if (!isAnyIdentifier(Ident.getTokenID())) |
| 888 |
return true; |
| 889 |
|
| 890 |
// Check for conflicting macro definitions. |
| 891 |
if (Ident.hasMacroDefinition()) |
| 892 |
return true; |
| 893 |
|
| 894 |
// Determine if the symbol was generated in a parent context. |
| 895 |
for (const Stmt *S = SourceStmt; S != nullptr; S = ReverseAST->lookup(S)) { |
| 896 |
StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S); |
| 897 |
if (I != GeneratedDecls->end() && I->second == Symbol) |
| 898 |
return true; |
| 899 |
} |
| 900 |
|
| 901 |
// FIXME: Rather than detecting conflicts at their usages, we should check the |
| 902 |
// parent context. |
| 903 |
// For some reason, lookup() always returns the pair (NULL, NULL) because its |
| 904 |
// StoredDeclsMap is not initialized (i.e. LookupPtr.getInt() is false inside |
| 905 |
// of DeclContext::lookup()). Why is this? |
| 906 |
|
| 907 |
// Finally, determine if the symbol was used in the loop or a child context. |
| 908 |
DeclFinderASTVisitor DeclFinder(std::string(Symbol), GeneratedDecls); |
| 909 |
return DeclFinder.findUsages(SourceStmt); |
| 910 |
} |
| 911 |
|
| 912 |
} // namespace clang::tidy::modernize |