Skip to main content

scionic_merkletree/
format.rs

1//! The things a tree is made of, and their exact bytes.
2//!
3//! * A **chunk** is a range of a file's bytes. Its hash is the SHA-256 of those
4//!   bytes, and nothing else.
5//! * A **file** is the list of its chunks, in the file's order.
6//! * A **folder** is the list of its entries, sorted by name. An entry holds a
7//!   name, and the file or folder under it.
8//! * The **record** says what a tree's root stands for.
9//!
10//! A thing's hash covers what the thing is, and its parent's hash covers where
11//! it sits. So a file has no name of its own and a chunk has no number of its
12//! own: the name is in the folder, and the number is the chunk's place in the
13//! file's list.
14//!
15//! A value of one of these types is always well formed. It is checked when it
16//! is made and when it is read from bytes, and reading is strict: bytes that
17//! could be written in two ways are read in one way only.
18
19use 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
30/// The most bytes a chunk may hold: 8 MiB.
31pub const MAX_CHUNK_BYTES: usize = FASTCDC_MAX_SIZE;
32/// How many bytes one item of a file's list takes: a hash and a length.
33pub const LIST_ITEM_BYTES: usize = 36;
34/// The most bytes a name may hold.
35pub const MAX_NAME_BYTES: usize = 255;
36/// The most values a set of extra data may hold.
37pub const MAX_EXTRA_VALUES: usize = 32;
38/// The most bytes the name of an extra value may hold.
39pub const MAX_EXTRA_NAME_BYTES: usize = 64;
40/// The most bytes an extra value may hold.
41pub const MAX_EXTRA_VALUE_BYTES: usize = 1024;
42/// The most folders that may sit inside one another, the top one counted.
43pub const MAX_FOLDER_DEPTH: usize = 128;
44/// The most nodes a branch may carry: 40 on each side of what it shows.
45pub const MAX_CARRIED_NODES: usize = 80;
46/// The most bytes a set of extra data may take: how many values it has, and
47/// 32 values that are as long as they can be.
48pub const MAX_EXTRA_BYTES: usize =
49    2 + MAX_EXTRA_VALUES * (4 + MAX_EXTRA_NAME_BYTES + MAX_EXTRA_VALUE_BYTES);
50/// The most bytes a record may take: its fixed part, and extra data that is
51/// as full as it can be.
52pub const MAX_RECORD_BYTES: usize = 66 + MAX_EXTRA_BYTES;
53/// The most bytes a folder's entry may take: its fixed part, the longest
54/// name, and extra data that is as full as it can be.
55pub const MAX_ENTRY_BYTES: usize = 43 + MAX_NAME_BYTES + MAX_EXTRA_BYTES;
56/// The extra value of a record that says how the tree's files were chunked.
57pub const CHUNKING_KEY: &str = "chunking";
58/// The extra value of a record that says when the tree was built.
59pub const TIMESTAMP_KEY: &str = "timestamp";
60/// How a tree says that its files were chunked by content.
61pub 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
78/// Reads numbers and bytes off the front of a slice.
79pub(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    /// Everything must have been read.
133    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/// Whether an entry is a file or a folder.
143#[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/// A file or a folder as the thing above it names it: its kind, its hash, and
167/// how many bytes of file content it holds.
168#[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
188/// Checks a name: 1 to 255 bytes, no `/`, no zero byte, and not `.` or `..`.
189pub 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/// A small set of named values, kept beside a name in a folder or in a tree's
210/// record. It holds at most 32 values. A value's name is 1 to 64 bytes, and a
211/// value is at most 1,024 bytes.
212#[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    /// Sets a value, in place of any value of the same name.
223    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    /// The same set with one more value.
240    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    /// A value as text, when it is UTF-8.
250    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    /// The values, in the order of their names' bytes.
268    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/// One item of a file's list: a chunk's hash, and how many bytes it holds.
324#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
325pub struct ChunkRef {
326    pub hash: Hash,
327    pub length: u32,
328}
329
330impl ChunkRef {
331    /// The item for a chunk with these bytes. A chunk holds 1 byte to 8 MiB.
332    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    /// Whether `bytes` are the chunk this item names: of its length, and
349    /// with its hash.
350    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    /// The item's leaf in its file's tree.
369    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/// One entry of a folder: a name, the file or folder under it, and extra data.
382#[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    /// How many bytes of file content are under this entry.
409    pub fn size(&self) -> u64 {
410        self.target.size
411    }
412
413    pub fn hash(&self) -> &Hash {
414        &self.target.hash
415    }
416
417    /// The file or folder under this entry.
418    pub fn target(&self) -> Target {
419        self.target
420    }
421
422    pub fn extra(&self) -> &ExtraData {
423        &self.extra
424    }
425
426    /// How many bytes the entry takes in its folder's list.
427    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    /// The entry's leaf in its folder's tree.
457    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
477/// The hash of a file with `count` chunks and `size` bytes, whose list's tree
478/// has `list` on top.
479pub fn file_hash(count: u64, size: u64, list: &Hash) -> Hash {
480    owner_hash(FILE_MARK, count, size, list)
481}
482
483/// The hash of a folder with `count` entries and `size` bytes of file content,
484/// whose list's tree has `list` on top.
485pub fn folder_hash(count: u64, size: u64, list: &Hash) -> Hash {
486    owner_hash(FOLDER_MARK, count, size, list)
487}
488
489/// Holds a rebuilt top against the file or folder it should be the top of.
490fn 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/// How a tree's files are split into chunks.
509#[derive(Clone, Copy, Debug, Eq, PartialEq)]
510pub enum Chunking {
511    /// By content: chunks of more than 512 KiB, about 2 MiB on average, and
512    /// 8 MiB at most. Only a file's last chunk may be smaller.
513    FastCdcV1,
514    /// Every chunk but a file's last holds exactly this many bytes. For tests.
515    Fixed(NonZeroU32),
516}
517
518impl Chunking {
519    /// Chunking at a fixed size, of 1 byte to 8 MiB.
520    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    /// How a record says this: `fastcdc-v1`, or `fixed-` and the size.
528    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    /// Reads what a record says. A size is written in digits with no zero in
536    /// front, so each way of chunking has one spelling.
537    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    /// Whether a chunk of `length` bytes fits, as a file's last chunk or as
559    /// one before it.
560    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    /// The fewest and the most chunks that a file of `size` bytes can have.
585    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    /// Whether a file of `size` bytes can have `count` chunks.
602    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/// A file: the list of its chunks, in the file's order.
615#[derive(Clone, Debug, Eq, PartialEq)]
616pub struct FileList {
617    items: Vec<ChunkRef>,
618    size: u64,
619    hash: Hash,
620}
621
622impl FileList {
623    /// The file with these chunks, in this order. A chunk that occurs twice
624    /// is listed twice. No chunks at all is the empty file.
625    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    /// Reads the items of a whole list: 36 bytes for each chunk.
643    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    /// Reads a whole list: 36 bytes for each chunk.
656    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    /// How many chunks the file has.
673    pub fn count(&self) -> u64 {
674        self.items.len() as u64
675    }
676
677    /// How many bytes the file holds.
678    pub fn size(&self) -> u64 {
679        self.size
680    }
681
682    /// The file's hash. It covers the chunks, their order, how many there
683    /// are and the size, and nothing about where the file sits.
684    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    /// How many bytes the list takes.
697    pub fn encoded_len(&self) -> u64 {
698        self.items.len() as u64 * LIST_ITEM_BYTES as u64
699    }
700
701    /// Whether every chunk has a length that `chunking` gives.
702    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    /// Shows chunks `start` up to, not including, `end`. This hashes the
722    /// whole list each time: keep an [`OpenFile`] to show many parts.
723    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/// A file's list with its tree kept, for showing many parts of it, and for
740/// finding the chunks that hold a stretch of bytes.
741#[derive(Clone, Debug)]
742pub struct OpenFile {
743    list: Arc<FileList>,
744    tree: ListTree,
745    /// Where each chunk starts, and after the last one the file's size.
746    starts: Vec<u64>,
747}
748
749impl OpenFile {
750    pub fn new(list: FileList) -> Result<Self> {
751        Self::shared(Arc::new(list))
752    }
753
754    /// As [`OpenFile::new`], for a list that others hold too.
755    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    /// Reads a whole list as [`FileList::decode`] does, and keeps its tree.
761    /// The list is hashed once for both.
762    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    /// The list, to hold beside this.
797    pub fn shared_list(&self) -> Arc<FileList> {
798        Arc::clone(&self.list)
799    }
800
801    /// The byte at which chunk `index` starts. The count gives the size.
802    pub fn start_of(&self, index: u64) -> Option<u64> {
803        self.starts.get(usize::try_from(index).ok()?).copied()
804    }
805
806    /// The chunks that hold the `length` bytes from `offset`: the first one's
807    /// number, and the number after the last one. The stretch must lie
808    /// inside the file and hold at least one byte.
809    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        // Every chunk holds a byte, so the starts ascend and each is found.
815        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    /// Shows chunks `start` up to, not including, `end`.
821    pub fn open(&self, start: u64, end: u64) -> Result<FileBranch> {
822        self.list.open_with(&self.tree, start, end)
823    }
824
825    /// Shows the chunks that hold the `length` bytes from `offset`.
826    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/// A branch of a file's list, with the nodes that stand for the rest of it.
833#[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    /// How many chunks the whole file is said to have.
843    pub fn count(&self) -> u64 {
844        self.count
845    }
846
847    /// The number of the first chunk shown.
848    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    /// Checks the branch against the file it is said to be a part of, and gives
905    /// the byte of the file at which the branch starts. With a way of chunking,
906    /// the chunks' lengths are held to it too.
907    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
935/// What every branch starts with: how many items the whole list has, the place
936/// of the first one shown, and how many are shown.
937fn 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/// A folder: the list of its entries, sorted by name, with no name twice.
959#[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    /// The folder with these entries. They must be in the order of their
969    /// names' bytes, with no name twice. No entries is the empty folder.
970    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    /// Reads the entries of a whole list, one after another.
989    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    /// Reads a whole list: its entries, one after another.
999    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    /// How many entries the folder has.
1016    pub fn count(&self) -> u64 {
1017        self.entries.len() as u64
1018    }
1019
1020    /// How many bytes of file content are under the folder.
1021    pub fn size(&self) -> u64 {
1022        self.size
1023    }
1024
1025    /// The folder's hash. It covers every entry: its name, its kind, its
1026    /// size, its hash and its extra data. It does not cover a name for the
1027    /// folder itself.
1028    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    /// How many bytes the list takes.
1041    pub fn encoded_len(&self) -> u64 {
1042        self.encoded_len
1043    }
1044
1045    /// The entry with this name.
1046    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    /// The one place where `name` can be: that of the last entry whose name
1054    /// does not sort after it, or the first place. An empty folder has none.
1055    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    /// Shows entries `start` up to, not including, `end`. This hashes the
1076    /// whole list each time: keep an [`OpenFolder`] to show many parts.
1077    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    /// Shows the entry at the one place where `name` can be. It answers
1083    /// whether the folder has the name, whichever way the answer falls.
1084    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/// A folder's list with its tree kept, for showing many parts of it.
1114#[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    /// Reads a whole list as [`FolderList::decode`] does, and keeps its tree.
1127    /// The list is hashed once for both.
1128    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    /// Shows entries `start` up to, not including, `end`.
1155    pub fn open(&self, start: u64, end: u64) -> Result<FolderBranch> {
1156        self.list.open_with(&self.tree, start, end)
1157    }
1158
1159    /// Shows the entry at the one place where `name` can be.
1160    pub fn open_name(&self, name: &str) -> Result<FolderBranch> {
1161        self.list.open_name_with(&self.tree, name)
1162    }
1163}
1164
1165/// A branch of a folder's list, with the nodes that stand for the rest of it.
1166/// A branch of an empty folder shows nothing, and carries nothing.
1167#[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    /// The branch of an empty folder: it shows nothing, and carries nothing.
1177    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    /// How many entries the whole folder is said to have.
1187    pub fn count(&self) -> u64 {
1188        self.count
1189    }
1190
1191    /// The place of the first entry shown.
1192    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        // An entry takes 45 bytes at least, so a count is held to the bytes.
1225        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            // The first carried node of a branch that does not start the list
1240            // is the node that begins the list. No fork hashes a name for
1241            // it, so it comes with none. Every other one comes with a name.
1242            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    /// Checks the branch against the folder it is said to be a part of. Every
1281    /// entry shown is then an entry of that folder, at the place where a
1282    /// search for its name ends.
1283    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    /// Checks the branch as the answer to "what is under `name` in this
1302    /// folder". It gives the entry, or nothing when the folder has no entry
1303    /// of that name. Either answer is proven: the branch must show the one place
1304    /// where the name can be.
1305    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/// What a tree says about itself as a whole: how much a store has to keep
1327/// for it. Each counts a thing once, however often the tree uses it.
1328#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1329pub struct Totals {
1330    /// How many different chunks the tree has.
1331    pub chunks: u64,
1332    /// How many bytes those chunks hold.
1333    pub chunk_bytes: u64,
1334    /// How many bytes the lists of its different files and folders take.
1335    pub list_bytes: u64,
1336}
1337
1338/// A tree's record: the file or folder on top, the tree's totals, and its
1339/// extra data. The hash of the record is the tree's root.
1340#[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    /// The record of a tree with `top` on top. How the tree was chunked is
1350    /// written into the extra data, in place of anything the caller put under
1351    /// that name.
1352    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    /// The tree's root: the hash of the record.
1413    pub fn root(&self) -> Root {
1414        Root::of_record(&self.encode())
1415    }
1416
1417    /// The file or folder on top of the tree.
1418    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    /// How the tree's files were chunked.
1431    pub fn chunking(&self) -> Chunking {
1432        self.chunking
1433    }
1434}
1435
1436/// What must hold between a record's numbers in any tree. Whether the totals
1437/// are right is checked against the whole tree.
1438fn 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    /// An entry's bytes, written by hand.
1498    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        // A file's list item, and its leaf.
1513        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        // A file of one chunk: the leaf is the top of its list.
1529        assert_eq!(
1530            *one.hash(),
1531            sha(&[&[0x10], &u64be(1), &u64be(5), first_leaf.as_bytes()])
1532        );
1533
1534        // A file of two chunks: the top is a fork over the two leaves.
1535        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        // An entry with extra data, and its leaf.
1553        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        // A folder of an empty folder and that file.
1577        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        // The record, and the root.
1610        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        // A file's hash covers its chunks, and nothing about where it sits.
1640        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        // A folder's hash covers its entries, and no name for itself.
1651        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        // Every empty file is one file, and it is not the empty folder.
1660        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        // The chunks' order, their number and their lengths are all covered.
1668        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        // Names are compared as bytes: these are two names.
1735        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        // Bytes, not letters: "Z" sorts before "a", and "a" before "a0".
1743        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            &not_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        // A file's list: whole items, and chunks of 1 byte to 8 MiB.
1815        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        // A folder's list: every entry whole, of a known kind, validly named.
1826        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        // A list's sizes are added up, and a sum that does not fit is refused.
1849        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        // A record that does not say how its tree was chunked is no record.
1894        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        // Totals that no tree can have.
1905        let bad_totals = [
1906            (3, 2, 200),            // more chunks than chunk bytes
1907            (1, top.size + 1, 200), // more chunk bytes than the tree holds
1908            (2, 3, 71),             // lists too short to name the chunks
1909            (0, 1, 0),              // bytes without chunks
1910        ];
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        // A terabyte: at most about two million chunks, never a billion. The
2000        // most is 2,097,148 chunks of 524,289 bytes, and a last one of 4.
2001        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        // What the bounds say is what lists of fitting chunks can add up to.
2011        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        // Another file, another size, and a folder.
2066        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        // The same bytes with another count, another place, or one item less.
2093        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        // The chunks' lengths are held to the way of chunking, when one is given.
2117        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        // A branch that claims more carried nodes than any list needs.
2126        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        // A branch that claims more items than it has bytes for.
2131        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        // Which chunk holds each byte, worked out the long way.
2149        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                // The answer the folder gives.
2225                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                // Any other entry shown in its place is refused, so there is
2229                // one answer, and it is the true one.
2230                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                // A branch of two entries is no answer for one name.
2240                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        // The same answer for a folder that is not empty is refused.
2260        let full = folder(&["a"]);
2261        assert!(answer.check_name(&full.target(), "a").is_err());
2262        assert!(answer.check(&full.target()).is_err());
2263        // And a branch that shows nothing of a folder with entries is no branch.
2264        let mut nothing = 3_u64.to_be_bytes().to_vec();
2265        nothing.extend_from_slice(&[0; 8 + 4 + 2]);
2266        assert!(FolderBranch::decode(&nothing).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}