Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[NLL] Bad higher ranked subtype error #57374

Open
matthewjasper opened this issue Jan 6, 2019 · 9 comments
Open

[NLL] Bad higher ranked subtype error #57374

matthewjasper opened this issue Jan 6, 2019 · 9 comments

Comments

@matthewjasper
Copy link
Contributor

@matthewjasper matthewjasper commented Jan 6, 2019

With the removal of the leak check the MIR type checker is now responsible for reporting higher-ranked lifetime errors in full NLL mode. The error messages are not currently very helpful, since they weren't user visible until now.

The following code (play):

#![feature(nll)]

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

gives the following output

error: higher-ranked subtype error
  --> <source>:19:12
   |
19 |     let x: fn(&'static ()) = |_| {};
   |            ^^^^^^^^^^^^^^^
error: aborting due to previous error
Compiler returned: 1

In migrate mode or with AST borrowck the error is much clearer:

error[E0308]: mismatched types
  --> <source>:20:33
   |
20 |     let y: for<'a> fn(&'a ()) = x;
   |                                 ^ one type is more general than the other
   |
   = note: expected type `for<'a> fn(&'a ())`
              found type `fn(&'static ())`
error: aborting due to previous error
For more information about this error, try `rustc --explain E0308`.
Compiler returned: 1

cc @rust-lang/wg-compiler-nll

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

@nikomatsakis nikomatsakis commented Jan 7, 2019

Yeah, I intended to port the newer errors to NLL but didn't do it yet since they are hidden by migration mode. But clearly we need to do that before we can stabilize NLL further.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

@nikomatsakis nikomatsakis commented Jan 7, 2019

Nominating for discussion in the NLL meeting -- this should probably be prioritized.

@nikomatsakis nikomatsakis added P-high and removed I-nominated labels Jan 9, 2019
@nikomatsakis nikomatsakis self-assigned this Jan 9, 2019
@nikomatsakis

This comment has been minimized.

Copy link
Contributor

@nikomatsakis nikomatsakis commented Jan 9, 2019

Discussed in the NLL meeting. Assigning to @lqd but also to me to leave some mentoring notes and/or sync with @lqd

@pnkfelix

This comment has been minimized.

Copy link
Member

@pnkfelix pnkfelix commented Jan 25, 2019

somewhat related bug: #57362

@pnkfelix

This comment has been minimized.

Copy link
Member

@pnkfelix pnkfelix commented Jan 30, 2019

N.B.: This bug continues to persist even after Issue #57362 was resolved by PR #57901

@lqd

This comment has been minimized.

Copy link
Contributor

@lqd lqd commented Feb 27, 2019

With the temporary return of the leak-check from #58592, this issue has expectedly "un-regressed" to diagnostics levels very similar to pre-Universes or AST borrowck:

error[E0308]: mismatched types
 --> src/main.rs:5:33
  |
5 |     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 ())`
@pnkfelix

This comment has been minimized.

Copy link
Member

@pnkfelix pnkfelix commented Feb 28, 2019

As discussed in the NLL meeting last night, one can use -Z no-leak-check to skip the leak check and thus return to the (regressed) behavior and thus attempt to fix it properly.

@lqd

This comment has been minimized.

Copy link
Contributor

@lqd lqd commented Mar 6, 2019

As mentioned on Zulip, I have made some progress here (and have rambling/meandering notes from the exploratory analysis), but will need some guidance to continue, so unassigning myself until then.

@pnkfelix pnkfelix unassigned lqd Mar 6, 2019
@pnkfelix

This comment has been minimized.

Copy link
Member

@pnkfelix pnkfelix commented Mar 28, 2019

triage: downgrading to P-medium.

Blocks: #59490

@pnkfelix pnkfelix added P-medium and removed P-high labels Mar 28, 2019
Aaron1011 added a commit to Aaron1011/rust that referenced this issue Aug 18, 2019
As described in rust-lang#57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outliev the current function.

When NNL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not decleared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is requires to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opoosite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter are more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region, or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
Aaron1011 added a commit to Aaron1011/rust that referenced this issue Aug 18, 2019
As described in rust-lang#57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outlive the current function.

When NLL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not declared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is required to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opposite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to the original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter is more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
Aaron1011 added a commit to Aaron1011/rust that referenced this issue Oct 2, 2019
As described in rust-lang#57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outlive the current function.

When NLL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not declared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is required to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opposite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to the original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter is more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
bors added a commit that referenced this issue Oct 3, 2019
Improve HRTB error span when -Zno-leak-check is used

As described in #57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outlive the current function.

When NLL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not declared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is required to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opposite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to the original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter is more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
Centril added a commit to Centril/rust that referenced this issue Oct 3, 2019
…akis

Improve HRTB error span when -Zno-leak-check is used

As described in rust-lang#57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outlive the current function.

When NLL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not declared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is required to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opposite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to the original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter is more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
choller added a commit to choller/rust that referenced this issue Oct 17, 2019
As described in rust-lang#57374, NLL currently produces unhelpful higher-ranked
trait bound (HRTB) errors when '-Zno-leak-check' is enabled.

This PR tackles one half of this issue - making the error message point
at the proper span. The error message itself is still the very generic
"higher-ranked subtype error", but this can be improved in a follow-up
PR.

The root cause of the bad spans lies in how NLL attempts to compute the
'blamed' region, for which it will retrieve a span for.
Consider the following code, which (correctly) does not compile:

```rust
let my_val: u8 = 25;
let a: &u8 = &my_val;
let b = a;
let c = b;
let d: &'static u8 = c;
```

This will cause NLL to generate the following subtype constraints:

d :< c
c :< b
b <: a

Since normal Rust lifetimes are covariant, this results in the following
region constraints (I'm using 'd to denote the lifetime of 'd',
'c to denote the lifetime of 'c, etc.):

'c: 'd
'b: 'c
'a: 'b

From this, we can derive that 'a: 'd holds, which implies that 'a: 'static
must hold. However, this is not the case, since 'a refers to 'my_val',
which does not outlive the current function.

When NLL attempts to infer regions for this code, it will see that the
region 'a has grown 'too large' - it will be inferred to outlive
'static, despite the fact that is not declared as outliving 'static
We can find the region responsible, 'd, by starting at the *end* of
the 'constraint chain' we generated above. This works because for normal
(non-higher-ranked) lifetimes, we generally build up a 'chain' of
lifetime constraints *away* from the original variable/lifetime.
That is, our original lifetime 'a is required to outlive progressively
more regions. If it ends up living for too long, we can look at the
'end' of this chain to determine the 'most recent' usage that caused
the lifetime to grow too large.

However, this logic does not work correctly when higher-ranked trait
bounds (HRTBs) come into play. This is because HRTBs have
*contravariance* with respect to their bound regions. For example,
this code snippet compiles:

```rust
let a: for<'a> fn(&'a ()) = |_| {};
let b: fn(&'static ()) = a;
```

Here, we require that 'a' is a subtype of 'b'. Because of
contravariance, we end up with the region constraint 'static: 'a,
*not* 'a: 'static

This means that our 'constraint chains' grow in the opposite direction
of 'normal lifetime' constraint chains. As we introduce subtypes, our
lifetime ends up being outlived by other lifetimes, rather than
outliving other lifetimes. Therefore, starting at the end of the
'constraint chain' will cause us to 'blame' a lifetime close to the original
definition of a variable, instead of close to where the bad lifetime
constraint is introduced.

This PR improves how we select the region to blame for 'too large'
universal lifetimes, when bound lifetimes are involved. If the region
we're checking is a 'placeholder' region (e.g. the region 'a' in
for<'a>, or the implicit region in fn(&())), we start traversing the
constraint chain from the beginning, rather than the end.

There are two (maybe more) different ways we generate region constraints for NLL:
requirements generated from trait queries, and requirements generated
from MIR subtype constraints. While the former always use explicit
placeholder regions, the latter is more tricky. In order to implement
contravariance for HRTBs, TypeRelating replaces placeholder regions with
existential regions. This requires us to keep track of whether or not an
existential region was originally a placeholder region. When we look for
a region to blame, we check if our starting region is either a
placeholder region or is an existential region created from a
placeholder region. If so, we start iterating from the beginning of the
constraint chain, rather than the end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.