470 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOPCONVERTUTILS_H10#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOPCONVERTUTILS_H11 12#include "clang/AST/ASTContext.h"13#include "clang/AST/RecursiveASTVisitor.h"14#include "clang/ASTMatchers/ASTMatchFinder.h"15#include "clang/Basic/SourceLocation.h"16#include "llvm/ADT/DenseMap.h"17#include "llvm/ADT/SmallSet.h"18#include "llvm/ADT/SmallVector.h"19#include "llvm/ADT/StringRef.h"20#include <algorithm>21#include <memory>22#include <string>23#include <utility>24 25namespace clang::tidy::modernize {26 27enum LoopFixerKind {28 LFK_Array,29 LFK_Iterator,30 LFK_ReverseIterator,31 LFK_PseudoArray32};33 34/// A map used to walk the AST in reverse: maps child Stmt to parent Stmt.35using StmtParentMap = llvm::DenseMap<const clang::Stmt *, const clang::Stmt *>;36 37/// A map used to walk the AST in reverse:38/// maps VarDecl to the to parent DeclStmt.39using DeclParentMap =40 llvm::DenseMap<const clang::VarDecl *, const clang::DeclStmt *>;41 42/// A map used to track which variables have been removed by a refactoring pass.43/// It maps the parent ForStmt to the removed index variable's VarDecl.44using ReplacedVarsMap =45 llvm::DenseMap<const clang::ForStmt *, const clang::VarDecl *>;46 47/// A map used to remember the variable names generated in a Stmt48using StmtGeneratedVarNameMap =49 llvm::DenseMap<const clang::Stmt *, std::string>;50 51/// A vector used to store the AST subtrees of an Expr.52using ComponentVector = llvm::SmallVector<const clang::Expr *, 16>;53 54/// Class used build the reverse AST properties needed to detect55/// name conflicts and free variables.56class StmtAncestorASTVisitor57 : public clang::RecursiveASTVisitor<StmtAncestorASTVisitor> {58public:59 StmtAncestorASTVisitor() { StmtStack.push_back(nullptr); }60 61 /// Run the analysis on the AST.62 ///63 /// In case we're running this analysis multiple times, don't repeat the work.64 void gatherAncestors(ASTContext &Ctx) {65 if (StmtAncestors.empty())66 TraverseAST(Ctx);67 }68 69 /// Accessor for StmtAncestors.70 const StmtParentMap &getStmtToParentStmtMap() { return StmtAncestors; }71 72 /// Accessor for DeclParents.73 const DeclParentMap &getDeclToParentStmtMap() { return DeclParents; }74 75 friend class clang::RecursiveASTVisitor<StmtAncestorASTVisitor>;76 77private:78 StmtParentMap StmtAncestors;79 DeclParentMap DeclParents;80 llvm::SmallVector<const clang::Stmt *, 16> StmtStack;81 82 bool TraverseStmt(clang::Stmt *Statement);83 bool VisitDeclStmt(clang::DeclStmt *Statement);84};85 86/// Class used to find the variables and member expressions on which an87/// arbitrary expression depends.88class ComponentFinderASTVisitor89 : public clang::RecursiveASTVisitor<ComponentFinderASTVisitor> {90public:91 ComponentFinderASTVisitor() = default;92 93 /// Find the components of an expression and place them in a ComponentVector.94 void findExprComponents(const clang::Expr *SourceExpr) {95 TraverseStmt(const_cast<clang::Expr *>(SourceExpr));96 }97 98 /// Accessor for Components.99 const ComponentVector &getComponents() { return Components; }100 101 friend class clang::RecursiveASTVisitor<ComponentFinderASTVisitor>;102 103private:104 ComponentVector Components;105 106 bool VisitDeclRefExpr(clang::DeclRefExpr *E);107 bool VisitMemberExpr(clang::MemberExpr *Member);108};109 110/// Class used to determine if an expression is dependent on a variable declared111/// inside of the loop where it would be used.112class DependencyFinderASTVisitor113 : public clang::RecursiveASTVisitor<DependencyFinderASTVisitor> {114public:115 DependencyFinderASTVisitor(const StmtParentMap *StmtParents,116 const DeclParentMap *DeclParents,117 const ReplacedVarsMap *ReplacedVars,118 const clang::Stmt *ContainingStmt)119 : StmtParents(StmtParents), DeclParents(DeclParents),120 ContainingStmt(ContainingStmt), ReplacedVars(ReplacedVars) {}121 122 /// Run the analysis on Body, and return true iff the expression123 /// depends on some variable declared within ContainingStmt.124 ///125 /// This is intended to protect against hoisting the container expression126 /// outside of an inner context if part of that expression is declared in that127 /// inner context.128 ///129 /// For example,130 /// \code131 /// const int N = 10, M = 20;132 /// int arr[N][M];133 /// int getRow();134 ///135 /// for (int i = 0; i < M; ++i) {136 /// int k = getRow();137 /// printf("%d:", arr[k][i]);138 /// }139 /// \endcode140 /// At first glance, this loop looks like it could be changed to141 /// \code142 /// for (int elem : arr[k]) {143 /// int k = getIndex();144 /// printf("%d:", elem);145 /// }146 /// \endcode147 /// But this is malformed, since `k` is used before it is defined!148 ///149 /// In order to avoid this, this class looks at the container expression150 /// `arr[k]` and decides whether or not it contains a sub-expression declared151 /// within the loop body.152 bool dependsOnInsideVariable(const clang::Stmt *Body) {153 DependsOnInsideVariable = false;154 TraverseStmt(const_cast<clang::Stmt *>(Body));155 return DependsOnInsideVariable;156 }157 158 friend class clang::RecursiveASTVisitor<DependencyFinderASTVisitor>;159 160private:161 const StmtParentMap *StmtParents;162 const DeclParentMap *DeclParents;163 const clang::Stmt *ContainingStmt;164 const ReplacedVarsMap *ReplacedVars;165 bool DependsOnInsideVariable;166 167 bool VisitVarDecl(clang::VarDecl *V);168 bool VisitDeclRefExpr(clang::DeclRefExpr *D);169};170 171/// Class used to determine if any declarations used in a Stmt would conflict172/// with a particular identifier. This search includes the names that don't173/// actually appear in the AST (i.e. created by a refactoring tool) by including174/// a map from Stmts to generated names associated with those stmts.175class DeclFinderASTVisitor176 : public clang::RecursiveASTVisitor<DeclFinderASTVisitor> {177public:178 DeclFinderASTVisitor(const StringRef &Name,179 const StmtGeneratedVarNameMap *GeneratedDecls)180 : Name(Name), GeneratedDecls(GeneratedDecls) {}181 182 /// Attempts to find any usages of variables name Name in Body, returning183 /// true when it is used in Body. This includes the generated loop variables184 /// of ForStmts which have already been transformed.185 bool findUsages(const clang::Stmt *Body) {186 Found = false;187 TraverseStmt(const_cast<clang::Stmt *>(Body));188 return Found;189 }190 191 friend class clang::RecursiveASTVisitor<DeclFinderASTVisitor>;192 193private:194 std::string Name;195 /// GeneratedDecls keeps track of ForStmts which have been transformed,196 /// mapping each modified ForStmt to the variable generated in the loop.197 const StmtGeneratedVarNameMap *GeneratedDecls;198 bool Found = false;199 200 bool VisitForStmt(clang::ForStmt *);201 bool VisitNamedDecl(clang::NamedDecl *);202 bool VisitDeclRefExpr(clang::DeclRefExpr *);203 bool VisitTypeLoc(clang::TypeLoc);204};205 206/// The information needed to describe a valid convertible usage207/// of an array index or iterator.208struct Usage {209 enum UsageKind {210 // Regular usages of the loop index (the ones not specified below). Some211 // examples:212 // \code213 // int X = 8 * Arr[i];214 // ^~~~~~215 // f(param1, param2, *It);216 // ^~~217 // if (Vec[i].SomeBool) {}218 // ^~~~~~219 // \endcode220 UK_Default,221 // Indicates whether this is an access to a member through the arrow222 // operator on pointers or iterators.223 UK_MemberThroughArrow,224 // If the variable is being captured by a lambda, indicates whether the225 // capture was done by value or by reference.226 UK_CaptureByCopy,227 UK_CaptureByRef228 };229 // The expression that is going to be converted. Null in case of lambda230 // captures.231 const Expr *Expression;232 233 UsageKind Kind;234 235 // Range that covers this usage.236 SourceRange Range;237 238 explicit Usage(const Expr *E)239 : Expression(E), Kind(UK_Default), Range(Expression->getSourceRange()) {}240 Usage(const Expr *E, UsageKind Kind, SourceRange Range)241 : Expression(E), Kind(Kind), Range(std::move(Range)) {}242};243 244/// A class to encapsulate lowering of the tool's confidence level.245class Confidence {246public:247 enum Level {248 // Transformations that are likely to change semantics.249 CL_Risky,250 251 // Transformations that might change semantics.252 CL_Reasonable,253 254 // Transformations that will not change semantics.255 CL_Safe256 };257 /// Initialize confidence level.258 explicit Confidence(Confidence::Level Level) : CurrentLevel(Level) {}259 260 /// Lower the internal confidence level to Level, but do not raise it.261 void lowerTo(Confidence::Level Level) {262 CurrentLevel = std::min(Level, CurrentLevel);263 }264 265 /// Return the internal confidence level.266 Level getLevel() const { return CurrentLevel; }267 268private:269 Level CurrentLevel;270};271 272// The main computational result of ForLoopIndexVisitor.273using UsageResult = llvm::SmallVector<Usage, 8>;274 275// General functions used by ForLoopIndexUseVisitor and LoopConvertCheck.276const Expr *digThroughConstructorsConversions(const Expr *E);277bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second);278const DeclRefExpr *getDeclRef(const Expr *E);279bool areSameVariable(const ValueDecl *First, const ValueDecl *Second);280 281/// Discover usages of expressions consisting of index or iterator282/// access.283///284/// Given an index variable, recursively crawls a for loop to discover if the285/// index variable is used in a way consistent with range-based for loop access.286class ForLoopIndexUseVisitor287 : public RecursiveASTVisitor<ForLoopIndexUseVisitor> {288public:289 ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar,290 const VarDecl *EndVar, const Expr *ContainerExpr,291 const Expr *ArrayBoundExpr,292 bool ContainerNeedsDereference);293 294 /// Finds all uses of IndexVar in Body, placing all usages in Usages,295 /// and returns true if IndexVar was only used in a way consistent with a296 /// range-based for loop.297 ///298 /// The general strategy is to reject any DeclRefExprs referencing IndexVar,299 /// with the exception of certain acceptable patterns.300 /// For arrays, the DeclRefExpr for IndexVar must appear as the index of an301 /// ArraySubscriptExpression. Iterator-based loops may dereference302 /// IndexVar or call methods through operator-> (builtin or overloaded).303 /// Array-like containers may use IndexVar as a parameter to the at() member304 /// function and in overloaded operator[].305 bool findAndVerifyUsages(const Stmt *Body);306 307 /// Add a set of components that we should consider relevant to the308 /// container.309 void addComponents(const ComponentVector &Components);310 311 /// Accessor for Usages.312 const UsageResult &getUsages() const { return Usages; }313 314 /// Adds the Usage if it was not added before.315 void addUsage(const Usage &U);316 317 /// Get the container indexed by IndexVar, if any.318 const Expr *getContainerIndexed() const { return ContainerExpr; }319 320 /// Returns the statement declaring the variable created as an alias321 /// for the loop element, if any.322 const DeclStmt *getAliasDecl() const { return AliasDecl; }323 324 /// Accessor for ConfidenceLevel.325 Confidence::Level getConfidenceLevel() const {326 return ConfidenceLevel.getLevel();327 }328 329 /// Indicates if the alias declaration was in a place where it cannot330 /// simply be removed but rather replaced with a use of the alias variable.331 /// For example, variables declared in the condition of an if, switch, or for332 /// stmt.333 bool aliasUseRequired() const { return ReplaceWithAliasUse; }334 335 /// Indicates if the alias declaration came from the init clause of a336 /// nested for loop. SourceRanges provided by Clang for DeclStmts in this337 /// case need to be adjusted.338 bool aliasFromForInit() const { return AliasFromForInit; }339 340private:341 /// Typedef used in CRTP functions.342 using VisitorBase = RecursiveASTVisitor<ForLoopIndexUseVisitor>;343 friend class RecursiveASTVisitor<ForLoopIndexUseVisitor>;344 345 /// Overriden methods for RecursiveASTVisitor's traversal.346 bool TraverseArraySubscriptExpr(ArraySubscriptExpr *E);347 bool TraverseCXXMemberCallExpr(CXXMemberCallExpr *MemberCall);348 bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *OpCall);349 bool TraverseLambdaCapture(LambdaExpr *LE, const LambdaCapture *C,350 Expr *Init);351 bool TraverseMemberExpr(MemberExpr *Member);352 bool TraverseUnaryOperator(UnaryOperator *Uop);353 bool VisitDeclRefExpr(DeclRefExpr *E);354 bool VisitDeclStmt(DeclStmt *S);355 bool TraverseStmt(Stmt *S);356 357 bool traverseStmtImpl(Stmt *S);358 359 /// Add an expression to the list of expressions on which the container360 /// expression depends.361 void addComponent(const Expr *E);362 363 // Input member variables:364 ASTContext *Context;365 /// The index variable's VarDecl.366 const VarDecl *IndexVar;367 /// The loop's 'end' variable, which cannot be mentioned at all.368 const VarDecl *EndVar;369 /// The Expr which refers to the container.370 const Expr *ContainerExpr;371 /// The Expr which refers to the terminating condition for array-based loops.372 const Expr *ArrayBoundExpr;373 bool ContainerNeedsDereference;374 375 // Output member variables:376 /// A container which holds all usages of IndexVar as the index of377 /// ArraySubscriptExpressions.378 UsageResult Usages;379 llvm::SmallSet<SourceLocation, 8> UsageLocations;380 bool OnlyUsedAsIndex = true;381 /// The DeclStmt for an alias to the container element.382 const DeclStmt *AliasDecl = nullptr;383 Confidence ConfidenceLevel;384 /// A list of expressions on which ContainerExpr depends.385 ///386 /// If any of these expressions are encountered outside of an acceptable usage387 /// of the loop element, lower our confidence level.388 llvm::SmallVector<std::pair<const Expr *, llvm::FoldingSetNodeID>, 16>389 DependentExprs;390 391 /// The parent-in-waiting. Will become the real parent once we traverse down392 /// one level in the AST.393 const Stmt *NextStmtParent = nullptr;394 /// The actual parent of a node when Visit*() calls are made. Only the395 /// parentage of DeclStmt's to possible iteration/selection statements is of396 /// importance.397 const Stmt *CurrStmtParent = nullptr;398 399 /// \see aliasUseRequired().400 bool ReplaceWithAliasUse = false;401 /// \see aliasFromForInit().402 bool AliasFromForInit = false;403};404 405struct TUTrackingInfo {406 /// Reset and initialize per-TU tracking information.407 ///408 /// Must be called before using container accessors.409 TUTrackingInfo() : ParentFinder(new StmtAncestorASTVisitor) {}410 411 StmtAncestorASTVisitor &getParentFinder() { return *ParentFinder; }412 StmtGeneratedVarNameMap &getGeneratedDecls() { return GeneratedDecls; }413 ReplacedVarsMap &getReplacedVars() { return ReplacedVars; }414 415private:416 std::unique_ptr<StmtAncestorASTVisitor> ParentFinder;417 StmtGeneratedVarNameMap GeneratedDecls;418 ReplacedVarsMap ReplacedVars;419};420 421/// Create names for generated variables within a particular statement.422///423/// VariableNamer uses a DeclContext as a reference point, checking for any424/// conflicting declarations higher up in the context or within SourceStmt.425/// It creates a variable name using hints from a source container and the old426/// index, if they exist.427class VariableNamer {428public:429 // Supported naming styles.430 enum NamingStyle {431 NS_CamelBack,432 NS_CamelCase,433 NS_LowerCase,434 NS_UpperCase,435 };436 437 VariableNamer(StmtGeneratedVarNameMap *GeneratedDecls,438 const StmtParentMap *ReverseAST, const clang::Stmt *SourceStmt,439 const clang::VarDecl *OldIndex,440 const clang::ValueDecl *TheContainer,441 const clang::ASTContext *Context, NamingStyle Style)442 : GeneratedDecls(GeneratedDecls), ReverseAST(ReverseAST),443 SourceStmt(SourceStmt), OldIndex(OldIndex), TheContainer(TheContainer),444 Context(Context), Style(Style) {}445 446 /// Generate a new index name.447 ///448 /// Generates the name to be used for an inserted iterator. It relies on449 /// declarationExists() to determine that there are no naming conflicts, and450 /// tries to use some hints from the container name and the old index name.451 std::string createIndexName();452 453private:454 StmtGeneratedVarNameMap *GeneratedDecls;455 const StmtParentMap *ReverseAST;456 const clang::Stmt *SourceStmt;457 const clang::VarDecl *OldIndex;458 const clang::ValueDecl *TheContainer;459 const clang::ASTContext *Context;460 const NamingStyle Style;461 462 // Determine whether or not a declaration that would conflict with Symbol463 // exists in an outer context or in any statement contained in SourceStmt.464 bool declarationExists(llvm::StringRef Symbol);465};466 467} // namespace clang::tidy::modernize468 469#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOPCONVERTUTILS_H470