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