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    /// Adds the table of `refset` with `fields` (names and kinds beyond the
278    /// referenced component) and its active `rows`.
279    ///
280    /// # Errors
281    ///
282    /// Returns [`RefsetsError::Arity`] when a row's values do not match the
283    /// fields, and [`RefsetsError::TooMany`] past `u32`.
284    pub fn insert(
285        &mut self,
286        refset: u64,
287        fields: &[(String, FieldKind)],
288        rows: Vec<MemberRow>,
289    ) -> Result<(), RefsetsError> {
290        let mut table = Table {
291            fields: fields.iter().map(|(name, _)| name.clone()).collect(),
292            kinds: fields.iter().map(|(_, kind)| *kind).collect(),
293            ..Table::default()
294        };
295        let mut interned: BTreeMap<String, u32> = BTreeMap::new();
296        let mut longs_seen: BTreeMap<u64, u32> = BTreeMap::new();
297        for row in rows {
298            if row.values.len() != table.fields.len() {
299                return Err(RefsetsError::Arity {
300                    refset,
301                    values: row.values.len(),
302                    fields: table.fields.len(),
303                });
304            }
305            table.concepts.push(row.concept.index());
306            table.members.insert(row.concept.index());
307            table.times.push(row.effective_time);
308            table.modules.push(row.module);
309            for value in row.values {
310                let (tag, payload) = match value {
311                    FieldValue::Concept(concept) => (TAG_CONCEPT, concept.index()),
312                    FieldValue::Component(id) => (
313                        TAG_COMPONENT,
314                        intern_long(&mut table.longs, &mut longs_seen, id)?,
315                    ),
316                    FieldValue::Integer(value) => (
317                        TAG_INTEGER,
318                        intern_long(
319                            &mut table.longs,
320                            &mut longs_seen,
321                            u64::from_le_bytes(value.to_le_bytes()),
322                        )?,
323                    ),
324                    FieldValue::String(text) => {
325                        let index = if let Some(&index) = interned.get(&text) {
326                            index
327                        } else {
328                            let index = u32::try_from(table.strings.len())
329                                .map_err(RefsetsError::TooMany)?;
330                            table.strings.push(text.clone());
331                            interned.insert(text, index);
332                            index
333                        };
334                        (TAG_STRING, index)
335                    }
336                };
337                table.tags.push(tag);
338                table.payloads.push(payload);
339            }
340        }
341        u32::try_from(table.concepts.len()).map_err(RefsetsError::TooMany)?;
342        self.tables.insert(refset, table);
343        Ok(())
344    }
345
346    /// The table of `refset`.
347    #[must_use]
348    pub fn table(&self, refset: u64) -> Option<&Table> {
349        self.tables.get(&refset)
350    }
351
352    /// The reference sets, ascending.
353    pub fn refsets(&self) -> impl Iterator<Item = u64> + '_ {
354        self.tables.keys().copied()
355    }
356
357    /// The number of reference sets.
358    #[must_use]
359    pub fn len(&self) -> usize {
360        self.tables.len()
361    }
362
363    /// Whether there are no reference sets.
364    #[must_use]
365    pub fn is_empty(&self) -> bool {
366        self.tables.is_empty()
367    }
368
369    /// The number of rows over every reference set.
370    #[must_use]
371    pub fn total(&self) -> u64 {
372        self.tables
373            .values()
374            .map(|t| u64::try_from(t.len()).unwrap_or(u64::MAX))
375            .sum()
376    }
377
378    /// Writes the layout.
379    ///
380    /// # Errors
381    ///
382    /// Returns [`RefsetsError::Io`] when writing fails.
383    pub fn write_to(&self, out: &mut impl Write) -> Result<(), RefsetsError> {
384        let count = |len: usize| u32::try_from(len).map_err(RefsetsError::TooMany);
385        out.write_all(MAGIC)?;
386        out.write_all(&VERSION.to_le_bytes())?;
387        out.write_all(&count(self.tables.len())?.to_le_bytes())?;
388        for (refset, table) in &self.tables {
389            out.write_all(&refset.to_le_bytes())?;
390            out.write_all(&count(table.fields.len())?.to_le_bytes())?;
391            for (name, kind) in table.fields.iter().zip(&table.kinds) {
392                write_text(out, name)?;
393                out.write_all(&[match kind {
394                    FieldKind::Component => 0,
395                    FieldKind::Integer => 1,
396                    FieldKind::String => 2,
397                }])?;
398            }
399            out.write_all(&count(table.concepts.len())?.to_le_bytes())?;
400            write_u32s(out, &table.concepts)?;
401            write_u32s(out, &table.times)?;
402            for module in &table.modules {
403                out.write_all(&module.to_le_bytes())?;
404            }
405            out.write_all(&table.tags)?;
406            write_u32s(out, &table.payloads)?;
407            out.write_all(&count(table.longs.len())?.to_le_bytes())?;
408            for long in &table.longs {
409                out.write_all(&long.to_le_bytes())?;
410            }
411            out.write_all(&count(table.strings.len())?.to_le_bytes())?;
412            for text in &table.strings {
413                write_text(out, text)?;
414            }
415        }
416        Ok(())
417    }
418
419    /// Reads the layout and derives the member bitmaps.
420    ///
421    /// # Errors
422    ///
423    /// Returns [`RefsetsError`] for a truncated, inconsistent, or foreign
424    /// artifact.
425    pub fn read_from(input: &mut impl Read) -> Result<Self, RefsetsError> {
426        let mut magic = [0_u8; 8];
427        input.read_exact(&mut magic)?;
428        if &magic != MAGIC {
429            return Err(RefsetsError::Magic);
430        }
431        let version = read_u32(input)?;
432        if version != VERSION {
433            return Err(RefsetsError::Version {
434                found: version,
435                expected: VERSION,
436            });
437        }
438        let mut tables = BTreeMap::new();
439        for _ in 0..read_u32(input)? {
440            let refset = read_u64(input)?;
441            let field_count = to_usize(read_u32(input)?);
442            let mut fields = Vec::with_capacity(field_count);
443            let mut kinds = Vec::with_capacity(field_count);
444            for _ in 0..field_count {
445                fields.push(read_text(input)?);
446                let mut kind = [0_u8; 1];
447                input.read_exact(&mut kind)?;
448                kinds.push(match kind[0] {
449                    0 => FieldKind::Component,
450                    1 => FieldKind::Integer,
451                    2 => FieldKind::String,
452                    _ => return Err(RefsetsError::Inconsistent),
453                });
454            }
455            let rows = to_usize(read_u32(input)?);
456            let concepts = read_u32s(input, rows)?;
457            let times = read_u32s(input, rows)?;
458            let mut modules = Vec::with_capacity(rows);
459            for _ in 0..rows {
460                modules.push(read_u64(input)?);
461            }
462            let cells = rows.saturating_mul(field_count);
463            let mut tags = vec![0_u8; cells];
464            input.read_exact(&mut tags)?;
465            let payloads = read_u32s(input, cells)?;
466            let mut longs = Vec::new();
467            for _ in 0..read_u32(input)? {
468                longs.push(read_u64(input)?);
469            }
470            let mut strings = Vec::new();
471            for _ in 0..read_u32(input)? {
472                strings.push(read_text(input)?);
473            }
474            let members = concepts.iter().copied().collect();
475            let table = Table {
476                fields,
477                kinds,
478                concepts,
479                times,
480                modules,
481                tags,
482                payloads,
483                longs,
484                strings,
485                members,
486            };
487            table.check()?;
488            tables.insert(refset, table);
489        }
490        Ok(Self { tables })
491    }
492}
493
494fn intern_long(
495    longs: &mut Vec<u64>,
496    seen: &mut BTreeMap<u64, u32>,
497    value: u64,
498) -> Result<u32, RefsetsError> {
499    if let Some(&index) = seen.get(&value) {
500        return Ok(index);
501    }
502    let index = u32::try_from(longs.len()).map_err(RefsetsError::TooMany)?;
503    longs.push(value);
504    seen.insert(value, index);
505    Ok(index)
506}
507
508fn write_text(out: &mut impl Write, text: &str) -> Result<(), RefsetsError> {
509    let len = u32::try_from(text.len()).map_err(RefsetsError::TooMany)?;
510    out.write_all(&len.to_le_bytes())?;
511    out.write_all(text.as_bytes())?;
512    Ok(())
513}
514
515fn read_text(input: &mut impl Read) -> Result<String, RefsetsError> {
516    let len = to_usize(read_u32(input)?);
517    let mut bytes = vec![0_u8; len];
518    input.read_exact(&mut bytes)?;
519    Ok(String::from_utf8(bytes)?)
520}
521
522fn write_u32s(out: &mut impl Write, values: &[u32]) -> Result<(), RefsetsError> {
523    for value in values {
524        out.write_all(&value.to_le_bytes())?;
525    }
526    Ok(())
527}
528
529fn read_u32(input: &mut impl Read) -> Result<u32, RefsetsError> {
530    let mut bytes = [0_u8; 4];
531    input.read_exact(&mut bytes)?;
532    Ok(u32::from_le_bytes(bytes))
533}
534
535fn read_u64(input: &mut impl Read) -> Result<u64, RefsetsError> {
536    let mut bytes = [0_u8; 8];
537    input.read_exact(&mut bytes)?;
538    Ok(u64::from_le_bytes(bytes))
539}
540
541fn read_u32s(input: &mut impl Read, count: usize) -> Result<Vec<u32>, RefsetsError> {
542    let mut bytes = vec![0_u8; count.saturating_mul(4)];
543    input.read_exact(&mut bytes)?;
544    Ok(bytes
545        .as_chunks::<4>()
546        .0
547        .iter()
548        .map(|chunk| u32::from_le_bytes(*chunk))
549        .collect())
550}
551
552#[cfg(test)]
553mod tests {
554    use super::{FieldKind, FieldValue, MemberRow, RefsetMembers, RefsetsError, ValueRef};
555    use crate::ordinal::Ordinal;
556
557    fn sample() -> RefsetMembers {
558        let mut members = RefsetMembers::default();
559        members
560            .insert(
561                42,
562                &[
563                    (String::from("mapGroup"), FieldKind::Integer),
564                    (String::from("mapTarget"), FieldKind::String),
565                    (String::from("correlationId"), FieldKind::Component),
566                ],
567                vec![
568                    MemberRow {
569                        concept: Ordinal::new(2),
570                        effective_time: 20_240_101,
571                        module: 99,
572                        values: vec![
573                            FieldValue::Integer(1),
574                            FieldValue::String(String::from("J45.9")),
575                            FieldValue::Concept(Ordinal::new(7)),
576                        ],
577                    },
578                    MemberRow {
579                        concept: Ordinal::new(3),
580                        effective_time: 20_230_731,
581                        module: 99,
582                        values: vec![
583                            FieldValue::Integer(-2),
584                            FieldValue::String(String::from("J45.9")),
585                            FieldValue::Component(123_456_789_012),
586                        ],
587                    },
588                ],
589            )
590            .expect("inserts");
591        members
592            .insert(7, &[], vec![])
593            .expect("an empty simple reference set");
594        members
595    }
596
597    #[test]
598    fn rows_answer_by_field_and_the_layout_round_trips() {
599        let members = sample();
600        let table = members.table(42).expect("table");
601        assert_eq!(table.len(), 2);
602        assert_eq!(table.field("MAPTARGET"), Some(1));
603        assert_eq!(table.value(0, 0), Some(ValueRef::Integer(1)));
604        assert_eq!(table.value(1, 0), Some(ValueRef::Integer(-2)));
605        assert_eq!(table.value(1, 1), Some(ValueRef::String("J45.9")));
606        assert_eq!(table.value(0, 2), Some(ValueRef::Concept(Ordinal::new(7))));
607        assert_eq!(
608            table.value(1, 2),
609            Some(ValueRef::Component(123_456_789_012))
610        );
611        assert_eq!(table.value(1, 3), None);
612        assert_eq!(table.effective_time(1), Some(20_230_731));
613        assert_eq!(table.members().iter().collect::<Vec<_>>(), [2, 3]);
614        assert_eq!(table.rows_with(2, Ordinal::new(7)).collect::<Vec<_>>(), [0]);
615        assert_eq!(table.rows_of(Ordinal::new(3)).collect::<Vec<_>>(), [1]);
616        assert_eq!(
617            table.rows_of(Ordinal::new(9)).collect::<Vec<_>>(),
618            Vec::<usize>::new(),
619            "a concept the reference set does not name owns no row"
620        );
621        assert_eq!(members.total(), 2);
622        let mut bytes = Vec::new();
623        members.write_to(&mut bytes).expect("writes");
624        assert_eq!(
625            RefsetMembers::read_from(&mut bytes.as_slice()).expect("reads"),
626            members
627        );
628        assert!(matches!(
629            RefsetMembers::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
630            Err(RefsetsError::Magic)
631        ));
632        let mut bad = RefsetMembers::default();
633        assert!(matches!(
634            bad.insert(
635                1,
636                &[(String::from("f"), FieldKind::String)],
637                vec![MemberRow {
638                    concept: Ordinal::new(0),
639                    effective_time: 0,
640                    module: 0,
641                    values: Vec::new(),
642                }]
643            ),
644            Err(RefsetsError::Arity { .. })
645        ));
646    }
647}
concept_graph/refsets.rs

concept_graph/
refsets.rs
