clang-tools 17.0.0git
LoopConvertUtils.cpp
Go to the documentation of this file.
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
28using namespace clang::ast_matchers;
29
30namespace 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).
38bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) {
39 StmtAncestors.insert(std::make_pair(Statement, StmtStack.back()));
40 StmtStack.push_back(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.
51bool 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.
60bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) {
61 Components.push_back(E);
62 return true;
63}
64
65/// record the MemberExpr as part of the parent expression.
66bool 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.
73bool 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.
80bool 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.
104bool 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.
115bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) {
116 const IdentifierInfo *Ident = D->getIdentifier();
117 if (Ident && Ident->getName() == Name) {
118 Found = true;
119 return false;
120 }
121 return true;
122}
123
124/// Forward any declaration references to the actual check on the
125/// referenced declaration.
126bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
127 if (auto *D = dyn_cast<NamedDecl>(DeclRef->getDecl()))
128 return VisitNamedDecl(D);
129 return true;
130}
131
132/// If the new variable name conflicts with any type used in the loop,
133/// then we mark that variable name as taken.
134bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) {
135 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()`
168const Expr *digThroughConstructorsConversions(const Expr *E) {
169 if (!E)
170 return nullptr;
171 E = E->IgnoreImplicit();
172 if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {
173 // The initial constructor must take exactly one parameter, but base 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();
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.
192bool 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.
203const DeclRefExpr *getDeclRef(const Expr *E) {
204 return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());
205}
206
207/// Returns true when two ValueDecls are the same variable.
208bool 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.
215static 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.
224static 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.
238template <typename ContainerT>
239static 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];
258static 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
292static 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
318static 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
331static 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
354static 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)) {
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
437static 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
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
472 TraverseStmt(const_cast<Stmt *>(Body));
473 return OnlyUsedAsIndex && ContainerExpr;
474}
475
477 // FIXME: add sort(on ID)+unique to avoid extra work.
478 for (const auto &I : Components)
479 addComponent(I);
480}
481
482void 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
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
509bool 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.
545bool 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()) {
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.
604bool 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
649bool 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.
695bool 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
750bool 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
783bool 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
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.
805bool 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
826bool 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
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.
882bool 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
const Expr * E
const FunctionDecl * Decl
const char Usage[]
const Decl * TheDecl
const Criteria C
std::string Container
const DeclRefExpr * DeclRef
A class to encapsulate lowering of the tool's confidence level.
void lowerTo(Confidence::Level Level)
Lower the internal confidence level to Level, but do not raise it.
ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar, const VarDecl *EndVar, const Expr *ContainerExpr, const Expr *ArrayBoundExpr, bool ContainerNeedsDereference)
bool findAndVerifyUsages(const Stmt *Body)
Finds all uses of IndexVar in Body, placing all usages in Usages, and returns true if IndexVar was on...
void addUsage(const Usage &U)
Adds the Usage if it was not added before.
void addComponents(const ComponentVector &Components)
Add a set of components that we should consider relevant to the container.
std::string createIndexName()
Generate a new index name.
llvm::json::Object Obj
Definition: LSPClient.cpp:173
static bool arrayMatchesBoundExpr(ASTContext *Context, const QualType &ArrayType, const Expr *ConditionExpr)
Determines whether the bound of a for loop condition expression is the same as the statically computa...
static bool containsExpr(ASTContext *Context, const ContainerT *Container, const Expr *E)
Returns true when the Container contains an Expr equivalent to E.
const DeclRefExpr * getDeclRef(const Expr *E)
Returns the DeclRefExpr represented by E, or NULL if there isn't one.
static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E)
Determines if an expression is a declaration reference to a particular variable.
bool areSameVariable(const ValueDecl *First, const ValueDecl *Second)
Returns true when two ValueDecls are the same variable.
static const Expr * getDereferenceOperand(const Expr *E)
If the expression is a dereference or call to operator*(), return the operand.
const Expr * digThroughConstructorsConversions(const Expr *E)
Look through conversion/copy constructors and member functions to find the explicit initialization ex...
static bool isAliasDecl(ASTContext *Context, const Decl *TheDecl, const VarDecl *IndexVar)
Determines whether the given Decl defines a variable initialized to the loop object.
static bool isIndexInSubscriptExpr(const Expr *IndexExpr, const VarDecl *IndexVar)
Returns true when the index expression is a declaration reference to IndexVar.
llvm::SmallVector< const clang::Expr *, 16 > ComponentVector
A vector used to store the AST subtrees of an Expr.
static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall, const VarDecl *IndexVar)
Returns true when Opcall is a call a one-parameter dereference of IndexVar.
bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second)
Returns true when two Exprs are equivalent.
static bool isDereferenceOfUop(const UnaryOperator *Uop, const VarDecl *IndexVar)
Returns true when Uop is a dereference of IndexVar.
The information needed to describe a valid convertible usage of an array index or iterator.