skif-core 0.4.0

//! Read-only file system abstraction so discovery runs against disk, memory or an embedder's buffers.

use std::collections::BTreeMap;
use std::io::{self, Read as _};
use std::ops::Bound;
use std::path::{Path, PathBuf};
use std::sync::Arc;
use std::time::SystemTime;

/// A directory entry returned by [`FileSystem::read_dir`].
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct DirEntry {
    /// Full path of the entry (the listed directory joined with the entry name).
    pub path: PathBuf,
    /// Whether the entry is a directory (symlinks are followed).
    pub is_dir: bool,
    /// Whether the entry is a regular file (symlinks are followed).
    pub is_file: bool,
    /// Whether the entry itself is a symbolic link; `is_dir` and `is_file` describe its target.
    pub is_symlink: bool,
}

impl DirEntry {
    /// An entry that is not a symbolic link.
    #[must_use]
    pub const fn new(path: PathBuf, is_dir: bool, is_file: bool) -> Self {
        Self {
            path,
            is_dir,
            is_file,
            is_symlink: false,
        }
    }

    /// Marks the entry as a symbolic link.
    #[must_use]
    pub const fn symlink(mut self) -> Self {
        self.is_symlink = true;
        self
    }
}

/// What a path is, with symbolic links followed. A path that does not exist is neither.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct PathKind {
    /// The path is a regular file.
    pub is_file: bool,
    /// The path is a directory.
    pub is_dir: bool,
}

impl PathKind {
    /// A path that is neither a file nor a directory.
    pub const NONE: Self = Self {
        is_file: false,
        is_dir: false,
    };
    /// A regular file.
    pub const FILE: Self = Self {
        is_file: true,
        is_dir: false,
    };
    /// A directory.
    pub const DIR: Self = Self {
        is_file: false,
        is_dir: true,
    };
}

/// Read-only file system access used by discovery.
pub trait FileSystem: Send + Sync {
    /// Reads a UTF-8 file.
    ///
    /// # Errors
    /// Any IO error from reading the file.
    fn read_to_string(&self, path: &Path) -> io::Result<Arc<str>>;
    /// Lists a directory, sorted by path.
    ///
    /// # Errors
    /// Any IO error from listing the directory.
    fn read_dir(&self, path: &Path) -> io::Result<Vec<DirEntry>>;
    /// Lists a directory like [`FileSystem::read_dir`], as a shared slice.
    ///
    /// Caching implementations hand out the listing they hold instead of copying it.
    ///
    /// # Errors
    /// Any IO error from listing the directory.
    fn read_dir_shared(&self, path: &Path) -> io::Result<Arc<[DirEntry]>> {
        self.read_dir(path).map(Arc::from)
    }
    /// Whether `path` is a regular file.
    fn is_file(&self, path: &Path) -> bool;
    /// Whether `path` is a directory.
    fn is_dir(&self, path: &Path) -> bool;
    /// What `path` is, in one query.
    ///
    /// The default asks [`FileSystem::is_file`] and then [`FileSystem::is_dir`]; an implementation that can answer both
    /// with one lookup (a `stat`) overrides it. An implementation that answers `is_file` or `is_dir` through `kind`
    /// must override `kind` as well.
    fn kind(&self, path: &Path) -> PathKind {
        let is_file = self.is_file(path);
        PathKind {
            is_file,
            is_dir: !is_file && self.is_dir(path),
        }
    }
    /// `path` as the file system resolves it: absolute, with every symbolic link followed.
    ///
    /// The default returns `path` unchanged, which is right for a tree that has no links (such as [`MemoryFs`]).
    ///
    /// # Errors
    /// Any IO error from resolving the path, such as it not existing.
    fn canonicalize(&self, path: &Path) -> io::Result<PathBuf> {
        Ok(path.to_path_buf())
    }
    /// Reads a file as raw bytes, for files that are not UTF-8.
    ///
    /// The default reads the file as text, so it fails for text that is not valid UTF-8.
    ///
    /// # Errors
    /// Any IO error from reading the file.
    fn read_bytes(&self, path: &Path) -> io::Result<Vec<u8>> {
        self.read_to_string(path).map(|text| text.as_bytes().to_vec())
    }
    /// Reads at most `limit` bytes from the start of a file, for a caller that inspects only its first lines. Fewer
    /// bytes than `limit` means the whole file was read.
    ///
    /// The default reads the whole file with [`FileSystem::read_bytes`] and keeps its first `limit` bytes; an
    /// implementation that can stop reading early overrides it.
    ///
    /// # Errors
    /// Any IO error from reading the file.
    fn read_prefix(&self, path: &Path, limit: usize) -> io::Result<Vec<u8>> {
        self.read_bytes(path).map(|mut bytes| {
            bytes.truncate(limit);
            bytes
        })
    }
    /// When the file at `path` was last modified; `None` when the file system cannot tell (the default), which a
    /// staleness check must treat as "unknown".
    fn modified(&self, path: &Path) -> Option<SystemTime> {
        let _ = path;
        None
    }
}

/// Forwards every [`FileSystem`] method to the target of a pointer type, so `&F`, `Box<F>` and `Arc<F>` can be used
/// wherever a file system is expected.
macro_rules! forward_file_system {
    ($($pointer:ty),+ $(,)?) => {$(
        impl<F: FileSystem + ?Sized> FileSystem for $pointer {
            fn read_to_string(&self, path: &Path) -> io::Result<Arc<str>> {
                (**self).read_to_string(path)
            }

            fn read_dir(&self, path: &Path) -> io::Result<Vec<DirEntry>> {
                (**self).read_dir(path)
            }

            fn read_dir_shared(&self, path: &Path) -> io::Result<Arc<[DirEntry]>> {
                (**self).read_dir_shared(path)
            }

            fn is_file(&self, path: &Path) -> bool {
                (**self).is_file(path)
            }

            fn is_dir(&self, path: &Path) -> bool {
                (**self).is_dir(path)
            }

            fn kind(&self, path: &Path) -> PathKind {
                (**self).kind(path)
            }

            fn canonicalize(&self, path: &Path) -> io::Result<PathBuf> {
                (**self).canonicalize(path)
            }

            fn read_bytes(&self, path: &Path) -> io::Result<Vec<u8>> {
                (**self).read_bytes(path)
            }

            fn read_prefix(&self, path: &Path, limit: usize) -> io::Result<Vec<u8>> {
                (**self).read_prefix(path, limit)
            }

            fn modified(&self, path: &Path) -> Option<SystemTime> {
                (**self).modified(path)
            }
        }
    )+};
}

forward_file_system!(&F, Box<F>, Arc<F>);

/// The real file system.
#[derive(Debug, Clone, Copy, Default)]
pub struct OsFs;

impl FileSystem for OsFs {
    fn read_to_string(&self, path: &Path) -> io::Result<Arc<str>> {
        let bytes = std::fs::read(path)?;
        // Validated with SIMD, several times faster than `str::from_utf8` on the large files a workspace holds; the
        // error is the one `fs::read_to_string` gives.
        let text = simdutf8::basic::from_utf8(&bytes)
            .map_err(|_| io::Error::new(io::ErrorKind::InvalidData, "stream did not contain valid UTF-8"))?;
        Ok(Arc::from(text))
    }

    fn read_dir(&self, path: &Path) -> io::Result<Vec<DirEntry>> {
        let mut entries = Vec::new();
        for entry in std::fs::read_dir(path)? {
            // An entry that vanished between the listing and the lookup, or cannot be read, is skipped; it must not
            // hide its siblings.
            let Ok(entry) = entry else { continue };
            let path = entry.path();
            // `file_type` comes from the directory record; only a symlink needs a `stat` to learn its target. When the
            // record has no type, a `stat` answers as it would for a probe of the path, so the entry is not lost.
            let (is_dir, is_file, is_symlink) = match entry.file_type() {
                Ok(file_type) if file_type.is_symlink() => {
                    let (is_dir, is_file) = std::fs::metadata(&path)
                        .map_or((false, false), |metadata| (metadata.is_dir(), metadata.is_file()));
                    (is_dir, is_file, true)
                }
                Ok(file_type) => (file_type.is_dir(), file_type.is_file(), false),
                Err(_) => match std::fs::metadata(&path) {
                    Ok(metadata) => (metadata.is_dir(), metadata.is_file(), false),
                    Err(_) => continue,
                },
            };
            let entry = DirEntry::new(path, is_dir, is_file);
            entries.push(if is_symlink { entry.symlink() } else { entry });
        }
        // Entries share one parent, so comparing the raw paths orders them like the component-wise `Path` order
        // without parsing components on every comparison.
        entries.sort_unstable_by(|a, b| a.path.as_os_str().cmp(b.path.as_os_str()));
        Ok(entries)
    }

    fn is_file(&self, path: &Path) -> bool {
        path.is_file()
    }

    fn is_dir(&self, path: &Path) -> bool {
        path.is_dir()
    }

    fn kind(&self, path: &Path) -> PathKind {
        std::fs::metadata(path).map_or(PathKind::NONE, |metadata| PathKind {
            is_file: metadata.is_file(),
            is_dir: metadata.is_dir(),
        })
    }

    fn canonicalize(&self, path: &Path) -> io::Result<PathBuf> {
        std::fs::canonicalize(path)
    }

    fn read_bytes(&self, path: &Path) -> io::Result<Vec<u8>> {
        std::fs::read(path)
    }

    fn read_prefix(&self, path: &Path, limit: usize) -> io::Result<Vec<u8>> {
        let mut head = Vec::new();
        std::fs::File::open(path)?
            .take(u64::try_from(limit).unwrap_or(u64::MAX))
            .read_to_end(&mut head)?;
        Ok(head)
    }

    fn modified(&self, path: &Path) -> Option<SystemTime> {
        std::fs::metadata(path).and_then(|metadata| metadata.modified()).ok()
    }
}

/// An in-memory file tree for tests and embedders. Directories exist implicitly as parents of files.
///
/// Paths order component-wise, so everything below a directory is one contiguous range of the map; listing and
/// directory checks are range queries rather than scans of the whole tree.
#[derive(Debug, Clone, Default)]
pub struct MemoryFs {
    files: BTreeMap<PathBuf, Arc<str>>,
}

impl MemoryFs {
    /// An empty tree.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Adds a file, builder style.
    #[must_use]
    pub fn with_file(mut self, path: impl Into<PathBuf>, content: impl AsRef<str>) -> Self {
        self.insert(path, content);
        self
    }

    /// Adds or replaces a file.
    pub fn insert(&mut self, path: impl Into<PathBuf>, content: impl AsRef<str>) {
        self.files.insert(path.into(), Arc::from(content.as_ref()));
    }

    /// The files strictly below `dir`.
    fn below<'a>(&'a self, dir: &'a Path) -> impl Iterator<Item = &'a PathBuf> + 'a {
        self.files
            .range::<Path, _>((Bound::Included(dir), Bound::Unbounded))
            .map(|(path, _)| path)
            .take_while(move |path| path.starts_with(dir))
            .filter(move |path| path.as_path() != dir)
    }
}

fn not_found(path: &Path) -> io::Error {
    io::Error::new(io::ErrorKind::NotFound, format!("{} not found", path.display()))
}

impl FileSystem for MemoryFs {
    fn read_to_string(&self, path: &Path) -> io::Result<Arc<str>> {
        self.files.get(path).cloned().ok_or_else(|| not_found(path))
    }

    fn read_dir(&self, path: &Path) -> io::Result<Vec<DirEntry>> {
        let mut children: BTreeMap<PathBuf, (bool, bool)> = BTreeMap::new();
        for file in self.below(path) {
            let Ok(rest) = file.strip_prefix(path) else { continue };
            let mut components = rest.components();
            let Some(first) = components.next() else { continue };
            let is_file = components.next().is_none();
            let flags = children.entry(path.join(first.as_os_str())).or_default();
            if is_file {
                flags.1 = true;
            } else {
                flags.0 = true;
            }
        }
        if children.is_empty() {
            return Err(not_found(path));
        }
        Ok(children
            .into_iter()
            .map(|(path, (is_dir, is_file))| DirEntry::new(path, is_dir, is_file))
            .collect())
    }

    fn is_file(&self, path: &Path) -> bool {
        self.files.contains_key(path)
    }

    fn is_dir(&self, path: &Path) -> bool {
        self.below(path).next().is_some()
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;

    fn tree() -> MemoryFs {
        MemoryFs::new()
            .with_file("/ws/a/package.json", "{}")
            .with_file("/ws/a/src/index.js", "")
            .with_file("/ws/a-b/package.json", "{}")
            .with_file("/ws/ab", "file")
            .with_file("/ws/z/package.json", "{}")
    }

    fn names(entries: &[DirEntry]) -> Vec<(String, bool, bool)> {
        entries
            .iter()
            .map(|e| {
                (
                    e.path.file_name().unwrap().to_string_lossy().into_owned(),
                    e.is_dir,
                    e.is_file,
                )
            })
            .collect()
    }

    #[test]
    fn memory_listing_is_a_sorted_range_that_ignores_prefix_siblings() {
        let fs = tree();
        assert_eq!(
            names(&fs.read_dir(Path::new("/ws")).unwrap()),
            [
                ("a".into(), true, false),
                ("a-b".into(), true, false),
                ("ab".into(), false, true),
                ("z".into(), true, false)
            ]
        );
        assert_eq!(
            names(&fs.read_dir(Path::new("/ws/a")).unwrap()),
            [("package.json".into(), false, true), ("src".into(), true, false)]
        );
    }

    #[test]
    fn memory_missing_and_file_paths_are_not_directories() {
        let fs = tree();
        assert!(fs.read_dir(Path::new("/ws/missing")).is_err());
        assert!(fs.read_dir(Path::new("/ws/ab")).is_err());
        assert!(fs.is_dir(Path::new("/ws/a")) && fs.is_dir(Path::new("/ws/a/src")) && fs.is_dir(Path::new("/ws")));
        assert!(!fs.is_dir(Path::new("/ws/ab")) && !fs.is_dir(Path::new("/ws/a/sr")) && !fs.is_dir(Path::new("/x")));
        assert!(fs.is_file(Path::new("/ws/ab")) && !fs.is_file(Path::new("/ws/a")));
    }

    #[test]
    fn memory_reads_share_one_allocation() {
        let fs = tree();
        let first = fs.read_to_string(Path::new("/ws/ab")).unwrap();
        let second = fs.read_to_string(Path::new("/ws/ab")).unwrap();
        assert_eq!(&*first, "file");
        assert!(Arc::ptr_eq(&first, &second));
        assert_eq!(
            fs.read_to_string(Path::new("/nope")).unwrap_err().kind(),
            io::ErrorKind::NotFound
        );
    }

    #[test]
    fn a_prefix_read_stops_at_the_limit_or_the_end_of_the_file() {
        let dir = tempfile::tempdir().unwrap();
        let path = dir.path().join("yarn.lock");
        std::fs::write(&path, "0123456789").unwrap();
        let memory = MemoryFs::new().with_file("/ws/yarn.lock", "0123456789");
        let memory_path = Path::new("/ws/yarn.lock");
        for (limit, expected) in [(0, ""), (4, "0123"), (10, "0123456789"), (64, "0123456789")] {
            assert_eq!(OsFs.read_prefix(&path, limit).unwrap(), expected.as_bytes(), "{limit}");
            assert_eq!(
                memory.read_prefix(memory_path, limit).unwrap(),
                expected.as_bytes(),
                "{limit}"
            );
        }
        assert_eq!(
            OsFs.read_prefix(&dir.path().join("missing"), 4).unwrap_err().kind(),
            io::ErrorKind::NotFound
        );
        assert!(memory.read_prefix(Path::new("/ws/missing"), 4).is_err());
    }

    #[test]
    fn os_listing_reports_kinds_sorted() {
        let dir = tempfile::tempdir().unwrap();
        std::fs::create_dir(dir.path().join("sub")).unwrap();
        std::fs::write(dir.path().join("b.txt"), "hello").unwrap();
        std::fs::write(dir.path().join("a.txt"), "").unwrap();
        let entries = OsFs.read_dir(dir.path()).unwrap();
        assert_eq!(
            names(&entries),
            [
                ("a.txt".into(), false, true),
                ("b.txt".into(), false, true),
                ("sub".into(), true, false)
            ]
        );
        assert_eq!(&*OsFs.read_to_string(&dir.path().join("b.txt")).unwrap(), "hello");
        assert!(OsFs.is_dir(dir.path()) && OsFs.is_file(&dir.path().join("a.txt")));
    }

    #[test]
    fn os_reads_fail_on_invalid_utf8_as_the_standard_library_does() {
        let dir = tempfile::tempdir().unwrap();
        let text = "r\u{e9}act \u{65e5}\u{672c} \u{1f600}\n";
        std::fs::write(dir.path().join("valid.txt"), text).unwrap();
        assert_eq!(&*OsFs.read_to_string(&dir.path().join("valid.txt")).unwrap(), text);
        for bytes in [&b"ok \xff"[..], b"\xc3", b"a\xed\xa0\x80b"] {
            let path = dir.path().join("invalid.txt");
            std::fs::write(&path, bytes).unwrap();
            let ours = OsFs.read_to_string(&path).unwrap_err();
            let expected = std::fs::read_to_string(&path).unwrap_err();
            assert_eq!(ours.kind(), io::ErrorKind::InvalidData, "{bytes:?}");
            assert_eq!(
                (ours.kind(), ours.to_string()),
                (expected.kind(), expected.to_string()),
                "{bytes:?}"
            );
        }
        assert_eq!(
            OsFs.read_to_string(&dir.path().join("missing.txt")).unwrap_err().kind(),
            io::ErrorKind::NotFound
        );
    }

    #[cfg(unix)]
    #[test]
    fn os_listing_marks_symlinks() {
        let dir = tempfile::tempdir().unwrap();
        std::fs::create_dir(dir.path().join("real")).unwrap();
        std::os::unix::fs::symlink(dir.path().join("real"), dir.path().join("link")).unwrap();
        let flags: Vec<(String, bool)> = OsFs
            .read_dir(dir.path())
            .unwrap()
            .iter()
            .map(|e| (e.path.file_name().unwrap().to_string_lossy().into_owned(), e.is_symlink))
            .collect();
        assert_eq!(flags, [("link".to_owned(), true), ("real".to_owned(), false)]);
    }

    #[test]
    fn memory_entries_are_not_symlinks() {
        let entries = tree().read_dir(Path::new("/ws")).unwrap();
        assert!(entries.iter().all(|entry| !entry.is_symlink));
    }

    #[cfg(unix)]
    #[test]
    fn os_listing_follows_symlinks() {
        let dir = tempfile::tempdir().unwrap();
        std::fs::create_dir(dir.path().join("real")).unwrap();
        std::fs::write(dir.path().join("file.txt"), "").unwrap();
        std::os::unix::fs::symlink(dir.path().join("real"), dir.path().join("dir-link")).unwrap();
        std::os::unix::fs::symlink(dir.path().join("file.txt"), dir.path().join("file-link")).unwrap();
        std::os::unix::fs::symlink(dir.path().join("gone"), dir.path().join("dangling")).unwrap();
        let entries = OsFs.read_dir(dir.path()).unwrap();
        assert_eq!(
            names(&entries),
            [
                ("dangling".into(), false, false),
                ("dir-link".into(), true, false),
                ("file-link".into(), false, true),
                ("file.txt".into(), false, true),
                ("real".into(), true, false)
            ]
        );
    }

    #[test]
    fn pointers_to_a_file_system_are_file_systems() {
        fn is_file(fs: impl FileSystem, path: &str) -> bool {
            fs.is_file(Path::new(path))
        }
        let fs = tree();
        assert!(is_file(&fs, "/ws/ab"));
        assert!(is_file(Box::new(fs.clone()), "/ws/ab"));
        assert!(is_file(Arc::new(fs.clone()), "/ws/ab"));
        let dynamic: Arc<dyn FileSystem> = Arc::new(fs);
        assert!(is_file(Arc::clone(&dynamic), "/ws/ab"));
        assert!(!is_file(dynamic, "/ws/a"));
    }

    #[test]
    fn bytes_default_to_the_text_and_modification_time_to_unknown() {
        let fs = tree();
        assert_eq!(fs.read_bytes(Path::new("/ws/ab")).unwrap(), b"file");
        assert_eq!(fs.modified(Path::new("/ws/ab")), None);
        let dir = tempfile::tempdir().unwrap();
        std::fs::write(dir.path().join("a.bin"), [0xff, 0xfe]).unwrap();
        assert_eq!(OsFs.read_bytes(&dir.path().join("a.bin")).unwrap(), [0xff, 0xfe]);
        assert!(OsFs.modified(&dir.path().join("a.bin")).is_some());
        assert!(OsFs.modified(&dir.path().join("missing")).is_none());
    }
}