vortex_array/arrays/list/
rebuild.rs1use 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 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 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 Ok(unsafe { ListArray::new_unchecked(elements, offsets, self.list_validity()) })
78 }
79}
80
81pub(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
97pub(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 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 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 referenced.filter(Mask::from_buffer_with_slices(bits.freeze(), kept))?
156 }
157 };
158 Ok((elements, offsets))
159}