concept_graph/
relations.rs

1// SPDX-FileCopyrightText: Cadasto B.V.
2// SPDX-License-Identifier: BUSL-1.1
3
4//! Typed adjacency: every edge carries a relationship type, and both
5//! directions are materialized.
6//!
7//! The is-a hierarchy is [`crate::persist::Hierarchy`]; this is for the other
8//! relationships a code system states between its concepts (`RxNorm`'s `REL`
9//! and `RELA`, SNOMED CT's attributes when they are served as a graph). No
10//! spec governs the layout: our own design. Little-endian, a magic and
11//! version prefix, the type names, then the outgoing and the incoming
12//! adjacency as offsets with parallel type and node arrays, each node's edges
13//! sorted by type then node.
14
15use std::io::{self, Read, Write};
16
17use crate::ordinal::{Ordinal, to_usize};
18
19const MAGIC: &[u8; 8] = b"FTRELS\0\0";
20const VERSION: u32 = 1;
21
22/// A failure while building, reading, or writing the relations.
23#[derive(Debug, thiserror::Error)]
24pub enum RelationsError {
25    /// An edge names a node or a type beyond the declared counts.
26    #[error("edge ({from}, {kind}, {target}) is out of range for {nodes} nodes and {types} types")]
27    OutOfRange {
28        /// The source node.
29        from: u32,
30        /// The type index.
31        kind: u32,
32        /// The target node.
33        target: u32,
34        /// The node count.
35        nodes: u32,
36        /// The type count.
37        types: u32,
38    },
39    /// An I/O failure.
40    #[error("relations I/O failed")]
41    Io(#[from] io::Error),
42    /// The bytes do not start with the relations magic.
43    #[error("not a relations artifact")]
44    Magic,
45    /// The layout version is not the one this build reads.
46    #[error("relations layout version {found}, expected {expected}")]
47    Version {
48        /// The version found.
49        found: u32,
50        /// The version this build reads.
51        expected: u32,
52    },
53    /// The arrays are inconsistent.
54    #[error("the relations arrays are inconsistent")]
55    Inconsistent,
56    /// A type name is not UTF-8.
57    #[error("a relationship type name is not UTF-8")]
58    Name(#[from] std::string::FromUtf8Error),
59}
60
61/// One direction of the adjacency.
62#[derive(Debug, Clone, PartialEq, Eq, Default)]
63struct Adjacency {
64    /// `nodes + 1` offsets into `kinds` and `ends`.
65    offsets: Vec<u32>,
66    kinds: Vec<u32>,
67    ends: Vec<u32>,
68}
69
70impl Adjacency {
71    fn build(nodes: u32, mut edges: Vec<(u32, u32, u32)>) -> Self {
72        edges.sort_unstable();
73        edges.dedup();
74        let mut offsets = Vec::with_capacity(to_usize(nodes).saturating_add(1));
75        let mut kinds = Vec::with_capacity(edges.len());
76        let mut ends = Vec::with_capacity(edges.len());
77        let mut cursor = 0usize;
78        for node in 0..nodes {
79            offsets.push(u32::try_from(kinds.len()).unwrap_or(u32::MAX));
80            while let Some(&(from, kind, to)) = edges.get(cursor) {
81                if from != node {
82                    break;
83                }
84                kinds.push(kind);
85                ends.push(to);
86                cursor = cursor.saturating_add(1);
87            }
88        }
89        offsets.push(u32::try_from(kinds.len()).unwrap_or(u32::MAX));
90        Self {
91            offsets,
92            kinds,
93            ends,
94        }
95    }
96
97    fn edges(&self, node: Ordinal) -> impl Iterator<Item = (u32, u32)> + '_ {
98        let index = to_usize(node.index());
99        let (start, end) = match (
100            self.offsets.get(index),
101            self.offsets.get(index.saturating_add(1)),
102        ) {
103            (Some(&s), Some(&e)) => (to_usize(s), to_usize(e)),
104            _ => (0, 0),
105        };
106        let kinds = self.kinds.get(start..end).unwrap_or_default();
107        let ends = self.ends.get(start..end).unwrap_or_default();
108        kinds.iter().copied().zip(ends.iter().copied())
109    }
110
111    fn check(&self, nodes: u32) -> Result<(), RelationsError> {
112        let consistent = self.offsets.len() == to_usize(nodes).saturating_add(1)
113            && self.kinds.len() == self.ends.len()
114            && self
115                .offsets
116                .last()
117                .is_some_and(|&l| to_usize(l) == self.kinds.len())
118            && self.offsets.windows(2).all(|w| w.first() <= w.get(1));
119        consistent.then_some(()).ok_or(RelationsError::Inconsistent)
120    }
121}
122
123/// The typed edges of a code system, both ways.
124#[derive(Debug, Clone, PartialEq, Eq, Default)]
125pub struct Relations {
126    /// The relationship type names; an edge's type is an index into this list.
127    types: Vec<String>,
128    outgoing: Adjacency,
129    incoming: Adjacency,
130}
131
132impl Relations {
133    /// Builds the relations of `nodes` nodes from `(source, type, target)` edges.
134    ///
135    /// # Errors
136    ///
137    /// Returns [`RelationsError::OutOfRange`] for an edge beyond `nodes` or
138    /// beyond the type list.
139    pub fn build(
140        nodes: u32,
141        types: Vec<String>,
142        edges: Vec<(Ordinal, u32, Ordinal)>,
143    ) -> Result<Self, RelationsError> {
144        let type_count = u32::try_from(types.len()).unwrap_or(u32::MAX);
145        let mut forward = Vec::with_capacity(edges.len());
146        let mut backward = Vec::with_capacity(edges.len());
147        for (source, kind, target) in edges {
148            let (s, t) = (source.index(), target.index());
149            if s >= nodes || t >= nodes || kind >= type_count {
150                return Err(RelationsError::OutOfRange {
151                    from: s,
152                    kind,
153                    target: t,
154                    nodes,
155                    types: type_count,
156                });
157            }
158            forward.push((s, kind, t));
159            backward.push((t, kind, s));
160        }
161        Ok(Self {
162            types,
163            outgoing: Adjacency::build(nodes, forward),
164            incoming: Adjacency::build(nodes, backward),
165        })
166    }
167
168    /// The relationship type names.
169    #[must_use]
170    pub fn types(&self) -> &[String] {
171        &self.types
172    }
173
174    /// The index of the type `name`.
175    #[must_use]
176    pub fn kind(&self, name: &str) -> Option<u32> {
177        self.types
178            .iter()
179            .position(|t| t == name)
180            .and_then(|i| u32::try_from(i).ok())
181    }
182
183    /// The node count.
184    #[must_use]
185    pub fn nodes(&self) -> u32 {
186        u32::try_from(self.outgoing.offsets.len().saturating_sub(1)).unwrap_or(u32::MAX)
187    }
188
189    /// The edge count.
190    #[must_use]
191    pub fn edges(&self) -> usize {
192        self.outgoing.ends.len()
193    }
194
195    /// The `(type, target)` pairs leaving `node`, by type then target.
196    pub fn outgoing(&self, node: Ordinal) -> impl Iterator<Item = (u32, Ordinal)> + '_ {
197        self.outgoing.edges(node).map(|(k, n)| (k, Ordinal::new(n)))
198    }
199
200    /// The `(type, source)` pairs arriving at `node`, by type then source.
201    pub fn incoming(&self, node: Ordinal) -> impl Iterator<Item = (u32, Ordinal)> + '_ {
202        self.incoming.edges(node).map(|(k, n)| (k, Ordinal::new(n)))
203    }
204
205    /// The sources of edges of type `kind` arriving at `node`.
206    pub fn sources(&self, node: Ordinal, kind: u32) -> impl Iterator<Item = Ordinal> + '_ {
207        self.incoming(node)
208            .filter(move |(k, _)| *k == kind)
209            .map(|(_, n)| n)
210    }
211
212    /// The targets of edges of type `kind` leaving `node`.
213    pub fn targets(&self, node: Ordinal, kind: u32) -> impl Iterator<Item = Ordinal> + '_ {
214        self.outgoing(node)
215            .filter(move |(k, _)| *k == kind)
216            .map(|(_, n)| n)
217    }
218
219    /// Writes the layout.
220    ///
221    /// # Errors
222    ///
223    /// Returns [`RelationsError::Io`] when writing fails.
224    pub fn write_to(&self, out: &mut impl Write) -> Result<(), RelationsError> {
225        out.write_all(MAGIC)?;
226        out.write_all(&VERSION.to_le_bytes())?;
227        let count = crate::persist::u32_len(self.types.len(), "the type count")?;
228        out.write_all(&count.to_le_bytes())?;
229        for name in &self.types {
230            let len = crate::persist::u32_len(name.len(), "a type name length")?;
231            out.write_all(&len.to_le_bytes())?;
232            out.write_all(name.as_bytes())?;
233        }
234        for side in [&self.outgoing, &self.incoming] {
235            write_u32s(out, &side.offsets)?;
236            write_u32s(out, &side.kinds)?;
237            write_u32s(out, &side.ends)?;
238        }
239        Ok(())
240    }
241
242    /// Reads the layout.
243    ///
244    /// # Errors
245    ///
246    /// Returns [`RelationsError`] for a truncated, foreign, or inconsistent artifact.
247    pub fn read_from(input: &mut impl Read) -> Result<Self, RelationsError> {
248        let mut magic = [0_u8; 8];
249        input.read_exact(&mut magic)?;
250        if &magic != MAGIC {
251            return Err(RelationsError::Magic);
252        }
253        let version = read_u32(input)?;
254        if version != VERSION {
255            return Err(RelationsError::Version {
256                found: version,
257                expected: VERSION,
258            });
259        }
260        let count = read_u32(input)?;
261        let mut types = Vec::with_capacity(to_usize(count));
262        for _ in 0..count {
263            let len = read_u32(input)?;
264            let mut bytes = vec![0_u8; to_usize(len)];
265            input.read_exact(&mut bytes)?;
266            types.push(String::from_utf8(bytes)?);
267        }
268        let mut sides = Vec::with_capacity(2);
269        for _ in 0..2 {
270            sides.push(Adjacency {
271                offsets: read_u32s(input)?,
272                kinds: read_u32s(input)?,
273                ends: read_u32s(input)?,
274            });
275        }
276        let incoming = sides.pop().ok_or(RelationsError::Inconsistent)?;
277        let outgoing = sides.pop().ok_or(RelationsError::Inconsistent)?;
278        // A node count past u32::MAX is an inconsistent artifact; the conversion
279        // error adds nothing to that.
280        let Ok(nodes) = u32::try_from(outgoing.offsets.len().saturating_sub(1)) else {
281            return Err(RelationsError::Inconsistent);
282        };
283        outgoing.check(nodes)?;
284        incoming.check(nodes)?;
285        Ok(Self {
286            types,
287            outgoing,
288            incoming,
289        })
290    }
291}
292
293fn write_u32s(out: &mut impl Write, values: &[u32]) -> io::Result<()> {
294    let len = crate::persist::u32_len(values.len(), "an array length")?;
295    out.write_all(&len.to_le_bytes())?;
296    for value in values {
297        out.write_all(&value.to_le_bytes())?;
298    }
299    Ok(())
300}
301
302fn read_u32(input: &mut impl Read) -> io::Result<u32> {
303    let mut buffer = [0_u8; 4];
304    input.read_exact(&mut buffer)?;
305    Ok(u32::from_le_bytes(buffer))
306}
307
308fn read_u32s(input: &mut impl Read) -> io::Result<Vec<u32>> {
309    let len = read_u32(input)?;
310    let mut values = Vec::with_capacity(to_usize(len));
311    for _ in 0..len {
312        values.push(read_u32(input)?);
313    }
314    Ok(values)
315}
316
317#[cfg(test)]
318mod tests {
319    use super::{Relations, RelationsError};
320    use crate::ordinal::Ordinal;
321
322    #[test]
323    fn edges_are_answered_both_ways_and_round_trip() {
324        let o = Ordinal::new;
325        let types = vec![String::from("has_ingredient"), String::from("isa")];
326        let relations = Relations::build(
327            4,
328            types,
329            vec![
330                (o(2), 0, o(0)),
331                (o(3), 0, o(0)),
332                (o(3), 1, o(2)),
333                (o(2), 0, o(0)),
334            ],
335        )
336        .expect("builds");
337        assert_eq!(relations.edges(), 3, "duplicates collapse");
338        assert_eq!(relations.kind("isa"), Some(1));
339        assert_eq!(relations.kind("part_of"), None);
340        let sources: Vec<u32> = relations.sources(o(0), 0).map(Ordinal::index).collect();
341        assert_eq!(sources, [2, 3]);
342        let targets: Vec<u32> = relations.targets(o(3), 1).map(Ordinal::index).collect();
343        assert_eq!(targets, [2]);
344        assert_eq!(relations.outgoing(o(1)).count(), 0);
345        let mut bytes = Vec::new();
346        relations.write_to(&mut bytes).expect("writes");
347        let back = Relations::read_from(&mut bytes.as_slice()).expect("reads");
348        assert_eq!(back, relations);
349        assert!(matches!(
350            Relations::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
351            Err(RelationsError::Magic)
352        ));
353        assert!(matches!(
354            Relations::build(2, Vec::new(), vec![(o(0), 0, o(1))]),
355            Err(RelationsError::OutOfRange { .. })
356        ));
357    }
358}
concept_graph/relations.rs

concept_graph/
relations.rs
