girt 0.18.0

use std::borrow::Cow;
use std::collections::HashSet;
use std::ffi::OsStr;
use std::fs::File;
use std::io::Read;
use std::os::unix::ffi::OsStrExt;
use std::path::{Component, Path};
use std::sync::atomic::AtomicBool;
use std::sync::{Arc, Condvar, Mutex};

use parallel::{Budget, Open, Queue, Task};
use rustix::fd::OwnedFd;
use rustix::fs::{AtFlags, Dir, FileType, Mode, OFlags, Stat, fstat, openat, statat};
use tracked::{Slots, Tracked};
mod untracked;
use unicode_normalization::UnicodeNormalization as _;

use super::types::{charge, check, value};
use super::{
    Error, Limits, Untracked, UntrackedFiles, UntrackedKind, UntrackedPath, WorktreeChange,
};
use crate::ignore::{self, Ignore, InputKind, Source};
use crate::pathspec::{Pathspec, Prune};
use crate::{EntryMode, ObjectId, Repository, TreeValue, index};

pub(super) struct Observation {
    pub changes: Vec<WorktreeChange>,
    pub cache_reused: usize,
    pub untracked: Vec<Vec<u8>>,
    pub listed: Vec<UntrackedPath>,
    pub boundaries: Vec<Vec<u8>>,
    /// Stage-zero entries whose content this scan read and found equal to the index, by
    /// position, with the stat words observed before the read; sorted by position.
    pub verified: Vec<(usize, index::Stat)>,
}

/// Conversion applied to tracked regular files before comparing them with the index.
pub(crate) trait Convert: Sync {
    /// The stored form of `file` at `path`, whose index entry names `staged`.
    fn convert(&self, path: &[u8], file: &[u8], staged: Option<ObjectId>)
    -> Result<Vec<u8>, Error>;
}

/// A shared pipeline with the objects `text=auto` reads staged blobs from.
pub(crate) struct Shared<'a> {
    pub(crate) pipeline: Mutex<&'a mut crate::filter::Pipeline>,
    pub(crate) objects: &'a crate::Objects,
}

impl Convert for Shared<'_> {
    fn convert(
        &self,
        path: &[u8],
        file: &[u8],
        staged: Option<ObjectId>,
    ) -> Result<Vec<u8>, Error> {
        let mut pipeline = self
            .pipeline
            .lock()
            .unwrap_or_else(std::sync::PoisonError::into_inner);
        let staged = staged.map_or(crate::filter::Staged::Absent, |id| {
            crate::filter::Staged::Object(self.objects, id)
        });
        pipeline
            .stored_for_status(path, file, staged)
            .map(std::borrow::Cow::into_owned)
            .map_err(|source| Error::Filter {
                path: path.to_vec(),
                source: Box::new(source),
            })
    }
}

pub(crate) type Filters<'a> = &'a dyn Convert;

/// How a scan treats paths absent from the index.
pub(super) enum Listing {
    /// Raw status: list every leaf or none, never consulting ignore rules.
    Raw(Untracked),
    /// Ignore-aware status: these rules plus each visited directory's `.gitignore`, and Git's
    /// name policy.
    Ignoring {
        rules: Box<Ignore>,
        files: UntrackedFiles,
        names: GitNames,
        environment: Box<crate::workflow::Environment>,
        monitor: Option<Box<crate::fsmonitor::Monitor>>,
        capture: Option<Arc<super::untracked::Capture>>,
        excludes: Option<[ObjectId; 2]>,
    },
}

/// How Git's `core.precomposeUnicode` and `core.ignoreCase` relate working-tree names to index
/// paths during ignore-aware status.
///
/// As in Git, an index path missing from its directory's listing is looked up by its own name,
/// so a volume that merges names still finds it. With `precompose`, listed names are composed
/// (NFC) before comparison and reporting, as Git composes them. With `ignore_case`, an untracked
/// listed name is hidden when an index path in the same directory matches it ignoring ASCII case,
/// even if the volume stores them as different files, as Git hides it.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub(crate) struct GitNames {
    pub(crate) ignore_case: bool,
    pub(crate) precompose: bool,
}

impl GitNames {
    /// The name Git compares and reports for a listed `name`.
    fn logical(self, name: &[u8]) -> Cow<'_, [u8]> {
        match std::str::from_utf8(name) {
            Ok(text) if self.precompose && !text.is_ascii() => {
                Cow::Owned(text.nfc().collect::<String>().into_bytes())
            }
            _ => Cow::Borrowed(name),
        }
    }
}

/// [`Listing`] without its rules, which travel with each directory instead.
#[derive(Clone, Copy, PartialEq)]
enum Policy {
    Raw(Untracked),
    Ignoring(UntrackedFiles),
}

/// One child of a directory being walked: its name on disk, the path Git reports for it, and the
/// index records at that path.
struct Child<'a, 'n> {
    name: Cow<'n, [u8]>,
    path: Vec<u8>,
    tracked: Option<(usize, &'a index::Entry)>,
    directory: Option<usize>,
    /// Looked up by its index name rather than listed under it.
    resolved: bool,
    /// Matched by the pathspec itself, not only as an ancestor of matched paths.
    selected: bool,
}

#[expect(clippy::too_many_arguments, reason = "one traversal's inputs")]
pub(super) fn scan(
    repo: &Repository,
    root: &Path,
    entries: &[index::Entry],
    index_written: Option<u32>,
    monitor_clean: &[bool],
    untracked_cache: Option<&super::untracked::Cache>,
    listing: Listing,
    paths: &Pathspec,
    filters: Option<Filters<'_>>,
    limits: Limits,
    cancel: &AtomicBool,
) -> Result<Observation, Error> {
    scan_with_hook(
        repo,
        root,
        entries,
        index_written,
        monitor_clean,
        untracked_cache,
        listing,
        paths,
        filters,
        limits,
        cancel,
        &|_| {},
    )
}

// A private checkpoint permits deterministic race/cancellation tests without timing assumptions.
#[expect(clippy::too_many_arguments, reason = "private test seam for `scan`")]
fn scan_with_hook(
    repo: &Repository,
    root: &Path,
    entries: &[index::Entry],
    index_written: Option<u32>,
    monitor_clean: &[bool],
    untracked_cache: Option<&super::untracked::Cache>,
    listing: Listing,
    paths: &Pathspec,
    filters: Option<Filters<'_>>,
    limits: Limits,
    cancel: &AtomicBool,
    after_read: &(dyn Fn(&[u8]) + Sync),
) -> Result<Observation, Error> {
    let configured = matches!(listing, Listing::Ignoring { .. });
    let ignored_gitlinks = if configured {
        crate::submodule::ignored_gitlinks(repo, entries, limits, paths)
            .map_err(|error| Error::Submodules(Box::new(error)))?
    } else {
        HashSet::new()
    };
    let file_mode = !configured
        || repo
            .config()
            .boolean("core", None, "filemode")
            .map_err(|_| unsupported(b"", "invalid core.fileMode boolean"))?
            .unwrap_or(true);
    let symlinks = !configured
        || repo
            .config()
            .boolean("core", None, "symlinks")
            .map_err(|_| unsupported(b"", "invalid core.symlinks boolean"))?
            .unwrap_or(true);
    let stat_policy = if configured {
        StatPolicy::configured(repo)?
    } else {
        StatPolicy::default()
    };
    let root_fd = Arc::new(open_root(root)?);
    let mut metadata = Vec::new();
    for path in [repo.git_dir(), repo.common_dir(), repo.object_dir()] {
        let stat = rustix::fs::stat(path).map_err(|source| io(b"", source))?;
        metadata.push(stat);
    }
    let max_depth = limits.max_depth.min(128);
    let mut path_bytes = limits.max_path_bytes;
    let mut directories = Vec::new();
    let mut previous: &[u8] = b"";
    for entry in entries {
        check(cancel)?;
        validate_path(&entry.path)?;
        if entry.path.iter().filter(|byte| **byte == b'/').count() > max_depth {
            return Err(Error::Limit("directory depth"));
        }
        // Paths sharing a directory are adjacent in index order, so a directory is new exactly
        // when it is not also an ancestor of the previous path.
        for (offset, byte) in entry.path.iter().enumerate() {
            let directory = &entry.path[..offset];
            if *byte == b'/'
                && !(previous.starts_with(directory) && previous.get(offset) == Some(&b'/'))
            {
                charge(&mut path_bytes, offset, "path bytes")?;
                directories.push(directory);
            }
        }
        previous = &entry.path;
    }
    directories.sort_unstable();
    let capture = match &listing {
        Listing::Ignoring { capture, .. } => capture.clone(),
        _ => None,
    };
    let (policy, rules, names) = match listing {
        Listing::Raw(policy) => (Policy::Raw(policy), None, None),
        Listing::Ignoring {
            rules,
            files,
            names,
            ..
        } => (Policy::Ignoring(files), Some(Arc::new(*rules)), Some(names)),
    };
    let ignore_limits = rules.as_ref().map(|rules| rules.limits());
    let ignore_usage = rules.as_ref().map(|rules| rules.usage());
    let scan = Scan {
        format: repo.object_format(),
        tracked: Tracked::new(entries, directories, names.is_some()),
        names,
        configured,
        monitor_clean,
        untracked_cache,
        capture,
        ignored_gitlinks,
        file_mode,
        symlinks,
        stat_policy,
        metadata,
        index_written,
        policy,
        paths,
        filters,
        max_file_bytes: limits.max_file_bytes,
        max_depth,
        directory_entries: Budget::new(limits.max_directory_entries),
        path_bytes: Budget::new(path_bytes),
        worktree_bytes: Budget::new(limits.max_worktree_bytes),
        ignore_sources: Budget::new(
            ignore_limits
                .map_or(0, |limits| limits.sources)
                .saturating_sub(ignore_usage.map_or(0, |usage| usage.sources)),
        ),
        ignore_bytes: Budget::new(rules.as_ref().map_or(0, |rules| rules.remaining_bytes())),
        ignore_patterns: Budget::new(
            ignore_limits
                .map_or(0, |limits| limits.patterns)
                .saturating_sub(ignore_usage.map_or(0, |usage| usage.patterns)),
        ),
        cancel,
        after_read,
        queue: Mutex::new(Queue {
            tasks: vec![Task {
                open: Open::Root(Arc::clone(&root_fd)),
                path: Vec::new(),
                depth: 0,
                walk: Walk::default(),
                rules,
                listed: false,
            }],
            active: 0,
            failure: None,
        }),
        ready: Condvar::new(),
        stopped: AtomicBool::new(false),
    };
    let found = scan.run(limits.max_threads)?;
    let reopened = open_root(root)?;
    let original = fstat(&*root_fd).map_err(|source| io(b"", source))?;
    let current = fstat(&reopened).map_err(|source| io(b"", source))?;
    same(b"", &original, &current)?;
    let observed = scan.tracked.collect(found.observations);
    let directories = scan.tracked.directory_states(&observed);
    let mut read = found.verified;
    read.sort_unstable_by_key(|(position, _)| *position);
    let mut read = read.into_iter().peekable();
    let mut verified = Vec::new();
    let mut changes = Vec::new();
    for (position, entry) in entries.iter().enumerate() {
        check(cancel)?;
        if entry.stage != index::Stage::Normal
            || (configured && (entry.assume_valid || entry.skip_worktree))
        {
            continue;
        }
        if entry.mode == index::Mode::Gitlink {
            let replaced_by_file = match observed[position] {
                Some(Observed::Leaf(value) | Observed::Resized(value)) => {
                    matches!(value.mode, EntryMode::Blob | EntryMode::Executable)
                }
                _ => false,
            };
            if !configured || !replaced_by_file {
                continue;
            }
        }
        let difference = if configured && entry.intent_to_add {
            match observed[position] {
                Some(Observed::Leaf(actual) | Observed::Resized(actual)) => {
                    Some(super::Change::Added(actual))
                }
                _ => scan.tracked.difference(position, &observed, &directories),
            }
        } else {
            scan.tracked.difference(position, &observed, &directories)
        };
        // A path observed more than once (two index names the volume stores as one file) has
        // its stat recorded only when every read agrees.
        let mut stats = Vec::new();
        while let Some((_, stat)) = read.next_if(|(slot, _)| *slot <= position) {
            stats.push(stat);
        }
        if let Some(change) = difference {
            changes.push(WorktreeChange {
                path: entry.path.clone(),
                index: value(entry),
                change,
            });
        } else if let Some(first) = stats.first()
            && !(configured && entry.intent_to_add)
            && stats.iter().all(|stat| stat == first)
        {
            verified.push((position, *first));
        }
    }
    let cache_reused = found.cache_reused;
    let Found {
        mut untracked,
        mut listed,
        mut boundaries,
        ..
    } = found;
    untracked.sort_unstable();
    listed.sort_unstable_by(|a, b| a.path.cmp(&b.path));
    boundaries.sort_unstable();
    check(cancel)?;
    Ok(Observation {
        changes,
        cache_reused,
        untracked,
        listed,
        boundaries,
        verified,
    })
}

/// Ignore state inherited by a directory's children.
#[derive(Clone, Copy, Default)]
struct Walk {
    /// An ancestor is ignored, so every untracked descendant is too.
    excluded: bool,
    cache_invalid: bool,
    /// Inside a collapsed untracked directory: the `listed` length when it was entered.
    collapse: Option<usize>,
}

/// What [`Scan::directory`] found at a directory path.
#[derive(PartialEq)]
enum Visited {
    Directory,
    /// A nested repository; never entered.
    Repository,
    /// This repository's own metadata directory; never entered.
    Metadata,
}

#[derive(Clone, Copy)]
enum Observed {
    Leaf(TreeValue),
    /// The file's size differs from the cached index size, which Git reports as modified even
    /// when its converted content matches the index.
    Resized(TreeValue),
    Directory,
    Blocked,
}

/// What one worker observed; merged after every worker finishes.
#[derive(Default)]
struct Found {
    cache_reused: usize,
    /// Observations of tracked paths and their directories, by [`Tracked::slots`].
    observations: Vec<(usize, Observed)>,
    untracked: Vec<Vec<u8>>,
    listed: Vec<UntrackedPath>,
    boundaries: Vec<Vec<u8>>,
    /// Entries whose content was read and matched the index, with their pre-read stat words.
    verified: Vec<(usize, index::Stat)>,
}

impl Found {
    fn observe(&mut self, slots: Slots, observed: Observed) {
        for slot in [slots.entry, slots.directory].into_iter().flatten() {
            self.observations.push((slot, observed));
        }
    }

    fn extend(&mut self, other: Self) {
        self.cache_reused += other.cache_reused;
        self.observations.extend(other.observations);
        self.untracked.extend(other.untracked);
        self.listed.extend(other.listed);
        self.boundaries.extend(other.boundaries);
        self.verified.extend(other.verified);
    }
}

struct Scan<'a> {
    format: crate::ObjectFormat,
    configured: bool,
    monitor_clean: &'a [bool],
    untracked_cache: Option<&'a super::untracked::Cache>,
    capture: Option<Arc<super::untracked::Capture>>,
    ignored_gitlinks: HashSet<Vec<u8>>,
    file_mode: bool,
    symlinks: bool,
    stat_policy: StatPolicy,
    tracked: Tracked<'a>,
    metadata: Vec<Stat>,
    /// Seconds word of the index file's mtime; `None` disables trusting cached stat words.
    index_written: Option<u32>,
    policy: Policy,
    /// Paths outside this pathspec are neither read nor listed.
    paths: &'a Pathspec,
    filters: Option<Filters<'a>>,
    /// Git's name policy; `None` compares exact bytes, as raw status does.
    names: Option<GitNames>,
    max_file_bytes: usize,
    max_depth: usize,
    directory_entries: Budget,
    path_bytes: Budget,
    worktree_bytes: Budget,
    ignore_sources: Budget,
    ignore_bytes: Budget,
    ignore_patterns: Budget,
    cancel: &'a AtomicBool,
    after_read: &'a (dyn Fn(&[u8]) + Sync),
    queue: Mutex<Queue>,
    ready: Condvar,
    /// Set once any worker fails, so the others stop early.
    stopped: AtomicBool,
}

impl Scan<'_> {
    /// Whether the pathspec selects a directory itself, written with its trailing `/`, which is
    /// how Git decides to list an untracked directory or nested repository as one entry.
    fn selects_directory(&self, path: &[u8]) -> bool {
        self.paths.matches_unchecked(&[path, b"/"].concat())
    }

    /// Under core.ignoreCase, the ASCII-lowercased names of `directory`'s tracked children;
    /// otherwise empty.
    fn case_folded_children(&self, directory: &[u8]) -> HashSet<Vec<u8>> {
        if !self.names.is_some_and(|names| names.ignore_case) {
            return HashSet::new();
        }
        self.tracked
            .children(directory)
            .into_iter()
            .map(<[u8]>::to_ascii_lowercase)
            .collect()
    }

    /// Whether untracked paths are listed at all.
    fn lists_untracked(&self) -> bool {
        match self.policy {
            Policy::Raw(policy) => policy == Untracked::RawFilesWithoutIgnores,
            Policy::Ignoring(files) => files != UntrackedFiles::Omit,
        }
    }

    /// Whether ignore rules exclude this path, given that no ancestor is excluded.
    fn ignored(
        &self,
        rules: Option<&Arc<Ignore>>,
        path: &[u8],
        kind: InputKind,
    ) -> Result<bool, Error> {
        let Some(rules) = rules else {
            return Ok(false);
        };
        let found = rules
            .check_direct(path, kind)
            .map_err(|source| Error::Ignore {
                path: path.to_vec(),
                source,
            })?;
        Ok(found.is_some_and(|found| found.ignored))
    }

    /// Returns `rules` plus this directory's `.gitignore`. Like Git, a symlink or non-file is
    /// skipped.
    ///
    /// Each directory extends its own copy, so workers never share mutable rules. Source, byte and
    /// pattern counts are also charged to repository-wide budgets, keeping the totals within the
    /// ignore limits as a single sequential walk would.
    fn load_gitignore(
        &self,
        fd: &OwnedFd,
        path: &[u8],
        rules: Arc<Ignore>,
        names: &Names,
    ) -> Result<Arc<Ignore>, Error> {
        let mut file = path.to_vec();
        if !file.is_empty() {
            file.push(b'/');
        }
        file.extend_from_slice(b".gitignore");
        let content = if names.ignore_observed {
            let Some(content) = &names.ignore_content else {
                return Ok(rules);
            };
            Cow::Borrowed(content.as_slice())
        } else {
            let Some(stat) = optional_stat(fd, b".gitignore", &file)? else {
                return Ok(rules);
            };
            if FileType::from_raw_mode(stat.st_mode) != FileType::RegularFile {
                return Ok(rules);
            }
            let max = self.max_file_bytes.min(self.worktree_bytes.remaining());
            let content = self.read_file(fd, b".gitignore", &file, &stat, max)?;
            self.worktree_bytes
                .charge(content.len(), "worktree bytes")?;
            Cow::Owned(content)
        };
        let limit = |label| Error::Ignore {
            path: file.clone(),
            source: ignore::Error::Limit(label),
        };
        if !self.ignore_sources.take(1) {
            return Err(limit("source count"));
        }
        if !self
            .ignore_bytes
            .take(content.len().saturating_add(path.len()))
        {
            return Err(limit("source bytes"));
        }
        let mut extended = Ignore::clone(&rules);
        let before = extended.usage().patterns;
        extended
            .add(Source::Directory(path), &content)
            .map_err(|source| Error::Ignore {
                path: file.clone(),
                source,
            })?;
        if !self
            .ignore_patterns
            .take(extended.usage().patterns - before)
        {
            return Err(limit("pattern count"));
        }
        Ok(Arc::new(extended))
    }

    /// Opens a child directory found by its parent, walks it and checks it was not replaced.
    #[expect(clippy::too_many_arguments, reason = "one directory's traversal state")]
    fn child_directory(
        &self,
        found: &mut Found,
        parent: &OwnedFd,
        name: &[u8],
        path: &[u8],
        stat: &Stat,
        depth: usize,
        walk: Walk,
        rules: Option<Arc<Ignore>>,
    ) -> Result<Visited, Error> {
        let child_fd = openat(
            parent,
            OsStr::from_bytes(name),
            directory_flags(),
            Mode::empty(),
        )
        .map_err(|source| io(path, source))?;
        let opened = fstat(&child_fd).map_err(|source| io(path, source))?;
        same(path, stat, &opened)?;
        let visited = self.directory(
            found,
            &Arc::new(child_fd),
            &opened,
            path,
            depth,
            walk,
            rules,
        )?;
        let after = statat(parent, OsStr::from_bytes(name), AtFlags::SYMLINK_NOFOLLOW)
            .map_err(|source| io(path, source))?;
        same(path, stat, &after)?;
        Ok(visited)
    }

    /// Walks an open directory whose `fstat` is `before`.
    #[expect(clippy::too_many_arguments, reason = "one directory's traversal state")]
    fn directory(
        &self,
        found: &mut Found,
        fd: &Arc<OwnedFd>,
        before: &Stat,
        path: &[u8],
        depth: usize,
        mut walk: Walk,
        rules: Option<Arc<Ignore>>,
    ) -> Result<Visited, Error> {
        self.check()?;
        if self
            .metadata
            .iter()
            .any(|metadata| metadata.st_dev == before.st_dev && metadata.st_ino == before.st_ino)
        {
            found.boundaries.push(path.to_vec());
            found.observe(self.tracked.slots(path), Observed::Blocked);
            return Ok(Visited::Metadata);
        }
        let (cached, invalidate) = if walk.cache_invalid || walk.excluded {
            (None, true)
        } else {
            self.cached_names(fd, before, path)?
        };
        walk.cache_invalid |= invalidate;
        let mut names = match cached {
            Some(names) => {
                found.cache_reused += usize::from(names.cached);
                names
            }
            None => self.read_names(fd, path)?,
        };
        // Detect nested repositories before entering any of their children. Merely lstat the
        // marker; never open it. The root marker is expected and ignored below.
        if !path.is_empty() && names.repository_marker(fd, path)? {
            found.boundaries.push(path.to_vec());
            found.observe(self.tracked.slots(path), Observed::Blocked);
            return Ok(Visited::Repository);
        }
        found.observe(self.tracked.slots(path), Observed::Directory);
        // Ignore rules decide only what is listed, so an omitted listing skips them entirely.
        let ignoring = matches!(self.policy, Policy::Ignoring(_)) && self.lists_untracked();
        if self.capture.is_some() && !walk.excluded && names.may_name(b".gitignore") {
            names.ignore_observed = true;
            if let Some(stat) = optional_stat(fd, b".gitignore", path)?
                && FileType::from_raw_mode(stat.st_mode) == FileType::RegularFile
            {
                let content = self.read_file(
                    fd,
                    b".gitignore",
                    path,
                    &stat,
                    self.max_file_bytes.min(self.worktree_bytes.remaining()),
                )?;
                self.worktree_bytes
                    .charge(content.len(), "worktree bytes")?;
                names.ignore_content = Some(content);
            }
        }
        let rules = match rules {
            Some(rules)
                if !walk.excluded && self.lists_untracked() && names.may_name(b".gitignore") =>
            {
                Some(self.load_gitignore(fd, path, rules, &names)?)
            }
            rules => rules,
        };
        let collapsed = self.policy == Policy::Ignoring(UntrackedFiles::Collapsed);
        let mut children = Vec::new();
        for name in names.iter() {
            self.check()?;
            if name.eq_ignore_ascii_case(b".git") {
                if name != b".git" {
                    return Err(unsupported(&join(path, name), "metadata name alias"));
                }
                continue;
            }
            let logical = self
                .names
                .map_or(Cow::Borrowed(name), |names| names.logical(name));
            let child = join(path, &logical);
            // Validate bytes before constructing an OS string or opening a directory entry.
            validate_path(&child)?;
            // Nothing at or below a path outside the pathspec is reported, so it is not examined.
            let selected = self.paths.matches_unchecked(&child);
            if !selected && self.paths.directory(&child) == Prune::Skip {
                continue;
            }
            children.push(Child {
                tracked: self.tracked.entry(&child),
                directory: self.tracked.directory(&child),
                name: Cow::Borrowed(name),
                path: child,
                resolved: false,
                selected,
            });
        }
        if self.names.is_some() {
            let listed = children
                .iter()
                .filter(|child| child.tracked.is_some() || child.directory.is_some())
                .count();
            if listed < self.tracked.child_count(path) {
                let seen: HashSet<&[u8]> = children.iter().map(|child| &child.path[..]).collect();
                let mut missing = Vec::new();
                for name in self.tracked.children(path) {
                    let child = join(path, name);
                    if !seen.contains(&child[..]) {
                        missing.push((name.to_vec(), child));
                    }
                }
                for (name, child) in missing {
                    self.check()?;
                    let selected = self.paths.matches_unchecked(&child);
                    let promised = self.configured
                        && self.policy == Policy::Ignoring(UntrackedFiles::All)
                        && self
                            .tracked
                            .entry(&child)
                            .is_some_and(|(_, entry)| entry.assume_valid || entry.skip_worktree);
                    // A promised replacement directory may match by its listed spelling instead.
                    if !selected && self.paths.directory(&child) == Prune::Skip && !promised {
                        continue;
                    }
                    if optional_stat(fd, &name, &child)?.is_none() {
                        continue;
                    }
                    children.push(Child {
                        tracked: self.tracked.entry(&child),
                        directory: self.tracked.directory(&child),
                        name: Cow::Owned(name),
                        path: child,
                        resolved: true,
                        selected,
                    });
                }
            }
        }
        let mut case_folded: Option<HashSet<Vec<u8>>> = None;
        for Child {
            name,
            path: mut child,
            tracked,
            directory,
            resolved,
            selected,
        } in children
        {
            self.check()?;
            // A collapsed directory needs only one visible untracked path.
            if walk.collapse.is_some_and(|mark| found.listed.len() > mark) {
                break;
            }
            let name = &name[..];
            let needed = directory.is_some();
            if tracked.is_none() && !needed && (!self.lists_untracked() || walk.excluded) {
                continue;
            }
            // With core.ignoreCase, Git never lists a name an index path matches ignoring case,
            // even when the volume stores them as different files.
            if tracked.is_none() && !needed && !resolved {
                let folded = case_folded.get_or_insert_with(|| self.case_folded_children(path));
                if folded.contains(&name.to_ascii_lowercase()) {
                    continue;
                }
            }
            if tracked.is_some_and(|(_, entry)| {
                (entry.mode == index::Mode::Gitlink
                    && (!self.configured || self.ignored_gitlinks.contains(&entry.path)))
                    || (self.configured
                        && (entry.assume_valid || entry.skip_worktree)
                        && self.policy != Policy::Ignoring(UntrackedFiles::All))
            }) {
                continue;
            }
            let slot = Slots {
                entry: tracked.map(|(slot, _)| slot),
                directory: directory.map(|directory| self.tracked.entries.len() + directory),
            };
            if selected
                && directory.is_none()
                && let Some((position, entry)) = tracked
                && entry.stage == index::Stage::Normal
                && !entry.intent_to_add
                && matches!(
                    entry.mode,
                    index::Mode::Regular | index::Mode::Executable | index::Mode::Symlink
                )
                && self.monitor_clean.get(position) == Some(&true)
            {
                found.observe(slot, Observed::Leaf(value(entry)));
                continue;
            }
            let stat = statat(&**fd, OsStr::from_bytes(name), AtFlags::SYMLINK_NOFOLLOW)
                .map_err(|source| io(&child, source))?;
            let kind = FileType::from_raw_mode(stat.st_mode);
            if tracked.is_some_and(|(_, entry)| entry.mode == index::Mode::Gitlink)
                && kind != FileType::RegularFile
            {
                continue;
            }
            if kind != FileType::Directory {
                if !selected {
                    // A selected tracked path below this one is still obstructed by it.
                    if slot.directory.is_some() {
                        found.observe(slot, Observed::Blocked);
                    }
                    continue;
                }
                self.leaf(
                    found,
                    fd,
                    name,
                    &child,
                    &stat,
                    tracked,
                    slot,
                    rules.as_ref(),
                )?;
                continue;
            }
            // A promised leaf replaced by a directory is only traversed for untracked files.
            // Git reports its listed spelling, even when we found it by the index name first.
            if resolved
                && self.configured
                && self.policy == Policy::Ignoring(UntrackedFiles::All)
                && tracked.is_some_and(|(_, entry)| entry.assume_valid || entry.skip_worktree)
            {
                let mut spelling = None;
                for listed in names.iter() {
                    self.check()?;
                    let Some(actual) = optional_stat(fd, listed, &child)? else {
                        continue;
                    };
                    if actual.st_dev == stat.st_dev && actual.st_ino == stat.st_ino {
                        let logical = self
                            .names
                            .map_or(Cow::Borrowed(listed), |names| names.logical(listed));
                        spelling = Some(join(path, &logical));
                        break;
                    }
                }
                if let Some(spelling) = spelling {
                    if self.paths.matches_unchecked(&spelling)
                        || self.paths.directory(&spelling) != Prune::Skip
                    {
                        child = spelling;
                    } else if selected || self.paths.directory(&child) == Prune::Skip {
                        continue;
                    }
                    // A descendant pathspec can explicitly traverse the index spelling even
                    // where it doesn't match the directory's listed name, as Git does.
                }
            }
            if tracked.is_some() && !needed && (!self.lists_untracked() || walk.excluded) {
                found.observe(slot, Observed::Directory);
                continue;
            }
            let mut inner = walk;
            if ignoring {
                let ignored =
                    walk.excluded || self.ignored(rules.as_ref(), &child, InputKind::Directory)?;
                if needed {
                    inner.excluded = ignored;
                } else {
                    // Git's collapsed listing hides a directory at a tracked file's path.
                    if ignored || (tracked.is_some() && collapsed) {
                        found.observe(slot, Observed::Directory);
                        continue;
                    }
                    // Under a pathspec Git collapses a directory only when the spec matches the
                    // directory itself, written with its trailing slash; otherwise it lists the
                    // matching paths inside.
                    if collapsed && inner.collapse.is_none() && self.selects_directory(&child) {
                        inner.collapse = Some(found.listed.len());
                    }
                }
            }
            if depth >= self.max_depth {
                return Err(Error::Limit("directory depth"));
            }
            if inner.collapse.is_some() {
                // A collapsed listing depends on what this worker finds first, so the subtree
                // stays on this worker.
                let visited = self.child_directory(
                    found,
                    fd,
                    name,
                    &child,
                    &stat,
                    depth + 1,
                    inner,
                    rules.clone(),
                )?;
                self.list_directory(found, child, visited, walk, inner);
            } else {
                self.push(Task {
                    open: Open::Child {
                        parent: Arc::clone(fd),
                        name: name.to_vec(),
                        stat,
                    },
                    path: child,
                    depth: depth + 1,
                    walk: inner,
                    rules: rules.clone(),
                    listed: ignoring && !needed,
                });
            }
        }
        let after = fstat(&**fd).map_err(|source| io(path, source))?;
        same(path, before, &after)?;
        if let Some(capture) = &self.capture {
            let untracked = found
                .listed
                .iter()
                .filter_map(|entry| {
                    let parent = entry
                        .path
                        .iter()
                        .rposition(|byte| *byte == b'/')
                        .map_or(&b""[..], |position| &entry.path[..position]);
                    (parent == path).then(|| {
                        let mut name = entry
                            .path
                            .get(path.len() + usize::from(!path.is_empty())..)
                            .unwrap_or_default()
                            .to_vec();
                        if entry.kind != UntrackedKind::File {
                            name.push(b'/');
                        }
                        name
                    })
                })
                .collect();
            capture
                .directories
                .lock()
                .unwrap_or_else(std::sync::PoisonError::into_inner)
                .insert(
                    path.to_vec(),
                    super::untracked::Record {
                        stat: index_stat(before),
                        exclude: names.ignore_content.as_ref().map(|bytes| {
                            let literal = ObjectId::for_blob(self.format, bytes);
                            let ignore_path = join(path, b".gitignore");
                            if self.tracked.entry(&ignore_path).is_some_and(|(_, entry)| {
                                entry.stage == index::Stage::Normal && entry.id == literal
                            }) {
                                literal
                            } else {
                                super::untracked::ignore_id(self.format, bytes)
                            }
                        }),
                        untracked,
                        check_only: walk.collapse.is_some(),
                        valid: !walk.excluded,
                    },
                );
        }
        Ok(Visited::Directory)
    }

    /// Lists a visible untracked directory after its traversal.
    fn list_directory(
        &self,
        found: &mut Found,
        path: Vec<u8>,
        visited: Visited,
        outer: Walk,
        inner: Walk,
    ) {
        let kind = match visited {
            Visited::Repository if !self.selects_directory(&path) => return,
            Visited::Repository => UntrackedKind::Repository,
            Visited::Metadata => return,
            Visited::Directory => {
                // Only the outermost collapsed directory replaces what was found inside it.
                let Some(mark) = inner.collapse.filter(|_| outer.collapse.is_none()) else {
                    return;
                };
                if found.listed.len() == mark {
                    return;
                }
                found.listed.truncate(mark);
                UntrackedKind::Directory
            }
        };
        found.listed.push(UntrackedPath { path, kind });
    }

    #[expect(clippy::too_many_arguments, reason = "one leaf's observation state")]
    fn leaf(
        &self,
        found: &mut Found,
        fd: &OwnedFd,
        name: &[u8],
        path: &[u8],
        stat: &Stat,
        tracked: Option<(usize, &index::Entry)>,
        slots: Slots,
        rules: Option<&Arc<Ignore>>,
    ) -> Result<(), Error> {
        let kind = FileType::from_raw_mode(stat.st_mode);
        let Some((_, entry)) = tracked else {
            // An untracked leaf can still block a tracked directory of the same name.
            found.observe(slots, Observed::Blocked);
            match self.policy {
                Policy::Raw(Untracked::RawFilesWithoutIgnores) => {
                    found.untracked.push(path.to_vec());
                }
                // Git lists only regular files and symlinks, never sockets or FIFOs.
                Policy::Ignoring(files)
                    if files != UntrackedFiles::Omit
                        && matches!(kind, FileType::RegularFile | FileType::Symlink)
                        && !self.ignored(rules, path, InputKind::File)? =>
                {
                    found.listed.push(UntrackedPath {
                        path: path.to_vec(),
                        kind: UntrackedKind::File,
                    });
                }
                _ => (),
            }
            return Ok(());
        };
        // All-files listing still inspects the kind: a directory replacing a promised leaf can
        // contain untracked files. Its tracked content remains unchecked.
        if self.configured && (entry.assume_valid || entry.skip_worktree) {
            return Ok(());
        }
        let mode = match kind {
            FileType::RegularFile if !self.symlinks && entry.mode == index::Mode::Symlink => {
                EntryMode::Symlink
            }
            FileType::RegularFile
                if !self.file_mode
                    && matches!(entry.mode, index::Mode::Regular | index::Mode::Executable) =>
            {
                value(entry).mode
            }
            FileType::RegularFile if stat.st_mode & 0o100 != 0 => EntryMode::Executable,
            FileType::RegularFile => EntryMode::Blob,
            FileType::Symlink => EntryMode::Symlink,
            _ => {
                found.observe(slots, Observed::Blocked);
                return Ok(());
            }
        };
        if !entry.intent_to_add && self.unchanged(entry, stat, mode) {
            found.observe(slots, Observed::Leaf(value(entry)));
            return Ok(());
        }
        let max = self.max_file_bytes.min(self.worktree_bytes.remaining());
        let bytes = if kind == FileType::Symlink {
            // One extra byte distinguishes an exact limit from truncation. Cap by the platform's
            // path bound as well, avoiding an oversized allocation for a caller's huge limit.
            let capacity = max
                .min(1024 * 1024)
                .checked_add(1)
                .ok_or(Error::Limit("file bytes"))?;
            let mut bytes = vec![0; capacity];
            let count =
                rustix::fs::readlinkat_raw(fd, OsStr::from_bytes(name), bytes.as_mut_slice())
                    .map_err(|source| io(path, source))?;
            self.check_bytes(count)?;
            if count == capacity {
                return Err(Error::Limit("file bytes"));
            }
            bytes.truncate(count);
            bytes
        } else {
            self.read_file(fd, name, path, stat, max)?
        };
        self.worktree_bytes.charge(bytes.len(), "worktree bytes")?;
        (self.after_read)(path);
        self.check()?;
        let after = statat(fd, OsStr::from_bytes(name), AtFlags::SYMLINK_NOFOLLOW)
            .map_err(|source| io(path, source))?;
        same(path, stat, &after)?;
        let (observed, resized) = match self.filters.filter(|_| kind == FileType::RegularFile) {
            None => (
                TreeValue {
                    id: ObjectId::for_blob(self.format, &bytes),
                    mode,
                },
                false,
            ),
            Some(filters) => {
                let staged = (entry.mode != index::Mode::Gitlink).then_some(entry.id);
                let id = ObjectId::for_blob(self.format, &filters.convert(path, &bytes, staged)?);
                let cached = entry.stat.size;
                (
                    TreeValue { id, mode },
                    cached != 0 && cached != stat.st_size as u32,
                )
            }
        };
        if resized {
            found.observe(slots, Observed::Resized(observed));
            return Ok(());
        }
        found.observe(slots, Observed::Leaf(observed));
        // `same` showed the bytes were read from the file these words describe.
        if let Some(position) = slots.entry
            && entry.stage == index::Stage::Normal
            && observed == value(entry)
        {
            found.verified.push((position, index_stat(stat)));
        }
        Ok(())
    }

    /// Whether the index's cached stat words show this leaf unchanged, so its content need not be
    /// read.
    ///
    /// The cached words [`StatPolicy`] selects must equal the observed ones and the mode must
    /// match. An entry is racily
    /// clean, and is read, when its cached mtime or ctime is in or after the second the index was
    /// written: a change within that second could leave every word equal. Git's rule compares
    /// the mtime with nanoseconds; comparing whole seconds of both times rereads a superset of
    /// what Git rereads. A zero cached size is how writers mark an entry for rereading.
    fn unchanged(&self, entry: &index::Entry, stat: &Stat, mode: EntryMode) -> bool {
        let Some(written) = self.index_written else {
            return false;
        };
        // Index words hold the low 32 bits of each value, as Git writes them.
        // Field types differ by platform (Linux nanoseconds are unsigned), so each is truncated
        // directly rather than through a common type.
        let mtime = index::Timestamp {
            seconds: stat.st_mtime as u32,
            nanoseconds: stat.st_mtime_nsec as u32,
        };
        let ctime = index::Timestamp {
            seconds: stat.st_ctime as u32,
            nanoseconds: stat.st_ctime_nsec as u32,
        };
        let cached = &entry.stat;
        let policy = self.stat_policy;
        let time = |cached: index::Timestamp, actual: index::Timestamp| {
            if policy.minimal {
                cached.seconds == actual.seconds
            } else {
                cached == actual
            }
        };
        entry.stage == index::Stage::Normal
            && value(entry).mode == mode
            && cached.size != 0
            && cached.size == stat.st_size as u32
            && time(cached.mtime, mtime)
            && (!policy.trust_ctime || time(cached.ctime, ctime))
            && (policy.minimal
                || (cached.device == stat.st_dev as u32
                    && cached.inode == stat.st_ino as u32
                    && cached.uid == stat.st_uid
                    && cached.gid == stat.st_gid))
            && cached.mtime.seconds < written
            && cached.ctime.seconds < written
    }

    /// Keep the per-file ceiling distinct from the remaining aggregate read budget.
    fn check_bytes(&self, size: usize) -> Result<(), Error> {
        if size > self.max_file_bytes {
            return Err(Error::Limit("file bytes"));
        }
        if size > self.worktree_bytes.remaining() {
            return Err(Error::Limit("worktree bytes"));
        }
        Ok(())
    }

    fn read_file(
        &self,
        fd: &OwnedFd,
        name: &[u8],
        path: &[u8],
        stat: &Stat,
        max: usize,
    ) -> Result<Vec<u8>, Error> {
        let opened = openat(
            fd,
            OsStr::from_bytes(name),
            OFlags::RDONLY | OFlags::NOFOLLOW | OFlags::CLOEXEC | OFlags::NONBLOCK,
            Mode::empty(),
        )
        .map_err(|source| io(path, source))?;
        let before = fstat(&opened).map_err(|source| io(path, source))?;
        same(path, stat, &before)?;
        if FileType::from_raw_mode(before.st_mode) != FileType::RegularFile {
            return Err(Error::Changed(path.to_vec()));
        }
        let size = usize::try_from(before.st_size).map_err(|_| Error::Limit("file bytes"))?;
        self.check_bytes(size)?;
        let mut file = File::from(opened);
        let mut bytes = Vec::with_capacity(size.min(max));
        let mut buffer = [0u8; 64 * 1024];
        loop {
            self.check()?;
            let remaining = max - bytes.len();
            let count = file
                .read(&mut buffer[..remaining.saturating_add(1).min(64 * 1024)])
                .map_err(|source| io(path, source))?;
            self.check_bytes(bytes.len() + count)?;
            if count == 0 {
                break;
            }
            bytes.extend_from_slice(&buffer[..count]);
        }
        let after = fstat(&file).map_err(|source| io(path, source))?;
        same(path, &before, &after)?;
        if bytes.len() != size {
            return Err(Error::Changed(path.to_vec()));
        }
        Ok(bytes)
    }
}

/// Which cached stat words decide that a file is unchanged without reading it.
///
/// Raw status compares every word. Configured status follows Git's `core.checkStat` and
/// `core.trustCtime`: `minimal` compares only the size and the whole seconds of the mtime (and of
/// the ctime, when trusted); an untrusted ctime is never compared.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct StatPolicy {
    minimal: bool,
    trust_ctime: bool,
}

impl Default for StatPolicy {
    fn default() -> Self {
        Self {
            minimal: false,
            trust_ctime: true,
        }
    }
}

impl StatPolicy {
    fn configured(repo: &Repository) -> Result<Self, Error> {
        let config = repo.config();
        let trust_ctime = config
            .boolean("core", None, "trustctime")
            .map_err(|_| unsupported(b"", "invalid core.trustCtime boolean"))?
            .unwrap_or(true);
        // Git accepts either value in any case and refuses anything else, including no value.
        let minimal = match config.value("core", None, "checkstat") {
            None => false,
            Some(Some(value)) if value.eq_ignore_ascii_case(b"default") => false,
            Some(Some(value)) if value.eq_ignore_ascii_case(b"minimal") => true,
            Some(_) => return Err(unsupported(b"", "invalid core.checkStat value")),
        };
        Ok(Self {
            minimal,
            trust_ctime,
        })
    }
}

/// The index's stat words for `stat`: the low 32 bits of each value, as Git writes them.
fn index_stat(stat: &Stat) -> index::Stat {
    // Field types differ by platform, so each is truncated directly.
    index::Stat {
        ctime: index::Timestamp {
            seconds: stat.st_ctime as u32,
            nanoseconds: stat.st_ctime_nsec as u32,
        },
        mtime: index::Timestamp {
            seconds: stat.st_mtime as u32,
            nanoseconds: stat.st_mtime_nsec as u32,
        },
        device: stat.st_dev as u32,
        inode: stat.st_ino as u32,
        uid: stat.st_uid,
        gid: stat.st_gid,
        size: stat.st_size as u32,
    }
}

/// Every name in one directory except `.` and `..`, packed into one buffer.
#[derive(Default)]
struct Names {
    cached: bool,
    // Reuse exactly the ignore bytes whose hash admitted this listing, avoiding a second read
    // that could pair changed rules with an older cached listing.
    ignore_observed: bool,
    ignore_content: Option<Vec<u8>>,
    bytes: Vec<u8>,
    ends: Vec<usize>,
}

impl Scan<'_> {
    /// Reads every name in a directory, charging each to the entry and path budgets and checking
    /// cancellation as it is read, so a huge directory cannot outgrow them.
    ///
    /// Reads through a duplicate descriptor, which is cheaper than reopening the directory and
    /// leaves `fd` for the `*at` calls that follow. Those calls do not use the shared offset.
    fn read_names(&self, fd: &OwnedFd, path: &[u8]) -> Result<Names, Error> {
        let duplicate = rustix::io::dup(fd).map_err(|source| io(path, source))?;
        let directory = Dir::new(duplicate).map_err(|source| io(path, source))?;
        let mut names = Names::default();
        for entry in directory {
            self.check()?;
            let entry = entry.map_err(|source| io(path, source))?;
            let name = entry.file_name().to_bytes();
            if name == b"." || name == b".." {
                continue;
            }
            self.directory_entries.charge(1, "directory entries")?;
            let length = path
                .len()
                .checked_add(name.len())
                .and_then(|n| n.checked_add(usize::from(!path.is_empty())))
                .ok_or(Error::Limit("path bytes"))?;
            self.path_bytes.charge(length, "path bytes")?;
            names.bytes.extend_from_slice(name);
            names.ends.push(names.bytes.len());
        }
        Ok(names)
    }
}

impl Names {
    fn iter(&self) -> impl Iterator<Item = &[u8]> {
        let starts = std::iter::once(0).chain(self.ends.iter().copied());
        starts
            .zip(&self.ends)
            .map(|(start, end)| &self.bytes[start..*end])
    }

    /// Whether `lstat` of the ASCII name `target` could succeed here. A case-insensitive
    /// filesystem resolves any ASCII case variant, and non-ASCII names are not ruled out.
    fn may_name(&self, target: &[u8]) -> bool {
        self.cached
            || self
                .iter()
                .any(|name| !name.is_ascii() || name.eq_ignore_ascii_case(target))
    }

    /// [`repository_marker`], skipping each `lstat` that no listed name could satisfy.
    fn repository_marker(&self, fd: &OwnedFd, path: &[u8]) -> Result<bool, Error> {
        let present = |name: &[u8]| -> Result<bool, Error> {
            Ok(self.may_name(name) && optional_stat(fd, name, path)?.is_some())
        };
        Ok(present(b".git")? || (present(b"HEAD")? && present(b"objects")? && present(b"refs")?))
    }
}

/// Index entries and the directories that contain them, looked up by path.
///
/// Every tracked path and directory has a slot: entries by their position in the index (the first
/// stage for a conflicted path), then directories after them.
pub(crate) fn validate_path(path: &[u8]) -> Result<(), Error> {
    if path.is_empty()
        || path.contains(&0)
        || path.split(|byte| *byte == b'/').any(|part| {
            part.is_empty() || part == b"." || part == b".." || part.eq_ignore_ascii_case(b".git")
        })
    {
        return Err(unsupported(path, "unsafe path"));
    }
    Ok(())
}

pub(crate) fn directory_flags() -> OFlags {
    OFlags::RDONLY | OFlags::DIRECTORY | OFlags::NOFOLLOW | OFlags::CLOEXEC
}

// Opening the absolute root component-by-component avoids following a substituted ancestor.
pub(crate) fn open_root(path: &Path) -> Result<OwnedFd, Error> {
    let mut fd = rustix::fs::open("/", directory_flags(), Mode::empty())
        .map_err(|source| io(b"", source))?;
    for component in path.components() {
        match component {
            Component::RootDir => (),
            Component::Normal(name) => {
                fd = openat(&fd, name, directory_flags(), Mode::empty())
                    .map_err(|source| io(b"", source))?;
            }
            _ => {
                return Err(unsupported(
                    b"",
                    "working-tree root is not canonical absolute",
                ));
            }
        }
    }
    Ok(fd)
}

pub(crate) fn repository_marker(fd: &OwnedFd, path: &[u8]) -> Result<bool, Error> {
    if optional_stat(fd, b".git", path)?.is_some() {
        return Ok(true);
    }
    // Conservatively recognize a bare repository without reading its metadata.
    Ok(optional_stat(fd, b"HEAD", path)?.is_some()
        && optional_stat(fd, b"objects", path)?.is_some()
        && optional_stat(fd, b"refs", path)?.is_some())
}

pub(crate) fn optional_stat(fd: &OwnedFd, name: &[u8], path: &[u8]) -> Result<Option<Stat>, Error> {
    match statat(fd, OsStr::from_bytes(name), AtFlags::SYMLINK_NOFOLLOW) {
        Ok(stat) => Ok(Some(stat)),
        Err(rustix::io::Errno::NOENT) => Ok(None),
        Err(source) => Err(io(path, source)),
    }
}

pub(crate) fn same(path: &[u8], before: &Stat, after: &Stat) -> Result<(), Error> {
    if before.st_dev != after.st_dev
        || before.st_ino != after.st_ino
        || before.st_mode != after.st_mode
        || before.st_size != after.st_size
        || before.st_mtime != after.st_mtime
        || before.st_mtime_nsec != after.st_mtime_nsec
        || before.st_ctime != after.st_ctime
        || before.st_ctime_nsec != after.st_ctime_nsec
    {
        Err(Error::Changed(path.to_vec()))
    } else {
        Ok(())
    }
}
fn join(parent: &[u8], name: &[u8]) -> Vec<u8> {
    let mut path = parent.to_vec();
    if !path.is_empty() {
        path.push(b'/');
    }
    path.extend_from_slice(name);
    path
}
fn io(path: &[u8], source: impl Into<std::io::Error>) -> Error {
    Error::Io {
        path: path.to_vec(),
        source: source.into(),
    }
}
fn unsupported(path: &[u8], reason: &'static str) -> Error {
    Error::Unsupported {
        path: path.to_vec(),
        reason,
    }
}

mod parallel;
#[cfg(test)]
mod tests;
mod tracked;