Skip to main content

vortex_array/builders/
list.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::any::Any;
5use std::sync::Arc;
6
7use num_traits::AsPrimitive;
8use vortex_buffer::BufferAllocatorRef;
9use vortex_error::VortexExpect;
10use vortex_error::VortexResult;
11use vortex_error::vortex_bail;
12use vortex_error::vortex_ensure_eq;
13use vortex_error::vortex_panic;
14
15use crate::ArrayRef;
16use crate::Canonical;
17use crate::ExecutionCtx;
18use crate::IntoArray;
19use crate::array::ArrayView;
20use crate::arrays::List;
21use crate::arrays::ListArray;
22use crate::arrays::ListView;
23use crate::arrays::ListViewArray;
24use crate::arrays::PrimitiveArray;
25use crate::arrays::list::ListArraySlotsExt;
26use crate::arrays::listview::ListViewArraySlotsExt;
27use crate::arrays::listview::ListViewRebuildMode;
28use crate::builders::ArrayBuilder;
29use crate::builders::ChildBuilder;
30use crate::builders::DEFAULT_BUILDER_CAPACITY;
31use crate::builders::PrimitiveBuilder;
32use crate::builders::ValidityBuilder;
33use crate::dtype::DType;
34use crate::dtype::IntegerPType;
35use crate::dtype::Nullability;
36use crate::dtype::Nullability::NonNullable;
37use crate::dtype::OffsetBuilderPType;
38use crate::match_each_integer_ptype;
39use crate::scalar::ListScalar;
40use crate::scalar::Scalar;
41
42/// The builder for building a [`ListArray`], parametrized by the [`OffsetBuilderPType`] of the
43/// `offsets` builder.
44pub struct ListBuilder<O: OffsetBuilderPType> {
45    /// The [`DType`] of the [`ListArray`]. This **must** be a [`DType::List`].
46    dtype: DType,
47
48    /// The builder for the underlying elements of the [`ListArray`].
49    elements_builder: ChildBuilder,
50
51    /// The builder for the `offsets` into the `elements` array.
52    offsets_builder: PrimitiveBuilder<O>,
53
54    /// The null map builder of the [`ListArray`].
55    nulls: ValidityBuilder,
56}
57
58impl<O: OffsetBuilderPType> ListBuilder<O> {
59    /// Creates a new `ListBuilder` with a capacity of [`DEFAULT_BUILDER_CAPACITY`].
60    #[deprecated(note = "use `new_in` with an explicit allocator")]
61    pub fn new(value_dtype: Arc<DType>, nullability: Nullability) -> Self {
62        Self::new_in(value_dtype, nullability, BufferAllocatorRef::static_ref())
63    }
64
65    /// Creates a new `ListBuilder` with the default capacity using `allocator`.
66    pub fn new_in(
67        value_dtype: Arc<DType>,
68        nullability: Nullability,
69        allocator: &BufferAllocatorRef,
70    ) -> Self {
71        Self::with_capacity_in(
72            value_dtype,
73            nullability,
74            // We arbitrarily choose 2 times the number of list scalars for the capacity of the
75            // elements builder since we cannot know this ahead of time.
76            DEFAULT_BUILDER_CAPACITY * 2,
77            DEFAULT_BUILDER_CAPACITY,
78            allocator,
79        )
80    }
81
82    /// Create a new [`ListArray`] builder with a with the given `capacity`, as well as an initial
83    /// capacity for the `elements` builder (since we cannot know that ahead of time solely based on
84    /// the outer array `capacity`).
85    ///
86    /// # Notes
87    ///
88    /// The number of offsets is one more than the length (# of list scalars) in the array.
89    #[deprecated(note = "use `with_capacity_in` with an explicit allocator")]
90    pub fn with_capacity(
91        value_dtype: Arc<DType>,
92        nullability: Nullability,
93        elements_capacity: usize,
94        capacity: usize,
95    ) -> Self {
96        Self::with_capacity_in(
97            value_dtype,
98            nullability,
99            elements_capacity,
100            capacity,
101            BufferAllocatorRef::static_ref(),
102        )
103    }
104
105    /// Creates a list builder with the given capacities using `allocator`.
106    pub fn with_capacity_in(
107        value_dtype: Arc<DType>,
108        nullability: Nullability,
109        elements_capacity: usize,
110        capacity: usize,
111        allocator: &BufferAllocatorRef,
112    ) -> Self {
113        let elements_builder =
114            ChildBuilder::with_capacity(value_dtype.as_ref(), elements_capacity, allocator);
115        let mut offsets_builder =
116            PrimitiveBuilder::<O>::with_capacity_in(NonNullable, capacity + 1, allocator);
117
118        // The first offset is always 0 and represents an empty list.
119        offsets_builder.append_zero();
120
121        Self {
122            elements_builder,
123            offsets_builder,
124            nulls: ValidityBuilder::new(capacity, allocator),
125            dtype: DType::List(value_dtype, nullability),
126        }
127    }
128
129    /// Appends an array as a single non-null list entry to the builder.
130    ///
131    /// The input `array` must have the same dtype as the element dtype of this list builder.
132    ///
133    /// Note that the list entry will be non-null but the elements themselves are allowed to be null
134    /// (only if the elements [`DType`] in nullable, of course).
135    pub fn append_array_as_list(
136        &mut self,
137        array: &ArrayRef,
138        ctx: &mut ExecutionCtx,
139    ) -> VortexResult<()> {
140        vortex_ensure_eq!(array.dtype(), self.element_dtype());
141
142        self.elements_builder.append_array(array, ctx)?;
143        self.nulls.append_non_null();
144        self.offsets_builder.append_value(
145            O::from_usize(self.elements_builder.len())
146                .vortex_expect("Failed to convert from usize to O"),
147        );
148
149        Ok(())
150    }
151
152    /// Appends a list `value` to the builder.
153    pub fn append_value(&mut self, value: ListScalar) -> VortexResult<()> {
154        match value.elements() {
155            None => {
156                if self.dtype.nullability() == NonNullable {
157                    vortex_bail!("Cannot append null value to non-nullable list");
158                }
159                self.append_null();
160            }
161            Some(elements) => {
162                for scalar in elements {
163                    // TODO(connor): This is slow, we should be able to append multiple values at
164                    // once, or the list scalar should hold an Array
165                    self.elements_builder.append_scalar(&scalar)?;
166                }
167
168                self.nulls.append_non_null();
169                self.offsets_builder.append_value(
170                    O::from_usize(self.elements_builder.len())
171                        .vortex_expect("Failed to convert from usize to O"),
172                );
173            }
174        }
175
176        Ok(())
177    }
178
179    /// Finishes the builder directly into a [`ListArray`].
180    pub fn finish_into_list(&mut self) -> ListArray {
181        assert_eq!(
182            self.offsets_builder.len(),
183            self.nulls.len() + 1,
184            "offsets length must be one more than nulls length."
185        );
186
187        // SAFETY: the builder appends non-negative, monotonically increasing offsets that end at
188        // the number of appended elements, and one validity bit per list.
189        unsafe {
190            ListArray::new_unchecked(
191                self.elements_builder.finish(),
192                self.offsets_builder.finish(),
193                self.nulls.finish_with_nullability(self.dtype.nullability()),
194            )
195        }
196    }
197
198    /// The [`DType`] of the inner elements. Note that this is **not** the same as the [`DType`] of
199    /// the outer `List`.
200    pub fn element_dtype(&self) -> &DType {
201        let DType::List(element_dtype, _) = &self.dtype else {
202            vortex_panic!("`ListBuilder` has an incorrect dtype: {}", self.dtype);
203        };
204
205        element_dtype
206    }
207
208    /// Appends the values of a [`List`]-encoded `array` to this builder.
209    ///
210    /// List encodings dispatch here through
211    /// [`match_each_list_builder!`](crate::match_each_list_builder) because the concrete list
212    /// builders are generic over their offset integer type, which cannot be named through a
213    /// `dyn ArrayBuilder`.
214    pub fn append_list_array(
215        &mut self,
216        array: ArrayView<'_, List>,
217        ctx: &mut ExecutionCtx,
218    ) -> VortexResult<()> {
219        if array.is_empty() {
220            return Ok(());
221        }
222
223        self.nulls.append_validity(array.validity()?, array.len());
224
225        let num_lists = array.len();
226        let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
227        match_each_integer_ptype!(offsets.ptype(), |OffsetType| {
228            let offsets = offsets.as_slice::<OffsetType>();
229            let first: usize = offsets[0].as_();
230            let last: usize = offsets[num_lists].as_();
231
232            // Lists in a `ListArray` are contiguous, so the referenced elements can be appended
233            // in bulk and the offsets rebased onto this builder's elements.
234            let elements_base = self.elements_builder.len();
235            if last > first {
236                self.elements_builder
237                    .append_array(&array.elements().slice(first..last)?, ctx)?;
238            }
239
240            self.offsets_builder.reserve_exact(num_lists);
241            let mut offsets_range = self.offsets_builder.uninit_range(num_lists);
242            for i in 0..num_lists {
243                let end: usize = offsets[i + 1].as_();
244                offsets_range.set_value(
245                    i,
246                    O::from_usize(end - first + elements_base)
247                        .vortex_expect("Failed to convert offset"),
248                );
249            }
250            // SAFETY: We have initialized all `num_lists` values, and since the `offsets` array is
251            // non-nullable, we are done.
252            unsafe { offsets_range.finish() };
253        });
254        Ok(())
255    }
256
257    /// Appends the values of a [`ListView`]-encoded `array` to this builder.
258    ///
259    /// See [`append_list_array`](Self::append_list_array); this is the same hook for the canonical
260    /// [`ListViewArray`] encoding.
261    ///
262    /// A `ListArray`'s offsets can only describe contiguous, in-order lists, so views laid out any
263    /// other way (overlapping, out of order, or with interior gaps) are flattened first.
264    pub fn append_listview_array(
265        &mut self,
266        array: ArrayView<'_, ListView>,
267        ctx: &mut ExecutionCtx,
268    ) -> VortexResult<()> {
269        if array.is_empty() {
270            return Ok(());
271        }
272
273        self.nulls.append_validity(array.validity()?, array.len());
274
275        // Flatten the views into the only layout `ListArray` offsets can express. This is a cheap
276        // clone when they already are laid out that way, and the flattened result keeps the
277        // original validity, so the null map appended above still describes it.
278        let array = array
279            .into_owned()
280            .rebuild(ListViewRebuildMode::MakeZeroCopyToList, ctx)?;
281        debug_assert!(array.is_zero_copy_to_list());
282
283        // Note that `ListViewArray` has `n` offsets and sizes, not `n+1` offsets like `ListArray`.
284        let elements = array.elements();
285        let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
286        let sizes = array.sizes().clone().execute::<PrimitiveArray>(ctx)?;
287
288        match_each_integer_ptype!(offsets.ptype(), |OffsetType| {
289            match_each_integer_ptype!(sizes.ptype(), |SizeType| {
290                extend_from_listview(
291                    self,
292                    elements,
293                    offsets.as_slice::<OffsetType>(),
294                    sizes.as_slice::<SizeType>(),
295                    ctx,
296                )?
297            })
298        });
299        Ok(())
300    }
301}
302
303/// Appends the lists of a zero-copy-to-list [`ListViewArray`] (`n` offsets and sizes) into a
304/// [`ListBuilder`], converting into the `ListArray` (`n + 1` offsets) layout.
305///
306/// The caller must have made `new_offsets` and `new_sizes` zero-copyable to a `ListArray`, so the
307/// lists they describe are contiguous and in order — which is the only layout `ListArray` offsets
308/// can express. That lets the referenced elements be appended in bulk, with the offsets rebased
309/// onto this builder's elements, instead of appending a slice per list.
310fn extend_from_listview<O, OffsetType, SizeType>(
311    builder: &mut ListBuilder<O>,
312    new_elements: &ArrayRef,
313    new_offsets: &[OffsetType],
314    new_sizes: &[SizeType],
315    ctx: &mut ExecutionCtx,
316) -> VortexResult<()>
317where
318    O: OffsetBuilderPType,
319    OffsetType: IntegerPType,
320    SizeType: IntegerPType,
321{
322    let num_lists = new_offsets.len();
323    debug_assert_eq!(num_lists, new_sizes.len());
324
325    // Leading and trailing unreferenced elements are allowed even in a zero-copy-to-list layout,
326    // so the referenced range is bounded by the first list's start and the last list's end.
327    let first: usize = new_offsets[0].as_();
328    let last: usize = new_offsets[num_lists - 1].as_() + new_sizes[num_lists - 1].as_();
329
330    let elements_base = builder.elements_builder.len();
331    if last > first {
332        builder
333            .elements_builder
334            .append_array(&new_elements.slice(first..last)?, ctx)?;
335    }
336
337    builder.offsets_builder.reserve_exact(num_lists);
338    let mut offsets_range = builder.offsets_builder.uninit_range(num_lists);
339    for i in 0..num_lists {
340        let end: usize = new_offsets[i].as_() + new_sizes[i].as_();
341        offsets_range.set_value(
342            i,
343            O::from_usize(end - first + elements_base).vortex_expect("Failed to convert offset"),
344        );
345    }
346
347    // SAFETY: We have initialized all `num_lists` values, and since the `offsets` array is
348    // non-nullable, we are done.
349    unsafe { offsets_range.finish() };
350    Ok(())
351}
352
353impl<O: OffsetBuilderPType> ArrayBuilder for ListBuilder<O> {
354    fn as_any(&self) -> &dyn Any {
355        self
356    }
357
358    fn as_any_mut(&mut self) -> &mut dyn Any {
359        self
360    }
361
362    fn dtype(&self) -> &DType {
363        &self.dtype
364    }
365
366    fn len(&self) -> usize {
367        self.nulls.len()
368    }
369
370    fn append_zeros(&mut self, n: usize) {
371        let curr_len = self.elements_builder.len();
372        for _ in 0..n {
373            self.offsets_builder.append_value(
374                O::from_usize(curr_len).vortex_expect("Failed to convert from usize to <O>"),
375            )
376        }
377        self.nulls.append_n_non_nulls(n);
378    }
379
380    unsafe fn append_nulls_unchecked(&mut self, n: usize) {
381        let curr_len = self.elements_builder.len();
382        for _ in 0..n {
383            // A list with a null element is can be a list with a zero-span offset and a validity
384            // bit set
385            self.offsets_builder.append_value(
386                O::from_usize(curr_len).vortex_expect("Failed to convert from usize to <O>"),
387            )
388        }
389        self.nulls.append_n_nulls(n);
390    }
391
392    fn append_scalar(&mut self, scalar: &Scalar) -> VortexResult<()> {
393        vortex_ensure_eq!(
394            scalar.dtype(),
395            self.dtype(),
396            "ListBuilder received a scalar with the wrong dtype"
397        );
398
399        self.append_value(scalar.as_list())
400    }
401
402    fn reserve_exact(&mut self, additional: usize) {
403        self.elements_builder.reserve_exact(additional);
404        self.offsets_builder.reserve_exact(additional);
405        self.nulls.reserve_exact(additional);
406    }
407
408    fn finish(&mut self) -> ArrayRef {
409        self.finish_into_list().into_array()
410    }
411
412    fn finish_into_canonical(&mut self, ctx: &mut ExecutionCtx) -> Canonical {
413        let listview = self
414            .finish()
415            .execute::<ListViewArray>(ctx)
416            .vortex_expect("list builder should canonicalize to listview");
417        Canonical::List(listview)
418    }
419}
420
421#[cfg(test)]
422mod tests {
423    use std::sync::Arc;
424    use std::sync::LazyLock;
425
426    use Nullability::NonNullable;
427    use Nullability::Nullable;
428    use vortex_buffer::BufferAllocatorRef;
429    use vortex_buffer::buffer;
430    use vortex_error::VortexExpect;
431    use vortex_error::VortexResult;
432    use vortex_session::VortexSession;
433
434    use crate::IntoArray;
435    use crate::arrays::ChunkedArray;
436    use crate::arrays::ListViewArray;
437    use crate::arrays::PrimitiveArray;
438    use crate::arrays::list::ListArraySlotsExt;
439    use crate::arrays::listview::ListViewArrayExt;
440    use crate::arrays::listview::ListViewArraySlotsExt;
441    use crate::assert_arrays_eq;
442    use crate::builders::ArrayBuilder;
443    use crate::builders::ListViewBuilder;
444    use crate::builders::builder_with_capacity_in;
445    use crate::builders::list::ListArray;
446    use crate::builders::list::ListBuilder;
447    use crate::dtype::DType;
448    use crate::dtype::Nullability;
449    use crate::dtype::OffsetBuilderPType;
450    use crate::dtype::PType::I32;
451    use crate::executor::VortexSessionExecute;
452    use crate::scalar::Scalar;
453    use crate::validity::Validity;
454
455    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
456
457    #[test]
458    fn test_empty() {
459        let mut builder = ListBuilder::<u32>::with_capacity_in(
460            Arc::new(I32.into()),
461            NonNullable,
462            0,
463            0,
464            BufferAllocatorRef::static_ref(),
465        );
466
467        let list = builder.finish();
468        assert_eq!(list.len(), 0);
469        assert_eq!(
470            list.dtype(),
471            &DType::List(Arc::new(I32.into()), NonNullable)
472        );
473    }
474
475    #[test]
476    fn test_values() {
477        let dtype: Arc<DType> = Arc::new(I32.into());
478        let mut builder = ListBuilder::<u32>::with_capacity_in(
479            Arc::clone(&dtype),
480            NonNullable,
481            0,
482            0,
483            BufferAllocatorRef::static_ref(),
484        );
485
486        builder
487            .append_value(
488                Scalar::list(
489                    Arc::clone(&dtype),
490                    vec![1i32.into(), 2i32.into(), 3i32.into()],
491                    NonNullable,
492                )
493                .as_list(),
494            )
495            .unwrap();
496
497        builder
498            .append_value(
499                Scalar::list(
500                    dtype,
501                    vec![4i32.into(), 5i32.into(), 6i32.into()],
502                    NonNullable,
503                )
504                .as_list(),
505            )
506            .unwrap();
507
508        let list = builder.finish();
509        assert_eq!(list.len(), 2);
510
511        let mut ctx = SESSION.create_execution_ctx();
512        let list_array = list.execute::<ListViewArray>(&mut ctx).unwrap();
513
514        assert_eq!(list_array.list_elements_at(0, &mut ctx).unwrap().len(), 3);
515        assert_eq!(list_array.list_elements_at(1, &mut ctx).unwrap().len(), 3);
516        let expected = ListArray::new(
517            buffer![1i32, 2, 3, 4, 5, 6].into_array(),
518            buffer![0u32, 3, 6].into_array(),
519            Validity::NonNullable,
520            &mut ctx,
521        );
522        assert_arrays_eq!(list_array, expected, &mut ctx);
523    }
524
525    #[test]
526    fn test_append_empty_list() {
527        let mut ctx = SESSION.create_execution_ctx();
528        let dtype: Arc<DType> = Arc::new(I32.into());
529        let mut builder = ListBuilder::<u32>::with_capacity_in(
530            Arc::clone(&dtype),
531            NonNullable,
532            0,
533            0,
534            BufferAllocatorRef::static_ref(),
535        );
536
537        assert!(
538            builder
539                .append_value(Scalar::list_empty(dtype, NonNullable).as_list())
540                .is_ok()
541        );
542        let expected = ListArray::new(
543            buffer![0i32; 0].into_array(),
544            buffer![0u32, 0].into_array(),
545            Validity::NonNullable,
546            &mut ctx,
547        );
548        assert_arrays_eq!(
549            builder.finish(),
550            expected,
551            &mut SESSION.create_execution_ctx()
552        );
553    }
554
555    #[test]
556    fn test_nullable_values() {
557        let dtype: Arc<DType> = Arc::new(I32.into());
558        let mut builder = ListBuilder::<u32>::with_capacity_in(
559            Arc::clone(&dtype),
560            Nullable,
561            0,
562            0,
563            BufferAllocatorRef::static_ref(),
564        );
565
566        builder
567            .append_value(
568                Scalar::list(
569                    Arc::clone(&dtype),
570                    vec![1i32.into(), 2i32.into(), 3i32.into()],
571                    NonNullable,
572                )
573                .as_list(),
574            )
575            .unwrap();
576
577        builder
578            .append_value(Scalar::list_empty(Arc::clone(&dtype), NonNullable).as_list())
579            .unwrap();
580
581        builder
582            .append_value(
583                Scalar::list(
584                    dtype,
585                    vec![4i32.into(), 5i32.into(), 6i32.into()],
586                    NonNullable,
587                )
588                .as_list(),
589            )
590            .unwrap();
591
592        let list = builder.finish();
593        assert_eq!(list.len(), 3);
594
595        let mut ctx = SESSION.create_execution_ctx();
596        let list_array = list.execute::<ListViewArray>(&mut ctx).unwrap();
597
598        assert_eq!(list_array.list_elements_at(0, &mut ctx).unwrap().len(), 3);
599        assert_eq!(list_array.list_elements_at(1, &mut ctx).unwrap().len(), 0);
600        assert_eq!(list_array.list_elements_at(2, &mut ctx).unwrap().len(), 3);
601        let expected = ListArray::new(
602            buffer![1i32, 2, 3, 4, 5, 6].into_array(),
603            buffer![0u32, 3, 3, 6].into_array(),
604            Validity::AllValid,
605            &mut ctx,
606        );
607        assert_arrays_eq!(list_array, expected, &mut ctx);
608    }
609
610    fn test_extend_builder_gen<O: OffsetBuilderPType>() {
611        let list = ListArray::from_iter_opt_slow::<O, _, _>(
612            [Some(vec![0, 1, 2]), None, Some(vec![4, 5])],
613            Arc::new(I32.into()),
614        )
615        .unwrap()
616        .into_array();
617        assert_eq!(list.len(), 3);
618
619        let mut ctx = SESSION.create_execution_ctx();
620
621        let mut builder = ListBuilder::<O>::with_capacity_in(
622            Arc::new(I32.into()),
623            Nullable,
624            18,
625            9,
626            BufferAllocatorRef::static_ref(),
627        );
628        list.append_to_builder(&mut builder, &mut ctx).unwrap();
629        list.append_to_builder(&mut builder, &mut ctx).unwrap();
630        list.slice(0..0)
631            .unwrap()
632            .append_to_builder(&mut builder, &mut ctx)
633            .unwrap();
634        list.slice(1..3)
635            .unwrap()
636            .append_to_builder(&mut builder, &mut ctx)
637            .unwrap();
638
639        let expected = ListArray::from_iter_opt_slow::<O, _, _>(
640            [
641                Some(vec![0, 1, 2]),
642                None,
643                Some(vec![4, 5]),
644                Some(vec![0, 1, 2]),
645                None,
646                Some(vec![4, 5]),
647                None,
648                Some(vec![4, 5]),
649            ],
650            Arc::new(DType::Primitive(I32, NonNullable)),
651        )
652        .unwrap()
653        .into_array()
654        .execute::<ListViewArray>(&mut ctx)
655        .unwrap();
656
657        let actual = builder.finish_into_canonical(&mut ctx).into_listview();
658
659        assert_arrays_eq!(actual.elements(), expected.elements(), &mut ctx);
660
661        assert_arrays_eq!(actual.offsets(), expected.offsets(), &mut ctx);
662
663        assert!(
664            actual
665                .validity()
666                .vortex_expect("list validity should be derivable")
667                .mask_eq(
668                    &expected
669                        .validity()
670                        .vortex_expect("list validity should be derivable"),
671                    actual.len(),
672                    &mut ctx,
673                )
674                .unwrap(),
675        );
676        let independent = ListArray::new(
677            buffer![0i32, 1, 2, 4, 5, 0, 1, 2, 4, 5, 4, 5].into_array(),
678            buffer![0u32, 3, 3, 5, 8, 8, 10, 10, 12].into_array(),
679            Validity::from_iter([true, false, true, true, false, true, false, true]),
680            &mut ctx,
681        );
682        assert_arrays_eq!(actual, independent, &mut ctx);
683    }
684
685    /// `append_to_builder` must handle any list builder kind without assuming the offset/size
686    /// integer types produced by `builder_with_capacity`. It appends a `List`-encoded array and a
687    /// `ListView`-encoded array into `ListViewBuilder`s and `ListBuilder`s with assorted (and
688    /// non-`u64`) offset/size types.
689    #[test]
690    fn test_append_to_builder_any_list_builder() -> VortexResult<()> {
691        let mut ctx = SESSION.create_execution_ctx();
692
693        let list = ListArray::from_iter_opt_slow::<u64, _, _>(
694            [Some(vec![0, 1, 2]), None, Some(vec![4, 5])],
695            Arc::new(I32.into()),
696        )?
697        .into_array();
698        let listview = list
699            .clone()
700            .execute::<ListViewArray>(&mut ctx)?
701            .into_array();
702        let elem_dtype = || Arc::new(I32.into());
703
704        // `builder_with_capacity` produces a `ListViewBuilder` for `DType::List`; appending the
705        // `List`-encoded array must dispatch into it instead of bailing.
706        let mut listview_builder =
707            builder_with_capacity_in(list.dtype(), list.len(), BufferAllocatorRef::static_ref());
708        list.append_to_builder(listview_builder.as_mut(), &mut ctx)?;
709        assert_arrays_eq!(listview_builder.finish(), list, &mut ctx);
710
711        // A `ListViewBuilder` with non-`u64` (including signed) offset and size types must work
712        // for both source encodings.
713        let mut lv_u64_u32 = ListViewBuilder::<u64, u32>::with_capacity_in(
714            elem_dtype(),
715            Nullable,
716            8,
717            4,
718            BufferAllocatorRef::static_ref(),
719        );
720        list.append_to_builder(&mut lv_u64_u32, &mut ctx)?;
721        assert_arrays_eq!(lv_u64_u32.finish(), list, &mut ctx);
722
723        let mut lv_i64_i32 = ListViewBuilder::<i64, i32>::with_capacity_in(
724            elem_dtype(),
725            Nullable,
726            8,
727            4,
728            BufferAllocatorRef::static_ref(),
729        );
730        list.append_to_builder(&mut lv_i64_i32, &mut ctx)?;
731        assert_arrays_eq!(lv_i64_i32.finish(), list, &mut ctx);
732
733        let mut lv_u32_u32 = ListViewBuilder::<u32, u32>::with_capacity_in(
734            elem_dtype(),
735            Nullable,
736            8,
737            4,
738            BufferAllocatorRef::static_ref(),
739        );
740        listview.append_to_builder(&mut lv_u32_u32, &mut ctx)?;
741        assert_arrays_eq!(lv_u32_u32.finish(), list, &mut ctx);
742
743        // Both source encodings appended into `ListBuilder`s with non-`u64` (including signed)
744        // offset types.
745        let mut list_builder = ListBuilder::<u32>::with_capacity_in(
746            elem_dtype(),
747            Nullable,
748            8,
749            4,
750            BufferAllocatorRef::static_ref(),
751        );
752        list.append_to_builder(&mut list_builder, &mut ctx)?;
753        assert_arrays_eq!(list_builder.finish(), list, &mut ctx);
754
755        let mut list_builder_i32 = ListBuilder::<i32>::with_capacity_in(
756            elem_dtype(),
757            Nullable,
758            8,
759            4,
760            BufferAllocatorRef::static_ref(),
761        );
762        listview.append_to_builder(&mut list_builder_i32, &mut ctx)?;
763        assert_arrays_eq!(list_builder_i32.finish(), list, &mut ctx);
764
765        Ok(())
766    }
767
768    #[test]
769    fn test_append_list_arrays_grow_builder() -> VortexResult<()> {
770        let mut ctx = SESSION.create_execution_ctx();
771        let dtype: Arc<DType> = Arc::new(I32.into());
772
773        // Enough lists to exceed the offsets capacity of a zero-capacity builder, so appending
774        // must grow the builder rather than panic in `uninit_range`.
775        let lists: Vec<Option<Vec<i32>>> =
776            (0..100).map(|i| (i % 10 != 0).then(|| vec![i])).collect();
777        let source = ListArray::from_iter_opt_slow::<u32, _, _>(lists.clone(), Arc::clone(&dtype))?;
778        let expected = ListArray::from_iter_opt_slow::<u32, _, _>(
779            lists.iter().cloned().chain(lists.iter().cloned()),
780            Arc::clone(&dtype),
781        )?;
782
783        // Appending twice checks growth from a non-empty builder and offset rebasing.
784        let mut builder = ListBuilder::<u32>::with_capacity_in(
785            Arc::clone(&dtype),
786            Nullable,
787            0,
788            0,
789            BufferAllocatorRef::static_ref(),
790        );
791        builder.append_list_array(source.as_view(), &mut ctx)?;
792        builder.append_list_array(source.as_view(), &mut ctx)?;
793        assert_arrays_eq!(builder.finish(), expected, &mut ctx);
794
795        let source_listview = source.into_array().execute::<ListViewArray>(&mut ctx)?;
796        let mut builder = ListBuilder::<u32>::with_capacity_in(
797            dtype,
798            Nullable,
799            0,
800            0,
801            BufferAllocatorRef::static_ref(),
802        );
803        builder.append_listview_array(source_listview.as_view(), &mut ctx)?;
804        builder.append_listview_array(source_listview.as_view(), &mut ctx)?;
805        assert_arrays_eq!(builder.finish(), expected, &mut ctx);
806
807        Ok(())
808    }
809
810    /// A `ListArray`'s offsets can only describe contiguous, in-order lists, so an overlapping
811    /// source has to be flattened before its elements can be appended in bulk. A sliced source,
812    /// meanwhile, keeps the layout it has and is appended from wherever its first list starts.
813    #[test]
814    fn test_append_listview_array_flattens_overlaps_and_skips_leading_elements() -> VortexResult<()>
815    {
816        let mut ctx = SESSION.create_execution_ctx();
817        let dtype: Arc<DType> = Arc::new(I32.into());
818
819        // Overlapping source, so not zero-copyable to a list:
820        // - List 0: [10, 20]
821        // - List 1: null (size is intentionally non-zero in the source metadata)
822        // - List 2: [10], sharing the elements list 0 already referenced
823        let overlapping = unsafe {
824            ListViewArray::new_unchecked(
825                buffer![10i32, 20, 30].into_array(),
826                buffer![0u32, 1, 0].into_array(),
827                buffer![2u8, 2, 1].into_array(),
828                Validity::from_iter([true, false, true]),
829            )
830        };
831        assert!(!overlapping.is_zero_copy_to_list());
832
833        // Zero-copyable source sliced past its first list, so its elements start at offset 2.
834        let sliced = unsafe {
835            ListViewArray::new_unchecked(
836                buffer![40i32, 50, 60, 70].into_array(),
837                buffer![0u32, 2].into_array(),
838                buffer![2u32, 2].into_array(),
839                Validity::AllValid,
840            )
841            .with_zero_copy_to_list(true)
842        }
843        .into_array()
844        .slice(1..2)?
845        .execute::<ListViewArray>(&mut ctx)?;
846
847        let mut builder = ListBuilder::<u32>::with_capacity_in(
848            dtype,
849            Nullable,
850            0,
851            0,
852            BufferAllocatorRef::static_ref(),
853        );
854        builder.append_listview_array(overlapping.as_view(), &mut ctx)?;
855        builder.append_listview_array(sliced.as_view(), &mut ctx)?;
856
857        let list = builder.finish_into_list();
858        assert_arrays_eq!(
859            list.elements(),
860            PrimitiveArray::from_iter([10i32, 20, 10, 60, 70]),
861            &mut ctx
862        );
863        assert_arrays_eq!(
864            list.offsets(),
865            PrimitiveArray::from_iter([0u32, 2, 2, 3, 5]),
866            &mut ctx
867        );
868
869        let expected = ListArray::new(
870            buffer![10i32, 20, 10, 60, 70].into_array(),
871            buffer![0u32, 2, 2, 3, 5].into_array(),
872            Validity::from_iter([true, false, true, true]),
873            &mut ctx,
874        );
875        assert_arrays_eq!(list, expected, &mut ctx);
876        Ok(())
877    }
878
879    #[test]
880    fn test_extend_builder() {
881        test_extend_builder_gen::<i32>();
882        test_extend_builder_gen::<i64>();
883
884        test_extend_builder_gen::<u32>();
885        test_extend_builder_gen::<u64>();
886    }
887
888    #[test]
889    pub fn test_array_with_gap() {
890        let mut ctx = SESSION.create_execution_ctx();
891        let one_trailing_unused_element = ListArray::try_new(
892            buffer![1, 2, 3, 4].into_array(),
893            buffer![0, 3].into_array(),
894            Validity::NonNullable,
895            &mut ctx,
896        )
897        .unwrap();
898
899        let second_array = ListArray::try_new(
900            buffer![5, 6].into_array(),
901            buffer![0, 2].into_array(),
902            Validity::NonNullable,
903            &mut ctx,
904        )
905        .unwrap();
906
907        let chunked_list = ChunkedArray::try_new(
908            vec![
909                one_trailing_unused_element.clone().into_array(),
910                second_array.clone().into_array(),
911            ],
912            DType::List(Arc::new(DType::Primitive(I32, NonNullable)), NonNullable),
913        );
914
915        let mut ctx = SESSION.create_execution_ctx();
916        let canon_values = chunked_list
917            .unwrap()
918            .as_array()
919            .clone()
920            .execute::<ListViewArray>(&mut ctx)
921            .unwrap();
922
923        assert_eq!(
924            one_trailing_unused_element
925                .execute_scalar(0, &mut SESSION.create_execution_ctx())
926                .unwrap(),
927            canon_values
928                .execute_scalar(0, &mut SESSION.create_execution_ctx())
929                .unwrap()
930        );
931        assert_eq!(
932            second_array
933                .execute_scalar(0, &mut SESSION.create_execution_ctx())
934                .unwrap(),
935            canon_values
936                .execute_scalar(1, &mut SESSION.create_execution_ctx())
937                .unwrap()
938        );
939    }
940
941    #[test]
942    fn test_append_scalar() {
943        let dtype: Arc<DType> = Arc::new(I32.into());
944        let mut builder = ListBuilder::<u64>::with_capacity_in(
945            Arc::clone(&dtype),
946            Nullable,
947            20,
948            10,
949            BufferAllocatorRef::static_ref(),
950        );
951
952        // Test appending a valid list.
953        let list_scalar1 =
954            Scalar::list(Arc::clone(&dtype), vec![1i32.into(), 2i32.into()], Nullable);
955        builder.append_scalar(&list_scalar1).unwrap();
956
957        // Test appending another list.
958        let list_scalar2 = Scalar::list(
959            Arc::clone(&dtype),
960            vec![3i32.into(), 4i32.into(), 5i32.into()],
961            Nullable,
962        );
963        builder.append_scalar(&list_scalar2).unwrap();
964
965        // Test appending null value.
966        let null_scalar = Scalar::null(DType::List(Arc::clone(&dtype), Nullable));
967        builder.append_scalar(&null_scalar).unwrap();
968
969        let array = builder.finish_into_list();
970        assert_eq!(array.len(), 3);
971
972        let mut ctx = SESSION.create_execution_ctx();
973
974        // Check actual values using scalar_at.
975
976        let scalar0 = array.execute_scalar(0, &mut ctx).unwrap();
977        let list0 = scalar0.as_list();
978        assert_eq!(list0.len(), 2);
979        if let Some(list0_items) = list0.elements() {
980            assert_eq!(list0_items[0].as_primitive().typed_value::<i32>(), Some(1));
981            assert_eq!(list0_items[1].as_primitive().typed_value::<i32>(), Some(2));
982        }
983
984        let scalar1 = array.execute_scalar(1, &mut ctx).unwrap();
985        let list1 = scalar1.as_list();
986        assert_eq!(list1.len(), 3);
987        if let Some(list1_items) = list1.elements() {
988            assert_eq!(list1_items[0].as_primitive().typed_value::<i32>(), Some(3));
989            assert_eq!(list1_items[1].as_primitive().typed_value::<i32>(), Some(4));
990            assert_eq!(list1_items[2].as_primitive().typed_value::<i32>(), Some(5));
991        }
992
993        let scalar2 = array.execute_scalar(2, &mut ctx).unwrap();
994        let list2 = scalar2.as_list();
995        assert!(list2.is_null()); // This should be null.
996
997        // Check validity.
998        assert!(
999            array
1000                .validity()
1001                .vortex_expect("list validity should be derivable")
1002                .execute_is_valid(0, &mut ctx)
1003                .unwrap()
1004        );
1005        assert!(
1006            array
1007                .validity()
1008                .vortex_expect("list validity should be derivable")
1009                .execute_is_valid(1, &mut ctx)
1010                .unwrap()
1011        );
1012        assert!(
1013            !array
1014                .validity()
1015                .vortex_expect("list validity should be derivable")
1016                .execute_is_valid(2, &mut ctx)
1017                .unwrap()
1018        );
1019
1020        // Test wrong dtype error.
1021        let mut builder = ListBuilder::<u64>::with_capacity_in(
1022            dtype,
1023            NonNullable,
1024            20,
1025            10,
1026            BufferAllocatorRef::static_ref(),
1027        );
1028        let wrong_scalar = Scalar::from(42i32);
1029        assert!(builder.append_scalar(&wrong_scalar).is_err());
1030    }
1031
1032    #[test]
1033    fn test_append_array_as_list() {
1034        let dtype: Arc<DType> = Arc::new(I32.into());
1035        let mut ctx = SESSION.create_execution_ctx();
1036        let mut builder = ListBuilder::<u32>::with_capacity_in(
1037            Arc::clone(&dtype),
1038            NonNullable,
1039            20,
1040            10,
1041            BufferAllocatorRef::static_ref(),
1042        );
1043
1044        // Append a primitive array as a single list entry.
1045        let arr1 = buffer![1i32, 2, 3].into_array();
1046        builder.append_array_as_list(&arr1, &mut ctx).unwrap();
1047
1048        // Interleave with a list scalar.
1049        builder
1050            .append_value(
1051                Scalar::list(
1052                    Arc::clone(&dtype),
1053                    vec![10i32.into(), 11i32.into()],
1054                    NonNullable,
1055                )
1056                .as_list(),
1057            )
1058            .unwrap();
1059
1060        // Append another primitive array as a single list entry.
1061        let arr2 = buffer![4i32, 5].into_array();
1062        builder.append_array_as_list(&arr2, &mut ctx).unwrap();
1063
1064        // Append an empty array as a single list entry (empty list).
1065        let arr3 = buffer![0i32; 0].into_array();
1066        builder.append_array_as_list(&arr3, &mut ctx).unwrap();
1067
1068        // Interleave with another list scalar (empty list).
1069        builder
1070            .append_value(Scalar::list_empty(Arc::clone(&dtype), NonNullable).as_list())
1071            .unwrap();
1072
1073        let list = builder.finish_into_list();
1074        assert_eq!(list.len(), 5);
1075
1076        // Verify elements array: [1, 2, 3, 10, 11, 4, 5].
1077        assert_arrays_eq!(
1078            list.elements(),
1079            PrimitiveArray::from_iter([1i32, 2, 3, 10, 11, 4, 5]),
1080            &mut ctx
1081        );
1082
1083        // Verify offsets array.
1084        assert_arrays_eq!(
1085            list.offsets(),
1086            PrimitiveArray::from_iter([0u32, 3, 5, 7, 7, 7]),
1087            &mut ctx
1088        );
1089
1090        // Test dtype mismatch error.
1091        let mut builder = ListBuilder::<u32>::with_capacity_in(
1092            dtype,
1093            NonNullable,
1094            20,
1095            10,
1096            BufferAllocatorRef::static_ref(),
1097        );
1098        let wrong_dtype_arr = buffer![1i64, 2, 3].into_array();
1099        assert!(
1100            builder
1101                .append_array_as_list(&wrong_dtype_arr, &mut ctx)
1102                .is_err()
1103        );
1104    }
1105}