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

[Rageking8]

I have absolutely 0 clue how the code works but is this (case 1) supposed to compile: playground

mod case1 {
struct MyTy<'x, 'a, 'b>(std::cell::Cell<(&'x (), &'a u8, &'x &'b u8)>); // Diff here, extra parens
fn wf<T>(_: T) {}
fn test<'a, 'b>() {
|_: &'a u8, x: MyTy<'_, 'a, 'b>| wf(x);
|x: MyTy<'_, 'a, 'b>, _: &'a u8| wf(x);
}}
fn main() {}

Found using a custom DIY Fuzzer. (Only the above compiled successfully for 10k iters)
Just wanted to ensure that if this is unintended, it can be handled.
If the successful compilation is intended, do kindly ignore this comment. Thanks.

[compiler-errors]

@Rageking8 I don't think that the example you produced is related to the issue that @aliemjay is highlighting here, since the changed code no longer requires that 'x is related to 'a in MyTy.

(Also, I don't recommend fuzzing random code in issue reports without understanding how it works first, especially if you're looking for changes in pass/fail conditions, and not just trying to find ICEs, for example)

[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);