Borrow Checking Zero-Cost Cyclic Mutability

41 points by jfecher 4 days ago|4 comments

•

Animats 2 days ago

Hm. One example from the article:

    match map.get_mut(&key) {
    //    --- first mutable borrow occurs here
        Some(value) => value,
        None => {
            map.insert(key, V::default());
            //  ^~~~~~ error[E0499]: cannot borrow `*map` as mutable more than once at a time
            map.get_mut(&key).unwrap()
        }
    }

That's a limitation of the current Rust borrow checker. The problem is that the argument of match is never used again on the None path, which should end the range of the borrow before the None branch starts. But, currently, it doesn't. The range of the borrow is too closely tied to scope.

This is supposed to be fixed with the Polonius borrow checker. It doesn't require a new language, just something that ends the lifetime of a borrow at the last use.

Wasn't this covered yesterday with the article about the Vale language? It seems related.

Regarding cycles, that looks interesting. GhostCell dates from 2021 but got stuck at "alpha quality". The usual approach to cycles in Rust, or at least backlinks, involves Rc, RefCell, and Weak. Forward links are strong, back links are weak.

I've suggested creating OwnerRc, which is like Rc but not cloneable. That's a single owner Rc. If you drop an OwnerRc, it panics if there are any outstanding weak links. This is useful because you no longer have to check when upgrading a Weak - it always works.

So these are fixable language problems without the need for a new language and new terminology.

•

jfecher 2 days ago

It should be fixed with Polonius, that's why it is mentioned in the paragraph after the example. Polonius reframes borrowing from lifetimes to places similarly to Ante so this is meant to show some advantages of this approach even without adding extra rules for unstable places, etc.

Ante shares parts of its approach with Valen - both having been based on the group borrowing concept. I'm in contact with its author and we share ideas every now and then. Ante is mentioned at the end of that article too. There are actually several upcoming languages using group borrowing (or something similar) as a base now - Ante, Valen, Carbon, Zeta, Fang, Mojo, and likely more.

There are a few parts of this overall approach that'd be difficult to fix in Rust without making it an entirely different language I think. The first would be separation of use vs reference, so users can pass around mutable references without the language thinking they may be mutated, and the second would be changing Rust's core semantics to allow shared mutability in general. With internal mutability like GhostCell this is allowed via UnsafeCell but I'd imagine making every reference UnsafeCell by default wouldn't be optimal and quite a few internal changes would be required.

•

nathanwh 2 days ago

“ The difference is in what I call shape stability. If the shape of a type is stable, then there is no way to mutate it such that a previously valid reference into it becomes invalid.”

From an application programmers standpoint, isn’t this much weaker? Part of the appeal of not having shared mutability is not having to worry about data races in general, while this shape stability approach prevents some classes of data races it requires others to be enforced by the programmer, as far as I can tell.

It’s hard for me to tell the net effect of this, maybe preventing reference errors is enough, but I suspect that once you start having to enforce other invariants manually, it will feel like the savings from the automatic shape stability enforcement are not enough of an improvement over languages without any significant compile time memory safety checks.

•

jfecher 2 days ago

You generally don't have to enforce any invariants manually unless you're implementing your own abstractions from unsafe primitives like raw pointers.

Multi-threading in general is made safe by separate mechanisms which don't permit shared mutability, but there's little reason to restrict it on a single thread when it can be verified to be safe. You still cannot mutate a collection while iterating over it for example, but you can easily mutate disjoint parts of it which is something I commonly encounter in Rust.