syd 3.57.0

//
// Syd: rock-solid application kernel
// src/wildmatch.rs: Shell-style pattern matching
//
// Copyright (c) 2024, 2025, 2026 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
// Based in part upon Kirk Krauss's FastWildCompare algorithm which is:
//   Copyright 2018 IBM Corporation
//   See: https://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html
//   SPDX-License-Identifier: Apache-2.0
//
// 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.
// - Rewrite using Kirk Krauss's FastWildCompare algorithm,
//   extended with dual backup points for '*' and '**' wildcards.
//
// 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::{errno::Errno, NixPath};

use crate::{
    likely,
    path::{XPath, XPathBuf, PATH_MAX},
    unlikely,
};

/// 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.
#[inline]
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) -> Result<Option<XPathBuf>, Errno> {
    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 Ok(Some(XPathBuf::try_from(pre)?));
        }
    } 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 Ok(Some(XPathBuf::try_from(pre)?));
        }
    }

    Ok(None)
}

/// Determine match method for a pattern and handle `/***` splitting.
///
/// Returns `(method, optional_split_pattern)`:
/// - `method`: The match method to use (Prefix, Literal, or Glob)
/// - `split`: For `/***` patterns, contains the intermediate `foo/**` pattern
///
/// For `/***` patterns: `foo/***` is split into `foo/**` (returned in Option)
/// and `foo` (mutated in place).
#[expect(clippy::disallowed_methods)]
pub fn get_match_method(pat: &mut XPathBuf) -> Result<(MatchMethod, Option<XPathBuf>), Errno> {
    if let Some(prefix) = get_prefix(pat)? {
        *pat = prefix;
        Ok((MatchMethod::Prefix, None))
    } else if is_literal(pat.as_bytes()) {
        Ok((MatchMethod::Literal, None))
    } else if pat.ends_with(b"/***") {
        // Pattern followed by triple star: split into `foo/**` and `foo`.
        let len = pat.len();
        let len0 = len.checked_sub(b"*".len()).unwrap();
        let len1 = len.checked_sub(b"/***".len()).unwrap();
        pat.truncate(len0); // foo/*** -> foo/**
        let split = pat.try_clone()?;
        pat.truncate(len1); // foo/*** -> foo
        Ok((MatchMethod::Glob, Some(split)))
    } else {
        Ok((MatchMethod::Glob, 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 "text".
///
/// 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.
/// * `text` - The text to match against the pattern.
///
/// # Returns
///
/// * `true` if the path matches the pattern.
/// * `false` otherwise.
// Two-loop algorithm based on Kirk Krauss's FastWildCompare.
// Loop 1: Fast path for literals until '*' is found.
// Loop 2: Handle wildcards with dual backup points.
#[expect(clippy::cognitive_complexity)]
pub fn wildmatch(pattern: &[u8], text: &[u8]) -> bool {
    // Loop 1: Match literals until a special character is found.
    let mut idx = 0;
    for (&p_ch, &t_ch) in pattern.iter().zip(text.iter()) {
        if unlikely(matches!(p_ch, b'*' | b'[' | b'\\')) {
            // Special character detected, enter 2nd loop.
            break;
        }
        if unlikely((p_ch != b'?' && p_ch != t_ch) || (p_ch != b'/' && t_ch == b'/')) {
            // ?: Match any single character except '/'.
            // x: Literal match.
            return false;
        }
        idx += 1;
    }

    // Handle cases where one ran out before the other or both exhausted.
    let p_len = pattern.len();
    let t_len = text.len();
    if unlikely(idx >= p_len) {
        // Pattern exhausted: Only match if text also exhausted.
        return idx >= t_len;
    }

    if likely(idx >= t_len) {
        // Text exhausted:
        // 1. Pattern must be all wildcards.
        // 2. Handle intuitive '/**/' where trailing '/' is optional.
        let mut p_idx = idx;
        while let Some(p_ch) = pattern.get(p_idx) {
            // Skip all consecutive '*' characters.
            if p_ch == &b'*' {
                p_idx += 1;
                while pattern.get(p_idx) == Some(&b'*') {
                    p_idx += 1;
                }
            } else {
                return false;
            }

            // If we encounter '/', check the previous two characters to be '**'.
            if pattern.get(p_idx) == Some(&b'/') {
                for n in 1..=2 {
                    if p_idx
                        .checked_sub(n)
                        .map(|idx| pattern.get(idx) != Some(&b'*'))
                        .unwrap_or(true)
                    {
                        return false;
                    }
                }
                p_idx += 1;
            }
        }
        return true;
    }

    // Loop 2: Handle wildcards with dual backup points.
    let mut p_idx = idx;
    let mut t_idx = idx;

    // Backup points for backtracking:
    // star:     Backup for '*' which stops at '/'.
    // globstar: Backup for '**' which crosses '/'.
    struct BackupPoint {
        // Index into the pattern.
        p_idx: usize,
        // Index into the text.
        t_idx: usize,
    }
    let mut star_p: Option<BackupPoint> = None;
    let mut globstar_p: Option<BackupPoint> = None;
    let mut globstar_anchored = false;

    loop {
        if let Some(&p_ch) = pattern.get(p_idx) {
            match p_ch {
                b'*' => {
                    // Check for '**'.
                    let is_double = pattern.get(p_idx + 1).map(|&b| b == b'*').unwrap_or(false);

                    if is_double {
                        // Find end of consecutive '*' run.
                        let mut star_end = p_idx;
                        while pattern.get(star_end) == Some(&b'*') {
                            star_end += 1;
                        }

                        // Check for intuitive '/**/' matching:
                        // If pattern is '/**/' make the trailing '/' optional.
                        let anchored = p_idx
                            .checked_sub(1)
                            .map(|idx| pattern.get(idx) == Some(&b'/'))
                            .unwrap_or(false)
                            && pattern.get(star_end) == Some(&b'/');

                        if anchored {
                            p_idx = star_end + 1; // Skip stars and trailing '/'.
                            globstar_anchored = true;
                        } else {
                            p_idx += 2; // Skip both stars.
                            globstar_anchored = false;
                        }

                        // Set globstar backup point.
                        globstar_p = Some(BackupPoint { p_idx, t_idx });

                        // Clear single star: globstar takes over.
                        star_p = None;
                    } else {
                        p_idx += 1; // Skip the star.

                        // SIMD optimization: If next pattern char is a literal,
                        // use memchr2 to skip to its first occurrence or a '/'.
                        match pattern.get(p_idx).copied() {
                            None | Some(b'*' | b'?' | b'[' | b'\\') => {
                                // Set star backup point for non-literal next chars.
                                star_p = Some(BackupPoint { p_idx, t_idx });
                            }
                            Some(next_p) => {
                                // Find next_p or '/' in remaining text.
                                star_p = if let Some(skip) = memchr2(next_p, b'/', &text[t_idx..]) {
                                    if text[t_idx + skip] != b'/' {
                                        // Found the literal: Skip directly to it.
                                        t_idx += skip;
                                    }
                                    // Else we hit slash barrier: Single star can't cross.
                                    // Set backup point and let backtracking handle it.
                                    Some(BackupPoint { p_idx, t_idx })
                                } else if globstar_p.is_some() {
                                    // globstar: Fall through to backtracking.
                                    Some(BackupPoint { p_idx, t_idx })
                                } else {
                                    // Literal not found, no slash, and no globstar.
                                    return false;
                                };
                                continue;
                            }
                        }
                    }

                    // Check for trailing wildcard.
                    if p_idx < p_len {
                        continue;
                    }

                    // '**' matches everything.
                    if is_double {
                        return true;
                    }

                    // '*' at end: Check if no more '/' in text.
                    // If there is a '/', fall through to try globstar backtracking.
                    if memchr(b'/', &text[t_idx..]).is_none() {
                        return true;
                    }

                    // There's a '/': If no globstar backup, fail.
                    // Otherwise fall through to backtracking.
                    if globstar_p.is_none() {
                        return false;
                    }
                    // Fall through to backtracking below.
                }

                b'?' => {
                    if text.get(t_idx).map(|&b| b != b'/').unwrap_or(false) {
                        p_idx += 1;
                        t_idx += 1;
                        continue;
                    }
                }

                b'[' => match text.get(t_idx) {
                    None | Some(&b'/') => {}
                    Some(&t_ch) => {
                        if let Some(new_p) = classmatch(pattern, p_idx + 1, t_ch) {
                            p_idx = new_p;
                            t_idx += 1;
                            continue;
                        }
                    }
                },

                b'\\' => {
                    if pattern
                        .get(p_idx + 1)
                        .map(|esc| text.get(t_idx) == Some(esc))
                        .unwrap_or(false)
                    {
                        p_idx += 2;
                        t_idx += 1;
                        continue;
                    }
                }

                // Literal match.
                _ => {
                    if text.get(t_idx) == Some(&p_ch) {
                        p_idx += 1;
                        t_idx += 1;
                        continue;
                    }
                }
            }
        }

        // Check if both exhausted which means success.
        if p_idx >= p_len && t_idx >= t_len {
            return true;
        }

        // Check for trailing wildcards in pattern.
        if t_idx >= t_len {
            while matches!(pattern.get(p_idx), Some(&b'*')) {
                p_idx += 1;
            }
            return p_idx >= p_len;
        }

        // Mismatch: Try backtracking.
        //
        // Step 1: Try single star '*' first, bounded by '/'.
        if let Some(BackupPoint {
            p_idx: sp,
            t_idx: st,
        }) = star_p
        {
            if text.get(st).map(|&b| b != b'/').unwrap_or(false) {
                p_idx = sp;
                t_idx = st + 1;
                star_p = Some(BackupPoint { p_idx, t_idx });
                continue;
            }
            // Hit '/' - star is exhausted: Fall through to globstar.
        }

        // Step 2: Try globstar '**' which crosses '/'.
        if let Some(BackupPoint {
            p_idx: gsp,
            t_idx: gst,
        }) = globstar_p
        {
            if gst < t_len {
                if globstar_anchored {
                    // Must resume at component boundary: Find next '/'.
                    if let Some(pos) = memchr(b'/', &text[gst..]) {
                        p_idx = gsp;
                        t_idx = gst + pos + 1;
                        star_p = None;
                        globstar_p = Some(BackupPoint { p_idx, t_idx });
                        continue;
                    }
                    // No more slashes: globstar is exhausted.
                } else {
                    // Non-anchored: Resume at any position.
                    p_idx = gsp;
                    t_idx = gst + 1;
                    star_p = None;
                    globstar_p = Some(BackupPoint { p_idx, t_idx });
                    continue;
                }
            }
        }

        // No backtracking options left.
        return false;
    }
}

// Match a character class [...]
//
// Returns the pattern index after ']' if matched, None otherwise.
// An unterminated '[' is treated as a literal byte.
#[expect(clippy::cognitive_complexity)]
#[inline]
fn classmatch(pattern: &[u8], mut p_idx: usize, t_ch: u8) -> Option<usize> {
    let open = p_idx;
    let mut matched = false;
    let mut negated = false;
    let mut prev_ch: u8 = 0;
    let mut first = true;

    loop {
        let p_ch = if let Some(&p_ch) = pattern.get(p_idx) {
            p_ch
        } else {
            return if t_ch == b'[' { Some(open) } else { None };
        };

        // Check for negation.
        if unlikely(first && !negated && matches!(p_ch, NEGATE_CLASS | NEGATE_CLASS2)) {
            negated = true;
            p_idx += 1;
            continue;
        }

        // Handle ']' - closes the class unless it's at the start.
        if unlikely(p_ch == b']' && !first) {
            break;
        }

        first = false;
        match p_ch {
            b'\\' => {
                // Escaped character
                p_idx += 1;
                let escaped = if let Some(&escaped) = pattern.get(p_idx) {
                    escaped
                } else {
                    return if t_ch == b'[' { Some(open) } else { None };
                };
                if escaped == t_ch {
                    // A byte before "-<end>" starts a range, not a literal.
                    let tail = &pattern[p_idx..];
                    let range_start = tail.get(1) == Some(&b'-')
                        && tail.get(2).map(|&b| b != b']').unwrap_or(false);
                    if !range_start {
                        matched = true;
                    }
                }
                prev_ch = escaped;
                p_idx += 1;
            }
            b'-' if prev_ch != 0 && pattern.get(p_idx + 1).map(|&b| b != b']').unwrap_or(false) => {
                // Character range: prev_ch - next_ch
                p_idx += 1;
                let mut range_end = pattern[p_idx];
                if range_end == b'\\' {
                    p_idx += 1;
                    range_end = if let Some(&ch) = pattern.get(p_idx) {
                        ch
                    } else {
                        return if t_ch == b'[' { Some(open) } else { None };
                    };
                }
                if t_ch >= prev_ch && t_ch <= range_end {
                    matched = true;
                }
                p_idx += 1;
                prev_ch = 0; // Reset after range.
            }
            b'[' if pattern.get(p_idx + 1).map(|&b| b == b':').unwrap_or(false) => {
                // POSIX character class [:name:]
                p_idx += 2;
                let class_start = p_idx;

                // Find closing ':]'.
                while let Some(ch) = pattern.get(p_idx) {
                    if ch == &b':' && pattern.get(p_idx + 1) == Some(&b']') {
                        break;
                    }
                    p_idx += 1;
                }

                if unlikely(pattern.get(p_idx).map(|&b| b != b':').unwrap_or(true)) {
                    // Didn't find ':', treat '[' as literal.
                    p_idx = class_start - 2;
                    if pattern[p_idx] == t_ch {
                        matched = true;
                    }
                    prev_ch = b'[';
                    p_idx += 1;
                    continue;
                }

                // Look up POSIX class and call respective closure.
                let class_name = &pattern[class_start..p_idx];
                if let Ok(pos) = POSIX_CLASSES.binary_search_by(|(name, _)| name.cmp(&class_name)) {
                    if POSIX_CLASSES[pos].1(t_ch) {
                        matched = true;
                    }
                } else {
                    // Unknown POSIX class.
                    return None;
                }

                p_idx += 2; // Skip ':]'
                prev_ch = 0; // Reset after character class.
            }
            _ => {
                // Literal character in class.
                if p_ch == t_ch {
                    // A byte before "-<end>" starts a range, not a literal.
                    let tail = &pattern[p_idx..];
                    let range_start = tail.get(1) == Some(&b'-')
                        && tail.get(2).map(|&b| b != b']').unwrap_or(false);
                    if !range_start {
                        matched = true;
                    }
                }
                p_idx += 1;
                prev_ch = p_ch;
            }
        }
    }

    // p_idx is now at ']'.
    if matched != negated {
        Some(p_idx + 1)
    } else {
        None
    }
}

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

// Supported POSIX classes.
// This array must be sorted by name for binary search.
#[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()),
];

/// Return true if two glob patterns can match a common string.
pub fn globinter(a: &[u8], b: &[u8]) -> bool {
    globinter_method(a, MatchMethod::Glob, b, MatchMethod::Glob)
}

// A token in a glob pattern, as seen by "globinter".
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Token {
    // A literal byte.
    Lit(u8),
    // Any single byte, '?' or a '[...]' class.
    Any,
    // Any run of bytes, possibly empty ('*' or '**').
    Star,
}

/// Like [`globinter`], but honours the match method of each pattern.
pub fn globinter_method(a: &[u8], a_meth: MatchMethod, b: &[u8], b_meth: MatchMethod) -> bool {
    // Conservatively report an intersection for too long patterns.
    if a.len() > PATH_MAX || b.len() > PATH_MAX {
        return true;
    }

    let mut reach = [false; PATH_MAX + 2];

    // Row 0 with empty "a": b's leading tokens match empty string only
    // while every one of them is a Star.
    reach[0] = true;
    let mut ncol = 0;
    let mut b_idx = 0;
    while let Some(b_tok) = glob_step(b, &mut b_idx, b_meth) {
        ncol += 1;
        reach[ncol] = reach[ncol - 1] && b_tok == Token::Star;
    }

    // Fold "a" one token at a time, each row sweeps "b" left to right.
    let mut a_idx = 0;
    while let Some(a_tok) = glob_step(a, &mut a_idx, a_meth) {
        let a_star = a_tok == Token::Star;

        let mut diag = reach[0]; // Previous row, one column back.
        reach[0] = reach[0] && a_star; // Column 0: "a" so far must be all stars.

        let mut b_idx = 0;
        let mut col = 0;
        while let Some(b_tok) = glob_step(b, &mut b_idx, b_meth) {
            col += 1;
            let up = reach[col]; // Previous row, same column.
            reach[col] = if a_star || b_tok == Token::Star {
                up || reach[col - 1]
            } else {
                diag && glob_token_match(a_tok, b_tok)
            };
            diag = up;
        }
    }

    reach[ncol]
}

// Return the index just past the closing ']' of the class starting at "start" or None.
fn globclass_end(pattern: &[u8], start: usize) -> Option<usize> {
    let mut idx = start + 1; // Past opening '['.
    let mut prev_ch: u8 = 0;
    let mut first = true;
    let mut negated = false;

    loop {
        let ch = *pattern.get(idx)?;

        if first && !negated && matches!(ch, NEGATE_CLASS | NEGATE_CLASS2) {
            negated = true;
            idx += 1;
            continue;
        }

        // A ']' closes class unless it is first member.
        if ch == b']' && !first {
            return Some(idx + 1);
        }

        first = false;
        match ch {
            b'\\' => {
                // Escaped member:
                // Escaped byte becomes prev_ch (it may start a range).
                idx += 1;
                prev_ch = *pattern.get(idx)?;
                idx += 1;
            }
            b'-' if prev_ch != 0 && pattern.get(idx + 1).map(|&b| b != b']').unwrap_or(false) => {
                // Range: prev_ch - end:
                // End may itself be escaped.
                idx += 1;
                if pattern[idx] == b'\\' {
                    idx += 1;
                    pattern.get(idx)?;
                }
                idx += 1;
                prev_ch = 0;
            }
            b'[' if pattern.get(idx + 1) == Some(&b':') => {
                // POSIX set "[:name:]".
                idx += 2;
                let class_start = idx;
                while let Some(&c) = pattern.get(idx) {
                    if c == b':' && pattern.get(idx + 1) == Some(&b']') {
                        break;
                    }
                    idx += 1;
                }
                if pattern.get(idx) != Some(&b':') {
                    // No closing ':]':
                    // '[' is a literal member.
                    idx = class_start - 1;
                    prev_ch = b'[';
                } else {
                    idx += 2; // Past ":]".
                    prev_ch = 0;
                }
            }
            _ => {
                idx += 1;
                prev_ch = ch;
            }
        }
    }
}

// Return token starting at "start" together with index of the next one.
fn glob_next_token(pattern: &[u8], start: usize) -> (Token, usize) {
    let len = pattern.len();
    let first = pattern[start];

    if first == b'*' || (first == b'/' && pattern.get(start + 1) == Some(&b'*')) {
        let mut end = start;
        if first == b'/' {
            end += 1;
        }
        while end < len && pattern[end] == b'*' {
            end += 1;
        }
        if end < len && pattern[end] == b'/' {
            end += 1;
        }
        return (Token::Star, end);
    }

    match first {
        b'?' => (Token::Any, start + 1),
        b'[' => match globclass_end(pattern, start) {
            Some(end) => (Token::Any, end),
            None => (Token::Lit(b'['), start + 1),
        },
        b'\\' => {
            let end = if start + 1 < len {
                start + 2
            } else {
                start + 1
            };
            (Token::Lit(*pattern.get(start + 1).unwrap_or(&b'\\')), end)
        }
        _ => (Token::Lit(first), start + 1),
    }
}

// Return true if two non-star tokens can match the same byte.
fn glob_token_match(lhs: Token, rhs: Token) -> bool {
    match (lhs, rhs) {
        (Token::Lit(lhs), Token::Lit(rhs)) => lhs == rhs,
        _ => true,
    }
}

// Yield next token of "pattern" from "*idx" and advance it.
fn glob_step(pattern: &[u8], idx: &mut usize, meth: MatchMethod) -> Option<Token> {
    let len = pattern.len();
    if *idx < len {
        if meth != MatchMethod::Glob {
            let byte = pattern[*idx];
            *idx += 1;
            return Some(Token::Lit(byte));
        }
        let (tok, next) = glob_next_token(pattern, *idx);
        *idx = next;
        Some(tok)
    } else if meth == MatchMethod::Prefix && *idx == len {
        *idx = len + 1;
        Some(Token::Star)
    } else {
        None
    }
}

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

    #[test]
    fn test_litmatch_1() {
        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_contains_1() {
        assert!(contains(b"hello world", b"world"));
        assert!(contains(b"hello world", b"hello"));
        assert!(!contains(b"hello world", b"xyz"));
        assert!(contains(b"hello", b""));
        assert!(!contains(b"", b"x"));
    }

    #[test]
    fn test_is_literal_1() {
        assert!(is_literal(b"hello"));
        assert!(is_literal(b"/usr/bin/bash"));
        assert!(is_literal(b""));
        assert!(!is_literal(b"*.txt"));
        assert!(!is_literal(b"file?.log"));
        assert!(!is_literal(b"[abc]"));
    }

    #[test]
    fn test_globmatch_1() {
        assert!(globmatch(b"/usr", b"/usr", MatchMethod::Literal));
        assert!(!globmatch(b"/usr", b"/usr/bin", MatchMethod::Literal));
    }

    #[test]
    fn test_globmatch_2() {
        assert!(globmatch(b"/usr", b"/usr/bin", MatchMethod::Prefix));
        assert!(!globmatch(b"/usr", b"/usrlocal", MatchMethod::Prefix));
    }

    #[test]
    fn test_globmatch_3() {
        assert!(globmatch(
            b"/usr/*/bash",
            b"/usr/bin/bash",
            MatchMethod::Glob
        ));
        assert!(!globmatch(
            b"/usr/*/bash",
            b"/usr/local/bin/bash",
            MatchMethod::Glob
        ));
    }

    #[test]
    fn test_inamematch_1() {
        assert!(inamematch("hello", "HELLO"));
        assert!(inamematch("hello", "say hello world"));
        assert!(!inamematch("xyz", "hello"));
    }

    #[test]
    fn test_inamematch_2() {
        assert!(inamematch("*.TXT", "file.txt"));
        assert!(!inamematch("*.TXT", "file.log"));
    }

    #[test]
    fn test_get_prefix_1() {
        let pat = XPath::from_bytes(b"/usr/***");
        let result = get_prefix(pat).unwrap();
        assert_eq!(result.unwrap().as_bytes(), b"/usr");
    }

    #[test]
    fn test_get_prefix_2() {
        let pat = XPath::from_bytes(b"/usr/**");
        let result = get_prefix(pat).unwrap();
        assert_eq!(result.unwrap().as_bytes(), b"/usr/");
    }

    #[test]
    fn test_get_prefix_3() {
        let pat = XPath::from_bytes(b"/usr/*");
        assert!(get_prefix(pat).unwrap().is_none());
    }

    #[test]
    fn test_get_prefix_4() {
        let pat = XPath::from_bytes(b"/usr/[ab]/***");
        assert!(get_prefix(pat).unwrap().is_none());
    }

    #[test]
    fn test_get_prefix_5() {
        let pat = XPath::from_bytes(b"/usr/[ab]/**");
        assert!(get_prefix(pat).unwrap().is_none());
    }

    #[test]
    fn test_get_match_method_1() {
        let mut pat = XPathBuf::try_from("/usr/**").unwrap();
        let (method, split) = get_match_method(&mut pat).unwrap();
        assert_eq!(method, MatchMethod::Prefix);
        assert!(split.is_none());
        assert_eq!(pat.as_bytes(), b"/usr/");
    }

    #[test]
    fn test_get_match_method_2() {
        let mut pat = XPathBuf::try_from("/usr/bin").unwrap();
        let (method, split) = get_match_method(&mut pat).unwrap();
        assert_eq!(method, MatchMethod::Literal);
        assert!(split.is_none());
    }

    #[test]
    fn test_get_match_method_3() {
        let mut pat = XPathBuf::try_from("/usr/*.so").unwrap();
        let (method, split) = get_match_method(&mut pat).unwrap();
        assert_eq!(method, MatchMethod::Glob);
        assert!(split.is_none());
    }

    #[test]
    fn test_get_match_method_4() {
        let mut pat = XPathBuf::try_from("/usr/[ab]/***").unwrap();
        let (method, split) = get_match_method(&mut pat).unwrap();
        assert_eq!(method, MatchMethod::Glob);
        assert!(split.is_some());
        assert_eq!(split.unwrap().as_bytes(), b"/usr/[ab]/**");
        assert_eq!(pat.as_bytes(), b"/usr/[ab]");
    }

    #[test]
    fn test_prematch_1() {
        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_prematch_2() {
        assert!(!prematch(b"/usr/bin", b"/usr"));
    }

    #[test]
    fn test_prematch_3() {
        assert!(prematch(b"/usr/", b"/usr/bin"));
    }

    #[test]
    fn test_wildmatch_1() {
        assert!(wildmatch(b"\\a", b"a"));
        assert!(!wildmatch(b"\\a", b"b"));
    }

    #[test]
    fn test_wildmatch_2() {
        assert!(!wildmatch(b"\\", b"a"));
    }

    #[test]
    fn test_wildmatch_3() {
        assert!(wildmatch(b"[[:alpha:]]", b"a"));
        assert!(!wildmatch(b"[[:alpha:]]", b"1"));
    }

    #[test]
    fn test_wildmatch_4() {
        assert!(wildmatch(b"[[:digit:]]", b"5"));
        assert!(!wildmatch(b"[[:digit:]]", b"x"));
    }

    #[test]
    fn test_wildmatch_5() {
        assert!(wildmatch(b"[[:upper:]]", b"Z"));
        assert!(!wildmatch(b"[[:upper:]]", b"z"));
    }

    #[test]
    fn test_wildmatch_6() {
        assert!(wildmatch(b"[[:lower:]]", b"z"));
        assert!(!wildmatch(b"[[:lower:]]", b"Z"));
    }

    #[test]
    fn test_wildmatch_7() {
        assert!(wildmatch(b"[[:alnum:]]", b"a"));
        assert!(wildmatch(b"[[:alnum:]]", b"5"));
        assert!(!wildmatch(b"[[:alnum:]]", b"!"));
    }

    #[test]
    fn test_wildmatch_8() {
        assert!(wildmatch(b"[[:space:]]", b" "));
        assert!(wildmatch(b"[[:space:]]", b"\t"));
        assert!(!wildmatch(b"[[:space:]]", b"a"));
    }

    #[test]
    fn test_wildmatch_9() {
        assert!(wildmatch(b"[[:xdigit:]]", b"f"));
        assert!(wildmatch(b"[[:xdigit:]]", b"A"));
        assert!(!wildmatch(b"[[:xdigit:]]", b"g"));
    }

    #[test]
    fn test_wildmatch_10() {
        assert!(wildmatch(b"[[:print:]]", b"a"));
        assert!(!wildmatch(b"[[:print:]]", b"\x01"));
    }

    #[test]
    fn test_wildmatch_11() {
        assert!(wildmatch(b"[[:punct:]]", b"!"));
        assert!(!wildmatch(b"[[:punct:]]", b"a"));
    }

    #[test]
    fn test_wildmatch_12() {
        assert!(wildmatch(b"[[:graph:]]", b"a"));
        assert!(!wildmatch(b"[[:graph:]]", b" "));
    }

    #[test]
    fn test_wildmatch_13() {
        assert!(wildmatch(b"[[:cntrl:]]", b"\x01"));
        assert!(!wildmatch(b"[[:cntrl:]]", b"a"));
    }

    #[test]
    fn test_wildmatch_14() {
        assert!(wildmatch(b"[[:blank:]]", b" "));
        assert!(wildmatch(b"[[:blank:]]", b"\t"));
        assert!(!wildmatch(b"[[:blank:]]", b"a"));
    }

    #[test]
    fn test_wildmatch_15() {
        assert!(!wildmatch(b"[[:bogus:]]", b"a"));
    }

    #[test]
    fn test_wildmatch_16() {
        assert!(wildmatch(b"[!a]", b"b"));
        assert!(!wildmatch(b"[!a]", b"a"));
    }

    #[test]
    fn test_wildmatch_17() {
        assert!(wildmatch(b"[^a]", b"b"));
        assert!(!wildmatch(b"[^a]", b"a"));
    }

    #[test]
    fn test_wildmatch_18() {
        assert!(wildmatch(b"[a-z]", b"m"));
        assert!(!wildmatch(b"[a-z]", b"M"));
    }

    #[test]
    fn test_wildmatch_19() {
        assert!(wildmatch(b"[\\a-\\z]", b"m"));
    }

    #[test]
    fn test_wildmatch_20() {
        assert!(wildmatch(b"[\\]]", b"]"));
        assert!(!wildmatch(b"[\\]]", b"a"));
    }

    #[test]
    fn test_wildmatch_21() {
        assert!(!wildmatch(b"[abc", b"a"));
    }

    #[test]
    fn test_wildmatch_22() {
        assert!(wildmatch(b"[]]", b"]"));
    }

    #[test]
    fn test_wildmatch_23() {
        assert!(!wildmatch(b"?", b"/"));
    }

    #[test]
    fn test_wildmatch_24() {
        assert!(wildmatch(b"/usr/*", b"/usr/bin"));
        assert!(!wildmatch(b"/usr/*", b"/usr/bin/bash"));
    }

    #[test]
    fn test_wildmatch_25() {
        assert!(wildmatch(b"/usr/**", b"/usr/bin/bash"));
        assert!(wildmatch(b"**", b"anything/at/all"));
    }

    #[test]
    fn test_wildmatch_26() {
        assert!(wildmatch(b"/usr/**/bash", b"/usr/bin/bash"));
        assert!(wildmatch(b"/usr/**/bash", b"/usr/bash"));
        assert!(wildmatch(b"/usr/**/bash", b"/usr/local/bin/bash"));
    }

    #[test]
    fn test_wildmatch_27() {
        assert!(wildmatch(b"/**/lib/*.so", b"/usr/lib/libc.so"));
        assert!(!wildmatch(b"/**/lib/*.so", b"/usr/lib/sub/libc.so"));
    }

    #[test]
    fn test_wildmatch_28() {
        assert!(wildmatch(b"abc*", b"abc"));
        assert!(wildmatch(b"abc**", b"abc"));
    }

    #[test]
    fn test_wildmatch_29() {
        assert!(wildmatch(b"", b""));
        assert!(!wildmatch(b"", b"a"));
        assert!(!wildmatch(b"a", b""));
    }

    #[test]
    fn test_wildmatch_30() {
        assert!(wildmatch(b"[[.a.]", b"["));
    }

    #[test]
    fn test_wildmatch_31() {
        assert!(!wildmatch(b"*", b"a/b"));
    }

    #[test]
    fn test_wildmatch_32() {
        assert!(!wildmatch(b"[abc]", b"/"));
    }

    #[test]
    fn test_wildmatch_33() {
        assert!(!wildmatch(b"a?", b"a"));
    }

    #[test]
    fn test_wildmatch_34() {
        assert!(!wildmatch(b"a\\", b"ab"));
    }

    #[test]
    fn test_wildmatch_35() {
        assert!(!wildmatch(b"*z", b"abc"));
    }

    #[test]
    fn test_wildmatch_36() {
        assert!(wildmatch(b"a/**/*", b"a/b"));
        assert!(wildmatch(b"a/**/*", b"a/b/c"));
    }

    #[test]
    fn test_wildmatch_blob() {
        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 {
                unreachable!("BUG: Fix test at line {test_cnt}: {line}!");
            }
        }

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

    // Parses a test line.
    // 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()
    }

    const GLOBINTER_CASES: &[(&[u8], &[u8], bool)] = &[
        (b"/usr/bin", b"/usr/bin", true),
        (b"/usr/bin", b"/usr/lib", false),
        (b"/usr/bin", b"/var/bin", false),
        (b"", b"", true),
        (b"", b"a", false),
        (b"/usr/*", b"/usr/bin", true),
        (b"/usr/**", b"/usr/local/bin", true),
        (b"*.so", b"/lib/libc.so", true),
        (b"*.so", b"*.txt", false),
        (b"abc*", b"abc", true),
        (b"abc*", b"abcdef", true),
        (b"abc*", b"ab", false),
        (b"a*b*c", b"a*c", true),
        (b"*", b"", true),
        (b"a?c", b"abc", true),
        (b"a?c", b"abd", false),
        (b"[abc]", b"b", true),
        (b"[abc]", b"bb", false),
        (b"[]a]", b"x", true),
        (b"[]a]", b"xy", false),
        (b"[abc", b"[abc", true),
        (b"[abc", b"abc", false),
        (b"[abc", b"xyz", false),
        (b"a/**/b", b"a/b", true),
        (b"a/**/b", b"a/x/y/b", true),
        (b"a/**/b", b"a/b/c", false),
        (b"x/**/y", b"x/z", false),
        (b"/home/*/.config", b"/home/alip/.config", true),
        (b"/home/*/.config", b"/home/alip/.cache", false),
    ];

    // Enumerate every byte string over "alphabet" with length in 0..=max_len.
    fn glob_all_strings(alphabet: &[u8], max_len: usize) -> Vec<Vec<u8>> {
        let mut strings = vec![Vec::new()];
        let mut frontier = vec![Vec::new()];
        for _ in 0..max_len {
            let mut next = Vec::new();
            for prefix in &frontier {
                for &byte in alphabet {
                    let mut candidate = prefix.clone();
                    candidate.push(byte);
                    next.push(candidate);
                }
            }
            strings.extend_from_slice(&next);
            frontier = next;
        }
        strings
    }

    // Tokenize a pattern exactly as "globinter" does.
    fn glob_token_list(pattern: &[u8]) -> Vec<Token> {
        let mut toks = Vec::new();
        let mut idx = 0;
        while idx < pattern.len() {
            let (tok, next) = glob_next_token(pattern, idx);
            toks.push(tok);
            idx = next;
        }
        toks
    }

    // Recursive glob matcher.
    fn glob_match_text(toks: &[Token], text: &[u8]) -> bool {
        match toks.split_first() {
            None => text.is_empty(),
            Some((Token::Star, rest)) => {
                glob_match_text(rest, text)
                    || (!text.is_empty() && glob_match_text(toks, &text[1..]))
            }
            Some((Token::Any, rest)) => !text.is_empty() && glob_match_text(rest, &text[1..]),
            Some((Token::Lit(byte), rest)) => {
                text.first() == Some(byte) && glob_match_text(rest, &text[1..])
            }
        }
    }

    fn globinter_check(pat_alphabet: &[u8], pat_len: usize, str_alphabet: &[u8], str_len: usize) {
        let patterns = glob_all_strings(pat_alphabet, pat_len);
        let strings = glob_all_strings(str_alphabet, str_len);

        for (i, a) in patterns.iter().enumerate() {
            for b in &patterns[i..] {
                assert_eq!(
                    globinter(a, b),
                    globinter(b, a),
                    "asymmetric: {:?} vs {:?}",
                    String::from_utf8_lossy(a),
                    String::from_utf8_lossy(b),
                );

                let common = strings.iter().any(|s| wildmatch(a, s) && wildmatch(b, s));
                if common {
                    assert!(
                        globinter(a, b),
                        "missed overlap of {:?} and {:?}",
                        String::from_utf8_lossy(a),
                        String::from_utf8_lossy(b),
                    );
                }
            }
        }
    }

    fn globinter_check2(pat_alphabet: &[u8], pat_len: usize, str_alphabet: &[u8], str_len: usize) {
        let patterns = glob_all_strings(pat_alphabet, pat_len);
        let strings = glob_all_strings(str_alphabet, str_len);

        for (i, a) in patterns.iter().enumerate() {
            for b in &patterns[i..] {
                let toks_a = glob_token_list(a);
                let toks_b = glob_token_list(b);
                let common = strings
                    .iter()
                    .any(|s| glob_match_text(&toks_a, s) && glob_match_text(&toks_b, s));
                assert_eq!(
                    globinter(a, b),
                    common,
                    "globinter disagrees with itself for {:?} and {:?}",
                    String::from_utf8_lossy(a),
                    String::from_utf8_lossy(b),
                );
            }
        }
    }

    fn globinter_check3(pat_alphabet: &[u8], pat_len: usize, str_alphabet: &[u8], str_len: usize) {
        let patterns = glob_all_strings(pat_alphabet, pat_len);
        let strings = glob_all_strings(str_alphabet, str_len);
        let methods = [MatchMethod::Literal, MatchMethod::Prefix, MatchMethod::Glob];

        for a in &patterns {
            for &a_meth in &methods {
                for b in &patterns {
                    for &b_meth in &methods {
                        let common = strings
                            .iter()
                            .any(|s| globmatch(a, s, a_meth) && globmatch(b, s, b_meth));
                        if common {
                            assert!(
                                globinter_method(a, a_meth, b, b_meth),
                                "missed overlap of {:?}/{:?} and {:?}/{:?}",
                                String::from_utf8_lossy(a),
                                a_meth,
                                String::from_utf8_lossy(b),
                                b_meth,
                            );
                        }
                        assert_eq!(
                            globinter_method(a, a_meth, b, b_meth),
                            globinter_method(b, b_meth, a, a_meth),
                            "asymmetric: {:?}/{:?} vs {:?}/{:?}",
                            String::from_utf8_lossy(a),
                            a_meth,
                            String::from_utf8_lossy(b),
                            b_meth,
                        );
                    }
                }
            }
        }
    }

    #[test]
    fn test_globinter_1() {
        for &(a, b, expected) in GLOBINTER_CASES {
            assert_eq!(
                globinter(a, b),
                expected,
                "globinter({:?}, {:?})",
                String::from_utf8_lossy(a),
                String::from_utf8_lossy(b),
            );
            assert_eq!(globinter(a, b), globinter(b, a));
        }
    }

    #[test]
    fn test_globinter_2() {
        // (pattern alphabet, string alphabet, max pattern length)
        let cases: &[(&[u8], &[u8], usize)] = &[
            (b"ab*", b"ab", 5),
            (b"a*/", b"a/", 5),
            (b"a?/", b"a/", 5),
            (b"[]a", b"a/", 5),
            (b"a*\\", b"a/", 5),
            (b"*?/", b"a/", 5),
            (b"ab*/", b"ab/", 3),
            (b"a*/\\", b"a/", 3),
            (b"a?*[", b"a/", 3),
            (b"[]\\", b"a]", 4),
            (b"[!]a", b"a/", 4),
            (b"[]:a", b"a]", 4),
            (b"[-]a", b"a-/", 4),
            (b"\\*[", b"a[*", 3),
            (b"a\\[", b"a[]", 4),
            (b"*?[]", b"a[]", 3),
            (b"a*[/", b"a[/", 3),
            (b"[]*/", b"a[/", 3),
            (b"[]?/", b"a[/", 3),
            (b"a*?[/", b"a[/", 3),
        ];

        for &(pat_alphabet, str_alphabet, max_pat) in cases {
            for pat_len in 1..=max_pat {
                for str_len in 1..=(8usize.saturating_sub(pat_len)).min(6) {
                    globinter_check(pat_alphabet, pat_len, str_alphabet, str_len);
                }
            }
        }
    }

    #[test]
    fn test_globinter_3() {
        for pat_len in 0..=2 {
            let str_len = (pat_len + 1) * (pat_len + 1) - 1;
            globinter_check2(b"ab*/?", pat_len, b"ab/", str_len);
        }
    }

    #[test]
    fn test_globinter_4() {
        use MatchMethod::{Glob, Literal, Prefix};

        // (a, a_meth, b, b_meth, intersects).
        let cases: &[(&[u8], MatchMethod, &[u8], MatchMethod, bool)] = &[
            (b"/usr/", Prefix, b"/usr/bin", Glob, true),
            (b"/usr/", Prefix, b"/var/bin", Glob, false),
            (b"/usr/", Prefix, b"/usr/", Prefix, true),
            (b"/a/b", Prefix, b"/a/b/c/d", Literal, true),
            (b"/etc/", Prefix, b"/etc/passwd", Literal, true),
            (b"/x", Prefix, b"/y", Prefix, false),
            (b"/usr", Literal, b"/usr/bin", Literal, false),
            (b"/usr", Prefix, b"/usr/bin", Literal, true),
        ];

        for &(a, a_meth, b, b_meth, expected) in cases {
            assert_eq!(
                globinter_method(a, a_meth, b, b_meth),
                expected,
                "globinter_method({:?}, {:?})",
                String::from_utf8_lossy(a),
                String::from_utf8_lossy(b),
            );
            assert_eq!(
                globinter_method(a, a_meth, b, b_meth),
                globinter_method(b, b_meth, a, a_meth),
            );
        }
    }

    #[test]
    fn test_globinter_5() {
        let long = vec![b'a'; PATH_MAX + 1];
        assert!(globinter(&long, b"b"));
        assert!(globinter(b"b", &long));
        assert!(globinter(&long, &long));
        let at_limit = vec![b'a'; PATH_MAX];
        assert!(!globinter(&at_limit, b"b"));
    }

    #[test]
    fn test_globinter_6() {
        for &(pat_alphabet, str_alphabet, max_pat) in &[
            (b"a*/" as &[u8], b"a/" as &[u8], 3usize),
            (b"[a]?" as &[u8], b"[a]" as &[u8], 3),
            (b"a?/*" as &[u8], b"a/" as &[u8], 3),
            (b"[]b" as &[u8], b"[]b" as &[u8], 4),
        ] {
            for pat_len in 1..=max_pat {
                for str_len in 1..=5 {
                    globinter_check3(pat_alphabet, pat_len, str_alphabet, str_len);
                }
            }
        }
    }

    #[test]
    fn test_globinter_7() {
        let patterns: &[&[u8]] = &[
            b"[[:digit:]]",
            b"[[:alpha:]]",
            b"[[:alnum:]]",
            b"[[:digit:]a]",
            b"[a-z]",
            b"[A-Z]",
            b"[0-9]",
            b"[!0-9]",
            b"[^a-z]",
            b"[\\]]",
            b"[][]",
            b"[-a]",
            b"[a-]",
            b"[[:bogus:]]",
            b"[[:digit:]]z",
            b"5",
            b"a",
            b"z",
            b"]",
            b"0",
            b"?",
            b"*",
            b"[abc]",
        ];
        let strings = glob_all_strings(b"a5]z0-[A", 2);

        for (i, &a) in patterns.iter().enumerate() {
            for &b in &patterns[i..] {
                let common = strings.iter().any(|s| wildmatch(a, s) && wildmatch(b, s));
                if common {
                    assert!(
                        globinter(a, b),
                        "missed overlap of {:?} and {:?}",
                        String::from_utf8_lossy(a),
                        String::from_utf8_lossy(b),
                    );
                }
                assert_eq!(
                    globinter(a, b),
                    globinter(b, a),
                    "asymmetric: {:?} vs {:?}",
                    String::from_utf8_lossy(a),
                    String::from_utf8_lossy(b),
                );
            }
        }
    }

    #[test]
    fn test_globinter_8() {
        assert!(wildmatch(b"\\*", b"*"));
        assert!(!wildmatch(b"\\*", b"abc"));
        assert!(!globinter(b"\\*", b"abc"));
    }

    #[test]
    fn test_globinter_9() {
        assert!(wildmatch(b"\\a", b"a"));
        assert!(!wildmatch(b"\\a", b"xa"));
        assert!(!globinter(b"\\a", b"xa"));
    }

    #[test]
    fn test_globinter_10() {
        assert!(wildmatch(b"\\\\", b"\\"));
        assert!(!wildmatch(b"\\\\", b"x"));
        assert!(!globinter(b"\\\\", b"x"));
    }
}