1//===- Origins.h - Origin and Origin Management ----------------*- 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// This file defines Origins, which represent the set of possible loans a
10// pointer-like object could hold, and the OriginManager, which manages the
11// creation, storage, and retrieval of origins for variables and expressions.
12//
13//===----------------------------------------------------------------------===//
14#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
15#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
16
17#include "clang/AST/Decl.h"
18#include "clang/AST/DeclCXX.h"
19#include "clang/AST/Expr.h"
20#include "clang/AST/TypeBase.h"
21#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeStats.h"
22#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"
23#include "clang/Analysis/AnalysisDeclContext.h"
24#include "llvm/Support/raw_ostream.h"
25
26namespace clang::lifetimes::internal {
27
28using OriginID = utils::ID<struct OriginTag>;
29
30inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) {
31 return OS << ID.Value;
32}
33
34/// An Origin is a symbolic identifier that represents the set of possible
35/// loans a pointer-like object could hold at any given time.
36///
37/// Each Origin corresponds to a single level of indirection. For complex types
38/// with multiple levels of indirection (e.g., `int**`), multiple Origins are
39/// organized into an OriginList structure (see below).
40struct Origin {
41 OriginID ID;
42 /// A pointer to the AST node that this origin represents. This union
43 /// distinguishes between origins from declarations (variables or parameters)
44 /// and origins from expressions.
45 llvm::PointerUnion<const clang::ValueDecl *, const clang::Expr *> Ptr;
46
47 /// The type at this indirection level.
48 ///
49 /// For `int** pp`:
50 /// Root origin: QT = `int**` (what pp points to)
51 /// Pointee origin: QT = `int*` (what *pp points to)
52 ///
53 /// Null for synthetic lvalue origins (e.g., outer origin of DeclRefExpr).
54 const Type *Ty;
55
56 /// True if this origin only holds a loan to a declaration named in scope, so
57 /// it can never hold an expired loan. For example, in
58 /// int s = 42;
59 /// int t = s;
60 /// the outer origin of the expression `s` holds a loan to `s`, which is alive
61 /// wherever `s` can be named.
62 bool NamesDeclStorage;
63
64 Origin(OriginID ID, const clang::ValueDecl *D, const Type *QT,
65 bool NamesDeclStorage)
66 : ID(ID), Ptr(D), Ty(QT), NamesDeclStorage(NamesDeclStorage) {}
67 Origin(OriginID ID, const clang::Expr *E, const Type *QT,
68 bool NamesDeclStorage)
69 : ID(ID), Ptr(E), Ty(QT), NamesDeclStorage(NamesDeclStorage) {}
70
71 const clang::ValueDecl *getDecl() const {
72 return Ptr.dyn_cast<const clang::ValueDecl *>();
73 }
74 const clang::Expr *getExpr() const {
75 return Ptr.dyn_cast<const clang::Expr *>();
76 }
77};
78
79/// A list of origins representing levels of indirection for pointer-like types.
80///
81/// Each node in the list contains an OriginID representing a level of
82/// indirection. The list structure captures the multi-level nature of
83/// pointer and reference types in the lifetime analysis.
84///
85/// Examples:
86/// - For `int& x`, the list has size 2:
87/// * Outer: origin for the reference storage itself (the lvalue `x`)
88/// * Inner: origin for what `x` refers to
89///
90/// - For `int* p`, the list has size 2:
91/// * Outer: origin for the pointer variable `p`
92/// * Inner: origin for what `p` points to
93///
94/// - For `View v` (where View is gsl::Pointer), the list has size 2:
95/// * Outer: origin for the view object itself
96/// * Inner: origin for what the view refers to
97///
98/// - For `int** pp`, the list has size 3:
99/// * Outer: origin for `pp` itself
100/// * Inner: origin for `*pp` (what `pp` points to)
101/// * Inner->Inner: origin for `**pp` (what `*pp` points to)
102///
103/// The list structure enables the analysis to track how loans flow through
104/// different levels of indirection when assignments and dereferences occur.
105class OriginList {
106public:
107 OriginList(OriginID OID) : OuterOID(OID) {}
108
109 OriginList *peelOuterOrigin() const { return InnerList; }
110 OriginID getOuterOriginID() const { return OuterOID; }
111
112 void setInnerOriginList(OriginList *Inner) { InnerList = Inner; }
113
114 // Used for assertion checks only (to ensure origin lists have matching
115 // lengths).
116 size_t getLength() const {
117 size_t Length = 1;
118 const OriginList *T = this;
119 while (T->InnerList) {
120 T = T->InnerList;
121 Length++;
122 }
123 return Length;
124 }
125
126private:
127 OriginID OuterOID;
128 OriginList *InnerList = nullptr;
129};
130
131bool doesDeclHaveStorage(const ValueDecl *D);
132
133/// Manages the creation, storage, and retrieval of origins for pointer-like
134/// variables and expressions.
135class OriginManager {
136public:
137 explicit OriginManager(const AnalysisDeclContext &AC);
138
139 /// Gets or creates the OriginList for a given ValueDecl.
140 ///
141 /// Creates a list structure mirroring the levels of indirection in the
142 /// declaration's type (e.g., `int** p` creates list of size 2).
143 ///
144 /// \returns The OriginList, or nullptr if the type is not pointer-like.
145 OriginList *getOrCreateList(const ValueDecl *D);
146
147 /// Gets or creates the OriginList for a given Expr.
148 ///
149 /// Creates a list based on the expression's type and value category:
150 /// - Lvalues get an implicit reference level (modeling addressability)
151 /// - Rvalues of non-pointer type return nullptr (no trackable origin)
152 /// - DeclRefExpr may reuse the underlying declaration's list
153 ///
154 /// \returns The OriginList, or nullptr for non-pointer rvalues.
155 OriginList *getOrCreateList(const Expr *E);
156
157 /// Wraps an existing OriginID in a new single-element OriginList, so a fact
158 /// can refer to a single level of an existing OriginList.
159 OriginList *createSingleOriginList(OriginID OID);
160
161 /// Returns the OriginList for the implicit 'this' parameter if the current
162 /// declaration is an instance method.
163 std::optional<OriginList *> getThisOrigins() const { return ThisOrigins; }
164
165 const Origin &getOrigin(OriginID ID) const;
166
167 llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; }
168
169 unsigned getNumOrigins() const { return NextOriginID.Value; }
170
171 /// Determines whether a type can carry lifetime origins.
172 ///
173 /// \param QT The type to check.
174 /// \param IntrinsicOnly If true, only consider types that can intrinsically
175 /// carry origins. If false, also include types that are tracked due to
176 /// context-sensitive annotations (e.g., return types of
177 /// [[clang::lifetimebound]] functions).
178 ///
179 /// Intrinsic origin types:
180 /// - Pointer types (int*, void*)
181 /// - Reference types (int&, const T&)
182 /// - gsl::Pointer annotated types (std::string_view)
183 /// - Lambdas capturing pointer-like objects
184 /// - Standard callable wrappers (std::function)
185 ///
186 /// TODO: Expand this list with other origin types such as: user-defined
187 /// structs with pointer-like fields.
188 ///
189 /// Contextual origin types (excluded when IntrinsicOnly=true):
190 /// - Types appearing as return values of functions with
191 /// [[clang::lifetimebound]] parameters, stored in
192 /// LifetimeAnnotatedOriginTypes during function body analysis.
193 bool hasOrigins(QualType QT, bool IntrinsicOnly = false) const;
194 bool hasOrigins(const Expr *E) const;
195
196 void dump(OriginID OID, llvm::raw_ostream &OS) const;
197
198 /// Collects statistics about expressions that lack associated origins.
199 void collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats);
200
201private:
202 OriginID getNextOriginID() { return NextOriginID++; }
203
204 OriginList *createNode(const ValueDecl *D, QualType QT,
205 bool NamesDeclStorage = false);
206 OriginList *createNode(const Expr *E, QualType QT,
207 bool NamesDeclStorage = false);
208
209 template <typename T>
210 OriginList *buildListForType(QualType QT, const T *Node,
211 bool NamesDeclStorage = false);
212
213 void initializeThisOrigins(const Decl *D);
214
215 /// Pre-scans the function body (and constructor init lists) to discover
216 /// return types of lifetime-annotated calls (currently
217 /// [[clang::lifetimebound]]), registering them for origin tracking.
218 void collectLifetimeAnnotatedOriginTypes(const AnalysisDeclContext &AC);
219 void registerLifetimeAnnotatedOriginType(QualType QT);
220
221 ASTContext &AST;
222 OriginID NextOriginID{.Value: 0};
223 /// TODO(opt): Profile and evaluate the usefulness of small buffer
224 /// optimisation.
225 llvm::SmallVector<Origin> AllOrigins;
226 llvm::BumpPtrAllocator ListAllocator;
227 llvm::DenseMap<const clang::ValueDecl *, OriginList *> DeclToList;
228 llvm::DenseMap<const clang::Expr *, OriginList *> ExprToList;
229 std::optional<OriginList *> ThisOrigins;
230 /// Types that are not inherently pointer-like but require origin tracking
231 /// because of lifetime annotations (currently [[clang::lifetimebound]]) on
232 /// functions that return them.
233 llvm::DenseSet<const Type *> LifetimeAnnotatedOriginTypes;
234};
235} // namespace clang::lifetimes::internal
236
237#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
238