Skip to main content

vortex_array/arrays/listview/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use 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    /// The `elements` data array, where each list scalar is a _slice_ of the `elements` array,
46    /// and each inner list element is a _scalar_ of the `elements` array.
47    #[slot(0)]
48    pub elements: ArrayRef,
49    /// The `offsets` array indicating the start position of each list in elements.
50    ///
51    /// Since we also store `sizes`, this `offsets` field is allowed to be stored out-of-order
52    /// (which is different from [`ListArray`](crate::arrays::ListArray)).
53    #[slot(1)]
54    pub offsets: ArrayRef,
55    /// The `sizes` array indicating the length of each list.
56    ///
57    /// This field is intended to be paired with a corresponding offset to determine the list
58    /// scalar we want to access.
59    #[slot(2)]
60    pub sizes: ArrayRef,
61    /// The validity bitmap indicating which list elements are non-null.
62    #[slot(3)]
63    pub validity: Option<ArrayRef>,
64}
65
66/// The canonical encoding for variable-length list arrays.
67///
68/// The `ListViewArray` encoding differs from [`ListArray`] in that it stores a child `sizes` array
69/// in addition to a child `offsets` array (which is the _only_ child in [`ListArray`]).
70///
71/// In the past, we used [`ListArray`] as the canonical encoding for [`DType::List`], but we have
72/// since migrated to `ListViewArray` for a few reasons:
73///
74/// - Enables better SIMD vectorization (no sequential dependency when reading `offsets`)
75/// - Allows out-of-order offsets for better compression (we can shuffle the buffers)
76/// - Supports different integer types for offsets vs sizes
77///
78/// It is worth mentioning that this encoding mirrors Apache Arrow's `ListView` array type, but does
79/// not exactly mirror the similar type found in DuckDB and Velox, which stores the pair of offset
80/// and size in a row-major fashion rather than column-major. More specifically, the row-major
81/// layout has a single child array with alternating offset and size next to each other.
82///
83/// We choose the column-major layout as it allows better compressability, as well as using
84/// different (logical) integer widths for our `offsets` and `sizes` buffers (note that the
85/// compressor will likely compress to a different bit-packed width, but this is speaking strictly
86/// about flexibility in the logcial type).
87///
88/// # Examples
89///
90/// ```
91/// # fn main() -> vortex_error::VortexResult<()> {
92/// # use vortex_array::arrays::{ListViewArray, PrimitiveArray};
93/// # use vortex_array::arrays::listview::ListViewArrayExt;
94/// # use vortex_array::validity::Validity;
95/// # use vortex_session::VortexSession;
96/// # use vortex_array::{IntoArray, VortexSessionExecute};
97/// # use vortex_buffer::buffer;
98/// # use std::sync::Arc;
99/// #
100/// // Create a list view array representing [[3, 4], [1], [2, 3]].
101/// // Note: Unlike `ListArray`, offsets don't need to be monotonic.
102///
103/// let elements = buffer![1i32, 2, 3, 4, 5].into_array();
104/// let offsets = buffer![2u32, 0, 1].into_array();  // Out-of-order offsets
105/// let sizes = buffer![2u32, 1, 2].into_array();  // The sizes cause overlaps
106///
107/// let mut ctx = VortexSession::empty().create_execution_ctx();
108/// let list_view = ListViewArray::new(
109///     elements.into_array(),
110///     offsets.into_array(),
111///     sizes.into_array(),
112///     Validity::NonNullable,
113///     &mut ctx,
114/// );
115///
116/// assert_eq!(list_view.len(), 3);
117///
118/// // Access individual lists
119/// let first_list = list_view.list_elements_at(0, &mut ctx)?;
120/// assert_eq!(first_list.len(), 2);
121/// // First list contains elements[2..4] = [3, 4]
122///
123/// let first_offset = list_view.offset_at(0, &mut ctx);
124/// let first_size = list_view.size_at(0, &mut ctx);
125/// assert_eq!(first_offset, 2);
126/// assert_eq!(first_size, 2);
127/// # Ok(())
128/// # }
129/// ```
130///
131/// [`ListArray`]: crate::arrays::ListArray
132#[derive(Clone, Debug)]
133pub struct ListViewData {
134    // TODO(connor)[ListView]: Add the n+1 memory allocation optimization.
135    /// A flag denoting if the array is zero-copyable* to a [`ListArray`](crate::arrays::ListArray).
136    ///
137    /// We use this information to help us more efficiently rebuild / compact our data.
138    ///
139    /// When this flag is true (indicating sorted offsets with no gaps and no overlaps and all
140    /// `offsets[i] + sizes[i]` are in order), conversions can bypass the very expensive rebuild
141    /// process which must rebuild the array from scratch.
142    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    /// See `ListViewArray::elements`
155    pub elements: ArrayRef,
156
157    /// See `ListViewArray::offsets`
158    pub offsets: ArrayRef,
159
160    /// See `ListViewArray::sizes`
161    pub sizes: ArrayRef,
162
163    /// See `ListViewArray::validity`
164    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    /// Creates a new `ListViewArray`.
185    ///
186    /// # Panics
187    ///
188    /// Panics if the provided components do not satisfy the invariants documented
189    /// in `ListViewArray::new_unchecked`.
190    pub fn new() -> Self {
191        Self {
192            is_zero_copy_to_list: false,
193        }
194    }
195
196    /// Constructs a new `ListViewArray`.
197    ///
198    /// # Errors
199    ///
200    /// Returns an error if the provided components do not satisfy the invariants documented
201    /// in `ListViewArray::new_unchecked`.
202    pub fn try_new() -> VortexResult<Self> {
203        Ok(Self::new())
204    }
205
206    /// Creates a new `ListViewArray` without validation.
207    ///
208    /// This unsafe function does not check the validity of the data. Prefer calling [`new()`] or
209    /// [`try_new()`] over this function, as they will check the validity of the data.
210    ///
211    /// [`ListArray`]: crate::arrays::ListArray
212    /// [`new()`]: Self::new
213    /// [`try_new()`]: Self::try_new
214    ///
215    /// # Safety
216    ///
217    /// The caller must ensure all of the following invariants are satisfied:
218    ///
219    /// - `offsets` and `sizes` must be non-nullable integer arrays.
220    /// - `offsets` and `sizes` must have the same length.
221    /// - Size integer width must be smaller than or equal to offset type (to prevent overflow).
222    /// - For each `i`, `offsets[i] + sizes[i]` must not overflow and must be `<= elements.len()`
223    ///   (even if the corresponding view is defined as null by the validity array).
224    /// - If validity is an array, its length must equal `offsets.len()`.
225    pub unsafe fn new_unchecked() -> Self {
226        Self::new()
227    }
228
229    /// Validates the components that would be used to create a `ListViewArray`.
230    pub fn validate(
231        elements: &ArrayRef,
232        offsets: &ArrayRef,
233        sizes: &ArrayRef,
234        validity: &Validity,
235        ctx: &mut ExecutionCtx,
236    ) -> VortexResult<()> {
237        // Check that offsets and sizes are integer arrays and non-nullable.
238        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        // Check that they have the same length.
250        vortex_ensure_eq!(
251            offsets.len(),
252            sizes.len(),
253            "offsets and sizes must have the same length",
254        );
255
256        // If a validity array is present, it must be the same length as the `ListViewArray`.
257        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        // Skip host-only validation when offsets/sizes are not host-resident.
266        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            // Offsets and sizes are non-negative; reinterpret to unsigned to dispatch over 4 widths
270            // each (4x4 instead of 8x8). This is a read-only validation, so result types are moot.
271            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            // Validate the `offsets` and `sizes` arrays.
277            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    /// Sets whether this `ListViewArray` is zero-copyable to a [`ListArray`].
295    ///
296    /// This is an optimization flag that enables more efficient conversion to [`ListArray`] without
297    /// needing to copy or reorganize the data.
298    ///
299    /// [`ListArray`]: crate::arrays::ListArray
300    ///
301    /// # Safety
302    ///
303    /// When setting `is_zctl` to `true`, the caller must ensure that the `ListViewArray` is
304    /// actually zero-copyable to a [`ListArray`]. This means:
305    ///
306    /// - Offsets must be sorted (but not strictly sorted, zero-length lists are allowed).
307    /// - `offsets[i] + sizes[i] == offsets[i + 1]` for all `i`.
308    /// - No gaps in elements between first and last referenced elements.
309    /// - No overlapping list views (each element referenced at most once).
310    ///
311    /// Note that leading and trailing unreferenced elements **ARE** allowed.
312    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    /// Returns true if the `ListViewArray` is zero-copyable to a
318    /// [`ListArray`](crate::arrays::ListArray).
319    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
330/// Walks parallel `(offset, size)` slices and sets each range `[offset, offset + size]` in `buf`.
331///
332/// **Preconditions**
333///
334/// `offsets` and `sizes` must be the same length (which is always the case in valid `ListViewArray`s).
335fn 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    /// Returns a [`Mask`] of length `elements.len()` where each bit is set iff that
416    /// position in `elements` is referenced by at least one view. Caller must ensure `elements`
417    /// is non-empty.
418    ///
419    /// Walks every `(offset, size)` pair, canonicalizes both `offsets` and `sizes`,
420    /// and allocates a `BitBuffer` of length `elements.len()`, so it is extremely costly.
421    ///
422    /// **Preconditions**
423    ///
424    /// `self.elements()` must be non-empty.
425    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        // Offsets/sizes are non-negative; reinterpret to unsigned (4x4 instead of 8x8).
435        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    /// Exact fraction of `elements` referenced by some view, in `[0.0, 1.0]`. Extremely costly.
453    ///
454    /// Returns `Ok(1.0)` when `elements` is empty instead of dividing by 0.
455    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    /// Upper-bound estimate of [`compute_density`](Self::compute_density) via
474    /// `sum(sizes) / elements.len()`, clamped to `[0.0, 1.0]`.
475    ///
476    /// Exact for non-overlapping views, but overcounts when multiple views share the same elements.
477    ///
478    /// Returns `Ok(1.0)` when `elements` is empty instead of dividing by 0.
479    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        // compute_stat short-circuits on a cached exact Sum and otherwise computes
491        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        // if the same elements are referenced more than once the estimate may be
500        // greater than 1.0, so clamp
501        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    /// Returns the half-open range `[start, end)` of `elements` indices referenced by any view:
509    /// the minimum offset and the maximum `offset + size`. Elements outside this range are
510    /// unreferenced leading or trailing slack that a
511    /// [`TrimElements`](super::ListViewRebuildMode::TrimElements) rebuild would reclaim.
512    ///
513    /// For **zero-copy-to-list** arrays this is `O(1)`: views are sorted and non-overlapping with
514    /// no interior gaps, so the bounds are exactly `[first_offset, last_offset + last_size)`.
515    /// Otherwise it computes min/max statistics over `offsets` and `offsets + sizes`.
516    ///
517    /// # Preconditions
518    ///
519    /// The array must contain at least one list (`len() > 0`).
520    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        // Cast offsets and sizes to the widest integer type so that `offset + size` cannot overflow
540        // the narrower input width.
541        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    /// Creates a new `ListViewArray`.
566    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    /// Constructs a new `ListViewArray`.
583    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    /// Creates a new `ListViewArray` without validation.
601    ///
602    /// # Safety
603    ///
604    /// See [`ListViewData::new_unchecked`].
605    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    /// Mark whether this list view can be zero-copy converted to a list.
619    ///
620    /// # Safety
621    ///
622    /// See [`ListViewData::with_zero_copy_to_list`].
623    pub unsafe fn with_zero_copy_to_list(self, is_zctl: bool) -> Self {
624        // The flag is only checked when the offsets and sizes are canonical and host-resident,
625        // since validation never executes them.
626        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
668/// Helper function to validate `offsets` and `sizes` with specific types.
669fn 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        // Check for overflow when adding offset + size.
697        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
719/// Helper function to validate if the `ListViewArray` components are actually zero-copyable to
720/// [`ListArray`](crate::arrays::ListArray).
721fn validate_zctl(
722    elements: &ArrayRef,
723    offsets_primitive: PrimitiveArray,
724    sizes_primitive: PrimitiveArray,
725) -> VortexResult<()> {
726    // Offsets must be sorted (but not strictly sorted, zero-length lists are allowed), even
727    // if there are null views.
728    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    // Validate that offset[i] + size[i] <= offset[i+1] for all items
734    // This ensures views are non-overlapping and properly ordered for zero-copy-to-list
735    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            // Check that this view starts at or after the previous view ended
747            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            // Update max_end for the next iteration
757            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    // Offsets/sizes are non-negative; reinterpret to unsigned (4x4 instead of 8x8).
769    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    // Check that offset + size values are monotonic (no overlaps)
774    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    // TODO(connor)[ListView]: Making this allocation is expensive, but the more efficient
784    // implementation would be even more complicated than this. We could use a bit buffer denoting
785    // if positions in `elements` are used, and then additionally store a separate flag that tells
786    // us if a position is used more than once.
787    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        // Note that we ignore nulls here, as the "null" view metadata must still maintain the same
798        // invariants as non-null views, even for a `bool` information.
799        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    // Allow leading and trailing unreferenced elements, but not gaps in the middle.
815    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}