Skip to main content

vortex_array/arrays/list/
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_error::VortexExpect;
10use vortex_error::VortexResult;
11use vortex_error::vortex_bail;
12use vortex_error::vortex_ensure;
13use vortex_error::vortex_ensure_eq;
14use vortex_error::vortex_panic;
15
16use crate::ArrayRef;
17use crate::ArraySlots;
18use crate::Canonical;
19use crate::ExecutionCtx;
20use crate::IntoArray;
21use crate::aggregate_fn::NumericalAggregateOpts;
22use crate::aggregate_fn::fns::min_max::min_max;
23use crate::array::Array;
24use crate::array::ArrayParts;
25use crate::array::TypedArrayRef;
26use crate::array::child_to_validity;
27use crate::array::validity_to_child;
28use crate::array_slots;
29use crate::arrays::ConstantArray;
30use crate::arrays::List;
31use crate::arrays::ListArray;
32use crate::arrays::Primitive;
33use crate::builtins::ArrayBuiltins;
34use crate::dtype::DType;
35use crate::dtype::NativePType;
36use crate::match_each_integer_ptype;
37use crate::match_each_native_ptype;
38use crate::scalar_fn::fns::operators::Operator;
39use crate::validity::Validity;
40
41#[array_slots(List)]
42pub struct ListSlots {
43    /// The elements data array containing all list elements concatenated together.
44    #[slot(0)]
45    pub elements: ArrayRef,
46    /// The offsets array defining the start/end of each list within the elements array.
47    #[slot(1)]
48    pub offsets: ArrayRef,
49    /// The validity bitmap indicating which list elements are non-null.
50    #[slot(2)]
51    pub validity: Option<ArrayRef>,
52}
53
54/// A list array that stores variable-length lists of elements, similar to `Vec<Vec<T>>`.
55///
56/// This mirrors the Apache Arrow List array encoding and provides efficient storage
57/// for nested data where each row contains a list of elements of the same type.
58///
59/// ## Data Layout
60///
61/// The list array uses an offset-based encoding:
62/// - **Elements array**: A flat array containing all list elements concatenated together
63/// - **Offsets array**: Integer array where `offsets[i]` is an (inclusive) start index into
64///   the **elements** and `offsets[i+1]` is the (exclusive) stop index for the `i`th list.
65/// - **Validity**: Optional mask indicating which lists are null
66///
67/// This allows for excellent cascading compression of the elements and offsets, as similar values
68/// are clustered together and the offsets have a predictable pattern and small deltas between
69/// consecutive elements.
70///
71/// ## Offset Semantics
72///
73/// - Offsets must be non-nullable integers (i32, i64, etc.)
74/// - Offsets array has length `n+1` where `n` is the number of lists
75/// - List `i` contains elements from `elements[offsets[i]..offsets[i+1]]`
76/// - Offsets must be monotonically increasing
77///
78/// # Examples
79///
80/// ```
81/// use vortex_array::arrays::{ListArray, PrimitiveArray};
82/// use vortex_array::arrays::list::ListArrayExt;
83/// use vortex_array::validity::Validity;
84/// use vortex_session::VortexSession;
85/// use vortex_array::{IntoArray, VortexSessionExecute};
86/// use vortex_buffer::buffer;
87/// use std::sync::Arc;
88///
89/// // Create a list array representing [[1, 2], [3, 4, 5], []]
90/// let elements = buffer![1i32, 2, 3, 4, 5].into_array();
91/// let offsets = buffer![0u32, 2, 5, 5].into_array(); // 3 lists
92///
93/// let mut ctx = VortexSession::empty().create_execution_ctx();
94/// let list_array = ListArray::try_new(
95///     elements.into_array(),
96///     offsets.into_array(),
97///     Validity::NonNullable,
98///     &mut ctx,
99/// ).unwrap();
100///
101/// assert_eq!(list_array.len(), 3);
102///
103/// // Access individual lists
104/// let first_list = list_array.list_elements_at(0, &mut ctx).unwrap();
105/// assert_eq!(first_list.len(), 2); // [1, 2]
106///
107/// let third_list = list_array.list_elements_at(2, &mut ctx).unwrap();
108/// assert!(third_list.is_empty()); // []
109/// ```
110#[derive(Clone, Debug, Default)]
111pub struct ListData;
112
113impl Display for ListData {
114    fn fmt(&self, _f: &mut Formatter<'_>) -> std::fmt::Result {
115        Ok(())
116    }
117}
118
119pub struct ListDataParts {
120    pub elements: ArrayRef,
121    pub offsets: ArrayRef,
122    pub validity: Validity,
123    pub dtype: DType,
124}
125
126impl ListData {
127    pub(crate) fn make_slots(
128        elements: &ArrayRef,
129        offsets: &ArrayRef,
130        validity: &Validity,
131        len: usize,
132    ) -> ArraySlots {
133        ListSlots {
134            elements: elements.clone(),
135            offsets: offsets.clone(),
136            validity: validity_to_child(validity, len),
137        }
138        .into_slots()
139    }
140
141    /// Creates a new `ListArray`.
142    ///
143    /// # Panics
144    ///
145    /// Panics if the provided components do not satisfy the invariants documented
146    /// in `ListArray::new_unchecked`.
147    pub fn build(
148        elements: ArrayRef,
149        offsets: ArrayRef,
150        validity: Validity,
151        ctx: &mut ExecutionCtx,
152    ) -> Self {
153        Self::try_build(elements, offsets, validity, ctx).vortex_expect("ListArray new")
154    }
155
156    /// Constructs a new `ListArray`.
157    ///
158    /// See `ListArray::new_unchecked` for more information.
159    ///
160    /// # Errors
161    ///
162    /// Returns an error if the provided components do not satisfy the invariants documented in
163    /// `ListArray::new_unchecked`.
164    pub(crate) fn try_build(
165        elements: ArrayRef,
166        offsets: ArrayRef,
167        validity: Validity,
168        ctx: &mut ExecutionCtx,
169    ) -> VortexResult<Self> {
170        Self::validate(&elements, &offsets, &validity, ctx)?;
171
172        // SAFETY: validate ensures all invariants are met.
173        Ok(unsafe { Self::new_unchecked() })
174    }
175
176    /// Creates a new `ListArray` without validation from these components:
177    ///
178    /// * `elements` is a flat array containing all list elements concatenated.
179    /// * `offsets` is an integer array where `offsets[i]` is the start index for list `i`.
180    /// * `validity` holds the null values.
181    ///
182    /// # Safety
183    ///
184    /// The caller must ensure all of the following invariants are satisfied:
185    ///
186    /// - Offsets must be a non-nullable integer array.
187    /// - Offsets must have at least one element (even for empty lists, it should contain \[0\]).
188    /// - Offsets must be sorted (monotonically increasing).
189    /// - All offset values must be non-negative.
190    /// - The maximum offset must not exceed `elements.len()`.
191    /// - If validity is an array, its length must equal `offsets.len() - 1`.
192    pub unsafe fn new_unchecked() -> Self {
193        Self
194    }
195
196    /// Validates the components that would be used to create a `ListArray`.
197    ///
198    /// This function checks all the invariants required by `ListArray::new_unchecked`.
199    pub fn validate(
200        elements: &ArrayRef,
201        offsets: &ArrayRef,
202        validity: &Validity,
203        ctx: &mut ExecutionCtx,
204    ) -> VortexResult<()> {
205        // Offsets must have at least one element
206        vortex_ensure!(
207            !offsets.is_empty(),
208            "Offsets must have at least one element, [0] for an empty list"
209        );
210
211        // Offsets must be of integer type, and cannot go lower than 0.
212        vortex_ensure!(
213            offsets.dtype().is_int() && !offsets.dtype().is_nullable(),
214            "offsets have invalid type {}",
215            offsets.dtype()
216        );
217
218        // We can safely unwrap the DType as primitive now
219        let offsets_ptype = offsets.dtype().as_ptype();
220
221        // Offsets must be sorted (but not strictly sorted, zero-length lists are allowed)
222        if let Some(is_sorted) = offsets.statistics().compute_is_sorted(ctx) {
223            vortex_ensure!(is_sorted, "offsets must be sorted");
224        } else {
225            vortex_bail!("offsets must report is_sorted statistic");
226        }
227
228        // Validate that offsets min is non-negative, and max does not exceed the length of
229        // the elements array.
230        if let Some(min_max) = min_max(offsets, ctx, NumericalAggregateOpts::default())? {
231            match_each_integer_ptype!(offsets_ptype, |P| {
232                #[allow(clippy::absurd_extreme_comparisons, unused_comparisons)]
233                {
234                    let max = min_max
235                        .max
236                        .as_primitive()
237                        .as_::<P>()
238                        .vortex_expect("offsets type must fit offsets values");
239                    let min = min_max
240                        .min
241                        .as_primitive()
242                        .as_::<P>()
243                        .vortex_expect("offsets type must fit offsets values");
244
245                    vortex_ensure!(
246                        min >= 0,
247                        "offsets minimum {min} outside valid range [0, {max}]"
248                    );
249
250                    vortex_ensure!(
251                        max <= P::try_from(elements.len()).unwrap_or_else(|_| vortex_panic!(
252                            "Offsets type {} must be able to fit elements length {}",
253                            <P as NativePType>::PTYPE,
254                            elements.len()
255                        )),
256                        "Max offset {max} is beyond the length of the elements array {}",
257                        elements.len()
258                    );
259                }
260            })
261        } else {
262            // TODO(aduffy): fallback to slower validation pathway?
263            vortex_bail!(
264                "offsets array with encoding {} must support min_max compute function",
265                offsets.encoding_id()
266            );
267        };
268
269        // If a validity array is present, it must be the same length as the ListArray
270        if let Some(validity_len) = validity.maybe_len() {
271            vortex_ensure_eq!(
272                validity_len,
273                offsets.len() - 1,
274                "validity length does not match array size",
275            );
276        }
277
278        Ok(())
279    }
280    // TODO(connor)[ListView]: Create 2 functions `reset_offsets` and `recursive_reset_offsets`,
281    // where `reset_offsets` is infallible.
282    // Also, `reset_offsets` can be made more efficient by replacing `sub_scalar` with a match on
283    // the offset type and manual subtraction.
284}
285
286pub trait ListArrayExt: ListArraySlotsExt {
287    fn nullability(&self) -> crate::dtype::Nullability {
288        match self.dtype() {
289            DType::List(_, nullability) => *nullability,
290            _ => unreachable!("ListArrayExt requires a list dtype"),
291        }
292    }
293
294    fn list_validity(&self) -> Validity {
295        child_to_validity(
296            self.slots()[ListSlots::VALIDITY].as_ref(),
297            self.nullability(),
298        )
299    }
300
301    fn offset_at(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
302        vortex_ensure!(
303            index <= self.len(),
304            "Index {index} out of bounds 0..={}",
305            self.len()
306        );
307
308        if let Some(p) = self.offsets().as_opt::<Primitive>() {
309            Ok(match_each_native_ptype!(p.ptype(), |P| {
310                p.as_slice::<P>()[index].as_()
311            }))
312        } else {
313            self.offsets()
314                .execute_scalar(index, ctx)?
315                .as_primitive()
316                .as_::<usize>()
317                .ok_or_else(|| vortex_error::vortex_err!("offset value does not fit in usize"))
318        }
319    }
320
321    fn list_elements_at(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
322        let start = self.offset_at(index, ctx)?;
323        let end = self.offset_at(index + 1, ctx)?;
324        self.elements().slice(start..end)
325    }
326
327    fn sliced_elements(&self, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
328        let start = self.offset_at(0, ctx)?;
329        let end = self.offset_at(self.len(), ctx)?;
330        self.elements().slice(start..end)
331    }
332
333    fn element_dtype(&self) -> &DType {
334        self.elements().dtype()
335    }
336
337    fn reset_offsets(&self, recurse: bool, ctx: &mut ExecutionCtx) -> VortexResult<Array<List>> {
338        let mut elements = self.sliced_elements(ctx)?;
339        if recurse && elements.is_canonical() {
340            let compacted = elements
341                .execute::<Canonical>(ctx)?
342                .compact(ctx)?
343                .into_array();
344            elements = compacted;
345        } else if recurse && let Some(child_list_array) = elements.as_opt::<List>() {
346            elements = child_list_array
347                .into_owned()
348                .reset_offsets(recurse, ctx)?
349                .into_array();
350        }
351
352        let offsets = self.offsets();
353        let first_offset = offsets.execute_scalar(0, ctx)?;
354        let adjusted_offsets = if first_offset.is_zero() == Some(true) {
355            offsets.clone()
356        } else {
357            offsets.clone().binary(
358                ConstantArray::new(first_offset, offsets.len()).into_array(),
359                Operator::Sub,
360            )?
361        };
362
363        // SAFETY: By resetting the offsets we simply "shift" everything left and discard trailing garbage, so all invariants remain the same.
364        Ok(unsafe { ListArray::new_unchecked(elements, adjusted_offsets, self.list_validity()) })
365    }
366}
367impl<T: TypedArrayRef<List>> ListArrayExt for T {}
368
369impl Array<List> {
370    /// Creates a new `ListArray`.
371    pub fn new(
372        elements: ArrayRef,
373        offsets: ArrayRef,
374        validity: Validity,
375        ctx: &mut ExecutionCtx,
376    ) -> Self {
377        let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
378        let len = offsets.len().saturating_sub(1);
379        let slots = ListData::make_slots(&elements, &offsets, &validity, len);
380        let data = ListData::build(elements, offsets, validity, ctx);
381        unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) }
382    }
383
384    /// Constructs a new `ListArray`.
385    pub fn try_new(
386        elements: ArrayRef,
387        offsets: ArrayRef,
388        validity: Validity,
389        ctx: &mut ExecutionCtx,
390    ) -> VortexResult<Self> {
391        let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
392        let len = offsets.len().saturating_sub(1);
393        let slots = ListData::make_slots(&elements, &offsets, &validity, len);
394        let data = ListData::try_build(elements, offsets, validity, ctx)?;
395        Ok(unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) })
396    }
397
398    /// Creates a new `ListArray` without validation.
399    ///
400    /// # Safety
401    ///
402    /// See [`ListData::new_unchecked`].
403    pub unsafe fn new_unchecked(elements: ArrayRef, offsets: ArrayRef, validity: Validity) -> Self {
404        let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
405        let len = offsets.len().saturating_sub(1);
406        let slots = ListData::make_slots(&elements, &offsets, &validity, len);
407        let data = unsafe { ListData::new_unchecked() };
408        unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) }
409    }
410
411    pub fn into_data_parts(self) -> ListDataParts {
412        let dtype = self.dtype().clone();
413        let elements = self.slots()[ListSlots::ELEMENTS]
414            .clone()
415            .vortex_expect("ListArray elements slot");
416        let offsets = self.slots()[ListSlots::OFFSETS]
417            .clone()
418            .vortex_expect("ListArray offsets slot");
419        let validity = self.list_validity();
420        ListDataParts {
421            elements,
422            offsets,
423            validity,
424            dtype,
425        }
426    }
427}