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

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