Skip to main content

scionic_merkletree/
read.rs

1//! Reading a tree that a store holds: finding a path, reading a file or a
2//! stretch of it, and writing the tree out to disk.
3//!
4//! Everything read from the store is checked again before it is used: a list
5//! against the hash it was asked for by, and a chunk against the hash and the
6//! length its file gives it. A file's bytes are handed out only when every
7//! chunk they need is there. Otherwise it is an error, never a shorter file.
8
9use crate::disk::{Held, Refused};
10use crate::format::{
11    check_name, ChunkRef, Entry, FileList, FolderList, Kind, OpenFile, Record, Target,
12    MAX_FOLDER_DEPTH,
13};
14use crate::hash::{Hash, Root};
15use crate::store::{load_file, load_folder, load_record, missing, ChunksAhead, Store, Stored};
16use crate::{io_error, Error, Result};
17use std::collections::{HashMap, HashSet};
18use std::fs::{self, OpenOptions};
19use std::io::{ErrorKind, Write};
20use std::path::{Path, PathBuf};
21use std::sync::Arc;
22
23fn invalid(detail: &str) -> Error {
24    Error::InvalidData {
25        detail: detail.to_owned(),
26    }
27}
28
29/// The record of the tree with this root.
30pub fn record_of(store: &dyn Store, root: &Root) -> Result<Record> {
31    load_record(store, root)?.ok_or_else(|| missing("the record of", root.as_hash()))
32}
33
34/// The entries of a folder.
35pub fn folder_of(store: &dyn Store, folder: &Target) -> Result<FolderList> {
36    load_folder(store, folder)?.ok_or_else(|| missing("the list of the folder", &folder.hash))
37}
38
39/// The list of a file's chunks.
40pub fn file_of(store: &dyn Store, file: &Target) -> Result<FileList> {
41    load_file(store, file)?.ok_or_else(|| missing("the list of the file", &file.hash))
42}
43
44/// What is at `path` in a tree: names with `/` between them, as in
45/// `weights/model.safetensors`. Nothing is there when a name on the way is
46/// missing, or is a file. A path that leads through more folders than a tree
47/// may have is an error.
48pub fn lookup(store: &dyn Store, root: &Root, path: &str) -> Result<Option<Entry>> {
49    let mut current = record_of(store, root)?.top();
50    let mut found = None;
51    for (folders_passed, name) in path.split('/').enumerate() {
52        check_name(name)?;
53        if current.kind != Kind::Folder {
54            return Ok(None);
55        }
56        if folders_passed >= MAX_FOLDER_DEPTH {
57            return Err(Error::TooDeep {
58                limit: MAX_FOLDER_DEPTH,
59            });
60        }
61        let list = folder_of(store, &current)?;
62        let Some(entry) = list.get(name) else {
63            return Ok(None);
64        };
65        current = entry.target();
66        found = Some(entry.clone());
67    }
68    Ok(found)
69}
70
71/// Writes all of a file's bytes to `out`.
72pub fn read_file(store: &dyn Store, file: &Target, out: &mut dyn Write) -> Result<()> {
73    read_range(store, file, 0, file.size, out)
74}
75
76/// A file's bytes, in memory.
77pub fn read_file_to_vec(store: &dyn Store, file: &Target) -> Result<Vec<u8>> {
78    let size = usize::try_from(file.size).map_err(|_| Error::SizeOverflow {
79        field: "a file read into memory",
80    })?;
81    let mut bytes = Vec::new();
82    bytes
83        .try_reserve_exact(size)
84        .map_err(|_| Error::AllocationFailed {
85            resource: "a file read into memory",
86            requested: file.size,
87        })?;
88    read_file(store, file, &mut bytes)?;
89    Ok(bytes)
90}
91
92/// Writes `length` bytes of a file, from byte `offset`, to `out`.
93///
94/// Before the first byte goes out, every chunk of the stretch is looked for.
95/// If one is missing, nothing is written. Each chunk is then checked against
96/// its hash as it is written.
97///
98/// The file's list is read and checked on every call. For many stretches of
99/// one long file, open its list once and use [`read_open`].
100pub fn read_range(
101    store: &dyn Store,
102    file: &Target,
103    offset: u64,
104    length: u64,
105    out: &mut dyn Write,
106) -> Result<()> {
107    let list = file_of(store, file)?;
108    let end = offset
109        .checked_add(length)
110        .filter(|end| *end <= list.size())
111        .ok_or_else(|| invalid("a stretch of bytes is outside the file"))?;
112    if length == 0 {
113        return Ok(());
114    }
115    // The chunks that hold the stretch, each with the byte it starts at.
116    let mut wanted = Vec::new();
117    let mut start = 0_u64;
118    for item in list.items() {
119        if start >= end {
120            break;
121        }
122        let after = start + u64::from(item.length);
123        if after > offset {
124            wanted.push((*item, start));
125        }
126        start = after;
127    }
128    write_stretch(store, &wanted, offset, end, out)
129}
130
131/// Writes `length` bytes of a file whose list is open, from byte `offset`,
132/// to `out`. It does what [`read_range`] does, and finds the chunks without
133/// a pass over the list.
134pub fn read_open(
135    store: &dyn Store,
136    file: &OpenFile,
137    offset: u64,
138    length: u64,
139    out: &mut dyn Write,
140) -> Result<()> {
141    if length == 0 {
142        return if offset <= file.list().size() {
143            Ok(())
144        } else {
145            Err(invalid("a stretch of bytes is outside the file"))
146        };
147    }
148    let (first, after) = file.chunks_for(offset, length)?;
149    let mut wanted = Vec::new();
150    for number in first..after {
151        let item = usize::try_from(number)
152            .ok()
153            .and_then(|place| file.list().items().get(place));
154        let (Some(item), Some(start)) = (item, file.start_of(number)) else {
155            return Err(Error::Invariant {
156                detail: "an open file names a chunk it does not have",
157            });
158        };
159        wanted.push((*item, start));
160    }
161    write_stretch(store, &wanted, offset, offset + length, out)
162}
163
164/// Writes the bytes from `offset` up to `end` out of the chunks that hold
165/// them. Each chunk comes with the byte of the file it starts at.
166fn write_stretch(
167    store: &dyn Store,
168    wanted: &[(ChunkRef, u64)],
169    offset: u64,
170    end: u64,
171    out: &mut dyn Write,
172) -> Result<()> {
173    for (item, _) in wanted {
174        match store.size(Stored::Chunk, &item.hash)? {
175            Some(size) if size == u64::from(item.length) => {}
176            Some(size) => {
177                return Err(Error::SizeMismatch {
178                    what: "a stored chunk",
179                    expected: u64::from(item.length),
180                    actual: size,
181                })
182            }
183            None => return Err(missing("the chunk", &item.hash)),
184        }
185    }
186    // A long stretch is read and checked several chunks at once, ahead of
187    // what is written.
188    let items: Vec<ChunkRef> = wanted.iter().map(|(item, _)| *item).collect();
189    ChunksAhead::new().lend(store, &items, &mut |place, bytes| {
190        let (item, start) = &wanted[place];
191        let from = offset.saturating_sub(*start) as usize;
192        let to = (end.min(start + u64::from(item.length)) - start) as usize;
193        out.write_all(&bytes[from..to])
194            .map_err(|source| Error::Stream {
195                operation: "write a file's bytes",
196                source,
197            })
198    })
199}
200
201/// Why this system cannot hold a name as it is, if it cannot.
202///
203/// A tree can hold a name that one system cannot. What is checked here is
204/// what would make a name land somewhere else than it says: on another file,
205/// on a device, or outside the folder.
206pub fn unwritable(name: &str) -> Option<&'static str> {
207    if check_name(name).is_err() {
208        return Some("the format does not allow it");
209    }
210    if cfg!(windows) {
211        return unwritable_on_windows(name);
212    }
213    None
214}
215
216/// Why Windows cannot hold a name as it is, if it cannot.
217pub fn unwritable_on_windows(name: &str) -> Option<&'static str> {
218    let forbidden = |letter: char| {
219        matches!(letter, '<' | '>' | ':' | '"' | '|' | '?' | '*' | '\\' | '/') || letter < ' '
220    };
221    if name.chars().any(forbidden) {
222        return Some("it holds a character that Windows does not allow in a name");
223    }
224    if name.ends_with('.') || name.ends_with(' ') {
225        return Some("Windows drops a dot or a space at the end of a name");
226    }
227    // A device name is one whatever follows its first dot: `NUL.txt` is `NUL`.
228    let stem = name.split('.').next().unwrap_or(name).trim_end_matches(' ');
229    let stem = stem.to_ascii_uppercase();
230    let numbered = |port: &str| {
231        stem.strip_prefix(port).is_some_and(|number| {
232            let mut letters = number.chars();
233            matches!(
234                (letters.next(), letters.next()),
235                (Some('0'..='9' | '\u{b9}' | '\u{b2}' | '\u{b3}'), None)
236            )
237        })
238    };
239    if matches!(
240        stem.as_str(),
241        "CON" | "PRN" | "AUX" | "NUL" | "CONIN$" | "CONOUT$"
242    ) || numbered("COM")
243        || numbered("LPT")
244    {
245        return Some("Windows takes it for a device");
246    }
247    None
248}
249
250fn unwritable_error(name: &str, reason: &'static str) -> Error {
251    Error::UnwritableName {
252        name: name.chars().take(80).collect(),
253        reason,
254    }
255}
256
257/// The most files and folders that [`write_to_disk`] makes unless it is told
258/// otherwise.
259pub const DEFAULT_MAX_WRITTEN_ENTRIES: u64 = 1_000_000;
260
261/// How far writing a tree out may go.
262///
263/// A tree keeps each folder once, however many places the folder has in it,
264/// and writing it out makes the folder at every one of those places. So a
265/// tree of a few small lists can stand for more folders than any disk
266/// holds: a folder with two names for one folder, a hundred deep. Both
267/// limits are held before anything is written.
268#[derive(Clone, Copy, Debug, Eq, PartialEq)]
269pub struct WriteOptions {
270    max_entries: u64,
271    max_bytes: u64,
272}
273
274impl Default for WriteOptions {
275    fn default() -> Self {
276        Self::new()
277    }
278}
279
280impl WriteOptions {
281    /// At most [`DEFAULT_MAX_WRITTEN_ENTRIES`] files and folders, and as many
282    /// bytes as the tree has.
283    pub fn new() -> Self {
284        Self {
285            max_entries: DEFAULT_MAX_WRITTEN_ENTRIES,
286            max_bytes: u64::MAX,
287        }
288    }
289
290    /// The most files and folders that may be made, the top one counted.
291    pub fn max_entries(mut self, most: u64) -> Self {
292        self.max_entries = most;
293        self
294    }
295
296    /// The most bytes that may be written. A tree's record says how many it
297    /// takes: the size of what is on top, with a file or a chunk that the
298    /// tree uses twice counted twice.
299    pub fn max_bytes(mut self, most: u64) -> Self {
300        self.max_bytes = most;
301        self
302    }
303}
304
305/// Writes a tree out to disk: its top folder as the new folder `dest`, or
306/// its top file as the new file `dest`.
307///
308/// Writing is stricter than holding. `dest` must not exist. Before anything
309/// is written, the whole tree is looked through: every list and every chunk
310/// must be there, no folder may sit too deep, every name must be one that
311/// this system can hold as it is, and what would be made must fit within
312/// [`WriteOptions::new`]. Every file and folder is then created as new.
313/// Where two names of one folder would land on the same file, as `File` and
314/// `file` do on Windows and macOS, the second one is refused, and so is a
315/// name that the system keeps differently from how it was given. A name is
316/// never changed to make it fit: the error says which name it was.
317///
318/// A tree holds no links, and every folder written into is one this call
319/// created, so nothing is written outside `dest`. After an error, what was
320/// written so far stays.
321pub fn write_to_disk(store: &dyn Store, root: &Root, dest: impl AsRef<Path>) -> Result<()> {
322    write_to_disk_with(store, root, dest, &WriteOptions::new())
323}
324
325/// Writes a tree out to disk as [`write_to_disk`] does, within other limits.
326pub fn write_to_disk_with(
327    store: &dyn Store,
328    root: &Root,
329    dest: impl AsRef<Path>,
330    options: &WriteOptions,
331) -> Result<()> {
332    let dest = dest.as_ref();
333    let top = record_of(store, root)?.top();
334
335    // First: find everything, count what would be made, and write nothing.
336    let entries = match top.kind {
337        Kind::File => {
338            require_chunks(store, &file_of(store, &top)?)?;
339            1
340        }
341        Kind::Folder => survey(store, &top)?,
342    };
343    if entries > options.max_entries {
344        return Err(Error::LimitExceeded {
345            what: "the files and folders that writing the tree out makes",
346            limit: options.max_entries,
347            requested: entries,
348        });
349    }
350    if top.size > options.max_bytes {
351        return Err(Error::LimitExceeded {
352            what: "the bytes that writing the tree out takes",
353            limit: options.max_bytes,
354            requested: top.size,
355        });
356    }
357    if top.kind == Kind::File {
358        // The place a caller names is the caller's.
359        let out = OpenOptions::new()
360            .write(true)
361            .create_new(true)
362            .open(dest)
363            .map_err(|error| io_error("create the file", dest, error))?;
364        return fill_file(store, &top, out, dest);
365    }
366
367    // Then: write. From here on nothing is reached by its path. The new
368    // folder is held open, and so is every folder under it while it is
369    // filled, so no folder on the way can be swapped for a link.
370    //
371    // A folder is made with its folder's other entries, and filled when its
372    // turn comes. The folders on the way down to the one that is filled stay
373    // open, and no others.
374    let held = Held::create(dest).map_err(|error| not_made(dest, error))?;
375    let mut way: Vec<ToFill> = Vec::new();
376    let mut next = Some((held, top));
377    loop {
378        if let Some((held, folder)) = next.take() {
379            let inside = fill_folder(store, &held, &folder)?;
380            way.push((held, inside));
381        }
382        let Some((held, inside)) = way.last_mut() else {
383            break;
384        };
385        match inside.pop() {
386            Some((name, folder)) => {
387                let below = held
388                    .open_folder(&name)
389                    .map_err(|refused| reopened(&held.path().join(&name), refused))?;
390                next = Some((below, folder));
391            }
392            None => {
393                way.pop();
394            }
395        }
396    }
397    Ok(())
398}
399
400/// A folder on the way down to the one that is filled, held open, with the
401/// folders inside it that are still to be filled.
402type ToFill = (Arc<Held>, Vec<(String, Target)>);
403
404/// Fills a new folder that is held open: writes its files, makes the folders
405/// inside it, and holds what it then lists against what it was given. Gives
406/// the folders inside it, which are still to be filled.
407fn fill_folder(
408    store: &dyn Store,
409    held: &Arc<Held>,
410    folder: &Target,
411) -> Result<Vec<(String, Target)>> {
412    let list = folder_of(store, folder)?;
413    let mut inside = Vec::new();
414    for entry in list.entries() {
415        let name = entry.name();
416        let child = child_path(held.path(), name)?;
417        match entry.kind() {
418            Kind::File => {
419                let out = held.create_file(name).map_err(|error| {
420                    if taken(&child, &error) {
421                        unwritable_error(name, "another name of its folder lands on the same place")
422                    } else {
423                        io_error("create the file", &child, error)
424                    }
425                })?;
426                fill_file(store, &entry.target(), out, &child)?;
427            }
428            Kind::Folder => {
429                // Made now, with the names beside it. It is opened again
430                // when its turn comes, so that a folder of many folders
431                // does not keep them all open.
432                held.create_folder(name)
433                    .map_err(|error| not_made(&child, error))?;
434                inside.push((name.to_owned(), entry.target()));
435            }
436        }
437    }
438    // The folder must now hold exactly the names it was given.
439    confirm_names(held, &list)?;
440    Ok(inside)
441}
442
443/// Looks through a whole tree before it is written out, each folder once,
444/// however many places it has. Every list and every chunk must be there,
445/// every name must be one this system can hold, and no folder may sit too
446/// deep. Gives how many files and folders writing the tree makes, the top
447/// one counted, and a folder with several places counted at each.
448fn survey(store: &dyn Store, top: &Target) -> Result<u64> {
449    let too_deep = || Error::TooDeep {
450        limit: MAX_FOLDER_DEPTH,
451    };
452    // For each folder that is done: how many files and folders are below
453    // it, and how many folders deep it goes, itself counted.
454    let mut done: HashMap<Hash, (u64, usize)> = HashMap::new();
455    let mut checked_files: HashSet<Hash> = HashSet::new();
456    // The folders on the way down: each with its list, and with the place
457    // of the entry that is looked at next.
458    let first = folder_of(store, top)?;
459    check_names(&first)?;
460    let mut path: Vec<(Hash, FolderList, usize)> = vec![(top.hash, first, 0)];
461    while let Some((_, list, next)) = path.last_mut() {
462        let entry = list
463            .entries()
464            .get(*next)
465            .map(|entry| (entry.kind(), entry.target()));
466        *next += 1;
467        match entry {
468            Some((Kind::File, file)) => {
469                if checked_files.insert(file.hash) {
470                    require_chunks(store, &file_of(store, &file)?)?;
471                }
472            }
473            Some((Kind::Folder, folder)) => {
474                if done.contains_key(&folder.hash) {
475                    continue;
476                }
477                if path.len() >= MAX_FOLDER_DEPTH {
478                    return Err(too_deep());
479                }
480                let inside = folder_of(store, &folder)?;
481                check_names(&inside)?;
482                path.push((folder.hash, inside, 0));
483            }
484            None => {
485                // Every entry is looked at, and every folder inside is done.
486                let Some((hash, list, _)) = path.pop() else {
487                    break;
488                };
489                let mut below = 0_u64;
490                let mut deep = 1_usize;
491                for entry in list.entries() {
492                    below = below.saturating_add(1);
493                    if entry.kind() == Kind::Folder {
494                        let (inside, depth) =
495                            done.get(entry.hash()).copied().ok_or(Error::Invariant {
496                                detail: "a folder is counted before the folders inside it",
497                            })?;
498                        below = below.saturating_add(inside);
499                        deep = deep.max(depth + 1);
500                    }
501                }
502                if deep > MAX_FOLDER_DEPTH {
503                    return Err(too_deep());
504                }
505                done.insert(hash, (below, deep));
506            }
507        }
508    }
509    let (below, _) = done.get(&top.hash).copied().ok_or(Error::Invariant {
510        detail: "the top folder is not counted",
511    })?;
512    Ok(below.saturating_add(1))
513}
514
515/// Every name of a folder has to be one that this system can hold as it is.
516fn check_names(folder: &FolderList) -> Result<()> {
517    for entry in folder.entries() {
518        if let Some(reason) = unwritable(entry.name()) {
519            return Err(unwritable_error(entry.name(), reason));
520        }
521    }
522    Ok(())
523}
524
525/// The path of `name` in `folder`. It has to be directly inside it.
526fn child_path(folder: &Path, name: &str) -> Result<PathBuf> {
527    let child = folder.join(name);
528    if child.parent() != Some(folder)
529        || child.file_name().and_then(|last| last.to_str()) != Some(name)
530    {
531        return Err(unwritable_error(
532            name,
533            "it would not land inside its folder",
534        ));
535    }
536    Ok(child)
537}
538
539/// Every chunk of a file has to be held, with the length its list gives it.
540fn require_chunks(store: &dyn Store, list: &FileList) -> Result<()> {
541    for item in list.items() {
542        match store.size(Stored::Chunk, &item.hash)? {
543            Some(size) if size == u64::from(item.length) => {}
544            Some(size) => {
545                return Err(Error::SizeMismatch {
546                    what: "a stored chunk",
547                    expected: u64::from(item.length),
548                    actual: size,
549                })
550            }
551            None => return Err(missing("the chunk", &item.hash)),
552        }
553    }
554    Ok(())
555}
556
557/// Whether something is at `path`, be it a file, a folder or a link. Systems
558/// do not agree on the error they give for making a thing where another one
559/// is, so the place is looked at.
560fn taken(path: &Path, error: &std::io::Error) -> bool {
561    error.kind() == ErrorKind::AlreadyExists || fs::symlink_metadata(path).is_ok()
562}
563
564/// Why a folder was not made at `path`.
565fn not_made(path: &Path, error: std::io::Error) -> Error {
566    match path.file_name().and_then(|name| name.to_str()) {
567        Some(name) if taken(path, &error) => {
568            unwritable_error(name, "something is there already under that name")
569        }
570        _ => io_error("create the folder", path, error),
571    }
572}
573
574/// A folder that was made has to be that folder still when its turn comes.
575fn reopened(path: &Path, refused: Refused) -> Error {
576    match refused {
577        Refused::Io(error) => io_error("open the folder", path, error),
578        Refused::Link | Refused::Other => {
579            invalid("a folder that was written was swapped for something else before it was filled")
580        }
581    }
582}
583
584/// Writes a file's bytes into a file that was just made. `path` is for
585/// messages.
586fn fill_file(store: &dyn Store, file: &Target, mut out: fs::File, path: &Path) -> Result<()> {
587    read_file(store, file, &mut out).map_err(|error| match error {
588        Error::Stream { source, .. } => io_error("write", path, source),
589        other => other,
590    })
591}
592
593/// A folder that was written must list exactly the names it was given, byte
594/// for byte. Where the system changed a name, the tree was not written as it
595/// is.
596fn confirm_names(held: &Held, folder: &FolderList) -> Result<()> {
597    let path = held.path();
598    let written: HashSet<std::ffi::OsString> = held
599        .list()
600        .map_err(|error| io_error("list", path, error))?
601        .into_iter()
602        .map(|(name, _)| name)
603        .collect();
604    for entry in folder.entries() {
605        if !written.contains(std::ffi::OsStr::new(entry.name())) {
606            return Err(unwritable_error(
607                entry.name(),
608                "this system keeps it under another name",
609            ));
610        }
611    }
612    if written.len() != folder.entries().len() {
613        return Err(invalid(
614            "a folder that was written holds a name it was not given",
615        ));
616    }
617    Ok(())
618}