arrow_data/equal/
union.rs

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
18use crate::data::ArrayData;
19use arrow_schema::{DataType, UnionFields, UnionMode};
20
21use super::equal_range;
22
23#[expect(clippy::too_many_arguments)]
24fn equal_dense(
25    lhs: &ArrayData,
26    rhs: &ArrayData,
27    lhs_type_ids: &[i8],
28    rhs_type_ids: &[i8],
29    lhs_offsets: &[i32],
30    rhs_offsets: &[i32],
31    lhs_fields: &UnionFields,
32    rhs_fields: &UnionFields,
33) -> bool {
34    let offsets = lhs_offsets.iter().zip(rhs_offsets.iter());
35
36    lhs_type_ids
37        .iter()
38        .zip(rhs_type_ids.iter())
39        .zip(offsets)
40        .all(|((l_type_id, r_type_id), (l_offset, r_offset))| {
41            let lhs_child_index = lhs_fields
42                .iter()
43                .position(|(r, _)| r == *l_type_id)
44                .unwrap();
45            let rhs_child_index = rhs_fields
46                .iter()
47                .position(|(r, _)| r == *r_type_id)
48                .unwrap();
49            let lhs_values = &lhs.child_data()[lhs_child_index];
50            let rhs_values = &rhs.child_data()[rhs_child_index];
51
52            equal_range(
53                lhs_values,
54                rhs_values,
55                *l_offset as usize,
56                *r_offset as usize,
57                1,
58            )
59        })
60}
61
62/// Compares `type_ids.len()` slots of two sparse unions whose type ids over that
63/// range are already known to be equal.
64///
65/// Only the child selected by each slot's type id contributes to the logical
66/// value of a sparse union; the values held by the other children at that slot
67/// are arbitrary and must not affect equality. Consecutive slots that select the
68/// same child are compared as a single range of that child.
69fn equal_sparse(
70    lhs: &ArrayData,
71    rhs: &ArrayData,
72    type_ids: &[i8],
73    fields: &UnionFields,
74    lhs_start: usize,
75    rhs_start: usize,
76) -> bool {
77    let mut run_start = 0;
78    type_ids.chunk_by(|a, b| a == b).all(|run| {
79        let start = run_start;
80        run_start += run.len();
81
82        // Both sides share the same `UnionFields` (checked when comparing the
83        // data types), so the type id maps to the same child index on each side.
84        let child_index = fields.iter().position(|(id, _)| id == run[0]).unwrap();
85        equal_range(
86            &lhs.child_data()[child_index],
87            &rhs.child_data()[child_index],
88            lhs_start + lhs.offset() + start,
89            rhs_start + rhs.offset() + start,
90            run.len(),
91        )
92    })
93}
94
95pub(super) fn union_equal(
96    lhs: &ArrayData,
97    rhs: &ArrayData,
98    lhs_start: usize,
99    rhs_start: usize,
100    len: usize,
101) -> bool {
102    let lhs_type_ids = lhs.buffer::<i8>(0);
103    let rhs_type_ids = rhs.buffer::<i8>(0);
104
105    let lhs_type_id_range = &lhs_type_ids[lhs_start..lhs_start + len];
106    let rhs_type_id_range = &rhs_type_ids[rhs_start..rhs_start + len];
107
108    match (lhs.data_type(), rhs.data_type()) {
109        (
110            DataType::Union(lhs_fields, UnionMode::Dense),
111            DataType::Union(rhs_fields, UnionMode::Dense),
112        ) => {
113            let lhs_offsets = lhs.buffer::<i32>(1);
114            let rhs_offsets = rhs.buffer::<i32>(1);
115
116            let lhs_offsets_range = &lhs_offsets[lhs_start..lhs_start + len];
117            let rhs_offsets_range = &rhs_offsets[rhs_start..rhs_start + len];
118
119            lhs_type_id_range == rhs_type_id_range
120                && equal_dense(
121                    lhs,
122                    rhs,
123                    lhs_type_id_range,
124                    rhs_type_id_range,
125                    lhs_offsets_range,
126                    rhs_offsets_range,
127                    lhs_fields,
128                    rhs_fields,
129                )
130        }
131        (DataType::Union(fields, UnionMode::Sparse), DataType::Union(_, UnionMode::Sparse)) => {
132            lhs_type_id_range == rhs_type_id_range
133                && equal_sparse(lhs, rhs, lhs_type_id_range, fields, lhs_start, rhs_start)
134        }
135        _ => unimplemented!(
136            "Logical equality not yet implemented between dense and sparse union arrays"
137        ),
138    }
139}
arrow_data/equal/union.rs

arrow_data/equal/
union.rs
