Skip to main content

qualia_core_db/topology/
csr_view.rs

1//! Zero-copy CSR/CSC and `CellAnchor` view for a `HarbouredGraphHeader`.
2//!
3//! Tier-1 Zero-Heap (`AGENTS.md` §0 & §0-A): all operations borrow directly from
4//! the caller's byte segment or slice arrays and write into caller-supplied `&mut [u32]` buffers.
5
6use bytemuck::Pod;
7
8use crate::topology::header::{
9    AnchorDomain, CellAnchor, HarbouredGraphHeader, TopologyError, TopologyInvariants,
10};
11
12/// Zero-copy view over a single harboured graph's `CellAnchor`, forward CSR,
13/// backward CSC, and optional `f32` edge weight tables.
14#[derive(Copy, Clone, Debug, PartialEq)]
15pub struct HarbouredCsrView<'a> {
16    header: &'a HarbouredGraphHeader,
17    anchors: &'a [CellAnchor],
18    csr_row_ptr: &'a [u32],
19    csr_col_idx: &'a [u32],
20    edge_anchor: &'a [u32],
21    csc_col_ptr: &'a [u32],
22    csc_row_idx: &'a [u32],
23    edge_weights: Option<&'a [f32]>,
24}
25
26impl<'a> HarbouredCsrView<'a> {
27    /// Construct and validate a `HarbouredCsrView` from pre-sliced tables.
28    #[allow(clippy::too_many_arguments)]
29    pub fn from_slices(
30        header: &'a HarbouredGraphHeader,
31        anchors: &'a [CellAnchor],
32        csr_row_ptr: &'a [u32],
33        csr_col_idx: &'a [u32],
34        edge_anchor: &'a [u32],
35        csc_col_ptr: &'a [u32],
36        csc_row_idx: &'a [u32],
37        edge_weights: Option<&'a [f32]>,
38    ) -> Result<Self, TopologyError> {
39        if header.embed_role != 0 && header.embed_role_enum().is_none() {
40            return Err(TopologyError::InvalidEmbedRole(header.embed_role));
41        }
42        if header.morphology != 0 && header.morphology_enum().is_none() {
43            return Err(TopologyError::InvalidMorphology(header.morphology));
44        }
45
46        let v_count = header.vertex_count as usize;
47        let e_count = header.edge_count as usize;
48
49        if anchors.len() != v_count
50            || csr_row_ptr.len() != v_count + 1
51            || csr_col_idx.len() != e_count
52            || edge_anchor.len() != e_count
53            || csc_col_ptr.len() != v_count + 1
54            || csc_row_idx.len() != e_count
55        {
56            return Err(TopologyError::BufferTooSmall);
57        }
58
59        if let Some(weights) = edge_weights {
60            if weights.len() != e_count {
61                return Err(TopologyError::BufferTooSmall);
62            }
63        }
64
65        if csr_row_ptr[0] != 0 {
66            return Err(TopologyError::NonMonotonicRowPtr { vertex: 0 });
67        }
68        for u in 0..v_count {
69            if csr_row_ptr[u] > csr_row_ptr[u + 1] {
70                return Err(TopologyError::NonMonotonicRowPtr { vertex: u as u32 });
71            }
72        }
73        if csr_row_ptr[v_count] != header.edge_count {
74            return Err(TopologyError::NonMonotonicRowPtr {
75                vertex: header.vertex_count,
76            });
77        }
78
79        if csc_col_ptr[0] != 0 {
80            return Err(TopologyError::NonMonotonicRowPtr { vertex: 0 });
81        }
82        for v in 0..v_count {
83            if csc_col_ptr[v] > csc_col_ptr[v + 1] {
84                return Err(TopologyError::NonMonotonicRowPtr { vertex: v as u32 });
85            }
86        }
87        if csc_col_ptr[v_count] != header.edge_count {
88            return Err(TopologyError::NonMonotonicRowPtr {
89                vertex: header.vertex_count,
90            });
91        }
92
93        for &col in csr_col_idx {
94            if col >= header.vertex_count {
95                return Err(TopologyError::VertexOutOfRange {
96                    vertex: col,
97                    count: header.vertex_count,
98                });
99            }
100        }
101
102        for &row in csc_row_idx {
103            if row >= header.vertex_count {
104                return Err(TopologyError::VertexOutOfRange {
105                    vertex: row,
106                    count: header.vertex_count,
107                });
108            }
109        }
110
111        Ok(Self {
112            header,
113            anchors,
114            csr_row_ptr,
115            csr_col_idx,
116            edge_anchor,
117            csc_col_ptr,
118            csc_row_idx,
119            edge_weights,
120        })
121    }
122
123    /// Construct a `HarbouredCsrView` by slicing a `GTOP` segment at the offsets in `header`.
124    pub fn from_segment_bytes(
125        segment: &'a [u8],
126        header: &'a HarbouredGraphHeader,
127    ) -> Result<Self, TopologyError> {
128        let v_count = header.vertex_count as usize;
129        let e_count = header.edge_count as usize;
130
131        let anchors = slice_pod::<CellAnchor>(segment, header.anchor_table_offset, v_count)?;
132        let csr_row_ptr = slice_pod::<u32>(segment, header.csr_row_ptr_offset, v_count + 1)?;
133        let csr_col_idx = slice_pod::<u32>(segment, header.csr_col_idx_offset, e_count)?;
134        let edge_anchor = slice_pod::<u32>(segment, header.edge_anchor_offset, e_count)?;
135        let csc_col_ptr = slice_pod::<u32>(segment, header.csc_col_ptr_offset, v_count + 1)?;
136        let csc_row_idx = slice_pod::<u32>(segment, header.csc_row_idx_offset, e_count)?;
137        let edge_weights = if header.edge_weight_offset != 0 {
138            Some(slice_pod::<f32>(
139                segment,
140                header.edge_weight_offset,
141                e_count,
142            )?)
143        } else {
144            None
145        };
146
147        Self::from_slices(
148            header,
149            anchors,
150            csr_row_ptr,
151            csr_col_idx,
152            edge_anchor,
153            csc_col_ptr,
154            csc_row_idx,
155            edge_weights,
156        )
157    }
158
159    #[inline]
160    pub const fn header(&self) -> &'a HarbouredGraphHeader {
161        self.header
162    }
163
164    #[inline]
165    pub const fn vertex_count(&self) -> u32 {
166        self.header.vertex_count
167    }
168
169    #[inline]
170    pub const fn edge_count(&self) -> u32 {
171        self.header.edge_count
172    }
173
174    #[inline]
175    pub const fn anchors(&self) -> &'a [CellAnchor] {
176        self.anchors
177    }
178
179    #[inline]
180    pub const fn csr_row_ptr(&self) -> &'a [u32] {
181        self.csr_row_ptr
182    }
183
184    #[inline]
185    pub const fn csr_col_idx(&self) -> &'a [u32] {
186        self.csr_col_idx
187    }
188
189    #[inline]
190    pub const fn edge_anchor(&self) -> &'a [u32] {
191        self.edge_anchor
192    }
193
194    #[inline]
195    pub const fn edge_anchors(&self) -> &'a [u32] {
196        self.edge_anchor
197    }
198
199    #[inline]
200    pub const fn csc_col_ptr(&self) -> &'a [u32] {
201        self.csc_col_ptr
202    }
203
204    #[inline]
205    pub const fn csc_row_idx(&self) -> &'a [u32] {
206        self.csc_row_idx
207    }
208
209    #[inline]
210    pub const fn edge_weights(&self) -> Option<&'a [f32]> {
211        self.edge_weights
212    }
213
214    /// Look up the 16-byte `CellAnchor` for vertex `v`.
215    #[inline]
216    pub fn cell_anchor(&self, v: u32) -> Result<&'a CellAnchor, TopologyError> {
217        self.anchors
218            .get(v as usize)
219            .ok_or(TopologyError::VertexOutOfRange {
220                vertex: v,
221                count: self.header.vertex_count,
222            })
223    }
224
225    /// Outgoing neighbour slice for vertex `u` in $O(1)$.
226    #[inline]
227    pub fn out_neighbors(&self, u: u32) -> Result<&'a [u32], TopologyError> {
228        if u >= self.header.vertex_count {
229            return Err(TopologyError::VertexOutOfRange {
230                vertex: u,
231                count: self.header.vertex_count,
232            });
233        }
234        let idx = u as usize;
235        let start = self.csr_row_ptr[idx] as usize;
236        let end = self.csr_row_ptr[idx + 1] as usize;
237        Ok(&self.csr_col_idx[start..end])
238    }
239
240    /// Outgoing edge anchor indices (1-cell ID or `NQuin` slot) for vertex `u` in $O(1)$.
241    #[inline]
242    pub fn out_edge_anchors(&self, u: u32) -> Result<&'a [u32], TopologyError> {
243        if u >= self.header.vertex_count {
244            return Err(TopologyError::VertexOutOfRange {
245                vertex: u,
246                count: self.header.vertex_count,
247            });
248        }
249        let idx = u as usize;
250        let start = self.csr_row_ptr[idx] as usize;
251        let end = self.csr_row_ptr[idx + 1] as usize;
252        Ok(&self.edge_anchor[start..end])
253    }
254
255    /// Optional outgoing edge weights for vertex `u` in $O(1)$.
256    #[inline]
257    pub fn out_edge_weights(&self, u: u32) -> Result<Option<&'a [f32]>, TopologyError> {
258        if u >= self.header.vertex_count {
259            return Err(TopologyError::VertexOutOfRange {
260                vertex: u,
261                count: self.header.vertex_count,
262            });
263        }
264        let idx = u as usize;
265        let start = self.csr_row_ptr[idx] as usize;
266        let end = self.csr_row_ptr[idx + 1] as usize;
267        Ok(self.edge_weights.map(|w| &w[start..end]))
268    }
269
270    /// Incoming neighbour slice for vertex `v` in $O(1)$ via backward CSC.
271    #[inline]
272    pub fn in_neighbors(&self, v: u32) -> Result<&'a [u32], TopologyError> {
273        if v >= self.header.vertex_count {
274            return Err(TopologyError::VertexOutOfRange {
275                vertex: v,
276                count: self.header.vertex_count,
277            });
278        }
279        let idx = v as usize;
280        let start = self.csc_col_ptr[idx] as usize;
281        let end = self.csc_col_ptr[idx + 1] as usize;
282        Ok(&self.csc_row_idx[start..end])
283    }
284
285    /// Out-degree of vertex `u` in $O(1)$.
286    #[inline]
287    pub fn out_degree(&self, u: u32) -> Result<u32, TopologyError> {
288        if u >= self.header.vertex_count {
289            return Err(TopologyError::VertexOutOfRange {
290                vertex: u,
291                count: self.header.vertex_count,
292            });
293        }
294        let idx = u as usize;
295        Ok(self.csr_row_ptr[idx + 1] - self.csr_row_ptr[idx])
296    }
297
298    /// In-degree of vertex `v` in $O(1)$ via backward CSC.
299    #[inline]
300    pub fn in_degree(&self, v: u32) -> Result<u32, TopologyError> {
301        if v >= self.header.vertex_count {
302            return Err(TopologyError::VertexOutOfRange {
303                vertex: v,
304                count: self.header.vertex_count,
305            });
306        }
307        let idx = v as usize;
308        Ok(self.csc_col_ptr[idx + 1] - self.csc_col_ptr[idx])
309    }
310
311    /// Find vertex index by 64-bit `entity_hash`.
312    /// Uses binary search when sorted by `entity_hash` and falls back to a deterministic linear scan.
313    pub fn find_vertex_by_entity_hash(&self, entity_hash: u64) -> Option<u32> {
314        if let Ok(idx) = self
315            .anchors
316            .binary_search_by_key(&entity_hash, |a| a.entity_hash)
317        {
318            return Some(idx as u32);
319        }
320        let mut i = 0usize;
321        while i < self.anchors.len() {
322            if self.anchors[i].entity_hash == entity_hash {
323                return Some(i as u32);
324            }
325            i += 1;
326        }
327        None
328    }
329
330    /// Collect all vertices anchored to `(domain, cell_index)` into caller buffer `out`.
331    pub fn find_vertices_by_cell(
332        &self,
333        domain: AnchorDomain,
334        cell_index: u32,
335        out: &mut [u32],
336    ) -> usize {
337        let domain_u8 = domain as u8;
338        let mut written = 0usize;
339        let mut v = 0usize;
340        while v < self.anchors.len() {
341            let a = &self.anchors[v];
342            if a.anchor_domain == domain_u8 && a.cell_index == cell_index {
343                if written >= out.len() {
344                    break;
345                }
346                out[written] = v as u32;
347                written += 1;
348            }
349            v += 1;
350        }
351        written
352    }
353
354    /// Collect all source/root vertices (`in_degree(v) == 0`) into `out`.
355    pub fn collect_roots(&self, out: &mut [u32]) -> usize {
356        let mut written = 0usize;
357        let v_count = self.header.vertex_count as usize;
358        let mut v = 0usize;
359        while v < v_count {
360            if self.csc_col_ptr[v + 1] == self.csc_col_ptr[v] {
361                if written >= out.len() {
362                    break;
363                }
364                out[written] = v as u32;
365                written += 1;
366            }
367            v += 1;
368        }
369        written
370    }
371
372    /// Collect all sink/leaf vertices (`out_degree(u) == 0`) into `out`.
373    pub fn collect_sinks(&self, out: &mut [u32]) -> usize {
374        let mut written = 0usize;
375        let v_count = self.header.vertex_count as usize;
376        let mut u = 0usize;
377        while u < v_count {
378            if self.csr_row_ptr[u + 1] == self.csr_row_ptr[u] {
379                if written >= out.len() {
380                    break;
381                }
382                out[written] = u as u32;
383                written += 1;
384            }
385            u += 1;
386        }
387        written
388    }
389
390    /// When `TopologyInvariants::REIFIED_EDGES` is active, resolves the edge at `edge_pos`
391    /// to its RDF-Star `TAG_EMBEDDED` virtual vertex in the graph.
392    pub fn resolve_reified_edge_vertex(
393        &self,
394        quins: &[crate::NQuin],
395        edge_pos: usize,
396    ) -> Option<u32> {
397        if !self
398            .header
399            .invariants
400            .contains(TopologyInvariants::REIFIED_EDGES)
401        {
402            return None;
403        }
404        let quin_idx = *self.edge_anchor.get(edge_pos)? as usize;
405        let q = quins.get(quin_idx)?;
406        let virtual_id = crate::query::rdf_star::create_virtual_id(q.subject, q.predicate, q.object);
407        self.find_vertex_by_entity_hash(virtual_id)
408    }
409}
410
411#[inline]
412pub(crate) fn slice_pod<'a, T: Pod>(
413    segment: &'a [u8],
414    offset: u32,
415    count: usize,
416) -> Result<&'a [T], TopologyError> {
417    let start = offset as usize;
418    if count == 0 {
419        if start > segment.len() {
420            return Err(TopologyError::BufferTooSmall);
421        }
422        return Ok(&[]);
423    }
424    let byte_len = count
425        .checked_mul(core::mem::size_of::<T>())
426        .ok_or(TopologyError::BufferTooSmall)?;
427    let end = start
428        .checked_add(byte_len)
429        .ok_or(TopologyError::BufferTooSmall)?;
430    let bytes = segment
431        .get(start..end)
432        .ok_or(TopologyError::BufferTooSmall)?;
433    bytemuck::try_cast_slice(bytes).map_err(|_| TopologyError::UnalignedBuffer)
434}
435