vyre 0.4.0

// CSR graph serialization used by graph dataflow engines.

use crate::error::{Error, Result};
use crate::ir::validate::limits::{MAX_GRAPH_EDGES, MAX_GRAPH_NODES};


/// Compressed sparse row graph buffers.
///
/// `offsets[node]..offsets[node + 1]` indexes the outgoing targets for a node.
/// `node_data` is domain-owned metadata consumed by graph shaders. A value of
/// zero means no metadata by convention.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CsrGraph {
    /// Edge offsets with length `node_count + 1`.
    pub offsets: Vec<u32>,
    /// Flattened edge targets.
    pub targets: Vec<u32>,
    /// Per-node metadata.
    pub node_data: Vec<u32>,
}


impl CsrGraph {
    /// Number of graph nodes represented by this CSR graph.
    pub fn node_count(&self) -> usize {
        self.node_data.len()
    }

    /// Validate CSR invariants before GPU execution.
    ///
    /// # Errors
    ///
    /// Returns an error when offset lengths, edge counts, monotonicity, or
    /// node ids are invalid. Fix the graph shape and rebuild the CSR buffers.
    pub fn validate(&self) -> Result<()> {
        let expected_offsets = self
            .node_data
            .len()
            .checked_add(1)
            .ok_or_else(|| Error::Csr {
                message: "CsrInvalid: node count overflows usize. Fix: reduce node_data length before building CSR offsets.".to_string(),
            })?;
        if self.offsets.len() != expected_offsets {
            return Err(Error::Csr {
                message: format!(
                    "CsrInvalid: offsets length {} does not equal node_count + 1 ({expected_offsets}). Fix: provide exactly one offset per node plus the final edge-count offset.",
                    self.offsets.len()
                ),
            });
        }
        let Some(&last_offset) = self.offsets.last() else {
            return Err(Error::Csr {
                message: "CsrInvalid: offsets are empty. Fix: provide at least the final zero offset for an empty graph.".to_string(),
            });
        };
        let last_offset_usize = usize::try_from(last_offset).map_err(|error| Error::Csr {
            message: format!(
                "CsrInvalid: final offset {last_offset} cannot fit usize: {error}. Fix: reduce edge count for this target platform."
            ),
        })?;
        if last_offset_usize != self.targets.len() {
            return Err(Error::Csr {
                message: format!(
                    "CsrInvalid: final offset {last_offset} does not equal target count {}. Fix: set the final offset to targets.len().",
                    self.targets.len()
                ),
            });
        }
        for window in self.offsets.windows(2) {
            if window[0] > window[1] {
                return Err(Error::Csr {
                    message: "CsrInvalid: offsets are not monotonically increasing. Fix: sort edges by source and rebuild offsets so each offset is >= the previous offset.".to_string(),
                });
            }
        }
        for &target in &self.targets {
            let target_usize = usize::try_from(target).map_err(|error| Error::Csr {
                message: format!(
                    "CsrInvalid: target {target} cannot fit usize: {error}. Fix: reduce node ids for this target platform."
                ),
            })?;
            if target_usize >= self.node_data.len() {
                return Err(Error::Csr {
                    message: format!(
                        "CsrInvalid: target {target} is outside node_count {}. Fix: remove the edge or increase node_count/node_data to include the target.",
                        self.node_data.len()
                    ),
                });
            }
        }
        Ok(())
    }
}

/// Convert directed edges into CSR buffers.
///
/// # Errors
///
/// Returns an error when graph sizes exceed CSR safety bounds or an edge
/// references a node outside `0..node_count`. Fix the edge list or node count.
pub fn to_csr(node_count: usize, edges: &[(u32, u32)]) -> Result<CsrGraph> {
    try_to_csr(node_count, edges)
}


/// Convert directed edges into CSR buffers and reject invalid node ids.
///
/// # Errors
///
/// Returns an error when `node_count` exceeds graph limits or an edge
/// references a node outside `0..node_count`. Fix the edge list or node count.
pub fn try_to_csr(node_count: usize, edges: &[(u32, u32)]) -> Result<CsrGraph> {
    validate_csr_sizes(node_count, edges.len())?;
    let max_nodes = usize::try_from(u32::MAX).unwrap_or(usize::MAX);
    if node_count > max_nodes {
        return Err(Error::Csr {
            message: format!(
                "GraphTooLarge: node_count {node_count} exceeds u32::MAX. Fix: split the graph or use at most u32::MAX nodes."
            ),
        });
    }
    for (edge_index, &(from, to)) in edges.iter().enumerate() {
        let from_usize = usize::try_from(from).map_err(|error| Error::Csr {
            message: format!(
                "InvalidEdge: edge_index {edge_index} source {from} cannot fit usize: {error}. Fix: Drop or repair edges that reference nonexistent nodes before building the CSR"
            ),
        })?;
        if from_usize >= node_count {
            return Err(Error::Csr {
                message: format!(
                    "InvalidEdge: edge_index {edge_index} source {from} target {to} max {node_count}. Fix: Drop or repair edges that reference nonexistent nodes before building the CSR"
                ),
            });
        }
        let to_usize = usize::try_from(to).map_err(|error| Error::Csr {
            message: format!(
                "InvalidEdge: edge_index {edge_index} target {to} cannot fit usize: {error}. Fix: Drop or repair edges that reference nonexistent nodes before building the CSR"
            ),
        })?;
        if to_usize >= node_count {
            return Err(Error::Csr {
                message: format!(
                    "InvalidEdge: edge_index {edge_index} source {from} target {to} max {node_count}. Fix: Drop or repair edges that reference nonexistent nodes before building the CSR"
                ),
            });
        }
    }
    build_csr(node_count, edges)
}


pub fn validate_csr_sizes(node_count: usize, edge_count: usize) -> Result<()> {
    if node_count > MAX_GRAPH_NODES {
        return Err(Error::Csr {
            message: format!(
                "GraphTooLarge: node_count {node_count} exceeds {MAX_GRAPH_NODES}. Fix: shard the graph before CSR construction."
            ),
        });
    }
    if edge_count > MAX_GRAPH_EDGES {
        return Err(Error::Csr {
            message: format!(
                "GraphTooLarge: edge count {edge_count} exceeds {MAX_GRAPH_EDGES}. Fix: shard the graph before CSR construction."
            ),
        });
    }
    Ok(())
}

pub fn build_csr(node_count: usize, edges: &[(u32, u32)]) -> Result<CsrGraph> {
    let mut adjacency = vec![Vec::<u32>::new(); node_count];
    for &(from, to) in edges {
        let from_index = usize::try_from(from).map_err(|error| Error::Csr {
            message: format!(
                "edge source {from} cannot fit usize during CSR build: {error}. Fix: reject invalid edges before construction."
            ),
        })?;
        let targets = adjacency.get_mut(from_index).ok_or_else(|| Error::Csr {
            message: format!(
                "edge source {from} is outside node_count {node_count} during CSR build. Fix: reject invalid edges before construction."
            ),
        })?;
        targets.push(to);
    }

    let offset_capacity = node_count.checked_add(1).ok_or_else(|| Error::Csr {
        message: "CSR offset capacity overflowed usize. Fix: reduce node_count.".to_string(),
    })?;
    let mut offsets = Vec::with_capacity(offset_capacity);
    let mut targets = Vec::with_capacity(edges.len());
    let mut current_offset = 0u32;
    for outgoing in adjacency {
        offsets.push(current_offset);
        targets.extend(outgoing.iter().copied());
        let outgoing_len = u32::try_from(outgoing.len()).map_err(|error| Error::Csr {
            message: format!(
                "Overflow: context outgoing.len value {} cannot fit u32: {error}. Fix: shard the graph before CSR construction.",
                outgoing.len()
            ),
        })?;
        current_offset = current_offset
            .checked_add(outgoing_len)
            .ok_or_else(|| Error::Csr {
                message:
                    "CSR edge offset overflowed u32. Fix: shard the graph before CSR construction."
                        .to_string(),
            })?;
    }
    offsets.push(current_offset);

    Ok(CsrGraph {
        offsets,
        targets,
        node_data: vec![0; node_count],
    })
}