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>

2 files changed, 35 insertions, 20 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 {