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