Skip to content

Commit 49f98c3

Browse files
robert3005claude
andauthored
Constrain List/ListView builder offset, size types to 32 and 64 bit types (#9053)
In #8609 we have inverted the flow of the append_to_builder methods. The side effect of that is we match on the builders but for lists the number of match cases is excessive due to trait bounds being arbitrary integer types. Realistically types smaller than u32 are not that useful as they define the upper bound on the size of the array. This pr introduces `OffsetBuilderPType` which constraints the offset and sizes buffer types in ListBuilder. We will use that on VarBinBuilder in a follow up --------- Signed-off-by: Claude <[email protected]> Co-authored-by: Claude <[email protected]>
1 parent a6b4527 commit 49f98c3

10 files changed

Lines changed: 398 additions & 261 deletions

File tree

‎encodings/sparse/src/canonical.rs‎

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -39,12 +39,13 @@ use vortex_array::dtype::IntegerPType;
3939
use vortex_array::dtype::NativeDecimalType;
4040
use vortex_array::dtype::NativePType;
4141
use vortex_array::dtype::Nullability;
42+
use vortex_array::dtype::OffsetBuilderPType;
4243
use vortex_array::dtype::StructFields;
4344
use vortex_array::match_each_decimal_value_type;
4445
use vortex_array::match_each_integer_ptype;
4546
use vortex_array::match_each_native_ptype;
4647
use vortex_array::match_each_unsigned_integer_ptype;
47-
use vortex_array::match_smallest_offset_type;
48+
use vortex_array::match_smallest_list_offset_type;
4849
use vortex_array::patches::Patches;
4950
use vortex_array::scalar::DecimalScalar;
5051
use vortex_array::scalar::ListScalar;
@@ -175,7 +176,7 @@ fn execute_sparse_lists(
175176
ctx: &mut ExecutionCtx,
176177
) -> VortexResult<ArrayRef> {
177178
// Patch indices are non-negative; reinterpret to unsigned so this dispatches over 4 widths
178-
// instead of 8. `O` is already unsigned (from `match_smallest_offset_type`).
179+
// instead of 8. `O` is already unsigned (from `match_smallest_list_offset_type`).
179180
let indices = resolved.indices().as_::<Primitive>().into_owned();
180181
let indices = indices.reinterpret_cast(indices.ptype().to_unsigned());
181182
let values = resolved.values().as_::<ListView>().into_owned();
@@ -185,7 +186,7 @@ fn execute_sparse_lists(
185186
let total_canonical_values = values.elements().len() + fill_list.len() * n_filled;
186187

187188
Ok(match_each_unsigned_integer_ptype!(indices.ptype(), |I| {
188-
match_smallest_offset_type!(total_canonical_values, |O| {
189+
match_smallest_list_offset_type!(total_canonical_values, |O| {
189190
execute_sparse_lists_inner::<I, O>(
190191
indices.as_slice(),
191192
values,
@@ -201,7 +202,7 @@ fn execute_sparse_lists(
201202
}
202203

203204
#[expect(clippy::too_many_arguments)]
204-
fn execute_sparse_lists_inner<I: IntegerPType, O: IntegerPType>(
205+
fn execute_sparse_lists_inner<I: IntegerPType, O: OffsetBuilderPType>(
205206
patch_indices: &[I],
206207
patch_values: ListViewArray,
207208
fill_scalar: ListScalar,
@@ -371,7 +372,7 @@ fn list_scalar_elements_array(list: ListScalar) -> Option<ArrayRef> {
371372
})
372373
}
373374

374-
fn append_list_fill<O: IntegerPType, S: IntegerPType>(
375+
fn append_list_fill<O: OffsetBuilderPType, S: OffsetBuilderPType>(
375376
builder: &mut ListViewBuilder<O, S>,
376377
fill_elements: Option<&ArrayRef>,
377378
count: usize,
@@ -1566,15 +1567,17 @@ mod test {
15661567
expected_elements.extend(buffer![42i32; 252]);
15671568
let expected = ListArray::try_new(
15681569
expected_elements.freeze().into_array(),
1569-
buffer![0u16, 1, 2, 3, 4, 256].into_array(),
1570+
buffer![0u32, 1, 2, 3, 4, 256].into_array(),
15701571
Validity::AllValid,
15711572
)?
15721573
.into_array();
15731574

1575+
// The canonical offsets outgrow the source's u8 offsets; u32 is the smallest offset type
1576+
// a list builder can produce (see `OffsetBuilderPType`).
15741577
let actual_listview = actual.clone().execute::<ListViewArray>(&mut ctx)?;
15751578
assert_eq!(
15761579
actual_listview.offsets().dtype(),
1577-
&DType::Primitive(PType::U16, NonNullable)
1580+
&DType::Primitive(PType::U32, NonNullable)
15781581
);
15791582
assert_arrays_eq!(&actual, &expected, &mut ctx);
15801583

‎vortex-array/src/arrays/arbitrary.rs‎

Lines changed: 6 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ use crate::dtype::DType;
3232
use crate::dtype::IntegerPType;
3333
use crate::dtype::NativePType;
3434
use crate::dtype::Nullability;
35+
use crate::dtype::OffsetBuilderPType;
3536
use crate::dtype::PType;
3637
use crate::match_each_decimal_value_type;
3738
use crate::scalar::Scalar;
@@ -238,17 +239,11 @@ fn random_list(
238239
// Worst-case total elements: each list can have up to 20 elements.
239240
let max_total_elements = array_length as u64 * 20;
240241

241-
match u.int_in_range(0..=5)? {
242-
0 if i16::max_value_as_u64() >= max_total_elements => {
243-
random_list_with_offset_type::<i16>(u, elem_dtype, null, array_length)
244-
}
245-
1 if i32::max_value_as_u64() >= max_total_elements => {
242+
match u.int_in_range(0..=3)? {
243+
0 if i32::max_value_as_u64() >= max_total_elements => {
246244
random_list_with_offset_type::<i32>(u, elem_dtype, null, array_length)
247245
}
248-
3 if u16::max_value_as_u64() >= max_total_elements => {
249-
random_list_with_offset_type::<u16>(u, elem_dtype, null, array_length)
250-
}
251-
4 if u32::max_value_as_u64() >= max_total_elements => {
246+
1 if u32::max_value_as_u64() >= max_total_elements => {
252247
random_list_with_offset_type::<u32>(u, elem_dtype, null, array_length)
253248
}
254249
// i64 and u64 always fit; also the fallback for when narrower types don't.
@@ -262,8 +257,8 @@ fn random_list(
262257
}
263258
}
264259

265-
/// Creates a random list array with the given [`IntegerPType`] for the internal offsets child.
266-
fn random_list_with_offset_type<O: IntegerPType>(
260+
/// Creates a random list array with the given [`OffsetBuilderPType`] for the internal offsets child.
261+
fn random_list_with_offset_type<O: OffsetBuilderPType>(
267262
u: &mut Unstructured,
268263
elem_dtype: &Arc<DType>,
269264
null: Nullability,

‎vortex-array/src/arrays/list/test_harness.rs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,14 +10,14 @@ use crate::arrays::ListArray;
1010
use crate::builders::ArrayBuilder;
1111
use crate::builders::ListBuilder;
1212
use crate::dtype::DType;
13-
use crate::dtype::IntegerPType;
13+
use crate::dtype::OffsetBuilderPType;
1414
use crate::scalar::Scalar;
1515

1616
impl ListArray {
1717
/// This is a convenience method to create a list array from an iterator of iterators.
1818
/// This method is slow however since each element is first converted to a scalar and then
1919
/// appended to the array.
20-
pub fn from_iter_slow<O: IntegerPType, I: IntoIterator>(
20+
pub fn from_iter_slow<O: OffsetBuilderPType, I: IntoIterator>(
2121
iter: I,
2222
dtype: Arc<DType>,
2323
) -> VortexResult<ListArray>
@@ -44,7 +44,7 @@ impl ListArray {
4444
Ok(builder.finish_into_list())
4545
}
4646

47-
pub fn from_iter_opt_slow<O: IntegerPType, I: IntoIterator<Item = Option<T>>, T>(
47+
pub fn from_iter_opt_slow<O: OffsetBuilderPType, I: IntoIterator<Item = Option<T>>, T>(
4848
iter: I,
4949
dtype: Arc<DType>,
5050
) -> VortexResult<ListArray>

‎vortex-array/src/arrays/list/vtable/mod.rs‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@ use crate::builders::ArrayBuilder;
3636
use crate::dtype::DType;
3737
use crate::dtype::Nullability;
3838
use crate::dtype::PType;
39+
use crate::match_each_list_builder;
3940
use crate::serde::ArrayChildren;
4041
use crate::validity::Validity;
4142
mod operations;
@@ -199,12 +200,21 @@ impl VTable for List {
199200
))
200201
}
201202

203+
// The complexity comes from the expansion of `match_each_list_builder!`.
204+
#[expect(clippy::cognitive_complexity)]
202205
fn append_to_builder(
203206
array: ArrayView<'_, Self>,
204207
builder: &mut dyn ArrayBuilder,
205208
ctx: &mut ExecutionCtx,
206209
) -> VortexResult<()> {
207-
builder.append_list_array(array, ctx)
210+
match match_each_list_builder!(&mut *builder, |b| b.append_list_array(array, ctx)) {
211+
Some(result) => result,
212+
None => vortex_bail!(
213+
"cannot append a List array of dtype {} to a {} builder",
214+
array.dtype(),
215+
builder.dtype()
216+
),
217+
}
208218
}
209219
}
210220

‎vortex-array/src/arrays/listview/vtable/mod.rs‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@ use crate::builders::ArrayBuilder;
3535
use crate::dtype::DType;
3636
use crate::dtype::Nullability;
3737
use crate::dtype::PType;
38+
use crate::match_each_list_builder;
3839
use crate::serde::ArrayChildren;
3940
use crate::validity::Validity;
4041
mod kernel;
@@ -223,12 +224,21 @@ impl VTable for ListView {
223224
Ok(ExecutionResult::done(array))
224225
}
225226

227+
// The complexity comes from the expansion of `match_each_list_builder!`.
228+
#[expect(clippy::cognitive_complexity)]
226229
fn append_to_builder(
227230
array: ArrayView<'_, Self>,
228231
builder: &mut dyn ArrayBuilder,
229232
ctx: &mut ExecutionCtx,
230233
) -> VortexResult<()> {
231-
builder.append_listview_array(array, ctx)
234+
match match_each_list_builder!(&mut *builder, |b| b.append_listview_array(array, ctx)) {
235+
Some(result) => result,
236+
None => vortex_bail!(
237+
"cannot append a ListView array of dtype {} to a {} builder",
238+
array.dtype(),
239+
builder.dtype()
240+
),
241+
}
232242
}
233243

234244
fn reduce_parent(

0 commit comments

Comments
 (0)