blob: 9af797927e2d4f2664b1836c46716b8defa60df3 [file] [log] [blame]
Alexander Kornienko04970842015-08-19 09:11:46 +00001//===--- LoopConvertCheck.cpp - clang-tidy---------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "LoopConvertCheck.h"
11#include "clang/AST/ASTContext.h"
12#include "clang/ASTMatchers/ASTMatchFinder.h"
13
14using namespace clang;
15using namespace clang::ast_matchers;
16using namespace llvm;
17
18namespace clang {
19namespace tidy {
20namespace modernize {
21
22const char LoopNameArray[] = "forLoopArray";
23const char LoopNameIterator[] = "forLoopIterator";
24const char LoopNamePseudoArray[] = "forLoopPseudoArray";
25const char ConditionBoundName[] = "conditionBound";
26const char ConditionVarName[] = "conditionVar";
27const char IncrementVarName[] = "incrementVar";
28const char InitVarName[] = "initVar";
29const char BeginCallName[] = "beginCall";
30const char EndCallName[] = "endCall";
31const char ConditionEndVarName[] = "conditionEndVar";
32const char EndVarName[] = "endVar";
33const char DerefByValueResultName[] = "derefByValueResult";
34const char DerefByRefResultName[] = "derefByRefResult";
35
36// shared matchers
37static const TypeMatcher AnyType = anything();
38
39static const StatementMatcher IntegerComparisonMatcher =
40 expr(ignoringParenImpCasts(
41 declRefExpr(to(varDecl(hasType(isInteger())).bind(ConditionVarName)))));
42
43static const DeclarationMatcher InitToZeroMatcher =
44 varDecl(hasInitializer(ignoringParenImpCasts(integerLiteral(equals(0)))))
45 .bind(InitVarName);
46
47static const StatementMatcher IncrementVarMatcher =
48 declRefExpr(to(varDecl(hasType(isInteger())).bind(IncrementVarName)));
49
50/// \brief The matcher for loops over arrays.
51///
52/// In this general example, assuming 'j' and 'k' are of integral type:
53/// \code
54/// for (int i = 0; j < 3 + 2; ++k) { ... }
55/// \endcode
56/// The following string identifiers are bound to these parts of the AST:
57/// ConditionVarName: 'j' (as a VarDecl)
58/// ConditionBoundName: '3 + 2' (as an Expr)
59/// InitVarName: 'i' (as a VarDecl)
60/// IncrementVarName: 'k' (as a VarDecl)
61/// LoopName: The entire for loop (as a ForStmt)
62///
63/// Client code will need to make sure that:
64/// - The three index variables identified by the matcher are the same
65/// VarDecl.
66/// - The index variable is only used as an array index.
67/// - All arrays indexed by the loop are the same.
68StatementMatcher makeArrayLoopMatcher() {
69 StatementMatcher ArrayBoundMatcher =
70 expr(hasType(isInteger())).bind(ConditionBoundName);
71
72 return forStmt(
Angel Garcia Gomez06d010c2015-08-25 15:44:00 +000073 unless(isInTemplateInstantiation()),
Alexander Kornienko04970842015-08-19 09:11:46 +000074 hasLoopInit(declStmt(hasSingleDecl(InitToZeroMatcher))),
75 hasCondition(anyOf(
76 binaryOperator(hasOperatorName("<"),
77 hasLHS(IntegerComparisonMatcher),
78 hasRHS(ArrayBoundMatcher)),
79 binaryOperator(hasOperatorName(">"), hasLHS(ArrayBoundMatcher),
80 hasRHS(IntegerComparisonMatcher)))),
81 hasIncrement(unaryOperator(hasOperatorName("++"),
82 hasUnaryOperand(IncrementVarMatcher))))
83 .bind(LoopNameArray);
84}
85
86/// \brief The matcher used for iterator-based for loops.
87///
88/// This matcher is more flexible than array-based loops. It will match
89/// catch loops of the following textual forms (regardless of whether the
90/// iterator type is actually a pointer type or a class type):
91///
92/// Assuming f, g, and h are of type containerType::iterator,
93/// \code
94/// for (containerType::iterator it = container.begin(),
95/// e = createIterator(); f != g; ++h) { ... }
96/// for (containerType::iterator it = container.begin();
97/// f != anotherContainer.end(); ++h) { ... }
98/// \endcode
99/// The following string identifiers are bound to the parts of the AST:
100/// InitVarName: 'it' (as a VarDecl)
101/// ConditionVarName: 'f' (as a VarDecl)
102/// LoopName: The entire for loop (as a ForStmt)
103/// In the first example only:
104/// EndVarName: 'e' (as a VarDecl)
105/// ConditionEndVarName: 'g' (as a VarDecl)
106/// In the second example only:
107/// EndCallName: 'container.end()' (as a CXXMemberCallExpr)
108///
109/// Client code will need to make sure that:
110/// - The iterator variables 'it', 'f', and 'h' are the same.
111/// - The two containers on which 'begin' and 'end' are called are the same.
112/// - If the end iterator variable 'g' is defined, it is the same as 'f'.
113StatementMatcher makeIteratorLoopMatcher() {
114 StatementMatcher BeginCallMatcher =
115 memberCallExpr(argumentCountIs(0), callee(methodDecl(hasName("begin"))))
116 .bind(BeginCallName);
117
118 DeclarationMatcher InitDeclMatcher =
119 varDecl(hasInitializer(anyOf(ignoringParenImpCasts(BeginCallMatcher),
120 materializeTemporaryExpr(
121 ignoringParenImpCasts(BeginCallMatcher)),
122 hasDescendant(BeginCallMatcher))))
123 .bind(InitVarName);
124
125 DeclarationMatcher EndDeclMatcher =
126 varDecl(hasInitializer(anything())).bind(EndVarName);
127
128 StatementMatcher EndCallMatcher =
129 memberCallExpr(argumentCountIs(0), callee(methodDecl(hasName("end"))));
130
131 StatementMatcher IteratorBoundMatcher =
132 expr(anyOf(ignoringParenImpCasts(
133 declRefExpr(to(varDecl().bind(ConditionEndVarName)))),
134 ignoringParenImpCasts(expr(EndCallMatcher).bind(EndCallName)),
135 materializeTemporaryExpr(ignoringParenImpCasts(
136 expr(EndCallMatcher).bind(EndCallName)))));
137
138 StatementMatcher IteratorComparisonMatcher = expr(
139 ignoringParenImpCasts(declRefExpr(to(varDecl().bind(ConditionVarName)))));
140
141 StatementMatcher OverloadedNEQMatcher =
142 operatorCallExpr(hasOverloadedOperatorName("!="), argumentCountIs(2),
143 hasArgument(0, IteratorComparisonMatcher),
144 hasArgument(1, IteratorBoundMatcher));
145
146 // This matcher tests that a declaration is a CXXRecordDecl that has an
147 // overloaded operator*(). If the operator*() returns by value instead of by
148 // reference then the return type is tagged with DerefByValueResultName.
149 internal::Matcher<VarDecl> TestDerefReturnsByValue =
150 hasType(recordDecl(hasMethod(allOf(
151 hasOverloadedOperatorName("*"),
152 anyOf(
153 // Tag the return type if it's by value.
154 returns(qualType(unless(hasCanonicalType(referenceType())))
155 .bind(DerefByValueResultName)),
156 returns(
157 // Skip loops where the iterator's operator* returns an
158 // rvalue reference. This is just weird.
159 qualType(unless(hasCanonicalType(rValueReferenceType())))
160 .bind(DerefByRefResultName)))))));
161
162 return forStmt(
Angel Garcia Gomez06d010c2015-08-25 15:44:00 +0000163 unless(isInTemplateInstantiation()),
Alexander Kornienko04970842015-08-19 09:11:46 +0000164 hasLoopInit(anyOf(declStmt(declCountIs(2),
165 containsDeclaration(0, InitDeclMatcher),
166 containsDeclaration(1, EndDeclMatcher)),
167 declStmt(hasSingleDecl(InitDeclMatcher)))),
168 hasCondition(
169 anyOf(binaryOperator(hasOperatorName("!="),
170 hasLHS(IteratorComparisonMatcher),
171 hasRHS(IteratorBoundMatcher)),
172 binaryOperator(hasOperatorName("!="),
173 hasLHS(IteratorBoundMatcher),
174 hasRHS(IteratorComparisonMatcher)),
175 OverloadedNEQMatcher)),
176 hasIncrement(anyOf(
177 unaryOperator(hasOperatorName("++"),
178 hasUnaryOperand(declRefExpr(
179 to(varDecl(hasType(pointsTo(AnyType)))
180 .bind(IncrementVarName))))),
181 operatorCallExpr(
182 hasOverloadedOperatorName("++"),
183 hasArgument(
184 0, declRefExpr(to(varDecl(TestDerefReturnsByValue)
185 .bind(IncrementVarName))))))))
186 .bind(LoopNameIterator);
187}
188
189/// \brief The matcher used for array-like containers (pseudoarrays).
190///
191/// This matcher is more flexible than array-based loops. It will match
192/// loops of the following textual forms (regardless of whether the
193/// iterator type is actually a pointer type or a class type):
194///
195/// Assuming f, g, and h are of type containerType::iterator,
196/// \code
197/// for (int i = 0, j = container.size(); f < g; ++h) { ... }
198/// for (int i = 0; f < container.size(); ++h) { ... }
199/// \endcode
200/// The following string identifiers are bound to the parts of the AST:
201/// InitVarName: 'i' (as a VarDecl)
202/// ConditionVarName: 'f' (as a VarDecl)
203/// LoopName: The entire for loop (as a ForStmt)
204/// In the first example only:
205/// EndVarName: 'j' (as a VarDecl)
206/// ConditionEndVarName: 'g' (as a VarDecl)
207/// In the second example only:
208/// EndCallName: 'container.size()' (as a CXXMemberCallExpr)
209///
210/// Client code will need to make sure that:
211/// - The index variables 'i', 'f', and 'h' are the same.
212/// - The containers on which 'size()' is called is the container indexed.
213/// - The index variable is only used in overloaded operator[] or
214/// container.at().
215/// - If the end iterator variable 'g' is defined, it is the same as 'j'.
216/// - The container's iterators would not be invalidated during the loop.
217StatementMatcher makePseudoArrayLoopMatcher() {
218 // Test that the incoming type has a record declaration that has methods
219 // called 'begin' and 'end'. If the incoming type is const, then make sure
220 // these methods are also marked const.
221 //
222 // FIXME: To be completely thorough this matcher should also ensure the
223 // return type of begin/end is an iterator that dereferences to the same as
224 // what operator[] or at() returns. Such a test isn't likely to fail except
225 // for pathological cases.
226 //
227 // FIXME: Also, a record doesn't necessarily need begin() and end(). Free
228 // functions called begin() and end() taking the container as an argument
229 // are also allowed.
230 TypeMatcher RecordWithBeginEnd = qualType(
231 anyOf(qualType(isConstQualified(),
232 hasDeclaration(recordDecl(
233 hasMethod(methodDecl(hasName("begin"), isConst())),
234 hasMethod(methodDecl(hasName("end"),
235 isConst())))) // hasDeclaration
236 ), // qualType
237 qualType(unless(isConstQualified()),
238 hasDeclaration(
239 recordDecl(hasMethod(hasName("begin")),
240 hasMethod(hasName("end"))))) // qualType
241 ));
242
243 StatementMatcher SizeCallMatcher = memberCallExpr(
244 argumentCountIs(0),
245 callee(methodDecl(anyOf(hasName("size"), hasName("length")))),
246 on(anyOf(hasType(pointsTo(RecordWithBeginEnd)),
247 hasType(RecordWithBeginEnd))));
248
249 StatementMatcher EndInitMatcher =
250 expr(anyOf(ignoringParenImpCasts(expr(SizeCallMatcher).bind(EndCallName)),
251 explicitCastExpr(hasSourceExpression(ignoringParenImpCasts(
252 expr(SizeCallMatcher).bind(EndCallName))))));
253
254 DeclarationMatcher EndDeclMatcher =
255 varDecl(hasInitializer(EndInitMatcher)).bind(EndVarName);
256
257 StatementMatcher IndexBoundMatcher =
258 expr(anyOf(ignoringParenImpCasts(declRefExpr(to(
259 varDecl(hasType(isInteger())).bind(ConditionEndVarName)))),
260 EndInitMatcher));
261
262 return forStmt(
Angel Garcia Gomez06d010c2015-08-25 15:44:00 +0000263 unless(isInTemplateInstantiation()),
Alexander Kornienko04970842015-08-19 09:11:46 +0000264 hasLoopInit(
265 anyOf(declStmt(declCountIs(2),
266 containsDeclaration(0, InitToZeroMatcher),
267 containsDeclaration(1, EndDeclMatcher)),
268 declStmt(hasSingleDecl(InitToZeroMatcher)))),
269 hasCondition(anyOf(
270 binaryOperator(hasOperatorName("<"),
271 hasLHS(IntegerComparisonMatcher),
272 hasRHS(IndexBoundMatcher)),
273 binaryOperator(hasOperatorName(">"), hasLHS(IndexBoundMatcher),
274 hasRHS(IntegerComparisonMatcher)))),
275 hasIncrement(unaryOperator(hasOperatorName("++"),
276 hasUnaryOperand(IncrementVarMatcher))))
277 .bind(LoopNamePseudoArray);
278}
279
280/// \brief Determine whether Init appears to be an initializing an iterator.
281///
282/// If it is, returns the object whose begin() or end() method is called, and
283/// the output parameter isArrow is set to indicate whether the initialization
284/// is called via . or ->.
285static const Expr *getContainerFromBeginEndCall(const Expr *Init, bool IsBegin,
286 bool *IsArrow) {
287 // FIXME: Maybe allow declaration/initialization outside of the for loop.
288 const auto *TheCall =
289 dyn_cast_or_null<CXXMemberCallExpr>(digThroughConstructors(Init));
290 if (!TheCall || TheCall->getNumArgs() != 0)
291 return nullptr;
292
293 const auto *Member = dyn_cast<MemberExpr>(TheCall->getCallee());
294 if (!Member)
295 return nullptr;
296 StringRef Name = Member->getMemberDecl()->getName();
297 StringRef TargetName = IsBegin ? "begin" : "end";
298 if (Name != TargetName)
299 return nullptr;
300
301 const Expr *SourceExpr = Member->getBase();
302 if (!SourceExpr)
303 return nullptr;
304
305 *IsArrow = Member->isArrow();
306 return SourceExpr;
307}
308
309/// \brief Determines the container whose begin() and end() functions are called
310/// for an iterator-based loop.
311///
312/// BeginExpr must be a member call to a function named "begin()", and EndExpr
313/// must be a member.
314static const Expr *findContainer(ASTContext *Context, const Expr *BeginExpr,
315 const Expr *EndExpr,
316 bool *ContainerNeedsDereference) {
317 // Now that we know the loop variable and test expression, make sure they are
318 // valid.
319 bool BeginIsArrow = false;
320 bool EndIsArrow = false;
321 const Expr *BeginContainerExpr =
322 getContainerFromBeginEndCall(BeginExpr, /*IsBegin=*/true, &BeginIsArrow);
323 if (!BeginContainerExpr)
324 return nullptr;
325
326 const Expr *EndContainerExpr =
327 getContainerFromBeginEndCall(EndExpr, /*IsBegin=*/false, &EndIsArrow);
328 // Disallow loops that try evil things like this (note the dot and arrow):
329 // for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }
330 if (!EndContainerExpr || BeginIsArrow != EndIsArrow ||
331 !areSameExpr(Context, EndContainerExpr, BeginContainerExpr))
332 return nullptr;
333
334 *ContainerNeedsDereference = BeginIsArrow;
335 return BeginContainerExpr;
336}
337
338/// \brief Obtain the original source code text from a SourceRange.
339static StringRef getStringFromRange(SourceManager &SourceMgr,
340 const LangOptions &LangOpts,
341 SourceRange Range) {
342 if (SourceMgr.getFileID(Range.getBegin()) !=
Alexander Kornienko74a44d92015-08-20 13:18:23 +0000343 SourceMgr.getFileID(Range.getEnd())) {
344 return StringRef(); // Empty string.
345 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000346
347 return Lexer::getSourceText(CharSourceRange(Range, true), SourceMgr,
348 LangOpts);
349}
350
351/// \brief If the given expression is actually a DeclRefExpr, find and return
352/// the underlying VarDecl; otherwise, return NULL.
353static const VarDecl *getReferencedVariable(const Expr *E) {
354 if (const DeclRefExpr *DRE = getDeclRef(E))
355 return dyn_cast<VarDecl>(DRE->getDecl());
356 return nullptr;
357}
358
359/// \brief Returns true when the given expression is a member expression
360/// whose base is `this` (implicitly or not).
361static bool isDirectMemberExpr(const Expr *E) {
362 if (const auto *Member = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))
363 return isa<CXXThisExpr>(Member->getBase()->IgnoreParenImpCasts());
364 return false;
365}
366
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000367/// \brief Returns true when it can be guaranteed that the elements of the
368/// container are not being modified.
369static bool usagesAreConst(const UsageResult &Usages) {
370 // FIXME: Make this function more generic.
371 return Usages.empty();
372}
373
374/// \brief Returns true if the elements of the container are never accessed
375/// by reference.
376static bool usagesReturnRValues(const UsageResult &Usages) {
377 for (const auto &U : Usages) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000378 if (U.Expression && !U.Expression->isRValue())
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000379 return false;
380 }
381 return true;
382}
383
Alexander Kornienko04970842015-08-19 09:11:46 +0000384LoopConvertCheck::LoopConvertCheck(StringRef Name, ClangTidyContext *Context)
385 : ClangTidyCheck(Name, Context), TUInfo(new TUTrackingInfo),
386 MinConfidence(StringSwitch<Confidence::Level>(
387 Options.get("MinConfidence", "reasonable"))
388 .Case("safe", Confidence::CL_Safe)
389 .Case("risky", Confidence::CL_Risky)
390 .Default(Confidence::CL_Reasonable)) {}
391
392void LoopConvertCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
393 SmallVector<std::string, 3> Confs{"risky", "reasonable", "safe"};
394 Options.store(Opts, "MinConfidence", Confs[static_cast<int>(MinConfidence)]);
395}
396
397/// \brief Computes the changes needed to convert a given for loop, and
398/// applies it.
399void LoopConvertCheck::doConversion(
400 ASTContext *Context, const VarDecl *IndexVar, const VarDecl *MaybeContainer,
401 StringRef ContainerString, const UsageResult &Usages,
402 const DeclStmt *AliasDecl, bool AliasUseRequired, bool AliasFromForInit,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000403 const ForStmt *TheLoop, RangeDescriptor Descriptor) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000404 auto Diag = diag(TheLoop->getForLoc(), "use range-based for loop instead");
405
406 std::string VarName;
407 bool VarNameFromAlias = (Usages.size() == 1) && AliasDecl;
408 bool AliasVarIsRef = false;
409
410 if (VarNameFromAlias) {
411 const auto *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());
412 VarName = AliasVar->getName().str();
413 AliasVarIsRef = AliasVar->getType()->isReferenceType();
414
415 // We keep along the entire DeclStmt to keep the correct range here.
416 const SourceRange &ReplaceRange = AliasDecl->getSourceRange();
417
418 std::string ReplacementText;
419 if (AliasUseRequired) {
420 ReplacementText = VarName;
421 } else if (AliasFromForInit) {
422 // FIXME: Clang includes the location of the ';' but only for DeclStmt's
423 // in a for loop's init clause. Need to put this ';' back while removing
424 // the declaration of the alias variable. This is probably a bug.
425 ReplacementText = ";";
426 }
427
428 Diag << FixItHint::CreateReplacement(
429 CharSourceRange::getTokenRange(ReplaceRange), ReplacementText);
430 // No further replacements are made to the loop, since the iterator or index
431 // was used exactly once - in the initialization of AliasVar.
432 } else {
433 VariableNamer Namer(&TUInfo->getGeneratedDecls(),
434 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
435 TheLoop, IndexVar, MaybeContainer, Context);
436 VarName = Namer.createIndexName();
437 // First, replace all usages of the array subscript expression with our new
438 // variable.
439 for (const auto &I : Usages) {
Alexander Kornienkoe1292f82015-08-19 16:54:51 +0000440 std::string ReplaceText = I.IsArrow ? VarName + "." : VarName;
Alexander Kornienko04970842015-08-19 09:11:46 +0000441 TUInfo->getReplacedVars().insert(std::make_pair(TheLoop, IndexVar));
442 Diag << FixItHint::CreateReplacement(
443 CharSourceRange::getTokenRange(I.Range), ReplaceText);
444 }
445 }
446
447 // Now, we need to construct the new range expression.
448 SourceRange ParenRange(TheLoop->getLParenLoc(), TheLoop->getRParenLoc());
449
450 QualType AutoRefType = Context->getAutoDeductType();
451
452 // If the new variable name is from the aliased variable, then the reference
453 // type for the new variable should only be used if the aliased variable was
454 // declared as a reference.
455 if (!VarNameFromAlias || AliasVarIsRef) {
456 // If an iterator's operator*() returns a 'T&' we can bind that to 'auto&'.
457 // If operator*() returns 'T' we can bind that to 'auto&&' which will deduce
458 // to 'T&&&'.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000459 if (Descriptor.DerefByValue) {
460 if (!Descriptor.IsTriviallyCopyable)
461 AutoRefType = Context->getRValueReferenceType(AutoRefType);
Alexander Kornienko04970842015-08-19 09:11:46 +0000462 } else {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000463 if (Descriptor.DerefByConstRef)
Alexander Kornienko04970842015-08-19 09:11:46 +0000464 AutoRefType = Context->getConstType(AutoRefType);
465 AutoRefType = Context->getLValueReferenceType(AutoRefType);
466 }
467 }
468
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000469 StringRef MaybeDereference = Descriptor.ContainerNeedsDereference ? "*" : "";
Alexander Kornienkoe1292f82015-08-19 16:54:51 +0000470 std::string TypeString = AutoRefType.getAsString();
471 std::string Range = ("(" + TypeString + " " + VarName + " : " +
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000472 MaybeDereference + ContainerString + ")")
473 .str();
Alexander Kornienko04970842015-08-19 09:11:46 +0000474 Diag << FixItHint::CreateReplacement(
475 CharSourceRange::getTokenRange(ParenRange), Range);
476 TUInfo->getGeneratedDecls().insert(make_pair(TheLoop, VarName));
477}
478
479/// \brief Determine if the change should be deferred or rejected, returning
480/// text which refers to the container iterated over if the change should
481/// proceed.
482StringRef LoopConvertCheck::checkRejections(ASTContext *Context,
483 const Expr *ContainerExpr,
484 const ForStmt *TheLoop) {
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000485 // If we already modified the range of this for loop, don't do any further
Alexander Kornienko04970842015-08-19 09:11:46 +0000486 // updates on this iteration.
487 if (TUInfo->getReplacedVars().count(TheLoop))
488 return "";
489
490 Context->getTranslationUnitDecl();
491 TUInfo->getParentFinder();
492 TUInfo->getParentFinder().gatherAncestors(Context->getTranslationUnitDecl());
493 // Ensure that we do not try to move an expression dependent on a local
494 // variable declared inside the loop outside of it.
495 DependencyFinderASTVisitor DependencyFinder(
496 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
497 &TUInfo->getParentFinder().getDeclToParentStmtMap(),
498 &TUInfo->getReplacedVars(), TheLoop);
499
500 // FIXME: Determine when the external dependency isn't an expression converted
501 // by another loop.
502 if (DependencyFinder.dependsOnInsideVariable(ContainerExpr))
503 return "";
504
505 StringRef ContainerString;
506 if (isa<CXXThisExpr>(ContainerExpr->IgnoreParenImpCasts())) {
507 ContainerString = "this";
508 } else {
509 ContainerString =
510 getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),
511 ContainerExpr->getSourceRange());
512 }
513
514 return ContainerString;
515}
516
517/// \brief Given a loop header that would be convertible, discover all usages
518/// of the index variable and convert the loop if possible.
519void LoopConvertCheck::findAndVerifyUsages(
520 ASTContext *Context, const VarDecl *LoopVar, const VarDecl *EndVar,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000521 const Expr *ContainerExpr, const Expr *BoundExpr, const ForStmt *TheLoop,
522 LoopFixerKind FixerKind, RangeDescriptor Descriptor) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000523 ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000524 BoundExpr,
525 Descriptor.ContainerNeedsDereference);
Alexander Kornienko04970842015-08-19 09:11:46 +0000526
527 if (ContainerExpr) {
528 ComponentFinderASTVisitor ComponentFinder;
529 ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
530 Finder.addComponents(ComponentFinder.getComponents());
531 }
532
533 if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
534 return;
535
536 Confidence ConfidenceLevel(Finder.getConfidenceLevel());
537 if (FixerKind == LFK_Array) {
538 // The array being indexed by IndexVar was discovered during traversal.
539 ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();
540 // Very few loops are over expressions that generate arrays rather than
541 // array variables. Consider loops over arrays that aren't just represented
542 // by a variable to be risky conversions.
543 if (!getReferencedVariable(ContainerExpr) &&
544 !isDirectMemberExpr(ContainerExpr))
545 ConfidenceLevel.lowerTo(Confidence::CL_Risky);
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000546 } else if (FixerKind == LFK_PseudoArray) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000547 if (!Descriptor.DerefByValue && !Descriptor.DerefByConstRef) {
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000548 const UsageResult &Usages = Finder.getUsages();
549 if (usagesAreConst(Usages)) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000550 Descriptor.DerefByConstRef = true;
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000551 } else if (usagesReturnRValues(Usages)) {
552 // If the index usages (dereference, subscript, at) return RValues,
553 // then we should not use a non-const reference.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000554 Descriptor.DerefByValue = true;
555 // Try to find the type of the elements on the container from the
556 // usages.
557 for (const Usage &U : Usages) {
558 if (!U.Expression || U.Expression->getType().isNull())
559 continue;
560 QualType Type = U.Expression->getType().getCanonicalType();
561 if (U.IsArrow) {
562 if (!Type->isPointerType())
563 continue;
564 Type = Type->getPointeeType();
565 }
566 Descriptor.IsTriviallyCopyable =
567 Type.isTriviallyCopyableType(*Context);
568 }
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000569 }
570 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000571 }
572
573 StringRef ContainerString = checkRejections(Context, ContainerExpr, TheLoop);
574
575 if (ContainerString.empty() || ConfidenceLevel.getLevel() < MinConfidence)
576 return;
577
578 doConversion(Context, LoopVar, getReferencedVariable(ContainerExpr),
579 ContainerString, Finder.getUsages(), Finder.getAliasDecl(),
580 Finder.aliasUseRequired(), Finder.aliasFromForInit(), TheLoop,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000581 Descriptor);
Alexander Kornienko04970842015-08-19 09:11:46 +0000582}
583
584void LoopConvertCheck::registerMatchers(MatchFinder *Finder) {
Aaron Ballman8b0583e2015-08-28 17:58:10 +0000585 // Only register the matchers for C++. Because this checker is used for
586 // modernization, it is reasonable to run it on any C++ standard with the
587 // assumption the user is trying to modernize their codebase.
588 if (getLangOpts().CPlusPlus) {
589 Finder->addMatcher(makeArrayLoopMatcher(), this);
590 Finder->addMatcher(makeIteratorLoopMatcher(), this);
591 Finder->addMatcher(makePseudoArrayLoopMatcher(), this);
592 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000593}
594
595void LoopConvertCheck::check(const MatchFinder::MatchResult &Result) {
596 const BoundNodes &Nodes = Result.Nodes;
597 Confidence ConfidenceLevel(Confidence::CL_Safe);
598 ASTContext *Context = Result.Context;
599
600 const ForStmt *TheLoop;
601 LoopFixerKind FixerKind;
602
603 if ((TheLoop = Nodes.getStmtAs<ForStmt>(LoopNameArray))) {
604 FixerKind = LFK_Array;
605 } else if ((TheLoop = Nodes.getStmtAs<ForStmt>(LoopNameIterator))) {
606 FixerKind = LFK_Iterator;
607 } else {
608 TheLoop = Nodes.getStmtAs<ForStmt>(LoopNamePseudoArray);
609 assert(TheLoop && "Bad Callback. No for statement");
610 FixerKind = LFK_PseudoArray;
611 }
612
613 // Check that we have exactly one index variable and at most one end variable.
614 const auto *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
615 const auto *CondVar = Nodes.getDeclAs<VarDecl>(ConditionVarName);
616 const auto *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
617 if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
618 return;
619 const auto *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
620 const auto *ConditionEndVar = Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
621 if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
622 return;
623
624 // If the end comparison isn't a variable, we can try to work with the
625 // expression the loop variable is being tested against instead.
626 const auto *EndCall = Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
627 const auto *BoundExpr = Nodes.getStmtAs<Expr>(ConditionBoundName);
628 // If the loop calls end()/size() after each iteration, lower our confidence
629 // level.
630 if (FixerKind != LFK_Array && !EndVar)
631 ConfidenceLevel.lowerTo(Confidence::CL_Reasonable);
632
633 const Expr *ContainerExpr = nullptr;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000634 RangeDescriptor Descriptor{false, false, false, false};
Alexander Kornienko04970842015-08-19 09:11:46 +0000635 // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
636 // don't allow the ight-recursive checks in digThroughConstructors.
637 if (FixerKind == LFK_Iterator) {
638 ContainerExpr = findContainer(Context, LoopVar->getInit(),
639 EndVar ? EndVar->getInit() : EndCall,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000640 &Descriptor.ContainerNeedsDereference);
Alexander Kornienko04970842015-08-19 09:11:46 +0000641
642 QualType InitVarType = InitVar->getType();
643 QualType CanonicalInitVarType = InitVarType.getCanonicalType();
644
645 const auto *BeginCall = Nodes.getNodeAs<CXXMemberCallExpr>(BeginCallName);
646 assert(BeginCall && "Bad Callback. No begin call expression");
647 QualType CanonicalBeginType =
648 BeginCall->getMethodDecl()->getReturnType().getCanonicalType();
649 if (CanonicalBeginType->isPointerType() &&
650 CanonicalInitVarType->isPointerType()) {
651 QualType BeginPointeeType = CanonicalBeginType->getPointeeType();
652 QualType InitPointeeType = CanonicalInitVarType->getPointeeType();
653 // If the initializer and the variable are both pointers check if the
654 // un-qualified pointee types match otherwise we don't use auto.
655 if (!Context->hasSameUnqualifiedType(InitPointeeType, BeginPointeeType))
656 return;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000657 Descriptor.IsTriviallyCopyable =
658 BeginPointeeType.isTriviallyCopyableType(*Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000659 } else {
660 // Check for qualified types to avoid conversions from non-const to const
661 // iterator types.
662 if (!Context->hasSameType(CanonicalInitVarType, CanonicalBeginType))
663 return;
664 }
665
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000666 const auto *DerefByValueType =
667 Nodes.getNodeAs<QualType>(DerefByValueResultName);
668 Descriptor.DerefByValue = DerefByValueType;
669 if (!Descriptor.DerefByValue) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000670 if (const auto *DerefType =
671 Nodes.getNodeAs<QualType>(DerefByRefResultName)) {
672 // A node will only be bound with DerefByRefResultName if we're dealing
673 // with a user-defined iterator type. Test the const qualification of
674 // the reference type.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000675 Descriptor.DerefByConstRef = (*DerefType)
676 ->getAs<ReferenceType>()
677 ->getPointeeType()
678 .isConstQualified();
Alexander Kornienko04970842015-08-19 09:11:46 +0000679 } else {
680 // By nature of the matcher this case is triggered only for built-in
681 // iterator types (i.e. pointers).
682 assert(isa<PointerType>(CanonicalInitVarType) &&
683 "Non-class iterator type is not a pointer type");
684 QualType InitPointeeType = CanonicalInitVarType->getPointeeType();
685 QualType BeginPointeeType = CanonicalBeginType->getPointeeType();
686 // If the initializer and variable have both the same type just use auto
687 // otherwise we test for const qualification of the pointed-at type.
688 if (!Context->hasSameType(InitPointeeType, BeginPointeeType))
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000689 Descriptor.DerefByConstRef = InitPointeeType.isConstQualified();
Alexander Kornienko04970842015-08-19 09:11:46 +0000690 }
691 } else {
692 // If the dereference operator returns by value then test for the
693 // canonical const qualification of the init variable type.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000694 Descriptor.DerefByConstRef = CanonicalInitVarType.isConstQualified();
695 Descriptor.IsTriviallyCopyable =
696 DerefByValueType->isTriviallyCopyableType(*Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000697 }
698 } else if (FixerKind == LFK_PseudoArray) {
699 if (!EndCall)
700 return;
701 ContainerExpr = EndCall->getImplicitObjectArgument();
702 const auto *Member = dyn_cast<MemberExpr>(EndCall->getCallee());
703 if (!Member)
704 return;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000705 Descriptor.ContainerNeedsDereference = Member->isArrow();
Alexander Kornienko04970842015-08-19 09:11:46 +0000706 }
707
708 // We must know the container or an array length bound.
709 if (!ContainerExpr && !BoundExpr)
710 return;
711
712 if (ConfidenceLevel.getLevel() < MinConfidence)
713 return;
714
715 findAndVerifyUsages(Context, LoopVar, EndVar, ContainerExpr, BoundExpr,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000716 TheLoop, FixerKind, Descriptor);
Alexander Kornienko04970842015-08-19 09:11:46 +0000717}
718
719} // namespace modernize
720} // namespace tidy
721} // namespace clang