Fixes according to code review comments
[lldb.git] / clang-tools-extra / loop-convert / LoopActions.cpp
1 #include "LoopActions.h"
2 #include "LoopMatchers.h"
3 #include "VariableNaming.h"
4
5 #include "clang/Lex/Lexer.h"
6
7 namespace clang {
8 namespace loop_migrate {
9
10 using namespace clang::ast_matchers;
11 using namespace clang::tooling;
12
13 /// \brief The information needed to describe a valid convertible usage
14 /// of an array index or iterator.
15 struct Usage {
16   const Expr *E;
17   bool IsArrow;
18   SourceRange Range;
19
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) { }
24 };
25
26 /// \brief A class to encapsulate lowering of the tool's confidence level.
27 class Confidence {
28   public:
29    /// \brief Initialize the default confidence level to the maximum value
30    /// (TCK_Safe).
31    explicit Confidence(TranslationConfidenceKind Level) :
32      CurrentLevel(Level) {}
33
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);
37    }
38
39    /// \brief Return the internal confidence level.
40    TranslationConfidenceKind get() const { return CurrentLevel; }
41
42    /// \brief Set the confidence level unconditionally.
43    void resetTo(TranslationConfidenceKind Level) { CurrentLevel = Level; }
44
45   private:
46    TranslationConfidenceKind CurrentLevel;
47 };
48
49 /// \brief Discover usages of expressions consisting of index or iterator
50 /// access.
51 ///
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> {
56  public:
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) {
65      if (ContainerExpr) {
66        addComponent(ContainerExpr);
67        llvm::FoldingSetNodeID ID;
68        const Expr *E = ContainerExpr->IgnoreParenImpCasts();
69        E->Profile(ID, *Context, true);
70      }
71   }
72
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.
76   ///
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;
87   }
88
89   /// \brief Add a set of components that we should consider relevant to the
90   /// container.
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)
95       addComponent(*I);
96   }
97
98   /// \brief Accessor for Usages.
99   const UsageResult &getUsages() const { return Usages; }
100
101   /// \brief Get the container indexed by IndexVar, if any.
102   const Expr *getContainerIndexed() const {
103     return ContainerExpr;
104   }
105
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; }
109
110   /// \brief Accessor for ConfidenceLevel.
111   TranslationConfidenceKind getConfidenceLevel() const {
112     return ConfidenceLevel.get();
113   }
114
115  private:
116   /// Typedef used in CRTP functions.
117   typedef RecursiveASTVisitor<ForLoopIndexUseVisitor> VisitorBase;
118   friend class RecursiveASTVisitor<ForLoopIndexUseVisitor>;
119
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);
128
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));
136   }
137
138   // Input member variables:
139   ASTContext *Context;
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;
149
150   // Output member variables:
151   /// A container which holds all usages of IndexVar as the index of
152   /// ArraySubscriptExpressions.
153   UsageResult Usages;
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.
159   ///
160   /// If any of these expressions are encountered outside of an acceptable usage
161   /// of the loop element, lower our confidence level.
162   llvm::SmallVector<
163       std::pair<const Expr *, llvm::FoldingSetNodeID>, 16> DependentExprs;
164 };
165
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,
170                                     SourceRange Range) {
171   if (SourceMgr.getFileID(Range.getBegin()) !=
172       SourceMgr.getFileID(Range.getEnd()))
173     return NULL;
174
175   CharSourceRange SourceChars(Range, true);
176   return Lexer::getSourceText(SourceChars, SourceMgr, LangOpts);
177 }
178
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());
182 }
183
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());
189   return NULL;
190 }
191
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());
197   return false;
198 }
199
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();
204 }
205
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) {
209   if (!Target || !E)
210     return false;
211   const DeclRefExpr *DRE = getDeclRef(E);
212   return DRE && areSameVariable(Target, DRE->getDecl());
213 }
214
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)
219     return false;
220
221   llvm::FoldingSetNodeID FirstID, SecondID;
222   First->Profile(FirstID, *Context, true);
223   Second->Profile(SecondID, *Context, true);
224   return FirstID == SecondID;
225 }
226
227 /// \brief Look through conversion/copy constructors to find the explicit
228 /// initialization expression, returning it is found.
229 ///
230 /// The main idea is that given
231 ///   vector<int> v;
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
236 /// not include
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) {
241   if (!E)
242     return NULL;
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)
249       return NULL;
250     E = ConstructExpr->getArg(0);
251     if (const MaterializeTemporaryExpr *MTE =
252         dyn_cast<MaterializeTemporaryExpr>(E))
253       E = MTE->GetTemporaryExpr();
254     return digThroughConstructors(E);
255   }
256   return E;
257 }
258
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;
264
265   if (const CXXOperatorCallExpr *OpCall = dyn_cast<CXXOperatorCallExpr>(E))
266     return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 ?
267         OpCall->getArg(0) : NULL;
268
269   return NULL;
270 }
271
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,
275                          const Expr *E) {
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)
280     if (ID == I->second)
281       return true;
282   return false;
283 }
284
285 /// \brief Returns true when the index expression is a declaration reference to
286 /// IndexVar.
287 ///
288 /// If the index variable is `index`, this function returns true on
289 ///    arrayExpression[index];
290 ///    containerExpression[index];
291 /// but not
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());
298 }
299
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.
303 ///
304 /// If PermitDeref is true, IndexExpression may
305 /// be a dereference (overloaded or builtin operator*).
306 ///
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
311 ///   container[index]
312 ///   container.at(index)
313 ///   container->at(index)
314 /// but not for
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))
325     return false;
326
327   if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
328                   Obj->IgnoreParenImpCasts()))
329     return true;
330
331   if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))
332     if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
333                                    InnerObj->IgnoreParenImpCasts()))
334       return true;
335
336   return false;
337 }
338
339 /// \brief Returns true when Opcall is a call a one-parameter dereference of
340 /// IndexVar.
341 ///
342 /// For example, if the index variable is `index`, returns true for
343 ///   *index
344 /// but not
345 ///   index
346 ///   *notIndex
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));
351 }
352
353 /// \brief Returns true when Uop is a dereference of IndexVar.
354 ///
355 /// For example, if the index variable is `index`, returns true for
356 ///   *index
357 /// but not
358 ///   index
359 ///   *notIndex
360 static bool isDereferenceOfUop(const UnaryOperator *Uop,
361                                const VarDecl *IndexVar) {
362   return Uop->getOpcode() == UO_Deref &&
363       exprReferencesVariable(IndexVar, Uop->getSubExpr());
364 }
365
366 /// \brief Determines whether the given Decl defines a variable initialized to
367 /// the loop object.
368 ///
369 /// This is intended to find cases such as
370 ///   for (int i = 0; i < arraySize(arr); ++i) {
371 ///     T t = arr[i];
372 ///     // use t, do not use i
373 ///   }
374 /// and
375 ///   for (iterator i = container.begin(), e = container.end(); i != e; ++i) {
376 ///     T t = *i;
377 ///     // use t, do not use i
378 ///   }
379 static bool isAliasDecl(const Decl *TheDecl, const VarDecl *IndexVar) {
380   const VarDecl *VDecl = dyn_cast<VarDecl>(TheDecl);
381   if (!VDecl)
382     return false;
383   if (!VDecl->hasInit())
384     return false;
385   const Expr *Init =
386       digThroughConstructors(VDecl->getInit()->IgnoreParenImpCasts());
387   if (!Init)
388     return false;
389
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);
396   }
397
398   case Stmt::UnaryOperatorClass:
399     return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar);
400
401   case Stmt::CXXOperatorCallExprClass: {
402       const CXXOperatorCallExpr *OpCall = cast<CXXOperatorCallExpr>(Init);
403       if (OpCall->getOperator() == OO_Star)
404         return isDereferenceOfOpCall(OpCall, IndexVar);
405       break;
406   }
407
408   default:
409     break;
410   }
411   return false;
412 }
413
414 /// \brief Determines whether the bound of a for loop condition expression is
415 /// the same as the statically computable size of ArrayType.
416 ///
417 /// Given
418 ///   const int N = 5;
419 ///   int arr[N];
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))
430       return false;
431     llvm::APSInt ArraySize(CAT->getSize());
432     return llvm::APSInt::isSameValue(ConditionSize, ArraySize);
433   }
434   return false;
435 }
436
437 /// \brief If the unary operator is a dereference of IndexVar, include it
438 /// as a valid usage and prune the traversal.
439 ///
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) {
444 ///     int k = *i + 2;
445 ///   }
446 bool ForLoopIndexUseVisitor::TraverseUnaryDeref(UnaryOperator *Uop) {
447   // If we dereference an iterator that's actually a pointer, count the
448   // occurrence.
449   if (isDereferenceOfUop(Uop, IndexVar)) {
450     Usages.push_back(Usage(Uop));
451     return true;
452   }
453
454   return VisitorBase::TraverseUnaryOperator(Uop);
455 }
456
457 /// \brief If the member expression is operator-> (overloaded or not) on
458 /// IndexVar, include it as a valid usage and prune the traversal.
459 ///
460 /// For example, given
461 ///   struct Foo { int bar(); int x; };
462 ///   vector<Foo> v;
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;
467 ///   }
468 /// though
469 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
470 ///     int k = i.insert(1);
471 ///   }
472 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
473 ///     int b = e->bar();
474 ///   }
475 /// will not.
476 bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
477   const Expr *Base = Member->getBase();
478   const DeclRefExpr *Obj = getDeclRef(Base);
479   const Expr *ResultExpr = Member;
480   QualType ExprType;
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));
494       ResultExpr = Obj;
495       ExprType = Call->getCallReturnType();
496     }
497   }
498
499   if (Member->isArrow() && Obj && exprReferencesVariable(IndexVar, Obj)) {
500     if (ExprType.isNull())
501       ExprType = Obj->getType();
502
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)));
515       return true;
516     }
517   }
518   return TraverseStmt(Member->getBase());
519 }
520
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
523 /// the traversal.
524 ///
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
533   // argument.
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));
540       return true;
541     }
542   }
543
544   if (containsExpr(Context, &DependentExprs, Member->getBase()))
545     ConfidenceLevel.lowerTo(TCK_Risky);
546
547   return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
548 }
549
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.
553 ///
554 /// For example, given
555 ///   struct Foo { int bar(); int x; };
556 ///   vector<Foo> v;
557 ///   void f(Foo);
558 /// the following uses will be considered convertible:
559 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
560 ///     f(*i);
561 ///   }
562 ///   for (int i = 0; i < v.size(); ++i) {
563 ///      int i = v[i] + 1;
564 ///   }
565 bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
566     CXXOperatorCallExpr *OpCall) {
567   switch (OpCall->getOperator()) {
568   case OO_Star:
569     if (isDereferenceOfOpCall(OpCall, IndexVar)) {
570       Usages.push_back(Usage(OpCall));
571       return true;
572     }
573     break;
574
575   case OO_Subscript:
576     if (OpCall->getNumArgs() != 2)
577       break;
578     if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,
579                                OpCall->getArg(0), ContainerExpr,
580                                ContainerNeedsDereference)) {
581       Usages.push_back(Usage(OpCall));
582       return true;
583     }
584     break;
585
586   default:
587     break;
588   }
589   return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
590 }
591
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
594 /// AST traversal.
595 ///
596 /// For example, given
597 ///   const int N = 5;
598 ///   int arr[N];
599 /// This is intended to permit
600 ///   for (int i = 0; i < N; ++i) {  /* use arr[i] */ }
601 /// but not
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
604 /// is referenced.
605 bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(
606     ArraySubscriptExpr *ASE) {
607   Expr *Arr = ASE->getBase();
608   if (!isIndexInSubscriptExpr(ASE->getIdx(), IndexVar))
609     return VisitorBase::TraverseArraySubscriptExpr(ASE);
610
611   if ((ContainerExpr && !areSameExpr(Context, Arr->IgnoreParenImpCasts(),
612                                      ContainerExpr->IgnoreParenImpCasts()))
613       || !arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(),
614                                 ArrayBoundExpr)) {
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);
619   }
620
621   if (!ContainerExpr)
622     ContainerExpr = Arr;
623
624   Usages.push_back(Usage(ASE));
625   return true;
626 }
627
628 /// \brief If we encounter a reference to IndexVar in an unpruned branch of the
629 /// traversal, mark this loop as unconvertible.
630 ///
631 /// This implements the whitelist for convertible loops: any usages of IndexVar
632 /// not explicitly considered convertible by this traversal will be caught by
633 /// this function.
634 ///
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.
638 ///
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();
642 ///        i != e; ++i)
643 ///     i.insert(0);
644 ///   for (vector<int>::iterator i = container.begin(), e = container.end();
645 ///        i != e; ++i)
646 ///     i.insert(0);
647 ///   for (vector<int>::iterator i = container.begin(), e = container.end();
648 ///        i != e; ++i)
649 ///     if (i + 1 != e)
650 ///       printf("%d", *i);
651 ///
652 ///  And these will raise the risk level:
653 ///    int arr[10][20];
654 ///    int l = 5;
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);
665   return true;
666 }
667
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.
670 ///
671 /// See the comments for isAliasDecl.
672 bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *DS) {
673   if (!AliasDecl && DS->isSingleDecl() &&
674       isAliasDecl(DS->getSingleDecl(), IndexVar))
675       AliasDecl = DS;
676   return true;
677 }
678
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);
688   std::string VarName;
689
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();
695     if (!CountOnly)
696       Replace->insert(
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.
701   } else {
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
706     // variable.
707     for (UsageResult::const_iterator I = Usages.begin(), E = Usages.end();
708          I != E; ++I) {
709       std::string ReplaceText = I->IsArrow ? VarName + "." : VarName;
710       ReplacedVarRanges->insert(std::make_pair(TheLoop, IndexVar));
711       if (!CountOnly)
712         Replace->insert(
713             Replacement(Context->getSourceManager(),
714                         CharSourceRange::getTokenRange(I->Range),
715                         ReplaceText));
716     }
717   }
718
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());
724
725   QualType AutoRefType =
726       Context->getLValueReferenceType(Context->getAutoDeductType());
727
728   std::string MaybeDereference = ContainerNeedsDereference ? "*" : "";
729   std::string TypeString = AutoRefType.getAsString();
730   std::string Range = ("(" + TypeString + " " + VarName + " : "
731                            + MaybeDereference + ContainerString + ")").str();
732   if (!CountOnly)
733     Replace->insert(Replacement(Context->getSourceManager(),
734                                 CharSourceRange::getTokenRange(ParenRange),
735                                 Range));
736   GeneratedDecls->insert(make_pair(TheLoop, VarName));
737 }
738
739 /// \brief Determine whether Init appears to be an initializing an iterator.
740 ///
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,
745                                                 bool *IsArrow) {
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)
750       return NULL;
751
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)
756     return NULL;
757
758   const Expr *SourceExpr = Member->getBase();
759   if (!SourceExpr)
760     return NULL;
761
762   *IsArrow = Member->isArrow();
763   return SourceExpr;
764 }
765
766 /// \brief Determines the container whose begin() and end() functions are called
767 /// for an iterator-based loop.
768 ///
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,
772                                  const Expr *EndExpr,
773                                  bool *ContainerNeedsDereference) {
774   // Now that we know the loop variable and test expression, make sure they are
775   // valid.
776   bool BeginIsArrow = false;
777   bool EndIsArrow = false;
778   const Expr *BeginContainerExpr =
779       getContainerFromBeginEndCall(BeginExpr, /*IsBegin=*/true, &BeginIsArrow);
780   if (!BeginContainerExpr)
781       return NULL;
782
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))
789     return NULL;
790
791   *ContainerNeedsDereference = BeginIsArrow;
792   return BeginContainerExpr;
793 }
794
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);
808   if (ContainerExpr) {
809     ComponentFinderASTVisitor ComponentFinder;
810     ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
811     Finder.addComponents(ComponentFinder.getComponents());
812   }
813
814   if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
815     return;
816
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);
827   }
828
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)) {
834     ++*DeferredChanges;
835     return;
836   }
837
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);
845
846   // Not all of these are actually deferred changes.
847   // FIXME: Determine when the external dependency isn't an expression converted
848   // by another loop.
849   if (DependencyFinder.dependsOnOutsideVariable(ContainerExpr)) {
850     ++*DeferredChanges;
851     return;
852   }
853   if (ConfidenceLevel.get() < RequiredConfidenceLevel) {
854     ++*RejectedChanges;
855     return;
856   }
857
858   doConversion(Context, LoopVar, ContainerExpr, Finder.getUsages(),
859                Finder.getAliasDecl(), TheLoop, ContainerNeedsDereference);
860   ++*AcceptedChanges;
861 }
862
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);
870
871   if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc()))
872     return;
873
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))
879     return;
880   const VarDecl *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
881   const VarDecl *ConditionEndVar =
882       Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
883   if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
884     return;
885
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
892   // level.
893   if (FixerKind == LFK_Array && !BoundExpr)
894       return;
895   if (FixerKind != LFK_Array && !EndVar) {
896     if (!EndCall)
897       return;
898     ConfidenceLevel.lowerTo(TCK_Reasonable);
899   }
900
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();
913   }
914   // We must know the container being iterated over by now for non-array loops.
915   if (!ContainerExpr && FixerKind != LFK_Array)
916     return;
917
918   FindAndVerifyUsages(Context, LoopVar, EndVar, ContainerExpr, BoundExpr,
919                       ContainerNeedsDereference, TheLoop, ConfidenceLevel);
920 }
921
922 } // namespace loop_migrate
923 } // namespace clang