arrow_string/
binary_predicate.rs1use arrow_array::{Array, ArrayAccessor, BinaryViewArray, BooleanArray};
6use arrow_buffer::BooleanBuffer;
7use memchr::memmem::Finder;
8use std::iter::zip;
9
10#[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 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 #[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
84fn 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}
97fn 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 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}