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, Kind, 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 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 {
// Retrieve the incompatibilities for the current package.
let Some(incompatibilities) = state.incompatibilities.get(&id) else {
return false;
};
for index in incompatibilities {
let incompat = &state.incompatibility_store[*index];
// Find a dependency from a package to the current package.
if let Kind::FromDependencyOf(id1, _, id2, v2) = &incompat.kind {
if id == *id2 && v2.contains(version) {
if let Some(version) = solution.get(id1) {
let p1 = &state.package_store[*id1];
let p2 = &state.package_store[*id2];
if p1.name_no_root() == p2.name_no_root() {
// Skip proxied dependencies.
if find_path(*id1, version, state, solution, path) {
return true;
}
} else if let Some(name) = p1.name_no_root() {
// Add to the current path.
path.push(DerivationStep::new(
name.clone(),
p1.extra().cloned(),
p1.group().cloned(),
Some(version.clone()),
v2.clone(),
));
// Recursively search the next package.
if find_path(*id1, 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())
}
}