basic_gc.rs

#[derive(Debug, Copy, Clone)]
enum AtomicValue {
    Undefined,
    Nil,
    Integer(i64),

    Pointer(*mut Self),
    Record(*mut Self, u32),
    Pair(*mut Self),
    
    ByteArray(*mut u8, u32),
    String(*mut u8, u32),

    Relocated(*const Self),
}

pub trait Managable: Sized + Copy + Default {
    fn record(ptr: *mut Self, len: usize) -> Self;
    fn array(ptr: *mut u8, len: usize) -> Self;
    fn pointer(ptr: *mut Self) -> Self;
    fn relocated(ptr: *const Self) -> Self;

    unsafe fn as_ptr(&self) -> Option<&mut Self>;
    unsafe fn as_array(&self) -> Option<&mut [u8]>;
    unsafe fn as_record(&self) -> Option<&mut [Self]>;
    fn as_relocated(&self) -> Option<*const Self>;

    fn is_ptr(&self) -> bool {
        unsafe { self.as_ptr().is_some() }
    }
    fn is_record(&self) -> bool {
        unsafe { self.as_record().is_some() }
    }
    fn is_relocated(&self) -> bool {
        self.as_relocated().is_some()
    }
    fn is_array(&self) -> bool {
        unsafe { self.as_array().is_some() }
    }
}

struct Context<T>
where
    T: Managable,
{
    storage: ManagedStorage<T>,
    roots: Vec<T>,
}

impl<T> Context<T>
where
    T: Managable,
{
    fn new() -> Self {
        Context {
            storage: ManagedStorage::new(0),
            roots: vec![],
        }
    }
    
    fn push_root(&mut self, value: T) {
        self.roots.push(value);
    }
    
    fn pop_root(&mut self) -> Option<T> {
        self.roots.pop()
    }

    fn cons(&mut self, car: T, cdr: T) -> T {
        if let Some(pair) = self.storage.make_record(&[car, cdr]) {
            return pair;
        }
        
        eprintln!("collecting...");
        
        self.roots.push(car);
        self.roots.push(cdr);
        let new_roots = unsafe { self.storage.collect_garbage(&self.roots, 0) };
        self.roots.clear();
        self.roots.extend(new_roots);
        
        if let Some(pair) = self.storage.make_record(&self.roots[self.roots.len() - 2..]) {
            self.roots.pop();
            self.roots.pop();
            return pair;
        }
        
        eprintln!("extending...");
        
        let extend_storage = self.storage.capacity().min(2);
        let new_roots = unsafe { self.storage.collect_garbage(&self.roots, extend_storage) };
        self.roots.clear();
        self.roots.extend(new_roots);
        
        if let Some(pair) = self.storage.make_record(&self.roots[self.roots.len() - 2..]) {
            self.roots.pop();
            self.roots.pop();
            return pair;
        }
        
        unreachable!("Unable to allocate")
    }

    fn array(&mut self, items: &[u8]) -> T {
        if let Some(pair) = self.storage.make_array(items) {
            return pair;
        }
        
        eprintln!("collecting...");
        
        let new_roots = unsafe { self.storage.collect_garbage(&self.roots, 0) };
        self.roots.clear();
        self.roots.extend(new_roots);
        
        if let Some(pair) = self.storage.make_record(&self.roots) {
            return pair;
        }
        
        eprintln!("extending...");
        
        let extend_storage = self.storage.capacity().min(items.len());
        let new_roots = unsafe { self.storage.collect_garbage(&self.roots, extend_storage) };
        self.roots.clear();
        self.roots.extend(new_roots);
        
        if let Some(pair) = self.storage.make_record(&self.roots) {
            return pair;
        }
        
        unreachable!("Unable to allocate")
    }
}

impl AtomicValue {
    fn into_str(self) -> Option<Self> {
        match self {
            AtomicValue::ByteArray(data, len) => Some(AtomicValue::String(data, len)),
            _ => None
        }
    }
}

impl Default for AtomicValue {
    fn default() -> Self {
        AtomicValue::Undefined
    }
}

impl PartialEq for AtomicValue {
    fn eq(&self, rhs: &Self) -> bool {
        use AtomicValue::*;
        match(self, rhs) {
            (Nil, Nil) => true,
            (Integer(a), Integer(b)) => a == b,
            (Pointer(a), Pointer(b)) => a == b,
            (Record(a, n), Record(b, m)) => a == b && n == m,
            _ => false
        }
    }
}

impl Managable for AtomicValue {
    fn record(ptr: *mut Self, len: usize) -> Self {
        //todo: assert len does not overflow
        match len {
            2 => AtomicValue::Pair(ptr),
            _ => AtomicValue::Record(ptr, len as u32)
        }
    }

    fn pointer(ptr: *mut Self) -> Self {
        AtomicValue::Pointer(ptr)
    }
    
    fn array(ptr: *mut u8, len: usize) -> Self {
        //todo: assert len does not overflow
        AtomicValue::ByteArray(ptr, len as u32)
    }

    fn relocated(ptr: *const Self) -> Self {
        AtomicValue::Relocated(ptr)
    }

    unsafe fn as_ptr(&self) -> Option<&mut Self> {
        match *self {
            AtomicValue::Pointer(ptr) => Some(&mut *ptr),
            _ => None,
        }
    }

    unsafe fn as_record(&self) -> Option<&mut [Self]> {
        match *self {
            AtomicValue::Record(ptr, len) => {
                Some(std::slice::from_raw_parts_mut(ptr, len as usize))
            }
            AtomicValue::Pair(ptr) => {
                Some(std::slice::from_raw_parts_mut(ptr, 2))
            }
            _ => None,
        }
    }

    unsafe fn as_array(&self) -> Option<&mut [u8]> {
        match *self {
            AtomicValue::ByteArray(ptr, len) => {
                Some(std::slice::from_raw_parts_mut(ptr, len as usize))
            }
            _ => None,
        }
    }

    fn as_relocated(&self) -> Option<*const Self> {
        match *self {
            AtomicValue::Relocated(ptr) => Some(ptr),
            _ => None,
        }
    }
}

impl std::fmt::Display for AtomicValue {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            AtomicValue::Undefined => write!(f, "#UNDEFINED"),
            AtomicValue::Nil => write!(f, "#NIL"),
            AtomicValue::Integer(i) => write!(f, "{}", i),
            AtomicValue::Pointer(ptr) => write!(f, "&{}", unsafe { **ptr }),
            AtomicValue::Pair(ptr) => write!(f, "({} . {})", unsafe { **ptr }, unsafe { *ptr.offset(1) }),
            AtomicValue::Record(_, n) => match unsafe { self.as_record() }.unwrap() {
                [] => write!(f, "()"),
                [a] => write!(f, "({} . )", a),
                [a, b] => write!(f, "({} . {})", a, b),
                s => write!(
                    f,
                    "({} . {})",
                    { s[0] },
                    AtomicValue::Record(&mut s[1], n - 1)
                ),
            },
            AtomicValue::ByteArray(ptr, n) => write!(f, "{:?}", unsafe { std::slice::from_raw_parts(*ptr, *n as usize) }),
            AtomicValue::String(ptr, n) => write!(f, "{:?}", unsafe { std::str::from_utf8(std::slice::from_raw_parts(*ptr, *n as usize)).unwrap() }),
            AtomicValue::Relocated(_) => write!(f, "\u{1f494}"),
        }
    }
}

pub struct ManagedStorage<T>
where
    T: Managable,
{
    heap: Vec<T>,
    last_root_size: usize,
}

impl<T> ManagedStorage<T>
where
    T: Managable,
{
    fn new(size: usize) -> Self {
        ManagedStorage {
            heap: Vec::with_capacity(size),
            last_root_size: 0,
        }
    }
    
    fn capacity(&self) -> usize {
        self.heap.capacity()
    }

    fn make_cell(&self, value: T) -> Option<T> {
        let data = self.alloc(1)?;
        unsafe { *data = value };
        Some(T::pointer(data))
    }

    fn make_record(&self, items: &[T]) -> Option<T> {
        let mut data = self.alloc(items.len())?;
        let rec = Some(T::record(data, items.len()));
        for i in items {
            unsafe {
                *data = *i;
                data = data.offset(1);
            }
        }
        rec
    }
    
    fn make_array(&self, items: &[u8]) -> Option<T> {
        let k = std::mem::size_of::<T>();
        let n = (items.len() + k - 1) /  k;
        let mut data = self.alloc(n)? as *mut u8;
        let arr = Some(T::array(data, items.len()));
        for i in items {
            unsafe {
                *data = *i;
                data = data.offset(1);
            }
        }
        unsafe {
            println!("{:?}", std::slice::from_raw_parts(data.offset(-4), 4));
        }
        arr
    }

    fn reference(&self, value: &T) -> T {
        T::pointer(value as *const _ as *mut _)
    }

    fn alloc(&self, n: usize) -> Option<*mut T> {
        let i = self.heap.len();

        // If the backing storage reallocates we're doomed.
        if self.heap.capacity() < i + n {
            return None;
        }

        unsafe {
            let mut_self = self.as_mut();
            mut_self.heap.resize_with(i + n, Default::default);
            Some(&mut mut_self.heap[i])
        }
    }

    /// Collect garbage.
    /// This function is marked as unsafe because it will invalidate all
    /// pointers to the heap. Objects reachable by the roots are preserved
    /// and their pointers updated. It is the responsibility of the caller to
    /// pass the roots required to reach all live objects. Otherwise there will
    /// be dangling pointers!
    unsafe fn collect_garbage(&mut self, roots: &[T], mut extend: usize) -> &[T] {
        let mem_used_before = self.heap.len();
        let capacity_before = self.heap.capacity();
        let mem_free_before = capacity_before - mem_used_before;

        if mem_free_before + self.last_root_size < roots.len() {
            extend += roots.len();
        }
        self.last_root_size = roots.len();

        let mut to_space = vec![T::default(); self.heap.capacity() + extend];

        let mut scan_ptr = &mut to_space[0] as *mut _;
        let mut insert_ptr = &mut to_space[0] as *mut _;

        for root in roots {
            *insert_ptr = *root;
            insert_ptr = insert_ptr.offset(1);
        }

        while scan_ptr < insert_ptr {
            match *scan_ptr {
                slot if slot.is_ptr() => {
                    let p = slot.as_ptr().unwrap();
                    if let Some(dst) = p.as_relocated() {
                        *scan_ptr = T::pointer(dst as *mut _);
                    } else {
                        *insert_ptr = *p;
                        *scan_ptr = T::pointer(insert_ptr);
                        *p = T::relocated(insert_ptr);
                        insert_ptr = insert_ptr.offset(1);
                    }
                }

                slot if slot.is_record() => {
                    let r = slot.as_record().unwrap();
                    if !r.is_empty() {
                        if let Some(dst) = r[0].as_relocated() {
                            *scan_ptr = T::record(dst as *mut _, r.len());
                        } else {
                            *insert_ptr = r[0];
                            *scan_ptr = T::record(insert_ptr, r.len());
                            r[0] = T::relocated(insert_ptr);
                            insert_ptr = insert_ptr.offset(1);
                            for item in &r[1..] {
                                *insert_ptr = *item;
                                insert_ptr = insert_ptr.offset(1);
                            }
                        }
                    }
                }

                _ => {}
            }
            scan_ptr = scan_ptr.offset(1);
        }

        let start = &to_space[0] as *const _ as usize;
        let len = (scan_ptr as usize - start) / std::mem::size_of::<T>();
        to_space.truncate(len);

        std::mem::replace(&mut self.as_mut().heap, to_space);

        let mem_used_after = self.heap.len();

        eprintln!(
            "{} collected, {} live, {} free, {} total",
            mem_used_before.saturating_sub(mem_used_after),
            mem_used_after,
            self.heap.capacity() - mem_used_after,
            self.heap.capacity()
        );

        &self.heap[..roots.len()]
    }

    unsafe fn as_mut(&self) -> &mut Self {
        &mut *(self as *const _ as *mut Self)
    }
}

/*impl<T> ManagedStorage<T>
where
    T: Managable + Default + Copy + std::fmt::Debug,
{
    fn print_heap(&self) {
        println!("===================================================");
        for x in &self.heap {
            println!("{:p} {:?}", x, x);
        }
        println!("===================================================");
    }
}*/

fn main() {
    use AtomicValue::*;
    println!("Stride: {}", std::mem::size_of::<AtomicValue>());

    let mut store = ManagedStorage::<AtomicValue>::new(64);
    let sublist = store
        .make_record(&[
            Integer(4),
            store
                .make_record(&[Integer(5), store.make_record(&[Integer(6), Nil]).unwrap()])
                .unwrap(),
        ])
        .unwrap();
    let list = store
        .make_record(&[
            Integer(1),
            store
                .make_record(&[
                    Integer(2),
                    store.make_record(&[Integer(3), sublist]).unwrap(),
                ])
                .unwrap(),
        ])
        .unwrap();
    println!("{}", list);
    
    let array = store.make_array("hello, garbage!".as_bytes()).unwrap().into_str().unwrap();
    println!("{}", array);
    println!("{:?}", array);

    let tmp = store.make_cell(Integer(7)).unwrap();
    let tmp = store.make_cell(tmp).unwrap();
    println!("{}", store.make_cell(tmp).unwrap());

    let a = store.reference(&sublist);
    let b = store.reference(&sublist);

    //store.print_heap();

    unsafe {
        let new_roots = store.collect_garbage(&[a, tmp, b, array], 0);
        for root in new_roots {
            println!("{}", root);
        }
    }

    //store.print_heap();

    println!("\u{1f494}");
    
    let mut context = Context::new();
    for i in 0..100 {
        let pair = context.cons(Integer(i), Nil);
        context.push_root(pair);
    }
    for i in 0..100 {
        context.pop_root();
    }
    for i in 0..100 {
        let pair = context.cons(Integer(i), Nil);
        context.push_root(pair);
    }
}