1use arrow_array::{Array, ArrayAccessor, BooleanArray, StringViewArray};
6use arrow_buffer::BooleanBuffer;
7use arrow_schema::ArrowError;
8use memchr::memchr3;
9use memchr::memmem::Finder;
10use regex::{Regex, RegexBuilder};
11use std::iter::zip;
12
13#[cfg_attr(target_arch = "x86_64", expect(clippy::large_enum_variant))]
15pub(crate) enum Predicate<'a> {
16 Eq(&'a str),
17 Contains(Finder<'a>),
18 StartsWith(&'a str),
19 EndsWith(&'a str),
20
21 IEqAscii(&'a str),
23 IStartsWithAscii(&'a str),
25 IEndsWithAscii(&'a str),
27
28 Regex(Regex),
29}
30
31impl<'a> Predicate<'a> {
32 pub(crate) fn like(pattern: &'a str) -> Result<Self, ArrowError> {
34 if !contains_like_pattern(pattern) {
35 Ok(Self::Eq(pattern))
36 } else if pattern.ends_with('%') && !contains_like_pattern(&pattern[..pattern.len() - 1]) {
37 Ok(Self::StartsWith(&pattern[..pattern.len() - 1]))
38 } else if pattern.starts_with('%') && !contains_like_pattern(&pattern[1..]) {
39 Ok(Self::EndsWith(&pattern[1..]))
40 } else if pattern.starts_with('%')
41 && pattern.ends_with('%')
42 && !contains_like_pattern(&pattern[1..pattern.len() - 1])
43 {
44 Ok(Self::contains(&pattern[1..pattern.len() - 1]))
45 } else {
46 Ok(Self::Regex(regex_like(pattern, false)?))
47 }
48 }
49
50 pub(crate) fn contains(needle: &'a str) -> Self {
51 Self::Contains(Finder::new(needle.as_bytes()))
52 }
53
54 pub(crate) fn ilike(pattern: &'a str, is_ascii: bool) -> Result<Self, ArrowError> {
56 if is_ascii && pattern.is_ascii() {
57 if !contains_like_pattern(pattern) {
58 return Ok(Self::IEqAscii(pattern));
59 } else if pattern.ends_with('%')
60 && !pattern.ends_with("\\%")
61 && !contains_like_pattern(&pattern[..pattern.len() - 1])
62 {
63 return Ok(Self::IStartsWithAscii(&pattern[..pattern.len() - 1]));
64 } else if pattern.starts_with('%') && !contains_like_pattern(&pattern[1..]) {
65 return Ok(Self::IEndsWithAscii(&pattern[1..]));
66 }
67 }
68 Ok(Self::Regex(regex_like(pattern, true)?))
69 }
70
71 pub(crate) fn evaluate(&self, haystack: &str) -> bool {
73 match self {
74 Predicate::Eq(v) => *v == haystack,
75 Predicate::IEqAscii(v) => haystack.eq_ignore_ascii_case(v),
76 Predicate::Contains(finder) => finder.find(haystack.as_bytes()).is_some(),
77 Predicate::StartsWith(v) => starts_with(haystack, v, equals_kernel),
78 Predicate::IStartsWithAscii(v) => {
79 starts_with(haystack, v, equals_ignore_ascii_case_kernel)
80 }
81 Predicate::EndsWith(v) => ends_with(haystack, v, equals_kernel),
82 Predicate::IEndsWithAscii(v) => ends_with(haystack, v, equals_ignore_ascii_case_kernel),
83 Predicate::Regex(v) => v.is_match(haystack),
84 }
85 }
86
87 #[inline(never)]
91 pub(crate) fn evaluate_array<'i, T>(&self, array: T, negate: bool) -> BooleanArray
92 where
93 T: ArrayAccessor<Item = &'i str>,
94 {
95 match self {
96 Predicate::Eq(v) => BooleanArray::from_unary(array, |haystack| {
97 (haystack.len() == v.len() && haystack == *v) != negate
98 }),
99 Predicate::IEqAscii(v) => BooleanArray::from_unary(array, |haystack| {
100 haystack.eq_ignore_ascii_case(v) != negate
101 }),
102 Predicate::Contains(finder) => BooleanArray::from_unary(array, |haystack| {
103 finder.find(haystack.as_bytes()).is_some() != negate
104 }),
105 Predicate::StartsWith(v) => {
106 if let Some(string_view_array) = array.as_any().downcast_ref::<StringViewArray>() {
107 let nulls = string_view_array.logical_nulls();
108 let values = BooleanBuffer::from(
109 string_view_array
110 .prefix_bytes_iter(v.len())
111 .map(|haystack| {
112 equals_bytes(haystack, v.as_bytes(), equals_kernel) != negate
113 })
114 .collect::<Vec<_>>(),
115 );
116 BooleanArray::new(values, nulls)
117 } else {
118 BooleanArray::from_unary(array, |haystack| {
119 starts_with(haystack, v, equals_kernel) != negate
120 })
121 }
122 }
123 Predicate::IStartsWithAscii(v) => {
124 if let Some(string_view_array) = array.as_any().downcast_ref::<StringViewArray>() {
125 let nulls = string_view_array.logical_nulls();
126 let values = BooleanBuffer::from(
127 string_view_array
128 .prefix_bytes_iter(v.len())
129 .map(|haystack| {
130 equals_bytes(
131 haystack,
132 v.as_bytes(),
133 equals_ignore_ascii_case_kernel,
134 ) != negate
135 })
136 .collect::<Vec<_>>(),
137 );
138 BooleanArray::new(values, nulls)
139 } else {
140 BooleanArray::from_unary(array, |haystack| {
141 starts_with(haystack, v, equals_ignore_ascii_case_kernel) != negate
142 })
143 }
144 }
145 Predicate::EndsWith(v) => {
146 if let Some(string_view_array) = array.as_any().downcast_ref::<StringViewArray>() {
147 let nulls = string_view_array.logical_nulls();
148 let values = BooleanBuffer::from(
149 string_view_array
150 .suffix_bytes_iter(v.len())
151 .map(|haystack| {
152 equals_bytes(haystack, v.as_bytes(), equals_kernel) != negate
153 })
154 .collect::<Vec<_>>(),
155 );
156 BooleanArray::new(values, nulls)
157 } else {
158 BooleanArray::from_unary(array, |haystack| {
159 ends_with(haystack, v, equals_kernel) != negate
160 })
161 }
162 }
163 Predicate::IEndsWithAscii(v) => {
164 if let Some(string_view_array) = array.as_any().downcast_ref::<StringViewArray>() {
165 let nulls = string_view_array.logical_nulls();
166 let values = BooleanBuffer::from(
167 string_view_array
168 .suffix_bytes_iter(v.len())
169 .map(|haystack| {
170 equals_bytes(
171 haystack,
172 v.as_bytes(),
173 equals_ignore_ascii_case_kernel,
174 ) != negate
175 })
176 .collect::<Vec<_>>(),
177 );
178 BooleanArray::new(values, nulls)
179 } else {
180 BooleanArray::from_unary(array, |haystack| {
181 ends_with(haystack, v, equals_ignore_ascii_case_kernel) != negate
182 })
183 }
184 }
185 Predicate::Regex(v) => {
186 BooleanArray::from_unary(array, |haystack| v.is_match(haystack) != negate)
187 }
188 }
189 }
190}
191
192fn equals_bytes(lhs: &[u8], rhs: &[u8], byte_eq_kernel: impl Fn((&u8, &u8)) -> bool) -> bool {
193 lhs.len() == rhs.len() && zip(lhs, rhs).all(byte_eq_kernel)
194}
195
196fn starts_with(haystack: &str, needle: &str, byte_eq_kernel: impl Fn((&u8, &u8)) -> bool) -> bool {
199 if needle.len() > haystack.len() {
200 false
201 } else {
202 zip(haystack.as_bytes(), needle.as_bytes()).all(byte_eq_kernel)
203 }
204}
205fn ends_with(haystack: &str, needle: &str, byte_eq_kernel: impl Fn((&u8, &u8)) -> bool) -> bool {
208 if needle.len() > haystack.len() {
209 false
210 } else {
211 zip(
212 haystack.as_bytes().iter().rev(),
213 needle.as_bytes().iter().rev(),
214 )
215 .all(byte_eq_kernel)
216 }
217}
218
219fn equals_kernel((n, h): (&u8, &u8)) -> bool {
220 n == h
221}
222
223fn equals_ignore_ascii_case_kernel((n, h): (&u8, &u8)) -> bool {
224 n.eq_ignore_ascii_case(h)
225}
226
227fn regex_like(pattern: &str, case_insensitive: bool) -> Result<Regex, ArrowError> {
235 let mut result = String::with_capacity(pattern.len() * 2);
236 let mut chars_iter = pattern.chars().peekable();
237 match chars_iter.peek() {
238 Some('%') => {
240 chars_iter.next();
241 }
242 _ => result.push('^'),
243 }
244
245 while let Some(c) = chars_iter.next() {
246 match c {
247 '\\' => {
248 match chars_iter.peek() {
249 Some(&next) => {
250 if regex_syntax::is_meta_character(next) {
251 result.push('\\');
252 }
253 result.push(next);
254 chars_iter.next();
256 }
257 None => {
258 result.push('\\');
260 result.push('\\');
261 }
262 }
263 }
264 '%' => result.push_str(".*"),
265 '_' => result.push('.'),
266 c => {
267 if regex_syntax::is_meta_character(c) {
268 result.push('\\');
269 }
270 result.push(c);
271 }
272 }
273 }
274 if result.ends_with(".*") {
276 result.pop();
277 result.pop();
278 } else {
279 result.push('$');
280 }
281 RegexBuilder::new(&result)
282 .case_insensitive(case_insensitive)
283 .dot_matches_new_line(true)
284 .build()
285 .map_err(|e| {
286 ArrowError::InvalidArgumentError(format!(
287 "Unable to build regex from LIKE pattern: {e}"
288 ))
289 })
290}
291
292fn contains_like_pattern(pattern: &str) -> bool {
293 memchr3(b'%', b'_', b'\\', pattern.as_bytes()).is_some()
294}
295
296#[cfg(test)]
297mod tests {
298 use super::*;
299
300 #[test]
301 fn test_regex_like() {
302 let test_cases = [
303 (r"%foobar%", r"foobar"),
305 (r"foo%bar", r"^foo.*bar$"),
307 (r"foo_bar", r"^foo.bar$"),
309 (r"\%\_", r"^%_$"),
311 (r"\a", r"^a$"),
313 (r"\\%", r"^\\"),
315 (r"\\a", r"^\\a$"),
317 (r".", r"^\.$"),
319 (r"$", r"^\$$"),
320 (r"\\", r"^\\$"),
321 ];
322
323 for (like_pattern, expected_regexp) in test_cases {
324 let r = regex_like(like_pattern, false).unwrap();
325 assert_eq!(r.to_string(), expected_regexp);
326 }
327 }
328
329 #[test]
330 fn test_contains() {
331 assert!(Predicate::contains("hay").evaluate("haystack"));
332 assert!(Predicate::contains("haystack").evaluate("haystack"));
333 assert!(Predicate::contains("h").evaluate("haystack"));
334 assert!(Predicate::contains("k").evaluate("haystack"));
335 assert!(Predicate::contains("stack").evaluate("haystack"));
336 assert!(Predicate::contains("sta").evaluate("haystack"));
337 assert!(Predicate::contains("stack").evaluate("hay£stack"));
338 assert!(Predicate::contains("y£s").evaluate("hay£stack"));
339 assert!(Predicate::contains("£").evaluate("hay£stack"));
340 assert!(Predicate::contains("a").evaluate("a"));
341 assert!(!Predicate::contains("hy").evaluate("haystack"));
343 assert!(!Predicate::contains("stackx").evaluate("haystack"));
344 assert!(!Predicate::contains("x").evaluate("haystack"));
345 assert!(!Predicate::contains("haystack haystack").evaluate("haystack"));
346 }
347
348 #[test]
349 fn test_starts_with() {
350 assert!(Predicate::StartsWith("hay").evaluate("haystack"));
351 assert!(Predicate::StartsWith("h£ay").evaluate("h£aystack"));
352 assert!(Predicate::StartsWith("haystack").evaluate("haystack"));
353 assert!(Predicate::StartsWith("ha").evaluate("haystack"));
354 assert!(Predicate::StartsWith("h").evaluate("haystack"));
355 assert!(Predicate::StartsWith("").evaluate("haystack"));
356
357 assert!(!Predicate::StartsWith("stack").evaluate("haystack"));
358 assert!(!Predicate::StartsWith("haystacks").evaluate("haystack"));
359 assert!(!Predicate::StartsWith("HAY").evaluate("haystack"));
360 assert!(!Predicate::StartsWith("h£ay").evaluate("haystack"));
361 assert!(!Predicate::StartsWith("hay").evaluate("h£aystack"));
362 }
363
364 #[test]
365 fn test_ends_with() {
366 assert!(Predicate::EndsWith("stack").evaluate("haystack"));
367 assert!(Predicate::EndsWith("st£ack").evaluate("hayst£ack"));
368 assert!(Predicate::EndsWith("haystack").evaluate("haystack"));
369 assert!(Predicate::EndsWith("ck").evaluate("haystack"));
370 assert!(Predicate::EndsWith("k").evaluate("haystack"));
371 assert!(Predicate::EndsWith("").evaluate("haystack"));
372
373 assert!(!Predicate::EndsWith("hay").evaluate("haystack"));
374 assert!(!Predicate::EndsWith("STACK").evaluate("haystack"));
375 assert!(!Predicate::EndsWith("haystacks").evaluate("haystack"));
376 assert!(!Predicate::EndsWith("xhaystack").evaluate("haystack"));
377 assert!(!Predicate::EndsWith("st£ack").evaluate("haystack"));
378 assert!(!Predicate::EndsWith("stack").evaluate("hayst£ack"));
379 }
380
381 #[test]
382 fn test_istarts_with() {
383 assert!(Predicate::IStartsWithAscii("hay").evaluate("haystack"));
384 assert!(Predicate::IStartsWithAscii("hay").evaluate("HAYSTACK"));
385 assert!(Predicate::IStartsWithAscii("HAY").evaluate("haystack"));
386 assert!(Predicate::IStartsWithAscii("HaY").evaluate("haystack"));
387 assert!(Predicate::IStartsWithAscii("hay").evaluate("HaYsTaCk"));
388 assert!(Predicate::IStartsWithAscii("HAY").evaluate("HaYsTaCk"));
389 assert!(Predicate::IStartsWithAscii("haystack").evaluate("HaYsTaCk"));
390 assert!(Predicate::IStartsWithAscii("HaYsTaCk").evaluate("HaYsTaCk"));
391 assert!(Predicate::IStartsWithAscii("").evaluate("HaYsTaCk"));
392
393 assert!(!Predicate::IStartsWithAscii("stack").evaluate("haystack"));
394 assert!(!Predicate::IStartsWithAscii("haystacks").evaluate("haystack"));
395 assert!(!Predicate::IStartsWithAscii("h.ay").evaluate("haystack"));
396 assert!(!Predicate::IStartsWithAscii("hay").evaluate("h£aystack"));
397 }
398
399 #[test]
400 fn test_iends_with() {
401 assert!(Predicate::IEndsWithAscii("stack").evaluate("haystack"));
402 assert!(Predicate::IEndsWithAscii("STACK").evaluate("haystack"));
403 assert!(Predicate::IEndsWithAscii("StAcK").evaluate("haystack"));
404 assert!(Predicate::IEndsWithAscii("stack").evaluate("HAYSTACK"));
405 assert!(Predicate::IEndsWithAscii("STACK").evaluate("HAYSTACK"));
406 assert!(Predicate::IEndsWithAscii("StAcK").evaluate("HAYSTACK"));
407 assert!(Predicate::IEndsWithAscii("stack").evaluate("HAYsTaCk"));
408 assert!(Predicate::IEndsWithAscii("STACK").evaluate("HAYsTaCk"));
409 assert!(Predicate::IEndsWithAscii("StAcK").evaluate("HAYsTaCk"));
410 assert!(Predicate::IEndsWithAscii("haystack").evaluate("haystack"));
411 assert!(Predicate::IEndsWithAscii("HAYSTACK").evaluate("haystack"));
412 assert!(Predicate::IEndsWithAscii("haystack").evaluate("HAYSTACK"));
413 assert!(Predicate::IEndsWithAscii("ck").evaluate("haystack"));
414 assert!(Predicate::IEndsWithAscii("cK").evaluate("haystack"));
415 assert!(Predicate::IEndsWithAscii("ck").evaluate("haystacK"));
416 assert!(Predicate::IEndsWithAscii("").evaluate("haystack"));
417
418 assert!(!Predicate::IEndsWithAscii("hay").evaluate("haystack"));
419 assert!(!Predicate::IEndsWithAscii("stac").evaluate("HAYSTACK"));
420 assert!(!Predicate::IEndsWithAscii("haystacks").evaluate("haystack"));
421 assert!(!Predicate::IEndsWithAscii("stack").evaluate("haystac£k"));
422 assert!(!Predicate::IEndsWithAscii("xhaystack").evaluate("haystack"));
423 }
424}