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