concept_graph/
refsets.rs

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

concept_graph/
refsets.rs
