diff options
Diffstat (limited to 'crates/mozart-sat-resolver/src/pool.rs')
| -rw-r--r-- | crates/mozart-sat-resolver/src/pool.rs | 427 |
1 files changed, 0 insertions, 427 deletions
diff --git a/crates/mozart-sat-resolver/src/pool.rs b/crates/mozart-sat-resolver/src/pool.rs deleted file mode 100644 index 8a63c05..0000000 --- a/crates/mozart-sat-resolver/src/pool.rs +++ /dev/null @@ -1,427 +0,0 @@ -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" - ); - } -} |