1use crate::arrow::buffer::offset_buffer::OffsetBuffer;
6use crate::arrow::record_reader::buffer::ValuesBuffer;
7use crate::errors::{ParquetError, Result};
8use ahash::RandomState;
9use arrow_array::{Array, DictionaryArray, PrimitiveArray, downcast_integer};
10use arrow_array::{
11 ArrayRef, FixedSizeBinaryArray, GenericBinaryArray, OffsetSizeTrait,
12 builder::FixedSizeBinaryDictionaryBuilder,
13 cast::AsArray,
14 types::{
15 ArrowDictionaryKeyType, ArrowPrimitiveType, Int8Type, Int16Type, Int32Type, Int64Type,
16 UInt8Type, UInt16Type, UInt32Type, UInt64Type,
17 },
18};
19use arrow_buffer::{
20 ArrowNativeType, BooleanBuffer, Buffer, MutableBuffer, NullBuffer, ScalarBuffer,
21};
22use arrow_schema::DataType as ArrowType;
23use hashbrown::HashMap as HbHashMap;
24use hashbrown::hash_map::Entry;
25use std::hash::{BuildHasher, Hasher};
26use std::mem::size_of;
27use std::ptr::write_unaligned;
28use std::slice::{from_raw_parts, from_raw_parts_mut};
29use std::sync::Arc;
30
31pub enum DictionaryBuffer<K: ArrowNativeType, V: OffsetSizeTrait> {
34 Dict {
35 keys: Vec<K>,
36 values: ArrayRef,
37 key_upper_bound: Option<u64>,
39 },
40 Values {
41 values: OffsetBuffer<V>,
42 },
43}
44
45fn widen_key_bound(existing: &mut Option<u64>, incoming: Option<u64>) {
46 *existing = match (*existing, incoming) {
47 (Some(current), Some(new)) => Some(current.max(new)),
48 _ => None,
49 };
50}
51
52impl<K: ArrowNativeType + Ord, V: OffsetSizeTrait> DictionaryBuffer<K, V> {
53 #[cfg_attr(not(test), expect(unused))]
54 pub fn len(&self) -> usize {
55 match self {
56 Self::Dict { keys, .. } => keys.len(),
57 Self::Values { values } => values.len(),
58 }
59 }
60
61 pub fn as_keys_with_bit_width(
70 &mut self,
71 dictionary: &ArrayRef,
72 rle_bit_width: Option<u8>,
73 ) -> Option<&mut Vec<K>> {
74 assert!(K::from_usize(dictionary.len()).is_some());
75
76 let incoming_bound = rle_bit_width.map(|bit_width| 1u64 << bit_width);
78
79 match self {
80 Self::Dict {
81 keys,
82 values,
83 key_upper_bound,
84 } => {
85 let values_ptr = std::ptr::from_ref(values.as_ref()).cast::<()>();
89 let dict_ptr = std::ptr::from_ref(dictionary.as_ref()).cast::<()>();
90 if values_ptr == dict_ptr {
91 widen_key_bound(key_upper_bound, incoming_bound);
92 Some(keys)
93 } else if keys.is_empty() {
94 *values = Arc::clone(dictionary);
95 *key_upper_bound = incoming_bound;
96 Some(keys)
97 } else {
98 None
99 }
100 }
101 Self::Values { values } if values.is_empty() => {
102 *self = Self::Dict {
103 keys: Default::default(),
104 values: Arc::clone(dictionary),
105 key_upper_bound: incoming_bound,
106 };
107 match self {
108 Self::Dict { keys, .. } => Some(keys),
109 Self::Values { .. } => unreachable!(),
110 }
111 }
112 Self::Values { .. } => None,
113 }
114 }
115
116 pub fn spill_values(&mut self) -> Result<&mut OffsetBuffer<V>> {
121 match self {
122 Self::Values { values } => Ok(values),
123 Self::Dict { keys, values, .. } => {
124 let mut spilled = OffsetBuffer::with_capacity(0);
125 let data = values.to_data();
126 let dict_buffers = data.buffers();
127 let dict_offsets = dict_buffers[0].typed_data::<V>();
128 let dict_values = dict_buffers[1].as_slice();
129
130 if values.is_empty() {
131 spilled.offsets.resize(keys.len() + 1, V::default());
133 } else {
134 spilled.extend_from_dictionary(keys.as_slice(), dict_offsets, dict_values)?;
140 }
141
142 *self = Self::Values { values: spilled };
143 match self {
144 Self::Values { values } => Ok(values),
145 Self::Dict { .. } => unreachable!(),
146 }
147 }
148 }
149 }
150
151 pub fn into_array(
153 self,
154 null_buffer: Option<Buffer>,
155 data_type: &ArrowType,
156 hash_scratch: &mut MutableBuffer,
157 ) -> Result<ArrayRef> {
158 assert!(matches!(data_type, ArrowType::Dictionary(_, _)));
159
160 match self {
161 Self::Dict {
162 keys,
163 values,
164 key_upper_bound,
165 } => {
166 let keys_provably_in_range = key_upper_bound
167 .map(|bound| bound <= values.len() as u64)
168 .unwrap_or(false);
169
170 if !values.is_empty() && !keys_provably_in_range {
171 let min = K::from_usize(0).unwrap();
172 let max = K::from_usize(values.len()).unwrap();
173
174 let (observed_min, observed_max) = keys.as_slice().iter().copied().fold(
175 (max, min),
176 |(current_min, current_max), key| {
177 (current_min.min(key), current_max.max(key))
178 },
179 );
180
181 if observed_min < min || observed_max >= max {
182 return Err(general_err!(
183 "dictionary key beyond bounds of dictionary: 0..{}",
184 values.len()
185 ));
186 }
187 }
188
189 let ArrowType::Dictionary(key_type, value_type) = data_type else {
190 unreachable!()
191 };
192 let values = if let ArrowType::FixedSizeBinary(size) = **value_type {
193 let binary = values.as_binary::<i32>();
194 Arc::new(FixedSizeBinaryArray::new(
195 size,
196 binary.values().clone(),
197 binary.nulls().cloned(),
198 )) as _
199 } else {
200 values
201 };
202
203 let num_keys = keys.len();
204 let keys_buffer = Buffer::from_vec(keys);
205 let null_buffer =
206 null_buffer.map(|b| NullBuffer::new(BooleanBuffer::new(b, 0, num_keys)));
207
208 build_dictionary_array(key_type, keys_buffer, num_keys, null_buffer, values)
209 }
210 Self::Values { values } => {
211 let (key_type, value_type) = match data_type {
212 ArrowType::Dictionary(k, v) => (k, v.as_ref().clone()),
213 _ => unreachable!(),
214 };
215
216 if let ArrowType::FixedSizeBinary(size) = value_type {
220 let binary = values.into_array(null_buffer, GenericBinaryArray::<V>::DATA_TYPE);
221 let binary = binary.as_binary::<V>();
222 let array =
223 FixedSizeBinaryArray::try_from_sparse_iter_with_size(binary.iter(), size)?;
224 return pack_fixed_values(key_type, &array);
225 }
226
227 hash_byte_slices(&values.offsets, &values.values, hash_scratch);
228 let hashes = hashes_as_u64(hash_scratch);
229
230 pack_values_from_offsets(key_type, &value_type, &values, hashes, null_buffer)
231 }
232 }
233 }
234}
235
236impl<K: ArrowNativeType, V: OffsetSizeTrait> ValuesBuffer for DictionaryBuffer<K, V> {
237 fn with_capacity(capacity: usize) -> Self {
238 Self::Values {
239 values: OffsetBuffer::with_capacity(capacity),
240 }
241 }
242
243 fn reserve_exact(&mut self, additional: usize) {
244 match self {
245 Self::Dict { keys, .. } => keys.reserve_exact(additional),
246 Self::Values { values, .. } => values.reserve_exact(additional),
247 }
248 }
249
250 fn pad_nulls(
251 &mut self,
252 read_offset: usize,
253 values_read: usize,
254 levels_read: usize,
255 valid_mask: &[u8],
256 ) -> Result<()> {
257 match self {
258 Self::Dict { keys, .. } => {
259 keys.resize(read_offset + levels_read, K::default());
260 keys.pad_nulls(read_offset, values_read, levels_read, valid_mask)
261 }
262 Self::Values { values, .. } => {
263 values.pad_nulls(read_offset, values_read, levels_read, valid_mask)
264 }
265 }
266 }
267}
268
269fn build_dictionary_array(
272 key_type: &ArrowType,
273 keys_buffer: Buffer,
274 num_keys: usize,
275 null_buffer: Option<NullBuffer>,
276 values: ArrayRef,
277) -> Result<ArrayRef> {
278 macro_rules! build {
279 ($kt:ty) => {{
280 let scalars =
281 ScalarBuffer::<<$kt as ArrowPrimitiveType>::Native>::new(keys_buffer, 0, num_keys);
282 let keys = PrimitiveArray::<$kt>::new(scalars, null_buffer);
283 let dict = unsafe { DictionaryArray::<$kt>::new_unchecked(keys, values) };
285 Ok(Arc::new(dict) as ArrayRef)
286 }};
287 }
288 match key_type {
289 ArrowType::Int8 => build!(Int8Type),
290 ArrowType::Int16 => build!(Int16Type),
291 ArrowType::Int32 => build!(Int32Type),
292 ArrowType::Int64 => build!(Int64Type),
293 ArrowType::UInt8 => build!(UInt8Type),
294 ArrowType::UInt16 => build!(UInt16Type),
295 ArrowType::UInt32 => build!(UInt32Type),
296 ArrowType::UInt64 => build!(UInt64Type),
297 _ => Err(general_err!("unsupported dictionary key type: {key_type}")),
298 }
299}
300
301macro_rules! fixed_dict_helper {
302 ($k:ty, $array:ident) => {
303 pack_fixed_values_impl::<$k>($array)
304 };
305}
306
307fn pack_fixed_values(key_type: &ArrowType, array: &FixedSizeBinaryArray) -> Result<ArrayRef> {
308 downcast_integer! {
309 key_type => (fixed_dict_helper, array),
310 _ => unreachable!(),
311 }
312}
313
314fn pack_fixed_values_impl<K: ArrowDictionaryKeyType>(
315 array: &FixedSizeBinaryArray,
316) -> Result<ArrayRef> {
317 let mut builder = FixedSizeBinaryDictionaryBuilder::<K>::with_capacity(
318 array.len(),
319 1024,
320 array.value_length(),
321 );
322 for x in array {
323 match x {
324 Some(x) => {
325 builder.append(x)?;
326 }
327 None => builder.append_null(),
328 }
329 }
330 Ok(Arc::new(builder.finish()))
331}
332
333macro_rules! offsets_dict_helper {
334 ($k:ty, $key_type:ident, $value_type:ident, $values:ident, $hashes:ident, $null_buffer:ident) => {
335 pack_values_from_offsets_impl::<$k, _>(
336 $values,
337 $hashes,
338 $null_buffer,
339 $key_type,
340 $value_type,
341 )
342 };
343}
344
345fn pack_values_from_offsets<V: OffsetSizeTrait>(
346 key_type: &ArrowType,
347 value_type: &ArrowType,
348 values: &OffsetBuffer<V>,
349 hashes: &[u64],
350 null_buffer: Option<Buffer>,
351) -> Result<ArrayRef> {
352 downcast_integer! {
353 key_type => (offsets_dict_helper, key_type, value_type, values, hashes, null_buffer),
354 _ => unreachable!(),
355 }
356}
357
358struct PassthroughHasher(u64);
361impl std::hash::Hasher for PassthroughHasher {
362 fn finish(&self) -> u64 {
363 self.0
364 }
365 fn write(&mut self, _: &[u8]) {
366 unreachable!()
367 }
368 fn write_u64(&mut self, value: u64) {
369 self.0 = value;
370 }
371}
372#[derive(Default)]
373struct BuildPassthroughHasher;
374impl std::hash::BuildHasher for BuildPassthroughHasher {
375 type Hasher = PassthroughHasher;
376 fn build_hasher(&self) -> PassthroughHasher {
377 PassthroughHasher(0)
378 }
379}
380
381fn pack_values_from_offsets_impl<K: ArrowDictionaryKeyType, V: OffsetSizeTrait>(
385 offset_buffer: &OffsetBuffer<V>,
386 hashes: &[u64],
387 null_buffer: Option<Buffer>,
388 key_type: &ArrowType,
389 value_type: &ArrowType,
390) -> Result<ArrayRef> {
391 let dict_type = ArrowType::Dictionary(Box::new(key_type.clone()), Box::new(value_type.clone()));
392 let num_values = offset_buffer.len();
393
394 let mut keys: Vec<K::Native> = Vec::with_capacity(num_values);
395 let mut unique_offsets: Vec<V> = Vec::with_capacity(num_values + 1);
396 unique_offsets.push(V::default());
397 let mut unique_bytes: Vec<u8> = Vec::with_capacity(offset_buffer.values.len());
398
399 let mut dedup: HbHashMap<u64, (usize, usize), BuildPassthroughHasher> =
400 HbHashMap::with_capacity_and_hasher(num_values, BuildPassthroughHasher);
401
402 let mut collision_overflow: Vec<(u64, usize, usize)> = Vec::new();
405
406 for (input_idx, &hash) in hashes.iter().enumerate() {
407 let byte_start = offset_buffer.offsets[input_idx].as_usize();
408 let byte_end = offset_buffer.offsets[input_idx + 1].as_usize();
409 let bytes = &offset_buffer.values[byte_start..byte_end];
410
411 let output_idx = match dedup.entry(hash) {
412 Entry::Occupied(entry) => {
413 let (first_input_idx, existing_output_idx) = *entry.get();
414 let first_start = offset_buffer.offsets[first_input_idx].as_usize();
415 let first_end = offset_buffer.offsets[first_input_idx + 1].as_usize();
416 if &offset_buffer.values[first_start..first_end] == bytes {
417 existing_output_idx
418 } else {
419 let existing = collision_overflow
421 .iter()
422 .find(|&&(entry_hash, collision_input_idx, _)| {
423 if entry_hash != hash {
424 return false;
425 }
426 let collision_start =
427 offset_buffer.offsets[collision_input_idx].as_usize();
428 let collision_end =
429 offset_buffer.offsets[collision_input_idx + 1].as_usize();
430 &offset_buffer.values[collision_start..collision_end] == bytes
431 })
432 .map(|&(_, _, collision_output_idx)| collision_output_idx);
433
434 match existing {
435 Some(collision_output_idx) => collision_output_idx,
436 None => {
437 let new_output_idx = unique_offsets.len() - 1;
438 unique_bytes.extend_from_slice(bytes);
439 let new_end = V::from_usize(unique_bytes.len()).ok_or_else(|| {
440 general_err!("offset overflow building dictionary")
441 })?;
442 unique_offsets.push(new_end);
443 collision_overflow.push((hash, input_idx, new_output_idx));
444 new_output_idx
445 }
446 }
447 }
448 }
449 Entry::Vacant(entry) => {
450 let output_idx = unique_offsets.len() - 1;
451 unique_bytes.extend_from_slice(bytes);
452 let new_end = V::from_usize(unique_bytes.len())
453 .ok_or_else(|| general_err!("offset overflow building dictionary"))?;
454 unique_offsets.push(new_end);
455 entry.insert((input_idx, output_idx));
456 output_idx
457 }
458 };
459
460 let key = K::Native::from_usize(output_idx)
461 .ok_or_else(|| general_err!("dictionary key overflow"))?;
462 keys.push(key);
463 }
464
465 let num_unique = unique_offsets.len() - 1;
466
467 let value_data = unsafe {
471 arrow_data::ArrayData::builder(value_type.clone())
472 .len(num_unique)
473 .add_buffer(Buffer::from_vec(unique_offsets))
474 .add_buffer(Buffer::from_vec(unique_bytes))
475 .build_unchecked()
476 };
477
478 let dict_array: DictionaryArray<K> = unsafe {
480 arrow_data::ArrayData::builder(dict_type)
481 .len(keys.len())
482 .add_buffer(Buffer::from_vec(keys))
483 .add_child_data(value_data)
484 .null_bit_buffer(null_buffer)
485 .build_unchecked()
486 .into()
487 };
488
489 Ok(Arc::new(dict_array))
490}
491
492fn hash_byte_slices<I: ArrowNativeType>(offsets: &[I], values: &[u8], scratch: &mut MutableBuffer) {
493 let count = offsets.len().saturating_sub(1);
494 scratch.clear();
495 scratch.resize(count * size_of::<u64>(), 0u8);
496
497 let state = RandomState::new();
498
499 #[expect(
501 clippy::cast_ptr_alignment,
502 reason = "MutableBuffer is 64-byte aligned"
503 )]
504 let hash_slots = unsafe { from_raw_parts_mut(scratch.as_mut_ptr().cast::<u64>(), count) };
505
506 for idx in 0..count {
507 let start = offsets[idx].as_usize();
508 let end = offsets[idx + 1].as_usize();
509 let mut hasher = state.build_hasher();
510 hasher.write(&values[start..end]);
511 unsafe { write_unaligned(hash_slots.as_mut_ptr().add(idx), hasher.finish()) };
513 }
514}
515
516#[inline]
517fn hashes_as_u64(scratch: &[u8]) -> &[u64] {
518 let n = scratch.len() / size_of::<u64>();
519 #[expect(
521 clippy::cast_ptr_alignment,
522 reason = "MutableBuffer is 64-byte aligned"
523 )]
524 unsafe {
525 from_raw_parts(scratch.as_ptr().cast::<u64>(), n)
526 }
527}
528
529#[cfg(test)]
530mod tests {
531 use super::*;
532 use arrow::compute::cast;
533 use arrow_array::StringArray;
534
535 #[test]
536 fn test_dictionary_buffer() {
537 let dict_type =
538 ArrowType::Dictionary(Box::new(ArrowType::Int32), Box::new(ArrowType::Utf8));
539
540 let d1: ArrayRef = Arc::new(StringArray::from(vec!["hello", "world", "", "a", "b"]));
541
542 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
543
544 let values = &[1, 0, 3, 2, 4];
546 buffer
547 .as_keys_with_bit_width(&d1, None)
548 .unwrap()
549 .extend_from_slice(values);
550
551 let mut valid = vec![false, false, true, true, false, true, true, true];
552 let valid_buffer = Buffer::from_iter(valid.iter().copied());
553 buffer
554 .pad_nulls(0, values.len(), valid.len(), valid_buffer.as_slice())
555 .unwrap();
556
557 let values = buffer.spill_values().unwrap();
560 let read_offset = values.len();
561 values.try_push(b"bingo", false).unwrap();
562 values.try_push(b"bongo", false).unwrap();
563
564 valid.extend_from_slice(&[false, false, true, false, true]);
565 let null_buffer = Buffer::from_iter(valid.iter().copied());
566 buffer
567 .pad_nulls(read_offset, 2, 5, null_buffer.as_slice())
568 .unwrap();
569
570 assert_eq!(buffer.len(), 13);
571 let split = std::mem::replace(&mut buffer, DictionaryBuffer::with_capacity(0));
572
573 let array = split
574 .into_array(Some(null_buffer), &dict_type, &mut MutableBuffer::new(0))
575 .unwrap();
576 assert_eq!(array.data_type(), &dict_type);
577
578 let strings = cast(&array, &ArrowType::Utf8).unwrap();
579 let strings = strings.as_any().downcast_ref::<StringArray>().unwrap();
580 assert_eq!(
581 strings.iter().collect::<Vec<_>>(),
582 vec![
583 None,
584 None,
585 Some("world"),
586 Some("hello"),
587 None,
588 Some("a"),
589 Some(""),
590 Some("b"),
591 None,
592 None,
593 Some("bingo"),
594 None,
595 Some("bongo")
596 ]
597 );
598
599 assert!(matches!(&buffer, DictionaryBuffer::Values { .. }));
601 assert_eq!(buffer.len(), 0);
602 let d2 = Arc::new(StringArray::from(vec!["bingo", ""])) as ArrayRef;
603 buffer
604 .as_keys_with_bit_width(&d2, None)
605 .unwrap()
606 .extend_from_slice(&[0, 1, 0, 1]);
607
608 let array = std::mem::replace(&mut buffer, DictionaryBuffer::with_capacity(0))
609 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
610 .unwrap();
611 assert_eq!(array.data_type(), &dict_type);
612
613 let strings = cast(&array, &ArrowType::Utf8).unwrap();
614 let strings = strings.as_any().downcast_ref::<StringArray>().unwrap();
615 assert_eq!(
616 strings.iter().collect::<Vec<_>>(),
617 vec![Some("bingo"), Some(""), Some("bingo"), Some("")]
618 );
619
620 assert!(matches!(&buffer, DictionaryBuffer::Values { .. }));
622 assert_eq!(buffer.len(), 0);
623 let d3 = Arc::new(StringArray::from(vec!["bongo"])) as ArrayRef;
624 buffer
625 .as_keys_with_bit_width(&d3, None)
626 .unwrap()
627 .extend_from_slice(&[0, 0]);
628
629 let d4 = Arc::new(StringArray::from(vec!["bananas"])) as ArrayRef;
631 assert!(buffer.as_keys_with_bit_width(&d4, None).is_none());
632 }
633
634 #[test]
635 fn test_validates_keys() {
636 let dict_type =
637 ArrowType::Dictionary(Box::new(ArrowType::Int32), Box::new(ArrowType::Utf8));
638
639 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
640 let d = Arc::new(StringArray::from(vec!["", "f"])) as ArrayRef;
641 buffer
642 .as_keys_with_bit_width(&d, None)
643 .unwrap()
644 .extend_from_slice(&[0, 2, 0]);
645
646 let err = buffer
647 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
648 .unwrap_err()
649 .to_string();
650 assert!(
651 err.contains("dictionary key beyond bounds of dictionary: 0..2"),
652 "{}",
653 err
654 );
655
656 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
657 let d = Arc::new(StringArray::from(vec![""])) as ArrayRef;
658 buffer
659 .as_keys_with_bit_width(&d, None)
660 .unwrap()
661 .extend_from_slice(&[0, 1, 0]);
662
663 let err = buffer.spill_values().unwrap_err().to_string();
664 assert!(
665 err.contains("dictionary key beyond bounds of dictionary: 0..1"),
666 "{}",
667 err
668 );
669 }
670
671 #[test]
673 fn test_values_path_large_utf8_type() {
674 let dict_type =
675 ArrowType::Dictionary(Box::new(ArrowType::Int32), Box::new(ArrowType::LargeUtf8));
676 let mut buffer = DictionaryBuffer::<i32, i64>::with_capacity(0);
677 let values = buffer.spill_values().unwrap();
678 for s in ["foo", "bar", "foo"] {
679 values.try_push(s.as_bytes(), false).unwrap();
680 }
681
682 let array = buffer
683 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
684 .unwrap();
685 let dict = array
686 .as_any()
687 .downcast_ref::<DictionaryArray<Int32Type>>()
688 .unwrap();
689
690 assert_eq!(dict.data_type(), &dict_type);
691 assert_eq!(dict.values().data_type(), &ArrowType::LargeUtf8);
692 }
693
694 #[test]
697 fn test_int8_key_overflow_boundary() {
698 let dict_type = ArrowType::Dictionary(Box::new(ArrowType::Int8), Box::new(ArrowType::Utf8));
699 let mut scratch = MutableBuffer::new(0);
700
701 {
702 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
703 let values = buffer.spill_values().unwrap();
704 for i in 0u32..128 {
705 values
706 .try_push(format!("val{i}").as_bytes(), false)
707 .unwrap();
708 }
709 buffer
710 .into_array(None, &dict_type, &mut scratch)
711 .expect("128 unique strings must fit: last index is 127 = i8::MAX");
712 }
713
714 {
715 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
716 let values = buffer.spill_values().unwrap();
717 for i in 0u32..129 {
718 values
719 .try_push(format!("val{i}").as_bytes(), false)
720 .unwrap();
721 }
722 let err = buffer
723 .into_array(None, &dict_type, &mut scratch)
724 .unwrap_err()
725 .to_string();
726 assert!(
727 err.contains("dictionary key overflow"),
728 "expected 'dictionary key overflow', got: {err}"
729 );
730 }
731 }
732
733 #[test]
734 fn test_fixed_size_binary_key_overflow_boundary() {
735 for (key_type, capacity) in [(ArrowType::Int8, 128u32), (ArrowType::UInt8, 256)] {
736 for unique in [capacity, capacity + 1] {
737 let values = (0..unique)
738 .map(|value| Some(value.to_le_bytes()))
739 .chain([None, Some(0u32.to_le_bytes())]);
740 let values =
741 FixedSizeBinaryArray::try_from_sparse_iter_with_size(values, 4).unwrap();
742 let result = pack_fixed_values(&key_type, &values);
743 if unique > capacity {
744 let error = result.unwrap_err();
745 let ParquetError::External(source) = &error else {
746 panic!("expected an Arrow dictionary overflow error, got {error}");
747 };
748 assert!(
749 matches!(
750 source.downcast_ref::<arrow_schema::ArrowError>(),
751 Some(arrow_schema::ArrowError::DictionaryKeyOverflowError)
752 ),
753 "{error}"
754 );
755 } else {
756 let array = result.unwrap();
757 assert_eq!(array.len(), unique as usize + 2);
758 assert_eq!(array.null_count(), 1);
759 assert!(array.is_null(unique as usize));
760 assert!(array.is_valid(unique as usize + 1));
761 let dictionary = array.as_any_dictionary();
762 assert_eq!(dictionary.values().len(), unique as usize);
763 assert_eq!(
764 dictionary.values().data_type(),
765 &ArrowType::FixedSizeBinary(4)
766 );
767 }
768 }
769 }
770 }
771
772 #[test]
775 fn test_hash_collision_deduplication() {
776 let key_type = ArrowType::Int32;
777 let value_type = ArrowType::Utf8;
778
779 let mut ob = OffsetBuffer::<i32>::with_capacity(3);
781 ob.try_push(b"alpha", false).unwrap();
782 ob.try_push(b"beta", false).unwrap();
783 ob.try_push(b"beta", false).unwrap();
784 let hashes = [0xdeadbeef_u64; 3];
785
786 let array = pack_values_from_offsets_impl::<Int32Type, i32>(
787 &ob,
788 &hashes,
789 None,
790 &key_type,
791 &value_type,
792 )
793 .unwrap();
794
795 let dict = array
796 .as_any()
797 .downcast_ref::<DictionaryArray<Int32Type>>()
798 .unwrap();
799
800 assert_eq!(dict.values().len(), 2);
801 let keys: Vec<i32> = dict.keys().values().iter().copied().collect();
802 assert_eq!(keys, vec![0, 1, 1]);
803 }
804
805 #[test]
807 fn test_values_path_binary_type() {
808 let dict_type =
809 ArrowType::Dictionary(Box::new(ArrowType::Int32), Box::new(ArrowType::Binary));
810 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
811 let values = buffer.spill_values().unwrap();
812 for s in [b"abc".as_ref(), b"\x00\xff", b"abc"] {
813 values.try_push(s, false).unwrap();
814 }
815
816 let array = buffer
817 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
818 .unwrap();
819 let dict = array
820 .as_any()
821 .downcast_ref::<DictionaryArray<Int32Type>>()
822 .unwrap();
823
824 assert_eq!(dict.data_type(), &dict_type);
825 assert_eq!(dict.values().data_type(), &ArrowType::Binary);
826 }
827
828 #[test]
829 fn test_key_upper_bound_skip_scan_when_bound_fits_otherwise_scan() {
830 let dict_type =
831 ArrowType::Dictionary(Box::new(ArrowType::Int32), Box::new(ArrowType::Utf8));
832 let dict_5 = Arc::new(StringArray::from(vec!["a", "b", "c", "d", "e"])) as ArrayRef;
833
834 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
835 buffer
836 .as_keys_with_bit_width(&dict_5, Some(2))
837 .unwrap()
838 .extend_from_slice(&[0, 1, 2, 3]);
839 assert!(matches!(
840 buffer,
841 DictionaryBuffer::Dict {
842 key_upper_bound: Some(4),
843 ..
844 }
845 ));
846 let array = buffer
847 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
848 .unwrap();
849 assert_eq!(array.len(), 4);
850
851 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
852 buffer
853 .as_keys_with_bit_width(&dict_5, Some(4))
854 .unwrap()
855 .extend_from_slice(&[0, 10]);
856 let err = buffer
857 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
858 .unwrap_err()
859 .to_string();
860 assert!(err.contains("dictionary key beyond bounds"), "{err}");
861
862 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
863 buffer
864 .as_keys_with_bit_width(&dict_5, None)
865 .unwrap()
866 .extend_from_slice(&[0, 7]);
867 buffer
868 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
869 .unwrap_err();
870
871 let mut buffer = DictionaryBuffer::<i32, i32>::with_capacity(0);
872 buffer
873 .as_keys_with_bit_width(&dict_5, Some(2))
874 .unwrap()
875 .extend_from_slice(&[0, 1]);
876 buffer
877 .as_keys_with_bit_width(&dict_5, Some(4))
878 .unwrap()
879 .extend_from_slice(&[10]);
880 assert!(matches!(
881 buffer,
882 DictionaryBuffer::Dict {
883 key_upper_bound: Some(16),
884 ..
885 }
886 ));
887 buffer
888 .into_array(None, &dict_type, &mut MutableBuffer::new(0))
889 .unwrap_err();
890 }
891}