Skip to main content

parquet_variant/
utils.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::{array::TryFromSliceError, borrow::Cow, ops::Range, str};
6
7use crate::VariantPathElement;
8use arrow_schema::ArrowError;
9
10use std::cmp::Ordering;
11use std::fmt::Debug;
12use std::slice::SliceIndex;
13
14/// Helper for reporting integer overflow errors in a consistent way.
15pub(crate) fn overflow_error(msg: &str) -> ArrowError {
16    ArrowError::InvalidArgumentError(format!("Integer overflow computing {msg}"))
17}
18
19#[inline]
20pub(crate) fn slice_from_slice<I: SliceIndex<[u8]> + Clone + Debug>(
21    bytes: &[u8],
22    index: I,
23) -> Result<&I::Output, ArrowError> {
24    bytes.get(index.clone()).ok_or_else(|| {
25        ArrowError::InvalidArgumentError(format!(
26            "Tried to extract byte(s) {index:?} from {}-byte buffer",
27            bytes.len(),
28        ))
29    })
30}
31
32/// Helper to safely slice bytes with offset calculations.
33///
34/// Equivalent to `slice_from_slice(bytes, (base_offset + range.start)..(base_offset + range.end))`
35/// but using checked addition to prevent integer overflow panics on 32-bit systems.
36#[inline]
37pub(crate) fn slice_from_slice_at_offset(
38    bytes: &[u8],
39    base_offset: usize,
40    range: Range<usize>,
41) -> Result<&[u8], ArrowError> {
42    let start_byte = base_offset
43        .checked_add(range.start)
44        .ok_or_else(|| overflow_error("slice start"))?;
45    let end_byte = base_offset
46        .checked_add(range.end)
47        .ok_or_else(|| overflow_error("slice end"))?;
48    slice_from_slice(bytes, start_byte..end_byte)
49}
50
51pub(crate) fn array_from_slice<const N: usize>(
52    bytes: &[u8],
53    offset: usize,
54) -> Result<[u8; N], ArrowError> {
55    slice_from_slice_at_offset(bytes, offset, 0..N)?
56        .try_into()
57        .map_err(|e: TryFromSliceError| ArrowError::InvalidArgumentError(e.to_string()))
58}
59
60pub(crate) fn first_byte_from_slice(slice: &[u8]) -> Result<u8, ArrowError> {
61    slice
62        .first()
63        .copied()
64        .ok_or_else(|| ArrowError::InvalidArgumentError("Received empty bytes".to_string()))
65}
66
67/// Helper to get a &str from a slice at the given offset and range, or an error if it contains invalid UTF-8 data.
68#[inline]
69pub(crate) fn string_from_slice(
70    slice: &[u8],
71    offset: usize,
72    range: Range<usize>,
73) -> Result<&str, ArrowError> {
74    let offset_buffer = slice_from_slice_at_offset(slice, offset, range)?;
75
76    //Use simdutf8 by default
77    #[cfg(feature = "simdutf8")]
78    {
79        simdutf8::basic::from_utf8(offset_buffer).map_err(|_| {
80            // Use simdutf8::compat to return details about the decoding error
81            let e = simdutf8::compat::from_utf8(offset_buffer).unwrap_err();
82            ArrowError::InvalidArgumentError(format!("encountered non UTF-8 data: {e}"))
83        })
84    }
85
86    //Use std::str if simdutf8 is not enabled
87    #[cfg(not(feature = "simdutf8"))]
88    str::from_utf8(offset_buffer)
89        .map_err(|_| ArrowError::InvalidArgumentError("invalid UTF-8 string".to_string()))
90}
91
92/// Performs a binary search over a range using a fallible key extraction function; a failed key
93/// extraction immediately terminates the search.
94///
95/// This is similar to the standard library's `binary_search_by`, but generalized to ranges instead
96/// of slices.
97///
98/// # Arguments
99/// * `range` - The range to search in
100/// * `target` - The target value to search for
101/// * `key_extractor` - A function that extracts a comparable key from slice elements.
102///   This function can fail and return None.
103///
104/// # Returns
105/// * `Some(Ok(index))` - Element found at the given index
106/// * `Some(Err(index))` - Element not found, but would be inserted at the given index
107/// * `None` - Key extraction failed
108pub(crate) fn try_binary_search_range_by<F>(
109    range: Range<usize>,
110    cmp: F,
111) -> Option<Result<usize, usize>>
112where
113    F: Fn(usize) -> Option<Ordering>,
114{
115    let Range { mut start, mut end } = range;
116    while start < end {
117        let mid = start + (end - start) / 2;
118        match cmp(mid)? {
119            Ordering::Equal => return Some(Ok(mid)),
120            Ordering::Greater => end = mid,
121            Ordering::Less => start = mid + 1,
122        }
123    }
124
125    Some(Err(start))
126}
127
128/// Verifies the expected size of type T, for a type that should only grow if absolutely necessary.
129pub(crate) const fn expect_size_of<T>(expected: usize) {
130    let size = std::mem::size_of::<T>();
131    if size != expected {
132        let _ = [""; 0][size];
133    }
134}
135
136/// Parse a path string into a vector of [`VariantPathElement`].
137///
138/// # Syntax
139/// - `.field` or `field` - access object field (do not support special char)
140/// - `[index]` - access array element by index
141/// - `[field]` - access object field (support special char with escape `\`)
142///
143/// # Escape Rules
144/// Inside brackets `[...]`:
145/// - `\\` -> literal `\`
146/// - `\]` -> literal `]`
147/// - Any other `\x` -> literal `x`
148/// - An unescaped `]` inside a quoted field is literal
149///
150/// Outside brackets, no escaping is supported.
151///
152/// # Examples
153/// - `""` -> empty path
154/// - `"foo"` -> single field `foo`
155/// - `"foo.bar"` -> nested fields `foo`, `bar`
156/// - `"[1]"` -> array index 1
157/// - `"['1']"` or `"["1"]"`-> field `1`
158/// - `"foo[1].bar"` -> field `foo`, index 1, field `bar`
159/// - `"['a.b']"` -> field `a.b` (dot is literal inside bracket)
160/// - `"['a\]b']"` -> field `a]b` (escaped `]`
161/// - `"['a]b']"` -> field `a]b` (`]` is literal inside quotes)
162/// - etc.
163///
164/// # Errors
165/// - Leading `.` (e.g., `".foo"`)
166/// - Trailing `.` (e.g., `"foo."`)
167/// - Unclosed '[' (e.g., `"foo[1"`)
168/// - Unexpected ']' (e.g., `"foo]"`)
169/// - Trailing `\` inside bracket (treated as unclosed bracket)
170#[inline]
171pub(crate) fn parse_path(s: &str) -> Result<Vec<VariantPathElement<'_>>, ArrowError> {
172    let scan_field = |start: usize| {
173        s[start..]
174            .find(['.', '[', ']'])
175            .map_or_else(|| s.len(), |p| start + p)
176    };
177
178    let bytes = s.as_bytes();
179    if bytes.first() == Some(&b'.') {
180        return Err(ArrowError::ParseError("Unexpected leading '.'".into()));
181    }
182
183    let mut elements = Vec::new();
184    let mut i = 0;
185
186    while i < bytes.len() {
187        let (elem, end) = match bytes[i] {
188            b'.' => {
189                i += 1; // skip the dot; a field must follow
190                let end = scan_field(i);
191                if end == i {
192                    return Err(ArrowError::ParseError(match bytes.get(i) {
193                        None => "Unexpected trailing '.'".into(),
194                        Some(&c) => format!("Unexpected '{}' at byte {i}", c as char),
195                    }));
196                }
197                (VariantPathElement::field(&s[i..end]), end)
198            }
199            b'[' => {
200                let (element, end) = parse_in_bracket(s, i)?;
201                (element, end)
202            }
203            b']' => {
204                return Err(ArrowError::ParseError(format!(
205                    "Unexpected ']' at byte {i}"
206                )));
207            }
208            _ => {
209                let end = scan_field(i);
210                (VariantPathElement::field(&s[i..end]), end)
211            }
212        };
213        elements.push(elem);
214        i = end;
215    }
216
217    Ok(elements)
218}
219
220/// Parse `[digits | field]` starting at `i` (which points to `[`).
221/// Returns (VariantPathElement, position after `]`).
222fn parse_in_bracket(s: &str, i: usize) -> Result<(VariantPathElement<'_>, usize), ArrowError> {
223    let start = i + 1; // skip '['
224
225    let mut unescaped = None;
226    let mut chars = s[start..].char_indices();
227    let mut end = None;
228    let mut quote = None;
229
230    while let Some((offset, c)) = chars.next() {
231        match c {
232            // Escape: take next char literally
233            '\\' => {
234                let unescaped =
235                    unescaped.get_or_insert_with(|| String::from(&s[start..start + offset]));
236                if let Some((_, next)) = chars.next() {
237                    unescaped.push(next);
238                }
239                // Trailing backslash will be handled as 'unclosed [' below
240            }
241            '\'' | '"' if quote == Some(c) => {
242                quote = None;
243                if let Some(unescaped) = &mut unescaped {
244                    unescaped.push(c);
245                }
246            }
247            // Every consumed char advances the offset, so a quote can only
248            // open the bracket content at offset 0
249            '\'' | '"' if quote.is_none() && offset == 0 => {
250                quote = Some(c);
251            }
252            ']' if quote.is_none() => {
253                // An unescaped ']' outside quotes ends the bracket
254                end = Some(start + offset);
255                break;
256            }
257            _ => {
258                if let Some(unescaped) = &mut unescaped {
259                    unescaped.push(c);
260                }
261            }
262        }
263    }
264
265    let Some(end) = end else {
266        return Err(ArrowError::ParseError(format!("Unclosed '[' at byte {i}")));
267    };
268
269    let value = match unescaped {
270        Some(value) => Cow::Owned(value),
271        None => Cow::Borrowed(&s[start..end]),
272    };
273    let element = parse_bracket_element(value)?;
274
275    Ok((element, end + 1))
276}
277
278fn parse_bracket_element(value: Cow<'_, str>) -> Result<VariantPathElement<'_>, ArrowError> {
279    let quoted = matches!(value.as_bytes(), [b'\'', .., b'\''] | [b'"', .., b'"']);
280
281    if quoted {
282        // Quoted field name, e.g., ['field'] or ['123'] or ["123"]
283        return Ok(VariantPathElement::field(match value {
284            Cow::Borrowed(value) => Cow::Borrowed(&value[1..value.len() - 1]),
285            Cow::Owned(mut value) => {
286                value.pop();
287                value.remove(0);
288                Cow::Owned(value)
289            }
290        }));
291    }
292
293    let element = if value == "*" {
294        VariantPathElement::list_element()
295    } else {
296        let Ok(idx) = value.parse() else {
297            return Err(ArrowError::ParseError(format!(
298                "Invalid token in bracket request: `{value}`. Expected `*`, a quoted string, or a number(e.g., `[*]`, `['field']`, or `[123]`)"
299            )));
300        };
301        VariantPathElement::index(idx)
302    };
303    Ok(element)
304}