## Coverage Report

#### Created: 2025-11-22 06:00

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /Users/andrewlamb/Software/datafusion/datafusion/common/src/hash_utils.rs

    Line
    Count
    Source
    1
    // Licensed to the Apache Software Foundation (ASF) under one
    2
    // or more contributor license agreements.  See the NOTICE file
    3
    // distributed with this work for additional information
    4
    // regarding copyright ownership.  The ASF licenses this file
    5
    // to you under the Apache License, Version 2.0 (the
    6
    // "License"); you may not use this file except in compliance
    7
    // with the License.  You may obtain a copy of the License at
    8
    //
    9
    //   http://www.apache.org/licenses/LICENSE-2.0
    10
    //
    11
    // Unless required by applicable law or agreed to in writing,
    12
    // software distributed under the License is distributed on an
    13
    // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    14
    // KIND, either express or implied.  See the License for the
    15
    // specific language governing permissions and limitations
    16
    // under the License.
    17
    18
    //! Functionality used both on logical and physical plans
    19
    20
    use ahash::RandomState;
    21
    use arrow::array::types::{IntervalDayTime, IntervalMonthDayNano};
    22
    use arrow::array::*;
    23
    use arrow::datatypes::*;
    24
    #[cfg(not(feature = "force_hash_collisions"))]
    25
    use arrow::{downcast_dictionary_array, downcast_primitive_array};
    26
    27
    #[cfg(not(feature = "force_hash_collisions"))]
    28
    use crate::cast::{
    29
        as_binary_view_array, as_boolean_array, as_fixed_size_list_array,
    30
        as_generic_binary_array, as_large_list_array, as_list_array, as_map_array,
    31
        as_string_array, as_string_view_array, as_struct_array, as_union_array,
    32
    };
    33
    use crate::error::Result;
    34
    use crate::error::{_internal_datafusion_err, _internal_err};
    35
    use std::cell::RefCell;
    36
    37
    // Combines two hashes into one hash
    38
    #[inline]
    39
    108
    pub fn combine_hashes(l: u64, r: u64) -> u64 {
    40
    108
        let hash = (17 * 37u64).wrapping_add(l);
    41
    108
        hash.wrapping_mul(37).wrapping_add(r)
    42
    108
    }
    43
    44
    /// Maximum size for the thread-local hash buffer before truncation (4MB = 524,288 u64 elements).
    45
    /// The goal of this is to avoid unbounded memory growth that would appear as a memory leak.
    46
    /// We allow temporary allocations beyond this size, but after use the buffer is truncated
    47
    /// to this size.
    48
    const MAX_BUFFER_SIZE: usize = 524_288;
    49
    50
    thread_local! {
    51
        /// Thread-local buffer for hash computations to avoid repeated allocations.
    52
        /// The buffer is reused across calls and truncated if it exceeds MAX_BUFFER_SIZE.
    53
        /// Defaults to a capacity of 8192 u64 elements which is the default batch size.
    54
        /// This corresponds to 64KB of memory.
    55
        static HASH_BUFFER: RefCell<Vec<u64>> = const { RefCell::new(Vec::new()) };
    56
    }
    57
    58
    /// Creates hashes for the given arrays using a thread-local buffer, then calls the provided callback
    59
    /// with an immutable reference to the computed hashes.
    60
    ///
    61
    /// This function manages a thread-local buffer to avoid repeated allocations. The buffer is automatically
    62
    /// truncated if it exceeds `MAX_BUFFER_SIZE` after use.
    63
    ///
    64
    /// # Arguments
    65
    /// * `arrays` - The arrays to hash (must contain at least one array)
    66
    /// * `random_state` - The random state for hashing
    67
    /// * `callback` - A function that receives an immutable reference to the hash slice and returns a result
    68
    ///
    69
    /// # Errors
    70
    /// Returns an error if:
    71
    /// - No arrays are provided
    72
    /// - The function is called reentrantly (i.e., the callback invokes `with_hashes` again on the same thread)
    73
    /// - The function is called during or after thread destruction
    74
    ///
    75
    /// # Example
    76
    /// ```ignore
    77
    /// use datafusion_common::hash_utils::{with_hashes, RandomState};
    78
    /// use arrow::array::{Int32Array, ArrayRef};
    79
    /// use std::sync::Arc;
    80
    ///
    81
    /// let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
    82
    /// let random_state = RandomState::new();
    83
    ///
    84
    /// let result = with_hashes([&array], &random_state, |hashes| {
    85
    ///     // Use the hashes here
    86
    ///     Ok(hashes.len())
    87
    /// })?;
    88
    /// ```
    89
    181
    pub fn with_hashes<I, T, F, R>(
    90
    181
        arrays: I,
    91
    181
        random_state: &RandomState,
    92
    181
        callback: F,
    93
    181
    ) -> Result<R>
    94
    181
    where
    95
    181
        I: IntoIterator<Item = T>,
    96
    181
        T: AsDynArray,
    97
    181
        F: FnOnce(&[u64]) -> Result<R>,
    98
    {
    99
        // Peek at the first array to determine buffer size without fully collecting
    100
    181
        let mut iter = arrays.into_iter().peekable();
    101
    102
        // Get the required size from the first array
    103
    181
        let required_size = match iter.peek() {
    104
    181
            Some(arr) => arr.as_dyn_array().len(),
    105
    0
            None => return _internal_err!("with_hashes requires at least one array"),
    106
        };
    107
    108
    181
        HASH_BUFFER.try_with(|cell| {
    109
    181
            let mut buffer = cell.try_borrow_mut()
    110
    181
                .map_err(|_| _internal_datafusion_err!0("with_hashes cannot be called reentrantly on the same thread"0))?0;
    111
    112
            // Ensure buffer has sufficient length, clearing old values
    113
    181
            buffer.clear();
    114
    181
            buffer.resize(required_size, 0);
    115
    116
            // Create hashes in the buffer - this consumes the iterator
    117
    181
            create_hashes(iter, random_state, &mut buffer[..required_size])?0;
    118
    119
            // Execute the callback with an immutable slice
    120
    181
            let result = callback(&buffer[..required_size])?0;
    121
    122
            // Cleanup: truncate if buffer grew too large
    123
    181
            if buffer.capacity() > MAX_BUFFER_SIZE {
    124
    0
                buffer.truncate(MAX_BUFFER_SIZE);
    125
    0
                buffer.shrink_to_fit();
    126
    181
            }
    127
    128
    181
            Ok(result)
    129
    181
        }).map_err(|_| _internal_datafusion_err!0("with_hashes cannot access thread-local storage during or after thread destruction"0))?0
    130
    181
    }
    131
    132
    #[cfg(not(feature = "force_hash_collisions"))]
    133
    0
    fn hash_null(random_state: &RandomState, hashes_buffer: &'_ mut [u64], mul_col: bool) {
    134
    0
        if mul_col {
    135
    0
            hashes_buffer.iter_mut().for_each(|hash| {
    136
                // stable hash for null value
    137
    0
                *hash = combine_hashes(random_state.hash_one(1), *hash);
    138
    0
            })
    139
        } else {
    140
    0
            hashes_buffer.iter_mut().for_each(|hash| {
    141
    0
                *hash = random_state.hash_one(1);
    142
    0
            })
    143
        }
    144
    0
    }
    145
    146
    pub trait HashValue {
    147
        fn hash_one(&self, state: &RandomState) -> u64;
    148
    }
    149
    150
    impl<T: HashValue + ?Sized> HashValue for &T {
    151
    180
        fn hash_one(&self, state: &RandomState) -> u64 {
    152
    180
            T::hash_one(self, state)
    153
    180
        }
    154
    }
    155
    156
    macro_rules! hash_value {
    157
        ($($t:ty),+) => {
    158
            $(impl HashValue for $t {
    159
    735
                fn hash_one(&self, state: &RandomState) -> u64 {
    160
    735
                    state.hash_one(self)
    161
    735
                }
    162
            })+
    163
        };
    164
    }
    165
    hash_value!(i8, i16, i32, i64, i128, i256, u8, u16, u32, u64);
    166
    hash_value!(bool, str, [u8], IntervalDayTime, IntervalMonthDayNano);
    167
    168
    macro_rules! hash_float_value {
    169
        ($(($t:ty, $i:ty)),+) => {
    170
            $(impl HashValue for $t {
    171
    52
                fn hash_one(&self, state: &RandomState) -> u64 {
    172
    52
                    state.hash_one(<$i>::from_ne_bytes(self.to_ne_bytes()))
    173
    52
                }
    174
            })+
    175
        };
    176
    }
    177
    hash_float_value!((half::f16, u16), (f32, u32), (f64, u64));
    178
    179
    /// Builds hash values of PrimitiveArray and writes them into `hashes_buffer`
    180
    /// If `rehash==true` this combines the previous hash value in the buffer
    181
    /// with the new hash using `combine_hashes`
    182
    #[cfg(not(feature = "force_hash_collisions"))]
    183
    121
    fn hash_array_primitive<T>(
    184
    121
        array: &PrimitiveArray<T>,
    185
    121
        random_state: &RandomState,
    186
    121
        hashes_buffer: &mut [u64],
    187
    121
        rehash: bool,
    188
    121
    ) where
    189
    121
        T: ArrowPrimitiveType<Native: HashValue>,
    190
    {
    191
    121
        assert_eq!(
    192
    121
            hashes_buffer.len(),
    193
    121
            array.len(),
    194
    0
            "hashes_buffer and array should be of equal length"
    195
        );
    196
    197
    121
        if array.null_count() == 0 {
    198
    67
            if rehash {
    199
    22
                for (hash, &value) in hashes_buffer20.iter_mut20().zip20(array.values().iter()20) {
    200
    22
                    *hash = combine_hashes(value.hash_one(random_state), *hash);
    201
    22
                }
    202
            } else {
    203
    493
                for (hash, &value) in hashes_buffer47.iter_mut47().zip47(array.values().iter()47) {
    204
    493
                    *hash = value.hash_one(random_state);
    205
    493
                }
    206
            }
    207
    54
        } else if rehash {
    208
    6
            for (i, hash) in hashes_buffer.iter_mut().enumerate() {
    209
    6
                if !array.is_null(i) {
    210
    0
                    let value = unsafe { array.value_unchecked(i) };
    211
    0
                    *hash = combine_hashes(value.hash_one(random_state), *hash);
    212
    6
                }
    213
            }
    214
        } else {
    215
    132
            for (i, hash) in hashes_buffer48.iter_mut48().enumerate48() {
    216
    132
                if !array.is_null(i) {
    217
    84
                    let value = unsafe { array.value_unchecked(i) };
    218
    84
                    *hash = value.hash_one(random_state);
    219
    84
                }48
    220
            }
    221
        }
    222
    121
    }
    223
    224
    /// Hashes one array into the `hashes_buffer`
    225
    /// If `rehash==true` this combines the previous hash value in the buffer
    226
    /// with the new hash using `combine_hashes`
    227
    #[cfg(not(feature = "force_hash_collisions"))]
    228
    102
    fn hash_array<T>(
    229
    102
        array: &T,
    230
    102
        random_state: &RandomState,
    231
    102
        hashes_buffer: &mut [u64],
    232
    102
        rehash: bool,
    233
    102
    ) where
    234
    102
        T: ArrayAccessor,
    235
    102
        T::Item: HashValue,
    236
    {
    237
    102
        assert_eq!(
    238
    102
            hashes_buffer.len(),
    239
    102
            array.len(),
    240
    0
            "hashes_buffer and array should be of equal length"
    241
        );
    242
    243
    102
        if array.null_count() == 0 {
    244
    48
            if rehash {
    245
    28
                for (i, hash) in hashes_buffer14.iter_mut14().enumerate14() {
    246
    28
                    let value = unsafe { array.value_unchecked(i) };
    247
    28
                    *hash = combine_hashes(value.hash_one(random_state), *hash);
    248
    28
                }
    249
            } else {
    250
    60
                for (i, hash) in hashes_buffer34.iter_mut34().enumerate34() {
    251
    60
                    let value = unsafe { array.value_unchecked(i) };
    252
    60
                    *hash = value.hash_one(random_state);
    253
    60
                }
    254
            }
    255
    54
        } else if rehash {
    256
    4
            for (i, hash) in hashes_buffer2.iter_mut2().enumerate2() {
    257
    4
                if !array.is_null(i) {
    258
    2
                    let value = unsafe { array.value_unchecked(i) };
    259
    2
                    *hash = combine_hashes(value.hash_one(random_state), *hash);
    260
    2
                }
    261
            }
    262
        } else {
    263
    150
            for (i, hash) in hashes_buffer52.iter_mut52().enumerate52() {
    264
    150
                if !array.is_null(i) {
    265
    98
                    let value = unsafe { array.value_unchecked(i) };
    266
    98
                    *hash = value.hash_one(random_state);
    267
    98
                }52
    268
            }
    269
        }
    270
    102
    }
    271
    272
    /// Helper function to update hash for a dictionary key if the value is valid
    273
    #[cfg(not(feature = "force_hash_collisions"))]
    274
    #[inline]
    275
    0
    fn update_hash_for_dict_key(
    276
    0
        hash: &mut u64,
    277
    0
        dict_hashes: &[u64],
    278
    0
        dict_values: &dyn Array,
    279
    0
        idx: usize,
    280
    0
        multi_col: bool,
    281
    0
    ) {
    282
    0
        if dict_values.is_valid(idx) {
    283
    0
            if multi_col {
    284
    0
                *hash = combine_hashes(dict_hashes[idx], *hash);
    285
    0
            } else {
    286
    0
                *hash = dict_hashes[idx];
    287
    0
            }
    288
    0
        }
    289
        // no update for invalid dictionary value
    290
    0
    }
    291
    292
    /// Hash the values in a dictionary array
    293
    #[cfg(not(feature = "force_hash_collisions"))]
    294
    0
    fn hash_dictionary<K: ArrowDictionaryKeyType>(
    295
    0
        array: &DictionaryArray<K>,
    296
    0
        random_state: &RandomState,
    297
    0
        hashes_buffer: &mut [u64],
    298
    0
        multi_col: bool,
    299
    0
    ) -> Result<()> {
    300
        // Hash each dictionary value once, and then use that computed
    301
        // hash for each key value to avoid a potentially expensive
    302
        // redundant hashing for large dictionary elements (e.g. strings)
    303
    0
        let dict_values = array.values();
    304
    0
        let mut dict_hashes = vec![0; dict_values.len()];
    305
    0
        create_hashes([dict_values], random_state, &mut dict_hashes)?;
    306
    307
        // combine hash for each index in values
    308
    0
        for (hash, key) in hashes_buffer.iter_mut().zip(array.keys().iter()) {
    309
    0
            if let Some(key) = key {
    310
    0
                let idx = key.as_usize();
    311
    0
                update_hash_for_dict_key(
    312
    0
                    hash,
    313
    0
                    &dict_hashes,
    314
    0
                    dict_values.as_ref(),
    315
    0
                    idx,
    316
    0
                    multi_col,
    317
    0
                );
    318
    0
            } // no update for Null key
    319
        }
    320
    0
        Ok(())
    321
    0
    }
    322
    323
    #[cfg(not(feature = "force_hash_collisions"))]
    324
    42
    fn hash_struct_array(
    325
    42
        array: &StructArray,
    326
    42
        random_state: &RandomState,
    327
    42
        hashes_buffer: &mut [u64],
    328
    42
    ) -> Result<()> {
    329
    42
        let nulls = array.nulls();
    330
    42
        let row_len = array.len();
    331
    332
    42
        let valid_row_indices: Vec<usize> = if let Some(nulls4) = nulls {
    333
    4
            nulls.valid_indices().collect()
    334
        } else {
    335
    38
            (0..row_len).collect()
    336
        };
    337
    338
        // Create hashes for each row that combines the hashes over all the column at that row.
    339
    42
        let mut values_hashes = vec![0u64; row_len];
    340
    42
        create_hashes(array.columns(), random_state, &mut values_hashes)?0;
    341
    342
    98
        for i56 in valid_row_indices {
    343
    56
            let hash = &mut hashes_buffer[i];
    344
    56
            *hash = combine_hashes(*hash, values_hashes[i]);
    345
    56
        }
    346
    347
    42
        Ok(())
    348
    42
    }
    349
    350
    // only adding this `cfg` b/c this function is only used with this `cfg`
    351
    #[cfg(not(feature = "force_hash_collisions"))]
    352
    0
    fn hash_map_array(
    353
    0
        array: &MapArray,
    354
    0
        random_state: &RandomState,
    355
    0
        hashes_buffer: &mut [u64],
    356
    0
    ) -> Result<()> {
    357
    0
        let nulls = array.nulls();
    358
    0
        let offsets = array.offsets();
    359
    360
        // Create hashes for each entry in each row
    361
    0
        let mut values_hashes = vec![0u64; array.entries().len()];
    362
    0
        create_hashes(array.entries().columns(), random_state, &mut values_hashes)?;
    363
    364
        // Combine the hashes for entries on each row with each other and previous hash for that row
    365
    0
        if let Some(nulls) = nulls {
    366
    0
            for (i, (start, stop)) in offsets.iter().zip(offsets.iter().skip(1)).enumerate() {
    367
    0
                if nulls.is_valid(i) {
    368
    0
                    let hash = &mut hashes_buffer[i];
    369
    0
                    for values_hash in &values_hashes[start.as_usize()..stop.as_usize()] {
    370
    0
                        *hash = combine_hashes(*hash, *values_hash);
    371
    0
                    }
    372
    0
                }
    373
            }
    374
        } else {
    375
    0
            for (i, (start, stop)) in offsets.iter().zip(offsets.iter().skip(1)).enumerate() {
    376
    0
                let hash = &mut hashes_buffer[i];
    377
    0
                for values_hash in &values_hashes[start.as_usize()..stop.as_usize()] {
    378
    0
                    *hash = combine_hashes(*hash, *values_hash);
    379
    0
                }
    380
            }
    381
        }
    382
    383
    0
        Ok(())
    384
    0
    }
    385
    386
    #[cfg(not(feature = "force_hash_collisions"))]
    387
    0
    fn hash_list_array<OffsetSize>(
    388
    0
        array: &GenericListArray<OffsetSize>,
    389
    0
        random_state: &RandomState,
    390
    0
        hashes_buffer: &mut [u64],
    391
    0
    ) -> Result<()>
    392
    0
    where
    393
    0
        OffsetSize: OffsetSizeTrait,
    394
    {
    395
    0
        let values = array.values();
    396
    0
        let offsets = array.value_offsets();
    397
    0
        let nulls = array.nulls();
    398
    0
        let mut values_hashes = vec![0u64; values.len()];
    399
    0
        create_hashes([values], random_state, &mut values_hashes)?;
    400
    0
        if let Some(nulls) = nulls {
    401
    0
            for (i, (start, stop)) in offsets.iter().zip(offsets.iter().skip(1)).enumerate() {
    402
    0
                if nulls.is_valid(i) {
    403
    0
                    let hash = &mut hashes_buffer[i];
    404
    0
                    for values_hash in &values_hashes[start.as_usize()..stop.as_usize()] {
    405
    0
                        *hash = combine_hashes(*hash, *values_hash);
    406
    0
                    }
    407
    0
                }
    408
            }
    409
        } else {
    410
    0
            for (i, (start, stop)) in offsets.iter().zip(offsets.iter().skip(1)).enumerate() {
    411
    0
                let hash = &mut hashes_buffer[i];
    412
    0
                for values_hash in &values_hashes[start.as_usize()..stop.as_usize()] {
    413
    0
                    *hash = combine_hashes(*hash, *values_hash);
    414
    0
                }
    415
            }
    416
        }
    417
    0
        Ok(())
    418
    0
    }
    419
    420
    #[cfg(not(feature = "force_hash_collisions"))]
    421
    0
    fn hash_union_array(
    422
    0
        array: &UnionArray,
    423
    0
        random_state: &RandomState,
    424
    0
        hashes_buffer: &mut [u64],
    425
    0
    ) -> Result<()> {
    426
        use std::collections::HashMap;
    427
    428
    0
        let DataType::Union(union_fields, _mode) = array.data_type() else {
    429
    0
            unreachable!()
    430
        };
    431
    432
    0
        let mut child_hashes = HashMap::with_capacity(union_fields.len());
    433
    434
    0
        for (type_id, _field) in union_fields.iter() {
    435
    0
            let child = array.child(type_id);
    436
    0
            let mut child_hash_buffer = vec![0; child.len()];
    437
    0
            create_hashes([child], random_state, &mut child_hash_buffer)?;
    438
    439
    0
            child_hashes.insert(type_id, child_hash_buffer);
    440
        }
    441
    442
        #[expect(clippy::needless_range_loop)]
    443
    0
        for i in 0..array.len() {
    444
    0
            let type_id = array.type_id(i);
    445
    0
            let child_offset = array.value_offset(i);
    446
    0
    447
    0
            let child_hash = child_hashes.get(&type_id).expect("invalid type_id");
    448
    0
            hashes_buffer[i] = combine_hashes(hashes_buffer[i], child_hash[child_offset]);
    449
    0
        }
    450
    451
    0
        Ok(())
    452
    0
    }
    453
    454
    #[cfg(not(feature = "force_hash_collisions"))]
    455
    0
    fn hash_fixed_list_array(
    456
    0
        array: &FixedSizeListArray,
    457
    0
        random_state: &RandomState,
    458
    0
        hashes_buffer: &mut [u64],
    459
    0
    ) -> Result<()> {
    460
    0
        let values = array.values();
    461
    0
        let value_length = array.value_length() as usize;
    462
    0
        let nulls = array.nulls();
    463
    0
        let mut values_hashes = vec![0u64; values.len()];
    464
    0
        create_hashes([values], random_state, &mut values_hashes)?;
    465
    0
        if let Some(nulls) = nulls {
    466
    0
            for i in 0..array.len() {
    467
    0
                if nulls.is_valid(i) {
    468
    0
                    let hash = &mut hashes_buffer[i];
    469
    0
                    for values_hash in
    470
    0
                        &values_hashes[i * value_length..(i + 1) * value_length]
    471
    0
                    {
    472
    0
                        *hash = combine_hashes(*hash, *values_hash);
    473
    0
                    }
    474
    0
                }
    475
            }
    476
        } else {
    477
    0
            for i in 0..array.len() {
    478
    0
                let hash = &mut hashes_buffer[i];
    479
    0
                for values_hash in &values_hashes[i * value_length..(i + 1) * value_length] {
    480
    0
                    *hash = combine_hashes(*hash, *values_hash);
    481
    0
                }
    482
            }
    483
        }
    484
    0
        Ok(())
    485
    0
    }
    486
    487
    /// Internal helper function that hashes a single array and either initializes or combines
    488
    /// the hash values in the buffer.
    489
    #[cfg(not(feature = "force_hash_collisions"))]
    490
    265
    fn hash_single_array(
    491
    265
        array: &dyn Array,
    492
    265
        random_state: &RandomState,
    493
    265
        hashes_buffer: &mut [u64],
    494
    265
        rehash: bool,
    495
    265
    ) -> Result<()> {
    496
    265
        downcast_primitive_array! {
    497
    0
            array => hash_array_primitive(array, random_state, hashes_buffer, rehash),
    498
    0
            DataType::Null => hash_null(random_state, hashes_buffer, rehash),
    499
    8
            DataType::Boolean => hash_array(&as_boolean_array(array)?0, random_state, hashes_buffer, rehash),
    500
    54
            DataType::Utf8 => hash_array(&as_string_array(array)?0, random_state, hashes_buffer, rehash),
    501
    8
            DataType::Utf8View => hash_array(&as_string_view_array(array)?0, random_state, hashes_buffer, rehash),
    502
    8
            DataType::LargeUtf8 => hash_array(&as_largestring_array(array), random_state, hashes_buffer, rehash),
    503
    8
            DataType::Binary => hash_array(&as_generic_binary_array::<i32>(array)?0, random_state, hashes_buffer, rehash),
    504
    8
            DataType::BinaryView => hash_array(&as_binary_view_array(array)?0, random_state, hashes_buffer, rehash),
    505
    8
            DataType::LargeBinary => hash_array(&as_generic_binary_array::<i64>(array)?0, random_state, hashes_buffer, rehash),
    506
            DataType::FixedSizeBinary(_) => {
    507
    0
                let array: &FixedSizeBinaryArray = array.as_any().downcast_ref().unwrap();
    508
    0
                hash_array(&array, random_state, hashes_buffer, rehash)
    509
            }
    510
    0
            DataType::Dictionary(_, _) => downcast_dictionary_array! {
    511
    0
                array => hash_dictionary(array, random_state, hashes_buffer, rehash)?,
    512
    0
                _ => unreachable!()
    513
            }
    514
            DataType::Struct(_) => {
    515
    42
                let array = as_struct_array(array)?0;
    516
    42
                hash_struct_array(array, random_state, hashes_buffer)?0;
    517
            }
    518
            DataType::List(_) => {
    519
    0
                let array = as_list_array(array)?;
    520
    0
                hash_list_array(array, random_state, hashes_buffer)?;
    521
            }
    522
            DataType::LargeList(_) => {
    523
    0
                let array = as_large_list_array(array)?;
    524
    0
                hash_list_array(array, random_state, hashes_buffer)?;
    525
            }
    526
            DataType::Map(_, _) => {
    527
    0
                let array = as_map_array(array)?;
    528
    0
                hash_map_array(array, random_state, hashes_buffer)?;
    529
            }
    530
            DataType::FixedSizeList(_,_) => {
    531
    0
                let array = as_fixed_size_list_array(array)?;
    532
    0
                hash_fixed_list_array(array, random_state, hashes_buffer)?;
    533
            }
    534
            DataType::Union(_, _) => {
    535
    0
                let array = as_union_array(array)?;
    536
    0
                hash_union_array(array, random_state, hashes_buffer)?;
    537
            }
    538
            _ => {
    539
                // This is internal because we should have caught this before.
    540
    0
                return _internal_err!(
    541
    0
                    "Unsupported data type in hasher: {}",
    542
    0
                    array.data_type()
    543
                );
    544
            }
    545
        }
    546
    265
        Ok(())
    547
    265
    }
    548
    549
    /// Test version of `hash_single_array` that forces all hashes to collide to zero.
    550
    #[cfg(feature = "force_hash_collisions")]
    551
    fn hash_single_array(
    552
        _array: &dyn Array,
    553
        _random_state: &RandomState,
    554
        hashes_buffer: &mut [u64],
    555
        _rehash: bool,
    556
    ) -> Result<()> {
    557
        for hash in hashes_buffer.iter_mut() {
    558
            *hash = 0
    559
        }
    560
        Ok(())
    561
    }
    562
    563
    /// Something that can be returned as a `&dyn Array`.
    564
    ///
    565
    /// We want `create_hashes` to accept either `&dyn Array` or `ArrayRef`,
    566
    /// and this seems the best way to do so.
    567
    ///
    568
    /// We tried having it accept `AsRef<dyn Array>`
    569
    /// but that is not implemented for and cannot be implemented for
    570
    /// `&dyn Array` so callers that have the latter would not be able
    571
    /// to call `create_hashes` directly. This shim trait makes it possible.
    572
    pub trait AsDynArray {
    573
        fn as_dyn_array(&self) -> &dyn Array;
    574
    }
    575
    576
    impl AsDynArray for dyn Array {
    577
    0
        fn as_dyn_array(&self) -> &dyn Array {
    578
    0
            self
    579
    0
        }
    580
    }
    581
    582
    impl AsDynArray for &dyn Array {
    583
    172
        fn as_dyn_array(&self) -> &dyn Array {
    584
    172
            *self
    585
    172
        }
    586
    }
    587
    588
    impl AsDynArray for ArrayRef {
    589
    0
        fn as_dyn_array(&self) -> &dyn Array {
    590
    0
            self.as_ref()
    591
    0
        }
    592
    }
    593
    594
    impl AsDynArray for &ArrayRef {
    595
    274
        fn as_dyn_array(&self) -> &dyn Array {
    596
    274
            self.as_ref()
    597
    274
        }
    598
    }
    599
    600
    /// Creates hash values for every row, based on the values in the columns.
    601
    ///
    602
    /// The number of rows to hash is determined by `hashes_buffer.len()`.
    603
    /// `hashes_buffer` should be pre-sized appropriately.
    604
    223
    pub fn create_hashes<'a, I, T>(
    605
    223
        arrays: I,
    606
    223
        random_state: &RandomState,
    607
    223
        hashes_buffer: &'a mut [u64],
    608
    223
    ) -> Result<&'a mut [u64]>
    609
    223
    where
    610
    223
        I: IntoIterator<Item = T>,
    611
    223
        T: AsDynArray,
    612
    {
    613
    265
        for (i, array) in arrays223.into_iter223().enumerate223() {
    614
            // combine hashes with `combine_hashes` for all columns besides the first
    615
    265
            let rehash = i >= 1;
    616
    265
            hash_single_array(array.as_dyn_array(), random_state, hashes_buffer, rehash)?0;
    617
        }
    618
    223
        Ok(hashes_buffer)
    619
    223
    }
    620
    621
    #[cfg(test)]
    622
    mod tests {
    623
        use std::sync::Arc;
    624
    625
        use arrow::array::*;
    626
        #[cfg(not(feature = "force_hash_collisions"))]
    627
        use arrow::datatypes::*;
    628
    629
        use super::*;
    630
    631
        #[test]
    632
        fn create_hashes_for_decimal_array() -> Result<()> {
    633
            let array = vec![1, 2, 3, 4]
    634
                .into_iter()
    635
                .map(Some)
    636
                .collect::<Decimal128Array>()
    637
                .with_precision_and_scale(20, 3)
    638
                .unwrap();
    639
            let array_ref: ArrayRef = Arc::new(array);
    640
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    641
            let hashes_buff = &mut vec![0; array_ref.len()];
    642
            let hashes = create_hashes(&[array_ref], &random_state, hashes_buff)?;
    643
            assert_eq!(hashes.len(), 4);
    644
            Ok(())
    645
        }
    646
    647
        #[test]
    648
        fn create_hashes_for_empty_fixed_size_lit() -> Result<()> {
    649
            let empty_array = FixedSizeListBuilder::new(StringBuilder::new(), 1).finish();
    650
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    651
            let hashes_buff = &mut [0; 0];
    652
            let hashes = create_hashes(
    653
                &[Arc::new(empty_array) as ArrayRef],
    654
                &random_state,
    655
                hashes_buff,
    656
            )?;
    657
            assert_eq!(hashes, &Vec::<u64>::new());
    658
            Ok(())
    659
        }
    660
    661
        #[test]
    662
        fn create_hashes_for_float_arrays() -> Result<()> {
    663
            let f32_arr: ArrayRef =
    664
                Arc::new(Float32Array::from(vec![0.12, 0.5, 1f32, 444.7]));
    665
            let f64_arr: ArrayRef =
    666
                Arc::new(Float64Array::from(vec![0.12, 0.5, 1f64, 444.7]));
    667
    668
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    669
            let hashes_buff = &mut vec![0; f32_arr.len()];
    670
            let hashes = create_hashes(&[f32_arr], &random_state, hashes_buff)?;
    671
            assert_eq!(hashes.len(), 4,);
    672
    673
            let hashes = create_hashes(&[f64_arr], &random_state, hashes_buff)?;
    674
            assert_eq!(hashes.len(), 4,);
    675
    676
            Ok(())
    677
        }
    678
    679
        macro_rules! create_hash_binary {
    680
            ($NAME:ident, $ARRAY:ty) => {
    681
                #[cfg(not(feature = "force_hash_collisions"))]
    682
                #[test]
    683
                fn $NAME() {
    684
                    let binary = [
    685
                        Some(b"short".to_byte_slice()),
    686
                        None,
    687
                        Some(b"long but different 12 bytes string"),
    688
                        Some(b"short2"),
    689
                        Some(b"Longer than 12 bytes string"),
    690
                        Some(b"short"),
    691
                        Some(b"Longer than 12 bytes string"),
    692
                    ];
    693
    694
                    let binary_array: ArrayRef =
    695
                        Arc::new(binary.iter().cloned().collect::<$ARRAY>());
    696
                    let ref_array: ArrayRef =
    697
                        Arc::new(binary.iter().cloned().collect::<BinaryArray>());
    698
    699
                    let random_state = RandomState::with_seeds(0, 0, 0, 0);
    700
    701
                    let mut binary_hashes = vec![0; binary.len()];
    702
                    create_hashes(&[binary_array], &random_state, &mut binary_hashes)
    703
                        .unwrap();
    704
    705
                    let mut ref_hashes = vec![0; binary.len()];
    706
                    create_hashes(&[ref_array], &random_state, &mut ref_hashes).unwrap();
    707
    708
                    // Null values result in a zero hash,
    709
                    for (val, hash) in binary.iter().zip(binary_hashes.iter()) {
    710
                        match val {
    711
                            Some(_) => assert_ne!(*hash, 0),
    712
                            None => assert_eq!(*hash, 0),
    713
                        }
    714
                    }
    715
    716
                    // same logical values should hash to the same hash value
    717
                    assert_eq!(binary_hashes, ref_hashes);
    718
    719
                    // Same values should map to same hash values
    720
                    assert_eq!(binary[0], binary[5]);
    721
                    assert_eq!(binary[4], binary[6]);
    722
    723
                    // different binary should map to different hash values
    724
                    assert_ne!(binary[0], binary[2]);
    725
                }
    726
            };
    727
        }
    728
    729
        create_hash_binary!(binary_array, BinaryArray);
    730
        create_hash_binary!(binary_view_array, BinaryViewArray);
    731
    732
        #[test]
    733
        fn create_hashes_fixed_size_binary() -> Result<()> {
    734
            let input_arg = vec![vec![1, 2], vec![5, 6], vec![5, 6]];
    735
            let fixed_size_binary_array: ArrayRef =
    736
                Arc::new(FixedSizeBinaryArray::try_from_iter(input_arg.into_iter()).unwrap());
    737
    738
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    739
            let hashes_buff = &mut vec![0; fixed_size_binary_array.len()];
    740
            let hashes =
    741
                create_hashes(&[fixed_size_binary_array], &random_state, hashes_buff)?;
    742
            assert_eq!(hashes.len(), 3,);
    743
    744
            Ok(())
    745
        }
    746
    747
        macro_rules! create_hash_string {
    748
            ($NAME:ident, $ARRAY:ty) => {
    749
                #[cfg(not(feature = "force_hash_collisions"))]
    750
                #[test]
    751
                fn $NAME() {
    752
                    let strings = [
    753
                        Some("short"),
    754
                        None,
    755
                        Some("long but different 12 bytes string"),
    756
                        Some("short2"),
    757
                        Some("Longer than 12 bytes string"),
    758
                        Some("short"),
    759
                        Some("Longer than 12 bytes string"),
    760
                    ];
    761
    762
                    let string_array: ArrayRef =
    763
                        Arc::new(strings.iter().cloned().collect::<$ARRAY>());
    764
                    let dict_array: ArrayRef = Arc::new(
    765
                        strings
    766
                            .iter()
    767
                            .cloned()
    768
                            .collect::<DictionaryArray<Int8Type>>(),
    769
                    );
    770
    771
                    let random_state = RandomState::with_seeds(0, 0, 0, 0);
    772
    773
                    let mut string_hashes = vec![0; strings.len()];
    774
                    create_hashes(&[string_array], &random_state, &mut string_hashes)
    775
                        .unwrap();
    776
    777
                    let mut dict_hashes = vec![0; strings.len()];
    778
                    create_hashes(&[dict_array], &random_state, &mut dict_hashes).unwrap();
    779
    780
                    // Null values result in a zero hash,
    781
                    for (val, hash) in strings.iter().zip(string_hashes.iter()) {
    782
                        match val {
    783
                            Some(_) => assert_ne!(*hash, 0),
    784
                            None => assert_eq!(*hash, 0),
    785
                        }
    786
                    }
    787
    788
                    // same logical values should hash to the same hash value
    789
                    assert_eq!(string_hashes, dict_hashes);
    790
    791
                    // Same values should map to same hash values
    792
                    assert_eq!(strings[0], strings[5]);
    793
                    assert_eq!(strings[4], strings[6]);
    794
    795
                    // different strings should map to different hash values
    796
                    assert_ne!(strings[0], strings[2]);
    797
                }
    798
            };
    799
        }
    800
    801
        create_hash_string!(string_array, StringArray);
    802
        create_hash_string!(large_string_array, LargeStringArray);
    803
        create_hash_string!(string_view_array, StringArray);
    804
        create_hash_string!(dict_string_array, DictionaryArray<Int8Type>);
    805
    806
        #[test]
    807
        // Tests actual values of hashes, which are different if forcing collisions
    808
        #[cfg(not(feature = "force_hash_collisions"))]
    809
        fn create_hashes_for_dict_arrays() {
    810
            let strings = [Some("foo"), None, Some("bar"), Some("foo"), None];
    811
    812
            let string_array: ArrayRef =
    813
                Arc::new(strings.iter().cloned().collect::<StringArray>());
    814
            let dict_array: ArrayRef = Arc::new(
    815
                strings
    816
                    .iter()
    817
                    .cloned()
    818
                    .collect::<DictionaryArray<Int8Type>>(),
    819
            );
    820
    821
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    822
    823
            let mut string_hashes = vec![0; strings.len()];
    824
            create_hashes(&[string_array], &random_state, &mut string_hashes).unwrap();
    825
    826
            let mut dict_hashes = vec![0; strings.len()];
    827
            create_hashes(&[dict_array], &random_state, &mut dict_hashes).unwrap();
    828
    829
            // Null values result in a zero hash,
    830
            for (val, hash) in strings.iter().zip(string_hashes.iter()) {
    831
                match val {
    832
                    Some(_) => assert_ne!(*hash, 0),
    833
                    None => assert_eq!(*hash, 0),
    834
                }
    835
            }
    836
    837
            // same logical values should hash to the same hash value
    838
            assert_eq!(string_hashes, dict_hashes);
    839
    840
            // Same values should map to same hash values
    841
            assert_eq!(strings[1], strings[4]);
    842
            assert_eq!(dict_hashes[1], dict_hashes[4]);
    843
            assert_eq!(strings[0], strings[3]);
    844
            assert_eq!(dict_hashes[0], dict_hashes[3]);
    845
    846
            // different strings should map to different hash values
    847
            assert_ne!(strings[0], strings[2]);
    848
            assert_ne!(dict_hashes[0], dict_hashes[2]);
    849
        }
    850
    851
        #[test]
    852
        // Tests actual values of hashes, which are different if forcing collisions
    853
        #[cfg(not(feature = "force_hash_collisions"))]
    854
        fn create_hashes_for_list_arrays() {
    855
            let data = vec![
    856
                Some(vec![Some(0), Some(1), Some(2)]),
    857
                None,
    858
                Some(vec![Some(3), None, Some(5)]),
    859
                Some(vec![Some(3), None, Some(5)]),
    860
                None,
    861
                Some(vec![Some(0), Some(1), Some(2)]),
    862
                Some(vec![]),
    863
            ];
    864
            let list_array =
    865
                Arc::new(ListArray::from_iter_primitive::<Int32Type, _, _>(data)) as ArrayRef;
    866
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    867
            let mut hashes = vec![0; list_array.len()];
    868
            create_hashes(&[list_array], &random_state, &mut hashes).unwrap();
    869
            assert_eq!(hashes[0], hashes[5]);
    870
            assert_eq!(hashes[1], hashes[4]);
    871
            assert_eq!(hashes[2], hashes[3]);
    872
            assert_eq!(hashes[1], hashes[6]); // null vs empty list
    873
        }
    874
    875
        #[test]
    876
        // Tests actual values of hashes, which are different if forcing collisions
    877
        #[cfg(not(feature = "force_hash_collisions"))]
    878
        fn create_hashes_for_fixed_size_list_arrays() {
    879
            let data = vec![
    880
                Some(vec![Some(0), Some(1), Some(2)]),
    881
                None,
    882
                Some(vec![Some(3), None, Some(5)]),
    883
                Some(vec![Some(3), None, Some(5)]),
    884
                None,
    885
                Some(vec![Some(0), Some(1), Some(2)]),
    886
            ];
    887
            let list_array =
    888
                Arc::new(FixedSizeListArray::from_iter_primitive::<Int32Type, _, _>(
    889
                    data, 3,
    890
                )) as ArrayRef;
    891
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    892
            let mut hashes = vec![0; list_array.len()];
    893
            create_hashes(&[list_array], &random_state, &mut hashes).unwrap();
    894
            assert_eq!(hashes[0], hashes[5]);
    895
            assert_eq!(hashes[1], hashes[4]);
    896
            assert_eq!(hashes[2], hashes[3]);
    897
        }
    898
    899
        #[test]
    900
        // Tests actual values of hashes, which are different if forcing collisions
    901
        #[cfg(not(feature = "force_hash_collisions"))]
    902
        fn create_hashes_for_struct_arrays() {
    903
            use arrow::buffer::Buffer;
    904
    905
            let boolarr = Arc::new(BooleanArray::from(vec![
    906
                false, false, true, true, true, true,
    907
            ]));
    908
            let i32arr = Arc::new(Int32Array::from(vec![10, 10, 20, 20, 30, 31]));
    909
    910
            let struct_array = StructArray::from((
    911
                vec![
    912
                    (
    913
                        Arc::new(Field::new("bool", DataType::Boolean, false)),
    914
                        Arc::clone(&boolarr) as ArrayRef,
    915
                    ),
    916
                    (
    917
                        Arc::new(Field::new("i32", DataType::Int32, false)),
    918
                        Arc::clone(&i32arr) as ArrayRef,
    919
                    ),
    920
                    (
    921
                        Arc::new(Field::new("i32", DataType::Int32, false)),
    922
                        Arc::clone(&i32arr) as ArrayRef,
    923
                    ),
    924
                    (
    925
                        Arc::new(Field::new("bool", DataType::Boolean, false)),
    926
                        Arc::clone(&boolarr) as ArrayRef,
    927
                    ),
    928
                ],
    929
                Buffer::from(&[0b001011]),
    930
            ));
    931
    932
            assert!(struct_array.is_valid(0));
    933
            assert!(struct_array.is_valid(1));
    934
            assert!(struct_array.is_null(2));
    935
            assert!(struct_array.is_valid(3));
    936
            assert!(struct_array.is_null(4));
    937
            assert!(struct_array.is_null(5));
    938
    939
            let array = Arc::new(struct_array) as ArrayRef;
    940
    941
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    942
            let mut hashes = vec![0; array.len()];
    943
            create_hashes(&[array], &random_state, &mut hashes).unwrap();
    944
            assert_eq!(hashes[0], hashes[1]);
    945
            // same value but the third row ( hashes[2] ) is null
    946
            assert_ne!(hashes[2], hashes[3]);
    947
            // different values but both are null
    948
            assert_eq!(hashes[4], hashes[5]);
    949
        }
    950
    951
        #[test]
    952
        // Tests actual values of hashes, which are different if forcing collisions
    953
        #[cfg(not(feature = "force_hash_collisions"))]
    954
        fn create_hashes_for_struct_arrays_more_column_than_row() {
    955
            let struct_array = StructArray::from(vec![
    956
                (
    957
                    Arc::new(Field::new("bool", DataType::Boolean, false)),
    958
                    Arc::new(BooleanArray::from(vec![false, false])) as ArrayRef,
    959
                ),
    960
                (
    961
                    Arc::new(Field::new("i32-1", DataType::Int32, false)),
    962
                    Arc::new(Int32Array::from(vec![10, 10])) as ArrayRef,
    963
                ),
    964
                (
    965
                    Arc::new(Field::new("i32-2", DataType::Int32, false)),
    966
                    Arc::new(Int32Array::from(vec![10, 10])) as ArrayRef,
    967
                ),
    968
                (
    969
                    Arc::new(Field::new("i32-3", DataType::Int32, false)),
    970
                    Arc::new(Int32Array::from(vec![10, 10])) as ArrayRef,
    971
                ),
    972
            ]);
    973
    974
            assert!(struct_array.is_valid(0));
    975
            assert!(struct_array.is_valid(1));
    976
    977
            let array = Arc::new(struct_array) as ArrayRef;
    978
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    979
            let mut hashes = vec![0; array.len()];
    980
            create_hashes(&[array], &random_state, &mut hashes).unwrap();
    981
            assert_eq!(hashes[0], hashes[1]);
    982
        }
    983
    984
        #[test]
    985
        // Tests actual values of hashes, which are different if forcing collisions
    986
        #[cfg(not(feature = "force_hash_collisions"))]
    987
        fn create_hashes_for_map_arrays() {
    988
            let mut builder =
    989
                MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
    990
            // Row 0
    991
            builder.keys().append_value("key1");
    992
            builder.keys().append_value("key2");
    993
            builder.values().append_value(1);
    994
            builder.values().append_value(2);
    995
            builder.append(true).unwrap();
    996
            // Row 1
    997
            builder.keys().append_value("key1");
    998
            builder.keys().append_value("key2");
    999
            builder.values().append_value(1);
    1000
            builder.values().append_value(2);
    1001
            builder.append(true).unwrap();
    1002
            // Row 2
    1003
            builder.keys().append_value("key1");
    1004
            builder.keys().append_value("key2");
    1005
            builder.values().append_value(1);
    1006
            builder.values().append_value(3);
    1007
            builder.append(true).unwrap();
    1008
            // Row 3
    1009
            builder.keys().append_value("key1");
    1010
            builder.keys().append_value("key3");
    1011
            builder.values().append_value(1);
    1012
            builder.values().append_value(2);
    1013
            builder.append(true).unwrap();
    1014
            // Row 4
    1015
            builder.keys().append_value("key1");
    1016
            builder.values().append_value(1);
    1017
            builder.append(true).unwrap();
    1018
            // Row 5
    1019
            builder.keys().append_value("key1");
    1020
            builder.values().append_null();
    1021
            builder.append(true).unwrap();
    1022
            // Row 6
    1023
            builder.append(true).unwrap();
    1024
            // Row 7
    1025
            builder.keys().append_value("key1");
    1026
            builder.values().append_value(1);
    1027
            builder.append(false).unwrap();
    1028
    1029
            let array = Arc::new(builder.finish()) as ArrayRef;
    1030
    1031
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1032
            let mut hashes = vec![0; array.len()];
    1033
            create_hashes(&[array], &random_state, &mut hashes).unwrap();
    1034
            assert_eq!(hashes[0], hashes[1]); // same value
    1035
            assert_ne!(hashes[0], hashes[2]); // different value
    1036
            assert_ne!(hashes[0], hashes[3]); // different key
    1037
            assert_ne!(hashes[0], hashes[4]); // missing an entry
    1038
            assert_ne!(hashes[4], hashes[5]); // filled vs null value
    1039
            assert_eq!(hashes[6], hashes[7]); // empty vs null map
    1040
        }
    1041
    1042
        #[test]
    1043
        // Tests actual values of hashes, which are different if forcing collisions
    1044
        #[cfg(not(feature = "force_hash_collisions"))]
    1045
        fn create_multi_column_hash_for_dict_arrays() {
    1046
            let strings1 = [Some("foo"), None, Some("bar")];
    1047
            let strings2 = [Some("blarg"), Some("blah"), None];
    1048
    1049
            let string_array: ArrayRef =
    1050
                Arc::new(strings1.iter().cloned().collect::<StringArray>());
    1051
            let dict_array: ArrayRef = Arc::new(
    1052
                strings2
    1053
                    .iter()
    1054
                    .cloned()
    1055
                    .collect::<DictionaryArray<Int32Type>>(),
    1056
            );
    1057
    1058
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1059
    1060
            let mut one_col_hashes = vec![0; strings1.len()];
    1061
            create_hashes(
    1062
                &[Arc::clone(&dict_array) as ArrayRef],
    1063
                &random_state,
    1064
                &mut one_col_hashes,
    1065
            )
    1066
            .unwrap();
    1067
    1068
            let mut two_col_hashes = vec![0; strings1.len()];
    1069
            create_hashes(
    1070
                &[dict_array, string_array],
    1071
                &random_state,
    1072
                &mut two_col_hashes,
    1073
            )
    1074
            .unwrap();
    1075
    1076
            assert_eq!(one_col_hashes.len(), 3);
    1077
            assert_eq!(two_col_hashes.len(), 3);
    1078
    1079
            assert_ne!(one_col_hashes, two_col_hashes);
    1080
        }
    1081
    1082
        #[test]
    1083
        fn test_create_hashes_from_arrays() {
    1084
            let int_array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4]));
    1085
            let float_array: ArrayRef =
    1086
                Arc::new(Float64Array::from(vec![1.0, 2.0, 3.0, 4.0]));
    1087
    1088
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1089
            let hashes_buff = &mut vec![0; int_array.len()];
    1090
            let hashes =
    1091
                create_hashes(&[int_array, float_array], &random_state, hashes_buff).unwrap();
    1092
            assert_eq!(hashes.len(), 4,);
    1093
        }
    1094
    1095
        #[test]
    1096
        fn test_create_hashes_from_dyn_arrays() {
    1097
            let int_array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4]));
    1098
            let float_array: ArrayRef =
    1099
                Arc::new(Float64Array::from(vec![1.0, 2.0, 3.0, 4.0]));
    1100
    1101
            // Verify that we can call create_hashes with only &dyn Array
    1102
            fn test(arr1: &dyn Array, arr2: &dyn Array) {
    1103
                let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1104
                let hashes_buff = &mut vec![0; arr1.len()];
    1105
                let hashes = create_hashes([arr1, arr2], &random_state, hashes_buff).unwrap();
    1106
                assert_eq!(hashes.len(), 4,);
    1107
            }
    1108
            test(&*int_array, &*float_array);
    1109
        }
    1110
    1111
        #[test]
    1112
        fn test_create_hashes_equivalence() {
    1113
            let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4]));
    1114
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1115
    1116
            let mut hashes1 = vec![0; array.len()];
    1117
            create_hashes(
    1118
                &[Arc::clone(&array) as ArrayRef],
    1119
                &random_state,
    1120
                &mut hashes1,
    1121
            )
    1122
            .unwrap();
    1123
    1124
            let mut hashes2 = vec![0; array.len()];
    1125
            create_hashes([array], &random_state, &mut hashes2).unwrap();
    1126
    1127
            assert_eq!(hashes1, hashes2);
    1128
        }
    1129
    1130
        #[test]
    1131
        fn test_with_hashes() {
    1132
            let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4]));
    1133
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1134
    1135
            // Test that with_hashes produces the same results as create_hashes
    1136
            let mut expected_hashes = vec![0; array.len()];
    1137
            create_hashes([&array], &random_state, &mut expected_hashes).unwrap();
    1138
    1139
            let result = with_hashes([&array], &random_state, |hashes| {
    1140
                assert_eq!(hashes.len(), 4);
    1141
                // Verify hashes match expected values
    1142
                assert_eq!(hashes, &expected_hashes[..]);
    1143
                // Return a copy of the hashes
    1144
                Ok(hashes.to_vec())
    1145
            })
    1146
            .unwrap();
    1147
    1148
            // Verify callback result is returned correctly
    1149
            assert_eq!(result, expected_hashes);
    1150
        }
    1151
    1152
        #[test]
    1153
        fn test_with_hashes_multi_column() {
    1154
            let int_array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
    1155
            let str_array: ArrayRef = Arc::new(StringArray::from(vec!["a", "b", "c"]));
    1156
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1157
    1158
            // Test multi-column hashing
    1159
            let mut expected_hashes = vec![0; int_array.len()];
    1160
            create_hashes(
    1161
                [&int_array, &str_array],
    1162
                &random_state,
    1163
                &mut expected_hashes,
    1164
            )
    1165
            .unwrap();
    1166
    1167
            with_hashes([&int_array, &str_array], &random_state, |hashes| {
    1168
                assert_eq!(hashes.len(), 3);
    1169
                assert_eq!(hashes, &expected_hashes[..]);
    1170
                Ok(())
    1171
            })
    1172
            .unwrap();
    1173
        }
    1174
    1175
        #[test]
    1176
        fn test_with_hashes_empty_arrays() {
    1177
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1178
    1179
            // Test that passing no arrays returns an error
    1180
            let empty: [&ArrayRef; 0] = [];
    1181
            let result = with_hashes(empty, &random_state, |_hashes| Ok(()));
    1182
    1183
            assert!(result.is_err());
    1184
            assert!(result
    1185
                .unwrap_err()
    1186
                .to_string()
    1187
                .contains("requires at least one array"));
    1188
        }
    1189
    1190
        #[test]
    1191
        fn test_with_hashes_reentrancy() {
    1192
            let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
    1193
            let array2: ArrayRef = Arc::new(Int32Array::from(vec![4, 5, 6]));
    1194
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1195
    1196
            // Test that reentrant calls return an error instead of panicking
    1197
            let result = with_hashes([&array], &random_state, |_hashes| {
    1198
                // Try to call with_hashes again inside the callback
    1199
                with_hashes([&array2], &random_state, |_inner_hashes| Ok(()))
    1200
            });
    1201
    1202
            assert!(result.is_err());
    1203
            let err_msg = result.unwrap_err().to_string();
    1204
            assert!(
    1205
                err_msg.contains("reentrantly") || err_msg.contains("cannot be called"),
    1206
                "Error message should mention reentrancy: {err_msg}",
    1207
            );
    1208
        }
    1209
    1210
        #[test]
    1211
        #[cfg(not(feature = "force_hash_collisions"))]
    1212
        fn create_hashes_for_sparse_union_arrays() {
    1213
            // logical array: [int(5), str("foo"), int(10), int(5)]
    1214
            let int_array = Int32Array::from(vec![Some(5), None, Some(10), Some(5)]);
    1215
            let str_array = StringArray::from(vec![None, Some("foo"), None, None]);
    1216
    1217
            let type_ids = vec![0_i8, 1, 0, 0].into();
    1218
            let children = vec![
    1219
                Arc::new(int_array) as ArrayRef,
    1220
                Arc::new(str_array) as ArrayRef,
    1221
            ];
    1222
    1223
            let union_fields = [
    1224
                (0, Arc::new(Field::new("a", DataType::Int32, true))),
    1225
                (1, Arc::new(Field::new("b", DataType::Utf8, true))),
    1226
            ]
    1227
            .into_iter()
    1228
            .collect();
    1229
    1230
            let array = UnionArray::try_new(union_fields, type_ids, None, children).unwrap();
    1231
            let array_ref = Arc::new(array) as ArrayRef;
    1232
    1233
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1234
            let mut hashes = vec![0; array_ref.len()];
    1235
            create_hashes(&[array_ref], &random_state, &mut hashes).unwrap();
    1236
    1237
            // Rows 0 and 3 both have type_id=0 (int) with value 5
    1238
            assert_eq!(hashes[0], hashes[3]);
    1239
            // Row 0 (int 5) vs Row 2 (int 10) - different values
    1240
            assert_ne!(hashes[0], hashes[2]);
    1241
            // Row 0 (int) vs Row 1 (string) - different types
    1242
            assert_ne!(hashes[0], hashes[1]);
    1243
        }
    1244
    1245
        #[test]
    1246
        #[cfg(not(feature = "force_hash_collisions"))]
    1247
        fn create_hashes_for_sparse_union_arrays_with_nulls() {
    1248
            // logical array: [int(5), str("foo"), int(null), str(null)]
    1249
            let int_array = Int32Array::from(vec![Some(5), None, None, None]);
    1250
            let str_array = StringArray::from(vec![None, Some("foo"), None, None]);
    1251
    1252
            let type_ids = vec![0, 1, 0, 1].into();
    1253
            let children = vec![
    1254
                Arc::new(int_array) as ArrayRef,
    1255
                Arc::new(str_array) as ArrayRef,
    1256
            ];
    1257
    1258
            let union_fields = [
    1259
                (0, Arc::new(Field::new("a", DataType::Int32, true))),
    1260
                (1, Arc::new(Field::new("b", DataType::Utf8, true))),
    1261
            ]
    1262
            .into_iter()
    1263
            .collect();
    1264
    1265
            let array = UnionArray::try_new(union_fields, type_ids, None, children).unwrap();
    1266
            let array_ref = Arc::new(array) as ArrayRef;
    1267
    1268
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1269
            let mut hashes = vec![0; array_ref.len()];
    1270
            create_hashes(&[array_ref], &random_state, &mut hashes).unwrap();
    1271
    1272
            // row 2 (int null) and row 3 (str null) should have the same hash
    1273
            // because they are both null values
    1274
            assert_eq!(hashes[2], hashes[3]);
    1275
    1276
            // row 0 (int 5) vs row 2 (int null) - different (value vs null)
    1277
            assert_ne!(hashes[0], hashes[2]);
    1278
    1279
            // row 1 (str "foo") vs row 3 (str null) - different (value vs null)
    1280
            assert_ne!(hashes[1], hashes[3]);
    1281
        }
    1282
    1283
        #[test]
    1284
        #[cfg(not(feature = "force_hash_collisions"))]
    1285
        fn create_hashes_for_dense_union_arrays() {
    1286
            // creates a dense union array with int and string types
    1287
            // [67, "norm", 100, "macdonald", 67]
    1288
            let int_array = Int32Array::from(vec![67, 100, 67]);
    1289
            let str_array = StringArray::from(vec!["norm", "macdonald"]);
    1290
    1291
            let type_ids = vec![0, 1, 0, 1, 0].into();
    1292
            let offsets = vec![0, 0, 1, 1, 2].into();
    1293
            let children = vec![
    1294
                Arc::new(int_array) as ArrayRef,
    1295
                Arc::new(str_array) as ArrayRef,
    1296
            ];
    1297
    1298
            let union_fields = [
    1299
                (0, Arc::new(Field::new("a", DataType::Int32, false))),
    1300
                (1, Arc::new(Field::new("b", DataType::Utf8, false))),
    1301
            ]
    1302
            .into_iter()
    1303
            .collect();
    1304
    1305
            let array =
    1306
                UnionArray::try_new(union_fields, type_ids, Some(offsets), children).unwrap();
    1307
            let array_ref = Arc::new(array) as ArrayRef;
    1308
    1309
            let random_state = RandomState::with_seeds(0, 0, 0, 0);
    1310
            let mut hashes = vec![0; array_ref.len()];
    1311
            create_hashes(&[array_ref], &random_state, &mut hashes).unwrap();
    1312
    1313
            // 67 vs "norm"
    1314
            assert_ne!(hashes[0], hashes[1]);
    1315
            // 67 vs 100
    1316
            assert_ne!(hashes[0], hashes[2]);
    1317
            // "norm" vs "macdonald"
    1318
            assert_ne!(hashes[1], hashes[3]);
    1319
            // 100 vs "macdonald"
    1320
            assert_ne!(hashes[2], hashes[3]);
    1321
            // 67 vs 67
    1322
            assert_eq!(hashes[0], hashes[4]);
    1323
        }
    1324
    }