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 AccessPath &AP = L->getAccessPath();
143 if (const auto *PVD = AP.getAsPlaceholderParam())
144 CheckParam(PVD);
145 else if (const auto *MD = AP.getAsPlaceholderThis())
146 CheckImplicitThis(MD);
147 }
148 }
149
150 /// Checks for use-after-free & use-after-return errors when an access path
151 /// expires (e.g., a variable goes out of scope).
152 ///
153 /// When a path expires, all loans having this path expires.
154 /// This method examines all live origins and reports warnings for loans they
155 /// hold that are prefixed by the expired path.
156 void checkExpiry(const ExpireFact *EF) {
157 const AccessPath &ExpiredPath = EF->getAccessPath();
158 LivenessMap Origins = LiveOrigins.getLiveOriginsAt(P: EF);
159 for (auto &[OID, LiveInfo] : Origins) {
160 LoanSet HeldLoans = LoanPropagation.getLoans(OID, P: EF);
161 for (LoanID HeldLoanID : HeldLoans) {
162 const Loan *HeldLoan = FactMgr.getLoanMgr().getLoan(ID: HeldLoanID);
163 if (ExpiredPath != HeldLoan->getAccessPath())
164 continue;
165 // HeldLoan is expired because its AccessPath is expired.
166 PendingWarning &CurWarning = FinalWarningsMap[HeldLoan->getID()];
167 const Expr *MovedExpr = nullptr;
168 if (auto *ME = MovedLoans.getMovedLoans(P: EF).lookup(K: HeldLoanID))
169 MovedExpr = *ME;
170 // Skip if we already have a dominating causing fact.
171 if (CurWarning.CausingFactDominatesExpiry)
172 continue;
173 if (causingFactDominatesExpiry(K: LiveInfo.Kind))
174 CurWarning.CausingFactDominatesExpiry = true;
175 CurWarning.CausingFact = LiveInfo.CausingFact;
176 CurWarning.ExpiryLoc = EF->getExpiryLoc();
177 CurWarning.MovedExpr = MovedExpr;
178 CurWarning.InvalidatedByExpr = nullptr;
179 }
180 }
181 }
182
183 /// Checks for use-after-invalidation errors when a container is modified.
184 ///
185 /// This method identifies origins that are live at the point of invalidation
186 /// and checks if they hold loans that are invalidated by the operation
187 /// (e.g., iterators into a vector that is being pushed to).
188 void checkInvalidation(const InvalidateOriginFact *IOF) {
189 OriginID InvalidatedOrigin = IOF->getInvalidatedOrigin();
190 /// Get loans directly pointing to the invalidated container
191 LoanSet DirectlyInvalidatedLoans =
192 LoanPropagation.getLoans(OID: InvalidatedOrigin, P: IOF);
193 auto IsInvalidated = [&](const Loan *L) {
194 for (LoanID InvalidID : DirectlyInvalidatedLoans) {
195 const Loan *InvalidL = FactMgr.getLoanMgr().getLoan(ID: InvalidID);
196 if (InvalidL->getAccessPath() == L->getAccessPath())
197 return true;
198 }
199 return false;
200 };
201 // For each live origin, check if it holds an invalidated loan and report.
202 LivenessMap Origins = LiveOrigins.getLiveOriginsAt(P: IOF);
203 for (auto &[OID, LiveInfo] : Origins) {
204 LoanSet HeldLoans = LoanPropagation.getLoans(OID, P: IOF);
205 for (LoanID LiveLoanID : HeldLoans)
206 if (IsInvalidated(FactMgr.getLoanMgr().getLoan(ID: LiveLoanID))) {
207 bool CurDomination = causingFactDominatesExpiry(K: LiveInfo.Kind);
208 bool LastDomination =
209 FinalWarningsMap.lookup(Val: LiveLoanID).CausingFactDominatesExpiry;
210 if (!LastDomination) {
211 FinalWarningsMap[LiveLoanID] = {
212 /*ExpiryLoc=*/{},
213 /*CausingFact=*/LiveInfo.CausingFact,
214 /*MovedExpr=*/nullptr,
215 /*InvalidatedByExpr=*/IOF->getInvalidationExpr(),
216 /*CausingFactDominatesExpiry=*/CurDomination};
217 }
218 }
219 }
220 }
221
222 void issuePendingWarnings() {
223 if (!SemaHelper)
224 return;
225 for (const auto &[LID, Warning] : FinalWarningsMap) {
226 const Loan *L = FactMgr.getLoanMgr().getLoan(ID: LID);
227 const Expr *IssueExpr = L->getIssuingExpr();
228 llvm::PointerUnion<const UseFact *, const OriginEscapesFact *>
229 CausingFact = Warning.CausingFact;
230 const ParmVarDecl *InvalidatedPVD =
231 L->getAccessPath().getAsPlaceholderParam();
232 const Expr *MovedExpr = Warning.MovedExpr;
233 SourceLocation ExpiryLoc = Warning.ExpiryLoc;
234
235 if (const auto *UF = CausingFact.dyn_cast<const UseFact *>()) {
236 if (Warning.InvalidatedByExpr) {
237 if (IssueExpr)
238 // Use-after-invalidation of an object on stack.
239 SemaHelper->reportUseAfterInvalidation(IssueExpr, UseExpr: UF->getUseExpr(),
240 InvalidationExpr: Warning.InvalidatedByExpr);
241 else if (InvalidatedPVD)
242 // Use-after-invalidation of a parameter.
243 SemaHelper->reportUseAfterInvalidation(
244 PVD: InvalidatedPVD, UseExpr: UF->getUseExpr(), InvalidationExpr: Warning.InvalidatedByExpr);
245
246 } else
247 // Scope-based expiry (use-after-scope).
248 SemaHelper->reportUseAfterFree(IssueExpr, UseExpr: UF->getUseExpr(), MovedExpr,
249 FreeLoc: ExpiryLoc);
250 } else if (const auto *OEF =
251 CausingFact.dyn_cast<const OriginEscapesFact *>()) {
252 if (const auto *RetEscape = dyn_cast<ReturnEscapeFact>(Val: OEF))
253 // Return stack address.
254 SemaHelper->reportUseAfterReturn(
255 IssueExpr, ReturnExpr: RetEscape->getReturnExpr(), MovedExpr, ExpiryLoc);
256 else if (const auto *FieldEscape = dyn_cast<FieldEscapeFact>(Val: OEF))
257 // Dangling field.
258 SemaHelper->reportDanglingField(
259 IssueExpr, Field: FieldEscape->getFieldDecl(), MovedExpr, ExpiryLoc);
260 else if (const auto *GlobalEscape = dyn_cast<GlobalEscapeFact>(Val: OEF))
261 // Global escape.
262 SemaHelper->reportDanglingGlobal(IssueExpr, DanglingGlobal: GlobalEscape->getGlobal(),
263 MovedExpr, ExpiryLoc);
264 else
265 llvm_unreachable("Unhandled OriginEscapesFact type");
266 } else
267 llvm_unreachable("Unhandled CausingFact type");
268 }
269 }
270
271 /// Returns the declaration of a function that is visible across translation
272 /// units, if such a declaration exists and is different from the definition.
273 static const FunctionDecl *getCrossTUDecl(const FunctionDecl &FD,
274 SourceManager &SM) {
275 if (!FD.isExternallyVisible())
276 return nullptr;
277 const FileID DefinitionFile = SM.getFileID(SpellingLoc: FD.getLocation());
278 for (const FunctionDecl *Redecl : FD.redecls())
279 if (SM.getFileID(SpellingLoc: Redecl->getLocation()) != DefinitionFile)
280 return Redecl;
281
282 return nullptr;
283 }
284
285 static const FunctionDecl *getCrossTUDecl(const ParmVarDecl &PVD,
286 SourceManager &SM) {
287 if (const auto *FD = dyn_cast<FunctionDecl>(Val: PVD.getDeclContext()))
288 return getCrossTUDecl(FD: *FD, SM);
289 return nullptr;
290 }
291
292 static void suggestWithScopeForParmVar(LifetimeSafetySemaHelper *SemaHelper,
293 const ParmVarDecl *PVD,
294 SourceManager &SM,
295 const Expr *EscapeExpr) {
296 if (const FunctionDecl *CrossTUDecl = getCrossTUDecl(PVD: *PVD, SM))
297 SemaHelper->suggestLifetimeboundToParmVar(
298 Scope: SuggestionScope::CrossTU,
299 ParmToAnnotate: CrossTUDecl->getParamDecl(i: PVD->getFunctionScopeIndex()), EscapeExpr);
300 else
301 SemaHelper->suggestLifetimeboundToParmVar(Scope: SuggestionScope::IntraTU, ParmToAnnotate: PVD,
302 EscapeExpr);
303 }
304
305 static void
306 suggestWithScopeForImplicitThis(LifetimeSafetySemaHelper *SemaHelper,
307 const CXXMethodDecl *MD, SourceManager &SM,
308 const Expr *EscapeExpr) {
309 if (const FunctionDecl *CrossTUDecl = getCrossTUDecl(FD: *MD, SM))
310 SemaHelper->suggestLifetimeboundToImplicitThis(
311 Scope: SuggestionScope::CrossTU, MD: cast<CXXMethodDecl>(Val: CrossTUDecl),
312 EscapeExpr);
313 else
314 SemaHelper->suggestLifetimeboundToImplicitThis(Scope: SuggestionScope::IntraTU,
315 MD, EscapeExpr);
316 }
317
318 void suggestAnnotations() {
319 if (!SemaHelper)
320 return;
321 SourceManager &SM = AST.getSourceManager();
322 for (auto [Target, EscapeExpr] : AnnotationWarningsMap) {
323 if (const auto *PVD = Target.dyn_cast<const ParmVarDecl *>())
324 suggestWithScopeForParmVar(SemaHelper, PVD, SM, EscapeExpr);
325 else if (const auto *MD = Target.dyn_cast<const CXXMethodDecl *>())
326 suggestWithScopeForImplicitThis(SemaHelper, MD, SM, EscapeExpr);
327 }
328 }
329
330 void reportNoescapeViolations() {
331 for (auto [PVD, EscapeTarget] : NoescapeWarningsMap) {
332 if (const auto *E = EscapeTarget.dyn_cast<const Expr *>())
333 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeExpr: E);
334 else if (const auto *FD = EscapeTarget.dyn_cast<const FieldDecl *>())
335 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeField: FD);
336 else if (const auto *G = EscapeTarget.dyn_cast<const VarDecl *>())
337 SemaHelper->reportNoescapeViolation(ParmWithNoescape: PVD, EscapeGlobal: G);
338 else
339 llvm_unreachable("Unhandled EscapingTarget type");
340 }
341 }
342
343 void inferAnnotations() {
344 for (auto [Target, EscapeExpr] : AnnotationWarningsMap) {
345 if (const auto *MD = Target.dyn_cast<const CXXMethodDecl *>()) {
346 if (!implicitObjectParamIsLifetimeBound(FD: MD))
347 SemaHelper->addLifetimeBoundToImplicitThis(MD: cast<CXXMethodDecl>(Val: MD));
348 } else if (const auto *PVD = Target.dyn_cast<const ParmVarDecl *>()) {
349 const auto *FD = dyn_cast<FunctionDecl>(Val: PVD->getDeclContext());
350 if (!FD)
351 continue;
352 // Propagates inferred attributes via the most recent declaration to
353 // ensure visibility for callers in post-order analysis.
354 FD = getDeclWithMergedLifetimeBoundAttrs(FD);
355 ParmVarDecl *InferredPVD = const_cast<ParmVarDecl *>(
356 FD->getParamDecl(i: PVD->getFunctionScopeIndex()));
357 if (!InferredPVD->hasAttr<LifetimeBoundAttr>())
358 InferredPVD->addAttr(
359 A: LifetimeBoundAttr::CreateImplicit(Ctx&: AST, Range: PVD->getLocation()));
360 }
361 }
362 }
363};
364} // namespace
365
366void runLifetimeChecker(const LoanPropagationAnalysis &LP,
367 const MovedLoansAnalysis &MovedLoans,
368 const LiveOriginsAnalysis &LO, FactManager &FactMgr,
369 AnalysisDeclContext &ADC,
370 LifetimeSafetySemaHelper *SemaHelper) {
371 llvm::TimeTraceScope TimeProfile("LifetimeChecker");
372 LifetimeChecker Checker(LP, MovedLoans, LO, FactMgr, ADC, SemaHelper);
373}
374
375} // namespace clang::lifetimes::internal
376