overly restrictive closure borrow-checking

[aliemjay]

Both of these test cases should pass borrowck: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2015&gist=50a263a9626cb0b08f5cee334df8a852

mod case1 {
    struct MyTy<'x, 'a, 'b>(std::cell::Cell<(&'x &'a u8, &'x &'b u8)>);
    fn wf<T>(_: T) {}
    fn test<'a, 'b>() {
        |_: &'a u8, x: MyTy<'_, 'a, 'b>| wf(x); // FAIL!
        |x: MyTy<'_, 'a, 'b>, _: &'a u8| wf(x); // PASS!!!
    }
}

mod case2 {
    struct MyTy<'a, 'b, 'x>(std::cell::Cell<(&'a &'x u8, &'b &'x u8)>);
    fn wf<T>(_: T) {}
    fn test<'a, 'b>() {
        |x: MyTy<'a, 'b, '_>| wf(x); // FAIL!
    }
}

They both fail because of the unnecessarily restrictive algorithm in try_propagate_universal_region_error:

• case1 fails because '_ has multiple "non-local upper bounds" ['a, 'b] and we do propagate the error to both of them while choosing a single one would be sufficient.
• case2 fails because '_ has multiple "non-local lower bounds" ['a, 'b] and the call to non_lcal_lower_bound simply returns None in this case!
• The different behavior in case1 when swapping arguments is due to the shortcut in

  rust/compiler/rustc_borrowck/src/region_infer/mod.rs

  Line 1560 in 79146ba

  if representative != longer_fr {

  which is sensitive to region numbering, but I think that's irrelevant here.

@rustbot label C-bug T-types A-NLL NLL-complete A-borrow-checker
@rustbot claim

[lcnr]

This issue also affects type tests (and i expect to this error even if region outlives were fixed)

fn reg_outlives<'a, 'b: 'a>() {}
fn type_outlives<'a, T: 'a>() {}

struct Constrain<'a: 'c, 'b: 'c, 'c: 'a>(*mut (&'a (), &'b (), &'c ()));

impl<'a, 'b, 'c> Constrain<'a, 'b, 'c> {
    fn req(&self)
    where
        'c: 'a,
    {
    }
}

fn promote_type_test<'a, 'b: 'a, T>(x: &'a T) {
    |x: Constrain<'a, 'b, '_>| {
        x.req(); // 'c: 'a
        type_outlives::<'a, T>(); // we've got `T: 'a`
    };
}

rust/compiler/rustc_borrowck/src/region_infer/mod.rs

Lines 1012 to 1016 in 2776bdf

	// For each region outlived by lower_bound find a non-local,
	// universal region (it may be the same region) and add it to
	// `ClosureOutlivesRequirement`.
	let mut found_outlived_universal_region = false;
	for ur in self.scc_values.universal_regions_outlived_by(r_scc) {

There's no reason to look at all lower bounds of our region in case that region is already external.

[aliemjay]

@lcnr Your issue can be reproduced and fixed independently using this alternative example:

#![feature(closure_lifetime_binder)]

fn type_outlives<'a, T: 'a>() {}

struct Constrain<'a: 'c, 'b: 'c, 'c: 'a>(*mut (&'a (), &'b (), &'c ()));

fn promote_type_test<'a, 'b, T>(_: &'a T) {
    for<'x> |_: Constrain<'a, 'b, 'x>| -> () {
        type_outlives::<'x, T>(); //~ `T` may not live long enough
        // unnecessarily requires T: 'b
    };
}

There's no reason to look at all lower bounds of our region in case that region is already external.

I think the way to fix it is a bit more subtle. Consider the example above where 'x is not external. The real problem is that non_local_upper_bounds('x) incorrectly returns ['a, 'b] when it should return ['a] only.

rust/compiler/rustc_borrowck/src/region_infer/mod.rs

Line 1019 in 2776bdf

let non_local_ub = self.universal_region_relations.non_local_upper_bounds(ur);