1//===- LifetimeAnnotations.cpp - -*--------------- C++------------------*-===//
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/LifetimeSafety/LifetimeAnnotations.h"
9#include "clang/AST/ASTContext.h"
10#include "clang/AST/Attr.h"
11#include "clang/AST/Decl.h"
12#include "clang/AST/DeclCXX.h"
13#include "clang/AST/DeclTemplate.h"
14#include "clang/AST/Type.h"
15#include "clang/AST/TypeLoc.h"
16#include "llvm/ADT/StringSet.h"
17
18namespace clang::lifetimes {
19
20const FunctionDecl *
21getDeclWithMergedLifetimeBoundAttrs(const FunctionDecl *FD) {
22 return FD != nullptr ? FD->getMostRecentDecl() : nullptr;
23}
24
25const CXXMethodDecl *
26getDeclWithMergedLifetimeBoundAttrs(const CXXMethodDecl *CMD) {
27 const FunctionDecl *FD = CMD;
28 return cast_if_present<CXXMethodDecl>(
29 Val: getDeclWithMergedLifetimeBoundAttrs(FD));
30}
31
32bool isNormalAssignmentOperator(const FunctionDecl *FD) {
33 OverloadedOperatorKind OO = FD->getDeclName().getCXXOverloadedOperator();
34 bool IsAssignment = OO == OO_Equal || isCompoundAssignmentOperator(Kind: OO);
35 if (!IsAssignment)
36 return false;
37 QualType RetT = FD->getReturnType();
38 if (!RetT->isLValueReferenceType())
39 return false;
40 ASTContext &Ctx = FD->getASTContext();
41 QualType LHST;
42 auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
43 if (MD && MD->isCXXInstanceMember())
44 LHST = Ctx.getLValueReferenceType(T: MD->getFunctionObjectParameterType());
45 else
46 LHST = FD->getParamDecl(i: 0)->getType();
47 return Ctx.hasSameType(T1: RetT, T2: LHST);
48}
49
50bool isAssignmentOperatorLifetimeBound(const CXXMethodDecl *CMD) {
51 CMD = getDeclWithMergedLifetimeBoundAttrs(CMD);
52 return CMD && isNormalAssignmentOperator(FD: CMD) && CMD->param_size() == 1 &&
53 CMD->getParamDecl(i: 0)->hasAttr<clang::LifetimeBoundAttr>();
54}
55
56/// Check if a function has a lifetimebound attribute on its function type
57/// (which represents the implicit 'this' parameter for methods).
58/// Returns the attribute if found, nullptr otherwise.
59static const LifetimeBoundAttr *
60getLifetimeBoundAttrFromFunctionType(const TypeSourceInfo &TSI) {
61 // Walk through the type layers looking for a lifetimebound attribute.
62 TypeLoc TL = TSI.getTypeLoc();
63 while (true) {
64 auto ATL = TL.getAsAdjusted<AttributedTypeLoc>();
65 if (!ATL)
66 break;
67 if (auto *LBAttr = ATL.getAttrAs<LifetimeBoundAttr>())
68 return LBAttr;
69 TL = ATL.getModifiedLoc();
70 }
71 return nullptr;
72}
73
74bool implicitObjectParamIsLifetimeBound(const FunctionDecl *FD) {
75 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
76 // Attribute merging doesn't work well with attributes on function types (like
77 // 'this' param). We need to check all redeclarations.
78 auto CheckRedecls = [](const FunctionDecl *F) {
79 return llvm::any_of(Range: F->redecls(), P: [](const FunctionDecl *Redecl) {
80 const TypeSourceInfo *TSI = Redecl->getTypeSourceInfo();
81 return TSI && getLifetimeBoundAttrFromFunctionType(TSI: *TSI);
82 });
83 };
84
85 if (CheckRedecls(FD))
86 return true;
87 if (const FunctionDecl *Pattern = FD->getTemplateInstantiationPattern();
88 Pattern && CheckRedecls(Pattern))
89 return true;
90 return isNormalAssignmentOperator(FD);
91}
92
93bool isInStlNamespace(const Decl *D) {
94 const DeclContext *DC = D->getDeclContext();
95 if (!DC)
96 return false;
97 if (const auto *ND = dyn_cast<NamespaceDecl>(Val: DC))
98 if (const IdentifierInfo *II = ND->getIdentifier()) {
99 StringRef Name = II->getName();
100 if (Name.size() >= 2 && Name.front() == '_' &&
101 (Name[1] == '_' || isUppercase(c: Name[1])))
102 return true;
103 }
104 return DC->isStdNamespace();
105}
106
107bool isPointerLikeType(QualType QT) {
108 return isGslPointerType(QT) || QT->isPointerType() || QT->isNullPtrType();
109}
110
111static bool isReferenceOrPointerLikeType(QualType QT) {
112 return QT->isReferenceType() || isPointerLikeType(QT);
113}
114
115bool shouldTrackImplicitObjectArg(const CXXMethodDecl *Callee,
116 bool RunningUnderLifetimeSafety) {
117 if (!Callee)
118 return false;
119 if (auto *Conv = dyn_cast<CXXConversionDecl>(Val: Callee))
120 if (isGslPointerType(QT: Conv->getConversionType()) &&
121 Callee->getParent()->hasAttr<OwnerAttr>())
122 return true;
123 if (!isGslPointerType(QT: Callee->getFunctionObjectParameterType()) &&
124 !isGslOwnerType(QT: Callee->getFunctionObjectParameterType()))
125 return false;
126
127 // Begin and end iterators.
128 static const llvm::StringSet<> IteratorMembers = {
129 "begin", "end", "rbegin", "rend", "cbegin", "cend", "crbegin", "crend"};
130 static const llvm::StringSet<> InnerPointerGetters = {
131 // Inner pointer getters.
132 "c_str", "data", "get"};
133 static const llvm::StringSet<> ContainerFindFns = {
134 // Map and set types.
135 "find", "equal_range", "lower_bound", "upper_bound"};
136 // Track dereference operator and transparent functions like begin(), get(),
137 // etc. for all GSL pointers. Only do so for lifetime safety analysis and not
138 // for Sema's statement-local analysis as it starts to have false-positives.
139 if (RunningUnderLifetimeSafety &&
140 isGslPointerType(QT: Callee->getFunctionObjectParameterType()) &&
141 isReferenceOrPointerLikeType(QT: Callee->getReturnType())) {
142 if (Callee->getOverloadedOperator() == OverloadedOperatorKind::OO_Star ||
143 Callee->getOverloadedOperator() == OverloadedOperatorKind::OO_Arrow)
144 return true;
145 if (Callee->getIdentifier() &&
146 (IteratorMembers.contains(key: Callee->getName()) ||
147 InnerPointerGetters.contains(key: Callee->getName())))
148 return true;
149 }
150
151 if (!isInStlNamespace(D: Callee->getParent()))
152 return false;
153
154 if (isPointerLikeType(QT: Callee->getReturnType())) {
155 if (!Callee->getIdentifier())
156 // e.g., std::optional<T>::operator->() returns T*.
157 return RunningUnderLifetimeSafety
158 ? Callee->getParent()->hasAttr<OwnerAttr>() &&
159 Callee->getOverloadedOperator() ==
160 OverloadedOperatorKind::OO_Arrow
161 : false;
162 return IteratorMembers.contains(key: Callee->getName()) ||
163 InnerPointerGetters.contains(key: Callee->getName()) ||
164 ContainerFindFns.contains(key: Callee->getName());
165 }
166 if (Callee->getReturnType()->isReferenceType()) {
167 if (!Callee->getIdentifier()) {
168 auto OO = Callee->getOverloadedOperator();
169 if (!Callee->getParent()->hasAttr<OwnerAttr>())
170 return false;
171 return OO == OverloadedOperatorKind::OO_Subscript ||
172 OO == OverloadedOperatorKind::OO_Star;
173 }
174 return llvm::StringSwitch<bool>(Callee->getName())
175 .Cases(CaseStrings: {"front", "back", "at", "top", "value"}, Value: true)
176 .Default(Value: false);
177 }
178 return false;
179}
180
181bool shouldTrackFirstArgument(const FunctionDecl *FD) {
182 if (!FD->getIdentifier() || FD->getNumParams() < 1)
183 return false;
184 if (!FD->isInStdNamespace())
185 return false;
186 // Track std:: algorithm functions that return an iterator whose lifetime is
187 // bound to the first argument.
188 if (FD->getNumParams() >= 2 && FD->isInStdNamespace() &&
189 isGslPointerType(QT: FD->getReturnType())) {
190 if (llvm::StringSwitch<bool>(FD->getName())
191 .Cases(
192 CaseStrings: {
193 "find",
194 "find_if",
195 "find_if_not",
196 "find_first_of",
197 "adjacent_find",
198 "search",
199 "find_end",
200 "lower_bound",
201 "upper_bound",
202 "partition_point",
203 },
204 Value: true)
205 .Default(Value: false))
206 return true;
207 }
208 const auto *RD = FD->getParamDecl(i: 0)->getType()->getPointeeCXXRecordDecl();
209 if (!RD || !RD->isInStdNamespace())
210 return false;
211 if (!RD->hasAttr<PointerAttr>() && !RD->hasAttr<OwnerAttr>())
212 return false;
213
214 if (FD->getNumParams() != 1)
215 return false;
216
217 if (FD->getReturnType()->isPointerType() ||
218 isGslPointerType(QT: FD->getReturnType())) {
219 return llvm::StringSwitch<bool>(FD->getName())
220 .Cases(CaseStrings: {"begin", "rbegin", "cbegin", "crbegin"}, Value: true)
221 .Cases(CaseStrings: {"end", "rend", "cend", "crend"}, Value: true)
222 .Case(S: "data", Value: true)
223 .Default(Value: false);
224 }
225 if (FD->getReturnType()->isReferenceType()) {
226 return llvm::StringSwitch<bool>(FD->getName())
227 .Cases(CaseStrings: {"get", "any_cast"}, Value: true)
228 .Default(Value: false);
229 }
230 return false;
231}
232
233template <typename T> static bool isRecordWithAttr(QualType Type) {
234 auto *RD = Type->getAsCXXRecordDecl();
235 if (!RD)
236 return false;
237 // Generally, if a primary template class declaration is annotated with an
238 // attribute, all its specializations generated from template instantiations
239 // should inherit the attribute.
240 //
241 // However, since lifetime analysis occurs during parsing, we may encounter
242 // cases where a full definition of the specialization is not required. In
243 // such cases, the specialization declaration remains incomplete and lacks the
244 // attribute. Therefore, we fall back to checking the primary template class.
245 //
246 // Note: it is possible for a specialization declaration to have an attribute
247 // even if the primary template does not.
248 //
249 // FIXME: What if the primary template and explicit specialization
250 // declarations have conflicting attributes? We should consider diagnosing
251 // this scenario.
252 bool Result = RD->hasAttr<T>();
253
254 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: RD))
255 Result |= CTSD->getSpecializedTemplate()->getTemplatedDecl()->hasAttr<T>();
256
257 return Result;
258}
259
260bool isGslPointerType(QualType QT) { return isRecordWithAttr<PointerAttr>(Type: QT); }
261bool isGslOwnerType(QualType QT) { return isRecordWithAttr<OwnerAttr>(Type: QT); }
262
263static StringRef getName(const CXXRecordDecl &RD) {
264 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: &RD))
265 return CTSD->getSpecializedTemplate()->getName();
266 if (RD.getIdentifier())
267 return RD.getName();
268 return "";
269}
270
271static bool isStdUniquePtr(const CXXRecordDecl &RD) {
272 return RD.isInStdNamespace() && getName(RD) == "unique_ptr";
273}
274
275bool isUniquePtrRelease(const CXXMethodDecl &MD) {
276 return MD.getIdentifier() && MD.getName() == "release" &&
277 MD.getNumParams() == 0 && isStdUniquePtr(RD: *MD.getParent());
278}
279
280bool isContainerInvalidationMethod(const CXXMethodDecl &MD) {
281 const CXXRecordDecl *RD = MD.getParent();
282 if (!isInStlNamespace(D: RD))
283 return false;
284
285 // `pop_back` is excluded: it only invalidates references to the removed
286 // element, not to other elements.
287 static const llvm::StringSet<> Vector = {// Insertion
288 "insert", "emplace", "emplace_back",
289 "push_back", "insert_range",
290 "append_range",
291 // Removal
292 "erase", "clear",
293 // Memory management
294 "reserve", "resize", "shrink_to_fit",
295 // Assignment
296 "assign", "assign_range"};
297
298 // `pop_*` methods are excluded: they only invalidate references to the
299 // removed element, not to other elements.
300 static const llvm::StringSet<> Deque = {// Insertion
301 "insert", "emplace", "insert_range",
302 // Removal
303 "erase", "clear",
304 // Memory management
305 "resize", "shrink_to_fit",
306 // Assignment
307 "assign", "assign_range"};
308
309 static const llvm::StringSet<> String = {
310 // Insertion
311 "insert", "push_back", "append", "replace", "replace_with_range",
312 "insert_range", "append_range",
313 // Removal
314 "pop_back", "erase", "clear",
315 // Memory management
316 "reserve", "resize", "resize_and_overwrite", "shrink_to_fit",
317 // Assignment
318 "swap", "assign", "assign_range"};
319
320 // FIXME: Add queue and stack and check for underlying container
321 // (e.g. no invalidation for std::list).
322 static const llvm::StringSet<> PriorityQueue = {// Insertion
323 "push", "emplace",
324 "push_range",
325 // Removal
326 "pop"};
327
328 // `erase` and `extract` are excluded: they only affect the removed element,
329 // not to other elements.
330 static const llvm::StringSet<> NodeBased = {// Removal
331 "clear"};
332
333 // For `flat_*` container adaptors, `try_emplace` and `insert_or_assign`
334 // only exist on `flat_map`. Listing them here is harmless since the methods
335 // won't be found on other types.
336 static const llvm::StringSet<> Flat = {// Insertion
337 "insert", "emplace", "emplace_hint",
338 "try_emplace", "insert_or_assign",
339 "insert_range", "merge",
340 // Removal
341 "extract", "erase", "clear",
342 // Assignment
343 "replace"};
344
345 const StringRef ContainerName = getName(RD: *RD);
346 // TODO: Consider caching this lookup by CXXMethodDecl pointer if this
347 // StringSwitch becomes a performance bottleneck.
348 const llvm::StringSet<> *InvalidatingMethods =
349 llvm::StringSwitch<const llvm::StringSet<> *>(ContainerName)
350 .Case(S: "vector", Value: &Vector)
351 .Case(S: "basic_string", Value: &String)
352 .Case(S: "deque", Value: &Deque)
353 .Case(S: "priority_queue", Value: &PriorityQueue)
354 .Cases(CaseStrings: {"set", "multiset", "map", "multimap", "unordered_set",
355 "unordered_multiset", "unordered_map", "unordered_multimap"},
356 Value: &NodeBased)
357 .Cases(CaseStrings: {"flat_map", "flat_set", "flat_multimap", "flat_multiset"},
358 Value: &Flat)
359 .Default(Value: nullptr);
360
361 if (!InvalidatingMethods)
362 return false;
363
364 // Handle Operators via OverloadedOperatorKind
365 OverloadedOperatorKind OO = MD.getOverloadedOperator();
366 if (OO != OO_None) {
367 switch (OO) {
368 case OO_Equal: // operator= : Always invalidates (Assignment)
369 case OO_PlusEqual: // operator+= : Append (String/Vector)
370 return true;
371 case OO_Subscript: // operator[] : Invalidation only for
372 // `flat_map` (Insert-or-access).
373 // `map` and `unordered_map` are excluded.
374 return ContainerName == "flat_map";
375 default:
376 return false;
377 }
378 }
379
380 if (!MD.getIdentifier())
381 return false;
382
383 return InvalidatingMethods->contains(key: MD.getName());
384}
385} // namespace clang::lifetimes
386