1//===- Origins.cpp - Origin Implementation -----------------------*- 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
9#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
10#include "clang/AST/ASTContext.h"
11#include "clang/AST/Attr.h"
12#include "clang/AST/Decl.h"
13#include "clang/AST/DeclCXX.h"
14#include "clang/AST/DeclTemplate.h"
15#include "clang/AST/Expr.h"
16#include "clang/AST/ExprCXX.h"
17#include "clang/AST/RecursiveASTVisitor.h"
18#include "clang/AST/TypeBase.h"
19#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h"
20#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeStats.h"
21#include "clang/Analysis/AnalysisDeclContext.h"
22#include "llvm/ADT/StringMap.h"
23
24namespace clang::lifetimes::internal {
25namespace {
26/// A utility class to traverse the function body in the analysis
27/// context and collect the count of expressions with missing origins.
28class MissingOriginCollector
29 : public RecursiveASTVisitor<MissingOriginCollector> {
30public:
31 MissingOriginCollector(
32 const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList,
33 const OriginManager &OM, LifetimeSafetyStats &LSStats)
34 : ExprToOriginList(ExprToOriginList), OM(OM), LSStats(LSStats) {}
35 bool VisitExpr(Expr *E) {
36 if (!OM.hasOrigins(E))
37 return true;
38 // Check if we have an origin for this expression.
39 if (!ExprToOriginList.contains(Val: E)) {
40 // No origin found: count this as missing origin.
41 LSStats.ExprTypeToMissingOriginCount[E->getType().getTypePtr()]++;
42 LSStats.ExprStmtClassToMissingOriginCount[std::string(
43 E->getStmtClassName())]++;
44 }
45 return true;
46 }
47
48private:
49 const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList;
50 const OriginManager &OM;
51 LifetimeSafetyStats &LSStats;
52};
53
54class LifetimeAnnotatedOriginTypeCollector
55 : public RecursiveASTVisitor<LifetimeAnnotatedOriginTypeCollector> {
56public:
57 bool VisitCallExpr(const CallExpr *CE) {
58 // Indirect calls (e.g., function pointers) are skipped because lifetime
59 // annotations currently apply to declarations, not types.
60 if (const auto *FD = CE->getDirectCallee())
61 collect(FD, RetType: FD->getReturnType());
62 return true;
63 }
64
65 bool VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
66 collect(FD: CCE->getConstructor(), RetType: CCE->getType());
67 return true;
68 }
69
70 bool shouldVisitLambdaBody() const { return false; }
71 bool shouldVisitTemplateInstantiations() const { return true; }
72
73 const llvm::SmallVector<QualType> &getCollectedTypes() const {
74 return CollectedTypes;
75 }
76
77private:
78 llvm::SmallVector<QualType> CollectedTypes;
79
80 void collect(const FunctionDecl *FD, QualType RetType) {
81 if (!FD)
82 return;
83 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
84
85 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
86 MD && MD->isInstance() && !isa<CXXConstructorDecl>(Val: MD) &&
87 implicitObjectParamIsLifetimeBound(FD: MD)) {
88 CollectedTypes.push_back(Elt: RetType);
89 return;
90 }
91
92 for (const auto *Param : FD->parameters()) {
93 if (Param->hasAttr<LifetimeBoundAttr>()) {
94 CollectedTypes.push_back(Elt: RetType);
95 return;
96 }
97 }
98 }
99};
100
101} // namespace
102
103bool OriginManager::hasOrigins(QualType QT, bool IntrinsicOnly) const {
104 if (QT->isPointerOrReferenceType() || isGslPointerType(QT))
105 return true;
106 if (!IntrinsicOnly &&
107 LifetimeAnnotatedOriginTypes.contains(V: QT.getCanonicalType().getTypePtr()))
108 return true;
109 // An `_Atomic(T)` wraps T transparently for lifetime purposes (the atomic
110 // holds the same value); see through it.
111 if (const auto *AT = QT->getAs<AtomicType>())
112 return hasOrigins(QT: AT->getValueType(), IntrinsicOnly);
113 const auto *RD = QT->getAsCXXRecordDecl();
114 if (!RD)
115 return false;
116 // Standard library callable wrappers (e.g., std::function) can propagate the
117 // stored lambda's origins.
118 if (isStdCallableWrapperType(RD))
119 return true;
120 // TODO: Limit to lambdas for now. This will be extended to user-defined
121 // structs with pointer-like fields.
122 if (!RD->isLambda())
123 return false;
124 for (const auto *FD : RD->fields())
125 if (hasOrigins(QT: FD->getType(), IntrinsicOnly))
126 return true;
127 return false;
128}
129
130/// Determines if an expression has origins that need to be tracked.
131///
132/// An expression has origins if:
133/// - It's a glvalue (has addressable storage), OR
134/// - Its type is pointer-like (pointer, reference, or gsl::Pointer), OR
135/// - Its type is registered for origin tracking (e.g., return type of a
136/// [[clang::lifetimebound]] function)
137///
138/// Examples:
139/// - `int x; x` : has origin (glvalue)
140/// - `int* p; p` : has 2 origins (1 for glvalue and 1 for pointer type)
141/// - `std::string_view{}` : has 1 origin (prvalue of pointer type)
142/// - `42` : no origin (prvalue of non-pointer type)
143/// - `x + y` : (where x, y are int) → no origin (prvalue of non-pointer type)
144bool OriginManager::hasOrigins(const Expr *E) const {
145 return E->isGLValue() || hasOrigins(QT: E->getType());
146}
147
148/// Returns true if the declaration has its own storage that can be borrowed.
149///
150/// References generally have no storage - they are aliases to other storage.
151/// For example:
152/// int x; // has storage (can issue loans to x's storage)
153/// int& r = x; // no storage (r is an alias to x's storage)
154/// int* p; // has storage (the pointer variable p itself has storage)
155///
156/// TODO: Handle lifetime extension. References initialized by temporaries
157/// can have storage when the temporary's lifetime is extended:
158/// const int& r = 42; // temporary has storage, lifetime extended
159/// Foo&& f = Foo{}; // temporary has storage, lifetime extended
160/// Currently, this function returns false for all reference types.
161bool doesDeclHaveStorage(const ValueDecl *D) {
162 return !D->getType()->isReferenceType();
163}
164
165OriginManager::OriginManager(const AnalysisDeclContext &AC)
166 : AST(AC.getASTContext()) {
167 collectLifetimeAnnotatedOriginTypes(AC);
168 initializeThisOrigins(D: AC.getDecl());
169}
170
171void OriginManager::initializeThisOrigins(const Decl *D) {
172 const auto *MD = llvm::dyn_cast_or_null<CXXMethodDecl>(Val: D);
173 if (!MD || !MD->isInstance())
174 return;
175 // Lambdas can capture 'this' from the surrounding context, but in that case
176 // 'this' does not refer to the lambda object itself.
177 if (const CXXRecordDecl *P = MD->getParent(); P && P->isLambda())
178 return;
179 ThisOrigins = buildListForType(QT: MD->getThisType(), Node: MD);
180}
181
182OriginList *OriginManager::createNode(const ValueDecl *D, QualType QT) {
183 OriginID NewID = getNextOriginID();
184 AllOrigins.emplace_back(Args&: NewID, Args&: D, Args: QT.getTypePtrOrNull());
185 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
186}
187
188OriginList *OriginManager::createNode(const Expr *E, QualType QT) {
189 OriginID NewID = getNextOriginID();
190 AllOrigins.emplace_back(Args&: NewID, Args&: E, Args: QT.getTypePtrOrNull());
191 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
192}
193
194OriginList *OriginManager::createSingleOriginList(OriginID OID) {
195 return new (ListAllocator.Allocate<OriginList>()) OriginList(OID);
196}
197
198template <typename T>
199OriginList *OriginManager::buildListForType(QualType QT, const T *Node) {
200 assert(hasOrigins(QT) && "buildListForType called for non-pointer type");
201 // `_Atomic(T)` is transparent for lifetime purposes: build the node for T.
202 if (const auto *AT = QT->getAs<AtomicType>())
203 return buildListForType(AT->getValueType(), Node);
204 OriginList *Head = createNode(Node, QT);
205
206 if (QT->isPointerOrReferenceType()) {
207 QualType PointeeTy = QT->getPointeeType();
208 // We recurse if the pointee type is pointer-like, to build the next
209 // level in the origin tree. E.g., for T*& / View&.
210 if (hasOrigins(QT: PointeeTy))
211 Head->setInnerOriginList(buildListForType(PointeeTy, Node));
212 }
213 return Head;
214}
215
216OriginList *OriginManager::getOrCreateList(const ValueDecl *D) {
217 if (!hasOrigins(QT: D->getType()))
218 return nullptr;
219 auto It = DeclToList.find(Val: D);
220 if (It != DeclToList.end())
221 return It->second;
222 return DeclToList[D] = buildListForType(QT: D->getType(), Node: D);
223}
224
225OriginList *OriginManager::getOrCreateList(const Expr *E) {
226 if (auto *ParenIgnored = E->IgnoreParens(); ParenIgnored != E)
227 return getOrCreateList(E: ParenIgnored);
228 // We do not see CFG stmts for ExprWithCleanups. Simply peel them.
229 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Val: E))
230 return getOrCreateList(E: EWC->getSubExpr());
231
232 // An OpaqueValueExpr is a placeholder for an already-evaluated subexpression
233 // (e.g. the common operand of `a ?: b`) and is not itself a CFG statement, so
234 // reuse its source's origins rather than flowing into a fresh node.
235 if (const auto *OVE = dyn_cast<OpaqueValueExpr>(Val: E))
236 if (const Expr *Src = OVE->getSourceExpr())
237 return getOrCreateList(E: Src);
238
239 if (!hasOrigins(E))
240 return nullptr;
241
242 auto It = ExprToList.find(Val: E);
243 if (It != ExprToList.end())
244 return It->second;
245
246 QualType Type = E->getType();
247 // Special handling for 'this' expressions to share origins with the method's
248 // implicit object parameter.
249 if (isa<CXXThisExpr>(Val: E) && ThisOrigins)
250 return *ThisOrigins;
251
252 // Special handling for expressions referring to a decl to share origins with
253 // the underlying decl.
254 const ValueDecl *ReferencedDecl = nullptr;
255 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E))
256 ReferencedDecl = DRE->getDecl();
257 else if (auto *ME = dyn_cast<MemberExpr>(Val: E))
258 if (auto *Field = dyn_cast<FieldDecl>(Val: ME->getMemberDecl());
259 Field && isa<CXXThisExpr>(Val: ME->getBase()->IgnoreParenImpCasts()))
260 ReferencedDecl = Field;
261 if (ReferencedDecl) {
262 OriginList *Head = nullptr;
263 // For non-reference declarations (e.g., `int* p`), the expression is an
264 // lvalue (addressable) that can be borrowed, so we create an outer origin
265 // for the lvalue itself, with the pointee being the declaration's list.
266 // This models taking the address: `&p` borrows the storage of `p`, not what
267 // `p` points to.
268 if (doesDeclHaveStorage(D: ReferencedDecl)) {
269 Head = createNode(E, QT: QualType{});
270 // This ensures origin sharing: multiple expressions to the same
271 // declaration share the same underlying origins.
272 Head->setInnerOriginList(getOrCreateList(D: ReferencedDecl));
273 } else {
274 // For reference-typed declarations (e.g., `int& r = p`) which have no
275 // storage, the DeclRefExpr directly reuses the declaration's list since
276 // references don't add an extra level of indirection at the expression
277 // level.
278 Head = getOrCreateList(D: ReferencedDecl);
279 }
280 return ExprToList[E] = Head;
281 }
282
283 // If E is an lvalue , it refers to storage. We model this storage as the
284 // first level of origin list, as if it were a reference, because l-values are
285 // addressable.
286 if (E->isGLValue() && !Type->isReferenceType())
287 Type = AST.getLValueReferenceType(T: Type);
288 return ExprToList[E] = buildListForType(QT: Type, Node: E);
289}
290
291void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const {
292 OS << OID << " (";
293 Origin O = getOrigin(ID: OID);
294 if (const ValueDecl *VD = O.getDecl()) {
295 OS << "Decl: " << VD->getNameAsString();
296 } else if (const Expr *E = O.getExpr()) {
297 OS << "Expr: " << E->getStmtClassName();
298 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E)) {
299 if (const ValueDecl *VD = DRE->getDecl())
300 OS << ", Decl: " << VD->getNameAsString();
301 }
302 } else {
303 OS << "Unknown";
304 }
305 if (O.Ty)
306 OS << ", Type : " << QualType(O.Ty, 0).getAsString();
307 OS << ")";
308}
309
310const Origin &OriginManager::getOrigin(OriginID ID) const {
311 assert(ID.Value < AllOrigins.size());
312 return AllOrigins[ID.Value];
313}
314
315void OriginManager::collectMissingOrigins(Stmt &FunctionBody,
316 LifetimeSafetyStats &LSStats) {
317 MissingOriginCollector Collector(this->ExprToList, *this, LSStats);
318 Collector.TraverseStmt(S: const_cast<Stmt *>(&FunctionBody));
319}
320
321void OriginManager::collectLifetimeAnnotatedOriginTypes(
322 const AnalysisDeclContext &AC) {
323 LifetimeAnnotatedOriginTypeCollector Collector;
324 if (Stmt *Body = AC.getBody())
325 Collector.TraverseStmt(S: Body);
326 if (const auto *CD = dyn_cast<CXXConstructorDecl>(Val: AC.getDecl()))
327 for (const auto *Init : CD->inits())
328 Collector.TraverseStmt(S: Init->getInit());
329 for (QualType QT : Collector.getCollectedTypes())
330 registerLifetimeAnnotatedOriginType(QT);
331}
332
333void OriginManager::registerLifetimeAnnotatedOriginType(QualType QT) {
334 if (!QT->getAsCXXRecordDecl() || hasOrigins(QT))
335 return;
336
337 LifetimeAnnotatedOriginTypes.insert(V: QT.getCanonicalType().getTypePtr());
338}
339
340} // namespace clang::lifetimes::internal
341