• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vortex-data / vortex / 16331938722

16 Jul 2025 10:49PM UTC coverage: 80.702% (-0.9%) from 81.557%
16331938722

push

github

web-flow
feat: build with stable rust (#3881)

120 of 173 new or added lines in 28 files covered. (69.36%)

174 existing lines in 102 files now uncovered.

41861 of 51871 relevant lines covered (80.7%)

157487.71 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.18
/vortex-array/src/patches.rs
1
// SPDX-License-Identifier: Apache-2.0
2
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3

4
use std::cmp::Ordering;
5
use std::fmt::Debug;
6
use std::hash::Hash;
7

8
use itertools::Itertools as _;
9
use num_traits::{NumCast, ToPrimitive};
10
use serde::{Deserialize, Serialize};
11
use vortex_buffer::BufferMut;
12
use vortex_dtype::Nullability::NonNullable;
13
use vortex_dtype::{
14
    DType, NativePType, PType, match_each_integer_ptype, match_each_unsigned_integer_ptype,
15
};
16
use vortex_error::{
17
    VortexError, VortexExpect, VortexResult, VortexUnwrap, vortex_bail, vortex_err,
18
};
19
use vortex_mask::{AllOr, Mask};
20
use vortex_scalar::{PValue, Scalar};
21
use vortex_utils::aliases::hash_map::HashMap;
22

23
use crate::arrays::PrimitiveArray;
24
use crate::compute::{cast, filter, take};
25
use crate::search_sorted::{SearchResult, SearchSorted, SearchSortedSide};
26
use crate::vtable::ValidityHelper;
27
use crate::{Array, ArrayRef, IntoArray, ToCanonical};
28

29
#[derive(Copy, Clone, Serialize, Deserialize, prost::Message)]
30
pub struct PatchesMetadata {
31
    #[prost(uint64, tag = "1")]
32
    len: u64,
33
    #[prost(uint64, tag = "2")]
34
    offset: u64,
35
    #[prost(enumeration = "PType", tag = "3")]
36
    indices_ptype: i32,
37
}
38

39
impl PatchesMetadata {
40
    pub fn new(len: usize, offset: usize, indices_ptype: PType) -> Self {
72✔
41
        Self {
72✔
42
            len: len as u64,
72✔
43
            offset: offset as u64,
72✔
44
            indices_ptype: indices_ptype as i32,
72✔
45
        }
72✔
46
    }
72✔
47

48
    #[inline]
49
    pub fn len(&self) -> usize {
1,276✔
50
        usize::try_from(self.len).vortex_expect("len is a valid usize")
1,276✔
51
    }
1,276✔
52

53
    #[inline]
54
    pub fn is_empty(&self) -> bool {
×
55
        self.len == 0
×
56
    }
×
57

58
    #[inline]
59
    pub fn offset(&self) -> usize {
638✔
60
        usize::try_from(self.offset).vortex_expect("offset is a valid usize")
638✔
61
    }
638✔
62

63
    #[inline]
64
    pub fn indices_dtype(&self) -> DType {
638✔
65
        assert!(
638✔
66
            self.indices_ptype().is_unsigned_int(),
638✔
67
            "Patch indices must be unsigned integers"
×
68
        );
69
        DType::Primitive(self.indices_ptype(), NonNullable)
638✔
70
    }
638✔
71
}
72

73
/// A helper for working with patched arrays.
74
#[derive(Debug, Clone)]
75
pub struct Patches {
76
    array_len: usize,
77
    offset: usize,
78
    indices: ArrayRef,
79
    values: ArrayRef,
80
}
81

82
impl Patches {
83
    pub fn new(array_len: usize, offset: usize, indices: ArrayRef, values: ArrayRef) -> Self {
8,230✔
84
        assert_eq!(
8,230✔
85
            indices.len(),
8,230✔
86
            values.len(),
8,230✔
87
            "Patch indices and values must have the same length"
×
88
        );
89
        assert!(
8,230✔
90
            indices.dtype().is_unsigned_int(),
8,230✔
91
            "Patch indices must be unsigned integers"
×
92
        );
93
        assert!(
8,230✔
94
            indices.len() <= array_len,
8,230✔
95
            "Patch indices must be shorter than the array length"
×
96
        );
97
        assert!(!indices.is_empty(), "Patch indices must not be empty");
8,230✔
98
        let max = usize::try_from(
8,230✔
99
            &indices
8,230✔
100
                .scalar_at(indices.len() - 1)
8,230✔
101
                .vortex_expect("indices are not empty"),
8,230✔
102
        )
103
        .vortex_expect("indices must be a number");
8,230✔
104
        assert!(
8,230✔
105
            max - offset < array_len,
8,230✔
106
            "Patch indices {max:?}, offset {offset} are longer than the array length {array_len}"
×
107
        );
108
        Self::new_unchecked(array_len, offset, indices, values)
8,230✔
109
    }
8,230✔
110

111
    /// Construct new patches without validating any of the arguments
112
    ///
113
    /// # Safety
114
    ///
115
    /// Users have to assert that
116
    /// * Indices and values have the same length
117
    /// * Indices is an unsigned integer type
118
    /// * Indices must be sorted
119
    /// * Last value in indices is smaller than array_len
120
    pub fn new_unchecked(
9,814✔
121
        array_len: usize,
9,814✔
122
        offset: usize,
9,814✔
123
        indices: ArrayRef,
9,814✔
124
        values: ArrayRef,
9,814✔
125
    ) -> Self {
9,814✔
126
        Self {
9,814✔
127
            array_len,
9,814✔
128
            offset,
9,814✔
129
            indices,
9,814✔
130
            values,
9,814✔
131
        }
9,814✔
132
    }
9,814✔
133

134
    pub fn array_len(&self) -> usize {
32,883✔
135
        self.array_len
32,883✔
136
    }
32,883✔
137

138
    pub fn num_patches(&self) -> usize {
1,441✔
139
        self.indices.len()
1,441✔
140
    }
1,441✔
141

142
    pub fn dtype(&self) -> &DType {
2,960✔
143
        self.values.dtype()
2,960✔
144
    }
2,960✔
145

146
    pub fn indices(&self) -> &ArrayRef {
10,875✔
147
        &self.indices
10,875✔
148
    }
10,875✔
149

150
    pub fn into_indices(self) -> ArrayRef {
×
151
        self.indices
×
152
    }
×
153

154
    pub fn indices_mut(&mut self) -> &mut ArrayRef {
×
155
        &mut self.indices
×
156
    }
×
157

158
    pub fn values(&self) -> &ArrayRef {
20,614✔
159
        &self.values
20,614✔
160
    }
20,614✔
161

162
    pub fn into_values(self) -> ArrayRef {
36✔
163
        self.values
36✔
164
    }
36✔
165

166
    pub fn values_mut(&mut self) -> &mut ArrayRef {
×
167
        &mut self.values
×
168
    }
×
169

170
    pub fn offset(&self) -> usize {
82,683✔
171
        self.offset
82,683✔
172
    }
82,683✔
173

174
    pub fn indices_ptype(&self) -> PType {
×
175
        PType::try_from(self.indices.dtype()).vortex_expect("primitive indices")
×
176
    }
×
177

178
    pub fn to_metadata(&self, len: usize, dtype: &DType) -> VortexResult<PatchesMetadata> {
200✔
179
        if self.indices.len() > len {
200✔
180
            vortex_bail!(
×
181
                "Patch indices {} are longer than the array length {}",
×
182
                self.indices.len(),
×
183
                len
184
            );
185
        }
200✔
186
        if self.values.dtype() != dtype {
200✔
187
            vortex_bail!(
×
188
                "Patch values dtype {} does not match array dtype {}",
×
189
                self.values.dtype(),
×
190
                dtype
191
            );
192
        }
200✔
193
        Ok(PatchesMetadata {
200✔
194
            len: self.indices.len() as u64,
200✔
195
            offset: self.offset as u64,
200✔
196
            indices_ptype: PType::try_from(self.indices.dtype()).vortex_expect("primitive indices")
200✔
197
                as i32,
200✔
198
        })
200✔
199
    }
200✔
200

201
    pub fn cast_values(self, values_dtype: &DType) -> VortexResult<Self> {
1,584✔
202
        Ok(Self::new_unchecked(
1,584✔
203
            self.array_len,
1,584✔
204
            self.offset,
1,584✔
205
            self.indices,
1,584✔
206
            cast(&self.values, values_dtype)?,
1,584✔
207
        ))
208
    }
1,584✔
209

210
    /// Get the patched value at a given index if it exists.
211
    pub fn get_patched(&self, index: usize) -> VortexResult<Option<Scalar>> {
383,568✔
212
        if let Some(patch_idx) = self.search_index(index)?.to_found() {
383,568✔
213
            self.values().scalar_at(patch_idx).map(Some)
5,988✔
214
        } else {
215
            Ok(None)
377,580✔
216
        }
217
    }
383,568✔
218

219
    /// Return the insertion point of `index` in the [Self::indices].
220
    pub fn search_index(&self, index: usize) -> VortexResult<SearchResult> {
385,800✔
221
        Ok(self.indices.as_primitive_typed().search_sorted(
385,800✔
222
            &PValue::U64((index + self.offset) as u64),
385,800✔
223
            SearchSortedSide::Left,
385,800✔
224
        ))
385,800✔
225
    }
385,800✔
226

227
    /// Return the search_sorted result for the given target re-mapped into the original indices.
228
    pub fn search_sorted<T: Into<Scalar>>(
11✔
229
        &self,
11✔
230
        target: T,
11✔
231
        side: SearchSortedSide,
11✔
232
    ) -> VortexResult<SearchResult> {
11✔
233
        let target = target.into();
11✔
234

235
        let sr = if self.values().dtype().is_primitive() {
11✔
236
            self.values()
11✔
237
                .as_primitive_typed()
11✔
238
                .search_sorted(&target.as_primitive().pvalue(), side)
11✔
239
        } else {
240
            self.values().search_sorted(&target, side)
×
241
        };
242

243
        let index_idx = sr.to_offsets_index(self.indices().len(), side);
11✔
244
        let index = usize::try_from(&self.indices().scalar_at(index_idx)?)? - self.offset;
11✔
245
        Ok(match sr {
11✔
246
            // If we reached the end of patched values when searching then the result is one after the last patch index
247
            SearchResult::Found(i) => SearchResult::Found(
3✔
248
                if i == self.indices().len() || side == SearchSortedSide::Right {
3✔
249
                    index + 1
2✔
250
                } else {
251
                    index
1✔
252
                },
253
            ),
254
            // If the result is NotFound we should return index that's one after the nearest not found index for the corresponding value
255
            SearchResult::NotFound(i) => {
8✔
256
                SearchResult::NotFound(if i == 0 { index } else { index + 1 })
8✔
257
            }
258
        })
259
    }
11✔
260

261
    /// Returns the minimum patch index
262
    pub fn min_index(&self) -> VortexResult<usize> {
397✔
263
        Ok(usize::try_from(&self.indices().scalar_at(0)?)? - self.offset)
397✔
264
    }
397✔
265

266
    /// Returns the maximum patch index
267
    pub fn max_index(&self) -> VortexResult<usize> {
397✔
268
        Ok(usize::try_from(&self.indices().scalar_at(self.indices().len() - 1)?)? - self.offset)
397✔
269
    }
397✔
270

271
    /// Filter the patches by a mask, resulting in new patches for the filtered array.
272
    pub fn filter(&self, mask: &Mask) -> VortexResult<Option<Self>> {
377✔
273
        match mask.indices() {
377✔
274
            AllOr::All => Ok(Some(self.clone())),
×
275
            AllOr::None => Ok(None),
×
276
            AllOr::Some(mask_indices) => {
377✔
277
                let flat_indices = self.indices().to_primitive()?;
377✔
278
                match_each_unsigned_integer_ptype!(flat_indices.ptype(), |I| {
377✔
279
                    filter_patches_with_mask(
×
280
                        flat_indices.as_slice::<I>(),
×
281
                        self.offset(),
×
282
                        self.values(),
×
283
                        mask_indices,
×
284
                    )
285
                })
286
            }
287
        }
288
    }
377✔
289

290
    /// Slice the patches by a range of the patched array.
291
    pub fn slice(&self, start: usize, stop: usize) -> VortexResult<Option<Self>> {
1,116✔
292
        let patch_start = self.search_index(start)?.to_index();
1,116✔
293
        let patch_stop = self.search_index(stop)?.to_index();
1,116✔
294

295
        if patch_start == patch_stop {
1,116✔
296
            return Ok(None);
236✔
297
        }
880✔
298

299
        // Slice out the values and indices
300
        let values = self.values().slice(patch_start, patch_stop)?;
880✔
301
        let indices = self.indices().slice(patch_start, patch_stop)?;
880✔
302

303
        Ok(Some(Self::new(
880✔
304
            stop - start,
880✔
305
            start + self.offset(),
880✔
306
            indices,
880✔
307
            values,
880✔
308
        )))
880✔
309
    }
1,116✔
310

311
    // https://docs.google.com/spreadsheets/d/1D9vBZ1QJ6mwcIvV5wIL0hjGgVchcEnAyhvitqWu2ugU
312
    const PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN: f64 = 5.0;
313

314
    fn is_map_faster_than_search(&self, take_indices: &PrimitiveArray) -> bool {
469✔
315
        (self.num_patches() as f64 / take_indices.len() as f64)
469✔
316
            < Self::PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN
469✔
317
    }
469✔
318

319
    /// Take the indicies from the patches
320
    ///
321
    /// Any nulls in take_indices are added to the resulting patches.
322
    pub fn take_with_nulls(&self, take_indices: &dyn Array) -> VortexResult<Option<Self>> {
72✔
323
        if take_indices.is_empty() {
72✔
324
            return Ok(None);
×
325
        }
72✔
326

327
        let take_indices = take_indices.to_primitive()?;
72✔
328
        if self.is_map_faster_than_search(&take_indices) {
72✔
329
            self.take_map(take_indices, true)
72✔
330
        } else {
331
            self.take_search(take_indices, true)
×
332
        }
333
    }
72✔
334

335
    /// Take the indices from the patches.
336
    ///
337
    /// Any nulls in take_indices are ignored.
338
    pub fn take(&self, take_indices: &dyn Array) -> VortexResult<Option<Self>> {
397✔
339
        if take_indices.is_empty() {
397✔
340
            return Ok(None);
×
341
        }
397✔
342

343
        let take_indices = take_indices.to_primitive()?;
397✔
344
        if self.is_map_faster_than_search(&take_indices) {
397✔
345
            self.take_map(take_indices, false)
325✔
346
        } else {
347
            self.take_search(take_indices, false)
72✔
348
        }
349
    }
397✔
350

351
    pub fn take_search(
72✔
352
        &self,
72✔
353
        take_indices: PrimitiveArray,
72✔
354
        include_nulls: bool,
72✔
355
    ) -> VortexResult<Option<Self>> {
72✔
356
        let indices = self.indices.to_primitive()?;
72✔
357
        let new_length = take_indices.len();
72✔
358

359
        let Some((new_indices, values_indices)) =
72✔
360
            match_each_unsigned_integer_ptype!(indices.ptype(), |Indices| {
72✔
361
                match_each_integer_ptype!(take_indices.ptype(), |TakeIndices| {
×
362
                    take_search::<_, TakeIndices>(
×
363
                        indices.as_slice::<Indices>(),
×
364
                        take_indices,
×
365
                        self.offset(),
×
366
                        include_nulls,
×
367
                    )?
×
368
                })
369
            })
370
        else {
371
            return Ok(None);
×
372
        };
373

374
        Ok(Some(Self::new(
72✔
375
            new_length,
72✔
376
            0,
377
            new_indices,
72✔
378
            take(self.values(), &values_indices)?,
72✔
379
        )))
380
    }
72✔
381

382
    pub fn take_map(
397✔
383
        &self,
397✔
384
        take_indices: PrimitiveArray,
397✔
385
        include_nulls: bool,
397✔
386
    ) -> VortexResult<Option<Self>> {
397✔
387
        let indices = self.indices.to_primitive()?;
397✔
388
        let new_length = take_indices.len();
397✔
389

390
        let Some((new_sparse_indices, value_indices)) =
361✔
391
            match_each_unsigned_integer_ptype!(indices.ptype(), |Indices| {
397✔
392
                match_each_integer_ptype!(take_indices.ptype(), |TakeIndices| {
36✔
UNCOV
393
                    take_map::<_, TakeIndices>(
×
394
                        indices.as_slice::<Indices>(),
×
395
                        take_indices,
×
396
                        self.offset(),
×
397
                        self.min_index()?,
×
398
                        self.max_index()?,
×
399
                        include_nulls,
×
400
                    )?
×
401
                })
402
            })
403
        else {
404
            return Ok(None);
36✔
405
        };
406

407
        Ok(Some(Patches::new(
361✔
408
            new_length,
361✔
409
            0,
410
            new_sparse_indices,
361✔
411
            take(self.values(), &value_indices)?,
361✔
412
        )))
413
    }
397✔
414

415
    pub fn map_values<F>(self, f: F) -> VortexResult<Self>
16✔
416
    where
16✔
417
        F: FnOnce(ArrayRef) -> VortexResult<ArrayRef>,
16✔
418
    {
419
        let values = f(self.values)?;
16✔
420
        if self.indices.len() != values.len() {
16✔
421
            vortex_bail!(
×
422
                "map_values must preserve length: expected {} received {}",
×
423
                self.indices.len(),
×
424
                values.len()
×
425
            )
426
        }
16✔
427
        Ok(Self::new(self.array_len, self.offset, self.indices, values))
16✔
428
    }
16✔
429
}
430

431
fn take_search<I: NativePType + NumCast + PartialOrd, T: NativePType + NumCast>(
72✔
432
    indices: &[I],
72✔
433
    take_indices: PrimitiveArray,
72✔
434
    indices_offset: usize,
72✔
435
    include_nulls: bool,
72✔
436
) -> VortexResult<Option<(ArrayRef, ArrayRef)>>
72✔
437
where
72✔
438
    usize: TryFrom<T>,
72✔
439
    VortexError: From<<usize as TryFrom<T>>::Error>,
72✔
440
{
441
    let take_indices_validity = take_indices.validity();
72✔
442
    let indices_offset = I::from(indices_offset).vortex_expect("indices_offset out of range");
72✔
443

444
    let (values_indices, new_indices): (BufferMut<u64>, BufferMut<u64>) = take_indices
72✔
445
        .as_slice::<T>()
72✔
446
        .iter()
72✔
447
        .enumerate()
72✔
448
        .filter_map(|(i, &v)| {
252✔
449
            I::from(v)
252✔
450
                .and_then(|v| {
252✔
451
                    // If we have to take nulls the take index doesn't matter, make it 0 for consistency
452
                    if include_nulls && take_indices_validity.is_null(i).vortex_unwrap() {
252✔
453
                        Some(0)
×
454
                    } else {
455
                        indices
252✔
456
                            .search_sorted(&(v + indices_offset), SearchSortedSide::Left)
252✔
457
                            .to_found()
252✔
458
                            .map(|patch_idx| patch_idx as u64)
252✔
459
                    }
460
                })
252✔
461
                .map(|patch_idx| (patch_idx, i as u64))
252✔
462
        })
252✔
463
        .unzip();
72✔
464

465
    if new_indices.is_empty() {
72✔
466
        return Ok(None);
×
467
    }
72✔
468

469
    let new_indices = new_indices.into_array();
72✔
470
    let values_validity = take_indices_validity.take(&new_indices)?;
72✔
471
    Ok(Some((
72✔
472
        new_indices,
72✔
473
        PrimitiveArray::new(values_indices, values_validity).into_array(),
72✔
474
    )))
72✔
475
}
72✔
476

477
fn take_map<I: NativePType + Hash + Eq + TryFrom<usize>, T: NativePType>(
397✔
478
    indices: &[I],
397✔
479
    take_indices: PrimitiveArray,
397✔
480
    indices_offset: usize,
397✔
481
    min_index: usize,
397✔
482
    max_index: usize,
397✔
483
    include_nulls: bool,
397✔
484
) -> VortexResult<Option<(ArrayRef, ArrayRef)>>
397✔
485
where
397✔
486
    usize: TryFrom<T>,
397✔
487
    VortexError: From<<I as TryFrom<usize>>::Error>,
397✔
488
{
489
    let take_indices_validity = take_indices.validity();
397✔
490
    let take_indices = take_indices.as_slice::<T>();
397✔
491
    let offset_i = I::try_from(indices_offset)?;
397✔
492

493
    let sparse_index_to_value_index: HashMap<I, usize> = indices
397✔
494
        .iter()
397✔
495
        .copied()
397✔
496
        .map(|idx| idx - offset_i)
939✔
497
        .enumerate()
397✔
498
        .map(|(value_index, sparse_index)| (sparse_index, value_index))
939✔
499
        .collect();
397✔
500

501
    let (new_sparse_indices, value_indices): (BufferMut<u64>, BufferMut<u64>) = take_indices
397✔
502
        .iter()
397✔
503
        .copied()
397✔
504
        .map(usize::try_from)
397✔
505
        .process_results(|iter| {
397✔
506
            iter.enumerate()
397✔
507
                .filter_map(|(idx_in_take, ti)| {
1,118✔
508
                    // If we have to take nulls the take index doesn't matter, make it 0 for consistency
509
                    if include_nulls && take_indices_validity.is_null(idx_in_take).vortex_unwrap() {
1,118✔
510
                        Some((idx_in_take as u64, 0))
72✔
511
                    } else if ti < min_index || ti > max_index {
1,046✔
512
                        None
361✔
513
                    } else {
514
                        sparse_index_to_value_index
685✔
515
                            .get(
685✔
516
                                &I::try_from(ti)
685✔
517
                                    .vortex_expect("take index is between min and max index"),
685✔
518
                            )
519
                            .map(|value_index| (idx_in_take as u64, *value_index as u64))
685✔
520
                    }
521
                })
1,118✔
522
                .unzip()
397✔
523
        })
397✔
524
        .map_err(|_| vortex_err!("Failed to convert index to usize"))?;
397✔
525

526
    if new_sparse_indices.is_empty() {
397✔
527
        return Ok(None);
36✔
528
    }
361✔
529

530
    let new_sparse_indices = new_sparse_indices.into_array();
361✔
531
    let values_validity = take_indices_validity.take(&new_sparse_indices)?;
361✔
532
    Ok(Some((
361✔
533
        new_sparse_indices,
361✔
534
        PrimitiveArray::new(value_indices, values_validity).into_array(),
361✔
535
    )))
361✔
536
}
397✔
537

538
/// Filter patches with the provided mask (in flattened space).
539
///
540
/// The filter mask may contain indices that are non-patched. The return value of this function
541
/// is a new set of `Patches` with the indices relative to the provided `mask` rank, and the
542
/// patch values.
543
fn filter_patches_with_mask<T: ToPrimitive + Copy + Ord>(
377✔
544
    patch_indices: &[T],
377✔
545
    offset: usize,
377✔
546
    patch_values: &dyn Array,
377✔
547
    mask_indices: &[usize],
377✔
548
) -> VortexResult<Option<Patches>> {
377✔
549
    let true_count = mask_indices.len();
377✔
550
    let mut new_patch_indices = BufferMut::<u64>::with_capacity(true_count);
377✔
551
    let mut new_mask_indices = Vec::with_capacity(true_count);
377✔
552

553
    // Attempt to move the window by `STRIDE` elements on each iteration. This assumes that
554
    // the patches are relatively sparse compared to the overall mask, and so many indices in the
555
    // mask will end up being skipped.
556
    const STRIDE: usize = 4;
557

558
    let mut mask_idx = 0usize;
377✔
559
    let mut true_idx = 0usize;
377✔
560

561
    while mask_idx < patch_indices.len() && true_idx < true_count {
317,498✔
562
        // NOTE: we are searching for overlaps between sorted, unaligned indices in `patch_indices`
563
        //  and `mask_indices`. We assume that Patches are sparse relative to the global space of
564
        //  the mask (which covers both patch and non-patch values of the parent array), and so to
565
        //  quickly jump through regions with no overlap, we attempt to move our pointers by STRIDE
566
        //  elements on each iteration. If we cannot rule out overlap due to min/max values, we
567
        //  fallback to performing a two-way iterator merge.
568
        if (mask_idx + STRIDE) < patch_indices.len() && (true_idx + STRIDE) < mask_indices.len() {
317,121✔
569
            // Load a vector of each into our registers.
570
            let left_min = patch_indices[mask_idx].to_usize().vortex_expect("left_min") - offset;
312,180✔
571
            let left_max = patch_indices[mask_idx + STRIDE]
312,180✔
572
                .to_usize()
312,180✔
573
                .vortex_expect("left_max")
312,180✔
574
                - offset;
312,180✔
575
            let right_min = mask_indices[true_idx];
312,180✔
576
            let right_max = mask_indices[true_idx + STRIDE];
312,180✔
577

578
            if left_min > right_max {
312,180✔
579
                // Advance right side
580
                true_idx += STRIDE;
30,708✔
581
                continue;
30,708✔
582
            } else if right_min > left_max {
281,472✔
583
                mask_idx += STRIDE;
4,362✔
584
                continue;
4,362✔
585
            } else {
277,110✔
586
                // Fallthrough to direct comparison path.
277,110✔
587
            }
277,110✔
588
        }
4,941✔
589

590
        // Two-way sorted iterator merge:
591

592
        let left = patch_indices[mask_idx].to_usize().vortex_expect("left") - offset;
282,051✔
593
        let right = mask_indices[true_idx];
282,051✔
594

595
        match left.cmp(&right) {
282,051✔
596
            Ordering::Less => {
120,809✔
597
                mask_idx += 1;
120,809✔
598
            }
120,809✔
599
            Ordering::Greater => {
157,384✔
600
                true_idx += 1;
157,384✔
601
            }
157,384✔
602
            Ordering::Equal => {
3,858✔
603
                // Save the mask index as well as the positional index.
3,858✔
604
                new_mask_indices.push(mask_idx);
3,858✔
605
                new_patch_indices.push(true_idx as u64);
3,858✔
606

3,858✔
607
                mask_idx += 1;
3,858✔
608
                true_idx += 1;
3,858✔
609
            }
3,858✔
610
        }
611
    }
612

613
    if new_mask_indices.is_empty() {
377✔
614
        return Ok(None);
24✔
615
    }
353✔
616

617
    let new_patch_indices = new_patch_indices.into_array();
353✔
618
    let new_patch_values = filter(
353✔
619
        patch_values,
353✔
620
        &Mask::from_indices(patch_values.len(), new_mask_indices),
353✔
UNCOV
621
    )?;
×
622

623
    Ok(Some(Patches::new(
353✔
624
        true_count,
353✔
625
        0,
353✔
626
        new_patch_indices,
353✔
627
        new_patch_values,
353✔
628
    )))
353✔
629
}
377✔
630

631
#[cfg(test)]
632
mod test {
633
    use rstest::{fixture, rstest};
634
    use vortex_buffer::buffer;
635
    use vortex_mask::Mask;
636

637
    use crate::arrays::PrimitiveArray;
638
    use crate::patches::Patches;
639
    use crate::search_sorted::{SearchResult, SearchSortedSide};
640
    use crate::validity::Validity;
641
    use crate::{IntoArray, ToCanonical};
642

643
    #[test]
644
    fn test_filter() {
1✔
645
        let patches = Patches::new(
1✔
646
            100,
647
            0,
648
            buffer![10u32, 11, 20].into_array(),
1✔
649
            buffer![100, 110, 200].into_array(),
1✔
650
        );
651

652
        let filtered = patches
1✔
653
            .filter(&Mask::from_indices(100, vec![10, 20, 30]))
1✔
654
            .unwrap()
1✔
655
            .unwrap();
1✔
656

657
        let indices = filtered.indices().to_primitive().unwrap();
1✔
658
        let values = filtered.values().to_primitive().unwrap();
1✔
659
        assert_eq!(indices.as_slice::<u64>(), &[0, 1]);
1✔
660
        assert_eq!(values.as_slice::<i32>(), &[100, 200]);
1✔
661
    }
1✔
662

663
    #[fixture]
664
    fn patches() -> Patches {
665
        Patches::new(
666
            20,
667
            0,
668
            buffer![2u64, 9, 15].into_array(),
669
            PrimitiveArray::new(buffer![33_i32, 44, 55], Validity::AllValid).into_array(),
670
        )
671
    }
672

673
    #[rstest]
674
    fn search_larger_than(patches: Patches) {
675
        let res = patches.search_sorted(66, SearchSortedSide::Left).unwrap();
676
        assert_eq!(res, SearchResult::NotFound(16));
677
    }
678

679
    #[rstest]
680
    fn search_less_than(patches: Patches) {
681
        let res = patches.search_sorted(22, SearchSortedSide::Left).unwrap();
682
        assert_eq!(res, SearchResult::NotFound(2));
683
    }
684

685
    #[rstest]
686
    fn search_found(patches: Patches) {
687
        let res = patches.search_sorted(44, SearchSortedSide::Left).unwrap();
688
        assert_eq!(res, SearchResult::Found(9));
689
    }
690

691
    #[rstest]
692
    fn search_not_found_right(patches: Patches) {
693
        let res = patches.search_sorted(56, SearchSortedSide::Right).unwrap();
694
        assert_eq!(res, SearchResult::NotFound(16));
695
    }
696

697
    #[rstest]
698
    fn search_sliced(patches: Patches) {
699
        let sliced = patches.slice(7, 20).unwrap().unwrap();
700
        assert_eq!(
701
            sliced.search_sorted(22, SearchSortedSide::Left).unwrap(),
702
            SearchResult::NotFound(2)
703
        );
704
    }
705

706
    #[test]
707
    fn search_right() {
1✔
708
        let patches = Patches::new(
1✔
709
            6,
710
            0,
711
            buffer![0u8, 1, 4, 5].into_array(),
1✔
712
            buffer![-128i8, -98, 8, 50].into_array(),
1✔
713
        );
714

715
        assert_eq!(
1✔
716
            patches.search_sorted(-98, SearchSortedSide::Right).unwrap(),
1✔
717
            SearchResult::Found(2)
718
        );
719
        assert_eq!(
1✔
720
            patches.search_sorted(50, SearchSortedSide::Right).unwrap(),
1✔
721
            SearchResult::Found(6),
722
        );
723
        assert_eq!(
1✔
724
            patches.search_sorted(7, SearchSortedSide::Right).unwrap(),
1✔
725
            SearchResult::NotFound(2),
726
        );
727
        assert_eq!(
1✔
728
            patches.search_sorted(51, SearchSortedSide::Right).unwrap(),
1✔
729
            SearchResult::NotFound(6)
730
        );
731
    }
1✔
732

733
    #[test]
734
    fn search_left() {
1✔
735
        let patches = Patches::new(
1✔
736
            20,
737
            0,
738
            buffer![0u64, 1, 17, 18, 19].into_array(),
1✔
739
            buffer![11i32, 22, 33, 44, 55].into_array(),
1✔
740
        );
741
        assert_eq!(
1✔
742
            patches.search_sorted(30, SearchSortedSide::Left).unwrap(),
1✔
743
            SearchResult::NotFound(2)
744
        );
745
        assert_eq!(
1✔
746
            patches.search_sorted(54, SearchSortedSide::Left).unwrap(),
1✔
747
            SearchResult::NotFound(19)
748
        );
749
    }
1✔
750

751
    #[rstest]
752
    fn take_wit_nulls(patches: Patches) {
753
        let taken = patches
754
            .take(
755
                &PrimitiveArray::new(buffer![9, 0], Validity::from_iter(vec![true, false]))
756
                    .into_array(),
757
            )
758
            .unwrap()
759
            .unwrap();
760
        let primitive_values = taken.values().to_primitive().unwrap();
761
        assert_eq!(taken.array_len(), 2);
762
        assert_eq!(primitive_values.as_slice::<i32>(), [44]);
763
        assert_eq!(
764
            primitive_values.validity_mask().unwrap(),
765
            Mask::from_iter(vec![true])
766
        );
767
    }
768

769
    #[test]
770
    fn test_slice() {
1✔
771
        let values = buffer![15_u32, 135, 13531, 42].into_array();
1✔
772
        let indices = buffer![10_u64, 11, 50, 100].into_array();
1✔
773

774
        let patches = Patches::new(101, 0, indices, values);
1✔
775

776
        let sliced = patches.slice(15, 100).unwrap().unwrap();
1✔
777
        assert_eq!(sliced.array_len(), 100 - 15);
1✔
778
        let primitive = sliced.values().to_primitive().unwrap();
1✔
779

780
        assert_eq!(primitive.as_slice::<u32>(), &[13531]);
1✔
781
    }
1✔
782

783
    #[test]
784
    fn doubly_sliced() {
1✔
785
        let values = buffer![15_u32, 135, 13531, 42].into_array();
1✔
786
        let indices = buffer![10_u64, 11, 50, 100].into_array();
1✔
787

788
        let patches = Patches::new(101, 0, indices, values);
1✔
789

790
        let sliced = patches.slice(15, 100).unwrap().unwrap();
1✔
791
        assert_eq!(sliced.array_len(), 100 - 15);
1✔
792
        let primitive = sliced.values().to_primitive().unwrap();
1✔
793

794
        assert_eq!(primitive.as_slice::<u32>(), &[13531]);
1✔
795

796
        let doubly_sliced = sliced.slice(35, 36).unwrap().unwrap();
1✔
797
        let primitive_doubly_sliced = doubly_sliced.values().to_primitive().unwrap();
1✔
798

799
        assert_eq!(primitive_doubly_sliced.as_slice::<u32>(), &[13531]);
1✔
800
    }
1✔
801
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc