Auto merge of #61775 - nikomatsakis:issue-56238-multiple-lifetimes-async-fn-region-solver, r=MatthewJasper

generalize impl trait to permit multiple lifetime bounds

Generalizes the region solver to support "pick constraints". These have the form:

```
pick R0 from [R1..Rn]
```

where `R1..Rn` are called the "option regions". The idea is that `R0` must be equal to *some* region in the set `R1..Rn`. These constraints are then used to handle cases like this:

```rust
fn foo<'a, 'b>(...) -> impl Trait<'a, 'b> { .. }
```

The problem here is that every region R in the hidden type must be equal to *either* `'a` *or* `'b` (or `'static`) -- in the past, the only kinds of constraints we had were outlives constraints, and since `'a` and `'b` are unrelated, there was no outlives constraint we could issue that would enforce that (`R: 'a` and `R: 'b` are both too strict, for example). But now we can issue a pick constraint: `pick R from ['a, 'b]`.

In general, solving pick constraints is tricky. We integrate them into the solver as follows. In general, during the propagation phase, we are monotonically growing a set of inference regions. To handle a case like `pick R from [O...]`, where `O...` represents the option regions, we do the following:

- Look for all the *lower bounds* of the region R -- that is, every region LB such that `R: LB` must hold.
- Look for all the *upper bounds* of the region R -- that is, every region UB such that `UB: R` must hold.
- Let the *viable options* be each option region O such that `UB: O` and `O: LB` for each UB, LB bound.
- Find the *minimal viable option* M, where `O: M` holds for every option region O.

If there is such a *minimal viable option*, then we make `R: M`. (This may in turn influence other bits of inference.) If there is no minimal viable option, either because all options were eliminated or because none of the remaining options are minimal, we do nothing. Ultimately, if the pick constraint is not satisfied, an error is reported.

For this logic, we currently require that the option regions O are always lifetime parameters. To determine the bounds, we walk the various outlives edges that were otherwise introduced.

r? @matthewjasper
cc @cramertj

Fixes #56238

TODO:

- [ ] Error messages include region variable info sometimes, how to fix?
- [ ] Tests for bare `existential type`  and other impl Trait usage

1 files changed, 18 insertions, 0 deletions

diff --git a/src/test/ui/async-await/multiple-lifetimes/variance.rs b/src/test/ui/async-await/multiple-lifetimes/variance.rs
new file mode 100644
index 00000000000..b52ad17d563
--- /dev/null
+++ b/src/test/ui/async-await/multiple-lifetimes/variance.rs
@@ -0,0 +1,18 @@
+// edition:2018
+// run-pass
+
+// Test for async fn where the parameters have distinct lifetime
+// parameters that appear in all possible variances.
+
+#![feature(async_await)]
+
+#[allow(dead_code)]
+async fn lotsa_lifetimes<'a, 'b, 'c>(_: fn(&'a u8), _: fn(&'b u8) -> &'b u8, _: fn() -> &'c u8) { }
+
+fn take_any(_: &u8) { }
+fn identify(x: &u8) -> &u8 { x }
+fn give_back() -> &'static u8 { &22 }
+
+fn main() {
+    let _ = lotsa_lifetimes(take_any, identify, give_back);
+}