vendor/gix-glob/src/wildmatch.rs

use bitflags::bitflags;
bitflags! {
    /// The match mode employed in [`Pattern::matches()`][crate::Pattern::matches()].
    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
    #[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
    pub struct Mode: u8 {
        /// Let globs like `*` and `?` not match the slash `/` literal, which is useful when matching paths.
        const NO_MATCH_SLASH_LITERAL = 1 << 0;
        /// Match case insensitively for ascii characters only.
        const IGNORE_CASE = 1 << 1;
    }
}

pub(crate) mod function {
    use bstr::{BStr, ByteSlice};

    use crate::wildmatch::Mode;

    #[derive(Eq, PartialEq)]
    enum Result {
        Match,
        NoMatch,
        AbortAll,
        AbortToStarStar,
        RecursionLimitReached,
    }

    const STAR: u8 = b'*';
    const BACKSLASH: u8 = b'\\';
    const SLASH: u8 = b'/';
    const BRACKET_OPEN: u8 = b'[';
    const BRACKET_CLOSE: u8 = b']';
    const COLON: u8 = b':';

    const NEGATE_CLASS: u8 = b'!';
    /// Setting this limit to something reasonable means less compute time spent on unnecessarily complex patterns, or malicious ones.
    const RECURSION_LIMIT: usize = 64;

    fn match_recursive(pattern: &BStr, text: &BStr, mode: Mode, depth: usize) -> Result {
        if depth == RECURSION_LIMIT {
            return RecursionLimitReached;
        }
        use self::Result::*;
        let possibly_lowercase = |c: &u8| {
            if mode.contains(Mode::IGNORE_CASE) {
                c.to_ascii_lowercase()
            } else {
                *c
            }
        };
        let mut p = pattern.iter().map(possibly_lowercase).enumerate().peekable();
        let mut t = text.iter().map(possibly_lowercase).enumerate();

        while let Some((mut p_idx, mut p_ch)) = p.next() {
            let (mut t_idx, mut t_ch) = match t.next() {
                Some(c) => c,
                None if p_ch != STAR => return AbortAll,
                None => (text.len(), 0),
            };

            if p_ch == BACKSLASH {
                match p.next() {
                    Some((_p_idx, p_ch)) => {
                        if p_ch != t_ch {
                            return NoMatch;
                        } else {
                            continue;
                        }
                    }
                    None => return NoMatch,
                };
            }
            match p_ch {
                b'?' => {
                    if mode.contains(Mode::NO_MATCH_SLASH_LITERAL) && t_ch == SLASH {
                        return NoMatch;
                    } else {
                        continue;
                    }
                }
                STAR => {
                    let mut match_slash = !mode.contains(Mode::NO_MATCH_SLASH_LITERAL);
                    match p.next() {
                        Some((next_p_idx, next_p_ch)) => {
                            let next;
                            if next_p_ch == STAR {
                                let leading_slash_idx = p_idx.checked_sub(1);
                                while p.next_if(|(_, c)| *c == STAR).is_some() {}
                                next = p.next();
                                if !mode.contains(Mode::NO_MATCH_SLASH_LITERAL) {
                                    match_slash = true;
                                } else if leading_slash_idx.map_or(true, |idx| pattern[idx] == SLASH)
                                    && next.map_or(true, |(_, c)| {
                                        c == SLASH || (c == BACKSLASH && p.peek().map(|t| t.1) == Some(SLASH))
                                    })
                                {
                                    if next.map_or(NoMatch, |(idx, _)| {
                                        match_recursive(
                                            pattern[idx + 1..].as_bstr(),
                                            text[t_idx..].as_bstr(),
                                            mode,
                                            depth + 1,
                                        )
                                    }) == Match
                                    {
                                        return Match;
                                    }
                                    match_slash = true;
                                } else {
                                    match_slash = false;
                                }
                            } else {
                                next = Some((next_p_idx, next_p_ch));
                            }

                            match next {
                                None => {
                                    return if !match_slash && text[t_idx..].contains(&SLASH) {
                                        NoMatch
                                    } else {
                                        Match
                                    };
                                }
                                Some((next_p_idx, next_p_ch)) => {
                                    p_idx = next_p_idx;
                                    p_ch = next_p_ch;
                                    if !match_slash && p_ch == SLASH {
                                        match text[t_idx..].find_byte(SLASH) {
                                            Some(distance_to_slash) => {
                                                for _ in t.by_ref().take(distance_to_slash) {}
                                                continue;
                                            }
                                            None => return NoMatch,
                                        }
                                    }
                                }
                            }
                        }
                        None => {
                            return if !match_slash && text[t_idx..].contains(&SLASH) {
                                NoMatch
                            } else {
                                Match
                            }
                        }
                    }

                    return loop {
                        if !crate::parse::GLOB_CHARACTERS.contains(&p_ch) {
                            loop {
                                if (!match_slash && t_ch == SLASH) || t_ch == p_ch {
                                    break;
                                }
                                match t.next() {
                                    Some(t) => {
                                        t_idx = t.0;
                                        t_ch = t.1;
                                    }
                                    None => break,
                                };
                            }
                            if t_ch != p_ch {
                                return NoMatch;
                            }
                        }
                        let res = match_recursive(pattern[p_idx..].as_bstr(), text[t_idx..].as_bstr(), mode, depth + 1);
                        if res != NoMatch {
                            if !match_slash || res != AbortToStarStar {
                                return res;
                            }
                        } else if !match_slash && t_ch == SLASH {
                            return AbortToStarStar;
                        }
                        match t.next() {
                            Some(t) => {
                                t_idx = t.0;
                                t_ch = t.1;
                            }
                            None => break AbortAll,
                        };
                    };
                }
                BRACKET_OPEN => {
                    match p.next() {
                        Some(t) => {
                            p_idx = t.0;
                            p_ch = t.1;
                        }
                        None => return AbortAll,
                    };

                    if p_ch == b'^' {
                        p_ch = NEGATE_CLASS;
                    }
                    let negated = p_ch == NEGATE_CLASS;
                    let mut next = if negated { p.next() } else { Some((p_idx, p_ch)) };
                    let mut prev_p_ch = 0;
                    let mut matched = false;
                    let mut p_idx_ofs = 0;
                    loop {
                        let Some((mut p_idx, mut p_ch)) = next else {
                            return AbortAll;
                        };
                        p_idx += p_idx_ofs;
                        match p_ch {
                            BACKSLASH => match p.next() {
                                Some((_, p_ch)) => {
                                    if p_ch == t_ch {
                                        matched = true
                                    } else {
                                        prev_p_ch = p_ch;
                                    }
                                }
                                None => return AbortAll,
                            },
                            b'-' if prev_p_ch != 0
                                && p.peek().is_some()
                                && p.peek().map(|t| t.1) != Some(BRACKET_CLOSE) =>
                            {
                                p_ch = p.next().expect("peeked").1;
                                if p_ch == BACKSLASH {
                                    p_ch = match p.next() {
                                        Some(t) => t.1,
                                        None => return AbortAll,
                                    };
                                }
                                if t_ch <= p_ch && t_ch >= prev_p_ch {
                                    matched = true;
                                } else if mode.contains(Mode::IGNORE_CASE) && t_ch.is_ascii_lowercase() {
                                    let t_ch_upper = t_ch.to_ascii_uppercase();
                                    if (t_ch_upper <= p_ch.to_ascii_uppercase()
                                        && t_ch_upper >= prev_p_ch.to_ascii_uppercase())
                                        || (t_ch_upper <= prev_p_ch.to_ascii_uppercase()
                                            && t_ch_upper >= p_ch.to_ascii_uppercase())
                                    {
                                        matched = true;
                                    }
                                }
                                prev_p_ch = 0;
                            }
                            BRACKET_OPEN if matches!(p.peek(), Some((_, COLON))) => {
                                p.next();
                                while p.peek().map_or(false, |t| t.1 != BRACKET_CLOSE) {
                                    p.next();
                                }
                                let closing_bracket_idx = match p.next() {
                                    Some((idx, _)) => idx,
                                    None => return AbortAll,
                                };
                                const BRACKET__COLON__BRACKET: usize = 3;
                                if closing_bracket_idx.saturating_sub(p_idx) < BRACKET__COLON__BRACKET
                                    || pattern[closing_bracket_idx - 1] != COLON
                                {
                                    if t_ch == BRACKET_OPEN {
                                        matched = true
                                    }
                                    if p_idx > pattern.len() {
                                        return AbortAll;
                                    }
                                    p = pattern[p_idx..].iter().map(possibly_lowercase).enumerate().peekable();
                                    p_idx_ofs += p_idx;
                                } else {
                                    let class = &pattern.as_bytes()[p_idx + 2..closing_bracket_idx - 1];
                                    match class {
                                        b"alnum" => {
                                            if t_ch.is_ascii_alphanumeric() {
                                                matched = true;
                                            }
                                        }
                                        b"alpha" => {
                                            if t_ch.is_ascii_alphabetic() {
                                                matched = true;
                                            }
                                        }
                                        b"blank" => {
                                            if t_ch.is_ascii_whitespace() {
                                                matched = true;
                                            }
                                        }
                                        b"cntrl" => {
                                            if t_ch.is_ascii_control() {
                                                matched = true;
                                            }
                                        }
                                        b"digit" => {
                                            if t_ch.is_ascii_digit() {
                                                matched = true;
                                            }
                                        }

                                        b"graph" => {
                                            if t_ch.is_ascii_graphic() {
                                                matched = true;
                                            }
                                        }
                                        b"lower" => {
                                            if t_ch.is_ascii_lowercase() {
                                                matched = true;
                                            }
                                        }
                                        b"print" => {
                                            if (0x20u8..=0x7e).contains(&t_ch) {
                                                matched = true;
                                            }
                                        }
                                        b"punct" => {
                                            if t_ch.is_ascii_punctuation() {
                                                matched = true;
                                            }
                                        }
                                        b"space" => {
                                            if t_ch == b' ' {
                                                matched = true;
                                            }
                                        }
                                        b"upper" => {
                                            if t_ch.is_ascii_uppercase()
                                                || mode.contains(Mode::IGNORE_CASE) && t_ch.is_ascii_lowercase()
                                            {
                                                matched = true;
                                            }
                                        }
                                        b"xdigit" => {
                                            if t_ch.is_ascii_hexdigit() {
                                                matched = true;
                                            }
                                        }
                                        _ => return AbortAll,
                                    };
                                    prev_p_ch = 0;
                                }
                            }
                            _ => {
                                prev_p_ch = p_ch;
                                if p_ch == t_ch {
                                    matched = true;
                                }
                            }
                        };
                        next = p.next();
                        if let Some((_, BRACKET_CLOSE)) = next {
                            break;
                        }
                    }
                    if matched == negated || mode.contains(Mode::NO_MATCH_SLASH_LITERAL) && t_ch == SLASH {
                        return NoMatch;
                    }
                    continue;
                }
                non_glob_ch => {
                    if non_glob_ch != t_ch {
                        return NoMatch;
                    } else {
                        continue;
                    }
                }
            }
        }
        t.next().map_or(Match, |_| NoMatch)
    }

    /// Employ pattern matching to see if `value` matches `pattern`.
    ///
    /// `mode` can be used to adjust the way the matching is performed.
    pub fn wildmatch(pattern: &BStr, value: &BStr, mode: Mode) -> bool {
        let res = match_recursive(pattern, value, mode, 0);
        if res == Result::RecursionLimitReached {
            gix_features::trace::error!("Recursion limit of {} reached for pattern '{pattern}'", RECURSION_LIMIT);
        }
        res == Result::Match
    }
}