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