9a2e1cc6355ba77ce300da45a87b7649201b99ee
[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 A type for holding the list of containers indexed.
14 typedef llvm::SmallVector<
15   std::pair<const Expr *, llvm::FoldingSetNodeID>, 1> ContainerResult;
16
17 /// \brief The information needed to describe a valid convertible usage
18 /// of an array index or iterator.
19 struct Usage {
20   const Expr *E;
21   bool IsArrow;
22   SourceRange Range;
23
24   explicit Usage(const Expr *E)
25       : E(E), IsArrow(false), Range(E->getSourceRange()) { }
26   Usage(const Expr *E, bool IsArrow, SourceRange Range)
27       : E(E), IsArrow(IsArrow), Range(Range) { }
28 };
29
30 /// \brief A class to encapsulate lowering of the tool's confidence level.
31 class Confidence {
32   public:
33    /// \brief Initialize the default confidence level to the maximum value
34    /// (TCK_Safe).
35    explicit Confidence(TranslationConfidenceKind Level) :
36      CurrentLevel(Level) {}
37
38    /// \brief Lower the internal confidence level to Level, but do not raise it.
39    void lowerTo(TranslationConfidenceKind Level) {
40      CurrentLevel = std::min(Level, CurrentLevel);
41    }
42
43    /// \brief Return the internal confidence level.
44    TranslationConfidenceKind get() const { return CurrentLevel; }
45
46    /// \brief Set the confidence level unconditionally.
47    void resetTo(TranslationConfidenceKind Level) { CurrentLevel = Level; }
48
49   private:
50    TranslationConfidenceKind CurrentLevel;
51 };
52
53 /// \brief Discover usages of expressions consisting of index or iterator
54 /// access.
55 ///
56 /// Given an index variable, recursively crawls a for loop to discover if the
57 /// index variable is used in a way consistent with range-based for loop access.
58 class ForLoopIndexUseVisitor
59     : public RecursiveASTVisitor<ForLoopIndexUseVisitor> {
60  public:
61   ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar,
62                          const VarDecl *EndVar, const Expr *ContainerExpr,
63                          bool ContainerNeedsDereference) :
64     Context(Context), IndexVar(IndexVar), EndVar(EndVar),
65     ContainerExpr(ContainerExpr),
66     ContainerNeedsDereference(ContainerNeedsDereference),
67     OnlyUsedAsIndex(true),  AliasDecl(NULL), ConfidenceLevel(TCK_Safe) {
68      if (ContainerExpr) {
69        addComponent(ContainerExpr);
70        llvm::FoldingSetNodeID ID;
71        const Expr *E = ContainerExpr->IgnoreParenImpCasts();
72        E->Profile(ID, *Context, true);
73        ContainersIndexed.push_back(std::make_pair(E, ID));
74      }
75   }
76
77   /// \brief Finds all uses of IndexVar in Body, placing all usages in Usages,
78   /// all referenced arrays in ContainersIndexed, and returns true if IndexVar
79   /// was only used in a way consistent with a range-based for loop.
80   ///
81   /// The general strategy is to reject any DeclRefExprs referencing IndexVar,
82   /// with the exception of certain acceptable patterns.
83   /// For arrays, the DeclRefExpr for IndexVar must appear as the index of an
84   /// ArraySubscriptExpression. Iterator-based loops may dereference
85   /// IndexVar or call methods through operator-> (builtin or overloaded).
86   /// Array-like containers may use IndexVar as a parameter to the at() member
87   /// function and in overloaded operator[].
88   bool findAndVerifyUsages(const Stmt *Body) {
89     TraverseStmt(const_cast<Stmt *>(Body));
90     return OnlyUsedAsIndex;
91   }
92
93   /// \brief Add a set of components that we should consider relevant to the
94   /// container.
95   void addComponents(const ComponentVector &Components) {
96     // FIXME: add sort(on ID)+unique to avoid extra work.
97     for (ComponentVector::const_iterator I = Components.begin(),
98                                          E = Components.end(); I != E; ++I)
99       addComponent(*I);
100   }
101
102   /// \brief Accessor for Usages.
103   const UsageResult &getUsages() const { return Usages; }
104
105   /// \brief Determines whether or not exactly one container was indexed by
106   /// IndexVar.
107   bool indexesSingleContainer() const {
108     return ContainersIndexed.size() == 1;
109   }
110
111   /// \brief Get the container indexed by IndexVar.
112   ///
113   /// This method asserts that there is only one container indexed; check that
114   /// indexesSingleContainer() returns true first.
115   const Expr *getSingleContainerIndexed() const {
116     assert(indexesSingleContainer() && "Index used for multiple containers");
117     return ContainersIndexed.begin()->first;
118   }
119
120   /// \brief Returns the statement declaring the variable created as an alias
121   /// for the loop element, if any.
122   const DeclStmt *getAliasDecl() const { return AliasDecl; }
123
124   /// \brief Accessor for ConfidenceLevel.
125   TranslationConfidenceKind getConfidenceLevel() const {
126     return ConfidenceLevel.get();
127   }
128
129  private:
130   /// Typedef used in CRTP functions.
131   typedef RecursiveASTVisitor<ForLoopIndexUseVisitor> VisitorBase;
132   friend class RecursiveASTVisitor<ForLoopIndexUseVisitor>;
133
134   /// Overriden methods for RecursiveASTVisitor's traversal.
135   bool TraverseArraySubscriptExpr(ArraySubscriptExpr *ASE);
136   bool TraverseCXXMemberCallExpr(CXXMemberCallExpr *MemberCall);
137   bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *OpCall);
138   bool TraverseMemberExpr(MemberExpr *Member);
139   bool TraverseUnaryDeref(UnaryOperator *Uop);
140   bool VisitDeclRefExpr(DeclRefExpr *DRE);
141   bool VisitDeclStmt(DeclStmt *DS);
142
143   /// \brief Add an expression to the list of expressions on which the container
144   /// expression depends.
145   void addComponent(const Expr *E) {
146     llvm::FoldingSetNodeID ID;
147     const Expr *Node = E->IgnoreParenImpCasts();
148     Node->Profile(ID, *Context, true);
149     DependentExprs.push_back(std::make_pair(Node, ID));
150   }
151
152   // Input member variables:
153   ASTContext *Context;
154   /// The index variable's VarDecl.
155   const VarDecl *IndexVar;
156   /// The loop's 'end' variable, which cannot be mentioned at all.
157   const VarDecl *EndVar;
158   /// The Expr which refers to the container.
159   const Expr *ContainerExpr;
160   bool ContainerNeedsDereference;
161
162   // Output member variables:
163   /// A container which holds all usages of IndexVar as the index of
164   /// ArraySubscriptExpressions.
165   UsageResult Usages;
166   bool OnlyUsedAsIndex;
167   /// A set which holds expressions containing the referenced arrays.
168   ContainerResult ContainersIndexed;
169   /// The DeclStmt for an alias to the container element.
170   const DeclStmt *AliasDecl;
171   Confidence ConfidenceLevel;
172   /// \brief A list of expressions on which ContainerExpr depends.
173   ///
174   /// If any of these expressions are encountered outside of an acceptable usage
175   /// of the loop element, lower our confidence level.
176   llvm::SmallVector<
177       std::pair<const Expr *, llvm::FoldingSetNodeID>, 16> DependentExprs;
178 };
179
180 // FIXME: Determine how not to break in the presence of problematic macros.
181 /// \brief Obtain the original source code text from a SourceRange.
182 static StringRef getStringFromRange(SourceManager &SourceMgr,
183                                     const LangOptions &LangOpts,
184                                     SourceRange Range) {
185   if (SourceMgr.getFileID(Range.getBegin()) !=
186       SourceMgr.getFileID(Range.getEnd()))
187     return NULL;
188
189   CharSourceRange SourceChars(Range, true);
190   return Lexer::getSourceText(SourceChars, SourceMgr, LangOpts);
191 }
192
193 /// \brief Returns the DeclRefExpr represented by E, or NULL if there isn't one.
194 static const DeclRefExpr *getDeclRef(const Expr *E) {
195   return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());
196 }
197
198 /// \brief If the given expression is actually a DeclRefExpr, find and return
199 /// the underlying VarDecl; otherwise, return NULL.
200 static const VarDecl *getReferencedVariable(const Expr *E) {
201   if (const DeclRefExpr *DRE = getDeclRef(E))
202     return dyn_cast<VarDecl>(DRE->getDecl());
203   return NULL;
204 }
205
206 /// \brief Returns true when the given expression is a member expression
207 /// whose base is `this` (implicitly or not).
208 static bool isDirectMemberExpr(const Expr *E) {
209   if (const MemberExpr *Member = dyn_cast<MemberExpr>(E->IgnoreParenImpCasts()))
210     return isa<CXXThisExpr>(Member->getBase()->IgnoreParenImpCasts());
211   return false;
212 }
213
214 /// \brief Returns true when two ValueDecls are the same variable.
215 static bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) {
216   return First && Second &&
217          First->getCanonicalDecl() == Second->getCanonicalDecl();
218 }
219
220 /// \brief Determines if an expression is a declaration reference to a
221 /// particular variable.
222 static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) {
223   if (!Target || !E)
224     return false;
225   const DeclRefExpr *DRE = getDeclRef(E);
226   return DRE && areSameVariable(Target, DRE->getDecl());
227 }
228
229 /// \brief Returns true when two Exprs are equivalent.
230 static bool areSameExpr(ASTContext* Context, const Expr *First,
231                         const Expr *Second) {
232   if (!First || !Second)
233     return false;
234
235   llvm::FoldingSetNodeID FirstID, SecondID;
236   First->Profile(FirstID, *Context, true);
237   Second->Profile(SecondID, *Context, true);
238   return FirstID == SecondID;
239 }
240
241 /// \brief Look through conversion/copy constructors to find the explicit
242 /// initialization expression, returning it is found.
243 ///
244 /// The main idea is that given
245 ///   vector<int> v;
246 /// we consider either of these initializations
247 ///   vector<int>::iterator it = v.begin();
248 ///   vector<int>::iterator it(v.begin());
249 /// and retrieve `v.begin()` as the expression used to initialize `it` but do
250 /// not include
251 ///   vector<int>::iterator it;
252 ///   vector<int>::iterator it(v.begin(), 0); // if this constructor existed
253 /// as being initialized from `v.begin()`
254 static const Expr *digThroughConstructors(const Expr *E) {
255   if (!E)
256     return NULL;
257   E = E->IgnoreParenImpCasts();
258   if (const CXXConstructExpr *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {
259     // The initial constructor must take exactly one parameter, but base class
260     // and deferred constructors can take more.
261     if (ConstructExpr->getNumArgs() != 1 ||
262         ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_Complete)
263       return NULL;
264     E = ConstructExpr->getArg(0);
265     if (const MaterializeTemporaryExpr *MTE =
266         dyn_cast<MaterializeTemporaryExpr>(E))
267       E = MTE->GetTemporaryExpr();
268     return digThroughConstructors(E);
269   }
270   return E;
271 }
272
273 /// \brief If the expression is a dereference or call to operator*(), return the
274 /// operand. Otherwise, returns NULL.
275 static const Expr *getDereferenceOperand(const Expr *E) {
276   if (const UnaryOperator *Uop = dyn_cast<UnaryOperator>(E))
277     return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : NULL;
278
279   if (const CXXOperatorCallExpr *OpCall = dyn_cast<CXXOperatorCallExpr>(E))
280     return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 ?
281         OpCall->getArg(0) : NULL;
282
283   return NULL;
284 }
285
286 /// \brief Returns true when the Container contains an Expr equivalent to E.
287 template<typename ContainerT>
288 static bool containsExpr(ASTContext *Context, const ContainerT *Container,
289                          const Expr *E) {
290   llvm::FoldingSetNodeID ID;
291   E->Profile(ID, *Context, true);
292   for (typename ContainerT::const_iterator I = Container->begin(),
293        End = Container->end(); I != End; ++I)
294     if (ID == I->second)
295       return true;
296   return false;
297 }
298
299 /// \brief Returns true when the index expression is a declaration reference to
300 /// IndexVar and the array's base exists.
301 ///
302 /// If the index variable is `index`, this function returns true on
303 ///    arrayExpression[index];
304 ///    containerExpression[index];
305 /// but not
306 ///    containerExpression[notIndex];
307 static bool isIndexInSubscriptExpr(const Expr *IndexExpr,
308                                    const VarDecl *IndexVar,
309                                    const Expr *Arr) {
310   const DeclRefExpr *Idx = getDeclRef(IndexExpr);
311   return Arr && Idx && Idx->getType()->isIntegerType()
312              && areSameVariable(IndexVar, Idx->getDecl());
313 }
314
315 /// \brief Returns true when the index expression is a declaration reference to
316 /// IndexVar, Obj is the same expression as SourceExpr after all parens and
317 /// implicit casts are stripped off.
318 ///
319 /// If PermitDeref is true, IndexExpression may
320 /// be a dereference (overloaded or builtin operator*).
321 ///
322 /// This function is intended for array-like containers, as it makes sure that
323 /// both the container and the index match.
324 /// If the loop has index variable `index` and iterates over `container`, then
325 /// isIndexInSubscriptExpr returns true for
326 ///   container[index]
327 ///   container.at(index)
328 ///   container->at(index)
329 /// but not for
330 ///   container[notIndex]
331 ///   notContainer[index]
332 /// If PermitDeref is true, then isIndexInSubscriptExpr additionally returns
333 /// true on these expressions:
334 ///   (*container)[index]
335 ///   (*container).at(index)
336 static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
337                                    const VarDecl *IndexVar, const Expr *Obj,
338                                    const Expr *SourceExpr, bool PermitDeref) {
339   if (!SourceExpr || !Obj
340       || !isIndexInSubscriptExpr(IndexExpr, IndexVar, Obj))
341     return false;
342
343   if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
344                    Obj->IgnoreParenImpCasts()))
345     return true;
346
347   if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))
348     if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
349                                    InnerObj->IgnoreParenImpCasts()))
350       return true;
351
352   return false;
353 }
354
355 /// \brief Returns true when Opcall is a call a one-parameter operator on
356 /// IndexVar.
357 ///
358 /// Note that this function assumes that the opcode is operator* or operator->.
359 /// For example, if the index variable is `index`, returns true for
360 ///   *index
361 /// but not
362 ///   index
363 ///   *notIndex
364 static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall,
365                                   const VarDecl *IndexVar) {
366   return OpCall->getNumArgs() == 1 &&
367          exprReferencesVariable(IndexVar, OpCall->getArg(0));
368 }
369
370 /// \brief Returns true when Uop is a dereference of IndexVar.
371 ///
372 /// Note that this is the
373 /// only isValidXXX function that confirms that the opcode is correct, as there
374 /// is only one way to trigger this case (namely, the builtin operator*).
375 /// For example, if the index variable is `index`, returns true for
376 ///   *index
377 /// but not
378 ///   index
379 ///   *notIndex
380 static bool isDereferenceOfUop(const UnaryOperator *Uop,
381                                const VarDecl *IndexVar) {
382   return Uop->getOpcode() == UO_Deref &&
383       exprReferencesVariable(IndexVar, Uop->getSubExpr());
384 }
385
386 /// \brief Determines whether the given Decl defines a variable initialized to
387 /// the loop object.
388 ///
389 /// This is intended to find cases such as
390 ///   for (int i = 0; i < arraySize(arr); ++i) {
391 ///     T t = arr[i];
392 ///     // use t, do not use i
393 ///   }
394 /// and
395 ///   for (iterator i = container.begin(), e = container.end(); i != e; ++i) {
396 ///     T t = *i;
397 ///     // use t, do not use i
398 ///   }
399 static bool isAliasDecl(const Decl *TheDecl, const VarDecl *TargetDecl) {
400   const VarDecl *VDecl = dyn_cast<VarDecl>(TheDecl);
401   if (!VDecl)
402     return false;
403   if (!VDecl->hasInit())
404     return false;
405   const Expr *Init =
406       digThroughConstructors(VDecl->getInit()->IgnoreImpCasts());
407   if (!Init)
408     return false;
409
410   switch (Init->getStmtClass()) {
411   case Stmt::ArraySubscriptExprClass: {
412     const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(Init);
413     // We don't really care which array is used here. We check to make sure
414     // it was the correct one later, since the AST will traverse it next.
415     return isIndexInSubscriptExpr(ASE->getIdx(), TargetDecl, ASE->getBase());
416   }
417
418   case Stmt::UnaryOperatorClass:
419     return isDereferenceOfUop(cast<UnaryOperator>(Init), TargetDecl);
420
421   case Stmt::CXXOperatorCallExprClass: {
422       const CXXOperatorCallExpr *OpCall = cast<CXXOperatorCallExpr>(Init);
423       if (OpCall->getOperator() == OO_Star)
424         return isDereferenceOfOpCall(OpCall, TargetDecl);
425       break;
426   }
427
428   default:
429     break;
430   }
431   return false;
432 }
433
434 /// \brief Determines whether the bound of a for loop condition expression is
435 /// the same as the statically computable size of ArrayType.
436 ///
437 /// Given
438 ///   const int N = 5;
439 ///   int arr[N];
440 /// This is intended to permit
441 ///   for (int i = 0; i < N; ++i) {  /* use arr[i] */ }
442 ///   for (int i = 0; i < arraysize(arr); ++i) { /* use arr[i] */ }
443 static bool arrayMatchesBoundExpr(ASTContext *Context,
444                                   const QualType &ArrayType,
445                                   const Expr *ConditionExpr) {
446   const Type *T = ArrayType.getCanonicalType().getTypePtr();
447   if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(T)) {
448     llvm::APSInt ConditionSize;
449     if (!ConditionExpr->isIntegerConstantExpr(ConditionSize, *Context))
450       return false;
451     llvm::APSInt ArraySize(CAT->getSize());
452     return llvm::APSInt::isSameValue(ConditionSize, ArraySize);
453   }
454   return false;
455 }
456
457 /// \brief If the unary operator is a dereference of IndexVar, include it
458 /// as a valid usage and prune the traversal.
459 ///
460 /// For example, if container.begin() and container.end() both return pointers
461 /// to int, this makes sure that the initialization for `k` is not counted as an
462 /// unconvertible use of the iterator `i`.
463 ///   for (int *i = container.begin(), *e = container.end(); i != e; ++i) {
464 ///     int k = *i + 2;
465 ///   }
466 bool ForLoopIndexUseVisitor::TraverseUnaryDeref(UnaryOperator *Uop) {
467   // If we dereference an iterator that's actually a pointer, count the
468   // occurrence.
469   if (isDereferenceOfUop(Uop, IndexVar)) {
470     Usages.push_back(Usage(Uop));
471     return true;
472   }
473
474   return VisitorBase::TraverseUnaryOperator(Uop);
475 }
476
477 /// \brief If the member expression is operator-> (overloaded or not) on
478 /// IndexVar, include it as a valid usage and prune the traversal.
479 ///
480 /// For example, given
481 ///   struct Foo { int bar(); int x; };
482 ///   vector<Foo> v;
483 /// the following uses will be considered convertible:
484 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
485 ///     int b = i->bar();
486 ///     int k = i->x + 1;
487 ///   }
488 /// though
489 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
490 ///     int k = i.insert(1);
491 ///   }
492 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
493 ///     int b = e->bar();
494 ///   }
495 /// will not.
496 bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
497   const Expr *Base = Member->getBase();
498   const DeclRefExpr *Obj = getDeclRef(Base);
499   const Expr *ResultExpr = Member;
500   QualType ExprType;
501   if (const CXXOperatorCallExpr *Call =
502       dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {
503     // If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then
504     // the MemberExpr does not have the expression we want. We therefore catch
505     // that instance here.
506     // For example, if vector<Foo>::iterator defines operator->(), then the
507     // example `i->bar()` at the top of this function is a CXXMemberCallExpr
508     // referring to `i->` as the member function called. We want just `i`, so
509     // we take the argument to operator->() as the base object.
510     if(Call->getOperator() == OO_Arrow) {
511       assert(Call->getNumArgs() == 1 &&
512              "Operator-> takes more than one argument");
513       Obj = getDeclRef(Call->getArg(0));
514       ResultExpr = Obj;
515       ExprType = Call->getCallReturnType();
516     }
517   }
518
519   if (Member->isArrow() && Obj && exprReferencesVariable(IndexVar, Obj)) {
520     if (ExprType.isNull())
521       ExprType = Obj->getType();
522
523     assert(ExprType->isPointerType() && "Operator-> returned non-pointer type");
524     // FIXME: This works around not having the location of the arrow operator.
525     // Consider adding OperatorLoc to MemberExpr?
526     SourceLocation ArrowLoc =
527         Lexer::getLocForEndOfToken(Base->getExprLoc(), 0,
528                                    Context->getSourceManager(),
529                                    Context->getLangOpts());
530     // If something complicated is happening (i.e. the next token isn't an
531     // arrow), give up on making this work.
532     if (!ArrowLoc.isInvalid()) {
533       Usages.push_back(Usage(ResultExpr, /*IsArrow=*/true,
534                              SourceRange(Base->getExprLoc(), ArrowLoc)));
535       return true;
536     }
537   }
538   return TraverseStmt(Member->getBase());
539 }
540
541 /// \brief If a member function call is the at() accessor on the container with
542 /// IndexVar as the single argument, include it as a valid usage and prune
543 /// the traversal.
544 ///
545 /// Member calls on other objects will not be permitted.
546 /// Calls on the iterator object are not permitted, unless done through
547 /// operator->(). The one exception is allowing vector::at() for pseudoarrays.
548 bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
549     CXXMemberCallExpr *MemberCall) {
550   MemberExpr *Member = cast<MemberExpr>(MemberCall->getCallee());
551   // We specifically allow an accessor named "at" to let STL in, though
552   // this is restricted to pseudo-arrays by requiring a single, integer
553   // argument.
554   const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
555   if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) {
556     if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar,
557                                Member->getBase(), ContainerExpr,
558                                ContainerNeedsDereference)) {
559       Usages.push_back(Usage(MemberCall));
560       return true;
561     }
562   }
563
564   if (containsExpr(Context, &DependentExprs, Member->getBase()))
565     ConfidenceLevel.lowerTo(TCK_Risky);
566
567   return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
568 }
569
570 /// \brief If an overloaded operator call is a dereference of IndexVar or
571 /// a subscript of a the container with IndexVar as the single argument,
572 /// include it as a valid usage and prune the traversal.
573 ///
574 /// For example, given
575 ///   struct Foo { int bar(); int x; };
576 ///   vector<Foo> v;
577 ///   void f(Foo);
578 /// the following uses will be considered convertible:
579 ///   for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
580 ///     f(*i);
581 ///   }
582 ///   for (int i = 0; i < v.size(); ++i) {
583 ///      int i = v[i] + 1;
584 ///   }
585 bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
586     CXXOperatorCallExpr *OpCall) {
587   switch (OpCall->getOperator()) {
588   case OO_Star:
589     if (isDereferenceOfOpCall(OpCall, IndexVar)) {
590       Usages.push_back(Usage(OpCall));
591       return true;
592     }
593     break;
594
595   case OO_Subscript:
596     if (OpCall->getNumArgs() != 2)
597       break;
598     if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,
599                                OpCall->getArg(0), ContainerExpr,
600                                ContainerNeedsDereference)) {
601       Usages.push_back(Usage(OpCall));
602       return true;
603     }
604     break;
605
606   default:
607     break;
608   }
609   return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
610 }
611
612 /// If we encounter an array with IndexVar as the index of an
613 /// ArraySubsriptExpression, note it as a consistent usage and prune the
614 /// AST traversal.
615 ///
616 /// For example, given
617 ///   const int N = 5;
618 ///   int arr[N];
619 /// This is intended to permit
620 ///   for (int i = 0; i < N; ++i) {  /* use arr[i] */ }
621 ///   for (int i = 0; i < N; ++i) {  /* use notArr[i] */ }
622 /// and further checking needs to be done later to ensure that exactly one array
623 /// is referenced.
624 bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(
625     ArraySubscriptExpr *ASE) {
626   Expr *Arr = ASE->getBase();
627   if (isIndexInSubscriptExpr(ASE->getIdx(), IndexVar, Arr)) {
628     const Expr *ArrReduced = Arr->IgnoreParenCasts();
629     if (!containsExpr(Context, &ContainersIndexed, ArrReduced)) {
630       llvm::FoldingSetNodeID ID;
631       ArrReduced->Profile(ID, *Context, true);
632       ContainersIndexed.push_back(std::make_pair(ArrReduced, ID));
633     }
634     Usages.push_back(Usage(ASE));
635     return true;
636   }
637   return VisitorBase::TraverseArraySubscriptExpr(ASE);
638 }
639
640 /// \brief If we encounter a reference to IndexVar in an unpruned branch of the
641 /// traversal, mark this loop as unconvertible.
642 ///
643 /// This implements the whitelist for convertible loops: any usages of IndexVar
644 /// not explicitly considered convertible by this traversal will be caught by
645 /// this function.
646 ///
647 /// Additionally, if the container expression is more complex than just a
648 /// DeclRefExpr, and some part of it is appears elsewhere in the loop, lower
649 /// our confidence in the transformation.
650 ///
651 /// For example, these are not permitted:
652 ///   for (int i = 0; i < N; ++i) {  printf("arr[%d] = %d", i, arr[i]); }
653 ///   for (vector<int>::iterator i = container.begin(), e = container.end();
654 ///        i != e; ++i)
655 ///     i.insert(0);
656 ///   for (vector<int>::iterator i = container.begin(), e = container.end();
657 ///        i != e; ++i)
658 ///     i.insert(0);
659 ///   for (vector<int>::iterator i = container.begin(), e = container.end();
660 ///        i != e; ++i)
661 ///     if (i + 1 != e)
662 ///       printf("%d", *i);
663 ///
664 ///  And these will raise the risk level:
665 ///    int arr[10][20];
666 ///    int l = 5;
667 ///    for (int j = 0; j < 20; ++j)
668 ///      int k = arr[l][j] + l; // using l outside arr[l] is considered risky
669 ///    for (int i = 0; i < obj.getVector().size(); ++i)
670 ///      obj.foo(10); // using `obj` is considered risky
671 bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *DRE) {
672   const ValueDecl *TheDecl = DRE->getDecl();
673   if (areSameVariable(IndexVar, TheDecl) || areSameVariable(EndVar, TheDecl))
674     OnlyUsedAsIndex = false;
675   if (containsExpr(Context, &DependentExprs, DRE))
676     ConfidenceLevel.lowerTo(TCK_Risky);
677   return true;
678 }
679
680 /// \brief If we find that another variable is created just to refer to the loop
681 /// element, note it for reuse as the loop variable.
682 ///
683 /// See the comments for isAliasDecl.
684 bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *DS) {
685   if (!AliasDecl && DS->isSingleDecl() &&
686       isAliasDecl(DS->getSingleDecl(), IndexVar))
687       AliasDecl = DS;
688   return true;
689 }
690
691 //// \brief Apply the source transformations necessary to migrate the loop!
692 void LoopFixer::doConversion(ASTContext *Context,
693                              const VarDecl *IndexVar, const VarDecl *EndVar,
694                              const Expr *ContainerExpr,
695                              const UsageResult &Usages,
696                              const DeclStmt *AliasDecl,
697                              const ForStmt *TheLoop,
698                              bool ContainerNeedsDereference) {
699   const VarDecl *MaybeContainer = getReferencedVariable(ContainerExpr);
700   std::string VarName;
701
702   if (Usages.size() == 1 && AliasDecl) {
703     const VarDecl *AliasVar = cast<VarDecl>(AliasDecl->getSingleDecl());
704     VarName = AliasVar->getName().str();
705     // We keep along the entire DeclStmt to keep the correct range here.
706     const SourceRange &ReplaceRange = AliasDecl->getSourceRange();
707     if (!CountOnly)
708       Replace->insert(
709           Replacement(Context->getSourceManager(),
710                       CharSourceRange::getTokenRange(ReplaceRange), ""));
711     // No further replacements are made to the loop, since the iterator or index
712     // was used exactly once - in the initialization of AliasVar.
713   } else {
714     VariableNamer Namer(Context, GeneratedDecls,
715                         &ParentFinder->getStmtToParentStmtMap(),
716                         IndexVar->getDeclContext(), TheLoop, IndexVar,
717                         MaybeContainer);
718     VarName = Namer.createIndexName();
719     // First, replace all usages of the array subscript expression with our new
720     // variable.
721     for (UsageResult::const_iterator I = Usages.begin(), E = Usages.end();
722          I != E; ++I) {
723       std::string ReplaceText;
724       if (I->IsArrow)
725         ReplaceText = VarName + ".";
726       else
727         ReplaceText = VarName;
728
729       ReplacedVarRanges->insert(std::make_pair(TheLoop, IndexVar));
730       if (!CountOnly)
731         Replace->insert(
732             Replacement(Context->getSourceManager(),
733                         CharSourceRange::getTokenRange(I->Range),
734                         ReplaceText));
735     }
736   }
737
738   // Now, we need to construct the new range expresion.
739   SourceRange ParenRange(TheLoop->getLParenLoc(), TheLoop->getRParenLoc());
740   StringRef ContainerString =
741       getStringFromRange(Context->getSourceManager(), Context->getLangOpts(),
742                          ContainerExpr->getSourceRange());
743
744   QualType AutoRefType =
745       Context->getLValueReferenceType(Context->getAutoDeductType());
746
747   std::string MaybeDereference = ContainerNeedsDereference ? "*" : "";
748   std::string TypeString = AutoRefType.getAsString();
749   std::string Range = ("(" + TypeString + " " + VarName + " : "
750                            + MaybeDereference + ContainerString + ")").str();
751   if (!CountOnly)
752     Replace->insert(Replacement(Context->getSourceManager(),
753                                      CharSourceRange::getTokenRange(ParenRange),
754                                      Range));
755   GeneratedDecls->insert(make_pair(TheLoop, VarName));
756 }
757
758 /// \brief Determine whether Init appears to be an initializing an iterator.
759 ///
760 /// If it is, returns the object whose begin() or end() method is called, and
761 /// the output parameter isArrow is set to indicate whether the initialization
762 /// is called via . or ->.
763 static const Expr *getContainerFromInitializer(const Expr* Init,
764                                                bool IsBegin, bool *IsArrow) {
765   // FIXME: Maybe allow declaration/initialization outside of the for loop?
766   const CXXMemberCallExpr *TheCall =
767       dyn_cast_or_null<CXXMemberCallExpr>(digThroughConstructors(Init));
768   if (!TheCall || TheCall->getNumArgs() != 0)
769       return NULL;
770
771   const MemberExpr *Member = cast<MemberExpr>(TheCall->getCallee());
772   const std::string Name = Member->getMemberDecl()->getName();
773   const std::string TargetName = IsBegin ? "begin" : "end";
774   if (Name != TargetName)
775     return NULL;
776
777   const Expr *SourceExpr = Member->getBase();
778   if (!SourceExpr)
779     return NULL;
780
781   *IsArrow = Member->isArrow();
782   return SourceExpr;
783 }
784
785 /// \brief Determines the variable whose begin() and end() functions are called
786 /// for an iterator-based loop.
787 static const Expr *findContainer(ASTContext *Context, const VarDecl *BeginVar,
788                                  const VarDecl *EndVar, const Expr *EndExpr,
789                                  bool *ContainerNeedsDereference) {
790   const Expr *BeginInitExpr = BeginVar->getInit();
791   const Expr *EndInitExpr = EndVar ? EndVar->getInit() : EndExpr;
792
793   // Now that we know the loop variable and test expression, make sure they are
794   // valid.
795   bool BeginIsArrow = false;
796   bool EndIsArrow = false;
797   const Expr *ContainerExpr = getContainerFromInitializer(BeginInitExpr,
798                                                           /*IsBegin=*/true,
799                                                           &BeginIsArrow);
800   if (!ContainerExpr)
801       return NULL;
802   const Expr *EndSourceExpr = getContainerFromInitializer(EndInitExpr,
803                                                           /*IsBegin=*/false,
804                                                           &EndIsArrow);
805   // Disallow loops that try evil things like this (note the dot and arrow):
806   //  for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }
807   if (!EndSourceExpr || BeginIsArrow != EndIsArrow ||
808       !areSameExpr(Context, EndSourceExpr, ContainerExpr))
809     return NULL;
810
811   *ContainerNeedsDereference = BeginIsArrow;
812   return ContainerExpr;
813 }
814
815 /// \brief The LoopFixer callback, which determines if loops discovered by the
816 /// matchers are convertible, printing information about the loops if so.
817 void LoopFixer::run(const MatchFinder::MatchResult &Result) {
818   Confidence ConfidenceLevel(TCK_Safe);
819   ASTContext *Context = Result.Context;
820   const ForStmt *TheLoop = Result.Nodes.getStmtAs<ForStmt>(LoopName);
821
822   if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc()))
823     return;
824
825   const VarDecl *LoopVar = Result.Nodes.getDeclAs<VarDecl>(IncrementVarName);
826   const VarDecl *CondVar = Result.Nodes.getDeclAs<VarDecl>(ConditionVarName);
827   const VarDecl *InitVar = Result.Nodes.getDeclAs<VarDecl>(InitVarName);
828
829   if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
830     return;
831   const Expr *BoundExpr= Result.Nodes.getStmtAs<Expr>(ConditionBoundName);
832   const VarDecl *EndVar = Result.Nodes.getDeclAs<VarDecl>(EndVarName);
833   const VarDecl *ConditionEndVar =
834         Result.Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
835   const Expr *ContainerExpr = NULL;
836
837   // Make sure that the end iterator defined in the loop is actually used in the
838   // loop condition.
839   if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
840     return;
841
842   // If the end comparison isn't a variable, we can try to work with the
843   // expression the loop variable is being tested against instead.
844   const CXXMemberCallExpr *EndCall =
845       Result.Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
846
847   // If the loop calls end()/size() after each iteration, lower our confidence
848   // level.
849   if (FixerKind != LFK_Array && !EndVar) {
850     if (!EndCall)
851       return;
852     ConfidenceLevel.lowerTo(TCK_Reasonable);
853   }
854
855   bool ContainerNeedsDereference = false;
856   // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
857   // don't allow the right-recursive checks in digThroughConstructors.
858   if (FixerKind == LFK_Iterator)
859     ContainerExpr = findContainer(Context, LoopVar, EndVar, EndCall,
860                                   &ContainerNeedsDereference);
861   else if (FixerKind == LFK_PseudoArray) {
862     ContainerExpr = EndCall->getImplicitObjectArgument();
863     ContainerNeedsDereference =
864         cast<MemberExpr>(EndCall->getCallee())->isArrow();
865   }
866
867   ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
868                            ContainerNeedsDereference);
869
870   // Either a container or an integral upper bound must exist.
871   if (ContainerExpr) {
872     ComponentFinderASTVisitor ComponentFinder;
873     ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
874     Finder.addComponents(ComponentFinder.getComponents());
875   } else if (!BoundExpr)
876     return;
877
878   if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
879     return;
880
881   if (!Finder.indexesSingleContainer())
882     return;
883
884   ConfidenceLevel.lowerTo(Finder.getConfidenceLevel());
885   // We require that a single array/container be indexed into by LoopVar.
886   // This check is done by ForLoopIndexUseVisitor for non-array loops, but we
887   // may not know which array is being looped over until the end of the
888   // traversal.
889   if (FixerKind == LFK_Array) {
890     ContainerExpr = Finder.getSingleContainerIndexed();
891     if (!arrayMatchesBoundExpr(Context, ContainerExpr->getType(), BoundExpr))
892       return;
893     // Very few loops are over expressions that generate arrays rather than
894     // array variables. Consider loops over arrays that aren't just represented
895     // by a variable to be risky conversions.
896     if (!getReferencedVariable(ContainerExpr) &&
897         !isDirectMemberExpr(ContainerExpr))
898       ConfidenceLevel.lowerTo(TCK_Risky);
899   }
900
901   // If we already modified the range of this for loop, don't do any further
902   // updates on this iteration.
903   // FIXME: Once Replacements can detect conflicting edits, replace this
904   // implementation and rely on conflicting edit detection instead.
905   if (ReplacedVarRanges->count(TheLoop)) {
906     ++*DeferredChanges;
907     return;
908   }
909
910   ParentFinder->gatherAncestors(Context->getTranslationUnitDecl(),
911                                 /*RunEvenIfNotEmpty=*/false);
912
913   // Ensure that we do not try to move an expression dependent on a local
914   // variable declared inside the loop outside of it!
915   DependencyFinderASTVisitor
916       DependencyFinder(&ParentFinder->getStmtToParentStmtMap(),
917                        &ParentFinder->getDeclToParentStmtMap(),
918                        ReplacedVarRanges, TheLoop);
919   // Not all of these are actually deferred changes.
920   // FIXME: Determine when the external dependency isn't an expression converted
921   // by another loop.
922   if (DependencyFinder.dependsOnOutsideVariable(ContainerExpr)) {
923     ++*DeferredChanges;
924     return;
925   }
926
927   if (ConfidenceLevel.get() < RequiredConfidenceLevel) {
928     ++*RejectedChanges;
929     return;
930   }
931
932   doConversion(Context, LoopVar, EndVar, ContainerExpr, Finder.getUsages(),
933                Finder.getAliasDecl(), TheLoop, ContainerNeedsDereference);
934
935   ++*AcceptedChanges;
936 }
937
938 } // namespace loop_migrate
939 } // namespace clang