1 //===---------- ExprMutationAnalyzer.cpp ----------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
10 #include "clang/ASTMatchers/ASTMatchFinder.h"
11 #include "llvm/ADT/STLExtras.h"
12
13 namespace clang {
14 using namespace ast_matchers;
15
16 namespace {
17
AST_MATCHER_P(LambdaExpr,hasCaptureInit,const Expr *,E)18 AST_MATCHER_P(LambdaExpr, hasCaptureInit, const Expr *, E) {
19 return llvm::is_contained(Node.capture_inits(), E);
20 }
21
AST_MATCHER_P(CXXForRangeStmt,hasRangeStmt,ast_matchers::internal::Matcher<DeclStmt>,InnerMatcher)22 AST_MATCHER_P(CXXForRangeStmt, hasRangeStmt,
23 ast_matchers::internal::Matcher<DeclStmt>, InnerMatcher) {
24 const DeclStmt *const Range = Node.getRangeStmt();
25 return InnerMatcher.matches(*Range, Finder, Builder);
26 }
27
28 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXTypeidExpr>
29 cxxTypeidExpr;
30
AST_MATCHER(CXXTypeidExpr,isPotentiallyEvaluated)31 AST_MATCHER(CXXTypeidExpr, isPotentiallyEvaluated) {
32 return Node.isPotentiallyEvaluated();
33 }
34
35 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
36 cxxNoexceptExpr;
37
38 const ast_matchers::internal::VariadicDynCastAllOfMatcher<Stmt,
39 GenericSelectionExpr>
40 genericSelectionExpr;
41
AST_MATCHER_P(GenericSelectionExpr,hasControllingExpr,ast_matchers::internal::Matcher<Expr>,InnerMatcher)42 AST_MATCHER_P(GenericSelectionExpr, hasControllingExpr,
43 ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
44 return InnerMatcher.matches(*Node.getControllingExpr(), Finder, Builder);
45 }
46
__anonee1e72710202null47 const auto nonConstReferenceType = [] {
48 return hasUnqualifiedDesugaredType(
49 referenceType(pointee(unless(isConstQualified()))));
50 };
51
__anonee1e72710302null52 const auto nonConstPointerType = [] {
53 return hasUnqualifiedDesugaredType(
54 pointerType(pointee(unless(isConstQualified()))));
55 };
56
__anonee1e72710402null57 const auto isMoveOnly = [] {
58 return cxxRecordDecl(
59 hasMethod(cxxConstructorDecl(isMoveConstructor(), unless(isDeleted()))),
60 hasMethod(cxxMethodDecl(isMoveAssignmentOperator(), unless(isDeleted()))),
61 unless(anyOf(hasMethod(cxxConstructorDecl(isCopyConstructor(),
62 unless(isDeleted()))),
63 hasMethod(cxxMethodDecl(isCopyAssignmentOperator(),
64 unless(isDeleted()))))));
65 };
66
67 template <class T> struct NodeID;
68 template <> struct NodeID<Expr> { static const std::string value; };
69 template <> struct NodeID<Decl> { static const std::string value; };
70 const std::string NodeID<Expr>::value = "expr";
71 const std::string NodeID<Decl>::value = "decl";
72
73 template <class T, class F = const Stmt *(ExprMutationAnalyzer::*)(const T *)>
tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,ExprMutationAnalyzer * Analyzer,F Finder)74 const Stmt *tryEachMatch(ArrayRef<ast_matchers::BoundNodes> Matches,
75 ExprMutationAnalyzer *Analyzer, F Finder) {
76 const StringRef ID = NodeID<T>::value;
77 for (const auto &Nodes : Matches) {
78 if (const Stmt *S = (Analyzer->*Finder)(Nodes.getNodeAs<T>(ID)))
79 return S;
80 }
81 return nullptr;
82 }
83
84 } // namespace
85
findMutation(const Expr * Exp)86 const Stmt *ExprMutationAnalyzer::findMutation(const Expr *Exp) {
87 return findMutationMemoized(Exp,
88 {&ExprMutationAnalyzer::findDirectMutation,
89 &ExprMutationAnalyzer::findMemberMutation,
90 &ExprMutationAnalyzer::findArrayElementMutation,
91 &ExprMutationAnalyzer::findCastMutation,
92 &ExprMutationAnalyzer::findRangeLoopMutation,
93 &ExprMutationAnalyzer::findReferenceMutation,
94 &ExprMutationAnalyzer::findFunctionArgMutation},
95 Results);
96 }
97
findMutation(const Decl * Dec)98 const Stmt *ExprMutationAnalyzer::findMutation(const Decl *Dec) {
99 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findMutation);
100 }
101
findPointeeMutation(const Expr * Exp)102 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Expr *Exp) {
103 return findMutationMemoized(Exp, {/*TODO*/}, PointeeResults);
104 }
105
findPointeeMutation(const Decl * Dec)106 const Stmt *ExprMutationAnalyzer::findPointeeMutation(const Decl *Dec) {
107 return tryEachDeclRef(Dec, &ExprMutationAnalyzer::findPointeeMutation);
108 }
109
findMutationMemoized(const Expr * Exp,llvm::ArrayRef<MutationFinder> Finders,ResultMap & MemoizedResults)110 const Stmt *ExprMutationAnalyzer::findMutationMemoized(
111 const Expr *Exp, llvm::ArrayRef<MutationFinder> Finders,
112 ResultMap &MemoizedResults) {
113 const auto Memoized = MemoizedResults.find(Exp);
114 if (Memoized != MemoizedResults.end())
115 return Memoized->second;
116
117 if (isUnevaluated(Exp))
118 return MemoizedResults[Exp] = nullptr;
119
120 for (const auto &Finder : Finders) {
121 if (const Stmt *S = (this->*Finder)(Exp))
122 return MemoizedResults[Exp] = S;
123 }
124
125 return MemoizedResults[Exp] = nullptr;
126 }
127
tryEachDeclRef(const Decl * Dec,MutationFinder Finder)128 const Stmt *ExprMutationAnalyzer::tryEachDeclRef(const Decl *Dec,
129 MutationFinder Finder) {
130 const auto Refs =
131 match(findAll(declRefExpr(to(equalsNode(Dec))).bind(NodeID<Expr>::value)),
132 Stm, Context);
133 for (const auto &RefNodes : Refs) {
134 const auto *E = RefNodes.getNodeAs<Expr>(NodeID<Expr>::value);
135 if ((this->*Finder)(E))
136 return E;
137 }
138 return nullptr;
139 }
140
isUnevaluated(const Expr * Exp)141 bool ExprMutationAnalyzer::isUnevaluated(const Expr *Exp) {
142 return selectFirst<Expr>(
143 NodeID<Expr>::value,
144 match(
145 findAll(
146 expr(equalsNode(Exp),
147 anyOf(
148 // `Exp` is part of the underlying expression of
149 // decltype/typeof if it has an ancestor of
150 // typeLoc.
151 hasAncestor(typeLoc(unless(
152 hasAncestor(unaryExprOrTypeTraitExpr())))),
153 hasAncestor(expr(anyOf(
154 // `UnaryExprOrTypeTraitExpr` is unevaluated
155 // unless it's sizeof on VLA.
156 unaryExprOrTypeTraitExpr(unless(sizeOfExpr(
157 hasArgumentOfType(variableArrayType())))),
158 // `CXXTypeidExpr` is unevaluated unless it's
159 // applied to an expression of glvalue of
160 // polymorphic class type.
161 cxxTypeidExpr(
162 unless(isPotentiallyEvaluated())),
163 // The controlling expression of
164 // `GenericSelectionExpr` is unevaluated.
165 genericSelectionExpr(hasControllingExpr(
166 hasDescendant(equalsNode(Exp)))),
167 cxxNoexceptExpr())))))
168 .bind(NodeID<Expr>::value)),
169 Stm, Context)) != nullptr;
170 }
171
172 const Stmt *
findExprMutation(ArrayRef<BoundNodes> Matches)173 ExprMutationAnalyzer::findExprMutation(ArrayRef<BoundNodes> Matches) {
174 return tryEachMatch<Expr>(Matches, this, &ExprMutationAnalyzer::findMutation);
175 }
176
177 const Stmt *
findDeclMutation(ArrayRef<BoundNodes> Matches)178 ExprMutationAnalyzer::findDeclMutation(ArrayRef<BoundNodes> Matches) {
179 return tryEachMatch<Decl>(Matches, this, &ExprMutationAnalyzer::findMutation);
180 }
181
findExprPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)182 const Stmt *ExprMutationAnalyzer::findExprPointeeMutation(
183 ArrayRef<ast_matchers::BoundNodes> Matches) {
184 return tryEachMatch<Expr>(Matches, this,
185 &ExprMutationAnalyzer::findPointeeMutation);
186 }
187
findDeclPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches)188 const Stmt *ExprMutationAnalyzer::findDeclPointeeMutation(
189 ArrayRef<ast_matchers::BoundNodes> Matches) {
190 return tryEachMatch<Decl>(Matches, this,
191 &ExprMutationAnalyzer::findPointeeMutation);
192 }
193
findDirectMutation(const Expr * Exp)194 const Stmt *ExprMutationAnalyzer::findDirectMutation(const Expr *Exp) {
195 // LHS of any assignment operators.
196 const auto AsAssignmentLhs =
197 binaryOperator(isAssignmentOperator(), hasLHS(equalsNode(Exp)));
198
199 // Operand of increment/decrement operators.
200 const auto AsIncDecOperand =
201 unaryOperator(anyOf(hasOperatorName("++"), hasOperatorName("--")),
202 hasUnaryOperand(equalsNode(Exp)));
203
204 // Invoking non-const member function.
205 // A member function is assumed to be non-const when it is unresolved.
206 const auto NonConstMethod = cxxMethodDecl(unless(isConst()));
207 const auto AsNonConstThis =
208 expr(anyOf(cxxMemberCallExpr(callee(NonConstMethod), on(equalsNode(Exp))),
209 cxxOperatorCallExpr(callee(NonConstMethod),
210 hasArgument(0, equalsNode(Exp))),
211 callExpr(callee(expr(anyOf(
212 unresolvedMemberExpr(hasObjectExpression(equalsNode(Exp))),
213 cxxDependentScopeMemberExpr(
214 hasObjectExpression(equalsNode(Exp)))))))));
215
216 // Taking address of 'Exp'.
217 // We're assuming 'Exp' is mutated as soon as its address is taken, though in
218 // theory we can follow the pointer and see whether it escaped `Stm` or is
219 // dereferenced and then mutated. This is left for future improvements.
220 const auto AsAmpersandOperand =
221 unaryOperator(hasOperatorName("&"),
222 // A NoOp implicit cast is adding const.
223 unless(hasParent(implicitCastExpr(hasCastKind(CK_NoOp)))),
224 hasUnaryOperand(equalsNode(Exp)));
225 const auto AsPointerFromArrayDecay =
226 castExpr(hasCastKind(CK_ArrayToPointerDecay),
227 unless(hasParent(arraySubscriptExpr())), has(equalsNode(Exp)));
228 // Treat calling `operator->()` of move-only classes as taking address.
229 // These are typically smart pointers with unique ownership so we treat
230 // mutation of pointee as mutation of the smart pointer itself.
231 const auto AsOperatorArrowThis =
232 cxxOperatorCallExpr(hasOverloadedOperatorName("->"),
233 callee(cxxMethodDecl(ofClass(isMoveOnly()),
234 returns(nonConstPointerType()))),
235 argumentCountIs(1), hasArgument(0, equalsNode(Exp)));
236
237 // Used as non-const-ref argument when calling a function.
238 // An argument is assumed to be non-const-ref when the function is unresolved.
239 // Instantiated template functions are not handled here but in
240 // findFunctionArgMutation which has additional smarts for handling forwarding
241 // references.
242 const auto NonConstRefParam = forEachArgumentWithParam(
243 equalsNode(Exp), parmVarDecl(hasType(nonConstReferenceType())));
244 const auto NotInstantiated = unless(hasDeclaration(isInstantiated()));
245 const auto AsNonConstRefArg = anyOf(
246 callExpr(NonConstRefParam, NotInstantiated),
247 cxxConstructExpr(NonConstRefParam, NotInstantiated),
248 callExpr(callee(expr(anyOf(unresolvedLookupExpr(), unresolvedMemberExpr(),
249 cxxDependentScopeMemberExpr(),
250 hasType(templateTypeParmType())))),
251 hasAnyArgument(equalsNode(Exp))),
252 cxxUnresolvedConstructExpr(hasAnyArgument(equalsNode(Exp))));
253
254 // Captured by a lambda by reference.
255 // If we're initializing a capture with 'Exp' directly then we're initializing
256 // a reference capture.
257 // For value captures there will be an ImplicitCastExpr <LValueToRValue>.
258 const auto AsLambdaRefCaptureInit = lambdaExpr(hasCaptureInit(Exp));
259
260 // Returned as non-const-ref.
261 // If we're returning 'Exp' directly then it's returned as non-const-ref.
262 // For returning by value there will be an ImplicitCastExpr <LValueToRValue>.
263 // For returning by const-ref there will be an ImplicitCastExpr <NoOp> (for
264 // adding const.)
265 const auto AsNonConstRefReturn = returnStmt(hasReturnValue(equalsNode(Exp)));
266
267 const auto Matches =
268 match(findAll(stmt(anyOf(AsAssignmentLhs, AsIncDecOperand, AsNonConstThis,
269 AsAmpersandOperand, AsPointerFromArrayDecay,
270 AsOperatorArrowThis, AsNonConstRefArg,
271 AsLambdaRefCaptureInit, AsNonConstRefReturn))
272 .bind("stmt")),
273 Stm, Context);
274 return selectFirst<Stmt>("stmt", Matches);
275 }
276
findMemberMutation(const Expr * Exp)277 const Stmt *ExprMutationAnalyzer::findMemberMutation(const Expr *Exp) {
278 // Check whether any member of 'Exp' is mutated.
279 const auto MemberExprs =
280 match(findAll(expr(anyOf(memberExpr(hasObjectExpression(equalsNode(Exp))),
281 cxxDependentScopeMemberExpr(
282 hasObjectExpression(equalsNode(Exp)))))
283 .bind(NodeID<Expr>::value)),
284 Stm, Context);
285 return findExprMutation(MemberExprs);
286 }
287
findArrayElementMutation(const Expr * Exp)288 const Stmt *ExprMutationAnalyzer::findArrayElementMutation(const Expr *Exp) {
289 // Check whether any element of an array is mutated.
290 const auto SubscriptExprs = match(
291 findAll(arraySubscriptExpr(hasBase(ignoringImpCasts(equalsNode(Exp))))
292 .bind(NodeID<Expr>::value)),
293 Stm, Context);
294 return findExprMutation(SubscriptExprs);
295 }
296
findCastMutation(const Expr * Exp)297 const Stmt *ExprMutationAnalyzer::findCastMutation(const Expr *Exp) {
298 // If 'Exp' is casted to any non-const reference type, check the castExpr.
299 const auto Casts =
300 match(findAll(castExpr(hasSourceExpression(equalsNode(Exp)),
301 anyOf(explicitCastExpr(hasDestinationType(
302 nonConstReferenceType())),
303 implicitCastExpr(hasImplicitDestinationType(
304 nonConstReferenceType()))))
305 .bind(NodeID<Expr>::value)),
306 Stm, Context);
307 if (const Stmt *S = findExprMutation(Casts))
308 return S;
309 // Treat std::{move,forward} as cast.
310 const auto Calls =
311 match(findAll(callExpr(callee(namedDecl(
312 hasAnyName("::std::move", "::std::forward"))),
313 hasArgument(0, equalsNode(Exp)))
314 .bind("expr")),
315 Stm, Context);
316 return findExprMutation(Calls);
317 }
318
findRangeLoopMutation(const Expr * Exp)319 const Stmt *ExprMutationAnalyzer::findRangeLoopMutation(const Expr *Exp) {
320 // If range for looping over 'Exp' with a non-const reference loop variable,
321 // check all declRefExpr of the loop variable.
322 const auto LoopVars =
323 match(findAll(cxxForRangeStmt(
324 hasLoopVariable(varDecl(hasType(nonConstReferenceType()))
325 .bind(NodeID<Decl>::value)),
326 hasRangeInit(equalsNode(Exp)))),
327 Stm, Context);
328 return findDeclMutation(LoopVars);
329 }
330
findReferenceMutation(const Expr * Exp)331 const Stmt *ExprMutationAnalyzer::findReferenceMutation(const Expr *Exp) {
332 // Follow non-const reference returned by `operator*()` of move-only classes.
333 // These are typically smart pointers with unique ownership so we treat
334 // mutation of pointee as mutation of the smart pointer itself.
335 const auto Ref =
336 match(findAll(cxxOperatorCallExpr(
337 hasOverloadedOperatorName("*"),
338 callee(cxxMethodDecl(ofClass(isMoveOnly()),
339 returns(nonConstReferenceType()))),
340 argumentCountIs(1), hasArgument(0, equalsNode(Exp)))
341 .bind(NodeID<Expr>::value)),
342 Stm, Context);
343 if (const Stmt *S = findExprMutation(Ref))
344 return S;
345
346 // If 'Exp' is bound to a non-const reference, check all declRefExpr to that.
347 const auto Refs = match(
348 stmt(forEachDescendant(
349 varDecl(
350 hasType(nonConstReferenceType()),
351 hasInitializer(anyOf(equalsNode(Exp),
352 conditionalOperator(anyOf(
353 hasTrueExpression(equalsNode(Exp)),
354 hasFalseExpression(equalsNode(Exp)))))),
355 hasParent(declStmt().bind("stmt")),
356 // Don't follow the reference in range statement, we've handled
357 // that separately.
358 unless(hasParent(declStmt(hasParent(
359 cxxForRangeStmt(hasRangeStmt(equalsBoundNode("stmt"))))))))
360 .bind(NodeID<Decl>::value))),
361 Stm, Context);
362 return findDeclMutation(Refs);
363 }
364
findFunctionArgMutation(const Expr * Exp)365 const Stmt *ExprMutationAnalyzer::findFunctionArgMutation(const Expr *Exp) {
366 const auto NonConstRefParam = forEachArgumentWithParam(
367 equalsNode(Exp),
368 parmVarDecl(hasType(nonConstReferenceType())).bind("parm"));
369 const auto IsInstantiated = hasDeclaration(isInstantiated());
370 const auto FuncDecl = hasDeclaration(functionDecl().bind("func"));
371 const auto Matches = match(
372 findAll(expr(anyOf(callExpr(NonConstRefParam, IsInstantiated, FuncDecl,
373 unless(callee(namedDecl(hasAnyName(
374 "::std::move", "::std::forward"))))),
375 cxxConstructExpr(NonConstRefParam, IsInstantiated,
376 FuncDecl)))
377 .bind(NodeID<Expr>::value)),
378 Stm, Context);
379 for (const auto &Nodes : Matches) {
380 const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
381 const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
382 if (!Func->getBody() || !Func->getPrimaryTemplate())
383 return Exp;
384
385 const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
386 const ArrayRef<ParmVarDecl *> AllParams =
387 Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();
388 QualType ParmType =
389 AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
390 AllParams.size() - 1)]
391 ->getType();
392 if (const auto *T = ParmType->getAs<PackExpansionType>())
393 ParmType = T->getPattern();
394
395 // If param type is forwarding reference, follow into the function
396 // definition and see whether the param is mutated inside.
397 if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
398 if (!RefType->getPointeeType().getQualifiers() &&
399 RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
400 std::unique_ptr<FunctionParmMutationAnalyzer> &Analyzer =
401 FuncParmAnalyzer[Func];
402 if (!Analyzer)
403 Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
404 if (Analyzer->findMutation(Parm))
405 return Exp;
406 continue;
407 }
408 }
409 // Not forwarding reference.
410 return Exp;
411 }
412 return nullptr;
413 }
414
FunctionParmMutationAnalyzer(const FunctionDecl & Func,ASTContext & Context)415 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
416 const FunctionDecl &Func, ASTContext &Context)
417 : BodyAnalyzer(*Func.getBody(), Context) {
418 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
419 // CXXCtorInitializer might also mutate Param but they're not part of
420 // function body, check them eagerly here since they're typically trivial.
421 for (const CXXCtorInitializer *Init : Ctor->inits()) {
422 ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context);
423 for (const ParmVarDecl *Parm : Ctor->parameters()) {
424 if (Results.find(Parm) != Results.end())
425 continue;
426 if (const Stmt *S = InitAnalyzer.findMutation(Parm))
427 Results[Parm] = S;
428 }
429 }
430 }
431 }
432
433 const Stmt *
findMutation(const ParmVarDecl * Parm)434 FunctionParmMutationAnalyzer::findMutation(const ParmVarDecl *Parm) {
435 const auto Memoized = Results.find(Parm);
436 if (Memoized != Results.end())
437 return Memoized->second;
438
439 if (const Stmt *S = BodyAnalyzer.findMutation(Parm))
440 return Results[Parm] = S;
441
442 return Results[Parm] = nullptr;
443 }
444
445 } // namespace clang
446