1use std::fmt::Display;
5use std::fmt::Formatter;
6use std::sync::Arc;
7
8use num_traits::AsPrimitive;
9use vortex_buffer::BitBufferMut;
10use vortex_error::VortexExpect;
11use vortex_error::VortexResult;
12use vortex_error::vortex_ensure;
13use vortex_error::vortex_ensure_eq;
14use vortex_error::vortex_err;
15use vortex_mask::Mask;
16
17use crate::ArrayRef;
18use crate::ArraySlots;
19use crate::ExecutionCtx;
20use crate::aggregate_fn::NumericalAggregateOpts;
21use crate::aggregate_fn::fns::min_max::min_max;
22use crate::array::Array;
23use crate::array::ArrayParts;
24use crate::array::TypedArrayRef;
25use crate::array::child_to_validity;
26use crate::array::validity_to_child;
27use crate::array_slots;
28use crate::arrays::ListView;
29use crate::arrays::Primitive;
30use crate::arrays::PrimitiveArray;
31use crate::arrays::bool;
32use crate::arrays::primitive::PrimitiveArrayExt;
33use crate::builtins::ArrayBuiltins;
34use crate::dtype::DType;
35use crate::dtype::IntegerPType;
36use crate::dtype::PType;
37use crate::expr::stats::Stat;
38use crate::match_each_integer_ptype;
39use crate::match_each_unsigned_integer_ptype;
40use crate::scalar_fn::fns::operators::Operator;
41use crate::validity::Validity;
42
43#[array_slots(ListView)]
44pub struct ListViewSlots {
45 #[slot(0)]
48 pub elements: ArrayRef,
49 #[slot(1)]
54 pub offsets: ArrayRef,
55 #[slot(2)]
60 pub sizes: ArrayRef,
61 #[slot(3)]
63 pub validity: Option<ArrayRef>,
64}
65
66#[derive(Clone, Debug)]
133pub struct ListViewData {
134 is_zero_copy_to_list: bool,
143}
144
145impl Display for ListViewData {
146 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
147 write!(f, "is_zero_copy_to_list: {}", self.is_zero_copy_to_list)
148 }
149}
150
151pub struct ListViewDataParts {
152 pub elements_dtype: Arc<DType>,
153
154 pub elements: ArrayRef,
156
157 pub offsets: ArrayRef,
159
160 pub sizes: ArrayRef,
162
163 pub validity: Validity,
165}
166
167impl ListViewData {
168 pub(crate) fn make_slots(
169 elements: &ArrayRef,
170 offsets: &ArrayRef,
171 sizes: &ArrayRef,
172 validity: &Validity,
173 len: usize,
174 ) -> ArraySlots {
175 ListViewSlots {
176 elements: elements.clone(),
177 offsets: offsets.clone(),
178 sizes: sizes.clone(),
179 validity: validity_to_child(validity, len),
180 }
181 .into_slots()
182 }
183
184 pub fn new() -> Self {
191 Self {
192 is_zero_copy_to_list: false,
193 }
194 }
195
196 pub fn try_new() -> VortexResult<Self> {
203 Ok(Self::new())
204 }
205
206 pub unsafe fn new_unchecked() -> Self {
226 Self::new()
227 }
228
229 pub fn validate(
231 elements: &ArrayRef,
232 offsets: &ArrayRef,
233 sizes: &ArrayRef,
234 validity: &Validity,
235 ctx: &mut ExecutionCtx,
236 ) -> VortexResult<()> {
237 vortex_ensure!(
239 offsets.dtype().is_int() && !offsets.dtype().is_nullable(),
240 "offsets must be non-nullable integer array, got {}",
241 offsets.dtype()
242 );
243 vortex_ensure!(
244 sizes.dtype().is_int() && !sizes.dtype().is_nullable(),
245 "sizes must be non-nullable integer array, got {}",
246 sizes.dtype()
247 );
248
249 vortex_ensure_eq!(
251 offsets.len(),
252 sizes.len(),
253 "offsets and sizes must have the same length",
254 );
255
256 if let Some(validity_len) = validity.maybe_len() {
258 vortex_ensure_eq!(
259 validity_len,
260 offsets.len(),
261 "validity length does not match array size",
262 );
263 }
264
265 if offsets.is_host() && sizes.is_host() {
267 let offsets_primitive = offsets.clone().execute::<PrimitiveArray>(ctx)?;
268 let sizes_primitive = sizes.clone().execute::<PrimitiveArray>(ctx)?;
269 let offsets_primitive =
272 offsets_primitive.reinterpret_cast(offsets_primitive.ptype().to_unsigned());
273 let sizes_primitive =
274 sizes_primitive.reinterpret_cast(sizes_primitive.ptype().to_unsigned());
275
276 match_each_unsigned_integer_ptype!(offsets_primitive.ptype(), |O| {
278 match_each_unsigned_integer_ptype!(sizes_primitive.ptype(), |S| {
279 let offsets_slice = offsets_primitive.as_slice::<O>();
280 let sizes_slice = sizes_primitive.as_slice::<S>();
281
282 validate_offsets_and_sizes::<O, S>(
283 offsets_slice,
284 sizes_slice,
285 elements.len() as u64,
286 )?;
287 })
288 });
289 }
290
291 Ok(())
292 }
293
294 pub unsafe fn with_zero_copy_to_list(mut self, is_zctl: bool) -> Self {
313 self.is_zero_copy_to_list = is_zctl;
314 self
315 }
316
317 pub fn is_zero_copy_to_list(&self) -> bool {
320 self.is_zero_copy_to_list
321 }
322}
323
324impl Default for ListViewData {
325 fn default() -> Self {
326 Self::new()
327 }
328}
329
330fn fill_referenced_mask<O: IntegerPType, S: IntegerPType>(
336 buf: &mut BitBufferMut,
337 offsets: &[O],
338 sizes: &[S],
339) {
340 let len = offsets.len();
341
342 assert_eq!(
343 len,
344 sizes.len(),
345 "offsets and sizes must be the same length"
346 );
347
348 for i in 0..len {
349 let start: usize = offsets[i].as_();
350 let size: usize = sizes[i].as_();
351 buf.fill_range(start, start + size, true);
352 }
353}
354
355pub trait ListViewArrayExt: ListViewArraySlotsExt {
356 fn nullability(&self) -> crate::dtype::Nullability {
357 match self.dtype() {
358 DType::List(_, nullability) => *nullability,
359 _ => unreachable!("ListViewArrayExt requires a list dtype"),
360 }
361 }
362
363 fn listview_validity(&self) -> Validity {
364 child_to_validity(
365 self.slots()[ListViewSlots::VALIDITY].as_ref(),
366 self.nullability(),
367 )
368 }
369
370 fn offset_at(&self, index: usize, ctx: &mut ExecutionCtx) -> usize {
371 assert!(
372 index < self.len(),
373 "Index {index} out of bounds 0..{}",
374 self.len()
375 );
376 self.offsets()
377 .as_opt::<Primitive>()
378 .map(|p| match_each_integer_ptype!(p.ptype(), |P| { p.as_slice::<P>()[index].as_() }))
379 .unwrap_or_else(|| {
380 self.offsets()
381 .execute_scalar(index, ctx)
382 .vortex_expect("offsets must support execute_scalar")
383 .as_primitive()
384 .as_::<usize>()
385 .vortex_expect("offset must fit in usize")
386 })
387 }
388
389 fn size_at(&self, index: usize, ctx: &mut ExecutionCtx) -> usize {
390 assert!(
391 index < self.len(),
392 "Index {} out of bounds 0..{}",
393 index,
394 self.len()
395 );
396 self.sizes()
397 .as_opt::<Primitive>()
398 .map(|p| match_each_integer_ptype!(p.ptype(), |P| { p.as_slice::<P>()[index].as_() }))
399 .unwrap_or_else(|| {
400 self.sizes()
401 .execute_scalar(index, ctx)
402 .vortex_expect("sizes must support execute_scalar")
403 .as_primitive()
404 .as_::<usize>()
405 .vortex_expect("size must fit in usize")
406 })
407 }
408
409 fn list_elements_at(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
410 let offset = self.offset_at(index, ctx);
411 let size = self.size_at(index, ctx);
412 self.elements().slice(offset..offset + size)
413 }
414
415 fn compute_referenced_elements_mask(&self, ctx: &mut ExecutionCtx) -> VortexResult<Mask> {
426 assert!(!self.elements().is_empty());
427 let len = self.elements().len();
428
429 let offsets_primitive = self.offsets().clone().execute::<PrimitiveArray>(ctx)?;
430 let sizes_primitive = self.sizes().clone().execute::<PrimitiveArray>(ctx)?;
431
432 let mut buf = BitBufferMut::new_unset(len);
433
434 let offsets_primitive =
436 offsets_primitive.reinterpret_cast(offsets_primitive.ptype().to_unsigned());
437 let sizes_primitive =
438 sizes_primitive.reinterpret_cast(sizes_primitive.ptype().to_unsigned());
439 match_each_unsigned_integer_ptype!(offsets_primitive.ptype(), |O| {
440 match_each_unsigned_integer_ptype!(sizes_primitive.ptype(), |S| {
441 fill_referenced_mask::<O, S>(
442 &mut buf,
443 offsets_primitive.as_slice::<O>(),
444 sizes_primitive.as_slice::<S>(),
445 );
446 })
447 });
448
449 Ok(Mask::from_buffer(buf.freeze()))
450 }
451
452 fn compute_density(&self, ctx: &mut ExecutionCtx) -> VortexResult<f32> {
456 if self.elements().is_empty() {
457 return Ok(1.0);
458 }
459
460 if self.sizes().is_empty() {
461 return Ok(0.0);
462 }
463
464 let density = match self.compute_referenced_elements_mask(ctx)? {
465 Mask::AllTrue(_) => 1.0,
466 Mask::AllFalse(_) => 0.0,
467 Mask::Values(values) => values.true_count() as f32 / self.elements().len() as f32,
468 };
469
470 Ok(density)
471 }
472
473 fn upper_bound_density(&self, ctx: &mut ExecutionCtx) -> VortexResult<f32> {
480 let n_elts = self.elements().len();
481 if n_elts == 0 {
482 return Ok(1.0);
483 }
484
485 let sizes = self.sizes();
486 if sizes.is_empty() {
487 return Ok(0.0);
488 }
489
490 let sizes_sum = sizes
492 .statistics()
493 .compute_stat(Stat::Sum, ctx)?
494 .vortex_expect("sizes array has integer ptype elements")
495 .as_primitive()
496 .as_::<u64>()
497 .vortex_expect("integer ptypes can be upcast to u64");
498
499 let estimate = (sizes_sum as f32 / n_elts as f32).min(1.0);
502
503 debug_assert!(estimate >= 0.0);
504
505 Ok(estimate)
506 }
507
508 fn referenced_element_bounds(&self, ctx: &mut ExecutionCtx) -> VortexResult<(usize, usize)> {
521 let n_lists = self.len();
522 vortex_ensure!(
523 n_lists > 0,
524 "referenced_element_bounds requires a non-empty array"
525 );
526
527 if self.is_zero_copy_to_list() {
528 let start = self.offset_at(0, ctx);
529 let end = self.offset_at(n_lists - 1, ctx) + self.size_at(n_lists - 1, ctx);
530 return Ok((start, end));
531 }
532
533 let start = self
534 .offsets()
535 .statistics()
536 .compute_min::<usize>(ctx)
537 .vortex_expect("offsets must report a usize min statistic");
538
539 let wide_dtype = DType::from(if self.offsets().dtype().as_ptype().is_unsigned_int() {
542 PType::U64
543 } else {
544 PType::I64
545 });
546 let offsets = self.offsets().cast(wide_dtype.clone())?;
547 let sizes = self.sizes().cast(wide_dtype)?;
548 let end = min_max(
549 &offsets.binary(sizes, Operator::Add)?,
550 ctx,
551 NumericalAggregateOpts::default(),
552 )?
553 .vortex_expect("non-empty array must report a min/max")
554 .max
555 .as_primitive()
556 .as_::<usize>()
557 .vortex_expect("max `offset + size` must fit in a usize");
558
559 Ok((start, end))
560 }
561}
562impl<T: TypedArrayRef<ListView>> ListViewArrayExt for T {}
563
564impl Array<ListView> {
565 pub fn new(
567 elements: ArrayRef,
568 offsets: ArrayRef,
569 sizes: ArrayRef,
570 validity: Validity,
571 ctx: &mut ExecutionCtx,
572 ) -> Self {
573 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
574 let len = offsets.len();
575 let slots = ListViewData::make_slots(&elements, &offsets, &sizes, &validity, len);
576 ListViewData::validate(&elements, &offsets, &sizes, &validity, ctx)
577 .vortex_expect("`ListViewArray` construction failed");
578 let data = ListViewData::new();
579 unsafe { Array::from_parts_unchecked(ArrayParts::new(ListView, dtype, len, data, slots)) }
580 }
581
582 pub fn try_new(
584 elements: ArrayRef,
585 offsets: ArrayRef,
586 sizes: ArrayRef,
587 validity: Validity,
588 ctx: &mut ExecutionCtx,
589 ) -> VortexResult<Self> {
590 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
591 let len = offsets.len();
592 let slots = ListViewData::make_slots(&elements, &offsets, &sizes, &validity, len);
593 ListViewData::validate(&elements, &offsets, &sizes, &validity, ctx)?;
594 let data = ListViewData::try_new()?;
595 Ok(unsafe {
596 Array::from_parts_unchecked(ArrayParts::new(ListView, dtype, len, data, slots))
597 })
598 }
599
600 pub unsafe fn new_unchecked(
606 elements: ArrayRef,
607 offsets: ArrayRef,
608 sizes: ArrayRef,
609 validity: Validity,
610 ) -> Self {
611 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
612 let len = offsets.len();
613 let slots = ListViewData::make_slots(&elements, &offsets, &sizes, &validity, len);
614 let data = unsafe { ListViewData::new_unchecked() };
615 unsafe { Array::from_parts_unchecked(ArrayParts::new(ListView, dtype, len, data, slots)) }
616 }
617
618 pub unsafe fn with_zero_copy_to_list(self, is_zctl: bool) -> Self {
624 if cfg!(debug_assertions)
627 && is_zctl
628 && self.offsets().is_host()
629 && self.sizes().is_host()
630 && let Some(offsets_primitive) = self.offsets().as_opt::<Primitive>()
631 && let Some(sizes_primitive) = self.sizes().as_opt::<Primitive>()
632 {
633 validate_zctl(
634 self.elements(),
635 offsets_primitive.into_owned(),
636 sizes_primitive.into_owned(),
637 )
638 .vortex_expect("Failed to validate zero-copy to list flag");
639 }
640 let dtype = self.dtype().clone();
641 let len = self.len();
642 let slots: ArraySlots = self.slots().iter().cloned().collect();
643 let data = unsafe { self.into_data().with_zero_copy_to_list(is_zctl) };
644 unsafe { Array::from_parts_unchecked(ArrayParts::new(ListView, dtype, len, data, slots)) }
645 }
646
647 pub fn into_data_parts(self) -> ListViewDataParts {
648 let elements = self.slots()[ListViewSlots::ELEMENTS]
649 .clone()
650 .vortex_expect("ListViewArray elements slot");
651 let offsets = self.slots()[ListViewSlots::OFFSETS]
652 .clone()
653 .vortex_expect("ListViewArray offsets slot");
654 let sizes = self.slots()[ListViewSlots::SIZES]
655 .clone()
656 .vortex_expect("ListViewArray sizes slot");
657 let validity = self.listview_validity();
658 ListViewDataParts {
659 elements_dtype: Arc::new(elements.dtype().clone()),
660 elements,
661 offsets,
662 sizes,
663 validity,
664 }
665 }
666}
667
668fn validate_offsets_and_sizes<O, S>(
670 offsets_slice: &[O],
671 sizes_slice: &[S],
672 elements_len: u64,
673) -> VortexResult<()>
674where
675 O: IntegerPType,
676 S: IntegerPType,
677{
678 debug_assert_eq!(offsets_slice.len(), sizes_slice.len());
679
680 #[allow(clippy::absurd_extreme_comparisons, unused_comparisons)]
681 for i in 0..offsets_slice.len() {
682 let offset = offsets_slice[i];
683 let size = sizes_slice[i];
684
685 vortex_ensure!(offset >= O::zero(), "cannot have negative offsets");
686 vortex_ensure!(size >= S::zero(), "cannot have negative size");
687
688 let offset_u64 = offset
689 .to_u64()
690 .ok_or_else(|| vortex_err!("offset[{i}] = {offset:?} cannot be converted to u64"))?;
691
692 let size_u64 = size
693 .to_u64()
694 .ok_or_else(|| vortex_err!("size[{i}] = {size:?} cannot be converted to u64"))?;
695
696 let end = offset_u64.checked_add(size_u64).ok_or_else(|| {
698 vortex_err!("offset[{i}] ({offset_u64}) + size[{i}] ({size_u64}) would overflow u64")
699 })?;
700
701 if offset_u64 == elements_len {
702 vortex_ensure_eq!(
703 size_u64,
704 0,
705 "views to the end of the elements array (length {elements_len}) must have size 0",
706 );
707 }
708
709 vortex_ensure!(
710 end <= elements_len,
711 "offset[{i}] + size[{i}] = {offset_u64} + {size_u64} = {end} \
712 exceeds elements length {elements_len}",
713 );
714 }
715
716 Ok(())
717}
718
719fn validate_zctl(
722 elements: &ArrayRef,
723 offsets_primitive: PrimitiveArray,
724 sizes_primitive: PrimitiveArray,
725) -> VortexResult<()> {
726 let offsets_sorted = match_each_integer_ptype!(offsets_primitive.ptype(), |P| {
729 offsets_primitive.as_slice::<P>().is_sorted()
730 });
731 vortex_ensure!(offsets_sorted, "offsets must be sorted");
732
733 fn validate_monotonic_ends<O: IntegerPType, S: IntegerPType>(
736 offsets_slice: &[O],
737 sizes_slice: &[S],
738 len: usize,
739 ) -> VortexResult<()> {
740 let mut max_end = 0usize;
741
742 for i in 0..len {
743 let offset = offsets_slice[i].to_usize().unwrap_or(usize::MAX);
744 let size = sizes_slice[i].to_usize().unwrap_or(usize::MAX);
745
746 vortex_ensure!(
748 offset >= max_end,
749 "Zero-copy-to-list requires views to be non-overlapping and ordered: \
750 view[{}] starts at {} but previous views extend to {}",
751 i,
752 offset,
753 max_end
754 );
755
756 let end = offset.saturating_add(size);
758 max_end = max_end.max(end);
759 }
760
761 Ok(())
762 }
763
764 let offsets_dtype = offsets_primitive.dtype();
765 let sizes_dtype = sizes_primitive.dtype();
766 let len = offsets_primitive.len();
767
768 let offsets_unsigned =
770 offsets_primitive.reinterpret_cast(offsets_dtype.as_ptype().to_unsigned());
771 let sizes_unsigned = sizes_primitive.reinterpret_cast(sizes_dtype.as_ptype().to_unsigned());
772
773 match_each_unsigned_integer_ptype!(offsets_unsigned.ptype(), |O| {
775 match_each_unsigned_integer_ptype!(sizes_unsigned.ptype(), |S| {
776 let offsets_slice = offsets_unsigned.as_slice::<O>();
777 let sizes_slice = sizes_unsigned.as_slice::<S>();
778
779 validate_monotonic_ends(offsets_slice, sizes_slice, len)?;
780 })
781 });
782
783 let mut element_references = vec![0u8; elements.len()];
788
789 fn count_references<O: IntegerPType, S: IntegerPType>(
790 element_references: &mut [u8],
791 offsets_primitive: PrimitiveArray,
792 sizes_primitive: PrimitiveArray,
793 ) {
794 let offsets_slice = offsets_primitive.as_slice::<O>();
795 let sizes_slice = sizes_primitive.as_slice::<S>();
796
797 for i in 0..offsets_slice.len() {
800 let offset: usize = offsets_slice[i].as_();
801 let size: usize = sizes_slice[i].as_();
802 for j in offset..offset + size {
803 element_references[j] = element_references[j].saturating_add(1);
804 }
805 }
806 }
807
808 match_each_unsigned_integer_ptype!(offsets_unsigned.ptype(), |O| {
809 match_each_unsigned_integer_ptype!(sizes_unsigned.ptype(), |S| {
810 count_references::<O, S>(&mut element_references, offsets_unsigned, sizes_unsigned);
811 })
812 });
813
814 let leftmost_used = element_references
816 .iter()
817 .position(|&references| references != 0);
818 let rightmost_used = element_references
819 .iter()
820 .rposition(|&references| references != 0);
821
822 if let (Some(first_ref), Some(last_ref)) = (leftmost_used, rightmost_used) {
823 vortex_ensure!(
824 element_references[first_ref..=last_ref]
825 .iter()
826 .all(|&references| references != 0),
827 "found gap in elements array between first and last referenced elements"
828 );
829 }
830
831 vortex_ensure!(element_references.iter().all(|&references| references <= 1));
832
833 Ok(())
834}