corium_core/
datom.rs

1//! Datoms and covering index key composition.
2
3use crate::{
4    AttrId, EntityId, TxId, Value,
5    encoding::{DecodeError, Encodable, decode_entity_id, decode_u64, decode_value},
6};
7
8/// A single immutable fact assertion or retraction.
9#[derive(Clone, Debug, Eq, PartialEq)]
10pub struct Datom {
11    /// Entity id.
12    pub e: EntityId,
13    /// Attribute id.
14    pub a: AttrId,
15    /// Value.
16    pub v: Value,
17    /// Transaction id.
18    pub tx: TxId,
19    /// Assertion (`true`) or retraction (`false`).
20    pub added: bool,
21}
22
23/// Covering index orders.
24#[derive(Clone, Copy, Debug, Eq, PartialEq)]
25pub enum IndexOrder {
26    /// Entity, attribute, value, transaction.
27    Eavt,
28    /// Attribute, entity, value, transaction.
29    Aevt,
30    /// Attribute, value, entity, transaction.
31    Avet,
32    /// Value, attribute, entity, transaction.
33    Vaet,
34}
35
36/// Byte width of the trailing `(tx, added)` component every covering-index
37/// key ends with (see [`encode_tx_added`]).
38pub const KEY_TX_SUFFIX_LEN: usize = 8;
39
40/// The `(e, a, v)` component prefix of a complete covering-index key.
41///
42/// Two datoms share a prefix exactly when they state the same fact, so a
43/// current-value index holds at most one entry per prefix and a retraction
44/// can find the assertion it cancels without knowing which transaction made
45/// it. Component encodings are self-delimiting, so no prefix is ever a byte
46/// prefix of another and sorting by prefix agrees with sorting by full key.
47#[must_use]
48pub fn key_components(key: &[u8]) -> &[u8] {
49    &key[..key.len().saturating_sub(KEY_TX_SUFFIX_LEN)]
50}
51
52impl Datom {
53    /// Returns this datom's byte key for the requested index order.
54    #[must_use]
55    pub fn key(&self, order: IndexOrder) -> Vec<u8> {
56        let mut out = Vec::new();
57        match order {
58            IndexOrder::Eavt => {
59                self.e.encode_into(&mut out);
60                self.a.encode_into(&mut out);
61                self.v.encode_into(&mut out);
62            }
63            IndexOrder::Aevt => {
64                self.a.encode_into(&mut out);
65                self.e.encode_into(&mut out);
66                self.v.encode_into(&mut out);
67            }
68            IndexOrder::Avet => {
69                self.a.encode_into(&mut out);
70                self.v.encode_into(&mut out);
71                self.e.encode_into(&mut out);
72            }
73            IndexOrder::Vaet => {
74                self.v.encode_into(&mut out);
75                self.a.encode_into(&mut out);
76                self.e.encode_into(&mut out);
77            }
78        }
79        encode_tx_added(self.tx, self.added, &mut out);
80        out
81    }
82
83    /// Decodes a complete covering-index key back into its datom.
84    ///
85    /// # Errors
86    /// Returns [`DecodeError`] when a component is truncated or malformed.
87    pub fn from_key(order: IndexOrder, input: &[u8]) -> Result<Self, DecodeError> {
88        let mut offset = 0;
89        let entity = |offset: &mut usize| {
90            let (value, used) = decode_entity_id(&input[*offset..])?;
91            *offset += used;
92            Ok::<_, DecodeError>(value)
93        };
94        let (e, a, v) = match order {
95            IndexOrder::Eavt => {
96                let e = entity(&mut offset)?;
97                let a = entity(&mut offset)?;
98                let (v, used) = decode_value(&input[offset..])?;
99                offset += used;
100                (e, a, v)
101            }
102            IndexOrder::Aevt => {
103                let a = entity(&mut offset)?;
104                let e = entity(&mut offset)?;
105                let (v, used) = decode_value(&input[offset..])?;
106                offset += used;
107                (e, a, v)
108            }
109            IndexOrder::Avet => {
110                let a = entity(&mut offset)?;
111                let (v, used) = decode_value(&input[offset..])?;
112                offset += used;
113                let e = entity(&mut offset)?;
114                (e, a, v)
115            }
116            IndexOrder::Vaet => {
117                let (v, used) = decode_value(&input[offset..])?;
118                offset += used;
119                let a = entity(&mut offset)?;
120                let e = entity(&mut offset)?;
121                (e, a, v)
122            }
123        };
124        let (tx_added, used) = decode_u64(&input[offset..])?;
125        offset += used;
126        if offset != input.len() {
127            return Err(DecodeError::Trailing);
128        }
129        Ok(Self {
130            e,
131            a,
132            v,
133            tx: EntityId::from_raw(tx_added >> 1),
134            added: tx_added & 1 == 1,
135        })
136    }
137}
138
139fn encode_tx_added(tx: TxId, added: bool, out: &mut Vec<u8>) {
140    ((tx.raw() << 1) | u64::from(added)).encode_into(out);
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    #[test]
148    fn covering_keys_round_trip() {
149        let datom = Datom {
150            e: EntityId::from_raw(42),
151            a: EntityId::from_raw(7),
152            v: Value::Str("a\0z".into()),
153            tx: EntityId::from_raw(19),
154            added: true,
155        };
156        for order in [
157            IndexOrder::Eavt,
158            IndexOrder::Aevt,
159            IndexOrder::Avet,
160            IndexOrder::Vaet,
161        ] {
162            let key = datom.key(order);
163            assert_eq!(Datom::from_key(order, &key), Ok(datom.clone()));
164        }
165    }
166
167    #[test]
168    fn key_components_strips_only_the_transaction_suffix() {
169        let datom = Datom {
170            e: EntityId::from_raw(42),
171            a: EntityId::from_raw(7),
172            v: Value::Str("a\0z".into()),
173            tx: EntityId::from_raw(19),
174            added: true,
175        };
176        // The same fact retracted by a later transaction shares the prefix,
177        // which is how a retraction finds the assertion it cancels.
178        let retraction = Datom {
179            tx: EntityId::from_raw(20),
180            added: false,
181            ..datom.clone()
182        };
183        for order in [
184            IndexOrder::Eavt,
185            IndexOrder::Aevt,
186            IndexOrder::Avet,
187            IndexOrder::Vaet,
188        ] {
189            let key = datom.key(order);
190            assert_eq!(key_components(&key).len(), key.len() - KEY_TX_SUFFIX_LEN);
191            assert!(key.starts_with(key_components(&key)));
192            assert_eq!(
193                key_components(&key),
194                key_components(&retraction.key(order)),
195                "a retraction must share the asserted fact's prefix"
196            );
197        }
198    }
199
200    #[test]
201    fn covering_key_rejects_trailing_bytes() {
202        let datom = Datom {
203            e: EntityId::from_raw(1),
204            a: EntityId::from_raw(2),
205            v: Value::Long(3),
206            tx: EntityId::from_raw(4),
207            added: false,
208        };
209        let mut key = datom.key(IndexOrder::Eavt);
210        key.push(0);
211        assert_eq!(
212            Datom::from_key(IndexOrder::Eavt, &key),
213            Err(DecodeError::Trailing)
214        );
215    }
216}
corium_core/datom.rs

corium_core/
datom.rs
