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