fix(install): align partial-update operation order with Composer

Three coordinated changes to make `update --with-dependencies` produce
the same operation trace Composer emits:

- LockFileGenerationRequest gains a previous_lock field. When a
  resolved package matches an entry in the old lock at the same name +
  version_normalized, its relationship-shaped fields (require /
  require-dev / conflict / replace / provide / suggest) are carried
  over verbatim. Source/dist refs and version-shaped fields still
  refresh from upstream metadata so dev packages can still pick up new
  commits. Without this carry-over, partial updates regenerated lock
  entries from upstream COMPOSER repo definitions, which can declare
  different requires than the lock — and topological_sort then sees a
  graph Composer's transaction never built.

- Transaction's topological_sort and get_root_packages now expand
  replace/provide targets when matching `require` links to result
  packages, mirroring Composer's getProvidersInResult. Previously a
  package was only treated as required when matched by its own name,
  so packages reached only via replace/provide were mis-classified as
  roots and the DFS stack visited deps in the wrong order.

- compute_operations iterates installed.json in reverse when emitting
  removals, mirroring Composer's array_unshift onto operations. Two
  co-orphaned packages otherwise emit removals in the wrong order vs
  Composer's trace.

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

1 files changed, 35 insertions, 20 deletions

diff --git a/crates/mozart-sat-resolver/src/transaction.rs b/crates/mozart-sat-resolver/src/transaction.rs
index de7c9a0..bf7befc 100644
--- a/crates/mozart-sat-resolver/src/transaction.rs
+++ b/crates/mozart-sat-resolver/src/transaction.rs
@@ -158,21 +158,30 @@ impl<'a> Transaction<'a> {
     /// Topologically sort result packages by their dependency order.
     /// Uses DFS: dependencies are processed before dependents.
     fn topological_sort(&self) -> Vec<PackageId> {
-        let result_set: IndexSet<PackageId> = self.result_ids.iter().copied().collect();
-        let result_by_name: IndexMap<&str, Vec<PackageId>> = {
-            let mut map: IndexMap<&str, Vec<PackageId>> = IndexMap::new();
-            for &id in &self.result_ids {
-                let pkg = self.pool.package_by_id(id);
-                map.entry(&pkg.name).or_default().push(id);
+        // Index every result package by every name it answers to (own name +
+        // `replaces` targets + `provides` targets). Mirrors Composer's
+        // `resultPackagesByName` map, which `getProvidersInResult` queries
+        // when walking a package's requires — so a replace/provide target
+        // resolves to the package that satisfies it. Without this expansion
+        // the DFS treats replace/provide-only requires as unsatisfied and
+        // misses the transitive ordering edge.
+        let mut result_by_target: IndexMap<&str, Vec<PackageId>> = IndexMap::new();
+        for &id in &self.result_ids {
+            let pkg = self.pool.package_by_id(id);
+            result_by_target.entry(&pkg.name).or_default().push(id);
+            for link in &pkg.replaces {
+                result_by_target.entry(&link.target).or_default().push(id);
             }
-            map
-        };
+            for link in &pkg.provides {
+                result_by_target.entry(&link.target).or_default().push(id);
+            }
+        }
 
         let mut visited: IndexSet<PackageId> = IndexSet::new();
         let mut order: Vec<PackageId> = Vec::new();
 
         // Find root packages (not required by any other result package)
-        let roots = self.get_root_packages(&result_set, &result_by_name);
+        let roots = self.get_root_packages(&result_by_target);
 
         // DFS from roots
         let mut stack: Vec<(PackageId, bool)> = Vec::new();
@@ -198,7 +207,7 @@ impl<'a> Transaction<'a> {
             // Push dependencies
             let pkg = self.pool.package_by_id(pkg_id);
             for req in &pkg.requires {
-                if let Some(provider_ids) = result_by_name.get(req.target.as_str()) {
+                if let Some(provider_ids) = result_by_target.get(req.target.as_str()) {
                     for &dep_id in provider_ids {
                         if !visited.contains(&dep_id) {
                             stack.push((dep_id, false));
@@ -218,26 +227,32 @@ impl<'a> Transaction<'a> {
         order
     }
 
-    /// Find root packages: result packages not required by any other result package.
+    /// Find root packages: result packages not required by any other result
+    /// package. A package whose own name (or any `replaces`/`provides`
+    /// target) appears in another result package's `requires` is excluded.
+    /// Mirrors Composer's `Transaction::getRootPackages`, which uses
+    /// `getProvidersInResult` to do the same expansion.
     fn get_root_packages(
         &self,
-        result_set: &IndexSet<PackageId>,
-        _result_by_name: &IndexMap<&str, Vec<PackageId>>,
+        result_by_target: &IndexMap<&str, Vec<PackageId>>,
     ) -> Vec<PackageId> {
-        // Collect all required package names
-        let mut required_names: IndexSet<&str> = IndexSet::new();
-        for &id in result_set {
+        let mut required: IndexSet<PackageId> = IndexSet::new();
+        for &id in &self.result_ids {
             let pkg = self.pool.package_by_id(id);
             for req in &pkg.requires {
-                required_names.insert(&req.target);
+                if let Some(provider_ids) = result_by_target.get(req.target.as_str()) {
+                    for &dep_id in provider_ids {
+                        if dep_id != id {
+                            required.insert(dep_id);
+                        }
+                    }
+                }
             }
         }
 
-        // Root packages are those whose name is NOT in required_names
         let mut roots: Vec<PackageId> = Vec::new();
         for &id in &self.result_ids {
-            let pkg = self.pool.package_by_id(id);
-            if !required_names.contains(pkg.name.as_str()) {
+            if !required.contains(&id) {
                 roots.push(id);
             }
         }