Fine-grained interior mutability

[moulins]

The current GcCell API for interior mutability is very coarse-grained: each GC'd object is either mutable or immutable (ignoring 'static fields that don't participate in the object graph), and the only safe way to mutate the object graph is to use the provided RefCell-like API, which incurs runtime checks. Anything else requires somewhat tricky unsafe code and a bespoke Collect implementation, which is suboptimal.

This PR reworks the mutation API by separating the type providing the unit of allocation (Gc) and the cell types providing interior mutability (cell::{Cell, RefCell}). The special cell::Mutable wrapper acts as a bridge between the two by enforcing the rules around write barriers.

Here's some example code I wrote to give a feel on how everything fits together:

use gc_arena::{Collect, Gc, MutationContext};
use gc_arena::cell::{Cell, Mutable};

// The infamous doubly-linked list!
#[derive(Collect)]
#[collect(no_drop)]
struct Node<'gc> {
    // The mutable parts are stored inline...
    prev: NodeLink<'gc>,
    next: NodeLink<'gc>,
    // ... and the rest stays immutable.
    value: Gc<'gc, /* whatever */>,
}

type NodeLink<'gc> = Cell<Option<Gc<'gc, Node<'gc>>>>;

// Ideally, this would be generated by some kind of proc-macro.
fn project_links<'a, 'gc>(
    node: &'a Mutable<Node<'gc>>,
) -> (&'a Mutable<NodeLink<'gc>>, &'a Mutable<NodeLink<'gc>>) {
    // Safe, this is just projecting fields.
    unsafe { (Mutable::assume(&node.prev), Mutable::assume(&node.next)) }
}

// Example usage. 100% safe code and no extra runtime checks!
fn detach_node<'gc>(mc: MutationContext<'gc, '_>, node: Gc<'gc, Node<'gc>>) {
    let (prev, next) = project_links(Gc::mutate(mc, &node));
    let prev = prev.replace(None);
    let next = next.replace(None);

    if let Some(p) = prev {
        let (_, prev_next) = project_links(Gc::mutate(mc, &p));
        prev_next.set(next);
    }

    if let Some(n) = next {
        let (next_prev, _) = project_links(Gc::mutate(mc, &n));
        next_prev.set(prev);
    }
}

This is still a work-in-progress (e.g. I'd like to implement the macro stuff), but now is the good time to get feedback on the core API :)

[moulins]

This took much more time than what I'd have liked, but I've finished implementing the #[derive(Mutable)] macro for safe projections! (see src/gc_arena/tests/ui-pass/mutable_linked_list.rs for an updated version of the linked-list example)

I have still some more ideas and/or unresolved questions (see the following), but I believe this is enough for an initial MVP.

---

This PR is mostly backwards-compatible; the only change is that GcCell::allocate is now GcCell::allocate_cell.

Here are some further API changes I would propose if backward-compatibility isn't an issue:

• Should GcCell be kept? It's a little unfortunate that GcCell<'_, T> is now an alias for Gc<'_, RefCell<T>> instead of Gc<'_, Cell<T>> (even though the second type is much less useful);
• Should the Gc::write_barrier method be kept? Gc::mutate does the same thing, but returns a more useful type.
• Maybe Gc::mutate should be moved to MutationContext? mc.mutate(gc) seems cleaner to me than Gc::mutate(mc, gc), idk.

---

Finally, a list of ideas for future improvements:

• Exploit the invariant 'gc lifetime to add a cell::LCell<'gc, _> type and provide a statically-checked alternative to RefCell. I'm not sure how useful this is, and how to make this ergonomic (this would at least require to give &mut GcContext<'gc> instead of MutationContext<'gc, '_> in arena mutation methods).
• Now that GC types can have mutable and immutable parts, it'd be nice if write barriers only traced the mutable parts; this could be done by, e.g., adding new Collect::{needs_write_barrier, write_barrier} methods. For an extreme example, the write barrier of DynamicRootSet could avoid tracing roots not added in the current GC cycle.
• Add more Mutable convenience methods to reduce the need for unsafe: e.g. Mutable::index<T: IndexNoGc>(&Self) -> &Mutable<T::Target>, or Mutable::transpose_slice<T>(&Mutable<[T]>) -> &[Mutable<T>]. Again, I'm not sure how useful this is.

[Bale001]

Is there anything more you wanted to do here? This feature would be really helpful

[moulins]

Is there anything more you wanted to do here? This feature would be really helpful

I'm really not happy with the Mutable projection stuff, the #[derive(Mutable)] macro is quite complex and doesn't work at all for third-party types. I'd like an alternative version where you don't need to annotate types at all, by providing a macro to type "mutable destructuring", e.g.:

mut_patterns! {
    let Node { prev, .. } = Gc::mutate(mc, &node);
}

// `prev`, `next`, `value` have type `&Mut<_>` here.
prev.replace(None);

This should be doable soundly, with a desugaring somewhat like this:

let _tmp: &Mutable<_> = Gc::mutate(mc, &node);
let &Mutable {
    __inner: Node { ref prev, .. },
    ..
} = _tmp;
// Sound because ref patterns never invoke Deref impls
let prev = unsafe { Mutable::assume(prev) };

[moulins]

Closing for now, in favor of the in-tree PR in Ruffle. I intend on opening a new PR once the proposed API has proven its worth in "real code", so to speak.