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