1use crate::fastcdc::{FASTCDC_MAX_SIZE, FASTCDC_MIN_SIZE};
20use crate::hash::{Hash, Root};
21use crate::tree::{
22 check_branch, check_lookup, top_of, Carried, Leaf, ListKind, ListTree, Node, EMPTY_LIST,
23 MAX_LIST_ITEMS,
24};
25use crate::{Error, Result};
26use std::collections::BTreeMap;
27use std::num::NonZeroU32;
28use std::sync::Arc;
29
30pub const MAX_CHUNK_BYTES: usize = FASTCDC_MAX_SIZE;
32pub const LIST_ITEM_BYTES: usize = 36;
34pub const MAX_NAME_BYTES: usize = 255;
36pub const MAX_EXTRA_VALUES: usize = 32;
38pub const MAX_EXTRA_NAME_BYTES: usize = 64;
40pub const MAX_EXTRA_VALUE_BYTES: usize = 1024;
42pub const MAX_FOLDER_DEPTH: usize = 128;
44pub const MAX_CARRIED_NODES: usize = 80;
46pub const MAX_EXTRA_BYTES: usize =
49 2 + MAX_EXTRA_VALUES * (4 + MAX_EXTRA_NAME_BYTES + MAX_EXTRA_VALUE_BYTES);
50pub const MAX_RECORD_BYTES: usize = 66 + MAX_EXTRA_BYTES;
53pub const MAX_ENTRY_BYTES: usize = 43 + MAX_NAME_BYTES + MAX_EXTRA_BYTES;
56pub const CHUNKING_KEY: &str = "chunking";
58pub const TIMESTAMP_KEY: &str = "timestamp";
60pub const CHUNKING_FASTCDC_V1: &str = "fastcdc-v1";
62const CHUNKING_FIXED_PREFIX: &str = "fixed-";
63
64const FILE_LEAF_MARK: u8 = 0x00;
65const FOLDER_LEAF_MARK: u8 = 0x02;
66const FILE_MARK: u8 = 0x10;
67const FOLDER_MARK: u8 = 0x11;
68pub(crate) const RECORD_MARK: u8 = 0x20;
69const KIND_FILE: u8 = 1;
70const KIND_FOLDER: u8 = 2;
71
72fn invalid(detail: impl Into<String>) -> Error {
73 Error::InvalidData {
74 detail: detail.into(),
75 }
76}
77
78pub(crate) struct Reader<'a> {
80 bytes: &'a [u8],
81 what: &'static str,
82}
83
84impl<'a> Reader<'a> {
85 pub(crate) fn new(bytes: &'a [u8], what: &'static str) -> Self {
86 Self { bytes, what }
87 }
88
89 pub(crate) fn take(&mut self, count: usize) -> Result<&'a [u8]> {
90 if self.bytes.len() < count {
91 return Err(invalid(format!("{} is cut short", self.what)));
92 }
93 let (head, tail) = self.bytes.split_at(count);
94 self.bytes = tail;
95 Ok(head)
96 }
97
98 fn array<const N: usize>(&mut self) -> Result<[u8; N]> {
99 let mut array = [0_u8; N];
100 array.copy_from_slice(self.take(N)?);
101 Ok(array)
102 }
103
104 pub(crate) fn u8(&mut self) -> Result<u8> {
105 Ok(self.array::<1>()?[0])
106 }
107
108 pub(crate) fn u16(&mut self) -> Result<u16> {
109 Ok(u16::from_be_bytes(self.array()?))
110 }
111
112 pub(crate) fn u32(&mut self) -> Result<u32> {
113 Ok(u32::from_be_bytes(self.array()?))
114 }
115
116 pub(crate) fn u64(&mut self) -> Result<u64> {
117 Ok(u64::from_be_bytes(self.array()?))
118 }
119
120 pub(crate) fn hash(&mut self) -> Result<Hash> {
121 Ok(Hash::from_bytes(self.array()?))
122 }
123
124 pub(crate) fn remaining(&self) -> usize {
125 self.bytes.len()
126 }
127
128 pub(crate) fn is_empty(&self) -> bool {
129 self.bytes.is_empty()
130 }
131
132 pub(crate) fn finish(self) -> Result<()> {
134 if self.bytes.is_empty() {
135 Ok(())
136 } else {
137 Err(invalid(format!("{} has bytes after its end", self.what)))
138 }
139 }
140}
141
142#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
144pub enum Kind {
145 File,
146 Folder,
147}
148
149impl Kind {
150 fn byte(self) -> u8 {
151 match self {
152 Self::File => KIND_FILE,
153 Self::Folder => KIND_FOLDER,
154 }
155 }
156
157 fn from_byte(byte: u8) -> Result<Self> {
158 match byte {
159 KIND_FILE => Ok(Self::File),
160 KIND_FOLDER => Ok(Self::Folder),
161 _ => Err(invalid("an entry is neither a file nor a folder")),
162 }
163 }
164}
165
166#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
169pub struct Target {
170 pub kind: Kind,
171 pub hash: Hash,
172 pub size: u64,
173}
174
175impl Target {
176 pub(crate) fn require(&self, kind: Kind) -> Result<()> {
177 if self.kind == kind {
178 Ok(())
179 } else {
180 Err(invalid(match kind {
181 Kind::File => "a folder was given where a file is needed",
182 Kind::Folder => "a file was given where a folder is needed",
183 }))
184 }
185 }
186}
187
188pub fn check_name(name: &str) -> Result<()> {
190 let reason = if name.is_empty() {
191 "it is empty"
192 } else if name.len() > MAX_NAME_BYTES {
193 "it is longer than 255 bytes"
194 } else if name == "." || name == ".." {
195 "it is a dot name"
196 } else if name.contains('/') {
197 "it holds a slash"
198 } else if name.contains('\0') {
199 "it holds a zero byte"
200 } else {
201 return Ok(());
202 };
203 Err(Error::InvalidName {
204 name: name.chars().take(80).collect(),
205 reason,
206 })
207}
208
209#[derive(Clone, Debug, Default, Eq, PartialEq)]
213pub struct ExtraData {
214 values: BTreeMap<String, Vec<u8>>,
215}
216
217impl ExtraData {
218 pub fn new() -> Self {
219 Self::default()
220 }
221
222 pub fn insert(&mut self, name: impl Into<String>, value: impl Into<Vec<u8>>) -> Result<()> {
224 let name = name.into();
225 let value = value.into();
226 if name.is_empty() || name.len() > MAX_EXTRA_NAME_BYTES {
227 return Err(invalid("the name of an extra value is not 1 to 64 bytes"));
228 }
229 if value.len() > MAX_EXTRA_VALUE_BYTES {
230 return Err(invalid("an extra value is longer than 1,024 bytes"));
231 }
232 if !self.values.contains_key(&name) && self.values.len() >= MAX_EXTRA_VALUES {
233 return Err(invalid("extra data holds more than 32 values"));
234 }
235 self.values.insert(name, value);
236 Ok(())
237 }
238
239 pub fn with(mut self, name: impl Into<String>, value: impl Into<Vec<u8>>) -> Result<Self> {
241 self.insert(name, value)?;
242 Ok(self)
243 }
244
245 pub fn get(&self, name: &str) -> Option<&[u8]> {
246 self.values.get(name).map(Vec::as_slice)
247 }
248
249 pub fn text(&self, name: &str) -> Option<&str> {
251 self.get(name)
252 .and_then(|value| std::str::from_utf8(value).ok())
253 }
254
255 pub fn remove(&mut self, name: &str) -> Option<Vec<u8>> {
256 self.values.remove(name)
257 }
258
259 pub fn len(&self) -> usize {
260 self.values.len()
261 }
262
263 pub fn is_empty(&self) -> bool {
264 self.values.is_empty()
265 }
266
267 pub fn iter(&self) -> impl Iterator<Item = (&str, &[u8])> {
269 self.values
270 .iter()
271 .map(|(name, value)| (name.as_str(), value.as_slice()))
272 }
273
274 pub(crate) fn encoded_len(&self) -> usize {
275 2 + self
276 .values
277 .iter()
278 .map(|(name, value)| 4 + name.len() + value.len())
279 .sum::<usize>()
280 }
281
282 pub(crate) fn encode_into(&self, out: &mut Vec<u8>) {
283 out.extend_from_slice(&(self.values.len() as u16).to_be_bytes());
284 for (name, value) in &self.values {
285 out.extend_from_slice(&(name.len() as u16).to_be_bytes());
286 out.extend_from_slice(name.as_bytes());
287 out.extend_from_slice(&(value.len() as u16).to_be_bytes());
288 out.extend_from_slice(value);
289 }
290 }
291
292 pub(crate) fn decode(reader: &mut Reader<'_>) -> Result<Self> {
293 let count = usize::from(reader.u16()?);
294 if count > MAX_EXTRA_VALUES {
295 return Err(invalid("extra data holds more than 32 values"));
296 }
297 let mut values = BTreeMap::new();
298 let mut previous: Option<&[u8]> = None;
299 for _ in 0..count {
300 let name_len = usize::from(reader.u16()?);
301 if name_len == 0 || name_len > MAX_EXTRA_NAME_BYTES {
302 return Err(invalid("the name of an extra value is not 1 to 64 bytes"));
303 }
304 let name = reader.take(name_len)?;
305 if previous.is_some_and(|previous| previous >= name) {
306 return Err(invalid(
307 "extra values are not in the order of their names, or a name is there twice",
308 ));
309 }
310 previous = Some(name);
311 let name = std::str::from_utf8(name)
312 .map_err(|_| invalid("the name of an extra value is not UTF-8"))?;
313 let value_len = usize::from(reader.u16()?);
314 if value_len > MAX_EXTRA_VALUE_BYTES {
315 return Err(invalid("an extra value is longer than 1,024 bytes"));
316 }
317 values.insert(name.to_owned(), reader.take(value_len)?.to_vec());
318 }
319 Ok(Self { values })
320 }
321}
322
323#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
325pub struct ChunkRef {
326 pub hash: Hash,
327 pub length: u32,
328}
329
330impl ChunkRef {
331 pub fn of(bytes: &[u8]) -> Result<Self> {
333 let item = Self {
334 hash: Hash::of(bytes),
335 length: u32::try_from(bytes.len()).unwrap_or(u32::MAX),
336 };
337 item.check()?;
338 Ok(item)
339 }
340
341 fn check(&self) -> Result<()> {
342 if self.length == 0 || self.length as usize > MAX_CHUNK_BYTES {
343 return Err(invalid("a chunk does not hold 1 byte to 8 MiB"));
344 }
345 Ok(())
346 }
347
348 pub fn matches(&self, bytes: &[u8]) -> bool {
351 bytes.len() as u64 == u64::from(self.length) && Hash::of(bytes) == self.hash
352 }
353
354 fn encode_into(&self, out: &mut Vec<u8>) {
355 out.extend_from_slice(self.hash.as_bytes());
356 out.extend_from_slice(&self.length.to_be_bytes());
357 }
358
359 fn decode(reader: &mut Reader<'_>) -> Result<Self> {
360 let item = Self {
361 hash: reader.hash()?,
362 length: reader.u32()?,
363 };
364 item.check()?;
365 Ok(item)
366 }
367
368 pub(crate) fn leaf(&self) -> Node {
370 let mut bytes = [0_u8; 1 + LIST_ITEM_BYTES];
371 bytes[0] = FILE_LEAF_MARK;
372 bytes[1..33].copy_from_slice(self.hash.as_bytes());
373 bytes[33..].copy_from_slice(&self.length.to_be_bytes());
374 Node {
375 hash: Hash::of(&bytes),
376 size: u64::from(self.length),
377 }
378 }
379}
380
381#[derive(Clone, Debug, Eq, PartialEq)]
383pub struct Entry {
384 name: String,
385 target: Target,
386 extra: ExtraData,
387}
388
389impl Entry {
390 pub fn new(name: impl Into<String>, target: Target, extra: ExtraData) -> Result<Self> {
391 let name = name.into();
392 check_name(&name)?;
393 Ok(Self {
394 name,
395 target,
396 extra,
397 })
398 }
399
400 pub fn name(&self) -> &str {
401 &self.name
402 }
403
404 pub fn kind(&self) -> Kind {
405 self.target.kind
406 }
407
408 pub fn size(&self) -> u64 {
410 self.target.size
411 }
412
413 pub fn hash(&self) -> &Hash {
414 &self.target.hash
415 }
416
417 pub fn target(&self) -> Target {
419 self.target
420 }
421
422 pub fn extra(&self) -> &ExtraData {
423 &self.extra
424 }
425
426 pub fn encoded_len(&self) -> usize {
428 1 + 8 + 32 + 2 + self.name.len() + self.extra.encoded_len()
429 }
430
431 pub(crate) fn encode_into(&self, out: &mut Vec<u8>) {
432 out.push(self.target.kind.byte());
433 out.extend_from_slice(&self.target.size.to_be_bytes());
434 out.extend_from_slice(self.target.hash.as_bytes());
435 out.extend_from_slice(&(self.name.len() as u16).to_be_bytes());
436 out.extend_from_slice(self.name.as_bytes());
437 self.extra.encode_into(out);
438 }
439
440 pub(crate) fn decode(reader: &mut Reader<'_>) -> Result<Self> {
441 let kind = Kind::from_byte(reader.u8()?)?;
442 let size = reader.u64()?;
443 let hash = reader.hash()?;
444 let name_len = usize::from(reader.u16()?);
445 let name = std::str::from_utf8(reader.take(name_len)?)
446 .map_err(|_| invalid("a name is not UTF-8"))?;
447 check_name(name)?;
448 let extra = ExtraData::decode(reader)?;
449 Ok(Self {
450 name: name.to_owned(),
451 target: Target { kind, hash, size },
452 extra,
453 })
454 }
455
456 pub(crate) fn leaf(&self) -> Node {
458 let mut bytes = Vec::with_capacity(1 + self.encoded_len());
459 bytes.push(FOLDER_LEAF_MARK);
460 self.encode_into(&mut bytes);
461 Node {
462 hash: Hash::of(&bytes),
463 size: self.target.size,
464 }
465 }
466}
467
468fn owner_hash(mark: u8, count: u64, size: u64, list: &Hash) -> Hash {
469 let mut bytes = [0_u8; 49];
470 bytes[0] = mark;
471 bytes[1..9].copy_from_slice(&count.to_be_bytes());
472 bytes[9..17].copy_from_slice(&size.to_be_bytes());
473 bytes[17..].copy_from_slice(list.as_bytes());
474 Hash::of(&bytes)
475}
476
477pub fn file_hash(count: u64, size: u64, list: &Hash) -> Hash {
480 owner_hash(FILE_MARK, count, size, list)
481}
482
483pub fn folder_hash(count: u64, size: u64, list: &Hash) -> Hash {
486 owner_hash(FOLDER_MARK, count, size, list)
487}
488
489fn confirm(target: &Target, count: u64, top: Node) -> Result<()> {
491 let (what, hash) = match target.kind {
492 Kind::File => ("a file's list", file_hash(count, top.size, &top.hash)),
493 Kind::Folder => ("a folder's list", folder_hash(count, top.size, &top.hash)),
494 };
495 if top.size != target.size {
496 return Err(Error::SizeMismatch {
497 what,
498 expected: target.size,
499 actual: top.size,
500 });
501 }
502 if hash != target.hash {
503 return Err(Error::HashMismatch { what });
504 }
505 Ok(())
506}
507
508#[derive(Clone, Copy, Debug, Eq, PartialEq)]
510pub enum Chunking {
511 FastCdcV1,
514 Fixed(NonZeroU32),
516}
517
518impl Chunking {
519 pub fn fixed(size: u32) -> Result<Self> {
521 NonZeroU32::new(size)
522 .filter(|size| size.get() as usize <= MAX_CHUNK_BYTES)
523 .map(Self::Fixed)
524 .ok_or_else(|| invalid("a fixed chunk size is not 1 byte to 8 MiB"))
525 }
526
527 pub fn tag(self) -> String {
529 match self {
530 Self::FastCdcV1 => CHUNKING_FASTCDC_V1.to_owned(),
531 Self::Fixed(size) => format!("{CHUNKING_FIXED_PREFIX}{size}"),
532 }
533 }
534
535 pub fn from_tag(tag: &[u8]) -> Result<Self> {
538 let unknown = || invalid("a record names a way of chunking that is not known");
539 if tag == CHUNKING_FASTCDC_V1.as_bytes() {
540 return Ok(Self::FastCdcV1);
541 }
542 let digits = tag
543 .strip_prefix(CHUNKING_FIXED_PREFIX.as_bytes())
544 .ok_or_else(unknown)?;
545 if digits.is_empty()
546 || digits.len() > 7
547 || digits[0] == b'0'
548 || !digits.iter().all(u8::is_ascii_digit)
549 {
550 return Err(unknown());
551 }
552 let size = digits
553 .iter()
554 .fold(0_u32, |size, digit| size * 10 + u32::from(digit - b'0'));
555 Self::fixed(size).map_err(|_| unknown())
556 }
557
558 pub fn check_length(self, length: u32, is_last: bool) -> Result<()> {
561 let length = length as usize;
562 let fits = match self {
563 Self::FastCdcV1 => {
564 (1..=FASTCDC_MAX_SIZE).contains(&length) && (is_last || length > FASTCDC_MIN_SIZE)
565 }
566 Self::Fixed(size) => {
567 let size = size.get() as usize;
568 if is_last {
569 (1..=size).contains(&length)
570 } else {
571 length == size
572 }
573 }
574 };
575 if fits {
576 Ok(())
577 } else {
578 Err(invalid(
579 "a chunk has a length that the tree's way of chunking does not give",
580 ))
581 }
582 }
583
584 pub fn count_bounds(self, size: u64) -> (u64, u64) {
586 if size == 0 {
587 return (0, 0);
588 }
589 match self {
590 Self::FastCdcV1 => (
591 size.div_ceil(FASTCDC_MAX_SIZE as u64),
592 (size - 1) / (FASTCDC_MIN_SIZE as u64 + 1) + 1,
593 ),
594 Self::Fixed(chunk) => {
595 let count = size.div_ceil(u64::from(chunk.get()));
596 (count, count)
597 }
598 }
599 }
600
601 pub fn check_count(self, size: u64, count: u64) -> Result<()> {
603 let (fewest, most) = self.count_bounds(size);
604 if (fewest..=most).contains(&count) {
605 Ok(())
606 } else {
607 Err(invalid(
608 "a file has a number of chunks that its size does not allow",
609 ))
610 }
611 }
612}
613
614#[derive(Clone, Debug, Eq, PartialEq)]
616pub struct FileList {
617 items: Vec<ChunkRef>,
618 size: u64,
619 hash: Hash,
620}
621
622impl FileList {
623 pub fn new(items: Vec<ChunkRef>) -> Result<Self> {
626 let mut leaves = Vec::with_capacity(items.len());
627 for item in &items {
628 item.check()?;
629 leaves.push(Leaf {
630 node: item.leaf(),
631 name: &[],
632 });
633 }
634 let top = top_of(ListKind::File, &leaves)?;
635 Ok(Self {
636 hash: file_hash(items.len() as u64, top.size, &top.hash),
637 size: top.size,
638 items,
639 })
640 }
641
642 fn items_of(bytes: &[u8]) -> Result<Vec<ChunkRef>> {
644 if bytes.len() % LIST_ITEM_BYTES != 0 {
645 return Err(invalid("a file's list is not a whole number of items"));
646 }
647 let mut reader = Reader::new(bytes, "a file's list");
648 let mut items = Vec::with_capacity(bytes.len() / LIST_ITEM_BYTES);
649 while !reader.is_empty() {
650 items.push(ChunkRef::decode(&mut reader)?);
651 }
652 Ok(items)
653 }
654
655 pub fn decode(bytes: &[u8]) -> Result<Self> {
657 Self::new(Self::items_of(bytes)?)
658 }
659
660 pub fn encode(&self) -> Vec<u8> {
661 let mut out = Vec::with_capacity(self.items.len() * LIST_ITEM_BYTES);
662 for item in &self.items {
663 item.encode_into(&mut out);
664 }
665 out
666 }
667
668 pub fn items(&self) -> &[ChunkRef] {
669 &self.items
670 }
671
672 pub fn count(&self) -> u64 {
674 self.items.len() as u64
675 }
676
677 pub fn size(&self) -> u64 {
679 self.size
680 }
681
682 pub fn hash(&self) -> &Hash {
685 &self.hash
686 }
687
688 pub fn target(&self) -> Target {
689 Target {
690 kind: Kind::File,
691 hash: self.hash,
692 size: self.size,
693 }
694 }
695
696 pub fn encoded_len(&self) -> u64 {
698 self.items.len() as u64 * LIST_ITEM_BYTES as u64
699 }
700
701 pub fn check_chunking(&self, chunking: Chunking) -> Result<()> {
703 chunking.check_count(self.size, self.count())?;
704 let last = self.items.len().saturating_sub(1);
705 for (index, item) in self.items.iter().enumerate() {
706 chunking.check_length(item.length, index == last)?;
707 }
708 Ok(())
709 }
710
711 fn leaves(&self) -> Vec<Leaf<'static>> {
712 self.items
713 .iter()
714 .map(|item| Leaf {
715 node: item.leaf(),
716 name: &[],
717 })
718 .collect()
719 }
720
721 pub fn open(&self, start: u64, end: u64) -> Result<FileBranch> {
724 let tree = ListTree::build(ListKind::File, &self.leaves())?;
725 self.open_with(&tree, start, end)
726 }
727
728 fn open_with(&self, tree: &ListTree, start: u64, end: u64) -> Result<FileBranch> {
729 let carried = tree.open(start, end)?;
730 Ok(FileBranch {
731 count: self.count(),
732 start,
733 items: self.items[start as usize..end as usize].to_vec(),
734 carried,
735 })
736 }
737}
738
739#[derive(Clone, Debug)]
742pub struct OpenFile {
743 list: Arc<FileList>,
744 tree: ListTree,
745 starts: Vec<u64>,
747}
748
749impl OpenFile {
750 pub fn new(list: FileList) -> Result<Self> {
751 Self::shared(Arc::new(list))
752 }
753
754 pub fn shared(list: Arc<FileList>) -> Result<Self> {
756 let tree = ListTree::build(ListKind::File, &list.leaves())?;
757 Ok(Self::with_tree(list, tree))
758 }
759
760 pub fn decode(bytes: &[u8]) -> Result<Self> {
763 let items = FileList::items_of(bytes)?;
764 let leaves: Vec<Leaf<'static>> = items
765 .iter()
766 .map(|item| Leaf {
767 node: item.leaf(),
768 name: &[],
769 })
770 .collect();
771 let tree = ListTree::build(ListKind::File, &leaves)?;
772 let top = tree.top()?;
773 let list = FileList {
774 hash: file_hash(items.len() as u64, top.size, &top.hash),
775 size: top.size,
776 items,
777 };
778 Ok(Self::with_tree(Arc::new(list), tree))
779 }
780
781 fn with_tree(list: Arc<FileList>, tree: ListTree) -> Self {
782 let mut starts = Vec::with_capacity(list.items.len() + 1);
783 let mut at = 0_u64;
784 for item in &list.items {
785 starts.push(at);
786 at += u64::from(item.length);
787 }
788 starts.push(at);
789 Self { list, tree, starts }
790 }
791
792 pub fn list(&self) -> &FileList {
793 &self.list
794 }
795
796 pub fn shared_list(&self) -> Arc<FileList> {
798 Arc::clone(&self.list)
799 }
800
801 pub fn start_of(&self, index: u64) -> Option<u64> {
803 self.starts.get(usize::try_from(index).ok()?).copied()
804 }
805
806 pub fn chunks_for(&self, offset: u64, length: u64) -> Result<(u64, u64)> {
810 let end = offset
811 .checked_add(length)
812 .filter(|end| length > 0 && *end <= self.list.size)
813 .ok_or_else(|| invalid("a stretch of bytes is outside the file"))?;
814 let first = self.starts.partition_point(|start| *start <= offset) - 1;
816 let after = self.starts.partition_point(|start| *start < end);
817 Ok((first as u64, after as u64))
818 }
819
820 pub fn open(&self, start: u64, end: u64) -> Result<FileBranch> {
822 self.list.open_with(&self.tree, start, end)
823 }
824
825 pub fn open_bytes(&self, offset: u64, length: u64) -> Result<FileBranch> {
827 let (start, end) = self.chunks_for(offset, length)?;
828 self.open(start, end)
829 }
830}
831
832#[derive(Clone, Debug, Eq, PartialEq)]
834pub struct FileBranch {
835 count: u64,
836 start: u64,
837 items: Vec<ChunkRef>,
838 carried: Vec<Carried>,
839}
840
841impl FileBranch {
842 pub fn count(&self) -> u64 {
844 self.count
845 }
846
847 pub fn start(&self) -> u64 {
849 self.start
850 }
851
852 pub fn items(&self) -> &[ChunkRef] {
853 &self.items
854 }
855
856 pub fn encode(&self) -> Vec<u8> {
857 let mut out =
858 Vec::with_capacity(22 + self.items.len() * LIST_ITEM_BYTES + self.carried.len() * 40);
859 out.extend_from_slice(&self.count.to_be_bytes());
860 out.extend_from_slice(&self.start.to_be_bytes());
861 out.extend_from_slice(&(self.items.len() as u32).to_be_bytes());
862 for item in &self.items {
863 item.encode_into(&mut out);
864 }
865 out.extend_from_slice(&(self.carried.len() as u16).to_be_bytes());
866 for carried in &self.carried {
867 out.extend_from_slice(carried.node.hash.as_bytes());
868 out.extend_from_slice(&carried.node.size.to_be_bytes());
869 }
870 out
871 }
872
873 pub fn decode(bytes: &[u8]) -> Result<Self> {
874 let mut reader = Reader::new(bytes, "a branch of a file's list");
875 let (count, start, shown) = branch_header(&mut reader)?;
876 if shown == 0 || reader.remaining() / LIST_ITEM_BYTES < shown {
877 return Err(invalid(
878 "a branch of a file's list is cut short, or shows nothing",
879 ));
880 }
881 let mut items = Vec::with_capacity(shown);
882 for _ in 0..shown {
883 items.push(ChunkRef::decode(&mut reader)?);
884 }
885 let mut carried = Vec::new();
886 for _ in 0..carried_count(&mut reader)? {
887 carried.push(Carried {
888 node: Node {
889 hash: reader.hash()?,
890 size: reader.u64()?,
891 },
892 first_name: Vec::new(),
893 });
894 }
895 reader.finish()?;
896 Ok(Self {
897 count,
898 start,
899 items,
900 carried,
901 })
902 }
903
904 pub fn check(&self, file: &Target, chunking: Option<Chunking>) -> Result<u64> {
908 file.require(Kind::File)?;
909 if let Some(chunking) = chunking {
910 chunking.check_count(file.size, self.count)?;
911 for (place, item) in (self.start..).zip(&self.items) {
912 chunking.check_length(item.length, place + 1 == self.count)?;
913 }
914 }
915 let leaves: Vec<Leaf<'_>> = self
916 .items
917 .iter()
918 .map(|item| Leaf {
919 node: item.leaf(),
920 name: &[],
921 })
922 .collect();
923 let shown = check_branch(
924 ListKind::File,
925 self.count,
926 self.start,
927 &leaves,
928 &self.carried,
929 )?;
930 confirm(file, self.count, shown.top)?;
931 Ok(shown.offset)
932 }
933}
934
935fn branch_header(reader: &mut Reader<'_>) -> Result<(u64, u64, usize)> {
938 let count = reader.u64()?;
939 let start = reader.u64()?;
940 let shown = reader.u32()?;
941 let inside = start
942 .checked_add(u64::from(shown))
943 .is_some_and(|end| end <= count);
944 if count > MAX_LIST_ITEMS || !inside {
945 return Err(invalid("a branch lies outside its list"));
946 }
947 Ok((count, start, shown as usize))
948}
949
950fn carried_count(reader: &mut Reader<'_>) -> Result<usize> {
951 let count = usize::from(reader.u16()?);
952 if count > MAX_CARRIED_NODES {
953 return Err(invalid("a branch carries more nodes than any list needs"));
954 }
955 Ok(count)
956}
957
958#[derive(Clone, Debug, Eq, PartialEq)]
960pub struct FolderList {
961 entries: Vec<Entry>,
962 size: u64,
963 hash: Hash,
964 encoded_len: u64,
965}
966
967impl FolderList {
968 pub fn new(entries: Vec<Entry>) -> Result<Self> {
971 let leaves: Vec<Leaf<'_>> = entries
972 .iter()
973 .map(|entry| Leaf {
974 node: entry.leaf(),
975 name: entry.name.as_bytes(),
976 })
977 .collect();
978 let top = top_of(ListKind::Folder, &leaves)?;
979 let encoded_len = entries.iter().map(|entry| entry.encoded_len() as u64).sum();
980 Ok(Self {
981 hash: folder_hash(entries.len() as u64, top.size, &top.hash),
982 size: top.size,
983 encoded_len,
984 entries,
985 })
986 }
987
988 fn entries_of(bytes: &[u8]) -> Result<Vec<Entry>> {
990 let mut reader = Reader::new(bytes, "a folder's list");
991 let mut entries = Vec::new();
992 while !reader.is_empty() {
993 entries.push(Entry::decode(&mut reader)?);
994 }
995 Ok(entries)
996 }
997
998 pub fn decode(bytes: &[u8]) -> Result<Self> {
1000 Self::new(Self::entries_of(bytes)?)
1001 }
1002
1003 pub fn encode(&self) -> Vec<u8> {
1004 let mut out = Vec::with_capacity(self.encoded_len as usize);
1005 for entry in &self.entries {
1006 entry.encode_into(&mut out);
1007 }
1008 out
1009 }
1010
1011 pub fn entries(&self) -> &[Entry] {
1012 &self.entries
1013 }
1014
1015 pub fn count(&self) -> u64 {
1017 self.entries.len() as u64
1018 }
1019
1020 pub fn size(&self) -> u64 {
1022 self.size
1023 }
1024
1025 pub fn hash(&self) -> &Hash {
1029 &self.hash
1030 }
1031
1032 pub fn target(&self) -> Target {
1033 Target {
1034 kind: Kind::Folder,
1035 hash: self.hash,
1036 size: self.size,
1037 }
1038 }
1039
1040 pub fn encoded_len(&self) -> u64 {
1042 self.encoded_len
1043 }
1044
1045 pub fn get(&self, name: &str) -> Option<&Entry> {
1047 self.entries
1048 .binary_search_by(|entry| entry.name.as_str().cmp(name))
1049 .ok()
1050 .map(|index| &self.entries[index])
1051 }
1052
1053 pub fn place_of(&self, name: &str) -> Option<u64> {
1056 if self.entries.is_empty() {
1057 return None;
1058 }
1059 let not_after = self
1060 .entries
1061 .partition_point(|entry| entry.name.as_str() <= name);
1062 Some(not_after.saturating_sub(1) as u64)
1063 }
1064
1065 fn leaves(&self) -> Vec<Leaf<'_>> {
1066 self.entries
1067 .iter()
1068 .map(|entry| Leaf {
1069 node: entry.leaf(),
1070 name: entry.name.as_bytes(),
1071 })
1072 .collect()
1073 }
1074
1075 pub fn open(&self, start: u64, end: u64) -> Result<FolderBranch> {
1078 let tree = ListTree::build(ListKind::Folder, &self.leaves())?;
1079 self.open_with(&tree, start, end)
1080 }
1081
1082 pub fn open_name(&self, name: &str) -> Result<FolderBranch> {
1085 let tree = ListTree::build(ListKind::Folder, &self.leaves())?;
1086 self.open_name_with(&tree, name)
1087 }
1088
1089 fn open_with(&self, tree: &ListTree, start: u64, end: u64) -> Result<FolderBranch> {
1090 let carried = tree.open(start, end)?;
1091 Ok(FolderBranch {
1092 count: self.count(),
1093 start,
1094 entries: self.entries[start as usize..end as usize].to_vec(),
1095 carried,
1096 })
1097 }
1098
1099 fn open_name_with(&self, tree: &ListTree, name: &str) -> Result<FolderBranch> {
1100 check_name(name)?;
1101 match self.place_of(name) {
1102 Some(place) => self.open_with(tree, place, place + 1),
1103 None => Ok(FolderBranch {
1104 count: 0,
1105 start: 0,
1106 entries: Vec::new(),
1107 carried: Vec::new(),
1108 }),
1109 }
1110 }
1111}
1112
1113#[derive(Clone, Debug)]
1115pub struct OpenFolder {
1116 list: FolderList,
1117 tree: ListTree,
1118}
1119
1120impl OpenFolder {
1121 pub fn new(list: FolderList) -> Result<Self> {
1122 let tree = ListTree::build(ListKind::Folder, &list.leaves())?;
1123 Ok(Self { list, tree })
1124 }
1125
1126 pub fn decode(bytes: &[u8]) -> Result<Self> {
1129 let entries = FolderList::entries_of(bytes)?;
1130 let leaves: Vec<Leaf<'_>> = entries
1131 .iter()
1132 .map(|entry| Leaf {
1133 node: entry.leaf(),
1134 name: entry.name.as_bytes(),
1135 })
1136 .collect();
1137 let tree = ListTree::build(ListKind::Folder, &leaves)?;
1138 let top = tree.top()?;
1139 drop(leaves);
1140 let encoded_len = entries.iter().map(|entry| entry.encoded_len() as u64).sum();
1141 let list = FolderList {
1142 hash: folder_hash(entries.len() as u64, top.size, &top.hash),
1143 size: top.size,
1144 encoded_len,
1145 entries,
1146 };
1147 Ok(Self { list, tree })
1148 }
1149
1150 pub fn list(&self) -> &FolderList {
1151 &self.list
1152 }
1153
1154 pub fn open(&self, start: u64, end: u64) -> Result<FolderBranch> {
1156 self.list.open_with(&self.tree, start, end)
1157 }
1158
1159 pub fn open_name(&self, name: &str) -> Result<FolderBranch> {
1161 self.list.open_name_with(&self.tree, name)
1162 }
1163}
1164
1165#[derive(Clone, Debug, Eq, PartialEq)]
1168pub struct FolderBranch {
1169 count: u64,
1170 start: u64,
1171 entries: Vec<Entry>,
1172 carried: Vec<Carried>,
1173}
1174
1175impl FolderBranch {
1176 pub(crate) fn empty() -> Self {
1178 Self {
1179 count: 0,
1180 start: 0,
1181 entries: Vec::new(),
1182 carried: Vec::new(),
1183 }
1184 }
1185
1186 pub fn count(&self) -> u64 {
1188 self.count
1189 }
1190
1191 pub fn start(&self) -> u64 {
1193 self.start
1194 }
1195
1196 pub fn entries(&self) -> &[Entry] {
1197 &self.entries
1198 }
1199
1200 pub fn encode(&self) -> Vec<u8> {
1201 let mut out = Vec::new();
1202 out.extend_from_slice(&self.count.to_be_bytes());
1203 out.extend_from_slice(&self.start.to_be_bytes());
1204 out.extend_from_slice(&(self.entries.len() as u32).to_be_bytes());
1205 for entry in &self.entries {
1206 entry.encode_into(&mut out);
1207 }
1208 out.extend_from_slice(&(self.carried.len() as u16).to_be_bytes());
1209 for carried in &self.carried {
1210 out.extend_from_slice(carried.node.hash.as_bytes());
1211 out.extend_from_slice(&carried.node.size.to_be_bytes());
1212 out.extend_from_slice(&(carried.first_name.len() as u16).to_be_bytes());
1213 out.extend_from_slice(&carried.first_name);
1214 }
1215 out
1216 }
1217
1218 pub fn decode(bytes: &[u8]) -> Result<Self> {
1219 let mut reader = Reader::new(bytes, "a branch of a folder's list");
1220 let (count, start, shown) = branch_header(&mut reader)?;
1221 if (shown == 0) != (count == 0) {
1222 return Err(invalid("a branch of a folder's list shows nothing"));
1223 }
1224 if reader.remaining() / 45 < shown {
1226 return Err(invalid("a branch of a folder's list is cut short"));
1227 }
1228 let mut entries = Vec::with_capacity(shown);
1229 for _ in 0..shown {
1230 entries.push(Entry::decode(&mut reader)?);
1231 }
1232 let mut carried = Vec::new();
1233 for index in 0..carried_count(&mut reader)? {
1234 let node = Node {
1235 hash: reader.hash()?,
1236 size: reader.u64()?,
1237 };
1238 let name_len = usize::from(reader.u16()?);
1239 let begins_the_list = index == 0 && start > 0;
1243 if begins_the_list != (name_len == 0) {
1244 return Err(invalid(if begins_the_list {
1245 "the carried node that begins a folder's list has a name"
1246 } else {
1247 "a carried node of a folder's list has no name"
1248 }));
1249 }
1250 if name_len > MAX_NAME_BYTES {
1251 return Err(invalid("a carried name is longer than 255 bytes"));
1252 }
1253 carried.push(Carried {
1254 node,
1255 first_name: reader.take(name_len)?.to_vec(),
1256 });
1257 }
1258 reader.finish()?;
1259 if count == 0 && !carried.is_empty() {
1260 return Err(invalid("a branch of an empty folder carries nodes"));
1261 }
1262 Ok(Self {
1263 count,
1264 start,
1265 entries,
1266 carried,
1267 })
1268 }
1269
1270 fn leaves(&self) -> Vec<Leaf<'_>> {
1271 self.entries
1272 .iter()
1273 .map(|entry| Leaf {
1274 node: entry.leaf(),
1275 name: entry.name.as_bytes(),
1276 })
1277 .collect()
1278 }
1279
1280 pub fn check(&self, folder: &Target) -> Result<()> {
1284 folder.require(Kind::Folder)?;
1285 if self.count == 0 {
1286 if !self.entries.is_empty() || !self.carried.is_empty() || self.start != 0 {
1287 return Err(invalid("a branch of an empty folder shows something"));
1288 }
1289 return confirm(folder, 0, EMPTY_LIST);
1290 }
1291 let shown = check_branch(
1292 ListKind::Folder,
1293 self.count,
1294 self.start,
1295 &self.leaves(),
1296 &self.carried,
1297 )?;
1298 confirm(folder, self.count, shown.top)
1299 }
1300
1301 pub fn check_name(&self, folder: &Target, name: &str) -> Result<Option<&Entry>> {
1306 check_name(name)?;
1307 folder.require(Kind::Folder)?;
1308 if self.count == 0 {
1309 self.check(folder)?;
1310 return Ok(None);
1311 }
1312 let [entry] = self.entries.as_slice() else {
1313 return Err(invalid("a name is answered by one entry, and no more"));
1314 };
1315 let leaf = Leaf {
1316 node: entry.leaf(),
1317 name: entry.name.as_bytes(),
1318 };
1319 let (shown, present) =
1320 check_lookup(self.count, self.start, leaf, name.as_bytes(), &self.carried)?;
1321 confirm(folder, self.count, shown.top)?;
1322 Ok(present.then_some(entry))
1323 }
1324}
1325
1326#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1329pub struct Totals {
1330 pub chunks: u64,
1332 pub chunk_bytes: u64,
1334 pub list_bytes: u64,
1336}
1337
1338#[derive(Clone, Debug, Eq, PartialEq)]
1341pub struct Record {
1342 top: Target,
1343 totals: Totals,
1344 extra: ExtraData,
1345 chunking: Chunking,
1346}
1347
1348impl Record {
1349 pub fn new(
1353 top: Target,
1354 totals: Totals,
1355 chunking: Chunking,
1356 mut extra: ExtraData,
1357 ) -> Result<Self> {
1358 extra.remove(CHUNKING_KEY);
1359 extra.insert(CHUNKING_KEY, chunking.tag())?;
1360 check_totals(&top, &totals)?;
1361 Ok(Self {
1362 top,
1363 totals,
1364 extra,
1365 chunking,
1366 })
1367 }
1368
1369 pub fn decode(bytes: &[u8]) -> Result<Self> {
1370 let mut reader = Reader::new(bytes, "a record");
1371 if reader.u8()? != RECORD_MARK {
1372 return Err(invalid("a record does not start with its mark"));
1373 }
1374 let kind = Kind::from_byte(reader.u8()?)?;
1375 let size = reader.u64()?;
1376 let hash = reader.hash()?;
1377 let totals = Totals {
1378 chunks: reader.u64()?,
1379 chunk_bytes: reader.u64()?,
1380 list_bytes: reader.u64()?,
1381 };
1382 let extra = ExtraData::decode(&mut reader)?;
1383 reader.finish()?;
1384 let chunking = Chunking::from_tag(
1385 extra
1386 .get(CHUNKING_KEY)
1387 .ok_or_else(|| invalid("a record does not say how the tree was chunked"))?,
1388 )?;
1389 let top = Target { kind, hash, size };
1390 check_totals(&top, &totals)?;
1391 Ok(Self {
1392 top,
1393 totals,
1394 extra,
1395 chunking,
1396 })
1397 }
1398
1399 pub fn encode(&self) -> Vec<u8> {
1400 let mut out = Vec::with_capacity(66 + self.extra.encoded_len());
1401 out.push(RECORD_MARK);
1402 out.push(self.top.kind.byte());
1403 out.extend_from_slice(&self.top.size.to_be_bytes());
1404 out.extend_from_slice(self.top.hash.as_bytes());
1405 out.extend_from_slice(&self.totals.chunks.to_be_bytes());
1406 out.extend_from_slice(&self.totals.chunk_bytes.to_be_bytes());
1407 out.extend_from_slice(&self.totals.list_bytes.to_be_bytes());
1408 self.extra.encode_into(&mut out);
1409 out
1410 }
1411
1412 pub fn root(&self) -> Root {
1414 Root::of_record(&self.encode())
1415 }
1416
1417 pub fn top(&self) -> Target {
1419 self.top
1420 }
1421
1422 pub fn totals(&self) -> Totals {
1423 self.totals
1424 }
1425
1426 pub fn extra(&self) -> &ExtraData {
1427 &self.extra
1428 }
1429
1430 pub fn chunking(&self) -> Chunking {
1432 self.chunking
1433 }
1434}
1435
1436fn check_totals(top: &Target, totals: &Totals) -> Result<()> {
1439 let fits = totals.chunks <= totals.chunk_bytes
1440 && totals.chunk_bytes <= top.size
1441 && totals
1442 .chunks
1443 .checked_mul(MAX_CHUNK_BYTES as u64)
1444 .is_none_or(|most| totals.chunk_bytes <= most)
1445 && totals
1446 .chunks
1447 .checked_mul(LIST_ITEM_BYTES as u64)
1448 .is_some_and(|least| totals.list_bytes >= least)
1449 && (top.kind == Kind::Folder || totals.list_bytes % LIST_ITEM_BYTES as u64 == 0);
1450 if fits {
1451 Ok(())
1452 } else {
1453 Err(invalid("a record's totals cannot belong to any tree"))
1454 }
1455}
1456
1457#[cfg(test)]
1458mod tests {
1459 use super::*;
1460
1461 fn chunk(seed: u8, length: u32) -> ChunkRef {
1462 ChunkRef {
1463 hash: Hash::of(&[seed]),
1464 length,
1465 }
1466 }
1467
1468 fn file(seed: u8) -> Target {
1469 FileList::new(vec![chunk(seed, u32::from(seed) + 1)])
1470 .unwrap()
1471 .target()
1472 }
1473
1474 fn entry(name: &str, target: Target) -> Entry {
1475 Entry::new(name, target, ExtraData::new()).unwrap()
1476 }
1477
1478 fn folder(names: &[&str]) -> FolderList {
1479 FolderList::new(
1480 names
1481 .iter()
1482 .enumerate()
1483 .map(|(index, name)| entry(name, file(index as u8)))
1484 .collect(),
1485 )
1486 .unwrap()
1487 }
1488
1489 fn sha(parts: &[&[u8]]) -> Hash {
1490 Hash::of(&parts.concat())
1491 }
1492
1493 fn u64be(value: u64) -> [u8; 8] {
1494 value.to_be_bytes()
1495 }
1496
1497 fn entry_bytes(kind: u8, size: u64, hash: &Hash, name: &[u8], extra: &[u8]) -> Vec<u8> {
1499 let mut bytes = vec![kind];
1500 bytes.extend_from_slice(&size.to_be_bytes());
1501 bytes.extend_from_slice(hash.as_bytes());
1502 bytes.extend_from_slice(&(name.len() as u16).to_be_bytes());
1503 bytes.extend_from_slice(name);
1504 bytes.extend_from_slice(extra);
1505 bytes
1506 }
1507
1508 const NO_EXTRA: [u8; 2] = [0, 0];
1509
1510 #[test]
1511 fn every_hash_covers_exactly_the_bytes_the_format_names() {
1512 let first = chunk(1, 5);
1514 let second = chunk(2, 7);
1515 let mut item = first.hash.as_bytes().to_vec();
1516 item.extend_from_slice(&5_u32.to_be_bytes());
1517 let one = FileList::new(vec![first]).unwrap();
1518 assert_eq!(one.encode(), item);
1519 let first_leaf = sha(&[&[0x00], &item]);
1520 assert_eq!(
1521 first.leaf(),
1522 Node {
1523 hash: first_leaf,
1524 size: 5
1525 }
1526 );
1527
1528 assert_eq!(
1530 *one.hash(),
1531 sha(&[&[0x10], &u64be(1), &u64be(5), first_leaf.as_bytes()])
1532 );
1533
1534 let second_leaf = second.leaf().hash;
1536 let top = sha(&[
1537 &[0x01],
1538 first_leaf.as_bytes(),
1539 &u64be(5),
1540 &u64be(1),
1541 second_leaf.as_bytes(),
1542 &u64be(7),
1543 &u64be(1),
1544 ]);
1545 let two = FileList::new(vec![first, second]).unwrap();
1546 assert_eq!(two.size(), 12);
1547 assert_eq!(
1548 *two.hash(),
1549 sha(&[&[0x10], &u64be(2), &u64be(12), top.as_bytes()])
1550 );
1551
1552 let extra = ExtraData::new()
1554 .with("mode", "644")
1555 .unwrap()
1556 .with("a", [0xff_u8])
1557 .unwrap();
1558 let named = Entry::new("b.txt", two.target(), extra).unwrap();
1559 let mut extra_bytes = vec![0, 2];
1560 extra_bytes.extend_from_slice(&[0, 1, b'a', 0, 1, 0xff]);
1561 extra_bytes.extend_from_slice(&[0, 4, b'm', b'o', b'd', b'e', 0, 3, b'6', b'4', b'4']);
1562 let named_bytes = entry_bytes(1, 12, two.hash(), b"b.txt", &extra_bytes);
1563 let mut encoded = Vec::new();
1564 named.encode_into(&mut encoded);
1565 assert_eq!(encoded, named_bytes);
1566 assert_eq!(named.encoded_len(), named_bytes.len());
1567 let named_leaf = sha(&[&[0x02], &named_bytes]);
1568 assert_eq!(
1569 named.leaf(),
1570 Node {
1571 hash: named_leaf,
1572 size: 12
1573 }
1574 );
1575
1576 let empty = FolderList::new(Vec::new()).unwrap();
1578 assert_eq!(
1579 *empty.hash(),
1580 sha(&[&[0x11], &u64be(0), &u64be(0), &[0; 32]])
1581 );
1582 let inner = entry("a", empty.target());
1583 let inner_bytes = entry_bytes(2, 0, empty.hash(), b"a", &NO_EXTRA);
1584 let inner_leaf = sha(&[&[0x02], &inner_bytes]);
1585 let both = FolderList::new(vec![inner, named]).unwrap();
1586 assert_eq!(
1587 both.encode(),
1588 [inner_bytes.clone(), named_bytes.clone()].concat()
1589 );
1590 assert_eq!(
1591 both.encoded_len(),
1592 (inner_bytes.len() + named_bytes.len()) as u64
1593 );
1594 let folder_top = sha(&[
1595 &[0x03],
1596 inner_leaf.as_bytes(),
1597 &u64be(0),
1598 &u64be(1),
1599 named_leaf.as_bytes(),
1600 &u64be(12),
1601 &u64be(1),
1602 b"b.txt",
1603 ]);
1604 assert_eq!(
1605 *both.hash(),
1606 sha(&[&[0x11], &u64be(2), &u64be(12), folder_top.as_bytes()])
1607 );
1608
1609 let totals = Totals {
1611 chunks: 2,
1612 chunk_bytes: 12,
1613 list_bytes: 72 + both.encoded_len(),
1614 };
1615 let record = Record::new(
1616 both.target(),
1617 totals,
1618 Chunking::fixed(5).unwrap(),
1619 ExtraData::new(),
1620 )
1621 .unwrap();
1622 let mut record_bytes = vec![0x20, 2];
1623 record_bytes.extend_from_slice(&u64be(12));
1624 record_bytes.extend_from_slice(both.hash().as_bytes());
1625 record_bytes.extend_from_slice(&u64be(2));
1626 record_bytes.extend_from_slice(&u64be(12));
1627 record_bytes.extend_from_slice(&u64be(totals.list_bytes));
1628 record_bytes.extend_from_slice(&[0, 1, 0, 8]);
1629 record_bytes.extend_from_slice(b"chunking");
1630 record_bytes.extend_from_slice(&[0, 7]);
1631 record_bytes.extend_from_slice(b"fixed-5");
1632 assert_eq!(record.encode(), record_bytes);
1633 assert_eq!(*record.root().as_hash(), Hash::of(&record_bytes));
1634 assert_eq!(Record::decode(&record_bytes).unwrap(), record);
1635 }
1636
1637 #[test]
1638 fn the_same_thing_has_the_same_hash_wherever_it_is() {
1639 let list = FileList::new(vec![chunk(1, 5), chunk(2, 7), chunk(1, 5)]).unwrap();
1641 let here = FolderList::new(vec![entry("a.bin", list.target())]).unwrap();
1642 let there = FolderList::new(vec![
1643 entry("other", file(9)),
1644 entry("renamed.bin", list.target()),
1645 ])
1646 .unwrap();
1647 assert_eq!(here.entries()[0].hash(), there.entries()[1].hash());
1648 assert_ne!(here.hash(), there.hash());
1649
1650 let outer = FolderList::new(vec![
1652 entry("one", here.target()),
1653 entry("two", here.target()),
1654 ])
1655 .unwrap();
1656 assert_eq!(outer.entries()[0].hash(), outer.entries()[1].hash());
1657 assert_eq!(outer.size(), 2 * here.size());
1658
1659 let empty_file = FileList::new(Vec::new()).unwrap();
1661 assert_eq!(*empty_file.hash(), file_hash(0, 0, &Hash::ZERO));
1662 assert_eq!(empty_file, FileList::decode(&[]).unwrap());
1663 let empty_folder = FolderList::decode(&[]).unwrap();
1664 assert_eq!(*empty_folder.hash(), folder_hash(0, 0, &Hash::ZERO));
1665 assert_ne!(empty_file.hash(), empty_folder.hash());
1666
1667 let other_order = FileList::new(vec![chunk(2, 7), chunk(1, 5), chunk(1, 5)]).unwrap();
1669 let one_less = FileList::new(vec![chunk(1, 5), chunk(2, 7)]).unwrap();
1670 let other_length = FileList::new(vec![chunk(1, 5), chunk(2, 6), chunk(1, 6)]).unwrap();
1671 assert_eq!(other_length.size(), list.size());
1672 for other in [&other_order, &one_less, &other_length] {
1673 assert_ne!(other.hash(), list.hash());
1674 }
1675 }
1676
1677 #[test]
1678 fn an_entry_differs_with_its_name_kind_size_hash_and_extra_data() {
1679 let target = file(1);
1680 let base = FolderList::new(vec![entry("a", target)]).unwrap();
1681 let renamed = FolderList::new(vec![entry("b", target)]).unwrap();
1682 let as_folder = FolderList::new(vec![entry(
1683 "a",
1684 Target {
1685 kind: Kind::Folder,
1686 ..target
1687 },
1688 )])
1689 .unwrap();
1690 let resized = FolderList::new(vec![entry(
1691 "a",
1692 Target {
1693 size: target.size + 1,
1694 ..target
1695 },
1696 )])
1697 .unwrap();
1698 let other_file = FolderList::new(vec![entry("a", file(2))]).unwrap();
1699 let with_extra = FolderList::new(vec![Entry::new(
1700 "a",
1701 target,
1702 ExtraData::new().with("mode", "755").unwrap(),
1703 )
1704 .unwrap()])
1705 .unwrap();
1706 for other in [&renamed, &as_folder, &resized, &other_file, &with_extra] {
1707 assert_ne!(other.hash(), base.hash());
1708 }
1709 }
1710
1711 #[test]
1712 fn names_are_held_to_the_rules() {
1713 let long = "x".repeat(255);
1714 for name in [
1715 "a",
1716 "A",
1717 ".a",
1718 "...",
1719 "a b",
1720 "a\\b",
1721 "\u{e9}t\u{e9}",
1722 long.as_str(),
1723 ] {
1724 assert!(check_name(name).is_ok(), "{name:?}");
1725 }
1726 let too_long = "x".repeat(256);
1727 for name in ["", ".", "..", "a/b", "/", "a\0b", too_long.as_str()] {
1728 assert!(check_name(name).is_err(), "{name:?}");
1729 assert!(
1730 Entry::new(name, file(1), ExtraData::new()).is_err(),
1731 "{name:?}"
1732 );
1733 }
1734 assert!(FolderList::new(vec![entry("File", file(1)), entry("file", file(2))]).is_ok());
1736 }
1737
1738 #[test]
1739 fn a_folder_list_is_sorted_by_its_names_bytes_with_no_name_twice() {
1740 assert!(FolderList::new(vec![entry("b", file(1)), entry("a", file(2))]).is_err());
1741 assert!(FolderList::new(vec![entry("a", file(1)), entry("a", file(1))]).is_err());
1742 let list = folder(&["Z", "a", "a0", "b"]);
1744 assert_eq!(list.get("a0").unwrap().name(), "a0");
1745 assert!(list.get("a1").is_none());
1746 let unsorted = [list.encode(), folder(&["B"]).encode()].concat();
1747 assert!(FolderList::decode(&unsorted).is_err());
1748 let twice = [folder(&["a"]).encode(), folder(&["a"]).encode()].concat();
1749 assert!(FolderList::decode(&twice).is_err());
1750 }
1751
1752 #[test]
1753 fn extra_data_is_held_to_its_limits_and_read_in_one_way_only() {
1754 let mut extra = ExtraData::new();
1755 assert!(extra.insert("", "x").is_err());
1756 assert!(extra.insert("n".repeat(65), "x").is_err());
1757 assert!(extra.insert("n".repeat(64), vec![0_u8; 1024]).is_ok());
1758 assert!(extra.insert("big", vec![0_u8; 1025]).is_err());
1759 for index in 0..31 {
1760 extra.insert(format!("k{index:02}"), "v").unwrap();
1761 }
1762 assert_eq!(extra.len(), 32);
1763 assert!(extra.insert("one-more", "v").is_err());
1764 assert!(
1765 extra.insert("k00", "again").is_ok(),
1766 "a name that is there is set again"
1767 );
1768 assert_eq!(extra.text("k00"), Some("again"));
1769
1770 let read = |bytes: &[u8]| {
1771 let mut reader = Reader::new(bytes, "extra data");
1772 ExtraData::decode(&mut reader).and_then(|extra| reader.finish().map(|()| extra))
1773 };
1774 let mut written = Vec::new();
1775 extra.encode_into(&mut written);
1776 assert_eq!(written.len(), extra.encoded_len());
1777 assert_eq!(read(&written).unwrap(), extra);
1778
1779 assert!(read(&[0, 0]).unwrap().is_empty());
1780 let good = [0, 2, 0, 1, b'a', 0, 1, 1, 0, 1, b'b', 0, 0];
1781 assert_eq!(read(&good).unwrap().len(), 2);
1782 let out_of_order = [0, 2, 0, 1, b'b', 0, 0, 0, 1, b'a', 0, 0];
1783 let name_twice = [0, 2, 0, 1, b'a', 0, 0, 0, 1, b'a', 0, 0];
1784 let empty_name = [0, 1, 0, 0, 0, 0];
1785 let not_utf8 = [0, 1, 0, 1, 0xff, 0, 0];
1786 let cut_short = [0, 1, 0, 1, b'a', 0, 5, 1];
1787 let count_too_high = [0, 2, 0, 1, b'a', 0, 0];
1788 let trailing = [0, 0, 0];
1789 for bad in [
1790 &out_of_order[..],
1791 &name_twice,
1792 &empty_name,
1793 ¬_utf8,
1794 &cut_short,
1795 &count_too_high,
1796 &trailing,
1797 &[0, 33],
1798 &[],
1799 ] {
1800 assert!(read(bad).is_err(), "{bad:?}");
1801 }
1802 let mut long_name = vec![0, 1, 0, 65];
1803 long_name.extend_from_slice(&[b'n'; 65]);
1804 long_name.extend_from_slice(&[0, 0]);
1805 assert!(read(&long_name).is_err());
1806 let mut long_value = vec![0, 1, 0, 1, b'a', 0x04, 0x01];
1807 long_value.extend_from_slice(&[0; 1025]);
1808 assert!(read(&long_value).is_err());
1809 }
1810
1811 #[test]
1812 fn lists_are_read_strictly() {
1813 let hash = Hash::of(b"x");
1814 let item = |length: u32| [hash.as_bytes().as_slice(), &length.to_be_bytes()].concat();
1816 assert!(FileList::decode(&item(1)).is_ok());
1817 assert!(FileList::decode(&item(MAX_CHUNK_BYTES as u32)).is_ok());
1818 assert!(FileList::decode(&item(0)).is_err());
1819 assert!(FileList::decode(&item(MAX_CHUNK_BYTES as u32 + 1)).is_err());
1820 assert!(FileList::decode(&item(1)[..35]).is_err());
1821 assert!(FileList::decode(&[item(1), vec![0]].concat()).is_err());
1822 assert!(ChunkRef::of(&[]).is_err());
1823 assert_eq!(ChunkRef::of(b"x").unwrap(), ChunkRef { hash, length: 1 });
1824
1825 assert!(FolderList::decode(&entry_bytes(1, 3, &hash, b"a", &NO_EXTRA)).is_ok());
1827 assert!(FolderList::decode(&entry_bytes(2, 3, &hash, b"a", &NO_EXTRA)).is_ok());
1828 for kind in [0, 3, 0xff] {
1829 assert!(FolderList::decode(&entry_bytes(kind, 3, &hash, b"a", &NO_EXTRA)).is_err());
1830 }
1831 for name in [
1832 &b""[..],
1833 b".",
1834 b"..",
1835 b"a/b",
1836 b"a\0",
1837 &[0xff, 0xfe],
1838 &[b'x'; 256],
1839 ] {
1840 let bytes = entry_bytes(1, 3, &hash, name, &NO_EXTRA);
1841 assert!(FolderList::decode(&bytes).is_err(), "{name:?}");
1842 }
1843 let whole = entry_bytes(1, 3, &hash, b"a", &NO_EXTRA);
1844 for cut in 1..whole.len() {
1845 assert!(FolderList::decode(&whole[..cut]).is_err(), "cut at {cut}");
1846 }
1847 assert!(FolderList::decode(&[whole.clone(), vec![0]].concat()).is_err());
1848 let huge = [
1850 entry_bytes(1, u64::MAX, &hash, b"a", &NO_EXTRA),
1851 entry_bytes(1, 1, &hash, b"b", &NO_EXTRA),
1852 ]
1853 .concat();
1854 assert!(matches!(
1855 FolderList::decode(&huge),
1856 Err(Error::SizeOverflow { .. })
1857 ));
1858 }
1859
1860 #[test]
1861 fn a_record_is_read_strictly() {
1862 let top = folder(&["a", "b"]).target();
1863 let totals = Totals {
1864 chunks: 2,
1865 chunk_bytes: 3,
1866 list_bytes: 200,
1867 };
1868 let extra = ExtraData::new()
1869 .with(CHUNKING_KEY, "a caller cannot set this")
1870 .unwrap()
1871 .with(TIMESTAMP_KEY, "2026-11-12T00:00:00Z")
1872 .unwrap();
1873 let record = Record::new(top, totals, Chunking::FastCdcV1, extra).unwrap();
1874 assert_eq!(record.extra().text(CHUNKING_KEY), Some("fastcdc-v1"));
1875 assert_eq!(record.chunking(), Chunking::FastCdcV1);
1876 assert_eq!(record.top(), top);
1877 assert_eq!(record.totals(), totals);
1878 let bytes = record.encode();
1879 assert_eq!(Record::decode(&bytes).unwrap(), record);
1880 assert_eq!(record.root(), Root::of_record(&bytes));
1881
1882 for cut in 0..bytes.len() {
1883 assert!(Record::decode(&bytes[..cut]).is_err(), "cut at {cut}");
1884 }
1885 assert!(Record::decode(&[bytes.clone(), vec![0]].concat()).is_err());
1886 let mut other_mark = bytes.clone();
1887 other_mark[0] = 0x21;
1888 assert!(Record::decode(&other_mark).is_err());
1889 let mut other_kind = bytes.clone();
1890 other_kind[1] = 3;
1891 assert!(Record::decode(&other_kind).is_err());
1892
1893 let mut untagged = bytes[..66].to_vec();
1895 untagged.extend_from_slice(&NO_EXTRA);
1896 assert!(Record::decode(&untagged).is_err());
1897 let mut unknown = bytes[..66].to_vec();
1898 unknown.extend_from_slice(&[0, 1, 0, 8]);
1899 unknown.extend_from_slice(b"chunking");
1900 unknown.extend_from_slice(&[0, 8]);
1901 unknown.extend_from_slice(b"fixed-2m");
1902 assert!(Record::decode(&unknown).is_err());
1903
1904 let bad_totals = [
1906 (3, 2, 200), (1, top.size + 1, 200), (2, 3, 71), (0, 1, 0), ];
1911 for (chunks, chunk_bytes, list_bytes) in bad_totals {
1912 let totals = Totals {
1913 chunks,
1914 chunk_bytes,
1915 list_bytes,
1916 };
1917 let made = Record::new(top, totals, Chunking::FastCdcV1, ExtraData::new());
1918 assert!(made.is_err(), "{totals:?}");
1919 }
1920 let file_top = FileList::new(vec![chunk(1, 5)]).unwrap().target();
1921 let uneven = Totals {
1922 chunks: 1,
1923 chunk_bytes: 5,
1924 list_bytes: 37,
1925 };
1926 assert!(Record::new(file_top, uneven, Chunking::FastCdcV1, ExtraData::new()).is_err());
1927 }
1928
1929 #[test]
1930 fn a_way_of_chunking_has_one_spelling_and_holds_chunks_to_its_lengths() {
1931 assert_eq!(Chunking::FastCdcV1.tag(), "fastcdc-v1");
1932 assert_eq!(Chunking::fixed(16).unwrap().tag(), "fixed-16");
1933 for chunking in [
1934 Chunking::FastCdcV1,
1935 Chunking::fixed(1).unwrap(),
1936 Chunking::fixed(16).unwrap(),
1937 Chunking::fixed(MAX_CHUNK_BYTES as u32).unwrap(),
1938 ] {
1939 assert_eq!(
1940 Chunking::from_tag(chunking.tag().as_bytes()).unwrap(),
1941 chunking
1942 );
1943 }
1944 for tag in [
1945 "",
1946 "fastcdc-v2",
1947 "FASTCDC-V1",
1948 "fastcdc-v1 ",
1949 "fixed-",
1950 "fixed-0",
1951 "fixed-016",
1952 "fixed-+16",
1953 "fixed-16 ",
1954 "fixed-2m",
1955 "fixed-8388609",
1956 "fixed-99999999",
1957 "fixed-4294967297",
1958 ] {
1959 assert!(Chunking::from_tag(tag.as_bytes()).is_err(), "{tag:?}");
1960 }
1961
1962 let content = Chunking::FastCdcV1;
1963 let min = FASTCDC_MIN_SIZE as u32;
1964 let max = FASTCDC_MAX_SIZE as u32;
1965 assert!(content.check_length(min + 1, false).is_ok());
1966 assert!(content.check_length(max, false).is_ok());
1967 assert!(
1968 content.check_length(min, false).is_err(),
1969 "the chunker never stops there"
1970 );
1971 assert!(content.check_length(1, false).is_err());
1972 assert!(content.check_length(1, true).is_ok());
1973 assert!(content.check_length(max, true).is_ok());
1974 assert!(content.check_length(max + 1, true).is_err());
1975 assert!(content.check_length(0, true).is_err());
1976
1977 let fixed = Chunking::fixed(16).unwrap();
1978 assert!(fixed.check_length(16, false).is_ok());
1979 assert!(fixed.check_length(15, false).is_err());
1980 assert!(fixed.check_length(17, false).is_err());
1981 assert!(fixed.check_length(1, true).is_ok());
1982 assert!(fixed.check_length(16, true).is_ok());
1983 assert!(fixed.check_length(17, true).is_err());
1984 assert!(fixed.check_length(0, true).is_err());
1985 }
1986
1987 #[test]
1988 fn a_files_size_bounds_how_many_chunks_it_can_have() {
1989 let step = FASTCDC_MIN_SIZE as u64 + 1;
1990 let max = FASTCDC_MAX_SIZE as u64;
1991 let content = Chunking::FastCdcV1;
1992 assert_eq!(content.count_bounds(0), (0, 0));
1993 assert_eq!(content.count_bounds(1), (1, 1));
1994 assert_eq!(content.count_bounds(step), (1, 1));
1995 assert_eq!(content.count_bounds(step + 1), (1, 2));
1996 assert_eq!(content.count_bounds(max), (1, 16));
1997 assert_eq!(content.count_bounds(max + 1), (2, 16));
1998 assert_eq!(content.count_bounds(2 * step + 1), (1, 3));
1999 let (fewest, most) = content.count_bounds(1 << 40);
2002 assert_eq!(fewest, 131_072);
2003 assert_eq!(most, 2_097_149);
2004 assert_eq!(2_097_148 * step + 4, 1 << 40);
2005 assert!(content.check_count(1 << 40, 500_000).is_ok());
2006 assert!(content.check_count(1 << 40, most + 1).is_err());
2007 assert!(content.check_count(1 << 40, fewest - 1).is_err());
2008 assert!(content.check_count(0, 1).is_err());
2009
2010 let fixed = Chunking::fixed(4).unwrap();
2012 for size in 0..40_u64 {
2013 let chunks = fixed.cut(&vec![0_u8; size as usize]).len() as u64;
2014 assert_eq!(fixed.count_bounds(size), (chunks, chunks), "size {size}");
2015 }
2016 let list = FileList::new(vec![chunk(1, 4), chunk(2, 4), chunk(3, 3)]).unwrap();
2017 assert!(list.check_chunking(fixed).is_ok());
2018 assert!(list.check_chunking(Chunking::fixed(5).unwrap()).is_err());
2019 assert!(list.check_chunking(content).is_err());
2020 let short_in_the_middle =
2021 FileList::new(vec![chunk(1, 4), chunk(2, 3), chunk(3, 4)]).unwrap();
2022 assert!(short_in_the_middle.check_chunking(fixed).is_err());
2023 assert!(FileList::new(Vec::new())
2024 .unwrap()
2025 .check_chunking(content)
2026 .is_ok());
2027 }
2028
2029 #[test]
2030 fn every_branch_of_a_file_checks_and_gives_the_byte_it_starts_at() {
2031 for count in 1..=17_u8 {
2032 let items: Vec<ChunkRef> = (0..count)
2033 .map(|index| chunk(index, u32::from(index % 5) + 1))
2034 .collect();
2035 let list = FileList::new(items.clone()).unwrap();
2036 let open = OpenFile::new(list.clone()).unwrap();
2037 let target = list.target();
2038 for start in 0..u64::from(count) {
2039 for end in start + 1..=u64::from(count) {
2040 let branch = open.open(start, end).unwrap();
2041 assert_eq!(branch, list.open(start, end).unwrap());
2042 assert_eq!(FileBranch::decode(&branch.encode()).unwrap(), branch);
2043 let before: u64 = items[..start as usize]
2044 .iter()
2045 .map(|item| u64::from(item.length))
2046 .sum();
2047 assert_eq!(branch.check(&target, None).unwrap(), before);
2048 assert_eq!(open.start_of(start), Some(before));
2049 assert_eq!(branch.items(), &items[start as usize..end as usize]);
2050 }
2051 }
2052 assert_eq!(open.start_of(u64::from(count)), Some(list.size()));
2053 assert_eq!(open.start_of(u64::from(count) + 1), None);
2054 }
2055 }
2056
2057 #[test]
2058 fn a_branch_of_a_file_is_refused_for_any_other_file_count_or_place() {
2059 let items: Vec<ChunkRef> = (0..9).map(|index| chunk(index, 4)).collect();
2060 let list = FileList::new(items).unwrap();
2061 let target = list.target();
2062 let branch = list.open(3, 5).unwrap();
2063 assert_eq!(branch.check(&target, None).unwrap(), 12);
2064
2065 assert!(matches!(
2067 branch.check(&file(1), None),
2068 Err(Error::SizeMismatch { .. })
2069 ));
2070 let other_hash = Target {
2071 hash: Hash::of(b"other"),
2072 ..target
2073 };
2074 assert!(matches!(
2075 branch.check(&other_hash, None),
2076 Err(Error::HashMismatch { .. })
2077 ));
2078 let other_size = Target {
2079 size: target.size + 1,
2080 ..target
2081 };
2082 assert!(matches!(
2083 branch.check(&other_size, None),
2084 Err(Error::SizeMismatch { .. })
2085 ));
2086 let as_folder = Target {
2087 kind: Kind::Folder,
2088 ..target
2089 };
2090 assert!(branch.check(&as_folder, None).is_err());
2091
2092 let bytes = branch.encode();
2094 let with = |at: usize, value: u8| {
2095 let mut changed = bytes.clone();
2096 changed[at] = value;
2097 FileBranch::decode(&changed).and_then(|branch| branch.check(&target, None))
2098 };
2099 assert!(with(7, 10).is_err(), "as a file of 10 chunks");
2100 assert!(with(7, 8).is_err(), "as a file of 8 chunks");
2101 assert!(with(15, 4).is_err(), "one place on");
2102 assert!(with(15, 2).is_err(), "one place back");
2103 assert!(with(19, 1).is_err(), "one item less");
2104 assert!(with(19, 0).is_err(), "no items");
2105 assert!(with(20, 0).is_err(), "another chunk");
2106 let last = bytes.len() - 1;
2107 assert!(
2108 with(last, bytes[last] ^ 1).is_err(),
2109 "another size for a carried node"
2110 );
2111 for cut in 0..bytes.len() {
2112 assert!(FileBranch::decode(&bytes[..cut]).is_err(), "cut at {cut}");
2113 }
2114 assert!(FileBranch::decode(&[bytes.clone(), vec![0]].concat()).is_err());
2115
2116 assert!(branch
2118 .check(&target, Some(Chunking::fixed(4).unwrap()))
2119 .is_ok());
2120 assert!(branch
2121 .check(&target, Some(Chunking::fixed(5).unwrap()))
2122 .is_err());
2123 assert!(branch.check(&target, Some(Chunking::FastCdcV1)).is_err());
2124
2125 let mut crowded = bytes[..20 + 2 * LIST_ITEM_BYTES].to_vec();
2127 crowded.extend_from_slice(&81_u16.to_be_bytes());
2128 crowded.extend_from_slice(&[0; 81 * 40]);
2129 assert!(FileBranch::decode(&crowded).is_err());
2130 let mut hollow = bytes[..16].to_vec();
2132 hollow.extend_from_slice(&u32::MAX.to_be_bytes());
2133 assert!(FileBranch::decode(&hollow).is_err());
2134 }
2135
2136 #[test]
2137 fn the_chunks_that_hold_a_stretch_of_bytes_are_found() {
2138 let lengths = [3_u32, 1, 4, 1, 5, 9, 2, 6];
2139 let items: Vec<ChunkRef> = lengths
2140 .iter()
2141 .enumerate()
2142 .map(|(index, length)| chunk(index as u8, *length))
2143 .collect();
2144 let list = FileList::new(items).unwrap();
2145 let open = OpenFile::new(list.clone()).unwrap();
2146 let size = list.size();
2147 assert_eq!(size, 31);
2148 let mut holder = Vec::new();
2150 for (index, length) in lengths.iter().enumerate() {
2151 holder.extend(std::iter::repeat_n(index as u64, *length as usize));
2152 }
2153 for offset in 0..size {
2154 for length in 1..=size - offset {
2155 let (first, after) = open.chunks_for(offset, length).unwrap();
2156 assert_eq!(first, holder[offset as usize], "{offset}+{length}");
2157 assert_eq!(
2158 after,
2159 holder[(offset + length - 1) as usize] + 1,
2160 "{offset}+{length}"
2161 );
2162 let branch = open.open_bytes(offset, length).unwrap();
2163 let starts_at = branch.check(&list.target(), None).unwrap();
2164 assert!(starts_at <= offset);
2165 let shown: u64 = branch
2166 .items()
2167 .iter()
2168 .map(|item| u64::from(item.length))
2169 .sum();
2170 assert!(starts_at + shown >= offset + length);
2171 }
2172 }
2173 assert!(open.chunks_for(0, 0).is_err());
2174 assert!(open.chunks_for(size, 1).is_err());
2175 assert!(open.chunks_for(size - 1, 2).is_err());
2176 assert!(open.chunks_for(u64::MAX, 2).is_err());
2177 assert!(OpenFile::new(FileList::new(Vec::new()).unwrap())
2178 .unwrap()
2179 .chunks_for(0, 1)
2180 .is_err());
2181 }
2182
2183 #[test]
2184 fn every_branch_of_a_folder_checks_and_reads_back() {
2185 let names: Vec<String> = (0..13).map(|index| format!("n{index:02}")).collect();
2186 let names: Vec<&str> = names.iter().map(String::as_str).collect();
2187 for count in 1..=names.len() {
2188 let list = folder(&names[..count]);
2189 let open = OpenFolder::new(list.clone()).unwrap();
2190 let target = list.target();
2191 for start in 0..count as u64 {
2192 for end in start + 1..=count as u64 {
2193 let branch = open.open(start, end).unwrap();
2194 assert_eq!(branch, list.open(start, end).unwrap());
2195 assert_eq!(FolderBranch::decode(&branch.encode()).unwrap(), branch);
2196 branch.check(&target).unwrap();
2197 assert_eq!(
2198 branch.entries(),
2199 &list.entries()[start as usize..end as usize]
2200 );
2201 assert!(branch.check(&folder(&["other"]).target()).is_err());
2202 let as_file = Target {
2203 kind: Kind::File,
2204 ..target
2205 };
2206 assert!(branch.check(&as_file).is_err());
2207 }
2208 }
2209 }
2210 }
2211
2212 #[test]
2213 fn a_name_is_shown_to_be_there_or_not_there_by_its_one_place() {
2214 let names = ["b", "d", "f", "h", "j", "l", "n"];
2215 let asked = [
2216 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "b0", "B",
2217 ];
2218 for count in 1..=names.len() {
2219 let list = folder(&names[..count]);
2220 let target = list.target();
2221 for name in asked {
2222 let place = list.place_of(name).unwrap();
2223 let truth = list.get(name);
2224 let answer = list.open_name(name).unwrap();
2226 assert_eq!(FolderBranch::decode(&answer.encode()).unwrap(), answer);
2227 assert_eq!(answer.check_name(&target, name).unwrap(), truth);
2228 for other in 0..count as u64 {
2231 let shown = list.open(other, other + 1).unwrap();
2232 let verdict = shown.check_name(&target, name);
2233 if other == place {
2234 assert_eq!(verdict.unwrap(), truth, "{count}: {name} at {other}");
2235 } else {
2236 assert!(verdict.is_err(), "{count}: {name} at {other}");
2237 }
2238 }
2239 if count >= 2 {
2241 let two = list.open(0, 2).unwrap();
2242 assert!(two.check_name(&target, name).is_err());
2243 }
2244 }
2245 assert!(list.open_name("a/b").is_err());
2246 let any = list.open(0, 1).unwrap();
2247 assert!(any.check_name(&target, "").is_err());
2248 }
2249 }
2250
2251 #[test]
2252 fn an_empty_folder_shows_that_it_holds_no_name() {
2253 let empty = FolderList::new(Vec::new()).unwrap();
2254 assert_eq!(empty.place_of("a"), None);
2255 let answer = empty.open_name("a").unwrap();
2256 assert_eq!(FolderBranch::decode(&answer.encode()).unwrap(), answer);
2257 assert_eq!(answer.check_name(&empty.target(), "a").unwrap(), None);
2258 answer.check(&empty.target()).unwrap();
2259 let full = folder(&["a"]);
2261 assert!(answer.check_name(&full.target(), "a").is_err());
2262 assert!(answer.check(&full.target()).is_err());
2263 let mut nothing = 3_u64.to_be_bytes().to_vec();
2265 nothing.extend_from_slice(&[0; 8 + 4 + 2]);
2266 assert!(FolderBranch::decode(¬hing).is_err());
2267 let mut carrying = 0_u64.to_be_bytes().to_vec();
2268 carrying.extend_from_slice(&[0; 8 + 4]);
2269 carrying.extend_from_slice(&[0, 1]);
2270 carrying.extend_from_slice(&[0; 40]);
2271 carrying.extend_from_slice(&[0, 1, b'a']);
2272 assert!(FolderBranch::decode(&carrying).is_err());
2273 }
2274}