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