region inference sometimes fails to recognize implied bound in closure

[nikomatsakis]

Following a bug sample from @jdm, I encountered this bug. The compiler errors out in this code:

struct Parser<'i: 't, 't> {
  data: &'t mut Vec<&'i String>
}

fn callback1<'i, 't, F>(parser: &mut Parser<'i, 't>, f: F)
    where F: for<'tt1> FnMut(&mut Parser<'i, 'tt1>)
{
    panic!()
}

fn callback2<'i, 't, F>(parser: &mut Parser<'i, 't>, mut f: F)
    where F: for<'tt2> FnMut(&mut Parser<'i, 'tt2>)
{
    callback1(parser, |input| {
        f(input)
    });
}

fn main() {
}

specifically it reports a "cannot infer" lifetime error, complaining about how the lifetime 'tt2 in the call f(input) must be some lifetime 'x where 'i: 'x and 'x: 'tt1 (where 'tt1 is the lifetime that appears in the type of input in the closure). The compiler is upset because it does not know that 'i: 'tt1. Those constraints are correct, but in fact the compiler should be able to deduce that 'i: 'tt1 based on the type of input, which is is &mut Parser<'i, 'tt1>. The implied bounds for this type suggest that 'i: 'tt1. But we fail to see it.

The problem is an interaction with inference. When we call callback1() here, we do not specify the lifetime, and so we create a variable 'x -- that is, the actual type of input is &mut Parser<'x, 'tt2>, where 'x is the inference variable. We then recognize that this means 'x: 'tt2, and we add a "given", which is this hacky bit of code in region inference. Then we infer that 'x must be 'i. But when we go to check that 'x: 'tt2, we substitute 'x to 'i, and then report an error, because we never added anything that tells us that 'i: 'tt2. If you specify callback::<'i> manually, it will work fine.

The most straightforward fix is to use the given logic here too. The better fix is to retool this part of region inference to be more robust, which I am in the process of trying to plan out right now for other reasons anyhow.

[nikomatsakis]

Hmm the fix isn't quite as straightforward as I thought. There is some annoying feedback here as well. In particular, in this case, we add a given like '0: 'tt where '0 is an inference variable. Then later we infer '0 to 'i. Then we (separately!) try to verify that 'i: '8 where '8 was inferred to 'tt (and error).

The simplest patch I have come up with thus far is that we could "refresh" the givens with the result of inference and then incorporate those into the free region map. The downside of this is that those new relationships might have affected inference in the first place, since the LUB of (e.g.) 'i and 'tt would then be 'i, and not (e.g.) 'static.

I don't think that there is much we can do about this in the current setup though. It seems best to not worry about this for now until we try to make region inference more general.

[nikomatsakis]

Argh. I just realized that the fix I had planned is probably not going to cut it. The real fix here is probably going to have to wait for a better model of region constraints, one that can carry the inference environment along with it. Which just happens to be what I'm working on in another context, so I guess that's good.

So what I did is to:

• process the givens array after inference is done and add any 'a: 'b relations so implied into the free-regions map

but my fear is that we may be able to synthesize false relations this way, through some sort of setup like:

fn foo<'a, 'b>(...) { // note: a and b have no relation 
    callback(|x| {
        // x: &'a &'b i32, so we get an implied relationship that `'a: 'b`.
        //
        // this ought to be impossible, but maybe the closure is never called.
    })
}

I haven't been able to construct such a scenario yet, but it seems plausible.

[SimonSapin]

Nightly now shows a warning when the work-around of explicitly specifying lifetime parameters in the call is used:

warning: cannot specify lifetime arguments explicitly if late bound lifetime parameters are present
   --> src/rules_and_declarations.rs:458:42
    |
458 |                     parse_nested_block::<'i, 't, _, _, _>(input, move |input| parser.parse_block(prelude, input))
    |                                          ^^
    | 
   ::: src/parser.rs
    |
791 | pub fn parse_nested_block<'i: 't, 't, F, T, E>(parser: &mut Parser<'i, 't>, parse: F)
    |                                                        - the late bound lifetime parameter is introduced here
    |
    = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
    = note: for more information, see issue #42868 <https://github.com/rust-lang/rust/issues/42868>

#42868 (comment) claims that specifying them explicitly does nothing, but that’s not the case here.

[eddyb]

@SimonSapin You can make them early-bound e.g. by writing 'i: 'i in the definition.

[SimonSapin]

@eddyb That doesn’t seem to change anything. The full definition is:

https://github.com/servo/rust-cssparser/blob/v0.19.0/src/parser.rs#L790-L793

pub fn parse_nested_block<'i: 't, 't, F, T, E>(parser: &mut Parser<'i, 't>, parse: F)
                                               -> Result <T, ParseError<'i, E>>
    where F: for<'tt> FnOnce(&mut Parser<'i, 'tt>) -> Result<T, ParseError<'i, E>> {

[eddyb]

Okay I wasn't clear enough: you have to do that for each lifetime. So 'i: 'i, 't: 't.

[arielb1]

I think you could use something like (parse_nested_block: fn(&mut Parser<'i, 't>, _))(...) (using type ascription) instead of passing generic parameters. Ugly, but works.

[steveklabnik]

Triage: this still does not compile