Skip to main content

vortex_array/arrays/list/vtable/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::hash::Hasher;
5use std::sync::Arc;
6
7use prost::Message;
8use vortex_error::VortexExpect;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11use vortex_error::vortex_ensure_eq;
12use vortex_error::vortex_err;
13use vortex_error::vortex_panic;
14use vortex_session::VortexSession;
15use vortex_session::registry::CachedId;
16
17use crate::ArrayEq;
18use crate::ArrayHash;
19use crate::ArrayRef;
20use crate::EqMode;
21use crate::ExecutionCtx;
22use crate::ExecutionResult;
23use crate::IntoArray;
24use crate::VortexSessionExecute;
25use crate::array::Array;
26use crate::array::ArrayId;
27use crate::array::ArrayParts;
28use crate::array::ArrayView;
29use crate::array::VTable;
30use crate::array::with_empty_buffers;
31use crate::arrays::list::ListArraySlotsExt;
32use crate::arrays::list::ListData;
33use crate::arrays::list::ListSlots;
34use crate::arrays::list::compute::rules::PARENT_RULES;
35use crate::arrays::listview::list_view_from_list;
36use crate::buffer::BufferHandle;
37use crate::builders::ArrayBuilder;
38use crate::dtype::DType;
39use crate::dtype::Nullability;
40use crate::dtype::PType;
41use crate::match_each_list_builder;
42use crate::serde::ArrayChildren;
43use crate::validity::Validity;
44mod operations;
45mod validity;
46/// A [`List`]-encoded Vortex array.
47pub type ListArray = Array<List>;
48
49#[derive(Clone, prost::Message)]
50pub struct ListMetadata {
51    #[prost(uint64, tag = "1")]
52    elements_len: u64,
53    #[prost(int32, tag = "2")]
54    offset_ptype: i32,
55}
56
57impl ListMetadata {
58    fn get_offset_ptype(&self) -> VortexResult<PType> {
59        PType::try_from(self.offset_ptype).map_err(|_| {
60            vortex_err!(
61                "ListMetadata offset_ptype must be a known PType, got {}",
62                self.offset_ptype
63            )
64        })
65    }
66}
67
68impl ArrayHash for ListData {
69    fn array_hash<H: Hasher>(&self, _state: &mut H, _accuracy: EqMode) {}
70}
71
72impl ArrayEq for ListData {
73    fn array_eq(&self, _other: &Self, _accuracy: EqMode) -> bool {
74        true
75    }
76}
77
78impl VTable for List {
79    type TypedArrayData = ListData;
80
81    type OperationsVTable = Self;
82    type ValidityVTable = Self;
83    fn id(&self) -> ArrayId {
84        static ID: CachedId = CachedId::new("vortex.list");
85        *ID
86    }
87
88    fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
89        0
90    }
91
92    fn buffer(_array: ArrayView<'_, Self>, idx: usize) -> BufferHandle {
93        vortex_panic!("ListArray buffer index {idx} out of bounds")
94    }
95
96    fn buffer_name(_array: ArrayView<'_, Self>, idx: usize) -> Option<String> {
97        vortex_panic!("ListArray buffer_name index {idx} out of bounds")
98    }
99
100    fn with_buffers(
101        &self,
102        array: ArrayView<'_, Self>,
103        buffers: &[BufferHandle],
104    ) -> VortexResult<ArrayParts<Self>> {
105        with_empty_buffers(self, array, buffers)
106    }
107
108    fn reduce_parent(
109        array: ArrayView<'_, Self>,
110        parent: &ArrayRef,
111        child_idx: usize,
112    ) -> VortexResult<Option<ArrayRef>> {
113        PARENT_RULES.evaluate(array, parent, child_idx)
114    }
115
116    fn serialize(
117        array: ArrayView<'_, Self>,
118        _session: &VortexSession,
119    ) -> VortexResult<Option<Vec<u8>>> {
120        Ok(Some(
121            ListMetadata {
122                elements_len: array.elements().len() as u64,
123                offset_ptype: PType::try_from(array.offsets().dtype())? as i32,
124            }
125            .encode_to_vec(),
126        ))
127    }
128
129    fn validate(
130        &self,
131        _data: &ListData,
132        dtype: &DType,
133        len: usize,
134        slots: &[Option<ArrayRef>],
135    ) -> VortexResult<()> {
136        vortex_ensure_eq!(slots.len(), ListSlots::COUNT);
137        let elements = slots[ListSlots::ELEMENTS]
138            .as_ref()
139            .vortex_expect("ListArray elements slot");
140        let offsets = slots[ListSlots::OFFSETS]
141            .as_ref()
142            .vortex_expect("ListArray offsets slot");
143        vortex_ensure_eq!(
144            offsets.len().saturating_sub(1),
145            len,
146            "ListArray length does not match outer length",
147        );
148
149        let actual_dtype = DType::List(Arc::new(elements.dtype().clone()), dtype.nullability());
150        vortex_ensure_eq!(
151            &actual_dtype,
152            dtype,
153            "ListArray dtype does not match outer dtype",
154        );
155
156        Ok(())
157    }
158
159    fn deserialize(
160        &self,
161        dtype: &DType,
162        len: usize,
163        metadata: &[u8],
164
165        _buffers: &[BufferHandle],
166        children: &dyn ArrayChildren,
167        session: &VortexSession,
168    ) -> VortexResult<ArrayParts<Self>> {
169        let metadata = ListMetadata::decode(metadata)?;
170        let offset_ptype = metadata.get_offset_ptype()?;
171        let validity = if children.len() == 2 {
172            Validity::from(dtype.nullability())
173        } else if children.len() == 3 {
174            let validity = children.get(2, &Validity::DTYPE, len)?;
175            Validity::Array(validity)
176        } else {
177            vortex_bail!("Expected 2 or 3 children, got {}", children.len());
178        };
179
180        let DType::List(element_dtype, _) = &dtype else {
181            vortex_bail!("Expected List dtype, got {:?}", dtype);
182        };
183        let elements = children.get(
184            0,
185            element_dtype.as_ref(),
186            usize::try_from(metadata.elements_len)?,
187        )?;
188
189        let offsets = children.get(
190            1,
191            &DType::Primitive(offset_ptype, Nullability::NonNullable),
192            len + 1,
193        )?;
194
195        let data = ListData::try_build(
196            elements.clone(),
197            offsets.clone(),
198            validity.clone(),
199            &mut session.create_execution_ctx(),
200        )?;
201        let slots = ListData::make_slots(&elements, &offsets, &validity, len);
202        Ok(ArrayParts::new(
203            self.clone(),
204            dtype.clone(),
205            len,
206            data,
207            slots,
208        ))
209    }
210
211    fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
212        ListSlots::NAMES[idx].to_string()
213    }
214
215    fn execute(array: Array<Self>, ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
216        Ok(ExecutionResult::done(
217            list_view_from_list(array, ctx)?.into_array(),
218        ))
219    }
220
221    // The complexity comes from the expansion of `match_each_list_builder!`.
222    #[expect(clippy::cognitive_complexity)]
223    fn append_to_builder(
224        array: ArrayView<'_, Self>,
225        builder: &mut dyn ArrayBuilder,
226        ctx: &mut ExecutionCtx,
227    ) -> VortexResult<()> {
228        match match_each_list_builder!(&mut *builder, |b| b.append_list_array(array, ctx)) {
229            Some(result) => result,
230            None => vortex_bail!(
231                "cannot append a List array of dtype {} to a {} builder",
232                array.dtype(),
233                builder.dtype()
234            ),
235        }
236    }
237}
238
239#[derive(Clone, Debug)]
240pub struct List;
241
242#[cfg(test)]
243mod tests {
244    use std::sync::Arc;
245    use std::sync::LazyLock;
246
247    use prost::Message;
248    use vortex_error::VortexResult;
249    use vortex_session::VortexSession;
250
251    use super::List;
252    use super::ListMetadata;
253    use crate::ArrayRef;
254    use crate::array::VTable;
255    use crate::dtype::DType;
256    use crate::dtype::Nullability;
257    use crate::dtype::PType;
258
259    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
260
261    #[test]
262    fn test_deserialize_rejects_unknown_offset_ptype() -> VortexResult<()> {
263        let dtype = DType::List(
264            Arc::new(DType::Primitive(PType::I32, Nullability::NonNullable)),
265            Nullability::NonNullable,
266        );
267        let metadata = ListMetadata {
268            offset_ptype: 11,
269            ..Default::default()
270        }
271        .encode_to_vec();
272        let children: Vec<ArrayRef> = Vec::new();
273        let result = List.deserialize(&dtype, 0, &metadata, &[], &children, &SESSION);
274        assert!(result.is_err_and(|err| {
275            err.to_string()
276                .contains("ListMetadata offset_ptype must be a known PType, got 11")
277        }));
278
279        let known = ListMetadata {
280            offset_ptype: PType::U32 as i32,
281            ..Default::default()
282        };
283        assert_eq!(known.get_offset_ptype()?, PType::U32);
284
285        Ok(())
286    }
287}