use std::fmt::Debug;
use std::fmt::Display;
use std::fmt::Formatter;
use futures::stream;
use vortex_buffer::BufferMut;
use vortex_error::VortexExpect;
use vortex_error::VortexResult;
use vortex_error::vortex_bail;
use crate::ArrayRef;
use crate::ArraySlots;
use crate::Canonical;
use crate::ExecutionCtx;
use crate::IntoArray;
use crate::array::Array;
use crate::array::ArrayParts;
use crate::array::TypedArrayRef;
use crate::array_slots;
use crate::arrays::Chunked;
use crate::arrays::PrimitiveArray;
use crate::dtype::DType;
use crate::iter::ArrayIterator;
use crate::iter::ArrayIteratorAdapter;
use crate::search_sorted::SearchSorted;
use crate::search_sorted::SearchSortedSide;
use crate::stream::ArrayStream;
use crate::stream::ArrayStreamAdapter;
use crate::validity::Validity;
#[array_slots(Chunked)]
pub struct ChunkedSlots {
#[slot(0)]
pub chunk_offsets: ArrayRef,
#[slot(1..)]
pub chunks: Vec<ArrayRef>,
}
#[derive(Clone, Debug)]
pub struct ChunkedData {
pub(super) chunk_offsets: Vec<usize>,
pub(super) next_builder_slot: usize,
}
impl Display for ChunkedData {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(f, "nchunks: {}", self.chunk_offsets.len().saturating_sub(1))
}
}
pub trait ChunkedArrayExt: TypedArrayRef<Chunked> {
fn chunk_offsets_array(&self) -> &ArrayRef {
self.slots()[ChunkedSlots::CHUNK_OFFSETS]
.as_ref()
.vortex_expect("validated chunk offsets slot")
}
fn nchunks(&self) -> usize {
self.slots()
.len()
.saturating_sub(ChunkedSlots::CHUNKS_OFFSET)
}
fn chunk(&self, idx: usize) -> &ArrayRef {
self.slots()[ChunkedSlots::CHUNKS_OFFSET + idx]
.as_ref()
.vortex_expect("validated chunk slot")
}
fn iter_chunks(&self) -> impl Iterator<Item = &ArrayRef> {
self.slots()[ChunkedSlots::CHUNKS_OFFSET..]
.iter()
.map(|slot| slot.as_ref().vortex_expect("validated chunk slot"))
}
fn chunks(&self) -> Vec<ArrayRef> {
self.iter_chunks().cloned().collect()
}
fn non_empty_chunks(&self) -> impl Iterator<Item = &ArrayRef> {
self.iter_chunks().filter(|chunk| !chunk.is_empty())
}
fn chunk_offset_values(&self) -> &[usize] {
&self.chunk_offsets
}
fn find_chunk_idx(&self, index: usize) -> VortexResult<(usize, usize)> {
assert!(index <= self.len(), "Index out of bounds of the array");
let chunk_offset_values = self.chunk_offset_values();
let index_chunk = chunk_offset_values
.search_sorted(&index, SearchSortedSide::Right)?
.to_ends_index(self.nchunks() + 1)
.saturating_sub(1);
let chunk_start = chunk_offset_values[index_chunk];
let index_in_chunk = index - chunk_start;
Ok((index_chunk, index_in_chunk))
}
fn array_iterator(&self) -> impl ArrayIterator + '_ {
ArrayIteratorAdapter::new(
self.dtype().clone(),
self.iter_chunks().map(|chunk| Ok(chunk.clone())),
)
}
fn array_stream(&self) -> impl ArrayStream + '_ {
ArrayStreamAdapter::new(
self.dtype().clone(),
stream::iter(self.iter_chunks().map(|chunk| Ok(chunk.clone()))),
)
}
}
impl<T: TypedArrayRef<Chunked>> ChunkedArrayExt for T {}
impl ChunkedData {
pub(super) fn new(chunk_offsets: Vec<usize>) -> Self {
Self {
chunk_offsets,
next_builder_slot: ChunkedSlots::CHUNKS_OFFSET,
}
}
pub(super) fn make_chunk_offsets_array(chunk_offsets: &[usize]) -> ArrayRef {
let mut chunk_offsets_buf = BufferMut::<u64>::with_capacity(chunk_offsets.len());
for &offset in chunk_offsets {
let offset = u64::try_from(offset)
.vortex_expect("chunk offset must fit in u64 for serialization");
unsafe { chunk_offsets_buf.push_unchecked(offset) }
}
PrimitiveArray::new(chunk_offsets_buf.freeze(), Validity::NonNullable).into_array()
}
pub fn validate(chunks: &[ArrayRef], dtype: &DType) -> VortexResult<()> {
for chunk in chunks {
if chunk.dtype() != dtype {
vortex_bail!("expected type: {} but instead got {}", dtype, chunk.dtype());
}
}
Ok(())
}
}
impl Array<Chunked> {
fn parts_from_chunks<const VALIDATE: bool>(
chunks: impl IntoIterator<Item = ArrayRef>,
dtype: DType,
) -> VortexResult<ArrayParts<Chunked>> {
let chunks = chunks.into_iter();
let (lower, _) = chunks.size_hint();
Self::parts_from_chunks_with_capacity::<VALIDATE>(chunks, dtype, lower)
}
fn parts_from_chunks_with_capacity<const VALIDATE: bool>(
chunks: impl IntoIterator<Item = ArrayRef>,
dtype: DType,
capacity: usize,
) -> VortexResult<ArrayParts<Chunked>> {
let mut slots = ArraySlots::with_capacity(ChunkedSlots::CHUNKS_OFFSET + capacity);
slots.push(None);
let mut chunk_offsets = Vec::with_capacity(capacity + 1);
chunk_offsets.push(0);
let mut len = 0usize;
for chunk in chunks {
if VALIDATE {
Self::validate_chunk_dtype(&chunk, &dtype)?;
}
len += chunk.len();
chunk_offsets.push(len);
slots.push(Some(chunk));
}
Ok(Self::parts_from_slots(dtype, len, chunk_offsets, slots))
}
fn validate_chunk_dtype(chunk: &ArrayRef, dtype: &DType) -> VortexResult<()> {
if chunk.dtype() != dtype {
vortex_bail!("expected type: {} but instead got {}", dtype, chunk.dtype());
}
Ok(())
}
fn parts_from_slots(
dtype: DType,
len: usize,
chunk_offsets: Vec<usize>,
mut slots: ArraySlots,
) -> ArrayParts<Chunked> {
slots[ChunkedSlots::CHUNK_OFFSETS] =
Some(ChunkedData::make_chunk_offsets_array(&chunk_offsets));
ArrayParts::new(Chunked, dtype, len, ChunkedData::new(chunk_offsets), slots)
}
pub(super) fn with_next_builder_slot(mut self, next_builder_slot: usize) -> Self {
if let Some(data) = self.data_mut() {
data.next_builder_slot = next_builder_slot;
return self;
}
let stats = self.statistics().to_owned();
let mut data = self.data().clone();
data.next_builder_slot = next_builder_slot;
unsafe {
Array::from_parts_unchecked(ArrayParts::new(
Chunked,
self.dtype().clone(),
self.len(),
data,
self.slots().iter().cloned().collect::<ArraySlots>(),
))
}
.with_stats_set(stats)
}
pub fn try_new(chunks: impl IntoIterator<Item = ArrayRef>, dtype: DType) -> VortexResult<Self> {
Self::try_from_chunked_parts(Self::parts_from_chunks::<true>(chunks, dtype)?)
}
pub fn rechunk(
&self,
target_bytesize: u64,
target_rowsize: usize,
ctx: &mut ExecutionCtx,
) -> VortexResult<Self> {
let mut new_chunks = Vec::new();
let mut chunks_to_combine = Vec::new();
let mut new_chunk_n_bytes = 0;
let mut new_chunk_n_elements = 0;
for chunk in self.iter_chunks() {
let n_bytes = chunk.nbytes();
let n_elements = chunk.len();
if (new_chunk_n_bytes + n_bytes > target_bytesize
|| new_chunk_n_elements + n_elements > target_rowsize)
&& !chunks_to_combine.is_empty()
{
let canonical = unsafe {
Array::<Chunked>::new_unchecked(
chunks_to_combine.drain(..),
self.dtype().clone(),
)
}
.into_array()
.execute::<Canonical>(ctx)?
.into_array();
new_chunks.push(canonical);
new_chunk_n_bytes = 0;
new_chunk_n_elements = 0;
}
if n_bytes > target_bytesize || n_elements > target_rowsize {
new_chunks.push(chunk.clone());
} else {
new_chunk_n_bytes += n_bytes;
new_chunk_n_elements += n_elements;
chunks_to_combine.push(chunk.clone());
}
}
if !chunks_to_combine.is_empty() {
let canonical =
unsafe { Array::<Chunked>::new_unchecked(chunks_to_combine, self.dtype().clone()) }
.into_array()
.execute::<Canonical>(ctx)?
.into_array();
new_chunks.push(canonical);
}
unsafe { Ok(Self::new_unchecked(new_chunks, self.dtype().clone())) }
}
pub unsafe fn new_unchecked(chunks: impl IntoIterator<Item = ArrayRef>, dtype: DType) -> Self {
let chunks = chunks.into_iter();
let (expected_nchunks, _) = chunks.size_hint();
unsafe { Self::new_unchecked_sized(chunks, dtype, expected_nchunks) }
}
pub unsafe fn new_unchecked_sized(
chunks: impl IntoIterator<Item = ArrayRef>,
dtype: DType,
expected_nchunks: usize,
) -> Self {
let parts = Self::parts_from_chunks_with_capacity::<false>(chunks, dtype, expected_nchunks)
.vortex_expect("unchecked chunked construction cannot fail");
unsafe { Self::from_chunked_parts_unchecked(parts) }
}
fn try_from_chunked_parts(parts: ArrayParts<Chunked>) -> VortexResult<Self> {
Array::try_from_parts(parts)
}
unsafe fn from_chunked_parts_unchecked(parts: ArrayParts<Chunked>) -> Self {
unsafe { Array::from_parts_unchecked(parts) }
}
}
impl FromIterator<ArrayRef> for Array<Chunked> {
fn from_iter<T: IntoIterator<Item = ArrayRef>>(iter: T) -> Self {
let mut chunks = iter.into_iter().peekable();
let dtype = chunks
.peek()
.map(|c| c.dtype().clone())
.vortex_expect("Cannot infer DType from an empty iterator");
Array::<Chunked>::try_new(chunks, dtype)
.vortex_expect("Failed to create chunked array from iterator")
}
}
#[cfg(test)]
mod test {
use std::sync::LazyLock;
use itertools::Itertools;
use rstest::rstest;
use vortex_buffer::buffer;
use vortex_error::VortexResult;
use vortex_error::vortex_err;
use vortex_session::VortexSession;
use crate::IntoArray;
use crate::VortexSessionExecute;
use crate::arrays::ChunkedArray;
use crate::arrays::PrimitiveArray;
use crate::arrays::chunked::ChunkedArrayExt;
use crate::assert_arrays_eq;
use crate::dtype::DType;
use crate::dtype::Nullability;
use crate::dtype::PType;
use crate::validity::Validity;
static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
#[rstest]
fn sized_chunks(
#[values(0, 1, 17)] nchunks: usize,
#[values(0, 1, 17)] expected_nchunks: usize,
) -> VortexResult<()> {
let dtype = DType::from(PType::U64);
let chunks = (0..nchunks as u64).map(|i| buffer![i].into_array());
let array =
unsafe { ChunkedArray::new_unchecked_sized(chunks, dtype.clone(), expected_nchunks) };
assert_eq!(array.dtype(), &dtype);
assert_eq!(array.nchunks(), nchunks);
assert_eq!(
array.chunk_offset_values(),
(0..=nchunks).collect::<Vec<_>>()
);
let mut ctx = SESSION.create_execution_ctx();
assert_arrays_eq!(
array,
PrimitiveArray::from_iter(0..nchunks as u64),
&mut ctx
);
Ok(())
}
#[rstest]
fn sized_chunks_with_process_results(#[values(0, 1)] error_at: usize) {
let mut visited = 0;
let chunks = (0..3).map(|i| {
visited += 1;
if i == error_at {
Err(vortex_err!("chunk source failed"))
} else {
Ok(buffer![1u64].into_array())
}
});
let dtype = DType::from(PType::U64);
let result = chunks.process_results(|chunks| {
unsafe { ChunkedArray::new_unchecked_sized(chunks, dtype, 3) }
});
assert!(
result
.unwrap_err()
.to_string()
.contains("chunk source failed")
);
assert_eq!(visited, error_at + 1);
}
#[test]
fn test_rechunk_one_chunk() {
let mut ctx = SESSION.create_execution_ctx();
let chunked = ChunkedArray::try_new(
vec![buffer![0u64].into_array()],
DType::Primitive(PType::U64, Nullability::NonNullable),
)
.unwrap();
let rechunked = chunked.rechunk(1 << 16, 1 << 16, &mut ctx).unwrap();
assert_arrays_eq!(chunked, rechunked, &mut ctx);
}
#[test]
fn test_rechunk_two_chunks() {
let mut ctx = SESSION.create_execution_ctx();
let chunked = ChunkedArray::try_new(
vec![buffer![0u64].into_array(), buffer![5u64].into_array()],
DType::Primitive(PType::U64, Nullability::NonNullable),
)
.unwrap();
let rechunked = chunked.rechunk(1 << 16, 1 << 16, &mut ctx).unwrap();
assert_eq!(rechunked.nchunks(), 1);
assert_arrays_eq!(chunked, rechunked, &mut ctx);
}
#[test]
fn test_rechunk_tiny_target_chunks() {
let mut ctx = SESSION.create_execution_ctx();
let chunked = ChunkedArray::try_new(
vec![
buffer![0u64, 1, 2, 3].into_array(),
buffer![4u64, 5].into_array(),
],
DType::Primitive(PType::U64, Nullability::NonNullable),
)
.unwrap();
let rechunked = chunked.rechunk(1 << 16, 5, &mut ctx).unwrap();
assert_eq!(rechunked.nchunks(), 2);
assert!(rechunked.iter_chunks().all(|c| c.len() < 5));
assert_arrays_eq!(chunked, rechunked, &mut ctx);
}
#[test]
fn test_rechunk_with_too_big_chunk() {
let mut ctx = SESSION.create_execution_ctx();
let chunked = ChunkedArray::try_new(
vec![
buffer![0u64, 1, 2].into_array(),
buffer![42_u64; 6].into_array(),
buffer![4u64, 5].into_array(),
buffer![6u64, 7].into_array(),
buffer![8u64, 9].into_array(),
],
DType::Primitive(PType::U64, Nullability::NonNullable),
)
.unwrap();
let rechunked = chunked.rechunk(1 << 16, 5, &mut ctx).unwrap();
assert_eq!(rechunked.nchunks(), 4);
assert_arrays_eq!(chunked, rechunked, &mut ctx);
}
#[test]
fn test_empty_chunks_all_valid() -> VortexResult<()> {
let mut ctx = SESSION.create_execution_ctx();
let chunks = vec![
PrimitiveArray::new(buffer![1u64, 2, 3], Validity::AllValid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), PrimitiveArray::new(buffer![4u64, 5], Validity::AllValid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), ];
let chunked =
ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
assert!(chunked.all_valid(&mut ctx)?);
assert!(!chunked.into_array().all_invalid(&mut ctx)?);
Ok(())
}
#[test]
fn test_empty_chunks_all_invalid() -> VortexResult<()> {
let mut ctx = SESSION.create_execution_ctx();
let chunks = vec![
PrimitiveArray::new(buffer![1u64, 2], Validity::AllInvalid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(),
PrimitiveArray::new(buffer![3u64, 4, 5], Validity::AllInvalid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(),
];
let chunked =
ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
assert!(!chunked.all_valid(&mut ctx)?);
assert!(chunked.into_array().all_invalid(&mut ctx)?);
Ok(())
}
#[test]
fn test_empty_chunks_mixed_validity() -> VortexResult<()> {
let mut ctx = SESSION.create_execution_ctx();
let chunks = vec![
PrimitiveArray::new(buffer![1u64, 2], Validity::AllValid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), PrimitiveArray::new(buffer![3u64, 4], Validity::AllInvalid).into_array(),
PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(),
];
let chunked =
ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
assert!(!chunked.all_valid(&mut ctx)?);
assert!(!chunked.into_array().all_invalid(&mut ctx)?);
Ok(())
}
}