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