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