universal-lock: implement resolver forking

[BurntSushi]

This is blocked on #3354 and #3355. It's part of the larger task of #3350.

Implementing forking requires detecting when there are multiple direct dependencies leading to different versions of the same package. In effect, instead of getting just a single list of dependencies, as we do here:

uv/crates/uv-resolver/src/resolver/mod.rs

Lines 794 to 800 in e33ff95

	async fn get_dependencies(
	&self,
	package: &PubGrubPackage,
	version: &Version,
	priorities: &mut PubGrubPriorities,
	request_sink: &tokio::sync::mpsc::Sender<Request>,
	) -> Result<Dependencies, ResolveError> {

We will get a list of lists of dependencies. This can be seen in my prototype:

uv/crates/uv-resolver/src/resolver/mod.rs

Lines 835 to 894 in 7f2b401

	/// Given a candidate package and version, return its dependencies.
	#[instrument(skip_all, fields(%package, %version))]
	async fn get_dependencies_forking(
	&self,
	package: &PubGrubPackage,
	version: &Version,
	priorities: &mut PubGrubPriorities,
	request_sink: &tokio::sync::mpsc::Sender<Request>,
	) -> Result<Vec<Dependencies>, ResolveError> {
	type Dep = (PubGrubPackage, Range<Version>, Option<MarkerTree>);
	let deps: Vec<Dep> = match self
	.get_dependencies(package, version, priorities, request_sink)
	.await?
	{
	Dependencies::Available(deps) => deps,
	Dependencies::Unavailable(err) => return Ok(vec![Dependencies::Unavailable(err)]),
	};
	// let mut by_grouping: FxHashMap<(&PackageName, &Option<ExtraName>, bool), Vec<&Dep>> =
	// FxHashMap::default();
	// let mut by_grouping: FxHashMap<&PackageName, Vec<&Dep>> = FxHashMap::default();
	// This assumes that the version ranges are non-overlapping. When we do this for real,
	// I believe it is true that we do NOT want to fork when there are overlapping version
	// ranges.
	let mut by_grouping: FxHashMap<&PackageName, FxHashMap<&Range<Version>, Vec<&Dep>>> =
	FxHashMap::default();
	for dep in deps.iter() {
	let (ref pkg, ref range, _) = *dep;
	let name = match *pkg {
	PubGrubPackage::Root(_) | PubGrubPackage::Python(_) => unreachable!(),
	PubGrubPackage::Package { ref name, .. } => name,
	};
	by_grouping
	.entry(name)
	.or_insert(FxHashMap::default())
	.entry(range)
	.or_insert(vec![])
	.push(dep);
	}
	let mut forks: Vec<Vec<Dep>> = vec![vec![]];
	for (_, mut groups) in by_grouping {
	if groups.len() <= 1 {
	for deps in groups.into_values() {
	for fork in forks.iter_mut() {
	fork.extend(deps.iter().map(|dep| (*dep).clone()));
	}
	}
	} else {
	let mut new_forks: Vec<Vec<Dep>> = vec![];
	for deps in groups.into_values() {
	let mut new_forks_for_group = forks.clone();
	for fork in new_forks_for_group.iter_mut() {
	fork.extend(deps.iter().map(|dep| (*dep).clone()));
	}
	new_forks.extend(new_forks_for_group);
	}
	forks = new_forks;
	}
	}
	Ok(forks.into_iter().map(Dependencies::Available).collect())
	}

We should be careful to ensure that we only fork when the conflicting packages have non-overlapping versions and non-overlapping marker expressions.