1use itertools::Itertools as _;
5use num_traits::AsPrimitive;
6use vortex_buffer::Buffer;
7use vortex_buffer::BufferMut;
8use vortex_error::VortexExpect;
9use vortex_error::VortexResult;
10use vortex_error::vortex_ensure_eq;
11use vortex_error::vortex_err;
12use vortex_mask::Mask;
13
14use crate::ArrayRef;
15use crate::Columnar;
16use crate::IntoArray;
17use crate::array::ArrayView;
18use crate::arrays::ConstantArray;
19use crate::arrays::List;
20use crate::arrays::ListArray;
21use crate::arrays::PiecewiseSequence;
22use crate::arrays::PiecewiseSequenceArray;
23use crate::arrays::Primitive;
24use crate::arrays::PrimitiveArray;
25use crate::arrays::dict::TakeExecute;
26use crate::arrays::list::ListArrayExt;
27use crate::arrays::list::ListArraySlotsExt;
28use crate::arrays::piecewise_sequence::constant_unsigned_usize;
29use crate::arrays::piecewise_sequence::maybe_contiguous_slices;
30use crate::arrays::primitive::PrimitiveArrayExt;
31use crate::dtype::IntegerPType;
32use crate::dtype::PType;
33use crate::dtype::UnsignedPType;
34use crate::executor::ExecutionCtx;
35use crate::match_each_unsigned_integer_ptype;
36use crate::match_smallest_offset_type;
37use crate::validity::Validity;
38
39impl TakeExecute for List {
43 #[expect(clippy::cognitive_complexity)]
49 fn take(
50 array: ArrayView<'_, List>,
51 indices: &ArrayRef,
52 ctx: &mut ExecutionCtx,
53 ) -> VortexResult<Option<ArrayRef>> {
54 if let Some(piecewise_indices) = indices.as_opt::<PiecewiseSequence>()
55 && let Some(taken) = take_slices(array, piecewise_indices, indices, ctx)?
56 {
57 return Ok(Some(taken));
58 }
59
60 let new_validity = array.validity()?.take(indices)?;
61 let indices = indices.clone().execute::<PrimitiveArray>(ctx)?;
62 let indices = indices.reinterpret_cast(indices.ptype().to_unsigned());
63 let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
64 let offsets = offsets.reinterpret_cast(offsets.ptype().to_unsigned());
65 let validity_mask = new_validity.execute_mask(indices.len(), ctx)?;
66 let total_approx = array.elements().len().saturating_mul(indices.len());
68
69 match_each_unsigned_integer_ptype!(offsets.ptype(), |O| {
70 match_each_unsigned_integer_ptype!(indices.ptype(), |I| {
71 match_smallest_offset_type!(total_approx, |OutOffset| {
72 take_with_piecewise_elements::<I, O, OutOffset>(
73 array,
74 offsets.as_view(),
75 indices.as_view(),
76 new_validity,
77 &validity_mask,
78 )
79 .map(Some)
80 })
81 })
82 })
83 }
84}
85
86fn take_with_piecewise_elements<I: IntegerPType, O: IntegerPType, OutOffset: IntegerPType>(
87 array: ArrayView<'_, List>,
88 offsets_array: ArrayView<'_, Primitive>,
89 indices_array: ArrayView<'_, Primitive>,
90 new_validity: Validity,
91 validity_mask: &Mask,
92) -> VortexResult<ArrayRef> {
93 let offsets: &[O] = offsets_array.as_slice();
94 let indices: &[I] = indices_array.as_slice();
95
96 let offsets_capacity = indices
97 .len()
98 .checked_add(1)
99 .ok_or_else(|| vortex_err!("List take offsets length overflow"))?;
100 let mut new_offsets = BufferMut::<OutOffset>::with_capacity(offsets_capacity);
101 let mut element_starts = BufferMut::<u64>::with_capacity(indices.len());
102 let mut element_lengths = BufferMut::<u64>::with_capacity(indices.len());
103
104 let mut current_offset = 0usize;
105 new_offsets.push(OutOffset::zero());
106
107 for (&data_idx, is_valid) in indices.iter().zip_eq(validity_mask.iter()) {
108 if !is_valid {
109 new_offsets.push(new_offset_value::<OutOffset>(current_offset));
110 element_starts.push(0);
111 element_lengths.push(0);
112 continue;
113 }
114
115 let data_idx: usize = data_idx.as_();
116
117 let start = offsets[data_idx];
118 let stop = offsets[data_idx + 1];
119 let start: usize = start.as_();
120 let stop: usize = stop.as_();
121 let length = stop - start;
122
123 current_offset = current_offset
124 .checked_add(length)
125 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
126 new_offsets.push(new_offset_value::<OutOffset>(current_offset));
127 element_starts.push(start as u64);
128 element_lengths.push(length as u64);
129 }
130
131 let new_offsets = PrimitiveArray::new(new_offsets.freeze(), Validity::NonNullable).into_array();
132 let multipliers = ConstantArray::new(1u64, element_starts.len()).into_array();
133
134 let element_indices = unsafe {
138 PiecewiseSequenceArray::new_unchecked(
139 element_starts.into_array(),
140 element_lengths.into_array(),
141 multipliers,
142 current_offset,
143 )
144 };
145 let new_elements = array.elements().take(element_indices.into_array())?;
146
147 Ok(unsafe { ListArray::new_unchecked(new_elements, new_offsets, new_validity) }.into_array())
150}
151
152fn take_slices(
153 array: ArrayView<'_, List>,
154 indices: ArrayView<'_, PiecewiseSequence>,
155 indices_ref: &ArrayRef,
156 ctx: &mut ExecutionCtx,
157) -> VortexResult<Option<ArrayRef>> {
158 let Some((starts, lengths)) = maybe_contiguous_slices(indices, ctx)? else {
159 return Ok(None);
160 };
161 let data_validity = array
162 .list_validity()
163 .execute_mask(array.as_ref().len(), ctx)?;
164 let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
165 let offsets = offsets.reinterpret_cast(offsets.ptype().to_unsigned());
166 let output_len = indices_ref.len();
167
168 let starts = pieces_as_u64(&starts);
171 let taken = match lengths {
172 Columnar::Constant(lengths) => {
173 let length = constant_unsigned_usize(&lengths);
174 match_each_unsigned_integer_ptype!(offsets.ptype(), |O| {
175 take_slices_constant_length::<u64, O>(
176 array,
177 &starts,
178 length,
179 offsets.as_slice::<O>(),
180 indices_ref,
181 output_len,
182 &data_validity,
183 )
184 })?
185 }
186 Columnar::Canonical(lengths) => {
187 let lengths = pieces_as_u64(&lengths.into_primitive());
188 match_each_unsigned_integer_ptype!(offsets.ptype(), |O| {
189 take_slices_typed::<u64, u64, O>(
190 array,
191 &starts,
192 &lengths,
193 offsets.as_slice::<O>(),
194 indices_ref,
195 output_len,
196 &data_validity,
197 )
198 })?
199 }
200 };
201 Ok(Some(taken))
202}
203
204fn pieces_as_u64(pieces: &PrimitiveArray) -> Buffer<u64> {
206 if pieces.ptype() == PType::U64 {
207 return pieces.to_buffer::<u64>();
208 }
209
210 match_each_unsigned_integer_ptype!(pieces.ptype(), |P| {
211 pieces
212 .as_slice::<P>()
213 .iter()
214 .map(|&piece| piece.as_())
215 .collect()
216 })
217}
218
219fn take_slices_constant_length<S, Offset>(
220 array: ArrayView<'_, List>,
221 starts: &[S],
222 length: usize,
223 offsets: &[Offset],
224 indices_ref: &ArrayRef,
225 output_len: usize,
226 data_validity: &Mask,
227) -> VortexResult<ArrayRef>
228where
229 S: UnsignedPType,
230 Offset: UnsignedPType,
231{
232 let computed_len = starts
233 .len()
234 .checked_mul(length)
235 .ok_or_else(|| vortex_err!("PiecewiseSequenceArray output length overflows usize"))?;
236 vortex_ensure_eq!(
237 computed_len,
238 output_len,
239 "PiecewiseSequenceArray expanded length does not match declared length",
240 );
241 let all_valid = data_validity.all_true();
242 let total_elements = if all_valid {
243 piecewise_list_elements_len_constant(offsets, starts, length)?
244 } else {
245 piecewise_list_elements_len_constant_validity(offsets, starts, length, data_validity)?
246 };
247 let validity = array.validity()?.take(indices_ref)?;
248
249 match_smallest_offset_type!(total_elements, |OutOffset| {
250 let gathered = if all_valid {
251 gather_piecewise_list_constant_length::<S, Offset, OutOffset>(
252 array.elements(),
253 offsets,
254 starts,
255 length,
256 output_len,
257 total_elements,
258 )?
259 } else {
260 gather_piecewise_list_constant_length_validity::<S, Offset, OutOffset>(
261 array.elements(),
262 offsets,
263 starts,
264 length,
265 output_len,
266 total_elements,
267 data_validity,
268 )?
269 };
270
271 Ok(
275 unsafe { ListArray::new_unchecked(gathered.elements, gathered.offsets, validity) }
276 .into_array(),
277 )
278 })
279}
280
281fn take_slices_typed<S, L, Offset>(
282 array: ArrayView<'_, List>,
283 starts: &[S],
284 lengths: &[L],
285 offsets: &[Offset],
286 indices_ref: &ArrayRef,
287 output_len: usize,
288 data_validity: &Mask,
289) -> VortexResult<ArrayRef>
290where
291 S: UnsignedPType,
292 L: UnsignedPType,
293 Offset: UnsignedPType,
294{
295 let mut computed_len = 0usize;
296 for &length in lengths {
297 let length: usize = length.as_();
298 computed_len = computed_len
299 .checked_add(length)
300 .ok_or_else(|| vortex_err!("PiecewiseSequenceArray output length overflows usize"))?;
301 }
302 vortex_ensure_eq!(
303 computed_len,
304 output_len,
305 "PiecewiseSequenceArray expanded length does not match declared length",
306 );
307 let all_valid = data_validity.all_true();
308 let total_elements = if all_valid {
309 piecewise_list_elements_len(offsets, starts, lengths)?
310 } else {
311 piecewise_list_elements_len_validity(offsets, starts, lengths, data_validity)?
312 };
313
314 match_smallest_offset_type!(total_elements, |OutOffset| {
315 let gathered = if all_valid {
316 gather_piecewise_list::<S, L, Offset, OutOffset>(
317 array.elements(),
318 offsets,
319 starts,
320 lengths,
321 output_len,
322 total_elements,
323 )?
324 } else {
325 gather_piecewise_list_validity::<S, L, Offset, OutOffset>(
326 array.elements(),
327 offsets,
328 starts,
329 lengths,
330 output_len,
331 total_elements,
332 data_validity,
333 )?
334 };
335 let validity = array.validity()?.take(indices_ref)?;
336
337 Ok(
341 unsafe { ListArray::new_unchecked(gathered.elements, gathered.offsets, validity) }
342 .into_array(),
343 )
344 })
345}
346
347struct GatheredList {
348 elements: ArrayRef,
349 offsets: ArrayRef,
350}
351
352struct ValidPieceGather<OutOffset> {
353 new_offsets: BufferMut<OutOffset>,
354 element_starts: BufferMut<u64>,
355 element_lengths: BufferMut<u64>,
356 output_elements: usize,
357}
358
359fn piecewise_list_elements_len_constant<S, Offset>(
360 offsets: &[Offset],
361 starts: &[S],
362 length: usize,
363) -> VortexResult<usize>
364where
365 S: UnsignedPType,
366 Offset: UnsignedPType,
367{
368 if length == 0 {
369 return Ok(0);
370 }
371
372 let mut total = 0usize;
373 for start in starts {
374 let start: usize = start.as_();
375 let offset_range = &offsets[start..][..=length];
376 let element_start: usize = offset_range[0].as_();
377 let element_end: usize = offset_range[length].as_();
378 total = total
379 .checked_add(element_end - element_start)
380 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
381 }
382 Ok(total)
383}
384
385fn piecewise_list_elements_len_constant_validity<S, Offset>(
386 offsets: &[Offset],
387 starts: &[S],
388 length: usize,
389 data_validity: &Mask,
390) -> VortexResult<usize>
391where
392 S: UnsignedPType,
393 Offset: UnsignedPType,
394{
395 if length == 0 {
396 return Ok(0);
397 }
398
399 let mut total = 0usize;
400 for start in starts {
401 let start: usize = start.as_();
402 let additional = valid_piece_elements_len(offsets, data_validity, start, length)?;
403 total = total
404 .checked_add(additional)
405 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
406 }
407 Ok(total)
408}
409
410fn piecewise_list_elements_len<S, L, Offset>(
411 offsets: &[Offset],
412 starts: &[S],
413 lengths: &[L],
414) -> VortexResult<usize>
415where
416 S: UnsignedPType,
417 L: UnsignedPType,
418 Offset: UnsignedPType,
419{
420 let mut total = 0usize;
421 for (&start, &length) in starts.iter().zip_eq(lengths) {
422 let start: usize = start.as_();
423 let length: usize = length.as_();
424 let offset_range = &offsets[start..][..=length];
425 let element_start: usize = offset_range[0].as_();
426 let element_end: usize = offset_range[length].as_();
427 total = total
428 .checked_add(element_end - element_start)
429 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
430 }
431 Ok(total)
432}
433
434fn piecewise_list_elements_len_validity<S, L, Offset>(
435 offsets: &[Offset],
436 starts: &[S],
437 lengths: &[L],
438 data_validity: &Mask,
439) -> VortexResult<usize>
440where
441 S: UnsignedPType,
442 L: UnsignedPType,
443 Offset: UnsignedPType,
444{
445 let mut total = 0usize;
446 for (&start, &length) in starts.iter().zip_eq(lengths) {
447 let start: usize = start.as_();
448 let length: usize = length.as_();
449 let additional = valid_piece_elements_len(offsets, data_validity, start, length)?;
450 total = total
451 .checked_add(additional)
452 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
453 }
454 Ok(total)
455}
456
457fn valid_piece_elements_len<Offset>(
458 offsets: &[Offset],
459 data_validity: &Mask,
460 start: usize,
461 length: usize,
462) -> VortexResult<usize>
463where
464 Offset: UnsignedPType,
465{
466 let offset_range = &offsets[start..][..=length];
467 let mut total = 0usize;
468 for (data_idx, window) in (start..).zip(offset_range.windows(2)) {
469 if !data_validity.value(data_idx) {
470 continue;
471 }
472 let element_start: usize = window[0].as_();
473 let element_end: usize = window[1].as_();
474 total = total
475 .checked_add(element_end - element_start)
476 .ok_or_else(|| vortex_err!("List take output elements length overflow"))?;
477 }
478 Ok(total)
479}
480
481fn gather_piecewise_list_constant_length<S, Offset, OutOffset>(
482 elements: &ArrayRef,
483 offsets: &[Offset],
484 starts: &[S],
485 length: usize,
486 output_len: usize,
487 total_elements: usize,
488) -> VortexResult<GatheredList>
489where
490 S: UnsignedPType,
491 Offset: UnsignedPType,
492 OutOffset: IntegerPType,
493{
494 let offsets_capacity = output_len
495 .checked_add(1)
496 .ok_or_else(|| vortex_err!("List take offsets length overflow"))?;
497 let mut new_offsets = BufferMut::<OutOffset>::with_capacity(offsets_capacity);
498 let mut element_starts = BufferMut::<u64>::with_capacity(starts.len());
499 let mut element_lengths = BufferMut::<u64>::with_capacity(starts.len());
500 let mut output_elements = 0usize;
501
502 new_offsets.push(OutOffset::zero());
503 for start in starts {
504 let start: usize = start.as_();
505 if length == 0 {
506 continue;
507 }
508
509 let offset_range = &offsets[start..][..=length];
510 let element_start: usize = offset_range[0].as_();
511 let element_end: usize = offset_range[length].as_();
512 for &offset in &offset_range[1..] {
513 let offset: usize = offset.as_();
514 let relative = offset - element_start;
515 let output_offset = output_elements + relative;
516 new_offsets.push(new_offset_value::<OutOffset>(output_offset));
517 }
518
519 let element_length = element_end - element_start;
520 element_starts.push(element_start as u64);
521 element_lengths.push(element_length as u64);
522 output_elements += element_length;
523 }
524 debug_assert_eq!(output_elements, total_elements);
525
526 let offsets = PrimitiveArray::new(new_offsets.freeze(), Validity::NonNullable).into_array();
527 let multipliers = ConstantArray::new(1u64, element_starts.len()).into_array();
528 let element_indices = unsafe {
531 PiecewiseSequenceArray::new_unchecked(
532 element_starts.into_array(),
533 element_lengths.into_array(),
534 multipliers,
535 total_elements,
536 )
537 };
538 let elements = elements.take(element_indices.into_array())?;
539
540 Ok(GatheredList { elements, offsets })
541}
542
543fn gather_piecewise_list_constant_length_validity<S, Offset, OutOffset>(
544 elements: &ArrayRef,
545 offsets: &[Offset],
546 starts: &[S],
547 length: usize,
548 output_len: usize,
549 total_elements: usize,
550 data_validity: &Mask,
551) -> VortexResult<GatheredList>
552where
553 S: UnsignedPType,
554 Offset: UnsignedPType,
555 OutOffset: IntegerPType,
556{
557 let offsets_capacity = output_len
558 .checked_add(1)
559 .ok_or_else(|| vortex_err!("List take offsets length overflow"))?;
560 let mut gather = ValidPieceGather {
561 new_offsets: BufferMut::<OutOffset>::with_capacity(offsets_capacity),
562 element_starts: BufferMut::<u64>::with_capacity(output_len),
563 element_lengths: BufferMut::<u64>::with_capacity(output_len),
564 output_elements: 0,
565 };
566
567 gather.new_offsets.push(OutOffset::zero());
568 for start in starts {
569 let start: usize = start.as_();
570 if length == 0 {
571 continue;
572 }
573
574 gather_valid_piece(offsets, data_validity, start, length, &mut gather);
575 }
576 debug_assert_eq!(gather.output_elements, total_elements);
577
578 let offsets =
579 PrimitiveArray::new(gather.new_offsets.freeze(), Validity::NonNullable).into_array();
580 let multipliers = ConstantArray::new(1u64, gather.element_starts.len()).into_array();
581 let element_indices = unsafe {
584 PiecewiseSequenceArray::new_unchecked(
585 gather.element_starts.into_array(),
586 gather.element_lengths.into_array(),
587 multipliers,
588 total_elements,
589 )
590 };
591 let elements = elements.take(element_indices.into_array())?;
592
593 Ok(GatheredList { elements, offsets })
594}
595
596fn gather_piecewise_list<S, L, Offset, OutOffset>(
597 elements: &ArrayRef,
598 offsets: &[Offset],
599 starts: &[S],
600 lengths: &[L],
601 output_len: usize,
602 total_elements: usize,
603) -> VortexResult<GatheredList>
604where
605 S: UnsignedPType,
606 L: UnsignedPType,
607 Offset: UnsignedPType,
608 OutOffset: IntegerPType,
609{
610 let offsets_capacity = output_len
611 .checked_add(1)
612 .ok_or_else(|| vortex_err!("List take offsets length overflow"))?;
613 let mut new_offsets = BufferMut::<OutOffset>::with_capacity(offsets_capacity);
614 let mut element_starts = BufferMut::<u64>::with_capacity(starts.len());
615 let mut element_lengths = BufferMut::<u64>::with_capacity(lengths.len());
616 let mut output_elements = 0usize;
617
618 new_offsets.push(OutOffset::zero());
619 for (&start, &length) in starts.iter().zip_eq(lengths) {
620 let start: usize = start.as_();
621 let length: usize = length.as_();
622 if length == 0 {
623 continue;
624 }
625
626 let offset_range = &offsets[start..][..=length];
627 let element_start: usize = offset_range[0].as_();
628 let element_end: usize = offset_range[length].as_();
629 for &offset in &offset_range[1..] {
630 let offset: usize = offset.as_();
631 let relative = offset - element_start;
632 let output_offset = output_elements + relative;
633 new_offsets.push(new_offset_value::<OutOffset>(output_offset));
634 }
635
636 let element_length = element_end - element_start;
637 element_starts.push(element_start as u64);
638 element_lengths.push(element_length as u64);
639 output_elements += element_length;
640 }
641 debug_assert_eq!(output_elements, total_elements);
642
643 let offsets = PrimitiveArray::new(new_offsets.freeze(), Validity::NonNullable).into_array();
644 let multipliers = ConstantArray::new(1u64, element_starts.len()).into_array();
645 let element_indices = unsafe {
648 PiecewiseSequenceArray::new_unchecked(
649 element_starts.into_array(),
650 element_lengths.into_array(),
651 multipliers,
652 total_elements,
653 )
654 };
655 let elements = elements.take(element_indices.into_array())?;
656
657 Ok(GatheredList { elements, offsets })
658}
659
660fn gather_piecewise_list_validity<S, L, Offset, OutOffset>(
661 elements: &ArrayRef,
662 offsets: &[Offset],
663 starts: &[S],
664 lengths: &[L],
665 output_len: usize,
666 total_elements: usize,
667 data_validity: &Mask,
668) -> VortexResult<GatheredList>
669where
670 S: UnsignedPType,
671 L: UnsignedPType,
672 Offset: UnsignedPType,
673 OutOffset: IntegerPType,
674{
675 let offsets_capacity = output_len
676 .checked_add(1)
677 .ok_or_else(|| vortex_err!("List take offsets length overflow"))?;
678 let mut gather = ValidPieceGather {
679 new_offsets: BufferMut::<OutOffset>::with_capacity(offsets_capacity),
680 element_starts: BufferMut::<u64>::with_capacity(output_len),
681 element_lengths: BufferMut::<u64>::with_capacity(output_len),
682 output_elements: 0,
683 };
684
685 gather.new_offsets.push(OutOffset::zero());
686 for (&start, &length) in starts.iter().zip_eq(lengths) {
687 let start: usize = start.as_();
688 let length: usize = length.as_();
689 if length == 0 {
690 continue;
691 }
692
693 gather_valid_piece(offsets, data_validity, start, length, &mut gather);
694 }
695 debug_assert_eq!(gather.output_elements, total_elements);
696
697 let offsets =
698 PrimitiveArray::new(gather.new_offsets.freeze(), Validity::NonNullable).into_array();
699 let multipliers = ConstantArray::new(1u64, gather.element_starts.len()).into_array();
700 let element_indices = unsafe {
703 PiecewiseSequenceArray::new_unchecked(
704 gather.element_starts.into_array(),
705 gather.element_lengths.into_array(),
706 multipliers,
707 total_elements,
708 )
709 };
710 let elements = elements.take(element_indices.into_array())?;
711
712 Ok(GatheredList { elements, offsets })
713}
714
715fn gather_valid_piece<Offset, OutOffset>(
716 offsets: &[Offset],
717 data_validity: &Mask,
718 start: usize,
719 length: usize,
720 gather: &mut ValidPieceGather<OutOffset>,
721) where
722 Offset: UnsignedPType,
723 OutOffset: IntegerPType,
724{
725 let offset_range = &offsets[start..][..=length];
726 for (data_idx, window) in (start..).zip(offset_range.windows(2)) {
727 if !data_validity.value(data_idx) {
728 gather
729 .new_offsets
730 .push(new_offset_value::<OutOffset>(gather.output_elements));
731 continue;
732 }
733
734 let element_start: usize = window[0].as_();
735 let element_end: usize = window[1].as_();
736 let element_length = element_end - element_start;
737 if element_length != 0 {
738 gather.element_starts.push(element_start as u64);
739 gather.element_lengths.push(element_length as u64);
740 gather.output_elements += element_length;
741 }
742 gather
743 .new_offsets
744 .push(new_offset_value::<OutOffset>(gather.output_elements));
745 }
746}
747
748fn new_offset_value<T: IntegerPType>(value: usize) -> T {
749 T::from_usize(value).vortex_expect("output offset fits selected offset type")
750}
751
752#[cfg(test)]
753mod test {
754 use std::sync::Arc;
755 use std::sync::LazyLock;
756
757 use rstest::rstest;
758 use vortex_buffer::Buffer;
759 use vortex_buffer::buffer;
760 use vortex_error::VortexResult;
761 use vortex_session::VortexSession;
762
763 use crate::ArrayRef;
764 use crate::IntoArray as _;
765 use crate::VortexSessionExecute;
766 use crate::arrays::BoolArray;
767 use crate::arrays::ConstantArray;
768 use crate::arrays::ListArray;
769 use crate::arrays::ListViewArray;
770 use crate::arrays::PiecewiseSequenceArray;
771 use crate::arrays::PrimitiveArray;
772 use crate::arrays::listview::ListViewArrayExt;
773 use crate::assert_arrays_eq;
774 use crate::compute::conformance::take::test_take_conformance;
775 use crate::dtype::DType;
776 use crate::dtype::Nullability;
777 use crate::dtype::PType::I32;
778 use crate::scalar::Scalar;
779 use crate::validity::Validity;
780
781 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
782
783 #[test]
784 fn nullable_take() {
785 let mut ctx = SESSION.create_execution_ctx();
786 let list = ListArray::try_new(
787 buffer![0i32, 5, 3, 4].into_array(),
788 buffer![0, 2, 3, 4, 4].into_array(),
789 Validity::Array(BoolArray::from_iter(vec![true, true, false, true]).into_array()),
790 &mut ctx,
791 )
792 .unwrap()
793 .into_array();
794
795 let idx =
796 PrimitiveArray::from_option_iter(vec![Some(0), None, Some(1), Some(3)]).into_array();
797
798 let result = list.take(idx).unwrap();
799
800 assert_eq!(
801 result.dtype(),
802 &DType::List(
803 Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
804 Nullability::Nullable
805 )
806 );
807
808 let result = result.execute::<ListViewArray>(&mut ctx).unwrap();
809
810 assert_eq!(result.len(), 4);
811
812 let element_dtype: Arc<DType> = Arc::new(I32.into());
813
814 assert!(
815 result
816 .is_valid(0, &mut SESSION.create_execution_ctx())
817 .unwrap()
818 );
819 assert_eq!(
820 result
821 .execute_scalar(0, &mut SESSION.create_execution_ctx())
822 .unwrap(),
823 Scalar::list(
824 Arc::clone(&element_dtype),
825 vec![0i32.into(), 5.into()],
826 Nullability::Nullable
827 )
828 );
829
830 assert!(
831 result
832 .is_invalid(1, &mut SESSION.create_execution_ctx())
833 .unwrap()
834 );
835
836 assert!(
837 result
838 .is_valid(2, &mut SESSION.create_execution_ctx())
839 .unwrap()
840 );
841 assert_eq!(
842 result
843 .execute_scalar(2, &mut SESSION.create_execution_ctx())
844 .unwrap(),
845 Scalar::list(
846 Arc::clone(&element_dtype),
847 vec![3i32.into()],
848 Nullability::Nullable
849 )
850 );
851
852 assert!(
853 result
854 .is_valid(3, &mut SESSION.create_execution_ctx())
855 .unwrap()
856 );
857 assert_eq!(
858 result
859 .execute_scalar(3, &mut SESSION.create_execution_ctx())
860 .unwrap(),
861 Scalar::list(element_dtype, vec![], Nullability::Nullable)
862 );
863 }
864
865 #[test]
866 fn null_index_ignores_out_of_bounds_payload() {
867 let mut ctx = SESSION.create_execution_ctx();
868 let list = ListArray::try_new(
869 buffer![1i32, 2, 3, 4].into_array(),
870 buffer![0u32, 2, 4].into_array(),
871 Validity::NonNullable,
872 &mut ctx,
873 )
874 .unwrap()
875 .into_array();
876
877 let idx = PrimitiveArray::new(
878 buffer![1u32, 99, 0],
879 Validity::from_iter([true, false, true]),
880 )
881 .into_array();
882 let result = list.take(idx).unwrap();
883
884 let expected = ListArray::new(
885 buffer![3i32, 4, 1, 2].into_array(),
886 buffer![0u32, 2, 2, 4].into_array(),
887 Validity::from_iter([true, false, true]),
888 &mut ctx,
889 );
890 assert_arrays_eq!(result, expected, &mut ctx);
891 }
892
893 #[test]
894 fn null_source_row_uses_valid_empty_output_range() {
895 let mut ctx = SESSION.create_execution_ctx();
896 let list = ListArray::new(
897 buffer![1i32, 2, 7, 8].into_array(),
898 buffer![0u32, 2, 4].into_array(),
899 Validity::from_iter([true, false]),
900 &mut ctx,
901 )
902 .into_array();
903
904 let idx = buffer![0u32, 1].into_array();
905 let result = list.take(idx).unwrap();
906
907 let expected = ListArray::new(
908 buffer![1i32, 2].into_array(),
909 buffer![0u32, 2, 2].into_array(),
910 Validity::from_iter([true, false]),
911 &mut ctx,
912 );
913 assert_arrays_eq!(result, expected, &mut ctx);
914 }
915
916 #[test]
917 fn change_validity() {
918 let mut ctx = SESSION.create_execution_ctx();
919 let list = ListArray::try_new(
920 buffer![0i32, 5, 3, 4].into_array(),
921 buffer![0, 2, 3].into_array(),
922 Validity::NonNullable,
923 &mut ctx,
924 )
925 .unwrap()
926 .into_array();
927
928 let idx = PrimitiveArray::from_option_iter(vec![Some(0), Some(1), None]).into_array();
929 let result = list.take(idx).unwrap();
932 assert_eq!(
933 result.dtype(),
934 &DType::List(
935 Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
936 Nullability::Nullable
937 )
938 );
939 let expected = ListArray::new(
940 buffer![0i32, 5, 3].into_array(),
941 buffer![0u32, 2, 3, 3].into_array(),
942 Validity::from_iter([true, true, false]),
943 &mut ctx,
944 );
945 assert_arrays_eq!(result, expected, &mut SESSION.create_execution_ctx());
946 }
947
948 #[test]
949 fn non_nullable_take() {
950 let mut ctx = SESSION.create_execution_ctx();
951 let list = ListArray::try_new(
952 buffer![0i32, 5, 3, 4].into_array(),
953 buffer![0, 2, 3, 3, 4].into_array(),
954 Validity::NonNullable,
955 &mut ctx,
956 )
957 .unwrap()
958 .into_array();
959
960 let idx = buffer![1, 0, 2].into_array();
961
962 let result = list.take(idx).unwrap();
963
964 assert_eq!(
965 result.dtype(),
966 &DType::List(
967 Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
968 Nullability::NonNullable
969 )
970 );
971
972 let result = result.execute::<ListViewArray>(&mut ctx).unwrap();
973
974 assert_eq!(result.len(), 3);
975
976 let element_dtype: Arc<DType> = Arc::new(I32.into());
977
978 assert!(
979 result
980 .is_valid(0, &mut SESSION.create_execution_ctx())
981 .unwrap()
982 );
983 assert_eq!(
984 result
985 .execute_scalar(0, &mut SESSION.create_execution_ctx())
986 .unwrap(),
987 Scalar::list(
988 Arc::clone(&element_dtype),
989 vec![3i32.into()],
990 Nullability::NonNullable
991 )
992 );
993
994 assert!(
995 result
996 .is_valid(1, &mut SESSION.create_execution_ctx())
997 .unwrap()
998 );
999 assert_eq!(
1000 result
1001 .execute_scalar(1, &mut SESSION.create_execution_ctx())
1002 .unwrap(),
1003 Scalar::list(
1004 Arc::clone(&element_dtype),
1005 vec![0i32.into(), 5.into()],
1006 Nullability::NonNullable
1007 )
1008 );
1009
1010 assert!(
1011 result
1012 .is_valid(2, &mut SESSION.create_execution_ctx())
1013 .unwrap()
1014 );
1015 assert_eq!(
1016 result
1017 .execute_scalar(2, &mut SESSION.create_execution_ctx())
1018 .unwrap(),
1019 Scalar::list(element_dtype, vec![], Nullability::NonNullable)
1020 );
1021 }
1022
1023 #[rstest]
1025 #[case::u8_pieces(
1026 buffer![1u8, 0].into_array(),
1027 buffer![2u8, 1].into_array(),
1028 buffer![2i32, 3, 4, 0, 1],
1029 buffer![0u32, 3, 3, 5]
1030 )]
1031 #[case::mixed_pieces(
1032 buffer![1u16, 0].into_array(),
1033 buffer![2u32, 1].into_array(),
1034 buffer![2i32, 3, 4, 0, 1],
1035 buffer![0u32, 3, 3, 5]
1036 )]
1037 #[case::constant_length(
1038 buffer![3u16, 0].into_array(),
1039 ConstantArray::new(1u8, 2).into_array(),
1040 buffer![5i32, 6, 0, 1],
1041 buffer![0u32, 2, 4]
1042 )]
1043 fn piecewise_sequence_take_narrow_pieces(
1044 #[case] starts: ArrayRef,
1045 #[case] lengths: ArrayRef,
1046 #[case] expected_elements: Buffer<i32>,
1047 #[case] expected_offsets: Buffer<u32>,
1048 ) -> VortexResult<()> {
1049 let mut ctx = SESSION.create_execution_ctx();
1050 let list = ListArray::try_new(
1051 buffer![0i32, 1, 2, 3, 4, 5, 6].into_array(),
1052 buffer![0u32, 2, 5, 5, 7].into_array(),
1053 Validity::NonNullable,
1054 &mut ctx,
1055 )?
1056 .into_array();
1057 let output_len = expected_offsets.len() - 1;
1058 let indices = PiecewiseSequenceArray::try_new(
1059 starts,
1060 lengths,
1061 ConstantArray::new(1u64, 2).into_array(),
1062 output_len,
1063 )?;
1064 let expected = ListArray::try_new(
1065 expected_elements.into_array(),
1066 expected_offsets.into_array(),
1067 Validity::NonNullable,
1068 &mut ctx,
1069 )?;
1070
1071 assert_arrays_eq!(list.take(indices.into_array())?, expected, &mut ctx);
1072 Ok(())
1073 }
1074
1075 #[test]
1076 fn piecewise_sequence_take() {
1077 let mut ctx = SESSION.create_execution_ctx();
1078 let list = ListArray::try_new(
1079 buffer![0i32, 1, 2, 3, 4, 5, 6].into_array(),
1080 buffer![0u32, 2, 5, 5, 7].into_array(),
1081 Validity::NonNullable,
1082 &mut ctx,
1083 )
1084 .unwrap()
1085 .into_array();
1086 let idx = PiecewiseSequenceArray::try_new(
1087 buffer![1u64, 0].into_array(),
1088 buffer![2u64, 1].into_array(),
1089 ConstantArray::new(1u64, 2).into_array(),
1090 3,
1091 )
1092 .unwrap()
1093 .into_array();
1094
1095 let result = list
1096 .take(idx)
1097 .unwrap()
1098 .execute::<ListViewArray>(&mut ctx)
1099 .unwrap();
1100
1101 let element_dtype: Arc<DType> = Arc::new(I32.into());
1102 assert_eq!(
1103 result.execute_scalar(0, &mut ctx).unwrap(),
1104 Scalar::list(
1105 Arc::clone(&element_dtype),
1106 vec![2i32.into(), 3.into(), 4.into()],
1107 Nullability::NonNullable
1108 )
1109 );
1110 assert_eq!(
1111 result.execute_scalar(1, &mut ctx).unwrap(),
1112 Scalar::list(Arc::clone(&element_dtype), vec![], Nullability::NonNullable)
1113 );
1114 assert_eq!(
1115 result.execute_scalar(2, &mut ctx).unwrap(),
1116 Scalar::list(
1117 element_dtype,
1118 vec![0i32.into(), 1.into()],
1119 Nullability::NonNullable
1120 )
1121 );
1122 }
1123
1124 #[test]
1125 fn piecewise_sequence_take_nullable_list_constant_lengths() -> VortexResult<()> {
1126 let mut ctx = SESSION.create_execution_ctx();
1127 let list = ListArray::try_new(
1128 buffer![0i32, 1, 99, 100, 2, 3, 4, 5].into_array(),
1129 buffer![0u32, 2, 4, 7, 8].into_array(),
1130 Validity::Array(BoolArray::from_iter([true, false, true, true]).into_array()),
1131 &mut ctx,
1132 )?
1133 .into_array();
1134 let idx = PiecewiseSequenceArray::try_new(
1135 buffer![0u64].into_array(),
1136 ConstantArray::new(4u64, 1).into_array(),
1137 ConstantArray::new(1u64, 1).into_array(),
1138 4,
1139 )?
1140 .into_array();
1141
1142 let result = list.take(idx)?.execute::<ListViewArray>(&mut ctx)?;
1143 assert_eq!(result.offset_at(0, &mut ctx), 0);
1144 assert_eq!(result.size_at(0, &mut ctx), 2);
1145 assert_eq!(result.offset_at(1, &mut ctx), 2);
1146 assert_eq!(result.size_at(1, &mut ctx), 0);
1147 assert_eq!(result.offset_at(2, &mut ctx), 2);
1148 assert_eq!(result.size_at(2, &mut ctx), 3);
1149 assert_eq!(result.offset_at(3, &mut ctx), 5);
1150 assert_eq!(result.size_at(3, &mut ctx), 1);
1151
1152 let element_dtype: Arc<DType> = Arc::new(I32.into());
1153 assert_eq!(
1154 result.execute_scalar(0, &mut ctx)?,
1155 Scalar::list(
1156 Arc::clone(&element_dtype),
1157 vec![0i32.into(), 1.into()],
1158 Nullability::Nullable
1159 )
1160 );
1161 assert!(result.is_invalid(1, &mut ctx)?);
1162 assert_eq!(
1163 result.execute_scalar(2, &mut ctx)?,
1164 Scalar::list(
1165 Arc::clone(&element_dtype),
1166 vec![2i32.into(), 3.into(), 4.into()],
1167 Nullability::Nullable
1168 )
1169 );
1170 assert_eq!(
1171 result.execute_scalar(3, &mut ctx)?,
1172 Scalar::list(element_dtype, vec![5i32.into()], Nullability::Nullable)
1173 );
1174 Ok(())
1175 }
1176
1177 #[test]
1178 fn piecewise_sequence_take_nullable_list_array_lengths() -> VortexResult<()> {
1179 let mut ctx = SESSION.create_execution_ctx();
1180 let list = ListArray::try_new(
1181 buffer![0i32, 1, 99, 100, 2, 3, 4, 5].into_array(),
1182 buffer![0u32, 2, 4, 7, 8].into_array(),
1183 Validity::Array(BoolArray::from_iter([true, false, true, true]).into_array()),
1184 &mut ctx,
1185 )?
1186 .into_array();
1187 let idx = PiecewiseSequenceArray::try_new(
1188 buffer![1u64, 0].into_array(),
1189 buffer![2u64, 1].into_array(),
1190 ConstantArray::new(1u64, 2).into_array(),
1191 3,
1192 )?
1193 .into_array();
1194
1195 let result = list.take(idx)?.execute::<ListViewArray>(&mut ctx)?;
1196 assert_eq!(result.offset_at(0, &mut ctx), 0);
1197 assert_eq!(result.size_at(0, &mut ctx), 0);
1198 assert_eq!(result.offset_at(1, &mut ctx), 0);
1199 assert_eq!(result.size_at(1, &mut ctx), 3);
1200 assert_eq!(result.offset_at(2, &mut ctx), 3);
1201 assert_eq!(result.size_at(2, &mut ctx), 2);
1202
1203 let element_dtype: Arc<DType> = Arc::new(I32.into());
1204 assert!(result.is_invalid(0, &mut ctx)?);
1205 assert_eq!(
1206 result.execute_scalar(1, &mut ctx)?,
1207 Scalar::list(
1208 Arc::clone(&element_dtype),
1209 vec![2i32.into(), 3.into(), 4.into()],
1210 Nullability::Nullable
1211 )
1212 );
1213 assert_eq!(
1214 result.execute_scalar(2, &mut ctx)?,
1215 Scalar::list(
1216 element_dtype,
1217 vec![0i32.into(), 1.into()],
1218 Nullability::Nullable
1219 )
1220 );
1221 Ok(())
1222 }
1223
1224 #[test]
1225 fn test_take_empty_array() {
1226 let mut ctx = SESSION.create_execution_ctx();
1227 let list = ListArray::try_new(
1228 buffer![0i32, 5, 3, 4].into_array(),
1229 buffer![0].into_array(),
1230 Validity::NonNullable,
1231 &mut ctx,
1232 )
1233 .unwrap()
1234 .into_array();
1235
1236 let idx = PrimitiveArray::empty::<i32>(Nullability::Nullable).into_array();
1237
1238 let result = list.take(idx).unwrap();
1239 assert_eq!(
1240 result.dtype(),
1241 &DType::List(
1242 Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
1243 Nullability::Nullable
1244 )
1245 );
1246 assert_eq!(result.len(), 0,);
1247 }
1248
1249 #[rstest]
1250 #[case(ListArray::try_new(
1251 buffer![0i32, 1, 2, 3, 4, 5].into_array(),
1252 buffer![0, 2, 3, 5, 5, 6].into_array(),
1253 Validity::NonNullable,
1254 &mut SESSION.create_execution_ctx(),
1255 ).unwrap())]
1256 #[case(ListArray::try_new(
1257 buffer![10i32, 20, 30, 40, 50].into_array(),
1258 buffer![0, 2, 3, 4, 5].into_array(),
1259 Validity::Array(BoolArray::from_iter(vec![true, false, true, true]).into_array()),
1260 &mut SESSION.create_execution_ctx(),
1261 ).unwrap())]
1262 #[case(ListArray::try_new(
1263 buffer![1i32, 2, 3].into_array(),
1264 buffer![0, 0, 2, 2, 3].into_array(), Validity::NonNullable,
1266 &mut SESSION.create_execution_ctx(),
1267 ).unwrap())]
1268 #[case(ListArray::try_new(
1269 buffer![42i32, 43].into_array(),
1270 buffer![0, 2].into_array(),
1271 Validity::NonNullable,
1272 &mut SESSION.create_execution_ctx(),
1273 ).unwrap())]
1274 #[case({
1275 let elements = buffer![0i32..200].into_array();
1276 let mut offsets = vec![0u64];
1277 for i in 1..=50 {
1278 offsets.push(offsets[i - 1] + (i as u64 % 5)); }
1280 ListArray::try_new(
1281 elements,
1282 PrimitiveArray::from_iter(offsets).into_array(),
1283 Validity::NonNullable,
1284 &mut SESSION.create_execution_ctx(),
1285 ).unwrap()
1286 })]
1287 #[case(ListArray::try_new(
1288 PrimitiveArray::from_option_iter([Some(1i32), None, Some(3), Some(4), None]).into_array(),
1289 buffer![0, 2, 3, 5].into_array(),
1290 Validity::NonNullable,
1291 &mut SESSION.create_execution_ctx(),
1292 ).unwrap())]
1293 fn test_take_list_conformance(#[case] list: ListArray) {
1294 test_take_conformance(&list.into_array(), &mut SESSION.create_execution_ctx());
1295 }
1296
1297 #[test]
1298 fn test_u64_offset_accumulation_non_nullable() {
1299 let mut ctx = SESSION.create_execution_ctx();
1300 let elements = buffer![0i32; 200].into_array();
1301 let offsets = buffer![0u8, 200].into_array();
1302 let list = ListArray::try_new(elements, offsets, Validity::NonNullable, &mut ctx)
1303 .unwrap()
1304 .into_array();
1305
1306 let idx = buffer![0u8, 0].into_array();
1308 let result = list.take(idx).unwrap();
1309
1310 assert_eq!(result.len(), 2);
1311
1312 let result_view = result.execute::<ListViewArray>(&mut ctx).unwrap();
1313 assert_eq!(result_view.len(), 2);
1314 assert!(
1315 result_view
1316 .is_valid(0, &mut SESSION.create_execution_ctx())
1317 .unwrap()
1318 );
1319 assert!(
1320 result_view
1321 .is_valid(1, &mut SESSION.create_execution_ctx())
1322 .unwrap()
1323 );
1324 let expected = ListArray::new(
1325 buffer![0i32; 400].into_array(),
1326 buffer![0u32, 200, 400].into_array(),
1327 Validity::NonNullable,
1328 &mut ctx,
1329 );
1330 assert_arrays_eq!(result_view, expected, &mut ctx);
1331 }
1332
1333 #[test]
1334 fn test_u64_offset_accumulation_nullable() {
1335 let mut ctx = SESSION.create_execution_ctx();
1336 let elements = buffer![0i32; 150].into_array();
1337 let offsets = buffer![0u8, 150, 150].into_array();
1338 let validity = BoolArray::from_iter(vec![true, false]).into_array();
1339 let list = ListArray::try_new(elements, offsets, Validity::Array(validity), &mut ctx)
1340 .unwrap()
1341 .into_array();
1342
1343 let idx = PrimitiveArray::from_option_iter(vec![Some(0u8), None, Some(0u8)]).into_array();
1345 let result = list.take(idx).unwrap();
1346
1347 assert_eq!(result.len(), 3);
1348
1349 let result_view = result.execute::<ListViewArray>(&mut ctx).unwrap();
1350 assert_eq!(result_view.len(), 3);
1351 assert!(
1352 result_view
1353 .is_valid(0, &mut SESSION.create_execution_ctx())
1354 .unwrap()
1355 );
1356 assert!(
1357 result_view
1358 .is_invalid(1, &mut SESSION.create_execution_ctx())
1359 .unwrap()
1360 );
1361 assert!(
1362 result_view
1363 .is_valid(2, &mut SESSION.create_execution_ctx())
1364 .unwrap()
1365 );
1366 let expected = ListArray::new(
1367 buffer![0i32; 300].into_array(),
1368 buffer![0u32, 150, 150, 300].into_array(),
1369 Validity::from_iter([true, false, true]),
1370 &mut ctx,
1371 );
1372 assert_arrays_eq!(result_view, expected, &mut ctx);
1373 }
1374
1375 #[test]
1380 fn test_take_validity_length_mismatch_regression() {
1381 let mut ctx = SESSION.create_execution_ctx();
1382 let list = ListArray::try_new(
1384 buffer![1i32, 2, 3, 4].into_array(),
1385 buffer![0, 2, 4].into_array(),
1386 Validity::Array(BoolArray::from_iter(vec![true, true]).into_array()),
1387 &mut ctx,
1388 )
1389 .unwrap()
1390 .into_array();
1391
1392 let idx = buffer![0u32, 1, 0, 1].into_array();
1394
1395 let result = list.take(idx).unwrap();
1397 assert_eq!(result.len(), 4);
1398 let expected = ListArray::new(
1399 buffer![1i32, 2, 3, 4, 1, 2, 3, 4].into_array(),
1400 buffer![0u32, 2, 4, 6, 8].into_array(),
1401 Validity::AllValid,
1402 &mut ctx,
1403 );
1404 assert_arrays_eq!(result, expected, &mut SESSION.create_execution_ctx());
1405 }
1406}