Clang Project

clang_source_code/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
12namespace clang {
13using namespace ast_matchers;
14
15namespace {
16
17AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
18  return llvm::is_contained(Node.capture_inits(), E);
19}
20
21AST_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
27AST_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
39const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
40    cxxTypeidExpr;
41
42AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
43  return Node.isPotentiallyEvaluated();
44}
45
46const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
47    cxxNoexceptExpr;
48
49const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt,
50                                                          GenericSelectionExpr>
51    genericSelectionExpr;
52
53AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
54              ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
55  return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
56}
57
58const auto nonConstReferenceType = [] {
59  return hasUnqualifiedDesugaredType(
60      referenceType(pointee(unless(isConstQualified()))));
61};
62
63const auto nonConstPointerType = [] {
64  return hasUnqualifiedDesugaredType(
65      pointerType(pointee(unless(isConstQualified()))));
66};
67
68const 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
78template <class T> struct NodeID;
79template <> struct NodeID<Expr> { static const std::string value; };
80template <> struct NodeID<Decl> { static const std::string value; };
81const std::string NodeID<Expr>::value = "expr";
82const std::string NodeID<Decl>::value = "decl";
83
84template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)>
85const 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
97const 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
109const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
110  return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
111}
112
113const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
114  return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
115}
116
117const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
118  return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
119}
120
121const 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
139const 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
152bool 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
183const Stmt *
184ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
185  return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation);
186}
187
188const Stmt *
189ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
190  return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation);
191}
192
193const Stmt *ExprMutationAnalyzer::findExprPointeeMutation(
194    ArrayRef<ast_matchers::BoundNodes> Matches) {
195  return tryEachMatch<Expr>(Matches, this,
196                            &ExprMutationAnalyzer::findPointeeMutation);
197}
198
199const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
200    ArrayRef<ast_matchers::BoundNodes> Matches) {
201  return tryEachMatch<Decl>(Matches, this,
202                            &ExprMutationAnalyzer::findPointeeMutation);
203}
204
205const 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
296const 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
307const 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
316const 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
338const 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
350const 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
384const 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
434FunctionParmMutationAnalyzer::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
452const Stmt *
453FunctionParmMutationAnalyzer::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
clang::ExprMutationAnalyzer::findMutation
clang::ExprMutationAnalyzer::findMutation
clang::ExprMutationAnalyzer::findPointeeMutation
clang::ExprMutationAnalyzer::findPointeeMutation
clang::ExprMutationAnalyzer::findMutationMemoized
clang::ExprMutationAnalyzer::tryEachDeclRef
clang::ExprMutationAnalyzer::isUnevaluated
clang::ExprMutationAnalyzer::findExprMutation
clang::ExprMutationAnalyzer::findDeclMutation
clang::ExprMutationAnalyzer::findExprPointeeMutation
clang::ExprMutationAnalyzer::findDeclPointeeMutation
clang::ExprMutationAnalyzer::findDirectMutation
clang::ExprMutationAnalyzer::findMemberMutation
clang::ExprMutationAnalyzer::findArrayElementMutation
clang::ExprMutationAnalyzer::findCastMutation
clang::ExprMutationAnalyzer::findRangeLoopMutation
clang::ExprMutationAnalyzer::findReferenceMutation
clang::ExprMutationAnalyzer::findFunctionArgMutation
clang::FunctionParmMutationAnalyzer::findMutation
CodeThinker, Enjoy your reading code