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/ASTMatchers/ASTMatchFinder.h" 10 #include "llvm/ADT/STLExtras.h" 11 12 namespace clang { 13 using namespace ast_matchers; 14 15 namespace { 16 17 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) { 18 return llvm::is_contained(Node.capture_inits(), E); 19 } 20 21 AST_MATCHER_P(CXXForRangeStmt, hasRangeStmt, 22 ast_matchers::internal::Matcher<DeclStmt>, InnerMatcher) { 23 const DeclStmt *const Range = Node.getRangeStmt(); 24 return InnerMatcher.matches(*Range, Finder, Builder); 25 } 26 27 AST_MATCHER_P(Expr, maybeEvalCommaExpr, 28 ast_matchers::internal::Matcher<Expr>, InnerMatcher) { 29 const Expr* Result = &Node; 30 while (const auto *BOComma = 31 dyn_cast_or_null<BinaryOperator>(Result->IgnoreParens())) { 32 if (!BOComma->isCommaOp()) 33 break; 34 Result = BOComma->getRHS(); 35 } 36 return InnerMatcher.matches(*Result, Finder, Builder); 37 } 38 39 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr> 40 cxxTypeidExpr; 41 42 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) { 43 return Node.isPotentiallyEvaluated(); 44 } 45 46 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr> 47 cxxNoexceptExpr; 48 49 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, 50 GenericSelectionExpr> 51 genericSelectionExpr; 52 53 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr, 54 ast_matchers::internal::Matcher<Expr>, InnerMatcher) { 55 return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder); 56 } 57 58 const auto nonConstReferenceType = [] { 59 return hasUnqualifiedDesugaredType( 60 referenceType(pointee(unless(isConstQualified())))); 61 }; 62 63 const auto nonConstPointerType = [] { 64 return hasUnqualifiedDesugaredType( 65 pointerType(pointee(unless(isConstQualified())))); 66 }; 67 68 const auto isMoveOnly = [] { 69 return cxxRecordDecl( 70 hasMethod(cxxConstructorDecl(isMoveConstructor(), unless(isDeleted()))), 71 hasMethod(cxxMethodDecl(isMoveAssignmentOperator(), unless(isDeleted()))), 72 unless(anyOf(hasMethod(cxxConstructorDecl(isCopyConstructor(), 73 unless(isDeleted()))), 74 hasMethod(cxxMethodDecl(isCopyAssignmentOperator(), 75 unless(isDeleted())))))); 76 }; 77 78 template <class T> struct NodeID; 79 template <> struct NodeID<Expr> { static const std::string value; }; 80 template <> struct NodeID<Decl> { static const std::string value; }; 81 const std::string NodeID<Expr>::value = "expr"; 82 const std::string NodeID<Decl>::value = "decl"; 83 84 template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)> 85 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches, 86 ExprMutationAnalyzer *Analyzer, F Finder) { 87 const StringRef ID = NodeID<T>::value; 88 for (const auto &Nodes : Matches) { 89 if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID))) 90 return S; 91 } 92 return nullptr; 93 } 94 95 } // namespace 96 97 const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) { 98 return findMutationMemoized(Exp, 99 {&ExprMutationAnalyzer::findDirectMutation, 100 &ExprMutationAnalyzer::findMemberMutation, 101 &ExprMutationAnalyzer::findArrayElementMutation, 102 &ExprMutationAnalyzer::findCastMutation, 103 &ExprMutationAnalyzer::findRangeLoopMutation, 104 &ExprMutationAnalyzer::findReferenceMutation, 105 &ExprMutationAnalyzer::findFunctionArgMutation}, 106 Results); 107 } 108 109 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) { 110 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation); 111 } 112 113 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) { 114 return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults); 115 } 116 117 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) { 118 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation); 119 } 120 121 const Stmt *ExprMutationAnalyzer::findMutationMemoized( 122 const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders, 123 ResultMap &MemoizedResults) { 124 const auto Memoized = MemoizedResults.find(Exp); 125 if (Memoized != MemoizedResults.end()) 126 return Memoized->second; 127 128 if (isUnevaluated(Exp)) 129 return MemoizedResults[Exp] = nullptr; 130 131 for (const auto &Finder : Finders) { 132 if (const Stmt *S = (this->*Finder)(Exp)) 133 return MemoizedResults[Exp] = S; 134 } 135 136 return MemoizedResults[Exp] = nullptr; 137 } 138 139 const Stmt *ExprMutationAnalyzer::tryEachDeclRef(const Decl *Dec, 140 MutationFinder Finder) { 141 const auto Refs = 142 match(findAll(declRefExpr(to(equalsNode(Dec))).bind(NodeID<Expr>::value)), 143 Stm, Context); 144 for (const auto &RefNodes : Refs) { 145 const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value); 146 if ((this->*Finder)(E)) 147 return E; 148 } 149 return nullptr; 150 } 151 152 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) { 153 return selectFirst<Expr>( 154 NodeID<Expr>::value, 155 match( 156 findAll( 157 expr(equalsNode(Exp), 158 anyOf( 159 // `Exp` is part of the underlying expression of 160 // decltype/typeof if it has an ancestor of 161 // typeLoc. 162 hasAncestor(typeLoc(unless( 163 hasAncestor(unaryExprOrTypeTraitExpr())))), 164 hasAncestor(expr(anyOf( 165 // `UnaryExprOrTypeTraitExpr` is unevaluated 166 // unless it's sizeof on VLA. 167 unaryExprOrTypeTraitExpr(unless(sizeOfExpr( 168 hasArgumentOfType(variableArrayType())))), 169 // `CXXTypeidExpr` is unevaluated unless it's 170 // applied to an expression of glvalue of 171 // polymorphic class type. 172 cxxTypeidExpr( 173 unless(isPotentiallyEvaluated())), 174 // The controlling expression of 175 // `GenericSelectionExpr` is unevaluated. 176 genericSelectionExpr(hasControllingExpr( 177 hasDescendant(equalsNode(Exp)))), 178 cxxNoexceptExpr()))))) 179 .bind(NodeID<Expr>::value)), 180 Stm, Context)) != nullptr; 181 } 182 183 const Stmt * 184 ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) { 185 return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation); 186 } 187 188 const Stmt * 189 ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) { 190 return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation); 191 } 192 193 const Stmt *ExprMutationAnalyzer::findExprPointeeMutation( 194 ArrayRef<ast_matchers::BoundNodes> Matches) { 195 return tryEachMatch<Expr>(Matches, this, 196 &ExprMutationAnalyzer::findPointeeMutation); 197 } 198 199 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation( 200 ArrayRef<ast_matchers::BoundNodes> Matches) { 201 return tryEachMatch<Decl>(Matches, this, 202 &ExprMutationAnalyzer::findPointeeMutation); 203 } 204 205 const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) { 206 // LHS of any assignment operators. 207 const auto AsAssignmentLhs = 208 binaryOperator(isAssignmentOperator(), 209 hasLHS(maybeEvalCommaExpr(equalsNode(Exp)))); 210 211 // Operand of increment/decrement operators. 212 const auto AsIncDecOperand = 213 unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")), 214 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp)))); 215 216 // Invoking non-const member function. 217 // A member function is assumed to be non-const when it is unresolved. 218 const auto NonConstMethod = cxxMethodDecl(unless(isConst())); 219 const auto AsNonConstThis = 220 expr(anyOf(cxxMemberCallExpr(callee(NonConstMethod), 221 on(maybeEvalCommaExpr(equalsNode(Exp)))), 222 cxxOperatorCallExpr(callee(NonConstMethod), 223 hasArgument(0, 224 maybeEvalCommaExpr(equalsNode(Exp)))), 225 callExpr(callee(expr(anyOf( 226 unresolvedMemberExpr( 227 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp)))), 228 cxxDependentScopeMemberExpr( 229 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp)))))))))); 230 231 // Taking address of 'Exp'. 232 // We're assuming 'Exp' is mutated as soon as its address is taken, though in 233 // theory we can follow the pointer and see whether it escaped `Stm` or is 234 // dereferenced and then mutated. This is left for future improvements. 235 const auto AsAmpersandOperand = 236 unaryOperator(hasOperatorName("&"), 237 // A NoOp implicit cast is adding const. 238 unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))), 239 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp)))); 240 const auto AsPointerFromArrayDecay = 241 castExpr(hasCastKind(CK_ArrayToPointerDecay), 242 unless(hasParent(arraySubscriptExpr())), 243 has(maybeEvalCommaExpr(equalsNode(Exp)))); 244 // Treat calling `operator->()` of move-only classes as taking address. 245 // These are typically smart pointers with unique ownership so we treat 246 // mutation of pointee as mutation of the smart pointer itself. 247 const auto AsOperatorArrowThis = 248 cxxOperatorCallExpr(hasOverloadedOperatorName("->"), 249 callee(cxxMethodDecl(ofClass(isMoveOnly()), 250 returns(nonConstPointerType()))), 251 argumentCountIs(1), 252 hasArgument(0, maybeEvalCommaExpr(equalsNode(Exp)))); 253 254 // Used as non-const-ref argument when calling a function. 255 // An argument is assumed to be non-const-ref when the function is unresolved. 256 // Instantiated template functions are not handled here but in 257 // findFunctionArgMutation which has additional smarts for handling forwarding 258 // references. 259 const auto NonConstRefParam = forEachArgumentWithParam( 260 maybeEvalCommaExpr(equalsNode(Exp)), 261 parmVarDecl(hasType(nonConstReferenceType()))); 262 const auto NotInstantiated = unless(hasDeclaration(isInstantiated())); 263 const auto AsNonConstRefArg = anyOf( 264 callExpr(NonConstRefParam, NotInstantiated), 265 cxxConstructExpr(NonConstRefParam, NotInstantiated), 266 callExpr(callee(expr(anyOf(unresolvedLookupExpr(), unresolvedMemberExpr(), 267 cxxDependentScopeMemberExpr(), 268 hasType(templateTypeParmType())))), 269 hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp)))), 270 cxxUnresolvedConstructExpr(hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp))))); 271 272 // Captured by a lambda by reference. 273 // If we're initializing a capture with 'Exp' directly then we're initializing 274 // a reference capture. 275 // For value captures there will be an ImplicitCastExpr <LValueToRValue>. 276 const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp)); 277 278 // Returned as non-const-ref. 279 // If we're returning 'Exp' directly then it's returned as non-const-ref. 280 // For returning by value there will be an ImplicitCastExpr <LValueToRValue>. 281 // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for 282 // adding const.) 283 const auto AsNonConstRefReturn = returnStmt(hasReturnValue( 284 maybeEvalCommaExpr(equalsNode(Exp)))); 285 286 const auto Matches = 287 match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis, 288 AsAmpersandOperand, AsPointerFromArrayDecay, 289 AsOperatorArrowThis, AsNonConstRefArg, 290 AsLambdaRefCaptureInit, AsNonConstRefReturn)) 291 .bind("stmt")), 292 Stm, Context); 293 return selectFirst<Stmt>("stmt", Matches); 294 } 295 296 const Stmt *ExprMutationAnalyzer::findMemberMutation(const Expr *Exp) { 297 // Check whether any member of 'Exp' is mutated. 298 const auto MemberExprs = 299 match(findAll(expr(anyOf(memberExpr(hasObjectExpression(equalsNode(Exp))), 300 cxxDependentScopeMemberExpr( 301 hasObjectExpression(equalsNode(Exp))))) 302 .bind(NodeID<Expr>::value)), 303 Stm, Context); 304 return findExprMutation(MemberExprs); 305 } 306 307 const Stmt *ExprMutationAnalyzer::findArrayElementMutation(const Expr *Exp) { 308 // Check whether any element of an array is mutated. 309 const auto SubscriptExprs = match( 310 findAll(arraySubscriptExpr(hasBase(ignoringImpCasts(equalsNode(Exp)))) 311 .bind(NodeID<Expr>::value)), 312 Stm, Context); 313 return findExprMutation(SubscriptExprs); 314 } 315 316 const Stmt *ExprMutationAnalyzer::findCastMutation(const Expr *Exp) { 317 // If 'Exp' is casted to any non-const reference type, check the castExpr. 318 const auto Casts = 319 match(findAll(castExpr(hasSourceExpression(equalsNode(Exp)), 320 anyOf(explicitCastExpr(hasDestinationType( 321 nonConstReferenceType())), 322 implicitCastExpr(hasImplicitDestinationType( 323 nonConstReferenceType())))) 324 .bind(NodeID<Expr>::value)), 325 Stm, Context); 326 if (const Stmt *S = findExprMutation(Casts)) 327 return S; 328 // Treat std::{move,forward} as cast. 329 const auto Calls = 330 match(findAll(callExpr(callee(namedDecl( 331 hasAnyName("::std::move", "::std::forward"))), 332 hasArgument(0, equalsNode(Exp))) 333 .bind("expr")), 334 Stm, Context); 335 return findExprMutation(Calls); 336 } 337 338 const Stmt *ExprMutationAnalyzer::findRangeLoopMutation(const Expr *Exp) { 339 // If range for looping over 'Exp' with a non-const reference loop variable, 340 // check all declRefExpr of the loop variable. 341 const auto LoopVars = 342 match(findAll(cxxForRangeStmt( 343 hasLoopVariable(varDecl(hasType(nonConstReferenceType())) 344 .bind(NodeID<Decl>::value)), 345 hasRangeInit(equalsNode(Exp)))), 346 Stm, Context); 347 return findDeclMutation(LoopVars); 348 } 349 350 const Stmt *ExprMutationAnalyzer::findReferenceMutation(const Expr *Exp) { 351 // Follow non-const reference returned by `operator*()` of move-only classes. 352 // These are typically smart pointers with unique ownership so we treat 353 // mutation of pointee as mutation of the smart pointer itself. 354 const auto Ref = 355 match(findAll(cxxOperatorCallExpr( 356 hasOverloadedOperatorName("*"), 357 callee(cxxMethodDecl(ofClass(isMoveOnly()), 358 returns(nonConstReferenceType()))), 359 argumentCountIs(1), hasArgument(0, equalsNode(Exp))) 360 .bind(NodeID<Expr>::value)), 361 Stm, Context); 362 if (const Stmt *S = findExprMutation(Ref)) 363 return S; 364 365 // If 'Exp' is bound to a non-const reference, check all declRefExpr to that. 366 const auto Refs = match( 367 stmt(forEachDescendant( 368 varDecl( 369 hasType(nonConstReferenceType()), 370 hasInitializer(anyOf(equalsNode(Exp), 371 conditionalOperator(anyOf( 372 hasTrueExpression(equalsNode(Exp)), 373 hasFalseExpression(equalsNode(Exp)))))), 374 hasParent(declStmt().bind("stmt")), 375 // Don't follow the reference in range statement, we've handled 376 // that separately. 377 unless(hasParent(declStmt(hasParent( 378 cxxForRangeStmt(hasRangeStmt(equalsBoundNode("stmt")))))))) 379 .bind(NodeID<Decl>::value))), 380 Stm, Context); 381 return findDeclMutation(Refs); 382 } 383 384 const Stmt *ExprMutationAnalyzer::findFunctionArgMutation(const Expr *Exp) { 385 const auto NonConstRefParam = forEachArgumentWithParam( 386 equalsNode(Exp), 387 parmVarDecl(hasType(nonConstReferenceType())).bind("parm")); 388 const auto IsInstantiated = hasDeclaration(isInstantiated()); 389 const auto FuncDecl = hasDeclaration(functionDecl().bind("func")); 390 const auto Matches = match( 391 findAll(expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl, 392 unless(callee(namedDecl(hasAnyName( 393 "::std::move", "::std::forward"))))), 394 cxxConstructExpr(NonConstRefParam, IsInstantiated, 395 FuncDecl))) 396 .bind(NodeID<Expr>::value)), 397 Stm, Context); 398 for (const auto &Nodes : Matches) { 399 const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value); 400 const auto *Func = Nodes.getNodeAs<FunctionDecl>("func"); 401 if (!Func->getBody() || !Func->getPrimaryTemplate()) 402 return Exp; 403 404 const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm"); 405 const ArrayRef<ParmVarDecl *> AllParams = 406 Func->getPrimaryTemplate()->getTemplatedDecl()->parameters(); 407 QualType ParmType = 408 AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(), 409 AllParams.size() - 1)] 410 ->getType(); 411 if (const auto *T = ParmType->getAs<PackExpansionType>()) 412 ParmType = T->getPattern(); 413 414 // If param type is forwarding reference, follow into the function 415 // definition and see whether the param is mutated inside. 416 if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) { 417 if (!RefType->getPointeeType().getQualifiers() && 418 RefType->getPointeeType()->getAs<TemplateTypeParmType>()) { 419 std::unique_ptr<FunctionParmMutationAnalyzer> &Analyzer = 420 FuncParmAnalyzer[Func]; 421 if (!Analyzer) 422 Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context)); 423 if (Analyzer->findMutation(Parm)) 424 return Exp; 425 continue; 426 } 427 } 428 // Not forwarding reference. 429 return Exp; 430 } 431 return nullptr; 432 } 433 434 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer( 435 const FunctionDecl &Func, ASTContext &Context) 436 : BodyAnalyzer(*Func.getBody(), Context) { 437 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) { 438 // CXXCtorInitializer might also mutate Param but they're not part of 439 // function body, check them eagerly here since they're typically trivial. 440 for (const CXXCtorInitializer *Init : Ctor->inits()) { 441 ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context); 442 for (const ParmVarDecl *Parm : Ctor->parameters()) { 443 if (Results.find(Parm) != Results.end()) 444 continue; 445 if (const Stmt *S = InitAnalyzer.findMutation(Parm)) 446 Results[Parm] = S; 447 } 448 } 449 } 450 } 451 452 const Stmt * 453 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) { 454 const auto Memoized = Results.find(Parm); 455 if (Memoized != Results.end()) 456 return Memoized->second; 457 458 if (const Stmt *S = BodyAnalyzer.findMutation(Parm)) 459 return Results[Parm] = S; 460 461 return Results[Parm] = nullptr; 462 } 463 464 } // namespace clang 465