Type parameters with generic lifetime parameters

language design
1

There's a use case which cannot be solved with current lifetimes.

There was a post about similar issue some time ago (CC Alfriadox).

So the problem. There's a trait, and we need a vtable-entry like function pointer to it.

trait MyObject<'a>: 'a {
    // We are using Cell<&'a u8> parameter so this argument could not be made raw pointer
    fn add(&self, other: Cell<&'a u8>) -> &'a [u8];
}

fn make_vtable_entry<'a, T: MyObject<'a>>() -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] {
  ???
}

Let's start with this simple version:

fn make_vtable_entry_wrong<'a, T: MyObject<'a>>() -> unsafe fn(*const (), Cell<&'a u8>) -> &'a [u8] {
    |x, y| {
        let x = &*(x as *const T);
        x.add(y)
    }
}

it works, but function is tied to lifetime of function parameter. We want to a function for<'b>.

The correct version would be:

fn make_vtable_entry<'a, T: MyObject<'a>>() -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] {
    #[cfg(doesnt_work)]
    |x, y| {
        let x = &*(x as *const T);
        // Error: lifetime of reference outlives lifetime of borrowed content
        x.add(y)
    };
    |x, y| {
        let x = &*(x as *const T);
        // This works, but requires transmuting every argument and return
        // to kill lifetimes.
        mem::transmute(x.add(mem::transmute(y)))
    }
}

What could work:

fn make_vtable_entry<T<'a>: MyObject<'a>>() -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] {
    |x, y| {
        let x = &*(x as *const T<'_>);
        x.add(y)
    }
}

That would be a new language feature: function type parameters with lifetime parameters.

The same problem could be solved if we pass GAT which exposes T instead of T, like:

trait MyObjectConstructor {
  type MyObject<'a>: MyObject<'a>,
}

but having to write higher kinder trait for each implementation of MyObject and having to pass it explicitly in many functions is somewhat unergonomic.

  • Edit: added unsafe to functions
  • Edit: changed function parameter to *const ()
2

What are you trying to assert with your input bounds? Your "correct version" with <'a, T: MyObject<'a>> only asserts that T can be used with the one particular lifetime 'a, which doesn't necessarily imply that add() can be called with any other lifetime 'b.

Also, make_vtable_entry() should return an unsafe fn(...), since it is UB to call it with anything other than a &T transmuted (or casted) into a &().

3

I get the feeling that the fact that your code examples are turning &() into &T might be distracting a lot from your main point here. At least that's my own experience reading your post :wink:

It's not even defined behavior in that case, unless T is a zero-sized type. Otherwise, the pointer you get from the &() doesn't have provenance over any memory, even if that reference was originally created from a &T.

1 Like
4

Your "correct version" with <'a, T: MyObject<'a>> only asserts that T can be used with the one particular lifetime 'a , which doesn't necessarily imply that add() can be called with any other lifetime 'b .

Why? 'a or 'b is just a symbol, generic lifetime parameter.

should return an unsafe fn(...)

This is not essential for explaining the problem, but thanks.

5

This is how vtables work: the accept a pointer like *const () and transmute them to actual type T.

6

Yes, there's a significant difference between *const () and &(). Using *const () (with pointer casts to turn *const T into it, and convert back later) would be fine.

1 Like
7

Yes, you are correct. I patched the post.

8

Are you aware of HRTBs? Seem like what you're after here might simply be something like

use std::cell::Cell;
use std::mem;

trait MyObject<'a>: 'a {
    // We are using Cell<&'a u8> parameter so this argument could not be made raw pointer
    fn add(&self, other: Cell<&'a u8>) -> &'a [u8];
}

fn make_vtable_entry<T: 'static + for<'b> MyObject<'b>>(
) -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] {
    |x, y| {
        let x = unsafe { &*(x as *const T) };
        x.add(y)
    }
}

Edit: Ah, neverming! You're saying that you don't want a single type T that implements all the MyObject<'b> trait bounds, but you want a whole family of types (parametrized by a single lifetime parameter) and create a combined "vtable entry" for that family, so to speak..

9

The problem is, the caller can choose 'a to be some short lifetime, then call the returned fn with 'b as a longer lifetime, even if T doesn't implement MyObject<'b>. To illustrate (Rust Playground):

use std::{cell::Cell, mem};

trait MyObject<'a>: 'a {
    fn add(&self, other: Cell<&'a u8>) -> &'a [u8];
}

fn make_vtable_entry<'a, T: MyObject<'a>>() -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8]
{
    |x, y| unsafe {
        let x = &*(x as *const () as *const T);
        mem::transmute(x.add(mem::transmute(y)))
    }
}

impl<'a> MyObject<'a> for &'a [u8] {
    fn add(&self, _other: Cell<&'a u8>) -> &'a [u8] {
        self
    }
}

fn main() {
    fn extend<'a>(slice: &'a [u8]) -> &'static [u8] {
        let add: for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] =
            make_vtable_entry::<'a, &'a [u8]>();
        let add: unsafe fn(*const (), Cell<&'static u8>) -> &'static [u8] = add;
        let ptr = &slice as *const _ as *const ();
        // SAFETY: `ptr` points to a valid `&'a [u8]`.
        unsafe { add(ptr, Cell::new(&0)) }
    }
    let vec: Vec<u8> = b"Hello, world!".to_vec();
    let slice: &'static [u8] = extend(&vec);
    drop(vec);
    assert_eq!(slice, b"Hello, world!"); // assertion failed
}
10

I experimented a bit how much the ergonomics could be improved with macros. This is what I came up with.

Rust Playground

In this particular case it might be easier / more straightforward to replace the whole make_vtable_entry by a macro instead that accepts an argument like ...!(|'a| Foo<'a>)) or ...!(|'a| Baz<'a, T>))

11

You wrote incorrect extend function signature, so obviously code is wrong. The problem explained here:

        // this is correct
        let add: unsafe fn(*const (), Cell<&'static u8>) -> &'static [u8] = add;
        // this is also correct
        let ptr = &slice as *const _ as *const ();
        // The problem is here: add function first parameter expects
        // &'static [u8] hidden as *const (), but `ptr` is not
        unsafe { add(ptr, Cell::new(&0)) }
12

T is not 'static.

Generally code is meant to be used like this:

struct MyObjectCustomDyn<'a> {
  ptr: &'a (),
  vtable: MyObjectVTable,
}

// Here we cannot require `T: 'static`
fn make_custom_dyn<'a, T: MyObject<'a>>(a: &'a T) -> MyObjectCustomDyn<'a> { ... }

(For the context, custom dyn is needed because current dyn implementation does not allow placing constants in vtable along with function, and calling a function to fetch a constant is performance hit).

13

I appreciate the effort. This function I'm talking about is to be used after several levels of abstractions. Macros are not an option. Code currently is used like this:

struct MyHeap {
  // We'd want to avoid explicitly specifying type constructor here (and in other places)
  fn allocate<'a, T: MyObject<'a>>(&'a mut self, object: T) -> MyObjectCustomDyn<'a> { ... }
}

Currently we use DynMetadata instead of constructing custom vtable. But as I described before, we also need constants in vtable which is not currently possible in rust.

14

I merely explored how implementing a trait like MyObjectConstructor (and passing such constructor type to a function) can be made more ergonomic with macros, since you said the approach would work but be unergonomic. So I would be surprised if this couldn't be used for some improvement (over the "unergonomic" solution you mentioned). Edit: On a second read, maybe you're actually saying that having to pass the type constructor to functions is the unergonomic part. The sentence “having to write higher kinder trait for each implementation of MyObject and having to pass it explicitly in many functions is somewhat unergonomic” is somewhat ambiguous as to which part of the process is how much hassle.

Arguably you might need to explicitly specify type constructors in order to specify which parameter to abstract over, even if they are made a language feature. Of course this requirement would be depending on the precise design of such a feature. (Of course you wouldn't need the dummy value anymore, or the explicit handling of "captured" type/lifetime variables and their where clauses.)

15

(NOT A CONTRIBUTION)

What you're asking for is higher kinded types: in your example, T<'a> is a higher kinded type (parameterized by a lifetime).

The problem with higher kinded types is the currying problem: suppose we try to substitute &'x &'y i32 as the parameter for T<'a>; is should 'a be 'x or 'y? Inferring this automatically is intractable. GATs avoid this problem, because you would have to specify using the GAT impl.

Haskell, in contrast, solves this with currying - all arguments are applied in a specific order (left to right), so it can be inferred that 'a is 'x You would need to define some sort of type alias I think to be able to make 'a equal to 'y instead. But Haskell uses currying throughout the language, whereas Rust otherwise has no such restrictions; artificially applying this restrictions to higher kinded parameters was considered too surprising, so the intention (previously) was just to have GATs. I would use GATs for this use case.

16

If it cannot be inferred, it need to be specified explicitly. But in majority of cases it can be inferred.

I would use GATs for this use case.

If we switch to GAT we are cursed (I think) to pass GAT everywhere the function is used. It is a lot of code on both sides: there implementations of MyObject are defined (and some of them are generic, so macros won't work).

For example, there's a generic implementation like:

struct Foo<'v, V: 'v> { ... }

impl MyObject<'v, V: 'v> Foo<'v, V> { ... }

// And how I need to implement GAT also for parameters of implementations of MyObject
struct FooType<V: VConstructor> { ... }

impl<V: VConstructor> MyObjectConstructor for FooType<V> {
  type MyObject<'v> = Foo<'v, VConstructor::V<'v>>;
}

trait VConstructor {
  type V<'v>;
}

impl VConstructor for ... { ... }

and all of this machinery is just to substitute lifetime parameter in one place deep down in the library. Abusing lifetimes with mem::transmute is way easier.

(NOT A CONTRIBUTION)

What does it mean?

17

For this specific case, since you're doing manual type erasure which is wildly unsafe already, I think it's fine if you have to transmute away some lifetimes to make it work. You only need a single transmute to make the pointer type more general:

pub trait MyObject<'a>: 'a {
    fn add(&self, other: Cell<&'a u8>) -> &'a [u8];
}

pub fn make_vtable_entry_concrete<'a, T: MyObject<'a>>(
) -> for<'b> fn(&'b T, Cell<&'a u8>) -> &'a [u8] {
    |x, y| x.add(y)
}

pub fn make_vtable_entry_erased<'a, T: MyObject<'a>>(
) -> for<'b> unsafe fn(*const (), Cell<&'b u8>) -> &'b [u8] {
    unsafe { mem::transmute(make_vtable_entry_concrete::<T>()) }
}

IIUC this makes no more assumptions than already introduced by using manual vtables.

Given that "lifetimes don't exist," though, I do think lifetime-specific HKT could be reasonable, the same way that we already allow for<'a> in other positions. That could look like

pub fn make_vtable_entry<for<'a> T<'a>: MyObject<'a>>(
) -> for<'a, 'b> fn(&'b T<'a>, Cell<&'a u8>) -> &'a [u8] {
    |x, y| x.add(y)
}

This would have to be called with an explicit turbofish, e.g.

make_vtable_entry::<for<'a> &'a u8>()

Your HKT signature cannot work for Foo as written, though, @stepancheg, as in the body of make_vtable_entry you can name T<'static> which may not be valid Foo<'v, V> for non-'static V. There needs to be an extra 'bound lifetime, which is where all of the additional complexity is coming from, e.g.

pub fn make_vtable_entry<'bound, for<'a where 'bound: 'a> T<'a>: MyObject<'a>(
) -> for<'a, 'b where 'bound: 'a> fn(&'b T<'a>, Cell<&'a u8>) -> &'a [u8] {
    |x, y| x.add(y)
}
make_vtable_entry::<'v, for<'a where 'v: 'a> Foo<'a, V>>()

or perhaps use '_ for single-lifetime sugar. The for<where> syntax is from Extending `for<'a>` construct.

I tried to explicitly reify this with GAT, but ran into a cryptic lifetime bound not satisfied error that doesn't even provide the source of the bound.

pub trait TMyObject<'bound> {
    type Apply<'a>: MyObject<'a>
    where
        'bound: 'a;
}

pub fn make_vtable_entry<'bound, Kind: TMyObject<'bound>>(
) -> for<'a, 'b> fn(&'b Kind::Apply<'a>, Cell<&'a u8>) -> &'a [u8] {
    |x, y| x.add(y)
}

pub struct Foo<'v, V: 'v> {
    // invariance for maximum pessimism; I tried covariance as well
    _phantom: PhantomData<fn(&'v V) -> &'v V>,
}

impl<'v, V: 'v> TMyObject<'v> for Foo<'v, V> {
    type Apply<'a> = Foo<'a, V>
    where
        'v: 'a;
}

impl<'v, V: 'v> MyObject<'v> for Foo<'v, V> {
    fn add(&self, _other: Cell<&'v u8>) -> &'v [u8] { unimplemented!() }
}

pub fn make_foo_vtable_entry<'v, V: 'v>(
) -> for<'a> fn(&'a Foo<'v, V>, Cell<&'v u8>) -> &'v [u8] {
    make_vtable_entry::<'v, Foo<'v, V>>()
}
18
1 Like
19

I also tried the standard GAT workaround, where you put _Outlives = &'a Self on MyObject and write T: for<'a> MyObject<'a>. However, this still doesn't work, since the output for<'a> can't be restricted to the lifetime of T (without adding extra dummy parameters, which creates its own mess). Also, the compiler can't seem to infer that T: MyObject<'a> implies T: 'a.

20

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