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>

8 files changed, 157 insertions, 32 deletions

diff --git a/crates/mozart-registry/src/lockfile.rs b/crates/mozart-registry/src/lockfile.rs
index 5e07e9d..6979301 100644
--- a/crates/mozart-registry/src/lockfile.rs
+++ b/crates/mozart-registry/src/lockfile.rs
@@ -459,6 +459,14 @@ pub struct LockFileGenerationRequest {
     /// Repository set used to fetch full metadata for resolved packages
     /// that aren't already covered by inline `type: package` repositories.
     pub repositories: std::sync::Arc<RepositorySet>,
+    /// Previous `composer.lock` (when running update / require / remove).
+    /// For each resolved package whose name+normalized-version matches an
+    /// entry in this lock, the entry is copied into the new lock verbatim
+    /// rather than being re-fetched from the inline / composer-repo /
+    /// Packagist sources. Mirrors Composer's `Locker::setLockData` behaviour
+    /// during partial updates: lock entries are stable across updates that
+    /// don't touch the package, even if the upstream metadata has drifted.
+    pub previous_lock: Option<LockFile>,
 }
 
 impl LockFileGenerationRequest {
@@ -666,7 +674,7 @@ fn classify_dev_packages(
     resolved: &[ResolvedPackage],
     require: &BTreeMap<String, String>,
     _require_dev: &BTreeMap<String, String>,
-    package_metadata: &IndexMap<String, PackagistVersion>,
+    requires_by_name: &IndexMap<String, Vec<String>>,
 ) -> IndexSet<String> {
     // Build set of all resolved package names for quick lookup
     let resolved_names: IndexSet<&str> = resolved.iter().map(|p| p.name.as_str()).collect();
@@ -690,8 +698,8 @@ fn classify_dev_packages(
 
     // BFS: walk transitive `require` deps of each production package
     while let Some(pkg_name) = queue.pop_front() {
-        if let Some(pv) = package_metadata.get(&pkg_name) {
-            for dep_name in pv.require.keys() {
+        if let Some(deps) = requires_by_name.get(&pkg_name) {
+            for dep_name in deps {
                 let dep_lower = dep_name.to_lowercase();
                 if is_platform_name(&dep_lower) {
                     continue;
@@ -759,6 +767,60 @@ pub async fn generate_lock_file(request: &LockFileGenerationRequest) -> anyhow::
     // — short-circuit those before hitting the network. Everything else goes
     // through `RepositorySet`, which today contains only Packagist; future
     // steps will move VCS / inline through the same set.
+    // Previous-lock relationship pass-through: when a resolved package
+    // matches an entry in `previous_lock` at the same name +
+    // version_normalized, capture the entry's relationship-shaped fields
+    // (require / require-dev / conflict / replace / provide / suggest).
+    // Composer's transaction calculates operation order using these
+    // relationship fields off the locked repository, so a partial update
+    // shouldn't refresh them from upstream metadata for packages that
+    // didn't move — otherwise topological_sort sees a different graph
+    // than Composer would.
+    //
+    // Source/dist references and version-shaped fields still come from
+    // the freshly-fetched metadata, so dev packages whose ref bumped (the
+    // resolver picked a new commit at the same version label) still get
+    // their ref refreshed.
+    struct PreservedRelationships {
+        require: BTreeMap<String, String>,
+        require_dev: BTreeMap<String, String>,
+        conflict: BTreeMap<String, String>,
+        provide: BTreeMap<String, String>,
+        replace: BTreeMap<String, String>,
+        suggest: Option<BTreeMap<String, String>>,
+    }
+    let mut preserved_rel: IndexMap<String, PreservedRelationships> = IndexMap::new();
+    if let Some(prev) = &request.previous_lock {
+        for prev_pkg in prev
+            .packages
+            .iter()
+            .chain(prev.packages_dev.iter().flatten())
+        {
+            let prev_normalized = prev_pkg.version_normalized.clone().unwrap_or_else(|| {
+                mozart_semver::Version::parse(&prev_pkg.version)
+                    .map(|v| v.to_string())
+                    .unwrap_or_else(|_| prev_pkg.version.clone())
+            });
+            for pkg in &real_resolved {
+                if pkg.name.eq_ignore_ascii_case(&prev_pkg.name)
+                    && pkg.version_normalized == prev_normalized
+                {
+                    preserved_rel.insert(
+                        pkg.name.clone(),
+                        PreservedRelationships {
+                            require: prev_pkg.require.clone(),
+                            require_dev: prev_pkg.require_dev.clone(),
+                            conflict: prev_pkg.conflict.clone(),
+                            provide: prev_pkg.provide.clone(),
+                            replace: prev_pkg.replace.clone(),
+                            suggest: prev_pkg.suggest.clone(),
+                        },
+                    );
+                }
+            }
+        }
+    }
+
     let mut package_metadata: IndexMap<String, PackagistVersion> = IndexMap::new();
     let repo_set = &request.repositories;
     for pkg in &real_resolved {
@@ -801,11 +863,23 @@ pub async fn generate_lock_file(request: &LockFileGenerationRequest) -> anyhow::
             alias_of_normalized: None,
         })
         .collect();
+    // Build the `name → require keys` view classify_dev_packages walks. Use
+    // preserved-from-old-lock requires when available so a partial update
+    // sees the same dev-classification graph the previous lock did.
+    let mut requires_by_name: IndexMap<String, Vec<String>> = IndexMap::new();
+    for (name, pv) in &package_metadata {
+        let keys: Vec<String> = if let Some(rel) = preserved_rel.get(name) {
+            rel.require.keys().cloned().collect()
+        } else {
+            pv.require.keys().cloned().collect()
+        };
+        requires_by_name.insert(name.to_lowercase(), keys);
+    }
     let dev_only = classify_dev_packages(
         &real_owned,
         &request.composer_json.require,
         &request.composer_json.require_dev,
-        &package_metadata,
+        &requires_by_name,
     );
 
     // 3. Build LockedPackage lists.
@@ -825,6 +899,18 @@ pub async fn generate_lock_file(request: &LockFileGenerationRequest) -> anyhow::
     for pkg in &real_resolved {
         let pv = &package_metadata[&pkg.name];
         let mut locked = packagist_version_to_locked_package(&pkg.name, pv);
+        // Overlay relationship fields from the previous lock when applicable
+        // — the resolver's transaction-time view came from the lock, so the
+        // new lock should mirror those relationships even if the upstream
+        // metadata has drifted.
+        if let Some(rel) = preserved_rel.get(&pkg.name) {
+            locked.require = rel.require.clone();
+            locked.require_dev = rel.require_dev.clone();
+            locked.conflict = rel.conflict.clone();
+            locked.provide = rel.provide.clone();
+            locked.replace = rel.replace.clone();
+            locked.suggest = rel.suggest.clone();
+        }
         if let Some(reference) = root_references.get(&pkg.name.to_lowercase()) {
             apply_reference_override(&mut locked, reference);
         }
@@ -1250,7 +1336,11 @@ mod tests {
             make_packagist_version("1.0.0", "1.0.0.0", BTreeMap::new()),
         );
 
-        let dev_only = classify_dev_packages(&resolved, &require, &require_dev, &metadata);
+        let requires_by_name: IndexMap<String, Vec<String>> = metadata
+            .iter()
+            .map(|(name, pv)| (name.to_lowercase(), pv.require.keys().cloned().collect()))
+            .collect();
+        let dev_only = classify_dev_packages(&resolved, &require, &require_dev, &requires_by_name);
 
         assert!(!dev_only.contains("vendor/a"), "A is a production package");
         assert!(dev_only.contains("vendor/b"), "B is dev-only");
@@ -1322,7 +1412,11 @@ mod tests {
             make_packagist_version("1.0.0", "1.0.0.0", BTreeMap::new()),
         );
 
-        let dev_only = classify_dev_packages(&resolved, &require, &require_dev, &metadata);
+        let requires_by_name: IndexMap<String, Vec<String>> = metadata
+            .iter()
+            .map(|(name, pv)| (name.to_lowercase(), pv.require.keys().cloned().collect()))
+            .collect();
+        let dev_only = classify_dev_packages(&resolved, &require, &require_dev, &requires_by_name);
 
         assert!(!dev_only.contains("vendor/a"), "A is a production package");
         assert!(dev_only.contains("vendor/b"), "B is dev-only");
@@ -1386,6 +1480,7 @@ mod tests {
             repositories: std::sync::Arc::new(RepositorySet::with_packagist(
                 crate::cache::Cache::new(std::env::temp_dir().join("mozart-test-cache"), false),
             )),
+            previous_lock: None,
         };
 
         let lock = generate_lock_file(&request).await.unwrap();
@@ -1529,6 +1624,7 @@ mod tests {
                 std::env::temp_dir().join("mozart-test-cache"),
                 false,
             ))),
+            previous_lock: None,
         };
 
         let lock = generate_lock_file(&gen_request)
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);
             }
         }
diff --git a/crates/mozart/src/commands/create_project.rs b/crates/mozart/src/commands/create_project.rs
index 13a2bb2..fc0efee 100644
--- a/crates/mozart/src/commands/create_project.rs
+++ b/crates/mozart/src/commands/create_project.rs
@@ -464,6 +464,7 @@ pub async fn execute(
         repositories: std::sync::Arc::new(
             mozart_registry::repository::RepositorySet::with_packagist(repo_cache.clone()),
         ),
+        previous_lock: None,
     })
     .await?;
 
diff --git a/crates/mozart/src/commands/install.rs b/crates/mozart/src/commands/install.rs
index 58a01b4..017c08e 100644
--- a/crates/mozart/src/commands/install.rs
+++ b/crates/mozart/src/commands/install.rs
@@ -206,12 +206,19 @@ pub fn compute_operations<'a>(
         ops.push((pkg, action));
     }
 
-    // Compute removals: packages in installed but not in locked
+    // Compute removals: packages in installed but not in locked. Iterate
+    // installed.json in reverse, mirroring Composer's
+    // `Transaction::calculateOperations`, which seeds `removeMap` from
+    // `presentPackages` in order and then `array_unshift`s each entry onto
+    // `operations` — flipping the iteration order. Without the flip, two
+    // co-orphaned packages emit removals in the wrong order vs Composer's
+    // trace.
     let locked_names: IndexSet<String> = locked.iter().map(|p| p.name.to_lowercase()).collect();
 
     let removals: Vec<String> = installed
         .packages
         .iter()
+        .rev()
         .filter(|p| !locked_names.contains(&p.name.to_lowercase()))
         .map(|p| p.name.clone())
         .collect();
diff --git a/crates/mozart/src/commands/remove.rs b/crates/mozart/src/commands/remove.rs
index 3ffe04a..eb6ee4a 100644
--- a/crates/mozart/src/commands/remove.rs
+++ b/crates/mozart/src/commands/remove.rs
@@ -376,6 +376,7 @@ pub async fn execute(
         repositories: std::sync::Arc::new(
             mozart_registry::repository::RepositorySet::with_packagist(repo_cache.clone()),
         ),
+        previous_lock: old_lock.clone(),
     })
     .await?;
 
@@ -619,6 +620,7 @@ async fn remove_unused(
         repositories: std::sync::Arc::new(
             mozart_registry::repository::RepositorySet::with_packagist(repo_cache.clone()),
         ),
+        previous_lock: Some(old_lock.clone()),
     })
     .await?;
 
@@ -934,6 +936,7 @@ mod tests {
                     ),
                 ),
             ),
+            previous_lock: None,
         })
         .await
         .expect("initial lock file generation should succeed");
@@ -994,6 +997,7 @@ mod tests {
                     ),
                 ),
             ),
+            previous_lock: Some(initial_lock.clone()),
         })
         .await
         .expect("post-remove lock file generation should succeed");
diff --git a/crates/mozart/src/commands/require.rs b/crates/mozart/src/commands/require.rs
index 45ad759..110bd1a 100644
--- a/crates/mozart/src/commands/require.rs
+++ b/crates/mozart/src/commands/require.rs
@@ -765,6 +765,7 @@ pub async fn execute(
         repositories: std::sync::Arc::new(
             mozart_registry::repository::RepositorySet::with_packagist(repo_cache.clone()),
         ),
+        previous_lock: old_lock.clone(),
     })
     .await?;
 
@@ -1095,6 +1096,7 @@ mod tests {
                     ),
                 ),
             ),
+            previous_lock: None,
         })
         .await
         .expect("Lock file generation should succeed");
@@ -1168,6 +1170,7 @@ mod tests {
                     ),
                 ),
             ),
+            previous_lock: None,
         })
         .await
         .expect("Lock file generation should succeed");
diff --git a/crates/mozart/src/commands/update.rs b/crates/mozart/src/commands/update.rs
index 5cf05c4..43825f2 100644
--- a/crates/mozart/src/commands/update.rs
+++ b/crates/mozart/src/commands/update.rs
@@ -1290,6 +1290,7 @@ pub async fn run(
         composer_json: composer_json.clone(),
         include_dev: dev_mode,
         repositories: repositories.clone(),
+        previous_lock: old_lock.clone(),
     })
     .await?;
 
@@ -2285,6 +2286,7 @@ mod tests {
                     ),
                 ),
             ),
+            previous_lock: None,
         })
         .await
         .expect("Lock file generation should succeed");
diff --git a/crates/mozart/tests/installer.rs b/crates/mozart/tests/installer.rs
index f6324b6..06c7581 100644
--- a/crates/mozart/tests/installer.rs
+++ b/crates/mozart/tests/installer.rs
@@ -373,10 +373,7 @@ installer_fixture!(update_allow_list_with_dependencies_alias, ignore);
 installer_fixture!(update_allow_list_with_dependencies_new_requirement);
 installer_fixture!(update_allow_list_with_dependencies_require_new);
 installer_fixture!(update_allow_list_with_dependencies_require_new_replace);
-installer_fixture!(
-    update_allow_list_with_dependencies_require_new_replace_mutual,
-    ignore
-);
+installer_fixture!(update_allow_list_with_dependencies_require_new_replace_mutual);
 installer_fixture!(update_allow_list_with_dependency_conflict);
 installer_fixture!(update_changes_url, ignore);
 installer_fixture!(update_dev_ignores_providers);
@@ -403,7 +400,7 @@ installer_fixture!(update_picks_up_change_of_vcs_type);
 installer_fixture!(update_prefer_lowest_stable);
 installer_fixture!(update_reference);
 installer_fixture!(update_reference_picks_latest);
-installer_fixture!(update_removes_unused_locked_dep, ignore);
+installer_fixture!(update_removes_unused_locked_dep);
 installer_fixture!(update_requiring_decision_reverts_and_learning_positive_literals);
 installer_fixture!(update_security_advisory_matching_direct_dependency, ignore);
 installer_fixture!(