Skip to main content

scionic_merkletree/
build.rs

1//! Building a tree: from a folder or a file on disk, or part by part.
2
3use crate::disk::{Found, Held, Refused};
4use crate::fastcdc::{chunks_of, FASTCDC_MAX_SIZE};
5use crate::format::{
6    check_name, ChunkRef, Chunking, Entry, ExtraData, FileList, FolderList, Kind, Record, Target,
7    MAX_FOLDER_DEPTH, TIMESTAMP_KEY,
8};
9use crate::hash::Root;
10use crate::intake::Intake;
11use crate::store::{Store, Stored};
12use crate::threads::{cores, with_helpers};
13use crate::{io_error, Error, Result};
14use std::collections::VecDeque;
15use std::fs::{self, File};
16use std::io::{self, ErrorKind, Read};
17use std::path::{Path, PathBuf};
18use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
19use std::sync::{Arc, Condvar, Mutex, MutexGuard};
20use std::time::{SystemTime, UNIX_EPOCH};
21
22/// Reads once, and again when the read was only interrupted.
23pub(crate) fn read_some(reader: &mut dyn Read, buffer: &mut [u8]) -> io::Result<usize> {
24    loop {
25        match reader.read(buffer) {
26            Err(error) if error.kind() == ErrorKind::Interrupted => {}
27            other => return other,
28        }
29    }
30}
31
32/// How much of a file a builder holds at a time when it works alone: two
33/// chunks of the longest kind, one in each of its two windows.
34const ROOM_ALONE: usize = 2 * FASTCDC_MAX_SIZE;
35
36/// How much of a file a builder holds at a time when other threads help it,
37/// in its two windows: enough chunks to give each of them some.
38const ROOM_WITH_HELP: usize = 8 * FASTCDC_MAX_SIZE;
39
40/// The least of a file that is worth a thread of its own, when several
41/// threads look through it for where its chunks may end.
42const LOOKED_THROUGH_BY_EACH: usize = 4 << 20;
43
44/// The least bytes of chunks that are worth a helper of their own, while
45/// the thread that reads a file reads on.
46const KEPT_BY_EACH: usize = 1 << 20;
47
48/// The most chunks of a fixed size that a window holds.
49const FIXED_CHUNKS_IN_A_WINDOW: usize = 1024;
50
51/// How many of a file's windows in a row must find its chunks still being
52/// kept once the next window is read, while as many helpers are free as the
53/// window could use, before its windows grow to what a builder with help
54/// holds. Helpers are free for a moment while other files are between
55/// windows, and that is not worth the memory.
56const WINDOWS_BEHIND_TO_GROW: usize = 3;
57
58/// What a window holds when it starts on its first file. A window grows only
59/// as a file turns out to be longer, so a small file never costs a large one.
60const WINDOW_START: usize = 64 * 1024;
61
62/// The threads that are free to help with a long file.
63///
64/// Where one chunk ends decides where the next begins, so a file is chunked
65/// in order, on the thread that asks for it. A long stretch of a file is
66/// first looked through by the helpers that are free, each in a part of its
67/// own, for every place where a chunk may end, and is then chunked from
68/// those places alone. Hashing and keeping the chunks is the greater part of
69/// the work and needs no order, so it is shared out among that thread and
70/// the helpers that are free: for a file that is read, while that thread
71/// reads on.
72pub(crate) struct Helpers {
73    free: AtomicUsize,
74}
75
76impl Helpers {
77    fn new(free: usize) -> Arc<Self> {
78        Arc::new(Self {
79            free: AtomicUsize::new(free),
80        })
81    }
82
83    /// The helpers of a builder that may use `threads` threads, its own
84    /// counted. Zero is one thread for each core.
85    fn for_threads(threads: usize) -> Arc<Self> {
86        let threads = match threads {
87            0 => cores(),
88            threads => threads,
89        };
90        Self::new(threads - 1)
91    }
92
93    /// How many helpers are free.
94    fn free(&self) -> usize {
95        self.free.load(Ordering::Relaxed)
96    }
97
98    fn any(&self) -> bool {
99        self.free() > 0
100    }
101
102    /// Takes up to `most` helpers, and says how many it got.
103    fn take(&self, most: usize) -> usize {
104        let mut free = self.free.load(Ordering::Relaxed);
105        loop {
106            let taken = free.min(most);
107            if taken == 0 {
108                return 0;
109            }
110            match self.free.compare_exchange_weak(
111                free,
112                free - taken,
113                Ordering::Relaxed,
114                Ordering::Relaxed,
115            ) {
116                Ok(_) => return taken,
117                Err(now) => free = now,
118            }
119        }
120    }
121
122    fn give(&self, count: usize) {
123        self.free.fetch_add(count, Ordering::Relaxed);
124    }
125}
126
127/// Builds a tree part by part: files from their bytes, folders from their
128/// entries, and at the end the record.
129///
130/// Everything goes into the store as it is made. A chunk, a file or a folder
131/// that the store holds already is not written again.
132pub struct Builder<'s> {
133    store: &'s dyn Store,
134    chunking: Chunking,
135    windows: Windows,
136    helpers: Arc<Helpers>,
137}
138
139impl<'s> Builder<'s> {
140    /// A builder that uses one thread for each core on a long file.
141    pub fn new(store: &'s dyn Store, chunking: Chunking) -> Self {
142        Self::sharing(store, chunking, Helpers::for_threads(0))
143    }
144
145    fn sharing(store: &'s dyn Store, chunking: Chunking, helpers: Arc<Helpers>) -> Self {
146        Self {
147            store,
148            chunking,
149            windows: Windows::default(),
150            helpers,
151        }
152    }
153
154    /// How many threads work on one file: 1 is the calling thread alone, and
155    /// zero is one thread for each core. They find where its chunks end, and
156    /// hash and keep them; for a file that is read, while the calling thread
157    /// reads on. With help, a builder holds up to 64 MiB of a long file that
158    /// it reads at a time; alone it holds up to 16 MiB. When the tree is
159    /// finished, they look in the store for the chunks of its long lists.
160    pub fn threads(mut self, threads: usize) -> Self {
161        self.helpers = Helpers::for_threads(threads);
162        self
163    }
164
165    /// How this builder chunks files.
166    pub fn chunking(&self) -> Chunking {
167        self.chunking
168    }
169
170    /// Splits everything `reader` gives into chunks, keeps the chunks and the
171    /// file's list, and says what the file is. The file is never held in
172    /// memory whole: only a window of it, as [`Builder::threads`] says.
173    pub fn file(&mut self, reader: &mut dyn Read) -> Result<Target> {
174        self.file_from(|buffer| {
175            read_some(reader, buffer).map_err(|source| Error::Stream {
176                operation: "read a file's bytes",
177                source,
178            })
179        })
180    }
181
182    /// The file with these bytes. They are chunked where they lie, and nothing
183    /// is copied on the way to the store.
184    pub fn file_from_bytes(&mut self, bytes: &[u8]) -> Result<Target> {
185        let chunks = settled(self.chunking, &self.helpers, bytes, true);
186        let mut items = Vec::with_capacity(chunks.len());
187        keep_chunks(self.store, &self.helpers, &chunks, &mut items)?;
188        self.keep_list(items)
189    }
190
191    /// The file at `path` on disk.
192    pub fn file_at(&mut self, path: &Path) -> Result<Target> {
193        let mut file = File::open(path).map_err(|error| io_error("open", path, error))?;
194        self.file_from(|buffer| {
195            read_some(&mut file, buffer).map_err(|error| io_error("read", path, error))
196        })
197    }
198
199    /// Chunks, hashes and keeps a file that `read` reads, one window at a
200    /// time. While the chunks of one window are hashed and kept, what is left
201    /// of it goes to the start of the other, and the file is read on into
202    /// that one.
203    ///
204    /// A file that starts while no helper is free is read in short windows.
205    /// They grow once keeping its chunks is what holds the file up while
206    /// helpers are free: a store that writes each chunk to a disk keeps it
207    /// more slowly than the file is read, and a longer window gives the free
208    /// helpers a share.
209    fn file_from(&mut self, mut read: impl FnMut(&mut [u8]) -> Result<usize>) -> Result<Target> {
210        let store = self.store;
211        let chunking = self.chunking;
212        let helpers = &*self.helpers;
213        let mut room = window_room(chunking, helpers.any());
214        let mut behind_in_a_row = 0;
215        let Windows { current, next } = &mut self.windows;
216        let mut items = Vec::new();
217        let (mut filled, mut ended) = fill(current, 0, room, &mut read)?;
218        while filled > 0 {
219            let chunks = settled(chunking, helpers, &current[..filled], ended);
220            if chunks.is_empty() {
221                return Err(Error::Invariant {
222                    detail: "a full window settled no chunk",
223                });
224            }
225            let settled_to: usize = chunks.iter().map(|chunk| chunk.len()).sum();
226            let tail = &current[settled_to..filled];
227            // Once the file has ended there is nothing to read meanwhile. A
228            // window takes no more helpers than it has chunks, and leaves the
229            // others to the files beside it.
230            let most = if ended {
231                chunks.len() / 2
232            } else {
233                settled_to.div_ceil(KEPT_BY_EACH).min(chunks.len())
234            };
235            let (kept, refilled) =
236                keep_chunks_while(store, helpers, most, &chunks, &mut items, |behind| {
237                    carry(tail, next, room)?;
238                    if ended {
239                        return Ok((tail.len(), true));
240                    }
241                    let refilled = fill(next, tail.len(), room, &mut read);
242                    if behind() && helpers.free() >= most {
243                        behind_in_a_row += 1;
244                        if behind_in_a_row >= WINDOWS_BEHIND_TO_GROW {
245                            room = window_room(chunking, true);
246                        }
247                    } else {
248                        behind_in_a_row = 0;
249                    }
250                    refilled
251                });
252            kept?;
253            (filled, ended) = refilled?;
254            std::mem::swap(current, next);
255        }
256        self.keep_list(items)
257    }
258
259    /// Keeps the list of a file whose chunks are kept, and says what the
260    /// file is.
261    fn keep_list(&self, items: Vec<ChunkRef>) -> Result<Target> {
262        let list = FileList::new(items)?;
263        if !self.store.has(Stored::FileList, list.hash())? {
264            self.store
265                .put(Stored::FileList, list.hash(), &list.encode())?;
266        }
267        Ok(list.target())
268    }
269
270    /// Keeps the folder with these entries, and says what it is. The entries
271    /// may come in any order. Two entries with one name are an error.
272    pub fn folder(&mut self, mut entries: Vec<Entry>) -> Result<Target> {
273        entries.sort_by(|left, right| left.name().as_bytes().cmp(right.name().as_bytes()));
274        let list = FolderList::new(entries)?;
275        if !self.store.has(Stored::FolderList, list.hash())? {
276            self.store
277                .put(Stored::FolderList, list.hash(), &list.encode())?;
278        }
279        Ok(list.target())
280    }
281
282    /// Writes the record of the tree that has `top` on top, and gives the
283    /// tree's root. The store must hold every list under `top`.
284    ///
285    /// The whole tree is checked before its record is kept: its sizes, how
286    /// its files are chunked, and how deep its folders sit. The checks are the
287    /// ones a tree goes through when it is taken in, and the totals in the
288    /// record are what those checks counted.
289    pub fn finish(self, top: Target, extra: ExtraData) -> Result<Root> {
290        // The tree is measured with this builder's threads: the helpers that
291        // are free look in the store for the chunks of a long list.
292        let helping = self.helpers.take(usize::MAX);
293        let totals = Intake::measure(self.store, top, self.chunking, helping + 1);
294        self.helpers.give(helping);
295        let record = Record::new(top, totals?, self.chunking, extra)?;
296        let bytes = record.encode();
297        let root = Root::of_record(&bytes);
298        self.store.put(Stored::Record, root.as_hash(), &bytes)?;
299        Ok(root)
300    }
301}
302
303/// Hashes and keeps one chunk, and says what it is. A chunk that the store
304/// holds already is not written again.
305fn keep_chunk(store: &dyn Store, chunk: &[u8]) -> Result<ChunkRef> {
306    let item = ChunkRef::of(chunk)?;
307    if !store.has(Stored::Chunk, &item.hash)? {
308        store.put(Stored::Chunk, &item.hash, chunk)?;
309    }
310    Ok(item)
311}
312
313/// Hashes and keeps chunks that follow one another in a file, and adds what
314/// they are to `items`, in their order. Helpers that are free take a share.
315fn keep_chunks(
316    store: &dyn Store,
317    helpers: &Helpers,
318    chunks: &[&[u8]],
319    items: &mut Vec<ChunkRef>,
320) -> Result<()> {
321    // A helper is worth starting only for a few chunks of its own.
322    keep_chunks_while(store, helpers, chunks.len() / 2, chunks, items, |_| ()).0
323}
324
325/// Hashes and keeps chunks as [`keep_chunks`] does, with up to `most`
326/// helpers, while this thread does `meanwhile`; then this thread takes a
327/// share too. `meanwhile` can ask whether helpers are still keeping the
328/// chunks. Gives what became of the chunks, and what `meanwhile` gave.
329fn keep_chunks_while<T>(
330    store: &dyn Store,
331    helpers: &Helpers,
332    most: usize,
333    chunks: &[&[u8]],
334    items: &mut Vec<ChunkRef>,
335    meanwhile: impl FnOnce(&dyn Fn() -> bool) -> T,
336) -> (Result<()>, T) {
337    let helping = helpers.take(most);
338    let next = AtomicUsize::new(0);
339    let finished = AtomicUsize::new(0);
340    let work = || {
341        let mut kept = Vec::new();
342        loop {
343            let index = next.fetch_add(1, Ordering::Relaxed);
344            let Some(chunk) = chunks.get(index) else {
345                return kept;
346            };
347            let item = keep_chunk(store, chunk);
348            if item.is_err() {
349                next.store(chunks.len(), Ordering::Relaxed);
350            }
351            kept.push((index, item));
352            finished.fetch_add(1, Ordering::Relaxed);
353        }
354    };
355    // With no helper, nothing is kept before `meanwhile` is done, and that
356    // says nothing of how fast the store keeps.
357    let behind = || helping > 0 && finished.load(Ordering::Relaxed) < chunks.len();
358    let (kept, done) = with_helpers(helping, &work, || meanwhile(&behind));
359    let kept: Vec<_> = kept.into_iter().flatten().collect();
360    helpers.give(helping);
361    (in_order(kept, chunks.len(), items), done)
362}
363
364/// Adds what the chunks that were kept are to `items`, in their order, or
365/// gives the failure there was.
366fn in_order(
367    kept: Vec<(usize, Result<ChunkRef>)>,
368    count: usize,
369    items: &mut Vec<ChunkRef>,
370) -> Result<()> {
371    let mut found: Vec<Option<ChunkRef>> = vec![None; count];
372    for (index, item) in kept {
373        found[index] = Some(item?);
374    }
375    for item in found {
376        items.push(item.ok_or(Error::Invariant {
377            detail: "a chunk was left out of a file",
378        })?);
379    }
380    Ok(())
381}
382
383/// What a builder holds of a file that it reads, in two windows: while the
384/// chunks of one are hashed and kept, the file is read on into the other.
385#[derive(Default)]
386struct Windows {
387    current: Vec<u8>,
388    next: Vec<u8>,
389}
390
391/// The most bytes one of a builder's two windows holds: half of what the
392/// builder may hold, and never less than one chunk of the longest kind.
393fn window_room(chunking: Chunking, help: bool) -> usize {
394    let room = if help { ROOM_WITH_HELP } else { ROOM_ALONE };
395    match chunking {
396        Chunking::FastCdcV1 => (room / 2).max(FASTCDC_MAX_SIZE),
397        Chunking::Fixed(size) => {
398            let size = size.get() as usize;
399            let most = size.saturating_mul(FIXED_CHUNKS_IN_A_WINDOW);
400            (room / 2).min(most).max(size)
401        }
402    }
403}
404
405/// The chunks of `data`, the start of what is left of a file, that are
406/// settled: all of them once the file has ended. Helpers that are free look
407/// through a long stretch for where its chunks may end.
408fn settled<'d>(
409    chunking: Chunking,
410    helpers: &Helpers,
411    data: &'d [u8],
412    ended: bool,
413) -> Vec<&'d [u8]> {
414    match chunking {
415        Chunking::FastCdcV1 => {
416            let wanted = (data.len() / LOOKED_THROUGH_BY_EACH).saturating_sub(1);
417            let helping = helpers.take(wanted);
418            let chunks = chunks_of(data, ended, helping + 1);
419            helpers.give(helping);
420            chunks
421        }
422        Chunking::Fixed(size) => {
423            let size = size.get() as usize;
424            let mut chunks: Vec<&[u8]> = data.chunks(size).collect();
425            if !ended && chunks.last().is_some_and(|last| last.len() < size) {
426                chunks.pop();
427            }
428            chunks
429        }
430    }
431}
432
433/// Makes `window` at least `least` bytes long: twice as long as it was, and
434/// no longer than `room` unless `least` is longer.
435fn grow(window: &mut Vec<u8>, least: usize, room: usize) -> Result<()> {
436    let length = (window.len() * 2).max(WINDOW_START).min(room).max(least);
437    let more = length.saturating_sub(window.len());
438    window
439        .try_reserve_exact(more)
440        .map_err(|_| Error::AllocationFailed {
441            resource: "the chunking window",
442            requested: length as u64,
443        })?;
444    window.resize(length, 0);
445    Ok(())
446}
447
448/// Reads into `window` from `filled` on, until it holds `room` bytes or the
449/// file has ended. Gives how many bytes it holds, and whether the file has
450/// ended.
451fn fill(
452    window: &mut Vec<u8>,
453    mut filled: usize,
454    room: usize,
455    read: &mut dyn FnMut(&mut [u8]) -> Result<usize>,
456) -> Result<(usize, bool)> {
457    while filled < room {
458        if filled == window.len() {
459            grow(window, filled + 1, room)?;
460        }
461        let end = window.len().min(room);
462        let count = read(&mut window[filled..end])?;
463        if count > end - filled {
464            return Err(Error::Invariant {
465                detail: "a reader gave more bytes than it was asked for",
466            });
467        }
468        if count == 0 {
469            return Ok((filled, true));
470        }
471        filled += count;
472    }
473    Ok((filled, false))
474}
475
476/// Puts `tail`, what is left of one window, at the start of the other.
477fn carry(tail: &[u8], window: &mut Vec<u8>, room: usize) -> Result<()> {
478    if window.len() < tail.len() {
479        grow(window, tail.len(), room)?;
480    }
481    window[..tail.len()].copy_from_slice(tail);
482    Ok(())
483}
484
485/// What a builder does with a link or a special file that it finds in a
486/// folder. Neither is stored in a tree, and a link is never followed: it
487/// could lead out of the folder that is being built.
488#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
489pub enum Links {
490    /// Stop, and say which one it was.
491    #[default]
492    Refuse,
493    /// Leave it out of the tree.
494    Skip,
495}
496
497/// How a tree is built from disk.
498#[derive(Clone, Debug, Default)]
499pub struct BuildOptions {
500    chunking: Option<Chunking>,
501    extra: ExtraData,
502    timestamp: bool,
503    workers: usize,
504    links: Links,
505}
506
507impl BuildOptions {
508    pub fn new() -> Self {
509        Self::default()
510    }
511
512    /// How files are chunked. Without this they are chunked by content, as every
513    /// tree outside a test should be.
514    pub fn chunking(mut self, chunking: Chunking) -> Self {
515        self.chunking = Some(chunking);
516        self
517    }
518
519    /// Extra data for the tree's record.
520    pub fn extra(mut self, extra: ExtraData) -> Self {
521        self.extra = extra;
522        self
523    }
524
525    /// Writes the time of building into the record. Two builds of the same
526    /// folder then have different roots.
527    pub fn timestamp(mut self, on: bool) -> Self {
528        self.timestamp = on;
529        self
530    }
531
532    /// How many threads build the tree. Zero is one for each core. Files
533    /// are chunked several at once, and a thread that has no file of its own
534    /// helps to hash the chunks of a long one.
535    pub fn workers(mut self, workers: usize) -> Self {
536        self.workers = workers;
537        self
538    }
539
540    pub fn links(mut self, links: Links) -> Self {
541        self.links = links;
542        self
543    }
544}
545
546/// Gives the extra data for one entry: its path on disk, its name, and
547/// whether it is a file or a folder.
548pub type EntryExtra<'a> = dyn Fn(&Path, &str, Kind) -> Result<ExtraData> + Sync + 'a;
549
550/// Builds the tree of the folder or the file at `path` into `store`, and
551/// gives its root.
552///
553/// A folder's own name is not part of its tree, so the same folder gives the
554/// same root wherever it is and whatever it is called. Entries have no extra
555/// data: [`build_with`] adds some.
556pub fn build(store: &dyn Store, path: impl AsRef<Path>, options: &BuildOptions) -> Result<Root> {
557    build_tree(store, path.as_ref(), options, None)
558}
559
560/// Builds a tree as [`build`] does, and asks `entry_extra` for the extra
561/// data of every entry.
562pub fn build_with(
563    store: &dyn Store,
564    path: impl AsRef<Path>,
565    options: &BuildOptions,
566    entry_extra: &EntryExtra<'_>,
567) -> Result<Root> {
568    build_tree(store, path.as_ref(), options, Some(entry_extra))
569}
570
571fn build_tree(
572    store: &dyn Store,
573    path: &Path,
574    options: &BuildOptions,
575    entry_extra: Option<&EntryExtra<'_>>,
576) -> Result<Root> {
577    let chunking = options.chunking.unwrap_or(Chunking::FastCdcV1);
578    let mut extra = options.extra.clone();
579    if options.timestamp {
580        extra.insert(TIMESTAMP_KEY, timestamp(SystemTime::now())?)?;
581    }
582    let metadata = fs::metadata(path).map_err(|error| io_error("look at", path, error))?;
583    let mut builder = Builder::new(store, chunking).threads(options.workers);
584    if !metadata.is_dir() {
585        let top = builder.file_at(path)?;
586        return builder.finish(top, extra);
587    }
588
589    // From here on nothing is reached by its path: the folder is held open,
590    // and so is every folder under it while it is read.
591    let top = Held::open(path).map_err(|error| io_error("open", path, error))?;
592    let (folders, file_targets) =
593        walk_and_chunk(store, chunking, &top, options.links, options.workers)?;
594    // A folder is found after the folder it is in, so going backwards every
595    // folder is made after the folders inside it.
596    let mut folder_targets: Vec<Option<Target>> = vec![None; folders.len()];
597    for index in (0..folders.len()).rev() {
598        let mut entries = Vec::with_capacity(folders[index].children.len());
599        for child in &folders[index].children {
600            let target = match child.kind {
601                Kind::File => *file_targets.get(child.index).ok_or(Error::Invariant {
602                    detail: "a file was left out of the build",
603                })?,
604                Kind::Folder => folder_targets[child.index].ok_or(Error::Invariant {
605                    detail: "a folder was made before a folder inside it",
606                })?,
607            };
608            let extra = match entry_extra {
609                // A file's path is put together here, for the caller to see,
610                // and only when there is a caller to see it. No file is opened
611                // by it.
612                Some(entry_extra) => match child.kind {
613                    Kind::File => entry_extra(
614                        &folders[index].path.join(&child.name),
615                        &child.name,
616                        child.kind,
617                    )?,
618                    Kind::Folder => {
619                        entry_extra(&folders[child.index].path, &child.name, child.kind)?
620                    }
621                },
622                None => ExtraData::new(),
623            };
624            entries.push(Entry::new(child.name.as_str(), target, extra)?);
625        }
626        folder_targets[index] = Some(builder.folder(entries)?);
627    }
628    let top = folder_targets[0].ok_or(Error::Invariant {
629        detail: "the top folder was not made",
630    })?;
631    builder.finish(top, extra)
632}
633
634struct Folder {
635    path: PathBuf,
636    children: Vec<Child>,
637}
638
639struct Child {
640    name: String,
641    kind: Kind,
642    /// The child's place among the folders, or among the files.
643    index: usize,
644}
645
646/// A folder on the way down to the one that is read, held open, with the
647/// folders inside it that are still to be read: each by its name and its
648/// place among the folders.
649type OnTheWay = (Arc<Held>, Vec<(String, usize)>);
650
651/// How many folders' files may wait for the threads that chunk. A folder is
652/// kept open while it has files that are not chunked yet, so this bounds how many
653/// folders are open at a time.
654const FOLDERS_AHEAD: usize = 16;
655
656/// The files that the walk found in one folder, for the threads to chunk. The
657/// folder is held open, and each file is opened from it by its name.
658struct Batch {
659    folder: Arc<Held>,
660    /// Each file's place among the files, and its name in the folder.
661    files: Vec<(usize, String)>,
662    /// How many of the files are taken.
663    taken: AtomicUsize,
664}
665
666impl Batch {
667    /// A file that no thread has taken yet. Each file is given once, to
668    /// whichever thread asks first.
669    fn take(&self) -> Option<&(usize, String)> {
670        self.files.get(self.taken.fetch_add(1, Ordering::Relaxed))
671    }
672
673    fn all_taken(&self) -> bool {
674        self.taken.load(Ordering::Relaxed) >= self.files.len()
675    }
676}
677
678/// What was there when a folder was read has to be there still when it is
679/// opened. If a link took its place meanwhile, the link is not followed.
680fn changed(path: &Path, refused: Refused) -> Error {
681    let what = match refused {
682        Refused::Io(error) => return io_error("open", path, error),
683        Refused::Link => "a link now, where a file or a folder was when the build began",
684        Refused::Other => "something else now than it was when the build began",
685    };
686    Error::UnsupportedEntry {
687        path: path.to_path_buf(),
688        what,
689    }
690}
691
692/// Chunks and keeps the file `name` of a folder that is held open. The file is
693/// opened from the folder itself. Once `stop` is set, the file is given up,
694/// however much of it is left.
695fn chunk_file_in(
696    builder: &mut Builder<'_>,
697    folder: &Held,
698    name: &str,
699    stop: Option<&AtomicBool>,
700) -> Result<Target> {
701    // The path is for messages, and is put together only for one.
702    let path = || folder.path().join(name);
703    let mut file = folder
704        .open_file(name)
705        .map_err(|refused| changed(&path(), refused))?;
706    builder.file_from(|buffer| {
707        if stop.is_some_and(|stop| stop.load(Ordering::Relaxed)) {
708            return Err(STOPPED);
709        }
710        read_some(&mut file, buffer).map_err(|error| io_error("read", &path(), error))
711    })
712}
713
714/// What a walk through a folder has found so far.
715struct Walk<'a> {
716    links: Links,
717    folders: Vec<Folder>,
718    /// How many files were found.
719    files: usize,
720    /// Takes the files of each folder, once the folder is read.
721    on_files: &'a mut dyn FnMut(Batch) -> Result<()>,
722}
723
724impl Walk<'_> {
725    /// Reads one folder, which is `depth` folders down from the top, the top
726    /// counted. Notes what is in it, hands its files on, and gives the
727    /// folders inside it, each with its place among the folders.
728    fn read(
729        &mut self,
730        held: &Arc<Held>,
731        index: usize,
732        depth: usize,
733    ) -> Result<Vec<(String, usize)>> {
734        let folder_path = held.path().to_path_buf();
735        let listed = held
736            .list()
737            .map_err(|error| io_error("list", &folder_path, error))?;
738        let mut children = Vec::with_capacity(listed.len());
739        let mut inside = Vec::new();
740        let mut files = Vec::new();
741        for (name, found) in listed {
742            let name = name.into_string().map_err(|name| Error::NonUtf8FileName {
743                path: folder_path.join(name),
744            })?;
745            check_name(&name)?;
746            match found {
747                Found::Folder => {
748                    if depth >= MAX_FOLDER_DEPTH {
749                        return Err(Error::TooDeep {
750                            limit: MAX_FOLDER_DEPTH,
751                        });
752                    }
753                    let below = self.folders.len();
754                    children.push(Child {
755                        name: name.clone(),
756                        kind: Kind::Folder,
757                        index: below,
758                    });
759                    self.folders.push(Folder {
760                        path: folder_path.join(&name),
761                        children: Vec::new(),
762                    });
763                    inside.push((name, below));
764                }
765                Found::File => {
766                    children.push(Child {
767                        name: name.clone(),
768                        kind: Kind::File,
769                        index: self.files,
770                    });
771                    files.push((self.files, name));
772                    self.files += 1;
773                }
774                Found::Link | Found::Other => {
775                    if self.links == Links::Refuse {
776                        return Err(Error::UnsupportedEntry {
777                            path: folder_path.join(&name),
778                            what: if found == Found::Link {
779                                "a link"
780                            } else {
781                                "a special file"
782                            },
783                        });
784                    }
785                }
786            }
787        }
788        children.sort_by(|left, right| left.name.as_bytes().cmp(right.name.as_bytes()));
789        self.folders[index].children = children;
790        if !files.is_empty() {
791            (self.on_files)(Batch {
792                folder: Arc::clone(held),
793                files,
794                taken: AtomicUsize::new(0),
795            })?;
796        }
797        Ok(inside)
798    }
799}
800
801/// Finds every folder and every file under `top`, and hands the files of
802/// each folder to `on_files` once the folder is read. A link is never
803/// followed. Gives the folders, and how many files there are.
804///
805/// A folder is opened from the folder it is in, which is held open, and is
806/// held open itself while it is read. So no folder on the way to a file can
807/// be swapped for a link between the reading of a folder and the opening of
808/// what is in it.
809fn walk(
810    top: &Arc<Held>,
811    links: Links,
812    on_files: &mut dyn FnMut(Batch) -> Result<()>,
813) -> Result<(Vec<Folder>, usize)> {
814    let mut walk = Walk {
815        links,
816        folders: vec![Folder {
817            path: top.path().to_path_buf(),
818            children: Vec::new(),
819        }],
820        files: 0,
821        on_files,
822    };
823    // The folders on the way down to the one that is read, each held open,
824    // with the folders inside it that are still to be read.
825    let mut way: Vec<OnTheWay> = Vec::new();
826    let mut next = Some((Arc::clone(top), 0_usize));
827    loop {
828        if let Some((held, index)) = next.take() {
829            let inside = walk.read(&held, index, way.len() + 1)?;
830            way.push((held, inside));
831        }
832        let Some((held, inside)) = way.last_mut() else {
833            break;
834        };
835        match inside.pop() {
836            Some((name, index)) => {
837                let below = held
838                    .open_folder(&name)
839                    .map_err(|refused| changed(&walk.folders[index].path, refused))?;
840                next = Some((below, index));
841            }
842            None => {
843                way.pop();
844            }
845        }
846    }
847    Ok((walk.folders, walk.files))
848}
849
850/// What a thread gives when it stopped because the build had failed
851/// somewhere else. The error that the caller is given is that failure's.
852const STOPPED_DETAIL: &str = "the build was stopped";
853const STOPPED: Error = Error::Invariant {
854    detail: STOPPED_DETAIL,
855};
856
857fn is_stopped(error: &Error) -> bool {
858    matches!(error, Error::Invariant { detail } if *detail == STOPPED_DETAIL)
859}
860
861fn lock<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
862    mutex
863        .lock()
864        .unwrap_or_else(|poisoned| poisoned.into_inner())
865}
866
867fn wait<'a, T>(told: &Condvar, guard: MutexGuard<'a, T>) -> MutexGuard<'a, T> {
868    told.wait(guard)
869        .unwrap_or_else(|poisoned| poisoned.into_inner())
870}
871
872/// The folders whose files wait for the threads that chunk, between the
873/// thread that walks and those threads.
874///
875/// Nobody waits here for a thread that is gone. A file that cannot be chunked, a
876/// walk that fails and a thread that falls over each set `failed`, and wake
877/// whoever waits.
878struct Waiting {
879    state: Mutex<WaitingState>,
880    /// Told when there is a folder to take files from, or none will come.
881    more: Condvar,
882    /// Told when a folder's files are all taken, so that the walk may go on.
883    room: Condvar,
884    /// Nothing more is to be chunked.
885    failed: AtomicBool,
886}
887
888struct WaitingState {
889    batches: VecDeque<Arc<Batch>>,
890    /// The walk is over: no more folders will come.
891    over: bool,
892}
893
894impl Waiting {
895    fn new() -> Self {
896        Self {
897            state: Mutex::new(WaitingState {
898                batches: VecDeque::new(),
899                over: false,
900            }),
901            more: Condvar::new(),
902            room: Condvar::new(),
903            failed: AtomicBool::new(false),
904        }
905    }
906
907    fn has_failed(&self) -> bool {
908        self.failed.load(Ordering::Relaxed)
909    }
910
911    /// For the walk: adds a folder's files, once there is room for them.
912    fn add(&self, batch: Batch) -> Result<()> {
913        let one_file = batch.files.len() == 1;
914        let mut state = lock(&self.state);
915        loop {
916            if self.has_failed() {
917                return Err(STOPPED);
918            }
919            if state.batches.len() < FOLDERS_AHEAD {
920                break;
921            }
922            state = wait(&self.room, state);
923        }
924        state.batches.push_back(Arc::new(batch));
925        drop(state);
926        if one_file {
927            self.more.notify_one();
928        } else {
929            self.more.notify_all();
930        }
931        Ok(())
932    }
933
934    /// For a thread that chunks: a folder that has files left to take. None
935    /// when the walk is over and every file is taken, or when the build has
936    /// failed.
937    fn next(&self) -> Option<Arc<Batch>> {
938        let mut state = lock(&self.state);
939        loop {
940            if self.has_failed() {
941                return None;
942            }
943            while state.batches.front().is_some_and(|batch| batch.all_taken()) {
944                state.batches.pop_front();
945                self.room.notify_one();
946            }
947            if let Some(batch) = state.batches.front() {
948                return Some(Arc::clone(batch));
949            }
950            if state.over {
951                return None;
952            }
953            state = wait(&self.more, state);
954        }
955    }
956
957    /// Nothing more is to be chunked. Set with the lock held, so that no thread
958    /// can look, miss it, and then wait.
959    fn fail(&self) {
960        let state = lock(&self.state);
961        self.failed.store(true, Ordering::Relaxed);
962        drop(state);
963        self.more.notify_all();
964        self.room.notify_all();
965    }
966
967    /// The walk is over.
968    fn end(&self) {
969        lock(&self.state).over = true;
970        self.more.notify_all();
971    }
972}
973
974/// Held by each thread of a build while it works. A thread that falls over
975/// tells the others as it goes, so that none of them waits for it.
976struct Working<'a>(&'a Waiting);
977
978impl Drop for Working<'_> {
979    fn drop(&mut self) {
980        if std::thread::panicking() {
981            self.0.fail();
982        }
983    }
984}
985
986/// Finds every folder and every file under `top`, and chunks and keeps the
987/// files while they are found, several at once. Gives the folders, and what
988/// each file is.
989fn walk_and_chunk(
990    store: &dyn Store,
991    chunking: Chunking,
992    top: &Arc<Held>,
993    links: Links,
994    threads: usize,
995) -> Result<(Vec<Folder>, Vec<Target>)> {
996    let threads = match threads {
997        0 => cores(),
998        threads => threads,
999    };
1000    // A thread that has no file left gives itself up to help with the long
1001    // files that are still being chunked.
1002    let helpers = Helpers::new(0);
1003    if threads == 1 {
1004        // One thread walks and chunks in turn.
1005        let mut builder = Builder::sharing(store, chunking, helpers);
1006        let mut targets = Vec::new();
1007        let (folders, _) = walk(top, links, &mut |batch| {
1008            for (index, name) in &batch.files {
1009                if *index != targets.len() {
1010                    return Err(Error::Invariant {
1011                        detail: "a file was chunked out of its turn",
1012                    });
1013                }
1014                targets.push(chunk_file_in(&mut builder, &batch.folder, name, None)?);
1015            }
1016            Ok(())
1017        })?;
1018        return Ok((folders, targets));
1019    }
1020    let waiting = Waiting::new();
1021    let work = || -> Result<Vec<(usize, Target)>> {
1022        let _working = Working(&waiting);
1023        let mut builder = Builder::sharing(store, chunking, Arc::clone(&helpers));
1024        let mut done = Vec::new();
1025        let mut first_error = None;
1026        while let Some(batch) = waiting.next() {
1027            // Every thread that is free takes files from the same folder,
1028            // one each, until the folder has none left.
1029            while let Some((index, name)) = batch.take() {
1030                if waiting.has_failed() {
1031                    break;
1032                }
1033                let stop = Some(&waiting.failed);
1034                match chunk_file_in(&mut builder, &batch.folder, name, stop) {
1035                    Ok(target) => done.push((*index, target)),
1036                    Err(error) => {
1037                        first_error.get_or_insert(error);
1038                        waiting.fail();
1039                    }
1040                }
1041            }
1042        }
1043        helpers.give(1);
1044        match first_error {
1045            Some(error) => Err(error),
1046            None => Ok(done),
1047        }
1048    };
1049    let (walked, chunked) = std::thread::scope(|scope| {
1050        let _working = Working(&waiting);
1051        let handles: Vec<_> = (0..threads).map(|_| scope.spawn(work)).collect();
1052        let walked = walk(top, links, &mut |batch| waiting.add(batch));
1053        // A walk that failed stops the chunking too: a thread gives up the
1054        // file it is on, however long that file is.
1055        if walked.is_err() {
1056            waiting.fail();
1057        }
1058        // With the walk over, the threads run out of files and end.
1059        waiting.end();
1060        let chunked: Vec<Result<Vec<(usize, Target)>>> = handles
1061            .into_iter()
1062            .map(|handle| match handle.join() {
1063                Ok(result) => result,
1064                Err(payload) => std::panic::resume_unwind(payload),
1065            })
1066            .collect();
1067        (walked, chunked)
1068    });
1069    // The failure that came first in its thread is the one to tell. A thread
1070    // that only stopped for another's failure has nothing to tell.
1071    let mut done = Vec::new();
1072    let mut stopped = false;
1073    for result in chunked {
1074        match result {
1075            Ok(part) => done.extend(part),
1076            Err(error) if is_stopped(&error) => stopped = true,
1077            Err(error) => return Err(error),
1078        }
1079    }
1080    let (folders, files) = walked?;
1081    if stopped {
1082        return Err(STOPPED);
1083    }
1084    let mut targets: Vec<Option<Target>> = vec![None; files];
1085    for (index, target) in done {
1086        targets[index] = Some(target);
1087    }
1088    let targets = targets
1089        .into_iter()
1090        .map(|target| {
1091            target.ok_or(Error::Invariant {
1092                detail: "a file was left out of the build",
1093            })
1094        })
1095        .collect::<Result<Vec<Target>>>()?;
1096    Ok((folders, targets))
1097}
1098
1099/// The time as text: `2026-11-12T08:30:00Z`, in UTC, to the second.
1100fn timestamp(time: SystemTime) -> Result<String> {
1101    let elapsed = time
1102        .duration_since(UNIX_EPOCH)
1103        .map_err(|_| Error::SystemTimeBeforeUnixEpoch)?;
1104    let seconds =
1105        i64::try_from(elapsed.as_secs()).map_err(|_| Error::SizeOverflow { field: "timestamp" })?;
1106    Ok(format_epoch_seconds(seconds))
1107}
1108
1109fn format_epoch_seconds(seconds: i64) -> String {
1110    let days = seconds.div_euclid(86_400);
1111    let seconds_of_day = seconds.rem_euclid(86_400);
1112    let shifted_days = days + 719_468;
1113    let era = shifted_days.div_euclid(146_097);
1114    let day_of_era = shifted_days - era * 146_097;
1115    let year_of_era =
1116        (day_of_era - day_of_era / 1_460 + day_of_era / 36_524 - day_of_era / 146_096) / 365;
1117    let mut year = year_of_era + era * 400;
1118    let day_of_year = day_of_era - (365 * year_of_era + year_of_era / 4 - year_of_era / 100);
1119    let month_prime = (5 * day_of_year + 2) / 153;
1120    let day = day_of_year - (153 * month_prime + 2) / 5 + 1;
1121    let month = month_prime + if month_prime < 10 { 3 } else { -9 };
1122    if month <= 2 {
1123        year += 1;
1124    }
1125    let hour = seconds_of_day / 3_600;
1126    let minute = seconds_of_day % 3_600 / 60;
1127    let second = seconds_of_day % 60;
1128    format!("{year:04}-{month:02}-{day:02}T{hour:02}:{minute:02}:{second:02}Z")
1129}
1130
1131#[cfg(test)]
1132mod tests {
1133    use super::*;
1134    use crate::{Hash, MemoryStore};
1135    use std::time::{Duration, Instant};
1136
1137    /// Chunks of a fixed 4 MiB: a window of a builder alone holds two, and
1138    /// one of a builder with help eight.
1139    const CHUNK: usize = 4 << 20;
1140
1141    /// What one window of a builder alone holds.
1142    const ALONE: usize = ROOM_ALONE / 2;
1143
1144    /// A store that takes a while over each thing it keeps, as one that
1145    /// writes to a disk does.
1146    struct Slow(MemoryStore);
1147
1148    impl Store for Slow {
1149        fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1150            std::thread::sleep(Duration::from_millis(100));
1151            self.0.put(kind, hash, bytes)
1152        }
1153
1154        fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1155            self.0.get(kind, hash)
1156        }
1157
1158        fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1159            self.0.remove(kind, hash)
1160        }
1161    }
1162
1163    /// A store that counts the chunks it has kept.
1164    struct Counted {
1165        inner: MemoryStore,
1166        chunks: AtomicUsize,
1167    }
1168
1169    impl Store for Counted {
1170        fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1171            self.inner.put(kind, hash, bytes)?;
1172            if kind == Stored::Chunk {
1173                self.chunks.fetch_add(1, Ordering::SeqCst);
1174            }
1175            Ok(())
1176        }
1177
1178        fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1179            self.inner.get(kind, hash)
1180        }
1181
1182        fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1183            self.inner.remove(kind, hash)
1184        }
1185    }
1186
1187    /// A store that takes every helper that is free whenever it is handed
1188    /// something to keep, as other files would.
1189    struct Taking {
1190        inner: MemoryStore,
1191        helpers: Arc<Helpers>,
1192    }
1193
1194    impl Store for Taking {
1195        fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1196            self.helpers.take(usize::MAX);
1197            self.inner.put(kind, hash, bytes)
1198        }
1199
1200        fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1201            self.inner.get(kind, hash)
1202        }
1203
1204        fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1205            self.inner.remove(kind, hash)
1206        }
1207    }
1208
1209    /// Builds a file of `chunks` chunks of [`CHUNK`] bytes, each of a byte of
1210    /// its own, with the helpers `helpers` counts. `asked` is told where each
1211    /// read starts and how much it asks for, before it is answered.
1212    fn read_through(
1213        store: &dyn Store,
1214        helpers: Arc<Helpers>,
1215        chunks: usize,
1216        mut asked: impl FnMut(usize, usize),
1217    ) {
1218        let chunking = Chunking::fixed(CHUNK as u32).unwrap();
1219        let mut builder = Builder::sharing(store, chunking, helpers);
1220        // Windows as long as they get, as a builder has them after a long
1221        // file: each read then asks for all that the window may hold.
1222        let longest = window_room(chunking, true);
1223        builder.windows.current.resize(longest, 0);
1224        builder.windows.next.resize(longest, 0);
1225        let length = chunks * CHUNK;
1226        let mut at = 0;
1227        builder
1228            .file_from(|buffer| {
1229                asked(at, buffer.len());
1230                let count = buffer.len().min(length - at);
1231                let mut done = 0;
1232                while done < count {
1233                    let chunk = (at + done) / CHUNK;
1234                    let end = ((chunk + 1) * CHUNK - at).min(count);
1235                    buffer[done..end].fill(chunk as u8);
1236                    done = end;
1237                }
1238                at += count;
1239                Ok(count)
1240            })
1241            .unwrap();
1242    }
1243
1244    #[test]
1245    fn a_file_whose_chunks_are_kept_slowly_is_read_in_longer_windows_once_helpers_are_free() {
1246        let store = Slow(MemoryStore::new());
1247        // The file starts while no helper is free, as one does that starts
1248        // before the threads with no file of their own give themselves up.
1249        let helpers = Helpers::new(0);
1250        let free = Arc::clone(&helpers);
1251        let mut longest = 0;
1252        read_through(&store, helpers, 12, |at, length| {
1253            if at == 0 {
1254                free.give(6);
1255            }
1256            longest = longest.max(length);
1257        });
1258        assert!(
1259            longest > ALONE,
1260            "the longest read asked for {longest} bytes"
1261        );
1262    }
1263
1264    #[test]
1265    fn a_file_whose_chunks_are_kept_as_fast_as_it_is_read_keeps_its_short_windows() {
1266        let store = Counted {
1267            inner: MemoryStore::new(),
1268            chunks: AtomicUsize::new(0),
1269        };
1270        let helpers = Helpers::new(0);
1271        let free = Arc::clone(&helpers);
1272        let mut longest = 0;
1273        read_through(&store, helpers, 12, |at, length| {
1274            if at == 0 {
1275                free.give(6);
1276            }
1277            // A window is read only once the chunks before it are kept, and
1278            // a while after: the store keeps up with the file, however long
1279            // hashing takes here.
1280            let waited = Instant::now();
1281            while store.chunks.load(Ordering::SeqCst) < at / CHUNK
1282                && waited.elapsed() < Duration::from_secs(10)
1283            {
1284                std::thread::sleep(Duration::from_millis(1));
1285            }
1286            std::thread::sleep(Duration::from_millis(20));
1287            longest = longest.max(length);
1288        });
1289        assert!(longest <= ALONE, "a read asked for {longest} bytes");
1290    }
1291
1292    #[test]
1293    fn helpers_that_are_free_for_a_moment_do_not_grow_a_window() {
1294        let store = Slow(MemoryStore::new());
1295        let helpers = Helpers::new(0);
1296        let free = Arc::clone(&helpers);
1297        let mut held = 0;
1298        let mut longest_early = 0;
1299        let mut longest = 0;
1300        // Free while windows 1 to WINDOWS_BEHIND_TO_GROW - 1 are read, taken
1301        // by other files while the next one is read, and free again from the
1302        // one after: the windows may grow only that many windows later.
1303        let early = (2 * WINDOWS_BEHIND_TO_GROW + 1) * ALONE;
1304        read_through(&store, helpers, 20, |at, length| {
1305            let window = at / ALONE;
1306            if at == 0 {
1307                free.give(6);
1308            } else if window == WINDOWS_BEHIND_TO_GROW {
1309                held += free.take(usize::MAX);
1310            } else if window == WINDOWS_BEHIND_TO_GROW + 1 {
1311                free.give(std::mem::take(&mut held));
1312            }
1313            if at < early {
1314                longest_early = longest_early.max(length);
1315            }
1316            longest = longest.max(length);
1317        });
1318        assert!(
1319            longest_early <= ALONE,
1320            "a read before byte {early} asked for {longest_early} bytes"
1321        );
1322        assert!(longest > ALONE, "the windows never grew");
1323    }
1324
1325    #[test]
1326    fn a_window_that_too_few_helpers_could_share_keeps_its_length() {
1327        let store = Slow(MemoryStore::new());
1328        let helpers = Helpers::new(0);
1329        let free = Arc::clone(&helpers);
1330        let mut longest = 0;
1331        // Each window takes two helpers for its two chunks, and leaves one.
1332        read_through(&store, helpers, 12, |at, length| {
1333            if at == 0 {
1334                free.give(3);
1335            }
1336            longest = longest.max(length);
1337        });
1338        assert!(longest <= ALONE, "a read asked for {longest} bytes");
1339    }
1340
1341    #[test]
1342    fn chunks_that_no_helper_keeps_do_not_count_as_behind() {
1343        let helpers = Helpers::new(0);
1344        let store = Taking {
1345            inner: MemoryStore::new(),
1346            helpers: Arc::clone(&helpers),
1347        };
1348        let free = Arc::clone(&helpers);
1349        let mut longest = 0;
1350        // No helper is free when a window's chunks are handed out, and six
1351        // are once the next window is read: this thread keeps every chunk
1352        // itself, after the read, and the store has kept none of them by then
1353        // whatever its speed.
1354        read_through(&store, helpers, 12, |at, length| {
1355            if at > 0 {
1356                free.give(6);
1357            }
1358            longest = longest.max(length);
1359        });
1360        assert!(longest <= ALONE, "a read asked for {longest} bytes");
1361    }
1362
1363    #[test]
1364    fn the_time_is_written_in_utc_to_the_second() {
1365        assert_eq!(format_epoch_seconds(0), "1970-01-01T00:00:00Z");
1366        assert_eq!(format_epoch_seconds(951_782_400), "2000-02-29T00:00:00Z");
1367        assert_eq!(format_epoch_seconds(1_794_472_200), "2026-11-12T08:30:00Z");
1368        assert_eq!(format_epoch_seconds(4_102_444_799), "2099-12-31T23:59:59Z");
1369        assert_eq!(format_epoch_seconds(-1), "1969-12-31T23:59:59Z");
1370    }
1371}