Function build_sharing_vec

crates/ixon/src/sharing.rs:632–676

Rewrite expressions to use Share(idx) references for shared subterms. Returns the rewritten expressions and the sharing vector.

(
  exprs: &[Arc<Expr>],
  shared_hashes: &IndexSet<blake3::Hash>,
  ptr_to_hash: &FxHashMap<*const Expr, blake3::Hash>,
  info_map: &HashMap<blake3::Hash, SubtermInfo>,
  topo_order: &[blake3::Hash],

/// Rewrite expressions to use Share(idx) references for shared subterms.
///
/// Returns the rewritten expressions and the sharing vector.
pub fn build_sharing_vec(
  exprs: &[Arc<Expr>],
  shared_hashes: &IndexSet<blake3::Hash>,
  ptr_to_hash: &FxHashMap<*const Expr, blake3::Hash>,
  info_map: &FxHashMap<blake3::Hash, SubtermInfo>,
  topo_order: &[blake3::Hash],
) -> (Vec<Arc<Expr>>, Vec<Arc<Expr>>) {
  // CRITICAL: Re-sort shared_hashes in topological order (leaves first).
  // decide_sharing returns hashes sorted by gross benefit (large terms first),
  // but we need leaves first so that when serializing sharing[i], all its
  // children are already available as Share(j) for j < i.
  let shared_in_topo_order: Vec<blake3::Hash> =
    topo_order.iter().copied().filter(|h| shared_hashes.contains(h)).collect();

  // Build sharing vector incrementally to avoid forward references.
  // When building sharing[i], only Share(j) for j < i is allowed.
  let mut sharing_vec: Vec<Arc<Expr>> = Vec::with_capacity(shared_hashes.len());
  let mut hash_to_idx: FxHashMap<blake3::Hash, u64> = FxHashMap::default();
  let mut cache: FxHashMap<*const Expr, Arc<Expr>> = FxHashMap::default();

  for h in &shared_in_topo_order {
    let info = info_map.get(h).expect("shared hash must be in info_map");
    // No cache.clear() needed: rewrite_expr checks hash_to_idx BEFORE the
    // cache, so newly-shareable expressions are always caught even if the
    // cache has a stale entry from a prior iteration. Topological order
    // guarantees all children of `h` were already added to hash_to_idx,
    // so their cached rewrites (containing correct Share references) remain
    // valid.
    let rewritten =
      rewrite_expr(&info.expr, &hash_to_idx, ptr_to_hash, &mut cache);

    let idx = sharing_vec.len() as u64;
    sharing_vec.push(rewritten);
    // Now add this hash to the map for subsequent entries
    hash_to_idx.insert(*h, idx);
  }

  // Rewrite the root expressions (can use all Share indices)
  let rewritten_exprs: Vec<Arc<Expr>> = exprs
    .iter()
    .map(|e| rewrite_expr(e, &hash_to_idx, ptr_to_hash, &mut cache))
    .collect();

  (rewritten_exprs, sharing_vec)
}

/// Frame for iterative rewrite traversal.