Author: Utkarsh Saxena Date: 2026-07-27T08:23:32Z New Revision: bb75638cb7fa090bb6e4c4c3e6e15e693a69b1d1
URL: https://github.com/llvm/llvm-project/commit/bb75638cb7fa090bb6e4c4c3e6e15e693a69b1d1 DIFF: https://github.com/llvm/llvm-project/commit/bb75638cb7fa090bb6e4c4c3e6e15e693a69b1d1.diff LOG: [LifetimeSafety][NFC] Refactor AccessPath and Loan representations (#180369) This patch refactors the internal representations of `AccessPath` and `Loan` to support path elements, preparing for field-sensitive and interior-sensitive lifetime tracking. * Introduces `PathElement` representing a field or interior dereference. * Refactors `AccessPath` to contain a base and a list of `PathElement`s. * Updates `Loan` and `LoanManager` to use the new `AccessPath` structure. --- Old PR description: Refactor loan representation to use structured access paths, enabling more precise borrow tracking and detection of use-after-invalidation. Previously, loans were associated only with top-level storage (e.g., a variable `x`, temporary `t`). This was insufficient for reasoning about borrows of sub-objects (interior memory regions), such as fields (`x.f`) or container elements (`vec[0]`), or for modelling views like `string_view` which borrow the interior of an object. We modify `AccessPath`, which now consists of a `base` (a _variable_, _temporary_, or _placeholder_ for _parameters/'this'_) and a sequence of `PathElements`. A `PathElement` can be a field access (`.field`) or an interior access (denoted as `.*`), representing an unnamed interior memory region of an object, like the character buffer of a `std::string`. High-level changes: * `PathLoan` and `PlaceholderLoan` are merged into a single Loan class, containing an `AccessPath`. * **Path-Based Expiry**: `ExpireFact` is changed from expiring a single loan to expiring an `AccessPath`. If `x` goes out of scope, any loan whose path starts with `x` (e.g., loans to `x`, `x.field`, `x.field.*`) is now considered expired. The checker uses `isPrefixOf` to detect this. * **Path Extension in Flows**: `OriginFlowFact` now supports extending loan paths: * Field access like for expression `obj.field` extends loans to `obj` into loans to `obj.field`. * Owner-to-view conversions like `std::string_view s(str)` extend loans to `str` into loans to `str.*`. * **Invalidation**: Container invalidation methods (e.g., `vec.push_back()`) invalidate loans whose path is a strict extension of the container's path (e.g., loans to `vec.*` but not loans to `vec`). The checker uses `isStrictPrefixOf`. * **Move-Tracking**: Moves are now tracked based on path prefixes via `isPrefixOf`. This refactoring enables detection of use-after-invalidation bugs for STL containers specially when the container appears as fields. Added: Modified: clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h clang/lib/Analysis/LifetimeSafety/Checker.cpp clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp clang/lib/Analysis/LifetimeSafety/Loans.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h index cfaae4d574686..8137a207290d7 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h @@ -18,6 +18,8 @@ #include "clang/AST/DeclCXX.h" #include "clang/AST/ExprCXX.h" #include "clang/Analysis/Analyses/LifetimeSafety/Utils.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/raw_ostream.h" namespace clang::lifetimes::internal { @@ -27,126 +29,203 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, LoanID ID) { return OS << ID.Value; } -/// Represents the storage location being borrowed, e.g., a specific stack -/// variable or a field within it: var.field.* +/// Represents one step in an access path: either a field access or an +/// access to an unnamed interior region (denoted by '*'). /// -/// An AccessPath consists of a root which is one of: -/// - ValueDecl: a local variable or global -/// - MaterializeTemporaryExpr: a temporary object -/// - ParmVarDecl: a function parameter (placeholder) -/// - CXXMethodDecl: the implicit 'this' object (placeholder) -/// - CXXNewExpr: a heap allocation made by `new` -/// -/// Placeholder paths never expire within the function scope, as they represent -/// storage from the caller's scope. -/// -/// TODO: Model access paths of other types, e.g. field, array subscript, heap -/// allocation not through `new`, and globals. -class AccessPath { +/// Examples: +/// - Field access: `obj.field` has PathElement 'field' +/// - Interior access: `owner.*` has '*' +/// - In `std::string s; std::string_view v = s;`, v has loan to s.* +/// - Array element: `arr[i]` has PathElement '*' (same as interior access) +class PathElement { public: - enum class Kind : uint8_t { - ValueDecl, - MaterializeTemporary, - PlaceholderParam, - PlaceholderThis, - NewAllocation, - }; + enum class Kind { Field, Interior }; + + static PathElement getField(const FieldDecl &FD) { + return PathElement(Kind::Field, &FD); + } + static PathElement getInterior() { + return PathElement(Kind::Interior, nullptr); + } + + bool isField() const { return K == Kind::Field; } + bool isInterior() const { return K == Kind::Interior; } + const FieldDecl *getFieldDecl() const { return FD; } + + bool operator==(const PathElement &Other) const { + return K == Other.K && FD == Other.FD; + } + bool operator!=(const PathElement &Other) const { return !(*this == Other); } + + void dump(llvm::raw_ostream &OS) const { + if (isField()) + OS << "." << FD->getNameAsString(); + else + OS << ".*"; + } private: + PathElement(Kind K, const FieldDecl *FD) : K(K), FD(FD) {} Kind K; - llvm::PointerUnion<const Expr *, const Decl *> Root; + const FieldDecl *FD; +}; + +/// Represents the base of a placeholder access path, which is either a +/// function parameter or the implicit 'this' object of an instance method. +/// Placeholder paths never expire within the function scope, as they represent +/// storage from the caller's scope. +class PlaceholderBase : public llvm::FoldingSetNode { + llvm::PointerUnion<const ParmVarDecl *, const CXXMethodDecl *> ParamOrMethod; public: - AccessPath(const clang::ValueDecl *D) : K(Kind::ValueDecl), Root(D) {} - AccessPath(const clang::MaterializeTemporaryExpr *MTE) - : K(Kind::MaterializeTemporary), Root(MTE) {} - AccessPath(const CXXNewExpr *New) : K(Kind::NewAllocation), Root(New) {} - static AccessPath Placeholder(const ParmVarDecl *PVD) { - return AccessPath(Kind::PlaceholderParam, PVD); + PlaceholderBase(const ParmVarDecl *PVD) : ParamOrMethod(PVD) {} + PlaceholderBase(const CXXMethodDecl *MD) : ParamOrMethod(MD) {} + + const ParmVarDecl *getParmVarDecl() const { + return ParamOrMethod.dyn_cast<const ParmVarDecl *>(); } - static AccessPath Placeholder(const CXXMethodDecl *MD) { - return AccessPath(Kind::PlaceholderThis, MD); + + const CXXMethodDecl *getImplicitThisParent() const { + return ParamOrMethod.dyn_cast<const CXXMethodDecl *>(); } - AccessPath(const AccessPath &Other) : K(Other.K), Root(Other.Root) {} - AccessPath &operator=(const AccessPath &) = delete; - Kind getKind() const { return K; } + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddPointer(ParamOrMethod.getOpaqueValue()); + } +}; + +/// Represents the storage location being borrowed, e.g., a specific stack +/// variable or a field within it: var.field.* +/// +/// An AccessPath consists of: +/// - A base: either a ValueDecl, MaterializeTemporaryExpr, or PlaceholderBase +/// - A sequence of PathElements representing field accesses or interior +/// regions +/// +/// Examples: +/// - `x` -> Base=x, Elements=[] +/// - `x.field` -> Base=x, Elements=[.field] +/// - `x.*` (e.g., string_view from string) -> Base=x, Elements=[.*] +/// - `x.field.*` -> Base=x, Elements=[.field, .*] +/// - `$param.field` -> Base=$param, Elements=[.field] +/// +/// TODO: Model access paths of other types, e.g. heap and globals. +class AccessPath { + /// The base of the access path: a variable, temporary, or placeholder. + const llvm::PointerUnion<const clang::ValueDecl *, + const clang::MaterializeTemporaryExpr *, + const PlaceholderBase *, const clang::CXXNewExpr *> + Base; + /// The path elements representing field accesses and access to unnamed + /// interior regions. + llvm::SmallVector<PathElement, 1> Elements; + +public: + AccessPath(const clang::ValueDecl *D) : Base(D) {} + AccessPath(const clang::MaterializeTemporaryExpr *MTE) : Base(MTE) {} + AccessPath(const PlaceholderBase *PB) : Base(PB) {} + AccessPath(const clang::CXXNewExpr *New) : Base(New) {} + + /// Creates an extended access path by appending a path element. + /// Example: AccessPath(x_path, field) creates path to `x.field`. + AccessPath(const AccessPath &Other, PathElement E) + : Base(Other.Base), Elements(Other.Elements) { + Elements.push_back(E); + } const clang::ValueDecl *getAsValueDecl() const { - return K == Kind::ValueDecl - ? cast<const clang::ValueDecl>(cast<const clang::Decl *>(Root)) - : nullptr; + return Base.dyn_cast<const clang::ValueDecl *>(); } + const clang::MaterializeTemporaryExpr *getAsMaterializeTemporaryExpr() const { - return K == Kind::MaterializeTemporary - ? cast<const MaterializeTemporaryExpr>( - cast<const clang::Expr *>(Root)) - : nullptr; - } - const ParmVarDecl *getAsPlaceholderParam() const { - return K == Kind::PlaceholderParam - ? cast<const ParmVarDecl>(cast<const clang::Decl *>(Root)) - : nullptr; + return Base.dyn_cast<const clang::MaterializeTemporaryExpr *>(); } - const CXXMethodDecl *getAsPlaceholderThis() const { - return K == Kind::PlaceholderThis - ? cast<const CXXMethodDecl>(cast<const clang::Decl *>(Root)) - : nullptr; + + const PlaceholderBase *getAsPlaceholderBase() const { + return Base.dyn_cast<const PlaceholderBase *>(); } - const CXXNewExpr *getAsNewAllocation() const { - return K == Kind::NewAllocation - ? cast<const CXXNewExpr>(cast<const clang::Expr *>(Root)) - : nullptr; + + const clang::CXXNewExpr *getAsNewAllocation() const { + return Base.dyn_cast<const clang::CXXNewExpr *>(); } bool operator==(const AccessPath &RHS) const { - return K == RHS.K && Root == RHS.Root; + return Base == RHS.Base && Elements == RHS.Elements; } bool operator!=(const AccessPath &RHS) const { return !(*this == RHS); } - void dump(llvm::raw_ostream &OS) const; -private: - AccessPath(Kind K, const ParmVarDecl *PVD) : K(K), Root(PVD) {} - AccessPath(Kind K, const CXXMethodDecl *MD) : K(K), Root(MD) {} + /// Returns true if this path is a prefix of Other (or same as Other). + /// Examples: + /// - `x` is a prefix of `x`, `x.field`, `x.field.*` + /// - `x.field` is a prefix of `x.field` and `x.field.nested` + /// - `x.field` is NOT a prefix of `x.other_field` + bool isPrefixOf(const AccessPath &Other) const { + if (Base != Other.Base || Elements.size() > Other.Elements.size()) + return false; + return std::equal(Elements.begin(), Elements.end(), Other.Elements.begin()); + } + + /// Returns true if this path is a strict prefix of Other. + /// Example: + /// - `x` is a strict prefix of `x.field` but NOT of `x` + bool isStrictPrefixOf(const AccessPath &Other) const { + return Elements.size() < Other.Elements.size() && isPrefixOf(Other); + } + llvm::ArrayRef<PathElement> getElements() const { return Elements; } + + void dump(llvm::raw_ostream &OS) const; }; -/// Represents lending a storage location. +/// Represents a component of an access path: either a named field access or an +/// abstract unnamed interior region (denoted by '*'). /// -/// A loan tracks the borrowing relationship created by operations like -/// taking a pointer/reference (&x), creating a view (std::string_view sv = s), -/// or receiving a parameter. +/// The interior access (`*`) represents the borrowable content of an object +/// without exposing its internal implementation details. It may abstract over +/// multiple underlying fields or memory regions. /// /// Examples: /// - `int* p = &x;` creates a loan to `x` +/// - `std::string_view v = s;` creates a loan to `s.*` (interior) +/// - `int* p = &obj.field;` creates a loan to `obj.field` /// - Parameter loans have no IssueExpr (created at function entry) class Loan { const LoanID ID; const AccessPath Path; - /// The expression that creates the loan, e.g., &x. Null for placeholder + /// The expression that creates the loan, e.g., &x. Optional for placeholder /// loans. - const Expr *IssuingExpr; + const Expr *IssueExpr; public: - Loan(LoanID ID, AccessPath Path, const Expr *IssuingExpr) - : ID(ID), Path(Path), IssuingExpr(IssuingExpr) {} + Loan(LoanID ID, AccessPath Path, const Expr *IssueExpr = nullptr) + : ID(ID), Path(Path), IssueExpr(IssueExpr) {} + LoanID getID() const { return ID; } const AccessPath &getAccessPath() const { return Path; } - const Expr *getIssuingExpr() const { return IssuingExpr; } + const Expr *getIssueExpr() const { return IssueExpr; } + void dump(llvm::raw_ostream &OS) const; }; /// Manages the creation, storage and retrieval of loans. class LoanManager { + public: LoanManager() = default; - Loan *createLoan(AccessPath Path, const Expr *IssueExpr) { + Loan *createLoan(AccessPath Path, const Expr *IssueExpr = nullptr) { void *Mem = LoanAllocator.Allocate<Loan>(); auto *NewLoan = new (Mem) Loan(getNextLoanID(), Path, IssueExpr); AllLoans.push_back(NewLoan); return NewLoan; } + Loan *createPlaceholderLoan(const ParmVarDecl *PVD) { + return createLoan(AccessPath(getOrCreatePlaceholderBase(PVD))); + } + Loan *createPlaceholderLoan(const CXXMethodDecl *MD) { + return createLoan(AccessPath(getOrCreatePlaceholderBase(MD))); + } + const Loan *getLoan(LoanID ID) const { assert(ID.Value < AllLoans.size()); return AllLoans[ID.Value]; @@ -157,7 +236,14 @@ class LoanManager { private: LoanID getNextLoanID() { return NextLoanID++; } + /// Gets or creates a placeholder base for a given parameter or method. + const PlaceholderBase *getOrCreatePlaceholderBase(const ParmVarDecl *PVD); + const PlaceholderBase *getOrCreatePlaceholderBase(const CXXMethodDecl *MD); + LoanID NextLoanID{0}; + + llvm::FoldingSet<PlaceholderBase> PlaceholderBases; + /// TODO(opt): Profile and evaluate the usefullness of small buffer /// optimisation. llvm::SmallVector<const Loan *> AllLoans; diff --git a/clang/lib/Analysis/LifetimeSafety/Checker.cpp b/clang/lib/Analysis/LifetimeSafety/Checker.cpp index 53e5077131147..380237d890bc8 100644 --- a/clang/lib/Analysis/LifetimeSafety/Checker.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Checker.cpp @@ -166,10 +166,12 @@ class LifetimeChecker { auto MovedAtEscape = MovedLoans.getMovedLoans(OEF); for (LoanID LID : EscapedLoans) { const Loan *L = FactMgr.getLoanMgr().getLoan(LID); - const AccessPath &AP = L->getAccessPath(); - if (const auto *PVD = AP.getAsPlaceholderParam()) + const PlaceholderBase *PB = L->getAccessPath().getAsPlaceholderBase(); + if (!PB) + continue; + if (const auto *PVD = PB->getParmVarDecl()) CheckParam(PVD, /*IsMoved=*/MovedAtEscape.lookup(LID)); - else if (const auto *MD = AP.getAsPlaceholderThis()) + else if (const auto *MD = PB->getImplicitThisParent()) CheckImplicitThis(MD); } } @@ -177,7 +179,8 @@ class LifetimeChecker { /// Checks for use-after-free & use-after-return errors when an access path /// expires (e.g., a variable goes out of scope). /// - /// When a path expires, all loans having this path expires. + /// When a path expires, all loans prefixed by that path expire. For example, + /// if `x` expires, loans to `x`, `x.field`, and `x.field.*` all expire. /// This method examines all live origins and reports warnings for loans they /// hold that are prefixed by the expired path. void checkExpiry(const ExpireFact *EF) { @@ -209,9 +212,11 @@ class LifetimeChecker { /// Checks for use-after-invalidation errors when a container is modified. /// - /// This method identifies origins that are live at the point of invalidation - /// and checks if they hold loans that are invalidated by the operation - /// (e.g., iterators into a vector that is being pushed to). + /// When a container is invalidated, loans pointing into its interior are + /// invalidated. For example, if container `v` is invalidated, iterators with + /// loans to `v.*` are invalidated. This method finds live origins holding + /// such loans and reports warnings. A loan is invalidated if its path extends + /// an invalidated container's path (e.g., `v.*` extends `v`). void checkInvalidation(const InvalidateOriginFact *IOF) { OriginID InvalidatedOrigin = IOF->getInvalidatedOrigin(); /// Get loans directly pointing to the invalidated container @@ -251,11 +256,13 @@ class LifetimeChecker { return; for (const auto &[LID, Warning] : FinalWarningsMap) { const Loan *L = FactMgr.getLoanMgr().getLoan(LID); - const Expr *IssueExpr = L->getIssuingExpr(); + const Expr *IssueExpr = L->getIssueExpr(); + const ParmVarDecl *InvalidatedPVD = nullptr; + if (const PlaceholderBase *PB = L->getAccessPath().getAsPlaceholderBase()) + InvalidatedPVD = PB->getParmVarDecl(); + llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> CausingFact = Warning.CausingFact; - const ParmVarDecl *InvalidatedPVD = - L->getAccessPath().getAsPlaceholderParam(); const Expr *MovedExpr = Warning.MovedExpr; SourceLocation ExpiryLoc = Warning.ExpiryLoc; diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index 466bb2185c6d8..ac6267dabf48e 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp @@ -1238,9 +1238,8 @@ llvm::SmallVector<Fact *> FactsGenerator::issuePlaceholderLoans() { llvm::SmallVector<Fact *> PlaceholderLoanFacts; if (auto ThisOrigins = FactMgr.getOriginMgr().getThisOrigins()) { OriginList *List = *ThisOrigins; - const Loan *L = FactMgr.getLoanMgr().createLoan( - AccessPath::Placeholder(cast<CXXMethodDecl>(FD)), - /*IssuingExpr=*/nullptr); + const Loan *L = + FactMgr.getLoanMgr().createPlaceholderLoan(cast<CXXMethodDecl>(FD)); PlaceholderLoanFacts.push_back( FactMgr.createFact<IssueFact>(L->getID(), List->getOuterOriginID())); } @@ -1248,8 +1247,7 @@ llvm::SmallVector<Fact *> FactsGenerator::issuePlaceholderLoans() { OriginList *List = getOriginsList(*PVD); if (!List) continue; - const Loan *L = FactMgr.getLoanMgr().createLoan( - AccessPath::Placeholder(PVD), /*IssuingExpr=*/nullptr); + const Loan *L = FactMgr.getLoanMgr().createPlaceholderLoan(PVD); PlaceholderLoanFacts.push_back( FactMgr.createFact<IssueFact>(L->getID(), List->getOuterOriginID())); } diff --git a/clang/lib/Analysis/LifetimeSafety/Loans.cpp b/clang/lib/Analysis/LifetimeSafety/Loans.cpp index c0c8d0b283f8b..e71842eefca6a 100644 --- a/clang/lib/Analysis/LifetimeSafety/Loans.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Loans.cpp @@ -11,28 +11,22 @@ namespace clang::lifetimes::internal { void AccessPath::dump(llvm::raw_ostream &OS) const { - switch (K) { - case Kind::ValueDecl: - if (const clang::ValueDecl *VD = getAsValueDecl()) - OS << VD->getNameAsString(); - break; - case Kind::MaterializeTemporary: - if (const clang::MaterializeTemporaryExpr *MTE = - getAsMaterializeTemporaryExpr()) - OS << "MaterializeTemporaryExpr at " << MTE; - break; - case Kind::PlaceholderParam: - if (const auto *PVD = getAsPlaceholderParam()) + if (const clang::ValueDecl *VD = getAsValueDecl()) + OS << VD->getNameAsString(); + else if (const clang::MaterializeTemporaryExpr *MTE = + getAsMaterializeTemporaryExpr()) + OS << "MaterializeTemporaryExpr at " << MTE; + else if (const PlaceholderBase *PB = getAsPlaceholderBase()) { + if (const auto *PVD = PB->getParmVarDecl()) OS << "$" << PVD->getNameAsString(); - break; - case Kind::PlaceholderThis: - OS << "$this"; - break; - case Kind::NewAllocation: - if (const auto *E = getAsNewAllocation()) - OS << "NewAllocation at " << E; - break; - } + else if (PB->getImplicitThisParent()) + OS << "$this"; + } else if (const auto *E = getAsNewAllocation()) + OS << "NewAllocation at " << E; + else + llvm_unreachable("access path base invalid"); + for (const auto &E : Elements) + E.dump(OS); } void Loan::dump(llvm::raw_ostream &OS) const { @@ -40,4 +34,34 @@ void Loan::dump(llvm::raw_ostream &OS) const { Path.dump(OS); OS << ")"; } + +const PlaceholderBase * +LoanManager::getOrCreatePlaceholderBase(const ParmVarDecl *PVD) { + llvm::FoldingSetNodeID ID; + ID.AddPointer(PVD); + void *InsertPos = nullptr; + if (PlaceholderBase *Existing = + PlaceholderBases.FindNodeOrInsertPos(ID, InsertPos)) + return Existing; + + void *Mem = LoanAllocator.Allocate<PlaceholderBase>(); + PlaceholderBase *NewPB = new (Mem) PlaceholderBase(PVD); + PlaceholderBases.InsertNode(NewPB, InsertPos); + return NewPB; +} + +const PlaceholderBase * +LoanManager::getOrCreatePlaceholderBase(const CXXMethodDecl *MD) { + llvm::FoldingSetNodeID ID; + ID.AddPointer(MD); + void *InsertPos = nullptr; + if (PlaceholderBase *Existing = + PlaceholderBases.FindNodeOrInsertPos(ID, InsertPos)) + return Existing; + + void *Mem = LoanAllocator.Allocate<PlaceholderBase>(); + PlaceholderBase *NewPB = new (Mem) PlaceholderBase(MD); + PlaceholderBases.InsertNode(NewPB, InsertPos); + return NewPB; +} } // namespace clang::lifetimes::internal _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
