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

source code of clang-tools-extra/clang-tidy/modernize/LoopConvertUtils.cpp