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