How to define a safe interface for pointer transformation?

Say, I have a pointer p: NonNull<A>, and I want to provide a function map<B>(f: impl FnOnce(NonNull<A>) -> NonNull<B>) to transform p to another pointer q: NonNull<B>.

Is it possible to enforce that whenever p can be cast to a immutable/mutable reference, q can also be cast to a immutable/mutable reference? If so, how? If not, why?

The function type signature of map is not restricted and is free to redesign if needed.

Thanks for any help!

Not really, no. The ability of NonNull to be cast to a reference is not information that the Rust type system keeps track of; that is why performing such a cast is unsafe. You could mark map as unsafe as well, and document the invariant.

But maybe this is an XY problem—what is your overall goal here?

"casting" a pointer to reference is done by deref the pointer then re-borrow, that's not really a cast per se. in rust, deref a pointer is always unsafe, because pointer types themselvs provide no guarantee to the type check where the pointer originated from. unsafe means the safety of the operation cannot be proved by rust's type checker, and the programmer is responsible for it.

since pointer cast is unrestricted (i.e. you can cast between pointers of unrelated types), in general, there's no way to guarantee a pointer to type A casted to a pointer to type B and is still a valid reference.

in your case, if the pointer is wrapped in a type which can guarantee the pointer is originated from a valid reference, and that the reference is still valid at the time the pointer is deref-ed, e.g. using a PhantomData marker, then it should be sound to deref the casted pointer, if proper trait bounds can guarantee there's no undefined behavior.

struct MyPtr<'a, T> {
    p: NonNull<T>,
    marker: PhantomData<&'a T>,
}

impl<'a, T> MyPtr<'a, T> {
    // only construct a MyPtr<T> through a valid reference
    fn new(p: &'a T) -> Self {
        MyPtr {
            p: NonNull::new(p as *const T as *mut T).unwrap(),
            marker: PhantomData,
        }
    }
    // can impl `Deref` or `AsRef` as needed
    // note: not return ref with 'a lifetime,
    // can be elided but just want to be explicity here
    fn as_ref<'r>(&'r self) -> &'r T {
        unsafe { self.p.as_ref() }
    }
    // this consumes self
    fn into_ref(self) -> &'a T {
        unsafe { self.p.as_ref() }        
    }
}

impl<'a, A> MyPtr<'a, A> {
    fn map<B>(self) -> MyPtr<'a, B> where A: AsRef<B> {
        // destruct self
        let Self {mut p,..} = self;
        // reborrow
        let p = unsafe {p.as_ref()};
        // do the pointer cast through the trait AsMut
        // prevent UB when the new pointer is `deref`-ed
        let p = p.as_ref() as *const B as *mut B;
        MyPtr {
            p: NonNull::new(p).unwrap(),
            marker: PhantomData,
        }
    }
}

@Jules-Bertholet @nerditation I will provide more information.

I am implementing a smart pointer which combines Rc and RefCell, and without any lifetime parameter. That involves threes types: BoxRef, ImRef, MutRef.

  • BoxRef just keeps the pointer, it cannot read or write. It is useful to keep a pointer when there is a MutRef which has exclusive access to the shared data
  • ImRef has immutable access to the shared data and it increases reference count, so the lifetime parameter can be avoid.
  • MutRef has mutable access to the shared data and it increases reference count, so the lifetime parameter can be avoid.
  • We can get a BoxRef from a BoxRef, a ImRef or a MutRef.
  • We can get a ImRef from a BoxRef if there is no MutRef or from a ImRef.
  • We can get a MutRef from a BoxRef if there is no ImRef.

Now I want to make them mappable, just like Ref, RefMut. It is easy to make ImRef or MutRef mappable because I can cast the pointer to a reference and provide a map function with reference in reference out. But how can I implement it with BoxRef? Because casting a pointer in BoxRef to a reference is undefined behavior when there is a MutRef.

I don't think you can offer a safe API for this map in the general case. However, you may be able to make use of the offset_of! macro (not yet stable, was just merged into Rust a few days ago) to offer a macro that can handle the most simple cases without unsafe.


Tangentially, is Rc<RefCell<T>> not enough for your use-case?

Yes, not enough. My use-case is very dynamical, so I can't involve any lifetime.

Rc<RefCell<T>> doesn't have a lifetime parameter?

But Ref, and RefMut have a lifetime parameter.

You could potentially store the mapping function to be applied after the lock is taken:

struct UnlockedImRef<T> {
    access: Box<dyn Fn()->ImRef<T>>
}

impl<T> BoxRef<T> {
    pub fn im(&self)->UnlockedImRef<T> {
        self.map_im(|x| x)
    }
    
    pub fn map_im<U>(&self, f:impl Fn(&T)->&U)->UnlockedImRef<U> {
        let box_ref = self.clone();
        let access = Box::new(move || {
            box_ref.borrow().map(f)
        }
        UnlockedImRef { access }
    }
}

impl<T> UnlockedImRef<T> {
    pub fn borrow(&self)->ImRef<T> {
        (self.access)()
    }
}

// And similar for `UnlockedMutRef`

Thans! This can be a backup resolution. And maybe this is the only safe resolution.

struct BoxRef<T, U> {
    ptr: NonNull<SharedCell<T>>,
    map: Box<dyn FnOnce(&T) -> &U>,
}

When we new a BoxRef, we set the map to a identity function, then we impl map as

impl<T,U> BoxRef<T, U> {
    fn map<V>(self, f: impl FnOnce(&U) -> &V)  -> BoxRef<T, V> {
        BoxRef {
            ptr: self.ptr,
            map: |t| f(self.map(t)),
        }
    }
}

And when we get a ImRef from BoxRef successfully, we can apply the map immediately.

1 Like

If you want BoxRef to be cloneable & reusable, you'll probably want map: Rc<dyn Fn(&T)->&U> instead.

You also can't use the BoxRef::map field to create a mapped MutRef because of the &s. You can, of course, also have a similar map_mut field but it may be hard to keep them in sync— That's why my example introduced a new UnlockedImRef type. (Also to remove the origin type parameter T, so that downstream code doesn't need to care what kind of BoxRef is responsible for storing the U that's being accessed).

Removing the origin type parameter T is what I want too, but I can't remove it.
Because I need to avoid lifetime parameter, every instance of BoxRef, ImRef, MutRef, or whatever types involved, need to increase reference count. That means, every type involved needs to care about data dropping when self is dropped, so we need the origin type parameter T to drop the data of type T.

They all need to be able to drop something of type T, yes, but it doesn't necessarily follow that they have to carry it around as a type parameter. You can erase the type by hiding the details inside some kind of trait object, which will dispatch to the correct drop implementation.

Actually, I want map: ImRef<dyn Fn(&T) -> &U> :laughing:
And I care about the memory usage.
Anyway, this is a direction. I will try to refine this resolution.

I ended up playing with this problem all morning; here's what I came up with. I've only done minimal testing, but Miri seems ok with everything so far.

(see link for details)

trait Opaque {}
impl<T> Opaque for T {}

struct SharedBox<T:?Sized = dyn Opaque> {
    ref_count: usize,
    imm_count: usize,
    mut_count: u8,
    data: UnsafeCell<T>
}

impl<T:?Sized> SharedBox<T> {
    fn new(init: T)->*mut Self where T:Sized;
    unsafe fn inc_ref(this: *mut Self)->usize;
    unsafe fn dec_ref(this: *mut Self)->usize;
    unsafe fn try_borrow(this:*mut Self)->Result<usize,()>;
    unsafe fn unborrow(this:*mut Self)->usize;
    unsafe fn try_borrow_mut(this:*mut Self)->Result<u8,()>;
    unsafe fn unborrow_mut(this:*mut Self)->u8;
    unsafe fn payload(this:*mut Self)->*mut T;
}

// ===================

pub struct RefBox<T>(*mut SharedBox<T>);

impl<T> Clone for RefBox<T> {}
impl<T> Drop for RefBox<T> {}

impl<T:'static> RefBox<T> {
    pub fn new(val: T)->Self where T:Sized;
    fn borrow_direct(&self)->Result<ImmRef<T>, ()>;
    fn borrow_direct_mut(&self)->Result<MutRef<T>, ()>;
    pub fn by_ref(&self)->ImmRefBox<T>;
    pub fn by_mut(&self)->MutRefBox<T>;
}

// ==================

pub struct ImmRefBox<T:?Sized>(ImmRef<dyn Fn()->Result<ImmRef<T>,()>>);

impl<T:?Sized> Clone for ImmRefBox<T> {}
impl<T:?Sized + 'static> ImmRefBox<T> {
    pub fn borrow(&self)->Result<ImmRef<T>,()>;
    pub fn map<U:?Sized + 'static>(&self, f:impl 'static + Fn(&T)->&U)->ImmRefBox<U>;
}

// ==================

pub struct ImmRef<T:?Sized> {
    storage: *mut SharedBox,
    ptr: *const T,
}

impl<T:?Sized> Clone for ImmRef<T> {}
impl<T:?Sized> Drop for ImmRef<T> {}
impl<T:?Sized> std::ops::Deref for ImmRef<T> {}
impl<T:?Sized> ImmRef<T> {
    fn map<U:?Sized>(this: &Self, f: impl FnOnce(&T)->&U)->ImmRef<U>;
}

// ==================

pub struct MutRefBox<T:?Sized>(ImmRef<dyn Fn()->Result<MutRef<T>,()>>);

impl<T:?Sized> Clone for MutRefBox<T> {}
mpl<T:?Sized + 'static> MutRefBox<T> {
    pub fn borrow(&self)->Result<MutRef<T>,()>;
    pub fn map<U:?Sized + 'static>(&self, f:impl 'static + Fn(&mut T)->&mut U)->MutRefBox<U>;
}

// ==================

pub struct MutRef<T:?Sized> {
    storage: *mut SharedBox,
    ptr: *mut T,
}

impl<T:?Sized> Drop for MutRef<T> {}
impl<T:?Sized> std::ops::Deref for MutRef<T> {}
impl<T:?Sized> std::ops::DerefMut for MutRef<T> {}
impl<T:?Sized> MutRef<T> {
    fn map<U:?Sized>(this: Self, f: impl FnOnce(&mut T)->&mut U)->MutRef<U>;
}
1 Like

Thank you very much! I have read through your code. The type parameter elimination trick is new to me and is very helpful! I think the framework could work, but I still need some time to decide whether to implement pointer transformation this way or should I do it. But anyway, thanks again!

I tried a while and found one drawback of your resolution.

We can't get a RefBox<T> from a ImmRef<T>, a ImmRef<U>, a MutRef<T> or a MutRef<U>, because of type parameter erasure. The ability to get a RefBox is important because it is the bridge to transform between ImmRef and MutRef.

Even without type parameter erasure, It's not possible to get a RefBox<P, T> from a ImmRef<P, T>, because the pointer to T is not guaranteed to be valid after all ImmRef<P, T> are dropped. And we can't recover the reference mapping function from just a pointer. Of course we can store the reference mapping inside ImmRef<P, T> to fix it, but I think it's not good.

Maybe letting RefBox mappable is not a good idea? I don't know. I'm still thinking about it.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.