ferrosys 0.8.0

Pure-Rust filesystem formatter and reader: ext4, ext3, ext2, FAT32, FAT16, FAT12, exFAT, btrfs, and APFS — rootless, in userspace, byte-reproducible
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
//! The extraction surface: [`FsTree`], what a sink and a caller need of any family's
//! reader.
//!
//! Opening an image hands back that family's own reader, whole, because the families'
//! readers are not interchangeable. Draining one into somewhere else is the exception: a
//! tar archive, a directory tree on this host, and a listing all want the same four things
//! — walk the names, stat one, stream a file's bytes, resolve a link — and none of them
//! wants to know which format is underneath. A caller answering one request at a time wants
//! three more: find a path, list a directory, and report the room.
//!
//! So this trait is exactly those seven, kept to what those consumers call. Anything one
//! family alone can answer stays on that family's concrete reader, where a caller reaches
//! it by matching on what opening an image hands back.
//!
//! # What a stat means when the format has no such field
//!
//! [`stat`](FsTree::stat) hands back a complete [`Attributes`] whatever the family is,
//! because a sink writing a host file needs an owner and a mode and there is no such thing
//! as half of one. A family with no field for a property fills it from the [`Synthesis`]
//! the caller supplied and names the property in
//! [`synthesized`](Attributes::synthesized), so a sink records what was invented without
//! knowing which family invented it.

use crate::fidelity::{Property, Synthesis};
use crate::finding::Family;
use crate::source::{Darwin, Metadata};
use crate::xattr::Xattr;

/// The most bytes of a file a sink asks [`FsTree::read_bytes`] for at a time. Large enough
/// that a big file is not a read per block, small enough that the buffer is not worth
/// thinking about.
///
/// It is a ceiling rather than the size: a file shorter than this gets a buffer its own size,
/// so a root filesystem of many small files does not allocate and zero a mebibyte per entry
/// to move a few hundred bytes through it.
#[cfg(any(
    feature = "tar",
    all(feature = "dir", any(target_os = "linux", target_os = "android"))
))]
pub(crate) const BODY_WINDOW: usize = 1 << 20;

/// A failure reading a filesystem through the extraction surface.
///
/// The classification is shared: whether the source could not be read at all, whether the
/// filesystem's own bytes are wrong, whether it uses something this build does not follow,
/// whether a bound stopped the read, and whether a path names nothing are the answers a sink
/// acts on, and they mean the same thing for every family. The family's own message rides
/// along, and a caller that needs the family's *typed* error opens that family's reader
/// directly rather than going through this surface.
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum TreeError {
    /// The underlying source could not be read or sought.
    ///
    /// The `kind` is [`std::io::Error`]'s own classification, kept beside the message rather
    /// than folded into it because it is what a caller *acts* on: a truncated image
    /// ([`UnexpectedEof`](std::io::ErrorKind::UnexpectedEof)) is a property of what is being
    /// read, while a permission failure
    /// ([`PermissionDenied`](std::io::ErrorKind::PermissionDenied)) is a property of the
    /// environment, and telling them apart should not require matching on text.
    ///
    /// It does not appear in the rendered message, because the message already says it:
    /// `message` is the underlying error rendered by [`std::io::Error`], which opens with the
    /// kind's own description. The field is the machine-readable half of a fact the text
    /// already carries.
    ///
    /// Every error in this crate records an i/o failure this way. They are separate variants
    /// on separate enums because their *other* variants are, and a caller matching on one
    /// should not reach through a wrapper for the two fields it wants.
    #[error("i/o error: {message}")]
    #[non_exhaustive]
    Io {
        /// How the underlying [`std::io::Error`] classified itself.
        kind: std::io::ErrorKind,
        /// The error rendered as text, for a message a person reads.
        message: String,
    },
    /// The filesystem's bytes are not what its format requires: a structure did not parse,
    /// a reference pointed outside the image, or something failed its own checksum.
    #[error("malformed {family} filesystem: {detail}", family = .family.as_str())]
    #[non_exhaustive]
    Malformed {
        /// The family whose reader refused.
        family: Family,
        /// That reader's own message.
        detail: String,
    },
    /// The image uses something this build's reader does not follow, so what it holds
    /// cannot be reported faithfully.
    #[error("unsupported {family} filesystem: {detail}", family = .family.as_str())]
    #[non_exhaustive]
    Unsupported {
        /// The family whose reader refused.
        family: Family,
        /// That reader's own message.
        detail: String,
    },
    /// A read would have exceeded a bound: one the caller set through
    /// [`Limits`](crate::Limits), or the longest path a walk builds.
    ///
    /// No verdict that the filesystem is malformed: a sound one can reach the caller's caps
    /// and the longest path. [`Bound::Entries`] is also reached by an image whose storage
    /// describes fewer names than it claims.
    #[error("{family} read exceeded a limit: {detail}", family = .family.as_str())]
    #[non_exhaustive]
    LimitExceeded {
        /// The family whose reader stopped.
        family: Family,
        /// Which bound applied.
        bound: Bound,
        /// That reader's own message, naming the bound that applied.
        detail: String,
    },
    /// A path names nothing in the filesystem: a component that is not there, one that is not a
    /// directory with a name after it, or a chain of symbolic links that does not end.
    ///
    /// A statement about the path that was asked for, and none about the filesystem.
    #[error(
        "no such path in the {family} filesystem: {}",
        crate::escape::printable(.path),
        family = .family.as_str()
    )]
    #[non_exhaustive]
    NotFound {
        /// The family whose reader looked.
        family: Family,
        /// The path, as it was given.
        path: Vec<u8>,
    },
}

impl TreeError {
    /// What a read `bound` stopped reports, in `family`'s words: `reason` is the family's own
    /// account of the bound it reached.
    pub(crate) fn limit(family: Family, bound: Bound, reason: &impl std::fmt::Display) -> Self {
        TreeError::LimitExceeded {
            family,
            bound,
            detail: reason.to_string(),
        }
    }
}

/// Which bound stopped a read, as [`TreeError::LimitExceeded`] reports it.
///
/// [`FileBytes`](Self::FileBytes) is the caller's, set through [`Limits`](crate::Limits), and a
/// read past it is one a larger setting carries out. [`Entries`](Self::Entries) is the
/// caller's cap too, or the names the image's storage has room to describe where that is
/// lower, which a well-formed filesystem never reaches. [`PathBytes`](Self::PathBytes) is this
/// crate's own and has no setting.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum Bound {
    /// [`Limits::max_file_bytes`](crate::Limits::max_file_bytes): a file, or an attribute's
    /// value, longer than the cap.
    FileBytes,
    /// [`Limits::max_walk_entries`](crate::Limits::max_walk_entries), or the names the
    /// image's storage has room to describe where that is lower: a walk, a directory, or a
    /// tree holding more entries than a read gathers.
    Entries,
    /// The longest path a walk builds, 4,096 bytes, which is Linux's `PATH_MAX`: a tree
    /// nested deeper than the paths a walk hands out reach. Every format here holds such a
    /// tree, and a scan reads one whole.
    PathBytes,
}

/// What a node in a filesystem tree is, as an extraction sees it.
///
/// This is the read-side mirror of [`EntryKind`](crate::EntryKind), and it differs in one
/// way: there is no hard-link variant. A second name for a node is not a *kind* — the node
/// is still a file — so it is reported through [`TreeEntry::shared`], which says which node
/// two names are both for.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum NodeKind {
    /// A directory.
    Directory,
    /// A regular file.
    File {
        /// The file's length in bytes, which is how much
        /// [`read_bytes`](FsTree::read_bytes) will yield.
        size: u64,
    },
    /// A symbolic link, whose target is read with [`link_target`](FsTree::link_target).
    Symlink,
    /// A character-special device node.
    CharDevice {
        /// Device major number.
        major: u32,
        /// Device minor number.
        minor: u32,
    },
    /// A block-special device node.
    BlockDevice {
        /// Device major number.
        major: u32,
        /// Device minor number.
        minor: u32,
    },
    /// A named pipe (FIFO).
    Fifo,
    /// A Unix-domain socket node.
    Socket,
}

/// One name in a directory: what it is called, what is there, and the family's own handle to
/// it — what [`FsTree::list`] hands back for each name, and [`FsTree::find`] for the one a path
/// ends at.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct Child<N> {
    /// The name. For a name [`FsTree::list`] hands back, it is the one the directory stores.
    /// For the node [`FsTree::find`] reaches, it is the last component of the path as the
    /// caller wrote it: the caller's spelling where a family compares names without case, `..`
    /// or `.` where the path ends in one, and empty for the root and for a path of separators
    /// alone. A separator at the end of a path ends no component.
    pub name: Vec<u8>,
    /// What is there.
    pub kind: NodeKind,
    /// The family's own handle to it, which the by-node operations take.
    pub node: N,
}

impl<N> Child<N> {
    /// A name `name`, holding `kind`, reached through `node`.
    pub fn new(name: Vec<u8>, kind: NodeKind, node: N) -> Self {
        Self { name, kind, node }
    }
}

/// How much room a filesystem has, counted in the unit it allocates in.
///
/// The count is the filesystem's own account of itself, read from what it records: each family
/// documents at [`FsTree::usage`] where its numbers come from.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct Usage {
    /// Bytes one unit holds: the block, the cluster, or the sector the format allocates in.
    pub unit: u64,
    /// How many units the filesystem holds.
    pub total: u64,
    /// How many of them are not allocated to anything, by the filesystem's own account. Where
    /// a format stores some blocks more than once, its account may count each once; each
    /// family's [`FsTree::usage`] says which account it reads.
    pub free: u64,
}

impl Usage {
    /// `total` units of `unit` bytes, `free` of them unallocated.
    pub fn new(unit: u64, total: u64, free: u64) -> Self {
        Self { unit, total, free }
    }
}

/// The names a listing hands back, out of a directory's entries: `.` and `..` left out, every
/// other name held to the rule a walk holds a name to, and the rest in byte order of their
/// names.
///
/// The one place a listing's names are decided, for every family: what a walk would refuse to
/// make a path of is refused here too, so a caller resolving a name it was listed reaches what
/// a walk reaches.
#[cfg(any(
    feature = "ext",
    feature = "fat",
    feature = "exfat",
    feature = "btrfs",
    feature = "apfs"
))]
pub(crate) fn listed<T>(
    family: Family,
    entries: impl IntoIterator<Item = (Vec<u8>, T)>,
) -> Result<Vec<(Vec<u8>, T)>, TreeError> {
    let mut out = Vec::new();
    for (name, keep) in entries {
        if crate::path::is_dot_entry(&name) {
            continue;
        }
        if crate::path::is_hostile_component(&name) {
            return Err(TreeError::Malformed {
                family,
                detail: format!(
                    "a directory entry carries a name no directory can hold: {}",
                    crate::escape::printable(&name)
                ),
            });
        }
        out.push((name, keep));
    }
    out.sort_by(|a, b| a.0.cmp(&b.0));
    Ok(out)
}

/// The name a path ends at, as [`FsTree::find`] reports it: its last component, empty for the
/// root.
#[cfg(any(
    feature = "ext",
    feature = "fat",
    feature = "exfat",
    feature = "btrfs",
    feature = "apfs"
))]
pub(crate) fn last_name(path: &[u8]) -> Vec<u8> {
    crate::path::canonical_parts(path)
        .last()
        .map_or_else(Vec::new, |name| name.to_vec())
}

/// A node `find` resolved that is not a directory, handed to `list`, as every family refuses it.
#[cfg(any(
    feature = "ext",
    feature = "fat",
    feature = "exfat",
    feature = "btrfs",
    feature = "apfs"
))]
pub(crate) fn not_a_directory(family: Family) -> TreeError {
    TreeError::Malformed {
        family,
        detail: "the node is not a directory".to_string(),
    }
}

/// One name a walk reached: where it is, what is there, and the family's own handle to it.
///
/// The handle is what the three by-node operations take, so a family hands back whatever it
/// already has — an inode for ext, a directory entry for FAT — and a sink never re-resolves
/// a path it was just given.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct TreeEntry<N> {
    /// Absolute path from the filesystem root, `/`-joined, always beginning with `/`.
    /// Empty for the root itself, which is the first entry a walk yields.
    pub path: Vec<u8>,
    /// What is at the path.
    pub kind: NodeKind,
    /// The node's identity, when the family says it may be reached by more than one name.
    ///
    /// Two entries carrying the same value are two names for one node — a hard link — and
    /// a sink writes the second as a link to the first rather than copying the contents.
    /// `None` where the family has no notion of a second name for one node, and where it
    /// has one but this node has only one name, which is what keeps a sink's table down to
    /// the tree's actual links rather than a path per file in it.
    pub shared: Option<u64>,
    /// The family's own handle to the node.
    pub node: N,
}

impl<N> TreeEntry<N> {
    /// An entry at `path` holding `kind`, reached through `node`, with no second name.
    #[must_use]
    pub fn new(path: Vec<u8>, kind: NodeKind, node: N) -> Self {
        Self {
            path,
            kind,
            shared: None,
            node,
        }
    }

    /// Declare that the node may be reached by more than one name, under the identity `id`.
    #[must_use]
    pub fn shared(mut self, id: u64) -> Self {
        self.shared = Some(id);
        self
    }
}

/// Everything a sink records about one node beyond what the walk carried.
///
/// Complete whichever family produced it: a sink writing a host file needs an owner, a
/// mode, and times, and a family with no field for one fills it from the caller's
/// [`Synthesis`] rather than leaving a hole. [`synthesized`](Self::synthesized) is what
/// says which of them that happened to.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct Attributes {
    /// Ownership, permission bits, and the three times.
    pub meta: Metadata,
    /// The node's extended attributes, empty for a node with none and for a family that
    /// has no such thing. Each value is in the boundary form [`Xattr`] describes, whatever
    /// the family stored it as.
    pub xattrs: Vec<Xattr>,
    /// The properties in `meta` that the family invented rather than read, because its
    /// format has no field for them. Empty for a family that records everything, which
    /// costs nothing.
    pub synthesized: Vec<Property>,
}

impl Attributes {
    /// Attributes read whole from the filesystem, with nothing invented.
    #[must_use]
    pub fn read(meta: Metadata, xattrs: Vec<Xattr>) -> Self {
        Self {
            meta,
            xattrs,
            synthesized: Vec::new(),
        }
    }

    /// What a [`stat`](FsTree::stat) answers on a family whose whole record of a node is a
    /// read-only bit and three times.
    ///
    /// This is the read-side mirror of
    /// [`LossPolicy::record_losses`](crate::fidelity::LossPolicy), which is the one place
    /// that says what such a format *drops*. The two families in that class lose the same
    /// six properties for the same reason and invent the same four back, so both answers
    /// have one home and neither can gain a clause the other does not.
    ///
    /// `times` is `(access, modification, birth)`, or `None` for a node the format stores no
    /// entry for — the root directory on both families, which therefore has no times at all
    /// rather than invented ones. The access and birth times are `None` where the entry records
    /// that one was not kept. There is no change time in either format, so the modification
    /// time stands for it, and for an access time not kept: it is the closest thing the volume
    /// records, and the alternative is a value invented out of nothing.
    ///
    /// The read-only bit is the single permission bit either format holds, and it clears the
    /// write bits of whatever mode the caller named. The other eight still came from the
    /// caller and nothing in the volume speaks to them, which is why the mode is named as
    /// invented either way.
    #[cfg(any(feature = "fat", feature = "exfat"))]
    pub(crate) fn from_read_only_bit(
        synthesis: &Synthesis,
        is_dir: bool,
        read_only: bool,
        times: Option<(
            Option<crate::time::Timestamp>,
            crate::time::Timestamp,
            Option<crate::time::Timestamp>,
        )>,
    ) -> Self {
        let mut mode = if is_dir {
            synthesis.dir_mode
        } else {
            synthesis.file_mode
        };
        if read_only {
            mode &= !crate::fidelity::WRITE_BITS;
        }
        let zero = crate::time::Timestamp::from_secs(0);
        let (atime, mtime, btime) = times.unwrap_or((None, zero, None));
        let mut synthesized = vec![
            Property::Ownership,
            Property::Permissions,
            Property::ChangeTime,
        ];
        // An access time the volume did not keep is the modification time, as the change time
        // the format has no field for is.
        if atime.is_none() {
            synthesized.push(Property::AccessTime);
        }
        if times.is_none() {
            synthesized.push(Property::ModificationTime);
        }
        let atime = atime.unwrap_or(mtime);
        Self {
            meta: Metadata {
                mode,
                uid: synthesis.uid,
                gid: synthesis.gid,
                atime,
                ctime: mtime,
                mtime,
                btime,
            },
            xattrs: Vec::new(),
            synthesized,
        }
    }
}

/// The operations an extraction, a lookup, and a listing need of a filesystem, whichever
/// family it is.
///
/// Implemented by each family's reader. A sink is written once against this and drains an
/// image of any family without a `match` and without knowing what it is draining.
///
/// The trait is deliberately narrow. It is not a general filesystem interface and is not
/// meant to grow into one: a question only one family can answer belongs on that family's
/// concrete reader, which a caller reaches by matching on what opening an image hands
/// back.
pub trait FsTree {
    /// The family's own handle to a node — an inode, a directory entry, whatever it
    /// already holds. A sink treats it as opaque and hands it back unchanged.
    type Node;

    /// Which family this reader is of, which is what a [`TreeError`] it produces names.
    fn family(&self) -> Family;

    /// The cap a read through this reader is held to — the caller's
    /// [`Limits::max_file_bytes`](crate::Limits::max_file_bytes), which defaults to no cap
    /// at all.
    ///
    /// The reader answers rather than the caller because the limits are the ones the
    /// reader was opened under, and a sink draining it never saw them.
    fn max_file_bytes(&self) -> u64;

    /// Walk every name in the tree, calling `visit` for each.
    ///
    /// The root comes first, under the empty path, so a sink that has to apply the root's
    /// own metadata does not need a second way to reach it. After that the order is
    /// depth-first with a parent before its children and siblings in a deterministic order,
    /// which is what lets a sink hold one open handle per directory on the current path
    /// rather than one per directory in the tree.
    ///
    /// The visitor is handed the reader back, so it can stat, read, and resolve while the
    /// walk is in progress and nothing has to be gathered up front. The error type is the
    /// visitor's, so a sink's own failures and the filesystem's stop the walk as
    /// themselves.
    ///
    /// # Errors
    ///
    /// Whatever the visitor returns, and a [`TreeError`] converted into it when the
    /// filesystem cannot be walked.
    fn walk_tree<E, F>(&mut self, visit: F) -> Result<(), E>
    where
        E: From<TreeError>,
        F: FnMut(&mut Self, TreeEntry<Self::Node>) -> Result<(), E>;

    /// Everything recorded about one node: its ownership, mode, and times, and its extended
    /// attributes.
    ///
    /// A property the family's format has no field for is filled from `synthesis` and named
    /// in [`Attributes::synthesized`], so what comes back is always complete and always
    /// says what in it was invented. A family that records a property ignores the
    /// corresponding input.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] if the node's metadata or attributes cannot be read.
    fn stat(&mut self, node: &Self::Node, synthesis: &Synthesis) -> Result<Attributes, TreeError>;

    /// Fill `buf` from `offset` in a regular file, returning how many bytes were placed.
    ///
    /// A short fill means the file ends there. Reading a whole file is a loop over this
    /// rather than one call, which is what keeps a sink's memory the size of its buffer
    /// instead of the size of the largest file in the tree.
    ///
    /// A node that is not a regular file holds no bytes, and this yields none of them: a
    /// directory's storage is its entries and a device node's is a pair of numbers, and
    /// handing either back as file contents would be a block pointer or a device number
    /// read as data. Every implementation answers that way, so a sink that asks gets the
    /// same nothing whichever family it is draining.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] if the file's bytes cannot be read.
    fn read_bytes(
        &mut self,
        node: &Self::Node,
        offset: u64,
        buf: &mut [u8],
    ) -> Result<usize, TreeError>;

    /// What a Darwin filesystem records of the node beyond what [`stat`](Self::stat)
    /// answers: its BSD flags, and a compressed file's content as stored. [`None`] on every
    /// family but those, which is every family's answer unless it says otherwise.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] if the node's record or its compressed form cannot be read.
    fn darwin(&mut self, node: &Self::Node) -> Result<Option<Darwin>, TreeError> {
        let _ = node;
        Ok(None)
    }

    /// The node's BSD flags, as [`darwin`](Self::darwin) answers them, without reading a
    /// compressed file's stored form: 0 on every family but a Darwin one.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] if the node's record cannot be read.
    fn bsd_flags(&mut self, node: &Self::Node) -> Result<u32, TreeError> {
        Ok(self.darwin(node)?.map_or(0, |darwin| darwin.bsd_flags))
    }

    /// A symbolic link's target, exactly as the filesystem records it.
    ///
    /// The target is reproduced as it stands — a link pointing at `/etc/passwd` or at
    /// `../../..` is that link, and reproducing it is what an extraction is for. Nothing
    /// here resolves it.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] if the target cannot be read. Calling it on a node that is not a
    /// symbolic link is a [`TreeError::Malformed`].
    fn link_target(&mut self, node: &Self::Node) -> Result<Vec<u8>, TreeError>;

    /// The node `path` names, resolved from the root the way the family's own `lookup`
    /// resolves it: through symbolic links in every component, the last one included, against
    /// the filesystem's own root.
    ///
    /// The [`Child`]'s name is the path's last component, empty for the root.
    ///
    /// # Errors
    ///
    /// [`TreeError::NotFound`] where the path names nothing, and a [`TreeError`] where what it
    /// passes through cannot be read.
    fn find(&mut self, path: &[u8]) -> Result<Child<Self::Node>, TreeError>;

    /// The names in directory `dir`, in byte order of their names, without `.` and `..`.
    ///
    /// Each name is one a walk would make a path of: one carrying a separator or a NUL, or
    /// standing for the directory itself or its parent, is refused rather than listed. Reading
    /// one directory reads that directory and the nodes it names, and nothing below them.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] where the directory or a node it names cannot be read. Calling it on a
    /// node that is not a directory is a [`TreeError::Malformed`].
    fn list(&mut self, dir: &Self::Node) -> Result<Vec<Child<Self::Node>>, TreeError>;

    /// How much room the filesystem has, by its own account.
    ///
    /// # Errors
    ///
    /// A [`TreeError`] where what the account is read from cannot be read.
    fn usage(&mut self) -> Result<Usage, TreeError>;

    /// Refuse a file whose declared length is past the cap this read is held to — the
    /// caller's [`Limits::max_file_bytes`](crate::Limits::max_file_bytes), which defaults to
    /// no cap at all.
    ///
    /// A sink asks so that the cap governs what an *extraction writes*, and not only what a
    /// whole-file read returns. Every sink here streams a file through a fixed buffer, so a
    /// sink's own memory is bounded whatever the file claims — but the bytes it writes are
    /// driven entirely by the size the image declares, and a hole reads back as zeros. An
    /// inode claiming sixteen tebibytes and mapping nothing therefore costs an extraction
    /// sixteen tebibytes of zeros written into the destination, from an image of a hundred
    /// kilobytes, with no setting a caller could reach that prevented it.
    ///
    /// The check is on the declared length and happens before a byte is written, so what a
    /// sink refuses is exactly what a whole-file read of the same node would refuse.
    ///
    /// The rule is one rule and the refusal is one sentence, so this is written here rather
    /// than once per family: what varies between them is the family in the message and the
    /// cap being applied, and both are asked for above.
    ///
    /// # Errors
    ///
    /// [`TreeError::LimitExceeded`] naming the path and the cap.
    // In a build with no family compiled in, [`Family`] has no variants, so `family()`
    // cannot return and everything after it here is unreachable. That build also has no
    // implementor of this trait, which is what makes the body dead rather than wrong. The
    // predicate names every family, so a build carrying any one of them reaches every line
    // here and carries no allowance hiding what the allowance was scoped to expose.
    #[cfg_attr(
        not(any(
            feature = "ext",
            feature = "fat",
            feature = "exfat",
            feature = "btrfs",
            feature = "apfs"
        )),
        allow(unreachable_code, unused_variables)
    )]
    fn check_file_size(&self, path: &[u8], size: u64) -> Result<(), TreeError> {
        let cap = self.max_file_bytes();
        if size > cap {
            return Err(TreeError::limit(
                self.family(),
                Bound::FileBytes,
                &format_args!(
                    "{}: the file is {size} bytes, more than the {cap}-byte cap this read is \
                     held to",
                    crate::escape::printable(path)
                ),
            ));
        }
        Ok(())
    }
}

/// Whether `path` is one `family`'s format makes for itself, which a sink and an image source
/// therefore leave out: `/lost+found` and everything under it, on an ext filesystem.
///
/// Every ext filesystem holds that directory from its first format, and the ext formatter
/// refuses a source that names it, so a tree carrying one is a tree that does not format back.
/// No other family's format makes one, and there a directory of that name is the volume's own,
/// written out like any other.
pub(crate) fn made_by_the_format(path: &[u8], family: Family) -> bool {
    #[cfg(feature = "ext")]
    if family == Family::Ext {
        return path == b"/lost+found" || path.starts_with(b"/lost+found/");
    }
    let _ = (family, path);
    false
}

/// The BSD flags of `node` an extraction does not carry, since no destination it writes holds
/// them: every one the node records but [`Darwin::COMPRESSED`], whose content a read decodes.
#[cfg(any(
    feature = "tar",
    all(feature = "dir", any(target_os = "linux", target_os = "android"))
))]
pub(crate) fn flags_not_carried<T: FsTree>(tree: &mut T, node: &T::Node) -> Result<u32, TreeError> {
    Ok(Darwin::new(tree.bsd_flags(node)?).stated_flags())
}

/// Every failure a walk through [`FsTree::walk_tree`] can have, kept apart until the walk
/// ends.
///
/// A family's walk carries one error type; a walk through this surface has three sources for
/// one — the filesystem's own, a node the shared frame cannot describe, and the visitor's,
/// which is the sink's. Collapsing them at the point they occur would report a sink's failure
/// as a fault in the image, so they ride separately for the length of the walk and are
/// unwrapped at the end.
///
/// `R` is the family's own read error. It is a parameter rather than a fixed type because the
/// conversion that makes `?` work on it — `From<R>` — is what each family writes for itself;
/// a blanket one here would collide with the reflexive `From<T> for T`.
///
/// Compiled where a family is: with none there is no tree to walk.
#[cfg(any(
    feature = "ext",
    feature = "fat",
    feature = "exfat",
    feature = "btrfs",
    feature = "apfs"
))]
pub(crate) enum WalkFail<R, E> {
    /// The filesystem's own failure, which the family's walk produced.
    Read(R),
    /// A node the walk reached that the shared frame cannot describe.
    ///
    /// A property of this surface rather than of any family, which is why every family's
    /// walk handles it. The ext, btrfs and APFS families produce one, for a mode naming no
    /// file type; every FAT and exFAT node is a directory or a file, and both are kinds the
    /// frame has.
    #[cfg_attr(
        not(any(feature = "ext", feature = "btrfs", feature = "apfs")),
        allow(dead_code)
    )]
    Tree(TreeError),
    /// The visitor's own failure, which is the sink's.
    Visitor(E),
}

#[cfg(test)]
mod tests {
    use super::{NodeKind, TreeEntry};

    #[test]
    fn an_entry_has_no_second_name_until_one_is_declared() {
        let entry = TreeEntry::new(b"/etc/hostname".to_vec(), NodeKind::File { size: 9 }, 12u32);
        assert_eq!(entry.shared, None);
        assert_eq!(entry.node, 12);
        // A node the family says has more than one name carries the identity the names
        // share, which is what lets a sink write the second as a link to the first.
        assert_eq!(entry.shared(12).shared, Some(12));
    }

    #[cfg(all(
        feature = "ext",
        any(
            feature = "tar",
            all(feature = "dir", any(target_os = "linux", target_os = "android"))
        )
    ))]
    #[test]
    fn lost_and_found_is_the_formats_own_on_ext_with_its_contents() {
        use super::made_by_the_format;
        use crate::finding::Family;
        assert!(made_by_the_format(b"/lost+found", Family::Ext));
        assert!(made_by_the_format(b"/lost+found/17", Family::Ext));
        // A name that merely begins the same way is a different file.
        assert!(!made_by_the_format(b"/lost+found-old", Family::Ext));
        assert!(!made_by_the_format(b"/etc/lost+found", Family::Ext));
    }

    #[cfg(all(
        any(feature = "fat", feature = "exfat", feature = "btrfs"),
        any(
            feature = "tar",
            all(feature = "dir", any(target_os = "linux", target_os = "android"))
        )
    ))]
    #[test]
    fn lost_and_found_is_the_volumes_own_where_the_format_makes_none() {
        use super::made_by_the_format;
        use crate::finding::Family;
        #[cfg(feature = "fat")]
        assert!(!made_by_the_format(b"/lost+found", Family::Fat));
        #[cfg(feature = "exfat")]
        assert!(!made_by_the_format(b"/lost+found/kept", Family::ExFat));
        #[cfg(feature = "btrfs")]
        assert!(!made_by_the_format(b"/lost+found", Family::Btrfs));
    }
}