blob: 2c623727119fe53d910e88f5dd576eef3487ddfe [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 =
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000115 cxxMemberCallExpr(argumentCountIs(0),
116 callee(cxxMethodDecl(hasName("begin"))))
Alexander Kornienko04970842015-08-19 09:11:46 +0000117 .bind(BeginCallName);
118
119 DeclarationMatcher InitDeclMatcher =
120 varDecl(hasInitializer(anyOf(ignoringParenImpCasts(BeginCallMatcher),
121 materializeTemporaryExpr(
122 ignoringParenImpCasts(BeginCallMatcher)),
123 hasDescendant(BeginCallMatcher))))
124 .bind(InitVarName);
125
126 DeclarationMatcher EndDeclMatcher =
127 varDecl(hasInitializer(anything())).bind(EndVarName);
128
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000129 StatementMatcher EndCallMatcher = cxxMemberCallExpr(
130 argumentCountIs(0), callee(cxxMethodDecl(hasName("end"))));
Alexander Kornienko04970842015-08-19 09:11:46 +0000131
132 StatementMatcher IteratorBoundMatcher =
133 expr(anyOf(ignoringParenImpCasts(
134 declRefExpr(to(varDecl().bind(ConditionEndVarName)))),
135 ignoringParenImpCasts(expr(EndCallMatcher).bind(EndCallName)),
136 materializeTemporaryExpr(ignoringParenImpCasts(
137 expr(EndCallMatcher).bind(EndCallName)))));
138
139 StatementMatcher IteratorComparisonMatcher = expr(
140 ignoringParenImpCasts(declRefExpr(to(varDecl().bind(ConditionVarName)))));
141
142 StatementMatcher OverloadedNEQMatcher =
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000143 cxxOperatorCallExpr(hasOverloadedOperatorName("!="), argumentCountIs(2),
144 hasArgument(0, IteratorComparisonMatcher),
145 hasArgument(1, IteratorBoundMatcher));
Alexander Kornienko04970842015-08-19 09:11:46 +0000146
147 // This matcher tests that a declaration is a CXXRecordDecl that has an
148 // overloaded operator*(). If the operator*() returns by value instead of by
149 // reference then the return type is tagged with DerefByValueResultName.
150 internal::Matcher<VarDecl> TestDerefReturnsByValue =
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000151 hasType(cxxRecordDecl(hasMethod(allOf(
Alexander Kornienko04970842015-08-19 09:11:46 +0000152 hasOverloadedOperatorName("*"),
153 anyOf(
154 // Tag the return type if it's by value.
155 returns(qualType(unless(hasCanonicalType(referenceType())))
156 .bind(DerefByValueResultName)),
157 returns(
158 // Skip loops where the iterator's operator* returns an
159 // rvalue reference. This is just weird.
160 qualType(unless(hasCanonicalType(rValueReferenceType())))
161 .bind(DerefByRefResultName)))))));
162
163 return forStmt(
Angel Garcia Gomez06d010c2015-08-25 15:44:00 +0000164 unless(isInTemplateInstantiation()),
Alexander Kornienko04970842015-08-19 09:11:46 +0000165 hasLoopInit(anyOf(declStmt(declCountIs(2),
166 containsDeclaration(0, InitDeclMatcher),
167 containsDeclaration(1, EndDeclMatcher)),
168 declStmt(hasSingleDecl(InitDeclMatcher)))),
169 hasCondition(
170 anyOf(binaryOperator(hasOperatorName("!="),
171 hasLHS(IteratorComparisonMatcher),
172 hasRHS(IteratorBoundMatcher)),
173 binaryOperator(hasOperatorName("!="),
174 hasLHS(IteratorBoundMatcher),
175 hasRHS(IteratorComparisonMatcher)),
176 OverloadedNEQMatcher)),
177 hasIncrement(anyOf(
178 unaryOperator(hasOperatorName("++"),
179 hasUnaryOperand(declRefExpr(
180 to(varDecl(hasType(pointsTo(AnyType)))
181 .bind(IncrementVarName))))),
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000182 cxxOperatorCallExpr(
Alexander Kornienko04970842015-08-19 09:11:46 +0000183 hasOverloadedOperatorName("++"),
184 hasArgument(
185 0, declRefExpr(to(varDecl(TestDerefReturnsByValue)
186 .bind(IncrementVarName))))))))
187 .bind(LoopNameIterator);
188}
189
190/// \brief The matcher used for array-like containers (pseudoarrays).
191///
192/// This matcher is more flexible than array-based loops. It will match
193/// loops of the following textual forms (regardless of whether the
194/// iterator type is actually a pointer type or a class type):
195///
196/// Assuming f, g, and h are of type containerType::iterator,
197/// \code
198/// for (int i = 0, j = container.size(); f < g; ++h) { ... }
199/// for (int i = 0; f < container.size(); ++h) { ... }
200/// \endcode
201/// The following string identifiers are bound to the parts of the AST:
202/// InitVarName: 'i' (as a VarDecl)
203/// ConditionVarName: 'f' (as a VarDecl)
204/// LoopName: The entire for loop (as a ForStmt)
205/// In the first example only:
206/// EndVarName: 'j' (as a VarDecl)
207/// ConditionEndVarName: 'g' (as a VarDecl)
208/// In the second example only:
209/// EndCallName: 'container.size()' (as a CXXMemberCallExpr)
210///
211/// Client code will need to make sure that:
212/// - The index variables 'i', 'f', and 'h' are the same.
213/// - The containers on which 'size()' is called is the container indexed.
214/// - The index variable is only used in overloaded operator[] or
215/// container.at().
216/// - If the end iterator variable 'g' is defined, it is the same as 'j'.
217/// - The container's iterators would not be invalidated during the loop.
218StatementMatcher makePseudoArrayLoopMatcher() {
219 // Test that the incoming type has a record declaration that has methods
220 // called 'begin' and 'end'. If the incoming type is const, then make sure
221 // these methods are also marked const.
222 //
223 // FIXME: To be completely thorough this matcher should also ensure the
224 // return type of begin/end is an iterator that dereferences to the same as
225 // what operator[] or at() returns. Such a test isn't likely to fail except
226 // for pathological cases.
227 //
228 // FIXME: Also, a record doesn't necessarily need begin() and end(). Free
229 // functions called begin() and end() taking the container as an argument
230 // are also allowed.
231 TypeMatcher RecordWithBeginEnd = qualType(
232 anyOf(qualType(isConstQualified(),
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000233 hasDeclaration(cxxRecordDecl(
234 hasMethod(cxxMethodDecl(hasName("begin"), isConst())),
235 hasMethod(cxxMethodDecl(hasName("end"),
236 isConst())))) // hasDeclaration
237 ), // qualType
Alexander Kornienko04970842015-08-19 09:11:46 +0000238 qualType(unless(isConstQualified()),
239 hasDeclaration(
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000240 cxxRecordDecl(hasMethod(hasName("begin")),
241 hasMethod(hasName("end"))))) // qualType
Alexander Kornienko04970842015-08-19 09:11:46 +0000242 ));
243
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000244 StatementMatcher SizeCallMatcher = cxxMemberCallExpr(
Alexander Kornienko04970842015-08-19 09:11:46 +0000245 argumentCountIs(0),
Aaron Ballmanb9ea09c2015-09-17 13:31:25 +0000246 callee(cxxMethodDecl(anyOf(hasName("size"), hasName("length")))),
Alexander Kornienko04970842015-08-19 09:11:46 +0000247 on(anyOf(hasType(pointsTo(RecordWithBeginEnd)),
248 hasType(RecordWithBeginEnd))));
249
250 StatementMatcher EndInitMatcher =
251 expr(anyOf(ignoringParenImpCasts(expr(SizeCallMatcher).bind(EndCallName)),
252 explicitCastExpr(hasSourceExpression(ignoringParenImpCasts(
253 expr(SizeCallMatcher).bind(EndCallName))))));
254
255 DeclarationMatcher EndDeclMatcher =
256 varDecl(hasInitializer(EndInitMatcher)).bind(EndVarName);
257
258 StatementMatcher IndexBoundMatcher =
259 expr(anyOf(ignoringParenImpCasts(declRefExpr(to(
260 varDecl(hasType(isInteger())).bind(ConditionEndVarName)))),
261 EndInitMatcher));
262
263 return forStmt(
Angel Garcia Gomez06d010c2015-08-25 15:44:00 +0000264 unless(isInTemplateInstantiation()),
Alexander Kornienko04970842015-08-19 09:11:46 +0000265 hasLoopInit(
266 anyOf(declStmt(declCountIs(2),
267 containsDeclaration(0, InitToZeroMatcher),
268 containsDeclaration(1, EndDeclMatcher)),
269 declStmt(hasSingleDecl(InitToZeroMatcher)))),
270 hasCondition(anyOf(
271 binaryOperator(hasOperatorName("<"),
272 hasLHS(IntegerComparisonMatcher),
273 hasRHS(IndexBoundMatcher)),
274 binaryOperator(hasOperatorName(">"), hasLHS(IndexBoundMatcher),
275 hasRHS(IntegerComparisonMatcher)))),
276 hasIncrement(unaryOperator(hasOperatorName("++"),
277 hasUnaryOperand(IncrementVarMatcher))))
278 .bind(LoopNamePseudoArray);
279}
280
281/// \brief Determine whether Init appears to be an initializing an iterator.
282///
283/// If it is, returns the object whose begin() or end() method is called, and
284/// the output parameter isArrow is set to indicate whether the initialization
285/// is called via . or ->.
286static const Expr *getContainerFromBeginEndCall(const Expr *Init, bool IsBegin,
287 bool *IsArrow) {
288 // FIXME: Maybe allow declaration/initialization outside of the for loop.
289 const auto *TheCall =
290 dyn_cast_or_null<CXXMemberCallExpr>(digThroughConstructors(Init));
291 if (!TheCall || TheCall->getNumArgs() != 0)
292 return nullptr;
293
294 const auto *Member = dyn_cast<MemberExpr>(TheCall->getCallee());
295 if (!Member)
296 return nullptr;
297 StringRef Name = Member->getMemberDecl()->getName();
298 StringRef TargetName = IsBegin ? "begin" : "end";
299 if (Name != TargetName)
300 return nullptr;
301
302 const Expr *SourceExpr = Member->getBase();
303 if (!SourceExpr)
304 return nullptr;
305
306 *IsArrow = Member->isArrow();
307 return SourceExpr;
308}
309
310/// \brief Determines the container whose begin() and end() functions are called
311/// for an iterator-based loop.
312///
313/// BeginExpr must be a member call to a function named "begin()", and EndExpr
314/// must be a member.
315static const Expr *findContainer(ASTContext *Context, const Expr *BeginExpr,
316 const Expr *EndExpr,
317 bool *ContainerNeedsDereference) {
318 // Now that we know the loop variable and test expression, make sure they are
319 // valid.
320 bool BeginIsArrow = false;
321 bool EndIsArrow = false;
322 const Expr *BeginContainerExpr =
323 getContainerFromBeginEndCall(BeginExpr, /*IsBegin=*/true, &BeginIsArrow);
324 if (!BeginContainerExpr)
325 return nullptr;
326
327 const Expr *EndContainerExpr =
328 getContainerFromBeginEndCall(EndExpr, /*IsBegin=*/false, &EndIsArrow);
329 // Disallow loops that try evil things like this (note the dot and arrow):
330 // for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }
331 if (!EndContainerExpr || BeginIsArrow != EndIsArrow ||
332 !areSameExpr(Context, EndContainerExpr, BeginContainerExpr))
333 return nullptr;
334
335 *ContainerNeedsDereference = BeginIsArrow;
336 return BeginContainerExpr;
337}
338
339/// \brief Obtain the original source code text from a SourceRange.
340static StringRef getStringFromRange(SourceManager &SourceMgr,
341 const LangOptions &LangOpts,
342 SourceRange Range) {
343 if (SourceMgr.getFileID(Range.getBegin()) !=
Alexander Kornienko74a44d92015-08-20 13:18:23 +0000344 SourceMgr.getFileID(Range.getEnd())) {
345 return StringRef(); // Empty string.
346 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000347
348 return Lexer::getSourceText(CharSourceRange(Range, true), SourceMgr,
349 LangOpts);
350}
351
352/// \brief If the given expression is actually a DeclRefExpr, find and return
353/// the underlying VarDecl; otherwise, return NULL.
354static const VarDecl *getReferencedVariable(const Expr *E) {
355 if (const DeclRefExpr *DRE = getDeclRef(E))
356 return dyn_cast<VarDecl>(DRE->getDecl());
357 return nullptr;
358}
359
360/// \brief Returns true when the given expression is a member expression
361/// whose base is `this` (implicitly or not).
362static bool isDirectMemberExpr(const Expr *E) {
363 if (const auto *Member = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))
364 return isa<CXXThisExpr>(Member->getBase()->IgnoreParenImpCasts());
365 return false;
366}
367
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000368/// \brief Returns true when it can be guaranteed that the elements of the
369/// container are not being modified.
370static bool usagesAreConst(const UsageResult &Usages) {
371 // FIXME: Make this function more generic.
372 return Usages.empty();
373}
374
375/// \brief Returns true if the elements of the container are never accessed
376/// by reference.
377static bool usagesReturnRValues(const UsageResult &Usages) {
378 for (const auto &U : Usages) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000379 if (U.Expression && !U.Expression->isRValue())
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000380 return false;
381 }
382 return true;
383}
384
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000385/// \brief Returns true if the container is const-qualified.
386static bool containerIsConst(const Expr *ContainerExpr, bool Dereference) {
387 if (const auto *VDec = getReferencedVariable(ContainerExpr)) {
388 QualType CType = VDec->getType();
389 if (Dereference) {
390 if (!CType->isPointerType())
391 return false;
392 CType = CType->getPointeeType();
393 }
394 return CType.isConstQualified();
395 }
396 return false;
397}
398
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000399LoopConvertCheck::RangeDescriptor::RangeDescriptor()
400 : ContainerNeedsDereference(false), DerefByConstRef(false),
401 DerefByValue(false), IsTriviallyCopyable(false) {}
402
Alexander Kornienko04970842015-08-19 09:11:46 +0000403LoopConvertCheck::LoopConvertCheck(StringRef Name, ClangTidyContext *Context)
404 : ClangTidyCheck(Name, Context), TUInfo(new TUTrackingInfo),
405 MinConfidence(StringSwitch<Confidence::Level>(
406 Options.get("MinConfidence", "reasonable"))
407 .Case("safe", Confidence::CL_Safe)
408 .Case("risky", Confidence::CL_Risky)
409 .Default(Confidence::CL_Reasonable)) {}
410
411void LoopConvertCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
412 SmallVector<std::string, 3> Confs{"risky", "reasonable", "safe"};
413 Options.store(Opts, "MinConfidence", Confs[static_cast<int>(MinConfidence)]);
414}
415
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000416void LoopConvertCheck::registerMatchers(MatchFinder *Finder) {
417 // Only register the matchers for C++. Because this checker is used for
418 // modernization, it is reasonable to run it on any C++ standard with the
419 // assumption the user is trying to modernize their codebase.
420 if (!getLangOpts().CPlusPlus)
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000421 return;
422
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000423 Finder->addMatcher(makeArrayLoopMatcher(), this);
424 Finder->addMatcher(makeIteratorLoopMatcher(), this);
425 Finder->addMatcher(makePseudoArrayLoopMatcher(), this);
426}
427
428/// \brief Computes the changes needed to convert a given for loop, and
429/// applies them.
430void LoopConvertCheck::doConversion(
431 ASTContext *Context, const VarDecl *IndexVar, const VarDecl *MaybeContainer,
432 const UsageResult &Usages, const DeclStmt *AliasDecl, bool AliasUseRequired,
433 bool AliasFromForInit, const ForStmt *Loop, RangeDescriptor Descriptor) {
434 auto Diag = diag(Loop->getForLoc(), "use range-based for loop instead");
Alexander Kornienko04970842015-08-19 09:11:46 +0000435
436 std::string VarName;
437 bool VarNameFromAlias = (Usages.size() == 1) && AliasDecl;
438 bool AliasVarIsRef = false;
439
440 if (VarNameFromAlias) {
441 const auto *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());
442 VarName = AliasVar->getName().str();
443 AliasVarIsRef = AliasVar->getType()->isReferenceType();
444
445 // We keep along the entire DeclStmt to keep the correct range here.
446 const SourceRange &ReplaceRange = AliasDecl->getSourceRange();
447
448 std::string ReplacementText;
449 if (AliasUseRequired) {
450 ReplacementText = VarName;
451 } else if (AliasFromForInit) {
452 // FIXME: Clang includes the location of the ';' but only for DeclStmt's
453 // in a for loop's init clause. Need to put this ';' back while removing
454 // the declaration of the alias variable. This is probably a bug.
455 ReplacementText = ";";
456 }
457
458 Diag << FixItHint::CreateReplacement(
459 CharSourceRange::getTokenRange(ReplaceRange), ReplacementText);
460 // No further replacements are made to the loop, since the iterator or index
461 // was used exactly once - in the initialization of AliasVar.
462 } else {
463 VariableNamer Namer(&TUInfo->getGeneratedDecls(),
464 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000465 Loop, IndexVar, MaybeContainer, Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000466 VarName = Namer.createIndexName();
467 // First, replace all usages of the array subscript expression with our new
468 // variable.
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000469 for (const auto &Usage : Usages) {
470 std::string ReplaceText;
471 if (Usage.Expression) {
472 // If this is an access to a member through the arrow operator, after
473 // the replacement it must be accessed through the '.' operator.
474 ReplaceText = Usage.Kind == Usage::UK_MemberThroughArrow ? VarName + "."
475 : VarName;
476 } else {
477 // The Usage expression is only null in case of lambda captures (which
478 // are VarDecl). If the index is captured by value, add '&' to capture
479 // by reference instead.
480 ReplaceText =
481 Usage.Kind == Usage::UK_CaptureByCopy ? "&" + VarName : VarName;
482 }
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000483 TUInfo->getReplacedVars().insert(std::make_pair(Loop, IndexVar));
Alexander Kornienko04970842015-08-19 09:11:46 +0000484 Diag << FixItHint::CreateReplacement(
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000485 CharSourceRange::getTokenRange(Usage.Range), ReplaceText);
Alexander Kornienko04970842015-08-19 09:11:46 +0000486 }
487 }
488
489 // Now, we need to construct the new range expression.
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000490 SourceRange ParenRange(Loop->getLParenLoc(), Loop->getRParenLoc());
Alexander Kornienko04970842015-08-19 09:11:46 +0000491
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000492 QualType AutoType = Context->getAutoDeductType();
Alexander Kornienko04970842015-08-19 09:11:46 +0000493
494 // If the new variable name is from the aliased variable, then the reference
495 // type for the new variable should only be used if the aliased variable was
496 // declared as a reference.
497 if (!VarNameFromAlias || AliasVarIsRef) {
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000498 if (Descriptor.DerefByConstRef) {
499 AutoType =
500 Context->getLValueReferenceType(Context->getConstType(AutoType));
501 } else if (Descriptor.DerefByValue) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000502 if (!Descriptor.IsTriviallyCopyable)
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000503 AutoType = Context->getRValueReferenceType(AutoType);
Alexander Kornienko04970842015-08-19 09:11:46 +0000504 } else {
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000505 AutoType = Context->getLValueReferenceType(AutoType);
Alexander Kornienko04970842015-08-19 09:11:46 +0000506 }
507 }
508
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000509 StringRef MaybeDereference = Descriptor.ContainerNeedsDereference ? "*" : "";
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000510 std::string TypeString = AutoType.getAsString();
Alexander Kornienkoe1292f82015-08-19 16:54:51 +0000511 std::string Range = ("(" + TypeString + " " + VarName + " : " +
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000512 MaybeDereference + Descriptor.ContainerString + ")")
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000513 .str();
Alexander Kornienko04970842015-08-19 09:11:46 +0000514 Diag << FixItHint::CreateReplacement(
515 CharSourceRange::getTokenRange(ParenRange), Range);
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000516 TUInfo->getGeneratedDecls().insert(make_pair(Loop, VarName));
Alexander Kornienko04970842015-08-19 09:11:46 +0000517}
518
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000519/// \brief Returns a string which refers to the container iterated over.
520StringRef LoopConvertCheck::getContainerString(ASTContext *Context,
521 const ForStmt *Loop,
522 const Expr *ContainerExpr) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000523 StringRef ContainerString;
524 if (isa<CXXThisExpr>(ContainerExpr->IgnoreParenImpCasts())) {
525 ContainerString = "this";
526 } else {
527 ContainerString =
528 getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),
529 ContainerExpr->getSourceRange());
530 }
531
532 return ContainerString;
533}
534
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000535/// \brief Determines what kind of 'auto' must be used after converting a for
536/// loop that iterates over an array or pseudoarray.
537void LoopConvertCheck::getArrayLoopQualifiers(ASTContext *Context,
538 const BoundNodes &Nodes,
539 const Expr *ContainerExpr,
540 const UsageResult &Usages,
541 RangeDescriptor &Descriptor) {
542 // On arrays and pseudoarrays, we must figure out the qualifiers from the
543 // usages.
544 if (usagesAreConst(Usages)) {
545 Descriptor.DerefByConstRef = true;
546 } else {
547 if (usagesReturnRValues(Usages)) {
548 // If the index usages (dereference, subscript, at, ...) return rvalues,
549 // then we should not use a reference, because we need to keep the code
550 // correct if it mutates the returned objects.
551 Descriptor.DerefByValue = true;
552 // Try to find the type of the elements on the container, to check if
553 // they are trivially copyable.
554 for (const Usage &U : Usages) {
555 if (!U.Expression || U.Expression->getType().isNull())
556 continue;
557 QualType Type = U.Expression->getType().getCanonicalType();
558 if (U.Kind == Usage::UK_MemberThroughArrow) {
559 if (!Type->isPointerType())
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000560 continue;
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000561 Type = Type->getPointeeType();
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000562 }
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000563 Descriptor.IsTriviallyCopyable = Type.isTriviallyCopyableType(*Context);
564 break;
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000565 }
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000566 } else if (containerIsConst(ContainerExpr,
567 Descriptor.ContainerNeedsDereference)) {
568 // The usages are lvalue references, we add a 'const' if the container
569 // is 'const'. This will always be the case with const arrays (unless
570 // usagesAreConst() returned true).
571 Descriptor.DerefByConstRef = true;
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000572 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000573 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000574}
575
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000576/// \brief Determines what kind of 'auto' must be used after converting an
577/// iterator based for loop.
578void LoopConvertCheck::getIteratorLoopQualifiers(ASTContext *Context,
579 const BoundNodes &Nodes,
580 RangeDescriptor &Descriptor) {
581 // The matchers for iterator loops provide bound nodes to obtain this
582 // information.
583 const auto *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
584 QualType CanonicalInitVarType = InitVar->getType().getCanonicalType();
585 const auto *DerefByValueType =
586 Nodes.getNodeAs<QualType>(DerefByValueResultName);
587 Descriptor.DerefByValue = DerefByValueType;
Alexander Kornienko04970842015-08-19 09:11:46 +0000588
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000589 if (Descriptor.DerefByValue) {
590 // If the dereference operator returns by value then test for the
591 // canonical const qualification of the init variable type.
592 Descriptor.DerefByConstRef = CanonicalInitVarType.isConstQualified();
593 Descriptor.IsTriviallyCopyable =
594 DerefByValueType->isTriviallyCopyableType(*Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000595 } else {
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000596 if (const auto *DerefType =
597 Nodes.getNodeAs<QualType>(DerefByRefResultName)) {
598 // A node will only be bound with DerefByRefResultName if we're dealing
599 // with a user-defined iterator type. Test the const qualification of
600 // the reference type.
601 Descriptor.DerefByConstRef = (*DerefType)
602 ->getAs<ReferenceType>()
603 ->getPointeeType()
604 .isConstQualified();
605 } else {
606 // By nature of the matcher this case is triggered only for built-in
607 // iterator types (i.e. pointers).
608 assert(isa<PointerType>(CanonicalInitVarType) &&
609 "Non-class iterator type is not a pointer type");
610
611 // We test for const qualification of the pointed-at type.
612 Descriptor.DerefByConstRef =
613 CanonicalInitVarType->getPointeeType().isConstQualified();
614 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000615 }
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000616}
617
618/// \brief Determines the parameters needed to build the range replacement.
619void LoopConvertCheck::determineRangeDescriptor(
620 ASTContext *Context, const BoundNodes &Nodes, const ForStmt *Loop,
621 LoopFixerKind FixerKind, const Expr *ContainerExpr,
622 const UsageResult &Usages, RangeDescriptor &Descriptor) {
623 Descriptor.ContainerString = getContainerString(Context, Loop, ContainerExpr);
624
625 if (FixerKind == LFK_Iterator)
626 getIteratorLoopQualifiers(Context, Nodes, Descriptor);
627 else
628 getArrayLoopQualifiers(Context, Nodes, ContainerExpr, Usages, Descriptor);
629}
630
631/// \brief Check some of the conditions that must be met for the loop to be
632/// convertible.
633bool LoopConvertCheck::isConvertible(ASTContext *Context,
634 const ast_matchers::BoundNodes &Nodes,
635 const ForStmt *Loop,
636 LoopFixerKind FixerKind) {
637 // If we already modified the range of this for loop, don't do any further
638 // updates on this iteration.
639 if (TUInfo->getReplacedVars().count(Loop))
640 return false;
Alexander Kornienko04970842015-08-19 09:11:46 +0000641
642 // Check that we have exactly one index variable and at most one end variable.
643 const auto *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
644 const auto *CondVar = Nodes.getDeclAs<VarDecl>(ConditionVarName);
645 const auto *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
646 if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000647 return false;
Alexander Kornienko04970842015-08-19 09:11:46 +0000648 const auto *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
649 const auto *ConditionEndVar = Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
650 if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000651 return false;
Alexander Kornienko04970842015-08-19 09:11:46 +0000652
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000653 // FIXME: Try to put most of this logic inside a matcher.
Alexander Kornienko04970842015-08-19 09:11:46 +0000654 if (FixerKind == LFK_Iterator) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000655 QualType InitVarType = InitVar->getType();
656 QualType CanonicalInitVarType = InitVarType.getCanonicalType();
657
658 const auto *BeginCall = Nodes.getNodeAs<CXXMemberCallExpr>(BeginCallName);
659 assert(BeginCall && "Bad Callback. No begin call expression");
660 QualType CanonicalBeginType =
661 BeginCall->getMethodDecl()->getReturnType().getCanonicalType();
662 if (CanonicalBeginType->isPointerType() &&
663 CanonicalInitVarType->isPointerType()) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000664 // If the initializer and the variable are both pointers check if the
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000665 // un-qualified pointee types match, otherwise we don't use auto.
666 if (!Context->hasSameUnqualifiedType(
667 CanonicalBeginType->getPointeeType(),
668 CanonicalInitVarType->getPointeeType()))
669 return false;
670 } else if (!Context->hasSameType(CanonicalInitVarType,
671 CanonicalBeginType)) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000672 // Check for qualified types to avoid conversions from non-const to const
673 // iterator types.
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000674 return false;
Alexander Kornienko04970842015-08-19 09:11:46 +0000675 }
676 } else if (FixerKind == LFK_PseudoArray) {
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000677 // This call is required to obtain the container.
678 const auto *EndCall = Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
679 if (!EndCall || !dyn_cast<MemberExpr>(EndCall->getCallee()))
680 return false;
681 }
682 return true;
683}
684
685void LoopConvertCheck::check(const MatchFinder::MatchResult &Result) {
686 const BoundNodes &Nodes = Result.Nodes;
687 Confidence ConfidenceLevel(Confidence::CL_Safe);
688 ASTContext *Context = Result.Context;
689
690 const ForStmt *Loop;
691 LoopFixerKind FixerKind;
692 RangeDescriptor Descriptor;
693
694 if ((Loop = Nodes.getStmtAs<ForStmt>(LoopNameArray))) {
695 FixerKind = LFK_Array;
696 } else if ((Loop = Nodes.getStmtAs<ForStmt>(LoopNameIterator))) {
697 FixerKind = LFK_Iterator;
698 } else {
699 Loop = Nodes.getStmtAs<ForStmt>(LoopNamePseudoArray);
700 assert(Loop && "Bad Callback. No for statement");
701 FixerKind = LFK_PseudoArray;
702 }
703
704 if (!isConvertible(Context, Nodes, Loop, FixerKind))
705 return;
706
707 const auto *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
708 const auto *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
709
710 // If the loop calls end()/size() after each iteration, lower our confidence
711 // level.
712 if (FixerKind != LFK_Array && !EndVar)
713 ConfidenceLevel.lowerTo(Confidence::CL_Reasonable);
714
715 // If the end comparison isn't a variable, we can try to work with the
716 // expression the loop variable is being tested against instead.
717 const auto *EndCall = Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
718 const auto *BoundExpr = Nodes.getStmtAs<Expr>(ConditionBoundName);
719
720 // Find container expression of iterators and pseudoarrays, and determine if
721 // this expression needs to be dereferenced to obtain the container.
722 // With array loops, the container is often discovered during the
723 // ForLoopIndexUseVisitor traversal.
724 const Expr *ContainerExpr = nullptr;
725 if (FixerKind == LFK_Iterator) {
726 ContainerExpr = findContainer(Context, LoopVar->getInit(),
727 EndVar ? EndVar->getInit() : EndCall,
728 &Descriptor.ContainerNeedsDereference);
729 } else if (FixerKind == LFK_PseudoArray) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000730 ContainerExpr = EndCall->getImplicitObjectArgument();
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000731 Descriptor.ContainerNeedsDereference =
732 dyn_cast<MemberExpr>(EndCall->getCallee())->isArrow();
Alexander Kornienko04970842015-08-19 09:11:46 +0000733 }
734
735 // We must know the container or an array length bound.
736 if (!ContainerExpr && !BoundExpr)
737 return;
738
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000739 ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
740 BoundExpr,
741 Descriptor.ContainerNeedsDereference);
742
743 // Find expressions and variables on which the container depends.
744 if (ContainerExpr) {
745 ComponentFinderASTVisitor ComponentFinder;
746 ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
747 Finder.addComponents(ComponentFinder.getComponents());
748 }
749
750 // Find usages of the loop index. If they are not used in a convertible way,
751 // stop here.
752 if (!Finder.findAndVerifyUsages(Loop->getBody()))
753 return;
754 ConfidenceLevel.lowerTo(Finder.getConfidenceLevel());
755
756 // Obtain the container expression, if we don't have it yet.
757 if (FixerKind == LFK_Array) {
758 ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();
759
760 // Very few loops are over expressions that generate arrays rather than
761 // array variables. Consider loops over arrays that aren't just represented
762 // by a variable to be risky conversions.
763 if (!getReferencedVariable(ContainerExpr) &&
764 !isDirectMemberExpr(ContainerExpr))
765 ConfidenceLevel.lowerTo(Confidence::CL_Risky);
766 }
767
768 // Find out which qualifiers we have to use in the loop range.
769 const UsageResult &Usages = Finder.getUsages();
770 determineRangeDescriptor(Context, Nodes, Loop, FixerKind, ContainerExpr,
771 Usages, Descriptor);
772
773 // Ensure that we do not try to move an expression dependent on a local
774 // variable declared inside the loop outside of it.
775 // FIXME: Determine when the external dependency isn't an expression converted
776 // by another loop.
777 TUInfo->getParentFinder().gatherAncestors(Context->getTranslationUnitDecl());
778 DependencyFinderASTVisitor DependencyFinder(
779 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
780 &TUInfo->getParentFinder().getDeclToParentStmtMap(),
781 &TUInfo->getReplacedVars(), Loop);
782
783 if (DependencyFinder.dependsOnInsideVariable(ContainerExpr) ||
784 Descriptor.ContainerString.empty() || Usages.empty() ||
785 ConfidenceLevel.getLevel() < MinConfidence)
Alexander Kornienko04970842015-08-19 09:11:46 +0000786 return;
787
Angel Garcia Gomezf41a6312015-09-21 09:32:59 +0000788 doConversion(Context, LoopVar, getReferencedVariable(ContainerExpr), Usages,
789 Finder.getAliasDecl(), Finder.aliasUseRequired(),
790 Finder.aliasFromForInit(), Loop, Descriptor);
Alexander Kornienko04970842015-08-19 09:11:46 +0000791}
792
793} // namespace modernize
794} // namespace tidy
795} // namespace clang