xref: /llvm-project/clang/lib/Analysis/ExprMutationAnalyzer.cpp (revision 53ea5ffcb38d428e446d357f310e9c28957eaec7)
1 //===---------- ExprMutationAnalyzer.cpp ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
9 #include "clang/AST/Expr.h"
10 #include "clang/AST/OperationKinds.h"
11 #include "clang/AST/Stmt.h"
12 #include "clang/ASTMatchers/ASTMatchFinder.h"
13 #include "clang/ASTMatchers/ASTMatchers.h"
14 #include "clang/ASTMatchers/ASTMatchersMacros.h"
15 #include "llvm/ADT/STLExtras.h"
16 
17 namespace clang {
18 using namespace ast_matchers;
19 
20 // Check if result of Source expression could be a Target expression.
21 // Checks:
22 //  - Implicit Casts
23 //  - Binary Operators
24 //  - ConditionalOperator
25 //  - BinaryConditionalOperator
26 static bool canExprResolveTo(const Expr *Source, const Expr *Target) {
27   const auto IgnoreDerivedToBase = [](const Expr *E, auto Matcher) {
28     if (Matcher(E))
29       return true;
30     if (const auto *Cast = dyn_cast<ImplicitCastExpr>(E)) {
31       if ((Cast->getCastKind() == CK_DerivedToBase ||
32            Cast->getCastKind() == CK_UncheckedDerivedToBase) &&
33           Matcher(Cast->getSubExpr()))
34         return true;
35     }
36     return false;
37   };
38 
39   const auto EvalCommaExpr = [](const Expr *E, auto Matcher) {
40     const Expr *Result = E;
41     while (const auto *BOComma =
42                dyn_cast_or_null<BinaryOperator>(Result->IgnoreParens())) {
43       if (!BOComma->isCommaOp())
44         break;
45       Result = BOComma->getRHS();
46     }
47 
48     return Result != E && Matcher(Result);
49   };
50 
51   // The 'ConditionalOperatorM' matches on `<anything> ? <expr> : <expr>`.
52   // This matching must be recursive because `<expr>` can be anything resolving
53   // to the `InnerMatcher`, for example another conditional operator.
54   // The edge-case `BaseClass &b = <cond> ? DerivedVar1 : DerivedVar2;`
55   // is handled, too. The implicit cast happens outside of the conditional.
56   // This is matched by `IgnoreDerivedToBase(canResolveToExpr(InnerMatcher))`
57   // below.
58   const auto ConditionalOperatorM = [Target](const Expr *E) {
59     if (const auto *CO = dyn_cast<AbstractConditionalOperator>(E)) {
60       const auto *TE = CO->getTrueExpr()->IgnoreParens();
61       if (TE && canExprResolveTo(TE, Target))
62         return true;
63       const auto *FE = CO->getFalseExpr()->IgnoreParens();
64       if (FE && canExprResolveTo(FE, Target))
65         return true;
66     }
67     return false;
68   };
69 
70   const Expr *SourceExprP = Source->IgnoreParens();
71   return IgnoreDerivedToBase(SourceExprP,
72                              [&](const Expr *E) {
73                                return E == Target || ConditionalOperatorM(E);
74                              }) ||
75          EvalCommaExpr(SourceExprP, [&](const Expr *E) {
76            return IgnoreDerivedToBase(
77                E->IgnoreParens(), [&](const Expr *EE) { return EE == Target; });
78          });
79 }
80 
81 namespace {
82 
83 AST_MATCHER(Type, isDependentType) { return Node.isDependentType(); }
84 
85 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
86   return llvm::is_contained(Node.capture_inits(), E);
87 }
88 
89 AST_MATCHER_P(CXXForRangeStmt, hasRangeStmt,
90               ast_matchers::internal::Matcher<DeclStmt>, InnerMatcher) {
91   const DeclStmt *const Range = Node.getRangeStmt();
92   return InnerMatcher.matches(*Range, Finder, Builder);
93 }
94 
95 AST_MATCHER_P(Stmt, canResolveToExpr, const Stmt *, Inner) {
96   auto *Exp = dyn_cast<Expr>(&Node);
97   if (!Exp)
98     return true;
99   auto *Target = dyn_cast<Expr>(Inner);
100   if (!Target)
101     return false;
102   return canExprResolveTo(Exp, Target);
103 }
104 
105 // use class member to store data can reduce stack usage to avoid stack overflow
106 // when recursive call.
107 class ExprPointeeResolve {
108   const Expr *T;
109 
110   bool resolveExpr(const Expr *E) {
111     if (E == nullptr)
112       return false;
113     if (E == T)
114       return true;
115 
116     if (const auto *BO = dyn_cast<BinaryOperator>(E)) {
117       if (BO->isAdditiveOp())
118         return (resolveExpr(BO->getLHS()) || resolveExpr(BO->getRHS()));
119       if (BO->isCommaOp())
120         return resolveExpr(BO->getRHS());
121       return false;
122     }
123 
124     if (const auto *PE = dyn_cast<ParenExpr>(E))
125       return resolveExpr(PE->getSubExpr());
126 
127     if (const auto *ICE = dyn_cast<ImplicitCastExpr>(E)) {
128       // only implicit cast needs to be treated as resolvable.
129       // explicit cast will be checked in `findPointeeToNonConst`
130       const CastKind kind = ICE->getCastKind();
131       if (kind == CK_LValueToRValue || kind == CK_DerivedToBase ||
132           kind == CK_UncheckedDerivedToBase)
133         return resolveExpr(ICE->getSubExpr());
134       return false;
135     }
136 
137     if (const auto *ACE = dyn_cast<AbstractConditionalOperator>(E))
138       return resolve(ACE->getTrueExpr()) || resolve(ACE->getFalseExpr());
139 
140     return false;
141   }
142 
143 public:
144   ExprPointeeResolve(const Expr *T) : T(T) {}
145   bool resolve(const Expr *S) { return resolveExpr(S); }
146 };
147 
148 AST_MATCHER_P(Stmt, canResolveToExprPointee, const Stmt *, T) {
149   auto *Exp = dyn_cast<Expr>(&Node);
150   if (!Exp)
151     return true;
152   auto *Target = dyn_cast<Expr>(T);
153   if (!Target)
154     return false;
155   return ExprPointeeResolve{Target}.resolve(Exp);
156 }
157 
158 // Similar to 'hasAnyArgument', but does not work because 'InitListExpr' does
159 // not have the 'arguments()' method.
160 AST_MATCHER_P(InitListExpr, hasAnyInit, ast_matchers::internal::Matcher<Expr>,
161               InnerMatcher) {
162   for (const Expr *Arg : Node.inits()) {
163     if (Arg == nullptr)
164       continue;
165     ast_matchers::internal::BoundNodesTreeBuilder Result(*Builder);
166     if (InnerMatcher.matches(*Arg, Finder, &Result)) {
167       *Builder = std::move(Result);
168       return true;
169     }
170   }
171   return false;
172 }
173 
174 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
175     cxxTypeidExpr;
176 
177 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
178   return Node.isPotentiallyEvaluated();
179 }
180 
181 AST_MATCHER(CXXMemberCallExpr, isConstCallee) {
182   const Decl *CalleeDecl = Node.getCalleeDecl();
183   const auto *VD = dyn_cast_or_null<ValueDecl>(CalleeDecl);
184   if (!VD)
185     return false;
186   const QualType T = VD->getType().getCanonicalType();
187   const auto *MPT = dyn_cast<MemberPointerType>(T);
188   const auto *FPT = MPT ? cast<FunctionProtoType>(MPT->getPointeeType())
189                         : dyn_cast<FunctionProtoType>(T);
190   if (!FPT)
191     return false;
192   return FPT->isConst();
193 }
194 
195 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
196               ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
197   if (Node.isTypePredicate())
198     return false;
199   return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
200 }
201 
202 template <typename T>
203 ast_matchers::internal::Matcher<T>
204 findFirst(const ast_matchers::internal::Matcher<T> &Matcher) {
205   return anyOf(Matcher, hasDescendant(Matcher));
206 }
207 
208 const auto nonConstReferenceType = [] {
209   return hasUnqualifiedDesugaredType(
210       referenceType(pointee(unless(isConstQualified()))));
211 };
212 
213 const auto nonConstPointerType = [] {
214   return hasUnqualifiedDesugaredType(
215       pointerType(pointee(unless(isConstQualified()))));
216 };
217 
218 const auto isMoveOnly = [] {
219   return cxxRecordDecl(
220       hasMethod(cxxConstructorDecl(isMoveConstructor(), unless(isDeleted()))),
221       hasMethod(cxxMethodDecl(isMoveAssignmentOperator(), unless(isDeleted()))),
222       unless(anyOf(hasMethod(cxxConstructorDecl(isCopyConstructor(),
223                                                 unless(isDeleted()))),
224                    hasMethod(cxxMethodDecl(isCopyAssignmentOperator(),
225                                            unless(isDeleted()))))));
226 };
227 
228 template <class T> struct NodeID;
229 template <> struct NodeID<Expr> { static constexpr StringRef value = "expr"; };
230 template <> struct NodeID<Decl> { static constexpr StringRef value = "decl"; };
231 constexpr StringRef NodeID<Expr>::value;
232 constexpr StringRef NodeID<Decl>::value;
233 
234 template <class T,
235           class F = const Stmt *(ExprMutationAnalyzer::Analyzer::*)(const T *)>
236 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
237                          ExprMutationAnalyzer::Analyzer *Analyzer, F Finder) {
238   const StringRef ID = NodeID<T>::value;
239   for (const auto &Nodes : Matches) {
240     if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
241       return S;
242   }
243   return nullptr;
244 }
245 
246 } // namespace
247 
248 const Stmt *ExprMutationAnalyzer::Analyzer::findMutation(const Expr *Exp) {
249   return findMutationMemoized(
250       Exp,
251       {&ExprMutationAnalyzer::Analyzer::findDirectMutation,
252        &ExprMutationAnalyzer::Analyzer::findMemberMutation,
253        &ExprMutationAnalyzer::Analyzer::findArrayElementMutation,
254        &ExprMutationAnalyzer::Analyzer::findCastMutation,
255        &ExprMutationAnalyzer::Analyzer::findRangeLoopMutation,
256        &ExprMutationAnalyzer::Analyzer::findReferenceMutation,
257        &ExprMutationAnalyzer::Analyzer::findFunctionArgMutation},
258       Memorized.Results);
259 }
260 
261 const Stmt *ExprMutationAnalyzer::Analyzer::findMutation(const Decl *Dec) {
262   return tryEachDeclRef(Dec, &ExprMutationAnalyzer::Analyzer::findMutation);
263 }
264 
265 const Stmt *
266 ExprMutationAnalyzer::Analyzer::findPointeeMutation(const Expr *Exp) {
267   return findMutationMemoized(
268       Exp,
269       {
270           &ExprMutationAnalyzer::Analyzer::findPointeeValueMutation,
271           &ExprMutationAnalyzer::Analyzer::findPointeeMemberMutation,
272           &ExprMutationAnalyzer::Analyzer::findPointeeToNonConst,
273       },
274       Memorized.PointeeResults);
275 }
276 
277 const Stmt *
278 ExprMutationAnalyzer::Analyzer::findPointeeMutation(const Decl *Dec) {
279   return tryEachDeclRef(Dec,
280                         &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
281 }
282 
283 const Stmt *ExprMutationAnalyzer::Analyzer::findMutationMemoized(
284     const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,
285     Memoized::ResultMap &MemoizedResults) {
286   // Assume Exp is not mutated before analyzing Exp.
287   auto [Memoized, Inserted] = MemoizedResults.try_emplace(Exp);
288   if (!Inserted)
289     return Memoized->second;
290 
291   if (ExprMutationAnalyzer::isUnevaluated(Exp, Context))
292     return nullptr;
293 
294   for (const auto &Finder : Finders) {
295     if (const Stmt *S = (this->*Finder)(Exp))
296       return MemoizedResults[Exp] = S;
297   }
298 
299   return nullptr;
300 }
301 
302 const Stmt *
303 ExprMutationAnalyzer::Analyzer::tryEachDeclRef(const Decl *Dec,
304                                                MutationFinder Finder) {
305   const auto Refs = match(
306       findAll(
307           declRefExpr(to(
308                           // `Dec` or a binding if `Dec` is a decomposition.
309                           anyOf(equalsNode(Dec),
310                                 bindingDecl(forDecomposition(equalsNode(Dec))))
311                           //
312                           ))
313               .bind(NodeID<Expr>::value)),
314       Stm, Context);
315   for (const auto &RefNodes : Refs) {
316     const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
317     if ((this->*Finder)(E))
318       return E;
319   }
320   return nullptr;
321 }
322 
323 bool ExprMutationAnalyzer::isUnevaluated(const Stmt *Stm, ASTContext &Context) {
324   return !match(stmt(anyOf(
325                     // `Exp` is part of the underlying expression of
326                     // decltype/typeof if it has an ancestor of
327                     // typeLoc.
328                     hasAncestor(typeLoc(
329                         unless(hasAncestor(unaryExprOrTypeTraitExpr())))),
330                     hasAncestor(expr(anyOf(
331                         // `UnaryExprOrTypeTraitExpr` is unevaluated
332                         // unless it's sizeof on VLA.
333                         unaryExprOrTypeTraitExpr(unless(sizeOfExpr(
334                             hasArgumentOfType(variableArrayType())))),
335                         // `CXXTypeidExpr` is unevaluated unless it's
336                         // applied to an expression of glvalue of
337                         // polymorphic class type.
338                         cxxTypeidExpr(unless(isPotentiallyEvaluated())),
339                         // The controlling expression of
340                         // `GenericSelectionExpr` is unevaluated.
341                         genericSelectionExpr(
342                             hasControllingExpr(hasDescendant(equalsNode(Stm)))),
343                         cxxNoexceptExpr()))))),
344                 *Stm, Context)
345               .empty();
346 }
347 
348 const Stmt *
349 ExprMutationAnalyzer::Analyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
350   return tryEachMatch<Expr>(Matches, this,
351                             &ExprMutationAnalyzer::Analyzer::findMutation);
352 }
353 
354 const Stmt *
355 ExprMutationAnalyzer::Analyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
356   return tryEachMatch<Decl>(Matches, this,
357                             &ExprMutationAnalyzer::Analyzer::findMutation);
358 }
359 
360 const Stmt *ExprMutationAnalyzer::Analyzer::findExprPointeeMutation(
361     ArrayRef<ast_matchers::BoundNodes> Matches) {
362   return tryEachMatch<Expr>(
363       Matches, this, &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
364 }
365 
366 const Stmt *ExprMutationAnalyzer::Analyzer::findDeclPointeeMutation(
367     ArrayRef<ast_matchers::BoundNodes> Matches) {
368   return tryEachMatch<Decl>(
369       Matches, this, &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
370 }
371 
372 const Stmt *
373 ExprMutationAnalyzer::Analyzer::findDirectMutation(const Expr *Exp) {
374   // LHS of any assignment operators.
375   const auto AsAssignmentLhs =
376       binaryOperator(isAssignmentOperator(), hasLHS(canResolveToExpr(Exp)));
377 
378   // Operand of increment/decrement operators.
379   const auto AsIncDecOperand =
380       unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
381                     hasUnaryOperand(canResolveToExpr(Exp)));
382 
383   // Invoking non-const member function.
384   // A member function is assumed to be non-const when it is unresolved.
385   const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
386 
387   const auto AsNonConstThis = expr(anyOf(
388       cxxMemberCallExpr(on(canResolveToExpr(Exp)), unless(isConstCallee())),
389       cxxOperatorCallExpr(callee(NonConstMethod),
390                           hasArgument(0, canResolveToExpr(Exp))),
391       // In case of a templated type, calling overloaded operators is not
392       // resolved and modelled as `binaryOperator` on a dependent type.
393       // Such instances are considered a modification, because they can modify
394       // in different instantiations of the template.
395       binaryOperator(isTypeDependent(),
396                      hasEitherOperand(ignoringImpCasts(canResolveToExpr(Exp)))),
397       // A fold expression may contain `Exp` as it's initializer.
398       // We don't know if the operator modifies `Exp` because the
399       // operator is type dependent due to the parameter pack.
400       cxxFoldExpr(hasFoldInit(ignoringImpCasts(canResolveToExpr(Exp)))),
401       // Within class templates and member functions the member expression might
402       // not be resolved. In that case, the `callExpr` is considered to be a
403       // modification.
404       callExpr(callee(expr(anyOf(
405           unresolvedMemberExpr(hasObjectExpression(canResolveToExpr(Exp))),
406           cxxDependentScopeMemberExpr(
407               hasObjectExpression(canResolveToExpr(Exp))))))),
408       // Match on a call to a known method, but the call itself is type
409       // dependent (e.g. `vector<T> v; v.push(T{});` in a templated function).
410       callExpr(allOf(
411           isTypeDependent(),
412           callee(memberExpr(hasDeclaration(NonConstMethod),
413                             hasObjectExpression(canResolveToExpr(Exp))))))));
414 
415   // Taking address of 'Exp'.
416   // We're assuming 'Exp' is mutated as soon as its address is taken, though in
417   // theory we can follow the pointer and see whether it escaped `Stm` or is
418   // dereferenced and then mutated. This is left for future improvements.
419   const auto AsAmpersandOperand =
420       unaryOperator(hasOperatorName("&"),
421                     // A NoOp implicit cast is adding const.
422                     unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
423                     hasUnaryOperand(canResolveToExpr(Exp)));
424   const auto AsPointerFromArrayDecay = castExpr(
425       hasCastKind(CK_ArrayToPointerDecay),
426       unless(hasParent(arraySubscriptExpr())), has(canResolveToExpr(Exp)));
427   // Treat calling `operator->()` of move-only classes as taking address.
428   // These are typically smart pointers with unique ownership so we treat
429   // mutation of pointee as mutation of the smart pointer itself.
430   const auto AsOperatorArrowThis = cxxOperatorCallExpr(
431       hasOverloadedOperatorName("->"),
432       callee(
433           cxxMethodDecl(ofClass(isMoveOnly()), returns(nonConstPointerType()))),
434       argumentCountIs(1), hasArgument(0, canResolveToExpr(Exp)));
435 
436   // Used as non-const-ref argument when calling a function.
437   // An argument is assumed to be non-const-ref when the function is unresolved.
438   // Instantiated template functions are not handled here but in
439   // findFunctionArgMutation which has additional smarts for handling forwarding
440   // references.
441   const auto NonConstRefParam = forEachArgumentWithParamType(
442       anyOf(canResolveToExpr(Exp),
443             memberExpr(
444                 hasObjectExpression(ignoringImpCasts(canResolveToExpr(Exp))))),
445       nonConstReferenceType());
446   const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
447 
448   const auto AsNonConstRefArg =
449       anyOf(callExpr(NonConstRefParam, NotInstantiated),
450             cxxConstructExpr(NonConstRefParam, NotInstantiated),
451             // If the call is type-dependent, we can't properly process any
452             // argument because required type conversions and implicit casts
453             // will be inserted only after specialization.
454             callExpr(isTypeDependent(), hasAnyArgument(canResolveToExpr(Exp))),
455             cxxUnresolvedConstructExpr(hasAnyArgument(canResolveToExpr(Exp))),
456             // Previous False Positive in the following Code:
457             // `template <typename T> void f() { int i = 42; new Type<T>(i); }`
458             // Where the constructor of `Type` takes its argument as reference.
459             // The AST does not resolve in a `cxxConstructExpr` because it is
460             // type-dependent.
461             parenListExpr(hasDescendant(expr(canResolveToExpr(Exp)))),
462             // If the initializer is for a reference type, there is no cast for
463             // the variable. Values are cast to RValue first.
464             initListExpr(hasAnyInit(expr(canResolveToExpr(Exp)))));
465 
466   // Captured by a lambda by reference.
467   // If we're initializing a capture with 'Exp' directly then we're initializing
468   // a reference capture.
469   // For value captures there will be an ImplicitCastExpr <LValueToRValue>.
470   const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp));
471 
472   // Returned as non-const-ref.
473   // If we're returning 'Exp' directly then it's returned as non-const-ref.
474   // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
475   // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
476   // adding const.)
477   const auto AsNonConstRefReturn =
478       returnStmt(hasReturnValue(canResolveToExpr(Exp)));
479 
480   // It is used as a non-const-reference for initializing a range-for loop.
481   const auto AsNonConstRefRangeInit = cxxForRangeStmt(hasRangeInit(declRefExpr(
482       allOf(canResolveToExpr(Exp), hasType(nonConstReferenceType())))));
483 
484   const auto Matches = match(
485       traverse(
486           TK_AsIs,
487           findFirst(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
488                                AsAmpersandOperand, AsPointerFromArrayDecay,
489                                AsOperatorArrowThis, AsNonConstRefArg,
490                                AsLambdaRefCaptureInit, AsNonConstRefReturn,
491                                AsNonConstRefRangeInit))
492                         .bind("stmt"))),
493       Stm, Context);
494   return selectFirst<Stmt>("stmt", Matches);
495 }
496 
497 const Stmt *
498 ExprMutationAnalyzer::Analyzer::findMemberMutation(const Expr *Exp) {
499   // Check whether any member of 'Exp' is mutated.
500   const auto MemberExprs = match(
501       findAll(expr(anyOf(memberExpr(hasObjectExpression(canResolveToExpr(Exp))),
502                          cxxDependentScopeMemberExpr(
503                              hasObjectExpression(canResolveToExpr(Exp))),
504                          binaryOperator(hasOperatorName(".*"),
505                                         hasLHS(equalsNode(Exp)))))
506                   .bind(NodeID<Expr>::value)),
507       Stm, Context);
508   return findExprMutation(MemberExprs);
509 }
510 
511 const Stmt *
512 ExprMutationAnalyzer::Analyzer::findArrayElementMutation(const Expr *Exp) {
513   // Check whether any element of an array is mutated.
514   const auto SubscriptExprs = match(
515       findAll(arraySubscriptExpr(
516                   anyOf(hasBase(canResolveToExpr(Exp)),
517                         hasBase(implicitCastExpr(allOf(
518                             hasCastKind(CK_ArrayToPointerDecay),
519                             hasSourceExpression(canResolveToExpr(Exp)))))))
520                   .bind(NodeID<Expr>::value)),
521       Stm, Context);
522   return findExprMutation(SubscriptExprs);
523 }
524 
525 const Stmt *ExprMutationAnalyzer::Analyzer::findCastMutation(const Expr *Exp) {
526   // If the 'Exp' is explicitly casted to a non-const reference type the
527   // 'Exp' is considered to be modified.
528   const auto ExplicitCast =
529       match(findFirst(stmt(castExpr(hasSourceExpression(canResolveToExpr(Exp)),
530                                     explicitCastExpr(hasDestinationType(
531                                         nonConstReferenceType()))))
532                           .bind("stmt")),
533             Stm, Context);
534 
535   if (const auto *CastStmt = selectFirst<Stmt>("stmt", ExplicitCast))
536     return CastStmt;
537 
538   // If 'Exp' is casted to any non-const reference type, check the castExpr.
539   const auto Casts = match(
540       findAll(expr(castExpr(hasSourceExpression(canResolveToExpr(Exp)),
541                             anyOf(explicitCastExpr(hasDestinationType(
542                                       nonConstReferenceType())),
543                                   implicitCastExpr(hasImplicitDestinationType(
544                                       nonConstReferenceType())))))
545                   .bind(NodeID<Expr>::value)),
546       Stm, Context);
547 
548   if (const Stmt *S = findExprMutation(Casts))
549     return S;
550   // Treat std::{move,forward} as cast.
551   const auto Calls =
552       match(findAll(callExpr(callee(namedDecl(
553                                  hasAnyName("::std::move", "::std::forward"))),
554                              hasArgument(0, canResolveToExpr(Exp)))
555                         .bind("expr")),
556             Stm, Context);
557   return findExprMutation(Calls);
558 }
559 
560 const Stmt *
561 ExprMutationAnalyzer::Analyzer::findRangeLoopMutation(const Expr *Exp) {
562   // Keep the ordering for the specific initialization matches to happen first,
563   // because it is cheaper to match all potential modifications of the loop
564   // variable.
565 
566   // The range variable is a reference to a builtin array. In that case the
567   // array is considered modified if the loop-variable is a non-const reference.
568   const auto DeclStmtToNonRefToArray = declStmt(hasSingleDecl(varDecl(hasType(
569       hasUnqualifiedDesugaredType(referenceType(pointee(arrayType())))))));
570   const auto RefToArrayRefToElements = match(
571       findFirst(stmt(cxxForRangeStmt(
572                          hasLoopVariable(
573                              varDecl(anyOf(hasType(nonConstReferenceType()),
574                                            hasType(nonConstPointerType())))
575                                  .bind(NodeID<Decl>::value)),
576                          hasRangeStmt(DeclStmtToNonRefToArray),
577                          hasRangeInit(canResolveToExpr(Exp))))
578                     .bind("stmt")),
579       Stm, Context);
580 
581   if (const auto *BadRangeInitFromArray =
582           selectFirst<Stmt>("stmt", RefToArrayRefToElements))
583     return BadRangeInitFromArray;
584 
585   // Small helper to match special cases in range-for loops.
586   //
587   // It is possible that containers do not provide a const-overload for their
588   // iterator accessors. If this is the case, the variable is used non-const
589   // no matter what happens in the loop. This requires special detection as it
590   // is then faster to find all mutations of the loop variable.
591   // It aims at a different modification as well.
592   const auto HasAnyNonConstIterator =
593       anyOf(allOf(hasMethod(allOf(hasName("begin"), unless(isConst()))),
594                   unless(hasMethod(allOf(hasName("begin"), isConst())))),
595             allOf(hasMethod(allOf(hasName("end"), unless(isConst()))),
596                   unless(hasMethod(allOf(hasName("end"), isConst())))));
597 
598   const auto DeclStmtToNonConstIteratorContainer = declStmt(
599       hasSingleDecl(varDecl(hasType(hasUnqualifiedDesugaredType(referenceType(
600           pointee(hasDeclaration(cxxRecordDecl(HasAnyNonConstIterator)))))))));
601 
602   const auto RefToContainerBadIterators = match(
603       findFirst(stmt(cxxForRangeStmt(allOf(
604                          hasRangeStmt(DeclStmtToNonConstIteratorContainer),
605                          hasRangeInit(canResolveToExpr(Exp)))))
606                     .bind("stmt")),
607       Stm, Context);
608 
609   if (const auto *BadIteratorsContainer =
610           selectFirst<Stmt>("stmt", RefToContainerBadIterators))
611     return BadIteratorsContainer;
612 
613   // If range for looping over 'Exp' with a non-const reference loop variable,
614   // check all declRefExpr of the loop variable.
615   const auto LoopVars =
616       match(findAll(cxxForRangeStmt(
617                 hasLoopVariable(varDecl(hasType(nonConstReferenceType()))
618                                     .bind(NodeID<Decl>::value)),
619                 hasRangeInit(canResolveToExpr(Exp)))),
620             Stm, Context);
621   return findDeclMutation(LoopVars);
622 }
623 
624 const Stmt *
625 ExprMutationAnalyzer::Analyzer::findReferenceMutation(const Expr *Exp) {
626   // Follow non-const reference returned by `operator*()` of move-only classes.
627   // These are typically smart pointers with unique ownership so we treat
628   // mutation of pointee as mutation of the smart pointer itself.
629   const auto Ref = match(
630       findAll(cxxOperatorCallExpr(
631                   hasOverloadedOperatorName("*"),
632                   callee(cxxMethodDecl(ofClass(isMoveOnly()),
633                                        returns(nonConstReferenceType()))),
634                   argumentCountIs(1), hasArgument(0, canResolveToExpr(Exp)))
635                   .bind(NodeID<Expr>::value)),
636       Stm, Context);
637   if (const Stmt *S = findExprMutation(Ref))
638     return S;
639 
640   // If 'Exp' is bound to a non-const reference, check all declRefExpr to that.
641   const auto Refs = match(
642       stmt(forEachDescendant(
643           varDecl(hasType(nonConstReferenceType()),
644                   hasInitializer(anyOf(
645                       canResolveToExpr(Exp),
646                       memberExpr(hasObjectExpression(canResolveToExpr(Exp))))),
647                   hasParent(declStmt().bind("stmt")),
648                   // Don't follow the reference in range statement, we've
649                   // handled that separately.
650                   unless(hasParent(declStmt(hasParent(cxxForRangeStmt(
651                       hasRangeStmt(equalsBoundNode("stmt"))))))))
652               .bind(NodeID<Decl>::value))),
653       Stm, Context);
654   return findDeclMutation(Refs);
655 }
656 
657 const Stmt *
658 ExprMutationAnalyzer::Analyzer::findFunctionArgMutation(const Expr *Exp) {
659   const auto NonConstRefParam = forEachArgumentWithParam(
660       canResolveToExpr(Exp),
661       parmVarDecl(hasType(nonConstReferenceType())).bind("parm"));
662   const auto IsInstantiated = hasDeclaration(isInstantiated());
663   const auto FuncDecl = hasDeclaration(functionDecl().bind("func"));
664   const auto Matches = match(
665       traverse(
666           TK_AsIs,
667           findAll(
668               expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl,
669                                   unless(callee(namedDecl(hasAnyName(
670                                       "::std::move", "::std::forward"))))),
671                          cxxConstructExpr(NonConstRefParam, IsInstantiated,
672                                           FuncDecl)))
673                   .bind(NodeID<Expr>::value))),
674       Stm, Context);
675   for (const auto &Nodes : Matches) {
676     const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
677     const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
678     if (!Func->getBody() || !Func->getPrimaryTemplate())
679       return Exp;
680 
681     const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
682     const ArrayRef<ParmVarDecl *> AllParams =
683         Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
684     QualType ParmType =
685         AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
686                                    AllParams.size() - 1)]
687             ->getType();
688     if (const auto *T = ParmType->getAs<PackExpansionType>())
689       ParmType = T->getPattern();
690 
691     // If param type is forwarding reference, follow into the function
692     // definition and see whether the param is mutated inside.
693     if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
694       if (!RefType->getPointeeType().getQualifiers() &&
695           RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
696         FunctionParmMutationAnalyzer *Analyzer =
697             FunctionParmMutationAnalyzer::getFunctionParmMutationAnalyzer(
698                 *Func, Context, Memorized);
699         if (Analyzer->findMutation(Parm))
700           return Exp;
701         continue;
702       }
703     }
704     // Not forwarding reference.
705     return Exp;
706   }
707   return nullptr;
708 }
709 
710 const Stmt *
711 ExprMutationAnalyzer::Analyzer::findPointeeValueMutation(const Expr *Exp) {
712   const auto Matches = match(
713       stmt(forEachDescendant(
714           expr(anyOf(
715                    // deref by *
716                    unaryOperator(hasOperatorName("*"),
717                                  hasUnaryOperand(canResolveToExprPointee(Exp))),
718                    // deref by []
719                    arraySubscriptExpr(hasBase(canResolveToExprPointee(Exp)))))
720               .bind(NodeID<Expr>::value))),
721       Stm, Context);
722   return findExprMutation(Matches);
723 }
724 
725 const Stmt *
726 ExprMutationAnalyzer::Analyzer::findPointeeMemberMutation(const Expr *Exp) {
727   const Stmt *MemberCallExpr = selectFirst<Stmt>(
728       "stmt", match(stmt(forEachDescendant(
729                         cxxMemberCallExpr(on(canResolveToExprPointee(Exp)),
730                                           unless(isConstCallee()))
731                             .bind("stmt"))),
732                     Stm, Context));
733   if (MemberCallExpr)
734     return MemberCallExpr;
735   const auto Matches =
736       match(stmt(forEachDescendant(
737                 memberExpr(hasObjectExpression(canResolveToExprPointee(Exp)))
738                     .bind(NodeID<Expr>::value))),
739             Stm, Context);
740   return findExprMutation(Matches);
741 }
742 
743 const Stmt *
744 ExprMutationAnalyzer::Analyzer::findPointeeToNonConst(const Expr *Exp) {
745   const auto NonConstPointerOrDependentType =
746       type(anyOf(nonConstPointerType(), isDependentType()));
747 
748   // assign
749   const auto InitToNonConst =
750       varDecl(hasType(NonConstPointerOrDependentType),
751               hasInitializer(expr(canResolveToExprPointee(Exp)).bind("stmt")));
752   const auto AssignToNonConst =
753       binaryOperation(hasOperatorName("="),
754                       hasLHS(expr(hasType(NonConstPointerOrDependentType))),
755                       hasRHS(canResolveToExprPointee(Exp)));
756   // arguments like
757   const auto ArgOfInstantiationDependent = allOf(
758       hasAnyArgument(canResolveToExprPointee(Exp)), isInstantiationDependent());
759   const auto ArgOfNonConstParameter = forEachArgumentWithParamType(
760       canResolveToExprPointee(Exp), NonConstPointerOrDependentType);
761   const auto CallLikeMatcher =
762       anyOf(ArgOfNonConstParameter, ArgOfInstantiationDependent);
763   const auto PassAsNonConstArg =
764       expr(anyOf(cxxUnresolvedConstructExpr(ArgOfInstantiationDependent),
765                  cxxConstructExpr(CallLikeMatcher), callExpr(CallLikeMatcher),
766                  parenListExpr(has(canResolveToExprPointee(Exp))),
767                  initListExpr(hasAnyInit(canResolveToExprPointee(Exp)))));
768   // cast
769   const auto CastToNonConst =
770       explicitCastExpr(hasSourceExpression(canResolveToExprPointee(Exp)),
771                        hasDestinationType(NonConstPointerOrDependentType));
772 
773   // capture
774   // FIXME: false positive if the pointee does not change in lambda
775   const auto CaptureNoConst = lambdaExpr(hasCaptureInit(Exp));
776 
777   const auto Matches =
778       match(stmt(anyOf(forEachDescendant(
779                            stmt(anyOf(AssignToNonConst, PassAsNonConstArg,
780                                       CastToNonConst, CaptureNoConst))
781                                .bind("stmt")),
782                        forEachDescendant(InitToNonConst))),
783             Stm, Context);
784   return selectFirst<Stmt>("stmt", Matches);
785 }
786 
787 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
788     const FunctionDecl &Func, ASTContext &Context,
789     ExprMutationAnalyzer::Memoized &Memorized)
790     : BodyAnalyzer(*Func.getBody(), Context, Memorized) {
791   if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
792     // CXXCtorInitializer might also mutate Param but they're not part of
793     // function body, check them eagerly here since they're typically trivial.
794     for (const CXXCtorInitializer *Init : Ctor->inits()) {
795       ExprMutationAnalyzer::Analyzer InitAnalyzer(*Init->getInit(), Context,
796                                                   Memorized);
797       for (const ParmVarDecl *Parm : Ctor->parameters()) {
798         if (Results.contains(Parm))
799           continue;
800         if (const Stmt *S = InitAnalyzer.findMutation(Parm))
801           Results[Parm] = S;
802       }
803     }
804   }
805 }
806 
807 const Stmt *
808 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
809   const auto Memoized = Results.find(Parm);
810   if (Memoized != Results.end())
811     return Memoized->second;
812   // To handle call A -> call B -> call A. Assume parameters of A is not mutated
813   // before analyzing parameters of A. Then when analyzing the second "call A",
814   // FunctionParmMutationAnalyzer can use this memoized value to avoid infinite
815   // recursion.
816   Results[Parm] = nullptr;
817   if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
818     return Results[Parm] = S;
819   return Results[Parm];
820 }
821 
822 } // namespace clang
823