Skip to main content

vortex_array/arrays/listview/
rebuild.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use 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
35/// The widened offset type used for a rebuilt, zero-copy-to-list array.
36///
37/// Offsets are widened to at least 32 bits (Arrow only permits 32/64-bit list offsets) while
38/// preserving signedness, since a signed result keeps the array zero-copyable to Arrow's
39/// `ListArray`.
40fn 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
50/// Density threshold to decide whether to rebuild a sparse `ListViewArray`.
51///
52/// A `ListViewArray` can accumulate unreferenced bytes in its `elements` buffer after
53/// metadata-only operations like `take` and `filter`. When density (referenced fraction of `elements`)
54/// falls below this threshold, the benefits of a rebuild may outweigh its cost.
55///
56/// This is a somewhat arbitrary rule-of-thumb and may be suboptimal depending on different use cases and
57/// list element dtypes.
58pub const DEFAULT_REBUILD_DENSITY_THRESHOLD: f32 = 0.1;
59
60/// Waste threshold to decide whether to trim a zero-copy-to-list `ListViewArray`.
61///
62/// A zero-copy-to-list array has no overlaps and no interior gaps, so its only unreferenced bytes
63/// are leading and trailing elements. Trimming those is much cheaper than a full rebuild (a lazy
64/// `elements` slice plus an `O(num_lists)` offset adjustment, with no element data copy), so we use
65/// a more aggressive threshold than [`DEFAULT_REBUILD_DENSITY_THRESHOLD`].
66///
67/// When the unreferenced (leading + trailing) fraction of `elements` exceeds this threshold, we trim.
68pub const DEFAULT_TRIM_ELEMENTS_THRESHOLD: f32 = 0.05;
69
70/// Modes for rebuilding a [`ListViewArray`].
71pub enum ListViewRebuildMode {
72    /// Removes all unused data and flattens out all list data, such that the array is zero-copyable
73    /// to a [`ListArray`].
74    ///
75    /// This mode will deduplicate all overlapping list views, such that the [`ListViewArray`] looks
76    /// like a [`ListArray`] but with an additional `sizes` array.
77    ///
78    /// [`ListArray`]: crate::arrays::ListArray
79    MakeZeroCopyToList,
80
81    /// Removes any leading or trailing elements that are unused / not referenced by any views in
82    /// the [`ListViewArray`].
83    ///
84    /// If the referenced `[start, end)` bounds are already known, prefer calling
85    /// [`trim_elements`](ListViewArray::trim_elements) directly to avoid recomputing them.
86    TrimElements,
87
88    /// Equivalent to `MakeZeroCopyToList` plus `TrimElements`.
89    ///
90    /// An array that is not yet zero-copy to a [`ListArray`] is copied with only its valid lists'
91    /// elements, and its null lists come out empty. One that already is zero-copy only loses the
92    /// elements before its first list and after its last, so its null lists keep theirs; use
93    /// [`MakeExactWithEmptyNulls`](Self::MakeExactWithEmptyNulls) to drop those too.
94    ///
95    /// This is useful when concatenating multiple [`ListViewArray`]s together to create a new
96    /// [`ListViewArray`] that is also zero-copy to a [`ListArray`].
97    ///
98    /// [`ListArray`]: crate::arrays::ListArray
99    MakeExact,
100
101    /// Equivalent to `MakeExact`, but the null lists of an array that is already zero-copy to a
102    /// [`ListArray`] come out empty as well, so only the valid lists' elements are left.
103    ///
104    /// This is useful for a function that must not see elements no valid list shows, such as one
105    /// that can fail on a value. An array that is already zero-copy to a [`ListArray`] keeps its
106    /// offsets' and sizes' types, and is returned as it is when there is nothing to drop.
107    ///
108    /// [`ListArray`]: crate::arrays::ListArray
109    MakeExactWithEmptyNulls,
110
111    // TODO(connor)[ListView]: Implement some version of this.
112    /// Finds the shortest packing / overlapping of list elements.
113    ///
114    /// This problem is known to be NP-hard, so maybe when someone proves that P=NP we can implement
115    /// this algorithm (but in all seriousness there are many approximate algorithms that could
116    /// work well here).
117    OverlapCompression,
118}
119
120impl ListViewArray {
121    /// Rebuilds the [`ListViewArray`] according to the specified mode.
122    pub fn rebuild(
123        &self,
124        mode: ListViewRebuildMode,
125        ctx: &mut ExecutionCtx,
126    ) -> VortexResult<ListViewArray> {
127        if self.is_empty() {
128            // An empty array uses none of its elements, so every mode drops them.
129            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    /// Rebuilds a non-empty [`ListViewArray`] over only the elements that valid lists reference:
146    /// nothing before the first list, after the last, between lists or under a null list.
147    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        // The lists are back to back, so the last one ends where the referenced elements do.
156        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        // Offsets are never negative, so they are rebuilt unsigned and reinterpreted back.
168        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    /// [`MakeExactWithEmptyNulls`](ListViewRebuildMode::MakeExactWithEmptyNulls) for an array that
176    /// is zero-copy to a list, whose lists start at `starts` and end at `end`.
177    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        // A list holds elements if and only if the next one starts later.
186        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        // SAFETY: the lists stay back to back and in order over the elements kept: each valid list
211        // keeps its elements, and each null list that held elements is now empty.
212        Ok(unsafe {
213            ListViewArray::new_unchecked(elements, offsets, sizes, self.validity()?)
214                .with_zero_copy_to_list(true)
215        })
216    }
217
218    /// Rebuilds a [`ListViewArray`], removing all data overlaps and creating a flattened layout.
219    ///
220    /// This is useful when the `elements` child array of the [`ListViewArray`] might have
221    /// overlapping, duplicate, and garbage data, and we want to have fully sequential data like
222    /// a [`ListArray`].
223    ///
224    /// [`ListArray`]: crate::arrays::ListArray
225    fn rebuild_zero_copy_to_list(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListViewArray> {
226        if self.is_zero_copy_to_list() {
227            // Note that since everything in `ListViewArray` is `Arc`ed, this is quite cheap.
228            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        // One of the main purposes behind adding this "zero-copyable to `ListArray`" optimization
235        // is that we want to pass data to systems that expect Arrow data.
236        // The arrow specification only allows for `i32` and `i64` offset and sizes types, so in
237        // order to also make `ListView` zero-copyable to **Arrow**'s `ListArray` (not just Vortex's
238        // `ListArray`), we rebuild the offsets as 32-bit or 64-bit integer types.
239        // TODO(connor)[ListView]: This is true for `sizes` as well, we should do this conversion
240        // for sizes as well.
241        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    /// Picks between [`rebuild_with_take`](Self::rebuild_with_take) and
253    /// [`rebuild_with_piecewise`](Self::rebuild_with_piecewise) based on average list size.
254    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    /// Returns `true` when we are confident that `rebuild_with_take` will
274    /// outperform `rebuild_with_piecewise`.
275    ///
276    /// Take is dramatically faster for small lists (often 10-100×) because it
277    /// avoids per-list builder overhead. LBL is the safer default for larger
278    /// lists since its sequential memcpy scales well. We only choose take when
279    /// the average list size is small enough that take clearly dominates.
280    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    /// Rebuilds elements using a single bulk `take`: collect all element indices into a flat
289    /// `BufferMut<u64>`, perform a single `take`.
290    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        // Resolve validity to a mask once instead of probing it per row: `execute_is_valid`
313        // executes a scalar on every call for array-backed validity, which is O(len) work repeated
314        // `len` times.
315        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        // Built unsigned; reinterpret back to the signed-preserving result types.
338        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        // SAFETY: offsets are sequential and non-overlapping, all (offset, size) pairs reference
346        // valid elements, and the validity array is preserved from the original.
347        Ok(unsafe {
348            ListViewArray::new_unchecked(elements, offsets, sizes, self.validity()?)
349                .with_zero_copy_to_list(true)
350        })
351    }
352
353    /// Rebuilds elements using one contiguous-run take over the element child.
354    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        // SAFETY: range starts and lengths are derived from valid ListView metadata; elements_len
397        // is the sum of all generated range lengths. Multiplier 1 preserves contiguous ranges.
398        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        // Built unsigned; reinterpret back to the signed-preserving result types.
410        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        // SAFETY: offsets are sequential and non-overlapping, all (offset, size) pairs reference
418        // valid elements, and validity is preserved from the original array.
419        Ok(unsafe {
420            ListViewArray::new_unchecked(elements, offsets, sizes, validity)
421                .with_zero_copy_to_list(true)
422        })
423    }
424
425    /// Rebuilds a [`ListViewArray`] by trimming any unused / unreferenced leading and trailing
426    /// elements, which is defined as a contiguous run of values in the `elements` array that are
427    /// not referenced by any views in the corresponding [`ListViewArray`].
428    fn rebuild_trim_elements(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListViewArray> {
429        let (start, end) = self.referenced_element_bounds(ctx)?;
430
431        // SAFETY: we calculated valid start and end bounds
432        unsafe { self.trim_elements(start, end) }
433    }
434
435    /// Unsafely trims `elements` to the referenced half-open range `[start, end)`, adjusting every offset
436    /// down by `start`. The result preserves the original `is_zero_copy_to_list` flag.
437    ///
438    /// # SAFETY
439    ///
440    /// `start` must be the minimum value of `offsets`, and end should be the maximum value of `offsets[i] + size[i]`
441    /// over all indices `i` of offsets. Otherwise, `offsets` and `sizes` may hold references to elements that no longer exist
442    /// and the array will be corrupted.
443    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        // SAFETY: The only thing we changed was the elements (which we verify through mins and
461        // maxes that all adjusted offsets + sizes are within the correct bounds), so the parameters
462        // are valid. And if the original array was zero-copyable to list, trimming elements doesn't
463        // change that property.
464        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            // When we completely rebuild the `ListViewArray`, we get the benefit that we also trim
480            // any leading and trailing garbage data.
481            self.rebuild_zero_copy_to_list(ctx)
482        }
483    }
484}
485
486/// The sizes with the lists in `runs` emptied.
487fn 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        // SAFETY: the cases marked zero-copy to a list have sorted lists with nothing between them.
679        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        // SAFETY: the lists are sorted with nothing between them.
716        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    /// `values` as a primitive array of `ptype`.
725    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    /// Random lists with elements before, after and under null lists, rebuilt as a `ListArray`
738    /// and as list views with and without the zero-copy flag, against a reference that gathers
739    /// each valid list's elements back to back.
740    #[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                // Validity that starts mid-byte.
759                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                // SAFETY: the views are a `ListArray`'s lists, sorted with nothing between them.
812                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                // The copy widens the offsets, so compare their values.
822                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        // Create a list view with overlapping lists: [A, B, C]
842        // List 0: offset=0, size=3 -> [A, B, C]
843        // List 1: offset=1, size=2 -> [B, C] (overlaps with List 0)
844        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        // After flatten: elements should be [A, B, C, B, C] = [1, 2, 3, 2, 3]
855        // Lists should be sequential with no overlaps
856        assert_eq!(flattened.elements().len(), 5);
857
858        // Offsets should be sequential
859        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        // Verify the data is correct
865        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        // Create a nullable list view with a null list
885        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        // Verify nullability is preserved
902        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        // Verify valid lists contain correct data
908        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        // SAFETY: all source ranges are valid, including the null row's non-empty range.
930        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        // No lists, but three elements left in the buffer.
966        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        // Test trimming both leading and trailing unused elements while preserving gaps in the
985        // middle.
986        // Elements: [_, _, A, B, _, C, D, _, _]
987        //            0  1  2  3  4  5  6  7  8
988        // List 0: offset=2, size=2 -> [A, B]
989        // List 1: offset=5, size=2 -> [C, D]
990        // Should trim to: [A, B, _, C, D] with adjusted offsets.
991        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        // After trimming: elements should be [A, B, _, C, D] = [1, 2, 97, 3, 4].
1003        assert_eq!(trimmed.elements().len(), 5);
1004
1005        // Offsets should be adjusted: old offset 2 -> new offset 0, old offset 5 -> new offset 3.
1006        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        // Verify the data is correct.
1012        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        // Note that element at index 2 (97) is preserved as a gap.
1025        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        // Regression test for issue #5412
1067        // Tests that zero-copy-to-list arrays with trailing NULLs correctly calculate
1068        // offsets for NULL items to maintain no-overlap invariant
1069
1070        // Create a ListViewArray with trailing NULLs
1071        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        // First rebuild to make it zero-copy-to-list
1079        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        // Verify NULL items have correct offsets (should not reuse previous offsets)
1084        // After rebuild: offsets should be [0, 2, 4, 4] for zero-copy-to-list
1085        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); // NULL should be at position 4
1088        assert_eq!(rebuilt.offset_at(3, &mut ctx), 4); // Second NULL also at position 4
1089
1090        // All sizes should be correct
1091        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); // NULL has size 0
1094        assert_eq!(rebuilt.size_at(3, &mut ctx), 0); // NULL has size 0
1095
1096        // Now rebuild with MakeExact (which calls naive_rebuild then trim_elements)
1097        // This should not panic (issue #5412)
1098        let exact = rebuilt.rebuild(ListViewRebuildMode::MakeExact, &mut ctx)?;
1099
1100        // Verify the result is still valid
1101        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        // Verify data is preserved
1107        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    /// Regression test for <https://github.com/vortex-data/vortex/issues/6773>.
1122    /// u32 offsets exceed u16::MAX, so u16 sizes are widened to u32 for the add.
1123    #[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    /// Regression test for <https://github.com/vortex-data/vortex/issues/6773>.
1148    /// u32 sizes exceed u16::MAX, so u16 offsets are widened to u32 for the add.
1149    #[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    /// Rebuild with signed offsets/sizes: exercises the unsigned-reinterpret read path and asserts
1172    /// the result offset/size dtypes preserve signedness (widened to >=32-bit for offsets).
1173    #[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        // Overlapping lists force an actual rebuild rather than the zero-copy fast path.
1180        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        // Values: [1,2,3] and [2,3].
1190        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        // Signed input -> signed result (offsets widened to i32, sizes kept i16).
1202        assert_eq!(rebuilt.offsets().dtype().as_ptype(), PType::I32);
1203        assert_eq!(rebuilt.sizes().dtype().as_ptype(), PType::I16);
1204        Ok(())
1205    }
1206
1207    // ── should_use_take heuristic tests ────────────────────────────────────
1208
1209    #[test]
1210    fn heuristic_small_lists_use_take() {
1211        // avg = 127 → take
1212        assert!(ListViewArray::should_use_take(127_000, 1_000));
1213        // avg = 128 → LBL
1214        assert!(!ListViewArray::should_use_take(128_000, 1_000));
1215    }
1216
1217    /// Regression test for <https://github.com/vortex-data/vortex/issues/6973>.
1218    /// Both offsets and sizes are u8, and offset + size exceeds u8::MAX.
1219    #[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        // min(offsets) = 0, so nothing to trim; output should equal input.
1232        assert_arrays_eq!(trimmed, listview, &mut ctx);
1233        Ok(())
1234    }
1235}