Skip to main content

rete_core/v06/
mod.rs

1//! Format generations `0x06` and `0x07` (SPEC.md §4): everything a reader needs to plan a
2//! query sits at the **front** of the file — a 128-byte header, the root block,
3//! the Dataset Card, the planner statistics and every leaf directory — and the
4//! payload follows, clustered by section.
5//!
6//! ```text
7//! 0          header (128 B)
8//! 128        root block: section table + directory roots
9//!            card region: card | build record | slack
10//!            front sections: stats+schema, then the leaf directories
11//! data_off   data sections: dictionary chunks, index tiles, quad tiles,
12//!            label blocks, text postings, pyramid
13//! file_len-8 footer "RETE" 06 00 00 00
14//! ```
15//!
16//! `0x07` is `0x06` plus two things: the label index's root node lives in a
17//! cold section of its own ([`kind::LABEL_ROOT`]) instead of in the root, and an
18//! optional card annex ([`kind::CARD_ANNEX`]) holds card fields too big for the
19//! hot card. The two generations share this module: [`Header06::version`] says
20//! which one a file is, readers read both, writers write [`VERSION`].
21//!
22//! Payload blocks (dictionary chunks, index tiles, quad tiles, label blocks,
23//! postings) are byte-identical to `0x05`; only their framing and their
24//! directories move. [`parts`] lifts a `0x05` file into [`parts::Parts`],
25//! [`write`](mod@write) assembles a `0x06` file from them, [`open`] reads one.
26
27pub mod annex;
28pub mod cluster;
29pub(crate) mod neworders;
30pub mod open;
31pub mod parts;
32pub use cluster::check_clusters;
33pub use neworders::check_orders;
34pub mod write;
35
36#[cfg(test)]
37mod cluster_tests;
38#[cfg(test)]
39mod roundtrip;
40
41use crate::file::FileError;
42use crate::varint::{read_uvarint, write_uvarint};
43
44/// The format byte writers stamp (the current generation).
45pub const VERSION: u8 = 0x07;
46/// The previous generation this reader still reads (no annex, label root in
47/// the root block).
48pub const VERSION_06: u8 = 0x06;
49
50/// Does this module read format byte `v`?
51pub fn reads(v: u8) -> bool {
52    v == VERSION_06 || v == VERSION
53}
54/// Fixed header length.
55pub const HEADER_LEN: usize = 128;
56/// What a reader fetches first: header, root, card, statistics and, on a small
57/// file, every leaf directory (SPEC.md §9).
58pub const FIRST_READ: u64 = 128 * 1024;
59/// The 8-byte footer of the current generation: the generation, then `RETE`
60/// — so every reader that confirms a length by the file's last four bytes
61/// finds the magic there.
62pub const FOOTER: [u8; 8] = *b"\x07\x00\x00\x00RETE";
63
64/// The footer of generation `version`.
65pub fn footer(version: u8) -> [u8; 8] {
66    let mut f = FOOTER;
67    f[0] = version;
68    f
69}
70
71/// Largest card annex a reader decompresses.
72pub const ANNEX_MAX: u64 = 64 << 20;
73/// The writer's root budget: leaves may grow (to [`LEAF_MAX`]) to bring the
74/// stored root under it, when growing them can.
75pub const ROOT_BUDGET: usize = 40 * 1024;
76/// Starting (uncompressed) size of a leaf block.
77pub const LEAF_START: usize = 16 * 1024;
78/// Largest leaf the writer grows to for the root budget (uncompressed).
79pub const LEAF_MAX: usize = 64 * 1024;
80/// The most the leaf lists may add to a root; past it leaves grow beyond
81/// [`LEAF_MAX`].
82pub const LIST_CAP: usize = 256 * 1024;
83/// Slack added to the card region beyond twice the card + record.
84pub const CARD_SLACK_MIN: u32 = 8 * 1024;
85
86/// Header flag: the file has named graphs (in the quad index).
87pub const F_NAMED: u8 = 0b0001;
88/// Header flag: some terms are RDF-star quoted triples.
89pub const F_QUOTED: u8 = 0b0010;
90/// Header flag: the text index also covers the named graphs' literals.
91pub const F_TEXT_NAMED: u8 = 0b0100;
92/// Header flag: quad tiles are clustered graph-major (all orders of a block of
93/// graphs adjacent) rather than order-major.
94pub const F_QUAD_GRAPH_MAJOR: u8 = 0b1000;
95/// Header flag (`0x07`): the subject-leading permutations (SPO, SOP) are
96/// clustered by class: their tiles are in `(cluster, s, p, o)` order, listed
97/// by the cluster root ([`tag::CLUSTER`]).
98pub const F_CLUSTERED: u8 = 0b1_0000;
99/// `ClusterOrder::si` of the quad index's SPOG (its quad slot).
100pub const QUAD_SPOG: usize = crate::quad7::FIRST_LAST_SLOT;
101/// The most classes a clustered permutation has a run for (the rest are run 0).
102pub const MAX_CLUSTERS: usize = 32;
103
104/// Presence bit: a text index.
105pub const P_TEXT: u16 = 1;
106/// Presence bit: the text index leaves some predicates out (kind 11 in 0x05).
107pub const P_TEXT_PARTIAL: u16 = 2;
108/// Presence bit: a label index.
109pub const P_LABELS: u16 = 4;
110/// Presence bit: a stats + schema section.
111pub const P_SCHEMA: u16 = 8;
112/// Presence bit: the community pyramid.
113pub const P_PYRAMID: u16 = 16;
114/// Presence bit: the quad index.
115pub const P_QUAD: u16 = 32;
116
117/// Section kinds of the root's section table.
118#[allow(missing_docs)]
119pub mod kind {
120    pub const SCHEMA: u8 = 1;
121    pub const DICT_LEAVES: u8 = 2;
122    pub const INDEX_LEAVES: u8 = 3;
123    pub const QUAD_LEAVES: u8 = 4;
124    pub const LABEL_LEAVES: u8 = 5;
125    pub const TEXT_LEAVES: u8 = 6;
126    pub const DICT_DATA: u8 = 16;
127    pub const INDEX_DATA: u8 = 17;
128    pub const QUAD_DATA: u8 = 18;
129    pub const LABEL_DATA: u8 = 19;
130    pub const TEXT_DATA: u8 = 20;
131    pub const PYRAMID: u8 = 21;
132    /// `0x07`: the label index's root node (front, after the other leaves).
133    pub const LABEL_ROOT: u8 = 7;
134    /// `0x07`: card fields too big for the hot card (the last data section).
135    pub const CARD_ANNEX: u8 = 22;
136
137    /// Every kind, in file order (front kinds, then data kinds).
138    pub const ORDER: [u8; 14] = [
139        SCHEMA,
140        DICT_LEAVES,
141        INDEX_LEAVES,
142        QUAD_LEAVES,
143        LABEL_LEAVES,
144        TEXT_LEAVES,
145        LABEL_ROOT,
146        DICT_DATA,
147        INDEX_DATA,
148        QUAD_DATA,
149        LABEL_DATA,
150        TEXT_DATA,
151        PYRAMID,
152        CARD_ANNEX,
153    ];
154
155    /// Kinds only a `0x07` file has.
156    pub fn is_v07_only(k: u8) -> bool {
157        k == LABEL_ROOT || k == CARD_ANNEX
158    }
159
160    /// A short name, for `verify --section` and `info`.
161    pub fn name(k: u8) -> &'static str {
162        match k {
163            SCHEMA => "schema",
164            DICT_LEAVES => "dict-leaves",
165            INDEX_LEAVES => "index-leaves",
166            QUAD_LEAVES => "quad-leaves",
167            LABEL_LEAVES => "label-leaves",
168            TEXT_LEAVES => "text-leaves",
169            DICT_DATA => "dict",
170            INDEX_DATA => "index",
171            QUAD_DATA => "quad",
172            LABEL_DATA => "labels",
173            TEXT_DATA => "text",
174            PYRAMID => "pyramid",
175            LABEL_ROOT => "label-root",
176            CARD_ANNEX => "card-annex",
177            _ => "unknown",
178        }
179    }
180
181    /// Front sections live before the data region.
182    pub fn is_front(k: u8) -> bool {
183        k < DICT_DATA
184    }
185}
186
187/// Unit-root tags inside the root block.
188#[allow(missing_docs)]
189pub mod tag {
190    pub const DICT: u8 = 1;
191    pub const INDEX: u8 = 2;
192    pub const QUAD: u8 = 3;
193    pub const LABELS: u8 = 4;
194    pub const TEXT: u8 = 5;
195    /// `0x07`: the class clusters of the subject-leading permutations.
196    pub const CLUSTER: u8 = 6;
197}
198
199/// The parsed 128-byte header.
200#[derive(Debug, Clone, Default, PartialEq, Eq)]
201#[allow(missing_docs)]
202pub struct Header06 {
203    /// The format byte: [`VERSION_06`] or [`VERSION`].
204    pub version: u8,
205    pub flags: u8,
206    pub content_hash: [u8; 16],
207    pub file_len: u64,
208    pub root_len: u32,
209    pub card_region_len: u32,
210    pub data_offset: u64,
211    pub quad_count: u64,
212    pub term_count: u64,
213    pub graph_count: u64,
214    pub perm_mask: u8,
215    pub dict_codec: u8,
216    pub block_codec: u8,
217    pub internal_codec: u8,
218    pub pyramid_levels: u16,
219    /// Per-position term-id widths, 2 bits each (subjects, objects, predicates,
220    /// graphs from the low bits): 0 = u32, 1 = u64 (refused by this reader).
221    pub id_widths: u8,
222    pub presence: u16,
223    pub card_off: u32,
224    pub card_len: u32,
225    pub card_digest: [u8; 16],
226    pub build_off: u32,
227    pub build_len: u32,
228    pub root_digest: [u8; 16],
229}
230
231impl Header06 {
232    /// Serialize the fixed 128 bytes.
233    pub fn to_bytes(&self) -> [u8; HEADER_LEN] {
234        let mut b = [0u8; HEADER_LEN];
235        b[0..4].copy_from_slice(&crate::header::MAGIC);
236        b[4] = self.version;
237        b[5] = self.flags;
238        b[6..8].copy_from_slice(&(HEADER_LEN as u16).to_le_bytes());
239        b[8..24].copy_from_slice(&self.content_hash);
240        b[24..32].copy_from_slice(&self.file_len.to_le_bytes());
241        b[32..36].copy_from_slice(&self.root_len.to_le_bytes());
242        b[36..40].copy_from_slice(&self.card_region_len.to_le_bytes());
243        b[40..48].copy_from_slice(&self.data_offset.to_le_bytes());
244        b[48..56].copy_from_slice(&self.quad_count.to_le_bytes());
245        b[56..64].copy_from_slice(&self.term_count.to_le_bytes());
246        b[64..72].copy_from_slice(&self.graph_count.to_le_bytes());
247        b[72] = self.perm_mask;
248        b[73] = self.dict_codec;
249        b[74] = self.block_codec;
250        b[75] = self.internal_codec;
251        b[76] = self.pyramid_levels as u8;
252        b[77] = self.id_widths;
253        b[78..80].copy_from_slice(&self.presence.to_le_bytes());
254        b[80..84].copy_from_slice(&self.card_off.to_le_bytes());
255        b[84..88].copy_from_slice(&self.card_len.to_le_bytes());
256        b[88..104].copy_from_slice(&self.card_digest);
257        b[104..108].copy_from_slice(&self.build_off.to_le_bytes());
258        b[108..112].copy_from_slice(&self.build_len.to_le_bytes());
259        b[112..128].copy_from_slice(&self.root_digest);
260        b
261    }
262
263    /// Parse and bounds-check the fixed 128 bytes. Every field is untrusted.
264    pub fn from_bytes(b: &[u8]) -> Result<Self, FileError> {
265        if b.len() < HEADER_LEN {
266            return Err(FileError::Container("0x06 header truncated"));
267        }
268        if b[0..4] != crate::header::MAGIC || !reads(b[4]) {
269            return Err(FileError::Container("not a 0x06 or 0x07 file"));
270        }
271        if u16::from_le_bytes([b[6], b[7]]) as usize != HEADER_LEN {
272            return Err(FileError::Container("0x06 header length is not 128"));
273        }
274        let u32_at = |o: usize| u32::from_le_bytes(b[o..o + 4].try_into().unwrap());
275        let u64_at = |o: usize| u64::from_le_bytes(b[o..o + 8].try_into().unwrap());
276        let h16 = |o: usize| {
277            let mut x = [0u8; 16];
278            x.copy_from_slice(&b[o..o + 16]);
279            x
280        };
281        let h = Header06 {
282            version: b[4],
283            flags: b[5],
284            content_hash: h16(8),
285            file_len: u64_at(24),
286            root_len: u32_at(32),
287            card_region_len: u32_at(36),
288            data_offset: u64_at(40),
289            quad_count: u64_at(48),
290            term_count: u64_at(56),
291            graph_count: u64_at(64),
292            perm_mask: b[72],
293            dict_codec: b[73],
294            block_codec: b[74],
295            internal_codec: b[75],
296            pyramid_levels: b[76] as u16,
297            id_widths: b[77],
298            presence: u16::from_le_bytes([b[78], b[79]]),
299            card_off: u32_at(80),
300            card_len: u32_at(84),
301            card_digest: h16(88),
302            build_off: u32_at(104),
303            build_len: u32_at(108),
304            root_digest: h16(112),
305        };
306        // Structural bounds: the front must fit in the file, the card and the
307        // record in their region.
308        let front_min = (HEADER_LEN as u64)
309            .checked_add(h.root_len as u64)
310            .and_then(|x| x.checked_add(h.card_region_len as u64))
311            .ok_or(FileError::Container("0x06 front overflows"))?;
312        if front_min > h.data_offset || h.data_offset > h.file_len {
313            return Err(FileError::Container("0x06 front overruns the data region"));
314        }
315        let card_end = h.card_off as u64 + h.card_len as u64;
316        let build_end = h.build_off as u64 + h.build_len as u64;
317        if card_end > h.card_region_len as u64 || build_end > h.card_region_len as u64 {
318            return Err(FileError::Container("0x06 card region overrun"));
319        }
320        crate::index::PermSet::from_bits(h.perm_mask)
321            .map_err(|_| FileError::Container("0x06 permutation mask invalid"))?;
322        check_id_widths_byte(h.id_widths)?;
323        Ok(h)
324    }
325
326    /// Absolute offset of the root block.
327    pub fn root_offset(&self) -> u64 {
328        HEADER_LEN as u64
329    }
330    /// Absolute offset of the card region.
331    pub fn card_region_offset(&self) -> u64 {
332        HEADER_LEN as u64 + self.root_len as u64
333    }
334    /// Absolute offset where the front sections start (after the card region).
335    pub fn front_base(&self) -> u64 {
336        self.card_region_offset() + self.card_region_len as u64
337    }
338    /// The stored card's absolute range (`len == 0`: no card).
339    pub fn card_range(&self) -> crate::file::ByteRange {
340        crate::file::ByteRange {
341            offset: self.card_region_offset() + self.card_off as u64,
342            len: self.card_len as u64,
343        }
344    }
345    /// The build record's absolute range (`len == 0`: none).
346    pub fn build_range(&self) -> crate::file::ByteRange {
347        crate::file::ByteRange {
348            offset: self.card_region_offset() + self.build_off as u64,
349            len: self.build_len as u64,
350        }
351    }
352    /// The permutations the file carries.
353    pub fn perms(&self) -> crate::index::PermSet {
354        crate::index::PermSet::from_bits(self.perm_mask).unwrap_or(crate::index::PermSet::ALL)
355    }
356    /// Does the file carry this presence bit?
357    pub fn has(&self, bit: u16) -> bool {
358        self.presence & bit != 0
359    }
360}
361
362/// The first 16 bytes of a BLAKE3 digest.
363pub fn digest16(bytes: &[u8]) -> [u8; 16] {
364    let mut out = [0u8; 16];
365    out.copy_from_slice(&blake3::hash(bytes).as_bytes()[..16]);
366    out
367}
368
369/// Term-id position names, in the order of the 2-bit fields of header byte 77.
370const ID_POSITIONS: [&str; 4] = ["subjects", "objects", "predicates", "graphs"];
371
372/// Refuse a width byte this reader cannot honour: a reserved value (2, 3) is a
373/// corrupt header, a `u64` field is a file from a later writer.
374fn check_id_widths_byte(w: u8) -> Result<(), FileError> {
375    for i in 0..4 {
376        match (w >> (2 * i)) & 3 {
377            0 => {}
378            1 => {
379                return Err(FileError::Container(match i {
380                    0 => "u64 term ids (subjects): not supported by this reader",
381                    1 => "u64 term ids (objects): not supported by this reader",
382                    2 => "u64 term ids (predicates): not supported by this reader",
383                    _ => "u64 term ids (graphs): not supported by this reader",
384                }))
385            }
386            _ => return Err(FileError::Container("0x06 header: reserved term id width")),
387        }
388    }
389    Ok(())
390}
391
392/// The width byte a writer stamps: every position `u32` (0), after checking
393/// that the largest id of each position (`[subjects, objects, predicates,
394/// graphs]`, SPEC §4.1) fits. It
395/// never truncates: an id that does not fit is an error.
396pub fn id_widths_for(max_ids: [u64; 4]) -> Result<u8, FileError> {
397    for (i, m) in max_ids.iter().enumerate() {
398        if *m > u32::MAX as u64 {
399            return Err(FileError::Container(match i {
400                0 => "this dataset needs u64 term ids in subjects, not supported yet",
401                1 => "this dataset needs u64 term ids in objects, not supported yet",
402                2 => "this dataset needs u64 term ids in predicates, not supported yet",
403                _ => "this dataset needs u64 term ids in graphs, not supported yet",
404            }));
405        }
406    }
407    Ok(0)
408}
409
410/// Names of the four id positions, in field order, for display.
411pub fn id_position_names() -> [&'static str; 4] {
412    ID_POSITIONS
413}
414
415/// The content hash of a header whose card and root digests are set (SPEC.md
416/// §5): the logical header fields, the card and the root, never an offset and
417/// never the build record.
418pub fn content_hash(h: &Header06) -> [u8; 16] {
419    let b = h.to_bytes();
420    let mut x = blake3::Hasher::new();
421    x.update(if h.version == VERSION_06 {
422        b"rete/0x06"
423    } else {
424        b"rete/0x07"
425    });
426    x.update(&b[4..8]);
427    x.update(&b[48..80]);
428    x.update(&h.card_len.to_le_bytes());
429    x.update(&h.card_digest);
430    x.update(&h.root_len.to_le_bytes());
431    x.update(&h.root_digest);
432    let mut out = [0u8; 16];
433    out.copy_from_slice(&x.finalize().as_bytes()[..16]);
434    out
435}
436
437/// One entry of the root's section table.
438#[derive(Debug, Clone, Copy, PartialEq, Eq)]
439pub struct Sec06 {
440    /// [`kind`].
441    pub kind: u8,
442    /// The largest decompressed block of the section (a dictionary chunk, a
443    /// tile, a leaf, …), as the writer measured it; `0` = not recorded, read
444    /// under [`BLOCK_CEILING`]. Readers refuse to decode past it.
445    pub max_block: u32,
446    /// Offset relative to its region base (the front base, or `data_offset`).
447    pub offset: u64,
448    /// Stored length.
449    pub len: u64,
450    /// `BLAKE3(stored bytes)[..16]`.
451    pub digest: [u8; 16],
452}
453
454/// Size of one section-table entry.
455pub const SEC_ENTRY_LEN: usize = 38;
456
457/// The decompression bound of a section whose largest block is not recorded
458/// (label blocks and nodes; the writer cuts them at 16 KiB).
459pub const BLOCK_CEILING: u64 = 4 << 20;
460/// The bound on the root's unit roots, decompressed (Meta's are ~100 KiB).
461pub const UNIT_MAX: u64 = 16 << 20;
462/// The bound on the Dataset Card, decompressed.
463pub const CARD_MAX: u64 = 64 << 20;
464
465impl Sec06 {
466    /// The absolute byte range of this section in a file with header `h`;
467    /// an error when its offset or end overflows (a hostile root).
468    pub fn abs(&self, h: &Header06) -> Result<crate::file::ByteRange, crate::file::FileError> {
469        let base = if kind::is_front(self.kind) {
470            h.front_base()
471        } else {
472            h.data_offset
473        };
474        let overflow = || crate::file::FileError::Container("0x06 section overflows");
475        let offset = base.checked_add(self.offset).ok_or_else(overflow)?;
476        offset.checked_add(self.len).ok_or_else(overflow)?;
477        Ok(crate::file::ByteRange {
478            offset,
479            len: self.len,
480        })
481    }
482}
483
484/// The decoded root block.
485#[derive(Debug, Clone, Default)]
486pub struct Root06 {
487    /// The section table, in file order.
488    pub sections: Vec<Sec06>,
489    /// The unit roots, decompressed: `(tag, payload)`.
490    pub units: Vec<(u8, Vec<u8>)>,
491}
492
493impl Root06 {
494    /// The section of `kind`, if present.
495    pub fn section(&self, k: u8) -> Option<&Sec06> {
496        self.sections.iter().find(|s| s.kind == k)
497    }
498
499    /// The unit root payload with `tag`, if present.
500    pub fn unit(&self, t: u8) -> Option<&[u8]> {
501        self.units
502            .iter()
503            .find(|(x, _)| *x == t)
504            .map(|(_, p)| p.as_slice())
505    }
506
507    /// Serialize: the fixed section table, then the compressed unit roots.
508    pub fn encode(&self, codec: u8) -> Vec<u8> {
509        let mut units = Vec::new();
510        for (t, p) in &self.units {
511            units.push(*t);
512            write_uvarint(&mut units, p.len() as u64);
513            units.extend_from_slice(p);
514        }
515        let stored = crate::file::compress(codec, &units);
516        let mut out =
517            Vec::with_capacity(2 + SEC_ENTRY_LEN * self.sections.len() + 4 + stored.len());
518        out.push(1u8);
519        out.push(self.sections.len() as u8);
520        for s in &self.sections {
521            out.push(s.kind);
522            out.push(0);
523            out.extend_from_slice(&s.max_block.to_le_bytes());
524            out.extend_from_slice(&s.offset.to_le_bytes());
525            out.extend_from_slice(&s.len.to_le_bytes());
526            out.extend_from_slice(&s.digest);
527        }
528        out.extend_from_slice(&(stored.len() as u32).to_le_bytes());
529        out.extend_from_slice(&stored);
530        out
531    }
532
533    /// Parse a stored root block. Every count and length is untrusted.
534    pub fn decode(bytes: &[u8], codec: u8) -> Result<Self, FileError> {
535        let bad = |w| FileError::Container(w);
536        if bytes.len() < 2 || bytes[0] != 1 {
537            return Err(bad("0x06 root block: unknown version"));
538        }
539        let n = bytes[1] as usize;
540        let table_end = 2 + n * SEC_ENTRY_LEN;
541        if bytes.len() < table_end + 4 {
542            return Err(bad("0x06 root block truncated"));
543        }
544        let mut sections = Vec::with_capacity(n);
545        for i in 0..n {
546            let e = &bytes[2 + i * SEC_ENTRY_LEN..2 + (i + 1) * SEC_ENTRY_LEN];
547            let mut digest = [0u8; 16];
548            digest.copy_from_slice(&e[22..38]);
549            sections.push(Sec06 {
550                kind: e[0],
551                max_block: u32::from_le_bytes(e[2..6].try_into().unwrap()),
552                offset: u64::from_le_bytes(e[6..14].try_into().unwrap()),
553                len: u64::from_le_bytes(e[14..22].try_into().unwrap()),
554                digest,
555            });
556        }
557        let ulen = u32::from_le_bytes(bytes[table_end..table_end + 4].try_into().unwrap()) as usize;
558        let stored = bytes
559            .get(table_end + 4..table_end + 4 + ulen)
560            .ok_or(bad("0x06 root units overrun"))?;
561        let units_raw = crate::file::decompress_bounded(codec, stored, UNIT_MAX)?;
562        let mut units = Vec::new();
563        let mut c = Cur::new(&units_raw);
564        while !c.done() {
565            let t = c.u8()?;
566            let l = c.len()?;
567            units.push((t, c.bytes(l)?.to_vec()));
568        }
569        Ok(Root06 { sections, units })
570    }
571}
572
573/// A bounds-checked cursor over untrusted bytes.
574pub struct Cur<'a> {
575    b: &'a [u8],
576    /// Current position.
577    pub pos: usize,
578}
579
580// `len` reads a length varint; it is not the cursor's own length.
581#[allow(clippy::len_without_is_empty)]
582impl<'a> Cur<'a> {
583    /// A cursor at the start of `b`.
584    pub fn new(b: &'a [u8]) -> Self {
585        Cur { b, pos: 0 }
586    }
587    /// At the end?
588    pub fn done(&self) -> bool {
589        self.pos >= self.b.len()
590    }
591    /// One varint.
592    pub fn uv(&mut self) -> Result<u64, FileError> {
593        let (v, n) = read_uvarint(self.b.get(self.pos..).unwrap_or(&[]))
594            .ok_or(FileError::Container("0x06: truncated varint"))?;
595        self.pos += n;
596        Ok(v)
597    }
598    /// One varint as a `u32`.
599    pub fn u32v(&mut self) -> Result<u32, FileError> {
600        u32::try_from(self.uv()?).map_err(|_| FileError::Container("0x06: value exceeds u32"))
601    }
602    /// One varint as a length bounded by the remaining bytes.
603    pub fn len(&mut self) -> Result<usize, FileError> {
604        let v = self.uv()?;
605        let rest = self.b.len().saturating_sub(self.pos) as u64;
606        if v > rest {
607            return Err(FileError::Container("0x06: length overruns"));
608        }
609        Ok(v as usize)
610    }
611    /// One varint as a count, sanity-bounded by `max`.
612    pub fn count(&mut self, max: u64) -> Result<usize, FileError> {
613        let v = self.uv()?;
614        if v > max {
615            return Err(FileError::Container("0x06: count out of range"));
616        }
617        Ok(v as usize)
618    }
619    /// One byte.
620    pub fn u8(&mut self) -> Result<u8, FileError> {
621        let v = *self
622            .b
623            .get(self.pos)
624            .ok_or(FileError::Container("0x06: truncated"))?;
625        self.pos += 1;
626        Ok(v)
627    }
628    /// `n` raw bytes.
629    pub fn bytes(&mut self, n: usize) -> Result<&'a [u8], FileError> {
630        let s = self
631            .b
632            .get(
633                self.pos
634                    ..self
635                        .pos
636                        .checked_add(n)
637                        .ok_or(FileError::Container("0x06: overflow"))?,
638            )
639            .ok_or(FileError::Container("0x06: truncated bytes"))?;
640        self.pos += n;
641        Ok(s)
642    }
643    /// A length-prefixed byte string.
644    pub fn lp(&mut self) -> Result<&'a [u8], FileError> {
645        let n = self.len()?;
646        self.bytes(n)
647    }
648}
649
650/// Append a length-prefixed byte string.
651pub fn put_lp(out: &mut Vec<u8>, b: &[u8]) {
652    write_uvarint(out, b.len() as u64);
653    out.extend_from_slice(b);
654}
655
656// ---------------------------------------------------------------------------
657// Unit roots
658// ---------------------------------------------------------------------------
659
660/// One leaf of a two-level directory, as the root describes it.
661#[derive(Debug, Clone, PartialEq, Eq, Default)]
662pub struct LeafRef {
663    /// Index of the leaf's first entry in the whole unit.
664    pub first: usize,
665    /// Entries in the leaf.
666    pub n: usize,
667    /// Leaf offset within its leaves section.
668    pub off: u64,
669    /// Stored (compressed) leaf length.
670    pub len: u64,
671}
672
673/// The root of one dictionary section.
674#[derive(Debug, Clone, Default)]
675pub struct DictSecRoot {
676    /// Terms in the section.
677    pub term_count: u32,
678    /// Restart interval of its front-coded runs.
679    pub restart_interval: u32,
680    /// Chunks in the section.
681    pub n_chunks: usize,
682    /// Offset of the section's first chunk within DICT_DATA.
683    pub data_off: u64,
684    /// Bytes of chunk data.
685    pub data_len: u64,
686    /// Leaves: `(leaf, first run, chunk offset within the section's data, first key)`.
687    pub leaves: Vec<(LeafRef, usize, u64, Vec<u8>)>,
688}
689
690/// Encode the dictionary unit root.
691pub fn encode_dict_root(secs: &[DictSecRoot; 4]) -> Vec<u8> {
692    let mut o = Vec::new();
693    for s in secs {
694        write_uvarint(&mut o, s.term_count as u64);
695        write_uvarint(&mut o, s.restart_interval as u64);
696        write_uvarint(&mut o, s.n_chunks as u64);
697        write_uvarint(&mut o, s.data_off);
698        write_uvarint(&mut o, s.data_len);
699        write_uvarint(&mut o, s.leaves.len() as u64);
700        for (l, run, coff, key) in &s.leaves {
701            write_uvarint(&mut o, l.n as u64);
702            write_uvarint(&mut o, l.off);
703            write_uvarint(&mut o, l.len);
704            write_uvarint(&mut o, *run as u64);
705            write_uvarint(&mut o, *coff);
706            put_lp(&mut o, key);
707        }
708    }
709    o
710}
711
712/// Decode the dictionary unit root.
713pub fn decode_dict_root(p: &[u8]) -> Result<[DictSecRoot; 4], FileError> {
714    let mut c = Cur::new(p);
715    let mut out: [DictSecRoot; 4] = Default::default();
716    for s in out.iter_mut() {
717        s.term_count = c.u32v()?;
718        s.restart_interval = c.u32v()?;
719        s.n_chunks = c.count(u32::MAX as u64)?;
720        s.data_off = c.uv()?;
721        s.data_len = c.uv()?;
722        let nl = c.count(p.len() as u64)?;
723        let mut first = 0usize;
724        for _ in 0..nl {
725            let n = c.count(u32::MAX as u64)?;
726            let off = c.uv()?;
727            let len = c.uv()?;
728            let run = c.count(u64::MAX)?;
729            let coff = c.uv()?;
730            let key = c.lp()?.to_vec();
731            s.leaves
732                .push((LeafRef { first, n, off, len }, run, coff, key));
733            first = first
734                .checked_add(n)
735                .ok_or(FileError::Container("0x06 dict leaves overflow"))?;
736        }
737        if first != s.n_chunks {
738            return Err(FileError::Container(
739                "0x06 dict leaves do not cover the chunks",
740            ));
741        }
742        if s.restart_interval == 0 && s.term_count > 0 {
743            return Err(FileError::Container("0x06 dict zero restart interval"));
744        }
745    }
746    Ok(out)
747}
748
749/// The root of one permutation's tile directory.
750#[derive(Debug, Clone, Default)]
751pub struct PermRoot {
752    /// Section index (`IndexPermutation::section_index`).
753    pub si: usize,
754    /// Tiles.
755    pub n_tiles: usize,
756    /// Offset of the permutation's first tile within INDEX_DATA.
757    pub data_off: u64,
758    /// Bytes of tiles.
759    pub data_len: u64,
760    /// Leaves: `(leaf, first min_a, last max_a, tile offset within the permutation's data)`.
761    pub leaves: Vec<(LeafRef, u32, u32, u64)>,
762}
763
764/// Encode the index unit root (permutations in section-index order).
765pub fn encode_index_root(perms: &[PermRoot]) -> Vec<u8> {
766    let mut o = Vec::new();
767    write_uvarint(&mut o, perms.len() as u64);
768    for p in perms {
769        write_uvarint(&mut o, p.si as u64);
770        write_uvarint(&mut o, p.n_tiles as u64);
771        write_uvarint(&mut o, p.data_off);
772        write_uvarint(&mut o, p.data_len);
773        write_uvarint(&mut o, p.leaves.len() as u64);
774        for (l, mn, mx, toff) in &p.leaves {
775            write_uvarint(&mut o, l.n as u64);
776            write_uvarint(&mut o, l.off);
777            write_uvarint(&mut o, l.len);
778            write_uvarint(&mut o, *mn as u64);
779            write_uvarint(&mut o, *mx as u64);
780            write_uvarint(&mut o, *toff);
781        }
782    }
783    o
784}
785
786/// Decode the index unit root.
787pub fn decode_index_root(p: &[u8]) -> Result<Vec<PermRoot>, FileError> {
788    let mut c = Cur::new(p);
789    let n = c.count(6)?;
790    let mut out = Vec::with_capacity(n);
791    for _ in 0..n {
792        let si = c.count(5)?;
793        let n_tiles = c.count(u32::MAX as u64)?;
794        let data_off = c.uv()?;
795        let data_len = c.uv()?;
796        let nl = c.count(p.len() as u64)?;
797        let mut leaves = Vec::with_capacity(nl.min(p.len() / 5));
798        let mut first = 0usize;
799        for _ in 0..nl {
800            let ln = c.count(u32::MAX as u64)?;
801            let off = c.uv()?;
802            let len = c.uv()?;
803            let mn = c.u32v()?;
804            let mx = c.u32v()?;
805            let toff = c.uv()?;
806            leaves.push((
807                LeafRef {
808                    first,
809                    n: ln,
810                    off,
811                    len,
812                },
813                mn,
814                mx,
815                toff,
816            ));
817            first = first
818                .checked_add(ln)
819                .ok_or(FileError::Container("0x06 index leaves overflow"))?;
820        }
821        if first != n_tiles {
822            return Err(FileError::Container(
823                "0x06 index leaves do not cover the tiles",
824            ));
825        }
826        out.push(PermRoot {
827            si,
828            n_tiles,
829            data_off,
830            data_len,
831            leaves,
832        });
833    }
834    Ok(out)
835}
836
837/// The class clusters of one subject-leading order (`0x07`, flag
838/// [`F_CLUSTERED`]): a permutation of the default graph (`si` 0 to 5, SPO or
839/// SOP) or the quad index's SPOG (`si` [`QUAD_SPOG`]). Its tiles are `k + 1` consecutive runs: run 0 holds the
840/// subjects of no listed class, run `i` (1-based) those whose primary class is
841/// `classes[i - 1]`. Within a run the tiles are in `(s, p, o)` order like an
842/// unclustered permutation; no tile and no directory leaf spans two runs.
843#[derive(Debug, Clone, Default, PartialEq, Eq)]
844pub struct ClusterOrder {
845    /// Section index of the permutation (`IndexPermutation::section_index`), or
846    /// [`QUAD_SPOG`] for the quad index's SPOG (its quad slot).
847    pub si: usize,
848    /// The class of runs `1..=k`, as object ids, rarest last.
849    pub classes: Vec<u32>,
850    /// Tiles of each run, run 0 first (`classes.len() + 1` entries).
851    pub run_tiles: Vec<usize>,
852}
853
854/// Encode the cluster unit root.
855pub fn encode_cluster_root(orders: &[ClusterOrder]) -> Vec<u8> {
856    let mut o = Vec::new();
857    write_uvarint(&mut o, orders.len() as u64);
858    for c in orders {
859        write_uvarint(&mut o, c.si as u64);
860        write_uvarint(&mut o, c.classes.len() as u64);
861        for &k in &c.classes {
862            write_uvarint(&mut o, k as u64);
863        }
864        for &t in &c.run_tiles {
865            write_uvarint(&mut o, t as u64);
866        }
867    }
868    o
869}
870
871/// Decode the cluster unit root. Every count is untrusted.
872pub fn decode_cluster_root(p: &[u8]) -> Result<Vec<ClusterOrder>, FileError> {
873    let bad = FileError::Container;
874    let mut c = Cur::new(p);
875    let n = c.count(7)?;
876    let mut out: Vec<ClusterOrder> = Vec::with_capacity(n);
877    for _ in 0..n {
878        let si = c.count(QUAD_SPOG as u64)?;
879        let k = c.count(MAX_CLUSTERS as u64)?;
880        let mut classes = Vec::with_capacity(k);
881        for _ in 0..k {
882            let id = c.u32v()?;
883            if id == 0 || classes.contains(&id) {
884                return Err(bad("0x07 cluster root: bad class"));
885            }
886            classes.push(id);
887        }
888        let mut run_tiles = Vec::with_capacity(k + 1);
889        for _ in 0..=k {
890            run_tiles.push(c.count(u32::MAX as u64)?);
891        }
892        if out.iter().any(|o| o.si == si) {
893            return Err(bad("0x07 cluster root: a permutation twice"));
894        }
895        out.push(ClusterOrder {
896            si,
897            classes,
898            run_tiles,
899        });
900    }
901    Ok(out)
902}
903
904/// The root of the text index.
905#[derive(Debug, Clone, Default)]
906pub struct TextRoot {
907    /// The scope block (empty for the default scope).
908    pub scope: Vec<u8>,
909    /// Distinct tokens.
910    pub n_tokens: usize,
911    /// Leaves: `(leaf, first token)`.
912    pub leaves: Vec<(LeafRef, Vec<u8>)>,
913}
914
915/// Encode the text unit root.
916pub fn encode_text_root(t: &TextRoot) -> Vec<u8> {
917    let mut o = Vec::new();
918    put_lp(&mut o, &t.scope);
919    write_uvarint(&mut o, t.n_tokens as u64);
920    write_uvarint(&mut o, t.leaves.len() as u64);
921    for (l, first) in &t.leaves {
922        write_uvarint(&mut o, l.n as u64);
923        write_uvarint(&mut o, l.off);
924        write_uvarint(&mut o, l.len);
925        put_lp(&mut o, first);
926    }
927    o
928}
929
930/// Decode the text unit root.
931pub fn decode_text_root(p: &[u8]) -> Result<TextRoot, FileError> {
932    let mut c = Cur::new(p);
933    let scope = c.lp()?.to_vec();
934    let n_tokens = c.count(u32::MAX as u64)?;
935    let nl = c.count(p.len() as u64)?;
936    let mut leaves = Vec::with_capacity(nl.min(p.len() / 5));
937    let mut first = 0usize;
938    for _ in 0..nl {
939        let n = c.count(u32::MAX as u64)?;
940        let off = c.uv()?;
941        let len = c.uv()?;
942        let tok = c.lp()?.to_vec();
943        leaves.push((LeafRef { first, n, off, len }, tok));
944        first = first
945            .checked_add(n)
946            .ok_or(FileError::Container("0x06 text leaves overflow"))?;
947    }
948    if first != n_tokens {
949        return Err(FileError::Container(
950            "0x06 text leaves do not cover the tokens",
951        ));
952    }
953    Ok(TextRoot {
954        scope,
955        n_tokens,
956        leaves,
957    })
958}
959
960/// The root of the label index: the 0x05 preamble and root node, and where the
961/// data blocks end in the 0x05 body coordinates (SPEC.md §6.4).
962#[derive(Debug, Clone, Default)]
963pub struct LabelRoot {
964    /// Bytes of data blocks (the 0x05 body offsets below this are blocks, the
965    /// rest are directory nodes).
966    pub data_len: u64,
967    /// The 32-byte 0x05 preamble (digest zeroed) followed by the root node.
968    pub head: Vec<u8>,
969}
970
971/// Encode the label unit root.
972pub fn encode_label_root(l: &LabelRoot) -> Vec<u8> {
973    let mut o = Vec::new();
974    write_uvarint(&mut o, l.data_len);
975    put_lp(&mut o, &l.head);
976    o
977}
978
979/// Decode the label unit root.
980pub fn decode_label_root(p: &[u8]) -> Result<LabelRoot, FileError> {
981    let mut c = Cur::new(p);
982    let data_len = c.uv()?;
983    let head = c.lp()?.to_vec();
984    if head.len() < 32 {
985        return Err(FileError::Container("0x06 label root truncated"));
986    }
987    Ok(LabelRoot { data_len, head })
988}
989
990/// `G+SPO`, `SPO+G`, ...: the name of a quad order by its slot (SPEC.md §6.5).
991pub fn quad_order_name(si: usize) -> String {
992    crate::quad7::slot_name(si)
993}
994
995/// The root of the quad index.
996#[derive(Debug, Clone, Default)]
997pub struct QuadRoot {
998    /// Named graphs.
999    pub graph_count: u64,
1000    /// Named-graph quads.
1001    pub quad_count: u64,
1002    /// Graphs per graph-directory block.
1003    pub block_graphs: u64,
1004    /// The 0x05 `P0`: the graph-directory block index (offsets from the start of
1005    /// QUAD_LEAVES, where the blocks are).
1006    pub p0: Vec<u8>,
1007    /// Bytes of graph-directory blocks at the start of QUAD_LEAVES.
1008    pub gdir_len: u64,
1009    /// Per order present (mask order): `(section index, tiles, leaves)`; a leaf
1010    /// is `(leaf, first (g, a), last (g, a), offset of its first tile in QUAD_DATA)`.
1011    pub orders: Vec<QuadOrderRoot>,
1012}
1013
1014/// One order of the quad index.
1015#[derive(Debug, Clone, Default)]
1016pub struct QuadOrderRoot {
1017    /// Section index of the order (`G+X` uses `X`'s index).
1018    pub si: usize,
1019    /// Tiles.
1020    pub n_tiles: usize,
1021    /// Leaves.
1022    pub leaves: Vec<QuadLeafRoot>,
1023}
1024
1025/// A quad order's leaf in the root: the leaf, the first tile's first `(g, a)`,
1026/// the last tile's last `(g, a)`, and the first tile's offset in `quad`.
1027pub type QuadLeafRoot = (LeafRef, (u32, u32), (u32, u32), u64);
1028
1029/// Encode the quad unit root.
1030pub fn encode_quad_root(q: &QuadRoot) -> Vec<u8> {
1031    let mut o = Vec::new();
1032    write_uvarint(&mut o, q.graph_count);
1033    write_uvarint(&mut o, q.quad_count);
1034    write_uvarint(&mut o, q.block_graphs);
1035    put_lp(&mut o, &q.p0);
1036    write_uvarint(&mut o, q.gdir_len);
1037    write_uvarint(&mut o, q.orders.len() as u64);
1038    for ord in &q.orders {
1039        write_uvarint(&mut o, ord.si as u64);
1040        write_uvarint(&mut o, ord.n_tiles as u64);
1041        write_uvarint(&mut o, ord.leaves.len() as u64);
1042        for (l, f, la, toff) in &ord.leaves {
1043            write_uvarint(&mut o, l.n as u64);
1044            write_uvarint(&mut o, l.off);
1045            write_uvarint(&mut o, l.len);
1046            write_uvarint(&mut o, f.0 as u64);
1047            write_uvarint(&mut o, f.1 as u64);
1048            write_uvarint(&mut o, la.0 as u64);
1049            write_uvarint(&mut o, la.1 as u64);
1050            write_uvarint(&mut o, *toff);
1051        }
1052    }
1053    o
1054}
1055
1056/// Decode the quad unit root.
1057pub fn decode_quad_root(p: &[u8]) -> Result<QuadRoot, FileError> {
1058    let mut c = Cur::new(p);
1059    let graph_count = c.uv()?;
1060    let quad_count = c.uv()?;
1061    let block_graphs = c.uv()?;
1062    let p0 = c.lp()?.to_vec();
1063    let gdir_len = c.uv()?;
1064    let no = c.count(crate::quad7::NUM_SLOTS as u64)?;
1065    let mut orders = Vec::with_capacity(no);
1066    for _ in 0..no {
1067        let si = c.count(crate::quad7::NUM_SLOTS as u64 - 1)?;
1068        let n_tiles = c.count(u32::MAX as u64)?;
1069        let nl = c.count(p.len() as u64)?;
1070        let mut leaves = Vec::with_capacity(nl.min(p.len() / 5));
1071        let mut first = 0usize;
1072        for _ in 0..nl {
1073            let n = c.count(u32::MAX as u64)?;
1074            let off = c.uv()?;
1075            let len = c.uv()?;
1076            let f = (c.u32v()?, c.u32v()?);
1077            let la = (c.u32v()?, c.u32v()?);
1078            let toff = c.uv()?;
1079            leaves.push((LeafRef { first, n, off, len }, f, la, toff));
1080            first = first
1081                .checked_add(n)
1082                .ok_or(FileError::Container("0x06 quad leaves overflow"))?;
1083        }
1084        if first != n_tiles {
1085            return Err(FileError::Container(
1086                "0x06 quad leaves do not cover the tiles",
1087            ));
1088        }
1089        orders.push(QuadOrderRoot {
1090            si,
1091            n_tiles,
1092            leaves,
1093        });
1094    }
1095    if block_graphs == 0 && graph_count > 0 {
1096        return Err(FileError::Container("0x06 quad block size is zero"));
1097    }
1098    Ok(QuadRoot {
1099        graph_count,
1100        quad_count,
1101        block_graphs,
1102        p0,
1103        gdir_len,
1104        orders,
1105    })
1106}
1107
1108// ---------------------------------------------------------------------------
1109// Leaf entries
1110// ---------------------------------------------------------------------------
1111
1112/// One dictionary chunk as a leaf lists it.
1113#[derive(Debug, Clone, PartialEq, Eq)]
1114pub struct ChunkEnt {
1115    /// Index of the chunk's first front-coded run.
1116    pub first_run: usize,
1117    /// Routing separator (SPEC.md §6.2).
1118    pub key: Vec<u8>,
1119    /// Compressed chunk length.
1120    pub clen: u64,
1121}
1122
1123/// Encode chunk entries (the first `first_run` absolute, then deltas).
1124pub fn encode_chunk_leaf(ents: &[ChunkEnt]) -> Vec<u8> {
1125    let mut o = Vec::new();
1126    let mut prev = 0usize;
1127    for (i, e) in ents.iter().enumerate() {
1128        write_uvarint(
1129            &mut o,
1130            (if i == 0 {
1131                e.first_run
1132            } else {
1133                e.first_run - prev
1134            }) as u64,
1135        );
1136        put_lp(&mut o, &e.key);
1137        write_uvarint(&mut o, e.clen);
1138        prev = e.first_run;
1139    }
1140    o
1141}
1142
1143/// Decode `n` chunk entries.
1144pub fn decode_chunk_leaf(b: &[u8], n: usize) -> Result<Vec<ChunkEnt>, FileError> {
1145    let mut c = Cur::new(b);
1146    let mut out = Vec::with_capacity(n.min(b.len()));
1147    let mut prev = 0usize;
1148    for i in 0..n {
1149        let d = c.count(u64::MAX)?;
1150        let first_run = if i == 0 {
1151            d
1152        } else {
1153            prev.checked_add(d)
1154                .ok_or(FileError::Container("0x06 chunk run overflow"))?
1155        };
1156        let key = c.lp()?.to_vec();
1157        let clen = c.uv()?;
1158        out.push(ChunkEnt {
1159            first_run,
1160            key,
1161            clen,
1162        });
1163        prev = first_run;
1164    }
1165    Ok(out)
1166}
1167
1168/// One index tile as a leaf lists it.
1169#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1170pub struct TileEnt {
1171    /// Leading-id range.
1172    pub min_a: u32,
1173    /// Leading-id range, inclusive.
1174    pub max_a: u32,
1175    /// Compressed length.
1176    pub clen: u64,
1177    /// `(min_b, max_b, min_c, max_c)`.
1178    pub syn: (u32, u32, u32, u32),
1179}
1180
1181/// Encode tile entries: the 0x05 directory rows, then the synopsis rows.
1182pub fn encode_tile_leaf(ents: &[TileEnt]) -> Vec<u8> {
1183    let mut o = Vec::new();
1184    let mut prev = 0u32;
1185    for (i, e) in ents.iter().enumerate() {
1186        write_uvarint(
1187            &mut o,
1188            (if i == 0 {
1189                e.min_a
1190            } else {
1191                e.min_a.wrapping_sub(prev)
1192            }) as u64,
1193        );
1194        write_uvarint(&mut o, e.max_a.wrapping_sub(e.min_a) as u64);
1195        write_uvarint(&mut o, e.clen);
1196        prev = e.min_a;
1197    }
1198    for e in ents {
1199        write_uvarint(&mut o, e.syn.0 as u64);
1200        write_uvarint(&mut o, e.syn.1.wrapping_sub(e.syn.0) as u64);
1201        write_uvarint(&mut o, e.syn.2 as u64);
1202        write_uvarint(&mut o, e.syn.3.wrapping_sub(e.syn.2) as u64);
1203    }
1204    o
1205}
1206
1207/// Decode `n` tile entries.
1208pub fn decode_tile_leaf(b: &[u8], n: usize) -> Result<Vec<TileEnt>, FileError> {
1209    let mut c = Cur::new(b);
1210    let mut out = Vec::with_capacity(n.min(b.len()));
1211    let mut prev = 0u32;
1212    for i in 0..n {
1213        let d = c.u32v()?;
1214        let min_a = if i == 0 { d } else { prev.wrapping_add(d) };
1215        let span = c.u32v()?;
1216        let clen = c.uv()?;
1217        out.push(TileEnt {
1218            min_a,
1219            max_a: min_a.wrapping_add(span),
1220            clen,
1221            syn: (0, 0, 0, 0),
1222        });
1223        prev = min_a;
1224    }
1225    for e in out.iter_mut() {
1226        let mb = c.u32v()?;
1227        let db = c.u32v()?;
1228        let mc = c.u32v()?;
1229        let dc = c.u32v()?;
1230        e.syn = (mb, mb.wrapping_add(db), mc, mc.wrapping_add(dc));
1231    }
1232    Ok(out)
1233}
1234
1235/// One text token as a leaf lists it.
1236#[derive(Debug, Clone, PartialEq, Eq)]
1237pub struct TokenEnt {
1238    /// The token.
1239    pub token: Vec<u8>,
1240    /// Posting offset within TEXT_DATA.
1241    pub off: u64,
1242    /// Posting length.
1243    pub len: u64,
1244}
1245
1246/// Encode token entries, front-coded within the leaf.
1247pub fn encode_token_leaf(ents: &[TokenEnt]) -> Vec<u8> {
1248    let mut o = Vec::new();
1249    let mut prev: &[u8] = &[];
1250    for e in ents {
1251        let shared = prev
1252            .iter()
1253            .zip(&e.token)
1254            .take_while(|(a, b)| a == b)
1255            .count();
1256        write_uvarint(&mut o, shared as u64);
1257        put_lp(&mut o, &e.token[shared..]);
1258        write_uvarint(&mut o, e.off);
1259        write_uvarint(&mut o, e.len);
1260        prev = &e.token;
1261    }
1262    o
1263}
1264
1265/// Decode `n` token entries.
1266pub fn decode_token_leaf(b: &[u8], n: usize) -> Result<Vec<TokenEnt>, FileError> {
1267    let mut c = Cur::new(b);
1268    let mut out: Vec<TokenEnt> = Vec::with_capacity(n.min(b.len()));
1269    for _ in 0..n {
1270        let shared = c.count(u32::MAX as u64)?;
1271        let suffix = c.lp()?;
1272        let mut token = match out.last() {
1273            Some(p) if shared <= p.token.len() => p.token[..shared].to_vec(),
1274            None if shared == 0 => Vec::new(),
1275            _ => return Err(FileError::Container("0x06 token front-coding out of range")),
1276        };
1277        token.extend_from_slice(suffix);
1278        let off = c.uv()?;
1279        let len = c.uv()?;
1280        out.push(TokenEnt { token, off, len });
1281    }
1282    Ok(out)
1283}
1284
1285/// One quad tile as a leaf lists it.
1286#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1287pub struct QTileEnt {
1288    /// Leading key of the first row: `(g, a)` of a graph-leading order, `(a, b)`
1289    /// of a graph-last one.
1290    pub first: (u32, u32),
1291    /// Leading key of the last row.
1292    pub last: (u32, u32),
1293    /// Stored length.
1294    pub clen: u64,
1295    /// Stored raw (not compressed).
1296    pub raw: bool,
1297    /// `(min_b, max_b, min_c, max_c)` of a graph-leading order; `(min_c, max_c,
1298    /// min_g, max_g)` of a graph-last one.
1299    pub syn: (u32, u32, u32, u32),
1300    /// Absolute offset of the tile within QUAD_DATA.
1301    pub off: u64,
1302}
1303
1304/// Encode quad tile entries. A tile's offset is written as `0` when it follows
1305/// the previous tile of the leaf (or, for the first, sits at the leaf's root
1306/// offset), else as `offset + 1` (PMTiles' clustered encoding). A `0x07` file
1307/// is order-major, so its tiles always follow each other and the field is
1308/// not written (`contiguous`).
1309pub fn encode_qtile_leaf(ents: &[QTileEnt], leaf_off: u64, contiguous: bool) -> Vec<u8> {
1310    let mut o = Vec::new();
1311    let mut prev_g = 0u32;
1312    let mut next = leaf_off;
1313    for (i, e) in ents.iter().enumerate() {
1314        write_uvarint(
1315            &mut o,
1316            (if i == 0 {
1317                e.first.0
1318            } else {
1319                e.first.0 - prev_g
1320            }) as u64,
1321        );
1322        write_uvarint(&mut o, e.first.1 as u64);
1323        write_uvarint(&mut o, (e.last.0 - e.first.0) as u64);
1324        write_uvarint(&mut o, e.last.1 as u64);
1325        write_uvarint(&mut o, (e.clen << 1) | e.raw as u64);
1326        write_uvarint(&mut o, e.syn.0 as u64);
1327        write_uvarint(&mut o, e.syn.1.wrapping_sub(e.syn.0) as u64);
1328        write_uvarint(&mut o, e.syn.2 as u64);
1329        write_uvarint(&mut o, e.syn.3.wrapping_sub(e.syn.2) as u64);
1330        if !contiguous {
1331            write_uvarint(&mut o, if e.off == next { 0 } else { e.off + 1 });
1332        }
1333        next = e.off + e.clen;
1334        prev_g = e.first.0;
1335    }
1336    o
1337}
1338
1339/// Decode `n` quad tile entries of a leaf whose first tile sits at `leaf_off`.
1340pub fn decode_qtile_leaf(
1341    b: &[u8],
1342    n: usize,
1343    leaf_off: u64,
1344    contiguous: bool,
1345) -> Result<Vec<QTileEnt>, FileError> {
1346    let mut c = Cur::new(b);
1347    let mut out = Vec::with_capacity(n.min(b.len()));
1348    let mut prev_g = 0u32;
1349    let mut next = leaf_off;
1350    for i in 0..n {
1351        let d = c.u32v()?;
1352        let g = if i == 0 {
1353            d
1354        } else {
1355            prev_g
1356                .checked_add(d)
1357                .ok_or(FileError::Container("0x06 quad graph overflow"))?
1358        };
1359        let fa = c.u32v()?;
1360        let dg = c.u32v()?;
1361        let la = c.u32v()?;
1362        let packed = c.uv()?;
1363        let mb = c.u32v()?;
1364        let db = c.u32v()?;
1365        let mc = c.u32v()?;
1366        let dc = c.u32v()?;
1367        let off = if contiguous {
1368            next
1369        } else {
1370            match c.uv()? {
1371                0 => next,
1372                oc => oc - 1,
1373            }
1374        };
1375        let clen = packed >> 1;
1376        out.push(QTileEnt {
1377            first: (g, fa),
1378            last: (
1379                g.checked_add(dg)
1380                    .ok_or(FileError::Container("0x06 quad graph overflow"))?,
1381                la,
1382            ),
1383            clen,
1384            raw: packed & 1 == 1,
1385            syn: (mb, mb.wrapping_add(db), mc, mc.wrapping_add(dc)),
1386            off,
1387        });
1388        next = off
1389            .checked_add(clen)
1390            .ok_or(FileError::Container("0x06 quad offset overflow"))?;
1391        prev_g = g;
1392    }
1393    Ok(out)
1394}
1395
1396/// Cut `sizes` (each entry's encoded size) into leaves of about `target`
1397/// bytes: `(start, end)` index ranges, never empty, covering everything.
1398pub fn cut(sizes: &[usize], target: usize) -> Vec<(usize, usize)> {
1399    let mut out = Vec::new();
1400    let mut start = 0usize;
1401    let mut acc = 0usize;
1402    for (i, &s) in sizes.iter().enumerate() {
1403        acc += s;
1404        if acc >= target {
1405            out.push((start, i + 1));
1406            start = i + 1;
1407            acc = 0;
1408        }
1409    }
1410    if start < sizes.len() {
1411        out.push((start, sizes.len()));
1412    }
1413    out
1414}
1415
1416/// A logical, 0x05-shaped [`crate::header::Header`] for a 0x06 file, so code
1417/// that asks presence questions (`text_index_len > 0`, `label_index_section()`)
1418/// answers them the same for both formats. Its offsets all point at the end of
1419/// the file, so a physical read that was not ported to 0x06 fails loudly instead
1420/// of reading the wrong bytes.
1421pub fn logical_header(h: &Header06) -> crate::header::Header {
1422    use crate::header::{Section, SectionKind};
1423    let end = h.file_len;
1424    let mut flags = crate::header::FLAG_TILE_SYNOPSIS;
1425    if h.flags & F_NAMED != 0 {
1426        flags |= crate::header::FLAG_HAS_QUADS;
1427    }
1428    if h.flags & F_QUOTED != 0 {
1429        flags |= crate::header::FLAG_HAS_QUOTED_TRIPLES;
1430    }
1431    if h.has(P_QUAD) {
1432        flags |= crate::header::FLAG_QUAD_INDEX;
1433    }
1434    if h.flags & F_TEXT_NAMED != 0 && h.has(P_TEXT) {
1435        flags |= crate::header::FLAG_TEXT_INDEX_NAMED_GRAPHS;
1436    }
1437    let present = |bit: u16| if h.has(bit) { 1u64 } else { 0 };
1438    let mut extra = Vec::new();
1439    if h.has(P_LABELS) {
1440        extra.push(Section {
1441            kind: SectionKind::LabelIndex,
1442            flags: 0,
1443            offset: end,
1444            length: 1,
1445        });
1446    }
1447    if h.has(P_SCHEMA) {
1448        extra.push(Section {
1449            kind: SectionKind::Schema,
1450            flags: 0,
1451            offset: end,
1452            length: 1,
1453        });
1454    }
1455    if h.has(P_QUAD) {
1456        extra.push(Section {
1457            kind: SectionKind::QuadIndex,
1458            flags: 0,
1459            offset: end,
1460            length: 1,
1461        });
1462    }
1463    crate::header::Header {
1464        version: h.version,
1465        flags,
1466        metadata_offset: end,
1467        metadata_len: h.card_len as u64,
1468        dictionary_offset: end,
1469        dictionary_len: 0,
1470        root_dir_offset: end,
1471        root_dir_len: 0,
1472        pyramid_meta_offset: end,
1473        pyramid_meta_len: present(P_PYRAMID),
1474        dict_codec: h.dict_codec,
1475        block_codec: h.block_codec,
1476        pyramid_levels: h.pyramid_levels,
1477        id_widths: h.id_widths,
1478        quad_count: h.quad_count,
1479        term_count: h.term_count,
1480        content_hash: h.content_hash,
1481        named_graphs_offset: 0,
1482        named_graphs_len: 0,
1483        schema_meta_len: 0,
1484        text_index_offset: end,
1485        text_index_len: present(P_TEXT),
1486        text_index_partial: h.has(P_TEXT_PARTIAL),
1487        build_info_offset: end,
1488        build_info_len: h.build_len as u64,
1489        perms: h.perms(),
1490        extra_sections: extra,
1491    }
1492}
1493
1494#[cfg(test)]
1495mod tests {
1496    use super::*;
1497
1498    #[test]
1499    fn header_round_trips() {
1500        let h = Header06 {
1501            version: VERSION,
1502            flags: F_NAMED | F_QUAD_GRAPH_MAJOR,
1503            content_hash: [7; 16],
1504            file_len: 10_000,
1505            root_len: 300,
1506            card_region_len: 100,
1507            data_offset: 2_000,
1508            quad_count: 5,
1509            term_count: 9,
1510            graph_count: 2,
1511            perm_mask: 0b11_1111,
1512            dict_codec: 1,
1513            block_codec: 1,
1514            internal_codec: 1,
1515            pyramid_levels: 0,
1516            id_widths: 0,
1517            presence: P_TEXT | P_QUAD,
1518            card_off: 0,
1519            card_len: 40,
1520            card_digest: [3; 16],
1521            build_off: 40,
1522            build_len: 20,
1523            root_digest: [4; 16],
1524        };
1525        let b = h.to_bytes();
1526        assert_eq!(Header06::from_bytes(&b).unwrap(), h);
1527        // The hash ignores offsets and the build record.
1528        let mut h2 = h.clone();
1529        h2.data_offset = 3_000;
1530        h2.build_len = 0;
1531        h2.file_len = 11_000;
1532        assert_eq!(content_hash(&h), content_hash(&h2));
1533        h2.card_digest = [9; 16];
1534        assert_ne!(content_hash(&h), content_hash(&h2));
1535    }
1536
1537    #[test]
1538    fn leaves_round_trip() {
1539        let c = vec![
1540            ChunkEnt {
1541                first_run: 0,
1542                key: vec![],
1543                clen: 10,
1544            },
1545            ChunkEnt {
1546                first_run: 5,
1547                key: b"ab".to_vec(),
1548                clen: 20,
1549            },
1550        ];
1551        assert_eq!(decode_chunk_leaf(&encode_chunk_leaf(&c), 2).unwrap(), c);
1552        let t = vec![
1553            TileEnt {
1554                min_a: 3,
1555                max_a: 9,
1556                clen: 100,
1557                syn: (1, 4, 2, 8),
1558            },
1559            TileEnt {
1560                min_a: 9,
1561                max_a: 20,
1562                clen: 7,
1563                syn: (0, 0, 5, 5),
1564            },
1565        ];
1566        assert_eq!(decode_tile_leaf(&encode_tile_leaf(&t), 2).unwrap(), t);
1567        let k = vec![
1568            TokenEnt {
1569                token: b"apple".to_vec(),
1570                off: 0,
1571                len: 3,
1572            },
1573            TokenEnt {
1574                token: b"apply".to_vec(),
1575                off: 3,
1576                len: 4,
1577            },
1578        ];
1579        assert_eq!(decode_token_leaf(&encode_token_leaf(&k), 2).unwrap(), k);
1580        let q = vec![
1581            QTileEnt {
1582                first: (5, 1),
1583                last: (6, 2),
1584                clen: 30,
1585                raw: true,
1586                syn: (0, 1, 2, 3),
1587                off: 100,
1588            },
1589            QTileEnt {
1590                first: (6, 3),
1591                last: (9, 0),
1592                clen: 10,
1593                raw: false,
1594                syn: (4, 4, 4, 4),
1595                off: 500,
1596            },
1597        ];
1598        assert_eq!(
1599            decode_qtile_leaf(&encode_qtile_leaf(&q, 100, false), 2, 100, false).unwrap(),
1600            q
1601        );
1602    }
1603
1604    #[test]
1605    fn cut_covers_everything() {
1606        assert_eq!(cut(&[5, 5, 5, 5, 5], 10), vec![(0, 2), (2, 4), (4, 5)]);
1607        assert_eq!(cut(&[], 10), Vec::<(usize, usize)>::new());
1608        assert_eq!(cut(&[50], 10), vec![(0, 1)]);
1609    }
1610}
1611
1612#[cfg(test)]
1613mod id_width_tests {
1614    use super::*;
1615
1616    fn sample() -> Header06 {
1617        Header06 {
1618            version: VERSION,
1619            file_len: 10_000,
1620            root_len: 300,
1621            card_region_len: 100,
1622            data_offset: 2_000,
1623            perm_mask: 0b11_1111,
1624            pyramid_levels: 7,
1625            ..Default::default()
1626        }
1627    }
1628
1629    #[test]
1630    fn width_byte_round_trips_and_is_hashed() {
1631        let h = sample();
1632        assert_eq!(Header06::from_bytes(&h.to_bytes()).unwrap(), h);
1633        assert_eq!(h.to_bytes()[76], 7);
1634        assert_eq!(h.to_bytes()[77], 0);
1635        // Hashing sees the byte: it is logical content.
1636        let mut other = h.clone();
1637        other.id_widths = 1;
1638        assert_ne!(content_hash(&h), content_hash(&other));
1639    }
1640
1641    #[test]
1642    fn a_reader_refuses_every_nonzero_width() {
1643        for (i, name) in id_position_names().iter().enumerate() {
1644            let mut b = sample().to_bytes();
1645            b[77] = 1 << (2 * i);
1646            let e = Header06::from_bytes(&b).unwrap_err().to_string();
1647            assert!(
1648                e.contains(&format!(
1649                    "u64 term ids ({name}): not supported by this reader"
1650                )),
1651                "{e}"
1652            );
1653            for reserved in [2u8, 3] {
1654                let mut b = sample().to_bytes();
1655                b[77] = reserved << (2 * i);
1656                let e = Header06::from_bytes(&b).unwrap_err().to_string();
1657                assert!(e.contains("reserved term id width"), "{e}");
1658            }
1659        }
1660    }
1661
1662    #[test]
1663    fn a_writer_refuses_an_id_that_does_not_fit_u32() {
1664        assert_eq!(id_widths_for([u32::MAX as u64; 4]).unwrap(), 0);
1665        for (i, name) in id_position_names().iter().enumerate() {
1666            let mut m = [1u64; 4];
1667            m[i] = u32::MAX as u64 + 1;
1668            let e = id_widths_for(m).unwrap_err().to_string();
1669            assert!(
1670                e.contains(&format!("needs u64 term ids in {name}, not supported yet")),
1671                "{e}"
1672            );
1673        }
1674    }
1675}
1676
1677#[cfg(test)]
1678mod hostile_root_tests {
1679    use super::*;
1680
1681    fn sec(kind: u8, offset: u64, len: u64) -> Sec06 {
1682        Sec06 {
1683            kind,
1684            max_block: 0,
1685            offset,
1686            len,
1687            digest: [0; 16],
1688        }
1689    }
1690
1691    #[test]
1692    fn section_range_overflow_is_an_error() {
1693        let h = Header06 {
1694            version: VERSION,
1695            data_offset: 100,
1696            ..Header06::default()
1697        };
1698        // A data section, a front section, an offset that overflows the base,
1699        // and one whose end overflows.
1700        for (k, o, l) in [
1701            (kind::DICT_DATA, u64::MAX, 0),
1702            (kind::DICT_DATA, u64::MAX - 50, 10),
1703            (kind::DICT_DATA, 10, u64::MAX),
1704            (kind::DICT_LEAVES, u64::MAX, 1),
1705        ] {
1706            assert!(sec(k, o, l).abs(&h).is_err(), "kind {k} offset {o} len {l}");
1707        }
1708        let ok = sec(kind::DICT_DATA, 5, 7).abs(&h).unwrap();
1709        assert_eq!((ok.offset, ok.len), (105, 7));
1710    }
1711
1712    /// A root whose leaf count is as large as the payload allows but whose
1713    /// leaf entries are missing: refused, not reserved for.
1714    fn varints(vals: &[u64]) -> Vec<u8> {
1715        let mut v = Vec::new();
1716        for &x in vals {
1717            write_uvarint(&mut v, x);
1718        }
1719        v
1720    }
1721
1722    #[test]
1723    fn index_root_with_a_huge_leaf_count_is_refused() {
1724        // 1 permutation: si 0, n_tiles 1, data_off 0, data_len 0, nl = 60 ...
1725        let mut p = varints(&[1, 0, 1, 0, 0, 60]);
1726        p.resize(p.len() + 54, 0);
1727        assert!(decode_index_root(&p).is_err());
1728    }
1729
1730    #[test]
1731    fn text_root_with_a_huge_leaf_count_is_refused() {
1732        // empty scope, 1 token, nl = 60, then too few entries.
1733        let mut p = varints(&[0, 1, 60]);
1734        p.resize(p.len() + 50, 0);
1735        assert!(decode_text_root(&p).is_err());
1736    }
1737
1738    #[test]
1739    fn quad_root_with_a_huge_leaf_count_is_refused() {
1740        // graph_count, quad_count, block_graphs, empty p0, gdir_len, 1 order:
1741        // si 0, n_tiles 1, nl = 60, then too few entries.
1742        let mut p = varints(&[1, 1, 1, 0, 0, 1, 0, 1, 60]);
1743        p.resize(p.len() + 50, 0);
1744        assert!(decode_quad_root(&p).is_err());
1745    }
1746}