pub(crate) fn matches(pattern: &str, name: &str) -> bool {
let tokens = tokenize(pattern);
let name: Vec<char> = name.chars().collect();
let mut next = vec![false; name.len() + 1];
next[name.len()] = true;
let mut here = vec![false; name.len() + 1];
for token in tokens.iter().rev() {
let mut segment_from_later = false;
for j in (0..=name.len()).rev() {
let c = name.get(j).copied();
here[j] = match token {
Token::Literal(want) => c == Some(*want) && next[j + 1],
Token::One => c.is_some_and(|c| c != '/') && next[j + 1],
Token::Star => next[j] || (c.is_some_and(|c| c != '/') && here[j + 1]),
Token::Cross => next[j] || (c.is_some() && here[j + 1]),
Token::Segments => next[j] || segment_from_later,
};
if c == Some('/') {
segment_from_later |= here[j + 1];
}
}
core::mem::swap(&mut here, &mut next);
}
next[0]
}
enum Token {
Literal(char),
One,
Star,
Cross,
Segments,
}
fn tokenize(pattern: &str) -> Vec<Token> {
let mut tokens = Vec::new();
let mut chars = pattern.chars().peekable();
while let Some(c) = chars.next() {
tokens.push(match c {
'*' if chars.peek() == Some(&'*') => {
chars.next();
if chars.peek() == Some(&'/') {
chars.next();
Token::Segments
} else {
Token::Cross
}
}
'*' => Token::Star,
'?' => Token::One,
c => Token::Literal(c),
});
}
tokens
}
#[cfg(test)]
mod tests {
use super::matches;
#[test]
fn a_single_star_stays_inside_one_segment() {
assert!(matches("*.png", "logo.png"));
assert!(!matches("*.png", "sub/logo.png"));
assert!(matches("sub/*.png", "sub/logo.png"));
assert!(!matches("sub/*.png", "sub/deep/logo.png"));
}
#[test]
fn a_question_mark_is_one_character_and_never_a_separator() {
assert!(matches("a?c.txt", "abc.txt"));
assert!(!matches("a?c.txt", "ac.txt"));
assert!(!matches("a?c", "a/c"));
}
#[test]
fn a_question_mark_is_one_character_in_any_script() {
assert!(matches("?.png", "é.png"));
assert!(matches("?.png", "日.png"));
assert!(matches("?.png", "😀.png"));
assert!(!matches("??.png", "é.png"));
assert!(matches("caf?.txt", "café.txt"));
assert!(matches("*é.txt", "café.txt"));
assert!(matches("caf*", "café.txt"));
assert!(matches("**/?.png", "sub/日.png"));
}
#[test]
fn a_double_star_segment_stands_for_any_number_of_segments() {
assert!(matches("**/logo.png", "logo.png"));
assert!(matches("**/logo.png", "sub/logo.png"));
assert!(matches("**/logo.png", "a/b/c/logo.png"));
assert!(matches("**/*.png", "a/b/logo.png"));
assert!(!matches("**/*.png", "a/b/logo.jpg"));
}
#[test]
fn a_double_star_matches_in_the_middle_and_at_the_end() {
assert!(matches("a/**/b.txt", "a/b.txt"));
assert!(matches("a/**/b.txt", "a/x/b.txt"));
assert!(matches("a/**/b.txt", "a/x/y/b.txt"));
assert!(!matches("a/**/b.txt", "z/x/b.txt"));
assert!(matches("a/**", "a/b.txt"));
assert!(matches("a/**", "a/x/y/b.txt"));
assert!(!matches("a/**", "a"));
}
#[test]
fn a_bare_double_star_takes_everything() {
assert!(matches("**", "a.txt"));
assert!(matches("**", "a/b/c.txt"));
}
#[test]
fn a_double_star_not_on_a_segment_boundary_is_a_star_that_crosses() {
assert!(matches("a**z", "abz"));
assert!(matches("a**z", "ab/cz"));
assert!(!matches("a*z", "ab/cz"));
}
#[test]
fn a_run_of_wildcards_does_not_take_exponential_time() {
let pattern = "*".repeat(40) + "x";
let name = "a".repeat(60);
assert!(!matches(&pattern, &name));
let pattern = "**/".repeat(20) + "?*x";
let name = "a/".repeat(30) + "b";
assert!(!matches(&pattern, &name));
assert!(matches(&("*".repeat(40) + "x"), &("a".repeat(60) + "x")));
}
#[test]
fn a_pattern_matches_nothing_it_does_not_cover() {
assert!(!matches("", "a"));
assert!(matches("", ""));
assert!(!matches("a.txt", "a.txtx"));
assert!(!matches("a.txt", "xa.txt"));
}
}