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/ASTMatchers/ASTMatchFinder.h"
10 #include "llvm/ADT/STLExtras.h"
11
12 namespace clang {
13 using namespace ast_matchers;
14
15 namespace {
16
AST_MATCHER_P(LambdaExpr,hasCaptureInit,const Expr *,E)17 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
18 return llvm::is_contained(Node.capture_inits(), E);
19 }
20
AST_MATCHER_P(CXXForRangeStmt,hasRangeStmt,ast_matchers::internal::Matcher<DeclStmt>,InnerMatcher)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);
25 }
26
AST_MATCHER_P(Expr,maybeEvalCommaExpr,ast_matchers::internal::Matcher<Expr>,InnerMatcher)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())
33 break;
34 Result = BOComma->getRHS();
35 }
36 return InnerMatcher.matches(*Result, Finder, Builder);
37 }
38
39 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
40 cxxTypeidExpr;
41
AST_MATCHER(CXXTypeidExpr,isPotentiallyEvaluated)42 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
43 return Node.isPotentiallyEvaluated();
44 }
45
46 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
47 cxxNoexceptExpr;
48
49 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt,
50 GenericSelectionExpr>
51 genericSelectionExpr;
52
AST_MATCHER_P(GenericSelectionExpr,hasControllingExpr,ast_matchers::internal::Matcher<Expr>,InnerMatcher)53 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
54 ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
55 return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
56 }
57
__anon672723b30202null58 const auto nonConstReferenceType = [] {
59 return hasUnqualifiedDesugaredType(
60 referenceType(pointee(unless(isConstQualified()))));
61 };
62
__anon672723b30302null63 const auto nonConstPointerType = [] {
64 return hasUnqualifiedDesugaredType(
65 pointerType(pointee(unless(isConstQualified()))));
66 };
67
__anon672723b30402null68 const auto isMoveOnly = [] {
69 return cxxRecordDecl(
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()))))));
76 };
77
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";
83
84 template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)>
tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,ExprMutationAnalyzer * Analyzer,F Finder)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)))
90 return S;
91 }
92 return nullptr;
93 }
94
95 } // namespace
96
findMutation(const Expr * Exp)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},
106 Results);
107 }
108
findMutation(const Decl * Dec)109 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
110 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
111 }
112
findPointeeMutation(const Expr * Exp)113 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
114 return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
115 }
116
findPointeeMutation(const Decl * Dec)117 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
118 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
119 }
120
findMutationMemoized(const Expr * Exp,llvm::ArrayRef<MutationFinder> Finders,ResultMap & MemoizedResults)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;
127
128 if (isUnevaluated(Exp))
129 return MemoizedResults[Exp] = nullptr;
130
131 for (const auto &Finder : Finders) {
132 if (const Stmt *S = (this->*Finder)(Exp))
133 return MemoizedResults[Exp] = S;
134 }
135
136 return MemoizedResults[Exp] = nullptr;
137 }
138
tryEachDeclRef(const Decl * Dec,MutationFinder Finder)139 const Stmt *ExprMutationAnalyzer::tryEachDeclRef(const Decl *Dec,
140 MutationFinder Finder) {
141 const auto Refs =
142 match(findAll(declRefExpr(to(equalsNode(Dec))).bind(NodeID<Expr>::value)),
143 Stm, Context);
144 for (const auto &RefNodes : Refs) {
145 const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
146 if ((this->*Finder)(E))
147 return E;
148 }
149 return nullptr;
150 }
151
isUnevaluated(const Expr * Exp)152 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) {
153 return selectFirst<Expr>(
154 NodeID<Expr>::value,
155 match(
156 findAll(
157 expr(equalsNode(Exp),
158 anyOf(
159 // `Exp` is part of the underlying expression of
160 // decltype/typeof if it has an ancestor of
161 // typeLoc.
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.
172 cxxTypeidExpr(
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;
181 }
182
183 const Stmt *
findExprMutation(ArrayRef<BoundNodes> Matches)184 ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
185 return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation);
186 }
187
188 const Stmt *
findDeclMutation(ArrayRef<BoundNodes> Matches)189 ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
190 return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation);
191 }
192
findExprPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)193 const Stmt *ExprMutationAnalyzer::findExprPointeeMutation(
194 ArrayRef<ast_matchers::BoundNodes> Matches) {
195 return tryEachMatch<Expr>(Matches, this,
196 &ExprMutationAnalyzer::findPointeeMutation);
197 }
198
findDeclPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)199 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
200 ArrayRef<ast_matchers::BoundNodes> Matches) {
201 return tryEachMatch<Decl>(Matches, this,
202 &ExprMutationAnalyzer::findPointeeMutation);
203 }
204
findDirectMutation(const Expr * Exp)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))));
210
211 // Operand of increment/decrement operators.
212 const auto AsIncDecOperand =
213 unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
214 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp))));
215
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),
223 hasArgument(0,
224 maybeEvalCommaExpr(equalsNode(Exp)))),
225 callExpr(callee(expr(anyOf(
226 unresolvedMemberExpr(
227 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp)))),
228 cxxDependentScopeMemberExpr(
229 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp))))))))));
230
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()))),
251 argumentCountIs(1),
252 hasArgument(0, maybeEvalCommaExpr(equalsNode(Exp))));
253
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
258 // references.
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)))));
271
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));
277
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
282 // adding const.)
283 const auto AsNonConstRefReturn = returnStmt(hasReturnValue(
284 maybeEvalCommaExpr(equalsNode(Exp))));
285
286 const auto Matches =
287 match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
288 AsAmpersandOperand, AsPointerFromArrayDecay,
289 AsOperatorArrowThis, AsNonConstRefArg,
290 AsLambdaRefCaptureInit, AsNonConstRefReturn))
291 .bind("stmt")),
292 Stm, Context);
293 return selectFirst<Stmt>("stmt", Matches);
294 }
295
findMemberMutation(const Expr * Exp)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)),
303 Stm, Context);
304 return findExprMutation(MemberExprs);
305 }
306
findArrayElementMutation(const Expr * Exp)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)),
312 Stm, Context);
313 return findExprMutation(SubscriptExprs);
314 }
315
findCastMutation(const Expr * Exp)316 const Stmt *ExprMutationAnalyzer::findCastMutation(const Expr *Exp) {
317 // If 'Exp' is casted to any non-const reference type, check the castExpr.
318 const auto Casts =
319 match(findAll(castExpr(hasSourceExpression(equalsNode(Exp)),
320 anyOf(explicitCastExpr(hasDestinationType(
321 nonConstReferenceType())),
322 implicitCastExpr(hasImplicitDestinationType(
323 nonConstReferenceType()))))
324 .bind(NodeID<Expr>::value)),
325 Stm, Context);
326 if (const Stmt *S = findExprMutation(Casts))
327 return S;
328 // Treat std::{move,forward} as cast.
329 const auto Calls =
330 match(findAll(callExpr(callee(namedDecl(
331 hasAnyName("::std::move", "::std::forward"))),
332 hasArgument(0, equalsNode(Exp)))
333 .bind("expr")),
334 Stm, Context);
335 return findExprMutation(Calls);
336 }
337
findRangeLoopMutation(const Expr * Exp)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)))),
346 Stm, Context);
347 return findDeclMutation(LoopVars);
348 }
349
findReferenceMutation(const Expr * Exp)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.
354 const auto Ref =
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)),
361 Stm, Context);
362 if (const Stmt *S = findExprMutation(Ref))
363 return S;
364
365 // If 'Exp' is bound to a non-const reference, check all declRefExpr to that.
366 const auto Refs = match(
367 stmt(forEachDescendant(
368 varDecl(
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
376 // that separately.
377 unless(hasParent(declStmt(hasParent(
378 cxxForRangeStmt(hasRangeStmt(equalsBoundNode("stmt"))))))))
379 .bind(NodeID<Decl>::value))),
380 Stm, Context);
381 return findDeclMutation(Refs);
382 }
383
findFunctionArgMutation(const Expr * Exp)384 const Stmt *ExprMutationAnalyzer::findFunctionArgMutation(const Expr *Exp) {
385 const auto NonConstRefParam = forEachArgumentWithParam(
386 equalsNode(Exp),
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,
395 FuncDecl)))
396 .bind(NodeID<Expr>::value)),
397 Stm, Context);
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())
402 return Exp;
403
404 const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
405 const ArrayRef<ParmVarDecl *> AllParams =
406 Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
407 QualType ParmType =
408 AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
409 AllParams.size() - 1)]
410 ->getType();
411 if (const auto *T = ParmType->getAs<PackExpansionType>())
412 ParmType = T->getPattern();
413
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];
421 if (!Analyzer)
422 Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
423 if (Analyzer->findMutation(Parm))
424 return Exp;
425 continue;
426 }
427 }
428 // Not forwarding reference.
429 return Exp;
430 }
431 return nullptr;
432 }
433
FunctionParmMutationAnalyzer(const FunctionDecl & Func,ASTContext & Context)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())
444 continue;
445 if (const Stmt *S = InitAnalyzer.findMutation(Parm))
446 Results[Parm] = S;
447 }
448 }
449 }
450 }
451
452 const Stmt *
findMutation(const ParmVarDecl * Parm)453 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
454 const auto Memoized = Results.find(Parm);
455 if (Memoized != Results.end())
456 return Memoized->second;
457
458 if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
459 return Results[Parm] = S;
460
461 return Results[Parm] = nullptr;
462 }
463
464 } // namespace clang
465