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