1use std::sync::Arc;
14
15use num_traits::ToPrimitive;
16use vortex_buffer::BufferAllocatorRef;
17use vortex_error::VortexExpect;
18use vortex_error::VortexResult;
19use vortex_error::vortex_ensure;
20use vortex_error::vortex_ensure_eq;
21use vortex_error::vortex_panic;
22
23use crate::ArrayRef;
24use crate::Canonical;
25use crate::ExecutionCtx;
26use crate::array::ArrayView;
27use crate::array::IntoArray;
28use crate::arrays::List;
29use crate::arrays::ListView;
30use crate::arrays::ListViewArray;
31use crate::arrays::PrimitiveArray;
32use crate::arrays::list::ListArraySlotsExt;
33use crate::arrays::listview::ListViewArrayExt;
34use crate::arrays::listview::ListViewArraySlotsExt;
35use crate::builders::ArrayBuilder;
36use crate::builders::ChildBuilder;
37use crate::builders::DEFAULT_BUILDER_CAPACITY;
38use crate::builders::PrimitiveBuilder;
39use crate::builders::UninitRange;
40use crate::builders::ValidityBuilder;
41use crate::dtype::DType;
42use crate::dtype::IntegerPType;
43use crate::dtype::Nullability;
44use crate::dtype::OffsetBuilderPType;
45use crate::match_each_integer_ptype;
46use crate::scalar::ListScalar;
47use crate::scalar::Scalar;
48
49pub struct ListViewBuilder<O: OffsetBuilderPType, S: OffsetBuilderPType> {
59 dtype: DType,
61
62 elements_builder: ChildBuilder,
64
65 offsets_builder: PrimitiveBuilder<O>,
67
68 sizes_builder: PrimitiveBuilder<S>,
70
71 nulls: ValidityBuilder,
73
74 zero_copy_to_list: bool,
81}
82
83impl<O: OffsetBuilderPType, S: OffsetBuilderPType> ListViewBuilder<O, S> {
84 #[deprecated(note = "use `new_in` with an explicit allocator")]
86 pub fn new(element_dtype: Arc<DType>, nullability: Nullability) -> Self {
87 Self::new_in(element_dtype, nullability, BufferAllocatorRef::static_ref())
88 }
89
90 pub fn new_in(
92 element_dtype: Arc<DType>,
93 nullability: Nullability,
94 allocator: &BufferAllocatorRef,
95 ) -> Self {
96 Self::with_capacity_in(
97 element_dtype,
98 nullability,
99 DEFAULT_BUILDER_CAPACITY * 2,
102 DEFAULT_BUILDER_CAPACITY,
103 allocator,
104 )
105 }
106
107 #[deprecated(note = "use `with_capacity_in` with an explicit allocator")]
115 pub fn with_capacity(
116 element_dtype: Arc<DType>,
117 nullability: Nullability,
118 elements_capacity: usize,
119 capacity: usize,
120 ) -> Self {
121 Self::with_capacity_in(
122 element_dtype,
123 nullability,
124 elements_capacity,
125 capacity,
126 BufferAllocatorRef::static_ref(),
127 )
128 }
129
130 pub fn with_capacity_in(
136 element_dtype: Arc<DType>,
137 nullability: Nullability,
138 elements_capacity: usize,
139 capacity: usize,
140 allocator: &BufferAllocatorRef,
141 ) -> Self {
142 let elements_builder =
143 ChildBuilder::with_capacity(&element_dtype, elements_capacity, allocator);
144
145 let offsets_builder =
146 PrimitiveBuilder::<O>::with_capacity_in(Nullability::NonNullable, capacity, allocator);
147 let sizes_builder =
148 PrimitiveBuilder::<S>::with_capacity_in(Nullability::NonNullable, capacity, allocator);
149
150 let nulls = ValidityBuilder::new(capacity, allocator);
151
152 Self {
153 dtype: DType::List(element_dtype, nullability),
154 elements_builder,
155 offsets_builder,
156 sizes_builder,
157 nulls,
158 zero_copy_to_list: true,
159 }
160 }
161
162 pub fn append_array_as_list(
169 &mut self,
170 array: &ArrayRef,
171 ctx: &mut ExecutionCtx,
172 ) -> VortexResult<()> {
173 vortex_ensure_eq!(array.dtype(), self.element_dtype());
174
175 let curr_offset = self.elements_builder.len();
176 let num_elements = array.len();
177
178 assert!(
181 ((curr_offset + num_elements) as u64) < O::max_value_as_u64(),
182 "appending this list would cause an offset overflow"
183 );
184
185 self.elements_builder.append_array(array, ctx)?;
186 self.nulls.append_non_null();
187
188 self.offsets_builder.append_value(
189 O::from_usize(curr_offset).vortex_expect("Failed to convert from usize to `O`"),
190 );
191 self.sizes_builder.append_value(
192 S::from_usize(num_elements).vortex_expect("Failed to convert from usize to `S`"),
193 );
194
195 Ok(())
196 }
197
198 pub fn append_value(&mut self, value: ListScalar) -> VortexResult<()> {
203 let Some(elements) = value.elements() else {
204 vortex_ensure!(
206 self.dtype.is_nullable(),
207 "Cannot append null value to non-nullable list builder"
208 );
209 self.append_null();
210 return Ok(());
211 };
212
213 let curr_offset = self.elements_builder.len();
214 let num_elements = elements.len();
215
216 assert!(
219 ((curr_offset + num_elements) as u64) < O::max_value_as_u64(),
220 "appending this list would cause an offset overflow"
221 );
222
223 for scalar in elements {
224 self.elements_builder.append_scalar(&scalar)?;
225 }
226 self.nulls.append_non_null();
227
228 self.offsets_builder.append_value(
229 O::from_usize(curr_offset).vortex_expect("Failed to convert from usize to `O`"),
230 );
231 self.sizes_builder.append_value(
232 S::from_usize(num_elements).vortex_expect("Failed to convert from usize to `S`"),
233 );
234
235 Ok(())
236 }
237
238 pub fn append_array_as_repeated_list(
248 &mut self,
249 array: &ArrayRef,
250 n: usize,
251 ctx: &mut ExecutionCtx,
252 ) -> VortexResult<()> {
253 vortex_ensure_eq!(array.dtype(), self.element_dtype());
254
255 if n == 0 {
256 return Ok(());
257 }
258
259 let curr_offset = self.elements_builder.len();
260 let num_elements = array.len();
261
262 assert!(
265 ((curr_offset + num_elements) as u64) < O::max_value_as_u64(),
266 "appending this list would cause an offset overflow"
267 );
268
269 self.elements_builder.append_array(array, ctx)?;
270
271 let offset =
272 O::from_usize(curr_offset).vortex_expect("Failed to convert from usize to `O`");
273 let size = S::from_usize(num_elements).vortex_expect("Failed to convert from usize to `S`");
274 self.offsets_builder.append_n_values(offset, n);
275 self.sizes_builder.append_n_values(size, n);
276 self.nulls.append_n_non_nulls(n);
277
278 if n > 1 && num_elements > 0 {
279 self.zero_copy_to_list = false;
280 }
281
282 Ok(())
283 }
284
285 pub fn finish_into_listview(&mut self) -> ListViewArray {
287 debug_assert_eq!(self.offsets_builder.len(), self.sizes_builder.len());
288 debug_assert_eq!(self.offsets_builder.len(), self.nulls.len());
289
290 let elements = self.elements_builder.finish();
291 let offsets = self.offsets_builder.finish();
292 let sizes = self.sizes_builder.finish();
293 let validity = self.nulls.finish_with_nullability(self.dtype.nullability());
294
295 let zero_copy_to_list = std::mem::replace(&mut self.zero_copy_to_list, true);
296
297 unsafe {
309 ListViewArray::new_unchecked(elements, offsets, sizes, validity)
310 .with_zero_copy_to_list(zero_copy_to_list)
311 }
312 }
313
314 pub fn element_dtype(&self) -> &DType {
317 let DType::List(element_dtype, ..) = &self.dtype else {
318 vortex_panic!("`ListViewBuilder` has an incorrect dtype: {}", self.dtype);
319 };
320
321 element_dtype
322 }
323
324 pub fn append_list_array(
331 &mut self,
332 array: ArrayView<'_, List>,
333 ctx: &mut ExecutionCtx,
334 ) -> VortexResult<()> {
335 if array.is_empty() {
336 return Ok(());
337 }
338
339 self.nulls.append_validity(array.validity()?, array.len());
340
341 let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
342 match_each_integer_ptype!(offsets.ptype(), |OffsetType| {
343 extend_from_list(
344 self,
345 array.elements(),
346 offsets.as_slice::<OffsetType>(),
347 ctx,
348 )?
349 });
350 Ok(())
351 }
352
353 pub fn append_listview_array(
364 &mut self,
365 array: ArrayView<'_, ListView>,
366 ctx: &mut ExecutionCtx,
367 ) -> VortexResult<()> {
368 if array.is_empty() {
369 return Ok(());
370 }
371
372 let len = array.len();
373
374 let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
381 let sizes = array.sizes().clone().execute::<PrimitiveArray>(ctx)?;
382
383 let (start, end) = if array.is_zero_copy_to_list() {
387 let last = len - 1;
388 (
389 metadata_at(&offsets, 0),
390 metadata_at(&offsets, last) + metadata_at(&sizes, last),
391 )
392 } else {
393 array.into_owned().referenced_element_bounds(ctx)?
394 };
395
396 self.zero_copy_to_list &= array.is_zero_copy_to_list();
399
400 self.nulls.append_validity(array.validity()?, len);
401
402 let elements_base = self.elements_builder.len();
404
405 assert!(
408 ((elements_base + (end - start)) as u64) < O::max_value_as_u64(),
409 "appending this list would cause an offset overflow"
410 );
411
412 if end > start {
413 self.elements_builder
414 .append_array(&array.elements().slice(start..end)?, ctx)?;
415 }
416
417 assert_eq!(
421 self.elements_builder.len(),
422 elements_base + (end - start),
423 "appending the referenced elements did not extend the child by the window's length"
424 );
425
426 self.offsets_builder.reserve_exact(len);
427 let offsets_range = self.offsets_builder.uninit_range(len);
428 match_each_integer_ptype!(offsets.ptype(), |A| {
429 extend_rebased_offsets::<O, A>(
430 offsets_range,
431 offsets.as_slice::<A>(),
432 start,
433 elements_base,
434 );
435 });
436
437 self.sizes_builder.reserve_exact(len);
438 let mut sizes_range = self.sizes_builder.uninit_range(len);
439 if sizes.ptype() == S::PTYPE {
440 sizes_range.copy_from_slice(0, sizes.as_slice::<S>());
442 unsafe { sizes_range.finish() };
445 } else {
446 match_each_integer_ptype!(sizes.ptype(), |A| {
447 extend_converted_sizes::<S, A>(sizes_range, sizes.as_slice::<A>());
448 });
449 }
450
451 Ok(())
452 }
453}
454
455impl<O: OffsetBuilderPType, S: OffsetBuilderPType> ArrayBuilder for ListViewBuilder<O, S> {
456 fn as_any(&self) -> &dyn std::any::Any {
457 self
458 }
459
460 fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
461 self
462 }
463
464 fn dtype(&self) -> &DType {
465 &self.dtype
466 }
467
468 fn len(&self) -> usize {
469 self.offsets_builder.len()
470 }
471
472 fn append_zeros(&mut self, n: usize) {
473 debug_assert_eq!(self.offsets_builder.len(), self.sizes_builder.len());
474 debug_assert_eq!(self.offsets_builder.len(), self.nulls.len());
475
476 let curr_offset = self.elements_builder.len();
478
479 for _ in 0..n {
482 self.offsets_builder.append_value(
483 O::from_usize(curr_offset).vortex_expect("Failed to convert from usize to `O`"),
484 );
485 self.sizes_builder.append_value(S::zero());
486 }
487
488 self.nulls.append_n_non_nulls(n);
489 }
490
491 unsafe fn append_nulls_unchecked(&mut self, n: usize) {
492 debug_assert_eq!(self.offsets_builder.len(), self.sizes_builder.len());
493 debug_assert_eq!(self.offsets_builder.len(), self.nulls.len());
494
495 let curr_offset = self.elements_builder.len();
497
498 for _ in 0..n {
500 self.offsets_builder.append_value(
501 O::from_usize(curr_offset).vortex_expect("Failed to convert from usize to `O`"),
502 );
503 self.sizes_builder.append_value(S::zero());
504 }
505
506 self.nulls.append_n_nulls(n);
508 }
509
510 fn append_scalar(&mut self, scalar: &Scalar) -> VortexResult<()> {
511 vortex_ensure_eq!(
512 scalar.dtype(),
513 self.dtype(),
514 "ListViewBuilder received a scalar with the wrong dtype"
515 );
516
517 let list_scalar = scalar.as_list();
518 self.append_value(list_scalar)
519 }
520
521 fn reserve_exact(&mut self, capacity: usize) {
522 self.elements_builder.reserve_exact(capacity * 2);
523 self.offsets_builder.reserve_exact(capacity);
524 self.sizes_builder.reserve_exact(capacity);
525 self.nulls.reserve_exact(capacity);
526 }
527
528 fn finish(&mut self) -> ArrayRef {
529 self.finish_into_listview().into_array()
530 }
531
532 fn finish_into_canonical(&mut self, _ctx: &mut ExecutionCtx) -> Canonical {
533 Canonical::List(self.finish_into_listview())
534 }
535}
536
537fn extend_from_list<O, S, OffsetType>(
543 builder: &mut ListViewBuilder<O, S>,
544 elements: &ArrayRef,
545 offsets: &[OffsetType],
546 ctx: &mut ExecutionCtx,
547) -> VortexResult<()>
548where
549 O: OffsetBuilderPType,
550 S: OffsetBuilderPType,
551 OffsetType: IntegerPType,
552{
553 let num_lists = offsets.len() - 1;
554 let first: usize = offsets[0].as_();
555 let last: usize = offsets[num_lists].as_();
556
557 let elements_base = builder.elements_builder.len();
558
559 assert!(
562 ((elements_base + (last - first)) as u64) < O::max_value_as_u64(),
563 "appending this list would cause an offset overflow"
564 );
565
566 if last > first {
567 builder
568 .elements_builder
569 .append_array(&elements.slice(first..last)?, ctx)?;
570 }
571
572 builder.offsets_builder.reserve_exact(num_lists);
573 builder.sizes_builder.reserve_exact(num_lists);
574 let mut offsets_range = builder.offsets_builder.uninit_range(num_lists);
575 let mut sizes_range = builder.sizes_builder.uninit_range(num_lists);
576 for i in 0..num_lists {
577 let start: usize = offsets[i].as_();
578 let end: usize = offsets[i + 1].as_();
579 offsets_range.set_value(
580 i,
581 O::from_usize(start - first + elements_base)
582 .vortex_expect("Failed to convert from usize to `O`"),
583 );
584 sizes_range.set_value(
585 i,
586 S::from_usize(end - start).vortex_expect("Failed to convert from usize to `S`"),
587 );
588 }
589 unsafe { offsets_range.finish() };
592 unsafe { sizes_range.finish() };
593 Ok(())
594}
595
596fn metadata_at(metadata: &PrimitiveArray, index: usize) -> usize {
598 match_each_integer_ptype!(metadata.ptype(), |A| {
599 metadata.as_slice::<A>()[index]
600 .to_usize()
601 .vortex_expect("list view metadata must fit in a usize")
602 })
603}
604
605fn extend_rebased_offsets<O: OffsetBuilderPType, A: IntegerPType>(
611 mut range: UninitRange<O>,
612 offsets: &[A],
613 window_start: usize,
614 elements_base: usize,
615) {
616 debug_assert_eq!(range.len(), offsets.len());
617
618 for (i, &offset) in offsets.iter().enumerate() {
619 let offset = offset
620 .to_usize()
621 .vortex_expect("offsets must always fit in usize");
622 debug_assert!(
623 offset >= window_start,
624 "offset {offset} precedes the referenced window at {window_start}"
625 );
626 let rebased = O::from_usize(offset - window_start + elements_base)
627 .vortex_expect("rebased offset did not fit into the builder's offset type");
628 range.set_value(i, rebased);
629 }
630
631 unsafe { range.finish() };
634}
635
636fn extend_converted_sizes<S: OffsetBuilderPType, A: IntegerPType>(
640 mut range: UninitRange<S>,
641 sizes: &[A],
642) {
643 debug_assert_eq!(range.len(), sizes.len());
644
645 for (i, &size) in sizes.iter().enumerate() {
646 let size = S::from_usize(
647 size.to_usize()
648 .vortex_expect("sizes must always fit in usize"),
649 )
650 .vortex_expect("size did not fit into the builder's size type");
651 range.set_value(i, size);
652 }
653
654 unsafe { range.finish() };
657}
658
659#[cfg(test)]
660mod tests {
661 use std::sync::Arc;
662 use std::sync::LazyLock;
663
664 use vortex_buffer::BufferAllocatorRef;
665 use vortex_buffer::buffer;
666 use vortex_error::VortexExpect;
667 use vortex_error::VortexResult;
668 use vortex_session::VortexSession;
669
670 use super::ListViewBuilder;
671 use crate::IntoArray;
672 use crate::VortexSessionExecute;
673 use crate::arrays::ConstantArray;
674 use crate::arrays::ListArray;
675 use crate::arrays::ListViewArray;
676 use crate::arrays::listview::ListViewArrayExt;
677 use crate::arrays::listview::ListViewArraySlotsExt;
678 use crate::assert_arrays_eq;
679 use crate::builders::ArrayBuilder;
680 use crate::builders::listview::PrimitiveArray;
681 use crate::dtype::DType;
682 use crate::dtype::Nullability::NonNullable;
683 use crate::dtype::Nullability::Nullable;
684 use crate::dtype::PType::I32;
685 use crate::scalar::Scalar;
686 use crate::validity::Validity;
687
688 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
689
690 #[test]
691 fn test_empty() {
692 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
693 Arc::new(I32.into()),
694 NonNullable,
695 0,
696 0,
697 BufferAllocatorRef::static_ref(),
698 );
699
700 let listview = builder.finish();
701 assert_eq!(listview.len(), 0);
702 assert_eq!(
703 listview.dtype(),
704 &DType::List(Arc::new(I32.into()), NonNullable)
705 );
706 }
707
708 #[test]
709 fn test_basic_append_and_nulls() {
710 let mut ctx = SESSION.create_execution_ctx();
711 let dtype: Arc<DType> = Arc::new(I32.into());
712 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
713 Arc::clone(&dtype),
714 Nullable,
715 0,
716 0,
717 BufferAllocatorRef::static_ref(),
718 );
719
720 builder
722 .append_value(
723 Scalar::list(
724 Arc::clone(&dtype),
725 vec![1i32.into(), 2i32.into(), 3i32.into()],
726 NonNullable,
727 )
728 .as_list(),
729 )
730 .unwrap();
731
732 builder
734 .append_value(Scalar::list_empty(Arc::clone(&dtype), NonNullable).as_list())
735 .unwrap();
736
737 builder.append_null();
739
740 builder
742 .append_value(
743 Scalar::list(dtype, vec![4i32.into(), 5i32.into()], NonNullable).as_list(),
744 )
745 .unwrap();
746
747 let listview = builder.finish_into_listview();
748 assert_eq!(listview.len(), 4);
749
750 assert_arrays_eq!(
752 listview.list_elements_at(0, &mut ctx).unwrap(),
753 PrimitiveArray::from_iter([1i32, 2, 3]),
754 &mut ctx
755 );
756
757 assert_eq!(listview.list_elements_at(1, &mut ctx).unwrap().len(), 0);
759
760 assert!(
762 !listview
763 .validity()
764 .vortex_expect("listview validity should be derivable")
765 .execute_is_valid(2, &mut ctx)
766 .unwrap()
767 );
768
769 assert_arrays_eq!(
771 listview.list_elements_at(3, &mut ctx).unwrap(),
772 PrimitiveArray::from_iter([4i32, 5]),
773 &mut ctx
774 );
775 let expected = ListArray::new(
776 buffer![1i32, 2, 3, 4, 5].into_array(),
777 buffer![0u32, 3, 3, 3, 5].into_array(),
778 Validity::from_iter([true, true, false, true]),
779 &mut ctx,
780 );
781 assert_arrays_eq!(listview, expected, &mut ctx);
782 }
783
784 #[test]
785 fn test_different_offset_size_types() {
786 let mut ctx = SESSION.create_execution_ctx();
787 let dtype: Arc<DType> = Arc::new(I32.into());
789 let mut builder = ListViewBuilder::<u64, u32>::with_capacity_in(
790 Arc::clone(&dtype),
791 NonNullable,
792 0,
793 0,
794 BufferAllocatorRef::static_ref(),
795 );
796
797 builder
798 .append_value(
799 Scalar::list(
800 Arc::clone(&dtype),
801 vec![1i32.into(), 2i32.into()],
802 NonNullable,
803 )
804 .as_list(),
805 )
806 .unwrap();
807
808 builder
809 .append_value(
810 Scalar::list(
811 dtype,
812 vec![3i32.into(), 4i32.into(), 5i32.into()],
813 NonNullable,
814 )
815 .as_list(),
816 )
817 .unwrap();
818
819 let listview = builder.finish_into_listview();
820 assert_eq!(listview.len(), 2);
821
822 assert_arrays_eq!(
824 listview.list_elements_at(0, &mut ctx).unwrap(),
825 PrimitiveArray::from_iter([1i32, 2]),
826 &mut ctx
827 );
828
829 assert_arrays_eq!(
831 listview.list_elements_at(1, &mut ctx).unwrap(),
832 PrimitiveArray::from_iter([3i32, 4, 5]),
833 &mut ctx
834 );
835
836 let dtype2: Arc<DType> = Arc::new(I32.into());
838 let mut builder2 = ListViewBuilder::<i64, i32>::with_capacity_in(
839 Arc::clone(&dtype2),
840 NonNullable,
841 0,
842 0,
843 BufferAllocatorRef::static_ref(),
844 );
845
846 for i in 0..5 {
847 builder2
848 .append_value(
849 Scalar::list(Arc::clone(&dtype2), vec![(i * 10).into()], NonNullable).as_list(),
850 )
851 .unwrap();
852 }
853
854 let listview2 = builder2.finish_into_listview();
855 assert_eq!(listview2.len(), 5);
856
857 for i in 0..5i32 {
859 assert_arrays_eq!(
860 listview2.list_elements_at(i as usize, &mut ctx).unwrap(),
861 PrimitiveArray::from_iter([i * 10]),
862 &mut ctx
863 );
864 }
865 }
866
867 #[test]
868 fn test_builder_trait_methods() {
869 let mut ctx = SESSION.create_execution_ctx();
870 let dtype: Arc<DType> = Arc::new(I32.into());
871 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
872 Arc::clone(&dtype),
873 Nullable,
874 0,
875 0,
876 BufferAllocatorRef::static_ref(),
877 );
878
879 builder.append_zeros(2);
881 assert_eq!(builder.len(), 2);
882
883 unsafe {
885 builder.append_nulls_unchecked(2);
886 }
887 assert_eq!(builder.len(), 4);
888
889 let list_scalar = Scalar::list(dtype, vec![10i32.into(), 20i32.into()], Nullable);
891 builder.append_scalar(&list_scalar).unwrap();
892 assert_eq!(builder.len(), 5);
893
894 let listview = builder.finish_into_listview();
895 assert_eq!(listview.len(), 5);
896
897 assert_eq!(listview.list_elements_at(0, &mut ctx).unwrap().len(), 0);
899 assert_eq!(listview.list_elements_at(1, &mut ctx).unwrap().len(), 0);
900
901 assert!(
903 !listview
904 .validity()
905 .vortex_expect("listview validity should be derivable")
906 .execute_is_valid(2, &mut ctx)
907 .unwrap()
908 );
909 assert!(
910 !listview
911 .validity()
912 .vortex_expect("listview validity should be derivable")
913 .execute_is_valid(3, &mut ctx)
914 .unwrap()
915 );
916
917 assert_arrays_eq!(
919 listview.list_elements_at(4, &mut ctx).unwrap(),
920 PrimitiveArray::from_iter([10i32, 20]),
921 &mut ctx
922 );
923 let expected = ListArray::new(
924 buffer![10i32, 20].into_array(),
925 buffer![0u32, 0, 0, 0, 0, 2].into_array(),
926 Validity::from_iter([true, true, false, false, true]),
927 &mut ctx,
928 );
929 assert_arrays_eq!(listview, expected, &mut ctx);
930 }
931
932 #[test]
933 fn test_extend_from_array() {
934 let mut ctx = SESSION.create_execution_ctx();
935 let dtype: Arc<DType> = Arc::new(I32.into());
936
937 let source = ListArray::from_iter_opt_slow::<u32, _, Vec<i32>>(
939 [Some(vec![1, 2, 3]), None, Some(vec![4, 5])],
940 Arc::new(I32.into()),
941 )
942 .unwrap();
943
944 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
945 Arc::clone(&dtype),
946 Nullable,
947 0,
948 0,
949 BufferAllocatorRef::static_ref(),
950 );
951
952 builder
954 .append_value(Scalar::list(dtype, vec![0i32.into()], NonNullable).as_list())
955 .unwrap();
956
957 let source = source
959 .into_array()
960 .execute::<ListViewArray>(&mut ctx)
961 .unwrap();
962 builder
963 .append_listview_array(source.as_view(), &mut ctx)
964 .unwrap();
965
966 let empty_source = ListArray::from_iter_opt_slow::<u32, _, Vec<i32>>(
968 std::iter::empty::<Option<Vec<i32>>>(),
969 Arc::new(I32.into()),
970 )
971 .unwrap();
972 let empty_source = empty_source
973 .into_array()
974 .execute::<ListViewArray>(&mut ctx)
975 .unwrap();
976 builder
977 .append_listview_array(empty_source.as_view(), &mut ctx)
978 .unwrap();
979
980 let listview = builder.finish_into_listview();
981 assert_eq!(listview.len(), 4);
982
983 assert_arrays_eq!(
986 listview.list_elements_at(0, &mut ctx).unwrap(),
987 PrimitiveArray::from_iter([0i32]),
988 &mut ctx
989 );
990
991 assert_arrays_eq!(
993 listview.list_elements_at(1, &mut ctx).unwrap(),
994 PrimitiveArray::from_iter([1i32, 2, 3]),
995 &mut ctx
996 );
997
998 assert!(
1000 !listview
1001 .validity()
1002 .vortex_expect("listview validity should be derivable")
1003 .execute_is_valid(2, &mut ctx)
1004 .unwrap()
1005 );
1006
1007 assert_arrays_eq!(
1009 listview.list_elements_at(3, &mut ctx).unwrap(),
1010 PrimitiveArray::from_iter([4i32, 5]),
1011 &mut ctx
1012 );
1013 let expected = ListArray::new(
1014 buffer![0i32, 1, 2, 3, 4, 5].into_array(),
1015 buffer![0u32, 1, 4, 4, 6].into_array(),
1016 Validity::from_iter([true, true, false, true]),
1017 &mut ctx,
1018 );
1019 assert_arrays_eq!(listview, expected, &mut ctx);
1020 }
1021
1022 #[test]
1023 fn test_append_list_array_grows_builder() -> VortexResult<()> {
1024 let mut ctx = SESSION.create_execution_ctx();
1025 let dtype: Arc<DType> = Arc::new(I32.into());
1026
1027 let lists: Vec<Option<Vec<i32>>> =
1030 (0..100).map(|i| (i % 10 != 0).then(|| vec![i])).collect();
1031 let source = ListArray::from_iter_opt_slow::<u32, _, _>(lists.clone(), Arc::clone(&dtype))?;
1032
1033 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1034 Arc::clone(&dtype),
1035 Nullable,
1036 0,
1037 0,
1038 BufferAllocatorRef::static_ref(),
1039 );
1040 builder.append_list_array(source.as_view(), &mut ctx)?;
1041 builder.append_list_array(source.as_view(), &mut ctx)?;
1043
1044 let listview = builder.finish_into_listview();
1045 assert!(listview.is_zero_copy_to_list());
1046
1047 let expected = ListArray::from_iter_opt_slow::<u32, _, _>(
1048 lists.iter().cloned().chain(lists.iter().cloned()),
1049 dtype,
1050 )?;
1051 assert_arrays_eq!(listview, expected, &mut ctx);
1052
1053 Ok(())
1054 }
1055
1056 #[test]
1059 fn test_constant_list_append_keeps_one_copy_of_the_value() -> VortexResult<()> {
1060 let mut ctx = SESSION.create_execution_ctx();
1061 let element_dtype: Arc<DType> = Arc::new(I32.into());
1062
1063 const ROWS: usize = 10_000;
1064 let fill = Scalar::list(
1065 Arc::clone(&element_dtype),
1066 vec![1i32.into(), 2i32.into(), 3i32.into()],
1067 NonNullable,
1068 );
1069 let constant = ConstantArray::new(fill, ROWS).into_array();
1070
1071 let mut builder = ListViewBuilder::<u64, u64>::with_capacity_in(
1072 element_dtype,
1073 NonNullable,
1074 0,
1075 0,
1076 BufferAllocatorRef::static_ref(),
1077 );
1078 constant.append_to_builder(&mut builder, &mut ctx)?;
1079 let listview = builder.finish_into_listview();
1080
1081 assert_eq!(listview.len(), ROWS);
1082 assert_eq!(
1083 listview.elements().len(),
1084 3,
1085 "the fill value should be stored once, not once per row",
1086 );
1087 assert!(!listview.is_zero_copy_to_list());
1088 assert_arrays_eq!(&listview.into_array(), &constant, &mut ctx);
1089
1090 Ok(())
1091 }
1092
1093 #[test]
1096 fn test_append_listview_array_trims_unreferenced_elements() -> VortexResult<()> {
1097 let mut ctx = SESSION.create_execution_ctx();
1098 let dtype: Arc<DType> = Arc::new(I32.into());
1099
1100 let source = ListArray::from_iter_slow::<u32, _>(
1102 (0..5).map(|i| vec![2 * i, 2 * i + 1]),
1103 Arc::clone(&dtype),
1104 )?
1105 .into_array()
1106 .execute::<ListViewArray>(&mut ctx)?;
1107 let middle = source.slice(1..4)?.execute::<ListViewArray>(&mut ctx)?;
1108
1109 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1110 Arc::clone(&dtype),
1111 NonNullable,
1112 0,
1113 0,
1114 BufferAllocatorRef::static_ref(),
1115 );
1116 builder.append_listview_array(middle.as_view(), &mut ctx)?;
1117 builder.append_listview_array(middle.as_view(), &mut ctx)?;
1119 let listview = builder.finish_into_listview();
1120
1121 assert_eq!(
1122 listview.elements().len(),
1123 12,
1124 "only the six referenced elements of each append should have landed",
1125 );
1126 assert!(
1127 listview.is_zero_copy_to_list(),
1128 "trimming an exact source keeps the result exact",
1129 );
1130
1131 let expected = ListArray::from_iter_slow::<u32, _>(
1132 (1..4).chain(1..4).map(|i| vec![2 * i, 2 * i + 1]),
1133 dtype,
1134 )?;
1135 assert_arrays_eq!(listview, expected, &mut ctx);
1136
1137 Ok(())
1138 }
1139
1140 #[test]
1141 fn test_extend_from_array_overlapping_listview() {
1142 let mut ctx = SESSION.create_execution_ctx();
1143 let dtype: Arc<DType> = Arc::new(I32.into());
1144
1145 let source = unsafe {
1150 ListViewArray::new_unchecked(
1151 buffer![10i32, 20, 30].into_array(),
1152 buffer![0u32, 1, 0].into_array(),
1153 buffer![2u8, 2, 1].into_array(),
1154 Validity::from_iter([true, false, true]),
1155 )
1156 };
1157 assert!(!source.is_zero_copy_to_list());
1158
1159 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1160 Arc::clone(&dtype),
1161 Nullable,
1162 0,
1163 0,
1164 BufferAllocatorRef::static_ref(),
1165 );
1166 builder
1167 .append_listview_array(source.as_view(), &mut ctx)
1168 .unwrap();
1169
1170 let listview = builder.finish_into_listview();
1171 assert_eq!(listview.len(), 3);
1172 assert!(!listview.is_zero_copy_to_list());
1174
1175 assert_arrays_eq!(
1176 listview.list_elements_at(0, &mut ctx).unwrap(),
1177 PrimitiveArray::from_iter([10i32, 20]),
1178 &mut ctx
1179 );
1180 assert!(
1181 !listview
1182 .validity()
1183 .vortex_expect("listview validity should be derivable")
1184 .execute_is_valid(1, &mut ctx)
1185 .unwrap()
1186 );
1187 assert_eq!(listview.size_at(1, &mut ctx), source.size_at(1, &mut ctx));
1189 assert_arrays_eq!(
1190 listview.list_elements_at(2, &mut ctx).unwrap(),
1191 PrimitiveArray::from_iter([10i32]),
1192 &mut ctx
1193 );
1194 let expected = ListArray::new(
1195 buffer![10i32, 20, 10].into_array(),
1196 buffer![0u32, 2, 2, 3].into_array(),
1197 Validity::from_iter([true, false, true]),
1198 &mut ctx,
1199 );
1200 assert_arrays_eq!(listview, expected, &mut ctx);
1201 }
1202
1203 #[test]
1204 fn test_error_append_null_to_non_nullable() {
1205 let dtype: Arc<DType> = Arc::new(I32.into());
1206 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1207 Arc::clone(&dtype),
1208 NonNullable,
1209 0,
1210 0,
1211 BufferAllocatorRef::static_ref(),
1212 );
1213
1214 let null_scalar = Scalar::null(DType::List(dtype, Nullable));
1216 let null_list = null_scalar.as_list();
1217
1218 let result = builder.append_value(null_list);
1220 assert!(result.is_err());
1221 assert!(
1222 result
1223 .unwrap_err()
1224 .to_string()
1225 .contains("null value to non-nullable")
1226 );
1227 }
1228
1229 #[test]
1230 fn test_append_array_as_list() {
1231 let dtype: Arc<DType> = Arc::new(I32.into());
1232 let mut ctx = SESSION.create_execution_ctx();
1233 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1234 Arc::clone(&dtype),
1235 NonNullable,
1236 20,
1237 10,
1238 BufferAllocatorRef::static_ref(),
1239 );
1240
1241 let arr1 = buffer![1i32, 2, 3].into_array();
1243 builder.append_array_as_list(&arr1, &mut ctx).unwrap();
1244
1245 builder
1247 .append_value(
1248 Scalar::list(
1249 Arc::clone(&dtype),
1250 vec![10i32.into(), 11i32.into()],
1251 NonNullable,
1252 )
1253 .as_list(),
1254 )
1255 .unwrap();
1256
1257 let arr2 = buffer![4i32, 5].into_array();
1259 builder.append_array_as_list(&arr2, &mut ctx).unwrap();
1260
1261 let arr3 = buffer![0i32; 0].into_array();
1263 builder.append_array_as_list(&arr3, &mut ctx).unwrap();
1264
1265 builder
1267 .append_value(Scalar::list_empty(Arc::clone(&dtype), NonNullable).as_list())
1268 .unwrap();
1269
1270 let listview = builder.finish_into_listview();
1271 assert_eq!(listview.len(), 5);
1272
1273 assert_arrays_eq!(
1275 listview.elements(),
1276 PrimitiveArray::from_iter([1i32, 2, 3, 10, 11, 4, 5]),
1277 &mut ctx
1278 );
1279
1280 assert_arrays_eq!(
1282 listview.offsets(),
1283 PrimitiveArray::from_iter([0u32, 3, 5, 7, 7]),
1284 &mut ctx
1285 );
1286
1287 assert_arrays_eq!(
1289 listview.sizes(),
1290 PrimitiveArray::from_iter([3u32, 2, 2, 0, 0]),
1291 &mut ctx
1292 );
1293
1294 let mut builder = ListViewBuilder::<u32, u32>::with_capacity_in(
1296 dtype,
1297 NonNullable,
1298 20,
1299 10,
1300 BufferAllocatorRef::static_ref(),
1301 );
1302 let wrong_dtype_arr = buffer![1i64, 2, 3].into_array();
1303 assert!(
1304 builder
1305 .append_array_as_list(&wrong_dtype_arr, &mut ctx)
1306 .is_err()
1307 );
1308 }
1309}