Skip to main content

arrow_string/
binary_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, BinaryViewArray, BooleanArray};
6use arrow_buffer::BooleanBuffer;
7use memchr::memmem::Finder;
8use std::iter::zip;
9
10/// A binary based predicate
11#[cfg_attr(target_arch = "x86_64", expect(clippy::large_enum_variant))]
12pub enum BinaryPredicate<'a> {
13    Contains(Finder<'a>),
14    StartsWith(&'a [u8]),
15    EndsWith(&'a [u8]),
16}
17
18impl<'a> BinaryPredicate<'a> {
19    pub fn contains(needle: &'a [u8]) -> Self {
20        Self::Contains(Finder::new(needle))
21    }
22
23    /// Evaluate this predicate against the given haystack
24    pub fn evaluate(&self, haystack: &[u8]) -> bool {
25        match self {
26            Self::Contains(finder) => finder.find(haystack).is_some(),
27            Self::StartsWith(v) => starts_with(haystack, v, equals_kernel),
28            Self::EndsWith(v) => ends_with(haystack, v, equals_kernel),
29        }
30    }
31
32    /// Evaluate this predicate against the elements of `array`
33    ///
34    /// If `negate` is true the result of the predicate will be negated
35    #[inline(never)]
36    pub fn evaluate_array<'i, T>(&self, array: T, negate: bool) -> BooleanArray
37    where
38        T: ArrayAccessor<Item = &'i [u8]>,
39    {
40        match self {
41            Self::Contains(finder) => BooleanArray::from_unary(array, |haystack| {
42                finder.find(haystack).is_some() != negate
43            }),
44            Self::StartsWith(v) => {
45                if let Some(view_array) = array.as_any().downcast_ref::<BinaryViewArray>() {
46                    let nulls = view_array.logical_nulls();
47                    let values = BooleanBuffer::from(
48                        view_array
49                            .prefix_bytes_iter(v.len())
50                            .map(|haystack| equals_bytes(haystack, v, equals_kernel) != negate)
51                            .collect::<Vec<_>>(),
52                    );
53                    BooleanArray::new(values, nulls)
54                } else {
55                    BooleanArray::from_unary(array, |haystack| {
56                        starts_with(haystack, v, equals_kernel) != negate
57                    })
58                }
59            }
60            Self::EndsWith(v) => {
61                if let Some(view_array) = array.as_any().downcast_ref::<BinaryViewArray>() {
62                    let nulls = view_array.logical_nulls();
63                    let values = BooleanBuffer::from(
64                        view_array
65                            .suffix_bytes_iter(v.len())
66                            .map(|haystack| equals_bytes(haystack, v, equals_kernel) != negate)
67                            .collect::<Vec<_>>(),
68                    );
69                    BooleanArray::new(values, nulls)
70                } else {
71                    BooleanArray::from_unary(array, |haystack| {
72                        ends_with(haystack, v, equals_kernel) != negate
73                    })
74                }
75            }
76        }
77    }
78}
79
80fn equals_bytes(lhs: &[u8], rhs: &[u8], byte_eq_kernel: impl Fn((&u8, &u8)) -> bool) -> bool {
81    lhs.len() == rhs.len() && zip(lhs, rhs).all(byte_eq_kernel)
82}
83
84/// This is faster than `[u8]::starts_with` for small slices.
85/// See <https://github.com/apache/arrow-rs/issues/6107> for more details.
86fn starts_with(
87    haystack: &[u8],
88    needle: &[u8],
89    byte_eq_kernel: impl Fn((&u8, &u8)) -> bool,
90) -> bool {
91    if needle.len() > haystack.len() {
92        false
93    } else {
94        zip(haystack, needle).all(byte_eq_kernel)
95    }
96}
97/// This is faster than `[u8]::ends_with` for small slices.
98/// See <https://github.com/apache/arrow-rs/issues/6107> for more details.
99fn ends_with(haystack: &[u8], needle: &[u8], byte_eq_kernel: impl Fn((&u8, &u8)) -> bool) -> bool {
100    if needle.len() > haystack.len() {
101        false
102    } else {
103        zip(haystack.iter().rev(), needle.iter().rev()).all(byte_eq_kernel)
104    }
105}
106
107fn equals_kernel((n, h): (&u8, &u8)) -> bool {
108    n == h
109}
110
111#[cfg(test)]
112mod tests {
113    use super::BinaryPredicate;
114
115    #[test]
116    fn test_contains() {
117        assert!(BinaryPredicate::contains(b"hay").evaluate(b"haystack"));
118        assert!(BinaryPredicate::contains(b"haystack").evaluate(b"haystack"));
119        assert!(BinaryPredicate::contains(b"h").evaluate(b"haystack"));
120        assert!(BinaryPredicate::contains(b"k").evaluate(b"haystack"));
121        assert!(BinaryPredicate::contains(b"stack").evaluate(b"haystack"));
122        assert!(BinaryPredicate::contains(b"sta").evaluate(b"haystack"));
123        assert!(BinaryPredicate::contains(b"stack").evaluate(b"hay\0stack"));
124        assert!(BinaryPredicate::contains(b"\0s").evaluate(b"hay\0stack"));
125        assert!(BinaryPredicate::contains(b"\0").evaluate(b"hay\0stack"));
126        assert!(BinaryPredicate::contains(b"a").evaluate(b"a"));
127        // not matching
128        assert!(!BinaryPredicate::contains(b"hy").evaluate(b"haystack"));
129        assert!(!BinaryPredicate::contains(b"stackx").evaluate(b"haystack"));
130        assert!(!BinaryPredicate::contains(b"x").evaluate(b"haystack"));
131        assert!(!BinaryPredicate::contains(b"haystack haystack").evaluate(b"haystack"));
132    }
133
134    #[test]
135    fn test_starts_with() {
136        assert!(BinaryPredicate::StartsWith(b"hay").evaluate(b"haystack"));
137        assert!(BinaryPredicate::StartsWith(b"h\0ay").evaluate(b"h\0aystack"));
138        assert!(BinaryPredicate::StartsWith(b"haystack").evaluate(b"haystack"));
139        assert!(BinaryPredicate::StartsWith(b"ha").evaluate(b"haystack"));
140        assert!(BinaryPredicate::StartsWith(b"h").evaluate(b"haystack"));
141        assert!(BinaryPredicate::StartsWith(b"").evaluate(b"haystack"));
142
143        assert!(!BinaryPredicate::StartsWith(b"stack").evaluate(b"haystack"));
144        assert!(!BinaryPredicate::StartsWith(b"haystacks").evaluate(b"haystack"));
145        assert!(!BinaryPredicate::StartsWith(b"HAY").evaluate(b"haystack"));
146        assert!(!BinaryPredicate::StartsWith(b"h\0ay").evaluate(b"haystack"));
147        assert!(!BinaryPredicate::StartsWith(b"hay").evaluate(b"h\0aystack"));
148    }
149
150    #[test]
151    fn test_ends_with() {
152        assert!(BinaryPredicate::EndsWith(b"stack").evaluate(b"haystack"));
153        assert!(BinaryPredicate::EndsWith(b"st\0ack").evaluate(b"hayst\0ack"));
154        assert!(BinaryPredicate::EndsWith(b"haystack").evaluate(b"haystack"));
155        assert!(BinaryPredicate::EndsWith(b"ck").evaluate(b"haystack"));
156        assert!(BinaryPredicate::EndsWith(b"k").evaluate(b"haystack"));
157        assert!(BinaryPredicate::EndsWith(b"").evaluate(b"haystack"));
158
159        assert!(!BinaryPredicate::EndsWith(b"hay").evaluate(b"haystack"));
160        assert!(!BinaryPredicate::EndsWith(b"STACK").evaluate(b"haystack"));
161        assert!(!BinaryPredicate::EndsWith(b"haystacks").evaluate(b"haystack"));
162        assert!(!BinaryPredicate::EndsWith(b"xhaystack").evaluate(b"haystack"));
163        assert!(!BinaryPredicate::EndsWith(b"st\0ack").evaluate(b"haystack"));
164        assert!(!BinaryPredicate::EndsWith(b"stack").evaluate(b"hayst\0ack"));
165    }
166}