Ideas to get interior mutability primitive working

Look at the following code. Idea is, if struct is !Sync, then we can allow to mutate it by shared reference in some atomic chunks - so new mutation cannot start before previous ended. For example it could be attempted to achieve with a closure - only one closure can be executing at a time in a single threaded environment (!Sync requirement comes in). But the problem is, what if it would reenter that inside the closure? Do you have any ideas, how could it be theoretically solved? Maybe effects? Because from what I can see, compiler has full info on that and can enforce it. I'm not suggesting it right away, just curious about it for now.

use core::{
    marker::PhantomData,
    cell::UnsafeCell,
};

// !Sync
pub struct SingleThread<T>(UnsafeCell<T>, PhantomData<*mut T>);

impl<T> SingleThread<T> {
    pub fn new(value: T) -> Self {
        Self(UnsafeCell::new(value), PhantomData)
    }
    // Maybe `with` should somehow pollute the function it is called in, so that
    // function cannot be passed to `with` as argument? Also, not every usage of
    // `with` should pollute it, but only for that single value, so code like that
    // is accepted:
    // ```rust
    // let a = SingleThread::new(42u8);
    // let b = SingleThread::new(42u8);
    // a.with(|x| {
    //     b.with(|y| *x = *y);
    // });
    pub fn with<R>(&self, f: impl FnOnce(&mut T) -> R) -> R {
        let mut_ref = unsafe { &mut *self.0.get() };
        f(mut_ref)
    }
    pub fn into_inner(self) -> T {
        self.0.into_inner()
    }
}

fn main() {
    let a = SingleThread::new(42u8);
    a.with(|x| {
        a.with(|y| { // UB at that point
            *x = *y;
        });
    });
}

Basically it plays on that &/&mut are not immutable and mutable references, but shared and exclusive ones, so there is nothing wrong to mutate stuff from several places unless there is a data race possibility

If this kind of API was doable, then std would certainly have it. Either on Cell itself or as a separate datatype. It's arguably quite close to possibly by means of requiring the closure to be Send, but that kind of API is unfortunately broken by thread-local data.

1 Like

Yes, but I'm asking more from a theoretical, forward-looking approach

In my view, this might be strongly related to the problems that task-level encapsulation also poses. Async tasks are a lot like threads, but you cannot encapsulate their data via the existing Send/Sync because those presume only OS-level thread encapsulation, and both thread-local data as well as libraries that enforce sound handling of !Send data via run-time checks of the thread ID can break that. Encapsulating data of a task properly would allow spawning of futures in multi-threaded runtimes even if the future internally uses non-thread-safe primitives such as RefCell

2 Likes

Feels related to ghost_cell - Rust which allows statically checked shared mutability like this:

GhostToken::new(|mut token0| {
    GhostToken::new(|mut token1| {
        let a0 = &GhostCell::new("a");
        let a1 = a0;
        let b0 = &GhostCell::new("b");
        let b1 = b0;
        let c0 = &GhostCell::new("c");
        let c1 = c0;

        let ar = a0.borrow_mut(&mut token0);
        let br = b0.borrow_mut(&mut token1);
        std::mem::swap(ar,br);

        let cr = c0.borrow_mut(&mut token0);
        std::mem::swap(cr,br);

        dbg!((a1.borrow(&token0), b1.borrow(&token1), c1.borrow(&token0)));
    });
});

Each GhostCell is associated to one, and only one, GhostToken, which can be used to access any of the associated GhostCells. Normal borrow checking of the tokens ensures safety, since any access to the cell interior requires a corresponding borrow of the associated unique token.

I'm not so sure about that. What if for example the SingleThread was stores in a thread_local? Then it could be accessed reentrantly from basically anywhere.

This API isn't possible without either runtime checks or some other unique access token. As the counterexample, consider:

fn clueless(a: &MagicCell<i32>, b: &MagicCell<i32>) {
    // surely we'd want this to be allowed…
    a.with(|a| {
        b.with(|b| {
            *a = *b;
        });
    });
}

fn main() {
    // except…
    let cell = MagicCell::new(0);
    clueless(&cell, &cell);
}

If you want to prevent re-entrantly opening a cell, you need to forbid opening any cell which you cannot prove is disjoint from any cells already open. The simplest way is to require unique access to the cell itself, e.g. Cell::get_mut. The clever approach is to manage access ownership independently from the cell itself, either via object associated keying (e.g. RefCell, RwLock, Mutex), runtime associated keying (e.g. QCell), type associated keying (e.g. TCell, TLCell), or lifetime associated keying (e.g. LCell).

Effect associated keying could be another way of creating unique families of cells, but it'd end up looking a lot like type associated keying with implicit-like sugar for tracking access permission.

(I don't particularly recommend using any of these cell crates, despite linking to them as examples of what's possible, as I generally think they fall into the category of too clever to be worth the bookkeeping overhead outside of highly specialized applications. Also, qcell is unfortunately missing a ZST way to pass access permissions around, even though that should be sufficient for some flavors.)