use super::index::Registry;
use super::{PkgError, PkgResult};
use crate::diagnostics::codes;
use crate::pkg::{parse_version_req, Version, VersionReq};
use std::collections::BTreeMap;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Picked {
pub version: Version,
pub checksum: String,
pub dependencies: BTreeMap<String, String>,
}
pub type Picks = BTreeMap<String, Picked>;
const MAX_ROUNDS: usize = 64;
pub fn resolve(registry: &Registry, root: &BTreeMap<String, String>) -> PkgResult<Picks> {
let mut picks = Picks::new();
for _ in 0..MAX_ROUNDS {
let wanted = gather(root, &picks)?;
let mut next = Picks::new();
for (name, reqs) in &wanted {
next.insert(name.clone(), pick(registry, name, reqs)?);
}
if next == picks {
return Ok(picks);
}
picks = next;
}
Err(PkgError::new(
codes::PKG_UNRESOLVABLE,
format!("resolution did not settle after {} rounds", MAX_ROUNDS),
))
}
type Wanted = BTreeMap<String, Vec<(VersionReq, String)>>;
fn gather(root: &BTreeMap<String, String>, picks: &Picks) -> PkgResult<Wanted> {
let mut wanted = Wanted::new();
for (name, req) in root {
add(&mut wanted, name, req, "the root manifest")?;
}
for (parent, picked) in picks {
let who = format!("{} {}", parent, picked.version);
for (name, req) in &picked.dependencies {
add(&mut wanted, name, req, &who)?;
}
}
Ok(wanted)
}
fn add(wanted: &mut Wanted, name: &str, req: &str, who: &str) -> PkgResult<()> {
let parsed = parse_version_req(req).map_err(|e| {
PkgError::new(
codes::PKG_UNRESOLVABLE,
format!(
"{} asks for {} \"{}\", which is not a version requirement: {}",
who, name, req, e
),
)
})?;
wanted
.entry(name.to_string())
.or_default()
.push((parsed, who.to_string()));
Ok(())
}
fn pick(registry: &Registry, name: &str, reqs: &[(VersionReq, String)]) -> PkgResult<Picked> {
let versions = registry.versions(name);
let asked = reqs
.iter()
.map(|(r, who)| format!("{} {} (from {})", name, r, who))
.collect::<Vec<_>>()
.join("; ");
if versions.is_empty() {
return Err(PkgError::new(
codes::PKG_UNRESOLVABLE,
format!(
"no package named {} in the registry; asked: {}",
name, asked
),
));
}
let best = versions
.iter()
.rev()
.find(|v| !v.is_prerelease() && reqs.iter().all(|(r, _)| r.matches(v)))
.or_else(|| {
versions
.iter()
.rev()
.find(|v| reqs.iter().all(|(r, _)| r.matches(v)))
});
let Some(version) = best else {
let have = versions
.iter()
.map(|v| v.to_string())
.collect::<Vec<_>>()
.join(", ");
return Err(PkgError::new(
codes::PKG_UNRESOLVABLE,
format!(
"no published version of {} meets every requirement; asked: {}; published: {}",
name, asked, have
),
));
};
let entry = registry
.version_entry(name, version)
.expect("a listed version has an entry");
Ok(Picked {
version: version.clone(),
checksum: entry.checksum.clone(),
dependencies: entry.dependencies.clone(),
})
}
pub fn build_order(picks: &Picks) -> Vec<String> {
let mut done: Vec<String> = Vec::new();
let mut left: Vec<String> = picks.keys().cloned().collect();
while !left.is_empty() {
let ready = left.iter().position(|name| {
picks[name]
.dependencies
.keys()
.all(|d| done.contains(d) || !picks.contains_key(d))
});
let i = ready.unwrap_or(0);
done.push(left.remove(i));
}
done
}