From ae1aa6540761e54a76b8f7984cf93cd3a0d011d0 Mon Sep 17 00:00:00 2001
From: nsfisis <nsfisis@gmail.com>
Date: Sun, 3 May 2026 11:55:03 +0900
Subject: refactor: switch internal maps/sets from HashMap to IndexMap

Adopt indexmap workspace-wide so iteration order is deterministic and
follows insertion order. The non-deterministic order of std HashMap
otherwise leaks into resolver decisions when multiple valid solutions
exist (e.g. cyclic require pairs under prefer-lowest), making behavior
flaky and divergent from Composer's PHP-array semantics.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
---
 crates/mozart-sat-resolver/src/transaction.rs | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

(limited to 'crates/mozart-sat-resolver/src/transaction.rs')

diff --git a/crates/mozart-sat-resolver/src/transaction.rs b/crates/mozart-sat-resolver/src/transaction.rs
index 176b862..de7c9a0 100644
--- a/crates/mozart-sat-resolver/src/transaction.rs
+++ b/crates/mozart-sat-resolver/src/transaction.rs
@@ -1,6 +1,6 @@
 use crate::decisions::Decisions;
 use crate::pool::{PackageId, Pool, literal_to_package_id};
-use std::collections::{HashMap, HashSet};
+use indexmap::{IndexMap, IndexSet};
 
 /// An operation to perform on a package.
 ///
@@ -104,14 +104,14 @@ impl<'a> Transaction<'a> {
     /// Calculate the delta between present and result packages.
     fn calculate_operations(&mut self) {
         // Build maps: name -> package_id for present packages
-        let mut present_by_name: HashMap<&str, PackageId> = HashMap::new();
+        let mut present_by_name: IndexMap<&str, PackageId> = IndexMap::new();
         for &id in &self.present_ids {
             let pkg = self.pool.package_by_id(id);
             present_by_name.insert(&pkg.name, id);
         }
 
         // Track which present packages have been matched
-        let mut matched_present: HashSet<PackageId> = HashSet::new();
+        let mut matched_present: IndexSet<PackageId> = IndexSet::new();
 
         // Build topologically sorted result packages via DFS
         let sorted_results = self.topological_sort();
@@ -158,9 +158,9 @@ 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: HashSet<PackageId> = self.result_ids.iter().copied().collect();
-        let result_by_name: HashMap<&str, Vec<PackageId>> = {
-            let mut map: HashMap<&str, Vec<PackageId>> = HashMap::new();
+        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);
@@ -168,7 +168,7 @@ impl<'a> Transaction<'a> {
             map
         };
 
-        let mut visited: HashSet<PackageId> = HashSet::new();
+        let mut visited: IndexSet<PackageId> = IndexSet::new();
         let mut order: Vec<PackageId> = Vec::new();
 
         // Find root packages (not required by any other result package)
@@ -221,11 +221,11 @@ impl<'a> Transaction<'a> {
     /// Find root packages: result packages not required by any other result package.
     fn get_root_packages(
         &self,
-        result_set: &HashSet<PackageId>,
-        _result_by_name: &HashMap<&str, Vec<PackageId>>,
+        result_set: &IndexSet<PackageId>,
+        _result_by_name: &IndexMap<&str, Vec<PackageId>>,
     ) -> Vec<PackageId> {
         // Collect all required package names
-        let mut required_names: HashSet<&str> = HashSet::new();
+        let mut required_names: IndexSet<&str> = IndexSet::new();
         for &id in result_set {
             let pkg = self.pool.package_by_id(id);
             for req in &pkg.requires {
@@ -270,7 +270,7 @@ impl<'a> LockTransaction<'a> {
     pub fn new(
         pool: &'a Pool,
         present_ids: Vec<PackageId>,
-        unlockable_ids: HashSet<PackageId>,
+        unlockable_ids: IndexSet<PackageId>,
         decisions: &Decisions,
     ) -> Self {
         // Extract result packages from decisions
@@ -300,7 +300,7 @@ impl<'a> LockTransaction<'a> {
     /// Set the non-dev packages from an extraction-only solve result.
     /// `extraction_ids` are the package IDs that were resolved without dev deps.
     pub fn set_non_dev_packages(&mut self, extraction_ids: &[PackageId]) {
-        let extraction_names: HashSet<String> = extraction_ids
+        let extraction_names: IndexSet<String> = extraction_ids
             .iter()
             .map(|&id| self.transaction.pool.package_by_id(id).name.clone())
             .collect();
-- 
cgit v1.3.1