s3s_policy/
pattern.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2023-2026 The s3s Authors
3
4pub struct PatternSet {
5    // TODO: rewrite the naive implementation with something like Aho-Corasick
6    patterns: Vec<Pattern>,
7}
8
9#[derive(Debug, thiserror::Error)]
10pub enum PatternError {
11    #[error("Invalid pattern")]
12    InvalidPattern,
13}
14
15#[derive(Debug)]
16struct Pattern {
17    bytes: Vec<u8>,
18}
19
20impl PatternSet {
21    /// Create a new matcher from a list of patterns.
22    ///
23    /// Patterns can contain
24    /// + `*` to match any sequence of characters (including empty sequence)
25    /// + `?` to match any single character
26    /// + any other character to match itself
27    ///
28    /// # Errors
29    /// Returns an error if any pattern is invalid.
30    pub fn new<'a>(patterns: impl IntoIterator<Item = &'a str>) -> Result<PatternSet, PatternError> {
31        let patterns = patterns.into_iter().map(Self::parse_pattern).collect::<Result<_, _>>()?;
32        Ok(PatternSet { patterns })
33    }
34
35    fn parse_pattern(pattern: &str) -> Result<Pattern, PatternError> {
36        if pattern.is_empty() {
37            return Err(PatternError::InvalidPattern);
38        }
39        Ok(Pattern {
40            bytes: pattern.as_bytes().to_owned(),
41        })
42    }
43
44    /// Check if the input matches any of the patterns.
45    #[must_use]
46    pub fn is_match(&self, input: &str) -> bool {
47        for pattern in &self.patterns {
48            if Self::match_pattern(&pattern.bytes, input.as_bytes()) {
49                return true;
50            }
51        }
52        false
53    }
54
55    /// <https://leetcode.com/problems/wildcard-matching/>
56    fn match_pattern(pattern: &[u8], input: &[u8]) -> bool {
57        let mut p_idx = 0;
58        let mut s_idx = 0;
59
60        let mut p_back = usize::MAX - 1;
61        let mut s_back = usize::MAX - 1;
62
63        loop {
64            if p_idx < pattern.len() {
65                let p = pattern[p_idx];
66                if p == b'*' {
67                    p_idx += 1;
68                    p_back = p_idx;
69                    s_back = s_idx;
70                    continue;
71                }
72
73                if s_idx < input.len() {
74                    let c = input[s_idx];
75                    if p == c || p == b'?' {
76                        p_idx += 1;
77                        s_idx += 1;
78                        continue;
79                    }
80                }
81            } else if s_idx == input.len() {
82                return true;
83            }
84
85            if p_back == pattern.len() {
86                return true;
87            }
88
89            if s_back + 1 < input.len() {
90                s_back += 1;
91                p_idx = p_back;
92                s_idx = s_back;
93                continue;
94            }
95
96            return false;
97        }
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn test_match() {
107        let cases = &[
108            ("*", "", true),
109            ("**", "", true),
110            ("***", "abc", true),
111            ("a", "aa", false),
112            ("***a", "aaaa", true),
113            ("*abc???def", "abcdefabc123def", true),
114            ("a*c?b", "acdcb", false),
115            ("*a*b*c*", "abc", true),
116            ("a*b*c*", "abc", true),
117            ("*a*b*c", "abc", true),
118            ("a*b*c", "abc", true),
119        ];
120
121        for &(pattern, input, expected) in cases {
122            let pattern = PatternSet::parse_pattern(pattern).unwrap();
123            let ans = PatternSet::match_pattern(&pattern.bytes, input.as_bytes());
124            assert_eq!(ans, expected, "pattern: {pattern:?}, input: {input:?}");
125        }
126    }
127}
s3s_policy/pattern.rs

s3s_policy/
pattern.rs
