1//===- FactsGenerator.cpp - Lifetime Facts Generation -----------*- 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 <cassert>
10#include <string>
11
12#include "clang/AST/Decl.h"
13#include "clang/AST/DeclCXX.h"
14#include "clang/AST/Expr.h"
15#include "clang/AST/ExprCXX.h"
16#include "clang/AST/OperationKinds.h"
17#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
18#include "clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h"
19#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h"
20#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
21#include "clang/Analysis/Analyses/PostOrderCFGView.h"
22#include "clang/Analysis/CFG.h"
23#include "clang/Basic/OperatorKinds.h"
24#include "llvm/ADT/ArrayRef.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/Support/Casting.h"
27#include "llvm/Support/Signals.h"
28#include "llvm/Support/TimeProfiler.h"
29
30namespace clang::lifetimes::internal {
31using llvm::isa_and_present;
32
33OriginList *FactsGenerator::getOriginsList(const ValueDecl &D) {
34 return FactMgr.getOriginMgr().getOrCreateList(D: &D);
35}
36OriginList *FactsGenerator::getOriginsList(const Expr &E) {
37 return FactMgr.getOriginMgr().getOrCreateList(E: &E);
38}
39
40bool FactsGenerator::hasOrigins(QualType QT) const {
41 return FactMgr.getOriginMgr().hasOrigins(QT);
42}
43
44bool FactsGenerator::hasOrigins(const Expr *E) const {
45 return FactMgr.getOriginMgr().hasOrigins(E);
46}
47
48/// Propagates origin information from Src to Dst through all levels of
49/// indirection, creating OriginFlowFacts at each level.
50///
51/// This function enforces a critical type-safety invariant: both lists must
52/// have the same shape (same depth/structure). This invariant ensures that
53/// origins flow only between compatible types during expression evaluation.
54///
55/// Examples:
56/// - `int* p = &x;` flows origins from `&x` (depth 1) to `p` (depth 1)
57/// - `int** pp = &p;` flows origins from `&p` (depth 2) to `pp` (depth 2)
58/// * Level 1: pp <- p's address
59/// * Level 2: (*pp) <- what p points to (i.e., &x)
60/// - `View v = obj;` flows origins from `obj` (depth 1) to `v` (depth 1)
61void FactsGenerator::flow(OriginList *Dst, OriginList *Src, bool Kill) {
62 if (!Dst)
63 return;
64 assert(Src &&
65 "Dst is non-null but Src is null. List must have the same length");
66 assert(Dst->getLength() == Src->getLength() &&
67 "Lists must have the same length");
68
69 while (Dst && Src) {
70 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
71 args: Dst->getOuterOriginID(), args: Src->getOuterOriginID(), args&: Kill));
72 Dst = Dst->peelOuterOrigin();
73 Src = Src->peelOuterOrigin();
74 }
75}
76
77/// Creates a loan for the storage path of a given declaration reference.
78/// This function should be called whenever a DeclRefExpr represents a borrow.
79/// \param DRE The declaration reference expression that initiates the borrow.
80/// \return The new Loan on success, nullptr otherwise.
81static const Loan *createLoan(FactManager &FactMgr, const DeclRefExpr *DRE) {
82 const ValueDecl *VD = DRE->getDecl();
83 AccessPath Path(VD);
84 // The loan is created at the location of the DeclRefExpr.
85 return FactMgr.getLoanMgr().createLoan(Path, IssueExpr: DRE);
86}
87
88/// Creates a loan for the storage location of a temporary object.
89/// \param MTE The MaterializeTemporaryExpr that represents the temporary
90/// binding. \return The new Loan.
91static const Loan *createLoan(FactManager &FactMgr,
92 const MaterializeTemporaryExpr *MTE) {
93 AccessPath Path(MTE);
94 return FactMgr.getLoanMgr().createLoan(Path, IssueExpr: MTE);
95}
96
97void FactsGenerator::run() {
98 llvm::TimeTraceScope TimeProfile("FactGenerator");
99 const CFG &Cfg = *AC.getCFG();
100 llvm::SmallVector<Fact *> PlaceholderLoanFacts = issuePlaceholderLoans();
101 // Iterate through the CFG blocks in reverse post-order to ensure that
102 // initializations and destructions are processed in the correct sequence.
103 for (const CFGBlock *Block : *AC.getAnalysis<PostOrderCFGView>()) {
104 CurrentBlockFacts.clear();
105 EscapesInCurrentBlock.clear();
106 if (Block == &Cfg.getEntry())
107 CurrentBlockFacts.append(in_start: PlaceholderLoanFacts.begin(),
108 in_end: PlaceholderLoanFacts.end());
109 for (unsigned I = 0; I < Block->size(); ++I) {
110 const CFGElement &Element = Block->Elements[I];
111 if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>())
112 Visit(S: CS->getStmt());
113 else if (std::optional<CFGInitializer> Initializer =
114 Element.getAs<CFGInitializer>())
115 handleCXXCtorInitializer(CII: Initializer->getInitializer());
116 else if (std::optional<CFGLifetimeEnds> LifetimeEnds =
117 Element.getAs<CFGLifetimeEnds>())
118 handleLifetimeEnds(LifetimeEnds: *LifetimeEnds);
119 else if (std::optional<CFGFullExprCleanup> FullExprCleanup =
120 Element.getAs<CFGFullExprCleanup>()) {
121 handleFullExprCleanup(FullExprCleanup: *FullExprCleanup);
122 }
123 }
124 if (Block == &Cfg.getExit())
125 handleExitBlock();
126
127 CurrentBlockFacts.append(in_start: EscapesInCurrentBlock.begin(),
128 in_end: EscapesInCurrentBlock.end());
129 FactMgr.addBlockFacts(B: Block, NewFacts: CurrentBlockFacts);
130 }
131}
132
133/// Simulates LValueToRValue conversion by peeling the outer lvalue origin
134/// if the expression is a GLValue. For pointer/view GLValues, this strips
135/// the origin representing the storage location to get the origins of the
136/// pointed-to value.
137///
138/// Example: For `View& v`, returns the origin of what v points to, not v's
139/// storage.
140static OriginList *getRValueOrigins(const Expr *E, OriginList *List) {
141 if (!List)
142 return nullptr;
143 return E->isGLValue() ? List->peelOuterOrigin() : List;
144}
145
146void FactsGenerator::VisitDeclStmt(const DeclStmt *DS) {
147 for (const Decl *D : DS->decls())
148 if (const auto *VD = dyn_cast<VarDecl>(Val: D))
149 if (const Expr *InitExpr = VD->getInit()) {
150 OriginList *VDList = getOriginsList(D: *VD);
151 if (!VDList)
152 continue;
153 OriginList *InitList = getOriginsList(E: *InitExpr);
154 assert(InitList && "VarDecl had origins but InitExpr did not");
155 flow(Dst: VDList, Src: InitList, /*Kill=*/true);
156 }
157}
158
159void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) {
160 // Skip function references as their lifetimes are not interesting. Skip non
161 // GLValues (like EnumConstants).
162 if (DRE->getFoundDecl()->isFunctionOrFunctionTemplate() || !DRE->isGLValue())
163 return;
164 handleUse(E: DRE);
165 // For all declarations with storage (non-references), we issue a loan
166 // representing the borrow of the variable's storage itself.
167 //
168 // Examples:
169 // - `int x; x` issues loan to x's storage
170 // - `int* p; p` issues loan to p's storage (the pointer variable)
171 // - `View v; v` issues loan to v's storage (the view object)
172 // - `int& r = x; r` issues no loan (r has no storage, it's an alias to x)
173 if (doesDeclHaveStorage(D: DRE->getDecl())) {
174 const Loan *L = createLoan(FactMgr, DRE);
175 assert(L);
176 OriginList *List = getOriginsList(E: *DRE);
177 assert(List &&
178 "gl-value DRE of non-pointer type should have an origin list");
179 // This loan specifically tracks borrowing the variable's storage location
180 // itself and is issued to outermost origin (List->OID).
181 CurrentBlockFacts.push_back(
182 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
183 }
184}
185
186void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
187 if (isGslPointerType(QT: CCE->getType())) {
188 handleGSLPointerConstruction(CCE);
189 return;
190 }
191 // For defaulted (implicit or `= default`) copy/move constructors, propagate
192 // origins directly. User-defined copy/move constructors have opaque semantics
193 // and fall through to `handleFunctionCall`, where [[clang::lifetimebound]] is
194 // needed to propagate origins.
195 if (CCE->getConstructor()->isCopyOrMoveConstructor() &&
196 CCE->getConstructor()->isDefaulted() && CCE->getNumArgs() == 1 &&
197 hasOrigins(QT: CCE->getType())) {
198 const Expr *Arg = CCE->getArg(Arg: 0);
199 if (OriginList *ArgList = getRValueOrigins(E: Arg, List: getOriginsList(E: *Arg))) {
200 flow(Dst: getOriginsList(E: *CCE), Src: ArgList, /*Kill=*/true);
201 return;
202 }
203 }
204 handleFunctionCall(Call: CCE, FD: CCE->getConstructor(),
205 Args: {CCE->getArgs(), CCE->getNumArgs()},
206 /*IsGslConstruction=*/false);
207}
208
209void FactsGenerator::handleCXXCtorInitializer(const CXXCtorInitializer *CII) {
210 // Flows origins from the initializer expression to the field.
211 // Example: `MyObj(std::string s) : view(s) {}`
212 if (const FieldDecl *FD = CII->getAnyMember())
213 killAndFlowOrigin(D: *FD, S: *CII->getInit());
214}
215
216void FactsGenerator::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE) {
217 // Specifically for conversion operators,
218 // like `std::string_view p = std::string{};`
219 if (isGslPointerType(QT: MCE->getType()) &&
220 isa_and_present<CXXConversionDecl>(Val: MCE->getCalleeDecl()) &&
221 isGslOwnerType(QT: MCE->getImplicitObjectArgument()->getType())) {
222 // The argument is the implicit object itself.
223 handleFunctionCall(Call: MCE, FD: MCE->getMethodDecl(),
224 Args: {MCE->getImplicitObjectArgument()},
225 /*IsGslConstruction=*/true);
226 return;
227 }
228 if (const CXXMethodDecl *Method = MCE->getMethodDecl()) {
229 // Construct the argument list, with the implicit 'this' object as the
230 // first argument.
231 llvm::SmallVector<const Expr *, 4> Args;
232 Args.push_back(Elt: MCE->getImplicitObjectArgument());
233 Args.append(in_start: MCE->getArgs(), in_end: MCE->getArgs() + MCE->getNumArgs());
234
235 handleFunctionCall(Call: MCE, FD: Method, Args, /*IsGslConstruction=*/false);
236 }
237}
238
239void FactsGenerator::VisitMemberExpr(const MemberExpr *ME) {
240 auto *MD = ME->getMemberDecl();
241 if (isa<FieldDecl>(Val: MD) && doesDeclHaveStorage(D: MD)) {
242 assert(ME->isGLValue() && "Field member should be GL value");
243 OriginList *Dst = getOriginsList(E: *ME);
244 assert(Dst && "Field member should have an origin list as it is GL value");
245 OriginList *Src = getOriginsList(E: *ME->getBase());
246 assert(Src && "Base expression should be a pointer/reference type");
247 // The field's glvalue (outermost origin) holds the same loans as the base
248 // expression.
249 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
250 args: Dst->getOuterOriginID(), args: Src->getOuterOriginID(),
251 /*Kill=*/args: true));
252 }
253}
254
255void FactsGenerator::VisitCallExpr(const CallExpr *CE) {
256 handleFunctionCall(Call: CE, FD: CE->getDirectCallee(),
257 Args: {CE->getArgs(), CE->getNumArgs()});
258}
259
260void FactsGenerator::VisitCXXNullPtrLiteralExpr(
261 const CXXNullPtrLiteralExpr *N) {
262 /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized
263 /// pointers can use the same type of loan.
264 getOriginsList(E: *N);
265}
266
267void FactsGenerator::VisitImplicitCastExpr(const ImplicitCastExpr *ICE) {
268 OriginList *Dest = getOriginsList(E: *ICE);
269 if (!Dest)
270 return;
271 const Expr *SubExpr = ICE->getSubExpr();
272 OriginList *Src = getOriginsList(E: *SubExpr);
273
274 switch (ICE->getCastKind()) {
275 case CK_LValueToRValue:
276 // TODO: Decide what to do for x-values here.
277 if (!SubExpr->isLValue())
278 return;
279
280 assert(Src && "LValue being cast to RValue has no origin list");
281 // The result of an LValue-to-RValue cast on a pointer lvalue (like `q` in
282 // `int *p, *q; p = q;`) should propagate the inner origin (what the pointer
283 // points to), not the outer origin (the pointer's storage location). Strip
284 // the outer lvalue origin.
285 flow(Dst: getOriginsList(E: *ICE), Src: getRValueOrigins(E: SubExpr, List: Src),
286 /*Kill=*/true);
287 return;
288 case CK_NullToPointer:
289 getOriginsList(E: *ICE);
290 // TODO: Flow into them a null origin.
291 return;
292 case CK_NoOp:
293 case CK_ConstructorConversion:
294 case CK_UserDefinedConversion:
295 flow(Dst: Dest, Src, /*Kill=*/true);
296 return;
297 case CK_UncheckedDerivedToBase:
298 case CK_DerivedToBase:
299 // It is possible that the derived class and base class have different
300 // gsl::Pointer annotations. Skip if their origin shape differ.
301 if (Dest && Src && Dest->getLength() == Src->getLength())
302 flow(Dst: Dest, Src, /*Kill=*/true);
303 return;
304 case CK_ArrayToPointerDecay:
305 assert(Src && "Array expression should have origins as it is GL value");
306 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
307 args: Dest->getOuterOriginID(), args: Src->getOuterOriginID(), /*Kill=*/args: true));
308 return;
309 case CK_FunctionToPointerDecay:
310 case CK_BuiltinFnToFnPtr:
311 // Ignore function-to-pointer decays.
312 return;
313 default:
314 return;
315 }
316}
317
318void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) {
319 switch (UO->getOpcode()) {
320 case UO_AddrOf: {
321 const Expr *SubExpr = UO->getSubExpr();
322 // The origin of an address-of expression (e.g., &x) is the origin of
323 // its sub-expression (x). This fact will cause the dataflow analysis
324 // to propagate any loans held by the sub-expression's origin to the
325 // origin of this UnaryOperator expression.
326 killAndFlowOrigin(D: *UO, S: *SubExpr);
327 return;
328 }
329 case UO_Deref: {
330 const Expr *SubExpr = UO->getSubExpr();
331 killAndFlowOrigin(D: *UO, S: *SubExpr);
332 return;
333 }
334 default:
335 return;
336 }
337}
338
339void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) {
340 if (const Expr *RetExpr = RS->getRetValue()) {
341 if (OriginList *List = getOriginsList(E: *RetExpr))
342 for (OriginList *L = List; L != nullptr; L = L->peelOuterOrigin())
343 EscapesInCurrentBlock.push_back(Elt: FactMgr.createFact<ReturnEscapeFact>(
344 args: L->getOuterOriginID(), args&: RetExpr));
345 }
346}
347
348void FactsGenerator::handleAssignment(const Expr *LHSExpr,
349 const Expr *RHSExpr) {
350 LHSExpr = LHSExpr->IgnoreParenImpCasts();
351 OriginList *LHSList = nullptr;
352
353 if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(Val: LHSExpr)) {
354 LHSList = getOriginsList(E: *DRE_LHS);
355 assert(LHSList && "LHS is a DRE and should have an origin list");
356 }
357 // Handle assignment to member fields (e.g., `this->view = s` or `view = s`).
358 // This enables detection of dangling fields when local values escape to
359 // fields.
360 if (const auto *ME_LHS = dyn_cast<MemberExpr>(Val: LHSExpr)) {
361 LHSList = getOriginsList(E: *ME_LHS);
362 assert(LHSList && "LHS is a MemberExpr and should have an origin list");
363 }
364 if (!LHSList)
365 return;
366 OriginList *RHSList = getOriginsList(E: *RHSExpr);
367 // For operator= with reference parameters (e.g.,
368 // `View& operator=(const View&)`), the RHS argument stays an lvalue,
369 // unlike built-in assignment where LValueToRValue cast strips the outer
370 // lvalue origin. Strip it manually to get the actual value origins being
371 // assigned.
372 RHSList = getRValueOrigins(E: RHSExpr, List: RHSList);
373
374 if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(Val: LHSExpr))
375 markUseAsWrite(DRE: DRE_LHS);
376 // Kill the old loans of the destination origin and flow the new loans
377 // from the source origin.
378 flow(Dst: LHSList->peelOuterOrigin(), Src: RHSList, /*Kill=*/true);
379}
380
381void FactsGenerator::handlePointerArithmetic(const BinaryOperator *BO) {
382 if (Expr *RHS = BO->getRHS(); RHS->getType()->isPointerType()) {
383 killAndFlowOrigin(D: *BO, S: *RHS);
384 return;
385 }
386 Expr *LHS = BO->getLHS();
387 assert(LHS->getType()->isPointerType() &&
388 "Pointer arithmetic must have a pointer operand");
389 killAndFlowOrigin(D: *BO, S: *LHS);
390}
391
392void FactsGenerator::VisitBinaryOperator(const BinaryOperator *BO) {
393 if (BO->isCompoundAssignmentOp())
394 return;
395 if (BO->getType()->isPointerType() && BO->isAdditiveOp())
396 handlePointerArithmetic(BO);
397 handleUse(E: BO->getRHS());
398 if (BO->isAssignmentOp())
399 handleAssignment(LHSExpr: BO->getLHS(), RHSExpr: BO->getRHS());
400 // TODO: Handle assignments involving dereference like `*p = q`.
401}
402
403void FactsGenerator::VisitConditionalOperator(const ConditionalOperator *CO) {
404 if (hasOrigins(E: CO)) {
405 // Merge origins from both branches of the conditional operator.
406 // We kill to clear the initial state and merge both origins into it.
407 killAndFlowOrigin(D: *CO, S: *CO->getTrueExpr());
408 flowOrigin(D: *CO, S: *CO->getFalseExpr());
409 }
410}
411
412void FactsGenerator::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE) {
413 // Assignment operators have special "kill-then-propagate" semantics
414 // and are handled separately.
415 if (OCE->getOperator() == OO_Equal && OCE->getNumArgs() == 2 &&
416 hasOrigins(QT: OCE->getArg(Arg: 0)->getType())) {
417 // Pointer-like types: assignment inherently propagates origins.
418 QualType LHSTy = OCE->getArg(Arg: 0)->getType();
419 if (LHSTy->isPointerOrReferenceType() || isGslPointerType(QT: LHSTy)) {
420 handleAssignment(LHSExpr: OCE->getArg(Arg: 0), RHSExpr: OCE->getArg(Arg: 1));
421 return;
422 }
423 // Other tracked types: only defaulted operator= propagates origins.
424 // User-defined operator= has opaque semantics, so don't handle them now.
425 if (const auto *MD =
426 dyn_cast_or_null<CXXMethodDecl>(Val: OCE->getDirectCallee());
427 MD && MD->isDefaulted()) {
428 handleAssignment(LHSExpr: OCE->getArg(Arg: 0), RHSExpr: OCE->getArg(Arg: 1));
429 return;
430 }
431 }
432
433 ArrayRef Args = {OCE->getArgs(), OCE->getNumArgs()};
434 // For `static operator()`, the first argument is the object argument,
435 // remove it from the argument list to avoid off-by-one errors.
436 if (OCE->getOperator() == OO_Call && OCE->getDirectCallee()->isStatic())
437 Args = Args.slice(N: 1);
438 handleFunctionCall(Call: OCE, FD: OCE->getDirectCallee(), Args);
439}
440
441void FactsGenerator::VisitCXXFunctionalCastExpr(
442 const CXXFunctionalCastExpr *FCE) {
443 // Check if this is a test point marker. If so, we are done with this
444 // expression.
445 if (handleTestPoint(FCE))
446 return;
447 if (isGslPointerType(QT: FCE->getType()))
448 killAndFlowOrigin(D: *FCE, S: *FCE->getSubExpr());
449}
450
451void FactsGenerator::VisitInitListExpr(const InitListExpr *ILE) {
452 if (!hasOrigins(E: ILE))
453 return;
454 // For list initialization with a single element, like `View{...}`, the
455 // origin of the list itself is the origin of its single element.
456 if (ILE->getNumInits() == 1)
457 killAndFlowOrigin(D: *ILE, S: *ILE->getInit(Init: 0));
458}
459
460void FactsGenerator::VisitCXXBindTemporaryExpr(
461 const CXXBindTemporaryExpr *BTE) {
462 killAndFlowOrigin(D: *BTE, S: *BTE->getSubExpr());
463}
464
465void FactsGenerator::VisitMaterializeTemporaryExpr(
466 const MaterializeTemporaryExpr *MTE) {
467 assert(MTE->isGLValue());
468 OriginList *MTEList = getOriginsList(E: *MTE);
469 if (!MTEList)
470 return;
471 OriginList *SubExprList = getOriginsList(E: *MTE->getSubExpr());
472 assert((!SubExprList ||
473 MTEList->getLength() == (SubExprList->getLength() + 1)) &&
474 "MTE top level origin should contain a loan to the MTE itself");
475
476 OriginList *RValMTEList = getRValueOrigins(E: MTE, List: MTEList);
477 flow(Dst: RValMTEList, Src: SubExprList, /*Kill=*/true);
478 OriginID OuterMTEID = MTEList->getOuterOriginID();
479 if (MTE->getStorageDuration() == SD_FullExpression) {
480 // Issue a loan to MTE for the storage location represented by MTE.
481 const Loan *L = createLoan(FactMgr, MTE);
482 CurrentBlockFacts.push_back(
483 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args&: OuterMTEID));
484 }
485}
486
487void FactsGenerator::VisitLambdaExpr(const LambdaExpr *LE) {
488 // The lambda gets a single merged origin that aggregates all captured
489 // pointer-like origins. Currently we only need to detect whether the lambda
490 // outlives any capture.
491 OriginList *LambdaList = getOriginsList(E: *LE);
492 if (!LambdaList)
493 return;
494 bool Kill = true;
495 for (const Expr *Init : LE->capture_inits()) {
496 if (!Init)
497 continue;
498 OriginList *InitList = getOriginsList(E: *Init);
499 if (!InitList)
500 continue;
501 // FIXME: Consider flowing all origin levels once lambdas support more than
502 // one origin. Currently only the outermost origin is flowed, so by-ref
503 // captures like `[&p]` (where p is string_view) miss inner-level
504 // invalidation.
505 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
506 args: LambdaList->getOuterOriginID(), args: InitList->getOuterOriginID(), args&: Kill));
507 Kill = false;
508 }
509}
510
511void FactsGenerator::VisitArraySubscriptExpr(const ArraySubscriptExpr *ASE) {
512 assert(ASE->isGLValue() && "Array subscript should be a GL value");
513 OriginList *Dst = getOriginsList(E: *ASE);
514 assert(Dst && "Array subscript should have origins as it is a GL value");
515 OriginList *Src = getOriginsList(E: *ASE->getBase());
516 assert(Src && "Base of array subscript should have origins");
517 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
518 args: Dst->getOuterOriginID(), args: Src->getOuterOriginID(), /*Kill=*/args: true));
519}
520
521bool FactsGenerator::escapesViaReturn(OriginID OID) const {
522 return llvm::any_of(Range: EscapesInCurrentBlock, P: [OID](const Fact *F) {
523 if (const auto *EF = F->getAs<ReturnEscapeFact>())
524 return EF->getEscapedOriginID() == OID;
525 return false;
526 });
527}
528
529void FactsGenerator::handleLifetimeEnds(const CFGLifetimeEnds &LifetimeEnds) {
530 const VarDecl *LifetimeEndsVD = LifetimeEnds.getVarDecl();
531 if (!LifetimeEndsVD)
532 return;
533 // Expire the origin when its variable's lifetime ends to ensure liveness
534 // doesn't persist through loop back-edges.
535 std::optional<OriginID> ExpiredOID;
536 if (OriginList *List = getOriginsList(D: *LifetimeEndsVD)) {
537 OriginID OID = List->getOuterOriginID();
538 // Skip origins that escape via return; the escape checker needs their loans
539 // to remain until the return statement is processed.
540 if (!escapesViaReturn(OID))
541 ExpiredOID = OID;
542 }
543 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<ExpireFact>(
544 args: AccessPath(LifetimeEndsVD), args: LifetimeEnds.getTriggerStmt()->getEndLoc(),
545 args&: ExpiredOID));
546}
547
548void FactsGenerator::handleFullExprCleanup(
549 const CFGFullExprCleanup &FullExprCleanup) {
550 for (const auto *MTE : FullExprCleanup.getExpiringMTEs())
551 CurrentBlockFacts.push_back(
552 Elt: FactMgr.createFact<ExpireFact>(args: AccessPath(MTE), args: MTE->getEndLoc()));
553}
554
555void FactsGenerator::handleExitBlock() {
556 for (const Origin &O : FactMgr.getOriginMgr().getOrigins())
557 if (auto *FD = dyn_cast_if_present<FieldDecl>(Val: O.getDecl()))
558 // Create FieldEscapeFacts for all field origins that remain live at exit.
559 EscapesInCurrentBlock.push_back(
560 Elt: FactMgr.createFact<FieldEscapeFact>(args: O.ID, args&: FD));
561 else if (auto *VD = dyn_cast_if_present<VarDecl>(Val: O.getDecl())) {
562 // Create GlobalEscapeFacts for all origins with global-storage that
563 // remain live at exit.
564 if (VD->hasGlobalStorage()) {
565 EscapesInCurrentBlock.push_back(
566 Elt: FactMgr.createFact<GlobalEscapeFact>(args: O.ID, args&: VD));
567 }
568 }
569}
570
571void FactsGenerator::handleGSLPointerConstruction(const CXXConstructExpr *CCE) {
572 assert(isGslPointerType(CCE->getType()));
573 if (CCE->getNumArgs() != 1)
574 return;
575
576 const Expr *Arg = CCE->getArg(Arg: 0);
577 if (isGslPointerType(QT: Arg->getType())) {
578 OriginList *ArgList = getOriginsList(E: *Arg);
579 assert(ArgList && "GSL pointer argument should have an origin list");
580 // GSL pointer is constructed from another gsl pointer.
581 // Example:
582 // View(View v);
583 // View(const View &v);
584 ArgList = getRValueOrigins(E: Arg, List: ArgList);
585 flow(Dst: getOriginsList(E: *CCE), Src: ArgList, /*Kill=*/true);
586 } else if (Arg->getType()->isPointerType()) {
587 // GSL pointer is constructed from a raw pointer. Flow only the outermost
588 // raw pointer. Example:
589 // View(const char*);
590 // Span<int*>(const in**);
591 OriginList *ArgList = getOriginsList(E: *Arg);
592 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
593 args: getOriginsList(E: *CCE)->getOuterOriginID(), args: ArgList->getOuterOriginID(),
594 /*Kill=*/args: true));
595 } else {
596 // This could be a new borrow.
597 // TODO: Add code example here.
598 handleFunctionCall(Call: CCE, FD: CCE->getConstructor(),
599 Args: {CCE->getArgs(), CCE->getNumArgs()},
600 /*IsGslConstruction=*/true);
601 }
602}
603
604void FactsGenerator::handleMovedArgsInCall(const FunctionDecl *FD,
605 ArrayRef<const Expr *> Args) {
606 unsigned IsInstance = 0;
607 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
608 MD && MD->isInstance() && !isa<CXXConstructorDecl>(Val: FD)) {
609 IsInstance = 1;
610 // std::unique_ptr::release() transfers ownership.
611 // Treat it as a move to prevent false-positive warnings when the unique_ptr
612 // destructor runs after ownership has been transferred.
613 if (isUniquePtrRelease(MD: *MD)) {
614 const Expr *UniquePtrExpr = Args[0];
615 OriginList *MovedOrigins = getOriginsList(E: *UniquePtrExpr);
616 if (MovedOrigins)
617 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<MovedOriginFact>(
618 args&: UniquePtrExpr, args: MovedOrigins->getOuterOriginID()));
619 }
620 }
621
622 // Skip 'this' arg as it cannot be moved.
623 for (unsigned I = IsInstance;
624 I < Args.size() && I < FD->getNumParams() + IsInstance; ++I) {
625 const ParmVarDecl *PVD = FD->getParamDecl(i: I - IsInstance);
626 if (!PVD->getType()->isRValueReferenceType())
627 continue;
628 const Expr *Arg = Args[I];
629 OriginList *MovedOrigins = getOriginsList(E: *Arg);
630 assert(MovedOrigins->getLength() >= 1 &&
631 "unexpected length for r-value reference param");
632 // Arg is being moved to this parameter. Mark the origin as moved.
633 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<MovedOriginFact>(
634 args&: Arg, args: MovedOrigins->getOuterOriginID()));
635 }
636}
637
638void FactsGenerator::handleInvalidatingCall(const Expr *Call,
639 const FunctionDecl *FD,
640 ArrayRef<const Expr *> Args) {
641 const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
642 if (!MD || !MD->isInstance())
643 return;
644
645 if (!isContainerInvalidationMethod(MD: *MD))
646 return;
647 // Heuristics to turn-down false positives.
648 auto *DRE = dyn_cast<DeclRefExpr>(Val: Args[0]);
649 if (!DRE || DRE->getDecl()->getType()->isReferenceType())
650 return;
651
652 OriginList *ThisList = getOriginsList(E: *Args[0]);
653 if (ThisList)
654 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<InvalidateOriginFact>(
655 args: ThisList->getOuterOriginID(), args&: Call));
656}
657
658void FactsGenerator::handleFunctionCall(const Expr *Call,
659 const FunctionDecl *FD,
660 ArrayRef<const Expr *> Args,
661 bool IsGslConstruction) {
662 OriginList *CallList = getOriginsList(E: *Call);
663 // Ignore functions returning values with no origin.
664 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
665 if (!FD)
666 return;
667 // All arguments to a function are a use of the corresponding expressions.
668 for (const Expr *Arg : Args)
669 handleUse(E: Arg);
670 handleInvalidatingCall(Call, FD, Args);
671 handleMovedArgsInCall(FD, Args);
672 if (!CallList)
673 return;
674 auto IsArgLifetimeBound = [FD](unsigned I) -> bool {
675 const ParmVarDecl *PVD = nullptr;
676 if (const auto *Method = dyn_cast<CXXMethodDecl>(Val: FD);
677 Method && Method->isInstance() && !isa<CXXConstructorDecl>(Val: FD)) {
678 if (I == 0)
679 // For the 'this' argument, the attribute is on the method itself.
680 return implicitObjectParamIsLifetimeBound(FD: Method) ||
681 shouldTrackImplicitObjectArg(
682 Callee: Method, /*RunningUnderLifetimeSafety=*/true);
683 if ((I - 1) < Method->getNumParams())
684 // For explicit arguments, find the corresponding parameter
685 // declaration.
686 PVD = Method->getParamDecl(i: I - 1);
687 } else if (I == 0 && shouldTrackFirstArgument(FD)) {
688 return true;
689 } else if (I < FD->getNumParams()) {
690 // For free functions or static methods.
691 PVD = FD->getParamDecl(i: I);
692 }
693 return PVD ? PVD->hasAttr<clang::LifetimeBoundAttr>() : false;
694 };
695 auto shouldTrackPointerImplicitObjectArg = [FD](unsigned I) -> bool {
696 const auto *Method = dyn_cast<CXXMethodDecl>(Val: FD);
697 if (!Method || !Method->isInstance())
698 return false;
699 return I == 0 &&
700 isGslPointerType(QT: Method->getFunctionObjectParameterType()) &&
701 shouldTrackImplicitObjectArg(Callee: Method,
702 /*RunningUnderLifetimeSafety=*/true);
703 };
704 if (Args.empty())
705 return;
706 bool KillSrc = true;
707 for (unsigned I = 0; I < Args.size(); ++I) {
708 OriginList *ArgList = getOriginsList(E: *Args[I]);
709 if (!ArgList)
710 continue;
711 if (IsGslConstruction) {
712 // TODO: document with code example.
713 // std::string_view(const std::string_view& from)
714 if (isGslPointerType(QT: Args[I]->getType())) {
715 assert(!Args[I]->isGLValue() || ArgList->getLength() >= 2);
716 ArgList = getRValueOrigins(E: Args[I], List: ArgList);
717 }
718 if (isGslOwnerType(QT: Args[I]->getType())) {
719 // The constructed gsl::Pointer borrows from the Owner's storage, not
720 // from what the Owner itself borrows, so only the outermost origin is
721 // needed.
722 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
723 args: CallList->getOuterOriginID(), args: ArgList->getOuterOriginID(),
724 args&: KillSrc));
725 KillSrc = false;
726 }
727 } else if (shouldTrackPointerImplicitObjectArg(I)) {
728 assert(ArgList->getLength() >= 2 &&
729 "Object arg of pointer type should have atleast two origins");
730 // See through the GSLPointer reference to see the pointer's value.
731 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
732 args: CallList->getOuterOriginID(),
733 args: ArgList->peelOuterOrigin()->getOuterOriginID(), args&: KillSrc));
734 KillSrc = false;
735 } else if (IsArgLifetimeBound(I)) {
736 // Lifetimebound on a non-GSL-ctor function means the returned
737 // pointer/reference itself must not outlive the arguments. This
738 // only constraints the top-level origin.
739 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
740 args: CallList->getOuterOriginID(), args: ArgList->getOuterOriginID(), args&: KillSrc));
741 KillSrc = false;
742 }
743 }
744}
745
746/// Checks if the expression is a `void("__lifetime_test_point_...")` cast.
747/// If so, creates a `TestPointFact` and returns true.
748bool FactsGenerator::handleTestPoint(const CXXFunctionalCastExpr *FCE) {
749 if (!FCE->getType()->isVoidType())
750 return false;
751
752 const auto *SubExpr = FCE->getSubExpr()->IgnoreParenImpCasts();
753 if (const auto *SL = dyn_cast<StringLiteral>(Val: SubExpr)) {
754 llvm::StringRef LiteralValue = SL->getString();
755 const std::string Prefix = "__lifetime_test_point_";
756
757 if (LiteralValue.starts_with(Prefix)) {
758 StringRef Annotation = LiteralValue.drop_front(N: Prefix.length());
759 CurrentBlockFacts.push_back(
760 Elt: FactMgr.createFact<TestPointFact>(args&: Annotation));
761 return true;
762 }
763 }
764 return false;
765}
766
767void FactsGenerator::handleUse(const Expr *E) {
768 OriginList *List = getOriginsList(E: *E);
769 if (!List)
770 return;
771 // For DeclRefExpr: Remove the outer layer of origin which borrows from the
772 // decl directly (e.g., when this is not a reference). This is a use of the
773 // underlying decl.
774 if (auto *DRE = dyn_cast<DeclRefExpr>(Val: E);
775 DRE && !DRE->getDecl()->getType()->isReferenceType())
776 List = getRValueOrigins(E: DRE, List);
777 // Skip if there is no inner origin (e.g., when it is not a pointer type).
778 if (!List)
779 return;
780 if (!UseFacts.contains(Val: E)) {
781 UseFact *UF = FactMgr.createFact<UseFact>(args&: E, args&: List);
782 CurrentBlockFacts.push_back(Elt: UF);
783 UseFacts[E] = UF;
784 }
785}
786
787void FactsGenerator::markUseAsWrite(const DeclRefExpr *DRE) {
788 if (UseFacts.contains(Val: DRE))
789 UseFacts[DRE]->markAsWritten();
790}
791
792// Creates an IssueFact for a new placeholder loan for each pointer or reference
793// parameter at the function's entry.
794llvm::SmallVector<Fact *> FactsGenerator::issuePlaceholderLoans() {
795 const auto *FD = dyn_cast<FunctionDecl>(Val: AC.getDecl());
796 if (!FD)
797 return {};
798
799 llvm::SmallVector<Fact *> PlaceholderLoanFacts;
800 if (auto ThisOrigins = FactMgr.getOriginMgr().getThisOrigins()) {
801 OriginList *List = *ThisOrigins;
802 const Loan *L = FactMgr.getLoanMgr().createLoan(
803 Path: AccessPath::Placeholder(MD: cast<CXXMethodDecl>(Val: FD)),
804 /*IssuingExpr=*/IssueExpr: nullptr);
805 PlaceholderLoanFacts.push_back(
806 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
807 }
808 for (const ParmVarDecl *PVD : FD->parameters()) {
809 OriginList *List = getOriginsList(D: *PVD);
810 if (!List)
811 continue;
812 const Loan *L = FactMgr.getLoanMgr().createLoan(
813 Path: AccessPath::Placeholder(PVD), /*IssuingExpr=*/IssueExpr: nullptr);
814 PlaceholderLoanFacts.push_back(
815 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
816 }
817 return PlaceholderLoanFacts;
818}
819
820} // namespace clang::lifetimes::internal
821