1use num_traits::FromPrimitive;
5use vortex_buffer::BufferAllocatorRef;
6use vortex_buffer::BufferMut;
7use vortex_error::VortexExpect;
8use vortex_error::VortexResult;
9use vortex_error::vortex_bail;
10use vortex_error::vortex_err;
11use vortex_mask::Mask;
12
13use crate::Canonical;
14use crate::ExecutionCtx;
15use crate::IntoArray;
16use crate::arrays::ConstantArray;
17use crate::arrays::ListViewArray;
18use crate::arrays::PiecewiseSequenceArray;
19use crate::arrays::PrimitiveArray;
20use crate::arrays::list::drop_unreferenced_elements;
21use crate::arrays::list::null_runs_holding_elements;
22use crate::arrays::listview::ListViewArrayExt;
23use crate::arrays::listview::ListViewArraySlotsExt;
24use crate::arrays::primitive::PrimitiveArrayExt;
25use crate::builtins::ArrayBuiltins;
26use crate::dtype::IntegerPType;
27use crate::dtype::Nullability;
28use crate::dtype::PType;
29use crate::match_each_integer_ptype;
30use crate::match_each_unsigned_integer_ptype;
31use crate::scalar::Scalar;
32use crate::scalar_fn::fns::operators::Operator;
33use crate::validity::Validity;
34
35fn rebuilt_offset_ptype(offsets_ptype: PType) -> PType {
41 match offsets_ptype {
42 PType::U8 | PType::U16 | PType::U32 => PType::U32,
43 PType::U64 => PType::U64,
44 PType::I8 | PType::I16 | PType::I32 => PType::I32,
45 PType::I64 => PType::I64,
46 _ => unreachable!("invalid offsets PType"),
47 }
48}
49
50pub const DEFAULT_REBUILD_DENSITY_THRESHOLD: f32 = 0.1;
59
60pub const DEFAULT_TRIM_ELEMENTS_THRESHOLD: f32 = 0.05;
69
70pub enum ListViewRebuildMode {
72 MakeZeroCopyToList,
80
81 TrimElements,
87
88 MakeExact,
100
101 MakeExactWithEmptyNulls,
110
111 OverlapCompression,
118}
119
120impl ListViewArray {
121 pub fn rebuild(
123 &self,
124 mode: ListViewRebuildMode,
125 ctx: &mut ExecutionCtx,
126 ) -> VortexResult<ListViewArray> {
127 if self.is_empty() {
128 return Ok(Canonical::empty(self.dtype()).into_listview());
130 }
131
132 match mode {
133 ListViewRebuildMode::MakeZeroCopyToList => self.rebuild_zero_copy_to_list(ctx),
134 ListViewRebuildMode::TrimElements => self.rebuild_trim_elements(ctx),
135 ListViewRebuildMode::MakeExact => self.rebuild_make_exact(ctx),
136 ListViewRebuildMode::MakeExactWithEmptyNulls => {
137 self.rebuild_make_exact_with_empty_nulls(ctx)
138 }
139 ListViewRebuildMode::OverlapCompression => {
140 vortex_bail!("ListViewRebuildMode::OverlapCompression is not implemented")
141 }
142 }
143 }
144
145 fn rebuild_make_exact_with_empty_nulls(
148 &self,
149 ctx: &mut ExecutionCtx,
150 ) -> VortexResult<ListViewArray> {
151 if !self.is_zero_copy_to_list() {
152 return self.rebuild_make_exact(ctx);
153 }
154 let validity = self.validity()?;
155 let last = self.len() - 1;
157 let end = self.offset_at(last, ctx) + self.size_at(last, ctx);
158 if validity.definitely_no_nulls()
159 && self.offset_at(0, ctx) == 0
160 && end == self.elements().len()
161 {
162 return Ok(self.clone());
163 }
164
165 let offsets = self.offsets().clone().execute::<PrimitiveArray>(ctx)?;
166 let offsets_ptype = offsets.ptype();
167 let offsets = offsets.reinterpret_cast(offsets_ptype.to_unsigned());
169 let valid = validity.execute_mask(self.len(), ctx)?;
170 match_each_unsigned_integer_ptype!(offsets.ptype(), |O| {
171 self.rebuild_back_to_back(offsets.as_slice::<O>(), offsets_ptype, end, &valid, ctx)
172 })
173 }
174
175 fn rebuild_back_to_back<O: IntegerPType>(
178 &self,
179 starts: &[O],
180 offsets_ptype: PType,
181 end: usize,
182 valid: &Mask,
183 ctx: &mut ExecutionCtx,
184 ) -> VortexResult<ListViewArray> {
185 let null_runs = null_runs_holding_elements(valid, |index| {
187 starts[index].as_() != starts.get(index + 1).map_or(end, |next| next.as_())
188 });
189 if null_runs.is_empty() && starts[0].as_() == 0 && end == self.elements().len() {
190 return Ok(self.clone());
191 }
192
193 let (elements, offsets) =
194 drop_unreferenced_elements(self.elements(), starts, end, &null_runs, ctx.allocator())?;
195 let offsets = PrimitiveArray::new(offsets.freeze(), Validity::NonNullable)
196 .reinterpret_cast(offsets_ptype)
197 .into_array();
198 let sizes = if null_runs.is_empty() {
199 self.sizes().clone()
200 } else {
201 let sizes = self.sizes().clone().execute::<PrimitiveArray>(ctx)?;
202 let sizes_ptype = sizes.ptype();
203 let sizes = sizes.reinterpret_cast(sizes_ptype.to_unsigned());
204 let sizes = match_each_unsigned_integer_ptype!(sizes.ptype(), |S| {
205 empty_runs(sizes.as_slice::<S>(), &null_runs, ctx.allocator())
206 });
207 sizes.reinterpret_cast(sizes_ptype).into_array()
208 };
209
210 Ok(unsafe {
213 ListViewArray::new_unchecked(elements, offsets, sizes, self.validity()?)
214 .with_zero_copy_to_list(true)
215 })
216 }
217
218 fn rebuild_zero_copy_to_list(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListViewArray> {
226 if self.is_zero_copy_to_list() {
227 return Ok(self.clone());
229 }
230
231 let offsets_ptype = self.offsets().dtype().as_ptype();
232 let sizes_ptype = self.sizes().dtype().as_ptype();
233
234 match_each_unsigned_integer_ptype!(sizes_ptype.to_unsigned(), |S| {
242 match offsets_ptype.to_unsigned() {
243 PType::U8 => self.naive_rebuild::<u8, u32, S>(ctx),
244 PType::U16 => self.naive_rebuild::<u16, u32, S>(ctx),
245 PType::U32 => self.naive_rebuild::<u32, u32, S>(ctx),
246 PType::U64 => self.naive_rebuild::<u64, u64, S>(ctx),
247 _ => unreachable!("invalid offsets PType"),
248 }
249 })
250 }
251
252 fn naive_rebuild<O: IntegerPType, NewOffset: IntegerPType, S: IntegerPType>(
255 &self,
256 ctx: &mut ExecutionCtx,
257 ) -> VortexResult<ListViewArray> {
258 let sizes_canonical = self.sizes().clone().execute::<PrimitiveArray>(ctx)?;
259 let sizes_canonical =
260 sizes_canonical.reinterpret_cast(sizes_canonical.ptype().to_unsigned());
261 let total: u64 = sizes_canonical
262 .as_slice::<S>()
263 .iter()
264 .map(|s| (*s).as_() as u64)
265 .sum();
266 if Self::should_use_take(total, self.len()) {
267 self.rebuild_with_take::<O, NewOffset, S>(ctx)
268 } else {
269 self.rebuild_with_piecewise::<NewOffset, S>(ctx)
270 }
271 }
272
273 fn should_use_take(total_output_elements: u64, num_lists: usize) -> bool {
281 if num_lists == 0 {
282 return true;
283 }
284 let avg = total_output_elements / num_lists as u64;
285 avg < 128
286 }
287
288 fn rebuild_with_take<O: IntegerPType, NewOffset: IntegerPType, S: IntegerPType>(
291 &self,
292 ctx: &mut ExecutionCtx,
293 ) -> VortexResult<ListViewArray> {
294 let new_offset_ptype = rebuilt_offset_ptype(self.offsets().dtype().as_ptype());
295 let size_ptype = self.sizes().dtype().as_ptype();
296
297 let offsets_canonical = self.offsets().clone().execute::<PrimitiveArray>(ctx)?;
298 let offsets_canonical =
299 offsets_canonical.reinterpret_cast(offsets_canonical.ptype().to_unsigned());
300 let offsets_slice = offsets_canonical.as_slice::<O>();
301 let sizes_canonical = self.sizes().clone().execute::<PrimitiveArray>(ctx)?;
302 let sizes_canonical =
303 sizes_canonical.reinterpret_cast(sizes_canonical.ptype().to_unsigned());
304 let sizes_slice = sizes_canonical.as_slice::<S>();
305
306 let len = offsets_slice.len();
307
308 let mut new_offsets = BufferMut::<NewOffset>::with_capacity(len);
309 let mut new_sizes = BufferMut::<S>::with_capacity(len);
310 let mut take_indices = BufferMut::<u64>::with_capacity(self.elements().len());
311
312 let validity = self.validity()?.execute_mask(len, ctx)?;
316
317 let mut n_elements = NewOffset::zero();
318 for index in 0..len {
319 if !validity.value(index) {
320 new_offsets.push(n_elements);
321 new_sizes.push(S::zero());
322 continue;
323 }
324
325 let offset = offsets_slice[index];
326 let size = sizes_slice[index];
327 let start = offset.as_();
328 let stop = start + size.as_();
329
330 new_offsets.push(n_elements);
331 new_sizes.push(size);
332 take_indices.extend(start as u64..stop as u64);
333 n_elements += num_traits::cast(size).vortex_expect("Cast failed");
334 }
335
336 let elements = self.elements().take(take_indices.into_array())?;
337 let offsets = PrimitiveArray::new(new_offsets.freeze(), Validity::NonNullable)
339 .reinterpret_cast(new_offset_ptype)
340 .into_array();
341 let sizes = PrimitiveArray::new(new_sizes.freeze(), Validity::NonNullable)
342 .reinterpret_cast(size_ptype)
343 .into_array();
344
345 Ok(unsafe {
348 ListViewArray::new_unchecked(elements, offsets, sizes, self.validity()?)
349 .with_zero_copy_to_list(true)
350 })
351 }
352
353 fn rebuild_with_piecewise<NewOffset: IntegerPType, S: IntegerPType>(
355 &self,
356 ctx: &mut ExecutionCtx,
357 ) -> VortexResult<ListViewArray> {
358 let new_offset_ptype = rebuilt_offset_ptype(self.offsets().dtype().as_ptype());
359 let size_ptype = self.sizes().dtype().as_ptype();
360
361 let offsets_canonical = self.offsets().clone().execute::<PrimitiveArray>(ctx)?;
362 let offsets_canonical =
363 offsets_canonical.reinterpret_cast(offsets_canonical.ptype().to_unsigned());
364 let sizes_canonical = self.sizes().clone().execute::<PrimitiveArray>(ctx)?;
365 let sizes_canonical =
366 sizes_canonical.reinterpret_cast(sizes_canonical.ptype().to_unsigned());
367
368 let len = offsets_canonical.len();
369 let validity = self.validity()?;
370 let validity_mask = validity.execute_mask(len, ctx)?;
371
372 let ranges = match_each_unsigned_integer_ptype!(offsets_canonical.ptype(), |O| {
373 rebuild_ranges::<NewOffset, O, S>(
374 offsets_canonical.as_slice::<O>(),
375 sizes_canonical.as_slice::<S>(),
376 &validity_mask,
377 )
378 })?;
379
380 let RebuildRanges {
381 new_offsets,
382 new_sizes,
383 starts,
384 lengths,
385 elements_len,
386 } = ranges;
387 let constant_length = lengths
388 .first()
389 .copied()
390 .filter(|first| lengths.iter().all(|length| *length == *first));
391 let lengths = match constant_length {
392 Some(length) => ConstantArray::new(length, starts.len()).into_array(),
393 None => lengths.into_array(),
394 };
395
396 let multipliers = ConstantArray::new(1u64, starts.len()).into_array();
399 let element_indices = unsafe {
400 PiecewiseSequenceArray::new_unchecked(
401 starts.into_array(),
402 lengths,
403 multipliers,
404 elements_len,
405 )
406 };
407 let elements = self.elements().take(element_indices.into_array())?;
408
409 let offsets = PrimitiveArray::new(new_offsets.freeze(), Validity::NonNullable)
411 .reinterpret_cast(new_offset_ptype)
412 .into_array();
413 let sizes = PrimitiveArray::new(new_sizes.freeze(), Validity::NonNullable)
414 .reinterpret_cast(size_ptype)
415 .into_array();
416
417 Ok(unsafe {
420 ListViewArray::new_unchecked(elements, offsets, sizes, validity)
421 .with_zero_copy_to_list(true)
422 })
423 }
424
425 fn rebuild_trim_elements(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListViewArray> {
429 let (start, end) = self.referenced_element_bounds(ctx)?;
430
431 unsafe { self.trim_elements(start, end) }
433 }
434
435 pub unsafe fn trim_elements(&self, start: usize, end: usize) -> VortexResult<ListViewArray> {
444 let adjusted_offsets = match_each_integer_ptype!(self.offsets().dtype().as_ptype(), |O| {
445 let offset = <O as FromPrimitive>::from_usize(start)
446 .vortex_expect("unable to convert the min offset `start` into a `usize`");
447 let scalar = Scalar::primitive(offset, Nullability::NonNullable);
448
449 self.offsets()
450 .clone()
451 .binary(
452 ConstantArray::new(scalar, self.offsets().len()).into_array(),
453 Operator::Sub,
454 )
455 .vortex_expect("was somehow unable to adjust offsets down by their minimum")
456 });
457
458 let sliced_elements = self.elements().slice(start..end)?;
459
460 Ok(unsafe {
465 ListViewArray::new_unchecked(
466 sliced_elements,
467 adjusted_offsets,
468 self.sizes().clone(),
469 self.validity()?,
470 )
471 .with_zero_copy_to_list(self.is_zero_copy_to_list())
472 })
473 }
474
475 fn rebuild_make_exact(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListViewArray> {
476 if self.is_zero_copy_to_list() {
477 self.rebuild_trim_elements(ctx)
478 } else {
479 self.rebuild_zero_copy_to_list(ctx)
482 }
483 }
484}
485
486fn empty_runs<S: IntegerPType>(
488 sizes: &[S],
489 runs: &[(usize, usize)],
490 allocator: &BufferAllocatorRef,
491) -> PrimitiveArray {
492 let mut emptied = BufferMut::with_capacity_in(sizes.len(), allocator.clone());
493 let mut from = 0;
494 for &(run_start, run_end) in runs {
495 emptied.extend_from_slice(&sizes[from..run_start]);
496 emptied.push_n(S::zero(), run_end - run_start);
497 from = run_end;
498 }
499 emptied.extend_from_slice(&sizes[from..]);
500 PrimitiveArray::new(emptied.freeze(), Validity::NonNullable)
501}
502
503struct RebuildRanges<NewOffset, S> {
504 new_offsets: BufferMut<NewOffset>,
505 new_sizes: BufferMut<S>,
506 starts: BufferMut<u64>,
507 lengths: BufferMut<u64>,
508 elements_len: usize,
509}
510
511fn rebuild_ranges<NewOffset, O, S>(
512 offsets: &[O],
513 sizes: &[S],
514 validity_mask: &Mask,
515) -> VortexResult<RebuildRanges<NewOffset, S>>
516where
517 NewOffset: IntegerPType,
518 O: IntegerPType,
519 S: IntegerPType,
520{
521 let len = offsets.len();
522 let mut new_offsets = BufferMut::<NewOffset>::with_capacity(len);
523 let mut new_sizes = BufferMut::<S>::with_capacity(len);
524 let mut starts = BufferMut::<u64>::with_capacity(len);
525 let mut lengths = BufferMut::<u64>::with_capacity(len);
526 let mut n_elements = NewOffset::zero();
527 let mut elements_len = 0usize;
528
529 for (index, is_valid) in validity_mask.iter().enumerate() {
530 if !is_valid {
531 new_offsets.push(n_elements);
532 new_sizes.push(S::zero());
533 starts.push(0);
534 lengths.push(0);
535 continue;
536 }
537
538 let size = sizes[index];
539 let start: usize = offsets[index].as_();
540 let length: usize = size.as_();
541 start.checked_add(length).ok_or_else(|| {
542 vortex_err!(
543 "ListView rebuild element range overflow for start {start} and length {length}"
544 )
545 })?;
546 elements_len = elements_len
547 .checked_add(length)
548 .ok_or_else(|| vortex_err!("ListView rebuild elements length overflow"))?;
549
550 new_offsets.push(n_elements);
551 new_sizes.push(size);
552 starts.push(start as u64);
553 lengths.push(length as u64);
554 n_elements += num_traits::cast(size).vortex_expect("Cast failed");
555 }
556
557 Ok(RebuildRanges {
558 new_offsets,
559 new_sizes,
560 starts,
561 lengths,
562 elements_len,
563 })
564}
565
566#[cfg(test)]
567mod tests {
568 use rand::RngExt;
569 use rand::SeedableRng;
570 use rand::rngs::StdRng;
571 use rstest::rstest;
572 use vortex_buffer::BitBuffer;
573 use vortex_error::VortexResult;
574
575 use super::super::tests::common::SESSION;
576 use super::ListViewRebuildMode;
577 use crate::ArrayRef;
578 use crate::ExecutionCtx;
579 use crate::IntoArray;
580 use crate::VortexSessionExecute;
581 use crate::arrays::BoolArray;
582 use crate::arrays::ListArray;
583 use crate::arrays::ListViewArray;
584 use crate::arrays::PrimitiveArray;
585 use crate::arrays::list::ListArraySlotsExt;
586 use crate::arrays::listview::ListViewArrayExt;
587 use crate::arrays::listview::ListViewArraySlotsExt;
588 use crate::assert_arrays_eq;
589 use crate::builtins::ArrayBuiltins;
590 use crate::dtype::DType;
591 use crate::dtype::Nullability;
592 use crate::dtype::PType;
593 use crate::validity::Validity;
594
595 #[rstest]
596 #[case::nothing_to_drop(&[1, 2], &[(0, 1), (1, 1)], &[true, true], true, &[1, 2], &[(0, 1), (1, 1)])]
597 #[case::leftovers_at_the_ends(
598 &[9, 1, 2, 9],
599 &[(1, 1), (2, 1)],
600 &[true, true],
601 true,
602 &[1, 2],
603 &[(0, 1), (1, 1)]
604 )]
605 #[case::null_list_holding_elements(
606 &[9, 1, 9, 2],
607 &[(1, 1), (2, 1), (3, 1)],
608 &[true, false, true],
609 true,
610 &[1, 2],
611 &[(0, 1), (1, 0), (1, 1)]
612 )]
613 #[case::gap_between_lists(&[1, 9, 2], &[(0, 1), (2, 1)], &[true, true], false, &[1, 2], &[(0, 1), (1, 1)])]
614 #[case::lists_out_of_order(
615 &[1, 2, 3, 9],
616 &[(2, 1), (0, 2)],
617 &[true, true],
618 false,
619 &[3, 1, 2],
620 &[(0, 1), (1, 2)]
621 )]
622 #[case::null_list_holding_elements_not_zero_copy(
623 &[9, 1, 9, 2],
624 &[(1, 1), (2, 1), (3, 1)],
625 &[true, false, true],
626 false,
627 &[1, 2],
628 &[(0, 1), (1, 0), (1, 1)]
629 )]
630 #[case::empty_null_list_with_leftovers_at_the_ends(
631 &[9, 1, 2, 9],
632 &[(1, 1), (2, 0), (2, 1)],
633 &[true, false, true],
634 true,
635 &[1, 2],
636 &[(0, 1), (1, 0), (1, 1)]
637 )]
638 #[case::every_list_null(
639 &[9, 9],
640 &[(0, 1), (1, 1)],
641 &[false, false],
642 true,
643 &[],
644 &[(0, 0), (0, 0)]
645 )]
646 #[case::empty_lists_with_leftovers(
647 &[9, 9],
648 &[(1, 0), (1, 0)],
649 &[true, true],
650 true,
651 &[],
652 &[(0, 0), (0, 0)]
653 )]
654 #[case::overlapping_lists(
655 &[1, 2, 3, 9],
656 &[(0, 3), (1, 2)],
657 &[true, true],
658 false,
659 &[1, 2, 3, 2, 3],
660 &[(0, 3), (3, 2)]
661 )]
662 fn test_rebuild_make_exact_with_empty_nulls(
663 #[case] elements: &[i32],
664 #[case] views: &[(u32, u32)],
665 #[case] validity: &[bool],
666 #[case] zero_copy_to_list: bool,
667 #[case] expected_elements: &[i32],
668 #[case] expected_views: &[(u32, u32)],
669 ) -> VortexResult<()> {
670 let mut ctx = SESSION.create_execution_ctx();
671 let view = ListViewArray::try_new(
672 PrimitiveArray::from_iter(elements.iter().copied()).into_array(),
673 PrimitiveArray::from_iter(views.iter().map(|(offset, _)| *offset)).into_array(),
674 PrimitiveArray::from_iter(views.iter().map(|(_, size)| *size)).into_array(),
675 Validity::from_iter(validity.iter().copied()),
676 &mut ctx,
677 )?;
678 let view = unsafe { view.with_zero_copy_to_list(zero_copy_to_list) };
680 let rebuilt = view.rebuild(ListViewRebuildMode::MakeExactWithEmptyNulls, &mut ctx)?;
681 assert!(rebuilt.is_zero_copy_to_list());
682 assert_arrays_eq!(
683 rebuilt.elements().clone(),
684 PrimitiveArray::from_iter(expected_elements.iter().copied()),
685 &mut ctx
686 );
687 assert_arrays_eq!(
688 rebuilt.offsets().clone(),
689 PrimitiveArray::from_iter(expected_views.iter().map(|(offset, _)| *offset)),
690 &mut ctx
691 );
692 assert_arrays_eq!(
693 rebuilt.sizes().clone(),
694 PrimitiveArray::from_iter(expected_views.iter().map(|(_, size)| *size)),
695 &mut ctx
696 );
697 assert_arrays_eq!(rebuilt, view, &mut ctx);
698 Ok(())
699 }
700
701 #[rstest]
702 #[case::non_nullable(Validity::NonNullable)]
703 #[case::empty_null_list(Validity::from_iter([true, false, true]))]
704 fn test_rebuild_make_exact_with_empty_nulls_returns_an_exact_list_view_as_is(
705 #[case] validity: Validity,
706 ) -> VortexResult<()> {
707 let mut ctx = SESSION.create_execution_ctx();
708 let view = ListViewArray::try_new(
709 PrimitiveArray::from_iter([1i32, 2, 3]).into_array(),
710 PrimitiveArray::from_iter([0u32, 1, 1]).into_array(),
711 PrimitiveArray::from_iter([1u32, 0, 2]).into_array(),
712 validity,
713 &mut ctx,
714 )?;
715 let view = unsafe { view.with_zero_copy_to_list(true) };
717 let rebuilt = view.rebuild(ListViewRebuildMode::MakeExactWithEmptyNulls, &mut ctx)?;
718 assert!(ArrayRef::ptr_eq(rebuilt.elements(), view.elements()));
719 assert!(ArrayRef::ptr_eq(rebuilt.offsets(), view.offsets()));
720 assert!(ArrayRef::ptr_eq(rebuilt.sizes(), view.sizes()));
721 Ok(())
722 }
723
724 fn primitive_of(
726 values: impl IntoIterator<Item = u32>,
727 ptype: PType,
728 ctx: &mut ExecutionCtx,
729 ) -> VortexResult<ArrayRef> {
730 Ok(PrimitiveArray::from_iter(values)
731 .into_array()
732 .cast(DType::Primitive(ptype, Nullability::NonNullable))?
733 .execute::<PrimitiveArray>(ctx)?
734 .into_array())
735 }
736
737 #[test]
741 fn test_compact_and_make_exact_with_empty_nulls_match_a_reference() -> VortexResult<()> {
742 const PTYPES: [PType; 5] = [PType::U8, PType::U16, PType::U64, PType::I32, PType::I64];
743 let u32_dtype = DType::Primitive(PType::U32, Nullability::NonNullable);
744 let mut ctx = SESSION.create_execution_ctx();
745 let mut rng = StdRng::seed_from_u64(0);
746 for _ in 0..500 {
747 let len = rng.random_range(0..10usize);
748 let mut offset = rng.random_range(0..3u32);
749 let mut offsets = vec![offset];
750 for _ in 0..len {
751 offset += rng.random_range(0..3u32);
752 offsets.push(offset);
753 }
754 let elements_len = offset + rng.random_range(0..3u32);
755 let valid: Vec<bool> = (0..len).map(|_| rng.random_bool(0.6)).collect();
756 let validity = match rng.random_range(0..3u8) {
757 0 if valid.iter().all(|valid| *valid) => Validity::NonNullable,
758 1 => Validity::Array(
760 BoolArray::from_iter([false].into_iter().chain(valid.iter().copied()))
761 .into_array()
762 .slice(1..len + 1)?,
763 ),
764 _ => Validity::from_iter(valid.iter().copied()),
765 };
766 let ptype = PTYPES[rng.random_range(0..PTYPES.len())];
767
768 let mut expected_elements = Vec::new();
769 let mut expected_offsets = vec![0u32];
770 let mut kept = 0u32;
771 for (bounds, is_valid) in offsets.windows(2).zip(&valid) {
772 if *is_valid {
773 expected_elements.extend(bounds[0]..bounds[1]);
774 kept += bounds[1] - bounds[0];
775 }
776 expected_offsets.push(kept);
777 }
778 let expected_elements = PrimitiveArray::from_iter(expected_elements);
779 let expected_sizes =
780 PrimitiveArray::from_iter(expected_offsets.windows(2).map(|w| w[1] - w[0]));
781
782 let elements = PrimitiveArray::from_iter(0..elements_len).into_array();
783 let list = ListArray::try_new(
784 elements.clone(),
785 primitive_of(offsets.iter().copied(), ptype, &mut ctx)?,
786 validity.clone(),
787 &mut ctx,
788 )?;
789 let rebuilt = list.compact(&mut ctx)?;
790 assert_arrays_eq!(
791 rebuilt.elements().clone(),
792 expected_elements.clone(),
793 &mut ctx
794 );
795 assert_eq!(rebuilt.offsets().dtype(), list.offsets().dtype());
796 assert_arrays_eq!(
797 rebuilt.offsets().cast(u32_dtype.clone())?,
798 PrimitiveArray::from_iter(expected_offsets.iter().copied()),
799 &mut ctx
800 );
801 assert_arrays_eq!(rebuilt, list, &mut ctx);
802
803 for zero_copy_to_list in [true, false] {
804 let view = ListViewArray::try_new(
805 elements.clone(),
806 primitive_of(offsets[..len].iter().copied(), ptype, &mut ctx)?,
807 primitive_of(offsets.windows(2).map(|w| w[1] - w[0]), ptype, &mut ctx)?,
808 validity.clone(),
809 &mut ctx,
810 )?;
811 let view = unsafe { view.with_zero_copy_to_list(zero_copy_to_list) };
813 let rebuilt =
814 view.rebuild(ListViewRebuildMode::MakeExactWithEmptyNulls, &mut ctx)?;
815 assert!(rebuilt.is_zero_copy_to_list());
816 assert_arrays_eq!(
817 rebuilt.elements().clone(),
818 expected_elements.clone(),
819 &mut ctx
820 );
821 assert_arrays_eq!(
823 rebuilt.offsets().cast(u32_dtype.clone())?,
824 PrimitiveArray::from_iter(expected_offsets[..len].iter().copied()),
825 &mut ctx
826 );
827 assert_arrays_eq!(
828 rebuilt.sizes().cast(u32_dtype.clone())?,
829 expected_sizes.clone(),
830 &mut ctx
831 );
832 assert_arrays_eq!(rebuilt, view, &mut ctx);
833 }
834 }
835 Ok(())
836 }
837
838 #[test]
839 fn test_rebuild_flatten_removes_overlaps() -> VortexResult<()> {
840 let mut ctx = SESSION.create_execution_ctx();
841 let elements = PrimitiveArray::from_iter(vec![1i32, 2, 3]).into_array();
845 let offsets = PrimitiveArray::from_iter(vec![0u32, 1]).into_array();
846 let sizes = PrimitiveArray::from_iter(vec![3u32, 2]).into_array();
847
848 let listview =
849 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
850
851 let mut ctx = SESSION.create_execution_ctx();
852 let flattened = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
853
854 assert_eq!(flattened.elements().len(), 5);
857
858 assert_eq!(flattened.offset_at(0, &mut ctx), 0);
860 assert_eq!(flattened.size_at(0, &mut ctx), 3);
861 assert_eq!(flattened.offset_at(1, &mut ctx), 3);
862 assert_eq!(flattened.size_at(1, &mut ctx), 2);
863
864 assert_arrays_eq!(
866 flattened.list_elements_at(0, &mut ctx)?,
867 PrimitiveArray::from_iter([1i32, 2, 3]),
868 &mut ctx
869 );
870
871 assert_arrays_eq!(
872 flattened.list_elements_at(1, &mut ctx)?,
873 PrimitiveArray::from_iter([2i32, 3]),
874 &mut ctx
875 );
876 Ok(())
877 }
878
879 #[test]
880 fn test_rebuild_flatten_with_nullable() -> VortexResult<()> {
881 let mut ctx = SESSION.create_execution_ctx();
882 use crate::arrays::BoolArray;
883
884 let elements = PrimitiveArray::from_iter(vec![1i32, 2, 3]).into_array();
886 let offsets = PrimitiveArray::from_iter(vec![0u32, 1, 2]).into_array();
887 let sizes = PrimitiveArray::from_iter(vec![2u32, 1, 1]).into_array();
888 let validity = Validity::Array(
889 BoolArray::new(
890 BitBuffer::from(vec![true, false, true]),
891 Validity::NonNullable,
892 )
893 .into_array(),
894 );
895
896 let listview = ListViewArray::new(elements, offsets, sizes, validity, &mut ctx);
897
898 let mut ctx = SESSION.create_execution_ctx();
899 let flattened = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
900
901 assert_eq!(flattened.dtype().nullability(), Nullability::Nullable);
903 assert!(flattened.validity()?.execute_is_valid(0, &mut ctx)?);
904 assert!(!flattened.validity()?.execute_is_valid(1, &mut ctx)?);
905 assert!(flattened.validity()?.execute_is_valid(2, &mut ctx)?);
906
907 assert_arrays_eq!(
909 flattened.list_elements_at(0, &mut ctx)?,
910 PrimitiveArray::from_iter([1i32, 2]),
911 &mut ctx
912 );
913
914 assert_arrays_eq!(
915 flattened.list_elements_at(2, &mut ctx)?,
916 PrimitiveArray::from_iter([3i32]),
917 &mut ctx
918 );
919 Ok(())
920 }
921
922 #[test]
923 fn test_rebuild_flatten_null_row_uses_valid_empty_range() -> VortexResult<()> {
924 let elements = PrimitiveArray::from_iter(vec![1i32, 2, 3, 4]).into_array();
925 let offsets = PrimitiveArray::from_iter(vec![0u32, 1, 2]).into_array();
926 let sizes = PrimitiveArray::from_iter(vec![1u32, 2, 2]).into_array();
927 let validity = Validity::from_iter([true, false, true]);
928
929 let listview = unsafe { ListViewArray::new_unchecked(elements, offsets, sizes, validity) };
931
932 let mut ctx = SESSION.create_execution_ctx();
933 let flattened = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
934
935 assert_eq!(flattened.offset_at(0, &mut ctx), 0);
936 assert_eq!(flattened.size_at(0, &mut ctx), 1);
937 assert_eq!(flattened.offset_at(1, &mut ctx), 1);
938 assert_eq!(flattened.size_at(1, &mut ctx), 0);
939 assert_eq!(flattened.offset_at(2, &mut ctx), 1);
940 assert_eq!(flattened.size_at(2, &mut ctx), 2);
941 assert!(flattened.validity()?.execute_is_valid(0, &mut ctx)?);
942 assert!(!flattened.validity()?.execute_is_valid(1, &mut ctx)?);
943 assert!(flattened.validity()?.execute_is_valid(2, &mut ctx)?);
944
945 assert_arrays_eq!(
946 flattened.list_elements_at(0, &mut ctx)?,
947 PrimitiveArray::from_iter([1i32]),
948 &mut ctx
949 );
950 assert_arrays_eq!(
951 flattened.list_elements_at(2, &mut ctx)?,
952 PrimitiveArray::from_iter([3i32, 4]),
953 &mut ctx
954 );
955 Ok(())
956 }
957
958 #[rstest]
959 #[case::zero_copy_to_list(ListViewRebuildMode::MakeZeroCopyToList)]
960 #[case::trim_elements(ListViewRebuildMode::TrimElements)]
961 #[case::make_exact(ListViewRebuildMode::MakeExact)]
962 #[case::make_exact_with_empty_nulls(ListViewRebuildMode::MakeExactWithEmptyNulls)]
963 fn test_rebuild_empty_drops_elements(#[case] mode: ListViewRebuildMode) -> VortexResult<()> {
964 let mut ctx = SESSION.create_execution_ctx();
965 let listview = ListViewArray::new(
967 PrimitiveArray::from_iter([1i32, 2, 3]).into_array(),
968 PrimitiveArray::from_iter::<[u32; 0]>([]).into_array(),
969 PrimitiveArray::from_iter::<[u32; 0]>([]).into_array(),
970 Validity::NonNullable,
971 &mut ctx,
972 );
973
974 let rebuilt = listview.rebuild(mode, &mut ctx)?;
975 assert!(rebuilt.is_empty());
976 assert_eq!(rebuilt.elements().len(), 0);
977 assert!(rebuilt.is_zero_copy_to_list());
978 Ok(())
979 }
980
981 #[test]
982 fn test_rebuild_trim_elements_basic() -> VortexResult<()> {
983 let mut ctx = SESSION.create_execution_ctx();
984 let elements =
992 PrimitiveArray::from_iter(vec![99i32, 98, 1, 2, 97, 3, 4, 96, 95]).into_array();
993 let offsets = PrimitiveArray::from_iter(vec![2u32, 5]).into_array();
994 let sizes = PrimitiveArray::from_iter(vec![2u32, 2]).into_array();
995
996 let listview =
997 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
998
999 let mut ctx = SESSION.create_execution_ctx();
1000 let trimmed = listview.rebuild(ListViewRebuildMode::TrimElements, &mut ctx)?;
1001
1002 assert_eq!(trimmed.elements().len(), 5);
1004
1005 assert_eq!(trimmed.offset_at(0, &mut ctx), 0);
1007 assert_eq!(trimmed.size_at(0, &mut ctx), 2);
1008 assert_eq!(trimmed.offset_at(1, &mut ctx), 3);
1009 assert_eq!(trimmed.size_at(1, &mut ctx), 2);
1010
1011 assert_arrays_eq!(
1013 trimmed.list_elements_at(0, &mut ctx)?,
1014 PrimitiveArray::from_iter([1i32, 2]),
1015 &mut ctx
1016 );
1017
1018 assert_arrays_eq!(
1019 trimmed.list_elements_at(1, &mut ctx)?,
1020 PrimitiveArray::from_iter([3i32, 4]),
1021 &mut ctx
1022 );
1023
1024 let all_elements = trimmed
1026 .elements()
1027 .clone()
1028 .execute::<PrimitiveArray>(&mut ctx)?;
1029 assert_eq!(all_elements.execute_scalar(2, &mut ctx)?, 97i32.into());
1030 Ok(())
1031 }
1032
1033 #[test]
1034 fn test_rebuild_flatten_large_lists_with_piecewise_indices() -> VortexResult<()> {
1035 let mut ctx = SESSION.create_execution_ctx();
1036 let elements = PrimitiveArray::from_iter(0i32..300).into_array();
1037 let offsets = PrimitiveArray::from_iter(vec![10u32, 0]).into_array();
1038 let sizes = PrimitiveArray::from_iter(vec![150u32, 130]).into_array();
1039 let listview =
1040 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
1041
1042 let flattened = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
1043
1044 assert_eq!(flattened.elements().len(), 280);
1045 assert_eq!(flattened.offset_at(0, &mut ctx), 0);
1046 assert_eq!(flattened.size_at(0, &mut ctx), 150);
1047 assert_eq!(flattened.offset_at(1, &mut ctx), 150);
1048 assert_eq!(flattened.size_at(1, &mut ctx), 130);
1049
1050 assert_arrays_eq!(
1051 flattened.list_elements_at(0, &mut ctx)?,
1052 PrimitiveArray::from_iter(10i32..160),
1053 &mut ctx
1054 );
1055 assert_arrays_eq!(
1056 flattened.list_elements_at(1, &mut ctx)?,
1057 PrimitiveArray::from_iter(0i32..130),
1058 &mut ctx
1059 );
1060 Ok(())
1061 }
1062
1063 #[test]
1064 fn test_rebuild_with_trailing_nulls_regression() -> VortexResult<()> {
1065 let mut ctx = SESSION.create_execution_ctx();
1066 let elements = PrimitiveArray::from_iter(vec![1i32, 2, 3, 4]).into_array();
1072 let offsets = PrimitiveArray::from_iter(vec![0u32, 2, 0, 0]).into_array();
1073 let sizes = PrimitiveArray::from_iter(vec![2u32, 2, 0, 0]).into_array();
1074 let validity = Validity::from_iter(vec![true, true, false, false]);
1075
1076 let listview = ListViewArray::new(elements, offsets, sizes, validity, &mut ctx);
1077
1078 let mut ctx = SESSION.create_execution_ctx();
1080 let rebuilt = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
1081 assert!(rebuilt.is_zero_copy_to_list());
1082
1083 assert_eq!(rebuilt.offset_at(0, &mut ctx), 0);
1086 assert_eq!(rebuilt.offset_at(1, &mut ctx), 2);
1087 assert_eq!(rebuilt.offset_at(2, &mut ctx), 4); assert_eq!(rebuilt.offset_at(3, &mut ctx), 4); assert_eq!(rebuilt.size_at(0, &mut ctx), 2);
1092 assert_eq!(rebuilt.size_at(1, &mut ctx), 2);
1093 assert_eq!(rebuilt.size_at(2, &mut ctx), 0); assert_eq!(rebuilt.size_at(3, &mut ctx), 0); let exact = rebuilt.rebuild(ListViewRebuildMode::MakeExact, &mut ctx)?;
1099
1100 assert!(exact.is_valid(0, &mut ctx)?);
1102 assert!(exact.is_valid(1, &mut ctx)?);
1103 assert!(!exact.is_valid(2, &mut ctx)?);
1104 assert!(!exact.is_valid(3, &mut ctx)?);
1105
1106 assert_arrays_eq!(
1108 exact.list_elements_at(0, &mut ctx)?,
1109 PrimitiveArray::from_iter([1i32, 2]),
1110 &mut ctx
1111 );
1112
1113 assert_arrays_eq!(
1114 exact.list_elements_at(1, &mut ctx)?,
1115 PrimitiveArray::from_iter([3i32, 4]),
1116 &mut ctx
1117 );
1118 Ok(())
1119 }
1120
1121 #[test]
1124 fn test_rebuild_trim_elements_offsets_wider_than_sizes() -> VortexResult<()> {
1125 let mut ctx = SESSION.create_execution_ctx();
1126 let mut elems = vec![0i32; 70_005];
1127 elems[70_000] = 10;
1128 elems[70_001] = 20;
1129 elems[70_002] = 30;
1130 elems[70_003] = 40;
1131 let elements = PrimitiveArray::from_iter(elems).into_array();
1132 let offsets = PrimitiveArray::from_iter(vec![70_000u32, 70_002]).into_array();
1133 let sizes = PrimitiveArray::from_iter(vec![2u16, 2]).into_array();
1134
1135 let listview =
1136 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
1137 let mut ctx = SESSION.create_execution_ctx();
1138 let trimmed = listview.rebuild(ListViewRebuildMode::TrimElements, &mut ctx)?;
1139 assert_arrays_eq!(
1140 trimmed.list_elements_at(1, &mut ctx)?,
1141 PrimitiveArray::from_iter([30i32, 40]),
1142 &mut ctx
1143 );
1144 Ok(())
1145 }
1146
1147 #[test]
1150 fn test_rebuild_trim_elements_sizes_wider_than_offsets() -> VortexResult<()> {
1151 let mut ctx = SESSION.create_execution_ctx();
1152 let mut elems = vec![0i32; 70_001];
1153 elems[3] = 30;
1154 elems[4] = 40;
1155 let elements = PrimitiveArray::from_iter(elems).into_array();
1156 let offsets = PrimitiveArray::from_iter(vec![1u16, 3]).into_array();
1157 let sizes = PrimitiveArray::from_iter(vec![70_000u32, 2]).into_array();
1158
1159 let listview =
1160 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
1161 let mut ctx = SESSION.create_execution_ctx();
1162 let trimmed = listview.rebuild(ListViewRebuildMode::TrimElements, &mut ctx)?;
1163 assert_arrays_eq!(
1164 trimmed.list_elements_at(1, &mut ctx)?,
1165 PrimitiveArray::from_iter([30i32, 40]),
1166 &mut ctx
1167 );
1168 Ok(())
1169 }
1170
1171 #[test]
1174 fn test_rebuild_preserves_signed_offset_and_size_types() -> VortexResult<()> {
1175 let mut ctx = SESSION.create_execution_ctx();
1176 use crate::arrays::listview::ListViewArraySlotsExt;
1177 use crate::dtype::PType;
1178
1179 let elements = PrimitiveArray::from_iter(vec![1i32, 2, 3]).into_array();
1181 let offsets = PrimitiveArray::from_iter(vec![0i32, 1]).into_array();
1182 let sizes = PrimitiveArray::from_iter(vec![3i16, 2]).into_array();
1183
1184 let listview =
1185 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
1186 let mut ctx = SESSION.create_execution_ctx();
1187 let rebuilt = listview.rebuild(ListViewRebuildMode::MakeZeroCopyToList, &mut ctx)?;
1188
1189 assert_arrays_eq!(
1191 rebuilt.list_elements_at(0, &mut ctx)?,
1192 PrimitiveArray::from_iter([1i32, 2, 3]),
1193 &mut ctx
1194 );
1195 assert_arrays_eq!(
1196 rebuilt.list_elements_at(1, &mut ctx)?,
1197 PrimitiveArray::from_iter([2i32, 3]),
1198 &mut ctx
1199 );
1200
1201 assert_eq!(rebuilt.offsets().dtype().as_ptype(), PType::I32);
1203 assert_eq!(rebuilt.sizes().dtype().as_ptype(), PType::I16);
1204 Ok(())
1205 }
1206
1207 #[test]
1210 fn heuristic_small_lists_use_take() {
1211 assert!(ListViewArray::should_use_take(127_000, 1_000));
1213 assert!(!ListViewArray::should_use_take(128_000, 1_000));
1215 }
1216
1217 #[test]
1220 fn test_rebuild_trim_elements_sum_overflows_type() -> VortexResult<()> {
1221 let mut ctx = SESSION.create_execution_ctx();
1222 let elements = PrimitiveArray::from_iter(vec![0i32; 261]).into_array();
1223 let offsets = PrimitiveArray::from_iter(vec![215u8, 0]).into_array();
1224 let sizes = PrimitiveArray::from_iter(vec![46u8, 10]).into_array();
1225
1226 let listview =
1227 ListViewArray::new(elements, offsets, sizes, Validity::NonNullable, &mut ctx);
1228 let mut ctx = SESSION.create_execution_ctx();
1229 let trimmed = listview.rebuild(ListViewRebuildMode::TrimElements, &mut ctx)?;
1230
1231 assert_arrays_eq!(trimmed, listview, &mut ctx);
1233 Ok(())
1234 }
1235}