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 "llvm/ADT/StringMap.h"
22
23namespace clang::lifetimes::internal {
24namespace {
25/// A utility class to traverse the function body in the analysis
26/// context and collect the count of expressions with missing origins.
27class MissingOriginCollector
28 : public RecursiveASTVisitor<MissingOriginCollector> {
29public:
30 MissingOriginCollector(
31 const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList,
32 LifetimeSafetyStats &LSStats)
33 : ExprToOriginList(ExprToOriginList), LSStats(LSStats) {}
34 bool VisitExpr(Expr *E) {
35 if (!hasOrigins(E))
36 return true;
37 // Check if we have an origin for this expression.
38 if (!ExprToOriginList.contains(Val: E)) {
39 // No origin found: count this as missing origin.
40 LSStats.ExprTypeToMissingOriginCount[E->getType().getTypePtr()]++;
41 LSStats.ExprStmtClassToMissingOriginCount[std::string(
42 E->getStmtClassName())]++;
43 }
44 return true;
45 }
46
47private:
48 const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList;
49 LifetimeSafetyStats &LSStats;
50};
51} // namespace
52
53bool hasOrigins(QualType QT) {
54 if (QT->isPointerOrReferenceType() || isGslPointerType(QT))
55 return true;
56 const auto *RD = QT->getAsCXXRecordDecl();
57 if (!RD)
58 return false;
59 // TODO: Limit to lambdas for now. This will be extended to user-defined
60 // structs with pointer-like fields.
61 if (!RD->isLambda())
62 return false;
63 for (const auto *FD : RD->fields())
64 if (hasOrigins(QT: FD->getType()))
65 return true;
66 return false;
67}
68
69/// Determines if an expression has origins that need to be tracked.
70///
71/// An expression has origins if:
72/// - It's a glvalue (has addressable storage), OR
73/// - Its type is pointer-like (pointer, reference, or gsl::Pointer)
74///
75/// Examples:
76/// - `int x; x` : has origin (glvalue)
77/// - `int* p; p` : has 2 origins (1 for glvalue and 1 for pointer type)
78/// - `std::string_view{}` : has 1 origin (prvalue of pointer type)
79/// - `42` : no origin (prvalue of non-pointer type)
80/// - `x + y` : (where x, y are int) → no origin (prvalue of non-pointer type)
81bool hasOrigins(const Expr *E) {
82 return E->isGLValue() || hasOrigins(QT: E->getType());
83}
84
85/// Returns true if the declaration has its own storage that can be borrowed.
86///
87/// References generally have no storage - they are aliases to other storage.
88/// For example:
89/// int x; // has storage (can issue loans to x's storage)
90/// int& r = x; // no storage (r is an alias to x's storage)
91/// int* p; // has storage (the pointer variable p itself has storage)
92///
93/// TODO: Handle lifetime extension. References initialized by temporaries
94/// can have storage when the temporary's lifetime is extended:
95/// const int& r = 42; // temporary has storage, lifetime extended
96/// Foo&& f = Foo{}; // temporary has storage, lifetime extended
97/// Currently, this function returns false for all reference types.
98bool doesDeclHaveStorage(const ValueDecl *D) {
99 return !D->getType()->isReferenceType();
100}
101
102OriginManager::OriginManager(ASTContext &AST, const Decl *D) : AST(AST) {
103 // Create OriginList for 'this' expr.
104 const auto *MD = llvm::dyn_cast_or_null<CXXMethodDecl>(Val: D);
105 if (!MD || !MD->isInstance())
106 return;
107 // Lambdas can capture 'this' from the surrounding context, but in that case
108 // 'this' does not refer to the lambda object itself.
109 if (const CXXRecordDecl *P = MD->getParent(); P && P->isLambda())
110 return;
111 ThisOrigins = buildListForType(QT: MD->getThisType(), Node: MD);
112}
113
114OriginList *OriginManager::createNode(const ValueDecl *D, QualType QT) {
115 OriginID NewID = getNextOriginID();
116 AllOrigins.emplace_back(Args&: NewID, Args&: D, Args: QT.getTypePtrOrNull());
117 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
118}
119
120OriginList *OriginManager::createNode(const Expr *E, QualType QT) {
121 OriginID NewID = getNextOriginID();
122 AllOrigins.emplace_back(Args&: NewID, Args&: E, Args: QT.getTypePtrOrNull());
123 return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID);
124}
125
126template <typename T>
127OriginList *OriginManager::buildListForType(QualType QT, const T *Node) {
128 assert(hasOrigins(QT) && "buildListForType called for non-pointer type");
129 OriginList *Head = createNode(Node, QT);
130
131 if (QT->isPointerOrReferenceType()) {
132 QualType PointeeTy = QT->getPointeeType();
133 // We recurse if the pointee type is pointer-like, to build the next
134 // level in the origin tree. E.g., for T*& / View&.
135 if (hasOrigins(QT: PointeeTy))
136 Head->setInnerOriginList(buildListForType(PointeeTy, Node));
137 }
138 return Head;
139}
140
141OriginList *OriginManager::getOrCreateList(const ValueDecl *D) {
142 if (!hasOrigins(QT: D->getType()))
143 return nullptr;
144 auto It = DeclToList.find(Val: D);
145 if (It != DeclToList.end())
146 return It->second;
147 return DeclToList[D] = buildListForType(QT: D->getType(), Node: D);
148}
149
150OriginList *OriginManager::getOrCreateList(const Expr *E) {
151 if (auto *ParenIgnored = E->IgnoreParens(); ParenIgnored != E)
152 return getOrCreateList(E: ParenIgnored);
153 // We do not see CFG stmts for ExprWithCleanups. Simply peel them.
154 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Val: E))
155 return getOrCreateList(E: EWC->getSubExpr());
156
157 if (!hasOrigins(E))
158 return nullptr;
159
160 auto It = ExprToList.find(Val: E);
161 if (It != ExprToList.end())
162 return It->second;
163
164 QualType Type = E->getType();
165 // Special handling for 'this' expressions to share origins with the method's
166 // implicit object parameter.
167 if (isa<CXXThisExpr>(Val: E) && ThisOrigins)
168 return *ThisOrigins;
169
170 // Special handling for expressions referring to a decl to share origins with
171 // the underlying decl.
172 const ValueDecl *ReferencedDecl = nullptr;
173 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E))
174 ReferencedDecl = DRE->getDecl();
175 else if (auto *ME = dyn_cast<MemberExpr>(Val: E))
176 if (auto *Field = dyn_cast<FieldDecl>(Val: ME->getMemberDecl());
177 Field && isa<CXXThisExpr>(Val: ME->getBase()))
178 ReferencedDecl = Field;
179 if (ReferencedDecl) {
180 OriginList *Head = nullptr;
181 // For non-reference declarations (e.g., `int* p`), the expression is an
182 // lvalue (addressable) that can be borrowed, so we create an outer origin
183 // for the lvalue itself, with the pointee being the declaration's list.
184 // This models taking the address: `&p` borrows the storage of `p`, not what
185 // `p` points to.
186 if (doesDeclHaveStorage(D: ReferencedDecl)) {
187 Head = createNode(E, QT: QualType{});
188 // This ensures origin sharing: multiple expressions to the same
189 // declaration share the same underlying origins.
190 Head->setInnerOriginList(getOrCreateList(D: ReferencedDecl));
191 } else {
192 // For reference-typed declarations (e.g., `int& r = p`) which have no
193 // storage, the DeclRefExpr directly reuses the declaration's list since
194 // references don't add an extra level of indirection at the expression
195 // level.
196 Head = getOrCreateList(D: ReferencedDecl);
197 }
198 return ExprToList[E] = Head;
199 }
200
201 // If E is an lvalue , it refers to storage. We model this storage as the
202 // first level of origin list, as if it were a reference, because l-values are
203 // addressable.
204 if (E->isGLValue() && !Type->isReferenceType())
205 Type = AST.getLValueReferenceType(T: Type);
206 return ExprToList[E] = buildListForType(QT: Type, Node: E);
207}
208
209void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const {
210 OS << OID << " (";
211 Origin O = getOrigin(ID: OID);
212 if (const ValueDecl *VD = O.getDecl()) {
213 OS << "Decl: " << VD->getNameAsString();
214 } else if (const Expr *E = O.getExpr()) {
215 OS << "Expr: " << E->getStmtClassName();
216 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E)) {
217 if (const ValueDecl *VD = DRE->getDecl())
218 OS << ", Decl: " << VD->getNameAsString();
219 }
220 } else {
221 OS << "Unknown";
222 }
223 if (O.Ty)
224 OS << ", Type : " << QualType(O.Ty, 0).getAsString();
225 OS << ")";
226}
227
228const Origin &OriginManager::getOrigin(OriginID ID) const {
229 assert(ID.Value < AllOrigins.size());
230 return AllOrigins[ID.Value];
231}
232
233void OriginManager::collectMissingOrigins(Stmt &FunctionBody,
234 LifetimeSafetyStats &LSStats) {
235 MissingOriginCollector Collector(this->ExprToList, LSStats);
236 Collector.TraverseStmt(S: const_cast<Stmt *>(&FunctionBody));
237}
238
239} // namespace clang::lifetimes::internal
240