-
Notifications
You must be signed in to change notification settings - Fork 2.9k
universal-lock: implement resolver forking #3358
Copy link
Copy link
Closed
Labels
previewExperimental behaviorExperimental behavior
Description
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.
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
previewExperimental behaviorExperimental behavior