weirflow 0.1.0

/// Reference oracle  -  returns `dom_set & target_set` per word.
#[must_use]
#[cfg(any(test, feature = "cpu-parity"))]
#[deprecated(
    note = "reference oracle only; production code must dispatch the Weir Program on a concrete GPU backend or use weir::oracle for parity evidence"
)]
pub(crate) fn cpu_ref(dom_set: &[u32], target_set: &[u32]) -> Vec<u32> {
    vyre_primitives::bitset::and::cpu_ref(dom_set, target_set)
}

/// Compute the dominator set for every node via the classical
/// iterative algorithm (Cooper-Harvey-Kennedy, simplified). Returns
/// a `node_count` x `bitset_words(node_count)` row-major bitmap;
/// row `n` is `dom(n)` (the set of nodes that dominate `n`).
///
/// `succ` is a CSR-style successor list: `succ[n]` is the list of
/// nodes that `n` flows to. `entry` is the function entry node.
///
/// The implementation is intentionally straightforward:
/// 1. `dom(entry) = {entry}`.
/// 2. `dom(n) = {n} + intersection of dom(p) for every predecessor `p`.
///    Iterate to fixpoint over a reverse-postorder traversal.
///
/// On disconnected nodes (no predecessor reachable from entry) the
/// dominator set is `{entry}`  -  the algorithm preserves the entry
/// invariant without diverging on unreachables.
#[must_use]
#[deprecated(
    note = "reference oracle only; production code must dispatch the Weir Program on a concrete GPU backend or use weir::oracle for parity evidence"
)]
pub(crate) fn compute_cpu(node_count: u32, succ: &[Vec<u32>], entry: u32) -> Vec<u32> {
    let n = dominators_u32_to_usize(node_count, "node count");
    if n == 0 {
        assert!(
            succ.is_empty(),
            "weir::dominators reference oracle received node_count=0 with {} successor rows; Fix: pass a CFG whose successor table exactly matches node_count",
            succ.len()
        );
        return Vec::new();
    }
    assert_eq!(
        succ.len(),
        n,
        "weir::dominators reference oracle received {} successor rows for node_count={node_count}; Fix: pass one successor row per CFG node",
        succ.len()
    );
    let entry_idx = dominators_u32_to_usize(entry, "entry node");
    assert!(
        entry_idx < n,
        "weir::dominators reference oracle received entry={entry} outside node_count={node_count}; Fix: pass a valid CFG entry node"
    );

    let words = dominator_words_usize(node_count);
    let dom_words = n.checked_mul(words).unwrap_or_else(|| {
        panic!(
            "weir::dominators reference oracle node_count={node_count} overflows dominator matrix word count. Fix: shard the CFG before parity comparison."
        )
    });
    let mut dom: Vec<u32> = vec![0u32; dom_words];
    let all_mask = compute_all_mask(node_count);
    for i in 0..n {
        if i == entry_idx {
            continue;
        }
        let (start, end) = dominator_row_bounds(i, words, "initial dominator row");
        let row = &mut dom[start..end];
        row.copy_from_slice(&all_mask);
    }
    set_bit(&mut dom, entry_idx, words, entry);

    let preds = build_predecessors(node_count, succ);
    let order = reverse_postorder(node_count, succ, entry);

    let mut changed = true;
    let mut iter_cap = n
        .checked_mul(2)
        .and_then(|value| value.checked_add(8))
        .unwrap_or_else(|| {
            panic!(
                "weir::dominators reference oracle node_count={node_count} overflows iteration cap. Fix: shard the CFG before parity comparison."
            )
        })
        .max(8);
    let mut new_row = vec![0u32; words];
    while changed && iter_cap > 0 {
        changed = false;
        iter_cap -= 1;
        for &node in &order {
            let i = dominators_u32_to_usize(node, "dominance iteration node");
            if i == entry_idx {
                continue;
            }
            let mut have_pred = false;
            for &p in &preds[i] {
                let p_index = dominators_u32_to_usize(p, "dominance predecessor node");
                let (p_start, p_end) =
                    dominator_row_bounds(p_index, words, "predecessor dominator row");
                let p_row = &dom[p_start..p_end];
                if have_pred {
                    for (acc, word) in new_row.iter_mut().zip(p_row.iter()) {
                        *acc &= *word;
                    }
                } else {
                    new_row.copy_from_slice(p_row);
                    have_pred = true;
                }
            }
            if !have_pred {
                new_row.fill(0);
                new_row[entry_idx / 32] |= 1u32 << (entry_idx % 32);
            } else {
                let bit = dominators_u32_to_usize(node, "dominance self bit");
                new_row[bit / 32] |= 1u32 << (bit % 32);
            }
            let (row_start, row_end) = dominator_row_bounds(i, words, "current dominator row");
            let row = &mut dom[row_start..row_end];
            if row != &new_row[..] {
                row.copy_from_slice(&new_row);
                changed = true;
            }
        }
    }
    dom
}

/// Build the byte-form dominator bitmap that surge-style scan
/// pipelines feed into the `dominates` predicate's `dom_set`
/// buffer. The output is the LE-byte serialization of the oracle
/// layout shared with [`compute_cpu`]'s `Vec<u32>`  -  a
/// `node_count x bitset_words(node_count)` row-major bitmap where row
/// `n`'s bits mark the dominators of `n`.
///
/// Returns an empty `Vec<u8>` when `node_count == 0`.
#[must_use]
#[deprecated(
    note = "reference oracle only; production code must dispatch the Weir Program on a concrete GPU backend or use weir::oracle for parity evidence"
)]
#[allow(deprecated)]
pub(crate) fn compute_bitmap_bytes(node_count: u32, succ: &[Vec<u32>], entry: u32) -> Vec<u8> {
    if node_count == 0 {
        assert!(
            succ.is_empty(),
            "weir::dominators reference oracle received node_count=0 with {} successor rows; Fix: pass a CFG whose successor table exactly matches node_count",
            succ.len()
        );
        return Vec::new();
    }
    let dom_words = compute_cpu(node_count, succ, entry);
    let byte_capacity = dom_words.len().checked_mul(4).unwrap_or_else(|| {
        panic!(
            "weir::dominators reference oracle bitmap byte capacity overflowed usize. Fix: shard the CFG before parity serialization."
        )
    });
    let mut out =
        crate::staging_reserve::reserved_vec(byte_capacity, "dominators CPU oracle bitmap bytes")
            .unwrap_or_else(|error| {
                panic!("dominators CPU oracle bitmap byte reservation failed: {error}")
            });
    for &word in &dom_words {
        out.extend_from_slice(&word.to_le_bytes());
    }
    out
}

#[cfg(test)]
mod allocation_order_tests {
    use super::*;

    #[allow(deprecated)]
    #[test]
    fn compute_cpu_rejects_row_mismatch_before_dominator_matrix_allocation() {
        let panic = std::panic::catch_unwind(|| compute_cpu(1_000_000_000, &[], 0))
            .expect_err("Fix: malformed CFG row count must be rejected before allocation.");
        let message = panic_message(panic.as_ref());
        assert!(
            message.contains("successor rows"),
            "Fix: row-count validation must run before dominator matrix allocation; got {message}"
        );
    }

    #[allow(deprecated)]
    #[test]
    fn compute_bitmap_bytes_rejects_zero_node_successor_rows() {
        let panic = std::panic::catch_unwind(|| compute_bitmap_bytes(0, &[Vec::new()], 0))
            .expect_err("Fix: zero-node bitmap oracle must reject non-empty successor tables.");
        let message = panic_message(panic.as_ref());
        assert!(
            message.contains("node_count=0"),
            "Fix: zero-node bitmap validation must preserve the CPU oracle shape contract; got {message}"
        );
    }

    fn panic_message(payload: &(dyn std::any::Any + Send)) -> String {
        if let Some(message) = payload.downcast_ref::<String>() {
            message.clone()
        } else if let Some(message) = payload.downcast_ref::<&'static str>() {
            (*message).to_string()
        } else {
            "<non-string panic payload>".to_string()
        }
    }
}

pub(super) fn compute_all_mask(node_count: u32) -> Vec<u32> {
    let words = dominator_words_usize(node_count);
    let n = dominators_u32_to_usize(node_count, "all-mask node count");
    let mut mask = vec![0u32; words];
    for i in 0..n {
        mask[i / 32] |= 1u32 << (i % 32);
    }
    mask
}

fn set_bit(dom: &mut [u32], row: usize, words: usize, bit: u32) {
    let (start, end) = dominator_row_bounds(row, words, "set-bit dominator row");
    let row_slice = &mut dom[start..end];
    let b = dominators_u32_to_usize(bit, "set-bit dominator bit");
    row_slice[b / 32] |= 1u32 << (b % 32);
}

fn build_predecessors(node_count: u32, succ: &[Vec<u32>]) -> Vec<Vec<u32>> {
    let n = dominators_u32_to_usize(node_count, "predecessor node count");
    let indegrees = predecessor_indegrees(node_count, n, succ);
    let mut preds = reserved_predecessor_rows(&indegrees);
    for (src, list) in succ.iter().enumerate() {
        let src_node = dominators_usize_to_u32(src, "predecessor source node");
        for &dst in list {
            let dst_index = dominators_u32_to_usize(dst, "predecessor destination node");
            preds[dst_index].push(src_node);
        }
    }
    preds
}

fn predecessor_indegrees(
    node_count: u32,
    node_count_usize: usize,
    succ: &[Vec<u32>],
) -> Vec<usize> {
    let mut indegrees: Vec<usize> = crate::staging_reserve::reserved_vec(
        node_count_usize,
        "dominators CPU oracle predecessor indegrees",
    )
    .unwrap_or_else(|error| {
        panic!("dominators CPU oracle predecessor indegree reservation failed: {error}")
    });
    indegrees.resize(node_count_usize, 0usize);
    for (src, list) in succ.iter().enumerate() {
        for &dst in list {
            let dst_index = dominators_u32_to_usize(dst, "predecessor destination node");
            assert!(
                dst_index < node_count_usize,
                "weir::dominators reference oracle received edge {src}->{dst} outside node_count={node_count}; Fix: validate CFG edge endpoints before dominator construction"
            );
            indegrees[dst_index] = indegrees[dst_index].checked_add(1).unwrap_or_else(|| {
                panic!(
                    "weir::dominators reference oracle predecessor count overflowed for node {dst}. Fix: shard the CFG before CPU parity construction."
                )
            });
        }
    }
    indegrees
}

fn reserved_predecessor_rows(indegrees: &[usize]) -> Vec<Vec<u32>> {
    let mut rows = crate::staging_reserve::reserved_vec(
        indegrees.len(),
        "dominators CPU oracle predecessor rows",
    )
    .unwrap_or_else(|error| {
        panic!("dominators CPU oracle predecessor row reservation failed: {error}")
    });
    for &indegree in indegrees {
        rows.push(
            crate::staging_reserve::reserved_vec(
                indegree,
                "dominators CPU oracle predecessor row entries",
            )
            .unwrap_or_else(|error| {
                panic!("dominators CPU oracle predecessor row entry reservation failed: {error}")
            }),
        );
    }
    rows
}

fn reverse_postorder(node_count: u32, succ: &[Vec<u32>], entry: u32) -> Vec<u32> {
    let n = dominators_u32_to_usize(node_count, "reverse-postorder node count");
    let mut order =
        crate::staging_reserve::reserved_vec(n, "dominators CPU oracle reverse-postorder")
            .unwrap_or_else(|error| {
                panic!("dominators CPU oracle reverse-postorder reservation failed: {error}")
            });
    let mut visited = vec![false; n];
    let mut stack: Vec<(u32, usize)> = Vec::new();
    stack.push((entry, 0));
    let entry_index = dominators_u32_to_usize(entry, "reverse-postorder entry node");
    assert!(
        entry_index < n,
        "weir::dominators reference oracle received entry={entry} outside node_count={node_count}; Fix: pass a valid CFG entry node"
    );
    visited[entry_index] = true;
    while let Some(&(node, idx)) = stack.last() {
        let node_index = dominators_u32_to_usize(node, "reverse-postorder stack node");
        let succs = succ[node_index].as_slice();
        if idx < succs.len() {
            let Some(back) = stack.last_mut() else {
                break;
            };
            back.1 += 1;
            let nxt = succs[idx];
            let nxt_index = dominators_u32_to_usize(nxt, "reverse-postorder successor node");
            if nxt_index < n && !visited[nxt_index] {
                visited[nxt_index] = true;
                stack.push((nxt, 0));
            }
        } else {
            order.push(node);
            stack.pop();
        }
    }
    for i in 0..n {
        if !visited[i] {
            order.push(dominators_usize_to_u32(
                i,
                "reverse-postorder disconnected node",
            ));
        }
    }
    order.reverse();
    order
}

fn dominator_words_usize(node_count: u32) -> usize {
    dominators_u32_to_usize(
        crate::graph_layout::LinearDomain::new(node_count).bitset_words(),
        "dominator bitset word count",
    )
}

fn dominator_row_bounds(row: usize, words: usize, label: &'static str) -> (usize, usize) {
    let start = row.checked_mul(words).unwrap_or_else(|| {
        panic!(
            "weir::dominators reference oracle {label} start overflowed: row={row}, words={words}. Fix: shard the CFG before parity comparison."
        )
    });
    let end = start.checked_add(words).unwrap_or_else(|| {
        panic!(
            "weir::dominators reference oracle {label} end overflowed: start={start}, words={words}. Fix: shard the CFG before parity comparison."
        )
    });
    (start, end)
}

fn dominators_u32_to_usize(value: u32, label: &'static str) -> usize {
    usize::try_from(value).unwrap_or_else(|source| {
        panic!(
            "weir::dominators reference oracle {label} value {value} cannot fit usize: {source}. Fix: shard the CFG before parity comparison."
        )
    })
}

fn dominators_usize_to_u32(value: usize, label: &'static str) -> u32 {
    u32::try_from(value).unwrap_or_else(|source| {
        panic!(
            "weir::dominators reference oracle {label} value {value} cannot fit u32: {source}. Fix: shard the CFG before parity comparison."
        )
    })
}

#[cfg(test)]
#[allow(deprecated)]
mod extra_panic_tests {
    use super::compute_cpu;

    #[test]
    #[should_panic(expected = "successor rows for node_count")]
    fn compute_cpu_rejects_row_count_mismatch() {
        let _ = compute_cpu(2, &[vec![1]], 0);
    }

    #[test]
    #[should_panic(expected = "entry=2 outside node_count=2")]
    fn compute_cpu_rejects_entry_out_of_bounds() {
        let _ = compute_cpu(2, &[vec![1], vec![]], 2);
    }

    #[test]
    #[should_panic(expected = "edge 0->5 outside node_count=2")]
    fn compute_cpu_rejects_edge_out_of_bounds() {
        let _ = compute_cpu(2, &[vec![5], vec![]], 0);
    }
}