wildmatch/
lib.rs

1//! Match strings against a simple wildcard pattern.
2//! Tests a wildcard pattern `p` against an input string `s`. Returns true only when `p` matches the entirety of `s`.
3//!
4//! See also the example described on [wikipedia](https://en.wikipedia.org/wiki/Matching_wildcards) for matching wildcards.
5//!
6//! No escape characters are defined.
7//!
8//! - `?` matches exactly one occurrence of any character.
9//! - `*` matches arbitrary many (including zero) occurrences of any character.
10//!
11//! Examples matching wildcards:
12//! ``` rust
13//! # extern crate wildmatch; use wildmatch::WildMatch;
14//! assert!(WildMatch::new("cat").matches("cat"));
15//! assert!(WildMatch::new("*cat*").matches("dog_cat_dog"));
16//! assert!(WildMatch::new("c?t").matches("cat"));
17//! assert!(WildMatch::new("c?t").matches("cot"));
18//! ```
19//! Examples not matching wildcards:
20//! ``` rust
21//! # extern crate wildmatch; use wildmatch::WildMatch;
22//! assert!(!WildMatch::new("dog").matches("cat"));
23//! assert!(!WildMatch::new("*d").matches("cat"));
24//! assert!(!WildMatch::new("????").matches("cat"));
25//! assert!(!WildMatch::new("?").matches("cat"));
26//! ```
27//!
28//! You can specify custom `char` values for the single and multi-character
29//! wildcards. For example, to use `%` as the multi-character wildcard and
30//! `_` as the single-character wildcard:
31//! ```rust
32//! # extern crate wildmatch; use wildmatch::WildMatchPattern;
33//! assert!(WildMatchPattern::<'%', '_'>::new("%cat%").matches("dog_cat_dog"));
34//! ```
35
36use std::fmt;
37
38#[cfg(feature = "serde")]
39use serde::{Deserialize, Serialize};
40
41/// A wildcard matcher using `*` as the multi-character wildcard and `?` as
42/// the single-character wildcard.
43pub type WildMatch = WildMatchPattern<'*', '?'>;
44
45/// Wildcard matcher used to match strings.
46///
47/// `MULTI_WILDCARD` is the character used to represent a
48/// multiple-character wildcard (e.g., `*`), and `SINGLE_WILDCARD` is the
49/// character used to represent a single-character wildcard (e.g., `?`).
50#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
51#[derive(Debug, Clone, PartialEq, PartialOrd, Default)]
52pub struct WildMatchPattern<const MULTI_WILDCARD: char, const SINGLE_WILDCARD: char> {
53    pattern: Vec<char>,
54    case_insensitive: bool,
55}
56
57impl<const MULTI_WILDCARD: char, const SINGLE_WILDCARD: char> fmt::Display
58    for WildMatchPattern<MULTI_WILDCARD, SINGLE_WILDCARD>
59{
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        use std::fmt::Write;
62        for c in &self.pattern {
63            f.write_char(*c)?;
64        }
65        Ok(())
66    }
67}
68
69impl<const MULTI_WILDCARD: char, const SINGLE_WILDCARD: char>
70    WildMatchPattern<MULTI_WILDCARD, SINGLE_WILDCARD>
71{
72    /// Constructor with pattern which can be used for matching.
73    pub fn new(pattern: &str) -> WildMatchPattern<MULTI_WILDCARD, SINGLE_WILDCARD> {
74        let mut simplified: Vec<char> = pattern.chars().collect();
75        let mut new_len = simplified.len();
76        let mut wildcard_count = 0;
77
78        for idx in (0..simplified.len()).rev() {
79            if simplified[idx] == MULTI_WILDCARD {
80                wildcard_count += 1;
81            } else {
82                if wildcard_count > 1 {
83                    new_len -= wildcard_count - 1;
84                    simplified[idx + 1..].rotate_left(wildcard_count - 1);
85                }
86                wildcard_count = 0;
87            }
88        }
89        if wildcard_count > 1 {
90            new_len -= wildcard_count - 1;
91            simplified.rotate_left(wildcard_count - 1);
92        }
93
94        simplified.truncate(new_len);
95
96        Self {
97            pattern: simplified,
98            case_insensitive: false,
99        }
100    }
101
102    /// Constructor with pattern which can be used for matching with case-insensitive comparison.
103    pub fn new_case_insensitive(
104        pattern: &str,
105    ) -> WildMatchPattern<MULTI_WILDCARD, SINGLE_WILDCARD> {
106        let mut m = Self::new(pattern);
107        m.case_insensitive = true;
108        m
109    }
110
111    #[deprecated(since = "2.0.0", note = "use `matches` instead")]
112    pub fn is_match(&self, input: &str) -> bool {
113        self.matches(input)
114    }
115
116    /// Returns true if pattern applies to the given input string
117    pub fn matches(&self, input: &str) -> bool {
118        if self.pattern.is_empty() {
119            return input.is_empty();
120        }
121        let mut input_chars = input.chars();
122
123        let mut pattern_idx = 0;
124        if let Some(mut input_char) = input_chars.next() {
125            const NONE: usize = usize::MAX;
126            let mut start_idx = NONE;
127            let mut matched = "".chars();
128
129            loop {
130                if pattern_idx < self.pattern.len() && self.pattern[pattern_idx] == MULTI_WILDCARD {
131                    start_idx = pattern_idx;
132                    matched = input_chars.clone();
133                    pattern_idx += 1;
134                } else if pattern_idx < self.pattern.len()
135                    && (self.pattern[pattern_idx] == SINGLE_WILDCARD
136                        || self.pattern[pattern_idx] == input_char
137                        || (self.case_insensitive
138                            && self.pattern[pattern_idx].to_ascii_lowercase()
139                                == input_char.to_ascii_lowercase()))
140                {
141                    pattern_idx += 1;
142                    if let Some(next_char) = input_chars.next() {
143                        input_char = next_char;
144                    } else {
145                        break;
146                    }
147                } else if start_idx != NONE {
148                    pattern_idx = start_idx + 1;
149                    if let Some(next_char) = matched.next() {
150                        input_char = next_char;
151                    } else {
152                        break;
153                    }
154                    input_chars = matched.clone();
155                } else {
156                    return false;
157                }
158            }
159        }
160
161        while pattern_idx < self.pattern.len() && self.pattern[pattern_idx] == MULTI_WILDCARD {
162            pattern_idx += 1;
163        }
164
165        // If we have reached the end of both the pattern and the text, the pattern matches the text.
166        pattern_idx == self.pattern.len()
167    }
168
169    /// Returns the pattern string.
170    /// N.B. Consecutive multi-wildcards are simplified to a single multi-wildcard.
171    pub fn pattern(&self) -> String {
172        self.pattern.iter().collect::<String>()
173    }
174
175    /// Returns the pattern string as a slice of chars.
176    pub fn pattern_chars(&self) -> &[char] {
177        &self.pattern
178    }
179
180    /// Returns if the pattern is case-insensitive.
181    pub fn is_case_insensitive(&self) -> bool {
182        self.case_insensitive
183    }
184}
185
186impl<'a, const MULTI_WILDCARD: char, const SINGLE_WILDCARD: char> PartialEq<&'a str>
187    for WildMatchPattern<MULTI_WILDCARD, SINGLE_WILDCARD>
188{
189    fn eq(&self, &other: &&'a str) -> bool {
190        self.matches(other)
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197    use ntest::assert_false;
198    use ntest::test_case;
199    use rand::{distributions::Alphanumeric, Rng};
200
201    #[test]
202    fn is_match_random() {
203        const PATTERN_LEN: usize = 100;
204
205        for _ in 0..1_000 {
206            let mut rng = rand::thread_rng();
207            let mut pattern: String = rand::thread_rng()
208                .sample_iter(&Alphanumeric)
209                .take(PATTERN_LEN)
210                .map(char::from)
211                .collect();
212            for _ in 0..rng.gen_range(0..15) {
213                let idx = rng.gen_range(0..PATTERN_LEN);
214                pattern.replace_range(idx..idx + 1, "?")
215            }
216            for _ in 0..rng.gen_range(0..15) {
217                let idx = rng.gen_range(0..PATTERN_LEN);
218                pattern.replace_range(idx..idx + 1, "*")
219            }
220            let m = WildMatch::new(&pattern);
221            for pattern_idx in 0..rng.gen_range(0..1_000) {
222                let mut input = pattern.clone();
223                for (i, c) in pattern.chars().rev().enumerate() {
224                    let idx = pattern.len() - i - 1;
225                    if c == '?' {
226                        let rand_char: String = rand::thread_rng()
227                            .sample_iter(&Alphanumeric)
228                            .take(1)
229                            .map(char::from)
230                            .collect();
231                        input.replace_range(idx..idx + 1, &rand_char)
232                    }
233                    if c == '*' {
234                        let rand_char: String = rand::thread_rng()
235                            .sample_iter(&Alphanumeric)
236                            .take(rng.gen_range(0..15))
237                            .map(char::from)
238                            .collect();
239                        input.replace_range(idx..idx + 1, &rand_char)
240                    }
241                }
242                assert!(
243                    m.matches(&input),
244                    "Pattern ({}): {} doesn't match input: {}",
245                    pattern_idx,
246                    pattern,
247                    input
248                );
249            }
250        }
251    }
252
253    #[test_case("**")]
254    #[test_case("*")]
255    #[test_case("*?*")]
256    #[test_case("c*")]
257    #[test_case("c?*")]
258    #[test_case("???")]
259    #[test_case("c?t")]
260    #[test_case("cat")]
261    #[test_case("*cat")]
262    #[test_case("cat*")]
263    fn is_match(pattern: &str) {
264        let m = WildMatch::new(pattern);
265        assert!(m.matches("cat"));
266    }
267
268    #[test_case("CAT", "cat")]
269    #[test_case("CAT", "CAT")]
270    #[test_case("CA?", "Cat")]
271    #[test_case("C*", "cAt")]
272    #[test_case("C?*", "cAT")]
273    #[test_case("C**", "caT")]
274    fn is_match_case_insensitive(pattern: &str, input: &str) {
275        let m = WildMatch::new_case_insensitive(pattern);
276        assert!(m.matches(input));
277    }
278
279    #[test_case("*d*")]
280    #[test_case("*d")]
281    #[test_case("d*")]
282    #[test_case("*c")]
283    #[test_case("?")]
284    #[test_case("??")]
285    #[test_case("????")]
286    #[test_case("?????")]
287    #[test_case("*????")]
288    #[test_case("cats")]
289    #[test_case("cat?")]
290    #[test_case("cacat")]
291    #[test_case("cat*dog")]
292    #[test_case("CAT")]
293    fn no_match(pattern: &str) {
294        let m = WildMatch::new(pattern);
295        assert_false!(m.matches("cat"));
296    }
297
298    #[test_case("1", "")]
299    #[test_case("?", "")]
300    #[test_case("?", "11")]
301    #[test_case("*1?", "123")]
302    #[test_case("*12", "122")]
303    #[test_case("cat?", "wildcats")]
304    #[test_case("cat*", "wildcats")]
305    #[test_case("*x*", "wildcats")]
306    #[test_case("*a", "wildcats")]
307    #[test_case("", "wildcats")]
308    #[test_case(" ", "wildcats")]
309    #[test_case(" ", "\n")]
310    #[test_case(" ", "\t", name = "whitespaceMismatch")]
311    #[test_case("???", "wildcats")]
312    fn no_match_long(pattern: &str, expected: &str) {
313        let m = WildMatch::new(pattern);
314        assert_false!(m.matches(expected))
315    }
316
317    #[test_case("*", "")]
318    #[test_case("*", "1")]
319    #[test_case("?", "1")]
320    #[test_case("*121", "12121")]
321    #[test_case("?*3", "111333")]
322    #[test_case("*113", "1113")]
323    #[test_case("*113", "113")]
324    #[test_case("*113", "11113")]
325    #[test_case("*113", "111113")]
326    #[test_case("*???a", "bbbba")]
327    #[test_case("*???a", "bbbbba")]
328    #[test_case("*???a", "bbbbbba")]
329    #[test_case("*o?a*", "foobar")]
330    #[test_case("*ooo?ar", "foooobar")]
331    #[test_case("*o?a*r", "foobar")]
332    #[test_case("*cat*", "d&(*og_cat_dog")]
333    #[test_case("*?*", "d&(*og_cat_dog")]
334    #[test_case("*a*", "d&(*og_cat_dog")]
335    #[test_case("a*b", "a*xb")]
336    #[test_case("*", "*")]
337    #[test_case("*", "?")]
338    #[test_case("?", "?")]
339    #[test_case("wildcats", "wildcats")]
340    #[test_case("wild*cats", "wild?cats")]
341    #[test_case("wi*ca*s", "wildcats")]
342    #[test_case("wi*ca?s", "wildcats")]
343    #[test_case("*o?", "hog_cat_dog")]
344    #[test_case("*o?", "cat_dog")]
345    #[test_case("*at_dog", "cat_dog")]
346    #[test_case(" ", " ")]
347    #[test_case("* ", "\n ")]
348    #[test_case("\n", "\n", name = "special_chars")]
349    #[test_case("*32", "432")]
350    #[test_case("*32", "332")]
351    #[test_case("*332", "332")]
352    #[test_case("*32", "32")]
353    #[test_case("*32", "3232")]
354    #[test_case("*32", "3232332")]
355    #[test_case("*?2", "332")]
356    #[test_case("*?2", "3332")]
357    #[test_case("33*", "333")]
358    #[test_case("da*da*da*", "daaadabadmanda")]
359    #[test_case("*?", "xx")]
360    fn match_long(pattern: &str, expected: &str) {
361        let m = WildMatch::new(pattern);
362        assert!(
363            m.matches(expected),
364            "Expected pattern {} to match {}",
365            pattern,
366            expected
367        );
368    }
369
370    #[test]
371    fn complex_pattern() {
372        const TEXT: &str = "Lorem ipsum dolor sit amet, \
373        consetetur sadipscing elitr, sed diam nonumy eirmod tempor \
374        invidunt ut labore et dolore magna aliquyam erat, sed diam \
375        voluptua. At vero eos et accusam et justo duo dolores et ea \
376        rebum. Stet clita kasd gubergren, no sea takimata sanctus est \
377        Lorem ipsum dolor sit amet.";
378        const COMPLEX_PATTERN: &str = "Lorem?ipsum*dolore*ea* ?????ata*.";
379        let m = WildMatch::new(COMPLEX_PATTERN);
380        assert!(m.matches(TEXT));
381    }
382
383    #[test]
384    fn complex_pattern_alternative_wildcards() {
385        const TEXT: &str = "Lorem ipsum dolor sit amet, \
386        consetetur sadipscing elitr, sed diam nonumy eirmod tempor \
387        invidunt ut labore et dolore magna aliquyam erat, sed diam \
388        voluptua. At vero eos et accusam et justo duo dolores et ea \
389        rebum. Stet clita kasd gubergren, no sea takimata sanctus est \
390        Lorem ipsum dolor sit amet.";
391        const COMPLEX_PATTERN: &str = "Lorem_ipsum%dolore%ea% _____ata%.";
392        let m = WildMatchPattern::<'%', '_'>::new(COMPLEX_PATTERN);
393        assert!(m.matches(TEXT));
394    }
395
396    #[test]
397    fn compare_via_equal() {
398        let m = WildMatch::new("c?*");
399        assert!(m == "cat");
400        assert!(m == "car");
401        assert!(m != "dog");
402    }
403
404    #[test]
405    fn compare_empty() {
406        let m: WildMatch = WildMatch::new("");
407        assert!(m != "bar");
408        assert!(m == "");
409    }
410
411    #[test]
412    fn compare_default() {
413        let m: WildMatch = Default::default();
414        assert!(m == "");
415        assert!(m != "bar");
416    }
417
418    #[test]
419    fn compare_wild_match() {
420        assert_eq!(WildMatch::default(), WildMatch::new(""));
421        assert_eq!(WildMatch::new("abc"), WildMatch::new("abc"));
422        assert_eq!(WildMatch::new("a*bc"), WildMatch::new("a*bc"));
423        assert_ne!(WildMatch::new("abc"), WildMatch::new("a*bc"));
424        assert_ne!(WildMatch::new("a*bc"), WildMatch::new("a?bc"));
425        assert_eq!(WildMatch::new("a***c"), WildMatch::new("a*c"));
426    }
427
428    #[test]
429    fn print_string() {
430        let m = WildMatch::new("Foo/Bar");
431        assert_eq!("Foo/Bar", m.to_string());
432    }
433
434    #[test]
435    fn to_string_f() {
436        let m = WildMatch::new("F");
437        assert_eq!("F", m.to_string());
438    }
439
440    #[test]
441    fn to_string_with_star() {
442        assert_eq!("a*bc", WildMatch::new("a*bc").to_string());
443        assert_eq!("a*bc", WildMatch::new("a**bc").to_string());
444        assert_eq!("a*bc*", WildMatch::new("a*bc*").to_string());
445    }
446
447    #[test]
448    fn to_string_with_question_sign() {
449        assert_eq!("a?bc", WildMatch::new("a?bc").to_string());
450        assert_eq!("a??bc", WildMatch::new("a??bc").to_string());
451    }
452
453    #[test]
454    fn to_string_empty() {
455        let m = WildMatch::new("");
456        assert_eq!("", m.to_string());
457    }
458}
wildmatch/lib.rs

wildmatch/
lib.rs
