vecstorage/
lib.rs

1//! # `VecStorage`
2//! Struct to re-use the storage of a vector for borrowing values with different lifetimes.
3//!
4//! ## Examples
5//! The following code does not compile:
6//! ```compile_fail
7//! let mut v = Vec::with_capacity(2);
8//! {
9//!     let x = 1; let y = 2;
10//!     v.push(&x);
11//!     v.push(&y);
12//!     v.clear(); // We stop borrowing here, but the compiler doesn't know that.
13//! }
14//! {
15//!     let a = 1; let b = 2;
16//!     v.push(&a);
17//!     v.push(&b);
18//!     v.clear(); // We stop borrowing here, but the compiler doesn't know that.
19//! }
20//! ```
21//!
22//! You can use [`VecStorage`] to solve this problem:
23//! ```
24//! use vecstorage::VecStorage;
25//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
26//! {
27//!     let x = 1; let y = 2;
28//!     let mut guard = v.vec_guard();
29//!     // `guard` behaves like a `Vec<&'_ u32>` that can be used to store `&x`.
30//!     guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
31//!     guard.push(&y);
32//!     // If we were going to push more items on the guard, we would allocate memory.
33//!     // When guard goes out of scope, it is cleared.
34//! }
35//! {
36//!     let a = 1; let b = 2;
37//!     let mut guard = v.vec_guard();
38//!     // Now guard behaves like a vector.
39//!     // The memory from the previous run has been cleared ...
40//!     assert_eq!(guard.len(), 0);
41//!     // ... but the memeroy has been reused.
42//!     assert_eq!(guard.capacity(), 2);
43//!     guard.push(&a);
44//!     guard.push(&b);
45//! }
46//! ```
47//!
48//! The [`VecStorage`] re-uses the same memory each time:
49//! ```
50//! use vecstorage::VecStorage;
51//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
52//! let capacity;
53//! {
54//!     let x = 1; let y = 2; let z = 3;
55//!     let mut guard = v.vec_guard();
56//!     guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
57//!     guard.push(&y);
58//!     // Let's push some more items on the guard and allocate memory:
59//!     guard.push(&z);
60//!     capacity = guard.capacity();
61//!     assert!(capacity > 2);
62//! }
63//! {
64//!     let mut guard = v.vec_guard::<&u32>();
65//!     // The memory from the previous run has been cleared ...
66//!     assert_eq!(guard.len(), 0);
67//!     // ... but the capacity is kept:
68//!     assert_eq!(capacity, guard.capacity());
69//! }
70//! ```
71//!
72//!
73//! The following example illustrates the typical usage of [`VecStorage`].
74//! ```
75//! use vecstorage::VecStorage;
76//!
77//! struct WithLifetime<'a> {
78//!     reference: &'a ()
79//! }
80//!
81//! struct MyStruct {
82//!     storage: VecStorage<WithLifetime<'static>>
83//! }
84//!
85//! impl MyStruct {
86//!     fn with_capacity(capacity: usize) -> Self {
87//!         Self {
88//!             storage: VecStorage::with_capacity(capacity)
89//!         }
90//!     }
91//!     
92//!     fn apply_from_iterator<'a, I, F>(&mut self, iterator: I, f: F)
93//!     where I: Iterator<Item = WithLifetime<'a>>, F: Fn(&[WithLifetime<'a>]) {
94//!         let mut guard = self.storage.vec_guard();
95//!         for item in iterator {
96//!             guard.push(item)
97//!         }
98//!         f(guard.as_slice());
99//!     }
100//! }
101//! ```
102//!
103//!
104//! [`VecStorage<T>`] allocates memory just like [`Vec<T>`].
105//! Typically, `T` is chosen to have a `'static` lifetime, but you actually want a
106//! a `Vec<TGuard>`, where `TGuard` is another data type that does not have a `'static` lifetime.
107//! If the types `T` and `TGuard` have the same size and alignment, you can use
108//! the [`VecStorage<T>`] to create a [`VecGuard<TGuard>`] with the [`vec_guard<'_, TGuard>()`] method.
109//! The [`VecGuard`] uses the memory from the [`VecStorage`] and can temporarily
110//! be used just like a [`Vec<TGuard>`]
111//! (i.e.: it implements `Deref<Target=Vec<TGuard>>` and `DerefMut<Target=Vec<TGuard>>`).
112//!
113//! When the [`VecGuard`] is dropped, the vector is cleared, but
114//! the memory "goes back to the [`VecStorage`]" and
115//! can be re-used later on to store references with a different lifetime.
116use std::ffi::c_void;
117use std::marker::PhantomData;
118use std::mem;
119use std::ops::Deref;
120use std::ops::DerefMut;
121
122/// Re-usable memory for creating a vector of references.
123///
124/// See the [module-level documentation] for more information.
125///
126/// [module-level documentation]: ./index.html
127#[derive(Debug)]
128pub struct VecStorage<T> {
129    ptr: *mut c_void,
130    capacity: usize,
131    // The borrow system already ensures that there cannot be two `VecGuard`'s of
132    // the same `VecStorage`, but when a `VecGuard` is "mem::forgotten", it cannot
133    // cleanup, so we use this field to ensure that no new `VecGuard` can be created
134    // if the previous one is "mem::forgotten".
135    is_locked: bool,
136    phantom: PhantomData<T>,
137}
138
139unsafe impl<T> Send for VecStorage<T> where T: Send {}
140unsafe impl<T> Sync for VecStorage<T> where T: Sync {}
141
142/// This can be used as a vector of `T` ([`Vec<T>`]).
143///
144/// See the [module-level documentation] for more information.
145///
146/// [module-level documentation]: ./index.html
147pub struct VecGuard<'s, TOrig, T> {
148    storage: &'s mut VecStorage<TOrig>,
149    borrow: Vec<T>,
150}
151
152impl<'s, TOrig, T> Deref for VecGuard<'s, TOrig, T> {
153    type Target = Vec<T>;
154
155    fn deref(&self) -> &Vec<T> {
156        &self.borrow
157    }
158}
159
160impl<'s, TOrig, T> DerefMut for VecGuard<'s, TOrig, T> {
161    fn deref_mut(&mut self) -> &mut Vec<T> {
162        &mut self.borrow
163    }
164}
165
166impl<'s, TOrig, T> Drop for VecGuard<'s, TOrig, T> {
167    fn drop(&mut self) {
168        self.borrow.clear();
169        self.storage.ptr = self.borrow.as_mut_ptr() as *mut c_void;
170        debug_assert_eq!(self.borrow.len(), 0);
171        self.storage.capacity = self.borrow.capacity();
172
173        // `drop` is always called recursively,
174        // see https://doc.rust-lang.org/nomicon/destructors.html
175        // So we have to manually drop `self.borrow`.
176        // We cannot simply "move out of borrowed content",
177        // so we swap it with another vector.
178        // Note: `Vec::new()` does not allocate.
179        let mut v = Vec::new();
180        mem::swap(&mut v, &mut self.borrow);
181        mem::forget(v);
182
183        self.storage.is_locked = false;
184    }
185}
186
187impl<T> VecStorage<T> {
188    /// Create a new [`VecStorage<T>`] with the provided capacity.
189    ///
190    /// # Example
191    /// ```
192    /// use vecstorage::VecStorage;
193    ///
194    /// let storage = VecStorage::<u32>::with_capacity(5);
195    /// assert_eq!(storage.capacity(), 5);
196    /// ```
197    pub fn with_capacity(capacity: usize) -> Self {
198        let mut vector: Vec<T> = Vec::with_capacity(capacity);
199        debug_assert_eq!(vector.len(), 0);
200        let result = Self {
201            is_locked: false,
202            ptr: vector.as_mut_ptr() as *mut c_void,
203            capacity: vector.capacity(),
204            phantom: PhantomData,
205        };
206        mem::forget(vector);
207        result
208    }
209
210    /// Get the capacity of the [`VecStorage`].
211    ///
212    /// # Example
213    /// ```
214    /// use vecstorage::VecStorage;
215    ///
216    /// let storage = VecStorage::<u32>::with_capacity(5);
217    /// assert_eq!(storage.capacity(), 5);
218    /// ```
219    pub fn capacity(&self) -> usize {
220        self.capacity
221    }
222
223    /// Creates a new [`VecGuard`] using the memory allocated by `self`.
224    /// This VecGuard` will automatically clear the vector when it goes out of scope.
225    ///
226    /// # Panics
227    /// Panics if `TGuard` doesn't have the same size and alignment as `T`.
228    ///
229    /// Panics if `mem::forget()` was called on a [`VecGuard`]
230    /// that was created previously on the same [`VecStorage`].
231    ///
232    /// # Example
233    /// ```
234    /// use vecstorage::VecStorage;
235    ///
236    /// let mut storage = VecStorage::<u32>::with_capacity(2);
237    /// {
238    ///    let mut guard = storage.vec_guard();
239    ///    assert_eq!(guard.capacity(), 2);
240    ///    assert_eq!(guard.len(), 0);
241    ///    guard.push(3);
242    ///    guard.push(2);
243    ///}
244    ///{
245    ///    let mut guard = storage.vec_guard::<u32>();
246    ///    assert_eq!(guard.capacity(), 2); // The memory of the `storage` is reused
247    ///    assert_eq!(guard.len(), 0);      // But its contents has been "cleared".
248    ///}
249    ///```
250    pub fn vec_guard<'s, TGuard>(&'s mut self) -> VecGuard<'s, T, TGuard> {
251        // If `mem::forget()` was called on the guard, then
252        // the `drop()` on the guard did not run and
253        // the ptr and the capacity of the underlying vector may not be
254        // correct anymore.
255        // It is then undefined behaviour to use `Vec::from_raw_parts`.
256        // Hence this check.
257        if self.is_locked {
258            panic!(
259                "`VecStorage` has been locked. \
260                 Probably `mem::forget()` was called on a `VecGuard`."
261            );
262        }
263        use std::alloc::Layout;
264        if Layout::new::<TGuard>() != Layout::new::<T>() {
265            panic!(
266                "The data type of the guard must have the same size and alignment \
267                 as the data type of the `VecStorage`."
268            );
269        }
270        self.is_locked = true;
271
272        let vector;
273        unsafe { vector = Vec::from_raw_parts(self.ptr as *mut TGuard, 0, self.capacity) }
274        VecGuard {
275            borrow: vector,
276            storage: self,
277        }
278    }
279}
280
281impl<T> Drop for VecStorage<T> {
282    fn drop(&mut self) {
283        if !self.is_locked {
284            unsafe {
285                mem::drop(Vec::from_raw_parts(self.ptr as *mut T, 0, self.capacity));
286            }
287        } else {
288            // If `mem::forget()` was called on a guard, then
289            // the `drop()` on the guard did not run and
290            // the ptr and the capacity of the underlying vector may not be
291            // correct anymore.
292            // It is probably not a good idea to panic inside the `drop()` function,
293            // so let's just leak some memory (`mem::forget()` was called after all.)
294            // We do nothing in this `else` branch.
295        }
296    }
297}
298
299#[test]
300#[should_panic(
301    expected = "`VecStorage` has been locked. Probably `mem::forget()` was called on a `VecGuard`"
302)]
303fn mem_forgetting_guard_leads_to_panic_with_new_guard() {
304    let mut v = VecStorage::<&u32>::with_capacity(2);
305    {
306        let x = 1;
307        let mut guard = v.vec_guard();
308        guard.push(&x);
309        // You should not do the following:
310        mem::forget(guard);
311    }
312    {
313        let _guard = v.vec_guard::<&u32>();
314    }
315}
316
317#[test]
318#[should_panic(
319    expected = "The data type of the guard must have the same size and alignment \
320                as the data type of the `VecStorage`."
321)]
322fn creating_guard_with_different_size_gives_leads_to_panic() {
323    let mut v = VecStorage::<u32>::with_capacity(2);
324    let _guard = v.vec_guard::<u64>();
325}
326
327#[test]
328fn mem_forgetting_guard_does_not_lead_to_panic() {
329    let mut v = VecStorage::<&u32>::with_capacity(2);
330    {
331        let x = 1;
332        let mut guard = v.vec_guard();
333        guard.push(&x);
334        // You should not do the following:
335        mem::forget(guard);
336    }
337    // The `VecStorage` is dropped and this should not lead to a panic.
338}
339
340#[test]
341fn vec_storage_mut_common_use_cases() {
342    let capacity;
343    let mut v = VecStorage::<&u32>::with_capacity(2);
344    {
345        let mut x = 1;
346        let mut y = 2;
347        let mut z = 3;
348        let mut guard = v.vec_guard();
349        assert_eq!(guard.capacity(), 2);
350        assert_eq!(guard.len(), 0);
351        guard.push(&mut x);
352        guard.push(&mut y);
353        guard.push(&mut z);
354        capacity = guard.capacity();
355    }
356    {
357        let mut a = 1;
358        let mut b = 2;
359        let mut guard = v.vec_guard();
360        assert_eq!(guard.len(), 0);
361        assert_eq!(capacity, guard.capacity());
362        guard.push(&mut a);
363        guard.push(&mut b);
364    }
365}
366
367#[cfg(test)]
368fn impls_send<T: Send>() {}
369
370#[test]
371fn vecstorage_implements_send() {
372    impls_send::<VecStorage<u32>>();
373}
374
375#[cfg(test)]
376fn impls_sync<T: Sync>() {}
377
378#[test]
379fn vecstorage_implements_sync() {
380    impls_sync::<VecStorage<u32>>();
381}