//! Recursive removal of a linked worktree and its administrative directory.

use std::{
    convert::Infallible,
    fs, io,
    path::{Path, PathBuf},
    sync::atomic::Ordering,
};

use gix_features::{
    parallel::{self, Reduce},
    progress::{NestedProgress, Progress},
};
/// A failure while scanning or deleting one of the removal roots.
#[derive(Debug, thiserror::Error)]
#[error("Could not remove '{path}': {source}")]
pub struct DirectoryError {
    /// The path whose scan or deletion failed.
    pub path: PathBuf,
    /// The underlying filesystem error.
    #[source]
    pub source: io::Error,
}

/// The error returned by [`remove()`].
///
#[derive(Debug, thiserror::Error)]
pub enum Error {
    /// The checkout could not be fully removed, but its private Git directory was removed.
    #[error("Could not fully remove the linked-worktree checkout")]
    Worktree(#[source] DirectoryError),
    /// The private Git directory could not be fully removed, but its checkout was removed.
    #[error("Could not fully remove the linked-worktree administration")]
    GitDir(#[source] DirectoryError),
    /// Neither the checkout nor its private Git directory could be fully removed.
    #[error("Could not fully remove the checkout ({worktree}) or its administration ({git_dir})")]
    Both {
        /// The first checkout-removal error.
        worktree: DirectoryError,
        /// The first administrative-removal error.
        git_dir: DirectoryError,
    },
}

/// Recursively remove `work_dir` and its private `git_dir` without following symbolic links.
///
/// Traversal and leaf deletion use all available threads when the `parallel` feature is enabled.
/// Traversal skips optional metadata, except for directory checks that protect Unix mount boundaries.
/// The private Git directory is removed even if removing the checkout fails. A missing root is
/// considered removed successfully, and an empty parent `worktrees` directory is removed as well.
/// Directory-not-empty races are retried while each pass finds fewer entries, up to three passes.
pub fn remove(
    work_dir: impl AsRef<Path>,
    git_dir: impl AsRef<Path>,
    mut progress: impl NestedProgress,
) -> Result<(), Error> {
    let work_dir = work_dir.as_ref();
    let git_dir = git_dir.as_ref();
    let worktree = remove_root(
        work_dir,
        progress.add_child("scan worktree"),
        progress.add_child("remove worktree"),
    )
    .err();
    let git_dir_error = remove_root(
        git_dir,
        progress.add_child("scan administration"),
        progress.add_child("remove administration"),
    )
    .err();

    if git_dir_error.is_none()
        && let Some(worktrees_dir) = git_dir
            .parent()
            .filter(|dir| dir.file_name().is_some_and(|name| name == "worktrees"))
    {
        // This is intentionally best-effort, like Git: a non-empty directory merely means other
        // linked worktrees remain.
        let _ = fs::remove_dir(worktrees_dir);
    }

    match (worktree, git_dir_error) {
        (None, None) => Ok(()),
        (Some(err), None) => Err(Error::Worktree(err)),
        (None, Some(err)) => Err(Error::GitDir(err)),
        (Some(worktree), Some(git_dir)) => Err(Error::Both { worktree, git_dir }),
    }
}

fn remove_root(root: &Path, scan: impl Progress, remove: impl Progress) -> Result<(), DirectoryError> {
    remove_root_with_after_scan(root, scan, remove, || {})
}

fn remove_root_with_after_scan(
    root: &Path,
    mut scan: impl Progress,
    mut remove: impl Progress,
    mut after_scan: impl FnMut(),
) -> Result<(), DirectoryError> {
    let root = absolute_root(root)?;
    let root = root.as_path();
    scan.init(None, gix_features::progress::count("entries"));
    #[cfg(unix)]
    let containing_device = root
        .parent()
        .and_then(|parent| fs::metadata(parent).ok())
        .map(|metadata| std::os::unix::fs::MetadataExt::dev(&metadata));
    #[cfg(unix)]
    let root_is_filesystem_root = root.parent().is_none();
    #[cfg(unix)]
    let descend = move |entry: &dua_core::Entry| {
        // Failed checks are reported when entries are collected below.
        may_descend(containing_device, root_is_filesystem_root, entry).unwrap_or(false)
    };
    #[cfg(not(unix))]
    let descend = |_: &dua_core::Entry| true;
    let mut walk = dua_core::walk(
        root,
        parallel::num_threads(None),
        dua_core::Order::Completion,
        dua_core::Options::default().skip_metadata(),
        descend,
    );
    let mut previous_entry_count = None;
    for attempt in 0..3 {
        let mut leaves = Vec::new();
        let mut directories = Vec::new();
        #[cfg(unix)]
        let mut retained_mounts = Vec::new();
        let mut first_error = None;
        let mut entry_count = 0;
        for entry in walk.by_ref() {
            entry_count += 1;
            scan.inc();
            match entry {
                Ok(entry) => {
                    let path = entry.path();
                    if entry.file_type.is_dir() {
                        #[cfg(unix)]
                        match may_descend(containing_device, root_is_filesystem_root, &entry) {
                            Ok(true) => {}
                            Ok(false) => retained_mounts.push(path.clone()),
                            Err(source) => {
                                if !gix_fs::io_err::is_not_found(source.kind(), source.raw_os_error()) {
                                    first_error.get_or_insert(DirectoryError { path, source });
                                }
                                continue;
                            }
                        }
                        directories.push((entry.depth, path));
                    } else {
                        leaves.push((path, entry.file_type.is_symlink()));
                    }
                }
                Err(source) if gix_fs::io_err::is_not_found(source.kind(), source.raw_os_error()) => {}
                Err(source) => {
                    first_error.get_or_insert_with(|| DirectoryError {
                        path: root.to_owned(),
                        source,
                    });
                }
            }
        }
        after_scan();

        remove.init(
            Some(leaves.len() + directories.len()),
            gix_features::progress::count("entries"),
        );
        let counter = remove.counter();
        let leaf_error = parallel::in_parallel(
            leaves.into_iter(),
            None,
            |_| (),
            {
                let counter = counter.clone();
                move |(path, is_symlink), _| {
                    let result = remove_leaf(&path, is_symlink);
                    counter.fetch_add(1, Ordering::Relaxed);
                    result
                        .err()
                        .filter(|err| !gix_fs::io_err::is_not_found(err.kind(), err.raw_os_error()))
                        .map(|source| DirectoryError { path, source })
                }
            },
            FirstError::default(),
        )
        .unwrap_or_else(|never| match never {});
        if first_error.is_none() {
            first_error = leaf_error;
        }

        directories.sort_unstable_by_key(|(depth, _)| std::cmp::Reverse(*depth));
        for (_, path) in directories {
            #[cfg(unix)]
            if let Some(mount) = retained_mount(&path, &retained_mounts) {
                // ponytail: mount points are rare; index their ancestors if this scan ever becomes measurable.
                if first_error.is_none() && mount == path {
                    first_error = Some(DirectoryError {
                        path: path.clone(),
                        source: io::Error::other("refusing to remove a mounted filesystem"),
                    });
                }
                remove.inc();
                continue;
            }
            let result = fs::remove_dir(&path);
            remove.inc();
            if first_error.is_none()
                && let Err(source) = result
                && !gix_fs::io_err::is_not_found(source.kind(), source.raw_os_error())
            {
                first_error = Some(DirectoryError { path, source });
            }
        }

        let Some(err) = first_error else {
            return Ok(());
        };
        if err.source.kind() != io::ErrorKind::DirectoryNotEmpty
            || attempt == 2
            || previous_entry_count.is_some_and(|previous| entry_count >= previous)
            || !walk.restart()
        {
            return Err(err);
        }
        previous_entry_count = Some(entry_count);
    }
    unreachable!("the final deletion attempt always returns")
}

fn absolute_root(root: &Path) -> Result<PathBuf, DirectoryError> {
    // Trailing separators make `symlink_metadata()` follow the final symlink.
    let absolute: PathBuf = std::path::absolute(root)
        .map(|path| path.components().collect())
        .map_err(|source| DirectoryError {
            path: root.to_owned(),
            source,
        })?;
    let resolved = match fs::symlink_metadata(&absolute) {
        // Keep file and symlink leaves intact; only directories need root and mount checks.
        Ok(metadata) if !metadata.is_dir() => return Ok(absolute),
        Ok(_) => fs::canonicalize(&absolute),
        Err(source) => Err(source),
    };
    match resolved {
        Ok(path) => Ok(path),
        Err(source) if gix_fs::io_err::is_not_found(source.kind(), source.raw_os_error()) => Ok(absolute),
        Err(source) => Err(DirectoryError { path: absolute, source }),
    }
}

fn remove_leaf(path: &Path, is_symlink: bool) -> io::Result<()> {
    let result = if is_symlink {
        gix_fs::symlink::remove(path)
    } else {
        fs::remove_file(path)
    };
    #[cfg(windows)]
    if !is_symlink
        && result
            .as_ref()
            .is_err_and(|err| err.kind() == io::ErrorKind::PermissionDenied)
    {
        let mut permissions = fs::metadata(path)?.permissions();
        permissions.set_readonly(false);
        fs::set_permissions(path, permissions)?;
        return fs::remove_file(path);
    }
    result
}

#[cfg(unix)]
fn may_descend(
    containing_device: Option<u64>,
    root_is_filesystem_root: bool,
    entry: &dua_core::Entry,
) -> io::Result<bool> {
    if root_is_filesystem_root {
        return Ok(false);
    }
    let Some(containing_device) = containing_device else {
        return Ok(true);
    };
    fs::symlink_metadata(entry.path())
        .map(|metadata| std::os::unix::fs::MetadataExt::dev(&metadata) == containing_device)
}

#[cfg(unix)]
fn retained_mount<'a>(path: &Path, mounts: &'a [PathBuf]) -> Option<&'a Path> {
    mounts
        .iter()
        .find(|mount| mount.starts_with(path))
        .map(PathBuf::as_path)
}

#[derive(Default)]
struct FirstError(Option<DirectoryError>);

impl Reduce for FirstError {
    type Input = Option<DirectoryError>;
    type FeedProduce = ();
    type Output = Option<DirectoryError>;
    type Error = Infallible;

    fn feed(&mut self, error: Self::Input) -> Result<Self::FeedProduce, Self::Error> {
        if self.0.is_none() {
            self.0 = error;
        }
        Ok(())
    }

    fn finalize(self) -> Result<Self::Output, Self::Error> {
        Ok(self.0)
    }
}

#[cfg(test)]
mod tests {
    #[cfg(unix)]
    #[test]
    fn relative_roots_are_normalized_before_finding_the_containing_device() {
        let root = super::absolute_root(std::path::Path::new("one-component"))
            .expect("the current directory can be made absolute");
        assert!(root.is_absolute());
        assert!(
            root.parent()
                .and_then(|parent| std::fs::metadata(parent).ok())
                .is_some(),
            "a relative root still has a containing filesystem"
        );
    }

    #[cfg(unix)]
    #[test]
    fn mount_boundaries_are_checked_without_traversal_metadata() -> std::io::Result<()> {
        let tmp = gix_testtools::tempfile::tempdir()?;
        let entry = dua_core::Entry::from_path(tmp.path(), dua_core::Options::default().skip_metadata())?;
        assert!(entry.metadata.is_none(), "removal walks omit entry metadata");
        let device = std::os::unix::fs::MetadataExt::dev(&std::fs::symlink_metadata(tmp.path())?);
        assert!(
            super::may_descend(Some(device), false, &entry)?,
            "the same filesystem is traversed"
        );
        assert!(
            !super::may_descend(Some(device.wrapping_add(1)), false, &entry)?,
            "mounted filesystems are not traversed"
        );
        let mount = tmp.path().join("checkout/mount");
        assert_eq!(
            super::retained_mount(&mount, std::slice::from_ref(&mount)),
            Some(mount.as_path()),
            "the mount itself records the removal error"
        );
        assert_eq!(
            super::retained_mount(tmp.path(), std::slice::from_ref(&mount)),
            Some(mount.as_path()),
            "mount ancestors are retained too"
        );
        tmp.close()?;
        assert_eq!(
            super::may_descend(Some(device), false, &entry)
                .expect_err("a failed metadata check cannot allow descent")
                .kind(),
            std::io::ErrorKind::NotFound,
            "directory metadata errors remain available to the removal loop"
        );
        Ok(())
    }

    #[cfg(unix)]
    #[test]
    fn filesystem_root_aliases_are_not_traversed() -> gix_testtools::Result {
        let tmp = gix_testtools::tempfile::tempdir()?;
        let root_link = tmp.path().join("root-link");
        gix_fs::symlink::create(std::path::Path::new("/"), &root_link)?;

        // Only inspect descent decisions; never invoke removal on the filesystem root.
        for root in [
            std::path::PathBuf::from("/"),
            std::path::PathBuf::from("/.."),
            root_link.join(".."),
        ] {
            let root = super::absolute_root(&root)?;
            let entry = dua_core::Entry::from_path(&root, dua_core::Options::default().skip_metadata())?;
            let device = std::os::unix::fs::MetadataExt::dev(&std::fs::symlink_metadata(&root)?);
            assert!(
                !super::may_descend(Some(device), root.parent().is_none(), &entry)?,
                "the filesystem root cannot be traversed via {}",
                root.display()
            );
        }
        Ok(())
    }

    #[test]
    fn retries_when_an_entry_appears_after_scanning() {
        let tmp = gix_testtools::tempfile::tempdir().expect("temporary directory can be created");
        let root = tmp.path().join("worktree");
        std::fs::create_dir(&root).expect("removal root can be created");
        let mut scans = 0;

        super::remove_root_with_after_scan(
            &root,
            gix_features::progress::Discard,
            gix_features::progress::Discard,
            || {
                scans += 1;
                if scans == 1 {
                    std::fs::write(root.join("late"), b"late").expect("late file can be created");
                }
            },
        )
        .expect("a later pass removes the late file");

        assert_eq!(scans, 2, "one retry was needed");
        assert!(!root.exists(), "the root was removed");
    }

    #[test]
    fn stops_retrying_if_the_workload_does_not_shrink() {
        for equal_size in [false, true] {
            let tmp = gix_testtools::tempfile::tempdir().expect("temporary directory can be created");
            let root = tmp.path().join("worktree");
            std::fs::create_dir(&root).expect("removal root can be created");
            let root = std::fs::canonicalize(&root).expect("the removal root exists");
            if equal_size {
                std::fs::write(root.join("initial"), b"initial").expect("initial file can be created");
            } else {
                std::fs::create_dir(root.join("nested")).expect("initial directory can be created");
            }
            let mut scans = 0;

            let err = super::remove_root_with_after_scan(
                &root,
                gix_features::progress::Discard,
                gix_features::progress::Discard,
                || {
                    let parent = if !equal_size && scans == 0 {
                        root.join("nested")
                    } else {
                        root.clone()
                    };
                    std::fs::write(parent.join(format!("late-{scans}")), b"late").expect("late file can be created");
                    scans += 1;
                },
            )
            .expect_err("a non-shrinking root is left to the concurrent writer");

            assert_eq!(err.source.kind(), std::io::ErrorKind::DirectoryNotEmpty);
            assert_eq!(err.path, root, "the latest attempt's error is returned");
            assert_eq!(scans, 2, "an equal or growing workload stops after one retry");
        }
    }

    #[test]
    fn stops_after_three_improving_deletion_passes() {
        let tmp = gix_testtools::tempfile::tempdir().expect("temporary directory can be created");
        let root = tmp.path().join("worktree");
        std::fs::create_dir(&root).expect("removal root can be created");
        for idx in 0..4 {
            std::fs::write(root.join(format!("initial-{idx}")), b"initial").expect("initial file can be created");
        }
        let mut scans = 0;

        let err = super::remove_root_with_after_scan(
            &root,
            gix_features::progress::Discard,
            gix_features::progress::Discard,
            || {
                match scans {
                    0 => std::fs::create_dir_all(root.join("late/child")).expect("late directories can be created"),
                    1 => std::fs::write(root.join("late-file"), b"late").expect("late file can be created"),
                    2 => std::fs::write(root.join("last-file"), b"late").expect("last file can be created"),
                    _ => unreachable!("only three scans are allowed"),
                }
                scans += 1;
            },
        )
        .expect_err("three passes cap retries despite continued progress");

        assert_eq!(err.source.kind(), std::io::ErrorKind::DirectoryNotEmpty);
        assert_eq!(scans, 3, "deletion is capped at three passes");
    }
}