fix(installer): match Composer's transaction order and uninstall label

Three coupled changes that bring `compute_operations` + the in-process
trace recorder into byte-parity with Composer's `Transaction::__toString`
output:

- `TraceRecorderExecutor`: emit "Removing X (V)" instead of "Uninstalling
  X (V)" — Composer's `UninstallOperation::__toString` uses "Removing".
- `install_from_lock`: run removals before installs/updates to mirror
  `Transaction::moveUninstallsToFront`. Both dry-run and real-execution
  branches now emit the same prefix order.
- `topological_sort`: replace recursive DFS with the stack-based DFS that
  Composer uses in `Transaction::calculateOperations`. Roots are seeded
  reverse-alphabetically (matching `setResultPackageMaps`'s uasort with
  `strcmp(b, a)`), and `getProvidersInResult` is mirrored by treating a
  package's `provide`/`replace` keys as additional name targets when
  resolving a `require` link.

To make the third change work end-to-end, `LockedPackage` gains typed
`provide` and `replace` fields (Composer's lock preserves them; Mozart
was silently dropping them). `packagist_version_to_locked_package` now
copies them through.

Unignores 13 installer fixtures (10 newly green from the fix, 3 that
were already green-but-still-flagged): conflict_downgrade_nested,
install_from_lock_removes_package, install_security_advisory_matching_dependency,
load_replaced_package_if_replacer_dropped, partial_update_keeps_older_dep_*
(×2), partial_update_security_advisory_matching_locked_dep,
provider_packages_can_be_installed_together_with_provided_if_both_installable,
remove_deletes_unused_deps, replace_priorities,
update_allow_list_require_new_replace,
update_allow_list_with_dependencies_require_new_replace,
update_requiring_decision_reverts_and_learning_positive_literals.

Installer scoreboard: 75/187 → 88/187.

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

11 files changed, 134 insertions, 63 deletions

diff --git a/crates/mozart/src/commands/audit.rs b/crates/mozart/src/commands/audit.rs
index 013e0c7..9cbff31 100644
--- a/crates/mozart/src/commands/audit.rs
+++ b/crates/mozart/src/commands/audit.rs
@@ -972,6 +972,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
@@ -1026,6 +1028,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
@@ -1049,6 +1053,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
diff --git a/crates/mozart/src/commands/browse.rs b/crates/mozart/src/commands/browse.rs
index 768c53c..24fc46f 100644
--- a/crates/mozart/src/commands/browse.rs
+++ b/crates/mozart/src/commands/browse.rs
@@ -329,6 +329,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: None,
             autoload: None,
diff --git a/crates/mozart/src/commands/bump.rs b/crates/mozart/src/commands/bump.rs
index 957120d..60b055f 100644
--- a/crates/mozart/src/commands/bump.rs
+++ b/crates/mozart/src/commands/bump.rs
@@ -353,6 +353,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: None,
             autoload: None,
diff --git a/crates/mozart/src/commands/fund.rs b/crates/mozart/src/commands/fund.rs
index 0440c9e..1cd78b7 100644
--- a/crates/mozart/src/commands/fund.rs
+++ b/crates/mozart/src/commands/fund.rs
@@ -408,6 +408,8 @@ mod tests {
                     require: BTreeMap::new(),
                     require_dev: BTreeMap::new(),
                     conflict: BTreeMap::new(),
+                    provide: BTreeMap::new(),
+                    replace: BTreeMap::new(),
                     suggest: None,
                     package_type: None,
                     autoload: None,
@@ -434,6 +436,8 @@ mod tests {
                     require: BTreeMap::new(),
                     require_dev: BTreeMap::new(),
                     conflict: BTreeMap::new(),
+                    provide: BTreeMap::new(),
+                    replace: BTreeMap::new(),
                     suggest: None,
                     package_type: None,
                     autoload: None,
@@ -544,6 +548,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
diff --git a/crates/mozart/src/commands/install.rs b/crates/mozart/src/commands/install.rs
index dbfeb92..356d622 100644
--- a/crates/mozart/src/commands/install.rs
+++ b/crates/mozart/src/commands/install.rs
@@ -211,65 +211,105 @@ pub fn compute_operations<'a>(
 }
 
 /// Order a slice of locked packages so every package's `require` deps that
-/// are present in the same slice come before it. Cycles fall back to the
-/// input order (Composer rejects cycles earlier in the resolver, so Mozart
-/// shouldn't see them here in practice). Mirrors the topological sort
-/// inside `Composer\DependencyResolver\Transaction::calculateOperations`.
+/// are present in the same slice come before it. Mirrors
+/// `Composer\DependencyResolver\Transaction::calculateOperations` — the
+/// stack-based DFS over the result map.
+///
+/// Three parity points worth keeping in sync with Composer:
+///
+/// - The result map is uasort-ed with `strcmp($b, $a)` (reverse alphabetical).
+///   Mozart's lock is alphabetical, so we pre-sort reverse to match.
+/// - `getProvidersInResult` returns every package in the result whose name
+///   *or* `provide`/`replace` entry matches a `require` link target. We
+///   build a multimap keyed by all three so a `require: x/y` push covers
+///   all packages that resolve `x/y`.
+/// - The DFS uses an explicit LIFO stack (Composer's `array_pop`). On first
+///   visit the package is re-pushed and its requires are pushed afterwards,
+///   so dep traversal order is the **reverse** of `getRequires` iteration.
+///
+/// Cycles fall back to input order (Composer rejects cycles earlier; this
+/// branch should not normally fire).
 fn topological_sort<'a>(
     packages: &[&'a lockfile::LockedPackage],
 ) -> Vec<&'a lockfile::LockedPackage> {
     use std::collections::BTreeMap;
 
-    let names: HashSet<String> = packages.iter().map(|p| p.name.to_lowercase()).collect();
-    let mut by_name: BTreeMap<String, &'a lockfile::LockedPackage> = BTreeMap::new();
-    for pkg in packages {
-        by_name.insert(pkg.name.to_lowercase(), *pkg);
+    // Reverse-alphabetical sort, mirroring `setResultPackageMaps`.
+    let mut sorted: Vec<&'a lockfile::LockedPackage> = packages.to_vec();
+    sorted.sort_by_key(|p| std::cmp::Reverse(p.name.to_lowercase()));
+
+    // Multimap: `name -> [packages]`. A package contributes itself under its
+    // own name *and* under every `provide`/`replace` entry. The vec values
+    // stay in `sorted` (reverse-alphabetical) order, mirroring Composer's
+    // `resultPackagesByName` after its uasort.
+    let mut resolves: BTreeMap<String, Vec<&'a lockfile::LockedPackage>> = BTreeMap::new();
+    for pkg in &sorted {
+        let names = std::iter::once(pkg.name.to_lowercase())
+            .chain(pkg.provide.keys().map(|s| s.to_lowercase()))
+            .chain(pkg.replace.keys().map(|s| s.to_lowercase()));
+        for n in names {
+            resolves.entry(n).or_default().push(*pkg);
+        }
+    }
+
+    // Identify root packages: those not pulled in by any other package's
+    // requires (counting provides/replaces as a match).
+    let mut required_by_others: HashSet<String> = HashSet::new();
+    for pkg in &sorted {
+        let pkg_lower = pkg.name.to_lowercase();
+        for dep in pkg.require.keys() {
+            let dep_lower = dep.to_lowercase();
+            if let Some(matches) = resolves.get(&dep_lower) {
+                for &m in matches {
+                    let m_lower = m.name.to_lowercase();
+                    if m_lower != pkg_lower {
+                        required_by_others.insert(m_lower);
+                    }
+                }
+            }
+        }
     }
 
+    let mut stack: Vec<&'a lockfile::LockedPackage> = sorted
+        .iter()
+        .filter(|p| !required_by_others.contains(&p.name.to_lowercase()))
+        .copied()
+        .collect();
+
     let mut visited: HashSet<String> = HashSet::new();
-    let mut on_stack: HashSet<String> = HashSet::new();
+    let mut processed: HashSet<String> = HashSet::new();
     let mut ordered: Vec<&'a lockfile::LockedPackage> = Vec::with_capacity(packages.len());
 
-    fn visit<'b>(
-        name: &str,
-        names: &HashSet<String>,
-        by_name: &BTreeMap<String, &'b lockfile::LockedPackage>,
-        visited: &mut HashSet<String>,
-        on_stack: &mut HashSet<String>,
-        ordered: &mut Vec<&'b lockfile::LockedPackage>,
-    ) {
-        if visited.contains(name) || on_stack.contains(name) {
-            return;
+    while let Some(pkg) = stack.pop() {
+        let lower = pkg.name.to_lowercase();
+        if processed.contains(&lower) {
+            continue;
         }
-        let Some(pkg) = by_name.get(name) else {
-            return;
-        };
-        on_stack.insert(name.to_string());
-        for dep in pkg.require.keys() {
-            let dep_lower = dep.to_lowercase();
-            if names.contains(&dep_lower) {
-                visit(&dep_lower, names, by_name, visited, on_stack, ordered);
+        if !visited.contains(&lower) {
+            visited.insert(lower);
+            // Re-push self so it's processed after its requires drain.
+            stack.push(pkg);
+            for dep in pkg.require.keys() {
+                let dep_lower = dep.to_lowercase();
+                if let Some(matches) = resolves.get(&dep_lower) {
+                    for &m in matches {
+                        stack.push(m);
+                    }
+                }
             }
+        } else {
+            processed.insert(lower);
+            ordered.push(pkg);
         }
-        on_stack.remove(name);
-        visited.insert(name.to_string());
-        ordered.push(*pkg);
     }
 
-    // Seed iteration in the input order so two packages with no relation
-    // come out in the order Mozart's lock writer produced them
-    // (alphabetical), matching Composer's deterministic output.
+    // Cycle / disconnected fallback: append any leftover packages in the
+    // input order so the function is total.
     for pkg in packages {
         let lower = pkg.name.to_lowercase();
-        if !visited.contains(&lower) {
-            visit(
-                &lower,
-                &names,
-                &by_name,
-                &mut visited,
-                &mut on_stack,
-                &mut ordered,
-            );
+        if !processed.contains(&lower) {
+            processed.insert(lower);
+            ordered.push(*pkg);
         }
     }
 
@@ -550,8 +590,12 @@ pub async fn install_from_lock(
         ));
     }
 
-    // Step 6: Execute operations (unless dry_run)
+    // Step 6: Execute operations (unless dry_run). Removals run first to
+    // mirror Composer's `Transaction::moveUninstallsToFront`.
     if config.dry_run {
+        for name in &removals {
+            console.info(&console_format!("  - Would remove <info>{}</info>", name));
+        }
         for (pkg, action) in &ops {
             match action {
                 Action::Skip => {}
@@ -571,9 +615,6 @@ pub async fn install_from_lock(
                 }
             }
         }
-        for name in &removals {
-            console.info(&console_format!("  - Would remove <info>{}</info>", name));
-        }
     } else {
         let exec_ctx = ExecuteContext {
             vendor_dir: vendor_dir.to_path_buf(),
@@ -581,6 +622,21 @@ pub async fn install_from_lock(
             prefer_source: config.prefer_source,
         };
 
+        for name in &removals {
+            console.info(&console_format!("  - Removing <info>{}</info>", name));
+            let from_version = installed
+                .packages
+                .iter()
+                .find(|p| p.name.eq_ignore_ascii_case(name))
+                .map(|p| p.version.as_str())
+                .unwrap_or("");
+            executor.uninstall_package(name, from_version, &exec_ctx)?;
+        }
+
+        if !removals.is_empty() {
+            executor.cleanup_after_uninstalls(&exec_ctx)?;
+        }
+
         for (pkg, action) in &ops {
             let op = match action {
                 Action::Skip => continue,
@@ -616,23 +672,6 @@ pub async fn install_from_lock(
             executor.install_package(op, &exec_ctx).await?;
         }
 
-        // Handle removals
-        for name in &removals {
-            console.info(&console_format!("  - Removing <info>{}</info>", name));
-            let from_version = installed
-                .packages
-                .iter()
-                .find(|p| p.name.eq_ignore_ascii_case(name))
-                .map(|p| p.version.as_str())
-                .unwrap_or("");
-            executor.uninstall_package(name, from_version, &exec_ctx)?;
-        }
-
-        // Step 7: Clean up empty vendor namespace directories
-        if !removals.is_empty() {
-            executor.cleanup_after_uninstalls(&exec_ctx)?;
-        }
-
         // Step 8: Write updated vendor/composer/installed.json (unless download_only)
         if !config.download_only {
             let mut new_installed = installed::InstalledPackages::new();
@@ -905,6 +944,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: Some("library".to_string()),
             autoload: None,
diff --git a/crates/mozart/src/commands/licenses.rs b/crates/mozart/src/commands/licenses.rs
index 50aaebe..b066fde 100644
--- a/crates/mozart/src/commands/licenses.rs
+++ b/crates/mozart/src/commands/licenses.rs
@@ -623,6 +623,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
@@ -646,6 +648,8 @@ mod tests {
                 require: BTreeMap::new(),
                 require_dev: BTreeMap::new(),
                 conflict: BTreeMap::new(),
+                provide: BTreeMap::new(),
+                replace: BTreeMap::new(),
                 suggest: None,
                 package_type: None,
                 autoload: None,
diff --git a/crates/mozart/src/commands/reinstall.rs b/crates/mozart/src/commands/reinstall.rs
index 508915a..c19d926 100644
--- a/crates/mozart/src/commands/reinstall.rs
+++ b/crates/mozart/src/commands/reinstall.rs
@@ -444,6 +444,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: Some("library".to_string()),
             autoload: None,
diff --git a/crates/mozart/src/commands/remove.rs b/crates/mozart/src/commands/remove.rs
index e499af0..58917e9 100644
--- a/crates/mozart/src/commands/remove.rs
+++ b/crates/mozart/src/commands/remove.rs
@@ -634,6 +634,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: Some("library".to_string()),
             autoload: None,
diff --git a/crates/mozart/src/commands/require.rs b/crates/mozart/src/commands/require.rs
index 50aa29f..630d960 100644
--- a/crates/mozart/src/commands/require.rs
+++ b/crates/mozart/src/commands/require.rs
@@ -897,6 +897,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: Some("library".to_string()),
             autoload: None,
diff --git a/crates/mozart/src/commands/suggests.rs b/crates/mozart/src/commands/suggests.rs
index 9a43211..394778f 100644
--- a/crates/mozart/src/commands/suggests.rs
+++ b/crates/mozart/src/commands/suggests.rs
@@ -532,6 +532,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest,
             package_type: None,
             autoload: None,
diff --git a/crates/mozart/src/commands/update.rs b/crates/mozart/src/commands/update.rs
index b4a3246..9ac2664 100644
--- a/crates/mozart/src/commands/update.rs
+++ b/crates/mozart/src/commands/update.rs
@@ -1329,6 +1329,8 @@ mod tests {
             require: BTreeMap::new(),
             require_dev: BTreeMap::new(),
             conflict: BTreeMap::new(),
+            provide: BTreeMap::new(),
+            replace: BTreeMap::new(),
             suggest: None,
             package_type: Some("library".to_string()),
             autoload: None,