Struct that conceptually contains parent and child mutable references

code review
1

Consider code like this:

fn main() {
    let mut v = vec![123, 45, 67, 89];
    let vref = &mut v;
    let v2ref = &mut vref[2];
    println!("{}", v2ref);
    println!("{:?}", vref);
}

That code, which puts the mutable references in local variables, is perfectly fine. I want to create a type that conceptually holds both vref and v2ref. This is what I came up with:

mod borrow_from {
    use std::marker::PhantomData;
    use std::ptr;
    
    pub struct BorrowFrom<'a, T, U> {
        original: *mut T,
        derived: *mut U,
        _phantom: PhantomData<(&'a mut T, Option<&'a mut U>)>,
    }
    
    impl<'a, T, U> BorrowFrom<'a, T, U> {
        pub fn new(original: &'a mut T) -> Self {
            Self {
                original: ptr::from_mut(original),
                derived: ptr::null_mut(),
                _phantom: PhantomData,
            }
        }
        
        pub fn get_original(&mut self) -> Option<&mut T> {
            if self.derived.is_null() {
                Some(unsafe { &mut *self.original })
            } else {
                None
            }
        }
    
        pub fn get_derived(&mut self) -> Option<&mut U> {
            unsafe { self.derived.as_mut() }
        }
        
        pub fn end_derive(&mut self) {
            self.derived = ptr::null_mut()
        }
    
        pub fn derive(&mut self, f: impl FnOnce(&mut T) -> &mut U) {
            self.derived = ptr::null_mut(); // in case f panics
            self.derived = f(unsafe { &mut *self.original });
        }
    }
}

use borrow_from::BorrowFrom;

fn use_bf(bf: &mut BorrowFrom<'_, Vec<i32>, i32>) {
    let derived = bf.get_derived().unwrap();
    println!("{}", derived);
    *derived = 76;
    bf.derive(|orig| &mut orig[1]);
    let derived_again = bf.get_derived().unwrap();
    println!("{}", derived_again);
    *derived_again = 54;
    bf.end_derive();
    println!("{:?}", bf.get_original());
}

fn main() {
    let mut v = vec![123, 45, 67, 89];
    let mut bf = borrow_from::BorrowFrom::new(&mut v);
    println!("{:?}", bf.get_original());
    bf.derive(|orig| &mut orig[2]);
    use_bf(&mut bf);
}

Is this sound? If so, is there an existing crate that does it? If not, can it be made sound?

1 Like
2

it's almost always unsound when you find yourself using raw pointers to bypass the lifetime restrictions. and self referential data structures are infamously tricky to implement in rust.

the raw pointers will dangle when the values get moved. the raw pointer will also dangle when the values get dropped.

to prevent the value from moving, Pin must be used. (heap allocated smart pointers like Box or Rc are Unpin so they can be safely Pin-ed)

to prevent the value from dropping, you must use references, just raw pointers is not enough.

the simplest implementation of self referential type I can think of is to use shared ownership i.e. Rc or Arc, instead of non-owning pointers, and always use heap allocation.

another way to implement is to use arena based allocator (which can use stack memory as backing storage), and you can use Cell<&'arena Self> for the internal pointer type.

oh, and an alternative way to implement self referential types is to use offset instead of actual pointers for internal links.

you can check the selfref crate.

1 Like
3

Is this actually a self-referential struct, though, since the value isn't in it?

4

any circular references can be considered self-referential.

maybe I misunderstood your questions. since you mentioned parent and child, I assume it's circular, right? if it's non circular, then why you need raw pointers? why not just use references?

5

For one thing, your new signature is inferred to this:

pub fn new<'in, 'any, T, U>(original: &'in mut T) -> BorrowFrom<'any, T, U> { ... }

This allows creating a BorrowFrom<'static> from a &'short mut T and using a value after it's freed, because the lifetimes in the types appear unrelated to the borrow checker.

Playground

The playground, at least for me, is showing genuinely unpredictable behavior with the value printed, and Miri detects UB.

(Further analysis of your concept pending, I'm thinking about some way to store the projection function and call it on the fly to remove all the unsafe)

6

This problem is not about self-referentiality, it's about multiple active unique borrows of the same data. In original code, both vref[2] and v2ref are pointing to the same element, therefore their regions of availability can't overlap, otherwise it's violation of, well, uniqueness.

For this to be sound, one must somehow guarantee that vref is not used in any way while v2ref is handed out. This can be done with either some kind of locking (essentially storing RefCell/Mutex/etc.), or with callback-based interface, which only gives these references to the passed function (and still needs some kind of runtime checks, to protect from reentrance).

...why don't you store index instead and generate v2ref on-the-fly as necessary?

2 Likes
7

Whoops. I just changed pub fn new(original: &mut T) -> Self { to pub fn new(original: &'a mut T) -> Self {, and that seems to have fixed that.

This is what I tried to do. The way it's supposed to work is that once self.derived gets set, you're locked out of self.original until it's unset again. Did I mess this up?

In this toy example I could, but pretend that the derived reference is more complicated than just indexing a Vec.

1 Like
8

Done.

I rewrote your OP with similar API in completely safe code, so no soundness issues.

mod borrow_from {
    type Projector<T, U> = for<'r> fn(&'r mut T) -> &'r mut U;
    pub struct BorrowFrom<'a, T, U> {
        original: &'a mut T,
        proj: Projector<T, U>,
    }
    
    impl<'a, T, U> BorrowFrom<'a, T, U> {
        pub fn new(original: &'a mut T, proj: Projector<T, U>) -> Self {
            Self { original, proj }
        }
        
        pub fn get_original(&mut self) -> &mut T {
            &mut self.original
        }
    
        pub fn get_derived(&mut self) -> &mut U {
            (self.proj)(&mut self.original)
        }

        pub fn projector(&mut self, f: Projector<T, U>) {
            self.proj = f;
        }
    }
}

use borrow_from::BorrowFrom;

fn use_bf(bf: &mut BorrowFrom<'_, Vec<i32>, i32>) {
    let derived = bf.get_derived();
    println!("{}", derived);
    *derived = 76;
    bf.projector(|orig| &mut orig[1]);
    let derived_again = bf.get_derived();
    println!("{}", derived_again);
    *derived_again = 54;
    println!("{:?}", bf.get_original());
}

fn main() {
    let mut v = vec![123, 45, 67, 89];
    let mut bf = BorrowFrom::new(
        &mut v,
        |orig| &mut orig[2],
    );
    println!("{:?}", bf.get_original());
    use_bf(&mut bf);
}

Playground

9

Yes, that's basically what I want. The only difference, and the reason I went toward unsafe code in the first place, was that I'd prefer to only have to call the projection function when it's first set, rather than every time get_derived is called.

10

In Rust &mut is an exclusive temporary loan. Think of the mut not as mutable, but mutually-exclusive, like a mutex.

So you can't have parent-child references using exclusive temporary loans, because there could exist multiple children and they can't all claim to have exclusive access to the parent. Besides that the temporary loans also are a wrong tool for the job, because they have many other restrictions making their use in structs impossible in most cases.

In Rust parent/child relationships are done using Rc<RefCell<T>>. Rc is a shared reference without being restricted to a temporary scope, and RefCell allows mutability from multiple locations, checking exclusivity at runtime.

Rc<RefCell<T>> is almost the same thing as Arc<Mutex<T>>, but the Arc version can be used across threads.

2 Likes