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 Origin(OriginID ID, const clang::ValueDecl *D, const Type *QT)
57 : ID(ID), Ptr(D), Ty(QT) {}
58 Origin(OriginID ID, const clang::Expr *E, const Type *QT)
59 : ID(ID), Ptr(E), Ty(QT) {}
60
61 const clang::ValueDecl *getDecl() const {
62 return Ptr.dyn_cast<const clang::ValueDecl *>();
63 }
64 const clang::Expr *getExpr() const {
65 return Ptr.dyn_cast<const clang::Expr *>();
66 }
67};
68
69/// A list of origins representing levels of indirection for pointer-like types.
70///
71/// Each node in the list contains an OriginID representing a level of
72/// indirection. The list structure captures the multi-level nature of
73/// pointer and reference types in the lifetime analysis.
74///
75/// Examples:
76/// - For `int& x`, the list has size 2:
77/// * Outer: origin for the reference storage itself (the lvalue `x`)
78/// * Inner: origin for what `x` refers to
79///
80/// - For `int* p`, the list has size 2:
81/// * Outer: origin for the pointer variable `p`
82/// * Inner: origin for what `p` points to
83///
84/// - For `View v` (where View is gsl::Pointer), the list has size 2:
85/// * Outer: origin for the view object itself
86/// * Inner: origin for what the view refers to
87///
88/// - For `int** pp`, the list has size 3:
89/// * Outer: origin for `pp` itself
90/// * Inner: origin for `*pp` (what `pp` points to)
91/// * Inner->Inner: origin for `**pp` (what `*pp` points to)
92///
93/// The list structure enables the analysis to track how loans flow through
94/// different levels of indirection when assignments and dereferences occur.
95class OriginList {
96public:
97 OriginList(OriginID OID) : OuterOID(OID) {}
98
99 OriginList *peelOuterOrigin() const { return InnerList; }
100 OriginID getOuterOriginID() const { return OuterOID; }
101
102 void setInnerOriginList(OriginList *Inner) { InnerList = Inner; }
103
104 // Used for assertion checks only (to ensure origin lists have matching
105 // lengths).
106 size_t getLength() const {
107 size_t Length = 1;
108 const OriginList *T = this;
109 while (T->InnerList) {
110 T = T->InnerList;
111 Length++;
112 }
113 return Length;
114 }
115
116private:
117 OriginID OuterOID;
118 OriginList *InnerList = nullptr;
119};
120
121bool doesDeclHaveStorage(const ValueDecl *D);
122
123/// Manages the creation, storage, and retrieval of origins for pointer-like
124/// variables and expressions.
125class OriginManager {
126public:
127 explicit OriginManager(const AnalysisDeclContext &AC);
128
129 /// Gets or creates the OriginList for a given ValueDecl.
130 ///
131 /// Creates a list structure mirroring the levels of indirection in the
132 /// declaration's type (e.g., `int** p` creates list of size 2).
133 ///
134 /// \returns The OriginList, or nullptr if the type is not pointer-like.
135 OriginList *getOrCreateList(const ValueDecl *D);
136
137 /// Gets or creates the OriginList for a given Expr.
138 ///
139 /// Creates a list based on the expression's type and value category:
140 /// - Lvalues get an implicit reference level (modeling addressability)
141 /// - Rvalues of non-pointer type return nullptr (no trackable origin)
142 /// - DeclRefExpr may reuse the underlying declaration's list
143 ///
144 /// \returns The OriginList, or nullptr for non-pointer rvalues.
145 OriginList *getOrCreateList(const Expr *E);
146
147 /// Wraps an existing OriginID in a new single-element OriginList, so a fact
148 /// can refer to a single level of an existing OriginList.
149 OriginList *createSingleOriginList(OriginID OID);
150
151 /// Returns the OriginList for the implicit 'this' parameter if the current
152 /// declaration is an instance method.
153 std::optional<OriginList *> getThisOrigins() const { return ThisOrigins; }
154
155 const Origin &getOrigin(OriginID ID) const;
156
157 llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; }
158
159 unsigned getNumOrigins() const { return NextOriginID.Value; }
160
161 /// Determines whether a type can carry lifetime origins.
162 ///
163 /// \param QT The type to check.
164 /// \param IntrinsicOnly If true, only consider types that can intrinsically
165 /// carry origins. If false, also include types that are tracked due to
166 /// context-sensitive annotations (e.g., return types of
167 /// [[clang::lifetimebound]] functions).
168 ///
169 /// Intrinsic origin types:
170 /// - Pointer types (int*, void*)
171 /// - Reference types (int&, const T&)
172 /// - gsl::Pointer annotated types (std::string_view)
173 /// - Lambdas capturing pointer-like objects
174 /// - Standard callable wrappers (std::function)
175 ///
176 /// TODO: Expand this list with other origin types such as: user-defined
177 /// structs with pointer-like fields.
178 ///
179 /// Contextual origin types (excluded when IntrinsicOnly=true):
180 /// - Types appearing as return values of functions with
181 /// [[clang::lifetimebound]] parameters, stored in
182 /// LifetimeAnnotatedOriginTypes during function body analysis.
183 bool hasOrigins(QualType QT, bool IntrinsicOnly = false) const;
184 bool hasOrigins(const Expr *E) const;
185
186 void dump(OriginID OID, llvm::raw_ostream &OS) const;
187
188 /// Collects statistics about expressions that lack associated origins.
189 void collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats);
190
191private:
192 OriginID getNextOriginID() { return NextOriginID++; }
193
194 OriginList *createNode(const ValueDecl *D, QualType QT);
195 OriginList *createNode(const Expr *E, QualType QT);
196
197 template <typename T>
198 OriginList *buildListForType(QualType QT, const T *Node);
199
200 void initializeThisOrigins(const Decl *D);
201
202 /// Pre-scans the function body (and constructor init lists) to discover
203 /// return types of lifetime-annotated calls (currently
204 /// [[clang::lifetimebound]]), registering them for origin tracking.
205 void collectLifetimeAnnotatedOriginTypes(const AnalysisDeclContext &AC);
206 void registerLifetimeAnnotatedOriginType(QualType QT);
207
208 ASTContext &AST;
209 OriginID NextOriginID{.Value: 0};
210 /// TODO(opt): Profile and evaluate the usefulness of small buffer
211 /// optimisation.
212 llvm::SmallVector<Origin> AllOrigins;
213 llvm::BumpPtrAllocator ListAllocator;
214 llvm::DenseMap<const clang::ValueDecl *, OriginList *> DeclToList;
215 llvm::DenseMap<const clang::Expr *, OriginList *> ExprToList;
216 std::optional<OriginList *> ThisOrigins;
217 /// Types that are not inherently pointer-like but require origin tracking
218 /// because of lifetime annotations (currently [[clang::lifetimebound]]) on
219 /// functions that return them.
220 llvm::DenseSet<const Type *> LifetimeAnnotatedOriginTypes;
221};
222} // namespace clang::lifetimes::internal
223
224#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
225