1//===--- DeclRefExprUtils.cpp - clang-tidy---------------------------------===//
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
9#include "DeclRefExprUtils.h"
10#include "Matchers.h"
11#include "clang/AST/ASTContext.h"
12#include "clang/AST/DeclCXX.h"
13#include "clang/AST/ExprCXX.h"
14#include "clang/ASTMatchers/ASTMatchFinder.h"
15#include <cassert>
16
17namespace clang::tidy::utils::decl_ref_expr {
18
19using namespace ::clang::ast_matchers;
20using llvm::SmallPtrSet;
21
22namespace {
23
24template <typename S> bool isSetDifferenceEmpty(const S &S1, const S &S2) {
25 for (auto E : S1)
26 if (S2.count(E) == 0)
27 return false;
28 return true;
29}
30
31// Extracts all Nodes keyed by ID from Matches and inserts them into Nodes.
32template <typename Node>
33void extractNodesByIdTo(ArrayRef<BoundNodes> Matches, StringRef ID,
34 SmallPtrSet<const Node *, 16> &Nodes) {
35 for (const auto &Match : Matches)
36 Nodes.insert(Match.getNodeAs<Node>(ID));
37}
38
39// Returns true if both types refer to the same type,
40// ignoring the const-qualifier.
41bool isSameTypeIgnoringConst(QualType A, QualType B) {
42 A = A.getCanonicalType();
43 B = B.getCanonicalType();
44 A.addConst();
45 B.addConst();
46 return A == B;
47}
48
49// Returns true if `D` and `O` have the same parameter types.
50bool hasSameParameterTypes(const CXXMethodDecl &D, const CXXMethodDecl &O) {
51 if (D.getNumParams() != O.getNumParams())
52 return false;
53 for (int I = 0, E = D.getNumParams(); I < E; ++I) {
54 if (!isSameTypeIgnoringConst(D.getParamDecl(I)->getType(),
55 O.getParamDecl(I)->getType()))
56 return false;
57 }
58 return true;
59}
60
61// If `D` has a const-qualified overload with otherwise identical
62// ref-qualifiers and parameter types, returns that overload.
63const CXXMethodDecl *findConstOverload(const CXXMethodDecl &D) {
64 assert(!D.isConst());
65
66 DeclContext::lookup_result LookupResult =
67 D.getParent()->lookup(Name: D.getNameInfo().getName());
68 if (LookupResult.isSingleResult()) {
69 // No overload.
70 return nullptr;
71 }
72 for (const Decl *Overload : LookupResult) {
73 const auto *O = dyn_cast<CXXMethodDecl>(Overload);
74 if (O && !O->isDeleted() && O->isConst() &&
75 O->getRefQualifier() == D.getRefQualifier() &&
76 hasSameParameterTypes(D, *O))
77 return O;
78 }
79 return nullptr;
80}
81
82// Returns true if both types are pointers or reference to the same type,
83// ignoring the const-qualifier.
84bool pointsToSameTypeIgnoringConst(QualType A, QualType B) {
85 assert(A->isPointerType() || A->isReferenceType());
86 assert(B->isPointerType() || B->isReferenceType());
87 return isSameTypeIgnoringConst(A: A->getPointeeType(), B: B->getPointeeType());
88}
89
90// Return true if non-const member function `M` likely does not mutate `*this`.
91//
92// Note that if the member call selects a method/operator `f` that
93// is not const-qualified, then we also consider that the object is
94// not mutated if:
95// - (A) there is a const-qualified overload `cf` of `f` that has
96// the
97// same ref-qualifiers;
98// - (B) * `f` returns a value, or
99// * if `f` returns a `T&`, `cf` returns a `const T&` (up to
100// possible aliases such as `reference` and
101// `const_reference`), or
102// * if `f` returns a `T*`, `cf` returns a `const T*` (up to
103// possible aliases).
104// - (C) the result of the call is not mutated.
105//
106// The assumption that `cf` has the same semantics as `f`.
107// For example:
108// - In `std::vector<T> v; const T t = v[...];`, we consider that
109// expression `v[...]` does not mutate `v` as
110// `T& std::vector<T>::operator[]` has a const overload
111// `const T& std::vector<T>::operator[] const`, and the
112// result expression of type `T&` is only used as a `const T&`;
113// - In `std::map<K, V> m; V v = m.at(...);`, we consider
114// `m.at(...)` to be an immutable access for the same reason.
115// However:
116// - In `std::map<K, V> m; const V v = m[...];`, We consider that
117// `m[...]` mutates `m` as `V& std::map<K, V>::operator[]` does
118// not have a const overload.
119// - In `std::vector<T> v; T& t = v[...];`, we consider that
120// expression `v[...]` mutates `v` as the result is kept as a
121// mutable reference.
122//
123// This function checks (A) ad (B), but the caller should make sure that the
124// object is not mutated through the return value.
125bool isLikelyShallowConst(const CXXMethodDecl &M) {
126 assert(!M.isConst());
127 // The method can mutate our variable.
128
129 // (A)
130 const CXXMethodDecl *ConstOverload = findConstOverload(D: M);
131 if (ConstOverload == nullptr) {
132 return false;
133 }
134
135 // (B)
136 const QualType CallTy = M.getReturnType().getCanonicalType();
137 const QualType OverloadTy = ConstOverload->getReturnType().getCanonicalType();
138 if (CallTy->isReferenceType()) {
139 return OverloadTy->isReferenceType() &&
140 pointsToSameTypeIgnoringConst(A: CallTy, B: OverloadTy);
141 }
142 if (CallTy->isPointerType()) {
143 return OverloadTy->isPointerType() &&
144 pointsToSameTypeIgnoringConst(A: CallTy, B: OverloadTy);
145 }
146 return isSameTypeIgnoringConst(A: CallTy, B: OverloadTy);
147}
148
149// A matcher that matches DeclRefExprs that are used in ways such that the
150// underlying declaration is not modified.
151// If the declaration is of pointer type, `Indirections` specifies the level
152// of indirection of the object whose mutations we are tracking.
153//
154// For example, given:
155// ```
156// int i;
157// int* p;
158// p = &i; // (A)
159// *p = 3; // (B)
160// ```
161//
162// `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(0))` matches
163// (B), but `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(1))`
164// matches (A).
165//
166AST_MATCHER_P(DeclRefExpr, doesNotMutateObject, int, Indirections) {
167 // We walk up the parents of the DeclRefExpr recursively. There are a few
168 // kinds of expressions:
169 // - Those that cannot be used to mutate the underlying variable. We can stop
170 // recursion there.
171 // - Those that can be used to mutate the underlying variable in analyzable
172 // ways (such as taking the address or accessing a subobject). We have to
173 // examine the parents.
174 // - Those that we don't know how to analyze. In that case we stop there and
175 // we assume that they can modify the expression.
176
177 struct StackEntry {
178 StackEntry(const Expr *E, int Indirections)
179 : E(E), Indirections(Indirections) {}
180 // The expression to analyze.
181 const Expr *E;
182 // The number of pointer indirections of the object being tracked (how
183 // many times an address was taken).
184 int Indirections;
185 };
186
187 llvm::SmallVector<StackEntry, 4> Stack;
188 Stack.emplace_back(Args: &Node, Args: Indirections);
189 ASTContext &Ctx = Finder->getASTContext();
190
191 while (!Stack.empty()) {
192 const StackEntry Entry = Stack.back();
193 Stack.pop_back();
194
195 // If the expression type is const-qualified at the appropriate indirection
196 // level then we can not mutate the object.
197 QualType Ty = Entry.E->getType().getCanonicalType();
198 for (int I = 0; I < Entry.Indirections; ++I) {
199 assert(Ty->isPointerType());
200 Ty = Ty->getPointeeType().getCanonicalType();
201 }
202 if (Ty->isVoidType() || Ty.isConstQualified())
203 continue;
204
205 // Otherwise we have to look at the parents to see how the expression is
206 // used.
207 const DynTypedNodeList Parents = Ctx.getParents(Node: *Entry.E);
208 // Note: most nodes have a single parents, but there exist nodes that have
209 // several parents, such as `InitListExpr` that have semantic and syntactic
210 // forms.
211 for (const auto &Parent : Parents) {
212 if (Parent.get<CompoundStmt>()) {
213 // Unused block-scope statement.
214 continue;
215 }
216 const Expr *const P = Parent.get<Expr>();
217 if (P == nullptr) {
218 // `Parent` is not an expr (e.g. a `VarDecl`).
219 // The case of binding to a `const&` or `const*` variable is handled by
220 // the fact that there is going to be a `NoOp` cast to const below the
221 // `VarDecl`, so we're not even going to get there.
222 // The case of copying into a value-typed variable is handled by the
223 // rvalue cast.
224 // This triggers only when binding to a mutable reference/ptr variable.
225 // FIXME: When we take a mutable reference we could keep checking the
226 // new variable for const usage only.
227 return false;
228 }
229 // Cosmetic nodes.
230 if (isa<ParenExpr>(Val: P) || isa<MaterializeTemporaryExpr>(Val: P)) {
231 Stack.emplace_back(Args: P, Args: Entry.Indirections);
232 continue;
233 }
234 if (const auto *const Cast = dyn_cast<CastExpr>(Val: P)) {
235 switch (Cast->getCastKind()) {
236 // NoOp casts are used to add `const`. We'll check whether adding that
237 // const prevents modification when we process the cast.
238 case CK_NoOp:
239 // These do nothing w.r.t. to mutability.
240 case CK_BaseToDerived:
241 case CK_DerivedToBase:
242 case CK_UncheckedDerivedToBase:
243 case CK_Dynamic:
244 case CK_BaseToDerivedMemberPointer:
245 case CK_DerivedToBaseMemberPointer:
246 Stack.emplace_back(Args: Cast, Args: Entry.Indirections);
247 continue;
248 case CK_ToVoid:
249 case CK_PointerToBoolean:
250 // These do not mutate the underlying variable.
251 continue;
252 case CK_LValueToRValue: {
253 // An rvalue is immutable.
254 if (Entry.Indirections == 0)
255 continue;
256 Stack.emplace_back(Args: Cast, Args: Entry.Indirections);
257 continue;
258 }
259 default:
260 // Bail out on casts that we cannot analyze.
261 return false;
262 }
263 }
264 if (const auto *const Member = dyn_cast<MemberExpr>(Val: P)) {
265 if (const auto *const Method =
266 dyn_cast<CXXMethodDecl>(Val: Member->getMemberDecl())) {
267 if (Method->isConst() || Method->isStatic()) {
268 // The method call cannot mutate our variable.
269 continue;
270 }
271 if (isLikelyShallowConst(M: *Method)) {
272 // We still have to check that the object is not modified through
273 // the method's return value (C).
274 const auto MemberParents = Ctx.getParents(Node: *Member);
275 assert(MemberParents.size() == 1);
276 const auto *Call = MemberParents[0].get<CallExpr>();
277 // If `o` is an object of class type and `f` is a member function,
278 // then `o.f` has to be used as part of a call expression.
279 assert(Call != nullptr && "member function has to be called");
280 Stack.emplace_back(
281 Call,
282 Method->getReturnType().getCanonicalType()->isPointerType()
283 ? 1
284 : 0);
285 continue;
286 }
287 return false;
288 }
289 Stack.emplace_back(Args: Member, Args: 0);
290 continue;
291 }
292 if (const auto *const OpCall = dyn_cast<CXXOperatorCallExpr>(Val: P)) {
293 // Operator calls have function call syntax. The `*this` parameter
294 // is the first parameter.
295 if (OpCall->getNumArgs() == 0 || OpCall->getArg(0) != Entry.E) {
296 return false;
297 }
298 const auto *const Method =
299 dyn_cast_or_null<CXXMethodDecl>(OpCall->getDirectCallee());
300
301 if (Method == nullptr) {
302 // This is not a member operator. Typically, a friend operator. These
303 // are handled like function calls.
304 return false;
305 }
306
307 if (Method->isConst() || Method->isStatic()) {
308 continue;
309 }
310 if (isLikelyShallowConst(*Method)) {
311 // We still have to check that the object is not modified through
312 // the operator's return value (C).
313 Stack.emplace_back(
314 OpCall,
315 Method->getReturnType().getCanonicalType()->isPointerType() ? 1
316 : 0);
317 continue;
318 }
319 return false;
320 }
321
322 if (const auto *const Op = dyn_cast<UnaryOperator>(Val: P)) {
323 switch (Op->getOpcode()) {
324 case UO_AddrOf:
325 Stack.emplace_back(Args: Op, Args: Entry.Indirections + 1);
326 continue;
327 case UO_Deref:
328 assert(Entry.Indirections > 0);
329 Stack.emplace_back(Args: Op, Args: Entry.Indirections - 1);
330 continue;
331 default:
332 // Bail out on unary operators that we cannot analyze.
333 return false;
334 }
335 }
336
337 // Assume any other expression can modify the underlying variable.
338 return false;
339 }
340 }
341
342 // No parent can modify the variable.
343 return true;
344}
345
346} // namespace
347
348SmallPtrSet<const DeclRefExpr *, 16>
349constReferenceDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt,
350 ASTContext &Context, int Indirections) {
351 auto Matches = match(findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl))),
352 doesNotMutateObject(Indirections))
353 .bind("declRef")),
354 Stmt, Context);
355 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;
356 extractNodesByIdTo(Matches, "declRef", DeclRefs);
357
358 return DeclRefs;
359}
360
361bool isOnlyUsedAsConst(const VarDecl &Var, const Stmt &Stmt,
362 ASTContext &Context, int Indirections) {
363 // Collect all DeclRefExprs to the loop variable and all CallExprs and
364 // CXXConstructExprs where the loop variable is used as argument to a const
365 // reference parameter.
366 // If the difference is empty it is safe for the loop variable to be a const
367 // reference.
368 auto AllDeclRefs = allDeclRefExprs(Var, Stmt, Context);
369 auto ConstReferenceDeclRefs =
370 constReferenceDeclRefExprs(Var, Stmt, Context, Indirections);
371 return isSetDifferenceEmpty(AllDeclRefs, ConstReferenceDeclRefs);
372}
373
374SmallPtrSet<const DeclRefExpr *, 16>
375allDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt, ASTContext &Context) {
376 auto Matches = match(
377 findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef")),
378 Stmt, Context);
379 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;
380 extractNodesByIdTo(Matches, "declRef", DeclRefs);
381 return DeclRefs;
382}
383
384SmallPtrSet<const DeclRefExpr *, 16>
385allDeclRefExprs(const VarDecl &VarDecl, const Decl &Decl, ASTContext &Context) {
386 auto Matches = match(
387 decl(forEachDescendant(
388 declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef"))),
389 Decl, Context);
390 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;
391 extractNodesByIdTo(Matches, "declRef", DeclRefs);
392 return DeclRefs;
393}
394
395bool isCopyConstructorArgument(const DeclRefExpr &DeclRef, const Decl &Decl,
396 ASTContext &Context) {
397 auto UsedAsConstRefArg = forEachArgumentWithParam(
398 declRefExpr(equalsNode(&DeclRef)),
399 parmVarDecl(hasType(InnerMatcher: matchers::isReferenceToConst())));
400 auto Matches = match(
401 decl(hasDescendant(
402 cxxConstructExpr(UsedAsConstRefArg, hasDeclaration(InnerMatcher: cxxConstructorDecl(
403 isCopyConstructor())))
404 .bind("constructExpr"))),
405 Decl, Context);
406 return !Matches.empty();
407}
408
409bool isCopyAssignmentArgument(const DeclRefExpr &DeclRef, const Decl &Decl,
410 ASTContext &Context) {
411 auto UsedAsConstRefArg = forEachArgumentWithParam(
412 declRefExpr(equalsNode(&DeclRef)),
413 parmVarDecl(hasType(InnerMatcher: matchers::isReferenceToConst())));
414 auto Matches = match(
415 decl(hasDescendant(
416 cxxOperatorCallExpr(UsedAsConstRefArg, hasOverloadedOperatorName(Name: "="),
417 callee(InnerMatcher: cxxMethodDecl(isCopyAssignmentOperator())))
418 .bind("operatorCallExpr"))),
419 Decl, Context);
420 return !Matches.empty();
421}
422
423} // namespace clang::tidy::utils::decl_ref_expr
424

source code of clang-tools-extra/clang-tidy/utils/DeclRefExprUtils.cpp