rete_core/dict.rs
1//! Front-coded, restart-indexed dictionary sections (SPEC.md §5.1).
2//!
3//! A section holds the UTF-8 terms of one kind (shared / subjects / objects /
4//! predicates / graphs), sorted and assigned dense 1-based IDs. Terms are stored
5//! in runs of `R`; each run starts with a full term and front-codes the rest.
6
7use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
8use std::sync::Arc;
9
10use crate::chunk_cache::{CacheEntry, ChunkCache};
11use crate::term_order::{GroupCounts, TermOrder};
12use crate::varint::{read_uvarint, write_uvarint};
13
14/// Default restart interval: a full term every `R` entries.
15pub const DEFAULT_RESTART_INTERVAL: u32 = 16;
16
17/// Reserved ID meaning "no such term".
18pub const ABSENT: u32 = 0;
19
20/// How many not-yet-resident chunks a windowed resolution
21/// ([`ChunkedSection::decode_and_walk`]) faults concurrently in one group. It
22/// bounds the transient set of decoded bodies held at once (this many `Arc`s,
23/// each ≤ one chunk), so the parallel decode's memory is a small constant on top
24/// of the `--memory-budget-mb` cache, independent of the window size or budget.
25/// Also the group size, so a larger value means fewer (larger) parallel
26/// dispatches — amortizing the per-dispatch cost on the tight-budget path where
27/// real decoding happens.
28#[cfg(feature = "parallel")]
29const PAR_DECODE_FANOUT: usize = 32;
30
31/// A small, dedicated rayon pool for parallel chunk decode. Separate from (and
32/// smaller than) the global pool so the number of decode worker threads — and
33/// thus their allocator arenas, the dominant driver of the resident-set bump
34/// under parallel decode — is a small constant, not the machine's full core
35/// count. Decode is memory-bandwidth/CPU bound and a handful of threads saturate
36/// it, so this bounds peak RSS without materially costing throughput. Built once.
37#[cfg(feature = "parallel")]
38fn decode_pool() -> &'static rayon::ThreadPool {
39 use std::sync::OnceLock;
40 static POOL: OnceLock<rayon::ThreadPool> = OnceLock::new();
41 POOL.get_or_init(|| {
42 let n = std::thread::available_parallelism()
43 .map(|n| n.get())
44 .unwrap_or(4)
45 .clamp(1, 8);
46 rayon::ThreadPoolBuilder::new()
47 .num_threads(n)
48 .thread_name(|i| format!("rete-decode-{i}"))
49 .build()
50 .expect("build dedicated chunk-decode thread pool")
51 })
52}
53
54#[derive(Debug, thiserror::Error)]
55pub enum DictError {
56 #[error("malformed dictionary section: {0}")]
57 Malformed(&'static str),
58}
59
60/// Build a dictionary section from terms (any order; sorted + deduped here).
61#[derive(Default)]
62pub struct DictSectionBuilder {
63 terms: Vec<String>,
64 restart_interval: u32,
65 order: TermOrder,
66}
67
68/// Terms per restart run, overridable via `RETE_DICT_RESTART_INTERVAL`.
69///
70/// The interval sets random-access granularity as well as front-coding gain:
71/// chunks are cut on whole-run boundaries, so with very large literals (e.g.
72/// base64-embedded images) a single run dwarfs the 64 KiB chunk budget and one
73/// term lookup drags in ~`r` terms' worth of bytes. Setting `1` makes every term
74/// its own restart — direct seek, larger restart table, no front-coding (which
75/// is worthless for base64 anyway, since such terms share no prefix).
76pub fn env_restart_interval() -> u32 {
77 static R: std::sync::OnceLock<u32> = std::sync::OnceLock::new();
78 *R.get_or_init(|| {
79 std::env::var("RETE_DICT_RESTART_INTERVAL")
80 .ok()
81 .and_then(|v| v.parse::<u32>().ok())
82 .filter(|&v| v >= 1)
83 .unwrap_or(DEFAULT_RESTART_INTERVAL)
84 })
85}
86
87impl DictSectionBuilder {
88 pub fn new() -> Self {
89 Self {
90 terms: Vec::new(),
91 restart_interval: env_restart_interval(),
92 order: TermOrder::Bytewise,
93 }
94 }
95
96 /// Sort the terms in `order` (default: [`TermOrder::Bytewise`]).
97 pub fn with_order(mut self, order: TermOrder) -> Self {
98 self.order = order;
99 self
100 }
101
102 pub fn with_restart_interval(mut self, r: u32) -> Self {
103 assert!(r >= 1, "restart interval must be >= 1");
104 self.restart_interval = r;
105 self
106 }
107
108 pub fn push(&mut self, term: impl Into<String>) {
109 self.terms.push(term.into());
110 }
111
112 /// Serialize to bytes. Terms are sorted and deduped; the resulting IDs are
113 /// `1..=n` in sorted order.
114 pub fn build(mut self) -> Vec<u8> {
115 let order = self.order;
116 self.terms
117 .sort_unstable_by(|a, b| order.cmp(a.as_bytes(), b.as_bytes()));
118 self.terms.dedup();
119 let r = self.restart_interval as usize;
120 let n = self.terms.len();
121 let num_restarts = n.div_ceil(r);
122
123 // Encode body and capture each run's starting offset (relative to body).
124 let mut body = Vec::new();
125 let mut restart_offsets = Vec::with_capacity(num_restarts);
126 let mut prev = "";
127 for (i, term) in self.terms.iter().enumerate() {
128 if i % r == 0 {
129 restart_offsets.push(body.len() as u64);
130 // restart entry: shared = 0, full term
131 write_uvarint(&mut body, 0);
132 write_uvarint(&mut body, term.len() as u64);
133 body.extend_from_slice(term.as_bytes());
134 } else {
135 let shared = common_prefix_len(prev, term);
136 let suffix = &term.as_bytes()[shared..];
137 write_uvarint(&mut body, shared as u64);
138 write_uvarint(&mut body, suffix.len() as u64);
139 body.extend_from_slice(suffix);
140 }
141 prev = term;
142 }
143
144 // header || restart-offset table || body
145 let mut out = Vec::new();
146 write_uvarint(&mut out, n as u64);
147 write_uvarint(&mut out, self.restart_interval as u64);
148 write_uvarint(&mut out, num_restarts as u64);
149 for off in &restart_offsets {
150 write_uvarint(&mut out, *off);
151 }
152 out.extend_from_slice(&body);
153 out
154 }
155}
156
157/// Parsed section metadata (the restart table) — cache this once and reuse it
158/// across lookups instead of re-parsing the section header every time.
159#[derive(Debug, Clone)]
160pub struct SectionMeta {
161 pub term_count: u32,
162 pub restart_interval: u32,
163 /// Absolute offsets into the section bytes for each run start.
164 ///
165 /// `u64`, not `usize`: a section may exceed 4 GiB and wasm32 is a 32-bit
166 /// target, so a `usize` offset silently truncates there (see #70). A
167 /// dictionary carrying embedded media is exactly this case — WikiArt's is
168 /// 23.4 GB.
169 pub restart_offsets: Vec<u64>,
170}
171
172/// Parse only the header/restart table of a section.
173pub fn parse_meta(bytes: &[u8]) -> Result<SectionMeta, DictError> {
174 let mut pos = 0;
175 let take = |pos: &mut usize| -> Result<u64, DictError> {
176 let (v, n) =
177 read_uvarint(&bytes[*pos..]).ok_or(DictError::Malformed("truncated header"))?;
178 *pos += n;
179 Ok(v)
180 };
181 // Checked, not `as`: a term count or interval past u32, or a restart count
182 // past this target's usize (wasm32), is corrupt — truncating it made a
183 // damaged header read as a smaller, plausible one.
184 let term_count = u32::try_from(take(&mut pos)?)
185 .map_err(|_| DictError::Malformed("term count out of range"))?;
186 let restart_interval = u32::try_from(take(&mut pos)?)
187 .map_err(|_| DictError::Malformed("restart interval out of range"))?;
188 let num_restarts = usize::try_from(take(&mut pos)?)
189 .map_err(|_| DictError::Malformed("restart count out of range"))?;
190 if restart_interval == 0 {
191 return Err(DictError::Malformed("zero restart interval"));
192 }
193 // `num_restarts` is untrusted; each restart is ≥1 byte, so cap the
194 // pre-allocation at the buffer length to avoid an OOM on a bogus count.
195 let mut rel = Vec::with_capacity(num_restarts.min(bytes.len()));
196 for _ in 0..num_restarts {
197 rel.push(take(&mut pos)?);
198 }
199 let body_start = pos as u64;
200 let restart_offsets = rel
201 .into_iter()
202 .map(|o| body_start.checked_add(o))
203 .collect::<Option<Vec<u64>>>()
204 .ok_or(DictError::Malformed("restart offset out of range"))?;
205 Ok(SectionMeta {
206 term_count,
207 restart_interval,
208 restart_offsets,
209 })
210}
211
212/// Decode the front-coded entry at `pos` *into* `buf`: truncate `buf` to the
213/// entry's shared-prefix length and append its suffix bytes. For a restart
214/// entry the stored shared length is 0, so the same decode works for both
215/// entry kinds. Returns the next entry's position; `None` on malformed bytes
216/// (including a shared length longer than the previous term). Allocation-free
217/// after `buf`'s first growth — this is the hot path of every term resolution.
218#[inline]
219fn entry_into(bytes: &[u8], pos: usize, buf: &mut Vec<u8>) -> Option<usize> {
220 let (shared, n1) = read_uvarint(bytes.get(pos..)?)?;
221 let p = pos + n1;
222 let (suf, n2) = read_uvarint(bytes.get(p..)?)?;
223 let start = p + n2;
224 let end = start
225 .checked_add(suf as usize)
226 .filter(|&e| e <= bytes.len())?;
227 if shared as usize > buf.len() {
228 return None;
229 }
230 buf.truncate(shared as usize);
231 buf.extend_from_slice(&bytes[start..end]);
232 Some(end)
233}
234
235/// Decode a run's restart (full-term) entry at `off` into `buf`.
236fn run_entry_into(bytes: &[u8], off: usize, buf: &mut Vec<u8>) -> Option<usize> {
237 buf.clear(); // a restart entry stands alone; stale prefix bytes must not leak
238 entry_into(bytes, off, buf)
239}
240
241/// Resolve `id` (1-based) to its term using cached metadata. Returns `None` on
242/// any inconsistency in untrusted metadata/bytes rather than panicking.
243pub fn section_term(bytes: &[u8], meta: &SectionMeta, id: u32) -> Option<String> {
244 if id == ABSENT || id > meta.term_count {
245 return None;
246 }
247 let idx = (id - 1) as usize;
248 let run = idx / meta.restart_interval as usize;
249 let steps = idx % meta.restart_interval as usize;
250 let mut buf = Vec::new();
251 let mut pos = run_entry_into(bytes, *meta.restart_offsets.get(run)? as usize, &mut buf)?;
252 for _ in 0..steps {
253 pos = entry_into(bytes, pos, &mut buf)?;
254 }
255 Some(String::from_utf8_lossy(&buf).into_owned())
256}
257
258/// Resolve `term` to its ID using cached metadata (a bytewise-ordered section).
259pub fn section_id(bytes: &[u8], meta: &SectionMeta, term: &str) -> Option<u32> {
260 section_id_ordered(bytes, meta, term, TermOrder::Bytewise)
261}
262
263/// [`section_id`] for a section whose terms are sorted in `order`.
264pub fn section_id_ordered(
265 bytes: &[u8],
266 meta: &SectionMeta,
267 term: &str,
268 order: TermOrder,
269) -> Option<u32> {
270 let probe = order.probe(term.as_bytes());
271 let mut buf = Vec::new();
272 // Binary search restart runs by their first (full) term.
273 let mut lo = 0usize;
274 let mut hi = meta.restart_offsets.len();
275 while lo < hi {
276 let mid = (lo + hi) / 2;
277 run_entry_into(bytes, meta.restart_offsets[mid] as usize, &mut buf)?;
278 if probe.cmp_stored(&buf) != std::cmp::Ordering::Greater {
279 lo = mid + 1;
280 } else {
281 hi = mid;
282 }
283 }
284 if lo == 0 {
285 return None; // smaller than every term
286 }
287 let run = lo - 1;
288 let mut pos = run_entry_into(bytes, meta.restart_offsets[run] as usize, &mut buf)?;
289 let base_id = (run * meta.restart_interval as usize) as u32 + 1;
290 // saturating_sub: corrupt metadata where run*interval > term_count must not
291 // underflow-panic.
292 let run_len = meta.restart_interval.min(
293 meta.term_count
294 .saturating_sub(run as u32 * meta.restart_interval),
295 );
296 for step in 0..run_len {
297 match probe.cmp_stored(&buf) {
298 std::cmp::Ordering::Equal => return Some(base_id + step),
299 std::cmp::Ordering::Greater => return None,
300 std::cmp::Ordering::Less => {}
301 }
302 if step + 1 < run_len {
303 pos = entry_into(bytes, pos, &mut buf)?;
304 }
305 }
306 None
307}
308
309// --- chunked sections ---------------------------------------------------------
310//
311// A section's body is split (on run boundaries) into **chunks** that are
312// compressed and fetched independently (format v0.2), so a remote client
313// resolves a term with one chunk fault instead of downloading the whole
314// section. Local sections are the degenerate case: one pre-set chunk holding
315// the entire serialized section — a single code path serves both.
316
317/// Fetches one chunk's decompressed body slice on demand (`None` = the fetch
318/// failed; the section records it and the lookup misses — callers over remote
319/// data must check [`ChunkedSection::load_incomplete`] after evaluating).
320pub type ChunkLoader = Box<dyn Fn(usize) -> Option<Vec<u8>> + Send + Sync>;
321
322/// Fetches **many** chunks in one round trip: given ascending chunk indices,
323/// returns each chunk's decompressed body in the same order. The ranged
324/// reader implements this by coalescing byte-adjacent chunk ranges into
325/// single range reads — a full-dictionary sweep (export, dump) costs a few
326/// requests per section instead of one per chunk. `None` = the batch failed;
327/// callers fall back to the per-chunk [`ChunkLoader`].
328pub type ChunkBulkLoader = Box<dyn Fn(&[usize]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
329
330/// Fetches chunks of **several sections** of one dictionary in one round trip:
331/// given `(section, chunk)` pairs, returns each chunk's decompressed body in
332/// the same order. Decoding a result touches every section (an IRI subject, a
333/// literal object, a predicate), and faulting them section by section cost one
334/// round trip per section on a remote file. The ranged reader issues the whole
335/// batch through one [`crate::RangeReader::read_many`]. `None` = the batch
336/// failed; the chunks stay unloaded for the per-chunk [`ChunkLoader`].
337pub type MultiChunkBulkLoader = Box<dyn Fn(&[(u8, usize)]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
338
339/// One chunk: a run-aligned slice of the section body. `body_start` is the
340/// offset (in the section's coordinate space — the same space
341/// [`SectionMeta::restart_offsets`] uses) where `data[0]` sits.
342pub struct SectionChunk {
343 first_run: usize,
344 /// The chunk's **routing key** — the only thing the chunk-level binary
345 /// search in [`ChunkedSection::id`] compares against. It is a *separator*,
346 /// **not a term**:
347 ///
348 /// ```text
349 /// last_term(chunk i-1) < key(i) <= first_term(chunk i)
350 /// ```
351 ///
352 /// and chunk 0's key is empty (`b"" <= anything`, and nothing routes before
353 /// chunk 0 anyway). Writers store the *shortest* such string — see
354 /// [`shortest_separator`] — which is why a file's chunk directory is a few
355 /// bytes per chunk instead of a full copy of every boundary term.
356 ///
357 /// Files written before that change carry the boundary term verbatim; the
358 /// verbatim first term is the degenerate separator, so both read the same
359 /// way and no version check is needed. Nothing may reconstruct a term from
360 /// this field, compare it for equality with a term, or report it as one: a
361 /// key that is *not* a separator (a truncation, a hash) mis-routes silently
362 /// — `term(id)` and every dump keep working because they route by
363 /// `first_run`, and only `id(term)` lies.
364 ///
365 /// Unused (empty) for the single local chunk.
366 key: Vec<u8>,
367 body_start: u64,
368}
369
370impl SectionChunk {
371 /// A chunk descriptor: routing metadata only. The decompressed body (and
372 /// its derived run-offset table) lives in the section's [`ChunkCache`],
373 /// keyed by `(section_index, chunk_index)`, faulted in on first touch and
374 /// evictable — not held here. `key` is the routing separator, **not a
375 /// term** (see the `key` field).
376 pub fn new(first_run: usize, key: Vec<u8>, body_start: u64) -> Self {
377 SectionChunk {
378 first_run,
379 key,
380 body_start,
381 }
382 }
383}
384
385/// Scan a chunk's decompressed body for the byte offset of each run start (see
386/// [`SectionChunk::run_offsets`]). O(terms-in-chunk), run once per faulted chunk.
387fn chunk_run_offsets(data: &[u8], restart_interval: usize) -> Vec<usize> {
388 let mut offs = vec![0usize];
389 let mut pos = 0usize;
390 let mut buf = Vec::new();
391 let mut count = 0usize;
392 while pos < data.len() {
393 let Some(next) = entry_into(data, pos, &mut buf) else {
394 break;
395 };
396 count += 1;
397 pos = next;
398 if pos < data.len() && count.is_multiple_of(restart_interval) {
399 offs.push(pos);
400 }
401 }
402 offs
403}
404
405/// The first (full) term of the run starting at `off`, as raw bytes. `None`
406/// on malformed bytes.
407pub fn run_first_term(bytes: &[u8], off: usize) -> Option<Vec<u8>> {
408 let mut buf = Vec::new();
409 run_entry_into(bytes, off, &mut buf)?;
410 Some(buf)
411}
412
413/// The LAST term encoded in `bytes[run_off..end]`, where `run_off` is a run
414/// (restart) boundary and `end` is the end of that run's chunk. Walks the
415/// front-coded entries forward, so it decodes at most `restart_interval` of
416/// them. `None` on malformed bytes.
417///
418/// Writers use it for one thing: the previous chunk's last term, the lower
419/// bound of the next chunk's [`shortest_separator`].
420pub fn run_last_term(bytes: &[u8], run_off: usize, end: usize) -> Option<Vec<u8>> {
421 let lim = bytes.get(..end)?;
422 let mut buf = Vec::new();
423 let mut pos = run_entry_into(lim, run_off, &mut buf)?;
424 while pos < end {
425 pos = entry_into(lim, pos, &mut buf)?;
426 }
427 Some(buf)
428}
429
430/// The **shortest** byte string `s` with `prev_last < s <= first`: `first`
431/// truncated one byte past where it first differs from `prev_last`.
432///
433/// This is the routing key a chunk directory stores (`SectionChunk::key`).
434/// `first` is the chunk's first term and `prev_last`
435/// the previous chunk's last term, so `prev_last < first` holds for any sorted
436/// section; if it does not (malformed input), the full `first` is returned —
437/// always a valid separator, just not a short one.
438///
439/// It really is the shortest. Let `k` be the length of the common prefix of
440/// `prev_last` and `first`; the result has length `k + 1`. No shorter `s`
441/// exists: any `s` with `|s| <= k` shares that prefix's bytes with both, so it
442/// is either a prefix of `prev_last` (hence `<= prev_last`), or it first
443/// differs from the shared prefix — below it, making `s < prev_last`, or above
444/// it, making `s > first`. Every case is outside `(prev_last, first]`.
445pub fn shortest_separator(prev_last: &[u8], first: &[u8]) -> Vec<u8> {
446 let shared = prev_last
447 .iter()
448 .zip(first)
449 .take_while(|(a, b)| a == b)
450 .count();
451 if shared >= first.len() {
452 // `first` is a prefix of `prev_last`, i.e. `first <= prev_last`: not a
453 // sorted pair. Keep the whole term.
454 return first.to_vec();
455 }
456 first[..shared + 1].to_vec()
457}
458
459/// One leaf of a dictionary section's chunk directory, as the `0x06` root
460/// describes it.
461#[derive(Debug, Clone)]
462pub struct ChunkLeaf {
463 /// Index of the leaf's first chunk in the section.
464 pub first: usize,
465 /// Chunks in the leaf.
466 pub n: usize,
467 /// First run of the leaf's first chunk.
468 pub first_run: usize,
469 /// Routing key of the leaf's first chunk (a separator; empty for chunk 0).
470 pub key: Vec<u8>,
471 /// Absolute range of the stored leaf block.
472 pub leaf: (u64, u64),
473 /// Absolute offset of the leaf's first chunk.
474 pub chunk_base: u64,
475}
476
477/// A chunk directory whose entries live in leaf blocks faulted on demand and
478/// kept for the session (format `0x06`, SPEC.md §4.4). `term → id` narrows by
479/// the leaves' first keys, `id → term` by their first runs, so either faults
480/// one leaf.
481/// A faulted dictionary leaf: each chunk's entry, data offset and length.
482type ChunkCell = std::sync::OnceLock<Box<[(SectionChunk, u64, u64)]>>;
483
484pub struct LeafedChunks {
485 leaves: Vec<ChunkLeaf>,
486 cells: Vec<ChunkCell>,
487 total: usize,
488 fetch: crate::index::LeafFetch,
489 codec: u8,
490 /// Decompression bound on a leaf.
491 max_block: u64,
492 failed: AtomicBool,
493}
494
495impl crate::index::LeafDir for LeafedChunks {
496 fn missing_leaf(&self, li: usize) -> Option<(u64, u64)> {
497 (li < self.cells.len() && self.cells[li].get().is_none()).then(|| self.leaves[li].leaf)
498 }
499
500 fn install_leaf(&self, li: usize, stored: &[u8]) {
501 match self.decode_leaf(li, stored) {
502 Some(v) => {
503 let _ = self.cells[li].set(v);
504 }
505 None => self.failed.store(true, Ordering::Relaxed),
506 }
507 }
508
509 fn fail_leaves(&self) {
510 self.failed.store(true, Ordering::Relaxed);
511 }
512
513 fn leaf_fetch(&self) -> &crate::index::LeafFetch {
514 &self.fetch
515 }
516}
517
518impl LeafedChunks {
519 /// Bound every leaf decompression at `max` bytes (from the `0x06` root).
520 pub fn with_max_block(mut self, max: u64) -> Self {
521 self.max_block = max;
522 self
523 }
524
525 /// A leafed directory of `total` chunks.
526 pub fn new(
527 leaves: Vec<ChunkLeaf>,
528 total: usize,
529 fetch: crate::index::LeafFetch,
530 codec: u8,
531 ) -> Self {
532 let cells = leaves.iter().map(|_| std::sync::OnceLock::new()).collect();
533 LeafedChunks {
534 leaves,
535 cells,
536 total,
537 fetch,
538 codec,
539 max_block: u64::MAX,
540 failed: AtomicBool::new(false),
541 }
542 }
543
544 fn leaf_of(&self, ci: usize) -> usize {
545 self.leaves
546 .partition_point(|l| l.first <= ci)
547 .saturating_sub(1)
548 }
549
550 fn decode_leaf(&self, li: usize, stored: &[u8]) -> Option<Box<[(SectionChunk, u64, u64)]>> {
551 let l = &self.leaves[li];
552 let raw = crate::file::decompress_bounded(self.codec, stored, self.max_block).ok()?;
553 let ents = crate::v06::decode_chunk_leaf(&raw, l.n).ok()?;
554 let mut at = l.chunk_base;
555 let mut out = Vec::with_capacity(ents.len());
556 for e in ents {
557 out.push((SectionChunk::new(e.first_run, e.key, 0), at, e.clen));
558 at = at.checked_add(e.clen)?;
559 }
560 Some(out.into_boxed_slice())
561 }
562
563 /// Fault every not-yet-resident leaf of `lis` in one batched read.
564 pub fn ensure_leaves(&self, lis: &[usize]) {
565 crate::index::ensure_leaves_across(&[(self, lis)]);
566 }
567
568 /// The leaves holding chunks `cis`.
569 pub fn leaves_of(&self, cis: &[usize]) -> Vec<usize> {
570 let mut v: Vec<usize> = cis
571 .iter()
572 .filter(|&&ci| ci < self.total)
573 .map(|&ci| self.leaf_of(ci))
574 .collect();
575 v.sort_unstable();
576 v.dedup();
577 v
578 }
579
580 fn entry(&self, ci: usize) -> Option<&(SectionChunk, u64, u64)> {
581 if ci >= self.total {
582 return None;
583 }
584 let li = self.leaf_of(ci);
585 if self.cells[li].get().is_none() {
586 self.ensure_leaves(&[li]);
587 }
588 self.cells[li].get()?.get(ci - self.leaves[li].first)
589 }
590
591 /// Chunk `ci`'s absolute stored range, faulting its leaf.
592 pub fn range(&self, ci: usize) -> Option<(u64, u64)> {
593 self.entry(ci).map(|(_, off, len)| (*off, *len))
594 }
595
596 /// The leaf whose runs hold `run`, by first run.
597 pub fn leaf_of_run(&self, run: usize) -> Option<usize> {
598 self.leaves
599 .partition_point(|l| l.first_run <= run)
600 .checked_sub(1)
601 }
602
603 /// The leaf whose keys route `term`, by first key.
604 pub fn leaf_of_term(&self, probe: &crate::term_order::Probe) -> Option<usize> {
605 self.leaves
606 .partition_point(|l| probe.cmp_stored(&l.key) != std::cmp::Ordering::Greater)
607 .checked_sub(1)
608 }
609
610 /// Did a leaf fault fail?
611 pub fn load_failed(&self) -> bool {
612 self.failed.load(Ordering::Relaxed)
613 }
614
615 fn resident_bytes(&self) -> u64 {
616 self.cells
617 .iter()
618 .filter_map(|c| c.get())
619 .flat_map(|v| v.iter())
620 .map(|(c, _, _)| (std::mem::size_of::<SectionChunk>() + 16 + c.key.capacity()) as u64)
621 .sum::<u64>()
622 + self
623 .leaves
624 .iter()
625 .map(|l| (std::mem::size_of::<ChunkLeaf>() + l.key.capacity()) as u64)
626 .sum::<u64>()
627 }
628}
629
630/// A dictionary section's chunk directory: resident in full (`0x05`), or two
631/// levels with leaves faulted on demand (`0x06`).
632pub enum ChunkDir {
633 /// Every chunk descriptor resident.
634 Full(Vec<SectionChunk>),
635 /// Root resident, leaves on demand.
636 Leafed(Arc<LeafedChunks>),
637}
638
639impl ChunkDir {
640 /// Number of chunks.
641 pub fn len(&self) -> usize {
642 match self {
643 ChunkDir::Full(v) => v.len(),
644 ChunkDir::Leafed(l) => l.total,
645 }
646 }
647
648 /// No chunks?
649 pub fn is_empty(&self) -> bool {
650 self.len() == 0
651 }
652
653 /// Chunk `ci`'s descriptor (faulting its leaf).
654 pub fn get(&self, ci: usize) -> Option<&SectionChunk> {
655 match self {
656 ChunkDir::Full(v) => v.get(ci),
657 ChunkDir::Leafed(l) => l.entry(ci).map(|(c, _, _)| c),
658 }
659 }
660
661 /// First run of chunk `ci + 1`, from the next leaf's root entry when `ci`
662 /// is a leaf's last chunk (no fault).
663 fn next_first_run(&self, ci: usize) -> Option<usize> {
664 match self {
665 ChunkDir::Full(v) => v.get(ci + 1).map(|c| c.first_run),
666 ChunkDir::Leafed(l) => {
667 if ci + 1 >= l.total {
668 return None;
669 }
670 let li = l.leaf_of(ci + 1);
671 if l.leaves[li].first == ci + 1 {
672 Some(l.leaves[li].first_run)
673 } else {
674 l.entry(ci + 1).map(|(c, _, _)| c.first_run)
675 }
676 }
677 }
678 }
679
680 /// The chunk holding `run`.
681 fn chunk_of_run(&self, run: usize) -> Option<usize> {
682 match self {
683 ChunkDir::Full(v) => v.partition_point(|c| c.first_run <= run).checked_sub(1),
684 ChunkDir::Leafed(l) => {
685 let li = l.leaf_of_run(run)?;
686 l.ensure_leaves(&[li]);
687 let cell = l.cells[li].get()?;
688 let j = cell.partition_point(|(c, _, _)| c.first_run <= run);
689 Some(l.leaves[li].first + j.checked_sub(1)?)
690 }
691 }
692 }
693
694 /// The chunk whose routing key range holds `term`.
695 fn chunk_for_term(&self, probe: &crate::term_order::Probe) -> Option<usize> {
696 use std::cmp::Ordering::Greater;
697 match self {
698 ChunkDir::Full(v) => match v.len() {
699 0 => None,
700 1 => Some(0),
701 _ => v
702 .partition_point(|c| probe.cmp_stored(&c.key) != Greater)
703 .checked_sub(1),
704 },
705 ChunkDir::Leafed(l) => {
706 if l.total == 0 {
707 return None;
708 }
709 let li = l.leaf_of_term(probe)?;
710 l.ensure_leaves(&[li]);
711 let cell = l.cells[li].get()?;
712 let j = cell.partition_point(|(c, _, _)| probe.cmp_stored(&c.key) != Greater);
713 // The leaf's first key routed here, so its first chunk is a
714 // candidate even when its own (equal) key compares <=.
715 Some(l.leaves[li].first + j.saturating_sub(1))
716 }
717 }
718 }
719
720 fn load_failed(&self) -> bool {
721 matches!(self, ChunkDir::Leafed(l) if l.load_failed())
722 }
723
724 fn directory_bytes(&self) -> u64 {
725 match self {
726 ChunkDir::Full(v) => {
727 v.len() as u64 * std::mem::size_of::<SectionChunk>() as u64
728 + v.iter().map(|c| c.key.capacity() as u64).sum::<u64>()
729 }
730 ChunkDir::Leafed(l) => l.resident_bytes(),
731 }
732 }
733}
734
735/// A dictionary section whose body is served chunk-by-chunk: metadata + chunk
736/// directory always present, chunk bytes local or faulted in on first touch.
737pub struct ChunkedSection {
738 meta: SectionMeta,
739 chunks: ChunkDir,
740 loader: Option<ChunkLoader>,
741 bulk: Option<ChunkBulkLoader>,
742 failed: AtomicBool,
743 /// Decompressed chunk bodies (and their derived run tables) live here, keyed
744 /// by `(section_index, chunk_index)`, faulted in on first touch and
745 /// evictable. Shared across a [`Dictionary`]'s four sections. Phase 0 caps
746 /// it at unlimited, so residency is identical to the old per-chunk
747 /// `OnceLock`s.
748 cache: Arc<ChunkCache>,
749 /// This section's discriminant in the shared cache's key space (0 shared,
750 /// 1 subject-only, 2 object-only, 3 predicates).
751 section_index: u8,
752 /// How the section's terms are ordered (`term -> id` searches with it).
753 order: TermOrder,
754 /// Terms per group, for a [`TermOrder::Sparql`] section: from the file's
755 /// root when it has them, else found on first use.
756 groups: std::sync::OnceLock<Option<GroupCounts>>,
757 /// Chunk ranges `(first chunk, chunks)` whose bodies the file does not
758 /// store (a derived IRI family, `crate::derived`): the term of an id in
759 /// them is rebuilt by the dictionary from the index, never read here.
760 elided: Vec<(usize, usize)>,
761}
762
763/// What looking a term up in one section found.
764#[derive(Debug, Clone, Copy, PartialEq, Eq)]
765pub enum Lookup {
766 /// The term's section-local id.
767 Found(u32),
768 /// The term is not in the section.
769 Absent,
770 /// The term routes to a chunk the file does not store: it is there only if
771 /// some id of `first..=last` (section-local) derives to it.
772 Elided {
773 /// First section-local id of the chunk.
774 first: u32,
775 /// Last section-local id of the chunk.
776 last: u32,
777 },
778}
779
780/// How many sections a thread keeps read-ahead state for.
781const RA_SLOTS: usize = 8;
782
783thread_local! {
784 /// Read-ahead on sequential chunk faults, per thread and section: the
785 /// section (its cache and index), the chunk whose miss would continue the
786 /// thread's run of misses plus one (0 = none), and the window the next
787 /// sequential miss fetches (doubling up to [`READAHEAD_MAX_CHUNKS`]; back
788 /// to 1 on a non-sequential miss). Per thread, because a run is one
789 /// reader's: several threads walking different parts of a section each
790 /// fault in order, and one shared state saw no order in them.
791 static READ_AHEAD: std::cell::RefCell<[(usize, u64, u32); RA_SLOTS]> =
792 const { std::cell::RefCell::new([(0, 0, 1); RA_SLOTS]) };
793}
794
795/// The chunk a caller's last [`ChunkedSection::term_held`] decoded from.
796#[derive(Default)]
797pub struct ChunkHold(Option<(usize, Arc<CacheEntry>)>);
798
799/// Terms decoded from a dictionary section by [`ChunkedSection::term`], process-wide.
800static TERMS_DECODED: AtomicU64 = AtomicU64::new(0);
801
802/// How many terms have been decoded from any dictionary so far (every
803/// `term(id)` of a section, one per id, memo hits excluded). A counter for
804/// tests and diagnostics: a query's decode cost is the difference around it.
805pub fn terms_decoded() -> u64 {
806 TERMS_DECODED.load(Ordering::Relaxed)
807}
808
809/// The most chunks one sequential read-ahead fetches (16 × ~64 KiB ≈ 1 MiB).
810pub const READAHEAD_MAX_CHUNKS: u32 = 16;
811
812impl ChunkedSection {
813 /// A local section: the whole serialized section (header + body) as one
814 /// resident chunk at coordinate 0, so the absolute restart offsets index it
815 /// directly. Malformed bytes degrade to an empty section (no panics on
816 /// untrusted files), matching the previous reader behavior. The body is
817 /// stored in `cache` at `(section_index, 0)` (unlimited cap ⇒ resident for
818 /// the section's lifetime, exactly as before).
819 pub fn local(section_bytes: Vec<u8>, cache: Arc<ChunkCache>, section_index: u8) -> Self {
820 let meta = parse_meta(§ion_bytes).unwrap_or(SectionMeta {
821 term_count: 0,
822 restart_interval: 1,
823 restart_offsets: Vec::new(),
824 });
825 cache.insert((section_index, 0), Arc::from(section_bytes));
826 ChunkedSection {
827 meta,
828 chunks: ChunkDir::Full(vec![SectionChunk::new(0, Vec::new(), 0)]),
829 loader: None,
830 bulk: None,
831 failed: AtomicBool::new(false),
832 cache,
833 section_index,
834 order: TermOrder::Bytewise,
835 groups: std::sync::OnceLock::new(),
836 elided: Vec::new(),
837 }
838 }
839
840 /// A section from parsed parts: metadata + chunk list, with an optional
841 /// loader for non-resident chunks (the remote lazy-open path) — resident
842 /// chunk lists (a locally-decoded chunked section) supply their bodies
843 /// through `resident` instead.
844 pub fn from_parts(
845 meta: SectionMeta,
846 chunks: Vec<SectionChunk>,
847 loader: Option<ChunkLoader>,
848 cache: Arc<ChunkCache>,
849 section_index: u8,
850 ) -> Self {
851 ChunkedSection {
852 meta,
853 chunks: ChunkDir::Full(chunks),
854 loader,
855 bulk: None,
856 failed: AtomicBool::new(false),
857 cache,
858 section_index,
859 order: TermOrder::Bytewise,
860 groups: std::sync::OnceLock::new(),
861 elided: Vec::new(),
862 }
863 }
864
865 /// A section whose chunk bodies are already decoded (the local chunked-file
866 /// open path): the descriptors and their bodies arrive together and the
867 /// bodies are seeded into the cache. No loader — every chunk is resident.
868 pub fn resident(
869 meta: SectionMeta,
870 chunks: Vec<(SectionChunk, Vec<u8>)>,
871 cache: Arc<ChunkCache>,
872 section_index: u8,
873 ) -> Self {
874 let descriptors = chunks
875 .into_iter()
876 .enumerate()
877 .map(|(ci, (chunk, body))| {
878 cache.insert((section_index, ci as u32), Arc::from(body));
879 chunk
880 })
881 .collect();
882 ChunkedSection {
883 meta,
884 chunks: ChunkDir::Full(descriptors),
885 loader: None,
886 bulk: None,
887 failed: AtomicBool::new(false),
888 cache,
889 section_index,
890 order: TermOrder::Bytewise,
891 groups: std::sync::OnceLock::new(),
892 elided: Vec::new(),
893 }
894 }
895
896 /// A `0x06` section: its chunk directory two-level (leaves faulted on
897 /// demand), chunk bodies faulted through `loader`.
898 pub fn leafed(
899 meta: SectionMeta,
900 dir: Arc<LeafedChunks>,
901 loader: ChunkLoader,
902 cache: Arc<ChunkCache>,
903 section_index: u8,
904 ) -> Self {
905 ChunkedSection {
906 meta,
907 chunks: ChunkDir::Leafed(dir),
908 loader: Some(loader),
909 bulk: None,
910 failed: AtomicBool::new(false),
911 cache,
912 section_index,
913 order: TermOrder::Bytewise,
914 groups: std::sync::OnceLock::new(),
915 elided: Vec::new(),
916 }
917 }
918
919 /// The chunk directory.
920 pub fn chunk_dir(&self) -> &ChunkDir {
921 &self.chunks
922 }
923
924 /// Say how this section's terms are ordered (the format generation does;
925 /// the constructors assume [`TermOrder::Bytewise`]).
926 pub fn with_order(mut self, order: TermOrder) -> Self {
927 self.order = order;
928 self
929 }
930
931 /// Hand over the section's per-group term counts, as a `0x08` root holds
932 /// them, so [`Self::groups`] reads no chunk.
933 pub fn with_groups(self, counts: GroupCounts) -> Self {
934 let _ = self.groups.set(Some(counts));
935 self
936 }
937
938 /// Say which chunk ranges the file does not store (`(first, count)`, sorted,
939 /// disjoint): derived IRI families. See [`Self::is_elided`].
940 pub fn with_elided(mut self, ranges: Vec<(usize, usize)>) -> Self {
941 self.elided = ranges;
942 self
943 }
944
945 /// Is chunk `ci` one the file stores no body for?
946 pub fn is_elided(&self, ci: usize) -> bool {
947 let at = self.elided.partition_point(|&(first, _)| first <= ci);
948 at > 0 && ci < self.elided[at - 1].0 + self.elided[at - 1].1
949 }
950
951 /// Does the section have chunks with no stored body?
952 pub fn has_elided(&self) -> bool {
953 !self.elided.is_empty()
954 }
955
956 /// Is the section-local id `id` in a chunk with no stored body?
957 pub fn id_is_elided(&self, id: u32) -> bool {
958 !self.elided.is_empty() && self.chunk_of_id(id).is_some_and(|ci| self.is_elided(ci))
959 }
960
961 /// First and last section-local id of chunk `ci`.
962 pub fn chunk_ids(&self, ci: usize) -> Option<(u32, u32)> {
963 let ri = self.meta.restart_interval as usize;
964 let tc = self.meta.term_count as u64;
965 let first = (self.chunks.get(ci)?.first_run.checked_mul(ri)? as u64 + 1).min(tc + 1);
966 let last = match self.chunks.next_first_run(ci) {
967 Some(next) => (next.checked_mul(ri)? as u64).min(tc),
968 None => tc,
969 };
970 (first <= last).then_some((u32::try_from(first).ok()?, u32::try_from(last).ok()?))
971 }
972
973 /// The order of this section's terms.
974 pub fn order(&self) -> TermOrder {
975 self.order
976 }
977
978 /// How many terms are in each group; `None` unless the section is
979 /// [`TermOrder::Sparql`] (or a chunk could not be read). From the root
980 /// when it was given, else three binary searches over the term ids, cached
981 /// once found.
982 pub fn groups(&self) -> Option<GroupCounts> {
983 if self.order != TermOrder::Sparql {
984 return None;
985 }
986 if let Some(g) = self.groups.get() {
987 return *g;
988 }
989 let found = self.find_groups();
990 if found.is_some() {
991 let _ = self.groups.set(found);
992 }
993 found
994 }
995
996 /// The first id (1-based, `term_count + 1` if none) whose group is at least `g`.
997 fn first_in_group_from(&self, g: u8) -> Option<u32> {
998 let n = self.meta.term_count;
999 let (mut lo, mut hi) = (1u32, n.checked_add(1)?);
1000 while lo < hi {
1001 let mid = lo + (hi - lo) / 2;
1002 let t = self.term(mid)?;
1003 if crate::term_order::group(t.as_bytes()) >= g {
1004 hi = mid;
1005 } else {
1006 lo = mid + 1;
1007 }
1008 }
1009 Some(lo)
1010 }
1011
1012 fn find_groups(&self) -> Option<GroupCounts> {
1013 use crate::term_order::GROUPS;
1014 let n = self.meta.term_count;
1015 let mut starts = [0u32; GROUPS + 1];
1016 for g in 1..GROUPS as u8 {
1017 starts[g as usize] = self.first_in_group_from(g)? - 1;
1018 }
1019 starts[GROUPS] = n;
1020 let mut c = GroupCounts::default();
1021 for g in 0..GROUPS {
1022 c.0[g] = starts[g + 1].saturating_sub(starts[g]);
1023 }
1024 Some(c)
1025 }
1026
1027 /// Attach a batched chunk fetcher (see [`ChunkBulkLoader`]): full-section
1028 /// sweeps ([`prefetch_all`](Self::prefetch_all)) go through it instead of
1029 /// faulting chunk by chunk.
1030 pub fn with_bulk_loader(mut self, bulk: ChunkBulkLoader) -> Self {
1031 self.bulk = Some(bulk);
1032 self
1033 }
1034
1035 /// Batch-fault every unloaded chunk through the bulk loader, if one is
1036 /// attached and at least two chunks are missing. Callers about to sweep
1037 /// the whole section (export/dump term resolution) call this once; a
1038 /// failed batch leaves the chunks unloaded for the per-chunk loader to
1039 /// retry (and record failures) lookup by lookup.
1040 pub fn prefetch_all(&self) {
1041 self.prefetch_chunks(&(0..self.chunks.len()).collect::<Vec<_>>());
1042 }
1043
1044 /// Batch-fault a *specific* set of chunks (the subset a bounded query's
1045 /// output touches) through the bulk loader, coalescing byte-adjacent ranges
1046 /// into single reads. `cis` should be ascending and deduped; chunks already
1047 /// resident are skipped. Like [`prefetch_all`](Self::prefetch_all) a single
1048 /// missing chunk is left for the per-chunk loader, and a failed batch leaves
1049 /// the chunks unloaded for that loader to retry (and record failures).
1050 pub fn prefetch_chunks(&self, cis: &[usize]) {
1051 let Some(bulk) = &self.bulk else { return };
1052 let missing: Vec<usize> = cis
1053 .iter()
1054 .copied()
1055 .filter(|&ci| {
1056 ci < self.chunks.len()
1057 && !self.is_elided(ci)
1058 && !self.cache.contains((self.section_index, ci as u32))
1059 })
1060 .collect();
1061 if missing.len() < 2 {
1062 return;
1063 }
1064 if let Some(bodies) = bulk(&missing) {
1065 if bodies.len() == missing.len() {
1066 for (&ci, body) in missing.iter().zip(bodies) {
1067 self.cache
1068 .insert((self.section_index, ci as u32), Arc::from(body));
1069 }
1070 }
1071 }
1072 }
1073
1074 /// The chunks of `cis` a batch would still have to fetch: in range, not
1075 /// resident, and only on a section that faults chunks in (a local section
1076 /// has none to fetch). Order is kept.
1077 pub(crate) fn missing_chunks(&self, cis: &[usize]) -> Vec<usize> {
1078 if self.loader.is_none() {
1079 return Vec::new();
1080 }
1081 cis.iter()
1082 .copied()
1083 .filter(|&ci| {
1084 ci < self.chunks.len()
1085 && !self.is_elided(ci)
1086 && !self.cache.contains((self.section_index, ci as u32))
1087 })
1088 .collect()
1089 }
1090
1091 /// Seed one batch-fetched chunk body into the cache.
1092 pub(crate) fn seed_chunk(&self, ci: usize, body: Vec<u8>) {
1093 self.cache
1094 .insert((self.section_index, ci as u32), Arc::from(body));
1095 }
1096
1097 pub fn meta(&self) -> &SectionMeta {
1098 &self.meta
1099 }
1100
1101 pub fn term_count(&self) -> u32 {
1102 self.meta.term_count
1103 }
1104
1105 /// The shared chunk cache backing this section (all four sections of a
1106 /// [`crate::dictionary::Dictionary`] share one instance) — the handle the
1107 /// bounded-export budget (phase 2) sets a byte cap on.
1108 pub(crate) fn cache(&self) -> &Arc<ChunkCache> {
1109 &self.cache
1110 }
1111
1112 /// Heap bytes this section holds for as long as it is open, independent
1113 /// of the chunk cache: the chunk directory (one descriptor plus its
1114 /// routing key per chunk), the per-chunk byte ranges the ranged loaders
1115 /// share, and any eager restart-offset table. Grows with the chunk count,
1116 /// never with what a dump touches.
1117 pub fn directory_bytes(&self) -> u64 {
1118 let n = self.chunks.len() as u64;
1119 let ranges = if self.loader.is_some() && matches!(self.chunks, ChunkDir::Full(_)) {
1120 16 * n
1121 } else {
1122 0
1123 };
1124 self.chunks.directory_bytes() + ranges + self.meta.restart_offsets.capacity() as u64 * 8
1125 }
1126
1127 /// Did any chunk fetch fail since this section was opened — or since the
1128 /// last [`reset_load_failure`](Self::reset_load_failure)?
1129 pub fn load_incomplete(&self) -> bool {
1130 self.failed.load(Ordering::Relaxed) || self.chunks.load_failed()
1131 }
1132
1133 /// Forget recorded fetch failures (see `GraphIndex::reset_load_failure` —
1134 /// the per-query reset for resident sessions). Failed chunks were never
1135 /// cached, so the next resolution retries them.
1136 pub fn reset_load_failure(&self) {
1137 self.failed.store(false, Ordering::Relaxed);
1138 }
1139
1140 /// The cache entry for chunk `ci`, faulting its body in through the loader
1141 /// on a miss. Returns an owned [`CacheEntry`] handle (an `Arc`) the caller
1142 /// holds for the duration of one decode — valid even if a later eviction
1143 /// drops the map slot (the handout invariant).
1144 ///
1145 /// A FAILED fetch records the failure and caches nothing (returns `None`),
1146 /// so a later resolution retries the chunk — a transient network error must
1147 /// not permanently poison a resident session. A local section with no
1148 /// loader returns an empty body for a missing chunk, matching the old
1149 /// `get_or_init(Vec::new)` behavior.
1150 fn chunk_entry(&self, ci: usize) -> Option<Arc<CacheEntry>> {
1151 if self.is_elided(ci) {
1152 return None;
1153 }
1154 let key = (self.section_index, ci as u32);
1155 if let Some(e) = self.cache.get(key) {
1156 return Some(e);
1157 }
1158 match &self.loader {
1159 Some(load) => {
1160 // Sequential misses (a walk over ascending ids or terms) read
1161 // ahead: the second miss in a row fetches 2 chunks in one
1162 // batch, then 4, 8, … up to READAHEAD_MAX_CHUNKS; any other
1163 // miss resets the window. Scattered lookups pay nothing extra.
1164 if self.bulk.is_some() {
1165 // This section, for the thread's read-ahead state.
1166 let me =
1167 (Arc::as_ptr(&self.cache) as usize) ^ (self.section_index as usize + 1);
1168 let total = self.chunks.len();
1169 let end = READ_AHEAD.with(|ra| {
1170 let mut ra = ra.borrow_mut();
1171 let at = match ra.iter().position(|s| s.0 == me) {
1172 Some(at) => at,
1173 None => {
1174 // Take over the slot of the section used
1175 // longest ago: the last one, as slots move
1176 // to the front on use.
1177 ra[RA_SLOTS - 1] = (me, 0, 1);
1178 RA_SLOTS - 1
1179 }
1180 };
1181 let (_, next, window) = ra[at];
1182 let w = if next == ci as u64 + 1 {
1183 (window * 2).min(READAHEAD_MAX_CHUNKS)
1184 } else {
1185 1
1186 };
1187 let end = (ci + w as usize).min(total);
1188 ra[..=at].rotate_right(1);
1189 ra[0] = (me, end as u64 + 1, w);
1190 end
1191 });
1192 if end > ci + 1 {
1193 self.prefetch_chunks(&(ci..end).collect::<Vec<_>>());
1194 if let Some(e) = self.cache.get(key) {
1195 return Some(e);
1196 }
1197 }
1198 }
1199 match load(ci) {
1200 Some(bytes) => Some(self.cache.insert(key, Arc::from(bytes))),
1201 None => {
1202 self.failed.store(true, Ordering::Relaxed);
1203 None
1204 }
1205 }
1206 }
1207 None => Some(self.cache.insert(key, Arc::from(Vec::new()))),
1208 }
1209 }
1210
1211 /// The chunk holding `run` (chunks ascend by `first_run`; the first chunk
1212 /// always starts at run 0).
1213 fn chunk_of_run(&self, run: usize) -> Option<usize> {
1214 self.chunks.chunk_of_run(run)
1215 }
1216
1217 /// The chunk index holding term `id` (1-based, section-local), or `None` if
1218 /// out of range. Mirrors the run→chunk math in [`term`](Self::term) so a
1219 /// caller can group a set of output ids by chunk and batch-prefetch them.
1220 pub fn chunk_of_id(&self, id: u32) -> Option<usize> {
1221 if id == ABSENT || id > self.meta.term_count {
1222 return None;
1223 }
1224 let run = (id - 1) as usize / self.meta.restart_interval as usize;
1225 self.chunk_of_run(run)
1226 }
1227
1228 /// The byte offset (into chunk `ci`'s decompressed body) of `run`.
1229 /// Full/local sections use the section-wide restart table (unchanged
1230 /// behavior); a *lite* remote section (empty `restart_offsets`) derives it
1231 /// from the chunk itself — that per-chunk run table is cached inside the
1232 /// `entry` (evicted with the body), so the open never holds the whole table.
1233 fn run_off_in_chunk(
1234 &self,
1235 ci: usize,
1236 run: usize,
1237 entry: &CacheEntry,
1238 ri: usize,
1239 ) -> Option<usize> {
1240 let chunk = self.chunks.get(ci)?;
1241 if self.meta.restart_offsets.is_empty() {
1242 entry
1243 .runs(|b| chunk_run_offsets(b, ri))
1244 .get(run.checked_sub(chunk.first_run)?)
1245 .copied()
1246 } else {
1247 self.meta
1248 .restart_offsets
1249 .get(run)?
1250 .checked_sub(chunk.body_start)
1251 .map(|o| o as usize)
1252 }
1253 }
1254
1255 /// One past the last run index held by chunk `ci` (its run range is
1256 /// `[first_run, run_end)`).
1257 fn run_end_of_chunk(&self, ci: usize, entry: &CacheEntry, ri: usize) -> usize {
1258 if let Some(next) = self.chunks.next_first_run(ci) {
1259 return next;
1260 }
1261 let first_run = self.chunks.get(ci).map_or(0, |c| c.first_run);
1262 if self.meta.restart_offsets.is_empty() {
1263 first_run + entry.runs(|b| chunk_run_offsets(b, ri)).len()
1264 } else {
1265 self.meta.restart_offsets.len()
1266 }
1267 }
1268
1269 /// Resolve `id` (1-based) to its term. One chunk fault at most.
1270 /// Chunk index holding term `id` — [`term`](Self::term)'s routing without
1271 /// faulting the chunk. `None` for an absent/out-of-range id.
1272 pub(crate) fn chunk_of_term(&self, id: u32) -> Option<usize> {
1273 if id == ABSENT || id > self.meta.term_count {
1274 return None;
1275 }
1276 self.chunk_of_run((id - 1) as usize / self.meta.restart_interval as usize)
1277 }
1278
1279 pub fn term(&self, id: u32) -> Option<String> {
1280 self.term_held(id, &mut ChunkHold::default())
1281 }
1282
1283 /// [`term`](Self::term) for a caller that decodes many ids: `hold` keeps
1284 /// the chunk the last id was in, and an id in the same chunk does not go
1285 /// back to the shared chunk cache. That cache is one lock for the whole
1286 /// dictionary; ids that come out of a scan are mostly neighbours, and a
1287 /// query run on several threads took the lock once per term from every
1288 /// thread. `hold` must only ever be used with this section. The held chunk
1289 /// stays alive (one chunk) even if the cache evicts it meanwhile.
1290 pub fn term_held(&self, id: u32, hold: &mut ChunkHold) -> Option<String> {
1291 if id == ABSENT || id > self.meta.term_count {
1292 return None;
1293 }
1294 TERMS_DECODED.fetch_add(1, Ordering::Relaxed);
1295 let idx = (id - 1) as usize;
1296 let ri = self.meta.restart_interval as usize;
1297 let run = idx / ri;
1298 let steps = idx % ri;
1299 let ci = self.chunk_of_run(run)?;
1300 let entry = match &hold.0 {
1301 Some((held, entry)) if *held == ci => Arc::clone(entry),
1302 _ => {
1303 let entry = self.chunk_entry(ci)?;
1304 hold.0 = Some((ci, Arc::clone(&entry)));
1305 entry
1306 }
1307 };
1308 let bytes: &[u8] = entry.body();
1309 let off = self.run_off_in_chunk(ci, run, &entry, ri)?;
1310 let mut buf = Vec::new();
1311 let mut pos = run_entry_into(bytes, off, &mut buf)?;
1312 for _ in 0..steps {
1313 pos = entry_into(bytes, pos, &mut buf)?;
1314 }
1315 Some(String::from_utf8_lossy(&buf).into_owned())
1316 }
1317
1318 /// Resolve many ids of THIS section in one chunk-ordered, single-pass walk,
1319 /// filling `out[slot]` for each `(id, slot)` in `jobs`.
1320 ///
1321 /// `jobs` is sorted in place by id. Because chunks and runs are *contiguous
1322 /// ascending* id ranges, sorting by id also groups the jobs by chunk and by
1323 /// run — so each chunk is faulted **once** and each run walked **once**
1324 /// forward, picking off every requested id as the decode passes its
1325 /// position. This is where the redundant per-id re-walk that
1326 /// [`term`](Self::term) does (decode from the run start for *every* id)
1327 /// disappears: within a run the walk advances monotonically across all the
1328 /// window's ids that live there.
1329 ///
1330 /// For any id this fills `out[slot]` with exactly what [`term`](Self::term)
1331 /// returns for that id (the same decoded bytes, the same
1332 /// `String::from_utf8_lossy`), and leaves `out[slot]` untouched where
1333 /// `term(id)` is `None` — an absent/out-of-range id, a failed chunk fault,
1334 /// or malformed bytes. Duplicate ids each fill their own slot. It is the
1335 /// batch twin of `term`, used by the export window
1336 /// ([`Dictionary::resolve_window`](crate::dictionary::Dictionary::resolve_window))
1337 /// so a window's scattered object ids touch each chunk once instead of
1338 /// re-faulting and re-walking per row.
1339 ///
1340 /// [`crate::dictionary::Dictionary::resolve_window`]: the sole caller.
1341 pub fn resolve_into(&self, jobs: &mut [(u32, usize)], out: &mut [Option<String>]) {
1342 let ri = self.meta.restart_interval as usize;
1343 if ri == 0 {
1344 return;
1345 }
1346 let tc = self.meta.term_count;
1347 // Sort by id: chunks and runs are contiguous ascending id ranges, so
1348 // this groups jobs by chunk and by run in one pass.
1349 jobs.sort_unstable_by_key(|&(id, _)| id);
1350 // Partition the sorted jobs into contiguous per-chunk segments
1351 // `(chunk, [start, end))`. Every job of a chunk is one contiguous slice
1352 // (chunks are ascending id ranges, `jobs` is id-sorted). Absent (id
1353 // `ABSENT` = 0) and out-of-range (`id > tc`) ids sort to the ends and
1354 // belong to no chunk — they form no segment, so their slots stay None,
1355 // exactly as `term(id) == None` leaves them.
1356 let mut segments: Vec<(usize, usize, usize)> = Vec::new();
1357 let mut i = 0;
1358 while i < jobs.len() {
1359 let id0 = jobs[i].0;
1360 if id0 == ABSENT || id0 > tc {
1361 i += 1;
1362 continue;
1363 }
1364 let Some(ci) = self.chunk_of_run((id0 - 1) as usize / ri) else {
1365 i += 1;
1366 continue;
1367 };
1368 let start = i;
1369 i += 1;
1370 while i < jobs.len() {
1371 let id = jobs[i].0;
1372 if id == ABSENT || id > tc {
1373 i += 1;
1374 continue;
1375 }
1376 if self.chunk_of_run((id - 1) as usize / ri) != Some(ci) {
1377 break; // first id of the next chunk
1378 }
1379 i += 1;
1380 }
1381 segments.push((ci, start, i));
1382 }
1383 if segments.is_empty() {
1384 return;
1385 }
1386 self.decode_and_walk(&segments, jobs, out, ri, tc);
1387 }
1388
1389 /// Fault each segment's chunk and fill its slots. The chunk decodes are
1390 /// independent and CPU-bound (zstd), so with the `parallel` feature a group
1391 /// whose chunks are **not yet resident** is decoded concurrently on a
1392 /// bounded pool before its (serial) fill; without it, one at a time — the
1393 /// exact behavior this refactor extracted. Either way each chunk is faulted
1394 /// once and its slots filled in segment order, so the output is byte-for-byte
1395 /// identical.
1396 ///
1397 /// **Parallel decode runs only where there is decode work.** A group whose
1398 /// chunks are already resident (a generous `--memory-budget-mb` after the
1399 /// window prefetch warmed them, or a chunk re-touched by a later window) is
1400 /// walked serially with **no** parallel dispatch — so the single-pass /
1401 /// large-budget export keeps its serial speed and the rayon fan-out only
1402 /// pays for itself in the tight-budget regime, where the whole dictionary
1403 /// does not fit and chunks are genuinely re-decoded. Skipping the dispatch
1404 /// on cache-warm windows is what keeps a large budget from regressing.
1405 ///
1406 /// The bound matters for `--memory-budget-mb`: a decoding group holds at
1407 /// most [`PAR_DECODE_FANOUT`] decoded bodies at once (a small constant,
1408 /// independent of the window size or the budget) and each is held behind its
1409 /// cache `Arc` for the group's fill — so even a budget that evicts a body
1410 /// the moment it lands cannot force a re-decode before the fill consumes it.
1411 /// The decode runs on a small dedicated pool ([`decode_pool`]), so the number
1412 /// of worker threads (and their allocator arenas) is bounded regardless of
1413 /// the machine's core count.
1414 #[cfg(feature = "parallel")]
1415 fn decode_and_walk(
1416 &self,
1417 segments: &[(usize, usize, usize)],
1418 jobs: &[(u32, usize)],
1419 out: &mut [Option<String>],
1420 ri: usize,
1421 tc: u32,
1422 ) {
1423 use rayon::prelude::*;
1424 for group in segments.chunks(PAR_DECODE_FANOUT) {
1425 let has_miss = group
1426 .iter()
1427 .any(|&(ci, _, _)| !self.cache.contains((self.section_index, ci as u32)));
1428 if has_miss {
1429 // Real decode work: fault this group's chunks in parallel on the
1430 // bounded pool (order preserved so each entry lines up with its
1431 // segment), then fill serially. A failed fault yields `None`
1432 // (recorded in `self.failed`), same as the serial path.
1433 let entries: Vec<Option<Arc<CacheEntry>>> = decode_pool().install(|| {
1434 group
1435 .par_iter()
1436 .map(|&(ci, _, _)| self.chunk_entry(ci))
1437 .collect()
1438 });
1439 for (&(ci, s, e), entry) in group.iter().zip(entries) {
1440 if let Some(entry) = entry {
1441 self.walk_chunk(ci, &entry, &jobs[s..e], out, ri, tc);
1442 }
1443 }
1444 } else {
1445 // Cache-warm: no decode to parallelize, so avoid the dispatch.
1446 for &(ci, s, e) in group {
1447 if let Some(entry) = self.chunk_entry(ci) {
1448 self.walk_chunk(ci, &entry, &jobs[s..e], out, ri, tc);
1449 }
1450 }
1451 }
1452 }
1453 }
1454
1455 /// Serial fallback for builds without the `parallel` feature (wasm, and
1456 /// `--no-default-features`): fault and walk one chunk at a time.
1457 #[cfg(not(feature = "parallel"))]
1458 fn decode_and_walk(
1459 &self,
1460 segments: &[(usize, usize, usize)],
1461 jobs: &[(u32, usize)],
1462 out: &mut [Option<String>],
1463 ri: usize,
1464 tc: u32,
1465 ) {
1466 for &(ci, s, e) in segments {
1467 if let Some(entry) = self.chunk_entry(ci) {
1468 self.walk_chunk(ci, &entry, &jobs[s..e], out, ri, tc);
1469 }
1470 }
1471 }
1472
1473 /// Fill the output slots owned by one chunk: `chunk_jobs` is the id-sorted
1474 /// slice of `(id, slot)` jobs that all live in chunk `ci`, and `entry` is
1475 /// that chunk's already-faulted body. Walks the chunk's front-coded runs
1476 /// once each, forward, picking off every requested id as the decode passes
1477 /// it — the single-pass twin of `term(id)`, writing exactly the bytes
1478 /// `term(id)` would for each id and leaving a slot None where `term(id)` is
1479 /// None (a malformed run entry, past which no larger id in that run decodes).
1480 fn walk_chunk(
1481 &self,
1482 ci: usize,
1483 entry: &CacheEntry,
1484 chunk_jobs: &[(u32, usize)],
1485 out: &mut [Option<String>],
1486 ri: usize,
1487 tc: u32,
1488 ) {
1489 let bytes: &[u8] = entry.body();
1490 let mut k = 0;
1491 while k < chunk_jobs.len() {
1492 let id = chunk_jobs[k].0;
1493 if id == ABSENT || id > tc {
1494 k += 1;
1495 continue;
1496 }
1497 let run = (id - 1) as usize / ri;
1498 // Decode this run's restart entry. Any failure here means
1499 // `term(id)` is None for the whole run — skip every job in it.
1500 let run_start = self.run_off_in_chunk(ci, run, entry, ri).and_then(|off| {
1501 let mut buf = Vec::new();
1502 run_entry_into(bytes, off, &mut buf).map(|pos| (buf, pos))
1503 });
1504 let Some((mut buf, mut pos)) = run_start else {
1505 while k < chunk_jobs.len() {
1506 let id = chunk_jobs[k].0;
1507 if id == ABSENT || id > tc {
1508 k += 1;
1509 continue;
1510 }
1511 if (id - 1) as usize / ri != run {
1512 break;
1513 }
1514 k += 1;
1515 }
1516 continue;
1517 };
1518 // `buf` holds the run's term #`cur_step`; advance monotonically.
1519 let mut cur_step = 0usize;
1520 let mut broken = false;
1521 while k < chunk_jobs.len() {
1522 let id = chunk_jobs[k].0;
1523 if id == ABSENT || id > tc {
1524 k += 1;
1525 continue;
1526 }
1527 if (id - 1) as usize / ri != run {
1528 break; // next run
1529 }
1530 let steps = (id - 1) as usize % ri;
1531 if !broken {
1532 while cur_step < steps {
1533 match entry_into(bytes, pos, &mut buf) {
1534 Some(next) => {
1535 pos = next;
1536 cur_step += 1;
1537 }
1538 None => {
1539 // Malformed past this point: `term(id)` is None
1540 // here and for every larger id in the run (they
1541 // all decode through this entry).
1542 broken = true;
1543 break;
1544 }
1545 }
1546 }
1547 if !broken && cur_step == steps {
1548 out[chunk_jobs[k].1] = Some(String::from_utf8_lossy(&buf).into_owned());
1549 }
1550 }
1551 k += 1;
1552 }
1553 }
1554 }
1555
1556 /// The chunk [`id`](Self::id) would fault to look `term` up — its routing
1557 /// on the (resident) chunk directory, without touching a chunk body. `None`
1558 /// for an empty section, or a term that sorts before the first chunk.
1559 pub(crate) fn chunk_for_term(&self, term: &str) -> Option<usize> {
1560 self.chunks
1561 .chunk_for_term(&self.order.probe(term.as_bytes()))
1562 }
1563
1564 /// The leaf directory block that routes `term` to a chunk, without reading
1565 /// it. `None` on a section whose directory is resident (nothing to fault).
1566 pub(crate) fn leaf_for_term(&self, term: &str) -> Option<usize> {
1567 match &self.chunks {
1568 ChunkDir::Leafed(l) if l.total > 0 => {
1569 l.leaf_of_term(&self.order.probe(term.as_bytes()))
1570 }
1571 _ => None,
1572 }
1573 }
1574
1575 /// The leaf directory block that routes term `id` (1-based, section-local)
1576 /// to a chunk, without reading it. `None` on a resident directory or an
1577 /// id out of range.
1578 pub(crate) fn leaf_of_id(&self, id: u32) -> Option<usize> {
1579 if id == ABSENT || id > self.meta.term_count {
1580 return None;
1581 }
1582 match &self.chunks {
1583 ChunkDir::Leafed(l) => {
1584 l.leaf_of_run((id - 1) as usize / self.meta.restart_interval as usize)
1585 }
1586 ChunkDir::Full(_) => None,
1587 }
1588 }
1589
1590 /// How many chunks the section has.
1591 pub(crate) fn chunk_total(&self) -> usize {
1592 self.chunks.len()
1593 }
1594
1595 /// Every leaf index of a leafed directory (none when it is resident).
1596 pub(crate) fn all_leaves(&self) -> Vec<usize> {
1597 self.leaf_dir()
1598 .map_or_else(Vec::new, |l| (0..l.leaves.len()).collect())
1599 }
1600
1601 /// This section's leaf directory, when it faults its leaves on demand.
1602 pub(crate) fn leaf_dir(&self) -> Option<&LeafedChunks> {
1603 match &self.chunks {
1604 ChunkDir::Leafed(l) => Some(l),
1605 ChunkDir::Full(_) => None,
1606 }
1607 }
1608
1609 /// How many terms of this section sort (in its order) before `bound`: the
1610 /// routed chunk is the only one the boundary can lie in (every term of an
1611 /// earlier chunk sorts before its routing key, every term of a later one at
1612 /// or after the next key), so this faults that one chunk and binary-searches
1613 /// its ids. `None` when a chunk cannot be read.
1614 pub(crate) fn rank(&self, bound: &str) -> Option<u32> {
1615 self.rank_via(bound, &|id| self.term(id))
1616 }
1617
1618 /// [`rank`](Self::rank) with the term of an id read by `term_of`: how a
1619 /// chunk with no stored body is searched.
1620 pub(crate) fn rank_via(
1621 &self,
1622 bound: &str,
1623 term_of: &dyn Fn(u32) -> Option<String>,
1624 ) -> Option<u32> {
1625 let probe = self.order.probe(bound.as_bytes());
1626 let tc = self.meta.term_count;
1627 let ri = self.meta.restart_interval as usize;
1628 if tc == 0 || ri == 0 {
1629 return Some(0);
1630 }
1631 let Some(ci) = self.chunk_for_term(bound) else {
1632 return Some(0); // `bound` sorts before the first chunk's key
1633 };
1634 // Ids of chunk `ci`: its first run's first id up to the id before the
1635 // next chunk's first run (or the last id).
1636 let first = (self.chunks.get(ci)?.first_run.checked_mul(ri)? as u64 + 1).min(tc as u64 + 1);
1637 let last = match self.chunks.next_first_run(ci) {
1638 Some(next) => (next.checked_mul(ri)? as u64).min(tc as u64),
1639 None => tc as u64,
1640 };
1641 // The first id in [first, last] whose term is >= bound (last + 1 if none).
1642 let (mut lo, mut hi) = (first, last + 1);
1643 while lo < hi {
1644 let mid = lo + (hi - lo) / 2;
1645 let term = term_of(u32::try_from(mid).ok()?)?;
1646 if probe.cmp_stored(term.as_bytes()) == std::cmp::Ordering::Less {
1647 lo = mid + 1;
1648 } else {
1649 hi = mid;
1650 }
1651 }
1652 u32::try_from(lo - 1).ok()
1653 }
1654
1655 /// Does this section fault chunk bodies in on demand (a lazy or ranged
1656 /// open), rather than hold them all resident?
1657 pub(crate) fn faults_chunks(&self) -> bool {
1658 self.loader.is_some()
1659 }
1660
1661 /// Resolve `term` to its ID. Chunk-level binary search runs on the (local)
1662 /// chunk directory, so this also costs at most one chunk fault.
1663 pub fn id(&self, term: &str) -> Option<u32> {
1664 match self.lookup(term) {
1665 Lookup::Found(id) => Some(id),
1666 Lookup::Absent | Lookup::Elided { .. } => None,
1667 }
1668 }
1669
1670 /// [`id`](Self::id), telling a term that routes to a chunk the file does
1671 /// not store from one that is absent.
1672 pub fn lookup(&self, term: &str) -> Lookup {
1673 let found = self.lookup_inner(term);
1674 found.map_or(Lookup::Absent, |l| l)
1675 }
1676
1677 /// Look up a string literal under both of its spellings in one search:
1678 /// `lo` is the plain one (`"x"`), `hi` the typed one
1679 /// (`"x"^^xsd:string`). Returns `lo`'s id, and `hi`'s when this search
1680 /// settled it (`None`: not settled, look `hi` up on its own).
1681 ///
1682 /// In the SPARQL order the two are neighbours: the same lexical form,
1683 /// datatype rank and tag, then the token, and the plain token is a prefix
1684 /// of the typed one. So the search for `lo` ends on `hi` or proves it
1685 /// absent, unless it ends at the edge of a run. A lookup that missed
1686 /// under one spelling used to search every section again for the other;
1687 /// a `BIND` of a new string is always such a miss. In the byte order
1688 /// other terms sort between the two (`"x"@en`), and nothing is settled.
1689 pub(crate) fn lookup_pair(&self, lo: &str, hi: &str) -> (Option<u32>, Option<Option<u32>>) {
1690 let settled = if self.order == TermOrder::Sparql {
1691 self.lookup_pair_inner(lo, hi)
1692 } else {
1693 None
1694 };
1695 settled.unwrap_or_else(|| (self.id(lo), None))
1696 }
1697
1698 /// `None`: the search could not be made this way (an elided chunk, a
1699 /// term before its chunk's first, a failed read); the caller looks each
1700 /// spelling up on its own.
1701 #[allow(clippy::type_complexity)]
1702 fn lookup_pair_inner(&self, lo: &str, hi: &str) -> Option<(Option<u32>, Option<Option<u32>>)> {
1703 if self.chunks.is_empty() {
1704 return None;
1705 }
1706 let ri = self.meta.restart_interval as usize;
1707 let probe = self.order.probe(lo.as_bytes());
1708 let ci = self.chunks.chunk_for_term(&probe)?;
1709 if self.is_elided(ci) {
1710 return None;
1711 }
1712 let first_run = self.chunks.get(ci)?.first_run;
1713 let entry = self.chunk_entry(ci)?;
1714 let bytes: &[u8] = entry.body();
1715 let run_end = self.run_end_of_chunk(ci, &entry, ri);
1716 let mut buf = Vec::new();
1717 let (mut a, mut b) = (first_run, run_end);
1718 while a < b {
1719 let mid = (a + b) / 2;
1720 let off = self.run_off_in_chunk(ci, mid, &entry, ri)?;
1721 run_entry_into(bytes, off, &mut buf)?;
1722 if probe.cmp_stored(&buf) != std::cmp::Ordering::Greater {
1723 a = mid + 1;
1724 } else {
1725 b = mid;
1726 }
1727 }
1728 if a == first_run {
1729 // `lo` sorts before the chunk's first term, which may be `hi`.
1730 return None;
1731 }
1732 let run = a - 1;
1733 let off = self.run_off_in_chunk(ci, run, &entry, ri)?;
1734 let mut pos = run_entry_into(bytes, off, &mut buf)?;
1735 let base_id = (run * ri) as u32 + 1;
1736 let run_len = self.meta.restart_interval.min(
1737 self.meta
1738 .term_count
1739 .saturating_sub(run as u32 * self.meta.restart_interval),
1740 );
1741 for step in 0..run_len {
1742 let id = base_id + step;
1743 match probe.cmp_stored(&buf) {
1744 std::cmp::Ordering::Equal => {
1745 // `hi` is the next term of the section, or not in it.
1746 if step + 1 < run_len {
1747 entry_into(bytes, pos, &mut buf)?;
1748 let next = (buf.as_slice() == hi.as_bytes()).then_some(id + 1);
1749 return Some((Some(id), Some(next)));
1750 }
1751 return Some((Some(id), None));
1752 }
1753 // The first term past `lo`: `hi`, or `hi` is absent too.
1754 std::cmp::Ordering::Greater => {
1755 let here = (buf.as_slice() == hi.as_bytes()).then_some(id);
1756 return Some((None, Some(here)));
1757 }
1758 std::cmp::Ordering::Less => {}
1759 }
1760 if step + 1 < run_len {
1761 pos = entry_into(bytes, pos, &mut buf)?;
1762 }
1763 }
1764 // Past the run's last term: `lo` is absent, `hi` may open the next run.
1765 Some((None, None))
1766 }
1767
1768 fn lookup_inner(&self, term: &str) -> Option<Lookup> {
1769 if self.chunks.is_empty() {
1770 return None;
1771 }
1772 let ri = self.meta.restart_interval as usize;
1773 // Pick the chunk: the last one whose ROUTING KEY is <= `term` (the
1774 // single local chunk skips the search — its key is unset).
1775 //
1776 // [`chunk_for_term`](Self::chunk_for_term) is the ONLY read of
1777 // [`SectionChunk::key`] in the codebase (the batched lookup prefetch
1778 // routes through it too, so it faults exactly the chunk this reads), and
1779 // all it needs is the separator invariant `last(i-1) < key(i) <=
1780 // first(i)`: `term` lands in chunk `i` exactly when `key(i) <= term <
1781 // key(i+1)`, which covers every term of chunk `i` and nothing in any
1782 // other chunk. A verbatim first term satisfies it too, which is why
1783 // files written either way route identically.
1784 //
1785 // With separators the search can land on chunk `i` for a `term` in the
1786 // gap `key(i) <= term < first(i)`; the run search below then hits its
1787 // `lo == first_run` branch and answers `None`, which is correct — such
1788 // a term is strictly between two chunks, i.e. absent.
1789 // The term is read once for the whole lookup ([`crate::term_order::Probe`]).
1790 let probe = self.order.probe(term.as_bytes());
1791 let ci = self.chunks.chunk_for_term(&probe)?;
1792 let first_run = self.chunks.get(ci)?.first_run;
1793 if self.is_elided(ci) {
1794 let (first, last) = self.chunk_ids(ci)?;
1795 return Some(Lookup::Elided { first, last });
1796 }
1797 let entry = self.chunk_entry(ci)?;
1798 let bytes: &[u8] = entry.body();
1799
1800 // Binary search this chunk's runs by their first (full) term.
1801 let run_end = self.run_end_of_chunk(ci, &entry, ri);
1802 let mut buf = Vec::new();
1803 let mut lo = first_run;
1804 let mut hi = run_end;
1805 while lo < hi {
1806 let mid = (lo + hi) / 2;
1807 let off = self.run_off_in_chunk(ci, mid, &entry, ri)?;
1808 run_entry_into(bytes, off, &mut buf)?;
1809 if probe.cmp_stored(&buf) != std::cmp::Ordering::Greater {
1810 lo = mid + 1;
1811 } else {
1812 hi = mid;
1813 }
1814 }
1815 if lo == first_run {
1816 // Smaller than every term in (and before) this chunk. Unreachable
1817 // when the key is a verbatim first term; reachable, and correct,
1818 // when it is a separator: `key(ci) <= term < first(ci)` puts the
1819 // term strictly between two chunks.
1820 return None;
1821 }
1822 let run = lo - 1;
1823 let off = self.run_off_in_chunk(ci, run, &entry, ri)?;
1824 let mut pos = run_entry_into(bytes, off, &mut buf)?;
1825 let base_id = (run * ri) as u32 + 1;
1826 // saturating_sub: corrupt metadata must not underflow-panic.
1827 let run_len = self.meta.restart_interval.min(
1828 self.meta
1829 .term_count
1830 .saturating_sub(run as u32 * self.meta.restart_interval),
1831 );
1832 for step in 0..run_len {
1833 match probe.cmp_stored(&buf) {
1834 std::cmp::Ordering::Equal => return Some(Lookup::Found(base_id + step)),
1835 std::cmp::Ordering::Greater => return None,
1836 std::cmp::Ordering::Less => {}
1837 }
1838 if step + 1 < run_len {
1839 pos = entry_into(bytes, pos, &mut buf)?;
1840 }
1841 }
1842 None
1843 }
1844
1845 /// The full serialized section (header + body), for the file writer. The
1846 /// local single-chunk case returns the stored bytes; a chunked section
1847 /// re-assembles them (header re-encoded from the metadata).
1848 pub fn raw_section_bytes(&self) -> Vec<u8> {
1849 if self.chunks.len() == 1 && self.chunks.get(0).is_some_and(|c| c.body_start == 0) {
1850 if let Some(entry) = self.cache.get((self.section_index, 0)) {
1851 return entry.body().to_vec();
1852 }
1853 }
1854 let mut out = encode_section_header(&self.meta);
1855 for ci in 0..self.chunks.len() {
1856 if let Some(entry) = self.chunk_entry(ci) {
1857 out.extend_from_slice(entry.body());
1858 }
1859 }
1860 out
1861 }
1862}
1863
1864/// Re-encode a section header (term_count, interval, restart table) from its
1865/// parsed metadata — the inverse of [`parse_meta`]. Restart offsets are stored
1866/// body-relative on disk; `meta` holds them absolute, so the body start is
1867/// re-derived as the first run's offset.
1868pub fn encode_section_header(meta: &SectionMeta) -> Vec<u8> {
1869 let body_start = meta.restart_offsets.first().copied().unwrap_or(0);
1870 let mut out = Vec::new();
1871 write_uvarint(&mut out, meta.term_count as u64);
1872 write_uvarint(&mut out, meta.restart_interval as u64);
1873 write_uvarint(&mut out, meta.restart_offsets.len() as u64);
1874 for off in &meta.restart_offsets {
1875 write_uvarint(&mut out, off.saturating_sub(body_start));
1876 }
1877 out
1878}
1879
1880/// A parsed, read-only dictionary section (parses its metadata on construction).
1881pub struct DictSection<'a> {
1882 bytes: &'a [u8],
1883 meta: SectionMeta,
1884}
1885
1886impl<'a> DictSection<'a> {
1887 pub fn parse(bytes: &'a [u8]) -> Result<Self, DictError> {
1888 Ok(Self {
1889 bytes,
1890 meta: parse_meta(bytes)?,
1891 })
1892 }
1893
1894 pub fn len(&self) -> u32 {
1895 self.meta.term_count
1896 }
1897
1898 pub fn is_empty(&self) -> bool {
1899 self.meta.term_count == 0
1900 }
1901
1902 /// Resolve `id` (1-based) to its term, or `None` if out of range.
1903 pub fn term(&self, id: u32) -> Option<String> {
1904 section_term(self.bytes, &self.meta, id)
1905 }
1906
1907 /// Resolve `term` to its ID, or `None` if absent.
1908 pub fn id(&self, term: &str) -> Option<u32> {
1909 section_id(self.bytes, &self.meta, term)
1910 }
1911}
1912
1913fn common_prefix_len(a: &str, b: &str) -> usize {
1914 a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count()
1915}
1916
1917#[cfg(test)]
1918mod tests {
1919 use super::*;
1920
1921 /// Build a *lite* (empty section-wide restart table), genuinely multi-chunk
1922 /// [`ChunkedSection`] from `terms`: the exact shape a ranged open produces,
1923 /// so `resolve_into`'s per-chunk run-table branch and its cross-chunk /
1924 /// cross-run walk are all exercised. `runs_per_chunk` chops the runs into
1925 /// several chunks regardless of size, so a tiny fixture still spans many.
1926 fn lite_multichunk(terms: &[&str], ri: u32, runs_per_chunk: usize) -> (ChunkedSection, u32) {
1927 let mut b = DictSectionBuilder::new().with_restart_interval(ri);
1928 for t in terms {
1929 b.push(*t);
1930 }
1931 let raw = b.build();
1932 let full_meta = parse_meta(&raw).unwrap();
1933 let n_runs = full_meta.restart_offsets.len();
1934 let mut chunks = Vec::new();
1935 let mut bodies: Vec<Vec<u8>> = Vec::new();
1936 let mut r = 0;
1937 while r < n_runs {
1938 let first_run = r;
1939 let start = full_meta.restart_offsets[r] as usize;
1940 let r2 = (r + runs_per_chunk).min(n_runs);
1941 let end = if r2 < n_runs {
1942 full_meta.restart_offsets[r2] as usize
1943 } else {
1944 raw.len()
1945 };
1946 chunks.push(SectionChunk::new(first_run, Vec::new(), start as u64));
1947 bodies.push(raw[start..end].to_vec());
1948 r = r2;
1949 }
1950 assert!(chunks.len() > 1, "fixture must be multi-chunk");
1951 // Lite: no section-wide restart table -> run offsets come from each
1952 // decoded chunk body, cached in its cache entry (the ranged path).
1953 let lite_meta = SectionMeta {
1954 term_count: full_meta.term_count,
1955 restart_interval: full_meta.restart_interval,
1956 restart_offsets: Vec::new(),
1957 };
1958 let loader: ChunkLoader = Box::new(move |ci| bodies.get(ci).cloned());
1959 let sec = ChunkedSection::from_parts(
1960 lite_meta,
1961 chunks,
1962 Some(loader),
1963 ChunkCache::unlimited_arc(),
1964 0,
1965 );
1966 (sec, full_meta.term_count)
1967 }
1968
1969 /// The windowed batch resolver must fill exactly what a per-id `term()`
1970 /// would, for a scrambled, duplicated, out-of-range id set spread across
1971 /// many chunks and runs — the byte-identity guarantee `dump_filtered_each`
1972 /// rests on (phase 1). Also cross-checked against the ground-truth
1973 /// `section_term` decoder.
1974 #[test]
1975 fn resolve_into_matches_term_across_chunks_and_runs() {
1976 // Shared prefixes (front-coding), a long literal (a run that dwarfs its
1977 // neighbors), blank nodes — 240 distinct terms.
1978 let owned: Vec<String> = (0..240)
1979 .map(|i| match i % 4 {
1980 0 => format!("<http://example.org/entity/{i:05}>"),
1981 1 => format!("<http://example.org/entity/{i:05}/sub/leaf>"),
1982 2 => format!("\"literal value {} padded {}\"", i, "x".repeat(i % 50)),
1983 _ => format!("_:b{i:05}"),
1984 })
1985 .collect();
1986 let terms: Vec<&str> = owned.iter().map(String::as_str).collect();
1987
1988 for (ri, rpc) in [(1u32, 5usize), (4, 3), (16, 2)] {
1989 let (sec, count) = lite_multichunk(&terms, ri, rpc);
1990 let raw = {
1991 let mut b = DictSectionBuilder::new().with_restart_interval(ri);
1992 for t in &terms {
1993 b.push(*t);
1994 }
1995 b.build()
1996 };
1997 let full_meta = parse_meta(&raw).unwrap();
1998
1999 // A scrambled probe set: every id once, a run of duplicates, some
2000 // out-of-range ids (0 and past the end) that must stay `None`.
2001 let mut probe: Vec<u32> = (1..=count).collect();
2002 probe.extend([1, 1, count, count, ABSENT, count + 3, count + 100]);
2003 // Deterministic shuffle so chunk order != probe order.
2004 let mut state = 0xDEAD_BEEF_1234_5678u64;
2005 for k in (1..probe.len()).rev() {
2006 state ^= state << 13;
2007 state ^= state >> 7;
2008 state ^= state << 17;
2009 probe.swap(k, (state % (k as u64 + 1)) as usize);
2010 }
2011
2012 let mut jobs: Vec<(u32, usize)> = probe.iter().map(|&id| (id, 0)).collect();
2013 for (slot, j) in jobs.iter_mut().enumerate() {
2014 j.1 = slot;
2015 }
2016 let mut out: Vec<Option<String>> = vec![None; probe.len()];
2017 sec.resolve_into(&mut jobs, &mut out);
2018
2019 for (slot, &id) in probe.iter().enumerate() {
2020 let via_term = sec.term(id);
2021 assert_eq!(
2022 out[slot], via_term,
2023 "resolve_into(id={id}) != term(id) at ri={ri} rpc={rpc}"
2024 );
2025 // Ground truth for in-range ids.
2026 let truth = section_term(&raw, &full_meta, id);
2027 assert_eq!(out[slot], truth, "resolve_into(id={id}) != section_term");
2028 }
2029 }
2030 }
2031
2032 fn sample() -> Vec<String> {
2033 // Deliberately unsorted, with shared prefixes and a duplicate.
2034 [
2035 "http://ex.org/Alice",
2036 "http://ex.org/Bob",
2037 "http://ex.org/Alan",
2038 "http://ex.org/knows",
2039 "http://ex.org/Alice", // dup
2040 "zeta",
2041 ]
2042 .iter()
2043 .map(|s| s.to_string())
2044 .collect()
2045 }
2046
2047 #[test]
2048 fn round_trip_all_ids_and_terms() {
2049 for r in [1u32, 2, 16, 1000] {
2050 let mut b = DictSectionBuilder::new().with_restart_interval(r);
2051 for t in sample() {
2052 b.push(t);
2053 }
2054 let bytes = b.build();
2055 let sec = DictSection::parse(&bytes).unwrap();
2056
2057 // Expected sorted unique set.
2058 let mut expected = sample();
2059 expected.sort();
2060 expected.dedup();
2061 assert_eq!(sec.len() as usize, expected.len());
2062
2063 for (i, term) in expected.iter().enumerate() {
2064 let id = (i + 1) as u32;
2065 assert_eq!(
2066 sec.term(id).as_deref(),
2067 Some(term.as_str()),
2068 "term({id}) r={r}"
2069 );
2070 assert_eq!(sec.id(term), Some(id), "id({term}) r={r}");
2071 }
2072 }
2073 }
2074
2075 #[test]
2076 fn lookups_for_absent_terms() {
2077 let mut b = DictSectionBuilder::new();
2078 for t in sample() {
2079 b.push(t);
2080 }
2081 let bytes = b.build();
2082 let sec = DictSection::parse(&bytes).unwrap();
2083 assert_eq!(sec.id("aaa-before-everything"), None);
2084 assert_eq!(sec.id("zzz-after-everything"), None);
2085 assert_eq!(sec.id("http://ex.org/Alic"), None); // prefix, not present
2086 assert_eq!(sec.term(0), None);
2087 assert_eq!(sec.term(9999), None);
2088 }
2089
2090 /// Property-style stress of the front-coded decode paths: a large
2091 /// deterministic-pseudo-random term pool (IRIs with heavy shared prefixes,
2092 /// literals, blank nodes — duplicates likely) must round-trip every id and
2093 /// term across restart intervals, and near-miss probes (a stored term ± a
2094 /// suffix/truncation, including run-boundary terms) must resolve to `None`.
2095 /// Term resolution is the engine's hot path, so this is the test that
2096 /// guards the buffer-reuse decode.
2097 #[test]
2098 fn randomized_round_trip_and_near_misses_across_restart_intervals() {
2099 let mut state = 0x9E37_79B9_7F4A_7C15u64;
2100 let mut next = move || {
2101 state ^= state << 13;
2102 state ^= state >> 7;
2103 state ^= state << 17;
2104 state
2105 };
2106 let pool: Vec<String> = (0..1500)
2107 .map(|i| {
2108 let n = next();
2109 match n % 4 {
2110 0 => format!("<http://example.org/entity/{n:x}>"),
2111 1 => format!("\"literal value {} with spaces\"", n % 300), // dups likely
2112 2 => format!("<http://example.org/entity/{}/sub/{i}>", n % 64), // long shared prefixes
2113 _ => format!("_:b{}", n % 256),
2114 }
2115 })
2116 .collect();
2117 let mut expected = pool.clone();
2118 expected.sort();
2119 expected.dedup();
2120
2121 for r in [1u32, 3, 16, 64] {
2122 let mut b = DictSectionBuilder::new().with_restart_interval(r);
2123 for t in &pool {
2124 b.push(t.clone());
2125 }
2126 let bytes = b.build();
2127 let sec = DictSection::parse(&bytes).unwrap();
2128 assert_eq!(sec.len() as usize, expected.len(), "r={r}");
2129
2130 for (i, term) in expected.iter().enumerate() {
2131 let id = (i + 1) as u32;
2132 assert_eq!(
2133 sec.term(id).as_deref(),
2134 Some(term.as_str()),
2135 "term({id}) r={r}"
2136 );
2137 assert_eq!(sec.id(term), Some(id), "id({term}) r={r}");
2138 }
2139 // Near misses around run boundaries (and a sample of the rest):
2140 // an appended suffix or a truncation is never a stored term unless
2141 // it happens to collide with one.
2142 for (i, term) in expected.iter().enumerate() {
2143 let near_boundary = (i as u32) % r <= 1;
2144 if !near_boundary && i % 37 != 0 {
2145 continue;
2146 }
2147 let longer = format!("{term}\u{1}");
2148 assert_eq!(sec.id(&longer), None, "near-miss long r={r}");
2149 let mut shorter = term.clone();
2150 shorter.pop();
2151 if !shorter.is_empty() && expected.binary_search(&shorter).is_err() {
2152 assert_eq!(sec.id(&shorter), None, "near-miss short {shorter:?} r={r}");
2153 }
2154 }
2155 assert_eq!(sec.term(expected.len() as u32 + 1), None, "past-end r={r}");
2156 }
2157 }
2158}