rete_core/dictionary.rs
1//! Dictionary assembly: classify RDF terms by role and assign the HDT-style
2//! global IDs that triple blocks reference (SPEC.md §5, §5.1).
3//!
4//! Four sections are built from the §5.1 front-coded primitive:
5//! `shared` (used as both subject and object), `subjects` (subject-only),
6//! `objects` (object-only), and `predicates`. Subject IDs run `1..=S` (shared)
7//! then `S+1..` (subject-only); object IDs reuse `1..=S` for the same shared
8//! terms then `S+1..` for object-only. Predicates have their own space.
9
10use std::collections::{HashMap, HashSet};
11
12use crate::chunk_cache::ChunkCache;
13use crate::dict::{ChunkedSection, DictSectionBuilder, Lookup, MultiChunkBulkLoader};
14use crate::term_order::TermOrder;
15use crate::terms::{NodeId, ObjectId, PredicateId, SubjectId};
16use std::sync::Arc;
17
18/// Sort a term slice ascending — in parallel when the `parallel` feature is on.
19/// The front-coded dictionary sections need ascending order; doing it once here
20/// (rather than per-insert in a `BTreeSet`) is the fast path for large graphs.
21#[cfg(feature = "parallel")]
22fn sort_terms(v: &mut [String], order: TermOrder) {
23 use rayon::slice::ParallelSliceMut;
24 v.par_sort_unstable_by(|a, b| order.cmp(a.as_bytes(), b.as_bytes()));
25}
26#[cfg(not(feature = "parallel"))]
27fn sort_terms(v: &mut [String], order: TermOrder) {
28 v.sort_unstable_by(|a, b| order.cmp(a.as_bytes(), b.as_bytes()));
29}
30
31/// Builds a [`Dictionary`] from observed `(subject, predicate, object)` terms.
32///
33/// Terms are deduped with `HashSet` during ingest (O(1) average insert, no tree
34/// rebalancing) and sorted **once** in [`Self::build`]. This replaces a trio of
35/// `BTreeSet<String>` whose per-insert `O(log n)` cost + a `String` allocation
36/// for *every* observed term (most of them duplicates) dominated the build on
37/// large graphs.
38#[derive(Default)]
39pub struct DictionaryBuilder {
40 subjects: HashSet<String>,
41 objects: HashSet<String>,
42 predicates: HashSet<String>,
43 /// Frequent-object promotion ([`Self::with_frequent_objects`]): how many of
44 /// the most frequent object-only terms move into the shared section.
45 promote: usize,
46 /// Object occurrence counts, kept **instead of** `objects` while promotion
47 /// is on (so a default build pays nothing for it).
48 object_counts: HashMap<String, u64>,
49 /// Count objects without promoting any ([`Self::with_object_counts`]).
50 count_objects: bool,
51 /// Entries in the three term sets — a term once per set it is in — and
52 /// their string bytes ([`Self::footprint`]).
53 entries: u64,
54 entry_bytes: u64,
55 /// How the sections sort their terms.
56 order: TermOrder,
57}
58
59impl DictionaryBuilder {
60 /// A builder with the process-wide writer settings
61 /// ([`crate::write_opts::frequent_objects`]), sorting terms in the SPARQL
62 /// order (the order of format `0x08`). `RETE_WRITE_FORMAT=5` makes the
63 /// legacy byte order the default, so that hook still writes a real `0x05`
64 /// image.
65 pub fn new() -> Self {
66 let order = crate::term_order::builder_order_override().unwrap_or_else(|| {
67 if crate::build_record::writes_legacy() {
68 TermOrder::Bytewise
69 } else {
70 TermOrder::Sparql
71 }
72 });
73 Self::default()
74 .with_order(order)
75 .with_frequent_objects(crate::write_opts::frequent_objects())
76 }
77
78 /// Sort the sections' terms in `order`. The `0x05` to `0x07` generations
79 /// need [`TermOrder::Bytewise`]: the tests that make an old-format input
80 /// use it.
81 pub fn with_order(mut self, order: TermOrder) -> Self {
82 self.order = order;
83 self
84 }
85
86 /// Promote the `n` most frequent **object-only** terms (by the number of
87 /// statements that carry them as object; ties by term order) into the
88 /// shared section (`0` = off, the default).
89 ///
90 /// The shared section is numbered first and in term order, so a promoted
91 /// vocabulary term (a class, a scheme individual, a status literal) gets a
92 /// small object id wherever it sorts ahead of the shared entities — the
93 /// effect declaring the vocabulary in a TBox has, without the TBox. A
94 /// promoted term keeps its object id role; the subject id it also gets is
95 /// simply never used by any statement. Readers need nothing new: the shared
96 /// section has always been looked up first for both roles.
97 ///
98 /// Set it before the first [`Self::observe`]: promotion counts objects as
99 /// they are observed.
100 pub fn with_frequent_objects(mut self, n: usize) -> Self {
101 debug_assert!(
102 self.objects.is_empty() && self.object_counts.is_empty(),
103 "with_frequent_objects after observe"
104 );
105 self.promote = n;
106 self
107 }
108
109 /// Count every object's occurrences, as promotion does, but promote
110 /// nothing: [`Self::build_counted`] hands the counts of the object-only
111 /// terms back instead. The memory-bounded build's chunks use it, because
112 /// a term's frequency is only known once every chunk's counts are summed
113 /// (`crate::extbuild`).
114 // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
115 #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
116 pub(crate) fn with_object_counts(mut self) -> Self {
117 debug_assert!(
118 self.objects.is_empty() && self.object_counts.is_empty(),
119 "with_object_counts after observe"
120 );
121 self.count_objects = true;
122 self
123 }
124
125 /// Whether objects are kept with their counts rather than as a set.
126 fn counting(&self) -> bool {
127 self.promote > 0 || self.count_objects
128 }
129
130 /// `(entries, bytes)`: the entries of the three term sets observed so far
131 /// — a term once for every set it is in (subject, object, predicate) — and
132 /// the bytes of their strings. What the memory-bounded build charges a
133 /// chunk's dictionary against its budget, since [`Self::build`] costs a
134 /// multiple of each entry.
135 // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
136 #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
137 pub(crate) fn footprint(&self) -> (u64, u64) {
138 (self.entries, self.entry_bytes)
139 }
140
141 fn note_entry(&mut self, term: &str) {
142 self.entries += 1;
143 self.entry_bytes += term.len() as u64;
144 }
145
146 /// Record one triple's terms (IDs are assigned later, in [`Self::build`]).
147 /// We probe with the borrowed `&str` first and only allocate a `String` for
148 /// a genuinely new term — so a graph of N triples does far fewer than 3N
149 /// allocations (each subject/predicate recurs across many triples).
150 pub fn observe(&mut self, subject: &str, predicate: &str, object: &str) {
151 if !self.subjects.contains(subject) {
152 self.subjects.insert(subject.to_string());
153 self.note_entry(subject);
154 }
155 if self.counting() {
156 if let Some(n) = self.object_counts.get_mut(object) {
157 *n += 1;
158 } else {
159 self.object_counts.insert(object.to_string(), 1);
160 self.note_entry(object);
161 }
162 } else if !self.objects.contains(object) {
163 self.objects.insert(object.to_string());
164 self.note_entry(object);
165 }
166 if !self.predicates.contains(predicate) {
167 self.predicates.insert(predicate.to_string());
168 self.note_entry(predicate);
169 }
170 }
171
172 /// Record a **graph name** as a term in the subject role — how the quad
173 /// index (SPEC.md §6.5) makes graph names dictionary ids. It lands in the
174 /// shared section when the name is also an object, else in the
175 /// subject-only section.
176 pub fn observe_graph(&mut self, graph: &str) {
177 if !self.subjects.contains(graph) {
178 self.subjects.insert(graph.to_string());
179 self.note_entry(graph);
180 }
181 }
182
183 pub fn build(self) -> Dictionary {
184 self.build_inner().0
185 }
186
187 /// [`Self::build`] for a builder made [`Self::with_object_counts`]: also
188 /// returns, for every object-only term in the order of the object-only
189 /// section (local ids `1..`), the number of statements that carry it.
190 /// Empty when objects were not counted.
191 // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
192 #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
193 pub(crate) fn build_counted(self) -> (Dictionary, Vec<u64>) {
194 self.build_inner()
195 }
196
197 fn build_inner(self) -> (Dictionary, Vec<u64>) {
198 // Sort each role's terms once (ascending) — identical output order to
199 // the old BTreeSet iteration, but without the per-insert tree cost.
200 let mut subjects: Vec<String> = self.subjects.into_iter().collect();
201 let mut predicates: Vec<String> = self.predicates.into_iter().collect();
202 let order = self.order;
203 sort_terms(&mut subjects, order);
204 sort_terms(&mut predicates, order);
205
206 // A term is "shared" when it appears as both a subject and an object.
207 let subject_set: HashSet<&str> = subjects.iter().map(String::as_str).collect();
208
209 // The object terms: a plain set, or (promotion on) the count map, used
210 // as-is rather than converted, so no second table over every object.
211 let count_objects = self.count_objects;
212 let object_set = if self.promote > 0 || count_objects {
213 ObjectTerms::Counted(self.object_counts)
214 } else {
215 ObjectTerms::Plain(self.objects)
216 };
217 // Frequent-object promotion: the top `promote` object-only terms by
218 // statement count (ties by term order) join the shared section.
219 let mut promoted: Vec<String> = Vec::new();
220 if let (true, ObjectTerms::Counted(counts)) = (self.promote > 0, &object_set) {
221 let mut top: Vec<(&String, u64)> = counts
222 .iter()
223 .filter(|(t, _)| !subject_set.contains(t.as_str()))
224 .map(|(t, &n)| (t, n))
225 .collect();
226 let k = self.promote.min(top.len());
227 if k > 0 && k < top.len() {
228 top.select_nth_unstable_by(k - 1, |a, b| {
229 b.1.cmp(&a.1).then_with(|| order.cmp_str(a.0, b.0))
230 });
231 }
232 top.truncate(k);
233 promoted = top.into_iter().map(|(t, _)| t.clone()).collect();
234 sort_terms(&mut promoted, order);
235 }
236 let promoted_set: HashSet<&str> = promoted.iter().map(String::as_str).collect();
237
238 let mut shared_b = DictSectionBuilder::new().with_order(order);
239 let mut subj_b = DictSectionBuilder::new().with_order(order);
240 let mut obj_b = DictSectionBuilder::new().with_order(order);
241 let mut pred_b = DictSectionBuilder::new().with_order(order);
242
243 // Subjects ascending: shared (also an object) vs subject-only. Promoted
244 // objects are merged into the shared run in term order.
245 let mut promoted_iter = promoted.iter().peekable();
246 for s in &subjects {
247 if object_set.contains(s) {
248 while let Some(p) =
249 promoted_iter.next_if(|p| order.cmp_str(p, s) == std::cmp::Ordering::Less)
250 {
251 shared_b.push(p.clone());
252 }
253 shared_b.push(s.clone());
254 } else {
255 subj_b.push(s.clone());
256 }
257 }
258 for p in promoted_iter {
259 shared_b.push(p.clone());
260 }
261 // Objects ascending: object-only (shared terms were emitted above),
262 // with their counts when the caller asked for them.
263 // RDF-star: a quoted triple only ever appears in subject/object position,
264 // so a single prefix scan of those term sets detects the whole file.
265 let mut has_quoted_triples = subjects.iter().any(|s| s.starts_with("<<"));
266 let mut object_only_counts: Vec<u64> = Vec::new();
267 let mut take_object = |o: &String, n: u64| {
268 has_quoted_triples |= o.starts_with("<<");
269 if !subject_set.contains(o.as_str()) && !promoted_set.contains(o.as_str()) {
270 obj_b.push(o.clone());
271 if count_objects {
272 object_only_counts.push(n);
273 }
274 }
275 };
276 match object_set {
277 ObjectTerms::Counted(counts) if count_objects => {
278 let mut objects: Vec<(String, u64)> = counts.into_iter().collect();
279 sort_counted_terms(&mut objects, order);
280 for (o, n) in &objects {
281 take_object(o, *n);
282 }
283 }
284 object_set => {
285 let mut objects: Vec<String> = object_set.into_terms();
286 sort_terms(&mut objects, order);
287 for o in &objects {
288 take_object(o, 0);
289 }
290 }
291 }
292 for p in &predicates {
293 pred_b.push(p.clone());
294 }
295
296 let shared = shared_b.build();
297 let mut dict = Dictionary::from_sections_ordered(
298 [shared, subj_b.build(), obj_b.build(), pred_b.build()],
299 order,
300 );
301 dict.has_quoted_triples = has_quoted_triples;
302 (dict, object_only_counts)
303 }
304}
305
306/// Sort `(term, count)` pairs by term — the terms are distinct, so the
307/// count never decides. In parallel when the `parallel` feature is on.
308fn sort_counted_terms(v: &mut [(String, u64)], order: TermOrder) {
309 #[cfg(feature = "parallel")]
310 {
311 use rayon::slice::ParallelSliceMut;
312 v.par_sort_unstable_by(|a, b| order.cmp(a.0.as_bytes(), b.0.as_bytes()));
313 }
314 #[cfg(not(feature = "parallel"))]
315 v.sort_unstable_by(|a, b| order.cmp(a.0.as_bytes(), b.0.as_bytes()));
316}
317
318/// The object terms a [`DictionaryBuilder`] observed: a set, or the
319/// occurrence counts frequent-object promotion needs.
320enum ObjectTerms {
321 Plain(HashSet<String>),
322 Counted(HashMap<String, u64>),
323}
324
325impl ObjectTerms {
326 fn contains(&self, term: &str) -> bool {
327 match self {
328 ObjectTerms::Plain(s) => s.contains(term),
329 ObjectTerms::Counted(m) => m.contains_key(term),
330 }
331 }
332
333 fn into_terms(self) -> Vec<String> {
334 match self {
335 ObjectTerms::Plain(s) => s.into_iter().collect(),
336 ObjectTerms::Counted(m) => m.into_keys().collect(),
337 }
338 }
339}
340
341/// Reusable per-window scratch for [`Dictionary::resolve_window`]: one job list
342/// per section (`(local_id, out_slot)` pairs) and the resolved-term output.
343/// Held across windows by the export loop so a window allocates only when a
344/// buffer must grow.
345#[derive(Default)]
346pub struct WindowResolver {
347 /// Jobs per dictionary section (shared, subject-only, object-only,
348 /// predicates): each `(section-local id, output slot)`.
349 jobs: [Vec<(u32, usize)>; 4],
350 /// Resolved terms, indexed by output slot `row * 3 + {0:s, 1:p, 2:o}`.
351 out: Vec<Option<String>>,
352}
353
354/// The most chunks one id-list prefetch ([`Dictionary::prefetch_subject_terms`],
355/// [`Dictionary::prefetch_node_terms`]) faults in a single batch. A batch holds
356/// every body it fetched until all are cached, so this bounds that transient
357/// (512 chunks of ≤64 KiB: ≤32 MiB) however many ids a caller passes; a longer
358/// list goes out in several batches.
359const PREFETCH_BATCH_CHUNKS: usize = 512;
360
361/// The most chunks the predicate section may have for a query with a variable
362/// predicate to read all of it up front ([`Dictionary::prefetch_lookups_with`]).
363const WHOLE_PREDICATE_CHUNKS: usize = 4;
364
365/// The chunk of each section a caller last decoded a term from
366/// ([`Dictionary::node_term_held`]).
367#[derive(Default)]
368pub(crate) struct TermHold([crate::dict::ChunkHold; 4]);
369
370/// A read-only dictionary mapping terms ↔ role-specific IDs.
371///
372/// Holds the four sections as [`ChunkedSection`]s — local files keep each
373/// section as one resident chunk; a lazily-opened remote file faults
374/// individual chunks in on first touch. Lookups never re-parse a header.
375pub struct Dictionary {
376 /// shared, subjects, objects, predicates.
377 sections: [ChunkedSection; 4],
378 shared_len: u32,
379 /// Whether any term is an RDF-star quoted triple (`<< … >>`). Set at build
380 /// time (from the observed terms); `false` on the read path, where the
381 /// header's `FLAG_HAS_QUOTED_TRIPLES` is the source of truth instead.
382 has_quoted_triples: bool,
383 /// Faults the chunks of several sections in one batch (a ranged open);
384 /// `None` = section by section (local, or no batch reader).
385 multi_bulk: Option<MultiChunkBulkLoader>,
386 /// The literal object ids ([`Self::literal_objects`]), once found.
387 literal_objects: std::sync::OnceLock<LiteralObjects>,
388 /// Rebuilds the terms of the subject-only chunks the file stores no body
389 /// for (a derived IRI family, [`crate::derived`]); `None` when it has none.
390 derived: Option<crate::derived::DerivedTerms>,
391}
392
393/// Which object ids are literals. The literals of a section are one run of
394/// consecutive ids in either term order: up to `0x07` literal tokens (`"…`)
395/// sort before quoted triples (`<<…`), IRIs (`<…`) and blank nodes (`_:…`), so
396/// the run is the section's start; in the `0x08` order it follows the blank
397/// nodes and IRIs and the group counts of the root say where it is. The shared
398/// section's are normally none (a literal is never a subject).
399#[derive(Debug, Clone, Copy, PartialEq, Eq)]
400pub struct LiteralObjects {
401 /// Shared object ids `shared.0+1..=shared.1` are literals.
402 pub shared: (u32, u32),
403 /// `S`, the shared-term count: object ids above it are object-only.
404 pub n_shared: u32,
405 /// Object-only object ids `S+only.0+1..=S+only.1` are literals.
406 pub only: (u32, u32),
407}
408
409impl LiteralObjects {
410 /// Is every object id in `lo..=hi` a literal?
411 pub fn covers(&self, lo: u32, hi: u32) -> bool {
412 let within = |(a, b): (u64, u64)| lo as u64 > a && hi as u64 <= b;
413 lo <= hi
414 && (within((self.shared.0 as u64, self.shared.1 as u64))
415 || within((
416 self.n_shared as u64 + self.only.0 as u64,
417 self.n_shared as u64 + self.only.1 as u64,
418 )))
419 }
420
421 /// Is object id `o` a literal?
422 pub fn contains(&self, o: u32) -> bool {
423 self.covers(o, o)
424 }
425}
426
427impl Dictionary {
428 /// Rebuild from four serialized sections (shared, subjects, objects,
429 /// predicates), e.g. when reading a `.rete` file. The four sections share one
430 /// [`ChunkCache`] (unlimited cap here, so every section body stays resident
431 /// exactly as before).
432 pub fn from_sections(sections: [Vec<u8>; 4]) -> Self {
433 Self::from_sections_ordered(sections, TermOrder::Bytewise)
434 }
435
436 /// [`Self::from_sections`] for sections whose terms are sorted in `order`.
437 pub fn from_sections_ordered(sections: [Vec<u8>; 4], order: TermOrder) -> Self {
438 let cache = ChunkCache::unlimited_arc();
439 let mut section_index = 0u8;
440 let chunked = sections.map(|bytes| {
441 let s = ChunkedSection::local(bytes, cache.clone(), section_index).with_order(order);
442 section_index += 1;
443 s
444 });
445 Self::from_chunked_sections(chunked)
446 }
447
448 /// How the terms of the four sections are ordered.
449 pub fn order(&self) -> TermOrder {
450 self.sections[0].order()
451 }
452
453 /// Rebuild from four already-chunked sections (the remote lazy-open path).
454 pub fn from_chunked_sections(sections: [ChunkedSection; 4]) -> Self {
455 let shared_len = sections[0].term_count();
456 Dictionary {
457 sections,
458 shared_len,
459 has_quoted_triples: false,
460 multi_bulk: None,
461 literal_objects: std::sync::OnceLock::new(),
462 derived: None,
463 }
464 }
465
466 /// The object ids that are literals (see [`LiteralObjects`]): two binary
467 /// searches per section for where the `"` tokens start and end, each in the
468 /// one chunk the boundary routes to — two chunk faults at most on a lazy
469 /// open, done once. `None` when a chunk cannot be read, which a caller
470 /// treats as "not proven".
471 pub fn literal_objects(&self) -> Option<LiteralObjects> {
472 if let Some(found) = self.literal_objects.get() {
473 return Some(*found);
474 }
475 // The SPARQL order puts literals after blank nodes and IRIs, as one run
476 // (text, then typed): the section's group counts say where.
477 if self.order() == TermOrder::Sparql {
478 let run = |si: usize| -> Option<(u32, u32)> {
479 let g = self.sections[si].groups()?;
480 Some((g.lit_start(), g.lit_end()))
481 };
482 let found = LiteralObjects {
483 shared: run(0)?,
484 n_shared: self.shared_len,
485 only: run(2)?,
486 };
487 return Some(*self.literal_objects.get_or_init(|| found));
488 }
489 // `"` is 0x22 and `#` the next byte: a literal token sorts in
490 // [`"`, `#`), and nothing a well-formed file holds sorts before it.
491 // A failed read is not cached, so the next query tries again.
492 let run = |si: usize| -> Option<(u32, u32)> {
493 Some((self.sections[si].rank("\"")?, self.sections[si].rank("#")?))
494 };
495 let found = LiteralObjects {
496 shared: run(0)?,
497 n_shared: self.shared_len,
498 only: run(2)?,
499 };
500 Some(*self.literal_objects.get_or_init(|| found))
501 }
502
503 /// Say which derived IRI families the subject-only section has chunks for
504 /// ([`crate::derived`]). The section must already know its elided chunks.
505 pub(crate) fn with_derived(mut self, families: Vec<crate::derived::Family>) -> Self {
506 if !families.is_empty() {
507 self.derived = Some(crate::derived::DerivedTerms::new(families));
508 }
509 self
510 }
511
512 /// The derived IRI families of this dictionary, if any.
513 pub fn derived_families(&self) -> &[crate::derived::Family] {
514 self.derived.as_ref().map_or(&[], |d| d.families())
515 }
516
517 /// Hand a dictionary with derived families the index it reads their inputs
518 /// from. Until it has one, a derived term does not resolve.
519 pub fn wire_derived(&self, index: Arc<crate::index::GraphIndex>) {
520 if let Some(d) = &self.derived {
521 d.wire(index);
522 }
523 }
524
525 /// The subject-only chunk holding section-local id `local`.
526 pub(crate) fn subject_only_chunk(&self, local: u32) -> Option<usize> {
527 self.sections[1].chunk_of_id(local)
528 }
529
530 /// The term of subject-only id `local`: stored, or rebuilt when its chunk is
531 /// one the file derives.
532 fn subject_only_term(&self, local: u32) -> Option<String> {
533 if let Some(t) = self.sections[1].term(local) {
534 return Some(t);
535 }
536 match &self.derived {
537 Some(d) if self.sections[1].id_is_elided(local) => d.term(self, local),
538 _ => None,
539 }
540 }
541
542 /// After a section's `resolve_into`: fill the jobs of subject-only ids in
543 /// derived chunks, which it left empty.
544 fn fill_derived(&self, jobs: &[(u32, usize)], out: &mut [Option<String>]) {
545 let Some(d) = &self.derived else { return };
546 let todo: Vec<(u32, usize)> = jobs
547 .iter()
548 .copied()
549 .filter(|&(id, slot)| out[slot].is_none() && self.sections[1].id_is_elided(id))
550 .collect();
551 if !todo.is_empty() {
552 d.terms(self, &todo, out);
553 }
554 }
555
556 /// The subject-only ids among unified node ids (those that can be derived).
557 fn derived_locals(&self, nodes: &[NodeId]) -> Vec<u32> {
558 if self.derived.is_none() {
559 return Vec::new();
560 }
561 nodes
562 .iter()
563 .filter_map(|&n| match self.node_section_id(n) {
564 Some((1, local)) => Some(local),
565 _ => None,
566 })
567 .collect()
568 }
569
570 /// Warm what decoding these subject-only ids in derived chunks reads.
571 fn prefetch_derived(&self, locals: impl IntoIterator<Item = u32>) {
572 let Some(d) = &self.derived else { return };
573 let ids: Vec<u32> = locals
574 .into_iter()
575 .filter(|&l| self.sections[1].id_is_elided(l))
576 .collect();
577 if !ids.is_empty() {
578 d.prefetch(self, &ids);
579 }
580 }
581
582 /// Attach a cross-section chunk fetcher (see [`MultiChunkBulkLoader`]):
583 /// the term prefetchers then fault every section's missing chunks in one
584 /// batch instead of one batch per section.
585 pub(crate) fn with_multi_bulk_loader(mut self, loader: MultiChunkBulkLoader) -> Self {
586 self.multi_bulk = Some(loader);
587 self
588 }
589
590 /// Fault, in one batched read across all four sections, the directory
591 /// leaves `leaves[si]` of each section — the routing step that must precede
592 /// reading a chunk. Routing a term or an id to its chunk faults its leaf, so
593 /// routing them one at a time was one dependent read per leaf and section.
594 /// A no-op on sections whose directory is resident.
595 fn fault_leaves(&self, leaves: &[Vec<usize>; 4]) {
596 let across: Vec<(&dyn crate::index::LeafDir, &[usize])> = leaves
597 .iter()
598 .enumerate()
599 .filter(|(_, lis)| !lis.is_empty())
600 .filter_map(|(si, lis)| {
601 let d: &dyn crate::index::LeafDir = self.sections[si].leaf_dir()?;
602 Some((d, lis.as_slice()))
603 })
604 .collect();
605 crate::index::ensure_leaves_across(&across);
606 }
607
608 /// Fault the chunks `want[si]` of each section, at most `batch` chunks
609 /// per read. With a cross-section fetcher every missing chunk goes out in
610 /// one batch (round trips: one, not one per section); without one, each
611 /// section batches its own. A failed batch leaves the chunks for the
612 /// per-chunk loader, which retries them lookup by lookup. Purely a cache
613 /// warmer: results never depend on it.
614 fn prefetch_sections(&self, want: &[Vec<usize>; 4], batch: usize) {
615 let batch = batch.max(2);
616 if let Some(multi) = &self.multi_bulk {
617 let pairs: Vec<(u8, usize)> = want
618 .iter()
619 .enumerate()
620 .flat_map(|(si, cis)| {
621 self.sections[si]
622 .missing_chunks(cis)
623 .into_iter()
624 .map(move |ci| (si as u8, ci))
625 })
626 .collect();
627 // A single missing chunk costs the same either way: leave it to
628 // the per-chunk loader, as a section's own batch does.
629 if pairs.len() < 2 {
630 return;
631 }
632 for part in pairs.chunks(batch) {
633 if let Some(bodies) = multi(part) {
634 if bodies.len() == part.len() {
635 for (&(si, ci), body) in part.iter().zip(bodies) {
636 self.sections[si as usize].seed_chunk(ci, body);
637 }
638 }
639 }
640 }
641 return;
642 }
643 for (si, cis) in want.iter().enumerate() {
644 for part in cis.chunks(batch) {
645 self.sections[si].prefetch_chunks(part);
646 }
647 }
648 }
649
650 /// Total number of distinct terms across all four sections.
651 pub fn term_count(&self) -> u32 {
652 self.sections.iter().map(|s| s.term_count()).sum()
653 }
654
655 /// Set the byte cap of the shared chunk cache (bounded-export phase 2).
656 /// `u64::MAX` (the default from every open) means unlimited — no eviction,
657 /// residency identical to the pre-budget design. A finite cap evicts
658 /// least-recently-used chunk bodies down to it on every fault, so a full
659 /// dump's peak dictionary residency is bounded rather than the whole
660 /// decompressed dictionary. All four sections share one cache; setting it on
661 /// each is idempotent (they are the same `Arc`).
662 pub fn set_cache_cap(&self, cap: u64) {
663 for s in &self.sections {
664 s.cache().set_cap(cap);
665 }
666 }
667
668 /// Heap bytes the four sections' chunk directories hold for as long as
669 /// the dictionary is open (see [`ChunkedSection::directory_bytes`]).
670 ///
671 /// [`ChunkedSection::directory_bytes`]: crate::dict::ChunkedSection::directory_bytes
672 pub fn directory_bytes(&self) -> u64 {
673 self.sections.iter().map(|s| s.directory_bytes()).sum()
674 }
675
676 /// The current chunk-cache byte cap (`u64::MAX` = unlimited).
677 pub fn cache_cap(&self) -> u64 {
678 self.sections[0].cache().cap()
679 }
680
681 /// A snapshot of the shared chunk cache's observability counters — for
682 /// `RETE_OPEN_DEBUG` accounting and the eviction tests.
683 pub fn cache_stats(&self) -> crate::chunk_cache::CacheStats {
684 self.sections[0].cache().stats()
685 }
686
687 /// Does this dataset contain RDF-star quoted triples? Meaningful only for a
688 /// freshly built dictionary (a read-back one carries the truth in the file
689 /// header's `FLAG_HAS_QUOTED_TRIPLES`, not here).
690 pub fn has_quoted_triples(&self) -> bool {
691 self.has_quoted_triples
692 }
693
694 /// Record whether the dataset holds quoted triples (a read-back dictionary
695 /// takes it from the file header).
696 pub fn set_has_quoted_triples(&mut self, v: bool) {
697 self.has_quoted_triples = v;
698 }
699
700 /// Did any lazy chunk fetch fail since this dictionary was opened — or
701 /// since the last [`reset_load_failure`](Self::reset_load_failure)?
702 pub fn load_incomplete(&self) -> bool {
703 self.sections.iter().any(|s| s.load_incomplete())
704 }
705
706 /// Forget recorded fetch failures across every section (see
707 /// `GraphIndex::reset_load_failure` — the per-query reset for resident
708 /// sessions). Failed chunks were never cached, so they simply retry.
709 pub fn reset_load_failure(&self) {
710 self.sections.iter().for_each(|s| s.reset_load_failure());
711 }
712
713 /// Batch-fault every unloaded chunk of every section (no-op for local
714 /// dictionaries). Callers about to resolve *every* term — export, dump —
715 /// call this once so the sweep coalesces into a few range reads instead
716 /// of one fetch per chunk.
717 pub fn prefetch_all(&self) {
718 for s in &self.sections {
719 s.prefetch_all();
720 }
721 }
722
723 /// Batch-fault just the chunks needed to resolve a bounded result set:
724 /// `node_ids` are unified-node ids (the `Val::Id(id)` with `id >= 0`),
725 /// `predicate_ids` are predicate-space ids. Groups them by `(section,
726 /// chunk)` and coalesces each section's faults into a few range reads —
727 /// turning "one request per distinct output term" into "a handful per
728 /// query". No-op for a local dictionary (every chunk is already resident).
729 pub fn prefetch_terms(&self, node_ids: &[u32], predicate_ids: &[u32]) {
730 self.prefetch_terms_batched(node_ids, predicate_ids, usize::MAX);
731 }
732
733 /// [`prefetch_terms`](Self::prefetch_terms), faulting at most `batch` chunks
734 /// per bulk read. A bulk read holds every chunk it fetches — the coalesced
735 /// span, the per-chunk slices and the decoded bodies — until all of them
736 /// are cached, so an unbatched prefetch of a scattered window materialized
737 /// up to thousands of chunks at once, outside every cache cap. A bounded
738 /// export batches it so that transient stays a few MB.
739 pub fn prefetch_terms_batched(&self, node_ids: &[u32], predicate_ids: &[u32], batch: usize) {
740 self.prefetch_derived(self.derived_locals(node_ids));
741 let mut leaves: [Vec<usize>; 4] = Default::default();
742 for &n in node_ids {
743 if let Some((si, local)) = self.node_section_id(n) {
744 leaves[si].extend(self.sections[si].leaf_of_id(local));
745 }
746 }
747 for &p in predicate_ids {
748 leaves[3].extend(self.sections[3].leaf_of_id(p));
749 }
750 self.fault_leaves(&leaves);
751 let mut want: [std::collections::BTreeSet<usize>; 4] = Default::default();
752 for &n in node_ids {
753 if let Some((si, ci)) = self.node_chunk(n) {
754 want[si].insert(ci);
755 }
756 }
757 for &p in predicate_ids {
758 if let Some(ci) = self.sections[3].chunk_of_id(p) {
759 want[3].insert(ci);
760 }
761 }
762 let want: [Vec<usize>; 4] = want.map(|set| set.into_iter().collect());
763 self.prefetch_sections(&want, batch);
764 }
765
766 /// Does any section fault chunk bodies in on demand (a lazy or ranged
767 /// open)? `false` for a resident dictionary, where every prefetch is a no-op.
768 pub fn faults_chunks(&self) -> bool {
769 self.sections.iter().any(|s| s.faults_chunks())
770 }
771
772 /// Batch-fault every chunk that looking these terms up will read, so the
773 /// lookups that follow are cache hits: **one** batched read (one round trip
774 /// remotely) instead of one dependent fetch per term and section.
775 ///
776 /// `node_terms` are looked up as nodes ([`node_of_term`](Self::node_of_term),
777 /// [`subject_id`](Self::subject_id), [`object_id`](Self::object_id)), which
778 /// probe the shared section and then the subject-only or object-only one —
779 /// so all three routed chunks are fetched, plus those of the other spelling
780 /// of a string literal (`"x"` ↔ `"x"^^xsd:string`). `pred_terms` are looked
781 /// up in the predicate section. The routing is the lookup's own
782 /// ([`ChunkedSection::chunk_for_term`]), read off the resident chunk
783 /// directories. Purely a cache warmer: no-op on a resident dictionary, and
784 /// a failed batch leaves every chunk to the per-lookup loader.
785 ///
786 /// [`ChunkedSection::chunk_for_term`]: crate::dict::ChunkedSection::chunk_for_term
787 pub fn prefetch_lookups<'a>(
788 &self,
789 node_terms: impl IntoIterator<Item = &'a str>,
790 pred_terms: impl IntoIterator<Item = &'a str>,
791 ) {
792 self.prefetch_lookups_with(node_terms, pred_terms, false);
793 }
794
795 /// [`prefetch_lookups`](Self::prefetch_lookups), and with `all_predicates`
796 /// the whole predicate section too when it is small (at most
797 /// [`WHOLE_PREDICATE_CHUNKS`] chunks, a few hundred bytes to a few KiB on
798 /// real files). A pattern with a variable predicate decodes and
799 /// canonicalizes every predicate it matches: reading them with the
800 /// constants costs no round trip of its own, where reading them when the
801 /// first rows arrive was two (the leaf, then the chunk).
802 pub(crate) fn prefetch_lookups_with<'a>(
803 &self,
804 node_terms: impl IntoIterator<Item = &'a str>,
805 pred_terms: impl IntoIterator<Item = &'a str>,
806 all_predicates: bool,
807 ) {
808 self.prefetch_lookups_and_terms(node_terms, pred_terms, all_predicates, &[], &[]);
809 }
810
811 /// [`prefetch_lookups_with`](Self::prefetch_lookups_with), and the chunks
812 /// that resolving `node_ids` and `predicate_ids` to strings
813 /// ([`prefetch_terms`](Self::prefetch_terms)) will read, in the same two
814 /// batches: every routing leaf of both in one read, every chunk of both in
815 /// one. Looking terms up and decoding ids are independent, so doing the one
816 /// after the other doubled the dependent reads on a leafed dictionary.
817 pub(crate) fn prefetch_lookups_and_terms<'a>(
818 &self,
819 node_terms: impl IntoIterator<Item = &'a str>,
820 pred_terms: impl IntoIterator<Item = &'a str>,
821 all_predicates: bool,
822 node_ids: &[u32],
823 predicate_ids: &[u32],
824 ) {
825 if !self.faults_chunks() {
826 return;
827 }
828 // Both term lists are walked twice (routing needs the leaves, which are
829 // faulted together first), so hold them.
830 self.prefetch_derived(self.derived_locals(node_ids));
831 let node_terms: Vec<&'a str> = node_terms.into_iter().collect();
832 // A term of a derived family is looked up through its two inputs: read
833 // theirs in the same batches.
834 let inputs: Vec<String> = match &self.derived {
835 Some(d) => node_terms.iter().flat_map(|t| d.lookup_terms(t)).collect(),
836 None => Vec::new(),
837 };
838 let node_terms: Vec<&str> = node_terms
839 .iter()
840 .copied()
841 .chain(inputs.iter().map(String::as_str))
842 .collect();
843 let pred_terms: Vec<&'a str> = pred_terms.into_iter().collect();
844 let mut leaves: [Vec<usize>; 4] = Default::default();
845 for &term in &node_terms {
846 let alias = crate::terms::string_literal_alias(term);
847 for t in std::iter::once(term).chain(alias.as_deref()) {
848 for (si, ls) in leaves.iter_mut().enumerate().take(3) {
849 ls.extend(self.sections[si].leaf_for_term(t));
850 }
851 }
852 }
853 for &term in &pred_terms {
854 leaves[3].extend(self.sections[3].leaf_for_term(term));
855 }
856 let whole_preds = all_predicates
857 && (1..=WHOLE_PREDICATE_CHUNKS).contains(&self.sections[3].chunk_total());
858 if whole_preds {
859 leaves[3].extend(self.sections[3].all_leaves());
860 }
861 for &n in node_ids {
862 if let Some((si, local)) = self.node_section_id(n) {
863 leaves[si].extend(self.sections[si].leaf_of_id(local));
864 }
865 }
866 for &p in predicate_ids {
867 leaves[3].extend(self.sections[3].leaf_of_id(p));
868 }
869 self.fault_leaves(&leaves);
870 let mut want: [std::collections::BTreeSet<usize>; 4] = Default::default();
871 for term in node_terms {
872 let alias = crate::terms::string_literal_alias(term);
873 for t in std::iter::once(term).chain(alias.as_deref()) {
874 for (si, set) in want.iter_mut().enumerate().take(3) {
875 if let Some(ci) = self.sections[si].chunk_for_term(t) {
876 set.insert(ci);
877 }
878 }
879 }
880 }
881 for term in pred_terms {
882 if let Some(ci) = self.sections[3].chunk_for_term(term) {
883 want[3].insert(ci);
884 }
885 }
886 if whole_preds {
887 want[3].extend(0..self.sections[3].chunk_total());
888 }
889 for &n in node_ids {
890 if let Some((si, ci)) = self.node_chunk(n) {
891 want[si].insert(ci);
892 }
893 }
894 for &p in predicate_ids {
895 if let Some(ci) = self.sections[3].chunk_of_id(p) {
896 want[3].insert(ci);
897 }
898 }
899 let want: [Vec<usize>; 4] = want.map(|set| set.into_iter().collect());
900 self.prefetch_sections(&want, PREFETCH_BATCH_CHUNKS);
901 }
902
903 /// The `(section, chunk)` holding a unified node id — mirrors the section
904 /// routing in [`node_term`](Self::node_term).
905 fn node_chunk(&self, node: u32) -> Option<(usize, usize)> {
906 let (si, local) = self.node_section_id(node)?;
907 Some((si, self.sections[si].chunk_of_id(local)?))
908 }
909
910 /// The `(section, section-local id)` of a unified node id — mirrors the
911 /// section routing in [`node_term`](Self::node_term).
912 fn node_section_id(&self, node: u32) -> Option<(usize, u32)> {
913 let su = self.subject_only_count();
914 let id = node.checked_add(1)?; // `node` may come from a corrupt tile
915 Some(if node < self.shared_len.saturating_add(su) {
916 // subject_term(id)
917 if id <= self.shared_len {
918 (0, id)
919 } else {
920 (1, id - self.shared_len)
921 }
922 } else {
923 let id = id - su; // object_term(id)
924 if id <= self.shared_len {
925 (0, id)
926 } else {
927 (2, id - self.shared_len)
928 }
929 })
930 }
931
932 /// Number of shared terms `S`.
933 pub fn shared_count(&self) -> u32 {
934 self.shared_len
935 }
936
937 /// Number of subject-only terms `Su`.
938 pub fn subject_only_count(&self) -> u32 {
939 self.sections[1].term_count()
940 }
941
942 /// Number of object-only terms `Oo`.
943 pub fn object_only_count(&self) -> u32 {
944 self.sections[2].term_count()
945 }
946
947 /// Number of predicate terms.
948 pub fn predicate_count(&self) -> u32 {
949 self.sections[3].term_count()
950 }
951
952 /// [`subject_term`](Self::subject_term) for many ids at once: one
953 /// chunk-ordered, single-pass walk per section
954 /// ([`ChunkedSection::resolve_into`]) instead of a fault and a run walk per
955 /// id — the difference between a whole-dictionary pass taking minutes and
956 /// taking hours. `out[i]` is exactly what `subject_term(ids[i])` returns.
957 ///
958 /// [`ChunkedSection::resolve_into`]: crate::dict::ChunkedSection::resolve_into
959 pub fn subject_terms(&self, ids: &[SubjectId]) -> Vec<Option<String>> {
960 self.role_terms(ids, 1)
961 }
962
963 /// [`object_term`](Self::object_term) for many ids at once — see
964 /// [`subject_terms`](Self::subject_terms).
965 pub fn object_terms(&self, ids: &[ObjectId]) -> Vec<Option<String>> {
966 self.role_terms(ids, 2)
967 }
968
969 /// Shared ids route to section 0, the rest to `own` (1 subjects, 2 objects)
970 /// with the shared block subtracted — the routing of `subject_term` /
971 /// `object_term`.
972 fn role_terms(&self, ids: &[u32], own: usize) -> Vec<Option<String>> {
973 let mut out = vec![None; ids.len()];
974 let mut shared = Vec::new();
975 let mut rest = Vec::new();
976 for (slot, &id) in ids.iter().enumerate() {
977 if id <= self.shared_len {
978 shared.push((id, slot));
979 } else {
980 rest.push((id - self.shared_len, slot));
981 }
982 }
983 self.sections[0].resolve_into(&mut shared, &mut out);
984 self.sections[own].resolve_into(&mut rest, &mut out);
985 if own == 1 {
986 self.fill_derived(&rest, &mut out);
987 }
988 out
989 }
990
991 // --- unified node space (for graph algorithms / the pyramid) ----------
992 //
993 // Subjects and objects use *separate* ID spaces that overlap on shared
994 // terms; the pyramid needs one node per distinct term. We lay them out as:
995 // [0 .. S) shared
996 // [S .. S+Su) subject-only
997 // [S+Su .. S+Su+Oo) object-only
998
999 /// Total distinct graph nodes `N = S + Su + Oo`.
1000 pub fn node_count(&self) -> u32 {
1001 // Saturating: the counts come from the file, and three hostile ones can
1002 // sum past u32 (a panic in debug builds, a wrong count in release).
1003 self.shared_len
1004 .saturating_add(self.subject_only_count())
1005 .saturating_add(self.object_only_count())
1006 }
1007
1008 /// Unified node ID for a subject-role ID. Shared and subject-only IDs are
1009 /// already contiguous (`1..=S+Su`), so this is just `sid - 1`.
1010 pub fn subject_node(&self, sid: SubjectId) -> NodeId {
1011 // saturating_sub: a corrupt block may carry id 0; valid ids are ≥1 so this
1012 // is identical for well-formed files but never underflow-panics.
1013 sid.saturating_sub(1)
1014 }
1015
1016 /// The subject-role ID of a unified node ID, when the node is a subject
1017 /// (shared or subject-only): the inverse of [`Self::subject_node`]. An
1018 /// object-only node has none. No term is decoded.
1019 pub fn node_subject_id(&self, node: NodeId) -> Option<SubjectId> {
1020 (node < self.shared_len.saturating_add(self.subject_only_count())).then(|| node + 1)
1021 }
1022
1023 /// Unified node ID for an object-role ID: shared stay at `oid-1`, object-only
1024 /// IDs are shifted past the subject-only block.
1025 pub fn object_node(&self, oid: ObjectId) -> NodeId {
1026 if oid <= self.shared_len {
1027 oid.saturating_sub(1)
1028 } else {
1029 // Saturating: a corrupt tile may carry an object id near u32::MAX;
1030 // the result is then past every node and resolves to nothing.
1031 oid.saturating_sub(1)
1032 .saturating_add(self.subject_only_count())
1033 }
1034 }
1035
1036 /// [`node_term`](Self::node_term) for a caller that decodes many nodes
1037 /// (see [`crate::dict::ChunkedSection::term_held`]): `hold` is the
1038 /// caller's, one per dictionary.
1039 pub(crate) fn node_term_held(&self, node: NodeId, hold: &mut TermHold) -> Option<String> {
1040 let su = self.subject_only_count();
1041 let id = node.checked_add(1)?;
1042 let (si, local) = if node < self.shared_len {
1043 (0, id)
1044 } else if node < self.shared_len.saturating_add(su) {
1045 (1, id - self.shared_len)
1046 } else {
1047 // An object id past the shared section, as `object_term` splits it.
1048 let oid = id - su;
1049 if oid <= self.shared_len {
1050 (0, oid)
1051 } else {
1052 (2, oid - self.shared_len)
1053 }
1054 };
1055 if let Some(t) = self.sections[si].term_held(local, &mut hold.0[si]) {
1056 return Some(t);
1057 }
1058 // A subject-only id in a chunk the file derives (`crate::derived`)
1059 // stores no text: rebuild it, as `subject_only_term` does for the
1060 // unheld path.
1061 match &self.derived {
1062 Some(d) if si == 1 && self.sections[1].id_is_elided(local) => d.term(self, local),
1063 _ => None,
1064 }
1065 }
1066
1067 /// [`predicate_term`](Self::predicate_term), as [`Self::node_term_held`].
1068 pub(crate) fn predicate_term_held(
1069 &self,
1070 id: PredicateId,
1071 hold: &mut TermHold,
1072 ) -> Option<String> {
1073 self.sections[3].term_held(id, &mut hold.0[3])
1074 }
1075
1076 /// Resolve a unified node ID back to its term.
1077 pub fn node_term(&self, node: NodeId) -> Option<String> {
1078 let su = self.subject_only_count();
1079 // Checked: `node` may come from a corrupt tile.
1080 let id = node.checked_add(1)?;
1081 if node < self.shared_len.saturating_add(su) {
1082 self.subject_term(id)
1083 } else {
1084 self.object_term(id - su)
1085 }
1086 }
1087
1088 /// Batch-fault the dictionary chunks that decoding these subject-role ids
1089 /// will touch — one coalesced read per section instead of a blocking round
1090 /// trip per id. Purely a cache warmer (resident sections no-op).
1091 pub fn prefetch_subject_terms(&self, ids: &[SubjectId]) {
1092 self.prefetch_derived(
1093 ids.iter()
1094 .filter(|&&id| id > self.shared_len)
1095 .map(|&id| id - self.shared_len),
1096 );
1097 let mut per_section: [Vec<usize>; 2] = Default::default();
1098 for &id in ids {
1099 let (si, local) = if id <= self.shared_len {
1100 (0usize, id)
1101 } else {
1102 (1, id - self.shared_len)
1103 };
1104 if let Some(ci) = self.sections[si].chunk_of_term(local) {
1105 per_section[si].push(ci);
1106 }
1107 }
1108 let [shared, subjects] = per_section;
1109 self.prefetch_sorted([shared, subjects, Vec::new(), Vec::new()]);
1110 }
1111
1112 /// Sort, dedup and fault each section's chunk list (one batch across
1113 /// sections when the dictionary has a cross-section fetcher), at most
1114 /// [`PREFETCH_BATCH_CHUNKS`] chunks per read.
1115 fn prefetch_sorted(&self, mut want: [Vec<usize>; 4]) {
1116 for cis in &mut want {
1117 cis.sort_unstable();
1118 cis.dedup();
1119 }
1120 self.prefetch_sections(&want, PREFETCH_BATCH_CHUNKS);
1121 }
1122
1123 /// [`prefetch_subject_terms`](Self::prefetch_subject_terms) for unified
1124 /// node ids — the id space solution rows carry. Warms every chunk a batch
1125 /// of row decodes (a FILTER's string ops, the projection) is about to
1126 /// fault, using [`node_term`](Self::node_term)'s exact routing.
1127 pub fn prefetch_node_terms(&self, nodes: &[NodeId]) {
1128 self.prefetch_derived(self.derived_locals(nodes));
1129 let su = self.subject_only_count();
1130 let mut per_section: [Vec<usize>; 3] = Default::default();
1131 for &node in nodes {
1132 // Checked: row ids come from tiles, which may be corrupt.
1133 let Some(id) = node.checked_add(1) else {
1134 continue;
1135 };
1136 let (si, local) = if node < self.shared_len.saturating_add(su) {
1137 let sid = id;
1138 if sid <= self.shared_len {
1139 (0usize, sid)
1140 } else {
1141 (1, sid - self.shared_len)
1142 }
1143 } else {
1144 let oid = id - su;
1145 if oid <= self.shared_len {
1146 (0, oid)
1147 } else {
1148 (2, oid - self.shared_len)
1149 }
1150 };
1151 if let Some(ci) = self.sections[si].chunk_of_term(local) {
1152 per_section[si].push(ci);
1153 }
1154 }
1155 let [shared, subjects, objects] = per_section;
1156 self.prefetch_sorted([shared, subjects, objects, Vec::new()]);
1157 }
1158
1159 /// Unified node ID for a term, resolving via subject role then object role.
1160 /// A string literal also matches its other spelling (`"x"` ↔
1161 /// `"x"^^xsd:string`, one RDF 1.1 term; see [`Self::subject_id`]).
1162 pub fn node_of_term(&self, term: &str) -> Option<NodeId> {
1163 // A string literal in the SPARQL order: both spellings in one search
1164 // of each section.
1165 if self.order() == TermOrder::Sparql {
1166 if let Some(alias) = crate::terms::string_literal_alias(term) {
1167 return self.node_of_string(term, &alias);
1168 }
1169 }
1170 self.node_of_term_each(term)
1171 }
1172
1173 /// [`node_of_term`](Self::node_of_term) for a string literal `term` whose
1174 /// other spelling is `alias`: `term` in the shared, subject-only and
1175 /// object-only sections, then `alias` in the same order, as two passes
1176 /// would find them, with each section searched once where the search for
1177 /// one spelling settles the other ([`ChunkedSection::lookup_pair`]).
1178 fn node_of_string(&self, term: &str, alias: &str) -> Option<NodeId> {
1179 let term_is_plain = term.len() < alias.len();
1180 let (lo, hi) = if term_is_plain {
1181 (term, alias)
1182 } else {
1183 (alias, term)
1184 };
1185 let node = |si: usize, id: u32| -> Option<NodeId> {
1186 Some(match si {
1187 0 => self.subject_node(id),
1188 1 => self.subject_node(self.shared_len.checked_add(id)?),
1189 _ => self.object_node(self.shared_len.checked_add(id)?),
1190 })
1191 };
1192 // What each section's search said about the alias (`None`: nothing).
1193 let mut aliases: [Option<Option<u32>>; 3] = [None; 3];
1194 for (si, slot) in aliases.iter_mut().enumerate() {
1195 let (plain, typed) = self.sections[si].lookup_pair(lo, hi);
1196 let (mine, other) = if term_is_plain {
1197 (Some(plain), typed)
1198 } else {
1199 (typed, Some(plain))
1200 };
1201 let mine = match mine {
1202 Some(found) => found,
1203 None => self.sections[si].id(term),
1204 };
1205 if let Some(id) = mine {
1206 return node(si, id);
1207 }
1208 *slot = other;
1209 }
1210 for (si, known) in aliases.into_iter().enumerate() {
1211 let found = match known {
1212 Some(found) => found,
1213 None => self.sections[si].id(alias),
1214 };
1215 if let Some(id) = found {
1216 return node(si, id);
1217 }
1218 }
1219 None
1220 }
1221
1222 /// [`node_of_term`](Self::node_of_term), each spelling looked up on its
1223 /// own: the byte order, and every term that is not a string literal.
1224 fn node_of_term_each(&self, term: &str) -> Option<NodeId> {
1225 // Shared, subject-only, object-only: each section once (the subject and
1226 // the object role both begin with the shared section).
1227 let exact = |t: &str| {
1228 if let Some(sid) = self.subject_id_exact(t) {
1229 return Some(self.subject_node(sid));
1230 }
1231 let oid = self.shared_len.checked_add(self.sections[2].id(t)?)?;
1232 Some(self.object_node(oid))
1233 };
1234 exact(term).or_else(|| exact(&crate::terms::string_literal_alias(term)?))
1235 }
1236
1237 /// Where a node sorts for `ORDER BY` without being decoded: its section
1238 /// (0 shared, 1 subject-only, 2 object-only) and its id in that section,
1239 /// when the dictionary is in the SPARQL order and the id is in an
1240 /// order-exact group (blank node, IRI, text literal, quoted triple). Two
1241 /// nodes of the **same** section compare as their local ids do; nodes of
1242 /// two sections, and a node that is `None` here (a typed literal: numbers
1243 /// sort by value), have to be decoded and compared as terms.
1244 pub fn order_slot(&self, node: NodeId) -> Option<(u8, u32)> {
1245 let (si, local) = self.node_section_id(node)?;
1246 self.sections[si]
1247 .groups()?
1248 .is_exact(local)
1249 .then_some((si as u8, local))
1250 }
1251
1252 /// The terms of section `si` (0 shared, 1 subject-only, 2 object-only, 3
1253 /// predicates) by group, for a SPARQL-ordered dictionary: where the literals
1254 /// and the quoted triples are.
1255 pub fn section_groups(&self, si: usize) -> Option<crate::term_order::GroupCounts> {
1256 self.sections.get(si)?.groups()
1257 }
1258
1259 /// How many terms of section `si` sort before `term` in the section's own
1260 /// order (0 shared, 1 subject-only, 2 object-only, 3 predicates): the
1261 /// section-local ids `1..=n` are the smaller ones. One chunk is read (the
1262 /// one `term` routes to). It places a decoded term among the ids of another
1263 /// section without decoding any of them. `None` if that chunk cannot be read.
1264 pub fn rank_in_section(&self, si: usize, term: &str) -> Option<u32> {
1265 let sec = self.sections.get(si)?;
1266 if si == 1 && sec.has_elided() {
1267 return sec.rank_via(term, &|id| self.subject_only_term(id));
1268 }
1269 sec.rank(term)
1270 }
1271
1272 /// [`Self::order_slot`] for a predicate id: always section 3.
1273 pub fn predicate_order_slot(&self, pid: PredicateId) -> Option<(u8, u32)> {
1274 self.sections[3].groups()?.is_exact(pid).then_some((3, pid))
1275 }
1276
1277 /// Subject-role ID of a node, or `None` if the node never appears as a
1278 /// subject (an object-only term).
1279 pub fn node_as_subject_id(&self, node: NodeId) -> Option<SubjectId> {
1280 if node < self.shared_len.saturating_add(self.subject_only_count()) {
1281 node.checked_add(1)
1282 } else {
1283 None
1284 }
1285 }
1286
1287 /// Object-role ID of a node, or `None` if the node never appears as an
1288 /// object (a subject-only term).
1289 pub fn node_as_object_id(&self, node: NodeId) -> Option<ObjectId> {
1290 let (s, su) = (self.shared_len, self.subject_only_count());
1291 if node < s {
1292 Some(node + 1) // shared
1293 } else if node >= s.saturating_add(su) {
1294 Some(node.checked_add(1)? - su) // object-only
1295 } else {
1296 None // subject-only
1297 }
1298 }
1299
1300 // --- term -> id -------------------------------------------------------
1301
1302 /// Subject-role ID for `term`: shared `1..=S`, else subject-only `S+1..`.
1303 ///
1304 /// A string literal that is not found under its own spelling is looked up
1305 /// under the other (`"x"` ↔ `"x"^^xsd:string`): RDF 1.1 makes them one
1306 /// term, ingest keeps only the plain one, and a file built before it did
1307 /// may hold the typed one. The second lookup runs only on a miss, and the
1308 /// two spellings sort side by side, so it reads no further chunk.
1309 pub fn subject_id(&self, term: &str) -> Option<SubjectId> {
1310 self.subject_id_exact(term)
1311 .or_else(|| self.subject_id_exact(&crate::terms::string_literal_alias(term)?))
1312 }
1313
1314 /// Object-role ID for `term`, with the same string-literal fallback as
1315 /// [`Self::subject_id`].
1316 pub fn object_id(&self, term: &str) -> Option<ObjectId> {
1317 self.object_id_exact(term)
1318 .or_else(|| self.object_id_exact(&crate::terms::string_literal_alias(term)?))
1319 }
1320
1321 fn subject_id_exact(&self, term: &str) -> Option<SubjectId> {
1322 if let Some(id) = self.sections[0].id(term) {
1323 return Some(id);
1324 }
1325 match self.sections[1].lookup(term) {
1326 Lookup::Found(id) => self.shared_len.checked_add(id),
1327 Lookup::Absent => None,
1328 Lookup::Elided { first, last } => self
1329 .derived
1330 .as_ref()?
1331 .lookup(self, term, first, last)
1332 .and_then(|id| self.shared_len.checked_add(id)),
1333 }
1334 }
1335
1336 /// Object-role ID for `term`: shared `1..=S`, else object-only `S+1..`.
1337 pub(crate) fn object_id_exact(&self, term: &str) -> Option<ObjectId> {
1338 if let Some(id) = self.sections[0].id(term) {
1339 return Some(id);
1340 }
1341 self.sections[2]
1342 .id(term)
1343 .and_then(|id| self.shared_len.checked_add(id))
1344 }
1345
1346 /// Predicate ID for `term` (independent space).
1347 pub fn predicate_id(&self, term: &str) -> Option<PredicateId> {
1348 self.sections[3].id(term)
1349 }
1350
1351 // --- id -> term -------------------------------------------------------
1352
1353 pub fn subject_term(&self, id: SubjectId) -> Option<String> {
1354 if id <= self.shared_len {
1355 self.sections[0].term(id)
1356 } else {
1357 self.subject_only_term(id - self.shared_len)
1358 }
1359 }
1360
1361 pub fn object_term(&self, id: ObjectId) -> Option<String> {
1362 if id <= self.shared_len {
1363 self.sections[0].term(id)
1364 } else {
1365 self.sections[2].term(id - self.shared_len)
1366 }
1367 }
1368
1369 pub fn predicate_term(&self, id: PredicateId) -> Option<String> {
1370 self.sections[3].term(id)
1371 }
1372
1373 /// Encode a `(s, p, o)` term triple to its `(subject_id, predicate_id,
1374 /// object_id)`. `None` if any term is unknown.
1375 pub fn encode(&self, s: &str, p: &str, o: &str) -> Option<(SubjectId, PredicateId, ObjectId)> {
1376 Some((
1377 self.subject_id(s)?,
1378 self.predicate_id(p)?,
1379 self.object_id(o)?,
1380 ))
1381 }
1382
1383 /// Resolve a window of `(subject_id, predicate_id, object_id)` triples in
1384 /// **chunk order** and emit each fully-resolved row through `emit` in the
1385 /// window's **original order**.
1386 ///
1387 /// This is the batch twin of resolving each row with
1388 /// [`subject_term`](Self::subject_term) /
1389 /// [`predicate_term`](Self::predicate_term) /
1390 /// [`object_term`](Self::object_term) and emitting on `(Some, Some, Some)`
1391 /// — the exact thing it replaces inside `Rete::dump_filtered_each`. A row is
1392 /// emitted only when all three of its terms resolve, and the bytes of each
1393 /// term are identical to the per-row path, so the dump stays
1394 /// byte-for-byte the same.
1395 ///
1396 /// What changes is *how* the terms are decoded. Each row contributes three
1397 /// jobs to the section that owns its id (shared/subject-only for the
1398 /// subject, predicates for the predicate, shared/object-only for the
1399 /// object); each section then resolves its jobs in one chunk-ordered,
1400 /// single-pass walk ([`ChunkedSection::resolve_into`]). A window whose
1401 /// object ids scatter across the object-only section therefore touches each
1402 /// chunk once — one faulted body, one forward walk — instead of the
1403 /// scattered re-faults and per-row re-walks the row-order path performed.
1404 ///
1405 /// `w` carries the per-window scratch buffers so back-to-back windows cost
1406 /// no allocation beyond growth.
1407 ///
1408 /// [`ChunkedSection::resolve_into`]: crate::dict::ChunkedSection::resolve_into
1409 pub fn resolve_window(
1410 &self,
1411 ids: &[(SubjectId, PredicateId, ObjectId)],
1412 w: &mut WindowResolver,
1413 mut emit: impl FnMut(&str, &str, &str),
1414 ) {
1415 for j in &mut w.jobs {
1416 j.clear();
1417 }
1418 w.out.clear();
1419 w.out.resize(ids.len() * 3, None);
1420 for (i, &(s, p, o)) in ids.iter().enumerate() {
1421 // Subject role: shared (section 0) if `id <= S`, else subject-only
1422 // (section 1) with the shared block subtracted — the exact routing
1423 // of `subject_term`.
1424 if s <= self.shared_len {
1425 w.jobs[0].push((s, i * 3));
1426 } else {
1427 w.jobs[1].push((s - self.shared_len, i * 3));
1428 }
1429 // Predicate role: its own section (3).
1430 w.jobs[3].push((p, i * 3 + 1));
1431 // Object role: shared (section 0) if `id <= S`, else object-only
1432 // (section 2) — the exact routing of `object_term`.
1433 if o <= self.shared_len {
1434 w.jobs[0].push((o, i * 3 + 2));
1435 } else {
1436 w.jobs[2].push((o - self.shared_len, i * 3 + 2));
1437 }
1438 }
1439 for si in 0..4 {
1440 self.sections[si].resolve_into(&mut w.jobs[si], &mut w.out);
1441 }
1442 self.fill_derived(&w.jobs[1], &mut w.out);
1443 for i in 0..ids.len() {
1444 if let (Some(s), Some(p), Some(o)) =
1445 (&w.out[i * 3], &w.out[i * 3 + 1], &w.out[i * 3 + 2])
1446 {
1447 emit(s, p, o);
1448 }
1449 }
1450 }
1451
1452 /// The four serialized sections (header + body each), for the file writer.
1453 pub fn sections(&self) -> [Vec<u8>; 4] {
1454 [
1455 self.sections[0].raw_section_bytes(),
1456 self.sections[1].raw_section_bytes(),
1457 self.sections[2].raw_section_bytes(),
1458 self.sections[3].raw_section_bytes(),
1459 ]
1460 }
1461}
1462
1463#[cfg(test)]
1464mod tests {
1465 use super::*;
1466
1467 fn dict() -> Dictionary {
1468 let mut b = DictionaryBuilder::new();
1469 // Alice knows Bob; Bob knows Carol. So Bob is both subject and object
1470 // (shared); Alice is subject-only; Carol is object-only.
1471 b.observe("Alice", "knows", "Bob");
1472 b.observe("Bob", "knows", "Carol");
1473 b.build()
1474 }
1475
1476 /// A string literal is found under either spelling, wherever each is
1477 /// stored, exactly as two separate lookups find it. The dictionary holds
1478 /// plain, typed and both, in every role, with language-tagged and other
1479 /// neighbours, and enough of them that pairs fall on run boundaries.
1480 #[test]
1481 fn a_string_literal_is_found_under_either_spelling_in_one_search() {
1482 const XS: &str = "^^<http://www.w3.org/2001/XMLSchema#string>";
1483 let mut b = DictionaryBuilder::new();
1484 let mut asked: Vec<String> = Vec::new();
1485 for i in 0..600u32 {
1486 let lex = format!("w{:03}", (i * 7) % 600);
1487 let plain = format!("\"{lex}\"");
1488 let typed = format!("\"{lex}\"{XS}");
1489 // Which spellings are stored, and in which role.
1490 let stored: Vec<&String> = match i % 5 {
1491 0 => vec![&plain],
1492 1 => vec![&typed],
1493 2 => vec![&plain, &typed],
1494 3 => vec![],
1495 _ => vec![&typed, &plain],
1496 };
1497 for (k, t) in stored.into_iter().enumerate() {
1498 match (i / 5 + k as u32) % 3 {
1499 0 => b.observe(t, "<p>", "<o>"),
1500 1 => b.observe("<s>", "<p>", t),
1501 _ => {
1502 b.observe(t, "<p>", "<o>");
1503 b.observe("<s>", "<q>", t);
1504 }
1505 }
1506 }
1507 if i % 4 == 0 {
1508 b.observe("<s>", "<p>", &format!("\"{lex}\"@en"));
1509 }
1510 if i % 9 == 0 {
1511 b.observe(
1512 "<s>",
1513 "<p>",
1514 &format!("\"{lex}\"^^<http://www.w3.org/2001/XMLSchema#token>"),
1515 );
1516 }
1517 asked.push(plain);
1518 asked.push(typed);
1519 }
1520 let d = b.build();
1521 assert_eq!(d.order(), TermOrder::Sparql);
1522 let mut found = 0;
1523 for t in &asked {
1524 let got = d.node_of_term(t);
1525 assert_eq!(got, d.node_of_term_each(t), "{t}");
1526 found += usize::from(got.is_some());
1527 }
1528 // Four in five lexical forms are stored under some spelling.
1529 assert_eq!(found, 2 * 480);
1530 // A spelling that is stored is found as itself, not as its alias.
1531 for t in &asked {
1532 if let Some(n) = d.node_of_term(t) {
1533 let back = d.node_term(n).unwrap();
1534 let other = crate::terms::string_literal_alias(t).unwrap();
1535 assert!(back == *t || back == other, "{t} -> {back}");
1536 if d.node_of_term_each(t).is_some() && back != *t {
1537 assert_eq!(
1538 d.sections.iter().take(3).find_map(|sec| sec.id(t)),
1539 None,
1540 "{t} is stored, yet its alias was returned"
1541 );
1542 }
1543 }
1544 }
1545 }
1546
1547 #[test]
1548 fn shared_term_has_same_id_in_both_roles() {
1549 let d = dict();
1550 assert_eq!(d.shared_count(), 1); // just "Bob"
1551 let sid = d.subject_id("Bob").unwrap();
1552 let oid = d.object_id("Bob").unwrap();
1553 assert_eq!(sid, oid, "shared term must share its ID across roles");
1554 assert_eq!(sid, 1, "shared terms get the lowest IDs");
1555 }
1556
1557 #[test]
1558 fn role_specific_terms_round_trip() {
1559 let d = dict();
1560 // subject-only Alice
1561 let a = d.subject_id("Alice").unwrap();
1562 assert!(a > d.shared_count());
1563 assert_eq!(d.subject_term(a).as_deref(), Some("Alice"));
1564 // object-only Carol
1565 let c = d.object_id("Carol").unwrap();
1566 assert!(c > d.shared_count());
1567 assert_eq!(d.object_term(c).as_deref(), Some("Carol"));
1568 // predicate
1569 let k = d.predicate_id("knows").unwrap();
1570 assert_eq!(d.predicate_term(k).as_deref(), Some("knows"));
1571 // Alice never appears as object, Carol never as subject.
1572 assert_eq!(d.object_id("Alice"), None);
1573 assert_eq!(d.subject_id("Carol"), None);
1574 }
1575
1576 #[test]
1577 fn encode_full_triples() {
1578 let d = dict();
1579 let t1 = d.encode("Alice", "knows", "Bob").unwrap();
1580 let t2 = d.encode("Bob", "knows", "Carol").unwrap();
1581 // Bob is object in t1 and subject in t2 — same ID both times.
1582 assert_eq!(t1.2, t2.0);
1583 assert!(d.encode("Nobody", "knows", "Bob").is_none());
1584 }
1585}