stack_dst/
lib.rs

1//! Support for storing dynamically-sized types within fixed-size allocations
2//!
3//! - The `Value` type provides a fixed size (7 word in the current version) buffer in which a trait object
4//!   or array can be stored, without resorting to a heap allocation.
5//! - The `Fifo` and `Stack` types provide collection types (first-in-first-out and last-in-first-out).
6//!
7//! # Examples
8//! ## An unboxed any
9//! As a quick example - The following wraps a 64-bit integer up in an inline DST using the Any trait.
10//!
11//! ```rust
12//! # use std::any::Any;
13//! # use stack_dst::Value;
14//! #
15//! let dst = Value::<dyn Any, ::stack_dst::buffers::Ptr2>::new_stable(1234u64, |p| p as _)
16//!     .ok().expect("Integer did not fit in allocation");
17//! println!("dst as u64 = {:?}", dst.downcast_ref::<u64>());
18//! println!("dst as i8 = {:?}", dst.downcast_ref::<i8>());
19//! ```
20//!
21//! ## Stack-allocated closure!
22//! The following snippet shows how small (`'static`) closures can be returned using this crate
23//!
24//! ```rust
25//! # use stack_dst::Value;
26//! #
27//! fn make_closure(value: u64) -> Value<dyn FnMut()->String, ::stack_dst::array_buf![u64; U2]> {
28//!     Value::new_stable(move || format!("Hello there! value={}", value), |p| p as _)
29//!         .ok().expect("Closure doesn't fit")
30//! }
31//! let mut closure = make_closure(666);
32//! assert_eq!( (&mut *closure)(), "Hello there! value=666" );
33//! ```
34//!
35//! ## Custom allocation sizes/types
36//! If you need larger alignment, you can use a different type for the backing array. (Note, that metadata uses at least one slot in the array)
37//!
38//! This code panics, because i128 requires 8/16 byte alignment (usually)
39//! ```should_panic
40//! # use stack_dst::Value;
41//! # use std::any::Any;
42//! let v: Value<dyn Any, ::stack_dst::buffers::U8_32> = Value::new_stable(123i128, |p| p as _).unwrap();
43//! ```
44//! This works, because the backing buffer has sufficient alignment
45//! ```rust
46//! # use stack_dst::Value;
47//! # use std::any::Any;
48//! let v: Value<dyn Any, ::stack_dst::array_buf![u128; U2]> = Value::new_stable(123i128, |p| p as _).unwrap();
49//! ```
50//!
51//! # Feature flags
52//! ## `alloc` (default)
53//! Provides the `StackDstA::new_or_boxed` method (if `unsize` feature is active too)
54//! ## `const_generics` (default)
55//! Uses value/constant generics to provide a slightly nicer API (e.g. [ValueU])
56//! ## `unsize` (optional)
57//! Uses the nightly feature `unsize` to provide a more egonomic API (no need for the `|p| p` closures)
58// //! ## `full_const_generics` (optional)
59// //! Uses extended const generics to give compile time alignment errors
60//!
61#![cfg_attr(feature = "unsize", feature(unsize))] // needed for Unsize
62#![cfg_attr(
63    feature = "full_const_generics",
64    feature(generic_const_exprs)
65)]
66#![cfg_attr(feature = "full_const_generics", allow(incomplete_features))]
67#![no_std]
68#![deny(missing_docs)]
69
70use core::{mem, ptr, slice};
71use ::core::mem::MaybeUninit;
72
73// Internal helper
74type BufSlice<T> = [MaybeUninit<T>];
75
76#[cfg(miri)]
77#[macro_use]
78extern crate std;
79
80#[cfg(feature = "alloc")]
81extern crate alloc;
82
83extern crate generic_array;
84
85mod data_buf;
86pub use self::data_buf::DataBuf;
87pub use self::data_buf::Pod;
88
89pub use fifo::Fifo;
90pub use stack::Stack;
91pub use value::Value;
92
93/// Shorthand for defining a array buffer
94/// 
95/// The array size must be a typenum unsigned integer (e.g `U8`)
96/// E.g. `array_buf![u8; U32]` expands to `::stack_dst::buffers::ArrayBuf<u8, ::stack_dst::buffers::n::::U32>`
97#[macro_export]
98macro_rules! array_buf {
99    ($t:ty; $n:ident) => { $crate::buffers::ArrayBuf<$t, $crate::buffers::n::$n> }
100}
101
102/// Type aliases for common buffer sizes and types
103/// 
104/// Some useful suggestions
105/// - [Ptr8] is the semi-standard buffer for holding a single object (a good balance of space used)
106/// - [Ptr2] is suitable for storing a single pointer and its vtable
107pub mod buffers {
108    /// A re-export of `typenum` for shorter names
109    pub use ::generic_array::typenum as n;
110    pub use self::array_buf::ArrayBuf;
111    #[cfg(feature="const_generics")]
112    pub use self::cg_array_buf::ArrayBuf as ConstArrayBuf;
113
114    mod array_buf {
115        use ::core::mem::MaybeUninit;
116
117        /// A buffer backing onto an array (used to provide default)
118        pub struct ArrayBuf<T, N>
119        where
120            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
121        {
122            inner: ::generic_array::GenericArray<MaybeUninit<T>, N>,
123        }
124        impl<T, N> ::core::default::Default for ArrayBuf<T, N>
125        where
126            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
127        {
128            fn default() -> Self {
129                ArrayBuf {
130                    // `unwarp` won't fail, lengths match
131                    inner: ::generic_array::GenericArray::from_exact_iter( (0 .. N::USIZE).map(|_| MaybeUninit::uninit()) ).unwrap(),
132                }
133            }
134        }
135        unsafe impl<T,N> crate::DataBuf for ArrayBuf<T, N>
136        where
137            T: crate::Pod,
138            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
139        {
140            type Inner = T;
141            fn as_ref(&self) -> &[MaybeUninit<Self::Inner>] {
142                &self.inner
143            }
144            fn as_mut(&mut self) -> &mut [MaybeUninit<Self::Inner>] {
145                &mut self.inner
146            }
147            fn extend(&mut self, len: usize) -> Result<(), ()> {
148                if len > N::USIZE {
149                    Err( () )
150                }
151                else {
152                    Ok( () )
153                }
154            }
155        }
156    }
157
158    #[cfg(feature="const_generics")]
159    mod cg_array_buf {
160        /// A buffer backing onto an array (used to provide default) - using constant generics
161        pub struct ArrayBuf<T, const N: usize>
162        {
163            inner: [::core::mem::MaybeUninit<T>; N],
164        }
165        impl<T:, const N: usize> ::core::default::Default for ArrayBuf<T, N>
166        where
167            T: crate::Pod,
168        {
169            fn default() -> Self {
170                ArrayBuf {
171                    inner: [::core::mem::MaybeUninit::uninit(); N],
172                }
173            }
174        }
175        unsafe impl<T,const N: usize> crate::DataBuf for ArrayBuf<T, N>
176        where
177            T: crate::Pod,
178        {
179            type Inner = T;
180            fn as_ref(&self) -> &[::core::mem::MaybeUninit<Self::Inner>] {
181                &self.inner
182            }
183            fn as_mut(&mut self) -> &mut [::core::mem::MaybeUninit<Self::Inner>] {
184                &mut self.inner
185            }
186            fn extend(&mut self, len: usize) -> Result<(), ()> {
187                if len > N {
188                    Err( () )
189                }
190                else {
191                    Ok( () )
192                }
193            }
194        }
195    }
196
197    /// 8 pointers (32/64 bytes, with pointer alignment)
198    pub type Ptr8 = ArrayBuf<*const (), n::U8>;
199    /// 64 bytes, 64-bit alignment
200    pub type U64_8 = ArrayBuf<u64, n::U8>;
201    /// 32 bytes, 8-bit alignment
202    pub type U8_32 = ArrayBuf<u8, n::U32>;
203
204    /// 16 bytes, 64-bit alignment
205    pub type U64_2 = ArrayBuf<u64, n::U2>;
206    
207    /// 16 pointers (64/128 bytes, with pointer alignment)
208    pub type Ptr16 = ArrayBuf<*const (), n::U16>;
209    
210    /// Two pointers, useful for wrapping a pointer along with a vtable
211    pub type Ptr2 = ArrayBuf<*const (), n::U2>;
212    /// One pointer, can only store the vtable
213    pub type Ptr1 = ArrayBuf<*const (), n::U1>;
214
215    /// Dyanamically allocated buffer with 8-byte alignment
216    #[cfg(feature="alloc")]
217    pub type U64Vec = ::alloc::vec::Vec<::core::mem::MaybeUninit<u64>>;
218    /// Dyanamically allocated buffer with 1-byte alignment
219    #[cfg(feature="alloc")]
220    pub type U8Vec = ::alloc::vec::Vec<::core::mem::MaybeUninit<u8>>;
221    /// Dyanamically allocated buffer with pointer alignment
222    #[cfg(feature="alloc")]
223    pub type PtrVec = ::alloc::vec::Vec<::core::mem::MaybeUninit<*const ()>>;
224}
225
226/// Implementation of the FIFO list structure
227pub mod fifo;
228/// Implementation of the LIFO stack structure
229pub mod stack;
230/// Implementation of the single-value structure
231pub mod value;
232
233#[cfg(feature = "const_generics")]
234/// A single dynamically-sized value stored in a `usize` aligned buffer
235/// 
236/// ```
237/// let v = ::stack_dst::ValueU::<[u8], 16>::new_stable([1,2,3], |v| v);
238/// ```
239pub type ValueU<T /*: ?Sized*/, const N: usize /* = {8+1}*/> = Value<T, buffers::ConstArrayBuf<usize, N>>;
240#[cfg(feature = "const_generics")]
241/// A single LIFO stack of DSTs using a `usize` aligned buffer
242/// 
243/// ```
244/// let mut stack = ::stack_dst::StackU::<[u8], 16>::new();
245/// stack.push_copied(&[1]);
246/// ```
247pub type StackU<T /*: ?Sized*/, const N: usize /* = 16*/> = Stack<T, buffers::ConstArrayBuf<usize, N>>;
248#[cfg(feature = "const_generics")]
249/// A FIFO queue of DSTs using a `usize` aligned buffer
250/// 
251/// ```
252/// let mut queue = ::stack_dst::FifoU::<[u8], 16>::new();
253/// queue.push_copied(&[1]);
254/// ```
255pub type FifoU<T /*: ?Sized*/, const N: usize /* = {8+1}*/> = Fifo<T, buffers::ConstArrayBuf<usize, N>>;
256
257fn decompose_pointer<T: ?Sized>(mut ptr: *const T) -> (*const (), usize, [usize; 3]) {
258    let addr = ptr as *const ();
259    let rv = mem_as_slice(&mut ptr);
260    let mut vals = [0; 3];
261    assert!(
262        rv[0] == addr as usize,
263        "BUG: Pointer layout is not (data_ptr, info...)"
264    );
265    vals[..rv.len()-1].copy_from_slice(&rv[1..]);
266    (addr, rv.len()-1, vals,)
267}
268
269fn mem_as_slice<T>(ptr: &mut T) -> &mut [usize] {
270    assert!(mem::size_of::<T>() % mem::size_of::<usize>() == 0);
271    assert!(mem::align_of::<T>() % mem::align_of::<usize>() == 0);
272    let words = mem::size_of::<T>() / mem::size_of::<usize>();
273    // SAFE: Points to valid memory (a raw pointer)
274    unsafe { slice::from_raw_parts_mut(ptr as *mut _ as *mut usize, words) }
275}
276
277/// Re-construct a fat pointer
278unsafe fn make_fat_ptr<T: ?Sized, W: Pod>(data_ptr: *mut (), meta_vals: &BufSlice<W>) -> *mut T {
279    #[repr(C)]
280    #[derive(Copy,Clone)]
281    struct Raw {
282        ptr: *const (),
283        meta: [usize; 4],
284    }
285    union Inner<T: ?Sized> {
286        ptr: *mut T,
287        raw: Raw,
288    }
289    let mut rv = Inner { raw: Raw { ptr: data_ptr, meta: [0; 4] } };
290    assert!(meta_vals.len() * mem::size_of::<W>() % mem::size_of::<usize>() == 0);
291    assert!(meta_vals.len() * mem::size_of::<W>() <= 4 * mem::size_of::<usize>());
292    ptr::copy(
293        meta_vals.as_ptr() as *const u8,
294        rv.raw.meta.as_mut_ptr() as *mut u8,
295        meta_vals.len() * mem::size_of::<W>()
296        );
297    let rv = rv.ptr;
298    assert_eq!(rv as *const (), data_ptr as *const ());
299    rv
300}
301/// Write metadata (abstraction around `ptr::copy`)
302fn store_metadata<W: Pod>(dst: &mut BufSlice<W>, meta_words: &[usize]) {
303    let n_bytes = meta_words.len() * mem::size_of::<usize>();
304    assert!(n_bytes <= dst.len() * mem::size_of::<W>(),
305        "nbytes [{}] <= dst.len() [{}] * sizeof [{}]", n_bytes, dst.len(), mem::size_of::<W>());
306    unsafe {
307        ptr::copy(
308            meta_words.as_ptr() as *const u8,
309            dst.as_mut_ptr() as *mut u8,
310            n_bytes,
311        );
312    }
313}
314
315fn round_to_words<T>(len: usize) -> usize {
316    (len + mem::size_of::<T>() - 1) / mem::size_of::<T>()
317}
318
319/// Calls a provided function to get a fat pointer version of `v` (and checks that the returned pointer is sane)
320fn check_fat_pointer<U, T: ?Sized>(v: &U, get_ref: impl FnOnce(&U) -> &T) -> &T {
321    let ptr: &T = get_ref(v);
322    assert_eq!(
323        ptr as *const _ as *const u8, v as *const _ as *const u8,
324        "MISUSE: Closure returned different pointer"
325    );
326    assert_eq!(
327        mem::size_of_val(ptr),
328        mem::size_of::<U>(),
329        "MISUSE: Closure returned a subset pointer"
330    );
331    ptr
332}
333
334/// Push items to a list using a generator function to get the items
335/// - `meta`  - Metadata slot (must be 1 usize long)
336/// - `data`  - Data slot, must be at least `count * sizeof(T)` long
337/// - `count` - Number of items to insert
338/// - `gen`   - Generator function (is passed the current index)
339/// - `reset_slot` - A slot updated with `reset_value` when a panic happens before push is complete
340/// - `reset_value` - Value used in `reset_slot`
341///
342/// This provides a panic-safe push as long as `reset_slot` and `reset_value` undo the allocation operation
343unsafe fn list_push_gen<T, W: Pod>(meta: &mut BufSlice<W>, data: &mut BufSlice<W>, count: usize, mut gen: impl FnMut(usize)->T, reset_slot: &mut usize, reset_value: usize)
344{
345    /// Helper to drop/zero all pushed items, and reset data structure state if there's a panic
346    struct PanicState<'a, T>(*mut T, usize, &'a mut usize, usize);
347    impl<'a, T> ::core::ops::Drop for PanicState<'a, T> {
348        fn drop(&mut self) {
349            if self.0.is_null() {
350                return ;
351            }
352            // Reset the state of the data structure (leaking items)
353            *self.2 = self.3;
354            // Drop all partially-populated items
355            unsafe {
356                while self.1 != 0 {
357                    ptr::drop_in_place(&mut *self.0);
358                    ptr::write_bytes(self.0 as *mut u8, 0, mem::size_of::<T>());
359                    self.0 = self.0.offset(1);
360                    self.1 -= 1;
361                }
362            }
363        }
364    }
365
366    let mut ptr = data.as_mut_ptr() as *mut T;
367    let mut clr = PanicState(ptr, 0, reset_slot, reset_value);
368    for i in 0 .. count {
369        let val = gen(i);
370        ptr::write(ptr, val);
371        ptr = ptr.offset(1);
372        clr.1 += 1;
373    }
374    clr.0 = ptr::null_mut();    // Prevent drops and prevent reset
375    // Save the length once everything has been written
376    crate::store_metadata(meta, &[count]);
377}
378
379/// Marker trait used to check alignment
380pub unsafe trait AlignmentValid {
381    #[doc(hidden)]
382    fn check();
383}
384#[cfg(feature = "full_const_generics")]
385unsafe impl<S, L> AlignmentValid for (S, L)
386where
387    [(); mem::align_of::<L>() - mem::align_of::<S>()]: Sized,
388{
389    fn check() {}
390}
391#[cfg(not(feature = "full_const_generics"))]
392unsafe impl<S, L> AlignmentValid for (S, L) {
393    fn check() {
394        assert!(
395            mem::align_of::<S>() <= mem::align_of::<L>(),
396            "TODO: Enforce alignment >{} (requires {})",
397            mem::align_of::<L>(),
398            mem::align_of::<S>()
399        );
400    }
401}
402
403/*
404#[cfg(doctest)]
405#[doc=include_str!("../README.md")]
406pub mod readme {
407}
408*/
stack_dst/lib.rs

stack_dst/
lib.rs
