-
Notifications
You must be signed in to change notification settings - Fork 2.9k
universal-lock: implement merging of forked resolver states #3360
Copy link
Copy link
Closed
Labels
previewExperimental behaviorExperimental behavior
Description
As part of #3350, when generating a universal lock file, it's possible for the resolver to fork when there are conflicting dependencies. Once all forks have completed, the resolutions from each fork need to be merged into one resolution (which might have multiple versions of the same package). And that in turn needs to get converted to a ResolutionGraph.
In my prototype, this is where resolver states are unioned:
uv/crates/uv-resolver/src/resolver/mod.rs
Lines 1367 to 1484 in 7f2b401
| #[derive(Clone)] | |
| pub(crate) struct ResolverState { | |
| pub(crate) pubgrub: State<UvDependencyProvider>, | |
| pub(crate) next: PubGrubPackage, | |
| pub(crate) pins: FilePins, | |
| pub(crate) priorities: PubGrubPriorities, | |
| pub(crate) added_dependencies: FxHashMap<PubGrubPackage, FxHashSet<Version>>, | |
| pub(crate) markers: FxHashMap<PubGrubPackage, MarkerTree>, | |
| } | |
| impl ResolverState { | |
| fn into_resolution(self) -> Resolution { | |
| let packages = self.pubgrub.partial_solution.extract_solution(); | |
| let mut dependencies = FxHashMap::default(); | |
| for (package, version) in &packages { | |
| for id in &self.pubgrub.incompatibilities[package] { | |
| let pubgrub::solver::Kind::FromDependencyOf( | |
| ref self_package, | |
| ref self_range, | |
| ref dep_package, | |
| ref dep_range, | |
| ) = self.pubgrub.incompatibility_store[*id].kind | |
| else { | |
| continue; | |
| }; | |
| if package != self_package { | |
| continue; | |
| } | |
| let PubGrubPackage::Package { | |
| name: ref self_name, | |
| .. | |
| } = self_package | |
| else { | |
| continue; | |
| }; | |
| let PubGrubPackage::Package { | |
| name: ref dep_name, .. | |
| } = dep_package | |
| else { | |
| continue; | |
| }; | |
| if self_name == dep_name { | |
| continue; | |
| } | |
| if self_range.contains(version) { | |
| let names = ResolutionDependencyNames { | |
| from: self_name.clone(), | |
| to: dep_name.clone(), | |
| }; | |
| let versions = ResolutionDependencyVersions { | |
| from: self_range.clone(), | |
| to: dep_range.clone(), | |
| }; | |
| dependencies | |
| .entry(names) | |
| .or_insert_with(|| vec![]) | |
| .push(versions); | |
| } | |
| } | |
| } | |
| let packages = packages | |
| .into_iter() | |
| .map(|(package, version)| { | |
| let marker = self.markers.get(&package).cloned(); | |
| let map = FxHashMap::from_iter([(version, marker)]); | |
| (package, map) | |
| }) | |
| .collect(); | |
| Resolution { | |
| packages, | |
| dependencies, | |
| pins: self.pins, | |
| } | |
| } | |
| } | |
| #[derive(Debug, Default)] | |
| pub(crate) struct Resolution { | |
| pub(crate) packages: FxHashMap<PubGrubPackage, FxHashMap<Version, Option<MarkerTree>>>, | |
| pub(crate) dependencies: | |
| FxHashMap<ResolutionDependencyNames, Vec<ResolutionDependencyVersions>>, | |
| pub(crate) pins: FilePins, | |
| } | |
| #[derive(Clone, Debug, Eq, Hash, PartialEq)] | |
| pub(crate) struct ResolutionDependencyNames { | |
| pub(crate) from: PackageName, | |
| pub(crate) to: PackageName, | |
| } | |
| #[derive(Clone, Debug, Eq, Hash, PartialEq)] | |
| pub(crate) struct ResolutionDependencyVersions { | |
| pub(crate) from: Range<Version>, | |
| pub(crate) to: Range<Version>, | |
| } | |
| impl Resolution { | |
| fn union(&mut self, other: Resolution) { | |
| for (package, versions) in other.packages { | |
| let entry = self.packages.entry(package); | |
| let mut map: &mut FxHashMap<Version, Option<MarkerTree>> = entry.or_default(); | |
| for (version, marker) in versions { | |
| if !map.contains_key(&version) || map[&version].is_none() { | |
| map.insert(version, marker); | |
| } else { | |
| if let Some(marker) = marker { | |
| map.get_mut(&version).unwrap().as_mut().unwrap().or(marker); | |
| } | |
| } | |
| } | |
| // self.packages.entry(package).or_default().extend(versions); | |
| } | |
| for (names, ranges) in other.dependencies { | |
| self.dependencies.entry(names).or_default().extend(ranges); | |
| } | |
| self.pins.union(other.pins); | |
| } | |
| } |
And the resolution graph constructor takes a merged resolution as input:
uv/crates/uv-resolver/src/resolution.rs
Lines 71 to 78 in 7f2b401
| /// Create a new graph from the resolved `PubGrub` state. | |
| #[allow(clippy::too_many_arguments)] | |
| pub(crate) fn from_state( | |
| index: &InMemoryIndex, | |
| preferences: &Preferences, | |
| editables: Editables, | |
| resolution: Resolution, | |
| ) -> Result<Self, ResolveError> { |
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
previewExperimental behaviorExperimental behavior