ixa/data_structures/
value_vec.rs

1/*!
2`ValueVec<T>`: a by-value, ref-less vector with interior mutability.
3
4You can convert to and from a `Vec<T>` at zero cost.
5
6Key properties:
7- All mutating operations use `&self` (immutable receiver).
8- No references to elements are ever given out.
9- Elements are inserted/removed/moved **by value**.
10- Getting a value returns a `Clone` (or `Copy`) of the stored element.
11- Many shared immutable references to a `ValueVec` can exist simultaneously safely.
12
13Trade-offs:
14- You can’t borrow into the backing memory; you pay cloning cost to read.
15- In return, the backing storage may reallocate at will without invalidating
16  any external references (because none are ever issued).
17
18Functionality:
19
20For any functionality of `Vec<T>` that `ValueVec<T>` doesn't provide,
21you can use `into_vec` to convert to a `Vec<T>` at zero cost.
22
23Soundness:
24
25We require `T` to be `Copy` to avoid subtle soundness issues. However, this requirement
26could be replaced with a requirement that prevents re-entrance into methods of
27`ValueVec<T>` (directly or indirectly) from the `Drop` or `Clone` implementations of `T`.
28
29*/
30
31use std::cell::UnsafeCell;
32use std::fmt::Debug;
33
34/**
35A by-value, `ref`-less vector with interior mutability. Values of type `V` can be moved into and out of the vector. We require `V` to be `Copy` to avoid subtle soundness issues.
36*/
37pub struct ValueVec<V: Copy> {
38    data: UnsafeCell<Vec<V>>,
39}
40
41impl<V: Copy> ValueVec<V> {
42    /// Creates an empty `ValueVec`.
43    #[must_use]
44    pub fn new() -> Self {
45        Self {
46            data: UnsafeCell::new(Vec::new()),
47        }
48    }
49
50    /// Creates with capacity.
51    #[must_use]
52    pub fn with_capacity(cap: usize) -> Self {
53        Self {
54            data: UnsafeCell::new(Vec::with_capacity(cap)),
55        }
56    }
57
58    /// Current number of elements.
59    #[inline]
60    #[must_use]
61    pub fn len(&self) -> usize {
62        // Safety: This is already an immutable operation
63        unsafe { (&*self.data.get()).len() }
64    }
65
66    /// Current capacity of the backing Vec.
67    #[inline]
68    #[must_use]
69    pub fn capacity(&self) -> usize {
70        // Safety: This is already an immutable operation
71        unsafe { (&*self.data.get()).capacity() }
72    }
73
74    /// Returns true if the vector has no elements.
75    #[inline]
76    #[must_use]
77    pub fn is_empty(&self) -> bool {
78        self.len() == 0
79    }
80
81    /// Ensures capacity for at least `additional` more elements.
82    pub fn reserve(&self, additional: usize) {
83        self.with_vec(|v| v.reserve(additional));
84    }
85
86    /// Shrinks the capacity as much as possible.
87    pub fn shrink_to_fit(&self) {
88        self.with_vec(|v| v.shrink_to_fit());
89    }
90
91    /// Pushes a value (by move) onto the end.
92    pub fn push(&self, value: V) {
93        self.with_vec(|v| v.push(value));
94    }
95
96    /// Pops and **returns** the last element (by move), or `None` if empty.
97    #[must_use]
98    pub fn pop(&self) -> Option<V> {
99        self.with_vec(|v| v.pop())
100    }
101
102    /// Returns the value of the element at `index`, if `index` is in range. Returns `None` if `index` is out of bounds.
103    /// This is a bounds-checked variant of [`ValueVec::at`].
104    #[must_use]
105    pub fn get(&self, index: usize) -> Option<V> {
106        unsafe { (&*self.data.get()).get(index).copied() }
107    }
108
109    /// Returns the value at `index`. Panics if `index` is out of bounds.
110    ///
111    /// Use [`ValueVec::get`] for a bounds-checked version of this method.
112    #[must_use]
113    pub fn at(&self, index: usize) -> V {
114        unsafe { (&*self.data.get())[index] }
115    }
116
117    /// Moves a value into the slot at `index`, returning the old value (via move). Panics if `index` is out of bounds.
118    #[must_use]
119    pub fn replace(&self, index: usize, value: V) -> V {
120        self.with_vec(|v| core::mem::replace(&mut v[index], value))
121    }
122
123    /// Sets the value of the slot at `index` to `value`. Panics if `index` is out of bounds.
124    pub fn set(&self, index: usize, value: V) {
125        self.with_vec(|v| v[index] = value)
126    }
127
128    /// Swaps the value at `index` with the provided one in place. Panics if `index` is out of bounds.
129    ///
130    /// The existing value ends up in `*value`.
131    pub fn swap_value(&self, index: usize, value: &mut V) {
132        self.with_vec(|v| {
133            core::mem::swap(&mut v[index], value);
134        })
135    }
136
137    /// Inserts `value` at position `index`, shifting elements to the right. Panics if `index` is out of bounds.
138    pub fn insert(&self, index: usize, value: V) {
139        self.with_vec(|v| {
140            v.insert(index, value);
141        })
142    }
143
144    /// Removes and returns the element at `index`, shifting elements left. Panics if `index` is out of bounds.
145    #[must_use]
146    pub fn remove(&self, index: usize) -> V {
147        self.with_vec(|v| v.remove(index))
148    }
149
150    /// Removes and returns the element at `index` by swapping in the last element.
151    ///
152    /// O(1) removal when order does not matter.
153    #[must_use]
154    pub fn swap_remove(&self, index: usize) -> V {
155        self.with_vec(|v| v.swap_remove(index))
156    }
157
158    /// Returns `true` if the `ValueVec` contains an element with the given value.
159    #[must_use]
160    pub fn contains(&self, value: &V) -> bool
161    where
162        V: PartialEq,
163    {
164        self.with_vec(|v| v.contains(value))
165    }
166
167    /// Clears all elements.
168    pub fn clear(&self) {
169        self.with_vec(|v| v.clear());
170    }
171
172    /// Extends the vector by moving in elements from an iterator.
173    pub fn extend<I>(&self, iter: I)
174    where
175        I: IntoIterator<Item = V>,
176    {
177        self.with_vec(|v| v.extend(iter));
178    }
179
180    pub fn resize(&self, new_len: usize, value: V) {
181        self.with_vec(|v| v.resize(new_len, value));
182    }
183
184    pub fn resize_with<F>(&self, new_len: usize, f: F)
185    where
186        F: FnMut() -> V,
187    {
188        self.with_vec(|v| v.resize_with(new_len, f));
189    }
190
191    /// Returns a **snapshot** `Vec<V>` by cloning all elements.
192    ///
193    /// Use `From<ValueVec<V>> for Vec<V>` for a zero-cost conversion if you don't want to clone.
194    #[must_use]
195    pub fn to_vec(&self) -> Vec<V>
196    where
197        V: Clone,
198    {
199        unsafe { (&*self.data.get()).clone() }
200    }
201
202    /// Applies `f` with exclusive access to the inner Vec.
203    ///
204    /// **Safety:** `with_vec` temporarily obtains an exclusive `&mut Vec<V>`
205    /// from the internal `UnsafeCell` and passes it to the provided closure.
206    /// This is considered sound **only under controlled internal use**:
207    ///
208    /// - The mutable borrow does not escape the function.
209    /// - No references to elements are ever returned or stored; all access
210    ///   to elements occurs by value (move or clone).
211    /// - Only one mutable borrow of the internal `Vec` exists at a time,
212    ///   and it ends before the method returns.
213    ///
214    /// The one additional requirement for soundness is that the closure
215    /// passed to `with_vec` must not re-enter any other `ValueVec` method
216    /// (directly or indirectly) while it holds the mutable borrow. Such
217    /// re-entrancy could occur, for example, from a user-defined `Drop` or
218    /// `Clone` implementation of `V` that calls back into the same instance,
219    /// and would cause overlapping borrows of the internal `Vec`, leading to
220    /// undefined behavior.
221    ///
222    /// This function remains private to ensure that every closure passed to
223    /// it is under our control and has been manually verified to uphold the
224    /// no-reentrancy invariant. Its soundness depends on that internal
225    /// discipline.
226    #[inline]
227    fn with_vec<R>(&self, f: impl FnOnce(&mut Vec<V>) -> R) -> R {
228        // SAFETY: `UnsafeCell` permits obtaining a unique mutable reference here.
229        // We never let any references escape, and we serialize access by construction
230        // (each method call performs one short-lived exclusive borrow of the Vec).
231        let vec: &mut Vec<V> = unsafe { &mut *self.data.get() };
232        f(vec)
233    }
234}
235
236impl<V: Copy> Default for ValueVec<V> {
237    fn default() -> Self {
238        Self::new()
239    }
240}
241
242impl<V: Copy + Debug> Debug for ValueVec<V> {
243    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
244        // SAFETY: We create a temporary shared reference to the inner Vec.
245        // No mutable borrows of the Vec exist concurrently by design.
246        let vec = unsafe { &*self.data.get() };
247        vec.fmt(f)
248    }
249}
250
251impl<V: Copy> From<Vec<V>> for ValueVec<V> {
252    /// Wraps an existing `Vec` without copying its elements.
253    fn from(src: Vec<V>) -> Self {
254        Self {
255            data: UnsafeCell::new(src),
256        }
257    }
258}
259
260impl<V: Copy> From<ValueVec<V>> for Vec<V> {
261    fn from(val: ValueVec<V>) -> Self {
262        val.data.into_inner()
263    }
264}
265
266impl<V: Copy> IntoIterator for ValueVec<V> {
267    type Item = V;
268    type IntoIter = std::vec::IntoIter<V>;
269
270    fn into_iter(self) -> Self::IntoIter {
271        // SAFETY: We are consuming `self`, so there can be no remaining references
272        // to the inner Vec. It is therefore safe to move it out of the UnsafeCell.
273        let vec = self.data.into_inner();
274        vec.into_iter()
275    }
276}
277
278impl<V: Copy> FromIterator<V> for ValueVec<V> {
279    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
280        Self::from(Vec::from_iter(iter))
281    }
282}
283
284#[cfg(test)]
285mod tests {
286    use super::ValueVec;
287
288    #[test]
289    fn push_pop() {
290        let v = ValueVec::new();
291        assert!(v.is_empty());
292        v.push(1);
293        v.push(2);
294        v.push(3);
295        assert_eq!(v.len(), 3);
296        assert_eq!(v.pop(), Some(3));
297        assert_eq!(v.pop(), Some(2));
298        assert_eq!(v.pop(), Some(1));
299        assert_eq!(v.pop(), None);
300    }
301
302    #[test]
303    fn capacity_reserve_and_shrink_to_fit() {
304        let v = ValueVec::with_capacity(4);
305        assert!(v.capacity() >= 4);
306
307        v.reserve(16);
308        assert!(v.capacity() >= 16);
309
310        v.extend([1, 2]);
311        v.shrink_to_fit();
312        assert!(v.capacity() >= v.len());
313    }
314
315    #[test]
316    fn get_cloned_and_replace() {
317        let v = ValueVec::new();
318        v.extend([10, 20, 30]);
319        assert_eq!(v.get(1), Some(20));
320        assert_eq!(v.replace(1, 99), 20);
321        assert_eq!(v.get(1), Some(99));
322    }
323
324    #[test]
325    fn set_swap_contains_clear_and_resize() {
326        let v = ValueVec::default();
327        assert!(v.is_empty());
328
329        v.resize(3, 7);
330        assert_eq!(v.to_vec(), vec![7, 7, 7]);
331
332        v.set(1, 9);
333        assert_eq!(v.at(1), 9);
334
335        let mut replacement = 42;
336        v.swap_value(1, &mut replacement);
337        assert_eq!(v.at(1), 42);
338        assert_eq!(replacement, 9);
339
340        assert!(v.contains(&42));
341        assert!(!v.contains(&9));
342
343        let mut next = 0;
344        v.resize_with(5, || {
345            next += 1;
346            next
347        });
348        assert_eq!(v.to_vec(), vec![7, 42, 7, 1, 2]);
349
350        v.clear();
351        assert!(v.is_empty());
352    }
353
354    #[test]
355    fn insert_and_remove() {
356        let v = ValueVec::new();
357        v.extend([1, 2, 3]);
358        v.insert(1, 9); // [1, 9, 2, 3]
359        assert_eq!(v.len(), 4);
360        assert_eq!(v.remove(2), 2); // [1, 9, 3]
361        assert_eq!(v.get(0), Some(1));
362        assert_eq!(v.at(1), 9);
363        assert_eq!(v.at(2), 3);
364        assert_eq!(v.remove(1), 9);
365    }
366
367    #[test]
368    fn swap_remove_works() {
369        let v = ValueVec::new();
370        v.extend([10, 20, 30, 40]);
371        let got = v.swap_remove(1);
372        assert_eq!(got, 20);
373        // Order not guaranteed after swap_remove, but len decreased:
374        assert_eq!(v.len(), 3);
375        let snapshot = v.to_vec();
376        assert!(snapshot.contains(&10));
377        assert!(snapshot.contains(&30));
378        assert!(snapshot.contains(&40));
379        assert!(!snapshot.contains(&20));
380
381        let v: Vec<i32> = v.into();
382        assert_eq!(snapshot, v);
383    }
384
385    #[test]
386    fn to_vec_clone_snapshot() {
387        let v = ValueVec::new();
388        v.extend(["a", "b"]);
389        let snap = v.to_vec();
390        assert_eq!(snap, vec!["a", "b"]);
391        // Mutate original; snapshot unaffected.
392        v.push("c");
393        assert_eq!(v.len(), 3);
394        assert_eq!(snap.len(), 2);
395    }
396
397    #[test]
398    fn debug_impl() {
399        let v = ValueVec::from(vec![1, 2, 3]);
400        let s = format!("{v:?}");
401        assert!(!s.contains("ValueVec"));
402        assert!(s.contains("[1, 2, 3]"));
403    }
404
405    #[test]
406    fn from_vec_wraps_without_copy() {
407        let v = vec![1, 2, 3];
408        let vv = ValueVec::from(v);
409        // We can't check memory identity directly, but we can check content and len.
410        assert_eq!(vv.len(), 3);
411        assert_eq!(vv.at(0), 1);
412        assert_eq!(vv.at(1), 2);
413        assert_eq!(vv.at(2), 3);
414        // Original vector is consumed and cannot be used.
415    }
416
417    #[test]
418    fn into_vec_unwraps_without_copy() {
419        let vv = ValueVec::from(vec!["a", "b"]);
420        let v: Vec<_> = vv.into(); // moves out inner Vec
421        assert_eq!(v, vec!["a", "b"]);
422    }
423
424    #[test]
425    fn round_trip_from_vec_into_vec() {
426        let original = vec![10, 20, 30];
427        let vv = ValueVec::from(original);
428        let roundtrip: Vec<_> = vv.into();
429        assert_eq!(roundtrip, vec![10, 20, 30]);
430    }
431
432    #[test]
433    fn into_iterator_consumes_valuevec() {
434        let vv = ValueVec::from(vec![1, 2, 3]);
435        let collected: Vec<_> = vv.into_iter().collect();
436        assert_eq!(collected, vec![1, 2, 3]);
437    }
438
439    #[test]
440    fn into_iterator_and_into_vec_equivalence() {
441        let vv1 = ValueVec::from(vec![5, 6, 7]);
442        let vv2 = ValueVec::from(vec![5, 6, 7]);
443        let collected_from_iter: Vec<_> = vv1.into_iter().collect();
444        let collected_from_into: Vec<_> = vv2.into();
445        assert_eq!(collected_from_iter, collected_from_into);
446    }
447
448    #[test]
449    fn from_iterator_collect() {
450        let source = [1, 2, 3, 4, 5];
451        let vv: ValueVec<i32> = source.iter().copied().collect();
452        assert_eq!(vv.len(), 5);
453        assert_eq!(vv.at(0), 1);
454        assert_eq!(vv.at(4), 5);
455    }
456}
ixa/data_structures/value_vec.rs

ixa/data_structures/
value_vec.rs
