feat(resolver): real constraint intersection and replace-aware same-name conflicts

`Pool::what_provides` previously accepted any provide/replace candidate
because `constraints_intersect` returned true unconditionally; the
same-name conflict pass also looked only at canonical names, so a
package replacing another at v1.0.0 was treated as a valid provider for
a v2.0.0 require and could coexist with the replaced package. Implement
interval-based `VersionConstraint::intersects` and index packages by
their `replace` targets (matching Composer's `getNames(false)`) when
generating same-name conflict rules.

Greens 3 installer fixtures: conflict_against_replaced_by_dep_package_problem,
provider_conflicts3, replaced_packages_should_not_be_installed.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>

4 files changed, 249 insertions, 32 deletions

diff --git a/crates/mozart-sat-resolver/src/pool.rs b/crates/mozart-sat-resolver/src/pool.rs
index d52d736..652fc60 100644
--- a/crates/mozart-sat-resolver/src/pool.rs
+++ b/crates/mozart-sat-resolver/src/pool.rs
@@ -67,6 +67,19 @@ impl PoolPackage {
         }
         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 {
@@ -281,20 +294,13 @@ impl fmt::Display for Pool {
     }
 }
 
-/// Simple intersection check: does there exist a version that satisfies both constraints?
-/// For provides/replaces matching, we just check if a "=version" from one constraint
-/// can match the other. This is a simplified check.
-fn constraints_intersect(_a: &VersionConstraint, _b: &VersionConstraint) -> bool {
-    // For a basic approximation: if b is a single exact constraint, check if a matches it
-    // and vice versa. For complex cases, we assume they intersect.
-    // This mirrors Composer's behavior where provide/replace constraints are matched
-    // against the requirement constraint.
-    //
-    // In Composer, this is done via `$constraint->matches($link->getConstraint())`
-    // which checks if there exists a version satisfying both.
-    // For now, we'll do a simple approach: always return true (provider matches).
-    // The RuleSetGenerator will create proper rules anyway.
-    true
+/// 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)]
diff --git a/crates/mozart-sat-resolver/src/rule_set_generator.rs b/crates/mozart-sat-resolver/src/rule_set_generator.rs
index bc56dff..83570d5 100644
--- a/crates/mozart-sat-resolver/src/rule_set_generator.rs
+++ b/crates/mozart-sat-resolver/src/rule_set_generator.rs
@@ -125,14 +125,23 @@ impl<'a> RuleSetGenerator<'a> {
             self.added_map.insert(current_id);
 
             let pkg = self.pool.package_by_id(current_id);
-            let pkg_name = pkg.name.clone();
+            let conflict_names: Vec<String> =
+                pkg.conflict_names().into_iter().map(String::from).collect();
             let requires = pkg.requires.clone();
 
-            // Index by name (for same-name conflict rules later)
-            self.added_packages_by_name
-                .entry(pkg_name)
-                .or_default()
-                .push(current_id);
+            // 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.
+            for name in conflict_names {
+                self.added_packages_by_name
+                    .entry(name)
+                    .or_default()
+                    .push(current_id);
+            }
 
             // Process each requirement
             for link in requires {
diff --git a/crates/mozart-semver/src/lib.rs b/crates/mozart-semver/src/lib.rs
index 29df538..8b77300 100644
--- a/crates/mozart-semver/src/lib.rs
+++ b/crates/mozart-semver/src/lib.rs
@@ -384,6 +384,20 @@ impl VersionConstraint {
         }
     }
 
+    /// Whether the two constraints share at least one satisfying version.
+    ///
+    /// Mirrors Composer's `MultiConstraint::matches` which is used to decide
+    /// whether a `provide` / `replace` link can satisfy a `require`. OR
+    /// constraints are flattened, then each AND/Single branch is reduced to a
+    /// single (low, high, excluded) interval; the two intervals are intersected
+    /// arithmetically.
+    pub fn intersects(&self, other: &VersionConstraint) -> bool {
+        let lhs = flatten_or(self);
+        let rhs = flatten_or(other);
+        lhs.iter()
+            .any(|a| rhs.iter().any(|b| ranges_intersect(a, b)))
+    }
+
     /// Parse a constraint string like `^1.2`, `>=1.0 <2.0`, `^1.0 || ^2.0`.
     pub fn parse(input: &str) -> Result<VersionConstraint, String> {
         let input = input.trim();
@@ -406,6 +420,147 @@ impl VersionConstraint {
     }
 }
 
+// ─────────────────────────────────────────────────────────────────────────────
+// Constraint intersection helpers
+// ─────────────────────────────────────────────────────────────────────────────
+
+/// A reduced range form of a constraint branch: a half-open interval with an
+/// optional excluded version (from `!=`). `lower`/`upper` are `(version,
+/// inclusive)`; `None` means unbounded on that side.
+#[derive(Debug, Clone)]
+struct Range {
+    lower: Option<(Version, bool)>,
+    upper: Option<(Version, bool)>,
+    excluded: Vec<Version>,
+}
+
+impl Range {
+    fn unbounded() -> Self {
+        Range {
+            lower: None,
+            upper: None,
+            excluded: Vec::new(),
+        }
+    }
+}
+
+/// Flatten an OR tree into a vector of single-branch ranges. Returns one entry
+/// per disjunct; AND trees are merged into a single Range.
+fn flatten_or(c: &VersionConstraint) -> Vec<Range> {
+    match c {
+        VersionConstraint::Or(cs) => cs.iter().flat_map(flatten_or).collect(),
+        _ => match constraint_to_range(c) {
+            Some(r) => vec![r],
+            None => vec![Range::unbounded()],
+        },
+    }
+}
+
+/// Reduce a non-OR constraint to a single Range. Returns `None` if the
+/// constraint has nested OR (caller should `flatten_or` first).
+fn constraint_to_range(c: &VersionConstraint) -> Option<Range> {
+    match c {
+        VersionConstraint::Single(atom) => Some(atom_to_range(atom)),
+        VersionConstraint::And(cs) => {
+            let mut acc = Range::unbounded();
+            for sub in cs {
+                let r = constraint_to_range(sub)?;
+                merge_into(&mut acc, &r);
+            }
+            Some(acc)
+        }
+        VersionConstraint::Or(_) => None,
+    }
+}
+
+fn atom_to_range(c: &Constraint) -> Range {
+    match c {
+        Constraint::Any => Range::unbounded(),
+        Constraint::Exact(v) => Range {
+            lower: Some((v.clone(), true)),
+            upper: Some((v.clone(), true)),
+            excluded: Vec::new(),
+        },
+        Constraint::GreaterThan(v) => Range {
+            lower: Some((v.clone(), false)),
+            upper: None,
+            excluded: Vec::new(),
+        },
+        Constraint::GreaterThanOrEqual(v) => Range {
+            lower: Some((v.clone(), true)),
+            upper: None,
+            excluded: Vec::new(),
+        },
+        Constraint::LessThan(v) => Range {
+            lower: None,
+            upper: Some((v.clone(), false)),
+            excluded: Vec::new(),
+        },
+        Constraint::LessThanOrEqual(v) => Range {
+            lower: None,
+            upper: Some((v.clone(), true)),
+            excluded: Vec::new(),
+        },
+        Constraint::NotEqual(v) => Range {
+            lower: None,
+            upper: None,
+            excluded: vec![v.clone()],
+        },
+    }
+}
+
+/// Tighten `acc` by intersecting with `other`. Lower bound becomes the higher
+/// of the two; upper bound becomes the lower; excluded versions accumulate.
+fn merge_into(acc: &mut Range, other: &Range) {
+    if let Some((ov, oi)) = &other.lower {
+        match &acc.lower {
+            None => acc.lower = Some((ov.clone(), *oi)),
+            Some((av, ai)) => {
+                if ov > av || (ov == av && !*oi && *ai) {
+                    acc.lower = Some((ov.clone(), *oi));
+                }
+            }
+        }
+    }
+    if let Some((ov, oi)) = &other.upper {
+        match &acc.upper {
+            None => acc.upper = Some((ov.clone(), *oi)),
+            Some((av, ai)) => {
+                if ov < av || (ov == av && !*oi && *ai) {
+                    acc.upper = Some((ov.clone(), *oi));
+                }
+            }
+        }
+    }
+    acc.excluded.extend(other.excluded.iter().cloned());
+}
+
+/// Whether two reduced ranges share at least one version.
+fn ranges_intersect(a: &Range, b: &Range) -> bool {
+    let mut combined = a.clone();
+    merge_into(&mut combined, b);
+
+    // Empty interval (lower > upper)
+    if let (Some((lo, li)), Some((hi, hi_inc))) = (&combined.lower, &combined.upper) {
+        if lo > hi {
+            return false;
+        }
+        if lo == hi && !(*li && *hi_inc) {
+            return false;
+        }
+        // Pinned to a single version that is excluded
+        if lo == hi && *li && *hi_inc && combined.excluded.iter().any(|e| e == lo) {
+            return false;
+        }
+    }
+
+    // Witness extraction is approximate: if no bounds, any version works.
+    // Excluded versions only invalidate when the interval has shrunk to a
+    // single excluded point (handled above) — for ranges with width, a
+    // satisfying neighbour always exists.
+    true
+}
+
 /// Split on `|` or `||` (pipe-OR). Composer accepts both forms.
 fn split_or(s: &str) -> Vec<&str> {
     let mut parts = Vec::new();
@@ -2101,4 +2256,60 @@ mod tests {
         let b = Version::parse("20220101.0.0").unwrap();
         assert!(a > b);
     }
+
+    #[test]
+    fn test_intersects_disjoint_exacts() {
+        // The replaced-packages cluster: a `replace: foo "1.0.0"` link is
+        // not a valid provider for a `require: foo "2.0.0"` request.
+        let a = VersionConstraint::parse("1.0.0").unwrap();
+        let b = VersionConstraint::parse("2.0.0").unwrap();
+        assert!(!a.intersects(&b));
+        assert!(!b.intersects(&a));
+    }
+
+    #[test]
+    fn test_intersects_overlapping_ranges() {
+        let a = VersionConstraint::parse("^1.0").unwrap();
+        let b = VersionConstraint::parse(">=1.5 <3.0").unwrap();
+        assert!(a.intersects(&b));
+    }
+
+    #[test]
+    fn test_intersects_disjoint_ranges() {
+        let a = VersionConstraint::parse("^1.0").unwrap();
+        let b = VersionConstraint::parse("^2.0").unwrap();
+        assert!(!a.intersects(&b));
+    }
+
+    #[test]
+    fn test_intersects_or_branch() {
+        // Either branch in an OR is enough to intersect.
+        let a = VersionConstraint::parse("1.0.0 || 2.0.0").unwrap();
+        let b = VersionConstraint::parse("2.0.0").unwrap();
+        assert!(a.intersects(&b));
+    }
+
+    #[test]
+    fn test_intersects_any() {
+        let a = VersionConstraint::parse("*").unwrap();
+        let b = VersionConstraint::parse("1.0.0").unwrap();
+        assert!(a.intersects(&b));
+        assert!(b.intersects(&a));
+    }
+
+    #[test]
+    fn test_intersects_touching_open_boundaries() {
+        // [1, 2) and (2, 3] do not share any version.
+        let a = VersionConstraint::parse(">=1.0 <2.0").unwrap();
+        let b = VersionConstraint::parse(">2.0 <=3.0").unwrap();
+        assert!(!a.intersects(&b));
+    }
+
+    #[test]
+    fn test_intersects_touching_closed_boundaries() {
+        // [1, 2] and [2, 3] share version 2.
+        let a = VersionConstraint::parse(">=1.0 <=2.0").unwrap();
+        let b = VersionConstraint::parse(">=2.0 <=3.0").unwrap();
+        assert!(a.intersects(&b));
+    }
 }
diff --git a/crates/mozart/tests/installer.rs b/crates/mozart/tests/installer.rs
index beeb8de..e1bc7a5 100644
--- a/crates/mozart/tests/installer.rs
+++ b/crates/mozart/tests/installer.rs
@@ -113,10 +113,7 @@ installer_fixture!(
 installer_fixture!(circular_dependency_errors);
 installer_fixture!(conflict_against_provided_by_dep_package_works);
 installer_fixture!(conflict_against_provided_package_works);
-installer_fixture!(
-    conflict_against_replaced_by_dep_package_problem,
-    ignore = "mozart binary cannot yet run this fixture"
-);
+installer_fixture!(conflict_against_replaced_by_dep_package_problem);
 installer_fixture!(
     conflict_against_replaced_package_problem,
     ignore = "mozart binary cannot yet run this fixture"
@@ -254,10 +251,7 @@ installer_fixture!(
     ignore = "mozart binary cannot yet run this fixture"
 );
 installer_fixture!(provider_conflicts2);
-installer_fixture!(
-    provider_conflicts3,
-    ignore = "mozart binary cannot yet run this fixture"
-);
+installer_fixture!(provider_conflicts3);
 installer_fixture!(
     provider_dev_require_can_satisfy_require,
     ignore = "mozart binary cannot yet run this fixture"
@@ -287,10 +281,7 @@ installer_fixture!(
 installer_fixture!(replace_priorities);
 installer_fixture!(replace_range_require_single_version);
 installer_fixture!(replace_root_require);
-installer_fixture!(
-    replaced_packages_should_not_be_installed,
-    ignore = "mozart binary cannot yet run this fixture"
-);
+installer_fixture!(replaced_packages_should_not_be_installed);
 installer_fixture!(
     replaced_packages_should_not_be_installed_when_installing_from_lock,
     ignore = "mozart binary cannot yet run this fixture"