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
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
//! Opening a btrfs and reaching its trees: the superblock and its copies, the chunk map built
//! through the bootstrap, and every tree block fetched and verified through that one map.
//!
//! This is the layer the filesystem view stands on. It knows about addresses, blocks, and
//! trees, and nothing about files: what an item *means* is decided by whoever asked for it.
//!
//! # What opening does, in order
//!
//! 1. Read every superblock location the source reaches, and judge each one — is it there, is
//!    it a superblock, does its checksum cover it, and does it agree about where it lives.
//! 2. Choose the copy at the highest generation, which is the filesystem's own rule for which
//!    of them is live. Where the primary verifies, only copies of its filesystem inside its
//!    device compete.
//! 3. Refuse what cannot be read at all: a filesystem spanning several devices, a checksum
//!    algorithm the format does not define, a feature bit this crate does not implement, a
//!    geometry the format does not define.
//! 4. Judge the copies that were *not* chosen against the device's own length and against the
//!    chosen one, so a missing or stale one, or one at the live generation that is not a copy
//!    of the live record, is reported rather than passed over.
//! 5. Load the bootstrap array, translate the chunk root through it, and read the chunk tree —
//!    which completes the map every read above this point goes through.
//!
//! This module does I/O.

use std::collections::BTreeMap;
use std::io::{Read, Seek, SeekFrom};
use std::sync::Arc;

use crate::cache::BlockCache;
use crate::compress::Algorithm;
use crate::io::{Bounded, io_error, offset_of, read_exact_at, read_exact_into};
use crate::{Limits, OpenOptions, ReadPolicy};

use super::ChunkMap;
use super::btree::Tree;
use super::ondisk::{
    self, ChecksumType, Chunk, DiskKey, Header, IncompatFlags, ItemType, MAX_BLOCK_SIZE, MAX_LEVEL,
    MIN_BLOCK_SIZE, MIRRORS, ParseError, RootItem, SUPER_INFO_SIZE, SuperBlock, holds_mirror,
    objectid,
};

/// Every `incompat` bit this crate understands well enough to read a filesystem carrying it.
///
/// A bit outside this set is a hard refusal by name, which is what the word means: the format
/// is telling a reader in advance that it will not understand what follows. The list is short
/// on purpose and grows with the code that earns each entry.
///
/// `MIXED_BACKREF`, `BIG_METADATA`, `EXTENDED_IREF`, `SKINNY_METADATA` and `NO_HOLES` are the
/// five the pinned baseline sets with no options at all. `DEFAULT_SUBVOL` and `METADATA_UUID`
/// change which subvolume is mounted and which id a tree block carries, both of which this
/// layer already reads.
///
/// **Two of the entries depend on what this build carries**, and that is the one place this
/// list is not fixed. A filesystem that sets a compression bit says some extent of it is
/// stored that way, so whether it can be read at all is whether this build has the decoder —
/// which makes each bit exactly as supported as its Cargo feature, `lzo` and `zstd`. The
/// remaining algorithm sets no bit, because every reader of this format has always understood
/// it, so a filesystem using it opens either way and it is the *file* that cannot be read
/// without the decoder.
pub const SUPPORTED_INCOMPAT: IncompatFlags = IncompatFlags::from_bits(
    IncompatFlags::MIXED_BACKREF.bits()
        | IncompatFlags::DEFAULT_SUBVOL.bits()
        | IncompatFlags::BIG_METADATA.bits()
        | IncompatFlags::EXTENDED_IREF.bits()
        | IncompatFlags::SKINNY_METADATA.bits()
        | IncompatFlags::NO_HOLES.bits()
        | IncompatFlags::METADATA_UUID.bits()
        | decodable_compression_bits(),
);

/// The `incompat` bits that say an extent is compressed, each with the algorithm it names.
const COMPRESSION_BITS: [(IncompatFlags, Algorithm); 2] = [
    (IncompatFlags::COMPRESS_LZO, Algorithm::Lzo),
    (IncompatFlags::COMPRESS_ZSTD, Algorithm::Zstd),
];

/// The [`COMPRESSION_BITS`] whose decoder this build carries.
const fn decodable_compression_bits() -> u64 {
    let mut bits = 0;
    let mut i = 0;
    while i < COMPRESSION_BITS.len() {
        let (flag, algorithm) = COMPRESSION_BITS[i];
        if algorithm.available() {
            bits |= flag.bits();
        }
        i += 1;
    }
    bits
}

/// What a refusal of `incompat` bits adds for each one that names a compression algorithm: the
/// feature that compiles its decoder. A build refuses such a bit only for want of that.
struct DecodersFor(u64);

impl std::fmt::Display for DecodersFor {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (flag, algorithm) in COMPRESSION_BITS {
            if self.0 & flag.bits() != 0 {
                write!(f, "{}", crate::compress::CompiledBy(Some(algorithm)))?;
            }
        }
        Ok(())
    }
}

/// What was found at one of the three superblock locations.
///
/// Every copy is judged whether or not it is the one used, because a filesystem whose copies
/// disagree is a filesystem something went wrong on — and the account of *how* they disagree
/// is what a caller needs to tell a torn write from an image carved out at the wrong offset.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum Mirror {
    /// The device is not long enough to hold this copy, so the format wrote none. Not a
    /// fault: the rule is every copy the device has room for, and a small filesystem has room
    /// for one or two.
    OutsideDevice,
    /// The device's own recorded length reaches this copy and the source does not, so the
    /// image in hand is shorter than the filesystem it holds.
    Truncated,
    /// The bytes are readable and are not a superblock.
    Absent,
    /// A superblock whose checksum does not cover it.
    Damaged,
    /// A superblock that records a different location as its own, which is what an image
    /// carved out of a disk at the wrong offset looks like — the checksum still verifies,
    /// because the address it disagrees about is inside what the checksum covers.
    Misplaced {
        /// The location the copy believes it lives at.
        bytenr: u64,
    },
    /// A superblock, at the transaction it records.
    Present {
        /// The transaction that wrote it. The highest across the copies is the live one.
        generation: u64,
    },
    /// A superblock at the live transaction that is not a copy of the live one: outside its
    /// checksum and the location it records as its own, its bytes differ.
    ///
    /// Every copy a transaction writes is the same record but for those two fields, so one
    /// that differs anywhere else at the same generation describes another filesystem, or
    /// this one inconsistently — a checksum that covers it says only that it is intact.
    Diverged {
        /// The transaction it records, which is the live one.
        generation: u64,
    },
    /// A superblock of another filesystem: its filesystem identifier is not the primary
    /// copy's. A filesystem written over the start of a device that held another leaves that
    /// one's copies wherever the new one wrote none of its own, at a generation of its own.
    Foreign,
}

impl Mirror {
    /// The transaction this copy was written by, or [`None`] where there is no copy to ask.
    #[must_use]
    pub const fn generation(self) -> Option<u64> {
        match self {
            Mirror::Present { generation } => Some(generation),
            _ => None,
        }
    }
}

/// Where one tree begins, and which tree it is.
///
/// The superblock supplies two of these directly and the root tree supplies the rest, so this
/// is the one currency in which a tree is named however it was found.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct TreeRoot {
    /// Which tree — one of [`objectid`]'s named values, or a subvolume's own id.
    pub objectid: u64,
    /// The logical address of the tree's top block.
    pub bytenr: u64,
    /// The height of that block, zero where the whole tree is one leaf.
    pub level: u8,
    /// The transaction that wrote it.
    pub generation: u64,
}

/// A btrfs image opened over a seekable source: its superblock, its address space, and its
/// trees.
///
/// This is the layer below a filesystem view. It hands back tree blocks, verified, at logical
/// addresses — which is what every part of a btrfs is addressed by, files included.
///
/// ```no_run
/// use ferrosys::btrfs::{Volume, ondisk::objectid};
///
/// let mut volume = Volume::open(std::fs::File::open("root.img")?)?;
/// // Every tree the filesystem has, found through the root tree.
/// for root in volume.tree_roots()? {
///     let items = volume.tree(root).count_items()?;
///     println!("{:>16}: {items} items", objectid::name(root.objectid).unwrap_or("subvolume"));
/// }
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub struct Volume<R> {
    /// The source, ending where the caller's region does.
    src: Bounded<R>,
    base: u64,
    policy: ReadPolicy,
    limits: Limits,
    /// Boxed, because it is not a header — it is 4096 bytes, two kibibytes of which are the
    /// bootstrap chunk array. Held by value it would make every reader of this family an
    /// order of magnitude larger than every other family's, and the enum that holds one of
    /// each is as large as its largest variant.
    superblock: Box<SuperBlock>,
    mirrors: [Mirror; MIRRORS.len()],
    chunks: ChunkMap,
    /// Tree blocks already read and verified. See [`TREE_CACHE_BYTES`].
    cache: BlockCache<TreeBlock>,
    /// Tree blocks read through a later copy. See [`read_through`](Self::read_through).
    read_through: BTreeMap<u64, ReadThrough>,
    /// Chunks the chunk tree maps differently from the bootstrap array, under a lenient read.
    /// See [`bootstrap_conflicts`](Self::bootstrap_conflicts).
    bootstrap_conflicts: Vec<u64>,
    /// The bytes the source holds from `base` on, measured at open through the caller's
    /// region. See [`source_bytes`](Self::source_bytes).
    source_bytes: u64,
}

/// A tree block whose first copy failed its checks and which a lenient read took from a later
/// one.
#[derive(Clone, PartialEq, Eq, Debug)]
pub(super) struct ReadThrough {
    /// The copy it was read through, counted from zero in the chunk's stripe order.
    pub(super) copy: usize,
    /// What the first copy failed.
    pub(super) fault: String,
}

impl<R: Read + Seek> Volume<R> {
    /// Open the filesystem at the start of `src`, strictly, with the default limits.
    ///
    /// # Errors
    ///
    /// See [`open_with`](Self::open_with).
    pub fn open(src: R) -> Result<Self, ReadError> {
        Self::open_with(src, OpenOptions::new())
    }

    /// Open the filesystem `options.base` bytes into `src`.
    ///
    /// # Errors
    ///
    /// [`ReadError::NotBtrfs`] where no location carries a superblock at all, and one of the
    /// refusals in [`ReadError`] where a filesystem is there and cannot be read: a checksum
    /// that does not cover its superblock, a feature bit nothing here implements, a
    /// multi-device filesystem this image is one device of, a geometry the format does not
    /// define, or a chunk tree that does not describe an address space.
    ///
    /// Under [`ReadPolicy::Strict`] a copy of the superblock that the device has room for and
    /// that is missing, damaged, misplaced, behind the chosen one, of another filesystem, or at
    /// its generation without being a copy of it is also a refusal.
    /// Under [`ReadPolicy::Lenient`] every one of those is recorded in
    /// [`mirrors`](Self::mirrors) and the filesystem opens.
    pub fn open_with(src: R, options: OpenOptions) -> Result<Self, ReadError> {
        let base = options.base;
        let mut src = Bounded::new(src, base, options.len);
        let mut found = [Mirror::Absent; MIRRORS.len()];
        let mut candidates: [Option<SuperBlock>; MIRRORS.len()] = [None, None, None];
        // Each candidate's bytes, so the copies that were not chosen can be held against the
        // one that was.
        let mut records: [Option<Vec<u8>>; MIRRORS.len()] = [None, None, None];

        for (index, &at) in MIRRORS.iter().enumerate() {
            // Through the shared addressing rather than by hand: `base` is a caller's and
            // `at` is the format's, and a sum that wrapped would read a superblock out of a
            // small offset the wrap landed on rather than failing.
            let Some(offset) = offset_of(base, at, 1) else {
                found[index] = Mirror::Truncated;
                continue;
            };
            let bytes = match read_exact_at(&mut src, offset, SUPER_INFO_SIZE) {
                Ok(bytes) => bytes,
                // A source that does not reach this far says nothing yet: whether the copy
                // *should* be there is a question about the device's length, and the device's
                // length is a field of a superblock not yet chosen.
                Err(e) if e.kind() == std::io::ErrorKind::UnexpectedEof => {
                    found[index] = Mirror::Truncated;
                    continue;
                }
                Err(e) => return Err(e.into()),
            };
            let Ok(superblock) = SuperBlock::read_from(&bytes) else {
                found[index] = Mirror::Absent;
                continue;
            };
            if !checksum_holds(&bytes, superblock.csum_type) {
                found[index] = Mirror::Damaged;
                continue;
            }
            if superblock.bytenr != at {
                found[index] = Mirror::Misplaced {
                    bytenr: superblock.bytenr,
                };
                continue;
            }
            found[index] = Mirror::Present {
                generation: superblock.generation,
            };
            candidates[index] = Some(superblock);
            records[index] = Some(bytes);
        }

        // A primary copy that verifies names the filesystem: a copy competes with it only where
        // it is of the same filesystem and inside the device the primary describes. A
        // filesystem written over the start of a device that held another leaves that one's
        // copies past its own end and wherever it wrote none, at generations of their own —
        // observed, the pinned `mkfs.btrfs` leaves a copy at 256 GiB in place when it formats
        // a smaller filesystem on a larger device — and the newest of those is no copy of
        // this one. Where the primary does not verify, the copies are all there is.
        if let Some(primary) = &candidates[0] {
            let (fsid, device) = (primary.fsid, primary.dev_item.total_bytes);
            for (index, &at) in MIRRORS.iter().enumerate().skip(1) {
                let state = match &candidates[index] {
                    Some(_) if !holds_mirror(device, at) => Mirror::OutsideDevice,
                    Some(copy) if copy.fsid != fsid => Mirror::Foreign,
                    _ => continue,
                };
                found[index] = state;
                candidates[index] = None;
                records[index] = None;
            }
        }

        // The filesystem's own rule for which copy is live: the newest. Ties go to the
        // earliest location, which is the one every tool reads first.
        let chosen = candidates
            .iter()
            .enumerate()
            .filter_map(|(index, sb)| sb.as_ref().map(|sb| (index, sb)))
            .max_by_key(|(index, sb)| (sb.generation, std::cmp::Reverse(*index)))
            .map(|(index, _)| index);
        let Some(chosen) = chosen else {
            // Nothing usable. Which of the two things went wrong is worth telling apart: a
            // source with no btrfs in it is a different answer from a btrfs whose superblock
            // has been damaged, and a caller pointed at the wrong file wants the first.
            return Err(
                match found.iter().find(|m| {
                    !matches!(
                        m,
                        Mirror::Absent | Mirror::OutsideDevice | Mirror::Truncated
                    )
                }) {
                    Some(Mirror::Damaged) => ReadError::BadChecksum {
                        object: "superblock",
                        at: MIRRORS[0],
                    },
                    Some(&Mirror::Misplaced { bytenr }) => ReadError::MisplacedSuperblock {
                        expected: MIRRORS[0],
                        bytenr,
                    },
                    _ => ReadError::NotBtrfs,
                },
            );
        };
        let superblock = candidates[chosen]
            .take()
            .expect("the chosen copy was parsed");

        check_readable(&superblock)?;

        // A copy at the live generation is the live record but for its checksum and its own
        // location, which is how every transaction writes them. One that differs anywhere
        // else is not a copy of this filesystem's live state, however well its checksum
        // covers it.
        let live = records[chosen].take().expect("the chosen copy was read");
        for (index, record) in records.iter().enumerate() {
            if let (Some(record), Mirror::Present { generation }) = (record, found[index])
                && generation == superblock.generation
                && !same_record(record, &live)
            {
                found[index] = Mirror::Diverged { generation };
            }
        }

        // Now that the device's length is known, each location that is not a superblock can be
        // told apart: one the device has no room for was never written, and one it has room
        // for is missing.
        let device_bytes = superblock.dev_item.total_bytes;
        for (index, &at) in MIRRORS.iter().enumerate() {
            if !holds_mirror(device_bytes, at) {
                found[index] = Mirror::OutsideDevice;
            }
        }
        if options.policy == ReadPolicy::Strict {
            for (index, &state) in found.iter().enumerate() {
                let fault = match state {
                    Mirror::OutsideDevice => continue,
                    Mirror::Present { generation } if generation == superblock.generation => {
                        continue;
                    }
                    Mirror::Present { .. } => "a copy of the superblock is behind the live one",
                    Mirror::Truncated => "the source is shorter than the device it describes",
                    Mirror::Absent => "a copy of the superblock is missing",
                    Mirror::Damaged => "a copy of the superblock fails its checksum",
                    Mirror::Misplaced { .. } => {
                        "a copy of the superblock records another place as its own"
                    }
                    Mirror::Diverged { .. } => {
                        "a copy of the superblock at the live generation is not a copy of the \
                         live one"
                    }
                    Mirror::Foreign => "a copy of the superblock belongs to another filesystem",
                };
                return Err(ReadError::MirrorDisagreement {
                    mirror: index,
                    at: MIRRORS[index],
                    fault,
                });
            }
        }

        let bootstrap = superblock
            .sys_chunk_bytes()
            .ok_or(ReadError::BadBootstrap {
                at: 0,
                fault: "the recorded length of the bootstrap array is longer than the array",
            })?;
        let chunks = ChunkMap::from_bootstrap(bootstrap, superblock.dev_item.devid, device_bytes)?;

        let cache = tree_cache(superblock.nodesize);
        let source_bytes = src.seek(SeekFrom::End(0))?.saturating_sub(base);
        let mut volume = Self {
            src,
            base,
            policy: options.policy,
            limits: options.limits,
            superblock: Box::new(superblock),
            mirrors: found,
            chunks,
            cache,
            read_through: BTreeMap::new(),
            bootstrap_conflicts: Vec::new(),
            source_bytes,
        };
        volume.load_chunk_tree()?;
        Ok(volume)
    }

    /// The superblock the filesystem was opened through: the newest copy of it that verified.
    #[must_use]
    pub fn superblock(&self) -> &SuperBlock {
        &self.superblock
    }

    /// What was found at each of the three superblock locations, in the order [`MIRRORS`]
    /// gives them.
    ///
    /// A strict open has already refused anything but [`Mirror::OutsideDevice`] and a
    /// [`Mirror::Present`] at the live generation, so this is what a lenient open is for.
    #[must_use]
    pub fn mirrors(&self) -> &[Mirror; MIRRORS.len()] {
        &self.mirrors
    }

    /// The bytes the source holds from where the filesystem begins, measured at open, and
    /// ending where the caller's region does.
    ///
    /// A device recording more bytes than this is longer than its source, which a
    /// [`scan`](super::Reader::scan) reports. Opening does not refuse it unless a copy of the
    /// superblock falls in the missing part, which [`Mirror::Truncated`] records.
    #[must_use]
    pub fn source_bytes(&self) -> u64 {
        self.source_bytes
    }

    /// The map from logical addresses to places on the device, complete once the chunk tree
    /// has been read.
    #[must_use]
    pub fn chunk_map(&self) -> &ChunkMap {
        &self.chunks
    }

    /// How strictly this volume is being read.
    #[must_use]
    pub fn policy(&self) -> ReadPolicy {
        self.policy
    }

    /// The caps this volume was opened under.
    #[must_use]
    pub fn limits(&self) -> Limits {
        self.limits
    }

    /// How long one tree block is, which is the filesystem's node size.
    #[must_use]
    pub fn node_size(&self) -> u32 {
        self.superblock.nodesize
    }

    /// The root tree, whose items name every other tree.
    #[must_use]
    pub fn root_tree(&self) -> TreeRoot {
        TreeRoot {
            objectid: objectid::ROOT_TREE,
            bytenr: self.superblock.root,
            level: self.superblock.root_level,
            generation: self.superblock.generation,
        }
    }

    /// The chunk tree, which the bootstrap array exists to make reachable.
    #[must_use]
    pub fn chunk_tree(&self) -> TreeRoot {
        TreeRoot {
            objectid: objectid::CHUNK_TREE,
            bytenr: self.superblock.chunk_root,
            level: self.superblock.chunk_root_level,
            generation: self.superblock.chunk_root_generation,
        }
    }

    /// Every tree the filesystem has.
    ///
    /// Two of them come from the superblock and are first: **the root tree**, which holds no
    /// record of itself, and **the chunk tree**, which cannot be in the root tree since
    /// reading the root tree needs the chunk tree already. Every other tree — the extent,
    /// device, checksum, uuid, free-space and block-group trees, the top-level filesystem
    /// tree, and one per subvolume — follows in key order.
    ///
    /// # Errors
    ///
    /// Whatever reading the root tree does, and [`ReadError::BadRootItem`] where an item that
    /// should name a tree does not describe one.
    pub fn tree_roots(&mut self) -> Result<Vec<TreeRoot>, ReadError> {
        let mut roots = vec![self.root_tree(), self.chunk_tree()];
        let mut failure = None;
        let root_tree = self.root_tree();
        self.tree(root_tree).for_each_item(|key, data| {
            if key.kind != ItemType::ROOT_ITEM {
                return true;
            }
            match RootItem::read_from(data) {
                Ok(item) => {
                    roots.push(TreeRoot {
                        objectid: key.objectid,
                        bytenr: item.bytenr,
                        level: item.level,
                        generation: item.generation,
                    });
                    true
                }
                Err(e) => {
                    failure = Some(ReadError::BadRootItem {
                        objectid: key.objectid,
                        source: e,
                    });
                    false
                }
            }
        })?;
        match failure {
            Some(e) => Err(e),
            None => Ok(roots),
        }
    }

    /// A handle on one tree, for searching or iterating it.
    pub fn tree(&mut self, root: TreeRoot) -> Tree<'_, R> {
        Tree::new(self, root)
    }

    /// One tree block, fetched through the chunk map and checked before it is handed back.
    ///
    /// Four things are checked, and each catches a different way of arriving at the wrong
    /// bytes: the checksum covers what was read, the block says it lives where it was fetched
    /// from, it belongs to this filesystem, and its height is one the format defines. What
    /// `nritems` may be depends on what the block is being read *as*, so that bound is applied
    /// where the array is walked rather than here.
    ///
    /// # Errors
    ///
    /// [`ReadError::UnmappedLogical`] where the chunk map does not cover the address,
    /// [`ReadError::BadChecksum`] where the block's checksum does not cover it, and
    /// [`ReadError::BadTreeBlock`] for each of the other three.
    ///
    /// A block in a mirrored block group has a copy for each of its stripes. A strict read
    /// takes the first and refuses the block where it fails. A lenient read takes the next copy
    /// where one fails its checks, fails only where every copy does, and the filesystem's
    /// [`scan`](super::Reader::scan) names each block it read that way.
    pub fn read_block(&mut self, logical: u64) -> Result<TreeBlock, ReadError> {
        self.fetch(logical, None)
    }

    /// The tree block at `logical`, as a tree reaches it: [`read_block`](Self::read_block)'s
    /// checks, and one more — the block was written by transaction `generation`, which is
    /// what the root item or the parent's pointer that led here records for it.
    ///
    /// A block at the right address, with a checksum that covers it, can still be the wrong
    /// block: one from an earlier transaction, left at an address the filesystem has since
    /// written again, verifies exactly as the right one does. The generation is what tells
    /// them apart, so a copy at another one is a copy that failed its checks — a strict read
    /// refuses it, and a lenient one reads through to the next copy as it would for a bad
    /// checksum.
    pub(super) fn read_tree_block(
        &mut self,
        logical: u64,
        generation: u64,
    ) -> Result<TreeBlock, ReadError> {
        self.fetch(logical, Some(generation))
    }

    /// One tree block, checked, and checked to be from `generation` where one is expected.
    ///
    /// A block already held answers only where it is from the generation asked for: two
    /// pointers to one address that expect different transactions are a filesystem that does
    /// not describe itself consistently, and the copies are read again so the one asked for is
    /// judged on its own bytes rather than on whichever pointer reached the address first.
    fn fetch(&mut self, logical: u64, generation: Option<u64>) -> Result<TreeBlock, ReadError> {
        if let Some(block) = self.cache.get(logical)
            && generation.is_none_or(|expected| block.header.generation == expected)
        {
            return Ok(block.clone());
        }
        let len = u64::from(self.superblock.nodesize);
        let mut first: Option<ReadError> = None;
        for (copy, physical) in self.chunks.copies_of(logical, len)?.into_iter().enumerate() {
            match self.read_copy(logical, physical, len, generation) {
                Ok(block) => {
                    if let Some(fault) = first {
                        self.read_through.insert(
                            logical,
                            ReadThrough {
                                copy,
                                fault: fault.to_string(),
                            },
                        );
                    }
                    self.cache.insert(logical, block.clone());
                    return Ok(block);
                }
                // What a mirrored block group is for. Under a lenient read, a copy that fails
                // its own checks is read past to the next, and the scan names the block.
                Err(
                    fault @ (ReadError::BadChecksum { .. }
                    | ReadError::BadTreeBlock { .. }
                    | ReadError::WrongGeneration { .. }),
                ) if self.policy == ReadPolicy::Lenient => {
                    first.get_or_insert(fault);
                }
                Err(fault) => return Err(first.unwrap_or(fault)),
            }
        }
        Err(first.expect("a chunk has at least one copy, and each failed"))
    }

    /// One copy of the tree block at `logical`, read from `physical` and checked — against
    /// `generation` too, where one is expected.
    fn read_copy(
        &mut self,
        logical: u64,
        physical: u64,
        len: u64,
        generation: Option<u64>,
    ) -> Result<TreeBlock, ReadError> {
        let offset =
            offset_of(self.base, physical, 1).ok_or(ReadError::UnmappedLogical { logical, len })?;
        let bytes = read_exact_at(&mut self.src, offset, len as usize)?;

        if !checksum_holds(&bytes, self.superblock.csum_type) {
            return Err(ReadError::BadChecksum {
                object: "tree block",
                at: logical,
            });
        }
        let header = Header::read_from(&bytes)?;
        if header.bytenr != logical {
            return Err(ReadError::BadTreeBlock {
                logical,
                fault: "the block records another logical address as its own",
            });
        }
        if header.fsid != self.superblock.metadata_id() {
            return Err(ReadError::BadTreeBlock {
                logical,
                fault: "the block belongs to another filesystem",
            });
        }
        if header.level > MAX_LEVEL {
            return Err(ReadError::BadTreeBlock {
                logical,
                fault: "the block is at a height the format does not define",
            });
        }
        if let Some(expected) = generation
            && header.generation != expected
        {
            return Err(ReadError::WrongGeneration {
                logical,
                generation: header.generation,
                expected,
            });
        }
        Ok(TreeBlock {
            header,
            bytes: bytes.into(),
        })
    }

    /// Every tree block this volume has read through a later copy because an earlier one
    /// failed its checks, by logical address. Only a lenient read does that; a strict one
    /// refuses the block instead.
    pub(super) fn read_through(&self) -> &BTreeMap<u64, ReadThrough> {
        &self.read_through
    }

    /// The logical start of every chunk the chunk tree maps differently from the superblock's
    /// bootstrap array, which a lenient read keeps the bootstrap's mapping of: that mapping is
    /// the one that read the chunk tree, so it is the one known to reach it. A strict read
    /// refuses the filesystem instead. At most as many as the bootstrap array has room for.
    pub(super) fn bootstrap_conflicts(&self) -> &[u64] {
        &self.bootstrap_conflicts
    }

    /// Fill `buf` from a logical address, through the chunk map.
    ///
    /// This is the raw form of what [`read_block`](Self::read_block) does, and it exists
    /// because **a file's bytes carry nothing that identifies them**: no header saying where
    /// they live, no checksum inside the run. A data extent is verified by holding it against
    /// the checksum tree, which is a separate structure and a separate read, so this hands
    /// back the bytes at an address and says nothing about whether they are the right ones.
    ///
    /// The whole run must be inside one chunk, which is what the map guarantees for any extent
    /// a filesystem allocated: an extent never straddles a chunk boundary.
    ///
    /// # Errors
    ///
    /// [`ReadError::UnmappedLogical`] where the chunk map does not cover the whole run, and
    /// [`ReadError::Io`] where the source does not reach that far.
    pub fn read_at(&mut self, logical: u64, buf: &mut [u8]) -> Result<(), ReadError> {
        let len = buf.len() as u64;
        let physical = self.chunks.translate(logical, len)?;
        let offset =
            offset_of(self.base, physical, 1).ok_or(ReadError::UnmappedLogical { logical, len })?;
        // Straight into the caller's buffer: this is the per-sector step of a data verify,
        // where an allocating read would cost a fresh buffer per sector of the volume.
        read_exact_into(&mut self.src, offset, buf)?;
        Ok(())
    }

    /// Read the chunk tree through the bootstrap map, adding every chunk it names.
    ///
    /// This is the second half of the bootstrap: after it, the map covers the whole address
    /// space rather than only the part that holds the chunk tree.
    fn load_chunk_tree(&mut self) -> Result<(), ReadError> {
        let devid = self.superblock.dev_item.devid;
        let device_bytes = self.superblock.dev_item.total_bytes;
        // Gathered before insertion rather than inserted during the walk, because the walk
        // borrows the volume the map lives in — and because a chunk tree that turns out to
        // overlap itself should leave the bootstrap map intact rather than half-extended.
        let mut found = Vec::new();
        let mut failure = None;
        let chunk_tree = self.chunk_tree();
        self.tree(chunk_tree).for_each_item(|key, data| {
            if key.kind != ItemType::CHUNK_ITEM {
                return true;
            }
            match Chunk::read_from(data) {
                Ok(chunk) if data.len() >= chunk.encoded_len() => {
                    found.push((*key, chunk, data[..chunk.encoded_len()].to_vec()));
                    true
                }
                Ok(chunk) => {
                    failure = Some(ReadError::BadChunk {
                        logical: key.offset,
                        fault: "a chunk item declares more stripes than the item holds",
                    });
                    let _ = chunk;
                    false
                }
                Err(e) => {
                    failure = Some(e.into());
                    false
                }
            }
        })?;
        if let Some(e) = failure {
            return Err(e);
        }
        for (key, chunk, record) in found {
            // The bootstrap array carries a copy of the system chunks the chunk tree also
            // records, so meeting one again is the ordinary case rather than a conflict. The
            // repeated record is validated as every other record is, and then held against the
            // copy already mapped: the same mapping is skipped, and a different one is two
            // places for one address. A strict read refuses that; a lenient one keeps the
            // bootstrap's mapping, which is the one that has just read the chunk tree, and
            // the scan names the chunk. A record overlapping a mapping without starting where
            // it does is the overlap `insert` refuses.
            if let Some(existing) = self.chunks.chunk_at(key.offset)
                && existing.logical == key.offset
            {
                let repeated = ChunkMap::mapped(&key, &chunk, &record, devid, device_bytes)?;
                if repeated == *existing {
                    continue;
                }
                if self.policy == ReadPolicy::Strict {
                    return Err(ReadError::BadChunk {
                        logical: key.offset,
                        fault: "the chunk tree maps this chunk differently from the superblock's \
                                bootstrap array",
                    });
                }
                self.bootstrap_conflicts.push(key.offset);
                continue;
            }
            self.chunks
                .insert(&key, &chunk, &record, devid, device_bytes)?;
        }
        Ok(())
    }
}

/// How many bytes of tree blocks a volume holds once read: 1 MiB, which at the default 16 KiB
/// node is 64 blocks.
///
/// A tree is read from its root down, and every search of it passes through the same few
/// blocks at the top. Held, those are read and verified once, where a walk that looks each
/// entry up again would otherwise read and checksum the root of every tree it consults once
/// per lookup. A walk's searches move through the keys in order, so what it returns to is the
/// upper levels and the leaves it is working through, a few blocks per tree. Measured over a
/// tree of 24,000 files, a cache four or sixteen times this size reads no fewer blocks and
/// spends longer searching itself.
const TREE_CACHE_BYTES: usize = 1 << 20;

/// The cache a volume with `node_size` tree blocks holds: [`TREE_CACHE_BYTES`] of them, and
/// never fewer than sixty-four, so the largest node the format defines holds as many blocks
/// as the default does.
fn tree_cache(node_size: u32) -> BlockCache<TreeBlock> {
    BlockCache::within(TREE_CACHE_BYTES, node_size as usize, 64)
}

/// One tree block, checked and held whole.
///
/// A block is read entire because that is what its checksum covers: verifying it means having
/// every byte, so there is nothing to be gained by fetching an item at a time.
///
/// Cloning one is cheap: the bytes are shared, so a block held by the volume's cache and
/// handed to a caller is one copy of them.
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TreeBlock {
    header: Header,
    bytes: Arc<[u8]>,
}

impl TreeBlock {
    /// What the block says about itself.
    #[must_use]
    pub fn header(&self) -> &Header {
        &self.header
    }

    /// The block's bytes, the header included.
    #[must_use]
    pub fn bytes(&self) -> &[u8] {
        &self.bytes
    }

    /// How many items or child pointers the block claims, held to what it has room for.
    ///
    /// This is the one bound that cannot be applied when a block is fetched, because what a
    /// count *may* be depends on which of the two things the block holds — 25 bytes per item,
    /// 33 per child pointer — and that follows from the level.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadTreeBlock`] where the count is larger than the block could hold.
    pub fn count(&self) -> Result<usize, ReadError> {
        let each = if self.header.is_leaf() {
            ondisk::Item::SIZE
        } else {
            ondisk::KeyPtr::SIZE
        };
        let claimed = self.header.nritems as usize;
        let room = (self.bytes.len() - Header::SIZE) / each;
        if claimed > room {
            return Err(ReadError::BadTreeBlock {
                logical: self.header.bytenr,
                fault: "the block claims more entries than it has room for",
            });
        }
        Ok(claimed)
    }

    /// The child pointer at `index` of an internal node.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadTreeBlock`] where the block is a leaf or `index` is past its count.
    pub fn key_ptr(&self, index: usize) -> Result<ondisk::KeyPtr, ReadError> {
        if self.header.is_leaf() {
            return Err(ReadError::BadTreeBlock {
                logical: self.header.bytenr,
                fault: "a leaf holds items rather than child pointers",
            });
        }
        if index >= self.count()? {
            return Err(ReadError::BadTreeBlock {
                logical: self.header.bytenr,
                fault: "a child pointer past the block's own count",
            });
        }
        let at = Header::SIZE + index * ondisk::KeyPtr::SIZE;
        Ok(ondisk::KeyPtr::read_from(&self.bytes[at..])?)
    }

    /// The item at `index` of a leaf.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadTreeBlock`] where the block is a node or `index` is past its count.
    pub fn item(&self, index: usize) -> Result<ondisk::Item, ReadError> {
        if !self.header.is_leaf() {
            return Err(ReadError::BadTreeBlock {
                logical: self.header.bytenr,
                fault: "an internal node holds child pointers rather than items",
            });
        }
        if index >= self.count()? {
            return Err(ReadError::BadTreeBlock {
                logical: self.header.bytenr,
                fault: "an item past the block's own count",
            });
        }
        let at = Header::SIZE + index * ondisk::Item::SIZE;
        Ok(ondisk::Item::read_from(&self.bytes[at..])?)
    }

    /// Whether the leaf's items are packed the way the format packs them.
    ///
    /// A leaf's free space is one run in the middle: the item array grows forward from the
    /// header and the data grows backward from the end of the block, with no gap between one
    /// item's data and the next's. So the first item's data ends exactly at the end of the
    /// block and every later item's ends exactly where the one before it begins.
    ///
    /// **Bounding each item separately does not imply this**, and the difference is a defect
    /// class rather than a nicety: data moved within a leaf, with the offsets moved to match,
    /// leaves every item inside the block and every item pointing at bytes that are not its
    /// own. Nothing about a bound notices, and what a reader then hands back is one record's
    /// bytes under another record's key.
    ///
    /// A block that is not a leaf is packed vacuously, and answers so.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadItem`] naming the first item whose data does not abut its neighbour's,
    /// and whatever [`item`](Self::item) refuses.
    pub fn check_leaf_packing(&self) -> Result<(), ReadError> {
        if !self.header.is_leaf() {
            return Ok(());
        }
        let count = self.count()?;
        // Item offsets are measured from the end of the header, so the region they address is
        // the block less its header.
        let mut abuts = (self.bytes.len() - Header::SIZE) as u64;
        for index in 0..count {
            let item = self.item(index)?;
            let start = u64::from(item.offset);
            if start + u64::from(item.size) != abuts {
                return Err(ReadError::BadItem {
                    logical: self.header.bytenr,
                    index,
                    fault: "the item's data does not end where the item before it begins",
                });
            }
            abuts = start;
        }
        Ok(())
    }

    /// The key of entry `index`, whichever of the two things the block holds: an item's key in
    /// a leaf, a child pointer's in a node.
    ///
    /// # Errors
    ///
    /// Whatever [`item`](Self::item) or [`key_ptr`](Self::key_ptr) refuses.
    pub fn key_at(&self, index: usize) -> Result<DiskKey, ReadError> {
        if self.header.is_leaf() {
            Ok(self.item(index)?.key)
        } else {
            Ok(self.key_ptr(index)?.key)
        }
    }

    /// Hold the block's keys against each other and against the keys its parent records.
    ///
    /// Every key must be above the one before it, in a node as in a leaf: a search over a
    /// block that is not sorted lands in the wrong place and misses what is there, rather
    /// than failing. And a block below a parent sits where the parent's keys say it does —
    /// its first key is `first`, the key the parent records for it, and its last is below
    /// `below`, the key the parent records for the block after it, or the bound the parent
    /// itself sits under. A node's keys are what a search steers by, and a checksum covers a
    /// misrouting key as faithfully as a correct one: a key that does not match the block it
    /// leads to sends a lookup past files the filesystem holds, while a walk of every block
    /// in order meets each of them and sees nothing wrong.
    ///
    /// The root of a tree has no parent, and is held to no bound.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadTreeBlock`] naming which of the three does not hold, and whatever
    /// [`key_at`](Self::key_at) refuses.
    pub fn check_keys(
        &self,
        first: Option<DiskKey>,
        below: Option<DiskKey>,
    ) -> Result<(), ReadError> {
        let logical = self.header.bytenr;
        let count = self.count()?;
        let mut previous: Option<DiskKey> = None;
        for index in 0..count {
            let key = self.key_at(index)?;
            if previous.is_some_and(|last| key <= last) {
                return Err(ReadError::BadTreeBlock {
                    logical,
                    fault: "a key is not above the one before it",
                });
            }
            previous = Some(key);
        }
        if let Some(first) = first
            && (count == 0 || self.key_at(0)? != first)
        {
            return Err(ReadError::BadTreeBlock {
                logical,
                fault: "the block's first key is not the key its parent records for it",
            });
        }
        if let (Some(last), Some(below)) = (previous, below)
            && last >= below
        {
            return Err(ReadError::BadTreeBlock {
                logical,
                fault: "the block holds a key at or above the key its parent records for the \
                        block after it",
            });
        }
        Ok(())
    }

    /// The bytes of the item at `index`, bounded by the leaf that holds them.
    ///
    /// An item's data grows backward from the end of the block while the item array grows
    /// forward from the header, so two things must hold and both are checked: the data begins
    /// past the array, and it ends within the block. An item that failed either would
    /// otherwise be read out of the array describing it or out of whatever follows the block.
    ///
    /// **The arithmetic is done in 64 bits whatever the target's pointer width is.** Both
    /// fields are 32 bits, so their sum is bounded by 2³³ and cannot wrap a `u64` — where in
    /// `usize` it wraps on a 32-bit target and cannot on a 64-bit one, which would make this
    /// function's behaviour on a crafted leaf a property of the machine reading it and leave
    /// the difference invisible wherever development happens.
    ///
    /// # Errors
    ///
    /// [`ReadError::BadItem`] where the item's data is not inside the space a leaf leaves for
    /// it, and whatever [`item`](Self::item) refuses.
    pub fn item_data(&self, index: usize) -> Result<&[u8], ReadError> {
        let count = self.count()?;
        let item = self.item(index)?;
        let array_end = (Header::SIZE + count * ondisk::Item::SIZE) as u64;
        let start = Header::SIZE as u64 + u64::from(item.offset);
        let end = start + u64::from(item.size);
        if start < array_end {
            return Err(ReadError::BadItem {
                logical: self.header.bytenr,
                index,
                fault: "the item's data begins inside the array describing it",
            });
        }
        if end > self.bytes.len() as u64 {
            return Err(ReadError::BadItem {
                logical: self.header.bytenr,
                index,
                fault: "the item's data runs past the end of the block",
            });
        }
        // Both casts are inside the block's own length, which the check above established.
        Ok(&self.bytes[start as usize..end as usize])
    }
}

/// Whether an object's stored checksum covers the bytes it was read as.
///
/// The bytes are the ones that came off the device, never a value re-serialized through this
/// crate's own types: a structure whose coverage of a format is partial cannot reproduce a
/// foreign tool's bytes, and a verifier built on one would report every filesystem it did not
/// write as damaged.
///
/// A value the format does not define answers `false` — but a filesystem carrying one never
/// reaches here, because [`check_readable`] refuses it by its number at open.
fn checksum_holds(object: &[u8], csum_type: ChecksumType) -> bool {
    csum_type.holds(object)
}

/// Whether two superblock records are copies of one: the same bytes outside the checksum
/// field and the location each records as its own, which are the two fields every copy a
/// transaction writes has to itself.
fn same_record(a: &[u8], b: &[u8]) -> bool {
    let checksum = ondisk::CSUM_FIELD_LEN;
    let location = SuperBlock::BYTENR_OFFSET..SuperBlock::BYTENR_OFFSET + 8;
    a.len() == b.len()
        && a[checksum..location.start] == b[checksum..location.start]
        && a[location.end..] == b[location.end..]
}

/// Whether the filesystem this superblock describes is one this crate can read at all.
///
/// Each refusal names what it would take to read it rather than reporting an unexpected value,
/// because every one of these is a filesystem that is *fine* and simply beyond this reader.
fn check_readable(sb: &SuperBlock) -> Result<(), ReadError> {
    if sb.csum_type.digest_len().is_none() {
        return Err(ReadError::UnsupportedChecksum {
            csum_type: sb.csum_type.value(),
        });
    }
    let unsupported = sb.incompat_flags.without(SUPPORTED_INCOMPAT);
    if !unsupported.is_empty() {
        let mut names = String::new();
        unsupported.describe(&mut names);
        return Err(ReadError::UnsupportedFeatures {
            bits: unsupported.bits(),
            names,
        });
    }
    if sb.num_devices != 1 {
        return Err(ReadError::MultiDevice {
            num_devices: sb.num_devices,
        });
    }
    for (field, value) in [("sector size", sb.sectorsize), ("node size", sb.nodesize)] {
        if !(MIN_BLOCK_SIZE..=MAX_BLOCK_SIZE).contains(&value) || !value.is_power_of_two() {
            return Err(ReadError::BadGeometry {
                field,
                value: u64::from(value),
            });
        }
    }
    if sb.nodesize < sb.sectorsize {
        return Err(ReadError::BadGeometry {
            field: "node size, which is never smaller than the sector size",
            value: u64::from(sb.nodesize),
        });
    }
    // Against the id every tree block carries, not the one a person sees. The device record
    // lives in the chunk tree and belongs to the metadata; on a filesystem whose two ids are
    // one — which is every filesystem until somebody changes the visible one — the two readings
    // agree, and on one whose ids differ only this reading accepts it.
    if sb.dev_item.fsid != sb.metadata_id() {
        return Err(ReadError::BadSuperblock {
            fault: "the device it describes belongs to another filesystem",
        });
    }
    if sb.dev_item.total_bytes == 0 {
        return Err(ReadError::BadSuperblock {
            fault: "the device it describes has no length",
        });
    }
    if sb.root == 0 || sb.chunk_root == 0 {
        return Err(ReadError::BadSuperblock {
            fault: "a tree this filesystem cannot be read without has no root",
        });
    }
    Ok(())
}

/// What reading a btrfs can fail on.
///
/// The variants divide into three kinds, and the difference is what a caller should do about
/// each. **These bytes are not ours** is [`NotBtrfs`](Self::NotBtrfs) alone. **This filesystem
/// is beyond this reader** is [`UnsupportedFeatures`](Self::UnsupportedFeatures),
/// [`UnsupportedChecksum`](Self::UnsupportedChecksum),
/// [`UnsupportedProfile`](Self::UnsupportedProfile) and [`MultiDevice`](Self::MultiDevice) —
/// each names a filesystem that is entirely well-formed and says what it would take. Every
/// other variant is **this filesystem does not describe itself consistently**, and each names
/// the structure and the address that made it so.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ReadError {
    /// The source could not be read.
    #[error("i/o error ({kind:?}): {message}")]
    #[non_exhaustive]
    Io {
        /// How the failure classified itself.
        kind: std::io::ErrorKind,
        /// What it said.
        message: String,
    },
    /// No superblock location carries a btrfs signature.
    #[error("no btrfs superblock at any of the three locations the format defines")]
    NotBtrfs,
    /// An on-disk structure could not be recovered from the bytes holding it.
    #[error(transparent)]
    Parse(#[from] ParseError),
    /// A checksum did not cover the object it was read with.
    #[error("{object} at {at}: the checksum does not cover it")]
    #[non_exhaustive]
    BadChecksum {
        /// What was being read.
        object: &'static str,
        /// Where it was: a device offset for a superblock, a logical address for a block.
        at: u64,
    },
    /// The only superblock found records another location as its own.
    #[error("a superblock at {expected} records {bytenr} as its own location")]
    #[non_exhaustive]
    MisplacedSuperblock {
        /// Where it was read from.
        expected: u64,
        /// Where it says it lives.
        bytenr: u64,
    },
    /// Under a strict read, a copy of the superblock the device has room for is not a copy of
    /// the live one.
    #[error("superblock copy {mirror} at {at}: {fault}")]
    #[non_exhaustive]
    MirrorDisagreement {
        /// Which of the three locations, counting from zero.
        mirror: usize,
        /// Its byte offset within the device.
        at: u64,
        /// What is wrong with it.
        fault: &'static str,
    },
    /// The filesystem's checksums name an algorithm the format does not define.
    #[error("checksum algorithm {csum_type} is not one the format defines")]
    #[non_exhaustive]
    UnsupportedChecksum {
        /// The on-disk value.
        csum_type: u16,
    },
    /// The filesystem carries a feature whose on-disk form this crate does not implement.
    #[error(
        "unsupported incompatible features: {names} ({bits:#x}){}",
        DecodersFor(*.bits)
    )]
    #[non_exhaustive]
    UnsupportedFeatures {
        /// The bits that are not supported.
        bits: u64,
        /// Their names, or their positions where the format has not defined them.
        names: String,
    },
    /// The filesystem spans devices, so this image is a part of it rather than the whole.
    #[error("a filesystem of {num_devices} devices cannot be read from one image")]
    #[non_exhaustive]
    MultiDevice {
        /// How many devices it spans.
        num_devices: u64,
    },
    /// A chunk is replicated in a way that needs more than the device in hand, or in a way the
    /// format does not define.
    #[error(
        "the chunk at {logical} has a profile this crate cannot read from one device ({flags:#x})"
    )]
    #[non_exhaustive]
    UnsupportedProfile {
        /// The chunk's logical start.
        logical: u64,
        /// Its type-and-profile word.
        flags: u64,
    },
    /// A geometry field holds a value the format does not define.
    #[error("{field} is {value}, which the format does not define")]
    #[non_exhaustive]
    BadGeometry {
        /// Which field.
        field: &'static str,
        /// What it held.
        value: u64,
    },
    /// The superblock does not describe a filesystem consistently.
    #[error("superblock: {fault}")]
    #[non_exhaustive]
    BadSuperblock {
        /// What is wrong with it.
        fault: &'static str,
    },
    /// The bootstrap array does not frame the chunks it holds.
    #[error("the superblock's bootstrap chunk array, at byte {at}: {fault}")]
    #[non_exhaustive]
    BadBootstrap {
        /// How far into the array the framing failed.
        at: usize,
        /// What was wrong.
        fault: &'static str,
    },
    /// A chunk item does not describe a mapping.
    #[error("the chunk at {logical}: {fault}")]
    #[non_exhaustive]
    BadChunk {
        /// The chunk's logical start.
        logical: u64,
        /// What was wrong.
        fault: &'static str,
    },
    /// Two chunks claim the same logical address, so it has two mappings.
    #[error("two chunks map the logical address {logical}")]
    #[non_exhaustive]
    ChunkOverlap {
        /// Where they meet.
        logical: u64,
    },
    /// No chunk maps a logical address, or a run leaves the chunk that maps its start.
    #[error("no chunk maps {len} bytes at the logical address {logical}")]
    #[non_exhaustive]
    UnmappedLogical {
        /// The address.
        logical: u64,
        /// How many bytes were wanted there.
        len: u64,
    },
    /// A tree block was written by another transaction than the one its root item or its
    /// parent's pointer records for it.
    ///
    /// Its checksum, its address and its filesystem all verify, which is what makes this its
    /// own refusal: a block from an earlier transaction, left at an address the filesystem has
    /// since written again, is that shape exactly, and it is not the committed state.
    #[error(
        "the tree block at {logical} was written by transaction {generation}, and what points \
         at it records transaction {expected}"
    )]
    #[non_exhaustive]
    WrongGeneration {
        /// The block's logical address.
        logical: u64,
        /// The transaction its header records.
        generation: u64,
        /// The transaction the pointer to it records.
        expected: u64,
    },
    /// A tree block does not describe itself consistently.
    #[error("the tree block at {logical}: {fault}")]
    #[non_exhaustive]
    BadTreeBlock {
        /// The block's logical address.
        logical: u64,
        /// What was wrong.
        fault: &'static str,
    },
    /// An item's data is not inside the space its leaf leaves for it.
    #[error("item {index} of the leaf at {logical}: {fault}")]
    #[non_exhaustive]
    BadItem {
        /// The leaf's logical address.
        logical: u64,
        /// Which item.
        index: usize,
        /// What was wrong.
        fault: &'static str,
    },
    /// A root item does not say where its tree is.
    #[error("the root item for tree {objectid}: {source}")]
    #[non_exhaustive]
    BadRootItem {
        /// Which tree it should have named.
        objectid: u64,
        /// What went wrong recovering it.
        source: ParseError,
    },
    /// A descent reached a block it had already been to, so the tree is not a tree.
    #[error("the tree block at {logical} is reachable from itself")]
    #[non_exhaustive]
    TreeCycle {
        /// The block met twice.
        logical: u64,
    },
    /// A child is not one level below its parent, so the descent would not terminate.
    #[error("the tree block at {logical} is at level {level} below a parent at level {parent}")]
    #[non_exhaustive]
    BadTreeLevel {
        /// The child's logical address.
        logical: u64,
        /// The level it records.
        level: u8,
        /// The level of the block that pointed at it.
        parent: u8,
    },
    /// A read would have gathered more entries than the caller's limits allow.
    #[error("a walk of tree {objectid} reached the limit of {limit} entries")]
    #[non_exhaustive]
    TooManyEntries {
        /// Which tree.
        objectid: u64,
        /// The cap that stopped it.
        limit: usize,
    },
    /// The filesystem has no tree of that id, though something named one.
    #[error("the filesystem has no tree {objectid}")]
    #[non_exhaustive]
    MissingTree {
        /// The id that was named.
        objectid: u64,
    },
    /// A subvolume's tree holds no record of an inode something named.
    #[error("subvolume {tree} holds no inode {inode}")]
    #[non_exhaustive]
    MissingInode {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
    },
    /// A path traverses through, or a name was looked up inside, something that is not a
    /// directory.
    ///
    /// The path is the one the caller stated, which is the one it can act on — this format
    /// numbers its inodes per subvolume, so the inode the traversal stopped at names nothing to
    /// a caller. Empty where no path was involved: a directory read asked of a node that is not
    /// one.
    #[error("not a directory: {}", crate::escape::printable(.path))]
    #[non_exhaustive]
    NotADirectory {
        /// The path as given.
        path: Vec<u8>,
    },
    /// A link target was asked of something that is not a symbolic link.
    #[error("inode {inode} of subvolume {tree} is not a symbolic link")]
    #[non_exhaustive]
    NotASymlink {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
    },
    /// No such path.
    #[error("no such path: {}", crate::escape::printable(.path))]
    #[non_exhaustive]
    NotFound {
        /// The path that was asked for.
        path: Vec<u8>,
    },
    /// A name in a path, or one an image stores, is one no directory can hold.
    #[error("{} is not a name a directory can hold", crate::escape::printable(.name))]
    #[non_exhaustive]
    HostileName {
        /// The offending name.
        name: Vec<u8>,
    },
    /// A directory entry names a directory the tree already reaches by another name, or one
    /// of its own ancestors. A btrfs directory has one name and one parent, so the
    /// filesystem contradicts itself. A walk never descends into such a directory twice; a
    /// strict read refuses the filesystem for it, and a lenient one passes the repeat over.
    #[error(
        "a directory entry names directory inode {inode} of subvolume {tree}, which the tree \
         reaches by another name as well"
    )]
    #[non_exhaustive]
    RepeatedDirectory {
        /// The subvolume the directory is in.
        tree: u64,
        /// The directory's inode.
        inode: u64,
    },
    /// A directory entry names something that is neither an inode nor a subvolume.
    #[error("an entry of inode {inode} in subvolume {tree}: {fault} (item type {kind})")]
    #[non_exhaustive]
    BadDirEntry {
        /// The subvolume the directory is in.
        tree: u64,
        /// The directory's inode.
        inode: u64,
        /// What is wrong with it.
        fault: &'static str,
        /// The item type the entry's location named.
        kind: u8,
    },
    /// An extended attribute record does not frame as a name and a value.
    #[error("the extended attributes of inode {inode} in subvolume {tree} do not frame")]
    #[non_exhaustive]
    BadXattr {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
    },
    /// An extent record does not describe a run of the file it belongs to.
    #[error("the extent at offset {at} of inode {inode} in subvolume {tree}: {fault}")]
    #[non_exhaustive]
    BadExtent {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
        /// The file offset the record is keyed by.
        at: u64,
        /// What is wrong with it.
        fault: &'static str,
    },
    /// A file's bytes are compressed by an algorithm this build does not decode.
    #[error(
        "inode {inode} of subvolume {tree} is compressed with {}, which this build does not \
         decode{}",
        crate::btrfs::ondisk::Compression::from_u8(*.compression)
            .name()
            .unwrap_or("an algorithm the format has not defined"),
        crate::compress::CompiledBy(
            crate::btrfs::decode::algorithm(crate::btrfs::ondisk::Compression::from_u8(
                *.compression
            ))
            .flatten()
        )
    )]
    #[non_exhaustive]
    UnsupportedCompression {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
        /// The on-disk algorithm byte.
        compression: u8,
    },
    /// A file's bytes are compressed with an algorithm this build decodes, and the stream is
    /// not a well-formed one.
    ///
    /// Apart from [`UnsupportedCompression`](Self::UnsupportedCompression), because the two
    /// say opposite things about the filesystem: that one is a filesystem that is entirely
    /// sound and beyond this build, and this one is a filesystem whose bytes do not hold what
    /// they say they hold.
    #[error(
        "the extent at offset {at} of inode {inode} in subvolume {tree} does not decode: {fault}"
    )]
    #[non_exhaustive]
    BadCompressedExtent {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
        /// The file offset the record is keyed by.
        at: u64,
        /// What was wrong with it, in the decoder's own words.
        fault: String,
    },
    /// A file's bytes carry an encoding beyond compression, which no release of the format
    /// defines a value for and nothing here can undo.
    #[error(
        "inode {inode} of subvolume {tree} is encoded ({encryption}, {other}), which this crate \
         does not decode"
    )]
    #[non_exhaustive]
    UnsupportedEncoding {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
        /// The encryption byte.
        encryption: u8,
        /// The other-encoding word.
        other: u16,
    },
    /// A whole-file read was asked for a file longer than the caller's cap.
    #[error(
        "inode {inode} of subvolume {tree} is {size} bytes, more than the {cap}-byte cap this \
         read is held to"
    )]
    #[non_exhaustive]
    FileTooLarge {
        /// Which subvolume.
        tree: u64,
        /// Which inode.
        inode: u64,
        /// The file's declared length.
        size: u64,
        /// The cap that applied.
        cap: u64,
    },
    /// A walk of the filesystem's names would have yielded more than the caller's cap.
    ///
    /// Separate from [`TooManyEntries`](Self::TooManyEntries), which is a cap on one B-tree
    /// walk. A filesystem holds one tree per subvolume and a walk of its *names* crosses all of
    /// them, so the two are different quantities and a caller acting on either wants to know
    /// which it hit.
    #[error("a walk of this filesystem reached the limit of {limit} names")]
    #[non_exhaustive]
    WalkTooLarge {
        /// The cap that stopped it.
        limit: usize,
    },
    /// A data extent's bytes do not match the checksum the filesystem recorded for them.
    ///
    /// The one fault in this crate that no structural check could have found: every tree is
    /// well-formed, every metadata block verifies, and the bytes of a file are not the bytes
    /// that were written.
    #[error("the data at {logical} does not match the checksum recorded for it")]
    #[non_exhaustive]
    DataChecksum {
        /// The logical address of the sector that failed.
        logical: u64,
    },
    /// A file whose inode says its data is checksummed has a run with no checksum recorded.
    #[error("no checksum is recorded for the data at {logical}")]
    #[non_exhaustive]
    MissingDataChecksum {
        /// The logical address with no checksum.
        logical: u64,
    },
    /// A walk reached a name whose path is longer than the longest a walk builds, 4,096
    /// bytes, which is Linux's `PATH_MAX`.
    ///
    /// Nothing in the format bounds how deep a tree nests, so the tree is well-formed and this
    /// is a limit rather than damage: the shared surface reports it as
    /// [`TreeError::LimitExceeded`](crate::TreeError::LimitExceeded) with
    /// [`Bound::PathBytes`](crate::Bound::PathBytes), and a scan reads the tree whole.
    #[error("a path longer than this crate builds: {}", crate::escape::printable(.path))]
    #[non_exhaustive]
    PathTooLong {
        /// The path that was being built.
        path: Vec<u8>,
    },
    /// Resolving a path followed more symbolic links than
    /// [`MAX_SYMLINK_HOPS`](crate::MAX_SYMLINK_HOPS) allows.
    ///
    /// A cycle reaches it, and so does a chain that is merely long — which is the case that
    /// matters on an image this crate did not write, where the chain can be as long as somebody
    /// cared to make it.
    #[error("too many symbolic links resolving {}", crate::escape::printable(.path))]
    #[non_exhaustive]
    SymlinkLoop {
        /// The path that was being resolved.
        path: Vec<u8>,
    },
}

io_error!(ReadError);

/// The tree engine reaches into a volume's source and its map, and nothing outside this module
/// does.
impl<R: Read + Seek> Volume<R> {
    /// This volume with a cache of `capacity` tree blocks, empty, for the tests that compare
    /// what the source is asked for at one size against another.
    #[cfg(test)]
    pub(crate) fn with_cache_capacity(mut self, capacity: usize) -> Self {
        self.cache = BlockCache::new(capacity);
        self
    }

    /// The key a search may not go past, and the tree it belongs to — used by the engine to
    /// name a limit it hit.
    pub(super) fn walk_limit(&self) -> usize {
        self.limits.max_walk_entries
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::btrfs::ondisk::{CSUM_FIELD_LEN, CompatFlags, CompatRoFlags, DevItem, SuperFlags};

    #[test]
    fn a_refused_compression_names_the_feature_that_decodes_it() {
        // zstd: an algorithm the format defines, refused only by a build that left it out.
        let refused = ReadError::UnsupportedCompression {
            tree: 5,
            inode: 257,
            compression: 3,
        };
        assert_eq!(
            refused.to_string(),
            "inode 257 of subvolume 5 is compressed with zstd, which this build does not \
             decode; the `zstd` feature compiles its decoder"
        );
        // A value the format leaves undefined has no feature to name.
        let undefined = ReadError::UnsupportedCompression {
            tree: 5,
            inode: 257,
            compression: 0x7f,
        };
        assert_eq!(
            undefined.to_string(),
            "inode 257 of subvolume 5 is compressed with an algorithm the format has not \
             defined, which this build does not decode"
        );
    }

    #[test]
    fn a_refused_compression_bit_names_the_feature_that_decodes_it() {
        // The refusal a build without the zstd decoder gives a filesystem whose feature word
        // says it stores zstd extents: it is refused at open, before any file is read.
        let mut names = String::new();
        IncompatFlags::COMPRESS_ZSTD.describe(&mut names);
        let refused = ReadError::UnsupportedFeatures {
            bits: IncompatFlags::COMPRESS_ZSTD.bits(),
            names,
        };
        assert_eq!(
            refused.to_string(),
            "unsupported incompatible features: compress-zstd (0x10); the `zstd` feature \
             compiles its decoder"
        );
        // A bit no feature decodes names nothing more.
        let mut names = String::new();
        IncompatFlags::RAID56.describe(&mut names);
        let raid = ReadError::UnsupportedFeatures {
            bits: IncompatFlags::RAID56.bits(),
            names: names.clone(),
        };
        assert_eq!(
            raid.to_string(),
            format!("unsupported incompatible features: {names} (0x80)")
        );
        // And each compression bit is supported exactly when its decoder is compiled.
        for (flag, algorithm) in COMPRESSION_BITS {
            assert_eq!(
                SUPPORTED_INCOMPAT.contains(flag),
                algorithm.available(),
                "{flag:?}"
            );
        }
    }

    fn a_superblock() -> SuperBlock {
        let mut sb = SuperBlock {
            csum: [0; CSUM_FIELD_LEN],
            fsid: [0x11; 16],
            bytenr: MIRRORS[0],
            flags: SuperFlags::NONE,
            magic: ondisk::MAGIC,
            generation: 8,
            root: 30_605_312,
            chunk_root: 22_036_480,
            log_root: 0,
            total_bytes: 1 << 30,
            bytes_used: 163_840,
            root_dir_objectid: 6,
            num_devices: 1,
            sectorsize: 4096,
            nodesize: 16_384,
            stripesize: 4096,
            sys_chunk_array_size: 0,
            chunk_root_generation: 8,
            compat_flags: CompatFlags::NONE,
            compat_ro_flags: CompatRoFlags::NONE,
            incompat_flags: IncompatFlags::MIXED_BACKREF,
            csum_type: ChecksumType::CRC32C,
            root_level: 0,
            chunk_root_level: 0,
            log_root_level: 0,
            dev_item: DevItem {
                devid: 1,
                total_bytes: 1 << 30,
                bytes_used: 0,
                io_align: 4096,
                io_width: 4096,
                sector_size: 4096,
                ty: 0,
                generation: 0,
                start_offset: 0,
                dev_group: 0,
                seek_speed: 0,
                bandwidth: 0,
                uuid: [0xec; 16],
                fsid: [0x11; 16],
            },
            label: [0; ondisk::LABEL_SIZE],
            cache_generation: 0,
            uuid_tree_generation: 0,
            metadata_uuid: [0; 16],
            nr_global_roots: 0,
            remap_root: 0,
            remap_root_generation: 0,
            remap_root_level: 0,
            sys_chunk_array: [0; ondisk::SYS_CHUNK_ARRAY_SIZE],
        };
        sb.sys_chunk_array_size = 0;
        sb
    }

    #[test]
    fn a_feature_bit_this_crate_does_not_implement_is_refused_by_name() {
        // The whole point of the incompatible word: the format is saying in advance that a
        // reader without the bit will misread what follows. Refusing it by name is what turns
        // the version drift this family expects into a message rather than a wrong read.
        let sb = SuperBlock {
            incompat_flags: IncompatFlags::MIXED_BACKREF | IncompatFlags::RAID_STRIPE_TREE,
            ..a_superblock()
        };
        let err = check_readable(&sb).expect_err("a stripe tree is not readable here");
        let ReadError::UnsupportedFeatures { bits, names } = err else {
            panic!("expected an unsupported-feature refusal, got {err:?}");
        };
        assert_eq!(bits, IncompatFlags::RAID_STRIPE_TREE.bits());
        // Named as `format -O` would take it, so a caller reading this refusal has the word
        // they would type to ask for such a filesystem.
        assert_eq!(names, "raid-stripe-tree");
        // And a bit the format grows after this release names its position rather than
        // vanishing, which is what makes the refusal readable.
        let future = SuperBlock {
            incompat_flags: IncompatFlags::from_bits(1 << 40),
            ..a_superblock()
        };
        let err = check_readable(&future).expect_err("a bit from the future");
        assert!(format!("{err}").contains("bit 40"), "{err}");
    }

    #[test]
    fn the_five_defaults_and_the_two_this_layer_reads_are_supported() {
        // The word the pinned baseline writes with no options at all, which must open.
        let sb = SuperBlock {
            incompat_flags: IncompatFlags::from_bits(0x361),
            ..a_superblock()
        };
        check_readable(&sb).expect("the baseline's default feature set");
        assert_eq!(SUPPORTED_INCOMPAT.bits() & 0x361, 0x361);
    }

    #[test]
    fn a_filesystem_that_spans_devices_is_refused_rather_than_read_as_a_part_of_itself() {
        let sb = SuperBlock {
            num_devices: 2,
            ..a_superblock()
        };
        assert!(matches!(
            check_readable(&sb),
            Err(ReadError::MultiDevice { num_devices: 2 })
        ));
    }

    #[test]
    fn a_geometry_the_format_does_not_define_is_refused_at_open() {
        for (sectorsize, nodesize) in [
            (2048, 16_384),  // below the floor
            (4096, 131_072), // above the ceiling
            (4096, 24_576),  // not a power of two
            (16_384, 4096),  // a node smaller than a sector
        ] {
            let sb = SuperBlock {
                sectorsize,
                nodesize,
                ..a_superblock()
            };
            assert!(
                matches!(check_readable(&sb), Err(ReadError::BadGeometry { .. })),
                "sector {sectorsize}, node {nodesize}"
            );
        }
        // And the range the pinned baseline accepts, at both ends.
        for size in [4096u32, 8192, 16_384, 32_768, 65_536] {
            let sb = SuperBlock {
                sectorsize: size,
                nodesize: size,
                ..a_superblock()
            };
            check_readable(&sb)
                .unwrap_or_else(|e| panic!("{size} is a size the format defines: {e}"));
        }
    }

    #[test]
    fn every_checksum_algorithm_the_format_defines_is_read_and_another_is_named() {
        // Each of the four is computed, so a filesystem checksummed by any of them opens.
        for value in [0u16, 1, 2, 3] {
            let sb = SuperBlock {
                csum_type: ChecksumType::from_value(value),
                ..a_superblock()
            };
            check_readable(&sb).unwrap_or_else(|e| panic!("checksum type {value}: {e}"));
        }
        // A value past them names no digest at all, and comparing bytes against one would
        // report every block of the filesystem as damaged, which says nothing true about it.
        for value in [4u16, 9, u16::MAX] {
            let sb = SuperBlock {
                csum_type: ChecksumType::from_value(value),
                ..a_superblock()
            };
            assert!(matches!(
                check_readable(&sb),
                Err(ReadError::UnsupportedChecksum { .. })
            ));
        }
    }

    #[test]
    fn a_superblock_describing_another_filesystems_device_is_refused() {
        let mut sb = a_superblock();
        sb.dev_item.fsid = [0x22; 16];
        assert!(matches!(
            check_readable(&sb),
            Err(ReadError::BadSuperblock { .. })
        ));
        // And one whose trees have no roots at all, which would otherwise fail one call later
        // with an unmapped address and no account of why.
        for sb in [
            SuperBlock {
                root: 0,
                ..a_superblock()
            },
            SuperBlock {
                chunk_root: 0,
                ..a_superblock()
            },
        ] {
            assert!(matches!(
                check_readable(&sb),
                Err(ReadError::BadSuperblock { .. })
            ));
        }
    }

    // ── Opening a forged filesystem: the copies of the superblock, and the policy over them ──

    use crate::btrfs::forge::{CHUNK_LOGICAL, CHUNK_TREE_AT, DEVICE_BYTES, Forge, ROOT_TREE_AT};

    /// Two mebibytes past the second location, so a forged device holds two copies and not
    /// three. Sparse, so it costs the pages it writes rather than its length.
    const TWO_MIRRORS: u64 = (64 << 20) + (2 << 20);

    /// A byte past the third location plus a whole superblock, which is where the count
    /// becomes three — the boundary that has two readings a superblock apart.
    const THREE_MIRRORS: u64 = (256 << 30) + SUPER_INFO_SIZE as u64;

    #[test]
    fn a_device_carries_every_copy_of_the_superblock_it_has_room_for_and_no_other() {
        // The mirror-count rule read back from the reader's side. The third location is a quarter of a
        // terabyte in, and the device the gate builds is sparse — so the boundary that costs
        // the tier with host tools a file the host may refuse to create costs nothing here.
        for (bytes, expected) in [(DEVICE_BYTES, 1), (TWO_MIRRORS, 2), (THREE_MIRRORS, 3)] {
            let volume = Volume::open(Forge::of_size(bytes).source())
                .unwrap_or_else(|e| panic!("a {bytes}-byte device: {e}"));
            let present = volume
                .mirrors()
                .iter()
                .filter(|m| matches!(m, Mirror::Present { .. }))
                .count();
            assert_eq!(present, expected, "a device of {bytes} bytes");
            assert!(
                volume.mirrors()[expected..]
                    .iter()
                    .all(|m| *m == Mirror::OutsideDevice),
                "every location past the last copy is outside the device"
            );
        }
    }

    #[test]
    fn a_copy_is_written_only_where_the_device_holds_all_of_it() {
        // "Large enough" has two readings and they differ by one copy: a device of exactly
        // the third location has no room for the superblock that would start there.
        let exact = Volume::open(Forge::of_size(256 << 30).source()).expect("a formatted device");
        assert_eq!(exact.mirrors()[2], Mirror::OutsideDevice);
        let one_more =
            Volume::open(Forge::of_size(THREE_MIRRORS).source()).expect("a formatted device");
        assert!(matches!(one_more.mirrors()[2], Mirror::Present { .. }));
    }

    #[test]
    fn the_newest_copy_of_the_superblock_is_the_one_the_filesystem_is_read_through() {
        // The filesystem's own rule. A copy left behind by a torn write must not be the one a
        // reader believes, whichever location it sits at.
        let mut forge = Forge::of_size(TWO_MIRRORS);
        forge.amend_superblock(1, |sb| {
            sb.generation = 99;
            sb.root = CHUNK_LOGICAL;
        });
        let volume = Volume::open_with(
            forge.source(),
            OpenOptions::new().policy(ReadPolicy::Lenient),
        )
        .expect("a filesystem whose copies disagree still opens leniently");
        assert_eq!(volume.superblock().generation, 99);
        assert_eq!(volume.superblock().root, CHUNK_LOGICAL);
        assert_eq!(
            volume.mirrors()[0].generation(),
            Some(super::super::forge::GENERATION)
        );
        assert_eq!(volume.mirrors()[1].generation(), Some(99));
    }

    #[test]
    fn a_copy_that_disagrees_with_the_live_one_is_refused_strictly_and_recorded_leniently() {
        // Each way a copy can be wrong, and each is a refusal under a strict read: what a
        // strict read returns is a filesystem whose every field it recognized, and a copy of
        // the superblock is a field of it.
        /// What a row does to a copy of the superblock, and what a lenient read must then
        /// say about it.
        type Damage = (&'static str, Box<dyn Fn(&mut Forge)>, Mirror);

        let damage: [Damage; 5] = [
            (
                "a checksum that no longer covers it",
                Box::new(|f: &mut Forge| {
                    f.break_superblock(1);
                }),
                Mirror::Damaged,
            ),
            (
                "a copy left behind by an earlier transaction",
                Box::new(|f: &mut Forge| {
                    f.amend_superblock(1, |sb| sb.generation = 1);
                }),
                Mirror::Present { generation: 1 },
            ),
            (
                "a copy written somewhere other than where it says it is",
                Box::new(|f: &mut Forge| {
                    f.copy_superblock(0, 1);
                }),
                Mirror::Misplaced { bytenr: MIRRORS[0] },
            ),
            (
                "a copy naming another filesystem",
                Box::new(|f: &mut Forge| {
                    f.amend_superblock(1, |sb| sb.fsid[0] ^= 1);
                }),
                Mirror::Foreign,
            ),
            (
                "a copy at the live generation recording another label",
                Box::new(|f: &mut Forge| {
                    f.amend_superblock(1, |sb| sb.label[0] ^= 1);
                }),
                Mirror::Diverged {
                    generation: super::super::forge::GENERATION,
                },
            ),
        ];
        for (what, apply, expected) in damage {
            let mut forge = Forge::of_size(TWO_MIRRORS);
            apply(&mut forge);
            let strict = Volume::open(forge.source()).err();
            assert!(
                matches!(
                    strict,
                    Some(ReadError::MirrorDisagreement { mirror: 1, .. })
                ),
                "{what}: {strict:?}"
            );
            let lenient = Volume::open_with(
                forge.source(),
                OpenOptions::new().policy(ReadPolicy::Lenient),
            )
            .unwrap_or_else(|e| panic!("{what} opens leniently: {e}"));
            assert_eq!(lenient.mirrors()[1], expected, "{what}");
            assert_eq!(
                lenient.superblock().generation,
                super::super::forge::GENERATION
            );
        }
    }

    #[test]
    fn a_damaged_first_copy_is_read_through_the_second_rather_than_refused_outright() {
        // The reason there is more than one copy. Under a lenient read the filesystem opens
        // through the surviving copy and says which one was damaged.
        let mut forge = Forge::of_size(TWO_MIRRORS);
        forge.break_superblock(0);
        let volume = Volume::open_with(
            forge.source(),
            OpenOptions::new().policy(ReadPolicy::Lenient),
        )
        .expect("the second copy is intact");
        assert_eq!(volume.mirrors()[0], Mirror::Damaged);
        assert!(matches!(volume.mirrors()[1], Mirror::Present { .. }));

        // And with every copy damaged there is nothing to read through, which is a checksum
        // refusal rather than "these bytes are not a btrfs" — the two say different things
        // about a source and a caller pointed at the wrong file wants the second.
        let mut forge = Forge::of_size(TWO_MIRRORS);
        forge.break_superblock(0).break_superblock(1);
        assert!(matches!(
            Volume::open_with(
                forge.source(),
                OpenOptions::new().policy(ReadPolicy::Lenient)
            )
            .err(),
            Some(ReadError::BadChecksum {
                object: "superblock",
                ..
            })
        ));
    }

    #[test]
    fn a_source_with_no_btrfs_in_it_says_so_rather_than_naming_a_structure() {
        let empty = std::io::Cursor::new(vec![0u8; 1 << 20]);
        assert!(matches!(
            Volume::open(empty).err(),
            Some(ReadError::NotBtrfs)
        ));
        // A source too short to hold even the first location is the same answer: not ours.
        let tiny = std::io::Cursor::new(vec![0u8; 1024]);
        assert!(matches!(
            Volume::open(tiny).err(),
            Some(ReadError::NotBtrfs)
        ));
    }

    #[test]
    fn a_source_shorter_than_the_device_it_describes_is_reported_as_that() {
        // The image in hand is not the whole of the filesystem it claims to be. The first
        // copy still reads, so this is a statement about the copies that do not.
        let forge = Forge::of_size(TWO_MIRRORS);
        let short = forge.truncated(2 << 20);
        assert!(matches!(
            Volume::open(short).err(),
            Some(ReadError::MirrorDisagreement { mirror: 1, .. })
        ));
        let short = forge.truncated(2 << 20);
        let lenient = Volume::open_with(short, OpenOptions::new().policy(ReadPolicy::Lenient))
            .expect("lenient");
        assert_eq!(lenient.mirrors()[1], Mirror::Truncated);
    }

    #[test]
    fn a_filesystem_inside_a_partition_is_read_from_where_the_caller_says_it_begins() {
        // Every location is relative to the filesystem rather than to the source, so a base
        // shifts all of them — and the self-address check must be made against the offset
        // within the filesystem or a partition would look misplaced.
        const BASE: u64 = 1 << 20;
        let forge = Forge::new();
        let mut device = vec![0u8; BASE as usize];
        let mut source = forge.source();
        std::io::Read::read_to_end(&mut source, &mut device).expect("the forged device");
        let mut volume =
            Volume::open_with(std::io::Cursor::new(device), OpenOptions::new().base(BASE))
                .expect("a filesystem a mebibyte into its source");
        assert!(matches!(volume.mirrors()[0], Mirror::Present { .. }));
        let root = volume.root_tree();
        assert_eq!(root.bytenr, ROOT_TREE_AT);
        volume
            .tree(root)
            .count_items()
            .expect("the root tree reads");
    }

    #[test]
    fn the_chunk_tree_is_read_through_the_bootstrap_and_completes_the_map() {
        // The bootstrap carries the system chunk and the chunk tree repeats it, so meeting it
        // again is the ordinary case rather than an overlap. What must not happen is the map
        // gaining a second entry for one address.
        let volume = Volume::open(Forge::new().source()).expect("a forged filesystem");
        assert_eq!(volume.chunk_map().len(), 1);
        let chunk = &volume.chunk_map().chunks()[0];
        assert_eq!(chunk.logical, CHUNK_LOGICAL);
        assert_eq!(chunk.copies.len(), 1);
        assert_ne!(
            chunk.copies[0], chunk.logical,
            "the mapping is not the identity"
        );
    }

    #[test]
    fn a_chunk_tree_that_moves_a_bootstrap_chunk_is_refused_strictly_and_recorded_leniently() {
        // The chunk tree repeats the bootstrap array's system chunk, and a repeated record is
        // held to say the same thing. Here it places the chunk's one copy 64 KiB further into
        // the device, which is a second answer for every address the chunk covers — the
        // bootstrap's answer is the one that read the chunk tree at all.
        let mut forge = Forge::new();
        forge.amend(CHUNK_TREE_AT, |block| {
            let item = ondisk::Item::read_from(&block[Header::SIZE..]).expect("the one item");
            let stripe_offset = Header::SIZE + item.offset as usize + Chunk::SIZE + 8;
            let moved = crate::bytes::get_u64(block, stripe_offset) + (64 << 10);
            block[stripe_offset..stripe_offset + 8].copy_from_slice(&moved.to_le_bytes());
        });
        assert!(
            matches!(
                Volume::open(forge.source()).err(),
                Some(ReadError::BadChunk { logical, .. }) if logical == CHUNK_LOGICAL
            ),
            "a strict open refuses two mappings of one chunk"
        );
        let lenient = Volume::open_with(
            forge.source(),
            OpenOptions::new().policy(ReadPolicy::Lenient),
        )
        .expect("a lenient open keeps the bootstrap's mapping");
        assert_eq!(lenient.bootstrap_conflicts(), [CHUNK_LOGICAL]);
        assert_eq!(lenient.chunk_map().len(), 1);
        assert_eq!(
            lenient.chunk_map().chunks()[0].copies,
            [super::super::forge::CHUNK_PHYSICAL]
        );

        // The control: the record the forge writes repeats the bootstrap's exactly, and is
        // neither refused nor recorded.
        let clean = Volume::open(Forge::new().source()).expect("the forged filesystem");
        assert!(clean.bootstrap_conflicts().is_empty());
    }

    #[test]
    fn a_checksum_is_only_held_to_hold_for_the_algorithm_that_produced_it() {
        let mut object = vec![0u8; SUPER_INFO_SIZE];
        object[64..72].copy_from_slice(&ondisk::MAGIC);
        let digest = ondisk::checksum(&object);
        object[..4].copy_from_slice(&digest.to_le_bytes());
        assert!(checksum_holds(&object, ChecksumType::CRC32C));

        // A byte anywhere past the field changes it.
        object[100] ^= 0xff;
        assert!(!checksum_holds(&object, ChecksumType::CRC32C));
        object[100] ^= 0xff;
        assert!(checksum_holds(&object, ChecksumType::CRC32C));

        // Something in the padding behind a four-byte digest is a field written by a tool
        // that did not agree about the algorithm.
        object[7] = 1;
        assert!(!checksum_holds(&object, ChecksumType::CRC32C));
        object[7] = 0;

        // And an algorithm this crate does not compute never answers "it holds".
        assert!(!checksum_holds(&object, ChecksumType::SHA256));
    }
}