diff options
Diffstat (limited to 'crates/mozart-core/src/dependency_resolver/pool.rs')
| -rw-r--r-- | crates/mozart-core/src/dependency_resolver/pool.rs | 427 |
1 files changed, 427 insertions, 0 deletions
diff --git a/crates/mozart-core/src/dependency_resolver/pool.rs b/crates/mozart-core/src/dependency_resolver/pool.rs new file mode 100644 index 0000000..8a63c05 --- /dev/null +++ b/crates/mozart-core/src/dependency_resolver/pool.rs @@ -0,0 +1,427 @@ +use indexmap::IndexMap; +use mozart_semver::VersionConstraint; +use std::fmt; + +/// Unique identifier for a package in the pool. 1-based. +pub type PackageId = u32; + +/// A SAT literal. Positive = install package, negative = don't install. +/// The absolute value is the PackageId. +pub type Literal = i32; + +/// Returns the PackageId from a literal. +#[inline] +pub fn literal_to_package_id(literal: Literal) -> PackageId { + literal.unsigned_abs() +} + +/// A link from a package to another package name with a version constraint. +#[derive(Debug, Clone)] +pub struct PoolLink { + /// The target package name. + pub target: String, + /// The version constraint string (e.g. "^1.0"). + pub constraint: String, + /// The source package name (the one declaring this link). + pub source: String, +} + +impl fmt::Display for PoolLink { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{} {} {}", self.source, self.target, self.constraint) + } +} + +/// A package entry in the pool. This is the SAT solver's view of a package. +#[derive(Debug, Clone)] +pub struct PoolPackage { + /// 1-based package ID assigned by the pool. + pub id: PackageId, + /// Normalized package name (e.g. "monolog/monolog"). + pub name: String, + /// Normalized version string (e.g. "1.0.0.0"). + pub version: String, + /// Pretty version string (e.g. "1.0.0"). + pub pretty_version: String, + /// Package requirements. + pub requires: Vec<PoolLink>, + /// Packages this replaces. + pub replaces: Vec<PoolLink>, + /// Packages this provides. + pub provides: Vec<PoolLink>, + /// Packages this conflicts with. + pub conflicts: Vec<PoolLink>, + /// Whether this is a fixed/locked package. + pub is_fixed: bool, + /// If `Some`, this package is an `AliasPackage` whose target is the + /// other pool entry with the given ID. Composer creates these for + /// `extra.branch-alias` entries (dev branch → numeric alias). When set, + /// the rule generator emits `PackageAlias`/`PackageInverseAlias` rules + /// instead of regular requires; same-name conflict rules also skip + /// alias packages. + pub is_alias_of: Option<PackageId>, +} + +impl PoolPackage { + /// Returns all names this package is known by (own name + provides + replaces targets). + pub fn names(&self) -> Vec<&str> { + let mut names = vec![self.name.as_str()]; + for link in &self.provides { + names.push(link.target.as_str()); + } + for link in &self.replaces { + names.push(link.target.as_str()); + } + names + } + + /// Names that drive same-name conflict resolution — own name plus + /// `replace` targets. `provide` targets are excluded because two packages + /// providing different versions of the same virtual name may legitimately + /// coexist; `replace` declares the replacing package fully supplants the + /// replaced one. Mirrors Composer's `BasePackage::getNames(false)`. + pub fn conflict_names(&self) -> Vec<&str> { + let mut names = vec![self.name.as_str()]; + for link in &self.replaces { + names.push(link.target.as_str()); + } + names + } +} + +impl fmt::Display for PoolPackage { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{} {}", self.name, self.pretty_version) + } +} + +/// Input for building a Pool. Users of the crate provide these. +#[derive(Debug, Clone)] +pub struct PoolPackageInput { + pub name: String, + pub version: String, + pub pretty_version: String, + pub requires: Vec<PoolLink>, + pub replaces: Vec<PoolLink>, + pub provides: Vec<PoolLink>, + pub conflicts: Vec<PoolLink>, + pub is_fixed: bool, + /// When `Some`, the value is the **normalized** version of another input + /// in this build batch with the same `name`; the pool will resolve it to + /// that input's [`PackageId`] in [`PoolPackage::is_alias_of`]. Used by + /// the registry layer to materialize Composer's `AliasPackage` for + /// `extra.branch-alias` entries. + pub is_alias_of: Option<String>, +} + +/// The package pool: contains all candidate packages for dependency resolution. +/// Packages are assigned sequential 1-based IDs. +/// +/// Port of Composer's Pool.php. +pub struct Pool { + /// All packages, indexed by (id - 1). + packages: Vec<PoolPackage>, + /// Index: package name → list of package IDs providing that name. + package_by_name: IndexMap<String, Vec<PackageId>>, + /// Cache for what_provides results. + provider_cache: IndexMap<(String, String), Vec<PackageId>>, + /// Packages that are fixed/locked but unacceptable (e.g. failed stability). + unacceptable_fixed_packages: Vec<PackageId>, +} + +impl Pool { + /// Create a new pool from a list of package inputs. + pub fn new(inputs: Vec<PoolPackageInput>, unacceptable_fixed_ids: Vec<PackageId>) -> Self { + let mut packages: Vec<PoolPackage> = Vec::with_capacity(inputs.len()); + let mut package_by_name: IndexMap<String, Vec<PackageId>> = IndexMap::new(); + // Collect alias links (alias_idx, target_name, target_normalized) for + // a second pass once every input has a stable ID. + let mut pending_aliases: Vec<(usize, String, String)> = Vec::new(); + + for (idx, input) in inputs.into_iter().enumerate() { + let id = (idx as PackageId) + 1; + if let Some(target) = input.is_alias_of.clone() { + pending_aliases.push((idx, input.name.clone(), target)); + } + let pkg = PoolPackage { + id, + name: input.name, + version: input.version, + pretty_version: input.pretty_version, + requires: input.requires, + replaces: input.replaces, + provides: input.provides, + conflicts: input.conflicts, + is_fixed: input.is_fixed, + is_alias_of: None, + }; + + // Index by all names this package provides + for name in pkg.names() { + package_by_name + .entry(name.to_string()) + .or_default() + .push(id); + } + + packages.push(pkg); + } + + // Resolve alias targets: for each alias input, find the matching + // (name, normalized version) entry and store its ID. Mirrors the + // post-construction wiring Composer does in + // `RepositorySet::createAliasPackage` / `addPackage`. + for (alias_idx, name, target_normalized) in pending_aliases { + if let Some(ids) = package_by_name.get(&name) { + let target_id = ids.iter().copied().find(|&id| { + let candidate = &packages[(id - 1) as usize]; + !candidate.name.is_empty() + && candidate.name == name + && candidate.version == target_normalized + && candidate.is_alias_of.is_none() + }); + if let Some(tid) = target_id { + packages[alias_idx].is_alias_of = Some(tid); + } + } + } + + Pool { + packages, + package_by_name, + provider_cache: IndexMap::new(), + unacceptable_fixed_packages: unacceptable_fixed_ids, + } + } + + /// Returns the number of packages in the pool. + pub fn len(&self) -> usize { + self.packages.len() + } + + /// Returns true if the pool has no packages. + pub fn is_empty(&self) -> bool { + self.packages.is_empty() + } + + /// Look up a package by its 1-based ID. + pub fn package_by_id(&self, id: PackageId) -> &PoolPackage { + &self.packages[(id - 1) as usize] + } + + /// All packages in the pool. + pub fn packages(&self) -> &[PoolPackage] { + &self.packages + } + + /// Convert a literal to its package reference. + pub fn literal_to_package(&self, literal: Literal) -> &PoolPackage { + self.package_by_id(literal_to_package_id(literal)) + } + + /// Format a literal as a human-readable string. + pub fn literal_to_pretty_string(&self, literal: Literal) -> String { + let pkg = self.literal_to_package(literal); + let prefix = if literal > 0 { + "install" + } else { + "don't install" + }; + format!("{prefix} {} {}", pkg.name, pkg.pretty_version) + } + + /// Find all packages matching a name and optional constraint. + /// Results are cached. + pub fn what_provides(&mut self, name: &str, constraint: Option<&str>) -> Vec<PackageId> { + let key = (name.to_string(), constraint.unwrap_or("").to_string()); + if let Some(cached) = self.provider_cache.get(&key) { + return cached.clone(); + } + + let result = self.compute_what_provides(name, constraint); + self.provider_cache.insert(key, result.clone()); + result + } + + fn compute_what_provides(&self, name: &str, constraint: Option<&str>) -> Vec<PackageId> { + let Some(candidate_ids) = self.package_by_name.get(name) else { + return vec![]; + }; + + let parsed_constraint = constraint.and_then(|c| VersionConstraint::parse(c).ok()); + + let mut matches = Vec::new(); + for &id in candidate_ids { + let pkg = self.package_by_id(id); + if self.matches_package(pkg, name, parsed_constraint.as_ref()) { + matches.push(id); + } + } + matches + } + + /// Check if a candidate package matches a name and optional constraint. + /// Handles provides and replaces. + fn matches_package( + &self, + candidate: &PoolPackage, + name: &str, + constraint: Option<&VersionConstraint>, + ) -> bool { + if candidate.name == name { + return match constraint { + None => true, + Some(vc) => { + // Try the normalized version first; fall back to the + // pretty version. Composer normalizes both sides of a + // constraint match to a single string form (e.g. + // `dev-master` → `9999999-dev`), so a query for + // `dev-master` matches a package whose pretty version + // is `dev-master` even when the pool stores its + // version field in a different normalized shape (e.g. + // the four-segment `9999999.9999999.9999999.9999999-dev` + // expansion Mozart uses internally for default-branch + // and root-alias entries). The pretty fallback bridges + // that gap without forcing the pool to commit to a + // single normalization. + if let Ok(v) = mozart_semver::Version::parse(&candidate.version) + && vc.matches(&v) + { + return true; + } + if let Ok(pv) = mozart_semver::Version::parse(&candidate.pretty_version) + && vc.matches(&pv) + { + return true; + } + false + } + }; + } + + // Check provides. A package may declare more than one provide link + // for the same target (e.g. an `AliasPackage` carries the base's link + // and an extra link tagged at the alias's own version), so keep + // iterating once a target name matches but the constraint doesn't — + // a later link may still satisfy. + for link in &candidate.provides { + if link.target != name { + continue; + } + match constraint { + None => return true, + Some(vc) => { + if let Ok(provide_vc) = VersionConstraint::parse(&link.constraint) + && constraints_intersect(vc, &provide_vc) + { + return true; + } + } + } + } + + for link in &candidate.replaces { + if link.target != name { + continue; + } + match constraint { + None => return true, + Some(vc) => { + if let Ok(replace_vc) = VersionConstraint::parse(&link.constraint) + && constraints_intersect(vc, &replace_vc) + { + return true; + } + } + } + } + + false + } + + /// Check if a package is in the unacceptable fixed list. + pub fn is_unacceptable_fixed_package(&self, id: PackageId) -> bool { + self.unacceptable_fixed_packages.contains(&id) + } +} + +impl fmt::Display for Pool { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + writeln!(f, "Pool:")?; + for pkg in &self.packages { + writeln!(f, " {:>6}: {} {}", pkg.id, pkg.name, pkg.pretty_version)?; + } + Ok(()) + } +} + +/// Whether the request constraint and the provide/replace link constraint +/// share at least one satisfying version. Mirrors Composer's +/// `ConstraintInterface::matches` semantics: a provide/replace link only +/// makes the candidate a viable provider for those versions of the target +/// that fall in the link's constraint. +fn constraints_intersect(a: &VersionConstraint, b: &VersionConstraint) -> bool { + a.intersects(b) +} + +#[cfg(test)] +mod tests { + use super::*; + + fn make_input(name: &str, version: &str) -> PoolPackageInput { + PoolPackageInput { + name: name.to_string(), + version: version.to_string(), + pretty_version: version.to_string(), + requires: vec![], + replaces: vec![], + provides: vec![], + conflicts: vec![], + is_fixed: false, + is_alias_of: None, + } + } + + #[test] + fn test_pool_basic() { + let mut pool = Pool::new( + vec![ + make_input("a/a", "1.0.0.0"), + make_input("a/a", "2.0.0.0"), + make_input("b/b", "1.0.0.0"), + ], + vec![], + ); + + assert_eq!(pool.len(), 3); + assert_eq!(pool.package_by_id(1).name, "a/a"); + assert_eq!(pool.package_by_id(2).name, "a/a"); + assert_eq!(pool.package_by_id(3).name, "b/b"); + + let providers = pool.what_provides("a/a", None); + assert_eq!(providers, vec![1, 2]); + } + + #[test] + fn test_literal_to_package() { + let pool = Pool::new( + vec![make_input("a/a", "1.0.0.0"), make_input("b/b", "1.0.0.0")], + vec![], + ); + + assert_eq!(pool.literal_to_package(1).name, "a/a"); + assert_eq!(pool.literal_to_package(-1).name, "a/a"); + assert_eq!(pool.literal_to_package(2).name, "b/b"); + assert_eq!(pool.literal_to_package(-2).name, "b/b"); + } + + #[test] + fn test_literal_pretty_string() { + let pool = Pool::new(vec![make_input("a/a", "1.0.0.0")], vec![]); + assert_eq!(pool.literal_to_pretty_string(1), "install a/a 1.0.0.0"); + assert_eq!( + pool.literal_to_pretty_string(-1), + "don't install a/a 1.0.0.0" + ); + } +} |