Cons element_iter! macro

[CeleritasCelery]

This one is a beast.

rune/src/cons/iter.rs

Lines 166 to 189 in 7136b74

	macro_rules! element_iter {
	($ident:ident, $obj:expr, $gc:ident) => {
	let mut root_elem = None;
	let mut root_cons = None;
	$crate::make_root_owner!(owner);
	let mut gc_root_elem = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };
	let mut gc_root_cons = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };
	#[allow(unused_qualifications)]
	let list: $crate::object::List = $obj.try_into()?;
	if let $crate::object::List::Cons(x) = list {
	root_elem =
	unsafe { Some($crate::arena::Root::new($crate::arena::RootObj::default())) };
	root_cons = unsafe { Some($crate::arena::Root::new($crate::arena::RootCons::new(!x))) };
	gc_root_elem.set(root_elem.as_mut().unwrap());
	gc_root_cons.set(root_cons.as_mut().unwrap());
	} else {
	std::mem::forget(gc_root_elem);
	std::mem::forget(gc_root_cons);
	}
	#[allow(unused_mut)]
	let mut $ident = $crate::cons::ElemStreamIter::new(&root_elem, &root_cons, owner);
	};
	}

Essentially what we need to do here is create a iterator where the returned value is rooted on each iteration and can only live for that iteration. This is because Cons cells are globally mutable and elements of the list could become unreachable at any point. So if the objects outlive their iteration cycle they could potentially get collected and lead to use-after-free. The only way to do this without GAT's is to use the streaming-iterator crate. This redefines the Iterator next method to bind the lifetime to the borrow of the iterator like this.

    fn next(&mut self) -> Option<&Self::Item> {
        self.advance();
        (*self).get()
    }

So this means we need a way to root the Item on every cycle. So we declare two new roots (one for the item, one for the cons we are using for iteration).

let mut gc_root_elem = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };
let mut gc_root_cons = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };

However we have to handle the case where the iterator is empty. In that case we can't set the root because we don't have anything to set it with (see #3 for the invariant of rooting). So we declare some Option types that will hold our pinned location on the stack.

let mut root_elem = None;
let mut root_cons = None;

Then we can conditionally set the value of those Option types of our cons is not nil. If it is nil then we simply call forget on the roots so that the drop glue is not called. If the drop glue was called it would pop items off the root stack that we never pushed on.

if let $crate::object::List::Cons(x) = list {
    root_elem =
        unsafe { Some($crate::arena::Root::new($crate::arena::RootObj::default())) };
    root_cons = unsafe { Some($crate::arena::Root::new($crate::arena::RootCons::new(!x))) };
    gc_root_elem.set(root_elem.as_mut().unwrap());
    gc_root_cons.set(root_cons.as_mut().unwrap());
} else {
    std::mem::forget(gc_root_elem);
    std::mem::forget(gc_root_cons);
}

Why this is sound

We are using streaming-iterator to make sure objects can't escape an iteration cycle. During that iteration cycle, we ensure that both item and cons are rooted. The root locations cannot move and store an Option, which allows us to conditionally set them. If the cons we are going to iterator over is nil then we make sure to forget the root so drop glue is not called.