1mod array;
43mod execute;
44
45use vortex_error::VortexExpect;
46use vortex_error::VortexResult;
47use vortex_error::vortex_bail;
48use vortex_error::vortex_ensure;
49use vortex_error::vortex_ensure_eq;
50use vortex_error::vortex_panic;
51use vortex_session::VortexSession;
52use vortex_session::registry::CachedId;
53
54pub use self::array::InterleaveArray;
55pub use self::array::InterleaveArrayExt;
56pub use self::array::InterleaveData;
57use self::array::InterleaveSlots;
58use crate::ArrayRef;
59use crate::ExecutionCtx;
60use crate::IntoArray;
61use crate::array::Array;
62use crate::array::ArrayId;
63use crate::array::ArrayParts;
64use crate::array::ArraySlots;
65use crate::array::ArrayView;
66use crate::array::OperationsVTable;
67use crate::array::VTable;
68use crate::array::ValidityVTable;
69use crate::array::with_empty_buffers;
70use crate::arrays::ConstantArray;
71use crate::buffer::BufferHandle;
72use crate::dtype::DType;
73use crate::dtype::Nullability;
74use crate::executor::ExecutionResult;
75use crate::scalar::Scalar;
76use crate::serde::ArrayChildren;
77use crate::validity::Validity;
78
79#[derive(Clone, Debug)]
81pub struct Interleave;
82
83impl Interleave {
84 fn check(
90 values: &[ArrayRef],
91 array_indices: &ArrayRef,
92 row_indices: &ArrayRef,
93 ) -> VortexResult<DType> {
94 vortex_ensure!(
95 values.len() >= 2,
96 "interleave requires at least 2 values, got {}",
97 values.len()
98 );
99
100 for (name, selector) in [
103 ("array_indices", array_indices),
104 ("row_indices", row_indices),
105 ] {
106 match selector.dtype() {
107 DType::Primitive(ptype, nullability) if ptype.is_unsigned_int() => {
108 vortex_ensure!(
109 !nullability.is_nullable(),
110 "interleave {name} must be non-nullable, got {}",
111 selector.dtype()
112 );
113 }
114 other => vortex_bail!(
115 "interleave {name} must be a non-nullable unsigned integer, got {other}"
116 ),
117 }
118 }
119
120 vortex_ensure_eq!(
121 array_indices.len(),
122 row_indices.len(),
123 "interleave selectors must have equal length",
124 );
125
126 let base_dtype = values[0].dtype();
127 let mut nullability = Nullability::NonNullable;
128 for value in values {
129 vortex_ensure!(
130 value.dtype().eq_ignore_nullability(base_dtype),
131 "interleave values must share a dtype up to nullability: {} vs {}",
132 base_dtype,
133 value.dtype()
134 );
135 nullability |= value.dtype().nullability();
136 }
137
138 Ok(base_dtype.with_nullability(nullability))
139 }
140}
141
142impl VTable for Interleave {
143 type TypedArrayData = InterleaveData;
144 type OperationsVTable = Self;
145 type ValidityVTable = Self;
146
147 fn id(&self) -> ArrayId {
148 static ID: CachedId = CachedId::new("vortex.interleave");
149 *ID
150 }
151
152 fn validate(
153 &self,
154 data: &Self::TypedArrayData,
155 dtype: &DType,
156 len: usize,
157 slots: &[Option<ArrayRef>],
158 ) -> VortexResult<()> {
159 vortex_ensure_eq!(
160 slots.len(),
161 data.num_values + InterleaveSlots::FIXED_COUNT,
162 "InterleaveArray expects values + array_indices + row_indices slots",
163 );
164 vortex_ensure!(
165 slots.iter().all(|s| s.is_some()),
166 "InterleaveArray slots must all be present"
167 );
168
169 let array_indices = slots[InterleaveSlots::ARRAY_INDICES]
170 .clone()
171 .vortex_expect("validated array_indices slot");
172 let row_indices = slots[InterleaveSlots::ROW_INDICES]
173 .clone()
174 .vortex_expect("validated row_indices slot");
175 let values: Vec<ArrayRef> = slots[InterleaveSlots::VALUES_OFFSET..]
176 .iter()
177 .map(|s| s.clone().vortex_expect("validated value slot"))
178 .collect();
179
180 let expected_dtype = Interleave::check(&values, &array_indices, &row_indices)?;
183 vortex_ensure_eq!(
184 dtype,
185 &expected_dtype,
186 "InterleaveArray dtype does not match the dtype implied by its children",
187 );
188 vortex_ensure_eq!(
189 len,
190 array_indices.len(),
191 "InterleaveArray length does not match array_indices length",
192 );
193 Ok(())
194 }
195
196 fn nbuffers(_array: ArrayView<'_, Self>) -> usize {
197 0
198 }
199
200 fn buffer(_array: ArrayView<'_, Self>, _idx: usize) -> BufferHandle {
201 vortex_panic!("InterleaveArray has no buffers")
202 }
203
204 fn buffer_name(_array: ArrayView<'_, Self>, _idx: usize) -> Option<String> {
205 None
206 }
207
208 fn with_buffers(
209 &self,
210 array: ArrayView<'_, Self>,
211 buffers: &[BufferHandle],
212 ) -> VortexResult<ArrayParts<Self>> {
213 with_empty_buffers(self, array, buffers)
214 }
215
216 fn slot_name(_array: ArrayView<'_, Self>, idx: usize) -> String {
217 InterleaveSlots::slot_name(idx)
218 }
219
220 fn serialize(
221 _array: ArrayView<'_, Self>,
222 _session: &VortexSession,
223 ) -> VortexResult<Option<Vec<u8>>> {
224 Ok(None)
225 }
226
227 fn deserialize(
228 &self,
229 _dtype: &DType,
230 _len: usize,
231 _metadata: &[u8],
232 _buffers: &[BufferHandle],
233 _children: &dyn ArrayChildren,
234 _session: &VortexSession,
235 ) -> VortexResult<ArrayParts<Self>> {
236 vortex_bail!("Interleave array is not serializable")
237 }
238
239 fn execute(array: Array<Self>, ctx: &mut ExecutionCtx) -> VortexResult<ExecutionResult> {
240 execute::execute(array, ctx)
241 }
242}
243
244impl OperationsVTable<Interleave> for Interleave {
245 type ProbeState = ();
246
247 fn scalar_at(
248 array: ArrayView<'_, Interleave>,
249 index: usize,
250 ctx: &mut ExecutionCtx,
251 ) -> VortexResult<Scalar> {
252 let branch_idx = array
255 .array_indices()
256 .execute_scalar(index, ctx)?
257 .as_primitive()
258 .as_::<usize>()
259 .vortex_expect("interleave array_indices is non-nullable");
260 let row = array
261 .row_indices()
262 .execute_scalar(index, ctx)?
263 .as_primitive()
264 .as_::<usize>()
265 .vortex_expect("interleave row_indices is non-nullable");
266
267 let scalar = array.value(branch_idx).execute_scalar(row, ctx)?;
268 Ok(if array.as_ref().dtype().is_nullable() {
270 scalar.into_nullable()
271 } else {
272 scalar
273 })
274 }
275}
276
277impl ValidityVTable<Interleave> for Interleave {
278 fn validity(array: ArrayView<'_, Interleave>) -> VortexResult<Validity> {
279 if !array.as_ref().dtype().is_nullable() {
280 return Ok(Validity::NonNullable);
281 }
282 let num_values = array.num_values();
283 let mut slots: ArraySlots =
284 ArraySlots::with_capacity(num_values + InterleaveSlots::FIXED_COUNT);
285 slots.push(Some(array.array_indices().clone()));
286 slots.push(Some(array.row_indices().clone()));
287 for i in 0..num_values {
288 slots.push(Some(value_validity_array(array.value(i))?));
289 }
290 let interleaved = unsafe {
293 InterleaveArray::new_unchecked_slots(slots, DType::Bool(Nullability::NonNullable))
294 };
295 Ok(Validity::Array(interleaved.into_array()))
296 }
297}
298
299fn value_validity_array(value: &ArrayRef) -> VortexResult<ArrayRef> {
302 Ok(match value.validity()? {
303 Validity::NonNullable | Validity::AllValid => {
304 ConstantArray::new(true, value.len()).into_array()
305 }
306 Validity::AllInvalid => ConstantArray::new(false, value.len()).into_array(),
307 Validity::Array(array) => array,
308 })
309}
310
311#[cfg(test)]
312mod tests {
313 use std::sync::LazyLock;
314
315 use rstest::rstest;
316 use vortex_error::VortexResult;
317 use vortex_session::VortexSession;
318
319 use super::*;
320 use crate::AnyColumnar;
321 use crate::Canonical;
322 use crate::VortexSessionExecute;
323 use crate::arrays::Bool;
324 use crate::arrays::BoolArray;
325 use crate::arrays::DecimalArray;
326 use crate::arrays::Primitive;
327 use crate::arrays::PrimitiveArray;
328 use crate::arrays::SliceArray;
329 use crate::assert_arrays_eq;
330 use crate::dtype::DecimalDType;
331 use crate::dtype::PType;
332
333 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
334
335 #[derive(Clone, Copy)]
336 enum LazyChild {
337 ArraySelector,
338 RowSelector,
339 ThirdValue,
340 }
341
342 #[derive(Clone, Copy)]
344 enum ValueKind {
345 Bool,
346 Primitive,
347 Decimal,
348 }
349
350 #[rstest]
351 #[case::array_selector(LazyChild::ArraySelector)]
352 #[case::row_selector(LazyChild::RowSelector)]
353 #[case::third_value(LazyChild::ThirdValue)]
354 fn executes_lazy_children(
355 #[case] lazy_child: LazyChild,
356 #[values(ValueKind::Bool, ValueKind::Primitive, ValueKind::Decimal)] value_kind: ValueKind,
357 ) -> VortexResult<()> {
358 let decimal_dtype = DecimalDType::new(9, 2);
359 let (mut values, expected) = match value_kind {
360 ValueKind::Bool => (
361 vec![
362 BoolArray::from_iter([true, false]).into_array(),
363 BoolArray::from_iter([false, true]).into_array(),
364 BoolArray::from_iter([Some(false), None]).into_array(),
365 ],
366 BoolArray::from_iter([None, Some(true), Some(true), Some(false), Some(false)])
367 .into_array(),
368 ),
369 ValueKind::Primitive => (
370 vec![
371 PrimitiveArray::from_iter([10i32, 11]).into_array(),
372 PrimitiveArray::from_iter([20i32, 21]).into_array(),
373 PrimitiveArray::from_option_iter([Some(30i32), None]).into_array(),
374 ],
375 PrimitiveArray::from_option_iter([None, Some(10i32), Some(21), Some(30), Some(11)])
376 .into_array(),
377 ),
378 ValueKind::Decimal => (
379 vec![
380 DecimalArray::from_iter([10i32, 11], decimal_dtype).into_array(),
381 DecimalArray::from_iter([20i32, 21], decimal_dtype).into_array(),
382 DecimalArray::from_option_iter([Some(30i32), None], decimal_dtype).into_array(),
383 ],
384 DecimalArray::from_option_iter(
385 [None, Some(10i32), Some(21), Some(30), Some(11)],
386 decimal_dtype,
387 )
388 .into_array(),
389 ),
390 };
391 let mut array_indices = PrimitiveArray::from_iter([2u8, 0, 1, 2, 0]).into_array();
392 let mut row_indices = PrimitiveArray::from_iter([1u32, 0, 1, 0, 1]).into_array();
393 let child = match lazy_child {
394 LazyChild::ArraySelector => &mut array_indices,
395 LazyChild::RowSelector => &mut row_indices,
396 LazyChild::ThirdValue => &mut values[2],
397 };
398 *child = SliceArray::try_new(child.clone(), 0..child.len())?.into_array();
399
400 assert_eq!(
401 array_indices.is::<Primitive>(),
402 !matches!(lazy_child, LazyChild::ArraySelector)
403 );
404 assert_eq!(
405 row_indices.is::<Primitive>(),
406 !matches!(lazy_child, LazyChild::RowSelector)
407 );
408 for (i, value) in values.iter().enumerate() {
409 let matches = match value_kind {
410 ValueKind::Bool => value.is::<Bool>(),
411 ValueKind::Primitive | ValueKind::Decimal => value.is::<AnyColumnar>(),
412 };
413 assert_eq!(
414 matches,
415 !(matches!(lazy_child, LazyChild::ThirdValue) && i == 2)
416 );
417 }
418
419 let interleaved =
420 InterleaveArray::try_new(values, array_indices, row_indices)?.into_array();
421 let mut ctx = SESSION.create_execution_ctx();
422 assert_arrays_eq!(interleaved, expected, &mut ctx);
423 Ok(())
424 }
425
426 fn interleave_reference(
433 values: &[ArrayRef],
434 array_indices: &ArrayRef,
435 row_indices: &ArrayRef,
436 ctx: &mut ExecutionCtx,
437 ) -> VortexResult<ArrayRef> {
438 let len = array_indices.len();
439 let nullable = values.iter().any(|v| v.dtype().is_nullable());
440 let mut out: Vec<Option<bool>> = Vec::with_capacity(len);
441
442 for i in 0..len {
443 let j = array_indices
444 .execute_scalar(i, ctx)?
445 .as_primitive()
446 .as_::<usize>()
447 .vortex_expect("array_indices is non-nullable");
448 let row = row_indices
449 .execute_scalar(i, ctx)?
450 .as_primitive()
451 .as_::<usize>()
452 .vortex_expect("row_indices is non-nullable");
453 out.push(values[j].execute_scalar(row, ctx)?.as_bool().value());
454 }
455
456 Ok(if nullable {
457 BoolArray::from_iter(out).into_array()
458 } else {
459 BoolArray::from_iter(
460 out.into_iter()
461 .map(|v| v.vortex_expect("non-nullable value produced a null")),
462 )
463 .into_array()
464 })
465 }
466
467 fn build(
470 branches: &[&[Option<bool>]],
471 indices: &[(usize, usize)],
472 ) -> (Vec<ArrayRef>, ArrayRef, ArrayRef) {
473 let nullable = branches.iter().flat_map(|b| b.iter()).any(Option::is_none);
474 let to_value = |vals: &[Option<bool>]| -> ArrayRef {
475 if nullable {
476 BoolArray::from_iter(vals.iter().copied()).into_array()
477 } else {
478 BoolArray::from_iter(
479 vals.iter()
480 .map(|v| v.vortex_expect("non-nullable value produced a null")),
481 )
482 .into_array()
483 }
484 };
485
486 let values = branches.iter().map(|b| to_value(b)).collect();
487 let array_indices = PrimitiveArray::from_iter(
488 indices
489 .iter()
490 .map(|&(a, _)| u32::try_from(a).vortex_expect("array index fits in u32")),
491 )
492 .into_array();
493 let row_indices = PrimitiveArray::from_iter(
494 indices
495 .iter()
496 .map(|&(_, r)| u32::try_from(r).vortex_expect("row index fits in u32")),
497 )
498 .into_array();
499 (values, array_indices, row_indices)
500 }
501
502 fn check(branches: &[&[Option<bool>]], indices: &[(usize, usize)]) -> VortexResult<()> {
506 let (values, array_indices, row_indices) = build(branches, indices);
507
508 let interleaved =
509 InterleaveArray::try_new(values.clone(), array_indices.clone(), row_indices.clone())?
510 .into_array();
511
512 let mut ctx = SESSION.create_execution_ctx();
513 let reference = interleave_reference(&values, &array_indices, &row_indices, &mut ctx)?;
514
515 assert_arrays_eq!(interleaved, reference, &mut ctx);
516 Ok(())
517 }
518
519 #[test]
520 fn interleave_reorders_and_repeats() -> VortexResult<()> {
521 check(
523 &[&[Some(true), Some(false)], &[Some(false), Some(true)]],
524 &[(0, 1), (1, 0), (0, 0), (1, 1), (0, 0)],
525 )
526 }
527
528 #[test]
529 fn interleave_skips_rows() -> VortexResult<()> {
530 check(
532 &[
533 &[Some(true), Some(false), Some(true)],
534 &[Some(false), Some(true)],
535 ],
536 &[(0, 0), (1, 1), (0, 2)],
537 )
538 }
539
540 #[test]
541 fn interleave_binary_spans_word_boundary() -> VortexResult<()> {
542 let branch0: Vec<Option<bool>> = (0..100).map(|i| Some(i % 3 == 0)).collect();
545 let branch1: Vec<Option<bool>> = (0..100).map(|i| Some(i % 5 == 0)).collect();
546 let indices: Vec<(usize, usize)> = (0..200).map(|i| (i % 2, (i * 7) % 100)).collect();
547 check(&[&branch0, &branch1], &indices)
548 }
549
550 #[test]
551 fn interleave_binary_nullable_spans_word_boundary() -> VortexResult<()> {
552 let branch0: Vec<Option<bool>> = (0..70)
554 .map(|i| (i % 4 != 0).then_some(i % 2 == 0))
555 .collect();
556 let branch1: Vec<Option<bool>> = (0..70)
557 .map(|i| (i % 3 != 0).then_some(i % 2 == 1))
558 .collect();
559 let indices: Vec<(usize, usize)> = (0..150).map(|i| (i % 2, (i * 11) % 70)).collect();
560 check(&[&branch0, &branch1], &indices)
561 }
562
563 #[test]
564 fn interleave_three_values() -> VortexResult<()> {
565 check(
567 &[
568 &[Some(true), Some(false)],
569 &[Some(false)],
570 &[Some(true), Some(true), Some(false)],
571 ],
572 &[(2, 1), (0, 0), (1, 0), (2, 2), (0, 1), (2, 0)],
573 )
574 }
575
576 #[test]
577 fn interleave_only_one_branch() -> VortexResult<()> {
578 check(
579 &[&[Some(true), Some(false), Some(true)], &[Some(false)]],
580 &[(0, 2), (0, 0), (0, 1)],
581 )
582 }
583
584 #[test]
585 fn interleave_nullable_with_nulls_in_values() -> VortexResult<()> {
586 check(
587 &[&[None, Some(true), None], &[Some(false), None]],
588 &[(1, 1), (0, 0), (1, 0), (0, 2), (0, 1)],
589 )
590 }
591
592 #[test]
593 fn interleave_empty() -> VortexResult<()> {
594 check(&[&[Some(true)], &[Some(false)]], &[])
595 }
596
597 #[test]
598 fn rejects_boolean_array_indices() {
599 let value = BoolArray::from_iter([true, false]).into_array();
600 let array_indices = BoolArray::from_iter([true, false]).into_array();
601 let row_indices = PrimitiveArray::from_iter([0u32, 1]).into_array();
602 let err = InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)
603 .err()
604 .vortex_expect("expected interleave to reject a boolean array_indices");
605 assert!(err.to_string().contains("unsigned integer"), "{err}");
606 }
607
608 #[test]
609 fn rejects_signed_integer_array_indices() {
610 let value = BoolArray::from_iter([true]).into_array();
611 let array_indices = PrimitiveArray::from_iter([0i32, 1]).into_array();
612 let row_indices = PrimitiveArray::from_iter([0u32, 0]).into_array();
613 let err = InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)
614 .err()
615 .vortex_expect("expected interleave to reject a signed integer array_indices");
616 assert!(err.to_string().contains("unsigned integer"), "{err}");
617 }
618
619 #[test]
620 fn rejects_nullable_row_indices() {
621 let value = BoolArray::from_iter([true, false]).into_array();
622 let array_indices = PrimitiveArray::from_iter([0u32, 1]).into_array();
623 let row_indices = PrimitiveArray::from_option_iter([Some(0u32), Some(1)]).into_array();
624 let err = InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)
625 .err()
626 .vortex_expect("expected interleave to reject nullable row_indices");
627 assert!(err.to_string().contains("non-nullable"), "{err}");
628 }
629
630 #[test]
631 fn rejects_mismatched_selector_lengths() {
632 let value = BoolArray::from_iter([true, false]).into_array();
633 let array_indices = PrimitiveArray::from_iter([0u32, 1]).into_array();
634 let row_indices = PrimitiveArray::from_iter([0u32]).into_array();
635 let err = InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)
636 .err()
637 .vortex_expect("expected interleave to reject mismatched selector lengths");
638 assert!(err.to_string().contains("equal length"), "{err}");
639 }
640
641 #[test]
642 fn execute_rejects_out_of_bounds_array_index() -> VortexResult<()> {
643 let value = BoolArray::from_iter([true]).into_array();
644 let array_indices = PrimitiveArray::from_iter([2u32]).into_array();
645 let row_indices = PrimitiveArray::from_iter([0u32]).into_array();
646 let interleaved =
647 InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)?
648 .into_array();
649
650 let mut ctx = SESSION.create_execution_ctx();
651 let err = interleaved
652 .execute::<Canonical>(&mut ctx)
653 .err()
654 .vortex_expect("expected execution to reject out-of-bounds array index");
655 assert!(
656 err.to_string().contains("array index out of bounds"),
657 "{err}"
658 );
659 Ok(())
660 }
661
662 #[test]
663 fn execute_rejects_out_of_bounds_row_index() -> VortexResult<()> {
664 let value = BoolArray::from_iter([true]).into_array();
665 let array_indices = PrimitiveArray::from_iter([0u32]).into_array();
666 let row_indices = PrimitiveArray::from_iter([1u32]).into_array();
667 let interleaved =
668 InterleaveArray::try_new(vec![value.clone(), value], array_indices, row_indices)?
669 .into_array();
670
671 let mut ctx = SESSION.create_execution_ctx();
672 let err = interleaved
673 .execute::<Canonical>(&mut ctx)
674 .err()
675 .vortex_expect("expected execution to reject out-of-bounds row index");
676 assert!(err.to_string().contains("row index out of bounds"), "{err}");
677 Ok(())
678 }
679
680 #[test]
681 fn executes_primitive_values() -> VortexResult<()> {
682 let v0 = PrimitiveArray::from_iter([1.0f64, 2.0]).into_array();
683 let v1 = PrimitiveArray::from_option_iter([Some(10.0f64), None]).into_array();
684 let array_indices = PrimitiveArray::from_iter([0u8, 1, 0, 1]).into_array();
685 let row_indices = PrimitiveArray::from_iter([0u32, 0, 1, 1]).into_array();
686 let interleaved =
687 InterleaveArray::try_new(vec![v0, v1], array_indices, row_indices)?.into_array();
688 let expected =
689 PrimitiveArray::from_option_iter([Some(1.0f64), Some(10.0), Some(2.0), None])
690 .into_array();
691 let mut ctx = SESSION.create_execution_ctx();
692 assert_arrays_eq!(interleaved, expected, &mut ctx);
693 Ok(())
694 }
695
696 #[test]
697 fn executes_primitive_constant_values() -> VortexResult<()> {
698 let constant = ConstantArray::new(1.0f64, 2).into_array();
699 let column = PrimitiveArray::from_iter([10.0f64, 20.0]).into_array();
700 let array_indices = PrimitiveArray::from_iter([0u8, 1, 0, 1]).into_array();
701 let row_indices = PrimitiveArray::from_iter([0u32, 0, 1, 1]).into_array();
702 let interleaved =
703 InterleaveArray::try_new(vec![constant, column], array_indices, row_indices)?
704 .into_array();
705 let expected = PrimitiveArray::from_iter([1.0f64, 10.0, 1.0, 20.0]).into_array();
706 let mut ctx = SESSION.create_execution_ctx();
707
708 assert_arrays_eq!(interleaved, expected, &mut ctx);
709 Ok(())
710 }
711
712 #[test]
713 fn executes_null_primitive_constant_values() -> VortexResult<()> {
714 let constant = ConstantArray::new(
715 Scalar::null(DType::Primitive(PType::F64, Nullability::Nullable)),
716 2,
717 )
718 .into_array();
719 let column = PrimitiveArray::from_iter([10.0f64, 20.0]).into_array();
720 let array_indices = PrimitiveArray::from_iter([0u8, 1, 0, 1]).into_array();
721 let row_indices = PrimitiveArray::from_iter([0u32, 0, 1, 1]).into_array();
722 let interleaved =
723 InterleaveArray::try_new(vec![constant, column], array_indices, row_indices)?
724 .into_array();
725 let expected =
726 PrimitiveArray::from_option_iter([None, Some(10.0f64), None, Some(20.0)]).into_array();
727 let mut ctx = SESSION.create_execution_ctx();
728
729 assert_arrays_eq!(interleaved, expected, &mut ctx);
730 Ok(())
731 }
732}