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

relay_pattern/
lib.rs
