Function build_plan

crates/kernel/src/shard.rs:367–401

Emit `node`'s plan entries; return the index of the entry representing it.

(node: &AggNode, arity: usize, ops: &mut Vec<FoldOp>)

/// *collapsed* so each agg call folds up to `arity` whole subtrees (never
/// splitting a subtree across calls), keeping the agg-proof count ~`N/(arity-1)`
/// — a strict binary fold would be ~`N` agg proofs, dominating cost. Children of
/// each agg are emitted in shard order so the subject merkle-fold matches the
/// guest's left-associative join.
pub fn agg_plan(tree: &AggNode, arity: usize) -> Vec<FoldOp> {
  let arity = arity.max(2);
  let mut ops: Vec<FoldOp> = Vec::new();
  build_plan(tree, arity, &mut ops);
  ops
}

/// Emit `node`'s plan entries; return the index of the entry representing it.
fn build_plan(node: &AggNode, arity: usize, ops: &mut Vec<FoldOp>) -> usize {
  match node {
    AggNode::Leaf(id) => {
      ops.push(FoldOp::Leaf(*id));
      ops.len() - 1
    },
    AggNode::Internal(l, r) => {
      // Collapse the binary subtree into up to `arity` child subtrees: start
      // from the two halves and repeatedly split the *largest* still-internal
      // frontier node until we have `arity` children or all are leaves. This
      // keeps tightly-coupled siblings together while bounding the fan-in.
      let mut frontier: Vec<&AggNode> = vec![l, r];
      while frontier.len() < arity {
        let largest = frontier
          .iter()
          .enumerate()
          .filter(|(_, nd)| matches!(nd, AggNode::Internal(_, _)))
          .max_by_key(|(_, nd)| nd.num_leaves())
          .map(|(i, _)| i);
        let Some(i) = largest else { break }; // all leaves: cannot expand
        let AggNode::Internal(l, r) = frontier.swap_remove(i) else {
          unreachable!()
        };
        frontier.push(l);
        frontier.push(r);
      }
      // Shard order keeps the merkle subject-fold left-associative.