1use 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#[derive(Clone)]
55pub struct ListArray {
56 data_type: DataType,
58 offsets: ScalarBuffer<i32>,
60 values: ArrayRef,
62 validity: Option<Bitmap>,
64}
65
66impl ListArray {
67 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 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 #[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 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 #[must_use]
186 pub fn field(&self) -> Option<&Field> {
187 crate::array::child_field(&self.data_type)
188 }
189
190 #[inline]
192 #[must_use]
193 pub const fn values(&self) -> &ArrayRef {
194 &self.values
195 }
196
197 #[inline]
199 #[must_use]
200 pub fn value_offsets(&self) -> &[i32] {
201 self.offsets.as_slice()
202 }
203
204 #[inline]
221 #[must_use]
222 pub const fn offsets_buffer(&self) -> &ScalarBuffer<i32> {
223 &self.offsets
224 }
225
226 #[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 #[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 #[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 pub fn iter(&self) -> ArrayIter<&Self> {
263 ArrayIter::new(self)
264 }
265
266 #[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 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 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 #[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 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}