Skip to main content

vortex_array/
normalize.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use smallvec::SmallVec;
5use vortex_error::VortexResult;
6use vortex_error::vortex_bail;
7use vortex_session::registry::Id;
8use vortex_utils::aliases::hash_set::HashSet;
9
10use crate::ArrayRef;
11use crate::ExecutionCtx;
12
13/// Options for normalizing an array.
14pub struct NormalizeOptions<'a> {
15    /// The set of allowed array encodings (in addition to the canonical ones) that are permitted
16    /// in the normalized array.
17    pub allowed: &'a HashSet<Id>,
18    /// The operation to perform when a non-allowed encoding is encountered.
19    pub operation: Operation<'a>,
20}
21
22/// The operation to perform when a non-allowed encoding is encountered.
23pub enum Operation<'a> {
24    Error,
25    Execute(&'a mut ExecutionCtx),
26}
27
28impl ArrayRef {
29    /// Normalize the array according to given options.
30    ///
31    /// This operation performs a recursive traversal of the array. Any non-allowed encoding is
32    /// normalized per the configured operation.
33    pub fn normalize(self, options: &mut NormalizeOptions) -> VortexResult<ArrayRef> {
34        match &mut options.operation {
35            Operation::Error => {
36                self.normalize_with_error(options.allowed)?;
37                // Note this takes ownership so we can at a later date remove non-allowed encodings.
38                Ok(self)
39            }
40            Operation::Execute(ctx) => self.normalize_with_execution(options.allowed, ctx),
41        }
42    }
43
44    fn normalize_with_error(&self, allowed: &HashSet<Id>) -> VortexResult<()> {
45        if !self.is_allowed_encoding(allowed) {
46            vortex_bail!("normalize forbids encoding ({})", self.encoding_id())
47        }
48
49        for child in self.children() {
50            child.normalize_with_error(allowed)?
51        }
52        Ok(())
53    }
54
55    fn normalize_with_execution(
56        self,
57        allowed: &HashSet<Id>,
58        ctx: &mut ExecutionCtx,
59    ) -> VortexResult<ArrayRef> {
60        let mut normalized = self;
61
62        // Top-first execute the array tree while we hit non-allowed encodings.
63        while !normalized.is_allowed_encoding(allowed) {
64            normalized = normalized.execute(ctx)?;
65        }
66
67        // Now we've normalized the root, we need to ensure the children are normalized also.
68        let slots = normalized.slots();
69        let mut normalized_slots = SmallVec::with_capacity(slots.len());
70        let mut any_slot_changed = false;
71
72        for slot in slots {
73            match slot {
74                Some(child) => {
75                    let normalized_child = child.clone().normalize(&mut NormalizeOptions {
76                        allowed,
77                        operation: Operation::Execute(ctx),
78                    })?;
79                    any_slot_changed |= !ArrayRef::ptr_eq(child, &normalized_child);
80                    normalized_slots.push(Some(normalized_child));
81                }
82                None => normalized_slots.push(None),
83            }
84        }
85
86        if any_slot_changed {
87            // SAFETY: normalization only rewrites child slots to logically equivalent allowed
88            // encodings, preserving parent logical values and statistics.
89            normalized = unsafe { normalized.with_slots(normalized_slots) }?;
90        }
91
92        Ok(normalized)
93    }
94
95    fn is_allowed_encoding(&self, allowed: &HashSet<Id>) -> bool {
96        allowed.contains(&self.encoding_id()) || self.is_canonical()
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use std::sync::LazyLock;
103
104    use vortex_error::VortexResult;
105    use vortex_session::VortexSession;
106    use vortex_utils::aliases::hash_set::HashSet;
107
108    use super::NormalizeOptions;
109    use super::Operation;
110    use crate::ArrayRef;
111    use crate::Canonical;
112    use crate::IntoArray;
113    use crate::VortexSessionExecute;
114    use crate::array::VTable;
115    use crate::arrays::Dict;
116    use crate::arrays::DictArray;
117    use crate::arrays::Primitive;
118    use crate::arrays::PrimitiveArray;
119    use crate::arrays::Slice;
120    use crate::arrays::SliceArray;
121    use crate::arrays::StructArray;
122    use crate::assert_arrays_eq;
123    use crate::validity::Validity;
124
125    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
126
127    #[test]
128    fn normalize_with_execution_keeps_parent_when_children_are_unchanged() -> VortexResult<()> {
129        let field = PrimitiveArray::from_iter(0i32..4).into_array();
130        let array = StructArray::try_new(
131            ["field"].into(),
132            vec![field.clone()],
133            field.len(),
134            Validity::NonNullable,
135        )?
136        .into_array();
137        let allowed = HashSet::from_iter([array.encoding_id(), field.encoding_id()]);
138        let mut ctx = SESSION.create_execution_ctx();
139
140        let normalized = array.clone().normalize(&mut NormalizeOptions {
141            allowed: &allowed,
142            operation: Operation::Execute(&mut ctx),
143        })?;
144
145        assert!(ArrayRef::ptr_eq(&array, &normalized));
146        Ok(())
147    }
148
149    #[test]
150    fn normalize_with_error_allows_canonical_arrays() -> VortexResult<()> {
151        let field = PrimitiveArray::from_iter(0i32..4).into_array();
152        let array = StructArray::try_new(
153            ["field"].into(),
154            vec![field.clone()],
155            field.len(),
156            Validity::NonNullable,
157        )?
158        .into_array();
159        let allowed = HashSet::default();
160
161        let normalized = array.clone().normalize(&mut NormalizeOptions {
162            allowed: &allowed,
163            operation: Operation::Error,
164        })?;
165
166        assert!(ArrayRef::ptr_eq(&array, &normalized));
167        Ok(())
168    }
169
170    #[test]
171    fn normalize_with_execution_rebuilds_parent_when_a_child_changes() -> VortexResult<()> {
172        let unchanged = PrimitiveArray::from_iter(0i32..4).into_array();
173        let sliced =
174            SliceArray::new(PrimitiveArray::from_iter(10i32..20).into_array(), 2..6).into_array();
175        let array = StructArray::try_new(
176            ["lhs", "rhs"].into(),
177            vec![unchanged.clone(), sliced],
178            unchanged.len(),
179            Validity::NonNullable,
180        )?
181        .into_array();
182        let allowed = HashSet::from_iter([array.encoding_id(), unchanged.encoding_id()]);
183        let mut ctx = SESSION.create_execution_ctx();
184
185        let normalized = array.clone().normalize(&mut NormalizeOptions {
186            allowed: &allowed,
187            operation: Operation::Execute(&mut ctx),
188        })?;
189
190        assert!(!ArrayRef::ptr_eq(&array, &normalized));
191
192        let original_children = array.children();
193        let normalized_children = normalized.children();
194        assert!(ArrayRef::ptr_eq(
195            &original_children[0],
196            &normalized_children[0]
197        ));
198        assert!(!ArrayRef::ptr_eq(
199            &original_children[1],
200            &normalized_children[1]
201        ));
202        assert!(normalized_children[1].is::<Primitive>());
203        assert_arrays_eq!(
204            normalized,
205            StructArray::try_from_iter([
206                ("lhs", PrimitiveArray::from_iter(0i32..4).into_array()),
207                ("rhs", PrimitiveArray::from_iter(12i32..16).into_array()),
208            ])?,
209            &mut ctx
210        );
211
212        Ok(())
213    }
214
215    #[test]
216    fn normalize_slice_of_dict_returns_dict() -> VortexResult<()> {
217        let codes = PrimitiveArray::from_iter(vec![0u32, 1, 0, 1, 2]).into_array();
218        let values = PrimitiveArray::from_iter(vec![10i32, 20, 30]).into_array();
219        let dict = DictArray::try_new(codes, values)?.into_array();
220
221        // Slice the dict array to get a SliceArray wrapping a DictArray.
222        let sliced = SliceArray::new(dict, 1..4).into_array();
223        assert_eq!(sliced.encoding_id(), Slice.id());
224
225        let allowed = HashSet::from_iter([Dict.id(), Primitive.id()]);
226        let mut ctx = SESSION.create_execution_ctx();
227
228        let normalized = sliced.normalize(&mut NormalizeOptions {
229            allowed: &allowed,
230            operation: Operation::Execute(&mut ctx),
231        })?;
232
233        // The normalized result should be a DictArray, not a SliceArray.
234        assert_eq!(normalized.encoding_id(), Dict.id());
235        assert_eq!(normalized.len(), 3);
236
237        // Verify the data: codes [1,0,1] -> values [20, 10, 20]
238        let normalized_canonical = normalized.execute::<Canonical>(&mut ctx)?;
239        assert_arrays_eq!(
240            normalized_canonical,
241            PrimitiveArray::from_iter(vec![20i32, 10, 20]),
242            &mut ctx
243        );
244
245        Ok(())
246    }
247}