Field projection for Rc and Arc

Given an Rc (or Arc) of a struct, the fields of the struct share the lifetime of the struct, so therefore it should be safe to create an Rc of a field of struct from an Rc of the struct. In more concrete terms, the following type signature should be safe:

impl<A> Rc<A> {
    fn project<'a, B>(self, project_fn: fn(&'a A) -> &'a B) -> Rc<B>;
}

This applies to Arc as well.

In reality, this type signature is not possible to create because of the structure of the Rc. Since the pointer of Rc points to the reference count as well as the data pointer, we'd need to create a separate type to make this work in reality - something like ProjectedRc. This struct would function exactly the same as Rc, but have separate pointer for data. Based on the signature above, substituting the identity function for project_fn yields a ProjectedRc from an Rc that points to the original data.

I think it is also possible to restructure Rc to allow for this sort of thing with no extra cost.

Use case

If you have a struct that satisfies some trait T and a field of that struct that also satisfies some trait T, it should be possible to store both the field and the struct in the same ProjectedRc<dyn T>, without storing the field as an Rc.

Okay, but how useful is this really?

Frankly, no idea. But. I really like the idea!

1 Like

ProjectedRc would need to contain a pointer usable to get the reference count, a pointer to the projected field and a function pointer that can be used to drop the data once the reference count reaches zero.

If you wanted to erase the type of the original struct, yes. However, you could also define ProjectedRc as follows:

struct ProjectedRc<Original, Projected> { 
     orig_ptr: NonNull<RcBox<Original>>,
     proj_ptr: *const Projected,
}

It's potentially useful. The general form of this is the "aliasing constructor" for shared_ptr in C++.

1 Like

A general instance of this in the wild is Bytes, used in networking stacks, where it's significantly easier to pass around owning handles rather than borrowed handles.

(This would be ProjectedArc<[u8], [u8]>.)

2 Likes

You would obviously need a HRTB callback for soundness, not like this where the caller can choose the lifetime. This capability is a lot like owning_ref::RcRef, though I don't really like that crate at the moment because of the high number of unfixed soundness issues. Actually.. reading through my very own open issue there, I think that even a simple change to HRTB callback in the API above might still leave the same soundness issue as owning_ref#71; and possibly an approach like owning_ref#72 might be necessary, so the type becomes something like ProjectedRc<'a, T, A: 'a> (where T is the target type of the original underlying Arc). And now I need to double-check if/why lock_api::MappedRwLockReadGuard doesn't have the same issue... Edit: Ah, it's because that type has a lifetime parameter, too!

The owning_ref example uses a FnOnce so I don't think a for<'a> is necessary? This requires a function pointer so unless I'm mistaken they're equivalent. You could substitute a lifetime that outlives 'a, but I think that would be sound?

It wouldn't be sound. For example:

Your function can be &'static A -> &'static (), and stash the &'static A into a global static variable while returning a &'static () to some other static variable. Afterwards, you can drop the Rc<A> and still have access to the (potentially already freed) A through the global static variable that stored the &'static A.

Edit: Some code to be more clear

use once_cell::sync::Lazy;
use std::sync::Mutex;

// stub implementation
struct Rc<A>(A);
impl<A> Rc<A> {
    fn project<'a, B>(self, project_fn: fn(&'a A) -> &'a B) -> Rc<B> {
        todo!()
    }
}

fn exploit() {
    struct A;
    let r: Rc<A> = todo!(); // somehow create the `Rc`
    static VAR: Lazy<Mutex<Option<&'static A>>> = Lazy::new(<_>::default);
    static UNIT: () = ();
    fn callback(r: &'static A) -> &'static () {
        *VAR.lock().unwrap() = Some(r);
        &UNIT
    }
    let r = r.project(callback);
    drop(r);
    // still able to read the &A:
    let x: &A = VAR.lock().unwrap().unwrap();
}

Oh, I understand now. So the correct form would be:

impl<A> Rc<A> {
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> Rc<B>;
}

You can't even get the original version to compile, for obvious reasons.

Well, yes.. except there's still the concern of


Edit: I'm not yet sure if it's really possible to exploit the issue when the API only supports fn instead of FnOnce.

I don't think that this exact issue is possible due to the deliberate requirement of having project_fn be a function pointer, and therefore unable to capture its environment except for items that are 'static. This was a deliberate design decision

Edit: And I don't think the issue you pointed out previously is possible, because you wouldn't be able to store &'a A into a static unless 'a == 'static

Here is a follow up design that I think works pretty generally:

struct Projection<Orig, Proj> { 
    orig: Orig,
    proj: *const Proj,
}

impl<T> Arc<T> { 
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> Projection<Arc<T>, B>;
}

impl<T> Rc<T> { 
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> Projection<Rc<T>, B>;
}

impl<O, P> Deref for Projection<O, P> 
where 
    O: Deref,
{
    type Target = P; 
    fn deref(&self) -> Self::Target;
}

// Similar implementations for DerefMut and other traits

I think it's still unsound. This is what I got; obviously untested because I don't have a "working" ProjectRc, but it compiles and hence should trigger UB if I'm not missing anything obvious:

use std::{cell::RefCell, rc::Rc};

// stub
struct ProjectRc<Orig, A>(Rc<Orig>, *const A);

impl<Orig> ProjectRc<Orig, Orig> {
    fn new(x: Rc<Orig>) -> Self {
        todo!()
    }
}

impl<Orig, A> ProjectRc<Orig, A> {
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> ProjectRc<Orig, B> {
        todo!()
    }
    fn deref(&self) -> &A {
        todo!()
    }
}

fn main() {
    let x = ProjectRc::new(Rc::new(()));
    let z: ProjectRc<(), String>;
    {
        let s = "Hello World".to_owned();
        let s_ref: &String = &s;
        let y: ProjectRc<(), RefCell<Option<&String>>> = x.project(|_| Box::leak(<_>::default()));
        *y.deref().borrow_mut() = Some(s_ref);
        z = y.project(|ref_cell| Box::leak(Box::new(ref_cell.borrow())).unwrap());
    }
    println!("{}", z.deref()); // accessing `s` after it’s freed
}

(playground)

Edit: I could confirm it "works" by using owning_ref as an implementation :laughing:

struct ProjectRc<Orig, A>(owning_ref::RcRef<Orig, A>);

impl<Orig> ProjectRc<Orig, Orig> {
    fn new(x: Rc<Orig>) -> Self {
        ProjectRc(owning_ref::RcRef::from(x))
    }
}

impl<Orig, A> ProjectRc<Orig, A> {
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> ProjectRc<Orig, B> {
        ProjectRc(self.0.map(project_fn))
    }
    fn deref(&self) -> &A {
        &self.0
    }
}

So in conclusion, this confirms that using fn instead of FnOnce does not improve soundness :wink:

1 Like

Ah, I see. Oh well, it was a nice idea.

At least we can do what C++ does to shared_ptr? I mean we can create a data member pointer like type based on memoffset, then let map take that as a parameter to avoid the soundness issue.

To better demonstrate the above-mentioned solution that I know for this soundness issue, let me show the change in the code. Something like this should be sound, as far as I'm aware:

// note that `PhantomData<&'a A>` implies a bound `A: 'a`
// and this bound is crucial for soundness of `project`
struct ProjectRc<'a, Orig, A>(owning_ref::RcRef<Orig, A>, PhantomData<&'a A>);

impl<'a, Orig> ProjectRc<'a, Orig, Orig> {
    fn new(x: Rc<Orig>) -> Self {
        ProjectRc(owning_ref::RcRef::from(x), PhantomData)
    }
}

impl<'a, Orig, A> ProjectRc<'a, Orig, A> {
    fn project<B>(self, project_fn: for<'b> fn(&'b A) -> &'b B) -> ProjectRc<'a, Orig, B> {
        ProjectRc(self.0.map(project_fn), PhantomData)
    }
    fn deref(&self) -> &A {
        &self.0
    }
}

E.g. he same main function with this API results in

error[E0597]: `s` does not live long enough
  --> src\main.rs:26:30
   |
26 |         let s_ref: &String = &s;
   |                              ^^ borrowed value does not live long enough
...
30 |     }
   |     - `s` dropped here while still borrowed
31 |     println!("{}", z.deref()); // accessing `s` after it’s freed
   |                    --------- borrow later used here

The API could then further be changed to allow any FnOnce.

Arguably rather than putting this in std, it would probably be enough to fix the owning_ref crate properly, and then use that crate.

1 Like

A solution that does not involve adding the extra lifetime is the following:

impl<Orig, A> ProjectRc<Orig, A> {
    fn project<B>(self, project_fn: for<'a> fn(&'a A) -> &'a B) -> ProjectRc<Orig, B>
    where 
        B: 'static
    {
        todo!()
    }
}

I think that the only useful storage for ProjectRc is 'static, considering that they derive from Rc and Arc, which are both generally 'static. If this is the case, then A -> B cannot produce a non-'static type