structured-zstd 0.2.6

//! Which files a run works on, and where their outputs land.
//!
//! The command line names inputs; `--filelist` adds more from a file; `-r`
//! turns the directories among them into the files underneath. The output of
//! each is then placed next to it, or under `--output-dir-flat` /
//! `--output-dir-mirror`. The reference command does this in `zstdcli.c` and
//! `util.c`, and the order of the steps is kept: symbolic links are dropped
//! from the NAMED inputs before the file lists are merged, and directories are
//! expanded after. One departure: whether anything is left to do is judged
//! once the file lists are in. The reference command judges the named inputs
//! alone, which fails a run whose list still names usable inputs.

use std::ffi::OsString;
use std::fs;
use std::io::{BufRead, BufReader};
use std::path::{Component, Path, PathBuf};

use super::{Result, WrapErr};

/// Largest `--filelist` the reference command reads (50 MiB).
pub const FILELIST_MAX_BYTES: u64 = 50 << 20;

/// The inputs a run ended up with.
#[derive(Debug)]
pub struct Selection {
    /// Every file to process, in command-line order, directories expanded.
    pub files: Vec<PathBuf>,
    /// Whether the command line gave a source of inputs at all: a name, or a
    /// `--filelist`, even one that lists nothing. A run that was given one and
    /// ended up with no files was pointed at empty directories or an empty
    /// list, which is not a request to read stdin.
    pub explicit: bool,
    /// Directories `-r` could not open: each was reported and contributed
    /// nothing, so the files under it were never selected.
    pub unreadable_dirs: usize,
}

/// Resolve the command line's inputs to the files a run processes.
///
/// `follow_links` is `-f`: without it a symbolic link is skipped with a
/// warning, both on the command line and inside a directory walked by `-r`.
/// A FIFO reached through a link is kept, since the link is how a named pipe
/// is usually handed over.
pub fn select_inputs(
    named: Vec<PathBuf>,
    filelists: &[PathBuf],
    recursive: bool,
    follow_links: bool,
    verbosity: i32,
) -> Result<Selection> {
    let mut files = Vec::with_capacity(named.len());
    let named_count = named.len();
    for input in named {
        if !follow_links && input != Path::new("-") && is_symlink(&input) && !is_fifo(&input) {
            display!(
                verbosity,
                2,
                "Warning : {} is a symbolic link, ignoring",
                input.display()
            );
            continue;
        }
        files.push(input);
    }
    // List entries are not link-filtered: the reference command filters the
    // named inputs only and merges the lists after (`zstdcli.c`), so a link
    // handed over through a list is processed, and a link to a directory is
    // walked by `-r` below. Links met inside that walk are still skipped.
    for list in filelists {
        files.extend(read_filelist(list)?);
    }
    if files.is_empty() && named_count > 0 {
        bail!("every named input is a symbolic link; pass -f to follow them");
    }
    let explicit = named_count > 0 || !filelists.is_empty();
    let mut walk = Walk {
        follow_links,
        verbosity,
        unreadable_dirs: 0,
    };
    if recursive {
        let mut expanded = Vec::with_capacity(files.len());
        for input in files {
            match fs::metadata(&input) {
                Ok(metadata) if metadata.is_dir() => {
                    let mut ancestors = Vec::new();
                    walk.descend(&input, &metadata, &mut expanded, &mut ancestors)?;
                }
                _ => expanded.push(input),
            }
        }
        files = expanded;
    }
    Ok(Selection {
        files,
        explicit,
        unreadable_dirs: walk.unreadable_dirs,
    })
}

/// A `-r` walk: its settings, and what it could not read.
struct Walk {
    follow_links: bool,
    verbosity: i32,
    /// Directories the walk reported and skipped because they would not open.
    unreadable_dirs: usize,
}

/// What identifies a directory whatever name reaches it, so a walk notices
/// when a link has led it back to a directory it is already inside.
#[cfg(unix)]
type DirId = (u64, u64);
#[cfg(not(unix))]
type DirId = PathBuf;

/// The identity of the directory at `path`, whose `metadata` (links followed)
/// is already in hand; the device and inode where the file system has them,
/// the canonical path elsewhere.
#[cfg(unix)]
fn dir_id(path: &Path, metadata: &fs::Metadata) -> Option<DirId> {
    use std::os::unix::fs::MetadataExt;
    let _ = path;
    Some((metadata.dev(), metadata.ino()))
}

#[cfg(not(unix))]
fn dir_id(path: &Path, metadata: &fs::Metadata) -> Option<DirId> {
    let _ = metadata;
    fs::canonicalize(path).ok()
}

impl Walk {
    /// Walk `dir` unless the walk is already inside it. A link followed under
    /// `-f`, or a bind mount, can lead back to an ancestor; entering it again
    /// would list the tree once more per nesting level until the path ran out
    /// of room, so the loop is reported and not descended. `ancestors` holds
    /// the directories on the way down to `dir`.
    fn descend(
        &mut self,
        dir: &Path,
        metadata: &fs::Metadata,
        out: &mut Vec<PathBuf>,
        ancestors: &mut Vec<DirId>,
    ) -> Result<()> {
        let Some(id) = dir_id(dir, metadata) else {
            return self.walk_directory(dir, out, ancestors);
        };
        if ancestors.contains(&id) {
            display!(
                self.verbosity,
                2,
                "Warning : {} leads back into a directory being walked, ignoring",
                dir.display()
            );
            return Ok(());
        }
        ancestors.push(id);
        let walked = self.walk_directory(dir, out, ancestors);
        ancestors.pop();
        walked
    }

    /// Append every file under `dir` to `out`, depth first.
    ///
    /// Entries are taken in name order so two runs over one tree process it
    /// the same way; the reference command takes them in directory order,
    /// which the filesystem does not promise to keep. Subdirectories go
    /// through [`Self::descend`], which keeps a link from leading the walk
    /// round in a circle.
    ///
    /// The two read failures end differently. A directory that cannot be
    /// opened is reported, contributes nothing, and is counted, so the run can
    /// fail on it once the readable rest is done. A listing that fails
    /// part-way is an error that ends the run, as in the reference command
    /// (`util.c`, `UTIL_prepareFileList`), since the tree it would leave
    /// behind is incomplete in a way nothing reports.
    fn walk_directory(
        &mut self,
        dir: &Path,
        out: &mut Vec<PathBuf>,
        ancestors: &mut Vec<DirId>,
    ) -> Result<()> {
        let entries = match fs::read_dir(dir) {
            Ok(entries) => entries,
            Err(err) => {
                display!(
                    self.verbosity,
                    1,
                    "Cannot open directory '{}': {err}",
                    dir.display()
                );
                self.unreadable_dirs += 1;
                return Ok(());
            }
        };
        let mut names: Vec<OsString> = Vec::new();
        for entry in entries {
            match entry {
                Ok(entry) => names.push(entry.file_name()),
                Err(err) => bail!("readdir({}) error: {err}", dir.display()),
            }
        }
        names.sort();
        for name in names {
            let path = dir.join(name);
            // Every link is skipped here without `-f`, a link to a named pipe
            // included: the FIFO exemption applies to names given on the
            // command line, where a link is how a pipe is handed over, and the
            // reference command's walk drops links without looking at what
            // they point at.
            if !self.follow_links && is_symlink(&path) {
                display!(
                    self.verbosity,
                    2,
                    "Warning : {} is a symbolic link, ignoring",
                    path.display()
                );
                continue;
            }
            match fs::metadata(&path) {
                Ok(metadata) if metadata.is_dir() => {
                    self.descend(&path, &metadata, out, ancestors)?;
                }
                _ => out.push(path),
            }
        }
        Ok(())
    }
}

/// Whether `path` itself is a symbolic link, whatever it points at.
fn is_symlink(path: &Path) -> bool {
    fs::symlink_metadata(path).is_ok_and(|m| m.file_type().is_symlink())
}

/// Whether `path`, links followed, is a named pipe.
fn is_fifo(path: &Path) -> bool {
    #[cfg(unix)]
    {
        use std::os::unix::fs::FileTypeExt;
        fs::metadata(path).is_ok_and(|m| m.file_type().is_fifo())
    }
    #[cfg(not(unix))]
    {
        let _ = path;
        false
    }
}

/// Read a `--filelist`: one file name per line, blank lines skipped.
///
/// The list has to be a regular file of bounded size, as the reference command
/// requires; a name that is not there or a directory is an error rather than
/// an empty list, since a script that mistyped the list name would otherwise
/// silently process nothing.
fn read_filelist(list: &Path) -> Result<Vec<PathBuf>> {
    let metadata =
        fs::metadata(list).wrap_err_with(|| format!("error reading {}", list.display()))?;
    if !metadata.is_file() {
        bail!("error reading {}: not a regular file", list.display());
    }
    if metadata.len() > FILELIST_MAX_BYTES {
        bail!(
            "error reading {}: file list is larger than {} bytes",
            list.display(),
            FILELIST_MAX_BYTES
        );
    }
    let file =
        fs::File::open(list).wrap_err_with(|| format!("error reading {}", list.display()))?;
    parse_filelist(file, FILELIST_MAX_BYTES, list)
}

/// The names in a `--filelist`, reading no more than `limit` bytes of it.
///
/// The size was checked before the list was opened, but a file can grow after
/// that and a pseudo-file can report less than it holds, so the limit is kept
/// on what is read as well: one byte past it is enough to know the list is too
/// large, and nothing beyond that is taken into memory.
fn parse_filelist(file: impl std::io::Read, limit: u64, list: &Path) -> Result<Vec<PathBuf>> {
    let mut names = Vec::new();
    // Lines are bytes, like the names in them: a filename need not be UTF-8,
    // and reading the list as text would reject or rename such an entry.
    // `limit` is a list-size cap (50 MiB in the run), far from `u64::MAX`.
    let mut reader = BufReader::new(file.take(limit + 1));
    let mut line = Vec::new();
    let mut total: u64 = 0;
    loop {
        line.clear();
        let read = reader
            .read_until(b'\n', &mut line)
            .wrap_err_with(|| format!("error reading {}", list.display()))?;
        if read == 0 {
            break;
        }
        // `read` is at most `limit + 1` over the whole list, so the sum stays in
        // range.
        total += read as u64;
        if total > limit {
            bail!(
                "error reading {}: file list is larger than {limit} bytes",
                list.display()
            );
        }
        if line.last() == Some(&b'\n') {
            line.pop();
        }
        if line.last() == Some(&b'\r') {
            line.pop();
        }
        if line.is_empty() {
            continue;
        }
        names.push(bytes_to_path(&line));
    }
    Ok(names)
}

#[cfg(unix)]
fn bytes_to_path(bytes: &[u8]) -> PathBuf {
    use std::os::unix::ffi::OsStrExt;
    PathBuf::from(std::ffi::OsStr::from_bytes(bytes))
}

#[cfg(not(unix))]
fn bytes_to_path(bytes: &[u8]) -> PathBuf {
    PathBuf::from(String::from_utf8_lossy(bytes).into_owned())
}

/// Where `--output-dir-flat DIR` puts the output of `src`: under `DIR`, by
/// the source's own file name.
pub fn flat_output_path(src: &Path, dir: &Path) -> PathBuf {
    dir.join(src.file_name().unwrap_or(src.as_os_str()))
}

/// The source path with the parts `--output-dir-mirror` drops: a leading
/// `./`, the root, and a drive prefix. `None` when a `..` component is in it,
/// since mirroring that would climb out of the output tree.
fn mirrored_relative(src: &Path) -> Option<PathBuf> {
    let mut relative = PathBuf::new();
    for component in src.components() {
        match component {
            Component::Prefix(_) | Component::RootDir | Component::CurDir => {}
            Component::ParentDir => return None,
            Component::Normal(part) => relative.push(part),
        }
    }
    Some(relative)
}

/// The directory `--output-dir-mirror ROOT` puts the output of `src` in: the
/// source's own directory, replayed under `ROOT`. `None` for a source the
/// reference command refuses to mirror (one with `..` in its path).
pub fn mirrored_output_dir(src: &Path, root: &Path) -> Option<PathBuf> {
    let relative = mirrored_relative(src)?;
    Some(match relative.parent() {
        Some(parent) => root.join(parent),
        None => root.to_path_buf(),
    })
}

/// Create the directory chain under `root` that mirrors the directory of
/// `src`, each level with the permissions of the source directory it mirrors.
///
/// `root` itself is created with the default permissions when it is missing.
/// A source whose path cannot be mirrored (see [`mirrored_output_dir`]) is
/// left for the caller to report.
pub fn create_mirrored_dirs(src: &Path, root: &Path) -> Result<()> {
    let Some(relative) = mirrored_relative(src) else {
        return Ok(());
    };
    create_dir_if_missing(root, None)
        .wrap_err_with(|| format!("failed to create DIR {}", root.display()))?;
    let Some(parent) = relative.parent() else {
        return Ok(());
    };
    // The source directory that each mirrored level stands for, rebuilt from
    // the source path as given so its permissions can be read: for
    // `/var/tmp/abc` the levels are `/var` and `/var/tmp`.
    //
    // `relative` holds the `Normal` components of `src` and nothing else, and
    // the ones it drops (a prefix, the root, a leading `.`) can only open a
    // path, so the difference is the count of those leading components.
    let source_count = src.components().count();
    let relative_count = relative.components().count();
    debug_assert!(
        relative_count <= source_count,
        "the mirrored path is a subset of the source's components"
    );
    let stripped = source_count - relative_count;
    let source_root: PathBuf = src.components().take(stripped).collect();
    let mut source_level = source_root;
    let mut destination = root.to_path_buf();
    for level in parent.components() {
        source_level.push(level);
        destination.push(level);
        let mode = fs::metadata(&source_level)
            .ok()
            .map(|metadata| metadata.permissions());
        create_dir_if_missing(&destination, mode)
            .wrap_err_with(|| format!("failed to create DIR {}", destination.display()))?;
    }
    Ok(())
}

/// Create `dir` unless it is already there, with `permissions` when given.
fn create_dir_if_missing(dir: &Path, permissions: Option<fs::Permissions>) -> std::io::Result<()> {
    match fs::metadata(dir) {
        Ok(existing) if existing.is_dir() => return Ok(()),
        Ok(_) => {
            return Err(std::io::Error::new(
                std::io::ErrorKind::AlreadyExists,
                "exists and is not a directory",
            ));
        }
        Err(err) if err.kind() == std::io::ErrorKind::NotFound => {}
        Err(err) => return Err(err),
    }
    #[cfg(unix)]
    let builder = {
        use std::os::unix::fs::{DirBuilderExt, PermissionsExt};
        let mut builder = fs::DirBuilder::new();
        if let Some(permissions) = &permissions {
            builder.mode(permissions.mode() & 0o7777);
        }
        builder
    };
    #[cfg(not(unix))]
    let builder = {
        let _ = permissions;
        fs::DirBuilder::new()
    };
    builder.create(dir)
}

/// The file names that more than one of `files` share, each once: given the
/// outputs of an `--output-dir-flat` run, the ones a later input replaces.
pub fn shared_file_names(files: &[PathBuf]) -> Vec<OsString> {
    let mut names: Vec<&std::ffi::OsStr> =
        files.iter().filter_map(|file| file.file_name()).collect();
    names.sort_unstable();
    let mut shared = Vec::new();
    for pair in names.windows(2) {
        if pair[0] == pair[1] && shared.last() != Some(&pair[0].to_os_string()) {
            shared.push(pair[0].to_os_string());
        }
    }
    shared
}

/// Extensions the reference command treats as already compressed under
/// `--exclude-compressed` (`fileio.c`, `compressedFileExtensions`).
const COMPRESSED_EXTENSIONS: &[&str] = &[
    ".zst", ".tzst", ".gz", ".tgz", ".lzma", ".xz", ".txz", ".lz4", ".tlz4", ".7z", ".aa3", ".aac",
    ".aar", ".ace", ".alac", ".ape", ".apk", ".apng", ".arc", ".archive", ".arj", ".ark", ".asf",
    ".avi", ".avif", ".ba", ".br", ".bz2", ".cab", ".cdx", ".chm", ".cr2", ".divx", ".dmg", ".dng",
    ".docm", ".docx", ".dotm", ".dotx", ".dsft", ".ear", ".eftx", ".emz", ".eot", ".epub", ".f4v",
    ".flac", ".flv", ".gho", ".gif", ".gifv", ".gnp", ".iso", ".jar", ".jpeg", ".jpg", ".jxl",
    ".lz", ".lzh", ".m4a", ".m4v", ".mkv", ".mov", ".mp2", ".mp3", ".mp4", ".mpa", ".mpc", ".mpe",
    ".mpeg", ".mpg", ".mpl", ".mpv", ".msi", ".odp", ".ods", ".odt", ".ogg", ".ogv", ".otp",
    ".ots", ".ott", ".pea", ".png", ".pptx", ".qt", ".rar", ".s7z", ".sfx", ".sit", ".sitx",
    ".sqx", ".svgz", ".swf", ".tbz2", ".tib", ".tlz", ".vob", ".war", ".webm", ".webp", ".wma",
    ".wmv", ".woff", ".woff2", ".wvl", ".xlsx", ".xpi", ".xps", ".zip", ".zipx", ".zoo", ".zpaq",
];

/// Whether `path` carries an extension of an already-compressed format.
///
/// The extension is the file name's last dot onward, compared exactly: a
/// dotfile has none, and `.GZ` is not `.gz`, as in the reference command.
/// Compared as the name's own bytes, since the extensions are ASCII and the
/// rest of the name need not be valid UTF-8.
pub fn has_compressed_extension(path: &Path) -> bool {
    let Some(name) = path.file_name() else {
        return false;
    };
    let name = name.as_encoded_bytes();
    match name.iter().rposition(|&byte| byte == b'.') {
        Some(0) | None => false,
        Some(at) => COMPRESSED_EXTENSIONS
            .iter()
            .any(|extension| extension.as_bytes() == &name[at..]),
    }
}

#[cfg(test)]
mod tests;