1use std::fmt::Debug;
5use std::hash::Hash;
6use std::ops::Range;
7
8use num_traits::NumCast;
9use vortex_buffer::BitBuffer;
10use vortex_buffer::BitBufferMut;
11use vortex_buffer::BufferAllocatorRef;
12use vortex_buffer::BufferMut;
13use vortex_error::VortexError;
14use vortex_error::VortexExpect as _;
15use vortex_error::VortexResult;
16use vortex_error::vortex_bail;
17use vortex_error::vortex_ensure;
18use vortex_error::vortex_ensure_eq;
19use vortex_error::vortex_err;
20use vortex_mask::AllOr;
21use vortex_mask::Mask;
22use vortex_mask::MaskValues;
23use vortex_utils::aliases::hash_map::HashMap;
24
25use crate::ArrayRef;
26use crate::ArraySlots;
27use crate::ExecutionCtx;
28use crate::IntoArray;
29use crate::arrays::Primitive;
30use crate::arrays::PrimitiveArray;
31use crate::arrays::primitive::PrimitiveArrayExt;
32use crate::builtins::ArrayBuiltins;
33use crate::dtype::DType;
34use crate::dtype::IntegerPType;
35use crate::dtype::NativePType;
36use crate::dtype::Nullability;
37use crate::dtype::Nullability::NonNullable;
38use crate::dtype::PType;
39use crate::dtype::UnsignedPType;
40use crate::match_each_unsigned_integer_ptype;
41use crate::scalar::Scalar;
42use crate::search_sorted::SearchResult;
43use crate::search_sorted::SearchSorted;
44use crate::search_sorted::SearchSortedPrimitiveArray;
45use crate::search_sorted::SearchSortedSide;
46use crate::validity::Validity;
47
48pub const PATCH_CHUNK_SIZE: usize = 1024;
51
52#[derive(Copy, Clone, prost::Message)]
53pub struct PatchesMetadata {
54 #[prost(uint64, tag = "1")]
55 len: u64,
56 #[prost(uint64, tag = "2")]
57 offset: u64,
58 #[prost(enumeration = "PType", tag = "3")]
59 indices_ptype: i32,
60 #[prost(uint64, optional, tag = "4")]
61 chunk_offsets_len: Option<u64>,
62 #[prost(enumeration = "PType", optional, tag = "5")]
63 chunk_offsets_ptype: Option<i32>,
64 #[prost(uint64, optional, tag = "6")]
65 offset_within_chunk: Option<u64>,
66}
67
68impl PatchesMetadata {
69 #[inline]
70 pub fn new(
71 len: usize,
72 offset: usize,
73 indices_ptype: PType,
74 chunk_offsets_len: Option<usize>,
75 chunk_offsets_ptype: Option<PType>,
76 offset_within_chunk: Option<usize>,
77 ) -> Self {
78 Self {
79 len: len as u64,
80 offset: offset as u64,
81 indices_ptype: indices_ptype as i32,
82 chunk_offsets_len: chunk_offsets_len.map(|len| len as u64),
83 chunk_offsets_ptype: chunk_offsets_ptype.map(|pt| pt as i32),
84 offset_within_chunk: offset_within_chunk.map(|len| len as u64),
85 }
86 }
87
88 #[inline]
89 pub fn len(&self) -> VortexResult<usize> {
90 usize::try_from(self.len).map_err(|_| vortex_err!("len does not fit in usize"))
91 }
92
93 #[inline]
94 pub fn is_empty(&self) -> bool {
95 self.len == 0
96 }
97
98 #[inline]
99 pub fn offset(&self) -> VortexResult<usize> {
100 usize::try_from(self.offset).map_err(|_| vortex_err!("offset does not fit in usize"))
101 }
102
103 #[inline]
104 pub fn chunk_offsets_dtype(&self) -> VortexResult<Option<DType>> {
105 self.chunk_offsets_ptype
106 .map(|t| {
107 PType::try_from(t)
108 .map_err(|e| vortex_err!("invalid i32 value {t} for PType: {}", e))
109 .map(|ptype| DType::Primitive(ptype, NonNullable))
110 })
111 .transpose()
112 }
113
114 #[inline]
115 pub fn indices_dtype(&self) -> VortexResult<DType> {
116 let ptype = PType::try_from(self.indices_ptype).map_err(|e| {
117 vortex_err!("invalid i32 value {} for PType: {}", self.indices_ptype, e)
118 })?;
119 vortex_ensure!(
120 ptype.is_unsigned_int(),
121 "Patch indices must be unsigned integers"
122 );
123 Ok(DType::Primitive(ptype, NonNullable))
124 }
125}
126
127#[derive(Clone, Debug, Hash, PartialEq, Eq)]
132pub struct PatchesData {
133 offset: usize,
134 offset_within_chunk: Option<usize>,
135}
136
137#[derive(Copy, Clone, Debug)]
139pub struct PatchSlotIndices {
140 pub indices: usize,
141 pub values: usize,
142 pub chunk_offsets: usize,
143}
144
145impl PatchesData {
146 pub fn from_patches(patches: &Patches) -> Self {
148 Self {
149 offset: patches.offset(),
150 offset_within_chunk: patches.offset_within_chunk(),
151 }
152 }
153
154 pub fn patches_from_slots(
159 patches_data: Option<&Self>,
160 len: usize,
161 slots: &[Option<ArrayRef>],
162 slot_idx: PatchSlotIndices,
163 ) -> Option<Patches> {
164 let data = patches_data?;
165 let indices = slots[slot_idx.indices]
166 .as_ref()
167 .vortex_expect("patches_data is set but patch_indices slot is missing");
168 let values = slots[slot_idx.values]
169 .as_ref()
170 .vortex_expect("patches_data is set but patch_values slot is missing");
171 Some(unsafe {
172 Patches::new_unchecked(
173 len,
174 data.offset,
175 indices.clone(),
176 values.clone(),
177 slots[slot_idx.chunk_offsets].clone(),
178 data.offset_within_chunk,
179 )
180 })
181 }
182
183 pub fn push_slots(slots: &mut ArraySlots, patches: Option<&Patches>) {
187 match patches {
188 Some(p) => {
189 slots.push(Some(p.indices().clone()));
190 slots.push(Some(p.values().clone()));
191 slots.push(p.chunk_offsets().clone());
192 }
193 None => {
194 slots.push(None);
195 slots.push(None);
196 slots.push(None);
197 }
198 }
199 }
200
201 #[inline]
203 pub fn offset(&self) -> usize {
204 self.offset
205 }
206
207 #[inline]
209 pub fn offset_within_chunk(&self) -> Option<usize> {
210 self.offset_within_chunk
211 }
212}
213
214#[derive(Debug, Clone)]
216pub struct Patches {
217 array_len: usize,
218 offset: usize,
219 indices: ArrayRef,
220 values: ArrayRef,
221 chunk_offsets: Option<ArrayRef>,
228 offset_within_chunk: Option<usize>,
238}
239
240impl Patches {
241 pub fn new(
242 array_len: usize,
243 offset: usize,
244 indices: ArrayRef,
245 values: ArrayRef,
246 chunk_offsets: Option<ArrayRef>,
247 ctx: &mut ExecutionCtx,
248 ) -> VortexResult<Self> {
249 vortex_ensure_eq!(indices.len(), values.len());
250 vortex_ensure!(
251 indices.dtype().is_unsigned_int() && !indices.dtype().is_nullable(),
252 "Patch indices must be non-nullable unsigned integers, got {:?}",
253 indices.dtype()
254 );
255
256 vortex_ensure!(
257 indices.len() <= array_len,
258 "Patch indices must be shorter than the array length"
259 );
260 vortex_ensure!(!indices.is_empty(), "Patch indices must not be empty");
261
262 if indices.is_host() && values.is_host() {
265 let max = usize::try_from(&indices.execute_scalar(indices.len() - 1, ctx)?)
266 .map_err(|_| vortex_err!("indices must be a number"))?;
267 vortex_ensure!(
268 max - offset < array_len,
269 "Patch indices {max:?}, offset {offset} are longer than the array length {array_len}"
270 );
271
272 #[cfg(debug_assertions)]
273 {
274 use crate::aggregate_fn::fns::is_sorted::is_strict_sorted;
275 assert!(
276 is_strict_sorted(&indices, ctx).unwrap_or(false),
277 "Patch indices must be strictly increasing"
278 );
279 }
280 }
281
282 Ok(Self {
283 array_len,
284 offset,
285 indices,
286 values,
287 chunk_offsets: chunk_offsets.clone(),
288 offset_within_chunk: chunk_offsets.map(|_| 0),
290 })
291 }
292
293 pub fn from_metadata(
298 array_len: usize,
299 metadata: &PatchesMetadata,
300 indices: ArrayRef,
301 values: ArrayRef,
302 chunk_offsets: Option<ArrayRef>,
303 ctx: &mut ExecutionCtx,
304 ) -> VortexResult<Self> {
305 let mut patches = Self::new(
306 array_len,
307 metadata.offset()?,
308 indices,
309 values,
310 chunk_offsets,
311 ctx,
312 )?;
313 if let Some(chunk_offsets) = &patches.chunk_offsets {
314 let offset_within_chunk = usize::try_from(metadata.offset_within_chunk())?;
315 let sliced_rows = patches.offset % PATCH_CHUNK_SIZE;
316 vortex_ensure!(
317 offset_within_chunk <= sliced_rows,
318 "Patch offset within chunk exceeds the sliced row count"
319 );
320
321 if chunk_offsets.len() > 1 && chunk_offsets.is_host() && patches.indices.is_host() {
324 let first_chunk_end = patches
325 .offset
326 .checked_add(PATCH_CHUNK_SIZE - sliced_rows)
327 .ok_or_else(|| vortex_err!("Patch chunk boundary overflows usize"))?;
328 let retained =
329 search_index_binary_search(&patches.indices, first_chunk_end, ctx)?.to_index();
330 let expected_offset = patches
331 .chunk_offset_at(1, ctx)?
332 .checked_sub(patches.chunk_offset_at(0, ctx)?)
333 .and_then(|count| count.checked_sub(retained))
334 .ok_or_else(|| vortex_err!("Invalid patch chunk offsets"))?;
335 vortex_ensure_eq!(
336 offset_within_chunk,
337 expected_offset,
338 "Patch offset within chunk disagrees with the patch indices"
339 );
340 }
341 patches.offset_within_chunk = Some(offset_within_chunk);
342 }
343 Ok(patches)
344 }
345
346 pub unsafe fn new_unchecked(
356 array_len: usize,
357 offset: usize,
358 indices: ArrayRef,
359 values: ArrayRef,
360 chunk_offsets: Option<ArrayRef>,
361 offset_within_chunk: Option<usize>,
362 ) -> Self {
363 Self {
364 array_len,
365 offset,
366 indices,
367 values,
368 chunk_offsets,
369 offset_within_chunk,
370 }
371 }
372
373 #[inline]
374 pub fn array_len(&self) -> usize {
375 self.array_len
376 }
377
378 #[inline]
379 pub fn num_patches(&self) -> usize {
380 self.indices.len()
381 }
382
383 #[inline]
384 pub fn dtype(&self) -> &DType {
385 self.values.dtype()
386 }
387
388 #[inline]
389 pub fn indices(&self) -> &ArrayRef {
390 &self.indices
391 }
392
393 #[inline]
394 pub fn into_indices(self) -> ArrayRef {
395 self.indices
396 }
397
398 #[inline]
399 pub fn indices_mut(&mut self) -> &mut ArrayRef {
400 &mut self.indices
401 }
402
403 #[inline]
404 pub fn values(&self) -> &ArrayRef {
405 &self.values
406 }
407
408 #[inline]
409 pub fn into_values(self) -> ArrayRef {
410 self.values
411 }
412
413 #[inline]
414 pub fn values_mut(&mut self) -> &mut ArrayRef {
415 &mut self.values
416 }
417
418 #[inline]
419 pub fn offset(&self) -> usize {
421 self.offset
422 }
423
424 #[inline]
425 pub fn chunk_offsets(&self) -> &Option<ArrayRef> {
426 &self.chunk_offsets
427 }
428
429 #[inline]
430 pub fn chunk_offset_at(&self, idx: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
431 let Some(chunk_offsets) = &self.chunk_offsets else {
432 vortex_bail!("chunk_offsets must be set to retrieve offset at index")
433 };
434
435 chunk_offsets
436 .execute_scalar(idx, ctx)?
437 .as_primitive()
438 .as_::<usize>()
439 .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))
440 }
441
442 #[inline]
451 pub fn offset_within_chunk(&self) -> Option<usize> {
452 self.offset_within_chunk
453 }
454
455 #[inline]
456 pub fn indices_ptype(&self) -> VortexResult<PType> {
457 PType::try_from(self.indices.dtype())
458 .map_err(|_| vortex_err!("indices dtype is not primitive"))
459 }
460
461 pub fn to_metadata(&self, len: usize, dtype: &DType) -> VortexResult<PatchesMetadata> {
462 if self.indices.len() > len {
463 vortex_bail!(
464 "Patch indices {} are longer than the array length {}",
465 self.indices.len(),
466 len
467 );
468 }
469 if self.values.dtype() != dtype {
470 vortex_bail!(
471 "Patch values dtype {} does not match array dtype {}",
472 self.values.dtype(),
473 dtype
474 );
475 }
476 let chunk_offsets_len = self.chunk_offsets.as_ref().map(|co| co.len());
477 let chunk_offsets_ptype = self.chunk_offsets.as_ref().map(|co| co.dtype().as_ptype());
478
479 Ok(PatchesMetadata::new(
480 self.indices.len(),
481 self.offset,
482 self.indices.dtype().as_ptype(),
483 chunk_offsets_len,
484 chunk_offsets_ptype,
485 self.offset_within_chunk,
486 ))
487 }
488
489 pub fn get_patched(
491 &self,
492 index: usize,
493 ctx: &mut ExecutionCtx,
494 ) -> VortexResult<Option<Scalar>> {
495 self.search_index(index, ctx)?
496 .to_found()
497 .map(|patch_idx| self.values().execute_scalar(patch_idx, ctx))
498 .transpose()
499 }
500
501 pub fn search_index(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<SearchResult> {
519 if self.chunk_offsets.is_some() {
520 return self.search_index_chunked(index, ctx);
521 }
522
523 search_index_binary_search(&self.indices, index + self.offset, ctx)
524 }
525
526 fn search_index_chunked(
536 &self,
537 index: usize,
538 ctx: &mut ExecutionCtx,
539 ) -> VortexResult<SearchResult> {
540 let Some(chunk_offsets) = &self.chunk_offsets else {
541 vortex_bail!("chunk_offsets is required to be set")
542 };
543
544 let Some(offset_within_chunk) = self.offset_within_chunk else {
545 vortex_bail!("offset_within_chunk is required to be set")
546 };
547
548 if index >= self.array_len() {
549 return Ok(SearchResult::NotFound(self.indices().len()));
550 }
551
552 let chunk_idx = (index + self.offset % PATCH_CHUNK_SIZE) / PATCH_CHUNK_SIZE;
553
554 let mut probe = chunk_offsets.repeated_probe();
557 let mut chunk_offset_at = |idx: usize| -> VortexResult<usize> {
558 probe
559 .execute_scalar(idx, ctx)?
560 .as_primitive()
561 .as_::<usize>()
562 .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))
563 };
564
565 let base_offset = chunk_offset_at(0)?;
567
568 let patches_start_idx = (chunk_offset_at(chunk_idx)? - base_offset)
569 .saturating_sub(offset_within_chunk);
576
577 let patches_end_idx = if chunk_idx < chunk_offsets.len() - 1 {
578 (chunk_offset_at(chunk_idx + 1)? - base_offset)
579 .saturating_sub(offset_within_chunk)
580 .min(self.indices.len())
581 } else {
582 self.indices.len()
583 };
584
585 let chunk_indices = self.indices.slice(patches_start_idx..patches_end_idx)?;
586 let result = search_index_binary_search(&chunk_indices, index + self.offset, ctx)?;
587
588 Ok(match result {
589 SearchResult::Found(idx) => SearchResult::Found(patches_start_idx + idx),
590 SearchResult::NotFound(idx) => SearchResult::NotFound(patches_start_idx + idx),
591 })
592 }
593
594 fn search_index_chunked_batch<T, O>(
600 &self,
601 indices: &[T],
602 chunk_offsets: &[O],
603 index: T,
604 ) -> VortexResult<SearchResult>
605 where
606 T: UnsignedPType,
607 O: UnsignedPType,
608 usize: TryFrom<T>,
609 usize: TryFrom<O>,
610 {
611 let Some(offset_within_chunk) = self.offset_within_chunk else {
612 vortex_bail!("offset_within_chunk is required to be set")
613 };
614
615 let chunk_idx = {
616 let Ok(index) = usize::try_from(index) else {
617 return Ok(SearchResult::NotFound(indices.len()));
619 };
620
621 if index >= self.array_len() {
622 return Ok(SearchResult::NotFound(self.indices().len()));
623 }
624
625 (index + self.offset % PATCH_CHUNK_SIZE) / PATCH_CHUNK_SIZE
626 };
627
628 let chunk_offset = usize::try_from(chunk_offsets[chunk_idx] - chunk_offsets[0])
630 .map_err(|_| vortex_err!("chunk_offset failed to convert to usize"))?;
631
632 let patches_start_idx = chunk_offset
633 .saturating_sub(offset_within_chunk);
640
641 let patches_end_idx = if chunk_idx < chunk_offsets.len() - 1 {
642 usize::try_from(chunk_offsets[chunk_idx + 1] - chunk_offsets[0])
643 .map_err(|_| vortex_err!("patches_end_idx failed to convert to usize"))?
644 .saturating_sub(offset_within_chunk)
645 .min(indices.len())
646 } else {
647 self.indices.len()
648 };
649
650 let Some(offset) = T::from(self.offset) else {
651 return Ok(SearchResult::NotFound(indices.len()));
653 };
654
655 let chunk_indices = &indices[patches_start_idx..patches_end_idx];
656 let result = chunk_indices.search_sorted(&(index + offset), SearchSortedSide::Left)?;
657
658 Ok(match result {
659 SearchResult::Found(idx) => SearchResult::Found(patches_start_idx + idx),
660 SearchResult::NotFound(idx) => SearchResult::NotFound(patches_start_idx + idx),
661 })
662 }
663
664 pub fn min_index(&self, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
666 let first = self
667 .indices
668 .execute_scalar(0, ctx)?
669 .as_primitive()
670 .as_::<usize>()
671 .ok_or_else(|| vortex_err!("index does not fit in usize"))?;
672 Ok(first - self.offset)
673 }
674
675 pub fn max_index(&self, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
677 let last = self
678 .indices
679 .execute_scalar(self.indices.len() - 1, ctx)?
680 .as_primitive()
681 .as_::<usize>()
682 .ok_or_else(|| vortex_err!("index does not fit in usize"))?;
683 Ok(last - self.offset)
684 }
685
686 pub fn filter(&self, mask: &Mask, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
688 if mask.len() != self.array_len {
689 vortex_bail!(
690 "Filter mask length {} does not match array length {}",
691 mask.len(),
692 self.array_len
693 );
694 }
695
696 match mask {
697 Mask::AllTrue(_) => Ok(Some(self.clone())),
698 Mask::AllFalse(_) => Ok(None),
699 Mask::Values(mask_values) => {
700 let flat_indices = self.indices().clone().execute::<PrimitiveArray>(ctx)?;
701 match_each_unsigned_integer_ptype!(flat_indices.ptype(), |I| {
702 filter_patches_with_mask(
703 flat_indices.as_slice::<I>(),
704 self.offset(),
705 self.values(),
706 mask_values,
707 ctx.allocator(),
708 )
709 })
710 }
711 }
712 }
713
714 pub fn mask(&self, mask: &Mask, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
723 if mask.len() != self.array_len {
724 vortex_bail!(
725 "Filter mask length {} does not match array length {}",
726 mask.len(),
727 self.array_len
728 );
729 }
730
731 let filter_mask = match mask.bit_buffer() {
732 AllOr::All => return Ok(None),
733 AllOr::None => return self.clone().into_nullable_values().map(Some),
734 AllOr::Some(masked) => {
735 let patch_indices = self.indices().clone().execute::<PrimitiveArray>(ctx)?;
736 match_each_unsigned_integer_ptype!(patch_indices.ptype(), |P| {
737 let patch_indices = patch_indices.as_slice::<P>();
738 Mask::from_buffer(BitBuffer::collect_bool_in(
739 patch_indices.len(),
740 |i| {
741 #[allow(clippy::cast_possible_truncation)]
742 let idx = (patch_indices[i] as usize) - self.offset;
743 !masked.value(idx)
744 },
745 ctx.allocator().clone(),
746 ))
747 })
748 }
749 };
750
751 if filter_mask.all_false() {
752 return Ok(None);
753 }
754
755 let filtered_indices = self.indices.filter(filter_mask.clone())?;
757 let filtered_values = self.values.filter(filter_mask)?;
758
759 Self {
760 array_len: self.array_len,
761 offset: self.offset,
762 indices: filtered_indices,
763 values: filtered_values,
764 chunk_offsets: None,
766 offset_within_chunk: self.offset_within_chunk,
767 }
768 .into_nullable_values()
769 .map(Some)
770 }
771
772 fn into_nullable_values(self) -> VortexResult<Self> {
777 if self.values.dtype().is_nullable() {
778 return Ok(self);
779 }
780 let nullable = self.values.dtype().as_nullable();
781 self.map_values(|values| values.cast(nullable))
782 }
783
784 pub fn slice(&self, range: Range<usize>, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
786 let slice_start_idx = self.search_index(range.start, ctx)?.to_index();
787 let slice_end_idx = self.search_index(range.end, ctx)?.to_index();
788
789 if slice_start_idx == slice_end_idx {
790 return Ok(None);
791 }
792
793 let values = self.values().slice(slice_start_idx..slice_end_idx)?;
794 let indices = self.indices().slice(slice_start_idx..slice_end_idx)?;
795
796 let new_chunk_offsets = self
797 .chunk_offsets
798 .as_ref()
799 .map(|chunk_offsets| -> VortexResult<ArrayRef> {
800 let chunk_relative_offset = self.offset % PATCH_CHUNK_SIZE;
801 let chunk_start_idx = (chunk_relative_offset + range.start) / PATCH_CHUNK_SIZE;
802 let chunk_end_idx = (chunk_relative_offset + range.end).div_ceil(PATCH_CHUNK_SIZE);
803 chunk_offsets.slice(chunk_start_idx..chunk_end_idx)
804 })
805 .transpose()?;
806
807 let offset_within_chunk = new_chunk_offsets
808 .as_ref()
809 .map(|new_chunk_offsets| -> VortexResult<usize> {
810 let new_chunk_base = new_chunk_offsets
811 .execute_scalar(0, ctx)?
812 .as_primitive()
813 .as_::<usize>()
814 .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))?;
815 let parent_chunk_base = self.chunk_offset_at(0, ctx)?;
816 let parent_within = self.offset_within_chunk.unwrap_or(0);
817 Ok(parent_chunk_base + parent_within + slice_start_idx - new_chunk_base)
818 })
819 .transpose()?;
820
821 Ok(Some(Self {
822 array_len: range.len(),
823 offset: range.start + self.offset(),
824 indices,
825 values,
826 chunk_offsets: new_chunk_offsets,
827 offset_within_chunk,
828 }))
829 }
830
831 const PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN: f64 = 5.0;
833
834 fn is_map_faster_than_search(&self, take_indices: &PrimitiveArray) -> bool {
835 (self.num_patches() as f64 / take_indices.len() as f64)
836 < Self::PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN
837 }
838
839 pub fn take_with_nulls(
843 &self,
844 take_indices: &ArrayRef,
845 ctx: &mut ExecutionCtx,
846 ) -> VortexResult<Option<Self>> {
847 if take_indices.is_empty() {
848 return Ok(None);
849 }
850
851 let take_indices = take_indices.clone().execute::<PrimitiveArray>(ctx)?;
852 if self.is_map_faster_than_search(&take_indices) {
853 self.take_map(take_indices, true, ctx)
854 } else {
855 self.take_search(take_indices, true, ctx)
856 }
857 }
858
859 pub fn take(
863 &self,
864 take_indices: &ArrayRef,
865 ctx: &mut ExecutionCtx,
866 ) -> VortexResult<Option<Self>> {
867 if take_indices.is_empty() {
868 return Ok(None);
869 }
870
871 let take_indices = take_indices.clone().execute::<PrimitiveArray>(ctx)?;
872 if self.is_map_faster_than_search(&take_indices) {
873 self.take_map(take_indices, false, ctx)
874 } else {
875 self.take_search(take_indices, false, ctx)
876 }
877 }
878
879 #[expect(
880 clippy::cognitive_complexity,
881 reason = "complexity is from nested match_each_* macros"
882 )]
883 pub fn take_search(
884 &self,
885 take_indices: PrimitiveArray,
886 include_nulls: bool,
887 ctx: &mut ExecutionCtx,
888 ) -> VortexResult<Option<Self>> {
889 let take_indices_validity = take_indices.validity()?;
890 let take_indices_unsigned =
893 take_indices.reinterpret_cast(take_indices.ptype().to_unsigned());
894 let patch_indices = self.indices.clone().execute::<PrimitiveArray>(ctx)?;
895 let chunk_offsets = self
896 .chunk_offsets()
897 .as_ref()
898 .map(|co| co.clone().execute::<PrimitiveArray>(ctx))
899 .transpose()?;
900
901 let (values_indices, new_indices): (BufferMut<u64>, BufferMut<u64>) =
902 match_each_unsigned_integer_ptype!(patch_indices.ptype(), |PatchT| {
903 let patch_indices_slice = patch_indices.as_slice::<PatchT>();
904 match_each_unsigned_integer_ptype!(take_indices_unsigned.ptype(), |TakeT| {
905 let take_slice = take_indices_unsigned.as_slice::<TakeT>();
906
907 if let Some(chunk_offsets) = chunk_offsets {
908 match_each_unsigned_integer_ptype!(chunk_offsets.ptype(), |OffsetT| {
909 let chunk_offsets = chunk_offsets.as_slice::<OffsetT>();
910 take_indices_with_search_fn(
911 patch_indices_slice,
912 take_slice,
913 take_indices
914 .as_ref()
915 .validity()?
916 .execute_mask(take_indices.as_ref().len(), ctx)?,
917 include_nulls,
918 ctx.allocator(),
919 |take_idx| {
920 self.search_index_chunked_batch(
921 patch_indices_slice,
922 chunk_offsets,
923 take_idx,
924 )
925 },
926 )?
927 })
928 } else {
929 take_indices_with_search_fn(
930 patch_indices_slice,
931 take_slice,
932 take_indices
933 .as_ref()
934 .validity()?
935 .execute_mask(take_indices.as_ref().len(), ctx)?,
936 include_nulls,
937 ctx.allocator(),
938 |take_idx| {
939 let Some(offset) = <PatchT as NumCast>::from(self.offset) else {
940 return Ok(SearchResult::NotFound(patch_indices_slice.len()));
942 };
943
944 patch_indices_slice
945 .search_sorted(&(take_idx + offset), SearchSortedSide::Left)
946 },
947 )?
948 }
949 })
950 });
951
952 if new_indices.is_empty() {
953 return Ok(None);
954 }
955
956 let new_indices = new_indices.into_array();
957 let new_array_len = take_indices.len();
958 let values_validity = take_indices_validity.take(&new_indices)?;
959
960 Ok(Some(Self {
961 array_len: new_array_len,
962 offset: 0,
963 indices: new_indices,
964 values: self
965 .values()
966 .take(PrimitiveArray::new(values_indices, values_validity).into_array())?,
967 chunk_offsets: None,
968 offset_within_chunk: Some(0), }))
970 }
971
972 pub fn take_map(
973 &self,
974 take_indices: PrimitiveArray,
975 include_nulls: bool,
976 ctx: &mut ExecutionCtx,
977 ) -> VortexResult<Option<Self>> {
978 let indices = self.indices.clone().execute::<PrimitiveArray>(ctx)?;
979 let new_length = take_indices.len();
980 let take_indices_unsigned =
982 take_indices.reinterpret_cast(take_indices.ptype().to_unsigned());
983
984 let min_index = self.min_index(ctx)?;
985 let max_index = self.max_index(ctx)?;
986
987 let Some((new_sparse_indices, value_indices)) =
988 match_each_unsigned_integer_ptype!(indices.ptype(), |Indices| {
989 match_each_unsigned_integer_ptype!(take_indices_unsigned.ptype(), |TakeIndices| {
990 let take_validity = take_indices
991 .validity()?
992 .execute_mask(take_indices.len(), ctx)?;
993 let take_nullability = take_indices.validity()?.nullability();
994 let take_slice = take_indices_unsigned.as_slice::<TakeIndices>();
995 take_map::<_, TakeIndices>(
996 indices.as_slice::<Indices>(),
997 take_slice,
998 take_validity,
999 take_nullability,
1000 self.offset(),
1001 min_index,
1002 max_index,
1003 include_nulls,
1004 ctx.allocator(),
1005 )?
1006 })
1007 })
1008 else {
1009 return Ok(None);
1010 };
1011
1012 let taken_values = self.values().take(value_indices)?;
1013
1014 Ok(Some(Patches {
1015 array_len: new_length,
1016 offset: 0,
1017 indices: new_sparse_indices,
1018 values: taken_values,
1019 chunk_offsets: None,
1021 offset_within_chunk: self.offset_within_chunk,
1022 }))
1023 }
1024
1025 pub fn map_values<F>(self, f: F) -> VortexResult<Self>
1026 where
1027 F: FnOnce(ArrayRef) -> VortexResult<ArrayRef>,
1028 {
1029 let values = f(self.values)?;
1030 if self.indices.len() != values.len() {
1031 vortex_bail!(
1032 "map_values must preserve length: expected {} received {}",
1033 self.indices.len(),
1034 values.len()
1035 )
1036 }
1037
1038 Ok(Self {
1039 array_len: self.array_len,
1040 offset: self.offset,
1041 indices: self.indices,
1042 values,
1043 chunk_offsets: self.chunk_offsets,
1044 offset_within_chunk: self.offset_within_chunk,
1045 })
1046 }
1047}
1048
1049fn search_index_binary_search(
1055 indices: &ArrayRef,
1056 needle: usize,
1057 ctx: &mut ExecutionCtx,
1058) -> VortexResult<SearchResult> {
1059 if let Some(primitive) = indices.as_opt::<Primitive>() {
1060 match_each_unsigned_integer_ptype!(primitive.ptype(), |T| {
1061 let Ok(needle) = T::try_from(needle) else {
1062 return Ok(SearchResult::NotFound(primitive.len()));
1067 };
1068 return primitive
1069 .as_slice::<T>()
1070 .search_sorted(&needle, SearchSortedSide::Left);
1071 });
1072 }
1073
1074 search_index_binary_search_scalar(indices, needle, ctx)
1075}
1076
1077fn search_index_binary_search_scalar(
1078 indices: &ArrayRef,
1079 needle: usize,
1080 ctx: &mut ExecutionCtx,
1081) -> VortexResult<SearchResult> {
1082 match_each_unsigned_integer_ptype!(indices.dtype().as_ptype(), |T| {
1083 SearchSortedPrimitiveArray::<T>::new(indices, ctx)
1084 .search_sorted(&needle, SearchSortedSide::Left)
1085 })
1086}
1087
1088#[expect(clippy::too_many_arguments)] fn take_map<I: NativePType + Hash + Eq + TryFrom<usize>, T: NativePType>(
1090 indices: &[I],
1091 take_indices: &[T],
1092 take_validity: Mask,
1093 take_nullability: Nullability,
1094 indices_offset: usize,
1095 min_index: usize,
1096 max_index: usize,
1097 include_nulls: bool,
1098 allocator: &BufferAllocatorRef,
1099) -> VortexResult<Option<(ArrayRef, ArrayRef)>>
1100where
1101 usize: TryFrom<T>,
1102 VortexError: From<<I as TryFrom<usize>>::Error>,
1103{
1104 let offset_i = I::try_from(indices_offset)?;
1105
1106 let sparse_index_to_value_index: HashMap<I, usize> = indices
1107 .iter()
1108 .copied()
1109 .map(|idx| idx - offset_i)
1110 .enumerate()
1111 .map(|(value_index, sparse_index)| (sparse_index, value_index))
1112 .collect();
1113
1114 let mut new_sparse_indices =
1115 BufferMut::<u64>::with_capacity_in(take_indices.len(), allocator.clone());
1116 let mut value_indices =
1117 BufferMut::<u64>::with_capacity_in(take_indices.len(), allocator.clone());
1118
1119 for (idx_in_take, &take_idx) in take_indices.iter().enumerate() {
1120 let ti = usize::try_from(take_idx)
1121 .map_err(|_| vortex_err!("Failed to convert index to usize"))?;
1122
1123 let is_null = match take_validity.bit_buffer() {
1125 AllOr::All => false,
1126 AllOr::None => true,
1127 AllOr::Some(buf) => !buf.value(idx_in_take),
1128 };
1129 if is_null {
1130 if include_nulls {
1131 new_sparse_indices.push(idx_in_take as u64);
1132 value_indices.push(0);
1133 }
1134 } else if ti >= min_index && ti <= max_index {
1135 let ti_as_i = I::try_from(ti)
1136 .map_err(|_| vortex_err!("take index does not fit in index type"))?;
1137 if let Some(&value_index) = sparse_index_to_value_index.get(&ti_as_i) {
1138 new_sparse_indices.push(idx_in_take as u64);
1139 value_indices.push(value_index as u64);
1140 }
1141 }
1142 }
1143
1144 if new_sparse_indices.is_empty() {
1145 return Ok(None);
1146 }
1147
1148 let new_sparse_indices = new_sparse_indices.into_array();
1149 let values_validity =
1150 Validity::from_mask(take_validity, take_nullability).take(&new_sparse_indices)?;
1151 Ok(Some((
1152 new_sparse_indices,
1153 PrimitiveArray::new(value_indices, values_validity).into_array(),
1154 )))
1155}
1156
1157fn filter_patches_with_mask<T: IntegerPType>(
1170 patch_indices: &[T],
1171 offset: usize,
1172 patch_values: &ArrayRef,
1173 mask: &MaskValues,
1174 allocator: &BufferAllocatorRef,
1175) -> VortexResult<Option<Patches>> {
1176 let true_count = mask.true_count();
1177 let patch_count = patch_indices.len();
1178 let expected_matches = true_count.min(patch_count);
1179
1180 let mut new_patch_indices =
1182 BufferMut::<u64>::with_capacity_in(expected_matches, allocator.clone());
1183 let mut kept_patches = BitBufferMut::from_buffer(
1184 BufferMut::zeroed_in(patch_count.div_ceil(8), allocator.clone()),
1185 0,
1186 patch_count,
1187 );
1188
1189 if patch_count > true_count {
1190 gallop_patches_for_mask_indices(
1191 patch_indices,
1192 offset,
1193 mask,
1194 &mut new_patch_indices,
1195 &mut kept_patches,
1196 )?;
1197 } else {
1198 match mask.cached_indices() {
1199 Some(mask_indices) => gallop_mask_indices_for_patches(
1200 patch_indices,
1201 offset,
1202 mask_indices,
1203 &mut new_patch_indices,
1204 &mut kept_patches,
1205 )?,
1206 None => rank_patches_in_mask_bitmap(
1207 patch_indices,
1208 offset,
1209 mask.bit_buffer(),
1210 &mut new_patch_indices,
1211 &mut kept_patches,
1212 )?,
1213 }
1214 }
1215
1216 let new_patch_values = match new_patch_indices.len() {
1217 0 => return Ok(None),
1218 kept if kept == patch_count => patch_values.clone(),
1219 _ => patch_values.filter(Mask::from_buffer(kept_patches.freeze()))?,
1220 };
1221 let new_patch_indices = new_patch_indices.into_array();
1222
1223 Ok(Some(unsafe {
1226 Patches::new_unchecked(
1227 true_count,
1228 0,
1229 new_patch_indices,
1230 new_patch_values,
1231 None,
1233 None,
1234 )
1235 }))
1236}
1237
1238fn gallop_lower_bound<T: Ord>(values: &[T], start: usize, needle: &T) -> usize {
1242 let mut low = start;
1243 let mut high = start;
1244 let mut step = 1;
1245
1246 while high < values.len() && values[high] < *needle {
1247 low = high + 1;
1248 high += step;
1249 step *= 2;
1250 }
1251
1252 let high = high.min(values.len());
1253 low + values[low..high].partition_point(|value| value < needle)
1254}
1255
1256fn gallop_patches_for_mask_indices<T: IntegerPType>(
1260 patch_indices: &[T],
1261 offset: usize,
1262 mask: &MaskValues,
1263 new_patch_indices: &mut BufferMut<u64>,
1264 kept_patches: &mut BitBufferMut,
1265) -> VortexResult<()> {
1266 let Some(&last_patch_index) = patch_indices.last() else {
1267 return Ok(());
1268 };
1269 let last_mask_index = patch_index_to_usize(last_patch_index, offset)?;
1270
1271 let mut patch_position = 0;
1272 let mut mask_position = 0;
1273
1274 let mut visit = |mask_index: usize| {
1275 let needle = <T as NumCast>::from(mask_index + offset)
1277 .vortex_expect("mask index is at most the last patch index");
1278
1279 patch_position = gallop_lower_bound(patch_indices, patch_position, &needle);
1280 if patch_indices[patch_position] == needle {
1281 new_patch_indices.push(mask_position as u64);
1282 kept_patches.set(patch_position);
1283 patch_position += 1;
1284 }
1285
1286 mask_position += 1;
1287 };
1288
1289 match mask.cached_indices() {
1290 Some(mask_indices) => {
1291 let end = mask_indices.partition_point(|&mask_index| mask_index <= last_mask_index);
1292 mask_indices[..end]
1293 .iter()
1294 .for_each(|&mask_index| visit(mask_index));
1295 }
1296 None => mask
1297 .bit_buffer()
1298 .slice(..=last_mask_index)
1299 .for_each_set_index(visit),
1300 }
1301
1302 Ok(())
1303}
1304
1305fn gallop_mask_indices_for_patches<T: IntegerPType>(
1307 patch_indices: &[T],
1308 offset: usize,
1309 mask_indices: &[usize],
1310 new_patch_indices: &mut BufferMut<u64>,
1311 kept_patches: &mut BitBufferMut,
1312) -> VortexResult<()> {
1313 let mut mask_position = 0;
1314
1315 for (patch_position, patch_index) in patch_indices.iter().enumerate() {
1316 let index = patch_index_to_usize(*patch_index, offset)?;
1317
1318 mask_position = gallop_lower_bound(mask_indices, mask_position, &index);
1319 if mask_position == mask_indices.len() {
1320 break;
1321 }
1322
1323 if mask_indices[mask_position] == index {
1324 new_patch_indices.push(mask_position as u64);
1325 kept_patches.set(patch_position);
1326 mask_position += 1;
1327 }
1328 }
1329
1330 Ok(())
1331}
1332
1333fn rank_patches_in_mask_bitmap<T: IntegerPType>(
1337 patch_indices: &[T],
1338 offset: usize,
1339 mask: &BitBuffer,
1340 new_patch_indices: &mut BufferMut<u64>,
1341 kept_patches: &mut BitBufferMut,
1342) -> VortexResult<()> {
1343 let mut rank = 0;
1344 let mut previous_index = 0;
1345
1346 for (patch_position, patch_index) in patch_indices.iter().enumerate() {
1347 let index = patch_index_to_usize(*patch_index, offset)?;
1348
1349 rank += mask.count_range(previous_index, index);
1350 previous_index = index;
1351
1352 if mask.value(index) {
1353 new_patch_indices.push(rank as u64);
1354 kept_patches.set(patch_position);
1355 }
1356 }
1357
1358 Ok(())
1359}
1360
1361#[inline]
1362fn patch_index_to_usize<T: IntegerPType>(patch_index: T, offset: usize) -> VortexResult<usize> {
1363 Ok(patch_index
1364 .to_usize()
1365 .ok_or_else(|| vortex_err!("patch index does not fit in usize"))?
1366 - offset)
1367}
1368
1369fn take_indices_with_search_fn<
1370 I: UnsignedPType,
1371 T: IntegerPType,
1372 F: Fn(I) -> VortexResult<SearchResult>,
1373>(
1374 indices: &[I],
1375 take_indices: &[T],
1376 take_validity: Mask,
1377 include_nulls: bool,
1378 allocator: &BufferAllocatorRef,
1379 search_fn: F,
1380) -> VortexResult<(BufferMut<u64>, BufferMut<u64>)> {
1381 let mut values_indices = BufferMut::with_capacity_in(take_indices.len(), allocator.clone());
1382 let mut new_indices = BufferMut::with_capacity_in(take_indices.len(), allocator.clone());
1383
1384 for (new_patch_idx, &take_idx) in take_indices.iter().enumerate() {
1385 if !take_validity.value(new_patch_idx) {
1386 if include_nulls {
1387 values_indices.push(0u64);
1389 new_indices.push(new_patch_idx as u64);
1390 }
1391 continue;
1392 } else {
1393 let search_result = match I::from(take_idx) {
1394 Some(idx) => search_fn(idx)?,
1395 None => SearchResult::NotFound(indices.len()),
1396 };
1397
1398 if let Some(patch_idx) = search_result.to_found() {
1399 values_indices.push(patch_idx as u64);
1400 new_indices.push(new_patch_idx as u64);
1401 }
1402 }
1403 }
1404
1405 Ok((values_indices, new_indices))
1406}
1407
1408#[cfg(test)]
1409mod test {
1410 use std::ops::Range;
1411 use std::sync::LazyLock;
1412
1413 use rstest::rstest;
1414 use vortex_buffer::BitBuffer;
1415 use vortex_buffer::Buffer;
1416 use vortex_buffer::BufferMut;
1417 use vortex_buffer::buffer;
1418 use vortex_error::VortexExpect;
1419 use vortex_error::VortexResult;
1420 use vortex_mask::Mask;
1421 use vortex_session::VortexSession;
1422
1423 use crate::IntoArray;
1424 use crate::VortexSessionExecute;
1425 use crate::assert_arrays_eq;
1426 use crate::dtype::PType;
1427 use crate::patches::Patches;
1428 use crate::patches::PatchesMetadata;
1429 use crate::patches::PrimitiveArray;
1430 use crate::search_sorted::SearchResult;
1431 use crate::validity::Validity;
1432
1433 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
1434
1435 #[rstest]
1436 #[case::unchunked(false)]
1437 #[case::chunked(true)]
1438 fn test_from_metadata_without_offset_within_chunk(#[case] chunked: bool) -> VortexResult<()> {
1439 let mut ctx = SESSION.create_execution_ctx();
1440 let metadata = PatchesMetadata::new(
1441 3,
1442 0,
1443 PType::U32,
1444 chunked.then_some(3),
1445 chunked.then_some(PType::U32),
1446 None,
1447 );
1448 let patches = Patches::from_metadata(
1449 3072,
1450 &metadata,
1451 buffer![7u32, 1029, 2051].into_array(),
1452 buffer![11i32, 22, 33].into_array(),
1453 chunked.then(|| buffer![0u32, 1, 2].into_array()),
1454 &mut ctx,
1455 )?;
1456
1457 assert_eq!(patches.offset_within_chunk(), chunked.then_some(0));
1458 assert_eq!(
1459 patches.search_index(1029, &mut ctx)?,
1460 SearchResult::Found(1)
1461 );
1462 Ok(())
1463 }
1464
1465 #[rstest]
1466 fn test_from_metadata_rejects_inconsistent_chunk_offset(
1467 #[values(0, 2, 3, 501, usize::MAX)] offset_within_chunk: usize,
1468 ) {
1469 let mut ctx = SESSION.create_execution_ctx();
1470 let metadata = PatchesMetadata::new(
1472 2,
1473 500,
1474 PType::U32,
1475 Some(2),
1476 Some(PType::U32),
1477 Some(offset_within_chunk),
1478 );
1479 let error = Patches::from_metadata(
1480 1000,
1481 &metadata,
1482 buffer![500u32, 1200].into_array(),
1483 buffer![11i32, 22].into_array(),
1484 Some(buffer![0u32, 2].into_array()),
1485 &mut ctx,
1486 )
1487 .expect_err("inconsistent patch offset must be rejected");
1488 assert!(error.to_string().contains("Patch offset within chunk"));
1489 }
1490
1491 #[rstest]
1492 #[case::single_chunk(900..901)]
1493 #[case::later_single_chunk(1500..1501)]
1494 #[case::multiple_chunks(900..2050)]
1495 fn test_from_metadata_short_slice(#[case] range: Range<usize>) -> VortexResult<()> {
1496 let mut ctx = SESSION.create_execution_ctx();
1497 let indices = PrimitiveArray::from_iter(0u32..3072).into_array();
1498 let patches = Patches::new(
1499 3072,
1500 0,
1501 indices.clone(),
1502 indices,
1503 Some(buffer![0u32, 1024, 2048].into_array()),
1504 &mut ctx,
1505 )?;
1506 let sliced = patches.slice(range, &mut ctx)?.expect("slice has patches");
1507 let metadata = sliced.to_metadata(sliced.array_len(), sliced.dtype())?;
1508 let read = Patches::from_metadata(
1509 sliced.array_len(),
1510 &metadata,
1511 sliced.indices().clone(),
1512 sliced.values().clone(),
1513 sliced.chunk_offsets().clone(),
1514 &mut ctx,
1515 )?;
1516
1517 assert_eq!(read.offset_within_chunk(), sliced.offset_within_chunk());
1518 assert_eq!(read.search_index(0, &mut ctx)?, SearchResult::Found(0));
1519 assert_arrays_eq!(read.values(), sliced.values(), &mut ctx);
1520 Ok(())
1521 }
1522
1523 #[cfg(debug_assertions)]
1524 #[test]
1525 #[should_panic(expected = "Patch indices must be strictly increasing")]
1526 fn test_new_rejects_repeated_indices() {
1527 let mut ctx = SESSION.create_execution_ctx();
1528 Patches::new(
1529 5,
1530 0,
1531 buffer![1u32, 1].into_array(),
1532 buffer![10i32, 20].into_array(),
1533 None,
1534 &mut ctx,
1535 )
1536 .unwrap();
1537 }
1538
1539 #[test]
1540 fn test_filter() {
1541 let mut ctx = SESSION.create_execution_ctx();
1542 let patches = Patches::new(
1543 100,
1544 0,
1545 buffer![10u32, 11, 20].into_array(),
1546 buffer![100, 110, 200].into_array(),
1547 None,
1548 &mut ctx,
1549 )
1550 .unwrap();
1551
1552 let filtered = patches
1553 .filter(&Mask::from_indices(100, vec![10, 20, 30]), &mut ctx)
1554 .unwrap()
1555 .unwrap();
1556
1557 assert_arrays_eq!(
1558 filtered.indices(),
1559 PrimitiveArray::from_iter([0u64, 1]),
1560 &mut ctx
1561 );
1562 assert_arrays_eq!(
1563 filtered.values(),
1564 PrimitiveArray::from_iter([100i32, 200]),
1565 &mut ctx
1566 );
1567 }
1568
1569 #[test]
1570 fn take_with_nulls() {
1571 let mut ctx = SESSION.create_execution_ctx();
1572 let patches = Patches::new(
1573 20,
1574 0,
1575 buffer![2u64, 9, 15].into_array(),
1576 PrimitiveArray::new(buffer![33_i32, 44, 55], Validity::AllValid).into_array(),
1577 None,
1578 &mut ctx,
1579 )
1580 .unwrap();
1581
1582 let taken = patches
1583 .take(
1584 &PrimitiveArray::new(buffer![9, 0], Validity::from_iter(vec![true, false]))
1585 .into_array(),
1586 &mut ctx,
1587 )
1588 .unwrap()
1589 .unwrap();
1590 let values = taken.values();
1591 let primitive_indices = taken.indices();
1592 assert_eq!(taken.array_len(), 2);
1593 assert_arrays_eq!(
1594 values,
1595 PrimitiveArray::from_option_iter([Some(44i32)]),
1596 &mut ctx
1597 );
1598 assert_arrays_eq!(
1599 primitive_indices,
1600 PrimitiveArray::from_iter([0u64]),
1601 &mut ctx
1602 );
1603 assert_eq!(
1604 values
1605 .validity()
1606 .unwrap()
1607 .execute_mask(values.len(), &mut ctx)
1608 .unwrap(),
1609 Mask::from_iter(vec![true])
1610 );
1611 }
1612
1613 #[test]
1614 fn take_search_with_nulls_chunked() {
1615 let mut ctx = SESSION.create_execution_ctx();
1616 let patches = Patches::new(
1617 20,
1618 0,
1619 buffer![2u64, 9, 15].into_array(),
1620 buffer![33_i32, 44, 55].into_array(),
1621 Some(buffer![0u64].into_array()),
1622 &mut ctx,
1623 )
1624 .unwrap();
1625
1626 let taken = patches
1627 .take_search(
1628 PrimitiveArray::new(buffer![9, 0], Validity::from_iter([true, false])),
1629 true,
1630 &mut ctx,
1631 )
1632 .unwrap()
1633 .unwrap();
1634
1635 let values = taken.values();
1636 assert_eq!(taken.array_len(), 2);
1637 assert_arrays_eq!(
1638 values,
1639 PrimitiveArray::from_option_iter([Some(44i32), None]),
1640 &mut ctx
1641 );
1642 assert_arrays_eq!(
1643 taken.indices(),
1644 PrimitiveArray::from_iter([0u64, 1]),
1645 &mut ctx
1646 );
1647
1648 assert_eq!(
1649 values
1650 .validity()
1651 .unwrap()
1652 .execute_mask(values.len(), &mut ctx)
1653 .unwrap(),
1654 Mask::from_iter([true, false])
1655 );
1656 }
1657
1658 #[test]
1659 fn take_search_chunked_multiple_chunks() {
1660 let mut ctx = SESSION.create_execution_ctx();
1661 let patches = Patches::new(
1662 2048,
1663 0,
1664 buffer![100u64, 500, 1200, 1800].into_array(),
1665 buffer![10_i32, 20, 30, 40].into_array(),
1666 Some(buffer![0u64, 2].into_array()),
1667 &mut ctx,
1668 )
1669 .unwrap();
1670
1671 let taken = patches
1672 .take_search(
1673 PrimitiveArray::new(buffer![500, 1200, 999], Validity::AllValid),
1674 true,
1675 &mut ctx,
1676 )
1677 .unwrap()
1678 .unwrap();
1679
1680 assert_eq!(taken.array_len(), 3);
1681 assert_arrays_eq!(
1682 taken.values(),
1683 PrimitiveArray::from_option_iter([Some(20i32), Some(30)]),
1684 &mut ctx
1685 );
1686 assert_arrays_eq!(
1687 taken.indices(),
1688 PrimitiveArray::from_iter([0u64, 1]),
1689 &mut ctx
1690 );
1691 }
1692
1693 #[test]
1694 fn take_search_chunked_indices_with_no_patches() {
1695 let mut ctx = SESSION.create_execution_ctx();
1696 let patches = Patches::new(
1697 20,
1698 0,
1699 buffer![2u64, 9, 15].into_array(),
1700 buffer![33_i32, 44, 55].into_array(),
1701 Some(buffer![0u64].into_array()),
1702 &mut ctx,
1703 )
1704 .unwrap();
1705
1706 let taken = patches
1707 .take_search(
1708 PrimitiveArray::new(buffer![3, 4, 5], Validity::AllValid),
1709 true,
1710 &mut ctx,
1711 )
1712 .unwrap();
1713
1714 assert!(taken.is_none());
1715 }
1716
1717 #[test]
1718 fn take_search_chunked_interleaved() {
1719 let mut ctx = SESSION.create_execution_ctx();
1720 let patches = Patches::new(
1721 30,
1722 0,
1723 buffer![5u64, 10, 20, 25].into_array(),
1724 buffer![100_i32, 200, 300, 400].into_array(),
1725 Some(buffer![0u64].into_array()),
1726 &mut ctx,
1727 )
1728 .unwrap();
1729
1730 let taken = patches
1731 .take_search(
1732 PrimitiveArray::new(buffer![10, 15, 20, 99], Validity::AllValid),
1733 true,
1734 &mut ctx,
1735 )
1736 .unwrap()
1737 .unwrap();
1738
1739 assert_eq!(taken.array_len(), 4);
1740 assert_arrays_eq!(
1741 taken.values(),
1742 PrimitiveArray::from_option_iter([Some(200i32), Some(300)]),
1743 &mut ctx
1744 );
1745 assert_arrays_eq!(
1746 taken.indices(),
1747 PrimitiveArray::from_iter([0u64, 2]),
1748 &mut ctx
1749 );
1750 }
1751
1752 #[test]
1753 fn test_take_search_multiple_chunk_offsets() {
1754 let mut ctx = SESSION.create_execution_ctx();
1755 let patches = Patches::new(
1756 1500,
1757 0,
1758 BufferMut::from_iter(0..1500u64).into_array(),
1759 BufferMut::from_iter(0..1500i32).into_array(),
1760 Some(buffer![0u64, 1024u64].into_array()),
1761 &mut ctx,
1762 )
1763 .unwrap();
1764
1765 let taken = patches
1766 .take_search(
1767 PrimitiveArray::new(BufferMut::from_iter(0..1500u64), Validity::AllValid),
1768 false,
1769 &mut ctx,
1770 )
1771 .unwrap()
1772 .unwrap();
1773
1774 assert_eq!(taken.array_len(), 1500);
1775 assert_arrays_eq!(
1776 taken.indices(),
1777 PrimitiveArray::from_iter(0..1500u64),
1778 &mut ctx
1779 );
1780 assert_arrays_eq!(
1781 taken.values(),
1782 PrimitiveArray::from_option_iter((0..1500i32).map(Some)),
1783 &mut ctx
1784 );
1785 }
1786
1787 #[test]
1788 fn doubly_sliced() {
1789 let mut ctx = SESSION.create_execution_ctx();
1790 let values = buffer![15_u32, 135, 13531, 42].into_array();
1791 let indices = buffer![10_u64, 11, 50, 100].into_array();
1792
1793 let patches = Patches::new(101, 0, indices, values, None, &mut ctx).unwrap();
1794
1795 let sliced = patches.slice(15..100, &mut ctx).unwrap().unwrap();
1796 assert_eq!(sliced.array_len(), 100 - 15);
1797 assert_arrays_eq!(
1798 sliced.values(),
1799 PrimitiveArray::from_iter([13531u32]),
1800 &mut ctx
1801 );
1802
1803 assert_eq!(sliced.offset(), 15);
1804 assert_arrays_eq!(
1805 sliced.indices(),
1806 PrimitiveArray::from_iter([50u64]),
1807 &mut ctx
1808 );
1809 let doubly_sliced = sliced.slice(35..36, &mut ctx).unwrap().unwrap();
1810 assert_eq!(doubly_sliced.array_len(), 1);
1811 assert_eq!(doubly_sliced.offset(), 50);
1812 assert_eq!(
1813 doubly_sliced.search_index(0, &mut ctx).unwrap(),
1814 SearchResult::Found(0)
1815 );
1816 assert_arrays_eq!(
1817 doubly_sliced.values(),
1818 PrimitiveArray::from_iter([13531u32]),
1819 &mut ctx
1820 );
1821 }
1822
1823 #[test]
1824 fn test_mask_all_true() {
1825 let mut ctx = SESSION.create_execution_ctx();
1826 let patches = Patches::new(
1827 10,
1828 0,
1829 buffer![2u64, 5, 8].into_array(),
1830 buffer![100i32, 200, 300].into_array(),
1831 None,
1832 &mut ctx,
1833 )
1834 .unwrap();
1835
1836 let mask = Mask::new_true(10);
1837 let masked = patches.mask(&mask, &mut ctx).unwrap();
1838 assert!(masked.is_none());
1839 }
1840
1841 #[test]
1842 fn test_mask_all_false() {
1843 let mut ctx = SESSION.create_execution_ctx();
1844 let patches = Patches::new(
1845 10,
1846 0,
1847 buffer![2u64, 5, 8].into_array(),
1848 buffer![100i32, 200, 300].into_array(),
1849 None,
1850 &mut ctx,
1851 )
1852 .unwrap();
1853
1854 let mask = Mask::new_false(10);
1855 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1856
1857 assert!(masked.values().dtype().is_nullable());
1859 assert_arrays_eq!(
1860 masked.values(),
1861 PrimitiveArray::from_option_iter([Some(100i32), Some(200), Some(300)]),
1862 &mut ctx
1863 );
1864 assert!(masked.values().is_valid(0, &mut ctx).unwrap());
1865 assert!(masked.values().is_valid(1, &mut ctx).unwrap());
1866 assert!(masked.values().is_valid(2, &mut ctx).unwrap());
1867
1868 assert_arrays_eq!(
1870 masked.indices(),
1871 PrimitiveArray::from_iter([2u64, 5, 8]),
1872 &mut ctx
1873 );
1874 }
1875
1876 #[test]
1877 fn test_mask_partial() {
1878 let mut ctx = SESSION.create_execution_ctx();
1879 let patches = Patches::new(
1880 10,
1881 0,
1882 buffer![2u64, 5, 8].into_array(),
1883 buffer![100i32, 200, 300].into_array(),
1884 None,
1885 &mut ctx,
1886 )
1887 .unwrap();
1888
1889 let mask = Mask::from_iter([
1891 false, false, true, false, false, false, false, false, true, false,
1892 ]);
1893 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1894
1895 assert_eq!(masked.values().len(), 1);
1897 assert_arrays_eq!(
1898 masked.values(),
1899 PrimitiveArray::from_option_iter([Some(200i32)]),
1900 &mut ctx
1901 );
1902
1903 assert_arrays_eq!(
1905 masked.indices(),
1906 PrimitiveArray::from_iter([5u64]),
1907 &mut ctx
1908 );
1909 }
1910
1911 #[test]
1912 fn test_mask_with_offset() {
1913 let mut ctx = SESSION.create_execution_ctx();
1914 let patches = Patches::new(
1915 10,
1916 5, buffer![7u64, 10, 13].into_array(), buffer![100i32, 200, 300].into_array(),
1919 None,
1920 &mut ctx,
1921 )
1922 .unwrap();
1923
1924 let mask = Mask::from_iter([
1926 false, false, true, false, false, false, false, false, false, false,
1927 ]);
1928
1929 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1930 assert_eq!(masked.array_len(), 10);
1931 assert_eq!(masked.offset(), 5);
1932 assert_arrays_eq!(
1933 masked.indices(),
1934 PrimitiveArray::from_iter([10u64, 13]),
1935 &mut ctx
1936 );
1937 assert_arrays_eq!(
1938 masked.values(),
1939 PrimitiveArray::from_option_iter([Some(200i32), Some(300)]),
1940 &mut ctx
1941 );
1942 }
1943
1944 #[test]
1945 fn test_mask_nullable_values() {
1946 let mut ctx = SESSION.create_execution_ctx();
1947 let patches = Patches::new(
1948 10,
1949 0,
1950 buffer![2u64, 5, 8].into_array(),
1951 PrimitiveArray::from_option_iter([Some(100i32), None, Some(300)]).into_array(),
1952 None,
1953 &mut ctx,
1954 )
1955 .unwrap();
1956
1957 let mask = Mask::from_iter([
1959 false, false, true, false, false, false, false, false, false, false,
1960 ]);
1961 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1962
1963 assert_arrays_eq!(
1965 masked.indices(),
1966 PrimitiveArray::from_iter([5u64, 8]),
1967 &mut ctx
1968 );
1969
1970 let masked_values = masked
1972 .values()
1973 .clone()
1974 .execute::<PrimitiveArray>(&mut ctx)
1975 .unwrap();
1976 assert_eq!(masked_values.len(), 2);
1977 assert!(!masked_values.is_valid(0, &mut ctx).unwrap()); assert!(masked_values.is_valid(1, &mut ctx).unwrap()); assert_eq!(
1980 i32::try_from(&masked_values.execute_scalar(1, &mut ctx).unwrap()).unwrap(),
1981 300i32
1982 );
1983 }
1984
1985 #[rstest]
1987 #[case::sparse_mask((0..1000).step_by(2).collect(), (0..1000).step_by(97).collect())]
1988 #[case::sparse_patches((0..1000).step_by(97).collect(), (0..1000).step_by(2).collect())]
1989 #[case::similar_sizes((0..1000).step_by(3).collect(), (0..1000).step_by(2).collect())]
1990 #[case::no_overlap((0..500).collect(), (500..1000).step_by(50).collect())]
1991 #[case::no_overlap_sparse_patches((500..1000).step_by(100).collect(), (0..500).collect())]
1992 #[case::edges(vec![0, 1, 998, 999], vec![0, 999])]
1993 #[case::all_patches_kept((0..1000).step_by(100).collect(), (0..1000).step_by(2).collect())]
1994 fn test_filter_matches_naive(
1995 #[case] patch_indices: Vec<usize>,
1996 #[case] mask_indices: Vec<usize>,
1997 #[values(0, 5)] offset: usize,
1998 #[values(true, false)] cache_mask_indices: bool,
1999 ) -> VortexResult<()> {
2000 const LEN: usize = 1000;
2001 let mut ctx = SESSION.create_execution_ctx();
2002
2003 let patches = Patches::new(
2004 LEN,
2005 offset,
2006 patch_indices
2007 .iter()
2008 .map(|&index| u32::try_from(index + offset).vortex_expect("index fits in u32"))
2009 .collect::<Buffer<u32>>()
2010 .into_array(),
2011 (0i32..)
2012 .take(patch_indices.len())
2013 .collect::<Buffer<i32>>()
2014 .into_array(),
2015 None,
2016 &mut ctx,
2017 )?;
2018
2019 let mask = if cache_mask_indices {
2020 Mask::from_indices(LEN, mask_indices.iter().copied())
2021 } else {
2022 Mask::from_buffer(BitBuffer::from_iter(
2023 (0..LEN).map(|index| mask_indices.binary_search(&index).is_ok()),
2024 ))
2025 };
2026
2027 let (expected_indices, expected_values): (Vec<u64>, Vec<i32>) = mask_indices
2028 .iter()
2029 .enumerate()
2030 .filter_map(|(mask_position, index)| {
2031 patch_indices
2032 .binary_search(index)
2033 .ok()
2034 .map(|patch_position| {
2035 (
2036 mask_position as u64,
2037 i32::try_from(patch_position).vortex_expect("position fits in i32"),
2038 )
2039 })
2040 })
2041 .unzip();
2042
2043 let filtered = patches.filter(&mask, &mut ctx)?;
2044
2045 let Some(filtered) = filtered else {
2046 assert!(expected_indices.is_empty());
2047 return Ok(());
2048 };
2049
2050 assert_eq!(filtered.array_len(), mask_indices.len());
2051 assert_arrays_eq!(
2052 filtered.indices(),
2053 PrimitiveArray::from_iter(expected_indices),
2054 &mut ctx
2055 );
2056 assert_arrays_eq!(
2057 filtered.values(),
2058 PrimitiveArray::from_iter(expected_values),
2059 &mut ctx
2060 );
2061
2062 Ok(())
2063 }
2064
2065 #[test]
2067 fn test_filter_sparse_mask_past_index_type_max() -> VortexResult<()> {
2068 let mut ctx = SESSION.create_execution_ctx();
2069 let patches = Patches::new(
2070 1000,
2071 0,
2072 (0..=u8::MAX).collect::<Buffer<u8>>().into_array(),
2073 (0..256i32).collect::<Buffer<i32>>().into_array(),
2074 None,
2075 &mut ctx,
2076 )?;
2077
2078 let mask = Mask::from_indices(1000, [3, 255, 256, 900]);
2079 let filtered = patches
2080 .filter(&mask, &mut ctx)?
2081 .expect("patches at 3 and 255 are kept");
2082
2083 assert_arrays_eq!(
2084 filtered.indices(),
2085 PrimitiveArray::from_iter([0u64, 1]),
2086 &mut ctx
2087 );
2088 assert_arrays_eq!(
2089 filtered.values(),
2090 PrimitiveArray::from_iter([3i32, 255]),
2091 &mut ctx
2092 );
2093
2094 Ok(())
2095 }
2096
2097 #[test]
2098 fn test_filter_keep_all() {
2099 let mut ctx = SESSION.create_execution_ctx();
2100 let patches = Patches::new(
2101 10,
2102 0,
2103 buffer![2u64, 5, 8].into_array(),
2104 buffer![100i32, 200, 300].into_array(),
2105 None,
2106 &mut ctx,
2107 )
2108 .unwrap();
2109
2110 let mask = Mask::from_indices(10, 0..10);
2112 let filtered = patches.filter(&mask, &mut ctx).unwrap().unwrap();
2113
2114 assert_arrays_eq!(
2115 filtered.indices(),
2116 PrimitiveArray::from_iter([2u64, 5, 8]),
2117 &mut ctx
2118 );
2119 assert_arrays_eq!(
2120 filtered.values(),
2121 PrimitiveArray::from_iter([100i32, 200, 300]),
2122 &mut ctx
2123 );
2124 }
2125
2126 #[test]
2127 fn test_filter_none() {
2128 let mut ctx = SESSION.create_execution_ctx();
2129 let patches = Patches::new(
2130 10,
2131 0,
2132 buffer![2u64, 5, 8].into_array(),
2133 buffer![100i32, 200, 300].into_array(),
2134 None,
2135 &mut ctx,
2136 )
2137 .unwrap();
2138
2139 let mask = Mask::from_indices(10, vec![]);
2141 let filtered = patches.filter(&mask, &mut ctx).unwrap();
2142 assert!(filtered.is_none());
2143 }
2144
2145 #[test]
2146 fn test_filter_with_indices() {
2147 let mut ctx = SESSION.create_execution_ctx();
2148 let patches = Patches::new(
2149 10,
2150 0,
2151 buffer![2u64, 5, 8].into_array(),
2152 buffer![100i32, 200, 300].into_array(),
2153 None,
2154 &mut ctx,
2155 )
2156 .unwrap();
2157
2158 let mask = Mask::from_indices(10, vec![2, 5, 9]);
2160 let filtered = patches.filter(&mask, &mut ctx).unwrap().unwrap();
2161
2162 assert_arrays_eq!(
2163 filtered.indices(),
2164 PrimitiveArray::from_iter([0u64, 1]),
2165 &mut ctx
2166 ); assert_arrays_eq!(
2168 filtered.values(),
2169 PrimitiveArray::from_iter([100i32, 200]),
2170 &mut ctx
2171 );
2172 }
2173
2174 #[test]
2175 fn test_slice_full_range() {
2176 let mut ctx = SESSION.create_execution_ctx();
2177 let patches = Patches::new(
2178 10,
2179 0,
2180 buffer![2u64, 5, 8].into_array(),
2181 buffer![100i32, 200, 300].into_array(),
2182 None,
2183 &mut ctx,
2184 )
2185 .unwrap();
2186
2187 let sliced = patches.slice(0..10, &mut ctx).unwrap().unwrap();
2188
2189 assert_arrays_eq!(
2190 sliced.indices(),
2191 PrimitiveArray::from_iter([2u64, 5, 8]),
2192 &mut ctx
2193 );
2194 assert_arrays_eq!(
2195 sliced.values(),
2196 PrimitiveArray::from_iter([100i32, 200, 300]),
2197 &mut ctx
2198 );
2199 }
2200
2201 #[test]
2202 fn test_slice_partial() {
2203 let mut ctx = SESSION.create_execution_ctx();
2204 let patches = Patches::new(
2205 10,
2206 0,
2207 buffer![2u64, 5, 8].into_array(),
2208 buffer![100i32, 200, 300].into_array(),
2209 None,
2210 &mut ctx,
2211 )
2212 .unwrap();
2213
2214 let sliced = patches.slice(3..8, &mut ctx).unwrap().unwrap();
2216
2217 assert_arrays_eq!(
2218 sliced.indices(),
2219 PrimitiveArray::from_iter([5u64]),
2220 &mut ctx
2221 ); assert_arrays_eq!(
2223 sliced.values(),
2224 PrimitiveArray::from_iter([200i32]),
2225 &mut ctx
2226 );
2227 assert_eq!(sliced.array_len(), 5); assert_eq!(sliced.offset(), 3); }
2230
2231 #[test]
2232 fn test_slice_no_patches() {
2233 let mut ctx = SESSION.create_execution_ctx();
2234 let patches = Patches::new(
2235 10,
2236 0,
2237 buffer![2u64, 5, 8].into_array(),
2238 buffer![100i32, 200, 300].into_array(),
2239 None,
2240 &mut ctx,
2241 )
2242 .unwrap();
2243
2244 let sliced = patches.slice(6..7, &mut ctx).unwrap();
2246 assert!(sliced.is_none());
2247 }
2248
2249 #[test]
2250 fn test_slice_with_offset() {
2251 let mut ctx = SESSION.create_execution_ctx();
2252 let patches = Patches::new(
2253 10,
2254 5, buffer![7u64, 10, 13].into_array(), buffer![100i32, 200, 300].into_array(),
2257 None,
2258 &mut ctx,
2259 )
2260 .unwrap();
2261
2262 let sliced = patches.slice(3..8, &mut ctx).unwrap().unwrap();
2264
2265 assert_arrays_eq!(
2266 sliced.indices(),
2267 PrimitiveArray::from_iter([10u64]),
2268 &mut ctx
2269 ); assert_arrays_eq!(
2271 sliced.values(),
2272 PrimitiveArray::from_iter([200i32]),
2273 &mut ctx
2274 );
2275 assert_eq!(sliced.offset(), 8); }
2277
2278 #[test]
2279 fn test_indices_range() {
2280 let mut ctx = SESSION.create_execution_ctx();
2281 let patches = Patches::new(
2282 10,
2283 0,
2284 buffer![2u64, 5, 8].into_array(),
2285 buffer![100i32, 200, 300].into_array(),
2286 None,
2287 &mut ctx,
2288 )
2289 .unwrap();
2290
2291 assert_eq!(patches.min_index(&mut ctx).unwrap(), 2);
2292 assert_eq!(patches.max_index(&mut ctx).unwrap(), 8);
2293 }
2294
2295 #[test]
2296 fn test_search_index() {
2297 let mut ctx = SESSION.create_execution_ctx();
2298 let patches = Patches::new(
2299 10,
2300 0,
2301 buffer![2u64, 5, 8].into_array(),
2302 buffer![100i32, 200, 300].into_array(),
2303 None,
2304 &mut ctx,
2305 )
2306 .unwrap();
2307
2308 assert_eq!(
2310 patches.search_index(2, &mut ctx).unwrap(),
2311 SearchResult::Found(0)
2312 );
2313 assert_eq!(
2314 patches.search_index(5, &mut ctx).unwrap(),
2315 SearchResult::Found(1)
2316 );
2317 assert_eq!(
2318 patches.search_index(8, &mut ctx).unwrap(),
2319 SearchResult::Found(2)
2320 );
2321
2322 assert_eq!(
2324 patches.search_index(0, &mut ctx).unwrap(),
2325 SearchResult::NotFound(0)
2326 );
2327 assert_eq!(
2328 patches.search_index(3, &mut ctx).unwrap(),
2329 SearchResult::NotFound(1)
2330 );
2331 assert_eq!(
2332 patches.search_index(6, &mut ctx).unwrap(),
2333 SearchResult::NotFound(2)
2334 );
2335 assert_eq!(
2336 patches.search_index(9, &mut ctx).unwrap(),
2337 SearchResult::NotFound(3)
2338 );
2339 }
2340
2341 #[test]
2342 fn test_mask_boundary_patches() {
2343 let mut ctx = SESSION.create_execution_ctx();
2344 let patches = Patches::new(
2346 10,
2347 0,
2348 buffer![0u64, 9].into_array(),
2349 buffer![100i32, 200].into_array(),
2350 None,
2351 &mut ctx,
2352 )
2353 .unwrap();
2354
2355 let mask = Mask::from_iter([
2356 true, false, false, false, false, false, false, false, false, false,
2357 ]);
2358 let masked = patches.mask(&mask, &mut ctx).unwrap();
2359 assert!(masked.is_some());
2360 let masked = masked.unwrap();
2361 assert_arrays_eq!(
2362 masked.indices(),
2363 PrimitiveArray::from_iter([9u64]),
2364 &mut ctx
2365 );
2366 assert_arrays_eq!(
2367 masked.values(),
2368 PrimitiveArray::from_option_iter([Some(200i32)]),
2369 &mut ctx
2370 );
2371 }
2372
2373 #[test]
2374 fn test_mask_all_patches_removed() {
2375 let mut ctx = SESSION.create_execution_ctx();
2376 let patches = Patches::new(
2378 10,
2379 0,
2380 buffer![2u64, 5, 8].into_array(),
2381 buffer![100i32, 200, 300].into_array(),
2382 None,
2383 &mut ctx,
2384 )
2385 .unwrap();
2386
2387 let mask = Mask::from_iter([
2389 false, false, true, false, false, true, false, false, true, false,
2390 ]);
2391 let masked = patches.mask(&mask, &mut ctx).unwrap();
2392 assert!(masked.is_none());
2393 }
2394
2395 #[test]
2396 fn test_mask_no_patches_removed() {
2397 let mut ctx = SESSION.create_execution_ctx();
2398 let patches = Patches::new(
2400 10,
2401 0,
2402 buffer![2u64, 5, 8].into_array(),
2403 buffer![100i32, 200, 300].into_array(),
2404 None,
2405 &mut ctx,
2406 )
2407 .unwrap();
2408
2409 let mask = Mask::from_iter([
2411 true, false, false, true, false, false, true, false, false, true,
2412 ]);
2413 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2414
2415 assert_arrays_eq!(
2416 masked.indices(),
2417 PrimitiveArray::from_iter([2u64, 5, 8]),
2418 &mut ctx
2419 );
2420 assert_arrays_eq!(
2421 masked.values(),
2422 PrimitiveArray::from_option_iter([Some(100i32), Some(200), Some(300)]),
2423 &mut ctx
2424 );
2425 }
2426
2427 #[test]
2428 fn test_mask_single_patch() {
2429 let mut ctx = SESSION.create_execution_ctx();
2430 let patches = Patches::new(
2432 5,
2433 0,
2434 buffer![2u64].into_array(),
2435 buffer![42i32].into_array(),
2436 None,
2437 &mut ctx,
2438 )
2439 .unwrap();
2440
2441 let mask = Mask::from_iter([false, false, true, false, false]);
2443 let masked = patches.mask(&mask, &mut ctx).unwrap();
2444 assert!(masked.is_none());
2445
2446 let mask = Mask::from_iter([true, false, false, true, false]);
2448 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2449 assert_arrays_eq!(
2450 masked.indices(),
2451 PrimitiveArray::from_iter([2u64]),
2452 &mut ctx
2453 );
2454 assert_arrays_eq!(
2455 masked.values(),
2456 PrimitiveArray::from_option_iter([Some(42i32)]),
2457 &mut ctx
2458 );
2459 }
2460
2461 #[test]
2462 fn test_mask_contiguous_patches() {
2463 let mut ctx = SESSION.create_execution_ctx();
2464 let patches = Patches::new(
2466 10,
2467 0,
2468 buffer![3u64, 4, 5, 6].into_array(),
2469 buffer![100i32, 200, 300, 400].into_array(),
2470 None,
2471 &mut ctx,
2472 )
2473 .unwrap();
2474
2475 let mask = Mask::from_iter([
2477 false, false, false, false, true, true, false, false, false, false,
2478 ]);
2479 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2480
2481 assert_arrays_eq!(
2482 masked.indices(),
2483 PrimitiveArray::from_iter([3u64, 6]),
2484 &mut ctx
2485 );
2486 assert_arrays_eq!(
2487 masked.values(),
2488 PrimitiveArray::from_option_iter([Some(100i32), Some(400)]),
2489 &mut ctx
2490 );
2491 }
2492
2493 #[test]
2494 fn test_mask_with_large_offset() {
2495 let mut ctx = SESSION.create_execution_ctx();
2496 let patches = Patches::new(
2498 20,
2499 15,
2500 buffer![16u64, 17, 19].into_array(), buffer![100i32, 200, 300].into_array(),
2502 None,
2503 &mut ctx,
2504 )
2505 .unwrap();
2506
2507 let mask = Mask::from_iter([
2509 false, false, true, false, false, false, false, false, false, false, false, false,
2510 false, false, false, false, false, false, false, false,
2511 ]);
2512 let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2513
2514 assert_arrays_eq!(
2515 masked.indices(),
2516 PrimitiveArray::from_iter([16u64, 19]),
2517 &mut ctx
2518 );
2519 assert_arrays_eq!(
2520 masked.values(),
2521 PrimitiveArray::from_option_iter([Some(100i32), Some(300)]),
2522 &mut ctx
2523 );
2524 }
2525
2526 #[test]
2527 #[should_panic(expected = "Filter mask length 5 does not match array length 10")]
2528 fn test_mask_wrong_length() {
2529 let mut ctx = SESSION.create_execution_ctx();
2530 let patches = Patches::new(
2531 10,
2532 0,
2533 buffer![2u64, 5, 8].into_array(),
2534 buffer![100i32, 200, 300].into_array(),
2535 None,
2536 &mut ctx,
2537 )
2538 .unwrap();
2539
2540 let mask = Mask::from_iter([false, false, true, false, false]);
2542 patches.mask(&mask, &mut ctx).unwrap();
2543 }
2544
2545 #[test]
2546 fn test_chunk_offsets_search() {
2547 let mut ctx = SESSION.create_execution_ctx();
2548 let indices = buffer![100u64, 200, 3000, 3100].into_array();
2549 let values = buffer![10i32, 20, 30, 40].into_array();
2550 let chunk_offsets = buffer![0u64, 2, 2, 3].into_array();
2551 let patches =
2552 Patches::new(4096, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2553
2554 assert!(patches.chunk_offsets.is_some());
2555
2556 assert_eq!(
2558 patches.search_index(100, &mut ctx).unwrap(),
2559 SearchResult::Found(0)
2560 );
2561 assert_eq!(
2562 patches.search_index(200, &mut ctx).unwrap(),
2563 SearchResult::Found(1)
2564 );
2565
2566 assert_eq!(
2568 patches.search_index(1500, &mut ctx).unwrap(),
2569 SearchResult::NotFound(2)
2570 );
2571 assert_eq!(
2572 patches.search_index(2000, &mut ctx).unwrap(),
2573 SearchResult::NotFound(2)
2574 );
2575
2576 assert_eq!(
2578 patches.search_index(3000, &mut ctx).unwrap(),
2579 SearchResult::Found(2)
2580 );
2581 assert_eq!(
2582 patches.search_index(3100, &mut ctx).unwrap(),
2583 SearchResult::Found(3)
2584 );
2585
2586 assert_eq!(
2587 patches.search_index(1024, &mut ctx).unwrap(),
2588 SearchResult::NotFound(2)
2589 );
2590 }
2591
2592 #[test]
2593 fn test_chunk_offsets_with_slice() {
2594 let mut ctx = SESSION.create_execution_ctx();
2595 let indices = buffer![100u64, 500, 1200, 1300, 1500, 1800, 2100, 2500].into_array();
2596 let values = buffer![10i32, 20, 30, 35, 40, 45, 50, 60].into_array();
2597 let chunk_offsets = buffer![0u64, 2, 6].into_array();
2598 let patches =
2599 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2600
2601 let sliced = patches.slice(1000..2200, &mut ctx).unwrap().unwrap();
2602
2603 assert!(sliced.chunk_offsets.is_some());
2604 assert_eq!(sliced.offset(), 1000);
2605
2606 assert_eq!(
2607 sliced.search_index(200, &mut ctx).unwrap(),
2608 SearchResult::Found(0)
2609 );
2610 assert_eq!(
2611 sliced.search_index(500, &mut ctx).unwrap(),
2612 SearchResult::Found(2)
2613 );
2614 assert_eq!(
2615 sliced.search_index(1100, &mut ctx).unwrap(),
2616 SearchResult::Found(4)
2617 );
2618
2619 assert_eq!(
2620 sliced.search_index(250, &mut ctx).unwrap(),
2621 SearchResult::NotFound(1)
2622 );
2623 assert_arrays_eq!(
2624 sliced.values(),
2625 PrimitiveArray::from_iter([30i32, 35, 40, 45, 50]),
2626 &mut ctx
2627 );
2628 }
2629
2630 #[test]
2631 fn test_chunk_offsets_with_slice_after_first_chunk() {
2632 let mut ctx = SESSION.create_execution_ctx();
2633 let indices = buffer![100u64, 500, 1200, 1300, 1500, 1800, 2100, 2500].into_array();
2634 let values = buffer![10i32, 20, 30, 35, 40, 45, 50, 60].into_array();
2635 let chunk_offsets = buffer![0u64, 2, 6].into_array();
2636 let patches =
2637 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2638
2639 let sliced = patches.slice(1300..2200, &mut ctx).unwrap().unwrap();
2640
2641 assert!(sliced.chunk_offsets.is_some());
2642 assert_eq!(sliced.offset(), 1300);
2643
2644 assert_eq!(
2645 sliced.search_index(0, &mut ctx).unwrap(),
2646 SearchResult::Found(0)
2647 );
2648 assert_eq!(
2649 sliced.search_index(200, &mut ctx).unwrap(),
2650 SearchResult::Found(1)
2651 );
2652 assert_eq!(
2653 sliced.search_index(500, &mut ctx).unwrap(),
2654 SearchResult::Found(2)
2655 );
2656 assert_eq!(
2657 sliced.search_index(250, &mut ctx).unwrap(),
2658 SearchResult::NotFound(2)
2659 );
2660 assert_eq!(
2661 sliced.search_index(900, &mut ctx).unwrap(),
2662 SearchResult::NotFound(4)
2663 );
2664 assert_arrays_eq!(
2665 sliced.values(),
2666 PrimitiveArray::from_iter([35i32, 40, 45, 50]),
2667 &mut ctx
2668 );
2669 }
2670
2671 #[test]
2672 fn test_chunk_offsets_slice_empty_result() {
2673 let mut ctx = SESSION.create_execution_ctx();
2674 let indices = buffer![100u64, 200, 3000, 3100].into_array();
2675 let values = buffer![10i32, 20, 30, 40].into_array();
2676 let chunk_offsets = buffer![0u64, 2, 2, 3].into_array();
2677 let patches =
2678 Patches::new(4000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2679
2680 let sliced = patches.slice(1000..2000, &mut ctx).unwrap();
2681 assert!(sliced.is_none());
2682 }
2683
2684 #[test]
2685 fn test_chunk_offsets_slice_single_patch() {
2686 let mut ctx = SESSION.create_execution_ctx();
2687 let indices = buffer![100u64, 1200, 1300, 2500].into_array();
2688 let values = buffer![10i32, 20, 30, 40].into_array();
2689 let chunk_offsets = buffer![0u64, 1, 3].into_array();
2690 let patches =
2691 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2692
2693 let sliced = patches.slice(1100..1250, &mut ctx).unwrap().unwrap();
2694
2695 assert_eq!(sliced.num_patches(), 1);
2696 assert_eq!(sliced.offset(), 1100);
2697 assert_eq!(
2698 sliced.search_index(100, &mut ctx).unwrap(),
2699 SearchResult::Found(0)
2700 ); assert_eq!(
2702 sliced.search_index(50, &mut ctx).unwrap(),
2703 SearchResult::NotFound(0)
2704 );
2705 assert_eq!(
2706 sliced.search_index(150, &mut ctx).unwrap(),
2707 SearchResult::NotFound(1)
2708 );
2709 assert_arrays_eq!(
2710 sliced.values(),
2711 PrimitiveArray::from_iter([20i32]),
2712 &mut ctx
2713 );
2714 }
2715
2716 #[test]
2717 fn test_chunk_offsets_slice_across_chunks() {
2718 let mut ctx = SESSION.create_execution_ctx();
2719 let indices = buffer![100u64, 200, 1100, 1200, 2100, 2200].into_array();
2720 let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2721 let chunk_offsets = buffer![0u64, 2, 4].into_array();
2722 let patches =
2723 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2724
2725 let sliced = patches.slice(150..2150, &mut ctx).unwrap().unwrap();
2726
2727 assert_eq!(sliced.num_patches(), 4);
2728 assert_eq!(sliced.offset(), 150);
2729
2730 assert_eq!(
2731 sliced.search_index(50, &mut ctx).unwrap(),
2732 SearchResult::Found(0)
2733 ); assert_eq!(
2735 sliced.search_index(950, &mut ctx).unwrap(),
2736 SearchResult::Found(1)
2737 ); assert_eq!(
2739 sliced.search_index(1050, &mut ctx).unwrap(),
2740 SearchResult::Found(2)
2741 ); assert_eq!(
2743 sliced.search_index(1950, &mut ctx).unwrap(),
2744 SearchResult::Found(3)
2745 ); assert_arrays_eq!(
2747 sliced.values(),
2748 PrimitiveArray::from_iter([20i32, 30, 40, 50]),
2749 &mut ctx
2750 );
2751 }
2752
2753 #[test]
2754 fn test_chunk_offsets_boundary_searches() {
2755 let mut ctx = SESSION.create_execution_ctx();
2756 let indices = buffer![1023u64, 1024, 1025, 2047, 2048].into_array();
2757 let values = buffer![10i32, 20, 30, 40, 50].into_array();
2758 let chunk_offsets = buffer![0u64, 1, 4].into_array();
2759 let patches =
2760 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2761
2762 assert_eq!(
2763 patches.search_index(1023, &mut ctx).unwrap(),
2764 SearchResult::Found(0)
2765 );
2766 assert_eq!(
2767 patches.search_index(1024, &mut ctx).unwrap(),
2768 SearchResult::Found(1)
2769 );
2770 assert_eq!(
2771 patches.search_index(1025, &mut ctx).unwrap(),
2772 SearchResult::Found(2)
2773 );
2774 assert_eq!(
2775 patches.search_index(2047, &mut ctx).unwrap(),
2776 SearchResult::Found(3)
2777 );
2778 assert_eq!(
2779 patches.search_index(2048, &mut ctx).unwrap(),
2780 SearchResult::Found(4)
2781 );
2782
2783 assert_eq!(
2784 patches.search_index(1022, &mut ctx).unwrap(),
2785 SearchResult::NotFound(0)
2786 );
2787 assert_eq!(
2788 patches.search_index(2046, &mut ctx).unwrap(),
2789 SearchResult::NotFound(3)
2790 );
2791 }
2792
2793 #[test]
2794 fn test_chunk_offsets_slice_edge_cases() {
2795 let mut ctx = SESSION.create_execution_ctx();
2796 let indices = buffer![0u64, 1, 1023, 1024, 2047, 2048].into_array();
2797 let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2798 let chunk_offsets = buffer![0u64, 3, 5].into_array();
2799 let patches =
2800 Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2801
2802 let sliced = patches.slice(0..10, &mut ctx).unwrap().unwrap();
2804 assert_eq!(sliced.num_patches(), 2);
2805 assert_eq!(
2806 sliced.search_index(0, &mut ctx).unwrap(),
2807 SearchResult::Found(0)
2808 );
2809 assert_eq!(
2810 sliced.search_index(1, &mut ctx).unwrap(),
2811 SearchResult::Found(1)
2812 );
2813
2814 assert_arrays_eq!(
2815 sliced.values(),
2816 PrimitiveArray::from_iter([10i32, 20]),
2817 &mut ctx
2818 );
2819
2820 let sliced = patches.slice(2040..3000, &mut ctx).unwrap().unwrap();
2822 assert_eq!(sliced.num_patches(), 2); assert_eq!(
2824 sliced.search_index(7, &mut ctx).unwrap(),
2825 SearchResult::Found(0)
2826 ); assert_eq!(
2828 sliced.search_index(8, &mut ctx).unwrap(),
2829 SearchResult::Found(1)
2830 ); assert_arrays_eq!(
2832 sliced.values(),
2833 PrimitiveArray::from_iter([50i32, 60]),
2834 &mut ctx
2835 );
2836 }
2837
2838 #[test]
2839 fn test_chunk_offsets_slice_nested() {
2840 let mut ctx = SESSION.create_execution_ctx();
2841 let indices = buffer![100u64, 200, 300, 400, 500, 600].into_array();
2842 let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2843 let chunk_offsets = buffer![0u64].into_array();
2844 let patches =
2845 Patches::new(1000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2846
2847 let sliced1 = patches.slice(150..550, &mut ctx).unwrap().unwrap();
2848 assert_eq!(sliced1.num_patches(), 4); let sliced2 = sliced1.slice(100..250, &mut ctx).unwrap().unwrap();
2851 assert_eq!(sliced2.num_patches(), 1); assert_eq!(sliced2.offset(), 250);
2853
2854 assert_eq!(
2855 sliced2.search_index(50, &mut ctx).unwrap(),
2856 SearchResult::Found(0)
2857 ); assert_eq!(
2859 sliced2.search_index(150, &mut ctx).unwrap(),
2860 SearchResult::NotFound(1)
2861 );
2862 assert_arrays_eq!(
2863 sliced1.values(),
2864 PrimitiveArray::from_iter([20i32, 30, 40, 50]),
2865 &mut ctx
2866 );
2867 assert_arrays_eq!(
2868 sliced2.values(),
2869 PrimitiveArray::from_iter([30i32]),
2870 &mut ctx
2871 );
2872 }
2873
2874 #[test]
2875 fn test_nested_slice_with_dropped_first_chunk() {
2876 let mut ctx = SESSION.create_execution_ctx();
2877 let indices = buffer![0u64, 1024].into_array();
2879 let values = buffer![1i32, 2].into_array();
2880 let chunk_offsets = buffer![0u64, 1].into_array();
2881 let patches =
2882 Patches::new(2048, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2883
2884 let dropped_first = patches.slice(1024..2048, &mut ctx).unwrap().unwrap();
2886 let resliced = dropped_first.slice(0..1024, &mut ctx).unwrap().unwrap();
2887 assert_eq!(resliced.num_patches(), 1);
2888 assert_eq!(resliced.array_len(), 1024);
2889 assert_eq!(resliced.offset(), 1024);
2890 assert_eq!(
2891 resliced.search_index(0, &mut ctx).unwrap(),
2892 SearchResult::Found(0)
2893 );
2894 assert_arrays_eq!(
2895 resliced.values(),
2896 PrimitiveArray::from_iter([2i32]),
2897 &mut ctx
2898 );
2899 }
2900
2901 #[test]
2902 fn test_index_larger_than_length() {
2903 let mut ctx = SESSION.create_execution_ctx();
2904 let chunk_offsets = buffer![0u64].into_array();
2905 let indices = buffer![1023u64].into_array();
2906 let values = buffer![42i32].into_array();
2907 let patches =
2908 Patches::new(1024, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2909 assert_eq!(
2910 patches.search_index(2048, &mut ctx).unwrap(),
2911 SearchResult::NotFound(1)
2912 );
2913 }
2914}