pub fn resolve(profile: &Profile) -> Result<ResolvedLoadOrder>Expand description
Resolve a profile into a topologically sorted load order.
Stability contract: the output preserves profile.mods input order
wherever possible, deviating only when a LoadAfter / LoadBefore
rule would otherwise be violated. This means:
- No rules → exact input order.
resolve(profile).orderequals the enabled subset ofprofile.modsin the same sequence. - Round-trip via swap. Swapping two adjacent mods in
profile.modsproduces a resolved order with those two mods swapped, as long as no rule spans the swap. This is what makesMessage::ReorderModvisible in theload_orderview — without stability, reordering could silently vanish. - Minimal change under rules. When a rule does force movement, only the rule-involved pair shifts; unrelated neighbors stay put.
- Deterministic. Identical inputs always produce identical outputs;
we don’t rely on
HashMapiteration order anywhere.
§Algorithm
Stable Kahn’s with input-position tiebreaking:
- Collect enabled mods, recording each
mod_id → input_pos. - Build adjacency + in-degree from
LoadAfter/LoadBeforerules, silently dropping edges whose endpoints aren’t enabled (matches the old behaviour). - Seed a min-heap (
BinaryHeap<Reverse<(input_pos, mod_id)>>) with every node whose in-degree is 0. - Pop the smallest-input-position ready node, emit it, decrement the in-degree of its successors, pushing any that hit 0.
- If fewer nodes come out than went in, there’s a cycle — pick any
remaining node to name in
CoreError::DependencyCycle.
Incompatible rules are checked up-front and short-circuit the
resolution with a FileConflict error (unchanged from the old impl).