use alloc::collections::{BTreeMap, BTreeSet, VecDeque};
use alloc::vec::Vec;
use super::workspace::{Package, PackageId, Workspace};
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Reach {
pub managed: BTreeMap<PackageId, Vec<PackageId>>,
pub stranded: BTreeSet<PackageId>,
}
#[must_use]
pub fn reach<'a>(
workspace: &Workspace,
changed: impl IntoIterator<Item = &'a PackageId>,
managed: impl Fn(&Package) -> bool,
) -> Reach {
let mut out = Reach::default();
for id in changed {
let Some(package) = workspace.get(id) else {
continue;
};
if managed(package) {
out.managed.insert(id.clone(), Vec::new());
continue;
}
let mut depth = BTreeMap::from([(id.clone(), 0_usize)]);
let mut hits: BTreeMap<PackageId, usize> = BTreeMap::new();
let mut queue = VecDeque::from([id.clone()]);
while let Some(at) = queue.pop_front() {
let next_depth = depth[&at] + 1;
for (dependent, _) in workspace.runtime_dependents(&at) {
let next = dependent.id();
if managed(dependent) {
hits.entry(next.clone()).or_insert(next_depth);
} else if !depth.contains_key(next) {
depth.insert(next.clone(), next_depth);
queue.push_back(next.clone());
}
}
}
if hits.is_empty() {
out.stranded.insert(id.clone());
}
for (hit, length) in hits {
let path = lowest_path(workspace, &hit, length, &depth);
keep_best(&mut out.managed, hit, path);
}
}
out
}
fn lowest_path(
workspace: &Workspace,
hit: &PackageId,
length: usize,
depth: &BTreeMap<PackageId, usize>,
) -> Vec<PackageId> {
let mut path = Vec::with_capacity(length);
let mut at = hit.clone();
for step in (0..length).rev() {
let Some(below) = workspace.get(&at).and_then(|package| {
package
.runtime_dependencies()
.map(|dependency| &dependency.on)
.filter(|on| depth.get(*on) == Some(&step))
.min()
.cloned()
}) else {
break;
};
path.push(below.clone());
at = below;
}
path
}
fn keep_best(
managed: &mut BTreeMap<PackageId, Vec<PackageId>>,
id: PackageId,
path: Vec<PackageId>,
) {
match managed.get(&id) {
Some(held) if (held.len(), held) <= (path.len(), &path) => {}
_ => {
managed.insert(id, path);
}
}
}
#[cfg(test)]
mod tests {
use alloc::vec;
use alloc::vec::Vec;
use semver::Version;
use super::reach;
use crate::plan::workspace::{
DeclaredRange, Dependency, DependencyKind, Ecosystem, Package, PackageId,
ResolvesDependenciesAt, Workspace,
};
use crate::plan::Bounds;
fn id(name: &str) -> PackageId {
PackageId::new(Ecosystem::Cargo, name)
}
fn on(name: &str, kind: DependencyKind) -> Dependency {
Dependency {
on: id(name),
kind,
declared_as: name.into(),
target: None,
range: DeclaredRange::Plain(Bounds::from_cargo_text("^0.1.0").expect("range")),
}
}
fn package(name: &str, dependencies: Vec<Dependency>) -> Package {
Package::new(
id(name),
Version::new(0, 1, 0),
ResolvesDependenciesAt::Install,
true,
dependencies,
)
}
fn workspace(packages: Vec<Package>) -> Workspace {
Workspace::new(packages).expect("workspace")
}
fn managed_set<'a>(names: &'a [&'a str]) -> impl Fn(&Package) -> bool + 'a {
move |package| names.contains(&package.id().name.as_str())
}
#[test]
fn a_normal_or_build_edge_reaches_the_shipping_package() {
for kind in [DependencyKind::Normal, DependencyKind::Build] {
let ws = workspace(vec![
package("app", vec![on("store", kind)]),
package("store", vec![]),
]);
let got = reach(&ws, [&id("store")], managed_set(&["app"]));
assert_eq!(
got.managed.get(&id("app")),
Some(&vec![id("store")]),
"{kind:?}"
);
assert!(got.stranded.is_empty(), "{kind:?}");
}
}
#[test]
fn a_dev_edge_reaches_nothing() {
let ws = workspace(vec![
package("app", vec![on("store", DependencyKind::Development)]),
package("store", vec![]),
]);
let got = reach(&ws, [&id("store")], managed_set(&["app"]));
assert!(got.managed.is_empty());
assert_eq!(got.stranded.into_iter().collect::<Vec<_>>(), [id("store")]);
}
#[test]
fn the_walk_passes_two_unmanaged_packages_and_stops_at_a_managed_one() {
let ws = workspace(vec![
package("cli", vec![on("app", DependencyKind::Normal)]),
package("app", vec![on("core", DependencyKind::Normal)]),
package("core", vec![on("store", DependencyKind::Normal)]),
package("store", vec![]),
]);
let got = reach(&ws, [&id("store")], managed_set(&["app", "cli"]));
assert_eq!(
got.managed.get(&id("app")),
Some(&vec![id("core"), id("store")])
);
assert!(!got.managed.contains_key(&id("cli")), "{got:?}");
}
#[test]
fn a_direct_change_beats_a_path_and_the_shortest_path_wins() {
let ws = workspace(vec![
package(
"app",
vec![
on("a-long", DependencyKind::Normal),
on("b-short", DependencyKind::Normal),
],
),
package("a-long", vec![on("store", DependencyKind::Normal)]),
package("b-short", vec![on("store", DependencyKind::Normal)]),
package("store", vec![]),
]);
let managed = managed_set(&["app"]);
let got = reach(&ws, [&id("store")], &managed);
assert_eq!(
got.managed.get(&id("app")),
Some(&vec![id("a-long"), id("store")]),
"equal lengths fall to the lower name"
);
let got = reach(&ws, [&id("store"), &id("b-short")], &managed);
assert_eq!(
got.managed.get(&id("app")),
Some(&vec![id("b-short")]),
"the shorter path wins"
);
let got = reach(&ws, [&id("store"), &id("app")], &managed);
assert_eq!(got.managed.get(&id("app")), Some(&Vec::new()));
}
#[test]
fn equal_paths_from_one_change_fall_to_the_lowest_name_nearest_first() {
let ws = workspace(vec![
package(
"app",
vec![
on("y", DependencyKind::Normal),
on("z", DependencyKind::Normal),
],
),
package("z", vec![on("a", DependencyKind::Normal)]),
package("y", vec![on("b", DependencyKind::Normal)]),
package("a", vec![on("store", DependencyKind::Normal)]),
package("b", vec![on("store", DependencyKind::Normal)]),
package("store", vec![]),
]);
let got = reach(&ws, [&id("store")], managed_set(&["app"]));
assert_eq!(
got.managed.get(&id("app")),
Some(&vec![id("y"), id("b"), id("store")])
);
}
#[test]
fn equal_paths_from_two_changes_fall_to_the_lowest_name() {
let ws = workspace(vec![
package(
"app",
vec![
on("w", DependencyKind::Normal),
on("z", DependencyKind::Normal),
],
),
package("z", vec![on("x", DependencyKind::Normal)]),
package("w", vec![on("y", DependencyKind::Normal)]),
package("x", vec![]),
package("y", vec![]),
]);
let managed = managed_set(&["app"]);
for changed in [[id("x"), id("y")], [id("y"), id("x")]] {
let got = reach(&ws, &changed, &managed);
assert_eq!(got.managed.get(&id("app")), Some(&vec![id("w"), id("y")]));
}
}
#[test]
fn a_self_edge_ends_the_walk() {
let ws = workspace(vec![
package("app", vec![on("store", DependencyKind::Normal)]),
package("store", vec![on("store", DependencyKind::Development)]),
]);
let got = reach(&ws, [&id("store")], managed_set(&["app"]));
assert_eq!(got.managed.get(&id("app")), Some(&vec![id("store")]));
}
#[test]
fn a_managed_change_is_direct_and_never_stranded() {
let ws = workspace(vec![package("app", vec![])]);
let got = reach(&ws, [&id("app")], managed_set(&["app"]));
assert_eq!(got.managed.get(&id("app")), Some(&Vec::new()));
assert!(got.stranded.is_empty());
}
}