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