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