Skip to main content

rete_core/
schema_section.rs

1//! The **SCHEMA** section (kind 9, SPEC §7.5): the class hierarchy, the
2//! per-level type rollups and lateral class links, the coherence axioms, the
3//! planner's per-predicate `query_stats` and the characteristic sets —
4//! computed **without the community dendrogram**, so any build writes it,
5//! `--no-pyramid` and the memory-bounded build included.
6//!
7//! These used to be blocks of the pyramid-meta (kind 4), built only after the
8//! dendrogram; a file without a pyramid had none of them, and the planner had
9//! no statistics on exactly the large files where it matters most.
10//!
11//! ## Layout
12//!
13//! ```text
14//! 0   16  digest: blake3(section[16..])[..16]  (the section is outside the header hash)
15//! 16  1   version (= 1)
16//! 17  …   varint len + bytes: the type predicate the rollups used (empty = no typing)
17//!     …   a pyramid-meta encoding (SPEC §7.3) with round 0, no superedges, no tiles,
18//!         no label block and no descriptors: [QSTATS_V1] [CHARSET_V1] [SCHEMA_V2]
19//! ```
20//!
21//! ## Rules (order-independent, so every builder writes the same bytes)
22//!
23//! Everything is computed over the **deduplicated** default graph:
24//! - the type predicate is `--type-predicate` when given, else `rdf:type`;
25//! - a subject's representative class is its type with the **smallest object
26//!   id**; instance counts count every type statement;
27//! - lateral links `(class(s), p, class(o))` skip the type and `subClassOf`
28//!   statements; `(literal)` / `(untyped)` are the object sentinels;
29//! - levels carry `round = 0` (there is no dendrogram to align with);
30//! - characteristic sets: the 128 commonest exact predicate sets.
31
32use std::collections::{BTreeMap, BTreeSet, HashMap};
33
34use crate::meta::{CharSet, ClassNode, LevelLinks, LevelRollup, PredStat, PyramidMeta};
35use crate::varint::{read_uvarint, write_uvarint};
36
37/// Section format version written by this crate.
38const VERSION: u8 = 1;
39/// Length of the leading digest.
40const DIGEST_LEN: usize = 16;
41/// Characteristic sets kept (the same bound as the pyramid's block).
42const MAX_CHAR_SETS: usize = 128;
43/// Distinct predicate sets tracked before singletons are pruned.
44const MAX_TRACKED_SHAPES: usize = 1 << 20;
45
46/// `rdfs:subClassOf`.
47pub(crate) const RDFS_SUBCLASS_OF: &str = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
48/// `owl:disjointWith`.
49pub(crate) const OWL_DISJOINT_WITH: &str = "<http://www.w3.org/2002/07/owl#disjointWith>";
50/// `owl:equivalentClass`.
51pub(crate) const OWL_EQUIVALENT_CLASS: &str = "<http://www.w3.org/2002/07/owl#equivalentClass>";
52
53/// Class code of an object with no class.
54pub(crate) const UNTYPED: u32 = u32::MAX;
55/// Class code of a literal object.
56pub(crate) const LITERAL: u32 = u32::MAX - 1;
57
58/// A decoded SCHEMA section — or, for a file built before it existed, the same
59/// fields read from the pyramid-meta (see [`SchemaMeta::from_pyramid`]).
60#[derive(Debug, Clone, Default, PartialEq)]
61pub struct SchemaMeta {
62    /// The type predicate the class rollups used; `None` when the graph has no
63    /// typing (or the fields came from a pyramid-meta, which does not say).
64    pub type_predicate: Option<String>,
65    /// Per-predicate cardinality for the planner; see [`PredStat`].
66    pub predicate_stats: Vec<PredStat>,
67    /// The commonest entity shapes; see [`CharSet`].
68    pub char_sets: Vec<CharSet>,
69    /// The `subClassOf` DAG with per-class depth.
70    pub class_hierarchy: Vec<ClassNode>,
71    /// The per-level type histograms.
72    pub level_rollups: Vec<LevelRollup>,
73    /// The per-level lateral class-relation graphs.
74    pub level_links: Vec<LevelLinks>,
75    /// `subClassOf` cycles.
76    pub subclass_cycles: Vec<Vec<String>>,
77    /// `owl:disjointWith` class pairs.
78    pub disjoint_pairs: Vec<(String, String)>,
79    /// `owl:equivalentClass` class pairs.
80    pub equivalent_pairs: Vec<(String, String)>,
81}
82
83impl SchemaMeta {
84    /// True when the section would carry nothing.
85    pub fn is_empty(&self) -> bool {
86        self.predicate_stats.is_empty()
87            && self.char_sets.is_empty()
88            && self.class_hierarchy.is_empty()
89            && self.level_rollups.is_empty()
90            && self.level_links.is_empty()
91            && self.subclass_cycles.is_empty()
92            && self.disjoint_pairs.is_empty()
93            && self.equivalent_pairs.is_empty()
94    }
95
96    /// The schema fields of a pyramid-meta (files built before kind 9).
97    pub fn from_pyramid(p: &PyramidMeta) -> Self {
98        SchemaMeta {
99            type_predicate: None,
100            predicate_stats: p.predicate_stats.clone(),
101            char_sets: p.char_sets.clone(),
102            class_hierarchy: p.class_hierarchy.clone(),
103            level_rollups: p.level_rollups.clone(),
104            level_links: p.level_links.clone(),
105            subclass_cycles: p.subclass_cycles.clone(),
106            disjoint_pairs: p.disjoint_pairs.clone(),
107            equivalent_pairs: p.equivalent_pairs.clone(),
108        }
109    }
110
111    /// Encode the whole section, digest first. Empty for an empty schema.
112    pub fn encode(&self) -> Vec<u8> {
113        if self.is_empty() {
114            return Vec::new();
115        }
116        let pm = PyramidMeta::new(0, Vec::new(), &[])
117            .with_schema(
118                self.class_hierarchy.clone(),
119                self.level_rollups.clone(),
120                self.level_links.clone(),
121                Vec::new(),
122                self.subclass_cycles.clone(),
123                self.disjoint_pairs.clone(),
124                self.equivalent_pairs.clone(),
125            )
126            .with_predicate_stats(self.predicate_stats.clone())
127            .with_char_sets(self.char_sets.clone());
128        let mut body = vec![VERSION];
129        let tp = self.type_predicate.as_deref().unwrap_or("");
130        write_uvarint(&mut body, tp.len() as u64);
131        body.extend_from_slice(tp.as_bytes());
132        body.extend_from_slice(&pm.encode());
133        let mut out = Vec::with_capacity(DIGEST_LEN + body.len());
134        out.extend_from_slice(&blake3::hash(&body).as_bytes()[..DIGEST_LEN]);
135        out.extend_from_slice(&body);
136        out
137    }
138
139    /// Decode a section, checking its digest and version.
140    pub fn decode(section: &[u8]) -> Result<Self, crate::file::FileError> {
141        use crate::file::FileError;
142        if !crate::label_index::digest_ok(section) {
143            return Err(FileError::Container("schema section: digest mismatch"));
144        }
145        let body = &section[DIGEST_LEN..];
146        if body.first() != Some(&VERSION) {
147            return Err(FileError::Container("schema section: unknown version"));
148        }
149        let (len, n) =
150            read_uvarint(&body[1..]).ok_or(FileError::Container("schema section: truncated"))?;
151        let start = 1 + n;
152        let end = start
153            .checked_add(len as usize)
154            .filter(|&e| e <= body.len())
155            .ok_or(FileError::Container("schema section: truncated"))?;
156        let tp = std::str::from_utf8(&body[start..end])
157            .map_err(|_| FileError::Container("schema section: bad utf8"))?;
158        let pm = PyramidMeta::decode(&body[end..])
159            .map_err(|_| FileError::Container("schema section: malformed blocks"))?;
160        Ok(SchemaMeta {
161            type_predicate: (!tp.is_empty()).then(|| tp.to_string()),
162            predicate_stats: pm.predicate_stats,
163            char_sets: pm.char_sets,
164            class_hierarchy: pm.class_hierarchy,
165            level_rollups: pm.level_rollups,
166            level_links: pm.level_links,
167            subclass_cycles: pm.subclass_cycles,
168            disjoint_pairs: pm.disjoint_pairs,
169            equivalent_pairs: pm.equivalent_pairs,
170        })
171    }
172}
173
174/// Which id space an id lives in, for resolving it to a term.
175#[derive(Debug, Clone, Copy, PartialEq, Eq)]
176pub(crate) enum Space {
177    Subject,
178    Object,
179    Predicate,
180}
181
182/// The ids a schema pass needs, resolved against one file's dictionary.
183#[derive(Debug, Clone, Default)]
184pub(crate) struct SchemaIds {
185    /// The type predicate's id and term.
186    pub type_pid: Option<u32>,
187    pub type_term: Option<String>,
188    pub subclass_pid: Option<u32>,
189    pub disjoint_pid: Option<u32>,
190    pub equivalent_pid: Option<u32>,
191    /// `S`, the shared-term count: object ids `1..=S` are also subjects.
192    pub n_shared: u32,
193    /// Shared ids `a+1..=b` are literals (normally none). In a byte-ordered
194    /// dictionary literals (`"…`) sort before IRIs (`<`) and blank nodes (`_`),
195    /// so `a` is 0; in the SPARQL order they follow the blank nodes and IRIs.
196    pub shared_literals: (u32, u32),
197    /// Object ids `S+a+1..=S+b` are literals.
198    pub objonly_literals: (u32, u32),
199}
200
201impl SchemaIds {
202    fn is_literal(&self, o: u32) -> bool {
203        (o > self.shared_literals.0 && o <= self.shared_literals.1)
204            || (o > self.n_shared && {
205                let l = o - self.n_shared;
206                l > self.objonly_literals.0 && l <= self.objonly_literals.1
207            })
208    }
209
210    /// The type predicate term a build uses: the override, else `rdf:type`.
211    pub(crate) fn type_term_for(type_override: Option<&str>) -> String {
212        type_override.unwrap_or(crate::RDF_TYPE).to_string()
213    }
214
215    /// Resolve against an in-memory dictionary.
216    pub(crate) fn from_dictionary(dict: &crate::Dictionary, type_override: Option<&str>) -> Self {
217        let type_term = Self::type_term_for(type_override);
218        let type_pid = dict.predicate_id(&type_term);
219        let n_shared = dict.shared_count();
220        let is_lit = |t: Option<String>| t.is_some_and(|t| t.starts_with('"'));
221        // Literals are a prefix of each sorted section: binary-search its end.
222        let prefix_len = |n: u32, term: &dyn Fn(u32) -> Option<String>| -> u32 {
223            let (mut lo, mut hi) = (0u32, n);
224            while lo < hi {
225                let mid = lo + (hi - lo) / 2;
226                if is_lit(term(mid + 1)) {
227                    lo = mid + 1;
228                } else {
229                    hi = mid;
230                }
231            }
232            lo
233        };
234        let (shared_literals, objonly_literals) = match dict
235            .literal_objects()
236            .filter(|_| dict.order() == crate::term_order::TermOrder::Sparql)
237        {
238            Some(l) => (l.shared, l.only),
239            None => (
240                (0, prefix_len(n_shared, &|i| dict.object_term(i))),
241                (
242                    0,
243                    prefix_len(dict.object_only_count(), &|i| {
244                        dict.object_term(n_shared + i)
245                    }),
246                ),
247            ),
248        };
249        SchemaIds {
250            type_pid,
251            type_term: type_pid.map(|_| type_term),
252            subclass_pid: dict.predicate_id(RDFS_SUBCLASS_OF),
253            disjoint_pid: dict.predicate_id(OWL_DISJOINT_WITH),
254            equivalent_pid: dict.predicate_id(OWL_EQUIVALENT_CLASS),
255            n_shared,
256            shared_literals,
257            objonly_literals,
258        }
259    }
260}
261
262/// A link whose object class is not known yet: `(object id, class(s), p)`.
263pub(crate) type DeferredLink = (u32, u32, u32);
264
265/// Accumulates every schema statistic from two sorted, deduplicated passes over
266/// the default graph — SPO order, then POS order. Both builders feed it the
267/// same statements in the same order, which is what makes their sections
268/// byte-identical.
269pub(crate) struct SchemaAccumulator {
270    ids: SchemaIds,
271    /// predicate → [count, distinct subjects, distinct objects,
272    /// max objects per subject, max subjects per object]
273    pstats: HashMap<u32, [u64; 5]>,
274    cur_s: Option<u32>,
275    cur_p: Option<u32>,
276    run_sp: u64,
277    shape: Vec<u32>,
278    shapes: HashMap<Vec<u32>, u64>,
279    shapes_frozen: bool,
280    cur_po: Option<(u32, u32)>,
281    run_po: u64,
282    instance: HashMap<u32, u64>,
283    subclass: Vec<(u32, u32)>,
284    disjoint: Vec<(u32, u32)>,
285    equivalent: Vec<(u32, u32)>,
286    links: HashMap<(u32, u32, u32), u64>,
287}
288
289impl SchemaAccumulator {
290    pub(crate) fn new(ids: SchemaIds) -> Self {
291        SchemaAccumulator {
292            ids,
293            pstats: HashMap::new(),
294            cur_s: None,
295            cur_p: None,
296            run_sp: 0,
297            shape: Vec::new(),
298            shapes: HashMap::new(),
299            shapes_frozen: false,
300            cur_po: None,
301            run_po: 0,
302            instance: HashMap::new(),
303            subclass: Vec::new(),
304            disjoint: Vec::new(),
305            equivalent: Vec::new(),
306            links: HashMap::new(),
307        }
308    }
309
310    /// Used by the memory-bounded build (native only).
311    #[cfg(not(target_arch = "wasm32"))]
312    pub(crate) fn ids(&self) -> &SchemaIds {
313        &self.ids
314    }
315
316    fn end_sp(&mut self) {
317        if let Some(p) = self.cur_p.take() {
318            let e = self.pstats.entry(p).or_default();
319            e[3] = e[3].max(self.run_sp);
320        }
321        self.run_sp = 0;
322    }
323
324    fn end_subject(&mut self) {
325        self.end_sp();
326        if self.cur_s.take().is_none() {
327            return;
328        }
329        let shape = std::mem::take(&mut self.shape);
330        if let Some(c) = self.shapes.get_mut(&shape) {
331            *c += 1;
332        } else if !self.shapes_frozen {
333            self.shapes.insert(shape, 1);
334            if self.shapes.len() > MAX_TRACKED_SHAPES {
335                // Deterministic bound: drop the shapes seen once so far; if
336                // that does not halve the map, stop admitting new shapes.
337                self.shapes.retain(|_, c| *c > 1);
338                if self.shapes.len() > MAX_TRACKED_SHAPES / 2 {
339                    self.shapes_frozen = true;
340                }
341            }
342        }
343    }
344
345    /// One statement in SPO order, with its subject's representative class.
346    /// Returns a [`DeferredLink`] when the object's class has to be looked up
347    /// by the caller (the object is a shared term); the caller resolves it
348    /// and calls [`add_link`](Self::add_link).
349    pub(crate) fn observe_spo(
350        &mut self,
351        s: u32,
352        p: u32,
353        o: u32,
354        class_s: Option<u32>,
355    ) -> Option<DeferredLink> {
356        if self.cur_s != Some(s) {
357            self.end_subject();
358            self.cur_s = Some(s);
359        }
360        if self.cur_p != Some(p) {
361            self.end_sp();
362            self.cur_p = Some(p);
363            self.shape.push(p);
364            self.pstats.entry(p).or_default()[1] += 1;
365        }
366        self.run_sp += 1;
367        self.pstats.entry(p).or_default()[0] += 1;
368
369        let ids = &self.ids;
370        if Some(p) == ids.type_pid {
371            *self.instance.entry(o).or_default() += 1;
372            return None;
373        }
374        if Some(p) == ids.subclass_pid {
375            self.subclass.push((s, o));
376            return None;
377        }
378        if Some(p) == ids.disjoint_pid {
379            self.disjoint.push((s, o));
380        }
381        if Some(p) == ids.equivalent_pid {
382            self.equivalent.push((s, o));
383        }
384        ids.type_pid?;
385        let cs = class_s.unwrap_or(UNTYPED);
386        if ids.is_literal(o) {
387            self.add_link(cs, p, LITERAL);
388            None
389        } else if o > ids.n_shared {
390            // An object-only term is never a subject, so it has no class.
391            self.add_link(cs, p, UNTYPED);
392            None
393        } else {
394            Some((o, cs, p))
395        }
396    }
397
398    /// Count one lateral link.
399    pub(crate) fn add_link(&mut self, class_s: u32, p: u32, class_o: u32) {
400        *self.links.entry((class_s, p, class_o)).or_default() += 1;
401    }
402
403    /// End of the SPO pass.
404    pub(crate) fn finish_spo(&mut self) {
405        self.end_subject();
406    }
407
408    fn end_po(&mut self) {
409        if let Some((p, _)) = self.cur_po.take() {
410            let e = self.pstats.entry(p).or_default();
411            e[4] = e[4].max(self.run_po);
412        }
413        self.run_po = 0;
414    }
415
416    /// One statement in POS order.
417    pub(crate) fn observe_pos(&mut self, p: u32, o: u32) {
418        if self.cur_po != Some((p, o)) {
419            self.end_po();
420            self.cur_po = Some((p, o));
421            self.pstats.entry(p).or_default()[2] += 1;
422        }
423        self.run_po += 1;
424    }
425
426    /// End of the POS pass.
427    pub(crate) fn finish_pos(&mut self) {
428        self.end_po();
429    }
430
431    /// Resolve ids to terms and fold everything into the section.
432    pub(crate) fn finalize(self, resolve: &dyn Fn(Space, u32) -> Option<String>) -> SchemaMeta {
433        let mut predicate_stats: Vec<PredStat> = self
434            .pstats
435            .iter()
436            .map(|(&predicate, e)| PredStat {
437                predicate,
438                count: e[0],
439                distinct_subjects: e[1],
440                distinct_objects: e[2],
441                max_objects_per_subject: e[3].min(u32::MAX as u64) as u32,
442                max_subjects_per_object: e[4].min(u32::MAX as u64) as u32,
443            })
444            .collect();
445        predicate_stats.sort_by_key(|p| p.predicate);
446
447        let mut char_sets: Vec<CharSet> = self
448            .shapes
449            .into_iter()
450            .map(|(predicates, subjects)| CharSet {
451                predicates,
452                subjects,
453            })
454            .collect();
455        char_sets.sort_by(|a, b| {
456            b.subjects
457                .cmp(&a.subjects)
458                .then_with(|| a.predicates.cmp(&b.predicates))
459        });
460        char_sets.truncate(MAX_CHAR_SETS);
461
462        let mut out = SchemaMeta {
463            type_predicate: None,
464            predicate_stats,
465            char_sets,
466            ..SchemaMeta::default()
467        };
468        if self.instance.is_empty() {
469            return out;
470        }
471        out.type_predicate = self.ids.type_term.clone();
472        let class = |c: u32| -> Option<String> {
473            match c {
474                UNTYPED => Some("(untyped)".to_string()),
475                LITERAL => Some("(literal)".to_string()),
476                _ => resolve(Space::Object, c),
477            }
478        };
479        let mut instance_counts: BTreeMap<String, u64> = BTreeMap::new();
480        for (&c, &n) in &self.instance {
481            if let Some(t) = resolve(Space::Object, c) {
482                *instance_counts.entry(t).or_default() += n;
483            }
484        }
485        let mut parents: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
486        let mut self_loops: BTreeSet<String> = BTreeSet::new();
487        for &(s, o) in &self.subclass {
488            if let (Some(child), Some(parent)) =
489                (resolve(Space::Subject, s), resolve(Space::Object, o))
490            {
491                if child != parent {
492                    parents.entry(child).or_default().insert(parent);
493                } else {
494                    self_loops.insert(child);
495                }
496            }
497        }
498        let pairs = |v: &[(u32, u32)]| -> Vec<(String, String)> {
499            let mut set: BTreeSet<(String, String)> = BTreeSet::new();
500            for &(s, o) in v {
501                if let (Some(a), Some(b)) = (resolve(Space::Subject, s), resolve(Space::Object, o))
502                {
503                    if a != b {
504                        set.insert(if a < b { (a, b) } else { (b, a) });
505                    }
506                }
507            }
508            set.into_iter().collect()
509        };
510        let disjoint_pairs = pairs(&self.disjoint);
511        let equivalent_pairs = pairs(&self.equivalent);
512        let mut leaf_links: BTreeMap<(String, String, String), u64> = BTreeMap::new();
513        for (&(cs, p, co), &n) in &self.links {
514            if let (Some(a), Some(pr), Some(b)) =
515                (class(cs), resolve(Space::Predicate, p), class(co))
516            {
517                *leaf_links.entry((a, pr, b)).or_default() += n;
518            }
519        }
520        let core = crate::schema_pyramid::assemble_schema(
521            &instance_counts,
522            &parents,
523            &self_loops,
524            &leaf_links,
525            &|_, _| 0,
526        );
527        out.class_hierarchy = core.class_hierarchy;
528        out.level_rollups = core.level_rollups;
529        out.level_links = core.level_links;
530        out.subclass_cycles = core.subclass_cycles;
531        out.disjoint_pairs = disjoint_pairs;
532        out.equivalent_pairs = equivalent_pairs;
533        out
534    }
535}
536
537/// Walks a `(subject, class)` list sorted by subject, answering "the class of
538/// subject `s`" for non-decreasing `s`.
539pub(crate) struct ClassCursor<I: Iterator<Item = (u32, u32)>> {
540    it: I,
541    cur: Option<(u32, u32)>,
542}
543
544impl<I: Iterator<Item = (u32, u32)>> ClassCursor<I> {
545    pub(crate) fn new(mut it: I) -> Self {
546        let cur = it.next();
547        ClassCursor { it, cur }
548    }
549
550    /// The class of `s`; calls must not go backwards in `s`.
551    pub(crate) fn get(&mut self, s: u32) -> Option<u32> {
552        while let Some((cs, _)) = self.cur {
553            if cs >= s {
554                break;
555            }
556            self.cur = self.it.next();
557        }
558        match self.cur {
559            Some((cs, c)) if cs == s => Some(c),
560            _ => None,
561        }
562    }
563}
564
565/// Compute the SCHEMA section of an in-memory graph. `triples` must hold the
566/// **deduplicated** default graph **sorted in SPO order**; it is left sorted
567/// in POS order (every index build re-sorts anyway).
568pub(crate) fn compute_in_memory(
569    dict: &crate::Dictionary,
570    triples: &mut [(u32, u32, u32)],
571    type_override: Option<&str>,
572) -> SchemaMeta {
573    let ids = SchemaIds::from_dictionary(dict, type_override);
574    // Representative class per subject: the smallest class id, which in SPO
575    // order is the first type statement of each subject.
576    let mut reps: Vec<(u32, u32)> = Vec::new();
577    if let Some(tp) = ids.type_pid {
578        for &(s, p, o) in triples.iter() {
579            if p == tp && reps.last().map(|r| r.0) != Some(s) {
580                reps.push((s, o));
581            }
582        }
583    }
584    let mut acc = SchemaAccumulator::new(ids);
585    let mut cursor = ClassCursor::new(reps.iter().copied());
586    for &(s, p, o) in triples.iter() {
587        let cs = cursor.get(s);
588        if let Some((obj, cls_s, pred)) = acc.observe_spo(s, p, o, cs) {
589            let co = reps
590                .binary_search_by_key(&obj, |r| r.0)
591                .map(|i| reps[i].1)
592                .unwrap_or(UNTYPED);
593            acc.add_link(cls_s, pred, co);
594        }
595    }
596    acc.finish_spo();
597    sort_pos(triples);
598    for &(_s, p, o) in triples.iter() {
599        acc.observe_pos(p, o);
600    }
601    acc.finish_pos();
602    acc.finalize(&|space, id| match space {
603        Space::Subject => dict.subject_term(id),
604        Space::Object => dict.object_term(id),
605        Space::Predicate => dict.predicate_term(id),
606    })
607}
608
609#[cfg(feature = "parallel")]
610fn sort_pos(v: &mut [(u32, u32, u32)]) {
611    use rayon::slice::ParallelSliceMut;
612    v.par_sort_unstable_by_key(|&(s, p, o)| (p, o, s));
613}
614#[cfg(not(feature = "parallel"))]
615fn sort_pos(v: &mut [(u32, u32, u32)]) {
616    v.sort_unstable_by_key(|&(s, p, o)| (p, o, s));
617}
618
619/// Sort and deduplicate id-triples in SPO order, in place.
620pub(crate) fn sort_dedup_spo(v: &mut Vec<(u32, u32, u32)>) {
621    #[cfg(feature = "parallel")]
622    {
623        use rayon::slice::ParallelSliceMut;
624        v.par_sort_unstable();
625    }
626    #[cfg(not(feature = "parallel"))]
627    v.sort_unstable();
628    v.dedup();
629}
630
631#[cfg(test)]
632mod tests {
633    use super::*;
634    use crate::DictionaryBuilder;
635
636    fn build(triples: &[(&str, &str, &str)]) -> (crate::Dictionary, Vec<(u32, u32, u32)>) {
637        let mut db = DictionaryBuilder::new();
638        for (s, p, o) in triples {
639            db.observe(s, p, o);
640        }
641        let dict = db.build();
642        let mut ids: Vec<_> = triples
643            .iter()
644            .map(|(s, p, o)| dict.encode(s, p, o).unwrap())
645            .collect();
646        sort_dedup_spo(&mut ids);
647        (dict, ids)
648    }
649
650    const T: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
651
652    #[test]
653    fn computes_stats_shapes_and_schema_without_a_dendrogram() {
654        let (dict, mut ids) = build(&[
655            ("<a>", T, "<Person>"),
656            ("<a>", "<knows>", "<b>"),
657            ("<a>", "<name>", "\"A\""),
658            ("<b>", T, "<Person>"),
659            ("<b>", "<name>", "\"B\""),
660            ("<b>", "<name>", "\"B2\""),
661            ("<c>", T, "<Org>"),
662            ("<a>", "<worksFor>", "<c>"),
663            ("<Person>", RDFS_SUBCLASS_OF, "<Agent>"),
664            ("<Org>", RDFS_SUBCLASS_OF, "<Agent>"),
665            ("<a>", "<knows>", "<b>"), // duplicate: must not count twice
666        ]);
667        let m = compute_in_memory(&dict, &mut ids, None);
668        let name = dict.predicate_id("<name>").unwrap();
669        let st = m
670            .predicate_stats
671            .iter()
672            .find(|s| s.predicate == name)
673            .unwrap();
674        assert_eq!(
675            (st.count, st.distinct_subjects, st.distinct_objects),
676            (3, 2, 3)
677        );
678        assert_eq!(st.max_objects_per_subject, 2);
679        let knows = dict.predicate_id("<knows>").unwrap();
680        assert_eq!(
681            m.predicate_stats
682                .iter()
683                .find(|s| s.predicate == knows)
684                .unwrap()
685                .count,
686            1,
687            "deduplicated"
688        );
689        assert!(!m.char_sets.is_empty());
690        assert_eq!(m.type_predicate.as_deref(), Some(T));
691        assert!(m.class_hierarchy.iter().any(|n| n.class == "<Person>"
692            && n.parents == vec!["<Agent>".to_string()]
693            && n.depth == 1));
694        // the abstract level rolls Person + Org up to Agent
695        let top = &m.level_rollups[0];
696        assert_eq!(top.round, 0);
697        assert_eq!(top.classes, vec![("<Agent>".to_string(), 3)]);
698        // the leaf links: Person -knows-> Person, Person -worksFor-> Org, Person -name-> literal
699        let leaf = m.level_links.last().unwrap();
700        let has = |s: &str, p: &str, o: &str, n: u64| {
701            leaf.links
702                .iter()
703                .any(|l| l.s_class == s && l.predicate == p && l.o_class == o && l.count == n)
704        };
705        assert!(has("<Person>", "<knows>", "<Person>", 1));
706        assert!(has("<Person>", "<worksFor>", "<Org>", 1));
707        assert!(has("<Person>", "<name>", "(literal)", 3));
708        // round trip through the section bytes
709        let bytes = m.encode();
710        assert_eq!(SchemaMeta::decode(&bytes).unwrap(), m);
711        let mut bad = bytes.clone();
712        bad[20] ^= 0xff;
713        assert!(SchemaMeta::decode(&bad).is_err(), "digest catches a flip");
714    }
715
716    #[test]
717    fn untyped_graph_still_gets_stats() {
718        let (dict, mut ids) = build(&[("<a>", "<p>", "<b>"), ("<b>", "<p>", "\"x\"")]);
719        let m = compute_in_memory(&dict, &mut ids, None);
720        assert_eq!(m.predicate_stats.len(), 1);
721        assert!(m.class_hierarchy.is_empty() && m.level_rollups.is_empty());
722        assert_eq!(m.type_predicate, None);
723        assert!(!m.encode().is_empty());
724    }
725
726    #[test]
727    fn literal_ranges_are_found_by_binary_search() {
728        let (dict, _) = build(&[
729            ("<a>", "<p>", "\"1\""),
730            ("<a>", "<p>", "\"2\""),
731            ("<a>", "<p>", "<x>"),
732            ("<a>", "<p>", "_:b"),
733            ("<x>", "<p>", "<a>"),
734        ]);
735        let ids = SchemaIds::from_dictionary(&dict, None);
736        let lits: Vec<u32> = (1..=dict.shared_count() + dict.object_only_count())
737            .filter(|&o| ids.is_literal(o))
738            .collect();
739        let expect: Vec<u32> = (1..=dict.shared_count() + dict.object_only_count())
740            .filter(|&o| dict.object_term(o).unwrap().starts_with('"'))
741            .collect();
742        assert_eq!(lits, expect);
743        assert_eq!(lits.len(), 2);
744    }
745}