lifetime order breaks member constraints

[aliemjay]

The following code should pass regardless of the declaration order of lifetimes: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=88e227f9f7a5b516bffe21e09b18cd5e

async fn fail<'a, 'b, 'c>(_: &'static str) where 'a: 'c, 'b: 'c, {}
async fn pass<'a, 'c, 'b>(_: &'static str) where 'a: 'c, 'b: 'c, {}

This is related to #63033 but it's different in that we do have a lower bound region, 'c, but we fail to recognize that because the algorithm here, which is responsible for calculating min_choice from choice_regions = ['static, 'a, 'b, 'c], assumes that the outlive relation is a total order, which is not true.

Here is the graph of self.universal_region_relations:

So we need an efficient algorithm that works for partial order relations, but the one that comes to mind is O(n^2). The perf may not be really important here but I'm curious to see the alternatives.

@rustbot label C-bug T-compiler A-borrow-checker E-mentor E-help-wanted

[chenyukang]

@rustbot claim

[aliemjay]

Here is the code of concern

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

Lines 746 to 769 in e07425d

	// Otherwise, we need to find the minimum remaining choice, if
	// any, and take that.
	debug!("choice_regions remaining are {:#?}", choice_regions);
	let min = |r1: ty::RegionVid, r2: ty::RegionVid| -> Option<ty::RegionVid> {
	let r1_outlives_r2 = self.universal_region_relations.outlives(r1, r2);
	let r2_outlives_r1 = self.universal_region_relations.outlives(r2, r1);
	match (r1_outlives_r2, r2_outlives_r1) {
	(true, true) => Some(r1.min(r2)),
	(true, false) => Some(r2),
	(false, true) => Some(r1),
	(false, false) => None,
	}
	};
	let mut min_choice = choice_regions[0];
	for &other_option in &choice_regions[1..] {
	debug!(?min_choice, ?other_option,);
	match min(min_choice, other_option) {
	Some(m) => min_choice = m,
	None => {
	debug!(?min_choice, ?other_option, "incomparable; no min choice",);
	return false;
	}
	}
	}

The code should calculate the min_choice from a set of universal regions (choice_regions). The relations are encoded in self.universal_region_relations and are guaranteed to be transitive and reflexive. The relation graph may have cycles and can be sparse.

The goal here is to find a unique minimum choice that is known to be outlived by all other regions. If none can be found, the function returns false.

Regions that have cycles between them are considered equivalent so we can pick either one of them as a unique choice. e.g. async fn<'a, 'b> f(_: &'static str) where 'a: 'b, 'b: 'a, {}, we can pick either one of ['a, 'b] as a minimum choice.