concept_graph/
refsets.rs

1// SPDX-FileCopyrightText: Cadasto B.V.
2// SPDX-License-Identifier: BUSL-1.1
3
4//! The active members of every concept-referencing reference set, with their
5//! fields.
6//!
7//! [`crate::members::Memberships`] answers "is this concept a member" from a
8//! bitmap; this holds the rows behind it (the effective time, the module, and
9//! every additional field the reference set declares), so the ECL member
10//! filters, the reference set field selection, and the history supplements
11//! read the values. No spec governs the layout: our own design. Little-endian,
12//! a magic and version prefix, then per reference set its SCTID, its field
13//! names and kinds, the rows as parallel arrays, and the interned longs and
14//! strings.
15
16use std::collections::BTreeMap;
17use std::io::{self, Read, Write};
18
19use roaring::RoaringBitmap;
20
21use crate::ordinal::{Ordinal, to_usize};
22
23const MAGIC: &[u8; 8] = b"FTMBRS\0\0";
24const VERSION: u32 = 1;
25const TAG_CONCEPT: u8 = 0;
26const TAG_COMPONENT: u8 = 1;
27const TAG_INTEGER: u8 = 2;
28const TAG_STRING: u8 = 3;
29
30/// A failure while building, reading, or writing the members.
31#[derive(Debug, thiserror::Error)]
32pub enum RefsetsError {
33    /// A row has a different number of values than the table has fields.
34    #[error("reference set {refset} row has {values} values for {fields} fields")]
35    Arity {
36        /// The reference set.
37        refset: u64,
38        /// The values in the row.
39        values: usize,
40        /// The fields declared.
41        fields: usize,
42    },
43    /// More rows or interned values than the `u32` offsets address.
44    #[error("too many reference set rows")]
45    TooMany(#[source] std::num::TryFromIntError),
46    /// An I/O failure.
47    #[error("reference set members I/O failed")]
48    Io(#[from] io::Error),
49    /// The bytes do not start with the members magic.
50    #[error("not a reference set members artifact")]
51    Magic,
52    /// The layout version is not the one this build reads.
53    #[error("reference set members layout version {found}, expected {expected}")]
54    Version {
55        /// The version found.
56        found: u32,
57        /// The version this build reads.
58        expected: u32,
59    },
60    /// The arrays are inconsistent.
61    #[error("the reference set member arrays are inconsistent")]
62    Inconsistent,
63    /// A name or value is not UTF-8.
64    #[error("a reference set field is not UTF-8")]
65    Text(#[from] std::string::FromUtf8Error),
66}
67
68/// The kind of a reference set field, as its file name declares it.
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub enum FieldKind {
71    /// A component identifier (`c`).
72    Component,
73    /// An integer (`i`).
74    Integer,
75    /// A string (`s`).
76    String,
77}
78
79/// A field value as built.
80#[derive(Debug, Clone, PartialEq, Eq)]
81pub enum FieldValue {
82    /// A concept of the edition.
83    Concept(Ordinal),
84    /// A component identifier that is not a concept of the edition.
85    Component(u64),
86    /// An integer.
87    Integer(i64),
88    /// A string.
89    String(String),
90}
91
92/// A field value as read.
93#[derive(Debug, Clone, Copy, PartialEq, Eq)]
94pub enum ValueRef<'a> {
95    /// A concept of the edition.
96    Concept(Ordinal),
97    /// A component identifier that is not a concept of the edition.
98    Component(u64),
99    /// An integer.
100    Integer(i64),
101    /// A string.
102    String(&'a str),
103}
104
105/// One active member as built.
106#[derive(Debug, Clone, PartialEq, Eq)]
107pub struct MemberRow {
108    /// The referenced concept.
109    pub concept: Ordinal,
110    /// The effective time as `YYYYMMDD`.
111    pub effective_time: u32,
112    /// The module SCTID.
113    pub module: u64,
114    /// The additional fields, in the table's field order.
115    pub values: Vec<FieldValue>,
116}
117
118/// The members of one reference set.
119#[derive(Debug, Clone, PartialEq, Eq, Default)]
120pub struct Table {
121    fields: Vec<String>,
122    kinds: Vec<FieldKind>,
123    concepts: Vec<u32>,
124    times: Vec<u32>,
125    modules: Vec<u64>,
126    tags: Vec<u8>,
127    payloads: Vec<u32>,
128    longs: Vec<u64>,
129    strings: Vec<String>,
130    /// The member concepts; derived.
131    members: RoaringBitmap,
132}
133
134impl Table {
135    /// The heap bytes this table holds ([`crate::footprint`]).
136    #[must_use]
137    pub fn size_in_bytes(&self) -> usize {
138        crate::footprint::strings(&self.fields)
139            .saturating_add(crate::footprint::vector(&self.kinds))
140            .saturating_add(crate::footprint::vector(&self.concepts))
141            .saturating_add(crate::footprint::vector(&self.times))
142            .saturating_add(crate::footprint::vector(&self.modules))
143            .saturating_add(crate::footprint::vector(&self.tags))
144            .saturating_add(crate::footprint::vector(&self.payloads))
145            .saturating_add(crate::footprint::vector(&self.longs))
146            .saturating_add(crate::footprint::strings(&self.strings))
147            .saturating_add(crate::footprint::bitmap(&self.members))
148    }
149
150    /// The additional field names, in column order.
151    #[must_use]
152    pub fn fields(&self) -> &[String] {
153        &self.fields
154    }
155
156    /// The additional field kinds, in column order.
157    #[must_use]
158    pub fn kinds(&self) -> &[FieldKind] {
159        &self.kinds
160    }
161
162    /// The column of the field named `name`, case-insensitively.
163    #[must_use]
164    pub fn field(&self, name: &str) -> Option<usize> {
165        self.fields
166            .iter()
167            .position(|f| f.eq_ignore_ascii_case(name))
168    }
169
170    /// The number of rows.
171    #[must_use]
172    pub fn len(&self) -> usize {
173        self.concepts.len()
174    }
175
176    /// Whether the table has no rows.
177    #[must_use]
178    pub fn is_empty(&self) -> bool {
179        self.concepts.is_empty()
180    }
181
182    /// The member concepts.
183    #[must_use]
184    pub fn members(&self) -> &RoaringBitmap {
185        &self.members
186    }
187
188    /// The referenced concept of row `row`.
189    #[must_use]
190    pub fn concept(&self, row: usize) -> Option<Ordinal> {
191        self.concepts.get(row).map(|&c| Ordinal::new(c))
192    }
193
194    /// The effective time of row `row`, as `YYYYMMDD`.
195    #[must_use]
196    pub fn effective_time(&self, row: usize) -> Option<u32> {
197        self.times.get(row).copied()
198    }
199
200    /// The module SCTID of row `row`.
201    #[must_use]
202    pub fn module(&self, row: usize) -> Option<u64> {
203        self.modules.get(row).copied()
204    }
205
206    /// The value of `field` (a column) in row `row`.
207    #[must_use]
208    pub fn value(&self, row: usize, field: usize) -> Option<ValueRef<'_>> {
209        if field >= self.fields.len() {
210            return None;
211        }
212        let index = row.checked_mul(self.fields.len())?.checked_add(field)?;
213        let payload = to_usize(*self.payloads.get(index)?);
214        Some(match *self.tags.get(index)? {
215            TAG_CONCEPT => ValueRef::Concept(Ordinal::new(*self.payloads.get(index)?)),
216            TAG_COMPONENT => ValueRef::Component(*self.longs.get(payload)?),
217            TAG_INTEGER => {
218                ValueRef::Integer(i64::from_le_bytes(self.longs.get(payload)?.to_le_bytes()))
219            }
220            _ => ValueRef::String(self.strings.get(payload)?),
221        })
222    }
223
224    /// The rows whose `field` holds the concept `target`.
225    pub fn rows_with(&self, field: usize, target: Ordinal) -> impl Iterator<Item = usize> + '_ {
226        (0..self.len())
227            .filter(move |&row| self.value(row, field) == Some(ValueRef::Concept(target)))
228    }
229
230    /// The rows whose referenced concept is `concept`.
231    pub fn rows_of(&self, concept: Ordinal) -> impl Iterator<Item = usize> + '_ {
232        self.concepts
233            .iter()
234            .enumerate()
235            .filter(move |&(_, &held)| held == concept.index())
236            .map(|(row, _)| row)
237    }
238
239    fn check(&self) -> Result<(), RefsetsError> {
240        let rows = self.concepts.len();
241        let cells = rows.saturating_mul(self.fields.len());
242        let consistent = self.kinds.len() == self.fields.len()
243            && self.times.len() == rows
244            && self.modules.len() == rows
245            && self.tags.len() == cells
246            && self.payloads.len() == cells
247            && self
248                .tags
249                .iter()
250                .zip(&self.payloads)
251                .all(|(&tag, &payload)| match tag {
252                    TAG_CONCEPT => true,
253                    TAG_COMPONENT | TAG_INTEGER => to_usize(payload) < self.longs.len(),
254                    TAG_STRING => to_usize(payload) < self.strings.len(),
255                    _ => false,
256                });
257        consistent.then_some(()).ok_or(RefsetsError::Inconsistent)
258    }
259}
260
261/// The member tables of every reference set, by SCTID.
262#[derive(Debug, Clone, PartialEq, Eq, Default)]
263pub struct RefsetMembers {
264    tables: BTreeMap<u64, Table>,
265}
266
267impl RefsetMembers {
268    /// The heap bytes every member table holds ([`crate::footprint`]).
269    #[must_use]
270    pub fn size_in_bytes(&self) -> usize {
271        self.tables.values().fold(
272            crate::footprint::entries::<u64, Table>(self.tables.len()),
273            |total, table| total.saturating_add(table.size_in_bytes()),
274        )
275    }
276
277    /// An empty set of tables.
278    #[must_use]
279    pub fn new() -> Self {
280        Self::default()
281    }
282
283    /// Adds the table of `refset` with `fields` (names and kinds beyond the
284    /// referenced component) and its active `rows`.
285    ///
286    /// # Errors
287    ///
288    /// Returns [`RefsetsError::Arity`] when a row's values do not match the
289    /// fields, and [`RefsetsError::TooMany`] past `u32`.
290    pub fn insert(
291        &mut self,
292        refset: u64,
293        fields: &[(String, FieldKind)],
294        rows: Vec<MemberRow>,
295    ) -> Result<(), RefsetsError> {
296        let mut table = Table {
297            fields: fields.iter().map(|(name, _)| name.clone()).collect(),
298            kinds: fields.iter().map(|(_, kind)| *kind).collect(),
299            ..Table::default()
300        };
301        let mut interned: BTreeMap<String, u32> = BTreeMap::new();
302        let mut longs_seen: BTreeMap<u64, u32> = BTreeMap::new();
303        for row in rows {
304            if row.values.len() != table.fields.len() {
305                return Err(RefsetsError::Arity {
306                    refset,
307                    values: row.values.len(),
308                    fields: table.fields.len(),
309                });
310            }
311            table.concepts.push(row.concept.index());
312            table.members.insert(row.concept.index());
313            table.times.push(row.effective_time);
314            table.modules.push(row.module);
315            for value in row.values {
316                let (tag, payload) = match value {
317                    FieldValue::Concept(concept) => (TAG_CONCEPT, concept.index()),
318                    FieldValue::Component(id) => (
319                        TAG_COMPONENT,
320                        intern_long(&mut table.longs, &mut longs_seen, id)?,
321                    ),
322                    FieldValue::Integer(value) => (
323                        TAG_INTEGER,
324                        intern_long(
325                            &mut table.longs,
326                            &mut longs_seen,
327                            u64::from_le_bytes(value.to_le_bytes()),
328                        )?,
329                    ),
330                    FieldValue::String(text) => {
331                        let index = if let Some(&index) = interned.get(&text) {
332                            index
333                        } else {
334                            let index = u32::try_from(table.strings.len())
335                                .map_err(RefsetsError::TooMany)?;
336                            table.strings.push(text.clone());
337                            interned.insert(text, index);
338                            index
339                        };
340                        (TAG_STRING, index)
341                    }
342                };
343                table.tags.push(tag);
344                table.payloads.push(payload);
345            }
346        }
347        u32::try_from(table.concepts.len()).map_err(RefsetsError::TooMany)?;
348        self.tables.insert(refset, table);
349        Ok(())
350    }
351
352    /// The table of `refset`.
353    #[must_use]
354    pub fn table(&self, refset: u64) -> Option<&Table> {
355        self.tables.get(&refset)
356    }
357
358    /// The reference sets, ascending.
359    pub fn refsets(&self) -> impl Iterator<Item = u64> + '_ {
360        self.tables.keys().copied()
361    }
362
363    /// The number of reference sets.
364    #[must_use]
365    pub fn len(&self) -> usize {
366        self.tables.len()
367    }
368
369    /// Whether there are no reference sets.
370    #[must_use]
371    pub fn is_empty(&self) -> bool {
372        self.tables.is_empty()
373    }
374
375    /// The number of rows over every reference set.
376    #[must_use]
377    pub fn total(&self) -> u64 {
378        self.tables
379            .values()
380            .map(|t| u64::try_from(t.len()).unwrap_or(u64::MAX))
381            .sum()
382    }
383
384    /// Writes the layout.
385    ///
386    /// # Errors
387    ///
388    /// Returns [`RefsetsError::Io`] when writing fails.
389    pub fn write_to(&self, out: &mut impl Write) -> Result<(), RefsetsError> {
390        let count = |len: usize| u32::try_from(len).map_err(RefsetsError::TooMany);
391        out.write_all(MAGIC)?;
392        out.write_all(&VERSION.to_le_bytes())?;
393        out.write_all(&count(self.tables.len())?.to_le_bytes())?;
394        for (refset, table) in &self.tables {
395            out.write_all(&refset.to_le_bytes())?;
396            out.write_all(&count(table.fields.len())?.to_le_bytes())?;
397            for (name, kind) in table.fields.iter().zip(&table.kinds) {
398                write_text(out, name)?;
399                out.write_all(&[match kind {
400                    FieldKind::Component => 0,
401                    FieldKind::Integer => 1,
402                    FieldKind::String => 2,
403                }])?;
404            }
405            out.write_all(&count(table.concepts.len())?.to_le_bytes())?;
406            write_u32s(out, &table.concepts)?;
407            write_u32s(out, &table.times)?;
408            for module in &table.modules {
409                out.write_all(&module.to_le_bytes())?;
410            }
411            out.write_all(&table.tags)?;
412            write_u32s(out, &table.payloads)?;
413            out.write_all(&count(table.longs.len())?.to_le_bytes())?;
414            for long in &table.longs {
415                out.write_all(&long.to_le_bytes())?;
416            }
417            out.write_all(&count(table.strings.len())?.to_le_bytes())?;
418            for text in &table.strings {
419                write_text(out, text)?;
420            }
421        }
422        Ok(())
423    }
424
425    /// Reads the layout and derives the member bitmaps.
426    ///
427    /// # Errors
428    ///
429    /// Returns [`RefsetsError`] for a truncated, inconsistent, or foreign
430    /// artifact.
431    pub fn read_from(input: &mut impl Read) -> Result<Self, RefsetsError> {
432        let mut magic = [0_u8; 8];
433        input.read_exact(&mut magic)?;
434        if &magic != MAGIC {
435            return Err(RefsetsError::Magic);
436        }
437        let version = read_u32(input)?;
438        if version != VERSION {
439            return Err(RefsetsError::Version {
440                found: version,
441                expected: VERSION,
442            });
443        }
444        let mut tables = BTreeMap::new();
445        for _ in 0..read_u32(input)? {
446            let refset = read_u64(input)?;
447            let field_count = to_usize(read_u32(input)?);
448            let mut fields = Vec::with_capacity(field_count);
449            let mut kinds = Vec::with_capacity(field_count);
450            for _ in 0..field_count {
451                fields.push(read_text(input)?);
452                let mut kind = [0_u8; 1];
453                input.read_exact(&mut kind)?;
454                kinds.push(match kind[0] {
455                    0 => FieldKind::Component,
456                    1 => FieldKind::Integer,
457                    2 => FieldKind::String,
458                    _ => return Err(RefsetsError::Inconsistent),
459                });
460            }
461            let rows = to_usize(read_u32(input)?);
462            let concepts = read_u32s(input, rows)?;
463            let times = read_u32s(input, rows)?;
464            let mut modules = Vec::with_capacity(rows);
465            for _ in 0..rows {
466                modules.push(read_u64(input)?);
467            }
468            let cells = rows.saturating_mul(field_count);
469            let mut tags = vec![0_u8; cells];
470            input.read_exact(&mut tags)?;
471            let payloads = read_u32s(input, cells)?;
472            let mut longs = Vec::new();
473            for _ in 0..read_u32(input)? {
474                longs.push(read_u64(input)?);
475            }
476            let mut strings = Vec::new();
477            for _ in 0..read_u32(input)? {
478                strings.push(read_text(input)?);
479            }
480            let members = concepts.iter().copied().collect();
481            let table = Table {
482                fields,
483                kinds,
484                concepts,
485                times,
486                modules,
487                tags,
488                payloads,
489                longs,
490                strings,
491                members,
492            };
493            table.check()?;
494            tables.insert(refset, table);
495        }
496        Ok(Self { tables })
497    }
498}
499
500fn intern_long(
501    longs: &mut Vec<u64>,
502    seen: &mut BTreeMap<u64, u32>,
503    value: u64,
504) -> Result<u32, RefsetsError> {
505    if let Some(&index) = seen.get(&value) {
506        return Ok(index);
507    }
508    let index = u32::try_from(longs.len()).map_err(RefsetsError::TooMany)?;
509    longs.push(value);
510    seen.insert(value, index);
511    Ok(index)
512}
513
514fn write_text(out: &mut impl Write, text: &str) -> Result<(), RefsetsError> {
515    let len = u32::try_from(text.len()).map_err(RefsetsError::TooMany)?;
516    out.write_all(&len.to_le_bytes())?;
517    out.write_all(text.as_bytes())?;
518    Ok(())
519}
520
521fn read_text(input: &mut impl Read) -> Result<String, RefsetsError> {
522    let len = to_usize(read_u32(input)?);
523    let mut bytes = vec![0_u8; len];
524    input.read_exact(&mut bytes)?;
525    Ok(String::from_utf8(bytes)?)
526}
527
528fn write_u32s(out: &mut impl Write, values: &[u32]) -> Result<(), RefsetsError> {
529    for value in values {
530        out.write_all(&value.to_le_bytes())?;
531    }
532    Ok(())
533}
534
535fn read_u32(input: &mut impl Read) -> Result<u32, RefsetsError> {
536    let mut bytes = [0_u8; 4];
537    input.read_exact(&mut bytes)?;
538    Ok(u32::from_le_bytes(bytes))
539}
540
541fn read_u64(input: &mut impl Read) -> Result<u64, RefsetsError> {
542    let mut bytes = [0_u8; 8];
543    input.read_exact(&mut bytes)?;
544    Ok(u64::from_le_bytes(bytes))
545}
546
547fn read_u32s(input: &mut impl Read, count: usize) -> Result<Vec<u32>, RefsetsError> {
548    let mut bytes = vec![0_u8; count.saturating_mul(4)];
549    input.read_exact(&mut bytes)?;
550    Ok(bytes
551        .as_chunks::<4>()
552        .0
553        .iter()
554        .map(|chunk| u32::from_le_bytes(*chunk))
555        .collect())
556}
557
558#[cfg(test)]
559mod tests {
560    use super::{FieldKind, FieldValue, MemberRow, RefsetMembers, RefsetsError, ValueRef};
561    use crate::ordinal::Ordinal;
562
563    fn sample() -> RefsetMembers {
564        let mut members = RefsetMembers::new();
565        members
566            .insert(
567                42,
568                &[
569                    (String::from("mapGroup"), FieldKind::Integer),
570                    (String::from("mapTarget"), FieldKind::String),
571                    (String::from("correlationId"), FieldKind::Component),
572                ],
573                vec![
574                    MemberRow {
575                        concept: Ordinal::new(2),
576                        effective_time: 20_240_101,
577                        module: 99,
578                        values: vec![
579                            FieldValue::Integer(1),
580                            FieldValue::String(String::from("J45.9")),
581                            FieldValue::Concept(Ordinal::new(7)),
582                        ],
583                    },
584                    MemberRow {
585                        concept: Ordinal::new(3),
586                        effective_time: 20_230_731,
587                        module: 99,
588                        values: vec![
589                            FieldValue::Integer(-2),
590                            FieldValue::String(String::from("J45.9")),
591                            FieldValue::Component(123_456_789_012),
592                        ],
593                    },
594                ],
595            )
596            .expect("inserts");
597        members
598            .insert(7, &[], vec![])
599            .expect("an empty simple reference set");
600        members
601    }
602
603    #[test]
604    fn rows_answer_by_field_and_the_layout_round_trips() {
605        let members = sample();
606        let table = members.table(42).expect("table");
607        assert_eq!(table.len(), 2);
608        assert_eq!(table.field("MAPTARGET"), Some(1));
609        assert_eq!(table.value(0, 0), Some(ValueRef::Integer(1)));
610        assert_eq!(table.value(1, 0), Some(ValueRef::Integer(-2)));
611        assert_eq!(table.value(1, 1), Some(ValueRef::String("J45.9")));
612        assert_eq!(table.value(0, 2), Some(ValueRef::Concept(Ordinal::new(7))));
613        assert_eq!(
614            table.value(1, 2),
615            Some(ValueRef::Component(123_456_789_012))
616        );
617        assert_eq!(table.value(1, 3), None);
618        assert_eq!(table.effective_time(1), Some(20_230_731));
619        assert_eq!(table.members().iter().collect::<Vec<_>>(), [2, 3]);
620        assert_eq!(table.rows_with(2, Ordinal::new(7)).collect::<Vec<_>>(), [0]);
621        assert_eq!(table.rows_of(Ordinal::new(3)).collect::<Vec<_>>(), [1]);
622        assert_eq!(
623            table.rows_of(Ordinal::new(9)).collect::<Vec<_>>(),
624            Vec::<usize>::new(),
625            "a concept the reference set does not name owns no row"
626        );
627        assert_eq!(members.total(), 2);
628        let mut bytes = Vec::new();
629        members.write_to(&mut bytes).expect("writes");
630        assert_eq!(
631            RefsetMembers::read_from(&mut bytes.as_slice()).expect("reads"),
632            members
633        );
634        assert!(matches!(
635            RefsetMembers::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
636            Err(RefsetsError::Magic)
637        ));
638        let mut bad = RefsetMembers::new();
639        assert!(matches!(
640            bad.insert(
641                1,
642                &[(String::from("f"), FieldKind::String)],
643                vec![MemberRow {
644                    concept: Ordinal::new(0),
645                    effective_time: 0,
646                    module: 0,
647                    values: Vec::new(),
648                }]
649            ),
650            Err(RefsetsError::Arity { .. })
651        ));
652    }
653}
concept_graph/refsets.rs

concept_graph/
refsets.rs
