Skip to main content

vortex_array/arrays/dict/compute/
fill_null.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use vortex_error::VortexResult;
5
6use super::Dict;
7use super::DictArray;
8use crate::ArrayRef;
9use crate::Canonical;
10use crate::ExecutionCtx;
11use crate::IntoArray;
12use crate::array::ArrayView;
13use crate::arrays::BoolArray;
14use crate::arrays::ConstantArray;
15use crate::arrays::bool::BoolArrayExt;
16use crate::arrays::dict::DictArrayExt;
17use crate::arrays::dict::DictArraySlotsExt;
18use crate::builtins::ArrayBuiltins;
19use crate::dtype::DType;
20use crate::dtype::Nullability;
21use crate::dtype::PType;
22use crate::scalar::Scalar;
23use crate::scalar_fn::fns::fill_null::FillNullKernel;
24use crate::scalar_fn::fns::operators::Operator;
25
26impl FillNullKernel for Dict {
27    fn fill_null(
28        array: ArrayView<'_, Dict>,
29        fill_value: &Scalar,
30        ctx: &mut ExecutionCtx,
31    ) -> VortexResult<Option<ArrayRef>> {
32        // If the fill value already exists in the dictionary, we can simply rewrite the null codes
33        // to point to the value.
34        let found_fill_values = array
35            .values()
36            .clone()
37            .binary(
38                ConstantArray::new(fill_value.clone(), array.values().len()).into_array(),
39                Operator::Eq,
40            )?
41            .execute::<BoolArray>(ctx)?;
42
43        // We found the fill value already in the values at this given index.
44        let Some(existing_fill_value_index) =
45            found_fill_values.bit_buffer_view().set_indices().next()
46        else {
47            // No fill values found, so we must canonicalize and fill_null.
48            return Ok(Some(
49                array
50                    .array()
51                    .clone()
52                    .execute::<Canonical>(ctx)?
53                    .into_array()
54                    .fill_null(fill_value.clone())?,
55            ));
56        };
57
58        // A dictionary can hold more values than its codes type can index, so the index of an
59        // unreferenced fill value can exceed the range of the codes. Non-nullable codes need no
60        // fill code. For nullable codes, widen the codes to the smallest unsigned type that can
61        // hold the fill index in that case. Codes are never negative, so the cast keeps them.
62        let codes = array.codes();
63        let codes = if codes.dtype().is_nullable() {
64            let fill_index = existing_fill_value_index as u64;
65            let codes = if fill_index > codes.dtype().as_ptype().max_value_as_u64() {
66                let wide_ptype = PType::min_unsigned_ptype_for_value(fill_index);
67                codes
68                    .clone()
69                    .cast(DType::Primitive(wide_ptype, Nullability::Nullable))?
70            } else {
71                codes.clone()
72            };
73
74            let codes_dtype = codes.dtype().as_nonnullable();
75            codes.fill_null(Scalar::from(fill_index).cast(&codes_dtype)?)?
76        } else {
77            codes.clone()
78        };
79
80        // Fill the nulls of the values. Note that the precondition of this function states that the
81        // fill value is non-null, so we do not have to worry about the nullability.
82        let values = array.values().clone().fill_null(fill_value.clone())?;
83
84        // SAFETY: invariants are still satisfied after patching nulls.
85        unsafe {
86            Ok(Some(
87                DictArray::new_unchecked(codes, values)
88                    .set_all_values_referenced(array.has_all_values_referenced())
89                    .into_array(),
90            ))
91        }
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use std::sync::LazyLock;
98
99    use rstest::rstest;
100    use vortex_buffer::BitBuffer;
101    use vortex_buffer::buffer;
102    use vortex_error::VortexExpect;
103    use vortex_error::VortexResult;
104    use vortex_session::VortexSession;
105
106    use crate::IntoArray;
107    use crate::VortexSessionExecute;
108    use crate::arrays::Dict;
109    use crate::arrays::DictArray;
110    use crate::arrays::PrimitiveArray;
111    use crate::arrays::dict::DictArraySlotsExt;
112    use crate::assert_arrays_eq;
113    use crate::builtins::ArrayBuiltins;
114    use crate::dtype::Nullability;
115    use crate::dtype::PType;
116    use crate::scalar::Scalar;
117    use crate::scalar_fn::fns::fill_null::FillNullKernel;
118    use crate::validity::Validity;
119
120    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
121
122    #[rstest]
123    #[case::u8_max(PrimitiveArray::from_option_iter([Some(0u8), None]), 255)]
124    #[case::u8_overflow(PrimitiveArray::from_option_iter([Some(0u8), None]), 256)]
125    #[case::u8_truncation(PrimitiveArray::from_option_iter([Some(0u8), None]), 300)]
126    #[case::i8_max(PrimitiveArray::from_option_iter([Some(0i8), None]), 127)]
127    #[case::i8_overflow(PrimitiveArray::from_option_iter([Some(0i8), None]), 128)]
128    fn fill_unreferenced_value(
129        #[case] codes: PrimitiveArray,
130        #[case] fill_value: i32,
131    ) -> VortexResult<()> {
132        let mut ctx = SESSION.create_execution_ctx();
133        let dict = DictArray::try_new(
134            codes.into_array(),
135            PrimitiveArray::from_iter(0..=fill_value).into_array(),
136        )?;
137
138        let filled = dict.into_array().fill_null(fill_value)?;
139        assert_arrays_eq!(filled, PrimitiveArray::from_iter([0, fill_value]), &mut ctx);
140
141        Ok(())
142    }
143
144    #[rstest]
145    #[case::u8_to_u16(PrimitiveArray::from_option_iter([Some(0u8), None]), 256, PType::U16)]
146    #[case::u8_to_u16_truncation(PrimitiveArray::from_option_iter([Some(0u8), None]), 300, PType::U16)]
147    #[case::i8_to_u8(PrimitiveArray::from_option_iter([Some(0i8), None]), 128, PType::U8)]
148    #[case::i8_to_u16(PrimitiveArray::from_option_iter([Some(0i8), None]), 256, PType::U16)]
149    #[case::u16_to_u32(PrimitiveArray::from_option_iter([Some(0u16), None]), 65_536, PType::U32)]
150    fn fill_unreferenced_value_widens_codes(
151        #[case] codes: PrimitiveArray,
152        #[case] fill_value: i32,
153        #[case] wide_ptype: PType,
154    ) -> VortexResult<()> {
155        let mut ctx = SESSION.create_execution_ctx();
156        let dict = DictArray::try_new(
157            codes.into_array(),
158            PrimitiveArray::from_iter(0..=fill_value).into_array(),
159        )?;
160
161        let filled = <Dict as FillNullKernel>::fill_null(
162            dict.as_view(),
163            &Scalar::from(fill_value),
164            &mut ctx,
165        )?
166        .vortex_expect("kernel should fill the dictionary codes");
167        let filled_dict = filled.as_::<Dict>();
168        assert_eq!(filled_dict.codes().dtype().as_ptype(), wide_ptype);
169        assert!(!filled_dict.codes().dtype().is_nullable());
170        assert_arrays_eq!(filled, PrimitiveArray::from_iter([0, fill_value]), &mut ctx);
171
172        Ok(())
173    }
174
175    #[test]
176    fn non_nullable_codes_fill_unreferenced_value() -> VortexResult<()> {
177        let mut ctx = SESSION.create_execution_ctx();
178        let values =
179            PrimitiveArray::from_option_iter((0..=300).map(|value| (value != 1).then_some(value)));
180        let dict = DictArray::try_new(buffer![0u8, 1].into_array(), values.into_array())?;
181
182        let filled = dict.into_array().fill_null(300)?;
183        assert_arrays_eq!(filled, PrimitiveArray::from_iter([0, 300]), &mut ctx);
184
185        Ok(())
186    }
187
188    #[test]
189    fn nullable_codes_fill_in_values() {
190        let mut ctx = SESSION.create_execution_ctx();
191        let dict = DictArray::try_new(
192            PrimitiveArray::new(
193                buffer![0u32, 1, 2],
194                Validity::from(BitBuffer::from(vec![true, false, true])),
195            )
196            .into_array(),
197            PrimitiveArray::new(buffer![10, 20, 20], Validity::AllValid).into_array(),
198        )
199        .vortex_expect("operation should succeed in test");
200
201        let filled = dict
202            .into_array()
203            .fill_null(Scalar::primitive(20, Nullability::NonNullable))
204            .vortex_expect("operation should succeed in test");
205        assert_arrays_eq!(filled, PrimitiveArray::from_iter([10, 20, 20]), &mut ctx);
206        assert!(filled.all_valid(&mut ctx).unwrap());
207    }
208}