vortex_array/arrays/list/
array.rs1use std::fmt::Display;
5use std::fmt::Formatter;
6use std::sync::Arc;
7
8use num_traits::AsPrimitive;
9use vortex_error::VortexExpect;
10use vortex_error::VortexResult;
11use vortex_error::vortex_bail;
12use vortex_error::vortex_ensure;
13use vortex_error::vortex_ensure_eq;
14use vortex_error::vortex_panic;
15
16use crate::ArrayRef;
17use crate::ArraySlots;
18use crate::Canonical;
19use crate::ExecutionCtx;
20use crate::IntoArray;
21use crate::aggregate_fn::NumericalAggregateOpts;
22use crate::aggregate_fn::fns::min_max::min_max;
23use crate::array::Array;
24use crate::array::ArrayParts;
25use crate::array::TypedArrayRef;
26use crate::array::child_to_validity;
27use crate::array::validity_to_child;
28use crate::array_slots;
29use crate::arrays::ConstantArray;
30use crate::arrays::List;
31use crate::arrays::ListArray;
32use crate::arrays::Primitive;
33use crate::builtins::ArrayBuiltins;
34use crate::dtype::DType;
35use crate::dtype::NativePType;
36use crate::match_each_integer_ptype;
37use crate::match_each_native_ptype;
38use crate::scalar_fn::fns::operators::Operator;
39use crate::validity::Validity;
40
41#[array_slots(List)]
42pub struct ListSlots {
43 #[slot(0)]
45 pub elements: ArrayRef,
46 #[slot(1)]
48 pub offsets: ArrayRef,
49 #[slot(2)]
51 pub validity: Option<ArrayRef>,
52}
53
54#[derive(Clone, Debug, Default)]
111pub struct ListData;
112
113impl Display for ListData {
114 fn fmt(&self, _f: &mut Formatter<'_>) -> std::fmt::Result {
115 Ok(())
116 }
117}
118
119pub struct ListDataParts {
120 pub elements: ArrayRef,
121 pub offsets: ArrayRef,
122 pub validity: Validity,
123 pub dtype: DType,
124}
125
126impl ListData {
127 pub(crate) fn make_slots(
128 elements: &ArrayRef,
129 offsets: &ArrayRef,
130 validity: &Validity,
131 len: usize,
132 ) -> ArraySlots {
133 ListSlots {
134 elements: elements.clone(),
135 offsets: offsets.clone(),
136 validity: validity_to_child(validity, len),
137 }
138 .into_slots()
139 }
140
141 pub fn build(
148 elements: ArrayRef,
149 offsets: ArrayRef,
150 validity: Validity,
151 ctx: &mut ExecutionCtx,
152 ) -> Self {
153 Self::try_build(elements, offsets, validity, ctx).vortex_expect("ListArray new")
154 }
155
156 pub(crate) fn try_build(
165 elements: ArrayRef,
166 offsets: ArrayRef,
167 validity: Validity,
168 ctx: &mut ExecutionCtx,
169 ) -> VortexResult<Self> {
170 Self::validate(&elements, &offsets, &validity, ctx)?;
171
172 Ok(unsafe { Self::new_unchecked() })
174 }
175
176 pub unsafe fn new_unchecked() -> Self {
193 Self
194 }
195
196 pub fn validate(
200 elements: &ArrayRef,
201 offsets: &ArrayRef,
202 validity: &Validity,
203 ctx: &mut ExecutionCtx,
204 ) -> VortexResult<()> {
205 vortex_ensure!(
207 !offsets.is_empty(),
208 "Offsets must have at least one element, [0] for an empty list"
209 );
210
211 vortex_ensure!(
213 offsets.dtype().is_int() && !offsets.dtype().is_nullable(),
214 "offsets have invalid type {}",
215 offsets.dtype()
216 );
217
218 let offsets_ptype = offsets.dtype().as_ptype();
220
221 if let Some(is_sorted) = offsets.statistics().compute_is_sorted(ctx) {
223 vortex_ensure!(is_sorted, "offsets must be sorted");
224 } else {
225 vortex_bail!("offsets must report is_sorted statistic");
226 }
227
228 if let Some(min_max) = min_max(offsets, ctx, NumericalAggregateOpts::default())? {
231 match_each_integer_ptype!(offsets_ptype, |P| {
232 #[allow(clippy::absurd_extreme_comparisons, unused_comparisons)]
233 {
234 let max = min_max
235 .max
236 .as_primitive()
237 .as_::<P>()
238 .vortex_expect("offsets type must fit offsets values");
239 let min = min_max
240 .min
241 .as_primitive()
242 .as_::<P>()
243 .vortex_expect("offsets type must fit offsets values");
244
245 vortex_ensure!(
246 min >= 0,
247 "offsets minimum {min} outside valid range [0, {max}]"
248 );
249
250 vortex_ensure!(
251 max <= P::try_from(elements.len()).unwrap_or_else(|_| vortex_panic!(
252 "Offsets type {} must be able to fit elements length {}",
253 <P as NativePType>::PTYPE,
254 elements.len()
255 )),
256 "Max offset {max} is beyond the length of the elements array {}",
257 elements.len()
258 );
259 }
260 })
261 } else {
262 vortex_bail!(
264 "offsets array with encoding {} must support min_max compute function",
265 offsets.encoding_id()
266 );
267 };
268
269 if let Some(validity_len) = validity.maybe_len() {
271 vortex_ensure_eq!(
272 validity_len,
273 offsets.len() - 1,
274 "validity length does not match array size",
275 );
276 }
277
278 Ok(())
279 }
280 }
285
286pub trait ListArrayExt: ListArraySlotsExt {
287 fn nullability(&self) -> crate::dtype::Nullability {
288 match self.dtype() {
289 DType::List(_, nullability) => *nullability,
290 _ => unreachable!("ListArrayExt requires a list dtype"),
291 }
292 }
293
294 fn list_validity(&self) -> Validity {
295 child_to_validity(
296 self.slots()[ListSlots::VALIDITY].as_ref(),
297 self.nullability(),
298 )
299 }
300
301 fn offset_at(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
302 vortex_ensure!(
303 index <= self.len(),
304 "Index {index} out of bounds 0..={}",
305 self.len()
306 );
307
308 if let Some(p) = self.offsets().as_opt::<Primitive>() {
309 Ok(match_each_native_ptype!(p.ptype(), |P| {
310 p.as_slice::<P>()[index].as_()
311 }))
312 } else {
313 self.offsets()
314 .execute_scalar(index, ctx)?
315 .as_primitive()
316 .as_::<usize>()
317 .ok_or_else(|| vortex_error::vortex_err!("offset value does not fit in usize"))
318 }
319 }
320
321 fn list_elements_at(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
322 let start = self.offset_at(index, ctx)?;
323 let end = self.offset_at(index + 1, ctx)?;
324 self.elements().slice(start..end)
325 }
326
327 fn sliced_elements(&self, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
328 let start = self.offset_at(0, ctx)?;
329 let end = self.offset_at(self.len(), ctx)?;
330 self.elements().slice(start..end)
331 }
332
333 fn element_dtype(&self) -> &DType {
334 self.elements().dtype()
335 }
336
337 fn reset_offsets(&self, recurse: bool, ctx: &mut ExecutionCtx) -> VortexResult<Array<List>> {
338 let mut elements = self.sliced_elements(ctx)?;
339 if recurse && elements.is_canonical() {
340 let compacted = elements
341 .execute::<Canonical>(ctx)?
342 .compact(ctx)?
343 .into_array();
344 elements = compacted;
345 } else if recurse && let Some(child_list_array) = elements.as_opt::<List>() {
346 elements = child_list_array
347 .into_owned()
348 .reset_offsets(recurse, ctx)?
349 .into_array();
350 }
351
352 let offsets = self.offsets();
353 let first_offset = offsets.execute_scalar(0, ctx)?;
354 let adjusted_offsets = if first_offset.is_zero() == Some(true) {
355 offsets.clone()
356 } else {
357 offsets.clone().binary(
358 ConstantArray::new(first_offset, offsets.len()).into_array(),
359 Operator::Sub,
360 )?
361 };
362
363 Ok(unsafe { ListArray::new_unchecked(elements, adjusted_offsets, self.list_validity()) })
365 }
366}
367impl<T: TypedArrayRef<List>> ListArrayExt for T {}
368
369impl Array<List> {
370 pub fn new(
372 elements: ArrayRef,
373 offsets: ArrayRef,
374 validity: Validity,
375 ctx: &mut ExecutionCtx,
376 ) -> Self {
377 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
378 let len = offsets.len().saturating_sub(1);
379 let slots = ListData::make_slots(&elements, &offsets, &validity, len);
380 let data = ListData::build(elements, offsets, validity, ctx);
381 unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) }
382 }
383
384 pub fn try_new(
386 elements: ArrayRef,
387 offsets: ArrayRef,
388 validity: Validity,
389 ctx: &mut ExecutionCtx,
390 ) -> VortexResult<Self> {
391 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
392 let len = offsets.len().saturating_sub(1);
393 let slots = ListData::make_slots(&elements, &offsets, &validity, len);
394 let data = ListData::try_build(elements, offsets, validity, ctx)?;
395 Ok(unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) })
396 }
397
398 pub unsafe fn new_unchecked(elements: ArrayRef, offsets: ArrayRef, validity: Validity) -> Self {
404 let dtype = DType::List(Arc::new(elements.dtype().clone()), validity.nullability());
405 let len = offsets.len().saturating_sub(1);
406 let slots = ListData::make_slots(&elements, &offsets, &validity, len);
407 let data = unsafe { ListData::new_unchecked() };
408 unsafe { Array::from_parts_unchecked(ArrayParts::new(List, dtype, len, data, slots)) }
409 }
410
411 pub fn into_data_parts(self) -> ListDataParts {
412 let dtype = self.dtype().clone();
413 let elements = self.slots()[ListSlots::ELEMENTS]
414 .clone()
415 .vortex_expect("ListArray elements slot");
416 let offsets = self.slots()[ListSlots::OFFSETS]
417 .clone()
418 .vortex_expect("ListArray offsets slot");
419 let validity = self.list_validity();
420 ListDataParts {
421 elements,
422 offsets,
423 validity,
424 dtype,
425 }
426 }
427}