yo_common/glob.rs
1//! Redis's glob matching, which is what `KEYS`, `SCAN MATCH`, `CONFIG GET` and
2//! `COMMAND LIST FILTERBY PATTERN` all mean by a pattern.
3//!
4//! It is not a regular expression and it is not the shell's glob either. There
5//! are four things in it: `*` for any run of bytes, `?` for one byte, `[...]`
6//! for a class, and a backslash for the byte after it. Everything else is a
7//! literal, including the bytes that are special in a regular expression, so
8//! `user.*` matches `user.1` and does not match `userX1`.
9//!
10//! Bytes rather than characters, the same as Redis. A pattern is matched
11//! against a key, a key is arbitrary bytes, and deciding what a character is
12//! would mean deciding what encoding a key is in, which nobody can do.
13
14/// Whether `text` matches `pattern`.
15///
16/// The `*` case backtracks: on a mismatch the search goes back to the last star
17/// and gives it one more byte. That is quadratic on a pattern built to be slow,
18/// such as a run of stars against a long key, and it is what Redis does. The
19/// difference is that Redis walks the whole keyspace with it and this walks a
20/// list of settings, so the pathological case is not reachable from a client
21/// until `KEYS` lands, at which point the cost is the keyspace scan and not
22/// this.
23#[must_use]
24pub fn matches(pattern: &[u8], text: &[u8]) -> bool {
25 matches_nocase(pattern, text, false)
26}
27
28/// Whether `text` matches `pattern`, optionally ignoring ASCII case.
29///
30/// `ARGREP GLOB` is the one caller that asks for the fold. Redis folds in three
31/// of the four places a byte is compared: a literal, an escaped literal and both
32/// ends of a range. The one it leaves alone is an escaped byte inside a class,
33/// so `[\A]` under `NOCASE` matches an `A` and not an `a`, which reads like an
34/// oversight and is old enough to be relied on.
35///
36/// The fold is ASCII only, deliberately, because the subject is arbitrary bytes
37/// and folding by a locale would make the answer depend on the machine.
38#[must_use]
39pub fn matches_nocase(pattern: &[u8], text: &[u8], nocase: bool) -> bool {
40 let (mut p, mut t) = (0usize, 0usize);
41 // Where to go back to when a `*` has to give up a byte. `None` until the
42 // first star, which is what makes a pattern without one a straight walk.
43 let mut star: Option<usize> = None;
44 let mut mark = 0usize;
45 while t < text.len() {
46 let mut step = false;
47 if p < pattern.len() {
48 match pattern[p] {
49 b'*' => {
50 star = Some(p);
51 mark = t;
52 p += 1;
53 continue;
54 }
55 b'?' => {
56 p += 1;
57 t += 1;
58 continue;
59 }
60 b'[' => {
61 let (next, hit) = class(pattern, p, text[t], nocase);
62 if hit {
63 p = next;
64 step = true;
65 }
66 }
67 b'\\' if p + 1 < pattern.len() => {
68 if same(pattern[p + 1], text[t], nocase) {
69 p += 2;
70 step = true;
71 }
72 }
73 c => {
74 if same(c, text[t], nocase) {
75 p += 1;
76 step = true;
77 }
78 }
79 }
80 }
81 if step {
82 t += 1;
83 continue;
84 }
85 match star {
86 Some(at) => {
87 p = at + 1;
88 mark += 1;
89 t = mark;
90 }
91 None => return false,
92 }
93 }
94 // Trailing stars match nothing, which is the one place a pattern is allowed
95 // to be longer than what it matched.
96 while p < pattern.len() && pattern[p] == b'*' {
97 p += 1;
98 }
99 p == pattern.len()
100}
101
102/// Match one byte against the class starting at `p`, which is a `[`.
103///
104/// Answers where the class ends and whether the byte belongs to it. A class
105/// with no closing bracket ends at the end of the pattern rather than being an
106/// error, which is Redis's reading and means a stray bracket in a key pattern
107/// is never a refusal.
108fn class(pattern: &[u8], p: usize, c: u8, nocase: bool) -> (usize, bool) {
109 let mut i = p + 1;
110 let negate = i < pattern.len() && pattern[i] == b'^';
111 if negate {
112 i += 1;
113 }
114 let mut hit = false;
115 while i < pattern.len() && pattern[i] != b']' {
116 if pattern[i] == b'\\' && i + 1 < pattern.len() {
117 i += 1;
118 // The one comparison Redis does not fold.
119 hit |= pattern[i] == c;
120 i += 1;
121 } else if i + 2 < pattern.len() && pattern[i + 1] == b'-' && pattern[i + 2] != b']' {
122 let (mut lo, mut hi) = (pattern[i], pattern[i + 2]);
123 // Redis puts the ends the right way round before it folds them and
124 // not after, so `[Z-a]` under NOCASE is the empty range `z` to `a`
125 // rather than the whole of the alphabet.
126 if lo > hi {
127 core::mem::swap(&mut lo, &mut hi);
128 }
129 let (lo, hi, c) = if nocase {
130 (fold(lo), fold(hi), fold(c))
131 } else {
132 (lo, hi, c)
133 };
134 hit |= c >= lo && c <= hi;
135 i += 3;
136 } else {
137 hit |= same(pattern[i], c, nocase);
138 i += 1;
139 }
140 }
141 let next = if i < pattern.len() { i + 1 } else { i };
142 (next, hit != negate)
143}
144
145/// One ASCII letter in lower case, and every other byte as it was.
146fn fold(b: u8) -> u8 {
147 b.to_ascii_lowercase()
148}
149
150/// Whether two bytes are the same, ASCII case aside when asked.
151fn same(a: u8, b: u8, nocase: bool) -> bool {
152 a == b || (nocase && fold(a) == fold(b))
153}
154
155#[cfg(test)]
156mod tests {
157 use super::*;
158
159 #[test]
160 fn a_pattern_without_a_wildcard_is_an_equality_test() {
161 assert!(matches(b"maxmemory", b"maxmemory"));
162 assert!(!matches(b"maxmemory", b"maxmemory-policy"));
163 assert!(!matches(b"maxmemory-policy", b"maxmemory"));
164 assert!(matches(b"", b""));
165 assert!(!matches(b"", b"x"));
166 }
167
168 #[test]
169 fn stars_match_any_run_including_none() {
170 assert!(matches(b"*", b""));
171 assert!(matches(b"*", b"anything at all"));
172 assert!(matches(b"maxmemory*", b"maxmemory"));
173 assert!(matches(b"maxmemory*", b"maxmemory-policy"));
174 assert!(matches(b"*policy", b"maxmemory-policy"));
175 assert!(matches(b"max*policy", b"maxmemory-policy"));
176 assert!(!matches(b"max*policy", b"maxmemory-clients"));
177 assert!(matches(b"a**b", b"ab"));
178 }
179
180 #[test]
181 fn a_question_mark_is_exactly_one_byte() {
182 assert!(matches(b"h?llo", b"hello"));
183 assert!(!matches(b"h?llo", b"hllo"));
184 assert!(!matches(b"h?llo", b"heello"));
185 }
186
187 #[test]
188 fn classes_do_ranges_and_negation() {
189 assert!(matches(b"h[ae]llo", b"hello"));
190 assert!(matches(b"h[ae]llo", b"hallo"));
191 assert!(!matches(b"h[ae]llo", b"hillo"));
192 assert!(matches(b"h[^e]llo", b"hallo"));
193 assert!(!matches(b"h[^e]llo", b"hello"));
194 assert!(matches(b"key[0-9]", b"key7"));
195 assert!(!matches(b"key[0-9]", b"keyx"));
196 // A range the wrong way round is read as if it were the right way
197 // round, which is what Redis does rather than matching nothing.
198 assert!(matches(b"key[9-0]", b"key7"));
199 }
200
201 #[test]
202 fn a_backslash_takes_the_special_out_of_the_next_byte() {
203 assert!(matches(br"a\*b", b"a*b"));
204 assert!(!matches(br"a\*b", b"axxb"));
205 assert!(matches(br"a\\b", br"a\b"));
206 }
207
208 /// The pattern that would run away if the backtracking were wrong. It
209 /// answers rather than hanging, which is the whole point of the test.
210 #[test]
211 fn a_pattern_built_to_be_slow_still_answers() {
212 let pattern = b"*a*a*a*a*a*b";
213 let text = vec![b'a'; 64];
214 assert!(!matches(pattern, &text));
215 }
216
217 #[test]
218 fn nocase_folds_everything_except_an_escape_inside_a_class() {
219 assert!(matches_nocase(b"HELLO", b"hello", true));
220 assert!(matches_nocase(b"h*O", b"hello", true));
221 assert!(matches_nocase(b"h[AE]llo", b"hello", true));
222 assert!(matches_nocase(b"KEY[A-Z]", b"keyx", true));
223 assert!(matches_nocase(br"a\Bc", b"abc", true));
224 assert!(!matches_nocase(b"HELLO", b"hello", false));
225 // The odd one out. Redis compares an escaped class item raw, so the
226 // fold does not reach it.
227 assert!(!matches_nocase(br"a[\B]c", b"abc", true));
228 assert!(matches_nocase(br"a[\B]c", b"aBc", true));
229 // The ends of a range are put in order before they are folded, which
230 // makes this one empty rather than everything from Z to a.
231 assert!(!matches_nocase(b"[Z-a]", b"b", true));
232 }
233
234 /// Not an error, and not a match for a bracket that is not there.
235 #[test]
236 fn a_class_that_is_never_closed_ends_at_the_end() {
237 assert!(matches(b"a[bc", b"ab"));
238 assert!(!matches(b"a[bc", b"ax"));
239 }
240}