vecstorage/

lib.rs

//! # `VecStorage`
//! Struct to re-use the storage of a vector for borrowing values with different lifetimes.
//!
//! ## Examples
//! The following code does not compile:
//! ```compile_fail
//! let mut v = Vec::with_capacity(2);
//! {
//!     let x = 1; let y = 2;
//!     v.push(&x);
//!     v.push(&y);
//!     v.clear(); // We stop borrowing here, but the compiler doesn't know that.
//! }
//! {
//!     let a = 1; let b = 2;
//!     v.push(&a);
//!     v.push(&b);
//!     v.clear(); // We stop borrowing here, but the compiler doesn't know that.
//! }
//! ```
//!
//! You can use [`VecStorage`] to solve this problem:
//! ```
//! use vecstorage::VecStorage;
//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
//! {
//!     let x = 1; let y = 2;
//!     let mut guard = v.vec_guard();
//!     // `guard` behaves like a `Vec<&'_ u32>` that can be used to store `&x`.
//!     guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
//!     guard.push(&y);
//!     // If we were going to push more items on the guard, we would allocate memory.
//!     // When guard goes out of scope, it is cleared.
//! }
//! {
//!     let a = 1; let b = 2;
//!     let mut guard = v.vec_guard();
//!     // Now guard behaves like a vector.
//!     // The memory from the previous run has been cleared ...
//!     assert_eq!(guard.len(), 0);
//!     // ... but the memeroy has been reused.
//!     assert_eq!(guard.capacity(), 2);
//!     guard.push(&a);
//!     guard.push(&b);
//! }
//! ```
//!
//! The [`VecStorage`] re-uses the same memory each time:
//! ```
//! use vecstorage::VecStorage;
//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
//! let capacity;
//! {
//!     let x = 1; let y = 2; let z = 3;
//!     let mut guard = v.vec_guard();
//!     guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
//!     guard.push(&y);
//!     // Let's push some more items on the guard and allocate memory:
//!     guard.push(&z);
//!     capacity = guard.capacity();
//!     assert!(capacity > 2);
//! }
//! {
//!     let mut guard = v.vec_guard::<&u32>();
//!     // The memory from the previous run has been cleared ...
//!     assert_eq!(guard.len(), 0);
//!     // ... but the capacity is kept:
//!     assert_eq!(capacity, guard.capacity());
//! }
//! ```
//!
//!
//! The following example illustrates the typical usage of [`VecStorage`].
//! ```
//! use vecstorage::VecStorage;
//!
//! struct WithLifetime<'a> {
//!     reference: &'a ()
//! }
//!
//! struct MyStruct {
//!     storage: VecStorage<WithLifetime<'static>>
//! }
//!
//! impl MyStruct {
//!     fn with_capacity(capacity: usize) -> Self {
//!         Self {
//!             storage: VecStorage::with_capacity(capacity)
//!         }
//!     }
//!     
//!     fn apply_from_iterator<'a, I, F>(&mut self, iterator: I, f: F)
//!     where I: Iterator<Item = WithLifetime<'a>>, F: Fn(&[WithLifetime<'a>]) {
//!         let mut guard = self.storage.vec_guard();
//!         for item in iterator {
//!             guard.push(item)
//!         }
//!         f(guard.as_slice());
//!     }
//! }
//! ```
//!
//!
//! [`VecStorage<T>`] allocates memory just like [`Vec<T>`].
//! Typically, `T` is chosen to have a `'static` lifetime, but you actually want a
//! a `Vec<TGuard>`, where `TGuard` is another data type that does not have a `'static` lifetime.
//! If the types `T` and `TGuard` have the same size and alignment, you can use
//! the [`VecStorage<T>`] to create a [`VecGuard<TGuard>`] with the [`vec_guard<'_, TGuard>()`] method.
//! The [`VecGuard`] uses the memory from the [`VecStorage`] and can temporarily
//! be used just like a [`Vec<TGuard>`]
//! (i.e.: it implements `Deref<Target=Vec<TGuard>>` and `DerefMut<Target=Vec<TGuard>>`).
//!
//! When the [`VecGuard`] is dropped, the vector is cleared, but
//! the memory "goes back to the [`VecStorage`]" and
//! can be re-used later on to store references with a different lifetime.
use std::ffi::c_void;
use std::marker::PhantomData;
use std::mem;
use std::ops::Deref;
use std::ops::DerefMut;

/// Re-usable memory for creating a vector of references.
///
/// See the [module-level documentation] for more information.
///
/// [module-level documentation]: ./index.html
#[derive(Debug)]
pub struct VecStorage<T> {
    ptr: *mut c_void,
    capacity: usize,
    // The borrow system already ensures that there cannot be two `VecGuard`'s of
    // the same `VecStorage`, but when a `VecGuard` is "mem::forgotten", it cannot
    // cleanup, so we use this field to ensure that no new `VecGuard` can be created
    // if the previous one is "mem::forgotten".
    is_locked: bool,
    phantom: PhantomData<T>,
}

unsafe impl<T> Send for VecStorage<T> where T: Send {}
unsafe impl<T> Sync for VecStorage<T> where T: Sync {}

/// This can be used as a vector of `T` ([`Vec<T>`]).
///
/// See the [module-level documentation] for more information.
///
/// [module-level documentation]: ./index.html
pub struct VecGuard<'s, TOrig, T> {
    storage: &'s mut VecStorage<TOrig>,
    borrow: Vec<T>,
}

impl<'s, TOrig, T> Deref for VecGuard<'s, TOrig, T> {
    type Target = Vec<T>;

    fn deref(&self) -> &Vec<T> {
        &self.borrow
    }
}

impl<'s, TOrig, T> DerefMut for VecGuard<'s, TOrig, T> {
    fn deref_mut(&mut self) -> &mut Vec<T> {
        &mut self.borrow
    }
}

impl<'s, TOrig, T> Drop for VecGuard<'s, TOrig, T> {
    fn drop(&mut self) {
        self.borrow.clear();
        self.storage.ptr = self.borrow.as_mut_ptr() as *mut c_void;
        debug_assert_eq!(self.borrow.len(), 0);
        self.storage.capacity = self.borrow.capacity();

        // `drop` is always called recursively,
        // see https://doc.rust-lang.org/nomicon/destructors.html
        // So we have to manually drop `self.borrow`.
        // We cannot simply "move out of borrowed content",
        // so we swap it with another vector.
        // Note: `Vec::new()` does not allocate.
        let mut v = Vec::new();
        mem::swap(&mut v, &mut self.borrow);
        mem::forget(v);

        self.storage.is_locked = false;
    }
}

impl<T> VecStorage<T> {
    /// Create a new [`VecStorage<T>`] with the provided capacity.
    ///
    /// # Example
    /// ```
    /// use vecstorage::VecStorage;
    ///
    /// let storage = VecStorage::<u32>::with_capacity(5);
    /// assert_eq!(storage.capacity(), 5);
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        let mut vector: Vec<T> = Vec::with_capacity(capacity);
        debug_assert_eq!(vector.len(), 0);
        let result = Self {
            is_locked: false,
            ptr: vector.as_mut_ptr() as *mut c_void,
            capacity: vector.capacity(),
            phantom: PhantomData,
        };
        mem::forget(vector);
        result
    }

    /// Get the capacity of the [`VecStorage`].
    ///
    /// # Example
    /// ```
    /// use vecstorage::VecStorage;
    ///
    /// let storage = VecStorage::<u32>::with_capacity(5);
    /// assert_eq!(storage.capacity(), 5);
    /// ```
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Creates a new [`VecGuard`] using the memory allocated by `self`.
    /// This VecGuard` will automatically clear the vector when it goes out of scope.
    ///
    /// # Panics
    /// Panics if `TGuard` doesn't have the same size and alignment as `T`.
    ///
    /// Panics if `mem::forget()` was called on a [`VecGuard`]
    /// that was created previously on the same [`VecStorage`].
    ///
    /// # Example
    /// ```
    /// use vecstorage::VecStorage;
    ///
    /// let mut storage = VecStorage::<u32>::with_capacity(2);
    /// {
    ///    let mut guard = storage.vec_guard();
    ///    assert_eq!(guard.capacity(), 2);
    ///    assert_eq!(guard.len(), 0);
    ///    guard.push(3);
    ///    guard.push(2);
    ///}
    ///{
    ///    let mut guard = storage.vec_guard::<u32>();
    ///    assert_eq!(guard.capacity(), 2); // The memory of the `storage` is reused
    ///    assert_eq!(guard.len(), 0);      // But its contents has been "cleared".
    ///}
    ///```
    pub fn vec_guard<'s, TGuard>(&'s mut self) -> VecGuard<'s, T, TGuard> {
        // If `mem::forget()` was called on the guard, then
        // the `drop()` on the guard did not run and
        // the ptr and the capacity of the underlying vector may not be
        // correct anymore.
        // It is then undefined behaviour to use `Vec::from_raw_parts`.
        // Hence this check.
        if self.is_locked {
            panic!(
                "`VecStorage` has been locked. \
                 Probably `mem::forget()` was called on a `VecGuard`."
            );
        }
        use std::alloc::Layout;
        if Layout::new::<TGuard>() != Layout::new::<T>() {
            panic!(
                "The data type of the guard must have the same size and alignment \
                 as the data type of the `VecStorage`."
            );
        }
        self.is_locked = true;

        let vector;
        unsafe { vector = Vec::from_raw_parts(self.ptr as *mut TGuard, 0, self.capacity) }
        VecGuard {
            borrow: vector,
            storage: self,
        }
    }
}

impl<T> Drop for VecStorage<T> {
    fn drop(&mut self) {
        if !self.is_locked {
            unsafe {
                mem::drop(Vec::from_raw_parts(self.ptr as *mut T, 0, self.capacity));
            }
        } else {
            // If `mem::forget()` was called on a guard, then
            // the `drop()` on the guard did not run and
            // the ptr and the capacity of the underlying vector may not be
            // correct anymore.
            // It is probably not a good idea to panic inside the `drop()` function,
            // so let's just leak some memory (`mem::forget()` was called after all.)
            // We do nothing in this `else` branch.
        }
    }
}

#[test]
#[should_panic(
    expected = "`VecStorage` has been locked. Probably `mem::forget()` was called on a `VecGuard`"
)]
fn mem_forgetting_guard_leads_to_panic_with_new_guard() {
    let mut v = VecStorage::<&u32>::with_capacity(2);
    {
        let x = 1;
        let mut guard = v.vec_guard();
        guard.push(&x);
        // You should not do the following:
        mem::forget(guard);
    }
    {
        let _guard = v.vec_guard::<&u32>();
    }
}

#[test]
#[should_panic(
    expected = "The data type of the guard must have the same size and alignment \
                as the data type of the `VecStorage`."
)]
fn creating_guard_with_different_size_gives_leads_to_panic() {
    let mut v = VecStorage::<u32>::with_capacity(2);
    let _guard = v.vec_guard::<u64>();
}

#[test]
fn mem_forgetting_guard_does_not_lead_to_panic() {
    let mut v = VecStorage::<&u32>::with_capacity(2);
    {
        let x = 1;
        let mut guard = v.vec_guard();
        guard.push(&x);
        // You should not do the following:
        mem::forget(guard);
    }
    // The `VecStorage` is dropped and this should not lead to a panic.
}

#[test]
fn vec_storage_mut_common_use_cases() {
    let capacity;
    let mut v = VecStorage::<&u32>::with_capacity(2);
    {
        let mut x = 1;
        let mut y = 2;
        let mut z = 3;
        let mut guard = v.vec_guard();
        assert_eq!(guard.capacity(), 2);
        assert_eq!(guard.len(), 0);
        guard.push(&mut x);
        guard.push(&mut y);
        guard.push(&mut z);
        capacity = guard.capacity();
    }
    {
        let mut a = 1;
        let mut b = 2;
        let mut guard = v.vec_guard();
        assert_eq!(guard.len(), 0);
        assert_eq!(capacity, guard.capacity());
        guard.push(&mut a);
        guard.push(&mut b);
    }
}

#[cfg(test)]
fn impls_send<T: Send>() {}

#[test]
fn vecstorage_implements_send() {
    impls_send::<VecStorage<u32>>();
}

#[cfg(test)]
fn impls_sync<T: Sync>() {}

#[test]
fn vecstorage_implements_sync() {
    impls_sync::<VecStorage<u32>>();
}