tsv_ignore 0.8.0

//! gitignore-style path matching for tsv's file discovery.
//!
//! tsv is non-configurable for *style*, but file *scope* is the one sanctioned
//! carve-out: gitignore-shaped files say which files `tsv format` reformats.
//! This crate is the shared, pure-Rust matcher behind that feature — used
//! natively by the `tsv` CLI and, through tsv's npm packages, by the JS CLI and the VS Code
//! extension. Part of [tsv](https://github.com/fuzdev/tsv). It implements the
//! [gitignore(5) pattern format](https://git-scm.com/docs/gitignore#_pattern_format),
//! the same grammar prettier matches via its `ignore` dependency and git matches
//! for `.gitignore`.
//!
//! The matcher is one type, [`IgnoreStack`] — a hierarchical, git-faithful evaluator: a
//! stack of per-directory `.gitignore` layers plus a parallel stack of per-directory
//! override layers (`.formatignore`), each layer one ignore file's rules anchored at its
//! directory, evaluated against paths relative to the format root ([Paths](#paths)) with
//! git's last-match-wins + parent-directory-prune semantics (oracle:
//! `git check-ignore --no-index`). At each path level every `.gitignore` layer is
//! evaluated, then every override layer, so an override-layer `!` can re-include a
//! gitignore'd path (subject to git's parent-dir rule) and a deeper layer wins over a
//! shallower one.
//!
//! Locating the files, resolving paths relative to them, and walking directories
//! are the callers' jobs. The caller decides which files become layers (tsv reads
//! `.formatignore` hierarchically and, inside a git repo, `.prettierignore`
//! hierarchically too — each shadowed by a sibling `.formatignore`); a layer records
//! which of the three it was read from, which changes nothing about matching and is
//! what a diagnostic about a match names ([`IgnoreStack::exclusion`]).
//!
//! ```
//! use tsv_ignore::{IgnoreStack, PathKind};
//!
//! let mut stack = IgnoreStack::new();
//! stack.push_gitignore("", "build/\n*.log\n"); // root .gitignore
//! stack.push_gitignore("a", "!*.log\n"); // a/.gitignore re-includes logs
//! stack.push_formatignore("", "*.snap\n"); // root override layer, applied after the gitignores
//! assert!(stack.is_ignored("build/out.js", PathKind::File));
//! assert!(stack.is_ignored("debug.log", PathKind::File));
//! assert!(!stack.is_ignored("a/debug.log", PathKind::File)); // a deeper `!` wins
//! assert!(stack.is_ignored("test/x.snap", PathKind::File)); // via the override layer
//! assert!(stack.is_ignored("build", PathKind::Directory)); // `build/` matches a directory
//! assert!(!stack.is_ignored("build", PathKind::File)); // ...never a file of that name
//! ```
//!
//! ## Differences from git
//!
//! The `.gitignore` half answers as `git check-ignore --no-index` does, except:
//!
//! - **No index.** A matcher reads rules, not git's index, so a tracked file a rule matches
//!   is ignored here, where plain `git check-ignore` (and `git status`) exempt it. A caller
//!   that wants git's view of a tracked file asks git.
//! - **Always case-sensitive.** Git on macOS and Windows sets `core.ignorecase` and matches
//!   case-insensitively there; reading machine-local git config would make the answer
//!   differ between machines.
//! - **Only `.gitignore` files.** `.git/info/exclude` and `core.excludesFile` are local,
//!   uncommitted sources, not read for the same reason.
//! - **Per code point.** `?`, `*` and `[...]` match per Unicode code point, where git
//!   matches per byte (and prettier's `ignore` per UTF-16 unit), so the three can disagree
//!   on a non-ASCII name.
//! - **No POSIX bracket classes.** `[[:alpha:]]` is read as ordinary class members, as
//!   prettier's matcher reads it.
//! - **A `**` glued to a literal prefix** (`foo**/bar.ts`) is two stars within one segment,
//!   as gitignore(5) says; git's matcher crosses directories there.
//!
//! ## A walk
//!
//! A directory's own `.gitignore` never classifies that directory — its parent's rules do —
//! so a walk asks about a child directory BEFORE pushing the child's layers, then descends,
//! then pops them. Below the root, only a directory the stack did not ignore is entered, so
//! a file inside is asked with [`is_ignored_leaf`](IgnoreStack::is_ignored_leaf), which
//! skips the ancestor walk [`is_ignored`](IgnoreStack::is_ignored) repeats:
//!
//! ```
//! use tsv_ignore::{IgnoreStack, PathKind};
//!
//! // walks `tree` (a stand-in filesystem: each directory's `.gitignore` and entries)
//! fn walk(stack: &mut IgnoreStack, dir: &str, tree: &Tree, found: &mut Vec<String>) {
//!     let pushed = tree.gitignore(dir).is_some();
//!     if let Some(content) = tree.gitignore(dir) {
//!         stack.push_gitignore(dir, content);
//!     }
//!     for (name, is_dir) in tree.children(dir) {
//!         let child = if dir.is_empty() { name.to_string() } else { format!("{dir}/{name}") };
//!         if is_dir {
//!             if !stack.is_ignored_leaf(&child, PathKind::Directory) {
//!                 walk(stack, &child, tree, found);
//!             }
//!         } else if !stack.is_ignored_leaf(&child, PathKind::File) {
//!             found.push(child);
//!         }
//!     }
//!     if pushed {
//!         stack.pop_gitignore();
//!     }
//! }
//! # struct Tree;
//! # impl Tree {
//! #     fn gitignore(&self, dir: &str) -> Option<&'static str> {
//! #         match dir { "" => Some("build/\n"), "src" => Some("*.gen.ts\n"), _ => None }
//! #     }
//! #     fn children(&self, dir: &str) -> Vec<(&'static str, bool)> {
//! #         match dir {
//! #             "" => vec![("build", true), ("src", true), ("a.ts", false)],
//! #             "src" => vec![("b.ts", false), ("c.gen.ts", false)],
//! #             _ => vec![("out.ts", false)],
//! #         }
//! #     }
//! # }
//!
//! let mut found = Vec::new();
//! walk(&mut IgnoreStack::new(), "", &Tree, &mut found);
//! assert_eq!(found, ["src/b.ts", "a.ts"]);
//! ```
//!
//! ## Paths
//!
//! Every path a query or a push takes is relative to the **format root** — the directory
//! the caller scopes its walk to, typically the repository root — and `/`-separated:
//!
//! - `\` is never a separator, on any platform — a caller on Windows converts first: hand a
//!   `std::path::Path` over as its `Normal` components joined by `/`;
//! - empty and `.` segments are dropped, so a leading `/` (`/a` is `a`), a doubled `//`
//!   and a `./` change nothing;
//! - `..` is a literal segment, never a step up — a caller resolves it first;
//! - a trailing `/` is an empty segment, dropped like the rest: whether a path is a
//!   directory is the [`PathKind`] a query takes, never its spelling;
//! - a name that is not UTF-8 is handed over in its lossy spelling, as the `tsv` CLI does.
//!   Each maximal invalid sequence is then one U+FFFD, which a `?` matches where git needs
//!   one per byte (the per-code-point difference above), and two names that differ only
//!   inside such a sequence read alike.
//!
//! ## Stability
//!
//! The public signatures follow 0.x semver like every tsv crate: a breaking change ships
//! only in a minor release. The items hidden from these docs — the `IgnoreStack` queries
//! that exist for tsv's discovery policy, and the `Negation*` types one of them returns —
//! are tsv's own plumbing for `tsv_discover`, outside semver.

#![warn(missing_docs)]
// The README's example compiles as a doctest, so the crates.io page cannot drift.
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeDoctests;

mod glob;

use glob::{PathSeg, Seg, Tok, match_segments, parse_segment};

/// A compiled set of ignore rules, applied in source order with last-match-wins
/// semantics (a later `!` negation re-includes an earlier exclusion).
#[derive(Debug, Default, Clone)]
pub(crate) struct IgnoreRules {
    rules: Vec<Rule>,
}

#[derive(Debug, Clone)]
struct Rule {
    segs: Vec<Seg>,
    /// `!`-prefixed: re-includes a path an earlier rule excluded.
    negated: bool,
    /// For a negated rule, its segments as the author wrote them after the `!` and any
    /// leading `/` — what a diagnostic re-spells anchored, from any segment on
    /// ([`NegationRule::pattern`]). `None` for every other rule, which no diagnostic
    /// quotes.
    spelling: Option<Box<[SpelledSeg]>>,
    /// trailing-`/`: matches directories only.
    dir_only: bool,
}

/// One segment of a negated rule as its author spelled it (trailing spaces trimmed,
/// escapes kept), and whether a `\/` rather than a bare `/` ended it.
#[derive(Debug, Clone)]
struct SpelledSeg {
    text: Box<str>,
    escaped_separator: bool,
}

impl Rule {
    fn matches(&self, path: &[PathSeg<'_>], is_dir: bool) -> bool {
        if self.dir_only && !is_dir {
            return false;
        }
        match_segments(&self.segs, path)
    }

    /// For a negated rule, its fixed leading path — the run of literal (non-glob)
    /// segments before the first wildcard or `**` — expressed relative to the
    /// rule's layer, and how the rule continues past that run. `None` for a
    /// non-negated rule. A *floating* negation (`!name`, which parses to a leading
    /// `**`) yields an empty path, so it is never anchored strictly under any
    /// directory. Powers [`IgnoreStack::negation_under`].
    fn negation_leading_path(&self) -> Option<(Vec<String>, NegationTail)> {
        self.negated.then(|| {
            let leading: Vec<String> = self.segs.iter().map_while(Seg::literal).collect();
            let tail = match &self.segs[leading.len()..] {
                [] => NegationTail::None,
                [Seg::Glob(_)] => NegationTail::Children,
                _ => NegationTail::Descendants,
            };
            (leading, tail)
        })
    }

    /// A negated rule's pattern from its `skip`th segment on, spelled as the author
    /// did — for a file `skip` directories below the rule's own, where the same rule
    /// anchored reads `/` + this. Empty for a non-negated rule.
    fn spelling_from(&self, skip: usize) -> String {
        let Some(segs) = self.spelling.as_deref() else {
            return String::new();
        };
        let mut pattern = String::new();
        for (i, seg) in segs.iter().enumerate().skip(skip) {
            if i > skip {
                pattern.push_str(if segs[i - 1].escaped_separator {
                    "\\/"
                } else {
                    "/"
                });
            }
            pattern.push_str(&seg.text);
        }
        if self.dir_only {
            pattern.push('/');
        }
        pattern
    }
}

impl IgnoreRules {
    /// Parses the text of one ignore file into a rule set.
    pub(crate) fn parse(content: &str) -> Self {
        // A leading UTF-8 BOM is not part of the first pattern: git skips it
        // (`add_patterns_from_buffer`), and an editor that writes one would otherwise
        // silently disable the file's first rule — in the unsafe direction, since
        // the first rule of a `.gitignore` is `node_modules` more often than not.
        let content = content.strip_prefix('\u{feff}').unwrap_or(content);
        // One rule per `\n`-separated line, one trailing `\r` stripped from each — the
        // last line's too, which git reads as if the file ended in a newline. (`lines()`
        // strips a `\r` only ahead of a `\n`, so a final `rule\r` kept it and never matched.)
        // A line then ends at its first NUL: git reads each pattern as a C string, so
        // `b.ts<NUL>junk` is the rule `b.ts` — the `\r` is stripped first, as git strips it
        // off the line before the pattern's own length is read.
        let rules = content
            .split('\n')
            .map(|line| line.strip_suffix('\r').unwrap_or(line))
            .map(|line| line.split_once('\0').map_or(line, |(pattern, _)| pattern))
            .filter_map(parse_line)
            .collect();
        Self { rules }
    }

    /// Whether there are no rules (no ignore files, or only comments/blanks) — what the
    /// parse tests grade a dropped line by. The stack never asks it: an empty layer
    /// matches nothing, and its presence alone can still set the regime
    /// ([`IgnoreStack::has_gitignore_layers`]).
    #[cfg(test)]
    pub(crate) fn is_empty(&self) -> bool {
        self.rules.is_empty()
    }

    /// Whether `path` is ignored. `path` is relative to the ignore-file root,
    /// `/`-separated; `is_dir` marks it as a directory (so trailing-`/`
    /// patterns apply).
    ///
    /// Evaluated top-down over the path's ancestors: as soon as an ancestor
    /// directory is excluded, the path is ignored and no deeper `!` can
    /// re-include it — matching git's "cannot re-include a file if a parent
    /// directory is excluded" rule. This also means a file under a directory
    /// that matches any rule (e.g. `build/`) is reported ignored without the
    /// caller having to test the directory separately.
    ///
    /// The stack never asks this — it layers `last_match` per prefix itself — so the
    /// single-file form survives only for the unit tests that grade one file's rules.
    #[cfg(test)]
    pub(crate) fn is_ignored(&self, path: &str, is_dir: bool) -> bool {
        first_excluded_prefix(path, is_dir, |prefix, dir| {
            self.last_match(prefix, dir).map(|ignored| (ignored, ()))
        })
        .is_some()
    }

    /// The polarity of the last rule matching `path` (one path, its segments
    /// relative to this file's root), or `None` if no rule matches.
    /// `Some(true)` excludes, `Some(false)` re-includes (a `!` negation). This
    /// is the per-level primitive [`IgnoreStack`] layers across files; on its
    /// own it does *not* apply the ancestor prune (the caller iterates prefixes).
    fn last_match(&self, path: &[PathSeg<'_>], is_dir: bool) -> Option<bool> {
        // last-match-wins, read as first-match-wins backwards: identical answer, and
        // the scan stops at the first rule that speaks — on the hot path (per layer,
        // per prefix, per entry) that is the whole difference between walking every
        // rule of a long `.gitignore` for each of a pruned tree's files and stopping
        // at the one that prunes it
        self.rules
            .iter()
            .rev()
            .find(|rule| rule.matches(path, is_dir))
            .map(|rule| !rule.negated)
    }
}

/// A hierarchical, git-faithful ignore evaluator: a stack of per-directory
/// `.gitignore` layers plus a parallel stack of per-directory override layers — the
/// **override** layers (`.formatignore` / `.prettierignore`), read after every
/// `.gitignore` so they win over it.
///
/// [`push_gitignore`](IgnoreStack::push_gitignore) /
/// [`push_formatignore`](IgnoreStack::push_formatignore) /
/// [`push_prettierignore`](IgnoreStack::push_prettierignore) add one directory's
/// `.gitignore` / override file, anchored at that directory
/// relative to the format root (the caller's chosen scope root). Layers **must** be
/// pushed shallowest-first (the order a DFS descends) — a directory's layer after every
/// ancestor's of the same kind: precedence among them is push order, not anchor depth,
/// so a deeper layer pushed ahead of its ancestor's loses to it and the answer is wrong.
/// The CLI calls [`pop_gitignore`](IgnoreStack::pop_gitignore) /
/// [`pop_override`](IgnoreStack::pop_override) on the way back up; non-traversal callers
/// (the VS Code extension) just push the whole chain.
///
/// [`is_ignored`](IgnoreStack::is_ignored) walks the path's ancestors top-down
/// and, at each level, evaluates every applicable `.gitignore` layer
/// (shallow→deep) then every applicable override layer (shallow→deep), last-match
/// winning. So an override layer overrides any `.gitignore`, a deeper layer overrides
/// a shallower one of its own kind, and a positive match at an ancestor prunes
/// the subtree before a deeper `!` can re-include it — matching git's "cannot
/// re-include a file whose parent directory is excluded" rule. The gitignore-only
/// behavior is byte-for-byte `git check-ignore` on case-sensitive filesystems, less
/// the [differences](crate#differences-from-git) the crate docs list.
///
/// Why a path is ignored, and which file says so, is [`exclusion`](Self::exclusion):
///
/// ```
/// use tsv_ignore::{IgnoreSource, IgnoreStack, PathKind};
///
/// let mut stack = IgnoreStack::new();
/// stack.push_gitignore("", "dist/\n");
/// stack.push_formatignore("src", "*.gen.ts\n");
///
/// // `dist/` excludes the directory, so the whole path is out of scope from depth 1
/// let exclusion = stack.exclusion("dist/app.js", PathKind::File).unwrap();
/// assert_eq!((exclusion.depth, exclusion.anchor_depth), (1, 0));
/// assert_eq!(exclusion.source, IgnoreSource::Gitignore);
///
/// // `src/.formatignore` excludes the file itself
/// let exclusion = stack.exclusion("src/a.gen.ts", PathKind::File).unwrap();
/// assert_eq!(exclusion.source.file_name(), ".formatignore");
/// assert_eq!(stack.exclusion("src/a.ts", PathKind::File), None);
/// ```
///
/// A push takes any content and returns nothing to check — a line git could never match is
/// dropped, as git drops it (only the debug-build order assertion can panic) — and a pop with
/// no layer of its kind pushed does nothing.
#[derive(Debug, Default, Clone)]
pub struct IgnoreStack {
    /// `.gitignore` layers in shallow→deep push order.
    gitignore: Vec<Layer>,
    /// override layers (`.formatignore`, plus a `.prettierignore` the caller may
    /// resolve — both hierarchical) in shallow→deep push order, evaluated after
    /// every `.gitignore`.
    overrides: Vec<Layer>,
}

// A stack is plain data a caller may share across threads and hold across a caught panic (a
// discovery worker pool); pin that so a field added later cannot take it away unnoticed.
const _: () = {
    const fn assert_auto_traits<
        T: Send + Sync + std::panic::UnwindSafe + std::panic::RefUnwindSafe,
    >() {
    }
    assert_auto_traits::<IgnoreStack>();
};

/// One directory's ignore file within an [`IgnoreStack`] — a `.gitignore` or an
/// override file, anchored at the directory it was read from.
#[derive(Debug, Clone)]
struct Layer {
    /// The directory, segments relative to the format root; empty = the root.
    anchor: Vec<String>,
    rules: IgnoreRules,
    /// The file the rules were read from — what a diagnostic about a match names.
    source: IgnoreSource,
}

impl Layer {
    fn new(anchor: &str, content: &str, source: IgnoreSource) -> Self {
        Self {
            anchor: split_path(anchor),
            rules: IgnoreRules::parse(content),
            source,
        }
    }

    /// `prefix` expressed relative to this layer's anchor, or `None` when the
    /// anchor is not a *strict* ancestor of `prefix`. Equal length (the anchor
    /// directory itself) returns `None`: a directory's own `.gitignore` never
    /// classifies that directory — its parent's files do.
    fn relativize<'a, 'p>(&self, prefix: &'p [PathSeg<'a>]) -> Option<&'p [PathSeg<'a>]> {
        if self.anchor.len() >= prefix.len() {
            return None;
        }
        self.anchor
            .iter()
            .zip(prefix)
            .all(|(a, p)| a.as_str() == p.text)
            .then(|| &prefix[self.anchor.len()..])
    }
}

/// The push-order rule, checked in debug builds: no layer already on `stack` may sit in a
/// directory BELOW `layer`'s, since precedence is push order and that deeper layer would
/// then lose to its ancestor's. A sibling's layer left on the stack is harmless (it never
/// applies to the same path) and passes.
fn debug_assert_pushed_in_order(stack: &[Layer], layer: &Layer) {
    debug_assert!(
        !stack.iter().any(|pushed| {
            pushed.anchor.len() > layer.anchor.len()
                && pushed.anchor.iter().zip(&layer.anchor).all(|(p, a)| p == a)
        }),
        "ignore layer {:?} pushed after a layer below it; push shallowest-first",
        layer.anchor.join("/")
    );
}

impl IgnoreStack {
    /// An empty stack (ignores nothing until layers are added).
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Push one directory's `.gitignore`. `anchor` is the directory relative to
    /// the format root, `/`-separated (empty string = the root). It **must** be pushed
    /// after the `.gitignore` of every ancestor directory: precedence is push order, not
    /// anchor depth (debug builds assert it). The layer classifies what is BELOW `anchor`,
    /// never the `anchor` directory itself — its parent's rules do — so a walk asks about a
    /// directory before pushing its layers ([A walk](crate#a-walk)).
    ///
    /// # Panics
    ///
    /// In debug builds, when a `.gitignore` layer is already pushed in a directory below
    /// `anchor` (the push order above is broken).
    pub fn push_gitignore(&mut self, anchor: &str, content: &str) {
        let layer = Layer::new(anchor, content, IgnoreSource::Gitignore);
        debug_assert_pushed_in_order(&self.gitignore, &layer);
        self.gitignore.push(layer);
    }

    /// Pop the most recently pushed `.gitignore` layer (a DFS unwinding out of a
    /// directory).
    pub fn pop_gitignore(&mut self) {
        self.gitignore.pop();
    }

    /// Push one directory's `.formatignore` as an override layer, applied after every
    /// `.gitignore`. `anchor` is the directory relative to the format root,
    /// `/`-separated (empty string = the root). It **must** be pushed after every
    /// ancestor directory's override layer: precedence is push order, not anchor depth.
    ///
    /// # Panics
    ///
    /// In debug builds, when an override layer is already pushed in a directory below
    /// `anchor` (the push order above is broken).
    pub fn push_formatignore(&mut self, anchor: &str, content: &str) {
        self.push_override(anchor, content, IgnoreSource::Formatignore);
    }

    /// Push one directory's `.prettierignore` as an override layer — the file a caller reads in
    /// place of a `.formatignore` the directory does not have. Matched exactly as a
    /// [`push_formatignore`](Self::push_formatignore) layer is; the two differ only in the
    /// file a diagnostic names ([`Exclusion::source`]). The same order rule holds:
    /// it **must** be pushed after every ancestor directory's override layer.
    ///
    /// # Panics
    ///
    /// In debug builds, when an override layer is already pushed in a directory below
    /// `anchor` (the push order above is broken).
    pub fn push_prettierignore(&mut self, anchor: &str, content: &str) {
        self.push_override(anchor, content, IgnoreSource::Prettierignore);
    }

    /// The one override-layer push behind the two public names, which differ only in the
    /// file a diagnostic names.
    fn push_override(&mut self, anchor: &str, content: &str, source: IgnoreSource) {
        let layer = Layer::new(anchor, content, source);
        debug_assert_pushed_in_order(&self.overrides, &layer);
        self.overrides.push(layer);
    }

    /// Pop the most recently pushed override layer — a `.formatignore` or
    /// `.prettierignore` — as a DFS unwinds out of a directory.
    pub fn pop_override(&mut self) {
        self.overrides.pop();
    }

    /// Whether any `.gitignore` layer has been pushed — true even for an
    /// empty/comments-only `.gitignore`, since its mere presence is what turns a
    /// caller's heuristic off (matching git, for which an empty `.gitignore`
    /// still establishes the gitignore regime). tsv's discovery uses this to
    /// assert that an active build-output heuristic has no `.gitignore` layer pushed.
    #[doc(hidden)]
    pub fn has_gitignore_layers(&self) -> bool {
        !self.gitignore.is_empty()
    }

    /// Whether a `.gitignore` layer is anchored at a **strict ancestor** of directory `dir`
    /// (relative to the format root, `/`-separated, normalized as every path here is). The
    /// root anchor is an ancestor of every directory but the root itself; a layer anchored
    /// AT `dir` is that directory's own `.gitignore`, which never classifies the directory,
    /// and does not count. Lets a per-file discovery replay that has no top-down walk — the
    /// VS Code extension formats one open document at a time — reconstruct, for each
    /// ancestor directory, whether the build-output heuristic applies: it is off at a level
    /// once a `.gitignore` anchored above it is present.
    #[doc(hidden)]
    #[must_use]
    pub fn has_gitignore_above(&self, dir: &str) -> bool {
        let dir = split_segments(dir);
        self.gitignore.iter().any(|layer| {
            layer.anchor.len() < dir.len()
                && layer.anchor.iter().zip(&dir).all(|(a, d)| a.as_str() == *d)
        })
    }

    /// Whether `path` (relative to the format root, `/`-separated) is ignored.
    /// `kind` says whether `path` itself is a directory, which trailing-`/` patterns
    /// apply to. [`exclusion`](Self::exclusion) with its witness dropped.
    #[must_use]
    pub fn is_ignored(&self, path: &str, kind: PathKind) -> bool {
        self.exclusion(path, kind).is_some()
    }

    /// Whether `path`'s **own** last-match polarity is an exclusion — the leaf
    /// path evaluated against every layer once, with **no ancestor walk**. Unlike
    /// [`is_ignored`](Self::is_ignored) it does not apply git's parent-directory
    /// prune, so a file under an excluded `build/` is reported *not* ignored
    /// unless a rule matches the file path itself.
    ///
    /// # Contract
    ///
    /// Equivalent to [`is_ignored`](Self::is_ignored) **only when every ancestor
    /// directory of `path` is already known not-ignored.** tsv's discovery walk
    /// guarantees that — it prunes ignored directories before descending, and
    /// gates the initial root with a full [`is_ignored`](Self::is_ignored) — so it
    /// uses this O(1)-per-level query instead of re-walking O(depth) ancestor
    /// prefixes per entry (the matcher dominates discovery cost). **Do not** call
    /// it for an arbitrary path whose ancestors haven't been cleared; that is what
    /// [`is_ignored`](Self::is_ignored) is for.
    #[must_use]
    pub fn is_ignored_leaf(&self, path: &str, kind: PathKind) -> bool {
        self.leaf_polarity(path, kind.is_dir()) == Some(true)
    }

    /// Whether `path` is explicitly *re-included* — the last rule matching this
    /// exact path is a `!` negation (`Some(false)`), with no ancestor prune
    /// applied. Distinct from `!is_ignored`: a path no rule mentions is neither
    /// ignored nor re-included. tsv's discovery uses this to let an explicit
    /// re-include override the build-output heuristic.
    #[doc(hidden)]
    pub fn is_reincluded(&self, path: &str, kind: PathKind) -> bool {
        self.leaf_polarity(path, kind.is_dir()) == Some(false)
    }

    /// The polarity of the last rule matching `path` **itself**, with no ancestor walk —
    /// the one query behind [`is_ignored_leaf`](Self::is_ignored_leaf) and
    /// [`is_reincluded`](Self::is_reincluded), which are its two readings.
    /// `Some(true)` excludes, `Some(false)` re-includes, `None` is a path no rule
    /// mentions — which a segment-less path (`""`, `"."`) always is, since there is
    /// nothing for a rule to match. Stating that once is the point: the two
    /// forms spelled the empty case twice, in two styles, and neither spelling was the
    /// interesting half of either answer.
    fn leaf_polarity(&self, path: &str, is_dir: bool) -> Option<bool> {
        let segments = path_segments(path);
        if segments.is_empty() {
            return None;
        }
        self.last_match_at(&segments, is_dir)
    }

    /// Every **override-layer** negation (`!`) anchored *under* `prefix` (a `/`-separated
    /// directory path relative to the format root), or `None` when there is none.
    /// "Anchored under" means the rule's fixed leading path — its layer's anchor plus the
    /// rule's run of literal (non-glob) segments — has `prefix` as a prefix, and the rule
    /// reaches beneath it: a literal segment beyond the prefix, or a glob tail (`!dist/*.ts`
    /// is as inert under a pruned `dist` as `!dist/keep.ts`; a path equal to the prefix
    /// with no tail is the directory itself, not under it). Only a layer anchored strictly
    /// *above* `prefix` is read: a directory's own ignore files classify only what lies
    /// inside it, and a walk that prunes `prefix` never reads them.
    ///
    /// `.gitignore` layers are not consulted; among override-layer rules only anchored
    /// negations count. A floating `!keep.ts` (parsed with a leading `**`) targets any
    /// depth, so it is never "under" one directory; and `!dist/` re-includes the directory
    /// itself, which is not *under* it.
    ///
    /// tsv's discovery uses this to warn when a directory an override-layer `!` was trying to
    /// re-include *into* is pruned — by its build-output heuristic or by a rule — since
    /// that re-include is a silent no-op: git's parent-directory rule (matched in the
    /// `.gitignore` regime) blocks re-including a descendant of an excluded directory. The
    /// sanctioned escape is re-including the directory itself, which
    /// [`is_reincluded`](Self::is_reincluded) detects instead. The witness names the
    /// deepest file holding such a rule, whose rules are read last, so a line added there
    /// wins — and carries every such rule from every layer above the prefix, spelled
    /// relative to that file, because the escape's `/dir/*` line silences each one it
    /// does not re-spell after it.
    #[doc(hidden)]
    pub fn negation_under(&self, prefix: &str) -> Option<Negation> {
        let prefix_segs = split_segments(prefix);
        // every anchored re-include reaching under the prefix, with its layer's depth and
        // file, in read order: layers shallow to deep, then file order within one
        let mut found = Vec::new();
        for layer in &self.overrides {
            if layer.anchor.len() >= prefix_segs.len() {
                continue;
            }
            for rule in &layer.rules.rules {
                let Some((leading, tail)) = rule.negation_leading_path() else {
                    continue;
                };
                // the fixed path the negation is anchored to is `layer.anchor` followed
                // by `leading`; `prefix_segs` must be a prefix of it, with the rule
                // reaching *under* the prefix — a literal segment beyond it, or a glob tail
                let mut concrete = layer.anchor.iter().chain(&leading);
                let reaches_under = prefix_segs
                    .iter()
                    .all(|seg| concrete.next().is_some_and(|c| c.as_str() == *seg))
                    && (concrete.next().is_some() || tail != NegationTail::None);
                if reaches_under {
                    found.push((layer.anchor.len(), layer.source, leading, tail, rule));
                }
            }
        }
        // the deepest layer holding one names the file; every rule is re-spelled relative
        // to it by dropping the segments between its own file's directory and that one —
        // segments its leading path holds, since the prefix runs through both
        let &(anchor_depth, source, ..) = found.iter().max_by_key(|f| f.0)?;
        let rules = found
            .into_iter()
            .map(|(depth, _, leading, tail, rule)| {
                let skip = anchor_depth - depth;
                NegationRule {
                    leading: leading[skip..].to_vec(),
                    tail,
                    pattern: rule.spelling_from(skip),
                }
            })
            .collect();
        Some(Negation {
            anchor_depth,
            source,
            rules,
        })
    }

    /// The combined last-match polarity across every applicable layer at one
    /// `prefix` — each `.gitignore` layer (shallow→deep) then each override layer
    /// (shallow→deep), so an override layer wins over `.gitignore` and a deeper layer
    /// wins over a shallower one of its kind. `None` if no layer matches. This is
    /// the per-level primitive; it does *not* apply the ancestor prune
    /// ([`is_ignored`](Self::is_ignored) iterates prefixes,
    /// [`is_reincluded`](Self::is_reincluded) queries the leaf directly).
    fn last_match_at(&self, prefix: &[PathSeg<'_>], is_dir: bool) -> Option<bool> {
        last_match_layer(self.gitignore.iter().chain(&self.overrides), prefix, is_dir)
            .map(|(ignored, _)| ignored)
    }

    /// Where `path` is ignored, and which file's rule ignored it — the witness behind
    /// [`is_ignored`](Self::is_ignored), which is this with the witness dropped. The
    /// shallowest excluded prefix is the one reported: an excluded directory prunes
    /// everything under it (git's parent-directory rule), so no deeper rule is consulted.
    ///
    /// A diagnostic query, off the discovery hot path: tsv's discovery asks it of a path
    /// an argument NAMED, to say which directory put the path out of scope and which
    /// file's rule did.
    #[must_use]
    pub fn exclusion(&self, path: &str, kind: PathKind) -> Option<Exclusion> {
        first_exclusion(path, kind.is_dir(), |prefix, dir| {
            last_match_layer(self.gitignore.iter().chain(&self.overrides), prefix, dir)
        })
    }

    /// [`exclusion`](Self::exclusion) over the `.gitignore` layers alone — what excludes
    /// `path` once every override layer is set aside. An override rule at a prefix is the witness
    /// [`exclusion`](Self::exclusion) names there, so this is how a diagnostic learns a
    /// `.gitignore` rule stands behind it, at that depth or below (narrowing the override rule
    /// alone would leave the path excluded).
    #[doc(hidden)]
    pub fn gitignore_exclusion(&self, path: &str, kind: PathKind) -> Option<Exclusion> {
        first_exclusion(path, kind.is_dir(), |prefix, dir| {
            last_match_layer(self.gitignore.iter(), prefix, dir)
        })
    }

    /// [`exclusion`](Self::exclusion) over the override layers alone: where `path` would be
    /// ignored with every `.gitignore` layer set aside, and which `.formatignore` or
    /// `.prettierignore` rule ignored it. `Some` only where `exclusion` is — an override layer is
    /// read after every `.gitignore`, so an override rule excluding a prefix excludes it in the
    /// whole stack too — and the same answer wherever `exclusion`'s witness is an override layer.
    ///
    /// A diagnostic query, off the discovery hot path: tsv's discovery asks it of a path an
    /// argument NAMED, since an override rule excluding the path is the one to report even where a
    /// `.gitignore` excludes it first — re-including the path past the `.gitignore` would
    /// leave that rule standing.
    #[doc(hidden)]
    pub fn override_exclusion(&self, path: &str, kind: PathKind) -> Option<Exclusion> {
        first_exclusion(path, kind.is_dir(), |prefix, dir| {
            last_match_layer(self.overrides.iter(), prefix, dir)
        })
    }

    /// The file the override layer anchored at `anchor` (`/`-separated, `""` = the format root)
    /// was read from, or `None` when no override layer is pushed there. What lets a diagnostic
    /// name the file a directory actually uses: telling someone to create a
    /// `.formatignore` beside the `.prettierignore` a directory reads would shadow every
    /// rule in it.
    #[doc(hidden)]
    pub fn override_layer_source(&self, anchor: &str) -> Option<IgnoreSource> {
        let anchor = split_segments(anchor);
        self.overrides
            .iter()
            .rev()
            .find(|layer| {
                layer
                    .anchor
                    .iter()
                    .map(String::as_str)
                    .eq(anchor.iter().copied())
            })
            .map(|layer| layer.source)
    }
}

/// Whether a queried path is a directory — the one fact about a path the matcher cannot
/// read off its text, and the one trailing-`/` patterns (`build/`) turn on: a directory
/// pattern matches a directory, never a file of the same name.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum PathKind {
    /// Anything but a directory.
    File,
    /// A directory.
    Directory,
}

impl PathKind {
    /// [`PathKind::Directory`] when `is_dir`, else [`PathKind::File`] — for a caller
    /// holding the answer as a flag (a directory walk's entry type, a binding's argument).
    #[must_use]
    pub const fn from_is_dir(is_dir: bool) -> Self {
        if is_dir { Self::Directory } else { Self::File }
    }

    /// Whether this is [`PathKind::Directory`].
    #[must_use]
    pub const fn is_dir(self) -> bool {
        matches!(self, Self::Directory)
    }
}

/// The file a layer's rules were read from — what a diagnostic about an ignored path
/// names, and what decides how it is undone: a `.gitignore`'d path is re-included from an
/// override layer, which is read after every `.gitignore`, while an override layer's own
/// rule is the user's to narrow.
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum IgnoreSource {
    /// A `.gitignore` ([`IgnoreStack::push_gitignore`]).
    Gitignore,
    /// A `.formatignore` ([`IgnoreStack::push_formatignore`]).
    Formatignore,
    /// A `.prettierignore` ([`IgnoreStack::push_prettierignore`]).
    Prettierignore,
}

impl IgnoreSource {
    /// The file's name.
    #[must_use]
    pub const fn file_name(self) -> &'static str {
        match self {
            Self::Gitignore => ".gitignore",
            Self::Formatignore => ".formatignore",
            Self::Prettierignore => ".prettierignore",
        }
    }
}

/// Where [`IgnoreStack::exclusion`] found a path ignored. Both depths count the queried
/// path's segments as [`split_segments`] splits it.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct Exclusion {
    /// How many leading segments name the excluded path: all of them when a rule excluded
    /// the path itself, fewer when it excluded an ancestor directory.
    pub depth: usize,
    /// How many leading segments name the directory holding the excluding rule's file —
    /// always fewer than `depth`, since a directory's own ignore file never classifies
    /// that directory.
    pub anchor_depth: usize,
    /// The file the excluding rule was read from.
    pub source: IgnoreSource,
}

/// Where [`IgnoreStack::negation_under`] found negations written under a directory, and
/// what each was trying to reach — enough for a diagnostic to spell the lines that would.
#[doc(hidden)]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Negation {
    /// How many leading segments of the queried directory name the directory holding the
    /// file every rule here is spelled for — the deepest override file holding one, counted as
    /// [`split_segments`] splits the directory, and always fewer than its own segments,
    /// since only a layer anchored above it is read.
    pub anchor_depth: usize,
    /// That file: a `.formatignore` or `.prettierignore`, never a `.gitignore`.
    pub source: IgnoreSource,
    /// Every negation reaching under the directory, from every override layer above it, in
    /// read order (shallower files first, then file order) — each spelled relative to
    /// the file `anchor_depth` names. Never empty.
    pub rules: Vec<NegationRule>,
}

/// One rule of a [`Negation`], relative to the file the negation is spelled for.
#[doc(hidden)]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NegationRule {
    /// The rule's fixed leading path relative to that file's directory — its literal
    /// segments up to the first wildcard or `**`, each as it matches (unescaped). The
    /// queried directory is a prefix of it.
    pub leading: Vec<String>,
    /// How the rule continues past `leading`.
    pub tail: NegationTail,
    /// The pattern relative to that file's directory, spelled as the author wrote it
    /// (escapes and any trailing `/` kept; no leading `/` or `!`) — with `!/` ahead of it,
    /// the same rule anchored there.
    pub pattern: String,
}

/// What follows a [`NegationRule`]'s literal leading path.
#[doc(hidden)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NegationTail {
    /// Nothing: the path's last segment is the file or directory the rule names.
    None,
    /// One glob segment (`!dist/*.ts`): the rule names direct children of the path's
    /// last directory.
    Children,
    /// More than that, or a `**` (`!dist/**/x`, `!dist/*/x`): the rule reaches into
    /// directories below the path's last one.
    Descendants,
}

/// Whether one `/`-delimited component of a path is a meaningful segment. Empty
/// and `.` components are dropped, so `""`, `"."`, `"a//b"`, and `"./a"` all
/// normalize cleanly. The single definition of "segment" — every
/// path-to-segments conversion here filters on this, each keeping its own split
/// so the hot one ([`path_segments`]) is free to pre-size.
fn is_segment(component: &str) -> bool {
    !component.is_empty() && component != "."
}

/// A `/`-separated path's meaningful segments — the unit every [`IgnoreStack`] query
/// splits a path into, and the one [`Exclusion`]'s depths count in.
#[must_use]
pub fn split_segments(path: &str) -> Vec<&str> {
    path.split('/').filter(|s| is_segment(s)).collect()
}

/// [`split_segments`] into owned segments, for a layer's stored anchor.
fn split_path(path: &str) -> Vec<String> {
    split_segments(path).into_iter().map(String::from).collect()
}

/// [`split_segments`] into [`PathSeg`]s — the form every path query
/// (`is_ignored`, `is_ignored_leaf`, `is_reincluded`) feeds into the matcher.
///
/// Built in **one** pre-sized pass, unlike [`split_path`]: this runs per file
/// *and* per ancestor prefix during discovery, where neither collecting an
/// intermediate `Vec<&str>` first (`PathSeg` is wider, so `collect` cannot reuse
/// that allocation) nor the doubling growth chain is worth paying for. The
/// separator count is an upper bound — empty and `.` components only make it
/// slack.
fn path_segments(path: &str) -> Vec<PathSeg<'_>> {
    let mut segments = Vec::with_capacity(path.bytes().filter(|&b| b == b'/').count() + 1);
    segments.extend(path.split('/').filter(|s| is_segment(s)).map(PathSeg::new));
    segments
}

/// Walk `path`'s prefixes top-down to the first at which `polarity` reports a positive
/// match (`Some((true, _))`), returning its length in segments and the witness `polarity`
/// handed back there. A positive match at an ancestor prunes the subtree before a deeper
/// `!` is ever consulted — git's parent-directory rule; a negative match (re-included
/// here) and `None` (no rule here) fall through to let deeper levels decide. `polarity` is
/// the per-prefix last-match lookup — one file's rules (`IgnoreRules::last_match`) or a
/// run of layers ([`last_match_layer`], whose witness is the layer that spoke). Every
/// prefix shorter than the full path is an ancestor directory; `is_dir` marks only the
/// leaf. The shared spine of both `is_ignored` methods and of [`first_exclusion`].
fn first_excluded_prefix<T>(
    path: &str,
    is_dir: bool,
    polarity: impl Fn(&[PathSeg<'_>], bool) -> Option<(bool, T)>,
) -> Option<(usize, T)> {
    let segments = path_segments(path);
    let last = segments.len().checked_sub(1)?;
    (0..segments.len()).find_map(|k| match polarity(&segments[..=k], k < last || is_dir) {
        Some((true, witness)) => Some((k + 1, witness)),
        _ => None,
    })
}

/// [`first_excluded_prefix`] over a run of layers, as the [`Exclusion`] its witness layer
/// makes — the shared body of [`IgnoreStack::exclusion`] and
/// [`IgnoreStack::override_exclusion`], which differ only in the layers `polarity` reads.
fn first_exclusion<'a>(
    path: &str,
    is_dir: bool,
    polarity: impl Fn(&[PathSeg<'_>], bool) -> Option<(bool, &'a Layer)>,
) -> Option<Exclusion> {
    first_excluded_prefix(path, is_dir, polarity).map(|(depth, layer)| Exclusion {
        depth,
        anchor_depth: layer.anchor.len(),
        source: layer.source,
    })
}

/// The last of `layers` (pushed shallowest-first, each kind after the kind it overrides)
/// to speak at `prefix`: its polarity and the layer — the last layer to speak wins, read
/// as the first from the end, stopping at the deepest layer that matches (as
/// `IgnoreRules::last_match` reads its rules). The one reading of layer precedence:
/// [`IgnoreStack::last_match_at`], the per-level primitive discovery asks per entry,
/// is this over the whole stack with the layer dropped.
fn last_match_layer<'a>(
    layers: impl DoubleEndedIterator<Item = &'a Layer>,
    prefix: &[PathSeg<'_>],
    is_dir: bool,
) -> Option<(bool, &'a Layer)> {
    layers.rev().find_map(|layer| {
        let ignored = layer.rules.last_match(layer.relativize(prefix)?, is_dir)?;
        Some((ignored, layer))
    })
}

/// Parses one raw line into a rule, or `None` for blanks and comments.
fn parse_line(raw: &str) -> Option<Rule> {
    let mut s = strip_trailing_spaces(raw);
    // a blank line, or a comment (`#`) — an escaped `\#` starts with `\`, so it
    // is not caught here and falls through to a literal in the tokenizer
    if s.is_empty() || s.starts_with('#') {
        return None;
    }

    // leading `!` negates (an escaped `\!` starts with `\` and is left alone)
    let negated = s.starts_with('!');
    if negated {
        s = &s[1..];
    }
    // trailing `/` restricts to directories
    let dir_only = s.ends_with('/');
    if dir_only {
        s = &s[..s.len() - 1];
    }
    // a leading or interior `/` anchors the pattern to the ignore-file root; a
    // pattern with no interior separator floats and matches at any depth
    let leading_slash = s.starts_with('/');
    if leading_slash {
        s = &s[1..];
    }
    // gitignore(5): "a backslash at the end of a pattern is an invalid pattern
    // that never matches." A final *unescaped* backslash is an odd-length trailing
    // run of `\` (an even run is escaped pairs — `foo\\` is a valid literal `foo\`).
    // A never-matching rule contributes nothing to last-match-wins, so dropping it
    // is equivalent to keeping it, and simpler than threading an always-false flag
    // through the matcher. (Checked after the trailing-`/` strip, matching git: a
    // dir-only `foo\/` is likewise invalid.)
    if s.bytes().rev().take_while(|&b| b == b'\\').count() % 2 == 1 {
        return None;
    }
    let anchored = leading_slash || s.contains('/');

    // Split on `/`, escaped or not: `\/` is a slash git matches literally against
    // the path's own separator, and since no path component can hold a `/`, an
    // escaped one separates segments as a bare one does (`a\/b.ts` ignores `a/b.ts`)
    // — with one difference, so each segment remembers which kind ended it: git takes
    // `**`'s zero-directory shortcut only across a BARE slash, so a `**` followed by
    // `\/` must match at least one directory (`**\/f.ts` ignores `s/f.ts`, never
    // `f.ts`). Any other escape stays with its segment for `parse_segment`. An EMPTY
    // segment — a doubled `//`, or the `foo/` left by `foo//` once the structural
    // trailing `/` is stripped — is a pattern git can never match (no path has an
    // empty component), and a never-matching rule contributes nothing to
    // last-match-wins, so it is dropped like the trailing-backslash one above.
    //
    // A `/` inside a bracket class (`x[/a].ts`, `y[\/a].ts`) is a member of the class,
    // not a separator: git reads the class whole (its `strchr` still anchors the pattern
    // on that slash, as `anchored` does above), and a text `/` never reaches a class since
    // no segment holds one, so the member is inert and the class's other members match.
    // Splitting there instead cut the class open and dropped the whole rule. The class
    // is read as `glob::parse_class` reads it: a `]` first in it — `[]]`, `[!]]` — is a member,
    // so `class_members` counts what the class holds so far.
    let mut raw_segs: Vec<(String, bool)> = Vec::new(); // (text, ended by `\/`)
    let mut seg = String::new();
    let mut chars = s.chars().peekable();
    let mut class_members: Option<usize> = None;
    while let Some(c) = chars.next() {
        match c {
            '/' if class_members.is_none() => raw_segs.push((std::mem::take(&mut seg), false)),
            '\\' => match chars.next() {
                Some('/') if class_members.is_none() => {
                    raw_segs.push((std::mem::take(&mut seg), true));
                }
                Some(next) => {
                    seg.push('\\');
                    seg.push(next);
                    if let Some(members) = &mut class_members {
                        *members += 1;
                    }
                }
                // unreachable — a trailing unescaped backslash returned above
                None => seg.push('\\'),
            },
            '[' if class_members.is_none() => {
                seg.push('[');
                class_members = Some(0);
                // a leading `!` or `^` negates the class and is no member
                if let Some(&negation) = chars.peek()
                    && (negation == '!' || negation == '^')
                {
                    seg.push(negation);
                    chars.next();
                }
            }
            ']' if class_members.is_some_and(|members| members > 0) => {
                seg.push(']');
                class_members = None;
            }
            c => {
                seg.push(c);
                if let Some(members) = &mut class_members {
                    *members += 1;
                }
            }
        }
    }
    raw_segs.push((seg, false));
    if raw_segs.iter().any(|(text, _)| text.is_empty()) {
        return None;
    }
    let mut segs = Vec::with_capacity(raw_segs.len() + 1);
    for (text, escaped_separator) in &raw_segs {
        // `parse_segment` refuses a segment git's matcher aborts on (an unterminated
        // `[`), which makes the whole pattern never match — dropped for the same reason
        let parsed = parse_segment(text)?;
        if *escaped_separator && matches!(parsed, Seg::DoubleStar) {
            // one directory, then `**`'s zero or more: at least one
            segs.push(Seg::Glob(vec![Tok::Star]));
        }
        segs.push(parsed);
    }
    // a floating pattern is equivalent to one prefixed with `**/`
    if !anchored {
        segs.insert(0, Seg::DoubleStar);
    }
    // a negated rule keeps its author's spelling, segment by segment, for the diagnostic
    // that re-spells it anchored in another file
    let spelling = negated.then(|| {
        raw_segs
            .into_iter()
            .map(|(text, escaped_separator)| SpelledSeg {
                text: Box::from(text),
                escaped_separator,
            })
            .collect()
    });
    Some(Rule {
        segs,
        negated,
        spelling,
        dir_only,
    })
}

/// Strips trailing spaces from a line, keeping a space escaped with `\`.
/// Per gitignore(5), trailing spaces are ignored unless backslash-quoted. The
/// kept text is always a prefix of `line`, so this borrows rather than
/// allocates; `' '` and `\` are ASCII and never appear as UTF-8 continuation
/// bytes, so the byte scan is correct on any input.
fn strip_trailing_spaces(line: &str) -> &str {
    let bytes = line.as_bytes();
    let mut end = bytes.len();
    while end > 0 && bytes[end - 1] == b' ' {
        // an odd run of backslashes before this space escapes it — stop trimming
        let backslashes = bytes[..end - 1]
            .iter()
            .rev()
            .take_while(|&&b| b == b'\\')
            .count();
        if backslashes % 2 == 1 {
            break;
        }
        end -= 1;
    }
    &line[..end]
}

#[cfg(test)]
mod tests {
    use super::{
        Exclusion, IgnoreRules, IgnoreSource, IgnoreStack, NegationRule, NegationTail, PathKind,
    };

    /// Pushing an ancestor's layer after a descendant's breaks precedence; debug builds say so.
    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "pushed after a layer below it")]
    fn pushing_an_ancestor_layer_after_a_descendants_asserts() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("a", "!x.log\n");
        stack.push_gitignore("", "*.log\n");
    }

    /// A sibling's layer left on the stack never applies to the same path, so it passes.
    #[test]
    fn a_siblings_layer_on_the_stack_is_no_order_violation() {
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("a", "x\n");
        stack.push_formatignore("b", "y\n");
        assert!(stack.is_ignored("b/y", PathKind::File));
        assert!(!stack.is_ignored("b/x", PathKind::File));
    }

    fn ig(content: &str) -> IgnoreRules {
        IgnoreRules::parse(content)
    }

    fn excluded(depth: usize, anchor_depth: usize, source: IgnoreSource) -> Option<Exclusion> {
        Some(Exclusion {
            depth,
            anchor_depth,
            source,
        })
    }

    #[test]
    fn empty_rules_ignore_nothing() {
        let rules = ig("");
        assert!(rules.is_empty());
        assert!(!rules.is_ignored("anything.ts", false));
        assert!(!rules.is_ignored("a/b/c.ts", false));
    }

    #[test]
    fn comments_and_blanks_are_skipped() {
        let rules = ig("# a comment\n\n   \n# another\n");
        assert!(rules.is_empty());
    }

    #[test]
    fn floating_name_matches_at_any_depth() {
        let rules = ig("foo.ts\n");
        assert!(rules.is_ignored("foo.ts", false));
        assert!(rules.is_ignored("a/foo.ts", false));
        assert!(rules.is_ignored("a/b/foo.ts", false));
        assert!(!rules.is_ignored("bar.ts", false));
        assert!(!rules.is_ignored("a/foobar.ts", false));
    }

    #[test]
    fn anchored_pattern_only_matches_from_root() {
        let rules = ig("/foo.ts\n");
        assert!(rules.is_ignored("foo.ts", false));
        assert!(!rules.is_ignored("a/foo.ts", false));
    }

    #[test]
    fn interior_slash_anchors_to_root() {
        let rules = ig("src/gen.ts\n");
        assert!(rules.is_ignored("src/gen.ts", false));
        assert!(!rules.is_ignored("a/src/gen.ts", false));
        assert!(!rules.is_ignored("src/sub/gen.ts", false));
    }

    #[test]
    fn star_matches_within_a_segment_only() {
        let rules = ig("*.log\n");
        assert!(rules.is_ignored("debug.log", false));
        assert!(rules.is_ignored("a/b/debug.log", false));
        assert!(!rules.is_ignored("debug.log.txt", false));
        // `*` does not cross `/`
        let rules = ig("src/*.ts\n");
        assert!(rules.is_ignored("src/a.ts", false));
        assert!(!rules.is_ignored("src/sub/a.ts", false));
    }

    #[test]
    fn question_matches_one_char() {
        let rules = ig("file?.ts\n");
        assert!(rules.is_ignored("file1.ts", false));
        assert!(rules.is_ignored("fileA.ts", false));
        assert!(!rules.is_ignored("file.ts", false));
        assert!(!rules.is_ignored("file12.ts", false));
    }

    #[test]
    fn glob_is_code_point_granular() {
        // tsv matches glob metacharacters per Unicode *code point* (a Rust
        // `char`), not per byte (`git check-ignore`) or per UTF-16 code unit
        // (prettier's `ignore`). On non-ASCII these three oracles disagree, so
        // tsv can't match both — see the multibyte bullet in CLAUDE.md. Pinned
        // here so a refactor of the segment matcher can't silently flip the
        // granularity. (Verified out of band: `git check-ignore` does NOT ignore
        // `fileé.ts`; `ignore` v5.3.2 DOES but does NOT ignore `a😀.ts`.)
        let rules = ig("file?.ts\n");
        assert!(rules.is_ignored("fileX.ts", false));
        assert!(rules.is_ignored("fileé.ts", false)); // `é` is one code point; git would not
        assert!(!rules.is_ignored("fileéé.ts", false)); // two → one `?` matches one

        // an astral char is one code point (one `char`) but two UTF-16 units, so
        // a single `?` spans it for tsv but not for prettier's `ignore`
        let rules = ig("a?.ts\n");
        assert!(rules.is_ignored("a😀.ts", false));

        // char-class ranges compare by code point too: `é` (U+00E9) is outside a–z
        let rules = ig("x[a-z].ts\n");
        assert!(rules.is_ignored("xa.ts", false));
        assert!(!rules.is_ignored("xé.ts", false));

        // `*` backtracking advances by whole code points as well — the retry
        // after a mismatch resumes one *character* past the star, not one byte,
        // so a multibyte segment neither mis-aligns nor (since the matcher
        // indexes bytes) lands mid-character.
        let rules = ig("*.ts\n");
        assert!(rules.is_ignored("é.ts", false));
        let rules = ig("x*é.ts\n");
        assert!(rules.is_ignored("xéé.ts", false));
        assert!(!rules.is_ignored("xéc.ts", false));
    }

    #[test]
    fn char_class_and_range_and_negation() {
        let rules = ig("file[0-9].ts\n");
        assert!(rules.is_ignored("file3.ts", false));
        assert!(!rules.is_ignored("fileA.ts", false));

        let rules = ig("file[!0-9].ts\n");
        assert!(rules.is_ignored("fileA.ts", false));
        assert!(!rules.is_ignored("file3.ts", false));

        let rules = ig("file[abc].ts\n");
        assert!(rules.is_ignored("filea.ts", false));
        assert!(!rules.is_ignored("filed.ts", false));
    }

    #[test]
    fn char_class_caret_negation_and_literal_caret() {
        // `[^...]` negates exactly like `[!...]` — git's matcher accepts both.
        let rules = ig("file[^0-9].ts\n");
        assert!(rules.is_ignored("fileA.ts", false));
        assert!(!rules.is_ignored("file3.ts", false));

        // `^` is the negation marker only as the *first* class character;
        // elsewhere it is a literal member (so `[ab^]` matches `a`, `b`, or `^`).
        let rules = ig("lit[ab^].ts\n");
        assert!(rules.is_ignored("lit^.ts", false));
        assert!(rules.is_ignored("lita.ts", false));
        assert!(!rules.is_ignored("litc.ts", false));
    }

    #[test]
    fn dir_only_matches_directories_not_files() {
        let rules = ig("build/\n");
        // a directory named build, and everything under it
        assert!(rules.is_ignored("build", true));
        assert!(rules.is_ignored("build/out.js", false));
        assert!(rules.is_ignored("a/build/out.js", false));
        assert!(rules.is_ignored("a/build", true));
        // a *file* named build is not matched by a dir-only pattern
        assert!(!rules.is_ignored("build", false));
    }

    #[test]
    fn plain_name_matches_both_file_and_dir_contents() {
        let rules = ig("node_modules\n");
        assert!(rules.is_ignored("node_modules", true));
        assert!(rules.is_ignored("node_modules", false));
        assert!(rules.is_ignored("node_modules/pkg/index.js", false));
        assert!(rules.is_ignored("packages/x/node_modules/pkg/index.js", false));
    }

    #[test]
    fn leading_double_star_matches_any_depth() {
        let rules = ig("**/gen.ts\n");
        assert!(rules.is_ignored("gen.ts", false));
        assert!(rules.is_ignored("a/gen.ts", false));
        assert!(rules.is_ignored("a/b/gen.ts", false));
    }

    #[test]
    fn trailing_double_star_matches_contents() {
        let rules = ig("logs/**\n");
        assert!(rules.is_ignored("logs/today.log", false));
        assert!(rules.is_ignored("logs/sub/today.log", false));
        assert!(!rules.is_ignored("other/today.log", false));
        // git: a trailing `**` matches everything *inside* the anchor (>= 1
        // segment deep), never the anchor directory itself.
        assert!(!rules.is_ignored("logs", true));
    }

    #[test]
    fn trailing_double_star_does_not_match_anchor_dir() {
        // git: `foo/**` matches everything inside foo, never foo itself, so a
        // later `!foo/keep.ts` is allowed to re-include the file (the parent
        // dir is not excluded). The `foo/*` form behaves identically; only the
        // `**` anchor-match broke it. Pinned against `git check-ignore`.
        let rules = ig("foo/**\n");
        assert!(!rules.is_ignored("foo", true));
        assert!(rules.is_ignored("foo/keep.ts", false));
        assert!(rules.is_ignored("foo/sub", true));
        assert!(rules.is_ignored("foo/sub/file.ts", false));

        let rules = ig("foo/**\n!foo/keep.ts\n");
        assert!(!rules.is_ignored("foo/keep.ts", false));
        assert!(rules.is_ignored("foo/sub/file.ts", false));
    }

    #[test]
    fn trailing_double_star_dir_only_spares_direct_files() {
        // git: `foo/**/` (dir-only trailing) ignores only proper subdirectories
        // of foo, leaving files directly in foo formattable.
        let rules = ig("foo/**/\n");
        assert!(!rules.is_ignored("foo", true));
        assert!(!rules.is_ignored("foo/keep.ts", false));
        assert!(rules.is_ignored("foo/sub", true));
        assert!(rules.is_ignored("foo/sub/file.ts", false));
    }

    #[test]
    fn middle_double_star_spans_directories() {
        let rules = ig("a/**/b.ts\n");
        assert!(rules.is_ignored("a/b.ts", false));
        assert!(rules.is_ignored("a/x/b.ts", false));
        assert!(rules.is_ignored("a/x/y/b.ts", false));
        assert!(!rules.is_ignored("x/a/b.ts", false));
    }

    #[test]
    fn multiple_double_stars_span_independently() {
        // more than one `**` forces the matcher's general split-point search (the
        // trailing-anchor fast path only fires when the tail after a `**` has no
        // further `**`); each `**` independently matches zero or more segments.
        let rules = ig("a/**/b/**/c.ts\n");
        assert!(rules.is_ignored("a/b/c.ts", false)); // both `**` match zero
        assert!(rules.is_ignored("a/x/b/y/c.ts", false)); // each matches one
        assert!(rules.is_ignored("a/x/y/b/z/w/c.ts", false)); // each matches several
        assert!(!rules.is_ignored("a/b/x.ts", false)); // trailing `c.ts` absent
        assert!(!rules.is_ignored("a/x/c.ts", false)); // middle `b` absent
        assert!(!rules.is_ignored("x/a/b/c.ts", false)); // anchored `a` not at root
    }

    #[test]
    fn negation_reincludes() {
        let rules = ig("*.ts\n!keep.ts\n");
        assert!(rules.is_ignored("drop.ts", false));
        assert!(rules.is_ignored("a/drop.ts", false));
        assert!(!rules.is_ignored("keep.ts", false));
        assert!(!rules.is_ignored("a/keep.ts", false));
    }

    #[test]
    fn negation_order_is_last_match_wins() {
        // re-include then exclude again
        let rules = ig("*.ts\n!keep.ts\nkeep.ts\n");
        assert!(rules.is_ignored("keep.ts", false));
    }

    #[test]
    fn stack_is_reincluded_reports_explicit_negation_polarity() {
        // is_reincluded = "the last matching rule re-includes this exact path"
        // (per-path polarity, no ancestor prune) — distinct from `!is_ignored`:
        // a path no rule mentions is neither ignored nor re-included. This is the
        // heuristic-override primitive (#5): an override-layer `!build/` re-includes the dir.
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "*.ts\n!keep.ts\n");
        assert!(stack.is_reincluded("keep.ts", PathKind::File)); // `!keep.ts` wins
        assert!(!stack.is_reincluded("drop.ts", PathKind::File)); // excluded, not re-included
        assert!(!stack.is_reincluded("other.js", PathKind::File)); // no rule matches

        // a dir-only negation re-includes the directory, not a same-named file
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!build/\n");
        assert!(stack.is_reincluded("build", PathKind::Directory));
        assert!(!stack.is_reincluded("build", PathKind::File));
        assert!(!stack.is_reincluded("src", PathKind::Directory)); // no rule → not re-included

        // a plain exclude is ignored, not re-included
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "build/\n");
        assert!(!stack.is_reincluded("build", PathKind::Directory));
        assert!(stack.is_ignored("build", PathKind::Directory));
    }

    #[test]
    fn stack_negation_under_only_counts_anchored_negations() {
        // an anchored negation strictly under the dir → found (the silent-no-op
        // case the discovery warning targets: `!dist/keep.ts` cannot reach a
        // file under a pruned `dist`)
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!dist/keep.ts\n");
        let negation = stack.negation_under("dist").unwrap();
        assert_eq!(negation.anchor_depth, 0);
        assert_eq!(negation.source, IgnoreSource::Formatignore);
        assert_eq!(
            negation.rules,
            [NegationRule {
                leading: vec!["dist".into(), "keep.ts".into()],
                tail: NegationTail::None,
                pattern: "dist/keep.ts".into(),
            }]
        );
        assert_eq!(stack.negation_under("build"), None); // unrelated dir

        // a glob tail reaches under the directory as a literal one does — `!dist/*.ts`
        // is as inert under a pruned `dist` — so the literal run may end AT the
        // directory when the rule continues past it; the pattern keeps the author's
        // spelling (escapes, the trailing `/`) less any leading `/`, since it is only
        // ever re-spelled anchored. Every rule under the directory is reported, in file
        // order, with the tail graded by how far past its literal path it reaches
        let mut stack = IgnoreStack::new();
        stack.push_formatignore(
            "",
            "!dist/*.ts\n!/build/**/keep.ts\n!out/sub/\n!dist/a\\ b/*/x.ts\n!dist/deep/**\n",
        );
        let dist = stack.negation_under("dist").unwrap();
        assert_eq!(
            dist.rules
                .iter()
                .map(|r| (r.leading.join("/"), r.tail, r.pattern.as_str()))
                .collect::<Vec<_>>(),
            [
                ("dist".to_string(), NegationTail::Children, "dist/*.ts"),
                (
                    "dist/a b".to_string(),
                    NegationTail::Descendants,
                    "dist/a\\ b/*/x.ts"
                ),
                (
                    "dist/deep".to_string(),
                    NegationTail::Descendants,
                    "dist/deep/**"
                ),
            ]
        );
        let anchored = stack.negation_under("build").unwrap();
        assert_eq!(anchored.rules.len(), 1);
        assert_eq!(anchored.rules[0].leading, ["build"]);
        assert_eq!(anchored.rules[0].tail, NegationTail::Descendants);
        assert_eq!(anchored.rules[0].pattern, "build/**/keep.ts");
        let dir_only = stack.negation_under("out").unwrap();
        assert_eq!(dir_only.rules.len(), 1);
        assert_eq!(dir_only.rules[0].leading, ["out", "sub"]);
        assert_eq!(dir_only.rules[0].tail, NegationTail::None);
        assert_eq!(dir_only.rules[0].pattern, "out/sub/");
        assert_eq!(stack.negation_under("out/sub"), None); // the leaf itself, not under it

        // an escaped separator is kept as one, since `**\/` and `**/` are two rules
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!dist/**\\/x.ts\n");
        assert_eq!(
            stack.negation_under("dist").unwrap().rules[0].pattern,
            "dist/**\\/x.ts"
        );

        // re-including the directory ITSELF is not "under" it (that's the
        // sanctioned escape, detected by is_reincluded, not here)
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!dist/\n");
        assert_eq!(stack.negation_under("dist"), None);
        assert!(stack.is_reincluded("dist", PathKind::Directory)); // the escape works

        // a floating `!keep.ts` parses to a leading `**` — it targets any depth,
        // not a particular dir, so it must NOT trigger just because a keep.ts
        // happens to sit under dist
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!keep.ts\n");
        assert_eq!(stack.negation_under("dist"), None);

        // a non-negated exclude is not a re-include attempt
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "dist/keep.ts\n");
        assert_eq!(stack.negation_under("dist"), None);

        // no rules at all
        let stack = IgnoreStack::new();
        assert_eq!(stack.negation_under("dist"), None);

        // `.gitignore`-layer negations are never consulted — only override layers
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "!dist/keep.ts\n");
        assert_eq!(stack.negation_under("dist"), None);
    }

    #[test]
    fn stack_gitignore_exclusion_reads_the_gitignore_layers_alone() {
        // the `.gitignore` half of `exclusion`: what excludes the path once every override layer
        // is set aside — an override rule at the same prefix is the witness `exclusion` names,
        // and this is how a caller learns a `.gitignore` rule stands behind it
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "same/\nvendor/lib/\n");
        stack.push_formatignore("", "same/\nvendor/\nonly.ts\n");
        let same = stack
            .gitignore_exclusion("same", PathKind::Directory)
            .unwrap();
        assert_eq!(
            (same.depth, same.anchor_depth, same.source),
            (1, 0, IgnoreSource::Gitignore)
        );
        assert_eq!(
            stack.exclusion("same", PathKind::Directory).unwrap().source,
            IgnoreSource::Formatignore
        );
        // deeper than the override rule that excludes the path first
        let lib = stack
            .gitignore_exclusion("vendor/lib", PathKind::Directory)
            .unwrap();
        assert_eq!(lib.depth, 2);
        assert_eq!(
            stack
                .exclusion("vendor/lib", PathKind::Directory)
                .unwrap()
                .depth,
            1
        );
        // a path only an override rule excludes
        assert_eq!(stack.gitignore_exclusion("only.ts", PathKind::File), None);
        assert!(stack.is_ignored("only.ts", PathKind::File));
    }

    #[test]
    fn stack_negation_under_respects_layer_anchor() {
        // a deeper override layer's negation is anchored at its own directory: a
        // `!dist/keep.ts` in `foo/.prettierignore` is under `foo/dist`, not `dist`,
        // and the witness names that file
        let mut stack = IgnoreStack::new();
        stack.push_prettierignore("foo", "!dist/keep.ts\n");
        let negation = stack.negation_under("foo/dist").unwrap();
        assert_eq!(negation.anchor_depth, 1);
        assert_eq!(negation.source, IgnoreSource::Prettierignore);
        // the leading path is relative to the rule's own file
        assert_eq!(negation.rules[0].leading, ["dist", "keep.ts"]);
        assert_eq!(stack.negation_under("dist"), None);

        // a root negation with a nested anchored path sits under each strict
        // prefix dir it passes through, but never the leaf path itself (equal,
        // not strictly under) nor an unrelated sibling
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!src/gen/keep.ts\n");
        assert!(stack.negation_under("src/gen").is_some());
        assert!(stack.negation_under("src").is_some());
        assert_eq!(stack.negation_under("src/gen/keep.ts"), None);
        assert_eq!(stack.negation_under("src/other"), None);

        // a layer anchored AT the directory is not read: its rules classify only
        // what lies inside it, and a walk pruning the directory never reads the file
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("dist", "!sub/keep.ts\n");
        assert_eq!(stack.negation_under("dist"), None);
        assert!(stack.negation_under("dist/sub").is_some());
    }

    #[test]
    fn stack_negation_under_reports_the_deepest_layer_holding_one() {
        // the rules of the deepest layer are read last, so a directory re-include added
        // there wins — it is the witness, and a later-pushed layer holding no negation
        // under the directory does not displace it. Every layer's rules under the
        // directory ride along, re-spelled relative to that file: the root's
        // `!pkg/dist/a.ts` reads `dist/a.ts` in `pkg/.prettierignore`
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "!pkg/dist/a.ts\n!pkg/dist/sub/**\n");
        stack.push_prettierignore("pkg", "!dist/b.ts\n");
        stack.push_formatignore("lib", "!dist/c.ts\n");
        let negation = stack.negation_under("pkg/dist").unwrap();
        assert_eq!(
            (negation.anchor_depth, negation.source),
            (1, IgnoreSource::Prettierignore)
        );
        assert_eq!(
            negation
                .rules
                .iter()
                .map(|r| (r.leading.join("/"), r.pattern.as_str()))
                .collect::<Vec<_>>(),
            [
                ("dist/a.ts".to_string(), "dist/a.ts"),
                ("dist/sub".to_string(), "dist/sub/**"),
                ("dist/b.ts".to_string(), "dist/b.ts"),
            ]
        );
    }

    #[test]
    fn cannot_reinclude_under_excluded_dir() {
        // git: a negation cannot re-include a file whose parent dir is excluded
        let rules = ig("build/\n!build/keep.js\n");
        assert!(rules.is_ignored("build/keep.js", false));
    }

    #[test]
    fn reincluding_the_dir_itself_allows_descendants() {
        let rules = ig("build/\n!build/\n");
        // the directory is re-included, so a file under it is evaluated normally
        assert!(!rules.is_ignored("build/keep.js", false));
    }

    #[test]
    fn escaped_special_characters_are_literal() {
        // leading `#` escaped → a literal name starting with `#`
        let rules = ig("\\#notacomment.ts\n");
        assert!(rules.is_ignored("#notacomment.ts", false));

        // leading `!` escaped → literal, not a negation
        let rules = ig("\\!bang.ts\n");
        assert!(rules.is_ignored("!bang.ts", false));

        // escaped `*` → literal star, not a wildcard
        let rules = ig("a\\*b.ts\n");
        assert!(rules.is_ignored("a*b.ts", false));
        assert!(!rules.is_ignored("axb.ts", false));
    }

    #[test]
    fn trailing_backslash_is_an_invalid_pattern() {
        // gitignore(5): "a backslash at the end of a pattern is an invalid pattern
        // that never matches." A final unescaped backslash matches nothing — not
        // even a file literally ending in `\`. Pinned against `git check-ignore`.
        let rules = ig("bar\\\n");
        assert!(rules.is_empty()); // the lone invalid rule is dropped
        assert!(!rules.is_ignored("bar", false));
        assert!(!rules.is_ignored("bar\\", false));

        // a dir-only `foo\/` is invalid the same way: once the structural trailing
        // `/` is stripped, the pattern still ends in an unescaped backslash. git
        // agrees — it does not match the `foo` directory.
        let rules = ig("foo\\/\n");
        assert!(rules.is_empty());
        assert!(!rules.is_ignored("foo", true));

        // an *even* trailing run is escaped pairs, so `foo\\` is a valid pattern
        // for a literal `foo\` (and git matches it).
        let rules = ig("foo\\\\\n");
        assert!(!rules.is_empty());
        assert!(rules.is_ignored("foo\\", false));
        assert!(!rules.is_ignored("foo", false));
    }

    /// The parse-level rules `tests/git_oracle.rs` holds against git; pinned here
    /// too so a git-less run still grades them.
    #[test]
    fn bom_escaped_slash_empty_segment_and_open_class_parse_like_git() {
        // a leading BOM is skipped, so the FIRST rule still applies
        let rules = ig("\u{feff}first.ts\nsecond.ts\n");
        assert!(rules.is_ignored("first.ts", false));
        assert!(rules.is_ignored("second.ts", false));

        // `\/` is a separator: no path component can hold a slash
        let rules = ig("a\\/b.ts\n");
        assert!(rules.is_ignored("a/b.ts", false));
        assert!(!rules.is_ignored("a\\", true));

        // an empty segment never matches (`foo//` is `foo/` after the structural strip)
        assert!(ig("foo//\n").is_empty());
        assert!(ig("a//b\n").is_empty());

        // an unterminated class aborts the whole pattern, not a literal `[`
        assert!(ig("q[bc.ts\n").is_empty());
        assert!(!ig("q[bc.ts\n").is_ignored("q[bc.ts", false));

        // a range's low end is a member even when the range is empty
        let rules = ig("x[z-a].ts\n");
        assert!(rules.is_ignored("xz.ts", false));
        assert!(!rules.is_ignored("xa.ts", false));

        // a `/` inside a class — bare or escaped — is a member, not a separator: the
        // class's other members match, the pattern is anchored on the slash as git's
        // `strchr` anchors it, and a leading `]` or `!` still reads as it does elsewhere
        for (rule, hit, miss) in [
            ("x[/a].ts\n", "xa.ts", "sub/xa.ts"),
            ("y[\\/a].ts\n", "ya.ts", "yb.ts"),
            ("z[!/a].ts\n", "zb.ts", "za.ts"),
            ("w[]/a].ts\n", "w].ts", "wb.ts"),
            ("v[/a]/k.ts\n", "va/k.ts", "va/sub/k.ts"),
        ] {
            let rules = ig(rule);
            assert!(rules.is_ignored(hit, false), "{rule:?} should ignore {hit}");
            assert!(
                !rules.is_ignored(miss, false),
                "{rule:?} should not ignore {miss}"
            );
        }
        // an unterminated class holding a `/` is still one never-matching pattern
        assert!(ig("q[/bc.ts\n").is_empty());

        // a line ends at its first NUL, as a C string does for git; the `\r` ahead of
        // the line ending comes off first
        let rules = ig("a.ts\nb.ts\0junk.ts\nc.ts\0\r\n");
        assert!(rules.is_ignored("b.ts", false));
        assert!(!rules.is_ignored("b.ts\0junk.ts", false));
        assert!(!rules.is_ignored("junk.ts", false));
        assert!(rules.is_ignored("c.ts", false));
    }

    /// The class, star-run, escaped-`**` and trailing-`\r` rules `tests/git_oracle.rs`
    /// holds against git, pinned here too so a git-less run still grades them.
    #[test]
    fn class_escapes_star_runs_escaped_double_star_and_final_cr_parse_like_git() {
        // an escape resolves before its `-` is read: `[\a-c]` is the range a–c
        let rules = ig("x[\\a-c].ts\n");
        assert!(rules.is_ignored("xb.ts", false));
        assert!(!rules.is_ignored("x-.ts", false));
        // an escaped `-` is a member, not a range
        let rules = ig("x[a\\-c].ts\n");
        assert!(rules.is_ignored("x-.ts", false));
        assert!(!rules.is_ignored("xb.ts", false));
        // a range's high end may be escaped
        assert!(ig("x[a-\\c].ts\n").is_ignored("xb.ts", false));
        // a leading `]` is a member, and can open a range (`]`–`a` holds `^`, not `-`)
        let rules = ig("x[]-a].ts\n");
        assert!(rules.is_ignored("x^.ts", false));
        assert!(!rules.is_ignored("x-.ts", false));
        // an escaped high end that swallows the `]` leaves the class unterminated
        assert!(ig("x[[-\\].ts\n").is_empty());

        // a segment of three stars is a double star
        let rules = ig("a/***/b.ts\n");
        assert!(rules.is_ignored("a/b.ts", false));
        assert!(rules.is_ignored("a/x/y/b.ts", false));

        // `**`'s zero-directory shortcut is taken across a bare slash only
        let rules = ig("**\\/f.ts\n");
        assert!(!rules.is_ignored("f.ts", false));
        assert!(rules.is_ignored("s/f.ts", false));
        assert!(ig("**/f.ts\n").is_ignored("f.ts", false));

        // a bare `\r` ends the last line too
        assert!(ig("a.ts\nb.ts\r").is_ignored("b.ts", false));
    }

    #[test]
    fn crlf_line_endings_parse_like_lf() {
        // `parse` strips one trailing `\r` from each `\n`-split line, so a CRLF
        // ignore file behaves identically to an LF one — the trailing-`/` and
        // negation markers are detected on the `\r`-stripped line.
        let rules = ig("*.log\r\nbuild/\r\n!keep.log\r\n");
        assert!(rules.is_ignored("debug.log", false));
        assert!(rules.is_ignored("build/out.js", false));
        assert!(!rules.is_ignored("keep.log", false));
        assert!(!rules.is_ignored("src/app.ts", false));
    }

    #[test]
    fn trailing_spaces_are_trimmed_unless_escaped() {
        let rules = ig("foo.ts   \n");
        assert!(rules.is_ignored("foo.ts", false));

        // multibyte content before trimmed trailing spaces still slices on a char
        // boundary (the byte-scan trims only ASCII spaces, never a content byte)
        let rules = ig("café   \n");
        assert!(rules.is_ignored("café", false));

        // an escaped trailing space is part of the name
        let rules = ig("foo\\ \n");
        assert!(rules.is_ignored("foo ", false));
        assert!(!rules.is_ignored("foo", false));
    }

    #[test]
    fn realistic_prettierignore() {
        let rules = ig(
            "# generated\nnode_modules\ndist/\nbuild/\n*.min.js\n.svelte-kit/\ntests/fixtures/\n",
        );
        assert!(rules.is_ignored("dist/app.js", false));
        assert!(rules.is_ignored("src/vendor/jquery.min.js", false));
        assert!(rules.is_ignored("tests/fixtures/x/input.svelte", false));
        assert!(rules.is_ignored(".svelte-kit/generated/root.svelte", false));
        assert!(!rules.is_ignored("src/app.ts", false));
        assert!(!rules.is_ignored("src/main.js", false));
    }

    // --- IgnoreStack (hierarchical) ---
    //
    // The boolean expectations below are pinned against `git check-ignore` on
    // the same tree of nested `.gitignore` files (verified out of band).

    #[test]
    fn stack_single_root_layer_matches_ignore_rules() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n*.min.js\n!keep.min.js\n");
        assert!(stack.is_ignored("build/out.js", PathKind::File));
        assert!(stack.is_ignored("a/b.min.js", PathKind::File));
        assert!(!stack.is_ignored("keep.min.js", PathKind::File));
        assert!(!stack.is_ignored("src/app.ts", PathKind::File));
    }

    #[test]
    fn stack_empty_and_blank_layers_ignore_nothing() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "");
        stack.push_formatignore("", "# just a comment\n");
        assert!(!stack.is_ignored("a/x.ts", PathKind::File));
        assert!(stack.has_gitignore_layers()); // an empty `.gitignore` still sets the regime
    }

    /// The full hierarchical oracle tree:
    /// root `.gitignore`: `*.log`, `build/`, `!keep.log`, `/rootonly.ts`, `float.ts`
    /// `a/.gitignore`:    `!*.log`, `b/`
    /// `a/b/.gitignore`:  `!special.ts`
    fn oracle_stack() -> IgnoreStack {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "*.log\nbuild/\n!keep.log\n/rootonly.ts\nfloat.ts\n");
        stack.push_gitignore("a", "!*.log\nb/\n");
        stack.push_gitignore("a/b", "!special.ts\n");
        stack
    }

    #[test]
    fn stack_deeper_negation_reincludes() {
        let stack = oracle_stack();
        // root `*.log` ignores, but `a/.gitignore`'s `!*.log` re-includes deeper
        assert!(stack.is_ignored("debug.log", PathKind::File));
        assert!(!stack.is_ignored("a/debug.log", PathKind::File));
        assert!(!stack.is_ignored("a/keep.log", PathKind::File));
        // root `!keep.log` re-includes at the root
        assert!(!stack.is_ignored("keep.log", PathKind::File));
    }

    #[test]
    fn stack_root_anchored_vs_floating() {
        let stack = oracle_stack();
        // `/rootonly.ts` is anchored to the root only
        assert!(stack.is_ignored("rootonly.ts", PathKind::File));
        assert!(!stack.is_ignored("a/rootonly.ts", PathKind::File));
        // `float.ts` floats and matches at any depth
        assert!(stack.is_ignored("float.ts", PathKind::File));
        assert!(stack.is_ignored("a/float.ts", PathKind::File));
    }

    #[test]
    fn stack_parent_prune_blocks_deeper_negation_across_files() {
        let stack = oracle_stack();
        // `a/b/` is excluded by `a/.gitignore`'s `b/`, so `a/b/.gitignore`'s
        // `!special.ts` CANNOT re-include a file under it — git's parent rule,
        // spanning two separate ignore files.
        assert!(stack.is_ignored("a/b/x.ts", PathKind::File));
        assert!(stack.is_ignored("a/b/special.ts", PathKind::File));
        // a dir-only `build/` matches the directory at any depth
        assert!(stack.is_ignored("build/x.ts", PathKind::File));
        assert!(stack.is_ignored("packages/foo/build/y.ts", PathKind::File));
    }

    #[test]
    fn stack_deeper_anchor_matches_relative_to_its_directory() {
        let mut stack = IgnoreStack::new();
        // `gen.ts` interior-anchored inside `pkg/` matches `pkg/src/gen.ts`,
        // not a root `src/gen.ts`
        stack.push_gitignore("", "");
        stack.push_gitignore("pkg", "src/gen.ts\n");
        assert!(stack.is_ignored("pkg/src/gen.ts", PathKind::File));
        assert!(!stack.is_ignored("src/gen.ts", PathKind::File));
        assert!(!stack.is_ignored("pkg/sub/src/gen.ts", PathKind::File));
    }

    #[test]
    fn stack_override_layer_applies_after_gitignore() {
        // the override layer can re-include a gitignore'd directory wholesale…
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n");
        stack.push_formatignore("", "!build/\n");
        assert!(!stack.is_ignored("build/keep.ts", PathKind::File));

        // …but, like git, an override-layer `!build/keep.ts` can NOT re-include a file under
        // a still-excluded `build/` (only re-including the dir itself works)
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n");
        stack.push_formatignore("", "!build/keep.ts\n");
        assert!(stack.is_ignored("build/keep.ts", PathKind::File));

        // and the override layer can exclude something `.gitignore` allows
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "*.snap\n");
        assert!(stack.is_ignored("a/x.snap", PathKind::File));
        assert!(!stack.is_ignored("a/x.ts", PathKind::File));
    }

    #[test]
    fn stack_override_layer_overrides_a_deeper_gitignore() {
        // the override layer is applied after every `.gitignore`, so a repo-root override
        // `!` wins even over a deeper `.gitignore` re-exclusion
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n");
        stack.push_gitignore("a", "build/\n");
        stack.push_formatignore("", "!build/\n");
        assert!(!stack.is_ignored("a/build/x.ts", PathKind::File));
    }

    #[test]
    fn stack_override_layers_are_hierarchical() {
        // a deeper override layer overrides a shallower one (like `.gitignore`)
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "*.snap\n"); // root override layer ignores snaps everywhere
        stack.push_formatignore("a", "!*.snap\n"); // a/ override layer re-includes them under a/
        assert!(stack.is_ignored("x.snap", PathKind::File));
        assert!(stack.is_ignored("b/x.snap", PathKind::File));
        assert!(!stack.is_ignored("a/x.snap", PathKind::File)); // deeper override layer wins
        assert!(!stack.is_ignored("a/deep/x.snap", PathKind::File));

        // an override layer's patterns are anchored at its own directory
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("pkg", "gen.ts\n"); // floating, but only within pkg/
        assert!(stack.is_ignored("pkg/gen.ts", PathKind::File));
        assert!(stack.is_ignored("pkg/sub/gen.ts", PathKind::File));
        assert!(!stack.is_ignored("gen.ts", PathKind::File)); // outside the pkg anchor
    }

    #[test]
    fn stack_pop_override_unwinds_a_layer() {
        let mut stack = IgnoreStack::new();
        stack.push_formatignore("", "*.snap\n");
        stack.push_formatignore("a", "!*.snap\n");
        assert!(!stack.is_ignored("a/x.snap", PathKind::File));
        // leaving `a/` drops its re-include, so the root rule applies again
        stack.pop_override();
        assert!(stack.is_ignored("a/x.snap", PathKind::File));
    }

    #[test]
    fn stack_pop_gitignore_unwinds_a_layer() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "*.log\n");
        stack.push_gitignore("a", "!*.log\n");
        assert!(!stack.is_ignored("a/x.log", PathKind::File));
        // leaving `a/` drops its negation, so the root rule applies again
        stack.pop_gitignore();
        assert!(stack.is_ignored("a/x.log", PathKind::File));
    }

    #[test]
    fn stack_directory_query_for_pruning() {
        // discovery asks `is_ignored(dir, true)` to prune a whole subtree
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\nnode_modules\n");
        assert!(stack.is_ignored("build", PathKind::Directory));
        assert!(stack.is_ignored("a/node_modules", PathKind::Directory));
        assert!(!stack.is_ignored("src", PathKind::Directory));
    }

    #[test]
    fn stack_is_ignored_leaf_skips_the_ancestor_prune() {
        // is_ignored_leaf reports only the leaf path's own last-match — it
        // diverges from is_ignored exactly where an *ancestor* directory is what
        // excludes the path. Discovery relies on the two being equivalent *when
        // ancestors are known clean* (it prunes ignored dirs before descending and
        // gates the root with full is_ignored), so this pins the difference.
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n");
        // the excluded dir itself: both agree (a rule matches the leaf)
        assert!(stack.is_ignored("build", PathKind::Directory));
        assert!(stack.is_ignored_leaf("build", PathKind::Directory));
        // a file UNDER it: is_ignored prunes via the `build` ancestor; the
        // leaf-only query does not (no rule matches `build/app.ts` as a file)
        assert!(stack.is_ignored("build/app.ts", PathKind::File));
        assert!(!stack.is_ignored_leaf("build/app.ts", PathKind::File));
        // a deeper subdir under it: same divergence, two levels down
        assert!(stack.is_ignored("build/sub", PathKind::Directory));
        assert!(!stack.is_ignored_leaf("build/sub", PathKind::Directory));

        // a leaf a rule matches directly: both agree at any depth
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "*.log\n");
        assert!(stack.is_ignored("a/b/x.log", PathKind::File));
        assert!(stack.is_ignored_leaf("a/b/x.log", PathKind::File));
        assert!(!stack.is_ignored_leaf("a/b/x.ts", PathKind::File));
    }

    #[test]
    fn stack_exclusion_names_the_shallowest_excluded_prefix_and_its_file() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "build/\n*.log\n");
        stack.push_gitignore("sub", "deep/\n");
        stack.push_formatignore("", "gen/\nbuild/keep/\n");
        stack.push_prettierignore("pkg", "out/\n");
        // an excluded ancestor: the shallowest excluded prefix, however deep the path runs
        assert_eq!(
            stack.exclusion("build/sub/a.ts", PathKind::File),
            excluded(1, 0, IgnoreSource::Gitignore)
        );
        // a rule under an excluded directory is never the one reported
        assert_eq!(
            stack.exclusion("build/keep/a.ts", PathKind::File),
            excluded(1, 0, IgnoreSource::Gitignore)
        );
        // the path itself, at any depth
        assert_eq!(
            stack.exclusion("build", PathKind::Directory),
            excluded(1, 0, IgnoreSource::Gitignore)
        );
        assert_eq!(
            stack.exclusion("a/b/x.log", PathKind::File),
            excluded(3, 0, IgnoreSource::Gitignore)
        );
        // a nested layer's rule, with the directory holding its file
        assert_eq!(
            stack.exclusion("sub/deep/a.ts", PathKind::File),
            excluded(2, 1, IgnoreSource::Gitignore)
        );
        // an override layer's rule, naming which of the two files it was read from
        assert_eq!(
            stack.exclusion("gen/sub", PathKind::Directory),
            excluded(1, 0, IgnoreSource::Formatignore)
        );
        assert_eq!(
            stack.exclusion("pkg/out/a.ts", PathKind::File),
            excluded(2, 1, IgnoreSource::Prettierignore)
        );
        // nothing excludes it — and `is_ignored` is this with the witness dropped
        assert_eq!(stack.exclusion("src/a.ts", PathKind::File), None);
        assert!(!stack.is_ignored("src/a.ts", PathKind::File));
        assert_eq!(stack.exclusion("", PathKind::Directory), None);

        // an override negation re-including a `.gitignore`'d directory: the last layer to speak
        let mut reincluded = IgnoreStack::new();
        reincluded.push_gitignore("", "build/\n");
        reincluded.push_formatignore("", "!build/\n");
        assert_eq!(reincluded.exclusion("build/sub", PathKind::Directory), None);
        // …and an override rule over a `.gitignore` negation
        let mut overridden = IgnoreStack::new();
        overridden.push_gitignore("", "!keep.ts\n");
        overridden.push_prettierignore("", "keep.ts\n");
        assert_eq!(
            overridden.exclusion("keep.ts", PathKind::File),
            excluded(1, 0, IgnoreSource::Prettierignore)
        );
    }

    #[test]
    fn stack_override_exclusion_sets_the_gitignore_layers_aside() {
        let mut stack = IgnoreStack::new();
        stack.push_gitignore("", "vendor/\n");
        stack.push_formatignore("", "vendor/x.ts\n");
        stack.push_prettierignore("pkg", "out/*.ts\n");
        // the whole stack's witness is the `.gitignore`'d directory above the file…
        assert_eq!(
            stack.exclusion("vendor/x.ts", PathKind::File),
            excluded(1, 0, IgnoreSource::Gitignore)
        );
        // …while the override layers alone exclude the file itself
        assert_eq!(
            stack.override_exclusion("vendor/x.ts", PathKind::File),
            excluded(2, 0, IgnoreSource::Formatignore)
        );
        // a path only the `.gitignore` excludes
        assert_eq!(
            stack.override_exclusion("vendor/y.ts", PathKind::File),
            None
        );
        // wherever the whole stack's witness is an override layer, the answers agree
        assert_eq!(
            stack.override_exclusion("pkg/out/a.ts", PathKind::File),
            excluded(3, 1, IgnoreSource::Prettierignore)
        );
        assert_eq!(
            stack.override_exclusion("pkg/out/a.ts", PathKind::File),
            stack.exclusion("pkg/out/a.ts", PathKind::File)
        );
        // an override negation re-including a `.gitignore`'d directory excludes nothing either way
        let mut reincluded = IgnoreStack::new();
        reincluded.push_gitignore("", "build/\n");
        reincluded.push_formatignore("", "!build/\n");
        assert_eq!(
            reincluded.override_exclusion("build/a.ts", PathKind::File),
            None
        );
        assert_eq!(reincluded.exclusion("build/a.ts", PathKind::File), None);
    }

    #[test]
    fn stack_override_layer_source_names_the_file_a_directory_reads() {
        let mut stack = IgnoreStack::new();
        assert_eq!(stack.override_layer_source(""), None);
        // a `.gitignore` is not an override layer
        stack.push_gitignore("", "a\n");
        assert_eq!(stack.override_layer_source(""), None);
        stack.push_prettierignore("", "b\n");
        stack.push_formatignore("src", "c\n");
        assert_eq!(
            stack.override_layer_source(""),
            Some(IgnoreSource::Prettierignore)
        );
        assert_eq!(
            stack.override_layer_source("src"),
            Some(IgnoreSource::Formatignore)
        );
        // anchors compare by segment, not by spelling
        assert_eq!(
            stack.override_layer_source("./src/"),
            Some(IgnoreSource::Formatignore)
        );
        assert_eq!(stack.override_layer_source("lib"), None);
        stack.pop_override();
        assert_eq!(stack.override_layer_source("src"), None);
    }
}