1use std::mem::MaybeUninit;
5use std::ops::BitAnd;
6use std::ops::BitOr;
7use std::ops::Not;
8
9use itertools::Either;
10use vortex_buffer::Buffer;
11use vortex_buffer::BufferMut;
12use vortex_error::VortexExpect;
13use vortex_error::VortexResult;
14use vortex_mask::Mask;
15
16use crate::ArrayRef;
17use crate::ExecutionCtx;
18use crate::IntoArray;
19use crate::array::ArrayView;
20use crate::arrays::Chunked;
21use crate::arrays::ChunkedArray;
22use crate::arrays::ListView;
23use crate::arrays::ListViewArray;
24use crate::arrays::chunked::ChunkedArrayExt;
25use crate::arrays::listview::ListViewArraySlotsExt;
26use crate::builtins::ArrayBuiltins;
27use crate::dtype::DType;
28use crate::dtype::Nullability;
29use crate::dtype::PType;
30use crate::scalar_fn::fns::zip::ZipKernel;
31use crate::validity::Validity;
32
33impl ZipKernel for ListView {
43 fn zip(
44 if_true: ArrayView<'_, ListView>,
45 if_false: &ArrayRef,
46 mask: &ArrayRef,
47 ctx: &mut ExecutionCtx,
48 ) -> VortexResult<Option<ArrayRef>> {
49 let Some(if_false) = if_false.as_opt::<ListView>() else {
50 return Ok(None);
51 };
52
53 let mask = mask.clone().fill_null(false)?.execute::<Mask>(ctx)?;
55 match &mask {
56 Mask::AllTrue(_) | Mask::AllFalse(_) => return Ok(None),
58 Mask::Values(_) => {}
59 }
60
61 let len = if_true.len();
62
63 let result_elements_dtype = if_true
64 .elements()
65 .dtype()
66 .union_nullability(if_false.elements().dtype().nullability());
67
68 let true_elements = if_true.elements().cast(result_elements_dtype.clone())?;
71 let false_elements = if_false.elements().cast(result_elements_dtype.clone())?;
72
73 let false_shift = true_elements.len() as u64;
75
76 let chunks = element_chunks(&true_elements).chain(element_chunks(&false_elements));
80 let elements = ChunkedArray::try_new(chunks, result_elements_dtype)?.into_array();
81
82 let true_offsets = to_u64(if_true.offsets(), ctx)?;
83 let true_sizes = to_u64(if_true.sizes(), ctx)?;
84 let false_offsets = to_u64(if_false.offsets(), ctx)?;
85 let false_sizes = to_u64(if_false.sizes(), ctx)?;
86
87 let mut offsets = BufferMut::<u64>::with_capacity(len);
88 let mut sizes = BufferMut::<u64>::with_capacity(len);
89 {
90 let true_offsets = true_offsets.as_slice();
91 let true_sizes = true_sizes.as_slice();
92 let false_offsets = false_offsets.as_slice();
93 let false_sizes = false_sizes.as_slice();
94
95 let offsets_out = offsets.spare_capacity_mut();
96 let sizes_out = sizes.spare_capacity_mut();
97
98 let mask_bits = mask
104 .values()
105 .vortex_expect("mask is Mask::Values")
106 .bit_buffer();
107 let unaligned = mask_bits.unaligned_chunks();
108 let lead = unaligned.lead_padding();
111
112 let mut select_block = |word: u64, base: usize, n: usize| {
113 let end = base + n;
114 select_column(
117 word,
118 &true_offsets[base..end],
119 &false_offsets[base..end],
120 false_shift,
121 &mut offsets_out[base..end],
122 );
123 select_column(
124 word,
125 &true_sizes[base..end],
126 &false_sizes[base..end],
127 0,
128 &mut sizes_out[base..end],
129 );
130 };
131
132 let mut base = 0;
133 if let Some(prefix) = unaligned.prefix() {
134 let n = (64 - lead).min(len);
135 select_block(prefix >> lead, base, n);
136 base += n;
137 }
138 for &word in unaligned.chunks() {
139 select_block(word, base, 64);
140 base += 64;
141 }
142 if let Some(suffix) = unaligned.suffix() {
143 select_block(suffix, base, len - base);
144 }
145 }
146
147 unsafe {
149 offsets.set_len(len);
150 sizes.set_len(len);
151 }
152
153 let validity = zip_validity(if_true.validity()?, if_false.validity()?, &mask, ctx)?;
154
155 Ok(Some(
156 ListViewArray::try_new(
157 elements,
158 offsets.freeze().into_array(),
159 sizes.freeze().into_array(),
160 validity,
161 ctx,
162 )?
163 .into_array(),
164 ))
165 }
166}
167
168#[inline]
175fn select_column(
176 word: u64,
177 true_vals: &[u64],
178 false_vals: &[u64],
179 false_add: u64,
180 out: &mut [MaybeUninit<u64>],
181) {
182 let n = out.len();
183 let true_vals = &true_vals[..n];
184 let false_vals = &false_vals[..n];
185 for j in 0..n {
186 let lane = 0u64.wrapping_sub((word >> j) & 1);
188 out[j].write((true_vals[j] & lane) | ((false_vals[j] + false_add) & !lane));
189 }
190}
191
192fn element_chunks(array: &ArrayRef) -> impl Iterator<Item = ArrayRef> + '_ {
195 match array.as_opt::<Chunked>() {
196 Some(chunked) => {
197 Either::Left((0..chunked.nchunks()).map(move |i| chunked.chunk(i).clone()))
198 }
199 None => Either::Right(std::iter::once(array.clone())),
200 }
201}
202
203fn to_u64(array: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Buffer<u64>> {
205 array
206 .clone()
207 .cast(DType::Primitive(PType::U64, Nullability::NonNullable))?
208 .execute::<Buffer<u64>>(ctx)
209}
210
211fn zip_validity(
214 if_true: Validity,
215 if_false: Validity,
216 mask: &Mask,
217 ctx: &mut ExecutionCtx,
218) -> VortexResult<Validity> {
219 Ok(match (&if_true, &if_false) {
220 (Validity::NonNullable, Validity::NonNullable) => Validity::NonNullable,
221 (Validity::AllValid, Validity::AllValid) => Validity::AllValid,
222 (Validity::AllInvalid, Validity::AllInvalid) => Validity::AllInvalid,
223 _ => {
224 let true_mask = if_true.execute_mask(mask.len(), ctx)?;
225 let false_mask = if_false.execute_mask(mask.len(), ctx)?;
226 let combined = true_mask
227 .bitand(mask)
228 .bitor(&false_mask.bitand(&mask.not()));
229 Validity::from_mask(combined, if_true.nullability() | if_false.nullability())
230 }
231 })
232}
233
234#[cfg(test)]
235mod tests {
236 #![allow(
237 clippy::cast_possible_truncation,
238 reason = "test fixtures use small indices that fit the target widths"
239 )]
240
241 use std::sync::LazyLock;
242
243 use vortex_buffer::Buffer;
244 use vortex_buffer::buffer;
245 use vortex_error::VortexResult;
246 use vortex_mask::Mask;
247 use vortex_session::VortexSession;
248
249 use crate::ArrayRef;
250 use crate::IntoArray;
251 use crate::VortexSessionExecute;
252 use crate::arrays::BoolArray;
253 use crate::arrays::Chunked;
254 use crate::arrays::ChunkedArray;
255 use crate::arrays::ListView;
256 use crate::arrays::ListViewArray;
257 use crate::arrays::chunked::ChunkedArrayExt;
258 use crate::arrays::listview::ListViewArraySlotsExt;
259 use crate::assert_arrays_eq;
260 use crate::builtins::ArrayBuiltins;
261 use crate::dtype::DType;
262 use crate::dtype::Nullability;
263 use crate::dtype::PType;
264 use crate::validity::Validity;
265
266 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
267
268 fn list_view(
269 elements: ArrayRef,
270 offsets: ArrayRef,
271 sizes: ArrayRef,
272 validity: Validity,
273 ) -> ArrayRef {
274 let mut ctx = SESSION.create_execution_ctx();
275 ListViewArray::try_new(elements, offsets, sizes, validity, &mut ctx)
276 .unwrap()
277 .into_array()
278 }
279
280 #[test]
282 fn zip_selects_lists() -> VortexResult<()> {
283 let mut ctx = SESSION.create_execution_ctx();
284 let if_true = list_view(
286 buffer![1i32, 2, 3, 4, 5, 6].into_array(),
287 buffer![0u32, 2, 3].into_array(),
288 buffer![2u32, 1, 3].into_array(),
289 Validity::NonNullable,
290 );
291 let if_false = list_view(
293 buffer![10i32, 20, 21, 30].into_array(),
294 buffer![0u32, 1, 3].into_array(),
295 buffer![1u32, 2, 1].into_array(),
296 Validity::NonNullable,
297 );
298 let mask = Mask::from_iter([true, false, true]);
299
300 let result = mask
301 .into_array()
302 .zip(if_true, if_false)?
303 .execute::<ArrayRef>(&mut ctx)?;
304
305 assert!(result.is::<ListView>());
307
308 let expected = list_view(
310 buffer![1i32, 2, 20, 21, 4, 5, 6].into_array(),
311 buffer![0u32, 2, 4].into_array(),
312 buffer![2u32, 2, 3].into_array(),
313 Validity::NonNullable,
314 );
315 assert_arrays_eq!(result, expected, &mut ctx);
316 Ok(())
317 }
318
319 #[test]
321 fn zip_selects_validity() -> VortexResult<()> {
322 let mut ctx = SESSION.create_execution_ctx();
323 let if_true = list_view(
325 buffer![1i32, 2].into_array(),
326 buffer![0u32, 1, 1].into_array(),
327 buffer![1u32, 0, 1].into_array(),
328 Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
329 );
330 let if_false = list_view(
332 buffer![10i32, 20].into_array(),
333 buffer![0u32, 1, 2].into_array(),
334 buffer![1u32, 1, 0].into_array(),
335 Validity::Array(BoolArray::from_iter([true, true, false]).into_array()),
336 );
337 let mask = Mask::from_iter([false, true, true]);
339
340 let result = mask.into_array().zip(if_true, if_false)?;
341
342 let expected = list_view(
344 buffer![10i32, 2].into_array(),
345 buffer![0u32, 1, 1].into_array(),
346 buffer![1u32, 0, 1].into_array(),
347 Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
348 );
349 assert_arrays_eq!(result, expected, &mut ctx);
350 Ok(())
351 }
352
353 #[test]
356 fn zip_out_of_order_offsets_and_widening() -> VortexResult<()> {
357 let mut ctx = SESSION.create_execution_ctx();
358 let if_true = list_view(
360 buffer![7i32, 8, 9, 5, 6].into_array(),
361 buffer![3u32, 0, 1].into_array(),
362 buffer![2u32, 1, 2].into_array(),
363 Validity::NonNullable,
364 );
365 let if_false = list_view(
367 buffer![100i32, 200, 201].into_array(),
368 buffer![0u32, 1, 1].into_array(),
369 buffer![1u32, 0, 2].into_array(),
370 Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
371 );
372 let mask = Mask::from_iter([true, true, false]);
373
374 let result = mask
375 .into_array()
376 .zip(if_true, if_false)?
377 .execute::<ArrayRef>(&mut ctx)?;
378 assert!(result.is::<ListView>());
379
380 let expected = list_view(
382 buffer![5i32, 6, 7, 200, 201].into_array(),
383 buffer![0u32, 2, 3].into_array(),
384 buffer![2u32, 1, 2].into_array(),
385 Validity::AllValid,
386 );
387 assert_arrays_eq!(result, expected, &mut ctx);
388 Ok(())
389 }
390
391 #[test]
394 fn zip_spans_multiple_mask_chunks() -> VortexResult<()> {
395 let mut ctx = SESSION.create_execution_ctx();
396 let len = 130usize;
398 let true_elements: Vec<i32> = (0..len as i32).collect();
399 let false_elements: Vec<i32> = (0..len as i32).map(|i| 1000 + i).collect();
400 let offsets: Vec<u64> = (0..len as u64).collect();
401 let sizes: Vec<u64> = vec![1; len];
402
403 let if_true = list_view(
404 true_elements
405 .iter()
406 .copied()
407 .collect::<Buffer<i32>>()
408 .into_array(),
409 offsets
410 .iter()
411 .copied()
412 .collect::<Buffer<u64>>()
413 .into_array(),
414 sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
415 Validity::NonNullable,
416 );
417 let if_false = list_view(
418 false_elements
419 .iter()
420 .copied()
421 .collect::<Buffer<i32>>()
422 .into_array(),
423 offsets
424 .iter()
425 .copied()
426 .collect::<Buffer<u64>>()
427 .into_array(),
428 sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
429 Validity::NonNullable,
430 );
431
432 let mask_bits: Vec<bool> = (0..len).map(|i| i.is_multiple_of(3) || i == 64).collect();
434 let mask = Mask::from_iter(mask_bits.iter().copied());
435
436 let result = mask
437 .into_array()
438 .zip(if_true, if_false)?
439 .execute::<ArrayRef>(&mut ctx)?;
440 assert!(result.is::<ListView>());
441
442 let expected_elements: Vec<i32> = (0..len)
444 .map(|i| {
445 if mask_bits[i] {
446 i as i32
447 } else {
448 1000 + i as i32
449 }
450 })
451 .collect();
452 let expected = list_view(
453 expected_elements
454 .iter()
455 .copied()
456 .collect::<Buffer<i32>>()
457 .into_array(),
458 offsets
459 .iter()
460 .copied()
461 .collect::<Buffer<u64>>()
462 .into_array(),
463 sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
464 Validity::NonNullable,
465 );
466 assert_arrays_eq!(result, expected, &mut ctx);
467 Ok(())
468 }
469
470 #[test]
474 fn zip_handles_offset_mask() -> VortexResult<()> {
475 let mut ctx = SESSION.create_execution_ctx();
476 let len = 200usize;
480 let true_elements: Vec<i32> = (0..len as i32).collect();
481 let false_elements: Vec<i32> = (0..len as i32).map(|i| 1000 + i).collect();
482 let offsets: Vec<u64> = (0..len as u64).collect();
483 let sizes: Vec<u64> = vec![1; len];
484
485 let single_element_view = |elements: &[i32]| {
486 list_view(
487 elements
488 .iter()
489 .copied()
490 .collect::<Buffer<i32>>()
491 .into_array(),
492 offsets
493 .iter()
494 .copied()
495 .collect::<Buffer<u64>>()
496 .into_array(),
497 sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
498 Validity::NonNullable,
499 )
500 };
501 let if_true = single_element_view(&true_elements);
502 let if_false = single_element_view(&false_elements);
503
504 let offset = 3usize;
508 let mask_bits: Vec<bool> = (0..offset + len)
509 .map(|i| i.is_multiple_of(3) || i == offset + 64)
510 .collect();
511 let mask = BoolArray::from_iter(mask_bits.iter().copied())
512 .into_array()
513 .slice(offset..offset + len)?;
514
515 let result = mask.zip(if_true, if_false)?.execute::<ArrayRef>(&mut ctx)?;
516 assert!(result.is::<ListView>());
517
518 let expected_elements: Vec<i32> = (0..len)
520 .map(|i| {
521 if mask_bits[offset + i] {
522 i as i32
523 } else {
524 1000 + i as i32
525 }
526 })
527 .collect();
528 let expected = single_element_view(&expected_elements);
529 assert_arrays_eq!(result, expected, &mut ctx);
530 Ok(())
531 }
532
533 #[test]
536 fn zip_flattens_chunked_elements() -> VortexResult<()> {
537 let mut ctx = SESSION.create_execution_ctx();
538 let chunked_elements = ChunkedArray::try_new(
540 vec![buffer![1i32, 2].into_array(), buffer![3i32].into_array()],
541 DType::Primitive(PType::I32, Nullability::NonNullable),
542 )?
543 .into_array();
544 let if_true = list_view(
545 chunked_elements,
546 buffer![0u32, 2].into_array(),
547 buffer![2u32, 1].into_array(),
548 Validity::NonNullable,
549 );
550 let if_false = list_view(
552 buffer![10i32, 20].into_array(),
553 buffer![0u32, 1].into_array(),
554 buffer![1u32, 1].into_array(),
555 Validity::NonNullable,
556 );
557 let mask = Mask::from_iter([true, false]);
558
559 let result = mask
560 .into_array()
561 .zip(if_true, if_false)?
562 .execute::<ArrayRef>(&mut ctx)?;
563
564 let result_lv = result
566 .as_opt::<ListView>()
567 .expect("zip keeps the list-view encoding");
568 let chunked = result_lv
569 .elements()
570 .as_opt::<Chunked>()
571 .expect("zip concatenates elements into a chunked array");
572 assert!(
573 chunked.iter_chunks().all(|chunk| !chunk.is::<Chunked>()),
574 "chunked elements must be flattened, not nested",
575 );
576
577 let expected = list_view(
579 buffer![1i32, 2, 20].into_array(),
580 buffer![0u32, 2].into_array(),
581 buffer![2u32, 1].into_array(),
582 Validity::NonNullable,
583 );
584 assert_arrays_eq!(result, expected, &mut ctx);
585 Ok(())
586 }
587}