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