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

concept_graph/
refsets.rs
