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::borrow::Borrow;
41use std::fmt;
42use std::num::NonZeroUsize;
43
44mod typed;
45mod wildmatch;
46
47pub use typed::*;
48
49/// Pattern parsing error.
50#[derive(Debug)]
51pub struct Error {
52    pattern: String,
53    kind: ErrorKind,
54}
55
56#[derive(Debug)]
57enum ErrorKind {
58    /// The specified range is invalid. The `end` character is lexicographically
59    /// after the `start` character.
60    InvalidRange(char, char),
61    /// Unbalanced character class. The pattern contains unbalanced `[`, `]` characters.
62    UnbalancedCharacterClass,
63    /// Character class is invalid and cannot be parsed.
64    InvalidCharacterClass,
65    /// Nested alternates are not valid.
66    NestedAlternates,
67    /// Unbalanced alternates. The pattern contains unbalanced `{`, `}` characters.
68    UnbalancedAlternates,
69    /// Dangling escape character.
70    DanglingEscape,
71    /// The pattern's complexity exceeds the maximum allowed complexity.
72    Complexity {
73        complexity: u64,
74        max_complexity: u64,
75    },
76}
77
78impl std::error::Error for Error {}
79
80impl fmt::Display for Error {
81    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
82        write!(f, "Error parsing pattern '{}': ", self.pattern)?;
83        match &self.kind {
84            ErrorKind::InvalidRange(start, end) => {
85                write!(f, "Invalid character range `{start}-{end}`")
86            }
87            ErrorKind::UnbalancedCharacterClass => write!(f, "Unbalanced character class"),
88            ErrorKind::InvalidCharacterClass => write!(f, "Invalid character class"),
89            ErrorKind::NestedAlternates => write!(f, "Nested alternates"),
90            ErrorKind::UnbalancedAlternates => write!(f, "Unbalanced alternates"),
91            ErrorKind::DanglingEscape => write!(f, "Dangling escape"),
92            ErrorKind::Complexity {
93                complexity,
94                max_complexity,
95            } => write!(
96                f,
97                "Pattern complexity ({complexity}) exceeds maximum allowed complexity ({max_complexity})"
98            ),
99        }
100    }
101}
102
103/// `Pattern` represents a successfully parsed Relay pattern.
104#[derive(Debug, Clone)]
105pub struct Pattern {
106    pattern: String,
107    options: Options,
108    strategy: MatchStrategy,
109}
110
111impl Pattern {
112    /// Create a new [`Pattern`] from a string with the default settings.
113    pub fn new(pattern: &str) -> Result<Self, Error> {
114        Self::builder(pattern).build()
115    }
116
117    /// Create a new [`PatternBuilder`]. The builder can be used to adjust the
118    /// pattern settings.
119    pub fn builder(pattern: &str) -> PatternBuilder<'_> {
120        PatternBuilder {
121            pattern,
122            options: Options::default(),
123            max_complexity: u64::MAX,
124        }
125    }
126
127    /// Returns `true` if the pattern matches the passed string.
128    pub fn is_match(&self, haystack: &str) -> bool {
129        self.strategy.is_match(haystack, self.options)
130    }
131}
132
133impl fmt::Display for Pattern {
134    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
135        f.write_str(&self.pattern)
136    }
137}
138
139impl PartialEq for Pattern {
140    fn eq(&self, other: &Self) -> bool {
141        self.pattern == other.pattern
142    }
143}
144
145impl Eq for Pattern {}
146
147impl Borrow<str> for Pattern {
148    fn borrow(&self) -> &str {
149        &self.pattern
150    }
151}
152
153impl std::hash::Hash for Pattern {
154    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
155        self.pattern.hash(state);
156    }
157}
158
159#[cfg(feature = "serde")]
160impl serde::Serialize for Pattern {
161    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
162    where
163        S: serde::Serializer,
164    {
165        serializer.serialize_str(&self.pattern)
166    }
167}
168
169#[cfg(feature = "serde")]
170impl<'de> serde::Deserialize<'de> for Pattern {
171    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
172    where
173        D: serde::Deserializer<'de>,
174    {
175        let pattern = String::deserialize(deserializer)?;
176        Pattern::new(&pattern).map_err(serde::de::Error::custom)
177    }
178}
179
180/// A collection of [`Pattern`]s sharing the same configuration.
181#[derive(Debug, Clone)]
182pub struct Patterns {
183    strategies: Vec<MatchStrategy>,
184    options: Options,
185}
186
187impl Patterns {
188    /// Creates an empty [`Patterns`] instance which never matches anything.
189    ///
190    /// ```
191    /// # use relay_pattern::Patterns;
192    /// let patterns = Patterns::empty();
193    ///
194    /// assert!(!patterns.is_match(""));
195    /// assert!(!patterns.is_match("foobar"));
196    /// ```
197    pub fn empty() -> Self {
198        Self {
199            strategies: Vec::new(),
200            options: Options::default(),
201        }
202    }
203
204    /// Returns a [`PatternsBuilder`].
205    pub fn builder() -> PatternsBuilder {
206        PatternsBuilder {
207            options: Options::default(),
208        }
209    }
210
211    /// Returns `true` if any of the contained patterns matches the passed string.
212    pub fn is_match(&self, haystack: &str) -> bool {
213        self.strategies
214            .iter()
215            .any(|s| s.is_match(haystack, self.options))
216    }
217
218    /// Returns `true` if this instance contains no patterns.
219    ///
220    /// An empty [`Patterns`] never matches any input.
221    pub fn is_empty(&self) -> bool {
222        self.strategies.is_empty()
223    }
224}
225
226/// A builder for a [`Pattern`].
227#[derive(Debug)]
228pub struct PatternBuilder<'a> {
229    pattern: &'a str,
230    max_complexity: u64,
231    options: Options,
232}
233
234impl PatternBuilder<'_> {
235    /// If enabled matches the pattern case insensitive.
236    ///
237    /// This is disabled by default.
238    pub fn case_insensitive(&mut self, enabled: bool) -> &mut Self {
239        self.options.case_insensitive = enabled;
240        self
241    }
242
243    /// Sets the max complexity for this pattern.
244    ///
245    /// Attempting to build a pattern with a complexity higher
246    /// than the maximum specified here will fail.
247    ///
248    /// Defaults to `u64::MAX`.
249    pub fn max_complexity(&mut self, max_complexity: u64) -> &mut Self {
250        self.max_complexity = max_complexity;
251        self
252    }
253
254    /// Build a new [`Pattern`] from the passed pattern and configured options.
255    pub fn build(&self) -> Result<Pattern, Error> {
256        let mut parser = Parser::new(self.pattern, self.options);
257        parser.parse().map_err(|kind| Error {
258            pattern: self.pattern.to_owned(),
259            kind,
260        })?;
261
262        if parser.complexity > self.max_complexity {
263            return Err(Error {
264                pattern: self.pattern.to_owned(),
265                kind: ErrorKind::Complexity {
266                    complexity: parser.complexity,
267                    max_complexity: self.max_complexity,
268                },
269            });
270        }
271
272        let strategy =
273            MatchStrategy::from_tokens(parser.tokens, self.options).map_err(|kind| Error {
274                pattern: self.pattern.to_owned(),
275                kind,
276            })?;
277
278        Ok(Pattern {
279            pattern: self.pattern.to_owned(),
280            options: self.options,
281            strategy,
282        })
283    }
284}
285
286/// A builder for a collection of [`Patterns`].
287#[derive(Debug)]
288pub struct PatternsBuilder {
289    options: Options,
290}
291
292impl PatternsBuilder {
293    /// If enabled matches the pattern case insensitive.
294    ///
295    /// This is disabled by default.
296    pub fn case_insensitive(&mut self, enabled: bool) -> &mut Self {
297        self.options.case_insensitive = enabled;
298        self
299    }
300
301    /// Returns a [`PatternsBuilderConfigured`] builder which allows adding patterns.
302    pub fn patterns(&mut self) -> PatternsBuilderConfigured {
303        PatternsBuilderConfigured {
304            strategies: Vec::new(),
305            options: self.options,
306        }
307    }
308
309    /// Adds a pattern to the builder and returns the resulting [`PatternsBuilderConfigured`].
310    pub fn add(&mut self, pattern: &str) -> Result<PatternsBuilderConfigured, Error> {
311        let mut builder = PatternsBuilderConfigured {
312            strategies: Vec::with_capacity(1),
313            options: self.options,
314        };
315        builder.add(pattern)?;
316        Ok(builder)
317    }
318}
319
320/// A [`PatternsBuilder`] with all options configured.
321///
322/// The second step after [`PatternsBuilder`].
323#[derive(Debug)]
324pub struct PatternsBuilderConfigured {
325    strategies: Vec<MatchStrategy>,
326    options: Options,
327}
328
329impl PatternsBuilderConfigured {
330    /// Adds a pattern to the builder.
331    pub fn add(&mut self, pattern: &str) -> Result<&mut Self, Error> {
332        let mut parser = Parser::new(pattern, self.options);
333        parser.parse().map_err(|kind| Error {
334            pattern: pattern.to_owned(),
335            kind,
336        })?;
337
338        let strategy =
339            MatchStrategy::from_tokens(parser.tokens, self.options).map_err(|kind| Error {
340                pattern: pattern.to_owned(),
341                kind,
342            })?;
343
344        self.strategies.push(strategy);
345
346        Ok(self)
347    }
348
349    /// Builds a [`Patterns`] from the contained patterns.
350    pub fn build(self) -> Patterns {
351        Patterns {
352            strategies: self.strategies,
353            options: self.options,
354        }
355    }
356
357    /// Returns [`Patterns`] containing all added patterns and removes them from the builder.
358    ///
359    /// The builder can still be used afterwards, it keeps the configuration.
360    pub fn take(&mut self) -> Patterns {
361        Patterns {
362            strategies: std::mem::take(&mut self.strategies),
363            options: self.options,
364        }
365    }
366}
367
368/// Options to influence [`Pattern`] matching behaviour.
369#[derive(Debug, Clone, Copy, Default)]
370struct Options {
371    case_insensitive: bool,
372}
373
374/// Matching strategy for a [`Pattern`].
375///
376/// Certain patterns can be matched more efficiently while the complex
377/// patterns fallback to [`wildmatch::is_match`].
378#[derive(Debug, Clone)]
379enum MatchStrategy {
380    /// The pattern is a single literal string.
381    ///
382    /// The stored string is converted to lowercase for case insensitive patterns.
383    ///
384    /// Example pattern: `foobar`.
385    Literal(Literal),
386    /// The pattern only has a single wildcard in the end and can be
387    /// matched with a simple prefix check.
388    ///
389    /// The stored string is converted to lowercase for case insensitive patterns.
390    ///
391    /// Example pattern: `foobar*`.
392    Prefix(Literal),
393    /// The pattern only has a single wildcard at the start and can be
394    /// matched with a simple suffix check.
395    ///
396    /// The stored string is converted to lowercase for case insensitive patterns.
397    ///
398    /// Example pattern: `*foobar`.
399    Suffix(Literal),
400    /// The pattern is surrounded with wildcards and contains a literal in the middle
401    /// and can be matched with a simple contains check.
402    ///
403    /// The stored string is converted to lowercase for case insensitive patterns.
404    ///
405    /// Example pattern: `*foobar*`.
406    Contains(Literal),
407    /// The pattern always evaluates to a static boolean.
408    ///
409    /// Example: `*`
410    Static(bool),
411    /// The pattern is complex and needs to be evaluated using [`wildmatch`].
412    Wildmatch(Tokens),
413    // Possible future optimizations for `Any` variations:
414    // Examples: `??`. `??suffix`, `prefix??` and `?contains?`.
415}
416
417impl MatchStrategy {
418    /// Create a [`MatchStrategy`] from [`Tokens`].
419    fn from_tokens(mut tokens: Tokens, _options: Options) -> Result<Self, ErrorKind> {
420        let s = match tokens.as_mut_slice() {
421            [] => Self::Static(false),
422            [Token::Wildcard] => Self::Static(true),
423            [Token::Literal(literal)] => Self::Literal(std::mem::take(literal)),
424            [Token::Literal(literal), Token::Wildcard] => Self::Prefix(std::mem::take(literal)),
425            [Token::Wildcard, Token::Literal(literal)] => Self::Suffix(std::mem::take(literal)),
426            [Token::Wildcard, Token::Literal(literal), Token::Wildcard] => {
427                Self::Contains(std::mem::take(literal))
428            }
429            _ => Self::Wildmatch(tokens),
430        };
431
432        Ok(s)
433    }
434
435    /// Returns `true` if the pattern matches the passed string.
436    pub fn is_match(&self, haystack: &str, options: Options) -> bool {
437        match &self {
438            MatchStrategy::Literal(literal) => match_literal(literal, haystack, options),
439            MatchStrategy::Prefix(prefix) => match_prefix(prefix, haystack, options),
440            MatchStrategy::Suffix(suffix) => match_suffix(suffix, haystack, options),
441            MatchStrategy::Contains(contains) => match_contains(contains, haystack, options),
442            MatchStrategy::Static(matches) => *matches,
443            MatchStrategy::Wildmatch(tokens) => wildmatch::is_match(haystack, tokens, options),
444        }
445    }
446}
447
448#[inline(always)]
449fn match_literal(literal: &Literal, haystack: &str, options: Options) -> bool {
450    if options.case_insensitive {
451        // Can't do an explicit len compare first here `literal.len() == haystack.len()`,
452        // the amount of characters can change when converting case.
453        let mut literal = literal.as_case_converted_str().chars();
454        let mut haystack = haystack.chars().flat_map(|c| c.to_lowercase());
455
456        loop {
457            match (literal.next(), haystack.next()) {
458                // Both iterators exhausted -> literal matches.
459                (None, None) => break true,
460                // Either iterator exhausted while the other one is not -> no match.
461                (None, _) | (_, None) => break false,
462                (Some(p), Some(h)) if p != h => break false,
463                _ => {}
464            }
465        }
466    } else {
467        literal.as_case_converted_str() == haystack
468    }
469}
470
471#[inline(always)]
472fn match_prefix(prefix: &Literal, haystack: &str, options: Options) -> bool {
473    if options.case_insensitive {
474        let mut prefix = prefix.as_case_converted_str().chars();
475        let mut haystack = haystack.chars().flat_map(|c| c.to_lowercase());
476
477        loop {
478            match (prefix.next(), haystack.next()) {
479                // If the prefix is exhausted it matched.
480                (None, _) => break true,
481                // If the haystack is exhausted, but the pattern is not -> no match.
482                (Some(_), None) => break false,
483                (Some(p), Some(h)) if p != h => break false,
484                _ => {}
485            }
486        }
487    } else {
488        haystack.starts_with(prefix.as_case_converted_str())
489    }
490}
491
492#[inline(always)]
493fn match_suffix(suffix: &Literal, haystack: &str, options: Options) -> bool {
494    if options.case_insensitive {
495        let mut suffix = suffix.as_case_converted_str().chars().rev();
496        let mut haystack = haystack.chars().flat_map(|c| c.to_lowercase()).rev();
497
498        loop {
499            match (suffix.next(), haystack.next()) {
500                // If the prefix is exhausted it matched.
501                (None, _) => break true,
502                // If the haystack is exhausted, but the pattern is not -> no match.
503                (Some(_), None) => break false,
504                (Some(s), Some(h)) if s != h => break false,
505                _ => {}
506            }
507        }
508    } else {
509        haystack.ends_with(suffix.as_case_converted_str())
510    }
511}
512
513#[inline(always)]
514fn match_contains(contains: &Literal, haystack: &str, options: Options) -> bool {
515    if options.case_insensitive {
516        let haystack = haystack.to_lowercase();
517        memchr::memmem::find(haystack.as_bytes(), contains.as_case_converted_bytes()).is_some()
518    } else {
519        memchr::memmem::find(haystack.as_bytes(), contains.as_case_converted_bytes()).is_some()
520    }
521}
522
523struct Parser<'a> {
524    chars: std::iter::Peekable<std::str::Chars<'a>>,
525    tokens: Tokens,
526    alternates: Option<Vec<Tokens>>,
527    current_literal: Option<String>,
528    options: Options,
529    complexity: u64,
530}
531
532impl<'a> Parser<'a> {
533    fn new(pattern: &'a str, options: Options) -> Self {
534        Self {
535            chars: pattern.chars().peekable(),
536            tokens: Default::default(),
537            alternates: None,
538            current_literal: None,
539            options,
540            complexity: 0,
541        }
542    }
543
544    fn parse(&mut self) -> Result<(), ErrorKind> {
545        while let Some(c) = self.advance() {
546            match c {
547                '?' => self.push_token(Token::Any(NonZeroUsize::MIN)),
548                '*' => self.push_token(Token::Wildcard),
549                '[' => self.parse_class()?,
550                ']' => return Err(ErrorKind::UnbalancedCharacterClass),
551                '{' => self.start_alternates()?,
552                '}' => self.end_alternates()?,
553                '\\' => match self.advance() {
554                    Some(c) => self.push_literal(c),
555                    None => return Err(ErrorKind::DanglingEscape),
556                },
557                ',' if self.alternates.is_some() => {
558                    self.finish_literal();
559                    // safe to unwrap, we just checked for `some`.
560                    let alternates = self.alternates.as_mut().unwrap();
561                    alternates.push(Tokens::default());
562                }
563                c => self.push_literal(c),
564            }
565        }
566
567        // Finish off the parsing with creating a token for any remaining literal buffered.
568        self.finish_literal();
569
570        Ok(())
571    }
572
573    fn start_alternates(&mut self) -> Result<(), ErrorKind> {
574        if self.alternates.is_some() {
575            return Err(ErrorKind::NestedAlternates);
576        }
577        self.finish_literal();
578        self.alternates = Some(vec![Tokens::default()]);
579        Ok(())
580    }
581
582    fn end_alternates(&mut self) -> Result<(), ErrorKind> {
583        self.finish_literal();
584        match self.alternates.take() {
585            None => return Err(ErrorKind::UnbalancedAlternates),
586            Some(alternates) => {
587                if !alternates.is_empty() {
588                    self.complexity = self
589                        .complexity
590                        .max(1)
591                        .saturating_mul(alternates.len() as u64);
592                    self.push_token(Token::Alternates(alternates));
593                }
594            }
595        }
596
597        Ok(())
598    }
599
600    fn parse_class(&mut self) -> Result<(), ErrorKind> {
601        let negated = self.advance_if(|c| c == '!');
602
603        let mut ranges = Ranges::default();
604
605        let mut first = true;
606        let mut in_range = false;
607        loop {
608            let Some(c) = self.advance() else {
609                return Err(ErrorKind::UnbalancedCharacterClass);
610            };
611
612            match c {
613                // Another opening bracket is invalid, literal `[` need to be escaped.
614                '[' => return Err(ErrorKind::InvalidCharacterClass),
615                ']' => break,
616                '-' => {
617                    if first {
618                        ranges.push(Range::single('-'));
619                    } else if in_range {
620                        // safe to unwrap, `in_range` is only true if there is already
621                        // a range pushed.
622                        ranges.last_mut().unwrap().set_end('-')?;
623                        in_range = false;
624                    } else {
625                        assert!(!ranges.is_empty());
626                        in_range = true;
627                    }
628                }
629                c => {
630                    let c = match c {
631                        '\\' => self.advance().ok_or(ErrorKind::DanglingEscape)?,
632                        c => c,
633                    };
634
635                    if in_range {
636                        // safe to unwrap, `in_range` is only true if there is already
637                        // a range pushed.
638                        ranges.last_mut().unwrap().set_end(c)?;
639                        in_range = false;
640                    } else {
641                        ranges.push(Range::single(c))
642                    }
643                }
644            }
645
646            first = false;
647        }
648
649        if in_range {
650            // A pattern which ends with a `-`.
651            ranges.push(Range::single('-'));
652        }
653
654        self.push_token(Token::Class { negated, ranges });
655
656        Ok(())
657    }
658
659    /// Pushes a new character into the currently active literal token.
660    ///
661    /// Starts a new literal token if there is none already.
662    fn push_literal(&mut self, c: char) {
663        self.current_literal.get_or_insert_with(String::new).push(c);
664    }
665
666    /// Finishes and pushes the currently in progress literal token.
667    fn finish_literal(&mut self) {
668        if let Some(literal) = self.current_literal.take() {
669            self.push_token(Token::Literal(Literal::new(literal, self.options)));
670        }
671    }
672
673    /// Pushes the passed `token` and finishes the currently in progress literal token.
674    fn push_token(&mut self, token: Token) {
675        self.finish_literal();
676        match self.alternates.as_mut() {
677            Some(alternates) => match alternates.last_mut() {
678                Some(tokens) => tokens.push(token),
679                None => {
680                    let mut tokens = Tokens::default();
681                    tokens.push(token);
682                    alternates.push(tokens);
683                }
684            },
685            None => self.tokens.push(token),
686        }
687    }
688
689    fn advance(&mut self) -> Option<char> {
690        self.chars.next()
691    }
692
693    fn advance_if(&mut self, matcher: impl FnOnce(char) -> bool) -> bool {
694        if self.peek().is_some_and(matcher) {
695            let _ = self.advance();
696            true
697        } else {
698            false
699        }
700    }
701
702    fn peek(&mut self) -> Option<char> {
703        self.chars.peek().copied()
704    }
705}
706
707/// A container of tokens.
708///
709/// Automatically folds redundant tokens.
710///
711/// The contained tokens are guaranteed to uphold the following invariants:
712/// - A [`Token::Wildcard`] is never followed by [`Token::Wildcard`].
713/// - A [`Token::Any`] is never followed by [`Token::Any`].
714/// - A [`Token::Literal`] is never followed by [`Token::Literal`].
715/// - A [`Token::Class`] is never empty.
716#[derive(Clone, Debug, Default)]
717struct Tokens(Vec<Token>);
718
719impl Tokens {
720    fn push(&mut self, mut token: Token) {
721        // Normalize / clean the token.
722        if let Token::Alternates(mut alternates) = token {
723            let mut contains_empty = false;
724            let mut contains_wildcard = false;
725            alternates.retain_mut(|alternate| {
726                if alternate.0.is_empty() {
727                    contains_empty = true;
728                    return false;
729                }
730
731                if matches!(alternate.0.as_slice(), [Token::Wildcard]) {
732                    contains_wildcard = true;
733                }
734
735                true
736            });
737
738            // At this point `alternates` contains only the nonempty branches
739            // and we additionally know
740            // * if one of the branches was just a wildcard
741            // * if there were any empty branches.
742            //
743            // We can push different tokens based on this.
744            if contains_wildcard {
745                // Case: {foo,*,} -> reduces to *
746                token = Token::Wildcard;
747            } else if alternates.len() == 1 {
748                if contains_empty {
749                    // Case: {foo*bar,} -> Optional(foo*bar)
750                    token = Token::Optional(alternates.remove(0));
751                } else {
752                    // Case: {foo*bar} -> remove the alternation and
753                    // push foo*bar directly
754                    for t in alternates.remove(0).0 {
755                        self.push(t);
756                    }
757                    return;
758                }
759            } else if alternates.len() > 1 {
760                if contains_empty {
761                    // Case: {foo,bar,} -> Optional({foo,bar})
762                    token = Token::Optional(Tokens(vec![Token::Alternates(alternates)]));
763                } else {
764                    // Case: {foo, bar} -> can stay as it is
765                    token = Token::Alternates(alternates);
766                }
767            } else {
768                // Case: {,,,} -> reduces to {}
769                return;
770            }
771        }
772
773        match (self.0.last_mut(), token) {
774            // Collapse Any's.
775            (Some(Token::Any(n)), Token::Any(n2)) => *n = n.saturating_add(n2.get()),
776            // We can collapse multiple wildcards into a single one.
777            // TODO: separator special handling (?)
778            (Some(Token::Wildcard), Token::Wildcard) => {}
779            // Collapse multiple literals into one.
780            (Some(Token::Literal(last)), Token::Literal(s)) => last.push(&s),
781            // Ignore empty class tokens.
782            (_, Token::Class { negated: _, ranges }) if ranges.is_empty() => {}
783            // Everything else is just another token.
784            (_, token) => self.0.push(token),
785        }
786    }
787
788    fn as_mut_slice(&mut self) -> &mut [Token] {
789        self.0.as_mut_slice()
790    }
791
792    fn as_slice(&self) -> &[Token] {
793        self.0.as_slice()
794    }
795}
796
797/// Represents a token in a Relay pattern.
798#[derive(Clone, Debug)]
799enum Token {
800    /// A literal token.
801    Literal(Literal),
802    /// The any token `?` and how many `?` are seen in a row.
803    Any(NonZeroUsize),
804    /// The wildcard token `*`.
805    Wildcard,
806    /// A class token `[abc]` or its negated variant `[!abc]`.
807    Class { negated: bool, ranges: Ranges },
808    /// A list of nested alternate tokens `{a,b}`.
809    Alternates(Vec<Tokens>),
810    /// A list of optional tokens.
811    ///
812    /// This has no syntax of its own, it's parsed
813    /// from alternatives containing empty branches
814    /// like `{a,b,}`.
815    Optional(Tokens),
816}
817
818/// A string literal.
819///
820/// The contained literal is only available as a case converted string.
821/// Depending on whether the pattern is case sensitive or case insensitive the literal is either
822/// the original string or converted to lowercase.
823#[derive(Clone, Debug, Default)]
824struct Literal(String);
825
826impl Literal {
827    /// Creates a new literal from `s` and `options`.
828    fn new(s: String, options: Options) -> Self {
829        match options.case_insensitive {
830            false => Self(s),
831            true => Self(s.to_lowercase()),
832        }
833    }
834
835    /// Adds a literal to this literal.
836    ///
837    /// This function does not validate case conversion, both literals must be for the same caseing.
838    fn push(&mut self, Literal(other): &Literal) {
839        self.0.push_str(other);
840    }
841
842    /// Returns a reference to the case converted string.
843    fn as_case_converted_str(&self) -> &str {
844        &self.0
845    }
846
847    /// Returns a reference to the case converted string as bytes.
848    fn as_case_converted_bytes(&self) -> &[u8] {
849        self.as_case_converted_str().as_bytes()
850    }
851}
852
853/// A [`Range`] contains whatever is contained between `[` and `]` of
854/// a glob pattern, except the negation.
855///
856/// For example the pattern `[a-z]` contains the range from `a` to `z`,
857/// the pattern `[ax-zbf-h]` contains the ranges `x-z`, `f-h`, `a-a` and `b-b`.
858#[derive(Clone, Debug, Default)]
859enum Ranges {
860    /// An empty, default range not containing any characters.
861    ///
862    /// The empty range matches nothing.
863    #[default]
864    Empty,
865    /// The pattern only contains a single range.
866    ///
867    /// For example: `[a]` or `[a-z]`.
868    Single(Range),
869    /// The pattern contains more than one range.
870    ///
871    /// The `Empty` and `Single` states are just explicit and optimized
872    /// cases for `Multiple` with a vector containing zero or just one range.
873    Multiple(Vec<Range>),
874}
875
876impl Ranges {
877    /// Pushes another range into the current [`Range`].
878    ///
879    /// Returns [`Error`] if the range starts with a lexicographically larger character than it
880    /// ends with.
881    fn push(&mut self, range: Range) {
882        match self {
883            Self::Empty => *self = Self::Single(range),
884            Self::Single(single) => *self = Self::Multiple(vec![*single, range]),
885            Self::Multiple(v) => v.push(range),
886        }
887    }
888
889    /// Returns a mutable reference to the last range contained.
890    fn last_mut(&mut self) -> Option<&mut Range> {
891        match self {
892            Ranges::Empty => None,
893            Ranges::Single(range) => Some(range),
894            Ranges::Multiple(ranges) => ranges.last_mut(),
895        }
896    }
897
898    /// Returns `true` if there is no contained range.
899    fn is_empty(&self) -> bool {
900        match self {
901            Ranges::Empty => true,
902            Ranges::Single(_) => false,
903            Ranges::Multiple(ranges) => {
904                // While not technically wrong, the invariant should uphold.
905                debug_assert!(!ranges.is_empty());
906                ranges.is_empty()
907            }
908        }
909    }
910
911    /// Returns `true` if the character `c` is contained matches any contained range.
912    #[inline(always)]
913    fn contains(&self, c: char) -> bool {
914        // TODO: optimize this into a `starts_with` which gets a `&str`, this can be optimized to
915        // byte matches
916        match self {
917            Self::Empty => false,
918            Self::Single(range) => range.contains(c),
919            Self::Multiple(ranges) => ranges.iter().any(|range| range.contains(c)),
920        }
921    }
922}
923
924/// Represents a character range in a [`Token::Class`].
925#[derive(Clone, Copy, Debug)]
926struct Range {
927    start: char,
928    end: char,
929}
930
931impl Range {
932    /// Create a new range which matches a single character.
933    fn single(c: char) -> Self {
934        Self { start: c, end: c }
935    }
936
937    /// Changes the end of the range to a new character.
938    ///
939    /// Returns an error if the new end character is lexicographically before
940    /// the start character.
941    fn set_end(&mut self, end: char) -> Result<(), ErrorKind> {
942        if self.start > end {
943            return Err(ErrorKind::InvalidRange(self.start, end));
944        }
945        self.end = end;
946        Ok(())
947    }
948
949    /// Returns `true` if the character `c` is contained in the range.
950    #[inline(always)]
951    fn contains(&self, c: char) -> bool {
952        self.start <= c && c <= self.end
953    }
954}
955
956#[cfg(test)]
957mod tests {
958    use super::*;
959
960    macro_rules! assert_pattern {
961        ($pattern:expr, $s:expr $(,$options:tt)?) => {{
962            let mut pattern = Pattern::builder($pattern);
963            for opt in stringify!($($options)?).chars() {
964                match opt {
965                    'i' => { pattern.case_insensitive(true); }
966                    _ => {}
967                }
968            }
969            let pattern = pattern.build().unwrap();
970            assert!(
971                pattern.is_match($s),
972                "expected pattern '{}' to match '{}' - {pattern:?}",
973                $pattern,
974                $s
975            );
976        }};
977        ($pattern:expr, NOT $s:expr $(,$options:tt)?) => {{
978            let mut pattern = Pattern::builder($pattern);
979            for opt in stringify!($($options)?).chars() {
980                match opt {
981                    'i' => { pattern.case_insensitive(true); }
982                    _ => {}
983                }
984            }
985            let pattern = pattern.build().unwrap();
986            assert!(
987                !pattern.is_match($s),
988                "expected pattern '{}' to not match '{}' - {pattern:?}",
989                $pattern,
990                $s
991            );
992        }};
993    }
994
995    macro_rules! assert_strategy {
996        ($pattern:expr, $expected:pat) => {{
997            let pattern = Pattern::new($pattern).unwrap();
998            let kind = match &pattern.strategy {
999                MatchStrategy::Literal(_) => "Literal",
1000                MatchStrategy::Prefix(_) => "Prefix",
1001                MatchStrategy::Suffix(_) => "Suffix",
1002                MatchStrategy::Contains(_) => "Contains",
1003                MatchStrategy::Static(_) => "Static",
1004                MatchStrategy::Wildmatch(_) => "Wildmatch",
1005            };
1006            assert_eq!(
1007                kind,
1008                stringify!($expected),
1009                "expected pattern '{}' to have strategy '{}' - {pattern:?}",
1010                $pattern,
1011                stringify!($expected)
1012            );
1013        }};
1014    }
1015
1016    macro_rules! assert_invalid {
1017        ($pattern:expr) => {{
1018            if let Ok(pattern) = Pattern::new($pattern) {
1019                assert!(
1020                    false,
1021                    "expected pattern '{}' to not compile - {pattern:?}",
1022                    $pattern
1023                );
1024            }
1025        }};
1026    }
1027
1028    #[test]
1029    fn test_empty() {
1030        assert_pattern!("", NOT "");
1031        assert_pattern!("", NOT "foo");
1032    }
1033
1034    #[test]
1035    fn test_literal() {
1036        assert_pattern!("foo", "foo");
1037        assert_pattern!("foo", NOT "fOo");
1038        assert_pattern!("foo", NOT "FOO");
1039        assert_pattern!(r"f\{\}o", "f{}o");
1040        assert_pattern!(r"f\}o", "f}o");
1041        assert_pattern!(r"f\{o", "f{o");
1042        assert_pattern!(r"f\{b,a,r\}o", "f{b,a,r}o");
1043        assert_pattern!(r"f\\o", r"f\o");
1044        assert_pattern!("fඞo", "fඞo");
1045    }
1046
1047    #[test]
1048    fn test_literal_case_insensitive() {
1049        assert_pattern!("foo", "foo", i);
1050        assert_pattern!("foo", "fOo", i);
1051        assert_pattern!("fOo", "Foo", i);
1052        assert_pattern!("İ", "i\u{307}", i);
1053        assert_pattern!("İ", "i̇", i);
1054    }
1055
1056    #[test]
1057    fn test_literal_strategy() {
1058        assert_strategy!("foo", Literal);
1059        assert_strategy!(r"f\{b,a,r\}o", Literal);
1060        assert_strategy!(r"f\\o", Literal);
1061        assert_strategy!("fඞo", Literal);
1062    }
1063
1064    #[test]
1065    fn test_prefix() {
1066        assert_pattern!("foo*", "foo___");
1067        assert_pattern!("foo*", "foo");
1068        assert_pattern!("foo**", "foo");
1069        assert_pattern!("foo*?*", NOT "foo");
1070        assert_pattern!("foo*?*", "foo_");
1071        assert_pattern!("foo*?*?", "foo_____");
1072        assert_pattern!("foo*?*?", NOT "foo");
1073        assert_pattern!("foo*?*?", "foo__");
1074        assert_pattern!("foo*?*?", "foo_____");
1075        assert_pattern!("foo**", "foo___");
1076        assert_pattern!("foo*?*", "foo___");
1077        assert_pattern!("foo*?*?", "foo___");
1078        assert_pattern!("foo*", "fooඞ");
1079        assert_pattern!("ඞ*", "ඞfoo");
1080        assert_pattern!("foo*", NOT "___");
1081        assert_pattern!("foo*", NOT "fo");
1082        assert_pattern!("foo*", NOT "fob");
1083        assert_pattern!("foo*", NOT "boo");
1084        assert_pattern!("foo*", NOT "Foo");
1085        assert_pattern!("foo*", NOT "FOO___");
1086
1087        // No special slash handling
1088        assert_pattern!("foo/bar*", "foo/bar___");
1089        assert_pattern!("foo*", "foo/bar___");
1090        assert_pattern!("foo*", NOT "/foo");
1091    }
1092
1093    #[test]
1094    fn test_prefix_case_insensitive() {
1095        assert_pattern!("foo*", "foo___", i);
1096        assert_pattern!("foo*", "fOo___", i);
1097        assert_pattern!("foo*", "FOO___", i);
1098        assert_pattern!("fOo*", "FOO___", i);
1099        assert_pattern!("fOo*", "Foo___", i);
1100
1101        assert_pattern!("İ*", "İ___", i);
1102        assert_pattern!("İ*", "İ", i);
1103        assert_pattern!("İ*", "i̇", i);
1104        assert_pattern!("İ*", "i\u{307}___", i);
1105        assert_pattern!("İ*", NOT "i____", i);
1106    }
1107
1108    #[test]
1109    fn test_prefix_strategy() {
1110        assert_strategy!("foo*", Prefix);
1111        assert_strategy!("foo**", Prefix);
1112        assert_strategy!("foo?*", Wildmatch);
1113    }
1114
1115    #[test]
1116    fn test_suffix() {
1117        assert_pattern!("*foo", "___foo");
1118        assert_pattern!("*foo", "foo");
1119        assert_pattern!("**foo", "foo");
1120        assert_pattern!("*?*foo", NOT "foo");
1121        assert_pattern!("*?*foo", "_foo");
1122        assert_pattern!("*?*foo", "_____foo");
1123        assert_pattern!("?*?*foo", NOT "foo");
1124        assert_pattern!("?*?*foo", NOT "_foo");
1125        assert_pattern!("?*?*foo", "__foo");
1126        assert_pattern!("?*?*foo", "_____foo");
1127        assert_pattern!("**foo", "___foo");
1128        assert_pattern!("*?*foo", "___foo");
1129        assert_pattern!("*?*?foo", "__foo");
1130        assert_pattern!("*foo", "ඞfoo");
1131        assert_pattern!("*ඞ", "fooඞ");
1132        assert_pattern!("*foo", NOT "bar");
1133        assert_pattern!("*foo", NOT "fo");
1134        assert_pattern!("*foo", NOT "fob");
1135        assert_pattern!("*foo", NOT "boo");
1136        assert_pattern!("*foo", NOT "Foo");
1137        assert_pattern!("*foo", NOT "___FOO");
1138
1139        // No special slash handling
1140        assert_pattern!("*foo/bar", "___foo/bar");
1141        assert_pattern!("*bar", "___foo/bar");
1142        assert_pattern!("*foo", NOT "foo/");
1143    }
1144
1145    #[test]
1146    fn test_suffix_case_insensitive() {
1147        assert_pattern!("foo*", "foo___", i);
1148        assert_pattern!("foo*", "fOo___", i);
1149        assert_pattern!("foo*", "FOO___", i);
1150        assert_pattern!("fOo*", "FOO___", i);
1151        assert_pattern!("fOo*", "Foo___", i);
1152
1153        assert_pattern!("*İ", "___İ", i);
1154        assert_pattern!("*İ", "İ", i);
1155        assert_pattern!("*İ", "i̇", i);
1156        assert_pattern!("*İ", "___i\u{307}", i);
1157        assert_pattern!("*İ", NOT "___i", i);
1158    }
1159
1160    #[test]
1161    fn test_suffix_strategy() {
1162        assert_strategy!("*foo", Suffix);
1163        assert_strategy!("**foo", Suffix);
1164        assert_strategy!("*?foo", Wildmatch);
1165    }
1166
1167    #[test]
1168    fn test_contains() {
1169        assert_pattern!("*foo*", "foo");
1170        assert_pattern!("*foo*", "foo___");
1171        assert_pattern!("*foo*", "___foo");
1172        assert_pattern!("*foo*", "___foo___");
1173        assert_pattern!("*foo*", NOT "___fo");
1174        assert_pattern!("*foo*", NOT "oo___");
1175        assert_pattern!("*foo*", NOT "___fo___");
1176        assert_pattern!("*foo*", NOT "fඞo");
1177        assert_pattern!("*foo*", NOT "___fOo___");
1178        assert_pattern!("*foo*", NOT "___FOO___");
1179
1180        // No special slash handling
1181        assert_pattern!("*foo*", "foo");
1182        assert_pattern!("*foo*", "foo_/_");
1183        assert_pattern!("*foo*", "_/_foo");
1184        assert_pattern!("*foo*", "_/_foo_/_");
1185        assert_pattern!("*f/o*", "_/_f/o_/_");
1186    }
1187
1188    #[test]
1189    fn test_contains_case_insensitive() {
1190        assert_pattern!("*foo*", "foo", i);
1191        assert_pattern!("*foo*", "fOo", i);
1192        assert_pattern!("*fOo*", "Foo", i);
1193        assert_pattern!("*foo*", "___foo___", i);
1194        assert_pattern!("*foo*", "___fOo___", i);
1195        assert_pattern!("*foo*", "___FOO___", i);
1196        assert_pattern!("*fOo*", "___FOO___", i);
1197        assert_pattern!("*fOo*", "___Foo___", i);
1198
1199        assert_pattern!("*İ*", "___İ___", i);
1200        assert_pattern!("*İ*", "İ", i);
1201        assert_pattern!("*İ*", "___İ", i);
1202        assert_pattern!("*İ*", "İ___", i);
1203        assert_pattern!("*İ*", "___İ___", i);
1204        assert_pattern!("*İ*", "i̇", i);
1205        assert_pattern!("*İ*", "___i̇", i);
1206        assert_pattern!("*İ*", "i̇___", i);
1207        assert_pattern!("*İ*", "___i̇___", i);
1208        assert_pattern!("*İ*", "___i\u{307}", i);
1209        assert_pattern!("*İ*", "i\u{307}___", i);
1210        assert_pattern!("*İ*", "___i\u{307}___", i);
1211        assert_pattern!("*İ*", NOT "i", i);
1212        assert_pattern!("*İ*", NOT "i___", i);
1213        assert_pattern!("*İ*", NOT "___i", i);
1214        assert_pattern!("*İ*", NOT "___i___", i);
1215    }
1216
1217    #[test]
1218    fn test_contains_strategy() {
1219        assert_strategy!("*foo*", Contains);
1220        assert_strategy!("**foo**", Contains);
1221        assert_strategy!("*?foo*", Wildmatch);
1222        assert_strategy!("*foo?*", Wildmatch);
1223        assert_strategy!("*foo*?", Wildmatch);
1224        assert_strategy!("?*foo*", Wildmatch);
1225    }
1226
1227    #[test]
1228    fn test_wildcard() {
1229        assert_pattern!("*", "");
1230        assert_pattern!("*", "a");
1231        assert_pattern!("*", "\n");
1232        assert_pattern!("*", "\n\n");
1233        assert_pattern!("*", "\na\n");
1234        assert_pattern!("*", "\na\nb\nc");
1235        assert_pattern!("*", "ඞfooඞfooඞ");
1236
1237        // No special slash handling
1238        assert_pattern!("*", "/");
1239        assert_pattern!("*", "_/");
1240        assert_pattern!("*", "/_");
1241        assert_pattern!("*", "_/_");
1242        assert_pattern!("*", "/?/?/");
1243    }
1244
1245    #[test]
1246    fn test_wildcard_strategy() {
1247        assert_strategy!("*", Static);
1248        assert_strategy!("{*}", Static);
1249        assert_strategy!("{*,}", Static);
1250        assert_strategy!("{foo,*}", Static);
1251        assert_strategy!("{foo,*}?{*,bar}", Wildmatch);
1252        assert_strategy!("{*,}?{*,}", Wildmatch);
1253    }
1254
1255    #[test]
1256    fn test_any() {
1257        assert_pattern!("?", NOT "");
1258        assert_pattern!("?", "ඞ");
1259        assert_pattern!("?", "?");
1260        assert_pattern!("?", "\n");
1261        assert_pattern!("?", "_");
1262        assert_pattern!("?", NOT "aa");
1263        assert_pattern!("?", NOT "aaaaaaaaaaaaaaaaaa");
1264        assert_pattern!("??", "aa");
1265        assert_pattern!("??", NOT "aaa");
1266        assert_pattern!("a?a?a", "aaaaa");
1267        assert_pattern!("a?a?a", "abaca");
1268        assert_pattern!("a?a?a", NOT "ab_ca");
1269        assert_pattern!("a?a?a", NOT "aaAaa");
1270        assert_pattern!("???????????x???????????", "???????????x???????????");
1271        assert_pattern!("???????????x???????????", "??______???x?????_?????");
1272        assert_pattern!("???????????x???????????", NOT "?______???x?????_?????");
1273        assert_pattern!("???????????x???????????", NOT "??______???_?????_?????");
1274        assert_pattern!(
1275            "??????????????????????????????????????????????????",
1276            "?????????????????????????????????????????????????!"
1277        );
1278        assert_pattern!("foo?bar", "foo?bar");
1279        assert_pattern!("foo?bar", "foo!bar");
1280        assert_pattern!("a??a", "aඞඞa");
1281
1282        // No special slash handling
1283        assert_pattern!("?", "/");
1284    }
1285
1286    #[test]
1287    fn test_any_wildcard() {
1288        assert_pattern!("??*", NOT "");
1289        assert_pattern!("??*", NOT "a");
1290        assert_pattern!("??*", "ab");
1291        assert_pattern!("??*", "abc");
1292        assert_pattern!("??*", "abcde");
1293
1294        assert_pattern!("*??", NOT "");
1295        assert_pattern!("*??", NOT "a");
1296        assert_pattern!("*??", "ab");
1297        assert_pattern!("*??", "abc");
1298        assert_pattern!("*??", "abcde");
1299
1300        assert_pattern!("*??*", NOT "");
1301        assert_pattern!("*??*", NOT "a");
1302        assert_pattern!("*??*", "ab");
1303        assert_pattern!("*??*", "abc");
1304        assert_pattern!("*??*", "abcde");
1305
1306        assert_pattern!("*?*?*", NOT "");
1307        assert_pattern!("*?*?*", NOT "a");
1308        assert_pattern!("*?*?*", "ab");
1309        assert_pattern!("*?*?*", "abc");
1310        assert_pattern!("*?*?*", "abcde");
1311    }
1312
1313    #[test]
1314    fn test_escapes() {
1315        assert_pattern!(r"f\\o", r"f\o");
1316        assert_pattern!(r"f\*o", r"f*o");
1317        assert_pattern!(r"f\*o", NOT r"f\*o");
1318        assert_pattern!(r"f\\*o", r"f\*o");
1319        assert_pattern!(r"f\\*o", r"f\o");
1320        assert_pattern!(r"f\\*o", r"f\___o");
1321        assert_pattern!(r"f\\\*o", r"f\*o");
1322        assert_pattern!(r"f\[\]o", r"f[]o");
1323        assert_pattern!(r"f\[?\]o", r"f[?]o");
1324        assert_pattern!(r"f\[a-z\]o", r"f[a-z]o");
1325        assert_pattern!(r"f\[o", r"f[o");
1326        assert_pattern!(r"f\]o", r"f]o");
1327        assert_pattern!(r"\[", r"[");
1328    }
1329
1330    #[test]
1331    fn test_invalid() {
1332        assert_invalid!(r"\");
1333        assert_invalid!(r"f\");
1334        assert_invalid!(r"*\");
1335        assert_invalid!("[");
1336        assert_invalid!("[a-z");
1337        assert_invalid!(r"[a-z\");
1338        assert_invalid!("[[]");
1339        assert_invalid!("[]]");
1340        assert_invalid!("]");
1341        assert_invalid!("[a-z");
1342        assert_invalid!("[b-a]");
1343        assert_invalid!("[a-A]");
1344    }
1345
1346    #[test]
1347    fn test_classes() {
1348        assert_pattern!("[]", NOT "");
1349        assert_pattern!("[]", NOT "_");
1350        assert_pattern!("[a]", "a");
1351        assert_pattern!("[a]", NOT "[a]");
1352        assert_pattern!("[a]", NOT "b");
1353        assert_pattern!("[a]", NOT "A");
1354        assert_pattern!("[ඞ]", "ඞ");
1355        assert_pattern!("[ඞ]", NOT "a");
1356        assert_pattern!("[ඞa]", "a");
1357        assert_pattern!("[aඞ]", "ඞ");
1358        assert_pattern!("[ඞa]", NOT "b");
1359        assert_pattern!("[ab]", "a");
1360        assert_pattern!("[ab]", "b");
1361        assert_pattern!("[ab]", NOT "c");
1362        assert_pattern!("x[ab]x", "xax");
1363        assert_pattern!("x[ab]x", "xbx");
1364        assert_pattern!("x[ab]x", NOT "xBx");
1365        assert_pattern!("x[ab]x", NOT "xcx");
1366        assert_pattern!("x[ab]x", NOT "aax");
1367        assert_pattern!("x[ab]x", NOT "xaa");
1368        assert_pattern!("x[ab]x", NOT "xaax");
1369        assert_pattern!("x[ab]x", NOT "xxax");
1370        assert_pattern!("x[ab]x", NOT "xaxx");
1371        assert_pattern!("[a-b]", "a");
1372        assert_pattern!("[a-b]", "b");
1373        assert_pattern!("[a-b]", NOT "c");
1374        assert_pattern!("[a-c]", "a");
1375        assert_pattern!("[a-c]", "b");
1376        assert_pattern!("[a-c]", "c");
1377        assert_pattern!("[a-c]", NOT "d");
1378        assert_pattern!("[a-c]", NOT "1");
1379        assert_pattern!("[a-c]", NOT "ඞ");
1380        assert_pattern!("[A-z]", "a");
1381        assert_pattern!("[A-z]", "z");
1382        assert_pattern!("[A-z]", "["); // `[` is actually inbetween here in the ascii table
1383        assert_pattern!("[A-z]", "A");
1384        assert_pattern!("[A-z]", "Z");
1385        assert_pattern!("[A-z]", NOT "0");
1386        assert_pattern!("[0-9]", "0");
1387        assert_pattern!("[0-9]", "1");
1388        assert_pattern!("[0-9]", "2");
1389        assert_pattern!("[0-9]", "3");
1390        assert_pattern!("[0-9]", "4");
1391        assert_pattern!("[0-9]", "5");
1392        assert_pattern!("[0-9]", "6");
1393        assert_pattern!("[0-9]", "7");
1394        assert_pattern!("[0-9]", "8");
1395        assert_pattern!("[0-9]", "9");
1396        assert_pattern!(
1397            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1398            "3bYf"
1399        );
1400        assert_pattern!(
1401            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1402            NOT "3cYf"
1403        );
1404        assert_pattern!(
1405            "[0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF][0-9a-bX-ZfF]",
1406            NOT "3ඞYf"
1407        );
1408        assert_pattern!("[0-9]", NOT "a9");
1409        assert_pattern!("[0-9]", NOT "9a");
1410        assert_pattern!("[0-9]", NOT "a9a");
1411        assert_pattern!("[0-9]", NOT "");
1412        assert_pattern!("[0-9!]", "!");
1413        assert_pattern!("[0-9][a-b]", NOT "");
1414        assert_pattern!("[0-9][a-b]", NOT "a");
1415        assert_pattern!("[0-9][a-b]", NOT "a0");
1416        assert_pattern!("[0-9][a-b]", "0a");
1417        assert_pattern!(r"a[\]a\-]b", "aab");
1418
1419        // TODO: lenient: assert_pattern!("a[]-]b", NOT "aab");
1420        // TODO: lenient: assert_pattern!("]", "]");
1421        // TODO: lenient: assert_pattern!("a[]-]b", "a-]b");
1422        // TODO: lenient: assert_pattern!("a[]-]b", "a]b");
1423        // TODO: lenient: assert_pattern!("a[]]b", "a]b");
1424
1425        // Escapes in character classes
1426        assert_pattern!(r"[\\]", r"\");
1427        assert_pattern!(r"[\\]", NOT "a");
1428        assert_pattern!(r"[\]]", "]");
1429        assert_pattern!(r"[\]]", NOT "a");
1430        assert_pattern!(r"[\[]", "[");
1431        assert_pattern!(r"[\[]", NOT "a");
1432        assert_pattern!(r"[\]]", NOT r"\");
1433
1434        assert_pattern!("a[X-]b", "a-b");
1435        assert_pattern!("a[X-]b", "aXb");
1436    }
1437
1438    #[test]
1439    fn test_classes_case_insensitive() {
1440        assert_pattern!("[a]", "a", i);
1441        assert_pattern!("[a]", "A", i);
1442        assert_pattern!("x[ab]x", "xAX", i);
1443        assert_pattern!("x[ab]x", "XBx", i);
1444        assert_pattern!("x[ab]x", NOT "Xcx", i);
1445        assert_pattern!("x[ab]x", NOT "aAx", i);
1446        assert_pattern!("x[ab]x", NOT "xAa", i);
1447        assert_pattern!("[ǧ]", "Ǧ", i);
1448        assert_pattern!("[Ǧ]", "ǧ", i);
1449    }
1450
1451    #[test]
1452    fn test_classes_negated() {
1453        assert_pattern!("[!]", NOT "");
1454        assert_pattern!("[!a]", "b");
1455        assert_pattern!("[!a]", "A");
1456        assert_pattern!("[!a]", "B");
1457        assert_pattern!("[!b]", NOT "b");
1458        assert_pattern!("[!ab]", NOT "a");
1459        assert_pattern!("[!ab]", NOT "b");
1460        assert_pattern!("[!ab]", "c");
1461        assert_pattern!("x[!ab]x", "xcx");
1462        assert_pattern!("x[!ab]x", NOT "xax");
1463        assert_pattern!("x[!ab]x", NOT "xbx");
1464        assert_pattern!("x[!ab]x", NOT "xxcx");
1465        assert_pattern!("x[!ab]x", NOT "xcxx");
1466        assert_pattern!("x[!ab]x", NOT "xc");
1467        assert_pattern!("x[!ab]x", NOT "cx");
1468        assert_pattern!("x[!ab]x", NOT "x");
1469        assert_pattern!("[!a-c]", NOT "a");
1470        assert_pattern!("[!a-c]", NOT "b");
1471        assert_pattern!("[!a-c]", NOT "c");
1472        assert_pattern!("[!a-c]", "d");
1473        assert_pattern!("[!a-c]", "A");
1474        assert_pattern!("[!a-c]", "ඞ");
1475        assert_pattern!(r"[!a-c\\]", "d");
1476        assert_pattern!(r"[!a-c\\]", NOT r"\");
1477        assert_pattern!(r"[!\]]", "a");
1478        assert_pattern!(r"[!\]]", NOT "]");
1479        assert_pattern!(r"[!!]", "a");
1480        assert_pattern!(r"[!!]", NOT "!");
1481    }
1482
1483    #[test]
1484    fn test_classes_negated_case_insensitive() {
1485        assert_pattern!("[!a]", "b", i);
1486        assert_pattern!("[!a]", "B", i);
1487        assert_pattern!("[!b]", NOT "b", i);
1488        assert_pattern!("[!b]", NOT "B", i);
1489        assert_pattern!("[!ab]", NOT "a", i);
1490        assert_pattern!("[!ab]", NOT "A", i);
1491        assert_pattern!("[!ab]", NOT "b", i);
1492        assert_pattern!("[!ab]", NOT "B", i);
1493        assert_pattern!("[!ab]", "c", i);
1494        assert_pattern!("[!ab]", "C", i);
1495    }
1496
1497    #[test]
1498    fn test_alternates() {
1499        assert_pattern!("{}foo{}", "foo");
1500        assert_pattern!("foo{}bar", "foobar");
1501        assert_pattern!("foo{}{}bar", "foobar");
1502        assert_pattern!("{foo}", "foo");
1503        assert_pattern!("{foo}", NOT "fOo");
1504        assert_pattern!("{foo}", NOT "bar");
1505        assert_pattern!("{foo,bar}", "foo");
1506        assert_pattern!("{foo,bar}", "bar");
1507        assert_pattern!("{foo,bar}", NOT "Foo");
1508        assert_pattern!("{foo,bar}", NOT "fOo");
1509        assert_pattern!("{foo,bar}", NOT "BAR");
1510        assert_pattern!("{foo,bar}", NOT "fooo");
1511        assert_pattern!("{foo,bar}", NOT "baar");
1512        assert_pattern!("{foo,bar,}baz", "foobaz");
1513        assert_pattern!("{foo,bar,}baz", "barbaz");
1514        assert_pattern!("{foo,bar,}baz", "baz");
1515        assert_pattern!("{foo,,bar}baz", "foobaz");
1516        assert_pattern!("{foo,,bar}baz", "barbaz");
1517        assert_pattern!("{foo,,bar}baz", "baz");
1518        assert_pattern!("{,foo,bar}baz", "foobaz");
1519        assert_pattern!("{,foo,bar}baz", "barbaz");
1520        assert_pattern!("{,foo,bar}baz", "baz");
1521        assert_pattern!("{foo*bar}", "foobar");
1522        assert_pattern!("{foo*bar}", "fooooobar");
1523        assert_pattern!("{foo*bar}", NOT "");
1524        assert_pattern!("{foo*bar,}", "foobar");
1525        assert_pattern!("{foo*bar,}", "fooooobar");
1526        assert_pattern!("{foo*bar,}", "");
1527        assert_pattern!("{foo*bar,baz}", "foobar");
1528        assert_pattern!("{foo*bar,baz}", "fooooobar");
1529        assert_pattern!("{foo*bar,baz}", "baz");
1530        assert_pattern!("{foo*bar,baz}", NOT "");
1531        assert_pattern!("{foo*bar,baz,}", "foobar");
1532        assert_pattern!("{foo*bar,baz,}", "fooooobar");
1533        assert_pattern!("{foo*bar,baz,}", "baz");
1534        assert_pattern!("{foo*bar,baz,}", "");
1535        assert_pattern!("{,,,,}", NOT "");
1536        assert_pattern!("{[fb][oa][or]}", "foo");
1537        assert_pattern!("{[fb][oa][or]}", "bar");
1538        assert_pattern!("{[fb][oa][or],baz}", "foo");
1539        assert_pattern!("{[fb][oa][or],baz}", "bar");
1540        assert_pattern!("{[fb][oa][or],baz}", "baz");
1541        assert_pattern!("{baz,[fb][oa][or]}", "baz");
1542        assert_pattern!("{baz,[fb][oa][or]}", "foo");
1543        assert_pattern!("{baz,[fb][oa][or]}", "bar");
1544        assert_pattern!("{baz,[fb][oa][or]}", "bor");
1545        assert_pattern!("{baz,[fb][oa][or]}", NOT "barr");
1546        assert_pattern!("{baz,[fb][oa][or]}", NOT "boz");
1547        assert_pattern!("{baz,[fb][oa][or]}", NOT "fbar");
1548        assert_pattern!("{baz,[fb][oa][or]}", NOT "bAr");
1549        assert_pattern!("{baz,[fb][oa][or]}", NOT "Foo");
1550        assert_pattern!("{baz,[fb][oa][or]}", NOT "Bar");
1551        assert_pattern!("{baz,b[aA]r}", NOT "bAz");
1552        assert_pattern!("{baz,b[!aA]r}", NOT "bar");
1553        assert_pattern!("{baz,b[!aA]r}", "bXr");
1554        assert_pattern!("{[a-z],[0-9]}", "a");
1555        assert_pattern!("{[a-z],[0-9]}", "3");
1556        assert_pattern!("a{[a-z],[0-9]}a", "a3a");
1557        assert_pattern!("a{[a-z],[0-9]}a", "aba");
1558        assert_pattern!("a{[a-z],[0-9]}a", NOT "aAa");
1559        assert_pattern!("a{[a-z],?}a", "aXa");
1560        assert_pattern!(r"a{[a-z],\?}a", "a?a");
1561        assert_pattern!(r"a{[a-z],\?}a", NOT "aXa");
1562        assert_pattern!(r"a{[a-z],\?}a", NOT r"a\a");
1563        assert_pattern!(r"a{\[\],\{\}}a", "a[]a");
1564        assert_pattern!(r"a{\[\],\{\}}a", "a{}a");
1565        assert_pattern!(r"a{\[\],\{\}}a", NOT "a[}a");
1566        assert_pattern!(r"a{\[\],\{\}}a", NOT "a{]a");
1567        assert_pattern!(r"a{\[\],\{\}}a", NOT "a[a");
1568        assert_pattern!(r"a{\[\],\{\}}a", NOT "a]a");
1569        assert_pattern!(r"a{\[\],\{\}}a", NOT "a{a");
1570        assert_pattern!(r"a{\[\],\{\}}a", NOT "a}a");
1571        assert_pattern!("foo/{*.js,*.html}", "foo/.js");
1572        assert_pattern!("foo/{*.js,*.html}", "foo/.html");
1573        assert_pattern!("foo/{*.js,*.html}", "foo/bar.js");
1574        assert_pattern!("foo/{*.js,*.html}", "foo/bar.html");
1575        assert_pattern!("foo/{*.js,*.html}", NOT "foo/bar.png");
1576        assert_pattern!("foo/{*.js,*.html}", NOT "bar/bar.js");
1577        assert_pattern!("{foo,abc}{def,bar}", "foodef");
1578        assert_pattern!("{foo,abc}{def,bar}", "foobar");
1579        assert_pattern!("{foo,abc}{def,bar}", "abcdef");
1580        assert_pattern!("{foo,abc}{def,bar}", "abcbar");
1581        assert_pattern!("{foo,abc}{def,bar}", NOT "foofoo");
1582        assert_pattern!("{foo,abc}{def,bar}", NOT "fooabc");
1583        assert_pattern!("{foo,abc}{def,bar}", NOT "defdef");
1584        assert_pattern!("{foo,abc}{def,bar}", NOT "defabc");
1585    }
1586
1587    #[test]
1588    fn test_alternate_strategy() {
1589        // Empty alternates can be simplified.
1590        assert_strategy!("{}foo{}", Literal);
1591        assert_strategy!("foo{}bar", Literal);
1592        assert_strategy!("foo{}{}{}bar", Literal);
1593        assert_strategy!("foo{,,,}bar", Literal);
1594    }
1595
1596    #[test]
1597    fn test_alternates_case_insensitive() {
1598        assert_pattern!("{foo}", "foo", i);
1599        assert_pattern!("{foo}", "fOo", i);
1600        assert_pattern!("{foo}", NOT "bar", i);
1601        assert_pattern!("{foo,bar}", "foo", i);
1602        assert_pattern!("{foo,bar}", "bar", i);
1603        assert_pattern!("{foo,bar}", "Foo", i);
1604        assert_pattern!("{foo,bar}", "fOo", i);
1605        assert_pattern!("{foo,bar}", "BAR", i);
1606        assert_pattern!("{foo,bar}", NOT "bao", i);
1607        assert_pattern!("{f[o0-9]o,b[a]r}", "foo", i);
1608        assert_pattern!("{f[o0-9]o,b[a]r}", "fOo", i);
1609        assert_pattern!("{f[o0-9]o,b[a]r}", "f1o", i);
1610        assert_pattern!("{f[o0-9]o,b[a]r}", "foO", i);
1611        assert_pattern!("{f[o0-9]o,b[a]r}", "FOO", i);
1612        assert_pattern!("{f[o0-9]o,b[a]r}", "bar", i);
1613        assert_pattern!("{f[o0-9]o,b[a]r}", "bAr", i);
1614        assert_pattern!("{f[o0-9]o,b[a]r}", "baR", i);
1615        assert_pattern!("{f[o0-9]o,b[a]r}", "BAR", i);
1616        assert_pattern!("{f[o0-9]o,b[!a]r}", "foo", i);
1617        assert_pattern!("{f[o0-9]o,b[!a]r}", "bXr", i);
1618        assert_pattern!("{f[o0-9]o,b[!a]r}", NOT "bar", i);
1619        assert_pattern!("{f[o0-9]o,b[!a]r}", NOT "bAr", i);
1620    }
1621
1622    #[test]
1623    fn test_complex() {
1624        assert_pattern!("*?", "\n");
1625        assert_pattern!("?*", "\n");
1626        assert_pattern!("*?*", "\n");
1627        assert_pattern!("1.18.[!0-4].*", "1.18.5.");
1628        assert_pattern!("1.18.[!0-4].*", "1.18.5.aBc");
1629        assert_pattern!("1.18.[!0-4].*", NOT "1.18.3.abc");
1630        assert_pattern!("!*!*.md", "!foo!.md"); // no `!` outside of character classes
1631        assert_pattern!("foo*foofoo*foobar", "foofoofooxfoofoobar");
1632        assert_pattern!("foo*fooFOO*fOobar", "fooFoofooXfoofooBAR", i);
1633        assert_pattern!("[0-9]*a", "0aaaaaaaaa", i);
1634        assert_pattern!("[0-9]*Bar[x]", "0foobarx", i);
1635
1636        assert_pattern!(
1637            r"/api/0/organizations/\{organization_slug\}/event*",
1638            "/api/0/organizations/{organization_slug}/event/foobar"
1639        );
1640        assert_pattern!(
1641            r"/api/0/organizations/\{organization_slug\}/event*",
1642            NOT r"/api/0/organizations/\{organization_slug\}/event/foobar"
1643        );
1644
1645        assert_pattern!(
1646            "*b??{foo,bar,baz,with}*cr{x,y,z,?}zyl[a-z]ng{suffix,pr?*ix}*it?**?uallymatches",
1647            "foobarwithacrazylongprefixandanditactuallymatches"
1648        );
1649        assert_pattern!(
1650            "*b??{foo,bar,baz,with}*cr{x,y,z,?}zyl[a-z]ng{suffix,pr?*ix}*it?**?uallymatches",
1651            "FOOBARWITHACRAZYLONGPREFIXANDANDITACTUALLYMATCHES",
1652            i
1653        );
1654    }
1655
1656    /// Tests collected by [Kirk J Krauss].
1657    ///
1658    /// Kirk J Krauss: http://developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html.
1659    #[test]
1660    fn test_kirk_j_krauss() {
1661        // Case with first wildcard after total match.
1662        assert_pattern!("Hi*", "Hi");
1663
1664        // Case with mismatch after '*'
1665        assert_pattern!("ab*d", NOT "abc");
1666
1667        // Cases with repeating character sequences.
1668        assert_pattern!("*ccd", "abcccd");
1669        assert_pattern!("*issip*ss*", "mississipissippi");
1670        assert_pattern!("xxxx*zzy*fffff", NOT "xxxx*zzzzzzzzy*f");
1671        assert_pattern!("xxx*zzy*f", "xxxx*zzzzzzzzy*f");
1672        assert_pattern!("xxxx*zzy*fffff", NOT "xxxxzzzzzzzzyf");
1673        assert_pattern!("xxxx*zzy*f", "xxxxzzzzzzzzyf");
1674        assert_pattern!("xy*z*xyz", "xyxyxyzyxyz");
1675        assert_pattern!("*sip*", "mississippi");
1676        assert_pattern!("xy*xyz", "xyxyxyxyz");
1677        assert_pattern!("mi*sip*", "mississippi");
1678        assert_pattern!("*abac*", "ababac");
1679        assert_pattern!("*abac*", "ababac");
1680        assert_pattern!("a*zz*", "aaazz");
1681        assert_pattern!("*12*23", NOT "a12b12");
1682        assert_pattern!("a12b", NOT "a12b12");
1683        assert_pattern!("*12*12*", "a12b12");
1684
1685        // From DDJ reader Andy Belf
1686        assert_pattern!("*a?b", "caaab");
1687
1688        // Additional cases where the '*' char appears in the tame string.
1689        assert_pattern!("*", "*");
1690        assert_pattern!("a*b", "a*abab");
1691        assert_pattern!("a*", "a*r");
1692        assert_pattern!("a*aar", NOT "a*ar");
1693
1694        // More double wildcard scenarios.
1695        assert_pattern!("XY*Z*XYz", "XYXYXYZYXYz");
1696        assert_pattern!("*SIP*", "missisSIPpi");
1697        assert_pattern!("*issip*PI", "mississipPI");
1698        assert_pattern!("xy*xyz", "xyxyxyxyz");
1699        assert_pattern!("mi*sip*", "miSsissippi");
1700        assert_pattern!("mi*Sip*", NOT "miSsissippi");
1701        assert_pattern!("*Abac*", "abAbac");
1702        assert_pattern!("*Abac*", "abAbac");
1703        assert_pattern!("a*zz*", "aAazz");
1704        assert_pattern!("*12*23", NOT "A12b12");
1705        assert_pattern!("*12*12*", "a12B12");
1706        assert_pattern!("*oWn*", "oWn");
1707
1708        // Completely tame (no wildcards) cases.
1709        assert_pattern!("bLah", "bLah");
1710        assert_pattern!("bLaH", NOT "bLah");
1711
1712        // Simple mixed wildcard tests suggested by Marlin Deckert.
1713        assert_pattern!("*?", "a");
1714        assert_pattern!("*?", "ab");
1715        assert_pattern!("*?", "abc");
1716
1717        // More mixed wildcard tests including coverage for false positives.
1718        assert_pattern!("??", NOT "a");
1719        assert_pattern!("?*?", "ab");
1720        assert_pattern!("*?*?*", "ab");
1721        assert_pattern!("?**?*?", "abc");
1722        assert_pattern!("?**?*&?", NOT "abc");
1723        assert_pattern!("?b*??", "abcd");
1724        assert_pattern!("?a*??", NOT "abcd");
1725        assert_pattern!("?**?c?", "abcd");
1726        assert_pattern!("?**?d?", NOT "abcd");
1727        assert_pattern!("?*b*?*d*?", "abcde");
1728
1729        // Single-character-match cases.
1730        assert_pattern!("bL?h", "bLah");
1731        assert_pattern!("bLa?", NOT "bLaaa");
1732        assert_pattern!("bLa?", "bLah");
1733        assert_pattern!("?Lah", NOT "bLaH");
1734        assert_pattern!("?LaH", "bLaH");
1735
1736        // Many-wildcard scenarios.
1737        assert_pattern!(
1738            "a*a*a*a*a*a*aa*aaa*a*a*b",
1739            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
1740        );
1741        assert_pattern!(
1742            "*a*b*ba*ca*a*aa*aaa*fa*ga*b*",
1743            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1744        );
1745        assert_pattern!(
1746            "*a*b*ba*ca*a*x*aaa*fa*ga*b*",
1747            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1748        );
1749        assert_pattern!(
1750            "*a*b*ba*ca*aaaa*fa*ga*gggg*b*",
1751            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1752        );
1753        assert_pattern!(
1754            "*a*b*ba*ca*aaaa*fa*ga*ggg*b*",
1755            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1756        );
1757        assert_pattern!("*aabbaa*a*", "aaabbaabbaab");
1758        assert_pattern!(
1759            "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*",
1760            "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*"
1761        );
1762        assert_pattern!("*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*", "aaaaaaaaaaaaaaaaa");
1763        assert_pattern!(
1764            "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*",
1765            NOT "aaaaaaaaaaaaaaaa"
1766        );
1767        assert_pattern!(
1768            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*",
1769            NOT "abc*abcd*abcde*abcdef*abcdefg*abcdefgh*abcdefghi*abcdefghij*abcdefghijk*abcdefghijkl*abcdefghijklm*abcdefghijklmn"
1770        );
1771        assert_pattern!(
1772            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*",
1773            "abc*abcd*abcde*abcdef*abcdefg*abcdefgh*abcdefghi*abcdefghij*abcdefghijk*abcdefghijkl*abcdefghijklm*abcdefghijklmn"
1774        );
1775        assert_pattern!("abc*abc*abc*abc*abc", NOT "abc*abcd*abcd*abc*abcd");
1776        assert_pattern!(
1777            "abc*abc*abc*abc*abc*abc*abc*abc*abc*abc*abcd",
1778            "abc*abcd*abcd*abc*abcd*abcd*abc*abcd*abc*abc*abcd"
1779        );
1780        assert_pattern!("********a********b********c********", "abc");
1781        assert_pattern!("abc", NOT "********a********b********c********");
1782        assert_pattern!("********a********b********b********", NOT "abc");
1783        assert_pattern!("***a*b*c***", "*abc*");
1784
1785        // A case-insensitive algorithm test.
1786        assert_pattern!("*issip*PI", "mississippi", i);
1787
1788        // Tests suggested by other DDJ readers
1789        assert_pattern!("?", NOT "");
1790        assert_pattern!("*?", NOT "");
1791        // assert_pattern!("", ""); - Removed, relay-pattern behaves differently for empty strings.
1792        assert_pattern!("", NOT "a");
1793
1794        // Tame tests:
1795        assert_pattern!("abd", NOT "abc");
1796
1797        // Cases with repeating character sequences.
1798        assert_pattern!("abcccd", "abcccd");
1799        assert_pattern!("mississipissippi", "mississipissippi");
1800        assert_pattern!("xxxxzzzzzzzzyfffff", NOT "xxxxzzzzzzzzyf");
1801        assert_pattern!("xxxxzzzzzzzzyf", "xxxxzzzzzzzzyf");
1802        assert_pattern!("xxxxzzy.fffff", NOT "xxxxzzzzzzzzyf");
1803        assert_pattern!("xxxxzzzzzzzzyf", "xxxxzzzzzzzzyf");
1804        assert_pattern!("xyxyxyzyxyz", "xyxyxyzyxyz");
1805        assert_pattern!("mississippi", "mississippi");
1806        assert_pattern!("xyxyxyxyz", "xyxyxyxyz");
1807        assert_pattern!("m ississippi", "m ississippi");
1808        assert_pattern!("ababac?", NOT "ababac");
1809        assert_pattern!("ababac", NOT "dababac");
1810        assert_pattern!("aaazz", "aaazz");
1811        assert_pattern!("1212", NOT "a12b12");
1812        assert_pattern!("a12b", NOT "a12b12");
1813        assert_pattern!("a12b12", "a12b12");
1814
1815        // A mix of cases
1816        assert_pattern!("n", "n");
1817        assert_pattern!("aabab", "aabab");
1818        assert_pattern!("ar", "ar");
1819        assert_pattern!("aaar", NOT "aar");
1820        assert_pattern!("XYXYXYZYXYz", "XYXYXYZYXYz");
1821        assert_pattern!("missisSIPpi", "missisSIPpi");
1822        assert_pattern!("mississipPI", "mississipPI");
1823        assert_pattern!("xyxyxyxyz", "xyxyxyxyz");
1824        assert_pattern!("miSsissippi", "miSsissippi");
1825        assert_pattern!("miSsisSippi", NOT "miSsissippi");
1826        assert_pattern!("abAbac", "abAbac");
1827        assert_pattern!("abAbac", "abAbac");
1828        assert_pattern!("aAazz", "aAazz");
1829        assert_pattern!("A12b123", NOT "A12b12");
1830        assert_pattern!("a12B12", "a12B12");
1831        assert_pattern!("oWn", "oWn");
1832        assert_pattern!("bLah", "bLah");
1833        assert_pattern!("bLaH", NOT "bLah");
1834
1835        // Single '?' cases.
1836        assert_pattern!("a", "a");
1837        assert_pattern!("a?", "ab");
1838        assert_pattern!("ab?", "abc");
1839
1840        // Mixed '?' cases.
1841        assert_pattern!("??", NOT "a");
1842        assert_pattern!("??", "ab");
1843        assert_pattern!("???", "abc");
1844        assert_pattern!("????", "abcd");
1845        assert_pattern!("????", NOT "abc");
1846        assert_pattern!("?b??", "abcd");
1847        assert_pattern!("?a??", NOT "abcd");
1848        assert_pattern!("??c?", "abcd");
1849        assert_pattern!("??d?", NOT "abcd");
1850        assert_pattern!("?b?d*?", "abcde");
1851
1852        // Longer string scenarios.
1853        assert_pattern!(
1854            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
1855            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
1856        );
1857        assert_pattern!(
1858            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
1859            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1860        );
1861        assert_pattern!(
1862            "abababababababababababababababababababaacacacacacacacadaeafagahaiajaxalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
1863            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1864        );
1865        assert_pattern!(
1866            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaggggagaaaaaaaab",
1867            NOT "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1868        );
1869        assert_pattern!(
1870            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab",
1871            "abababababababababababababababababababaacacacacacacacadaeafagahaiajakalaaaaaaaaaaaaaaaaaffafagaagggagaaaaaaaab"
1872        );
1873        assert_pattern!("aaabbaabbaab", "aaabbaabbaab");
1874        assert_pattern!(
1875            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
1876            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1877        );
1878        assert_pattern!("aaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaa");
1879        assert_pattern!("aaaaaaaaaaaaaaaaa", NOT "aaaaaaaaaaaaaaaa");
1880        assert_pattern!(
1881            "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc",
1882            NOT "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn"
1883        );
1884        assert_pattern!(
1885            "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn",
1886            "abcabcdabcdeabcdefabcdefgabcdefghabcdefghiabcdefghijabcdefghijkabcdefghijklabcdefghijklmabcdefghijklmn"
1887        );
1888        assert_pattern!("abcabc?abcabcabc", NOT "abcabcdabcdabcabcd");
1889        assert_pattern!(
1890            "abcabc?abc?abcabc?abc?abc?bc?abc?bc?bcd",
1891            "abcabcdabcdabcabcdabcdabcabcdabcabcabcd"
1892        );
1893        assert_pattern!("?abc?", "?abc?");
1894    }
1895
1896    #[test]
1897    fn test_builder_complexity() {
1898        assert!(
1899            Pattern::builder("{foo,bar}")
1900                .max_complexity(1)
1901                .build()
1902                .is_err()
1903        );
1904        assert!(
1905            Pattern::builder("{foo,bar}")
1906                .max_complexity(2)
1907                .build()
1908                .is_ok()
1909        );
1910        assert!(
1911            Pattern::builder("{foo,bar}/{*.html,*.js,*.css}")
1912                .max_complexity(5)
1913                .build()
1914                .is_err()
1915        );
1916        assert!(
1917            Pattern::builder("{foo,bar}/{*.html,*.js,*.css}")
1918                .max_complexity(6)
1919                .build()
1920                .is_ok()
1921        );
1922    }
1923
1924    #[test]
1925    fn test_patterns() {
1926        let patterns = Patterns::builder()
1927            .add("foobaR")
1928            .unwrap()
1929            .add("a*")
1930            .unwrap()
1931            .add("*a")
1932            .unwrap()
1933            .add("[0-9]*baz")
1934            .unwrap()
1935            .take();
1936
1937        assert!(patterns.is_match("foobaR"));
1938        assert!(patterns.is_match("abc"));
1939        assert!(patterns.is_match("cba"));
1940        assert!(patterns.is_match("3baz"));
1941        assert!(patterns.is_match("123456789baz"));
1942        assert!(!patterns.is_match("foobar"));
1943        assert!(!patterns.is_match("FOOBAR"));
1944    }
1945
1946    #[test]
1947    fn test_patterns_case_insensitive() {
1948        let patterns = Patterns::builder()
1949            .case_insensitive(true)
1950            .add("fOObar")
1951            .unwrap()
1952            .add("a*")
1953            .unwrap()
1954            .add("*a")
1955            .unwrap()
1956            .add("[0-9]*baz")
1957            .unwrap()
1958            .take();
1959
1960        assert!(patterns.is_match("FooBar"));
1961        assert!(patterns.is_match("abC"));
1962        assert!(patterns.is_match("cbA"));
1963        assert!(patterns.is_match("3BAZ"));
1964        assert!(patterns.is_match("123456789baz"));
1965        assert!(!patterns.is_match("b"));
1966    }
1967
1968    #[test]
1969    fn test_patterns_take_clears_builder() {
1970        let mut builder = Patterns::builder().add("foo").unwrap();
1971
1972        let patterns = builder.take();
1973        assert!(patterns.is_match("foo"));
1974        assert!(!patterns.is_match("bar"));
1975
1976        builder.add("bar").unwrap();
1977        let patterns = builder.build();
1978        assert!(!patterns.is_match("foo"));
1979        assert!(patterns.is_match("bar"));
1980    }
1981}
relay_pattern/lib.rs

relay_pattern/
lib.rs
