1//===- Checker.cpp - C++ Lifetime Safety Checker ----------------*- 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// This file implements the LifetimeChecker, which detects use-after-free
10// errors by checking if live origins hold loans that have expired.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Analysis/Analyses/LifetimeSafety/Checker.h"
15#include "clang/AST/Decl.h"
16#include "clang/AST/Expr.h"
17#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
18#include "clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h"
19#include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h"
20#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
21#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"
22#include "clang/Analysis/Analyses/PostOrderCFGView.h"
23#include "clang/Analysis/AnalysisDeclContext.h"
24#include "clang/Basic/SourceLocation.h"
25#include "clang/Basic/SourceManager.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/TimeProfiler.h"
29
30namespace clang::lifetimes::internal {
31
32static bool causingFactDominatesExpiry(LivenessKind K) {
33 switch (K) {
34 case LivenessKind::Must:
35 return true;
36 case LivenessKind::Maybe:
37 case LivenessKind::Dead:
38 return false;
39 }
40 llvm_unreachable("unknown liveness kind");
41}
42
43namespace {
44
45/// Struct to store the complete context for a potential lifetime violation.
46struct PendingWarning {
47 SourceLocation ExpiryLoc; // Where the loan expired.
48 llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> CausingFact;
49 const Expr *MovedExpr;
50 const Expr *InvalidatedByExpr;
51 bool CausingFactDominatesExpiry;
52};
53
54using AnnotationTarget =
55 llvm::PointerUnion<const ParmVarDecl *, const CXXMethodDecl *>;
56using EscapingTarget =
57 llvm::PointerUnion<const Expr *, const FieldDecl *, const VarDecl *>;
58
59class LifetimeChecker {
60private:
61 llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap;
62 llvm::DenseMap<AnnotationTarget, const Expr *> AnnotationWarningsMap;
63 llvm::DenseMap<const ParmVarDecl *, EscapingTarget> NoescapeWarningsMap;
64 const LoanPropagationAnalysis &LoanPropagation;
65 const MovedLoansAnalysis &MovedLoans;
66 const LiveOriginsAnalysis &LiveOrigins;
67 FactManager &FactMgr;
68 LifetimeSafetySemaHelper *SemaHelper;
69 ASTContext &AST;
70
71 static SourceLocation
72 GetFactLoc(llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> F) {
73 if (const auto *UF = F.dyn_cast<const UseFact *>())
74 return UF->getUseExpr()->getExprLoc();
75 if (const auto *OEF = F.dyn_cast<const OriginEscapesFact *>()) {
76 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
77 return ReturnEsc->getReturnExpr()->getExprLoc();
78 if (auto *FieldEsc = dyn_cast<FieldEscapeFact>(Val: OEF))
79 return FieldEsc->getFieldDecl()->getLocation();
80 }
81 llvm_unreachable("unhandled causing fact in PointerUnion");
82 }
83
84public:
85 LifetimeChecker(const LoanPropagationAnalysis &LoanPropagation,
86 const MovedLoansAnalysis &MovedLoans,
87 const LiveOriginsAnalysis &LiveOrigins, FactManager &FM,
88 AnalysisDeclContext &ADC,
89 LifetimeSafetySemaHelper *SemaHelper)
90 : LoanPropagation(LoanPropagation), MovedLoans(MovedLoans),
91 LiveOrigins(LiveOrigins), FactMgr(FM), SemaHelper(SemaHelper),
92 AST(ADC.getASTContext()) {
93 for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>())
94 for (const Fact *F : FactMgr.getFacts(B))
95 if (const auto *EF = F->getAs<ExpireFact>())
96 checkExpiry(EF);
97 else if (const auto *IOF = F->getAs<InvalidateOriginFact>())
98 checkInvalidation(IOF);
99 else if (const auto *OEF = F->getAs<OriginEscapesFact>())
100 checkAnnotations(OEF);
101 issuePendingWarnings();
102 suggestAnnotations();
103 reportNoescapeViolations();
104 // Annotation inference is currently guarded by a frontend flag. In the
105 // future, this might be replaced by a design that differentiates between
106 // explicit and inferred findings with separate warning groups.
107 if (AST.getLangOpts().EnableLifetimeSafetyInference)
108 inferAnnotations();
109 }
110
111 /// Checks if an escaping origin holds a placeholder loan, indicating a
112 /// missing [[clang::lifetimebound]] annotation or a violation of
113 /// [[clang::noescape]].
114 void checkAnnotations(const OriginEscapesFact *OEF) {
115 OriginID EscapedOID = OEF->getEscapedOriginID();
116 LoanSet EscapedLoans = LoanPropagation.getLoans(OID: EscapedOID, P: OEF);
117 auto CheckParam = [&](const ParmVarDecl *PVD) {
118 // NoEscape param should not escape.
119 if (PVD->hasAttr<NoEscapeAttr>()) {
120 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
121 NoescapeWarningsMap.try_emplace(Key: PVD, Args: ReturnEsc->getReturnExpr());
122 if (auto *FieldEsc = dyn_cast<FieldEscapeFact>(Val: OEF))
123 NoescapeWarningsMap.try_emplace(Key: PVD, Args: FieldEsc->getFieldDecl());
124 if (auto *GlobalEsc = dyn_cast<GlobalEscapeFact>(Val: OEF))
125 NoescapeWarningsMap.try_emplace(Key: PVD, Args: GlobalEsc->getGlobal());
126 return;
127 }
128 // Suggest lifetimebound for parameter escaping through return.
129 if (!PVD->hasAttr<LifetimeBoundAttr>())
130 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
131 AnnotationWarningsMap.try_emplace(Key: PVD, Args: ReturnEsc->getReturnExpr());
132 // TODO: Suggest lifetime_capture_by(this) for parameter escaping to a
133 // field!
134 };
135 auto CheckImplicitThis = [&](const CXXMethodDecl *MD) {
136 if (!implicitObjectParamIsLifetimeBound(FD: MD))
137 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
138 AnnotationWarningsMap.try_emplace(Key: MD, Args: ReturnEsc->getReturnExpr());
139 };
140 for (LoanID LID : EscapedLoans) {
141 const Loan *L = FactMgr.getLoanMgr().getLoan(ID: LID);
142 const auto *PL = dyn_cast<PlaceholderLoan>(Val: L);
143 if (!PL)
144 continue;
145 if (const auto *PVD = PL->getParmVarDecl())
146 CheckParam(PVD);
147 else if (const auto *MD = PL->getMethodDecl())
148 CheckImplicitThis(MD);
149 }
150 }
151
152 /// Checks for use-after-free & use-after-return errors when a loan expires.
153 ///
154 /// This method examines all live origins at the expiry point and determines
155 /// if any of them hold the expiring loan. If so, it creates a pending
156 /// warning.
157 ///
158 /// Note: This implementation considers only the confidence of origin
159 /// liveness. Future enhancements could also consider the confidence of loan
160 /// propagation (e.g., a loan may only be held on some execution paths).
161 void checkExpiry(const ExpireFact *EF) {
162 LoanID ExpiredLoan = EF->getLoanID();
163 const Expr *MovedExpr = nullptr;
164 if (auto *ME = MovedLoans.getMovedLoans(P: EF).lookup(K: ExpiredLoan))
165 MovedExpr = *ME;
166
167 LivenessMap Origins = LiveOrigins.getLiveOriginsAt(P: EF);
168 bool CurDomination = false;
169 // The UseFact or OriginEscapesFact most indicative of a lifetime error,
170 // prioritized by earlier source location.
171 llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> CausingFact =
172 nullptr;
173
174 for (auto &[OID, LiveInfo] : Origins) {
175 LoanSet HeldLoans = LoanPropagation.getLoans(OID, P: EF);
176 if (!HeldLoans.contains(V: ExpiredLoan))
177 continue;
178 // Loan is defaulted.
179
180 if (!CurDomination || causingFactDominatesExpiry(K: LiveInfo.Kind))
181 CausingFact = LiveInfo.CausingFact;
182 }
183 if (!CausingFact)
184 return;
185
186 bool LastDomination =
187 FinalWarningsMap.lookup(Val: ExpiredLoan).CausingFactDominatesExpiry;
188 if (LastDomination)
189 return;
190 FinalWarningsMap[ExpiredLoan] = {
191 /*ExpiryLoc=*/EF->getExpiryLoc(),
192 /*CausingFact=*/CausingFact,
193 /*MovedExpr=*/MovedExpr,
194 /*InvalidatedByExpr=*/nullptr,
195 /*CausingFactDominatesExpiry=*/CurDomination};
196 }
197
198 /// Checks for use-after-invalidation errors when a container is modified.
199 ///
200 /// This method identifies origins that are live at the point of invalidation
201 /// and checks if they hold loans that are invalidated by the operation
202 /// (e.g., iterators into a vector that is being pushed to).
203 void checkInvalidation(const InvalidateOriginFact *IOF) {
204 OriginID InvalidatedOrigin = IOF->getInvalidatedOrigin();
205 /// Get loans directly pointing to the invalidated container
206 LoanSet DirectlyInvalidatedLoans =
207 LoanPropagation.getLoans(OID: InvalidatedOrigin, P: IOF);
208 auto IsInvalidated = [&](const Loan *L) {
209 auto *PathL = dyn_cast<PathLoan>(Val: L);
210 auto *PlaceholderL = dyn_cast<PlaceholderLoan>(Val: L);
211 for (LoanID InvalidID : DirectlyInvalidatedLoans) {
212 const Loan *L = FactMgr.getLoanMgr().getLoan(ID: InvalidID);
213 auto *InvalidPathL = dyn_cast<PathLoan>(Val: L);
214 auto *InvalidPlaceholderL = dyn_cast<PlaceholderLoan>(Val: L);
215 if (PathL && InvalidPathL &&
216 PathL->getAccessPath() == InvalidPathL->getAccessPath())
217 return true;
218 if (PlaceholderL && InvalidPlaceholderL &&
219 PlaceholderL->getParmVarDecl() ==
220 InvalidPlaceholderL->getParmVarDecl())
221 return true;
222 }
223 return false;
224 };
225 // For each live origin, check if it holds an invalidated loan and report.
226 LivenessMap Origins = LiveOrigins.getLiveOriginsAt(P: IOF);
227 for (auto &[OID, LiveInfo] : Origins) {
228 LoanSet HeldLoans = LoanPropagation.getLoans(OID, P: IOF);
229 for (LoanID LiveLoanID : HeldLoans)
230 if (IsInvalidated(FactMgr.getLoanMgr().getLoan(ID: LiveLoanID))) {
231 bool CurDomination = causingFactDominatesExpiry(K: LiveInfo.Kind);
232 bool LastDomination =
233 FinalWarningsMap.lookup(Val: LiveLoanID).CausingFactDominatesExpiry;
234 if (!LastDomination) {
235 FinalWarningsMap[LiveLoanID] = {
236 /*ExpiryLoc=*/{},
237 /*CausingFact=*/LiveInfo.CausingFact,
238 /*MovedExpr=*/nullptr,
239 /*InvalidatedByExpr=*/IOF->getInvalidationExpr(),
240 /*CausingFactDominatesExpiry=*/CurDomination};
241 }
242 }
243 }
244 }
245
246 void issuePendingWarnings() {
247 if (!SemaHelper)
248 return;
249 for (const auto &[LID, Warning] : FinalWarningsMap) {
250 const Loan *L = FactMgr.getLoanMgr().getLoan(ID: LID);
251
252 const Expr *IssueExpr = nullptr;
253 if (const auto *BL = dyn_cast<PathLoan>(Val: L))
254 IssueExpr = BL->getIssueExpr();
255 const ParmVarDecl *InvalidatedPVD = nullptr;
256 if (const auto *PL = dyn_cast<PlaceholderLoan>(Val: L))
257 InvalidatedPVD = PL->getParmVarDecl();
258 llvm::PointerUnion<const UseFact *, const OriginEscapesFact *>
259 CausingFact = Warning.CausingFact;
260 const Expr *MovedExpr = Warning.MovedExpr;
261 SourceLocation ExpiryLoc = Warning.ExpiryLoc;
262
263 if (const auto *UF = CausingFact.dyn_cast<const UseFact *>()) {
264 if (Warning.InvalidatedByExpr) {
265 if (IssueExpr)
266 SemaHelper->reportUseAfterInvalidation(IssueExpr, UseExpr: UF->getUseExpr(),
267 InvalidationExpr: Warning.InvalidatedByExpr);
268 if (InvalidatedPVD)
269 SemaHelper->reportUseAfterInvalidation(
270 PVD: InvalidatedPVD, UseExpr: UF->getUseExpr(), InvalidationExpr: Warning.InvalidatedByExpr);
271
272 } else
273 SemaHelper->reportUseAfterFree(IssueExpr, UseExpr: UF->getUseExpr(), MovedExpr,
274 FreeLoc: ExpiryLoc);
275 } else if (const auto *OEF =
276 CausingFact.dyn_cast<const OriginEscapesFact *>()) {
277 if (const auto *RetEscape = dyn_cast<ReturnEscapeFact>(Val: OEF))
278 SemaHelper->reportUseAfterReturn(
279 IssueExpr, ReturnExpr: RetEscape->getReturnExpr(), MovedExpr, ExpiryLoc);
280 else if (const auto *FieldEscape = dyn_cast<FieldEscapeFact>(Val: OEF))
281 SemaHelper->reportDanglingField(
282 IssueExpr, Field: FieldEscape->getFieldDecl(), MovedExpr, ExpiryLoc);
283 else if (const auto *GlobalEscape = dyn_cast<GlobalEscapeFact>(Val: OEF))
284 SemaHelper->reportDanglingGlobal(IssueExpr, DanglingGlobal: GlobalEscape->getGlobal(),
285 MovedExpr, ExpiryLoc);
286 else
287 llvm_unreachable("Unhandled OriginEscapesFact type");
288 } else
289 llvm_unreachable("Unhandled CausingFact type");
290 }
291 }
292
293 /// Returns the declaration of a function that is visible across translation
294 /// units, if such a declaration exists and is different from the definition.
295 static const FunctionDecl *getCrossTUDecl(const FunctionDecl &FD,
296 SourceManager &SM) {
297 if (!FD.isExternallyVisible())
298 return nullptr;
299 const FileID DefinitionFile = SM.getFileID(SpellingLoc: FD.getLocation());
300 for (const FunctionDecl *Redecl : FD.redecls())
301 if (SM.getFileID(SpellingLoc: Redecl->getLocation()) != DefinitionFile)
302 return Redecl;
303
304 return nullptr;
305 }
306
307 static const FunctionDecl *getCrossTUDecl(const ParmVarDecl &PVD,
308 SourceManager &SM) {
309 if (const auto *FD = dyn_cast<FunctionDecl>(Val: PVD.getDeclContext()))
310 return getCrossTUDecl(FD: *FD, SM);
311 return nullptr;
312 }
313
314 static void suggestWithScopeForParmVar(LifetimeSafetySemaHelper *SemaHelper,
315 const ParmVarDecl *PVD,
316 SourceManager &SM,
317 const Expr *EscapeExpr) {
318 if (const FunctionDecl *CrossTUDecl = getCrossTUDecl(PVD: *PVD, SM))
319 SemaHelper->suggestLifetimeboundToParmVar(
320 Scope: SuggestionScope::CrossTU,
321 ParmToAnnotate: CrossTUDecl->getParamDecl(i: PVD->getFunctionScopeIndex()), EscapeExpr);
322 else
323 SemaHelper->suggestLifetimeboundToParmVar(Scope: SuggestionScope::IntraTU, ParmToAnnotate: PVD,
324 EscapeExpr);
325 }
326
327 static void
328 suggestWithScopeForImplicitThis(LifetimeSafetySemaHelper *SemaHelper,
329 const CXXMethodDecl *MD, SourceManager &SM,
330 const Expr *EscapeExpr) {
331 if (const FunctionDecl *CrossTUDecl = getCrossTUDecl(FD: *MD, SM))
332 SemaHelper->suggestLifetimeboundToImplicitThis(
333 Scope: SuggestionScope::CrossTU, MD: cast<CXXMethodDecl>(Val: CrossTUDecl),
334 EscapeExpr);
335 else
336 SemaHelper->suggestLifetimeboundToImplicitThis(Scope: SuggestionScope::IntraTU,
337 MD, EscapeExpr);
338 }
339
340 void suggestAnnotations() {
341 if (!SemaHelper)
342 return;
343 SourceManager &SM = AST.getSourceManager();
344 for (auto [Target, EscapeExpr] : AnnotationWarningsMap) {
345 if (const auto *PVD = Target.dyn_cast<const ParmVarDecl *>())
346 suggestWithScopeForParmVar(SemaHelper, PVD, SM, EscapeExpr);
347 else if (const auto *MD = Target.dyn_cast<const CXXMethodDecl *>())
348 suggestWithScopeForImplicitThis(SemaHelper, MD, SM, EscapeExpr);
349 }
350 }
351
352 void reportNoescapeViolations() {
353 for (auto [PVD, EscapeTarget] : NoescapeWarningsMap) {
354 if (const auto *E = EscapeTarget.dyn_cast<const Expr *>())
355 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeExpr: E);
356 else if (const auto *FD = EscapeTarget.dyn_cast<const FieldDecl *>())
357 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeField: FD);
358 else if (const auto *G = EscapeTarget.dyn_cast<const VarDecl *>())
359 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeGlobal: G);
360 else
361 llvm_unreachable("Unhandled EscapingTarget type");
362 }
363 }
364
365 void inferAnnotations() {
366 for (auto [Target, EscapeExpr] : AnnotationWarningsMap) {
367 if (const auto *MD = Target.dyn_cast<const CXXMethodDecl *>()) {
368 if (!implicitObjectParamIsLifetimeBound(FD: MD))
369 SemaHelper->addLifetimeBoundToImplicitThis(MD: cast<CXXMethodDecl>(Val: MD));
370 } else if (const auto *PVD = Target.dyn_cast<const ParmVarDecl *>()) {
371 const auto *FD = dyn_cast<FunctionDecl>(Val: PVD->getDeclContext());
372 if (!FD)
373 continue;
374 // Propagates inferred attributes via the most recent declaration to
375 // ensure visibility for callers in post-order analysis.
376 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
377 ParmVarDecl *InferredPVD = const_cast<ParmVarDecl *>(
378 FD->getParamDecl(i: PVD->getFunctionScopeIndex()));
379 if (!InferredPVD->hasAttr<LifetimeBoundAttr>())
380 InferredPVD->addAttr(
381 A: LifetimeBoundAttr::CreateImplicit(Ctx&: AST, Range: PVD->getLocation()));
382 }
383 }
384 }
385};
386} // namespace
387
388void runLifetimeChecker(const LoanPropagationAnalysis &LP,
389 const MovedLoansAnalysis &MovedLoans,
390 const LiveOriginsAnalysis &LO, FactManager &FactMgr,
391 AnalysisDeclContext &ADC,
392 LifetimeSafetySemaHelper *SemaHelper) {
393 llvm::TimeTraceScope TimeProfile("LifetimeChecker");
394 LifetimeChecker Checker(LP, MovedLoans, LO, FactMgr, ADC, SemaHelper);
395}
396
397} // namespace clang::lifetimes::internal
398