tsv_ignore 0.8.0

//! Glob matching for a single ignore pattern, segment by segment.
//!
//! A pattern is parsed into a list of `Seg`ments split on `/`. A `**` segment
//! matches zero or more path segments; every other segment is a list of `Tok`s
//! that match within one path segment (never crossing `/`, which is why `*` and
//! character classes don't need to special-case the separator — segments are
//! already split). This mirrors the gitignore(5) pattern grammar.

/// One segment of a pattern.
#[derive(Debug, Clone)]
pub(crate) enum Seg {
    /// A `**` segment (or any longer run of stars) — matches zero or more path
    /// segments.
    DoubleStar,
    /// A normal segment, matched against one path segment via its tokens.
    Glob(Vec<Tok>),
}

/// A token within a single (non-`**`) segment.
#[derive(Debug, Clone)]
pub(crate) enum Tok {
    /// A literal character (escapes are resolved into this at parse time).
    Lit(char),
    /// `*` — matches zero or more characters within the segment.
    Star,
    /// `?` — matches exactly one character within the segment.
    Question,
    /// `[...]` — matches one character from (or not from) the set.
    Class {
        negated: bool,
        items: Vec<ClassItem>,
    },
}

#[derive(Debug, Clone)]
pub(crate) enum ClassItem {
    Ch(char),
    Range(char, char),
}

/// A path segment, classified once per query as all-ASCII or not.
///
/// `match_segments` runs the same path against many rules across many ancestor
/// prefixes, so the inner glob match wants O(1) indexed character access. For an
/// ASCII segment — every segment of essentially every real path — the segment's
/// own bytes already *are* that array, so the flag buys the whole amortization
/// with no collection at all: one `is_ascii` word-scan per segment instead of
/// collecting a `Vec<char>` (a heap allocation, plus its `realloc` growth
/// chain, per segment per query). `text` also powers the cheap `&str` anchor
/// comparison in `Layer::relativize`.
#[derive(Debug)]
pub(crate) struct PathSeg<'a> {
    pub(crate) text: &'a str,
    /// Whether `text` is wholly ASCII, so a byte index is a character index.
    ascii: bool,
}

impl<'a> PathSeg<'a> {
    pub(crate) fn new(text: &'a str) -> Self {
        Self {
            text,
            ascii: text.is_ascii(),
        }
    }
}

impl Seg {
    /// The exact string this segment matches, or `None` if it carries any
    /// wildcard (`*`, `?`, `[...]`) or is a `**` segment. Used to resolve a
    /// rule's fixed leading path — the run of literal directory names before any
    /// glob — for the heuristic-shadow diagnostic (`IgnoreStack::negation_under`).
    pub(crate) fn literal(&self) -> Option<String> {
        match self {
            Seg::DoubleStar => None,
            Seg::Glob(toks) => toks
                .iter()
                .map(|t| match t {
                    Tok::Lit(c) => Some(*c),
                    Tok::Star | Tok::Question | Tok::Class { .. } => None,
                })
                .collect(),
        }
    }
}

/// Parses one pattern segment into its matcher form, or `None` for a segment git's
/// matcher aborts on — an unterminated `[`, which `wildmatch` answers with
/// `WM_ABORT_ALL`, so the whole pattern matches nothing (not even a literal `[`).
pub(crate) fn parse_segment(s: &str) -> Option<Seg> {
    // `wildmatch` consumes a whole run of stars before it tests what bounds it, so a
    // segment that is nothing but stars — `***` included — is a double star
    if s.len() >= 2 && s.bytes().all(|b| b == b'*') {
        return Some(Seg::DoubleStar);
    }
    let chars: Vec<char> = s.chars().collect();
    let mut toks = Vec::new();
    let mut i = 0;
    while i < chars.len() {
        match chars[i] {
            '\\' => {
                // backslash escapes the next char into a literal
                if i + 1 < chars.len() {
                    toks.push(Tok::Lit(chars[i + 1]));
                    i += 2;
                } else {
                    toks.push(Tok::Lit('\\'));
                    i += 1;
                }
            }
            '*' => {
                // collapse a run of `*` — inside a segment `**` is just `*`
                while i < chars.len() && chars[i] == '*' {
                    i += 1;
                }
                toks.push(Tok::Star);
            }
            '?' => {
                toks.push(Tok::Question);
                i += 1;
            }
            '[' => {
                let (class, next) = parse_class(&chars, i)?;
                toks.push(class);
                i = next;
            }
            c => {
                toks.push(Tok::Lit(c));
                i += 1;
            }
        }
    }
    Some(Seg::Glob(toks))
}

/// Parses a `[...]` class starting at `open` (where `chars[open] == '['`).
/// Returns the class token and the index just past the closing `]`, or `None`
/// if the class is unterminated.
///
/// A transcription of git's `wildmatch` class loop, whose reading order decides
/// every edge. Each element is a member the moment it is read: an escape resolves
/// first (`[\a-c]` is the range `a`–`c`, not `a`, `-`, `c`), a `]` in the first
/// position is a literal rather than the terminator, and a range's low end has
/// already matched as a plain member by the time its `-` is read (so the empty
/// range `[z-a]` still matches `z`). A `-` opens a range only when an element
/// precedes it and the next character is not `]`; the element a range consumed
/// cannot open another (`[a-c-e]` is `a`–`c`, `-`, `e`), and the high end may be
/// escaped (`[a-\]]`).
///
/// One arm of that loop is deliberately absent: git's POSIX bracket expression
/// (`[[:alpha:]]`), which `wildmatch` reads as a named class where this reads `[`,
/// `:`, `a`, … as plain members. prettier's `ignore` doesn't implement it either, so
/// tsv tracks prettier there — a listed known edge (the crate's `CLAUDE.md`), which
/// is why "every edge" above is the reading order's, not the grammar's.
fn parse_class(chars: &[char], open: usize) -> Option<(Tok, usize)> {
    let mut i = open + 1;
    let mut negated = false;
    if i < chars.len() && (chars[i] == '!' || chars[i] == '^') {
        negated = true;
        i += 1;
    }
    let first = i;
    let mut items = Vec::new();
    // `wildmatch`'s `prev_ch`: the element a following `-` ranges from, `None` at the
    // class start and once a range has consumed it
    let mut prev: Option<char> = None;
    loop {
        let c = *chars.get(i)?;
        // a `]` right after `[` (or `[!`) is a literal member, not the terminator
        if c == ']' && i > first {
            return Some((Tok::Class { negated, items }, i + 1));
        }
        if c == '\\' {
            let escaped = *chars.get(i + 1)?;
            items.push(ClassItem::Ch(escaped));
            prev = Some(escaped);
            i += 2;
        } else if c == '-'
            && let Some(low) = prev
            && let Some(&next) = chars.get(i + 1)
            && next != ']'
        {
            let (high, width) = if next == '\\' {
                (*chars.get(i + 2)?, 3)
            } else {
                (next, 2)
            };
            items.push(ClassItem::Range(low, high));
            prev = None;
            i += width;
        } else {
            items.push(ClassItem::Ch(c));
            prev = Some(c);
            i += 1;
        }
    }
}

fn class_matches(negated: bool, items: &[ClassItem], c: char) -> bool {
    let hit = items.iter().any(|it| match it {
        ClassItem::Ch(x) => *x == c,
        ClassItem::Range(a, b) => *a <= c && c <= *b,
    });
    hit != negated
}

/// The `char` at byte offset `i` of a **non-ASCII** segment (`i` must be a char
/// boundary), paired with its UTF-8 width. Only this path decodes UTF-8; an
/// ASCII segment reads its byte inline in [`glob_seg_match`], which keeps that
/// loop indexing a hoisted byte slice — the shape the win depends on, since it
/// is what lets the bounds check and the stride fold away.
fn char_at(s: &str, i: usize) -> (char, usize) {
    // `i` is a char boundary, so this always yields; the fallback is unreachable
    // and, being a replacement char, could only fail to match anyway.
    let c = s[i..].chars().next().unwrap_or(char::REPLACEMENT_CHARACTER);
    (c, c.len_utf8())
}

/// Matches a pattern's segments against a path's segments, with `**` consuming
/// zero or more path segments.
pub(crate) fn match_segments(pat: &[Seg], path: &[PathSeg<'_>]) -> bool {
    match pat.split_first() {
        None => path.is_empty(),
        Some((Seg::DoubleStar, rest)) => {
            // `**` matches any number of leading path segments, then `rest` must
            // match the remainder. When `rest` carries no further `**` it has a
            // fixed segment count and can only align with the path's *tail*, so
            // jump straight there instead of trying every split point — the
            // floating `**/name` case (every plain pattern parses to a leading
            // `**`) was O(depth) match attempts against a deep path.
            if rest.iter().any(|s| matches!(s, Seg::DoubleStar)) {
                // another `**` ahead: every split point of every `**` is a candidate,
                // which a recursive search tries exponentially often — answer it in
                // one bounded pass instead
                match_reachable(pat, path)
            } else if rest.is_empty() {
                // a *trailing* `**` matches everything inside the anchor (≥ 1
                // segment), never the anchor dir itself — so a later `!foo/keep.ts`
                // can re-include the file (git's rule).
                !path.is_empty()
            } else {
                // fixed-length, `**`-free tail: it must match exactly the last
                // `rest.len()` segments (an interior `**` still consumed zero here,
                // so `a/**/b` keeps matching `a/b`).
                rest.len() <= path.len() && match_segments(rest, &path[path.len() - rest.len()..])
            }
        }
        Some((Seg::Glob(toks), rest)) => match path.split_first() {
            Some((head, tail)) if glob_seg_match(toks, head) => match_segments(rest, tail),
            _ => false,
        },
    }
}

/// [`match_segments`] for a pattern holding several `**`, as forward reachability:
/// after `pat[..i]`, which path prefixes `path[..j]` can it have consumed? A glob
/// segment advances each reachable `j` by one where it matches `path[j]`; a `**`
/// reaches every `j` at or past the earliest reachable one (strictly past it for a
/// *trailing* `**`, which matches at least one segment). The pattern matches when the
/// whole path is reachable after its last segment.
///
/// O(pattern × path) segment matches, where trying every split point of every `**`
/// recursively is exponential in the `**` count — a `.gitignore` line like
/// `**/a/**/a/…/b/` against a deep path, once per ancestor prefix discovery walks,
/// would otherwise hang the walk. Same answers, by the exhaustive differential in this
/// module's tests.
fn match_reachable(pat: &[Seg], path: &[PathSeg<'_>]) -> bool {
    // `cur[j]`: the segments consumed so far can match exactly `path[..j]`
    let mut cur = vec![false; path.len() + 1];
    let mut next = vec![false; path.len() + 1];
    cur[0] = true;
    for (i, seg) in pat.iter().enumerate() {
        next.fill(false);
        match seg {
            Seg::DoubleStar => {
                let at_least = usize::from(i + 1 == pat.len());
                if let Some(earliest) = cur.iter().position(|&r| r) {
                    for r in next.iter_mut().skip(earliest + at_least) {
                        *r = true;
                    }
                }
            }
            Seg::Glob(toks) => {
                for (j, seg) in path.iter().enumerate() {
                    if cur[j] && glob_seg_match(toks, seg) {
                        next[j + 1] = true;
                    }
                }
            }
        }
        std::mem::swap(&mut cur, &mut next);
        if !cur.contains(&true) {
            return false;
        }
    }
    cur[path.len()]
}

/// Matches one path segment against a segment's tokens. Classic two-pointer
/// glob match with single-star backtracking; segments are short so this is
/// cheap.
///
/// Both cursors index *bytes*, but every advance steps one whole code point, so
/// `?`, `*` and `[...]` stay code-point granular — the granularity
/// `glob_is_code_point_granular` pins. `si` is therefore always on a char
/// boundary. On an ASCII segment (the universal case) the character *is* the
/// byte and the step is a constant 1, so a read costs exactly what indexing a
/// pre-collected `Vec<char>` did; `seg.ascii` is loop-invariant, so the decode
/// branch unswitches rather than running per character.
fn glob_seg_match(toks: &[Tok], seg: &PathSeg<'_>) -> bool {
    #[cfg(test)]
    tests::GLOB_SEG_MATCHES.with(|n| n.set(n.get() + 1));
    let bytes = seg.text.as_bytes();
    let mut ti = 0;
    let mut si = 0;
    // (token index after the last `*`, byte offset where that `*` started)
    let mut star: Option<(usize, usize)> = None;
    while si < bytes.len() {
        if ti < toks.len() {
            let (c, width) = if seg.ascii {
                (char::from(bytes[si]), 1)
            } else {
                char_at(seg.text, si)
            };
            let matched = match &toks[ti] {
                Tok::Star => {
                    star = Some((ti + 1, si));
                    ti += 1;
                    continue;
                }
                Tok::Question => true,
                Tok::Lit(lit) => *lit == c,
                Tok::Class { negated, items } => class_matches(*negated, items, c),
            };
            if matched {
                ti += 1;
                si += width;
                continue;
            }
        }
        // mismatch (or tokens exhausted) — backtrack to the last `*` and let it
        // swallow one more character
        if let Some((sti, ssi)) = star {
            ti = sti;
            // `ssi` was recorded inside the loop, so it is a valid char boundary
            // below the segment's length — advancing by that char's width keeps
            // it one.
            let width = if seg.ascii {
                1
            } else {
                char_at(seg.text, ssi).1
            };
            si = ssi + width;
            star = Some((sti, si));
        } else {
            return false;
        }
    }
    // trailing `*`s can match the empty remainder
    while ti < toks.len() && matches!(toks[ti], Tok::Star) {
        ti += 1;
    }
    ti == toks.len()
}

#[cfg(test)]
mod tests {
    use super::{PathSeg, Seg, glob_seg_match, match_segments, parse_segment};
    use std::cell::Cell;

    thread_local! {
        /// How many single-segment glob matches this thread has run — the matcher's
        /// unit of work, counted so a complexity bound is graded without a clock.
        pub(super) static GLOB_SEG_MATCHES: Cell<usize> = const { Cell::new(0) };
    }

    /// The glob-segment matches `f` runs.
    fn count_matches(f: impl FnOnce() -> bool) -> (bool, usize) {
        let before = GLOB_SEG_MATCHES.with(Cell::get);
        let result = f();
        (result, GLOB_SEG_MATCHES.with(Cell::get) - before)
    }

    /// The plain recursive matcher: every split point of every `**` tried in turn.
    /// Exponential in the `**` count, so only the reference the reachability pass is
    /// graded against.
    fn match_segments_reference(pat: &[Seg], path: &[PathSeg<'_>]) -> bool {
        match pat.split_first() {
            None => path.is_empty(),
            Some((Seg::DoubleStar, rest)) => {
                if rest.iter().any(|s| matches!(s, Seg::DoubleStar)) {
                    (0..=path.len()).any(|i| match_segments_reference(rest, &path[i..]))
                } else if rest.is_empty() {
                    !path.is_empty()
                } else {
                    rest.len() <= path.len()
                        && match_segments_reference(rest, &path[path.len() - rest.len()..])
                }
            }
            Some((Seg::Glob(toks), rest)) => match path.split_first() {
                Some((head, tail)) if glob_seg_match(toks, head) => {
                    match_segments_reference(rest, tail)
                }
                _ => false,
            },
        }
    }

    fn segs(pattern: &[&str]) -> Vec<Seg> {
        pattern
            .iter()
            .map(|s| parse_segment(s).expect("a valid segment"))
            .collect()
    }

    /// Every sequence of `len` items drawn from `alphabet`, for each `len` up to `max`.
    fn sequences<'a>(alphabet: &[&'a str], max: usize) -> Vec<Vec<&'a str>> {
        let mut all = vec![Vec::new()];
        let mut level = vec![Vec::new()];
        for _ in 0..max {
            level = level
                .iter()
                .flat_map(|prefix: &Vec<&str>| {
                    alphabet.iter().map(move |item| {
                        let mut seq = prefix.clone();
                        seq.push(*item);
                        seq
                    })
                })
                .collect();
            all.extend(level.iter().cloned());
        }
        all
    }

    #[test]
    fn reachability_agrees_with_the_recursive_reference_exhaustively() {
        // every pattern of up to six segments over `**`, two literals and `*`, against
        // every path of up to six segments over the literals: each `**` placement
        // (leading, interior, trailing, adjacent pairs) meets every alignment
        let patterns = sequences(&["**", "a", "b", "*"], 6);
        let paths = sequences(&["a", "b"], 6);
        let mut multi = 0;
        for pattern in &patterns {
            let pat = segs(pattern);
            if pat.iter().filter(|s| matches!(s, Seg::DoubleStar)).count() >= 2 {
                multi += 1;
            }
            for path in &paths {
                let path: Vec<PathSeg<'_>> = path.iter().map(|s| PathSeg::new(s)).collect();
                assert_eq!(
                    match_segments(&pat, &path),
                    match_segments_reference(&pat, &path),
                    "pattern {pattern:?} against {path:?}",
                );
            }
        }
        // the multi-`**` branch is what changed, so the domain must reach it
        assert!(multi > 1000, "only {multi} multi-`**` patterns");
    }

    #[test]
    fn many_double_stars_match_in_bounded_work() {
        // `**/a/` six times then a `b` that never matches: the recursive search tries
        // every split point of every `**`; reachability runs at most one glob match
        // per pattern segment per path segment
        let mut pattern = ["**", "a"].repeat(6);
        pattern.push("b");
        let pat = segs(&pattern);
        let path: Vec<PathSeg<'_>> = (0..24).map(|_| PathSeg::new("a")).collect();
        let bound = pat.len() * path.len();
        let (matched, work) = count_matches(|| match_segments(&pat, &path));
        assert!(!matched);
        assert!(work <= bound, "{work} glob matches, bound {bound}");
        // the bound discriminates: the reference blows through it at this size
        let (reference, reference_work) = count_matches(|| match_segments_reference(&pat, &path));
        assert!(!reference);
        assert!(
            reference_work > 100 * bound,
            "the reference ran only {reference_work} glob matches"
        );
    }

    #[test]
    fn many_double_stars_in_a_gitignore_stay_bounded_across_ancestors() {
        // the shipped query: one rule, every ancestor prefix of a deep path walked — at a
        // size the recursive search still finishes, so a regression fails the bound
        // rather than hanging the suite
        let double_stars = 6;
        let mut rule = "**/a/".repeat(double_stars);
        rule.push_str("b/");
        let rule_segments = 2 * double_stars + 1;
        let mut stack = crate::IgnoreStack::new();
        stack.push_gitignore("", &rule);
        let depth = 24;
        let path = format!("{}/x.ts", vec!["a"; depth].join("/"));
        let (ignored, work) = count_matches(|| stack.is_ignored(&path, crate::PathKind::File));
        assert!(!ignored);
        // per ancestor prefix of `k` segments, at most one match per rule segment per
        // path segment
        let bound: usize = (1..=depth).map(|k| rule_segments * k).sum();
        assert!(work <= bound, "{work} glob matches, bound {bound}");
    }

    /// A seeded linear congruential generator — deterministic, dependency-free.
    struct Lcg(u64);

    impl Lcg {
        fn below(&mut self, n: usize) -> usize {
            self.0 = self
                .0
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            usize::try_from(self.0 >> 33).unwrap_or(0) % n
        }
    }

    #[test]
    fn reachability_agrees_with_the_recursive_reference_on_random_cases() {
        // past the exhaustive domain: longer patterns and paths, and every token kind in
        // the segments around a `**` (`?`, classes, negated classes, `]` as a member,
        // star-only runs that parse as `**`)
        let pattern_alphabet = [
            "**", "**", "***", "a", "b", "*", "?", "[ab]", "[!a]", "c*", "*b", "[a-c]", "a?",
            "[]a]",
        ];
        let path_alphabet = ["a", "b", "c", "ab", "ba", "cb", "]"];
        let mut rng = Lcg(0x5eed);
        for _ in 0..100_000 {
            let pattern: Vec<&str> = (0..=rng.below(8))
                .map(|_| pattern_alphabet[rng.below(pattern_alphabet.len())])
                .collect();
            let path: Vec<&str> = (0..rng.below(10))
                .map(|_| path_alphabet[rng.below(path_alphabet.len())])
                .collect();
            let pat = segs(&pattern);
            let path_segs: Vec<PathSeg<'_>> = path.iter().map(|s| PathSeg::new(s)).collect();
            assert_eq!(
                match_segments(&pat, &path_segs),
                match_segments_reference(&pat, &path_segs),
                "pattern {pattern:?} against {path:?}",
            );
        }
    }
}