1 #include "LoopActions.h"
2 #include "LoopMatchers.h"
3 #include "VariableNaming.h"
5 #include "clang/Lex/Lexer.h"
8 namespace loop_migrate {
10 using namespace clang::ast_matchers;
11 using namespace clang::tooling;
13 /// \brief The information needed to describe a valid convertible usage
14 /// of an array index or iterator.
20 explicit Usage(const Expr *E)
21 : E(E), IsArrow(false), Range(E->getSourceRange()) { }
22 Usage(const Expr *E, bool IsArrow, SourceRange Range)
23 : E(E), IsArrow(IsArrow), Range(Range) { }
26 /// \brief A class to encapsulate lowering of the tool's confidence level.
29 /// \brief Initialize the default confidence level to the maximum value
31 explicit Confidence(TranslationConfidenceKind Level) :
32 CurrentLevel(Level) {}
34 /// \brief Lower the internal confidence level to Level, but do not raise it.
35 void lowerTo(TranslationConfidenceKind Level) {
36 CurrentLevel = std::min(Level, CurrentLevel);
39 /// \brief Return the internal confidence level.
40 TranslationConfidenceKind get() const { return CurrentLevel; }
42 /// \brief Set the confidence level unconditionally.
43 void resetTo(TranslationConfidenceKind Level) { CurrentLevel = Level; }
46 TranslationConfidenceKind CurrentLevel;
49 /// \brief Discover usages of expressions consisting of index or iterator
52 /// Given an index variable, recursively crawls a for loop to discover if the
53 /// index variable is used in a way consistent with range-based for loop access.
54 class ForLoopIndexUseVisitor
55 : public RecursiveASTVisitor<ForLoopIndexUseVisitor> {
57 ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar,
58 const VarDecl *EndVar, const Expr *ContainerExpr,
59 const Expr *ArrayBoundExpr,
60 bool ContainerNeedsDereference) :
61 Context(Context), IndexVar(IndexVar), EndVar(EndVar),
62 ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),
63 ContainerNeedsDereference(ContainerNeedsDereference),
64 OnlyUsedAsIndex(true), AliasDecl(NULL), ConfidenceLevel(TCK_Safe) {
66 addComponent(ContainerExpr);
67 llvm::FoldingSetNodeID ID;
68 const Expr *E = ContainerExpr->IgnoreParenImpCasts();
69 E->Profile(ID, *Context, true);
73 /// \brief Finds all uses of IndexVar in Body, placing all usages in Usages,
74 /// and returns true if IndexVar was only used in a way consistent with a
75 /// range-based for loop.
77 /// The general strategy is to reject any DeclRefExprs referencing IndexVar,
78 /// with the exception of certain acceptable patterns.
79 /// For arrays, the DeclRefExpr for IndexVar must appear as the index of an
80 /// ArraySubscriptExpression. Iterator-based loops may dereference
81 /// IndexVar or call methods through operator-> (builtin or overloaded).
82 /// Array-like containers may use IndexVar as a parameter to the at() member
83 /// function and in overloaded operator[].
84 bool findAndVerifyUsages(const Stmt *Body) {
85 TraverseStmt(const_cast<Stmt *>(Body));
86 return OnlyUsedAsIndex && ContainerExpr;
89 /// \brief Add a set of components that we should consider relevant to the
91 void addComponents(const ComponentVector &Components) {
92 // FIXME: add sort(on ID)+unique to avoid extra work.
93 for (ComponentVector::const_iterator I = Components.begin(),
94 E = Components.end(); I != E; ++I)
98 /// \brief Accessor for Usages.
99 const UsageResult &getUsages() const { return Usages; }
101 /// \brief Get the container indexed by IndexVar, if any.
102 const Expr *getContainerIndexed() const {
103 return ContainerExpr;
106 /// \brief Returns the statement declaring the variable created as an alias
107 /// for the loop element, if any.
108 const DeclStmt *getAliasDecl() const { return AliasDecl; }
110 /// \brief Accessor for ConfidenceLevel.
111 TranslationConfidenceKind getConfidenceLevel() const {
112 return ConfidenceLevel.get();
116 /// Typedef used in CRTP functions.
117 typedef RecursiveASTVisitor<ForLoopIndexUseVisitor> VisitorBase;
118 friend class RecursiveASTVisitor<ForLoopIndexUseVisitor>;
120 /// Overriden methods for RecursiveASTVisitor's traversal.
121 bool TraverseArraySubscriptExpr(ArraySubscriptExpr *ASE);
122 bool TraverseCXXMemberCallExpr(CXXMemberCallExpr *MemberCall);
123 bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *OpCall);
124 bool TraverseMemberExpr(MemberExpr *Member);
125 bool TraverseUnaryDeref(UnaryOperator *Uop);
126 bool VisitDeclRefExpr(DeclRefExpr *DRE);
127 bool VisitDeclStmt(DeclStmt *DS);
129 /// \brief Add an expression to the list of expressions on which the container
130 /// expression depends.
131 void addComponent(const Expr *E) {
132 llvm::FoldingSetNodeID ID;
133 const Expr *Node = E->IgnoreParenImpCasts();
134 Node->Profile(ID, *Context, true);
135 DependentExprs.push_back(std::make_pair(Node, ID));
138 // Input member variables:
140 /// The index variable's VarDecl.
141 const VarDecl *IndexVar;
142 /// The loop's 'end' variable, which cannot be mentioned at all.
143 const VarDecl *EndVar;
144 /// The Expr which refers to the container.
145 const Expr *ContainerExpr;
146 /// The Expr which refers to the terminating condition for array-based loops.
147 const Expr *ArrayBoundExpr;
148 bool ContainerNeedsDereference;
150 // Output member variables:
151 /// A container which holds all usages of IndexVar as the index of
152 /// ArraySubscriptExpressions.
154 bool OnlyUsedAsIndex;
155 /// The DeclStmt for an alias to the container element.
156 const DeclStmt *AliasDecl;
157 Confidence ConfidenceLevel;
158 /// \brief A list of expressions on which ContainerExpr depends.
160 /// If any of these expressions are encountered outside of an acceptable usage
161 /// of the loop element, lower our confidence level.
163 std::pair<const Expr *, llvm::FoldingSetNodeID>, 16> DependentExprs;
166 // FIXME: Determine how not to break in the presence of problematic macros.
167 /// \brief Obtain the original source code text from a SourceRange.
168 static StringRef getStringFromRange(SourceManager &SourceMgr,
169 const LangOptions &LangOpts,
171 if (SourceMgr.getFileID(Range.getBegin()) !=
172 SourceMgr.getFileID(Range.getEnd()))
175 CharSourceRange SourceChars(Range, true);
176 return Lexer::getSourceText(SourceChars, SourceMgr, LangOpts);
179 /// \brief Returns the DeclRefExpr represented by E, or NULL if there isn't one.
180 static const DeclRefExpr *getDeclRef(const Expr *E) {
181 return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());
184 /// \brief If the given expression is actually a DeclRefExpr, find and return
185 /// the underlying VarDecl; otherwise, return NULL.
186 static const VarDecl *getReferencedVariable(const Expr *E) {
187 if (const DeclRefExpr *DRE = getDeclRef(E))
188 return dyn_cast<VarDecl>(DRE->getDecl());
192 /// \brief Returns true when the given expression is a member expression
193 /// whose base is `this` (implicitly or not).
194 static bool isDirectMemberExpr(const Expr *E) {
195 if (const MemberExpr *Member = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))
196 return isa<CXXThisExpr>(Member->getBase()->IgnoreParenImpCasts());
200 /// \brief Returns true when two ValueDecls are the same variable.
201 static bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) {
202 return First && Second &&
203 First->getCanonicalDecl() == Second->getCanonicalDecl();
206 /// \brief Determines if an expression is a declaration reference to a
207 /// particular variable.
208 static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) {
211 const DeclRefExpr *DRE = getDeclRef(E);
212 return DRE && areSameVariable(Target, DRE->getDecl());
215 /// \brief Returns true when two Exprs are equivalent.
216 static bool areSameExpr(ASTContext* Context, const Expr *First,
217 const Expr *Second) {
218 if (!First || !Second)
221 llvm::FoldingSetNodeID FirstID, SecondID;
222 First->Profile(FirstID, *Context, true);
223 Second->Profile(SecondID, *Context, true);
224 return FirstID == SecondID;
227 /// \brief Look through conversion/copy constructors to find the explicit
228 /// initialization expression, returning it is found.
230 /// The main idea is that given
232 /// we consider either of these initializations
233 /// vector<int>::iterator it = v.begin();
234 /// vector<int>::iterator it(v.begin());
235 /// and retrieve `v.begin()` as the expression used to initialize `it` but do
237 /// vector<int>::iterator it;
238 /// vector<int>::iterator it(v.begin(), 0); // if this constructor existed
239 /// as being initialized from `v.begin()`
240 static const Expr *digThroughConstructors(const Expr *E) {
243 E = E->IgnoreParenImpCasts();
244 if (const CXXConstructExpr *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {
245 // The initial constructor must take exactly one parameter, but base class
246 // and deferred constructors can take more.
247 if (ConstructExpr->getNumArgs() != 1 ||
248 ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_Complete)
250 E = ConstructExpr->getArg(0);
251 if (const MaterializeTemporaryExpr *MTE =
252 dyn_cast<MaterializeTemporaryExpr>(E))
253 E = MTE->GetTemporaryExpr();
254 return digThroughConstructors(E);
259 /// \brief If the expression is a dereference or call to operator*(), return the
260 /// operand. Otherwise, return NULL.
261 static const Expr *getDereferenceOperand(const Expr *E) {
262 if (const UnaryOperator *Uop = dyn_cast<UnaryOperator>(E))
263 return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : NULL;
265 if (const CXXOperatorCallExpr *OpCall = dyn_cast<CXXOperatorCallExpr>(E))
266 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 ?
267 OpCall->getArg(0) : NULL;
272 /// \brief Returns true when the Container contains an Expr equivalent to E.
273 template<typename ContainerT>
274 static bool containsExpr(ASTContext *Context, const ContainerT *Container,
276 llvm::FoldingSetNodeID ID;
277 E->Profile(ID, *Context, true);
278 for (typename ContainerT::const_iterator I = Container->begin(),
279 End = Container->end(); I != End; ++I)
285 /// \brief Returns true when the index expression is a declaration reference to
288 /// If the index variable is `index`, this function returns true on
289 /// arrayExpression[index];
290 /// containerExpression[index];
292 /// containerExpression[notIndex];
293 static bool isIndexInSubscriptExpr(const Expr *IndexExpr,
294 const VarDecl *IndexVar) {
295 const DeclRefExpr *Idx = getDeclRef(IndexExpr);
296 return Idx && Idx->getType()->isIntegerType()
297 && areSameVariable(IndexVar, Idx->getDecl());
300 /// \brief Returns true when the index expression is a declaration reference to
301 /// IndexVar, Obj is the same expression as SourceExpr after all parens and
302 /// implicit casts are stripped off.
304 /// If PermitDeref is true, IndexExpression may
305 /// be a dereference (overloaded or builtin operator*).
307 /// This function is intended for array-like containers, as it makes sure that
308 /// both the container and the index match.
309 /// If the loop has index variable `index` and iterates over `container`, then
310 /// isIndexInSubscriptExpr returns true for
312 /// container.at(index)
313 /// container->at(index)
315 /// container[notIndex]
316 /// notContainer[index]
317 /// If PermitDeref is true, then isIndexInSubscriptExpr additionally returns
318 /// true on these expressions:
319 /// (*container)[index]
320 /// (*container).at(index)
321 static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
322 const VarDecl *IndexVar, const Expr *Obj,
323 const Expr *SourceExpr, bool PermitDeref) {
324 if (!SourceExpr || !Obj || !isIndexInSubscriptExpr(IndexExpr, IndexVar))
327 if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
328 Obj->IgnoreParenImpCasts()))
331 if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))
332 if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
333 InnerObj->IgnoreParenImpCasts()))
339 /// \brief Returns true when Opcall is a call a one-parameter dereference of
342 /// For example, if the index variable is `index`, returns true for
347 static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall,
348 const VarDecl *IndexVar) {
349 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&
350 exprReferencesVariable(IndexVar, OpCall->getArg(0));
353 /// \brief Returns true when Uop is a dereference of IndexVar.
355 /// For example, if the index variable is `index`, returns true for
360 static bool isDereferenceOfUop(const UnaryOperator *Uop,
361 const VarDecl *IndexVar) {
362 return Uop->getOpcode() == UO_Deref &&
363 exprReferencesVariable(IndexVar, Uop->getSubExpr());
366 /// \brief Determines whether the given Decl defines a variable initialized to
369 /// This is intended to find cases such as
370 /// for (int i = 0; i < arraySize(arr); ++i) {
372 /// // use t, do not use i
375 /// for (iterator i = container.begin(), e = container.end(); i != e; ++i) {
377 /// // use t, do not use i
379 static bool isAliasDecl(const Decl *TheDecl, const VarDecl *IndexVar) {
380 const VarDecl *VDecl = dyn_cast<VarDecl>(TheDecl);
383 if (!VDecl->hasInit())
386 digThroughConstructors(VDecl->getInit()->IgnoreParenImpCasts());
390 switch (Init->getStmtClass()) {
391 case Stmt::ArraySubscriptExprClass: {
392 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(Init);
393 // We don't really care which array is used here. We check to make sure
394 // it was the correct one later, since the AST will traverse it next.
395 return isIndexInSubscriptExpr(ASE->getIdx(), IndexVar);
398 case Stmt::UnaryOperatorClass:
399 return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar);
401 case Stmt::CXXOperatorCallExprClass: {
402 const CXXOperatorCallExpr *OpCall = cast<CXXOperatorCallExpr>(Init);
403 if (OpCall->getOperator() == OO_Star)
404 return isDereferenceOfOpCall(OpCall, IndexVar);
414 /// \brief Determines whether the bound of a for loop condition expression is
415 /// the same as the statically computable size of ArrayType.
420 /// This is intended to permit
421 /// for (int i = 0; i < N; ++i) { /* use arr[i] */ }
422 /// for (int i = 0; i < arraysize(arr); ++i) { /* use arr[i] */ }
423 static bool arrayMatchesBoundExpr(ASTContext *Context,
424 const QualType &ArrayType,
425 const Expr *ConditionExpr) {
426 const Type *T = ArrayType.getCanonicalType().getTypePtr();
427 if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(T)) {
428 llvm::APSInt ConditionSize;
429 if (!ConditionExpr->isIntegerConstantExpr(ConditionSize, *Context))
431 llvm::APSInt ArraySize(CAT->getSize());
432 return llvm::APSInt::isSameValue(ConditionSize, ArraySize);
437 /// \brief If the unary operator is a dereference of IndexVar, include it
438 /// as a valid usage and prune the traversal.
440 /// For example, if container.begin() and container.end() both return pointers
441 /// to int, this makes sure that the initialization for `k` is not counted as an
442 /// unconvertible use of the iterator `i`.
443 /// for (int *i = container.begin(), *e = container.end(); i != e; ++i) {
446 bool ForLoopIndexUseVisitor::TraverseUnaryDeref(UnaryOperator *Uop) {
447 // If we dereference an iterator that's actually a pointer, count the
449 if (isDereferenceOfUop(Uop, IndexVar)) {
450 Usages.push_back(Usage(Uop));
454 return VisitorBase::TraverseUnaryOperator(Uop);
457 /// \brief If the member expression is operator-> (overloaded or not) on
458 /// IndexVar, include it as a valid usage and prune the traversal.
460 /// For example, given
461 /// struct Foo { int bar(); int x; };
463 /// the following uses will be considered convertible:
464 /// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
465 /// int b = i->bar();
466 /// int k = i->x + 1;
469 /// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
470 /// int k = i.insert(1);
472 /// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
473 /// int b = e->bar();
476 bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
477 const Expr *Base = Member->getBase();
478 const DeclRefExpr *Obj = getDeclRef(Base);
479 const Expr *ResultExpr = Member;
481 if (const CXXOperatorCallExpr *Call =
482 dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {
483 // If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then
484 // the MemberExpr does not have the expression we want. We therefore catch
485 // that instance here.
486 // For example, if vector<Foo>::iterator defines operator->(), then the
487 // example `i->bar()` at the top of this function is a CXXMemberCallExpr
488 // referring to `i->` as the member function called. We want just `i`, so
489 // we take the argument to operator->() as the base object.
490 if(Call->getOperator() == OO_Arrow) {
491 assert(Call->getNumArgs() == 1 &&
492 "Operator-> takes more than one argument");
493 Obj = getDeclRef(Call->getArg(0));
495 ExprType = Call->getCallReturnType();
499 if (Member->isArrow() && Obj && exprReferencesVariable(IndexVar, Obj)) {
500 if (ExprType.isNull())
501 ExprType = Obj->getType();
503 assert(ExprType->isPointerType() && "Operator-> returned non-pointer type");
504 // FIXME: This works around not having the location of the arrow operator.
505 // Consider adding OperatorLoc to MemberExpr?
506 SourceLocation ArrowLoc =
507 Lexer::getLocForEndOfToken(Base->getExprLoc(), 0,
508 Context->getSourceManager(),
509 Context->getLangOpts());
510 // If something complicated is happening (i.e. the next token isn't an
511 // arrow), give up on making this work.
512 if (!ArrowLoc.isInvalid()) {
513 Usages.push_back(Usage(ResultExpr, /*IsArrow=*/true,
514 SourceRange(Base->getExprLoc(), ArrowLoc)));
518 return TraverseStmt(Member->getBase());
521 /// \brief If a member function call is the at() accessor on the container with
522 /// IndexVar as the single argument, include it as a valid usage and prune
525 /// Member calls on other objects will not be permitted.
526 /// Calls on the iterator object are not permitted, unless done through
527 /// operator->(). The one exception is allowing vector::at() for pseudoarrays.
528 bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
529 CXXMemberCallExpr *MemberCall) {
530 MemberExpr *Member = cast<MemberExpr>(MemberCall->getCallee());
531 // We specifically allow an accessor named "at" to let STL in, though
532 // this is restricted to pseudo-arrays by requiring a single, integer
534 const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
535 if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) {
536 if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar,
537 Member->getBase(), ContainerExpr,
538 ContainerNeedsDereference)) {
539 Usages.push_back(Usage(MemberCall));
544 if (containsExpr(Context, &DependentExprs, Member->getBase()))
545 ConfidenceLevel.lowerTo(TCK_Risky);
547 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
550 /// \brief If an overloaded operator call is a dereference of IndexVar or
551 /// a subscript of a the container with IndexVar as the single argument,
552 /// include it as a valid usage and prune the traversal.
554 /// For example, given
555 /// struct Foo { int bar(); int x; };
558 /// the following uses will be considered convertible:
559 /// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
562 /// for (int i = 0; i < v.size(); ++i) {
563 /// int i = v[i] + 1;
565 bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
566 CXXOperatorCallExpr *OpCall) {
567 switch (OpCall->getOperator()) {
569 if (isDereferenceOfOpCall(OpCall, IndexVar)) {
570 Usages.push_back(Usage(OpCall));
576 if (OpCall->getNumArgs() != 2)
578 if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,
579 OpCall->getArg(0), ContainerExpr,
580 ContainerNeedsDereference)) {
581 Usages.push_back(Usage(OpCall));
589 return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
592 /// \brief If we encounter an array with IndexVar as the index of an
593 /// ArraySubsriptExpression, note it as a consistent usage and prune the
596 /// For example, given
599 /// This is intended to permit
600 /// for (int i = 0; i < N; ++i) { /* use arr[i] */ }
602 /// for (int i = 0; i < N; ++i) { /* use notArr[i] */ }
603 /// and further checking needs to be done later to ensure that exactly one array
605 bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(
606 ArraySubscriptExpr *ASE) {
607 Expr *Arr = ASE->getBase();
608 if (!isIndexInSubscriptExpr(ASE->getIdx(), IndexVar))
609 return VisitorBase::TraverseArraySubscriptExpr(ASE);
611 if ((ContainerExpr && !areSameExpr(Context, Arr->IgnoreParenImpCasts(),
612 ContainerExpr->IgnoreParenImpCasts()))
613 || !arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(),
615 // If we have already discovered the array being indexed and this isn't it
616 // or this array doesn't match, mark this loop as unconvertible.
617 OnlyUsedAsIndex = false;
618 return VisitorBase::TraverseArraySubscriptExpr(ASE);
624 Usages.push_back(Usage(ASE));
628 /// \brief If we encounter a reference to IndexVar in an unpruned branch of the
629 /// traversal, mark this loop as unconvertible.
631 /// This implements the whitelist for convertible loops: any usages of IndexVar
632 /// not explicitly considered convertible by this traversal will be caught by
635 /// Additionally, if the container expression is more complex than just a
636 /// DeclRefExpr, and some part of it is appears elsewhere in the loop, lower
637 /// our confidence in the transformation.
639 /// For example, these are not permitted:
640 /// for (int i = 0; i < N; ++i) { printf("arr[%d] = %d", i, arr[i]); }
641 /// for (vector<int>::iterator i = container.begin(), e = container.end();
644 /// for (vector<int>::iterator i = container.begin(), e = container.end();
647 /// for (vector<int>::iterator i = container.begin(), e = container.end();
650 /// printf("%d", *i);
652 /// And these will raise the risk level:
655 /// for (int j = 0; j < 20; ++j)
656 /// int k = arr[l][j] + l; // using l outside arr[l] is considered risky
657 /// for (int i = 0; i < obj.getVector().size(); ++i)
658 /// obj.foo(10); // using `obj` is considered risky
659 bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *DRE) {
660 const ValueDecl *TheDecl = DRE->getDecl();
661 if (areSameVariable(IndexVar, TheDecl) || areSameVariable(EndVar, TheDecl))
662 OnlyUsedAsIndex = false;
663 if (containsExpr(Context, &DependentExprs, DRE))
664 ConfidenceLevel.lowerTo(TCK_Risky);
668 /// \brief If we find that another variable is created just to refer to the loop
669 /// element, note it for reuse as the loop variable.
671 /// See the comments for isAliasDecl.
672 bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *DS) {
673 if (!AliasDecl && DS->isSingleDecl() &&
674 isAliasDecl(DS->getSingleDecl(), IndexVar))
679 //// \brief Apply the source transformations necessary to migrate the loop!
680 void LoopFixer::doConversion(ASTContext *Context,
681 const VarDecl *IndexVar,
682 const Expr *ContainerExpr,
683 const UsageResult &Usages,
684 const DeclStmt *AliasDecl,
685 const ForStmt *TheLoop,
686 bool ContainerNeedsDereference) {
687 const VarDecl *MaybeContainer = getReferencedVariable(ContainerExpr);
690 if (Usages.size() == 1 && AliasDecl) {
691 const VarDecl *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());
692 VarName = AliasVar->getName().str();
693 // We keep along the entire DeclStmt to keep the correct range here.
694 const SourceRange &ReplaceRange = AliasDecl->getSourceRange();
697 Replacement(Context->getSourceManager(),
698 CharSourceRange::getTokenRange(ReplaceRange), ""));
699 // No further replacements are made to the loop, since the iterator or index
700 // was used exactly once - in the initialization of AliasVar.
702 VariableNamer Namer(GeneratedDecls, &ParentFinder->getStmtToParentStmtMap(),
703 TheLoop, IndexVar, MaybeContainer);
704 VarName = Namer.createIndexName();
705 // First, replace all usages of the array subscript expression with our new
707 for (UsageResult::const_iterator I = Usages.begin(), E = Usages.end();
709 std::string ReplaceText = I->IsArrow ? VarName + "." : VarName;
710 ReplacedVarRanges->insert(std::make_pair(TheLoop, IndexVar));
713 Replacement(Context->getSourceManager(),
714 CharSourceRange::getTokenRange(I->Range),
719 // Now, we need to construct the new range expresion.
720 SourceRange ParenRange(TheLoop->getLParenLoc(), TheLoop->getRParenLoc());
721 StringRef ContainerString =
722 getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),
723 ContainerExpr->getSourceRange());
725 QualType AutoRefType =
726 Context->getLValueReferenceType(Context->getAutoDeductType());
728 std::string MaybeDereference = ContainerNeedsDereference ? "*" : "";
729 std::string TypeString = AutoRefType.getAsString();
730 std::string Range = ("(" + TypeString + " " + VarName + " : "
731 + MaybeDereference + ContainerString + ")").str();
733 Replace->insert(Replacement(Context->getSourceManager(),
734 CharSourceRange::getTokenRange(ParenRange),
736 GeneratedDecls->insert(make_pair(TheLoop, VarName));
739 /// \brief Determine whether Init appears to be an initializing an iterator.
741 /// If it is, returns the object whose begin() or end() method is called, and
742 /// the output parameter isArrow is set to indicate whether the initialization
743 /// is called via . or ->.
744 static const Expr *getContainerFromBeginEndCall(const Expr* Init, bool IsBegin,
746 // FIXME: Maybe allow declaration/initialization outside of the for loop?
747 const CXXMemberCallExpr *TheCall =
748 dyn_cast_or_null<CXXMemberCallExpr>(digThroughConstructors(Init));
749 if (!TheCall || TheCall->getNumArgs() != 0)
752 const MemberExpr *Member = cast<MemberExpr>(TheCall->getCallee());
753 const std::string Name = Member->getMemberDecl()->getName();
754 const std::string TargetName = IsBegin ? "begin" : "end";
755 if (Name != TargetName)
758 const Expr *SourceExpr = Member->getBase();
762 *IsArrow = Member->isArrow();
766 /// \brief Determines the container whose begin() and end() functions are called
767 /// for an iterator-based loop.
769 /// BeginExpr must be a member call to a function named "begin()", and EndExpr
770 /// must be a member .
771 static const Expr *findContainer(ASTContext *Context, const Expr *BeginExpr,
773 bool *ContainerNeedsDereference) {
774 // Now that we know the loop variable and test expression, make sure they are
776 bool BeginIsArrow = false;
777 bool EndIsArrow = false;
778 const Expr *BeginContainerExpr =
779 getContainerFromBeginEndCall(BeginExpr, /*IsBegin=*/true, &BeginIsArrow);
780 if (!BeginContainerExpr)
783 const Expr *EndContainerExpr =
784 getContainerFromBeginEndCall(EndExpr, /*IsBegin=*/false, &EndIsArrow);
785 // Disallow loops that try evil things like this (note the dot and arrow):
786 // for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }
787 if (!EndContainerExpr || BeginIsArrow != EndIsArrow ||
788 !areSameExpr(Context, EndContainerExpr, BeginContainerExpr))
791 *ContainerNeedsDereference = BeginIsArrow;
792 return BeginContainerExpr;
795 /// \brief Given that we have verified that the loop's header appears to be
796 /// convertible, run the complete analysis on the loop to determine if the
797 /// loop's body is convertible.
798 void LoopFixer::FindAndVerifyUsages(ASTContext *Context,
799 const VarDecl *LoopVar,
800 const VarDecl *EndVar,
801 const Expr *ContainerExpr,
802 const Expr *BoundExpr,
803 bool ContainerNeedsDereference,
804 const ForStmt *TheLoop,
805 Confidence ConfidenceLevel) {
806 ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
807 BoundExpr, ContainerNeedsDereference);
809 ComponentFinderASTVisitor ComponentFinder;
810 ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
811 Finder.addComponents(ComponentFinder.getComponents());
814 if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
817 ConfidenceLevel.lowerTo(Finder.getConfidenceLevel());
818 if (FixerKind == LFK_Array) {
819 // The array being indexed by IndexVar was discovered during traversal.
820 ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();
821 // Very few loops are over expressions that generate arrays rather than
822 // array variables. Consider loops over arrays that aren't just represented
823 // by a variable to be risky conversions.
824 if (!getReferencedVariable(ContainerExpr) &&
825 !isDirectMemberExpr(ContainerExpr))
826 ConfidenceLevel.lowerTo(TCK_Risky);
829 // If we already modified the range of this for loop, don't do any further
830 // updates on this iteration.
831 // FIXME: Once Replacements can detect conflicting edits, replace this
832 // implementation and rely on conflicting edit detection instead.
833 if (ReplacedVarRanges->count(TheLoop)) {
838 ParentFinder->gatherAncestors(Context->getTranslationUnitDecl());
839 // Ensure that we do not try to move an expression dependent on a local
840 // variable declared inside the loop outside of it!
841 DependencyFinderASTVisitor
842 DependencyFinder(&ParentFinder->getStmtToParentStmtMap(),
843 &ParentFinder->getDeclToParentStmtMap(),
844 ReplacedVarRanges, TheLoop);
846 // Not all of these are actually deferred changes.
847 // FIXME: Determine when the external dependency isn't an expression converted
849 if (DependencyFinder.dependsOnOutsideVariable(ContainerExpr)) {
853 if (ConfidenceLevel.get() < RequiredConfidenceLevel) {
858 doConversion(Context, LoopVar, ContainerExpr, Finder.getUsages(),
859 Finder.getAliasDecl(), TheLoop, ContainerNeedsDereference);
863 /// \brief The LoopFixer callback, which determines if loops discovered by the
864 /// matchers are convertible, printing information about the loops if so.
865 void LoopFixer::run(const MatchFinder::MatchResult &Result) {
866 const BoundNodes &Nodes = Result.Nodes;
867 Confidence ConfidenceLevel(TCK_Safe);
868 ASTContext *Context = Result.Context;
869 const ForStmt *TheLoop = Nodes.getStmtAs<ForStmt>(LoopName);
871 if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc()))
874 // Check that we have exactly one index variable and at most one end variable.
875 const VarDecl *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
876 const VarDecl *CondVar = Nodes.getDeclAs<VarDecl>(ConditionVarName);
877 const VarDecl *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
878 if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
880 const VarDecl *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
881 const VarDecl *ConditionEndVar =
882 Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
883 if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
886 // If the end comparison isn't a variable, we can try to work with the
887 // expression the loop variable is being tested against instead.
888 const CXXMemberCallExpr *EndCall =
889 Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
890 const Expr *BoundExpr = Nodes.getStmtAs<Expr>(ConditionBoundName);
891 // If the loop calls end()/size() after each iteration, lower our confidence
893 if (FixerKind == LFK_Array && !BoundExpr)
895 if (FixerKind != LFK_Array && !EndVar) {
898 ConfidenceLevel.lowerTo(TCK_Reasonable);
901 const Expr *ContainerExpr = NULL;
902 bool ContainerNeedsDereference = false;
903 // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
904 // don't allow the right-recursive checks in digThroughConstructors.
905 if (FixerKind == LFK_Iterator)
906 ContainerExpr = findContainer(Context, LoopVar->getInit(),
907 EndVar ? EndVar->getInit() : EndCall,
908 &ContainerNeedsDereference);
909 else if (FixerKind == LFK_PseudoArray) {
910 ContainerExpr = EndCall->getImplicitObjectArgument();
911 ContainerNeedsDereference =
912 cast<MemberExpr>(EndCall->getCallee())->isArrow();
914 // We must know the container being iterated over by now for non-array loops.
915 if (!ContainerExpr && FixerKind != LFK_Array)
918 FindAndVerifyUsages(Context, LoopVar, EndVar, ContainerExpr, BoundExpr,
919 ContainerNeedsDereference, TheLoop, ConfidenceLevel);
922 } // namespace loop_migrate