Skip to main content

parquet_variant/builder/
metadata.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 std::collections::HashMap;
6
7use arrow_schema::ArrowError;
8use indexmap::IndexSet;
9
10use crate::{VARIANT_SPEC_VERSION, VariantMetadata, int_size};
11
12/// Write little-endian integer to buffer
13fn write_offset(buf: &mut Vec<u8>, value: usize, nbytes: u8) {
14    let bytes = value.to_le_bytes();
15    buf.extend_from_slice(&bytes[..nbytes as usize]);
16}
17
18/// A trait for building variant metadata dictionaries, to be used in conjunction with a
19/// [`ValueBuilder`]. The trait provides methods for managing field names and their IDs, as well as
20/// rolling back a failed builder operation that might have created new field ids.
21///
22/// [`ValueBuilder`]: crate::builder::ValueBuilder
23pub trait MetadataBuilder: std::fmt::Debug {
24    /// Attempts to register a field name, returning the corresponding (possibly newly-created)
25    /// field id on success. Attempting to register the same field name twice will _generally_
26    /// produce the same field id both times, but the variant spec does not actually require it.
27    fn try_upsert_field_name(&mut self, field_name: &str) -> Result<u32, ArrowError>;
28
29    /// Retrieves the field name for a given field id, which must be less than
30    /// [`Self::num_field_names`]. Panics if the field id is out of bounds.
31    fn field_name(&self, field_id: usize) -> &str;
32
33    /// Returns the number of field names stored in this metadata builder. Any number less than this
34    /// is a valid field id. The builder can be reverted back to this size later on (discarding any
35    /// newer/higher field ids) by calling [`Self::truncate_field_names`].
36    fn num_field_names(&self) -> usize;
37
38    /// Reverts the field names to a previous size, discarding any newly out of bounds field ids.
39    fn truncate_field_names(&mut self, new_size: usize);
40
41    /// Finishes the current metadata dictionary, returning the new size of the underlying buffer.
42    fn finish(&mut self) -> usize;
43}
44
45impl MetadataBuilder for WritableMetadataBuilder {
46    fn try_upsert_field_name(&mut self, field_name: &str) -> Result<u32, ArrowError> {
47        Ok(self.upsert_field_name(field_name))
48    }
49    fn field_name(&self, field_id: usize) -> &str {
50        self.field_name(field_id)
51    }
52    fn num_field_names(&self) -> usize {
53        self.num_field_names()
54    }
55    fn truncate_field_names(&mut self, new_size: usize) {
56        self.field_names.truncate(new_size)
57    }
58    fn finish(&mut self) -> usize {
59        self.finish()
60    }
61}
62
63/// A metadata builder that cannot register new field names, and merely returns the field id
64/// associated with a known field name. This is useful for variant unshredding operations, where the
65/// metadata column is fixed and -- per variant shredding spec -- already contains all field names
66/// from the typed_value column. It is also useful when projecting a subset of fields from a variant
67/// object value, since the bytes can be copied across directly without re-encoding their field ids.
68///
69/// NOTE: [`Self::finish`] is a no-op. If the intent is to make a copy of the underlying bytes each
70/// time `finish` is called, a different trait impl will be needed.
71#[derive(Debug)]
72pub struct ReadOnlyMetadataBuilder<'m> {
73    metadata: &'m VariantMetadata<'m>,
74    // A cache that tracks field names this builder has already seen, because finding the field id
75    // for a given field name is expensive -- O(n) for a large and unsorted metadata dictionary.
76    // Field names borrowed from a sorted `metadata` bypass this cache; see
77    // `VariantMetadata::borrowed_field_id`.
78    known_field_names: HashMap<&'m str, u32>,
79}
80
81impl<'m> ReadOnlyMetadataBuilder<'m> {
82    /// Creates a new read-only metadata builder from the given metadata dictionary.
83    pub fn new(metadata: &'m VariantMetadata<'m>) -> Self {
84        Self {
85            metadata,
86            known_field_names: HashMap::new(),
87        }
88    }
89}
90
91impl MetadataBuilder for ReadOnlyMetadataBuilder<'_> {
92    fn try_upsert_field_name(&mut self, field_name: &str) -> Result<u32, ArrowError> {
93        // Callers that copy fields out of an object and back into the same metadata dictionary
94        // (unshredding, shredding, and projection all do this) pass field names that are slices of
95        // the dictionary itself. For a sorted dictionary those resolve without hashing or any
96        // string comparison, which matters because this builder is often created per row and so
97        // its `known_field_names` cache would otherwise be populated and discarded without ever
98        // serving a lookup. An unsorted dictionary may hold duplicate entries, so it keeps using
99        // the cache and the name-based search below.
100        if let Some(field_id) = self.metadata.borrowed_field_id(field_name) {
101            return Ok(field_id);
102        }
103
104        if let Some(field_id) = self.known_field_names.get(field_name) {
105            return Ok(*field_id);
106        }
107
108        let Some((field_id, field_name)) = self.metadata.get_entry(field_name) else {
109            return Err(ArrowError::InvalidArgumentError(format!(
110                "Field name '{field_name}' not found in metadata dictionary"
111            )));
112        };
113
114        self.known_field_names.insert(field_name, field_id);
115        Ok(field_id)
116    }
117    fn field_name(&self, field_id: usize) -> &str {
118        &self.metadata[field_id]
119    }
120    fn num_field_names(&self) -> usize {
121        self.metadata.len()
122    }
123    fn truncate_field_names(&mut self, new_size: usize) {
124        debug_assert_eq!(self.metadata.len(), new_size);
125    }
126    fn finish(&mut self) -> usize {
127        self.metadata.bytes.len()
128    }
129}
130
131/// Builder for constructing metadata for [`Variant`] values.
132///
133/// This is used internally by the [`VariantBuilder`] to construct the metadata
134///
135/// You can use an existing `Vec<u8>` as the metadata buffer by using the `from` impl.
136///
137/// [`Variant`]: crate::Variant
138/// [`VariantBuilder`]: crate::VariantBuilder
139#[derive(Default, Debug)]
140pub struct WritableMetadataBuilder {
141    pub(crate) field_names: IndexSet<String>,
142
143    pub(crate) is_sorted: bool,
144
145    /// Output buffer. Metadata is written to the end of this buffer
146    metadata_buffer: Vec<u8>,
147}
148
149impl WritableMetadataBuilder {
150    /// Upsert field name to dictionary, return its ID
151    pub fn upsert_field_name(&mut self, field_name: &str) -> u32 {
152        let (id, new_entry) = self.field_names.insert_full(field_name.to_string());
153
154        if new_entry {
155            let n = self.num_field_names();
156
157            // Dictionary sort order tracking:
158            // - An empty dictionary is unsorted (ambiguous in spec but required by interop tests)
159            // - A single-entry dictionary is trivially sorted
160            // - Otherwise, an already-sorted dictionary becomes unsorted if the new entry breaks order
161            self.is_sorted =
162                n == 1 || self.is_sorted && (self.field_names[n - 2] < self.field_names[n - 1]);
163        }
164
165        id as u32
166    }
167
168    /// The current length of the underlying metadata buffer
169    pub fn offset(&self) -> usize {
170        self.metadata_buffer.len()
171    }
172
173    /// Returns the number of field names stored in the metadata builder.
174    /// Note: this method should be the only place to call `self.field_names.len()`
175    ///
176    /// # Panics
177    ///
178    /// If the number of field names exceeds the maximum allowed value for `u32`.
179    fn num_field_names(&self) -> usize {
180        let n = self.field_names.len();
181        assert!(u32::try_from(n).is_ok());
182
183        n
184    }
185
186    fn field_name(&self, i: usize) -> &str {
187        &self.field_names[i]
188    }
189
190    fn metadata_size(&self) -> usize {
191        self.field_names.iter().map(|k| k.len()).sum()
192    }
193
194    /// Finalizes the metadata dictionary and appends its serialized bytes to the underlying buffer,
195    /// returning the resulting [`Self::offset`]. The builder state is reset and ready to start
196    /// building a new metadata dictionary.
197    pub fn finish(&mut self) -> usize {
198        let nkeys = self.num_field_names();
199
200        // Calculate metadata size
201        let total_dict_size = self.metadata_size();
202
203        let metadata_buffer = &mut self.metadata_buffer;
204        let is_sorted = std::mem::take(&mut self.is_sorted);
205        let field_names = std::mem::take(&mut self.field_names);
206
207        // Determine appropriate offset size based on the larger of dict size or total string size
208        let max_offset = std::cmp::max(total_dict_size, nkeys);
209        let offset_size = int_size(max_offset) as u8;
210
211        let offset_start = 1 + offset_size as usize;
212        let string_start = offset_start + (nkeys + 1) * offset_size as usize;
213        let metadata_size = string_start + total_dict_size;
214
215        metadata_buffer.reserve(metadata_size);
216
217        // Write header: version=1, field names are sorted, with calculated offset_size
218        metadata_buffer
219            .push(VARIANT_SPEC_VERSION | ((is_sorted as u8) << 4) | ((offset_size - 1) << 6));
220
221        // Write dictionary size
222        write_offset(metadata_buffer, nkeys, offset_size);
223
224        // Write offsets
225        let mut cur_offset = 0;
226        for key in &field_names {
227            write_offset(metadata_buffer, cur_offset, offset_size);
228            cur_offset += key.len();
229        }
230        // Write final offset
231        write_offset(metadata_buffer, cur_offset, offset_size);
232
233        // Write string data
234        for key in field_names {
235            metadata_buffer.extend_from_slice(key.as_bytes());
236        }
237
238        metadata_buffer.len()
239    }
240
241    /// Returns the inner buffer, consuming self without finalizing any in progress metadata.
242    pub fn into_inner(self) -> Vec<u8> {
243        self.metadata_buffer
244    }
245}
246
247impl<S: AsRef<str>> FromIterator<S> for WritableMetadataBuilder {
248    fn from_iter<T: IntoIterator<Item = S>>(iter: T) -> Self {
249        let mut this = Self::default();
250        this.extend(iter);
251
252        this
253    }
254}
255
256impl<S: AsRef<str>> Extend<S> for WritableMetadataBuilder {
257    fn extend<T: IntoIterator<Item = S>>(&mut self, iter: T) {
258        let iter = iter.into_iter();
259        let (min, _) = iter.size_hint();
260
261        self.field_names.reserve(min);
262
263        for field_name in iter {
264            self.upsert_field_name(field_name.as_ref());
265        }
266    }
267}
268
269#[cfg(test)]
270mod test {
271    use crate::{
272        ParentState, ValueBuilder, VariantMetadata,
273        builder::{
274            metadata::{ReadOnlyMetadataBuilder, WritableMetadataBuilder},
275            object::ObjectBuilder,
276        },
277    };
278
279    #[test]
280    fn test_metadata_builder_from_iter() {
281        let metadata = WritableMetadataBuilder::from_iter(vec!["apple", "banana", "cherry"]);
282        assert_eq!(metadata.num_field_names(), 3);
283        assert_eq!(metadata.field_name(0), "apple");
284        assert_eq!(metadata.field_name(1), "banana");
285        assert_eq!(metadata.field_name(2), "cherry");
286        assert!(metadata.is_sorted);
287
288        let metadata = WritableMetadataBuilder::from_iter(["zebra", "apple", "banana"]);
289        assert_eq!(metadata.num_field_names(), 3);
290        assert_eq!(metadata.field_name(0), "zebra");
291        assert_eq!(metadata.field_name(1), "apple");
292        assert_eq!(metadata.field_name(2), "banana");
293        assert!(!metadata.is_sorted);
294
295        let metadata = WritableMetadataBuilder::from_iter(Vec::<&str>::new());
296        assert_eq!(metadata.num_field_names(), 0);
297        assert!(!metadata.is_sorted);
298    }
299
300    #[test]
301    fn test_metadata_builder_extend() {
302        let mut metadata = WritableMetadataBuilder::default();
303        assert_eq!(metadata.num_field_names(), 0);
304        assert!(!metadata.is_sorted);
305
306        metadata.extend(["apple", "cherry"]);
307        assert_eq!(metadata.num_field_names(), 2);
308        assert_eq!(metadata.field_name(0), "apple");
309        assert_eq!(metadata.field_name(1), "cherry");
310        assert!(metadata.is_sorted);
311
312        // extend with more field names that maintain sort order
313        metadata.extend(vec!["dinosaur", "monkey"]);
314        assert_eq!(metadata.num_field_names(), 4);
315        assert_eq!(metadata.field_name(2), "dinosaur");
316        assert_eq!(metadata.field_name(3), "monkey");
317        assert!(metadata.is_sorted);
318
319        // test extending with duplicate field names
320        let initial_count = metadata.num_field_names();
321        metadata.extend(["apple", "monkey"]);
322        assert_eq!(metadata.num_field_names(), initial_count); // No new fields added
323    }
324
325    #[test]
326    fn test_metadata_builder_extend_sort_order() {
327        let mut metadata = WritableMetadataBuilder::default();
328
329        metadata.extend(["middle"]);
330        assert!(metadata.is_sorted);
331
332        metadata.extend(["zebra"]);
333        assert!(metadata.is_sorted);
334
335        // add field that breaks sort order
336        metadata.extend(["apple"]);
337        assert!(!metadata.is_sorted);
338    }
339
340    #[test]
341    fn test_metadata_builder_from_iter_with_string_types() {
342        // &str
343        let metadata = WritableMetadataBuilder::from_iter(["a", "b", "c"]);
344        assert_eq!(metadata.num_field_names(), 3);
345
346        // string
347        let metadata = WritableMetadataBuilder::from_iter(vec![
348            "a".to_string(),
349            "b".to_string(),
350            "c".to_string(),
351        ]);
352        assert_eq!(metadata.num_field_names(), 3);
353
354        // mixed types (anything that implements AsRef<str>)
355        let field_names: Vec<Box<str>> = vec!["a".into(), "b".into(), "c".into()];
356        let metadata = WritableMetadataBuilder::from_iter(field_names);
357        assert_eq!(metadata.num_field_names(), 3);
358    }
359
360    #[test]
361    fn test_read_only_metadata_builder_fails_on_unknown_field() {
362        // Create metadata with only one field
363        let mut default_builder = WritableMetadataBuilder::default();
364        default_builder.upsert_field_name("known_field");
365        default_builder.finish();
366        let metadata_bytes = default_builder.into_inner();
367
368        // Use the metadata to build new variant values
369        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
370        let mut metadata_builder = ReadOnlyMetadataBuilder::new(&metadata);
371        let mut value_builder = ValueBuilder::new();
372
373        {
374            let state = ParentState::variant(&mut value_builder, &mut metadata_builder);
375            let mut obj = ObjectBuilder::new(state, false);
376
377            // This should succeed
378            obj.insert("known_field", "value");
379
380            // This should fail because "unknown_field" is not in the metadata
381            let result = obj.try_insert("unknown_field", "value");
382            assert!(result.is_err());
383            assert!(
384                result
385                    .unwrap_err()
386                    .to_string()
387                    .contains("Field name 'unknown_field' not found")
388            );
389        }
390    }
391}