#[must_use]
pub(crate) fn matches(pattern: &str, path: &str) -> bool {
starred(Glob::of(pattern), Segments(Some(path)))
}
#[derive(Clone, Copy)]
struct Glob<'a> {
lead: bool,
core: Segments<'a>,
tail: bool,
}
impl<'a> Glob<'a> {
fn of(pattern: &'a str) -> Self {
let anchored = pattern.starts_with('/');
let trimmed = pattern.trim_start_matches('/');
let core = trimmed.trim_end_matches('/');
Self {
lead: !anchored && !core.contains('/'),
core: Segments(Some(core)),
tail: trimmed.ends_with('/'),
}
}
}
trait Units: Copy {
type Unit;
fn split(self) -> Option<(Self::Unit, Self)>;
}
trait Wildcard: Units {
type Text: Units;
fn is_star(unit: &Self::Unit) -> bool;
fn accepts(unit: &Self::Unit, text: &<Self::Text as Units>::Unit) -> bool;
}
#[derive(Clone, Copy)]
struct Chars<'a>(&'a str);
#[derive(Clone, Copy)]
struct Segments<'a>(Option<&'a str>);
impl Units for Chars<'_> {
type Unit = char;
fn split(self) -> Option<(char, Self)> {
let mut chars = self.0.chars();
let first = chars.next()?;
Some((first, Self(chars.as_str())))
}
}
impl<'a> Units for Segments<'a> {
type Unit = &'a str;
fn split(self) -> Option<(&'a str, Self)> {
let rest = self.0?;
Some(match rest.split_once('/') {
Some((head, tail)) => (head, Self(Some(tail))),
None => (rest, Self(None)),
})
}
}
impl<'a> Units for Glob<'a> {
type Unit = &'a str;
fn split(self) -> Option<(&'a str, Self)> {
if self.lead {
let rest = Self {
lead: false,
..self
};
return Some(("**", rest));
}
if let Some((unit, core)) = self.core.split() {
return Some((unit, Self { core, ..self }));
}
let rest = Self {
tail: false,
..self
};
self.tail.then_some(("**", rest))
}
}
impl Wildcard for Chars<'_> {
type Text = Self;
fn is_star(unit: &char) -> bool {
*unit == '*'
}
fn accepts(unit: &char, text: &char) -> bool {
*unit == '?' || unit == text
}
}
impl<'a> Wildcard for Glob<'a> {
type Text = Segments<'a>;
fn is_star(unit: &&str) -> bool {
*unit == "**"
}
fn accepts(unit: &&str, text: &&str) -> bool {
starred(Chars(unit), Chars(text))
}
}
enum Step<P, T> {
Star(P),
Took(P, T),
Done,
Stuck,
}
fn step<P: Wildcard>(pattern: P, text: P::Text) -> Step<P, P::Text> {
match (pattern.split(), text.split()) {
(Some((unit, after)), _) if P::is_star(&unit) => Step::Star(after),
(None, None) => Step::Done,
(Some((unit, after)), Some((got, rest))) if P::accepts(&unit, &got) => {
Step::Took(after, rest)
}
_ => Step::Stuck,
}
}
fn retry<P: Units, T: Units>(star: Option<(P, T)>) -> Option<(P, T)> {
let (after, mark) = star?;
let (_, rest) = mark.split()?;
Some((after, rest))
}
fn starred<P: Wildcard>(pattern: P, text: P::Text) -> bool {
let mut at = (pattern, text);
let mut star = None;
loop {
match step(at.0, at.1) {
Step::Star(after) => (star, at.0) = (Some((after, at.1)), after),
Step::Took(after, rest) => at = (after, rest),
Step::Done => return true,
Step::Stuck => match retry(star) {
Some(resume) => (star, at) = (Some(resume), resume),
None => return false,
},
}
}
}
#[cfg(test)]
mod tests {
use super::matches;
#[test]
fn a_pattern_with_no_slash_matches_at_any_depth() {
assert!(matches("*.md", "README.md"));
assert!(matches("*.md", "docs/guide.md"));
assert!(matches("*.md", "a/b/c/deep.md"));
assert!(!matches("*.md", "docs/guide.txt"));
}
#[test]
fn a_leading_slash_anchors_to_the_root() {
assert!(matches("/README.md", "README.md"));
assert!(!matches("/README.md", "docs/README.md"));
}
#[test]
fn a_pattern_with_an_inner_slash_is_already_anchored() {
assert!(matches("docs/*.md", "docs/guide.md"));
assert!(!matches("docs/*.md", "src/docs/guide.md"));
}
#[test]
fn a_trailing_slash_names_a_directory_and_all_under_it() {
assert!(matches("locales/", "locales/pl.yml"));
assert!(matches("locales/", "app/locales/pl.yml"));
assert!(!matches("locales/", "locales.yml"));
}
#[test]
fn a_star_never_crosses_a_separator() {
assert!(matches("src/*.rs", "src/main.rs"));
assert!(!matches("src/*.rs", "src/rules/glob.rs"));
assert!(matches("src/*", "src/rules"));
assert!(!matches("src/*", "src/rules/glob.rs"));
}
#[test]
fn a_double_star_crosses_segments_including_none() {
assert!(matches("src/**/*.rs", "src/rules/glob.rs"));
assert!(matches("src/**/*.rs", "src/main.rs"));
assert!(!matches("src/**/*.rs", "tests/a.rs"));
}
#[test]
fn a_question_mark_is_exactly_one_character() {
assert!(matches("a?.rs", "ab.rs"));
assert!(!matches("a?.rs", "abc.rs"));
assert!(!matches("a?.rs", "a.rs"));
assert!(!matches("a?c", "a/c"));
}
#[test]
fn a_literal_pattern_is_an_exact_path() {
assert!(matches("SPEC.md", "SPEC.md"));
assert!(matches("src/rules/SPEC.md", "src/rules/SPEC.md"));
assert!(!matches("src/rules/SPEC.md", "src/scan/SPEC.md"));
}
#[test]
fn no_pattern_is_invalid() {
assert!(matches("a[b.rs", "a[b.rs"));
assert!(matches("", ""));
assert!(!matches("", "a"));
}
}
#[cfg(test)]
#[path = "glob_test.rs"]
mod differential;