From c024ff6135f0ca6ce247d98f380346f76375408d Mon Sep 17 00:00:00 2001 From: Ian Jackson Date: Thu, 14 Nov 2024 23:18:49 +0000 Subject: [PATCH] eocs --- src/lib.rs | 133 ++++++++++++++++++++++++++++++++++++++++++++--- src/test/demo.rs | 2 +- 2 files changed, 126 insertions(+), 9 deletions(-) diff --git a/src/lib.rs b/src/lib.rs index 3dc8d5a..b343c7d 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,18 +1,99 @@ +//! Manual memory management, with a reasonable API and fewer footguns +//! +//! [`Ptr`] is a halfway house between `Box` and `*mut T`. +//! See its documentation for the detailed of the API. +//! +//! We aim to reproduce roughly the division of responsibility +//! (between programmer and compiler) +//! found in C. +//! +//! ### Caller responsibilities +//! +//! * Knowing which data is still live, freeing it as and when needed, +//! and not freeing it too soon. +//! Not accessing freed data. +//! +//! * Not defeating the library's anti-alias protections. +//! In particular: holding a suitable singleton ([`NoAliasSingleton`]) +//! which each `Ptr` belogns to +//! (even though there is nothing in the API +//! eg, lifetimes, to link them). +//! +//! ### Library responsibilities +//! +//! * Following Rust's aliasing rules, +//! which are (for our purposes) stricter than C's. +//! The library should prevent accidental creation +//! of overlapping `&mut`, for example. +//! +//! * Threadsafety; `Send` and `Sync`. +//! (The caller must still make sure not to free an object +//! that another thread may be using, of course.) +//! +//! * Soundness in the face of panics, including in methods +//! of the contained type `T`, eg `T`'s `Drop` impl. +//! +//! * "`Drop` footguns", and others, sometimes found in unsafe code. +//! +//! ### Soundness +//! +//! This library aims to be sound in the usual Rust sense. +//! That is, you should not be able to produce UB +//! without calling `unsafe` functions and writing buggy code. +//! +//! **However**, it is impossible to use this library +//! without making calls to unsafe functions. +//! And the invariants and rules for the unsafe entrypoints, +//! are more global, and arguably harder to uphold, +//! than is usual for a Rust API. +//! +//! In practice this means that in a real program, +//! correctness is likely to depend on the behaviour +//! of even nominally "safe" code. +//! The rules have been chosen pragmatically, +//! to minimise the proportion of the caller that needs +//! to be *actually marked* with `unsafe`. +//! But in practice, much of a caller's code +//! will be able to violate invariants and cause UB. +//! +//! You cannot sensibly pass `Ptr` to naive, safe, code. +//! If you want to provide a conventionally safe and sound API, +//! you must wrap up your entire data structure, +//! hiding all of this library's types. #[cfg(test)] mod test; use std::collections::HashSet; -use std::fmt::{self, Debug}; +use std::fmt::{self, Debug, Display}; use std::marker::PhantomData; use std::ptr::NonNull; //---------- public types ---------- -/// Pointer to manually-memory-managed `T` +/// **Pointer to manually-memory-managed `T`** /// /// Ensuring that `Ptr`s are freed at the right time is up to the caller. -/// But aliasing, drop, etc., is (largely) handled by the library. +/// But aliasing, and other Rust unsafe footguns, +/// is (largely) handled by the library. +/// +/// To access the contained data, +/// [`Ptr::borrow()`] +/// and +/// [`borrow_mut()`](Ptr::borrow_mut). +/// +/// To mutably access the data of more than one node at once, +/// use +/// [`IsMutToken::multi_static`], +/// [`IsMutToken::multi_dynamic`], +/// or for manual aliasing checks, +/// [`.borrow_mut()`](Ptr::borrow_mut()) with +/// [`MutToken::new_unchecked()`]. +/// +/// # +/// +/// The API is sound in the usual Rust sense: +/// however, it /// /// This type is `Copy`. Copying it (or, indeed, cloning it) /// does not copy the underlying data. @@ -64,7 +145,8 @@ pub struct MutToken<'a>( impl<'a> MutToken<'a> { /// Allowing borrowing on the caller's recognisance /// - /// This will let you call [`Ptr::borrow()`]/[`borrow_kut()`] + /// This will let you call + /// [`Ptr::borrow()`]/[`borrow_mut()`](Ptr::borrow_mut) /// multiple times, retaining and using all the resulting references. /// /// SAFETY @@ -104,6 +186,18 @@ pub unsafe trait IsMutToken<'a>: IsRefToken<'a> + Sized + Sealed { MutToken(PhantomData) } + /// Borrow from a small, fixed, number of multiple `Ptr` + /// + /// Call + /// [`.borrow`](MultiStatic::borrow) + /// and + /// [`.borrow_mut`](MultiStatic::borrow) + /// to obtain real references from multiple `Ptr`s. + /// + /// A `MultiStatic` embodies the values of the `Ptr`s + /// which have been borrowed already. + /// Runtime checks are done by a simple search, + /// O(n^2) time and O(n) space in the number of borrows. fn multi_static<'r>(self) -> MultiStatic<'r, ()> where 'a: 'r { MultiStatic { tok: self.mut_token(), @@ -111,8 +205,19 @@ pub unsafe trait IsMutToken<'a>: IsRefToken<'a> + Sized + Sealed { } } - fn multi_runtime<'r>(self) -> MultiRuntime<'r> where 'a: 'r { - MultiRuntime { + /// Borrow from an unknown number of `Ptr` with dynamic runtime checking + /// + /// Call + /// [`.borrow`](MultiDynamic::borrow) + /// and + /// [`.borrow_mut`](MultiDynamic::borrow) + /// to obtain real references from multiple `Ptr`s + /// + /// `MultiDynamic` contains two `HashSet`s + /// tracking which `Ptr`s have been borrowed already. + /// Borrowing uses O(n) space, on the heap, and O(n) time. + fn multi_dynamic<'r>(self) -> MultiDynamic<'r> where 'a: 'r { + MultiDynamic { _tok: self.mut_token(), ref_given: HashSet::new(), mut_given: HashSet::new(), @@ -275,18 +380,30 @@ impl Debug for Ptr { //---------- multi-borrowing, runtime-checked ---------- +/// Conflicting borrows occurred #[derive(Debug)] pub struct BorrowConflict; +impl Display for BorrowConflict { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "conflicting borrows attempted") + } +} +impl std::error::Error for BorrowConflict { +} + type BorrowResult = Result; -pub struct MultiRuntime<'a> { +/// Tracker for multiple borrows +/// +/// Returned from ` +pub struct MultiDynamic<'a> { _tok: MutToken<'a>, ref_given: HashSet>, mut_given: HashSet>, } -impl<'a> MultiRuntime<'a> { +impl<'a> MultiDynamic<'a> { #[inline] pub fn borrow<'r, T>(&mut self, p: Ptr) -> BorrowResult<&'r T> where 'a: 'r diff --git a/src/test/demo.rs b/src/test/demo.rs index 5d57cb0..b4536b5 100644 --- a/src/test/demo.rs +++ b/src/test/demo.rs @@ -109,7 +109,7 @@ impl List { } pub fn all_mut_safe(&mut self) -> impl Iterator { - let mut multi = self.noalias.multi_runtime(); + let mut multi = self.noalias.multi_dynamic(); Self::iter_ptrs(self.head, move |node| { let node = multi.borrow_mut(node).expect("untangled!"); (&mut node.data, node.next) -- 2.30.2