weirflow 0.1.0

//! CPU IFDS oracle for parity tests and conformance checks.

use crate::ifds_gpu::{validate_ifds_problem, IfdsShape};
use vyre_primitives::graph::exploded::{build_cpu_reference, dense_to_encoded};

/// CPU-reference IFDS solver. Constructs the exploded supergraph on the CPU
/// and runs BFS from `seed_facts` to convergence.
///
/// This is a parity oracle only. Production code must dispatch the GPU IFDS
/// program or use the resident IFDS APIs.
#[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(clippy::too_many_arguments)]
pub(crate) fn solve_cpu(
    num_procs: u32,
    blocks_per_proc: u32,
    facts_per_proc: u32,
    intra_edges: &[(u32, u32, u32)],
    inter_edges: &[(u32, u32, u32, u32)],
    flow_gen: &[(u32, u32, u32)],
    flow_kill: &[(u32, u32, u32)],
    seed_facts: &[(u32, u32, u32)],
) -> Vec<u32> {
    validate_ifds_problem(
        "weir IFDS CPU oracle",
        num_procs,
        blocks_per_proc,
        facts_per_proc,
        intra_edges,
        inter_edges,
        flow_gen,
        flow_kill,
        seed_facts,
    )
    .unwrap_or_else(|error| panic!("IFDS CPU oracle received malformed problem: {error}"));
    let edge_count = intra_edges
        .len()
        .checked_add(inter_edges.len())
        .and_then(|count| count.checked_add(flow_gen.len()))
        .and_then(|count| count.checked_add(flow_kill.len()))
        .unwrap_or_else(|| {
            panic!(
                "IFDS CPU oracle edge count overflows usize. Fix: shard the IFDS problem before building the exploded CSR."
            )
        });
    let edge_count = u32::try_from(edge_count).unwrap_or_else(|error| {
        panic!(
            "IFDS CPU oracle edge count does not fit u32: {error}. Fix: shard the IFDS problem or reduce the encoded domain before building the exploded CSR."
        )
    });
    let shape = IfdsShape {
        num_procs,
        blocks_per_proc,
        facts_per_proc,
        edge_count,
    };
    if !shape.fits() {
        panic!(
            "IFDS CPU oracle dimensions exceed 32-bit exploded-node encoding: procs={} blocks={} facts={}. Fix: shard the IFDS problem or reduce the encoded domain.",
            num_procs, blocks_per_proc, facts_per_proc
        );
    }
    let (row_ptr, col_idx) = build_cpu_reference(
        num_procs,
        blocks_per_proc,
        facts_per_proc,
        intra_edges,
        inter_edges,
        flow_gen,
        flow_kill,
    );
    let dense = bfs_dense_queue(
        &row_ptr,
        &col_idx,
        seed_facts,
        blocks_per_proc,
        facts_per_proc,
    );
    let mut out = crate::staging_reserve::reserved_vec(dense.len(), "IFDS CPU oracle output")
        .unwrap_or_else(|error| panic!("IFDS CPU oracle output reservation failed: {error}"));
    for dense_id in dense {
        let encoded = dense_to_encoded(dense_id, blocks_per_proc, facts_per_proc).unwrap_or_else(|| {
            panic!(
                "IFDS CPU oracle dense node {dense_id} cannot be encoded with blocks_per_proc={blocks_per_proc} facts_per_proc={facts_per_proc}. Fix: keep the oracle dense domain identical to the encoded IFDS shape."
            )
        });
        out.push(encoded);
    }
    out.sort_unstable();
    out
}

fn dense_idx(p: u32, b: u32, f: u32, blocks_per_proc: u32, facts_per_proc: u32) -> u32 {
    p * blocks_per_proc * facts_per_proc + b * facts_per_proc + f
}

fn bfs_dense_queue(
    row_ptr: &[u32],
    col_idx: &[u32],
    seed_facts: &[(u32, u32, u32)],
    blocks_per_proc: u32,
    facts_per_proc: u32,
) -> Vec<u32> {
    let total_nodes = row_ptr
        .len()
        .checked_sub(1)
        .expect("weir IFDS dense BFS oracle received an empty CSR row_ptr. Fix: pass a CSR table with node_count + 1 row offsets.");
    let mut visited = vec![false; total_nodes];
    let mut queue =
        crate::staging_reserve::reserved_vec(seed_facts.len(), "IFDS CPU oracle BFS queue")
            .unwrap_or_else(|error| {
                panic!("IFDS CPU oracle BFS queue reservation failed: {error}")
            });
    let mut result =
        crate::staging_reserve::reserved_vec(seed_facts.len(), "IFDS CPU oracle BFS result")
            .unwrap_or_else(|error| {
                panic!("IFDS CPU oracle BFS result reservation failed: {error}")
            });
    for &(p, b, f) in seed_facts {
        let n = dense_idx(p, b, f, blocks_per_proc, facts_per_proc);
        let idx = dense_u32_to_usize(n, "seed dense node");
        if idx < total_nodes && !visited[idx] {
            visited[idx] = true;
            queue.push(n);
            result.push(n);
        }
    }
    let mut head = 0usize;
    while head < queue.len() {
        let node = queue[head];
        head += 1;
        let node_idx = dense_u32_to_usize(node, "queued dense node");
        let next_node_idx = node_idx.checked_add(1).unwrap_or_else(|| {
            panic!(
                "IFDS CPU oracle row offset sentinel index overflowed usize. Fix: shard the dense IFDS graph."
            )
        });
        let start = dense_u32_to_usize(row_ptr[node_idx], "CSR row start");
        let end = dense_u32_to_usize(row_ptr[next_node_idx], "CSR row end");
        for &neighbour in &col_idx[start..end] {
            let idx = dense_u32_to_usize(neighbour, "neighbour dense node");
            if idx < total_nodes && !visited[idx] {
                visited[idx] = true;
                queue.push(neighbour);
                result.push(neighbour);
            }
        }
    }
    result
}

fn dense_u32_to_usize(value: u32, label: &'static str) -> usize {
    usize::try_from(value).unwrap_or_else(|source| {
        panic!(
            "IFDS CPU oracle {label} value {value} cannot fit usize: {source}. Fix: shard the dense IFDS graph before parity decoding."
        )
    })
}