1use std::collections::{BTreeMap, BTreeSet, HashMap};
33
34use crate::meta::{CharSet, ClassNode, LevelLinks, LevelRollup, PredStat, PyramidMeta};
35use crate::varint::{read_uvarint, write_uvarint};
36
37const VERSION: u8 = 1;
39const DIGEST_LEN: usize = 16;
41const MAX_CHAR_SETS: usize = 128;
43const MAX_TRACKED_SHAPES: usize = 1 << 20;
45
46pub(crate) const RDFS_SUBCLASS_OF: &str = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
48pub(crate) const OWL_DISJOINT_WITH: &str = "<http://www.w3.org/2002/07/owl#disjointWith>";
50pub(crate) const OWL_EQUIVALENT_CLASS: &str = "<http://www.w3.org/2002/07/owl#equivalentClass>";
52
53pub(crate) const UNTYPED: u32 = u32::MAX;
55pub(crate) const LITERAL: u32 = u32::MAX - 1;
57
58#[derive(Debug, Clone, Default, PartialEq)]
61pub struct SchemaMeta {
62 pub type_predicate: Option<String>,
65 pub predicate_stats: Vec<PredStat>,
67 pub char_sets: Vec<CharSet>,
69 pub class_hierarchy: Vec<ClassNode>,
71 pub level_rollups: Vec<LevelRollup>,
73 pub level_links: Vec<LevelLinks>,
75 pub subclass_cycles: Vec<Vec<String>>,
77 pub disjoint_pairs: Vec<(String, String)>,
79 pub equivalent_pairs: Vec<(String, String)>,
81}
82
83impl SchemaMeta {
84 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 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 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 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 = §ion[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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
176pub(crate) enum Space {
177 Subject,
178 Object,
179 Predicate,
180}
181
182#[derive(Debug, Clone, Default)]
184pub(crate) struct SchemaIds {
185 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 pub n_shared: u32,
193 pub shared_literals: (u32, u32),
197 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 pub(crate) fn type_term_for(type_override: Option<&str>) -> String {
212 type_override.unwrap_or(crate::RDF_TYPE).to_string()
213 }
214
215 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 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
262pub(crate) type DeferredLink = (u32, u32, u32);
264
265pub(crate) struct SchemaAccumulator {
270 ids: SchemaIds,
271 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 #[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 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 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 self.add_link(cs, p, UNTYPED);
392 None
393 } else {
394 Some((o, cs, p))
395 }
396 }
397
398 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 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 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 pub(crate) fn finish_pos(&mut self) {
428 self.end_po();
429 }
430
431 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
537pub(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 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
565pub(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 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
619pub(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>"), ]);
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 let top = &m.level_rollups[0];
696 assert_eq!(top.round, 0);
697 assert_eq!(top.classes, vec![("<Agent>".to_string(), 3)]);
698 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 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}