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