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