Auto merge of #67016 - lqd:placeholder_loans, r=matthewjasper

In which we implement illegal subset relations errors using Polonius

This PR is the rustc side of implementing subset errors using Polonius. That is, in
```rust
fn foo<'a, 'b>(x: &'a u32, y: &'b u32) -> &'a u32 {
    y
}
```
returning `y` requires that `'b: 'a` but we have no evidence of that, so this is an error. (Evidence that the relation holds could come from explicit bounds, or via implied bounds).

Polonius outputs one such error per CFG point where the free region's placeholder loan unexpectedly flowed into another free region. While all these CFG locations could be useful in diagnostics in the future, rustc does not do that (and the duplication is only partially handled in the rest of the errors/diagnostics infrastructure, e.g. duplicate suggestions will be shown by the "outlives suggestions" or some of the `#[rustc_*]` NLL/MIR debug dumps), so I deduplicated the errors.

(The ordering also matters, otherwise some of the elided lifetime naming would change behaviour).

I've blessed a couple of tests, where the output is currently suboptimal:
- the `hrtb-perfect-forwarding` tests mix subset errors with higher-ranked subtyping, however the plan is for chalk to eventually take care of some of this to generate polonius constraints (i.e. it's not polonius' job). Until that happens, polonius will not see the error that NLL sees.
- some other tests have errors and diagnostics specific to `'static`, I _believe_ this to be because of it being treated as more "special" than in polonius. I believe the output is not wrong, but could be better, and appears elsewhere (I feel we'll need to look at polonius' handling of `'static` at some point in the future, maybe to match a bit more what NLL does when it produces errors)

I'll create a tracking issue in the polonius repo to record these 2 points (and a general "we'll need to go over the blessed output" issue, much like we did for NLLs)

The last blessed test is because it's an improvement: in this case, more errors/suggestions were computed, instead of the existing code path where this case apparently stops at the first error.

The `Naive` variant in Polonius computes those errors, so this PR also switches the default variant to that, as we're also in the process of temporarily deactivating all other variants (which exist mostly for performance considerations) until we have completed more work on completeness and correctness, before focusing on efficiency once again.

While most of the correctness in this PR is hidden in the polonius compare-mode (which of course passes locally), I've added a couple of smoke-tests to the existing ones, so that we have some confidence that it works (and keeps working) until we're in a position where we can run them on CI.

As mentioned during yesterday's wg-polonius meeting, @nikomatsakis has already read through most of this PR (and which is matching  what they thought needed to be done [during the recent Polonius sprint](https://hackmd.io/CGMNjt1hR_qYtsR9hgdGmw#Compiler-notes-on-generating-the-placeholder-loans-support)), but Matthew was hopefully going to review (again, not urgent), so:

r? @matthewjasper

(This updates to the latest `polonius-engine` release, and I'm not sure whether `Cargo.lock` updates can easily be rolled up, but apart from that: this changes little that's tested on CI, so seems safe-ish to rollup ?)

7 files changed, 361 insertions, 0 deletions

diff --git a/src/test/ui/closures/closure-expected-type/expect-region-supply-region.polonius.stderr b/src/test/ui/closures/closure-expected-type/expect-region-supply-region.polonius.stderr
new file mode 100644
index 00000000000..2a7461fb469
--- /dev/null
+++ b/src/test/ui/closures/closure-expected-type/expect-region-supply-region.polonius.stderr
@@ -0,0 +1,56 @@
+error[E0521]: borrowed data escapes outside of closure
+  --> $DIR/expect-region-supply-region.rs:18:9
+   |
+LL |     let mut f: Option<&u32> = None;
+   |         ----- `f` is declared here, outside of the closure body
+LL |     closure_expecting_bound(|x| {
+   |                              - `x` is a reference that is only valid in the closure body
+LL |         f = Some(x);
+   |         ^^^^^^^^^^^ `x` escapes the closure body here
+
+error[E0521]: borrowed data escapes outside of closure
+  --> $DIR/expect-region-supply-region.rs:28:9
+   |
+LL |     let mut f: Option<&u32> = None;
+   |         ----- `f` is declared here, outside of the closure body
+LL |     closure_expecting_bound(|x: &u32| {
+   |                              - `x` is a reference that is only valid in the closure body
+LL |         f = Some(x);
+   |         ^^^^^^^^^^^ `x` escapes the closure body here
+
+error: lifetime may not live long enough
+  --> $DIR/expect-region-supply-region.rs:37:30
+   |
+LL | fn expect_bound_supply_named<'x>() {
+   |                              -- lifetime `'x` defined here
+...
+LL |     closure_expecting_bound(|x: &'x u32| {
+   |                              ^  - let's call the lifetime of this reference `'1`
+   |                              |
+   |                              requires that `'1` must outlive `'x`
+
+error[E0521]: borrowed data escapes outside of closure
+  --> $DIR/expect-region-supply-region.rs:42:9
+   |
+LL |     let mut f: Option<&u32> = None;
+   |         ----- `f` is declared here, outside of the closure body
+...
+LL |     closure_expecting_bound(|x: &'x u32| {
+   |                              - `x` is a reference that is only valid in the closure body
+...
+LL |         f = Some(x);
+   |         ^^^^^^^^^^^ `x` escapes the closure body here
+
+error: lifetime may not live long enough
+  --> $DIR/expect-region-supply-region.rs:37:30
+   |
+LL | fn expect_bound_supply_named<'x>() {
+   |                              -- lifetime `'x` defined here
+...
+LL |     closure_expecting_bound(|x: &'x u32| {
+   |                              ^ requires that `'x` must outlive `'static`
+   |
+   = help: consider replacing `'x` with `'static`
+
+error: aborting due to 5 previous errors
+
diff --git a/src/test/ui/hrtb/hrtb-perfect-forwarding.polonius.stderr b/src/test/ui/hrtb/hrtb-perfect-forwarding.polonius.stderr
new file mode 100644
index 00000000000..558d643cde8
--- /dev/null
+++ b/src/test/ui/hrtb/hrtb-perfect-forwarding.polonius.stderr
@@ -0,0 +1,68 @@
+warning: function cannot return without recursing
+  --> $DIR/hrtb-perfect-forwarding.rs:22:1
+   |
+LL | / fn no_hrtb<'b,T>(mut t: T)
+LL | |     where T : Bar<&'b isize>
+LL | | {
+LL | |     // OK -- `T : Bar<&'b isize>`, and thus the impl above ensures that
+LL | |     // `&mut T : Bar<&'b isize>`.
+LL | |     no_hrtb(&mut t);
+   | |     --------------- recursive call site
+LL | | }
+   | |_^ cannot return without recursing
+   |
+   = note: `#[warn(unconditional_recursion)]` on by default
+   = help: a `loop` may express intention better if this is on purpose
+
+warning: function cannot return without recursing
+  --> $DIR/hrtb-perfect-forwarding.rs:30:1
+   |
+LL | / fn bar_hrtb<T>(mut t: T)
+LL | |     where T : for<'b> Bar<&'b isize>
+LL | | {
+LL | |     // OK -- `T : for<'b> Bar<&'b isize>`, and thus the impl above
+...  |
+LL | |     bar_hrtb(&mut t);
+   | |     ---------------- recursive call site
+LL | | }
+   | |_^ cannot return without recursing
+   |
+   = help: a `loop` may express intention better if this is on purpose
+
+warning: function cannot return without recursing
+  --> $DIR/hrtb-perfect-forwarding.rs:39:1
+   |
+LL | / fn foo_hrtb_bar_not<'b,T>(mut t: T)
+LL | |     where T : for<'a> Foo<&'a isize> + Bar<&'b isize>
+LL | | {
+LL | |     // Not OK -- The forwarding impl for `Foo` requires that `Bar` also
+...  |
+LL | |     foo_hrtb_bar_not(&mut t);
+   | |     ------------------------ recursive call site
+LL | | }
+   | |_^ cannot return without recursing
+   |
+   = help: a `loop` may express intention better if this is on purpose
+
+error: higher-ranked subtype error
+  --> $DIR/hrtb-perfect-forwarding.rs:46:5
+   |
+LL |     foo_hrtb_bar_not(&mut t);
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^
+
+warning: function cannot return without recursing
+  --> $DIR/hrtb-perfect-forwarding.rs:49:1
+   |
+LL | / fn foo_hrtb_bar_hrtb<T>(mut t: T)
+LL | |     where T : for<'a> Foo<&'a isize> + for<'b> Bar<&'b isize>
+LL | | {
+LL | |     // OK -- now we have `T : for<'b> Bar&'b isize>`.
+LL | |     foo_hrtb_bar_hrtb(&mut t);
+   | |     ------------------------- recursive call site
+LL | | }
+   | |_^ cannot return without recursing
+   |
+   = help: a `loop` may express intention better if this is on purpose
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/impl-trait/multiple-lifetimes/error-handling.polonius.stderr b/src/test/ui/impl-trait/multiple-lifetimes/error-handling.polonius.stderr
new file mode 100644
index 00000000000..72e8fa33d7b
--- /dev/null
+++ b/src/test/ui/impl-trait/multiple-lifetimes/error-handling.polonius.stderr
@@ -0,0 +1,12 @@
+error: lifetime may not live long enough
+  --> $DIR/error-handling.rs:13:56
+   |
+LL | fn foo<'a, 'b, 'c>(x: &'static i32, mut y: &'a i32) -> E<'b, 'c> {
+   |        --  -- lifetime `'b` defined here               ^^^^^^^^^ opaque type requires that `'a` must outlive `'b`
+   |        |
+   |        lifetime `'a` defined here
+   |
+   = help: consider adding the following bound: `'a: 'b`
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/nll/outlives-suggestion-simple.polonius.stderr b/src/test/ui/nll/outlives-suggestion-simple.polonius.stderr
new file mode 100644
index 00000000000..815744618f6
--- /dev/null
+++ b/src/test/ui/nll/outlives-suggestion-simple.polonius.stderr
@@ -0,0 +1,121 @@
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:6:5
+   |
+LL | fn foo1<'a, 'b>(x: &'a usize) -> &'b usize {
+   |         --  -- lifetime `'b` defined here
+   |         |
+   |         lifetime `'a` defined here
+LL |     x
+   |     ^ returning this value requires that `'a` must outlive `'b`
+   |
+   = help: consider adding the following bound: `'a: 'b`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:10:5
+   |
+LL | fn foo2<'a>(x: &'a usize) -> &'static usize {
+   |         -- lifetime `'a` defined here
+LL |     x
+   |     ^ returning this value requires that `'a` must outlive `'static`
+   |
+   = help: consider replacing `'a` with `'static`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:14:5
+   |
+LL | fn foo3<'a, 'b>(x: &'a usize, y: &'b usize) -> (&'b usize, &'a usize) {
+   |         --  -- lifetime `'b` defined here
+   |         |
+   |         lifetime `'a` defined here
+LL |     (x, y)
+   |     ^^^^^^ function was supposed to return data with lifetime `'b` but it is returning data with lifetime `'a`
+   |
+   = help: consider adding the following bound: `'a: 'b`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:14:5
+   |
+LL | fn foo3<'a, 'b>(x: &'a usize, y: &'b usize) -> (&'b usize, &'a usize) {
+   |         --  -- lifetime `'b` defined here
+   |         |
+   |         lifetime `'a` defined here
+LL |     (x, y)
+   |     ^^^^^^ function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'b`
+   |
+   = help: consider adding the following bound: `'b: 'a`
+
+help: `'a` and `'b` must be the same: replace one with the other
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:22:5
+   |
+LL | fn foo4<'a, 'b, 'c>(x: &'a usize) -> (&'b usize, &'c usize) {
+   |         --  -- lifetime `'b` defined here
+   |         |
+   |         lifetime `'a` defined here
+...
+LL |     (x, x)
+   |     ^^^^^^ returning this value requires that `'a` must outlive `'b`
+   |
+   = help: consider adding the following bound: `'a: 'b`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:22:5
+   |
+LL | fn foo4<'a, 'b, 'c>(x: &'a usize) -> (&'b usize, &'c usize) {
+   |         --      -- lifetime `'c` defined here
+   |         |
+   |         lifetime `'a` defined here
+...
+LL |     (x, x)
+   |     ^^^^^^ returning this value requires that `'a` must outlive `'c`
+   |
+   = help: consider adding the following bound: `'a: 'c`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:31:9
+   |
+LL |     pub fn foo<'a>(x: &'a usize) -> Self {
+   |                -- lifetime `'a` defined here
+LL |         Foo { x }
+   |         ^^^^^^^^^ returning this value requires that `'a` must outlive `'static`
+   |
+   = help: consider replacing `'a` with `'static`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:41:9
+   |
+LL | impl<'a> Bar<'a> {
+   |      -- lifetime `'a` defined here
+LL |     pub fn get<'b>(&self) -> &'b usize {
+   |                -- lifetime `'b` defined here
+LL |         self.x
+   |         ^^^^^^ returning this value requires that `'a` must outlive `'b`
+   |
+   = help: consider adding the following bound: `'a: 'b`
+
+error: lifetime may not live long enough
+  --> $DIR/outlives-suggestion-simple.rs:52:9
+   |
+LL | impl<'a> Baz<'a> {
+   |      -- lifetime `'a` defined here
+LL |     fn get<'b>(&'b self) -> &'a i32 {
+   |            -- lifetime `'b` defined here
+LL |         self.x
+   |         ^^^^^^ returning this value requires that `'b` must outlive `'a`
+   |
+   = help: consider adding the following bound: `'b: 'a`
+
+error[E0521]: borrowed data escapes outside of function
+  --> $DIR/outlives-suggestion-simple.rs:73:9
+   |
+LL |     fn get_bar(&self) -> Bar2 {
+   |                -----
+   |                |
+   |                `self` is declared here, outside of the function body
+   |                `self` is a reference that is only valid in the function body
+LL |         Bar2::new(&self)
+   |         ^^^^^^^^^^^^^^^^ `self` escapes the function body here
+
+error: aborting due to 10 previous errors
+
diff --git a/src/test/ui/nll/polonius/subset-relations.rs b/src/test/ui/nll/polonius/subset-relations.rs
new file mode 100644
index 00000000000..3f6f67ebf40
--- /dev/null
+++ b/src/test/ui/nll/polonius/subset-relations.rs
@@ -0,0 +1,30 @@
+// Checks that Polonius can compute cases of universal regions errors:
+// "illegal subset relation errors", cases where analysis finds that
+// two free regions outlive each other, without any evidence that this
+// relation holds.
+
+// ignore-compare-mode-nll
+// compile-flags: -Z borrowck=mir -Zpolonius
+
+// returning `y` requires that `'b: 'a`, but it's not known to be true
+fn missing_subset<'a, 'b>(x: &'a u32, y: &'b u32) -> &'a u32 {
+    y //~ ERROR
+}
+
+// `'b: 'a` is explicitly declared
+fn valid_subset<'a, 'b: 'a>(x: &'a u32, y: &'b u32) -> &'a u32 {
+    y
+}
+
+// because of `x`, it is implied that `'b: 'a` holds
+fn implied_bounds_subset<'a, 'b>(x: &'a &'b mut u32) -> &'a u32 {
+    x
+}
+
+// `'b: 'a` is declared, and `'a: 'c` is known via implied bounds:
+// `'b: 'c` is therefore known to hold transitively
+fn transitively_valid_subset<'a, 'b: 'a, 'c>(x: &'c &'a u32, y: &'b u32) -> &'c u32  {
+    y
+}
+
+fn main() {}
diff --git a/src/test/ui/nll/polonius/subset-relations.stderr b/src/test/ui/nll/polonius/subset-relations.stderr
new file mode 100644
index 00000000000..63645106f82
--- /dev/null
+++ b/src/test/ui/nll/polonius/subset-relations.stderr
@@ -0,0 +1,14 @@
+error: lifetime may not live long enough
+  --> $DIR/subset-relations.rs:11:5
+   |
+LL | fn missing_subset<'a, 'b>(x: &'a u32, y: &'b u32) -> &'a u32 {
+   |                   --  -- lifetime `'b` defined here
+   |                   |
+   |                   lifetime `'a` defined here
+LL |     y
+   |     ^ function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'b`
+   |
+   = help: consider adding the following bound: `'b: 'a`
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/nll/user-annotations/closure-substs.polonius.stderr b/src/test/ui/nll/user-annotations/closure-substs.polonius.stderr
new file mode 100644
index 00000000000..d5bcdf64441
--- /dev/null
+++ b/src/test/ui/nll/user-annotations/closure-substs.polonius.stderr
@@ -0,0 +1,60 @@
+error: lifetime may not live long enough
+  --> $DIR/closure-substs.rs:8:16
+   |
+LL | fn foo<'a>() {
+   |        -- lifetime `'a` defined here
+...
+LL |         return x;
+   |                ^ returning this value requires that `'a` must outlive `'static`
+   |
+   = help: consider replacing `'a` with `'static`
+
+error: lifetime may not live long enough
+  --> $DIR/closure-substs.rs:15:16
+   |
+LL |     |x: &i32| -> &'static i32 {
+   |         - let's call the lifetime of this reference `'1`
+LL |         return x;
+   |                ^ returning this value requires that `'1` must outlive `'static`
+
+error: lifetime may not live long enough
+  --> $DIR/closure-substs.rs:15:16
+   |
+LL |     |x: &i32| -> &'static i32 {
+   |         -        ------------ return type of closure is &'2 i32
+   |         |
+   |         let's call the lifetime of this reference `'1`
+LL |         return x;
+   |                ^ returning this value requires that `'1` must outlive `'2`
+
+error: lifetime may not live long enough
+  --> $DIR/closure-substs.rs:22:9
+   |
+LL | fn bar<'a>() {
+   |        -- lifetime `'a` defined here
+...
+LL |         b(x);
+   |         ^^^^ argument requires that `'a` must outlive `'static`
+   |
+   = help: consider replacing `'a` with `'static`
+
+error[E0521]: borrowed data escapes outside of closure
+  --> $DIR/closure-substs.rs:29:9
+   |
+LL |     |x: &i32, b: fn(&'static i32)| {
+   |      - `x` is a reference that is only valid in the closure body
+LL |         b(x);
+   |         ^^^^ `x` escapes the closure body here
+
+error[E0521]: borrowed data escapes outside of closure
+  --> $DIR/closure-substs.rs:29:9
+   |
+LL |     |x: &i32, b: fn(&'static i32)| {
+   |      -        - `b` is declared here, outside of the closure body
+   |      |
+   |      `x` is a reference that is only valid in the closure body
+LL |         b(x);
+   |         ^^^^ `x` escapes the closure body here
+
+error: aborting due to 6 previous errors
+