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>

12 files changed, 80 insertions, 76 deletions

diff --git a/crates/mozart-sat-resolver/Cargo.toml b/crates/mozart-sat-resolver/Cargo.toml
index c02904f..5b8a46c 100644
--- a/crates/mozart-sat-resolver/Cargo.toml
+++ b/crates/mozart-sat-resolver/Cargo.toml
@@ -6,5 +6,6 @@ edition.workspace = true
 [dependencies]
 mozart-semver.workspace = true
 mozart-core.workspace = true
+indexmap.workspace = true
 
 [dev-dependencies]
diff --git a/crates/mozart-sat-resolver/src/decisions.rs b/crates/mozart-sat-resolver/src/decisions.rs
index abfbe3d..e9cc935 100644
--- a/crates/mozart-sat-resolver/src/decisions.rs
+++ b/crates/mozart-sat-resolver/src/decisions.rs
@@ -1,7 +1,7 @@
 use crate::error::SolverBugError;
 use crate::pool::{Literal, PackageId, literal_to_package_id};
 use crate::rule_set::RuleId;
-use std::collections::HashMap;
+use indexmap::IndexMap;
 
 /// A decision entry: which literal was decided and which rule caused it.
 #[derive(Debug, Clone)]
@@ -16,7 +16,7 @@ pub struct Decision {
 pub struct Decisions {
     /// Package ID → signed level. Positive = install, negative = uninstall.
     /// The absolute value is the decision level.
-    decision_map: HashMap<PackageId, i32>,
+    decision_map: IndexMap<PackageId, i32>,
     /// Queue of decisions in order.
     decision_queue: Vec<Decision>,
 }
@@ -24,7 +24,7 @@ pub struct Decisions {
 impl Decisions {
     pub fn new() -> Self {
         Decisions {
-            decision_map: HashMap::new(),
+            decision_map: IndexMap::new(),
             decision_queue: Vec::new(),
         }
     }
diff --git a/crates/mozart-sat-resolver/src/policy.rs b/crates/mozart-sat-resolver/src/policy.rs
index a66719f..a2678d5 100644
--- a/crates/mozart-sat-resolver/src/policy.rs
+++ b/crates/mozart-sat-resolver/src/policy.rs
@@ -1,5 +1,5 @@
 use crate::pool::{Literal, Pool};
-use std::collections::HashMap;
+use indexmap::IndexMap;
 
 /// Version selection policy: decides which version to prefer when multiple
 /// candidates satisfy a requirement.
@@ -35,7 +35,7 @@ impl DefaultPolicy {
         }
 
         // Group literals by package name
-        let mut groups: HashMap<&str, Vec<Literal>> = HashMap::new();
+        let mut groups: IndexMap<&str, Vec<Literal>> = IndexMap::new();
         for &lit in literals {
             let pkg = pool.literal_to_package(lit);
             groups.entry(pkg.name.as_str()).or_default().push(lit);
diff --git a/crates/mozart-sat-resolver/src/pool.rs b/crates/mozart-sat-resolver/src/pool.rs
index 0312c24..9268675 100644
--- a/crates/mozart-sat-resolver/src/pool.rs
+++ b/crates/mozart-sat-resolver/src/pool.rs
@@ -1,5 +1,5 @@
+use indexmap::IndexMap;
 use mozart_semver::VersionConstraint;
-use std::collections::HashMap;
 use std::fmt;
 
 /// Unique identifier for a package in the pool. 1-based.
@@ -122,9 +122,9 @@ pub struct Pool {
     /// All packages, indexed by (id - 1).
     packages: Vec<PoolPackage>,
     /// Index: package name → list of package IDs providing that name.
-    package_by_name: HashMap<String, Vec<PackageId>>,
+    package_by_name: IndexMap<String, Vec<PackageId>>,
     /// Cache for what_provides results.
-    provider_cache: HashMap<(String, String), Vec<PackageId>>,
+    provider_cache: IndexMap<(String, String), Vec<PackageId>>,
     /// Packages that are fixed/locked but unacceptable (e.g. failed stability).
     unacceptable_fixed_packages: Vec<PackageId>,
 }
@@ -133,7 +133,7 @@ impl Pool {
     /// Create a new pool from a list of package inputs.
     pub fn new(inputs: Vec<PoolPackageInput>, unacceptable_fixed_ids: Vec<PackageId>) -> Self {
         let mut packages: Vec<PoolPackage> = Vec::with_capacity(inputs.len());
-        let mut package_by_name: HashMap<String, Vec<PackageId>> = HashMap::new();
+        let mut package_by_name: IndexMap<String, Vec<PackageId>> = IndexMap::new();
         // Collect alias links (alias_idx, target_name, target_normalized) for
         // a second pass once every input has a stable ID.
         let mut pending_aliases: Vec<(usize, String, String)> = Vec::new();
@@ -189,7 +189,7 @@ impl Pool {
         Pool {
             packages,
             package_by_name,
-            provider_cache: HashMap::new(),
+            provider_cache: IndexMap::new(),
             unacceptable_fixed_packages: unacceptable_fixed_ids,
         }
     }
diff --git a/crates/mozart-sat-resolver/src/pool_builder.rs b/crates/mozart-sat-resolver/src/pool_builder.rs
index 83684aa..3883d85 100644
--- a/crates/mozart-sat-resolver/src/pool_builder.rs
+++ b/crates/mozart-sat-resolver/src/pool_builder.rs
@@ -1,5 +1,6 @@
 use crate::pool::{Pool, PoolLink, PoolPackageInput};
-use std::collections::{HashSet, VecDeque};
+use indexmap::IndexSet;
+use std::collections::VecDeque;
 
 /// Builder for constructing a Pool from package metadata.
 ///
@@ -10,13 +11,13 @@ pub struct PoolBuilder {
     /// Packages to add to the pool.
     inputs: Vec<PoolPackageInput>,
     /// Names already added (to avoid duplicates).
-    added: HashSet<String>,
+    added: IndexSet<String>,
     /// Queue of package names that need to be explored.
     pending_names: VecDeque<String>,
     /// Package names that have already been explored (returned by next_pending).
-    explored_names: HashSet<String>,
+    explored_names: IndexSet<String>,
     /// Specific platform packages to ignore (from `--ignore-platform-req=name`).
-    ignore_platform_reqs: HashSet<String>,
+    ignore_platform_reqs: IndexSet<String>,
     /// When true, ignore every platform package (php, ext-*, lib-*, composer-*).
     /// Mirrors `--ignore-platform-reqs` (no value).
     ignore_all_platform_reqs: bool,
@@ -26,16 +27,16 @@ impl PoolBuilder {
     pub fn new() -> Self {
         PoolBuilder {
             inputs: Vec::new(),
-            added: HashSet::new(),
+            added: IndexSet::new(),
             pending_names: VecDeque::new(),
-            explored_names: HashSet::new(),
-            ignore_platform_reqs: HashSet::new(),
+            explored_names: IndexSet::new(),
+            ignore_platform_reqs: IndexSet::new(),
             ignore_all_platform_reqs: false,
         }
     }
 
     /// Set platform requirements to ignore during exploration.
-    pub fn set_ignore_platform_reqs(&mut self, names: HashSet<String>) {
+    pub fn set_ignore_platform_reqs(&mut self, names: IndexSet<String>) {
         self.ignore_platform_reqs = names;
     }
 
diff --git a/crates/mozart-sat-resolver/src/problem.rs b/crates/mozart-sat-resolver/src/problem.rs
index c453fa9..a1692fd 100644
--- a/crates/mozart-sat-resolver/src/problem.rs
+++ b/crates/mozart-sat-resolver/src/problem.rs
@@ -75,7 +75,7 @@ impl Problem {
         }
 
         // Deduplicate
-        let mut seen = std::collections::HashSet::new();
+        let mut seen = indexmap::IndexSet::new();
         let mut unique = Vec::new();
         for msg in messages {
             if seen.insert(msg.clone()) {
@@ -367,7 +367,7 @@ fn rule_pretty_string(pool: &Pool, rule: &Rule) -> String {
 /// Similar to Composer's formatPackagesUnique.
 fn format_providers(pool: &Pool, literals: &[Literal]) -> String {
     // Group by package name
-    let mut groups: std::collections::HashMap<&str, Vec<&str>> = std::collections::HashMap::new();
+    let mut groups: indexmap::IndexMap<&str, Vec<&str>> = indexmap::IndexMap::new();
     for &lit in literals {
         let pkg = pool.literal_to_package(lit);
         groups
diff --git a/crates/mozart-sat-resolver/src/request.rs b/crates/mozart-sat-resolver/src/request.rs
index 94891f0..26c17ba 100644
--- a/crates/mozart-sat-resolver/src/request.rs
+++ b/crates/mozart-sat-resolver/src/request.rs
@@ -1,5 +1,5 @@
 use crate::pool::PackageId;
-use std::collections::HashMap;
+use indexmap::IndexMap;
 
 /// A requirement: package name + version constraint string.
 #[derive(Debug, Clone)]
@@ -14,7 +14,7 @@ pub struct Require {
 #[derive(Debug, Clone)]
 pub struct Request {
     /// Root requirements: package name → constraint string.
-    pub requires: HashMap<String, Option<String>>,
+    pub requires: IndexMap<String, Option<String>>,
     /// Fixed packages (must be installed, cannot be modified).
     pub fixed_packages: Vec<PackageId>,
     /// Locked packages (installed but can be removed if nothing requires them).
@@ -24,7 +24,7 @@ pub struct Request {
 impl Request {
     pub fn new() -> Self {
         Request {
-            requires: HashMap::new(),
+            requires: IndexMap::new(),
             fixed_packages: Vec::new(),
             locked_packages: Vec::new(),
         }
diff --git a/crates/mozart-sat-resolver/src/rule_set.rs b/crates/mozart-sat-resolver/src/rule_set.rs
index 4d1a8a6..918bdae 100644
--- a/crates/mozart-sat-resolver/src/rule_set.rs
+++ b/crates/mozart-sat-resolver/src/rule_set.rs
@@ -1,5 +1,5 @@
 use crate::rule::{Rule, RuleType};
-use std::collections::HashMap;
+use indexmap::IndexMap;
 
 /// A unique identifier for a rule within the RuleSet.
 pub type RuleId = usize;
@@ -18,7 +18,7 @@ pub struct RuleSet {
     /// Total rule count.
     next_rule_id: usize,
     /// Deduplication index.
-    rules_by_hash: HashMap<String, Vec<usize>>,
+    rules_by_hash: IndexMap<String, Vec<usize>>,
     /// Maps rule ID → (type, index within type's vec).
     rule_type_index: Vec<(RuleType, usize)>,
 }
@@ -31,7 +31,7 @@ impl RuleSet {
             request_rules: Vec::new(),
             learned_rules: Vec::new(),
             next_rule_id: 0,
-            rules_by_hash: HashMap::new(),
+            rules_by_hash: IndexMap::new(),
             rule_type_index: Vec::new(),
         }
     }
diff --git a/crates/mozart-sat-resolver/src/rule_set_generator.rs b/crates/mozart-sat-resolver/src/rule_set_generator.rs
index 11c04cc..2ab9f86 100644
--- a/crates/mozart-sat-resolver/src/rule_set_generator.rs
+++ b/crates/mozart-sat-resolver/src/rule_set_generator.rs
@@ -1,8 +1,10 @@
 use crate::pool::{Literal, PackageId, Pool, PoolLink};
 use crate::rule::{ReasonData, Rule, RuleReason, RuleType};
 use crate::rule_set::RuleSet;
+use indexmap::IndexMap;
+use indexmap::IndexSet;
 use mozart_semver::VersionConstraint;
-use std::collections::{HashMap, HashSet, VecDeque};
+use std::collections::VecDeque;
 
 /// Generates SAT rules from the pool and request.
 ///
@@ -11,11 +13,11 @@ pub struct RuleSetGenerator<'a> {
     pool: &'a mut Pool,
     rules: RuleSet,
     /// Packages already processed.
-    added_map: HashSet<PackageId>,
+    added_map: IndexSet<PackageId>,
     /// Package names → list of package IDs with that name (non-alias).
-    added_packages_by_name: HashMap<String, Vec<PackageId>>,
+    added_packages_by_name: IndexMap<String, Vec<PackageId>>,
     /// Specific platform packages to ignore (from `--ignore-platform-req=name`).
-    ignore_platform_reqs: HashSet<String>,
+    ignore_platform_reqs: IndexSet<String>,
     /// When true, every platform package is treated as ignored.
     /// Mirrors `--ignore-platform-reqs` (no value).
     ignore_all_platform_reqs: bool,
@@ -26,15 +28,15 @@ impl<'a> RuleSetGenerator<'a> {
         RuleSetGenerator {
             pool,
             rules: RuleSet::new(),
-            added_map: HashSet::new(),
-            added_packages_by_name: HashMap::new(),
-            ignore_platform_reqs: HashSet::new(),
+            added_map: IndexSet::new(),
+            added_packages_by_name: IndexMap::new(),
+            ignore_platform_reqs: IndexSet::new(),
             ignore_all_platform_reqs: false,
         }
     }
 
     /// Set platform requirements to ignore.
-    pub fn set_ignore_platform_reqs(&mut self, names: HashSet<String>) {
+    pub fn set_ignore_platform_reqs(&mut self, names: IndexSet<String>) {
         self.ignore_platform_reqs = names;
     }
 
@@ -76,10 +78,10 @@ impl<'a> RuleSetGenerator<'a> {
     /// unresolvable problem.
     pub fn generate(
         mut self,
-        requires: &HashMap<String, Option<String>>,
+        requires: &IndexMap<String, Option<String>>,
         fixed_packages: &[PackageId],
-        root_provides: &HashMap<String, String>,
-        root_replaces: &HashMap<String, String>,
+        root_provides: &IndexMap<String, String>,
+        root_replaces: &IndexMap<String, String>,
     ) -> (RuleSet, Vec<(String, Option<String>)>) {
         let mut missing_root_requires: Vec<(String, Option<String>)> = Vec::new();
         // Process fixed packages
@@ -351,7 +353,7 @@ impl<'a> RuleSetGenerator<'a> {
 fn root_self_fulfills(
     target: &str,
     require_constraint: Option<&str>,
-    root_links: &HashMap<String, String>,
+    root_links: &IndexMap<String, String>,
 ) -> bool {
     let Some(link_constraint_str) = root_links.get(target) else {
         return false;
@@ -394,11 +396,11 @@ mod tests {
             vec![],
         );
 
-        let mut requires = HashMap::new();
+        let mut requires = IndexMap::new();
         requires.insert("a/a".to_string(), None);
 
         let generator = RuleSetGenerator::new(&mut pool);
-        let (rules, _) = generator.generate(&requires, &[], &HashMap::new(), &HashMap::new());
+        let (rules, _) = generator.generate(&requires, &[], &IndexMap::new(), &IndexMap::new());
 
         // Should have a request rule: (1 | 2)
         let request_count = rules.iter_type(RuleType::Request).count();
@@ -434,11 +436,11 @@ mod tests {
             vec![],
         );
 
-        let mut requires = HashMap::new();
+        let mut requires = IndexMap::new();
         requires.insert("a/a".to_string(), None);
 
         let generator = RuleSetGenerator::new(&mut pool);
-        let (rules, _) = generator.generate(&requires, &[], &HashMap::new(), &HashMap::new());
+        let (rules, _) = generator.generate(&requires, &[], &IndexMap::new(), &IndexMap::new());
 
         // Should have:
         // 1. Request rule: (1) — root requires a/a
@@ -452,7 +454,7 @@ mod tests {
 
         let generator = RuleSetGenerator::new(&mut pool);
         let (rules, _) =
-            generator.generate(&HashMap::new(), &[1], &HashMap::new(), &HashMap::new());
+            generator.generate(&IndexMap::new(), &[1], &IndexMap::new(), &IndexMap::new());
 
         // Should have an assertion rule: (1)
         let request_rules: Vec<_> = rules.iter_type(RuleType::Request).collect();
diff --git a/crates/mozart-sat-resolver/src/rule_watch_graph.rs b/crates/mozart-sat-resolver/src/rule_watch_graph.rs
index 1b7604d..202dcca 100644
--- a/crates/mozart-sat-resolver/src/rule_watch_graph.rs
+++ b/crates/mozart-sat-resolver/src/rule_watch_graph.rs
@@ -2,7 +2,7 @@ use crate::decisions::Decisions;
 use crate::pool::Literal;
 use crate::rule::Rule;
 use crate::rule_set::RuleId;
-use std::collections::HashMap;
+use indexmap::IndexMap;
 
 /// A watch node: tracks which 2 literals a rule watches.
 ///
@@ -24,7 +24,7 @@ struct WatchNode {
 /// Port of Composer's RuleWatchGraph.php.
 pub struct RuleWatchGraph {
     /// Literal → list of watch node indices watching that literal.
-    watch_chains: HashMap<Literal, Vec<usize>>,
+    watch_chains: IndexMap<Literal, Vec<usize>>,
     /// All watch nodes.
     nodes: Vec<WatchNode>,
 }
@@ -32,7 +32,7 @@ pub struct RuleWatchGraph {
 impl RuleWatchGraph {
     pub fn new() -> Self {
         RuleWatchGraph {
-            watch_chains: HashMap::new(),
+            watch_chains: IndexMap::new(),
             nodes: Vec::new(),
         }
     }
diff --git a/crates/mozart-sat-resolver/src/solver.rs b/crates/mozart-sat-resolver/src/solver.rs
index 49a4ce4..8739381 100644
--- a/crates/mozart-sat-resolver/src/solver.rs
+++ b/crates/mozart-sat-resolver/src/solver.rs
@@ -6,7 +6,7 @@ use crate::problem::Problem;
 use crate::rule::{ReasonData, Rule, RuleReason, RuleType};
 use crate::rule_set::{RuleId, RuleSet};
 use crate::rule_watch_graph::RuleWatchGraph;
-use std::collections::{HashMap, HashSet};
+use indexmap::{IndexMap, IndexSet};
 
 /// Result of solving: the list of package IDs to install.
 #[derive(Debug)]
@@ -25,7 +25,7 @@ pub struct Solver<'a> {
     watch_graph: RuleWatchGraph,
     decisions: Decisions,
     /// Fixed packages by ID.
-    fixed_map: HashSet<PackageId>,
+    fixed_map: IndexSet<PackageId>,
     /// Current propagation index in decision queue.
     propagate_index: usize,
     /// Branch points: (alternative literals, decision level).
@@ -35,7 +35,7 @@ pub struct Solver<'a> {
     /// Learned rule pool: for each learned rule, the chain of rules that led to it.
     learned_pool: Vec<Vec<RuleId>>,
     /// Map from rule ID → learned pool index.
-    learned_why: HashMap<RuleId, usize>,
+    learned_why: IndexMap<RuleId, usize>,
 }
 
 impl<'a> Solver<'a> {
@@ -44,7 +44,7 @@ impl<'a> Solver<'a> {
         rules: RuleSet,
         pool: &'a Pool,
         policy: DefaultPolicy,
-        fixed_packages: HashSet<PackageId>,
+        fixed_packages: IndexSet<PackageId>,
     ) -> Self {
         Solver {
             pool,
@@ -57,7 +57,7 @@ impl<'a> Solver<'a> {
             branches: Vec::new(),
             problems: Vec::new(),
             learned_pool: Vec::new(),
-            learned_why: HashMap::new(),
+            learned_why: IndexMap::new(),
         }
     }
 
@@ -333,7 +333,7 @@ impl<'a> Solver<'a> {
         let mut rule_level: i32 = 1;
         let mut num: i32 = 0;
         let mut l1num: i32 = 0;
-        let mut seen: HashSet<PackageId> = HashSet::new();
+        let mut seen: IndexSet<PackageId> = IndexSet::new();
         let mut learned_literal: Option<Literal> = None;
         let mut other_learned_literals: Vec<Literal> = Vec::new();
 
@@ -430,7 +430,7 @@ impl<'a> Solver<'a> {
                 let decision = self.decisions.at_offset(decision_id);
                 let literal = decision.literal;
 
-                seen.remove(&literal_to_package_id(literal));
+                seen.shift_remove(&literal_to_package_id(literal));
 
                 if num != 0 {
                     num -= 1;
@@ -456,7 +456,7 @@ impl<'a> Solver<'a> {
 
                         // Only level 1 marks left
                         for other in &other_learned_literals {
-                            seen.remove(&literal_to_package_id(*other));
+                            seen.shift_remove(&literal_to_package_id(*other));
                         }
                         l1num += 1;
                         l1retry = true;
@@ -504,7 +504,7 @@ impl<'a> Solver<'a> {
         &self,
         problem: &mut Problem,
         conflict_rule_id: RuleId,
-        rule_seen: &mut HashSet<RuleId>,
+        rule_seen: &mut IndexSet<RuleId>,
     ) {
         if rule_seen.contains(&conflict_rule_id) {
             return;
@@ -542,11 +542,11 @@ impl<'a> Solver<'a> {
         let mut problem = Problem::new();
         problem.add_rule(conflict_rule_id);
 
-        let mut rule_seen = HashSet::new();
+        let mut rule_seen = IndexSet::new();
         self.analyze_unsolvable_rule(&mut problem, conflict_rule_id, &mut rule_seen);
 
         // Collect related decisions
-        let mut seen: HashSet<PackageId> = HashSet::new();
+        let mut seen: IndexSet<PackageId> = IndexSet::new();
         let conflict_literals = self.rules.rule_by_id(conflict_rule_id).literals().to_vec();
         for &lit in &conflict_literals {
             if self.decisions.satisfy(lit) {
@@ -835,7 +835,7 @@ mod tests {
     /// Creates a pool with N dummy packages (1..=max_id).
     fn make_rules_and_solve(
         rules: Vec<(Rule, RuleType)>,
-        fixed: HashSet<PackageId>,
+        fixed: IndexSet<PackageId>,
         max_id: u32,
     ) -> Result<SolverResult, SolverError> {
         let mut rs = RuleSet::new();
@@ -859,7 +859,7 @@ mod tests {
                 Rule::new(vec![1], RuleReason::RootRequire, ReasonData::None),
                 RuleType::Request,
             )],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         )
         .unwrap();
@@ -881,7 +881,7 @@ mod tests {
                     RuleType::Request,
                 ),
             ],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         )
         .unwrap();
@@ -907,7 +907,7 @@ mod tests {
                     RuleType::Package,
                 ),
             ],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         )
         .unwrap();
@@ -944,7 +944,7 @@ mod tests {
                     RuleType::Request,
                 ),
             ],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         )
         .unwrap();
@@ -970,7 +970,7 @@ mod tests {
                     RuleType::Package,
                 ),
             ],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         )
         .unwrap();
@@ -999,7 +999,7 @@ mod tests {
                     RuleType::Package,
                 ),
             ],
-            HashSet::new(),
+            IndexSet::new(),
             3,
         );
 
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();