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 additional field names, in column order.
133    #[must_use]
134    pub fn fields(&self) -> &[String] {
135        &self.fields
136    }
137
138    /// The additional field kinds, in column order.
139    #[must_use]
140    pub fn kinds(&self) -> &[FieldKind] {
141        &self.kinds
142    }
143
144    /// The column of the field named `name`, case-insensitively.
145    #[must_use]
146    pub fn field(&self, name: &str) -> Option<usize> {
147        self.fields
148            .iter()
149            .position(|f| f.eq_ignore_ascii_case(name))
150    }
151
152    /// The number of rows.
153    #[must_use]
154    pub fn len(&self) -> usize {
155        self.concepts.len()
156    }
157
158    /// Whether the table has no rows.
159    #[must_use]
160    pub fn is_empty(&self) -> bool {
161        self.concepts.is_empty()
162    }
163
164    /// The member concepts.
165    #[must_use]
166    pub fn members(&self) -> &RoaringBitmap {
167        &self.members
168    }
169
170    /// The referenced concept of row `row`.
171    #[must_use]
172    pub fn concept(&self, row: usize) -> Option<Ordinal> {
173        self.concepts.get(row).map(|&c| Ordinal::new(c))
174    }
175
176    /// The effective time of row `row`, as `YYYYMMDD`.
177    #[must_use]
178    pub fn effective_time(&self, row: usize) -> Option<u32> {
179        self.times.get(row).copied()
180    }
181
182    /// The module SCTID of row `row`.
183    #[must_use]
184    pub fn module(&self, row: usize) -> Option<u64> {
185        self.modules.get(row).copied()
186    }
187
188    /// The value of `field` (a column) in row `row`.
189    #[must_use]
190    pub fn value(&self, row: usize, field: usize) -> Option<ValueRef<'_>> {
191        if field >= self.fields.len() {
192            return None;
193        }
194        let index = row.checked_mul(self.fields.len())?.checked_add(field)?;
195        let payload = to_usize(*self.payloads.get(index)?);
196        Some(match *self.tags.get(index)? {
197            TAG_CONCEPT => ValueRef::Concept(Ordinal::new(*self.payloads.get(index)?)),
198            TAG_COMPONENT => ValueRef::Component(*self.longs.get(payload)?),
199            TAG_INTEGER => {
200                ValueRef::Integer(i64::from_le_bytes(self.longs.get(payload)?.to_le_bytes()))
201            }
202            _ => ValueRef::String(self.strings.get(payload)?),
203        })
204    }
205
206    /// The rows whose `field` holds the concept `target`.
207    pub fn rows_with(&self, field: usize, target: Ordinal) -> impl Iterator<Item = usize> + '_ {
208        (0..self.len())
209            .filter(move |&row| self.value(row, field) == Some(ValueRef::Concept(target)))
210    }
211
212    /// The rows whose referenced concept is `concept`.
213    pub fn rows_of(&self, concept: Ordinal) -> impl Iterator<Item = usize> + '_ {
214        self.concepts
215            .iter()
216            .enumerate()
217            .filter(move |&(_, &held)| held == concept.index())
218            .map(|(row, _)| row)
219    }
220
221    fn check(&self) -> Result<(), RefsetsError> {
222        let rows = self.concepts.len();
223        let cells = rows.saturating_mul(self.fields.len());
224        let consistent = self.kinds.len() == self.fields.len()
225            && self.times.len() == rows
226            && self.modules.len() == rows
227            && self.tags.len() == cells
228            && self.payloads.len() == cells
229            && self
230                .tags
231                .iter()
232                .zip(&self.payloads)
233                .all(|(&tag, &payload)| match tag {
234                    TAG_CONCEPT => true,
235                    TAG_COMPONENT | TAG_INTEGER => to_usize(payload) < self.longs.len(),
236                    TAG_STRING => to_usize(payload) < self.strings.len(),
237                    _ => false,
238                });
239        consistent.then_some(()).ok_or(RefsetsError::Inconsistent)
240    }
241}
242
243/// The member tables of every reference set, by SCTID.
244#[derive(Debug, Clone, PartialEq, Eq, Default)]
245pub struct RefsetMembers {
246    tables: BTreeMap<u64, Table>,
247}
248
249impl RefsetMembers {
250    /// An empty set of tables.
251    #[must_use]
252    pub fn new() -> Self {
253        Self::default()
254    }
255
256    /// Adds the table of `refset` with `fields` (names and kinds beyond the
257    /// referenced component) and its active `rows`.
258    ///
259    /// # Errors
260    ///
261    /// Returns [`RefsetsError::Arity`] when a row's values do not match the
262    /// fields, and [`RefsetsError::TooMany`] past `u32`.
263    pub fn insert(
264        &mut self,
265        refset: u64,
266        fields: &[(String, FieldKind)],
267        rows: Vec<MemberRow>,
268    ) -> Result<(), RefsetsError> {
269        let mut table = Table {
270            fields: fields.iter().map(|(name, _)| name.clone()).collect(),
271            kinds: fields.iter().map(|(_, kind)| *kind).collect(),
272            ..Table::default()
273        };
274        let mut interned: BTreeMap<String, u32> = BTreeMap::new();
275        let mut longs_seen: BTreeMap<u64, u32> = BTreeMap::new();
276        for row in rows {
277            if row.values.len() != table.fields.len() {
278                return Err(RefsetsError::Arity {
279                    refset,
280                    values: row.values.len(),
281                    fields: table.fields.len(),
282                });
283            }
284            table.concepts.push(row.concept.index());
285            table.members.insert(row.concept.index());
286            table.times.push(row.effective_time);
287            table.modules.push(row.module);
288            for value in row.values {
289                let (tag, payload) = match value {
290                    FieldValue::Concept(concept) => (TAG_CONCEPT, concept.index()),
291                    FieldValue::Component(id) => (
292                        TAG_COMPONENT,
293                        intern_long(&mut table.longs, &mut longs_seen, id)?,
294                    ),
295                    FieldValue::Integer(value) => (
296                        TAG_INTEGER,
297                        intern_long(
298                            &mut table.longs,
299                            &mut longs_seen,
300                            u64::from_le_bytes(value.to_le_bytes()),
301                        )?,
302                    ),
303                    FieldValue::String(text) => {
304                        let index = if let Some(&index) = interned.get(&text) {
305                            index
306                        } else {
307                            let index = u32::try_from(table.strings.len())
308                                .map_err(RefsetsError::TooMany)?;
309                            table.strings.push(text.clone());
310                            interned.insert(text, index);
311                            index
312                        };
313                        (TAG_STRING, index)
314                    }
315                };
316                table.tags.push(tag);
317                table.payloads.push(payload);
318            }
319        }
320        u32::try_from(table.concepts.len()).map_err(RefsetsError::TooMany)?;
321        self.tables.insert(refset, table);
322        Ok(())
323    }
324
325    /// The table of `refset`.
326    #[must_use]
327    pub fn table(&self, refset: u64) -> Option<&Table> {
328        self.tables.get(&refset)
329    }
330
331    /// The reference sets, ascending.
332    pub fn refsets(&self) -> impl Iterator<Item = u64> + '_ {
333        self.tables.keys().copied()
334    }
335
336    /// The number of reference sets.
337    #[must_use]
338    pub fn len(&self) -> usize {
339        self.tables.len()
340    }
341
342    /// Whether there are no reference sets.
343    #[must_use]
344    pub fn is_empty(&self) -> bool {
345        self.tables.is_empty()
346    }
347
348    /// The number of rows over every reference set.
349    #[must_use]
350    pub fn total(&self) -> u64 {
351        self.tables
352            .values()
353            .map(|t| u64::try_from(t.len()).unwrap_or(u64::MAX))
354            .sum()
355    }
356
357    /// Writes the layout.
358    ///
359    /// # Errors
360    ///
361    /// Returns [`RefsetsError::Io`] when writing fails.
362    pub fn write_to(&self, out: &mut impl Write) -> Result<(), RefsetsError> {
363        let count = |len: usize| u32::try_from(len).map_err(RefsetsError::TooMany);
364        out.write_all(MAGIC)?;
365        out.write_all(&VERSION.to_le_bytes())?;
366        out.write_all(&count(self.tables.len())?.to_le_bytes())?;
367        for (refset, table) in &self.tables {
368            out.write_all(&refset.to_le_bytes())?;
369            out.write_all(&count(table.fields.len())?.to_le_bytes())?;
370            for (name, kind) in table.fields.iter().zip(&table.kinds) {
371                write_text(out, name)?;
372                out.write_all(&[match kind {
373                    FieldKind::Component => 0,
374                    FieldKind::Integer => 1,
375                    FieldKind::String => 2,
376                }])?;
377            }
378            out.write_all(&count(table.concepts.len())?.to_le_bytes())?;
379            write_u32s(out, &table.concepts)?;
380            write_u32s(out, &table.times)?;
381            for module in &table.modules {
382                out.write_all(&module.to_le_bytes())?;
383            }
384            out.write_all(&table.tags)?;
385            write_u32s(out, &table.payloads)?;
386            out.write_all(&count(table.longs.len())?.to_le_bytes())?;
387            for long in &table.longs {
388                out.write_all(&long.to_le_bytes())?;
389            }
390            out.write_all(&count(table.strings.len())?.to_le_bytes())?;
391            for text in &table.strings {
392                write_text(out, text)?;
393            }
394        }
395        Ok(())
396    }
397
398    /// Reads the layout and derives the member bitmaps.
399    ///
400    /// # Errors
401    ///
402    /// Returns [`RefsetsError`] for a truncated, inconsistent, or foreign
403    /// artifact.
404    pub fn read_from(input: &mut impl Read) -> Result<Self, RefsetsError> {
405        let mut magic = [0_u8; 8];
406        input.read_exact(&mut magic)?;
407        if &magic != MAGIC {
408            return Err(RefsetsError::Magic);
409        }
410        let version = read_u32(input)?;
411        if version != VERSION {
412            return Err(RefsetsError::Version {
413                found: version,
414                expected: VERSION,
415            });
416        }
417        let mut tables = BTreeMap::new();
418        for _ in 0..read_u32(input)? {
419            let refset = read_u64(input)?;
420            let field_count = to_usize(read_u32(input)?);
421            let mut fields = Vec::with_capacity(field_count);
422            let mut kinds = Vec::with_capacity(field_count);
423            for _ in 0..field_count {
424                fields.push(read_text(input)?);
425                let mut kind = [0_u8; 1];
426                input.read_exact(&mut kind)?;
427                kinds.push(match kind[0] {
428                    0 => FieldKind::Component,
429                    1 => FieldKind::Integer,
430                    2 => FieldKind::String,
431                    _ => return Err(RefsetsError::Inconsistent),
432                });
433            }
434            let rows = to_usize(read_u32(input)?);
435            let concepts = read_u32s(input, rows)?;
436            let times = read_u32s(input, rows)?;
437            let mut modules = Vec::with_capacity(rows);
438            for _ in 0..rows {
439                modules.push(read_u64(input)?);
440            }
441            let cells = rows.saturating_mul(field_count);
442            let mut tags = vec![0_u8; cells];
443            input.read_exact(&mut tags)?;
444            let payloads = read_u32s(input, cells)?;
445            let mut longs = Vec::new();
446            for _ in 0..read_u32(input)? {
447                longs.push(read_u64(input)?);
448            }
449            let mut strings = Vec::new();
450            for _ in 0..read_u32(input)? {
451                strings.push(read_text(input)?);
452            }
453            let members = concepts.iter().copied().collect();
454            let table = Table {
455                fields,
456                kinds,
457                concepts,
458                times,
459                modules,
460                tags,
461                payloads,
462                longs,
463                strings,
464                members,
465            };
466            table.check()?;
467            tables.insert(refset, table);
468        }
469        Ok(Self { tables })
470    }
471}
472
473fn intern_long(
474    longs: &mut Vec<u64>,
475    seen: &mut BTreeMap<u64, u32>,
476    value: u64,
477) -> Result<u32, RefsetsError> {
478    if let Some(&index) = seen.get(&value) {
479        return Ok(index);
480    }
481    let index = u32::try_from(longs.len()).map_err(RefsetsError::TooMany)?;
482    longs.push(value);
483    seen.insert(value, index);
484    Ok(index)
485}
486
487fn write_text(out: &mut impl Write, text: &str) -> Result<(), RefsetsError> {
488    let len = u32::try_from(text.len()).map_err(RefsetsError::TooMany)?;
489    out.write_all(&len.to_le_bytes())?;
490    out.write_all(text.as_bytes())?;
491    Ok(())
492}
493
494fn read_text(input: &mut impl Read) -> Result<String, RefsetsError> {
495    let len = to_usize(read_u32(input)?);
496    let mut bytes = vec![0_u8; len];
497    input.read_exact(&mut bytes)?;
498    Ok(String::from_utf8(bytes)?)
499}
500
501fn write_u32s(out: &mut impl Write, values: &[u32]) -> Result<(), RefsetsError> {
502    for value in values {
503        out.write_all(&value.to_le_bytes())?;
504    }
505    Ok(())
506}
507
508fn read_u32(input: &mut impl Read) -> Result<u32, RefsetsError> {
509    let mut bytes = [0_u8; 4];
510    input.read_exact(&mut bytes)?;
511    Ok(u32::from_le_bytes(bytes))
512}
513
514fn read_u64(input: &mut impl Read) -> Result<u64, RefsetsError> {
515    let mut bytes = [0_u8; 8];
516    input.read_exact(&mut bytes)?;
517    Ok(u64::from_le_bytes(bytes))
518}
519
520fn read_u32s(input: &mut impl Read, count: usize) -> Result<Vec<u32>, RefsetsError> {
521    let mut bytes = vec![0_u8; count.saturating_mul(4)];
522    input.read_exact(&mut bytes)?;
523    Ok(bytes
524        .as_chunks::<4>()
525        .0
526        .iter()
527        .map(|chunk| u32::from_le_bytes(*chunk))
528        .collect())
529}
530
531#[cfg(test)]
532mod tests {
533    use super::{FieldKind, FieldValue, MemberRow, RefsetMembers, RefsetsError, ValueRef};
534    use crate::ordinal::Ordinal;
535
536    fn sample() -> RefsetMembers {
537        let mut members = RefsetMembers::new();
538        members
539            .insert(
540                42,
541                &[
542                    (String::from("mapGroup"), FieldKind::Integer),
543                    (String::from("mapTarget"), FieldKind::String),
544                    (String::from("correlationId"), FieldKind::Component),
545                ],
546                vec![
547                    MemberRow {
548                        concept: Ordinal::new(2),
549                        effective_time: 20_240_101,
550                        module: 99,
551                        values: vec![
552                            FieldValue::Integer(1),
553                            FieldValue::String(String::from("J45.9")),
554                            FieldValue::Concept(Ordinal::new(7)),
555                        ],
556                    },
557                    MemberRow {
558                        concept: Ordinal::new(3),
559                        effective_time: 20_230_731,
560                        module: 99,
561                        values: vec![
562                            FieldValue::Integer(-2),
563                            FieldValue::String(String::from("J45.9")),
564                            FieldValue::Component(123_456_789_012),
565                        ],
566                    },
567                ],
568            )
569            .expect("inserts");
570        members
571            .insert(7, &[], vec![])
572            .expect("an empty simple reference set");
573        members
574    }
575
576    #[test]
577    fn rows_answer_by_field_and_the_layout_round_trips() {
578        let members = sample();
579        let table = members.table(42).expect("table");
580        assert_eq!(table.len(), 2);
581        assert_eq!(table.field("MAPTARGET"), Some(1));
582        assert_eq!(table.value(0, 0), Some(ValueRef::Integer(1)));
583        assert_eq!(table.value(1, 0), Some(ValueRef::Integer(-2)));
584        assert_eq!(table.value(1, 1), Some(ValueRef::String("J45.9")));
585        assert_eq!(table.value(0, 2), Some(ValueRef::Concept(Ordinal::new(7))));
586        assert_eq!(
587            table.value(1, 2),
588            Some(ValueRef::Component(123_456_789_012))
589        );
590        assert_eq!(table.value(1, 3), None);
591        assert_eq!(table.effective_time(1), Some(20_230_731));
592        assert_eq!(table.members().iter().collect::<Vec<_>>(), [2, 3]);
593        assert_eq!(table.rows_with(2, Ordinal::new(7)).collect::<Vec<_>>(), [0]);
594        assert_eq!(table.rows_of(Ordinal::new(3)).collect::<Vec<_>>(), [1]);
595        assert_eq!(
596            table.rows_of(Ordinal::new(9)).collect::<Vec<_>>(),
597            Vec::<usize>::new(),
598            "a concept the reference set does not name owns no row"
599        );
600        assert_eq!(members.total(), 2);
601        let mut bytes = Vec::new();
602        members.write_to(&mut bytes).expect("writes");
603        assert_eq!(
604            RefsetMembers::read_from(&mut bytes.as_slice()).expect("reads"),
605            members
606        );
607        assert!(matches!(
608            RefsetMembers::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
609            Err(RefsetsError::Magic)
610        ));
611        let mut bad = RefsetMembers::new();
612        assert!(matches!(
613            bad.insert(
614                1,
615                &[(String::from("f"), FieldKind::String)],
616                vec![MemberRow {
617                    concept: Ordinal::new(0),
618                    effective_time: 0,
619                    module: 0,
620                    values: Vec::new(),
621                }]
622            ),
623            Err(RefsetsError::Arity { .. })
624        ));
625    }
626}
concept_graph/refsets.rs

concept_graph/
refsets.rs
