A simple presentation of garbage collection of reference counted graphs.

rc_collection.rs

use std::cell::{Cell};
use std::rc::Rc;
use std::collections::HashMap;
use std::ops;


// seen = 0 for all objects
// for each object in the queue
//     for child in object
//         if child not aggregate, continue
//         seen[child] += 1
//         if seen[child] != owners[child], continue
//         queue.add child
// seen[root] += 1
// if seen[child] != owners[child], return
// root.unlink()

pub fn release_value_with_cycles(root: Value) {
    // Cycle detection works by speculatively releasing the object,
    // and if its reference count drops to zero as a result, it's valid to actually do the drop.
    if let Some(agg) = root.aggregate().filter(|r| Rc::strong_count(r) != 1) {
        let mut unseen = HashMap::new();
        speculative_release(agg, &mut unseen);
        if *unseen.entry(Rc::as_ptr(agg)).or_insert(Rc::strong_count(agg)) == 1 {
            drop(agg.content.take());
        }
    }
}
fn speculative_release(agg: &AggregateRef, unseen: &mut HashMap<AggregateId, usize>) {
    for child in agg.content.modify().children().filter_map(|child| child.aggregate()) {
        let child_n = unseen.entry(Rc::as_ptr(child)).or_insert(Rc::strong_count(child));
        
        // When we are the only remaining owner, we should release the child
        if *child_n == 1 {
            speculative_release(child, unseen);
        } else {
            *child_n -= 1;
        }
    }
}

#[derive(Clone, Debug)]
pub enum Value {
    Unit,
    Int(i32),
    Aggregate(AggregateRef),
}
pub enum AggregateContent {
    // More aggregates can be added here, like dynamic maps and records
    List(Vec<Value>),
}

type AggregateRef = Rc<Aggregate>;
type AggregateId = *const Aggregate;
#[derive(Default)]
pub struct Aggregate {
    pub content: Cell<AggregateContent>,
}
impl Default for AggregateContent {
    fn default() -> Self {
        Self::List(vec![])
    }
}
impl Value {
    pub fn aggregate(&self) -> Option<&AggregateRef> {
        match self {
            Self::Aggregate(r) => Some(r),
            _ => None,
        }
    }
}
impl AggregateContent {
    fn children(&self) -> impl Iterator<Item = &Value> + '_ {
        match self {
            AggregateContent::List(l) => l.iter(),
        }
    }
}
fn main() {
    
    let basic_value = Value::Int(12);
    release_value_with_cycles(basic_value);
    let basic_agg = Value::Aggregate(Default::default());
    release_value_with_cycles(basic_agg);
    let list = Rc::new(Aggregate::default());
    list.content.set(AggregateContent::List(vec![Value::Aggregate(list.clone())]));
    let cyclic_value = Value::Aggregate(list);
    
    let have_outer_ref = cyclic_value.clone();
    println!("dropping external ref");
    
    release_value_with_cycles(have_outer_ref);
    println!("dropping true owner");
    release_value_with_cycles(cyclic_value);
    
    // diamond test
    let a = Value::Aggregate(Default::default());
    {
        let b = Value::Aggregate(Default::default());
        let c = Value::Aggregate(Default::default());
        let d = Value::Aggregate(Default::default());
        list_mut(&mut *a.aggregate().unwrap().content.modify()).unwrap().extend([&b, &c].map(|r| r.clone()));
        list_mut(&mut *b.aggregate().unwrap().content.modify()).unwrap().extend([&d].map(|r| r.clone()));
        list_mut(&mut *c.aggregate().unwrap().content.modify()).unwrap().extend([&d].map(|r| r.clone()));
        list_mut(&mut *d.aggregate().unwrap().content.modify()).unwrap().extend([&a].map(|r| r.clone()));
    }
    println!("dropping diamond");
    release_value_with_cycles(a);
    
    use core::fmt;
    #[allow(non_local_definitions)]
    impl fmt::Debug for Aggregate {
        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
            write!(f, "{self:p}: ")?;
            f.debug_list()
                .entries(self.content.modify().children().map(|r| r))
                .finish()
        }
    }
    #[allow(non_local_definitions)]
    impl Drop for Aggregate {
        fn drop(&mut self) {
            println!("rec::Aggregate drop: {self:?}");
        }
    }
    fn list_mut(v: &mut AggregateContent) -> Option<&mut Vec<Value>> {
        match v {
            AggregateContent::List(l) => Some(l),
        }
    }
}



// ---- Cell::modify ----


impl<T: Default> ops::Deref for CellModify<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.value
    }
}
impl<T: Default> ops::DerefMut for CellModify<'_, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.value
    }
}
trait CellExt<T: Default> {
    fn modify(&self) -> CellModify<'_, T>;
}
struct CellModify<'a, T: Default> {
    content: &'a Cell<T>,
    value: T,
}
impl<T: Default> CellExt<T> for Cell<T> {
    fn modify(&self) -> CellModify<'_, T> {
        CellModify {
            content: self,
            value: self.replace(Default::default())
        }
    }
}
impl<T: Default> Drop for CellModify<'_, T> {
    fn drop(&mut self) {
        self.content.replace(std::mem::take(&mut self.value));
    }
}