Skip to content

Commit bc58587

Browse files
authored
Require strictly increasing patch indices (#11181)
## Summary `Patches::new` now checks, in debug builds, that patch indices are strictly increasing instead of only sorted. Nothing in the workspace produces repeated indices; only hand-built tests did. The paths that handle them also disagree: `search_index` returns the first patch at a repeated index, while decoding keeps the last. ## Changes - `Patches::new` asserts `is_strict_sorted`; the `new_unchecked` safety contract says "strictly increasing". - Remove the repeated-index handling: the last-wins skip in `append_patch_walk_to_varbin`, and the repeated-position checks in `execute_sparse_lists` and `lists::can_use_native_list`. - Remove `test_append_utf8_with_duplicate_patch_indices` and the `repeated_position` cases from the sparse list tests added in #11173; add `test_new_rejects_repeated_indices`. ## Testing - `test_new_rejects_repeated_indices` (debug builds only). --------- Signed-off-by: Matt Katz <[email protected]>
1 parent 22e02f1 commit bc58587

5 files changed

Lines changed: 55 additions & 121 deletions

File tree

‎encodings/sparse/src/canonical.rs‎

Lines changed: 2 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -243,11 +243,6 @@ where
243243
let mut previous = 0usize;
244244
for (patch, row) in indices.iter().enumerate() {
245245
let row = AsPrimitive::<usize>::as_(*row);
246-
// The canonical decode scatters the patches in order, so of duplicate indices the
247-
// last one wins; skip a patch that the next one lands on top of.
248-
if patch + 1 < indices.len() && AsPrimitive::<usize>::as_(indices[patch + 1]) == row {
249-
continue;
250-
}
251246
vortex_ensure!(
252247
previous <= row && row < len,
253248
"Sparse patch indices must be ascending within the array length {len}"
@@ -393,16 +388,9 @@ fn execute_sparse_lists(
393388
.rebuild(ListViewRebuildMode::MakeExact, ctx)?;
394389

395390
// Keep the builder for at most one valid list: there is no repeated element gather to
396-
// avoid, and constructing run-end offsets would add setup work. Duplicate positions still
397-
// need the metadata path to preserve last-patch-wins semantics.
391+
// avoid, and constructing run-end offsets would add setup work.
398392
let patch_validity = values.listview_validity().execute_mask(values.len(), ctx)?;
399-
let use_shared_elements = patch_validity.true_count() > 1
400-
|| match_each_unsigned_integer_ptype!(indices.ptype(), |I| {
401-
indices
402-
.as_slice::<I>()
403-
.windows(2)
404-
.any(|pair| pair[0] == pair[1])
405-
});
393+
let use_shared_elements = patch_validity.true_count() > 1;
406394

407395
// Null lists also have no elements, so null and empty fills take the same path.
408396
if fill_list.is_empty() && use_shared_elements {

‎encodings/sparse/src/canonical/lists/mod.rs‎

Lines changed: 8 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ pub(super) fn empty_fill(
4444
.execute::<PrimitiveArray>(ctx)?;
4545
let positions = positions.as_slice::<u64>();
4646

47-
if !can_use_native_list(positions, &values)? {
47+
if !can_use_native_list(&values)? {
4848
return empty_fill_as_views(patches, values, fill, len, nullability, ctx);
4949
}
5050

@@ -85,21 +85,18 @@ pub(super) fn empty_fill(
8585
)
8686
}
8787

88-
/// Checks the two cases where the patch layout needs independent starting offsets and sizes.
89-
fn can_use_native_list(positions: &[u64], values: &ListViewArray) -> VortexResult<bool> {
88+
/// Checks whether the patch layout's terminal offset fits a native List's offsets.
89+
fn can_use_native_list(values: &ListViewArray) -> VortexResult<bool> {
9090
// A native List needs a terminal offset in the same type as its starting offsets. A view
9191
// can instead represent an end that exceeds that type, e.g. u8 offset 130 + size 130 = 260.
9292
let elements_len = u64::try_from(values.elements().len())
9393
.map_err(|err| vortex_err!("sparse list elements length: {err}"))?;
94-
let terminal_offset_fits = Scalar::from(elements_len)
94+
Ok(Scalar::from(elements_len)
9595
.cast(values.offsets().dtype())
96-
.is_ok();
97-
98-
// Duplicate positions require the last patch to win, rather than consuming both lists.
99-
Ok(terminal_offset_fits && positions.windows(2).all(|pair| pair[0] < pair[1]))
96+
.is_ok())
10097
}
10198

102-
/// Keeps shared elements and scatters view metadata for duplicate positions or narrow offsets.
99+
/// Keeps shared elements and scatters view metadata for narrow offsets.
103100
fn empty_fill_as_views(
104101
patches: &Patches,
105102
values: ListViewArray,
@@ -108,9 +105,8 @@ fn empty_fill_as_views(
108105
nullability: Nullability,
109106
ctx: &mut ExecutionCtx,
110107
) -> VortexResult<ArrayRef> {
111-
// Scatter starting offsets and sizes independently. Fill rows get an empty view (0, 0),
112-
// and Sparse's existing patch handling makes the last patch win at repeated positions.
113-
// Keeping these as separate arrays also avoids overflowing a narrow terminal offset.
108+
// Scatter starting offsets and sizes independently. Fill rows get an empty view (0, 0).
109+
// Keeping these as separate arrays avoids overflowing a narrow terminal offset.
114110
let offsets = values.offsets();
115111
let offsets = Sparse::try_new_from_patches(
116112
patches.clone().map_values(|_| Ok(offsets.clone()))?,

‎encodings/sparse/src/canonical/lists/tests.rs‎

Lines changed: 25 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@ use rstest::rstest;
55
use vortex_array::ArrayRef;
66
use vortex_array::IntoArray;
77
use vortex_array::VortexSessionExecute;
8-
use vortex_array::arrays::ConstantArray;
98
use vortex_array::arrays::List;
109
use vortex_array::arrays::ListArray;
1110
use vortex_array::arrays::ListViewArray;
@@ -23,10 +22,7 @@ use vortex_session::VortexSession;
2322
use crate::Sparse;
2423

2524
#[rstest]
26-
fn empty_fill_reuses_elements(
27-
#[values(false, true)] null_fill: bool,
28-
#[values(false, true)] repeated_position: bool,
29-
) -> VortexResult<()> {
25+
fn empty_fill_reuses_elements(#[values(false, true)] null_fill: bool) -> VortexResult<()> {
3026
let session = VortexSession::empty();
3127
crate::initialize(&session);
3228
let mut ctx = session.create_execution_ctx();
@@ -45,54 +41,26 @@ fn empty_fill_reuses_elements(
4541
Scalar::zero_value(lists.dtype())
4642
};
4743
let sparse = Sparse::try_new(
48-
if repeated_position {
49-
buffer![1u32, 1, 7].into_array()
50-
} else {
51-
buffer![1u32, 4, 7].into_array()
52-
},
44+
buffer![1u32, 4, 7].into_array(),
5345
lists.into_array(),
5446
10,
5547
fill,
5648
&mut ctx,
5749
)?;
5850

59-
let actual = if repeated_position {
60-
sparse
61-
.into_array()
62-
.execute::<ListViewArray>(&mut ctx)?
63-
.into_array()
64-
} else {
65-
sparse.into_array().execute_until::<List>(&mut ctx)?
66-
};
67-
68-
if let Some(list) = actual.as_opt::<List>() {
69-
assert!(ArrayRef::ptr_eq(list.elements(), &elements));
70-
assert!(list.offsets().is::<RunEnd>());
71-
} else {
72-
let view = actual.as_::<vortex_array::arrays::ListView>();
73-
assert!(ArrayRef::ptr_eq(view.elements(), &elements));
74-
assert!(view.offsets().is::<Sparse>());
75-
assert!(view.sizes().is::<Sparse>());
76-
}
51+
let actual = sparse.into_array().execute_until::<List>(&mut ctx)?;
52+
let list = actual.as_::<List>();
53+
assert!(ArrayRef::ptr_eq(list.elements(), &elements));
54+
assert!(list.offsets().is::<RunEnd>());
7755

78-
// The middle patch is null. At a repeated position it replaces the first, valid patch.
56+
// The middle patch is null.
7957
let mut validity = vec![!null_fill; 10];
80-
validity[1] = !repeated_position;
81-
if !repeated_position {
82-
validity[4] = false;
83-
}
58+
validity[1] = true;
59+
validity[4] = false;
8460
validity[7] = true;
8561
let expected = ListArray::try_new(
86-
if repeated_position {
87-
buffer![3i32].into_array()
88-
} else {
89-
buffer![1i32, 2, 3].into_array()
90-
},
91-
if repeated_position {
92-
buffer![0u32, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1].into_array()
93-
} else {
94-
buffer![0u32, 0, 2, 2, 2, 2, 2, 2, 3, 3, 3].into_array()
95-
},
62+
buffer![1i32, 2, 3].into_array(),
63+
buffer![0u32, 0, 2, 2, 2, 2, 2, 2, 3, 3, 3].into_array(),
9664
Validity::from_iter(validity),
9765
&mut ctx,
9866
)?;
@@ -143,10 +111,8 @@ fn terminal_offset_wider_than_view_offsets() -> VortexResult<()> {
143111
Ok(())
144112
}
145113

146-
#[rstest]
147-
fn single_valid_patch_with_nulls(
148-
#[values(false, true)] repeated_position: bool,
149-
) -> VortexResult<()> {
114+
#[test]
115+
fn single_valid_patch_with_nulls() -> VortexResult<()> {
150116
let session = VortexSession::empty();
151117
crate::initialize(&session);
152118
let mut ctx = session.create_execution_ctx();
@@ -160,33 +126,23 @@ fn single_valid_patch_with_nulls(
160126
)?;
161127
let fill = Scalar::null(lists.dtype().clone());
162128
let sparse = Sparse::try_new(
163-
if repeated_position {
164-
buffer![1u32, 3, 3].into_array()
165-
} else {
166-
buffer![1u32, 3, 5].into_array()
167-
},
129+
buffer![1u32, 3, 5].into_array(),
168130
lists.into_array(),
169131
7,
170-
fill.clone(),
132+
fill,
171133
&mut ctx,
172134
)?;
173135

174136
let actual = sparse.into_array().execute::<ListViewArray>(&mut ctx)?;
175-
if repeated_position {
176-
// The final null patch replaces the only valid list at row 3.
177-
assert!(actual.offsets().is::<Sparse>());
178-
assert_arrays_eq!(actual, ConstantArray::new(fill, 7), &mut ctx);
179-
} else {
180-
// A single list needs no repeated gather, and the builder remains ready for Arrow export.
181-
assert!(actual.is_zero_copy_to_list());
182-
assert!(actual.offsets().is::<vortex_array::arrays::Primitive>());
183-
let expected = ListArray::try_new(
184-
elements,
185-
buffer![0u32, 0, 0, 0, 3, 3, 3, 3].into_array(),
186-
Validity::from_iter([false, false, false, true, false, false, false]),
187-
&mut ctx,
188-
)?;
189-
assert_arrays_eq!(actual, expected, &mut ctx);
190-
}
137+
// A single list needs no repeated gather, and the builder remains ready for Arrow export.
138+
assert!(actual.is_zero_copy_to_list());
139+
assert!(actual.offsets().is::<vortex_array::arrays::Primitive>());
140+
let expected = ListArray::try_new(
141+
elements,
142+
buffer![0u32, 0, 0, 0, 3, 3, 3, 3].into_array(),
143+
Validity::from_iter([false, false, false, true, false, false, false]),
144+
&mut ctx,
145+
)?;
146+
assert_arrays_eq!(actual, expected, &mut ctx);
191147
Ok(())
192148
}

‎encodings/sparse/src/lib.rs‎

Lines changed: 0 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -980,28 +980,6 @@ mod test {
980980
assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
981981
}
982982

983-
#[test]
984-
fn test_append_utf8_with_duplicate_patch_indices() {
985-
let mut ctx = SESSION.create_execution_ctx();
986-
let values = VarBinViewArray::from_iter_str(["first", "second"]).into_array();
987-
let array = Sparse::try_new(
988-
buffer![1u8, 1].into_array(),
989-
values,
990-
2,
991-
Scalar::utf8("fill".to_string(), Nullability::NonNullable),
992-
&mut ctx,
993-
)
994-
.unwrap();
995-
let expected = VarBinViewArray::from_iter_str(["fill", "second"]).into_array();
996-
let mut builder = VarBinBuilder::<i32>::with_capacity_in(
997-
array.dtype().clone(),
998-
array.len(),
999-
vortex_buffer::BufferAllocatorRef::static_ref(),
1000-
);
1001-
array.append_to_builder(&mut builder, &mut ctx).unwrap();
1002-
assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
1003-
}
1004-
1005983
#[test]
1006984
#[should_panic]
1007985
fn test_invalid_length() {

‎vortex-array/src/patches.rs‎

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -271,10 +271,10 @@ impl Patches {
271271

272272
#[cfg(debug_assertions)]
273273
{
274-
use crate::aggregate_fn::fns::is_sorted::is_sorted;
274+
use crate::aggregate_fn::fns::is_sorted::is_strict_sorted;
275275
assert!(
276-
is_sorted(&indices, ctx).unwrap_or(false),
277-
"Patch indices must be sorted"
276+
is_strict_sorted(&indices, ctx).unwrap_or(false),
277+
"Patch indices must be strictly increasing"
278278
);
279279
}
280280
}
@@ -350,7 +350,7 @@ impl Patches {
350350
/// Users have to assert that
351351
/// * Indices and values have the same length
352352
/// * Indices is an unsigned integer type
353-
/// * Indices must be sorted
353+
/// * Indices must be strictly increasing
354354
/// * Last value in indices is smaller than array_len
355355
pub unsafe fn new_unchecked(
356356
array_len: usize,
@@ -1520,6 +1520,22 @@ mod test {
15201520
Ok(())
15211521
}
15221522

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+
15231539
#[test]
15241540
fn test_filter() {
15251541
let mut ctx = SESSION.create_execution_ctx();

0 commit comments

Comments
 (0)