Skip to main content

astrs_data/array/
list.rs

1//! [`ListArray`] — a column whose every value is a variable-length run of
2//! child values.
3//!
4//! # Layout
5//!
6//! ```text
7//!   offsets  [o0, o1, o2, …]      len + 1 entries into the child array
8//!   values   ├─ list 0 ─┼─ list 1 ─┼ …    one flat child array
9//!   validity  1          0                optional, one bit per list
10//! ```
11//!
12//! The child is itself an [`ArrayRef`], so lists nest arbitrarily: a
13//! `List(List(Float32))` is a list array whose child is a list array whose
14//! child is a `Float32` column. `value(i)` returns a *slice* of the child
15//! array, which is an `Arc` clone plus a window adjustment — no copying.
16//!
17//! Blueprint §6.1 keeps only 32-bit offsets in the P0 set (there is no
18//! `LargeList`), so this type is not generic over the offset width.
19//!
20//! ```
21//! use astrs_data::array::{Array, Int32Array, IntoArrayRef, ListArray};
22//! use astrs_data::{DataType, Field, ScalarBuffer};
23//!
24//! let child = Int32Array::from_values([1, 2, 3, 4, 5]).into_array_ref();
25//! let lists = ListArray::try_new(
26//!     Field::new("item", DataType::Int32, false),
27//!     ScalarBuffer::from_slice(&[0, 2, 2, 5]),
28//!     child,
29//!     None,
30//! )?;
31//!
32//! assert_eq!(lists.len(), 3);
33//! assert_eq!(lists.value_length(0), Some(2));
34//! assert_eq!(lists.value_length(1), Some(0), "an empty list is not a null list");
35//! assert_eq!(lists.get(2).map(|v| v.len()), Some(3));
36//! # Ok::<(), astrs_data::DataError>(())
37//! ```
38
39use std::any::Any;
40use std::fmt;
41use std::sync::Arc;
42
43use crate::array::iter::{ArrayAccessor, ArrayIter};
44use crate::array::offset::validate_offsets;
45use crate::array::{
46    Array, ArrayRef, check_validity, clamp_window, new_empty_array, slice_array, validity_eq,
47};
48use crate::buffer::{Bitmap, ScalarBuffer};
49use crate::datatype::{DataType, Field};
50use crate::error::{DataError, Result};
51use crate::sealed::Sealed;
52
53/// A column of variable-length lists over a shared child array.
54#[derive(Clone)]
55pub struct ListArray {
56    /// Always `DataType::List(field)`.
57    data_type: DataType,
58    /// `len + 1` non-decreasing offsets into `values`.
59    offsets: ScalarBuffer<i32>,
60    /// The flat child array every list points into.
61    values: ArrayRef,
62    /// Validity, or `None` when every list is valid.
63    validity: Option<Bitmap>,
64}
65
66impl ListArray {
67    /// Builds a list array from its child, offsets and validity.
68    ///
69    /// # Errors
70    ///
71    /// * The offset errors listed on [`validate_offsets`].
72    /// * [`DataError::TypeMismatch`] when the child array's type differs from
73    ///   the field's.
74    /// * [`DataError::ValidityLengthMismatch`] when the bitmap length is wrong.
75    pub fn try_new(
76        field: Field,
77        offsets: ScalarBuffer<i32>,
78        values: ArrayRef,
79        validity: Option<Bitmap>,
80    ) -> Result<Self> {
81        if field.data_type() != values.data_type() {
82            return Err(DataError::type_mismatch(
83                field.data_type().clone(),
84                values.data_type().clone(),
85            ));
86        }
87        let len = validate_offsets(offsets.as_slice(), values.len())?;
88        check_validity(validity.as_ref(), len)?;
89        Ok(Self {
90            data_type: DataType::list(field),
91            offsets,
92            values,
93            validity,
94        })
95    }
96
97    /// Builds a list array from a child and per-list lengths.
98    ///
99    /// The lengths must sum to the child's length.
100    ///
101    /// # Errors
102    ///
103    /// * [`DataError::TypeMismatch`] when the child's type differs from the
104    ///   field's.
105    /// * [`DataError::ChildLengthMismatch`] when the lengths do not add up.
106    ///
107    /// ```
108    /// use astrs_data::array::{Array, Int32Array, IntoArrayRef, ListArray};
109    /// use astrs_data::{DataType, Field};
110    ///
111    /// let child = Int32Array::from_values([1, 2, 3]).into_array_ref();
112    /// let lists = ListArray::try_from_lengths(
113    ///     Field::new("item", DataType::Int32, false),
114    ///     [2, 1],
115    ///     child,
116    /// )?;
117    /// assert_eq!(lists.len(), 2);
118    /// # Ok::<(), astrs_data::DataError>(())
119    /// ```
120    pub fn try_from_lengths(
121        field: Field,
122        lengths: impl IntoIterator<Item = usize>,
123        values: ArrayRef,
124    ) -> Result<Self> {
125        let mut offsets = vec![0i32];
126        let mut total = 0usize;
127        for length in lengths {
128            total += length;
129            offsets.push(
130                i32::try_from(total).map_err(|_| DataError::OffsetOutOfBounds {
131                    index: offsets.len(),
132                    offset: total,
133                    values_len: values.len(),
134                })?,
135            );
136        }
137        if total != values.len() {
138            return Err(DataError::ChildLengthMismatch {
139                expected: total,
140                actual: values.len(),
141            });
142        }
143        Self::try_new(field, ScalarBuffer::from_slice(&offsets), values, None)
144    }
145
146    /// An all-null list array of `len` slots over an empty child.
147    ///
148    /// The child type comes from `field`; a field whose type cannot be
149    /// instantiated empty falls back to a `Null` child, which keeps the
150    /// constructor infallible.
151    #[must_use]
152    pub fn new_null(field: Field, len: usize) -> Self {
153        let values = new_empty_array(field.data_type())
154            .unwrap_or_else(|_| Arc::new(crate::array::NullArray::new(0)));
155        Self {
156            data_type: DataType::list(field),
157            offsets: ScalarBuffer::zeroed(len + 1),
158            values,
159            validity: Some(Bitmap::new_unset(len)),
160        }
161    }
162
163    /// Assembles the parts without revalidating.
164    ///
165    /// Safe, and crate-internal: [`crate::builder::ListBuilder`] constructs
166    /// its own offsets and checks the child type up front, so revalidating on
167    /// every `finish` would be pure overhead.
168    pub(crate) fn from_parts(
169        field: Field,
170        offsets: ScalarBuffer<i32>,
171        values: ArrayRef,
172        validity: Option<Bitmap>,
173    ) -> Self {
174        debug_assert_eq!(field.data_type(), values.data_type());
175        debug_assert!(validate_offsets(offsets.as_slice(), values.len()).is_ok());
176        Self {
177            data_type: DataType::list(field),
178            offsets,
179            values,
180            validity,
181        }
182    }
183
184    /// The child field describing one element.
185    #[must_use]
186    pub fn field(&self) -> Option<&Field> {
187        crate::array::child_field(&self.data_type)
188    }
189
190    /// The flat child array every list points into.
191    #[inline]
192    #[must_use]
193    pub const fn values(&self) -> &ArrayRef {
194        &self.values
195    }
196
197    /// The offset buffer, `len + 1` entries.
198    #[inline]
199    #[must_use]
200    pub fn value_offsets(&self) -> &[i32] {
201        self.offsets.as_slice()
202    }
203
204    /// The offset buffer as a shareable typed window.
205    ///
206    /// See [`crate::array::GenericBinaryArray::offsets_buffer`]: the IPC
207    /// encoder clones this window rather than copying the offsets out of a
208    /// slice.
209    ///
210    /// ```
211    /// use astrs_data::array::{Int32Array, IntoArrayRef, ListArray};
212    /// use astrs_data::{DataType, Field};
213    ///
214    /// let child = Int32Array::from_values([1, 2, 3]).into_array_ref();
215    /// let lists =
216    ///     ListArray::try_from_lengths(Field::new("item", DataType::Int32, false), [2, 1], child)?;
217    /// assert_eq!(lists.offsets_buffer().as_slice(), &[0, 2, 3]);
218    /// # Ok::<(), astrs_data::DataError>(())
219    /// ```
220    #[inline]
221    #[must_use]
222    pub const fn offsets_buffer(&self) -> &ScalarBuffer<i32> {
223        &self.offsets
224    }
225
226    /// The list at `index` as a zero-copy slice of the child, ignoring
227    /// validity.
228    ///
229    /// Returns `None` only when `index` is out of range.
230    #[must_use]
231    pub fn value(&self, index: usize) -> Option<ArrayRef> {
232        let start = usize::try_from(*self.offsets.as_slice().get(index)?).ok()?;
233        let end = usize::try_from(*self.offsets.as_slice().get(index + 1)?).ok()?;
234        Some(slice_array(&self.values, start, end.checked_sub(start)?))
235    }
236
237    /// The logical list at `index`: `None` when the slot is null or out of
238    /// range.
239    ///
240    /// A *null* list and an *empty* list are different: the first returns
241    /// `None`, the second a zero-length array.
242    #[must_use]
243    pub fn get(&self, index: usize) -> Option<ArrayRef> {
244        if self.is_valid_index(index) {
245            self.value(index)
246        } else {
247            None
248        }
249    }
250
251    /// Number of child values in list `index`, ignoring validity.
252    #[inline]
253    #[must_use]
254    pub fn value_length(&self, index: usize) -> Option<usize> {
255        let offsets = self.offsets.as_slice();
256        let start = usize::try_from(*offsets.get(index)?).ok()?;
257        let end = usize::try_from(*offsets.get(index + 1)?).ok()?;
258        end.checked_sub(start)
259    }
260
261    /// Iterates over the logical lists, `None` for nulls.
262    pub fn iter(&self) -> ArrayIter<&Self> {
263        ArrayIter::new(self)
264    }
265
266    /// A zero-copy sub-range, clamped to the array (the crate-wide slicing
267    /// convention).
268    ///
269    /// Only the offset buffer and validity are narrowed; the child array is
270    /// shared unchanged, exactly as for [`crate::array::GenericBinaryArray`].
271    #[must_use]
272    pub fn slice(&self, offset: usize, len: usize) -> Self {
273        let (offset, len) = clamp_window(self.len(), offset, len);
274        Self {
275            data_type: self.data_type.clone(),
276            offsets: self.offsets.slice(offset, len + 1),
277            values: Arc::clone(&self.values),
278            validity: self.validity.as_ref().map(|bits| bits.slice(offset, len)),
279        }
280    }
281
282    /// Checked [`ListArray::slice`].
283    ///
284    /// # Errors
285    ///
286    /// [`DataError::SliceOutOfBounds`] when the window leaves the array.
287    pub fn try_slice(&self, offset: usize, len: usize) -> Result<Self> {
288        if offset.saturating_add(len) > self.len() {
289            return Err(DataError::SliceOutOfBounds {
290                offset,
291                len,
292                available: self.len(),
293            });
294        }
295        Ok(self.slice(offset, len))
296    }
297
298    /// Returns a copy with a different validity bitmap.
299    ///
300    /// # Errors
301    ///
302    /// [`DataError::ValidityLengthMismatch`] when the bitmap length is wrong.
303    pub fn with_validity(&self, validity: Option<Bitmap>) -> Result<Self> {
304        check_validity(validity.as_ref(), self.len())?;
305        Ok(Self {
306            data_type: self.data_type.clone(),
307            offsets: self.offsets.clone(),
308            values: Arc::clone(&self.values),
309            validity,
310        })
311    }
312
313    /// Whether `index` is inside the array and not null.
314    #[inline]
315    fn is_valid_index(&self, index: usize) -> bool {
316        index < self.len() && self.validity.as_ref().is_none_or(|bits| bits.value(index))
317    }
318}
319
320impl Sealed for ListArray {}
321
322impl Array for ListArray {
323    fn as_any(&self) -> &dyn Any {
324        self
325    }
326
327    fn data_type(&self) -> &DataType {
328        &self.data_type
329    }
330
331    fn len(&self) -> usize {
332        self.offsets.len().saturating_sub(1)
333    }
334
335    fn validity(&self) -> Option<&Bitmap> {
336        self.validity.as_ref()
337    }
338
339    fn slice(&self, offset: usize, len: usize) -> ArrayRef {
340        Arc::new(Self::slice(self, offset, len))
341    }
342
343    fn buffer_memory_size(&self) -> usize {
344        self.offsets.inner().backing_len()
345            + self.values.buffer_memory_size()
346            + self
347                .validity
348                .as_ref()
349                .map_or(0, |bits| bits.buffer().backing_len())
350    }
351
352    fn children(&self) -> Vec<&ArrayRef> {
353        vec![&self.values]
354    }
355
356    fn equals(&self, other: &dyn Array) -> bool {
357        let Some(other) = other.as_any().downcast_ref::<Self>() else {
358            return false;
359        };
360        if self.data_type != other.data_type
361            || self.len() != other.len()
362            || !validity_eq(self.validity.as_ref(), other.validity.as_ref(), self.len())
363        {
364            return false;
365        }
366        (0..self.len()).all(|index| match (self.get(index), other.get(index)) {
367            (Some(a), Some(b)) => a == b,
368            (None, None) => true,
369            _ => false,
370        })
371    }
372}
373
374impl ArrayAccessor for &ListArray {
375    type Item = ArrayRef;
376
377    #[inline]
378    fn accessor_len(&self) -> usize {
379        Array::len(*self)
380    }
381
382    #[inline]
383    fn accessor_get(&self, index: usize) -> Option<ArrayRef> {
384        ListArray::get(self, index)
385    }
386}
387
388impl PartialEq for ListArray {
389    #[inline]
390    fn eq(&self, other: &Self) -> bool {
391        self.equals(other)
392    }
393}
394
395impl<'a> IntoIterator for &'a ListArray {
396    type Item = Option<ArrayRef>;
397    type IntoIter = ArrayIter<&'a ListArray>;
398
399    fn into_iter(self) -> Self::IntoIter {
400        self.iter()
401    }
402}
403
404impl fmt::Debug for ListArray {
405    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
406        let lengths: Vec<Option<usize>> = (0..self.len().min(10))
407            .map(|index| {
408                self.is_valid(index)
409                    .then(|| self.value_length(index))
410                    .flatten()
411            })
412            .collect();
413        write!(
414            f,
415            "ListArray[{}; len={}, nulls={}] lengths={lengths:?}",
416            self.data_type,
417            self.len(),
418            self.null_count()
419        )
420    }
421}
422
423#[cfg(test)]
424mod tests {
425    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
426
427    use super::*;
428    use crate::array::{Int32Array, IntoArrayRef, StringArray};
429
430    fn item_field() -> Field {
431        Field::new("item", DataType::Int32, false)
432    }
433
434    fn sample() -> ListArray {
435        let child = Int32Array::from_values([1, 2, 3, 4, 5]).into_array_ref();
436        ListArray::try_new(
437            item_field(),
438            ScalarBuffer::from_slice(&[0, 2, 2, 5]),
439            child,
440            None,
441        )
442        .unwrap()
443    }
444
445    fn as_values(array: &ArrayRef) -> Vec<i32> {
446        array
447            .as_any()
448            .downcast_ref::<Int32Array>()
449            .map(|a| a.values().to_vec())
450            .unwrap_or_default()
451    }
452
453    #[test]
454    fn empty_array() {
455        let child = Int32Array::from_values([] as [i32; 0]).into_array_ref();
456        let lists =
457            ListArray::try_new(item_field(), ScalarBuffer::from_slice(&[0]), child, None).unwrap();
458        assert!(lists.is_empty());
459        assert_eq!(lists.null_count(), 0);
460        assert!(lists.get(0).is_none());
461        assert_eq!(lists.iter().count(), 0);
462    }
463
464    #[test]
465    fn no_null_array() {
466        let lists = sample();
467        assert_eq!(lists.len(), 3);
468        assert_eq!(lists.null_count(), 0);
469        assert_eq!(as_values(&lists.get(0).unwrap()), vec![1, 2]);
470        assert_eq!(as_values(&lists.get(1).unwrap()), Vec::<i32>::new());
471        assert_eq!(as_values(&lists.get(2).unwrap()), vec![3, 4, 5]);
472        assert!(lists.get(3).is_none());
473        assert_eq!(lists.value_offsets(), &[0, 2, 2, 5]);
474        assert_eq!(lists.field().map(Field::name), Some("item"));
475        assert_eq!(lists.values().len(), 5);
476    }
477
478    #[test]
479    fn empty_lists_differ_from_null_lists() {
480        let lists = sample()
481            .with_validity(Some([true, false, true].into_iter().collect()))
482            .unwrap();
483        assert_eq!(lists.null_count(), 1);
484        assert!(lists.get(1).is_none(), "null list");
485        assert_eq!(
486            lists.value(1).map(|v| v.len()),
487            Some(0),
488            "the raw slot is still an empty list"
489        );
490        assert_eq!(lists.value_length(1), Some(0));
491    }
492
493    #[test]
494    fn all_null_array() {
495        let lists = ListArray::new_null(item_field(), 3);
496        assert_eq!(lists.len(), 3);
497        assert_eq!(lists.null_count(), 3);
498        assert_eq!(lists.data_type(), &DataType::list(item_field()));
499        for index in 0..3 {
500            assert!(lists.get(index).is_none());
501        }
502    }
503
504    #[test]
505    fn from_lengths() {
506        let child = Int32Array::from_values([1, 2, 3]).into_array_ref();
507        let lists = ListArray::try_from_lengths(item_field(), [2, 0, 1], child.clone()).unwrap();
508        assert_eq!(lists.len(), 3);
509        assert_eq!(lists.value_offsets(), &[0, 2, 2, 3]);
510        assert_eq!(
511            ListArray::try_from_lengths(item_field(), [2, 2], child).unwrap_err(),
512            DataError::ChildLengthMismatch {
513                expected: 4,
514                actual: 3
515            }
516        );
517    }
518
519    #[test]
520    fn child_type_must_match_the_field() {
521        let child = StringArray::from_values(["a"]).into_array_ref();
522        let err = ListArray::try_new(item_field(), ScalarBuffer::from_slice(&[0, 1]), child, None)
523            .unwrap_err();
524        assert!(matches!(err, DataError::TypeMismatch { .. }));
525    }
526
527    #[test]
528    fn offsets_are_validated_against_the_child() {
529        let child = Int32Array::from_values([1, 2]).into_array_ref();
530        assert!(matches!(
531            ListArray::try_new(
532                item_field(),
533                ScalarBuffer::from_slice(&[0, 9]),
534                child.clone(),
535                None
536            ),
537            Err(DataError::OffsetOutOfBounds { .. })
538        ));
539        assert!(matches!(
540            ListArray::try_new(
541                item_field(),
542                ScalarBuffer::from_slice(&[0, 2, 1]),
543                child.clone(),
544                None
545            ),
546            Err(DataError::NonMonotonicOffsets { .. })
547        ));
548        assert!(matches!(
549            ListArray::try_new(
550                item_field(),
551                ScalarBuffer::from_slice(&[0, 2]),
552                child,
553                Some(Bitmap::new_set(5))
554            ),
555            Err(DataError::ValidityLengthMismatch { .. })
556        ));
557    }
558
559    #[test]
560    fn slicing_shares_the_child() {
561        let lists = sample();
562        let window = lists.slice(1, 2);
563        assert_eq!(window.len(), 2);
564        assert_eq!(as_values(&window.get(0).unwrap()), Vec::<i32>::new());
565        assert_eq!(as_values(&window.get(1).unwrap()), vec![3, 4, 5]);
566        assert_eq!(window.values().len(), 5, "the child is shared whole");
567        assert_eq!(window.value_offsets(), &[2, 2, 5]);
568
569        assert_eq!(lists.slice(2, 99).len(), 1);
570        assert_eq!(lists.slice(99, 1).len(), 0);
571        assert_eq!(lists.slice(0, 3).slice(1, 1).len(), 1);
572        assert!(lists.try_slice(2, 2).is_err());
573    }
574
575    #[test]
576    fn nested_lists() {
577        let leaf = Int32Array::from_values([1, 2, 3, 4]).into_array_ref();
578        let inner = ListArray::try_new(
579            item_field(),
580            ScalarBuffer::from_slice(&[0, 2, 4]),
581            leaf,
582            None,
583        )
584        .unwrap();
585        let inner_field = Field::new("inner", inner.data_type().clone(), true);
586        let outer = ListArray::try_new(
587            inner_field,
588            ScalarBuffer::from_slice(&[0, 1, 2]),
589            inner.into_array_ref(),
590            None,
591        )
592        .unwrap();
593        assert_eq!(outer.len(), 2);
594        let first = outer.get(0).unwrap();
595        assert_eq!(first.len(), 1);
596        let first_inner = first.as_any().downcast_ref::<ListArray>().unwrap();
597        assert_eq!(as_values(&first_inner.get(0).unwrap()), vec![1, 2]);
598        assert!(outer.buffer_memory_size() > 0);
599        assert_eq!(outer.children().len(), 1);
600    }
601
602    #[test]
603    fn equality_is_by_logical_content() {
604        let a = sample();
605        let b = sample();
606        assert_eq!(a, b);
607        let different_child = ListArray::try_new(
608            item_field(),
609            ScalarBuffer::from_slice(&[0, 2, 2, 5]),
610            Int32Array::from_values([9, 2, 3, 4, 5]).into_array_ref(),
611            None,
612        )
613        .unwrap();
614        assert_ne!(a, different_child);
615        assert_ne!(a, a.slice(0, 2));
616
617        // A null list and an empty list are not equal.
618        let with_null = a
619            .with_validity(Some([true, false, true].into_iter().collect()))
620            .unwrap();
621        assert_ne!(a, with_null);
622    }
623
624    #[test]
625    fn debug_output_shows_lengths() {
626        let lists = sample();
627        let rendered = format!("{lists:?}");
628        assert!(rendered.contains("List(Int32)"), "{rendered}");
629        assert!(rendered.contains("len=3"), "{rendered}");
630        assert!(rendered.contains("Some(2)"), "{rendered}");
631    }
632
633    #[test]
634    fn iteration_yields_child_slices() {
635        let lists = sample()
636            .with_validity(Some([true, false, true].into_iter().collect()))
637            .unwrap();
638        let lengths: Vec<Option<usize>> = lists.iter().map(|v| v.map(|a| a.len())).collect();
639        assert_eq!(lengths, vec![Some(2), None, Some(3)]);
640        assert_eq!((&lists).into_iter().count(), 3);
641    }
642}