Skip to main content

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}