Skip to main content

arrow_string/
predicate.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use 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/// A string based predicate
14#[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    /// Equality ignoring ASCII case
22    IEqAscii(&'a str),
23    /// Starts with ignoring ASCII case
24    IStartsWithAscii(&'a str),
25    /// Ends with ignoring ASCII case
26    IEndsWithAscii(&'a str),
27
28    Regex(Regex),
29}
30
31impl<'a> Predicate<'a> {
32    /// Create a predicate for the given like pattern
33    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    /// Create a predicate for the given ilike pattern
55    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    /// Evaluate this predicate against the given haystack
72    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    /// Evaluate this predicate against the elements of `array`
88    ///
89    /// If `negate` is true the result of the predicate will be negated
90    #[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
196/// This is faster than `str::starts_with` for small strings.
197/// See <https://github.com/apache/arrow-rs/issues/6107> for more details.
198fn 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}
205/// This is faster than `str::ends_with` for small strings.
206/// See <https://github.com/apache/arrow-rs/issues/6107> for more details.
207fn 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
227/// Transforms a like `pattern` to a regex compatible pattern. To achieve that, it does:
228///
229/// 1. Replace `LIKE` multi-character wildcards `%` => `.*` (unless they're at the start or end of the pattern,
230///    where the regex is just truncated - e.g. `%foo%` => `foo` rather than `^.*foo.*$`)
231/// 2. Replace `LIKE` single-character wildcards `_` => `.`
232/// 3. Escape regex meta characters to match them and not be evaluated as regex special chars. e.g. `.` => `\\.`
233/// 4. Replace escaped `LIKE` wildcards removing the escape characters to be able to match it as a regex. e.g. `\\%` => `%`
234fn 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        // if the pattern starts with `%`, we avoid starting the regex with a slow but meaningless `^.*`
239        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                        // Skipping the next char as it is already appended
255                        chars_iter.next();
256                    }
257                    None => {
258                        // Trailing backslash in the pattern. E.g. PostgreSQL and Trino treat it as an error, but e.g. Snowflake treats it as a literal backslash
259                        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    // instead of ending the regex with `.*$` and making it needlessly slow, we just end the regex
275    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            // %..%
304            (r"%foobar%", r"foobar"),
305            // ..%..
306            (r"foo%bar", r"^foo.*bar$"),
307            // .._..
308            (r"foo_bar", r"^foo.bar$"),
309            // escaped wildcards
310            (r"\%\_", r"^%_$"),
311            // escaped non-wildcard
312            (r"\a", r"^a$"),
313            // escaped escape and wildcard
314            (r"\\%", r"^\\"),
315            // escaped escape and non-wildcard
316            (r"\\a", r"^\\a$"),
317            // regex meta character
318            (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        // not matching
342        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}