syd 3.42.0

//
// Syd: rock-solid application kernel
// src/wildmatch.rs: Shell-style pattern matching
//
// Copyright (c) 2024, 2025 Ali Polatel <alip@chesswob.org>
// Based in part upon rsync's lib/wildmatch.c which is:
//   Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
//   Rich $alz is now <rsalz@bbn.com>.
//   Modified by Wayne Davison to special-case '/' matching, to make '**'
//   work differently than '*', and to fix the character-class code.
//   SPDX-License-Identifier: GPL-3.0-or-later
//
// Changes by alip:
// - Ported to Rust.
// - Added SIMD support.
// - Intuitive matching for consecutive slashes separated by double
//   star, e.g. /usr/**/bin/bash matches /usr/bin/bash.
//
// SPDX-License-Identifier: GPL-3.0

// SAFETY: This module has been liberated from unsafe code!
#![forbid(unsafe_code)]

use std::{borrow::Cow, cmp::Ordering};

use memchr::{
    arch::all::{is_equal, is_prefix},
    memchr, memchr3, memmem,
};
use nix::NixPath;

use crate::{path::XPathBuf, XPath};

#[derive(Debug, PartialEq)]
enum MatchResult {
    Match,
    NoMatch,
    AbortAll,
    AbortToStarStar,
}

/// Match methods
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub enum MatchMethod {
    /// Literal match
    Literal,
    /// Prefix match
    Prefix,
    /// Glob match
    Glob,
}

/// Return true if haystack contains the substring needle.
#[inline(always)]
pub fn contains(haystack: &[u8], needle: &[u8]) -> bool {
    memmem::find(haystack, needle).is_some()
}

/// Apply matching according to given type and return result.
#[inline(always)]
pub fn globmatch(pattern: &[u8], path: &[u8], method: MatchMethod) -> bool {
    match method {
        MatchMethod::Literal => litmatch(pattern, path),
        MatchMethod::Prefix => prematch(pattern, path),
        MatchMethod::Glob => wildmatch(pattern, path),
    }
}

/// Convenience for glob matching of names.
///
/// Pattern is prefixed and suffixed with the `*` character
/// for literal, non-glob patterns.
///
/// Matching is done case-insensitively.
pub fn inamematch(pattern: &str, name: &str) -> bool {
    let glob = if !is_literal(pattern.as_bytes()) {
        Cow::Borrowed(pattern)
    } else {
        Cow::Owned(format!("*{pattern}*"))
    };

    wildmatch(
        glob.to_ascii_lowercase().as_bytes(),
        name.to_ascii_lowercase().as_bytes(),
    )
}

/// Return true if the pattern contains none of '*', '?', or '[',
/// indicating a literal string rather than a glob pattern.
pub fn is_literal(pattern: &[u8]) -> bool {
    memchr3(b'*', b'?', b'[', pattern).is_none()
}

/// Return Some(prefix) if the pattern can be reduced to a substring match.
pub fn get_prefix(pattern: &XPath) -> Option<XPathBuf> {
    if pattern.ends_with(b"/***") {
        // 1. Extract prefix (remove the slash).
        // 2. Check if the prefix is a literal string.
        let len = pattern.len();
        let pre = &pattern.as_bytes()[..len - "/***".len()];
        if is_literal(pre) {
            return Some(pre.into());
        }
    } else if pattern.ends_with(b"/**") {
        // 1. Extract prefix (keep the slash!)
        // 2. Check if the prefix is a literal string.
        let len = pattern.len();
        let pre = &pattern.as_bytes()[..len - "**".len()];
        if is_literal(pre) {
            return Some(pre.into());
        }
    }

    None
}

/// Match the "pattern" against the "path" literally.
///
/// This function performs simple string matching.
///
/// # Arguments
///
/// * `pattern` - The literal string to match.
/// * `path` - The path to match against the pattern.
///
/// # Returns
///
/// * `true` if the path matches the pattern.
/// * `false` otherwise.
#[inline(always)]
pub fn litmatch(pattern: &[u8], path: &[u8]) -> bool {
    is_equal(path, pattern)
}

/// Match the "pattern" against the "path" using prefix match.
///
/// This function performs simple substring matching.
///
/// # Arguments
///
/// * `pattern` - The prefix to match.
/// * `path` - The path to match against the pattern.
///
/// # Returns
///
/// * `true` if the path matches the pattern.
/// * `false` otherwise.
#[inline(always)]
pub fn prematch(pattern: &[u8], path: &[u8]) -> bool {
    let len = pattern.len();
    let ord = path.len().cmp(&len);
    (ord == Ordering::Equal
        || (ord == Ordering::Greater && (pattern.last() == Some(&b'/') || path[len] == b'/')))
        && is_prefix(path, pattern)
}

/// Match the "pattern" against the "path".
///
/// This function performs shell-style pattern matching, supporting ?, \, [], and * characters.
/// It is 8-bit clean and has special handling for '/' characters and '**' patterns.
///
/// # Arguments
///
/// * `pattern` - The glob pattern to match.
/// * `path` - The path to match against the pattern.
///
/// # Returns
///
/// * `true` if the path matches the pattern.
/// * `false` otherwise.
pub fn wildmatch(pattern: &[u8], path: &[u8]) -> bool {
    const NOMORE: [&[u8]; 0] = [];
    dowild(pattern, path, &NOMORE) == MatchResult::Match
}

const NEGATE_CLASS: u8 = b'!';
const NEGATE_CLASS2: u8 = b'^';

#[inline(always)]
#[expect(clippy::cognitive_complexity)]
fn dowild<'a>(p: &[u8], mut text: &'a [u8], mut a: &'a [&'a [u8]]) -> MatchResult {
    let mut p_idx = 0;

    while p_idx < p.len() {
        let p_ch = p[p_idx];

        while text.is_empty() {
            if a.is_empty() {
                if p_ch != b'*' {
                    return MatchResult::AbortAll;
                }
                break;
            }
            text = a[0];
            a = &a[1..];
        }

        let t_ch = text.first();
        match p_ch {
            b'\\' => {
                // Literal match with following character.
                p_idx += 1;
                if p_idx >= p.len() || t_ch != Some(&p[p_idx]) {
                    return MatchResult::NoMatch;
                }
            }
            b'?' => {
                // Match anything but '/'.
                if t_ch == Some(&b'/') {
                    return MatchResult::NoMatch;
                }
            }
            b'*' => {
                // Increment to skip '*' and check for double star '**'.
                p_idx += 1;
                let is_double_star = p_idx < p.len() && p[p_idx] == b'*';
                if is_double_star {
                    // Move past the second '*'.
                    p_idx += 1;

                    // Ensure intuitive matching for consecutive slashes
                    // separated by double star. This ensures, e.g.
                    // /usr/**/bin/bash matches /usr/bin/bash.
                    if p_idx < p.len() && p[p_idx] == b'/' && p_idx >= 3 && p[p_idx - 3] == b'/' {
                        p_idx += 1;
                    }
                }

                // Handle trailing '*' or '**'.
                if p_idx == p.len() {
                    // Trailing '**' matches everything.
                    // Trailing '*' matches only if there are no more '/' in the remaining segments.
                    if !is_double_star {
                        if memchr(b'/', text).is_some() {
                            return MatchResult::NoMatch;
                        }
                        for &text in a {
                            if memchr(b'/', text).is_some() {
                                return MatchResult::NoMatch;
                            }
                        }
                    }
                    return MatchResult::Match;
                }

                let mut next_start = 0;
                while next_start <= text.len() {
                    if is_double_star
                        && p_idx >= 4
                        && p[p_idx - 4] == b'/'
                        && p[p_idx - 3] == b'*'
                        && p[p_idx - 2] == b'*'
                        && p[p_idx - 1] == b'/'
                        && next_start > 0
                        && text[next_start - 1] != b'/'
                    {
                        // Ensure component-anchored matching after "/**/".
                        // Prevent mid-component matches (e.g., /usr/**/bin !~ /usr/sabin)
                        // and avoid drifting ".*/" into names (e.g., / ** /.*/ ** !~ /a/b.c/...).
                        // Zero-segment behavior is preserved (e.g., /**/bin matches /bin).
                        next_start += 1;
                        continue;
                    }
                    if next_start == text.len() {
                        // Attempt to move to the next segment if available.
                        if let Some(next_text) = a.first() {
                            text = next_text;
                            a = &a[1..];
                            next_start = 0; // Reset start position for new segment.
                            continue;
                        } else {
                            break; // No more segments to process.
                        }
                    }

                    let m = dowild(&p[p_idx..], &text[next_start..], a);
                    if m != MatchResult::NoMatch {
                        if !is_double_star || m != MatchResult::AbortToStarStar {
                            return m;
                        }
                    } else if !is_double_star && text[next_start] == b'/' {
                        return MatchResult::AbortToStarStar; // Stop at '/' if '*'.
                    }

                    next_start += 1;
                }

                return MatchResult::AbortAll; // If no match found after all attempts.
            }
            b'[' => {
                // Handle character classes
                p_idx += 1;
                let mut negated = false;
                let mut matched = false;
                let mut prev_ch = 0;

                // Check for negation at the beginning of the class
                if p_idx < p.len() && matches!(p[p_idx], NEGATE_CLASS | NEGATE_CLASS2) {
                    negated = true;
                    p_idx += 1;
                }

                if p_idx >= p.len() {
                    return MatchResult::AbortAll;
                }
                let mut p_ch = p[p_idx];
                loop {
                    if p_ch == b'\\' {
                        // Handle escaped characters within the class.
                        p_idx += 1;
                        if p_idx < p.len() {
                            p_ch = p[p_idx];
                            if let Some(c) = t_ch {
                                if p_ch == *c {
                                    matched = true;
                                }
                            }
                        } else {
                            return MatchResult::AbortAll;
                        }
                    } else if p_ch == b'-'
                        && prev_ch != 0
                        && p_idx + 1 < p.len()
                        && p[p_idx + 1] != b']'
                    {
                        // Handle character ranges, e.g., a-z.
                        p_idx += 1;
                        p_ch = p[p_idx];
                        if p_ch == b'\\' {
                            p_idx += 1;
                            if p_idx < p.len() {
                                p_ch = p[p_idx];
                            } else {
                                return MatchResult::AbortAll;
                            }
                        }
                        if let Some(&c) = t_ch {
                            if c >= prev_ch && c <= p_ch {
                                matched = true;
                            }
                        }
                        p_ch = 0; // sets "prev_ch" to 0.
                    } else if p_ch == b'[' && p_idx + 1 < p.len() && p[p_idx + 1] == b':' {
                        // Start of a POSIX character class.
                        p_idx += 2;
                        let class_start = p_idx;
                        if let Some(n) = memchr(b']', &p[class_start..]) {
                            p_idx += n;
                        } else {
                            return MatchResult::AbortAll;
                        }
                        if p_idx - class_start == 0 || p[p_idx - 1] != b':' {
                            // Didn't find ":]", so treat like a normal set.
                            p_idx = class_start - 2;
                            p_ch = b'[';
                            if let Some(c) = t_ch {
                                if p_ch == *c {
                                    matched = true;
                                }
                            }
                            p_idx += 1;
                            if p_idx >= p.len() || p[p_idx] == b']' {
                                break;
                            }
                            prev_ch = p_ch;
                            p_ch = p[p_idx];
                            continue;
                        }

                        // Properly closed POSIX class.
                        let class = &p[class_start..p_idx - 1];
                        if match (class, t_ch) {
                            (_, None) => false,
                            (b"alnum", Some(c)) => c.is_ascii_alphanumeric(),
                            (b"alpha", Some(c)) => c.is_ascii_alphabetic(),
                            (b"blank", Some(c)) => matches!(c, b' ' | b'\t'),
                            (b"cntrl", Some(c)) => c.is_ascii_control(),
                            (b"digit", Some(c)) => c.is_ascii_digit(),
                            (b"graph", Some(c)) => c.is_ascii_graphic(),
                            (b"lower", Some(c)) => c.is_ascii_lowercase(),
                            (b"print", Some(c)) => c.is_ascii() && !c.is_ascii_control(),
                            (b"punct", Some(c)) => c.is_ascii_punctuation(),
                            (b"space", Some(c)) => c.is_ascii_whitespace(),
                            (b"upper", Some(c)) => c.is_ascii_uppercase(),
                            (b"xdigit", Some(c)) => c.is_ascii_hexdigit(),
                            _ => return MatchResult::AbortAll,
                        } {
                            matched = true;
                        }
                        p_ch = 0; // set "prev_ch" to 0.
                    } else if let Some(c) = t_ch {
                        if p_ch == *c {
                            matched = true;
                        }
                    }

                    p_idx += 1;
                    if p_idx >= p.len() {
                        return MatchResult::AbortAll;
                    } else if p[p_idx] == b']' {
                        break;
                    }
                    prev_ch = p_ch;
                    p_ch = p[p_idx];
                }

                // Final checks for matching or negation
                if matched == negated || t_ch == Some(&b'/') {
                    return MatchResult::NoMatch;
                }
            }
            _ => {
                // Literal character match
                if let Some(c) = t_ch {
                    if p_ch != *c {
                        return MatchResult::NoMatch;
                    }
                }
            }
        }

        p_idx += 1;
        text = &text[1..];
    }

    if !text.is_empty() {
        return MatchResult::NoMatch;
    }

    for sub_text in a {
        if !sub_text.is_empty() {
            return MatchResult::NoMatch;
        }
    }

    MatchResult::Match
}

#[cfg(test)]
mod tests {
    use std::{
        ffi::{OsStr, OsString},
        os::unix::ffi::{OsStrExt, OsStringExt},
    };

    use super::*;

    const WILDTEST: &[u8] = include_bytes!("wildtest.txt");

    #[test]
    fn test_litmatch() {
        assert!(litmatch(b"", b""));
        assert!(litmatch(b"p", b"p"));
        assert!(!litmatch(b"p", b"P"));
        assert!(litmatch(b"/usr", b"/usr"));
        assert!(!litmatch(b"/usr", b"/usr/"));
    }

    #[test]
    fn test_prematch() {
        assert!(prematch(b"", b""));
        assert!(prematch(b"p", b"p"));
        assert!(!prematch(b"p", b"P"));
        assert!(prematch(b"/usr", b"/usr"));
        assert!(prematch(b"/usr", b"/usr/"));
        assert!(prematch(b"/usr", b"/usr/bin"));
        assert!(!prematch(b"/usr", b"/usra"));
        assert!(!prematch(b"/usr", b"/usra/bin"));
    }

    #[test]
    fn test_wildmatch() {
        let lines: Vec<&[u8]> = WILDTEST.split(|&b| b == b'\n').collect();
        let mut failures = Vec::new();
        let mut test_cnt = 0;

        for (index, line) in lines.iter().enumerate() {
            let line_num = index + 1;
            if line.starts_with(&[b'#'])
                || line.iter().all(|&b| b == b' ' || b == b'\t' || b == b'\n')
            {
                continue;
            }
            // Split the line into parts and handle quoted sections properly
            let parts = split_quoted_parts(line);
            if parts.len() < 4 {
                failures.push(format!(
                    "Invalid test format on line {}: {}",
                    line_num,
                    String::from_utf8_lossy(line),
                ));
                continue;
            }
            let expected = parts[0].as_bytes().first() == Some(&b'1');
            let text = &parts[2];
            let pattern = &parts[3];

            test_cnt += 1;
            if let Err(err) = run_wildtest(line_num, expected, text, pattern) {
                failures.push(err);
            }
        }

        if !failures.is_empty() {
            for failure in &failures {
                eprintln!("{}", failure);
            }
            panic!("{} out of {} tests failed.", failures.len(), test_cnt);
        }
    }

    fn run_wildtest(
        line: usize,
        expected: bool,
        text: &OsStr,
        pattern: &OsStr,
    ) -> Result<(), String> {
        let result = wildmatch(pattern.as_bytes(), text.as_bytes());
        let text_display = text.to_string_lossy();
        let pattern_display = pattern.to_string_lossy();
        if result == expected {
            let msg = format!(
                "[*] Test passed on line {}: text='{}', pattern='{}', expected={}, got={}",
                line, text_display, pattern_display, expected, result
            );
            eprintln!("{msg}");
            Ok(())
        } else {
            let msg = format!(
                "[!] Test failed on line {}: text='{}', pattern='{}', expected={}, got={}",
                line, text_display, pattern_display, expected, result
            );
            eprintln!("{msg}");
            Err(msg)
        }
    }

    fn split_quoted_parts(input: &[u8]) -> Vec<OsString> {
        let mut parts = Vec::new();
        let mut current_part = Vec::new();
        let mut in_quotes = false;

        for &byte in input {
            match byte {
                b'\'' | b'"' => {
                    if in_quotes {
                        in_quotes = false;
                        parts.push(OsString::from_vec(current_part.clone()));
                        current_part.clear();
                    } else {
                        in_quotes = true;
                    }
                }
                b' ' | b'\t' if !in_quotes => {
                    if !current_part.is_empty() {
                        parts.push(OsString::from_vec(current_part.clone()));
                        current_part.clear();
                    }
                }
                _ => current_part.push(byte),
            }
        }
        if !current_part.is_empty() {
            parts.push(OsString::from_vec(current_part));
        }
        parts
    }
}