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