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