I had a type that was essentially Rc<[RefCell<T>]>, but I wanted to reduce the need for runtime checks and the extra memory used for each item. I couldn't figure out how to construct Rc<RefCell<[T]>>, so I tried to come up with an alternative to RefCell.
Here's what I came up with, I think it doesn't have any UB problems; SwapCell::inner is private, so it shouldn't be possible for more than one reference to it to exist. The only way to access it is by swapping it with another value, or cloning it. I believe both unsafe blocks [#1] and [#2] should be fine, but I would appreciate some feedback in case I actually did something unsafe.
Here's some sample code demonstrating how I plan on using it.
use std::rc::Rc;
use std::cell::RefCell;
fn main() {
let my_list = MyList::new([MyObject::None, MyObject::None, MyObject::None]
.into_iter().map(|i| swap_cell::SwapCell::new(i)).collect());
my_list.set(0, MyObject::Number(5.0));
my_list.set(1, MyObject::FixedSizedList(my_list.clone()));
my_list.set(2, MyObject::Number(7.0));
my_list.set(1, MyObject::Number(6.0));
}
#[derive(Clone)]
enum MyObject {
None,
List(Rc<RefCell<Vec<MyObject>>>),
FixedSizedList(MyList),
Number(f64),
// ...
}
// fixed sized list, Rc<[T]> has less indirection than Rc<Vec<T>>
#[derive(Clone)]
struct MyList {
// uses a lot of memory per item
// items: Rc<[RefCell<T>]>
// difficult to construct (only [T; N] vs from Vec<T>)
// items: Rc<RefCell<[T]>>
// the solution I came up with
items: Rc<[swap_cell::SwapCell<MyObject>]>
}
impl MyList {
fn new(items: Vec<swap_cell::SwapCell<MyObject>>) -> Self {
Self {
items: Rc::from(items),
}
}
fn get(&self, offset: usize) -> Option<MyObject> {
Some(self.items.get(offset)?.clone_inner())
}
fn set(&self, offset: usize, mut obj: MyObject) -> Option<MyObject> {
self.items.get(offset)?.swap(&mut obj);
Some(obj)
}
}
For some reason, I never thought to look at Cell! I always associated it as requiring T: Copy, but that's only for a subset of it's methods...
I guess I learned a bit about UnsafeCell reimplementing this, thanks for pointing me to that!
#2 is unsound because the cell could be swapped while inner_ref.clone() is running, by code that inner_ref.clone() calls, resulting in prohibited aliasing.
You have to avoid calling arbitrary other code (T::clone) while you have temporarily broken an invariant, unless you can prove that that other code can't observe the broken invariant or cause it to stay broken by panicking. (The invariant in this case is "no references to the inside of the UnsafeCell exist".)
In my example code, T::clone would only ever be dispatched to T: Copy, or Rc::clone, so it should be ok. I think I switch to using std::cell::Cell within MyList; I can use Cell::swap to remove unsafe #1, but I might still have something similar clone_inner with unsafe #2 (to avoid swapping a value twice in order to clone it). As long as I document this unsafe use and invariant within MyList and don't have any custom Clone implementations in MyObject, I think this should work (unless I missed anything).
I might manually implement Clone on the MyObject enum, repeating the invariant so I don't accidentally break it later. (or a separate safe_clone method)
That may be true about how you use swap_cell::SwapCell in your example, but it's not a property that swap_cell enforces. Therefore, the swap_cell module is unsound. That’s what unsoundness is: an API by which safe code can cause UB. Your responsibility as the author of an unsafe-using module is to make it sound way by either:
making the relevant public functions unsafe, or
restricting it using the type and trait system so that it is safe.
Also, T: Copy is not a sufficient restriction, because T::clone() can still run arbitrary code. It shouldn't — clone() should always be equivalent to a copy when copying is possible — but safe code can mis-implement clone(), so unsafe code must not rely on arbitrary T::clone() being a copy.
What would be a sufficient restriction is to have a trait dedicated to the job of specifying that clone() doesn't do anything problematic for this use case:
unsafe trait CloneDoesNotAccessAnythingElse: Clone {}
impl<T: ?Sized> CloneDoesNotAccessAnythingElse for Rc<T> {}
impl<T: ?Sized> CloneDoesNotAccessAnythingElse for &T {}
impl CloneDoesNotAccessAnythingElse for bool {}
impl CloneDoesNotAccessAnythingElse for u8 {}
...
I had forgotten about unsafe trait syntax, that's a good way to indicate things.
My last reply's explanation was unclear, so I adapted my original example code to match it. I decided to just implement SafeClone so I could include comments for all the variants.
fn main() {
let my_list = MyList::new([MyObject::None, MyObject::None, MyObject::None]);
my_list.set(0, MyObject::Number(5.0));
my_list.set(1, MyObject::FixedSizedList(my_list.clone()));
let _my_list2 = my_list.get(1).unwrap();
my_list.set(2, MyObject::Number(7.0));
my_list.set(1, MyObject::Number(6.0));
}
use my_data::{MyList, MyObject};
mod my_data {
use std::rc::Rc;
use std::cell::{Cell, RefCell};
unsafe trait SafeClone {
// implementations must not alias or mutate fields within {MyObject, MyList}.
fn safe_clone(&self) -> Self;
}
#[derive(Clone)]
pub enum MyObject {
None,
List(Rc<RefCell<Vec<MyObject>>>),
FixedSizedList(MyList),
Number(f64),
// ...
}
unsafe impl SafeClone for MyObject {
fn safe_clone(&self) -> Self {
// manually verify aliasing and mutating invariant is held;
match self {
Self::None => Self::None,
// Rc::clone is safe
Self::List(list) => Self::List(list.clone()),
// MyList::safe_clone calls Rc::clone, is safe
Self::FixedSizedList(list) => Self::FixedSizedList(list.safe_clone()),
// Copy is safe
Self::Number(number) => Self::Number(*number),
}
}
}
#[derive(Clone)]
pub struct MyList {
items: Rc<[Cell<MyObject>]>
}
impl MyList {
pub fn new<I: IntoIterator<Item = MyObject>>(iter: I) -> Self {
Self {
items: Rc::from_iter(iter.into_iter().map(|val| Cell::new(val))),
}
}
pub fn get(&self, offset: usize) -> Option<MyObject> {
let cell = self.items.get(offset)?;
let safe_cloned = unsafe {
// SafeClone trait invariant; cell will not be aliased or mutated
(&*cell.as_ptr()).safe_clone()
};
Some(safe_cloned)
}
pub fn set(&self, offset: usize, obj: MyObject) -> Option<MyObject> {
let cell = Cell::new(obj);
self.items.get(offset)?.swap(&cell);
Some(cell.into_inner())
}
}
unsafe impl SafeClone for MyList {
fn safe_clone(&self) -> Self {
// manually verify aliasing and mutating invariant is held;
Self {
// Rc::clone is safe
items: self.items.clone()
}
}
}
}