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