kaish-vfs 0.8.2

//! In-memory filesystem implementation.
//!
//! Used for `/v` and testing. All data is ephemeral.

use crate::budget::ByteBudget;
use crate::traits::{DirEntry, DirEntryKind, Filesystem};
use async_trait::async_trait;
use std::collections::HashMap;
use std::io;
use std::path::{Path, PathBuf};
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use std::time::SystemTime;
use tokio::sync::RwLock;

/// Entry in the memory filesystem.
#[derive(Debug, Clone)]
enum Entry {
    File { data: Vec<u8>, modified: SystemTime },
    Directory { modified: SystemTime },
    Symlink { target: PathBuf, modified: SystemTime },
}

/// In-memory filesystem.
///
/// Thread-safe via internal `RwLock`. All data is lost when dropped.
/// Tracks its resident content bytes exactly (net: an overwrite charges the
/// delta, a remove credits) and optionally draws them from a shared
/// [`ByteBudget`].
#[derive(Debug)]
pub struct MemoryFs {
    entries: RwLock<HashMap<PathBuf, Entry>>,
    resident: AtomicU64,
    budget: Option<Arc<ByteBudget>>,
}

impl Default for MemoryFs {
    fn default() -> Self {
        Self::new()
    }
}

impl MemoryFs {
    /// Create a new empty in-memory filesystem.
    pub fn new() -> Self {
        Self::build(None)
    }

    /// Create a filesystem whose content bytes draw on a shared budget.
    /// Writes that would exceed it fail loudly, ENOSPC-style.
    pub fn with_budget(budget: Arc<ByteBudget>) -> Self {
        Self::build(Some(budget))
    }

    fn build(budget: Option<Arc<ByteBudget>>) -> Self {
        let mut entries = HashMap::new();
        // Root directory always exists
        entries.insert(
            PathBuf::from(""),
            Entry::Directory {
                modified: SystemTime::now(),
            },
        );
        Self {
            entries: RwLock::new(entries),
            resident: AtomicU64::new(0),
            budget,
        }
    }

    /// Content bytes of a file entry; directories and symlinks count zero.
    fn file_len(entry: Option<&Entry>) -> u64 {
        match entry {
            Some(Entry::File { data, .. }) => data.len() as u64,
            _ => 0,
        }
    }

    /// Reserve budget for a growth *before* mutating, so a refused charge
    /// leaves the filesystem untouched.
    fn charge_grow(&self, old: u64, new: u64) -> io::Result<()> {
        if new > old
            && let Some(budget) = &self.budget
        {
            budget.try_charge(new - old)?;
        }
        Ok(())
    }

    /// Apply the net byte delta after a successful mutation: bump the
    /// resident counter and return shrinkage to the budget.
    fn settle(&self, old: u64, new: u64) {
        if new >= old {
            self.resident.fetch_add(new - old, Ordering::AcqRel);
        } else {
            let shrink = old - new;
            let previous = self.resident.fetch_sub(shrink, Ordering::AcqRel);
            assert!(
                previous >= shrink,
                "MemoryFs resident counter underflow: {} - {} — accounting bug",
                previous,
                shrink
            );
            if let Some(budget) = &self.budget {
                budget.credit(shrink);
            }
        }
    }

    /// Normalize a path: remove leading `/`, resolve `.` and `..`.
    fn normalize(path: &Path) -> PathBuf {
        crate::paths::normalize(path)
    }

    /// Maximum symlink follow depth (matches Linux ELOOP limit).
    const MAX_SYMLINK_DEPTH: usize = 40;

    /// Read a file, following symlinks with depth limit.
    fn read_inner(&self, path: &Path, depth: usize) -> std::pin::Pin<Box<dyn std::future::Future<Output = io::Result<Vec<u8>>> + Send + '_>> {
        let path = path.to_path_buf();
        Box::pin(async move {
            if depth > Self::MAX_SYMLINK_DEPTH {
                return Err(io::Error::other(
                    "too many levels of symbolic links",
                ));
            }
            let normalized = Self::normalize(&path);
            let entries = self.entries.read().await;

            match entries.get(&normalized) {
                Some(Entry::File { data, .. }) => Ok(data.clone()),
                Some(Entry::Directory { .. }) => Err(io::Error::new(
                    io::ErrorKind::IsADirectory,
                    format!("is a directory: {}", path.display()),
                )),
                Some(Entry::Symlink { target, .. }) => {
                    let target = target.clone();
                    drop(entries);
                    self.read_inner(&target, depth + 1).await
                }
                None => Err(io::Error::new(
                    io::ErrorKind::NotFound,
                    format!("not found: {}", path.display()),
                )),
            }
        })
    }

    /// Stat a file, following symlinks with depth limit.
    /// Returns a DirEntry with a placeholder name (caller should override).
    fn stat_inner(&self, path: &Path, depth: usize) -> std::pin::Pin<Box<dyn std::future::Future<Output = io::Result<DirEntry>> + Send + '_>> {
        let path = path.to_path_buf();
        Box::pin(async move {
            if depth > Self::MAX_SYMLINK_DEPTH {
                return Err(io::Error::other(
                    "too many levels of symbolic links",
                ));
            }
            let normalized = Self::normalize(&path);

            if normalized.as_os_str().is_empty() {
                return Ok(DirEntry {
                    name: String::new(),
                    kind: DirEntryKind::Directory,
                    size: 0,
                    modified: Some(SystemTime::now()),
                    permissions: None,
                    symlink_target: None,
                });
            }

            let entry_info: Option<(DirEntry, Option<PathBuf>)> = {
                let entries = self.entries.read().await;
                match entries.get(&normalized) {
                    Some(Entry::File { data, modified }) => Some((
                        DirEntry {
                            name: String::new(),
                            kind: DirEntryKind::File,
                            size: data.len() as u64,
                            modified: Some(*modified),
                            permissions: None,
                            symlink_target: None,
                        },
                        None,
                    )),
                    Some(Entry::Directory { modified }) => Some((
                        DirEntry {
                            name: String::new(),
                            kind: DirEntryKind::Directory,
                            size: 0,
                            modified: Some(*modified),
                            permissions: None,
                            symlink_target: None,
                        },
                        None,
                    )),
                    Some(Entry::Symlink { target, .. }) => Some((
                        DirEntry {
                            name: String::new(),
                            kind: DirEntryKind::File, // placeholder, will be overridden
                            size: 0,
                            modified: None,
                            permissions: None,
                            symlink_target: None,
                        },
                        Some(target.clone()),
                    )),
                    None => None,
                }
            };

            match entry_info {
                Some((entry, None)) => Ok(entry),
                Some((_, Some(target))) => self.stat_inner(&target, depth + 1).await,
                None => Err(io::Error::new(
                    io::ErrorKind::NotFound,
                    format!("not found: {}", path.display()),
                )),
            }
        })
    }

    /// Ensure all parent directories of `path` exist, operating on an
    /// already-held write guard.
    ///
    /// Callers acquire `self.entries.write()` once and perform both the
    /// parent-creation and the actual mutation (insert/remove) under that
    /// single guard. Previously `ensure_parents` took and released its own
    /// lock, leaving a TOCTOU window in which a concurrent task could remove
    /// or replace a parent directory between the setup and the mutation
    /// (affected `write`, `mkdir`, `symlink`, `rename`). Folding it into the
    /// caller's guard closes that window.
    fn ensure_parents_locked(
        entries: &mut HashMap<PathBuf, Entry>,
        path: &Path,
    ) -> io::Result<()> {
        let mut current = PathBuf::new();
        for component in path.parent().into_iter().flat_map(|p| p.components()) {
            if let std::path::Component::Normal(s) = component {
                current.push(s);
                match entries.entry(current.clone()) {
                    std::collections::hash_map::Entry::Occupied(e) => {
                        if matches!(e.get(), Entry::File { .. }) {
                            return Err(io::Error::new(
                                io::ErrorKind::NotADirectory,
                                format!("not a directory: {}", current.display()),
                            ));
                        }
                    }
                    std::collections::hash_map::Entry::Vacant(e) => {
                        e.insert(Entry::Directory {
                            modified: SystemTime::now(),
                        });
                    }
                }
            }
        }
        Ok(())
    }
}

/// Credit resident content bytes back to the shared budget when the
/// filesystem is dropped. Without this, dropping a budgeted `MemoryFs` (e.g.
/// the upper inside a dropped `over_with_budget` overlay, or a fork's fresh
/// upper) strands its charge: repeated create-then-drop cycles drain the
/// shared `ByteBudget` toward spurious `StorageFull` with zero actual RAM
/// held. Mirrors `OverlayFs`'s drop of its base-snapshot bytes.
impl Drop for MemoryFs {
    fn drop(&mut self) {
        let bytes = self.resident.load(Ordering::Acquire);
        if bytes > 0
            && let Some(budget) = &self.budget
        {
            budget.credit(bytes);
        }
    }
}

#[async_trait]
impl Filesystem for MemoryFs {
    async fn read(&self, path: &Path) -> io::Result<Vec<u8>> {
        self.read_inner(path, 0).await
    }

    async fn write(&self, path: &Path, data: &[u8]) -> io::Result<()> {
        let normalized = Self::normalize(path);

        let mut entries = self.entries.write().await;

        // Ensure parent directories exist (under the same guard — no TOCTOU)
        Self::ensure_parents_locked(&mut entries, &normalized)?;

        // Check we're not overwriting a directory
        if let Some(Entry::Directory { .. }) = entries.get(&normalized) {
            return Err(io::Error::new(
                io::ErrorKind::IsADirectory,
                format!("is a directory: {}", path.display()),
            ));
        }

        let old_len = Self::file_len(entries.get(&normalized));
        let new_len = data.len() as u64;
        self.charge_grow(old_len, new_len)?;

        entries.insert(
            normalized,
            Entry::File {
                data: data.to_vec(),
                modified: SystemTime::now(),
            },
        );
        self.settle(old_len, new_len);
        Ok(())
    }

    async fn set_mtime(&self, path: &Path, mtime: SystemTime) -> io::Result<()> {
        let normalized = Self::normalize(path);
        let mut entries = self.entries.write().await;
        match entries.get_mut(&normalized) {
            Some(Entry::File { modified, .. })
            | Some(Entry::Directory { modified })
            | Some(Entry::Symlink { modified, .. }) => {
                *modified = mtime;
                Ok(())
            }
            None => Err(io::Error::new(
                io::ErrorKind::NotFound,
                format!("no such file or directory: {}", path.display()),
            )),
        }
    }

    async fn list(&self, path: &Path) -> io::Result<Vec<DirEntry>> {
        let normalized = Self::normalize(path);
        let entries = self.entries.read().await;

        // Verify the path is a directory
        match entries.get(&normalized) {
            Some(Entry::Directory { .. }) => {}
            Some(Entry::File { .. }) => {
                return Err(io::Error::new(
                    io::ErrorKind::NotADirectory,
                    format!("not a directory: {}", path.display()),
                ))
            }
            Some(Entry::Symlink { .. }) => {
                return Err(io::Error::new(
                    io::ErrorKind::NotADirectory,
                    format!("not a directory: {}", path.display()),
                ))
            }
            None if normalized.as_os_str().is_empty() => {
                // Root directory
            }
            None => {
                return Err(io::Error::new(
                    io::ErrorKind::NotFound,
                    format!("not found: {}", path.display()),
                ))
            }
        }

        // Find all direct children
        let prefix = if normalized.as_os_str().is_empty() {
            PathBuf::new()
        } else {
            normalized.clone()
        };

        let mut result = Vec::new();
        for (entry_path, entry) in entries.iter() {
            if let Some(parent) = entry_path.parent()
                && parent == prefix && entry_path != &normalized
                    && let Some(name) = entry_path.file_name() {
                        let (kind, size, modified, symlink_target) = match entry {
                            Entry::File { data, modified } => (DirEntryKind::File, data.len() as u64, Some(*modified), None),
                            Entry::Directory { modified } => (DirEntryKind::Directory, 0, Some(*modified), None),
                            Entry::Symlink { target, modified } => (DirEntryKind::Symlink, 0, Some(*modified), Some(target.clone())),
                        };
                        result.push(DirEntry {
                            name: name.to_string_lossy().into_owned(),
                            kind,
                            size,
                            modified,
                            permissions: None,
                            symlink_target,
                        });
                    }
        }

        // Sort for consistent ordering
        result.sort_by(|a, b| a.name.cmp(&b.name));
        Ok(result)
    }

    async fn stat(&self, path: &Path) -> io::Result<DirEntry> {
        let mut entry = self.stat_inner(path, 0).await?;
        // Set name from the requested path
        let normalized = Self::normalize(path);
        entry.name = normalized
            .file_name()
            .map(|n| n.to_string_lossy().into_owned())
            .unwrap_or_else(|| "/".to_string());
        Ok(entry)
    }

    async fn lstat(&self, path: &Path) -> io::Result<DirEntry> {
        let normalized = Self::normalize(path);

        let name = normalized
            .file_name()
            .map(|n| n.to_string_lossy().into_owned())
            .unwrap_or_else(|| "/".to_string());

        let entries = self.entries.read().await;

        // Handle root directory
        if normalized.as_os_str().is_empty() {
            return Ok(DirEntry {
                name,
                kind: DirEntryKind::Directory,
                size: 0,
                modified: Some(SystemTime::now()),
                permissions: None,
                symlink_target: None,
            });
        }

        match entries.get(&normalized) {
            Some(Entry::File { data, modified }) => Ok(DirEntry {
                name,
                kind: DirEntryKind::File,
                size: data.len() as u64,
                modified: Some(*modified),
                permissions: None,
                symlink_target: None,
            }),
            Some(Entry::Directory { modified }) => Ok(DirEntry {
                name,
                kind: DirEntryKind::Directory,
                size: 0,
                modified: Some(*modified),
                permissions: None,
                symlink_target: None,
            }),
            Some(Entry::Symlink { target, modified }) => Ok(DirEntry {
                name,
                kind: DirEntryKind::Symlink,
                size: 0,
                modified: Some(*modified),
                permissions: None,
                symlink_target: Some(target.clone()),
            }),
            None => Err(io::Error::new(
                io::ErrorKind::NotFound,
                format!("not found: {}", path.display()),
            )),
        }
    }

    async fn read_link(&self, path: &Path) -> io::Result<PathBuf> {
        let normalized = Self::normalize(path);
        let entries = self.entries.read().await;

        match entries.get(&normalized) {
            Some(Entry::Symlink { target, .. }) => Ok(target.clone()),
            Some(_) => Err(io::Error::new(
                io::ErrorKind::InvalidInput,
                format!("not a symbolic link: {}", path.display()),
            )),
            None => Err(io::Error::new(
                io::ErrorKind::NotFound,
                format!("not found: {}", path.display()),
            )),
        }
    }

    async fn symlink(&self, target: &Path, link: &Path) -> io::Result<()> {
        let normalized = Self::normalize(link);

        let mut entries = self.entries.write().await;

        // Ensure parent directories exist (under the same guard — no TOCTOU)
        Self::ensure_parents_locked(&mut entries, &normalized)?;

        // Check if something already exists at this path
        if entries.contains_key(&normalized) {
            return Err(io::Error::new(
                io::ErrorKind::AlreadyExists,
                format!("file exists: {}", link.display()),
            ));
        }

        entries.insert(
            normalized,
            Entry::Symlink {
                target: target.to_path_buf(),
                modified: SystemTime::now(),
            },
        );
        Ok(())
    }

    async fn mkdir(&self, path: &Path) -> io::Result<()> {
        let normalized = Self::normalize(path);

        let mut entries = self.entries.write().await;

        // Ensure parent directories exist (under the same guard — no TOCTOU)
        Self::ensure_parents_locked(&mut entries, &normalized)?;

        // Check if something already exists
        if let Some(existing) = entries.get(&normalized) {
            return match existing {
                Entry::Directory { .. } => Ok(()), // Already exists, fine
                Entry::File { .. } | Entry::Symlink { .. } => Err(io::Error::new(
                    io::ErrorKind::AlreadyExists,
                    format!("file exists: {}", path.display()),
                )),
            };
        }

        entries.insert(
            normalized,
            Entry::Directory {
                modified: SystemTime::now(),
            },
        );
        Ok(())
    }

    async fn remove(&self, path: &Path) -> io::Result<()> {
        let normalized = Self::normalize(path);

        if normalized.as_os_str().is_empty() {
            return Err(io::Error::new(
                io::ErrorKind::PermissionDenied,
                "cannot remove root directory",
            ));
        }

        let mut entries = self.entries.write().await;

        // Check if it's a non-empty directory
        if let Some(Entry::Directory { .. }) = entries.get(&normalized) {
            // Check for children
            let has_children = entries.keys().any(|k| {
                k.parent() == Some(&normalized) && k != &normalized
            });
            if has_children {
                return Err(io::Error::new(
                    io::ErrorKind::DirectoryNotEmpty,
                    format!("directory not empty: {}", path.display()),
                ));
            }
        }

        let removed = entries.remove(&normalized).ok_or_else(|| {
            io::Error::new(
                io::ErrorKind::NotFound,
                format!("not found: {}", path.display()),
            )
        })?;
        self.settle(Self::file_len(Some(&removed)), 0);
        Ok(())
    }

    async fn rename(&self, from: &Path, to: &Path) -> io::Result<()> {
        let from_normalized = Self::normalize(from);
        let to_normalized = Self::normalize(to);

        if from_normalized.as_os_str().is_empty() {
            return Err(io::Error::new(
                io::ErrorKind::PermissionDenied,
                "cannot rename root directory",
            ));
        }

        // Identity rename is a no-op
        if from_normalized == to_normalized {
            return Ok(());
        }

        // Cannot move a directory into itself
        if to_normalized.starts_with(&from_normalized) {
            return Err(io::Error::new(
                io::ErrorKind::InvalidInput,
                format!("cannot move '{}' into itself", from.display()),
            ));
        }

        let mut entries = self.entries.write().await;

        // Ensure parent directories exist for destination (under the same
        // guard — no TOCTOU). Error is intentionally ignored: a missing or
        // file-shaped parent surfaces below as a normal rename failure.
        let _ = Self::ensure_parents_locked(&mut entries, &to_normalized);

        // Get the source entry
        let entry = entries.remove(&from_normalized).ok_or_else(|| {
            io::Error::new(
                io::ErrorKind::NotFound,
                format!("not found: {}", from.display()),
            )
        })?;

        // Check we're not overwriting a directory with a file or vice versa
        if let Some(existing) = entries.get(&to_normalized) {
            match (&entry, existing) {
                (Entry::File { .. }, Entry::Directory { .. }) => {
                    // Put the source back and error
                    entries.insert(from_normalized, entry);
                    return Err(io::Error::new(
                        io::ErrorKind::IsADirectory,
                        format!("destination is a directory: {}", to.display()),
                    ));
                }
                (Entry::Directory { .. }, Entry::File { .. }) => {
                    entries.insert(from_normalized, entry);
                    return Err(io::Error::new(
                        io::ErrorKind::NotADirectory,
                        format!("destination is not a directory: {}", to.display()),
                    ));
                }
                _ => {}
            }
        }

        // A rename moves bytes, net zero — but inserting over an existing
        // dest entry destroys its content, which must be credited back.
        let mut clobbered: u64 = 0;

        // For directories, we need to rename all children too
        if matches!(entry, Entry::Directory { .. }) {
            // Collect paths to rename (can't modify while iterating)
            let children_to_rename: Vec<(PathBuf, Entry)> = entries
                .iter()
                .filter(|(k, _)| k.starts_with(&from_normalized) && *k != &from_normalized)
                .map(|(k, v)| (k.clone(), v.clone()))
                .collect();

            // Remove old children and insert with new paths
            for (old_path, child_entry) in children_to_rename {
                entries.remove(&old_path);
                let Ok(relative) = old_path.strip_prefix(&from_normalized) else {
                    continue;
                };
                let new_path = to_normalized.join(relative);
                clobbered += Self::file_len(entries.get(&new_path));
                entries.insert(new_path, child_entry);
            }
        }

        // Insert at new location
        clobbered += Self::file_len(entries.get(&to_normalized));
        entries.insert(to_normalized, entry);
        self.settle(clobbered, 0);
        Ok(())
    }

    fn read_only(&self) -> bool {
        false
    }

    fn resident_bytes(&self) -> Option<u64> {
        Some(self.resident.load(Ordering::Acquire))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[tokio::test]
    async fn test_write_and_read() {
        let fs = MemoryFs::new();
        fs.write(Path::new("test.txt"), b"hello world").await.unwrap();
        let data = fs.read(Path::new("test.txt")).await.unwrap();
        assert_eq!(data, b"hello world");
    }

    #[tokio::test]
    async fn test_set_mtime_updates_existing() {
        let fs = MemoryFs::new();
        fs.write(Path::new("t.txt"), b"x").await.unwrap();
        let pinned = SystemTime::UNIX_EPOCH + std::time::Duration::from_secs(1_000_000);
        fs.set_mtime(Path::new("t.txt"), pinned).await.unwrap();
        let entry = fs.stat(Path::new("t.txt")).await.unwrap();
        assert_eq!(entry.modified, Some(pinned));
    }

    #[tokio::test]
    async fn test_set_mtime_missing_errors() {
        let fs = MemoryFs::new();
        let result = fs.set_mtime(Path::new("nope.txt"), SystemTime::now()).await;
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotFound);
    }

    #[tokio::test]
    async fn test_read_not_found() {
        let fs = MemoryFs::new();
        let result = fs.read(Path::new("nonexistent.txt")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotFound);
    }

    #[tokio::test]
    async fn test_nested_directories() {
        let fs = MemoryFs::new();
        fs.write(Path::new("a/b/c/file.txt"), b"nested").await.unwrap();

        // Should have created parent directories
        let entry = fs.stat(Path::new("a")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);

        let entry = fs.stat(Path::new("a/b")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);

        let entry = fs.stat(Path::new("a/b/c")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);

        let data = fs.read(Path::new("a/b/c/file.txt")).await.unwrap();
        assert_eq!(data, b"nested");
    }

    #[tokio::test]
    async fn test_list_directory() {
        let fs = MemoryFs::new();
        fs.write(Path::new("a.txt"), b"a").await.unwrap();
        fs.write(Path::new("b.txt"), b"b").await.unwrap();
        fs.mkdir(Path::new("subdir")).await.unwrap();

        let entries = fs.list(Path::new("")).await.unwrap();
        assert_eq!(entries.len(), 3);

        let names: Vec<_> = entries.iter().map(|e| &e.name).collect();
        assert!(names.contains(&&"a.txt".to_string()));
        assert!(names.contains(&&"b.txt".to_string()));
        assert!(names.contains(&&"subdir".to_string()));
    }

    #[tokio::test]
    async fn test_mkdir_and_stat() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("mydir")).await.unwrap();

        let entry = fs.stat(Path::new("mydir")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);
    }

    #[tokio::test]
    async fn test_remove_file() {
        let fs = MemoryFs::new();
        fs.write(Path::new("file.txt"), b"data").await.unwrap();

        fs.remove(Path::new("file.txt")).await.unwrap();

        let result = fs.stat(Path::new("file.txt")).await;
        assert!(result.is_err());
    }

    #[tokio::test]
    async fn test_remove_empty_directory() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("emptydir")).await.unwrap();

        fs.remove(Path::new("emptydir")).await.unwrap();

        let result = fs.stat(Path::new("emptydir")).await;
        assert!(result.is_err());
    }

    #[tokio::test]
    async fn test_remove_non_empty_directory_fails() {
        let fs = MemoryFs::new();
        fs.write(Path::new("dir/file.txt"), b"data").await.unwrap();

        let result = fs.remove(Path::new("dir")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::DirectoryNotEmpty);
    }

    #[tokio::test]
    async fn test_path_normalization() {
        let fs = MemoryFs::new();
        fs.write(Path::new("/a/b/c.txt"), b"data").await.unwrap();

        // Various path forms should all work
        let data1 = fs.read(Path::new("a/b/c.txt")).await.unwrap();
        let data2 = fs.read(Path::new("/a/b/c.txt")).await.unwrap();
        let data3 = fs.read(Path::new("a/./b/c.txt")).await.unwrap();
        let data4 = fs.read(Path::new("a/b/../b/c.txt")).await.unwrap();

        assert_eq!(data1, data2);
        assert_eq!(data2, data3);
        assert_eq!(data3, data4);
    }

    #[tokio::test]
    async fn test_overwrite_file() {
        let fs = MemoryFs::new();
        fs.write(Path::new("file.txt"), b"first").await.unwrap();
        fs.write(Path::new("file.txt"), b"second").await.unwrap();

        let data = fs.read(Path::new("file.txt")).await.unwrap();
        assert_eq!(data, b"second");
    }

    #[tokio::test]
    async fn test_exists() {
        let fs = MemoryFs::new();
        assert!(!fs.exists(Path::new("nope.txt")).await);

        fs.write(Path::new("yes.txt"), b"here").await.unwrap();
        assert!(fs.exists(Path::new("yes.txt")).await);
    }

    #[tokio::test]
    async fn test_rename_file() {
        let fs = MemoryFs::new();
        fs.write(Path::new("old.txt"), b"content").await.unwrap();

        fs.rename(Path::new("old.txt"), Path::new("new.txt")).await.unwrap();

        // New path exists with same content
        let data = fs.read(Path::new("new.txt")).await.unwrap();
        assert_eq!(data, b"content");

        // Old path no longer exists
        assert!(!fs.exists(Path::new("old.txt")).await);
    }

    #[tokio::test]
    async fn test_rename_directory() {
        let fs = MemoryFs::new();
        fs.write(Path::new("dir/a.txt"), b"a").await.unwrap();
        fs.write(Path::new("dir/b.txt"), b"b").await.unwrap();
        fs.write(Path::new("dir/sub/c.txt"), b"c").await.unwrap();

        fs.rename(Path::new("dir"), Path::new("renamed")).await.unwrap();

        // New paths exist
        assert!(fs.exists(Path::new("renamed")).await);
        assert!(fs.exists(Path::new("renamed/a.txt")).await);
        assert!(fs.exists(Path::new("renamed/b.txt")).await);
        assert!(fs.exists(Path::new("renamed/sub/c.txt")).await);

        // Old paths don't exist
        assert!(!fs.exists(Path::new("dir")).await);
        assert!(!fs.exists(Path::new("dir/a.txt")).await);

        // Content preserved
        let data = fs.read(Path::new("renamed/a.txt")).await.unwrap();
        assert_eq!(data, b"a");
    }

    #[tokio::test]
    async fn test_rename_not_found() {
        let fs = MemoryFs::new();
        let result = fs.rename(Path::new("nonexistent"), Path::new("dest")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotFound);
    }

    // --- Symlink tests ---

    #[tokio::test]
    async fn test_symlink_create_and_read_link() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"content").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // read_link returns the raw target
        let target = fs.read_link(Path::new("link.txt")).await.unwrap();
        assert_eq!(target, Path::new("target.txt"));
    }

    #[tokio::test]
    async fn test_symlink_read_follows_link() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"hello from target").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // Reading through symlink should return target's content
        let data = fs.read(Path::new("link.txt")).await.unwrap();
        assert_eq!(data, b"hello from target");
    }

    #[tokio::test]
    async fn test_symlink_stat_follows_link() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"12345").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // stat follows symlinks - should report file metadata
        let entry = fs.stat(Path::new("link.txt")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::File);
        assert_eq!(entry.size, 5);
    }

    #[tokio::test]
    async fn test_symlink_lstat_returns_symlink_info() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"content").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // lstat does not follow symlinks
        let entry = fs.lstat(Path::new("link.txt")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Symlink);
    }

    #[tokio::test]
    async fn test_symlink_in_list() {
        let fs = MemoryFs::new();
        fs.write(Path::new("file.txt"), b"content").await.unwrap();
        fs.symlink(Path::new("file.txt"), Path::new("link.txt")).await.unwrap();
        fs.mkdir(Path::new("dir")).await.unwrap();

        let entries = fs.list(Path::new("")).await.unwrap();
        assert_eq!(entries.len(), 3);

        // Find the symlink entry
        let link_entry = entries.iter().find(|e| e.name == "link.txt").unwrap();
        assert_eq!(link_entry.kind, DirEntryKind::Symlink);
        assert_eq!(link_entry.symlink_target, Some(PathBuf::from("file.txt")));
    }

    #[tokio::test]
    async fn test_symlink_broken_link() {
        let fs = MemoryFs::new();
        // Create symlink to non-existent target
        fs.symlink(Path::new("nonexistent.txt"), Path::new("broken.txt")).await.unwrap();

        // read_link still works
        let target = fs.read_link(Path::new("broken.txt")).await.unwrap();
        assert_eq!(target, Path::new("nonexistent.txt"));

        // lstat works (the symlink exists)
        let entry = fs.lstat(Path::new("broken.txt")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Symlink);

        // stat fails (target doesn't exist)
        let result = fs.stat(Path::new("broken.txt")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotFound);

        // read fails (target doesn't exist)
        let result = fs.read(Path::new("broken.txt")).await;
        assert!(result.is_err());
    }

    #[tokio::test]
    async fn test_symlink_read_link_on_non_symlink_fails() {
        let fs = MemoryFs::new();
        fs.write(Path::new("file.txt"), b"content").await.unwrap();

        let result = fs.read_link(Path::new("file.txt")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::InvalidInput);
    }

    #[tokio::test]
    async fn test_symlink_already_exists() {
        let fs = MemoryFs::new();
        fs.write(Path::new("existing.txt"), b"content").await.unwrap();

        // Can't create symlink over existing file
        let result = fs.symlink(Path::new("target"), Path::new("existing.txt")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::AlreadyExists);
    }

    // --- Edge case tests ---

    #[tokio::test]
    async fn test_symlink_chain() {
        // a -> b -> c -> file.txt
        let fs = MemoryFs::new();
        fs.write(Path::new("file.txt"), b"end of chain").await.unwrap();
        fs.symlink(Path::new("file.txt"), Path::new("c")).await.unwrap();
        fs.symlink(Path::new("c"), Path::new("b")).await.unwrap();
        fs.symlink(Path::new("b"), Path::new("a")).await.unwrap();

        // Reading through chain should work
        let data = fs.read(Path::new("a")).await.unwrap();
        assert_eq!(data, b"end of chain");

        // stat through chain should report file
        let entry = fs.stat(Path::new("a")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::File);
    }

    #[tokio::test]
    async fn test_symlink_to_directory() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("realdir")).await.unwrap();
        fs.write(Path::new("realdir/file.txt"), b"inside dir").await.unwrap();
        fs.symlink(Path::new("realdir"), Path::new("linkdir")).await.unwrap();

        // stat follows symlink - should see directory
        let entry = fs.stat(Path::new("linkdir")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);

        // Note: listing through symlink requires following in list(),
        // which we don't currently support (symlink to dir returns NotADirectory)
    }

    #[tokio::test]
    async fn test_symlink_relative_path_stored_as_is() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("subdir")).await.unwrap();
        fs.write(Path::new("subdir/target.txt"), b"content").await.unwrap();

        // Store a relative path in the symlink
        fs.symlink(Path::new("../subdir/target.txt"), Path::new("subdir/link.txt")).await.unwrap();

        // read_link returns the path as stored
        let target = fs.read_link(Path::new("subdir/link.txt")).await.unwrap();
        assert_eq!(target.to_string_lossy(), "../subdir/target.txt");
    }

    #[tokio::test]
    async fn test_symlink_absolute_path() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"content").await.unwrap();

        // Store absolute path
        fs.symlink(Path::new("/target.txt"), Path::new("link.txt")).await.unwrap();

        let target = fs.read_link(Path::new("link.txt")).await.unwrap();
        assert_eq!(target.to_string_lossy(), "/target.txt");

        // Following should work (normalize strips leading /)
        let data = fs.read(Path::new("link.txt")).await.unwrap();
        assert_eq!(data, b"content");
    }

    #[tokio::test]
    async fn test_symlink_remove() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"content").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // Remove symlink (not the target)
        fs.remove(Path::new("link.txt")).await.unwrap();

        // Symlink gone
        assert!(!fs.exists(Path::new("link.txt")).await);

        // Target still exists
        assert!(fs.exists(Path::new("target.txt")).await);
    }

    #[tokio::test]
    async fn test_symlink_overwrite_target_content() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"original").await.unwrap();
        fs.symlink(Path::new("target.txt"), Path::new("link.txt")).await.unwrap();

        // Modify target
        fs.write(Path::new("target.txt"), b"modified").await.unwrap();

        // Reading through link shows new content
        let data = fs.read(Path::new("link.txt")).await.unwrap();
        assert_eq!(data, b"modified");
    }

    #[tokio::test]
    async fn test_symlink_empty_name() {
        let fs = MemoryFs::new();
        fs.write(Path::new("target.txt"), b"content").await.unwrap();

        // Symlink with empty path components in target
        fs.symlink(Path::new("./target.txt"), Path::new("link.txt")).await.unwrap();

        let target = fs.read_link(Path::new("link.txt")).await.unwrap();
        assert_eq!(target.to_string_lossy(), "./target.txt");
    }

    #[tokio::test]
    async fn test_symlink_nested_creation() {
        let fs = MemoryFs::new();
        // Symlink in non-existent directory should create parents
        fs.symlink(Path::new("target"), Path::new("a/b/c/link")).await.unwrap();

        // Parents created
        let entry = fs.stat(Path::new("a/b")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Directory);

        // Symlink exists (lstat)
        let entry = fs.lstat(Path::new("a/b/c/link")).await.unwrap();
        assert_eq!(entry.kind, DirEntryKind::Symlink);
    }

    #[tokio::test]
    async fn test_symlink_read_link_not_found() {
        let fs = MemoryFs::new();

        let result = fs.read_link(Path::new("nonexistent")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotFound);
    }

    #[tokio::test]
    async fn test_symlink_read_link_on_directory() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("dir")).await.unwrap();

        let result = fs.read_link(Path::new("dir")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::InvalidInput);
    }

    #[tokio::test]
    async fn test_symlink_circular_read_returns_error() {
        // Bug F: circular symlinks should return error, not stack overflow
        let fs = MemoryFs::new();
        fs.symlink(Path::new("b"), Path::new("a")).await.unwrap();
        fs.symlink(Path::new("a"), Path::new("b")).await.unwrap();

        let result = fs.read(Path::new("a")).await;
        assert!(result.is_err());
        let err = result.unwrap_err();
        assert!(
            err.to_string().contains("symbolic links"),
            "expected symlink loop error, got: {}",
            err
        );
    }

    #[tokio::test]
    async fn test_symlink_circular_stat_returns_error() {
        let fs = MemoryFs::new();
        fs.symlink(Path::new("b"), Path::new("a")).await.unwrap();
        fs.symlink(Path::new("a"), Path::new("b")).await.unwrap();

        let result = fs.stat(Path::new("a")).await;
        assert!(result.is_err());
        let err = result.unwrap_err();
        assert!(
            err.to_string().contains("symbolic links"),
            "expected symlink loop error, got: {}",
            err
        );
    }

    #[tokio::test]
    async fn test_rename_into_self_errors() {
        let fs = MemoryFs::new();
        fs.mkdir(Path::new("a")).await.unwrap();

        let result = fs.rename(Path::new("a"), Path::new("a/b")).await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::InvalidInput);
    }

    #[tokio::test]
    async fn test_rename_identity_noop() {
        let fs = MemoryFs::new();
        fs.write(Path::new("a"), b"data").await.unwrap();

        // Renaming to self should succeed as a no-op
        fs.rename(Path::new("a"), Path::new("a")).await.unwrap();

        // Data should still be there
        let data = fs.read(Path::new("a")).await.unwrap();
        assert_eq!(data, b"data");
    }

    // --- Byte accounting tests ---

    #[tokio::test]
    async fn test_resident_bytes_net_accounting() {
        let fs = MemoryFs::new();
        assert_eq!(fs.resident_bytes(), Some(0));

        fs.write(Path::new("a.txt"), b"0123456789").await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(10));

        // Overwrite charges the delta, not the gross.
        fs.write(Path::new("a.txt"), b"0123").await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(4));

        // Directories and symlinks count zero.
        fs.mkdir(Path::new("dir")).await.unwrap();
        fs.symlink(Path::new("a.txt"), Path::new("link")).await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(4));

        // A move is net zero; removing credits.
        fs.rename(Path::new("a.txt"), Path::new("b.txt")).await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(4));
        fs.remove(Path::new("b.txt")).await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(0));
    }

    #[tokio::test]
    async fn test_rename_over_existing_file_credits_clobbered_bytes() {
        let fs = MemoryFs::new();
        fs.write(Path::new("src.txt"), b"123").await.unwrap();
        fs.write(Path::new("dest.txt"), b"1234567").await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(10));

        fs.rename(Path::new("src.txt"), Path::new("dest.txt")).await.unwrap();
        assert_eq!(fs.resident_bytes(), Some(3));
    }

    #[tokio::test]
    async fn test_budget_refusal_leaves_fs_untouched() {
        let budget = Arc::new(ByteBudget::labeled(10, "test-budget"));
        let fs = MemoryFs::with_budget(budget.clone());

        fs.write(Path::new("a.txt"), b"01234567").await.unwrap();
        assert_eq!(budget.used(), 8);

        let error = fs.write(Path::new("b.txt"), b"012").await.unwrap_err();
        assert_eq!(error.kind(), io::ErrorKind::StorageFull);
        assert!(error.to_string().contains("test-budget"));

        // Nothing changed: no b.txt, a.txt intact, counters steady.
        assert!(!fs.exists(Path::new("b.txt")).await);
        assert_eq!(fs.read(Path::new("a.txt")).await.unwrap(), b"01234567");
        assert_eq!(fs.resident_bytes(), Some(8));
        assert_eq!(budget.used(), 8);

        // Shrinking and removing return bytes to the budget.
        fs.write(Path::new("a.txt"), b"0123").await.unwrap();
        assert_eq!(budget.used(), 4);
        fs.remove(Path::new("a.txt")).await.unwrap();
        assert_eq!(budget.used(), 0);
    }

    #[tokio::test]
    async fn test_drop_credits_budget() {
        let budget = Arc::new(ByteBudget::new(100));
        {
            let fs = MemoryFs::with_budget(budget.clone());
            fs.write(Path::new("a.txt"), b"0123456789").await.unwrap();
            assert_eq!(budget.used(), 10);
        }
        // The dropped filesystem returned its bytes to the pool.
        assert_eq!(budget.used(), 0);
    }

    #[tokio::test]
    async fn test_budget_shared_across_filesystems() {
        let budget = Arc::new(ByteBudget::new(10));
        let fs_one = MemoryFs::with_budget(budget.clone());
        let fs_two = MemoryFs::with_budget(budget.clone());

        fs_one.write(Path::new("a"), b"012345").await.unwrap();
        let error = fs_two.write(Path::new("b"), b"01234").await.unwrap_err();
        assert_eq!(error.kind(), io::ErrorKind::StorageFull);

        fs_two.write(Path::new("b"), b"0123").await.unwrap();
        assert_eq!(budget.used(), 10);
        assert_eq!(fs_one.resident_bytes(), Some(6));
        assert_eq!(fs_two.resident_bytes(), Some(4));
    }

    #[tokio::test]
    async fn test_ensure_parents_rejects_file_as_dir() {
        let fs = MemoryFs::new();
        // Create a file at "a"
        fs.write(Path::new("a"), b"I am a file").await.unwrap();

        // Now try to write "a/b" — "a" is a file, not a directory
        let result = fs.write(Path::new("a/b"), b"child").await;
        assert!(result.is_err());
        assert_eq!(result.unwrap_err().kind(), io::ErrorKind::NotADirectory);
    }
}