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