1 //===---------- ExprMutationAnalyzer.cpp ----------------------------------===//
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
7 //===----------------------------------------------------------------------===//
8 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
9 #include "clang/ASTMatchers/ASTMatchFinder.h"
10 #include "llvm/ADT/STLExtras.h"
13 using namespace ast_matchers;
17 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
18 return llvm::is_contained(Node.capture_inits(), E);
21 AST_MATCHER_P(CXXForRangeStmt, hasRangeStmt,
22 ast_matchers::internal::Matcher<DeclStmt>, InnerMatcher) {
23 const DeclStmt *const Range = Node.getRangeStmt();
24 return InnerMatcher.matches(*Range, Finder, Builder);
27 AST_MATCHER_P(Expr, maybeEvalCommaExpr,
28 ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
29 const Expr* Result = &Node;
30 while (const auto *BOComma =
31 dyn_cast_or_null<BinaryOperator>(Result->IgnoreParens())) {
32 if (!BOComma->isCommaOp())
34 Result = BOComma->getRHS();
36 return InnerMatcher.matches(*Result, Finder, Builder);
39 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
42 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
43 return Node.isPotentiallyEvaluated();
46 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
49 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt,
53 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
54 ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
55 return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
58 const auto nonConstReferenceType = [] {
59 return hasUnqualifiedDesugaredType(
60 referenceType(pointee(unless(isConstQualified()))));
63 const auto nonConstPointerType = [] {
64 return hasUnqualifiedDesugaredType(
65 pointerType(pointee(unless(isConstQualified()))));
68 const auto isMoveOnly = [] {
70 hasMethod(cxxConstructorDecl(isMoveConstructor(), unless(isDeleted()))),
71 hasMethod(cxxMethodDecl(isMoveAssignmentOperator(), unless(isDeleted()))),
72 unless(anyOf(hasMethod(cxxConstructorDecl(isCopyConstructor(),
73 unless(isDeleted()))),
74 hasMethod(cxxMethodDecl(isCopyAssignmentOperator(),
75 unless(isDeleted()))))));
78 template <class T> struct NodeID;
79 template <> struct NodeID<Expr> { static const std::string value; };
80 template <> struct NodeID<Decl> { static const std::string value; };
81 const std::string NodeID<Expr>::value = "expr";
82 const std::string NodeID<Decl>::value = "decl";
84 template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)>
85 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
86 ExprMutationAnalyzer *Analyzer, F Finder) {
87 const StringRef ID = NodeID<T>::value;
88 for (const auto &Nodes : Matches) {
89 if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
97 const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) {
98 return findMutationMemoized(Exp,
99 {&ExprMutationAnalyzer::findDirectMutation,
100 &ExprMutationAnalyzer::findMemberMutation,
101 &ExprMutationAnalyzer::findArrayElementMutation,
102 &ExprMutationAnalyzer::findCastMutation,
103 &ExprMutationAnalyzer::findRangeLoopMutation,
104 &ExprMutationAnalyzer::findReferenceMutation,
105 &ExprMutationAnalyzer::findFunctionArgMutation},
109 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
110 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
113 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
114 return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
117 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
118 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
121 const Stmt *ExprMutationAnalyzer::findMutationMemoized(
122 const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,
123 ResultMap &MemoizedResults) {
124 const auto Memoized = MemoizedResults.find(Exp);
125 if (Memoized != MemoizedResults.end())
126 return Memoized->second;
128 if (isUnevaluated(Exp))
129 return MemoizedResults[Exp] = nullptr;
131 for (const auto &Finder : Finders) {
132 if (const Stmt *S = (this->*Finder)(Exp))
133 return MemoizedResults[Exp] = S;
136 return MemoizedResults[Exp] = nullptr;
139 const Stmt *ExprMutationAnalyzer::tryEachDeclRef(const Decl *Dec,
140 MutationFinder Finder) {
142 match(findAll(declRefExpr(to(equalsNode(Dec))).bind(NodeID<Expr>::value)),
144 for (const auto &RefNodes : Refs) {
145 const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
146 if ((this->*Finder)(E))
152 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) {
153 return selectFirst<Expr>(
157 expr(equalsNode(Exp),
159 // `Exp` is part of the underlying expression of
160 // decltype/typeof if it has an ancestor of
162 hasAncestor(typeLoc(unless(
163 hasAncestor(unaryExprOrTypeTraitExpr())))),
164 hasAncestor(expr(anyOf(
165 // `UnaryExprOrTypeTraitExpr` is unevaluated
166 // unless it's sizeof on VLA.
167 unaryExprOrTypeTraitExpr(unless(sizeOfExpr(
168 hasArgumentOfType(variableArrayType())))),
169 // `CXXTypeidExpr` is unevaluated unless it's
170 // applied to an expression of glvalue of
171 // polymorphic class type.
173 unless(isPotentiallyEvaluated())),
174 // The controlling expression of
175 // `GenericSelectionExpr` is unevaluated.
176 genericSelectionExpr(hasControllingExpr(
177 hasDescendant(equalsNode(Exp)))),
178 cxxNoexceptExpr())))))
179 .bind(NodeID<Expr>::value)),
180 Stm, Context)) != nullptr;
184 ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
185 return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation);
189 ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
190 return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation);
193 const Stmt *ExprMutationAnalyzer::findExprPointeeMutation(
194 ArrayRef<ast_matchers::BoundNodes> Matches) {
195 return tryEachMatch<Expr>(Matches, this,
196 &ExprMutationAnalyzer::findPointeeMutation);
199 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
200 ArrayRef<ast_matchers::BoundNodes> Matches) {
201 return tryEachMatch<Decl>(Matches, this,
202 &ExprMutationAnalyzer::findPointeeMutation);
205 const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
206 // LHS of any assignment operators.
207 const auto AsAssignmentLhs =
208 binaryOperator(isAssignmentOperator(),
209 hasLHS(maybeEvalCommaExpr(equalsNode(Exp))));
211 // Operand of increment/decrement operators.
212 const auto AsIncDecOperand =
213 unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
214 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp))));
216 // Invoking non-const member function.
217 // A member function is assumed to be non-const when it is unresolved.
218 const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
219 const auto AsNonConstThis =
220 expr(anyOf(cxxMemberCallExpr(callee(NonConstMethod),
221 on(maybeEvalCommaExpr(equalsNode(Exp)))),
222 cxxOperatorCallExpr(callee(NonConstMethod),
224 maybeEvalCommaExpr(equalsNode(Exp)))),
225 callExpr(callee(expr(anyOf(
226 unresolvedMemberExpr(
227 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp)))),
228 cxxDependentScopeMemberExpr(
229 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp))))))))));
231 // Taking address of 'Exp'.
232 // We're assuming 'Exp' is mutated as soon as its address is taken, though in
233 // theory we can follow the pointer and see whether it escaped `Stm` or is
234 // dereferenced and then mutated. This is left for future improvements.
235 const auto AsAmpersandOperand =
236 unaryOperator(hasOperatorName("&"),
237 // A NoOp implicit cast is adding const.
238 unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
239 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp))));
240 const auto AsPointerFromArrayDecay =
241 castExpr(hasCastKind(CK_ArrayToPointerDecay),
242 unless(hasParent(arraySubscriptExpr())),
243 has(maybeEvalCommaExpr(equalsNode(Exp))));
244 // Treat calling `operator->()` of move-only classes as taking address.
245 // These are typically smart pointers with unique ownership so we treat
246 // mutation of pointee as mutation of the smart pointer itself.
247 const auto AsOperatorArrowThis =
248 cxxOperatorCallExpr(hasOverloadedOperatorName("->"),
249 callee(cxxMethodDecl(ofClass(isMoveOnly()),
250 returns(nonConstPointerType()))),
252 hasArgument(0, maybeEvalCommaExpr(equalsNode(Exp))));
254 // Used as non-const-ref argument when calling a function.
255 // An argument is assumed to be non-const-ref when the function is unresolved.
256 // Instantiated template functions are not handled here but in
257 // findFunctionArgMutation which has additional smarts for handling forwarding
259 const auto NonConstRefParam = forEachArgumentWithParam(
260 maybeEvalCommaExpr(equalsNode(Exp)),
261 parmVarDecl(hasType(nonConstReferenceType())));
262 const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
263 const auto AsNonConstRefArg = anyOf(
264 callExpr(NonConstRefParam, NotInstantiated),
265 cxxConstructExpr(NonConstRefParam, NotInstantiated),
266 callExpr(callee(expr(anyOf(unresolvedLookupExpr(), unresolvedMemberExpr(),
267 cxxDependentScopeMemberExpr(),
268 hasType(templateTypeParmType())))),
269 hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp)))),
270 cxxUnresolvedConstructExpr(hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp)))));
272 // Captured by a lambda by reference.
273 // If we're initializing a capture with 'Exp' directly then we're initializing
274 // a reference capture.
275 // For value captures there will be an ImplicitCastExpr <LValueToRValue>.
276 const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp));
278 // Returned as non-const-ref.
279 // If we're returning 'Exp' directly then it's returned as non-const-ref.
280 // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
281 // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
283 const auto AsNonConstRefReturn = returnStmt(hasReturnValue(
284 maybeEvalCommaExpr(equalsNode(Exp))));
287 match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
288 AsAmpersandOperand, AsPointerFromArrayDecay,
289 AsOperatorArrowThis, AsNonConstRefArg,
290 AsLambdaRefCaptureInit, AsNonConstRefReturn))
293 return selectFirst<Stmt>("stmt", Matches);
296 const Stmt *ExprMutationAnalyzer::findMemberMutation(const Expr *Exp) {
297 // Check whether any member of 'Exp' is mutated.
298 const auto MemberExprs =
299 match(findAll(expr(anyOf(memberExpr(hasObjectExpression(equalsNode(Exp))),
300 cxxDependentScopeMemberExpr(
301 hasObjectExpression(equalsNode(Exp)))))
302 .bind(NodeID<Expr>::value)),
304 return findExprMutation(MemberExprs);
307 const Stmt *ExprMutationAnalyzer::findArrayElementMutation(const Expr *Exp) {
308 // Check whether any element of an array is mutated.
309 const auto SubscriptExprs = match(
310 findAll(arraySubscriptExpr(hasBase(ignoringImpCasts(equalsNode(Exp))))
311 .bind(NodeID<Expr>::value)),
313 return findExprMutation(SubscriptExprs);
316 const Stmt *ExprMutationAnalyzer::findCastMutation(const Expr *Exp) {
317 // If 'Exp' is casted to any non-const reference type, check the castExpr.
319 match(findAll(castExpr(hasSourceExpression(equalsNode(Exp)),
320 anyOf(explicitCastExpr(hasDestinationType(
321 nonConstReferenceType())),
322 implicitCastExpr(hasImplicitDestinationType(
323 nonConstReferenceType()))))
324 .bind(NodeID<Expr>::value)),
326 if (const Stmt *S = findExprMutation(Casts))
328 // Treat std::{move,forward} as cast.
330 match(findAll(callExpr(callee(namedDecl(
331 hasAnyName("::std::move", "::std::forward"))),
332 hasArgument(0, equalsNode(Exp)))
335 return findExprMutation(Calls);
338 const Stmt *ExprMutationAnalyzer::findRangeLoopMutation(const Expr *Exp) {
339 // If range for looping over 'Exp' with a non-const reference loop variable,
340 // check all declRefExpr of the loop variable.
341 const auto LoopVars =
342 match(findAll(cxxForRangeStmt(
343 hasLoopVariable(varDecl(hasType(nonConstReferenceType()))
344 .bind(NodeID<Decl>::value)),
345 hasRangeInit(equalsNode(Exp)))),
347 return findDeclMutation(LoopVars);
350 const Stmt *ExprMutationAnalyzer::findReferenceMutation(const Expr *Exp) {
351 // Follow non-const reference returned by `operator*()` of move-only classes.
352 // These are typically smart pointers with unique ownership so we treat
353 // mutation of pointee as mutation of the smart pointer itself.
355 match(findAll(cxxOperatorCallExpr(
356 hasOverloadedOperatorName("*"),
357 callee(cxxMethodDecl(ofClass(isMoveOnly()),
358 returns(nonConstReferenceType()))),
359 argumentCountIs(1), hasArgument(0, equalsNode(Exp)))
360 .bind(NodeID<Expr>::value)),
362 if (const Stmt *S = findExprMutation(Ref))
365 // If 'Exp' is bound to a non-const reference, check all declRefExpr to that.
366 const auto Refs = match(
367 stmt(forEachDescendant(
369 hasType(nonConstReferenceType()),
370 hasInitializer(anyOf(equalsNode(Exp),
371 conditionalOperator(anyOf(
372 hasTrueExpression(equalsNode(Exp)),
373 hasFalseExpression(equalsNode(Exp)))))),
374 hasParent(declStmt().bind("stmt")),
375 // Don't follow the reference in range statement, we've handled
377 unless(hasParent(declStmt(hasParent(
378 cxxForRangeStmt(hasRangeStmt(equalsBoundNode("stmt"))))))))
379 .bind(NodeID<Decl>::value))),
381 return findDeclMutation(Refs);
384 const Stmt *ExprMutationAnalyzer::findFunctionArgMutation(const Expr *Exp) {
385 const auto NonConstRefParam = forEachArgumentWithParam(
387 parmVarDecl(hasType(nonConstReferenceType())).bind("parm"));
388 const auto IsInstantiated = hasDeclaration(isInstantiated());
389 const auto FuncDecl = hasDeclaration(functionDecl().bind("func"));
390 const auto Matches = match(
391 findAll(expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl,
392 unless(callee(namedDecl(hasAnyName(
393 "::std::move", "::std::forward"))))),
394 cxxConstructExpr(NonConstRefParam, IsInstantiated,
396 .bind(NodeID<Expr>::value)),
398 for (const auto &Nodes : Matches) {
399 const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
400 const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
401 if (!Func->getBody() || !Func->getPrimaryTemplate())
404 const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
405 const ArrayRef<ParmVarDecl *> AllParams =
406 Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
408 AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
409 AllParams.size() - 1)]
411 if (const auto *T = ParmType->getAs<PackExpansionType>())
412 ParmType = T->getPattern();
414 // If param type is forwarding reference, follow into the function
415 // definition and see whether the param is mutated inside.
416 if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
417 if (!RefType->getPointeeType().getQualifiers() &&
418 RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
419 std::unique_ptr<FunctionParmMutationAnalyzer> &Analyzer =
420 FuncParmAnalyzer[Func];
422 Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
423 if (Analyzer->findMutation(Parm))
428 // Not forwarding reference.
434 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
435 const FunctionDecl &Func, ASTContext &Context)
436 : BodyAnalyzer(*Func.getBody(), Context) {
437 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
438 // CXXCtorInitializer might also mutate Param but they're not part of
439 // function body, check them eagerly here since they're typically trivial.
440 for (const CXXCtorInitializer *Init : Ctor->inits()) {
441 ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context);
442 for (const ParmVarDecl *Parm : Ctor->parameters()) {
443 if (Results.find(Parm) != Results.end())
445 if (const Stmt *S = InitAnalyzer.findMutation(Parm))
453 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
454 const auto Memoized = Results.find(Parm);
455 if (Memoized != Results.end())
456 return Memoized->second;
458 if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
459 return Results[Parm] = S;
461 return Results[Parm] = nullptr;