weir/test_harness/

ifds_builder.rs

//! Deterministic IFDS problem fixtures for Weir oracle tests.
//!
//! The builder computes `expected_reached` with a small worklist interpreter
//! over IFDS triples instead of calling the CPU oracle under test. That keeps
//! builder parity tests independent of the CSR construction path they verify.

/// Complete IFDS problem fixture consumed by oracle and resident tests.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IfdsProblemFixture {
    pub num_procs: u32,
    pub blocks_per_proc: u32,
    pub facts_per_proc: u32,
    pub intra_edges: Vec<(u32, u32, u32)>,
    pub inter_edges: Vec<(u32, u32, u32, u32)>,
    pub flow_gen: Vec<(u32, u32, u32)>,
    pub flow_kill: Vec<(u32, u32, u32)>,
    pub seed_facts: Vec<(u32, u32, u32)>,
    pub expected_reached: Vec<u32>,
}

/// Factory for deterministic IFDS fixtures.
pub struct IfdsProblemBuilder;

impl IfdsProblemBuilder {
    #[allow(clippy::too_many_arguments)]
    pub fn random_valid(
        num_procs: u32,
        blocks_per_proc: u32,
        facts_per_proc: u32,
        intra_edge_count: u32,
        seed_count: u32,
        summary_edge_count: u32,
        seed: u64,
    ) -> IfdsProblemFixture {
        assert!(
            num_procs > 0 && blocks_per_proc > 0 && facts_per_proc > 0,
            "IfdsProblemBuilder::random_valid requires non-zero dimensions"
        );
        let _ = checked_total_nodes(num_procs, blocks_per_proc, facts_per_proc);
        let mut rng = SplitMix64::new(
            seed ^ ((num_procs as u64) << 42)
                ^ ((blocks_per_proc as u64) << 21)
                ^ facts_per_proc as u64,
        );

        let mut intra_edges = Vec::with_capacity(intra_edge_count as usize);
        for edge_idx in 0..intra_edge_count {
            let proc_id = if edge_idx < num_procs {
                edge_idx
            } else {
                rng.below(num_procs)
            };
            let src_block = if blocks_per_proc <= 1 {
                0
            } else if edge_idx < blocks_per_proc - 1 {
                edge_idx
            } else {
                rng.below(blocks_per_proc)
            };
            let mut dst_block = if blocks_per_proc <= 1 {
                0
            } else if edge_idx < blocks_per_proc - 1 {
                src_block + 1
            } else {
                rng.below(blocks_per_proc)
            };
            if blocks_per_proc > 1 && dst_block == src_block {
                dst_block = (dst_block + 1) % blocks_per_proc;
            }
            intra_edges.push((proc_id % num_procs, src_block, dst_block));
        }

        let mut inter_edges = Vec::with_capacity(summary_edge_count as usize);
        for _ in 0..summary_edge_count {
            let src_proc = rng.below(num_procs);
            let mut dst_proc = rng.below(num_procs);
            if num_procs > 1 && dst_proc == src_proc {
                dst_proc = (dst_proc + 1) % num_procs;
            }
            inter_edges.push((
                src_proc,
                rng.below(blocks_per_proc),
                dst_proc,
                rng.below(blocks_per_proc),
            ));
        }

        let mut flow_gen = Vec::with_capacity(summary_edge_count as usize);
        let mut flow_kill = Vec::with_capacity((summary_edge_count / 2) as usize);
        for rule_idx in 0..summary_edge_count {
            let proc_id = rng.below(num_procs);
            let block_id = rng.below(blocks_per_proc);
            let gen_fact = rng.below(facts_per_proc);
            flow_gen.push((proc_id, block_id, gen_fact));
            if rule_idx % 2 == 1 {
                let kill_fact = if facts_per_proc > 1 {
                    1 + rng.below(facts_per_proc - 1)
                } else {
                    0
                };
                flow_kill.push((proc_id, block_id, kill_fact));
            }
        }

        let mut seed_facts = Vec::with_capacity(seed_count as usize);
        for seed_idx in 0..seed_count {
            let proc_id = if seed_idx < num_procs {
                seed_idx
            } else {
                rng.below(num_procs)
            };
            let block_id = if blocks_per_proc > 1 && seed_idx == 0 {
                0
            } else {
                rng.below(blocks_per_proc)
            };
            let fact_id = if facts_per_proc > 1 && seed_idx == 0 {
                0
            } else {
                rng.below(facts_per_proc)
            };
            seed_facts.push((proc_id % num_procs, block_id, fact_id));
        }

        let expected_reached = expected_reachability(
            num_procs,
            blocks_per_proc,
            facts_per_proc,
            &intra_edges,
            &inter_edges,
            &flow_gen,
            &flow_kill,
            &seed_facts,
        );

        IfdsProblemFixture {
            num_procs,
            blocks_per_proc,
            facts_per_proc,
            intra_edges,
            inter_edges,
            flow_gen,
            flow_kill,
            seed_facts,
            expected_reached,
        }
    }

    pub fn adversarial_zero_dimensions() -> IfdsProblemFixture {
        IfdsProblemFixture {
            num_procs: 0,
            blocks_per_proc: 1,
            facts_per_proc: 1,
            intra_edges: Vec::new(),
            inter_edges: Vec::new(),
            flow_gen: Vec::new(),
            flow_kill: Vec::new(),
            seed_facts: Vec::new(),
            expected_reached: Vec::new(),
        }
    }

    pub fn adversarial_overflow_shape() -> IfdsProblemFixture {
        IfdsProblemFixture {
            num_procs: 4097,
            blocks_per_proc: 1,
            facts_per_proc: 1,
            intra_edges: Vec::new(),
            inter_edges: Vec::new(),
            flow_gen: Vec::new(),
            flow_kill: Vec::new(),
            seed_facts: Vec::new(),
            expected_reached: Vec::new(),
        }
    }
}

#[allow(clippy::too_many_arguments)]
fn expected_reachability(
    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> {
    let total_nodes = checked_total_nodes(num_procs, blocks_per_proc, facts_per_proc);
    let mut killed = vec![false; total_nodes];
    for &(proc_id, block_id, fact_id) in flow_kill {
        killed[dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc)] = true;
    }

    let mut visited = vec![false; total_nodes];
    let mut queue = Vec::with_capacity(seed_facts.len());
    for &(proc_id, block_id, fact_id) in seed_facts {
        mark_reached(
            proc_id,
            block_id,
            fact_id,
            blocks_per_proc,
            facts_per_proc,
            &mut visited,
            &mut queue,
        );
    }

    let mut head = 0usize;
    while head < queue.len() {
        let (proc_id, block_id, fact_id) = queue[head];
        head += 1;

        for &(edge_proc, src_block, dst_block) in intra_edges {
            if edge_proc != proc_id || src_block != block_id {
                continue;
            }
            let current_idx =
                dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc);
            if !killed[current_idx] {
                mark_reached(
                    proc_id,
                    dst_block,
                    fact_id,
                    blocks_per_proc,
                    facts_per_proc,
                    &mut visited,
                    &mut queue,
                );
            }
            if fact_id == 0 {
                for &(gen_proc, gen_block, gen_fact) in flow_gen {
                    if gen_proc == proc_id && gen_block == block_id {
                        mark_reached(
                            proc_id,
                            dst_block,
                            gen_fact,
                            blocks_per_proc,
                            facts_per_proc,
                            &mut visited,
                            &mut queue,
                        );
                    }
                }
            }
        }

        for &(src_proc, src_block, dst_proc, dst_block) in inter_edges {
            if src_proc == proc_id && src_block == block_id {
                mark_reached(
                    dst_proc,
                    dst_block,
                    fact_id,
                    blocks_per_proc,
                    facts_per_proc,
                    &mut visited,
                    &mut queue,
                );
            }
        }
    }

    visited
        .into_iter()
        .enumerate()
        .filter_map(|(dense_id, reached)| reached.then_some(dense_id as u32))
        .collect()
}

fn mark_reached(
    proc_id: u32,
    block_id: u32,
    fact_id: u32,
    blocks_per_proc: u32,
    facts_per_proc: u32,
    visited: &mut [bool],
    queue: &mut Vec<(u32, u32, u32)>,
) {
    let idx = dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc);
    if !visited[idx] {
        visited[idx] = true;
        queue.push((proc_id, block_id, fact_id));
    }
}

fn checked_total_nodes(num_procs: u32, blocks_per_proc: u32, facts_per_proc: u32) -> usize {
    let total = (num_procs as u64)
        .checked_mul(blocks_per_proc as u64)
        .and_then(|value| value.checked_mul(facts_per_proc as u64))
        ;
    assert!(
        total.is_some(),
        "IFDS fixture node count overflows u64"
    );
    let total = total.unwrap_or(u64::MAX);
    assert!(
        total <= u32::MAX as u64,
        "IFDS fixture node count {total} exceeds u32 dense domain"
    );
    assert!(
        total <= usize::MAX as u64,
        "IFDS fixture node count {total} does not fit usize"
    );
    total as usize
}

fn dense_index(
    proc_id: u32,
    block_id: u32,
    fact_id: u32,
    blocks_per_proc: u32,
    facts_per_proc: u32,
) -> usize {
    let idx = (proc_id as u64)
        .checked_mul(blocks_per_proc as u64)
        .and_then(|value| value.checked_mul(facts_per_proc as u64))
        .and_then(|value| {
            (block_id as u64)
                .checked_mul(facts_per_proc as u64)
                .and_then(|block_offset| value.checked_add(block_offset))
        })
        .and_then(|value| value.checked_add(fact_id as u64))
        ;
    assert!(idx.is_some(), "IFDS fixture dense index overflows u64");
    let idx = idx.unwrap_or(u64::MAX);
    assert!(
        idx <= usize::MAX as u64,
        "IFDS fixture dense index {idx} does not fit usize"
    );
    idx as usize
}

#[derive(Debug, Clone, Copy)]
struct SplitMix64 {
    state: u64,
}

impl SplitMix64 {
    fn new(seed: u64) -> Self {
        Self {
            state: seed ^ 0x9e37_79b9_7f4a_7c15,
        }
    }

    fn next(&mut self) -> u64 {
        self.state = self.state.wrapping_add(0x9e37_79b9_7f4a_7c15);
        let mut z = self.state;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        z ^ (z >> 31)
    }

    fn below(&mut self, upper: u32) -> u32 {
        if upper == 0 {
            return 0;
        }
        (self.next() % upper as u64) as u32
    }
}