Function topological_sort

crates/ixon/src/sharing.rs:343–388

Topological sort of subterms (leaves first, parents last). CRITICAL: Keys are sorted by hash bytes for deterministic output. This ensures Lean and Rust produce the same topological order.

(
  info_map: &HashMap<blake3::Hash, SubtermInfo>,
)

/// Topological sort of subterms (leaves first, parents last).
/// CRITICAL: Keys are sorted by hash bytes for deterministic output.
/// This ensures Lean and Rust produce the same topological order.
pub fn topological_sort(
  info_map: &FxHashMap<blake3::Hash, SubtermInfo>,
) -> Vec<blake3::Hash> {
  #[derive(Clone, Copy, PartialEq, Eq)]
  enum VisitState {
    InProgress,
    Done,
  }

  let mut state: FxHashMap<blake3::Hash, VisitState> = FxHashMap::default();
  let mut result: Vec<blake3::Hash> = Vec::new();

  fn visit(
    hash: blake3::Hash,
    info_map: &FxHashMap<blake3::Hash, SubtermInfo>,
    state: &mut FxHashMap<blake3::Hash, VisitState>,
    result: &mut Vec<blake3::Hash>,
  ) {
    match state.get(&hash) {
      Some(VisitState::Done) => return,
      Some(VisitState::InProgress) => return, // Cycle (shouldn't happen)
      _ => {},
    }

    state.insert(hash, VisitState::InProgress);

    if let Some(info) = info_map.get(&hash) {
      for child in &info.children {
        visit(*child, info_map, state, result);
      }
    }

    state.insert(hash, VisitState::Done);
    result.push(hash);
  }

  // Sort keys deterministically by hash bytes (lexicographic comparison)
  let mut sorted_keys: Vec<blake3::Hash> = info_map.keys().cloned().collect();
  sorted_keys.sort_by_key(|h| *h.as_bytes());

  for hash in sorted_keys {
    visit(hash, info_map, &mut state, &mut result);
  }

  result
}

/// Compute effective sizes for all subterms in topological order.