Skip to content

Commit f044ef9

Browse files
authored
Feature: Add FixedSizeListArray and FixedSizeListVTable (#4405)
Tracking Issue: #4372 Implements `FixedSizeListArray` and `FixedSizeListVTable` and adds `Canonical::FixedSizeList`. Additonally adds 33 tests for fixed size list, mostly because we allow the possibility for degenerate fixed-size list array where each list scalar has size 0 (and thus no actual data is stored unless the validity is an array) ### Notes I decided to split out the different `VTable` traits into separate modules under a `vtable` folder. I know that this is different from the rest of the codebase, but I would argue that this makes much more sense than having a subset of these files and add different vtable implementations under different file names (for example, `serde.rs` having both `SerdeVTable` implementation as well as `VisitorVTable`). I would go as far to say that we should just refactor every array module in `vortex-array` to split each trait implementation into a different file. --------- Signed-off-by: Connor Tsui <[email protected]>
1 parent 4c51c78 commit f044ef9

21 files changed

Lines changed: 1676 additions & 30 deletions

File tree

Lines changed: 193 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,193 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
use std::sync::Arc;
5+
6+
use vortex_dtype::DType;
7+
use vortex_error::{VortexExpect, VortexResult, vortex_ensure};
8+
9+
use crate::stats::ArrayStats;
10+
use crate::validity::Validity;
11+
use crate::{Array, ArrayRef};
12+
13+
mod vtable;
14+
pub use vtable::{FixedSizeListEncoding, FixedSizeListVTable};
15+
16+
#[cfg(test)]
17+
mod tests;
18+
19+
/// The canonical encoding for fixed-size list arrays.
20+
#[derive(Clone, Debug)]
21+
pub struct FixedSizeListArray {
22+
/// The [`DType`] of the fixed-size list.
23+
///
24+
/// This type **must** be the variant [`DType::FixedSizeList`].
25+
dtype: DType,
26+
27+
/// The `elements` data array, where each fixed-size list scalar is a _slice_ of the `elements`
28+
/// array, and each inner list element is a _scalar_ of the `elements` array.
29+
///
30+
/// The fixed-size list scalars (or the elements of the array) are contiguous (regardless of
31+
/// nullability for easy lookups), each with equal size in memory.
32+
elements: ArrayRef,
33+
34+
/// The size of each fixed-size list scalar in the array.
35+
///
36+
/// We store the size of each fixed-size list in the array as a field for convenience.
37+
list_size: u32,
38+
39+
/// The validity / null map of the array.
40+
///
41+
/// Note that this null map refers to the fixed-size list scalars, **not** the elements of the
42+
/// _individual_ fixed-size list scalars. The `elements` array will track individual value
43+
/// nullability.
44+
validity: Validity,
45+
46+
/// The length of the array.
47+
///
48+
/// Note that this is different from the size of each fixed-size list scalar (`list_size`).
49+
///
50+
/// The main reason we need to store this (rather than calculate it on the fly via `list_size`
51+
/// and `elements.len()`) is because in the degenerate case where `list_size == 0`, we cannot
52+
/// use `0 / 0` to determine the length.
53+
len: usize,
54+
55+
/// The stats for this array.
56+
stats_set: ArrayStats,
57+
}
58+
59+
impl FixedSizeListArray {
60+
/// Creates a new `FixedSizeListArray`. This is simply a wrapper around [`try_new()`].
61+
///
62+
/// # Panics
63+
///
64+
/// Panics if the inputs are invalid. See
65+
///
66+
/// [`try_new()`]: Self::try_new
67+
pub fn new(elements: ArrayRef, list_size: u32, validity: Validity, len: usize) -> Self {
68+
Self::try_new(elements, list_size, validity, len)
69+
.vortex_expect("FixedSizeListArray `try_new` failed")
70+
}
71+
72+
/// Attempts to create a new `FixedSizeListArray`.
73+
///
74+
/// # Errors
75+
///
76+
/// Returns an error if the inputs are invalid. The inputs are **valid** if:
77+
///
78+
/// - The `list_size` is 0 and:
79+
/// - The `elements` array is empty.
80+
/// - The `len` is equal to the length of the `validity` map.
81+
/// - The length of the `elements` array is a multiple of the size of the fixed-size lists
82+
/// (`list_size`).
83+
/// - The `Validity` length (if it exists) times the `list_size` is equal to the length of the
84+
/// `elements` (or put another way, the length of the array divided by the size of each
85+
/// fixed-size list is equal to the length of the validity).
86+
pub fn try_new(
87+
elements: ArrayRef,
88+
list_size: u32,
89+
validity: Validity,
90+
len: usize,
91+
) -> VortexResult<Self> {
92+
Self::validate(&elements, len, list_size, &validity)?;
93+
94+
// SAFETY: we validate that the inputs are valid above.
95+
Ok(unsafe { Self::new_unchecked(elements, list_size, validity, len) })
96+
}
97+
98+
/// Creates a new `FixedSizeListArray`, assuming that the caller has validated the inputs.
99+
///
100+
/// # Safety
101+
///
102+
/// This function is only safe to call if the inputs are valid. See [`try_new()`] for more
103+
/// details on what the validity requirements are.
104+
///
105+
/// [`try_new()`]: Self::try_new
106+
pub unsafe fn new_unchecked(
107+
elements: ArrayRef,
108+
list_size: u32,
109+
validity: Validity,
110+
len: usize,
111+
) -> Self {
112+
let nullability = validity.nullability();
113+
114+
Self {
115+
dtype: DType::FixedSizeList(Arc::new(elements.dtype().clone()), list_size, nullability),
116+
elements,
117+
list_size,
118+
validity,
119+
len,
120+
stats_set: Default::default(),
121+
}
122+
}
123+
124+
/// Returns the elements array.
125+
pub fn elements(&self) -> &ArrayRef {
126+
&self.elements
127+
}
128+
129+
/// The size of each fixed-size list scalar in the array.
130+
pub const fn list_size(&self) -> u32 {
131+
self.list_size
132+
}
133+
134+
/// Returns the elements at the given index from the list array.
135+
///
136+
/// # Panics
137+
///
138+
/// Panics if the index is out of bounds.
139+
pub fn fixed_size_list_at(&self, index: usize) -> ArrayRef {
140+
debug_assert!(
141+
index < self.len,
142+
"index out of bounds: the len is {} but the index is {index}",
143+
self.len
144+
);
145+
debug_assert!(
146+
self.validity
147+
.is_valid(index)
148+
.vortex_expect("this shouldn't be a result in the first place")
149+
);
150+
151+
let start = self.list_size as usize * index;
152+
let end = self.list_size as usize * (index + 1);
153+
self.elements().slice(start..end)
154+
}
155+
156+
/// Checks if the components of a `FixedSizeListArray` are valid.
157+
///
158+
/// See [`try_new()`](Self::try_new) for the validation semantics.
159+
fn validate(
160+
elements: &dyn Array,
161+
len: usize,
162+
list_size: u32,
163+
validity: &Validity,
164+
) -> VortexResult<()> {
165+
// A fixed-size list array where each list scalar is empty is completely useless, but we can
166+
// support it regardless.
167+
if list_size == 0 {
168+
vortex_ensure!(
169+
elements.is_empty() && validity.maybe_len().is_none_or(|vlen| vlen == len),
170+
"an empty `FixedSizeList` should have no elements"
171+
);
172+
return Ok(());
173+
}
174+
175+
let num_elements = elements.len();
176+
177+
vortex_ensure!(
178+
len * list_size as usize == num_elements,
179+
"the `elements` array has the incorrect number of elements to construct a \
180+
`FixedSizeList[{list_size}] array of length {len}",
181+
);
182+
183+
// If a validity array is present, it must be the same length as the fixed-size list array.
184+
if let Some(validity_len) = validity.maybe_len() {
185+
vortex_ensure!(
186+
len == validity_len,
187+
"validity with size {validity_len} does not match fixed-size list array size {len}",
188+
);
189+
}
190+
191+
Ok(())
192+
}
193+
}
Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
use std::sync::Arc;
5+
6+
use vortex_dtype::{DType, Nullability, PType};
7+
use vortex_scalar::Scalar;
8+
9+
use crate::arrays::{FixedSizeListArray, PrimitiveArray};
10+
use crate::validity::Validity;
11+
use crate::{Array, IntoArray};
12+
13+
#[test]
14+
fn test_basic_fixed_size_list() {
15+
let len = 4;
16+
let list_size = 3;
17+
18+
// Create a FSL of size 3 with 4 lists: [[1,2,3], [4,5,6], [7,8,9], [10,11,12]].
19+
let elements = PrimitiveArray::from_iter([1i32, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]);
20+
let fsl = FixedSizeListArray::new(elements.into_array(), list_size, Validity::NonNullable, len);
21+
22+
assert_eq!(fsl.len(), len);
23+
assert_eq!(fsl.list_size(), list_size);
24+
assert_eq!(fsl.elements().len(), (len * list_size as usize));
25+
26+
// Check the dtype.
27+
assert!(matches!(
28+
fsl.dtype(),
29+
DType::FixedSizeList(elem_dtype, 3, Nullability::NonNullable)
30+
if matches!(elem_dtype.as_ref(), DType::Primitive(PType::I32, Nullability::NonNullable))
31+
));
32+
}
33+
34+
#[test]
35+
fn test_scalar_at() {
36+
let len = 2;
37+
let list_size = 3;
38+
39+
let elements = PrimitiveArray::from_iter([1i32, 2, 3, 4, 5, 6]);
40+
let fsl = FixedSizeListArray::new(elements.into_array(), list_size, Validity::NonNullable, len);
41+
42+
// First list: [1, 2, 3].
43+
let first = fsl.scalar_at(0);
44+
assert_eq!(
45+
first,
46+
Scalar::fixed_size_list(
47+
Arc::new(PType::I32.into()),
48+
vec![1i32.into(), 2i32.into(), 3i32.into()],
49+
Nullability::NonNullable,
50+
)
51+
);
52+
53+
// Second list: [4, 5, 6].
54+
let second = fsl.scalar_at(1);
55+
assert_eq!(
56+
second,
57+
Scalar::fixed_size_list(
58+
Arc::new(PType::I32.into()),
59+
vec![4i32.into(), 5i32.into(), 6i32.into()],
60+
Nullability::NonNullable,
61+
)
62+
);
63+
}
64+
65+
#[test]
66+
fn test_fixed_size_list_at() {
67+
let len = 3;
68+
let list_size = 2;
69+
70+
let elements = PrimitiveArray::from_iter([1.0f64, 2.0, 3.0, 4.0, 5.0, 6.0]);
71+
let fsl = FixedSizeListArray::new(elements.into_array(), list_size, Validity::AllValid, len);
72+
73+
// Get the first list [1.0, 2.0].
74+
let first_list = fsl.fixed_size_list_at(0);
75+
assert_eq!(first_list.len(), list_size as usize);
76+
assert_eq!(first_list.scalar_at(0), 1.0f64.into());
77+
assert_eq!(first_list.scalar_at(1), 2.0f64.into());
78+
79+
// Get the third list [5.0, 6.0].
80+
let third_list = fsl.fixed_size_list_at(2);
81+
assert_eq!(third_list.len(), list_size as usize);
82+
assert_eq!(third_list.scalar_at(0), 5.0f64.into());
83+
assert_eq!(third_list.scalar_at(1), 6.0f64.into());
84+
}
85+
86+
#[test]
87+
fn test_validation_error_length_mismatch() {
88+
let len = 2;
89+
let list_size = 3;
90+
91+
// Elements length is not a multiple of list_size.
92+
let elements = PrimitiveArray::from_iter([1i32, 2, 3, 4, 5]);
93+
let result = FixedSizeListArray::try_new(
94+
elements.into_array(),
95+
list_size, // List size is 3, but we have 5 elements (not enough for 2 complete lists).
96+
Validity::NonNullable,
97+
len, // Claiming 2 lists would need 6 elements.
98+
);
99+
100+
assert!(result.is_err());
101+
let err = result.unwrap_err();
102+
assert!(err.to_string().contains("incorrect number of elements"));
103+
}
104+
105+
#[test]
106+
fn test_validation_error_validity_length() {
107+
let len = 3;
108+
let list_size = 2;
109+
110+
let elements = PrimitiveArray::from_iter([1i32, 2, 3, 4, 5, 6]);
111+
112+
// Create a validity array with wrong length.
113+
let validity = Validity::from_iter([true, false]); // Length 2.
114+
115+
let result = FixedSizeListArray::try_new(
116+
elements.into_array(),
117+
list_size,
118+
validity,
119+
len, // Array length is 3, but validity has length 2.
120+
);
121+
122+
assert!(result.is_err());
123+
let err = result.unwrap_err();
124+
assert!(err.to_string().contains("does not match"));
125+
}

0 commit comments

Comments
 (0)