## Coverage Report

#### Created: 2025-09-08 21:26

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /home/noah/src/ruchy/src/frontend/arena.rs

    Line
    Count
    Source
    1
    //! Arena-based memory allocator for AST nodes (safe version)
    2
    //!
    3
    //! This module provides an efficient arena allocator for AST nodes that:
    4
    //! - Reduces allocation overhead by pooling allocations
    5
    //! - Improves cache locality by keeping related nodes close
    6
    //! - Enables fast bulk deallocation when the arena is dropped
    7
    //! - Uses only safe Rust code
    8
    9
    use std::cell::RefCell;
    10
    use std::collections::HashMap;
    11
    use std::rc::Rc;
    12
    13
    /// Memory pool for reusing allocations
    14
    pub struct Arena {
    15
        /// Track total allocated items for statistics
    16
        total_allocated: RefCell<usize>,
    17
        /// Storage for allocated values (using Rc for shared ownership)
    18
        storage: RefCell<Vec<Rc<dyn std::any::Any>>>,
    19
    }
    20
    21
    impl Arena {
    22
        /// Create a new arena allocator
    23
    0
        pub fn new() -> Self {
    24
    0
            Self {
    25
    0
                total_allocated: RefCell::new(0),
    26
    0
                storage: RefCell::new(Vec::new()),
    27
    0
            }
    28
    0
        }
    29
    30
        /// Allocate a value in the arena (returns Rc for shared ownership)
    31
    0
        pub fn alloc<T: 'static>(&self, value: T) -> Rc<T> {
    32
    0
            *self.total_allocated.borrow_mut() += 1;
    33
    0
            let rc = Rc::new(value);
    34
    0
            self.storage
    35
    0
                .borrow_mut()
    36
    0
                .push(rc.clone() as Rc<dyn std::any::Any>);
    37
    0
            rc
    38
    0
        }
    39
    40
        /// Get total items allocated
    41
    0
        pub fn total_allocated(&self) -> usize {
    42
    0
            *self.total_allocated.borrow()
    43
    0
        }
    44
    45
        /// Get number of items in storage
    46
    0
        pub fn num_items(&self) -> usize {
    47
    0
            self.storage.borrow().len()
    48
    0
        }
    49
    50
        /// Clear all allocations (for reuse)
    51
    0
        pub fn clear(&self) {
    52
    0
            self.storage.borrow_mut().clear();
    53
    0
            *self.total_allocated.borrow_mut() = 0;
    54
    0
        }
    55
    }
    56
    57
    impl Default for Arena {
    58
    0
        fn default() -> Self {
    59
    0
            Self::new()
    60
    0
        }
    61
    }
    62
    63
    /// String interner for deduplicating strings in the AST
    64
    pub struct StringInterner {
    65
        map: RefCell<HashMap<String, Rc<str>>>,
    66
    }
    67
    68
    impl StringInterner {
    69
        /// Create a new string interner
    70
    0
        pub fn new() -> Self {
    71
    0
            Self {
    72
    0
                map: RefCell::new(HashMap::new()),
    73
    0
            }
    74
    0
        }
    75
    76
        /// Intern a string, returning an Rc that can be cheaply cloned
    77
    0
        pub fn intern(&self, s: &str) -> Rc<str> {
    78
    0
            let mut map = self.map.borrow_mut();
    79
    80
    0
            if let Some(interned) = map.get(s) {
    81
    0
                Rc::clone(interned)
    82
            } else {
    83
    0
                let rc: Rc<str> = Rc::from(s);
    84
    0
                map.insert(s.to_string(), Rc::clone(&rc));
    85
    0
                rc
    86
            }
    87
    0
        }
    88
    89
        /// Get statistics about the interner
    90
    0
        pub fn stats(&self) -> (usize, usize) {
    91
    0
            let map = self.map.borrow();
    92
    0
            let total_size: usize = map.values().map(|s| s.len()).sum();
    93
    0
            (map.len(), total_size)
    94
    0
        }
    95
    96
        /// Clear the interner
    97
    0
        pub fn clear(&self) {
    98
    0
            self.map.borrow_mut().clear();
    99
    0
        }
    100
    }
    101
    102
    impl Default for StringInterner {
    103
    0
        fn default() -> Self {
    104
    0
            Self::new()
    105
    0
        }
    106
    }
    107
    108
    /// Fast bump allocator for sequential allocations
    109
    pub struct BumpAllocator<T> {
    110
        /// Pre-allocated vector with capacity
    111
        storage: RefCell<Vec<T>>,
    112
        /// Track allocations
    113
        count: RefCell<usize>,
    114
    }
    115
    116
    impl<T> BumpAllocator<T> {
    117
        /// Create a new bump allocator with initial capacity
    118
    0
        pub fn with_capacity(capacity: usize) -> Self {
    119
    0
            Self {
    120
    0
                storage: RefCell::new(Vec::with_capacity(capacity)),
    121
    0
                count: RefCell::new(0),
    122
    0
            }
    123
    0
        }
    124
    125
        /// Allocate a value, returning its index
    126
    0
        pub fn alloc(&self, value: T) -> usize {
    127
    0
            let mut storage = self.storage.borrow_mut();
    128
    0
            let index = storage.len();
    129
    0
            storage.push(value);
    130
    0
            *self.count.borrow_mut() += 1;
    131
    0
            index
    132
    0
        }
    133
    134
        /// Get a reference to an allocated value by index
    135
    0
        pub fn get(&self, index: usize) -> Option<T>
    136
    0
        where
    137
    0
            T: Clone,
    138
        {
    139
    0
            self.storage.borrow().get(index).cloned()
    140
    0
        }
    141
    142
        /// Get the number of allocated items
    143
    0
        pub fn len(&self) -> usize {
    144
    0
            self.storage.borrow().len()
    145
    0
        }
    146
    147
        /// Check if allocator is empty
    148
    0
        pub fn is_empty(&self) -> bool {
    149
    0
            self.storage.borrow().is_empty()
    150
    0
        }
    151
    152
        /// Clear all allocations
    153
    0
        pub fn clear(&self) {
    154
    0
            self.storage.borrow_mut().clear();
    155
    0
            *self.count.borrow_mut() = 0;
    156
    0
        }
    157
    }
    158
    159
    impl<T> Default for BumpAllocator<T> {
    160
    0
        fn default() -> Self {
    161
    0
            Self::with_capacity(128)
    162
    0
        }
    163
    }
    164
    165
    #[cfg(test)]
    166
    mod tests {
    167
        use super::*;
    168
    169
        #[test]
    170
        fn test_arena_basic() {
    171
            let arena = Arena::new();
    172
    173
            let x = arena.alloc(42i32);
    174
            assert_eq!(*x, 42);
    175
    176
            let y = arena.alloc("hello".to_string());
    177
            assert_eq!(y.as_ref(), "hello");
    178
    179
            assert_eq!(arena.total_allocated(), 2);
    180
        }
    181
    182
        #[test]
    183
        fn test_string_interner() {
    184
            let interner = StringInterner::new();
    185
    186
            let s1 = interner.intern("hello");
    187
            let s2 = interner.intern("hello");
    188
            let s3 = interner.intern("world");
    189
    190
            assert_eq!(&*s1, "hello");
    191
            assert_eq!(&*s2, "hello");
    192
            assert_eq!(&*s3, "world");
    193
    194
            // Check that identical strings share the same Rc
    195
            assert!(Rc::ptr_eq(&s1, &s2));
    196
            assert!(!Rc::ptr_eq(&s1, &s3));
    197
    198
            let (num_strings, _) = interner.stats();
    199
            assert_eq!(num_strings, 2); // Only "hello" and "world"
    200
        }
    201
    202
        #[test]
    203
        fn test_bump_allocator() {
    204
            let alloc = BumpAllocator::with_capacity(10);
    205
    206
            let idx1 = alloc.alloc(42i32);
    207
            let idx2 = alloc.alloc(100i32);
    208
    209
            assert_eq!(idx1, 0);
    210
            assert_eq!(idx2, 1);
    211
            assert_eq!(alloc.get(idx1), Some(42));
    212
            assert_eq!(alloc.get(idx2), Some(100));
    213
            assert_eq!(alloc.len(), 2);
    214
        }
    215
    216
        #[test]
    217
        fn test_arena_many_allocations() {
    218
            let arena = Arena::new();
    219
    220
            for i in 0..1000 {
    221
                let _x = arena.alloc(i);
    222
            }
    223
    224
            assert_eq!(arena.total_allocated(), 1000);
    225
            assert_eq!(arena.num_items(), 1000);
    226
    227
            arena.clear();
    228
            assert_eq!(arena.total_allocated(), 0);
    229
            assert_eq!(arena.num_items(), 0);
    230
        }
    231
    }