Avoiding heap allocations in (some) async trait methods

Now that's a lot for me to digest. The term "covariance" is new to me, and I just had to look it up in the Rustonomicon. I'll need some time to process all that. I really have to read (and understand) more about variance first.

With those changes it works here!

That also works for me, and is much shorter. I also assumed if I do not mention any lifetime it would be 'static, but it isn't. So that is good to know.

But when I combine it with my trait example, it does not work:

#![feature(type_alias_impl_trait)]
#![feature(generic_associated_types)]
use std::future::Future;

trait GetAnInteger {
    type GetFuture<'a, 'b>: Future<Output = i32>; // NOTE: Could add `+ Sync` here
    fn get<'a, 'b>(&'a self, offset: &'b i32) -> Self::GetFuture<'a, 'b>;
}

struct ManualGetAnInteger {
    value: i32,
}

impl GetAnInteger for ManualGetAnInteger {
    type GetFuture<'a, 'b> = std::future::Ready<i32>;
    fn get<'a, 'b>(&'a self, offset: &'b i32) -> Self::GetFuture<'a, 'b> {
        std::future::ready(self.value + *offset)
    }
}

struct AutomaticGetAnInteger {
    value: i32,
}

async fn some_async_stuff() {
    println!("Let's pretend we do some async stuff here.");
}

impl GetAnInteger for AutomaticGetAnInteger {
    type GetFuture<'a, 'b> = impl Future<Output = i32> + Send;
    fn get<'a, 'b>(&'a self, offset: &'b i32) -> Self::GetFuture<'a, 'b> {
        async {
            // code might be added here in future
            some_async_stuff().await;
            // code might be added here in future
            self.value + *offset
        }
    }
}

#[tokio::main]
async fn main() {
    let getter1 = ManualGetAnInteger { value: 17 };
    println!("Got value: {}", getter1.get(&100).await);
    let getter2 = AutomaticGetAnInteger { value: 18 };
    println!("Got value: {}", getter2.get(&200).await);
}

I get the following error:

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
  --> src/main.rs:30:30
   |
30 |     type GetFuture<'a, 'b> = impl Future<Output = i32> + Send;
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: hidden type `impl Future` captures lifetime smaller than the function body
  --> src/main.rs:30:30
   |
30 |     type GetFuture<'a, 'b> = impl Future<Output = i32> + Send;
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

By the way, my rustc version is rustc 1.57.0-nightly (485ced56b 2021-10-07).

Do you get that with async move too?

2 Likes

Note that my explanation is off. I’m explaining why

use std::future::Future;

fn foo<'args, 'a, 'b> (it: &'a mut &'b ())
  -> impl 'args + Future<Output = ()>
where
    'a : 'args,
    'b : 'args,
{
    async move {
        drop(it);
    }
}

doesn’t work, not why

#![feature(type_alias_impl_trait)]

use std::future::Future;

type FooRet<'args, 'a, 'b> = impl 'args + Future<Output = ()>;
fn foo<'args, 'a, 'b> (it: &'a mut &'b ())
  -> FooRet<'args, 'a, 'b>
where
    'a : 'args,
    'b : 'args,
{
    async move {
        drop(it);
    }
}

Doesn’t work. I’ve only noticed my confusion later. For why the latter doesn’t work, the answer from @Yandros is currect, just the 'a: 'args and 'b: 'args bounds are missing.

The former (where my explanation applies) also gives a different error message:

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
 --> src/lib.rs:4:6
  |
4 |   -> impl 'args + Future<Output = ()>
  |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: hidden type `impl Future` captures the lifetime `'b` as defined on the function body at 3:19
 --> src/lib.rs:3:19
  |
3 | fn foo<'args, 'a, 'b> (it: &'a mut &'b ())
  |                   ^^

@Yandros With async move it works! Thanks to both of you for all that info. Will look more into that later.

I did take a look at covariance and invariance in Rust, and I think I now have an idea what's happening. I tried again to understand things here:

As &'a mut &'b T is invariant over 'b (if I understand it right), we must ensure that the returned future (which captures it)

  • lives at most as long as 'a
  • and lives exactly as long as 'b'.

Thus, the returned future has lifetime 'b, and 'a must live at least as long as 'b does. This leads to the following code:

#![feature(type_alias_impl_trait)]
use std::future::Future;

type FooRet<'c> = impl 'c + Future<Output = ()>;
fn foo<'a, 'b>(it: &'a mut &'b ()) -> FooRet<'b>
where
    'a: 'b,
{
    async move {
        drop(it);
    }
}

#[tokio::main]
async fn main() {
    let v: () = ();
    let mut r: &() = &v;
    foo(&mut r).await;
}

This code compiles with my rustc (and also executes without a panic). Note that it does not seem necessary to provide more than one lifetime argument to FooRet (which I named 'c here) if I correctly provide the relationship between 'a and 'b as bounds to foo.

An alternative seems to provide two lifetime parameters to FooRet and elide the lifetime in impl, as @Yandros pointed out:

In which case the above example would be written as:

type FooRet<'a, 'b> = impl Future<Output = ()>;
fn foo<'a, 'b>(it: &'a mut &'b ()) -> FooRet<'a, 'b> {
    async move {
        drop(it);
    }
}

I hope I did get things right so far. Now to something @steffahn said:

Is there any authoritative reference regarding the behavior of impl without explicit lifetimes? The chapter Lifetime elision in the Rust reference doesn't seem to say anything about it. When you say the rules are "weird and inconsistent/buggy", does that mean I should expect them to change in future? That would be an argument against using type FooRet<'a, 'b> = impl Future<…>.

Well, @Yandros took part in that discussion; I didn't. And I'm afraid I'm super confused now :sweat_smile:. Any way to explain it in more simpler words? (I'll try to read that thread though, and try to follow up here.)

I really would like to understand the exact behavior with impl regarding lifetimes, and using impl in associated types, as I think this should allow us to have efficient async trait methods (with a clunky syntax yet).

Let me put it all together and let's modify (and simplify) my original example with all that gathered knowledge:

#![feature(generic_associated_types)]
#![feature(type_alias_impl_trait)]
use std::future::Future;

trait NumberChanger {
    type ChangeRet<'a, 'b>: Future<Output = ()>;
    fn change<'a, 'b>(&'a self, number: &'b mut i32) -> Self::ChangeRet<'a, 'b>;
}

struct AddOffset {
    offset: i32,
}

async fn some_async_stuff() {
    println!("Let's pretend we do some async stuff here.");
}

impl NumberChanger for AddOffset {
    type ChangeRet<'a, 'b> = impl Future<Output = ()>;
    fn change<'a, 'b>(&'a self, number: &'b mut i32) -> Self::ChangeRet<'a, 'b> {
        async move {
            some_async_stuff().await;
            *number += self.offset;
        }
    }
}

#[tokio::main]
async fn main() {
    let mut i: i32 = 17;
    let changer = AddOffset { offset: 2 };
    let future = changer.change(&mut i);
    future.await;
    assert_eq!(i, 19);
}

This code compiles and executes without any error using my rustc. Thus, we can avoid unnecessary heap allocations in async trait methods, can't we?

It only seems to be a matter of using some (yet?) unstable features and dealing with a clunky syntax. The syntax issue could be solved by a crate providing a macro, such as real-async-trait, I guess, though real-async-trait has too many limitations as of now. In real-life code, I'd rather deal with the syntax above, instead of not being able to use more complex lifetimes.

What do you think?

That's the rules for what happens if you wrote impl 'a + … with a lifetime. Also I'm mostly talking about the rules around impl Trait return types without type_alias_impl_trait. I'm not sure how much of the weirdness also applies to the type aliases. Note that anything that's only possible with a #(feature(…)) flag can change in the future. Since the weird rules I'm talking about are observable on stable and don't seem to be unsound, I don't expect them to change in a breaking manner.

This code effectively restricts 'a and 'b to be the same lifetime and it's most definitely not what you want. (A type &'a mut T where T itself uses/mentions/contains the lifetime argument 'a as well is quite useless/annoying to use in Rust.)

You've got the relationship mixed up, it's the other way. 'b: 'a. This kind of bound comes implicitly with using the type &'a mut &'b (). Together with your bound the two lifetimes are thus restricted to be the same.

Well, for type alias impl trait, you won't find rules explaining that in the reference (the reference is about stable features).

Ultimately, I think with type Foo<'a, …> = impl Trait; you really never need to add a + 'a to the right hand side. I don't think it helps in any way (i. e. all code that compiles with the extra + 'lifetime will also compile without it, AFAICT). As discussed in that other thread (the one you mentioned here

), the usage of + 'lifetime in impl Trait return types (without using type_alias_impl_trait) is really only done for its effect on what the lifetime arguments of the implicitly generated opaque type are going to be according to the rules in the RFC I've linked

1951-expand-impl-trait - The Rust RFC Book

in particular, it's usually not used for its effect in terms of what a T: 'a + Trait bound actually means, and the weirdness/buggy-ness I was referring to is the fact that this effect is not really usable for a caller of the fn f() -> impl 'a + Trait function anyway. So it's like putting up extra hurdles for the implementors of the function without any benefits for the caller. fn f() -> impl 'a + Trait should - for the caller - be just as useful as fn f() -> impl CapturesLifetime<'a> + Trait. Since with type Foo<'a> = impl Trait; you explicitly specify the lifetimes involved anyway, you'll need neither of the 'a + or CapturesLifetime<'a> +.

1 Like

E.g. it will have the effect that you cannot do the call to foo twice in your example

#![feature(type_alias_impl_trait)]
use std::future::Future;

type FooRet<'c> = impl 'c + Future<Output = ()>;
fn foo<'a, 'b>(it: &'a mut &'b ()) -> FooRet<'b>
where
    'a: 'b,
{
    async move {
        drop(it);
    }
}

#[tokio::main]
async fn main() {
    let v: () = ();
    let mut r: &() = &v;
    foo(&mut r).await;
    foo(&mut r).await; // error
}

The quick explanation:

  • First: what does T: 'a mean?
    • it mean that the type T cannot use/mention/contain any lifetimes that are shorter than 'a.
    • on way to phrase it: T must be such that every reference that a value of type T contains has a lifetime longer than 'a.
    • another more syntactic interpretation: If you write the concrete type that the parameter T gets instantiated with, that type must not, syntactically, mention any lifetime shorter than 'a.
      • e.g. for T == &'b (), the bound T: 'a is only true if 'b is no shorter than 'a, i.e. 'b outlives 'a, i.e. 'b: 'a.
    • The bound T: 'a is a necessary condition for the type &'a T or &'a mut T to be well-formed.
      • Think of them as struct Ref<'a, T> where T: 'a { ... } (note the where bound!), just that Ref<'a, T> has special syntax &'a T.
      • This is also why &'a mut &'b () discussed earlier comes with a bound: The bound &'b (): 'a, which in turn requires 'b: 'a. Here T is &'b ().
  • The impl Trait + 'a really only means that the return type T must fulfill T: Trait + 'a, which means it fulfills both T: Trait and T: 'a. The side-effect that this signature also mentions the lifetime 'a is important, too. As mentioned, it’s the most important thing about this + 'a in usual usage without type_alias_impl_trait.
  • Struct/enums you define follow the syntactic rule for T: 'a bounds as-well:
    • A struct Foo<'a, 'b> = { /* some fields */ } always behaves such that Foo<'a, 'b>: 'c is fulfilled if and only if 'a: 'c and 'b: 'c are fulfilled.
  • A type defined by type_alias_impl_trait, i.e. type Foo<'a, 'b> = impl Trait; behaves exactly like structs / enums in this case.
    • This means that even a type Foo<'a, 'b> = impl 'a + Trait; would only fulfill Foo<'a, 'b>: 'a if 'b: 'a. This is weird because one would expect that Foo<'a, 'b> implements 'a + Trait, but it really – effectively – doesn’t. (Example code.) That’s the weirdness I was referring to, and it’s what makes writing the 'a + … fairly useless in type_alias_impl_trait aliases.

If you haven’t already, you might also be interested in reading this blog post
rust-blog/common-rust-lifetime-misconceptions.md at master · pretzelhammer/rust-blog · GitHub

2 Likes

Ah, okay :sweat_smile:.

Yeah, I shouldn't forget that, but if some behavior is obviously weird/inconsistent/buggy, it would (hopefully) be more prone to change.

I guess that's because 'b: 'a is implied by it: &'a mut &'b (). My reasoning that the invariance over 'b requires that the future lives at least as long as 'b' was wrong, I think. Still very difficult for me to gather an overview on all this :woozy_face:.

Now I wonder what exactly happens when I write:

type FooRet<'a, 'b> = impl Future<Output = ()>;

I assume each 'a and 'b must live at least as long as FooRet<'a, 'b> does, thus a: FooRet<'a, 'b>, right? And the lifetime requirements for FooRet<'a, 'b> (and the concrete type being used) are determined by the compiler?

But it's also possible to use impl without type aliases (e.g. as a return type), and I guess you can omit the lifetime there too? Then it also isn't 'static? Or is it the same as the lifetime of a reference to self? Or automagically calcuated somehow? :face_with_raised_eyebrow: That should be part of stable rust already, but I don't find any info on that either.

I'll omit that extra + 'a then (i.e. when I use impl with type).

Thanks for bringing up that example!

I guess that's what I meant earlier with 'b: 'a is implied by it: &'a mut &'b (), but you expressed more precisely :sweat_smile:.

I still feel like understanding only half of what you wrote.

I'll definitely take a look at that. I thought I (mostly) understood lifetimes in Rust, but I think I was wrong. There's definitely a lot for me to catch up on. (And sorry if in this post I messed up things again.)

Feel free to bring up any more misconceptions I have (I do want to learn and get better at understanding Rust!), but let me get back to the original topic of this thread:

Avoiding heap allocations in (some) async trait methods

Let's assume I use this syntax (as done in my last example):

#![feature(generic_associated_types)]
#![feature(type_alias_impl_trait)]
use std::future::Future;
trait SomeTrait {
    type SomeMethodRet<'a, 'b, 'c, 'd, …>: Future<Output = SomeRetType>; // optionally: + Send
    fn some_method<'a, 'b, 'c, 'd, …>(&'a self, some_arg: &'b SomeArgType, …) -> Self::SomeMethodRet<'a, 'b, 'c, 'd, …>;
}
impl SomeTrait for SomeType {
    type SomeMethodRet<'a, 'b, 'c, 'd, …> = impl Future<Output = SomeRetType>;
    fn some_method<'a, 'b, 'c, 'd, …>(&'a self, some_arg: &'b SomeArgType, …) -> Self::SomeMethodRet<'a, 'b, 'c, 'd, …> {
        async move {
            /* method body goes here */
        }
    }
}

Does this solve the problem of missing (efficient) asynchronous trait methods in Rust (apart from the clunky syntax)?

Basically

struct Bar;
trait Trait {}
fn foo<'a>(x: &'a Bar) -> impl Trait {…}

is the same as

struct Foo;
trait Trait {}
type FooReturnType = impl Trait;
fn foo<'a>(x: &'a Bar) -> FooReturnType {…}

while

struct Bar;
trait Trait {}
fn foo<'a>(x: &'a Bar) -> impl Trait + 'a {…}

is the same as

struct Bar;
trait Trait {}
type FooReturnType<'a> = impl Trait + 'a;
fn foo<'a>(x: &'a Bar) -> FooReturnType<'a> {…}

and

trait CapturesLifetime<'a> {}
impl<T: ?Sized> CapturesLifetime<'_> for T {}
struct Bar;
trait Trait {}
fn foo<'a>(x: &'a Bar) -> impl Trait + CapturesLifetime<'a> {…}

is the same as

trait CapturesLifetime<'a> {}
impl<T: ?Sized> CapturesLifetime<'_> for T {}
struct Bar;
trait Trait {}
type FooReturnType<'a> = impl Trait + CapturesLifetime<'a>;
fn foo<'a>(x: &'a Bar) -> FooReturnType<'a> {…}

See how the first case doesn’t put <'a> on the type FooReturnType definition. This in turn has the effect that the actual type returned by fn foo cannot contain anything with a lifetime 'a either. The CapturesLifetime<'a> is a hack/workaround to make the compiler add the argument 'a to FooReturnType without the + 'a bound. The bound T: CapturesLifetime<'a> is basically no bound at all because due to the generic implementation, any type T fulfills this bound. Thus

trait CapturesLifetime<'a> {}
impl<T: ?Sized> CapturesLifetime<'_> for T {}
struct Bar;
trait Trait {}
fn foo<'a>(x: &'a Bar) -> impl Trait + CapturesLifetime<'a> {…}

is basically equivalent to

struct Bar;
trait Trait {}
type FooReturnType<'a> = impl Trait;
fn foo<'a>(x: &'a Bar) -> FooReturnType<'a> {…}

The return type of fn foo<'a>(x: &'a Bar) -> impl Trait {…} is indeed 'static, because it’s the type FooReturnType, which doesn’t have any lifetime parameters. A type T without lifetime parameters always fulfills T: 'static.

The return type of fn foo<'a>(x: &'a Bar) -> impl Trait + CapturesLifetime<'a> is not 'static unless 'a is 'static. Its return type is FooReturnType<'a>, and that type mentions the lifetime 'a. Hence the bound FooReturnType<'a>: 'b is only fulfilled if 'a: 'b. In effect, you only get FooReturnType<'a>: 'static if 'a: 'static. The bound 'static: 'a is trivially true for any lifetime; hence FooReturnType<'a>: 'static is only fulfilled if 'a == 'static, i.e. the lifetime 'a is the lifetime 'static.


Yes, this should work. At least ignoring potential bugs around type_alias_impl_trait with associated types. Lasts time I played around with it I remember sometime needing to define top-level type Foo<'a> = impl … definitions and using those in the trait impl … for … { type Bar<'a> = Foo<'a>; … }. Otherwise, I got weird compiler errors sometimes. I don’t remember the details of when exactly I ran into problem and when I didn’t – feel free to try it yourself :slight_smile:

1 Like

So the problem with writing impl directly as a return type is that there is no syntax to capture any lifetime. If I add it explicitly with impl 'lt + …, then the return type would have to have the exact same lifetime as 'lt (which I don't want in most cases), right?

So I guess some syntax extension should be added, like impl<'lt> Trait.

I'll then try to incorporate that into my code (replacing the #[async_trait] workaround) and hope for the best :fearful:.

Okay, I'll keep that in mind as a potential workaround if I run into trouble; thanks for the warning/advice.

I'm definitely excited now. Also thanks to @Yandros for bringing up min_type_alias_impl_trait… Well, wait… is there a difference between type_alias_impl_trait (that I used in my last example) and min_type_alias_impl_trait?

I'm surprised that async trait methods seem to be possible with unstable rust and won't require any strange workarounds (other than a slightly verbose syntax). At the same time, I can impose additional bounds on the returned futures, such as Send.

Note that some of the problems mentioned here

why async fn in traits are hard

are still unaddressed by this approach. (Send bounds, support for trait objects.)

I just tried to get rid of some of my #[async_trait] annotations using the last described method, and I feel like giving up already :tired_face:. It generally seems to work, but I even have to include all generic types as arguments to the associated type, e.g.:

pub trait Dumpable: Sized {
    type DumpRet<'a, 'b, W>: Future<Output = io::Result<()>>;
    fn dump<'a, 'b, W>(&'a self, writer: &'b mut W) -> Self::DumpRet<'a, 'b, W>
    where
        W: AsyncWrite + Unpin + Send;

I did encounter one example where I needed to declare a top-level `type Foo<…> = impl …, which happened when I wanted to provide a default implementation for a trait method.

No other error(s) here (yet), but I didn't test it very extensively.

I don't see why Send bounds are an issue. At least I can simply add + Send to the bounds of the associated type in the trait and in each implementation. Maybe it gets messy when the Future shall be Send if some of the arguments are Send. Maybe the issue with trait objects is the biggest problem. Not sure if I really understand all of the problems mentioned in that post though (despite having read it a couple of times). I still feel like a beginner, even if all this is pretty complex stuff.

Bottom line is: The syntax alone is already discouraging me enough to stop me from manually using associated types to avoid the heap allocations. I'll switch back to use #[async_trait] and deal with the runtime penalty (it won't really matter for the project I'm working on). I feel like using associated types would make my code much less readable, and [#real_async_trait] seems to be unusable in practice yet (which has been warned about in its documentation).

Nonetheless, this journey has taught me a lot about lifetimes, associated types, and the impl keyword.

Perhaps I might use the associated type approach in rare cases to get rid of heap allocations in some async trait methods, i.e. where the syntax overkill is worth the efficiency gain.

1 Like

Let's "summarize" every lifetime-related notion mentioned or used in this thread, shall we.

Putting it all together

1- About T : 'a and impl 'a + …

In that example, the input it: &'a mut &'b () is captured by the future (async move { drop(it); }), so the compiler, under the hood, has generated something like:

struct AsyncMoveFuture<'a, 'b> {
    it: &'a mut &'b (),
    // …
}

impl<'a, 'b> Future for AsyncMoveFuture<'a, 'b> {

Now, the type AsyncMoveFuture features two lifetime( parameter)s, 'a and 'b, and since 'a represents the region of a borrow of a 'b-infected type, we have that the region 'a must be a subset of / contained within the region 'b:

  • 'b ⊇ 'a ; which in Rust syntax is written as:

  • 'b : 'a

  • (And, indeed, when you added the 'a ⊇ 'b bound, you ended up with 'a = 'b and thus not really having two free lifetimes parameters but one).

With that being said, what can we say about AsyncMoveFuture<'a, 'b>?

  • that object, itself, can only be used within a region that must be contained within the region of each borrow / lifetime appearing inside it.

    That is, if we wanted to use that object within a region 'c, then we must have that 'a ⊇ 'c and 'b ⊇ 'c (in this instance, since 'b ⊇ 'a, the former superset property suffices).

    • (In the case of unrelated lifetimes, we'd have to carry that extra "intersection" lifetime parameters, which was named 'args in our previous unsugarings in this thread)

    So this means that we can use any instance of type AsyncMoveFuture<'a, 'b> safely within the region 'c, written as AsyncMoveFuture<'a, 'b> : 'c, if and only if ('a ⊇ 'c) & ('b ⊇ 'c) holds. Let's call it 'inter for intersection:

    for<'inter, 'a : 'inter, 'b : 'inter> 
        AsyncMoveFuture<'a, 'b> : 'inter
    ,
    
    • In our 'b : 'a case, this is equivalent to:

      for<'a, 'b /* : 'a */>
          AsyncMoveFuture<'a, 'b> : 'a
      ,
      
  • But the type is definitely infected with the lifetimes 'a and 'b: if you tried to define

    type MyAlias<'a> = AsyncMoveFuture<'a, '???>;
    

    you wouldn't have that potentially-distinct-from-'a parameter 'b in scope, and thus would be unable to fully describe the actual type.

    • Often, this limitation is side-stepped thanks to variance. If the type AsyncMoveFuture<'a, 'b> were covariant in 'b / its second lifetime parameter (i.e., if its second lifetime parameter were "shrinkable" / if we could substitute 'b with any 'smaller_than_b lifetime), then we would be able to shrink it down to 'a, and have:
    // By covariance in the second parameter, and since `'b : 'a`,
    AsyncMoveFuture<'a, 'b> => AsyncMoveFuture<'a, 'a>
    

    and then type MyAlias<'a> = AsyncMoveFuture<'a, 'a> would be able to describe our type.

Notice how, until this point, I haven't really mentioned the existential type aliases.


2- Enter type aliases!

  1. Explicit existential type aliases: type Name<…> = impl …

    When we introduce them manually, we can then write:

    type RetFuture<'a, 'b> = impl ['lt +]? Future<Output = ()>;
    
    • (we'll see about the + 'lt afterwards).

    If we then try to unify that existential with "our" AsyncMoveFuture<'a, 'b>, then the compiler can check that:

    • AsyncMoveFuture<'a, 'b> : Future :white_check_mark:

      • (if we had + 'lt in the definition, then it would also have to check that AsyncMoveFuture<'a, 'b> : 'lt, i.e., that 'a : 'lt and 'b : 'lt)
    • with the parameters 'a and 'b in scope of the type alias, we can fully name the AsyncMoveFuture<'a, 'b> type :white_check_mark:

      • (Again, this would not be possible if, for instance, we only had <'a> in the alias, and the type weren't covariant in 'b).

    And so everything checks out.

    Regarding the + 'lt: in the case of an explicit existential type alias, it can be skipped (as discovered in this thread). The compiler will just not perform any "outlives 'lt"-check whatsoever at definition site, and "downstream" users of the existential RetFuture<'a, 'b> type will not have any "extra" lifetime property, besides the default / most conservative property:

    • If a type is infected by both a 'a and a 'b parameters, then, since it may be invalidated if we are outside 'a or if we are outside 'b, it must only be used within their intersection.

      That is, for an explicit existential type alias, the following two definitions are equivalent:

      type Ty<'a, 'b> = impl Trait;
      

      and

      type Ty<'inter, 'a: 'inter, 'b: 'inter> = impl 'inter + Trait;
      

      Hence @steffahn's rule of thumb: don't put the + 'inter bound on an existential type alias (see 1 for more info).

    All this is what makes:

    type RetFuture<'a, 'b> = impl Future<'a, 'b>;
    
    fn test<'a, 'b> (
        a: Invariant<'a>,
        b: Invariant<'b>,
    ) -> RetFuture<'a, 'b>
    {
        /* return */ async move {
            drop((a, b));
        }
    }
    

    work.


  2. Implicit existential type aliases: -> impl …

    They are often called RPIT (Return Position impl Trait). In that case, the compiler will be using an existential type alias under the hood, which is why I'm calling them "implicit existential type aliases".

    That is,

    fn foo<'a, 'b, T, U> (args…)
      -> impl Bounds…
    …
    

    becomes, under the hood:

    fn foo<'a, 'b, T, U> (args…)
      -> __CompilerGeneratedReturnOf_foo<…>
    …
    
    // where
    type __CompilerGeneratedReturnOf_foo<…> = impl Bounds…;
    

    And when doing so, there is something subtle going on regarding the <…> generics of the existential type alias: the compiler will follow certain (not necessarily optimal) heuristics —you can find more details and the rationale in the associated RFC (thanks @steffahn!)— such as:

    • Any type parameter in scope of the function definition will automagically become a generic type parameter of the existential type alias

      - type __CompilerGeneratedReturnOf_foo<…      > = impl Bounds…;
      + type __CompilerGeneratedReturnOf_foo<…, T, U> = impl Bounds…;
      

      Thus leads to -> impl Trait being allowed to capture any type parameter in scope!

    • But, contrary to type parameters, the above rule —in a rather inconsistent fashion may I add— does not apply to generic lifetime parameters:

      The existential type alias will only be generic over the lifetime parameters that appear in the impl Bounds… "expression"

      So, for instance, if impl Bounds… were impl 'a + Trait1 (or impl Trait2<'a>), then we'd have:

      - type __CompilerGeneratedReturnOf_foo< …, T, U> = impl Bounds…;
      + type __CompilerGeneratedReturnOf_foo<'a, T, U> = impl Bounds…;
      

      Which means that when the actual returned type captures another lifetime, such as 'b, even when 'b ⊇ 'a (to avoid the obvious "outlives failure"), if it is captured in a non-covariant-over-'b fashion, we hit that infamous "hidden lifetime" error.

    And this is what leads to the following silly workaround: we would like to mention the lifetime 'b,

    • and using + 'b is out of the question, since when this is done for multiple lifetimes, the returned thing is only usable within the intersection, and not the union (which is what would be expressed by, for instance, + 'a + 'b),

    • so we only have + Trait<'b> left,

    but since the returned thing would then have to uphold + Trait<'b>, we'd like that Trait to be a dummy one, trivially implemented by everything:

    trait Dummy<'lt> {}
    impl<'any, Everything : ?Sized> Dummy<'any> for Everything {}
    

    That way we can use + Dummy<'b> to trick the existential heuristics into correctly adding 'b, to its list of generic parameters.

    Given that use site, and to avoid calling out this silly aspect of Rust for some reason, we can be more polite and rename Dummy to, for instance, Captures or Mentions.

    Hence the solution:

    type Invariant<'lt> = ::core::marker::PhantomData<
        fn(&()) -> &mut &'lt (),
    >;
    
    fn example<'a, 'b> (
        a: Invariant<'a>,
        b: Invariant<'b>,
    ) -> impl Future<Output = ()> + Dummy<'a> + Dummy<'b>
    {
        /* return */ async move {
            drop((a, b));
        }
    }
    
    trait Dummy<'__> {}
    impl<T : ?Sized> Dummy<'_> for T {}
    

    And the interesting thing is that no explicit + 'region_of_usability bound is needed here either, so, again, for 'intersection kind of bounds1, there is no need to add it, since it would be equivalent:

    fn example<'inter, 'a : 'inter, 'b : 'inter> (
        a: Invariant<'a>,
        b: Invariant<'b>,
    ) -> impl 'inter + Future<…> + Dummy<'a> + Dummy<'b>
    

1Quid of non-intersection lifetimes?

Because of some limitations of the compiler, it turns out that impl 'region_of_usability + …, despite being checked at construction time, is not an actionable property for "downstream" users, at least whenever 'region_of_usability ⊋ 'intersection.

That is, if we called 'inter the intersection of, say, 'a and 'b, then

type Existential<'a, 'b> = impl Trait;

has the semantics of:

type Existential<'a, 'b> = impl 'inter + Trait;

And since + 'lt1 + 'lt2 is something that ought to express that something is usable within both 'lt1 and 'lt2, i.e., that it is usable within the union of those two regions,
the expected behavior in Rust of something like:

type Existential<'a, 'b> = impl 'static + Trait;

is that Existential<'a, 'b> : 'static ought to hold (even if that would be impossible to uphold for any implementation of the type that happens to mention 'a and 'b). That is, despite being a seemingly silly situation, it's one that could theoretically come up, and and one which, in practice, with generic associated types, may come up in a non-silly fashion.

And it turns out that Rust conservatively condemns any lifetime-infected type not to outlive the intersection of the generic lifetimes it has available to its definition, which means that, given

type Existential<'lt> = impl 'static + …;

we only have that Existential<'lt> : 'lt and not that Existential<'lt> : 'static.

  • it does lead to quite silly situations such as the following:

    /// Given
    fn foo<'lt> (
      f: impl 'static + Fn(&'lt ())
    ) -> impl 'static + Fn(&'lt ())
    {
        f
    }
    

    the return type of foo does not meet the input bounds of foo:

    fn f(&()) {}
    
    let f = foo(f); // OK
    let f = foo(f); // Error!
    

    as I mentioned in that other post @steffahn linked to.

All this leads to, currently, impl 'inter + necessarily being the semantics of all the generic existential types, which means that, currently, there is no reason whatsoever to write impl 'region_of_usability for existential types :scream:.

I keep this addendum / note nonetheless, since I personally view that as a bug / language limitation which ought to be, ultimately, fixed, and in that case we may go back to having meaningul impl 'bigger_than_inter (e.g., impl 'static) existentials.

5 Likes

Great explanation. Thanks a lot for taking the time and collecting / writing down all the details in one coherent post. Two minor things:

The phrasing makes it seem like adding the + 'lt would give any advantage (compared to that “most conservative” default) to the downstream user. AFAIK, it doesn’t: It’s always 100% useless. If there is ever any benefit a downstream user can have from the added + 'lt, please give me an example!

The rules are explained in the RFC I’ve already linked in this thread:

1951-expand-impl-trait - The Rust RFC Book

1 Like

Thanks for pointing out both points :ok_hand:

  • I had made the mistake not to read that RFC until now :sweat_smile:; having an official confirmation (and more importantly, the rationale behind it!) is ideal.

  • I have edited my post at the end to add a whole section about situations where I would like / have expected impl 'outlives to matter, even though in Rust it currently doesn't :disappointed:. So, yes, you are totally right: currently, in Rust, there does not seem to be any reason whatsoever to write impl 'outlives + … for an existential type.

1 Like

@Yandros I'm slowly trying to understand your post. I didn't get much farther than the first few paragraphs, but I think I understood a bit. I think I messed up a couple of times the direction of which lifetime must outlive which other lifetime. (The fact that the sub-type relationship is vice-versa added even more confusion.)

I guess what I should have tried to write is:

type FooRet<'c> = impl Future<Output = ()>;
fn foo<'a, 'b, 'c>(it: &'a mut &'b ()) -> FooRet<'c>
where
    'a: 'c,
    'b: 'c,

But that's causing an error:

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
 --> src/main.rs:5:43
  |
5 | fn foo<'a, 'b, 'c>(it: &'a mut &'b ()) -> FooRet<'c>
  |                                           ^^^^^^^^^^
  |
note: hidden type `impl Future` captures the lifetime `'b` as defined on the function body at 5:12
 --> src/main.rs:5:12
  |
5 | fn foo<'a, 'b, 'c>(it: &'a mut &'b ()) -> FooRet<'c>
  |            ^^

Trying to work around that error, I messed up the direction of dependency.

I think. :sweat_smile:

So, the error E0700 is an infamous one that has to deal with the fact that you cannot express the type &'a mut &'b () with the lifetime 'c alone. But do not despair, your are on the right path!

  • Just so that you see you are on the right path, if you replace FooRet<'c> with BoxFuture<'c, ()> (and surrounding the async move in a Box::pin() call), you'll see that your code will compile: that means that you got the + 'region_of_usability lifetime bound right (indeed, for any region 'c contained within both 'a and 'b, and thus, their intersection, the returned object will necessarily be safe to use within it (the region 'c)).

  • It's just on the type alias part that you are getting the error: while your type is necessarily usable within 'c, it carries extra lifetime information (the 'b lifetime) which cannot be dismissed / discarded and which cannot be expressed with 'c alone.

    So you have to keep carrying that "vestigial" 'b parameter in the type alias, since it must be kept around:

    - type FooRet<'c    > = impl Future<Output = ()>;
    + type FooRet<'c, 'b> = impl Future<Output = ()>;
    

See also:

In some real code, I just encountered a case where I have to use dyn with multiple lifetimes (I'm currently experimenting on how to use streams). Actually I was forced to introduce a single lifetime as apparently dyn only allows one lifetime specified. This is what I had to do:

fn transactions_exist<'a: 'ret, 'b: 'ret, 'c: 'ret, 'ret>(
    &'a self,
    ids: impl 'b + Iterator<Item = &'c TransactionId> + Send,
) -> Box<dyn 'ret + Stream<Item = std::io::Result<bool>> + Send>
where
    Self: Sync,
{
    Box::new(
        futures::stream::iter(ids).then(move |id|
            self.transaction_exists(id)
        )
    )
}

So dealing with impl and with dyn seems to work very differently and my "naive" approach to come up with a single new lifetime (which caused E0700 when using impl) works with dyn (and even seems to be required?). That is a bit confusing. If I try dyn + 'a + 'b + 'c + …, then I get:

error[E0226]: only a single explicit lifetime bound is permitted
   --> src/xyz/mod.rs:212:23
    |
212 |     ) -> Box<dyn 'a + 'b + 'c + Stream<Item = IoResult<bool>> + Send>
    |                       ^^

So do I get it right that dyn and impl need to be used in completely different ways when it comes to lifetimes?

Update: Just before falling asleep, I figured I mixed up the direction of the relationship again: dyn 'a + 'b + … would make no sense anyway, as the dyn object doesn't need to live as long as the arguments to my function are living, but the other way around: the arguments must live at least as long as the returned boxed dyn object lives. :crazy_face:

Nonetheless, dyn and trait seem to work differently, because it's okay to come up with a new single lifetime for dyn, while this doesn't work with trait.

There is an inconsistency between dyn and impl, yes (which is something I personally hope gets solved in the language):

  • thanks to type erasure, dyn only cares about the 'region_of_usability,

  • whereas impl does need access to the larger invariant lifetimes nonetheless, since it's not really erasing the type, just hiding it.

Yep, that's the way to express the 'intersection lifetime, as I have been calling it, which indeed represents a region within which the returned item will always be valid to use :+1:

3 Likes

I wonder if in the concrete example, I can use a single lifetime for the two lifetimes 'b and 'c, because the iterator cannot live longer than its items anyway:

fn transactions_exist<'a: 'ret, 'b: 'ret, 'ret>(
    &'a self,
    ids: impl 'b + Iterator<Item = &'b TransactionId> + Send,
) -> Box<dyn 'ret + Stream<Item = std::io::Result<bool>> + Send>
where
    Self: Sync,
{ /* … */ }

The code compiles (so far). But does that restrict the argument type to those iterators that live exactly as long as the items (but not shorter, yet longer than 'ret)? That I wouldn't want. Thus I assume this simplification is a bad idea?

Note that impl in the last two examples is in argument position, so it will behave different once more :rofl:


I.e., writing it without impl, it should be equal to this:

fn transactions_exist<'a, 'b, 'ret, I>(&'a self, ids: I)
    -> Box<dyn 'ret + Stream<Item = std::io::Result<bool>> + Send>
where
    'a: 'ret,
    'b: 'ret,
    I: 'b + Iterator<Item = &'b TransactionId> + Send,
    Self: Sync,
{ /* … */ }

I assume, that would force the iterator type I to live as long as each Item (of the iterator), which is what I don't want, right? Or could the iterator items live longer than 'b here? I'm not sure exactly what the syntax means.


Update: I just figured out, I probably need two different lifetimes for the iterator itself and its items, as the following example shows:

// The following doesn't work:
// fn accept_iter<'a>(iter: impl 'a + Iterator<Item = &'a str>) {
//
// Instead we need:
fn accept_iter<'a, 'b>(iter: impl 'a + Iterator<Item = &'b str>) {
    for s in iter {
        println!("Got: {}", s);
    }
}
fn main() {
    let v = vec!["static1", "static2"];
    let dummy: i32 = 99;
    struct Iter<'dummy> {
        storage: Vec<&'static str>,
        index: usize,
        _dummy: &'dummy i32,
    }
    impl<'a> Iterator for Iter<'a> {
        type Item = &'static str;
        fn next(&mut self) -> Option<Self::Item> {
            if self.index < self.storage.len() {
                let result = self.storage[self.index];
                self.index += 1;
                Some(result)
            } else {
                None
            }
        }
    }
    let iter = Iter {
        storage: v,
        index: 0,
        _dummy: &dummy,
    };
    accept_iter(iter);
    drop(dummy);
}

If I use a single lifetime, then _dummy is expected to be 'static too.

This is very evil, as the following program neither creates a compile- nor a runtime-error:

fn accept_iter<'a>(iter: impl 'a + Iterator<Item = &'a str>) {
    for s in iter {
        println!("Got: {}", s);
    }
}
fn main() {
    let v = vec!["static1", "static2"];
    accept_iter(v.into_iter());
}

Thus, I might believe my implementation of accept_iter with only one lifetime 'a is sound, which it is not.

Is this common pitfall regarding lifetimes described somewhere? I think I stumbled upon it multiple times.