crates/nornir-release-core/src/version_solve.rs
//! # `version_solve` — a PubGrub-style interval CSP version solver
//!
//! The release doctor already checks each *individual* version requirement against
//! the versions that will be AVAILABLE for a dependency ([`graph_precheck`]). This
//! module adds the missing *constraint-satisfaction* angle: when SEVERAL consumers
//! each pin the same dependency, are their requirement RANGES mutually satisfiable at
//! all — and is there a single coherent assignment of a version to every crate in the
//! publish set that honours every edge simultaneously?
//!
//! That is exactly the problem [PubGrub] solves. The `pubgrub` crate is not vendored
//! in this (offline, SSH-only) constellation, so this is a **minimal, pure interval
//! solver** built on the `semver` leaf we already link under the `release` feature:
//!
//! * [`Interval`] — a convex half-open version range with inclusive/exclusive
//! endpoints and ±∞ open sides. Every `semver` `VersionReq` (an AND of comparators)
//! maps to exactly ONE interval, so intersection is just endpoint arithmetic.
//! * [`check_crate_constraints`] — the crate-level CSP the doctor calls: group every
//! consumer requirement by dependency, intersect the ranges, and flag the two
//! distinct failure modes — a **provably empty** range intersection (unsatisfiable
//! no matter WHAT is published) and **no available version** in a non-empty
//! intersection (unsatisfiable given what WILL ship).
//! * [`solve`] — the general PubGrub-flavoured backtracking solver over a package
//! [`Universe`]: pick a version highest-first, propagate the dependencies it
//! induces, backtrack on conflict, and return either a full assignment or the crate
//! whose accumulated requirements could not be met.
//!
//! Pure (no I/O, no warehouse, no `nornir` dep); deterministic (BTree/Version order).
//!
//! [PubGrub]: https://nex3.medium.com/pubgrub-2fb6470504f
//! [`graph_precheck`]: crate::graph_precheck
use semver::{Comparator, Op, Version, VersionReq};
use std::collections::{BTreeMap, BTreeSet};
use std::fmt;
// ─────────────────────────────── intervals ───────────────────────────────
/// One endpoint of an [`Interval`]: a version plus whether the bound is inclusive.
#[derive(Clone, Debug, PartialEq, Eq)]
struct Endpoint {
version: Version,
inclusive: bool,
}
/// A convex version range `[lo, hi]` / `(lo, hi)` (mixed inclusivity), with `None`
/// standing for an open ±∞ side. Every `semver::VersionReq` reduces to exactly one of
/// these, so intersection is closed under `VersionReq`. `pre`-release identifiers are
/// intentionally dropped from the bounds (release-set crates ship release versions);
/// the solver's concrete membership test defers to `VersionReq::matches`, which keeps
/// prerelease semantics authoritative where it matters.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Interval {
lower: Option<Endpoint>,
upper: Option<Endpoint>,
}
fn ver(major: u64, minor: u64, patch: u64) -> Version {
Version::new(major, minor, patch)
}
impl Interval {
/// The whole version line, `(-∞, +∞)`.
pub fn full() -> Self {
Interval { lower: None, upper: None }
}
/// The empty set — no version satisfies it.
pub fn empty() -> Self {
// A canonical contradiction: `[1.0.0, 1.0.0)`.
Interval {
lower: Some(Endpoint { version: ver(1, 0, 0), inclusive: true }),
upper: Some(Endpoint { version: ver(1, 0, 0), inclusive: false }),
}
}
/// `true` when the range contains no version at all.
pub fn is_empty(&self) -> bool {
match (&self.lower, &self.upper) {
(Some(lo), Some(hi)) => {
if lo.version > hi.version {
true
} else if lo.version == hi.version {
// A single point survives only when BOTH ends include it.
!(lo.inclusive && hi.inclusive)
} else {
false
}
}
_ => false,
}
}
/// Does `v` lie inside this interval (by the bounds alone)?
pub fn contains(&self, v: &Version) -> bool {
let lower_ok = match &self.lower {
None => true,
Some(lo) => {
if lo.inclusive {
*v >= lo.version
} else {
*v > lo.version
}
}
};
let upper_ok = match &self.upper {
None => true,
Some(hi) => {
if hi.inclusive {
*v <= hi.version
} else {
*v < hi.version
}
}
};
lower_ok && upper_ok
}
/// The intersection of two intervals — still one interval (ranges are convex).
pub fn intersect(&self, other: &Interval) -> Interval {
let lower = max_lower(self.lower.as_ref(), other.lower.as_ref());
let upper = min_upper(self.upper.as_ref(), other.upper.as_ref());
Interval { lower, upper }
}
/// The interval an entire `VersionReq` (AND of comparators) resolves to.
pub fn from_req(req: &VersionReq) -> Interval {
// `*` / an empty comparator list matches everything.
req.comparators
.iter()
.map(Interval::from_comparator)
.fold(Interval::full(), |acc, iv| acc.intersect(&iv))
}
/// The interval a single comparator resolves to, following cargo's caret/tilde/
/// wildcard expansion rules.
fn from_comparator(c: &Comparator) -> Interval {
let minor = c.minor;
let patch = c.patch;
let major = c.major;
let inc = |version: Version| Some(Endpoint { version, inclusive: true });
let exc = |version: Version| Some(Endpoint { version, inclusive: false });
let lower_all = inc(ver(major, minor.unwrap_or(0), patch.unwrap_or(0)));
match c.op {
Op::Exact | Op::Wildcard => {
// =/no-part behaves as a range over the UNSPECIFIED tail.
let (lower, upper) = match (minor, patch) {
(None, _) => (ver(major, 0, 0), ver(major + 1, 0, 0)),
(Some(mi), None) => (ver(major, mi, 0), ver(major, mi + 1, 0)),
(Some(mi), Some(pa)) => (ver(major, mi, pa), ver(major, mi, pa + 1)),
};
Interval { lower: inc(lower), upper: exc(upper) }
}
Op::Greater => {
// `>1.2` ⇒ `>=1.3.0`; `>1` ⇒ `>=2.0.0`; `>1.2.3` ⇒ strictly above.
let lower = match (minor, patch) {
(None, _) => inc(ver(major + 1, 0, 0)),
(Some(mi), None) => inc(ver(major, mi + 1, 0)),
(Some(mi), Some(pa)) => exc(ver(major, mi, pa)),
};
Interval { lower, upper: None }
}
Op::GreaterEq => Interval { lower: lower_all, upper: None },
Op::Less => {
let upper = match (minor, patch) {
(None, _) => exc(ver(major, 0, 0)),
(Some(mi), None) => exc(ver(major, mi, 0)),
(Some(mi), Some(pa)) => exc(ver(major, mi, pa)),
};
Interval { lower: None, upper }
}
Op::LessEq => {
// `<=1.2` ⇒ `<1.3.0`; `<=1` ⇒ `<2.0.0`; `<=1.2.3` inclusive.
let upper = match (minor, patch) {
(None, _) => exc(ver(major + 1, 0, 0)),
(Some(mi), None) => exc(ver(major, mi + 1, 0)),
(Some(mi), Some(pa)) => inc(ver(major, mi, pa)),
};
Interval { lower: None, upper }
}
Op::Tilde => {
// `~1.2.3`/`~1.2` ⇒ `<1.3.0`; `~1` ⇒ `<2.0.0`.
let upper = match (minor, patch) {
(None, _) => ver(major + 1, 0, 0),
(Some(mi), _) => ver(major, mi + 1, 0),
};
Interval { lower: lower_all, upper: exc(upper) }
}
Op::Caret => {
let upper = caret_upper(major, minor, patch);
Interval { lower: lower_all, upper: exc(upper) }
}
// `semver::Op` is `#[non_exhaustive]`; be conservative for any future op.
_ => Interval::full(),
}
}
}
/// Cargo's caret upper bound: increment the left-most NON-ZERO component.
fn caret_upper(major: u64, minor: Option<u64>, patch: Option<u64>) -> Version {
if major != 0 {
return ver(major + 1, 0, 0);
}
match minor {
None => ver(1, 0, 0), // ^0 ⇒ <1.0.0
Some(mi) if mi != 0 => ver(0, mi + 1, 0), // ^0.2.x ⇒ <0.3.0
Some(_) => match patch {
None => ver(0, 1, 0), // ^0.0 ⇒ <0.1.0
Some(pa) => ver(0, 0, pa + 1), // ^0.0.3 ⇒ <0.0.4
},
}
}
/// Pick the TIGHTER (greater) of two lower bounds.
fn max_lower(a: Option<&Endpoint>, b: Option<&Endpoint>) -> Option<Endpoint> {
match (a, b) {
(None, x) | (x, None) => x.cloned(),
(Some(x), Some(y)) => {
if x.version != y.version {
Some(if x.version > y.version { x.clone() } else { y.clone() })
} else {
// Same version: exclusive is the tighter lower bound.
Some(Endpoint {
version: x.version.clone(),
inclusive: x.inclusive && y.inclusive,
})
}
}
}
}
/// Pick the TIGHTER (lesser) of two upper bounds.
fn min_upper(a: Option<&Endpoint>, b: Option<&Endpoint>) -> Option<Endpoint> {
match (a, b) {
(None, x) | (x, None) => x.cloned(),
(Some(x), Some(y)) => {
if x.version != y.version {
Some(if x.version < y.version { x.clone() } else { y.clone() })
} else {
// Same version: exclusive is the tighter upper bound.
Some(Endpoint {
version: x.version.clone(),
inclusive: x.inclusive && y.inclusive,
})
}
}
}
}
impl fmt::Display for Interval {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_empty() {
return write!(f, "∅");
}
match &self.lower {
None => write!(f, "(-∞")?,
Some(lo) => write!(f, "{}{}", if lo.inclusive { '[' } else { '(' }, lo.version)?,
}
write!(f, ", ")?;
match &self.upper {
None => write!(f, "+∞)"),
Some(hi) => write!(f, "{}{}", hi.version, if hi.inclusive { ']' } else { ')' }),
}
}
}
// ─────────────────────────── crate-level CSP ───────────────────────────
/// One version requirement a `consumer` crate declares on a `dep` crate.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CrateConstraint {
pub consumer: String,
pub dep: String,
/// The raw `semver` requirement string, e.g. `"^1.2"`, `"=0.3.1"`.
pub raw_req: String,
}
/// Why a dependency's set of requirements cannot be satisfied.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ConflictKind {
/// The requirement ranges have an EMPTY intersection — unsatisfiable no matter
/// which version is published (e.g. `^1` from one consumer, `^2` from another).
EmptyIntersection,
/// The ranges DO intersect, but no version that will be AVAILABLE for the dep
/// falls inside the intersection.
NoAvailableMatch,
}
/// A single unsatisfiable dependency, with the consumers and requirements at fault.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct VersionConflict {
pub dep: String,
pub kind: ConflictKind,
pub consumers: Vec<String>,
pub requirements: Vec<String>,
pub detail: String,
}
/// The crate-level constraint check the release doctor calls: group every consumer
/// requirement by its dependency, intersect the ranges, and report each dependency
/// whose requirements cannot be jointly satisfied.
///
/// `available` maps a dependency crate to the versions that WILL exist for it (the
/// about-to-publish version, the crates.io max, a local checkout). A dependency with
/// no entry is left to cargo/registry resolution (never a false block) — only the
/// interval intersection is checked for it. Deterministic in dependency name order.
pub fn check_crate_constraints(
constraints: &[CrateConstraint],
available: &BTreeMap<String, Vec<Version>>,
) -> Vec<VersionConflict> {
// dep → (interval intersection, raw reqs, consumers)
let mut grouped: BTreeMap<String, (Interval, Vec<String>, BTreeSet<String>)> = BTreeMap::new();
for c in constraints {
let Ok(req) = VersionReq::parse(&c.raw_req) else {
continue; // unparsable ⇒ leave to cargo (never a false block).
};
let iv = Interval::from_req(&req);
let entry = grouped
.entry(c.dep.clone())
.or_insert_with(|| (Interval::full(), Vec::new(), BTreeSet::new()));
entry.0 = entry.0.intersect(&iv);
if !entry.1.contains(&c.raw_req) {
entry.1.push(c.raw_req.clone());
}
entry.2.insert(c.consumer.clone());
}
let mut conflicts = Vec::new();
for (dep, (interval, reqs, consumers)) in grouped {
let consumers: Vec<String> = consumers.into_iter().collect();
if interval.is_empty() {
conflicts.push(VersionConflict {
detail: format!(
"requirements on `{dep}` are mutually exclusive: {} intersect to ∅",
reqs.join(" ∧ "),
),
dep,
kind: ConflictKind::EmptyIntersection,
consumers,
requirements: reqs,
});
continue;
}
// Non-empty range: if we know what will be available, at least one version
// must land inside the intersection (checked authoritatively via `matches`).
if let Some(versions) = available.get(&dep) {
let parsed_reqs: Vec<VersionReq> =
reqs.iter().filter_map(|r| VersionReq::parse(r).ok()).collect();
let any_ok = versions
.iter()
.any(|v| parsed_reqs.iter().all(|r| r.matches(v)));
if !any_ok {
let have: Vec<String> = versions.iter().map(|v| v.to_string()).collect();
conflicts.push(VersionConflict {
detail: format!(
"no available version of `{dep}` ({}) satisfies {} (feasible range {interval})",
have.join(", "),
reqs.join(" ∧ "),
),
dep,
kind: ConflictKind::NoAvailableMatch,
consumers,
requirements: reqs,
});
}
}
}
conflicts
}
/// Build [`CrateConstraint`]s from the release doctor's cross-repo [`RepoGraph`] facts
/// (`crate_dep_reqs`: consumer → dep → requirement strings). Wires the interval CSP to
/// the exact per-consumer requirements the doctor already gathers.
///
/// [`RepoGraph`]: crate::model::RepoGraph
pub fn constraints_from_graphs(
graphs: &[crate::model::RepoGraph],
) -> Vec<CrateConstraint> {
let mut out = Vec::new();
for g in graphs {
for (consumer, deps) in &g.crate_dep_reqs {
for (dep, reqs) in deps {
for raw in reqs {
out.push(CrateConstraint {
consumer: consumer.clone(),
dep: dep.clone(),
raw_req: raw.clone(),
});
}
}
}
}
out
}
// ─────────────────────── general backtracking solver ───────────────────────
/// The package universe the [`solve`] search reasons over.
#[derive(Clone, Debug, Default)]
pub struct Universe {
/// package → the versions that exist for it (any order; the solver tries highest
/// first).
pub available: BTreeMap<String, Vec<Version>>,
/// `(package, version)` → the dependency requirements that version induces.
pub deps: BTreeMap<(String, Version), Vec<(String, VersionReq)>>,
}
/// The crate whose accumulated requirements the solver could not satisfy.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SolveConflict {
pub package: String,
/// The requirements active on `package` when the search dead-ended.
pub requirements: Vec<String>,
pub detail: String,
}
/// Outcome of a full [`solve`]: a coherent version per package, or the blocking crate.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SolveResult {
Solved(BTreeMap<String, Version>),
Conflict(SolveConflict),
}
/// A PubGrub-flavoured backtracking version solver: assign a version to every package
/// reachable from `roots` such that every requirement (root + transitively induced) is
/// honoured. Tries the highest satisfying version first and backtracks on conflict.
/// Returns the first crate whose requirements cannot be met when the whole search
/// space is exhausted.
pub fn solve(roots: &[(String, VersionReq)], universe: &Universe) -> SolveResult {
let mut constraints: BTreeMap<String, Vec<VersionReq>> = BTreeMap::new();
for (pkg, req) in roots {
constraints.entry(pkg.clone()).or_default().push(req.clone());
}
let mut assignment: BTreeMap<String, Version> = BTreeMap::new();
search(&mut constraints, &mut assignment, universe)
}
fn search(
constraints: &mut BTreeMap<String, Vec<VersionReq>>,
assignment: &mut BTreeMap<String, Version>,
universe: &Universe,
) -> SolveResult {
// Deterministic package choice: first constrained-but-unassigned package.
let next = constraints
.keys()
.find(|p| !assignment.contains_key(*p))
.cloned();
let Some(pkg) = next else {
return SolveResult::Solved(assignment.clone());
};
let reqs = constraints.get(&pkg).cloned().unwrap_or_default();
// Provably empty range ⇒ dead end for this branch.
let interval = reqs
.iter()
.map(Interval::from_req)
.fold(Interval::full(), |acc, iv| acc.intersect(&iv));
let raw_reqs: Vec<String> = reqs.iter().map(|r| r.to_string()).collect();
if interval.is_empty() {
return SolveResult::Conflict(SolveConflict {
detail: format!("requirements on `{pkg}` intersect to ∅"),
package: pkg,
requirements: raw_reqs,
});
}
// Candidate versions: available ∩ all reqs, highest first.
let mut candidates: Vec<Version> = universe
.available
.get(&pkg)
.cloned()
.unwrap_or_default()
.into_iter()
.filter(|v| reqs.iter().all(|r| r.matches(v)))
.collect();
candidates.sort();
candidates.dedup();
candidates.reverse();
if candidates.is_empty() {
return SolveResult::Conflict(SolveConflict {
detail: format!(
"no available version of `{pkg}` satisfies {} (feasible range {interval})",
if raw_reqs.is_empty() { "its requirements".into() } else { raw_reqs.join(" ∧ ") },
),
package: pkg,
requirements: raw_reqs,
});
}
let mut last_conflict: Option<SolveConflict> = None;
for v in candidates {
assignment.insert(pkg.clone(), v.clone());
// Propagate the dependencies this choice induces, remembering what we added so
// we can undo cleanly on backtrack.
let induced = universe.deps.get(&(pkg.clone(), v.clone())).cloned().unwrap_or_default();
let mut added_keys: Vec<String> = Vec::new();
let mut immediate_conflict = false;
for (dep, req) in &induced {
// An induced requirement that contradicts an ALREADY-chosen version fails
// this candidate immediately.
if let Some(chosen) = assignment.get(dep) {
if !req.matches(chosen) {
immediate_conflict = true;
}
}
constraints.entry(dep.clone()).or_default().push(req.clone());
added_keys.push(dep.clone());
}
if !immediate_conflict {
match search(constraints, assignment, universe) {
SolveResult::Solved(sol) => return SolveResult::Solved(sol),
SolveResult::Conflict(c) => last_conflict = Some(c),
}
}
// Backtrack: pop exactly the requirements we pushed, and unassign.
for dep in added_keys.iter().rev() {
if let Some(v) = constraints.get_mut(dep) {
v.pop();
if v.is_empty() {
constraints.remove(dep);
}
}
}
assignment.remove(&pkg);
}
SolveResult::Conflict(last_conflict.unwrap_or_else(|| SolveConflict {
detail: format!("no assignment for `{pkg}` led to a solution"),
package: pkg,
requirements: raw_reqs,
}))
}
// ─────────────────────────────── tests ───────────────────────────────
#[cfg(test)]
mod tests {
use super::*;
fn req(s: &str) -> VersionReq {
VersionReq::parse(s).unwrap()
}
/// Comparator → interval expansion follows cargo's caret/tilde/wildcard rules.
#[test]
fn interval_from_req_matches_cargo_semantics() {
let cases = [
("^1.2.3", ver(1, 2, 3), ver(2, 0, 0)),
("^1", ver(1, 0, 0), ver(2, 0, 0)),
("^0.2.3", ver(0, 2, 3), ver(0, 3, 0)),
("^0.0.3", ver(0, 0, 3), ver(0, 0, 4)),
("~1.2.3", ver(1, 2, 3), ver(1, 3, 0)),
("~1", ver(1, 0, 0), ver(2, 0, 0)),
("=1.2.3", ver(1, 2, 3), ver(1, 2, 4)),
("1.*", ver(1, 0, 0), ver(2, 0, 0)),
];
for (s, lo, hi) in cases {
let iv = Interval::from_req(&req(s));
assert!(iv.contains(&lo), "{s}: lower {lo} should be in {iv}");
assert!(!iv.contains(&hi), "{s}: upper {hi} should be excluded from {iv}");
assert!(!iv.is_empty(), "{s} is non-empty");
}
}
/// A `>=` / `<` pair intersects to a real window; a disjoint pair to ∅.
#[test]
fn interval_intersection_detects_emptiness() {
let win = Interval::from_req(&req(">=1.2.0")).intersect(&Interval::from_req(&req("<1.5.0")));
assert!(win.contains(&ver(1, 3, 0)) && !win.is_empty());
let disjoint = Interval::from_req(&req("^1")).intersect(&Interval::from_req(&req("^2")));
assert!(disjoint.is_empty(), "^1 ∧ ^2 must be empty, got {disjoint}");
}
/// RED-WHEN-BROKEN: two consumers pin the SAME dep to disjoint majors — the
/// crate-level CSP must surface exactly one `EmptyIntersection` conflict naming
/// both consumers and both requirements. If interval intersection ever silently
/// widened (a real bug we guard), this fires.
#[test]
fn conflicting_range_fixture_is_flagged() {
let constraints = vec![
CrateConstraint { consumer: "skade".into(), dep: "edda".into(), raw_req: "^1".into() },
CrateConstraint { consumer: "holger".into(), dep: "edda".into(), raw_req: "^2".into() },
];
let conflicts = check_crate_constraints(&constraints, &BTreeMap::new());
assert_eq!(conflicts.len(), 1, "one conflicting dep");
let c = &conflicts[0];
assert_eq!(c.dep, "edda");
assert_eq!(c.kind, ConflictKind::EmptyIntersection);
assert_eq!(c.consumers, vec!["holger".to_string(), "skade".to_string()]);
assert!(c.requirements.contains(&"^1".to_string()));
assert!(c.requirements.contains(&"^2".to_string()));
}
/// Ranges that DO overlap but whose overlap no available version reaches ⇒ a
/// `NoAvailableMatch` conflict, distinct from an empty intersection.
#[test]
fn overlapping_ranges_with_no_available_version() {
// `^1.2` ∧ `<1.4` ⇒ feasible [1.2.0, 1.4.0); only 1.5.0 is available.
let constraints = vec![
CrateConstraint { consumer: "a".into(), dep: "edda".into(), raw_req: "^1.2".into() },
CrateConstraint { consumer: "b".into(), dep: "edda".into(), raw_req: "<1.4".into() },
];
let mut avail = BTreeMap::new();
avail.insert("edda".to_string(), vec![ver(1, 5, 0)]);
let conflicts = check_crate_constraints(&constraints, &avail);
assert_eq!(conflicts.len(), 1);
assert_eq!(conflicts[0].kind, ConflictKind::NoAvailableMatch);
// Add a version inside the window ⇒ no conflict.
avail.get_mut("edda").unwrap().push(ver(1, 3, 0));
assert!(check_crate_constraints(&constraints, &avail).is_empty());
}
/// A satisfiable multi-consumer fixture yields no conflicts.
#[test]
fn compatible_ranges_pass() {
let constraints = vec![
CrateConstraint { consumer: "a".into(), dep: "edda".into(), raw_req: "^1.2".into() },
CrateConstraint { consumer: "b".into(), dep: "edda".into(), raw_req: ">=1.3, <2".into() },
];
let mut avail = BTreeMap::new();
avail.insert("edda".to_string(), vec![ver(1, 3, 5)]);
assert!(check_crate_constraints(&constraints, &avail).is_empty());
}
/// The general solver finds a coherent assignment through an induced dependency.
#[test]
fn solver_resolves_transitive_chain() {
let mut u = Universe::default();
u.available.insert("app".into(), vec![ver(1, 0, 0)]);
u.available.insert("lib".into(), vec![ver(1, 0, 0), ver(2, 0, 0)]);
// app 1.0.0 needs lib ^1 (so 2.0.0 must be rejected in favour of 1.0.0).
u.deps.insert(("app".into(), ver(1, 0, 0)), vec![("lib".into(), req("^1"))]);
let roots = vec![("app".to_string(), req("^1"))];
match solve(&roots, &u) {
SolveResult::Solved(sol) => {
assert_eq!(sol.get("app"), Some(&ver(1, 0, 0)));
assert_eq!(sol.get("lib"), Some(&ver(1, 0, 0)), "must pick lib 1.0.0, not 2.0.0");
}
SolveResult::Conflict(c) => panic!("expected a solution, got conflict on {}", c.package),
}
}
/// The general solver reports a conflict when a transitive requirement cannot be
/// met by any available version.
#[test]
fn solver_reports_unsatisfiable_transitive() {
let mut u = Universe::default();
u.available.insert("app".into(), vec![ver(1, 0, 0)]);
u.available.insert("lib".into(), vec![ver(2, 0, 0)]); // only a 2.x exists
u.deps.insert(("app".into(), ver(1, 0, 0)), vec![("lib".into(), req("^1"))]);
let roots = vec![("app".to_string(), req("^1"))];
match solve(&roots, &u) {
SolveResult::Conflict(c) => assert_eq!(c.package, "lib"),
SolveResult::Solved(_) => panic!("lib ^1 is unsatisfiable — expected a conflict"),
}
}
/// Integration: constraints lifted from a `RepoGraph` feed the CSP unchanged.
#[test]
fn constraints_from_repograph_roundtrip() {
use crate::model::RepoGraph;
let mut g = RepoGraph { repo: "edda".into(), ..Default::default() };
let mut deps = BTreeMap::new();
deps.insert("edda".to_string(), BTreeSet::from(["^1".to_string()]));
g.crate_dep_reqs.insert("skade".to_string(), deps);
let mut deps2 = BTreeMap::new();
deps2.insert("edda".to_string(), BTreeSet::from(["^2".to_string()]));
g.crate_dep_reqs.insert("holger".to_string(), deps2);
let constraints = constraints_from_graphs(&[g]);
assert_eq!(constraints.len(), 2);
let conflicts = check_crate_constraints(&constraints, &BTreeMap::new());
assert_eq!(conflicts.len(), 1);
assert_eq!(conflicts[0].kind, ConflictKind::EmptyIntersection);
}
}