safe_bump/
lib.rs

1//! Safe bump-pointer arena allocator.
2//!
3//! `safe-bump` provides a typed arena allocator built entirely with safe Rust
4//! (zero `unsafe` blocks). Values are allocated by appending to an internal
5//! buffer and accessed via stable [`Idx<T>`] indices.
6//!
7//! # Key properties
8//!
9//! - **Zero `unsafe`**: enforced by `#![forbid(unsafe_code)]`
10//! - **Auto [`Drop`]**: destructors run on reset, rollback, and arena drop
11//! - **Checkpoint/rollback**: save state and discard speculative allocations
12//! - **O(1) amortized allocation**: backed by [`Vec::push`]
13//! - **O(1) index access**: direct indexing into backing storage
14//!
15//! # Example
16//!
17//! ```
18//! use safe_bump::{Arena, Idx};
19//!
20//! let mut arena: Arena<String> = Arena::new();
21//! let a: Idx<String> = arena.alloc(String::from("hello"));
22//! let b: Idx<String> = arena.alloc(String::from("world"));
23//!
24//! assert_eq!(arena[a], "hello");
25//! assert_eq!(arena[b], "world");
26//! assert_eq!(arena.len(), 2);
27//!
28//! // Checkpoint and rollback
29//! let cp = arena.checkpoint();
30//! let _tmp = arena.alloc(String::from("temporary"));
31//! assert_eq!(arena.len(), 3);
32//!
33//! arena.rollback(cp); // "temporary" is dropped
34//! assert_eq!(arena.len(), 2);
35//! ```
36//!
37//! # References
38//!
39//! - Hanson, 1990 — "Fast Allocation and Deallocation of Memory
40//!   Based on Object Lifetimes"
41
42#![forbid(unsafe_code)]
43#![deny(missing_docs)]
44
45use std::marker::PhantomData;
46
47/// Typed arena allocator.
48///
49/// Stores values of type `T` in a contiguous buffer, returning stable
50/// [`Idx<T>`] handles for O(1) access. Values are dropped when the arena
51/// is dropped, reset, or rolled back past their allocation point.
52///
53/// # Differences from other arena crates
54///
55/// | Feature | `safe-bump` | `bumpalo` | `typed-arena` | `bump-scope` |
56/// |---------|------------|-----------|---------------|-------------|
57/// | `unsafe` code | none | yes | yes | yes |
58/// | Auto `Drop` | yes | no | yes | yes |
59/// | Checkpoint/rollback | yes | no | no | scopes (LIFO only) |
60/// | Keep OR discard | yes | no | no | discard only |
61/// | Access pattern | `Idx<T>` | `&T` | `&T` | `BumpBox<T>` |
62pub struct Arena<T> {
63    items: Vec<T>,
64}
65
66/// Stable index into an [`Arena<T>`].
67///
68/// Obtained from [`Arena::alloc`]. Implements [`Copy`], so it can be
69/// freely duplicated and stored in data structures.
70///
71/// Valid as long as the arena has not been reset or rolled back past
72/// this index.
73///
74/// # Panics
75///
76/// Indexing with a stale `Idx` (after rollback/reset) panics with
77/// an out-of-bounds error.
78pub struct Idx<T> {
79    index: usize,
80    _marker: PhantomData<T>,
81}
82
83/// Saved allocation state for [`Arena::rollback`].
84///
85/// Created by [`Arena::checkpoint`]. Rolling back to a checkpoint
86/// drops all values allocated after it and retains everything before.
87pub struct Checkpoint<T> {
88    len: usize,
89    _marker: PhantomData<T>,
90}
91
92// ─── Arena ───────────────────────────────────────────────────────────────────
93
94impl<T> Arena<T> {
95    /// Creates an empty arena.
96    #[must_use]
97    pub const fn new() -> Self {
98        Self { items: Vec::new() }
99    }
100
101    /// Creates an arena with pre-allocated capacity for `capacity` items.
102    #[must_use]
103    pub fn with_capacity(capacity: usize) -> Self {
104        Self {
105            items: Vec::with_capacity(capacity),
106        }
107    }
108
109    /// Allocates a value in the arena, returning its stable index.
110    ///
111    /// O(1) amortized (backed by [`Vec::push`]).
112    pub fn alloc(&mut self, value: T) -> Idx<T> {
113        let index = self.items.len();
114        self.items.push(value);
115        Idx {
116            index,
117            _marker: PhantomData,
118        }
119    }
120
121    /// Returns a reference to the value at `idx`.
122    ///
123    /// # Panics
124    ///
125    /// Panics if `idx` is out of bounds (stale after rollback/reset).
126    #[must_use]
127    pub fn get(&self, idx: Idx<T>) -> &T {
128        &self.items[idx.index]
129    }
130
131    /// Returns a mutable reference to the value at `idx`.
132    ///
133    /// # Panics
134    ///
135    /// Panics if `idx` is out of bounds (stale after rollback/reset).
136    #[must_use]
137    pub fn get_mut(&mut self, idx: Idx<T>) -> &mut T {
138        &mut self.items[idx.index]
139    }
140
141    /// Returns the number of allocated items.
142    #[must_use]
143    pub const fn len(&self) -> usize {
144        self.items.len()
145    }
146
147    /// Returns `true` if the arena contains no items.
148    #[must_use]
149    pub const fn is_empty(&self) -> bool {
150        self.items.is_empty()
151    }
152
153    /// Returns the current capacity in items.
154    #[must_use]
155    pub const fn capacity(&self) -> usize {
156        self.items.capacity()
157    }
158
159    /// Saves the current allocation state.
160    ///
161    /// Use with [`rollback`](Arena::rollback) to discard allocations
162    /// made after this point.
163    #[must_use]
164    pub const fn checkpoint(&self) -> Checkpoint<T> {
165        Checkpoint {
166            len: self.items.len(),
167            _marker: PhantomData,
168        }
169    }
170
171    /// Rolls back to a previous checkpoint, dropping all values
172    /// allocated after it.
173    ///
174    /// O(k) where k = number of items dropped (destructors run).
175    ///
176    /// # Panics
177    ///
178    /// Panics if `cp` points beyond the current length.
179    pub fn rollback(&mut self, cp: Checkpoint<T>) {
180        assert!(
181            cp.len <= self.items.len(),
182            "checkpoint {} beyond current length {}",
183            cp.len,
184            self.items.len(),
185        );
186        self.items.truncate(cp.len);
187    }
188
189    /// Removes all items, running their destructors.
190    ///
191    /// Retains allocated memory for reuse.
192    pub fn reset(&mut self) {
193        self.items.clear();
194    }
195
196    /// Returns an iterator over all allocated items.
197    pub fn iter(&self) -> std::slice::Iter<'_, T> {
198        self.items.iter()
199    }
200
201    /// Returns a mutable iterator over all allocated items.
202    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> {
203        self.items.iter_mut()
204    }
205
206    /// Allocates multiple values from an iterator, returning the index
207    /// of the first allocated item.
208    ///
209    /// Returns `None` if the iterator is empty.
210    ///
211    /// O(n) where n = items yielded by the iterator.
212    pub fn alloc_extend(&mut self, iter: impl IntoIterator<Item = T>) -> Option<Idx<T>> {
213        let start = self.items.len();
214        self.items.extend(iter);
215        if self.items.len() > start {
216            Some(Idx {
217                index: start,
218                _marker: PhantomData,
219            })
220        } else {
221            None
222        }
223    }
224
225    /// Returns `true` if `idx` points to a valid item in this arena.
226    ///
227    /// An index becomes invalid after [`rollback`](Arena::rollback) or
228    /// [`reset`](Arena::reset) removes the item it pointed to.
229    #[must_use]
230    pub const fn is_valid(&self, idx: Idx<T>) -> bool {
231        idx.index < self.items.len()
232    }
233
234    /// Returns a reference to the value at `idx`, or `None` if the
235    /// index is out of bounds.
236    #[must_use]
237    pub fn try_get(&self, idx: Idx<T>) -> Option<&T> {
238        self.items.get(idx.index)
239    }
240
241    /// Returns a mutable reference to the value at `idx`, or `None`
242    /// if the index is out of bounds.
243    #[must_use]
244    pub fn try_get_mut(&mut self, idx: Idx<T>) -> Option<&mut T> {
245        self.items.get_mut(idx.index)
246    }
247
248    /// Removes all items, returning an iterator that yields them
249    /// in allocation order.
250    ///
251    /// The arena is empty after the iterator is consumed or dropped.
252    /// Capacity is retained.
253    pub fn drain(&mut self) -> std::vec::Drain<'_, T> {
254        self.items.drain(..)
255    }
256
257    /// Returns an iterator yielding `(Idx<T>, &T)` pairs in allocation order.
258    #[must_use]
259    pub fn iter_indexed(&self) -> IterIndexed<'_, T> {
260        IterIndexed {
261            inner: self.items.iter().enumerate(),
262        }
263    }
264
265    /// Returns a mutable iterator yielding `(Idx<T>, &mut T)` pairs in
266    /// allocation order.
267    pub fn iter_indexed_mut(&mut self) -> IterIndexedMut<'_, T> {
268        IterIndexedMut {
269            inner: self.items.iter_mut().enumerate(),
270        }
271    }
272
273    /// Reserves capacity for at least `additional` more items.
274    pub fn reserve(&mut self, additional: usize) {
275        self.items.reserve(additional);
276    }
277
278    /// Shrinks the backing storage to fit the current number of items.
279    pub fn shrink_to_fit(&mut self) {
280        self.items.shrink_to_fit();
281    }
282}
283
284impl<T> Default for Arena<T> {
285    fn default() -> Self {
286        Self::new()
287    }
288}
289
290impl<T> std::ops::Index<Idx<T>> for Arena<T> {
291    type Output = T;
292
293    fn index(&self, idx: Idx<T>) -> &T {
294        self.get(idx)
295    }
296}
297
298impl<T> std::ops::IndexMut<Idx<T>> for Arena<T> {
299    fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
300        self.get_mut(idx)
301    }
302}
303
304impl<'a, T> IntoIterator for &'a Arena<T> {
305    type Item = &'a T;
306    type IntoIter = std::slice::Iter<'a, T>;
307
308    fn into_iter(self) -> Self::IntoIter {
309        self.iter()
310    }
311}
312
313impl<'a, T> IntoIterator for &'a mut Arena<T> {
314    type Item = &'a mut T;
315    type IntoIter = std::slice::IterMut<'a, T>;
316
317    fn into_iter(self) -> Self::IntoIter {
318        self.iter_mut()
319    }
320}
321
322impl<T> Extend<T> for Arena<T> {
323    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
324        self.items.extend(iter);
325    }
326}
327
328impl<T> std::iter::FromIterator<T> for Arena<T> {
329    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
330        Self {
331            items: iter.into_iter().collect(),
332        }
333    }
334}
335
336impl<T> IntoIterator for Arena<T> {
337    type Item = T;
338    type IntoIter = std::vec::IntoIter<T>;
339
340    fn into_iter(self) -> Self::IntoIter {
341        self.items.into_iter()
342    }
343}
344
345// ─── IterIndexed ─────────────────────────────────────────────────────────────
346
347/// Iterator yielding `(Idx<T>, &T)` pairs in allocation order.
348///
349/// Created by [`Arena::iter_indexed`].
350pub struct IterIndexed<'a, T> {
351    inner: std::iter::Enumerate<std::slice::Iter<'a, T>>,
352}
353
354impl<'a, T> Iterator for IterIndexed<'a, T> {
355    type Item = (Idx<T>, &'a T);
356
357    fn next(&mut self) -> Option<Self::Item> {
358        self.inner.next().map(|(i, v)| {
359            (
360                Idx {
361                    index: i,
362                    _marker: PhantomData,
363                },
364                v,
365            )
366        })
367    }
368
369    fn size_hint(&self) -> (usize, Option<usize>) {
370        self.inner.size_hint()
371    }
372}
373
374impl<T> ExactSizeIterator for IterIndexed<'_, T> {}
375
376// ─── IterIndexedMut ─────────────────────────────────────────────────────────
377
378/// Mutable iterator yielding `(Idx<T>, &mut T)` pairs in allocation order.
379///
380/// Created by [`Arena::iter_indexed_mut`].
381pub struct IterIndexedMut<'a, T> {
382    inner: std::iter::Enumerate<std::slice::IterMut<'a, T>>,
383}
384
385impl<'a, T> Iterator for IterIndexedMut<'a, T> {
386    type Item = (Idx<T>, &'a mut T);
387
388    fn next(&mut self) -> Option<Self::Item> {
389        self.inner.next().map(|(i, v)| {
390            (
391                Idx {
392                    index: i,
393                    _marker: PhantomData,
394                },
395                v,
396            )
397        })
398    }
399
400    fn size_hint(&self) -> (usize, Option<usize>) {
401        self.inner.size_hint()
402    }
403}
404
405impl<T> ExactSizeIterator for IterIndexedMut<'_, T> {}
406
407// ─── Idx ─────────────────────────────────────────────────────────────────────
408
409impl<T> Idx<T> {
410    /// Returns the raw index value.
411    #[must_use]
412    pub const fn into_raw(self) -> usize {
413        self.index
414    }
415
416    /// Creates an index from a raw value.
417    ///
418    /// The caller must ensure the index is valid for the target arena.
419    #[must_use]
420    pub const fn from_raw(index: usize) -> Self {
421        Self {
422            index,
423            _marker: PhantomData,
424        }
425    }
426}
427
428impl<T> Clone for Idx<T> {
429    fn clone(&self) -> Self {
430        *self
431    }
432}
433
434impl<T> Copy for Idx<T> {}
435
436impl<T> PartialEq for Idx<T> {
437    fn eq(&self, other: &Self) -> bool {
438        self.index == other.index
439    }
440}
441
442impl<T> Eq for Idx<T> {}
443
444impl<T> std::hash::Hash for Idx<T> {
445    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
446        self.index.hash(state);
447    }
448}
449
450impl<T> std::fmt::Debug for Idx<T> {
451    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
452        write!(f, "Idx({})", self.index)
453    }
454}
455
456impl<T> PartialOrd for Idx<T> {
457    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
458        Some(self.cmp(other))
459    }
460}
461
462impl<T> Ord for Idx<T> {
463    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
464        self.index.cmp(&other.index)
465    }
466}
467
468// ─── Checkpoint ──────────────────────────────────────────────────────────────
469
470impl<T> Checkpoint<T> {
471    /// Returns the saved length.
472    #[must_use]
473    pub const fn len(&self) -> usize {
474        self.len
475    }
476
477    /// Returns `true` if the checkpoint was taken at an empty state.
478    #[must_use]
479    pub const fn is_empty(&self) -> bool {
480        self.len == 0
481    }
482}
483
484impl<T> Clone for Checkpoint<T> {
485    fn clone(&self) -> Self {
486        *self
487    }
488}
489
490impl<T> Copy for Checkpoint<T> {}
491
492impl<T> PartialEq for Checkpoint<T> {
493    fn eq(&self, other: &Self) -> bool {
494        self.len == other.len
495    }
496}
497
498impl<T> Eq for Checkpoint<T> {}
499
500impl<T> std::hash::Hash for Checkpoint<T> {
501    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
502        self.len.hash(state);
503    }
504}
505
506impl<T> std::fmt::Debug for Checkpoint<T> {
507    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
508        write!(f, "Checkpoint({})", self.len)
509    }
510}
511
512impl<T> PartialOrd for Checkpoint<T> {
513    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
514        Some(self.cmp(other))
515    }
516}
517
518impl<T> Ord for Checkpoint<T> {
519    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
520        self.len.cmp(&other.len)
521    }
522}
523
524// ─── Tests ───────────────────────────────────────────────────────────────────
525
526#[cfg(test)]
527mod tests {
528    use std::cell::Cell;
529    use std::rc::Rc;
530
531    use super::*;
532
533    #[test]
534    fn empty_arena() {
535        let arena: Arena<i32> = Arena::new();
536        assert!(arena.is_empty());
537        assert_eq!(arena.len(), 0);
538    }
539
540    #[test]
541    fn alloc_and_access() {
542        let mut arena = Arena::new();
543        let a = arena.alloc(42);
544        let b = arena.alloc(99);
545
546        assert_eq!(arena[a], 42);
547        assert_eq!(arena[b], 99);
548        assert_eq!(arena.len(), 2);
549    }
550
551    #[test]
552    fn alloc_strings() {
553        let mut arena = Arena::new();
554        let a = arena.alloc(String::from("hello"));
555        let b = arena.alloc(String::from("world"));
556
557        assert_eq!(arena[a], "hello");
558        assert_eq!(arena[b], "world");
559    }
560
561    #[test]
562    fn get_mut_modifies() {
563        let mut arena = Arena::new();
564        let a = arena.alloc(String::from("old"));
565
566        arena[a] = String::from("new");
567        assert_eq!(arena[a], "new");
568    }
569
570    #[test]
571    fn with_capacity() {
572        let arena: Arena<u64> = Arena::with_capacity(100);
573        assert!(arena.capacity() >= 100);
574        assert!(arena.is_empty());
575    }
576
577    #[test]
578    fn checkpoint_rollback() {
579        let mut arena = Arena::new();
580        let a = arena.alloc(1);
581        let b = arena.alloc(2);
582        let cp = arena.checkpoint();
583
584        let _c = arena.alloc(3);
585        let _d = arena.alloc(4);
586        assert_eq!(arena.len(), 4);
587
588        arena.rollback(cp);
589        assert_eq!(arena.len(), 2);
590        assert_eq!(arena[a], 1);
591        assert_eq!(arena[b], 2);
592    }
593
594    #[test]
595    fn rollback_runs_drop() {
596        let drop_count = Rc::new(Cell::new(0u32));
597
598        struct Tracked(Rc<Cell<u32>>);
599        impl Drop for Tracked {
600            fn drop(&mut self) {
601                self.0.set(self.0.get() + 1);
602            }
603        }
604
605        let mut arena = Arena::new();
606        let _a = arena.alloc(Tracked(Rc::clone(&drop_count)));
607        let cp = arena.checkpoint();
608        let _b = arena.alloc(Tracked(Rc::clone(&drop_count)));
609        let _c = arena.alloc(Tracked(Rc::clone(&drop_count)));
610
611        assert_eq!(drop_count.get(), 0);
612        arena.rollback(cp);
613        assert_eq!(drop_count.get(), 2); // b and c dropped
614    }
615
616    #[test]
617    fn reset_runs_drop() {
618        let drop_count = Rc::new(Cell::new(0u32));
619
620        struct Tracked(Rc<Cell<u32>>);
621        impl Drop for Tracked {
622            fn drop(&mut self) {
623                self.0.set(self.0.get() + 1);
624            }
625        }
626
627        let mut arena = Arena::new();
628        let _a = arena.alloc(Tracked(Rc::clone(&drop_count)));
629        let _b = arena.alloc(Tracked(Rc::clone(&drop_count)));
630
631        arena.reset();
632        assert_eq!(drop_count.get(), 2);
633        assert!(arena.is_empty());
634    }
635
636    #[test]
637    fn reset_preserves_capacity() {
638        let mut arena = Arena::with_capacity(100);
639        for i in 0..50 {
640            arena.alloc(i);
641        }
642        let cap_before = arena.capacity();
643
644        arena.reset();
645        assert!(arena.is_empty());
646        assert_eq!(arena.capacity(), cap_before);
647    }
648
649    #[test]
650    fn nested_checkpoints() {
651        let mut arena = Arena::new();
652        let a = arena.alloc(1);
653
654        let cp1 = arena.checkpoint();
655        let _b = arena.alloc(2);
656
657        let cp2 = arena.checkpoint();
658        let _c = arena.alloc(3);
659
660        arena.rollback(cp2);
661        assert_eq!(arena.len(), 2);
662
663        arena.rollback(cp1);
664        assert_eq!(arena.len(), 1);
665        assert_eq!(arena[a], 1);
666    }
667
668    #[test]
669    fn rollback_to_empty() {
670        let mut arena = Arena::new();
671        let cp = arena.checkpoint();
672
673        arena.alloc(1);
674        arena.alloc(2);
675        arena.rollback(cp);
676
677        assert!(arena.is_empty());
678    }
679
680    #[test]
681    #[should_panic(expected = "checkpoint 5 beyond current length 2")]
682    fn rollback_beyond_length_panics() {
683        let mut arena = Arena::new();
684        arena.alloc(1);
685        arena.alloc(2);
686
687        let bad_cp = Checkpoint::<i32> {
688            len: 5,
689            _marker: PhantomData,
690        };
691        arena.rollback(bad_cp);
692    }
693
694    #[test]
695    #[should_panic]
696    fn stale_index_panics() {
697        let mut arena = Arena::new();
698        let _a = arena.alloc(1);
699        let b = arena.alloc(2);
700
701        arena.reset();
702        let _ = arena[b]; // stale index
703    }
704
705    #[test]
706    fn idx_is_copy() {
707        let mut arena = Arena::new();
708        let a = arena.alloc(42);
709        let b = a; // Copy
710        assert_eq!(arena[a], arena[b]);
711    }
712
713    #[test]
714    fn idx_equality() {
715        let a = Idx::<i32>::from_raw(5);
716        let b = Idx::<i32>::from_raw(5);
717        let c = Idx::<i32>::from_raw(3);
718
719        assert_eq!(a, b);
720        assert_ne!(a, c);
721    }
722
723    #[test]
724    fn idx_ordering() {
725        let a = Idx::<i32>::from_raw(1);
726        let b = Idx::<i32>::from_raw(5);
727
728        assert!(a < b);
729    }
730
731    #[test]
732    fn idx_raw_roundtrip() {
733        let idx = Idx::<String>::from_raw(42);
734        assert_eq!(idx.into_raw(), 42);
735    }
736
737    #[test]
738    fn iter() {
739        let mut arena = Arena::new();
740        arena.alloc(10);
741        arena.alloc(20);
742        arena.alloc(30);
743
744        let sum: i32 = arena.iter().sum();
745        assert_eq!(sum, 60);
746    }
747
748    #[test]
749    fn default_is_empty() {
750        let arena: Arena<u8> = Arena::default();
751        assert!(arena.is_empty());
752    }
753
754    #[test]
755    fn many_allocations() {
756        let mut arena = Arena::with_capacity(0);
757        for i in 0..10_000 {
758            let idx = arena.alloc(i);
759            assert_eq!(arena[idx], i);
760        }
761        assert_eq!(arena.len(), 10_000);
762    }
763
764    #[test]
765    fn checkpoint_len() {
766        let mut arena = Arena::new();
767        arena.alloc(1);
768        arena.alloc(2);
769        let cp = arena.checkpoint();
770        assert_eq!(cp.len(), 2);
771    }
772
773    #[test]
774    fn reuse_after_reset() {
775        let mut arena = Arena::new();
776        arena.alloc(String::from("first"));
777        arena.reset();
778
779        let a = arena.alloc(String::from("second"));
780        assert_eq!(arena[a], "second");
781        assert_eq!(arena.len(), 1);
782    }
783
784    #[test]
785    fn alloc_extend_returns_first_idx() {
786        let mut arena = Arena::new();
787        arena.alloc(0);
788
789        let first = arena.alloc_extend(vec![10, 20, 30]);
790        assert_eq!(first, Some(Idx::from_raw(1)));
791        assert_eq!(arena.len(), 4);
792        assert_eq!(arena[Idx::from_raw(1)], 10);
793        assert_eq!(arena[Idx::from_raw(2)], 20);
794        assert_eq!(arena[Idx::from_raw(3)], 30);
795    }
796
797    #[test]
798    fn alloc_extend_empty_returns_none() {
799        let mut arena: Arena<i32> = Arena::new();
800        let result = arena.alloc_extend(std::iter::empty());
801        assert_eq!(result, None);
802        assert!(arena.is_empty());
803    }
804
805    #[test]
806    fn is_valid_after_rollback() {
807        let mut arena = Arena::new();
808        let a = arena.alloc(1);
809        let cp = arena.checkpoint();
810        let b = arena.alloc(2);
811
812        assert!(arena.is_valid(a));
813        assert!(arena.is_valid(b));
814
815        arena.rollback(cp);
816        assert!(arena.is_valid(a));
817        assert!(!arena.is_valid(b));
818    }
819
820    #[test]
821    fn is_valid_after_reset() {
822        let mut arena = Arena::new();
823        let a = arena.alloc(1);
824
825        assert!(arena.is_valid(a));
826        arena.reset();
827        assert!(!arena.is_valid(a));
828    }
829
830    #[test]
831    fn try_get_returns_none_for_stale() {
832        let mut arena = Arena::new();
833        let a = arena.alloc(42);
834        let cp = arena.checkpoint();
835        let b = arena.alloc(99);
836
837        arena.rollback(cp);
838        assert_eq!(arena.try_get(a), Some(&42));
839        assert_eq!(arena.try_get(b), None);
840    }
841
842    #[test]
843    fn try_get_mut_returns_none_for_stale() {
844        let mut arena = Arena::new();
845        let _a = arena.alloc(1);
846        let cp = arena.checkpoint();
847        let b = arena.alloc(2);
848
849        arena.rollback(cp);
850        assert_eq!(arena.try_get_mut(b), None);
851    }
852
853    #[test]
854    fn drain_returns_all_items() {
855        let mut arena = Arena::new();
856        arena.alloc(10);
857        arena.alloc(20);
858        arena.alloc(30);
859
860        let items: Vec<_> = arena.drain().collect();
861        assert_eq!(items, vec![10, 20, 30]);
862        assert!(arena.is_empty());
863    }
864
865    #[test]
866    fn drain_runs_no_extra_drops() {
867        let drop_count = Rc::new(Cell::new(0u32));
868
869        struct Tracked(Rc<Cell<u32>>);
870        impl Drop for Tracked {
871            fn drop(&mut self) {
872                self.0.set(self.0.get() + 1);
873            }
874        }
875
876        let mut arena = Arena::new();
877        arena.alloc(Tracked(Rc::clone(&drop_count)));
878        arena.alloc(Tracked(Rc::clone(&drop_count)));
879
880        let items: Vec<_> = arena.drain().collect();
881        assert_eq!(drop_count.get(), 0); // not dropped yet — owned by items
882        drop(items);
883        assert_eq!(drop_count.get(), 2); // now dropped
884    }
885
886    #[test]
887    fn iter_indexed_yields_correct_pairs() {
888        let mut arena = Arena::new();
889        let a = arena.alloc("x");
890        let b = arena.alloc("y");
891        let c = arena.alloc("z");
892
893        let pairs: Vec<_> = arena.iter_indexed().collect();
894        assert_eq!(pairs.len(), 3);
895        assert_eq!(pairs[0], (a, &"x"));
896        assert_eq!(pairs[1], (b, &"y"));
897        assert_eq!(pairs[2], (c, &"z"));
898    }
899
900    #[test]
901    fn iter_indexed_empty() {
902        let arena: Arena<i32> = Arena::new();
903        assert_eq!(arena.iter_indexed().count(), 0);
904    }
905
906    #[test]
907    fn iter_indexed_exact_size() {
908        let mut arena = Arena::new();
909        arena.alloc(1);
910        arena.alloc(2);
911        arena.alloc(3);
912
913        let iter = arena.iter_indexed();
914        assert_eq!(iter.len(), 3);
915    }
916
917    #[test]
918    fn shrink_to_fit_reduces_capacity() {
919        let mut arena: Arena<u64> = Arena::with_capacity(1000);
920        arena.alloc(1);
921        arena.alloc(2);
922        assert!(arena.capacity() >= 1000);
923
924        arena.shrink_to_fit();
925        assert!(arena.capacity() < 1000);
926        assert_eq!(arena.len(), 2);
927    }
928
929    #[test]
930    fn iter_mut_modifies_all() {
931        let mut arena = Arena::new();
932        arena.alloc(1);
933        arena.alloc(2);
934        arena.alloc(3);
935
936        for item in &mut arena {
937            *item *= 10;
938        }
939
940        let values: Vec<_> = arena.iter().copied().collect();
941        assert_eq!(values, vec![10, 20, 30]);
942    }
943
944    #[test]
945    fn iter_indexed_mut_yields_correct_pairs() {
946        let mut arena = Arena::new();
947        let a = arena.alloc(String::from("x"));
948        let b = arena.alloc(String::from("y"));
949
950        let pairs: Vec<_> = arena
951            .iter_indexed_mut()
952            .map(|(idx, val)| (idx, val.clone()))
953            .collect();
954        assert_eq!(pairs.len(), 2);
955        assert_eq!(pairs[0], (a, String::from("x")));
956        assert_eq!(pairs[1], (b, String::from("y")));
957    }
958
959    #[test]
960    fn iter_indexed_mut_modifies() {
961        let mut arena = Arena::new();
962        arena.alloc(1);
963        arena.alloc(2);
964        arena.alloc(3);
965
966        for (_, val) in arena.iter_indexed_mut() {
967            *val += 100;
968        }
969
970        assert_eq!(arena[Idx::from_raw(0)], 101);
971        assert_eq!(arena[Idx::from_raw(1)], 102);
972        assert_eq!(arena[Idx::from_raw(2)], 103);
973    }
974
975    #[test]
976    fn iter_indexed_mut_exact_size() {
977        let mut arena = Arena::new();
978        arena.alloc(1);
979        arena.alloc(2);
980
981        let iter = arena.iter_indexed_mut();
982        assert_eq!(iter.len(), 2);
983    }
984
985    #[test]
986    fn reserve_increases_capacity() {
987        let mut arena: Arena<u64> = Arena::new();
988        arena.reserve(500);
989        assert!(arena.capacity() >= 500);
990        assert!(arena.is_empty());
991    }
992
993    #[test]
994    fn extend_trait() {
995        let mut arena = Arena::new();
996        arena.alloc(1);
997        arena.extend(vec![2, 3, 4]);
998        assert_eq!(arena.len(), 4);
999
1000        let values: Vec<_> = arena.iter().copied().collect();
1001        assert_eq!(values, vec![1, 2, 3, 4]);
1002    }
1003
1004    #[test]
1005    fn from_iterator() {
1006        let arena: Arena<i32> = (0..5).collect();
1007        assert_eq!(arena.len(), 5);
1008        assert_eq!(arena[Idx::from_raw(0)], 0);
1009        assert_eq!(arena[Idx::from_raw(4)], 4);
1010    }
1011
1012    #[test]
1013    fn checkpoint_equality() {
1014        let mut arena = Arena::new();
1015        let cp1 = arena.checkpoint();
1016        let cp2 = arena.checkpoint();
1017        assert_eq!(cp1, cp2);
1018
1019        arena.alloc(1);
1020        let cp3 = arena.checkpoint();
1021        assert_ne!(cp1, cp3);
1022    }
1023
1024    #[test]
1025    fn checkpoint_ordering() {
1026        let mut arena = Arena::new();
1027        let cp1 = arena.checkpoint();
1028        arena.alloc(1);
1029        let cp2 = arena.checkpoint();
1030        arena.alloc(2);
1031        let cp3 = arena.checkpoint();
1032
1033        assert!(cp1 < cp2);
1034        assert!(cp2 < cp3);
1035    }
1036
1037    #[test]
1038    fn into_iter_consuming() {
1039        let mut arena = Arena::new();
1040        arena.alloc(String::from("a"));
1041        arena.alloc(String::from("b"));
1042        arena.alloc(String::from("c"));
1043
1044        let collected: Vec<String> = arena.into_iter().collect();
1045        assert_eq!(collected, vec!["a", "b", "c"]);
1046    }
1047}
safe_bump/lib.rs

safe_bump/
lib.rs
