Can `&mut T` be redefined as a wrapper of `&uniq Cell<T>`

The topic of a unique immutable reference (&uniq T) distinct from &mut T has come up on this forum before, e.g in:

Unique Borrowing
Sharing for a lifetime

However, these threads do not discuss the interesting idea of using redefining &mut as a library type using &uniq and Cell. As I cannot verify my intuition that the only significant problems would be the actual implementation, backwards compatibility, and the problem of reborrowing, which I believe could all be solved, I am asking the question here:

Can &mut T be redefined as a wrapper type of &uniq Cell<T> for some sensible choice of intrinsic type &uniq?

1 Like

So the purpose would be in allowing one to have &k#uniq T where you have a unique borrow of T's region, but not the ability to change it?

I fail to see what the benefit of this would be, tbh.

I want to note that the example of let r: &mut _; *r is not special because r doesn't need to be mut, and there's some sort of interior mut thing going on. The difference is that &mut can be implicitly reborrowed, and this allows it to be "used by-value" without being invalidated.

By-value items in Rust are always mutable, i.e. {binding}.mutate().

2 Likes

From a pure implementation perspective, the answer is almost certainly "yes with enough effort", but I agree with @CAD97 -- I don't quite see the motivation for this.

From a logical standpoint, I don't think this would work, or at least not very well. Thinking about the invariants associated with each type, we would have to define the invariant for &mut T in terms of the invariant for Cell<T>... I don't quite see how this should happen. Not to mention the fact that interior mutability is a fascinating feature of Rust, but core Rust can be explained entirely without interior mutability and I think that is a good thing -- it leads to a much simpler model.

6 Likes

I mostly asked out of curiosity regarding "factoring" types into compositions of generic types. It is reasonable that this factoring has not been done because there are few or no cases where &uniq would work and &mut wouldn't.
Thanks to you both, and I appreciate your blog posts @RalfJung, very interesting.

1 Like

Here's one big thorn in representing &mut T as &k#uniq Cell<T>: how do you handle Send/Sync?

Obviously &k#uniq isn't implemented, so I'm using &mut as a standin, and this gives us a few interesting immediate notes:

<        Cell<i32>>:  Send, !Sync // <              Cell<i32> >
<&mut    Cell<i32>>:  Send, !Sync // <&uniq Cell<   Cell<i32>>>
<&mut         i32 >:  Send,  Sync // <&uniq Cell<        i32 >>
<     RefCell<i32>>:  Send, !Sync // <           RefCell<i32> >
<&mut RefCell<i32>>:  Send, !Sync // <&uniq Cell<RefCell<i32>>>
<&??? RefCell<i32>>: ?Send, ?Sync // <&uniq      RefCell<i32> >
// I say you'd want:  Send,  Sync, to match &uniq Cell<i32>

but there isn't enough type information to allow &uniq to have this behavior of ignoring the "outer level" of sync-ness (and I'm not sure it'd be sound), so you'd have to provide a special impl for &uniq Cell<T> anyway, so &mut T is still special (at a logical level, even if it's defined by lib and not by language), so that makes it even less evident that &uniq would reduce complexity any via separation of "unique" from "mutable", since &mut is still special anyway.

3 Likes

Is &uniq T intended to provide unique, immutable access to T? If so, &uniq T: Send if T: Send is provable.

There was a fairly long discussion about this on the Community Discord Server's #black-magic channel, about a "SoftSync" trait, which allows shared access to be moved accross threads soundly as long as at most one thread has access at a time. This would work for providing an api like (which notably is functionally equivalent to &uniq, though the latter would have better language support, like safely borrowing non-mutable bindings as &uniq):

// Note no Clone or Copy impl
pub struct UnsharedRef<'a,T: ?Sized>(&'a T);

impl<'a, T: ?Sized> UnsharedRef<'a,T: ?Sized>{
    pub fn from_mut(r: &'a mut T) -> Self{
        // SAFETY: 
        // The fact we have &mut implies no other access exists
        Self(r)
    }
    // .. Other constructors/methods, etc.
}

impl<T: ?Sized> Deref for UnsharedRef<'_,T>{
    type Target = T;
    fn deref(&self) -> &T{
         self
    }
}
// Sound because exactly one thread can have ownership of an UnsharedRef<'a,T>, and SoftSync requires T can be accessed through shared references from exactly one thread
unsafe impl<'a,T: SoftSync + ?Sized> Send for UnsharedRef<'a,T>{} 

The result of the discussion is that the fictional SoftSync auto trait is a superset of both Send and Sync, the reason is that Sync allows any thread to have shared access to an object, and Send allows a thread to have unique access (both ownership and mutable borrows), which can both be turned into a shared reference. Thus any type that cannot be accessed through a shared reference on the thread that did not create (or that will not destroy) the type also cannot allow unique access on such threads. So, for a &uniq type, unsafe impl<T: Send> Send for &uniq T{}, like is present for &mut T, would be sound. &uniq Cell<T> could thus be Send, just like &mut T already is. However, it could not be sync, as &&uniq Cell<T> would (presumably) decay to &&Cell<T>, granting shared (mutable) access accross threads. It would also notably be sound for &uniq T: Send if T: Sync, because you cannot write to an immutable &uniq (and thus cannot move out of a !Copy &uniq).

1 Like

I don't think I quite get the motivation of &uniq.

If I were asked to prove soundness of UnsharedRef, I would literally model it as a mutable reference. Then you could have

unsafe impl<'a,T: Send + ?Sized> Send for UnsharedRef<'a,T>{} 

But I guess by "superset" you mean that T: Sync would also be sufficient for UnsharedRef: Send? As you said

It would also notably be sound for &uniq T: Send if T: Sync, because you cannot write to an immutable &uniq (and thus cannot move out of a !Copy &uniq).

That is a very strong claim and it is not at all clear to me that it is true. But it depends on all of the other things you can or cannot do with &uniq. So far I don't understand which problem &uniq is trying to solve so this is all like stabbing in the dark.

Send and Sync exist both because every type has two user-defined invariants: one invariant that holds when the type is owned, and one invariant that holds when the type is shared. Send reflects that the "owned" invariant is 'thread-independent'; Sync says the same thing about the "shared" invariant. Neither of them have anything to do with "moving out", so I am not sure why you bring that up.

3 Likes