concept_graph/
attributes.rs

1//! The attribute relationships of an edition.
2//!
3//! Per source concept, every active relationship that is not is-a, with its
4//! role group, its type, and its value (a concept, a number, or a string),
5//! plus the inverted index the ECL evaluator reads (`type = value` as the
6//! sources of a type with a value in a set).
7//!
8//! No spec governs the layout: our own design. Little-endian, a magic and
9//! version prefix, the type SCTIDs, the node count, `nodes + 1` row offsets,
10//! then the rows as parallel arrays (group, type index, value tag, payload)
11//! and the interned strings. The inverted index is derived on read.
12
13use std::collections::BTreeMap;
14use std::io::{self, Read, Write};
15
16use roaring::RoaringBitmap;
17
18use crate::ordinal::{Ordinal, to_usize};
19
20const MAGIC: &[u8; 8] = b"FTATTR\0\0";
21const VERSION: u32 = 1;
22const TAG_CONCEPT: u8 = 0;
23const TAG_NUMBER: u8 = 1;
24const TAG_STRING: u8 = 2;
25
26/// A failure while building, reading, or writing the attributes.
27#[derive(Debug, thiserror::Error)]
28pub enum AttributesError {
29    /// A row names a node or a type beyond the declared counts.
30    #[error("attribute row ({from}, {kind}) is out of range for {nodes} nodes and {types} types")]
31    OutOfRange {
32        /// The source node.
33        from: u32,
34        /// The type index.
35        kind: u32,
36        /// The node count.
37        nodes: u32,
38        /// The type count.
39        types: u32,
40    },
41    /// More rows or strings than the `u32` offsets address.
42    #[error("too many attribute rows")]
43    TooMany(#[source] std::num::TryFromIntError),
44    /// An I/O failure.
45    #[error("attributes I/O failed")]
46    Io(#[from] io::Error),
47    /// The bytes do not start with the attributes magic.
48    #[error("not an attributes artifact")]
49    Magic,
50    /// The layout version is not the one this build reads.
51    #[error("attributes layout version {found}, expected {expected}")]
52    Version {
53        /// The version found.
54        found: u32,
55        /// The version this build reads.
56        expected: u32,
57    },
58    /// The arrays are inconsistent.
59    #[error("the attribute arrays are inconsistent")]
60    Inconsistent,
61    /// An interned string is not UTF-8.
62    #[error("an attribute value is not UTF-8")]
63    Text(#[from] std::string::FromUtf8Error),
64}
65
66/// An attribute value as built.
67#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
68pub enum Value {
69    /// The destination concept.
70    Concept(Ordinal),
71    /// A concrete number, as the release spells it (`500`, `0.25`, `-1`).
72    Number(String),
73    /// A concrete string.
74    String(String),
75}
76
77/// One attribute relationship as built.
78#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
79pub struct Edge {
80    /// The source concept.
81    pub source: Ordinal,
82    /// The role group; `0` is ungrouped.
83    pub group: u32,
84    /// The attribute type, an index into the type list.
85    pub kind: u32,
86    /// The value.
87    pub value: Value,
88}
89
90/// An attribute value as read.
91#[derive(Debug, Clone, Copy, PartialEq, Eq)]
92pub enum ValueRef<'a> {
93    /// The destination concept.
94    Concept(Ordinal),
95    /// A concrete number, as the release spells it.
96    Number(&'a str),
97    /// A concrete string.
98    String(&'a str),
99}
100
101/// One attribute relationship as read.
102#[derive(Debug, Clone, Copy, PartialEq, Eq)]
103pub struct Row<'a> {
104    /// The role group; `0` is ungrouped.
105    pub group: u32,
106    /// The attribute type, an index into the type list.
107    pub kind: u32,
108    /// The value.
109    pub value: ValueRef<'a>,
110}
111
112/// The sources of one type by destination concept, and all of them.
113#[derive(Debug, Clone, PartialEq, Eq, Default)]
114struct Inverted {
115    /// The destination concepts, sorted.
116    targets: Vec<u32>,
117    /// `targets.len() + 1` offsets into `sources`.
118    offsets: Vec<u32>,
119    /// The sources per destination, each run sorted.
120    sources: Vec<u32>,
121    /// Every source with a relationship of the type, whatever its value.
122    all_sources: RoaringBitmap,
123}
124
125impl Inverted {
126    fn build(mut pairs: Vec<(u32, u32)>, all_sources: RoaringBitmap) -> Self {
127        pairs.sort_unstable();
128        pairs.dedup();
129        let mut targets = Vec::new();
130        let mut offsets = Vec::new();
131        let mut sources = Vec::with_capacity(pairs.len());
132        for (target, source) in pairs {
133            if targets.last() != Some(&target) {
134                targets.push(target);
135                offsets.push(u32::try_from(sources.len()).unwrap_or(u32::MAX));
136            }
137            sources.push(source);
138        }
139        offsets.push(u32::try_from(sources.len()).unwrap_or(u32::MAX));
140        Self {
141            targets,
142            offsets,
143            sources,
144            all_sources,
145        }
146    }
147
148    fn size_in_bytes(&self) -> usize {
149        crate::footprint::vector(&self.targets)
150            .saturating_add(crate::footprint::vector(&self.offsets))
151            .saturating_add(crate::footprint::vector(&self.sources))
152            .saturating_add(crate::footprint::bitmap(&self.all_sources))
153    }
154
155    fn sources(&self, target: u32) -> &[u32] {
156        let Ok(index) = self.targets.binary_search(&target) else {
157            return &[];
158        };
159        match (
160            self.offsets.get(index),
161            self.offsets.get(index.saturating_add(1)),
162        ) {
163            (Some(&start), Some(&end)) => self
164                .sources
165                .get(to_usize(start)..to_usize(end))
166                .unwrap_or_default(),
167            _ => &[],
168        }
169    }
170}
171
172/// The attribute relationships of every concept.
173#[derive(Debug, Clone, PartialEq, Eq, Default)]
174pub struct Attributes {
175    /// The attribute type SCTIDs; a row's type is an index into this list.
176    types: Vec<u64>,
177    /// `nodes + 1` offsets into the row arrays.
178    offsets: Vec<u32>,
179    groups: Vec<u32>,
180    kinds: Vec<u32>,
181    tags: Vec<u8>,
182    payloads: Vec<u32>,
183    strings: Vec<String>,
184    /// Per type, the inverted index; derived, not persisted.
185    inverted: Vec<Inverted>,
186}
187
188impl Attributes {
189    /// The heap bytes the rows hold ([`crate::footprint`]).
190    #[must_use]
191    pub fn rows_size_in_bytes(&self) -> usize {
192        crate::footprint::vector(&self.types)
193            .saturating_add(crate::footprint::vector(&self.offsets))
194            .saturating_add(crate::footprint::vector(&self.groups))
195            .saturating_add(crate::footprint::vector(&self.kinds))
196            .saturating_add(crate::footprint::vector(&self.tags))
197            .saturating_add(crate::footprint::vector(&self.payloads))
198            .saturating_add(crate::footprint::strings(&self.strings))
199    }
200
201    /// The heap bytes the inverted index holds.
202    ///
203    /// It is derived when the artifact opens rather than read from it, so it
204    /// is reported apart from the rows it was derived from.
205    #[must_use]
206    pub fn inverted_size_in_bytes(&self) -> usize {
207        self.inverted.iter().fold(
208            crate::footprint::vector(&self.inverted),
209            |total, inverted| total.saturating_add(inverted.size_in_bytes()),
210        )
211    }
212
213    /// The heap bytes the rows and the inverted index hold together.
214    #[must_use]
215    pub fn size_in_bytes(&self) -> usize {
216        self.rows_size_in_bytes()
217            .saturating_add(self.inverted_size_in_bytes())
218    }
219
220    /// Builds the attributes of `nodes` concepts from `edges`, whose types
221    /// index `types`.
222    ///
223    /// # Errors
224    ///
225    /// Returns [`AttributesError::OutOfRange`] for a row beyond `nodes` or
226    /// beyond the type list, and [`AttributesError::TooMany`] past `u32`.
227    pub fn build(
228        nodes: u32,
229        types: Vec<u64>,
230        mut edges: Vec<Edge>,
231    ) -> Result<Self, AttributesError> {
232        let type_count = u32::try_from(types.len()).map_err(AttributesError::TooMany)?;
233        Self::check_range(nodes, type_count, &edges)?;
234        edges.sort_unstable();
235        edges.dedup();
236        u32::try_from(edges.len()).map_err(AttributesError::TooMany)?;
237        let mut attributes = Self::pack(nodes, types, &edges)?;
238        attributes.derive();
239        Ok(attributes)
240    }
241
242    /// Refuses an edge whose source, type, or concept value lies outside the
243    /// `nodes` concepts and `type_count` attribute types.
244    fn check_range(nodes: u32, type_count: u32, edges: &[Edge]) -> Result<(), AttributesError> {
245        for edge in edges {
246            let target_ok = match edge.value {
247                Value::Concept(target) => target.index() < nodes,
248                Value::Number(_) | Value::String(_) => true,
249            };
250            if edge.source.index() >= nodes || edge.kind >= type_count || !target_ok {
251                return Err(AttributesError::OutOfRange {
252                    from: edge.source.index(),
253                    kind: edge.kind,
254                    nodes,
255                    types: type_count,
256                });
257            }
258        }
259        Ok(())
260    }
261
262    /// The row arrays of `nodes` concepts read off the sorted `edges`, with the
263    /// number and string values interned; the inverted index is not derived yet.
264    fn pack(nodes: u32, types: Vec<u64>, edges: &[Edge]) -> Result<Self, AttributesError> {
265        let mut interned: BTreeMap<String, u32> = BTreeMap::new();
266        let mut strings = Vec::new();
267        let mut intern = |text: &str| -> Result<u32, AttributesError> {
268            if let Some(&index) = interned.get(text) {
269                return Ok(index);
270            }
271            let index = u32::try_from(strings.len()).map_err(AttributesError::TooMany)?;
272            strings.push(text.to_owned());
273            interned.insert(text.to_owned(), index);
274            Ok(index)
275        };
276        let mut offsets = Vec::with_capacity(to_usize(nodes).saturating_add(1));
277        let (mut groups, mut kinds, mut tags, mut payloads) =
278            (Vec::new(), Vec::new(), Vec::new(), Vec::new());
279        let mut cursor = 0_usize;
280        for node in 0..nodes {
281            offsets.push(u32::try_from(groups.len()).unwrap_or(u32::MAX));
282            while let Some(edge) = edges.get(cursor) {
283                if edge.source.index() != node {
284                    break;
285                }
286                groups.push(edge.group);
287                kinds.push(edge.kind);
288                let (tag, payload) = match &edge.value {
289                    Value::Concept(target) => (TAG_CONCEPT, target.index()),
290                    Value::Number(text) => (TAG_NUMBER, intern(text)?),
291                    Value::String(text) => (TAG_STRING, intern(text)?),
292                };
293                tags.push(tag);
294                payloads.push(payload);
295                cursor = cursor.saturating_add(1);
296            }
297        }
298        offsets.push(u32::try_from(groups.len()).unwrap_or(u32::MAX));
299        Ok(Self {
300            types,
301            offsets,
302            groups,
303            kinds,
304            tags,
305            payloads,
306            strings,
307            inverted: Vec::new(),
308        })
309    }
310
311    /// Builds the inverted index from the rows.
312    fn derive(&mut self) {
313        let mut pairs: Vec<Vec<(u32, u32)>> = vec![Vec::new(); self.types.len()];
314        let mut all: Vec<RoaringBitmap> = vec![RoaringBitmap::new(); self.types.len()];
315        for node in 0..self.nodes() {
316            for row in self.rows(Ordinal::new(node)) {
317                let kind = to_usize(row.kind);
318                if let Some(set) = all.get_mut(kind) {
319                    set.insert(node);
320                }
321                if let (ValueRef::Concept(target), Some(list)) = (row.value, pairs.get_mut(kind)) {
322                    list.push((target.index(), node));
323                }
324            }
325        }
326        self.inverted = pairs
327            .into_iter()
328            .zip(all)
329            .map(|(pairs, all_sources)| Inverted::build(pairs, all_sources))
330            .collect();
331    }
332
333    /// The attribute type SCTIDs, in type-index order.
334    #[must_use]
335    pub fn types(&self) -> &[u64] {
336        &self.types
337    }
338
339    /// The type index of `sctid`.
340    #[must_use]
341    pub fn kind(&self, sctid: u64) -> Option<u32> {
342        self.types
343            .iter()
344            .position(|&t| t == sctid)
345            .and_then(|i| u32::try_from(i).ok())
346    }
347
348    /// The number of concepts.
349    #[must_use]
350    pub fn nodes(&self) -> u32 {
351        u32::try_from(self.offsets.len().saturating_sub(1)).unwrap_or(u32::MAX)
352    }
353
354    /// The number of rows.
355    #[must_use]
356    pub fn edges(&self) -> usize {
357        self.groups.len()
358    }
359
360    /// The rows of `source`, sorted by group, then type, then value.
361    pub fn rows(&self, source: Ordinal) -> impl Iterator<Item = Row<'_>> + '_ {
362        let index = to_usize(source.index());
363        let (start, end) = match (
364            self.offsets.get(index),
365            self.offsets.get(index.saturating_add(1)),
366        ) {
367            (Some(&s), Some(&e)) => (to_usize(s), to_usize(e)),
368            _ => (0, 0),
369        };
370        (start..end).filter_map(move |i| {
371            Some(Row {
372                group: *self.groups.get(i)?,
373                kind: *self.kinds.get(i)?,
374                value: match (*self.tags.get(i)?, *self.payloads.get(i)?) {
375                    (TAG_CONCEPT, target) => ValueRef::Concept(Ordinal::new(target)),
376                    (TAG_NUMBER, text) => ValueRef::Number(self.strings.get(to_usize(text))?),
377                    (_, text) => ValueRef::String(self.strings.get(to_usize(text))?),
378                },
379            })
380        })
381    }
382
383    /// The sources with a relationship of type `kind` to `target`, sorted.
384    #[must_use]
385    pub fn sources(&self, kind: u32, target: Ordinal) -> &[u32] {
386        self.inverted
387            .get(to_usize(kind))
388            .map_or(&[], |inverted| inverted.sources(target.index()))
389    }
390
391    /// Every source with a relationship of type `kind`, whatever its value.
392    #[must_use]
393    pub fn sources_of_kind(&self, kind: u32) -> Option<&RoaringBitmap> {
394        self.inverted.get(to_usize(kind)).map(|i| &i.all_sources)
395    }
396
397    /// The destination concepts of type `kind`, sorted.
398    #[must_use]
399    pub fn targets_of_kind(&self, kind: u32) -> &[u32] {
400        self.inverted
401            .get(to_usize(kind))
402            .map_or(&[], |i| i.targets.as_slice())
403    }
404
405    /// Writes the layout.
406    ///
407    /// # Errors
408    ///
409    /// Returns [`AttributesError::Io`] when writing fails.
410    pub fn write_to(&self, out: &mut impl Write) -> Result<(), AttributesError> {
411        let count = |len: usize| u32::try_from(len).map_err(AttributesError::TooMany);
412        out.write_all(MAGIC)?;
413        out.write_all(&VERSION.to_le_bytes())?;
414        out.write_all(&count(self.types.len())?.to_le_bytes())?;
415        for sctid in &self.types {
416            out.write_all(&sctid.to_le_bytes())?;
417        }
418        out.write_all(&self.nodes().to_le_bytes())?;
419        write_u32s(out, &self.offsets)?;
420        out.write_all(&count(self.groups.len())?.to_le_bytes())?;
421        write_u32s(out, &self.groups)?;
422        write_u32s(out, &self.kinds)?;
423        out.write_all(&self.tags)?;
424        write_u32s(out, &self.payloads)?;
425        out.write_all(&count(self.strings.len())?.to_le_bytes())?;
426        for text in &self.strings {
427            out.write_all(&count(text.len())?.to_le_bytes())?;
428            out.write_all(text.as_bytes())?;
429        }
430        Ok(())
431    }
432
433    /// Reads the layout and derives the inverted index.
434    ///
435    /// # Errors
436    ///
437    /// Returns [`AttributesError`] for a truncated, inconsistent, or foreign
438    /// artifact.
439    pub fn read_from(input: &mut impl Read) -> Result<Self, AttributesError> {
440        let mut magic = [0_u8; 8];
441        input.read_exact(&mut magic)?;
442        if &magic != MAGIC {
443            return Err(AttributesError::Magic);
444        }
445        let version = read_u32(input)?;
446        if version != VERSION {
447            return Err(AttributesError::Version {
448                found: version,
449                expected: VERSION,
450            });
451        }
452        let type_count = read_u32(input)?;
453        let mut types = Vec::with_capacity(to_usize(type_count));
454        for _ in 0..type_count {
455            let mut long = [0_u8; 8];
456            input.read_exact(&mut long)?;
457            types.push(u64::from_le_bytes(long));
458        }
459        let nodes = read_u32(input)?;
460        let offsets = read_u32s(input, to_usize(nodes).saturating_add(1))?;
461        let rows = to_usize(read_u32(input)?);
462        let groups = read_u32s(input, rows)?;
463        let kinds = read_u32s(input, rows)?;
464        let mut tags = vec![0_u8; rows];
465        input.read_exact(&mut tags)?;
466        let payloads = read_u32s(input, rows)?;
467        let string_count = read_u32(input)?;
468        let mut strings = Vec::with_capacity(to_usize(string_count));
469        for _ in 0..string_count {
470            let len = to_usize(read_u32(input)?);
471            let mut bytes = vec![0_u8; len];
472            input.read_exact(&mut bytes)?;
473            strings.push(String::from_utf8(bytes)?);
474        }
475        let consistent = offsets.last().is_some_and(|&l| to_usize(l) == rows)
476            && offsets.windows(2).all(|w| w.first() <= w.get(1))
477            && kinds.iter().all(|&k| to_usize(k) < types.len())
478            && tags
479                .iter()
480                .zip(&payloads)
481                .all(|(&tag, &payload)| match tag {
482                    TAG_CONCEPT => payload < nodes,
483                    TAG_NUMBER | TAG_STRING => to_usize(payload) < strings.len(),
484                    _ => false,
485                });
486        if !consistent {
487            return Err(AttributesError::Inconsistent);
488        }
489        let mut attributes = Self {
490            types,
491            offsets,
492            groups,
493            kinds,
494            tags,
495            payloads,
496            strings,
497            inverted: Vec::new(),
498        };
499        attributes.derive();
500        Ok(attributes)
501    }
502}
503
504fn write_u32s(out: &mut impl Write, values: &[u32]) -> Result<(), AttributesError> {
505    for value in values {
506        out.write_all(&value.to_le_bytes())?;
507    }
508    Ok(())
509}
510
511fn read_u32(input: &mut impl Read) -> Result<u32, AttributesError> {
512    let mut bytes = [0_u8; 4];
513    input.read_exact(&mut bytes)?;
514    Ok(u32::from_le_bytes(bytes))
515}
516
517fn read_u32s(input: &mut impl Read, count: usize) -> Result<Vec<u32>, AttributesError> {
518    let mut bytes = vec![0_u8; count.saturating_mul(4)];
519    input.read_exact(&mut bytes)?;
520    Ok(bytes
521        .as_chunks::<4>()
522        .0
523        .iter()
524        .map(|chunk| u32::from_le_bytes(*chunk))
525        .collect())
526}
527
528#[cfg(test)]
529mod tests {
530    use super::{Attributes, AttributesError, Edge, Value, ValueRef};
531    use crate::ordinal::Ordinal;
532
533    fn sample() -> Attributes {
534        let edge = |source: u32, group: u32, kind: u32, value: Value| Edge {
535            source: Ordinal::new(source),
536            group,
537            kind,
538            value,
539        };
540        Attributes::build(
541            5,
542            vec![100, 200],
543            vec![
544                edge(1, 1, 0, Value::Concept(Ordinal::new(3))),
545                edge(1, 1, 1, Value::Number(String::from("4"))),
546                edge(2, 0, 0, Value::Concept(Ordinal::new(3))),
547                edge(2, 2, 1, Value::Number(String::from("4"))),
548                edge(2, 0, 0, Value::Concept(Ordinal::new(3))),
549                edge(4, 0, 1, Value::String(String::from("blue"))),
550            ],
551        )
552        .expect("builds")
553    }
554
555    #[test]
556    fn rows_are_grouped_and_the_inverted_index_answers_by_type_and_target() {
557        let attributes = sample();
558        assert_eq!(attributes.edges(), 5, "the duplicate row is dropped");
559        let cat: Vec<_> = attributes.rows(Ordinal::new(1)).collect();
560        assert_eq!(cat.len(), 2);
561        assert_eq!(cat[0].group, 1);
562        assert_eq!(cat[0].value, ValueRef::Concept(Ordinal::new(3)));
563        assert_eq!(cat[1].value, ValueRef::Number("4"));
564        assert_eq!(attributes.sources(0, Ordinal::new(3)), [1, 2]);
565        assert!(attributes.sources(1, Ordinal::new(3)).is_empty());
566        assert_eq!(attributes.targets_of_kind(0), [3]);
567        assert_eq!(
568            attributes
569                .sources_of_kind(1)
570                .expect("kind")
571                .iter()
572                .collect::<Vec<_>>(),
573            [1, 2, 4]
574        );
575        assert_eq!(attributes.kind(200), Some(1));
576        assert_eq!(attributes.kind(300), None);
577        assert_eq!(
578            attributes.rows(Ordinal::new(4)).next().expect("row").value,
579            ValueRef::String("blue")
580        );
581        assert!(attributes.rows(Ordinal::new(0)).next().is_none());
582    }
583
584    #[test]
585    fn the_layout_round_trips_and_refuses_bad_input() {
586        let attributes = sample();
587        let mut bytes = Vec::new();
588        attributes.write_to(&mut bytes).expect("writes");
589        let again = Attributes::read_from(&mut bytes.as_slice()).expect("reads");
590        assert_eq!(again, attributes);
591        assert!(matches!(
592            Attributes::read_from(&mut b"nope".as_slice()),
593            Err(AttributesError::Io(_))
594        ));
595        assert!(matches!(
596            Attributes::build(
597                2,
598                vec![1],
599                vec![Edge {
600                    source: Ordinal::new(1),
601                    group: 0,
602                    kind: 1,
603                    value: Value::Concept(Ordinal::new(0)),
604                }]
605            ),
606            Err(AttributesError::OutOfRange { kind: 1, .. })
607        ));
608        let mut wrong = bytes.clone();
609        wrong[0] = b'X';
610        assert!(matches!(
611            Attributes::read_from(&mut wrong.as_slice()),
612            Err(AttributesError::Magic)
613        ));
614    }
615}
concept_graph/attributes.rs

concept_graph/
attributes.rs
