path: root/crates/mozart-sat-resolver/src/rule_set_generator.rs

use crate::pool::{Literal, PackageId, Pool, PoolLink};
use crate::rule::{ReasonData, Rule, RuleReason, RuleType};
use crate::rule_set::RuleSet;
use mozart_semver::VersionConstraint;
use std::collections::{HashMap, HashSet, VecDeque};

/// Generates SAT rules from the pool and request.
///
/// Port of Composer's RuleSetGenerator.php.
pub struct RuleSetGenerator<'a> {
    pool: &'a mut Pool,
    rules: RuleSet,
    /// Packages already processed.
    added_map: HashSet<PackageId>,
    /// Package names → list of package IDs with that name (non-alias).
    added_packages_by_name: HashMap<String, Vec<PackageId>>,
    /// Specific platform packages to ignore (from `--ignore-platform-req=name`).
    ignore_platform_reqs: HashSet<String>,
    /// When true, every platform package is treated as ignored.
    /// Mirrors `--ignore-platform-reqs` (no value).
    ignore_all_platform_reqs: bool,
}

impl<'a> RuleSetGenerator<'a> {
    pub fn new(pool: &'a mut Pool) -> Self {
        RuleSetGenerator {
            pool,
            rules: RuleSet::new(),
            added_map: HashSet::new(),
            added_packages_by_name: HashMap::new(),
            ignore_platform_reqs: HashSet::new(),
            ignore_all_platform_reqs: false,
        }
    }

    /// Set platform requirements to ignore.
    pub fn set_ignore_platform_reqs(&mut self, names: HashSet<String>) {
        self.ignore_platform_reqs = names;
    }

    /// When set, every platform package is treated as ignored.
    pub fn set_ignore_all_platform_reqs(&mut self, ignore_all: bool) {
        self.ignore_all_platform_reqs = ignore_all;
    }

    fn is_ignored_platform_dep(&self, name: &str) -> bool {
        if self
            .ignore_platform_reqs
            .iter()
            .any(|p| mozart_core::matches_wildcard(name, p))
        {
            return true;
        }
        self.ignore_all_platform_reqs && mozart_core::platform::is_platform_package(name)
    }

    /// Generate rules for a set of requirements and fixed packages.
    ///
    /// Port of Composer's RuleSetGenerator::getRulesFor.
    ///
    /// `root_provides` / `root_replaces` map a target package name to the
    /// constraint declared in the root composer.json's `provide` / `replace`
    /// section. They mirror the "self-fulfilling rule" check in Composer's
    /// `RuleSetGenerator::createRequireRule`: when the root package itself
    /// provides or replaces a name it requires, no install-one-of rule is
    /// emitted for that root require — root is implicitly already installed,
    /// so the requirement is trivially satisfied without forcing a real
    /// provider. Without this, Mozart picks up an inline `provided/pkg` from
    /// the repository even though the root claims to fulfill it itself.
    pub fn generate(
        mut self,
        requires: &HashMap<String, Option<String>>,
        fixed_packages: &[PackageId],
        root_provides: &HashMap<String, String>,
        root_replaces: &HashMap<String, String>,
    ) -> RuleSet {
        // Process fixed packages
        for &pkg_id in fixed_packages {
            if self.pool.is_unacceptable_fixed_package(pkg_id) {
                continue;
            }

            self.add_rules_for_package(pkg_id);

            // Create assertion rule: this package must be installed
            let rule = Rule::new(
                vec![pkg_id as Literal],
                RuleReason::Fixed,
                ReasonData::Fixed { package_id: pkg_id },
            );
            self.rules.add(rule, RuleType::Request);
        }

        // Process root requirements
        for (name, constraint) in requires {
            if self.is_ignored_platform_dep(name.as_str()) {
                continue;
            }

            // Self-fulfilling root require: if the root composer.json declares
            // `provide` / `replace` for this name and the link constraint
            // intersects the require constraint, drop the install-one-of rule
            // entirely. Mirrors Composer's `createRequireRule` returning null
            // when a provider IS the package itself: there, the root is in the
            // pool as a fixed package and `whatProvides` includes it, so the
            // resulting rule is trivially satisfied. Mozart does not yet add
            // the root to the pool, so we make the same decision here based
            // on the explicit root provide/replace tables.
            if root_self_fulfills(name, constraint.as_deref(), root_provides)
                || root_self_fulfills(name, constraint.as_deref(), root_replaces)
            {
                continue;
            }

            let providers = self.pool.what_provides(name, constraint.as_deref());

            if !providers.is_empty() {
                for &pkg_id in &providers {
                    self.add_rules_for_package(pkg_id);
                }

                // Create "install one of" rule
                let literals: Vec<Literal> = providers.iter().map(|&id| id as Literal).collect();
                let rule = Rule::new(
                    literals,
                    RuleReason::RootRequire,
                    ReasonData::RootRequire {
                        package_name: name.clone(),
                        constraint: constraint.clone().unwrap_or_default(),
                    },
                );
                self.rules.add(rule, RuleType::Request);
            }
        }

        // Mirror Composer's `RuleSetGenerator::addRulesForRootAliases`:
        // ensure every alias whose target was already added gets its own
        // alias↔target rules, even when the alias itself didn't appear in
        // any root require's `whatProvides` (e.g. the synthetic
        // `9999999-dev` alias from a `default-branch: true` package, which
        // only matches a literal `9999999-dev` constraint).
        let alias_pairs: Vec<(PackageId, PackageId)> = self
            .pool
            .packages()
            .iter()
            .filter_map(|p| p.is_alias_of.map(|t| (p.id, t)))
            .collect();
        for (alias_id, target_id) in alias_pairs {
            if self.added_map.contains(&target_id) && !self.added_map.contains(&alias_id) {
                self.add_rules_for_package(alias_id);
            }
        }

        // Add conflict rules
        self.add_conflict_rules();

        self.rules
    }

    /// Add rules for a package and its transitive dependencies.
    ///
    /// Port of Composer's RuleSetGenerator::addRulesForPackage.
    fn add_rules_for_package(&mut self, pkg_id: PackageId) {
        let mut work_queue: VecDeque<PackageId> = VecDeque::new();
        work_queue.push_back(pkg_id);

        while let Some(current_id) = work_queue.pop_front() {
            if self.added_map.contains(&current_id) {
                continue;
            }
            self.added_map.insert(current_id);

            let pkg = self.pool.package_by_id(current_id);
            let conflict_names: Vec<String> =
                pkg.conflict_names().into_iter().map(String::from).collect();
            let requires = pkg.requires.clone();
            let alias_target = pkg.is_alias_of;

            if let Some(target_id) = alias_target {
                // Mirror Composer's RuleSetGenerator::addRulesForPackage alias
                // branch: enqueue the target, emit `(-alias | target)` so the
                // alias forces the target, and `(-target | alias)` so the
                // target forces the alias (they install together). The alias
                // is NOT indexed under its name for same-name conflicts —
                // Composer skips that for aliases too.
                work_queue.push_back(target_id);

                let alias_rule = Rule::two_literals(
                    -(current_id as Literal),
                    target_id as Literal,
                    RuleReason::PackageAlias,
                    ReasonData::AliasPackage(current_id),
                );
                self.rules.add(alias_rule, RuleType::Package);

                let inverse_rule = Rule::two_literals(
                    -(target_id as Literal),
                    current_id as Literal,
                    RuleReason::PackageInverseAlias,
                    ReasonData::AliasPackage(current_id),
                );
                self.rules.add(inverse_rule, RuleType::Package);

                // The aliased target carries the actual requires; skip
                // alias's own (link-rewritten copy) to avoid duplicates.
                continue;
            }

            // Index by every name this package fully claims (own name +
            // `replace` targets). Same-name conflict rules (below) then
            // prevent two packages from coexisting under the same logical
            // identity. Mirrors `BasePackage::getNames(false)` indexing in
            // Composer's RuleSetGenerator::addRulesForPackage — `provide`
            // targets are intentionally omitted so that providers can
            // coexist with the package they provide. Alias packages are
            // skipped because the target package's name already covers them.
            for name in conflict_names {
                self.added_packages_by_name
                    .entry(name)
                    .or_default()
                    .push(current_id);
            }

            // Process each requirement
            for link in requires {
                if self.is_ignored_platform_dep(&link.target) {
                    continue;
                }

                let possible_requires = self
                    .pool
                    .what_provides(&link.target, Some(&link.constraint));

                // Create require rule: (-current | provider1 | provider2 | ...)
                let mut literals: Vec<Literal> = vec![-(current_id as Literal)];
                let mut self_fulfilling = false;

                for &provider_id in &possible_requires {
                    if provider_id == current_id {
                        self_fulfilling = true;
                        break;
                    }
                    literals.push(provider_id as Literal);
                }

                if !self_fulfilling {
                    let rule = Rule::new(
                        literals,
                        RuleReason::PackageRequires,
                        ReasonData::Link(PoolLink {
                            target: link.target.clone(),
                            constraint: link.constraint.clone(),
                            source: self.pool.package_by_id(current_id).name.clone(),
                        }),
                    );
                    self.rules.add(rule, RuleType::Package);
                }

                // Enqueue providers for further processing
                for &provider_id in &possible_requires {
                    work_queue.push_back(provider_id);
                }
            }
        }
    }

    /// Add conflict rules: explicit conflicts and same-name rules.
    ///
    /// Port of Composer's RuleSetGenerator::addConflictRules.
    fn add_conflict_rules(&mut self) {
        // Explicit conflicts
        let added_ids: Vec<PackageId> = self.added_map.iter().copied().collect();
        for &pkg_id in &added_ids {
            let pkg = self.pool.package_by_id(pkg_id);
            let conflicts = pkg.conflicts.clone();

            for link in conflicts {
                if self.is_ignored_platform_dep(&link.target) {
                    continue;
                }

                if !self.added_packages_by_name.contains_key(&link.target) {
                    continue;
                }

                let conflicting = self
                    .pool
                    .what_provides(&link.target, Some(&link.constraint));

                for &conflict_id in &conflicting {
                    if conflict_id == pkg_id {
                        continue; // ignore self-conflict
                    }
                    let rule = Rule::two_literals(
                        -(pkg_id as Literal),
                        -(conflict_id as Literal),
                        RuleReason::PackageConflict,
                        ReasonData::Link(link.clone()),
                    );
                    self.rules.add(rule, RuleType::Package);
                }
            }
        }

        // Same-name rules: only one version of a package can be installed
        let names_to_process: Vec<(String, Vec<PackageId>)> = self
            .added_packages_by_name
            .iter()
            .filter(|(_, ids)| ids.len() > 1)
            .map(|(name, ids)| (name.clone(), ids.clone()))
            .collect();

        for (name, pkg_ids) in names_to_process {
            let literals: Vec<Literal> = pkg_ids.iter().map(|&id| -(id as Literal)).collect();

            if literals.len() == 2 {
                let rule = Rule::two_literals(
                    literals[0],
                    literals[1],
                    RuleReason::PackageSameName,
                    ReasonData::PackageName(name),
                );
                self.rules.add(rule, RuleType::Package);
            } else if literals.len() >= 3 {
                let rule = Rule::multi_conflict(
                    literals,
                    RuleReason::PackageSameName,
                    ReasonData::PackageName(name),
                );
                self.rules.add(rule, RuleType::Package);
            }
        }
    }
}

/// True when the root composer.json's `provide` / `replace` map declares
/// `target` with a constraint that intersects the require's constraint. A
/// missing require constraint is treated as `*` (matches anything), and a
/// missing/unparsable link constraint conservatively does NOT match — the
/// fixture fails closed back to the regular install-one-of path.
fn root_self_fulfills(
    target: &str,
    require_constraint: Option<&str>,
    root_links: &HashMap<String, String>,
) -> bool {
    let Some(link_constraint_str) = root_links.get(target) else {
        return false;
    };
    let Ok(link_vc) = VersionConstraint::parse(link_constraint_str) else {
        return false;
    };
    match require_constraint {
        None => true,
        Some(req) => match VersionConstraint::parse(req) {
            Ok(req_vc) => req_vc.intersects(&link_vc),
            Err(_) => false,
        },
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::pool::{Pool, PoolLink, PoolPackageInput};

    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_root_require_generates_rule() {
        let mut pool = Pool::new(
            vec![make_input("a/a", "1.0.0.0"), make_input("a/a", "2.0.0.0")],
            vec![],
        );

        let mut requires = HashMap::new();
        requires.insert("a/a".to_string(), None);

        let generator = RuleSetGenerator::new(&mut pool);
        let rules = generator.generate(&requires, &[], &HashMap::new(), &HashMap::new());

        // Should have a request rule: (1 | 2)
        let request_count = rules.iter_type(RuleType::Request).count();
        assert_eq!(request_count, 1);

        // Should have a same-name rule: (-1 | -2)
        let package_count = rules.iter_type(RuleType::Package).count();
        assert!(package_count >= 1);
    }

    #[test]
    fn test_dependency_chain_rules() {
        // a/a 1.0 requires b/b
        let mut pool = Pool::new(
            vec![
                PoolPackageInput {
                    name: "a/a".to_string(),
                    version: "1.0.0.0".to_string(),
                    pretty_version: "1.0.0".to_string(),
                    requires: vec![PoolLink {
                        target: "b/b".to_string(),
                        constraint: "*".to_string(),
                        source: "a/a".to_string(),
                    }],
                    replaces: vec![],
                    provides: vec![],
                    conflicts: vec![],
                    is_fixed: false,
                    is_alias_of: None,
                },
                make_input("b/b", "1.0.0.0"),
            ],
            vec![],
        );

        let mut requires = HashMap::new();
        requires.insert("a/a".to_string(), None);

        let generator = RuleSetGenerator::new(&mut pool);
        let rules = generator.generate(&requires, &[], &HashMap::new(), &HashMap::new());

        // Should have:
        // 1. Request rule: (1) — root requires a/a
        // 2. Package rule: (-1 | 2) — a/a requires b/b
        assert!(rules.len() >= 2);
    }

    #[test]
    fn test_fixed_package_rule() {
        let mut pool = Pool::new(vec![make_input("php", "8.2.0.0")], vec![]);

        let generator = RuleSetGenerator::new(&mut pool);
        let rules = generator.generate(&HashMap::new(), &[1], &HashMap::new(), &HashMap::new());

        // Should have an assertion rule: (1)
        let request_rules: Vec<_> = rules.iter_type(RuleType::Request).collect();
        assert_eq!(request_rules.len(), 1);
        assert!(request_rules[0].1.is_assertion());
    }
}