blob: bee77d9840f5d0d046bdcbef6e19a981349d08ee [file] [log] [blame]
//===--- LoopConvertUtils.h - clang-tidy ------------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOP_CONVERT_UTILS_H
#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOP_CONVERT_UTILS_H
#include "clang/AST/ASTContext.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/Basic/SourceLocation.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include <algorithm>
#include <memory>
#include <string>
#include <utility>
namespace clang {
namespace tidy {
namespace modernize {
enum LoopFixerKind { LFK_Array, LFK_Iterator, LFK_PseudoArray };
/// A map used to walk the AST in reverse: maps child Stmt to parent Stmt.
typedef llvm::DenseMap<const clang::Stmt *, const clang::Stmt *> StmtParentMap;
/// A map used to walk the AST in reverse:
/// maps VarDecl to the to parent DeclStmt.
typedef llvm::DenseMap<const clang::VarDecl *, const clang::DeclStmt *>
DeclParentMap;
/// A map used to track which variables have been removed by a refactoring pass.
/// It maps the parent ForStmt to the removed index variable's VarDecl.
typedef llvm::DenseMap<const clang::ForStmt *, const clang::VarDecl *>
ReplacedVarsMap;
/// A map used to remember the variable names generated in a Stmt
typedef llvm::DenseMap<const clang::Stmt *, std::string>
StmtGeneratedVarNameMap;
/// A vector used to store the AST subtrees of an Expr.
typedef llvm::SmallVector<const clang::Expr *, 16> ComponentVector;
/// \brief Class used build the reverse AST properties needed to detect
/// name conflicts and free variables.
class StmtAncestorASTVisitor
: public clang::RecursiveASTVisitor<StmtAncestorASTVisitor> {
public:
StmtAncestorASTVisitor() { StmtStack.push_back(nullptr); }
/// \brief Run the analysis on the TranslationUnitDecl.
///
/// In case we're running this analysis multiple times, don't repeat the work.
void gatherAncestors(const clang::TranslationUnitDecl *T) {
if (StmtAncestors.empty())
TraverseDecl(const_cast<clang::TranslationUnitDecl *>(T));
}
/// Accessor for StmtAncestors.
const StmtParentMap &getStmtToParentStmtMap() { return StmtAncestors; }
/// Accessor for DeclParents.
const DeclParentMap &getDeclToParentStmtMap() { return DeclParents; }
friend class clang::RecursiveASTVisitor<StmtAncestorASTVisitor>;
private:
StmtParentMap StmtAncestors;
DeclParentMap DeclParents;
llvm::SmallVector<const clang::Stmt *, 16> StmtStack;
bool TraverseStmt(clang::Stmt *Statement);
bool VisitDeclStmt(clang::DeclStmt *Statement);
};
/// Class used to find the variables and member expressions on which an
/// arbitrary expression depends.
class ComponentFinderASTVisitor
: public clang::RecursiveASTVisitor<ComponentFinderASTVisitor> {
public:
ComponentFinderASTVisitor() = default;
/// Find the components of an expression and place them in a ComponentVector.
void findExprComponents(const clang::Expr *SourceExpr) {
TraverseStmt(const_cast<clang::Expr *>(SourceExpr));
}
/// Accessor for Components.
const ComponentVector &getComponents() { return Components; }
friend class clang::RecursiveASTVisitor<ComponentFinderASTVisitor>;
private:
ComponentVector Components;
bool VisitDeclRefExpr(clang::DeclRefExpr *E);
bool VisitMemberExpr(clang::MemberExpr *Member);
};
/// Class used to determine if an expression is dependent on a variable declared
/// inside of the loop where it would be used.
class DependencyFinderASTVisitor
: public clang::RecursiveASTVisitor<DependencyFinderASTVisitor> {
public:
DependencyFinderASTVisitor(const StmtParentMap *StmtParents,
const DeclParentMap *DeclParents,
const ReplacedVarsMap *ReplacedVars,
const clang::Stmt *ContainingStmt)
: StmtParents(StmtParents), DeclParents(DeclParents),
ContainingStmt(ContainingStmt), ReplacedVars(ReplacedVars) {}
/// \brief Run the analysis on Body, and return true iff the expression
/// depends on some variable declared within ContainingStmt.
///
/// This is intended to protect against hoisting the container expression
/// outside of an inner context if part of that expression is declared in that
/// inner context.
///
/// For example,
/// \code
/// const int N = 10, M = 20;
/// int arr[N][M];
/// int getRow();
///
/// for (int i = 0; i < M; ++i) {
/// int k = getRow();
/// printf("%d:", arr[k][i]);
/// }
/// \endcode
/// At first glance, this loop looks like it could be changed to
/// \code
/// for (int elem : arr[k]) {
/// int k = getIndex();
/// printf("%d:", elem);
/// }
/// \endcode
/// But this is malformed, since `k` is used before it is defined!
///
/// In order to avoid this, this class looks at the container expression
/// `arr[k]` and decides whether or not it contains a sub-expression declared
/// within the the loop body.
bool dependsOnInsideVariable(const clang::Stmt *Body) {
DependsOnInsideVariable = false;
TraverseStmt(const_cast<clang::Stmt *>(Body));
return DependsOnInsideVariable;
}
friend class clang::RecursiveASTVisitor<DependencyFinderASTVisitor>;
private:
const StmtParentMap *StmtParents;
const DeclParentMap *DeclParents;
const clang::Stmt *ContainingStmt;
const ReplacedVarsMap *ReplacedVars;
bool DependsOnInsideVariable;
bool VisitVarDecl(clang::VarDecl *V);
bool VisitDeclRefExpr(clang::DeclRefExpr *D);
};
/// Class used to determine if any declarations used in a Stmt would conflict
/// with a particular identifier. This search includes the names that don't
/// actually appear in the AST (i.e. created by a refactoring tool) by including
/// a map from Stmts to generated names associated with those stmts.
class DeclFinderASTVisitor
: public clang::RecursiveASTVisitor<DeclFinderASTVisitor> {
public:
DeclFinderASTVisitor(const std::string &Name,
const StmtGeneratedVarNameMap *GeneratedDecls)
: Name(Name), GeneratedDecls(GeneratedDecls), Found(false) {}
/// Attempts to find any usages of variables name Name in Body, returning
/// true when it is used in Body. This includes the generated loop variables
/// of ForStmts which have already been transformed.
bool findUsages(const clang::Stmt *Body) {
Found = false;
TraverseStmt(const_cast<clang::Stmt *>(Body));
return Found;
}
friend class clang::RecursiveASTVisitor<DeclFinderASTVisitor>;
private:
std::string Name;
/// GeneratedDecls keeps track of ForStmts which have been transformed,
/// mapping each modified ForStmt to the variable generated in the loop.
const StmtGeneratedVarNameMap *GeneratedDecls;
bool Found;
bool VisitForStmt(clang::ForStmt *F);
bool VisitNamedDecl(clang::NamedDecl *D);
bool VisitDeclRefExpr(clang::DeclRefExpr *D);
bool VisitTypeLoc(clang::TypeLoc TL);
};
/// \brief The information needed to describe a valid convertible usage
/// of an array index or iterator.
struct Usage {
enum UsageKind {
// Regular usages of the loop index (the ones not specified below). Some
// examples:
// \code
// int X = 8 * Arr[i];
// ^~~~~~
// f(param1, param2, *It);
// ^~~
// if (Vec[i].SomeBool) {}
// ^~~~~~
// \endcode
UK_Default,
// Indicates whether this is an access to a member through the arrow
// operator on pointers or iterators.
UK_MemberThroughArrow,
// If the variable is being captured by a lambda, indicates whether the
// capture was done by value or by reference.
UK_CaptureByCopy,
UK_CaptureByRef
};
// The expression that is going to be converted. Null in case of lambda
// captures.
const Expr *Expression;
UsageKind Kind;
// Range that covers this usage.
SourceRange Range;
explicit Usage(const Expr *E)
: Expression(E), Kind(UK_Default), Range(Expression->getSourceRange()) {}
Usage(const Expr *E, UsageKind Kind, SourceRange Range)
: Expression(E), Kind(Kind), Range(std::move(Range)) {}
};
/// \brief A class to encapsulate lowering of the tool's confidence level.
class Confidence {
public:
enum Level {
// Transformations that are likely to change semantics.
CL_Risky,
// Transformations that might change semantics.
CL_Reasonable,
// Transformations that will not change semantics.
CL_Safe
};
/// \brief Initialize confidence level.
explicit Confidence(Confidence::Level Level) : CurrentLevel(Level) {}
/// \brief Lower the internal confidence level to Level, but do not raise it.
void lowerTo(Confidence::Level Level) {
CurrentLevel = std::min(Level, CurrentLevel);
}
/// \brief Return the internal confidence level.
Level getLevel() const { return CurrentLevel; }
private:
Level CurrentLevel;
};
// The main computational result of ForLoopIndexVisitor.
typedef llvm::SmallVector<Usage, 8> UsageResult;
// General functions used by ForLoopIndexUseVisitor and LoopConvertCheck.
const Expr *digThroughConstructors(const Expr *E);
bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second);
const DeclRefExpr *getDeclRef(const Expr *E);
bool areSameVariable(const ValueDecl *First, const ValueDecl *Second);
/// \brief Discover usages of expressions consisting of index or iterator
/// access.
///
/// Given an index variable, recursively crawls a for loop to discover if the
/// index variable is used in a way consistent with range-based for loop access.
class ForLoopIndexUseVisitor
: public RecursiveASTVisitor<ForLoopIndexUseVisitor> {
public:
ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar,
const VarDecl *EndVar, const Expr *ContainerExpr,
const Expr *ArrayBoundExpr,
bool ContainerNeedsDereference);
/// \brief Finds all uses of IndexVar in Body, placing all usages in Usages,
/// and returns true if IndexVar was only used in a way consistent with a
/// range-based for loop.
///
/// The general strategy is to reject any DeclRefExprs referencing IndexVar,
/// with the exception of certain acceptable patterns.
/// For arrays, the DeclRefExpr for IndexVar must appear as the index of an
/// ArraySubscriptExpression. Iterator-based loops may dereference
/// IndexVar or call methods through operator-> (builtin or overloaded).
/// Array-like containers may use IndexVar as a parameter to the at() member
/// function and in overloaded operator[].
bool findAndVerifyUsages(const Stmt *Body);
/// \brief Add a set of components that we should consider relevant to the
/// container.
void addComponents(const ComponentVector &Components);
/// \brief Accessor for Usages.
const UsageResult &getUsages() const { return Usages; }
/// \brief Adds the Usage if it was not added before.
void addUsage(const Usage &U);
/// \brief Get the container indexed by IndexVar, if any.
const Expr *getContainerIndexed() const { return ContainerExpr; }
/// \brief Returns the statement declaring the variable created as an alias
/// for the loop element, if any.
const DeclStmt *getAliasDecl() const { return AliasDecl; }
/// \brief Accessor for ConfidenceLevel.
Confidence::Level getConfidenceLevel() const {
return ConfidenceLevel.getLevel();
}
/// \brief Indicates if the alias declaration was in a place where it cannot
/// simply be removed but rather replaced with a use of the alias variable.
/// For example, variables declared in the condition of an if, switch, or for
/// stmt.
bool aliasUseRequired() const { return ReplaceWithAliasUse; }
/// \brief Indicates if the alias declaration came from the init clause of a
/// nested for loop. SourceRanges provided by Clang for DeclStmts in this
/// case need to be adjusted.
bool aliasFromForInit() const { return AliasFromForInit; }
private:
/// Typedef used in CRTP functions.
typedef RecursiveASTVisitor<ForLoopIndexUseVisitor> VisitorBase;
friend class RecursiveASTVisitor<ForLoopIndexUseVisitor>;
/// Overriden methods for RecursiveASTVisitor's traversal.
bool TraverseArraySubscriptExpr(ArraySubscriptExpr *E);
bool TraverseCXXMemberCallExpr(CXXMemberCallExpr *MemberCall);
bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *OpCall);
bool TraverseLambdaCapture(LambdaExpr *LE, const LambdaCapture *C,
Expr *Init);
bool TraverseMemberExpr(MemberExpr *Member);
bool TraverseUnaryDeref(UnaryOperator *Uop);
bool VisitDeclRefExpr(DeclRefExpr *E);
bool VisitDeclStmt(DeclStmt *S);
bool TraverseStmt(Stmt *S);
/// \brief Add an expression to the list of expressions on which the container
/// expression depends.
void addComponent(const Expr *E);
// Input member variables:
ASTContext *Context;
/// The index variable's VarDecl.
const VarDecl *IndexVar;
/// The loop's 'end' variable, which cannot be mentioned at all.
const VarDecl *EndVar;
/// The Expr which refers to the container.
const Expr *ContainerExpr;
/// The Expr which refers to the terminating condition for array-based loops.
const Expr *ArrayBoundExpr;
bool ContainerNeedsDereference;
// Output member variables:
/// A container which holds all usages of IndexVar as the index of
/// ArraySubscriptExpressions.
UsageResult Usages;
llvm::SmallSet<SourceLocation, 8> UsageLocations;
bool OnlyUsedAsIndex;
/// The DeclStmt for an alias to the container element.
const DeclStmt *AliasDecl;
Confidence ConfidenceLevel;
/// \brief A list of expressions on which ContainerExpr depends.
///
/// If any of these expressions are encountered outside of an acceptable usage
/// of the loop element, lower our confidence level.
llvm::SmallVector<std::pair<const Expr *, llvm::FoldingSetNodeID>, 16>
DependentExprs;
/// The parent-in-waiting. Will become the real parent once we traverse down
/// one level in the AST.
const Stmt *NextStmtParent;
/// The actual parent of a node when Visit*() calls are made. Only the
/// parentage of DeclStmt's to possible iteration/selection statements is of
/// importance.
const Stmt *CurrStmtParent;
/// \see aliasUseRequired().
bool ReplaceWithAliasUse;
/// \see aliasFromForInit().
bool AliasFromForInit;
};
struct TUTrackingInfo {
/// \brief Reset and initialize per-TU tracking information.
///
/// Must be called before using container accessors.
TUTrackingInfo() : ParentFinder(new StmtAncestorASTVisitor) {}
StmtAncestorASTVisitor &getParentFinder() { return *ParentFinder; }
StmtGeneratedVarNameMap &getGeneratedDecls() { return GeneratedDecls; }
ReplacedVarsMap &getReplacedVars() { return ReplacedVars; }
private:
std::unique_ptr<StmtAncestorASTVisitor> ParentFinder;
StmtGeneratedVarNameMap GeneratedDecls;
ReplacedVarsMap ReplacedVars;
};
/// \brief Create names for generated variables within a particular statement.
///
/// VariableNamer uses a DeclContext as a reference point, checking for any
/// conflicting declarations higher up in the context or within SourceStmt.
/// It creates a variable name using hints from a source container and the old
/// index, if they exist.
class VariableNamer {
public:
// Supported naming styles.
enum NamingStyle {
NS_CamelBack,
NS_CamelCase,
NS_LowerCase,
NS_UpperCase,
};
VariableNamer(StmtGeneratedVarNameMap *GeneratedDecls,
const StmtParentMap *ReverseAST, const clang::Stmt *SourceStmt,
const clang::VarDecl *OldIndex,
const clang::ValueDecl *TheContainer,
const clang::ASTContext *Context, NamingStyle Style)
: GeneratedDecls(GeneratedDecls), ReverseAST(ReverseAST),
SourceStmt(SourceStmt), OldIndex(OldIndex), TheContainer(TheContainer),
Context(Context), Style(Style) {}
/// \brief Generate a new index name.
///
/// Generates the name to be used for an inserted iterator. It relies on
/// declarationExists() to determine that there are no naming conflicts, and
/// tries to use some hints from the container name and the old index name.
std::string createIndexName();
private:
StmtGeneratedVarNameMap *GeneratedDecls;
const StmtParentMap *ReverseAST;
const clang::Stmt *SourceStmt;
const clang::VarDecl *OldIndex;
const clang::ValueDecl *TheContainer;
const clang::ASTContext *Context;
const NamingStyle Style;
// Determine whether or not a declaration that would conflict with Symbol
// exists in an outer context or in any statement contained in SourceStmt.
bool declarationExists(llvm::StringRef Symbol);
};
} // namespace modernize
} // namespace tidy
} // namespace clang
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_LOOP_CONVERT_UTILS_H