1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
//! Support for storing dynamically-sized types within fixed-size allocations
//!
//! - The `Value` type provides a fixed size (7 word in the current version) buffer in which a trait object
//!   or array can be stored, without resorting to a heap allocation.
//! - The `Fifo` and `Stack` types provide collection types (first-in-first-out and last-in-first-out).
//!
//! # Examples
//! ## An unboxed any
//! As a quick example - The following wraps a 64-bit integer up in an inline DST using the Any trait.
//!
//! ```rust
//! # use std::any::Any;
//! # use stack_dst::Value;
//! #
//! let dst = Value::<dyn Any, ::stack_dst::buffers::Ptr2>::new_stable(1234u64, |p| p as _)
//!     .ok().expect("Integer did not fit in allocation");
//! println!("dst as u64 = {:?}", dst.downcast_ref::<u64>());
//! println!("dst as i8 = {:?}", dst.downcast_ref::<i8>());
//! ```
//!
//! ## Stack-allocated closure!
//! The following snippet shows how small (`'static`) closures can be returned using this crate
//!
//! ```rust
//! # use stack_dst::Value;
//! #
//! fn make_closure(value: u64) -> Value<dyn FnMut()->String, ::stack_dst::array_buf![u64; U2]> {
//!     Value::new_stable(move || format!("Hello there! value={}", value), |p| p as _)
//!         .ok().expect("Closure doesn't fit")
//! }
//! let mut closure = make_closure(666);
//! assert_eq!( (&mut *closure)(), "Hello there! value=666" );
//! ```
//!
//! ## Custom allocation sizes/types
//! 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)
//!
//! This code panics, because i128 requires 8/16 byte alignment (usually)
//! ```should_panic
//! # use stack_dst::Value;
//! # use std::any::Any;
//! let v: Value<dyn Any, ::stack_dst::buffers::U8_32> = Value::new_stable(123i128, |p| p as _).unwrap();
//! ```
//! This works, because the backing buffer has sufficient alignment
//! ```rust
//! # use stack_dst::Value;
//! # use std::any::Any;
//! let v: Value<dyn Any, ::stack_dst::array_buf![u128; U2]> = Value::new_stable(123i128, |p| p as _).unwrap();
//! ```
//!
//! # Feature flags
//! ## `alloc` (default)
//! Provides the `StackDstA::new_or_boxed` method (if `unsize` feature is active too)
//! ## `const_generics` (default)
//! Uses value/constant generics to provide a slightly nicer API (e.g. [ValueU])
//! ## `unsize` (optional)
//! Uses the nightly feature `unsize` to provide a more egonomic API (no need for the `|p| p` closures)
// //! ## `full_const_generics` (optional)
// //! Uses extended const generics to give compile time alignment errors
//!
#![cfg_attr(feature = "unsize", feature(unsize))] // needed for Unsize
#![cfg_attr(
    feature = "full_const_generics",
    feature(generic_const_exprs)
)]
#![cfg_attr(feature = "full_const_generics", allow(incomplete_features))]
#![no_std]
#![deny(missing_docs)]

use core::{mem, ptr, slice};
use ::core::mem::MaybeUninit;

// Internal helper
type BufSlice<T> = [MaybeUninit<T>];

#[cfg(miri)]
#[macro_use]
extern crate std;

#[cfg(feature = "alloc")]
extern crate alloc;

extern crate generic_array;

mod data_buf;
pub use self::data_buf::DataBuf;
pub use self::data_buf::Pod;

pub use fifo::Fifo;
pub use stack::Stack;
pub use value::Value;

/// Shorthand for defining a array buffer
/// 
/// The array size must be a typenum unsigned integer (e.g `U8`)
/// E.g. `array_buf![u8; U32]` expands to `::stack_dst::buffers::ArrayBuf<u8, ::stack_dst::buffers::n::::U32>`
#[macro_export]
macro_rules! array_buf {
    ($t:ty; $n:ident) => { $crate::buffers::ArrayBuf<$t, $crate::buffers::n::$n> }
}

/// Type aliases for common buffer sizes and types
/// 
/// Some useful suggestions
/// - [Ptr8] is the semi-standard buffer for holding a single object (a good balance of space used)
/// - [Ptr2] is suitable for storing a single pointer and its vtable
pub mod buffers {
    /// A re-export of `typenum` for shorter names
    pub use ::generic_array::typenum as n;
    pub use self::array_buf::ArrayBuf;
    #[cfg(feature="const_generics")]
    pub use self::cg_array_buf::ArrayBuf as ConstArrayBuf;

    mod array_buf {
        use ::core::mem::MaybeUninit;

        /// A buffer backing onto an array (used to provide default)
        pub struct ArrayBuf<T, N>
        where
            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
        {
            inner: ::generic_array::GenericArray<MaybeUninit<T>, N>,
        }
        impl<T, N> ::core::default::Default for ArrayBuf<T, N>
        where
            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
        {
            fn default() -> Self {
                ArrayBuf {
                    // `unwarp` won't fail, lengths match
                    inner: ::generic_array::GenericArray::from_exact_iter( (0 .. N::USIZE).map(|_| MaybeUninit::uninit()) ).unwrap(),
                }
            }
        }
        unsafe impl<T,N> crate::DataBuf for ArrayBuf<T, N>
        where
            T: crate::Pod,
            N: ::generic_array::ArrayLength<MaybeUninit<T>>,
        {
            type Inner = T;
            fn as_ref(&self) -> &[MaybeUninit<Self::Inner>] {
                &self.inner
            }
            fn as_mut(&mut self) -> &mut [MaybeUninit<Self::Inner>] {
                &mut self.inner
            }
            fn extend(&mut self, len: usize) -> Result<(), ()> {
                if len > N::USIZE {
                    Err( () )
                }
                else {
                    Ok( () )
                }
            }
        }
    }

    #[cfg(feature="const_generics")]
    mod cg_array_buf {
        /// A buffer backing onto an array (used to provide default) - using constant generics
        pub struct ArrayBuf<T, const N: usize>
        {
            inner: [::core::mem::MaybeUninit<T>; N],
        }
        impl<T:, const N: usize> ::core::default::Default for ArrayBuf<T, N>
        where
            T: crate::Pod,
        {
            fn default() -> Self {
                ArrayBuf {
                    inner: [::core::mem::MaybeUninit::uninit(); N],
                }
            }
        }
        unsafe impl<T,const N: usize> crate::DataBuf for ArrayBuf<T, N>
        where
            T: crate::Pod,
        {
            type Inner = T;
            fn as_ref(&self) -> &[::core::mem::MaybeUninit<Self::Inner>] {
                &self.inner
            }
            fn as_mut(&mut self) -> &mut [::core::mem::MaybeUninit<Self::Inner>] {
                &mut self.inner
            }
            fn extend(&mut self, len: usize) -> Result<(), ()> {
                if len > N {
                    Err( () )
                }
                else {
                    Ok( () )
                }
            }
        }
    }

    /// 8 pointers (32/64 bytes, with pointer alignment)
    pub type Ptr8 = ArrayBuf<*const (), n::U8>;
    /// 64 bytes, 64-bit alignment
    pub type U64_8 = ArrayBuf<u64, n::U8>;
    /// 32 bytes, 8-bit alignment
    pub type U8_32 = ArrayBuf<u8, n::U32>;

    /// 16 bytes, 64-bit alignment
    pub type U64_2 = ArrayBuf<u64, n::U2>;
    
    /// 16 pointers (64/128 bytes, with pointer alignment)
    pub type Ptr16 = ArrayBuf<*const (), n::U16>;
    
    /// Two pointers, useful for wrapping a pointer along with a vtable
    pub type Ptr2 = ArrayBuf<*const (), n::U2>;
    /// One pointer, can only store the vtable
    pub type Ptr1 = ArrayBuf<*const (), n::U1>;

    /// Dyanamically allocated buffer with 8-byte alignment
    #[cfg(feature="alloc")]
    pub type U64Vec = ::alloc::vec::Vec<::core::mem::MaybeUninit<u64>>;
    /// Dyanamically allocated buffer with 1-byte alignment
    #[cfg(feature="alloc")]
    pub type U8Vec = ::alloc::vec::Vec<::core::mem::MaybeUninit<u8>>;
    /// Dyanamically allocated buffer with pointer alignment
    #[cfg(feature="alloc")]
    pub type PtrVec = ::alloc::vec::Vec<::core::mem::MaybeUninit<*const ()>>;
}

/// Implementation of the FIFO list structure
pub mod fifo;
/// Implementation of the LIFO stack structure
pub mod stack;
/// Implementation of the single-value structure
pub mod value;

#[cfg(feature = "const_generics")]
/// A single dynamically-sized value stored in a `usize` aligned buffer
/// 
/// ```
/// let v = ::stack_dst::ValueU::<[u8], 16>::new_stable([1,2,3], |v| v);
/// ```
pub type ValueU<T /*: ?Sized*/, const N: usize /* = {8+1}*/> = Value<T, buffers::ConstArrayBuf<usize, N>>;
#[cfg(feature = "const_generics")]
/// A single LIFO stack of DSTs using a `usize` aligned buffer
/// 
/// ```
/// let mut stack = ::stack_dst::StackU::<[u8], 16>::new();
/// stack.push_copied(&[1]);
/// ```
pub type StackU<T /*: ?Sized*/, const N: usize /* = 16*/> = Stack<T, buffers::ConstArrayBuf<usize, N>>;
#[cfg(feature = "const_generics")]
/// A FIFO queue of DSTs using a `usize` aligned buffer
/// 
/// ```
/// let mut queue = ::stack_dst::FifoU::<[u8], 16>::new();
/// queue.push_copied(&[1]);
/// ```
pub type FifoU<T /*: ?Sized*/, const N: usize /* = {8+1}*/> = Fifo<T, buffers::ConstArrayBuf<usize, N>>;

fn decompose_pointer<T: ?Sized>(mut ptr: *const T) -> (*const (), usize, [usize; 3]) {
    let addr = ptr as *const ();
    let rv = mem_as_slice(&mut ptr);
    let mut vals = [0; 3];
    assert!(
        rv[0] == addr as usize,
        "BUG: Pointer layout is not (data_ptr, info...)"
    );
    vals[..rv.len()-1].copy_from_slice(&rv[1..]);
    (addr, rv.len()-1, vals,)
}

fn mem_as_slice<T>(ptr: &mut T) -> &mut [usize] {
    assert!(mem::size_of::<T>() % mem::size_of::<usize>() == 0);
    assert!(mem::align_of::<T>() % mem::align_of::<usize>() == 0);
    let words = mem::size_of::<T>() / mem::size_of::<usize>();
    // SAFE: Points to valid memory (a raw pointer)
    unsafe { slice::from_raw_parts_mut(ptr as *mut _ as *mut usize, words) }
}

/// Re-construct a fat pointer
unsafe fn make_fat_ptr<T: ?Sized, W: Pod>(data_ptr: *mut (), meta_vals: &BufSlice<W>) -> *mut T {
    #[repr(C)]
    #[derive(Copy,Clone)]
    struct Raw {
        ptr: *const (),
        meta: [usize; 4],
    }
    union Inner<T: ?Sized> {
        ptr: *mut T,
        raw: Raw,
    }
    let mut rv = Inner { raw: Raw { ptr: data_ptr, meta: [0; 4] } };
    assert!(meta_vals.len() * mem::size_of::<W>() % mem::size_of::<usize>() == 0);
    assert!(meta_vals.len() * mem::size_of::<W>() <= 4 * mem::size_of::<usize>());
    ptr::copy(
        meta_vals.as_ptr() as *const u8,
        rv.raw.meta.as_mut_ptr() as *mut u8,
        meta_vals.len() * mem::size_of::<W>()
        );
    let rv = rv.ptr;
    assert_eq!(rv as *const (), data_ptr as *const ());
    rv
}
/// Write metadata (abstraction around `ptr::copy`)
fn store_metadata<W: Pod>(dst: &mut BufSlice<W>, meta_words: &[usize]) {
    let n_bytes = meta_words.len() * mem::size_of::<usize>();
    assert!(n_bytes <= dst.len() * mem::size_of::<W>(),
        "nbytes [{}] <= dst.len() [{}] * sizeof [{}]", n_bytes, dst.len(), mem::size_of::<W>());
    unsafe {
        ptr::copy(
            meta_words.as_ptr() as *const u8,
            dst.as_mut_ptr() as *mut u8,
            n_bytes,
        );
    }
}

fn round_to_words<T>(len: usize) -> usize {
    (len + mem::size_of::<T>() - 1) / mem::size_of::<T>()
}

/// Calls a provided function to get a fat pointer version of `v` (and checks that the returned pointer is sane)
fn check_fat_pointer<U, T: ?Sized>(v: &U, get_ref: impl FnOnce(&U) -> &T) -> &T {
    let ptr: &T = get_ref(v);
    assert_eq!(
        ptr as *const _ as *const u8, v as *const _ as *const u8,
        "MISUSE: Closure returned different pointer"
    );
    assert_eq!(
        mem::size_of_val(ptr),
        mem::size_of::<U>(),
        "MISUSE: Closure returned a subset pointer"
    );
    ptr
}

/// Push items to a list using a generator function to get the items
/// - `meta`  - Metadata slot (must be 1 usize long)
/// - `data`  - Data slot, must be at least `count * sizeof(T)` long
/// - `count` - Number of items to insert
/// - `gen`   - Generator function (is passed the current index)
/// - `reset_slot` - A slot updated with `reset_value` when a panic happens before push is complete
/// - `reset_value` - Value used in `reset_slot`
///
/// This provides a panic-safe push as long as `reset_slot` and `reset_value` undo the allocation operation
unsafe 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)
{
    /// Helper to drop/zero all pushed items, and reset data structure state if there's a panic
    struct PanicState<'a, T>(*mut T, usize, &'a mut usize, usize);
    impl<'a, T> ::core::ops::Drop for PanicState<'a, T> {
        fn drop(&mut self) {
            if self.0.is_null() {
                return ;
            }
            // Reset the state of the data structure (leaking items)
            *self.2 = self.3;
            // Drop all partially-populated items
            unsafe {
                while self.1 != 0 {
                    ptr::drop_in_place(&mut *self.0);
                    ptr::write_bytes(self.0 as *mut u8, 0, mem::size_of::<T>());
                    self.0 = self.0.offset(1);
                    self.1 -= 1;
                }
            }
        }
    }

    let mut ptr = data.as_mut_ptr() as *mut T;
    let mut clr = PanicState(ptr, 0, reset_slot, reset_value);
    for i in 0 .. count {
        let val = gen(i);
        ptr::write(ptr, val);
        ptr = ptr.offset(1);
        clr.1 += 1;
    }
    clr.0 = ptr::null_mut();    // Prevent drops and prevent reset
    // Save the length once everything has been written
    crate::store_metadata(meta, &[count]);
}

/// Marker trait used to check alignment
pub unsafe trait AlignmentValid {
    #[doc(hidden)]
    fn check();
}
#[cfg(feature = "full_const_generics")]
unsafe impl<S, L> AlignmentValid for (S, L)
where
    [(); mem::align_of::<L>() - mem::align_of::<S>()]: Sized,
{
    fn check() {}
}
#[cfg(not(feature = "full_const_generics"))]
unsafe impl<S, L> AlignmentValid for (S, L) {
    fn check() {
        assert!(
            mem::align_of::<S>() <= mem::align_of::<L>(),
            "TODO: Enforce alignment >{} (requires {})",
            mem::align_of::<L>(),
            mem::align_of::<S>()
        );
    }
}

/*
#[cfg(doctest)]
#[doc=include_str!("../README.md")]
pub mod readme {
}
*/