rework min_choice algorithm of member constraints

See the inline comments for the description of the new algorithm.

8 files changed, 288 insertions, 11 deletions

diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index 308f6e19a73..9dd5a6c7607 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -739,20 +739,33 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         }
         debug!(?choice_regions, "after ub");
 
-        // If we ruled everything out, we're done.
-        if choice_regions.is_empty() {
-            return false;
-        }
-
-        // Otherwise, we need to find the minimum remaining choice, if
-        // any, and take that.
-        debug!("choice_regions remaining are {:#?}", choice_regions);
-        let Some(&min_choice) = choice_regions.iter().find(|&r1| {
+        // At this point we can pick any member of `choice_regions`, but to avoid potential
+        // non-determinism we will pick the *unique minimum* choice.
+        //
+        // Because universal regions are only partially ordered (i.e, not every two regions are
+        // comparable), we will ignore any region that doesn't compare to all others when picking
+        // the minimum choice.
+        // For example, consider `choice_regions = ['static, 'a, 'b, 'c, 'd, 'e]`, where
+        // `'static: 'a, 'static: 'b, 'a: 'c, 'b: 'c, 'c: 'd, 'c: 'e`.
+        // `['d, 'e]` are ignored because they do not compare - the same goes for `['a, 'b]`.
+        let totally_ordered_subset = choice_regions.iter().copied().filter(|&r1| {
             choice_regions.iter().all(|&r2| {
-                self.universal_region_relations.outlives(r2, *r1)
+                self.universal_region_relations.outlives(r1, r2)
+                    || self.universal_region_relations.outlives(r2, r1)
             })
+        });
+        // Now we're left with `['static, 'c]`. Pick `'c` as the minimum!
+        let Some(min_choice) = totally_ordered_subset.reduce(|r1, r2| {
+            let r1_outlives_r2 = self.universal_region_relations.outlives(r1, r2);
+            let r2_outlives_r1 = self.universal_region_relations.outlives(r2, r1);
+            match (r1_outlives_r2, r2_outlives_r1) {
+                (true, true) => r1.min(r2),
+                (true, false) => r2,
+                (false, true) => r1,
+                (false, false) => bug!("incomparable regions in total order"),
+            }
         }) else {
-            debug!("no choice region outlived by all others");
+            debug!("no unique minimum choice");
             return false;
         };
 
diff --git a/tests/ui/async-await/multiple-lifetimes/member-constraints-min-choice-issue-63033.rs b/tests/ui/async-await/multiple-lifetimes/member-constraints-min-choice-issue-63033.rs
new file mode 100644
index 00000000000..614f1897291
--- /dev/null
+++ b/tests/ui/async-await/multiple-lifetimes/member-constraints-min-choice-issue-63033.rs
@@ -0,0 +1,10 @@
+// Regression test for #63033.
+
+// check-pass
+// edition: 2018
+
+async fn test1(_: &'static u8, _: &'_ u8, _: &'_ u8) {}
+
+async fn test2<'s>(_: &'s u8, _: &'_ &'s u8, _: &'_ &'s u8) {}
+
+fn main() {}
diff --git a/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.rs b/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.rs
new file mode 100644
index 00000000000..52ea0f28d69
--- /dev/null
+++ b/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.rs
@@ -0,0 +1,43 @@
+// ... continued from ./min-choice.rs
+
+// check-fail
+
+trait Cap<'a> {}
+impl<T> Cap<'_> for T {}
+
+fn type_test<'a, T: 'a>() -> &'a u8 { &0 }
+
+// Make sure we don't pick `'b`.
+fn test_b<'a, 'b, 'c, T>() -> impl Cap<'a> + Cap<'b> + Cap<'c>
+where
+    'a: 'b,
+    'a: 'c,
+    T: 'b,
+{
+    type_test::<'_, T>() // This should pass if we pick 'b.
+    //~^ ERROR the parameter type `T` may not live long enough
+}
+
+// Make sure we don't pick `'c`.
+fn test_c<'a, 'b, 'c, T>() -> impl Cap<'a> + Cap<'b> + Cap<'c>
+where
+    'a: 'b,
+    'a: 'c,
+    T: 'c,
+{
+    type_test::<'_, T>() // This should pass if we pick 'c.
+    //~^ ERROR the parameter type `T` may not live long enough
+}
+
+// We need to pick min_choice from `['b, 'c]`, but it's ambiguous which one to pick because
+// they're incomparable.
+fn test_ambiguous<'a, 'b, 'c>(s: &'a u8) -> impl Cap<'b> + Cap<'c>
+where
+    'a: 'b,
+    'a: 'c,
+{
+    s
+    //~^ ERROR captures lifetime that does not appear in bounds
+}
+
+fn main() {}
diff --git a/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.stderr b/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.stderr
new file mode 100644
index 00000000000..1e6ef614dee
--- /dev/null
+++ b/tests/ui/nll/member-constraints/min-choice-reject-ambiguous.stderr
@@ -0,0 +1,40 @@
+error[E0309]: the parameter type `T` may not live long enough
+  --> $DIR/min-choice-reject-ambiguous.rs:17:5
+   |
+LL |     type_test::<'_, T>() // This should pass if we pick 'b.
+   |     ^^^^^^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds
+   |
+help: consider adding an explicit lifetime bound...
+   |
+LL |     T: 'b + 'a,
+   |           ++++
+
+error[E0309]: the parameter type `T` may not live long enough
+  --> $DIR/min-choice-reject-ambiguous.rs:28:5
+   |
+LL |     type_test::<'_, T>() // This should pass if we pick 'c.
+   |     ^^^^^^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds
+   |
+help: consider adding an explicit lifetime bound...
+   |
+LL |     T: 'c + 'a,
+   |           ++++
+
+error[E0700]: hidden type for `impl Cap<'b> + Cap<'c>` captures lifetime that does not appear in bounds
+  --> $DIR/min-choice-reject-ambiguous.rs:39:5
+   |
+LL | fn test_ambiguous<'a, 'b, 'c>(s: &'a u8) -> impl Cap<'b> + Cap<'c>
+   |                   -- hidden type `&'a u8` captures the lifetime `'a` as defined here
+...
+LL |     s
+   |     ^
+   |
+help: to declare that `impl Cap<'b> + Cap<'c>` captures `'a`, you can add an explicit `'a` lifetime bound
+   |
+LL | fn test_ambiguous<'a, 'b, 'c>(s: &'a u8) -> impl Cap<'b> + Cap<'c> + 'a
+   |                                                                    ++++
+
+error: aborting due to 3 previous errors
+
+Some errors have detailed explanations: E0309, E0700.
+For more information about an error, try `rustc --explain E0309`.
diff --git a/tests/ui/nll/member-constraints/min-choice.rs b/tests/ui/nll/member-constraints/min-choice.rs
new file mode 100644
index 00000000000..14b4dae7abf
--- /dev/null
+++ b/tests/ui/nll/member-constraints/min-choice.rs
@@ -0,0 +1,34 @@
+// Assuming that the hidden type in these tests is `&'_#15r u8`,
+// we have a member constraint: `'_#15r member ['static, 'a, 'b, 'c]`.
+//
+// Make sure we pick up the minimum non-ambiguous region among them.
+// We will have to exclude `['b, 'c]` because they're incomparable,
+// and then we should pick `'a` because we know `'static: 'a`.
+
+// check-pass
+
+trait Cap<'a> {}
+impl<T> Cap<'_> for T {}
+
+fn type_test<'a, T: 'a>() -> &'a u8 { &0 }
+
+// Basic test: make sure we don't bail out because 'b and 'c are incomparable.
+fn basic<'a, 'b, 'c>() -> impl Cap<'a> + Cap<'b> + Cap<'c>
+where
+    'a: 'b,
+    'a: 'c,
+{
+    &0
+}
+
+// Make sure we don't pick `'static`.
+fn test_static<'a, 'b, 'c, T>() -> impl Cap<'a> + Cap<'b> + Cap<'c>
+where
+    'a: 'b,
+    'a: 'c,
+    T: 'a,
+{
+    type_test::<'_, T>() // This will fail if we pick 'static
+}
+
+fn main() {}
diff --git a/tests/ui/nll/member-constraints/nested-impl-trait-fail.rs b/tests/ui/nll/member-constraints/nested-impl-trait-fail.rs
new file mode 100644
index 00000000000..66ff828a84f
--- /dev/null
+++ b/tests/ui/nll/member-constraints/nested-impl-trait-fail.rs
@@ -0,0 +1,33 @@
+// Nested impl-traits can impose different member constraints on the same region variable.
+
+// check-fail
+
+trait Cap<'a> {}
+impl<T> Cap<'_> for T {}
+
+// Assuming the hidden type is `[&'_#15r u8; 1]`, we have two distinct member constraints:
+// - '_#15r member ['static, 'a, 'b] // from outer impl-trait
+// - '_#15r member ['static, 'a, 'b] // from inner impl-trait
+// To satisfy both we can choose 'a or 'b, so it's a failure due to ambiguity.
+fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>
+where
+    's: 'a,
+    's: 'b,
+{
+    [a]
+    //~^ E0700
+    //~| E0700
+}
+
+// Same as the above but with late-bound regions.
+fn fail_late_bound<'s, 'a, 'b>(
+    a: &'s u8,
+    _: &'a &'s u8,
+    _: &'b &'s u8,
+) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>> {
+    [a]
+    //~^ E0700
+    //~| E0700
+}
+
+fn main() {}
diff --git a/tests/ui/nll/member-constraints/nested-impl-trait-fail.stderr b/tests/ui/nll/member-constraints/nested-impl-trait-fail.stderr
new file mode 100644
index 00000000000..6824e27ead0
--- /dev/null
+++ b/tests/ui/nll/member-constraints/nested-impl-trait-fail.stderr
@@ -0,0 +1,75 @@
+error[E0700]: hidden type for `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures lifetime that does not appear in bounds
+  --> $DIR/nested-impl-trait-fail.rs:17:5
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>
+   |                     -- hidden type `[&'s u8; 1]` captures the lifetime `'s` as defined here
+...
+LL |     [a]
+   |     ^^^
+   |
+help: to declare that `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>> + 's
+   |                                                                                                ++++
+help: to declare that `impl Cap<'a> + Cap<'b>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b> + 's>
+   |                                                                                               ++++
+
+error[E0700]: hidden type for `impl Cap<'a> + Cap<'b>` captures lifetime that does not appear in bounds
+  --> $DIR/nested-impl-trait-fail.rs:17:5
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>
+   |                     -- hidden type `&'s u8` captures the lifetime `'s` as defined here
+...
+LL |     [a]
+   |     ^^^
+   |
+help: to declare that `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>> + 's
+   |                                                                                                ++++
+help: to declare that `impl Cap<'a> + Cap<'b>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | fn fail_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b> + 's>
+   |                                                                                               ++++
+
+error[E0700]: hidden type for `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures lifetime that does not appear in bounds
+  --> $DIR/nested-impl-trait-fail.rs:28:5
+   |
+LL | fn fail_late_bound<'s, 'a, 'b>(
+   |                    -- hidden type `[&'s u8; 1]` captures the lifetime `'s` as defined here
+...
+LL |     [a]
+   |     ^^^
+   |
+help: to declare that `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | ) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>> + 's {
+   |                                                       ++++
+help: to declare that `impl Cap<'a> + Cap<'b>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | ) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b> + 's> {
+   |                                                      ++++
+
+error[E0700]: hidden type for `impl Cap<'a> + Cap<'b>` captures lifetime that does not appear in bounds
+  --> $DIR/nested-impl-trait-fail.rs:28:5
+   |
+LL | fn fail_late_bound<'s, 'a, 'b>(
+   |                    -- hidden type `&'s u8` captures the lifetime `'s` as defined here
+...
+LL |     [a]
+   |     ^^^
+   |
+help: to declare that `impl IntoIterator<Item = impl Cap<'a> + Cap<'b>>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | ) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b>> + 's {
+   |                                                       ++++
+help: to declare that `impl Cap<'a> + Cap<'b>` captures `'s`, you can add an explicit `'s` lifetime bound
+   |
+LL | ) -> impl IntoIterator<Item = impl Cap<'a> + Cap<'b> + 's> {
+   |                                                      ++++
+
+error: aborting due to 4 previous errors
+
+For more information about this error, try `rustc --explain E0700`.
diff --git a/tests/ui/nll/member-constraints/nested-impl-trait-pass.rs b/tests/ui/nll/member-constraints/nested-impl-trait-pass.rs
new file mode 100644
index 00000000000..15540cb460e
--- /dev/null
+++ b/tests/ui/nll/member-constraints/nested-impl-trait-pass.rs
@@ -0,0 +1,29 @@
+// Nested impl-traits can impose different member constraints on the same region variable.
+
+// check-pass
+
+trait Cap<'a> {}
+impl<T> Cap<'_> for T {}
+
+// Assuming the hidden type is `[&'_#15r u8; 1]`, we have two distinct member constraints:
+// - '_#15r member ['static, 'a, 'b] // from outer impl-trait
+// - '_#15r member ['static, 'a]     // from inner impl-trait
+// To satisfy both we can only choose 'a.
+fn pass_early_bound<'s, 'a, 'b>(a: &'s u8) -> impl IntoIterator<Item = impl Cap<'a>> + Cap<'b>
+where
+    's: 'a,
+    's: 'b,
+{
+    [a]
+}
+
+// Same as the above but with late-bound regions.
+fn pass_late_bound<'s, 'a, 'b>(
+    a: &'s u8,
+    _: &'a &'s u8,
+    _: &'b &'s u8,
+) -> impl IntoIterator<Item = impl Cap<'a>> + Cap<'b> {
+    [a]
+}
+
+fn main() {}