Safe & generic self-referential types: Can it be done?

I've recently had an idea how to potentially realize safe, self-referential, generic types, but haven't quite figured out how to pull it off, because ultimately my knowledge about lifetimes is too limited I'm afraid.

The generic type I am envisioning is structured like this:

pub struct SelfRef<P, D> {
    // the dependent type must be dropped before its owner
    dependent: ManuallyDrop<D>, 
    // the owner must be pinned
    owner: Pin<P>,
}

Instances of this type can be created by passing some pinned value and a function pointer (not a closure!)

pub fn with<'a>(owner: Pin<P>, func: fn(&'a Pin<P>) -> D) -> Self {
    let dep = unsafe { func(&*(&owner as *const Pin<P>)) };
    Self {
        dependent: ManuallyDrop::new(dep),
        owner
    }
}

The lifetime 'a can be any lifetime, including 'static, which would even be preferable when the SelfRef is to be stored within another type. The reference to the pinned owner is converted into a raw pointer and then de-referenced so that its lifetime matches 'a.
The passed function can be used to create any dependent type, e.g. a MutexGuard<'a, T> that references the pinned owner, but we pretend the lifetime to be e.g. 'static, whereas it should actually be the unnameable lifetime 'self.

The trick would now be to ensure that no 'static reference can ever be allowed to escape from within the SelfRef, which is where I am having issues.
My idea was, to only allow accessing dependent through closures/function pointers which should be able to restrict the lifetimes of any returned references:

(all lifetimes are deliberately explicit)

// any returned type must be borrowed *at most* for 'a for this to be sound
pub fn map_ref<'a, U: 'a>(&'a self, func: fn(&'a D) -> U) -> U {
    func(&self.dependent)
}

However, it is possible to circumvent this by returning a reference to the static reference, which I believe is possible because 'static is a sub-type of all other lifetimes, and U: 'a can not prevent sub-typing.

#[derive(Default)]
struct Data {
    foo: u64,
    bar: i32,
    baz: f64,
}

struct View<'a> {
    foo: &'a u64,
    baz: &'a f64,
}

fn main() {
    let data = Box::pin(Data::default());
    // this should be fine, as long as the 'static references can never escape.
    let owning: SelfRef<Box<Data>, View<'static>> = SelfRef::with(data, |data| View {
       foo: &data.foo,
       baz: &data.baz,
    });
    
    // this does not compile, however...
    // let _foo: &'static u64 = owning.map_ref(|view: &View<'static>| -> &'static u64 { view.foo });
    
    // this does...
    let foo: &&'static u64 = owning.map_ref(|view: &View<'static>| -> &&'static u64 { &view.foo });
    let static_ref = *foo;
    mem::drop(owning);
    // and since the 'static has escaped, it is possible to access freed memory
    assert_eq!(*static_ref, 0);
}

Here's a link to the playground with the example code.

Is it possible to create a signature for the map_ref method that ensures that any returned references may be borrowed at most for the lifetime of &'a self, perhaps by returning some kind of contra-variant wrapper type?

The other potential achilles heel of my approach is the with function, since I'm not 100% that it is impossible to do funky stuff with the "fake" 'static reference to the pinned owner.

You can't have a "fake" 'static, as that will allow dangling references to escape. View<'static> is not the right lifetime, what we need is something like 'self, but that doesn't exist.

2 Likes

Actually, I think we can make this work somehow, playground

I added a unsafe trait OutlivedBy<'a>, while this is unsafe that the user must implement, it is actually really easy to make a proc-macro for it so it should be fine.

This trait exposes any inner lifetimes of whatever views you have, and this allows making an upper bound on the lifetimes through clever use of lifetime bounds.

In general you can implement OutlivedBy<'a> like so,

struct Foo<'a, 'b, 'c, ..., A, B, C, ...> {
    field_0: T,
    field_1: U,
    field_2: V,
    ...
}

unsafe impl<'new, 'a, 'b, 'c, ..., A, B, C, ...> OutlivedBy<'new> for Foo<'a, 'b, 'c, ..., A, B, C, ...>
where
    'new: 'a + 'b + 'c + ...,
    T: OutlivedBy<'new>,
    U: OutlivedBy<'new>,
    V: OutlivedBy<'new>,
    ... {}

This will always correctly expose the necessary lifetimes without being unnecessarily restrictive.

2 Likes

That looks really promising I think, although I can not claim to understand this solution, yet.
I will look into it further, but if it were possible to implement something like this completely generically with blanket implementations only, this would be an ideal solution.

I had more expected a solution could be found using Rust's variance and sub-typing rules, which I likewise do not understand thoroughly. Interestingly, it seems only possible to trivially specify a types lower lifetime bound using the T: 'a syntax, but not an upper bound.
I have a gut feeling that it should be possible, though, using contra-variance rules.

// simplify D to always have "fake" 'static lifetime
impl<P, D: 'static> SelfRef<P, D> {
    // ...
    // U needs to have an upper bound for `'s ` somehow
    pub fn map_ref<'s, U: 's>(&'self, func: fn(&'s D) -> U) -> U {
        // ....
    }
}

All I would need is a way to ensure that U can not outlive 's and then it could be any type, not only a reference.

An even better solution I think would be to simply transmute the dependent type back to the appropriate lifetime 'a before handing a reference to the closure, but alas, this is not possible in Rust, at least not generically.
I can easily transmute a concrete type View<'static> to View<'a>, but there isn't even syntax for expressing such a thing generically, I believe. Perhaps GAT will allow something like this?