Avoiding heap allocations in (some) async trait methods

steffahn · October 9, 2021, 9:23am

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

jbe · October 9, 2021, 10:42am

Ah, okay .

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 .

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? 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 .

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)?

steffahn · October 9, 2021, 11:10am

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

jbe · October 9, 2021, 11:42am

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 .

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.

steffahn · October 9, 2021, 12:10pm

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.)

jbe · October 9, 2021, 12:59pm

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 . 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.

Yandros · October 11, 2021, 11:31am

jbe:

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 .

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?

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!

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
  - (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
  - (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.
  - Demo
  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 ¹ 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.
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 {}
```
- Playground
And the interesting thing is that no explicit + 'region_of_usability bound is needed here either, so, again, for 'intersection kind of bounds¹, 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>
```

¹Quid 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.

An example.

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 .

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.

steffahn · October 11, 2021, 11:46am

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

Yandros · October 11, 2021, 1:09pm

Thanks for pointing out both points

I had made the mistake not to read that RFC until now ; 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 . 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.

jbe · October 11, 2021, 2:46pm

@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.

Yandros · October 11, 2021, 4:04pm

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:

Yandros:

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.

jbe · October 11, 2021, 9:48pm

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.

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.

Yandros · October 12, 2021, 9:23am

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

jbe · October 12, 2021, 9:47am

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

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.

Yandros · October 13, 2021, 9:06am

jbe:

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.

The official documentation never delves too far w.r.t. lifetime (anti-)patterns and idioms, so it's rather the occasional blog post which may be more useful in that regard, at the cost of discoverability of the very post.

Related to this instance, rather than a pitfall, there is a rule of thumb which is that if you can use distinct lifetime parameters, then go for it / you should use as many distinct lifetime parameters as possible: the very mechanism of lifetimes is that when they appear repeated in several places of a signature they impose equality constraints.

A corollary of that rule of thumb is that lifetime elision thus very often does the right thing, and thus that lifetimes should rarely be named (although the corollary can't be applied to the situation in this thread, where we do need to name all the input lifetimes so that they all appear in the Future-existential return type).
A tangential version of this rule of thumb is that explicit ⊇-bounds on lifetimes (e.g., 'a : 'b) ought to be avoided, since they are almost always implicitly generated, and, again, if they are misused they may over-constrain the signature (c.f. the signature you had which reversed the bound and thus implicitly featured lifetime equality).

And, as your &'static Thing-yielding Iter<'lt> example showcases, there is a no reason that a borrowing entity such as Iter<'lt> should be yielding items that are bound with the very same lifetime.

In this area, especially regarding your code that compiles, you might have been surprised by a non-borrowing entity such as a vec! meeting the impl 'static bounds. But this is actually correct, since impl 'region_of_usability (or T : 'region_of_usability) is the way to express that, when you own an entity of that type, you can / are allowed to use it within that whole 'region_of_usability, even though, in practice, you rarely go that far. And, indeed, your Vec<&'static str>, much like a Vec<u8>, or a String or Vec<String>, they can all be owned indefinitely long, i.e., they can be owned within the never-ending 'static region, and so they are all very much 'static. This is different than, say, a Vec<&'short u8>, which may dangle / contain dangling references beyond that 'short region, and thus all we have is that it is 'short (more generally, it is 'c for any 'c where 'short ⊇ 'c).

So, back to the "where can I read about these things" question, you may be interested by the following blog post (if you haven't seen it already):

Common lifetime misconceptions

jbe · October 13, 2021, 10:11am

I did read through it some time before, but I didn't remember having seen this advice before:

It seems to make sense though, because:

That is very helpful to know / keep in mind.

I always thought of &'x T meaning that the reference lives at least as long as 'x. But apparently that is wrong, and the reference lives exactly as long as 'x.

Lifetimes seem to be the issue most people stumble upon (even when you think you have understood them), so maybe it would be wise to extend the documentation in that regard and to emphasize that in many cases you need distinct lifetime parameters. (I also remember a thread in this forum where someone was confused about why he/she can't use a single lifetime parameter.) But perhaps I was also not focussed enough when learning the language and missed some crucial parts.

steffahn · October 13, 2021, 11:17am

Well, perhaps most in this direction, and also directly related to your observation

is the

5) if it compiles then my lifetime annotations are correct

which actually features two examples where a problem is created by two lifetimes in a signature being the same (without any need for that in the implementation)

This interpretation of yours may have arisen because &'a T is covariant in 'a. Thus, even if you have two references &'a Foo and &'b Bar with two different lifetimes, you can still call a function fn baz<'c>(f: &'c Foo, b: &'c Bar) with them because &'a Foo can coerce to &'c Foo and 'b Bar can coerce to &'c Bar (as long ass 'a: 'c and 'b: 'c).

jbe · October 13, 2021, 11:33am

From my short time experimenting with Haskell, I often had the effect that "if it compiles, it is correct" (in Haskell!). Of course, that is an exaggeration.

Maybe Rust is different in that matter. I have meanwhile stumbled upon a lot of cases where code compiled, but was, in fact, very wrong. Rust (without unsafe) guarantees memory safety (if the code compiles), but it doesn't mean that the compiler helps you specifically to get your code right.

Don't get me wrong, I still love Rust's safety guarantees, because memory errors are most difficult to debug (and if I do not use unsafe, then I should not run into any of these). But I do have to keep in mind that compile-time checks are indeed limited and won't fix all my problems and mistakes.

jbe · October 13, 2021, 11:42am

Exactly (without having known the term "covariance" in that context at that time). I made that (wrong) interpretation due to observing Rust's behavior when calling functions.

steffahn · October 13, 2021, 11:43am

AFAIK, Rust is also often described this way. This kind of statement is of course limited. It’s more of a “if you know what you want, you can write it down, tweak it until it compiles and then it usually works”. With lifetimes, people often don’t know what they want at all, because they don’t understand lifetimes. When the approach is, try out random ways of assigning lifetimes until you find the first one that happens to compile, then it’s unlikely that the signature you found actually is the “correct” one. (This is especially true if you didn’t even write any uses of your function yet, how is the compiler supposed to be able to check that your function signature fits both the implementation of the function and the ways you’d like to use it, if the ways you’d like to use it aren’t even in your code yet?)

Maybe you could also view this as a rule of thumb: If you give incorrect type/function signatures, it’s hard to end up with the right thing. The compiler usually prefers to suggest you changing your implementation to fit the signature than to change the signature to fit the implementation. This applies to Haskell, too; but Haskell has the advantage that type signatures are optional – the language is better suited for type inference and the compiler can usually tell you the correct most general type signature to put on your function after you wrote it. Rust can’t do that; on one hand due to some language mechanisms like method resolution necessarily requiring types to already be known; on the other hand because the compiler currently won’t really accept you leaving out function signatures, even temporarily.

I imagine in the future, we could write a function without any lifetime annotations first (which would still result in a little unobtrusive error informing us that we’ll have to put them in eventually), but you can keep coding until all other errors/warning are gone, and then ask the compiler to fill in the lifetime details in function signatures for you in the most general manner possible, taking the function implementation into account.

The Rust Programming Language Forum

Avoiding heap allocations in (some) async trait methods

Putting it all together

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

2- Enter `type` aliases!

Explicit existential type aliases: `type Name<…> = impl …`

Demo

Implicit existential type aliases: `-> impl …`

Common lifetime misconceptions

Avoiding heap allocations in (some) async trait methods

Putting it all together

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

2- Enter type aliases!

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

Demo

Implicit existential type aliases: -> impl …

Common lifetime misconceptions

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

2- Enter `type` aliases!

Explicit existential type aliases: `type Name<…> = impl …`

Implicit existential type aliases: `-> impl …`