[clang-tidy] Add support for determining constness of more expressions. (#82617)

This uses a more systematic approach for determining whcich
`DeclRefExpr`s mutate the underlying object: Instead of using a few
matchers, we walk up the AST until we find a parent that we can prove
cannot change the underlying object.

This allows us to handle most address taking and dereference, bindings
to value and const& variables, and track constness of pointee (see
changes in DeclRefExprUtilsTest.cpp).

This allows supporting more patterns in
`performance-unnecessary-copy-initialization`.

Those two patterns are relatively common:

```
const auto e = (*vector_ptr)[i]
```

and

```
const auto e = vector_ptr->at(i);
```

In our codebase, we have around 25% additional findings from
`performance-unnecessary-copy-initialization` with this change. I did
not see any additional false positives.

1 files changed, 163 insertions, 47 deletions

diff --git a/clang-tools-extra/clang-tidy/utils/DeclRefExprUtils.cpp b/clang-tools-extra/clang-tidy/utils/DeclRefExprUtils.cpp
index 2d73179..f0ffa51 100644
--- a/clang-tools-extra/clang-tidy/utils/DeclRefExprUtils.cpp
+++ b/clang-tools-extra/clang-tidy/utils/DeclRefExprUtils.cpp
@@ -10,7 +10,9 @@
 #include "Matchers.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include <cassert>
 
 namespace clang::tidy::utils::decl_ref_expr {
 
@@ -34,69 +36,183 @@ void extractNodesByIdTo(ArrayRef<BoundNodes> Matches, StringRef ID,
     Nodes.insert(Match.getNodeAs<Node>(ID));
 }
 
+// A matcher that matches DeclRefExprs that are used in ways such that the
+// underlying declaration is not modified.
+// If the declaration is of pointer type, `Indirections` specifies the level
+// of indirection of the object whose mutations we are tracking.
+//
+// For example, given:
+//   ```
+//   int i;
+//   int* p;
+//   p = &i;  // (A)
+//   *p = 3;  // (B)
+//   ```
+//
+//  `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(0))` matches
+//  (B), but `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(1))`
+//  matches (A).
+//
+AST_MATCHER_P(DeclRefExpr, doesNotMutateObject, int, Indirections) {
+  // We walk up the parents of the DeclRefExpr recursively until we end up on a
+  // parent that cannot modify the underlying object. There are a few kinds of
+  // expressions:
+  //  - Those that cannot be used to mutate the underlying object. We can stop
+  //    recursion there.
+  //  - Those that can be used to mutate the underlying object in analyzable
+  //    ways (such as taking the address or accessing a subobject). We have to
+  //    examine the parents.
+  //  - Those that we don't know how to analyze. In that case we stop there and
+  //    we assume that they can mutate the underlying expression.
+
+  struct StackEntry {
+    StackEntry(const Expr *E, int Indirections)
+        : E(E), Indirections(Indirections) {}
+    // The expression to analyze.
+    const Expr *E;
+    // The number of pointer indirections of the object being tracked (how
+    // many times an address was taken).
+    int Indirections;
+  };
+
+  llvm::SmallVector<StackEntry, 4> Stack;
+  Stack.emplace_back(&Node, Indirections);
+  ASTContext &Ctx = Finder->getASTContext();
+
+  while (!Stack.empty()) {
+    const StackEntry Entry = Stack.back();
+    Stack.pop_back();
+
+    // If the expression type is const-qualified at the appropriate indirection
+    // level then we can not mutate the object.
+    QualType Ty = Entry.E->getType().getCanonicalType();
+    for (int I = 0; I < Entry.Indirections; ++I) {
+      assert(Ty->isPointerType());
+      Ty = Ty->getPointeeType().getCanonicalType();
+    }
+    if (Ty.isConstQualified())
+      continue;
+
+    // Otherwise we have to look at the parents to see how the expression is
+    // used.
+    const DynTypedNodeList Parents = Ctx.getParents(*Entry.E);
+    // Note: most nodes have a single parents, but there exist nodes that have
+    // several parents, such as `InitListExpr` that have semantic and syntactic
+    // forms.
+    for (const auto &Parent : Parents) {
+      if (Parent.get<CompoundStmt>()) {
+        // Unused block-scope statement.
+        continue;
+      }
+      const Expr *const P = Parent.get<Expr>();
+      if (P == nullptr) {
+        // `Parent` is not an expr (e.g. a `VarDecl`).
+        // The case of binding to a `const&` or `const*` variable is handled by
+        // the fact that there is going to be a `NoOp` cast to const below the
+        // `VarDecl`, so we're not even going to get there.
+        // The case of copying into a value-typed variable is handled by the
+        // rvalue cast.
+        // This triggers only when binding to a mutable reference/ptr variable.
+        // FIXME: When we take a mutable reference we could keep checking the
+        // new variable for const usage only.
+        return false;
+      }
+      // Cosmetic nodes.
+      if (isa<ParenExpr>(P) || isa<MaterializeTemporaryExpr>(P)) {
+        Stack.emplace_back(P, Entry.Indirections);
+        continue;
+      }
+      if (const auto *const Cast = dyn_cast<CastExpr>(P)) {
+        switch (Cast->getCastKind()) {
+        // NoOp casts are used to add `const`. We'll check whether adding that
+        // const prevents modification when we process the cast.
+        case CK_NoOp:
+        // These do nothing w.r.t. to mutability.
+        case CK_BaseToDerived:
+        case CK_DerivedToBase:
+        case CK_UncheckedDerivedToBase:
+        case CK_Dynamic:
+        case CK_BaseToDerivedMemberPointer:
+        case CK_DerivedToBaseMemberPointer:
+          Stack.emplace_back(Cast, Entry.Indirections);
+          continue;
+        case CK_ToVoid:
+        case CK_PointerToBoolean:
+          // These do not mutate the underlying variable.
+          continue;
+        case CK_LValueToRValue: {
+          // An rvalue is immutable.
+          if (Entry.Indirections == 0)
+            continue;
+          Stack.emplace_back(Cast, Entry.Indirections);
+          continue;
+        }
+        default:
+          // Bail out on casts that we cannot analyze.
+          return false;
+        }
+      }
+      if (const auto *const Member = dyn_cast<MemberExpr>(P)) {
+        if (const auto *const Method =
+                dyn_cast<CXXMethodDecl>(Member->getMemberDecl())) {
+          if (!Method->isConst()) {
+            // The method can mutate our variable.
+            return false;
+          }
+          continue;
+        }
+        Stack.emplace_back(Member, 0);
+        continue;
+      }
+      if (const auto *const Op = dyn_cast<UnaryOperator>(P)) {
+        switch (Op->getOpcode()) {
+        case UO_AddrOf:
+          Stack.emplace_back(Op, Entry.Indirections + 1);
+          continue;
+        case UO_Deref:
+          assert(Entry.Indirections > 0);
+          Stack.emplace_back(Op, Entry.Indirections - 1);
+          continue;
+        default:
+          // Bail out on unary operators that we cannot analyze.
+          return false;
+        }
+      }
+
+      // Assume any other expression can modify the underlying variable.
+      return false;
+    }
+  }
+
+  // No parent can modify the variable.
+  return true;
+}
+
 } // namespace
 
-// Finds all DeclRefExprs where a const method is called on VarDecl or VarDecl
-// is the a const reference or value argument to a CallExpr or CXXConstructExpr.
 SmallPtrSet<const DeclRefExpr *, 16>
 constReferenceDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt,
-                           ASTContext &Context) {
-  auto DeclRefToVar =
-      declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef");
-  auto MemberExprOfVar = memberExpr(hasObjectExpression(DeclRefToVar));
-  auto DeclRefToVarOrMemberExprOfVar =
-      stmt(anyOf(DeclRefToVar, MemberExprOfVar));
-  auto ConstMethodCallee = callee(cxxMethodDecl(isConst()));
-  // Match method call expressions where the variable is referenced as the this
-  // implicit object argument and operator call expression for member operators
-  // where the variable is the 0-th argument.
-  auto Matches = match(
-      findAll(expr(anyOf(
-          cxxMemberCallExpr(ConstMethodCallee,
-                            on(DeclRefToVarOrMemberExprOfVar)),
-          cxxOperatorCallExpr(ConstMethodCallee,
-                              hasArgument(0, DeclRefToVarOrMemberExprOfVar))))),
-      Stmt, Context);
+                           ASTContext &Context, int Indirections) {
+  auto Matches = match(findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl))),
+                                           doesNotMutateObject(Indirections))
+                                   .bind("declRef")),
+                       Stmt, Context);
   SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;
   extractNodesByIdTo(Matches, "declRef", DeclRefs);
-  auto ConstReferenceOrValue =
-      qualType(anyOf(matchers::isReferenceToConst(),
-                     unless(anyOf(referenceType(), pointerType(),
-                                  substTemplateTypeParmType()))));
-  auto ConstReferenceOrValueOrReplaced = qualType(anyOf(
-      ConstReferenceOrValue,
-      substTemplateTypeParmType(hasReplacementType(ConstReferenceOrValue))));
-  auto UsedAsConstRefOrValueArg = forEachArgumentWithParam(
-      DeclRefToVarOrMemberExprOfVar,
-      parmVarDecl(hasType(ConstReferenceOrValueOrReplaced)));
-  Matches = match(findAll(invocation(UsedAsConstRefOrValueArg)), Stmt, Context);
-  extractNodesByIdTo(Matches, "declRef", DeclRefs);
-  // References and pointers to const assignments.
-  Matches = match(
-      findAll(declStmt(has(varDecl(
-          hasType(qualType(matchers::isReferenceToConst())),
-          hasInitializer(ignoringImpCasts(DeclRefToVarOrMemberExprOfVar)))))),
-      Stmt, Context);
-  extractNodesByIdTo(Matches, "declRef", DeclRefs);
-  Matches = match(findAll(declStmt(has(varDecl(
-                      hasType(qualType(matchers::isPointerToConst())),
-                      hasInitializer(ignoringImpCasts(unaryOperator(
-                          hasOperatorName("&"),
-                          hasUnaryOperand(DeclRefToVarOrMemberExprOfVar)))))))),
-                  Stmt, Context);
-  extractNodesByIdTo(Matches, "declRef", DeclRefs);
+
   return DeclRefs;
 }
 
 bool isOnlyUsedAsConst(const VarDecl &Var, const Stmt &Stmt,
-                       ASTContext &Context) {
+                       ASTContext &Context, int Indirections) {
   // Collect all DeclRefExprs to the loop variable and all CallExprs and
   // CXXConstructExprs where the loop variable is used as argument to a const
   // reference parameter.
   // If the difference is empty it is safe for the loop variable to be a const
   // reference.
   auto AllDeclRefs = allDeclRefExprs(Var, Stmt, Context);
-  auto ConstReferenceDeclRefs = constReferenceDeclRefExprs(Var, Stmt, Context);
+  auto ConstReferenceDeclRefs =
+      constReferenceDeclRefExprs(Var, Stmt, Context, Indirections);
   return isSetDifferenceEmpty(AllDeclRefs, ConstReferenceDeclRefs);
 }