Implicit and explicit HRTB are not equivalent

[vickenty]

A Fn trait bound with implicit lifetimes is not equivalent to the trait bound with explicit lifetimes.

fn foo<F>(f: F) where F: for<'a> Fn(&'a str) -> &'a str {}
fn bar<F>(f: F) where F: Fn(&str) -> &str {}

fn main() {
    foo(|a: &str| a); // Fails
    bar(|a: &str| a); // Works
}

(playpen: https://is.gd/nKZx1O)

I expected that foo and bar would be equivalent and that both calls would compile (or fail to compile the same way).

instead, calling bar compiles fine, but calling foo results in the following error:

rustc 1.14.0 (e8a012324 2016-12-16)
error[E0312]: lifetime of reference outlives lifetime of borrowed content...
 --> <anon>:6:19
  |
6 |     foo(|a: &str| a); // Fails
  |                   ^
  |
note: ...the reference is valid for the lifetime 'a as defined on the block at 6:18...
 --> <anon>:6:19
  |
6 |     foo(|a: &str| a); // Fails
  |                   ^
note: ...but the borrowed content is only valid for the anonymous lifetime #1 defined on the block at 6:18
 --> <anon>:6:19
  |
6 |     foo(|a: &str| a); // Fails
  |                   ^
help: consider using an explicit lifetime parameter as shown: fn main()
 --> <anon>:5:1
  |
5 | fn main() {
  | ^

error: aborting due to previous error

Somewhat related (but different) problem about a closure with annotated argument was reported in #22557

[JDemler]

I think I ran into the same problem. Alas, for me, it is not possible to use implicit lifetimes:
playpen

struct UsizeRef<'a> {
    a: &'a usize
}

type RefTo = Box<for<'r> Fn(&'r Vec<usize>) -> UsizeRef<'r>>;

//Compiles
fn ref_to<'a>(vec: &'a Vec<usize>) -> UsizeRef<'a> {
    UsizeRef{ a: &vec[0]}
}

fn main() {
    //Does not compile
    let a: RefTo = Box::new(|vec: &Vec<usize>| {
            UsizeRef{ a: &vec[0] }
        }
    );
}

results in:

rustc 1.15.1 (021bd294c 2017-02-08)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> <anon>:15:27
   |
15 |             UsizeRef{ a: &vec[0] }
   |                           ^^^^^^
   |
help: consider using an explicit lifetime parameter as shown: fn main()
  --> <anon>:12:1
   |
12 |   fn main() {
   |  _^ starting here...
13 | |     //Does not compile
14 | |     let a: RefTo = Box::new(|vec: &Vec<usize>| {
15 | |             UsizeRef{ a: &vec[0] }
16 | |         }
17 | |     );
18 | | }
   | |_^ ...ending here

error: aborting due to previous error

[vickenty]

@JDemler This problem only shows up if the closure parameter is typed explicitly. Your example compiles if the type annotation is removed: https://is.gd/e5ILB5

[JDemler]

Aha. Thank you. Didn't know that was possible!

[F001]

I ran into this issue too. The compiler panicked when I was testing @vickenty 's test case.

rustc -V
rustc 1.22.0-nightly (f861b6ee4 2017-09-01)

For the good case, if I declare the closure as a local variable, it also leads to compile error.

fn foo<F>(f: F) where F: for<'a> Fn(&'a str) -> &'a str {}
fn bar<F>(f: F) where F: Fn(&str) -> &str {}

fn main() {
//    foo(|a: &str| a); // Compiler panic
    bar(|a: &str| a); // Works

    let local = |a: &str| a;
    bar(local);  // compile failed
}

[arielb1]

This causes ICE: no representative region on beta.

The code not working with a local would be expected, because of the way higher-ranked inference works.

[nikomatsakis]

In what sense is this a regression? That is, which code specifically works and where...?

[arielb1]

fn foo<F>(f: F) where F: for<'a> Fn(&'a str) -> &'a str {}
fn bar<F>(f: F) where F: Fn(&str) -> &str {}

fn main() {
    foo(|a: &str| a); // Compiler panic
    bar(|a: &str| a); // Works

    let local = |a: &str| a;
    bar(local);  // compile failed
}

Causes an ICE in beta, none in stable.

[nikomatsakis]

triage: P-high

Assigning to myself to investigate.

[Mark-Simulacrum]

@nikomatsakis This is a reminder ping for you to investigate if that hasn't happened yet!

[nikomatsakis]

OK, so I've tracked down the problem. The problem is that astconv produces a kind of "incoherent" signature for the closure by combining the expected return type (which is expressed in terms of some regions) with the explicit annotations that the user gave (which are expressed in terms of some other regions). In the case where for<'a> was used explicitly, those do not match. But in the case where elision was used, it happens to work out.

This has probably always been a bug, but I think that the reason the behavior changed recently was that we removed some of the code in the projection cache that "compensated" for this kind of bad behavior (that code was needed because we were keeping some backwards compat hacks around for a while to give people a chance to update).

Specifically, what happens is this. In the case of for<'a> Fn(&'a str) -> &'a str, the "expected signature" is something like: &'a str as argument and &'a str as return type. The user, on the other hand, wrote &str (an anonymous region). We prefer the thing the user wrote (the anonymous region). But then, since no explicit return type was given, we take the return type from the expected signature: &'a str. The final signature is thus fn(&str) -> &'a str, where both are late-bound. This is actually an illegal signature -- late-bound regions must appear in the parameters of the function, but 'a does not. This makes the projection cache do bad things and ICE.

I'm not sure of how best to fix this. The scenario gets more complex with multiple arguments. Imagine an expected signature of for<'a> fn(&'a u32, &'a u32) -> &'a u32, but the user wrote foo(|x: &str, y| ...). Here are some strategies I can imagine:

• The most conservative thing would be to ignore the expected return type if any arguments had an explicit type provided. Presuming we still use the expected type for other arguments, that would give us fn(&u32, &'a u32) -> _ (we'd infer the return type from the body).
• Ignore the expected type if it contains late-bound regions that don't appear in the inputs. That still kind of permits "weirdness", though... e.g., We would wind up with a signature of fn(&u32, &'a u32) -> &'a u32.
• Another way to go would be to track regions that are invalidated by an explicit type -- that is, that appear in the expected type of an input but are overridden -- in which case we would wind up with a signature like fn(&u32, &'a u32) -> _ again.
• Maybe the best thing would be to make ty_of_arg steal the region from the expected type, so that we wind up with fn(&'a u32, 'a u32) -> &'a u32. That would require some careful coding. It would also alter the current behavior of something like foo(|x: &str, y: &str| ...), but that would probably only make more code compile in practice.

Right now, the signatures that can be manually specified in closures are kind of impoverished anyway: one cannot for example write foo(for<'a> |&'a u32, &'a u32| -> &'a u32 { ... }), though you probably should be able to.

[arielb1]

@nikomatsakis

I'm tempted to just do some sort of LUB of the expected type and the user-specified type. Of course, we can't just replace the regions with normal "outside-universe" _ and merge them because that'll cause an error, but there's maybe something we can do.

The sort of "frankenmerging" bound regions between the expected return type with the user is certainly broken and I'll want none of it.

[nikomatsakis]

@arielb1

I don't think "LUB" precisely makes sense, but it does seem pretty clear that the intent when you write foo(|x: &str| ...) -- and an expected type exists -- is always going to be "use the regions from the expected type". In particular, I think that anonymous regions in closure signatures seem like they want to come from the expected type.

Would it be too hacky to do something like this:

• if there is an expected signature S
• and all the regions in the user-provided signature are late-bound and anonymous
• and no user-provided types include _ (e.g., nothing like |x: Vec<_>|)
• and the expected argument types + user-provided types are unifiable, once the (late-bound, anonymous) regions in the user-provided types are replaced with fresh inference variables

then we would assign the types from the expected signature and ignore the user-provided types. In the example given here, the closure |x: &str| would thus be considered to be for<'a> |x: &'a str| -> &'a str (if that were legal syntax), since that comes from the expected type (and &'_ str is unifiable with &'a str). In terms of my "franken" example where the user provides |x: &str, y|, we would wind up with the signature from the expected type again, because the one argument that the user gave is unifiable.

These sorts of cases would use the signatures that the user gave:

// non-anonymous region appears in `x`, so keep both `x` and `y` just as they wrote it
foo(|x: &'a str, y: &str| ..)

// `_` in the user's signature is just weird, ignore the expected type, which I think we would also do today.
bar(|x: Vec<_>, y| ..)

// signatures not unifiable, just use what they wrote
fn baz<F>(f: F) where F: FnOnce(&str)
baz(|x: &u8| ...)

Actually that seems kind of ok.

[nikomatsakis]

We backported a fix for this to beta. I'm going to adjust the tags to mark as regression only on nightly.

[nikomatsakis]

Believed fixed for good by #45072.