async fn should support multiple lifetimes

[withoutboats]

According to the RFC, the async fn syntax is supposed to capture all input lifetimes in the implicit outer return type. Currently it only captures one elided lifetime, and returns errors regarding other lifetimes.

This needs to be changed so that all lifetimes are captured in async fn.

Example:

async fn foo(x: &mut i32, y: &mut i32) -> i32 {
    *x += *y;
    *y += *x;
    *x + *y
}

Playground: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2015&gist=1953befb5a939c1379468aae9788dac8

cc @cramertj @Nemo157

[Nemo157]

In case this helps either ideas on how to fix this, or others that get stuck with needing this, here's a way to write this that compiles currently, using the normal multi-lifetime Captures workaround for impl Trait:

fn foo<'a: 'c, 'b: 'c, 'c>(
    x: &'a mut i32,
    y: &'b mut i32,
) -> impl Future<Output = i32> + Captures<'a> + Captures<'b> + 'c {
    async move {
        *x += *y;
        *y += *x;
        *x + *y
    }
}

Playground: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=d8199b6efc90fe1c3e5df485a5006d15

[cramertj]

(note that in order for that to work you have to still introduce a third lifetime, 'c, which outlives all of the lifetimes used elsewhere)

[Nemo157]

(note that in order for that to work you have to still introduce a third lifetime, 'c, which outlives all of the lifetimes used elsewhere)

Isn't it a new lifetime that is outlived by all the lifetimes used elsewhere (i.e. the returned future can only live for the intersection of all incoming data's lifetimes).

[cramertj]

Yes, you're correct.

[bbangert]

I ran into this on my first attempt to make some small async programs with nightly, the Capture workaround gets unwieldy fast as a fn has more elided lifetimes.

[nikomatsakis]

Marking as a blocker. We spent quite a lot of time discussing how to fix this (recorded here). The short version is that we will alter the desugaring of async fn to capture all the lifetimes that appear in the inputs and so forth. Some notes here.

I think @cramertj was planning to take this on, but not 100% sure.

[nikomatsakis]

So @cramertj and I had a big meeting about this (video). We took some notes in this dropbox paper.

For the time being, we are hoping to make a "fairly small" change and see how far it takes us. The basic idea is that we will add a form of constraint R0 in {R1..Rn}, which asserts that the variable R0 must be equal to one of the regions R1..Rn. For some simple cases, this is quite unambiguous. For others, it is not really sufficient, but we'll defer that.

As a working example, consider this one:

existential type T<'a, 'b>; // = (&'a (), &'b ())
fn foo<'a, 'b>(x: &'a (), y: &'b ()) -> T<'a, 'b> { (x, y) }

Here, what would happen is roughly like this (borrowed from the dropbox paper):

• we will create a type variable ?H representing the hidden type
  • (&'0 (), &'1 ())
• (&'a (), &'b ()) <: (&'0 () ,&'1 ())
  • 'a: '0
  • 'b: '1
• '0 in { 'a, 'b, 'static }
• '1 in { 'a, 'b, 'static }

Our goal is basically to convert these "in" constraints into equality constraints, in the case where exactly one of the choices should work. In this case, if we look at '0, we could iterate through the constraints to find that 'a: '0 must hold. If we then iterate through the choices, we will find that 'a: 'a holds, but 'a: 'b and 'a: 'static do not.

At present, we can ensure that we only add these "in" bounds for cases where we have -> impl Trait or some other similar construct, which means that the regions R1..Rn will all be "free regions" declared on the function. This makes comparison relatively easy.

Extending the lexical solver. The idea would be to do a sort of pre-pass, I imagine -- we would walk the region graph starting from R0 and find all successors (Rs) and predecessors (Rp) from R0, filtering down to just free regions (as well as 'static). We would then iterate through the regions in the "in" set and compare against the successors/predecessors. If we find exactly one region that matches, we can add an additional equality constraint, setting R0 to that region.

I think I would just do this as a pre-pass, even though it's sort of inefficient in some sense -- i.e., we'll be walking the regiion graph once per constraint etc. There won't be many of these constraints so I don't think it'll be a particularly efficiency concern.

Extending the NLL solver. This is perhaps a more interesting question. The NLL solver works rather differently than the lexical solver. It begins with a constraint set, which it converts into a graph. For this graph, it computes the SCCs of the graph, resulting in a tree. It then walks from the leaves of the tree up, merging the bits from the children into the parent.

We have a few options here. We could do a similar graph walk but before the SCC computation. We could then convert "in" constraints into new edges in the graph, and ultimately do the SCC computation on this combined graph. (Note that the ConstraintSet representation would need to be converted to a graph to make the traversal efficient.)

An alternative would be to try and convert "in" constraints after the SCCs are computed. The advantage here is that the "depth-first search" just becomes walking all the parents in the SCC tree and all the children. If we found we could convert an "in" constraint, we would presumably "set" the value of the given region to contain the appropriate bits. However, this would come with a complication for diagnostics -- if that value resulted in an error, we would need to include some indication that those bits arose from an "in" constraint and adjust some of the diagnostic code appropriately (currently, it assumes that bits either come from liveness constraints or from the constraint graph, and this would kind of be a new thing). I'm not 100% sure which bits of code would need to change. This feels like a more complex but ultimately more efficient way to go about things.

OK, these are some high-level notes, I can try to lower them into more actionable steps. One thing I'm not sure about, for example, is where to detect that these "in" constraints are needed and how to "materialize" them. Presumably the code should live somewhere in the vicinity of the "opaque types" code.

[nikomatsakis]

I spent some time reading into the related code etc and refreshing my memory how things work.

Presumably the plan is going to look something like this:

Extend the RegionConstraintData structure with a new sort of constraint, the "in" constraint.

Modify the the code that constrains opaque type values. If there is no "least" constraint, we presently report an error, but I think we ought to be adding an "in" constraint.

Then we have to modify the solvers: we may be able to avoid modifying the lexical solver, since async fn is 2018 only -- we could say that if we are not using the NLL borrowck, then we continue to report an error unless there is a "least region".

We'll have to pass these 'in constraints' into the NLL solver. I think I would probably begin by converting them into the simpler constraints as I described before, versus integrating them as "first class" things.