[Idea] Immutable and exclusive reference

[Idea] Immutable and exclusive reference

Rust has two types of references, &T which is immutable and shareable, and &mut T which is mutable but exclusive. The borrow checker ensures that there is always only one type of reference to a type and thus ensures memory safety.

Logically there could be two more reference types:

  1. mutable and shareable
  2. immutable and exclusive

Option 1 is obviously completely unsafe and will never be introduced in Rust. Option 2 (let's call it "&fixed T" for now) on the other hand is very restricted and safe. But there is no obvious use case for it, since it is strictly less powerful than both &T and &mut T. *

Casting &mut to &fixed (and back!)

But I have an idea which could provide a use case and allow code that AFAIK is not currently possible in safe Rust:

  1. Allow converting a &mut T into an arbitrary, but fixed number of &fixed T, e.g.:

let m = &mut x; let ref fixed (a, b, c) = m;

  1. These &fixed T references can then be passed around separately and reborrowed just as a &mut T, but their number cannot be increased. They also cannot coexist with a &mut T or &T reference.
  2. If you collect all of the &fixed T references you can convert them back into an &mut T:

let ref mut m = (a, b, c);

(Syntax as well as the name &fixed is obviously subject to bikeshedding.)

Since the number of &fixed T references is fixed at creation, the borrow checker can keep track of them and only allow merging them into &mut if all of them are accounted for.

In effect this allows fragmenting and later re-assembling a mutable reference.

Is this safe?

I will yield to the experts here, but I don't see why it should not be. At any point in time there is only ever a mutable, exclusive reference or a fixed number of immutable, (non-shareable) ones.

The difficulty and innovation(?) here is obviously at step 3. This is not in general possible for shared references &T because they can be copied and the borrow checker would need to prove that no more shared references exist anywhere else.

With &fixed references this is much easier, since their number can never increase after their creation. The borrow checker can annotate each &fixed reference with the total number that exists and only allow re-assembly of the &mut if all of the existing &fixed references are collected (or dead).

Is this feasible?

I'm not a compiler writer so I don't know for sure. Exclusive and immutable references used to exist in pre-1.0 Rust (see footnote) so I don't expect this to be a big problem. Allowing the re-assembly of &mut from &fixed might be more difficult, but seems possible. Depending on the syntax there might need to be a new reserved keyword.

Is this useful?

Suppose you have a &mut T reference to a node in a data structure (say a directed graph of some kind). You want to traverse the graph in several directions at once while keeping a reference to your original node, so you can compare them. So you fragment the &mut reference into several &fixed references which you can take along on the traversals. At some point you want to collect all the data gathered from the traversals and use it to update the original node. Now you can recreate the &mut reference from the &fixed references. Doing the same thing currently would be much more difficult. Now, admittedly this a very constructed scenario. But then again I don't really work on graph theory and if I can come up with an example, then I'm sure people could find many creative uses for this.

Further thoughts

  • In theory &T references and &fixed T references could co-exist, because they are all immutable. However when we want to reconstruct a &mut T from the &fixed T references, no &T can still be alive. This might be difficult to prove.

  • Should &fixed T references be constructible directly from an owned type? Probably. They will only be useful though if you want to assemble a &mut T later. They can not be cast from &T, because that would indirectly allow casting &T to &mut T.

  • I'm not that happy with the name &fixed (or &fix?). Any better suggestions?

References

I thought of this while reading this discussion on the user forum. I have not been using Rust for very long and don't have that much experience with it. I mostly expect that this idea will be shot down as infeasible or not useful enough, but I still wanted to post it in case it does have some merit.

*It seems to actually have existed in pre- 1.0 Rust under the name &const T and was removed due to the perceived uselessness. However the name &const T is confusing with the usual meaning of const in Rust and should probably not be reused, if this idea goes anywhere.

Rust already supports fragmenting &muts. For example, this compiles:

fn main() {
    let mut t = (1, 2);
    let x = &mut t.0;
    let y = &mut t.1;
}

So I think &fixed doesn't add any new capabilities.

Did you have some other examples that don't work with &mut?

3 Likes

Mutability is not a defining characteristic of Rust references, as seen with &Cell<u32> which is a shared mutable reference to a u32.

I don't see any value in a immutable exclusive reference unless it truly meant immutable (no way of changing the value, not even with UnsafeCell), but that sort of change would shake Rust down to its foundations. I don't think it is worth adding now.


This proposal doesn't add anything new to Rust, as this type is identical to your proposal

struct YourRef<'a, T: ?Sized>(pub &'a mut T);

impl<T: ?Sized>std::ops::Deref for YourRef<'_, T> {
    type Target = T;

    fn deref(&self) -> &T {
        self.0
    }
}

impl<'a> YourRef<'a, T> {
    pub fn reborrow(&mut self) -> YourRef<'_, T> { Self(self.0) }
}
2 Likes

I've had a similar idea before and also had this simple implementation around for the case of exactly two references:

Playground

A Twin<'a, T> is essentially a &T such that only two can be created (to_twins), and by uniquely borrowing both you can get a &mut T (from_twins). Pointer equality doesn't work for ZSTs so I just panic for those, and I haven't really considered ?Sized types. I'm not entirely confident on the soundness of this implementation with the lifetimes and such, but the concept seems correct. The ergonomics could probably be improved.

I wish Rust had a way to differentiate between shared+immutable and shared+mutable. I dislike Rust's current solution (interior mutability) because there's no way to express (in the type system/function signature) whether or not a function that takes &T will be mutated (where T has interior mutability).

Mutable and shareable references can be safe (i.e. core::cell::Cell proves this), though they do have limitations.

1 Like

To me, that would seem like "Leaky Abstraction" in that implementation details of the type are exposed outside it's boundaries.