fix: non-deterministic chunk generation (#8882)

sapphi-red · sapphi-red · commit efad9757065a · 2026-03-24T03:46:56.000Z
I told claude to investigate the reason of #8834 (comment) and it suggested this change. <details> ``` Root Cause Analysis: Non-deterministic /* empty css */ placement The Observed Problem The /* empty css */ comment (which replaces imports to pure CSS chunks) appears in the entry chunk on local (Windows) but in the non-entry chunk on CI (Linux). This means the cross-chunk import for the CSS chunk is assigned to different chunks across platforms. Primary Root Cause: FxHashMap iteration order in Rolldown's chunk optimizer There are three interacting sources of non-determinism in Rolldown, all involving FxHashMap / FxHashSet iteration where order matters: 1. chunk_optimizer.rs:98 — Non-deterministic bits_to_chunk_idx ordering // crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs:98 bits_to_chunk_idx: bits_to_chunk_idx.iter().map(|(k, v)| (k.clone(), *v)).collect(), An FxHashMap<BitSet, ChunkIdx> is iterated and collected into an FxIndexMap. Since FxHashMap iteration order is unspecified, the resulting FxIndexMap preserves a platform-dependent insertion order. 2. chunk_optimizer.rs:344-400 — Stateful sequential assignment with non-deterministic input // Line 344-366: First pass collects assignments in non-deterministic order let assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter() .filter_map(|(bits, temp_chunk_idx)| { ... }) .collect(); // Line 368-400: Second pass applies assignments SEQUENTIALLY for (bits, temp_chunk_idx, chunk_idxs, merge_target) in assignments { // Circular dependency check depends on PREVIOUS merges let merge_target = match merge_target { Some(target) if temp_chunk_graph.would_create_circular_dependency(...) => None, other => other, }; // merge_chunk_dependencies MODIFIES state for subsequent iterations temp_chunk_graph.merge_chunk_dependencies(target_chunk_idx, temp_chunk_idx); } The first pass iterates the non-deterministically-ordered FxIndexMap. The second pass applies assignments sequentially, where each merge modifies the dependency graph (merge_chunk_dependencies), affecting circular dependency checks for later iterations. Different iteration orders → different merge decisions → different chunk structures. 3. compute_cross_chunk_links.rs:262-264 — Non-deterministic symbol ordering // crates/rolldown/src/stages/generate_stage/compute_cross_chunk_links.rs:262 for export_ref in entry_meta.resolved_exports.values() // FxHashMap iteration! .filter(|resolved_export| !resolved_export.came_from_cjs) { depended_symbols.insert(symbols.canonical_ref_resolving_namespace(export_ref.symbol_ref)); } resolved_exports is an FxHashMap. Its iteration order feeds into depended_symbols (FxIndexSet), which maintains insertion order. This non-deterministic ordering affects which symbols are processed first when computing cross-chunk imports (line 429). Why It Differs Between Local and CI FxHasher is deterministic for the same key bytes, but the HashMap's bucket layout depends on the hash values and the capacity/resize patterns. On Windows vs Linux: - Module indices (ModuleIdx) may be assigned in slightly different order due to platform-specific path normalization or parallel module resolution - This causes BitSet keys to have different bit patterns → different hash values → different bucket assignments → different iteration order - This cascades through the chunk optimizer, causing different merge decisions Recommended Fix (in Rolldown) Fix 1 — Sort bits_to_chunk_idx deterministically before processing (chunk_optimizer.rs:344): let mut assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter() .filter_map(...) .collect(); assignments.sort_by_key(|(bits, _, _, _)| bits.clone()); // deterministic sort Fix 2 — Sort resolved_exports before iterating (compute_cross_chunk_links.rs:262): for export_ref in entry_meta.resolved_exports.iter() .sorted_by_key(|(name, _)| name.clone()) // sort by export name .map(|(_, v)| v) .filter(...) Fix 3 — Add secondary sort key in Modules::from() (output_chunk.rs:42): kvs.sort_by(|a, b| { a.1.exec_order.cmp(&b.1.exec_order) .then_with(|| a.0.cmp(&b.0)) // secondary sort by module ID }); The most impactful fix is Fix 1, as it directly controls how common chunks are merged or created, which determines the overall chunk structure. ``` </details> While this didn't fix the output for #8834 (comment), I think the fix itself makes sense.
diff --git a/crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs b/crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs
@@ -93,12 +93,12 @@ impl ChunkOptimizationGraph {
         }
       })
       .collect();
-    Self {
-      chunks,
-      bits_to_chunk_idx: bits_to_chunk_idx.iter().map(|(k, v)| (k.clone(), *v)).collect(),
-      module_to_chunk,
-      chunk_idx_to_temp_chunk_idx,
-    }
+
+    let mut bits_to_chunk_idx: FxIndexMap<_, _> =
+      bits_to_chunk_idx.iter().map(|(k, v)| (k.clone(), *v)).collect();
+    bits_to_chunk_idx.sort_unstable_keys();
+
+    Self { chunks, bits_to_chunk_idx, module_to_chunk, chunk_idx_to_temp_chunk_idx }
   }
 
   /// Assigns a module to a temporary chunk based on its reachability bits.
diff --git a/crates/rolldown/src/stages/generate_stage/compute_cross_chunk_links.rs b/crates/rolldown/src/stages/generate_stage/compute_cross_chunk_links.rs
@@ -261,7 +261,9 @@ impl GenerateStage<'_> {
           if !matches!(entry_meta.wrap_kind(), WrapKind::Cjs) {
             for export_ref in entry_meta
               .resolved_exports
-              .values()
+              .iter()
+              .sorted_by_key(|(name, _)| *name)
+              .map(|(_, export)| export)
               // A chunk should always consume a cjs export symbol by property access, so filter
               // out a exported symbol that came from a cjs module.
               .filter(|resolved_export| !resolved_export.came_from_cjs)
