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, MultiChunkBulkLoader};
14use crate::terms::{NodeId, ObjectId, PredicateId, SubjectId};
15
16/// Sort a term slice ascending — in parallel when the `parallel` feature is on.
17/// The front-coded dictionary sections need ascending order; doing it once here
18/// (rather than per-insert in a `BTreeSet`) is the fast path for large graphs.
19#[cfg(feature = "parallel")]
20fn sort_terms(v: &mut [String]) {
21    use rayon::slice::ParallelSliceMut;
22    v.par_sort_unstable();
23}
24#[cfg(not(feature = "parallel"))]
25fn sort_terms(v: &mut [String]) {
26    v.sort_unstable();
27}
28
29/// Builds a [`Dictionary`] from observed `(subject, predicate, object)` terms.
30///
31/// Terms are deduped with `HashSet` during ingest (O(1) average insert, no tree
32/// rebalancing) and sorted **once** in [`Self::build`]. This replaces a trio of
33/// `BTreeSet<String>` whose per-insert `O(log n)` cost + a `String` allocation
34/// for *every* observed term (most of them duplicates) dominated the build on
35/// large graphs.
36#[derive(Default)]
37pub struct DictionaryBuilder {
38    subjects: HashSet<String>,
39    objects: HashSet<String>,
40    predicates: HashSet<String>,
41    /// Frequent-object promotion ([`Self::with_frequent_objects`]): how many of
42    /// the most frequent object-only terms move into the shared section.
43    promote: usize,
44    /// Object occurrence counts, kept **instead of** `objects` while promotion
45    /// is on (so a default build pays nothing for it).
46    object_counts: HashMap<String, u64>,
47    /// Count objects without promoting any ([`Self::with_object_counts`]).
48    count_objects: bool,
49    /// Entries in the three term sets — a term once per set it is in — and
50    /// their string bytes ([`Self::footprint`]).
51    entries: u64,
52    entry_bytes: u64,
53}
54
55impl DictionaryBuilder {
56    /// A builder with the process-wide writer settings
57    /// ([`crate::write_opts::frequent_objects`]).
58    pub fn new() -> Self {
59        Self::default().with_frequent_objects(crate::write_opts::frequent_objects())
60    }
61
62    /// Promote the `n` most frequent **object-only** terms (by the number of
63    /// statements that carry them as object; ties by term order) into the
64    /// shared section (`0` = off, the default).
65    ///
66    /// The shared section is numbered first and in term order, so a promoted
67    /// vocabulary term (a class, a scheme individual, a status literal) gets a
68    /// small object id wherever it sorts ahead of the shared entities — the
69    /// effect declaring the vocabulary in a TBox has, without the TBox. A
70    /// promoted term keeps its object id role; the subject id it also gets is
71    /// simply never used by any statement. Readers need nothing new: the shared
72    /// section has always been looked up first for both roles.
73    ///
74    /// Set it before the first [`Self::observe`]: promotion counts objects as
75    /// they are observed.
76    pub fn with_frequent_objects(mut self, n: usize) -> Self {
77        debug_assert!(
78            self.objects.is_empty() && self.object_counts.is_empty(),
79            "with_frequent_objects after observe"
80        );
81        self.promote = n;
82        self
83    }
84
85    /// Count every object's occurrences, as promotion does, but promote
86    /// nothing: [`Self::build_counted`] hands the counts of the object-only
87    /// terms back instead. The memory-bounded build's chunks use it, because
88    /// a term's frequency is only known once every chunk's counts are summed
89    /// (`crate::extbuild`).
90    // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
91    #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
92    pub(crate) fn with_object_counts(mut self) -> Self {
93        debug_assert!(
94            self.objects.is_empty() && self.object_counts.is_empty(),
95            "with_object_counts after observe"
96        );
97        self.count_objects = true;
98        self
99    }
100
101    /// Whether objects are kept with their counts rather than as a set.
102    fn counting(&self) -> bool {
103        self.promote > 0 || self.count_objects
104    }
105
106    /// `(entries, bytes)`: the entries of the three term sets observed so far
107    /// — a term once for every set it is in (subject, object, predicate) — and
108    /// the bytes of their strings. What the memory-bounded build charges a
109    /// chunk's dictionary against its budget, since [`Self::build`] costs a
110    /// multiple of each entry.
111    // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
112    #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
113    pub(crate) fn footprint(&self) -> (u64, u64) {
114        (self.entries, self.entry_bytes)
115    }
116
117    fn note_entry(&mut self, term: &str) {
118        self.entries += 1;
119        self.entry_bytes += term.len() as u64;
120    }
121
122    /// Record one triple's terms (IDs are assigned later, in [`Self::build`]).
123    /// We probe with the borrowed `&str` first and only allocate a `String` for
124    /// a genuinely new term — so a graph of N triples does far fewer than 3N
125    /// allocations (each subject/predicate recurs across many triples).
126    pub fn observe(&mut self, subject: &str, predicate: &str, object: &str) {
127        if !self.subjects.contains(subject) {
128            self.subjects.insert(subject.to_string());
129            self.note_entry(subject);
130        }
131        if self.counting() {
132            if let Some(n) = self.object_counts.get_mut(object) {
133                *n += 1;
134            } else {
135                self.object_counts.insert(object.to_string(), 1);
136                self.note_entry(object);
137            }
138        } else if !self.objects.contains(object) {
139            self.objects.insert(object.to_string());
140            self.note_entry(object);
141        }
142        if !self.predicates.contains(predicate) {
143            self.predicates.insert(predicate.to_string());
144            self.note_entry(predicate);
145        }
146    }
147
148    /// Record a **graph name** as a term in the subject role — how the quad
149    /// index (SPEC.md §6.5) makes graph names dictionary ids. It lands in the
150    /// shared section when the name is also an object, else in the
151    /// subject-only section.
152    pub fn observe_graph(&mut self, graph: &str) {
153        if !self.subjects.contains(graph) {
154            self.subjects.insert(graph.to_string());
155            self.note_entry(graph);
156        }
157    }
158
159    pub fn build(self) -> Dictionary {
160        self.build_inner().0
161    }
162
163    /// [`Self::build`] for a builder made [`Self::with_object_counts`]: also
164    /// returns, for every object-only term in the order of the object-only
165    /// section (local ids `1..`), the number of statements that carry it.
166    /// Empty when objects were not counted.
167    // Only the memory-bounded build (`crate::extbuild`, not on wasm32) uses it.
168    #[cfg_attr(target_arch = "wasm32", allow(dead_code))]
169    pub(crate) fn build_counted(self) -> (Dictionary, Vec<u64>) {
170        self.build_inner()
171    }
172
173    fn build_inner(self) -> (Dictionary, Vec<u64>) {
174        // Sort each role's terms once (ascending) — identical output order to
175        // the old BTreeSet iteration, but without the per-insert tree cost.
176        let mut subjects: Vec<String> = self.subjects.into_iter().collect();
177        let mut predicates: Vec<String> = self.predicates.into_iter().collect();
178        sort_terms(&mut subjects);
179        sort_terms(&mut predicates);
180
181        // A term is "shared" when it appears as both a subject and an object.
182        let subject_set: HashSet<&str> = subjects.iter().map(String::as_str).collect();
183
184        // The object terms: a plain set, or (promotion on) the count map, used
185        // as-is rather than converted, so no second table over every object.
186        let count_objects = self.count_objects;
187        let object_set = if self.promote > 0 || count_objects {
188            ObjectTerms::Counted(self.object_counts)
189        } else {
190            ObjectTerms::Plain(self.objects)
191        };
192        // Frequent-object promotion: the top `promote` object-only terms by
193        // statement count (ties by term order) join the shared section.
194        let mut promoted: Vec<String> = Vec::new();
195        if let (true, ObjectTerms::Counted(counts)) = (self.promote > 0, &object_set) {
196            let mut top: Vec<(&String, u64)> = counts
197                .iter()
198                .filter(|(t, _)| !subject_set.contains(t.as_str()))
199                .map(|(t, &n)| (t, n))
200                .collect();
201            let k = self.promote.min(top.len());
202            if k > 0 && k < top.len() {
203                top.select_nth_unstable_by(k - 1, |a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(b.0)));
204            }
205            top.truncate(k);
206            promoted = top.into_iter().map(|(t, _)| t.clone()).collect();
207            sort_terms(&mut promoted);
208        }
209        let promoted_set: HashSet<&str> = promoted.iter().map(String::as_str).collect();
210
211        let mut shared_b = DictSectionBuilder::new();
212        let mut subj_b = DictSectionBuilder::new();
213        let mut obj_b = DictSectionBuilder::new();
214        let mut pred_b = DictSectionBuilder::new();
215
216        // Subjects ascending: shared (also an object) vs subject-only. Promoted
217        // objects are merged into the shared run in term order.
218        let mut promoted_iter = promoted.iter().peekable();
219        for s in &subjects {
220            if object_set.contains(s) {
221                while let Some(p) = promoted_iter.next_if(|p| p.as_str() < s.as_str()) {
222                    shared_b.push(p.clone());
223                }
224                shared_b.push(s.clone());
225            } else {
226                subj_b.push(s.clone());
227            }
228        }
229        for p in promoted_iter {
230            shared_b.push(p.clone());
231        }
232        // Objects ascending: object-only (shared terms were emitted above),
233        // with their counts when the caller asked for them.
234        // RDF-star: a quoted triple only ever appears in subject/object position,
235        // so a single prefix scan of those term sets detects the whole file.
236        let mut has_quoted_triples = subjects.iter().any(|s| s.starts_with("<<"));
237        let mut object_only_counts: Vec<u64> = Vec::new();
238        let mut take_object = |o: &String, n: u64| {
239            has_quoted_triples |= o.starts_with("<<");
240            if !subject_set.contains(o.as_str()) && !promoted_set.contains(o.as_str()) {
241                obj_b.push(o.clone());
242                if count_objects {
243                    object_only_counts.push(n);
244                }
245            }
246        };
247        match object_set {
248            ObjectTerms::Counted(counts) if count_objects => {
249                let mut objects: Vec<(String, u64)> = counts.into_iter().collect();
250                sort_counted_terms(&mut objects);
251                for (o, n) in &objects {
252                    take_object(o, *n);
253                }
254            }
255            object_set => {
256                let mut objects: Vec<String> = object_set.into_terms();
257                sort_terms(&mut objects);
258                for o in &objects {
259                    take_object(o, 0);
260                }
261            }
262        }
263        for p in &predicates {
264            pred_b.push(p.clone());
265        }
266
267        let shared = shared_b.build();
268        let mut dict =
269            Dictionary::from_sections([shared, subj_b.build(), obj_b.build(), pred_b.build()]);
270        dict.has_quoted_triples = has_quoted_triples;
271        (dict, object_only_counts)
272    }
273}
274
275/// Sort `(term, count)` pairs by term — the terms are distinct, so the
276/// count never decides. In parallel when the `parallel` feature is on.
277fn sort_counted_terms(v: &mut [(String, u64)]) {
278    #[cfg(feature = "parallel")]
279    {
280        use rayon::slice::ParallelSliceMut;
281        v.par_sort_unstable_by(|a, b| a.0.cmp(&b.0));
282    }
283    #[cfg(not(feature = "parallel"))]
284    v.sort_unstable_by(|a, b| a.0.cmp(&b.0));
285}
286
287/// The object terms a [`DictionaryBuilder`] observed: a set, or the
288/// occurrence counts frequent-object promotion needs.
289enum ObjectTerms {
290    Plain(HashSet<String>),
291    Counted(HashMap<String, u64>),
292}
293
294impl ObjectTerms {
295    fn contains(&self, term: &str) -> bool {
296        match self {
297            ObjectTerms::Plain(s) => s.contains(term),
298            ObjectTerms::Counted(m) => m.contains_key(term),
299        }
300    }
301
302    fn into_terms(self) -> Vec<String> {
303        match self {
304            ObjectTerms::Plain(s) => s.into_iter().collect(),
305            ObjectTerms::Counted(m) => m.into_keys().collect(),
306        }
307    }
308}
309
310/// Reusable per-window scratch for [`Dictionary::resolve_window`]: one job list
311/// per section (`(local_id, out_slot)` pairs) and the resolved-term output.
312/// Held across windows by the export loop so a window allocates only when a
313/// buffer must grow.
314#[derive(Default)]
315pub struct WindowResolver {
316    /// Jobs per dictionary section (shared, subject-only, object-only,
317    /// predicates): each `(section-local id, output slot)`.
318    jobs: [Vec<(u32, usize)>; 4],
319    /// Resolved terms, indexed by output slot `row * 3 + {0:s, 1:p, 2:o}`.
320    out: Vec<Option<String>>,
321}
322
323/// The most chunks one id-list prefetch ([`Dictionary::prefetch_subject_terms`],
324/// [`Dictionary::prefetch_node_terms`]) faults in a single batch. A batch holds
325/// every body it fetched until all are cached, so this bounds that transient
326/// (512 chunks of ≤64 KiB: ≤32 MiB) however many ids a caller passes; a longer
327/// list goes out in several batches.
328const PREFETCH_BATCH_CHUNKS: usize = 512;
329
330/// The most chunks the predicate section may have for a query with a variable
331/// predicate to read all of it up front ([`Dictionary::prefetch_lookups_with`]).
332const WHOLE_PREDICATE_CHUNKS: usize = 4;
333
334/// A read-only dictionary mapping terms ↔ role-specific IDs.
335///
336/// Holds the four sections as [`ChunkedSection`]s — local files keep each
337/// section as one resident chunk; a lazily-opened remote file faults
338/// individual chunks in on first touch. Lookups never re-parse a header.
339pub struct Dictionary {
340    /// shared, subjects, objects, predicates.
341    sections: [ChunkedSection; 4],
342    shared_len: u32,
343    /// Whether any term is an RDF-star quoted triple (`<< … >>`). Set at build
344    /// time (from the observed terms); `false` on the read path, where the
345    /// header's `FLAG_HAS_QUOTED_TRIPLES` is the source of truth instead.
346    has_quoted_triples: bool,
347    /// Faults the chunks of several sections in one batch (a ranged open);
348    /// `None` = section by section (local, or no batch reader).
349    multi_bulk: Option<MultiChunkBulkLoader>,
350    /// The literal object ids ([`Self::literal_objects`]), once found.
351    literal_objects: std::sync::OnceLock<LiteralObjects>,
352}
353
354/// Which object ids are literals. Literal tokens (`"…`) sort before IRIs
355/// (`<…`), blank nodes (`_:…`) and quoted triples (`<<…`) in every dictionary
356/// section, so the literals of a section are one run of consecutive ids: the
357/// shared section's are normally none (a literal is never a subject), the
358/// object-only section's come first.
359#[derive(Debug, Clone, Copy, PartialEq, Eq)]
360pub struct LiteralObjects {
361    /// Shared object ids `shared.0+1..=shared.1` are literals.
362    pub shared: (u32, u32),
363    /// `S`, the shared-term count: object ids above it are object-only.
364    pub n_shared: u32,
365    /// Object-only object ids `S+only.0+1..=S+only.1` are literals.
366    pub only: (u32, u32),
367}
368
369impl LiteralObjects {
370    /// Is every object id in `lo..=hi` a literal?
371    pub fn covers(&self, lo: u32, hi: u32) -> bool {
372        let within = |(a, b): (u64, u64)| lo as u64 > a && hi as u64 <= b;
373        lo <= hi
374            && (within((self.shared.0 as u64, self.shared.1 as u64))
375                || within((
376                    self.n_shared as u64 + self.only.0 as u64,
377                    self.n_shared as u64 + self.only.1 as u64,
378                )))
379    }
380
381    /// Is object id `o` a literal?
382    pub fn contains(&self, o: u32) -> bool {
383        self.covers(o, o)
384    }
385}
386
387impl Dictionary {
388    /// Rebuild from four serialized sections (shared, subjects, objects,
389    /// predicates), e.g. when reading a `.rete` file. The four sections share one
390    /// [`ChunkCache`] (unlimited cap here, so every section body stays resident
391    /// exactly as before).
392    pub fn from_sections(sections: [Vec<u8>; 4]) -> Self {
393        let cache = ChunkCache::unlimited_arc();
394        let mut section_index = 0u8;
395        let chunked = sections.map(|bytes| {
396            let s = ChunkedSection::local(bytes, cache.clone(), section_index);
397            section_index += 1;
398            s
399        });
400        Self::from_chunked_sections(chunked)
401    }
402
403    /// Rebuild from four already-chunked sections (the remote lazy-open path).
404    pub fn from_chunked_sections(sections: [ChunkedSection; 4]) -> Self {
405        let shared_len = sections[0].term_count();
406        Dictionary {
407            sections,
408            shared_len,
409            has_quoted_triples: false,
410            multi_bulk: None,
411            literal_objects: std::sync::OnceLock::new(),
412        }
413    }
414
415    /// The object ids that are literals (see [`LiteralObjects`]): two binary
416    /// searches per section for where the `"` tokens start and end, each in the
417    /// one chunk the boundary routes to — two chunk faults at most on a lazy
418    /// open, done once. `None` when a chunk cannot be read, which a caller
419    /// treats as "not proven".
420    pub fn literal_objects(&self) -> Option<LiteralObjects> {
421        if let Some(found) = self.literal_objects.get() {
422            return Some(*found);
423        }
424        // `"` is 0x22 and `#` the next byte: a literal token sorts in
425        // [`"`, `#`), and nothing a well-formed file holds sorts before it.
426        // A failed read is not cached, so the next query tries again.
427        let run = |si: usize| -> Option<(u32, u32)> {
428            Some((self.sections[si].rank("\"")?, self.sections[si].rank("#")?))
429        };
430        let found = LiteralObjects {
431            shared: run(0)?,
432            n_shared: self.shared_len,
433            only: run(2)?,
434        };
435        Some(*self.literal_objects.get_or_init(|| found))
436    }
437
438    /// Attach a cross-section chunk fetcher (see [`MultiChunkBulkLoader`]):
439    /// the term prefetchers then fault every section's missing chunks in one
440    /// batch instead of one batch per section.
441    pub(crate) fn with_multi_bulk_loader(mut self, loader: MultiChunkBulkLoader) -> Self {
442        self.multi_bulk = Some(loader);
443        self
444    }
445
446    /// Fault, in one batched read across all four sections, the directory
447    /// leaves `leaves[si]` of each section — the routing step that must precede
448    /// reading a chunk. Routing a term or an id to its chunk faults its leaf, so
449    /// routing them one at a time was one dependent read per leaf and section.
450    /// A no-op on sections whose directory is resident.
451    fn fault_leaves(&self, leaves: &[Vec<usize>; 4]) {
452        let across: Vec<(&dyn crate::index::LeafDir, &[usize])> = leaves
453            .iter()
454            .enumerate()
455            .filter(|(_, lis)| !lis.is_empty())
456            .filter_map(|(si, lis)| {
457                let d: &dyn crate::index::LeafDir = self.sections[si].leaf_dir()?;
458                Some((d, lis.as_slice()))
459            })
460            .collect();
461        crate::index::ensure_leaves_across(&across);
462    }
463
464    /// Fault the chunks `want[si]` of each section, at most `batch` chunks
465    /// per read. With a cross-section fetcher every missing chunk goes out in
466    /// one batch (round trips: one, not one per section); without one, each
467    /// section batches its own. A failed batch leaves the chunks for the
468    /// per-chunk loader, which retries them lookup by lookup. Purely a cache
469    /// warmer: results never depend on it.
470    fn prefetch_sections(&self, want: &[Vec<usize>; 4], batch: usize) {
471        let batch = batch.max(2);
472        if let Some(multi) = &self.multi_bulk {
473            let pairs: Vec<(u8, usize)> = want
474                .iter()
475                .enumerate()
476                .flat_map(|(si, cis)| {
477                    self.sections[si]
478                        .missing_chunks(cis)
479                        .into_iter()
480                        .map(move |ci| (si as u8, ci))
481                })
482                .collect();
483            // A single missing chunk costs the same either way: leave it to
484            // the per-chunk loader, as a section's own batch does.
485            if pairs.len() < 2 {
486                return;
487            }
488            for part in pairs.chunks(batch) {
489                if let Some(bodies) = multi(part) {
490                    if bodies.len() == part.len() {
491                        for (&(si, ci), body) in part.iter().zip(bodies) {
492                            self.sections[si as usize].seed_chunk(ci, body);
493                        }
494                    }
495                }
496            }
497            return;
498        }
499        for (si, cis) in want.iter().enumerate() {
500            for part in cis.chunks(batch) {
501                self.sections[si].prefetch_chunks(part);
502            }
503        }
504    }
505
506    /// Total number of distinct terms across all four sections.
507    pub fn term_count(&self) -> u32 {
508        self.sections.iter().map(|s| s.term_count()).sum()
509    }
510
511    /// Set the byte cap of the shared chunk cache (bounded-export phase 2).
512    /// `u64::MAX` (the default from every open) means unlimited — no eviction,
513    /// residency identical to the pre-budget design. A finite cap evicts
514    /// least-recently-used chunk bodies down to it on every fault, so a full
515    /// dump's peak dictionary residency is bounded rather than the whole
516    /// decompressed dictionary. All four sections share one cache; setting it on
517    /// each is idempotent (they are the same `Arc`).
518    pub fn set_cache_cap(&self, cap: u64) {
519        for s in &self.sections {
520            s.cache().set_cap(cap);
521        }
522    }
523
524    /// Heap bytes the four sections' chunk directories hold for as long as
525    /// the dictionary is open (see [`ChunkedSection::directory_bytes`]).
526    ///
527    /// [`ChunkedSection::directory_bytes`]: crate::dict::ChunkedSection::directory_bytes
528    pub fn directory_bytes(&self) -> u64 {
529        self.sections.iter().map(|s| s.directory_bytes()).sum()
530    }
531
532    /// The current chunk-cache byte cap (`u64::MAX` = unlimited).
533    pub fn cache_cap(&self) -> u64 {
534        self.sections[0].cache().cap()
535    }
536
537    /// A snapshot of the shared chunk cache's observability counters — for
538    /// `RETE_OPEN_DEBUG` accounting and the eviction tests.
539    pub fn cache_stats(&self) -> crate::chunk_cache::CacheStats {
540        self.sections[0].cache().stats()
541    }
542
543    /// Does this dataset contain RDF-star quoted triples? Meaningful only for a
544    /// freshly built dictionary (a read-back one carries the truth in the file
545    /// header's `FLAG_HAS_QUOTED_TRIPLES`, not here).
546    pub fn has_quoted_triples(&self) -> bool {
547        self.has_quoted_triples
548    }
549
550    /// Record whether the dataset holds quoted triples (a read-back dictionary
551    /// takes it from the file header).
552    pub fn set_has_quoted_triples(&mut self, v: bool) {
553        self.has_quoted_triples = v;
554    }
555
556    /// Did any lazy chunk fetch fail since this dictionary was opened — or
557    /// since the last [`reset_load_failure`](Self::reset_load_failure)?
558    pub fn load_incomplete(&self) -> bool {
559        self.sections.iter().any(|s| s.load_incomplete())
560    }
561
562    /// Forget recorded fetch failures across every section (see
563    /// `GraphIndex::reset_load_failure` — the per-query reset for resident
564    /// sessions). Failed chunks were never cached, so they simply retry.
565    pub fn reset_load_failure(&self) {
566        self.sections.iter().for_each(|s| s.reset_load_failure());
567    }
568
569    /// Batch-fault every unloaded chunk of every section (no-op for local
570    /// dictionaries). Callers about to resolve *every* term — export, dump —
571    /// call this once so the sweep coalesces into a few range reads instead
572    /// of one fetch per chunk.
573    pub fn prefetch_all(&self) {
574        for s in &self.sections {
575            s.prefetch_all();
576        }
577    }
578
579    /// Batch-fault just the chunks needed to resolve a bounded result set:
580    /// `node_ids` are unified-node ids (the `Val::Id(id)` with `id >= 0`),
581    /// `predicate_ids` are predicate-space ids. Groups them by `(section,
582    /// chunk)` and coalesces each section's faults into a few range reads —
583    /// turning "one request per distinct output term" into "a handful per
584    /// query". No-op for a local dictionary (every chunk is already resident).
585    pub fn prefetch_terms(&self, node_ids: &[u32], predicate_ids: &[u32]) {
586        self.prefetch_terms_batched(node_ids, predicate_ids, usize::MAX);
587    }
588
589    /// [`prefetch_terms`](Self::prefetch_terms), faulting at most `batch` chunks
590    /// per bulk read. A bulk read holds every chunk it fetches — the coalesced
591    /// span, the per-chunk slices and the decoded bodies — until all of them
592    /// are cached, so an unbatched prefetch of a scattered window materialized
593    /// up to thousands of chunks at once, outside every cache cap. A bounded
594    /// export batches it so that transient stays a few MB.
595    pub fn prefetch_terms_batched(&self, node_ids: &[u32], predicate_ids: &[u32], batch: usize) {
596        let mut leaves: [Vec<usize>; 4] = Default::default();
597        for &n in node_ids {
598            if let Some((si, local)) = self.node_section_id(n) {
599                leaves[si].extend(self.sections[si].leaf_of_id(local));
600            }
601        }
602        for &p in predicate_ids {
603            leaves[3].extend(self.sections[3].leaf_of_id(p));
604        }
605        self.fault_leaves(&leaves);
606        let mut want: [std::collections::BTreeSet<usize>; 4] = Default::default();
607        for &n in node_ids {
608            if let Some((si, ci)) = self.node_chunk(n) {
609                want[si].insert(ci);
610            }
611        }
612        for &p in predicate_ids {
613            if let Some(ci) = self.sections[3].chunk_of_id(p) {
614                want[3].insert(ci);
615            }
616        }
617        let want: [Vec<usize>; 4] = want.map(|set| set.into_iter().collect());
618        self.prefetch_sections(&want, batch);
619    }
620
621    /// Does any section fault chunk bodies in on demand (a lazy or ranged
622    /// open)? `false` for a resident dictionary, where every prefetch is a no-op.
623    pub fn faults_chunks(&self) -> bool {
624        self.sections.iter().any(|s| s.faults_chunks())
625    }
626
627    /// Batch-fault every chunk that looking these terms up will read, so the
628    /// lookups that follow are cache hits: **one** batched read (one round trip
629    /// remotely) instead of one dependent fetch per term and section.
630    ///
631    /// `node_terms` are looked up as nodes ([`node_of_term`](Self::node_of_term),
632    /// [`subject_id`](Self::subject_id), [`object_id`](Self::object_id)), which
633    /// probe the shared section and then the subject-only or object-only one —
634    /// so all three routed chunks are fetched, plus those of the other spelling
635    /// of a string literal (`"x"` ↔ `"x"^^xsd:string`). `pred_terms` are looked
636    /// up in the predicate section. The routing is the lookup's own
637    /// ([`ChunkedSection::chunk_for_term`]), read off the resident chunk
638    /// directories. Purely a cache warmer: no-op on a resident dictionary, and
639    /// a failed batch leaves every chunk to the per-lookup loader.
640    ///
641    /// [`ChunkedSection::chunk_for_term`]: crate::dict::ChunkedSection::chunk_for_term
642    pub fn prefetch_lookups<'a>(
643        &self,
644        node_terms: impl IntoIterator<Item = &'a str>,
645        pred_terms: impl IntoIterator<Item = &'a str>,
646    ) {
647        self.prefetch_lookups_with(node_terms, pred_terms, false);
648    }
649
650    /// [`prefetch_lookups`](Self::prefetch_lookups), and with `all_predicates`
651    /// the whole predicate section too when it is small (at most
652    /// [`WHOLE_PREDICATE_CHUNKS`] chunks, a few hundred bytes to a few KiB on
653    /// real files). A pattern with a variable predicate decodes and
654    /// canonicalizes every predicate it matches: reading them with the
655    /// constants costs no round trip of its own, where reading them when the
656    /// first rows arrive was two (the leaf, then the chunk).
657    pub(crate) fn prefetch_lookups_with<'a>(
658        &self,
659        node_terms: impl IntoIterator<Item = &'a str>,
660        pred_terms: impl IntoIterator<Item = &'a str>,
661        all_predicates: bool,
662    ) {
663        self.prefetch_lookups_and_terms(node_terms, pred_terms, all_predicates, &[], &[]);
664    }
665
666    /// [`prefetch_lookups_with`](Self::prefetch_lookups_with), and the chunks
667    /// that resolving `node_ids` and `predicate_ids` to strings
668    /// ([`prefetch_terms`](Self::prefetch_terms)) will read, in the same two
669    /// batches: every routing leaf of both in one read, every chunk of both in
670    /// one. Looking terms up and decoding ids are independent, so doing the one
671    /// after the other doubled the dependent reads on a leafed dictionary.
672    pub(crate) fn prefetch_lookups_and_terms<'a>(
673        &self,
674        node_terms: impl IntoIterator<Item = &'a str>,
675        pred_terms: impl IntoIterator<Item = &'a str>,
676        all_predicates: bool,
677        node_ids: &[u32],
678        predicate_ids: &[u32],
679    ) {
680        if !self.faults_chunks() {
681            return;
682        }
683        // Both term lists are walked twice (routing needs the leaves, which are
684        // faulted together first), so hold them.
685        let node_terms: Vec<&'a str> = node_terms.into_iter().collect();
686        let pred_terms: Vec<&'a str> = pred_terms.into_iter().collect();
687        let mut leaves: [Vec<usize>; 4] = Default::default();
688        for &term in &node_terms {
689            let alias = crate::terms::string_literal_alias(term);
690            for t in std::iter::once(term).chain(alias.as_deref()) {
691                for (si, ls) in leaves.iter_mut().enumerate().take(3) {
692                    ls.extend(self.sections[si].leaf_for_term(t));
693                }
694            }
695        }
696        for &term in &pred_terms {
697            leaves[3].extend(self.sections[3].leaf_for_term(term));
698        }
699        let whole_preds = all_predicates
700            && (1..=WHOLE_PREDICATE_CHUNKS).contains(&self.sections[3].chunk_total());
701        if whole_preds {
702            leaves[3].extend(self.sections[3].all_leaves());
703        }
704        for &n in node_ids {
705            if let Some((si, local)) = self.node_section_id(n) {
706                leaves[si].extend(self.sections[si].leaf_of_id(local));
707            }
708        }
709        for &p in predicate_ids {
710            leaves[3].extend(self.sections[3].leaf_of_id(p));
711        }
712        self.fault_leaves(&leaves);
713        let mut want: [std::collections::BTreeSet<usize>; 4] = Default::default();
714        for term in node_terms {
715            let alias = crate::terms::string_literal_alias(term);
716            for t in std::iter::once(term).chain(alias.as_deref()) {
717                for (si, set) in want.iter_mut().enumerate().take(3) {
718                    if let Some(ci) = self.sections[si].chunk_for_term(t) {
719                        set.insert(ci);
720                    }
721                }
722            }
723        }
724        for term in pred_terms {
725            if let Some(ci) = self.sections[3].chunk_for_term(term) {
726                want[3].insert(ci);
727            }
728        }
729        if whole_preds {
730            want[3].extend(0..self.sections[3].chunk_total());
731        }
732        for &n in node_ids {
733            if let Some((si, ci)) = self.node_chunk(n) {
734                want[si].insert(ci);
735            }
736        }
737        for &p in predicate_ids {
738            if let Some(ci) = self.sections[3].chunk_of_id(p) {
739                want[3].insert(ci);
740            }
741        }
742        let want: [Vec<usize>; 4] = want.map(|set| set.into_iter().collect());
743        self.prefetch_sections(&want, PREFETCH_BATCH_CHUNKS);
744    }
745
746    /// The `(section, chunk)` holding a unified node id — mirrors the section
747    /// routing in [`node_term`](Self::node_term).
748    fn node_chunk(&self, node: u32) -> Option<(usize, usize)> {
749        let (si, local) = self.node_section_id(node)?;
750        Some((si, self.sections[si].chunk_of_id(local)?))
751    }
752
753    /// The `(section, section-local id)` of a unified node id — mirrors the
754    /// section routing in [`node_term`](Self::node_term).
755    fn node_section_id(&self, node: u32) -> Option<(usize, u32)> {
756        let su = self.subject_only_count();
757        let id = node.checked_add(1)?; // `node` may come from a corrupt tile
758        Some(if node < self.shared_len.saturating_add(su) {
759            // subject_term(id)
760            if id <= self.shared_len {
761                (0, id)
762            } else {
763                (1, id - self.shared_len)
764            }
765        } else {
766            let id = id - su; // object_term(id)
767            if id <= self.shared_len {
768                (0, id)
769            } else {
770                (2, id - self.shared_len)
771            }
772        })
773    }
774
775    /// Number of shared terms `S`.
776    pub fn shared_count(&self) -> u32 {
777        self.shared_len
778    }
779
780    /// Number of subject-only terms `Su`.
781    pub fn subject_only_count(&self) -> u32 {
782        self.sections[1].term_count()
783    }
784
785    /// Number of object-only terms `Oo`.
786    pub fn object_only_count(&self) -> u32 {
787        self.sections[2].term_count()
788    }
789
790    /// Number of predicate terms.
791    pub fn predicate_count(&self) -> u32 {
792        self.sections[3].term_count()
793    }
794
795    /// [`subject_term`](Self::subject_term) for many ids at once: one
796    /// chunk-ordered, single-pass walk per section
797    /// ([`ChunkedSection::resolve_into`]) instead of a fault and a run walk per
798    /// id — the difference between a whole-dictionary pass taking minutes and
799    /// taking hours. `out[i]` is exactly what `subject_term(ids[i])` returns.
800    ///
801    /// [`ChunkedSection::resolve_into`]: crate::dict::ChunkedSection::resolve_into
802    pub fn subject_terms(&self, ids: &[SubjectId]) -> Vec<Option<String>> {
803        self.role_terms(ids, 1)
804    }
805
806    /// [`object_term`](Self::object_term) for many ids at once — see
807    /// [`subject_terms`](Self::subject_terms).
808    pub fn object_terms(&self, ids: &[ObjectId]) -> Vec<Option<String>> {
809        self.role_terms(ids, 2)
810    }
811
812    /// Shared ids route to section 0, the rest to `own` (1 subjects, 2 objects)
813    /// with the shared block subtracted — the routing of `subject_term` /
814    /// `object_term`.
815    fn role_terms(&self, ids: &[u32], own: usize) -> Vec<Option<String>> {
816        let mut out = vec![None; ids.len()];
817        let mut shared = Vec::new();
818        let mut rest = Vec::new();
819        for (slot, &id) in ids.iter().enumerate() {
820            if id <= self.shared_len {
821                shared.push((id, slot));
822            } else {
823                rest.push((id - self.shared_len, slot));
824            }
825        }
826        self.sections[0].resolve_into(&mut shared, &mut out);
827        self.sections[own].resolve_into(&mut rest, &mut out);
828        out
829    }
830
831    // --- unified node space (for graph algorithms / the pyramid) ----------
832    //
833    // Subjects and objects use *separate* ID spaces that overlap on shared
834    // terms; the pyramid needs one node per distinct term. We lay them out as:
835    //   [0 .. S)            shared
836    //   [S .. S+Su)         subject-only
837    //   [S+Su .. S+Su+Oo)   object-only
838
839    /// Total distinct graph nodes `N = S + Su + Oo`.
840    pub fn node_count(&self) -> u32 {
841        // Saturating: the counts come from the file, and three hostile ones can
842        // sum past u32 (a panic in debug builds, a wrong count in release).
843        self.shared_len
844            .saturating_add(self.subject_only_count())
845            .saturating_add(self.object_only_count())
846    }
847
848    /// Unified node ID for a subject-role ID. Shared and subject-only IDs are
849    /// already contiguous (`1..=S+Su`), so this is just `sid - 1`.
850    pub fn subject_node(&self, sid: SubjectId) -> NodeId {
851        // saturating_sub: a corrupt block may carry id 0; valid ids are ≥1 so this
852        // is identical for well-formed files but never underflow-panics.
853        sid.saturating_sub(1)
854    }
855
856    /// Unified node ID for an object-role ID: shared stay at `oid-1`, object-only
857    /// IDs are shifted past the subject-only block.
858    pub fn object_node(&self, oid: ObjectId) -> NodeId {
859        if oid <= self.shared_len {
860            oid.saturating_sub(1)
861        } else {
862            // Saturating: a corrupt tile may carry an object id near u32::MAX;
863            // the result is then past every node and resolves to nothing.
864            oid.saturating_sub(1)
865                .saturating_add(self.subject_only_count())
866        }
867    }
868
869    /// Resolve a unified node ID back to its term.
870    pub fn node_term(&self, node: NodeId) -> Option<String> {
871        let su = self.subject_only_count();
872        // Checked: `node` may come from a corrupt tile.
873        let id = node.checked_add(1)?;
874        if node < self.shared_len.saturating_add(su) {
875            self.subject_term(id)
876        } else {
877            self.object_term(id - su)
878        }
879    }
880
881    /// Batch-fault the dictionary chunks that decoding these subject-role ids
882    /// will touch — one coalesced read per section instead of a blocking round
883    /// trip per id. Purely a cache warmer (resident sections no-op).
884    pub fn prefetch_subject_terms(&self, ids: &[SubjectId]) {
885        let mut per_section: [Vec<usize>; 2] = Default::default();
886        for &id in ids {
887            let (si, local) = if id <= self.shared_len {
888                (0usize, id)
889            } else {
890                (1, id - self.shared_len)
891            };
892            if let Some(ci) = self.sections[si].chunk_of_term(local) {
893                per_section[si].push(ci);
894            }
895        }
896        let [shared, subjects] = per_section;
897        self.prefetch_sorted([shared, subjects, Vec::new(), Vec::new()]);
898    }
899
900    /// Sort, dedup and fault each section's chunk list (one batch across
901    /// sections when the dictionary has a cross-section fetcher), at most
902    /// [`PREFETCH_BATCH_CHUNKS`] chunks per read.
903    fn prefetch_sorted(&self, mut want: [Vec<usize>; 4]) {
904        for cis in &mut want {
905            cis.sort_unstable();
906            cis.dedup();
907        }
908        self.prefetch_sections(&want, PREFETCH_BATCH_CHUNKS);
909    }
910
911    /// [`prefetch_subject_terms`](Self::prefetch_subject_terms) for unified
912    /// node ids — the id space solution rows carry. Warms every chunk a batch
913    /// of row decodes (a FILTER's string ops, the projection) is about to
914    /// fault, using [`node_term`](Self::node_term)'s exact routing.
915    pub fn prefetch_node_terms(&self, nodes: &[NodeId]) {
916        let su = self.subject_only_count();
917        let mut per_section: [Vec<usize>; 3] = Default::default();
918        for &node in nodes {
919            // Checked: row ids come from tiles, which may be corrupt.
920            let Some(id) = node.checked_add(1) else {
921                continue;
922            };
923            let (si, local) = if node < self.shared_len.saturating_add(su) {
924                let sid = id;
925                if sid <= self.shared_len {
926                    (0usize, sid)
927                } else {
928                    (1, sid - self.shared_len)
929                }
930            } else {
931                let oid = id - su;
932                if oid <= self.shared_len {
933                    (0, oid)
934                } else {
935                    (2, oid - self.shared_len)
936                }
937            };
938            if let Some(ci) = self.sections[si].chunk_of_term(local) {
939                per_section[si].push(ci);
940            }
941        }
942        let [shared, subjects, objects] = per_section;
943        self.prefetch_sorted([shared, subjects, objects, Vec::new()]);
944    }
945
946    /// Unified node ID for a term, resolving via subject role then object role.
947    /// A string literal also matches its other spelling (`"x"` ↔
948    /// `"x"^^xsd:string`, one RDF 1.1 term; see [`Self::subject_id`]).
949    pub fn node_of_term(&self, term: &str) -> Option<NodeId> {
950        let exact = |t: &str| {
951            self.subject_id_exact(t)
952                .map(|sid| self.subject_node(sid))
953                .or_else(|| self.object_id_exact(t).map(|oid| self.object_node(oid)))
954        };
955        exact(term).or_else(|| exact(&crate::terms::string_literal_alias(term)?))
956    }
957
958    /// Subject-role ID of a node, or `None` if the node never appears as a
959    /// subject (an object-only term).
960    pub fn node_as_subject_id(&self, node: NodeId) -> Option<SubjectId> {
961        if node < self.shared_len.saturating_add(self.subject_only_count()) {
962            node.checked_add(1)
963        } else {
964            None
965        }
966    }
967
968    /// Object-role ID of a node, or `None` if the node never appears as an
969    /// object (a subject-only term).
970    pub fn node_as_object_id(&self, node: NodeId) -> Option<ObjectId> {
971        let (s, su) = (self.shared_len, self.subject_only_count());
972        if node < s {
973            Some(node + 1) // shared
974        } else if node >= s.saturating_add(su) {
975            Some(node.checked_add(1)? - su) // object-only
976        } else {
977            None // subject-only
978        }
979    }
980
981    // --- term -> id -------------------------------------------------------
982
983    /// Subject-role ID for `term`: shared `1..=S`, else subject-only `S+1..`.
984    ///
985    /// A string literal that is not found under its own spelling is looked up
986    /// under the other (`"x"` ↔ `"x"^^xsd:string`): RDF 1.1 makes them one
987    /// term, ingest keeps only the plain one, and a file built before it did
988    /// may hold the typed one. The second lookup runs only on a miss, and the
989    /// two spellings sort side by side, so it reads no further chunk.
990    pub fn subject_id(&self, term: &str) -> Option<SubjectId> {
991        self.subject_id_exact(term)
992            .or_else(|| self.subject_id_exact(&crate::terms::string_literal_alias(term)?))
993    }
994
995    /// Object-role ID for `term`, with the same string-literal fallback as
996    /// [`Self::subject_id`].
997    pub fn object_id(&self, term: &str) -> Option<ObjectId> {
998        self.object_id_exact(term)
999            .or_else(|| self.object_id_exact(&crate::terms::string_literal_alias(term)?))
1000    }
1001
1002    fn subject_id_exact(&self, term: &str) -> Option<SubjectId> {
1003        if let Some(id) = self.sections[0].id(term) {
1004            return Some(id);
1005        }
1006        self.sections[1]
1007            .id(term)
1008            .and_then(|id| self.shared_len.checked_add(id))
1009    }
1010
1011    /// Object-role ID for `term`: shared `1..=S`, else object-only `S+1..`.
1012    fn object_id_exact(&self, term: &str) -> Option<ObjectId> {
1013        if let Some(id) = self.sections[0].id(term) {
1014            return Some(id);
1015        }
1016        self.sections[2]
1017            .id(term)
1018            .and_then(|id| self.shared_len.checked_add(id))
1019    }
1020
1021    /// Predicate ID for `term` (independent space).
1022    pub fn predicate_id(&self, term: &str) -> Option<PredicateId> {
1023        self.sections[3].id(term)
1024    }
1025
1026    // --- id -> term -------------------------------------------------------
1027
1028    pub fn subject_term(&self, id: SubjectId) -> Option<String> {
1029        if id <= self.shared_len {
1030            self.sections[0].term(id)
1031        } else {
1032            self.sections[1].term(id - self.shared_len)
1033        }
1034    }
1035
1036    pub fn object_term(&self, id: ObjectId) -> Option<String> {
1037        if id <= self.shared_len {
1038            self.sections[0].term(id)
1039        } else {
1040            self.sections[2].term(id - self.shared_len)
1041        }
1042    }
1043
1044    pub fn predicate_term(&self, id: PredicateId) -> Option<String> {
1045        self.sections[3].term(id)
1046    }
1047
1048    /// Encode a `(s, p, o)` term triple to its `(subject_id, predicate_id,
1049    /// object_id)`. `None` if any term is unknown.
1050    pub fn encode(&self, s: &str, p: &str, o: &str) -> Option<(SubjectId, PredicateId, ObjectId)> {
1051        Some((
1052            self.subject_id(s)?,
1053            self.predicate_id(p)?,
1054            self.object_id(o)?,
1055        ))
1056    }
1057
1058    /// Resolve a window of `(subject_id, predicate_id, object_id)` triples in
1059    /// **chunk order** and emit each fully-resolved row through `emit` in the
1060    /// window's **original order**.
1061    ///
1062    /// This is the batch twin of resolving each row with
1063    /// [`subject_term`](Self::subject_term) /
1064    /// [`predicate_term`](Self::predicate_term) /
1065    /// [`object_term`](Self::object_term) and emitting on `(Some, Some, Some)`
1066    /// — the exact thing it replaces inside `Rete::dump_filtered_each`. A row is
1067    /// emitted only when all three of its terms resolve, and the bytes of each
1068    /// term are identical to the per-row path, so the dump stays
1069    /// byte-for-byte the same.
1070    ///
1071    /// What changes is *how* the terms are decoded. Each row contributes three
1072    /// jobs to the section that owns its id (shared/subject-only for the
1073    /// subject, predicates for the predicate, shared/object-only for the
1074    /// object); each section then resolves its jobs in one chunk-ordered,
1075    /// single-pass walk ([`ChunkedSection::resolve_into`]). A window whose
1076    /// object ids scatter across the object-only section therefore touches each
1077    /// chunk once — one faulted body, one forward walk — instead of the
1078    /// scattered re-faults and per-row re-walks the row-order path performed.
1079    ///
1080    /// `w` carries the per-window scratch buffers so back-to-back windows cost
1081    /// no allocation beyond growth.
1082    ///
1083    /// [`ChunkedSection::resolve_into`]: crate::dict::ChunkedSection::resolve_into
1084    pub fn resolve_window(
1085        &self,
1086        ids: &[(SubjectId, PredicateId, ObjectId)],
1087        w: &mut WindowResolver,
1088        mut emit: impl FnMut(&str, &str, &str),
1089    ) {
1090        for j in &mut w.jobs {
1091            j.clear();
1092        }
1093        w.out.clear();
1094        w.out.resize(ids.len() * 3, None);
1095        for (i, &(s, p, o)) in ids.iter().enumerate() {
1096            // Subject role: shared (section 0) if `id <= S`, else subject-only
1097            // (section 1) with the shared block subtracted — the exact routing
1098            // of `subject_term`.
1099            if s <= self.shared_len {
1100                w.jobs[0].push((s, i * 3));
1101            } else {
1102                w.jobs[1].push((s - self.shared_len, i * 3));
1103            }
1104            // Predicate role: its own section (3).
1105            w.jobs[3].push((p, i * 3 + 1));
1106            // Object role: shared (section 0) if `id <= S`, else object-only
1107            // (section 2) — the exact routing of `object_term`.
1108            if o <= self.shared_len {
1109                w.jobs[0].push((o, i * 3 + 2));
1110            } else {
1111                w.jobs[2].push((o - self.shared_len, i * 3 + 2));
1112            }
1113        }
1114        for si in 0..4 {
1115            self.sections[si].resolve_into(&mut w.jobs[si], &mut w.out);
1116        }
1117        for i in 0..ids.len() {
1118            if let (Some(s), Some(p), Some(o)) =
1119                (&w.out[i * 3], &w.out[i * 3 + 1], &w.out[i * 3 + 2])
1120            {
1121                emit(s, p, o);
1122            }
1123        }
1124    }
1125
1126    /// The four serialized sections (header + body each), for the file writer.
1127    pub fn sections(&self) -> [Vec<u8>; 4] {
1128        [
1129            self.sections[0].raw_section_bytes(),
1130            self.sections[1].raw_section_bytes(),
1131            self.sections[2].raw_section_bytes(),
1132            self.sections[3].raw_section_bytes(),
1133        ]
1134    }
1135}
1136
1137#[cfg(test)]
1138mod tests {
1139    use super::*;
1140
1141    fn dict() -> Dictionary {
1142        let mut b = DictionaryBuilder::new();
1143        // Alice knows Bob; Bob knows Carol. So Bob is both subject and object
1144        // (shared); Alice is subject-only; Carol is object-only.
1145        b.observe("Alice", "knows", "Bob");
1146        b.observe("Bob", "knows", "Carol");
1147        b.build()
1148    }
1149
1150    #[test]
1151    fn shared_term_has_same_id_in_both_roles() {
1152        let d = dict();
1153        assert_eq!(d.shared_count(), 1); // just "Bob"
1154        let sid = d.subject_id("Bob").unwrap();
1155        let oid = d.object_id("Bob").unwrap();
1156        assert_eq!(sid, oid, "shared term must share its ID across roles");
1157        assert_eq!(sid, 1, "shared terms get the lowest IDs");
1158    }
1159
1160    #[test]
1161    fn role_specific_terms_round_trip() {
1162        let d = dict();
1163        // subject-only Alice
1164        let a = d.subject_id("Alice").unwrap();
1165        assert!(a > d.shared_count());
1166        assert_eq!(d.subject_term(a).as_deref(), Some("Alice"));
1167        // object-only Carol
1168        let c = d.object_id("Carol").unwrap();
1169        assert!(c > d.shared_count());
1170        assert_eq!(d.object_term(c).as_deref(), Some("Carol"));
1171        // predicate
1172        let k = d.predicate_id("knows").unwrap();
1173        assert_eq!(d.predicate_term(k).as_deref(), Some("knows"));
1174        // Alice never appears as object, Carol never as subject.
1175        assert_eq!(d.object_id("Alice"), None);
1176        assert_eq!(d.subject_id("Carol"), None);
1177    }
1178
1179    #[test]
1180    fn encode_full_triples() {
1181        let d = dict();
1182        let t1 = d.encode("Alice", "knows", "Bob").unwrap();
1183        let t2 = d.encode("Bob", "knows", "Carol").unwrap();
1184        // Bob is object in t1 and subject in t2 — same ID both times.
1185        assert_eq!(t1.2, t2.0);
1186        assert!(d.encode("Nobody", "knows", "Bob").is_none());
1187    }
1188}