//
// 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!
// Tests call fnmatch(3) to compare.
#![cfg_attr(not(test), forbid(unsafe_code))]

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

use memchr::{
    arch::all::{is_equal, is_prefix},
    memchr, memchr2, 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.
pub fn contains(haystack: &[u8], needle: &[u8]) -> bool {
    memmem::find(haystack, needle).is_some()
}

/// Apply matching according to given type and return result.
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.
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.
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 {
    dowild(pattern, path) == MatchResult::Match
}

// Return true if the character is a glob special character: `*`, `?`, or `[`.
const fn is_glob_special(c: u8) -> bool {
    matches!(c, b'*' | b'?' | b'[')
}

// Helper function to determine if the next character in the pattern is a literal target.
// Returns `Some(target)` if a literal is found, `None` otherwise.
fn litchar(p: &[u8], idx: usize) -> Option<u8> {
    match p.get(idx).copied()? {
        b'\\' => p.get(idx + 1).copied(),
        ch if is_glob_special(ch) => None,
        ch => Some(ch),
    }
}

// Fast path optimization for '*' wildcard matching.
// Scans `text` for `target` character or path separator using SIMD.
fn matchfast(target: u8, mut text: &[u8], p_rest: &[u8]) -> MatchResult {
    while let Some(pos) = memchr2(target, b'/', text) {
        // Check if we hit a path separator first.
        if text[pos] == b'/' {
            if target == b'/' {
                // If the target itself is '/',
                // we must check if recursing from here matches.
                let m = dowild(p_rest, &text[pos..]);
                if m != MatchResult::NoMatch {
                    return m;
                }
            }

            // We hit a slash (barrier) before finding a valid match for `target`.
            // Single '*' cannot match across directory boundaries.
            return MatchResult::AbortToStarStar;
        }

        // We found the target literal.
        // Try to match the rest of the pattern.
        let m = dowild(p_rest, &text[pos..]);
        if m != MatchResult::NoMatch {
            return m;
        }

        // Logic to advance:
        // We found 'target' at 'pos', but dowild returned NoMatch.
        // We must continue searching `text` *after* this position.
        // SAFETY: pos + 1 may be at text.len(), which is valid for slicing (empty slice).
        text = &text[pos + 1..];
    }

    // Neither target nor slash found.
    // Since '*' consumes everything until it hits a barrier or match,
    // and we hit nothing interesting, we have consumed the rest of this
    // segment without finding the target.
    MatchResult::AbortAll
}

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

// Supported POSIX classes.
// This array must be sorted by name, it's binary searched.
#[expect(clippy::type_complexity)]
const POSIX_CLASSES: &[(&[u8], fn(u8) -> bool)] = &[
    (b"alnum", |c| c.is_ascii_alphanumeric()),
    (b"alpha", |c| c.is_ascii_alphabetic()),
    (b"blank", |c| matches!(c, b' ' | b'\t')),
    (b"cntrl", |c| c.is_ascii_control()),
    (b"digit", |c| c.is_ascii_digit()),
    (b"graph", |c| c.is_ascii_graphic()),
    (b"lower", |c| c.is_ascii_lowercase()),
    (b"print", |c| c.is_ascii() && !c.is_ascii_control()),
    (b"punct", |c| c.is_ascii_punctuation()),
    (b"space", |c| c.is_ascii_whitespace()),
    (b"upper", |c| c.is_ascii_uppercase()),
    (b"xdigit", |c| c.is_ascii_hexdigit()),
];

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

    while let Some(p_ch) = p.get(p_idx).copied() {
        if text.is_empty() && p_ch != b'*' {
            return MatchResult::AbortAll;
        }

        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 && memchr(b'/', text).is_some() {
                        return MatchResult::NoMatch;
                    }
                    return MatchResult::Match;
                }

                let mut next_start = 0;

                // Fast path for single star '*' followed by a literal.
                if !is_double_star {
                    if let Some(target) = litchar(p, p_idx) {
                        let m = matchfast(target, text, &p[p_idx..]);
                        if m != MatchResult::NoMatch {
                            return m;
                        }
                        // If matchfast returns NoMatch, it means it scanned the whole segment
                        // and didn't find a valid match. We can skip the slow loop for this segment.
                        next_start = text.len();
                    }
                }

                let check_anchored = 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'/';

                while next_start <= text.len() {
                    if check_anchored && 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;
                    }

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

                    next_start += 1;
                }

                // If no match found after all attempts.
                return MatchResult::AbortAll;
            }
            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 let Some(c) = t_ch.copied() {
                            if let Ok(pos) =
                                POSIX_CLASSES.binary_search_by(|(name, _)| name.cmp(&class))
                            {
                                if POSIX_CLASSES[pos].1(c) {
                                    matched = true;
                                }
                            } else {
                                return MatchResult::AbortAll;
                            }
                        }
                        p_ch = 0; // set "prev_ch" to 0.
                    } else if t_ch.copied().map(|c| c == p_ch).unwrap_or(false) {
                        matched = true;
                    }

                    p_idx += 1;
                    match p.get(p_idx).copied() {
                        None => return MatchResult::AbortAll,
                        Some(b']') => break,
                        Some(c) => {
                            prev_ch = p_ch;
                            p_ch = c;
                        }
                    }
                }

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

        p_idx += 1;
        if !text.is_empty() {
            text = &text[1..];
        }
    }

    if text.is_empty() {
        MatchResult::Match
    } else {
        MatchResult::NoMatch
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[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() {
        use std::io::BufRead;

        let data = include_bytes!("wildtest.txt.xz");
        let decoder = xz2::read::XzDecoder::new(&data[..]);
        let reader = std::io::BufReader::new(decoder);

        let mut failures = 0;
        let mut test_cnt = 0;

        for (index, line) in reader.lines().enumerate() {
            let line = line.expect("Failed to read line from wildtest.txt.xz");
            let line_bytes = line.as_bytes();
            let line_num = index + 1;

            if line_bytes.starts_with(&[b'#'])
                || line_bytes.iter().all(|&b| b == b' ' || b == b'\t')
                || line.is_empty()
            {
                continue;
            }

            if let Some((expected, fnmatch_same, text, pattern)) = parse_test_line(line_bytes) {
                test_cnt += 1;
                if let Err(err) = run_wildtest(line_num, expected, fnmatch_same, text, pattern) {
                    eprintln!("FAIL[{test_cnt}]\t{err}");
                    if !err.contains("fnmatch") {
                        failures += 1;
                    }
                } else {
                    eprint!(".");
                }
            } else {
                unreachable!("BUG: Fix test at line {test_cnt}: {line}!");
            }
        }

        if failures > 0 {
            panic!("{failures} out of {test_cnt} tests failed.");
        }
    }

    /// Parse a test line without allocating intermediate structures.
    /// Returns (expected, fnmatch_same, text, pattern) if valid, None otherwise.
    fn parse_test_line(line: &[u8]) -> Option<(bool, bool, &[u8], &[u8])> {
        let mut parts = [&b""[..]; 4];
        let mut part_idx = 0;
        let mut i = 0;

        while i < line.len() && part_idx < 4 {
            // Skip whitespace
            while i < line.len() && matches!(line[i], b' ' | b'\t') {
                i += 1;
            }
            if i >= line.len() {
                break;
            }

            // Check for quoted section
            if matches!(line[i], b'\'' | b'"' | b'`') {
                let quote = line[i];
                i += 1;
                let start = i;
                while i < line.len() && line[i] != quote {
                    i += 1;
                }
                parts[part_idx] = &line[start..i];
                if i < line.len() {
                    i += 1; // Skip closing quote
                }
            } else {
                // Unquoted section
                let start = i;
                while i < line.len() && !matches!(line[i], b' ' | b'\t') {
                    i += 1;
                }
                parts[part_idx] = &line[start..i];
            }
            part_idx += 1;
        }

        if part_idx >= 4 {
            let expected = parts[0].first() == Some(&b'1');
            let fnmatch_same = parts[1].first() == Some(&b'1');
            Some((expected, fnmatch_same, parts[2], parts[3]))
        } else {
            None
        }
    }

    fn run_wildtest(
        line: usize,
        expected: bool,
        fnmatch_same: bool,
        text: &[u8],
        pattern: &[u8],
    ) -> Result<(), String> {
        let result = wildmatch(pattern, text);
        if result != expected {
            let text = String::from_utf8_lossy(text);
            let pattern = String::from_utf8_lossy(pattern);
            let msg = format!(
                "[!] Test failed on line {line}: text='{text}', pattern='{pattern}', expected={expected}, got={result}",
            );
            return Err(msg);
        }

        let fn_result = fnmatch(pattern, text);
        let same = fn_result == result;
        if same != fnmatch_same {
            let text = String::from_utf8_lossy(text);
            let pattern = String::from_utf8_lossy(pattern);
            let msg = format!(
                "[!] fnmatch divergence on line {line}: text='{text}', pattern='{pattern}', wildmatch={result}, fnmatch={fn_result}, expected_same={fnmatch_same}",
            );
            return Err(msg);
        }

        Ok(())
    }

    fn fnmatch(pat: &[u8], input: &[u8]) -> bool {
        pat.with_nix_path(|pat_cstr| {
            input.with_nix_path(|input_cstr| {
                let flags = libc::FNM_PATHNAME | libc::FNM_NOESCAPE | libc::FNM_PERIOD;
                // SAFETY: FFI call to fnmatch(3)
                unsafe { libc::fnmatch(pat_cstr.as_ptr(), input_cstr.as_ptr(), flags) == 0 }
            })
        })
        .map(|res| res.unwrap())
        .unwrap()
    }
}
