clang/lib/Analysis/ExprMutationAnalyzer.cpp

   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
  15 namespace clang {
  16 using 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
  24 static 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
  93 namespace {
  94
  95 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
  96   return llvm::is_contained(Node.capture_inits(), E);
  97 }
  98
  99 AST_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
 105 AST_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.
 117 AST_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
 129 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
 130     cxxTypeidExpr;
 131
 132 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
 133   return Node.isPotentiallyEvaluated();
 134 }
 135
 136 AST_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
 150 AST_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
 157 template <typename T>
 158 ast_matchers::internal::Matcher<T>
 159 findFirst(const ast_matchers::internal::Matcher<T> &Matcher) {
 160   return anyOf(Matcher, hasDescendant(Matcher));
 161 }
 162
 163 const auto nonConstReferenceType = [] {
 164   return hasUnqualifiedDesugaredType(
 165       referenceType(pointee(unless(isConstQualified()))));
 166 };
 167
 168 const auto nonConstPointerType = [] {
 169   return hasUnqualifiedDesugaredType(
 170       pointerType(pointee(unless(isConstQualified()))));
 171 };
 172
 173 const 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
 183 template <class T> struct NodeID;
 184 template <> struct NodeID<Expr> { static constexpr StringRef value = "expr"; };
 185 template <> struct NodeID<Decl> { static constexpr StringRef value = "decl"; };
 186 constexpr StringRef NodeID<Expr>::value;
 187 constexpr StringRef NodeID<Decl>::value;
 188
 189 template <class T,
 190           class F = const Stmt *(ExprMutationAnalyzer::Analyzer::*)(const T *)>
 191 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
 192                          ExprMutationAnalyzer::Analyzer *Analyzer, F Finder) {
 193   const StringRef ID = NodeID<T>::value;
 194   for (const auto &Nodes : Matches) {
 195     if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
 196       return S;
 197   }
 198   return nullptr;
 199 }
 200
 201 } // namespace
 202
 203 const Stmt *ExprMutationAnalyzer::Analyzer::findMutation(const Expr *Exp) {
 204   return findMutationMemoized(
 205       Exp,
 206       {&ExprMutationAnalyzer::Analyzer::findDirectMutation,
 207        &ExprMutationAnalyzer::Analyzer::findMemberMutation,
 208        &ExprMutationAnalyzer::Analyzer::findArrayElementMutation,
 209        &ExprMutationAnalyzer::Analyzer::findCastMutation,
 210        &ExprMutationAnalyzer::Analyzer::findRangeLoopMutation,
 211        &ExprMutationAnalyzer::Analyzer::findReferenceMutation,
 212        &ExprMutationAnalyzer::Analyzer::findFunctionArgMutation},
 213       Memorized.Results);
 214 }
 215
 216 const Stmt *ExprMutationAnalyzer::Analyzer::findMutation(const Decl *Dec) {
 217   return tryEachDeclRef(Dec, &ExprMutationAnalyzer::Analyzer::findMutation);
 218 }
 219
 220 const Stmt *
 221 ExprMutationAnalyzer::Analyzer::findPointeeMutation(const Expr *Exp) {
 222   return findMutationMemoized(Exp, {/*TODO*/}, Memorized.PointeeResults);
 223 }
 224
 225 const Stmt *
 226 ExprMutationAnalyzer::Analyzer::findPointeeMutation(const Decl *Dec) {
 227   return tryEachDeclRef(Dec,
 228                         &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
 229 }
 230
 231 const Stmt *ExprMutationAnalyzer::Analyzer::findMutationMemoized(
 232     const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,
 233     Memoized::ResultMap &MemoizedResults) {
 234   // Assume Exp is not mutated before analyzing Exp.
 235   auto [Memoized, Inserted] = MemoizedResults.try_emplace(Exp);
 236   if (!Inserted)
 237     return Memoized->second;
 238
 239   if (ExprMutationAnalyzer::isUnevaluated(Exp, Context))
 240     return nullptr;
 241
 242   for (const auto &Finder : Finders) {
 243     if (const Stmt *S = (this->*Finder)(Exp))
 244       return MemoizedResults[Exp] = S;
 245   }
 246
 247   return nullptr;
 248 }
 249
 250 const Stmt *
 251 ExprMutationAnalyzer::Analyzer::tryEachDeclRef(const Decl *Dec,
 252                                                MutationFinder Finder) {
 253   const auto Refs = match(
 254       findAll(
 255           declRefExpr(to(
 256                           // `Dec` or a binding if `Dec` is a decomposition.
 257                           anyOf(equalsNode(Dec),
 258                                 bindingDecl(forDecomposition(equalsNode(Dec))))
 259                           //
 260                           ))
 261               .bind(NodeID<Expr>::value)),
 262       Stm, Context);
 263   for (const auto &RefNodes : Refs) {
 264     const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
 265     if ((this->*Finder)(E))
 266       return E;
 267   }
 268   return nullptr;
 269 }
 270
 271 bool ExprMutationAnalyzer::isUnevaluated(const Stmt *Stm, ASTContext &Context) {
 272   return !match(stmt(anyOf(
 273                     // `Exp` is part of the underlying expression of
 274                     // decltype/typeof if it has an ancestor of
 275                     // typeLoc.
 276                     hasAncestor(typeLoc(
 277                         unless(hasAncestor(unaryExprOrTypeTraitExpr())))),
 278                     hasAncestor(expr(anyOf(
 279                         // `UnaryExprOrTypeTraitExpr` is unevaluated
 280                         // unless it's sizeof on VLA.
 281                         unaryExprOrTypeTraitExpr(unless(sizeOfExpr(
 282                             hasArgumentOfType(variableArrayType())))),
 283                         // `CXXTypeidExpr` is unevaluated unless it's
 284                         // applied to an expression of glvalue of
 285                         // polymorphic class type.
 286                         cxxTypeidExpr(unless(isPotentiallyEvaluated())),
 287                         // The controlling expression of
 288                         // `GenericSelectionExpr` is unevaluated.
 289                         genericSelectionExpr(
 290                             hasControllingExpr(hasDescendant(equalsNode(Stm)))),
 291                         cxxNoexceptExpr()))))),
 292                 *Stm, Context)
 293               .empty();
 294 }
 295
 296 const Stmt *
 297 ExprMutationAnalyzer::Analyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
 298   return tryEachMatch<Expr>(Matches, this,
 299                             &ExprMutationAnalyzer::Analyzer::findMutation);
 300 }
 301
 302 const Stmt *
 303 ExprMutationAnalyzer::Analyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
 304   return tryEachMatch<Decl>(Matches, this,
 305                             &ExprMutationAnalyzer::Analyzer::findMutation);
 306 }
 307
 308 const Stmt *ExprMutationAnalyzer::Analyzer::findExprPointeeMutation(
 309     ArrayRef<ast_matchers::BoundNodes> Matches) {
 310   return tryEachMatch<Expr>(
 311       Matches, this, &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
 312 }
 313
 314 const Stmt *ExprMutationAnalyzer::Analyzer::findDeclPointeeMutation(
 315     ArrayRef<ast_matchers::BoundNodes> Matches) {
 316   return tryEachMatch<Decl>(
 317       Matches, this, &ExprMutationAnalyzer::Analyzer::findPointeeMutation);
 318 }
 319
 320 const Stmt *
 321 ExprMutationAnalyzer::Analyzer::findDirectMutation(const Expr *Exp) {
 322   // LHS of any assignment operators.
 323   const auto AsAssignmentLhs =
 324       binaryOperator(isAssignmentOperator(), hasLHS(canResolveToExpr(Exp)));
 325
 326   // Operand of increment/decrement operators.
 327   const auto AsIncDecOperand =
 328       unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
 329                     hasUnaryOperand(canResolveToExpr(Exp)));
 330
 331   // Invoking non-const member function.
 332   // A member function is assumed to be non-const when it is unresolved.
 333   const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
 334
 335   const auto AsNonConstThis = expr(anyOf(
 336       cxxMemberCallExpr(on(canResolveToExpr(Exp)), unless(isConstCallee())),
 337       cxxOperatorCallExpr(callee(NonConstMethod),
 338                           hasArgument(0, canResolveToExpr(Exp))),
 339       // In case of a templated type, calling overloaded operators is not
 340       // resolved and modelled as `binaryOperator` on a dependent type.
 341       // Such instances are considered a modification, because they can modify
 342       // in different instantiations of the template.
 343       binaryOperator(isTypeDependent(),
 344                      hasEitherOperand(ignoringImpCasts(canResolveToExpr(Exp)))),
 345       // A fold expression may contain `Exp` as it's initializer.
 346       // We don't know if the operator modifies `Exp` because the
 347       // operator is type dependent due to the parameter pack.
 348       cxxFoldExpr(hasFoldInit(ignoringImpCasts(canResolveToExpr(Exp)))),
 349       // Within class templates and member functions the member expression might
 350       // not be resolved. In that case, the `callExpr` is considered to be a
 351       // modification.
 352       callExpr(callee(expr(anyOf(
 353           unresolvedMemberExpr(hasObjectExpression(canResolveToExpr(Exp))),
 354           cxxDependentScopeMemberExpr(
 355               hasObjectExpression(canResolveToExpr(Exp))))))),
 356       // Match on a call to a known method, but the call itself is type
 357       // dependent (e.g. `vector<T> v; v.push(T{});` in a templated function).
 358       callExpr(allOf(
 359           isTypeDependent(),
 360           callee(memberExpr(hasDeclaration(NonConstMethod),
 361                             hasObjectExpression(canResolveToExpr(Exp))))))));
 362
 363   // Taking address of 'Exp'.
 364   // We're assuming 'Exp' is mutated as soon as its address is taken, though in
 365   // theory we can follow the pointer and see whether it escaped `Stm` or is
 366   // dereferenced and then mutated. This is left for future improvements.
 367   const auto AsAmpersandOperand =
 368       unaryOperator(hasOperatorName("&"),
 369                     // A NoOp implicit cast is adding const.
 370                     unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
 371                     hasUnaryOperand(canResolveToExpr(Exp)));
 372   const auto AsPointerFromArrayDecay = castExpr(
 373       hasCastKind(CK_ArrayToPointerDecay),
 374       unless(hasParent(arraySubscriptExpr())), has(canResolveToExpr(Exp)));
 375   // Treat calling `operator->()` of move-only classes as taking address.
 376   // These are typically smart pointers with unique ownership so we treat
 377   // mutation of pointee as mutation of the smart pointer itself.
 378   const auto AsOperatorArrowThis = cxxOperatorCallExpr(
 379       hasOverloadedOperatorName("->"),
 380       callee(
 381           cxxMethodDecl(ofClass(isMoveOnly()), returns(nonConstPointerType()))),
 382       argumentCountIs(1), hasArgument(0, canResolveToExpr(Exp)));
 383
 384   // Used as non-const-ref argument when calling a function.
 385   // An argument is assumed to be non-const-ref when the function is unresolved.
 386   // Instantiated template functions are not handled here but in
 387   // findFunctionArgMutation which has additional smarts for handling forwarding
 388   // references.
 389   const auto NonConstRefParam = forEachArgumentWithParamType(
 390       anyOf(canResolveToExpr(Exp),
 391             memberExpr(hasObjectExpression(canResolveToExpr(Exp)))),
 392       nonConstReferenceType());
 393   const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
 394
 395   const auto AsNonConstRefArg =
 396       anyOf(callExpr(NonConstRefParam, NotInstantiated),
 397             cxxConstructExpr(NonConstRefParam, NotInstantiated),
 398             // If the call is type-dependent, we can't properly process any
 399             // argument because required type conversions and implicit casts
 400             // will be inserted only after specialization.
 401             callExpr(isTypeDependent(), hasAnyArgument(canResolveToExpr(Exp))),
 402             cxxUnresolvedConstructExpr(hasAnyArgument(canResolveToExpr(Exp))),
 403             // Previous False Positive in the following Code:
 404             // `template <typename T> void f() { int i = 42; new Type<T>(i); }`
 405             // Where the constructor of `Type` takes its argument as reference.
 406             // The AST does not resolve in a `cxxConstructExpr` because it is
 407             // type-dependent.
 408             parenListExpr(hasDescendant(expr(canResolveToExpr(Exp)))),
 409             // If the initializer is for a reference type, there is no cast for
 410             // the variable. Values are cast to RValue first.
 411             initListExpr(hasAnyInit(expr(canResolveToExpr(Exp)))));
 412
 413   // Captured by a lambda by reference.
 414   // If we're initializing a capture with 'Exp' directly then we're initializing
 415   // a reference capture.
 416   // For value captures there will be an ImplicitCastExpr <LValueToRValue>.
 417   const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp));
 418
 419   // Returned as non-const-ref.
 420   // If we're returning 'Exp' directly then it's returned as non-const-ref.
 421   // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
 422   // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
 423   // adding const.)
 424   const auto AsNonConstRefReturn =
 425       returnStmt(hasReturnValue(canResolveToExpr(Exp)));
 426
 427   // It is used as a non-const-reference for initializing a range-for loop.
 428   const auto AsNonConstRefRangeInit = cxxForRangeStmt(hasRangeInit(declRefExpr(
 429       allOf(canResolveToExpr(Exp), hasType(nonConstReferenceType())))));
 430
 431   const auto Matches = match(
 432       traverse(
 433           TK_AsIs,
 434           findFirst(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
 435                                AsAmpersandOperand, AsPointerFromArrayDecay,
 436                                AsOperatorArrowThis, AsNonConstRefArg,
 437                                AsLambdaRefCaptureInit, AsNonConstRefReturn,
 438                                AsNonConstRefRangeInit))
 439                         .bind("stmt"))),
 440       Stm, Context);
 441   return selectFirst<Stmt>("stmt", Matches);
 442 }
 443
 444 const Stmt *
 445 ExprMutationAnalyzer::Analyzer::findMemberMutation(const Expr *Exp) {
 446   // Check whether any member of 'Exp' is mutated.
 447   const auto MemberExprs = match(
 448       findAll(expr(anyOf(memberExpr(hasObjectExpression(canResolveToExpr(Exp))),
 449                          cxxDependentScopeMemberExpr(
 450                              hasObjectExpression(canResolveToExpr(Exp))),
 451                          binaryOperator(hasOperatorName(".*"),
 452                                         hasLHS(equalsNode(Exp)))))
 453                   .bind(NodeID<Expr>::value)),
 454       Stm, Context);
 455   return findExprMutation(MemberExprs);
 456 }
 457
 458 const Stmt *
 459 ExprMutationAnalyzer::Analyzer::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
 472 const Stmt *ExprMutationAnalyzer::Analyzer::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
 507 const Stmt *
 508 ExprMutationAnalyzer::Analyzer::findRangeLoopMutation(const Expr *Exp) {
 509   // Keep the ordering for the specific initialization matches to happen first,
 510   // because it is cheaper to match all potential modifications of the loop
 511   // variable.
 512
 513   // The range variable is a reference to a builtin array. In that case the
 514   // array is considered modified if the loop-variable is a non-const reference.
 515   const auto DeclStmtToNonRefToArray = declStmt(hasSingleDecl(varDecl(hasType(
 516       hasUnqualifiedDesugaredType(referenceType(pointee(arrayType())))))));
 517   const auto RefToArrayRefToElements = match(
 518       findFirst(stmt(cxxForRangeStmt(
 519                          hasLoopVariable(
 520                              varDecl(anyOf(hasType(nonConstReferenceType()),
 521                                            hasType(nonConstPointerType())))
 522                                  .bind(NodeID<Decl>::value)),
 523                          hasRangeStmt(DeclStmtToNonRefToArray),
 524                          hasRangeInit(canResolveToExpr(Exp))))
 525                     .bind("stmt")),
 526       Stm, Context);
 527
 528   if (const auto *BadRangeInitFromArray =
 529           selectFirst<Stmt>("stmt", RefToArrayRefToElements))
 530     return BadRangeInitFromArray;
 531
 532   // Small helper to match special cases in range-for loops.
 533   //
 534   // It is possible that containers do not provide a const-overload for their
 535   // iterator accessors. If this is the case, the variable is used non-const
 536   // no matter what happens in the loop. This requires special detection as it
 537   // is then faster to find all mutations of the loop variable.
 538   // It aims at a different modification as well.
 539   const auto HasAnyNonConstIterator =
 540       anyOf(allOf(hasMethod(allOf(hasName("begin"), unless(isConst()))),
 541                   unless(hasMethod(allOf(hasName("begin"), isConst())))),
 542             allOf(hasMethod(allOf(hasName("end"), unless(isConst()))),
 543                   unless(hasMethod(allOf(hasName("end"), isConst())))));
 544
 545   const auto DeclStmtToNonConstIteratorContainer = declStmt(
 546       hasSingleDecl(varDecl(hasType(hasUnqualifiedDesugaredType(referenceType(
 547           pointee(hasDeclaration(cxxRecordDecl(HasAnyNonConstIterator)))))))));
 548
 549   const auto RefToContainerBadIterators = match(
 550       findFirst(stmt(cxxForRangeStmt(allOf(
 551                          hasRangeStmt(DeclStmtToNonConstIteratorContainer),
 552                          hasRangeInit(canResolveToExpr(Exp)))))
 553                     .bind("stmt")),
 554       Stm, Context);
 555
 556   if (const auto *BadIteratorsContainer =
 557           selectFirst<Stmt>("stmt", RefToContainerBadIterators))
 558     return BadIteratorsContainer;
 559
 560   // If range for looping over 'Exp' with a non-const reference loop variable,
 561   // check all declRefExpr of the loop variable.
 562   const auto LoopVars =
 563       match(findAll(cxxForRangeStmt(
 564                 hasLoopVariable(varDecl(hasType(nonConstReferenceType()))
 565                                     .bind(NodeID<Decl>::value)),
 566                 hasRangeInit(canResolveToExpr(Exp)))),
 567             Stm, Context);
 568   return findDeclMutation(LoopVars);
 569 }
 570
 571 const Stmt *
 572 ExprMutationAnalyzer::Analyzer::findReferenceMutation(const Expr *Exp) {
 573   // Follow non-const reference returned by `operator*()` of move-only classes.
 574   // These are typically smart pointers with unique ownership so we treat
 575   // mutation of pointee as mutation of the smart pointer itself.
 576   const auto Ref = match(
 577       findAll(cxxOperatorCallExpr(
 578                   hasOverloadedOperatorName("*"),
 579                   callee(cxxMethodDecl(ofClass(isMoveOnly()),
 580                                        returns(nonConstReferenceType()))),
 581                   argumentCountIs(1), hasArgument(0, canResolveToExpr(Exp)))
 582                   .bind(NodeID<Expr>::value)),
 583       Stm, Context);
 584   if (const Stmt *S = findExprMutation(Ref))
 585     return S;
 586
 587   // If 'Exp' is bound to a non-const reference, check all declRefExpr to that.
 588   const auto Refs = match(
 589       stmt(forEachDescendant(
 590           varDecl(hasType(nonConstReferenceType()),
 591                   hasInitializer(anyOf(
 592                       canResolveToExpr(Exp),
 593                       memberExpr(hasObjectExpression(canResolveToExpr(Exp))))),
 594                   hasParent(declStmt().bind("stmt")),
 595                   // Don't follow the reference in range statement, we've
 596                   // handled that separately.
 597                   unless(hasParent(declStmt(hasParent(cxxForRangeStmt(
 598                       hasRangeStmt(equalsBoundNode("stmt"))))))))
 599               .bind(NodeID<Decl>::value))),
 600       Stm, Context);
 601   return findDeclMutation(Refs);
 602 }
 603
 604 const Stmt *
 605 ExprMutationAnalyzer::Analyzer::findFunctionArgMutation(const Expr *Exp) {
 606   const auto NonConstRefParam = forEachArgumentWithParam(
 607       canResolveToExpr(Exp),
 608       parmVarDecl(hasType(nonConstReferenceType())).bind("parm"));
 609   const auto IsInstantiated = hasDeclaration(isInstantiated());
 610   const auto FuncDecl = hasDeclaration(functionDecl().bind("func"));
 611   const auto Matches = match(
 612       traverse(
 613           TK_AsIs,
 614           findAll(
 615               expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl,
 616                                   unless(callee(namedDecl(hasAnyName(
 617                                       "::std::move", "::std::forward"))))),
 618                          cxxConstructExpr(NonConstRefParam, IsInstantiated,
 619                                           FuncDecl)))
 620                   .bind(NodeID<Expr>::value))),
 621       Stm, Context);
 622   for (const auto &Nodes : Matches) {
 623     const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
 624     const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
 625     if (!Func->getBody() || !Func->getPrimaryTemplate())
 626       return Exp;
 627
 628     const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
 629     const ArrayRef<ParmVarDecl *> AllParams =
 630         Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
 631     QualType ParmType =
 632         AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
 633                                    AllParams.size() - 1)]
 634             ->getType();
 635     if (const auto *T = ParmType->getAs<PackExpansionType>())
 636       ParmType = T->getPattern();
 637
 638     // If param type is forwarding reference, follow into the function
 639     // definition and see whether the param is mutated inside.
 640     if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
 641       if (!RefType->getPointeeType().getQualifiers() &&
 642           RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
 643         FunctionParmMutationAnalyzer *Analyzer =
 644             FunctionParmMutationAnalyzer::getFunctionParmMutationAnalyzer(
 645                 *Func, Context, Memorized);
 646         if (Analyzer->findMutation(Parm))
 647           return Exp;
 648         continue;
 649       }
 650     }
 651     // Not forwarding reference.
 652     return Exp;
 653   }
 654   return nullptr;
 655 }
 656
 657 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
 658     const FunctionDecl &Func, ASTContext &Context,
 659     ExprMutationAnalyzer::Memoized &Memorized)
 660     : BodyAnalyzer(*Func.getBody(), Context, Memorized) {
 661   if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
 662     // CXXCtorInitializer might also mutate Param but they're not part of
 663     // function body, check them eagerly here since they're typically trivial.
 664     for (const CXXCtorInitializer *Init : Ctor->inits()) {
 665       ExprMutationAnalyzer::Analyzer InitAnalyzer(*Init->getInit(), Context,
 666                                                   Memorized);
 667       for (const ParmVarDecl *Parm : Ctor->parameters()) {
 668         if (Results.contains(Parm))
 669           continue;
 670         if (const Stmt *S = InitAnalyzer.findMutation(Parm))
 671           Results[Parm] = S;
 672       }
 673     }
 674   }
 675 }
 676
 677 const Stmt *
 678 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
 679   const auto Memoized = Results.find(Parm);
 680   if (Memoized != Results.end())
 681     return Memoized->second;
 682   // To handle call A -> call B -> call A. Assume parameters of A is not mutated
 683   // before analyzing parameters of A. Then when analyzing the second "call A",
 684   // FunctionParmMutationAnalyzer can use this memoized value to avoid infinite
 685   // recursion.
 686   Results[Parm] = nullptr;
 687   if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
 688     return Results[Parm] = S;
 689   return Results[Parm];
 690 }
 691
 692 } // namespace clang