Function analyze_block

crates/ixon/src/sharing.rs:221–329

Analyze expressions for sharing opportunities within a block. Returns a map from content hash to SubtermInfo, and a map from pointer to hash. Uses a two-phase algorithm: 1. Build DAG structure via post-order traversal with Merkle-tree hashing 2. Propagate usage counts structurally from roots to leaves (O(n) total) If `track_hash_consed_size` is true, computes the hash-consed size for each subter

(
  exprs: &[Arc<Expr>],
  track_hash_consed_size: bool,
)

/// subterm (32-byte key + value). This adds overhead and can be disabled when
/// only sharing analysis is needed.
pub fn analyze_block(
  exprs: &[Arc<Expr>],
  track_hash_consed_size: bool,
) -> (
  HashMap<blake3::Hash, SubtermInfo>,
  FxHashMap<*const Expr, blake3::Hash>,
  Vec<blake3::Hash>,
) {
  let mut info_map: HashMap<blake3::Hash, SubtermInfo> = HashMap::new();
  let mut ptr_to_hash: FxHashMap<*const Expr, blake3::Hash> =
    FxHashMap::default();
  let mut hash_buf: Vec<u8> = Vec::with_capacity(128);

  // Phase 1: Build DAG structure via post-order traversal
  // Don't compute usage counts here - just build the hash→children mapping
  enum Frame<'a> {
    Visit(&'a Arc<Expr>),
    Process(&'a Arc<Expr>),
  }

  for root in exprs {
    let mut stack: Vec<Frame<'_>> = vec![Frame::Visit(root)];

    while let Some(frame) = stack.pop() {
      match frame {
        Frame::Visit(arc_expr) => {
          let ptr = arc_expr.as_ref() as *const Expr;

          // Already processed this pointer - just skip
          // Usage counts will be computed in phase 2
          if ptr_to_hash.contains_key(&ptr) {
            continue;
          }

          // Push process frame, then children (in reverse for correct order)
          stack.push(Frame::Process(arc_expr));
          for child in get_children(arc_expr).into_iter().rev() {
            stack.push(Frame::Visit(child));
          }
        },
        Frame::Process(arc_expr) => {
          let ptr = arc_expr.as_ref() as *const Expr;
          if ptr_to_hash.contains_key(&ptr) {
            continue;
          }

          let (hash, children, value_size) =
            hash_node(arc_expr.as_ref(), &ptr_to_hash, &mut hash_buf);

          // Add to ptr_to_hash cache
          ptr_to_hash.insert(ptr, hash);

          // Add to info_map if not already present (same content hash from different pointer)
          info_map.entry(hash).or_insert_with(|| {
            let base_size = compute_base_size(arc_expr.as_ref());
            let hash_consed_size =
              if track_hash_consed_size { 32 + value_size } else { 0 };
            SubtermInfo {