I'd like to implement a data structure that stores values in 2 different orders.
Values are inserted once (in both orders) and cannot be removed without dropping the entire data structure ("append only"). They can still be mutated in place.
The values can be accessed immutably or mutably through either one of the orders and the appropriate functions take an immutable borrow of self or a mutable borrow of self, respectively. Mutating a value is applied to the value in both orders.
A simplified version of the code looks something like this:
pub struct TwoOrders<V> {
first_order: Vec<*mut V>,
second_order: Vec<*mut V>,
}
impl<V> TwoOrders<V> {
pub fn new() -> Self {
Self {
first_order: vec![],
second_order: vec![],
}
}
pub fn insert(&mut self, value: V) {
let ptr = Box::into_raw(Box::new(value));
// insert ptr into self.first_order in some position
// insert ptr into self.second_order in another position
}
pub fn get_from_first_order(&self, index: usize) -> Option<&V> {
self.first_order
.get(index)
.map(|v| unsafe { v.as_ref().unwrap() })
}
pub fn get_from_second_order(&self, index: usize) -> Option<&V> {
self.second_order
.get(index)
.map(|v| unsafe { v.as_ref().unwrap() })
}
pub fn get_mut_from_first_order(
&mut self,
index: usize,
) -> Option<&mut V> {
self.first_order
.get_mut(index)
.map(|v| unsafe { v.as_mut().unwrap() })
}
pub fn get_mut_from_second_order(
&mut self,
index: usize,
) -> Option<&mut V> {
self.second_order
.get_mut(index)
.map(|v| unsafe { v.as_mut().unwrap() })
}
}
impl<V> Drop for TwoOrders<V> {
fn drop(&mut self) {
self.first_order.clear();
for value_ptr in self.second_order.drain(..) {
std::mem::drop(unsafe { Box::from_raw(value_ptr) })
}
}
}
My question is: is this actually safe?
I am assuming that since a mutable reference to a value is attained only with a mutable borrow of self, it means that the borrow checker guarantees that there is only one exclusive reference to this value during its lifetime, so the struct itself is conceptually like a compile-time lock.
The raw pointers are never exposed outside the struct and no function allows any access to the values in a way that breaks the safety requirements of references.
Box::into_raw stops the values from being automatically dropped, and only one copy of the raw pointers is dropped with a manually implemented Drop (using Box::from_raw).
Are my assumptions correct?
Another question is: is there any existing construct in rust (in the standard library or otherwise) that would solve this use case without using raw pointers, but also without having to use a reference counted pointer or locks?
A simplified version of the code looks something like this
If this is not the complete code then no one can say for certain. Any other unsafe usage could mean these unsafe blocks really aren't safe. Whether an unsafe usage is safe cannot be determined in isolation.
However, it looks like you have the basics. Only exposing the internals via &self -> &T and &mut self -> &mut T is a great rule of thumb. Using raw pointers instead of trying to keep the Boxs is the right way to go. You do not need MaybeUninit or ManuallyDrop.
Something you are missing though is a PhantomData<V> field in the TwoOrders struct:
pub struct TwoOrders<V> {
first_order: Vec<*mut V>,
second_order: Vec<*mut V>,
_marker: PhantomData<V>,
}
This tells the compiler that your struct owns and may run destructors for Vs. This is needed so that the compiler can do drop check analysis that guards against lifetime issues in drops. See the Rust Nomicon on PhantomData.