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