1pub 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
47pub const VERSION: u8 = 0x08;
49pub const VERSION_07: u8 = 0x07;
52pub const VERSION_06: u8 = 0x06;
55
56pub fn reads(v: u8) -> bool {
58 (VERSION_06..=VERSION).contains(&v)
59}
60
61pub fn has_v07(v: u8) -> bool {
64 v >= VERSION_07
65}
66
67pub 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}
76pub const HEADER_LEN: usize = 128;
78pub const FIRST_READ: u64 = 128 * 1024;
81pub const FOOTER: [u8; 8] = *b"\x08\x00\x00\x00RETE";
85
86pub fn footer(version: u8) -> [u8; 8] {
88 let mut f = FOOTER;
89 f[0] = version;
90 f
91}
92
93pub const ANNEX_MAX: u64 = 64 << 20;
95pub const ROOT_BUDGET: usize = 40 * 1024;
98pub const LEAF_START: usize = 16 * 1024;
100pub const LEAF_MAX: usize = 64 * 1024;
102pub const LIST_CAP: usize = 256 * 1024;
105pub const CARD_SLACK_MIN: u32 = 8 * 1024;
107
108pub const F_NAMED: u8 = 0b0001;
110pub const F_QUOTED: u8 = 0b0010;
112pub const F_TEXT_NAMED: u8 = 0b0100;
114pub const F_QUAD_GRAPH_MAJOR: u8 = 0b1000;
117pub const F_CLUSTERED: u8 = 0b1_0000;
121pub const F_DERIVED: u8 = 0b10_0000;
125pub const F_KNOWN: u8 =
127 F_NAMED | F_QUOTED | F_TEXT_NAMED | F_QUAD_GRAPH_MAJOR | F_CLUSTERED | F_DERIVED;
128pub const QUAD_SPOG: usize = crate::quad7::FIRST_LAST_SLOT;
130pub const MAX_CLUSTERS: usize = 32;
132
133pub const P_TEXT: u16 = 1;
135pub const P_TEXT_PARTIAL: u16 = 2;
137pub const P_LABELS: u16 = 4;
139pub const P_SCHEMA: u16 = 8;
141pub const P_PYRAMID: u16 = 16;
143pub const P_QUAD: u16 = 32;
145
146#[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 pub const LABEL_ROOT: u8 = 7;
163 pub const CARD_ANNEX: u8 = 22;
165
166 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 pub fn is_v07_only(k: u8) -> bool {
186 k == LABEL_ROOT || k == CARD_ANNEX
187 }
188
189 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 pub fn is_front(k: u8) -> bool {
212 k < DICT_DATA
213 }
214}
215
216#[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 pub const CLUSTER: u8 = 6;
226 pub const DERIVED: u8 = 7;
228}
229
230#[derive(Debug, Clone, Default, PartialEq, Eq)]
232#[allow(missing_docs)]
233pub struct Header06 {
234 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 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 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 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 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 pub fn root_offset(&self) -> u64 {
369 HEADER_LEN as u64
370 }
371 pub fn card_region_offset(&self) -> u64 {
373 HEADER_LEN as u64 + self.root_len as u64
374 }
375 pub fn front_base(&self) -> u64 {
377 self.card_region_offset() + self.card_region_len as u64
378 }
379 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 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 pub fn perms(&self) -> crate::index::PermSet {
395 crate::index::PermSet::from_bits(self.perm_mask).unwrap_or(crate::index::PermSet::ALL)
396 }
397 pub fn has(&self, bit: u16) -> bool {
399 self.presence & bit != 0
400 }
401}
402
403pub 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
410const ID_POSITIONS: [&str; 4] = ["subjects", "objects", "predicates", "graphs"];
412
413fn 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
433pub 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
451pub fn id_position_names() -> [&'static str; 4] {
453 ID_POSITIONS
454}
455
456pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
480pub struct Sec06 {
481 pub kind: u8,
483 pub max_block: u32,
487 pub offset: u64,
489 pub len: u64,
491 pub digest: [u8; 16],
493}
494
495pub const SEC_ENTRY_LEN: usize = 38;
497
498pub const BLOCK_CEILING: u64 = 4 << 20;
501pub const UNIT_MAX: u64 = 16 << 20;
503pub const CARD_MAX: u64 = 64 << 20;
505
506impl Sec06 {
507 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#[derive(Debug, Clone, Default)]
527pub struct Root06 {
528 pub sections: Vec<Sec06>,
530 pub units: Vec<(u8, Vec<u8>)>,
532}
533
534impl Root06 {
535 pub fn section(&self, k: u8) -> Option<&Sec06> {
537 self.sections.iter().find(|s| s.kind == k)
538 }
539
540 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 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 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
614pub struct Cur<'a> {
616 b: &'a [u8],
617 pub pos: usize,
619}
620
621#[allow(clippy::len_without_is_empty)]
623impl<'a> Cur<'a> {
624 pub fn new(b: &'a [u8]) -> Self {
626 Cur { b, pos: 0 }
627 }
628 pub fn done(&self) -> bool {
630 self.pos >= self.b.len()
631 }
632 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 pub fn u32v(&mut self) -> Result<u32, FileError> {
641 u32::try_from(self.uv()?).map_err(|_| FileError::Container("0x06: value exceeds u32"))
642 }
643 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 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 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 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 pub fn lp(&mut self) -> Result<&'a [u8], FileError> {
686 let n = self.len()?;
687 self.bytes(n)
688 }
689}
690
691pub 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#[derive(Debug, Clone, PartialEq, Eq, Default)]
703pub struct LeafRef {
704 pub first: usize,
706 pub n: usize,
708 pub off: u64,
710 pub len: u64,
712}
713
714#[derive(Debug, Clone, Default)]
716pub struct DictSecRoot {
717 pub term_count: u32,
719 pub restart_interval: u32,
721 pub n_chunks: usize,
723 pub data_off: u64,
725 pub data_len: u64,
727 pub leaves: Vec<(LeafRef, usize, u64, Vec<u8>)>,
729 pub groups: crate::term_order::GroupCounts,
732}
733
734pub 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
761pub 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#[derive(Debug, Clone, Default)]
810pub struct PermRoot {
811 pub si: usize,
813 pub n_tiles: usize,
815 pub data_off: u64,
817 pub data_len: u64,
819 pub leaves: Vec<(LeafRef, u32, u32, u64)>,
821}
822
823pub 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
845pub 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#[derive(Debug, Clone, Default, PartialEq, Eq)]
903pub struct ClusterOrder {
904 pub si: usize,
907 pub classes: Vec<u32>,
909 pub run_tiles: Vec<usize>,
911}
912
913pub 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
930pub 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#[derive(Debug, Clone, Default)]
965pub struct TextRoot {
966 pub scope: Vec<u8>,
968 pub n_tokens: usize,
970 pub leaves: Vec<(LeafRef, Vec<u8>)>,
972}
973
974pub 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
989pub 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#[derive(Debug, Clone, Default)]
1022pub struct LabelRoot {
1023 pub data_len: u64,
1026 pub head: Vec<u8>,
1028}
1029
1030pub 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
1038pub 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
1049pub fn quad_order_name(si: usize) -> String {
1051 crate::quad7::slot_name(si)
1052}
1053
1054#[derive(Debug, Clone, Default)]
1056pub struct QuadRoot {
1057 pub graph_count: u64,
1059 pub quad_count: u64,
1061 pub block_graphs: u64,
1063 pub p0: Vec<u8>,
1066 pub gdir_len: u64,
1068 pub orders: Vec<QuadOrderRoot>,
1071}
1072
1073#[derive(Debug, Clone, Default)]
1075pub struct QuadOrderRoot {
1076 pub si: usize,
1078 pub n_tiles: usize,
1080 pub leaves: Vec<QuadLeafRoot>,
1082}
1083
1084pub type QuadLeafRoot = (LeafRef, (u32, u32), (u32, u32), u64);
1087
1088pub 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
1115pub 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#[derive(Debug, Clone, PartialEq, Eq)]
1173pub struct ChunkEnt {
1174 pub first_run: usize,
1176 pub key: Vec<u8>,
1178 pub clen: u64,
1180}
1181
1182pub 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
1202pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1229pub struct TileEnt {
1230 pub min_a: u32,
1232 pub max_a: u32,
1234 pub clen: u64,
1236 pub syn: (u32, u32, u32, u32),
1238}
1239
1240pub 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
1266pub 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#[derive(Debug, Clone, PartialEq, Eq)]
1296pub struct TokenEnt {
1297 pub token: Vec<u8>,
1299 pub off: u64,
1301 pub len: u64,
1303}
1304
1305pub 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
1324pub 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1346pub struct QTileEnt {
1347 pub first: (u32, u32),
1350 pub last: (u32, u32),
1352 pub clen: u64,
1354 pub raw: bool,
1356 pub syn: (u32, u32, u32, u32),
1359 pub off: u64,
1361}
1362
1363pub 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
1398pub 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
1455pub 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
1475pub 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 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 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 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 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 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 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 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}