triblespace_core/trible/
tribleset.rs

1mod triblesetconstraint;
2
3use triblesetconstraint::*;
4
5use crate::query::TriblePattern;
6
7use crate::patch::Entry;
8use crate::patch::PATCH;
9use crate::query::Variable;
10use crate::trible::AEVOrder;
11use crate::trible::AVEOrder;
12use crate::trible::EAVOrder;
13use crate::trible::EVAOrder;
14use crate::trible::Trible;
15use crate::trible::VAEOrder;
16use crate::trible::VEAOrder;
17use crate::trible::TRIBLE_LEN;
18use crate::value::schemas::genid::GenId;
19use crate::value::ValueSchema;
20
21use std::iter::FromIterator;
22use std::iter::Map;
23use std::ops::Add;
24use std::ops::AddAssign;
25
26/// A collection of [Trible]s.
27///
28/// A [TribleSet] is a collection of [Trible]s that can be queried and manipulated.
29/// It supports efficient set operations like union, intersection, and difference.
30///
31/// The stored [Trible]s are indexed by the six possible orderings of their fields
32/// in corresponding [PATCH]es.
33///
34/// Clone is extremely cheap and can be used to create a snapshot of the current state of the [TribleSet].
35///
36/// Note that the [TribleSet] does not support an explicit `delete`/`remove` operation,
37/// as this would conflict with the CRDT semantics of the [TribleSet] and CALM principles as a whole.
38/// It does allow for set subtraction, but that operation is meant to compute the difference between two sets
39/// and not to remove elements from the set. A subtle but important distinction.
40#[derive(Debug, Clone)]
41pub struct TribleSet {
42    /// Entity → Attribute → Value index.
43    pub eav: PATCH<TRIBLE_LEN, EAVOrder, ()>,
44    /// Value → Entity → Attribute index.
45    pub vea: PATCH<TRIBLE_LEN, VEAOrder, ()>,
46    /// Attribute → Value → Entity index.
47    pub ave: PATCH<TRIBLE_LEN, AVEOrder, ()>,
48    /// Value → Attribute → Entity index.
49    pub vae: PATCH<TRIBLE_LEN, VAEOrder, ()>,
50    /// Entity → Value → Attribute index.
51    pub eva: PATCH<TRIBLE_LEN, EVAOrder, ()>,
52    /// Attribute → Entity → Value index.
53    pub aev: PATCH<TRIBLE_LEN, AEVOrder, ()>,
54}
55
56/// O(1) fingerprint for a [`TribleSet`], derived from the PATCH root hash.
57///
58/// This matches the equality semantics of `TribleSet`, but it is not stable
59/// across process boundaries because PATCH uses a per-process hash key.
60#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
61pub struct TribleSetFingerprint(Option<u128>);
62
63impl TribleSetFingerprint {
64    /// Fingerprint of an empty set.
65    pub const EMPTY: Self = Self(None);
66
67    /// Returns `true` for the empty-set fingerprint.
68    pub fn is_empty(self) -> bool {
69        self.0.is_none()
70    }
71
72    /// Returns the raw 128-bit hash, or `None` for an empty set.
73    pub fn as_u128(self) -> Option<u128> {
74        self.0
75    }
76}
77
78type TribleSetInner<'a> =
79    Map<crate::patch::PATCHIterator<'a, 64, EAVOrder, ()>, fn(&[u8; 64]) -> &Trible>;
80
81/// Iterator over the tribles in a [`TribleSet`], yielded in EAV order.
82pub struct TribleSetIterator<'a> {
83    inner: TribleSetInner<'a>,
84}
85
86impl TribleSet {
87    /// Union of two [TribleSet]s.
88    ///
89    /// The other [TribleSet] is consumed, and this [TribleSet] is updated in place.
90    pub fn union(&mut self, other: Self) {
91        self.eav.union(other.eav);
92        self.eva.union(other.eva);
93        self.aev.union(other.aev);
94        self.ave.union(other.ave);
95        self.vea.union(other.vea);
96        self.vae.union(other.vae);
97    }
98
99    /// Returns a new set containing only tribles present in both sets.
100    pub fn intersect(&self, other: &Self) -> Self {
101        Self {
102            eav: self.eav.intersect(&other.eav),
103            eva: self.eva.intersect(&other.eva),
104            aev: self.aev.intersect(&other.aev),
105            ave: self.ave.intersect(&other.ave),
106            vea: self.vea.intersect(&other.vea),
107            vae: self.vae.intersect(&other.vae),
108        }
109    }
110
111    /// Returns a new set containing tribles in `self` but not in `other`.
112    pub fn difference(&self, other: &Self) -> Self {
113        Self {
114            eav: self.eav.difference(&other.eav),
115            eva: self.eva.difference(&other.eva),
116            aev: self.aev.difference(&other.aev),
117            ave: self.ave.difference(&other.ave),
118            vea: self.vea.difference(&other.vea),
119            vae: self.vae.difference(&other.vae),
120        }
121    }
122
123    /// Creates an empty set.
124    pub fn new() -> TribleSet {
125        TribleSet {
126            eav: PATCH::<TRIBLE_LEN, EAVOrder, ()>::new(),
127            eva: PATCH::<TRIBLE_LEN, EVAOrder, ()>::new(),
128            aev: PATCH::<TRIBLE_LEN, AEVOrder, ()>::new(),
129            ave: PATCH::<TRIBLE_LEN, AVEOrder, ()>::new(),
130            vea: PATCH::<TRIBLE_LEN, VEAOrder, ()>::new(),
131            vae: PATCH::<TRIBLE_LEN, VAEOrder, ()>::new(),
132        }
133    }
134
135    /// Returns the number of tribles in the set.
136    pub fn len(&self) -> usize {
137        self.eav.len() as usize
138    }
139
140    /// Returns `true` when the set contains no tribles.
141    pub fn is_empty(&self) -> bool {
142        self.len() == 0
143    }
144
145    /// Returns a fast fingerprint suitable for in-memory caching.
146    ///
147    /// The fingerprint matches `TribleSet` equality, but it is not stable
148    /// across process boundaries because PATCH uses a per-process hash key.
149    pub fn fingerprint(&self) -> TribleSetFingerprint {
150        TribleSetFingerprint(self.eav.root_hash())
151    }
152
153    /// Inserts a trible into all six covering indexes.
154    pub fn insert(&mut self, trible: &Trible) {
155        let key = Entry::new(&trible.data);
156        self.eav.insert(&key);
157        self.eva.insert(&key);
158        self.aev.insert(&key);
159        self.ave.insert(&key);
160        self.vea.insert(&key);
161        self.vae.insert(&key);
162    }
163
164    /// Returns `true` when the exact trible is present in the set.
165    pub fn contains(&self, trible: &Trible) -> bool {
166        self.eav.has_prefix(&trible.data)
167    }
168
169    /// Iterates over all tribles in EAV order.
170    pub fn iter(&self) -> TribleSetIterator<'_> {
171        TribleSetIterator {
172            inner: self
173                .eav
174                .iter()
175                .map(|data| Trible::as_transmute_raw_unchecked(data)),
176        }
177    }
178}
179
180impl PartialEq for TribleSet {
181    fn eq(&self, other: &Self) -> bool {
182        self.eav == other.eav
183    }
184}
185
186impl Eq for TribleSet {}
187
188impl Default for TribleSetFingerprint {
189    fn default() -> Self {
190        Self::EMPTY
191    }
192}
193
194impl From<&TribleSet> for TribleSetFingerprint {
195    fn from(set: &TribleSet) -> Self {
196        set.fingerprint()
197    }
198}
199
200impl AddAssign for TribleSet {
201    fn add_assign(&mut self, rhs: Self) {
202        self.union(rhs);
203    }
204}
205
206impl Add for TribleSet {
207    type Output = Self;
208
209    fn add(mut self, rhs: Self) -> Self::Output {
210        self.union(rhs);
211        self
212    }
213}
214
215impl FromIterator<Trible> for TribleSet {
216    fn from_iter<I: IntoIterator<Item = Trible>>(iter: I) -> Self {
217        let mut set = TribleSet::new();
218
219        for t in iter {
220            set.insert(&t);
221        }
222
223        set
224    }
225}
226
227impl TriblePattern for TribleSet {
228    type PatternConstraint<'a> = TribleSetConstraint;
229
230    fn pattern<V: ValueSchema>(
231        &self,
232        e: Variable<GenId>,
233        a: Variable<GenId>,
234        v: Variable<V>,
235    ) -> Self::PatternConstraint<'static> {
236        TribleSetConstraint::new(e, a, v, self.clone())
237    }
238}
239
240impl<'a> Iterator for TribleSetIterator<'a> {
241    type Item = &'a Trible;
242
243    fn next(&mut self) -> Option<Self::Item> {
244        self.inner.next()
245    }
246}
247
248impl<'a> IntoIterator for &'a TribleSet {
249    type Item = &'a Trible;
250    type IntoIter = TribleSetIterator<'a>;
251
252    fn into_iter(self) -> Self::IntoIter {
253        self.iter()
254    }
255}
256
257impl Default for TribleSet {
258    fn default() -> Self {
259        Self::new()
260    }
261}
262
263#[cfg(test)]
264mod tests {
265    use crate::examples::literature;
266    use crate::prelude::*;
267
268    use super::*;
269    use fake::faker::lorem::en::Words;
270    use fake::faker::name::raw::FirstName;
271    use fake::faker::name::raw::LastName;
272    use fake::locales::EN;
273    use fake::Fake;
274
275    use rayon::iter::IntoParallelIterator;
276    use rayon::iter::ParallelIterator;
277
278    #[test]
279    fn union() {
280        let mut kb = TribleSet::new();
281        for _i in 0..100 {
282            let author = ufoid();
283            let book = ufoid();
284            kb += entity! { &author @
285               literature::firstname: FirstName(EN).fake::<String>(),
286               literature::lastname: LastName(EN).fake::<String>(),
287            };
288            kb += entity! { &book @
289               literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
290               literature::author: &author
291            };
292        }
293        assert_eq!(kb.len(), 400);
294    }
295
296    #[test]
297    fn union_parallel() {
298        let kb = (0..1000)
299            .into_par_iter()
300            .flat_map(|_| {
301                let author = ufoid();
302                let book = ufoid();
303                [
304                    entity! { &author @
305                       literature::firstname: FirstName(EN).fake::<String>(),
306                       literature::lastname: LastName(EN).fake::<String>(),
307                    },
308                    entity! { &book @
309                       literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
310                       literature::author: &author
311                    },
312                ]
313            })
314            .reduce(Fragment::default, |a, b| a + b);
315        assert_eq!(kb.len(), 4000);
316    }
317
318    #[test]
319    fn intersection() {
320        let mut kb1 = TribleSet::new();
321        let mut kb2 = TribleSet::new();
322        for _i in 0..100 {
323            let author = ufoid();
324            let book = ufoid();
325            kb1 += entity! { &author @
326               literature::firstname: FirstName(EN).fake::<String>(),
327               literature::lastname: LastName(EN).fake::<String>(),
328            };
329            kb1 += entity! { &book @
330               literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
331               literature::author: &author
332            };
333            kb2 += entity! { &author @
334               literature::firstname: FirstName(EN).fake::<String>(),
335               literature::lastname: LastName(EN).fake::<String>(),
336            };
337            kb2 += entity! { &book @
338               literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
339               literature::author: &author
340            };
341        }
342        let intersection = kb1.intersect(&kb2);
343        // Verify that the intersection contains only elements present in both kb1 and kb2
344        for trible in &intersection {
345            assert!(kb1.contains(trible));
346            assert!(kb2.contains(trible));
347        }
348    }
349
350    #[test]
351    fn difference() {
352        let mut kb1 = TribleSet::new();
353        let mut kb2 = TribleSet::new();
354        for _i in 0..100 {
355            let author = ufoid();
356            let book = ufoid();
357            kb1 += entity! { &author @
358               literature::firstname: FirstName(EN).fake::<String>(),
359               literature::lastname: LastName(EN).fake::<String>(),
360            };
361            kb1 += entity! { &book @
362               literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
363               literature::author: &author
364            };
365            if _i % 2 == 0 {
366                kb2 += entity! { &author @
367                   literature::firstname: FirstName(EN).fake::<String>(),
368                   literature::lastname: LastName(EN).fake::<String>(),
369                };
370                kb2 += entity! { &book @
371                   literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
372                   literature::author: &author
373                };
374            }
375        }
376        let difference = kb1.difference(&kb2);
377        // Verify that the difference contains only elements present in kb1 but not in kb2
378        for trible in &difference {
379            assert!(kb1.contains(trible));
380            assert!(!kb2.contains(trible));
381        }
382    }
383
384    #[test]
385    fn test_contains() {
386        let mut kb = TribleSet::new();
387        let author = ufoid();
388        let book = ufoid();
389        let author_tribles = entity! { &author @
390           literature::firstname: FirstName(EN).fake::<String>(),
391           literature::lastname: LastName(EN).fake::<String>(),
392        };
393        let book_tribles = entity! { &book @
394           literature::title: Words(1..3).fake::<Vec<String>>().join(" "),
395           literature::author: &author
396        };
397
398        kb += author_tribles.clone();
399        kb += book_tribles.clone();
400
401        for trible in &author_tribles {
402            assert!(kb.contains(trible));
403        }
404        for trible in &book_tribles {
405            assert!(kb.contains(trible));
406        }
407
408        let non_existent_trible = entity! { &ufoid() @
409           literature::firstname: FirstName(EN).fake::<String>(),
410           literature::lastname: LastName(EN).fake::<String>(),
411        };
412
413        for trible in &non_existent_trible {
414            assert!(!kb.contains(trible));
415        }
416    }
417}
triblespace_core/trible/tribleset.rs

triblespace_core/trible/
tribleset.rs
