contrib/llvm/tools/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/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