triblespace_core/blob/schemas/
succinctarchive.rs

1mod succinctarchiveconstraint;
2mod universe;
3
4use crate::blob::Blob;
5use crate::blob::BlobSchema;
6use crate::blob::ToBlob;
7use crate::blob::TryFromBlob;
8use crate::id::id_from_value;
9use crate::id::id_into_value;
10use crate::id::ExclusiveId;
11use crate::id::Id;
12use crate::id_hex;
13use crate::macros::entity;
14use crate::metadata;
15use crate::metadata::ConstMetadata;
16use crate::query::TriblePattern;
17use crate::repo::BlobStore;
18use crate::trible::Trible;
19use crate::trible::TribleSet;
20use crate::value::schemas::genid::GenId;
21use crate::value::schemas::hash::Blake3;
22use crate::value::schemas::UnknownValue;
23use crate::value::RawValue;
24use crate::value::Value;
25use crate::value::ValueSchema;
26use succinctarchiveconstraint::*;
27
28pub use universe::*;
29
30use std::convert::TryInto;
31use std::iter;
32
33use itertools::Itertools;
34
35use anybytes::area::{ByteArea, SectionWriter};
36use anybytes::Bytes;
37use jerky::bit_vector::rank9sel::Rank9SelIndex;
38use jerky::bit_vector::BitVector;
39use jerky::bit_vector::BitVectorBuilder;
40use jerky::bit_vector::BitVectorDataMeta;
41use jerky::bit_vector::NumBits;
42use jerky::bit_vector::Rank;
43use jerky::bit_vector::Select;
44use jerky::char_sequences::wavelet_matrix::WaveletMatrixMeta;
45use jerky::char_sequences::{WaveletMatrix, WaveletMatrixBuilder};
46use jerky::serialization::{Metadata, Serializable};
47
48pub struct SuccinctArchiveBlob;
49
50impl BlobSchema for SuccinctArchiveBlob {}
51
52impl ConstMetadata for SuccinctArchiveBlob {
53    fn id() -> Id {
54        id_hex!("8FAD1D4C7F884B51BAA5D6C56B873E41")
55    }
56
57    fn describe<B>(blobs: &mut B) -> Result<TribleSet, B::PutError>
58    where
59        B: BlobStore<Blake3>,
60    {
61        let id = Self::id();
62        let description = blobs.put(
63            "Succinct archive index for fast offline trible queries. The bytes store a compressed, query-friendly layout derived from a canonical trible set.\n\nUse for large, read-heavy, mostly immutable datasets where fast scans or joins matter more than incremental updates. Build it from a TribleSet or SimpleArchive, and keep a canonical source if you need to regenerate or validate the index.",
64        )?;
65        Ok(entity! {
66            ExclusiveId::force_ref(&id) @
67                metadata::name: blobs.put("succinctarchive".to_string())?,
68                metadata::description: description,
69                metadata::tag: metadata::KIND_BLOB_SCHEMA,
70        })
71    }
72}
73
74#[derive(Debug, Clone, Copy, zerocopy::FromBytes, zerocopy::KnownLayout, zerocopy::Immutable)]
75#[repr(C)]
76pub struct SuccinctArchiveMeta<D: Metadata> {
77    pub entity_count: usize,
78    pub attribute_count: usize,
79    pub value_count: usize,
80    pub domain: D,
81    pub e_a: BitVectorDataMeta,
82    pub a_a: BitVectorDataMeta,
83    pub v_a: BitVectorDataMeta,
84    pub changed_e_a: BitVectorDataMeta,
85    pub changed_e_v: BitVectorDataMeta,
86    pub changed_a_e: BitVectorDataMeta,
87    pub changed_a_v: BitVectorDataMeta,
88    pub changed_v_e: BitVectorDataMeta,
89    pub changed_v_a: BitVectorDataMeta,
90    pub eav_c: WaveletMatrixMeta,
91    pub vea_c: WaveletMatrixMeta,
92    pub ave_c: WaveletMatrixMeta,
93    pub vae_c: WaveletMatrixMeta,
94    pub eva_c: WaveletMatrixMeta,
95    pub aev_c: WaveletMatrixMeta,
96}
97
98fn build_prefix_bv<I>(
99    domain_len: usize,
100    triple_count: usize,
101    iter: I,
102    writer: &mut SectionWriter,
103) -> BitVector<Rank9SelIndex>
104where
105    I: IntoIterator<Item = (usize, usize)>,
106{
107    let mut builder =
108        BitVectorBuilder::from_bit(false, triple_count + domain_len + 1, writer).unwrap();
109
110    let mut seen = 0usize;
111    let mut last = 0usize;
112    for (val, count) in iter {
113        for c in last..=val {
114            builder.set_bit(seen + c, true).unwrap();
115        }
116        seen += count;
117        last = val + 1;
118    }
119    for c in last..=domain_len {
120        builder.set_bit(seen + c, true).unwrap();
121    }
122    builder.freeze::<Rank9SelIndex>()
123}
124
125#[derive(Debug, Clone)]
126pub struct SuccinctArchive<U> {
127    pub bytes: Bytes,
128    pub domain: U,
129
130    pub entity_count: usize,
131    pub attribute_count: usize,
132    pub value_count: usize,
133
134    pub e_a: BitVector<Rank9SelIndex>,
135    pub a_a: BitVector<Rank9SelIndex>,
136    pub v_a: BitVector<Rank9SelIndex>,
137
138    /// Bit vector marking the first occurrence of each `(entity, attribute)` pair
139    /// in `eav_c`.
140    pub changed_e_a: BitVector<Rank9SelIndex>,
141    /// Bit vector marking the first occurrence of each `(entity, value)` pair in
142    /// `eva_c`.
143    pub changed_e_v: BitVector<Rank9SelIndex>,
144    /// Bit vector marking the first occurrence of each `(attribute, entity)` pair
145    /// in `aev_c`.
146    pub changed_a_e: BitVector<Rank9SelIndex>,
147    /// Bit vector marking the first occurrence of each `(attribute, value)` pair
148    /// in `ave_c`.
149    pub changed_a_v: BitVector<Rank9SelIndex>,
150    /// Bit vector marking the first occurrence of each `(value, entity)` pair in
151    /// `vea_c`.
152    pub changed_v_e: BitVector<Rank9SelIndex>,
153    /// Bit vector marking the first occurrence of each `(value, attribute)` pair
154    /// in `vae_c`.
155    pub changed_v_a: BitVector<Rank9SelIndex>,
156
157    pub eav_c: WaveletMatrix<Rank9SelIndex>,
158    pub vea_c: WaveletMatrix<Rank9SelIndex>,
159    pub ave_c: WaveletMatrix<Rank9SelIndex>,
160    pub vae_c: WaveletMatrix<Rank9SelIndex>,
161    pub eva_c: WaveletMatrix<Rank9SelIndex>,
162    pub aev_c: WaveletMatrix<Rank9SelIndex>,
163}
164
165impl<U> SuccinctArchive<U>
166where
167    U: Universe,
168{
169    pub fn iter<'a>(&'a self) -> impl Iterator<Item = Trible> + 'a {
170        (0..self.eav_c.len()).map(move |v_i| {
171            let v = self.eav_c.access(v_i).unwrap();
172            let a_i = self.v_a.select1(v).unwrap() - v + self.eav_c.rank(v_i, v).unwrap();
173            let a = self.vea_c.access(a_i).unwrap();
174            let e_i = self.a_a.select1(a).unwrap() - a + self.vea_c.rank(a_i, a).unwrap();
175            let e = self.ave_c.access(e_i).unwrap();
176
177            let e = self.domain.access(e);
178            let a = self.domain.access(a);
179            let v = self.domain.access(v);
180
181            let e: Id = Id::new(id_from_value(&e).unwrap()).unwrap();
182            let a: Id = Id::new(id_from_value(&a).unwrap()).unwrap();
183            let v: Value<UnknownValue> = Value::new(v);
184
185            Trible::force(&e, &a, &v)
186        })
187    }
188
189    /// Count the number of set bits in `bv` within `range`.
190    ///
191    /// The bit vectors in this archive encode the first occurrence of each
192    /// component pair.  By counting the set bits between two offsets we can
193    /// quickly determine how many distinct pairs appear in that slice of the
194    /// index.
195    pub fn distinct_in(
196        &self,
197        bv: &BitVector<Rank9SelIndex>,
198        range: &std::ops::Range<usize>,
199    ) -> usize {
200        bv.rank1(range.end).unwrap() - bv.rank1(range.start).unwrap()
201    }
202
203    /// Enumerate the rotated offsets of set bits in `bv` within `range`.
204    ///
205    /// `bv` marks the first occurrence of component pairs in the ordering that
206    /// produced `col`.  For each selected bit this function reads the component
207    /// value from `col` and uses `prefix` to translate the index to the adjacent
208    /// orientation.  The iterator therefore yields indices positioned to access
209    /// the middle component of each pair.
210    pub fn enumerate_in<'a>(
211        &'a self,
212        bv: &'a BitVector<Rank9SelIndex>,
213        range: &std::ops::Range<usize>,
214        col: &'a WaveletMatrix<Rank9SelIndex>,
215        prefix: &'a BitVector<Rank9SelIndex>,
216    ) -> impl Iterator<Item = usize> + 'a {
217        let start = bv.rank1(range.start).unwrap();
218        let end = bv.rank1(range.end).unwrap();
219        (start..end).map(move |r| {
220            let idx = bv.select1(r).unwrap();
221            let val = col.access(idx).unwrap();
222            prefix.select1(val).unwrap() - val + col.rank(idx, val).unwrap()
223        })
224    }
225
226    /// Enumerate the identifiers present in `prefix` using `rank`/`select` to
227    /// jump directly to the next distinct prefix sum.
228    pub fn enumerate_domain<'a>(
229        &'a self,
230        prefix: &'a BitVector<Rank9SelIndex>,
231    ) -> impl Iterator<Item = RawValue> + 'a {
232        let zero_count = prefix.num_bits() - (self.domain.len() + 1);
233        let mut z = 0usize;
234        std::iter::from_fn(move || {
235            if z >= zero_count {
236                return None;
237            }
238            let pos = prefix.select0(z).unwrap();
239            let id = prefix.rank1(pos).unwrap() - 1;
240            z = prefix.rank0(prefix.select1(id + 1).unwrap()).unwrap();
241            Some(self.domain.access(id))
242        })
243    }
244
245    pub fn meta(&self) -> SuccinctArchiveMeta<U::Meta>
246    where
247        U: Serializable,
248    {
249        SuccinctArchiveMeta {
250            entity_count: self.entity_count,
251            attribute_count: self.attribute_count,
252            value_count: self.value_count,
253            domain: self.domain.metadata(),
254            e_a: self.e_a.metadata(),
255            a_a: self.a_a.metadata(),
256            v_a: self.v_a.metadata(),
257            changed_e_a: self.changed_e_a.metadata(),
258            changed_e_v: self.changed_e_v.metadata(),
259            changed_a_e: self.changed_a_e.metadata(),
260            changed_a_v: self.changed_a_v.metadata(),
261            changed_v_e: self.changed_v_e.metadata(),
262            changed_v_a: self.changed_v_a.metadata(),
263            eav_c: self.eav_c.metadata(),
264            vea_c: self.vea_c.metadata(),
265            ave_c: self.ave_c.metadata(),
266            vae_c: self.vae_c.metadata(),
267            eva_c: self.eva_c.metadata(),
268            aev_c: self.aev_c.metadata(),
269        }
270    }
271}
272
273impl<U> From<&TribleSet> for SuccinctArchive<U>
274where
275    U: Universe + Serializable<Error = jerky::error::Error>,
276    <U as Serializable>::Meta: Clone,
277{
278    fn from(set: &TribleSet) -> Self {
279        let triple_count = set.eav.len() as usize;
280
281        let entity_count = set.eav.segmented_len(&[0; 0]) as usize;
282        let attribute_count = set.ave.segmented_len(&[0; 0]) as usize;
283        let value_count = set.vea.segmented_len(&[0; 0]) as usize;
284
285        let e_iter = set
286            .eav
287            .iter_prefix_count::<16>()
288            .map(|(e, _)| id_into_value(&e));
289        let a_iter = set
290            .ave
291            .iter_prefix_count::<16>()
292            .map(|(a, _)| id_into_value(&a));
293        let v_iter = set.vea.iter_prefix_count::<32>().map(|(v, _)| v);
294
295        let mut area = ByteArea::new().unwrap();
296        let mut sections = area.sections();
297
298        let domain_iter = e_iter.merge(a_iter).merge(v_iter).dedup();
299        let domain = U::with_sorted_dedup(domain_iter, &mut sections);
300
301        let e_a = build_prefix_bv(
302            domain.len(),
303            triple_count,
304            set.eav.iter_prefix_count::<16>().map(|(e, c)| {
305                (
306                    domain.search(&id_into_value(&e)).expect("e in domain"),
307                    c as usize,
308                )
309            }),
310            &mut sections,
311        );
312
313        let a_a = build_prefix_bv(
314            domain.len(),
315            triple_count,
316            set.ave.iter_prefix_count::<16>().map(|(a, c)| {
317                (
318                    domain.search(&id_into_value(&a)).expect("a in domain"),
319                    c as usize,
320                )
321            }),
322            &mut sections,
323        );
324
325        let v_a = build_prefix_bv(
326            domain.len(),
327            triple_count,
328            set.vea
329                .iter_prefix_count::<32>()
330                .map(|(v, c)| (domain.search(&v).expect("v in domain"), c as usize)),
331            &mut sections,
332        );
333
334        let eav_c = {
335            let mut builder =
336                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
337                    .unwrap();
338            let mut iter = set
339                .eav
340                .iter_prefix_count::<64>()
341                .map(|(t, _)| t[32..64].try_into().unwrap())
342                .map(|v| domain.search(&v).expect("v in domain"));
343            builder.set_ints_from_iter(0, &mut iter).unwrap();
344            builder.freeze::<Rank9SelIndex>().unwrap()
345        };
346
347        let vea_c = {
348            let mut builder =
349                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
350                    .unwrap();
351            let mut iter = set
352                .vea
353                .iter_prefix_count::<64>()
354                .map(|(t, _)| id_into_value(t[48..64].try_into().unwrap()))
355                .map(|a| domain.search(&a).expect("a in domain"));
356            builder.set_ints_from_iter(0, &mut iter).unwrap();
357            builder.freeze::<Rank9SelIndex>().unwrap()
358        };
359
360        let ave_c = {
361            let mut builder =
362                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
363                    .unwrap();
364            let mut iter = set
365                .ave
366                .iter_prefix_count::<64>()
367                .map(|(t, _)| id_into_value(t[48..64].try_into().unwrap()))
368                .map(|e| domain.search(&e).expect("e in domain"));
369            builder.set_ints_from_iter(0, &mut iter).unwrap();
370            builder.freeze::<Rank9SelIndex>().unwrap()
371        };
372
373        let vae_c = {
374            let mut builder =
375                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
376                    .unwrap();
377            let mut iter = set
378                .vae
379                .iter_prefix_count::<64>()
380                .map(|(t, _)| id_into_value(t[48..64].try_into().unwrap()))
381                .map(|e| domain.search(&e).expect("e in domain"));
382            builder.set_ints_from_iter(0, &mut iter).unwrap();
383            builder.freeze::<Rank9SelIndex>().unwrap()
384        };
385
386        let eva_c = {
387            let mut builder =
388                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
389                    .unwrap();
390            let mut iter = set
391                .eva
392                .iter_prefix_count::<64>()
393                .map(|(t, _)| id_into_value(t[48..64].try_into().unwrap()))
394                .map(|a| domain.search(&a).expect("a in domain"));
395            builder.set_ints_from_iter(0, &mut iter).unwrap();
396            builder.freeze::<Rank9SelIndex>().unwrap()
397        };
398
399        let aev_c = {
400            let mut builder =
401                WaveletMatrixBuilder::with_capacity(domain.len(), triple_count, &mut sections)
402                    .unwrap();
403            let mut iter = set
404                .aev
405                .iter_prefix_count::<64>()
406                .map(|(t, _)| t[32..64].try_into().unwrap())
407                .map(|v| domain.search(&v).expect("v in domain"));
408            builder.set_ints_from_iter(0, &mut iter).unwrap();
409            builder.freeze::<Rank9SelIndex>().unwrap()
410        };
411
412        let changed_e_a = {
413            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
414            let mut bits = set.eav.iter_prefix_count::<32>().flat_map(|(_, c)| {
415                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
416            });
417            b.set_bits_from_iter(0, &mut bits).unwrap();
418            b.freeze::<Rank9SelIndex>()
419        };
420
421        let changed_e_v = {
422            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
423            let mut bits = set.eva.iter_prefix_count::<48>().flat_map(|(_, c)| {
424                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
425            });
426            b.set_bits_from_iter(0, &mut bits).unwrap();
427            b.freeze::<Rank9SelIndex>()
428        };
429
430        let changed_a_e = {
431            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
432            let mut bits = set.aev.iter_prefix_count::<32>().flat_map(|(_, c)| {
433                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
434            });
435            b.set_bits_from_iter(0, &mut bits).unwrap();
436            b.freeze::<Rank9SelIndex>()
437        };
438
439        let changed_a_v = {
440            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
441            let mut bits = set.ave.iter_prefix_count::<48>().flat_map(|(_, c)| {
442                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
443            });
444            b.set_bits_from_iter(0, &mut bits).unwrap();
445            b.freeze::<Rank9SelIndex>()
446        };
447
448        let changed_v_e = {
449            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
450            let mut bits = set.vea.iter_prefix_count::<48>().flat_map(|(_, c)| {
451                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
452            });
453            b.set_bits_from_iter(0, &mut bits).unwrap();
454            b.freeze::<Rank9SelIndex>()
455        };
456
457        let changed_v_a = {
458            let mut b = BitVectorBuilder::with_capacity(triple_count, &mut sections).unwrap();
459            let mut bits = set.vae.iter_prefix_count::<48>().flat_map(|(_, c)| {
460                iter::once(true).chain(std::iter::repeat_n(false, c as usize - 1))
461            });
462            b.set_bits_from_iter(0, &mut bits).unwrap();
463            b.freeze::<Rank9SelIndex>()
464        };
465
466        let meta = SuccinctArchiveMeta {
467            entity_count,
468            attribute_count,
469            value_count,
470            domain: domain.metadata(),
471            e_a: e_a.metadata(),
472            a_a: a_a.metadata(),
473            v_a: v_a.metadata(),
474            changed_e_a: changed_e_a.metadata(),
475            changed_e_v: changed_e_v.metadata(),
476            changed_a_e: changed_a_e.metadata(),
477            changed_a_v: changed_a_v.metadata(),
478            changed_v_e: changed_v_e.metadata(),
479            changed_v_a: changed_v_a.metadata(),
480            eav_c: eav_c.metadata(),
481            vea_c: vea_c.metadata(),
482            ave_c: ave_c.metadata(),
483            vae_c: vae_c.metadata(),
484            eva_c: eva_c.metadata(),
485            aev_c: aev_c.metadata(),
486        };
487
488        let mut meta_sec = sections.reserve::<SuccinctArchiveMeta<U::Meta>>(1).unwrap();
489        meta_sec.as_mut_slice()[0] = meta.clone();
490        meta_sec.freeze().unwrap();
491
492        let bytes = area.freeze().unwrap();
493
494        SuccinctArchive::from_bytes(meta, bytes).unwrap()
495    }
496}
497
498impl<U> From<&SuccinctArchive<U>> for TribleSet
499where
500    U: Universe,
501{
502    fn from(archive: &SuccinctArchive<U>) -> Self {
503        archive.iter().collect()
504    }
505}
506
507impl<U> TriblePattern for SuccinctArchive<U>
508where
509    U: Universe,
510{
511    type PatternConstraint<'a>
512        = SuccinctArchiveConstraint<'a, U>
513    where
514        U: 'a;
515
516    fn pattern<'a, V: ValueSchema>(
517        &'a self,
518        e: crate::query::Variable<GenId>,
519        a: crate::query::Variable<GenId>,
520        v: crate::query::Variable<V>,
521    ) -> Self::PatternConstraint<'a> {
522        SuccinctArchiveConstraint::new(e, a, v, self)
523    }
524}
525
526impl<U> Serializable for SuccinctArchive<U>
527where
528    U: Universe + Serializable<Error = jerky::error::Error>,
529{
530    type Meta = SuccinctArchiveMeta<U::Meta>;
531    type Error = jerky::error::Error;
532
533    fn metadata(&self) -> Self::Meta {
534        self.meta()
535    }
536
537    fn from_bytes(meta: Self::Meta, bytes: Bytes) -> Result<Self, Self::Error> {
538        let domain = U::from_bytes(meta.domain, bytes.clone())?;
539
540        let e_a = BitVector::from_bytes(meta.e_a, bytes.clone())?;
541        let a_a = BitVector::from_bytes(meta.a_a, bytes.clone())?;
542        let v_a = BitVector::from_bytes(meta.v_a, bytes.clone())?;
543        let changed_e_a = BitVector::from_bytes(meta.changed_e_a, bytes.clone())?;
544        let changed_e_v = BitVector::from_bytes(meta.changed_e_v, bytes.clone())?;
545        let changed_a_e = BitVector::from_bytes(meta.changed_a_e, bytes.clone())?;
546        let changed_a_v = BitVector::from_bytes(meta.changed_a_v, bytes.clone())?;
547        let changed_v_e = BitVector::from_bytes(meta.changed_v_e, bytes.clone())?;
548        let changed_v_a = BitVector::from_bytes(meta.changed_v_a, bytes.clone())?;
549
550        let eav_c = WaveletMatrix::from_bytes(meta.eav_c, bytes.clone())?;
551        let vea_c = WaveletMatrix::from_bytes(meta.vea_c, bytes.clone())?;
552        let ave_c = WaveletMatrix::from_bytes(meta.ave_c, bytes.clone())?;
553        let vae_c = WaveletMatrix::from_bytes(meta.vae_c, bytes.clone())?;
554        let eva_c = WaveletMatrix::from_bytes(meta.eva_c, bytes.clone())?;
555        let aev_c = WaveletMatrix::from_bytes(meta.aev_c, bytes.clone())?;
556
557        Ok(SuccinctArchive {
558            bytes,
559            domain,
560            entity_count: meta.entity_count,
561            attribute_count: meta.attribute_count,
562            value_count: meta.value_count,
563            e_a,
564            a_a,
565            v_a,
566            changed_e_a,
567            changed_e_v,
568            changed_a_e,
569            changed_a_v,
570            changed_v_e,
571            changed_v_a,
572            eav_c,
573            vea_c,
574            ave_c,
575            vae_c,
576            eva_c,
577            aev_c,
578        })
579    }
580}
581
582impl<U> ToBlob<SuccinctArchiveBlob> for &SuccinctArchive<U>
583where
584    U: Universe + Serializable,
585{
586    fn to_blob(self) -> Blob<SuccinctArchiveBlob> {
587        Blob::new(self.bytes.clone())
588    }
589}
590
591impl<U> ToBlob<SuccinctArchiveBlob> for SuccinctArchive<U>
592where
593    U: Universe + Serializable,
594{
595    fn to_blob(self) -> Blob<SuccinctArchiveBlob> {
596        Blob::new(self.bytes)
597    }
598}
599
600pub struct SuccinctArchiveError;
601
602impl std::error::Error for SuccinctArchiveError {}
603
604impl std::fmt::Display for SuccinctArchiveError {
605    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
606        write!(f, "SuccinctArchiveError")
607    }
608}
609
610impl std::fmt::Debug for SuccinctArchiveError {
611    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
612        write!(f, "SuccinctArchiveError")
613    }
614}
615
616impl<U> TryFromBlob<SuccinctArchiveBlob> for SuccinctArchive<U>
617where
618    U: Universe + Serializable<Error = jerky::error::Error>,
619    <U as Serializable>::Meta: Copy + 'static,
620{
621    type Error = SuccinctArchiveError;
622
623    fn try_from_blob(blob: Blob<SuccinctArchiveBlob>) -> Result<Self, Self::Error> {
624        let bytes = blob.bytes;
625        let mut tail = bytes.clone();
626        let meta = *tail
627            .view_suffix::<SuccinctArchiveMeta<U::Meta>>()
628            .map_err(|_| SuccinctArchiveError)?;
629        SuccinctArchive::from_bytes(meta, bytes).map_err(|_| SuccinctArchiveError)
630    }
631}
632
633#[cfg(test)]
634mod tests {
635    use std::convert::TryInto;
636
637    use crate::blob::ToBlob;
638    use crate::id::fucid;
639    use crate::prelude::*;
640    use crate::query::find;
641    use crate::trible::Trible;
642    use crate::value::ToValue;
643    use crate::value::TryToValue;
644
645    use super::*;
646    use anybytes::area::ByteArea;
647    use itertools::Itertools;
648    use proptest::prelude::*;
649
650    pub mod knights {
651        use crate::prelude::*;
652
653        attributes! {
654            "328edd7583de04e2bedd6bd4fd50e651" as loves: valueschemas::GenId;
655            "328147856cc1984f0806dbb824d2b4cb" as name: valueschemas::ShortString;
656            "328f2c33d2fdd675e733388770b2d6c4" as title: valueschemas::ShortString;
657        }
658    }
659
660    proptest! {
661        #[test]
662        fn create(entries in prop::collection::vec(prop::collection::vec(0u8..255, 64), 1..128)) {
663            let mut set = TribleSet::new();
664            for entry in entries {
665                let mut key = [0; 64];
666                key.iter_mut().set_from(entry.iter().cloned());
667                set.insert(&Trible{ data: key});
668            }
669
670            let _archive: SuccinctArchive<CompressedUniverse> = (&set).into();
671        }
672
673        #[test]
674        fn roundtrip(entries in prop::collection::vec(prop::collection::vec(0u8..255, 64), 1..128)) {
675            let mut set = TribleSet::new();
676            for entry in entries {
677                let mut key = [0; 64];
678                key.iter_mut().set_from(entry.iter().cloned());
679                set.insert(&Trible{ data: key});
680            }
681
682            let archive: SuccinctArchive<CompressedUniverse> = (&set).into();
683            let set_: TribleSet = (&archive).into();
684
685            assert_eq!(set, set_);
686        }
687
688        #[test]
689        fn ordered_universe(values in prop::collection::vec(prop::collection::vec(0u8..255, 32), 1..128)) {
690            let mut values: Vec<RawValue> = values.into_iter().map(|v| v.try_into().unwrap()).collect();
691            values.sort();
692            let mut area = ByteArea::new().unwrap();
693            let mut sections = area.sections();
694            let u = OrderedUniverse::with(values.iter().copied(), &mut sections);
695            drop(sections);
696            let _bytes = area.freeze().unwrap();
697            for i in 0..u.len() {
698                let original = values[i];
699                let reconstructed = u.access(i);
700                assert_eq!(original, reconstructed);
701            }
702            for i in 0..u.len() {
703                let original = Some(i);
704                let found = u.search(&values[i]);
705                assert_eq!(original, found);
706            }
707        }
708
709        #[test]
710        fn compressed_universe(values in prop::collection::vec(prop::collection::vec(0u8..255, 32), 1..128)) {
711            let mut values: Vec<RawValue> = values.into_iter().map(|v| v.try_into().unwrap()).collect();
712            values.sort();
713            let mut area = ByteArea::new().unwrap();
714            let mut sections = area.sections();
715            let u = CompressedUniverse::with(values.iter().copied(), &mut sections);
716            drop(sections);
717            let _bytes = area.freeze().unwrap();
718            for i in 0..u.len() {
719                let original = values[i];
720                let reconstructed = u.access(i);
721                assert_eq!(original, reconstructed);
722            }
723            for i in 0..u.len() {
724                let original = Some(i);
725                let found = u.search(&values[i]);
726                assert_eq!(original, found);
727            }
728        }
729    }
730
731    #[test]
732    fn archive_pattern() {
733        let juliet = fucid();
734        let romeo = fucid();
735
736        let mut kb = TribleSet::new();
737
738        kb += entity! { &juliet @
739           knights::name: "Juliet",
740           knights::loves: &romeo,
741           knights::title: "Maiden"
742        };
743        kb += entity! { &romeo @
744           knights::name: "Romeo",
745           knights::loves: &juliet,
746           knights::title: "Prince"
747        };
748        kb += entity! {
749           knights::name: "Angelica",
750           knights::title: "Nurse"
751        };
752
753        let archive: SuccinctArchive<OrderedUniverse> = (&kb).into();
754
755        let r: Vec<_> = find!(
756            (juliet, name),
757            pattern!(&archive, [
758            {knights::name: "Romeo",
759             knights::loves: ?juliet},
760            {?juliet @
761                knights::name: ?name
762            }])
763        )
764        .collect();
765        assert_eq!(
766            vec![((&juliet).to_value(), "Juliet".try_to_value().unwrap(),)],
767            r
768        );
769    }
770
771    #[test]
772    fn blob_roundtrip() {
773        let juliet = fucid();
774        let romeo = fucid();
775
776        let mut kb = TribleSet::new();
777
778        kb += entity! {&juliet @
779            knights::name: "Juliet",
780            knights::loves: &romeo,
781            knights::title: "Maiden"
782        };
783        kb += entity! {&romeo @
784            knights::name: "Romeo",
785            knights::loves: &juliet,
786            knights::title: "Prince"
787        };
788
789        let archive: SuccinctArchive<OrderedUniverse> = (&kb).into();
790        let blob = (&archive).to_blob();
791        let rebuilt: SuccinctArchive<OrderedUniverse> = blob.try_from_blob().unwrap();
792        let kb2: TribleSet = (&rebuilt).into();
793        assert_eq!(kb, kb2);
794    }
795}
triblespace_core/blob/schemas/succinctarchive.rs

triblespace_core/blob/schemas/
succinctarchive.rs
