Skip to main content

vortex_array/scalar_fn/fns/
list_length.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use num_traits::AsPrimitive;
5use vortex_error::VortexResult;
6use vortex_error::vortex_bail;
7use vortex_session::VortexSession;
8use vortex_session::registry::CachedId;
9
10use crate::ArrayRef;
11use crate::ExecutionCtx;
12use crate::IntoArray;
13use crate::array::ArrayView;
14use crate::arrays::ConstantArray;
15use crate::arrays::FixedSizeList;
16use crate::arrays::List;
17use crate::arrays::ListView;
18use crate::arrays::fixed_size_list::FixedSizeListArrayExt;
19use crate::arrays::list::ListArrayExt;
20use crate::arrays::list::ListArraySlotsExt;
21use crate::arrays::listview::ListViewArrayExt;
22use crate::arrays::listview::ListViewArraySlotsExt;
23use crate::builtins::ArrayBuiltins;
24use crate::dtype::DType;
25use crate::dtype::Nullability;
26use crate::dtype::PType;
27use crate::matcher::Matcher;
28use crate::scalar::Scalar;
29use crate::scalar_fn::Arity;
30use crate::scalar_fn::ChildName;
31use crate::scalar_fn::EmptyOptions;
32use crate::scalar_fn::ExecutionArgs;
33use crate::scalar_fn::ScalarFnId;
34use crate::scalar_fn::ScalarFnVTable;
35use crate::scalar_fn::fns::operators::Operator;
36
37/// Number of elements in each list of a `List` or `FixedSizeList` typed array.
38///
39/// This is computed purely from the list's offsets (`ListArray`), sizes (`ListViewArray`), or
40/// dtype (`FixedSizeListArray`) without reading the element *values*. Validity is carried over
41/// from the original array.
42#[derive(Clone)]
43pub struct ListLength;
44
45impl ScalarFnVTable for ListLength {
46    type Options = EmptyOptions;
47
48    fn id(&self) -> ScalarFnId {
49        static ID: CachedId = CachedId::new("vortex.list.length");
50        *ID
51    }
52
53    fn serialize(&self, _instance: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
54        Ok(Some(vec![]))
55    }
56
57    fn deserialize(
58        &self,
59        _metadata: &[u8],
60        _session: &VortexSession,
61    ) -> VortexResult<Self::Options> {
62        Ok(EmptyOptions)
63    }
64
65    fn arity(&self, _options: &Self::Options) -> Arity {
66        Arity::Exact(1)
67    }
68
69    fn child_name(&self, _instance: &Self::Options, child_idx: usize) -> ChildName {
70        match child_idx {
71            0 => ChildName::from("input"),
72            _ => unreachable!("Invalid child index {child_idx} for list_length()"),
73        }
74    }
75
76    fn return_dtype(&self, _options: &Self::Options, arg_dtypes: &[DType]) -> VortexResult<DType> {
77        match &arg_dtypes[0] {
78            DType::List(_, nullable) | DType::FixedSizeList(_, _, nullable) => {
79                Ok(DType::Primitive(PType::U64, *nullable))
80            }
81            other => {
82                vortex_bail!("list_length() requires List or FixedSizeList, got {other}")
83            }
84        }
85    }
86
87    fn execute(
88        &self,
89        _options: &Self::Options,
90        args: &dyn ExecutionArgs,
91        ctx: &mut ExecutionCtx,
92    ) -> VortexResult<ArrayRef> {
93        let input = args.get(0)?;
94        let nullability = input.dtype().nullability();
95
96        if let Some(scalar) = input.as_constant() {
97            let len_scalar = scalar_list_length(scalar, nullability)?;
98            return Ok(ConstantArray::new(len_scalar, args.row_count()).into_array());
99        }
100
101        list_length(&input, nullability, ctx)
102    }
103
104    fn is_strict(&self, _options: &Self::Options) -> bool {
105        // A null list has a null length, and the length of a valid list is a non-null value
106        // determined by that list alone, with `return_dtype` carrying over the input nullability.
107        true
108    }
109
110    fn is_infallible(&self, _options: &Self::Options) -> bool {
111        true
112    }
113}
114
115fn scalar_list_length(scalar: &Scalar, nullability: Nullability) -> VortexResult<Scalar> {
116    if scalar.is_null() {
117        let dtype = DType::Primitive(PType::U64, Nullability::Nullable);
118        return Ok(Scalar::null(dtype));
119    }
120    let len: u64 = scalar.as_list().len().as_();
121    Ok(Scalar::primitive(len, nullability))
122}
123
124pub(crate) fn list_length(
125    array: &ArrayRef,
126    nullability: Nullability,
127    ctx: &mut ExecutionCtx,
128) -> VortexResult<ArrayRef> {
129    let any_list = array.clone().execute_until::<AnyList>(ctx)?;
130
131    let (lengths, validity) = if let Some(fsl) = any_list.as_opt::<FixedSizeList>() {
132        // The length of fixed-size list is constant, so just need to carry over validity
133        let size = fsl.list_size() as u64;
134        let lengths =
135            ConstantArray::new(Scalar::primitive(size, Nullability::NonNullable), fsl.len())
136                .into_array();
137        (lengths, fsl.validity()?)
138    } else if let Some(lv) = any_list.as_opt::<ListView>() {
139        // Length array is exactly the sizes child
140        (lv.sizes().clone(), lv.listview_validity())
141    } else if let Some(l) = any_list.as_opt::<List>() {
142        let lengths = list_length_from_offsets(l)?;
143        (lengths, l.list_validity())
144    } else {
145        let dtype = any_list.dtype();
146        vortex_bail!("list_length() requires List, ListView, or FixedSizeList but got {dtype}")
147    };
148
149    // Cast to `U64`
150    let len = lengths.len();
151    let lengths = lengths.cast(DType::Primitive(PType::U64, nullability))?;
152
153    // Carry over validity mask for nullable arrays
154    if matches!(nullability, Nullability::Nullable) {
155        lengths.mask(validity.to_array(len))
156    } else {
157        Ok(lengths)
158    }
159}
160
161/// Calculate the lengths of `ListArray` elements via the `offsets` child:
162/// `length[i] = offsets[i + 1] - offsets[i]`.
163fn list_length_from_offsets(list: ArrayView<'_, List>) -> VortexResult<ArrayRef> {
164    let offsets = list.offsets();
165    let n = offsets.len().saturating_sub(1);
166
167    offsets
168        .slice(1..offsets.len())?
169        .binary(offsets.slice(0..n)?, Operator::Sub)
170}
171
172/// Matches an `Array<List>`, `Array<ListView>`, or `Array<FixedSizeList>`
173struct AnyList;
174
175impl Matcher for AnyList {
176    type Match<'a> = ();
177
178    fn try_match(array: &ArrayRef) -> Option<Self::Match<'_>> {
179        (array.as_opt::<List>().is_some()
180            || array.as_opt::<ListView>().is_some()
181            || array.as_opt::<FixedSizeList>().is_some())
182        .then_some(())
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use std::sync::Arc;
189    use std::sync::LazyLock;
190
191    use rstest::rstest;
192    use vortex_buffer::buffer;
193    use vortex_error::VortexResult;
194    use vortex_session::VortexSession;
195
196    use crate::ArrayRef;
197    use crate::IntoArray;
198    use crate::VortexSessionExecute;
199    use crate::arrays::BoolArray;
200    use crate::arrays::ConstantArray;
201    use crate::arrays::FixedSizeListArray;
202    use crate::arrays::ListArray;
203    use crate::arrays::ListViewArray;
204    use crate::arrays::PrimitiveArray;
205    use crate::assert_arrays_eq;
206    use crate::dtype::DType;
207    use crate::dtype::Nullability;
208    use crate::dtype::PType;
209    use crate::expr::cast;
210    use crate::expr::list_length;
211    use crate::expr::root;
212    use crate::scalar::Scalar;
213    use crate::validity::Validity;
214
215    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
216
217    fn create_list_elements() -> ArrayRef {
218        PrimitiveArray::from_option_iter::<i32, _>([
219            Some(1),
220            Some(2),
221            Some(3),
222            Some(4),
223            Some(5),
224            Some(6),
225            None,
226        ])
227        .into_array()
228    }
229
230    #[rstest]
231    #[case(buffer![0u32, 2, 5, 5, 7].into_array())]
232    #[case(buffer![0u64, 2, 5, 5, 7].into_array())]
233    fn test_list_length(#[case] offsets: ArrayRef) -> VortexResult<()> {
234        let mut ctx = SESSION.create_execution_ctx();
235        let elements = create_list_elements();
236        let list =
237            ListArray::try_new(elements, offsets, Validity::NonNullable, &mut ctx)?.into_array();
238        let result = list.apply(&list_length(root()))?;
239        let mut ctx = SESSION.create_execution_ctx();
240        assert_arrays_eq!(result, PrimitiveArray::from_iter([2u64, 3, 0, 2]), &mut ctx);
241        Ok(())
242    }
243
244    #[rstest]
245    #[case(buffer![0u32, 2, 5, 5, 7].into_array())]
246    #[case(buffer![0u64, 2, 5, 5, 7].into_array())]
247    fn test_nullable_list_length(#[case] offsets: ArrayRef) -> VortexResult<()> {
248        let mut ctx = SESSION.create_execution_ctx();
249        let elements = create_list_elements();
250        let list = ListArray::try_new(
251            elements,
252            offsets,
253            Validity::Array(BoolArray::from_iter([true, false, true, false]).into_array()),
254            &mut ctx,
255        )?
256        .into_array();
257        let result = list.apply(&list_length(root()))?;
258
259        let mut ctx = SESSION.create_execution_ctx();
260
261        let expected = PrimitiveArray::from_option_iter::<u64, _>([Some(2), None, Some(0), None]);
262
263        assert_arrays_eq!(result, expected, &mut ctx);
264
265        Ok(())
266    }
267
268    #[test]
269    fn test_null_scalar_list_length() -> VortexResult<()> {
270        let null_scalar = Scalar::null(DType::List(
271            Arc::new(DType::Primitive(PType::I32, Nullability::NonNullable)),
272            Nullability::Nullable,
273        ));
274        let array = ConstantArray::new(null_scalar, 2).into_array();
275        let result = array.apply(&list_length(root()))?;
276
277        let mut ctx = SESSION.create_execution_ctx();
278        assert!(!result.is_valid(0, &mut ctx)?);
279        assert!(!result.is_valid(1, &mut ctx)?);
280        assert_arrays_eq!(
281            result,
282            PrimitiveArray::from_option_iter([None::<u64>, None]),
283            &mut ctx
284        );
285        Ok(())
286    }
287
288    #[test]
289    fn test_listview_length() -> VortexResult<()> {
290        let mut ctx = SESSION.create_execution_ctx();
291        let elements = create_list_elements();
292        let lv = ListViewArray::new(
293            elements,
294            buffer![5u32, 0, 4, 1].into_array(),
295            buffer![2u32, 3, 0, 2].into_array(),
296            Validity::NonNullable,
297            &mut ctx,
298        )
299        .into_array();
300        let result = lv.apply(&list_length(root()))?;
301        let mut ctx = SESSION.create_execution_ctx();
302        assert_arrays_eq!(result, PrimitiveArray::from_iter([2u64, 3, 0, 2]), &mut ctx);
303        Ok(())
304    }
305
306    #[test]
307    fn test_listview_length_nullable() -> VortexResult<()> {
308        let mut ctx = SESSION.create_execution_ctx();
309        let elements = create_list_elements();
310        let lv = ListViewArray::new(
311            elements,
312            buffer![5u32, 0, 4, 1].into_array(),
313            buffer![2u32, 3, 0, 2].into_array(),
314            Validity::Array(BoolArray::from_iter([true, false, true, false]).into_array()),
315            &mut ctx,
316        )
317        .into_array();
318        let result = lv.apply(&list_length(root()))?;
319
320        let mut ctx = SESSION.create_execution_ctx();
321
322        let expected = PrimitiveArray::from_option_iter::<u64, _>([Some(2), None, Some(0), None]);
323        assert_arrays_eq!(result, expected, &mut ctx);
324        Ok(())
325    }
326
327    #[test]
328    fn test_list_length_take() -> VortexResult<()> {
329        let mut ctx = SESSION.create_execution_ctx();
330        let elements = create_list_elements();
331        let list = ListArray::try_new(
332            elements,
333            buffer![0u32, 2, 5, 5, 7].into_array(),
334            Validity::NonNullable,
335            &mut ctx,
336        )?
337        .into_array();
338        let taken = list.take(buffer![3u64, 0, 2].into_array())?;
339
340        let result = taken.apply(&list_length(root()))?;
341        let mut ctx = SESSION.create_execution_ctx();
342        assert_arrays_eq!(result, PrimitiveArray::from_iter([2u64, 2, 0]), &mut ctx);
343        Ok(())
344    }
345
346    fn create_fixed_size_list(validity: Validity) -> ArrayRef {
347        // 4 lists of size 2 over 8 primitive elements.
348        let elements = PrimitiveArray::from_iter([1i32, 2, 3, 4, 5, 6, 7, 8]).into_array();
349        FixedSizeListArray::new(elements, 2, validity, 4).into_array()
350    }
351
352    #[test]
353    fn test_fixed_size_list_length() -> VortexResult<()> {
354        let fsl = create_fixed_size_list(Validity::NonNullable);
355        let result = fsl.apply(&list_length(root()))?;
356
357        let mut ctx = SESSION.create_execution_ctx();
358        assert_arrays_eq!(result, PrimitiveArray::from_iter([2u64, 2, 2, 2]), &mut ctx);
359        Ok(())
360    }
361
362    #[test]
363    fn test_fixed_size_list_length_nullable() -> VortexResult<()> {
364        let fsl = create_fixed_size_list(Validity::Array(
365            BoolArray::from_iter([true, false, true, false]).into_array(),
366        ));
367        let result = fsl.apply(&list_length(root()))?;
368
369        let mut ctx = SESSION.create_execution_ctx();
370
371        let expected = PrimitiveArray::from_option_iter::<u64, _>([Some(2), None, Some(2), None]);
372        assert_arrays_eq!(result, expected, &mut ctx);
373        Ok(())
374    }
375
376    #[test]
377    fn test_fallible_child_expression_fails() -> VortexResult<()> {
378        let fsl = create_fixed_size_list(Validity::Array(
379            BoolArray::from_iter([true, false, true, false]).into_array(),
380        ));
381        let failing_cast_dtype = DType::FixedSizeList(
382            Arc::new(DType::Primitive(PType::I32, Nullability::NonNullable)),
383            2,
384            Nullability::NonNullable,
385        );
386
387        let lengths = fsl.apply(&list_length(cast(root(), failing_cast_dtype)))?;
388
389        let mut ctx = SESSION.create_execution_ctx();
390        let result = lengths.execute::<ArrayRef>(&mut ctx);
391
392        assert!(result.is_err());
393
394        let err_message = result.unwrap_err().to_string();
395
396        assert!(
397            err_message.contains("Cannot cast array with invalid values to non-nullable type.")
398        );
399
400        Ok(())
401    }
402
403    #[test]
404    fn test_display() {
405        let expr = list_length(root());
406        assert_eq!(expr.to_string(), "vortex.list.length($)");
407    }
408}