# Notes on issue 57374

Github issue [#57374](https://github.com/rust-lang/rust/issues/57374). Since the Return of the Leak Check™, the flag `-Zno-leak-check` needs to be passed so that the regular Universes code runs, causing this issue.

#![feature(nll)]

fn main() {
    let x: fn(&'static ()) = |_| {};
    let y: for<'a> fn(&'a ()) = x;
}

error: higher-ranked subtype error
  --> src/main.rs:18:33
   |
18 |     let x: fn(&'static ()) = |_| {};
   |            ^^^^^^^^^^^^^^^

error: aborting due to previous error

The following points are ordered in the order I've chronologically looked at them during my investigations, not by importance.

#### 1. The span points at the type of `x`.

The error is the invalid assignment of `x` to `y` but the chosen span does not show that.

The piece of code responsible for finding the span here is: `find_outlives_blame_span` from the [error_reporting module](https://github.com/rust-lang/rust/blob/f47ec2ad5b6887b3d400aee49e2294bd27733d18/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs#L699), but it delegates most of that work to `best_blame_constraint` [here](https://github.com/rust-lang/rust/blob/f47ec2ad5b6887b3d400aee49e2294bd27733d18/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs#L62-L146).

We're looking for the best span to blame for the fact that `'_#20r: '_#0r`.
`'_#20r` is the bound universal region we're checking: a variable whose origin is a Placeholder in U7.

We start with the constraint path between the two regions, via `find_constraint_paths_between_regions`.

Here, we have this path:

[
"(\'_#20r: \'_#4r) due to Single(bb0[8]) - category: Assignment",
"(\'_#4r: \'_#6r) due to All(...) - category: TypeAnnotation",
"(\'_#6r: \'_#0r) due to All(...) - category: BoringNoLocation"
]

- `bb0[8]` is the assignment `_3 = _1`.
- the type of `_3` is `for<'a> fn(&ReLateBound(DebruijnIndex(0), BrNamed(crate0:DefIndex(1:10), 'a)) ()) // "y"`
- the type of `_1` is `fn(&'_#4r ()) // "x"`

More info about the other variables:
- `'_#4r` has an `Existential` NLLRegionVariableOrigin
- `'_#6r` has an `Existential` NLLRegionVariableOrigin

We then walk this chain of constraints backwards, choosing the "best span to cite", using a few factors. Here, the constraint category is the most important one: the `BoringNoLocation` is ignored, and we have a `TypeAnnotation` "before" the `Assignment` so this span is considered the best. (As this category is found first, the SCC of the later constraints doesn't matter)

#### 2. The span can be incorrect in other similar cases.

In similar looking code, the structure of the constraint path would be the same, with the late `TypeAnnotation` causing to show the wrong span.

For example, as an argument in a function call, like so:

#![feature(nll)]

fn main() {
    let x: fn(&'static ()) = |_| {};
    f(x);
}

fn f(y: for<'a> fn(&'a ())) {
}

Resulting in the same span as before:

error: higher-ranked subtype error
  --> src/main.rs:18:33
   |
18 |     let x: fn(&'static ()) = |_| {};
   |            ^^^^^^^^^^^^^^^

error: aborting due to previous error

Here, we have this path:

[
"(\'_#9r: \'_#6r) due to Single(bb0[9]) - category: CallArgument",
"(\'_#6r: \'_#4r) due to Single(bb0[8]) - category: Boring",
"(\'_#4r: \'_#7r) due to All(...) - category: TypeAnnotation",
"(\'_#7r: \'_#0r) due to All(...) - category: BoringNoLocation"
]

It's possible similar looking code causing different categories of constraints would be similarly showing the wrong span:

- when "very interesting" constraint categories are late in the chain: like the `TypeAnnotation` in these examples, but the same applies to `Return` and `Yield`.
- when other "less interesting" constraint categories are early in the chain before the "very interesting" ones (`Cast`, `ClosureBounds`, etc.)

It may be interesting to try to find other examples where these less interesting categories other than `Assignment` and `CallArgument` show up early like here ?

#### 3. The higher-ranked subtype error itself

With the leak check, or AST borrowck, the error is pointing at the assignment:

error[E0308]: mismatched types
  --> src/main.rs:39:33
   |
39 |     let y: for<'a> fn(&'a ()) = x;
   |                                 ^ expected concrete lifetime, found bound lifetime parameter 'a
   |
   = note: expected type `for<'a> fn(&'a ())`
              found type `fn(&'static ())`

AST borrowck finds this type error as a `RegionsPlaceholderMismatch` (ultimately, "one type is more general than the other"), while the leak-check as a `RegionsOverlyPolymorphic` (ultimately, "expected concrete lifetime, found bound lifetime parameter 'a").

With NLLs, MIR borrowck will call `nll::compute_regions`, which will want to solve the region constraints. `RegionInferenceContext::solve()` will check the universal regions (`check_universal_regions`), which will check the bound universal regions (`check_bound_universal_region`) for the placeholders.

Checking `'_#20r` here will first find the error element `Location(bb0[0])` (which seems to be `StorageLive(_1)` ?), as the first `Location` element contained in the SCC.

This seems interesting, all the SCC elements wouldn't have the same "error region" -- but likely the same starting and ending points in the constraint paths, all leading to the erroneous constraint ? This would make sense that we take the first SCC element here, if all paths lead to Rome.

In any case, here are SCC 18's 17 elements:

[
Location(bb0[0]), Location(bb0[1]), Location(bb0[2]), Location(bb0[3]),
Location(bb0[4]), Location(bb0[5]), Location(bb0[6]), Location(bb0[7]),
Location(bb0[8]), Location(bb0[9]), Location(bb0[10]), Location(bb0[11]),
Location(bb0[12]), Location(bb0[13]), Location(bb0[14]),
RootUniversalRegion('_#0r), RootUniversalRegion('_#1r)
]

The 17 "error regions" for these elements:

[
'_#0r, '_#0r, '_#0r, '_#3r,
'_#0r, '_#0r, '_#0r, '_#0r,
'_#0r, '_#0r, '_#0r, '_#0r,
'_#0r, '_#0r, '_#0r,
'_#0r, '_#1r
]

`'_#3r` looks different so let's trace this instead, similarly to how we traced `'_#0r` earlier.

`'_#3r` is coming from `Location(bb0[3])` — that is, the statement `_1 = move _2 as fn(&'_#3r ()) (ClosureFnPointer);` which involves `_1` a part of our erroneous assignment `_3 = _1;`. Like `'_#4r` and `'_#6r`, it has an `Existential` NLLRegionVariableOrigin.

The span found by `find_outlives_blame_span` for region `'_#3r`, `bb0[3]`, is a bit different this time, but still wrong:

let x: fn(&'static ()) = |_| {};
                         ^^^^^^

The constraint path between `'_#20r` and `'_#3r` is:

[
"(\'_#20r: \'_#4r) due to Single(bb0[8]) - category: Assignment",
"(\'_#4r: \'_#3r) due to Single(bb0[3]) - category: Assignment"
]

and `bb0[8]`, as before, would be the one we want.

Once again, we have `bb0[8]` at the beginning of the constraint path, just like the constraint path explored in part 1. These 2 different paths lead to what appears to be the erroneous assigment.

In this case, there are only `Assignment`s in the constraint path, and the reason this span was chosen was because of [this test](https://github.com/rust-lang/rust/blob/a21d82438b72a0394a670b6bfe95e3e62ee08802/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs#L131): `'_#3r` is in SCC 1 and not 18.

(Anecdote, but this is the error region with the shortest constraint path between the free region and the error region, maybe that's an interesting property ? Here:
- `'_#20r` -> `'_#0r`: length 3
- `'_#20r` -> `'_#3r`: length 2
- `'_#20r` -> `'_#1r`: length 4)

So, some questions I have left, assuming the previous analysis is somewhat on the right track:
- What is [this](https://github.com/rust-lang/rust/blob/a21d82438b72a0394a670b6bfe95e3e62ee08802/src/librustc_mir/borrow_check/nll/region_infer/mod.rs#L1294-L1300) trying to find ? Is it picking the error element and error region we expect here (if all these paths would lead to the expected error here, the answer would be yes) ? Do we still want to use `find_outlives_blame_span` ? If so, how do we want it to work to return the beginning of the path here, when it was tailored to work backwards from the end of path ? Do higher-ranked errors require forwards traversal ?
- What is the error we want to emit for higher-rank subtype errors ? How to find the data it would need (without extracting it from the MIR itself in this function) ? The `nice_region_error`s could be probably be used but I don't know where to find the information they need ( for example, the "Expected/Found" errors). Is it still stored at this point in the compilation pipeline, and if so, where ?

##### Note:

The similar following example shows that as long as a lifetime is specified in `x`'s type', the example code will fail (except, say, `'_` which should be in this context similar to the forall we need here -- maybe surprising that it can mean both existential and universal depending on the context but it makes sense).

It might be interesting for a rustc regression test ?

#![feature(nll)]

fn f<'a>() {
    let x: fn(&'a ()) = |_| {};
    let y: for<'b> fn(&'b ()) = x;
}

fn main() {}

---

#### 4. Survey of tests with higher-ranked subtype errors

To have a better understanding on how `check_bound_universal_region` currently behaves, here's a summary of what rustc's existing tests errors look like.

There are 3 such errors in the tests.

##### 4.1. `universe_violation.rs`

Very interesting because [it looks similar](https://github.com/rust-lang/rust/blob/906deae0790bd18681b937fe9a141a3c26cf1855/src/test/ui/nll/relate_tys/universe-violation.rs) to the code in the issue.

Minimized and made to look even more similar:

fn make_it() -> fn(&'static ()) {
    panic!()
}

fn main() {
    let a: fn(&'static ()) = make_it();
    let b: fn(&()) = a;
}

error: higher-ranked subtype error
  --> src/main.rs:40:22
   |
40 |     let b: fn(&()) = a;
                          ^

Interestingly, the span is correct, even with a constraint path is very similar to path explored in part 3, without `TypeAnnotation`s:

[
"(\'_#17r: \'_#2r) due to Single(bb2[3]) - category: Assignment",
"(\'_#2r: \'_#0r) due to Single(bb0[1]) - category: Assignment"
]

(Note: no constraint path from `'_#17r` to the error regions from the 15 elements in SCC 17 contain a `TypeAnnotation`)

The correct span is displayed here, because of the "unusual" case [here](https://github.com/rust-lang/rust/blob/a21d82438b72a0394a670b6bfe95e3e62ee08802/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs#L138-L145): the search failed and everything is indeed in the same SCC 17 (as mentioned before, this wasn't the case for the code in the issue).

##### 4.2. `relate_tys/hr-fn-aaa-as-aba.rs foo()`

Exploring this doesn't matter much: there's only one span in the running here, all the constraints for this error are coming from a single MIR statement.

#![feature(nll)]

fn make_it() -> for<'a> fn(&'a u32, &'a u32) -> &'a u32 {
    panic!()
}

fn foo() {
    let a: for<'a, 'b> fn(&'a u32, &'b u32) -> &'a u32 = make_it();
}

fn main() { }

error: higher-ranked subtype error
  --> src/main.rs:39:58
   |
39 |     let a: for<'a, 'b> fn(&'a u32, &'b u32) -> &'a u32 = make_it();
   |                                                          ^^^^^^^^^

Again, no `TypeAnnotation` in the constraint path:

[
"(\'_#27r: \'_#28r) due to Single(bb0[1]) - category: Assignment",
"(\'_#28r: \'_#26r) due to Single(bb0[1]) - category: Assignment"
]

`'_#27r` is in SCC 20, and `'_#26r` in SCC 19.

##### 4.3. `relate_tys/hr-fn-aaa-as-aba.rs bar()`

This is turning the previous `foo()` test code in a pattern, going through a slightly different code path.

#![feature(nll)]

fn make_it() -> for<'a> fn(&'a u32, &'a u32) -> &'a u32 {
    panic!()
}

fn bar() {
    let _: for<'a, 'b> fn(&'a u32, &'b u32) -> &'a u32 = make_it();
}

fn main() { }

error: higher-ranked subtype error
  --> src/main.rs:39:12
   |
39 |     let _: for<'a, 'b> fn(&'a u32, &'b u32) -> &'a u32 = make_it();
   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This behaves a bit like the code in the issue, pointing to the type, I wonder if that's intended ?

In any case there's only one span in the running, like `foo()`, but this time it's chosen reluctantly:

[
"(\'_#14r: \'_#15r) due to All(...) - category: BoringNoLocation",
"(\'_#15r: \'_#13r) due to All(...) - category: BoringNoLocation"
]

The first constraint is picked because of the "unusual" case [again](https://github.com/rust-lang/rust/blob/a21d82438b72a0394a670b6bfe95e3e62ee08802/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs#L138-L145) but for different reasons: the search failed because no `ConstraintCategory` was of interest, all the `BoringNoLocation`s are ignored (not that it would matter much here, but they were in different SCCs -- 10 and 9 respectively -- while the linked comment mostly references the unusual case for a single SCC).