vortex_zigzag/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Display;
5use std::fmt::Formatter;
6use std::hash::Hasher;
7
8use vortex_array::Array;
9use vortex_array::ArrayEq;
10use vortex_array::ArrayHash;
11use vortex_array::ArrayId;
12use vortex_array::ArrayParts;
13use vortex_array::ArrayRef;
14use vortex_array::ArrayView;
15use vortex_array::ExecutionCtx;
16use vortex_array::ExecutionResult;
17use vortex_array::IntoArray;
18use vortex_array::Precision;
19use vortex_array::TypedArrayRef;
20use vortex_array::buffer::BufferHandle;
21use vortex_array::dtype::DType;
22use vortex_array::dtype::PType;
23use vortex_array::match_each_unsigned_integer_ptype;
24use vortex_array::scalar::Scalar;
25use vortex_array::serde::ArrayChildren;
26use vortex_array::vtable::OperationsVTable;
27use vortex_array::vtable::VTable;
28use vortex_array::vtable::ValidityChild;
29use vortex_array::vtable::ValidityVTableFromChild;
30use vortex_error::VortexExpect;
31use vortex_error::VortexResult;
32use vortex_error::vortex_bail;
33use vortex_error::vortex_ensure;
34use vortex_error::vortex_panic;
35use vortex_session::VortexSession;
36use vortex_session::registry::CachedId;
37use zigzag::ZigZag as ExternalZigZag;
38
39use crate::compute::ZigZagEncoded;
40use crate::kernel::PARENT_KERNELS;
41use crate::rules::RULES;
42use crate::zigzag_decode;
43
44/// A [`ZigZag`]-encoded Vortex array.
45pub type ZigZagArray = Array<ZigZag>;
46
47impl VTable for ZigZag {
48    type ArrayData = ZigZagData;
49
50    type OperationsVTable = Self;
51    type ValidityVTable = ValidityVTableFromChild;
52
53    fn id(&self) -> ArrayId {
54        static ID: CachedId = CachedId::new("vortex.zigzag");
55        *ID
56    }
57
58    fn validate(
59        &self,
60        _data: &Self::ArrayData,
61        dtype: &DType,
62        len: usize,
63        slots: &[Option<ArrayRef>],
64    ) -> VortexResult<()> {
65        let encoded = slots[ENCODED_SLOT]
66            .as_ref()
67            .vortex_expect("ZigZagArray encoded slot");
68        let expected_dtype = ZigZagData::dtype_from_encoded_dtype(encoded.dtype())?;
69        vortex_ensure!(
70            dtype == &expected_dtype,
71            "expected dtype {expected_dtype}, got {dtype}"
72        );
73        vortex_ensure!(
74            encoded.len() == len,
75            "expected len {len}, got {}",
76            encoded.len()
77        );
78        Ok(())
79    }
80
81    fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
82        0
83    }
84
85    fn buffer(_array: ArrayView<'_, Self>, idx: usize) -> BufferHandle {
86        vortex_panic!("ZigZagArray buffer index {idx} out of bounds")
87    }
88
89    fn buffer_name(_array: ArrayView<'_, Self>, idx: usize) -> Option<String> {
90        vortex_panic!("ZigZagArray buffer_name index {idx} out of bounds")
91    }
92
93    fn serialize(
94        _array: ArrayView<'_, Self>,
95        _session: &VortexSession,
96    ) -> VortexResult<Option<Vec<u8>>> {
97        Ok(Some(vec![]))
98    }
99
100    fn deserialize(
101        &self,
102        dtype: &DType,
103        len: usize,
104        metadata: &[u8],
105        _buffers: &[BufferHandle],
106        children: &dyn ArrayChildren,
107        _session: &VortexSession,
108    ) -> VortexResult<ArrayParts<Self>> {
109        if !metadata.is_empty() {
110            vortex_bail!(
111                "ZigZagArray expects empty metadata, got {} bytes",
112                metadata.len()
113            );
114        }
115        if children.len() != 1 {
116            vortex_bail!("Expected 1 child, got {}", children.len());
117        }
118
119        let ptype = PType::try_from(dtype)?;
120        let encoded_type = DType::Primitive(ptype.to_unsigned(), dtype.nullability());
121
122        let encoded = children.get(0, &encoded_type, len)?;
123        let slots = vec![Some(encoded.clone())];
124        let data = ZigZagData::try_new(encoded.dtype())?;
125        Ok(ArrayParts::new(self.clone(), dtype.clone(), len, data).with_slots(slots))
126    }
127
128    fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
129        SLOT_NAMES[idx].to_string()
130    }
131
132    fn execute(array: Array<Self>, ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
133        Ok(ExecutionResult::done(
134            zigzag_decode(array.encoded().clone().execute(ctx)?).into_array(),
135        ))
136    }
137
138    fn reduce_parent(
139        array: ArrayView<'_, Self>,
140        parent: &ArrayRef,
141        child_idx: usize,
142    ) -> VortexResult<Option<ArrayRef>> {
143        RULES.evaluate(array, parent, child_idx)
144    }
145
146    fn execute_parent(
147        array: ArrayView<'_, Self>,
148        parent: &ArrayRef,
149        child_idx: usize,
150        ctx: &mut ExecutionCtx,
151    ) -> VortexResult<Option<ArrayRef>> {
152        PARENT_KERNELS.execute(array, parent, child_idx, ctx)
153    }
154}
155
156impl ArrayHash for ZigZagData {
157    fn array_hash<H: Hasher>(&self, _state: &mut H, _precision: Precision) {}
158}
159
160impl ArrayEq for ZigZagData {
161    fn array_eq(&self, _other: &Self, _precision: Precision) -> bool {
162        true
163    }
164}
165
166/// The zigzag-encoded values (signed integers mapped to unsigned).
167pub(super) const ENCODED_SLOT: usize = 0;
168pub(super) const NUM_SLOTS: usize = 1;
169pub(super) const SLOT_NAMES: [&str; NUM_SLOTS] = ["encoded"];
170
171#[derive(Clone, Debug)]
172pub struct ZigZagData {}
173
174impl Display for ZigZagData {
175    fn fmt(&self, _f: &mut Formatter<'_>) -> std::fmt::Result {
176        Ok(())
177    }
178}
179
180pub trait ZigZagArrayExt: TypedArrayRef<ZigZag> {
181    fn encoded(&self) -> &ArrayRef {
182        self.as_ref().slots()[ENCODED_SLOT]
183            .as_ref()
184            .vortex_expect("ZigZagArray encoded slot")
185    }
186
187    fn ptype(&self) -> PType {
188        PType::try_from(self.encoded().dtype())
189            .vortex_expect("ZigZagArray encoded dtype")
190            .to_signed()
191    }
192}
193
194impl<T: TypedArrayRef<ZigZag>> ZigZagArrayExt for T {}
195
196#[derive(Clone, Debug)]
197pub struct ZigZag;
198
199impl ZigZag {
200    /// Construct a new [`ZigZagArray`] from an encoded unsigned integer array.
201    pub fn try_new(encoded: ArrayRef) -> VortexResult<ZigZagArray> {
202        let dtype = ZigZagData::dtype_from_encoded_dtype(encoded.dtype())?;
203        let len = encoded.len();
204        let slots = vec![Some(encoded.clone())];
205        let data = ZigZagData::try_new(encoded.dtype())?;
206        Ok(unsafe {
207            Array::from_parts_unchecked(ArrayParts::new(ZigZag, dtype, len, data).with_slots(slots))
208        })
209    }
210}
211
212impl ZigZagData {
213    fn dtype_from_encoded_dtype(encoded_dtype: &DType) -> VortexResult<DType> {
214        Ok(DType::from(PType::try_from(encoded_dtype)?.to_signed())
215            .with_nullability(encoded_dtype.nullability()))
216    }
217
218    pub fn new() -> Self {
219        Self {}
220    }
221
222    pub fn try_new(encoded_dtype: &DType) -> VortexResult<Self> {
223        if !encoded_dtype.is_unsigned_int() {
224            vortex_bail!(MismatchedTypes: "unsigned int", encoded_dtype);
225        }
226
227        Self::dtype_from_encoded_dtype(encoded_dtype)?;
228
229        Ok(Self {})
230    }
231}
232
233impl Default for ZigZagData {
234    fn default() -> Self {
235        Self::new()
236    }
237}
238
239impl OperationsVTable<ZigZag> for ZigZag {
240    fn scalar_at(
241        array: ArrayView<'_, ZigZag>,
242        index: usize,
243        ctx: &mut ExecutionCtx,
244    ) -> VortexResult<Scalar> {
245        let scalar = array.encoded().execute_scalar(index, ctx)?;
246        if scalar.is_null() {
247            return scalar.primitive_reinterpret_cast(ZigZagArrayExt::ptype(&array));
248        }
249
250        let pscalar = scalar.as_primitive();
251        Ok(match_each_unsigned_integer_ptype!(pscalar.ptype(), |P| {
252            Scalar::primitive(
253                <<P as ZigZagEncoded>::Int>::decode(
254                    pscalar
255                        .typed_value::<P>()
256                        .vortex_expect("zigzag corruption"),
257                ),
258                array.dtype().nullability(),
259            )
260        }))
261    }
262}
263
264impl ValidityChild<ZigZag> for ZigZag {
265    fn validity_child(array: ArrayView<'_, ZigZag>) -> ArrayRef {
266        array.encoded().clone()
267    }
268}
269
270#[cfg(test)]
271mod test {
272    use vortex_array::IntoArray;
273    use vortex_array::LEGACY_SESSION;
274    use vortex_array::ToCanonical;
275    use vortex_array::VortexSessionExecute;
276    use vortex_array::scalar::Scalar;
277    use vortex_buffer::buffer;
278
279    use super::*;
280    use crate::zigzag_encode;
281
282    #[test]
283    fn test_compute_statistics() -> VortexResult<()> {
284        let array = buffer![1i32, -5i32, 2, 3, 4, 5, 6, 7, 8, 9, 10]
285            .into_array()
286            .to_primitive();
287        let zigzag = zigzag_encode(array.as_view())?;
288        let mut ctx = LEGACY_SESSION.create_execution_ctx();
289
290        assert_eq!(
291            zigzag.statistics().compute_max::<i32>(&mut ctx),
292            array.statistics().compute_max::<i32>(&mut ctx)
293        );
294        assert_eq!(
295            zigzag.statistics().compute_null_count(&mut ctx),
296            array.statistics().compute_null_count(&mut ctx)
297        );
298        assert_eq!(
299            zigzag.statistics().compute_is_constant(&mut ctx),
300            array.statistics().compute_is_constant(&mut ctx)
301        );
302
303        let sliced = zigzag.slice(0..2).unwrap();
304        let sliced = sliced.as_::<ZigZag>();
305        assert_eq!(
306            sliced
307                .array()
308                .execute_scalar(sliced.len() - 1, &mut ctx,)
309                .unwrap(),
310            Scalar::from(-5i32)
311        );
312
313        assert_eq!(
314            sliced.statistics().compute_min::<i32>(&mut ctx),
315            array.statistics().compute_min::<i32>(&mut ctx)
316        );
317        assert_eq!(
318            sliced.statistics().compute_null_count(&mut ctx),
319            array.statistics().compute_null_count(&mut ctx)
320        );
321        assert_eq!(
322            sliced.statistics().compute_is_constant(&mut ctx),
323            array.statistics().compute_is_constant(&mut ctx)
324        );
325        Ok(())
326    }
327}
vortex_zigzag/array.rs

vortex_zigzag/
array.rs
