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