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)
61///
62/// \param Dst The destination origin list.
63/// \param Src The source origin list.
64/// \param Kill If true, the destination's existing loans are killed before
65/// flowing.
66/// \param Block Optional. If provided, the generated flow facts are appended to
67/// this specific CFG block. Otherwise, they are appended to the
68/// current block being visited.
69void FactsGenerator::flow(OriginList *Dst, OriginList *Src, bool Kill,
70 const CFGBlock *Block) {
71 if (!Dst)
72 return;
73 assert(Src &&
74 "Dst is non-null but Src is null. List must have the same length");
75 assert(Dst->getLength() == Src->getLength() &&
76 "Lists must have the same length");
77
78 while (Dst && Src) {
79 Fact *F = FactMgr.createFact<OriginFlowFact>(args: Dst->getOuterOriginID(),
80 args: Src->getOuterOriginID(), args&: Kill);
81 if (Block)
82 FactMgr.appendBlockFact(B: Block, F);
83 else
84 CurrentBlockFacts.push_back(Elt: F);
85 Dst = Dst->peelOuterOrigin();
86 Src = Src->peelOuterOrigin();
87 }
88}
89
90/// Creates a loan for the storage path of a given declaration reference.
91/// This function should be called whenever a DeclRefExpr represents a borrow.
92/// \param DRE The declaration reference expression that initiates the borrow.
93/// \return The new Loan on success, nullptr otherwise.
94static const Loan *createLoan(FactManager &FactMgr, const DeclRefExpr *DRE) {
95 const ValueDecl *VD = DRE->getDecl();
96 AccessPath Path(VD);
97 // The loan is created at the location of the DeclRefExpr.
98 return FactMgr.getLoanMgr().createLoan(Path, IssueExpr: DRE);
99}
100
101/// Creates a loan for the storage location of a temporary object.
102/// \param MTE The MaterializeTemporaryExpr that represents the temporary
103/// binding. \return The new Loan.
104static const Loan *createLoan(FactManager &FactMgr,
105 const MaterializeTemporaryExpr *MTE) {
106 AccessPath Path(MTE);
107 return FactMgr.getLoanMgr().createLoan(Path, IssueExpr: MTE);
108}
109
110/// Creates a loan for an allocation through 'new'
111/// \param NE The CXXNewExpr that represents the allocation
112/// \return The new Loan on success, nullptr otherwise
113static const Loan *createLoan(FactManager &FactMgr, const CXXNewExpr *NE) {
114 AccessPath Path(NE);
115 return FactMgr.getLoanMgr().createLoan(Path, IssueExpr: NE);
116}
117
118void FactsGenerator::run() {
119 llvm::TimeTraceScope TimeProfile("FactGenerator");
120 const CFG &Cfg = *AC.getCFG();
121 llvm::SmallVector<Fact *> PlaceholderLoanFacts = issuePlaceholderLoans();
122 // Iterate through the CFG blocks in reverse post-order to ensure that
123 // initializations and destructions are processed in the correct sequence.
124 for (const CFGBlock *Block : *AC.getAnalysis<PostOrderCFGView>()) {
125 CurrentBlockFacts.clear();
126 EscapesInCurrentBlock.clear();
127 CurrentBlock = Block;
128 if (Block == &Cfg.getEntry())
129 CurrentBlockFacts.append(in_start: PlaceholderLoanFacts.begin(),
130 in_end: PlaceholderLoanFacts.end());
131 for (unsigned I = 0; I < Block->size(); ++I) {
132 const CFGElement &Element = Block->Elements[I];
133 if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>())
134 Visit(S: CS->getStmt());
135 else if (std::optional<CFGInitializer> Initializer =
136 Element.getAs<CFGInitializer>())
137 handleCXXCtorInitializer(CII: Initializer->getInitializer());
138 else if (std::optional<CFGLifetimeEnds> LifetimeEnds =
139 Element.getAs<CFGLifetimeEnds>())
140 handleLifetimeEnds(LifetimeEnds: *LifetimeEnds);
141 else if (std::optional<CFGFullExprCleanup> FullExprCleanup =
142 Element.getAs<CFGFullExprCleanup>()) {
143 handleFullExprCleanup(FullExprCleanup: *FullExprCleanup);
144 }
145 }
146 if (Block == &Cfg.getExit())
147 handleExitBlock();
148
149 CurrentBlockFacts.append(in_start: EscapesInCurrentBlock.begin(),
150 in_end: EscapesInCurrentBlock.end());
151 FactMgr.addBlockFacts(B: Block, NewFacts: CurrentBlockFacts);
152 }
153 FactMgr.computePersistentOrigins(Cfg);
154}
155
156OriginList *FactsGenerator::readValue(const Expr *E) {
157 OriginList *List = getOriginsList(E: *E);
158 if (!List)
159 return nullptr;
160 if (!E->isGLValue())
161 return List;
162 handleAccess(E);
163 return List->peelOuterOrigin();
164}
165
166void FactsGenerator::VisitDeclStmt(const DeclStmt *DS) {
167 for (const Decl *D : DS->decls())
168 if (const auto *VD = dyn_cast<VarDecl>(Val: D))
169 if (const Expr *InitExpr = VD->getInit()) {
170 OriginList *VDList = getOriginsList(D: *VD);
171 if (!VDList)
172 continue;
173 OriginList *InitList = getOriginsList(E: *InitExpr);
174 assert(InitList && "VarDecl had origins but InitExpr did not");
175 flow(Dst: VDList, Src: InitList, /*Kill=*/true);
176 }
177}
178
179void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) {
180 // Skip function references as their lifetimes are not interesting. Skip non
181 // GLValues (like EnumConstants).
182 if (DRE->getFoundDecl()->isFunctionOrFunctionTemplate() || !DRE->isGLValue())
183 return;
184 // For all declarations with storage (non-references), we issue a loan
185 // representing the borrow of the variable's storage itself.
186 //
187 // Examples:
188 // - `int x; x` issues loan to x's storage
189 // - `int* p; p` issues loan to p's storage (the pointer variable)
190 // - `View v; v` issues loan to v's storage (the view object)
191 // - `int& r = x; r` issues no loan (r has no storage, it's an alias to x)
192 if (doesDeclHaveStorage(D: DRE->getDecl())) {
193 const Loan *L = createLoan(FactMgr, DRE);
194 assert(L);
195 OriginList *List = getOriginsList(E: *DRE);
196 assert(List &&
197 "gl-value DRE of non-pointer type should have an origin list");
198 // This loan specifically tracks borrowing the variable's storage location
199 // itself and is issued to outermost origin (List->OID).
200 CurrentBlockFacts.push_back(
201 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
202 }
203}
204
205void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
206 if (isGslPointerType(QT: CCE->getType())) {
207 handleGSLPointerConstruction(CCE);
208 return;
209 }
210 // For defaulted (implicit or `= default`) copy/move constructors, propagate
211 // origins directly. User-defined copy/move constructors are not handled here
212 // as they have opaque semantics.
213 if (CCE->getConstructor()->isCopyOrMoveConstructor() &&
214 CCE->getConstructor()->isDefaulted() && CCE->getNumArgs() == 1 &&
215 hasOrigins(QT: CCE->getType())) {
216 const Expr *Arg = CCE->getArg(Arg: 0);
217 if (OriginList *ArgList = readValue(E: Arg)) {
218 flow(Dst: getOriginsList(E: *CCE), Src: ArgList, /*Kill=*/true);
219 return;
220 }
221 }
222 // Standard library callable wrappers (e.g., std::function) propagate the
223 // stored lambda's origins.
224 if (const auto *RD = CCE->getType()->getAsCXXRecordDecl();
225 RD && isStdCallableWrapperType(RD) && CCE->getNumArgs() == 1) {
226 const Expr *Arg = CCE->getArg(Arg: 0);
227 if (OriginList *ArgList = readValue(E: Arg)) {
228 flow(Dst: getOriginsList(E: *CCE), Src: ArgList, /*Kill=*/true);
229 return;
230 }
231 }
232 handleFunctionCall(Call: CCE, /*IsGslConstruction=*/false);
233}
234
235void FactsGenerator::VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *DIE) {
236 if (const Expr *Init = DIE->getExpr())
237 killAndFlowOrigin(D: *DIE, S: *Init);
238}
239
240void FactsGenerator::handleCXXCtorInitializer(const CXXCtorInitializer *CII) {
241 // Flows origins from the initializer expression to the field.
242 // Example: `MyObj(std::string s) : view(s) {}`
243 if (const FieldDecl *FD = CII->getAnyMember())
244 killAndFlowOrigin(D: *FD, S: *CII->getInit());
245}
246
247void FactsGenerator::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE) {
248 // Specifically for conversion operators,
249 // like `std::string_view p = std::string{};`
250 if (isGslPointerType(QT: MCE->getType()) &&
251 isa_and_present<CXXConversionDecl>(Val: MCE->getCalleeDecl()) &&
252 isGslOwnerType(QT: MCE->getImplicitObjectArgument()->getType())) {
253 handleFunctionCall(Call: MCE, /*IsGslConstruction=*/true);
254 return;
255 }
256 handleFunctionCall(Call: MCE, /*IsGslConstruction=*/false);
257}
258
259void FactsGenerator::VisitMemberExpr(const MemberExpr *ME) {
260 auto *MD = ME->getMemberDecl();
261 if (isa<FieldDecl>(Val: MD) && doesDeclHaveStorage(D: MD)) {
262 assert(ME->isGLValue() && "Field member should be GL value");
263 OriginList *Dst = getOriginsList(E: *ME);
264 assert(Dst && "Field member should have an origin list as it is GL value");
265 OriginList *Src = getOriginsList(E: *ME->getBase());
266 assert(Src && "Base expression should be a pointer/reference type");
267 // The field's glvalue (outermost origin) holds the same loans as the base
268 // expression.
269 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
270 args: Dst->getOuterOriginID(), args: Src->getOuterOriginID(),
271 /*Kill=*/args: true));
272 }
273}
274
275void FactsGenerator::VisitCallExpr(const CallExpr *CE) {
276 handleFunctionCall(Call: CE);
277}
278
279void FactsGenerator::VisitCXXNullPtrLiteralExpr(
280 const CXXNullPtrLiteralExpr *N) {
281 /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized
282 /// pointers can use the same type of loan.
283 getOriginsList(E: *N);
284}
285
286void FactsGenerator::VisitCastExpr(const CastExpr *CE) {
287 const Expr *SubExpr = CE->getSubExpr();
288 // May be null: loading an `int` has no origins but still reads the operand.
289 OriginList *Dest = getOriginsList(E: *CE);
290 OriginList *Src = Dest ? getOriginsList(E: *SubExpr) : nullptr;
291
292 switch (CE->getCastKind()) {
293 case CK_LValueToRValue:
294 // The result of an LValue-to-RValue cast on a pointer lvalue (like `q` in
295 // `int *p, *q; p = q;`) should propagate the inner origin (what the pointer
296 // points to), not the outer origin (the pointer's storage location).
297 flow(Dst: Dest, Src: readValue(E: SubExpr), /*Kill=*/true);
298 return;
299 case CK_Dynamic:
300 handleAccess(E: SubExpr);
301 return;
302 case CK_NullToPointer:
303 // TODO: Flow into them a null origin.
304 return;
305 case CK_NoOp:
306 case CK_ConstructorConversion:
307 case CK_UserDefinedConversion:
308 flow(Dst: Dest, Src, /*Kill=*/true);
309 return;
310 case CK_UncheckedDerivedToBase:
311 case CK_DerivedToBase:
312 case CK_BaseToDerived:
313 // The conversion cast doesn't change what it refers to, so preserve the
314 // borrow if we can.
315 // It is possible that the derived class and base class have different
316 // gsl::Pointer annotations. Skip if their origin shape differ.
317 if (Dest && Src && Dest->getLength() == Src->getLength())
318 flow(Dst: Dest, Src, /*Kill=*/true);
319 return;
320 case CK_ArrayToPointerDecay:
321 // va_arg(ap, array_type) is UB and does not provide addressable array
322 // storage to model.
323 if (!Dest || isa<VAArgExpr>(Val: SubExpr->IgnoreParens()))
324 return;
325 assert(Src && "Array expression should have origins as it is GL value");
326 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
327 args: Dest->getOuterOriginID(), args: Src->getOuterOriginID(), /*Kill=*/args: true));
328 return;
329 case CK_FunctionToPointerDecay:
330 case CK_BuiltinFnToFnPtr:
331 // Ignore function-to-pointer decays.
332 return;
333 case CK_BitCast:
334 // OriginLists for Src and Dst may differ here. For example when casting
335 // from int** to void*
336 if (Src && Dest && Dest->getLength() == Src->getLength())
337 flow(Dst: Dest, Src, /*Kill=*/true);
338 return;
339 case CK_LValueToRValueBitCast:
340 case CK_NonAtomicToAtomic:
341 case CK_AtomicToNonAtomic: {
342 // `__builtin_bit_cast`/`std::bit_cast` of a pointer, and
343 // wrapping/unwrapping `_Atomic(T*)`, preserve the pointer value, so
344 // propagate the borrow. readValue peels a glvalue operand's storage level
345 // and records the read. A bit-cast that materializes a pointer from a
346 // non-pointer representation has no matching source origin and is
347 // untracked.
348 OriginList *RVSrc = readValue(E: SubExpr);
349 if (Dest && RVSrc && Dest->getLength() == RVSrc->getLength())
350 flow(Dst: Dest, Src: RVSrc, /*Kill=*/true);
351 return;
352 }
353 default:
354 return;
355 }
356}
357
358void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) {
359 switch (UO->getOpcode()) {
360 case UO_AddrOf: {
361 const Expr *SubExpr = UO->getSubExpr();
362 // Function addresses do not need lifetime tracking.
363 if (SubExpr->getType()->isFunctionType())
364 return;
365 // Skip address-of on void expressions: GNU C permits them, but void itself
366 // has no origins to track.
367 if (IsCMode && SubExpr->getType()->isVoidType())
368 return;
369 assert(!SubExpr->getType()->isVoidType() &&
370 "Taking address of void is not valid in C++");
371 // The origin of an address-of expression (e.g., &x) is the origin of
372 // its sub-expression (x). This fact will cause the dataflow analysis
373 // to propagate any loans held by the sub-expression's origin to the
374 // origin of this UnaryOperator expression.
375 killAndFlowOrigin(D: *UO, S: *SubExpr);
376 return;
377 }
378 case UO_Deref: {
379 const Expr *SubExpr = UO->getSubExpr();
380 killAndFlowOrigin(D: *UO, S: *SubExpr);
381 return;
382 }
383 case UO_Plus: {
384 // Unary plus on a pointer is the identity (`+p == p`), so the prvalue
385 // result carries the operand's loans. Flow the operand's rvalue origins
386 // (peeling storage only when the operand is itself a glvalue).
387 if (!UO->getType()->isPointerType())
388 return;
389 const Expr *SubExpr = UO->getSubExpr();
390 flow(Dst: getOriginsList(E: *UO), Src: readValue(E: SubExpr), /*Kill=*/true);
391 return;
392 }
393 case UO_PreInc:
394 case UO_PostInc:
395 case UO_PreDec:
396 case UO_PostDec: {
397 handleAccess(E: UO->getSubExpr());
398 // Inc/dec keeps a pointer in the same allocation, so the result carries the
399 // operand's loans. Peel the operand's storage origin when the *result* is a
400 // prvalue (post-inc/dec, or any form in C).
401 if (!UO->getType()->isPointerType())
402 return;
403 OriginList *SubList = getOriginsList(E: *UO->getSubExpr());
404 flow(Dst: getOriginsList(E: *UO),
405 Src: UO->isGLValue() ? SubList : SubList->peelOuterOrigin(), /*Kill=*/true);
406 return;
407 }
408 default:
409 return;
410 }
411}
412
413void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) {
414 if (const Expr *RetExpr = RS->getRetValue()) {
415 if (OriginList *List = getOriginsList(E: *RetExpr))
416 for (OriginList *L = List; L != nullptr; L = L->peelOuterOrigin())
417 EscapesInCurrentBlock.push_back(Elt: FactMgr.createFact<ReturnEscapeFact>(
418 args: L->getOuterOriginID(), args&: RetExpr));
419 }
420}
421
422void FactsGenerator::handleAssignment(const Expr *TargetExpr,
423 const Expr *LHSExpr,
424 const Expr *RHSExpr) {
425 LHSExpr = LHSExpr->IgnoreParenImpCasts();
426 handleAccess(E: LHSExpr);
427 OriginList *RHSList = readValue(E: RHSExpr);
428 OriginList *LHSList = nullptr;
429
430 if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(Val: LHSExpr)) {
431 LHSList = getOriginsList(E: *DRE_LHS);
432 assert(LHSList && "LHS is a DRE and should have an origin list");
433 }
434 // Handle assignment to member fields (e.g., `this->view = s` or `view = s`).
435 // This enables detection of dangling fields when local values escape to
436 // fields.
437 if (const auto *ME_LHS = dyn_cast<MemberExpr>(Val: LHSExpr)) {
438 LHSList = getOriginsList(E: *ME_LHS);
439 assert(LHSList && "LHS is a MemberExpr and should have an origin list");
440 }
441 if (!LHSList)
442 return;
443
444 if (!RHSList) {
445 // RHS has no tracked origins (e.g., assigning a callable without origins
446 // to std::function). Clear loans of the destination.
447 for (OriginList *LHSInner = LHSList->peelOuterOrigin(); LHSInner;
448 LHSInner = LHSInner->peelOuterOrigin())
449 CurrentBlockFacts.push_back(
450 Elt: FactMgr.createFact<KillOriginFact>(args: LHSInner->getOuterOriginID()));
451 return;
452 }
453 // Kill the old loans of the destination origin and flow the new loans
454 // from the source origin.
455 flow(Dst: LHSList->peelOuterOrigin(), Src: RHSList, /*Kill=*/true);
456
457 // In C, assignment expressions are not GLValues, so the assignment result has
458 // the assigned value origins, not the LHS storage origin.
459 if (IsCMode)
460 LHSList = LHSList->peelOuterOrigin();
461 flow(Dst: getOriginsList(E: *TargetExpr), Src: LHSList, /*Kill=*/true);
462}
463
464void FactsGenerator::handlePointerArithmetic(const BinaryOperator *BO) {
465 if (Expr *RHS = BO->getRHS(); RHS->getType()->isPointerType()) {
466 killAndFlowOrigin(D: *BO, S: *RHS);
467 return;
468 }
469 Expr *LHS = BO->getLHS();
470 assert(LHS->getType()->isPointerType() &&
471 "Pointer arithmetic must have a pointer operand");
472 killAndFlowOrigin(D: *BO, S: *LHS);
473}
474
475void FactsGenerator::VisitBinaryOperator(const BinaryOperator *BO) {
476 if (BO->getOpcode() == BO_PtrMemD || BO->getOpcode() == BO_PtrMemI) {
477 // `obj.*pm` / `objptr->*pm` names a member of the object, so a borrow of it
478 // borrows the object; flow the object's origin into the result. For `.*`
479 // the object is the LHS; for `->*` it is the LHS pointer's pointee.
480 //
481 // Only the result's outer (storage) origin relates to the object: borrowing
482 // the member borrows the object's storage. Deeper levels of the result (a
483 // pointer/view member's own pointee) are the member's value, with no
484 // counterpart in the object's origin -- so the lists may differ in length
485 // and we flow just the top level, leaving the member's value untouched.
486 OriginList *Dst = getOriginsList(E: *BO);
487 OriginList *ObjSrc = BO->getOpcode() == BO_PtrMemD
488 ? getOriginsList(E: *BO->getLHS())
489 : readValue(E: BO->getLHS());
490 if (Dst && ObjSrc)
491 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
492 args: Dst->getOuterOriginID(), args: ObjSrc->getOuterOriginID(), /*Kill=*/args: true));
493 return;
494 }
495 if (BO->getOpcode() == BO_Comma) {
496 killAndFlowOrigin(D: *BO, S: *BO->getRHS());
497 return;
498 }
499 if (BO->isCompoundAssignmentOp()) {
500 handleAccess(E: BO->getLHS());
501 // A pointer compound additive assignment (`p += n`) carries the LHS's loans
502 // like inc/dec above; in C the result is a prvalue, so peel its outer
503 // (storage) origin.
504 if (BO->getType()->isPointerType()) {
505 OriginList *LHSList = getOriginsList(E: *BO->getLHS());
506 flow(Dst: getOriginsList(E: *BO), Src: IsCMode ? LHSList->peelOuterOrigin() : LHSList,
507 /*Kill=*/true);
508 }
509 return;
510 }
511 if (BO->getType()->isPointerType() && BO->isAdditiveOp())
512 handlePointerArithmetic(BO);
513 if (BO->isAssignmentOp())
514 handleAssignment(TargetExpr: BO, LHSExpr: BO->getLHS(), RHSExpr: BO->getRHS());
515 // TODO: Propagate origins for assignments through a dereference (`*p = q`).
516}
517
518static const CFGBlock *findPredBlockForExpr(const CFGBlock *MergeBlock,
519 const Expr *ArmExpr) {
520 if (!ArmExpr)
521 return nullptr;
522 const Expr *Target = ArmExpr->IgnoreParenImpCasts();
523 if (const auto *OVE = dyn_cast<OpaqueValueExpr>(Val: Target))
524 if (const Expr *Src = OVE->getSourceExpr())
525 Target = Src->IgnoreParenImpCasts();
526
527 for (const CFGBlock *Pred : MergeBlock->preds()) {
528 if (!Pred)
529 continue;
530 for (const CFGElement &Elt : *Pred)
531 if (auto CS = Elt.getAs<CFGStmt>())
532 if (const auto *E = dyn_cast<Expr>(Val: CS->getStmt()))
533 if (E->IgnoreParenImpCasts() == Target)
534 return Pred;
535 }
536 return nullptr;
537}
538
539/// Visits conditional operators (e.g., `cond ? a : b`).
540///
541/// To prevent liveness leakage across loop backedges (which causes false
542/// positives like in `while (...) { int x; consume(cond ? &x : nullptr); }`),
543/// we generate the flow facts in the respective predecessor blocks of the arms
544/// rather than in the merge block. This ensures that the liveness of the
545/// temporary origin from one arm does not propagate into the other arm's path.
546void FactsGenerator::VisitAbstractConditionalOperator(
547 const AbstractConditionalOperator *CO) {
548 if (!hasOrigins(E: CO))
549 return;
550
551 const Expr *TrueExpr = CO->getTrueExpr();
552 const Expr *FalseExpr = CO->getFalseExpr();
553
554 if (const CFGBlock *TBPred = findPredBlockForExpr(MergeBlock: CurrentBlock, ArmExpr: TrueExpr))
555 flow(Dst: getOriginsList(E: *CO), Src: getOriginsList(E: *TrueExpr), /*Kill=*/true, Block: TBPred);
556 if (const CFGBlock *FBPred = findPredBlockForExpr(MergeBlock: CurrentBlock, ArmExpr: FalseExpr))
557 flow(Dst: getOriginsList(E: *CO), Src: getOriginsList(E: *FalseExpr), /*Kill=*/true,
558 Block: FBPred);
559}
560
561void FactsGenerator::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE) {
562 // Assignment operators have special "kill-then-propagate" semantics
563 // and are handled separately.
564 if (OCE->getOperator() == OO_Equal && OCE->getNumArgs() == 2 &&
565 hasOrigins(QT: OCE->getArg(Arg: 0)->getType())) {
566 // Pointer-like types: assignment inherently propagates origins.
567 QualType LHSTy = OCE->getArg(Arg: 0)->getType();
568 if (LHSTy->isPointerOrReferenceType() || isGslPointerType(QT: LHSTy) ||
569 isGslOwnerType(QT: LHSTy)) {
570 handleAssignment(TargetExpr: OCE, LHSExpr: OCE->getArg(Arg: 0), RHSExpr: OCE->getArg(Arg: 1));
571 return;
572 }
573 // Standard library callable wrappers (e.g., std::function) can propagate
574 // the stored lambda's origins.
575 if (const auto *RD = LHSTy->getAsCXXRecordDecl();
576 RD && isStdCallableWrapperType(RD)) {
577 handleAssignment(TargetExpr: OCE, LHSExpr: OCE->getArg(Arg: 0), RHSExpr: OCE->getArg(Arg: 1));
578 return;
579 }
580 // Other tracked types: only defaulted operator= propagates origins.
581 // User-defined operator= has opaque semantics, so don't handle them now.
582 if (const auto *MD =
583 dyn_cast_or_null<CXXMethodDecl>(Val: OCE->getDirectCallee());
584 MD && MD->isDefaulted()) {
585 handleAssignment(TargetExpr: OCE, LHSExpr: OCE->getArg(Arg: 0), RHSExpr: OCE->getArg(Arg: 1));
586 return;
587 }
588 }
589
590 handleFunctionCall(Call: OCE);
591}
592
593void FactsGenerator::VisitCXXFunctionalCastExpr(
594 const CXXFunctionalCastExpr *FCE) {
595 // Check if this is a test point marker. If so, we are done with this
596 // expression.
597 if (handleTestPoint(FCE))
598 return;
599 VisitCastExpr(CE: FCE);
600}
601
602void FactsGenerator::VisitInitListExpr(const InitListExpr *ILE) {
603 if (!hasOrigins(E: ILE))
604 return;
605 // For list initialization with a single element, like `View{...}`, the
606 // origin of the list itself is the origin of its single element.
607 if (ILE->getNumInits() == 1) {
608 // A type with origins may be list-initialized from an element with none
609 // (e.g., an int). Only flow if the element carries any.
610 if (!hasOrigins(E: ILE->getInit(Init: 0)))
611 return;
612 killAndFlowOrigin(D: *ILE, S: *ILE->getInit(Init: 0));
613 }
614}
615
616void FactsGenerator::VisitCXXBindTemporaryExpr(
617 const CXXBindTemporaryExpr *BTE) {
618 killAndFlowOrigin(D: *BTE, S: *BTE->getSubExpr());
619}
620
621void FactsGenerator::VisitMaterializeTemporaryExpr(
622 const MaterializeTemporaryExpr *MTE) {
623 assert(MTE->isGLValue());
624 OriginList *MTEList = getOriginsList(E: *MTE);
625 if (!MTEList)
626 return;
627 OriginList *SubExprList = getOriginsList(E: *MTE->getSubExpr());
628 assert((!SubExprList ||
629 MTEList->getLength() == (SubExprList->getLength() + 1)) &&
630 "MTE top level origin should contain a loan to the MTE itself");
631
632 OriginList *RValMTEList = MTEList->peelOuterOrigin();
633 flow(Dst: RValMTEList, Src: SubExprList, /*Kill=*/true);
634 OriginID OuterMTEID = MTEList->getOuterOriginID();
635 if (MTE->getStorageDuration() == SD_FullExpression) {
636 // Issue a loan to MTE for the storage location represented by MTE.
637 const Loan *L = createLoan(FactMgr, MTE);
638 CurrentBlockFacts.push_back(
639 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args&: OuterMTEID));
640 }
641}
642
643void FactsGenerator::VisitLambdaExpr(const LambdaExpr *LE) {
644 for (const LambdaCapture &C : LE->captures()) {
645 if (C.capturesThis())
646 FactMgr.setThisCapturedByLambda();
647 else if (C.capturesVariable() && C.getCapturedVar()->isInitCapture()) {
648 const Expr *Init = cast<VarDecl>(Val: C.getCapturedVar())->getInit();
649 if (!Init)
650 continue;
651 if (const auto *ME = dyn_cast<MemberExpr>(Val: Init->IgnoreParenImpCasts())) {
652 if (const auto *FD = dyn_cast<FieldDecl>(Val: ME->getMemberDecl()))
653 FactMgr.addCapturedField(FD);
654 }
655 }
656 }
657
658 // The lambda gets a single merged origin that aggregates all captured
659 // pointer-like origins. Currently we only need to detect whether the lambda
660 // outlives any capture.
661 OriginList *LambdaList = getOriginsList(E: *LE);
662 if (!LambdaList)
663 return;
664 bool Kill = true;
665 for (const Expr *Init : LE->capture_inits()) {
666 if (!Init)
667 continue;
668 // The lambda body may dereference a capture to any depth.
669 handleUse(E: Init);
670 OriginList *InitList = getOriginsList(E: *Init);
671 if (!InitList)
672 continue;
673 // FIXME: Consider flowing all origin levels once lambdas support more than
674 // one origin. Currently only the outermost origin is flowed, so by-ref
675 // captures like `[&p]` (where p is string_view) miss inner-level
676 // invalidation.
677 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
678 args: LambdaList->getOuterOriginID(), args: InitList->getOuterOriginID(), args&: Kill));
679 Kill = false;
680 }
681}
682
683void FactsGenerator::VisitArraySubscriptExpr(const ArraySubscriptExpr *ASE) {
684 // Some C subscripts do not refer to addressable storage with origins, such as
685 // GNU void-pointer subscripts and vector element extraction from rvalues.
686 if (IsCMode && !ASE->isGLValue())
687 return;
688 assert(ASE->isGLValue() && "Array subscript should be a GL value");
689 OriginList *Dst = getOriginsList(E: *ASE);
690 assert(Dst && "Array subscript should have origins as it is a GL value");
691 OriginList *Src = getOriginsList(E: *ASE->getBase());
692 assert(Src && "Base of array subscript should have origins");
693 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
694 args: Dst->getOuterOriginID(), args: Src->getOuterOriginID(), /*Kill=*/args: true));
695}
696
697bool FactsGenerator::handlePlacementNew(const CXXNewExpr *NE,
698 OriginList *NewList) {
699 // Model only the standard single-argument placement new form, where the
700 // placement argument corresponds to a void* allocation-function parameter.
701 // Other placement forms, such as std::nothrow, are not modeled as providing
702 // storage for the returned pointer.
703 if (NE->getNumPlacementArgs() != 1)
704 return false;
705
706 const FunctionDecl *OperatorNew = NE->getOperatorNew();
707 if (OperatorNew->getNumParams() <= 1)
708 return false;
709
710 const auto *Arg =
711 OperatorNew->getParamDecl(i: 1)->getType()->getAs<PointerType>();
712 if (!Arg || !Arg->isVoidPointerType())
713 return false;
714
715 // Use the placement argument before the implicit conversion to void*, so
716 // inner origins are still available.
717 const Expr *PlacementArg = NE->getPlacementArg(I: 0);
718 if (const auto *ICE = dyn_cast<ImplicitCastExpr>(Val: PlacementArg);
719 ICE && ICE->getCastKind() == CK_BitCast &&
720 PlacementArg->getType()->isVoidPointerType())
721 PlacementArg = ICE->getSubExpr();
722 OriginList *PlacementList = getOriginsList(E: *PlacementArg);
723 // FIXME: General placement arguments need separate handling to overwrite
724 // the right origins.
725
726 handleAccess(E: PlacementArg);
727
728 // The pointer returned by placement new comes from the placement
729 // argument.
730 if (PlacementList)
731 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
732 args: NewList->getOuterOriginID(), args: PlacementList->getOuterOriginID(), args: true));
733 return true;
734}
735
736void FactsGenerator::VisitCXXNewExpr(const CXXNewExpr *NE) {
737 OriginList *NewList = getOriginsList(E: *NE);
738 const Expr *Init = NE->getInitializer();
739
740 bool HandledAsPlacementNew = false;
741 if (NE->getNumPlacementArgs() == 1)
742 HandledAsPlacementNew = handlePlacementNew(NE, NewList);
743
744 // Treat ordinary new and replaceable global allocation forms as heap
745 // allocations.
746 const FunctionDecl *OperatorNew = NE->getOperatorNew();
747 if (!HandledAsPlacementNew &&
748 (NE->getNumPlacementArgs() == 0 ||
749 (OperatorNew && OperatorNew->isReplaceableGlobalAllocationFunction()))) {
750 const Loan *L = createLoan(FactMgr, NE);
751 CurrentBlockFacts.push_back(
752 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: NewList->getOuterOriginID()));
753 }
754
755 NewList = NewList->peelOuterOrigin();
756
757 if (!NewList || !Init)
758 return;
759
760 // FIXME: OriginList is null for `new[]` initializers. Remove this `Init`
761 // check once array origins are supported.
762 if (OriginList *InitList = getOriginsList(E: *Init); InitList)
763 flow(Dst: NewList, Src: InitList, Kill: true);
764}
765
766// TODO: An escape fact may fit `throw` and asm better than a use.
767void FactsGenerator::VisitCXXThrowExpr(const CXXThrowExpr *TE) {
768 if (const Expr *Sub = TE->getSubExpr())
769 handleUse(E: Sub);
770}
771
772void FactsGenerator::VisitGCCAsmStmt(const GCCAsmStmt *AS) {
773 for (const Expr *Input : AS->inputs())
774 handleUse(E: Input);
775 for (unsigned I = 0, N = AS->getNumOutputs(); I != N; ++I)
776 if (AS->isOutputPlusConstraint(i: I)) // Also read.
777 handleUse(E: AS->getOutputExpr(i: I));
778 else
779 handleAccess(E: AS->getOutputExpr(i: I));
780}
781
782void FactsGenerator::VisitCXXTypeidExpr(const CXXTypeidExpr *TE) {
783 if (TE->isPotentiallyEvaluated())
784 handleAccess(E: TE->getExprOperand());
785}
786
787void FactsGenerator::VisitCXXDeleteExpr(const CXXDeleteExpr *DE) {
788 // The destructor may dereference to any depth.
789 handleUse(E: DE->getArgument());
790 OriginList *List = getOriginsList(E: *DE->getArgument());
791 CurrentBlockFacts.push_back(
792 Elt: FactMgr.createFact<InvalidateOriginFact>(args: List->getOuterOriginID(), args&: DE));
793}
794
795void FactsGenerator::VisitStmtExpr(const StmtExpr *SE) {
796 // A statement expression (`({ ...; e; })`) yields the value of its final
797 // expression `e`. Flow `e`'s origins into the statement expression's origin
798 // so a borrow `e` carries reaches the value's users.
799 const auto *CS = SE->getSubStmt();
800 if (!CS || CS->body_empty())
801 return;
802 const auto *Last = dyn_cast<Expr>(Val: CS->body_back());
803 if (!Last)
804 return;
805 if (OriginList *Dst = getOriginsList(E: *SE))
806 if (OriginList *Src = readValue(E: Last))
807 flow(Dst, Src, /*Kill=*/true);
808}
809
810bool FactsGenerator::escapesViaReturn(OriginID OID) const {
811 return llvm::any_of(Range: EscapesInCurrentBlock, P: [OID](const Fact *F) {
812 if (const auto *EF = F->getAs<ReturnEscapeFact>())
813 return EF->getEscapedOriginID() == OID;
814 return false;
815 });
816}
817
818void FactsGenerator::handleLifetimeEnds(const CFGLifetimeEnds &LifetimeEnds) {
819 const VarDecl *LifetimeEndsVD = LifetimeEnds.getVarDecl();
820 if (!LifetimeEndsVD)
821 return;
822 // Expire the origin when its variable's lifetime ends to ensure liveness
823 // doesn't persist through loop back-edges.
824 std::optional<OriginID> ExpiredOID;
825 if (OriginList *List = getOriginsList(D: *LifetimeEndsVD)) {
826 OriginID OID = List->getOuterOriginID();
827 // Skip origins that escape via return; the escape checker needs their loans
828 // to remain until the return statement is processed.
829 if (!escapesViaReturn(OID))
830 ExpiredOID = OID;
831 }
832 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<ExpireFact>(
833 args: AccessPath(LifetimeEndsVD), args: LifetimeEnds.getTriggerStmt()->getEndLoc(),
834 args&: ExpiredOID));
835}
836
837void FactsGenerator::handleFullExprCleanup(
838 const CFGFullExprCleanup &FullExprCleanup) {
839 for (const auto *MTE : FullExprCleanup.getExpiringMTEs())
840 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<ExpireFact>(
841 args: AccessPath(MTE), args: FullExprCleanup.getCleanupLoc()));
842}
843
844void FactsGenerator::handleExitBlock() {
845 bool IsDestructor = isa_and_nonnull<CXXDestructorDecl>(Val: AC.getDecl());
846 for (const Origin &O : FactMgr.getOriginMgr().getOrigins())
847 // Create FieldEscapeFacts for all field origins that remain live at exit.
848 // Fields in destructors do not escape since the object is being destroyed.
849 if (auto *FD = dyn_cast_if_present<FieldDecl>(Val: O.getDecl());
850 FD && !IsDestructor)
851 EscapesInCurrentBlock.push_back(
852 Elt: FactMgr.createFact<FieldEscapeFact>(args: O.ID, args&: FD));
853 else if (auto *VD = dyn_cast_if_present<VarDecl>(Val: O.getDecl())) {
854 // Create GlobalEscapeFacts for all origins with global-storage that
855 // remain live at exit.
856 if (VD->hasGlobalStorage()) {
857 EscapesInCurrentBlock.push_back(
858 Elt: FactMgr.createFact<GlobalEscapeFact>(args: O.ID, args&: VD));
859 }
860 }
861}
862
863void FactsGenerator::handleGSLPointerConstruction(const CXXConstructExpr *CCE) {
864 assert(isGslPointerType(CCE->getType()));
865 if (CCE->getNumArgs() != 1)
866 return;
867
868 const Expr *Arg = CCE->getArg(Arg: 0);
869 if (isGslPointerType(QT: Arg->getType())) {
870 // GSL pointer is constructed from another gsl pointer.
871 // Example:
872 // View(View v);
873 // View(const View &v);
874 OriginList *ArgList = readValue(E: Arg);
875 assert(ArgList && "GSL pointer argument should have an origin list");
876 flow(Dst: getOriginsList(E: *CCE), Src: ArgList, /*Kill=*/true);
877 } else if (Arg->getType()->isPointerType()) {
878 // GSL pointer is constructed from a raw pointer. Flow only the outermost
879 // raw pointer. Example:
880 // View(const char*);
881 // Span<int*>(const in**);
882 OriginList *ArgList = getOriginsList(E: *Arg);
883 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
884 args: getOriginsList(E: *CCE)->getOuterOriginID(), args: ArgList->getOuterOriginID(),
885 /*Kill=*/args: true));
886 } else {
887 // This could be a new borrow.
888 // TODO: Add code example here.
889 handleFunctionCall(Call: CCE, /*IsGslConstruction=*/true);
890 }
891}
892
893void FactsGenerator::handleMovedArgsInCall(const FunctionDecl *FD,
894 ArrayRef<const Expr *> Args) {
895 unsigned ImplicitObjectArgOffset = 0;
896 // Constructors are excluded because Args has no object argument for them,
897 // even though isImplicitObjectMemberFunction() is true.
898 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
899 MD && !isa<CXXConstructorDecl>(Val: FD) &&
900 MD->isImplicitObjectMemberFunction()) {
901 ImplicitObjectArgOffset = 1;
902 // std::unique_ptr::release() transfers ownership.
903 // Treat it as a move to prevent false-positive warnings when the unique_ptr
904 // destructor runs after ownership has been transferred.
905 if (isUniquePtrRelease(MD: *MD)) {
906 const Expr *UniquePtrExpr = Args[0];
907 OriginList *MovedOrigins = getOriginsList(E: *UniquePtrExpr);
908 if (MovedOrigins)
909 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<MovedOriginFact>(
910 args&: UniquePtrExpr, args: MovedOrigins->getOuterOriginID()));
911 }
912 }
913
914 // Skip implicit 'this' arg as it cannot be moved.
915 for (unsigned I = ImplicitObjectArgOffset;
916 I < Args.size() && I < FD->getNumParams() + ImplicitObjectArgOffset;
917 ++I) {
918 const ParmVarDecl *PVD = FD->getParamDecl(i: I - ImplicitObjectArgOffset);
919 // In principle, explicit object parameters can be moved, but skip marking
920 // them as moved for consistency with implicit 'this'.
921 if (PVD->isExplicitObjectParameter())
922 continue;
923 if (!PVD->getType()->isRValueReferenceType())
924 continue;
925 // Skip lifetime annotated r-value reference parameters. Lifetime annotation
926 // indicates that the parameter is borrowed (not consumed), so it should not
927 // be marked as moved even though it's an r-value reference.
928 if (PVD->hasAttr<LifetimeBoundAttr>() ||
929 PVD->hasAttr<LifetimeCaptureByAttr>())
930 continue;
931 const Expr *Arg = Args[I];
932 OriginList *MovedOrigins = getOriginsList(E: *Arg);
933 assert(MovedOrigins->getLength() >= 1 &&
934 "unexpected length for r-value reference param");
935 // Arg is being moved to this parameter. Mark the origin as moved.
936 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<MovedOriginFact>(
937 args&: Arg, args: MovedOrigins->getOuterOriginID()));
938 }
939}
940
941void FactsGenerator::handleInvalidatingCall(const Expr *Call,
942 const FunctionDecl *FD,
943 ArrayRef<const Expr *> Args) {
944 const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
945 if (!MD || !MD->isInstance())
946 return;
947
948 if (!isInvalidationMethod(MD: *MD))
949 return;
950
951 // Heuristics to turn-down false positives. Skip member field expressions for
952 // now. This is not a perfect filter and will still surface some false
953 // positives (e.g. `auto& r = s.v`).
954 if (!isa<DeclRefExpr>(Val: Args[0]->IgnoreImpCasts()))
955 return;
956
957 OriginList *ThisList = getOriginsList(E: *Args[0]);
958 if (ThisList)
959 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<InvalidateOriginFact>(
960 args: ThisList->getOuterOriginID(), args&: Call));
961}
962
963void FactsGenerator::handleDestructiveCall(const Expr *Call,
964 const FunctionDecl *FD,
965 ArrayRef<const Expr *> Args) {
966 if (!destructsFirstArg(FD: *FD))
967 return;
968 OriginList *ArgList = getOriginsList(E: *Args[0]);
969 if (ArgList)
970 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<InvalidateOriginFact>(
971 args: ArgList->getOuterOriginID(), args&: Call));
972}
973
974void FactsGenerator::handleImplicitObjectFieldUses(const Expr *Call,
975 const FunctionDecl *FD) {
976 const auto *MemberCall = dyn_cast_or_null<CXXMemberCallExpr>(Val: Call);
977 if (!MemberCall)
978 return;
979
980 if (!isa_and_present<CXXThisExpr>(
981 Val: MemberCall->getImplicitObjectArgument()->IgnoreImpCasts()))
982 return;
983
984 const auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
985 assert(MD && "Function must be a CXXMethodDecl for member calls");
986
987 const auto *ClassDecl = MD->getParent()->getDefinition();
988 if (!ClassDecl)
989 return;
990
991 const auto UseFields = [&](const CXXRecordDecl *RD) {
992 for (const auto *Field : RD->fields())
993 if (auto *FieldList = getOriginsList(D: *Field))
994 CurrentBlockFacts.push_back(
995 Elt: FactMgr.createFact<UseFact>(args&: Call, args&: FieldList));
996 };
997
998 UseFields(ClassDecl);
999
1000 ClassDecl->forallBases(BaseMatches: [&](const CXXRecordDecl *Base) {
1001 UseFields(Base);
1002 return true;
1003 });
1004}
1005
1006void FactsGenerator::handleLifetimeCaptureBy(const FunctionDecl *FD,
1007 ArrayRef<const Expr *> Args) {
1008 if (Args.empty())
1009 return;
1010 // FIXME: Add support for capture_by on constructors.
1011 if (isa<CXXConstructorDecl>(Val: FD))
1012 return;
1013 const auto *Method = dyn_cast<CXXMethodDecl>(Val: FD);
1014 bool HasImplicitObjectArg = Method &&
1015 Method->isImplicitObjectMemberFunction() &&
1016 !isa<CXXConstructorDecl>(Val: FD);
1017 auto getParamDeclAt =
1018 [FD, HasImplicitObjectArg](unsigned I) -> const ParmVarDecl * {
1019 if (HasImplicitObjectArg) {
1020 // FIXME: Add support for I == 0 i.e. capture_by on function declarations
1021 if (I > 0 && I - 1 < FD->getNumParams())
1022 return FD->getParamDecl(i: I - 1);
1023 } else {
1024 if (I < FD->getNumParams())
1025 return FD->getParamDecl(i: I);
1026 }
1027 return nullptr;
1028 };
1029 for (unsigned I = 0; I < Args.size(); ++I) {
1030 const ParmVarDecl *PVD = getParamDeclAt(I);
1031 if (!PVD)
1032 continue;
1033 const auto *Attr = PVD->getAttr<LifetimeCaptureByAttr>();
1034 if (!Attr)
1035 continue;
1036 OriginList *CapturedOriginList = getOriginsList(E: *Args[I]);
1037 if (!CapturedOriginList)
1038 continue;
1039 // For references to pointer-like types, peel the outer origin (the pointer
1040 // object itself) so that we capture the underlying data (the inner origin).
1041 if (QualType ParamType = PVD->getType();
1042 (ParamType->isReferenceType() &&
1043 isPointerLikeType(QT: ParamType->getPointeeType())) &&
1044 CapturedOriginList->getLength() > 1)
1045 CapturedOriginList = CapturedOriginList->peelOuterOrigin();
1046 for (int CapturingArgIdx : Attr->params()) {
1047 // FIXME: Add support for capturing to Global/unknown.
1048 if (CapturingArgIdx == LifetimeCaptureByAttr::Global ||
1049 CapturingArgIdx == LifetimeCaptureByAttr::Unknown ||
1050 CapturingArgIdx == LifetimeCaptureByAttr::Invalid)
1051 continue;
1052 // FIXME: Diagnose bad CapturingArgIdx.
1053 if (CapturingArgIdx != LifetimeCaptureByAttr::This &&
1054 (CapturingArgIdx < 0 ||
1055 static_cast<size_t>(CapturingArgIdx) >= Args.size()))
1056 continue;
1057 const Expr *CapturedByArg = Args[CapturingArgIdx];
1058 assert(CapturedByArg && "Capturer expression must be valid");
1059
1060 OriginList *Dest = readValue(E: CapturedByArg);
1061 if (!Dest)
1062 continue;
1063 // KillDest=false because we cannot know if previous captures are being
1064 // replaced or accumulated. Multiple successive captures into the same
1065 // destination must all be tracked, so captured lifetimes are always
1066 // merged.
1067 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
1068 args: Dest->getOuterOriginID(), args: CapturedOriginList->getOuterOriginID(),
1069 /*KillDest=*/args: false));
1070 }
1071 }
1072}
1073
1074void FactsGenerator::handleFunctionCall(const Expr *Call,
1075 bool IsGslConstruction) {
1076 FunctionCallInfo CallInfo(Call);
1077 llvm::ArrayRef<const Expr *> Args = CallInfo.Args;
1078 // The callee may dereference any argument to any depth.
1079 for (const Expr *Arg : Args)
1080 handleUse(E: Arg);
1081 if (!CallInfo.FD)
1082 return;
1083 OriginList *CallList = getOriginsList(E: *Call);
1084 // Ignore functions returning values with no origin.
1085 const FunctionDecl *FD = getDeclWithMergedLifetimeBoundAttrs(FD: CallInfo.FD);
1086 if (!FD)
1087 return;
1088 handleInvalidatingCall(Call, FD, Args);
1089 handleDestructiveCall(Call, FD, Args);
1090 handleMovedArgsInCall(FD, Args);
1091 handleImplicitObjectFieldUses(Call, FD);
1092 handleLifetimeCaptureBy(FD, Args);
1093 if (!CallList)
1094 return;
1095 if (isStdReferenceCast(FD)) {
1096 assert(Args.size() == 1 &&
1097 "std reference cast builtins take exactly one argument");
1098 // std reference-cast functions like std::move return a result that refers
1099 // to the same object as the argument, so propagate the full origins.
1100 flow(Dst: CallList, Src: getOriginsList(E: *Args[0]), /*Kill=*/true);
1101 return;
1102 }
1103 auto shouldTrackPointerImplicitObjectArg = [FD, &Args](unsigned I) -> bool {
1104 const auto *Method = dyn_cast<CXXMethodDecl>(Val: FD);
1105 if (!Method || !Method->isInstance())
1106 return false;
1107 return I == 0 &&
1108 isGslPointerType(QT: Method->getFunctionObjectParameterType()) &&
1109 shouldTrackImplicitObjectArg(ImplicitObjectArgument: *Args[0], Callee: Method,
1110 /*RunningUnderLifetimeSafety=*/true);
1111 };
1112 if (Args.empty())
1113 return;
1114 bool KillSrc = true;
1115 for (unsigned I = 0; I < Args.size(); ++I) {
1116 OriginList *ArgList = getOriginsList(E: *Args[I]);
1117 if (!ArgList)
1118 continue;
1119 bool ShouldTrackArg = getTrackedArgInfo(FD, Args, I).has_value();
1120 if (IsGslConstruction) {
1121 // TODO: document with code example.
1122 // std::string_view(const std::string_view& from)
1123 if (isGslPointerType(QT: Args[I]->getType())) {
1124 assert(!Args[I]->isGLValue() || ArgList->getLength() >= 2);
1125 ArgList = readValue(E: Args[I]);
1126 }
1127 if (isGslOwnerType(QT: Args[I]->getType())) {
1128 // The constructed gsl::Pointer borrows from the Owner's storage, not
1129 // from what the Owner itself borrows, so only the outermost origin is
1130 // needed.
1131 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
1132 args: CallList->getOuterOriginID(), args: ArgList->getOuterOriginID(),
1133 args&: KillSrc));
1134 KillSrc = false;
1135 } else if (ShouldTrackArg) {
1136 // Only flow the outer origin here. For lifetimebound args in
1137 // gsl::Pointer construction, we do not have enough information to
1138 // safely match inner origins, so the source and
1139 // destination origin lists may have different lengths.
1140 // FIXME: Handle origin-shape mismatches gracefully so we can also flow
1141 // inner origins.
1142 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
1143 args: CallList->getOuterOriginID(), args: ArgList->getOuterOriginID(),
1144 args&: KillSrc));
1145 KillSrc = false;
1146 }
1147 } else if (shouldTrackPointerImplicitObjectArg(I)) {
1148 assert(ArgList->getLength() >= 2 &&
1149 "Object arg of pointer type should have at least two origins");
1150 // See through the GSLPointer reference to see the pointer's value.
1151 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
1152 args: CallList->getOuterOriginID(),
1153 args: ArgList->peelOuterOrigin()->getOuterOriginID(), args&: KillSrc));
1154 KillSrc = false;
1155 } else if (ShouldTrackArg) {
1156 // Lifetimebound on a non-GSL-ctor function means the returned
1157 // pointer/reference itself must not outlive the arguments. This
1158 // only constrains the top-level origin.
1159 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<OriginFlowFact>(
1160 args: CallList->getOuterOriginID(), args: ArgList->getOuterOriginID(), args&: KillSrc));
1161 KillSrc = false;
1162 }
1163 }
1164}
1165
1166/// Checks if the expression is a `void("__lifetime_test_point_...")` cast.
1167/// If so, creates a `TestPointFact` and returns true.
1168bool FactsGenerator::handleTestPoint(const CXXFunctionalCastExpr *FCE) {
1169 if (!FCE->getType()->isVoidType())
1170 return false;
1171
1172 const auto *SubExpr = FCE->getSubExpr()->IgnoreParenImpCasts();
1173 if (const auto *SL = dyn_cast<StringLiteral>(Val: SubExpr)) {
1174 llvm::StringRef LiteralValue = SL->getString();
1175 const std::string Prefix = "__lifetime_test_point_";
1176
1177 if (LiteralValue.starts_with(Prefix)) {
1178 StringRef Annotation = LiteralValue.drop_front(N: Prefix.length());
1179 CurrentBlockFacts.push_back(
1180 Elt: FactMgr.createFact<TestPointFact>(args&: Annotation));
1181 return true;
1182 }
1183 }
1184 return false;
1185}
1186
1187bool FactsGenerator::namesDeclStorage(const OriginList *List) const {
1188 return FactMgr.getOriginMgr()
1189 .getOrigin(ID: List->getOuterOriginID())
1190 .NamesDeclStorage;
1191}
1192
1193void FactsGenerator::handleAccess(const Expr *E) {
1194 OriginList *List = getOriginsList(E: *E);
1195 if (!List || namesDeclStorage(List))
1196 return;
1197 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<UseFact>(
1198 args&: E,
1199 args: FactMgr.getOriginMgr().createSingleOriginList(OID: List->getOuterOriginID())));
1200}
1201
1202void FactsGenerator::handleUse(const Expr *E) {
1203 OriginList *List = getOriginsList(E: *E);
1204 if (List && namesDeclStorage(List))
1205 List = List->peelOuterOrigin();
1206 if (List)
1207 CurrentBlockFacts.push_back(Elt: FactMgr.createFact<UseFact>(args&: E, args&: List));
1208}
1209
1210// Issues a placeholder loan (this->field) for each origin-carrying field of the
1211// class and its bases. It represents the storage the field refers to, as
1212// opposed to the field itself (covered by $this).
1213void FactsGenerator::issueFieldPlaceholderLoans(
1214 const CXXMethodDecl *MD, llvm::SmallVectorImpl<Fact *> &Facts) {
1215 const CXXRecordDecl *ClassDecl = MD->getParent()->getDefinition();
1216 if (!ClassDecl)
1217 return;
1218 auto IssueForRecord = [&](const CXXRecordDecl *RD) {
1219 for (const FieldDecl *Field : RD->fields()) {
1220 // Skip private fields of bases as they cannot be named in MD.
1221 if (RD != ClassDecl && Field->getAccess() == AS_private)
1222 continue;
1223 OriginList *FieldList = getOriginsList(D: *Field);
1224 if (!FieldList)
1225 continue;
1226 const Loan *L = FactMgr.getLoanMgr().createPlaceholderLoan(FD: Field);
1227 Facts.push_back(Elt: FactMgr.createFact<IssueFact>(
1228 args: L->getID(), args: FieldList->getOuterOriginID()));
1229 }
1230 return true;
1231 };
1232 IssueForRecord(ClassDecl);
1233 ClassDecl->forallBases(BaseMatches: IssueForRecord);
1234}
1235
1236// Creates an IssueFact for a new placeholder loan for each pointer or reference
1237// parameter, the implicit 'this', and (if enabled) each origin-carrying field
1238// at the function's entry.
1239llvm::SmallVector<Fact *> FactsGenerator::issuePlaceholderLoans() {
1240 const auto *FD = dyn_cast<FunctionDecl>(Val: AC.getDecl());
1241 if (!FD)
1242 return {};
1243
1244 llvm::SmallVector<Fact *> PlaceholderLoanFacts;
1245 if (auto ThisOrigins = FactMgr.getOriginMgr().getThisOrigins()) {
1246 OriginList *List = *ThisOrigins;
1247 const auto *MD = cast<CXXMethodDecl>(Val: FD);
1248 const Loan *L = FactMgr.getLoanMgr().createPlaceholderLoan(MD);
1249 PlaceholderLoanFacts.push_back(
1250 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
1251 if (LSOpts.CheckFieldOriginEscape && !isa<CXXConstructorDecl>(Val: MD))
1252 issueFieldPlaceholderLoans(MD, Facts&: PlaceholderLoanFacts);
1253 }
1254 for (const ParmVarDecl *PVD : FD->parameters()) {
1255 OriginList *List = getOriginsList(D: *PVD);
1256 if (!List)
1257 continue;
1258 const Loan *L = FactMgr.getLoanMgr().createPlaceholderLoan(PVD);
1259 PlaceholderLoanFacts.push_back(
1260 Elt: FactMgr.createFact<IssueFact>(args: L->getID(), args: List->getOuterOriginID()));
1261 }
1262 return PlaceholderLoanFacts;
1263}
1264
1265} // namespace clang::lifetimes::internal
1266