Rc::map attempt two, rustc can't tell lifetimes are related?

1

In the spirit of Ref::map I am trying to define a Rc::map. Given a Rc<T>, the map operation would let you produce a RcMap<S> which contains a clone of the Rc<T>, guaranteeing that the original T stays alive as the RcMap<S> exists, and making it safe for the S object to refer to the T object without an explicit lifetime.

The shared-rc crate and mappable_rc crates both provide this operation already, but they require the closure passed in to map to return a reference. I want to be able to map Rc<Vec<i32>> to RcMap<std::slice::iter<'static, i32>>. In other words I want to be able to return a type that wraps a reference rather than just direct references. Instead of returning &'a U I want to return U + 'a (and then erase the lifetime to be 'static so that it doesn't infect the RcMap).

I think I am 95% of the way there. I have a trait ConvertLifetime that can be used to define conversions via associated type between the 'static version of a type (e.g. std::slice::Iter<'static, i32>) and the non-static version (e.g. std::slice::Iter<'a, i32>). I use this in the signature of the map operation and rustc seems happy with it.

The issue is when I try to actually use the map operation as defined the error message makes it sound like rustc forgets that myvec and myvec.iter() have related lifetimes. If I define a standalone function that's not generic that does the same thing as the closure I pass into map, I get no error (see this_is_allowed function below). Why doesn't this compile?

#![allow(dead_code)]
#![allow(unused_variables)]

use std::rc::Rc;

trait ConvertLifetime<'a, 'b> {
    type Type;
}

impl<'a, 'b, T: 'a + 'b> ConvertLifetime<'a, 'b> for std::slice::Iter<'a, T> {
    type Type = std::slice::Iter<'b, T>;
}

impl<'a, 'b, T: 'a + 'b> ConvertLifetime<'a, 'b> for &'a T {
    type Type = &'b T;
}

trait RcMapping {
    fn map<'a, U: 'a + ConvertLifetime<'a, 'static>, F: FnOnce(&Self) -> U>(
        self: &Rc<Self>,
        f: F,
    ) -> RcMap<Self, U::Type>;
}

/// Taken from the transmute crate. `std::mem::transmute` complains
/// that the source type is not Sized even when it is if the type is generic.
///
/// # Safety
/// See docs for `std::mem::transmute`.
#[inline]
pub unsafe fn transmute<A, B>(a: A) -> B {
    let b = ::core::ptr::read(&a as *const A as *const B);
    ::core::mem::forget(a);
    b
}

impl<X> RcMapping for X {
    fn map<'a, U: 'a + ConvertLifetime<'a, 'static>, F: FnOnce(&Self) -> U>(
        self: &Rc<Self>,
        f: F,
    ) -> RcMap<Self, U::Type> {
        RcMap {
            parent: self.clone(),
            data: unsafe { transmute::<U, U::Type>(f(self)) },
        }
    }
}

struct RcMap<P: ?Sized, T> {
    parent: Rc<P>,
    data: T,
}

#[allow(clippy::ptr_arg)]
fn this_is_allowed<'a>(x: &'a Vec<i32>) -> std::slice::Iter<'a, i32> {
    x.iter()
}

fn why_is_this_not() {
    let x = Rc::new(vec![1, 2, 3]);

    // AFAICT the map closure is doing the same thing as
    // `this_is_allowed`. rustc seems to think that the lifetime of
    // `x` and `x.iter()` are unrelated?
    let y = x.map(|x| x.iter());
}

Produces the error:

  --> src/lib.rs:64:23
   |
64 |     let y = x.map(|x| x.iter());
   |                    -- ^^^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                    ||
   |                    |return type of closure is std::slice::Iter<'2, i32>
   |                    has type `&'1 std::vec::Vec<i32>`
2

You might be re-inventing yoke - Rust more-or-less?

3

Is the idea that RcMap<S> would deref to S? Because if so that's not going to work, you could get a &'static i32 out of the RcMap<std::slice::Iter<'static, i32>> and it would end up dangling after you dropped the RcMap and the original Rc.

4

No, there's no deref impl. Instead, it provides fn RcMap<Ref<'static, T>>::get<'a>(&'a self) -> &'a Ref<'a, T>, "rehydrating" the yoked type by putting the shorter lifetime back in.

You're missing the unsafe requirement that the yoked type is covariant, i.e. that it's safe to convert Ref<'long> to Ref<'short>.

The problem is that in fn map, 'a is some lifetime which outlives the call to map, but you want 'a to be the lifetime of the output of f and borrow from the input of f.

What you need is to change the generic to U: for<'a> ConvertLifetime<'a, 'static> to say that you can convert the lifetime between any 'a and 'static.

This implementation is at best problematic. Because a is passed to forget after creating b, this could invalidate borrows in b. The correct ordering is to suppress a's drop first with ManuallyDrop and then transmute_copy from there.

But you shouldn't be using this at all, anyway. Put the functionality you need onto the trait, where the types are known!

unsafe trait CovariantLifetime<'short, 'long: 'short>: 'short {
    type Lengthened: 'long;

    fn shorten(this: Self::Lengthened) -> Self;
    unsafe fn lengthen(this: Self) -> Self::Lengthened;
}

unsafe impl<'short, 'long: 'short, T: 'long> CovariantLifetime<'short, 'long>
    for std::slice::Iter<'short, T>
{
    type Lengthened = std::slice::Iter<'long, T>;

    fn shorten(this: Self::Lengthened) -> Self {
        this
    }

    unsafe fn lengthen(this: Self) -> Self::Lengthened {
        std::mem::transmute(this)
    }
}

unsafe impl<'short, 'long: 'short, T: 'long> CovariantLifetime<'short, 'long>
    for &'short T
{
    type Lengthened = &'long T;

    fn shorten(this: Self::Lengthened) -> Self {
        this
    }

    unsafe fn lengthen(this: Self) -> Self::Lengthened {
        std::mem::transmute(this)
    }
}

The implementation will be the same shape for all implementing types which aren't themselves generic over CovariantLifetime types. If this implementation compiles (and the associated type correctly replaces just the lifetime), then it should always be sound.

It could be possible to simplify the trait a bit by flipping it to be implemented on the long-lived version instead, allowing you to remove one of the lifetimes from the trait and put it onto the now generic associated type, e.g. type Shortened<'short> where Self: 'short. This may also help out type inference (or maybe it will, but only without the GAT).

Yes, and I've said as much previously. RcMap<P, T> is exactly Yoke<T, Rc<P>>. (The inconsistent type ordering you're using is very difficult to track, @jgarvin.)

See the bounds on Yoke::attach_to_cart for comparison. And then just implement RcMap by using Yoke to avoid reinventing what already exists and is maintained by people with a deeper understanding of what's required to make the interface properly sound.

And I say this as the publisher of shared-rc. I published that crate because it provides a meaningfully easier to use API by only working for yoking &T, most importantly by not dealing with the lifetime substitution. There's essentially no API or implementation simplification to be gained by restricting yoke to Rc carts.

Plus, both your partial implementation and shared-rc are probably vulnerable to the contravariant cart payload soundness hole. This is dangerously subtle territory.

3 Likes
5

Untested, but what you want is probably roughly

trait RcMap {
    fn map<Y, F>(self: Rc<Self>, f: F) -> Yoke<Y, Rc<Self>>
    where
        Y: for<'a> Yokeable<'a>,
        F: for<'a> FnOnce(&'a Self) -> <Y as Yokeable<'a>>::Output,
    {
        Yoke::attach_to_cart(self, f)
    }
}

impl<T> RcMap for T {}

Depending on the solution yoke adopts for the covariance attack, this might require an added 'static bound, but otherwise does what you want.

6

Nice… another crate to report soundness issues on :slight_smile:

3 Likes
7

sigh

I was questioning whether I should publish it when I did, and then again just recently when I remembered I had because of this (extended history) thread and fixed the fact that I had originally made it essentially unusable (except as a even huger soundness hole).

The answer is pretty clearly no, I didn't do it any better than the alternatives. Despite actively looking at the crate closest to getting it right.

I actually was going to ask you if you'd check for the typical holes, but I wanted to finish my write-up on Unpin/aliasing first :upside_down_face:

1 Like
8

While the idea is indeed to only be able to get a more limited lifetime out does this prevent supporting Deref? Doesn't Deref tie the lifetime to &self so it should work out okay as long as Target is set to the more limited lifetime version... or I guess the problem is there's no way to refer to the lifetime you need to do that?

Oof yes, still not in the habit of thinking about this.

Could you elaborate? I know ManuallyDrop is the more up to date way to do this, but is there a set of inputs where this definition does the wrong thing?

I'm surprised Rust considers the types to be known here. I figure if std::mem::transmute is broken when T is a generic argument it should also be broken by std::slice::Iter<T>. How does it know the sizes match in this case? Because Self and Self::Lengthened only vary in lifetime, then it's smart enough to know the sizes are equal?

Ah but then how do I ever become one of those people? :slight_smile: I aspire to understand things well enough to follow that soundness hole discussion :wink:

9

This makes sense to me, and I gave this a try, but I get the same error still. I'd like to understand why what I have doesn't work before I try switching over to your version of the trait, figure there's something for me to learn here....

Playground link

#![allow(dead_code)]
#![allow(unused_variables)]

use std::rc::Rc;

trait ConvertLifetime<'a, 'b> {
    type Type;
}

impl<'a, 'b, T: 'a + 'b> ConvertLifetime<'a, 'b> for std::slice::Iter<'a, T> {
    type Type = std::slice::Iter<'b, T>;
}

impl<'a, 'b, T: 'a + 'b> ConvertLifetime<'a, 'b> for &'a T {
    type Type = &'b T;
}

trait RcMapping {
    fn map<'a, U: for<'b> ConvertLifetime<'b, 'static>, F: FnOnce(&Self) -> U>(
        self: &Rc<Self>,
        f: F,
    ) -> RcMap<Self, <U as ConvertLifetime<'a, 'static>>::Type>;
}

/// Taken from the transmute crate. `std::mem::transmute` complains
/// that the source type is not Sized even when it is.
///
/// # Safety
/// See docs for `std::mem::transmute`.
#[inline]
pub unsafe fn transmute<A, B>(a: A) -> B {
    let b = ::core::ptr::read(&a as *const A as *const B);
    ::core::mem::forget(a);
    b
}

impl<X> RcMapping for X {
    fn map<'a, U: for<'b> ConvertLifetime<'b, 'static>, F: FnOnce(&Self) -> U>(
        self: &Rc<Self>,
        f: F,
    ) -> RcMap<Self, <U as ConvertLifetime<'a, 'static>>::Type> {
        RcMap {
            parent: self.clone(),
            data: unsafe { transmute::<U, U::Type>(f(self)) },
        }
    }
}

struct RcMap<P: ?Sized, T> {
    parent: Rc<P>,
    data: T,
}

#[allow(clippy::ptr_arg)]
fn this_is_allowed<'a>(x: &'a Vec<i32>) -> std::slice::Iter<'a, i32> {
    x.iter()
}

fn why_is_this_not() {
    let x = Rc::new(vec![1, 2, 3]);

    // AFAICT the map closure is doing the same thing as
    // `this_is_allowed`. rustc seems to think that the lifetime of
    // `x` and `x.iter()` are unrelated?
    let y = x.map(|x| x.iter());
}

Error:

error: lifetime may not live long enough
  --> src/lib.rs:65:23
   |
65 |     let y = x.map(|x| x.iter());
   |                    -- ^^^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                    ||
   |                    |return type of closure is std::slice::Iter<'2, i32>
   |                    has type `&'1 std::vec::Vec<i32>`
10

The issue is that Deref::Target is not a GAT. The Target type returned from a dereference must be derived solely from the Self type and cannot itself borrow from Self. The simple failure case to see is by clone()ing the dereferenced value; now you have Iter<'static, T>. It's the exact same problem class as lending iterators.

For a uniquely referencing type like Box or &mut, moves count as a "use" and invalidate derived pointers. I don't know if this would ever cause an issue in practice -- the transmute_copyd value is an exact copy, after all -- but it could be, and ManuallyDrop is unambiguously good... [probably; it's at least intended to be].

Slowly, incrementally, and with great care. And a lot of free help from observing people like @steffahn poke soundness holes in other peoples' and your own APIs. In a specific case like self-referencing abstractions, looking at all of the soundness issues (both unfixed and fixed) reported against other instances of the pattern, and understanding both what the hole is and what the proposed/implemented fix is, if any.

It's probably at least related to the fact that F: for<'f> FnOnce(&'f Self) -> U, a completely unrelated lifetime to your input 'a, and in fact constrained to not escape the definition of map, but 'a must cover the entire definition of map.

A bit of playing showed that this direction of the trait doesn't want the for<'b> ConvertLifetime; you have a restriction that Iter<'a>: ConvertLifetime<'a, '_>, so the general for<'b> doesn't actually hold.

This function signature compiles:

trait RcMapping {
    fn map<'a, U: ConvertLifetime<'a, 'static>, F: FnOnce(&'a Self) -> U>(
        self: &'a Rc<Self>,
        f: F,
    ) -> RcMap<Self, <U as ConvertLifetime<'a, 'static>>::Type>
    where
        Self: 'a;
}

Note the wider use of 'a: every borrow of Self is given this lifetime. The caller of map chooses the lifetime 'a being used.

Though I still remain unconvinced of the correctness of the definition you're using. The development of yoke broke literal new ground in the compiler that used to not compile multiple times; the constraint being expressed is literally at the bleeding edge of Rust expressiveness and trying to properly comprehend the full implications is difficult.

The main issue with this direction of defining the trait on the 'short version instead of the 'static version of the yoke like the yoke crate is that the real bound we would like to express is for<'a> Iter<'a, T>: ConvertLifetime<'a, 'static>. That's not a thing which can be spelled generically, so we have to ask whether asserting the bound for each 'a we actually end up using is sufficient.

The "ideal" definition maybe looks like

unsafe trait Covariant {
    type Rebound<'a>;
    unsafe fn rebind<'a>(this: Self) -> Self::Rebound<'a>;
}

but this isn't writable yet.

2 Likes
11

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.