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