Skip to main content

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(&section_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}