[nll] `gluon_base` does not compile with NLL

[nikomatsakis]

I reduced a crater run failure of gluon_base v0.8.0 to this standalone snippet:

#![feature(nll)]

use std::ops::Deref;

pub struct TypeFieldIterator<'a, T: 'a> {
    typ: &'a T,
    current: usize,
}

pub enum Type<Id, T> {
    Unit,

    Record(T),
    
    ExtendRow {
        types: Vec<(Id, T)>,
        rest: T,
    },
}

impl<'a, Id: 'a, T> Iterator for TypeFieldIterator<'a, T>
where
    T: Deref<Target = Type<Id, T>>,
{
    type Item = &'a (Id, T);
    
    fn next(&mut self) -> Option<&'a (Id, T)> {
        match **self.typ {
            Type::Unit => None,

            Type::Record(ref row) => {
                self.typ = row;
                self.next()
            }
            
            Type::ExtendRow { ref types, ref rest } => {
                let current = self.current;
                self.current += 1;
                types.get(current).or_else(|| {
                    self.current = 0;
                    self.typ = rest;
                    self.next()
                })
            }            
        }
    }
}

fn main() { }

this compiles without NLL; with NLL it fails with:

error[E0310]: the parameter type `Id` may not live long enough
  --> src/main.rs:39:44
   |
39 |                   types.get(current).or_else(|| {
   |  ____________________________________________^
40 | |                     self.current = 0;
41 | |                     self.typ = rest;
42 | |                     self.next()
43 | |                 })
   | |_________________^
   |
   = help: consider adding an explicit lifetime bound `Id: 'static`...

I think this is some kind of failure from the "closure checking" code.

[nikomatsakis]

OK, the problem here has to do with the "closure region requirements" logic. If look at the closure region requirements from the closure here, we see:

   = note: defining type: DefId(0/1:24 ~ issue_53119[8787]::{{impl}}[0]::next[0]::{{closure}}[0]) with closure substs [
               '_#1r,
               Id,
               T,
               i32,
               extern "rust-call" fn(()) -> std::option::Option<&'_#2r (Id, T)>,
               &'_#3r mut &'_#4r mut TypeFieldIterator<'_#5r, T>,
               &'_#6r &'_#7r T
           ]
   = note: number of external vids: 8
   = note: where Id: '_#0r
   = note: where Id: '_#0r
   = note: where Id: '_#0r
   = note: where '_#5r: '_#2r
   = note: where '_#7r: '_#2r

Note that where Id: '_#0r requirements -- those are saying to the creator of the closure that Id must outlive 'static (which is always '_#0r). This leads to the error message you see above.

But why are we requiring that? What the closure actually has to prove is something more complicated. It knows that Id outlives '_#1r, '_#2r, and '_#8r, and it has to prove that Id outlives '_#24r = {... '_#2r, '_#5r}. This causes a problem because we don't know that '_#1r: '_#5r. So we try to find some single region to approximate '_#2r and '_#5r:

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Lines 670 to 679 in cf84056

	// Find some bounding subject-region R+ that is a super-region
	// of the existing subject-region R. This should be a non-local, universal
	// region, which ensures it can be encoded in a `ClosureOutlivesRequirement`.
	let lower_bound_plus = self.non_local_universal_upper_bound(*lower_bound);
	assert!(self.universal_regions.is_universal_region(lower_bound_plus));
	assert!(
	!self
	.universal_regions
	.is_local_free_region(lower_bound_plus)
	);

and we find up with 'static.

Now, the problem here is that we've introduced a lot more regions than originally existed. In fact, the closure's '_#5r will actually be equal to '_#1r in the creator. (You can see from the comment above that both represent 'a, but appearing in different places.)

I've always assumed we'll have to get smarter at some point in this logic but perhaps the time has come. =)

The easiest fix, I suspect, is to try to filter out just to the parts that are not satisfied. In particular, we basically want to prove that Id: ('_#2r|'_#5r). We ourselves can see that Id: '_#2r, so if we filter that out, we are left just with Id: '_#5r. That should work fine.

[nikomatsakis]

Ugh. That's kind of a pain. Won't get to it today, anyway.

[nikomatsakis]

Having thought about this some I think I was pursuing a fix that would be too hard. Currently, our logic is something like this:

We are trying to prove that T: 'X. We tried to do that locally using the information at our disposal about the bounds of T, but we failed. So we push it to the closure creator to prove.

In order to do that, we first check that the type T contains only regions that the creator knows about. This is clearly true here, so we can ignore that, but as a consequence, we do know that all regions in the type T are free regions that outlive the closure body.

Then we try to "promote" 'X to some region that is "external" to the closure. This is where our problem arises, as right now the region 'X is the union of three things:

• some parts of the closure body
• the free lifetime '1
• the free lifetime '5

and we don't know a good common upper bound for '1 and '5. Hence we promote to 'static ('0).

What we should do instead, I think, is to create two bounds for our creator: T: '1 and T: '5. As it happens, our creator knows that '1 and '5 are the same region anyhow ('a).

Note that we can ignore the details from closure body because we know that T contains all free regions.

[nikomatsakis]

cc @mikhail-m1 -- think you'd be able to take this issue on?

[nikomatsakis]

Here is a guide to the code in question. The following function has the job of "promoting" a failed type test, so that it becomes the creator's obligation to check it:

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Lines 648 to 654 in 18925de

	fn try_promote_type_test<'gcx>(
	&self,
	infcx: &InferCtxt<'_, 'gcx, 'tcx>,
	mir: &Mir<'tcx>,
	type_test: &TypeTest<'tcx>,
	propagated_outlives_requirements: &mut Vec<ClosureOutlivesRequirement<'gcx>>,
	) -> bool {

We begin by promoting the "subject" of the type-test (in this case, the type Id):

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Lines 665 to 668 in 18925de

	let subject = match self.try_promote_type_test_subject(infcx, generic_ty) {
	Some(s) => s,
	None => return false,
	};

Then we compute a "non-local" version of the region 'X (this is where we wind up computing 'static incorrectly):

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Line 673 in 18925de

let lower_bound_plus = self.non_local_universal_upper_bound(*lower_bound);

We then push the type-test into the caller's requirements:

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Lines 681 to 685 in 18925de

	propagated_outlives_requirements.push(ClosureOutlivesRequirement {
	subject,
	outlived_free_region: lower_bound_plus,
	blame_span: locations.span(mir),
	});

Basically what we want to do is to modify that line to instead do something like this:

for each free region `r` in `lower_bound` {
    let r = self.non_local_universal_upper_bound(r); // typically but not always a no-op
    propagated_outlives_requirements.push(ClosureOutlivesRequirement {
        subject,
        outlived_free_region: r,
        blame_span: locations.span(mir),
    });
}

[lovesegfault]

Actually, @nikomatsakis, is there any chance I could give this a try? I've been wanting to start helping out on compiler work for a while, and I like this issue!

Assuming you'd have time to lend a hand I'd love to take it!

[mikhail-m1]

@bemeurer sorry, I am already working on it, I think you get ask for a task at https://rust-lang.zulipchat.com, all NLL discussions are there

[lovesegfault]

@mikhail-m1 No problem! Thank you!

[nikomatsakis]

@bemeurer I just posted an update that includes some links, but please reach out to me on Zulip if you like and we can discuss as well. =)