Skip to main content

vortex_array/arrays/patched/vtable/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use prost::Message;
5
6use crate::ArrayEq;
7use crate::ArrayHash;
8mod kernels;
9mod operations;
10mod slice;
11
12use std::hash::Hash;
13use std::hash::Hasher;
14
15use vortex_buffer::Buffer;
16use vortex_error::VortexExpect;
17use vortex_error::VortexResult;
18use vortex_error::vortex_panic;
19use vortex_session::VortexSession;
20use vortex_session::registry::CachedId;
21
22use crate::ArrayRef;
23use crate::Canonical;
24use crate::EqMode;
25use crate::ExecutionCtx;
26use crate::ExecutionResult;
27use crate::IntoArray;
28use crate::array::Array;
29use crate::array::ArrayId;
30use crate::array::ArrayParts;
31use crate::array::ArrayView;
32use crate::array::VTable;
33use crate::array::ValidityChild;
34use crate::array::ValidityVTableFromChild;
35use crate::array::with_empty_buffers;
36use crate::arrays::Primitive;
37use crate::arrays::PrimitiveArray;
38use crate::arrays::patched::PatchedArrayExt;
39use crate::arrays::patched::PatchedArraySlotsExt;
40use crate::arrays::patched::PatchedData;
41use crate::arrays::patched::PatchedSlots;
42use crate::arrays::patched::PatchedSlotsView;
43use crate::arrays::patched::compute::rules::PARENT_RULES;
44use crate::arrays::primitive::PrimitiveDataParts;
45use crate::buffer::BufferHandle;
46use crate::builders::ArrayBuilder;
47use crate::builders::PrimitiveBuilder;
48use crate::dtype::DType;
49use crate::dtype::NativePType;
50use crate::dtype::PType;
51use crate::match_each_native_ptype;
52use crate::require_child;
53use crate::serde::ArrayChildren;
54
55/// A [`Patched`]-encoded Vortex array.
56pub type PatchedArray = Array<Patched>;
57
58pub(crate) fn initialize(session: &VortexSession) {
59    kernels::initialize(session);
60}
61
62#[derive(Clone, Debug)]
63pub struct Patched;
64
65impl ValidityChild<Patched> for Patched {
66    fn validity_child(array: ArrayView<'_, Patched>) -> ArrayRef {
67        array.inner().clone()
68    }
69}
70
71#[derive(Clone, prost::Message)]
72pub struct PatchedMetadata {
73    /// The total number of patches, and the length of the indices and values child arrays.
74    #[prost(uint32, tag = "1")]
75    pub(crate) n_patches: u32,
76
77    /// The number of lanes used for patch indexing. Must be a power of two between 1 and 128.
78    #[prost(uint32, tag = "2")]
79    pub(crate) n_lanes: u32,
80
81    /// An offset into the first chunk's patches that should be considered in-view.
82    ///
83    /// Always between 0 and 1023.
84    #[prost(uint32, tag = "3")]
85    pub(crate) offset: u32,
86}
87
88impl ArrayHash for PatchedData {
89    fn array_hash<H: Hasher>(&self, state: &mut H, _accuracy: EqMode) {
90        self.offset.hash(state);
91        self.n_lanes.hash(state);
92    }
93}
94
95impl ArrayEq for PatchedData {
96    fn array_eq(&self, other: &Self, _accuracy: EqMode) -> bool {
97        self.offset == other.offset && self.n_lanes == other.n_lanes
98    }
99}
100
101impl VTable for Patched {
102    type TypedArrayData = PatchedData;
103    type OperationsVTable = Self;
104    type ValidityVTable = ValidityVTableFromChild;
105
106    fn id(&self) -> ArrayId {
107        static ID: CachedId = CachedId::new("vortex.patched");
108        *ID
109    }
110
111    fn validate(
112        &self,
113        data: &PatchedData,
114        dtype: &DType,
115        len: usize,
116        slots: &[Option<ArrayRef>],
117    ) -> VortexResult<()> {
118        data.validate(dtype, len, &PatchedSlotsView::from_slots(slots))
119    }
120
121    fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
122        0
123    }
124
125    fn buffer(_array: ArrayView<'_, Self>, idx: usize) -> BufferHandle {
126        vortex_panic!("invalid buffer index for PatchedArray: {idx}");
127    }
128
129    fn buffer_name(_array: ArrayView<'_, Self>, idx: usize) -> Option<String> {
130        vortex_panic!("invalid buffer index for PatchedArray: {idx}");
131    }
132
133    fn with_buffers(
134        &self,
135        array: ArrayView<'_, Self>,
136        buffers: &[BufferHandle],
137    ) -> VortexResult<ArrayParts<Self>> {
138        with_empty_buffers(self, array, buffers)
139    }
140
141    fn serialize(
142        array: ArrayView<'_, Self>,
143        _session: &VortexSession,
144    ) -> VortexResult<Option<Vec<u8>>> {
145        Ok(Some(
146            PatchedMetadata {
147                n_patches: u32::try_from(array.patch_indices().len())?,
148                n_lanes: u32::try_from(array.n_lanes())?,
149                offset: u32::try_from(array.offset())?,
150            }
151            .encode_to_vec(),
152        ))
153    }
154
155    fn deserialize(
156        &self,
157        dtype: &DType,
158        len: usize,
159        metadata: &[u8],
160        _buffers: &[BufferHandle],
161        children: &dyn ArrayChildren,
162        _session: &VortexSession,
163    ) -> VortexResult<ArrayParts<Self>> {
164        let metadata = PatchedMetadata::decode(metadata)?;
165        let n_patches = metadata.n_patches as usize;
166        let n_lanes = metadata.n_lanes as usize;
167        let offset = metadata.offset as usize;
168
169        // n_chunks should correspond to the chunk in the `inner`.
170        // After slicing when offset > 0, there may be additional chunks.
171        let n_chunks = (len + offset).div_ceil(1024);
172
173        let inner = children.get(0, dtype, len)?;
174        let lane_offsets = children.get(1, PType::U32.into(), n_chunks * n_lanes + 1)?;
175        let indices = children.get(2, PType::U16.into(), n_patches)?;
176        let values = children.get(3, dtype, n_patches)?;
177
178        let data = PatchedData { n_lanes, offset };
179        let slots = PatchedSlots {
180            inner,
181            lane_offsets,
182            patch_indices: indices,
183            patch_values: values,
184        }
185        .into_slots();
186        Ok(ArrayParts::new(
187            self.clone(),
188            dtype.clone(),
189            len,
190            data,
191            slots,
192        ))
193    }
194
195    fn append_to_builder(
196        array: ArrayView<'_, Self>,
197        builder: &mut dyn ArrayBuilder,
198        ctx: &mut ExecutionCtx,
199    ) -> VortexResult<()> {
200        let dtype = array.array().dtype();
201
202        if !dtype.is_primitive() {
203            // Default pathway: canonicalize and propagate.
204            let canonical = array
205                .array()
206                .clone()
207                .execute::<Canonical>(ctx)?
208                .into_array();
209            return canonical.append_to_builder(builder, ctx);
210        }
211
212        let ptype = dtype.as_ptype();
213
214        let len = array.len();
215
216        array.inner().append_to_builder(builder, ctx)?;
217
218        let offset = array.offset();
219        let lane_offsets = array
220            .lane_offsets()
221            .clone()
222            .execute::<PrimitiveArray>(ctx)?;
223        let indices = array
224            .patch_indices()
225            .clone()
226            .execute::<PrimitiveArray>(ctx)?;
227        let values = array
228            .patch_values()
229            .clone()
230            .execute::<PrimitiveArray>(ctx)?;
231
232        match_each_native_ptype!(ptype, |V| {
233            let typed_builder = builder
234                .as_any_mut()
235                .downcast_mut::<PrimitiveBuilder<V>>()
236                .vortex_expect("correctly typed builder");
237
238            // Overwrite the last `len` elements of the builder. These would have been
239            // populated by the inner.append_to_builder() call above.
240            let output = typed_builder.values_mut();
241            let trailer = output.len() - len;
242
243            apply_patches_primitive::<V>(
244                &mut output[trailer..],
245                offset,
246                len,
247                array.n_lanes(),
248                lane_offsets.as_slice::<u32>(),
249                indices.as_slice::<u16>(),
250                values.as_slice::<V>(),
251            );
252        });
253
254        Ok(())
255    }
256
257    fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
258        PatchedSlots::NAMES[idx].to_string()
259    }
260
261    fn execute(array: Array<Self>, _ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
262        let array = require_child!(array, array.inner(), PatchedSlots::INNER => Primitive);
263        let array =
264            require_child!(array, array.lane_offsets(), PatchedSlots::LANE_OFFSETS => Primitive);
265        let array =
266            require_child!(array, array.patch_indices(), PatchedSlots::PATCH_INDICES => Primitive);
267        let array =
268            require_child!(array, array.patch_values(), PatchedSlots::PATCH_VALUES => Primitive);
269
270        let len = array.len();
271
272        let n_lanes = array.n_lanes;
273        let offset = array.offset;
274        let slots = match array.try_into_parts() {
275            Ok(parts) => PatchedSlots::from_slots(parts.slots),
276            Err(array) => PatchedSlotsView::from_slots(array.slots()).to_owned(),
277        };
278
279        // TODO(joe): use iterative execution
280        let PrimitiveDataParts {
281            buffer,
282            ptype,
283            validity,
284        } = slots.inner.downcast::<Primitive>().into_data_parts();
285
286        let values = slots.patch_values.downcast::<Primitive>();
287        let lane_offsets = slots.lane_offsets.downcast::<Primitive>();
288        let patch_indices = slots.patch_indices.downcast::<Primitive>();
289
290        let patched_values = match_each_native_ptype!(values.ptype(), |V| {
291            let mut output = Buffer::<V>::from_byte_buffer(buffer.unwrap_host()).into_mut();
292
293            apply_patches_primitive::<V>(
294                &mut output,
295                offset,
296                len,
297                n_lanes,
298                lane_offsets.as_slice::<u32>(),
299                patch_indices.as_slice::<u16>(),
300                values.as_slice::<V>(),
301            );
302
303            let output = output.freeze();
304
305            PrimitiveArray::from_byte_buffer(output.into_byte_buffer(), ptype, validity)
306        });
307
308        Ok(ExecutionResult::done(patched_values.into_array()))
309    }
310
311    fn reduce_parent(
312        array: ArrayView<'_, Self>,
313        parent: &ArrayRef,
314        child_idx: usize,
315    ) -> VortexResult<Option<ArrayRef>> {
316        PARENT_RULES.evaluate(array, parent, child_idx)
317    }
318}
319
320/// Apply patches on top of the existing value types.
321fn apply_patches_primitive<V: NativePType>(
322    output: &mut [V],
323    offset: usize,
324    len: usize,
325    n_lanes: usize,
326    lane_offsets: &[u32],
327    indices: &[u16],
328    values: &[V],
329) {
330    let n_chunks = (offset + len).div_ceil(1024);
331    for chunk in 0..n_chunks {
332        let start = lane_offsets[chunk * n_lanes] as usize;
333        let stop = lane_offsets[chunk * n_lanes + n_lanes] as usize;
334
335        for idx in start..stop {
336            // the indices slice is measured as an offset into the 1024-value chunk.
337            let index = chunk * 1024 + indices[idx] as usize;
338            if index < offset || index >= offset + len {
339                continue;
340            }
341
342            let value = values[idx];
343            output[index - offset] = value;
344        }
345    }
346}
347
348#[cfg(test)]
349mod tests {
350    use std::sync::LazyLock;
351
352    use rstest::rstest;
353    use vortex_buffer::ByteBufferMut;
354    use vortex_buffer::buffer;
355    use vortex_buffer::buffer_mut;
356    use vortex_error::VortexResult;
357    use vortex_session::VortexSession;
358    use vortex_session::registry::ReadContext;
359
360    use crate::Array;
361    use crate::ArrayContext;
362    use crate::ArrayParts;
363    use crate::ArraySlots;
364    use crate::IntoArray;
365    use crate::VortexSessionExecute;
366    use crate::arrays::Patched;
367    use crate::arrays::PatchedArray;
368    use crate::arrays::PrimitiveArray;
369    use crate::arrays::patched::PatchedArrayExt;
370    use crate::arrays::patched::PatchedArraySlotsExt;
371    use crate::arrays::patched::PatchedData;
372    use crate::arrays::patched::PatchedSlots;
373    use crate::arrays::patched::PatchedSlotsView;
374    use crate::assert_arrays_eq;
375    use crate::builders::builder_with_capacity_in;
376    use crate::patches::Patches;
377    use crate::serde::SerializeOptions;
378    use crate::serde::SerializedArray;
379    use crate::session::ArraySessionExt;
380    use crate::validity::Validity;
381
382    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
383
384    #[test]
385    fn test_execute() {
386        let mut ctx = SESSION.create_execution_ctx();
387        let values = buffer![0u16; 1024].into_array();
388        let patches = Patches::new(
389            1024,
390            0,
391            buffer![1u32, 2, 3].into_array(),
392            buffer![1u16; 3].into_array(),
393            None,
394            &mut ctx,
395        )
396        .unwrap();
397
398        let mut ctx = SESSION.create_execution_ctx();
399
400        let array = Patched::from_array_and_patches(values, &patches, &mut ctx)
401            .unwrap()
402            .into_array();
403
404        let mut expected = buffer_mut![0u16; 1024];
405        expected[1] = 1;
406        expected[2] = 1;
407        expected[3] = 1;
408
409        assert_arrays_eq!(array, expected.into_array(), &mut ctx);
410    }
411
412    #[test]
413    fn test_execute_sliced() {
414        let mut ctx = SESSION.create_execution_ctx();
415        let values = buffer![0u16; 1024].into_array();
416        let patches = Patches::new(
417            1024,
418            0,
419            buffer![1u32, 2, 3].into_array(),
420            buffer![1u16; 3].into_array(),
421            None,
422            &mut ctx,
423        )
424        .unwrap();
425
426        let mut ctx = SESSION.create_execution_ctx();
427
428        let array = Patched::from_array_and_patches(values, &patches, &mut ctx)
429            .unwrap()
430            .into_array()
431            .slice(3..1024)
432            .unwrap();
433
434        let mut expected = buffer_mut![0u16; 1021];
435        expected[0] = 1;
436
437        assert_arrays_eq!(array, expected.into_array(), &mut ctx);
438    }
439
440    #[test]
441    fn test_append_to_builder_non_nullable() {
442        let mut ctx = SESSION.create_execution_ctx();
443        let values = PrimitiveArray::new(buffer![0u16; 1024], Validity::NonNullable).into_array();
444        let patches = Patches::new(
445            1024,
446            0,
447            buffer![1u32, 2, 3].into_array(),
448            buffer![10u16, 20, 30].into_array(),
449            None,
450            &mut ctx,
451        )
452        .unwrap();
453
454        let mut ctx = SESSION.create_execution_ctx();
455
456        let array = Patched::from_array_and_patches(values, &patches, &mut ctx)
457            .unwrap()
458            .into_array();
459
460        let mut builder = builder_with_capacity_in(
461            array.dtype(),
462            array.len(),
463            vortex_buffer::BufferAllocatorRef::static_ref(),
464        );
465        array.append_to_builder(builder.as_mut(), &mut ctx).unwrap();
466
467        let result = builder.finish();
468
469        let mut expected = buffer_mut![0u16; 1024];
470        expected[1] = 10;
471        expected[2] = 20;
472        expected[3] = 30;
473        let expected = expected.into_array();
474
475        assert_arrays_eq!(result, expected, &mut ctx);
476    }
477
478    #[test]
479    fn test_append_to_builder_sliced() {
480        let mut ctx = SESSION.create_execution_ctx();
481        let values = PrimitiveArray::new(buffer![0u16; 1024], Validity::NonNullable).into_array();
482        let patches = Patches::new(
483            1024,
484            0,
485            buffer![1u32, 2, 3].into_array(),
486            buffer![10u16, 20, 30].into_array(),
487            None,
488            &mut ctx,
489        )
490        .unwrap();
491
492        let mut ctx = SESSION.create_execution_ctx();
493
494        let array = Patched::from_array_and_patches(values, &patches, &mut ctx)
495            .unwrap()
496            .into_array()
497            .slice(3..1024)
498            .unwrap();
499
500        let mut builder = builder_with_capacity_in(
501            array.dtype(),
502            array.len(),
503            vortex_buffer::BufferAllocatorRef::static_ref(),
504        );
505        array.append_to_builder(builder.as_mut(), &mut ctx).unwrap();
506
507        let result = builder.finish();
508
509        let mut expected = buffer_mut![0u16; 1021];
510        expected[0] = 30;
511        let expected = expected.into_array();
512
513        assert_arrays_eq!(result, expected, &mut ctx);
514    }
515
516    #[test]
517    fn test_append_to_builder_with_validity() {
518        let mut ctx = SESSION.create_execution_ctx();
519        // Create inner array with nulls at indices 0 and 5.
520        let validity = Validity::from_iter((0..10).map(|i| i != 0 && i != 5));
521        let values = PrimitiveArray::new(buffer![0u16; 10], validity).into_array();
522
523        // Apply patches at indices 1, 2, 3.
524        let patches = Patches::new(
525            10,
526            0,
527            buffer![1u32, 2, 3].into_array(),
528            buffer![10u16, 20, 30].into_array(),
529            None,
530            &mut ctx,
531        )
532        .unwrap();
533
534        let mut ctx = SESSION.create_execution_ctx();
535
536        let array = Patched::from_array_and_patches(values, &patches, &mut ctx)
537            .unwrap()
538            .into_array();
539
540        let mut builder = builder_with_capacity_in(
541            array.dtype(),
542            array.len(),
543            vortex_buffer::BufferAllocatorRef::static_ref(),
544        );
545        array.append_to_builder(builder.as_mut(), &mut ctx).unwrap();
546
547        let result = builder.finish();
548
549        // Expected: null at 0, patched 10/20/30 at 1/2/3, zero at 4, null at 5, zeros at 6-9.
550        let expected = PrimitiveArray::from_option_iter([
551            None,
552            Some(10u16),
553            Some(20),
554            Some(30),
555            Some(0),
556            None,
557            Some(0),
558            Some(0),
559            Some(0),
560            Some(0),
561        ])
562        .into_array();
563
564        assert_arrays_eq!(result, expected, &mut ctx);
565    }
566
567    fn make_patched_array(
568        inner: impl IntoIterator<Item = u16>,
569        patch_indices: &[u32],
570        patch_values: &[u16],
571    ) -> VortexResult<PatchedArray> {
572        let mut ctx = SESSION.create_execution_ctx();
573        let values: Vec<u16> = inner.into_iter().collect();
574        let len = values.len();
575        let array = PrimitiveArray::from_iter(values).into_array();
576
577        let indices = PrimitiveArray::from_iter(patch_indices.iter().copied()).into_array();
578        let patch_vals = PrimitiveArray::from_iter(patch_values.iter().copied()).into_array();
579
580        let patches = Patches::new(len, 0, indices, patch_vals, None, &mut ctx)?;
581
582        let mut ctx = SESSION.create_execution_ctx();
583
584        Patched::from_array_and_patches(array, &patches, &mut ctx)
585    }
586
587    #[rstest]
588    #[case::basic(
589        make_patched_array(vec![0u16; 1024], &[1, 2, 3], &[10, 20, 30]).unwrap().into_array(),
590        (0..1024).map(|i| match i { 1 => 10u16, 2 => 20, 3 => 30, _ => 0 }).collect::<Vec<_>>()
591    )]
592    #[case::multi_chunk(
593        make_patched_array(vec![0u16; 4096], &[100, 1500, 2500, 3500], &[11, 22, 33, 44]).unwrap().into_array(),
594        (0..4096).map(|i| match i { 100 => 11u16, 1500 => 22, 2500 => 33, 3500 => 44, _ => 0 }).collect::<Vec<_>>()
595    )]
596    #[case::sliced({
597        let arr = make_patched_array(vec![0u16; 1024], &[1, 2, 3], &[10, 20, 30]).unwrap();
598        arr.into_array().slice(2..1024).unwrap()
599    }, (2..1024).map(|i| match i { 2 => 20u16, 3 => 30, _ => 0 }).collect::<Vec<_>>())]
600    fn test_serde_roundtrip(#[case] array: crate::ArrayRef, #[case] expected: Vec<u16>) {
601        let dtype = array.dtype().clone();
602        let len = array.len();
603
604        let session = VortexSession::empty();
605        session.arrays().register(Patched);
606
607        let ctx = ArrayContext::empty().with_allowed_ids(
608            session
609                .arrays()
610                .registry()
611                .read(|map| map.keys().copied().collect()),
612        );
613        let serialized = array
614            .serialize(&ctx, &session, &SerializeOptions::default())
615            .unwrap();
616
617        // Concat into a single buffer.
618        let mut concat = ByteBufferMut::empty();
619        for buf in serialized {
620            concat.extend_from_slice(buf.as_ref());
621        }
622        let concat = concat.freeze();
623
624        let parts = SerializedArray::try_from(concat).unwrap();
625        let decoded = parts
626            .decode(&dtype, len, &ReadContext::new(ctx.to_ids()), &session)
627            .unwrap();
628
629        assert!(decoded.is::<Patched>());
630        let expected = PrimitiveArray::from_iter(expected);
631        let mut exec_ctx = session.create_execution_ctx();
632        assert_arrays_eq!(array, &expected, &mut exec_ctx);
633        assert_arrays_eq!(decoded, expected, &mut exec_ctx);
634    }
635
636    #[test]
637    fn test_with_slots_basic() -> VortexResult<()> {
638        let array = make_patched_array(vec![0u16; 1024], &[1, 2, 3], &[10, 20, 30])?;
639
640        // Get original children via accessor methods
641        let slots = PatchedSlots::from_slots(
642            array
643                .as_array()
644                .slots()
645                .iter()
646                .cloned()
647                .collect::<ArraySlots>(),
648        );
649        let view = PatchedSlotsView::from_slots(array.as_array().slots());
650        assert_eq!(view.inner.len(), array.inner().len());
651
652        // Create new PatchedArray with same children using with_slots
653        let array_ref = array.into_array();
654        // SAFETY: the replacement slots are the original children, preserving logical values and
655        // parent statistics.
656        let new_array = unsafe { array_ref.clone().with_slots(slots.into_slots()) }?;
657
658        assert!(new_array.is::<Patched>());
659        assert_eq!(array_ref.len(), new_array.len());
660        assert_eq!(array_ref.dtype(), new_array.dtype());
661
662        let mut ctx = SESSION.create_execution_ctx();
663
664        let expected = PrimitiveArray::from_iter((0..1024).map(|i| match i {
665            1 => 10u16,
666            2 => 20,
667            3 => 30,
668            _ => 0,
669        }));
670        assert_arrays_eq!(new_array, expected, &mut ctx);
671
672        Ok(())
673    }
674
675    #[test]
676    fn test_rebuild_modified_inner_from_parts() -> VortexResult<()> {
677        let array = make_patched_array(vec![0u16; 10], &[1, 2, 3], &[10, 20, 30])?;
678
679        // Create a different inner array (all 5s instead of 0s)
680        let new_inner = PrimitiveArray::from_iter(vec![5u16; 10]).into_array();
681        let slots = PatchedSlots {
682            inner: new_inner,
683            lane_offsets: array.lane_offsets().clone(),
684            patch_indices: array.patch_indices().clone(),
685            patch_values: array.patch_values().clone(),
686        };
687
688        let data = PatchedData {
689            n_lanes: array.n_lanes(),
690            offset: array.offset(),
691        };
692        let new_array = Array::try_from_parts(ArrayParts::new(
693            Patched,
694            array.dtype().clone(),
695            array.len(),
696            data,
697            slots.into_slots(),
698        ))?
699        .into_array();
700
701        // Execute and verify the inner values changed (except at patch positions)
702        let mut ctx = SESSION.create_execution_ctx();
703
704        // Expected: all 5s except indices 1, 2, 3 which are patched to 10, 20, 30
705        let expected = PrimitiveArray::from_iter([5u16, 10, 20, 30, 5, 5, 5, 5, 5, 5]);
706        assert_arrays_eq!(new_array, expected, &mut ctx);
707
708        Ok(())
709    }
710}