Converting an early bound lifetime in fn to late bound

[dovahcrow]

TL DR

A function fn foo<'a, T>(&'a mut T) where T: Trait<'a> makes the lifetime 'a early-bound. As a result, let f = foo<T> cannot be used in a place that requires late-bound lifetime 'a.

The solution is, wrap the function into a closure let f = |bar: &mut _| foo<T>, this closure will be an fn with late-bound 'a again.

Original post

Hi Rustaceans, recently I was building a project which requires to have an abstraction of a bytes buffer that can produce (parse) some type T.
The trait definition looks like this:

pub trait Produce<T> {
    fn produce<'b>(&'b mut self) -> Result<T>
    where
       // how to declare for all the lifetime in T, they are shorter than 'b?
}

I'd like to make T not only work for owned types but also borrowed types. This means all the lifetimes in T must be shorter than the self-borrow lifetime 'b. I know rust allows us to have a bound T:'b indicates all the references in T live longer than 'b. However, does rust provide similar syntax for the opposite?

Edit1

The original description was not complete to my whole problem. After discussing in the threads below, I think it would be better to put the whole problem here.

pub trait Produce<'a, T> {
    fn produce(&'a mut self) -> T;
}

// Get a function pointer of different type T based on flag
fn get_fptr(flag: bool) -> fn(p: &mut Foo) {
    fn inner<T>(p: &mut Foo)
    where
        for<'a> Foo: Produce<'a, T>,
        T: std::fmt::Debug
    {
        println!("{:?}", Produce::<T>::produce(p));
    }
    
    if flag {
        inner::<&str>
    } else {
        inner::<i32>
    }
}

pub struct Foo(String);

impl<'a> Produce<'a, i32> for Foo {
    fn produce(&'a mut self) -> i32 {
        1
    }
}

impl<'a> Produce<'a, &'a str> for Foo {
    fn produce(&'a mut self) -> &'a str {
        &self.0
    }
}


fn main() {
    let mut foo = Foo("bar".into());
    
    let fptrs = vec![get_fptr(true), get_fptr(false)];
    
    for _ in 0..10 {
        for &f in &fptrs {
            f(&mut foo)
        }
    }
}

The use case is that, there exists a produce trait to describe a producer, which can produce owned values and borrowed values (borrow from itself).

Now we'd like to store a bunch of function pointers based on a flag, where each of the function pointers calls the producer to produce a specific type of value.

However, the compiler is complaining about the lifetime.

@dovahcrow

error: implementation of `Produce` is not general enough
  --> src/main.rs:16:9
   |
1  | / pub trait Produce<'a, T> {
2  | |     fn produce(&'a mut self) -> T;
3  | | }
  | |_- trait `Produce` defined here
...
16 |           inner::<&str>
   |           ^^^^^^^^^^^^^ implementation of `Produce` is not general enough
   |
   = note: `Foo` must implement `Produce<'0, &str>`, for any lifetime `'0`...
   = note: ...but `Foo` actually implements `Produce<'1, &'1 str>`, for some specific lifetime `'1`

error: aborting due to previous error

Edit2

After some investigation, I think this might caused by that for<'a> Produce<'a,T> asks for a late bound lifetime however the implementation impl<'a> Produce<'a, &'a str> for Foo implicitly means where Self: 'a so that 'a becomes early bound. Does anyone aware of some tricks to make the impl late bound?

[arnaudgolfouse]

I don't think this is possible, I believe what you are asking is:

• For a fixed type T (and so a fixed lifetime)
• For any lifetime 'b
• You want T shorter than 'b

As written here, it seems complicated

However, maybe moving the lifetime bound would work ?

pub type Result<T> = std::result::Result<T, ()>;

pub trait Produce<'b, T> { // now 'b is here
    fn produce(&'b mut self) -> Result<T>;
}

impl<'b, T> Produce<'b, &'b mut T> for T {
    fn produce(&'b mut self) -> Result<&'b mut T> {
        Ok(self)
    }
}

[SkiFire13]

I don't think this exists, but even if it existed it wouldn't work with owned types. An owned T implies T: 'static, so if you want all the lifetimes in T to live less than 'b then you get that 'b must live longer than 'static and this would make the method pretty much useless.

[steffahn]

@dovahcrow

The trait definition looks like this:

pub trait Produce<T> {
    fn produce<'b>(&'b mut self) -> Result<T>
    where
       // how to declare for all the lifetime in T, they are shorter than 'b?
}

Even if Rust had a way to specify that “all lifetimes in T must be shorter than the lifetime 'b”, I’m having a feeling that the API you’re developing here might quite likely still be unsound. You’re not presenting the full picture here, so it’s hard to tell exactly what you’re trying to do.

[kornel]

No. That would declare dangling pointers, which is an error.

An object in Rust is not allowed to reference anything that lives shorter than itself, ever. If it could, it would mean the object can be still alive while one of references it contains is a dangling pointer, and that's a safety problem.

So everything that an object can access must live as long as the object, or longer.

A function that takes only &(mut) self as an argument can only lend things out of self, so it can only lend things that live as long as itself or longer.

Additionally, taking &mut self means exclusive borrow, so such function can return only one thing in the lifetime of the borrow (otherwise a next call to this function could delete whatever it has lent before).

Lifetime on the trait can only extend the borrow to be even longer. Normally &mut self is borrowed only in a scope where the function call was executed, but with a lifetime on the trait that extends it to the whole scope of the entire object's lifetime. For &'b mut self that is a maximally inflexible borrow-checker disaster that freezes the whole object to one-time-use only.

If something in self really lives shorter than self, then you need Weak (of Rc/Arc).

If &mut lifetimes are too restrictive, try using &self and interior mutability.

If you need to implement Producer on an object with a lifetime shorter than T, then create a new temporary object. Like collections implement iterators (e.g. Vec.iter() returns slice::Iter) where lifetime of the iterator is shorter than the lifetime of the collection.

[dovahcrow]

@dovahcrow

pub trait Produce<T> {
    fn produce<'b>(&'b mut self) -> Result<T>
    where
       // how to declare for all the lifetime in T, they are shorter than 'b?
}

Thanks! Yes, this is one of the ways I'm thinking of. However, this brings in other problems.

For example in the following case, the produce won't be able to be called twice in a function, due to the lifetime bound on the trait definition.

pub trait Produce<'b, T> {
    fn produce(&'b mut self) -> T;
}

fn consume<T>(_: T) {}

fn proceed<'a, P>(producer: &'a mut P)
where
    P: Produce<'a, &'a str>,
{
    let val = producer.produce();
    consume(val);

    // The second call won't work
    let val = producer.produce();
    consume(val);
}

It is true that one can use HRTB to fix this, i.e.

fn proceed<P>(producer: &'a mut P)
where
    for<'a> P: Produce<'a, &'a str>,
{
    let val = producer.produce();
    consume(val);

    // The will succeed
    let val = producer.produce();
    consume(val);
}

However, my original code is a little more complicated than that, and HRTB is not solving the whole problem. I'll try to simplify the original problem in a little bit.

[dovahcrow]

Yep, I agree. I think maybe moving the lifetime to the trait definition would be the only choice like @arnaudgolfouse mentioned. However, that causes another problem. I'll post it here later.

[dovahcrow]

Yes, you are right. It is likely that I'm posting an XY problem. I'll put my original problem below.

[dovahcrow]

Thanks for the reply. I think writing T: 'b with &'b self while T is borrowing something from self is the dangling situation. However, I was thinking about how to have a constraint 'b: T (all the references in T is shorter than 'b), which is totally valid since the references in T will not outlive self, a.k.a. T will be destructed before self.

[quinedot]

You can be explicit that both borrowed and owned data may be returned.

[EdmundsEcho]

Is there not a way to exploit the variance/~ subtyping capacity where ’a is effectively a subtype of ’b because 'a lives longer than ’b (where ’b is the lifetime of T). So, a where clause that specifies ’a:’b?

[trentj]

Apart from what this would mean and how it could play in to... everything, I also doubt whether it actually solves the problem you're having.

@dovahcrow

I'd like to make T not only work for owned types but also borrowed types. This means all the lifetimes in T must be shorter than the self-borrow lifetime 'b .

This doesn't seem to follow. As written,

pub trait Produce<T> {
    fn produce<'b>(&'b mut self) -> Result<T>;
}

with no where clause at all, it's perfectly fine for T to be a borrowed type, with or without a contained lifetime shorter than 'b. The version with the hoisted lifetime,

pub trait Produce<'b, T> {
    fn produce(&'b mut self) -> Result<T>
}

also permits implementors to make T a borrowed type with any lifetime, including ones shorter than 'b. Similarly, putting either of these in a regular (non-higher-ranked) bound also doesn't put any particular limitation on T to be owned or outlive 'b. So I don't see why you would need a new bound to make T work for borrowed types; as far as I know, it already does.

[kornel]

While this does in theory, you won't be able to do this in practice. Where are you going to take the instance of T from? You can't return anything shorter-lived from self, because then struct's definition would force it to live at least as long as self.

[trentj]

Well, you can narrow the lifetime of any longer-lived reference to make it shorter than 'b, but it's rather contrived. That's more or less my point: the language does permit you to implement Produce<&'short _> and call it with obj.produce::<'long>(), even though it's not particularly useful, so whatever problem @dovahcrow has, it can't be that T doesn't work for borrowed types.

I think it would help if we had an example of how one would implement Produce, so we can see what the actual lifetime error is.

[Barugon]

@kornel

You can't return anything shorter-lived from self

A reference that you return can be used as long as 'b is still alive. You can drop a returned reference at any point before that.

[edit] If you want to return a reference to something that may not live as long as 'b then wrap it in a Rc or Arc.

[dovahcrow]

@arnaudgolfouse @trentj @kornel Thanks for the insightful answers! I managed to reduce the use case into the following code Rust Playground

pub trait Produce<'a, T> {
    fn produce(&'a mut self) -> T;
}

// Get a function pointer of different type T based on flag
fn get_fptr(flag: bool) -> fn(p: &mut Foo) {
    fn inner<T>(p: &mut Foo)
    where
        for<'a> Foo: Produce<'a, T>,
        T: std::fmt::Debug
    {
        println!("{:?}", Produce::<T>::produce(p));
    }
    
    if flag {
        inner::<&str>
    } else {
        inner::<i32>
    }
}

pub struct Foo(String);

impl<'a> Produce<'a, i32> for Foo {
    fn produce(&'a mut self) -> i32 {
        1
    }
}

impl<'a> Produce<'a, &'a str> for Foo {
    fn produce(&'a mut self) -> &'a str {
        &self.0
    }
}


fn main() {
    let mut foo = Foo("bar".into());
    
    let fptrs = vec![get_fptr(true), get_fptr(false)];
    
    for _ in 0..10 {
        for &f in &fptrs {
            f(&mut foo)
        }
    }
}

Basically, I'd like to precompute a vector of function pointers and call them repeatedly. The function pointers will ask the producer to produce different types based on a flag. While for owned types, e.g. i32, this works totally fine, for borrowed types like &str, the compiler complains:

error: implementation of `Produce` is not general enough
  --> src/main.rs:16:9
   |
1  | / pub trait Produce<'a, T> {
2  | |     fn produce(&'a mut self) -> T;
3  | | }
  | |_- trait `Produce` defined here
...
16 |           inner::<&str>
   |           ^^^^^^^^^^^^^ implementation of `Produce` is not general enough
   |
   = note: `Foo` must implement `Produce<'0, &str>`, for any lifetime `'0`...
   = note: ...but `Foo` actually implements `Produce<'1, &'1 str>`, for some specific lifetime `'1`

error: aborting due to previous error

[quinedot]

Let's play "follow the errors" and see what we get. Apologies in advance if I'm just retreading ground that doesn't fit your use case.

For this function:

@dovahcrow

    fn inner<T>(p: &mut Foo)
    where
        for<'a> Foo: Produce<'a, T>,
        T: std::fmt::Debug
    {
        println!("{:?}", Produce::<T>::produce(p));
    }

Foo<String>'s implementation is not the more general version because of the lifetime relations in produce(&'a mut self) -> &'a str. So you need to relate the caller-chosen lifetime on p to the implementation. That would make inner not-more-general than the implementation of Produce. The change is:

fn inner<'a, T>(p: &'a mut Foo) where Foo: Produce<'a, T>, T: std::fmt::Debug

(Note that given the new signature, it might make sense to just make inner part of the Produce trait at this point.)

But then you get a similar error at a different level. We need to relate this lifetime to that in the get_fptr parameters as well. Unfortunately, nested item generics cannot refer to the outer generic, so we're going to have to move inner to be outside of get_fptr.

This brings us to a new error, but now it's about lifetimes in your loop and not in get_fptr. The issue is that the lifetime chosen for the invocations of get_fptr are too long. You want them to only last until the end of each loop iteration, but they are lasting until... probably the lifetime of the Vec? You really need a new lifetime to be chosen each time, at the call site.

We can do that with your example. Now it runs. But I'm not sure if it's useful to you; you would need to carry around the flags and create the function pointer each time.

That would just be an odd form of dynamic dispatch. If you're willing to accept that, you can get back the ability to choose which inner ahead of time. And hope the optimizer boils all of that indirection away. I admit it's not great.

inner relying on produce is really tying your lifetimes down. Do you really need it? Here's a version where that dependency has been removed, so inner can be more general, and the function pointers can be determined early.

[Yandros]

Regarding the code snippets in:

@quinedot

But then you get a similar error at a different level. We need to relate this lifetime to that in the get_fptr parameters as well. Unfortunately, nested item generics cannot refer to the outer generic, so we're going to have to move inner to be outside of get_fptr .

This brings us to a new error, but now it's about lifetimes in your loop and not in get_fptr . The issue is that the lifetime chosen for the invocations of get_fptr are too long. You want them to only last until the end of each loop iteration, but they are lasting until... probably the lifetime of the Vec ? You really need a new lifetime to be chosen each time, at the call site.

When trying to solve the error with the snippet in the first link (playground),

• For context, the change was:

  fn get_fptr(flag: bool) -> fn(&mut Foo) {
  -   fn inner<    T>(p: &'_ mut Foo)
  +   fn inner<'a, T>(p: &'a mut Foo)
      where
  -       Foo: for<'a> Produce<'a, T>,
  +       Foo:         Produce<'a, T>,
          T: std::fmt::Debug
      {
          println!("{:?}", Produce::<T>::produce(p));
      }
      
      if flag {
          inner::<&str> // error, got a `fn(&'inferred mut Foo)`
      } else {
          inner::<i32> // error, got a `fn(&'inferred mut Foo)`
      } // expected a `for<'any> fn(&'any mut Foo)`
  }
  

the issue is that we want a higher-order function pointer type fn(&mut Foo) = for<'any> fn(&'any mut Foo) (also called late-bound lifetime parameters), but by having used a clause bound that mentions the lifetime parameter 'a, the function pointers yielded when writing inner::<…> doesn't get higher-order / late-bound promoted; instead, the lifetime parameter is "early-bound" / fixed (and inferred), hence the error.

There is thus an interesting alternative to solve this:

• if you have a generic constructor that yields early-bound lifetime every time it is instanced, you can make it late-bound / higher-order again by wrapping it in a dummy closure:

      if flag {
  -       inner::<&str> // error, got a `fn(&'inferred mut Foo)`
  +       |foo: &mut _| inner::<&str>(foo) // Ok, explicit lifetime parameter in closure's input can be higher-order promoted
      } else {
  

• Playground

[dovahcrow]

Thanks, @quinedot ! These step-by-step examples are really helpful!

I also have explored the first two solutions and got the same errors, and I stopped there.

The third solution is something I tried to avoid because I don't want to let the CPU test the flag every time. In the real codebase, there are two flags, one for the consumer and one for the producer. For simplicity, I only put the producer in the example. As a result, I'm worrying that having tests on two flags here in every loop will confuse the branch predictor. (I'm doing something high-performance zero-copy stuff, so I think this is not a premature optimization).

The fourth solution introduces two indirection function calls (the indirection to the vtable, and then an indirect call on the function pointer). I feel this might be the same as doing tests on two flags every loop. But this solution is interesting, I'll definitely try and evaluate the performance.

As mentioned before, there are actually two parts, producer and consumer. So I think this solution might not fit the use case.

[dovahcrow]

Interesting solution! Thanks for the insight, I'll give it a try.

Never know I can make a lifetime late bound again by using closure.