slice_dst/lib.rs
1#![warn(missing_docs, missing_debug_implementations)]
2#![no_std]
3
4//! Support for custom slice-based DSTs.
5//!
6//! By handling allocation manually, we can manually allocate the `Box` for a custom DST.
7//! So long as the size lines up with what it should be, once the metadata is created,
8//! Rust actually already handles the DSTs it already supports perfectly well, safely!
9//! Setting them up is the hard part, which this crate handles for you.
10//!
11//! # Examples
12//!
13//! We have a tree structure! Each node holds some data and its children array.
14//! In normal Rust, you would probably typically implement it something like this:
15//!
16//! ```rust
17//! # use std::sync::Arc;
18//! struct Node {
19//! data: &'static str,
20//! children: Vec<Arc<Node>>,
21//! }
22//!
23//! let a = Node { data: "a", children: vec![] };
24//! let b = Node { data: "b", children: vec![] };
25//! let c = Node { data: "c", children: vec![] };
26//! let abc = Node { data: "abc", children: vec![a.into(), b.into(), c.into()] };
27//! ```
28//!
29//! With this setup, the memory layout looks vaguely like the following diagram:
30//!
31//! ```text
32//! +--------------+
33//! |Node |
34//! +---->|data: "a" |
35//! +------------+ +---------------+ | |children: none|
36//! |Node | |Vec<Arc<Node>> | | +--------------+
37//! |data: "abc" | |[0]: +--------------+ |Node |
38//! |children: +----->|[1]: +------------------->|data: "b" |
39//! +------------+ |[2]: +--------------+ |children: none|
40//! +---------------| | +--------------+
41//! | |Node |
42//! +---->|data: "c" |
43//! |children: none|
44//! +--------------+
45//! ```
46//!
47//! With this crate, however, the children array can be stored inline with the node's data:
48//!
49//! ```rust
50//! # use std::{iter, sync::Arc}; use slice_dst::*;
51//! struct Node(Arc<SliceWithHeader<&'static str, Node>>);
52//!
53//! let a = Node(SliceWithHeader::new("a", None));
54//! let b = Node(SliceWithHeader::new("b", None));
55//! let c = Node(SliceWithHeader::new("c", None));
56//! // this vec is just an easy way to get an ExactSizeIterator
57//! let abc = Node(SliceWithHeader::new("abc", vec![a, b, c]));
58//! ```
59//!
60//! ```text
61//! +-----------+
62//! +-------------+ |Node |
63//! |Node | +---->|length: 0 |
64//! |length: 3 | | |header: "a"|
65//! |header: "abc"| | +-----------+
66//! |slice: [0]: +-----+ |Node |
67//! | [1]: +---------->|length: 0 |
68//! | [2]: +-----+ |header: "b"|
69//! +-------------+ | +-----------+
70//! | |Node |
71//! +---->|length: 0 |
72//! |header: "c"|
73//! +------------
74//! ```
75//!
76//! The exact times you will want to use this rather than just standard types varries.
77//! This is mostly useful when space optimization is very important.
78//! This is still useful when using an arena: it reduces the allocations in the arena
79//! in exchange for moving node payloads to the heap alongside the children array.
80//!
81//! # But how?
82//!
83//! This is possible because of the following key building blocks:
84//!
85//! - `Box`'s [memory layout][boxed-memory-layout] is defined and uses the
86//! [global allocator][std::alloc::Global], and is allowed to be manually allocated.
87//! - [Array layout][array-layout] and [slice layout][slice-layout] are defined.
88//! - [`#[repr(C)]`][repr-c-layout] allows us to make compound types with defined layout.
89//! - We can turn an opaque pointer into a slice fat pointer with
90//! [`ptr::slice_from_raw_parts`].
91//! - We can cast a slice pointer to a pointer to our compound type
92//! in order to keep the correct fat pointer metadata.
93//!
94//! So with these guarantees, we can "just" manually allocate some space, initialize it
95//! for some custom `repr(C)` structure, and convert it into a `Box`. From that point,
96//! `Box` handles managing the memory, including deallocation or moving it into another
97//! smart pointer, such as `Arc`.
98//!
99//! [boxed-memory-layout]: <https://doc.rust-lang.org/stable/std/boxed/index.html#memory-layout>
100//! [array-layout]: <https://doc.rust-lang.org/stable/reference/type-layout.html#array-layout>
101//! [slice-layout]: <https://doc.rust-lang.org/stable/reference/type-layout.html#slice-layout>
102//! [repr-c-layout]: <https://doc.rust-lang.org/stable/reference/type-layout.html#reprc-structs>
103//! [std::alloc::Global]: <https://doc.rust-lang.org/stable/std/alloc/index.html#the-global_allocator-attribute>
104//!
105//! [`SliceDst`] defines the capabilities required of the pointee type. It must be able to
106//! turn a trailing slice length into a [`Layout`] for the whole pointee, and it must provide
107//! a way to turn a untyped slice pointer `*mut [()]` into a correctly typed pointer.
108//!
109//! The functions [`alloc_slice_dst`] and [`alloc_slice_dst_in`] provide a way
110//! to allocate space for a `SliceDst` type via the global allocator.
111//!
112//! [`AllocSliceDst`] types are owning heap pointers that can create a new slice DST.
113//! They take an initialization routine that is responsible for initializing the
114//! uninitialized allocated place, and do the ceremony required to allocate the place
115//! and turn it into the proper type by delgating to `SliceDst` and `alloc_slice_dst`.
116//! They also handle panic/unwind safety of the initialization routine and prevent
117//! leaking of the allocated place due to an initialization panic.
118//!
119//! [`TryAllocSliceDst`] is the potentially fallible initialization version.
120//!
121//! All of these pieces are the glue, but [`SliceWithHeader`] and [`StrWithHeader`]
122//! put the pieces together into a safe package. They take a header and an iterator
123//! (or copyable slice) and put together all of the pieces to allocate a dynamically
124//! sized custom type.
125//!
126//! Additionaly, though not strictly required, these types store the slice length inline.
127//! This gives them the ability to reconstruct pointers from fully type erased pointers
128#![cfg_attr(feature = "erasable", doc = "via the [`Erasable`] trait")]
129//! .
130
131// All hail Chairity!
132// The one who saves our sanity -
133// blessing us with Clarity.
134// Queen of popularity.
135// When haboo becomes a rarity -
136// we thank Yoba for Chairity.
137// https://twitch.tv/thehaboo
138
139extern crate alloc;
140
141#[cfg(feature = "erasable")]
142use erasable::{Erasable, ErasedPtr};
143use {
144 alloc::{
145 alloc::{alloc, dealloc, handle_alloc_error},
146 boxed::Box,
147 rc::Rc,
148 sync::Arc,
149 },
150 core::{alloc::Layout, mem::ManuallyDrop, ptr},
151};
152
153/// A custom slice-based dynamically sized type.
154///
155/// Unless you are making a custom slice DST that needs to pack its length extremely well,
156/// then you should just use [`SliceWithHeader`] instead.
157///
158/// # Safety
159///
160/// Must be implemented as described and may be relied upon by generic code.
161pub unsafe trait SliceDst {
162 /// Get the layout of the slice-containing type with the given slice length.
163 fn layout_for(len: usize) -> Layout;
164
165 /// Add the type onto an untyped pointer.
166 ///
167 /// This is used to add the type on during allocation.
168 /// This function is required because otherwise Rust cannot
169 /// guarantee that the metadata on both sides of the cast lines up.
170 ///
171 /// # Safety
172 ///
173 /// The implementation _must not_ dereference the input pointer.
174 /// This function is safe because it must work for all input pointers,
175 /// without asserting the pointer's validity of any kind, express or implied,
176 /// including but not limited to the validities of alignment, fitness for
177 /// dereferencing and nullity.
178 ///
179 /// In practice, this means that the implementation should just be a pointer cast.
180 fn retype(ptr: ptr::NonNull<[()]>) -> ptr::NonNull<Self>;
181}
182
183unsafe impl<T> SliceDst for [T] {
184 fn layout_for(len: usize) -> Layout {
185 Layout::array::<T>(len).unwrap()
186 }
187
188 fn retype(ptr: ptr::NonNull<[()]>) -> ptr::NonNull<Self> {
189 unsafe { ptr::NonNull::new_unchecked(ptr.as_ptr() as *mut _) }
190 }
191}
192
193/// Allocate a slice-based DST with the [global allocator][`alloc()`].
194///
195/// The returned pointer is owned and completely uninitialized;
196/// you are required to initialize it correctly.
197///
198/// If the type to be allocated has zero size,
199/// then an arbitrary aligned dangling nonnull pointer is returned.
200pub fn alloc_slice_dst<S: ?Sized + SliceDst>(len: usize) -> ptr::NonNull<S> {
201 alloc_slice_dst_in(|it| it, len)
202}
203
204/// Allocate a slice-based DST with the [global allocator][`alloc()`] within some container.
205///
206/// The returned pointer is owned and completely uninitialized;
207/// you are required to initialize it correctly.
208///
209/// Note that while this function returns a `ptr::NonNull<S>`,
210/// the pointer is to the allocation as specified by `container(S::layout(len))`,
211/// so if you want/need a pointer to `S`, you will need to offset it.
212///
213/// If the layout to be allocated has zero size,
214/// then an arbitrary aligned dangling nonnull pointer is returned.
215pub fn alloc_slice_dst_in<S: ?Sized + SliceDst, F>(container: F, len: usize) -> ptr::NonNull<S>
216where
217 F: FnOnce(Layout) -> Layout,
218{
219 let layout = container(S::layout_for(len));
220 unsafe {
221 let ptr = if layout.size() == 0 {
222 // Do not allocate in the ZST case! CAD97/pointer-utils#23
223 ptr::NonNull::new(polyfill::ptr_dangling_at(layout.align()))
224 } else {
225 ptr::NonNull::new(alloc(layout) as *mut ())
226 }
227 .unwrap_or_else(|| handle_alloc_error(layout));
228 let ptr = ptr::NonNull::new_unchecked(ptr::slice_from_raw_parts_mut(ptr.as_ptr(), len));
229 S::retype(ptr)
230 }
231}
232
233/// Types that can allocate a custom slice DST within them.
234///
235/// # Implementation note
236///
237/// For most types, [`TryAllocSliceDst`] should be the implementation primitive.
238/// This trait can then be implemented in terms of `TryAllocSliceDst`:
239///
240/// ```rust
241/// # use {slice_dst::*, std::ptr};
242/// # struct Container<T: ?Sized>(Box<T>);
243/// # unsafe impl<S: ?Sized + SliceDst> TryAllocSliceDst<S> for Container<S> {
244/// # unsafe fn try_new_slice_dst<I, E>(len: usize, init: I) -> Result<Self, E>
245/// # where I: FnOnce(ptr::NonNull<S>) -> Result<(), E>
246/// # { unimplemented!() }
247/// # }
248/// unsafe impl<S: ?Sized + SliceDst> AllocSliceDst<S> for Container<S> {
249/// unsafe fn new_slice_dst<I>(len: usize, init: I) -> Self
250/// where
251/// I: FnOnce(ptr::NonNull<S>),
252/// {
253/// enum Void {} // or never (!) once it is stable
254/// #[allow(clippy::unit_arg)]
255/// let init = |ptr| Ok::<(), Void>(init(ptr));
256/// match Self::try_new_slice_dst(len, init) {
257/// Ok(a) => a,
258/// Err(void) => match void {},
259/// }
260/// }
261/// }
262/// ```
263///
264/// This is not a blanket impl due to coherence rules; if the blanket impl were present,
265/// it would be impossible to implement `AllocSliceDst` instead of `TryAllocSliceDst`.
266///
267/// # Safety
268///
269/// Must be implemented as described and may be relied upon by generic code.
270pub unsafe trait AllocSliceDst<S: ?Sized + SliceDst> {
271 /// Create a new custom slice DST.
272 ///
273 /// # Safety
274 ///
275 /// `init` must properly initialize the object behind the pointer.
276 /// `init` receives a fully uninitialized pointer and must not read anything before writing.
277 unsafe fn new_slice_dst<I>(len: usize, init: I) -> Self
278 where
279 I: FnOnce(ptr::NonNull<S>);
280}
281
282// FUTURE: export? Would need better generic support.
283macro_rules! impl_alloc_by_try_alloc {
284 ($T:ident) => {
285 unsafe impl<S: ?Sized + SliceDst> $crate::AllocSliceDst<S> for $T<S> {
286 unsafe fn new_slice_dst<I>(len: usize, init: I) -> Self
287 where
288 I: FnOnce(::core::ptr::NonNull<S>),
289 {
290 enum Void {}
291 #[allow(clippy::unit_arg)]
292 let init = |ptr| ::core::result::Result::<(), Void>::Ok(init(ptr));
293 match <Self as $crate::TryAllocSliceDst<S>>::try_new_slice_dst(len, init) {
294 Ok(a) => a,
295 Err(void) => match void {},
296 }
297 }
298 }
299 };
300}
301
302/// Types that can allocate a custom slice DST within them,
303/// given a fallible initialization function.
304///
305/// # Safety
306///
307/// Must be implemented as described and may be relied upon by generic code.
308pub unsafe trait TryAllocSliceDst<S: ?Sized + SliceDst>: AllocSliceDst<S> + Sized {
309 /// Create a new custom slice DST with a fallible initialization function.
310 ///
311 /// # Safety
312 ///
313 /// `init` must properly initialize the object behind the pointer.
314 /// `init` receives a fully uninitialized pointer and must not read anything before writing.
315 ///
316 /// If the initialization closure panics or returns an error,
317 /// the allocated place will be deallocated but not dropped.
318 /// To clean up the partially initialized type, we suggest
319 /// proxying creation through scope guarding types.
320 unsafe fn try_new_slice_dst<I, E>(len: usize, init: I) -> Result<Self, E>
321 where
322 I: FnOnce(ptr::NonNull<S>) -> Result<(), E>;
323}
324
325// SAFETY: Box is guaranteed to be allocatable by GlobalAlloc.
326impl_alloc_by_try_alloc!(Box);
327unsafe impl<S: ?Sized + SliceDst> TryAllocSliceDst<S> for Box<S> {
328 unsafe fn try_new_slice_dst<I, E>(len: usize, init: I) -> Result<Self, E>
329 where
330 I: FnOnce(ptr::NonNull<S>) -> Result<(), E>,
331 {
332 struct RawBox<S: ?Sized + SliceDst>(ptr::NonNull<S>, Layout);
333
334 impl<S: ?Sized + SliceDst> RawBox<S> {
335 unsafe fn new(len: usize) -> Self {
336 let layout = S::layout_for(len);
337 RawBox(alloc_slice_dst(len), layout)
338 }
339
340 unsafe fn finalize(self) -> Box<S> {
341 let this = ManuallyDrop::new(self);
342 Box::from_raw(this.0.as_ptr())
343 }
344 }
345
346 impl<S: ?Sized + SliceDst> Drop for RawBox<S> {
347 fn drop(&mut self) {
348 unsafe {
349 dealloc(self.0.as_ptr().cast(), self.1);
350 }
351 }
352 }
353
354 let ptr = RawBox::new(len);
355 init(ptr.0)?;
356 Ok(ptr.finalize())
357 }
358}
359
360// SAFETY: just delegates to `Box`'s implementation (for now?)
361impl_alloc_by_try_alloc!(Rc);
362unsafe impl<S: ?Sized + SliceDst> TryAllocSliceDst<S> for Rc<S> {
363 unsafe fn try_new_slice_dst<I, E>(len: usize, init: I) -> Result<Self, E>
364 where
365 I: FnOnce(ptr::NonNull<S>) -> Result<(), E>,
366 {
367 Box::try_new_slice_dst(len, init).map(Into::into)
368 }
369}
370
371// SAFETY: just delegates to `Box`'s implementation (for now?)
372impl_alloc_by_try_alloc!(Arc);
373unsafe impl<S: ?Sized + SliceDst> TryAllocSliceDst<S> for Arc<S> {
374 unsafe fn try_new_slice_dst<I, E>(len: usize, init: I) -> Result<Self, E>
375 where
376 I: FnOnce(ptr::NonNull<S>) -> Result<(), E>,
377 {
378 Box::try_new_slice_dst(len, init).map(Into::into)
379 }
380}
381
382pub(crate) mod polyfill;
383mod provided_types;
384
385pub use provided_types::{SliceWithHeader, StrWithHeader};