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

vortex_zigzag/
array.rs
