[analyzer] Handle forwarding reference better in ExprMutationAnalyzer.

[shuaiwang]

Summary

We used to treat an Expr mutated whenever it's passed as non-const
reference argument to a function. This results in false positives in
cases like this:

int x;
std::vector<int> v;
v.emplace_back(x); // `x` is passed as non-const reference to `emplace_back`

In theory the false positives can be suppressed with
v.emplace_back(std::as_const(x)) but that's considered overly verbose,
inconsistent with existing code and spammy as diags.

This diff is first step in handling such cases by following into the function definition
and see whether the argument is mutated inside.

[lebedev.ri]

Thanks for working on this! I tried, and it appears to not fix the issue at hand.

struct C1 {
  C1(const C1* c, int num);
};

int x = 0;
auto y = std::make_unique<C1>(nullptr, x); // <- still considered a mutation?

struct C3 {}; // some class

struct C2 {
  C2(const int* whatever, int n, C3 zz);
};

int x = 0;
std::vector<C2> v;
v.emplace_back(nullptr, x, {}); // <- still considered a mutation?

And so on. These are hand-reduced, so hopefully you can reproduce?

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

32

Thanks!
I know this has performance implications, but those will exist even if one has this in his own code.

[JonasToth]

The new functionality looks very good. It can be used in a readability check that suggests const for parameters.

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

32

The analysis itself should not be executed twice, as it is cached. Only the way to figuring out that its cached will be run. I think its acceptable.

60

Why do we need a separate class for this?
I think you can just create another object of ExprMutAnalyzer and do the analysis with findDeclMutation(FunctioParm).

The Stmt is the functionDecl().getBody(). Right now it could be that you pass in an functionDecl without body.

Could there something happen with extern templates that the body is not accessible?

lib/Analysis/ExprMutationAnalyzer.cpp

201

I think this will not all cases correctly.

Say

template <typename T>
struct Foo {
  static void bar() { SomethingWith(T()); }
};

bar it self is not a template and NotInstantiated will be false (only 90% sure on that) as the declaration of bar does not match.
In another check I had to do this: unless(has(expr(anyOf(isTypeDependent(), isValueDependent())))) to ensure that there are no unresolved constructs in the stmt.

318

Same instantiation concerns

367

Just to be sure, this will recurse ?

struct Foo {
  std::string s;
  Foo(std::string s) : s (std::move(s)) {}
};

std::move will be resolved through the new mechanism right?

unittests/Analysis/ExprMutationAnalyzerTest.cpp

625

Please add a Results(declRefTo("y"), notMutated(y), same above

659

There are tests missing for the constructors. Please ensure that std::move and std::forward are handled properly.

[shuaiwang]

Just some quick comments, I'll take a deeper look into other comments later.

This diff along unfortunately won't be able to handle emplace_back just yet, the reason (I believe, haven't fully tested) is that std::forward is not handled properly and almost all std functions involving forwarding references at least std::forward'ed once.
I have some more changes locally that treats std::move and std::forward just as casts and that should be able to really push the analysis further down the forwarding chain instead of stopping at std::forward call.
Rephased diff description to be more clear. Sorry for the confusion.

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

60

It's mostly for the special handling of constructors in which case initializer list also could mutate param.

[JonasToth]

In D52008#1233667, @shuaiwang wrote:

Just some quick comments, I'll take a deeper look into other comments later.

This diff along unfortunately won't be able to handle emplace_back just yet, the reason (I believe, haven't fully tested) is that std::forward is not handled properly and almost all std functions involving forwarding references at least std::forward'ed once.
I have some more changes locally that treats std::move and std::forward just as casts and that should be able to really push the analysis further down the forwarding chain instead of stopping at std::forward call.
Rephased diff description to be more clear. Sorry for the confusion.

I did look up the rules for resolved the universal references.

void f() {
  int x;
  std::move(x);
}

Will create a normal reference to x. This would be the point were have to recursivly follow all references created from a value and check if they are mutated. Do you see another possibility on handling universal references correctly?

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

60

Hmm, still why not within ExprMutAnalyzer?
You could make it a class living within ExprMutAnalyzer in the private section. Then its clear its an implementation detail.

[lebedev.ri]

In D52008#1233667, @shuaiwang wrote:

Just some quick comments, I'll take a deeper look into other comments later.

This diff along unfortunately won't be able to handle emplace_back just yet

My apologies, for some reason i though it was supposed to.
Once again, thank you for working on this!

, the reason (I believe, haven't fully tested) is that std::forward is not handled properly and almost all std functions involving forwarding references at least std::forward'ed once.
I have some more changes locally that treats std::move and std::forward just as casts and that should be able to really push the analysis further down the forwarding chain instead of stopping at std::forward call.

Rephased diff description to be more clear. Sorry for the confusion.

No problem!

[shuaiwang]

More test cases addressing review comments

[shuaiwang]

In D52008#1232923, @lebedev.ri wrote:

Thanks for working on this! I tried, and it appears to not fix the issue at hand.

struct C1 {
  C1(const C1* c, int num);
};

int x = 0;
auto y = std::make_unique<C1>(nullptr, x); // <- still considered a mutation?

struct C3 {}; // some class

struct C2 {
  C2(const int* whatever, int n, C3 zz);
};

int x = 0;
std::vector<C2> v;
v.emplace_back(nullptr, x, {}); // <- still considered a mutation?

And so on. These are hand-reduced, so hopefully you can reproduce?

I've patched D51870 and tried these cases, they work correctly with this change plus the change making std::move & std::forward considered casts. I also tested

struct D {
  D(int&);
};
void h() {
  std::vector<D> v;
  for (int i = 0; i < 10; ++i) {
    v.emplace_back(i);
  }
}

and that's also correctly considered as mutation at emplace_back

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

60

Oh actually I'm planning to use this also in UnnecessaryValueParamCheck

lib/Analysis/ExprMutationAnalyzer.cpp

201

I think it's fine here since we only care about skipping those with forwarding references.

367

This diff along won't handle std::move "properly" yet.
We'll look into definition of std::move, it'll be something like

return static_cast<remove_reference<T>::type&&>(t);

and we'll simply conclude t is mutated: because it's being returned.

So for you case, we'll see s is mutated by std::move(s) and stop there, when we treat std::move as cast, we'll go one step further and found std::move(s) is passed as non-const argument to constructor of std::string, and we'll stop there concluding s is mutated.

[JonasToth]

The std::move as cast is a follow up patch?

From my side only the nits are left.

lib/Analysis/ExprMutationAnalyzer.cpp

333

Please spell out the type here

339

could T be a const pointer?

344

could RefType be a const pointer?

347

Please spell out the type here

381

Please spell out the type here

[george.karpenkov]

This looks very useful!

[shuaiwang]

Addressed review comments.

[shuaiwang]

In D52008#1234828, @JonasToth wrote:

The std::move as cast is a follow up patch?

Yes I'll send a follow up patch.

lib/Analysis/ExprMutationAnalyzer.cpp

381

This type is a bit cumbersome to spell out as it's an iterator. I feel it's fine to keep it auto.

[JonasToth]

LGTM

lib/Analysis/ExprMutationAnalyzer.cpp

381

Oh true, iterator can be autoed I would say ;)

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

 #include <type_traits>
 
 #include "clang/AST/AST.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "llvm/ADT/DenseMap.h"
 
 namespace clang {
 
+class FunctionParmMutationAnalyzer;
+
 /// Analyzes whether any mutative operations are applied to an expression within
 /// a given statement.
 class ExprMutationAnalyzer {
 public:
   ExprMutationAnalyzer(const Stmt &Stm, ASTContext &Context)
       : Stm(Stm), Context(Context) {}
 
   bool isMutated(const Decl *Dec) { return findDeclMutation(Dec) != nullptr; }
   bool isMutated(const Expr *Exp) { return findMutation(Exp) != nullptr; }
   const Stmt *findMutation(const Expr *Exp);
+  const Stmt *findDeclMutation(const Decl *Dec);
 
 private:
   bool isUnevaluated(const Expr *Exp);
 
   const Stmt *findExprMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
   const Stmt *findDeclMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
-  const Stmt *findDeclMutation(const Decl *Dec);
 
   const Stmt *findDirectMutation(const Expr *Exp);
   const Stmt *findMemberMutation(const Expr *Exp);
   const Stmt *findArrayElementMutation(const Expr *Exp);
   const Stmt *findCastMutation(const Expr *Exp);
   const Stmt *findRangeLoopMutation(const Expr *Exp);
   const Stmt *findReferenceMutation(const Expr *Exp);
+  const Stmt *findFunctionArgMutation(const Expr *Exp);
 
   const Stmt &Stm;
   ASTContext &Context;
+  llvm::DenseMap<const FunctionDecl *,
+                 std::unique_ptr<FunctionParmMutationAnalyzer>>
+      FuncParmAnalyzer;
   llvm::DenseMap<const Expr *, const Stmt *> Results;
 };
 
+// A convenient wrapper around ExprMutationAnalyzer for analyzing function
+// params.
+class FunctionParmMutationAnalyzer {
+public:
+  FunctionParmMutationAnalyzer(const FunctionDecl &Func, ASTContext &Context);
+
+  bool isMutated(const ParmVarDecl *Parm) {
+    return findMutation(Parm) != nullptr;
+  }
+  const Stmt *findMutation(const ParmVarDecl *Parm);
+
+private:
+  ExprMutationAnalyzer BodyAnalyzer;
+  llvm::DenseMap<const ParmVarDecl *, const Stmt *> Results;
+};
+
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_EXPRMUTATIONANALYZER_H

lib/Analysis/ExprMutationAnalyzer.cpp

const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) {
   if (isUnevaluated(Exp))
     return Results[Exp] = nullptr;
 
   for (const auto &Finder : {&ExprMutationAnalyzer::findDirectMutation,
                              &ExprMutationAnalyzer::findMemberMutation,
                              &ExprMutationAnalyzer::findArrayElementMutation,
                              &ExprMutationAnalyzer::findCastMutation,
                              &ExprMutationAnalyzer::findRangeLoopMutation,
-                             &ExprMutationAnalyzer::findReferenceMutation}) {
+                             &ExprMutationAnalyzer::findReferenceMutation,
+                             &ExprMutationAnalyzer::findFunctionArgMutation}) {
     if (const Stmt *S = (this->*Finder)(Exp))
       return Results[Exp] = S;
   }
 
   return Results[Exp] = nullptr;
 }
 
 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) {
const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
   const auto AsOperatorArrowThis =
       cxxOperatorCallExpr(hasOverloadedOperatorName("->"),
                           callee(cxxMethodDecl(ofClass(isMoveOnly()),
                                                returns(nonConstPointerType()))),
                           argumentCountIs(1), hasArgument(0, equalsNode(Exp)));
 
   // Used as non-const-ref argument when calling a function.
   // An argument is assumed to be non-const-ref when the function is unresolved.
+  // Instantiated template functions are not handled here but in
+  // findFunctionArgMutation which has additional smarts for handling forwarding
+  // references.
   const auto NonConstRefParam = forEachArgumentWithParam(
       equalsNode(Exp), parmVarDecl(hasType(nonConstReferenceType())));
+  const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
   const auto AsNonConstRefArg = anyOf(
-      callExpr(NonConstRefParam), cxxConstructExpr(NonConstRefParam),
+      callExpr(NonConstRefParam, NotInstantiated),
+      cxxConstructExpr(NonConstRefParam, NotInstantiated),
       callExpr(callee(expr(anyOf(unresolvedLookupExpr(), unresolvedMemberExpr(),
                                  cxxDependentScopeMemberExpr(),
                                  hasType(templateTypeParmType())))),
                hasAnyArgument(equalsNode(Exp))),
       cxxUnresolvedConstructExpr(hasAnyArgument(equalsNode(Exp))));
 
   // Captured by a lambda by reference.
   // If we're initializing a capture with 'Exp' directly then we're initializing
const auto Refs = match(
               // that separately.
               unless(hasParent(declStmt(hasParent(
                   cxxForRangeStmt(hasRangeStmt(equalsBoundNode("stmt"))))))))
               .bind("decl"))),
       Stm, Context);
   return findDeclMutation(Refs);
 }
 
+const Stmt *ExprMutationAnalyzer::findFunctionArgMutation(const Expr *Exp) {
+  const auto NonConstRefParam = forEachArgumentWithParam(
+      equalsNode(Exp),
+      parmVarDecl(hasType(nonConstReferenceType())).bind("parm"));
+  const auto IsInstantiated = hasDeclaration(isInstantiated());
+  const auto FuncDecl = hasDeclaration(functionDecl().bind("func"));
+  const auto Matches = match(
+      findAll(expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl),
+                         cxxConstructExpr(NonConstRefParam, IsInstantiated,
+                                          FuncDecl)))
+                  .bind("expr")),
+      Stm, Context);
+  for (const auto &Nodes : Matches) {
+    const auto *Exp = Nodes.getNodeAs<Expr>("expr");
+    const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
+    if (!Func->getBody())
+      return Exp;
+
+    const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
+    const auto AllParams =
+        Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
+    QualType ParmType =
+        AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
+                                   AllParams.size() - 1)]
+            ->getType();
+    if (auto *T = ParmType->getAs<PackExpansionType>())
+      ParmType = T->getPattern();
+
+    // If param type is forwarding reference, follow into the function
+    // definition and see whether the param is mutated inside.
+    if (auto *RefType = ParmType->getAs<RValueReferenceType>()) {
+      if (!RefType->getPointeeType().getQualifiers() &&
+          RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
+        auto &Analyzer = FuncParmAnalyzer[Func];
+        if (!Analyzer)
+          Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
+        if (Analyzer->findMutation(Parm))
+          return Exp;
+        continue;
+      }
+    }
+    // Not forwarding reference.
+    return Exp;
+  }
+  return nullptr;
+}
+
+FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
+    const FunctionDecl &Func, ASTContext &Context)
+    : BodyAnalyzer(*Func.getBody(), Context) {
+  if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
+    // CXXCtorInitializer might also mutate Param but they're not part of
+    // function body, check them eagerly here since they're typically trivial.
+    for (const CXXCtorInitializer *Init : Ctor->inits()) {
+      ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context);
+      for (const ParmVarDecl *Parm : Ctor->parameters()) {
+        if (Results.find(Parm) != Results.end())
+          continue;
+        if (const Stmt *S = InitAnalyzer.findDeclMutation(Parm))
+          Results[Parm] = S;
+      }
+    }
+  }
+}
+
+const Stmt *
+FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
+  const auto Memoized = Results.find(Parm);
+  if (Memoized != Results.end())
+    return Memoized->second;
+
+  if (const Stmt *S = BodyAnalyzer.findDeclMutation(Parm))
+    return Results[Parm] = S;
+
+  return Results[Parm] = nullptr;
+}
+
 } // namespace clang

unittests/Analysis/ExprMutationAnalyzerTest.cpp

 TEST(ExprMutationAnalyzerTest, FollowConditionalRefNotModified) {
   const auto AST = tooling::buildASTFromCode(
       "void f() { int x, y; bool b; int& r = b ? x : y; }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
+TEST(ExprMutationAnalyzerTest, FollowFuncArgModified) {
+  auto AST =
+      tooling::buildASTFromCode("template <class T> void g(T&& t) { t = 10; }"
+                                "void f() { int x; g(x); }");
+  auto Results =
+      match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("g(x)"));
+
+  AST = tooling::buildASTFromCode(
+      "void h(int&);"
+      "template <class... Args> void g(Args&&... args) { h(args...); }"
+      "void f() { int x; g(x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("g(x)"));
+
+  AST = tooling::buildASTFromCode(
+      "void h(int&, int);"
+      "template <class... Args> void g(Args&&... args) { h(args...); }"
+      "void f() { int x, y; g(x, y); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("g(x, y)"));
+
+  AST = tooling::buildASTFromCode(
+      "void h(int, int&);"
+      "template <class... Args> void g(Args&&... args) { h(args...); }"
+      "void f() { int x, y; g(y, x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("g(y, x)"));
+}
+
+TEST(ExprMutationAnalyzerTest, FollowFuncArgNotModified) {
+  auto AST = tooling::buildASTFromCode("template <class T> void g(T&&) {}"
+                                       "void f() { int x; g(x); }");
+  auto Results =
+      match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = tooling::buildASTFromCode("template <class T> void g(T&& t) { t; }"
+                                  "void f() { int x; g(x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST =
+      tooling::buildASTFromCode("template <class... Args> void g(Args&&...) {}"
+                                "void f() { int x; g(x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST =
+      tooling::buildASTFromCode("template <class... Args> void g(Args&&...) {}"
+                                "void f() { int y, x; g(y, x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = tooling::buildASTFromCode(
+      "void h(int, int&);"
+      "template <class... Args> void g(Args&&... args) { h(args...); }"
+      "void f() { int x, y; g(x, y); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+}
+
 TEST(ExprMutationAnalyzerTest, ArrayElementModified) {
   const auto AST =
       tooling::buildASTFromCode("void f() { int x[2]; x[0] = 10; }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x[0] = 10"));
 }