NLL ICE: "unresolved inference variable in outlives"

[nikomatsakis]

The crater run turned up a number of crates encountering an ICE with a message like "unresolved inference variable in outlives" (see list in #52054). I'm not sure what is the problem yet but I'm filing this bug to track the issue.

A good representative is combine-language-2.0.0-beta4, which failed with this log.

[matthewjasper]

Self contained example. Related to #51649?

// Delayed ICE:
// error: internal compiler error: unresolved inference variable in outlives: _#0t
#![feature(nll)]

pub trait Parser {
    type Input;

    #[inline(always)]
    fn parse_first(input: &mut Self::Input);
}

impl<'a, I, P: ?Sized> Parser for &'a mut P
where
    P: Parser<Input = I>,
{
    type Input = I;

    fn parse_first(_: &mut Self::Input) {}
}

fn main() {}

[pnkfelix]

triage re-assigning to self

[nikomatsakis]

I think this may have been fixed by #51959. At least @matthewjasper's example no longer reproduces. I'll have to try the original crate.

[nikomatsakis]

OK wait. @matthewjasper's example now fails to build, whereas it builds without nll. It no longer ICEs though.

[nikomatsakis]

Ah, I see the problem. It arises because we don't normalize types before computing the implied bounds in the universal regions code:

rust/src/librustc_mir/borrow_check/nll/universal_regions.rs

Lines 502 to 506 in fefe816

	// Add the implied bounds from inputs and outputs.
	for ty in inputs_and_output {
	debug!("build: input_or_output={:?}", ty);
	self.add_implied_bounds(&indices, ty);
	}

even though we just "liberated" late-bound regions:

rust/src/librustc_mir/borrow_check/nll/universal_regions.rs

Lines 487 to 492 in fefe816

	let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars(
	FR,
	self.mir_def_id,
	&bound_inputs_and_output,
	&mut indices,
	);

[nikomatsakis]

It's a bit tricky -- we don't just want to insert a random call to normalize until we've finished generating all the "free regions". That call could produce outlives obligations we have to propagate to the right place. It's not that big a deal, in fact at this point we have generated all the free regions:

rust/src/librustc_mir/borrow_check/nll/universal_regions.rs

Line 494 in fefe816

let num_universals = self.infcx.num_region_vars();

but we still need to route the resulting outlives obligations to the right place. This will take a touch of reorganization in the code.

[nikomatsakis]

I'm working on this. It's non-trivial.

[nikomatsakis]

But I'm getting there =)