Skip to main content

astrs_data/array/
fixed_size_list.rs

1//! [`FixedSizeListArray`] — a column whose every value is exactly `size`
2//! child values.
3//!
4//! No offset buffer at all: slot `i` is `values[i * size .. (i + 1) * size]`.
5//! This is the tensor layout of the AstRS data plane — a `FixedSizeList(
6//! Float32, 3)` is a column of XYZ points, a `FixedSizeList(FixedSizeList(
7//! UInt8, 3), 640)` is a row of RGB pixels — and it is what the stage-3 tensor
8//! views are built on.
9//!
10//! ```
11//! use astrs_data::array::{Array, FixedSizeListArray, Float32Array, IntoArrayRef};
12//! use astrs_data::{DataType, Field};
13//!
14//! let child = Float32Array::from_values([1.0, 2.0, 3.0, 4.0, 5.0, 6.0]).into_array_ref();
15//! let points = FixedSizeListArray::try_new(
16//!     Field::new("xyz", DataType::Float32, false),
17//!     3,
18//!     child,
19//!     None,
20//! )?;
21//!
22//! assert_eq!(points.len(), 2, "six floats, three per point");
23//! assert_eq!(points.value_size(), 3);
24//! assert_eq!(points.get(1).map(|p| p.len()), Some(3));
25//! # Ok::<(), astrs_data::DataError>(())
26//! ```
27
28use std::any::Any;
29use std::fmt;
30use std::sync::Arc;
31
32use crate::array::iter::{ArrayAccessor, ArrayIter};
33use crate::array::{
34    Array, ArrayRef, check_fixed_size, check_validity, clamp_window, new_empty_array, slice_array,
35    validity_eq,
36};
37use crate::buffer::Bitmap;
38use crate::datatype::{DataType, Field};
39use crate::error::{DataError, Result};
40use crate::sealed::Sealed;
41
42/// A column of fixed-length runs over a shared child array.
43#[derive(Clone)]
44pub struct FixedSizeListArray {
45    /// Always `DataType::FixedSizeList(field, size)`.
46    data_type: DataType,
47    /// Child values per slot. Always positive.
48    size: usize,
49    /// The flat child array, `len * size` values long.
50    values: ArrayRef,
51    /// Logical length, `values.len() / size`.
52    len: usize,
53    /// Validity, or `None` when every slot is valid.
54    validity: Option<Bitmap>,
55}
56
57impl FixedSizeListArray {
58    /// Builds a fixed-size list array from its child and validity.
59    ///
60    /// # Errors
61    ///
62    /// * [`DataError::InvalidFixedSize`] when `size` is not positive.
63    /// * [`DataError::TypeMismatch`] when the child's type differs from the
64    ///   field's.
65    /// * [`DataError::ChildLengthMismatch`] when the child length is not a
66    ///   multiple of `size`.
67    /// * [`DataError::ValidityLengthMismatch`] when the bitmap length is wrong.
68    pub fn try_new(
69        field: Field,
70        size: i32,
71        values: ArrayRef,
72        validity: Option<Bitmap>,
73    ) -> Result<Self> {
74        let width = check_fixed_size(size)?;
75        if field.data_type() != values.data_type() {
76            return Err(DataError::type_mismatch(
77                field.data_type().clone(),
78                values.data_type().clone(),
79            ));
80        }
81        if !values.len().is_multiple_of(width) {
82            return Err(DataError::ChildLengthMismatch {
83                expected: values.len().next_multiple_of(width),
84                actual: values.len(),
85            });
86        }
87        let len = values.len() / width;
88        check_validity(validity.as_ref(), len)?;
89        Ok(Self {
90            data_type: DataType::fixed_size_list(field, size),
91            size: width,
92            values,
93            len,
94            validity,
95        })
96    }
97
98    /// An all-null array of `len` slots.
99    ///
100    /// The child is `len * size` null values of the field's type, which keeps
101    /// the layout well formed even though every slot is null.
102    ///
103    /// # Errors
104    ///
105    /// [`DataError::InvalidFixedSize`] when `size` is not positive.
106    pub fn new_null(field: Field, size: i32, len: usize) -> Result<Self> {
107        let width = check_fixed_size(size)?;
108        let values = crate::array::new_null_array(field.data_type(), len * width)
109            .or_else(|_| new_empty_array(field.data_type()))?;
110        Ok(Self {
111            data_type: DataType::fixed_size_list(field, size),
112            size: width,
113            values,
114            len,
115            validity: Some(Bitmap::new_unset(len)),
116        })
117    }
118
119    /// Assembles the parts without revalidating.
120    ///
121    /// Safe, and crate-internal: see [`crate::array::ListArray::from_parts`].
122    pub(crate) fn from_parts(
123        field: Field,
124        size: i32,
125        values: ArrayRef,
126        validity: Option<Bitmap>,
127    ) -> Self {
128        let width = usize::try_from(size).unwrap_or(1).max(1);
129        debug_assert_eq!(field.data_type(), values.data_type());
130        debug_assert_eq!(values.len() % width, 0);
131        Self {
132            data_type: DataType::fixed_size_list(field, size),
133            size: width,
134            len: values.len() / width,
135            values,
136            validity,
137        }
138    }
139
140    /// Child values per slot.
141    #[inline]
142    #[must_use]
143    pub const fn value_size(&self) -> usize {
144        self.size
145    }
146
147    /// The child field describing one element.
148    #[must_use]
149    pub fn field(&self) -> Option<&Field> {
150        crate::array::child_field(&self.data_type)
151    }
152
153    /// The flat child array.
154    #[inline]
155    #[must_use]
156    pub const fn values(&self) -> &ArrayRef {
157        &self.values
158    }
159
160    /// The run at `index` as a zero-copy slice of the child, ignoring
161    /// validity.
162    ///
163    /// Returns `None` only when `index` is out of range.
164    #[must_use]
165    pub fn value(&self, index: usize) -> Option<ArrayRef> {
166        if index >= self.len {
167            return None;
168        }
169        Some(slice_array(&self.values, index * self.size, self.size))
170    }
171
172    /// The logical run at `index`: `None` when the slot is null or out of
173    /// range.
174    #[must_use]
175    pub fn get(&self, index: usize) -> Option<ArrayRef> {
176        if self.is_valid_index(index) {
177            self.value(index)
178        } else {
179            None
180        }
181    }
182
183    /// Iterates over the logical runs, `None` for nulls.
184    pub fn iter(&self) -> ArrayIter<&Self> {
185        ArrayIter::new(self)
186    }
187
188    /// A zero-copy sub-range, clamped to the array (the crate-wide slicing
189    /// convention).
190    ///
191    /// Unlike [`crate::array::ListArray`], the child *is* narrowed here: the
192    /// fixed stride makes the child window exactly `offset * size` long, so
193    /// slicing releases the child memory outside the window.
194    #[must_use]
195    pub fn slice(&self, offset: usize, len: usize) -> Self {
196        let (offset, len) = clamp_window(self.len, offset, len);
197        Self {
198            data_type: self.data_type.clone(),
199            size: self.size,
200            values: slice_array(&self.values, offset * self.size, len * self.size),
201            len,
202            validity: self.validity.as_ref().map(|bits| bits.slice(offset, len)),
203        }
204    }
205
206    /// Checked [`FixedSizeListArray::slice`].
207    ///
208    /// # Errors
209    ///
210    /// [`DataError::SliceOutOfBounds`] when the window leaves the array.
211    pub fn try_slice(&self, offset: usize, len: usize) -> Result<Self> {
212        if offset.saturating_add(len) > self.len {
213            return Err(DataError::SliceOutOfBounds {
214                offset,
215                len,
216                available: self.len,
217            });
218        }
219        Ok(self.slice(offset, len))
220    }
221
222    /// Returns a copy with a different validity bitmap.
223    ///
224    /// # Errors
225    ///
226    /// [`DataError::ValidityLengthMismatch`] when the bitmap length is wrong.
227    pub fn with_validity(&self, validity: Option<Bitmap>) -> Result<Self> {
228        check_validity(validity.as_ref(), self.len)?;
229        Ok(Self {
230            data_type: self.data_type.clone(),
231            size: self.size,
232            values: Arc::clone(&self.values),
233            len: self.len,
234            validity,
235        })
236    }
237
238    /// Pushes this array's validity down onto the child, one parent bit per
239    /// `size` child slots.
240    ///
241    /// Stage 2 needs the flattened form when encoding a nested body, and
242    /// kernels need it when a fixed-size list is turned into a dense tensor.
243    ///
244    /// ```
245    /// use astrs_data::array::{Array, FixedSizeListArray, Int32Array, IntoArrayRef};
246    /// use astrs_data::{Bitmap, DataType, Field};
247    ///
248    /// let child = Int32Array::from_values([1, 2, 3, 4]).into_array_ref();
249    /// let lists = FixedSizeListArray::try_new(
250    ///     Field::new("pair", DataType::Int32, false),
251    ///     2,
252    ///     child,
253    ///     Some([true, false].into_iter().collect()),
254    /// )?;
255    /// let flat = lists.child_validity();
256    /// assert_eq!(flat.map(|b| b.count_unset()), Some(2));
257    /// # Ok::<(), astrs_data::DataError>(())
258    /// ```
259    #[must_use]
260    pub fn child_validity(&self) -> Option<Bitmap> {
261        self.validity
262            .as_ref()
263            .map(|bits| bits.repeat_each(self.size))
264    }
265
266    /// Whether `index` is inside the array and not null.
267    #[inline]
268    fn is_valid_index(&self, index: usize) -> bool {
269        index < self.len && self.validity.as_ref().is_none_or(|bits| bits.value(index))
270    }
271}
272
273impl Sealed for FixedSizeListArray {}
274
275impl Array for FixedSizeListArray {
276    fn as_any(&self) -> &dyn Any {
277        self
278    }
279
280    fn data_type(&self) -> &DataType {
281        &self.data_type
282    }
283
284    fn len(&self) -> usize {
285        self.len
286    }
287
288    fn validity(&self) -> Option<&Bitmap> {
289        self.validity.as_ref()
290    }
291
292    fn slice(&self, offset: usize, len: usize) -> ArrayRef {
293        Arc::new(Self::slice(self, offset, len))
294    }
295
296    fn buffer_memory_size(&self) -> usize {
297        self.values.buffer_memory_size()
298            + self
299                .validity
300                .as_ref()
301                .map_or(0, |bits| bits.buffer().backing_len())
302    }
303
304    fn children(&self) -> Vec<&ArrayRef> {
305        vec![&self.values]
306    }
307
308    fn equals(&self, other: &dyn Array) -> bool {
309        let Some(other) = other.as_any().downcast_ref::<Self>() else {
310            return false;
311        };
312        if self.data_type != other.data_type
313            || self.len != other.len
314            || !validity_eq(self.validity.as_ref(), other.validity.as_ref(), self.len)
315        {
316            return false;
317        }
318        (0..self.len).all(|index| match (self.get(index), other.get(index)) {
319            (Some(a), Some(b)) => a == b,
320            (None, None) => true,
321            _ => false,
322        })
323    }
324}
325
326impl ArrayAccessor for &FixedSizeListArray {
327    type Item = ArrayRef;
328
329    #[inline]
330    fn accessor_len(&self) -> usize {
331        self.len
332    }
333
334    #[inline]
335    fn accessor_get(&self, index: usize) -> Option<ArrayRef> {
336        FixedSizeListArray::get(self, index)
337    }
338}
339
340impl PartialEq for FixedSizeListArray {
341    #[inline]
342    fn eq(&self, other: &Self) -> bool {
343        self.equals(other)
344    }
345}
346
347impl<'a> IntoIterator for &'a FixedSizeListArray {
348    type Item = Option<ArrayRef>;
349    type IntoIter = ArrayIter<&'a FixedSizeListArray>;
350
351    fn into_iter(self) -> Self::IntoIter {
352        self.iter()
353    }
354}
355
356impl fmt::Debug for FixedSizeListArray {
357    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
358        write!(
359            f,
360            "FixedSizeListArray[{}; len={}, nulls={}, size={}]",
361            self.data_type,
362            self.len,
363            self.null_count(),
364            self.size
365        )
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
372
373    use super::*;
374    use crate::array::{Float32Array, Int32Array, IntoArrayRef, StringArray};
375
376    fn xyz_field() -> Field {
377        Field::new("xyz", DataType::Float32, false)
378    }
379
380    fn points() -> FixedSizeListArray {
381        let child = Float32Array::from_values([1.0, 2.0, 3.0, 4.0, 5.0, 6.0]).into_array_ref();
382        FixedSizeListArray::try_new(xyz_field(), 3, child, None).unwrap()
383    }
384
385    fn as_floats(array: &ArrayRef) -> Vec<f32> {
386        array
387            .as_any()
388            .downcast_ref::<Float32Array>()
389            .map(|a| a.values().to_vec())
390            .unwrap_or_default()
391    }
392
393    #[test]
394    fn empty_array() {
395        let child = Float32Array::from_values([] as [f32; 0]).into_array_ref();
396        let points = FixedSizeListArray::try_new(xyz_field(), 3, child, None).unwrap();
397        assert!(points.is_empty());
398        assert_eq!(points.value_size(), 3);
399        assert!(points.get(0).is_none());
400        assert_eq!(points.iter().count(), 0);
401    }
402
403    #[test]
404    fn no_null_array() {
405        let points = points();
406        assert_eq!(points.len(), 2);
407        assert_eq!(points.null_count(), 0);
408        assert_eq!(as_floats(&points.get(0).unwrap()), vec![1.0, 2.0, 3.0]);
409        assert_eq!(as_floats(&points.get(1).unwrap()), vec![4.0, 5.0, 6.0]);
410        assert!(points.get(2).is_none());
411        assert_eq!(points.field().map(Field::name), Some("xyz"));
412        assert_eq!(points.values().len(), 6);
413        assert!(points.child_validity().is_none());
414    }
415
416    #[test]
417    fn all_null_array() {
418        let points = FixedSizeListArray::new_null(xyz_field(), 3, 2).unwrap();
419        assert_eq!(points.len(), 2);
420        assert_eq!(points.null_count(), 2);
421        assert_eq!(points.values().len(), 6);
422        assert!(points.get(0).is_none());
423        assert_eq!(points.value(0).map(|v| v.len()), Some(3));
424    }
425
426    #[test]
427    fn mixed_nulls_and_child_validity() {
428        let child = Int32Array::from_values([1, 2, 3, 4]).into_array_ref();
429        let lists = FixedSizeListArray::try_new(
430            Field::new("pair", DataType::Int32, false),
431            2,
432            child,
433            Some([true, false].into_iter().collect()),
434        )
435        .unwrap();
436        assert_eq!(lists.null_count(), 1);
437        assert!(lists.get(1).is_none());
438        assert_eq!(lists.value(1).map(|v| v.len()), Some(2));
439        let flat = lists.child_validity().unwrap();
440        assert_eq!(flat.len(), 4);
441        assert_eq!(
442            flat.iter().collect::<Vec<_>>(),
443            vec![true, true, false, false]
444        );
445    }
446
447    #[test]
448    fn invalid_sizes_are_rejected() {
449        let child = Float32Array::from_values([1.0]).into_array_ref();
450        assert!(FixedSizeListArray::try_new(xyz_field(), 0, child.clone(), None).is_err());
451        assert!(FixedSizeListArray::try_new(xyz_field(), -2, child, None).is_err());
452        assert!(FixedSizeListArray::new_null(xyz_field(), 0, 1).is_err());
453    }
454
455    #[test]
456    fn child_length_must_be_a_multiple_of_the_size() {
457        let child = Float32Array::from_values([1.0, 2.0, 3.0, 4.0]).into_array_ref();
458        assert_eq!(
459            FixedSizeListArray::try_new(xyz_field(), 3, child, None).unwrap_err(),
460            DataError::ChildLengthMismatch {
461                expected: 6,
462                actual: 4
463            }
464        );
465    }
466
467    #[test]
468    fn child_type_must_match_the_field() {
469        let child = StringArray::from_values(["a"]).into_array_ref();
470        assert!(matches!(
471            FixedSizeListArray::try_new(xyz_field(), 1, child, None),
472            Err(DataError::TypeMismatch { .. })
473        ));
474    }
475
476    #[test]
477    fn validity_length_is_checked() {
478        let child = Float32Array::from_values([1.0, 2.0]).into_array_ref();
479        assert!(matches!(
480            FixedSizeListArray::try_new(xyz_field(), 1, child, Some(Bitmap::new_set(5))),
481            Err(DataError::ValidityLengthMismatch { .. })
482        ));
483    }
484
485    #[test]
486    fn slicing_narrows_the_child_too() {
487        let child = Int32Array::from_values(0..30).into_array_ref();
488        let lists = FixedSizeListArray::try_new(
489            Field::new("triple", DataType::Int32, false),
490            3,
491            child,
492            None,
493        )
494        .unwrap();
495        assert_eq!(lists.len(), 10);
496        let window = lists.slice(2, 3);
497        assert_eq!(window.len(), 3);
498        assert_eq!(window.values().len(), 9, "the child window is exact");
499        assert_eq!(
500            window.get(0).and_then(|v| v
501                .as_any()
502                .downcast_ref::<Int32Array>()
503                .map(|a| a.values()[0])),
504            Some(6)
505        );
506        assert_eq!(lists.slice(9, 99).len(), 1);
507        assert_eq!(lists.slice(99, 1).len(), 0);
508        assert_eq!(lists.slice(1, 5).slice(2, 2).len(), 2);
509        assert!(lists.try_slice(9, 2).is_err());
510    }
511
512    #[test]
513    fn nested_fixed_size_lists_model_an_image_row() {
514        // 4 pixels of RGB = FixedSizeList(FixedSizeList(UInt8, 3), 4)
515        let bytes = crate::array::UInt8Array::from_values(0..12u8).into_array_ref();
516        let pixels = FixedSizeListArray::try_new(
517            Field::new("channel", DataType::UInt8, false),
518            3,
519            bytes,
520            None,
521        )
522        .unwrap();
523        assert_eq!(pixels.len(), 4);
524        let row = FixedSizeListArray::try_new(
525            Field::new("pixel", pixels.data_type().clone(), false),
526            4,
527            pixels.into_array_ref(),
528            None,
529        )
530        .unwrap();
531        assert_eq!(row.len(), 1);
532        let first = row.get(0).unwrap();
533        assert_eq!(first.len(), 4);
534        assert_eq!(row.children().len(), 1);
535        assert!(row.buffer_memory_size() >= 12);
536    }
537
538    #[test]
539    fn equality_is_by_logical_content() {
540        assert_eq!(points(), points());
541        let other = FixedSizeListArray::try_new(
542            xyz_field(),
543            3,
544            Float32Array::from_values([9.0, 2.0, 3.0, 4.0, 5.0, 6.0]).into_array_ref(),
545            None,
546        )
547        .unwrap();
548        assert_ne!(points(), other);
549        assert_ne!(points(), points().slice(0, 1));
550
551        let masked = points()
552            .with_validity(Some([true, false].into_iter().collect()))
553            .unwrap();
554        assert_ne!(points(), masked);
555        assert!(points().with_validity(Some(Bitmap::new_set(9))).is_err());
556    }
557
558    #[test]
559    fn different_sizes_are_not_equal() {
560        let child = Int32Array::from_values([1, 2, 3, 4]).into_array_ref();
561        let field = Field::new("v", DataType::Int32, false);
562        let two = FixedSizeListArray::try_new(field.clone(), 2, child.clone(), None).unwrap();
563        let four = FixedSizeListArray::try_new(field, 4, child, None).unwrap();
564        assert_ne!(two, four);
565    }
566
567    #[test]
568    fn debug_output_shows_the_size() {
569        let rendered = format!("{:?}", points());
570        assert!(rendered.contains("FixedSizeList(Float32, 3)"), "{rendered}");
571        assert!(rendered.contains("size=3"), "{rendered}");
572        assert!(rendered.contains("len=2"), "{rendered}");
573    }
574
575    #[test]
576    fn iteration_yields_child_slices() {
577        let masked = points()
578            .with_validity(Some([true, false].into_iter().collect()))
579            .unwrap();
580        let lengths: Vec<Option<usize>> = masked.iter().map(|v| v.map(|a| a.len())).collect();
581        assert_eq!(lengths, vec![Some(3), None]);
582        assert_eq!((&masked).into_iter().count(), 2);
583    }
584}