contrib/llvm/tools/clang/lib/Analysis/ExprMutationAnalyzer.cpp

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