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,
47 GenericSelectionExpr>
48 genericSelectionExpr;
49
AST_MATCHER_P(GenericSelectionExpr,hasControllingExpr,ast_matchers::internal::Matcher<Expr>,InnerMatcher)50 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
51 ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
52 return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
53 }
54
__anon8ee68b350202null55 const auto nonConstReferenceType = [] {
56 return hasUnqualifiedDesugaredType(
57 referenceType(pointee(unless(isConstQualified()))));
58 };
59
__anon8ee68b350302null60 const auto nonConstPointerType = [] {
61 return hasUnqualifiedDesugaredType(
62 pointerType(pointee(unless(isConstQualified()))));
63 };
64
__anon8ee68b350402null65 const auto isMoveOnly = [] {
66 return cxxRecordDecl(
67 hasMethod(cxxConstructorDecl(isMoveConstructor(), unless(isDeleted()))),
68 hasMethod(cxxMethodDecl(isMoveAssignmentOperator(), unless(isDeleted()))),
69 unless(anyOf(hasMethod(cxxConstructorDecl(isCopyConstructor(),
70 unless(isDeleted()))),
71 hasMethod(cxxMethodDecl(isCopyAssignmentOperator(),
72 unless(isDeleted()))))));
73 };
74
75 template <class T> struct NodeID;
76 template <> struct NodeID<Expr> { static constexpr StringRef value = "expr"; };
77 template <> struct NodeID<Decl> { static constexpr StringRef value = "decl"; };
78 constexpr StringRef NodeID<Expr>::value;
79 constexpr StringRef NodeID<Decl>::value;
80
81 template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)>
tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,ExprMutationAnalyzer * Analyzer,F Finder)82 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
83 ExprMutationAnalyzer *Analyzer, F Finder) {
84 const StringRef ID = NodeID<T>::value;
85 for (const auto &Nodes : Matches) {
86 if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
87 return S;
88 }
89 return nullptr;
90 }
91
92 } // namespace
93
findMutation(const Expr * Exp)94 const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) {
95 return findMutationMemoized(Exp,
96 {&ExprMutationAnalyzer::findDirectMutation,
97 &ExprMutationAnalyzer::findMemberMutation,
98 &ExprMutationAnalyzer::findArrayElementMutation,
99 &ExprMutationAnalyzer::findCastMutation,
100 &ExprMutationAnalyzer::findRangeLoopMutation,
101 &ExprMutationAnalyzer::findReferenceMutation,
102 &ExprMutationAnalyzer::findFunctionArgMutation},
103 Results);
104 }
105
findMutation(const Decl * Dec)106 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
107 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
108 }
109
findPointeeMutation(const Expr * Exp)110 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
111 return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
112 }
113
findPointeeMutation(const Decl * Dec)114 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
115 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
116 }
117
findMutationMemoized(const Expr * Exp,llvm::ArrayRef<MutationFinder> Finders,ResultMap & MemoizedResults)118 const Stmt *ExprMutationAnalyzer::findMutationMemoized(
119 const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,
120 ResultMap &MemoizedResults) {
121 const auto Memoized = MemoizedResults.find(Exp);
122 if (Memoized != MemoizedResults.end())
123 return Memoized->second;
124
125 if (isUnevaluated(Exp))
126 return MemoizedResults[Exp] = nullptr;
127
128 for (const auto &Finder : Finders) {
129 if (const Stmt *S = (this->*Finder)(Exp))
130 return MemoizedResults[Exp] = S;
131 }
132
133 return MemoizedResults[Exp] = nullptr;
134 }
135
tryEachDeclRef(const Decl * Dec,MutationFinder Finder)136 const Stmt *ExprMutationAnalyzer::tryEachDeclRef(const Decl *Dec,
137 MutationFinder Finder) {
138 const auto Refs =
139 match(findAll(declRefExpr(to(equalsNode(Dec))).bind(NodeID<Expr>::value)),
140 Stm, Context);
141 for (const auto &RefNodes : Refs) {
142 const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
143 if ((this->*Finder)(E))
144 return E;
145 }
146 return nullptr;
147 }
148
isUnevaluated(const Expr * Exp)149 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) {
150 return selectFirst<Expr>(
151 NodeID<Expr>::value,
152 match(
153 findAll(
154 expr(equalsNode(Exp),
155 anyOf(
156 // `Exp` is part of the underlying expression of
157 // decltype/typeof if it has an ancestor of
158 // typeLoc.
159 hasAncestor(typeLoc(unless(
160 hasAncestor(unaryExprOrTypeTraitExpr())))),
161 hasAncestor(expr(anyOf(
162 // `UnaryExprOrTypeTraitExpr` is unevaluated
163 // unless it's sizeof on VLA.
164 unaryExprOrTypeTraitExpr(unless(sizeOfExpr(
165 hasArgumentOfType(variableArrayType())))),
166 // `CXXTypeidExpr` is unevaluated unless it's
167 // applied to an expression of glvalue of
168 // polymorphic class type.
169 cxxTypeidExpr(
170 unless(isPotentiallyEvaluated())),
171 // The controlling expression of
172 // `GenericSelectionExpr` is unevaluated.
173 genericSelectionExpr(hasControllingExpr(
174 hasDescendant(equalsNode(Exp)))),
175 cxxNoexceptExpr())))))
176 .bind(NodeID<Expr>::value)),
177 Stm, Context)) != nullptr;
178 }
179
180 const Stmt *
findExprMutation(ArrayRef<BoundNodes> Matches)181 ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
182 return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation);
183 }
184
185 const Stmt *
findDeclMutation(ArrayRef<BoundNodes> Matches)186 ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
187 return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation);
188 }
189
findExprPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)190 const Stmt *ExprMutationAnalyzer::findExprPointeeMutation(
191 ArrayRef<ast_matchers::BoundNodes> Matches) {
192 return tryEachMatch<Expr>(Matches, this,
193 &ExprMutationAnalyzer::findPointeeMutation);
194 }
195
findDeclPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)196 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
197 ArrayRef<ast_matchers::BoundNodes> Matches) {
198 return tryEachMatch<Decl>(Matches, this,
199 &ExprMutationAnalyzer::findPointeeMutation);
200 }
201
findDirectMutation(const Expr * Exp)202 const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
203 // LHS of any assignment operators.
204 const auto AsAssignmentLhs = binaryOperator(
205 isAssignmentOperator(),
206 hasLHS(maybeEvalCommaExpr(ignoringParenImpCasts(equalsNode(Exp)))));
207
208 // Operand of increment/decrement operators.
209 const auto AsIncDecOperand =
210 unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
211 hasUnaryOperand(maybeEvalCommaExpr(
212 ignoringParenImpCasts(equalsNode(Exp)))));
213
214 // Invoking non-const member function.
215 // A member function is assumed to be non-const when it is unresolved.
216 const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
217 const auto AsNonConstThis =
218 expr(anyOf(cxxMemberCallExpr(callee(NonConstMethod),
219 on(maybeEvalCommaExpr(equalsNode(Exp)))),
220 cxxOperatorCallExpr(callee(NonConstMethod),
221 hasArgument(0,
222 maybeEvalCommaExpr(equalsNode(Exp)))),
223 callExpr(callee(expr(anyOf(
224 unresolvedMemberExpr(
225 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp)))),
226 cxxDependentScopeMemberExpr(
227 hasObjectExpression(maybeEvalCommaExpr(equalsNode(Exp))))))))));
228
229 // Taking address of 'Exp'.
230 // We're assuming 'Exp' is mutated as soon as its address is taken, though in
231 // theory we can follow the pointer and see whether it escaped `Stm` or is
232 // dereferenced and then mutated. This is left for future improvements.
233 const auto AsAmpersandOperand =
234 unaryOperator(hasOperatorName("&"),
235 // A NoOp implicit cast is adding const.
236 unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
237 hasUnaryOperand(maybeEvalCommaExpr(equalsNode(Exp))));
238 const auto AsPointerFromArrayDecay =
239 castExpr(hasCastKind(CK_ArrayToPointerDecay),
240 unless(hasParent(arraySubscriptExpr())),
241 has(maybeEvalCommaExpr(equalsNode(Exp))));
242 // Treat calling `operator->()` of move-only classes as taking address.
243 // These are typically smart pointers with unique ownership so we treat
244 // mutation of pointee as mutation of the smart pointer itself.
245 const auto AsOperatorArrowThis =
246 cxxOperatorCallExpr(hasOverloadedOperatorName("->"),
247 callee(cxxMethodDecl(ofClass(isMoveOnly()),
248 returns(nonConstPointerType()))),
249 argumentCountIs(1),
250 hasArgument(0, maybeEvalCommaExpr(equalsNode(Exp))));
251
252 // Used as non-const-ref argument when calling a function.
253 // An argument is assumed to be non-const-ref when the function is unresolved.
254 // Instantiated template functions are not handled here but in
255 // findFunctionArgMutation which has additional smarts for handling forwarding
256 // references.
257 const auto NonConstRefParam = forEachArgumentWithParam(
258 maybeEvalCommaExpr(equalsNode(Exp)),
259 parmVarDecl(hasType(nonConstReferenceType())));
260 const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
261 const auto AsNonConstRefArg = anyOf(
262 callExpr(NonConstRefParam, NotInstantiated),
263 cxxConstructExpr(NonConstRefParam, NotInstantiated),
264 callExpr(callee(expr(anyOf(unresolvedLookupExpr(), unresolvedMemberExpr(),
265 cxxDependentScopeMemberExpr(),
266 hasType(templateTypeParmType())))),
267 hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp)))),
268 cxxUnresolvedConstructExpr(hasAnyArgument(maybeEvalCommaExpr(equalsNode(Exp)))));
269
270 // Captured by a lambda by reference.
271 // If we're initializing a capture with 'Exp' directly then we're initializing
272 // a reference capture.
273 // For value captures there will be an ImplicitCastExpr <LValueToRValue>.
274 const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp));
275
276 // Returned as non-const-ref.
277 // If we're returning 'Exp' directly then it's returned as non-const-ref.
278 // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
279 // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
280 // adding const.)
281 const auto AsNonConstRefReturn = returnStmt(hasReturnValue(
282 maybeEvalCommaExpr(equalsNode(Exp))));
283
284 const auto Matches = match(
285 traverse(
286 ast_type_traits::TK_AsIs,
287 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 traverse(
392 ast_type_traits::TK_AsIs,
393 findAll(
394 expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl,
395 unless(callee(namedDecl(hasAnyName(
396 "::std::move", "::std::forward"))))),
397 cxxConstructExpr(NonConstRefParam, IsInstantiated,
398 FuncDecl)))
399 .bind(NodeID<Expr>::value))),
400 Stm, Context);
401 for (const auto &Nodes : Matches) {
402 const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
403 const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
404 if (!Func->getBody() || !Func->getPrimaryTemplate())
405 return Exp;
406
407 const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
408 const ArrayRef<ParmVarDecl *> AllParams =
409 Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
410 QualType ParmType =
411 AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
412 AllParams.size() - 1)]
413 ->getType();
414 if (const auto *T = ParmType->getAs<PackExpansionType>())
415 ParmType = T->getPattern();
416
417 // If param type is forwarding reference, follow into the function
418 // definition and see whether the param is mutated inside.
419 if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
420 if (!RefType->getPointeeType().getQualifiers() &&
421 RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
422 std::unique_ptr<FunctionParmMutationAnalyzer> &Analyzer =
423 FuncParmAnalyzer[Func];
424 if (!Analyzer)
425 Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
426 if (Analyzer->findMutation(Parm))
427 return Exp;
428 continue;
429 }
430 }
431 // Not forwarding reference.
432 return Exp;
433 }
434 return nullptr;
435 }
436
FunctionParmMutationAnalyzer(const FunctionDecl & Func,ASTContext & Context)437 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
438 const FunctionDecl &Func, ASTContext &Context)
439 : BodyAnalyzer(*Func.getBody(), Context) {
440 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
441 // CXXCtorInitializer might also mutate Param but they're not part of
442 // function body, check them eagerly here since they're typically trivial.
443 for (const CXXCtorInitializer *Init : Ctor->inits()) {
444 ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context);
445 for (const ParmVarDecl *Parm : Ctor->parameters()) {
446 if (Results.find(Parm) != Results.end())
447 continue;
448 if (const Stmt *S = InitAnalyzer.findMutation(Parm))
449 Results[Parm] = S;
450 }
451 }
452 }
453 }
454
455 const Stmt *
findMutation(const ParmVarDecl * Parm)456 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
457 const auto Memoized = Results.find(Parm);
458 if (Memoized != Results.end())
459 return Memoized->second;
460
461 if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
462 return Results[Parm] = S;
463
464 return Results[Parm] = nullptr;
465 }
466
467 } // namespace clang
468