uv_resolver/resolver/
derivation.rs

1use pubgrub::{Id, Kind, State};
2use rustc_hash::FxHashMap;
3
4use uv_distribution_types::{DerivationChain, DerivationStep};
5use uv_pep440::Version;
6
7use crate::dependency_provider::UvDependencyProvider;
8use crate::pubgrub::PubGrubPackage;
9
10/// Build a [`DerivationChain`] from the pubgrub state, which is available in `uv-resolver`, but not
11/// in `uv-distribution-types`.
12#[derive(Debug, Default, Clone, PartialEq, Eq, Hash)]
13pub struct DerivationChainBuilder;
14
15impl DerivationChainBuilder {
16    /// Compute a [`DerivationChain`] from the current PubGrub state.
17    ///
18    /// This is used to construct a derivation chain upon resolution failure.
19    pub(crate) fn from_state(
20        id: Id<PubGrubPackage>,
21        version: &Version,
22        state: &State<UvDependencyProvider>,
23    ) -> Option<DerivationChain> {
24        /// Find a path from the current package to the root package.
25        fn find_path(
26            id: Id<PubGrubPackage>,
27            version: &Version,
28            state: &State<UvDependencyProvider>,
29            solution: &FxHashMap<Id<PubGrubPackage>, Version>,
30            path: &mut Vec<DerivationStep>,
31        ) -> bool {
32            // Retrieve the incompatibilities for the current package.
33            let Some(incompatibilities) = state.incompatibilities.get(&id) else {
34                return false;
35            };
36            for index in incompatibilities {
37                let incompat = &state.incompatibility_store[*index];
38
39                // Find a dependency from a package to the current package.
40                if let Kind::FromDependencyOf(id1, _, id2, v2) = &incompat.kind {
41                    if id == *id2 && v2.contains(version) {
42                        if let Some(version) = solution.get(id1) {
43                            let p1 = &state.package_store[*id1];
44                            let p2 = &state.package_store[*id2];
45
46                            if p1.name_no_root() == p2.name_no_root() {
47                                // Skip proxied dependencies.
48                                if find_path(*id1, version, state, solution, path) {
49                                    return true;
50                                }
51                            } else if let Some(name) = p1.name_no_root() {
52                                // Add to the current path.
53                                path.push(DerivationStep::new(
54                                    name.clone(),
55                                    p1.extra().cloned(),
56                                    p1.group().cloned(),
57                                    Some(version.clone()),
58                                    v2.clone(),
59                                ));
60
61                                // Recursively search the next package.
62                                if find_path(*id1, version, state, solution, path) {
63                                    return true;
64                                }
65
66                                // Backtrack if the path didn't lead to the root.
67                                path.pop();
68                            } else {
69                                // If we've reached the root, return.
70                                return true;
71                            }
72                        }
73                    }
74                }
75            }
76            false
77        }
78
79        let solution: FxHashMap<_, _> = state.partial_solution.extract_solution().collect();
80        let path = {
81            let mut path = vec![];
82            if !find_path(id, version, state, &solution, &mut path) {
83                return None;
84            }
85            path.reverse();
86            path
87        };
88
89        Some(path.into_iter().collect())
90    }
91}
uv_resolver/resolver/derivation.rs

uv_resolver/resolver/
derivation.rs
