1pub mod open;
22pub mod parts;
23pub mod write;
24
25#[cfg(test)]
26mod roundtrip;
27
28use crate::file::FileError;
29use crate::varint::{read_uvarint, write_uvarint};
30
31pub const VERSION: u8 = 0x06;
33pub const HEADER_LEN: usize = 128;
35pub const FIRST_READ: u64 = 64 * 1024;
38pub const FOOTER: [u8; 8] = *b"\x06\x00\x00\x00RETE";
41pub const ROOT_BUDGET: usize = 40 * 1024;
44pub const LEAF_START: usize = 16 * 1024;
46pub const LEAF_MAX: usize = 64 * 1024;
48pub const LIST_CAP: usize = 256 * 1024;
51pub const CARD_SLACK_MIN: u32 = 8 * 1024;
53
54pub const F_NAMED: u8 = 0b0001;
56pub const F_QUOTED: u8 = 0b0010;
58pub const F_TEXT_NAMED: u8 = 0b0100;
60pub const F_QUAD_GRAPH_MAJOR: u8 = 0b1000;
63
64pub const P_TEXT: u16 = 1;
66pub const P_TEXT_PARTIAL: u16 = 2;
68pub const P_LABELS: u16 = 4;
70pub const P_SCHEMA: u16 = 8;
72pub const P_PYRAMID: u16 = 16;
74pub const P_QUAD: u16 = 32;
76
77#[allow(missing_docs)]
79pub mod kind {
80 pub const SCHEMA: u8 = 1;
81 pub const DICT_LEAVES: u8 = 2;
82 pub const INDEX_LEAVES: u8 = 3;
83 pub const QUAD_LEAVES: u8 = 4;
84 pub const LABEL_LEAVES: u8 = 5;
85 pub const TEXT_LEAVES: u8 = 6;
86 pub const DICT_DATA: u8 = 16;
87 pub const INDEX_DATA: u8 = 17;
88 pub const QUAD_DATA: u8 = 18;
89 pub const LABEL_DATA: u8 = 19;
90 pub const TEXT_DATA: u8 = 20;
91 pub const PYRAMID: u8 = 21;
92
93 pub const ORDER: [u8; 12] = [
95 SCHEMA,
96 DICT_LEAVES,
97 INDEX_LEAVES,
98 QUAD_LEAVES,
99 LABEL_LEAVES,
100 TEXT_LEAVES,
101 DICT_DATA,
102 INDEX_DATA,
103 QUAD_DATA,
104 LABEL_DATA,
105 TEXT_DATA,
106 PYRAMID,
107 ];
108
109 pub fn name(k: u8) -> &'static str {
111 match k {
112 SCHEMA => "schema",
113 DICT_LEAVES => "dict-leaves",
114 INDEX_LEAVES => "index-leaves",
115 QUAD_LEAVES => "quad-leaves",
116 LABEL_LEAVES => "label-leaves",
117 TEXT_LEAVES => "text-leaves",
118 DICT_DATA => "dict",
119 INDEX_DATA => "index",
120 QUAD_DATA => "quad",
121 LABEL_DATA => "labels",
122 TEXT_DATA => "text",
123 PYRAMID => "pyramid",
124 _ => "unknown",
125 }
126 }
127
128 pub fn is_front(k: u8) -> bool {
130 k < DICT_DATA
131 }
132}
133
134#[allow(missing_docs)]
136pub mod tag {
137 pub const DICT: u8 = 1;
138 pub const INDEX: u8 = 2;
139 pub const QUAD: u8 = 3;
140 pub const LABELS: u8 = 4;
141 pub const TEXT: u8 = 5;
142}
143
144#[derive(Debug, Clone, Default, PartialEq, Eq)]
146#[allow(missing_docs)]
147pub struct Header06 {
148 pub flags: u8,
149 pub content_hash: [u8; 16],
150 pub file_len: u64,
151 pub root_len: u32,
152 pub card_region_len: u32,
153 pub data_offset: u64,
154 pub quad_count: u64,
155 pub term_count: u64,
156 pub graph_count: u64,
157 pub perm_mask: u8,
158 pub dict_codec: u8,
159 pub block_codec: u8,
160 pub internal_codec: u8,
161 pub pyramid_levels: u16,
162 pub id_widths: u8,
165 pub presence: u16,
166 pub card_off: u32,
167 pub card_len: u32,
168 pub card_digest: [u8; 16],
169 pub build_off: u32,
170 pub build_len: u32,
171 pub root_digest: [u8; 16],
172}
173
174impl Header06 {
175 pub fn to_bytes(&self) -> [u8; HEADER_LEN] {
177 let mut b = [0u8; HEADER_LEN];
178 b[0..4].copy_from_slice(&crate::header::MAGIC);
179 b[4] = VERSION;
180 b[5] = self.flags;
181 b[6..8].copy_from_slice(&(HEADER_LEN as u16).to_le_bytes());
182 b[8..24].copy_from_slice(&self.content_hash);
183 b[24..32].copy_from_slice(&self.file_len.to_le_bytes());
184 b[32..36].copy_from_slice(&self.root_len.to_le_bytes());
185 b[36..40].copy_from_slice(&self.card_region_len.to_le_bytes());
186 b[40..48].copy_from_slice(&self.data_offset.to_le_bytes());
187 b[48..56].copy_from_slice(&self.quad_count.to_le_bytes());
188 b[56..64].copy_from_slice(&self.term_count.to_le_bytes());
189 b[64..72].copy_from_slice(&self.graph_count.to_le_bytes());
190 b[72] = self.perm_mask;
191 b[73] = self.dict_codec;
192 b[74] = self.block_codec;
193 b[75] = self.internal_codec;
194 b[76] = self.pyramid_levels as u8;
195 b[77] = self.id_widths;
196 b[78..80].copy_from_slice(&self.presence.to_le_bytes());
197 b[80..84].copy_from_slice(&self.card_off.to_le_bytes());
198 b[84..88].copy_from_slice(&self.card_len.to_le_bytes());
199 b[88..104].copy_from_slice(&self.card_digest);
200 b[104..108].copy_from_slice(&self.build_off.to_le_bytes());
201 b[108..112].copy_from_slice(&self.build_len.to_le_bytes());
202 b[112..128].copy_from_slice(&self.root_digest);
203 b
204 }
205
206 pub fn from_bytes(b: &[u8]) -> Result<Self, FileError> {
208 if b.len() < HEADER_LEN {
209 return Err(FileError::Container("0x06 header truncated"));
210 }
211 if b[0..4] != crate::header::MAGIC || b[4] != VERSION {
212 return Err(FileError::Container("not a 0x06 file"));
213 }
214 if u16::from_le_bytes([b[6], b[7]]) as usize != HEADER_LEN {
215 return Err(FileError::Container("0x06 header length is not 128"));
216 }
217 let u32_at = |o: usize| u32::from_le_bytes(b[o..o + 4].try_into().unwrap());
218 let u64_at = |o: usize| u64::from_le_bytes(b[o..o + 8].try_into().unwrap());
219 let h16 = |o: usize| {
220 let mut x = [0u8; 16];
221 x.copy_from_slice(&b[o..o + 16]);
222 x
223 };
224 let h = Header06 {
225 flags: b[5],
226 content_hash: h16(8),
227 file_len: u64_at(24),
228 root_len: u32_at(32),
229 card_region_len: u32_at(36),
230 data_offset: u64_at(40),
231 quad_count: u64_at(48),
232 term_count: u64_at(56),
233 graph_count: u64_at(64),
234 perm_mask: b[72],
235 dict_codec: b[73],
236 block_codec: b[74],
237 internal_codec: b[75],
238 pyramid_levels: b[76] as u16,
239 id_widths: b[77],
240 presence: u16::from_le_bytes([b[78], b[79]]),
241 card_off: u32_at(80),
242 card_len: u32_at(84),
243 card_digest: h16(88),
244 build_off: u32_at(104),
245 build_len: u32_at(108),
246 root_digest: h16(112),
247 };
248 let front_min = (HEADER_LEN as u64)
251 .checked_add(h.root_len as u64)
252 .and_then(|x| x.checked_add(h.card_region_len as u64))
253 .ok_or(FileError::Container("0x06 front overflows"))?;
254 if front_min > h.data_offset || h.data_offset > h.file_len {
255 return Err(FileError::Container("0x06 front overruns the data region"));
256 }
257 let card_end = h.card_off as u64 + h.card_len as u64;
258 let build_end = h.build_off as u64 + h.build_len as u64;
259 if card_end > h.card_region_len as u64 || build_end > h.card_region_len as u64 {
260 return Err(FileError::Container("0x06 card region overrun"));
261 }
262 crate::index::PermSet::from_bits(h.perm_mask)
263 .map_err(|_| FileError::Container("0x06 permutation mask invalid"))?;
264 check_id_widths_byte(h.id_widths)?;
265 Ok(h)
266 }
267
268 pub fn root_offset(&self) -> u64 {
270 HEADER_LEN as u64
271 }
272 pub fn card_region_offset(&self) -> u64 {
274 HEADER_LEN as u64 + self.root_len as u64
275 }
276 pub fn front_base(&self) -> u64 {
278 self.card_region_offset() + self.card_region_len as u64
279 }
280 pub fn card_range(&self) -> crate::file::ByteRange {
282 crate::file::ByteRange {
283 offset: self.card_region_offset() + self.card_off as u64,
284 len: self.card_len as u64,
285 }
286 }
287 pub fn build_range(&self) -> crate::file::ByteRange {
289 crate::file::ByteRange {
290 offset: self.card_region_offset() + self.build_off as u64,
291 len: self.build_len as u64,
292 }
293 }
294 pub fn perms(&self) -> crate::index::PermSet {
296 crate::index::PermSet::from_bits(self.perm_mask).unwrap_or(crate::index::PermSet::ALL)
297 }
298 pub fn has(&self, bit: u16) -> bool {
300 self.presence & bit != 0
301 }
302}
303
304pub fn digest16(bytes: &[u8]) -> [u8; 16] {
306 let mut out = [0u8; 16];
307 out.copy_from_slice(&blake3::hash(bytes).as_bytes()[..16]);
308 out
309}
310
311const ID_POSITIONS: [&str; 4] = ["subjects", "objects", "predicates", "graphs"];
313
314fn check_id_widths_byte(w: u8) -> Result<(), FileError> {
317 for i in 0..4 {
318 match (w >> (2 * i)) & 3 {
319 0 => {}
320 1 => {
321 return Err(FileError::Container(match i {
322 0 => "u64 term ids (subjects): not supported by this reader",
323 1 => "u64 term ids (objects): not supported by this reader",
324 2 => "u64 term ids (predicates): not supported by this reader",
325 _ => "u64 term ids (graphs): not supported by this reader",
326 }))
327 }
328 _ => return Err(FileError::Container("0x06 header: reserved term id width")),
329 }
330 }
331 Ok(())
332}
333
334pub fn id_widths_for(max_ids: [u64; 4]) -> Result<u8, FileError> {
339 for (i, m) in max_ids.iter().enumerate() {
340 if *m > u32::MAX as u64 {
341 return Err(FileError::Container(match i {
342 0 => "this dataset needs u64 term ids in subjects, not supported yet",
343 1 => "this dataset needs u64 term ids in objects, not supported yet",
344 2 => "this dataset needs u64 term ids in predicates, not supported yet",
345 _ => "this dataset needs u64 term ids in graphs, not supported yet",
346 }));
347 }
348 }
349 Ok(0)
350}
351
352pub fn id_position_names() -> [&'static str; 4] {
354 ID_POSITIONS
355}
356
357pub fn content_hash(h: &Header06) -> [u8; 16] {
361 let b = h.to_bytes();
362 let mut x = blake3::Hasher::new();
363 x.update(b"rete/0x06");
364 x.update(&b[4..8]);
365 x.update(&b[48..80]);
366 x.update(&h.card_len.to_le_bytes());
367 x.update(&h.card_digest);
368 x.update(&h.root_len.to_le_bytes());
369 x.update(&h.root_digest);
370 let mut out = [0u8; 16];
371 out.copy_from_slice(&x.finalize().as_bytes()[..16]);
372 out
373}
374
375#[derive(Debug, Clone, Copy, PartialEq, Eq)]
377pub struct Sec06 {
378 pub kind: u8,
380 pub max_block: u32,
384 pub offset: u64,
386 pub len: u64,
388 pub digest: [u8; 16],
390}
391
392pub const SEC_ENTRY_LEN: usize = 38;
394
395pub const BLOCK_CEILING: u64 = 4 << 20;
398pub const UNIT_MAX: u64 = 16 << 20;
400pub const CARD_MAX: u64 = 64 << 20;
402
403impl Sec06 {
404 pub fn abs(&self, h: &Header06) -> Result<crate::file::ByteRange, crate::file::FileError> {
407 let base = if kind::is_front(self.kind) {
408 h.front_base()
409 } else {
410 h.data_offset
411 };
412 let overflow = || crate::file::FileError::Container("0x06 section overflows");
413 let offset = base.checked_add(self.offset).ok_or_else(overflow)?;
414 offset.checked_add(self.len).ok_or_else(overflow)?;
415 Ok(crate::file::ByteRange {
416 offset,
417 len: self.len,
418 })
419 }
420}
421
422#[derive(Debug, Clone, Default)]
424pub struct Root06 {
425 pub sections: Vec<Sec06>,
427 pub units: Vec<(u8, Vec<u8>)>,
429}
430
431impl Root06 {
432 pub fn section(&self, k: u8) -> Option<&Sec06> {
434 self.sections.iter().find(|s| s.kind == k)
435 }
436
437 pub fn unit(&self, t: u8) -> Option<&[u8]> {
439 self.units
440 .iter()
441 .find(|(x, _)| *x == t)
442 .map(|(_, p)| p.as_slice())
443 }
444
445 pub fn encode(&self, codec: u8) -> Vec<u8> {
447 let mut units = Vec::new();
448 for (t, p) in &self.units {
449 units.push(*t);
450 write_uvarint(&mut units, p.len() as u64);
451 units.extend_from_slice(p);
452 }
453 let stored = crate::file::compress(codec, &units);
454 let mut out =
455 Vec::with_capacity(2 + SEC_ENTRY_LEN * self.sections.len() + 4 + stored.len());
456 out.push(1u8);
457 out.push(self.sections.len() as u8);
458 for s in &self.sections {
459 out.push(s.kind);
460 out.push(0);
461 out.extend_from_slice(&s.max_block.to_le_bytes());
462 out.extend_from_slice(&s.offset.to_le_bytes());
463 out.extend_from_slice(&s.len.to_le_bytes());
464 out.extend_from_slice(&s.digest);
465 }
466 out.extend_from_slice(&(stored.len() as u32).to_le_bytes());
467 out.extend_from_slice(&stored);
468 out
469 }
470
471 pub fn decode(bytes: &[u8], codec: u8) -> Result<Self, FileError> {
473 let bad = |w| FileError::Container(w);
474 if bytes.len() < 2 || bytes[0] != 1 {
475 return Err(bad("0x06 root block: unknown version"));
476 }
477 let n = bytes[1] as usize;
478 let table_end = 2 + n * SEC_ENTRY_LEN;
479 if bytes.len() < table_end + 4 {
480 return Err(bad("0x06 root block truncated"));
481 }
482 let mut sections = Vec::with_capacity(n);
483 for i in 0..n {
484 let e = &bytes[2 + i * SEC_ENTRY_LEN..2 + (i + 1) * SEC_ENTRY_LEN];
485 let mut digest = [0u8; 16];
486 digest.copy_from_slice(&e[22..38]);
487 sections.push(Sec06 {
488 kind: e[0],
489 max_block: u32::from_le_bytes(e[2..6].try_into().unwrap()),
490 offset: u64::from_le_bytes(e[6..14].try_into().unwrap()),
491 len: u64::from_le_bytes(e[14..22].try_into().unwrap()),
492 digest,
493 });
494 }
495 let ulen = u32::from_le_bytes(bytes[table_end..table_end + 4].try_into().unwrap()) as usize;
496 let stored = bytes
497 .get(table_end + 4..table_end + 4 + ulen)
498 .ok_or(bad("0x06 root units overrun"))?;
499 let units_raw = crate::file::decompress_bounded(codec, stored, UNIT_MAX)?;
500 let mut units = Vec::new();
501 let mut c = Cur::new(&units_raw);
502 while !c.done() {
503 let t = c.u8()?;
504 let l = c.len()?;
505 units.push((t, c.bytes(l)?.to_vec()));
506 }
507 Ok(Root06 { sections, units })
508 }
509}
510
511pub struct Cur<'a> {
513 b: &'a [u8],
514 pub pos: usize,
516}
517
518#[allow(clippy::len_without_is_empty)]
520impl<'a> Cur<'a> {
521 pub fn new(b: &'a [u8]) -> Self {
523 Cur { b, pos: 0 }
524 }
525 pub fn done(&self) -> bool {
527 self.pos >= self.b.len()
528 }
529 pub fn uv(&mut self) -> Result<u64, FileError> {
531 let (v, n) = read_uvarint(self.b.get(self.pos..).unwrap_or(&[]))
532 .ok_or(FileError::Container("0x06: truncated varint"))?;
533 self.pos += n;
534 Ok(v)
535 }
536 pub fn u32v(&mut self) -> Result<u32, FileError> {
538 u32::try_from(self.uv()?).map_err(|_| FileError::Container("0x06: value exceeds u32"))
539 }
540 pub fn len(&mut self) -> Result<usize, FileError> {
542 let v = self.uv()?;
543 let rest = self.b.len().saturating_sub(self.pos) as u64;
544 if v > rest {
545 return Err(FileError::Container("0x06: length overruns"));
546 }
547 Ok(v as usize)
548 }
549 pub fn count(&mut self, max: u64) -> Result<usize, FileError> {
551 let v = self.uv()?;
552 if v > max {
553 return Err(FileError::Container("0x06: count out of range"));
554 }
555 Ok(v as usize)
556 }
557 pub fn u8(&mut self) -> Result<u8, FileError> {
559 let v = *self
560 .b
561 .get(self.pos)
562 .ok_or(FileError::Container("0x06: truncated"))?;
563 self.pos += 1;
564 Ok(v)
565 }
566 pub fn bytes(&mut self, n: usize) -> Result<&'a [u8], FileError> {
568 let s = self
569 .b
570 .get(
571 self.pos
572 ..self
573 .pos
574 .checked_add(n)
575 .ok_or(FileError::Container("0x06: overflow"))?,
576 )
577 .ok_or(FileError::Container("0x06: truncated bytes"))?;
578 self.pos += n;
579 Ok(s)
580 }
581 pub fn lp(&mut self) -> Result<&'a [u8], FileError> {
583 let n = self.len()?;
584 self.bytes(n)
585 }
586}
587
588pub fn put_lp(out: &mut Vec<u8>, b: &[u8]) {
590 write_uvarint(out, b.len() as u64);
591 out.extend_from_slice(b);
592}
593
594#[derive(Debug, Clone, PartialEq, Eq, Default)]
600pub struct LeafRef {
601 pub first: usize,
603 pub n: usize,
605 pub off: u64,
607 pub len: u64,
609}
610
611#[derive(Debug, Clone, Default)]
613pub struct DictSecRoot {
614 pub term_count: u32,
616 pub restart_interval: u32,
618 pub n_chunks: usize,
620 pub data_off: u64,
622 pub data_len: u64,
624 pub leaves: Vec<(LeafRef, usize, u64, Vec<u8>)>,
626}
627
628pub fn encode_dict_root(secs: &[DictSecRoot; 4]) -> Vec<u8> {
630 let mut o = Vec::new();
631 for s in secs {
632 write_uvarint(&mut o, s.term_count as u64);
633 write_uvarint(&mut o, s.restart_interval as u64);
634 write_uvarint(&mut o, s.n_chunks as u64);
635 write_uvarint(&mut o, s.data_off);
636 write_uvarint(&mut o, s.data_len);
637 write_uvarint(&mut o, s.leaves.len() as u64);
638 for (l, run, coff, key) in &s.leaves {
639 write_uvarint(&mut o, l.n as u64);
640 write_uvarint(&mut o, l.off);
641 write_uvarint(&mut o, l.len);
642 write_uvarint(&mut o, *run as u64);
643 write_uvarint(&mut o, *coff);
644 put_lp(&mut o, key);
645 }
646 }
647 o
648}
649
650pub fn decode_dict_root(p: &[u8]) -> Result<[DictSecRoot; 4], FileError> {
652 let mut c = Cur::new(p);
653 let mut out: [DictSecRoot; 4] = Default::default();
654 for s in out.iter_mut() {
655 s.term_count = c.u32v()?;
656 s.restart_interval = c.u32v()?;
657 s.n_chunks = c.count(u32::MAX as u64)?;
658 s.data_off = c.uv()?;
659 s.data_len = c.uv()?;
660 let nl = c.count(p.len() as u64)?;
661 let mut first = 0usize;
662 for _ in 0..nl {
663 let n = c.count(u32::MAX as u64)?;
664 let off = c.uv()?;
665 let len = c.uv()?;
666 let run = c.count(u64::MAX)?;
667 let coff = c.uv()?;
668 let key = c.lp()?.to_vec();
669 s.leaves
670 .push((LeafRef { first, n, off, len }, run, coff, key));
671 first = first
672 .checked_add(n)
673 .ok_or(FileError::Container("0x06 dict leaves overflow"))?;
674 }
675 if first != s.n_chunks {
676 return Err(FileError::Container(
677 "0x06 dict leaves do not cover the chunks",
678 ));
679 }
680 if s.restart_interval == 0 && s.term_count > 0 {
681 return Err(FileError::Container("0x06 dict zero restart interval"));
682 }
683 }
684 Ok(out)
685}
686
687#[derive(Debug, Clone, Default)]
689pub struct PermRoot {
690 pub si: usize,
692 pub n_tiles: usize,
694 pub data_off: u64,
696 pub data_len: u64,
698 pub leaves: Vec<(LeafRef, u32, u32, u64)>,
700}
701
702pub fn encode_index_root(perms: &[PermRoot]) -> Vec<u8> {
704 let mut o = Vec::new();
705 write_uvarint(&mut o, perms.len() as u64);
706 for p in perms {
707 write_uvarint(&mut o, p.si as u64);
708 write_uvarint(&mut o, p.n_tiles as u64);
709 write_uvarint(&mut o, p.data_off);
710 write_uvarint(&mut o, p.data_len);
711 write_uvarint(&mut o, p.leaves.len() as u64);
712 for (l, mn, mx, toff) in &p.leaves {
713 write_uvarint(&mut o, l.n as u64);
714 write_uvarint(&mut o, l.off);
715 write_uvarint(&mut o, l.len);
716 write_uvarint(&mut o, *mn as u64);
717 write_uvarint(&mut o, *mx as u64);
718 write_uvarint(&mut o, *toff);
719 }
720 }
721 o
722}
723
724pub fn decode_index_root(p: &[u8]) -> Result<Vec<PermRoot>, FileError> {
726 let mut c = Cur::new(p);
727 let n = c.count(6)?;
728 let mut out = Vec::with_capacity(n);
729 for _ in 0..n {
730 let si = c.count(5)?;
731 let n_tiles = c.count(u32::MAX as u64)?;
732 let data_off = c.uv()?;
733 let data_len = c.uv()?;
734 let nl = c.count(p.len() as u64)?;
735 let mut leaves = Vec::with_capacity(nl.min(p.len() / 5));
736 let mut first = 0usize;
737 for _ in 0..nl {
738 let ln = c.count(u32::MAX as u64)?;
739 let off = c.uv()?;
740 let len = c.uv()?;
741 let mn = c.u32v()?;
742 let mx = c.u32v()?;
743 let toff = c.uv()?;
744 leaves.push((
745 LeafRef {
746 first,
747 n: ln,
748 off,
749 len,
750 },
751 mn,
752 mx,
753 toff,
754 ));
755 first = first
756 .checked_add(ln)
757 .ok_or(FileError::Container("0x06 index leaves overflow"))?;
758 }
759 if first != n_tiles {
760 return Err(FileError::Container(
761 "0x06 index leaves do not cover the tiles",
762 ));
763 }
764 out.push(PermRoot {
765 si,
766 n_tiles,
767 data_off,
768 data_len,
769 leaves,
770 });
771 }
772 Ok(out)
773}
774
775#[derive(Debug, Clone, Default)]
777pub struct TextRoot {
778 pub scope: Vec<u8>,
780 pub n_tokens: usize,
782 pub leaves: Vec<(LeafRef, Vec<u8>)>,
784}
785
786pub fn encode_text_root(t: &TextRoot) -> Vec<u8> {
788 let mut o = Vec::new();
789 put_lp(&mut o, &t.scope);
790 write_uvarint(&mut o, t.n_tokens as u64);
791 write_uvarint(&mut o, t.leaves.len() as u64);
792 for (l, first) in &t.leaves {
793 write_uvarint(&mut o, l.n as u64);
794 write_uvarint(&mut o, l.off);
795 write_uvarint(&mut o, l.len);
796 put_lp(&mut o, first);
797 }
798 o
799}
800
801pub fn decode_text_root(p: &[u8]) -> Result<TextRoot, FileError> {
803 let mut c = Cur::new(p);
804 let scope = c.lp()?.to_vec();
805 let n_tokens = c.count(u32::MAX as u64)?;
806 let nl = c.count(p.len() as u64)?;
807 let mut leaves = Vec::with_capacity(nl.min(p.len() / 5));
808 let mut first = 0usize;
809 for _ in 0..nl {
810 let n = c.count(u32::MAX as u64)?;
811 let off = c.uv()?;
812 let len = c.uv()?;
813 let tok = c.lp()?.to_vec();
814 leaves.push((LeafRef { first, n, off, len }, tok));
815 first = first
816 .checked_add(n)
817 .ok_or(FileError::Container("0x06 text leaves overflow"))?;
818 }
819 if first != n_tokens {
820 return Err(FileError::Container(
821 "0x06 text leaves do not cover the tokens",
822 ));
823 }
824 Ok(TextRoot {
825 scope,
826 n_tokens,
827 leaves,
828 })
829}
830
831#[derive(Debug, Clone, Default)]
834pub struct LabelRoot {
835 pub data_len: u64,
838 pub head: Vec<u8>,
840}
841
842pub fn encode_label_root(l: &LabelRoot) -> Vec<u8> {
844 let mut o = Vec::new();
845 write_uvarint(&mut o, l.data_len);
846 put_lp(&mut o, &l.head);
847 o
848}
849
850pub fn decode_label_root(p: &[u8]) -> Result<LabelRoot, FileError> {
852 let mut c = Cur::new(p);
853 let data_len = c.uv()?;
854 let head = c.lp()?.to_vec();
855 if head.len() < 32 {
856 return Err(FileError::Container("0x06 label root truncated"));
857 }
858 Ok(LabelRoot { data_len, head })
859}
860
861#[derive(Debug, Clone, Default)]
863pub struct QuadRoot {
864 pub graph_count: u64,
866 pub quad_count: u64,
868 pub block_graphs: u64,
870 pub p0: Vec<u8>,
873 pub gdir_len: u64,
875 pub orders: Vec<QuadOrderRoot>,
878}
879
880#[derive(Debug, Clone, Default)]
882pub struct QuadOrderRoot {
883 pub si: usize,
885 pub n_tiles: usize,
887 pub leaves: Vec<QuadLeafRoot>,
889}
890
891pub type QuadLeafRoot = (LeafRef, (u32, u32), (u32, u32), u64);
894
895pub fn encode_quad_root(q: &QuadRoot) -> Vec<u8> {
897 let mut o = Vec::new();
898 write_uvarint(&mut o, q.graph_count);
899 write_uvarint(&mut o, q.quad_count);
900 write_uvarint(&mut o, q.block_graphs);
901 put_lp(&mut o, &q.p0);
902 write_uvarint(&mut o, q.gdir_len);
903 write_uvarint(&mut o, q.orders.len() as u64);
904 for ord in &q.orders {
905 write_uvarint(&mut o, ord.si as u64);
906 write_uvarint(&mut o, ord.n_tiles as u64);
907 write_uvarint(&mut o, ord.leaves.len() as u64);
908 for (l, f, la, toff) in &ord.leaves {
909 write_uvarint(&mut o, l.n as u64);
910 write_uvarint(&mut o, l.off);
911 write_uvarint(&mut o, l.len);
912 write_uvarint(&mut o, f.0 as u64);
913 write_uvarint(&mut o, f.1 as u64);
914 write_uvarint(&mut o, la.0 as u64);
915 write_uvarint(&mut o, la.1 as u64);
916 write_uvarint(&mut o, *toff);
917 }
918 }
919 o
920}
921
922pub fn decode_quad_root(p: &[u8]) -> Result<QuadRoot, FileError> {
924 let mut c = Cur::new(p);
925 let graph_count = c.uv()?;
926 let quad_count = c.uv()?;
927 let block_graphs = c.uv()?;
928 let p0 = c.lp()?.to_vec();
929 let gdir_len = c.uv()?;
930 let no = c.count(6)?;
931 let mut orders = Vec::with_capacity(no);
932 for _ in 0..no {
933 let si = c.count(5)?;
934 let n_tiles = 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 f = (c.u32v()?, c.u32v()?);
943 let la = (c.u32v()?, c.u32v()?);
944 let toff = c.uv()?;
945 leaves.push((LeafRef { first, n, off, len }, f, la, toff));
946 first = first
947 .checked_add(n)
948 .ok_or(FileError::Container("0x06 quad leaves overflow"))?;
949 }
950 if first != n_tiles {
951 return Err(FileError::Container(
952 "0x06 quad leaves do not cover the tiles",
953 ));
954 }
955 orders.push(QuadOrderRoot {
956 si,
957 n_tiles,
958 leaves,
959 });
960 }
961 if block_graphs == 0 && graph_count > 0 {
962 return Err(FileError::Container("0x06 quad block size is zero"));
963 }
964 Ok(QuadRoot {
965 graph_count,
966 quad_count,
967 block_graphs,
968 p0,
969 gdir_len,
970 orders,
971 })
972}
973
974#[derive(Debug, Clone, PartialEq, Eq)]
980pub struct ChunkEnt {
981 pub first_run: usize,
983 pub key: Vec<u8>,
985 pub clen: u64,
987}
988
989pub fn encode_chunk_leaf(ents: &[ChunkEnt]) -> Vec<u8> {
991 let mut o = Vec::new();
992 let mut prev = 0usize;
993 for (i, e) in ents.iter().enumerate() {
994 write_uvarint(
995 &mut o,
996 (if i == 0 {
997 e.first_run
998 } else {
999 e.first_run - prev
1000 }) as u64,
1001 );
1002 put_lp(&mut o, &e.key);
1003 write_uvarint(&mut o, e.clen);
1004 prev = e.first_run;
1005 }
1006 o
1007}
1008
1009pub fn decode_chunk_leaf(b: &[u8], n: usize) -> Result<Vec<ChunkEnt>, FileError> {
1011 let mut c = Cur::new(b);
1012 let mut out = Vec::with_capacity(n.min(b.len()));
1013 let mut prev = 0usize;
1014 for i in 0..n {
1015 let d = c.count(u64::MAX)?;
1016 let first_run = if i == 0 {
1017 d
1018 } else {
1019 prev.checked_add(d)
1020 .ok_or(FileError::Container("0x06 chunk run overflow"))?
1021 };
1022 let key = c.lp()?.to_vec();
1023 let clen = c.uv()?;
1024 out.push(ChunkEnt {
1025 first_run,
1026 key,
1027 clen,
1028 });
1029 prev = first_run;
1030 }
1031 Ok(out)
1032}
1033
1034#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1036pub struct TileEnt {
1037 pub min_a: u32,
1039 pub max_a: u32,
1041 pub clen: u64,
1043 pub syn: (u32, u32, u32, u32),
1045}
1046
1047pub fn encode_tile_leaf(ents: &[TileEnt]) -> Vec<u8> {
1049 let mut o = Vec::new();
1050 let mut prev = 0u32;
1051 for (i, e) in ents.iter().enumerate() {
1052 write_uvarint(
1053 &mut o,
1054 (if i == 0 {
1055 e.min_a
1056 } else {
1057 e.min_a.wrapping_sub(prev)
1058 }) as u64,
1059 );
1060 write_uvarint(&mut o, e.max_a.wrapping_sub(e.min_a) as u64);
1061 write_uvarint(&mut o, e.clen);
1062 prev = e.min_a;
1063 }
1064 for e in ents {
1065 write_uvarint(&mut o, e.syn.0 as u64);
1066 write_uvarint(&mut o, e.syn.1.wrapping_sub(e.syn.0) as u64);
1067 write_uvarint(&mut o, e.syn.2 as u64);
1068 write_uvarint(&mut o, e.syn.3.wrapping_sub(e.syn.2) as u64);
1069 }
1070 o
1071}
1072
1073pub fn decode_tile_leaf(b: &[u8], n: usize) -> Result<Vec<TileEnt>, FileError> {
1075 let mut c = Cur::new(b);
1076 let mut out = Vec::with_capacity(n.min(b.len()));
1077 let mut prev = 0u32;
1078 for i in 0..n {
1079 let d = c.u32v()?;
1080 let min_a = if i == 0 { d } else { prev.wrapping_add(d) };
1081 let span = c.u32v()?;
1082 let clen = c.uv()?;
1083 out.push(TileEnt {
1084 min_a,
1085 max_a: min_a.wrapping_add(span),
1086 clen,
1087 syn: (0, 0, 0, 0),
1088 });
1089 prev = min_a;
1090 }
1091 for e in out.iter_mut() {
1092 let mb = c.u32v()?;
1093 let db = c.u32v()?;
1094 let mc = c.u32v()?;
1095 let dc = c.u32v()?;
1096 e.syn = (mb, mb.wrapping_add(db), mc, mc.wrapping_add(dc));
1097 }
1098 Ok(out)
1099}
1100
1101#[derive(Debug, Clone, PartialEq, Eq)]
1103pub struct TokenEnt {
1104 pub token: Vec<u8>,
1106 pub off: u64,
1108 pub len: u64,
1110}
1111
1112pub fn encode_token_leaf(ents: &[TokenEnt]) -> Vec<u8> {
1114 let mut o = Vec::new();
1115 let mut prev: &[u8] = &[];
1116 for e in ents {
1117 let shared = prev
1118 .iter()
1119 .zip(&e.token)
1120 .take_while(|(a, b)| a == b)
1121 .count();
1122 write_uvarint(&mut o, shared as u64);
1123 put_lp(&mut o, &e.token[shared..]);
1124 write_uvarint(&mut o, e.off);
1125 write_uvarint(&mut o, e.len);
1126 prev = &e.token;
1127 }
1128 o
1129}
1130
1131pub fn decode_token_leaf(b: &[u8], n: usize) -> Result<Vec<TokenEnt>, FileError> {
1133 let mut c = Cur::new(b);
1134 let mut out: Vec<TokenEnt> = Vec::with_capacity(n.min(b.len()));
1135 for _ in 0..n {
1136 let shared = c.count(u32::MAX as u64)?;
1137 let suffix = c.lp()?;
1138 let mut token = match out.last() {
1139 Some(p) if shared <= p.token.len() => p.token[..shared].to_vec(),
1140 None if shared == 0 => Vec::new(),
1141 _ => return Err(FileError::Container("0x06 token front-coding out of range")),
1142 };
1143 token.extend_from_slice(suffix);
1144 let off = c.uv()?;
1145 let len = c.uv()?;
1146 out.push(TokenEnt { token, off, len });
1147 }
1148 Ok(out)
1149}
1150
1151#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1153pub struct QTileEnt {
1154 pub first: (u32, u32),
1156 pub last: (u32, u32),
1158 pub clen: u64,
1160 pub raw: bool,
1162 pub syn: (u32, u32, u32, u32),
1164 pub off: u64,
1166}
1167
1168pub fn encode_qtile_leaf(ents: &[QTileEnt], leaf_off: u64) -> Vec<u8> {
1172 let mut o = Vec::new();
1173 let mut prev_g = 0u32;
1174 let mut next = leaf_off;
1175 for (i, e) in ents.iter().enumerate() {
1176 write_uvarint(
1177 &mut o,
1178 (if i == 0 {
1179 e.first.0
1180 } else {
1181 e.first.0 - prev_g
1182 }) as u64,
1183 );
1184 write_uvarint(&mut o, e.first.1 as u64);
1185 write_uvarint(&mut o, (e.last.0 - e.first.0) as u64);
1186 write_uvarint(&mut o, e.last.1 as u64);
1187 write_uvarint(&mut o, (e.clen << 1) | e.raw as u64);
1188 write_uvarint(&mut o, e.syn.0 as u64);
1189 write_uvarint(&mut o, e.syn.1.wrapping_sub(e.syn.0) as u64);
1190 write_uvarint(&mut o, e.syn.2 as u64);
1191 write_uvarint(&mut o, e.syn.3.wrapping_sub(e.syn.2) as u64);
1192 write_uvarint(&mut o, if e.off == next { 0 } else { e.off + 1 });
1193 next = e.off + e.clen;
1194 prev_g = e.first.0;
1195 }
1196 o
1197}
1198
1199pub fn decode_qtile_leaf(b: &[u8], n: usize, leaf_off: u64) -> Result<Vec<QTileEnt>, FileError> {
1201 let mut c = Cur::new(b);
1202 let mut out = Vec::with_capacity(n.min(b.len()));
1203 let mut prev_g = 0u32;
1204 let mut next = leaf_off;
1205 for i in 0..n {
1206 let d = c.u32v()?;
1207 let g = if i == 0 {
1208 d
1209 } else {
1210 prev_g
1211 .checked_add(d)
1212 .ok_or(FileError::Container("0x06 quad graph overflow"))?
1213 };
1214 let fa = c.u32v()?;
1215 let dg = c.u32v()?;
1216 let la = c.u32v()?;
1217 let packed = c.uv()?;
1218 let mb = c.u32v()?;
1219 let db = c.u32v()?;
1220 let mc = c.u32v()?;
1221 let dc = c.u32v()?;
1222 let oc = c.uv()?;
1223 let off = if oc == 0 { next } else { oc - 1 };
1224 let clen = packed >> 1;
1225 out.push(QTileEnt {
1226 first: (g, fa),
1227 last: (
1228 g.checked_add(dg)
1229 .ok_or(FileError::Container("0x06 quad graph overflow"))?,
1230 la,
1231 ),
1232 clen,
1233 raw: packed & 1 == 1,
1234 syn: (mb, mb.wrapping_add(db), mc, mc.wrapping_add(dc)),
1235 off,
1236 });
1237 next = off
1238 .checked_add(clen)
1239 .ok_or(FileError::Container("0x06 quad offset overflow"))?;
1240 prev_g = g;
1241 }
1242 Ok(out)
1243}
1244
1245pub fn cut(sizes: &[usize], target: usize) -> Vec<(usize, usize)> {
1248 let mut out = Vec::new();
1249 let mut start = 0usize;
1250 let mut acc = 0usize;
1251 for (i, &s) in sizes.iter().enumerate() {
1252 acc += s;
1253 if acc >= target {
1254 out.push((start, i + 1));
1255 start = i + 1;
1256 acc = 0;
1257 }
1258 }
1259 if start < sizes.len() {
1260 out.push((start, sizes.len()));
1261 }
1262 out
1263}
1264
1265pub fn logical_header(h: &Header06) -> crate::header::Header {
1271 use crate::header::{Section, SectionKind};
1272 let end = h.file_len;
1273 let mut flags = crate::header::FLAG_TILE_SYNOPSIS;
1274 if h.flags & F_NAMED != 0 {
1275 flags |= crate::header::FLAG_HAS_QUADS;
1276 }
1277 if h.flags & F_QUOTED != 0 {
1278 flags |= crate::header::FLAG_HAS_QUOTED_TRIPLES;
1279 }
1280 if h.has(P_QUAD) {
1281 flags |= crate::header::FLAG_QUAD_INDEX;
1282 }
1283 if h.flags & F_TEXT_NAMED != 0 && h.has(P_TEXT) {
1284 flags |= crate::header::FLAG_TEXT_INDEX_NAMED_GRAPHS;
1285 }
1286 let present = |bit: u16| if h.has(bit) { 1u64 } else { 0 };
1287 let mut extra = Vec::new();
1288 if h.has(P_LABELS) {
1289 extra.push(Section {
1290 kind: SectionKind::LabelIndex,
1291 flags: 0,
1292 offset: end,
1293 length: 1,
1294 });
1295 }
1296 if h.has(P_SCHEMA) {
1297 extra.push(Section {
1298 kind: SectionKind::Schema,
1299 flags: 0,
1300 offset: end,
1301 length: 1,
1302 });
1303 }
1304 if h.has(P_QUAD) {
1305 extra.push(Section {
1306 kind: SectionKind::QuadIndex,
1307 flags: 0,
1308 offset: end,
1309 length: 1,
1310 });
1311 }
1312 crate::header::Header {
1313 version: VERSION,
1314 flags,
1315 metadata_offset: end,
1316 metadata_len: h.card_len as u64,
1317 dictionary_offset: end,
1318 dictionary_len: 0,
1319 root_dir_offset: end,
1320 root_dir_len: 0,
1321 pyramid_meta_offset: end,
1322 pyramid_meta_len: present(P_PYRAMID),
1323 dict_codec: h.dict_codec,
1324 block_codec: h.block_codec,
1325 pyramid_levels: h.pyramid_levels,
1326 id_widths: h.id_widths,
1327 quad_count: h.quad_count,
1328 term_count: h.term_count,
1329 content_hash: h.content_hash,
1330 named_graphs_offset: 0,
1331 named_graphs_len: 0,
1332 schema_meta_len: 0,
1333 text_index_offset: end,
1334 text_index_len: present(P_TEXT),
1335 text_index_partial: h.has(P_TEXT_PARTIAL),
1336 build_info_offset: end,
1337 build_info_len: h.build_len as u64,
1338 perms: h.perms(),
1339 extra_sections: extra,
1340 }
1341}
1342
1343#[cfg(test)]
1344mod tests {
1345 use super::*;
1346
1347 #[test]
1348 fn header_round_trips() {
1349 let h = Header06 {
1350 flags: F_NAMED | F_QUAD_GRAPH_MAJOR,
1351 content_hash: [7; 16],
1352 file_len: 10_000,
1353 root_len: 300,
1354 card_region_len: 100,
1355 data_offset: 2_000,
1356 quad_count: 5,
1357 term_count: 9,
1358 graph_count: 2,
1359 perm_mask: 0b11_1111,
1360 dict_codec: 1,
1361 block_codec: 1,
1362 internal_codec: 1,
1363 pyramid_levels: 0,
1364 id_widths: 0,
1365 presence: P_TEXT | P_QUAD,
1366 card_off: 0,
1367 card_len: 40,
1368 card_digest: [3; 16],
1369 build_off: 40,
1370 build_len: 20,
1371 root_digest: [4; 16],
1372 };
1373 let b = h.to_bytes();
1374 assert_eq!(Header06::from_bytes(&b).unwrap(), h);
1375 let mut h2 = h.clone();
1377 h2.data_offset = 3_000;
1378 h2.build_len = 0;
1379 h2.file_len = 11_000;
1380 assert_eq!(content_hash(&h), content_hash(&h2));
1381 h2.card_digest = [9; 16];
1382 assert_ne!(content_hash(&h), content_hash(&h2));
1383 }
1384
1385 #[test]
1386 fn leaves_round_trip() {
1387 let c = vec![
1388 ChunkEnt {
1389 first_run: 0,
1390 key: vec![],
1391 clen: 10,
1392 },
1393 ChunkEnt {
1394 first_run: 5,
1395 key: b"ab".to_vec(),
1396 clen: 20,
1397 },
1398 ];
1399 assert_eq!(decode_chunk_leaf(&encode_chunk_leaf(&c), 2).unwrap(), c);
1400 let t = vec![
1401 TileEnt {
1402 min_a: 3,
1403 max_a: 9,
1404 clen: 100,
1405 syn: (1, 4, 2, 8),
1406 },
1407 TileEnt {
1408 min_a: 9,
1409 max_a: 20,
1410 clen: 7,
1411 syn: (0, 0, 5, 5),
1412 },
1413 ];
1414 assert_eq!(decode_tile_leaf(&encode_tile_leaf(&t), 2).unwrap(), t);
1415 let k = vec![
1416 TokenEnt {
1417 token: b"apple".to_vec(),
1418 off: 0,
1419 len: 3,
1420 },
1421 TokenEnt {
1422 token: b"apply".to_vec(),
1423 off: 3,
1424 len: 4,
1425 },
1426 ];
1427 assert_eq!(decode_token_leaf(&encode_token_leaf(&k), 2).unwrap(), k);
1428 let q = vec![
1429 QTileEnt {
1430 first: (5, 1),
1431 last: (6, 2),
1432 clen: 30,
1433 raw: true,
1434 syn: (0, 1, 2, 3),
1435 off: 100,
1436 },
1437 QTileEnt {
1438 first: (6, 3),
1439 last: (9, 0),
1440 clen: 10,
1441 raw: false,
1442 syn: (4, 4, 4, 4),
1443 off: 500,
1444 },
1445 ];
1446 assert_eq!(
1447 decode_qtile_leaf(&encode_qtile_leaf(&q, 100), 2, 100).unwrap(),
1448 q
1449 );
1450 }
1451
1452 #[test]
1453 fn cut_covers_everything() {
1454 assert_eq!(cut(&[5, 5, 5, 5, 5], 10), vec![(0, 2), (2, 4), (4, 5)]);
1455 assert_eq!(cut(&[], 10), Vec::<(usize, usize)>::new());
1456 assert_eq!(cut(&[50], 10), vec![(0, 1)]);
1457 }
1458}
1459
1460#[cfg(test)]
1461mod id_width_tests {
1462 use super::*;
1463
1464 fn sample() -> Header06 {
1465 Header06 {
1466 file_len: 10_000,
1467 root_len: 300,
1468 card_region_len: 100,
1469 data_offset: 2_000,
1470 perm_mask: 0b11_1111,
1471 pyramid_levels: 7,
1472 ..Default::default()
1473 }
1474 }
1475
1476 #[test]
1477 fn width_byte_round_trips_and_is_hashed() {
1478 let h = sample();
1479 assert_eq!(Header06::from_bytes(&h.to_bytes()).unwrap(), h);
1480 assert_eq!(h.to_bytes()[76], 7);
1481 assert_eq!(h.to_bytes()[77], 0);
1482 let mut other = h.clone();
1484 other.id_widths = 1;
1485 assert_ne!(content_hash(&h), content_hash(&other));
1486 }
1487
1488 #[test]
1489 fn a_reader_refuses_every_nonzero_width() {
1490 for (i, name) in id_position_names().iter().enumerate() {
1491 let mut b = sample().to_bytes();
1492 b[77] = 1 << (2 * i);
1493 let e = Header06::from_bytes(&b).unwrap_err().to_string();
1494 assert!(
1495 e.contains(&format!(
1496 "u64 term ids ({name}): not supported by this reader"
1497 )),
1498 "{e}"
1499 );
1500 for reserved in [2u8, 3] {
1501 let mut b = sample().to_bytes();
1502 b[77] = reserved << (2 * i);
1503 let e = Header06::from_bytes(&b).unwrap_err().to_string();
1504 assert!(e.contains("reserved term id width"), "{e}");
1505 }
1506 }
1507 }
1508
1509 #[test]
1510 fn a_writer_refuses_an_id_that_does_not_fit_u32() {
1511 assert_eq!(id_widths_for([u32::MAX as u64; 4]).unwrap(), 0);
1512 for (i, name) in id_position_names().iter().enumerate() {
1513 let mut m = [1u64; 4];
1514 m[i] = u32::MAX as u64 + 1;
1515 let e = id_widths_for(m).unwrap_err().to_string();
1516 assert!(
1517 e.contains(&format!("needs u64 term ids in {name}, not supported yet")),
1518 "{e}"
1519 );
1520 }
1521 }
1522}
1523
1524#[cfg(test)]
1525mod hostile_root_tests {
1526 use super::*;
1527
1528 fn sec(kind: u8, offset: u64, len: u64) -> Sec06 {
1529 Sec06 {
1530 kind,
1531 max_block: 0,
1532 offset,
1533 len,
1534 digest: [0; 16],
1535 }
1536 }
1537
1538 #[test]
1539 fn section_range_overflow_is_an_error() {
1540 let h = Header06 {
1541 data_offset: 100,
1542 ..Header06::default()
1543 };
1544 for (k, o, l) in [
1547 (kind::DICT_DATA, u64::MAX, 0),
1548 (kind::DICT_DATA, u64::MAX - 50, 10),
1549 (kind::DICT_DATA, 10, u64::MAX),
1550 (kind::DICT_LEAVES, u64::MAX, 1),
1551 ] {
1552 assert!(sec(k, o, l).abs(&h).is_err(), "kind {k} offset {o} len {l}");
1553 }
1554 let ok = sec(kind::DICT_DATA, 5, 7).abs(&h).unwrap();
1555 assert_eq!((ok.offset, ok.len), (105, 7));
1556 }
1557
1558 fn varints(vals: &[u64]) -> Vec<u8> {
1561 let mut v = Vec::new();
1562 for &x in vals {
1563 write_uvarint(&mut v, x);
1564 }
1565 v
1566 }
1567
1568 #[test]
1569 fn index_root_with_a_huge_leaf_count_is_refused() {
1570 let mut p = varints(&[1, 0, 1, 0, 0, 60]);
1572 p.resize(p.len() + 54, 0);
1573 assert!(decode_index_root(&p).is_err());
1574 }
1575
1576 #[test]
1577 fn text_root_with_a_huge_leaf_count_is_refused() {
1578 let mut p = varints(&[0, 1, 60]);
1580 p.resize(p.len() + 50, 0);
1581 assert!(decode_text_root(&p).is_err());
1582 }
1583
1584 #[test]
1585 fn quad_root_with_a_huge_leaf_count_is_refused() {
1586 let mut p = varints(&[1, 1, 1, 0, 0, 1, 0, 1, 60]);
1589 p.resize(p.len() + 50, 0);
1590 assert!(decode_quad_root(&p).is_err());
1591 }
1592}