Skip to main content

vortex_array/arrays/runend/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Debug;
5use std::fmt::Display;
6use std::fmt::Formatter;
7use std::hash::Hash;
8use std::hash::Hasher;
9
10use prost::Message;
11use vortex_error::VortexExpect as _;
12use vortex_error::VortexResult;
13use vortex_error::vortex_bail;
14use vortex_error::vortex_ensure;
15use vortex_error::vortex_ensure_eq;
16use vortex_error::vortex_err;
17use vortex_error::vortex_panic;
18use vortex_session::VortexSession;
19use vortex_session::registry::CachedId;
20
21use crate::AnyCanonical;
22use crate::Array;
23use crate::ArrayEq;
24use crate::ArrayHash;
25use crate::ArrayId;
26use crate::ArrayParts;
27use crate::ArrayRef;
28use crate::ArrayView;
29use crate::EqMode;
30use crate::ExecutionCtx;
31use crate::ExecutionResult;
32use crate::IntoArray;
33use crate::TypedArrayRef;
34use crate::VortexSessionExecute;
35use crate::array_slots;
36use crate::arrays::DecimalArray;
37use crate::arrays::ListViewArray;
38use crate::arrays::Primitive;
39use crate::arrays::PrimitiveArray;
40use crate::arrays::VarBinViewArray;
41use crate::arrays::listview::ListViewArraySlotsExt;
42use crate::arrays::runend::compress::runend_decode_decimal;
43use crate::arrays::runend::compress::runend_decode_primitive;
44use crate::arrays::runend::compress::runend_decode_varbinview;
45use crate::arrays::runend::compress::runend_encode;
46use crate::arrays::runend::decompress_bool::runend_decode_bools;
47use crate::arrays::runend::ops::find_physical_index;
48use crate::arrays::runend::ops::find_slice_end_index;
49use crate::arrays::runend::rules::RULES;
50use crate::buffer::BufferHandle;
51use crate::dtype::DType;
52use crate::dtype::Nullability;
53use crate::dtype::PType;
54use crate::require_child;
55use crate::serde::ArrayChildren;
56use crate::validity::Validity;
57use crate::vtable::VTable;
58use crate::vtable::ValidityVTable;
59
60/// A [`RunEnd`]-encoded Vortex array.
61pub type RunEndArray = Array<RunEnd>;
62
63#[derive(Clone, prost::Message)]
64pub struct RunEndMetadata {
65    #[prost(int32, tag = "1")]
66    pub(crate) ends_ptype: i32,
67    #[prost(uint64, tag = "2")]
68    pub(crate) num_runs: u64,
69    #[prost(uint64, tag = "3")]
70    pub(crate) offset: u64,
71}
72
73impl RunEndMetadata {
74    fn get_ends_ptype(&self) -> VortexResult<PType> {
75        PType::try_from(self.ends_ptype).map_err(|_| {
76            vortex_err!(
77                "RunEndMetadata ends_ptype must be a known PType, got {}",
78                self.ends_ptype
79            )
80        })
81    }
82}
83
84impl ArrayHash for RunEndData {
85    fn array_hash<H: Hasher>(&self, state: &mut H, _accuracy: EqMode) {
86        self.offset.hash(state);
87    }
88}
89
90impl ArrayEq for RunEndData {
91    fn array_eq(&self, other: &Self, _accuracy: EqMode) -> bool {
92        self.offset == other.offset
93    }
94}
95
96impl VTable for RunEnd {
97    type TypedArrayData = RunEndData;
98
99    type OperationsVTable = Self;
100    type ValidityVTable = Self;
101
102    fn id(&self) -> ArrayId {
103        static ID: CachedId = CachedId::new("vortex.runend");
104        *ID
105    }
106
107    fn validate(
108        &self,
109        data: &Self::TypedArrayData,
110        dtype: &DType,
111        len: usize,
112        slots: &[Option<ArrayRef>],
113    ) -> VortexResult<()> {
114        let run_end_slots = RunEndSlotsView::from_slots(slots);
115        let ends = run_end_slots.ends;
116        let values = run_end_slots.values;
117        RunEndData::validate_shape(ends, values, data.offset, len)?;
118        vortex_ensure_eq!(values.dtype(), dtype);
119        Ok(())
120    }
121
122    fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
123        0
124    }
125
126    fn buffer(_array: ArrayView<'_, Self>, idx: usize) -> BufferHandle {
127        vortex_panic!("RunEndArray buffer index {idx} out of bounds")
128    }
129
130    fn buffer_name(_array: ArrayView<'_, Self>, idx: usize) -> Option<String> {
131        vortex_panic!("RunEndArray buffer_name index {idx} out of bounds")
132    }
133
134    fn with_buffers(
135        &self,
136        array: ArrayView<'_, Self>,
137        buffers: &[BufferHandle],
138    ) -> VortexResult<ArrayParts<Self>> {
139        crate::vtable::with_empty_buffers(self, array, buffers)
140    }
141
142    fn serialize(
143        array: ArrayView<'_, Self>,
144        _session: &VortexSession,
145    ) -> VortexResult<Option<Vec<u8>>> {
146        Ok(Some(
147            RunEndMetadata {
148                ends_ptype: PType::try_from(array.ends().dtype())
149                    .vortex_expect("Must be a valid PType") as i32,
150                num_runs: array.ends().len() as u64,
151                offset: array.offset() as u64,
152            }
153            .encode_to_vec(),
154        ))
155    }
156
157    fn deserialize(
158        &self,
159        dtype: &DType,
160        len: usize,
161        metadata: &[u8],
162        _buffers: &[BufferHandle],
163        children: &dyn ArrayChildren,
164        session: &VortexSession,
165    ) -> VortexResult<ArrayParts<Self>> {
166        let metadata = RunEndMetadata::decode(metadata)?;
167        let ends_ptype = metadata.get_ends_ptype()?;
168        let ends_dtype = DType::Primitive(ends_ptype, Nullability::NonNullable);
169        let runs = usize::try_from(metadata.num_runs).vortex_expect("Must be a valid usize");
170        let ends = children.get(0, &ends_dtype, runs)?;
171
172        let values = children.get(1, dtype, runs)?;
173        let offset = usize::try_from(metadata.offset).vortex_expect("Offset must be a valid usize");
174        RunEndData::validate_parts(
175            &ends,
176            &values,
177            offset,
178            len,
179            &mut session.create_execution_ctx(),
180        )?;
181        let slots = RunEndSlots { ends, values }.into_slots();
182        let data = RunEndData::new(offset);
183        Ok(ArrayParts::new(
184            self.clone(),
185            dtype.clone(),
186            len,
187            data,
188            slots,
189        ))
190    }
191
192    fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
193        RunEndSlots::NAMES[idx].to_string()
194    }
195
196    fn reduce_parent(
197        array: ArrayView<'_, Self>,
198        parent: &ArrayRef,
199        child_idx: usize,
200    ) -> VortexResult<Option<ArrayRef>> {
201        RULES.evaluate(array, parent, child_idx)
202    }
203
204    fn execute(array: Array<Self>, ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
205        let array = require_child!(array, array.ends(), RunEndSlots::ENDS => Primitive);
206        let array = require_child!(array, array.values(), RunEndSlots::VALUES => AnyCanonical);
207        run_end_canonicalize(&array, ctx).map(ExecutionResult::done)
208    }
209}
210
211#[array_slots(RunEnd)]
212pub struct RunEndSlots {
213    /// The run-end positions marking where each run terminates.
214    #[slot(0)]
215    pub ends: ArrayRef,
216    /// The values for each run.
217    #[slot(1)]
218    pub values: ArrayRef,
219}
220
221#[derive(Clone, Debug)]
222pub struct RunEndData {
223    offset: usize,
224}
225
226impl Display for RunEndData {
227    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
228        write!(f, "offset: {}", self.offset)
229    }
230}
231
232pub struct RunEndDataParts {
233    pub ends: ArrayRef,
234    pub values: ArrayRef,
235    pub offset: usize,
236}
237
238pub trait RunEndArrayExt: RunEndArraySlotsExt {
239    fn offset(&self) -> usize {
240        self.offset
241    }
242
243    fn dtype(&self) -> &DType {
244        self.values().dtype()
245    }
246
247    fn find_physical_index(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
248        find_physical_index(self.ends(), index + self.offset(), ctx)
249    }
250
251    fn find_slice_end_index(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
252        find_slice_end_index(self.ends(), index + self.offset(), ctx)
253    }
254}
255
256impl<T: TypedArrayRef<RunEnd>> RunEndArrayExt for T {}
257
258#[derive(Clone, Debug)]
259pub struct RunEnd;
260
261impl RunEnd {
262    /// Build a new [`RunEndArray`] without validation.
263    ///
264    /// # Safety
265    /// See [`RunEndData::new_unchecked`] for preconditions.
266    pub unsafe fn new_unchecked(
267        ends: ArrayRef,
268        values: ArrayRef,
269        offset: usize,
270        length: usize,
271    ) -> RunEndArray {
272        let dtype = values.dtype().clone();
273        let slots = RunEndSlots { ends, values }.into_slots();
274        let data = unsafe { RunEndData::new_unchecked(offset) };
275        unsafe { Array::from_parts_unchecked(ArrayParts::new(RunEnd, dtype, length, data, slots)) }
276    }
277
278    /// Build a new [`RunEndArray`] from ends and values.
279    pub fn try_new(
280        ends: ArrayRef,
281        values: ArrayRef,
282        ctx: &mut ExecutionCtx,
283    ) -> VortexResult<RunEndArray> {
284        let len = RunEndData::logical_len_from_ends(&ends, ctx)?;
285        RunEndData::validate_parts(&ends, &values, 0, len, ctx)?;
286        let dtype = values.dtype().clone();
287        let slots = RunEndSlots { ends, values }.into_slots();
288        let data = RunEndData::new(0);
289        Array::try_from_parts(ArrayParts::new(RunEnd, dtype, len, data, slots))
290    }
291
292    /// Build a new [`RunEndArray`] from ends, values, offset, and length.
293    pub fn try_new_offset_length(
294        ends: ArrayRef,
295        values: ArrayRef,
296        offset: usize,
297        length: usize,
298        ctx: &mut ExecutionCtx,
299    ) -> VortexResult<RunEndArray> {
300        RunEndData::validate_parts(&ends, &values, offset, length, ctx)?;
301        let dtype = values.dtype().clone();
302        let slots = RunEndSlots { ends, values }.into_slots();
303        let data = RunEndData::new(offset);
304        Array::try_from_parts(ArrayParts::new(RunEnd, dtype, length, data, slots))
305    }
306
307    /// Build a new [`RunEndArray`] from ends and values (panics on invalid input).
308    pub fn new(ends: ArrayRef, values: ArrayRef, ctx: &mut ExecutionCtx) -> RunEndArray {
309        Self::try_new(ends, values, ctx).vortex_expect("RunEndData is always valid")
310    }
311
312    /// Run the array through run-end encoding.
313    pub fn encode(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<RunEndArray> {
314        if let Some(parray) = array.as_opt::<Primitive>() {
315            let (ends, values) = runend_encode(parray, ctx);
316            let ends = ends.into_array();
317            let len = array.len();
318            let dtype = values.dtype().clone();
319            let slots = RunEndSlots { ends, values }.into_slots();
320            let data = unsafe { RunEndData::new_unchecked(0) };
321            Array::try_from_parts(ArrayParts::new(RunEnd, dtype, len, data, slots))
322        } else {
323            vortex_bail!("REE can only encode primitive arrays")
324        }
325    }
326}
327
328impl RunEndData {
329    fn logical_len_from_ends(ends: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
330        if ends.is_empty() {
331            Ok(0)
332        } else {
333            usize::try_from(&ends.execute_scalar(ends.len() - 1, ctx)?)
334        }
335    }
336
337    /// Validate that `ends` and `values` form a well-formed run-end array covering
338    /// `offset..offset + length`.
339    pub fn validate_parts(
340        ends: &ArrayRef,
341        values: &ArrayRef,
342        offset: usize,
343        length: usize,
344        ctx: &mut ExecutionCtx,
345    ) -> VortexResult<()> {
346        if !Self::validate_shape(ends, values, offset, length)? {
347            return Ok(());
348        }
349
350        #[cfg(debug_assertions)]
351        {
352            // Run ends must be strictly sorted for binary search to work correctly.
353            let pre_validation = ends.statistics().to_owned();
354
355            let is_sorted = ends
356                .statistics()
357                .compute_is_strict_sorted(ctx)
358                .unwrap_or(false);
359
360            // Preserve the original statistics since compute_is_strict_sorted may have mutated them.
361            // We don't want to run with different stats in debug mode and outside.
362            ends.statistics().inherit(pre_validation.iter());
363            debug_assert!(is_sorted);
364        }
365
366        // Skip host-only validation when ends are not host-resident.
367        if !ends.is_host() {
368            return Ok(());
369        }
370
371        let first_run_end = if offset == 0 {
372            0
373        } else {
374            usize::try_from(&ends.execute_scalar(0, ctx)?)?
375        };
376        let last_run_end = usize::try_from(&ends.execute_scalar(ends.len() - 1, ctx)?)?;
377        Self::validate_run_end_bounds(first_run_end, last_run_end, offset, length)
378    }
379
380    /// Validates the dtypes and lengths of the parts. Returns `false` when there are no runs to
381    /// check against `offset..offset + length`.
382    fn validate_shape(
383        ends: &ArrayRef,
384        values: &ArrayRef,
385        offset: usize,
386        length: usize,
387    ) -> VortexResult<bool> {
388        // DType validation
389        vortex_ensure!(
390            ends.dtype().is_unsigned_int(),
391            "run ends must be unsigned integers, was {}",
392            ends.dtype(),
393        );
394        vortex_ensure_eq!(ends.len(), values.len());
395
396        // Handle empty run-ends
397        if ends.is_empty() {
398            vortex_ensure_eq!(offset, 0, "non-zero offset provided for empty RunEndArray");
399            return Ok(false);
400        }
401
402        // Zero-length logical slices may retain run metadata from the source array.
403        Ok(length != 0)
404    }
405
406    /// Validates that the first and last run ends cover `offset..offset + length`.
407    fn validate_run_end_bounds(
408        first_run_end: usize,
409        last_run_end: usize,
410        offset: usize,
411        length: usize,
412    ) -> VortexResult<()> {
413        if first_run_end < offset {
414            vortex_bail!("First run end {first_run_end} must be >= offset {offset}");
415        }
416
417        let min_required_end = offset + length;
418        if last_run_end < min_required_end {
419            vortex_bail!("Last run end {last_run_end} must be >= offset+length {min_required_end}");
420        }
421
422        Ok(())
423    }
424}
425
426impl RunEndData {
427    /// Build a new `RunEndArray` from an array of run `ends` and an array of `values`.
428    ///
429    /// Panics if any of the validation conditions described in [`RunEnd::try_new`] is
430    /// not satisfied.
431    ///
432    /// # Examples
433    ///
434    /// ```
435    /// # use vortex_array::arrays::BoolArray;
436    /// # use vortex_array::arrays::runend::RunEnd;
437    /// # use vortex_array::IntoArray;
438    /// # use vortex_session::VortexSession;
439    /// # use vortex_array::VortexSessionExecute;
440    /// # use vortex_buffer::buffer;
441    /// # use vortex_error::VortexResult;
442    /// # fn main() -> VortexResult<()> {
443    /// let session = VortexSession::empty();
444    /// let mut ctx = session.create_execution_ctx();
445    /// let ends = buffer![2u8, 3u8].into_array();
446    /// let values = BoolArray::from_iter([false, true]).into_array();
447    /// let run_end = RunEnd::new(ends, values, &mut ctx);
448    ///
449    /// // Array encodes
450    /// assert_eq!(run_end.execute_scalar(0, &mut ctx)?, false.into());
451    /// assert_eq!(run_end.execute_scalar(1, &mut ctx)?, false.into());
452    /// assert_eq!(run_end.execute_scalar(2, &mut ctx)?, true.into());
453    /// # Ok(())
454    /// # }
455    /// ```
456    pub fn new(offset: usize) -> Self {
457        Self { offset }
458    }
459
460    /// Build a new `RunEndArray` without validation.
461    ///
462    /// # Safety
463    ///
464    /// The caller must ensure that all the validation performed in
465    /// [`RunEnd::try_new_offset_length`] is
466    /// satisfied before calling this function.
467    ///
468    /// See [`RunEnd::try_new_offset_length`] for the preconditions needed to build a new array.
469    pub unsafe fn new_unchecked(offset: usize) -> Self {
470        Self { offset }
471    }
472
473    /// Run the array through run-end encoding.
474    pub fn encode(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Self> {
475        if let Some(parray) = array.as_opt::<Primitive>() {
476            let (_ends, _values) = runend_encode(parray, ctx);
477            // SAFETY: runend_encode handles this
478            unsafe { Ok(Self::new_unchecked(0)) }
479        } else {
480            vortex_bail!("REE can only encode primitive arrays")
481        }
482    }
483
484    pub fn into_parts(self, ends: ArrayRef, values: ArrayRef) -> RunEndDataParts {
485        RunEndDataParts {
486            ends,
487            values,
488            offset: self.offset,
489        }
490    }
491}
492
493impl ValidityVTable<RunEnd> for RunEnd {
494    fn validity(array: ArrayView<'_, RunEnd>) -> VortexResult<Validity> {
495        Ok(match array.values().validity()? {
496            Validity::NonNullable | Validity::AllValid => Validity::AllValid,
497            Validity::AllInvalid => Validity::AllInvalid,
498            Validity::Array(values_validity) => Validity::Array(unsafe {
499                RunEnd::new_unchecked(
500                    array.ends().clone(),
501                    values_validity,
502                    array.offset(),
503                    array.len(),
504                )
505                .into_array()
506            }),
507        })
508    }
509}
510
511pub(super) fn run_end_canonicalize(
512    array: &RunEndArray,
513    ctx: &mut ExecutionCtx,
514) -> VortexResult<ArrayRef> {
515    let pends = array.ends().clone().execute_as("ends", ctx)?;
516
517    Ok(match array.dtype() {
518        DType::Bool(_) => {
519            let bools = array.values().clone().execute_as("values", ctx)?;
520            runend_decode_bools(pends, bools, array.offset(), array.len(), ctx)?
521        }
522        DType::Primitive(..) => {
523            let pvalues = array.values().clone().execute_as("values", ctx)?;
524            runend_decode_primitive(pends, pvalues, array.offset(), array.len(), ctx)?
525        }
526        DType::Decimal(..) => {
527            let values = array
528                .values()
529                .clone()
530                .execute_as::<DecimalArray>("values", ctx)?;
531            runend_decode_decimal(pends, values, array.offset(), array.len(), ctx)?
532        }
533        DType::Utf8(_) | DType::Binary(_) => {
534            let values = array
535                .values()
536                .clone()
537                .execute_as::<VarBinViewArray>("values", ctx)?;
538            runend_decode_varbinview(pends, values, array.offset(), array.len(), ctx)?
539        }
540        DType::List(..) => {
541            let values = array
542                .values()
543                .clone()
544                .execute_as::<ListViewArray>("values", ctx)?;
545            runend_decode_listview(pends, values, array.offset(), array.len())?.into_array()
546        }
547        _ => vortex_bail!("Unsupported RunEnd value type: {}", array.dtype()),
548    })
549}
550
551fn runend_decode_listview(
552    ends: PrimitiveArray,
553    values: ListViewArray,
554    offset: usize,
555    length: usize,
556) -> VortexResult<ListViewArray> {
557    let validity = match values.validity()? {
558        Validity::NonNullable => Validity::NonNullable,
559        Validity::AllValid => Validity::AllValid,
560        Validity::AllInvalid => Validity::AllInvalid,
561        Validity::Array(validity) => Validity::Array(unsafe {
562            RunEnd::new_unchecked(ends.clone().into_array(), validity, offset, length).into_array()
563        }),
564    };
565
566    // SAFETY: the `RunEndArray`s re-express valid per-run ListView metadata over the logical output
567    // length. The original `elements` child is reused, so every view still points at a valid range.
568    Ok(unsafe {
569        ListViewArray::new_unchecked(
570            values.elements().clone(),
571            RunEnd::new_unchecked(
572                ends.clone().into_array(),
573                values.offsets().clone(),
574                offset,
575                length,
576            )
577            .into_array(),
578            RunEnd::new_unchecked(ends.into_array(), values.sizes().clone(), offset, length)
579                .into_array(),
580            validity,
581        )
582    })
583}
584
585#[cfg(test)]
586mod tests {
587    use std::sync::Arc;
588    use std::sync::LazyLock;
589
590    use prost::Message;
591    use vortex_buffer::buffer;
592    use vortex_error::VortexResult;
593    use vortex_session::VortexSession;
594
595    use super::RunEndMetadata;
596    use crate::ArrayRef;
597    use crate::IntoArray;
598    use crate::VortexSessionExecute;
599    use crate::arrays::DecimalArray;
600    use crate::arrays::DictArray;
601    use crate::arrays::ListArray;
602    use crate::arrays::ListViewArray;
603    use crate::arrays::VarBinViewArray;
604    use crate::arrays::listview::ListViewArraySlotsExt;
605    use crate::arrays::runend::RunEnd;
606    use crate::assert_arrays_eq;
607    use crate::builders::VarBinBuilder;
608    use crate::dtype::DType;
609    use crate::dtype::DecimalDType;
610    use crate::dtype::Nullability;
611    use crate::dtype::PType;
612    use crate::dtype::i256;
613    use crate::validity::Validity;
614    use crate::vtable::VTable;
615
616    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
617
618    #[test]
619    fn test_runend_constructor() {
620        let mut ctx = SESSION.create_execution_ctx();
621        let arr = RunEnd::new(
622            buffer![2u32, 5, 10].into_array(),
623            buffer![1i32, 2, 3].into_array(),
624            &mut ctx,
625        );
626        assert_eq!(arr.len(), 10);
627        assert_eq!(
628            arr.dtype(),
629            &DType::Primitive(PType::I32, Nullability::NonNullable)
630        );
631
632        // 0, 1 => 1
633        // 2, 3, 4 => 2
634        // 5, 6, 7, 8, 9 => 3
635        let expected = buffer![1, 1, 2, 2, 2, 3, 3, 3, 3, 3].into_array();
636        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
637    }
638
639    #[test]
640    fn test_runend_utf8() {
641        let mut ctx = SESSION.create_execution_ctx();
642        let values =
643            VarBinViewArray::from_iter_nullable_str([Some("a"), None, Some("c")]).into_array();
644        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
645        assert_eq!(arr.len(), 10);
646        assert_eq!(arr.dtype(), &DType::Utf8(Nullability::Nullable));
647
648        let expected = VarBinViewArray::from_iter_nullable_str([
649            Some("a"),
650            Some("a"),
651            None,
652            None,
653            None,
654            Some("c"),
655            Some("c"),
656            Some("c"),
657            Some("c"),
658            Some("c"),
659        ])
660        .into_array();
661        let mut builder = VarBinBuilder::<i32>::with_capacity_in(
662            arr.dtype().clone(),
663            arr.len(),
664            vortex_buffer::BufferAllocatorRef::static_ref(),
665        );
666        arr.append_to_builder(&mut builder, &mut ctx).unwrap();
667        assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
668        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
669    }
670
671    #[test]
672    fn test_runend_decimal() {
673        let mut ctx = SESSION.create_execution_ctx();
674        let decimal_dtype = DecimalDType::new(10, 2);
675        let values = DecimalArray::from_iter([12345i64, 67890, -12300], decimal_dtype).into_array();
676        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
677        assert_eq!(arr.len(), 10);
678        assert_eq!(
679            arr.dtype(),
680            &DType::Decimal(decimal_dtype, Nullability::NonNullable)
681        );
682
683        let expected = DecimalArray::from_iter(
684            [
685                12345i64, 12345, 67890, 67890, 67890, -12300, -12300, -12300, -12300, -12300,
686            ],
687            decimal_dtype,
688        )
689        .into_array();
690        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
691    }
692
693    #[test]
694    fn test_runend_list_i64() {
695        let mut ctx = SESSION.create_execution_ctx();
696        let values = ListArray::from_iter_slow::<u32, _>(
697            vec![vec![1i64, 2], vec![3], vec![4, 5, 6]],
698            Arc::new(DType::Primitive(PType::I64, Nullability::NonNullable)),
699        )
700        .unwrap()
701        .into_array();
702        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
703
704        let expected = ListArray::from_iter_slow::<u32, _>(
705            vec![
706                vec![1i64, 2],
707                vec![1, 2],
708                vec![3],
709                vec![3],
710                vec![3],
711                vec![4, 5, 6],
712                vec![4, 5, 6],
713                vec![4, 5, 6],
714                vec![4, 5, 6],
715                vec![4, 5, 6],
716            ],
717            Arc::new(DType::Primitive(PType::I64, Nullability::NonNullable)),
718        )
719        .unwrap()
720        .into_array();
721        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
722    }
723
724    #[test]
725    fn test_runend_nullable_decimal() {
726        let mut ctx = SESSION.create_execution_ctx();
727        let decimal_dtype = DecimalDType::new(10, 2);
728        let values =
729            DecimalArray::from_option_iter([Some(12345i64), None, Some(-12300)], decimal_dtype)
730                .into_array();
731        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
732        assert_eq!(arr.len(), 10);
733        assert_eq!(
734            arr.dtype(),
735            &DType::Decimal(decimal_dtype, Nullability::Nullable)
736        );
737
738        let expected = DecimalArray::from_option_iter(
739            [
740                Some(12345i64),
741                Some(12345),
742                None,
743                None,
744                None,
745                Some(-12300),
746                Some(-12300),
747                Some(-12300),
748                Some(-12300),
749                Some(-12300),
750            ],
751            decimal_dtype,
752        )
753        .into_array();
754        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
755    }
756
757    #[test]
758    fn test_runend_list_bool() {
759        let mut ctx = SESSION.create_execution_ctx();
760        let values = ListArray::from_iter_slow::<u32, _>(
761            vec![vec![true, false], vec![false], vec![true, true, false]],
762            Arc::new(DType::Bool(Nullability::NonNullable)),
763        )
764        .unwrap()
765        .into_array();
766        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
767
768        let expected = ListArray::from_iter_slow::<u32, _>(
769            vec![
770                vec![true, false],
771                vec![true, false],
772                vec![false],
773                vec![false],
774                vec![false],
775                vec![true, true, false],
776                vec![true, true, false],
777                vec![true, true, false],
778                vec![true, true, false],
779                vec![true, true, false],
780            ],
781            Arc::new(DType::Bool(Nullability::NonNullable)),
782        )
783        .unwrap()
784        .into_array();
785        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
786    }
787
788    #[test]
789    fn test_runend_list_utf8() {
790        let mut ctx = SESSION.create_execution_ctx();
791        let values = ListArray::try_new(
792            VarBinViewArray::from_iter_str(["a", "b", "c", "d", "e", "f"]).into_array(),
793            buffer![0u32, 2, 3, 6].into_array(),
794            Validity::NonNullable,
795            &mut ctx,
796        )
797        .unwrap()
798        .into_array();
799        let arr = RunEnd::new(buffer![2u32, 5, 10].into_array(), values, &mut ctx);
800
801        let expected = ListArray::try_new(
802            VarBinViewArray::from_iter_str([
803                "a", "b", "a", "b", "c", "c", "c", "d", "e", "f", "d", "e", "f", "d", "e", "f",
804                "d", "e", "f", "d", "e", "f",
805            ])
806            .into_array(),
807            buffer![0u32, 2, 4, 5, 6, 7, 10, 13, 16, 19, 22].into_array(),
808            Validity::NonNullable,
809            &mut ctx,
810        )
811        .unwrap()
812        .into_array();
813        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
814    }
815
816    #[test]
817    fn test_runend_list_canonicalizes_to_runend_listview_slots() -> VortexResult<()> {
818        let mut ctx = SESSION.create_execution_ctx();
819        let values = ListArray::try_new(
820            buffer![1i64, 2, 3, 4, 5, 6].into_array(),
821            buffer![0u32, 2, 3, 6].into_array(),
822            Validity::from_iter([true, false, true]),
823            &mut ctx,
824        )?
825        .into_array();
826        let arr = RunEnd::try_new(buffer![2u32, 5, 6].into_array(), values, &mut ctx)?;
827
828        let listview = arr
829            .clone()
830            .into_array()
831            .execute::<ListViewArray>(&mut ctx)?;
832        assert!(listview.offsets().is::<RunEnd>());
833        assert!(listview.sizes().is::<RunEnd>());
834        match listview.validity()? {
835            Validity::Array(validity) => assert!(validity.is::<RunEnd>()),
836            validity => panic!("expected array-backed validity, got {validity:?}"),
837        }
838
839        let expected = ListArray::try_new(
840            buffer![1i64, 2, 1, 2, 3, 3, 3, 4, 5, 6].into_array(),
841            buffer![0u32, 2, 4, 5, 6, 7, 10].into_array(),
842            Validity::from_iter([true, true, false, false, false, true]),
843            &mut ctx,
844        )?
845        .into_array();
846        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
847        Ok(())
848    }
849
850    #[test]
851    fn test_runend_dict() {
852        let mut ctx = SESSION.create_execution_ctx();
853        let dict_values = VarBinViewArray::from_iter_str(["x", "y", "z"]).into_array();
854        let dict_codes = buffer![0u32, 1, 2].into_array();
855        let dict = DictArray::try_new(dict_codes, dict_values).unwrap();
856
857        let arr = RunEnd::try_new(
858            buffer![2u32, 5, 10].into_array(),
859            dict.into_array(),
860            &mut ctx,
861        )
862        .unwrap();
863        assert_eq!(arr.len(), 10);
864
865        let expected =
866            VarBinViewArray::from_iter_str(["x", "x", "y", "y", "y", "z", "z", "z", "z", "z"])
867                .into_array();
868        assert_arrays_eq!(arr.into_array(), expected, &mut ctx);
869    }
870
871    #[test]
872    fn test_runend_decimal_i128() -> VortexResult<()> {
873        let mut ctx = SESSION.create_execution_ctx();
874        let decimal_dtype = DecimalDType::new(20, 2);
875        let values = DecimalArray::from_iter([12_345i128, -67_890, 100], decimal_dtype);
876        let arr = RunEnd::try_new(
877            buffer![2u32, 5, 6].into_array(),
878            values.into_array(),
879            &mut ctx,
880        )?;
881
882        let expected = DecimalArray::from_iter(
883            [12_345i128, 12_345, -67_890, -67_890, -67_890, 100],
884            decimal_dtype,
885        );
886        assert_arrays_eq!(arr, expected, &mut ctx);
887        Ok(())
888    }
889
890    #[test]
891    fn test_runend_decimal_nullable() -> VortexResult<()> {
892        let mut ctx = SESSION.create_execution_ctx();
893        let decimal_dtype = DecimalDType::new(20, 2);
894        let values =
895            DecimalArray::from_option_iter([Some(12_345i128), None, Some(-67_890)], decimal_dtype);
896        let arr = RunEnd::try_new(
897            buffer![2u32, 5, 7].into_array(),
898            values.into_array(),
899            &mut ctx,
900        )?;
901
902        let expected = DecimalArray::from_option_iter(
903            [
904                Some(12_345i128),
905                Some(12_345),
906                None,
907                None,
908                None,
909                Some(-67_890),
910                Some(-67_890),
911            ],
912            decimal_dtype,
913        );
914        assert_arrays_eq!(arr, expected, &mut ctx);
915        Ok(())
916    }
917
918    #[test]
919    fn test_runend_decimal_slice() -> VortexResult<()> {
920        let mut ctx = SESSION.create_execution_ctx();
921        let decimal_dtype = DecimalDType::new(20, 2);
922        let values = DecimalArray::from_iter([100i128, 200, 300], decimal_dtype);
923        let arr = RunEnd::try_new(
924            buffer![3u32, 5, 10].into_array(),
925            values.into_array(),
926            &mut ctx,
927        )?;
928
929        let sliced = arr.slice(2..8)?;
930        let expected = DecimalArray::from_iter([100i128, 200, 200, 300, 300, 300], decimal_dtype);
931        assert_arrays_eq!(sliced, expected, &mut ctx);
932        Ok(())
933    }
934
935    #[test]
936    fn test_runend_decimal_i256() -> VortexResult<()> {
937        let mut ctx = SESSION.create_execution_ctx();
938        let decimal_dtype = DecimalDType::new(40, 4);
939        let first = i256::from_i128(123_456);
940        let second = i256::from_i128(-789_012);
941        let values = DecimalArray::from_iter([first, second], decimal_dtype);
942        let arr = RunEnd::try_new(buffer![2u32, 5].into_array(), values.into_array(), &mut ctx)?;
943
944        let expected =
945            DecimalArray::from_iter([first, first, second, second, second], decimal_dtype);
946        assert_arrays_eq!(arr, expected, &mut ctx);
947        Ok(())
948    }
949
950    #[test]
951    fn test_deserialize_rejects_unknown_ends_ptype() -> VortexResult<()> {
952        let metadata = RunEndMetadata {
953            ends_ptype: 11,
954            ..Default::default()
955        }
956        .encode_to_vec();
957        let children: Vec<ArrayRef> = Vec::new();
958        let result = RunEnd.deserialize(
959            &DType::Primitive(PType::I32, Nullability::NonNullable),
960            0,
961            &metadata,
962            &[],
963            &children,
964            &SESSION,
965        );
966        assert!(result.is_err_and(|err| {
967            err.to_string()
968                .contains("RunEndMetadata ends_ptype must be a known PType, got 11")
969        }));
970
971        let known = RunEndMetadata {
972            ends_ptype: PType::U32 as i32,
973            ..Default::default()
974        };
975        assert_eq!(known.get_ends_ptype()?, PType::U32);
976
977        Ok(())
978    }
979}