use std::cell::OnceCell;
use std::hash::Hash;
use std::mem;
use rustc_hash::FxBuildHasher;
use vortex_buffer::Alignment;
use vortex_buffer::BitBufferMut;
use vortex_buffer::BufferAllocatorRef;
use vortex_buffer::BufferMut;
use vortex_error::VortexExpect;
use vortex_error::VortexResult;
use vortex_error::vortex_panic;
use vortex_mask::Mask;
use vortex_utils::aliases::hash_map::Entry;
use vortex_utils::aliases::hash_map::HashMap;
use super::DictConstraints;
use super::DictEncoder;
use crate::ArrayRef;
use crate::ExecutionCtx;
use crate::IntoArray;
use crate::arrays::PrimitiveArray;
use crate::arrays::primitive::NativeValue;
use crate::dtype::NativePType;
use crate::dtype::Nullability;
use crate::dtype::PType;
use crate::dtype::UnsignedPType;
use crate::validity::Validity;
pub fn primitive_dict_builder<T: NativePType>(
nullability: Nullability,
constraints: &DictConstraints,
allocator: BufferAllocatorRef,
) -> Box<dyn DictEncoder>
where
NativeValue<T>: Hash + Eq,
{
let max_code = match T::PTYPE.bit_width() {
8 => u8::MAX as u64,
16 => u16::MAX as u64,
32 => u32::MAX as u64,
64 => u64::MAX,
width => vortex_panic!("invalid bit_width: {width}"),
}
.saturating_add(u64::from(nullability.is_nullable()));
let max_code = max_code.min(constraints.max_len.saturating_sub(1) as u64);
match max_code {
max if max <= u8::MAX as u64 => Box::new(PrimitiveDictBuilder::<T, u8>::new_in(
nullability,
constraints,
allocator,
)),
max if max <= u16::MAX as u64 => Box::new(PrimitiveDictBuilder::<T, u16>::new_in(
nullability,
constraints,
allocator,
)),
max if max <= u32::MAX as u64 => Box::new(PrimitiveDictBuilder::<T, u32>::new_in(
nullability,
constraints,
allocator,
)),
_ => Box::new(PrimitiveDictBuilder::<T, u64>::new_in(
nullability,
constraints,
allocator,
)),
}
}
impl<T, Code> PrimitiveDictBuilder<T, Code>
where
T: NativePType,
NativeValue<T>: Hash + Eq,
Code: UnsignedPType,
{
pub fn new_in(
nullability: Nullability,
constraints: &DictConstraints,
allocator: BufferAllocatorRef,
) -> Self {
let max_dict_len = constraints
.max_len
.min(constraints.max_bytes / T::PTYPE.byte_width());
Self {
lookup: HashMap::with_hasher(FxBuildHasher),
null_code: OnceCell::new(),
values: BufferMut::<T>::empty_aligned_in(Alignment::of::<T>(), allocator.clone()),
values_nulls: BitBufferMut::empty_in(allocator.clone()),
allocator,
nullability,
max_dict_len,
}
}
fn encode_value(&mut self, v: T) -> Option<Code> {
match self.lookup.entry(NativeValue(v)) {
Entry::Occupied(o) => Some(*o.get()),
Entry::Vacant(vac) => {
if !self.values.is_empty() && self.values.len() >= self.max_dict_len {
return None;
}
let next_code = Code::from_usize(self.values.len()).unwrap_or_else(|| {
vortex_panic!("{} has to fit into {}", self.values.len(), Code::PTYPE)
});
self.values.push(v);
self.values_nulls.append_true();
Some(*vac.insert(next_code))
}
}
}
fn encode_null(&mut self) -> Option<Code> {
if let Some(code) = self.null_code.get() {
return Some(*code);
}
if !self.values.is_empty() && self.values.len() >= self.max_dict_len {
return None;
}
let code = Code::from_usize(self.values.len()).unwrap_or_else(|| {
vortex_panic!("{} has to fit into {}", self.values.len(), Code::PTYPE)
});
self.values.push(T::default());
self.values_nulls.append_false();
self.null_code
.set(code)
.ok()
.vortex_expect("null code is initialized once");
Some(code)
}
}
pub struct PrimitiveDictBuilder<T, Code> {
lookup: HashMap<NativeValue<T>, Code, FxBuildHasher>,
null_code: OnceCell<Code>,
values: BufferMut<T>,
values_nulls: BitBufferMut,
nullability: Nullability,
max_dict_len: usize,
allocator: BufferAllocatorRef,
}
impl<T, Code> DictEncoder for PrimitiveDictBuilder<T, Code>
where
T: NativePType,
NativeValue<T>: Hash + Eq,
Code: UnsignedPType,
{
fn encode(&mut self, array: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<PrimitiveArray> {
let mut codes = BufferMut::<Code>::with_capacity_in(array.len(), self.allocator.clone());
let prim = array.clone().execute::<PrimitiveArray>(ctx)?;
match prim.validity()?.execute_mask(array.len(), ctx)? {
Mask::AllTrue(_) => {
for &value in prim.as_slice::<T>() {
let Some(code) = self.encode_value(value) else {
break;
};
unsafe { codes.push_unchecked(code) }
}
}
Mask::AllFalse(_) => {
if let Some(code) = self.encode_null() {
unsafe { codes.push_n_unchecked(code, array.len()) }
}
}
Mask::Values(v) => {
let bit_buff = v.bit_buffer();
for (&value, valid) in prim.as_slice::<T>().iter().zip(bit_buff) {
if !valid {
let Some(code) = self.encode_null() else {
break;
};
unsafe { codes.push_unchecked(code) }
} else {
let Some(code) = self.encode_value(value) else {
break;
};
unsafe { codes.push_unchecked(code) }
}
}
}
}
Ok(PrimitiveArray::new(codes, Validity::NonNullable))
}
fn reset(&mut self) -> ArrayRef {
self.lookup.clear();
self.null_code = OnceCell::new();
let values = mem::replace(
&mut self.values,
BufferMut::empty_aligned_in(Alignment::of::<T>(), self.allocator.clone()),
);
let nulls = mem::replace(
&mut self.values_nulls,
BitBufferMut::empty_in(self.allocator.clone()),
)
.freeze();
PrimitiveArray::new(values, Validity::from_bit_buffer(nulls, self.nullability)).into_array()
}
fn codes_ptype(&self) -> PType {
Code::PTYPE
}
}
#[cfg(test)]
mod tests {
use std::sync::LazyLock;
use rstest::rstest;
use vortex_buffer::buffer;
use vortex_error::VortexResult;
use vortex_session::VortexSession;
use super::primitive_dict_builder;
use crate::IntoArray as _;
use crate::VortexSessionExecute;
use crate::arrays::dict::DictArraySlotsExt;
use crate::assert_arrays_eq;
use crate::builders::dict::DictConstraints;
use crate::builders::dict::UNCONSTRAINED;
use crate::builders::dict::dict_encode;
use crate::builders::dict::dict_encoder_in;
use crate::builders::dict::primitive::PrimitiveArray;
use crate::dtype::DType;
use crate::dtype::Nullability;
use crate::dtype::Nullability::NonNullable;
use crate::dtype::Nullability::Nullable;
use crate::dtype::PType;
use crate::match_each_integer_ptype;
use crate::match_each_native_ptype;
static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
const USIZE_PTYPE: PType = PType::min_unsigned_ptype_for_value(usize::MAX as u64);
#[test]
fn encode_primitive() {
let mut ctx = SESSION.create_execution_ctx();
let arr = buffer![1, 1, 3, 3, 3].into_array();
let dict = dict_encode(&arr, &mut SESSION.create_execution_ctx()).unwrap();
let expected_codes = buffer![0u8, 0, 1, 1, 1].into_array();
assert_arrays_eq!(dict.codes(), expected_codes, &mut ctx);
let expected_values = buffer![1i32, 3].into_array();
assert_arrays_eq!(dict.values(), expected_values, &mut ctx);
}
#[test]
fn encode_primitive_nulls() {
let mut ctx = SESSION.create_execution_ctx();
let arr = PrimitiveArray::from_option_iter([
Some(1),
Some(1),
None,
Some(3),
Some(3),
None,
Some(3),
None,
])
.into_array();
let dict = dict_encode(&arr, &mut SESSION.create_execution_ctx()).unwrap();
let expected_codes = buffer![0u8, 0, 1, 2, 2, 1, 2, 1].into_array();
assert_arrays_eq!(dict.codes(), expected_codes, &mut ctx);
let expected_values =
PrimitiveArray::from_option_iter([Some(1i32), None, Some(3)]).into_array();
assert_arrays_eq!(dict.values(), expected_values, &mut ctx);
}
#[test]
fn reset_clears_dict() {
let mut ctx = SESSION.create_execution_ctx();
let first = PrimitiveArray::from_option_iter([Some(1i32), None, Some(3)]).into_array();
let constraints = DictConstraints {
max_len: u32::MAX as usize,
..UNCONSTRAINED
};
let mut encoder = dict_encoder_in(&first, &constraints, ctx.allocator().clone());
assert_arrays_eq!(
encoder.encode(&first, &mut ctx).unwrap(),
buffer![0u32, 1, 2].into_array(),
&mut ctx
);
assert_arrays_eq!(encoder.reset(), first, &mut ctx);
let second = PrimitiveArray::from_option_iter([Some(4i32), Some(5)]).into_array();
assert_arrays_eq!(
encoder.encode(&second, &mut ctx).unwrap(),
buffer![0u32, 1].into_array(),
&mut ctx
);
assert_arrays_eq!(encoder.reset(), second, &mut ctx);
}
#[rstest]
#[case::u8(PType::U8, PType::U16)]
#[case::i8(PType::I8, PType::U16)]
#[case::u16(PType::U16, PType::U32)]
#[case::i16(PType::I16, PType::U32)]
fn encode_every_value_and_a_null(
#[case] ptype: PType,
#[case] codes_ptype: PType,
#[values(false, true)] null_first: bool,
) -> VortexResult<()> {
let mut ctx = SESSION.create_execution_ctx();
let arr = match_each_integer_ptype!(ptype, |T| {
let mut values = (T::MIN..=T::MAX).map(Some).collect::<Vec<_>>();
values.insert(if null_first { 0 } else { values.len() }, None);
PrimitiveArray::from_option_iter(values).into_array()
});
let dict = dict_encode(&arr, &mut ctx)?;
assert_eq!(
dict.codes().dtype(),
&DType::Primitive(codes_ptype, NonNullable)
);
assert_eq!(dict.values().len(), arr.len());
assert_arrays_eq!(dict, arr, &mut ctx);
Ok(())
}
#[rstest]
#[case::u8(PType::U8, NonNullable, usize::MAX, PType::U8)]
#[case::u16(PType::U16, NonNullable, usize::MAX, PType::U16)]
#[case::u32(PType::U32, NonNullable, usize::MAX, PType::U32)]
#[case::nullable_u32(PType::U32, Nullable, usize::MAX, USIZE_PTYPE)]
#[case::nullable_u64(PType::U64, Nullable, usize::MAX, USIZE_PTYPE)]
#[case::nullable_f16(PType::F16, Nullable, usize::MAX, PType::U32)]
#[case::nullable_f32(PType::F32, Nullable, usize::MAX, USIZE_PTYPE)]
#[case::empty_budget(PType::U16, Nullable, 0, PType::U8)]
#[case::full_u8_codes(PType::U16, Nullable, 256, PType::U8)]
#[case::widen_u8_codes(PType::U16, Nullable, 257, PType::U16)]
#[case::full_u16_codes(PType::U32, Nullable, 65_536, PType::U16)]
#[case::widen_u16_codes(PType::U32, Nullable, 65_537, PType::U32)]
fn codes_fit_dictionary_bounds(
#[case] ptype: PType,
#[case] nullability: Nullability,
#[case] max_len: usize,
#[case] expected_codes_ptype: PType,
) {
let ctx = SESSION.create_execution_ctx();
let constraints = DictConstraints {
max_len,
..UNCONSTRAINED
};
let encoder = match_each_native_ptype!(ptype, |T| {
primitive_dict_builder::<T>(nullability, &constraints, ctx.allocator().clone())
});
assert_eq!(encoder.codes_ptype(), expected_codes_ptype);
}
}