ocy_core/

walker.rs

use std::{
    cell::{Cell, RefCell},
    collections::HashSet,
    path::{Path, PathBuf},
};

use crate::{
    filesystem::FileSystem,
    models::RemovalCandidate,
    models::{FileInfo, SimpleFileKind},
    rule::{CleanAction, Rule, Target},
};
use eyre::Report;
use eyre::Result;

/// Version-control metadata, never descended into.
///
/// These directories hold thousands of small objects and no build output. Walking them is
/// pure cost, so they are skipped even under [`WalkOptions::walk_all`].
pub const VCS_DIRS: &[&str] = &[".git", ".svn", ".hg", ".jj", ".bzr"];

#[derive(Debug, Default, Clone)]
pub struct WalkOptions {
    /// Absolute paths that are neither scanned nor reclaimed.
    pub ignores: HashSet<PathBuf>,

    /// Descend into every hidden directory, not only [`WalkOptions::scanned_hidden`].
    pub walk_all: bool,

    /// Hidden directories descended into even when `walk_all` is false.
    ///
    /// Build output routinely hides behind a leading dot -- `.venv`, `.gradle`, `.next`.
    /// Skipping every dotted directory by default means missing most of it.
    pub scanned_hidden: HashSet<String>,

    /// Maximum depth below the scan root, or [`None`] for unlimited.
    pub max_depth: Option<usize>,

    /// Do not cross onto another filesystem, so a scan cannot wander onto network mounts.
    pub one_file_system: bool,
}

/// Tracks paths already claimed by a rule, so nested candidates are not walked or re-reported.
///
/// This wrapper encapsulates the `RefCell<HashSet<PathBuf>>` to ensure borrow/borrow_mut
/// operations are temporary and cannot overlap.
#[derive(Debug, Default)]
pub struct PrunedSet {
    inner: RefCell<HashSet<PathBuf>>,
}

impl PrunedSet {
    /// Creates a new empty PrunedSet.
    pub fn new() -> Self {
        Self {
            inner: RefCell::new(HashSet::new()),
        }
    }

    /// Checks if a path is directly in the pruned set.
    pub fn contains(&self, path: &Path) -> bool {
        self.inner.borrow().contains(path)
    }

    /// Inserts a path into the pruned set.
    pub fn insert(&self, path: PathBuf) {
        self.inner.borrow_mut().insert(path);
    }

    /// Whether this path overlaps a candidate that has already been reported.
    ///
    /// Reporting both a directory and something inside it would count the nested bytes
    /// twice in the total and race the two deletions against each other. Rules within a
    /// directory are applied in order, so the overlap can be found in either direction:
    /// a nested target may be claimed before the parent enclosing it, or after.
    ///
    /// Candidates stream to the user as they are found, so the first claim stands and the
    /// overlapping one is dropped. That can leave an enclosing directory unreclaimed,
    /// which is the safe direction to err for a tool that deletes things.
    ///
    /// Returns true if:
    /// - Any ancestor of `path` is in the pruned set (path is inside a claimed directory)
    /// - Any path in the pruned set starts with `path` (path is a parent of something claimed)
    pub fn is_already_claimed(&self, path: &Path) -> bool {
        let pruned = self.inner.borrow();
        path.ancestors().any(|ancestor| pruned.contains(ancestor))
            || pruned.iter().any(|claimed| claimed.starts_with(path))
    }
}

pub struct Walker<FS: FileSystem, N: WalkNotifier> {
    fs: FS,
    rules: Vec<Rule>,
    notifier: N,
    options: WalkOptions,
    /// Paths already claimed by a rule, so nested candidates are not walked or re-reported.
    pruned: PrunedSet,
    root_device: RefCell<Option<u64>>,
    /// Directories already walked, so a worktree reached both by descent and by its git
    /// record is scanned once and counted once.
    visited: RefCell<HashSet<PathBuf>>,
    /// Checkouts of linked worktrees found during the walk, scanned once it finishes.
    pending_worktrees: RefCell<Vec<FileInfo>>,
    directories_scanned: Cell<usize>,
    candidates_found: Cell<usize>,
}

pub trait WalkNotifier {
    fn notify_entered_directory(&self, dir: &FileInfo);
    fn notify_candidate_for_removal(&self, candidate: RemovalCandidate);
    fn notify_fail_to_scan(&self, e: &FileInfo, report: Report);
    fn notify_walk_finish(&self);
}

/// What the walk should do with a directory once its rules have been applied.
enum DirOutcome {
    /// Continue into these child directories.
    Descend(Vec<FileInfo>),
    /// The directory is itself a candidate; there is nothing below it worth visiting.
    Reclaimed,
}

impl<FS: FileSystem, N: WalkNotifier> Walker<FS, N> {
    pub fn new(fs: FS, rules: Vec<Rule>, notifier: N, options: WalkOptions) -> Self {
        Self {
            fs,
            rules,
            notifier,
            options,
            pruned: PrunedSet::new(),
            root_device: RefCell::default(),
            visited: RefCell::default(),
            pending_worktrees: RefCell::default(),
            directories_scanned: Cell::default(),
            candidates_found: Cell::default(),
        }
    }

    pub fn walk_from_path(&self, path: &FileInfo) {
        if self.options.one_file_system {
            *self.root_device.borrow_mut() = self.fs.device_id(path);
        }

        log::info!(
            "scanning {} with {} rules",
            path.path.display(),
            self.rules.len()
        );
        self.process_dir(path, 0);
        self.process_pending_worktrees(&path.path);
        log::info!(
            "scanned {} directories, found {} candidates",
            self.directories_scanned.get(),
            self.candidates_found.get()
        );

        self.notifier.notify_walk_finish();
    }

    /// Walk the linked worktrees discovered during the main walk.
    ///
    /// Deferred rather than recursed into on the spot, so that a worktree nested inside
    /// the tree is reached by ordinary descent first and skipped here as already visited.
    /// Only checkouts below `root` are followed: `ocy` was asked to clean one directory,
    /// and a worktree parked in `/tmp` is outside what was asked for.
    fn process_pending_worktrees(&self, root: &Path) {
        loop {
            // Popped in its own statement: as the scrutinee of a `while let`, the borrow
            // would live for the whole body, and walking a worktree can queue more.
            let next = self.pending_worktrees.borrow_mut().pop();
            let Some(worktree) = next else {
                break;
            };

            if worktree.path.starts_with(root) {
                log::debug!("following linked worktree {}", worktree.path.display());
                self.process_dir(&worktree, 0);
            } else {
                log::debug!(
                    "skipping worktree outside the scan root: {}",
                    worktree.path.display()
                );
            }
        }
    }

    fn process_dir(&self, file: &FileInfo, depth: usize) {
        // TODO consider using is_already_claimed
        if self.is_ignored(&file.path) || self.pruned.contains(&file.path) {
            return;
        }
        if !self.visited.borrow_mut().insert(file.path.clone()) {
            return;
        }

        match self.process_entries(file, depth) {
            Ok(DirOutcome::Descend(children)) => children
                .iter()
                .for_each(|child| self.process_dir(child, depth + 1)),
            Ok(DirOutcome::Reclaimed) => (),
            Err(report) => self.notifier.notify_fail_to_scan(file, report),
        }
    }

    fn process_entries(&self, dir: &FileInfo, depth: usize) -> Result<DirOutcome> {
        self.notifier.notify_entered_directory(dir);
        self.directories_scanned
            .set(self.directories_scanned.get() + 1);

        let listing = self.fs.list_files(dir)?;
        listing
            .errors
            .into_iter()
            .for_each(|report| self.notifier.notify_fail_to_scan(dir, report));
        let mut entries = listing.entries;

        for rule in &self.rules {
            if !rule.matches(&entries) {
                continue;
            }

            match rule.action() {
                // The scan root is never proposed for deletion: running ocy from inside a
                // venv must not offer to delete the directory being scanned.
                CleanAction::RemoveSelf if depth > 0 => {
                    if self.claim(rule, dir.clone()) {
                        return Ok(DirOutcome::Reclaimed);
                    }
                }
                CleanAction::RemoveSelf => (),
                CleanAction::Remove(targets) => {
                    let claimed = self.claim_targets(rule, &entries, targets);
                    entries.retain(|entry| !claimed.contains(&entry.path));
                }
                CleanAction::Run(command) => {
                    self.notifier
                        .notify_candidate_for_removal(RemovalCandidate::new_cmd(
                            rule.name.clone(),
                            dir.clone(),
                            command.clone(),
                        ));
                }
                CleanAction::RemoveStaleWorktrees => {
                    self.claim_stale_worktrees(rule, dir);
                    self.queue_linked_worktrees(dir);
                }
            }
        }

        entries.retain(|entry| self.is_walkable(entry, depth));
        Ok(DirOutcome::Descend(entries))
    }

    /// Report every target of a matched rule that actually exists.
    ///
    /// Returns the paths that were claimed, so the caller can drop them from the entries
    /// it is about to descend into.
    fn claim_targets(
        &self,
        rule: &Rule,
        entries: &[FileInfo],
        targets: &[Target],
    ) -> HashSet<PathBuf> {
        targets
            .iter()
            .flat_map(|target| self.resolve_target(entries, target))
            .filter_map(|found| {
                let path = found.path.clone();
                self.claim(rule, found).then_some(path)
            })
            .collect()
    }

    /// Walk a target's components one directory level at a time.
    ///
    /// The first component is matched against the already-listed entries, so the common
    /// single-component target costs no extra syscall; only a nested target such as
    /// `.angular/cache` reads further directories.
    fn resolve_target(&self, entries: &[FileInfo], target: &Target) -> Vec<FileInfo> {
        let Some((first, rest)) = target.components.split_first() else {
            return Vec::new();
        };

        let mut found: Vec<FileInfo> = entries
            .iter()
            .filter(|entry| first.matches(&entry.name))
            .cloned()
            .collect();

        for component in rest {
            found = found
                .iter()
                .filter(|entry| entry.kind == SimpleFileKind::Directory)
                .filter_map(|dir| self.fs.list_files(dir).ok())
                .flat_map(|listing| listing.entries)
                .filter(|entry| component.matches(&entry.name))
                .collect();
        }

        found.retain(|entry| target.kind.is_none_or(|kind| kind == entry.kind));
        found
    }

    /// Report the records of worktrees whose checkout is gone.
    ///
    /// This reads the records directly rather than through [`FileSystem`], because
    /// deciding staleness means following a `gitdir` pointer out of the tree being
    /// walked. The logic is covered by the tests in [`crate::git`].
    fn claim_stale_worktrees(&self, rule: &Rule, dir: &FileInfo) {
        crate::git::stale_worktree_records(&dir.path.join(".git"))
            .into_iter()
            .for_each(|record| {
                let name = record
                    .file_name()
                    .map(|name| name.to_string_lossy().into_owned())
                    .unwrap_or_default();
                self.claim(rule, FileInfo::new(record, name, SimpleFileKind::Directory));
            });
    }

    /// Note the checkouts of this repository's linked worktrees for later walking.
    ///
    /// A worktree is a working copy with its own build output, and it is routinely parked
    /// under a hidden directory that the walk would otherwise never enter.
    fn queue_linked_worktrees(&self, dir: &FileInfo) {
        let found = crate::git::linked_worktree_paths(&dir.path.join(".git"));

        self.pending_worktrees
            .borrow_mut()
            .extend(found.into_iter().map(|path| {
                let name = path
                    .file_name()
                    .map(|name| name.to_string_lossy().into_owned())
                    .unwrap_or_default();
                FileInfo::new(path, name, SimpleFileKind::Directory)
            }));
    }

    /// Claim `file` for `rule` and report it, unless it must not be claimed.
    ///
    /// Every claim goes through here, so being ignored, overlapping an existing candidate
    /// and recording what has been claimed are decided in one place instead of in each
    /// caller. Returns whether the claim was taken.
    fn claim(&self, rule: &Rule, file: FileInfo) -> bool {
        if self.is_ignored(&file.path) || self.pruned.is_already_claimed(&file.path) {
            return false;
        }
        self.pruned.insert(file.path.clone());

        let size = match self.fs.file_size(&file) {
            Ok(size) => Some(size),
            Err(report) => {
                // The candidate is still offered; only its size is unknown.
                log::debug!("cannot size {}: {report:#}", file.path.display());
                None
            }
        };
        log::debug!(
            "rule `{}` claims {} ({})",
            rule.name,
            file.path.display(),
            size.map_or_else(
                || "size unknown".to_string(),
                |size| format!("{size} bytes")
            )
        );
        self.candidates_found.update(|n| n + 1);
        self.notifier
            .notify_candidate_for_removal(RemovalCandidate::new(rule.name.clone(), file, size));
        true
    }

    fn is_ignored(&self, path: &Path) -> bool {
        self.options.ignores.contains(path)
    }

    fn is_walkable(&self, file: &FileInfo, depth: usize) -> bool {
        file.kind == SimpleFileKind::Directory
            && self.within_depth(depth)
            && self.is_scannable_name(&file.name)
            && self.stays_on_one_filesystem(file)
    }

    fn within_depth(&self, depth: usize) -> bool {
        self.options
            .max_depth
            .is_none_or(|max_depth| depth < max_depth)
    }

    fn is_scannable_name(&self, name: &str) -> bool {
        if VCS_DIRS.contains(&name) {
            log::trace!("skipping {name}: version control metadata");
            false
        } else if name.starts_with('.') {
            let scannable = self.options.walk_all || self.options.scanned_hidden.contains(name);
            if !scannable {
                // The most common reason a user reports something as "not found".
                log::debug!("skipping hidden {name}; use --all to descend into it");
            }
            scannable
        } else {
            true
        }
    }

    fn stays_on_one_filesystem(&self, file: &FileInfo) -> bool {
        match (self.options.one_file_system, *self.root_device.borrow()) {
            (true, Some(root)) => self.fs.device_id(file).is_none_or(|device| device == root),
            _ => true,
        }
    }
}

#[cfg(test)]
mod tests;