[clang-tidy] Add loop-convert check to clang-tidy.
Move LoopConvert from clang-modernize to modernize module in clang-tidy.
http://reviews.llvm.org/D12076
Patch by Angel Garcia!
llvm-svn: 245427
diff --git a/clang-tools-extra/clang-tidy/modernize/LoopConvertUtils.cpp b/clang-tools-extra/clang-tidy/modernize/LoopConvertUtils.cpp
new file mode 100644
index 0000000..ac8210f
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/modernize/LoopConvertUtils.cpp
@@ -0,0 +1,817 @@
+//===--- LoopConvertUtils.cpp - clang-tidy --------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LoopConvertUtils.h"
+
+using namespace clang::ast_matchers;
+using namespace clang::tooling;
+using namespace clang;
+using namespace llvm;
+
+namespace clang {
+namespace tidy {
+namespace modernize {
+
+/// \brief Tracks a stack of parent statements during traversal.
+///
+/// All this really does is inject push_back() before running
+/// RecursiveASTVisitor::TraverseStmt() and pop_back() afterwards. The Stmt atop
+/// the stack is the parent of the current statement (NULL for the topmost
+/// statement).
+bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) {
+ StmtAncestors.insert(std::make_pair(Statement, StmtStack.back()));
+ StmtStack.push_back(Statement);
+ RecursiveASTVisitor<StmtAncestorASTVisitor>::TraverseStmt(Statement);
+ StmtStack.pop_back();
+ return true;
+}
+
+/// \brief Keep track of the DeclStmt associated with each VarDecl.
+///
+/// Combined with StmtAncestors, this provides roughly the same information as
+/// Scope, as we can map a VarDecl to its DeclStmt, then walk up the parent tree
+/// using StmtAncestors.
+bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Decls) {
+ for (const auto *decl : Decls->decls()) {
+ if (const auto *V = dyn_cast<VarDecl>(decl))
+ DeclParents.insert(std::make_pair(V, Decls));
+ }
+ return true;
+}
+
+/// \brief record the DeclRefExpr as part of the parent expression.
+bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) {
+ Components.push_back(E);
+ return true;
+}
+
+/// \brief record the MemberExpr as part of the parent expression.
+bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) {
+ Components.push_back(Member);
+ return true;
+}
+
+/// \brief Forward any DeclRefExprs to a check on the referenced variable
+/// declaration.
+bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
+ if (auto *V = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
+ return VisitVarDecl(V);
+ return true;
+}
+
+/// \brief Determine if any this variable is declared inside the ContainingStmt.
+bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) {
+ const Stmt *Curr = DeclParents->lookup(V);
+ // First, see if the variable was declared within an inner scope of the loop.
+ while (Curr != nullptr) {
+ if (Curr == ContainingStmt) {
+ DependsOnInsideVariable = true;
+ return false;
+ }
+ Curr = StmtParents->lookup(Curr);
+ }
+
+ // Next, check if the variable was removed from existence by an earlier
+ // iteration.
+ for (const auto &I : *ReplacedVars) {
+ if (I.second == V) {
+ DependsOnInsideVariable = true;
+ return false;
+ }
+ }
+ return true;
+}
+
+/// \brief If we already created a variable for TheLoop, check to make sure
+/// that the name was not already taken.
+bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) {
+ StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(TheLoop);
+ if (I != GeneratedDecls->end() && I->second == Name) {
+ Found = true;
+ return false;
+ }
+ return true;
+}
+
+/// \brief If any named declaration within the AST subtree has the same name,
+/// then consider Name already taken.
+bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) {
+ const IdentifierInfo *Ident = D->getIdentifier();
+ if (Ident && Ident->getName() == Name) {
+ Found = true;
+ return false;
+ }
+ return true;
+}
+
+/// \brief Forward any declaration references to the actual check on the
+/// referenced declaration.
+bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
+ if (auto *D = dyn_cast<NamedDecl>(DeclRef->getDecl()))
+ return VisitNamedDecl(D);
+ return true;
+}
+
+/// \brief If the new variable name conflicts with any type used in the loop,
+/// then we mark that variable name as taken.
+bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) {
+ QualType QType = TL.getType();
+
+ // Check if our name conflicts with a type, to handle for typedefs.
+ if (QType.getAsString() == Name) {
+ Found = true;
+ return false;
+ }
+ // Check for base type conflicts. For example, when a struct is being
+ // referenced in the body of the loop, the above getAsString() will return the
+ // whole type (ex. "struct s"), but will be caught here.
+ if (const IdentifierInfo *Ident = QType.getBaseTypeIdentifier()) {
+ if (Ident->getName() == Name) {
+ Found = true;
+ return false;
+ }
+ }
+ return true;
+}
+
+/// \brief Look through conversion/copy constructors to find the explicit
+/// initialization expression, returning it is found.
+///
+/// The main idea is that given
+/// vector<int> v;
+/// we consider either of these initializations
+/// vector<int>::iterator it = v.begin();
+/// vector<int>::iterator it(v.begin());
+/// and retrieve `v.begin()` as the expression used to initialize `it` but do
+/// not include
+/// vector<int>::iterator it;
+/// vector<int>::iterator it(v.begin(), 0); // if this constructor existed
+/// as being initialized from `v.begin()`
+const Expr *digThroughConstructors(const Expr *E) {
+ if (!E)
+ return nullptr;
+ E = E->IgnoreParenImpCasts();
+ if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {
+ // The initial constructor must take exactly one parameter, but base class
+ // and deferred constructors can take more.
+ if (ConstructExpr->getNumArgs() != 1 ||
+ ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_Complete)
+ return nullptr;
+ E = ConstructExpr->getArg(0);
+ if (const auto *Temp = dyn_cast<MaterializeTemporaryExpr>(E))
+ E = Temp->GetTemporaryExpr();
+ return digThroughConstructors(E);
+ }
+ return E;
+}
+
+/// \brief Returns true when two Exprs are equivalent.
+bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second) {
+ if (!First || !Second)
+ return false;
+
+ llvm::FoldingSetNodeID FirstID, SecondID;
+ First->Profile(FirstID, *Context, true);
+ Second->Profile(SecondID, *Context, true);
+ return FirstID == SecondID;
+}
+
+/// \brief Returns the DeclRefExpr represented by E, or NULL if there isn't one.
+const DeclRefExpr *getDeclRef(const Expr *E) {
+ return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());
+}
+
+/// \brief Returns true when two ValueDecls are the same variable.
+bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) {
+ return First && Second &&
+ First->getCanonicalDecl() == Second->getCanonicalDecl();
+}
+
+/// \brief Determines if an expression is a declaration reference to a
+/// particular variable.
+static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) {
+ if (!Target || !E)
+ return false;
+ const DeclRefExpr *Decl = getDeclRef(E);
+ return Decl && areSameVariable(Target, Decl->getDecl());
+}
+
+/// \brief If the expression is a dereference or call to operator*(), return the
+/// operand. Otherwise, return NULL.
+static const Expr *getDereferenceOperand(const Expr *E) {
+ if (const auto *Uop = dyn_cast<UnaryOperator>(E))
+ return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : nullptr;
+
+ if (const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(E)) {
+ return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1
+ ? OpCall->getArg(0)
+ : nullptr;
+ }
+
+ return nullptr;
+}
+
+/// \brief Returns true when the Container contains an Expr equivalent to E.
+template <typename ContainerT>
+static bool containsExpr(ASTContext *Context, const ContainerT *Container,
+ const Expr *E) {
+ llvm::FoldingSetNodeID ID;
+ E->Profile(ID, *Context, true);
+ for (const auto &I : *Container) {
+ if (ID == I.second)
+ return true;
+ }
+ return false;
+}
+
+/// \brief Returns true when the index expression is a declaration reference to
+/// IndexVar.
+///
+/// If the index variable is `index`, this function returns true on
+/// arrayExpression[index];
+/// containerExpression[index];
+/// but not
+/// containerExpression[notIndex];
+static bool isIndexInSubscriptExpr(const Expr *IndexExpr,
+ const VarDecl *IndexVar) {
+ const DeclRefExpr *Idx = getDeclRef(IndexExpr);
+ return Idx && Idx->getType()->isIntegerType() &&
+ areSameVariable(IndexVar, Idx->getDecl());
+}
+
+/// \brief Returns true when the index expression is a declaration reference to
+/// IndexVar, Obj is the same expression as SourceExpr after all parens and
+/// implicit casts are stripped off.
+///
+/// If PermitDeref is true, IndexExpression may
+/// be a dereference (overloaded or builtin operator*).
+///
+/// This function is intended for array-like containers, as it makes sure that
+/// both the container and the index match.
+/// If the loop has index variable `index` and iterates over `container`, then
+/// isIndexInSubscriptExpr returns true for
+/// \code
+/// container[index]
+/// container.at(index)
+/// container->at(index)
+/// \endcode
+/// but not for
+/// \code
+/// container[notIndex]
+/// notContainer[index]
+/// \endcode
+/// If PermitDeref is true, then isIndexInSubscriptExpr additionally returns
+/// true on these expressions:
+/// \code
+/// (*container)[index]
+/// (*container).at(index)
+/// \endcode
+static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
+ const VarDecl *IndexVar, const Expr *Obj,
+ const Expr *SourceExpr, bool PermitDeref) {
+ if (!SourceExpr || !Obj || !isIndexInSubscriptExpr(IndexExpr, IndexVar))
+ return false;
+
+ if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
+ Obj->IgnoreParenImpCasts()))
+ return true;
+
+ if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))
+ if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
+ InnerObj->IgnoreParenImpCasts()))
+ return true;
+
+ return false;
+}
+
+/// \brief Returns true when Opcall is a call a one-parameter dereference of
+/// IndexVar.
+///
+/// For example, if the index variable is `index`, returns true for
+/// *index
+/// but not
+/// index
+/// *notIndex
+static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall,
+ const VarDecl *IndexVar) {
+ return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&
+ exprReferencesVariable(IndexVar, OpCall->getArg(0));
+}
+
+/// \brief Returns true when Uop is a dereference of IndexVar.
+///
+/// For example, if the index variable is `index`, returns true for
+/// *index
+/// but not
+/// index
+/// *notIndex
+static bool isDereferenceOfUop(const UnaryOperator *Uop,
+ const VarDecl *IndexVar) {
+ return Uop->getOpcode() == UO_Deref &&
+ exprReferencesVariable(IndexVar, Uop->getSubExpr());
+}
+
+/// \brief Determines whether the given Decl defines a variable initialized to
+/// the loop object.
+///
+/// This is intended to find cases such as
+/// \code
+/// for (int i = 0; i < arraySize(arr); ++i) {
+/// T t = arr[i];
+/// // use t, do not use i
+/// }
+/// \endcode
+/// and
+/// \code
+/// for (iterator i = container.begin(), e = container.end(); i != e; ++i) {
+/// T t = *i;
+/// // use t, do not use i
+/// }
+/// \endcode
+static bool isAliasDecl(const Decl *TheDecl, const VarDecl *IndexVar) {
+ const auto *VDecl = dyn_cast<VarDecl>(TheDecl);
+ if (!VDecl)
+ return false;
+ if (!VDecl->hasInit())
+ return false;
+
+ const Expr *Init =
+ digThroughConstructors(VDecl->getInit()->IgnoreParenImpCasts());
+ if (!Init)
+ return false;
+
+ switch (Init->getStmtClass()) {
+ case Stmt::ArraySubscriptExprClass: {
+ const auto *E = cast<ArraySubscriptExpr>(Init);
+ // We don't really care which array is used here. We check to make sure
+ // it was the correct one later, since the AST will traverse it next.
+ return isIndexInSubscriptExpr(E->getIdx(), IndexVar);
+ }
+
+ case Stmt::UnaryOperatorClass:
+ return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar);
+
+ case Stmt::CXXOperatorCallExprClass: {
+ const auto *OpCall = cast<CXXOperatorCallExpr>(Init);
+ if (OpCall->getOperator() == OO_Star)
+ return isDereferenceOfOpCall(OpCall, IndexVar);
+ if (OpCall->getOperator() == OO_Subscript) {
+ assert(OpCall->getNumArgs() == 2);
+ return true;
+ }
+ break;
+ }
+
+ case Stmt::CXXMemberCallExprClass:
+ return true;
+
+ default:
+ break;
+ }
+ return false;
+}
+
+/// \brief Determines whether the bound of a for loop condition expression is
+/// the same as the statically computable size of ArrayType.
+///
+/// Given
+/// \code
+/// const int N = 5;
+/// int arr[N];
+/// \endcode
+/// This is intended to permit
+/// \code
+/// for (int i = 0; i < N; ++i) { /* use arr[i] */ }
+/// for (int i = 0; i < arraysize(arr); ++i) { /* use arr[i] */ }
+/// \endcode
+static bool arrayMatchesBoundExpr(ASTContext *Context,
+ const QualType &ArrayType,
+ const Expr *ConditionExpr) {
+ if (!ConditionExpr || ConditionExpr->isValueDependent())
+ return false;
+ const ConstantArrayType *ConstType =
+ Context->getAsConstantArrayType(ArrayType);
+ if (!ConstType)
+ return false;
+ llvm::APSInt ConditionSize;
+ if (!ConditionExpr->isIntegerConstantExpr(ConditionSize, *Context))
+ return false;
+ llvm::APSInt ArraySize(ConstType->getSize());
+ return llvm::APSInt::isSameValue(ConditionSize, ArraySize);
+}
+
+ForLoopIndexUseVisitor::ForLoopIndexUseVisitor(ASTContext *Context,
+ const VarDecl *IndexVar,
+ const VarDecl *EndVar,
+ const Expr *ContainerExpr,
+ const Expr *ArrayBoundExpr,
+ bool ContainerNeedsDereference)
+ : Context(Context), IndexVar(IndexVar), EndVar(EndVar),
+ ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),
+ ContainerNeedsDereference(ContainerNeedsDereference),
+ OnlyUsedAsIndex(true), AliasDecl(nullptr),
+ ConfidenceLevel(Confidence::CL_Safe), NextStmtParent(nullptr),
+ CurrStmtParent(nullptr), ReplaceWithAliasUse(false),
+ AliasFromForInit(false) {
+ if (ContainerExpr) {
+ addComponent(ContainerExpr);
+ FoldingSetNodeID ID;
+ const Expr *E = ContainerExpr->IgnoreParenImpCasts();
+ E->Profile(ID, *Context, true);
+ }
+}
+
+bool ForLoopIndexUseVisitor::findAndVerifyUsages(const Stmt *Body) {
+ TraverseStmt(const_cast<Stmt *>(Body));
+ return OnlyUsedAsIndex && ContainerExpr;
+}
+
+void ForLoopIndexUseVisitor::addComponents(const ComponentVector &Components) {
+ // FIXME: add sort(on ID)+unique to avoid extra work.
+ for (const auto &I : Components)
+ addComponent(I);
+}
+
+void ForLoopIndexUseVisitor::addComponent(const Expr *E) {
+ FoldingSetNodeID ID;
+ const Expr *Node = E->IgnoreParenImpCasts();
+ Node->Profile(ID, *Context, true);
+ DependentExprs.push_back(std::make_pair(Node, ID));
+}
+
+/// \brief If the unary operator is a dereference of IndexVar, include it
+/// as a valid usage and prune the traversal.
+///
+/// For example, if container.begin() and container.end() both return pointers
+/// to int, this makes sure that the initialization for `k` is not counted as an
+/// unconvertible use of the iterator `i`.
+/// \code
+/// for (int *i = container.begin(), *e = container.end(); i != e; ++i) {
+/// int k = *i + 2;
+/// }
+/// \endcode
+bool ForLoopIndexUseVisitor::TraverseUnaryDeref(UnaryOperator *Uop) {
+ // If we dereference an iterator that's actually a pointer, count the
+ // occurrence.
+ if (isDereferenceOfUop(Uop, IndexVar)) {
+ Usages.push_back(Usage(Uop));
+ return true;
+ }
+
+ return VisitorBase::TraverseUnaryOperator(Uop);
+}
+
+/// \brief If the member expression is operator-> (overloaded or not) on
+/// IndexVar, include it as a valid usage and prune the traversal.
+///
+/// For example, given
+/// \code
+/// struct Foo { int bar(); int x; };
+/// vector<Foo> v;
+/// \endcode
+/// the following uses will be considered convertible:
+/// \code
+/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
+/// int b = i->bar();
+/// int k = i->x + 1;
+/// }
+/// \endcode
+/// though
+/// \code
+/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
+/// int k = i.insert(1);
+/// }
+/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
+/// int b = e->bar();
+/// }
+/// \endcode
+/// will not.
+bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
+ const Expr *Base = Member->getBase();
+ const DeclRefExpr *Obj = getDeclRef(Base);
+ const Expr *ResultExpr = Member;
+ QualType ExprType;
+ if (const auto *Call =
+ dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {
+ // If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then
+ // the MemberExpr does not have the expression we want. We therefore catch
+ // that instance here.
+ // For example, if vector<Foo>::iterator defines operator->(), then the
+ // example `i->bar()` at the top of this function is a CXXMemberCallExpr
+ // referring to `i->` as the member function called. We want just `i`, so
+ // we take the argument to operator->() as the base object.
+ if (Call->getOperator() == OO_Arrow) {
+ assert(Call->getNumArgs() == 1 &&
+ "Operator-> takes more than one argument");
+ Obj = getDeclRef(Call->getArg(0));
+ ResultExpr = Obj;
+ ExprType = Call->getCallReturnType(*Context);
+ }
+ }
+
+ if (Member->isArrow() && Obj && exprReferencesVariable(IndexVar, Obj)) {
+ if (ExprType.isNull())
+ ExprType = Obj->getType();
+
+ assert(ExprType->isPointerType() && "Operator-> returned non-pointer type");
+ // FIXME: This works around not having the location of the arrow operator.
+ // Consider adding OperatorLoc to MemberExpr?
+ SourceLocation ArrowLoc = Lexer::getLocForEndOfToken(
+ Base->getExprLoc(), 0, Context->getSourceManager(),
+ Context->getLangOpts());
+ // If something complicated is happening (i.e. the next token isn't an
+ // arrow), give up on making this work.
+ if (!ArrowLoc.isInvalid()) {
+ Usages.push_back(Usage(ResultExpr, /*IsArrow=*/true,
+ SourceRange(Base->getExprLoc(), ArrowLoc)));
+ return true;
+ }
+ }
+ return TraverseStmt(Member->getBase());
+}
+
+/// \brief If a member function call is the at() accessor on the container with
+/// IndexVar as the single argument, include it as a valid usage and prune
+/// the traversal.
+///
+/// Member calls on other objects will not be permitted.
+/// Calls on the iterator object are not permitted, unless done through
+/// operator->(). The one exception is allowing vector::at() for pseudoarrays.
+bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
+ CXXMemberCallExpr *MemberCall) {
+ auto *Member =
+ dyn_cast<MemberExpr>(MemberCall->getCallee()->IgnoreParenImpCasts());
+ if (!Member)
+ return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
+
+ // We specifically allow an accessor named "at" to let STL in, though
+ // this is restricted to pseudo-arrays by requiring a single, integer
+ // argument.
+ const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
+ if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) {
+ if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar,
+ Member->getBase(), ContainerExpr,
+ ContainerNeedsDereference)) {
+ Usages.push_back(Usage(MemberCall));
+ return true;
+ }
+ }
+
+ if (containsExpr(Context, &DependentExprs, Member->getBase()))
+ ConfidenceLevel.lowerTo(Confidence::CL_Risky);
+
+ return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
+}
+
+/// \brief If an overloaded operator call is a dereference of IndexVar or
+/// a subscript of a the container with IndexVar as the single argument,
+/// include it as a valid usage and prune the traversal.
+///
+/// For example, given
+/// \code
+/// struct Foo { int bar(); int x; };
+/// vector<Foo> v;
+/// void f(Foo);
+/// \endcode
+/// the following uses will be considered convertible:
+/// \code
+/// for (vector<Foo>::iterator i = v.begin(), e = v.end(); i != e; ++i) {
+/// f(*i);
+/// }
+/// for (int i = 0; i < v.size(); ++i) {
+/// int i = v[i] + 1;
+/// }
+/// \endcode
+bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
+ CXXOperatorCallExpr *OpCall) {
+ switch (OpCall->getOperator()) {
+ case OO_Star:
+ if (isDereferenceOfOpCall(OpCall, IndexVar)) {
+ Usages.push_back(Usage(OpCall));
+ return true;
+ }
+ break;
+
+ case OO_Subscript:
+ if (OpCall->getNumArgs() != 2)
+ break;
+ if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,
+ OpCall->getArg(0), ContainerExpr,
+ ContainerNeedsDereference)) {
+ Usages.push_back(Usage(OpCall));
+ return true;
+ }
+ break;
+
+ default:
+ break;
+ }
+ return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
+}
+
+/// \brief If we encounter an array with IndexVar as the index of an
+/// ArraySubsriptExpression, note it as a consistent usage and prune the
+/// AST traversal.
+///
+/// For example, given
+/// \code
+/// const int N = 5;
+/// int arr[N];
+/// \endcode
+/// This is intended to permit
+/// \code
+/// for (int i = 0; i < N; ++i) { /* use arr[i] */ }
+/// \endcode
+/// but not
+/// \code
+/// for (int i = 0; i < N; ++i) { /* use notArr[i] */ }
+/// \endcode
+/// and further checking needs to be done later to ensure that exactly one array
+/// is referenced.
+bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(ArraySubscriptExpr *E) {
+ Expr *Arr = E->getBase();
+ if (!isIndexInSubscriptExpr(E->getIdx(), IndexVar))
+ return VisitorBase::TraverseArraySubscriptExpr(E);
+
+ if ((ContainerExpr &&
+ !areSameExpr(Context, Arr->IgnoreParenImpCasts(),
+ ContainerExpr->IgnoreParenImpCasts())) ||
+ !arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(),
+ ArrayBoundExpr)) {
+ // If we have already discovered the array being indexed and this isn't it
+ // or this array doesn't match, mark this loop as unconvertible.
+ OnlyUsedAsIndex = false;
+ return VisitorBase::TraverseArraySubscriptExpr(E);
+ }
+
+ if (!ContainerExpr)
+ ContainerExpr = Arr;
+
+ Usages.push_back(Usage(E));
+ return true;
+}
+
+/// \brief If we encounter a reference to IndexVar in an unpruned branch of the
+/// traversal, mark this loop as unconvertible.
+///
+/// This implements the whitelist for convertible loops: any usages of IndexVar
+/// not explicitly considered convertible by this traversal will be caught by
+/// this function.
+///
+/// Additionally, if the container expression is more complex than just a
+/// DeclRefExpr, and some part of it is appears elsewhere in the loop, lower
+/// our confidence in the transformation.
+///
+/// For example, these are not permitted:
+/// \code
+/// for (int i = 0; i < N; ++i) { printf("arr[%d] = %d", i, arr[i]); }
+/// for (vector<int>::iterator i = container.begin(), e = container.end();
+/// i != e; ++i)
+/// i.insert(0);
+/// for (vector<int>::iterator i = container.begin(), e = container.end();
+/// i != e; ++i)
+/// i.insert(0);
+/// for (vector<int>::iterator i = container.begin(), e = container.end();
+/// i != e; ++i)
+/// if (i + 1 != e)
+/// printf("%d", *i);
+/// \endcode
+///
+/// And these will raise the risk level:
+/// \code
+/// int arr[10][20];
+/// int l = 5;
+/// for (int j = 0; j < 20; ++j)
+/// int k = arr[l][j] + l; // using l outside arr[l] is considered risky
+/// for (int i = 0; i < obj.getVector().size(); ++i)
+/// obj.foo(10); // using `obj` is considered risky
+/// \endcode
+bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *E) {
+ const ValueDecl *TheDecl = E->getDecl();
+ if (areSameVariable(IndexVar, TheDecl) || areSameVariable(EndVar, TheDecl))
+ OnlyUsedAsIndex = false;
+ if (containsExpr(Context, &DependentExprs, E))
+ ConfidenceLevel.lowerTo(Confidence::CL_Risky);
+ return true;
+}
+
+/// \brief If we find that another variable is created just to refer to the loop
+/// element, note it for reuse as the loop variable.
+///
+/// See the comments for isAliasDecl.
+bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *S) {
+ if (!AliasDecl && S->isSingleDecl() &&
+ isAliasDecl(S->getSingleDecl(), IndexVar)) {
+ AliasDecl = S;
+ if (CurrStmtParent) {
+ if (isa<IfStmt>(CurrStmtParent) || isa<WhileStmt>(CurrStmtParent) ||
+ isa<SwitchStmt>(CurrStmtParent))
+ ReplaceWithAliasUse = true;
+ else if (isa<ForStmt>(CurrStmtParent)) {
+ if (cast<ForStmt>(CurrStmtParent)->getConditionVariableDeclStmt() == S)
+ ReplaceWithAliasUse = true;
+ else
+ // It's assumed S came the for loop's init clause.
+ AliasFromForInit = true;
+ }
+ }
+ }
+
+ return true;
+}
+
+bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) {
+ // All this pointer swapping is a mechanism for tracking immediate parentage
+ // of Stmts.
+ const Stmt *OldNextParent = NextStmtParent;
+ CurrStmtParent = NextStmtParent;
+ NextStmtParent = S;
+ bool Result = VisitorBase::TraverseStmt(S);
+ NextStmtParent = OldNextParent;
+ return Result;
+}
+
+std::string VariableNamer::createIndexName() {
+ // FIXME: Add in naming conventions to handle:
+ // - Uppercase/lowercase indices.
+ // - How to handle conflicts.
+ // - An interactive process for naming.
+ std::string IteratorName;
+ std::string ContainerName;
+ if (TheContainer)
+ ContainerName = TheContainer->getName().str();
+
+ size_t Len = ContainerName.length();
+ if (Len > 1 && ContainerName[Len - 1] == 's')
+ IteratorName = ContainerName.substr(0, Len - 1);
+ else
+ IteratorName = "elem";
+
+ if (!declarationExists(IteratorName))
+ return IteratorName;
+
+ IteratorName = ContainerName + "_" + OldIndex->getName().str();
+ if (!declarationExists(IteratorName))
+ return IteratorName;
+
+ IteratorName = ContainerName + "_elem";
+ if (!declarationExists(IteratorName))
+ return IteratorName;
+
+ IteratorName += "_elem";
+ if (!declarationExists(IteratorName))
+ return IteratorName;
+
+ IteratorName = "_elem_";
+
+ // Someone defeated my naming scheme...
+ while (declarationExists(IteratorName))
+ IteratorName += "i";
+ return IteratorName;
+}
+
+/// \brief Determines whether or not the the name \a Symbol conflicts with
+/// language keywords or defined macros. Also checks if the name exists in
+/// LoopContext, any of its parent contexts, or any of its child statements.
+///
+/// We also check to see if the same identifier was generated by this loop
+/// converter in a loop nested within SourceStmt.
+bool VariableNamer::declarationExists(StringRef Symbol) {
+ assert(Context != nullptr && "Expected an ASTContext");
+ IdentifierInfo &Ident = Context->Idents.get(Symbol);
+
+ // Check if the symbol is not an identifier (ie. is a keyword or alias).
+ if (!isAnyIdentifier(Ident.getTokenID()))
+ return true;
+
+ // Check for conflicting macro definitions.
+ if (Ident.hasMacroDefinition())
+ return true;
+
+ // Determine if the symbol was generated in a parent context.
+ for (const Stmt *S = SourceStmt; S != nullptr; S = ReverseAST->lookup(S)) {
+ StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S);
+ if (I != GeneratedDecls->end() && I->second == Symbol)
+ return true;
+ }
+
+ // FIXME: Rather than detecting conflicts at their usages, we should check the
+ // parent context.
+ // For some reason, lookup() always returns the pair (NULL, NULL) because its
+ // StoredDeclsMap is not initialized (i.e. LookupPtr.getInt() is false inside
+ // of DeclContext::lookup()). Why is this?
+
+ // Finally, determine if the symbol was used in the loop or a child context.
+ DeclFinderASTVisitor DeclFinder(Symbol, GeneratedDecls);
+ return DeclFinder.findUsages(SourceStmt);
+}
+
+} // namespace modernize
+} // namespace tidy
+} // namespace clang