impl<T> Clone for Cell<Rc<T>>

[SimonSapin]

In what context would an Cell<Rc<T>> be used?

@SimonSapin had a use case in this comment: https://github.com/rust-lang/rfcs/pull/1651#issuecomment-259620591

In that project I have a custom MoveCell which could now be replaced with std::cell::Cell. I’d need extension traits for these extra methods, but in the meantime I have:

impl<T> MoveCell<Option<T>> {
    pub fn is_none(&self) -> bool { … }
    pub fn take(&self) -> Option<T> { … }
}

impl<T> MoveCell<Option<Rc<T>>> {
    /// Return `Some` if this `Rc` is the only strong reference count, even if there are weak references.
    pub fn take_if_unique_strong(&self) -> Option<Rc<T>> { … }
}

impl<T> MoveCell<Option<Weak<T>>> {
    pub fn upgrade(&self) -> Option<Rc<T>> { … }
}

impl<T> MoveCell<T> where T: WellBehavedClone {
    pub fn clone_inner(&self) -> T { … }
}

pub unsafe trait WellBehavedClone: Clone {}
unsafe impl<T> WellBehavedClone for Rc<T> {}
unsafe impl<T> WellBehavedClone for Weak<T> {}
unsafe impl<T> WellBehavedClone for Option<T> where T: WellBehavedClone {}

See this explanation for why WellBehavedClone is needed.

Each of these methods uses UnsafeCell::get in an unsafe block.

This clone_inner method doesn’t fit the signature of the Clone trait (since it doesn’t return a Cell). But more generally, this shows that there is a number of operations that could be safely done with something inside Cell without moving it out and then back in (which requires leaving some default value behind in the meantime, and may or may not be optimized away in release mode). But these operations have to be carefully vetted to not break the safety of Cell. I don’t know of a good way to generalize this pattern without many new methods that need to use unsafe in their impl.

[glaebhoerl]

If I understand correctly, you also need support for cloning Cell<Option<Rc<T>>, so merely adding the Clone for Cell<Rc<T>> impl I suggest would not be enough?

I guess this idea isn’t really worth pursuing in this form then?

[SimonSapin]

This particular project wouldn’t happen to use Clone for Cell<Rc<T>> (even if we ignore the fact that that returns Cell<Rc<T>>, which seems less useful than returning Rc<T>). Maybe other projects would, I don’t know.

To me it feels like too much of a special case: why Rc<T> but not Arc<T>, or Vec<Rc<T>>, or many other standard library types? Why clone but not Option::is_none, or many other operations? I think that something that goes into std should have a principled mechanism that can work with many types and operations, not a bunch of random one-offs.

Unfortunately I don’t have a suggestion for such mechanism that isn’t a foot-gun. The memory-safety of Cell<T> can be a bit subtle, when you start playing with &*cell.as_ptr().

[arielb1]

With Rc there’s not much problem with doing rc.clone().is_none()

[SimonSapin]

rc.clone().is_none()

Is the increment-then-decrement optimized away? Is it with Arc?

[RalfJung]

To me it feels like too much of a special case: why Rc<T> but not Arc<T>, or Vec<Rc<T>>, or many other standard library types? Why clone but not Option::is_none, or many other operations? I think that something that goes into std should have a principled mechanism that can work with many types and operations, not a bunch of random one-offs.

The more general concept here seems to be "method that does not, ever, touch (read to or write from) any Cell"; let’s say such a method is “Cell-free”. Such a method is fine to be called directly on a Cell, without copying anything out first. Rc::clone and Arc::clone are Cell-free… well, kind of. They actually do use Cell internally, but that Cell is never exposed to the user. Still, this shows that the proposed API is subtle; the Cell in Rc is now magically “different” from other Cells in that Cell-freeness is fine with this particular Cell being modified, while OTOH, Rc must not call a method on Cell just because that method is Cell-free. Vec<T>::clone and Option<T>::clone are Cell-free if T::clone is; similar for many other containers. Option::is_none is Cell-free.

Funny enough, there’s actually a way Cell-freeness makes sense in my formal model; however, I don’t see a way to encode this in the Rust type system – there doesn’t seem to be a way to mark a method as having some property (as opposed to marking types, which can be done with marker traits).

However, the proposal of using rc.clone().is_none() confuses me; how is that useful for Cell<Option<T>>? No Rc involved… I must be misunderstanding something.

[withoutboats]

there doesn’t seem to be a way to mark a method as having some property (as opposed to marking types, which can be done with marker traits).

A use case for constraint kinds (that is, if the methods are encapsulated in a trait, we could apply a marker trait to T: Clone instead of a type)

[SimonSapin]

does not, ever, touch (read to or write from) any Cell

This would work, but as you noted it excludes Rc::clone. I think the real criteria for safety of manipulation of data inside Cell is “does not ever touch this particular cell again”, which is much more subtle to express systematically. Perhaps it helps to reason about reference cycles? Since a cycle would be needed to reach that cell again.

However, the proposal of using rc.clone().is_none() confuses me; how is that useful for Cell<Option<T>>? No Rc involved…

Yes, .clone().is_none() would be unsound with an arbitrary T in Cell<Option<T>>, it was only proposed for Cell<Option<Rc<U>>>.

[glaebhoerl]

FWIW, one conservative bound we can currently write that (I think!) ensures that no Cells will be accessed is Sync. Interestingly, this is sufficient for a whole bunch of things except for Rc<T> which was the motivation for the idea in the original post! But it’d work for, for example, Option and Vec.

I think you could safely have something like:

fn with_cell_contents<T, F, Z>(this: &Cell<T>, f: F) -> Z
   where F: FnOnce(&T) -> Z + Sync

in other words it is safe to pass a reference to the contents of the Cell to a function which is (because Cell is not Sync) guaranteed not to close over any Cells, and therefore, presumably, cannot have closed over the Cell whose contents you are giving it a reference to, and so cannot invalidate it with a set() or replace().

[SimonSapin]

F: Sync only prevents cells from being captured by a closure, right? There could be other ways to reach the same cell. (Globals, a cycle from &T, …)

[glaebhoerl]

Oh, yeah, you’re right that F: Sync doesn’t imply T: Sync which I had for some reason assumed. But that’s easy to fix by just adding T: Sync if it’s necessary. I’m not sure about globals… you aren’t really ‘supposed’ to put Cells in globals anyway because of the possibility of multi-threaded access (i.e. it’s not Sync)? Can you come up with an example which would be “otherwise sound”, but become unsound if you add with_cell_contents?

[rkruppe]

Can you come up with an example which would be “otherwise sound”, but become unsound if you add with_cell_contents?

You can certainly synchronize access to non-Sync globals, e.g. by locking (though in general you’d need a re-entrant lock to be able to produce multiple references in the same thread) or with thread locals (not a “global” in every sense of the word, but close enough to break with_cell_contents).

[glaebhoerl]

ISTR something to the effect that recursive mutexes are unsound in Rust as-is, precisely because you can get multiple &mut references out?

But yeah, thread locals seem like a problem :o( dang thread locals, always messing things up.

[rkruppe]

Oh, right, a re-entrant lock would have to hand out shared references, not mut references (cf. RwLock, but unlike RwLock it would not allow readers from multiple threads and could thus contain non-Sync data). There’s no such thing in std, and it may not be very useful, but it seems pretty obvious sound (and would still break with_cell_contents).

[glaebhoerl]

Maybe the problem is that Rust isn’t pure (= doesn’t have type of pure functions)? If we could require F to be pure then I think that would close off all of these tricks for sneakily accessing things through side channels, and then our Sync bounds would actually be sufficient.

[rkruppe]

As has been pointed out in past discussions, “pure” means different things to different people. I’m not sure what the right definition of “pure” for this problem would be. Any of the variants implying referential transparency are a bit too strong to bea satisfactory solution (e.g., they rule out almost all uses of mutable references). Approaching it from the other end, merely “doesn’t access globals” is too weak because of re-entrant locks and similar things.

[RalfJung]

This would work, but as you noted it excludes Rc::clone. I think the real criteria for safety of manipulation of data inside Cell is “does not ever touch this particular cell again”, which is much more subtle to express systematically. Perhaps it helps to reason about reference cycles? Since a cycle would be needed to reach that cell again.

This makes “cell-freeness” generic in which cell it is talking about (as in, “this particular cell”). The way I think about it (based on how this works in some concurrency logics, which have a similar problem of avoiding reentrancy) is that each cell has some “color” or “class” or however you want to call it. There’s some default class that is used when safe code just instantiates a cell, but unsafe code like Rc can declare its cells to be in a different class. Cell-safety for a class then means that no cell of that class is accessed.

Essentially, this is a static approximation making sure there no reference cycles are followed.

Yes, .clone().is_none() would be unsound with an arbitrary T in Cell<Option<T>>, it was only proposed for Cell<Option<Rc<U>>>.

However, .is_none() should be sound with an arbitrary Cell<Option<T>>.

[SimonSapin]

However, .is_none() should be sound with an arbitrary Cell<Option<T>>.

Agreed.

[earthengine]

To be honest it is not hard to do on a newtyped Cell<Rc<T>>:

use std::cell::Cell;
use std::rc::Rc;

struct CellRc<T>(Cell<Rc<T>>);

impl<T> Clone for CellRc<T> {
    fn clone(&self) -> Self {
        unsafe {
            CellRc(Cell::new((*self.0.as_ptr()).clone()))
        }
    }
}
impl CellRc {
    fn new(t: T) -> Self {
        Self(Cell::new(Rc::new(t)))
    }
}

fn main() {
    let c = CellRc::new(10);
    let g = c.clone();
}

or have a free function

pub fn clone_cell_rc<T>(t: &Cell<Rc<T>>) -> Cell<Rc<T>> {
    unsafe {
        Cell::new((*t.as_ptr()).clone())
    }
}

in general we can do

pub fn clone_cell<T: Clone>(t: &Cell<T>) -> Cell<T> {
    unsafe {
        Cell::new((*t.as_ptr()).clone())
    }
}

But we need to justify the unsafe block above.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.