relay_pattern/
lib.rs

1//! A glob like pattern used throught Relay and its APIs.
2//!
3//! # Behaviour
4//!
5//! A pattern is similar to a glob but without support for brace expansions and without any support
6//! for filesystem specific behaviour like platform dependent separators and file extension
7//! matching.
8//!
9//! By default a [`Pattern`] does not support any separator characters.
10//! For example `*` usually only matches up to the next path separator (often platform dependent),
11//! in a [`Pattern`] `*` matches all characters. Optional support for a single separator character
12//! is available.
13//!
14//! The empty glob `""` never matches.
15//!
16//! # Syntax
17//!
18//! Basic glob like syntax is supported with Unix style negations.
19//!
20//! * `?` matches any single character.
21//! * `*` matches any number of any characters, including none.
22//! * `[abc]` matches one character in the given bracket.
23//! * `[!abc]` matches one character that is not in the given bracket.
24//! * `[a-z]` matches one character in the given range.
25//! * `[!a-z]` matches one character that is not in the given range.
26//! * `{a,b}` matches any pattern within the alternation group.
27//! * `\` escapes any of the above special characters and treats it as a literal.
28//!
29//! # Complexity
30//!
31//! Patterns can be limited to a maximum complexity using [`PatternBuilder::max_complexity`].
32//! Complexity of a pattern is calculated by the amount of possible combinations created with
33//! alternations.
34//!
35//! For example, the pattern `{foo,bar}` has a complexity of 2, the pattern `{foo,bar}/{*.html,*.js,*.css}`
36//! has a complexity of `2 * 3`.
37//!
38//! For untrusted user input it is highly recommended to limit the maximum complexity.
39
40use std::fmt::{self, Write};
41use std::num::NonZeroUsize;
42
43mod typed;
44mod wildmatch;
45
46pub use typed::*;
47
48/// Pattern parsing error.
49#[derive(Debug)]
50pub struct Error {
51    pattern: String,
52    kind: ErrorKind,
53}
54
55#[derive(Debug)]
56enum ErrorKind {
57    /// The specified range is invalid. The `end` character is lexicographically
58    /// after the `start` character.
59    InvalidRange(char, char),
60    /// Unbalanced character class. The pattern contains unbalanced `[`, `]` characters.
61    UnbalancedCharacterClass,
62    /// Character class is invalid and cannot be parsed.
63    InvalidCharacterClass,
64    /// Nested alternates are not valid.
65    NestedAlternates,
66    /// Unbalanced alternates. The pattern contains unbalanced `{`, `}` characters.
67    UnbalancedAlternates,
68    /// Dangling escape character.
69    DanglingEscape,
70    /// The pattern's complexity exceeds the maximum allowed complexity.
71    Complexity {
72        complexity: u64,
73        max_complexity: u64,
74    },
75}
76
77impl std::error::Error for Error {}
78
79impl fmt::Display for Error {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        write!(f, "Error parsing pattern '{}': ", self.pattern)?;
82        match &self.kind {
83            ErrorKind::InvalidRange(start, end) => {
84                write!(f, "Invalid character range `{start}-{end}`")
85            }
86            ErrorKind::UnbalancedCharacterClass => write!(f, "Unbalanced character class"),
87            ErrorKind::InvalidCharacterClass => write!(f, "Invalid character class"),
88            ErrorKind::NestedAlternates => write!(f, "Nested alternates"),
89            ErrorKind::UnbalancedAlternates => write!(f, "Unbalanced alternates"),
90            ErrorKind::DanglingEscape => write!(f, "Dangling escape"),
91            ErrorKind::Complexity {
92                complexity,
93                max_complexity,
94            } => write!(
95                f,
96                "Pattern complexity ({complexity}) exceeds maximum allowed complexity ({max_complexity})"
97            ),
98        }
99    }
100}
101
102/// `Pattern` represents a successfully parsed Relay pattern.
103///
104/// A pattern can be parsed/de-serialized from a string, serializing a pattern again may not produce
105/// the same original pattern but a normalized variant of the pattern.
106///
107/// ```
108/// # use relay_pattern::Pattern;
109/// let pattern = Pattern::builder("Foo**").case_insensitive(true).build().unwrap();
110/// assert_eq!(&pattern.to_string(), "foo*");
111/// ```
112///
113/// Patterns can be compared with other patterns, a pattern is considered equal with another pattern
114/// if its parsed and normalized forms and options are the same. Two patterns with the same options
115/// but built from different strings may compare equal if their normalized forms are the same.
116///
117/// ```
118/// # use relay_pattern::Pattern;
119/// let pattern1 = Pattern::builder("Foo**").case_insensitive(true).build().unwrap();
120/// let pattern2 = Pattern::builder("foo*").case_insensitive(true).build().unwrap();
121/// assert_eq!(&pattern1, &pattern2);
122/// # assert_eq!(&pattern2, &pattern1);
123///
124/// let pattern1 = Pattern::builder("Foo**").case_insensitive(true).build().unwrap();
125/// let pattern2 = Pattern::builder("foo*").case_insensitive(false).build().unwrap();
126/// assert_ne!(&pattern1, &pattern2);
127/// # assert_ne!(&pattern2, &pattern1);
128/// ```
129#[derive(Clone, PartialEq, Eq)]
130pub struct Pattern {
131    options: Options,
132    strategy: MatchStrategy,
133}
134
135impl Pattern {
136    /// Create a new [`Pattern`] from a string with the default settings.
137    pub fn new(pattern: &str) -> Result<Self, Error> {
138        Self::builder(pattern).build()
139    }
140
141    /// Create a new [`PatternBuilder`]. The builder can be used to adjust the
142    /// pattern settings.
143    pub fn builder(pattern: &str) -> PatternBuilder<'_> {
144        PatternBuilder {
145            pattern,
146            options: Options::default(),
147            max_complexity: u64::MAX,
148        }
149    }
150
151    /// Returns `true` if the pattern matches the passed string.
152    pub fn is_match(&self, haystack: &str) -> bool {
153        self.strategy.is_match(haystack, self.options)
154    }
155}
156
157impl fmt::Debug for Pattern {
158    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
159        f.debug_struct("Pattern")
160            .field("<pattern>", &self.to_string())
161            .field("options", &self.options)
162            .field("strategy", &self.strategy)
163            .finish()
164    }
165}
166
167impl fmt::Display for Pattern {
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        self.strategy.fmt(f)
170    }
171}
172
173#[cfg(feature = "serde")]
174impl serde::Serialize for Pattern {
175    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
176    where
177        S: serde::Serializer,
178    {
179        serializer.collect_str(&self)
180    }
181}
182
183#[cfg(feature = "serde")]
184impl<'de> serde::Deserialize<'de> for Pattern {
185    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
186    where
187        D: serde::Deserializer<'de>,
188    {
189        let pattern = String::deserialize(deserializer)?;
190        Pattern::new(&pattern).map_err(serde::de::Error::custom)
191    }
192}
193
194/// A collection of [`Pattern`]s sharing the same configuration.
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub struct Patterns {
197    strategies: Box<[MatchStrategy]>,
198    options: Options,
199}
200
201impl Patterns {
202    /// Creates an empty [`Patterns`] instance which never matches anything.
203    ///
204    /// ```
205    /// # use relay_pattern::Patterns;
206    /// let patterns = Patterns::empty();
207    ///
208    /// assert!(!patterns.is_match(""));
209    /// assert!(!patterns.is_match("foobar"));
210    /// ```
211    pub fn empty() -> Self {
212        Self {
213            strategies: Default::default(),
214            options: Options::default(),
215        }
216    }
217
218    /// Returns a [`PatternsBuilder`].
219    pub fn builder() -> PatternsBuilder {
220        PatternsBuilder {
221            options: Options::default(),
222        }
223    }
224
225    /// Returns `true` if any of the contained patterns matches the passed string.
226    pub fn is_match(&self, haystack: &str) -> bool {
227        self.strategies
228            .iter()
229            .any(|s| s.is_match(haystack, self.options))
230    }
231
232    /// Returns `true` if this instance contains no patterns.
233    ///
234    /// An empty [`Patterns`] never matches any input.
235    pub fn is_empty(&self) -> bool {
236        self.strategies.is_empty()
237    }
238}
239
240#[cfg(feature = "serde")]
241impl serde::Serialize for Patterns {
242    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
243    where
244        S: serde::Serializer,
245    {
246        struct AsDisplay<'a>(&'a MatchStrategy);
247        impl serde::Serialize for AsDisplay<'_> {
248            fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
249                serializer.collect_str(self.0)
250            }
251        }
252
253        serializer.collect_seq(self.strategies.iter().map(AsDisplay))
254    }
255}
256
257#[cfg(feature = "serde")]
258impl<'de> serde::Deserialize<'de> for Patterns {
259    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
260    where
261        D: serde::Deserializer<'de>,
262    {
263        struct Visitor;
264
265        impl<'de> serde::de::Visitor<'de> for Visitor {
266            type Value = Patterns;
267
268            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
269                formatter.write_str("a sequence of patterns")
270            }
271
272            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
273            where
274                A: serde::de::SeqAccess<'de>,
275            {
276                let mut builder = Patterns::builder().patterns();
277                while let Some(pattern) = seq.next_element::<std::borrow::Cow<'_, str>>()? {
278                    builder.add(&pattern).map_err(serde::de::Error::custom)?;
279                }
280                Ok(builder.build())
281            }
282        }
283
284        deserializer.deserialize_seq(Visitor)
285    }
286}
287
288/// A builder for a [`Pattern`].
289#[derive(Debug)]
290pub struct PatternBuilder<'a> {
291    pattern: &'a str,
292    max_complexity: u64,
293    options: Options,
294}
295
296impl PatternBuilder<'_> {
297    /// If enabled matches the pattern case insensitive.
298    ///
299    /// This is disabled by default.
300    pub fn case_insensitive(&mut self, enabled: bool) -> &mut Self {
301        self.options.case_insensitive = enabled;
302        self
303    }
304
305    /// Sets the max complexity for this pattern.
306    ///
307    /// Attempting to build a pattern with a complexity higher
308    /// than the maximum specified here will fail.
309    ///
310    /// Complexity is a constraint enforced when building a pattern,
311    /// it does not change [`PartialEq`] and [`Eq`] comparisons.
312    ///
313    /// Defaults to `u64::MAX`.
314    pub fn max_complexity(&mut self, max_complexity: u64) -> &mut Self {
315        self.max_complexity = max_complexity;
316        self
317    }
318
319    /// Build a new [`Pattern`] from the passed pattern and configured options.
320    pub fn build(&self) -> Result<Pattern, Error> {
321        let mut parser = Parser::new(self.pattern, self.options);
322        parser.parse().map_err(|kind| Error {
323            pattern: self.pattern.to_owned(),
324            kind,
325        })?;
326
327        if parser.complexity > self.max_complexity {
328            return Err(Error {
329                pattern: self.pattern.to_owned(),
330                kind: ErrorKind::Complexity {
331                    complexity: parser.complexity,
332                    max_complexity: self.max_complexity,
333                },
334            });
335        }
336
337        let strategy =
338            MatchStrategy::from_tokens(parser.tokens, self.options).map_err(|kind| Error {
339                pattern: self.pattern.to_owned(),
340                kind,
341            })?;
342
343        Ok(Pattern {
344            options: self.options,
345            strategy,
346        })
347    }
348}
349
350/// A builder for a collection of [`Patterns`].
351#[derive(Debug)]
352pub struct PatternsBuilder {
353    options: Options,
354}
355
356impl PatternsBuilder {
357    /// If enabled matches the pattern case insensitive.
358    ///
359    /// This is disabled by default.
360    pub fn case_insensitive(&mut self, enabled: bool) -> &mut Self {
361        self.options.case_insensitive = enabled;
362        self
363    }
364
365    /// Returns a [`PatternsBuilderConfigured`] builder which allows adding patterns.
366    pub fn patterns(&mut self) -> PatternsBuilderConfigured {
367        PatternsBuilderConfigured {
368            strategies: Vec::new(),
369            options: self.options,
370        }
371    }
372
373    /// Adds a pattern to the builder and returns the resulting [`PatternsBuilderConfigured`].
374    pub fn add(&mut self, pattern: &str) -> Result<PatternsBuilderConfigured, Error> {
375        let mut builder = PatternsBuilderConfigured {
376            strategies: Vec::with_capacity(1),
377            options: self.options,
378        };
379        builder.add(pattern)?;
380        Ok(builder)
381    }
382}
383
384/// A [`PatternsBuilder`] with all options configured.
385///
386/// The second step after [`PatternsBuilder`].
387#[derive(Debug)]
388pub struct PatternsBuilderConfigured {
389    strategies: Vec<MatchStrategy>,
390    options: Options,
391}
392
393impl PatternsBuilderConfigured {
394    /// Adds a pattern to the builder.
395    pub fn add(&mut self, pattern: &str) -> Result<&mut Self, Error> {
396        let mut parser = Parser::new(pattern, self.options);
397        parser.parse().map_err(|kind| Error {
398            pattern: pattern.to_owned(),
399            kind,
400        })?;
401
402        let strategy =
403            MatchStrategy::from_tokens(parser.tokens, self.options).map_err(|kind| Error {
404                pattern: pattern.to_owned(),
405                kind,
406            })?;
407
408        self.strategies.push(strategy);
409
410        Ok(self)
411    }
412
413    /// Builds a [`Patterns`] from the contained patterns.
414    pub fn build(self) -> Patterns {
415        Patterns {
416            strategies: self.strategies.into_boxed_slice(),
417            options: self.options,
418        }
419    }
420
421    /// Returns [`Patterns`] containing all added patterns and removes them from the builder.
422    ///
423    /// The builder can still be used afterwards, it keeps the configuration.
424    pub fn take(&mut self) -> Patterns {
425        Patterns {
426            strategies: std::mem::take(&mut self.strategies).into_boxed_slice(),
427            options: self.options,
428        }
429    }
430}
431
432/// Options to influence [`Pattern`] matching behaviour.
433#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
434struct Options {
435    case_insensitive: bool,
436}
437
438/// Matching strategy for a [`Pattern`].
439///
440/// Certain patterns can be matched more efficiently while the complex
441/// patterns fallback to [`wildmatch::is_match`].
442#[derive(Debug, Clone, PartialEq, Eq)]
443enum MatchStrategy {
444    /// The pattern is a single literal string.
445    ///
446    /// The stored string is converted to lowercase for case insensitive patterns.
447    ///
448    /// Example pattern: `foobar`.
449    Literal(Literal),
450    /// The pattern only has a single wildcard in the end and can be
451    /// matched with a simple prefix check.
452    ///
453    /// The stored string is converted to lowercase for case insensitive patterns.
454    ///
455    /// Example pattern: `foobar*`.
456    Prefix(Literal),
457    /// The pattern only has a single wildcard at the start and can be
458    /// matched with a simple suffix check.
459    ///
460    /// The stored string is converted to lowercase for case insensitive patterns.
461    ///
462    /// Example pattern: `*foobar`.
463    Suffix(Literal),
464    /// The pattern is surrounded with wildcards and contains a literal in the middle
465    /// and can be matched with a simple contains check.
466    ///
467    /// The stored string is converted to lowercase for case insensitive patterns.
468    ///
469    /// Example pattern: `*foobar*`.
470    Contains(Literal),
471    /// The pattern always evaluates to a static boolean.
472    ///
473    /// Example: `*`
474    Static(bool),
475    /// The pattern is complex and needs to be evaluated using [`wildmatch`].
476    Wildmatch(Tokens),
477    // Possible future optimizations for `Any` variations:
478    // Examples: `??`. `??suffix`, `prefix??` and `?contains?`.
479}
480
481impl MatchStrategy {
482    /// Create a [`MatchStrategy`] from [`Tokens`].
483    fn from_tokens(mut tokens: Tokens, _options: Options) -> Result<Self, ErrorKind> {
484        let s = match tokens.as_mut_slice() {
485            [] => Self::Static(false),
486            [Token::Wildcard] => Self::Static(true),
487            [Token::Literal(literal)] => Self::Literal(std::mem::take(literal)),
488            [Token::Literal(literal), Token::Wildcard] => Self::Prefix(std::mem::take(literal)),
489            [Token::Wildcard, Token::Literal(literal)] => Self::Suffix(std::mem::take(literal)),
490            [Token::Wildcard, Token::Literal(literal), Token::Wildcard] => {
491                Self::Contains(std::mem::take(literal))
492            }
493            _ => Self::Wildmatch(tokens),
494        };
495
496        Ok(s)
497    }
498
499    /// Returns `true` if the pattern matches the passed string.
500    pub fn is_match(&self, haystack: &str, options: Options) -> bool {
501        match &self {
502            MatchStrategy::Literal(literal) => match_literal(literal, haystack, options),
503            MatchStrategy::Prefix(prefix) => match_prefix(prefix, haystack, options),
504            MatchStrategy::Suffix(suffix) => match_suffix(suffix, haystack, options),
505            MatchStrategy::Contains(contains) => match_contains(contains, haystack, options),
506            MatchStrategy::Static(matches) => *matches,
507            MatchStrategy::Wildmatch(tokens) => wildmatch::is_match(haystack, tokens, options),
508        }
509    }
510}
511
512impl fmt::Display for MatchStrategy {
513    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
514        match self {
515            MatchStrategy::Literal(literal) => literal.fmt(f),
516            MatchStrategy::Prefix(literal) => {
517                literal.fmt(f)?;
518                f.write_char('*')
519            }
520            MatchStrategy::Suffix(literal) => {
521                f.write_char('*')?;
522                literal.fmt(f)
523            }
524            MatchStrategy::Contains(literal) => {
525                f.write_char('*')?;
526                literal.fmt(f)?;
527                f.write_char('*')
528            }
529            MatchStrategy::Static(true) => f.write_char('*'),
530            // This is the empty glob, which never matches.
531            MatchStrategy::Static(false) => Ok(()),
532            MatchStrategy::Wildmatch(tokens) => tokens.fmt(f),
533        }
534    }
535}
536
537#[inline(always)]
538fn match_literal(literal: &Literal, haystack: &str, options: Options) -> bool {
539    if options.case_insensitive {
540        // Can't do an explicit len compare first here `literal.len() == haystack.len()`,
541        // the amount of characters can change when converting case.
542        //
543        // The literal matches if the prefix match consumes the entire haystack.
544        wildmatch::is_prefix_case_insensitive(haystack, literal)
545            .is_some_and(|len| len == haystack.len())
546    } else {
547        literal.as_case_converted_str() == haystack
548    }
549}
550
551#[inline(always)]
552fn match_prefix(prefix: &Literal, haystack: &str, options: Options) -> bool {
553    if options.case_insensitive {
554        wildmatch::is_prefix_case_insensitive(haystack, prefix).is_some()
555    } else {
556        haystack.starts_with(prefix.as_case_converted_str())
557    }
558}
559
560#[inline(always)]
561fn match_suffix(suffix: &Literal, haystack: &str, options: Options) -> bool {
562    if options.case_insensitive {
563        let mut suffix = suffix.as_case_converted_str().chars().rev();
564        let mut haystack = haystack.chars().flat_map(|c| c.to_lowercase()).rev();
565
566        loop {
567            match (suffix.next(), haystack.next()) {
568                // If the prefix is exhausted it matched.
569                (None, _) => break true,
570                // If the haystack is exhausted, but the pattern is not -> no match.
571                (Some(_), None) => break false,
572                (Some(s), Some(h)) if s != h => break false,
573                _ => {}
574            }
575        }
576    } else {
577        haystack.ends_with(suffix.as_case_converted_str())
578    }
579}
580
581#[inline(always)]
582fn match_contains(contains: &Literal, haystack: &str, options: Options) -> bool {
583    if options.case_insensitive {
584        let haystack = haystack.to_lowercase();
585        memchr::memmem::find(haystack.as_bytes(), contains.as_case_converted_bytes()).is_some()
586    } else {
587        memchr::memmem::find(haystack.as_bytes(), contains.as_case_converted_bytes()).is_some()
588    }
589}
590
591struct Parser<'a> {
592    chars: std::iter::Peekable<std::str::Chars<'a>>,
593    tokens: Tokens,
594    alternates: Option<Vec<Tokens>>,
595    current_literal: Option<String>,
596    options: Options,
597    complexity: u64,
598}
599
600impl<'a> Parser<'a> {
601    fn new(pattern: &'a str, options: Options) -> Self {
602        Self {
603            chars: pattern.chars().peekable(),
604            tokens: Default::default(),
605            alternates: None,
606            current_literal: None,
607            options,
608            complexity: 0,
609        }
610    }
611
612    fn parse(&mut self) -> Result<(), ErrorKind> {
613        while let Some(c) = self.advance() {
614            match c {
615                '?' => self.push_token(Token::Any(NonZeroUsize::MIN)),
616                '*' => self.push_token(Token::Wildcard),
617                '[' => self.parse_class()?,
618                ']' => return Err(ErrorKind::UnbalancedCharacterClass),
619                '{' => self.start_alternates()?,
620                '}' => self.end_alternates()?,
621                '\\' => match self.advance() {
622                    Some(c) => self.push_literal(c),
623                    None => return Err(ErrorKind::DanglingEscape),
624                },
625                ',' if self.alternates.is_some() => {
626                    self.finish_literal();
627                    // safe to unwrap, we just checked for `some`.
628                    let alternates = self.alternates.as_mut().unwrap();
629                    alternates.push(Tokens::default());
630                }
631                c => self.push_literal(c),
632            }
633        }
634
635        // Finish off the parsing with creating a token for any remaining literal buffered.
636        self.finish_literal();
637
638        Ok(())
639    }
640
641    fn start_alternates(&mut self) -> Result<(), ErrorKind> {
642        if self.alternates.is_some() {
643            return Err(ErrorKind::NestedAlternates);
644        }
645        self.finish_literal();
646        self.alternates = Some(vec![Tokens::default()]);
647        Ok(())
648    }
649
650    fn end_alternates(&mut self) -> Result<(), ErrorKind> {
651        self.finish_literal();
652        match self.alternates.take() {
653            None => return Err(ErrorKind::UnbalancedAlternates),
654            Some(alternates) => {
655                if !alternates.is_empty() {
656                    self.complexity = self
657                        .complexity
658                        .max(1)
659                        .saturating_mul(alternates.len() as u64);
660                    self.push_token(Token::Alternates(alternates));
661                }
662            }
663        }
664
665        Ok(())
666    }
667
668    fn parse_class(&mut self) -> Result<(), ErrorKind> {
669        let negated = self.advance_if(|c| c == '!');
670
671        let mut ranges = Ranges::default();
672
673        let mut first = true;
674        let mut in_range = false;
675        loop {
676            let Some(c) = self.advance() else {
677                return Err(ErrorKind::UnbalancedCharacterClass);
678            };
679
680            match c {
681                // Another opening bracket is invalid, literal `[` need to be escaped.
682                '[' => return Err(ErrorKind::InvalidCharacterClass),
683                ']' => break,
684                '-' => {
685                    if first {
686                        ranges.push(Range::single('-'));
687                    } else if in_range {
688                        // safe to unwrap, `in_range` is only true if there is already
689                        // a range pushed.
690                        ranges.last_mut().unwrap().set_end('-')?;
691                        in_range = false;
692                    } else {
693                        assert!(!ranges.is_empty());
694                        in_range = true;
695                    }
696                }
697                c => {
698                    let c = match c {
699                        '\\' => self.advance().ok_or(ErrorKind::DanglingEscape)?,
700                        c => c,
701                    };
702
703                    if in_range {
704                        // safe to unwrap, `in_range` is only true if there is already
705                        // a range pushed.
706                        ranges.last_mut().unwrap().set_end(c)?;
707                        in_range = false;
708                    } else {
709                        ranges.push(Range::single(c))
710                    }
711                }
712            }
713
714            first = false;
715        }
716
717        if in_range {
718            // A pattern which ends with a `-`.
719            ranges.push(Range::single('-'));
720        }
721
722        self.push_token(Token::Class { negated, ranges });
723
724        Ok(())
725    }
726
727    /// Pushes a new character into the currently active literal token.
728    ///
729    /// Starts a new literal token if there is none already.
730    fn push_literal(&mut self, c: char) {
731        self.current_literal.get_or_insert_with(String::new).push(c);
732    }
733
734    /// Finishes and pushes the currently in progress literal token.
735    fn finish_literal(&mut self) {
736        if let Some(literal) = self.current_literal.take() {
737            self.push_token(Token::Literal(Literal::new(literal, self.options)));
738        }
739    }
740
741    /// Pushes the passed `token` and finishes the currently in progress literal token.
742    fn push_token(&mut self, token: Token) {
743        self.finish_literal();
744        match self.alternates.as_mut() {
745            Some(alternates) => match alternates.last_mut() {
746                Some(tokens) => tokens.push(token),
747                None => {
748                    let mut tokens = Tokens::default();
749                    tokens.push(token);
750                    alternates.push(tokens);
751                }
752            },
753            None => self.tokens.push(token),
754        }
755    }
756
757    fn advance(&mut self) -> Option<char> {
758        self.chars.next()
759    }
760
761    fn advance_if(&mut self, matcher: impl FnOnce(char) -> bool) -> bool {
762        if self.peek().is_some_and(matcher) {
763            let _ = self.advance();
764            true
765        } else {
766            false
767        }
768    }
769
770    fn peek(&mut self) -> Option<char> {
771        self.chars.peek().copied()
772    }
773}
774
775/// A container of tokens.
776///
777/// Automatically folds redundant tokens.
778///
779/// The contained tokens are guaranteed to uphold the following invariants:
780/// - A [`Token::Wildcard`] is never followed by [`Token::Wildcard`].
781/// - A [`Token::Any`] is never followed by [`Token::Any`].
782/// - A [`Token::Literal`] is never followed by [`Token::Literal`].
783/// - A [`Token::Class`] is never empty.
784#[derive(Clone, Debug, Default, PartialEq, Eq)]
785struct Tokens(Vec<Token>);
786
787impl Tokens {
788    fn push(&mut self, mut token: Token) {
789        // Normalize / clean the token.
790        if let Token::Alternates(mut alternates) = token {
791            let mut contains_empty = false;
792            let mut contains_wildcard = false;
793            alternates.retain_mut(|alternate| {
794                if alternate.0.is_empty() {
795                    contains_empty = true;
796                    return false;
797                }
798
799                if matches!(alternate.0.as_slice(), [Token::Wildcard]) {
800                    contains_wildcard = true;
801                }
802
803                true
804            });
805
806            // At this point `alternates` contains only the nonempty branches
807            // and we additionally know
808            // * if one of the branches was just a wildcard
809            // * if there were any empty branches.
810            //
811            // We can push different tokens based on this.
812            if contains_wildcard {
813                // Case: {foo,*,} -> reduces to *
814                token = Token::Wildcard;
815            } else if alternates.len() == 1 {
816                if contains_empty {
817                    // Case: {foo*bar,} -> Optional(foo*bar)
818                    token = Token::Optional(alternates.remove(0));
819                } else {
820                    // Case: {foo*bar} -> remove the alternation and
821                    // push foo*bar directly
822                    for t in alternates.remove(0).0 {
823                        self.push(t);
824                    }
825                    return;
826                }
827            } else if alternates.len() > 1 {
828                if contains_empty {
829                    // Case: {foo,bar,} -> Optional({foo,bar})
830                    token = Token::OptionalAlternates(alternates);
831                } else {
832                    // Case: {foo, bar} -> can stay as it is
833                    token = Token::Alternates(alternates);
834                }
835            } else {
836                // Case: {,,,} -> reduces to {}
837                return;
838            }
839        }
840
841        match (self.0.last_mut(), token) {
842            // Collapse Any's.
843            (Some(Token::Any(n)), Token::Any(n2)) => *n = n.saturating_add(n2.get()),
844            // Collapse multiple wildcards into a single one.
845            // TODO: separator special handling (?)
846            (Some(Token::Wildcard), Token::Wildcard) => {}
847            // Collapse wildcards with optionals.
848            (Some(Token::Wildcard), Token::Optional(_) | Token::OptionalAlternates(_)) => {}
849            (Some(Token::Optional(_) | Token::OptionalAlternates(_)), Token::Wildcard) => {
850                self.0.pop();
851                // We can now also remove all other preceding optionals.
852                while let Some(Token::Optional(_) | Token::OptionalAlternates(_)) = self.0.last() {
853                    self.0.pop();
854                }
855                self.0.push(Token::Wildcard);
856            }
857            // Collapse multiple literals into one.
858            (Some(Token::Literal(last)), Token::Literal(s)) => last.push(&s),
859            // Ignore empty class tokens.
860            (_, Token::Class { negated: _, ranges }) if ranges.is_empty() => {}
861            // Everything else is just another token.
862            (_, token) => self.0.push(token),
863        }
864    }
865
866    fn as_mut_slice(&mut self) -> &mut [Token] {
867        self.0.as_mut_slice()
868    }
869
870    fn as_slice(&self) -> &[Token] {
871        self.0.as_slice()
872    }
873}
874
875impl fmt::Display for Tokens {
876    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
877        for token in &self.0 {
878            token.fmt(f)?;
879        }
880
881        Ok(())
882    }
883}
884
885/// Represents a token in a Relay pattern.
886#[derive(Clone, Debug, PartialEq, Eq)]
887enum Token {
888    /// A literal token.
889    Literal(Literal),
890    /// The any token `?` and how many `?` are seen in a row.
891    Any(NonZeroUsize),
892    /// The wildcard token `*`.
893    Wildcard,
894    /// A class token `[abc]` or its negated variant `[!abc]`.
895    Class { negated: bool, ranges: Ranges },
896    /// A list of nested alternate tokens `{a,b}`.
897    Alternates(Vec<Tokens>),
898    /// A list of nested alternate tokens, where none need to match.
899    ///
900    /// There is no dedicated syntax for this, it is parsed from an alternate
901    /// group with an empty alternate: `{a,b,}`.
902    OptionalAlternates(Vec<Tokens>),
903    /// A list of optional tokens.
904    ///
905    /// This has no syntax of its own, it's parsed from an alternate with two
906    /// alternations where one of them is empty: `{a,}`.
907    Optional(Tokens),
908}
909
910impl fmt::Display for Token {
911    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
912        match self {
913            Token::Literal(literal) => literal.fmt(f),
914            Token::Any(num) => {
915                for _ in 0..num.get() {
916                    f.write_char('?')?;
917                }
918                Ok(())
919            }
920            Token::Wildcard => f.write_char('*'),
921            Token::Class { negated, ranges } => {
922                f.write_char('[')?;
923                if *negated {
924                    f.write_char('!')?;
925                }
926                ranges.fmt(f)?;
927                f.write_char(']')
928            }
929            Token::Alternates(items) => {
930                f.write_char('{')?;
931                let mut is_first = true;
932                for item in items {
933                    if !is_first {
934                        f.write_char(',')?;
935                    } else {
936                        is_first = false;
937                    }
938                    item.fmt(f)?;
939                }
940                f.write_char('}')
941            }
942            Token::OptionalAlternates(items) => {
943                f.write_char('{')?;
944                for item in items {
945                    item.fmt(f)?;
946                    // This will always produce an empty group as the last item in the alternate,
947                    // which is exactly what this token is built from.
948                    f.write_char(',')?;
949                }
950                f.write_char('}')
951            }
952            Token::Optional(tokens) => {
953                f.write_char('{')?;
954                tokens.fmt(f)?;
955                f.write_char(',')?;
956                f.write_char('}')
957            }
958        }
959    }
960}
961
962/// A string literal.
963///
964/// The contained literal is only available as a case converted string.
965/// Depending on whether the pattern is case sensitive or case insensitive the literal is either
966/// the original string or converted to lowercase.
967#[derive(Clone, Debug, Default, PartialEq, Eq)]
968struct Literal(String);
969
970impl Literal {
971    /// Creates a new literal from `s` and `options`.
972    fn new(s: String, options: Options) -> Self {
973        match options.case_insensitive {
974            false => Self(s),
975            true => Self(s.to_lowercase()),
976        }
977    }
978
979    /// Adds a literal to this literal.
980    ///
981    /// This function does not validate case conversion, both literals must be for the same caseing.
982    fn push(&mut self, Literal(other): &Literal) {
983        self.0.push_str(other);
984    }
985
986    /// Returns a reference to the case converted string.
987    fn as_case_converted_str(&self) -> &str {
988        &self.0
989    }
990
991    /// Returns a reference to the case converted string as bytes.
992    fn as_case_converted_bytes(&self) -> &[u8] {
993        self.as_case_converted_str().as_bytes()
994    }
995}
996
997impl fmt::Display for Literal {
998    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
999        fn print_escaped_char(c: char, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1000            // A comma must be escaped if the surrounding context is an alternation,
1001            // to not make the printing context dependent the comma is always escaped.
1002            if matches!(c, '*' | '?' | '[' | ']' | '{' | '}' | '\\' | ',') {
1003                f.write_char('\\')?;
1004            }
1005            f.write_char(c)
1006        }
1007
1008        for c in self.0.chars() {
1009            print_escaped_char(c, f)?;
1010        }
1011        Ok(())
1012    }
1013}
1014
1015/// A [`Range`] contains whatever is contained between `[` and `]` of
1016/// a glob pattern, except the negation.
1017///
1018/// For example the pattern `[a-z]` contains the range from `a` to `z`,
1019/// the pattern `[ax-zbf-h]` contains the ranges `x-z`, `f-h`, `a-a` and `b-b`.
1020#[derive(Clone, Debug, Default, PartialEq, Eq)]
1021enum Ranges {
1022    /// An empty, default range not containing any characters.
1023    ///
1024    /// The empty range matches nothing.
1025    #[default]
1026    Empty,
1027    /// The pattern only contains a single range.
1028    ///
1029    /// For example: `[a]` or `[a-z]`.
1030    Single(Range),
1031    /// The pattern contains more than one range.
1032    ///
1033    /// The `Empty` and `Single` states are just explicit and optimized
1034    /// cases for `Multiple` with a vector containing zero or just one range.
1035    Multiple(Vec<Range>),
1036}
1037
1038impl Ranges {
1039    /// Pushes another range into the current [`Range`].
1040    ///
1041    /// Returns [`Error`] if the range starts with a lexicographically larger character than it
1042    /// ends with.
1043    fn push(&mut self, range: Range) {
1044        match self {
1045            Self::Empty => *self = Self::Single(range),
1046            Self::Single(single) => *self = Self::Multiple(vec![*single, range]),
1047            Self::Multiple(v) => v.push(range),
1048        }
1049    }
1050
1051    /// Returns a mutable reference to the last range contained.
1052    fn last_mut(&mut self) -> Option<&mut Range> {
1053        match self {
1054            Ranges::Empty => None,
1055            Ranges::Single(range) => Some(range),
1056            Ranges::Multiple(ranges) => ranges.last_mut(),
1057        }
1058    }
1059
1060    /// Returns `true` if there is no contained range.
1061    fn is_empty(&self) -> bool {
1062        match self {
1063            Ranges::Empty => true,
1064            Ranges::Single(_) => false,
1065            Ranges::Multiple(ranges) => {
1066                // While not technically wrong, the invariant should uphold.
1067                debug_assert!(!ranges.is_empty());
1068                ranges.is_empty()
1069            }
1070        }
1071    }
1072
1073    /// Returns `true` if the character `c` is contained matches any contained range.
1074    #[inline(always)]
1075    fn contains(&self, c: char) -> bool {
1076        // TODO: optimize this into a `starts_with` which gets a `&str`, this can be optimized to
1077        // byte matches
1078        match self {
1079            Self::Empty => false,
1080            Self::Single(range) => range.contains(c),
1081            Self::Multiple(ranges) => ranges.iter().any(|range| range.contains(c)),
1082        }
1083    }
1084}
1085
1086impl fmt::Display for Ranges {
1087    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1088        match self {
1089            Ranges::Empty => Ok(()),
1090            Ranges::Single(range) => range.fmt(f),
1091            Ranges::Multiple(ranges) => {
1092                for range in ranges {
1093                    range.fmt(f)?;
1094                }
1095                Ok(())
1096            }
1097        }
1098    }
1099}
1100
1101/// Represents a character range in a [`Token::Class`].
1102#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1103struct Range {
1104    start: char,
1105    end: char,
1106}
1107
1108impl Range {
1109    /// Create a new range which matches a single character.
1110    fn single(c: char) -> Self {
1111        Self { start: c, end: c }
1112    }
1113
1114    /// Changes the end of the range to a new character.
1115    ///
1116    /// Returns an error if the new end character is lexicographically before
1117    /// the start character.
1118    fn set_end(&mut self, end: char) -> Result<(), ErrorKind> {
1119        if self.start > end {
1120            return Err(ErrorKind::InvalidRange(self.start, end));
1121        }
1122        self.end = end;
1123        Ok(())
1124    }
1125
1126    /// Returns `true` if the character `c` is contained in the range.
1127    #[inline(always)]
1128    fn contains(&self, c: char) -> bool {
1129        self.start <= c && c <= self.end
1130    }
1131}
1132
1133impl fmt::Display for Range {
1134    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1135        fn print_escaped_char(c: char, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1136            // The `!` only needs to be escaped if the range is the first range in a class,
1137            // to not make the escaping context dependent it's always escaped. Similar reasoning
1138            // applies also to `-`.
1139            if matches!(c, '[' | ']' | '\\' | '!' | '-') {
1140                f.write_char('\\')?;
1141            }
1142            f.write_char(c)
1143        }
1144
1145        print_escaped_char(self.start, f)?;
1146        if self.start != self.end {
1147            f.write_char('-')?;
1148            print_escaped_char(self.end, f)?;
1149        }
1150        Ok(())
1151    }
1152}
1153
1154#[cfg(test)]
1155mod tests {
1156    use super::*;
1157
1158    #[track_caller]
1159    fn build_pattern(p: &str, options: &str) -> Pattern {
1160        let mut pattern = Pattern::builder(p);
1161        for opt in options.chars() {
1162            match opt {
1163                'i' => drop(pattern.case_insensitive(true)),
1164                _ => unimplemented!("{opt} not implemented"),
1165            }
1166        }
1167        pattern.build().unwrap()
1168    }
1169
1170    #[track_caller]
1171    fn build_patterns(patterns: &[&str], options: &str) -> Patterns {
1172        let mut builder = Patterns::builder();
1173        for opt in options.chars() {
1174            match opt {
1175                'i' => drop(builder.case_insensitive(true)),
1176                _ => unimplemented!("{opt} not implemented"),
1177            }
1178        }
1179        let mut builder = builder.patterns();
1180        for pattern in patterns {
1181            builder.add(pattern).unwrap();
1182        }
1183        builder.build()
1184    }
1185
1186    macro_rules! pattern {
1187        ($pattern:expr $(,$options:tt)?) => {
1188            build_pattern($pattern, stringify!($($options)?))
1189        };
1190    }
1191
1192    macro_rules! patterns {
1193        ($($pattern:expr),* $(,)?) => {
1194            build_patterns(&[$($pattern),*], "")
1195        };
1196        ($($pattern:expr,)* @ $options:tt) => {
1197            build_patterns(&[$($pattern),*], stringify!($options))
1198        };
1199    }
1200
1201    macro_rules! assert_pattern {
1202        ($pattern:expr, $s:expr $(,$options:tt)?) => {{
1203            let pattern = pattern!($pattern $(,$options)?);
1204            assert!(
1205                pattern.is_match($s),
1206                "expected pattern '{}' to match '{}' - {pattern:?}",
1207                $pattern,
1208                $s
1209            );
1210            let pattern = pattern!(&pattern.to_string() $(,$options)?);
1211            assert!(
1212                pattern.is_match($s),
1213                "expected round-tripped pattern '{}' to match '{}' - {pattern:?}",
1214                $pattern,
1215                $s
1216            );
1217        }};
1218        ($pattern:expr, NOT $s:expr $(,$options:tt)?) => {{
1219            let pattern = pattern!($pattern $(,$options)?);
1220            assert!(
1221                !pattern.is_match($s),
1222                "expected pattern '{}' to not match '{}' - {pattern:?}",
1223                $pattern,
1224                $s
1225            );
1226            let pattern = pattern!(&pattern.to_string() $(,$options)?);
1227            assert!(
1228                !pattern.is_match($s),
1229                "expected round-tripped pattern '{}' to not match '{}' - {pattern:?}",
1230                $pattern,
1231                $s
1232            );
1233        }};
1234    }
1235
1236    macro_rules! assert_strategy {
1237        ($pattern:expr, $expected:pat) => {{
1238            let pattern = Pattern::new($pattern).unwrap();
1239            let kind = match &pattern.strategy {
1240                MatchStrategy::Literal(_) => "Literal",
1241                MatchStrategy::Prefix(_) => "Prefix",
1242                MatchStrategy::Suffix(_) => "Suffix",
1243                MatchStrategy::Contains(_) => "Contains",
1244                MatchStrategy::Static(_) => "Static",
1245                MatchStrategy::Wildmatch(_) => "Wildmatch",
1246            };
1247            assert_eq!(
1248                kind,
1249                stringify!($expected),
1250                "expected pattern '{}' to have strategy '{}' - {pattern:?}",
1251                $pattern,
1252                stringify!($expected)
1253            );
1254        }};
1255    }
1256
1257    macro_rules! assert_invalid {
1258        ($pattern:expr) => {{
1259            if let Ok(pattern) = Pattern::new($pattern) {
1260                assert!(
1261                    false,
1262                    "expected pattern '{}' to not compile - {pattern:?}",
1263                    $pattern
1264                );
1265            }
1266        }};
1267    }
1268
1269    #[test]
1270    fn test_empty() {
1271        assert_pattern!("", NOT "");
1272        assert_pattern!("", NOT "foo");
1273    }
1274
1275    #[test]
1276    fn test_literal() {
1277        assert_pattern!("foo", "foo");
1278        assert_pattern!("foo", NOT "fOo");
1279        assert_pattern!("foo", NOT "FOO");
1280        assert_pattern!(r"f\{\}o", "f{}o");
1281        assert_pattern!(r"f\}o", "f}o");
1282        assert_pattern!(r"f\{o", "f{o");
1283        assert_pattern!(r"f\{b,a,r\}o", "f{b,a,r}o");
1284        assert_pattern!(r"f\\o", r"f\o");
1285        assert_pattern!("fඞo", "fඞo");
1286    }
1287
1288    #[test]
1289    fn test_literal_case_insensitive() {
1290        assert_pattern!("foo", "foo", i);
1291        assert_pattern!("foo", "fOo", i);
1292        assert_pattern!("fOo", "Foo", i);
1293        assert_pattern!("İ", "i\u{307}", i);
1294        assert_pattern!("İ", "i̇", i);
1295        assert_pattern!("İ", NOT "i", i);
1296        assert_pattern!("i", NOT "İ", i);
1297        assert_pattern!("kelvin", "\u{212A}elvin", i);
1298        assert_pattern!("\u{212A}elvin", "kelvin", i);
1299        assert_pattern!("ß", "ẞ", i);
1300        assert_pattern!("straße", "straẞe", i);
1301        assert_pattern!("strasse", NOT "straẞe", i);
1302        assert_pattern!("ΑΣ", NOT "ΑΣ", i);
1303        assert_pattern!("ΑΣ", "ας", i);
1304        assert_pattern!("ΑΣ", NOT "ασ", i);
1305        assert_pattern!("ασ", "ΑΣ", i);
1306    }
1307
1308    #[test]
1309    fn test_literal_strategy() {
1310        assert_strategy!("foo", Literal);
1311        assert_strategy!(r"f\{b,a,r\}o", Literal);
1312        assert_strategy!(r"f\\o", Literal);
1313        assert_strategy!("fඞo", Literal);
1314    }
1315
1316    #[test]
1317    fn test_prefix() {
1318        assert_pattern!("foo*", "foo___");
1319        assert_pattern!("foo*", "foo");
1320        assert_pattern!(r"foo\?*", "foo?___");
1321        assert_pattern!(r"foo\?*", NOT "foox___");
1322        assert_pattern!("foo**", "foo");
1323        assert_pattern!("foo*?*", NOT "foo");
1324        assert_pattern!("foo*?*", "foo_");
1325        assert_pattern!("foo*?*?", "foo_____");
1326        assert_pattern!("foo*?*?", NOT "foo");
1327        assert_pattern!("foo*?*?", "foo__");
1328        assert_pattern!("foo*?*?", "foo_____");
1329        assert_pattern!("foo**", "foo___");
1330        assert_pattern!("foo*?*", "foo___");
1331        assert_pattern!("foo*?*?", "foo___");
1332        assert_pattern!("foo*", "fooඞ");
1333        assert_pattern!("ඞ*", "ඞfoo");
1334        assert_pattern!("foo*", NOT "___");
1335        assert_pattern!("foo*", NOT "fo");
1336        assert_pattern!("foo*", NOT "fob");
1337        assert_pattern!("foo*", NOT "boo");
1338        assert_pattern!("foo*", NOT "Foo");
1339        assert_pattern!("foo*", NOT "FOO___");
1340
1341        // No special slash handling
1342        assert_pattern!("foo/bar*", "foo/bar___");
1343        assert_pattern!("foo*", "foo/bar___");
1344        assert_pattern!("foo*", NOT "/foo");
1345    }
1346
1347    #[test]
1348    fn test_prefix_case_insensitive() {
1349        assert_pattern!("foo*", "foo___", i);
1350        assert_pattern!("foo*", "fOo___", i);
1351        assert_pattern!("foo*", "FOO___", i);
1352        assert_pattern!("fOo*", "FOO___", i);
1353        assert_pattern!("fOo*", "Foo___", i);
1354
1355        assert_pattern!("İ*", "İ___", i);
1356        assert_pattern!("İ*", "İ", i);
1357        assert_pattern!("İ*", "i̇", i);
1358        assert_pattern!("İ*", "i\u{307}___", i);
1359        assert_pattern!("İ*", NOT "i____", i);
1360
1361        assert_pattern!("kelvin*", "\u{212A}elvin___", i);
1362        assert_pattern!("\u{212A}elvin*", "kelvin___", i);
1363        assert_pattern!("ΑΣ*", NOT "ΑΣ", i);
1364        assert_pattern!("ΑΣ*", "ας___", i);
1365        assert_pattern!("ΑΣ*", NOT "ασ___", i);
1366        assert_pattern!("ασ*", "ΑΣ___", i);
1367    }
1368
1369    #[test]
1370    fn test_prefix_strategy() {
1371        assert_strategy!("foo*", Prefix);
1372        assert_strategy!("foo**", Prefix);
1373        assert_strategy!("foo?*", Wildmatch);
1374    }
1375
1376    #[test]
1377    fn test_suffix() {
1378        assert_pattern!("*foo", "___foo");
1379        assert_pattern!("*foo", "foo");
1380        assert_pattern!(r"*\?foo", "___?foo");
1381        assert_pattern!(r"*\?foo", NOT "___xfoo");
1382        assert_pattern!("**foo", "foo");
1383        assert_pattern!("*?*foo", NOT "foo");
1384        assert_pattern!("*?*foo", "_foo");
1385        assert_pattern!("*?*foo", "_____foo");
1386        assert_pattern!("?*?*foo", NOT "foo");
1387        assert_pattern!("?*?*foo", NOT "_foo");
1388        assert_pattern!("?*?*foo", "__foo");
1389        assert_pattern!("?*?*foo", "_____foo");
1390        assert_pattern!("**foo", "___foo");
1391        assert_pattern!("*?*foo", "___foo");
1392        assert_pattern!("*?*?foo", "__foo");
1393        assert_pattern!("*foo", "ඞfoo");
1394        assert_pattern!("*ඞ", "fooඞ");
1395        assert_pattern!("*foo", NOT "bar");
1396        assert_pattern!("*foo", NOT "fo");
1397        assert_pattern!("*foo", NOT "fob");
1398        assert_pattern!("*foo", NOT "boo");
1399        assert_pattern!("*foo", NOT "Foo");
1400        assert_pattern!("*foo", NOT "___FOO");
1401
1402        // No special slash handling
1403        assert_pattern!("*foo/bar", "___foo/bar");
1404        assert_pattern!("*bar", "___foo/bar");
1405        assert_pattern!("*foo", NOT "foo/");
1406    }
1407
1408    #[test]
1409    fn test_suffix_case_insensitive() {
1410        assert_pattern!("foo*", "foo___", i);
1411        assert_pattern!("foo*", "fOo___", i);
1412        assert_pattern!("foo*", "FOO___", i);
1413        assert_pattern!("fOo*", "FOO___", i);
1414        assert_pattern!("fOo*", "Foo___", i);
1415
1416        assert_pattern!("*İ", "___İ", i);
1417        assert_pattern!("*İ", "İ", i);
1418        assert_pattern!("*İ", "i̇", i);
1419        assert_pattern!("*İ", "___i\u{307}", i);
1420        assert_pattern!("*İ", NOT "___i", i);
1421    }
1422
1423    #[test]
1424    fn test_suffix_strategy() {
1425        assert_strategy!("*foo", Suffix);
1426        assert_strategy!("**foo", Suffix);
1427        assert_strategy!("*?foo", Wildmatch);
1428    }
1429
1430    #[test]
1431    fn test_contains() {
1432        assert_pattern!("*foo*", "foo");
1433        assert_pattern!(r"*\?foo*", "___?foo___");
1434        assert_pattern!(r"*\?foo*", NOT "___xfoo___");
1435        assert_pattern!("*foo*", "foo___");
1436        assert_pattern!("*foo*", "___foo");
1437        assert_pattern!("*foo*", "___foo___");
1438        assert_pattern!("*foo*", NOT "___fo");
1439        assert_pattern!("*foo*", NOT "oo___");
1440        assert_pattern!("*foo*", NOT "___fo___");
1441        assert_pattern!("*foo*", NOT "fඞo");
1442        assert_pattern!("*foo*", NOT "___fOo___");
1443        assert_pattern!("*foo*", NOT "___FOO___");
1444
1445        // No special slash handling
1446        assert_pattern!("*foo*", "foo");
1447        assert_pattern!("*foo*", "foo_/_");
1448        assert_pattern!("*foo*", "_/_foo");
1449        assert_pattern!("*foo*", "_/_foo_/_");
1450        assert_pattern!("*f/o*", "_/_f/o_/_");
1451    }
1452
1453    #[test]
1454    fn test_contains_case_insensitive() {
1455        assert_pattern!("*foo*", "foo", i);
1456        assert_pattern!("*foo*", "fOo", i);
1457        assert_pattern!("*fOo*", "Foo", i);
1458        assert_pattern!("*foo*", "___foo___", i);
1459        assert_pattern!("*foo*", "___fOo___", i);
1460        assert_pattern!("*foo*", "___FOO___", i);
1461        assert_pattern!("*fOo*", "___FOO___", i);
1462        assert_pattern!("*fOo*", "___Foo___", i);
1463
1464        assert_pattern!("*İ*", "___İ___", i);
1465        assert_pattern!("*İ*", "İ", i);
1466        assert_pattern!("*İ*", "___İ", i);
1467        assert_pattern!("*İ*", "İ___", i);
1468        assert_pattern!("*İ*", "___İ___", i);
1469        assert_pattern!("*İ*", "i̇", i);
1470        assert_pattern!("*İ*", "___i̇", i);
1471        assert_pattern!("*İ*", "i̇___", i);
1472        assert_pattern!("*İ*", "___i̇___", i);
1473        assert_pattern!("*İ*", "___i\u{307}", i);
1474        assert_pattern!("*İ*", "i\u{307}___", i);
1475        assert_pattern!("*İ*", "___i\u{307}___", i);
1476        assert_pattern!("*İ*", NOT "i", i);
1477        assert_pattern!("*İ*", NOT "i___", i);
1478        assert_pattern!("*İ*", NOT "___i", i);
1479        assert_pattern!("*İ*", NOT "___i___", i);
1480    }
1481
1482    #[test]
1483    fn test_contains_strategy() {
1484        assert_strategy!("*foo*", Contains);
1485        assert_strategy!("**foo**", Contains);
1486        assert_strategy!("*?foo*", Wildmatch);
1487        assert_strategy!("*foo?*", Wildmatch);
1488        assert_strategy!("*foo*?", Wildmatch);
1489        assert_strategy!("?*foo*", Wildmatch);
1490    }
1491
1492    #[test]
1493    fn test_wildcard() {
1494        assert_pattern!("*", "");
1495        assert_pattern!("*", "a");
1496        assert_pattern!("*", "\n");
1497        assert_pattern!("*", "\n\n");
1498        assert_pattern!("*", "\na\n");
1499        assert_pattern!("*", "\na\nb\nc");
1500        assert_pattern!("*", "ඞfooඞfooඞ");
1501
1502        // No special slash handling
1503        assert_pattern!("*", "/");
1504        assert_pattern!("*", "_/");
1505        assert_pattern!("*", "/_");
1506        assert_pattern!("*", "_/_");
1507        assert_pattern!("*", "/?/?/");
1508    }
1509
1510    #[test]
1511    fn test_wildcard_strategy() {
1512        assert_strategy!("*", Static);
1513        assert_strategy!("{*}", Static);
1514        assert_strategy!("{*,}", Static);
1515        assert_strategy!("{foo,*}", Static);
1516        assert_strategy!("{foo,*}?{*,bar}", Wildmatch);
1517        assert_strategy!("{*,}?{*,}", Wildmatch);
1518    }
1519
1520    #[test]
1521    fn test_any() {
1522        assert_pattern!("?", NOT "");
1523        assert_pattern!("?", "ඞ");
1524        assert_pattern!("?", "?");
1525        assert_pattern!("?", "\n");
1526        assert_pattern!("?", "_");
1527        assert_pattern!("?", NOT "aa");
1528        assert_pattern!("?", NOT "aaaaaaaaaaaaaaaaaa");
1529        assert_pattern!("??", "aa");
1530        assert_pattern!("??", NOT "aaa");
1531        assert_pattern!("a?a?a", "aaaaa");
1532        assert_pattern!("a?a?a", "abaca");
1533        assert_pattern!("a?a?a", NOT "ab_ca");
1534        assert_pattern!("a?a?a", NOT "aaAaa");
1535        assert_pattern!("???????????x???????????", "???????????x???????????");
1536        assert_pattern!("???????????x???????????", "??______???x?????_?????");
1537        assert_pattern!("???????????x???????????", NOT "?______???x?????_?????");
1538        assert_pattern!("???????????x???????????", NOT "??______???_?????_?????");
1539        assert_pattern!(
1540            "??????????????????????????????????????????????????",
1541            "?????????????????????????????????????????????????!"
1542        );
1543        assert_pattern!("foo?bar", "foo?bar");
1544        assert_pattern!("foo?bar", "foo!bar");
1545        assert_pattern!("a??a", "aඞඞa");
1546
1547        // No special slash handling
1548        assert_pattern!("?", "/");
1549    }
1550
1551    #[test]
1552    fn test_any_wildcard() {
1553        assert_pattern!("??*", NOT "");
1554        assert_pattern!("??*", NOT "a");
1555        assert_pattern!("??*", "ab");
1556        assert_pattern!("??*", "abc");
1557        assert_pattern!("??*", "abcde");
1558
1559        assert_pattern!("*??", NOT "");
1560        assert_pattern!("*??", NOT "a");
1561        assert_pattern!("*??", "ab");
1562        assert_pattern!("*??", "abc");
1563        assert_pattern!("*??", "abcde");
1564
1565        assert_pattern!("*??*", NOT "");
1566        assert_pattern!("*??*", NOT "a");
1567        assert_pattern!("*??*", "ab");
1568        assert_pattern!("*??*", "abc");
1569        assert_pattern!("*??*", "abcde");
1570
1571        assert_pattern!("*?*?*", NOT "");
1572        assert_pattern!("*?*?*", NOT "a");
1573        assert_pattern!("*?*?*", "ab");
1574        assert_pattern!("*?*?*", "abc");
1575        assert_pattern!("*?*?*", "abcde");
1576    }
1577
1578    #[test]
1579    fn test_escapes() {
1580        assert_pattern!(r"f\\o", r"f\o");
1581        assert_pattern!(r"f\*o", r"f*o");
1582        assert_pattern!(r"f\*o", NOT r"f\*o");
1583        assert_pattern!(r"f\?o", "f?o");
1584        assert_pattern!(r"f\?o", NOT "fao");
1585        assert_pattern!(r"f\\*o", r"f\*o");
1586        assert_pattern!(r"f\\*o", r"f\o");
1587        assert_pattern!(r"f\\*o", r"f\___o");
1588        assert_pattern!(r"f\\\*o", r"f\*o");
1589        assert_pattern!(r"f\[\]o", r"f[]o");
1590        assert_pattern!(r"f\[?\]o", r"f[?]o");
1591        assert_pattern!(r"f\[a-z\]o", r"f[a-z]o");
1592        assert_pattern!(r"f\[o", r"f[o");
1593        assert_pattern!(r"f\]o", r"f]o");
1594        assert_pattern!(r"f\,o", "f,o");
1595        assert_pattern!(r"\[", r"[");
1596    }
1597
1598    #[test]
1599    fn test_invalid() {
1600        assert_invalid!(r"\");
1601        assert_invalid!(r"f\");
1602        assert_invalid!(r"*\");
1603        assert_invalid!("[");
1604        assert_invalid!("[a-z");
1605        assert_invalid!(r"[a-z\");
1606        assert_invalid!("[[]");
1607        assert_invalid!("[]]");
1608        assert_invalid!("]");
1609        assert_invalid!("[a-z");
1610        assert_invalid!("[b-a]");
1611        assert_invalid!("[a-A]");
1612        assert_invalid!("{a,b,{c,d}}");
1613    }
1614
1615    #[test]
1616    fn test_classes() {
1617        assert_pattern!("[]", NOT "");
1618        assert_pattern!("[]", NOT "_");
1619        assert_pattern!("[a]", "a");
1620        assert_pattern!("[a]", NOT "[a]");
1621        assert_pattern!("[a]", NOT "b");
1622        assert_pattern!("[a]", NOT "A");
1623        assert_pattern!("[ඞ]", "ඞ");
1624        assert_pattern!("[ඞ]", NOT "a");
1625        assert_pattern!("[ඞa]", "a");
1626        assert_pattern!("[aඞ]", "ඞ");
1627        assert_pattern!("[ඞa]", NOT "b");
1628        assert_pattern!("[ab]", "a");
1629        assert_pattern!("[ab]", "b");
1630        assert_pattern!("[ab]", NOT "c");
1631        assert_pattern!("x[ab]x", "xax");
1632        assert_pattern!("x[ab]x", "xbx");
1633        assert_pattern!("x[ab]x", NOT "xBx");
1634        assert_pattern!("x[ab]x", NOT "xcx");
1635        assert_pattern!("x[ab]x", NOT "aax");
1636        assert_pattern!("x[ab]x", NOT "xaa");
1637        assert_pattern!("x[ab]x", NOT "xaax");
1638        assert_pattern!("x[ab]x", NOT "xxax");
1639        assert_pattern!("x[ab]x", NOT "xaxx");
1640        assert_pattern!("[a-b]", "a");
1641        assert_pattern!("[a-b]", "b");
1642        assert_pattern!("[a-b]", NOT "c");
1643        assert_pattern!("[a-c]", "a");
1644        assert_pattern!("[a-c]", "b");
1645        assert_pattern!("[a-c]", "c");
1646        assert_pattern!("[a-c]", NOT "d");
1647        assert_pattern!("[a-c]", NOT "1");
1648        assert_pattern!("[a-c]", NOT "ඞ");
1649        assert_pattern!("[A-z]", "a");
1650        assert_pattern!("[A-z]", "z");
1651        assert_pattern!("[A-z]", "["); // `[` is actually inbetween here in the ascii table
1652        assert_pattern!("[A-z]", "A");
1653        assert_pattern!("[A-z]", "Z");
1654        assert_pattern!("[A-z]", NOT "0");
1655        assert_pattern!("[0-9]", "0");
1656        assert_pattern!("[0-9]", "1");
1657        assert_pattern!("[0-9]", "2");
1658        assert_pattern!("[0-9]", "3");
1659        assert_pattern!("[0-9]", "4");
1660        assert_pattern!("[0-9]", "5");
1661        assert_pattern!("[0-9]", "6");
1662        assert_pattern!("[0-9]", "7");
1663        assert_pattern!("[0-9]", "8");
1664        assert_pattern!("[0-9]", "9");
1665        assert_pattern!(
1666            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1667            "3bYf"
1668        );
1669        assert_pattern!(
1670            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1671            NOT "3cYf"
1672        );
1673        assert_pattern!(
1674            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1675            NOT "3ඞYf"
1676        );
1677        assert_pattern!("[0-9]", NOT "a9");
1678        assert_pattern!("[0-9]", NOT "9a");
1679        assert_pattern!("[0-9]", NOT "a9a");
1680        assert_pattern!("[0-9]", NOT "");
1681        assert_pattern!("[0-9!]", "!");
1682        assert_pattern!("[0-9][a-b]", NOT "");
1683        assert_pattern!("[0-9][a-b]", NOT "a");
1684        assert_pattern!("[0-9][a-b]", NOT "a0");
1685        assert_pattern!("[0-9][a-b]", "0a");
1686        assert_pattern!(r"a[\]a\-]b", "aab");
1687
1688        // TODO: lenient: assert_pattern!("a[]-]b", NOT "aab");
1689        // TODO: lenient: assert_pattern!("]", "]");
1690        // TODO: lenient: assert_pattern!("a[]-]b", "a-]b");
1691        // TODO: lenient: assert_pattern!("a[]-]b", "a]b");
1692        // TODO: lenient: assert_pattern!("a[]]b", "a]b");
1693
1694        // Escapes in character classes
1695        assert_pattern!(r"[\\]", r"\");
1696        assert_pattern!(r"[\\]", NOT "a");
1697        assert_pattern!(r"[\]]", "]");
1698        assert_pattern!(r"[\]]", NOT "a");
1699        assert_pattern!(r"[\[]", "[");
1700        assert_pattern!(r"[\[]", NOT "a");
1701        assert_pattern!(r"[\]]", NOT r"\");
1702        assert_pattern!(r"[\!]", "!");
1703        assert_pattern!(r"[\!]", NOT "a");
1704        assert_pattern!(r"[a\-c]", "-");
1705        assert_pattern!(r"[a\-c]", NOT "b");
1706        assert_pattern!(r"[\!--]", "!");
1707        assert_pattern!(r"[\!--]", "-");
1708        assert_pattern!(r"[\!--]", NOT "a");
1709        assert_pattern!(r"[\[-a]", "[");
1710        assert_pattern!(r"[\[-a]", "a");
1711        assert_pattern!(r"[\[-a]", NOT "b");
1712        assert_pattern!(r"[A-\]]", "]");
1713        assert_pattern!(r"[A-\]]", "Z");
1714        assert_pattern!(r"[A-\]]", NOT "a");
1715        assert_pattern!(r"[A-\\]", r"\");
1716        assert_pattern!(r"[A-\\]", NOT "a");
1717        assert_pattern!(r"[\]-z]", "]");
1718        assert_pattern!(r"[\]-z]", "z");
1719        assert_pattern!(r"[\]-z]", NOT r"\");
1720        assert_pattern!(r"[\\-z]", r"\");
1721        assert_pattern!(r"[\\-z]", "z");
1722        assert_pattern!(r"[\\-z]", NOT "[");
1723        assert_pattern!(r"[\--z]", "-");
1724        assert_pattern!(r"[\--z]", "z");
1725        assert_pattern!(r"[\--z]", NOT "!");
1726        assert_pattern!("[*?{},]", "*");
1727        assert_pattern!("[*?{},]", "?");
1728        assert_pattern!("[*?{},]", "{");
1729        assert_pattern!("[*?{},]", "}");
1730        assert_pattern!("[*?{},]", ",");
1731        assert_pattern!("[*?{},]", NOT "a");
1732
1733        assert_pattern!("a[X-]b", "a-b");
1734        assert_pattern!("a[X-]b", "aXb");
1735    }
1736
1737    #[test]
1738    fn test_classes_case_insensitive() {
1739        assert_pattern!("[a]", "a", i);
1740        assert_pattern!("[a]", "A", i);
1741        assert_pattern!("x[ab]x", "xAX", i);
1742        assert_pattern!("x[ab]x", "XBx", i);
1743        assert_pattern!("x[ab]x", NOT "Xcx", i);
1744        assert_pattern!("x[ab]x", NOT "aAx", i);
1745        assert_pattern!("x[ab]x", NOT "xAa", i);
1746        assert_pattern!("[ǧ]", "Ǧ", i);
1747        assert_pattern!("[Ǧ]", "ǧ", i);
1748    }
1749
1750    #[test]
1751    fn test_classes_negated() {
1752        assert_pattern!("[!]", NOT "");
1753        assert_pattern!(r"[!\!]", "a");
1754        assert_pattern!(r"[!\!]", NOT "!");
1755        assert_pattern!("[!a]", "b");
1756        assert_pattern!("[!a]", "A");
1757        assert_pattern!("[!a]", "B");
1758        assert_pattern!("[!b]", NOT "b");
1759        assert_pattern!("[!ab]", NOT "a");
1760        assert_pattern!("[!ab]", NOT "b");
1761        assert_pattern!("[!ab]", "c");
1762        assert_pattern!("x[!ab]x", "xcx");
1763        assert_pattern!("x[!ab]x", NOT "xax");
1764        assert_pattern!("x[!ab]x", NOT "xbx");
1765        assert_pattern!("x[!ab]x", NOT "xxcx");
1766        assert_pattern!("x[!ab]x", NOT "xcxx");
1767        assert_pattern!("x[!ab]x", NOT "xc");
1768        assert_pattern!("x[!ab]x", NOT "cx");
1769        assert_pattern!("x[!ab]x", NOT "x");
1770        assert_pattern!("[!a-c]", NOT "a");
1771        assert_pattern!("[!a-c]", NOT "b");
1772        assert_pattern!("[!a-c]", NOT "c");
1773        assert_pattern!("[!a-c]", "d");
1774        assert_pattern!("[!a-c]", "A");
1775        assert_pattern!("[!a-c]", "ඞ");
1776        assert_pattern!(r"[!a-c\\]", "d");
1777        assert_pattern!(r"[!a-c\\]", NOT r"\");
1778        assert_pattern!(r"[!\]]", "a");
1779        assert_pattern!(r"[!\]]", NOT "]");
1780        assert_pattern!(r"[!!]", "a");
1781        assert_pattern!(r"[!!]", NOT "!");
1782    }
1783
1784    #[test]
1785    fn test_classes_negated_case_insensitive() {
1786        assert_pattern!("[!a]", "b", i);
1787        assert_pattern!("[!a]", "B", i);
1788        assert_pattern!("[!b]", NOT "b", i);
1789        assert_pattern!("[!b]", NOT "B", i);
1790        assert_pattern!("[!ab]", NOT "a", i);
1791        assert_pattern!("[!ab]", NOT "A", i);
1792        assert_pattern!("[!ab]", NOT "b", i);
1793        assert_pattern!("[!ab]", NOT "B", i);
1794        assert_pattern!("[!ab]", "c", i);
1795        assert_pattern!("[!ab]", "C", i);
1796    }
1797
1798    #[test]
1799    fn test_alternates() {
1800        assert_pattern!("{}foo{}", "foo");
1801        assert_pattern!("foo{}bar", "foobar");
1802        assert_pattern!("foo{}{}bar", "foobar");
1803        assert_pattern!("{foo}", "foo");
1804        assert_pattern!("{foo}", NOT "fOo");
1805        assert_pattern!("{foo}", NOT "bar");
1806        assert_pattern!("{foo,bar}", "foo");
1807        assert_pattern!("{foo,bar}", "bar");
1808        assert_pattern!(r"{foo,bar,baz\,}", "foo");
1809        assert_pattern!(r"{foo,bar,baz\,}", "baz,");
1810        assert_pattern!(r"{foo,bar,baz\,}", NOT "baz");
1811        assert_pattern!(r"{foo,bar,baz\,}", NOT "");
1812        assert_pattern!(r"{foo\,,}", "foo,");
1813        assert_pattern!(r"{foo\,,}", "");
1814        assert_pattern!(r"{foo\,,}", NOT "foo");
1815        assert_pattern!(r"{foo,bar\,,}", "bar,");
1816        assert_pattern!(r"{foo,bar\,,}", "");
1817        assert_pattern!(r"{foo,bar\,,}", NOT "bar");
1818        assert_pattern!("{foo,bar}", NOT "Foo");
1819        assert_pattern!("{foo,bar}", NOT "fOo");
1820        assert_pattern!("{foo,bar}", NOT "BAR");
1821        assert_pattern!("{foo,bar}", NOT "fooo");
1822        assert_pattern!("{foo,bar}", NOT "baar");
1823        assert_pattern!("{foo,bar,}baz", "foobaz");
1824        assert_pattern!("{foo,bar,}baz", "barbaz");
1825        assert_pattern!("{foo,bar,}baz", "baz");
1826        assert_pattern!("{foo,,bar}baz", "foobaz");
1827        assert_pattern!("{foo,,bar}baz", "barbaz");
1828        assert_pattern!("{foo,,bar}baz", "baz");
1829        assert_pattern!("{,foo,bar}baz", "foobaz");
1830        assert_pattern!("{,foo,bar}baz", "barbaz");
1831        assert_pattern!("{,foo,bar}baz", "baz");
1832        assert_pattern!("{foo*bar}", "foobar");
1833        assert_pattern!("{foo*bar}", "fooooobar");
1834        assert_pattern!("{foo*bar}", NOT "");
1835        assert_pattern!("{foo*bar,}", "foobar");
1836        assert_pattern!("{foo*bar,}", "fooooobar");
1837        assert_pattern!("{foo*bar,}", "");
1838        assert_pattern!("{foo*bar,baz}", "foobar");
1839        assert_pattern!("{foo*bar,baz}", "fooooobar");
1840        assert_pattern!("{foo*bar,baz}", "baz");
1841        assert_pattern!("{foo*bar,baz}", NOT "");
1842        assert_pattern!("{foo*bar,baz,}", "foobar");
1843        assert_pattern!("{foo*bar,baz,}", "fooooobar");
1844        assert_pattern!("{foo*bar,baz,}", "baz");
1845        assert_pattern!("{foo*bar,baz,}", "");
1846        assert_pattern!("{,,,,}", NOT "");
1847        assert_pattern!("{[fb][oa][or]}", "foo");
1848        assert_pattern!("{[fb][oa][or]}", "bar");
1849        assert_pattern!("{[fb][oa][or],baz}", "foo");
1850        assert_pattern!("{[fb][oa][or],baz}", "bar");
1851        assert_pattern!("{[fb][oa][or],baz}", "baz");
1852        assert_pattern!("{baz,[fb][oa][or]}", "baz");
1853        assert_pattern!("{baz,[fb][oa][or]}", "foo");
1854        assert_pattern!("{baz,[fb][oa][or]}", "bar");
1855        assert_pattern!("{baz,[fb][oa][or]}", "bor");
1856        assert_pattern!("{baz,[fb][oa][or]}", NOT "barr");
1857        assert_pattern!("{baz,[fb][oa][or]}", NOT "boz");
1858        assert_pattern!("{baz,[fb][oa][or]}", NOT "fbar");
1859        assert_pattern!("{baz,[fb][oa][or]}", NOT "bAr");
1860        assert_pattern!("{baz,[fb][oa][or]}", NOT "Foo");
1861        assert_pattern!("{baz,[fb][oa][or]}", NOT "Bar");
1862        assert_pattern!("{baz,b[aA]r}", NOT "bAz");
1863        assert_pattern!("{baz,b[!aA]r}", NOT "bar");
1864        assert_pattern!("{baz,b[!aA]r}", "bXr");
1865        assert_pattern!("{[a-z],[0-9]}", "a");
1866        assert_pattern!("{[a-z],[0-9]}", "3");
1867        assert_pattern!("a{[a-z],[0-9]}a", "a3a");
1868        assert_pattern!("a{[a-z],[0-9]}a", "aba");
1869        assert_pattern!("a{[a-z],[0-9]}a", NOT "aAa");
1870        assert_pattern!("a{[a-z],?}a", "aXa");
1871        assert_pattern!(r"a{[a-z],\?}a", "a?a");
1872        assert_pattern!(r"a{[a-z],\?}a", NOT "aXa");
1873        assert_pattern!(r"a{[a-z],\?}a", NOT r"a\a");
1874        assert_pattern!(r"a{\[\],\{\}}a", "a[]a");
1875        assert_pattern!(r"a{\[\],\{\}}a", "a{}a");
1876        assert_pattern!(r"a{\[\],\{\}}a", NOT "a[}a");
1877        assert_pattern!(r"a{\[\],\{\}}a", NOT "a{]a");
1878        assert_pattern!(r"a{\[\],\{\}}a", NOT "a[a");
1879        assert_pattern!(r"a{\[\],\{\}}a", NOT "a]a");
1880        assert_pattern!(r"a{\[\],\{\}}a", NOT "a{a");
1881        assert_pattern!(r"a{\[\],\{\}}a", NOT "a}a");
1882        assert_pattern!("foo/{*.js,*.html}", "foo/.js");
1883        assert_pattern!("foo/{*.js,*.html}", "foo/.html");
1884        assert_pattern!("foo/{*.js,*.html}", "foo/bar.js");
1885        assert_pattern!("foo/{*.js,*.html}", "foo/bar.html");
1886        assert_pattern!("foo/{*.js,*.html}", NOT "foo/bar.png");
1887        assert_pattern!("foo/{*.js,*.html}", NOT "bar/bar.js");
1888        assert_pattern!("{foo,abc}{def,bar}", "foodef");
1889        assert_pattern!("{foo,abc}{def,bar}", "foobar");
1890        assert_pattern!("{foo,abc}{def,bar}", "abcdef");
1891        assert_pattern!("{foo,abc}{def,bar}", "abcbar");
1892        assert_pattern!("{foo,abc}{def,bar}", NOT "foofoo");
1893        assert_pattern!("{foo,abc}{def,bar}", NOT "fooabc");
1894        assert_pattern!("{foo,abc}{def,bar}", NOT "defdef");
1895        assert_pattern!("{foo,abc}{def,bar}", NOT "defabc");
1896    }
1897
1898    #[test]
1899    fn test_alternates_many() {
1900        const N: usize = 100_000;
1901
1902        let pattern = Pattern::new(&"{ab,ba}".repeat(N)).unwrap();
1903        assert!(pattern.is_match(&"ab".repeat(N)));
1904        assert!(pattern.is_match(&"ba".repeat(N)));
1905        assert!(pattern.is_match(&"abba".repeat(N / 2)));
1906        assert!(!pattern.is_match(&"ab".repeat(N - 1)));
1907        assert!(!pattern.is_match(&format!("{}aa", "ab".repeat(N - 1))));
1908    }
1909
1910    #[test]
1911    fn test_alternates_optional() {
1912        assert_pattern!("{a,}{b,}", "ab");
1913        assert_pattern!("{a,}{b,}", "a");
1914        assert_pattern!("{a,}{b,}", "b");
1915        assert_pattern!("{a,}{b,}", "");
1916        assert_pattern!("{a,b,}{c,}", "ac");
1917        assert_pattern!("{a,b,}{c,}", "bc");
1918        assert_pattern!("{a,b,}{c,}", "a");
1919        assert_pattern!("{a,b,}{c,}", "b");
1920        assert_pattern!("{a,b,}{c,}", "c");
1921        assert_pattern!("{a,b,}{c,}", "");
1922        assert_pattern!("{a,b,}{c,}", NOT "ab");
1923        assert_pattern!("{a,b,}{c,}", NOT "abc");
1924    }
1925
1926    #[test]
1927    fn test_alternate_strategy() {
1928        // Empty alternates can be simplified.
1929        assert_strategy!("{}foo{}", Literal);
1930        assert_strategy!("foo{}bar", Literal);
1931        assert_strategy!("foo{}{}{}bar", Literal);
1932        assert_strategy!("foo{,,,}bar", Literal);
1933    }
1934
1935    #[test]
1936    fn test_optional_wildcard_strategy() {
1937        // Optional alternates after a wildcard can be folded into a wildcard.
1938        assert_strategy!("*{foo,}", Static);
1939        assert_strategy!("*{foo,bar,}", Static);
1940        assert_strategy!("foo*{bar,}", Prefix);
1941        assert_strategy!("foo*{bar,baz,}", Prefix);
1942        assert_strategy!("*{foo,}bar", Suffix);
1943        assert_strategy!("*{foo,baz,}bar", Suffix);
1944        assert_strategy!("*{bar,}foo*", Contains);
1945        assert_strategy!("*{bar,baz,}foo*", Contains);
1946
1947        // The same is true for the inverse, we can fold alterantes followed by a wildcard into a wildcard.
1948        assert_strategy!("{foo,}*", Static);
1949        assert_strategy!("{foo,bar,}*", Static);
1950        assert_strategy!("foo{bar,}*", Prefix);
1951        assert_strategy!("foo{bar,baz,}*", Prefix);
1952        assert_strategy!("{foo,}*bar", Suffix);
1953        assert_strategy!("{foo,baz,}*bar", Suffix);
1954        assert_strategy!("*foo{bar,}*", Contains);
1955        assert_strategy!("*foo{bar,baz,}*", Contains);
1956
1957        // This also applies for multiple chained alternates.
1958        assert_strategy!("*{bar,}{baz,qux,}foo", Suffix);
1959        assert_strategy!("{*,bar}{baz,qux,}foo", Suffix);
1960        assert_strategy!("foo{bar,}{baz,qux,}*", Prefix);
1961        assert_strategy!("foo{bar,}{baz,qux,}{bar,*}", Prefix);
1962    }
1963
1964    #[test]
1965    fn test_alternates_case_insensitive() {
1966        assert_pattern!("{foo}", "foo", i);
1967        assert_pattern!("{foo}", "fOo", i);
1968        assert_pattern!("{foo}", NOT "bar", i);
1969        assert_pattern!("{foo,bar}", "foo", i);
1970        assert_pattern!("{foo,bar}", "bar", i);
1971        assert_pattern!("{foo,bar}", "Foo", i);
1972        assert_pattern!("{foo,bar}", "fOo", i);
1973        assert_pattern!("{foo,bar}", "BAR", i);
1974        assert_pattern!("{foo,bar}", NOT "bao", i);
1975        assert_pattern!("{f[o0-9]o,b[a]r}", "foo", i);
1976        assert_pattern!("{f[o0-9]o,b[a]r}", "fOo", i);
1977        assert_pattern!("{f[o0-9]o,b[a]r}", "f1o", i);
1978        assert_pattern!("{f[o0-9]o,b[a]r}", "foO", i);
1979        assert_pattern!("{f[o0-9]o,b[a]r}", "FOO", i);
1980        assert_pattern!("{f[o0-9]o,b[a]r}", "bar", i);
1981        assert_pattern!("{f[o0-9]o,b[a]r}", "bAr", i);
1982        assert_pattern!("{f[o0-9]o,b[a]r}", "baR", i);
1983        assert_pattern!("{f[o0-9]o,b[a]r}", "BAR", i);
1984        assert_pattern!("{f[o0-9]o,b[!a]r}", "foo", i);
1985        assert_pattern!("{f[o0-9]o,b[!a]r}", "bXr", i);
1986        assert_pattern!("{f[o0-9]o,b[!a]r}", NOT "bar", i);
1987        assert_pattern!("{f[o0-9]o,b[!a]r}", NOT "bAr", i);
1988    }
1989
1990    #[test]
1991    fn test_complex() {
1992        assert_pattern!("*?", "\n");
1993        assert_pattern!("?*", "\n");
1994        assert_pattern!("*?*", "\n");
1995        assert_pattern!("1.18.[!0-4].*", "1.18.5.");
1996        assert_pattern!("1.18.[!0-4].*", "1.18.5.aBc");
1997        assert_pattern!("1.18.[!0-4].*", NOT "1.18.3.abc");
1998        assert_pattern!("!*!*.md", "!foo!.md"); // no `!` outside of character classes
1999        assert_pattern!("foo*foofoo*foobar", "foofoofooxfoofoobar");
2000        assert_pattern!("foo*fooFOO*fOobar", "fooFoofooXfoofooBAR", i);
2001        assert_pattern!("[0-9]*a", "0aaaaaaaaa", i);
2002        assert_pattern!("[0-9]*Bar[x]", "0foobarx", i);
2003
2004        assert_pattern!(
2005            r"/api/0/organizations/\{organization_slug\}/event*",
2006            "/api/0/organizations/{organization_slug}/event/foobar"
2007        );
2008        assert_pattern!(
2009            r"/api/0/organizations/\{organization_slug\}/event*",
2010            NOT r"/api/0/organizations/\{organization_slug\}/event/foobar"
2011        );
2012
2013        assert_pattern!(
2014            "*b??{foo,bar,baz,with}*cr{x,y,z,?}zyl[a-z]ng{suffix,pr?*ix}*it?**?uallymatches",
2015            "foobarwithacrazylongprefixandanditactuallymatches"
2016        );
2017        assert_pattern!(
2018            "*b??{foo,bar,baz,with}*cr{x,y,z,?}zyl[a-z]ng{suffix,pr?*ix}*it?**?uallymatches",
2019            "FOOBARWITHACRAZYLONGPREFIXANDANDITACTUALLYMATCHES",
2020            i
2021        );
2022    }
2023
2024    /// Tests collected by [Kirk J Krauss].
2025    ///
2026    /// Kirk J Krauss: http://developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html.
2027    #[test]
2028    fn test_kirk_j_krauss() {
2029        // Case with first wildcard after total match.
2030        assert_pattern!("Hi*", "Hi");
2031
2032        // Case with mismatch after '*'
2033        assert_pattern!("ab*d", NOT "abc");
2034
2035        // Cases with repeating character sequences.
2036        assert_pattern!("*ccd", "abcccd");
2037        assert_pattern!("*issip*ss*", "mississipissippi");
2038        assert_pattern!("xxxx*zzy*fffff", NOT "xxxx*zzzzzzzzy*f");
2039        assert_pattern!("xxx*zzy*f", "xxxx*zzzzzzzzy*f");
2040        assert_pattern!("xxxx*zzy*fffff", NOT "xxxxzzzzzzzzyf");
2041        assert_pattern!("xxxx*zzy*f", "xxxxzzzzzzzzyf");
2042        assert_pattern!("xy*z*xyz", "xyxyxyzyxyz");
2043        assert_pattern!("*sip*", "mississippi");
2044        assert_pattern!("xy*xyz", "xyxyxyxyz");
2045        assert_pattern!("mi*sip*", "mississippi");
2046        assert_pattern!("*abac*", "ababac");
2047        assert_pattern!("*abac*", "ababac");
2048        assert_pattern!("a*zz*", "aaazz");
2049        assert_pattern!("*12*23", NOT "a12b12");
2050        assert_pattern!("a12b", NOT "a12b12");
2051        assert_pattern!("*12*12*", "a12b12");
2052
2053        // From DDJ reader Andy Belf
2054        assert_pattern!("*a?b", "caaab");
2055
2056        // Additional cases where the '*' char appears in the tame string.
2057        assert_pattern!("*", "*");
2058        assert_pattern!("a*b", "a*abab");
2059        assert_pattern!("a*", "a*r");
2060        assert_pattern!("a*aar", NOT "a*ar");
2061
2062        // More double wildcard scenarios.
2063        assert_pattern!("XY*Z*XYz", "XYXYXYZYXYz");
2064        assert_pattern!("*SIP*", "missisSIPpi");
2065        assert_pattern!("*issip*PI", "mississipPI");
2066        assert_pattern!("xy*xyz", "xyxyxyxyz");
2067        assert_pattern!("mi*sip*", "miSsissippi");
2068        assert_pattern!("mi*Sip*", NOT "miSsissippi");
2069        assert_pattern!("*Abac*", "abAbac");
2070        assert_pattern!("*Abac*", "abAbac");
2071        assert_pattern!("a*zz*", "aAazz");
2072        assert_pattern!("*12*23", NOT "A12b12");
2073        assert_pattern!("*12*12*", "a12B12");
2074        assert_pattern!("*oWn*", "oWn");
2075
2076        // Completely tame (no wildcards) cases.
2077        assert_pattern!("bLah", "bLah");
2078        assert_pattern!("bLaH", NOT "bLah");
2079
2080        // Simple mixed wildcard tests suggested by Marlin Deckert.
2081        assert_pattern!("*?", "a");
2082        assert_pattern!("*?", "ab");
2083        assert_pattern!("*?", "abc");
2084
2085        // More mixed wildcard tests including coverage for false positives.
2086        assert_pattern!("??", NOT "a");
2087        assert_pattern!("?*?", "ab");
2088        assert_pattern!("*?*?*", "ab");
2089        assert_pattern!("?**?*?", "abc");
2090        assert_pattern!("?**?*&?", NOT "abc");
2091        assert_pattern!("?b*??", "abcd");
2092        assert_pattern!("?a*??", NOT "abcd");
2093        assert_pattern!("?**?c?", "abcd");
2094        assert_pattern!("?**?d?", NOT "abcd");
2095        assert_pattern!("?*b*?*d*?", "abcde");
2096
2097        // Single-character-match cases.
2098        assert_pattern!("bL?h", "bLah");
2099        assert_pattern!("bLa?", NOT "bLaaa");
2100        assert_pattern!("bLa?", "bLah");
2101        assert_pattern!("?Lah", NOT "bLaH");
2102        assert_pattern!("?LaH", "bLaH");
2103
2104        // Many-wildcard scenarios.
2105        assert_pattern!(
2106            "a*a*a*a*a*a*aa*aaa*a*a*b",
2107            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
2108        );
2109        assert_pattern!(
2110            "*a*b*ba*ca*a*aa*aaa*fa*ga*b*",
2111            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2112        );
2113        assert_pattern!(
2114            "*a*b*ba*ca*a*x*aaa*fa*ga*b*",
2115            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2116        );
2117        assert_pattern!(
2118            "*a*b*ba*ca*aaaa*fa*ga*gggg*b*",
2119            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2120        );
2121        assert_pattern!(
2122            "*a*b*ba*ca*aaaa*fa*ga*ggg*b*",
2123            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2124        );
2125        assert_pattern!("*aabbaa*a*", "aaabbaabbaab");
2126        assert_pattern!(
2127            "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*",
2128            "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*"
2129        );
2130        assert_pattern!("*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*", "aaaaaaaaaaaaaaaaa");
2131        assert_pattern!(
2132            "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*",
2133            NOT "aaaaaaaaaaaaaaaa"
2134        );
2135        assert_pattern!(
2136            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*",
2137            NOT "abc*abcd*abcde*abcdef*abcdefg*abcdefgh*abcdefghi*abcdefghij*abcdefghijk*abcdefghijkl*abcdefghijklm*abcdefghijklmn"
2138        );
2139        assert_pattern!(
2140            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*",
2141            "abc*abcd*abcde*abcdef*abcdefg*abcdefgh*abcdefghi*abcdefghij*abcdefghijk*abcdefghijkl*abcdefghijklm*abcdefghijklmn"
2142        );
2143        assert_pattern!("abc*abc*abc*abc*abc", NOT "abc*abcd*abcd*abc*abcd");
2144        assert_pattern!(
2145            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abcd",
2146            "abc*abcd*abcd*abc*abcd*abcd*abc*abcd*abc*abc*abcd"
2147        );
2148        assert_pattern!("********a********b********c********", "abc");
2149        assert_pattern!("abc", NOT "********a********b********c********");
2150        assert_pattern!("********a********b********b********", NOT "abc");
2151        assert_pattern!("***a*b*c***", "*abc*");
2152
2153        // A case-insensitive algorithm test.
2154        assert_pattern!("*issip*PI", "mississippi", i);
2155
2156        // Tests suggested by other DDJ readers
2157        assert_pattern!("?", NOT "");
2158        assert_pattern!("*?", NOT "");
2159        // assert_pattern!("", ""); - Removed, relay-pattern behaves differently for empty strings.
2160        assert_pattern!("", NOT "a");
2161
2162        // Tame tests:
2163        assert_pattern!("abd", NOT "abc");
2164
2165        // Cases with repeating character sequences.
2166        assert_pattern!("abcccd", "abcccd");
2167        assert_pattern!("mississipissippi", "mississipissippi");
2168        assert_pattern!("xxxxzzzzzzzzyfffff", NOT "xxxxzzzzzzzzyf");
2169        assert_pattern!("xxxxzzzzzzzzyf", "xxxxzzzzzzzzyf");
2170        assert_pattern!("xxxxzzy.fffff", NOT "xxxxzzzzzzzzyf");
2171        assert_pattern!("xxxxzzzzzzzzyf", "xxxxzzzzzzzzyf");
2172        assert_pattern!("xyxyxyzyxyz", "xyxyxyzyxyz");
2173        assert_pattern!("mississippi", "mississippi");
2174        assert_pattern!("xyxyxyxyz", "xyxyxyxyz");
2175        assert_pattern!("m ississippi", "m ississippi");
2176        assert_pattern!("ababac?", NOT "ababac");
2177        assert_pattern!("ababac", NOT "dababac");
2178        assert_pattern!("aaazz", "aaazz");
2179        assert_pattern!("1212", NOT "a12b12");
2180        assert_pattern!("a12b", NOT "a12b12");
2181        assert_pattern!("a12b12", "a12b12");
2182
2183        // A mix of cases
2184        assert_pattern!("n", "n");
2185        assert_pattern!("aabab", "aabab");
2186        assert_pattern!("ar", "ar");
2187        assert_pattern!("aaar", NOT "aar");
2188        assert_pattern!("XYXYXYZYXYz", "XYXYXYZYXYz");
2189        assert_pattern!("missisSIPpi", "missisSIPpi");
2190        assert_pattern!("mississipPI", "mississipPI");
2191        assert_pattern!("xyxyxyxyz", "xyxyxyxyz");
2192        assert_pattern!("miSsissippi", "miSsissippi");
2193        assert_pattern!("miSsisSippi", NOT "miSsissippi");
2194        assert_pattern!("abAbac", "abAbac");
2195        assert_pattern!("abAbac", "abAbac");
2196        assert_pattern!("aAazz", "aAazz");
2197        assert_pattern!("A12b123", NOT "A12b12");
2198        assert_pattern!("a12B12", "a12B12");
2199        assert_pattern!("oWn", "oWn");
2200        assert_pattern!("bLah", "bLah");
2201        assert_pattern!("bLaH", NOT "bLah");
2202
2203        // Single '?' cases.
2204        assert_pattern!("a", "a");
2205        assert_pattern!("a?", "ab");
2206        assert_pattern!("ab?", "abc");
2207
2208        // Mixed '?' cases.
2209        assert_pattern!("??", NOT "a");
2210        assert_pattern!("??", "ab");
2211        assert_pattern!("???", "abc");
2212        assert_pattern!("????", "abcd");
2213        assert_pattern!("????", NOT "abc");
2214        assert_pattern!("?b??", "abcd");
2215        assert_pattern!("?a??", NOT "abcd");
2216        assert_pattern!("??c?", "abcd");
2217        assert_pattern!("??d?", NOT "abcd");
2218        assert_pattern!("?b?d*?", "abcde");
2219
2220        // Longer string scenarios.
2221        assert_pattern!(
2222            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
2223            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
2224        );
2225        assert_pattern!(
2226            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
2227            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2228        );
2229        assert_pattern!(
2230            "abababababababababababababababababababaacacacacacacacadaeafagahaiajaxalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
2231            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2232        );
2233        assert_pattern!(
2234            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaggggagaaaaaaaab",
2235            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2236        );
2237        assert_pattern!(
2238            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
2239            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
2240        );
2241        assert_pattern!("aaabbaabbaab", "aaabbaabbaab");
2242        assert_pattern!(
2243            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
2244            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
2245        );
2246        assert_pattern!("aaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaa");
2247        assert_pattern!("aaaaaaaaaaaaaaaaa", NOT "aaaaaaaaaaaaaaaa");
2248        assert_pattern!(
2249            "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc",
2250            NOT "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn"
2251        );
2252        assert_pattern!(
2253            "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn",
2254            "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn"
2255        );
2256        assert_pattern!("abcabc?abcabcabc", NOT "abcabcdabcdabcabcd");
2257        assert_pattern!(
2258            "abcabc?abc?abcabc?abc?abc?bc?abc?bc?bcd",
2259            "abcabcdabcdabcabcdabcdabcabcdabcabcabcd"
2260        );
2261        assert_pattern!("?abc?", "?abc?");
2262    }
2263
2264    #[test]
2265    fn test_builder_complexity() {
2266        assert!(
2267            Pattern::builder("{foo,bar}")
2268                .max_complexity(1)
2269                .build()
2270                .is_err()
2271        );
2272        assert!(
2273            Pattern::builder("{foo,bar}")
2274                .max_complexity(2)
2275                .build()
2276                .is_ok()
2277        );
2278        assert!(
2279            Pattern::builder("{foo,bar}/{*.html,*.js,*.css}")
2280                .max_complexity(5)
2281                .build()
2282                .is_err()
2283        );
2284        assert!(
2285            Pattern::builder("{foo,bar}/{*.html,*.js,*.css}")
2286                .max_complexity(6)
2287                .build()
2288                .is_ok()
2289        );
2290    }
2291
2292    #[test]
2293    fn test_patterns() {
2294        let patterns = patterns!("foobaR", "a*", "*a", "[0-9]*baz");
2295
2296        assert!(patterns.is_match("foobaR"));
2297        assert!(patterns.is_match("abc"));
2298        assert!(patterns.is_match("cba"));
2299        assert!(patterns.is_match("3baz"));
2300        assert!(patterns.is_match("123456789baz"));
2301        assert!(!patterns.is_match("foobar"));
2302        assert!(!patterns.is_match("FOOBAR"));
2303    }
2304
2305    #[test]
2306    fn test_patterns_case_insensitive() {
2307        let patterns = patterns!("fOObar", "a*", "*a", "[0-9]*baz", @ i);
2308
2309        assert!(patterns.is_match("FooBar"));
2310        assert!(patterns.is_match("abC"));
2311        assert!(patterns.is_match("cbA"));
2312        assert!(patterns.is_match("3BAZ"));
2313        assert!(patterns.is_match("123456789baz"));
2314        assert!(!patterns.is_match("b"));
2315    }
2316
2317    #[test]
2318    fn test_patterns_take_clears_builder() {
2319        let mut builder = Patterns::builder().add("foo").unwrap();
2320
2321        let patterns = builder.take();
2322        assert_eq!(patterns, patterns!("foo"));
2323        assert!(patterns.is_match("foo"));
2324        assert!(!patterns.is_match("bar"));
2325
2326        builder.add("bar").unwrap();
2327        let patterns = builder.build();
2328        assert_eq!(patterns, patterns!("bar"));
2329        assert!(!patterns.is_match("foo"));
2330        assert!(patterns.is_match("bar"));
2331    }
2332
2333    #[test]
2334    fn test_pattern_eq() {
2335        let pattern1 = pattern!("Foo**", i);
2336        let pattern2 = pattern!("Foo**", i);
2337        let pattern3 = pattern!("foo*", i);
2338        assert_eq!(&pattern1, &pattern1);
2339        assert_eq!(&pattern1, &pattern2);
2340        assert_eq!(&pattern1, &pattern3);
2341        assert_eq!(&pattern2, &pattern3);
2342
2343        let pattern = Pattern::builder("foo*").max_complexity(1).build().unwrap();
2344        assert_eq!(pattern, Pattern::new("foo*").unwrap());
2345    }
2346
2347    #[test]
2348    fn test_pattern_neq() {
2349        assert_ne!(pattern!("Foo**"), pattern!("foo*"));
2350        assert_ne!(pattern!("foo*"), pattern!("foo*", i));
2351        assert_ne!(pattern!("foo*"), pattern!("bar*"));
2352    }
2353
2354    #[test]
2355    fn test_patterns_eq() {
2356        let patterns1 = patterns!("Foo**", "*[rt]X", @ i);
2357        let patterns2 = patterns1.clone();
2358        let patterns3 = patterns!("foo*", "*[rt]x", @ i);
2359        assert_eq!(&patterns1, &patterns1);
2360        assert_eq!(&patterns1, &patterns2);
2361        assert_eq!(&patterns1, &patterns3);
2362        assert_eq!(&patterns2, &patterns3);
2363        assert_eq!(Patterns::empty(), patterns!());
2364    }
2365
2366    #[test]
2367    fn test_patterns_neq() {
2368        let patterns = patterns!("foo*", "bar");
2369        let case_insensitive = patterns!("foo*", "bar", @ i);
2370        let reordered = patterns!("bar", "foo*");
2371        assert_ne!(patterns, case_insensitive);
2372        assert_ne!(patterns, reordered);
2373        assert_ne!(patterns, patterns!("foo*"));
2374        assert_ne!(patterns, patterns!());
2375        assert_ne!(patterns!(), patterns!(@ i));
2376    }
2377
2378    #[test]
2379    #[cfg(feature = "serde")]
2380    fn test_pattern_deserialize() {
2381        let pattern: Pattern = serde_json::from_str(r#""**[rt]x""#).unwrap();
2382        assert_eq!(pattern, Pattern::new("*[rt]x").unwrap());
2383        assert!(pattern.is_match("foobar_rx"));
2384        assert!(pattern.is_match("foobar_tx"));
2385        assert!(!pattern.is_match("foobar_RX"));
2386        assert!(!pattern.is_match("foobar"));
2387    }
2388
2389    #[test]
2390    #[cfg(feature = "serde")]
2391    fn test_pattern_deserialize_err() {
2392        for json in [r#""[invalid""#, "null", "true", "42", "[]", "{}"] {
2393            assert!(serde_json::from_str::<Pattern>(json).is_err(), "{json}");
2394        }
2395    }
2396
2397    #[test]
2398    #[cfg(feature = "serde")]
2399    fn test_pattern_serialize() {
2400        for (source, expected) in [
2401            ("", r#""""#),
2402            ("**", r#""*""#),
2403            ("Foobar", r#""Foobar""#),
2404            ("Foo**", r#""Foo*""#),
2405            ("**Bar", r#""*Bar""#),
2406            ("**Foo**", r#""*Foo*""#),
2407            ("*[rt]x", r#""*[rt]x""#),
2408            (r"f\*o", r#""f\\*o""#),
2409            (r#"f"o"#, r#""f\"o""#),
2410        ] {
2411            let pattern = Pattern::new(source).unwrap();
2412            assert_eq!(serde_json::to_string(&pattern).unwrap(), expected);
2413        }
2414
2415        let pattern = pattern!("Foo**", i);
2416        assert_eq!(serde_json::to_string(&pattern).unwrap(), r#""foo*""#);
2417    }
2418
2419    #[test]
2420    #[cfg(feature = "serde")]
2421    fn test_pattern_serde_roundtrip() {
2422        for source in [
2423            "",
2424            "*",
2425            "Foobar",
2426            "Foo**",
2427            "*Bar",
2428            "*Foo*",
2429            "*[rt]x",
2430            "{foo,bar}",
2431            r"f\*o",
2432            r#"f"o"#,
2433            "Grüße",
2434        ] {
2435            let pattern = Pattern::new(source).unwrap();
2436            let json = serde_json::to_string(&pattern).unwrap();
2437            let deserialized: Pattern = serde_json::from_str(&json).unwrap();
2438            assert_eq!(pattern, deserialized);
2439        }
2440    }
2441
2442    #[test]
2443    #[cfg(feature = "serde")]
2444    fn test_patterns_deserialize() {
2445        let patterns: Patterns = serde_json::from_str(r#"["**[rt]x","Foobar"]"#).unwrap();
2446        let expected = patterns!("*[rt]x", "Foobar");
2447        assert_eq!(patterns, expected);
2448        assert!(patterns.is_match("foobar_rx"));
2449        assert!(patterns.is_match("Foobar"));
2450        assert!(!patterns.is_match("foobar_RX"));
2451        assert!(!patterns.is_match("FOOBAR"));
2452    }
2453
2454    #[test]
2455    #[cfg(feature = "serde")]
2456    fn test_patterns_deserialize_err() {
2457        for json in [
2458            r#"["[invalid","foobar"]"#,
2459            r#"["foobar","[invalid"]"#,
2460            r#"["foobar",42]"#,
2461            r#"["foobar",null]"#,
2462            r#"["foobar",[]]"#,
2463            r#""foobar""#,
2464            "null",
2465            "true",
2466            "42",
2467            "{}",
2468        ] {
2469            assert!(serde_json::from_str::<Patterns>(json).is_err());
2470        }
2471    }
2472
2473    #[test]
2474    #[cfg(feature = "serde")]
2475    fn test_patterns_serialize() {
2476        let p = patterns!(
2477            "", "**", "Foobar", "Foo**", "**Bar", "**Foo**", "*[rt]x", r"f\*o",
2478        );
2479        assert_eq!(
2480            serde_json::to_string(&p).unwrap(),
2481            r#"["","*","Foobar","Foo*","*Bar","*Foo*","*[rt]x","f\\*o"]"#,
2482        );
2483
2484        let p = patterns!(
2485            "", "**", "Foobar", "Foo**", "**Bar", "**Foo**", "*[rt]x", r"f\*o", @ i
2486        );
2487        assert_eq!(
2488            serde_json::to_string(&p).unwrap(),
2489            r#"["","*","foobar","foo*","*bar","*foo*","*[rt]x","f\\*o"]"#,
2490        );
2491    }
2492
2493    #[test]
2494    #[cfg(feature = "serde")]
2495    fn test_patterns_serde_empty() {
2496        let patterns: Patterns = serde_json::from_str("[]").unwrap();
2497        assert_eq!(patterns, patterns!());
2498        assert!(patterns.is_empty());
2499        assert!(!patterns.is_match(""));
2500        assert!(!patterns.is_match("foobar"));
2501        assert_eq!(serde_json::to_string(&patterns).unwrap(), "[]");
2502    }
2503}
relay_pattern/lib.rs

relay_pattern/
lib.rs
