Unsure how to use cells effectively

help
1

Hi. I'm new to Rust and I'm having a lot of trouble understanding how to use cells well, among other things. I'm implementing a quick Scheme interpreter and that's gone okay: I'm using this GC library which provides a Gc type, which is like Rc but garbage collected. My Lisp Objects are just an enum where any internal fields are Gcs. When I call functions with Lisp objects they get a &Gc<Object>, and if they return a Lisp object they return a Gc<Object> to indicate that there's a new way to get at the underlying object. I think I'm thinking about this little of the reference semantics correctly, and it seems to be the same reference discipline used by another much more sophisticated Scheme in Rust I found.

I can use the match operator to pick objects apart when necessary. For example, my eval looks like this:

pub fn eval(form: &Gc<Object>, env: &Gc<Object>) -> EvalResult {
    match *form.borrow() {
        Object::Cons {car: ref op, cdr: ref args} => {
            combine(&eval(op, env)?, args, env)
        }
        ...
    }
}

The problem comes in when I try to make a mutable field. The GC library says to wrap in GcCell, which is like RefCell. So for example I would have

enum Object {
    Cons { car: GcCell<Gc<Object>>, cdr: GcCell<Gc<Object>> },
    ... }

Now in this eval for example, op and args will no longer be &Gcs, they will be &GcCell<Gc>s. GcCell's borrow, like the standard RefCell, returns a GcCellRef (resp. Ref) instead of an actual reference, so I can't just call borrow. To get a &Gc out of &GcCell<Gc>, for passing around, all I've managed to come up with is &*op.borrow(), which I think borrows the underlying Gc from the cell, then dereferences that GcCellRef (which copies, maybe? which I don't want if I can avoid it?) to get a Gc, and then I take a reference to that. That's pretty weird to write everywhere, and doesn't seem normal. I can't hide it away in a function, either, since the function would return a reference to the temporary Gc.

I suspect there's something deeply wrong with my thinking. Should I just be using GcCellRef everywhere instead of actual references? Or define my own Ref-like thing? Any advice would be appreciated. I'm sorry if using Gc makes it needlessly confusing, but I used to just use Rc and I think I'd have the same problem with RefCell.

2

I think you want to be using Gc<GcCell<Whatever>> everywhere instead of GcCell<Gc<Whatever>>. This is analogous to how you usually want Rc<RefCell<T>> instead of RefCell<Rc<T>>, and Arc<Mutex<T>> instead of Mutex<Arc<T>>: the "shared" goes on the outside and the "mutable" goes on the inside. That way you get a shared handle to a mutable thing instead of a mutable handle to an (immutable) shared thing.

4 Likes
3

I saw that described in the Rust book and the docs, but I think I actually do want a mutable handle to an "immutable" thing here. Say in Scheme I wrote

(let* ((a (cons 7 ()))
       (b (cons a ())))
  (set-car! b 8)
  a)

i.e. I bind a to the cons (7 . ()), and then b to ((7 . ()) . ()). Then I do set-car, which mutates the latter into (8 . ()). a should be unaffected by this, since it's just the replaced content of the cons, so (7. ()) is returned. The actual GCable objects are the conses (the Objects in my Rust code), and when I mutate a cons I change what it points to (mutate the RefCell) without changing that pointed-to object.

ETA: And for what it's worth, the GC library readme does have a cell holding a Gc (though it's held by a Gc in turn):

#[derive(Trace, Finalize)]
struct Foo {
    cyclic: GcCell<Option<Gc<Foo>>>,
    data: u8,
}
1 Like
4

Assuming (as I think is likely; I haven't read the entire library docs/code) this is basically the same problem as Rc and RefCell: you can't take a bare reference to the contents of a GcCell. This is because, if you could, the contents of your GcCell<Gc<Object>> could be changed out from under that reference, causing the Gc and thus its owned Object to possibly be freed.

This is the tradeoff of interior mutability, in general: for SomeContainer<T>, you can have either

  • the ability to get an &'a T through &'a SomeContainer<T>, or
  • the ability to mutate/replace the T through &SomeContainer<T> (rather than &mut SomeContainer<T>),

but you cannot have both of those abilities at once, because they lead to invalid references existing. You have to pick one. Normal Rust data types pick the first, and interior-mutable types pick the second.

If you want to implement Lisp/Python/Java/insert-other-GC-oriented-language-here style semantics, then

  • Your structures have fields of type GcCell<Gc<Object>>.
  • Whenever you read a field and thereby get an reference (in the non-Rust sense) to the object that has its own independent life, you must clone the Gc<Object> out of the GcCell.
  • If you want to not pay the cost of that clone, you have to track that you're borrowing something which could otherwise be mutated but in this case must not be mutated, by using the GcCellRef.

This looks clunky in Rust because you are writing code which implements the same care with reference counts/GC roots which something like a Python interpreter would in its implementation — and, simultaneously obeys Rust's “you cannot accidentally cause use-after-free by writing the wrong code” safety rules.

So, in summary: you're not missing anything; there are good reasons for the complications you meet, and there are no simple alternatives.

There is one sort of refinement that might be of interest: your library has GcCell but it doesn't have another sort of cell it could have that's analogous to arc-swap — something that makes the “borrow momentarily to clone” operation a little cheaper, in exchange for it being the only operation you get to perform — no GcCellRefs at all.

4 Likes
5

I see! No, I was missing something. I hadn't realized that if I could get a reference, it could end up dangling if the cell is swapped out. That makes sense. So I'll probably have to actually clone a new Gc and make sure it's in scope while I work with the reference (and maybe think about using the GcCellRef directly later, but that's probably even more complicated). Kind of inconvenient for me, but yeah, I see the reasoning and it beats a segfault. I've written these kinds of things in C and C++ before and obviously haven't had to think about ownership/borrowing quite as exactly - Rust has been enlightening.

Thank you very much! I'll check out the arc swap thing sometime but I'll see if I can get this working first.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.