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 /// Returns the OriginList for the implicit 'this' parameter if the current
148 /// declaration is an instance method.
149 std::optional<OriginList *> getThisOrigins() const { return ThisOrigins; }
150
151 const Origin &getOrigin(OriginID ID) const;
152
153 llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; }
154
155 unsigned getNumOrigins() const { return NextOriginID.Value; }
156
157 bool hasOrigins(QualType QT) const;
158 bool hasOrigins(const Expr *E) const;
159
160 void dump(OriginID OID, llvm::raw_ostream &OS) const;
161
162 /// Collects statistics about expressions that lack associated origins.
163 void collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats);
164
165private:
166 OriginID getNextOriginID() { return NextOriginID++; }
167
168 OriginList *createNode(const ValueDecl *D, QualType QT);
169 OriginList *createNode(const Expr *E, QualType QT);
170
171 template <typename T>
172 OriginList *buildListForType(QualType QT, const T *Node);
173
174 void initializeThisOrigins(const Decl *D);
175
176 /// Pre-scans the function body (and constructor init lists) to discover
177 /// return types of lifetime-annotated calls (currently
178 /// [[clang::lifetimebound]]), registering them for origin tracking.
179 void collectLifetimeAnnotatedOriginTypes(const AnalysisDeclContext &AC);
180 void registerLifetimeAnnotatedOriginType(QualType QT);
181
182 ASTContext &AST;
183 OriginID NextOriginID{.Value: 0};
184 /// TODO(opt): Profile and evaluate the usefulness of small buffer
185 /// optimisation.
186 llvm::SmallVector<Origin> AllOrigins;
187 llvm::BumpPtrAllocator ListAllocator;
188 llvm::DenseMap<const clang::ValueDecl *, OriginList *> DeclToList;
189 llvm::DenseMap<const clang::Expr *, OriginList *> ExprToList;
190 std::optional<OriginList *> ThisOrigins;
191 /// Types that are not inherently pointer-like but require origin tracking
192 /// because of lifetime annotations (currently [[clang::lifetimebound]]) on
193 /// functions that return them.
194 llvm::DenseSet<const Type *> LifetimeAnnotatedOriginTypes;
195};
196} // namespace clang::lifetimes::internal
197
198#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
199