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 "llvm/Support/raw_ostream.h"
24
25namespace clang::lifetimes::internal {
26
27using OriginID = utils::ID<struct OriginTag>;
28
29inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) {
30 return OS << ID.Value;
31}
32
33/// An Origin is a symbolic identifier that represents the set of possible
34/// loans a pointer-like object could hold at any given time.
35///
36/// Each Origin corresponds to a single level of indirection. For complex types
37/// with multiple levels of indirection (e.g., `int**`), multiple Origins are
38/// organized into an OriginList structure (see below).
39struct Origin {
40 OriginID ID;
41 /// A pointer to the AST node that this origin represents. This union
42 /// distinguishes between origins from declarations (variables or parameters)
43 /// and origins from expressions.
44 llvm::PointerUnion<const clang::ValueDecl *, const clang::Expr *> Ptr;
45
46 /// The type at this indirection level.
47 ///
48 /// For `int** pp`:
49 /// Root origin: QT = `int**` (what pp points to)
50 /// Pointee origin: QT = `int*` (what *pp points to)
51 ///
52 /// Null for synthetic lvalue origins (e.g., outer origin of DeclRefExpr).
53 const Type *Ty;
54
55 Origin(OriginID ID, const clang::ValueDecl *D, const Type *QT)
56 : ID(ID), Ptr(D), Ty(QT) {}
57 Origin(OriginID ID, const clang::Expr *E, const Type *QT)
58 : ID(ID), Ptr(E), Ty(QT) {}
59
60 const clang::ValueDecl *getDecl() const {
61 return Ptr.dyn_cast<const clang::ValueDecl *>();
62 }
63 const clang::Expr *getExpr() const {
64 return Ptr.dyn_cast<const clang::Expr *>();
65 }
66};
67
68/// A list of origins representing levels of indirection for pointer-like types.
69///
70/// Each node in the list contains an OriginID representing a level of
71/// indirection. The list structure captures the multi-level nature of
72/// pointer and reference types in the lifetime analysis.
73///
74/// Examples:
75/// - For `int& x`, the list has size 2:
76/// * Outer: origin for the reference storage itself (the lvalue `x`)
77/// * Inner: origin for what `x` refers to
78///
79/// - For `int* p`, the list has size 2:
80/// * Outer: origin for the pointer variable `p`
81/// * Inner: origin for what `p` points to
82///
83/// - For `View v` (where View is gsl::Pointer), the list has size 2:
84/// * Outer: origin for the view object itself
85/// * Inner: origin for what the view refers to
86///
87/// - For `int** pp`, the list has size 3:
88/// * Outer: origin for `pp` itself
89/// * Inner: origin for `*pp` (what `pp` points to)
90/// * Inner->Inner: origin for `**pp` (what `*pp` points to)
91///
92/// The list structure enables the analysis to track how loans flow through
93/// different levels of indirection when assignments and dereferences occur.
94class OriginList {
95public:
96 OriginList(OriginID OID) : OuterOID(OID) {}
97
98 OriginList *peelOuterOrigin() const { return InnerList; }
99 OriginID getOuterOriginID() const { return OuterOID; }
100
101 void setInnerOriginList(OriginList *Inner) { InnerList = Inner; }
102
103 // Used for assertion checks only (to ensure origin lists have matching
104 // lengths).
105 size_t getLength() const {
106 size_t Length = 1;
107 const OriginList *T = this;
108 while (T->InnerList) {
109 T = T->InnerList;
110 Length++;
111 }
112 return Length;
113 }
114
115private:
116 OriginID OuterOID;
117 OriginList *InnerList = nullptr;
118};
119
120bool hasOrigins(QualType QT);
121bool hasOrigins(const Expr *E);
122bool doesDeclHaveStorage(const ValueDecl *D);
123
124/// Manages the creation, storage, and retrieval of origins for pointer-like
125/// variables and expressions.
126class OriginManager {
127public:
128 explicit OriginManager(ASTContext &AST, const Decl *D);
129
130 /// Gets or creates the OriginList for a given ValueDecl.
131 ///
132 /// Creates a list structure mirroring the levels of indirection in the
133 /// declaration's type (e.g., `int** p` creates list of size 2).
134 ///
135 /// \returns The OriginList, or nullptr if the type is not pointer-like.
136 OriginList *getOrCreateList(const ValueDecl *D);
137
138 /// Gets or creates the OriginList for a given Expr.
139 ///
140 /// Creates a list based on the expression's type and value category:
141 /// - Lvalues get an implicit reference level (modeling addressability)
142 /// - Rvalues of non-pointer type return nullptr (no trackable origin)
143 /// - DeclRefExpr may reuse the underlying declaration's list
144 ///
145 /// \returns The OriginList, or nullptr for non-pointer rvalues.
146 OriginList *getOrCreateList(const Expr *E);
147
148 /// Returns the OriginList for the implicit 'this' parameter if the current
149 /// declaration is an instance method.
150 std::optional<OriginList *> getThisOrigins() const { return ThisOrigins; }
151
152 const Origin &getOrigin(OriginID ID) const;
153
154 llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; }
155
156 unsigned getNumOrigins() const { return NextOriginID.Value; }
157
158 void dump(OriginID OID, llvm::raw_ostream &OS) const;
159
160 /// Collects statistics about expressions that lack associated origins.
161 void collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats);
162
163private:
164 OriginID getNextOriginID() { return NextOriginID++; }
165
166 OriginList *createNode(const ValueDecl *D, QualType QT);
167 OriginList *createNode(const Expr *E, QualType QT);
168
169 template <typename T>
170 OriginList *buildListForType(QualType QT, const T *Node);
171
172 ASTContext &AST;
173 OriginID NextOriginID{.Value: 0};
174 /// TODO(opt): Profile and evaluate the usefulness of small buffer
175 /// optimisation.
176 llvm::SmallVector<Origin> AllOrigins;
177 llvm::BumpPtrAllocator ListAllocator;
178 llvm::DenseMap<const clang::ValueDecl *, OriginList *> DeclToList;
179 llvm::DenseMap<const clang::Expr *, OriginList *> ExprToList;
180 std::optional<OriginList *> ThisOrigins;
181};
182} // namespace clang::lifetimes::internal
183
184#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINS_H
185