weir/

graph_layout.rs

//! Shared graph-layout contracts for Weir GPU analyses.
//!
//! Dataflow analyses all consume the same forward CSR shape: node count,
//! row offsets, edge targets, and edge-kind masks. This module centralizes
//! validation and canonicalization so fixed-point, resident, IFDS, slicing,
//! dominators, and range-oriented paths can converge on one layout contract
//! instead of growing analysis-local CSR dialects.

use vyre_primitives::bitset::bitset_words;

/// Shared one-dimensional analysis domain.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct LinearDomain {
    element_count: u32,
}

impl LinearDomain {
    /// Build a linear analysis domain.
    #[inline]
    #[must_use]
    pub const fn new(element_count: u32) -> Self {
        Self { element_count }
    }

    /// Number of logical elements in the domain.
    #[inline]
    #[must_use]
    pub const fn element_count(self) -> u32 {
        self.element_count
    }

    /// Number of u32 words required to represent this domain as a bitset.
    #[inline]
    #[must_use]
    pub fn bitset_words(self) -> u32 {
        bitset_words(self.element_count)
    }

    /// Number of u32 slots required when every element owns `slots_per_element`
    /// scalar lanes.
    pub fn scalar_slots(self, stage: &str, slots_per_element: u32) -> Result<u32, String> {
        self.element_count
            .checked_mul(slots_per_element)
            .map(|slots| slots.max(1))
            .ok_or_else(|| {
                format!(
                    "{stage} element_count={} with {slots_per_element} slot(s) per element overflows u32 buffer slots. Fix: shard the analysis domain before building the GPU Program.",
                    self.element_count
                )
            })
    }
}

/// Borrowed CSR graph view shared by Weir analyses.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct CsrGraph<'a> {
    /// Number of graph nodes in the analysis domain.
    pub node_count: u32,
    /// CSR row offsets, length `node_count + 1`.
    pub edge_offsets: &'a [u32],
    /// CSR edge targets.
    pub edge_targets: &'a [u32],
    /// CSR edge-kind masks, length equal to `edge_targets`.
    pub edge_kind_mask: &'a [u32],
}

impl<'a> CsrGraph<'a> {
    /// Build a borrowed CSR graph view.
    #[inline]
    #[must_use]
    pub fn new(
        node_count: u32,
        edge_offsets: &'a [u32],
        edge_targets: &'a [u32],
        edge_kind_mask: &'a [u32],
    ) -> Self {
        Self {
            node_count,
            edge_offsets,
            edge_targets,
            edge_kind_mask,
        }
    }

    /// Validate this graph against the shared Weir CSR ABI.
    pub fn validate(self, stage: &str) -> Result<Self, String> {
        crate::dispatch_decode::require_csr_shape(
            stage,
            self.node_count,
            self.edge_offsets,
            self.edge_targets,
            self.edge_kind_mask,
        )?;
        Ok(self)
    }

    /// Validate and canonicalize rows into sorted, duplicate-free edge order.
    pub fn normalize(self, stage: &str) -> Result<NormalizedCsrGraph, String> {
        let mut normalized = NormalizedCsrGraph::empty();
        let mut scratch = CsrGraphNormalizationScratch::new();
        self.normalize_with_edge_kind_map_into(
            stage,
            false,
            |mask| mask,
            &mut normalized,
            &mut scratch,
        )?;
        Ok(normalized)
    }

    /// Validate and canonicalize rows after masking each edge-kind word.
    ///
    /// This avoids analysis-local temporary `Vec<u32>` filters before graph
    /// normalization. Analyses such as points-to can keep a single shared CSR
    /// contract while applying their allowed-edge predicate during packing.
    pub fn normalize_with_edge_kind_mask(
        self,
        stage: &str,
        allowed_mask: u32,
    ) -> Result<NormalizedCsrGraph, String> {
        let mut normalized = NormalizedCsrGraph::empty();
        let mut scratch = CsrGraphNormalizationScratch::new();
        self.normalize_with_edge_kind_map_into(
            stage,
            true,
            |mask| mask & allowed_mask,
            &mut normalized,
            &mut scratch,
        )?;
        Ok(normalized)
    }

    /// Validate and canonicalize rows into caller-owned output and scratch.
    pub fn normalize_into(
        self,
        stage: &str,
        output: &mut NormalizedCsrGraph,
        scratch: &mut CsrGraphNormalizationScratch,
    ) -> Result<(), String> {
        self.normalize_with_edge_kind_map_into(stage, false, |mask| mask, output, scratch)
    }

    /// Validate and canonicalize rows after masking into caller-owned buffers.
    pub fn normalize_with_edge_kind_mask_into(
        self,
        stage: &str,
        allowed_mask: u32,
        output: &mut NormalizedCsrGraph,
        scratch: &mut CsrGraphNormalizationScratch,
    ) -> Result<(), String> {
        self.normalize_with_edge_kind_map_into(
            stage,
            true,
            |mask| mask & allowed_mask,
            output,
            scratch,
        )
    }

    fn normalize_with_edge_kind_map_into<F>(
        self,
        stage: &str,
        drop_zero_mapped_edges: bool,
        mut map_edge_kind: F,
        output: &mut NormalizedCsrGraph,
        scratch: &mut CsrGraphNormalizationScratch,
    ) -> Result<(), String>
    where
        F: FnMut(u32) -> u32,
    {
        self.validate(stage)?;
        let nodes = usize::try_from(self.node_count).map_err(|_| {
            format!("{stage} node_count={} cannot fit usize during CSR normalization. Fix: shard the graph before dispatch.", self.node_count)
        })?;
        let offset_capacity = nodes.checked_add(1).ok_or_else(|| {
            format!(
                "{stage} node_count={} overflows CSR offset capacity. Fix: shard the graph before dispatch.",
                self.node_count
            )
        })?;
        output.clear();
        crate::staging_reserve::reserve_vec(
            &mut output.edge_offsets,
            offset_capacity,
            "CSR normalized row offset",
        )?;
        crate::staging_reserve::reserve_vec(
            &mut output.edge_targets,
            self.edge_targets.len(),
            "CSR normalized edge target",
        )?;
        crate::staging_reserve::reserve_vec(
            &mut output.edge_kind_mask,
            self.edge_kind_mask.len(),
            "CSR normalized edge-kind mask",
        )?;
        output.edge_offsets.push(0);
        for node in 0..nodes {
            let start = crate::dispatch_decode::u32_to_usize(
                self.edge_offsets[node],
                "CSR normalization row start offset",
            )?;
            let end = crate::dispatch_decode::u32_to_usize(
                self.edge_offsets[node + 1],
                "CSR normalization row end offset",
            )?;
            let row_len = end.checked_sub(start).ok_or_else(|| {
                format!(
                    "{stage} CSR offsets decreased at node {node}: start={start}, end={end}. Fix: pass monotonically increasing edge offsets."
                )
            })?;
            if row_len <= 1 {
                if start != end {
                    let mapped = map_edge_kind(self.edge_kind_mask[start]);
                    if !(drop_zero_mapped_edges && mapped == 0) {
                        output.edge_targets.push(self.edge_targets[start]);
                        output.edge_kind_mask.push(mapped);
                    }
                }
                let offset = u32::try_from(output.edge_targets.len()).map_err(|error| {
                    format!(
                        "{stage} normalized CSR row {node} offset does not fit u32: {error}. Fix: shard the ProgramGraph before GPU dispatch."
                    )
                })?;
                output.edge_offsets.push(offset);
                continue;
            }
            scratch.row.clear();
            let output_row_start = output.edge_targets.len();
            let mut previous_direct_target = None;
            let mut direct_sorted_unique = true;
            for (&target, &mask) in self.edge_targets[start..end]
                .iter()
                .zip(self.edge_kind_mask[start..end].iter())
            {
                let mapped = map_edge_kind(mask);
                if drop_zero_mapped_edges && mapped == 0 {
                    continue;
                }
                if let Some(previous) = previous_direct_target {
                    if target <= previous {
                        direct_sorted_unique = false;
                    }
                }
                previous_direct_target = Some(target);
                output.edge_targets.push(target);
                output.edge_kind_mask.push(mapped);
            }
            if direct_sorted_unique {
                let offset = u32::try_from(output.edge_targets.len()).map_err(|error| {
                    format!(
                        "{stage} normalized CSR row {node} offset does not fit u32: {error}. Fix: shard the ProgramGraph before GPU dispatch."
                    )
                })?;
                output.edge_offsets.push(offset);
                continue;
            }
            let output_row_len =
                output.edge_targets.len().checked_sub(output_row_start).ok_or_else(|| {
                    format!(
                        "{stage} normalized CSR output row start exceeded target length at node {node}. Fix: rebuild the graph normalization state before dispatch."
                    )
                })?;
            crate::staging_reserve::reserve_vec(
                &mut scratch.row,
                output_row_len,
                "CSR graph normalization row scratch",
            )?;
            scratch.row.extend(
                output.edge_targets[output_row_start..]
                    .iter()
                    .copied()
                    .zip(output.edge_kind_mask[output_row_start..].iter().copied()),
            );
            output.edge_targets.truncate(output_row_start);
            output.edge_kind_mask.truncate(output_row_start);
            scratch.row.sort_unstable_by_key(|(target, _)| *target);
            let mut merged = 0usize;
            for idx in 0..scratch.row.len() {
                if merged != 0 && scratch.row[merged - 1].0 == scratch.row[idx].0 {
                    scratch.row[merged - 1].1 |= scratch.row[idx].1;
                } else {
                    scratch.row[merged] = scratch.row[idx];
                    merged += 1;
                }
            }
            output
                .edge_targets
                .extend(scratch.row[..merged].iter().map(|(target, _)| *target));
            output
                .edge_kind_mask
                .extend(scratch.row[..merged].iter().map(|(_, mask)| *mask));
            let offset = u32::try_from(output.edge_targets.len()).map_err(|error| {
                format!(
                    "{stage} normalized CSR row {node} offset does not fit u32: {error}. Fix: shard the ProgramGraph before GPU dispatch."
                )
            })?;
            output.edge_offsets.push(offset);
        }
        let edge_count = u32::try_from(output.edge_targets.len()).map_err(|error| {
            format!(
                "{stage} normalized edge target count does not fit u32: {error}. Fix: shard the ProgramGraph before GPU dispatch."
            )
        })?;
        output.node_count = self.node_count;
        output.edge_count = edge_count;
        output.stable_layout_hash = stable_csr_layout_hash(
            self.node_count,
            edge_count,
            &output.edge_offsets,
            &output.edge_targets,
            &output.edge_kind_mask,
        );
        Ok(())
    }
}

/// Caller-owned scratch for CSR graph normalization.
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct CsrGraphNormalizationScratch {
    row: Vec<(u32, u32)>,
}

impl CsrGraphNormalizationScratch {
    /// Create empty reusable normalization scratch.
    #[inline]
    #[must_use]
    pub const fn new() -> Self {
        Self { row: Vec::new() }
    }

    /// Create reusable normalization scratch with row capacity.
    #[inline]
    #[must_use]
    #[cfg(any(test, feature = "legacy-infallible"))]
    pub fn with_row_capacity(row_capacity: usize) -> Self {
        Self::try_with_row_capacity(row_capacity)
            .expect("CSR graph normalization scratch allocation failed. Fix: shard the graph before preparing fixed-point analysis state.")
    }

    /// Create reusable normalization scratch with a fallible row reservation.
    #[inline]
    pub fn try_with_row_capacity(row_capacity: usize) -> Result<Self, String> {
        let mut scratch = Self::new();
        crate::staging_reserve::reserve_vec(
            &mut scratch.row,
            row_capacity,
            "CSR graph normalization row scratch",
        )?;
        Ok(scratch)
    }

    /// Retained row capacity.
    #[inline]
    #[must_use]
    pub fn row_capacity(&self) -> usize {
        self.row.capacity()
    }
}

/// Owned canonical CSR layout for cache keys, packed graph state, and reuse.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct NormalizedCsrGraph {
    node_count: u32,
    edge_count: u32,
    stable_layout_hash: u64,
    edge_offsets: Vec<u32>,
    edge_targets: Vec<u32>,
    edge_kind_mask: Vec<u32>,
}

impl NormalizedCsrGraph {
    /// Create an empty reusable normalized graph output.
    #[inline]
    #[must_use]
    pub const fn empty() -> Self {
        Self {
            node_count: 0,
            edge_count: 0,
            stable_layout_hash: 0,
            edge_offsets: Vec::new(),
            edge_targets: Vec::new(),
            edge_kind_mask: Vec::new(),
        }
    }

    #[inline]
    fn clear(&mut self) {
        self.node_count = 0;
        self.edge_count = 0;
        self.stable_layout_hash = 0;
        self.edge_offsets.clear();
        self.edge_targets.clear();
        self.edge_kind_mask.clear();
    }

    /// Number of nodes in the normalized graph domain.
    #[inline]
    #[must_use]
    pub fn node_count(&self) -> u32 {
        self.node_count
    }

    /// Number of canonical edges after duplicate row entries are removed.
    #[inline]
    #[must_use]
    pub fn edge_count(&self) -> u32 {
        self.edge_count
    }

    /// Canonical CSR row offsets.
    #[inline]
    #[must_use]
    pub fn edge_offsets(&self) -> &[u32] {
        &self.edge_offsets
    }

    /// Canonical CSR edge targets.
    #[inline]
    #[must_use]
    pub fn edge_targets(&self) -> &[u32] {
        &self.edge_targets
    }

    /// Canonical CSR edge-kind masks.
    #[inline]
    #[must_use]
    pub fn edge_kind_mask(&self) -> &[u32] {
        &self.edge_kind_mask
    }

    /// Retained canonical offset capacity.
    #[inline]
    #[must_use]
    pub fn edge_offsets_capacity(&self) -> usize {
        self.edge_offsets.capacity()
    }

    /// Retained canonical target capacity.
    #[inline]
    #[must_use]
    pub fn edge_targets_capacity(&self) -> usize {
        self.edge_targets.capacity()
    }

    /// Retained canonical edge-kind capacity.
    #[inline]
    #[must_use]
    pub fn edge_kind_mask_capacity(&self) -> usize {
        self.edge_kind_mask.capacity()
    }

    /// Stable hash of the canonical CSR graph layout.
    ///
    /// Cache identity belongs to the shared graph contract: domain size,
    /// canonical row offsets, targets, and edge-kind masks. It intentionally
    /// excludes transient dispatch buffers such as zeroed ProgramGraph node
    /// arrays.
    #[inline]
    #[must_use]
    pub fn stable_layout_hash(&self) -> u64 {
        self.stable_layout_hash
    }
}

const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

#[inline]
fn mix_layout_bytes(mut hash: u64, bytes: &[u8]) -> u64 {
    for byte in bytes {
        hash ^= u64::from(*byte);
        hash = hash.wrapping_mul(FNV_PRIME);
    }
    hash
}

#[inline]
fn mix_layout_words(hash: u64, words: &[u32]) -> u64 {
    #[cfg(target_endian = "little")]
    {
        mix_layout_bytes(hash, bytemuck::cast_slice(words))
    }
    #[cfg(target_endian = "big")]
    {
        for word in words {
            hash = mix_layout_bytes(hash, &word.to_le_bytes());
        }
        hash
    }
}

/// Stable hash for canonical Weir CSR layouts.
#[must_use]
pub fn stable_csr_layout_hash(
    node_count: u32,
    edge_count: u32,
    edge_offsets: &[u32],
    edge_targets: &[u32],
    edge_kind_mask: &[u32],
) -> u64 {
    let mut hash = FNV_OFFSET;
    hash = mix_layout_bytes(hash, &node_count.to_le_bytes());
    hash = mix_layout_bytes(hash, &edge_count.to_le_bytes());
    hash = mix_layout_words(hash, edge_offsets);
    hash = mix_layout_words(hash, edge_targets);
    mix_layout_words(hash, edge_kind_mask)
}

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

    #[test]
    fn linear_domain_computes_bitset_and_scalar_slots() {
        let domain = LinearDomain::new(65);

        assert_eq!(domain.element_count(), 65);
        assert_eq!(domain.bitset_words(), 3);
        assert_eq!(
            domain
                .scalar_slots("shared linear domain scalar test", 2)
                .expect("scalar slots must fit"),
            130
        );
    }

    #[test]
    fn linear_domain_rejects_scalar_slot_overflow() {
        let err = LinearDomain::new(u32::MAX)
            .scalar_slots("shared linear domain overflow test", 2)
            .expect_err("slot multiplication must fail loudly");
        assert!(err.contains("overflows"), "unexpected diagnostic: {err}");
    }

    #[test]
    fn csr_graph_rejects_mismatched_masks() {
        let err = CsrGraph::new(2, &[0, 1, 1], &[1], &[])
            .validate("shared graph layout test")
            .expect_err("mask length must match final CSR edge count");
        assert!(
            err.contains("edge_kind_mask"),
            "unexpected diagnostic: {err}"
        );
    }

    #[test]
    fn csr_graph_normalizes_rows_for_shared_cache_keys() {
        let graph = CsrGraph::new(
            3,
            &[0, 3, 4, 4],
            &[2, 1, 1, 2],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CALL_ARG,
                vyre_primitives::predicate::edge_kind::CONTROL,
            ],
        )
        .normalize("shared graph layout normalize test")
        .expect("valid graph must normalize");

        assert_eq!(graph.node_count(), 3);
        assert_eq!(graph.edge_count(), 3);
        assert_eq!(graph.edge_offsets(), &[0, 2, 3, 3]);
        assert_eq!(graph.edge_targets(), &[1, 2, 2]);
        assert_eq!(
            graph.edge_kind_mask(),
            &[
                vyre_primitives::predicate::edge_kind::ASSIGNMENT
                    | vyre_primitives::predicate::edge_kind::CALL_ARG,
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::CONTROL,
            ]
        );
    }

    #[test]
    fn csr_graph_singleton_rows_normalize_without_sort_scratch_growth() {
        let mut normalized = NormalizedCsrGraph::empty();
        let mut scratch = CsrGraphNormalizationScratch::new();
        CsrGraph::new(
            5,
            &[0, 1, 1, 2, 2, 3],
            &[3, 4, 1],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CALL_ARG,
            ],
        )
        .normalize_into(
            "shared graph layout singleton-row fast path test",
            &mut normalized,
            &mut scratch,
        )
        .expect("singleton-heavy graph must normalize");

        assert_eq!(normalized.edge_offsets(), &[0, 1, 1, 2, 2, 3]);
        assert_eq!(normalized.edge_targets(), &[3, 4, 1]);
        assert_eq!(
            normalized.edge_kind_mask(),
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CALL_ARG,
            ]
        );
        assert!(
            scratch.row_capacity() <= 1,
            "Fix: singleton CSR rows should not grow normalization scratch for sort/dedup work"
        );
    }

    #[test]
    fn csr_graph_sorted_unique_multi_rows_bypass_sort_scratch() {
        let mut normalized = NormalizedCsrGraph::empty();
        let mut scratch = CsrGraphNormalizationScratch::new();
        CsrGraph::new(
            5,
            &[0, 3, 5, 5, 5, 5],
            &[1, 2, 4, 0, 2],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CALL_ARG,
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
            ],
        )
        .normalize_into(
            "shared graph layout sorted-row fast path test",
            &mut normalized,
            &mut scratch,
        )
        .expect("sorted unique rows must normalize without scratch sorting");

        assert_eq!(normalized.edge_offsets(), &[0, 3, 5, 5, 5, 5]);
        assert_eq!(normalized.edge_targets(), &[1, 2, 4, 0, 2]);
        assert_eq!(
            scratch.row_capacity(),
            0,
            "Fix: already-canonical multi-edge rows must append directly without row scratch growth."
        );
    }

    #[test]
    fn csr_graph_normalizes_into_caller_owned_buffers_without_reallocating() {
        let mut normalized = NormalizedCsrGraph::empty();
        let mut scratch = CsrGraphNormalizationScratch::with_row_capacity(8);
        CsrGraph::new(
            3,
            &[0, 3, 4, 4],
            &[2, 1, 1, 2],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CALL_ARG,
                vyre_primitives::predicate::edge_kind::CONTROL,
            ],
        )
        .normalize_into(
            "shared graph layout normalize into scratch test",
            &mut normalized,
            &mut scratch,
        )
        .expect("first graph must normalize into reusable buffers");
        let offsets_capacity = normalized.edge_offsets.capacity();
        let targets_capacity = normalized.edge_targets.capacity();
        let masks_capacity = normalized.edge_kind_mask.capacity();
        let row_capacity = scratch.row_capacity();
        let first_hash = normalized.stable_layout_hash();

        CsrGraph::new(
            3,
            &[0, 2, 3, 3],
            &[1, 2, 2],
            &[
                vyre_primitives::predicate::edge_kind::ASSIGNMENT
                    | vyre_primitives::predicate::edge_kind::CALL_ARG,
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::CONTROL,
            ],
        )
        .normalize_into(
            "shared graph layout normalize into scratch test",
            &mut normalized,
            &mut scratch,
        )
        .expect("equivalent canonical graph must reuse normalization buffers");

        assert_eq!(normalized.stable_layout_hash(), first_hash);
        assert_eq!(normalized.edge_offsets.capacity(), offsets_capacity);
        assert_eq!(normalized.edge_targets.capacity(), targets_capacity);
        assert_eq!(normalized.edge_kind_mask.capacity(), masks_capacity);
        assert_eq!(scratch.row_capacity(), row_capacity);
    }

    #[test]
    fn csr_graph_masks_edge_kinds_during_normalization_without_prefilter() {
        let graph = CsrGraph::new(
            2,
            &[0, 2, 2],
            &[1, 1],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL
                    | vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::DOMINANCE,
            ],
        )
        .normalize_with_edge_kind_mask(
            "shared graph layout masked normalize test",
            vyre_primitives::predicate::edge_kind::ASSIGNMENT,
        )
        .expect("valid graph must normalize with masked edge kinds");

        assert_eq!(graph.edge_targets(), &[1]);
        assert_eq!(
            graph.edge_kind_mask(),
            &[vyre_primitives::predicate::edge_kind::ASSIGNMENT]
        );
    }

    #[test]
    fn csr_graph_preserves_zero_mask_singletons_during_normalization() {
        let graph = CsrGraph::new(2, &[0, 2, 2], &[1, 1], &[0, 0])
            .normalize("shared graph layout zero-mask singleton normalize test")
            .expect("valid graph must normalize zero-mask singleton edges");

        assert_eq!(graph.edge_count(), 1);
        assert_eq!(graph.edge_offsets(), &[0, 1, 1]);
        assert_eq!(graph.edge_targets(), &[1]);
        assert_eq!(graph.edge_kind_mask(), &[0]);
    }

    #[test]
    fn masked_normalization_drops_edges_that_cannot_fire() {
        let graph = CsrGraph::new(
            3,
            &[0, 2, 3, 3],
            &[1, 2, 2],
            &[
                vyre_primitives::predicate::edge_kind::CONTROL,
                vyre_primitives::predicate::edge_kind::ASSIGNMENT,
                vyre_primitives::predicate::edge_kind::CONTROL,
            ],
        )
        .normalize_with_edge_kind_mask(
            "shared graph layout masked normalize test",
            vyre_primitives::predicate::edge_kind::ASSIGNMENT,
        )
        .expect("valid graph must normalize under mask");

        assert_eq!(graph.edge_count(), 1);
        assert_eq!(graph.edge_offsets(), &[0, 1, 1, 1]);
        assert_eq!(graph.edge_targets(), &[2]);
        assert_eq!(
            graph.edge_kind_mask(),
            &[vyre_primitives::predicate::edge_kind::ASSIGNMENT]
        );
    }

    #[test]
    fn csr_graph_rejects_zero_node_graph_with_non_empty_edges() {
        let err = CsrGraph::new(0, &[1], &[0], &[0])
            .validate("test")
            .expect_err("zero-node with edges");
        assert!(err.contains("edge_offsets[0]"), "{err}");
    }

    #[test]
    fn csr_graph_rejects_nonzero_first_offset() {
        let err = CsrGraph::new(2, &[1, 1, 1], &[0], &[0])
            .validate("test")
            .expect_err("nonzero first offset");
        assert!(err.contains("edge_offsets[0]"), "{err}");
    }

    #[test]
    fn csr_graph_rejects_missing_sentinel_offset() {
        let err = CsrGraph::new(2, &[0, 1], &[0], &[0])
            .validate("test")
            .expect_err("missing sentinel");
        assert!(err.contains("expected exactly node_count + 1"), "{err}");
    }

    #[test]
    fn csr_graph_rejects_target_outside_domain() {
        let err = CsrGraph::new(2, &[0, 1, 1], &[2], &[0])
            .validate("test")
            .expect_err("OOB target");
        assert!(err.contains("targets node 2"), "{err}");
    }

    #[test]
    fn csr_graph_rejects_mismatched_edge_kind_mask() {
        let err = CsrGraph::new(2, &[0, 1, 1], &[0], &[0, 0])
            .validate("test")
            .expect_err("mask mismatch");
        assert!(err.contains("edge_kind_mask"), "{err}");
    }

    #[test]
    fn normalize_rejects_non_monotonic_offsets() {
        let err = CsrGraph::new(3, &[0, 1, 0, 1], &[0], &[0])
            .normalize("test")
            .expect_err("non-monotonic");
        assert!(err.contains("not monotonic"), "{err}");
    }

    #[test]
    fn normalize_rejects_mismatched_edge_target_count() {
        let err = CsrGraph::new(2, &[0, 1, 2], &[0], &[0])
            .normalize("test")
            .expect_err("mismatched edge target count");
        assert!(err.contains("edge_targets has 1"), "{err}");
    }

    #[test]
    fn linear_domain_rejects_scalar_slot_overflow_large() {
        let err = LinearDomain::new(u32::MAX)
            .scalar_slots("test", 2)
            .expect_err("overflow");
        assert!(err.contains("overflows"), "{err}");
    }

    #[test]
    fn linear_domain_scalar_slots_returns_one_for_zero() {
        assert_eq!(LinearDomain::new(0).scalar_slots("test", 2).unwrap(), 1);
    }
}