rework min_choice algorithm of member constraints

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

7 files changed, 264 insertions, 0 deletions

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() {}