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
72 const llvm::SmallVector<QualType> &getCollectedTypes() const {
73 return CollectedTypes;
74 }
75
76private:
77 llvm::SmallVector<QualType> CollectedTypes;
78
79 void collect(const FunctionDecl *FD, QualType RetType) {
80 if (!FD)
81 return;
82 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
83
84 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
85 MD && MD->isInstance() && !isa<CXXConstructorDecl>(Val: MD) &&
86 implicitObjectParamIsLifetimeBound(FD: MD)) {
87 CollectedTypes.push_back(Elt: RetType);
88 return;
89 }
90
91 for (const auto *Param : FD->parameters()) {
92 if (Param->hasAttr<LifetimeBoundAttr>()) {
93 CollectedTypes.push_back(Elt: RetType);
94 return;
95 }
96 }
97 }
98};
99
100} // namespace
101
102bool OriginManager::hasOrigins(QualType QT) const {
103 if (QT->isPointerOrReferenceType() || isGslPointerType(QT))
104 return true;
105 if (LifetimeAnnotatedOriginTypes.contains(V: QT.getCanonicalType().getTypePtr()))
106 return true;
107 const auto *RD = QT->getAsCXXRecordDecl();
108 if (!RD)
109 return false;
110 // TODO: Limit to lambdas for now. This will be extended to user-defined
111 // structs with pointer-like fields.
112 if (!RD->isLambda())
113 return false;
114 for (const auto *FD : RD->fields())
115 if (hasOrigins(QT: FD->getType()))
116 return true;
117 return false;
118}
119
120/// Determines if an expression has origins that need to be tracked.
121///
122/// An expression has origins if:
123/// - It's a glvalue (has addressable storage), OR
124/// - Its type is pointer-like (pointer, reference, or gsl::Pointer), OR
125/// - Its type is registered for origin tracking (e.g., return type of a
126/// [[clang::lifetimebound]] function)
127///
128/// Examples:
129/// - `int x; x` : has origin (glvalue)
130/// - `int* p; p` : has 2 origins (1 for glvalue and 1 for pointer type)
131/// - `std::string_view{}` : has 1 origin (prvalue of pointer type)
132/// - `42` : no origin (prvalue of non-pointer type)
133/// - `x + y` : (where x, y are int) → no origin (prvalue of non-pointer type)
134bool OriginManager::hasOrigins(const Expr *E) const {
135 return E->isGLValue() || hasOrigins(QT: E->getType());
136}
137
138/// Returns true if the declaration has its own storage that can be borrowed.
139///
140/// References generally have no storage - they are aliases to other storage.
141/// For example:
142/// int x; // has storage (can issue loans to x's storage)
143/// int& r = x; // no storage (r is an alias to x's storage)
144/// int* p; // has storage (the pointer variable p itself has storage)
145///
146/// TODO: Handle lifetime extension. References initialized by temporaries
147/// can have storage when the temporary's lifetime is extended:
148/// const int& r = 42; // temporary has storage, lifetime extended
149/// Foo&& f = Foo{}; // temporary has storage, lifetime extended
150/// Currently, this function returns false for all reference types.
151bool doesDeclHaveStorage(const ValueDecl *D) {
152 return !D->getType()->isReferenceType();
153}
154
155OriginManager::OriginManager(const AnalysisDeclContext &AC)
156 : AST(AC.getASTContext()) {
157 collectLifetimeAnnotatedOriginTypes(AC);
158 initializeThisOrigins(D: AC.getDecl());
159}
160
161void OriginManager::initializeThisOrigins(const Decl *D) {
162 const auto *MD = llvm::dyn_cast_or_null<CXXMethodDecl>(Val: D);
163 if (!MD || !MD->isInstance())
164 return;
165 // Lambdas can capture 'this' from the surrounding context, but in that case
166 // 'this' does not refer to the lambda object itself.
167 if (const CXXRecordDecl *P = MD->getParent(); P && P->isLambda())
168 return;
169 ThisOrigins = buildListForType(QT: MD->getThisType(), Node: MD);
170}
171
172OriginList *OriginManager::createNode(const ValueDecl *D, QualType QT) {
173 OriginID NewID = getNextOriginID();
174 AllOrigins.emplace_back(Args&: NewID, Args&: D, Args: QT.getTypePtrOrNull());
175 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
176}
177
178OriginList *OriginManager::createNode(const Expr *E, QualType QT) {
179 OriginID NewID = getNextOriginID();
180 AllOrigins.emplace_back(Args&: NewID, Args&: E, Args: QT.getTypePtrOrNull());
181 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
182}
183
184template <typename T>
185OriginList *OriginManager::buildListForType(QualType QT, const T *Node) {
186 assert(hasOrigins(QT) && "buildListForType called for non-pointer type");
187 OriginList *Head = createNode(Node, QT);
188
189 if (QT->isPointerOrReferenceType()) {
190 QualType PointeeTy = QT->getPointeeType();
191 // We recurse if the pointee type is pointer-like, to build the next
192 // level in the origin tree. E.g., for T*& / View&.
193 if (hasOrigins(QT: PointeeTy))
194 Head->setInnerOriginList(buildListForType(PointeeTy, Node));
195 }
196 return Head;
197}
198
199OriginList *OriginManager::getOrCreateList(const ValueDecl *D) {
200 if (!hasOrigins(QT: D->getType()))
201 return nullptr;
202 auto It = DeclToList.find(Val: D);
203 if (It != DeclToList.end())
204 return It->second;
205 return DeclToList[D] = buildListForType(QT: D->getType(), Node: D);
206}
207
208OriginList *OriginManager::getOrCreateList(const Expr *E) {
209 if (auto *ParenIgnored = E->IgnoreParens(); ParenIgnored != E)
210 return getOrCreateList(E: ParenIgnored);
211 // We do not see CFG stmts for ExprWithCleanups. Simply peel them.
212 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Val: E))
213 return getOrCreateList(E: EWC->getSubExpr());
214
215 if (!hasOrigins(E))
216 return nullptr;
217
218 auto It = ExprToList.find(Val: E);
219 if (It != ExprToList.end())
220 return It->second;
221
222 QualType Type = E->getType();
223 // Special handling for 'this' expressions to share origins with the method's
224 // implicit object parameter.
225 if (isa<CXXThisExpr>(Val: E) && ThisOrigins)
226 return *ThisOrigins;
227
228 // Special handling for expressions referring to a decl to share origins with
229 // the underlying decl.
230 const ValueDecl *ReferencedDecl = nullptr;
231 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E))
232 ReferencedDecl = DRE->getDecl();
233 else if (auto *ME = dyn_cast<MemberExpr>(Val: E))
234 if (auto *Field = dyn_cast<FieldDecl>(Val: ME->getMemberDecl());
235 Field && isa<CXXThisExpr>(Val: ME->getBase()))
236 ReferencedDecl = Field;
237 if (ReferencedDecl) {
238 OriginList *Head = nullptr;
239 // For non-reference declarations (e.g., `int* p`), the expression is an
240 // lvalue (addressable) that can be borrowed, so we create an outer origin
241 // for the lvalue itself, with the pointee being the declaration's list.
242 // This models taking the address: `&p` borrows the storage of `p`, not what
243 // `p` points to.
244 if (doesDeclHaveStorage(D: ReferencedDecl)) {
245 Head = createNode(E, QT: QualType{});
246 // This ensures origin sharing: multiple expressions to the same
247 // declaration share the same underlying origins.
248 Head->setInnerOriginList(getOrCreateList(D: ReferencedDecl));
249 } else {
250 // For reference-typed declarations (e.g., `int& r = p`) which have no
251 // storage, the DeclRefExpr directly reuses the declaration's list since
252 // references don't add an extra level of indirection at the expression
253 // level.
254 Head = getOrCreateList(D: ReferencedDecl);
255 }
256 return ExprToList[E] = Head;
257 }
258
259 // If E is an lvalue , it refers to storage. We model this storage as the
260 // first level of origin list, as if it were a reference, because l-values are
261 // addressable.
262 if (E->isGLValue() && !Type->isReferenceType())
263 Type = AST.getLValueReferenceType(T: Type);
264 return ExprToList[E] = buildListForType(QT: Type, Node: E);
265}
266
267void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const {
268 OS << OID << " (";
269 Origin O = getOrigin(ID: OID);
270 if (const ValueDecl *VD = O.getDecl()) {
271 OS << "Decl: " << VD->getNameAsString();
272 } else if (const Expr *E = O.getExpr()) {
273 OS << "Expr: " << E->getStmtClassName();
274 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E)) {
275 if (const ValueDecl *VD = DRE->getDecl())
276 OS << ", Decl: " << VD->getNameAsString();
277 }
278 } else {
279 OS << "Unknown";
280 }
281 if (O.Ty)
282 OS << ", Type : " << QualType(O.Ty, 0).getAsString();
283 OS << ")";
284}
285
286const Origin &OriginManager::getOrigin(OriginID ID) const {
287 assert(ID.Value < AllOrigins.size());
288 return AllOrigins[ID.Value];
289}
290
291void OriginManager::collectMissingOrigins(Stmt &FunctionBody,
292 LifetimeSafetyStats &LSStats) {
293 MissingOriginCollector Collector(this->ExprToList, *this, LSStats);
294 Collector.TraverseStmt(S: const_cast<Stmt *>(&FunctionBody));
295}
296
297void OriginManager::collectLifetimeAnnotatedOriginTypes(
298 const AnalysisDeclContext &AC) {
299 LifetimeAnnotatedOriginTypeCollector Collector;
300 if (Stmt *Body = AC.getBody())
301 Collector.TraverseStmt(S: Body);
302 if (const auto *CD = dyn_cast<CXXConstructorDecl>(Val: AC.getDecl()))
303 for (const auto *Init : CD->inits())
304 Collector.TraverseStmt(S: Init->getInit());
305 for (QualType QT : Collector.getCollectedTypes())
306 registerLifetimeAnnotatedOriginType(QT);
307}
308
309void OriginManager::registerLifetimeAnnotatedOriginType(QualType QT) {
310 if (!QT->getAsCXXRecordDecl() || hasOrigins(QT))
311 return;
312
313 LifetimeAnnotatedOriginTypes.insert(V: QT.getCanonicalType().getTypePtr());
314}
315
316} // namespace clang::lifetimes::internal
317