Skip to main content

parquet/arrow/buffer/
dictionary_buffer.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use 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
31/// An array of variable length byte arrays that are potentially dictionary encoded
32/// and can be converted into a corresponding [`ArrayRef`]
33pub enum DictionaryBuffer<K: ArrowNativeType, V: OffsetSizeTrait> {
34    Dict {
35        keys: Vec<K>,
36        values: ArrayRef,
37        /// Exclusive upper bound for decoded keys.
38        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    /// Returns the key buffer or `None` if the dictionary must be rebuilt.
62    ///
63    /// Records an exclusive bound derived from `rle_bit_width`. A missing width
64    /// discards any previously recorded bound.
65    ///
66    /// # Panics
67    ///
68    /// Panics if the dictionary is too large for `K`.
69    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        // Dictionary RLE bit widths are validated to be at most 32.
77        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                // Need to discard fat pointer for equality check
86                // - https://stackoverflow.com/a/67114787
87                // - https://github.com/rust-lang/rust/issues/46139
88                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    /// Returns a mutable reference to a values array
117    ///
118    /// If this is currently dictionary encoded, this will convert from the
119    /// dictionary encoded representation
120    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                    // If dictionary is empty, zero pad offsets
132                    spilled.offsets.resize(keys.len() + 1, V::default());
133                } else {
134                    // Note: at this point null positions will have arbitrary dictionary keys
135                    // and this will hydrate them to the corresponding byte array. This is
136                    // likely sub-optimal, as we would prefer zero length null "slots", but
137                    // spilling is already a degenerate case and so it is unclear if this is
138                    // worth optimising for, e.g. by keeping a null mask around
139                    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    /// Converts this into an [`ArrayRef`] with the provided `data_type` and `null_buffer`
152    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                // Plain byte-array pages are decoded into an offset buffer. Convert
217                // this representation explicitly before rebuilding an FSB dictionary,
218                // as FixedSizeBinary arrays have no offsets buffer.
219                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
269/// Build a dictionary array from a raw keys buffer and an already-decoded values
270/// `ArrayRef`, skipping the ArrayData round-trip.
271fn 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            // SAFETY: key bounds already validated by caller
284            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
358// Avoids double-hashing: keys are already high-quality u64 hashes from ahash,
359// so we pass them through directly rather than re-hashing inside the HashMap.
360struct 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
381/// Builds a [`DictionaryArray`] directly from a flat [`OffsetBuffer`] using pre-computed
382/// hashes to deduplicate values in a single pass, avoiding the intermediate StringArray
383/// materialization
384fn 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    // Tracks colliding values (same hash, different bytes) so repeated occurrences
403    // are deduplicated rather than inserted as new entries. Empty in the common case.
404    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                    // True hash collision — check overflow list before inserting.
420                    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    // SAFETY: buffers are constructed directly from typed Vecs above; offsets are
468    // monotonically non-decreasing and bounded by unique_bytes.len(), and all
469    // key values are within 0..num_unique, so the invariants Arrow requires hold.
470    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    // SAFETY: keys are within 0..num_unique and value_data is valid.
479    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    // SAFETY: MutableBuffer is 64-byte aligned; scratch is sized to exactly count * size_of::<u64>()
500    #[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        // SAFETY: idx is within 0..count
512        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    // SAFETY: scratch was written as u64s by hash_byte_slices, and MutableBuffer is 64-byte aligned
520    #[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        // Read some data preserving the dictionary
545        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        // Read some data not preserving the dictionary
558
559        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        // Can recreate with new dictionary as values is empty
600        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        // Can recreate with new dictionary as keys empty
621        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        // Cannot change dictionary as keys not empty
630        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    /// A dictionary requested with LargeUtf8 values must come back with LargeUtf8, not Utf8.
672    #[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    /// 128 unique strings fill Int8 keys to capacity (last index = 127 = i8::MAX).
695    /// A 129th unique string overflows and must return an error.
696    #[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    /// A colliding string repeated after its initial collision must reuse its key,
773    /// not be inserted again as a new dictionary entry.
774    #[test]
775    fn test_hash_collision_deduplication() {
776        let key_type = ArrowType::Int32;
777        let value_type = ArrowType::Utf8;
778
779        // "alpha", "beta", "beta" — all forced to share the same hash.
780        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    /// A dictionary requested with Binary values must come back with Binary, not Utf8.
806    #[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}