blob: 15ca113f6da4a1dca9a7d879f60bae535ba5a460 [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
Alexander Kornienko04970842015-08-19 09:11:46 +0000399LoopConvertCheck::LoopConvertCheck(StringRef Name, ClangTidyContext *Context)
400 : ClangTidyCheck(Name, Context), TUInfo(new TUTrackingInfo),
401 MinConfidence(StringSwitch<Confidence::Level>(
402 Options.get("MinConfidence", "reasonable"))
403 .Case("safe", Confidence::CL_Safe)
404 .Case("risky", Confidence::CL_Risky)
405 .Default(Confidence::CL_Reasonable)) {}
406
407void LoopConvertCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
408 SmallVector<std::string, 3> Confs{"risky", "reasonable", "safe"};
409 Options.store(Opts, "MinConfidence", Confs[static_cast<int>(MinConfidence)]);
410}
411
412/// \brief Computes the changes needed to convert a given for loop, and
413/// applies it.
414void LoopConvertCheck::doConversion(
415 ASTContext *Context, const VarDecl *IndexVar, const VarDecl *MaybeContainer,
416 StringRef ContainerString, const UsageResult &Usages,
417 const DeclStmt *AliasDecl, bool AliasUseRequired, bool AliasFromForInit,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000418 const ForStmt *TheLoop, RangeDescriptor Descriptor) {
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000419 // If there aren't any usages, converting the loop would generate an unused
420 // variable warning.
421 if (Usages.size() == 0)
422 return;
423
Alexander Kornienko04970842015-08-19 09:11:46 +0000424 auto Diag = diag(TheLoop->getForLoc(), "use range-based for loop instead");
425
426 std::string VarName;
427 bool VarNameFromAlias = (Usages.size() == 1) && AliasDecl;
428 bool AliasVarIsRef = false;
429
430 if (VarNameFromAlias) {
431 const auto *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());
432 VarName = AliasVar->getName().str();
433 AliasVarIsRef = AliasVar->getType()->isReferenceType();
434
435 // We keep along the entire DeclStmt to keep the correct range here.
436 const SourceRange &ReplaceRange = AliasDecl->getSourceRange();
437
438 std::string ReplacementText;
439 if (AliasUseRequired) {
440 ReplacementText = VarName;
441 } else if (AliasFromForInit) {
442 // FIXME: Clang includes the location of the ';' but only for DeclStmt's
443 // in a for loop's init clause. Need to put this ';' back while removing
444 // the declaration of the alias variable. This is probably a bug.
445 ReplacementText = ";";
446 }
447
448 Diag << FixItHint::CreateReplacement(
449 CharSourceRange::getTokenRange(ReplaceRange), ReplacementText);
450 // No further replacements are made to the loop, since the iterator or index
451 // was used exactly once - in the initialization of AliasVar.
452 } else {
453 VariableNamer Namer(&TUInfo->getGeneratedDecls(),
454 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
455 TheLoop, IndexVar, MaybeContainer, Context);
456 VarName = Namer.createIndexName();
457 // First, replace all usages of the array subscript expression with our new
458 // variable.
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000459 for (const auto &Usage : Usages) {
460 std::string ReplaceText;
461 if (Usage.Expression) {
462 // If this is an access to a member through the arrow operator, after
463 // the replacement it must be accessed through the '.' operator.
464 ReplaceText = Usage.Kind == Usage::UK_MemberThroughArrow ? VarName + "."
465 : VarName;
466 } else {
467 // The Usage expression is only null in case of lambda captures (which
468 // are VarDecl). If the index is captured by value, add '&' to capture
469 // by reference instead.
470 ReplaceText =
471 Usage.Kind == Usage::UK_CaptureByCopy ? "&" + VarName : VarName;
472 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000473 TUInfo->getReplacedVars().insert(std::make_pair(TheLoop, IndexVar));
474 Diag << FixItHint::CreateReplacement(
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000475 CharSourceRange::getTokenRange(Usage.Range), ReplaceText);
Alexander Kornienko04970842015-08-19 09:11:46 +0000476 }
477 }
478
479 // Now, we need to construct the new range expression.
480 SourceRange ParenRange(TheLoop->getLParenLoc(), TheLoop->getRParenLoc());
481
482 QualType AutoRefType = Context->getAutoDeductType();
483
484 // If the new variable name is from the aliased variable, then the reference
485 // type for the new variable should only be used if the aliased variable was
486 // declared as a reference.
487 if (!VarNameFromAlias || AliasVarIsRef) {
488 // If an iterator's operator*() returns a 'T&' we can bind that to 'auto&'.
489 // If operator*() returns 'T' we can bind that to 'auto&&' which will deduce
490 // to 'T&&&'.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000491 if (Descriptor.DerefByValue) {
492 if (!Descriptor.IsTriviallyCopyable)
493 AutoRefType = Context->getRValueReferenceType(AutoRefType);
Alexander Kornienko04970842015-08-19 09:11:46 +0000494 } else {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000495 if (Descriptor.DerefByConstRef)
Alexander Kornienko04970842015-08-19 09:11:46 +0000496 AutoRefType = Context->getConstType(AutoRefType);
497 AutoRefType = Context->getLValueReferenceType(AutoRefType);
498 }
499 }
500
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000501 StringRef MaybeDereference = Descriptor.ContainerNeedsDereference ? "*" : "";
Alexander Kornienkoe1292f82015-08-19 16:54:51 +0000502 std::string TypeString = AutoRefType.getAsString();
503 std::string Range = ("(" + TypeString + " " + VarName + " : " +
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000504 MaybeDereference + ContainerString + ")")
505 .str();
Alexander Kornienko04970842015-08-19 09:11:46 +0000506 Diag << FixItHint::CreateReplacement(
507 CharSourceRange::getTokenRange(ParenRange), Range);
508 TUInfo->getGeneratedDecls().insert(make_pair(TheLoop, VarName));
509}
510
511/// \brief Determine if the change should be deferred or rejected, returning
512/// text which refers to the container iterated over if the change should
513/// proceed.
514StringRef LoopConvertCheck::checkRejections(ASTContext *Context,
515 const Expr *ContainerExpr,
516 const ForStmt *TheLoop) {
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000517 // If we already modified the range of this for loop, don't do any further
Alexander Kornienko04970842015-08-19 09:11:46 +0000518 // updates on this iteration.
519 if (TUInfo->getReplacedVars().count(TheLoop))
520 return "";
521
522 Context->getTranslationUnitDecl();
523 TUInfo->getParentFinder();
524 TUInfo->getParentFinder().gatherAncestors(Context->getTranslationUnitDecl());
525 // Ensure that we do not try to move an expression dependent on a local
526 // variable declared inside the loop outside of it.
527 DependencyFinderASTVisitor DependencyFinder(
528 &TUInfo->getParentFinder().getStmtToParentStmtMap(),
529 &TUInfo->getParentFinder().getDeclToParentStmtMap(),
530 &TUInfo->getReplacedVars(), TheLoop);
531
532 // FIXME: Determine when the external dependency isn't an expression converted
533 // by another loop.
534 if (DependencyFinder.dependsOnInsideVariable(ContainerExpr))
535 return "";
536
537 StringRef ContainerString;
538 if (isa<CXXThisExpr>(ContainerExpr->IgnoreParenImpCasts())) {
539 ContainerString = "this";
540 } else {
541 ContainerString =
542 getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),
543 ContainerExpr->getSourceRange());
544 }
545
546 return ContainerString;
547}
548
549/// \brief Given a loop header that would be convertible, discover all usages
550/// of the index variable and convert the loop if possible.
551void LoopConvertCheck::findAndVerifyUsages(
552 ASTContext *Context, const VarDecl *LoopVar, const VarDecl *EndVar,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000553 const Expr *ContainerExpr, const Expr *BoundExpr, const ForStmt *TheLoop,
554 LoopFixerKind FixerKind, RangeDescriptor Descriptor) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000555 ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000556 BoundExpr,
557 Descriptor.ContainerNeedsDereference);
Alexander Kornienko04970842015-08-19 09:11:46 +0000558
559 if (ContainerExpr) {
560 ComponentFinderASTVisitor ComponentFinder;
561 ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
562 Finder.addComponents(ComponentFinder.getComponents());
563 }
564
565 if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
566 return;
567
568 Confidence ConfidenceLevel(Finder.getConfidenceLevel());
569 if (FixerKind == LFK_Array) {
570 // The array being indexed by IndexVar was discovered during traversal.
571 ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000572
Alexander Kornienko04970842015-08-19 09:11:46 +0000573 // Very few loops are over expressions that generate arrays rather than
574 // array variables. Consider loops over arrays that aren't just represented
575 // by a variable to be risky conversions.
576 if (!getReferencedVariable(ContainerExpr) &&
577 !isDirectMemberExpr(ContainerExpr))
578 ConfidenceLevel.lowerTo(Confidence::CL_Risky);
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000579
580 // Use 'const' if the array is const.
581 if (containerIsConst(ContainerExpr, Descriptor.ContainerNeedsDereference))
582 Descriptor.DerefByConstRef = true;
583
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000584 } else if (FixerKind == LFK_PseudoArray) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000585 if (!Descriptor.DerefByValue && !Descriptor.DerefByConstRef) {
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000586 const UsageResult &Usages = Finder.getUsages();
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000587 if (usagesAreConst(Usages) ||
588 containerIsConst(ContainerExpr,
589 Descriptor.ContainerNeedsDereference)) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000590 Descriptor.DerefByConstRef = true;
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000591 } else if (usagesReturnRValues(Usages)) {
592 // If the index usages (dereference, subscript, at) return RValues,
593 // then we should not use a non-const reference.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000594 Descriptor.DerefByValue = true;
595 // Try to find the type of the elements on the container from the
596 // usages.
597 for (const Usage &U : Usages) {
598 if (!U.Expression || U.Expression->getType().isNull())
599 continue;
600 QualType Type = U.Expression->getType().getCanonicalType();
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000601 if (U.Kind == Usage::UK_MemberThroughArrow) {
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000602 if (!Type->isPointerType())
603 continue;
604 Type = Type->getPointeeType();
605 }
606 Descriptor.IsTriviallyCopyable =
607 Type.isTriviallyCopyableType(*Context);
608 }
Angel Garcia Gomez692cbb52015-09-01 15:05:15 +0000609 }
610 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000611 }
612
613 StringRef ContainerString = checkRejections(Context, ContainerExpr, TheLoop);
614
615 if (ContainerString.empty() || ConfidenceLevel.getLevel() < MinConfidence)
616 return;
617
618 doConversion(Context, LoopVar, getReferencedVariable(ContainerExpr),
619 ContainerString, Finder.getUsages(), Finder.getAliasDecl(),
620 Finder.aliasUseRequired(), Finder.aliasFromForInit(), TheLoop,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000621 Descriptor);
Alexander Kornienko04970842015-08-19 09:11:46 +0000622}
623
624void LoopConvertCheck::registerMatchers(MatchFinder *Finder) {
Aaron Ballman8b0583e2015-08-28 17:58:10 +0000625 // Only register the matchers for C++. Because this checker is used for
626 // modernization, it is reasonable to run it on any C++ standard with the
627 // assumption the user is trying to modernize their codebase.
628 if (getLangOpts().CPlusPlus) {
629 Finder->addMatcher(makeArrayLoopMatcher(), this);
630 Finder->addMatcher(makeIteratorLoopMatcher(), this);
631 Finder->addMatcher(makePseudoArrayLoopMatcher(), this);
632 }
Alexander Kornienko04970842015-08-19 09:11:46 +0000633}
634
635void LoopConvertCheck::check(const MatchFinder::MatchResult &Result) {
636 const BoundNodes &Nodes = Result.Nodes;
637 Confidence ConfidenceLevel(Confidence::CL_Safe);
638 ASTContext *Context = Result.Context;
639
640 const ForStmt *TheLoop;
641 LoopFixerKind FixerKind;
642
643 if ((TheLoop = Nodes.getStmtAs<ForStmt>(LoopNameArray))) {
644 FixerKind = LFK_Array;
645 } else if ((TheLoop = Nodes.getStmtAs<ForStmt>(LoopNameIterator))) {
646 FixerKind = LFK_Iterator;
647 } else {
648 TheLoop = Nodes.getStmtAs<ForStmt>(LoopNamePseudoArray);
649 assert(TheLoop && "Bad Callback. No for statement");
650 FixerKind = LFK_PseudoArray;
651 }
652
653 // Check that we have exactly one index variable and at most one end variable.
654 const auto *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
655 const auto *CondVar = Nodes.getDeclAs<VarDecl>(ConditionVarName);
656 const auto *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
657 if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
658 return;
659 const auto *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
660 const auto *ConditionEndVar = Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
661 if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
662 return;
663
664 // If the end comparison isn't a variable, we can try to work with the
665 // expression the loop variable is being tested against instead.
666 const auto *EndCall = Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
667 const auto *BoundExpr = Nodes.getStmtAs<Expr>(ConditionBoundName);
Angel Garcia Gomezbb9ca542015-09-11 10:02:07 +0000668
Alexander Kornienko04970842015-08-19 09:11:46 +0000669 // If the loop calls end()/size() after each iteration, lower our confidence
670 // level.
671 if (FixerKind != LFK_Array && !EndVar)
672 ConfidenceLevel.lowerTo(Confidence::CL_Reasonable);
673
674 const Expr *ContainerExpr = nullptr;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000675 RangeDescriptor Descriptor{false, false, false, false};
Alexander Kornienko04970842015-08-19 09:11:46 +0000676 // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
677 // don't allow the ight-recursive checks in digThroughConstructors.
678 if (FixerKind == LFK_Iterator) {
679 ContainerExpr = findContainer(Context, LoopVar->getInit(),
680 EndVar ? EndVar->getInit() : EndCall,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000681 &Descriptor.ContainerNeedsDereference);
Alexander Kornienko04970842015-08-19 09:11:46 +0000682
683 QualType InitVarType = InitVar->getType();
684 QualType CanonicalInitVarType = InitVarType.getCanonicalType();
685
686 const auto *BeginCall = Nodes.getNodeAs<CXXMemberCallExpr>(BeginCallName);
687 assert(BeginCall && "Bad Callback. No begin call expression");
688 QualType CanonicalBeginType =
689 BeginCall->getMethodDecl()->getReturnType().getCanonicalType();
690 if (CanonicalBeginType->isPointerType() &&
691 CanonicalInitVarType->isPointerType()) {
692 QualType BeginPointeeType = CanonicalBeginType->getPointeeType();
693 QualType InitPointeeType = CanonicalInitVarType->getPointeeType();
694 // If the initializer and the variable are both pointers check if the
695 // un-qualified pointee types match otherwise we don't use auto.
696 if (!Context->hasSameUnqualifiedType(InitPointeeType, BeginPointeeType))
697 return;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000698 Descriptor.IsTriviallyCopyable =
699 BeginPointeeType.isTriviallyCopyableType(*Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000700 } else {
701 // Check for qualified types to avoid conversions from non-const to const
702 // iterator types.
703 if (!Context->hasSameType(CanonicalInitVarType, CanonicalBeginType))
704 return;
705 }
706
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000707 const auto *DerefByValueType =
708 Nodes.getNodeAs<QualType>(DerefByValueResultName);
709 Descriptor.DerefByValue = DerefByValueType;
710 if (!Descriptor.DerefByValue) {
Alexander Kornienko04970842015-08-19 09:11:46 +0000711 if (const auto *DerefType =
712 Nodes.getNodeAs<QualType>(DerefByRefResultName)) {
713 // A node will only be bound with DerefByRefResultName if we're dealing
714 // with a user-defined iterator type. Test the const qualification of
715 // the reference type.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000716 Descriptor.DerefByConstRef = (*DerefType)
717 ->getAs<ReferenceType>()
718 ->getPointeeType()
719 .isConstQualified();
Alexander Kornienko04970842015-08-19 09:11:46 +0000720 } else {
721 // By nature of the matcher this case is triggered only for built-in
722 // iterator types (i.e. pointers).
723 assert(isa<PointerType>(CanonicalInitVarType) &&
724 "Non-class iterator type is not a pointer type");
725 QualType InitPointeeType = CanonicalInitVarType->getPointeeType();
726 QualType BeginPointeeType = CanonicalBeginType->getPointeeType();
727 // If the initializer and variable have both the same type just use auto
728 // otherwise we test for const qualification of the pointed-at type.
729 if (!Context->hasSameType(InitPointeeType, BeginPointeeType))
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000730 Descriptor.DerefByConstRef = InitPointeeType.isConstQualified();
Alexander Kornienko04970842015-08-19 09:11:46 +0000731 }
732 } else {
733 // If the dereference operator returns by value then test for the
734 // canonical const qualification of the init variable type.
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000735 Descriptor.DerefByConstRef = CanonicalInitVarType.isConstQualified();
736 Descriptor.IsTriviallyCopyable =
737 DerefByValueType->isTriviallyCopyableType(*Context);
Alexander Kornienko04970842015-08-19 09:11:46 +0000738 }
739 } else if (FixerKind == LFK_PseudoArray) {
740 if (!EndCall)
741 return;
742 ContainerExpr = EndCall->getImplicitObjectArgument();
743 const auto *Member = dyn_cast<MemberExpr>(EndCall->getCallee());
744 if (!Member)
745 return;
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000746 Descriptor.ContainerNeedsDereference = Member->isArrow();
Alexander Kornienko04970842015-08-19 09:11:46 +0000747 }
748
749 // We must know the container or an array length bound.
750 if (!ContainerExpr && !BoundExpr)
751 return;
752
753 if (ConfidenceLevel.getLevel() < MinConfidence)
754 return;
755
756 findAndVerifyUsages(Context, LoopVar, EndVar, ContainerExpr, BoundExpr,
Angel Garcia Gomezd930ef72015-09-08 09:01:21 +0000757 TheLoop, FixerKind, Descriptor);
Alexander Kornienko04970842015-08-19 09:11:46 +0000758}
759
760} // namespace modernize
761} // namespace tidy
762} // namespace clang