ontomark_ngg1/
encode.rs

1//! The NGG1 encoder and the record types it consumes.
2//!
3//! Provenance: the byte-writing code, [`Csr`] and [`build_csr`] are the
4//! VisionClaw `crates/vault/src/build/ngg1.rs` writer at `1044b0722`, moved
5//! here from `ontomark-compile`; the output is held byte-identical to it by
6//! the conformance suite. Compared with that code, the sanity checks that were
7//! `assert!`s are now typed [`EncodeError`]s. The layout algorithms stayed in
8//! `ontomark-compile`. Derived in part from vowl-wasm 0.1.2 (MIT, Copyright
9//! (c) 2025-2026 DreamLab-AI).
10
11use core::fmt;
12
13use crate::{HEADER_SIZE, MAGIC, NODE_STRIDE, VERSION};
14
15/// One graph node as stored in a tier, in local-index order.
16///
17/// This is the owned form of [`NodeRecord`](crate::NodeRecord) plus the two
18/// strings. Positions are `f32` because that is what the file stores;
19/// producers that lay out in `f64` narrow with `as f32` exactly once.
20///
21/// ```
22/// use ontomark_ngg1::{GraphNode, CATEGORY_NONE, DOMAIN_NONE};
23///
24/// let node = GraphNode {
25///     id: 7,
26///     x: 1.5,
27///     y: -2.0,
28///     domain: DOMAIN_NONE,
29///     category: CATEGORY_NONE,
30///     flags: 0,
31///     degree: 0,
32///     label: "Café".to_owned(),
33///     iri: "https://example.org/cafe".to_owned(),
34/// };
35/// assert_eq!(node.label.chars().count(), 4);
36/// ```
37#[derive(Debug, Clone, PartialEq)]
38pub struct GraphNode {
39    /// Stable external id, shared across tiers.
40    pub id: u32,
41    /// Seed x position.
42    pub x: f32,
43    /// Seed y position.
44    pub y: f32,
45    /// Domain id, or [`DOMAIN_NONE`](crate::DOMAIN_NONE).
46    pub domain: u16,
47    /// Category id, or [`CATEGORY_NONE`](crate::CATEGORY_NONE).
48    pub category: u16,
49    /// Flag bits (`FLAG_*`).
50    pub flags: u8,
51    /// Full-graph incident degree.
52    pub degree: u32,
53    /// Display label.
54    pub label: String,
55    /// Canonical IRI.
56    pub iri: String,
57}
58
59/// Compressed sparse row adjacency.
60///
61/// ```
62/// let csr = ontomark_ngg1::build_csr(2, &[(0, 1, 0)]);
63/// assert_eq!(csr.row_ptr, vec![0, 1, 1]);
64/// ```
65#[derive(Debug, Clone, Default, PartialEq, Eq)]
66pub struct Csr {
67    /// `nodes + 1` offsets into [`Csr::col_idx`].
68    pub row_ptr: Vec<u32>,
69    /// Target local indices.
70    pub col_idx: Vec<u32>,
71    /// One edge type per entry of [`Csr::col_idx`].
72    pub edge_type: Vec<u8>,
73}
74
75/// A decoded tier: nodes plus adjacency. Produced by
76/// [`Ngg1::to_graph`](crate::Ngg1::to_graph) and written by [`Graph::encode`].
77#[derive(Debug, Clone, Default, PartialEq)]
78pub struct Graph {
79    /// Nodes in local-index order.
80    pub nodes: Vec<GraphNode>,
81    /// Adjacency over the local indices of [`Graph::nodes`].
82    pub csr: Csr,
83}
84
85impl Graph {
86    /// Serialise with [`encode`].
87    ///
88    /// # Errors
89    /// As [`encode`].
90    pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
91        encode(&self.nodes, &self.csr)
92    }
93}
94
95/// Build CSR from directed `(src_local, tgt_local, edge_type)` triples.
96///
97/// Edges arrive pre-ordered per source (backbone before relations); this only
98/// groups them, preserving arrival order within a source.
99///
100/// # Panics
101/// When a source index is not below `num_nodes`.
102///
103/// ```
104/// let csr = ontomark_ngg1::build_csr(3, &[(0, 1, 0), (0, 2, 1), (2, 0, 0)]);
105/// assert_eq!(csr.row_ptr, vec![0, 2, 2, 3]);
106/// assert_eq!(csr.col_idx, vec![1, 2, 0]);
107/// assert_eq!(csr.edge_type, vec![0, 1, 0]);
108/// ```
109#[must_use]
110pub fn build_csr(num_nodes: usize, edges: &[(u32, u32, u8)]) -> Csr {
111    let mut counts = vec![0u32; num_nodes];
112    for (src, _, _) in edges {
113        counts[*src as usize] += 1;
114    }
115    let mut row_ptr = vec![0u32; num_nodes + 1];
116    for i in 0..num_nodes {
117        row_ptr[i + 1] = row_ptr[i] + counts[i];
118    }
119    let mut col_idx = vec![0u32; edges.len()];
120    let mut edge_type = vec![0u8; edges.len()];
121    let mut cursor: Vec<u32> = row_ptr[..num_nodes].to_vec();
122    for (src, tgt, t) in edges {
123        let p = cursor[*src as usize] as usize;
124        col_idx[p] = *tgt;
125        edge_type[p] = *t;
126        cursor[*src as usize] += 1;
127    }
128    Csr {
129        row_ptr,
130        col_idx,
131        edge_type,
132    }
133}
134
135/// Why [`encode`] refused its input.
136#[derive(Debug, Clone, PartialEq, Eq)]
137#[non_exhaustive]
138pub enum EncodeError {
139    /// `row_ptr` is not `nodes + 1` long.
140    RowPtrLength {
141        /// Length found.
142        found: usize,
143        /// Length required.
144        expected: usize,
145    },
146    /// `edge_type` is not as long as `col_idx`.
147    EdgeTypeLength {
148        /// Length found.
149        found: usize,
150        /// Length required.
151        expected: usize,
152    },
153    /// `row_ptr` does not start at 0, decreases, or does not end at the edge count.
154    RowPtr {
155        /// Index into `row_ptr` where the rule first fails.
156        index: usize,
157    },
158    /// An edge target is not a node index.
159    EdgeTarget {
160        /// Edge slot.
161        edge: usize,
162        /// Target found.
163        target: u32,
164    },
165    /// A count or offset does not fit the format's `u32` fields.
166    TooLarge,
167}
168
169impl fmt::Display for EncodeError {
170    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171        match self {
172            Self::RowPtrLength { found, expected } => {
173                write!(f, "row_ptr length {found}, expected {expected}")
174            }
175            Self::EdgeTypeLength { found, expected } => {
176                write!(f, "edge_type length {found}, expected {expected}")
177            }
178            Self::RowPtr { index } => write!(f, "row_ptr[{index}] breaks the CSR invariants"),
179            Self::EdgeTarget { edge, target } => {
180                write!(f, "edge {edge} targets node {target}, which does not exist")
181            }
182            Self::TooLarge => f.write_str("graph exceeds the u32 limits of the NGG1 format"),
183        }
184    }
185}
186
187impl std::error::Error for EncodeError {}
188
189const fn pad4(n: usize) -> usize {
190    (4 - (n & 3)) & 3
191}
192
193fn to_u32(v: usize) -> Result<u32, EncodeError> {
194    u32::try_from(v).map_err(|_| EncodeError::TooLarge)
195}
196
197/// Serialise one tier to NGG1 bytes.
198///
199/// `nodes` are in local-index order and `csr.col_idx` holds local indices.
200/// The input is checked first: whatever this returns, [`Ngg1::parse`] accepts.
201///
202/// # Errors
203/// An [`EncodeError`] when `csr` is inconsistent with `nodes` or the graph is
204/// too large for the format's `u32` fields.
205///
206/// ```
207/// use ontomark_ngg1::{build_csr, encode, GraphNode, Ngg1, DOMAIN_NONE, CATEGORY_NONE};
208///
209/// let nodes: Vec<GraphNode> = (0..3)
210///     .map(|i| GraphNode {
211///         id: i,
212///         x: 0.0,
213///         y: 0.0,
214///         domain: DOMAIN_NONE,
215///         category: CATEGORY_NONE,
216///         flags: 0,
217///         degree: 0,
218///         label: format!("N{i}"),
219///         iri: format!("urn:n:{i}"),
220///     })
221///     .collect();
222/// let bytes = encode(&nodes, &build_csr(3, &[(0, 1, 0), (1, 2, 1), (2, 0, 1)]))?;
223/// // 32 header + 3 * 24 nodes + 16 row_ptr + 12 col_idx + (3 types + 1 pad) + strings
224/// assert_eq!(&bytes[..4], b"NGG1");
225/// assert_eq!(Ngg1::parse(&bytes)?.edge_count(), 3);
226/// # Ok::<(), Box<dyn std::error::Error>>(())
227/// ```
228///
229/// [`Ngg1::parse`]: crate::Ngg1::parse
230pub fn encode(nodes: &[GraphNode], csr: &Csr) -> Result<Vec<u8>, EncodeError> {
231    let node_count = nodes.len();
232    let edge_count = csr.col_idx.len();
233    if csr.row_ptr.len() != node_count + 1 {
234        return Err(EncodeError::RowPtrLength {
235            found: csr.row_ptr.len(),
236            expected: node_count + 1,
237        });
238    }
239    if csr.edge_type.len() != edge_count {
240        return Err(EncodeError::EdgeTypeLength {
241            found: csr.edge_type.len(),
242            expected: edge_count,
243        });
244    }
245    let mut last = 0u32;
246    if csr.row_ptr[0] != 0 {
247        return Err(EncodeError::RowPtr { index: 0 });
248    }
249    for (i, &v) in csr.row_ptr.iter().enumerate().skip(1) {
250        if v < last || v as usize > edge_count {
251            return Err(EncodeError::RowPtr { index: i });
252        }
253        last = v;
254    }
255    if last as usize != edge_count {
256        return Err(EncodeError::RowPtr { index: node_count });
257    }
258    if let Some((edge, &target)) = csr
259        .col_idx
260        .iter()
261        .enumerate()
262        .find(|&(_, &t)| t as usize >= node_count)
263    {
264        return Err(EncodeError::EdgeTarget { edge, target });
265    }
266
267    // Layout arithmetic in u64 so a 32-bit target cannot wrap before the check.
268    let n = node_count as u64;
269    let e = edge_count as u64;
270    let off_nodes = HEADER_SIZE as u64;
271    let off_adjacency = off_nodes + n * NODE_STRIDE as u64;
272    let off_edge_types = off_adjacency + (n + 1) * 4 + e * 4;
273    let off_strings = off_edge_types + e + pad4(edge_count) as u64;
274    let off_nodes = HEADER_SIZE as u32;
275    let off_adjacency = u32::try_from(off_adjacency).map_err(|_| EncodeError::TooLarge)?;
276    let off_edge_types = u32::try_from(off_edge_types).map_err(|_| EncodeError::TooLarge)?;
277    let off_strings = u32::try_from(off_strings).map_err(|_| EncodeError::TooLarge)?;
278
279    let mut out: Vec<u8> = Vec::with_capacity(off_strings as usize + 8 + node_count * 8);
280    out.extend_from_slice(MAGIC);
281    out.extend_from_slice(&VERSION.to_le_bytes());
282    out.extend_from_slice(&0u16.to_le_bytes()); // pad
283    for v in [
284        to_u32(node_count)?,
285        to_u32(edge_count)?,
286        off_nodes,
287        off_adjacency,
288        off_edge_types,
289        off_strings,
290    ] {
291        out.extend_from_slice(&v.to_le_bytes());
292    }
293
294    for node in nodes {
295        out.extend_from_slice(&node.id.to_le_bytes());
296        out.extend_from_slice(&node.x.to_le_bytes());
297        out.extend_from_slice(&node.y.to_le_bytes());
298        out.extend_from_slice(&node.domain.to_le_bytes());
299        out.extend_from_slice(&node.category.to_le_bytes());
300        out.push(node.flags);
301        out.extend_from_slice(&[0u8; 3]); // pad
302        out.extend_from_slice(&node.degree.to_le_bytes());
303    }
304
305    for v in &csr.row_ptr {
306        out.extend_from_slice(&v.to_le_bytes());
307    }
308    for v in &csr.col_idx {
309        out.extend_from_slice(&v.to_le_bytes());
310    }
311
312    out.extend_from_slice(&csr.edge_type);
313    out.extend(std::iter::repeat_n(0u8, pad4(edge_count)));
314
315    let mut blob: Vec<u8> = Vec::new();
316    let mut offsets: Vec<u32> = Vec::with_capacity(node_count * 2);
317    for node in nodes {
318        offsets.push(to_u32(blob.len())?);
319        blob.extend_from_slice(node.label.as_bytes());
320        offsets.push(to_u32(blob.len())?);
321        blob.extend_from_slice(node.iri.as_bytes());
322    }
323    out.extend_from_slice(&to_u32(offsets.len())?.to_le_bytes());
324    out.extend_from_slice(&to_u32(blob.len())?.to_le_bytes());
325    for v in &offsets {
326        out.extend_from_slice(&v.to_le_bytes());
327    }
328    out.extend_from_slice(&blob);
329
330    debug_assert_eq!(
331        out.len(),
332        off_strings as usize + 8 + offsets.len() * 4 + blob.len()
333    );
334    Ok(out)
335}
ontomark_ngg1/encode.rs

ontomark_ngg1/
encode.rs
