Skip to main content

parquet/arrow/buffer/
offset_buffer.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 crate::arrow::buffer::bit_util::iter_set_bits_rev;
6use crate::arrow::record_reader::buffer::ValuesBuffer;
7use crate::errors::{ParquetError, Result};
8use crate::util::utf8::check_valid_utf8;
9use arrow_array::{ArrayRef, OffsetSizeTrait, make_array};
10use arrow_buffer::{ArrowNativeType, Buffer};
11use arrow_data::ArrayDataBuilder;
12use arrow_schema::DataType as ArrowType;
13
14/// A buffer of variable-sized byte arrays that can be converted into
15/// a corresponding [`ArrayRef`]
16#[derive(Debug)]
17pub struct OffsetBuffer<I: OffsetSizeTrait> {
18    pub offsets: Vec<I>,
19    pub values: Vec<u8>,
20}
21
22impl<I: OffsetSizeTrait> OffsetBuffer<I> {
23    /// Create a new `OffsetBuffer` with capacity for at least `capacity` elements
24    ///
25    /// Pre-allocates the offsets vector to avoid reallocations during reading.
26    /// The values vector is not pre-allocated as its size is unpredictable.
27    pub fn with_capacity(capacity: usize) -> Self {
28        let mut offsets = Vec::with_capacity(capacity + 1);
29        offsets.push(I::default());
30        Self {
31            offsets,
32            values: Vec::new(),
33        }
34    }
35
36    /// Returns the number of byte arrays in this buffer
37    pub fn len(&self) -> usize {
38        self.offsets.len() - 1
39    }
40
41    pub fn is_empty(&self) -> bool {
42        self.len() == 0
43    }
44
45    /// If `validate_utf8` this verifies that the first character of `data` is
46    /// the start of a UTF-8 codepoint
47    ///
48    /// Note: This does not verify that the entirety of `data` is valid
49    /// UTF-8. This should be done by calling [`Self::check_valid_utf8`] after
50    /// all data has been written
51    // Always inlined, as it is called for every value by the PLAIN and
52    // DELTA_BYTE_ARRAY decoders, and is otherwise not inlined into their loops
53    #[inline(always)]
54    pub fn try_push(&mut self, data: &[u8], validate_utf8: bool) -> Result<()> {
55        if validate_utf8 && let Some(&b) = data.first() {
56            // A valid code-point iff it does not start with 0b10xxxxxx
57            // Bit-magic taken from `std::str::is_char_boundary`
58            if (b as i8) < -0x40 {
59                return Err(ParquetError::General(
60                    "encountered non UTF-8 data".to_string(),
61                ));
62            }
63        }
64
65        self.values.extend_from_slice(data);
66
67        let index_offset = I::from_usize(self.values.len())
68            .ok_or_else(|| general_err!("index overflow decoding byte array"))?;
69
70        self.offsets.push(index_offset);
71        Ok(())
72    }
73
74    /// Extends this buffer with a list of keys
75    ///
76    /// For each value `key` in `keys` this will insert
77    /// `&dict_values[dict_offsets[key]..dict_offsets[key+1]]`
78    ///
79    /// Note: This will validate offsets are valid
80    pub fn extend_from_dictionary<K: ArrowNativeType, V: ArrowNativeType>(
81        &mut self,
82        keys: &[K],
83        dict_offsets: &[V],
84        dict_values: &[u8],
85    ) -> Result<()> {
86        self.offsets.reserve(keys.len());
87
88        for key in keys {
89            let index = key.as_usize();
90            if index + 1 >= dict_offsets.len() {
91                return Err(general_err!(
92                    "dictionary key beyond bounds of dictionary: 0..{}",
93                    dict_offsets.len().saturating_sub(1)
94                ));
95            }
96            let start_offset = dict_offsets[index].as_usize();
97            let end_offset = dict_offsets[index + 1].as_usize();
98
99            // Dictionary values are verified when decoding dictionary page
100            self.values
101                .extend_from_slice(&dict_values[start_offset..end_offset]);
102            let index_offset = I::from_usize(self.values.len())
103                .ok_or_else(|| general_err!("index overflow decoding byte array"))?;
104            self.offsets.push(index_offset);
105        }
106        Ok(())
107    }
108
109    /// Validates that `&self.values[start_offset..]` is a valid UTF-8 sequence
110    ///
111    /// This MUST be combined with validating that the offsets start on a character
112    /// boundary, otherwise it would be possible for the values array to be a valid UTF-8
113    /// sequence, but not the individual string slices it contains
114    ///
115    /// [`Self::try_push`] can perform this validation check on insertion
116    pub fn check_valid_utf8(&self, start_offset: usize) -> Result<()> {
117        check_valid_utf8(&self.values.as_slice()[start_offset..])
118    }
119
120    /// Converts this into an [`ArrayRef`] with the provided `data_type` and `null_buffer`
121    pub fn into_array(self, null_buffer: Option<Buffer>, data_type: ArrowType) -> ArrayRef {
122        let array_data_builder = ArrayDataBuilder::new(data_type)
123            .len(self.len())
124            .add_buffer(Buffer::from_vec(self.offsets))
125            .add_buffer(Buffer::from_vec(self.values))
126            .null_bit_buffer(null_buffer);
127
128        let data = match cfg!(debug_assertions) {
129            true => array_data_builder.build().unwrap(),
130            false => unsafe { array_data_builder.build_unchecked() },
131        };
132
133        make_array(data)
134    }
135}
136
137impl<I: OffsetSizeTrait> ValuesBuffer for OffsetBuffer<I> {
138    fn with_capacity(capacity: usize) -> Self {
139        Self::with_capacity(capacity)
140    }
141
142    fn reserve_exact(&mut self, additional: usize) {
143        self.offsets.reserve_exact(additional);
144    }
145
146    fn pad_nulls(
147        &mut self,
148        read_offset: usize,
149        values_read: usize,
150        levels_read: usize,
151        valid_mask: &[u8],
152    ) -> Result<()> {
153        if self.offsets.len() != read_offset + values_read + 1 {
154            return Err(general_err!(
155                "found inconsistent offsets while padding nulls: expected {} offsets, got {}",
156                read_offset + values_read + 1,
157                self.offsets.len()
158            ));
159        }
160        self.offsets
161            .resize(read_offset + levels_read + 1, I::default());
162
163        let offsets = &mut self.offsets;
164
165        let mut last_pos = read_offset + levels_read + 1;
166        let mut last_start_offset = I::from_usize(self.values.len()).unwrap();
167
168        let values_range = read_offset..read_offset + values_read;
169        for (value_pos, level_pos) in values_range
170            .clone()
171            .rev()
172            .zip(iter_set_bits_rev(valid_mask))
173        {
174            if level_pos < value_pos || level_pos >= last_pos {
175                return Err(general_err!("found corrupt level data while padding nulls"));
176            }
177
178            let end_offset = offsets[value_pos + 1];
179            let start_offset = offsets[value_pos];
180
181            // Fill in any nulls
182            for x in &mut offsets[level_pos + 1..last_pos] {
183                *x = end_offset;
184            }
185
186            if level_pos == value_pos {
187                return Ok(());
188            }
189
190            offsets[level_pos] = start_offset;
191            last_pos = level_pos;
192            last_start_offset = start_offset;
193        }
194
195        // Pad leading nulls up to `last_offset`
196        for x in &mut offsets[values_range.start + 1..last_pos] {
197            *x = last_start_offset
198        }
199        Ok(())
200    }
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206    use arrow_array::{Array, LargeStringArray, StringArray};
207
208    #[test]
209    fn test_offset_buffer_empty() {
210        let buffer = OffsetBuffer::<i32>::with_capacity(0);
211        let array = buffer.into_array(None, ArrowType::Utf8);
212        let strings = array.as_any().downcast_ref::<StringArray>().unwrap();
213        assert_eq!(strings.len(), 0);
214    }
215
216    #[test]
217    fn test_offset_buffer_append() {
218        let mut buffer = OffsetBuffer::<i64>::with_capacity(0);
219        buffer.try_push(b"hello", true).unwrap();
220        buffer.try_push(b"bar", true).unwrap();
221        buffer
222            .extend_from_dictionary(&[1, 3, 0, 2], &[0, 2, 4, 5, 6], b"abcdef")
223            .unwrap();
224
225        let array = buffer.into_array(None, ArrowType::LargeUtf8);
226        let strings = array.as_any().downcast_ref::<LargeStringArray>().unwrap();
227        assert_eq!(
228            strings.iter().map(|x| x.unwrap()).collect::<Vec<_>>(),
229            vec!["hello", "bar", "cd", "f", "ab", "e"]
230        )
231    }
232
233    #[test]
234    fn test_offset_buffer() {
235        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
236        for v in ["hello", "world", "cupcakes", "a", "b", "c"] {
237            buffer.try_push(v.as_bytes(), false).unwrap()
238        }
239        let split = std::mem::replace(&mut buffer, OffsetBuffer::with_capacity(0));
240
241        let array = split.into_array(None, ArrowType::Utf8);
242        let strings = array.as_any().downcast_ref::<StringArray>().unwrap();
243        assert_eq!(
244            strings.iter().map(|x| x.unwrap()).collect::<Vec<_>>(),
245            vec!["hello", "world", "cupcakes", "a", "b", "c"]
246        );
247
248        buffer.try_push(b"test", false).unwrap();
249        let array = buffer.into_array(None, ArrowType::Utf8);
250        let strings = array.as_any().downcast_ref::<StringArray>().unwrap();
251        assert_eq!(
252            strings.iter().map(|x| x.unwrap()).collect::<Vec<_>>(),
253            vec!["test"]
254        );
255    }
256
257    #[test]
258    fn test_offset_buffer_pad_nulls() {
259        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
260        let values = ["a", "b", "c", "def", "gh"];
261        for v in &values {
262            buffer.try_push(v.as_bytes(), false).unwrap()
263        }
264
265        let valid = [
266            true, false, false, true, false, true, false, true, true, false, false,
267        ];
268        let valid_mask = Buffer::from_iter(valid.iter().copied());
269
270        // Both trailing and leading nulls
271        buffer
272            .pad_nulls(1, values.len() - 1, valid.len() - 1, valid_mask.as_slice())
273            .unwrap();
274
275        let array = buffer.into_array(Some(valid_mask), ArrowType::Utf8);
276        let strings = array.as_any().downcast_ref::<StringArray>().unwrap();
277        assert_eq!(
278            strings.iter().collect::<Vec<_>>(),
279            vec![
280                Some("a"),
281                None,
282                None,
283                Some("b"),
284                None,
285                Some("c"),
286                None,
287                Some("def"),
288                Some("gh"),
289                None,
290                None
291            ]
292        );
293    }
294
295    #[test]
296    fn test_utf8_validation() {
297        let valid_2_byte_utf8 = &[0b11001000, 0b10001000];
298        std::str::from_utf8(valid_2_byte_utf8).unwrap();
299        let valid_3_byte_utf8 = &[0b11101000, 0b10001000, 0b10001000];
300        std::str::from_utf8(valid_3_byte_utf8).unwrap();
301        let valid_4_byte_utf8 = &[0b11110010, 0b10101000, 0b10101001, 0b10100101];
302        std::str::from_utf8(valid_4_byte_utf8).unwrap();
303
304        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
305        buffer.try_push(valid_2_byte_utf8, true).unwrap();
306        buffer.try_push(valid_3_byte_utf8, true).unwrap();
307        buffer.try_push(valid_4_byte_utf8, true).unwrap();
308
309        // Cannot append string starting with incomplete codepoint
310        buffer.try_push(&valid_2_byte_utf8[1..], true).unwrap_err();
311        buffer.try_push(&valid_3_byte_utf8[1..], true).unwrap_err();
312        buffer.try_push(&valid_3_byte_utf8[2..], true).unwrap_err();
313        buffer.try_push(&valid_4_byte_utf8[1..], true).unwrap_err();
314        buffer.try_push(&valid_4_byte_utf8[2..], true).unwrap_err();
315        buffer.try_push(&valid_4_byte_utf8[3..], true).unwrap_err();
316
317        // Can append data containing an incomplete codepoint
318        buffer.try_push(&[0b01111111, 0b10111111], true).unwrap();
319
320        assert_eq!(buffer.len(), 4);
321        assert_eq!(buffer.values.len(), 11);
322
323        buffer.try_push(valid_3_byte_utf8, true).unwrap();
324
325        // Should fail due to incomplete codepoint
326        buffer.check_valid_utf8(0).unwrap_err();
327
328        // After broken codepoint -> success
329        buffer.check_valid_utf8(11).unwrap();
330
331        // Fails if run from middle of codepoint
332        buffer.check_valid_utf8(12).unwrap_err();
333    }
334
335    #[test]
336    fn test_pad_nulls_corrupt_input_returns_err() {
337        // Corrupt input must produce a decode error rather than panicking.
338
339        // Offsets inconsistent with `values_read`: only one value was pushed,
340        // but three are claimed to have been read.
341        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
342        buffer.try_push(b"a", false).unwrap();
343        let valid_mask = Buffer::from_iter([true, false, false]);
344        let err = buffer
345            .pad_nulls(0, 3, 3, valid_mask.as_slice())
346            .unwrap_err();
347        assert!(
348            err.to_string().contains("inconsistent offsets"),
349            "unexpected error: {err}"
350        );
351
352        // Valid mask has fewer set bits than `values_read`, which previously
353        // tripped an assertion in the null-padding loop.
354        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
355        for v in ["a", "b", "c"] {
356            buffer.try_push(v.as_bytes(), false).unwrap();
357        }
358        let valid_mask = Buffer::from_iter([true, false, false]);
359        let err = buffer
360            .pad_nulls(0, 3, 3, valid_mask.as_slice())
361            .unwrap_err();
362        assert!(
363            err.to_string().contains("corrupt level data"),
364            "unexpected error: {err}"
365        );
366    }
367
368    #[test]
369    fn test_pad_nulls_empty() {
370        let mut buffer = OffsetBuffer::<i32>::with_capacity(0);
371        let valid_mask = Buffer::from_iter(std::iter::repeat_n(false, 9));
372        buffer.pad_nulls(0, 0, 9, valid_mask.as_slice()).unwrap();
373
374        let array = buffer.into_array(Some(valid_mask), ArrowType::Utf8);
375        let strings = array.as_any().downcast_ref::<StringArray>().unwrap();
376
377        assert_eq!(strings.len(), 9);
378        assert!(strings.iter().all(|x| x.is_none()))
379    }
380}