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}