weirflow 0.1.0

//! IFDS shape, domain sizing, and problem-boundary validation.

use vyre_primitives::bitset::bitset_words;
use vyre_primitives::graph::exploded::validate_ifds_csr_layout;

#[allow(clippy::too_many_arguments)]
pub fn validate_ifds_problem(
    context: &str,
    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)],
) -> Result<(), String> {
    if num_procs == 0 || blocks_per_proc == 0 || facts_per_proc == 0 {
        return Err(format!(
            "{context} requires non-zero dimensions, got procs={num_procs}, blocks={blocks_per_proc}, facts={facts_per_proc}. Fix: validate the IFDS problem shape before dispatch."
        ));
    }
    for (idx, &(proc_id, src_block, dst_block)) in intra_edges.iter().enumerate() {
        if proc_id >= num_procs || src_block >= blocks_per_proc || dst_block >= blocks_per_proc {
            return Err(format!(
                "{context} intra edge {idx} is out of domain: proc={proc_id}, src_block={src_block}, dst_block={dst_block}, domain procs={num_procs}, blocks={blocks_per_proc}. Fix: discard or remap malformed CFG edges before IFDS dispatch."
            ));
        }
    }
    for (idx, &(src_proc, src_block, dst_proc, dst_block)) in inter_edges.iter().enumerate() {
        if src_proc >= num_procs
            || dst_proc >= num_procs
            || src_block >= blocks_per_proc
            || dst_block >= blocks_per_proc
        {
            return Err(format!(
                "{context} inter edge {idx} is out of domain: src_proc={src_proc}, src_block={src_block}, dst_proc={dst_proc}, dst_block={dst_block}, domain procs={num_procs}, blocks={blocks_per_proc}. Fix: discard or remap malformed callgraph edges before IFDS dispatch."
            ));
        }
    }
    for (label, triples) in [("GEN", flow_gen), ("KILL", flow_kill), ("seed", seed_facts)] {
        for (idx, &(proc_id, block_id, fact_id)) in triples.iter().enumerate() {
            if proc_id >= num_procs || block_id >= blocks_per_proc || fact_id >= facts_per_proc {
                return Err(format!(
                    "{context} {label} tuple {idx} is out of domain: proc={proc_id}, block={block_id}, fact={fact_id}, domain procs={num_procs}, blocks={blocks_per_proc}, facts={facts_per_proc}. Fix: discard or remap malformed dataflow facts before IFDS dispatch."
                ));
            }
        }
    }
    Ok(())
}

/// Dispatch geometry for one IFDS BFS step on the GPU.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct IfdsShape {
    /// Number of procedures in the exploded supergraph.
    pub num_procs: u32,
    /// Number of basic blocks encoded per procedure.
    pub blocks_per_proc: u32,
    /// Number of dataflow facts encoded per procedure.
    pub facts_per_proc: u32,
    /// Number of graph edges in the CSR representation.
    pub edge_count: u32,
}

/// Auditable IFDS shape report for release evidence, resident planning, and
/// dispatch diagnostics.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct IfdsShapeCertificate {
    /// Number of procedures in the exploded supergraph.
    pub num_procs: u32,
    /// Number of basic blocks encoded per procedure.
    pub blocks_per_proc: u32,
    /// Number of dataflow facts encoded per procedure.
    pub facts_per_proc: u32,
    /// Number of graph edges in the CSR representation.
    pub edge_count: u32,
    /// Whether `edge_count == 0`; valid for disconnected seed-only problems.
    pub zero_edge_budget: bool,
    /// Whether the dimensions fit the packed IFDS domain.
    pub fits: bool,
    /// Exploded node count when dimensions are valid.
    pub exploded_nodes: Option<u32>,
    /// Packed bitset words required for one frontier over `exploded_nodes`.
    pub bitset_words: Option<u32>,
    /// Structured rejection reason when the shape exceeds a domain cap.
    pub cap_reason: Option<String>,
}

impl IfdsShape {
    /// Construct an [`IfdsShape`] from individual dimensions.
    #[inline]
    #[must_use]
    pub const fn new(
        num_procs: u32,
        blocks_per_proc: u32,
        facts_per_proc: u32,
        edge_count: u32,
    ) -> Self {
        Self {
            num_procs,
            blocks_per_proc,
            facts_per_proc,
            edge_count,
        }
    }

    /// Number of exploded-supergraph nodes = `procs * blocks * facts`.
    #[inline]
    pub fn node_count(&self) -> Result<u32, String> {
        self.checked_node_count()
    }

    /// Checked node count for callers that can return structured errors.
    #[inline]
    pub fn checked_node_count(&self) -> Result<u32, String> {
        validate_ifds_csr_layout(
            self.num_procs,
            self.blocks_per_proc,
            self.facts_per_proc,
            0,
            0,
            0,
        )
        .map(|layout| layout.total_nodes)
        .map_err(|error| format!("weir IFDS dimensions invalid: {error}"))
    }

    /// Shared linear layout domain for the exploded IFDS supergraph.
    #[inline]
    pub fn node_domain(&self) -> Result<crate::graph_layout::LinearDomain, String> {
        self.checked_node_count()
            .map(crate::graph_layout::LinearDomain::new)
    }

    /// Pre-flight fit check for 32-bit exploded-node encoding.
    #[inline]
    #[must_use]
    pub fn fits(&self) -> bool {
        validate_ifds_csr_layout(
            self.num_procs,
            self.blocks_per_proc,
            self.facts_per_proc,
            0,
            0,
            0,
        )
        .is_ok()
    }

    /// Build an auditable shape certificate without duplicating validation
    /// logic. Invalid shapes return `fits=false` plus the same cap reason used
    /// by checked dispatch paths.
    #[must_use]
    pub fn certificate(&self) -> IfdsShapeCertificate {
        match self.checked_node_count() {
            Ok(exploded_nodes) => IfdsShapeCertificate {
                num_procs: self.num_procs,
                blocks_per_proc: self.blocks_per_proc,
                facts_per_proc: self.facts_per_proc,
                edge_count: self.edge_count,
                zero_edge_budget: self.edge_count == 0,
                fits: true,
                exploded_nodes: Some(exploded_nodes),
                bitset_words: Some(bitset_words(exploded_nodes)),
                cap_reason: None,
            },
            Err(error) => IfdsShapeCertificate {
                num_procs: self.num_procs,
                blocks_per_proc: self.blocks_per_proc,
                facts_per_proc: self.facts_per_proc,
                edge_count: self.edge_count,
                zero_edge_budget: self.edge_count == 0,
                fits: false,
                exploded_nodes: None,
                bitset_words: None,
                cap_reason: Some(error),
            },
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{validate_ifds_problem, IfdsShape};
    use vyre_primitives::graph::exploded::{MAX_BLOCK_ID, MAX_FACT_ID, MAX_PROC_ID};

    // ------------------------------------------------------------------
    // 1. Overflow rejection (u32::MAX dimensions must be rejected).
    // ------------------------------------------------------------------

    #[test]
    fn ifds_shape_rejects_u32_max_procs() {
        let shape = IfdsShape::new(u32::MAX, 1, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
        assert!(shape.node_domain().is_err());
    }

    #[test]
    fn ifds_shape_rejects_u32_max_blocks() {
        let shape = IfdsShape::new(1, u32::MAX, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_u32_max_facts() {
        let shape = IfdsShape::new(1, 1, u32::MAX, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_product_overflow_with_legal_axes() {
        // 65536 * 65536 = 2^32, overflowing u32. Each axis is individually
        // inside the packed encoding limits, but the product overflows.
        let shape = IfdsShape::new(2, 65536, 65536, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_max_proc_id_plus_one() {
        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_max_block_id_plus_one() {
        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_max_fact_id_plus_one() {
        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    // ------------------------------------------------------------------
    // 2. Zero-dimension rejection.
    // ------------------------------------------------------------------

    #[test]
    fn ifds_shape_rejects_zero_procs() {
        let shape = IfdsShape::new(0, 1, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_zero_blocks() {
        let shape = IfdsShape::new(1, 0, 1, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn ifds_shape_rejects_zero_facts() {
        let shape = IfdsShape::new(1, 1, 0, 0);
        assert!(!shape.fits());
        assert!(shape.checked_node_count().is_err());
    }

    #[test]
    fn validate_ifds_problem_rejects_zero_procs() {
        let err = validate_ifds_problem("test", 0, 1, 1, &[], &[], &[], &[], &[])
            .expect_err("zero procs must be rejected");
        assert!(err.contains("requires non-zero dimensions"));
    }

    #[test]
    fn validate_ifds_problem_rejects_zero_blocks() {
        let err = validate_ifds_problem("test", 1, 0, 1, &[], &[], &[], &[], &[])
            .expect_err("zero blocks must be rejected");
        assert!(err.contains("requires non-zero dimensions"));
    }

    #[test]
    fn validate_ifds_problem_rejects_zero_facts() {
        let err = validate_ifds_problem("test", 1, 1, 0, &[], &[], &[], &[], &[])
            .expect_err("zero facts must be rejected");
        assert!(err.contains("requires non-zero dimensions"));
    }

    #[test]
    fn validate_ifds_problem_accepts_empty_edges_and_seeds() {
        // Empty edge / seed lists are fine as long as dimensions are non-zero.
        validate_ifds_problem("test", 1, 1, 1, &[], &[], &[], &[], &[])
            .expect("empty edges/seeds with valid dims should succeed");
    }

    #[test]
    fn validate_ifds_problem_accepts_zero_edge_count() {
        // edge_count is not validated by validate_ifds_problem.
        validate_ifds_problem("test", 2, 4, 8, &[], &[], &[], &[], &[])
            .expect("zero edge count should be accepted");
    }

    // ------------------------------------------------------------------
    // 3. fits() on extreme shapes.
    // ------------------------------------------------------------------

    #[test]
    fn ifds_shape_fits_at_exact_max_limits() {
        // MAX_PROC_ID + 1 = 4096, MAX_BLOCK_ID + 1 = 1024, MAX_FACT_ID + 1 = 1024.
        // The product 4096*1024*1024 overflows u32, so we test the largest encoding
        // that still fits in the product: 4095 procs × 1024 blocks × 1024 facts.
        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
        assert!(shape.fits());
    }

    #[test]
    fn ifds_shape_fits_at_one_per_axis() {
        let shape = IfdsShape::new(1, 1, 1, 0);
        assert!(shape.fits());
    }

    #[test]
    fn ifds_shape_fits_rejects_proc_overflow() {
        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn ifds_shape_fits_rejects_block_overflow() {
        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn ifds_shape_fits_rejects_fact_overflow() {
        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn ifds_shape_fits_rejects_overflow_product() {
        let shape = IfdsShape::new(2, 65536, 65536, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn ifds_shape_fits_accepts_realistic_dimensions() {
        let shape = IfdsShape::new(64, 128, 32, 4096);
        assert!(shape.fits());
    }

    // ------------------------------------------------------------------
    // 4. checked_node_count saturation.
    // ------------------------------------------------------------------

    #[test]
    fn checked_node_count_computes_small_product_correctly() {
        let shape = IfdsShape::new(2, 3, 4, 0);
        assert_eq!(shape.checked_node_count().unwrap(), 24);
    }

    #[test]
    fn checked_node_count_saturation_on_proc_overflow() {
        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
        let err = shape.checked_node_count().expect_err("must error");
        assert!(err.contains("weir IFDS dimensions invalid"));
    }

    #[test]
    fn checked_node_count_saturation_on_block_overflow() {
        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
        let err = shape.checked_node_count().expect_err("must error");
        assert!(err.contains("weir IFDS dimensions invalid"));
    }

    #[test]
    fn checked_node_count_saturation_on_fact_overflow() {
        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
        let err = shape.checked_node_count().expect_err("must error");
        assert!(err.contains("weir IFDS dimensions invalid"));
    }

    #[test]
    fn checked_node_count_saturation_on_product_overflow() {
        let shape = IfdsShape::new(2, 65536, 65536, 0);
        let err = shape.checked_node_count().expect_err("must error");
        assert!(err.contains("weir IFDS dimensions invalid"));
    }

    #[test]
    fn checked_node_count_at_max_limits() {
        // Use dimensions that fit both encoding limits and u32 product space.
        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
        let count = shape.checked_node_count().unwrap();
        assert_eq!(
            count as u64,
            (MAX_PROC_ID as u64 + 1) * (MAX_BLOCK_ID as u64 + 1) * (MAX_FACT_ID as u64)
        );
    }

    #[test]
    fn node_count_alias_matches_checked_node_count() {
        let shape = IfdsShape::new(3, 7, 11, 0);
        assert_eq!(
            shape.node_count().unwrap(),
            shape.checked_node_count().unwrap()
        );
    }

    // ------------------------------------------------------------------
    // 5. node_domain() correctness for valid shapes.
    // ------------------------------------------------------------------

    #[test]
    fn node_domain_returns_correct_element_count() {
        let shape = IfdsShape::new(2, 3, 5, 0);
        let domain = shape.node_domain().unwrap();
        assert_eq!(domain.element_count(), 30);
    }

    #[test]
    fn node_domain_rejects_zero_dimensions() {
        let shape = IfdsShape::new(0, 1, 1, 0);
        assert!(shape.node_domain().is_err());
    }

    #[test]
    fn node_domain_rejects_overflow_dimensions() {
        let shape = IfdsShape::new(u32::MAX, 1, 1, 0);
        assert!(shape.node_domain().is_err());
    }

    #[test]
    fn node_domain_at_max_limits_succeeds() {
        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
        let domain = shape.node_domain().unwrap();
        assert_eq!(
            domain.element_count() as u64,
            (MAX_PROC_ID as u64 + 1) * (MAX_BLOCK_ID as u64 + 1) * (MAX_FACT_ID as u64)
        );
    }

    // ------------------------------------------------------------------
    // 6. IfdsShape::new with various valid/invalid combinations.
    // ------------------------------------------------------------------

    #[test]
    fn new_with_valid_small_dimensions() {
        let shape = IfdsShape::new(1, 1, 1, 0);
        assert_eq!(shape.num_procs, 1);
        assert_eq!(shape.blocks_per_proc, 1);
        assert_eq!(shape.facts_per_proc, 1);
        assert_eq!(shape.edge_count, 0);
        assert!(shape.fits());
    }

    #[test]
    fn new_with_large_valid_dimensions() {
        // 1000³ = 1_000_000_000 fits comfortably inside u32 and encoding limits.
        let shape = IfdsShape::new(1000, 1000, 1000, 1_000_000);
        assert!(shape.fits());
    }

    #[test]
    fn new_with_invalid_proc_dimension() {
        let shape = IfdsShape::new(0, 1, 1, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn new_with_invalid_block_dimension() {
        let shape = IfdsShape::new(1, 0, 1, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn new_with_invalid_fact_dimension() {
        let shape = IfdsShape::new(1, 1, 0, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn new_preserves_edge_count() {
        let shape = IfdsShape::new(4, 8, 16, 12345);
        assert_eq!(shape.edge_count, 12345);
    }

    #[test]
    fn new_with_all_axes_at_boundary() {
        // Use encoding-max dimensions whose product still fits in u32.
        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, u32::MAX);
        assert!(shape.fits());
        assert_eq!(shape.edge_count, u32::MAX);
    }

    // ------------------------------------------------------------------
    // 7. validate_ifds_problem edge / tuple domain checking.
    // ------------------------------------------------------------------

    #[test]
    fn validate_intra_edge_out_of_domain_proc() {
        let err = validate_ifds_problem(
            "test",
            2,
            4,
            4,
            &[(2, 0, 1)], // proc_id == num_procs is OOB
            &[],
            &[],
            &[],
            &[],
        )
        .expect_err("must error");
        assert!(err.contains("intra edge 0 is out of domain"));
    }

    #[test]
    fn validate_intra_edge_out_of_domain_block() {
        let err = validate_ifds_problem(
            "test",
            2,
            4,
            4,
            &[(0, 4, 1)], // src_block == blocks_per_proc is OOB
            &[],
            &[],
            &[],
            &[],
        )
        .expect_err("must error");
        assert!(err.contains("intra edge 0 is out of domain"));
    }

    #[test]
    fn validate_inter_edge_out_of_domain_src_proc() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(2, 0, 1, 1)], &[], &[], &[])
            .expect_err("must error");
        assert!(err.contains("inter edge 0 is out of domain"));
    }

    #[test]
    fn validate_inter_edge_out_of_domain_dst_proc() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 0, 2, 1)], &[], &[], &[])
            .expect_err("must error");
        assert!(err.contains("inter edge 0 is out of domain"));
    }

    #[test]
    fn validate_flow_gen_out_of_domain() {
        let err = validate_ifds_problem(
            "test",
            2,
            4,
            4,
            &[],
            &[],
            &[(0, 0, 4)], // fact_id == facts_per_proc is OOB
            &[],
            &[],
        )
        .expect_err("must error");
        assert!(err.contains("GEN tuple 0 is out of domain"));
    }

    #[test]
    fn validate_flow_kill_out_of_domain() {
        let err = validate_ifds_problem(
            "test",
            2,
            4,
            4,
            &[],
            &[],
            &[],
            &[(1, 4, 0)], // block_id == blocks_per_proc is OOB
            &[],
        )
        .expect_err("must error");
        assert!(err.contains("KILL tuple 0 is out of domain"));
    }

    #[test]
    fn validate_seed_facts_out_of_domain() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[], &[(0, 0, 4)])
            .expect_err("must error");
        assert!(err.contains("seed tuple 0 is out of domain"));
    }

    #[test]
    fn validate_multiple_intra_edges_first_oob() {
        let err =
            validate_ifds_problem("test", 2, 4, 4, &[(0, 0, 0), (2, 0, 0)], &[], &[], &[], &[])
                .expect_err("must error");
        assert!(err.contains("intra edge 1 is out of domain"));
    }

    #[test]
    fn validate_mixed_valid_and_invalid() {
        // Valid edges but invalid seed fact.
        let err = validate_ifds_problem(
            "test",
            2,
            4,
            4,
            &[(0, 0, 1), (1, 2, 3)],
            &[(0, 0, 1, 1)],
            &[(0, 0, 0)],
            &[(1, 1, 1)],
            &[(0, 0, 4)],
        )
        .expect_err("must error");
        assert!(err.contains("seed tuple 0 is out of domain"));
    }

    #[test]
    fn validate_all_valid_edges_and_tuples() {
        validate_ifds_problem(
            "test",
            4,
            8,
            8,
            &[(0, 0, 1), (1, 2, 3)],
            &[(0, 0, 1, 1), (2, 3, 3, 7)],
            &[(0, 0, 0), (3, 7, 7)],
            &[(1, 1, 1)],
            &[(0, 0, 0), (2, 4, 4)],
        )
        .expect("all valid edges and tuples should succeed");
    }

    #[test]
    fn validate_problem_context_included_in_error() {
        let err = validate_ifds_problem("my_context", 0, 1, 1, &[], &[], &[], &[], &[])
            .expect_err("must error");
        assert!(err.contains("my_context"));
    }

    #[test]
    fn ifds_shape_clone_and_debug() {
        let shape = IfdsShape::new(2, 4, 8, 16);
        let cloned = shape;
        assert_eq!(cloned.num_procs, shape.num_procs);
        let debug = format!("{:?}", shape);
        assert!(debug.contains("IfdsShape"));
    }

    #[test]
    fn ifds_shape_copy_semantics() {
        let a = IfdsShape::new(1, 2, 3, 4);
        let b = a;
        // a is still usable because IfdsShape is Copy.
        assert_eq!(a.num_procs, 1);
        assert_eq!(b.facts_per_proc, 3);
    }

    #[test]
    fn fits_with_two_axes_at_boundary() {
        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, 1, 0);
        assert!(shape.fits());
        let shape = IfdsShape::new(MAX_PROC_ID + 1, 1, MAX_FACT_ID + 1, 0);
        assert!(shape.fits());
        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 1, MAX_FACT_ID + 1, 0);
        assert!(shape.fits());
    }

    #[test]
    fn fits_rejects_two_axes_overflow() {
        let shape = IfdsShape::new(MAX_PROC_ID + 2, MAX_BLOCK_ID + 2, 1, 0);
        assert!(!shape.fits());
        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, MAX_FACT_ID + 2, 0);
        assert!(!shape.fits());
        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, MAX_FACT_ID + 2, 0);
        assert!(!shape.fits());
    }

    #[test]
    fn checked_node_count_for_mid_size_shape() {
        let shape = IfdsShape::new(100, 50, 20, 0);
        assert_eq!(shape.checked_node_count().unwrap(), 100 * 50 * 20);
    }

    #[test]
    fn checked_node_count_rejects_zero_procs() {
        assert!(IfdsShape::new(0, 1, 1, 0).checked_node_count().is_err());
    }

    #[test]
    fn checked_node_count_rejects_zero_blocks() {
        assert!(IfdsShape::new(1, 0, 1, 0).checked_node_count().is_err());
    }

    #[test]
    fn checked_node_count_rejects_zero_facts() {
        assert!(IfdsShape::new(1, 1, 0, 0).checked_node_count().is_err());
    }

    #[test]
    fn node_domain_for_single_node() {
        let domain = IfdsShape::new(1, 1, 1, 0).node_domain().unwrap();
        assert_eq!(domain.element_count(), 1);
    }

    #[test]
    fn node_domain_for_medium_shape() {
        let domain = IfdsShape::new(10, 10, 10, 0).node_domain().unwrap();
        assert_eq!(domain.element_count(), 1000);
    }

    #[test]
    fn validate_inter_edge_out_of_domain_src_block() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 4, 1, 1)], &[], &[], &[])
            .expect_err("must error");
        assert!(err.contains("inter edge 0 is out of domain"));
    }

    #[test]
    fn validate_inter_edge_out_of_domain_dst_block() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 0, 1, 4)], &[], &[], &[])
            .expect_err("must error");
        assert!(err.contains("inter edge 0 is out of domain"));
    }

    #[test]
    fn validate_seed_fact_at_exact_boundary_rejected() {
        // fact_id == facts_per_proc is out of domain.
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[], &[(0, 0, 4)])
            .expect_err("must error");
        assert!(err.contains("seed tuple 0 is out of domain"));
    }

    #[test]
    fn validate_flow_gen_at_exact_boundary_rejected() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[(0, 4, 0)], &[], &[])
            .expect_err("must error");
        assert!(err.contains("GEN tuple 0 is out of domain"));
    }

    #[test]
    fn validate_flow_kill_at_exact_boundary_rejected() {
        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[(2, 0, 0)], &[])
            .expect_err("must error");
        assert!(err.contains("KILL tuple 0 is out of domain"));
    }

    #[test]
    fn new_with_u32_max_edge_count_preserves_value() {
        let shape = IfdsShape::new(1, 1, 1, u32::MAX);
        assert_eq!(shape.edge_count, u32::MAX);
        assert!(shape.fits());
    }

    #[test]
    fn fits_with_all_ones() {
        assert!(IfdsShape::new(1, 1, 1, 1).fits());
    }

    #[test]
    fn node_count_error_contains_weir_prefix() {
        let err = IfdsShape::new(0, 1, 1, 0)
            .checked_node_count()
            .expect_err("must err");
        assert!(err.starts_with("weir IFDS dimensions invalid"));
    }

    #[test]
    fn ifds_shape_certificate_reports_valid_dimensions() {
        let cert = IfdsShape::new(2, 3, 4, 5).certificate();
        assert_eq!(cert.num_procs, 2);
        assert_eq!(cert.blocks_per_proc, 3);
        assert_eq!(cert.facts_per_proc, 4);
        assert_eq!(cert.edge_count, 5);
        assert!(!cert.zero_edge_budget);
        assert!(cert.fits);
        assert_eq!(cert.exploded_nodes, Some(24));
        assert_eq!(cert.bitset_words, Some(1));
        assert_eq!(cert.cap_reason, None);
    }

    #[test]
    fn ifds_shape_certificate_reports_frontier_bitset_width() {
        let cert = IfdsShape::new(1, 33, 1, 1).certificate();
        assert!(cert.fits);
        assert_eq!(cert.exploded_nodes, Some(33));
        assert_eq!(cert.bitset_words, Some(2));
    }

    #[test]
    fn ifds_shape_certificate_preserves_zero_edge_budget() {
        let cert = IfdsShape::new(2, 2, 2, 0).certificate();
        assert!(cert.fits);
        assert!(cert.zero_edge_budget);
        assert_eq!(cert.exploded_nodes, Some(8));
        assert_eq!(cert.bitset_words, Some(1));
        assert_eq!(cert.cap_reason, None);
    }

    #[test]
    fn ifds_shape_certificate_reports_zero_dimension_cap_reason() {
        let cert = IfdsShape::new(0, 1, 1, 0).certificate();
        assert!(!cert.fits);
        assert_eq!(cert.exploded_nodes, None);
        assert_eq!(cert.bitset_words, None);
        let reason = cert.cap_reason.expect("invalid shape must carry cap reason");
        assert!(reason.contains("weir IFDS dimensions invalid"), "{reason}");
        assert!(reason.contains("nonzero"), "{reason}");
    }

    #[test]
    fn ifds_shape_certificate_reports_overflow_cap_reason() {
        let cert = IfdsShape::new(2, 65536, 65536, 0).certificate();
        assert!(!cert.fits);
        assert_eq!(cert.exploded_nodes, None);
        assert_eq!(cert.bitset_words, None);
        let reason = cert.cap_reason.expect("overflow shape must carry cap reason");
        assert!(reason.contains("weir IFDS dimensions invalid"), "{reason}");
    }
}