11#include "clang/Basic/IdentifierTable.h"
12#include "clang/Basic/LLVM.h"
13#include "clang/Basic/Lambda.h"
14#include "clang/Basic/SourceLocation.h"
15#include "clang/Basic/SourceManager.h"
16#include "clang/Basic/TokenKinds.h"
17#include "clang/Lex/Lexer.h"
18#include "llvm/ADT/APSInt.h"
19#include "llvm/ADT/FoldingSet.h"
20#include "llvm/ADT/StringRef.h"
37bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) {
38 StmtAncestors.insert(std::make_pair(Statement, StmtStack.back()));
39 StmtStack.push_back(Statement);
40 RecursiveASTVisitor<StmtAncestorASTVisitor>::TraverseStmt(Statement);
50bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Statement) {
51 for (
const auto *Decl : Statement->decls()) {
52 if (
const auto *V = dyn_cast<VarDecl>(Decl))
53 DeclParents.insert(std::make_pair(V, Statement));
59bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) {
60 Components.push_back(E);
65bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) {
66 Components.push_back(Member);
72bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
73 if (
auto *V = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
74 return VisitVarDecl(V);
79bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) {
80 const Stmt *Curr = DeclParents->lookup(V);
82 while (Curr !=
nullptr) {
83 if (Curr == ContainingStmt) {
84 DependsOnInsideVariable =
true;
87 Curr = StmtParents->lookup(Curr);
92 for (
const auto &I : *ReplacedVars) {
94 DependsOnInsideVariable =
true;
103bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) {
104 StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(TheLoop);
105 if (I != GeneratedDecls->end() && I->second == Name) {
114bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) {
115 const IdentifierInfo *Ident =
D->getIdentifier();
116 if (Ident && Ident->getName() == Name) {
125bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
126 if (
auto *D = dyn_cast<NamedDecl>(DeclRef->getDecl()))
127 return VisitNamedDecl(D);
133bool DeclFinderASTVisitor::VisitTypeLoc(TypeLoc TL) {
134 QualType QType = TL.getType();
137 if (QType.getAsString() == Name) {
144 if (
const IdentifierInfo *Ident = QType.getBaseTypeIdentifier()) {
145 if (Ident->getName() == Name) {
170 E = E->IgnoreImplicit();
171 if (
const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(E)) {
174 if (ConstructExpr->getNumArgs() != 1 ||
175 ConstructExpr->getConstructionKind() != CXXConstructionKind::Complete)
177 E = ConstructExpr->getArg(0);
178 if (
const auto *Temp = dyn_cast<MaterializeTemporaryExpr>(E))
179 E = Temp->getSubExpr();
184 if (
const auto *ME = dyn_cast<CXXMemberCallExpr>(E))
185 if (isa<CXXConversionDecl>(ME->getMethodDecl()))
191bool areSameExpr(ASTContext *Context,
const Expr *First,
const Expr *Second) {
197 return dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());
202 return First && Second &&
203 First->getCanonicalDecl() == Second->getCanonicalDecl();
218 if (
const auto *Uop = dyn_cast<UnaryOperator>(E))
219 return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() :
nullptr;
221 if (
const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(E)) {
222 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1
231template <
typename ContainerT>
232static bool containsExpr(ASTContext *Context,
const ContainerT *Container,
234 llvm::FoldingSetNodeID ID;
235 E->Profile(ID, *Context,
true);
236 for (
const auto &I : *Container) {
252 const VarDecl *IndexVar) {
253 const DeclRefExpr *Idx =
getDeclRef(IndexExpr);
254 return Idx && Idx->getType()->isIntegerType() &&
286 const VarDecl *IndexVar,
const Expr *Obj,
287 const Expr *SourceExpr,
bool PermitDeref) {
291 if (
areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
292 Obj->IgnoreParenImpCasts()))
296 if (PermitDeref &&
areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
297 InnerObj->IgnoreParenImpCasts()))
312 const VarDecl *IndexVar) {
313 return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&
325 const VarDecl *IndexVar) {
326 return Uop->getOpcode() == UO_Deref &&
348 const VarDecl *IndexVar) {
349 const auto *VDecl = dyn_cast<VarDecl>(TheDecl);
352 if (!VDecl->hasInit())
355 bool OnlyCasts =
true;
356 const Expr *Init = VDecl->getInit()->IgnoreParenImpCasts();
357 if (isa_and_nonnull<CXXConstructExpr>(Init)) {
367 QualType InitType = Init->getType();
368 QualType DeclarationType = VDecl->getType();
369 if (!DeclarationType.isNull() && DeclarationType->isReferenceType())
370 DeclarationType = DeclarationType.getNonReferenceType();
372 if (InitType.isNull() || DeclarationType.isNull() ||
373 !Context->hasSameUnqualifiedType(DeclarationType, InitType))
377 switch (Init->getStmtClass()) {
378 case Stmt::ArraySubscriptExprClass: {
379 const auto *E = cast<ArraySubscriptExpr>(Init);
385 case Stmt::UnaryOperatorClass:
388 case Stmt::CXXOperatorCallExprClass: {
389 const auto *OpCall = cast<CXXOperatorCallExpr>(Init);
390 if (OpCall->getOperator() == OO_Star)
392 if (OpCall->getOperator() == OO_Subscript) {
393 return OpCall->getNumArgs() == 2 &&
399 case Stmt::CXXMemberCallExprClass: {
400 const auto *MemCall = cast<CXXMemberCallExpr>(Init);
403 const auto *MDecl = MemCall->getMethodDecl();
404 if (MDecl && !isa<CXXConversionDecl>(MDecl) &&
405 MDecl->getNameAsString() ==
"at" && MemCall->getNumArgs() == 1) {
431 const QualType &ArrayType,
432 const Expr *ConditionExpr) {
433 if (!ConditionExpr || ConditionExpr->isValueDependent())
435 const ConstantArrayType *ConstType =
436 Context->getAsConstantArrayType(ArrayType);
439 std::optional<llvm::APSInt> ConditionSize =
440 ConditionExpr->getIntegerConstantExpr(*Context);
443 llvm::APSInt ArraySize(ConstType->getSize());
444 return llvm::APSInt::isSameValue(*ConditionSize, ArraySize);
448 const VarDecl *IndexVar,
449 const VarDecl *EndVar,
450 const Expr *ContainerExpr,
451 const Expr *ArrayBoundExpr,
452 bool ContainerNeedsDereference)
453 : Context(Context), IndexVar(IndexVar), EndVar(EndVar),
454 ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),
455 ContainerNeedsDereference(ContainerNeedsDereference),
459 addComponent(ContainerExpr);
463 TraverseStmt(
const_cast<Stmt *
>(Body));
464 return OnlyUsedAsIndex && ContainerExpr;
469 for (
const auto &I : Components)
473void ForLoopIndexUseVisitor::addComponent(
const Expr *E) {
474 llvm::FoldingSetNodeID ID;
475 const Expr *Node = E->IgnoreParenImpCasts();
476 Node->Profile(ID, *Context,
true);
477 DependentExprs.push_back(std::make_pair(Node, ID));
481 SourceLocation Begin = U.
Range.getBegin();
482 if (Begin.isMacroID())
483 Begin = Context->getSourceManager().getSpellingLoc(Begin);
485 if (UsageLocations.insert(Begin).second)
500bool ForLoopIndexUseVisitor::TraverseUnaryOperator(UnaryOperator *Uop) {
508 return VisitorBase::TraverseUnaryOperator(Uop);
536bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) {
537 const Expr *Base = Member->getBase();
539 const Expr *ResultExpr = Member;
541 if (
const auto *Call =
542 dyn_cast<CXXOperatorCallExpr>(Base->IgnoreParenImpCasts())) {
550 if (Call->getOperator() == OO_Arrow) {
551 assert(Call->getNumArgs() == 1 &&
552 "Operator-> takes more than one argument");
555 ExprType = Call->getCallReturnType(*Context);
561 if (!Member->isArrow()) {
562 OnlyUsedAsIndex =
false;
566 if (ExprType.isNull())
567 ExprType =
Obj->getType();
569 if (!ExprType->isPointerType())
574 SourceLocation ArrowLoc = Lexer::getLocForEndOfToken(
575 Base->getExprLoc(), 0, Context->getSourceManager(),
576 Context->getLangOpts());
579 if (ArrowLoc.isValid()) {
581 SourceRange(Base->getExprLoc(), ArrowLoc)));
585 return VisitorBase::TraverseMemberExpr(Member);
595bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
596 CXXMemberCallExpr *MemberCall) {
598 dyn_cast<MemberExpr>(MemberCall->getCallee()->IgnoreParenImpCasts());
600 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
605 const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
606 if (Ident && Ident->isStr(
"at") && MemberCall->getNumArgs() == 1) {
608 Member->getBase(), ContainerExpr,
609 ContainerNeedsDereference)) {
615 if (
containsExpr(Context, &DependentExprs, Member->getBase()))
618 return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);
640bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
641 CXXOperatorCallExpr *OpCall) {
642 switch (OpCall->getOperator()) {
651 if (OpCall->getNumArgs() != 2)
654 OpCall->getArg(0), ContainerExpr,
655 ContainerNeedsDereference)) {
664 return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
686bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(ArraySubscriptExpr *E) {
687 Expr *Arr = E->getBase();
689 return VisitorBase::TraverseArraySubscriptExpr(E);
691 if ((ContainerExpr && !
areSameExpr(Context, Arr->IgnoreParenImpCasts(),
692 ContainerExpr->IgnoreParenImpCasts())) ||
697 OnlyUsedAsIndex =
false;
698 return VisitorBase::TraverseArraySubscriptExpr(E);
740bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *E) {
741 const ValueDecl *TheDecl = E->getDecl();
745 OnlyUsedAsIndex =
false;
773bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE,
774 const LambdaCapture *C,
776 if (
C->capturesVariable()) {
777 ValueDecl *VDecl =
C->getCapturedVar();
787 if (VDecl->isInitCapture())
788 TraverseStmtImpl(cast<VarDecl>(VDecl)->getInit());
790 return VisitorBase::TraverseLambdaCapture(LE, C, Init);
797bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *S) {
798 if (!AliasDecl && S->isSingleDecl() &&
799 isAliasDecl(Context, S->getSingleDecl(), IndexVar)) {
801 if (CurrStmtParent) {
802 if (isa<IfStmt>(CurrStmtParent) || isa<WhileStmt>(CurrStmtParent) ||
803 isa<SwitchStmt>(CurrStmtParent))
804 ReplaceWithAliasUse =
true;
805 else if (isa<ForStmt>(CurrStmtParent)) {
806 if (cast<ForStmt>(CurrStmtParent)->getConditionVariableDeclStmt() == S)
807 ReplaceWithAliasUse =
true;
810 AliasFromForInit =
true;
818bool ForLoopIndexUseVisitor::TraverseStmtImpl(Stmt *S) {
821 const Stmt *OldNextParent = NextStmtParent;
822 CurrStmtParent = NextStmtParent;
824 bool Result = VisitorBase::TraverseStmt(S);
825 NextStmtParent = OldNextParent;
829bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) {
834 if (
const auto *LE = dyn_cast_or_null<LambdaExpr>(NextStmtParent)) {
837 if (S != LE->getBody()) {
841 return TraverseStmtImpl(S);
848 std::string IteratorName;
849 StringRef ContainerName;
851 ContainerName = TheContainer->getName();
853 size_t Len = ContainerName.size();
854 if (Len > 1 && ContainerName.ends_with(Style ==
NS_UpperCase ?
"S" :
"s")) {
855 IteratorName = std::string(ContainerName.substr(0, Len - 1));
857 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())
861 if (Len > 2 && ContainerName.ends_with(Style ==
NS_UpperCase ?
"S_" :
"s_")) {
862 IteratorName = std::string(ContainerName.substr(0, Len - 2));
864 if (!declarationExists(IteratorName) || IteratorName == OldIndex->getName())
868 return std::string(OldIndex->getName());
877bool VariableNamer::declarationExists(StringRef Symbol) {
878 assert(Context !=
nullptr &&
"Expected an ASTContext");
879 IdentifierInfo &Ident = Context->Idents.get(Symbol);
882 if (!isAnyIdentifier(Ident.getTokenID()))
886 if (Ident.hasMacroDefinition())
890 for (
const Stmt *S = SourceStmt; S !=
nullptr; S = ReverseAST->lookup(S)) {
891 StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S);
892 if (I != GeneratedDecls->end() && I->second == Symbol)
903 DeclFinderASTVisitor DeclFinder(std::string(Symbol), GeneratedDecls);
904 return DeclFinder.findUsages(SourceStmt);
A class to encapsulate lowering of the tool's confidence level.
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.
llvm::SmallVector< const clang::Expr *, 16 > ComponentVector
A vector used to store the AST subtrees of an Expr.
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.
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.
bool areStatementsIdentical(const Stmt *FirstStmt, const Stmt *SecondStmt, const ASTContext &Context, bool Canonical)
The information needed to describe a valid convertible usage of an array index or iterator.