1pub 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
44pub const VERSION: u8 = 0x07;
46pub const VERSION_06: u8 = 0x06;
49
50pub fn reads(v: u8) -> bool {
52 v == VERSION_06 || v == VERSION
53}
54pub const HEADER_LEN: usize = 128;
56pub const FIRST_READ: u64 = 128 * 1024;
59pub const FOOTER: [u8; 8] = *b"\x07\x00\x00\x00RETE";
63
64pub fn footer(version: u8) -> [u8; 8] {
66 let mut f = FOOTER;
67 f[0] = version;
68 f
69}
70
71pub const ANNEX_MAX: u64 = 64 << 20;
73pub const ROOT_BUDGET: usize = 40 * 1024;
76pub const LEAF_START: usize = 16 * 1024;
78pub const LEAF_MAX: usize = 64 * 1024;
80pub const LIST_CAP: usize = 256 * 1024;
83pub const CARD_SLACK_MIN: u32 = 8 * 1024;
85
86pub const F_NAMED: u8 = 0b0001;
88pub const F_QUOTED: u8 = 0b0010;
90pub const F_TEXT_NAMED: u8 = 0b0100;
92pub const F_QUAD_GRAPH_MAJOR: u8 = 0b1000;
95pub const F_CLUSTERED: u8 = 0b1_0000;
99pub const QUAD_SPOG: usize = crate::quad7::FIRST_LAST_SLOT;
101pub const MAX_CLUSTERS: usize = 32;
103
104pub const P_TEXT: u16 = 1;
106pub const P_TEXT_PARTIAL: u16 = 2;
108pub const P_LABELS: u16 = 4;
110pub const P_SCHEMA: u16 = 8;
112pub const P_PYRAMID: u16 = 16;
114pub const P_QUAD: u16 = 32;
116
117#[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 pub const LABEL_ROOT: u8 = 7;
134 pub const CARD_ANNEX: u8 = 22;
136
137 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 pub fn is_v07_only(k: u8) -> bool {
157 k == LABEL_ROOT || k == CARD_ANNEX
158 }
159
160 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 pub fn is_front(k: u8) -> bool {
183 k < DICT_DATA
184 }
185}
186
187#[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 pub const CLUSTER: u8 = 6;
197}
198
199#[derive(Debug, Clone, Default, PartialEq, Eq)]
201#[allow(missing_docs)]
202pub struct Header06 {
203 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 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 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 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 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 pub fn root_offset(&self) -> u64 {
328 HEADER_LEN as u64
329 }
330 pub fn card_region_offset(&self) -> u64 {
332 HEADER_LEN as u64 + self.root_len as u64
333 }
334 pub fn front_base(&self) -> u64 {
336 self.card_region_offset() + self.card_region_len as u64
337 }
338 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 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 pub fn perms(&self) -> crate::index::PermSet {
354 crate::index::PermSet::from_bits(self.perm_mask).unwrap_or(crate::index::PermSet::ALL)
355 }
356 pub fn has(&self, bit: u16) -> bool {
358 self.presence & bit != 0
359 }
360}
361
362pub 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
369const ID_POSITIONS: [&str; 4] = ["subjects", "objects", "predicates", "graphs"];
371
372fn 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
392pub 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
410pub fn id_position_names() -> [&'static str; 4] {
412 ID_POSITIONS
413}
414
415pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
439pub struct Sec06 {
440 pub kind: u8,
442 pub max_block: u32,
446 pub offset: u64,
448 pub len: u64,
450 pub digest: [u8; 16],
452}
453
454pub const SEC_ENTRY_LEN: usize = 38;
456
457pub const BLOCK_CEILING: u64 = 4 << 20;
460pub const UNIT_MAX: u64 = 16 << 20;
462pub const CARD_MAX: u64 = 64 << 20;
464
465impl Sec06 {
466 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#[derive(Debug, Clone, Default)]
486pub struct Root06 {
487 pub sections: Vec<Sec06>,
489 pub units: Vec<(u8, Vec<u8>)>,
491}
492
493impl Root06 {
494 pub fn section(&self, k: u8) -> Option<&Sec06> {
496 self.sections.iter().find(|s| s.kind == k)
497 }
498
499 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 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 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
573pub struct Cur<'a> {
575 b: &'a [u8],
576 pub pos: usize,
578}
579
580#[allow(clippy::len_without_is_empty)]
582impl<'a> Cur<'a> {
583 pub fn new(b: &'a [u8]) -> Self {
585 Cur { b, pos: 0 }
586 }
587 pub fn done(&self) -> bool {
589 self.pos >= self.b.len()
590 }
591 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 pub fn u32v(&mut self) -> Result<u32, FileError> {
600 u32::try_from(self.uv()?).map_err(|_| FileError::Container("0x06: value exceeds u32"))
601 }
602 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 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 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 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 pub fn lp(&mut self) -> Result<&'a [u8], FileError> {
645 let n = self.len()?;
646 self.bytes(n)
647 }
648}
649
650pub 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#[derive(Debug, Clone, PartialEq, Eq, Default)]
662pub struct LeafRef {
663 pub first: usize,
665 pub n: usize,
667 pub off: u64,
669 pub len: u64,
671}
672
673#[derive(Debug, Clone, Default)]
675pub struct DictSecRoot {
676 pub term_count: u32,
678 pub restart_interval: u32,
680 pub n_chunks: usize,
682 pub data_off: u64,
684 pub data_len: u64,
686 pub leaves: Vec<(LeafRef, usize, u64, Vec<u8>)>,
688}
689
690pub 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
712pub 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#[derive(Debug, Clone, Default)]
751pub struct PermRoot {
752 pub si: usize,
754 pub n_tiles: usize,
756 pub data_off: u64,
758 pub data_len: u64,
760 pub leaves: Vec<(LeafRef, u32, u32, u64)>,
762}
763
764pub 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
786pub 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#[derive(Debug, Clone, Default, PartialEq, Eq)]
844pub struct ClusterOrder {
845 pub si: usize,
848 pub classes: Vec<u32>,
850 pub run_tiles: Vec<usize>,
852}
853
854pub 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
871pub 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#[derive(Debug, Clone, Default)]
906pub struct TextRoot {
907 pub scope: Vec<u8>,
909 pub n_tokens: usize,
911 pub leaves: Vec<(LeafRef, Vec<u8>)>,
913}
914
915pub 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
930pub 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#[derive(Debug, Clone, Default)]
963pub struct LabelRoot {
964 pub data_len: u64,
967 pub head: Vec<u8>,
969}
970
971pub 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
979pub 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
990pub fn quad_order_name(si: usize) -> String {
992 crate::quad7::slot_name(si)
993}
994
995#[derive(Debug, Clone, Default)]
997pub struct QuadRoot {
998 pub graph_count: u64,
1000 pub quad_count: u64,
1002 pub block_graphs: u64,
1004 pub p0: Vec<u8>,
1007 pub gdir_len: u64,
1009 pub orders: Vec<QuadOrderRoot>,
1012}
1013
1014#[derive(Debug, Clone, Default)]
1016pub struct QuadOrderRoot {
1017 pub si: usize,
1019 pub n_tiles: usize,
1021 pub leaves: Vec<QuadLeafRoot>,
1023}
1024
1025pub type QuadLeafRoot = (LeafRef, (u32, u32), (u32, u32), u64);
1028
1029pub 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
1056pub 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#[derive(Debug, Clone, PartialEq, Eq)]
1114pub struct ChunkEnt {
1115 pub first_run: usize,
1117 pub key: Vec<u8>,
1119 pub clen: u64,
1121}
1122
1123pub 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
1143pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1170pub struct TileEnt {
1171 pub min_a: u32,
1173 pub max_a: u32,
1175 pub clen: u64,
1177 pub syn: (u32, u32, u32, u32),
1179}
1180
1181pub 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
1207pub 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#[derive(Debug, Clone, PartialEq, Eq)]
1237pub struct TokenEnt {
1238 pub token: Vec<u8>,
1240 pub off: u64,
1242 pub len: u64,
1244}
1245
1246pub 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
1265pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1287pub struct QTileEnt {
1288 pub first: (u32, u32),
1291 pub last: (u32, u32),
1293 pub clen: u64,
1295 pub raw: bool,
1297 pub syn: (u32, u32, u32, u32),
1300 pub off: u64,
1302}
1303
1304pub 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
1339pub 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
1396pub 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
1416pub 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 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 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 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 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 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 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 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}