LoopConvertUtils.cpp | Explore in Territory

//===--- LoopConvertUtils.cpp - clang-tidy --------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "LoopConvertUtils.h"
#include "../utils/ASTUtils.h"
#include "clang/Basic/IdentifierTable.h"
#include "clang/Basic/LLVM.h"
#include "clang/Basic/Lambda.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Basic/TokenKinds.h"
#include "clang/Lex/Lexer.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <optional>
#include <string>
#include <utility>

usingnamespaceclang::ast_matchers;

namespace clang::tidy::modernize {

/// 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) { … }

/// 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 *Statement) { … }

/// record the DeclRefExpr as part of the parent expression.
bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) { … }

/// record the MemberExpr as part of the parent expression.
bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) { … }

/// Forward any DeclRefExprs to a check on the referenced variable
/// declaration.
bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) { … }

/// Determine if any this variable is declared inside the ContainingStmt.
bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *V) { … }

/// If we already created a variable for TheLoop, check to make sure
/// that the name was not already taken.
bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) { … }

/// If any named declaration within the AST subtree has the same name,
/// then consider Name already taken.
bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *D) { … }

/// Forward any declaration references to the actual check on the
/// referenced declaration.
bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) { … }

/// 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) { … }

/// Look through conversion/copy constructors and member functions 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());
///   vector<int>::const_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 *digThroughConstructorsConversions(const Expr *E) { … }

/// Returns true when two Exprs are equivalent.
bool areSameExpr(ASTContext *Context, const Expr *First, const Expr *Second) { … }

/// Returns the DeclRefExpr represented by E, or NULL if there isn't one.
const DeclRefExpr *getDeclRef(const Expr *E) { … }

/// Returns true when two ValueDecls are the same variable.
bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) { … }

/// Determines if an expression is a declaration reference to a
/// particular variable.
static bool exprReferencesVariable(const ValueDecl *Target, const Expr *E) { … }

/// If the expression is a dereference or call to operator*(), return the
/// operand. Otherwise, return NULL.
static const Expr *getDereferenceOperand(const Expr *E) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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(ASTContext *Context, const Decl *TheDecl,
                        const VarDecl *IndexVar) { … }

/// 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) { … }

ForLoopIndexUseVisitor::ForLoopIndexUseVisitor(ASTContext *Context,
                                               const VarDecl *IndexVar,
                                               const VarDecl *EndVar,
                                               const Expr *ContainerExpr,
                                               const Expr *ArrayBoundExpr,
                                               bool ContainerNeedsDereference)
    : … { … }

bool ForLoopIndexUseVisitor::findAndVerifyUsages(const Stmt *Body) { … }

void ForLoopIndexUseVisitor::addComponents(const ComponentVector &Components) { … }

void ForLoopIndexUseVisitor::addComponent(const Expr *E) { … }

void ForLoopIndexUseVisitor::addUsage(const Usage &U) { … }

/// 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::TraverseUnaryOperator(UnaryOperator *Uop) { … }

/// 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) { … }

/// 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) { … }

/// If an overloaded operator call is a dereference of IndexVar or
/// a subscript of 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) { … }

/// If we encounter an array with IndexVar as the index of an
/// ArraySubscriptExpression, 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) { … }

/// If we encounter a reference to IndexVar in an unpruned branch of the
/// traversal, mark this loop as unconvertible.
///
/// This determines the set of 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)
///     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) { … }

/// If the loop index is captured by a lambda, replace this capture
/// by the range-for loop variable.
///
/// For example:
/// \code
///   for (int i = 0; i < N; ++i) {
///     auto f = [v, i](int k) {
///       printf("%d\n", v[i] + k);
///     };
///     f(v[i]);
///   }
/// \endcode
///
/// Will be replaced by:
/// \code
///   for (auto & elem : v) {
///     auto f = [v, elem](int k) {
///       printf("%d\n", elem + k);
///     };
///     f(elem);
///   }
/// \endcode
bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE,
                                                   const LambdaCapture *C,
                                                   Expr *Init) { … }

/// 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) { … }

bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) { … }

std::string VariableNamer::createIndexName() { … }

/// Determines whether or not 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) { … }

} // namespace clang::tidy::modernize
llvm/clang-tools-extra/clang-tidy/modernize/LoopConvertUtils.cpp
