[analyzer] (1/n) Support pointee mutation analysis in ExprMutationAnalyzer.

[shuaiwang]

Summary

We handle pointee mutation for native pointers & pointer-like types
(loosely defined as having an operator* returning non-const reference)

This diff alone just implemented the cases where pointee of an Exp is
*directly* mutated (e.g. invoking non-const member function.)

The most trivial class of casts is handled as well for easier unit
testing, findPointeeCastMutation is not done yet.

Planned future work:

• findPointeeDerefMutation: Exp is first dereferenced, and then mutated.
• findPointee{Member,Array}Mutation: member (or array element) of pointee is accessed and then mutated.
• findPointeeArithmeticMutation: handling pointer arithmetic
• findPointeeAssignmentMutation: pointer is assigned to another var and then mutated.

[JonasToth]

Looks like a good start! I think getting the pointers right will be most difficult, because of the multiple levels of indirection they allow. Do you think it would be possible to the analysis for >const?< int ***-cases? (recursively checking through the pointer levels)

lib/Analysis/ExprMutationAnalyzer.cpp

225

Just to be sure that i understand:
the changes here are more performance optimizations then directly related to detect pointee mutations?

467

no else after return. this makes the short circuit logic clearer

469

values are not marked as const by the llvm code guideline

486

implicit conversion from pointer to bool? Please make that better visible and please dont use const on values.
Not sure for the matchers, I have seen both, but they should be treated as values as well i think.

490

Please make that sentence clearer, i could not understand it (only interpret :D)

508

shouldn't be the constness of the argument considered here?

515

Either remove the comment or make it a full sentence please. I think the variable naming is clear enough to elide

527

Please add a todo to ensure the missing casts are not forgotten

unittests/Analysis/ExprMutationAnalyzerTest.cpp

54

maybe even assert(E && S)?

76

That doesn't look like a super idea. It is super hidden that variable 'p*' will be analyzed for pointee mutation and others aren't. Especially in 12 months and when someone else wants to change something, this will be the source of headaches.

Don't you think there could be a better way of doing this switch?

169

I feel that there a multiple tests missing:

• multiple levels of pointers int ***, int * const *
• pointers to references int &*
• references to pointers int *&
• ensure that having a const pointer does no influence the pointee analysis int * const p = &i; *p = 42;
• a class with operator* + operator-> const/non-const and the analysis for pointers to that class
• pointer returned from a function
• non-const reference returned

int& foo(int *p) {
  return *p;
}

194

Could you please add the EXPECT_FALSE(isMutated()) && EXPECT_TRUE(isPointeeMutated()?
Maybe a short helper for that like isOnlyPointeeMutated() would be nice.

Here and the other cases as well

705

Please add a mutating example for array access through a pointer (as its very common in C-style code).

[shuaiwang]

Rebase

[shuaiwang]

[WIP] Addressed some of review comments.

[shuaiwang]

In D52219#1238423, @JonasToth wrote:

Do you think it would be possible to the analysis for >const?< int ***-cases? (recursively checking through the pointer levels)

I think that should be possible, will do after single-layer pointee analysis is done. I believe we can build multi-layer analysis based on much of the single-layer analysis.

lib/Analysis/ExprMutationAnalyzer.cpp

225

Yes :)

508

We need that for non-pointee version, but not for pointee version, for example:

void g1(int * const);

void f1() {
  int *x;
  g1(x); // <-- x is passed to `g1`, we consider that as a mutation, the argument type do have a top-level const
}

void g2(const int *);

void f2() {
  int *x;
  g2(x); // <-- declRefExp(to(x)) is NOT directly passed to `g2`, there's a layer a ImplicitCastExpr<NoOp> in between, and after the implicit cast, the type of the expression becomes "const int *" instead of just "int*", so it'll fail the `isPointeeMutable` check at the beginning of `findPointeeDirectMutation`
}

In summary, we rely on:

• Checking whether pointee is actually mutable at the beginning
• Carefully handling casts by not trivially ignoring them unless absolutely safe

[JonasToth]

lib/Analysis/ExprMutationAnalyzer.cpp

508

I see. That makes sense, thanks for clarification :)

[Szelethus]

lib/Analysis/ExprMutationAnalyzer.cpp

86

Didn't you mean these to be doxygen comments?

[shuaiwang]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

76

Yeah... agree :)
But how about let's keep it this way just for now, and I'll pause the work on supporting pointee analysis and fix it properly but in a separate diff following this one?

I've been thinking about this and also did some prototyping, and here are my thoughts:
In order to properly fix this we need to change the interface of ExprMutationAnalyzer to not simply return a Stmt but instead return a MutationTrace with additional metadata. This wasn't needed before because we can reconstruct a mutation chain by continuously calling findMutation, and that works well for cases like "int x; int& r0 = x; int& r1 = r0; r1 = 123;". But now that pointers come into play, and we need to handle cases like "int *p; int *p2 = p; int& r = *p2; r = 123;", and in order to reconstruct the mutation chain, we need to do findPointeeMutation(p) -> findPointeeMutation(p2) -> findMutation(r), notice that we need to switch from calling findPointeeMutation to calling findMutation. However we don't know where the switch should happen simply based on what's returned from findPointeeMutation, we need additional metadata for that.

That interface change will unavoidably affect how memoization is done so we need to change memoization as well.

Now since we need to change both the interface and memoization anyway, we might as well design them properly so that multiple-layers of pointers can be supported nicely. I think we can end up with something like this:

class ExprMutationAnalyzer {
public:
  struct MutationTrace {
    const Stmt *Value;
    const MutationTrace *Next;
    // Other metadata
  };

  // Finds whether any mutative operations are performed on the given expression after dereferencing `DerefLayers` times.
  const MutationTrace *findMutation(const Expr *, int DerefLayers = 0);
  const MutationTrace *findMutation(const Decl *, int DerefLayers = 0);
};

This involves quite some refactoring, and doing this refactoring before this diff and later rebasing seems quite some trouble that I'd like to avoid.

Let me know what do you think :)

[JonasToth]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

76

Is the second part of your answer part to adressing this testing issue?
Given the whole Analyzer is WIP it is ok to postpone the testing change to later for me. But I feel that this is a quality issue that more experience clang develops should comment on because it still lands in trunk. Are you aware of other patches then clang-tidy that rely on EMA?

Regarding you second part (its related to multi-layer pointer mutation?!):
Having a dependency-graph that follows the general data flow _with_ mutation annotations would be nice to have. There is probably even something in clang (e.g. CFG is probably similar in idea, just with all execution paths), but I don't know enough to properly judge here.

In my opinion it is ok, to not do the refactoring now and just support one layer of pointer indirection. Especially in C++ there is usually no need for multi-layer pointers but more a relict from C-style.
C on the other hand relies on that.
Designing EMA new for the more generalized functionality (if necessary) would be of course great, but again: Better analyzer ppl should be involved then me, even though I would still be very interested to help :)

169

for the multi-level pointer mutation: it would be enough to test, that the second layer is analyzed properly, and that the int * >const< * would be detected.

[shuaiwang]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

76

The second part is more of trying to explain why I'd prefer to keep the test this way just for this diff.
Basically we need a refactoring that makes EMA returns MutationTrace in order to fix this test util here.

But thinking more about this, maybe we don't need that (for now), this util is to help restore a mutation chain, and since we don't support a chain of mutation for pointers yet we can have a simpler version of pointeeMutatedBy that doesn't support chaining.

I mentioned multi-layer pointer mutation because _if_ we were to do a refactoring, we'd better just do it right and take possible features needed in the future into account. But the refactoring itself is motivated by the need of fixing this testing util (and making the return value from findMutation generally more useful.)

BTW by MutationTrace it's not as complicated or sophisticated as CFG, it's simply a trace helping understand why the mutation happens, for example in this case:

int x;
int &y = x;
int &z = y;
z = 123;

it's a bit disconnected if we just say z = 123 mutated declRefExpr(to(x)), instead:

• findMutation(x) returns y
• findMutation(y) returns z
• findMutation(z) returns z = 123

This doesn't apply to (majority) of cases where the mutative expression is an ancestor of the given expression, in those cases it's typically quite clear why the ancestor expression mutated its descendant.

Anyway, I'll remove this little hackery here and address other comments later (hopefully today), and I'll do a refactoring before pointer analysis supports chaining.

[JonasToth]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

76

Ok, understanding the decision making of the EMA would be a good thing to have in general as well.

[shuaiwang]

lib/Analysis/ExprMutationAnalyzer.cpp

86

I feel these don't need to be doxygen comments.

unittests/Analysis/ExprMutationAnalyzerTest.cpp

169

Added except for:

• Anything that requires following a dereference, we need findPointeeDerefMutation for that.
• Pointer to a class with operator* + operator->, I think those two operators doesn't matter, there's no way to accidentally invoke them from a pointer.

705

This also need findPointeeDerefMutation.

[shuaiwang]

Addresses review comments.

[JonasToth]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

169

But we want to analyze smart pointers in the future as well, not? It would be good to already prepare that in the testing department.
Or would the nature of operator* already make that happen magically?

[shuaiwang]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

169

Yes we'll handle smart pointers, and we'll handle that in findPointeeDerefMutation, basically it'll look like:

if (native pointer && derefed with *) findMutation(deref expr)
if (smart pointer && called operator*) findMutation(operator call expr)
if (smart pointer && called operator->) findPointeeMutation(operator call expr)

I think it would be more clear if we can match the implementation progress with unit test cases as that shows what kind of cases starts to be supported by the change.

[JonasToth]

TDD, thats ok ;)

Am 22.09.2018 um 19:37 schrieb Shuai Wang via Phabricator:

shuaiwang added inline comments.

Comment at: unittests/Analysis/ExprMutationAnalyzerTest.cpp:156

EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x.mf()"));

+

+ AST = tooling::buildASTFromCode(

JonasToth wrote:

shuaiwang wrote:

JonasToth wrote:

JonasToth wrote:

I feel that there a multiple tests missing:

• multiple levels of pointers int ***, int * const *
• pointers to references int &*
• references to pointers int *&
• ensure that having a const pointer does no influence the pointee analysis int * const p = &i; *p = 42;
• a class with operator* + operator-> const/non-const and the analysis for pointers to that class
• pointer returned from a function
• non-const reference returned

int& foo(int *p) {
  return *p;
}

for the multi-level pointer mutation: it would be enough to test, that the second layer is analyzed properly, and that the int * >const< * would be detected.

Added except for:

• Anything that requires following a dereference, we need findPointeeDerefMutation for that.
• Pointer to a class with operator* + operator->, I think those two operators doesn't matter, there's no way to accidentally invoke them from a pointer.

But we want to analyze smart pointers in the future as well, not? It would be good to already prepare that in the testing department.
Or would the nature of operator* already make that happen magically?

Yes we'll handle smart pointers, and we'll handle that in findPointeeDerefMutation, basically it'll look like:

if (native pointer && derefed with *) findMutation(deref expr)
if (smart pointer && called operator*) findMutation(operator call expr)
if (smart pointer && called operator->) findPointeeMutation(operator call expr)

I think it would be more clear if we can match the implementation progress with unit test cases as that shows what kind of cases starts to be supported by the change.

Repository:

rC Clang

https://reviews.llvm.org/D52219

[shuaiwang]

Added test case place holder for cases that should be supported in later patches.

[JonasToth]

unittests/Analysis/ExprMutationAnalyzerTest.cpp

61

Is there a reason why the pointer is marked const? Usually this is not done in the codebase and I feel consistency is key (similar to const for values).

90

You can put this line 2 lines below, 'initialize late'

169

Ok.

639

a nice test to add would be `const int* f() { int* x; return x; }.

[shuaiwang]

Addressed review comments.

[JonasToth]

LGTM, with a few nits and a question. Please wait a bit if @aaron.ballman or @george.karpenkov have any comments before committing.

lib/Analysis/ExprMutationAnalyzer.cpp

88

you can elide the braces here

101

Please make this a full sentence (adding ... the overloaded 'operator*' is returning ... is enough.)

226

This comment is one sentence, just replace const. Bail with const, bail

unittests/Analysis/ExprMutationAnalyzerTest.cpp

87

pointer is const, please remove the last const

645

I am confused. The const int* guarantees, that x-pointee is not mutated. Why shall this be diagnosed as a mutation?

[shuaiwang]

Resolved review comments.

[JonasToth]

I think you can commit, there was enough opportunity to respond and we pinged directly as well.

include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

private:
   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 *findPointeeDirectMutation(const Expr *Exp);
+  const Stmt *findPointeeCastMutation(const Expr *Exp);
+
   const Stmt &Stm;
   ASTContext &Context;
   llvm::DenseMap<const FunctionDecl *,
                  std::unique_ptr<FunctionParmMutationAnalyzer>>
       FuncParmAnalyzer;
   ResultMap Results;
   ResultMap PointeeResults;
 };

lib/Analysis/ExprMutationAnalyzer.cpp

const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
   const StringRef ID = NodeID<T>::value;
   for (const auto &Nodes : Matches) {
     if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
       return S;
   }
   return nullptr;
 }
 
+// Pointee of `Exp` can be *directly* mutated if the type of `Exp` is:
+// - Pointer to non-const
+// - Pointer-like type with `operator*` returning non-const reference
+bool isPointeeMutable(const Expr *Exp, const ASTContext &Context) {
+  if (const auto *PT = Exp->getType()->getAs<PointerType>())
+    return !PT->getPointeeType().isConstant(Context);
+  if (const auto *RT = Exp->getType()->getAs<RecordType>()) {
+    if (const CXXRecordDecl *RecordDecl = RT->getAsCXXRecordDecl()) {
+      bool ExpIsConst = Exp->getType().isConstant(Context);
+      return llvm::any_of(
+          RecordDecl->methods(),
+          [ExpIsConst, &Context](const CXXMethodDecl *MethodDecl) {
+            // Look for `operator*` with the same constness as `Exp`.
+            if (MethodDecl->getOverloadedOperator() != OO_Star ||
+                MethodDecl->isConst() != ExpIsConst)
+              return false;
+            // Check whether the `operator*` returns non-const reference.
+            if (const auto *RT =
+                    MethodDecl->getReturnType()->getAs<ReferenceType>())
+              return !RT->getPointeeType().isConstant(Context);
+            return false;
+          });
+    }
+  }
+  return false;
+}
+
 } // namespace
 
 const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) {
   return findMutationMemoized(Exp,
                               {&ExprMutationAnalyzer::findDirectMutation,
                                &ExprMutationAnalyzer::findMemberMutation,
                                &ExprMutationAnalyzer::findArrayElementMutation,
                                &ExprMutationAnalyzer::findCastMutation,
                                &ExprMutationAnalyzer::findRangeLoopMutation,
                                &ExprMutationAnalyzer::findReferenceMutation,
                                &ExprMutationAnalyzer::findFunctionArgMutation},
                               Results);
 }
 
 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
   return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
 }
 
 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
-  return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
+  return findMutationMemoized(Exp,
+                              {&ExprMutationAnalyzer::findPointeeDirectMutation,
+                               &ExprMutationAnalyzer::findPointeeCastMutation},
+                              PointeeResults);
 }
 
 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
   return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
 }
 
 const Stmt *ExprMutationAnalyzer::findMutationMemoized(
     const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,

 
 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
     ArrayRef<ast_matchers::BoundNodes> Matches) {
   return tryEachMatch<Decl>(Matches, this,
                             &ExprMutationAnalyzer::findPointeeMutation);
 }
 
 const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
+  // `Exp` can be *directly* mutated if the type of `Exp` is not const, bail out
+  // early otherwise.
+  if (Exp->getType().isConstant(Context))
+    return nullptr;
+  bool ExpIsPointer = Exp->getType()->getAs<PointerType>() != nullptr;
+
   // LHS of any assignment operators.
   const auto AsAssignmentLhs =
       binaryOperator(isAssignmentOperator(), hasLHS(equalsNode(Exp)));
 
   // Operand of increment/decrement operators.
   const auto AsIncDecOperand =
       unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
                     hasUnaryOperand(equalsNode(Exp)));
 
   // Invoking non-const member function.
   // A member function is assumed to be non-const when it is unresolved.
   const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
-  const auto AsNonConstThis =
-      expr(anyOf(cxxMemberCallExpr(callee(NonConstMethod), on(equalsNode(Exp))),
-                 cxxOperatorCallExpr(callee(NonConstMethod),
-                                     hasArgument(0, equalsNode(Exp))),
-                 callExpr(callee(expr(anyOf(
-                     unresolvedMemberExpr(hasObjectExpression(equalsNode(Exp))),
-                     cxxDependentScopeMemberExpr(
-                         hasObjectExpression(equalsNode(Exp)))))))));
+  const auto AsNonConstNonPointerThis =
+      ExpIsPointer
+          ? expr(unless(anything()))
+          : expr(anyOf(
+                cxxMemberCallExpr(callee(NonConstMethod), on(equalsNode(Exp))),
 
   // Taking address of 'Exp'.
   // We're assuming 'Exp' is mutated as soon as its address is taken, though in
   // theory we can follow the pointer and see whether it escaped `Stm` or is
   // dereferenced and then mutated. This is left for future improvements.
   const auto AsAmpersandOperand =
       unaryOperator(hasOperatorName("&"),
                     // A NoOp implicit cast is adding const.
                     unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
                     hasUnaryOperand(equalsNode(Exp)));
   const auto AsPointerFromArrayDecay =
       castExpr(hasCastKind(CK_ArrayToPointerDecay),
+               // A NoOp implicit cast is adding const.
+               unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
                unless(hasParent(arraySubscriptExpr())), has(equalsNode(Exp)));
   // Treat calling `operator->()` of move-only classes as taking address.
   // These are typically smart pointers with unique ownership so we treat
   // mutation of pointee as mutation of the smart pointer itself.
   const auto AsOperatorArrowThis =
-      cxxOperatorCallExpr(hasOverloadedOperatorName("->"),
-                          callee(cxxMethodDecl(ofClass(isMoveOnly()),
-                                               returns(nonConstPointerType()))),
-                          argumentCountIs(1), hasArgument(0, equalsNode(Exp)));
+      ExpIsPointer ? cxxOperatorCallExpr(unless(anything()))
+                   : cxxOperatorCallExpr(
+                         hasOverloadedOperatorName("->"),
 
   // 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 Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
   // Returned as non-const-ref.
   // If we're returning 'Exp' directly then it's returned as non-const-ref.
   // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
   // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
   // adding const.)
   const auto AsNonConstRefReturn = returnStmt(hasReturnValue(equalsNode(Exp)));
 
   const auto Matches =
-      match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
-                               AsAmpersandOperand, AsPointerFromArrayDecay,
-                               AsOperatorArrowThis, AsNonConstRefArg,
-                               AsLambdaRefCaptureInit, AsNonConstRefReturn))
+      match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand,
+                               AsNonConstNonPointerThis, AsAmpersandOperand,
+                               AsPointerFromArrayDecay, AsOperatorArrowThis,
+                               AsNonConstRefArg, AsLambdaRefCaptureInit,
+                               AsNonConstRefReturn))
                         .bind("stmt")),
             Stm, Context);
   return selectFirst<Stmt>("stmt", Matches);
 }
 
 const Stmt *ExprMutationAnalyzer::findMemberMutation(const Expr *Exp) {
   // Check whether any member of 'Exp' is mutated.
   const auto MemberExprs =
if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
       }
     }
     // Not forwarding reference.
     return Exp;
   }
   return nullptr;
 }
 
+const Stmt *ExprMutationAnalyzer::findPointeeDirectMutation(const Expr *Exp) {
+  // Bail out early if pointee can't be *directly* mutated.
+  if (!isPointeeMutable(Exp, Context))
+    return nullptr;
+  bool ExpIsPointer = Exp->getType()->getAs<PointerType>() != nullptr;
+
+  // Invoking non-const member function.
+  // A member function is assumed to be non-const when it is unresolved.
+  // We don't handle pointer-like types here, because they need to be
+  // dereferenced first before any non-const member function of the pointee can
+  // be invoked, and once dereferenced they become real pointers.
+  const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
+  const auto AsNonConstPointerThis =
+      ExpIsPointer
+          ? expr(anyOf(
+                cxxMemberCallExpr(callee(NonConstMethod), on(equalsNode(Exp))),
+                cxxOperatorCallExpr(callee(NonConstMethod),
+                                    hasArgument(0, equalsNode(Exp))),
+                callExpr(callee(expr(anyOf(
+                    unresolvedMemberExpr(hasObjectExpression(equalsNode(Exp))),
+                    cxxDependentScopeMemberExpr(
+                        hasObjectExpression(equalsNode(Exp)))))))))
+          : expr(unless(anything()));
+
+  // Used as an argument when calling a function.
+  const auto AsArg =
+      anyOf(callExpr(hasAnyArgument(equalsNode(Exp))),
+            cxxConstructExpr(hasAnyArgument(equalsNode(Exp))),
+            cxxUnresolvedConstructExpr(hasAnyArgument(equalsNode(Exp))));
+
+  // Captured by a lambda.
+  const auto AsLambdaCaptureInit = lambdaExpr(hasCaptureInit(Exp));
+
+  // Returned from the function.
+  const auto AsReturnValue = returnStmt(hasReturnValue(equalsNode(Exp)));
+
+  const auto Matches =
+      match(findAll(stmt(anyOf(AsNonConstPointerThis, AsArg,
+                               AsLambdaCaptureInit, AsReturnValue))
+                        .bind("stmt")),
+            Stm, Context);
+  return selectFirst<Stmt>("stmt", Matches);
+}
+
+const Stmt *ExprMutationAnalyzer::findPointeeCastMutation(const Expr *Exp) {
+  // Only handling LValueToRValue for now for easier unit testing during
+  // implementation.
+  // TODO: properly handle all casts scenarios.
+  const auto Casts =
+      match(findAll(implicitCastExpr(hasSourceExpression(equalsNode(Exp)),
+                                     hasCastKind(CK_LValueToRValue))
+                        .bind(NodeID<Expr>::value)),
+            Stm, Context);
+  return findExprPointeeMutation(Casts);
+}
+
 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.findMutation(Parm))
           Results[Parm] = S;
       }
     }
   }
 }
 
 const Stmt *
 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
   const auto Memoized = Results.find(Parm);

unittests/Analysis/ExprMutationAnalyzerTest.cpp

ExprMatcher declRefTo(StringRef Name) {
   return declRefExpr(to(namedDecl(hasName(Name))));
 }
 
 StmtMatcher withEnclosingCompound(ExprMatcher Matcher) {
   return expr(Matcher, hasAncestor(compoundStmt().bind("stmt"))).bind("expr");
 }
 
 bool isMutated(const SmallVectorImpl<BoundNodes> &Results, ASTUnit *AST) {
-  const auto *const S = selectFirst<Stmt>("stmt", Results);
-  const auto *const E = selectFirst<Expr>("expr", Results);
+  const auto *S = selectFirst<Stmt>("stmt", Results);
+  const auto *E = selectFirst<Expr>("expr", Results);
+  assert(S && E);
   return ExprMutationAnalyzer(*S, AST->getASTContext()).isMutated(E);
 }
 
+bool isPointeeMutated(const SmallVectorImpl<BoundNodes> &Results,
+                      ASTUnit *AST) {
+  const auto *S = selectFirst<Stmt>("stmt", Results);
+  const auto *E = selectFirst<Expr>("expr", Results);
+  assert(S && E);
+  return ExprMutationAnalyzer(*S, AST->getASTContext()).isPointeeMutated(E);
+}
+
 SmallVector<std::string, 1>
 mutatedBy(const SmallVectorImpl<BoundNodes> &Results, ASTUnit *AST) {
+  EXPECT_TRUE(isMutated(Results, AST));
   const auto *const S = selectFirst<Stmt>("stmt", Results);
   SmallVector<std::string, 1> Chain;
   ExprMutationAnalyzer Analyzer(*S, AST->getASTContext());
   for (const auto *E = selectFirst<Expr>("expr", Results); E != nullptr;) {
     const Stmt *By = Analyzer.findMutation(E);
     std::string buffer;
     llvm::raw_string_ostream stream(buffer);
     By->printPretty(stream, nullptr, AST->getASTContext().getPrintingPolicy());
     Chain.push_back(StringRef(stream.str()).trim().str());
     E = dyn_cast<DeclRefExpr>(By);
   }
   return Chain;
 }
 
+std::string pointeeMutatedBy(const SmallVectorImpl<BoundNodes> &Results,
+                             ASTUnit *AST) {
+  EXPECT_TRUE(isPointeeMutated(Results, AST));
+  const auto *S = selectFirst<Stmt>("stmt", Results);
+  const auto *E = selectFirst<Expr>("expr", Results);
+  ExprMutationAnalyzer Analyzer(*S, AST->getASTContext());
+  std::string buffer;
+  llvm::raw_string_ostream stream(buffer);
+  const Stmt *By = Analyzer.findPointeeMutation(E);
+  By->printPretty(stream, nullptr, AST->getASTContext().getPrintingPolicy());
+  return StringRef(stream.str()).trim().str();
+}
+
 std::string removeSpace(std::string s) {
   s.erase(std::remove_if(s.begin(), s.end(),
                          [](char c) { return std::isspace(c); }),
           s.end());
   return s;
 }
 
 const std::string StdRemoveReference =
const std::string StdForward =
     "template<class T> T&& "
     "forward(typename remove_reference<T>::type& t) noexcept { return t; }"
     "template<class T> T&& "
     "forward(typename remove_reference<T>::type&& t) noexcept { return t; } }";
 
 } // namespace
 
 TEST(ExprMutationAnalyzerTest, Trivial) {
-  const auto AST = buildASTFromCode("void f() { int x; x; }");
-  const auto Results =
+  auto AST = buildASTFromCode("void f() { int x; x; }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = buildASTFromCode("void f() { const int x = 0; x; }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 class AssignmentTest : public ::testing::TestWithParam<std::string> {};
 
 TEST_P(AssignmentTest, AssignmentModifies) {
   const std::string ModExpr = "x " + GetParam() + " 10";
   const auto AST = buildASTFromCode("void f() { int x; " + ModExpr + "; }");
   const auto Results =
const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre(ModExpr));
 }
 
 INSTANTIATE_TEST_CASE_P(AllIncDecOperators, IncDecTest,
                         Values("++x", "--x", "x++", "x--"), );
 
 TEST(ExprMutationAnalyzerTest, NonConstMemberFunc) {
-  const auto AST = buildASTFromCode(
+  auto AST = buildASTFromCode(
       "void f() { struct Foo { void mf(); }; Foo x; x.mf(); }");
-  const auto Results =
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x.mf()"));
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
+
+  AST = buildASTFromCode(
+      "void f() { struct Foo { void mf(); }; Foo *p; p->mf(); }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "p->mf()");
+
+  AST = buildASTFromCode(
+      "void f() { struct Foo { void mf(); }; Foo *x; Foo *&p = x; p->mf(); }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "p->mf()");
 }
 
 TEST(ExprMutationAnalyzerTest, AssumedNonConstMemberFunc) {
   auto AST = buildASTFromCodeWithArgs(
       "struct X { template <class T> void mf(); };"
-      "template <class T> void f() { X x; x.mf<T>(); }",
+      "template <class T> void f() { X x; x.mf<T>(); }"
+      "template <class T> void g() { X *p; p->mf<T>(); }",
       {"-fno-delayed-template-parsing"});
   auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x.mf<T>()"));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "p->mf<T>()");
 
-  AST = buildASTFromCodeWithArgs("template <class T> void f() { T x; x.mf(); }",
-                                 {"-fno-delayed-template-parsing"});
+  AST =
+      buildASTFromCodeWithArgs("template <class T> void f() { T x; x.mf(); }"
+                               "template <class T> void g() { T *p; p->mf(); }",
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x.mf()"));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "p->mf()");
 
   AST = buildASTFromCodeWithArgs(
       "template <class T> struct X;"
-      "template <class T> void f() { X<T> x; x.mf(); }",
+      "template <class T> void f() { X<T> x; x.mf(); }"
+      "template <class T> void g() { X<T> *p; p->mf(); }",
       {"-fno-delayed-template-parsing"});
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x.mf()"));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "p->mf()");
+
+  AST = buildASTFromCodeWithArgs(
+      "struct X { template <class T> void mf() const; };"
+      "template <class T> void f() { const X x; x.mf<T>(); }"
+      "template <class T> void g() { const X *p; p->mf<T>(); }",
+      {"-fno-delayed-template-parsing"});
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
+
+  AST = buildASTFromCodeWithArgs(
+      "template <class T> void f() { const T x; x.mf(); }"
+      "template <class T> void g() { const T *p; p->mf(); }",
+      {"-fno-delayed-template-parsing"});
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
+
+  AST = buildASTFromCodeWithArgs(
+      "template <class T> struct X;"
+      "template <class T> void f() { const X<T> x; x.mf(); }"
+      "template <class T> void g() { const X<T> *p; p->mf(); }",
+      {"-fno-delayed-template-parsing"});
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, ConstMemberFunc) {
-  const auto AST = buildASTFromCode(
+  auto AST = buildASTFromCode(
       "void f() { struct Foo { void mf() const; }; Foo x; x.mf(); }");
-  const auto Results =
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = buildASTFromCode(
+      "void f() { struct Foo { void mf() const; }; const Foo x; x.mf(); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = buildASTFromCode(
+      "void f() { struct Foo { void mf() const; }; Foo *p; p->mf(); }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
+
+  AST = buildASTFromCode(
+      "void f() { struct Foo { void mf() const; }; const Foo *p; p->mf(); }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, NonConstOperator) {
   const auto AST = buildASTFromCode(
       "void f() { struct Foo { Foo& operator=(int); }; Foo x; x = 10; }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x = 10"));
 }
 
 TEST(ExprMutationAnalyzerTest, ConstOperator) {
   const auto AST = buildASTFromCode(
       "void f() { struct Foo { int operator()() const; }; Foo x; x(); }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, ByValueArgument) {
   auto AST = buildASTFromCode("void g(int); void f() { int x; g(x); }");
   auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 
-  AST = buildASTFromCode("void g(int*); void f() { int* x; g(x); }");
-  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  AST = buildASTFromCode("void g(int*); void f() { int* p; g(p); }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "g(p)");
 
   AST = buildASTFromCode("typedef int* IntPtr;"
                          "void g(IntPtr); void f() { int* x; g(x); }");
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 
   AST = buildASTFromCode(
       "struct A {}; A operator+(A, int); void f() { A x; x + 1; }");
TEST(ExprMutationAnalyzerTest, ReturnAsValue) {
   auto AST = buildASTFromCode("int f() { int x; return x; }");
   auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 
   AST = buildASTFromCode("int* f() { int* x; return x; }");
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "return x;");
+
+  AST = buildASTFromCode("const int* f() { int* x; return x; }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_FALSE(isPointeeMutated(Results, AST.get()));
+  // TODO: this should work when casts of pointers are handled.
+  // EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "return x;");
 
   AST = buildASTFromCode("typedef int* IntPtr;"
                          "IntPtr f() { int* x; return x; }");
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_EQ(pointeeMutatedBy(Results, AST.get()), "return x;");
 }
 
 TEST(ExprMutationAnalyzerTest, ReturnAsNonConstRef) {
   const auto AST = buildASTFromCode("int& f() { int x; return x; }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("return x;"));
 }
TEST(ExprMutationAnalyzerTest, ReturnAsConstRRef) {
   const auto AST = buildASTFromCode(
       "const int&& f() { int x; return static_cast<int&&>(x); }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, TakeAddress) {
-  const auto AST = buildASTFromCode("void g(int*); void f() { int x; g(&x); }");
-  const auto Results =
+  auto AST = buildASTFromCode("void g(int*); void f() { int x; g(&x); }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("&x"));
+
+  AST = buildASTFromCode(
+      "void g(const int*); void f() { const int x = 10; g(&x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, ArrayToPointerDecay) {
-  const auto AST =
-      buildASTFromCode("void g(int*); void f() { int x[2]; g(x); }");
-  const auto Results =
+  auto AST = buildASTFromCode("void g(int*); void f() { int x[2]; g(x); }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x"));
+
+  AST = buildASTFromCode("void f() { int x[2]; *x = 10; }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x"));
+
+  AST = buildASTFromCode(
+      "void g(const int*); void f() { const int x[2] = {}; g(x); }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, TemplateWithArrayToPointerDecay) {
   const auto AST = buildASTFromCodeWithArgs(
       "template <typename T> struct S { static constexpr int v = 8; };"
       "template <> struct S<int> { static constexpr int v = 4; };"
       "void g(char*);"
       "template <typename T> void f() { char x[S<T>::v]; g(x); }"
TEST(ExprMutationAnalyzerTest, CastToConstRef) {
 
   AST = buildASTFromCode("typedef const int& CIntRef;"
                          "void f() { int x; static_cast<CIntRef>(x); }");
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, LambdaDefaultCaptureByValue) {
-  const auto AST = buildASTFromCode("void f() { int x; [=]() { x; }; }");
-  const auto Results =
+  auto AST = buildASTFromCode("void f() { int x; [=]() { x; }; }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = buildASTFromCode("void f() { int *p; [=]() { *p = 10; }; }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_THAT(pointeeMutatedBy(Results, AST.get()),
+              ResultOf(removeSpace, "[=](){*p=10;}"));
 }
 
 TEST(ExprMutationAnalyzerTest, LambdaExplicitCaptureByValue) {
-  const auto AST = buildASTFromCode("void f() { int x; [x]() { x; }; }");
-  const auto Results =
+  auto AST = buildASTFromCode("void f() { int x; [x]() { x; }; }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));
+
+  AST = buildASTFromCode("void f() { int *p; [p]() { *p = 10; }; }");
+  Results = match(withEnclosingCompound(declRefTo("p")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+  EXPECT_THAT(pointeeMutatedBy(Results, AST.get()),
+              ResultOf(removeSpace, "[p](){*p=10;}"));
 }
 
 TEST(ExprMutationAnalyzerTest, LambdaDefaultCaptureByRef) {
-  const auto AST = buildASTFromCode("void f() { int x; [&]() { x = 10; }; }");
-  const auto Results =
+  auto AST = buildASTFromCode("void f() { int x; [&]() { x = 10; }; }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()),
               ElementsAre(ResultOf(removeSpace, "[&](){x=10;}")));
+
+  AST = buildASTFromCode("void f() { const int x = 10; [&]() { x; }; }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, LambdaExplicitCaptureByRef) {
-  const auto AST = buildASTFromCode("void f() { int x; [&x]() { x = 10; }; }");
-  const auto Results =
+  auto AST = buildASTFromCode("void f() { int x; [&x]() { x = 10; }; }");
+  auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()),
               ElementsAre(ResultOf(removeSpace, "[&x](){x=10;}")));
+
+  AST = buildASTFromCode("void f() { const int x = 10; [&x]() { x; }; }");
+  Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
 TEST(ExprMutationAnalyzerTest, RangeForArrayByRefModified) {
   auto AST =
       buildASTFromCode("void f() { int x[2]; for (int& e : x) e = 10; }");
   auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("e", "e = 10"));
TEST(ExprMutationAnalyzerTest, UniquePtr) {
 
   AST = buildASTFromCodeWithArgs(
       UniquePtrDef + "template <class T> void f() { UniquePtr<T> x; x->mf(); }",
       {"-fno-delayed-template-parsing"});
   Results = match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_THAT(mutatedBy(Results, AST.get()), ElementsAre("x->mf()"));
 }
 
+TEST(ExprMutationAnalyzerTest, Dereference) {
+  // TODO: add follow cases:
+  // - multiple levels of pointers `int ***`, `int * const *`
+  //   (ensure that having a const pointer does no influence the pointee
+  //   analysis `int * const p = &i; *p = 42;`)
+  // - a class with `operator*` + `operator->`
+}
+
 } // namespace clang