Skip to main content

vortex_array/arrays/list/
rebuild.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use vortex_buffer::BitBuffer;
5use vortex_buffer::BitBufferMut;
6use vortex_buffer::BufferAllocatorRef;
7use vortex_buffer::BufferMut;
8use vortex_error::VortexExpect;
9use vortex_error::VortexResult;
10use vortex_mask::AllOr;
11use vortex_mask::Mask;
12
13use crate::ArrayRef;
14use crate::ExecutionCtx;
15use crate::IntoArray;
16use crate::arrays::ListArray;
17use crate::arrays::PrimitiveArray;
18use crate::arrays::list::ListArrayExt;
19use crate::arrays::list::ListArraySlotsExt;
20use crate::arrays::primitive::PrimitiveArrayExt;
21use crate::dtype::IntegerPType;
22use crate::dtype::PType;
23use crate::match_each_unsigned_integer_ptype;
24use crate::validity::Validity;
25
26impl ListArray {
27    /// Compacts the [`ListArray`] to only the elements that valid lists reference: nothing before
28    /// the first list, after the last or under a null list.
29    ///
30    /// Null lists come out empty, the offsets start at 0, end at the length of the elements and
31    /// keep their type, and the validity is kept. An array with nothing to drop is returned as it
32    /// is.
33    pub fn compact(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListArray> {
34        let validity = self.list_validity();
35        if validity.definitely_no_nulls()
36            && self.offset_at(0, ctx)? == 0
37            && self.offset_at(self.len(), ctx)? == self.elements().len()
38        {
39            return Ok(self.clone());
40        }
41
42        let offsets = self.offsets().clone().execute::<PrimitiveArray>(ctx)?;
43        let offsets_ptype = offsets.ptype();
44        // Offsets are never negative, so they are rebuilt unsigned and reinterpreted back.
45        let offsets = offsets.reinterpret_cast(offsets_ptype.to_unsigned());
46        let valid = validity.execute_mask(self.len(), ctx)?;
47        match_each_unsigned_integer_ptype!(offsets.ptype(), |O| {
48            self.rebuild_with_valid(offsets.as_slice::<O>(), offsets_ptype, &valid, ctx)
49        })
50    }
51
52    fn rebuild_with_valid<O: IntegerPType>(
53        &self,
54        offsets: &[O],
55        offsets_ptype: PType,
56        valid: &Mask,
57        ctx: &mut ExecutionCtx,
58    ) -> VortexResult<ListArray> {
59        let (starts, end) = (&offsets[..self.len()], offsets[self.len()].as_());
60        let null_runs =
61            null_runs_holding_elements(valid, |index| offsets[index] != offsets[index + 1]);
62        if null_runs.is_empty() && offsets[0].as_() == 0 && end == self.elements().len() {
63            return Ok(self.clone());
64        }
65
66        let (elements, mut offsets) =
67            drop_unreferenced_elements(self.elements(), starts, end, &null_runs, ctx.allocator())?;
68        offsets.push(
69            num_traits::cast(elements.len())
70                .vortex_expect("the elements kept fit the offsets' type"),
71        );
72        let offsets = PrimitiveArray::new(offsets.freeze(), Validity::NonNullable)
73            .reinterpret_cast(offsets_ptype)
74            .into_array();
75        // SAFETY: the offsets keep their type, start at 0, never decrease and end at the length of
76        // the elements, which are the valid lists' elements in order.
77        Ok(unsafe { ListArray::new_unchecked(elements, offsets, self.list_validity()) })
78    }
79}
80
81/// The runs of null lists that hold elements, given which lists hold elements.
82pub(crate) fn null_runs_holding_elements(
83    valid: &Mask,
84    mut holds_elements: impl FnMut(usize) -> bool,
85) -> Vec<(usize, usize)> {
86    match valid.bit_buffer() {
87        AllOr::All => Vec::new(),
88        AllOr::None if (0..valid.len()).any(&mut holds_elements) => vec![(0, valid.len())],
89        AllOr::None => Vec::new(),
90        AllOr::Some(valid) => BitBuffer::collect_bool(valid.len(), &mut holds_elements)
91            .bitand_not(valid)
92            .set_slices()
93            .collect(),
94    }
95}
96
97/// Drops the elements before the first of the lists laid out back to back, after the last, and
98/// under the runs of null lists from [`null_runs_holding_elements`], which come out empty.
99///
100/// `end` is where the last list ends. It is a `usize` rather than an `O` because a list view's last
101/// list can end past what its offsets' type holds: with `u8` offsets `[1, 5, 105]` and sizes
102/// `[4, 100, 200]`, it ends at 305.
103///
104/// Returns the elements kept and where each list now starts. A [`ListArray`] needs one more offset,
105/// where its last list ends, so the buffer has room to push it without reallocating.
106pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
107    elements: &ArrayRef,
108    starts: &[O],
109    end: usize,
110    null_runs: &[(usize, usize)],
111    allocator: &BufferAllocatorRef,
112) -> VortexResult<(ArrayRef, BufferMut<O>)> {
113    let start_of = |index: usize| starts.get(index).map_or(end, |start| start.as_());
114    let first = start_of(0);
115    // The ranges of elements kept, counted from the first list's start.
116    let mut kept = Vec::with_capacity(null_runs.len() + 1);
117    let mut kept_start = 0;
118    let mut offsets = BufferMut::with_capacity_in(starts.len() + 1, allocator.clone());
119    offsets.extend_from_slice(starts);
120    let mut dropped = starts.first().copied().unwrap_or_else(O::zero);
121    let mut from = 0;
122    for &(run_start, run_end) in null_runs {
123        if kept_start < start_of(run_start) - first {
124            kept.push((kept_start, start_of(run_start) - first));
125        }
126        kept_start = start_of(run_end) - first;
127
128        for offset in &mut offsets[from..run_start] {
129            *offset = *offset - dropped;
130        }
131        offsets[run_start..run_end].fill(starts[run_start] - dropped);
132        // A run at the end leaves no list after it to move down.
133        if let Some(&next) = starts.get(run_end) {
134            dropped += next - starts[run_start];
135        }
136        from = run_end;
137    }
138    if kept_start < end - first {
139        kept.push((kept_start, end - first));
140    }
141    for offset in &mut offsets[from..] {
142        *offset = *offset - dropped;
143    }
144
145    let referenced = elements.slice(first..end)?;
146    let elements = match kept[..] {
147        [] => referenced.slice(0..0)?,
148        [(start, stop)] => referenced.slice(start..stop)?,
149        _ => {
150            let mut bits = BitBufferMut::new_unset(end - first);
151            for &(start, stop) in &kept {
152                bits.fill_range(start, stop, true);
153            }
154            // With the ranges cached on the mask, the filter copies the elements range by range.
155            referenced.filter(Mask::from_buffer_with_slices(bits.freeze(), kept))?
156        }
157    };
158    Ok((elements, offsets))
159}