Add `Cell::get` for `Rc`-like shallow-copying types

[frank-king]

Proposal

Problem statement

A typical pattern of interior mutability in single-thread contexts is to use Cell<T> for T: Copy, and RefCell<T> for T: !Copy. Then the default choice for an interiorly mutable Rc<T> seems to be wrapping it to a RefCell<Rc<T>>.

However, the borrow sign in an RefCell<Rc<T>> is a waste because Rc<T> can be cloned as cheaply as incrementing the borrow sign. However, if we wrap the Rc<T> into a Cell<Rc<T>> instead, we can not get its value since Cell::get requires T: Copy.

Motivating examples or use cases

Suppose we are going to implement a binary tree with both children and parent references in a single-thread context. There are usually two ways to implement:

use std::{cell::{Cell, RefCell}, rc::{Rc, Weak}};
mod ref_cell_v1 {
    struct BinaryTree<T> {
        parent: RefCell<Option<Weak<BinaryTree<T>>>>,
        left: RefCell<Option<Rc<BinaryTree<T>>>>,
        right: RefCell<Option<Rc<BinaryTree<T>>>>,
        depth: Cell<usize>,
        value: RefCell<T>,
    }
}
mod ref_cell_v2 {
    struct BinaryTree<T> {
        parent: Option<Weak<RefCell<BinaryTree<T>>>>,
        left: Option<Rc<RefCell<BinaryTree<T>>>>,
        right: Option<Rc<RefCell<BinaryTree<T>>>>,
        depth: usize,
        value: T,
    }
}

Version ref_cell_v1 has overheads of 4 borrow signs and the version ref_cell_v2 has 3 borrow signs.
(If T: Copy, ref_cell_v1 can reduce 1 borrow sign by switching to value: Cell<T> instead.)

Solution sketch

These overheads can be avoided by using Cell to wrap the Option<Rc> and Option<Weak> references, but requires Cell::get for these types to read their values.

mod cell {
    struct BinaryTree<T> {
        parent: Cell<Option<Weak<BinaryTree<T>>>>,
        left: Cell<Option<Rc<BinaryTree<T>>>>,
        right: Cell<Option<Rc<BinaryTree<T>>>>,
        depth: Cell<usize>,
        value: RefCell<T>,
    }
}

Now in this cell version, there is only one overhead borrow sign in value: RefCell<T>.

The user can add a Cell::get for Rc-like types via a trait. But it is impossible to write a trait that supports both Rc-like types and Copy types, because it would be a conflict to have both an implementation of Cell<T> where T: Copy and that where T: ShallowCopy.

Alternatives

use std::{cell::Cell, rc::{Rc, Weak}};

trait CellGet {
    type Target;
    fn get(&self) -> Self::Target;
}

impl<T> CellGet for Cell<Rc<T>> {
    type Target = Rc<T>;
    fn get(&self) -> Self::Target {
        Clone::clone(unsafe {&*self.as_ptr()})
    }
}

impl<T> CellGet for Cell<Weak<T>> {
    type Target = Weak<T>;
    fn get(&self) -> Self::Target {
        Clone::clone(unsafe {&*self.as_ptr()})
    }
}

impl<T> CellGet for Cell<Option<Rc<T>>> {
    type Target = Option<Rc<T>>;
    fn get(&self) -> Self::Target {
        Clone::clone(unsafe {&*self.as_ptr()})
    }
}

impl<T> CellGet for Cell<Option<Weak<T>>> {
    type Target = Option<Weak<T>>;
    fn get(&self) -> Self::Target {
        Clone::clone(unsafe {&*self.as_ptr()})
    }
}

Links and related work

None

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

why not just impl Clone for Cell<Rc<T>> and similar?

[scottmcm]

left: Cell<Option<Rc<BinaryTree>>>,

With this another alternative would be to use something like https://docs.rs/pawn/latest/pawn/trait.PawnExt.html, where you could do left_cell_ref.pawn().deref().cloned() to clone the Option<Rc<_>> without needing anything new.

---

I guess the thing that's special about Rc::clone is that it guarantees that no user code runs, so there's no way to make a tricky re-entrant case that would violate the reference rules?

[frank-king]

why not just impl Clone for Cell<Rc<T>> and similar?

That sounds good, but it still requires some method to get the inner Rc<T> from the cloned Cell<Rc<T>, then it can solve my desire of unifying the read access of Cell<T: Copy> and Cell<Rc<T>>.

In fact, I'm doing some proc macro that provides automatic interior mutability and provides helper getters/setters like this:

#[auto_mut]
struct Foo {
    copy_value: u32, // => wrapped into `Cell<u32>`
    rc_value: Rc<u32>, // => wrapped into `Cell<Rc<u32>>`
    #[final]
    non_copy_immut: String, // => no wrapping, just keep it `String`,
    #[mutable]
    non_copy_mut: String, // => wrapped into `RefCell<String>`,
}

Having impl<T> Cell<Rc<T>> { pub fn get(&self) -> Rc<T> }, I can directly generate the same getters for the first two cases:

impl Foo {
    fn get_copy_value(&self) -> u32 {
        self.copy_value.get()
    }
    fn get_rc_value(&self) -> Rc<u32> {
        self.rc_value.get()
    }
}

[scottmcm]

That sounds good, but it still requires some method to get the inner Rc<T> from the cloned Cell<Rc<T>,

Well, if you cloned it you have ownership of the cloned version, so https://doc.rust-lang.org/std/cell/struct.Cell.html#method.into_inner.

[frank-king]

Well, if you cloned it you have ownership of the cloned version, so https://doc.rust-lang.org/std/cell/struct.Cell.html#method.into_inner.

Oh, yes, so impl<T> Clone for Cell<Rc<T>> is better.

[kennytm]

I guess the thing that's special about Rc::clone is that it guarantees that no user code runs, so there's no way to make a tricky re-entrant case that would violate the reference rules?

For future reference, an example showing it is not safe to extend the Clone impl to impl<T: Clone> Clone for Cell<T>:

#![deny(unsafe_code)]

use std::{cell::Cell, rc::{Rc, Weak}};

#[expect(unsafe_code)]
fn bad_clone<T: Clone>(c: &Cell<T>) -> Cell<T> {
    Cell::new(unsafe { &*c.as_ptr() }.clone())
}

struct E {
    cell: Weak<Cell<E>>,
}

impl Clone for E {
    fn clone(&self) -> Self {
        let cell = self.cell.clone();
        let rc = self.cell.upgrade().unwrap();
        // (&*rc).replace() will temporarily produce an `&mut E`,
        // but we already have an active `self: &E`.
        rc.replace(Self { cell })
    }
}

fn main() {
    let b = Rc::new_cyclic(|weak| Cell::new(E { cell: weak.clone() }));
    bad_clone(&*b);
}

[joboet]

That sounds good, but it still requires some method to get the inner Rc<T> from the cloned Cell<Rc<T>,

Well, if you cloned it you have ownership of the cloned version, so https://doc.rust-lang.org/std/cell/struct.Cell.html#method.into_inner.

How often do you actually want to get a Cell<Rc<T>> from another Cell? I think most people will want to access the Rc<T> directly. And you can get a Cell<Rc<T>> by using Cell::new any time you from that.

[hanna-kruppe]

At the very least, anything Clone-shaped for a type with Cell<Rc<T>> fields wants that, including but not limited to derive(Clone). I’m not sure how commonly a derived Clone is useful with such fields, but RefCell does implement Clone that way.

[hanna-kruppe]

Note: for the motivating use case of tree with parent/sibling references, impl Clone for Cell<Rc<T>> is only sufficient if the fields are Option<Cell<Rc<T>>>. But due to UnsafeCell erasing niches of its contents, that is less efficient than Cell<Option<Rc<T>>>. Besides, having the Cell “at the top level” is generally more flexible for manipulating the tree structure.

The good news is that that type already allows cloning today (Cell::take the option, clone it, put it back in the cell). However, I suspect that won’t optimize well, and even if it does, it’s a very convoluted and non-obvious dance, so it would be great if this ACP could also address that variant in some way.

[programmerjake]

I think Clone should be implemented for all of:

• Cell<Rc<T>>
• Cell<Arc<T>> (sometimes you want a link from a !Sync type to an object shared between threads)
• Cell<rc::Weak<T>>
• Cell<sync::Weak<T>>

and for recursively nested types (up to maybe 2 recursions? so Cell<Option<Option<Rc<T>>> but not with 3 nested Options):

• Cell<Option<U>> where Cell<U>: Clone (can be limited to std types)
• Cell<Result<U, V>> where Cell<U>: Clone, Cell<V>: Clone (can be limited to std types)

this makes me wish we could add a trait CellClone but afaict that would need lattice specialization which isn't implemented:

trait CellClone {
    /// Safety: must be called with a byte-wise copy of some valid `Self`
    unsafe fn cell_clone(self: MaybeUninit<Self>) -> Self;
}

// replacement for impl<T: Copy> Clone for Cell<T>
impl<T: CellClone> Clone for Cell<T> {
    fn clone(&self) -> Self {
        unsafe { Cell::new(MaybeUninit::new(self.as_ptr().read()).cell_clone()) }
    }
}

impl<T: Copy> CellClone for T {
    unsafe fn cell_clone(self: MaybeUninit<Self>) -> Self {
        unsafe { self.assume_init() }
    }
}

// partially overlaps with above impl
impl<T: CellClone> CellClone for Option<T> {
    unsafe fn cell_clone(self: MaybeUninit<Self>) -> Self {
        unsafe {
            match self.assume_init() {
                Some(v) => Some(MaybeUninit::new(v).cell_clone()),
                None => None,
            }
        }
    }
}

...

[Amanieu]

One alternative would be to add this method to Cell:

impl Cell<T> {
    fn get_cloned(&self) -> T where T: Default + Clone ;
}

This would internally remove the value from the cell, clone it and then put it back in the cell (including on the panic path). This avoids the need for an unsafe trait and is usable by user-defined types, but is a bit awkward in that it requires T: Default. It would work for Cell<Option<Rc>> but not Cell<Rc>.

[kennytm]

I suppose it is safe to allow Copy-allocators too

impl<T: ?Sized, A: Copy + Allocator> CellClone for Rc<T, A> {}
impl<T: ?Sized, A: Copy + Allocator> CellClone for Weak<T, A> {}

this makes me wish we could add a trait CellClone but afaict that would need lattice specialization which isn't implemented:

If you can make CellClone a marker trait and make Cell<T>::clone rely on T::clone (or T::clone_to_uninit) only, there's no need to care about specialization.

#![feature(marker_trait_attr)]

/// SAFETY: <TODO>
#[marker]
unsafe trait CellClone {}

unsafe impl<T: Copy> CellClone for T {}
unsafe impl<T: CellClone> CellClone for Option<T> {}
unsafe impl<T: ?Sized> CellClone for Rc<T> {}

impl<T: CellClone + Clone> Clone for Cell<T> {
    fn clone(&self) -> Self {
        Cell::new(unsafe { &*self.as_ptr() }.clone()) // i assume it is safe 🤷
    }
}

[programmerjake]

impl<T: CellClone + Clone> Clone for Cell<T> {
    fn clone(&self) -> Self {
        Cell::new(unsafe { &*self.as_ptr() }.clone()) // i assume it is safe 🤷
    }
}

I think you'd have to copy Self and call clone() on the copy otherwise you can get UB:

#[derive(Copy)]
struct MyBadType<'a>(u8, Option<&'a Cell<Self>>);

impl Clone for MyBadType {
    fn clone(&self) -> Self {
        let self_0: &u8 = &self.0;
        self.1.unwrap().set(Self(123, None)); // UB: write to self.0 while we have a read-only reference to it
        dbg!(self_0);
        todo!()
    }
}

fn main() {
    let v = Cell::new(MyBadType(0, None));
    v.set(MyBadType(0, Some(&v)));
    v.clone();
}