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

triblespace_core/trible/
tribleset.rs
