10#include "clang/Basic/IdentifierTable.h"
11#include "clang/Basic/LLVM.h"
12#include "clang/Basic/Lambda.h"
13#include "clang/Basic/SourceLocation.h"
14#include "clang/Basic/SourceManager.h"
15#include "clang/Basic/TokenKinds.h"
16#include "clang/Lex/Lexer.h"
17#include "llvm/ADT/APSInt.h"
18#include "llvm/ADT/FoldingSet.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/Support/Casting.h"
38bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) {
39 StmtAncestors.insert(std::make_pair(Statement, StmtStack.back()));
40 StmtStack.push_back(Statement);
51bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Decls) {
52 for (
const auto *
Decl : Decls->decls()) {
53 if (
const auto *V = dyn_cast<VarDecl>(
Decl))
54 DeclParents.insert(std::make_pair(V, Decls));
60bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *
E) {
61 Components.push_back(
E);
66bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) {
67 Components.push_back(Member);
73bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *
DeclRef) {
74 if (
auto *V = dyn_cast_or_null<VarDecl>(
DeclRef->getDecl()))
75 return VisitVarDecl(V);
80bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) {
81 const Stmt *Curr = DeclParents->lookup(V);
83 while (Curr !=
nullptr) {
84 if (Curr == ContainingStmt) {
85 DependsOnInsideVariable =
true;
88 Curr = StmtParents->lookup(Curr);
93 for (
const auto &I : *ReplacedVars) {
95 DependsOnInsideVariable =
true;
104bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) {
105 StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(TheLoop);
106 if (I != GeneratedDecls->end() && I->second == Name) {
115bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) {
116 const IdentifierInfo *Ident =
D->getIdentifier();
117 if (Ident && Ident->getName() == Name) {
126bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *
DeclRef) {
127 if (
auto *D = dyn_cast<NamedDecl>(
DeclRef->getDecl()))
128 return VisitNamedDecl(D);
134bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) {
135 QualType QType = TL.getType();
138 if (QType.getAsString() == Name) {
145 if (
const IdentifierInfo *Ident = QType.getBaseTypeIdentifier()) {
146 if (Ident->getName() == Name) {
171 E =
E->IgnoreImplicit();
172 if (
const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(
E)) {
175 if (ConstructExpr->getNumArgs() != 1 ||
176 ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_Complete)
178 E = ConstructExpr->getArg(0);
179 if (
const auto *Temp = dyn_cast<MaterializeTemporaryExpr>(
E))
180 E = Temp->getSubExpr();
185 if (
const auto *ME = dyn_cast<CXXMemberCallExpr>(
E))
186 if (isa<CXXConversionDecl>(ME->getMethodDecl()))
192bool areSameExpr(ASTContext *Context,
const Expr *First,
const Expr *Second) {
193 if (!First || !Second)
196 llvm::FoldingSetNodeID FirstID, SecondID;
197 First->Profile(FirstID, *Context,
true);
198 Second->Profile(SecondID, *Context,
true);
199 return FirstID == SecondID;
204 return dyn_cast<DeclRefExpr>(
E->IgnoreParenImpCasts());
209 return First && Second &&
210 First->getCanonicalDecl() == Second->getCanonicalDecl();
225 if (
const auto *Uop = dyn_cast<UnaryOperator>(
E))
226 return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() :
nullptr;
228 if (
const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(
E)) {
229 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1
238template <
typename ContainerT>
239static bool containsExpr(ASTContext *Context,
const ContainerT *Container,
241 llvm::FoldingSetNodeID ID;
242 E->Profile(ID, *Context,
true);
259 const VarDecl *IndexVar) {
260 const DeclRefExpr *Idx =
getDeclRef(IndexExpr);
261 return Idx && Idx->getType()->isIntegerType() &&
293 const VarDecl *IndexVar,
const Expr *Obj,
294 const Expr *SourceExpr,
bool PermitDeref) {
298 if (
areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
299 Obj->IgnoreParenImpCasts()))
303 if (PermitDeref &&
areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
304 InnerObj->IgnoreParenImpCasts()))
319 const VarDecl *IndexVar) {
320 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&
332 const VarDecl *IndexVar) {
333 return Uop->getOpcode() == UO_Deref &&
355 const VarDecl *IndexVar) {
356 const auto *VDecl = dyn_cast<VarDecl>(
TheDecl);
359 if (!VDecl->hasInit())
362 bool OnlyCasts =
true;
363 const Expr *Init = VDecl->getInit()->IgnoreParenImpCasts();
364 if (isa_and_nonnull<CXXConstructExpr>(Init)) {
374 QualType InitType = Init->getType();
375 QualType DeclarationType = VDecl->getType();
376 if (!DeclarationType.isNull() && DeclarationType->isReferenceType())
377 DeclarationType = DeclarationType.getNonReferenceType();
379 if (InitType.isNull() || DeclarationType.isNull() ||
380 !Context->hasSameUnqualifiedType(DeclarationType, InitType))
384 switch (Init->getStmtClass()) {
385 case Stmt::ArraySubscriptExprClass: {
386 const auto *
E = cast<ArraySubscriptExpr>(Init);
392 case Stmt::UnaryOperatorClass:
395 case Stmt::CXXOperatorCallExprClass: {
396 const auto *OpCall = cast<CXXOperatorCallExpr>(Init);
397 if (OpCall->getOperator() == OO_Star)
399 if (OpCall->getOperator() == OO_Subscript) {
400 return OpCall->getNumArgs() == 2 &&
406 case Stmt::CXXMemberCallExprClass: {
407 const auto *MemCall = cast<CXXMemberCallExpr>(Init);
410 const auto *MDecl = MemCall->getMethodDecl();
411 if (MDecl && !isa<CXXConversionDecl>(MDecl) &&
412 MDecl->getNameAsString() ==
"at" && MemCall->getNumArgs() == 1) {
438 const QualType &ArrayType,
439 const Expr *ConditionExpr) {
440 if (!ConditionExpr || ConditionExpr->isValueDependent())
442 const ConstantArrayType *ConstType =
443 Context->getAsConstantArrayType(ArrayType);
446 std::optional<llvm::APSInt> ConditionSize =
447 ConditionExpr->getIntegerConstantExpr(*Context);
450 llvm::APSInt ArraySize(ConstType->getSize());
451 return llvm::APSInt::isSameValue(*ConditionSize, ArraySize);
455 const VarDecl *IndexVar,
456 const VarDecl *EndVar,
457 const Expr *ContainerExpr,
458 const Expr *ArrayBoundExpr,
459 bool ContainerNeedsDereference)
460 : Context(Context), IndexVar(IndexVar), EndVar(EndVar),
461 ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),
462 ContainerNeedsDereference(ContainerNeedsDereference),
463 OnlyUsedAsIndex(true), AliasDecl(nullptr),
464 ConfidenceLevel(
Confidence::CL_Safe), NextStmtParent(nullptr),
465 CurrStmtParent(nullptr), ReplaceWithAliasUse(false),
466 AliasFromForInit(false) {
468 addComponent(ContainerExpr);
472 TraverseStmt(
const_cast<Stmt *
>(Body));
473 return OnlyUsedAsIndex && ContainerExpr;
478 for (
const auto &I : Components)
482void ForLoopIndexUseVisitor::addComponent(
const Expr *
E) {
483 llvm::FoldingSetNodeID ID;
484 const Expr *Node =
E->IgnoreParenImpCasts();
485 Node->Profile(ID, *Context,
true);
486 DependentExprs.push_back(std::make_pair(Node, ID));
490 SourceLocation Begin = U.
Range.getBegin();
491 if (Begin.isMacroID())
492 Begin = Context->getSourceManager().getSpellingLoc(Begin);
494 if (UsageLocations.insert(Begin).second)
509bool ForLoopIndexUseVisitor::TraverseUnaryOperator(UnaryOperator *Uop) {
517 return VisitorBase::TraverseUnaryOperator(Uop);
545bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
546 const Expr *Base = Member->getBase();
548 const Expr *ResultExpr = Member;
550 if (
const auto *Call =
551 dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {
559 if (Call->getOperator() == OO_Arrow) {
560 assert(Call->getNumArgs() == 1 &&
561 "Operator-> takes more than one argument");
564 ExprType = Call->getCallReturnType(*Context);
570 if (!Member->isArrow()) {
571 OnlyUsedAsIndex =
false;
575 if (ExprType.isNull())
576 ExprType =
Obj->getType();
578 if (!ExprType->isPointerType())
583 SourceLocation ArrowLoc = Lexer::getLocForEndOfToken(
584 Base->getExprLoc(), 0, Context->getSourceManager(),
585 Context->getLangOpts());
588 if (ArrowLoc.isValid()) {
590 SourceRange(Base->getExprLoc(), ArrowLoc)));
594 return VisitorBase::TraverseMemberExpr(Member);
604bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
605 CXXMemberCallExpr *MemberCall) {
607 dyn_cast<MemberExpr>(MemberCall->getCallee()->IgnoreParenImpCasts());
609 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
614 const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
615 if (Ident && Ident->isStr(
"at") && MemberCall->getNumArgs() == 1) {
617 Member->getBase(), ContainerExpr,
618 ContainerNeedsDereference)) {
624 if (
containsExpr(Context, &DependentExprs, Member->getBase()))
627 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
649bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
650 CXXOperatorCallExpr *OpCall) {
651 switch (OpCall->getOperator()) {
660 if (OpCall->getNumArgs() != 2)
663 OpCall->getArg(0), ContainerExpr,
664 ContainerNeedsDereference)) {
673 return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
695bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(ArraySubscriptExpr *
E) {
696 Expr *Arr =
E->getBase();
698 return VisitorBase::TraverseArraySubscriptExpr(
E);
700 if ((ContainerExpr &&
702 ContainerExpr->IgnoreParenImpCasts())) ||
707 OnlyUsedAsIndex =
false;
708 return VisitorBase::TraverseArraySubscriptExpr(
E);
750bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *
E) {
751 const ValueDecl *
TheDecl =
E->getDecl();
755 OnlyUsedAsIndex =
false;
783bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE,
784 const LambdaCapture *
C,
786 if (
C->capturesVariable()) {
787 const ValueDecl *VDecl =
C->getCapturedVar();
798 return VisitorBase::TraverseLambdaCapture(LE,
C, Init);
805bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *S) {
806 if (!AliasDecl && S->isSingleDecl() &&
807 isAliasDecl(Context, S->getSingleDecl(), IndexVar)) {
809 if (CurrStmtParent) {
810 if (isa<IfStmt>(CurrStmtParent) || isa<WhileStmt>(CurrStmtParent) ||
811 isa<SwitchStmt>(CurrStmtParent))
812 ReplaceWithAliasUse =
true;
813 else if (isa<ForStmt>(CurrStmtParent)) {
814 if (cast<ForStmt>(CurrStmtParent)->getConditionVariableDeclStmt() == S)
815 ReplaceWithAliasUse =
true;
818 AliasFromForInit =
true;
826bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) {
831 if (
const auto *LE = dyn_cast_or_null<LambdaExpr>(NextStmtParent)) {
834 if (S != LE->getBody()) {
841 const Stmt *OldNextParent = NextStmtParent;
842 CurrStmtParent = NextStmtParent;
844 bool Result = VisitorBase::TraverseStmt(S);
845 NextStmtParent = OldNextParent;
853 std::string IteratorName;
854 StringRef ContainerName;
856 ContainerName = TheContainer->getName();
858 size_t Len = ContainerName.size();
859 if (Len > 1 && ContainerName.endswith(Style ==
NS_UpperCase ?
"S" :
"s")) {
860 IteratorName = std::string(ContainerName.substr(0, Len - 1));
862 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())
866 if (Len > 2 && ContainerName.endswith(Style ==
NS_UpperCase ?
"S_" :
"s_")) {
867 IteratorName = std::string(ContainerName.substr(0, Len - 2));
869 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())
873 return std::string(OldIndex->getName());
882bool VariableNamer::declarationExists(StringRef Symbol) {
883 assert(Context !=
nullptr &&
"Expected an ASTContext");
884 IdentifierInfo &Ident = Context->Idents.get(Symbol);
887 if (!isAnyIdentifier(Ident.getTokenID()))
891 if (Ident.hasMacroDefinition())
895 for (
const Stmt *S = SourceStmt; S !=
nullptr; S = ReverseAST->lookup(S)) {
896 StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S);
897 if (I != GeneratedDecls->end() && I->second == Symbol)
908 DeclFinderASTVisitor DeclFinder(std::string(Symbol), GeneratedDecls);
909 return DeclFinder.findUsages(SourceStmt);
const FunctionDecl * Decl
const DeclRefExpr * DeclRef
A class to encapsulate lowering of the tool's confidence level.
void lowerTo(Confidence::Level Level)
Lower the internal confidence level to Level, but do not raise it.
ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar, const VarDecl *EndVar, const Expr *ContainerExpr, const Expr *ArrayBoundExpr, bool ContainerNeedsDereference)
bool findAndVerifyUsages(const Stmt *Body)
Finds all uses of IndexVar in Body, placing all usages in Usages, and returns true if IndexVar was on...
void addUsage(const Usage &U)
Adds the Usage if it was not added before.
void addComponents(const ComponentVector &Components)
Add a set of components that we should consider relevant to the container.
std::string createIndexName()
Generate a new index name.
static bool arrayMatchesBoundExpr(ASTContext *Context, const QualType &ArrayType, const Expr *ConditionExpr)
Determines whether the bound of a for loop condition expression is the same as the statically computa...
static bool containsExpr(ASTContext *Context, const ContainerT *Container, const Expr *E)
Returns true when the Container contains an Expr equivalent to E.
const DeclRefExpr * getDeclRef(const Expr *E)
Returns the DeclRefExpr represented by E, or NULL if there isn't one.
static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E)
Determines if an expression is a declaration reference to a particular variable.
bool areSameVariable(const ValueDecl *First, const ValueDecl *Second)
Returns true when two ValueDecls are the same variable.
static const Expr * getDereferenceOperand(const Expr *E)
If the expression is a dereference or call to operator*(), return the operand.
const Expr * digThroughConstructorsConversions(const Expr *E)
Look through conversion/copy constructors and member functions to find the explicit initialization ex...
static bool isAliasDecl(ASTContext *Context, const Decl *TheDecl, const VarDecl *IndexVar)
Determines whether the given Decl defines a variable initialized to the loop object.
static bool isIndexInSubscriptExpr(const Expr *IndexExpr, const VarDecl *IndexVar)
Returns true when the index expression is a declaration reference to IndexVar.
llvm::SmallVector< const clang::Expr *, 16 > ComponentVector
A vector used to store the AST subtrees of an Expr.
static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall, const VarDecl *IndexVar)
Returns true when Opcall is a call a one-parameter dereference of IndexVar.
bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second)
Returns true when two Exprs are equivalent.
static bool isDereferenceOfUop(const UnaryOperator *Uop, const VarDecl *IndexVar)
Returns true when Uop is a dereference of IndexVar.
The information needed to describe a valid convertible usage of an array index or iterator.