A trait object with an implied lifetime

1

Given a type like dyn Trait<W> + 'w, I am thoroughly convinced that there is no reason for the compiler to require that 'w contains all of the lifetime information in Self in cases where this information is already contained in W.

/// The compiler will guarantee that this type cannot outlive any
/// lifetime contained in W, because this type is invariant in W.
///
/// When we construct it unsafely in hide_lifetime(), we use W = Self.
pub type ImpliedLifetime<W> = Box<dyn Trait<W> + 'static>;

pub fn hide_lifetime<W: Trait<W>>(w: W) -> ImpliedLifetime<W> {
    unsafe {
        std::mem::transmute::<
            Box<dyn Trait<W> + '_>,
            Box<dyn Trait<W> + 'static>,
        >(Box::new(w))
    }
}

pub trait Trait<W> { fn method(&self); }

// this blanket impl was chosen to give you many types that
// do implement the trait bound, and many types that don't.
impl<W: ToString> Trait<W> for W {
    fn method(&self) { println!("{}", self.to_string()); }
}

I challenge anyone to invoke undefined behavior with this function. You're free to add any amount of safe code, including arbitrary trait impls. But you cannot change the code above. Here is a playground to get you started.

Why do I care? A hack like this is the only way I can achieve the perfect signatures I want for writing an NPY file, which only conditionally requires a Seek bound:

// simplified signatures; in the link above, these are Builder::begin_1d
//  and Builder::begin_nd
impl<W: Write> NpyWriter<W> {
    pub fn new_nd(w: W, shape: &[usize]) -> NpyWriter<W>;
    pub fn new_1d(w: W) -> NpyWriter<W> where W: Seek;
}

Without this, I have to settle for new_nd() -> NpyWriter<PanicSeek<W>> or new_1d() -> NpyWriter<'w, W> where W: 'w

1 Like
2

Any takers?

Has anybody seen this pattern? Basically I tried to replace a lifetime+type parameter <'w, W: 'w> with just a type parameter <W>.

3

This was my attempt at inducing a use-after-free, but it looks like your comment above the ImpliedLifetime typedef held.

struct Dodgy<'a> {
    s: &'a str,
}

impl<'a> Trait<Dodgy<'a>> for Dodgy<'a> {
    fn method(&self) {
        println!("{}", self.s);
    }
}

fn main() {
    let hello_world = String::from("Hello, World!");    
    let implied = hide_lifetime(Dodgy { s: hello_world.as_str() });    
    drop(hello_world);    
    implied.method();
}
4

From a lifetime perspective, Dodgy<'a> basically looks no different from &'a str.

This made me think of something, though, so I tried this:

impl<'a, 'b> Trait<Dodgy<'b>> for Dodgy<'a> {
    fn method(&self) {
        println!("{}", self.s);
    }
}

The compiler can still see clean through it, though. The W: Trait<W> bound on the function prevents it from picking two different lifetimes at the callsite.

5

The + 'static can be dropped.
Problem comes with extending risks adding error;

fn wrap<W>(good: ImpliedLifetime<W>) -> ImpliedLifetime<W> {
    struct Other<W> {
        b: ImpliedLifetime<W>
    };
    impl<W> implied::Trait<W> for Other<W> {
        fn method(&self) {
            println!("other");
        }
    }
    
    unsafe {
        std::mem::transmute::<
            Box<dyn implied::Trait<W> + '_>,
            Box<dyn implied::Trait<W>>,
        >(Box::new(Other{b:good}))
    }
}

Add a second structure and could be breaking some lifetime if not careful.
(If you don't extend no need for box and trait object.)

6

I'm not sure what you are showing here? AFAICT your wrap function is still safe. (though when I asked for examples of unsoundness I assumed it was implied that you couldn't add more unsafe!)

P.S. In my particular use case, nobody will be extending this. The trait is private and will only ever have one impl. However, I made it pub in this thread just because I was confident that the privacy was not integral to its safety.

7

Ok, I have done quite a bit of experimentation:

Observations (given trait Trait<T> {})

  • type F<'a, T> = dyn Trait<T> + 'a is covariant w.r.t. 'a, and invariant w.r.t. T;

  • for all lifetimes <'a, 'b>, and type <T>,
    dyn Trait<T> + 'a : 'b if and only if both 'a : 'b and T : 'b

So, with an imagined notation |T| for the infimum lifetime / "effective lifetime" of T,

  • i.e., T : |T| and for all 'a, T : 'a ⇒ |T| : 'a;

    • This assumes such thing exists (I fail to see why it wouldn't);

  • (since this cannot be written in Rust, in the playground I use T = LT<'a> = &'a (),
    so that |T| = |LT<'a>| = 'a);

then:

For all type <T> and lifetime <'a>,
|dyn Trait<T> + 'a| = intersect(|T|, 'a)

So, with an added 'a : |T| bound,

  • |dyn Trait<T> + 'a| = intersect(|T|, 'a) = |T|,

  • and, by covariance,
    dyn Trait<T> + 'static : dyn Trait<T> + 'a : dyn Trait<T> + |T|

So, since by covariance dyn Trait<T> + 'static subtypes both the parametric dyn Trait<T> + '_ and the ineffable dyn Trait<T> + |T|, and since they all have the same "effective lifetime",
dyn Trait<T> + 'static is indeed a non parametric way to name / express this "entity" without lifetime parameters;
therefore, hide_lifetime is sound (the '_ in the transmute being |W|).

If we were to be able to express that T : U (meaning that T : |U|), we could even make hide_lifetime a little bit more general:

pub fn hide_lifetime<W, T>(x: T) -> Box<dyn Trait<W> + 'static>
where
    T : Trait<W>,
    T : W, /* i.e. T : |W| */
{
    unsafe {
        mem::transmute::<
            Box<dyn Trait<W> + '_>,
             /* dyn Trait<W> + |W| */
            Box<dyn Trait<W> + 'static>,
        >(Box::new(x))
    }
}

For instance, if our Trait was generic over a lifetime instead of a type: trait Trait<'a> {},

pub fn hide_lifetime<'a, T>(x: T) -> Box<dyn Trait<'a> + 'static>
where
    T : Trait<'a>,
    T : 'a, /* if we had trait Trait<'a> : 'a {}, this bound would not even be necessary */
{
    unsafe {
        mem::transmute::<
            Box<dyn Trait<'a> + 'a>,
            Box<dyn Trait<'a> + 'static>,
        >(Box::new(x))
    }
}
5 Likes
8

Yup, this all sounds consistent with my own investigations with the borrow checker. Namely:

  • dyn Trait<T, Assoc=A> + 'a is covariant in 'a and invariant in T and A.
  • The effective lifetime of a type is a region that is a subset of each lifetime that appears in either a covariant or invariant position in the type.
    • There's no syntax to express this (even if you had a type SomeType<'a, 'b>, there's no operator that can construct the effective lifetime from 'a and 'b; 'a + 'b has the opposite meaning!)

It's nice to see somebody else digging into this space. Somehow I suspect that the concept of effective lifetimes does not actually exist in the compiler, but it's certainly an useful concept to talk about.

1 Like
9

Yep, we'd need an intersect('a, 'b) operator.

  • for two comparable / ordered lifetimes this would be the min operator;

Given that the combination of a : 'a bound with a : 'b bound can be written as the : 'a + 'b bound, the additive notation would indeed correspond to the union.

So for the intersection we could use the * operator notation (even if I find the ^
operator more intuitive).

Then the effective lifetime could be recursively defined as:

  • |&'a [mut] T| = 'a;

  • for a type constructor / generic type |Type<'_1, .., '_n, T1, .. Tm>| = '_1 * .. * '_n * |T1| * .. * |Tm|

    • so for a non generic type, this gives the 'static effective lifetime.
10

I might try to go even further and say that &'a [mut] T can be considered the same as Ref<'a, T> or Mut<'a, T>, and that |T| = 'static if T has no generic parameters.

However, last I recall the compiler seems to be pretty brutal about enforcing the T: 'a condition for references. I.e. I don't think it allows &'static &'a T to be produced even through transmute. My current understanding is that this is probably not necessary, but it does serve as a lint for some unsafe code. (in particular code dealing with unbound lifetimes)

11

Yes, for &'a [mut] T to be valid, T : 'a; current stable Rust (1.35.0) had even an ICE related to that.

Hence 'a = 'a * |T| = |Ref[Mut]<'a, T>|.

But yes, this case can actually be derived from the more general formula :slight_smile:

1 Like
12

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.