Skip to main content

arrow_json/reader/
tape.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::reader::serializer::TapeSerializer;
6use arrow_schema::ArrowError;
7use memchr::memchr2;
8use serde_core::Serialize;
9use std::fmt::Write;
10
11/// We decode JSON to a flattened tape representation,
12/// allowing for efficient traversal of the JSON data
13///
14/// This approach is inspired by [simdjson]
15///
16/// Uses `u32` for offsets to ensure `TapeElement` is 64-bits. A future
17/// iteration may increase this to a custom `u56` type.
18///
19/// Numbers take more than one form, and matches must handle all of them. Parsing JSON
20/// text always yields [`Self::Number`], holding the value textually (read via
21/// [`Tape::get_string`]). Serializing Rust values (see
22/// [`Decoder::serialize`](super::Decoder::serialize)) yields [`Self::I32`],
23/// [`Self::I64`], [`Self::F32`] or [`Self::F64`] — 64-bit values spanning two
24/// elements, high bits first — or [`Self::Number`] for integers exceeding `i64`.
25///
26/// [simdjson]: https://github.com/simdjson/simdjson/blob/master/doc/tape.md
27#[derive(Debug, Copy, Clone, PartialEq, Eq)]
28#[non_exhaustive]
29pub enum TapeElement {
30    /// The start of an object, i.e. `{`
31    ///
32    /// Contains the offset of the corresponding [`Self::EndObject`]
33    StartObject(u32),
34    /// The end of an object, i.e. `}`
35    ///
36    /// Contains the offset of the corresponding [`Self::StartObject`]
37    EndObject(u32),
38    /// The start of a list , i.e. `[`
39    ///
40    /// Contains the offset of the corresponding [`Self::EndList`]
41    StartList(u32),
42    /// The end of a list , i.e. `]`
43    ///
44    /// Contains the offset of the corresponding [`Self::StartList`]
45    EndList(u32),
46    /// A string value
47    ///
48    /// Contains the offset into the [`Tape`] string data
49    String(u32),
50    /// A numeric value
51    ///
52    /// Contains the offset into the [`Tape`] string data
53    Number(u32),
54
55    /// The high bits of a i64
56    ///
57    /// Followed by [`Self::I32`] containing the low bits
58    I64(i32),
59
60    /// A 32-bit signed integer
61    ///
62    /// May be preceded by [`Self::I64`] containing high bits
63    I32(i32),
64
65    /// The high bits of a 64-bit float
66    ///
67    /// Followed by [`Self::F32`] containing the low bits
68    F64(u32),
69
70    /// A 32-bit float or the low-bits of a 64-bit float if preceded by [`Self::F64`]
71    F32(u32),
72
73    /// A true literal
74    True,
75    /// A false literal
76    False,
77    /// A null literal
78    Null,
79}
80
81/// A decoded JSON tape
82///
83/// String and numeric data is stored alongside an array of [`TapeElement`]
84///
85/// The first element is always [`TapeElement::Null`]
86///
87/// This approach to decoding JSON is inspired by [simdjson]
88///
89/// String data is copied into the tape with escapes resolved, so [`Tape::get_string`]
90/// borrows from the tape, not the input. A `Tape` is read, never constructed.
91///
92/// [simdjson]: https://github.com/simdjson/simdjson/blob/master/doc/tape.md
93#[derive(Debug)]
94pub struct Tape<'a> {
95    elements: &'a [TapeElement],
96    strings: &'a str,
97    string_offsets: &'a [usize],
98    num_rows: usize,
99}
100
101impl<'a> Tape<'a> {
102    /// Returns the string for the given string index
103    #[inline]
104    pub fn get_string(&self, idx: u32) -> &'a str {
105        let end_offset = self.string_offsets[idx as usize + 1];
106        let start_offset = self.string_offsets[idx as usize];
107        // SAFETY:
108        // Verified offsets
109        unsafe { self.strings.get_unchecked(start_offset..end_offset) }
110    }
111
112    /// Returns the tape element at `idx`
113    pub fn get(&self, idx: u32) -> TapeElement {
114        self.elements[idx as usize]
115    }
116
117    /// Returns the index of the next field at the same level as `cur_idx`
118    ///
119    /// Return an error if `cur_idx` is not the start of a field
120    pub fn next(&self, cur_idx: u32, expected: &str) -> Result<u32, ArrowError> {
121        match self.get(cur_idx) {
122            TapeElement::String(_)
123            | TapeElement::Number(_)
124            | TapeElement::True
125            | TapeElement::False
126            | TapeElement::Null
127            | TapeElement::I32(_)
128            | TapeElement::F32(_) => Ok(cur_idx + 1),
129            TapeElement::I64(_) | TapeElement::F64(_) => Ok(cur_idx + 2),
130            TapeElement::StartList(end_idx) => Ok(end_idx + 1),
131            TapeElement::StartObject(end_idx) => Ok(end_idx + 1),
132            TapeElement::EndObject(_) | TapeElement::EndList(_) => {
133                Err(self.error(cur_idx, expected))
134            }
135        }
136    }
137
138    /// Returns the number of rows
139    pub fn num_rows(&self) -> usize {
140        self.num_rows
141    }
142
143    /// Serialize the tape element at index `idx` to `out` returning the next field index
144    fn serialize(&self, out: &mut String, idx: u32) -> u32 {
145        match self.get(idx) {
146            TapeElement::StartObject(end) => {
147                out.push('{');
148                let mut cur_idx = idx + 1;
149                while cur_idx < end {
150                    cur_idx = self.serialize(out, cur_idx);
151                    out.push_str(": ");
152                    cur_idx = self.serialize(out, cur_idx);
153                }
154                out.push('}');
155                return end + 1;
156            }
157            TapeElement::EndObject(_) => out.push('}'),
158            TapeElement::StartList(end) => {
159                out.push('[');
160                let mut cur_idx = idx + 1;
161                while cur_idx < end {
162                    cur_idx = self.serialize(out, cur_idx);
163                    if cur_idx < end {
164                        out.push_str(", ");
165                    }
166                }
167                out.push(']');
168                return end + 1;
169            }
170            TapeElement::EndList(_) => out.push(']'),
171            TapeElement::String(s) => {
172                out.push('"');
173                out.push_str(self.get_string(s));
174                out.push('"')
175            }
176            TapeElement::Number(n) => out.push_str(self.get_string(n)),
177            TapeElement::True => out.push_str("true"),
178            TapeElement::False => out.push_str("false"),
179            TapeElement::Null => out.push_str("null"),
180            TapeElement::I64(high) => match self.get(idx + 1) {
181                TapeElement::I32(low) => {
182                    let val = ((high as i64) << 32) | (low as u32) as i64;
183                    let _ = write!(out, "{val}");
184                    return idx + 2;
185                }
186                _ => unreachable!(),
187            },
188            TapeElement::I32(val) => {
189                let _ = write!(out, "{val}");
190            }
191            TapeElement::F64(high) => match self.get(idx + 1) {
192                TapeElement::F32(low) => {
193                    let val = f64::from_bits(((high as u64) << 32) | low as u64);
194                    let _ = write!(out, "{val}");
195                    return idx + 2;
196                }
197                _ => unreachable!(),
198            },
199            TapeElement::F32(val) => {
200                let _ = write!(out, "{}", f32::from_bits(val));
201            }
202        }
203        idx + 1
204    }
205
206    /// Returns an error reading index `idx`
207    pub fn error(&self, idx: u32, expected: &str) -> ArrowError {
208        let mut out = String::with_capacity(64);
209        self.serialize(&mut out, idx);
210        ArrowError::JsonError(format!("expected {expected} got {out}"))
211    }
212}
213
214/// States based on <https://www.json.org/json-en.html>
215#[derive(Debug, Copy, Clone)]
216enum DecoderState {
217    /// Decoding a top-level list, where each element is
218    /// treated as an individual row
219    ///
220    /// This can only appear as the first element on the stack,
221    /// and it is valid to flush a batch when this is the only
222    /// state on the stack
223    TopLevelList,
224    /// Decoding an object
225    ///
226    /// Contains index of start [`TapeElement::StartObject`]
227    Object(u32),
228    /// Decoding a list
229    ///
230    /// Contains index of start [`TapeElement::StartList`]
231    List(u32),
232    String,
233    Value,
234    Number,
235    Colon,
236    Escape,
237    /// A unicode escape sequence,
238    ///
239    /// Consists of a `(low surrogate, high surrogate, decoded length)`
240    Unicode(u16, u16, u8),
241    /// A boolean, null, or enabled nonfinite number literal
242    ///
243    /// Consists of `(literal, decoded length)`
244    Literal(Literal, u8),
245}
246
247impl DecoderState {
248    fn as_str(&self) -> &'static str {
249        match self {
250            DecoderState::TopLevelList => "top-level list",
251            DecoderState::Object(_) => "object",
252            DecoderState::List(_) => "list",
253            DecoderState::String => "string",
254            DecoderState::Value => "value",
255            DecoderState::Number => "number",
256            DecoderState::Colon => "colon",
257            DecoderState::Escape => "escape",
258            DecoderState::Unicode(_, _, _) => "unicode literal",
259            DecoderState::Literal(d, _) => d.as_str(),
260        }
261    }
262}
263
264#[derive(Debug, Copy, Clone)]
265enum Literal {
266    Null,
267    True,
268    False,
269    NaN,
270    Infinity,
271    NegativeInfinity,
272}
273
274impl Literal {
275    fn element(&self, bytes: &mut Vec<u8>, offsets: &mut Vec<usize>) -> TapeElement {
276        match self {
277            Literal::Null => TapeElement::Null,
278            Literal::True => TapeElement::True,
279            Literal::False => TapeElement::False,
280            Literal::NaN | Literal::Infinity | Literal::NegativeInfinity => {
281                let index = offsets.len() - 1;
282                bytes.extend_from_slice(self.bytes());
283                offsets.push(bytes.len());
284                TapeElement::Number(index as _)
285            }
286        }
287    }
288
289    fn as_str(&self) -> &'static str {
290        match self {
291            Literal::Null => "null",
292            Literal::True => "true",
293            Literal::False => "false",
294            Literal::NaN => "NaN",
295            Literal::Infinity => "Infinity",
296            Literal::NegativeInfinity => "-Infinity",
297        }
298    }
299
300    fn bytes(&self) -> &'static [u8] {
301        self.as_str().as_bytes()
302    }
303}
304
305/// Evaluates to the next element in the iterator or breaks the current loop
306macro_rules! next {
307    ($next:ident) => {
308        match $next.next() {
309            Some(b) => b,
310            None => break,
311        }
312    };
313}
314
315/// Implements a state machine for decoding JSON to a tape
316#[derive(Debug)]
317pub struct TapeDecoder {
318    /// The decoded elements
319    elements: Vec<TapeElement>,
320
321    /// The number of rows decoded, including any in progress if `!stack.is_empty()`
322    cur_row: usize,
323
324    /// Number of rows to read per batch
325    batch_size: usize,
326
327    /// Whether to flatten top-level arrays into the stream of JSON rows,
328    /// meaning that each of their elements will be treated as an individual row
329    ///
330    /// When `false` (the default), the entire top-level array will be treated as one row
331    flatten_top_level_arrays: bool,
332
333    /// Whether to accept nonstandard NaN and Infinity number literals
334    allow_non_finite_floats: bool,
335
336    /// A buffer of parsed string data
337    ///
338    /// Note: if part way through a record, i.e. `stack` is not empty,
339    /// this may contain truncated UTF-8 data
340    bytes: Vec<u8>,
341
342    /// Offsets into `data`
343    offsets: Vec<usize>,
344
345    /// A stack of [`DecoderState`]
346    stack: Vec<DecoderState>,
347}
348
349/// Configuration for a `TapeDecoder`.
350#[derive(Clone, Copy, Debug)]
351pub struct TapeDecoderOptions {
352    /// The batch size
353    pub batch_size: usize,
354    /// The estimated number of fields in each row
355    pub num_fields: usize,
356    /// Whether to flatten top-level arrays
357    pub flatten_top_level_arrays: bool,
358    /// Whether to accept nonstandard NaN and Infinity number literals
359    pub allow_non_finite_floats: bool,
360}
361
362impl TapeDecoder {
363    /// Create a new [`TapeDecoder`] with the provided options
364    pub fn new(options: TapeDecoderOptions) -> Self {
365        let TapeDecoderOptions {
366            batch_size,
367            num_fields,
368            flatten_top_level_arrays,
369            allow_non_finite_floats,
370        } = options;
371
372        let tokens_per_row = 2 + num_fields * 2;
373        let mut offsets = Vec::with_capacity(batch_size * (num_fields * 2) + 1);
374        offsets.push(0);
375
376        let mut elements = Vec::with_capacity(batch_size * tokens_per_row);
377        elements.push(TapeElement::Null);
378
379        Self {
380            offsets,
381            elements,
382            batch_size,
383            flatten_top_level_arrays,
384            allow_non_finite_floats,
385            cur_row: 0,
386            bytes: Vec::with_capacity(num_fields * 2 * 8),
387            stack: Vec::with_capacity(10),
388        }
389    }
390
391    pub fn decode(&mut self, buf: &[u8]) -> Result<usize, ArrowError> {
392        let mut iter = BufIter::new(buf);
393
394        while !iter.is_empty() {
395            let state = match self.stack.last_mut() {
396                Some(l) => l,
397                None => {
398                    iter.skip_whitespace();
399                    if self.cur_row >= self.batch_size {
400                        break;
401                    }
402
403                    match iter.peek() {
404                        Some(b'[') if self.flatten_top_level_arrays => {
405                            // Consume the `[` without writing it
406                            iter.next();
407                            self.stack.push(DecoderState::TopLevelList);
408                        }
409                        Some(_) => {
410                            // Start of row
411                            self.cur_row += 1;
412                            self.stack.push(DecoderState::Value);
413                        }
414                        None => break,
415                    }
416
417                    // There is now a top-most state to process
418                    self.stack.last_mut().unwrap()
419                }
420            };
421
422            match state {
423                // Decoding a top-level list
424                DecoderState::TopLevelList => {
425                    iter.advance_until(|b| !json_whitespace(b) && b != b',');
426                    if self.cur_row >= self.batch_size {
427                        break;
428                    }
429
430                    match iter.peek() {
431                        Some(b']') => {
432                            // Consume the `]` without writing it
433                            iter.next();
434                            self.stack.pop();
435                        }
436                        Some(_) => {
437                            // Start of row
438                            self.cur_row += 1;
439                            self.stack.push(DecoderState::Value);
440                        }
441                        None => break,
442                    }
443                }
444                // Decoding an object
445                DecoderState::Object(start_idx) => {
446                    iter.advance_until(|b| !json_whitespace(b) && b != b',');
447                    match next!(iter) {
448                        b'"' => {
449                            self.stack.push(DecoderState::Value);
450                            self.stack.push(DecoderState::Colon);
451                            self.stack.push(DecoderState::String);
452                        }
453                        b'}' => {
454                            let start_idx = *start_idx;
455                            let end_idx = self.elements.len() as u32;
456                            self.elements[start_idx as usize] = TapeElement::StartObject(end_idx);
457                            self.elements.push(TapeElement::EndObject(start_idx));
458                            self.stack.pop();
459                        }
460                        b => return Err(err(b, "parsing object")),
461                    }
462                }
463                // Decoding a list
464                DecoderState::List(start_idx) => {
465                    iter.advance_until(|b| !json_whitespace(b) && b != b',');
466                    match iter.peek() {
467                        Some(b']') => {
468                            iter.next();
469                            let start_idx = *start_idx;
470                            let end_idx = self.elements.len() as u32;
471                            self.elements[start_idx as usize] = TapeElement::StartList(end_idx);
472                            self.elements.push(TapeElement::EndList(start_idx));
473                            self.stack.pop();
474                        }
475                        Some(_) => self.stack.push(DecoderState::Value),
476                        None => break,
477                    }
478                }
479                // Decoding a string
480                DecoderState::String => {
481                    let s = iter.skip_chrs(b'\\', b'"');
482                    self.bytes.extend_from_slice(s);
483
484                    match next!(iter) {
485                        b'\\' => self.stack.push(DecoderState::Escape),
486                        b'"' => {
487                            let idx = self.offsets.len() - 1;
488                            self.elements.push(TapeElement::String(idx as _));
489                            self.offsets.push(self.bytes.len());
490                            self.stack.pop();
491                        }
492                        b => unreachable!("{}", b),
493                    }
494                }
495                state @ DecoderState::Value => {
496                    iter.skip_whitespace();
497                    *state = match next!(iter) {
498                        b'"' => DecoderState::String,
499                        b @ (b'-' | b'0'..=b'9') => {
500                            self.bytes.push(b);
501                            DecoderState::Number
502                        }
503                        b'N' if self.allow_non_finite_floats => {
504                            DecoderState::Literal(Literal::NaN, 1)
505                        }
506                        b'I' if self.allow_non_finite_floats => {
507                            DecoderState::Literal(Literal::Infinity, 1)
508                        }
509                        b'n' => DecoderState::Literal(Literal::Null, 1),
510                        b'f' => DecoderState::Literal(Literal::False, 1),
511                        b't' => DecoderState::Literal(Literal::True, 1),
512                        b'[' => {
513                            let idx = self.elements.len() as u32;
514                            self.elements.push(TapeElement::StartList(u32::MAX));
515                            DecoderState::List(idx)
516                        }
517                        b'{' => {
518                            let idx = self.elements.len() as u32;
519                            self.elements.push(TapeElement::StartObject(u32::MAX));
520                            DecoderState::Object(idx)
521                        }
522                        b => return Err(err(b, "parsing value")),
523                    };
524                }
525                state @ DecoderState::Number => {
526                    // A leading minus may have arrived in the previous input buffer.
527                    if self.allow_non_finite_floats
528                        && iter.peek() == Some(b'I')
529                        && self.bytes.last() == Some(&b'-')
530                        && self.bytes.len() == self.offsets[self.offsets.len() - 1] + 1
531                    {
532                        self.bytes.pop();
533                        *state = DecoderState::Literal(Literal::NegativeInfinity, 1);
534                        continue;
535                    }
536                    let s = iter.advance_until(|b| {
537                        !matches!(b, b'0'..=b'9' | b'-' | b'+' | b'.' | b'e' | b'E')
538                    });
539                    self.bytes.extend_from_slice(s);
540
541                    if !iter.is_empty() {
542                        self.stack.pop();
543                        let idx = self.offsets.len() - 1;
544                        self.elements.push(TapeElement::Number(idx as _));
545                        self.offsets.push(self.bytes.len());
546                    }
547                }
548                DecoderState::Colon => {
549                    iter.skip_whitespace();
550                    match next!(iter) {
551                        b':' => self.stack.pop(),
552                        b => return Err(err(b, "parsing colon")),
553                    };
554                }
555                DecoderState::Literal(literal, idx) => {
556                    let bytes = literal.bytes();
557                    let expected = bytes.iter().skip(*idx as usize).copied();
558                    for (expected, b) in expected.zip(&mut iter) {
559                        match b == expected {
560                            true => *idx += 1,
561                            false => return Err(err(b, "parsing literal")),
562                        }
563                    }
564                    if *idx == bytes.len() as u8 {
565                        let element = literal.element(&mut self.bytes, &mut self.offsets);
566                        self.stack.pop();
567                        self.elements.push(element);
568                    }
569                }
570                DecoderState::Escape => {
571                    let v = match next!(iter) {
572                        b'u' => {
573                            self.stack.pop();
574                            self.stack.push(DecoderState::Unicode(0, 0, 0));
575                            continue;
576                        }
577                        b'"' => b'"',
578                        b'\\' => b'\\',
579                        b'/' => b'/',
580                        b'b' => 8,  // BS
581                        b'f' => 12, // FF
582                        b'n' => b'\n',
583                        b'r' => b'\r',
584                        b't' => b'\t',
585                        b => return Err(err(b, "parsing escape sequence")),
586                    };
587
588                    self.stack.pop();
589                    self.bytes.push(v);
590                }
591                // Parse a unicode escape sequence
592                DecoderState::Unicode(high, low, idx) => loop {
593                    match *idx {
594                        0..=3 => *high = (*high << 4) | parse_hex(next!(iter))? as u16,
595                        4 => {
596                            if let Some(c) = char::from_u32(*high as u32) {
597                                write_char(c, &mut self.bytes);
598                                self.stack.pop();
599                                break;
600                            }
601
602                            match next!(iter) {
603                                b'\\' => {}
604                                b => return Err(err(b, "parsing surrogate pair escape")),
605                            }
606                        }
607                        5 => match next!(iter) {
608                            b'u' => {}
609                            b => return Err(err(b, "parsing surrogate pair unicode")),
610                        },
611                        6..=9 => *low = (*low << 4) | parse_hex(next!(iter))? as u16,
612                        _ => {
613                            let c = char_from_surrogate_pair(*low, *high)?;
614                            write_char(c, &mut self.bytes);
615                            self.stack.pop();
616                            break;
617                        }
618                    }
619                    *idx += 1;
620                },
621            }
622        }
623
624        Ok(buf.len() - iter.len())
625    }
626
627    /// Writes any type that implements [`Serialize`] into this [`TapeDecoder`]
628    pub fn serialize<S: Serialize>(&mut self, rows: &[S]) -> Result<(), ArrowError> {
629        if let Some(b) = self.stack.last() {
630            return Err(ArrowError::JsonError(format!(
631                "Cannot serialize to tape containing partial decode state {}",
632                b.as_str()
633            )));
634        }
635
636        let mut serializer =
637            TapeSerializer::new(&mut self.elements, &mut self.bytes, &mut self.offsets);
638
639        rows.iter()
640            .try_for_each(|row| row.serialize(&mut serializer))
641            .map_err(|e| ArrowError::JsonError(e.to_string()))?;
642
643        self.cur_row += rows.len();
644
645        Ok(())
646    }
647
648    /// The number of buffered rows, including the partially decoded row (if any).
649    pub fn num_buffered_rows(&self) -> usize {
650        self.cur_row
651    }
652
653    /// True if the decoder is part way through decoding a row. If so, calling [`Self::finish`]
654    /// would return an error.
655    pub fn has_partial_row(&self) -> bool {
656        !matches!(self.stack.last(), None | Some(DecoderState::TopLevelList))
657    }
658
659    /// Finishes the current [`Tape`]
660    pub fn finish(&self) -> Result<Tape<'_>, ArrowError> {
661        match self.stack.last() {
662            None => {}
663            Some(DecoderState::TopLevelList) => {}
664            Some(state) => {
665                return Err(ArrowError::JsonError(format!(
666                    "Truncated record whilst reading {}",
667                    state.as_str()
668                )));
669            }
670        }
671
672        if self.offsets.len() >= u32::MAX as usize {
673            return Err(ArrowError::JsonError(format!(
674                "Encountered more than {} bytes of string data, consider using a smaller batch size",
675                u32::MAX
676            )));
677        }
678
679        if self.offsets.len() >= u32::MAX as usize {
680            return Err(ArrowError::JsonError(format!(
681                "Encountered more than {} JSON elements, consider using a smaller batch size",
682                u32::MAX
683            )));
684        }
685
686        // Sanity check
687        assert_eq!(
688            self.offsets.last().copied().unwrap_or_default(),
689            self.bytes.len()
690        );
691
692        let strings = simdutf8::basic::from_utf8(&self.bytes)
693            .map_err(|_| ArrowError::JsonError("Encountered non-UTF-8 data".to_string()))?;
694
695        for offset in self.offsets.iter().copied() {
696            if !strings.is_char_boundary(offset) {
697                return Err(ArrowError::JsonError(
698                    "Encountered truncated UTF-8 sequence".to_string(),
699                ));
700            }
701        }
702
703        Ok(Tape {
704            strings,
705            elements: &self.elements,
706            string_offsets: &self.offsets,
707            num_rows: self.cur_row,
708        })
709    }
710
711    /// Clears this [`TapeDecoder`] in preparation to read the next batch
712    pub fn clear(&mut self) {
713        assert!(!self.has_partial_row());
714
715        self.cur_row = 0;
716        self.bytes.clear();
717        self.elements.clear();
718        self.elements.push(TapeElement::Null);
719        self.offsets.clear();
720        self.offsets.push(0);
721    }
722}
723
724/// A wrapper around a slice iterator that provides some helper functionality
725struct BufIter<'a> {
726    buf: &'a [u8],
727    pos: usize,
728}
729
730impl<'a> BufIter<'a> {
731    fn new(buf: &'a [u8]) -> Self {
732        Self { buf, pos: 0 }
733    }
734
735    #[inline]
736    fn as_slice(&self) -> &'a [u8] {
737        &self.buf[self.pos..]
738    }
739
740    #[inline]
741    fn is_empty(&self) -> bool {
742        self.pos >= self.buf.len()
743    }
744
745    fn peek(&self) -> Option<u8> {
746        self.buf.get(self.pos).copied()
747    }
748
749    #[inline]
750    fn advance(&mut self, skip: usize) {
751        self.pos += skip;
752    }
753
754    fn advance_until<F: FnMut(u8) -> bool>(&mut self, f: F) -> &[u8] {
755        let s = self.as_slice();
756        match s.iter().copied().position(f) {
757            Some(x) => {
758                self.advance(x);
759                &s[..x]
760            }
761            None => {
762                self.advance(s.len());
763                s
764            }
765        }
766    }
767
768    fn skip_chrs(&mut self, c1: u8, c2: u8) -> &[u8] {
769        let s = self.as_slice();
770        match memchr2(c1, c2, s) {
771            Some(p) => {
772                self.advance(p);
773                &s[..p]
774            }
775            None => {
776                self.advance(s.len());
777                s
778            }
779        }
780    }
781
782    fn skip_whitespace(&mut self) {
783        self.advance_until(|b| !json_whitespace(b));
784    }
785}
786
787impl Iterator for BufIter<'_> {
788    type Item = u8;
789
790    fn next(&mut self) -> Option<Self::Item> {
791        let b = self.peek();
792        self.pos += 1;
793        b
794    }
795
796    fn size_hint(&self) -> (usize, Option<usize>) {
797        let s = self.buf.len().saturating_sub(self.pos);
798        (s, Some(s))
799    }
800}
801
802impl ExactSizeIterator for BufIter<'_> {}
803
804/// Returns an error for a given byte `b` and context `ctx`
805fn err(b: u8, ctx: &str) -> ArrowError {
806    ArrowError::JsonError(format!(
807        "Encountered unexpected '{}' whilst {ctx}",
808        b as char
809    ))
810}
811
812/// Creates a character from an UTF-16 surrogate pair
813fn char_from_surrogate_pair(low: u16, high: u16) -> Result<char, ArrowError> {
814    match (low, high) {
815        (0xDC00..=0xDFFF, 0xD800..=0xDBFF) => {
816            let n = (((high - 0xD800) as u32) << 10) + ((low - 0xDC00) as u32 + 0x1_0000);
817            char::from_u32(n)
818                .ok_or_else(|| ArrowError::JsonError(format!("Invalid UTF-16 surrogate pair {n}")))
819        }
820        _ => Err(ArrowError::JsonError(format!(
821            "Invalid UTF-16 surrogate pair. High: {high:#04X}, Low: {low:#04X}"
822        ))),
823    }
824}
825
826/// Writes `c` as UTF-8 to `out`
827fn write_char(c: char, out: &mut Vec<u8>) {
828    let mut t = [0; 4];
829    out.extend_from_slice(c.encode_utf8(&mut t).as_bytes());
830}
831
832/// Evaluates to true if `b` is a valid JSON whitespace character
833#[inline]
834fn json_whitespace(b: u8) -> bool {
835    matches!(b, b' ' | b'\n' | b'\r' | b'\t')
836}
837
838/// Parse a hex character to `u8`
839fn parse_hex(b: u8) -> Result<u8, ArrowError> {
840    let digit = char::from(b)
841        .to_digit(16)
842        .ok_or_else(|| err(b, "unicode escape"))?;
843    Ok(digit as u8)
844}
845
846#[cfg(test)]
847mod tests {
848    use super::*;
849
850    /// Helper method to create a `TapeDecoder` with sensible defaults
851    fn tape_decoder() -> TapeDecoder {
852        TapeDecoder::new(TapeDecoderOptions {
853            batch_size: 16,
854            num_fields: 2,
855            flatten_top_level_arrays: false,
856            allow_non_finite_floats: false,
857        })
858    }
859
860    #[test]
861    fn test_sizes() {
862        assert_eq!(std::mem::size_of::<DecoderState>(), 8);
863        assert_eq!(std::mem::size_of::<TapeElement>(), 8);
864    }
865
866    #[test]
867    fn test_basic() {
868        let a = r#"
869        {"hello": "world", "foo": 2, "bar": 45}
870
871        {"foo": "bar"}
872
873        {"fiz": null}
874
875        {"a": true, "b": false, "c": null}
876
877        {"a": "", "": "a"}
878
879        {"a": "b", "object": {"nested": "hello", "foo": 23}, "b": {}, "c": {"foo": null }}
880
881        {"a": ["", "foo", ["bar", "c"]], "b": {"1": []}, "c": {"2": [1, 2, 3]} }
882        "#;
883        let mut decoder = tape_decoder();
884        decoder.decode(a.as_bytes()).unwrap();
885        assert!(!decoder.has_partial_row());
886        assert_eq!(decoder.num_buffered_rows(), 7);
887
888        let finished = decoder.finish().unwrap();
889        assert!(!decoder.has_partial_row());
890        assert_eq!(decoder.num_buffered_rows(), 7); // didn't call clear() yet
891        assert_eq!(
892            finished.elements,
893            &[
894                TapeElement::Null,
895                TapeElement::StartObject(8), // {"hello": "world", "foo": 2, "bar": 45}
896                TapeElement::String(0),      // "hello"
897                TapeElement::String(1),      // "world"
898                TapeElement::String(2),      // "foo"
899                TapeElement::Number(3),      // 2
900                TapeElement::String(4),      // "bar"
901                TapeElement::Number(5),      // 45
902                TapeElement::EndObject(1),
903                TapeElement::StartObject(12), // {"foo": "bar"}
904                TapeElement::String(6),       // "foo"
905                TapeElement::String(7),       // "bar"
906                TapeElement::EndObject(9),
907                TapeElement::StartObject(16), // {"fiz": null}
908                TapeElement::String(8),       // "fiz
909                TapeElement::Null,            // null
910                TapeElement::EndObject(13),
911                TapeElement::StartObject(24), // {"a": true, "b": false, "c": null}
912                TapeElement::String(9),       // "a"
913                TapeElement::True,            // true
914                TapeElement::String(10),      // "b"
915                TapeElement::False,           // false
916                TapeElement::String(11),      // "c"
917                TapeElement::Null,            // null
918                TapeElement::EndObject(17),
919                TapeElement::StartObject(30), // {"a": "", "": "a"}
920                TapeElement::String(12),      // "a"
921                TapeElement::String(13),      // ""
922                TapeElement::String(14),      // ""
923                TapeElement::String(15),      // "a"
924                TapeElement::EndObject(25),
925                TapeElement::StartObject(49), // {"a": "b", "object": {"nested": "hello", "foo": 23}, "b": {}, "c": {"foo": null }}
926                TapeElement::String(16),      // "a"
927                TapeElement::String(17),      // "b"
928                TapeElement::String(18),      // "object"
929                TapeElement::StartObject(40), // {"nested": "hello", "foo": 23}
930                TapeElement::String(19),      // "nested"
931                TapeElement::String(20),      // "hello"
932                TapeElement::String(21),      // "foo"
933                TapeElement::Number(22),      // 23
934                TapeElement::EndObject(35),
935                TapeElement::String(23),      // "b"
936                TapeElement::StartObject(43), // {}
937                TapeElement::EndObject(42),
938                TapeElement::String(24),      // "c"
939                TapeElement::StartObject(48), // {"foo": null }
940                TapeElement::String(25),      // "foo"
941                TapeElement::Null,            // null
942                TapeElement::EndObject(45),
943                TapeElement::EndObject(31),
944                TapeElement::StartObject(75), // {"a": ["", "foo", ["bar", "c"]], "b": {"1": []}, "c": {"2": [1, 2, 3]} }
945                TapeElement::String(26),      // "a"
946                TapeElement::StartList(59),   // ["", "foo", ["bar", "c"]]
947                TapeElement::String(27),      // ""
948                TapeElement::String(28),      // "foo"
949                TapeElement::StartList(58),   // ["bar", "c"]
950                TapeElement::String(29),      // "bar"
951                TapeElement::String(30),      // "c"
952                TapeElement::EndList(55),
953                TapeElement::EndList(52),
954                TapeElement::String(31),      // "b"
955                TapeElement::StartObject(65), // {"1": []}
956                TapeElement::String(32),      // "1"
957                TapeElement::StartList(64),   // []
958                TapeElement::EndList(63),
959                TapeElement::EndObject(61),
960                TapeElement::String(33),      // "c"
961                TapeElement::StartObject(74), // {"2": [1, 2, 3]}
962                TapeElement::String(34),      // "2"
963                TapeElement::StartList(73),   // [1, 2, 3]
964                TapeElement::Number(35),      // 1
965                TapeElement::Number(36),      // 2
966                TapeElement::Number(37),      // 3
967                TapeElement::EndList(69),
968                TapeElement::EndObject(67),
969                TapeElement::EndObject(50)
970            ]
971        );
972
973        assert_eq!(
974            finished.strings,
975            "helloworldfoo2bar45foobarfizabcaaabobjectnestedhellofoo23bcfooafoobarcb1c2123"
976        );
977        assert_eq!(
978            &finished.string_offsets,
979            &[
980                0, 5, 10, 13, 14, 17, 19, 22, 25, 28, 29, 30, 31, 32, 32, 32, 33, 34, 35, 41, 47,
981                52, 55, 57, 58, 59, 62, 63, 63, 66, 69, 70, 71, 72, 73, 74, 75, 76, 77
982            ]
983        );
984
985        decoder.clear();
986        assert!(!decoder.has_partial_row());
987        assert_eq!(decoder.num_buffered_rows(), 0);
988    }
989
990    #[test]
991    fn test_surrogate_pairs() {
992        let mut decoder = tape_decoder();
993        decoder
994            .decode(
995                br#"{"v": [
996                    "\ud800\udc00",
997                    "\ud83d\ude00",
998                    "\ud840\udc00",
999                    "\udbff\udfff",
1000                    "\uD840\uDC00",
1001                    "a\ud840\udc00b"
1002                ]}"#,
1003            )
1004            .unwrap();
1005        let tape = decoder.finish().unwrap();
1006
1007        // String 0 is the key "v"
1008        assert_eq!(tape.get_string(1), "\u{10000}"); // lowest supplementary
1009        assert_eq!(tape.get_string(2), "\u{1F600}"); // emoji
1010        assert_eq!(tape.get_string(3), "\u{20000}");
1011        assert_eq!(tape.get_string(4), "\u{10FFFF}");
1012        assert_eq!(tape.get_string(5), "\u{20000}"); // uppercase hex
1013        assert_eq!(tape.get_string(6), "a\u{20000}b"); // surrounded by ASCII
1014    }
1015
1016    #[test]
1017    fn test_invalid() {
1018        // Test invalid
1019        let mut decoder = tape_decoder();
1020        let err = decoder.decode(b"hello").unwrap_err().to_string();
1021        assert_eq!(
1022            err,
1023            "Json error: Encountered unexpected 'h' whilst parsing value"
1024        );
1025
1026        let mut decoder = tape_decoder();
1027        let err = decoder.decode(b"{\"hello\": }").unwrap_err().to_string();
1028        assert_eq!(
1029            err,
1030            "Json error: Encountered unexpected '}' whilst parsing value"
1031        );
1032
1033        let mut decoder = tape_decoder();
1034        let err = decoder
1035            .decode(b"{\"hello\": [ false, tru ]}")
1036            .unwrap_err()
1037            .to_string();
1038        assert_eq!(
1039            err,
1040            "Json error: Encountered unexpected ' ' whilst parsing literal"
1041        );
1042
1043        let mut decoder = tape_decoder();
1044        let err = decoder
1045            .decode(b"{\"hello\": \"\\ud8\"}")
1046            .unwrap_err()
1047            .to_string();
1048        assert_eq!(
1049            err,
1050            "Json error: Encountered unexpected '\"' whilst unicode escape"
1051        );
1052
1053        // Missing surrogate pair
1054        let mut decoder = tape_decoder();
1055        let err = decoder
1056            .decode(b"{\"hello\": \"\\ud83d\"}")
1057            .unwrap_err()
1058            .to_string();
1059        assert_eq!(
1060            err,
1061            "Json error: Encountered unexpected '\"' whilst parsing surrogate pair escape"
1062        );
1063
1064        // Test truncation
1065        let mut decoder = tape_decoder();
1066        decoder.decode(b"{\"he").unwrap();
1067        assert!(decoder.has_partial_row());
1068        assert_eq!(decoder.num_buffered_rows(), 1);
1069        let err = decoder.finish().unwrap_err().to_string();
1070        assert_eq!(err, "Json error: Truncated record whilst reading string");
1071
1072        let mut decoder = tape_decoder();
1073        decoder.decode(b"{\"hello\" : ").unwrap();
1074        let err = decoder.finish().unwrap_err().to_string();
1075        assert_eq!(err, "Json error: Truncated record whilst reading value");
1076
1077        let mut decoder = tape_decoder();
1078        decoder.decode(b"{\"hello\" : [").unwrap();
1079        let err = decoder.finish().unwrap_err().to_string();
1080        assert_eq!(err, "Json error: Truncated record whilst reading list");
1081
1082        let mut decoder = tape_decoder();
1083        decoder.decode(b"{\"hello\" : tru").unwrap();
1084        let err = decoder.finish().unwrap_err().to_string();
1085        assert_eq!(err, "Json error: Truncated record whilst reading true");
1086
1087        let mut decoder = tape_decoder();
1088        decoder.decode(b"{\"hello\" : nu").unwrap();
1089        let err = decoder.finish().unwrap_err().to_string();
1090        assert_eq!(err, "Json error: Truncated record whilst reading null");
1091
1092        // Test invalid UTF-8
1093        let mut decoder = tape_decoder();
1094        decoder.decode(b"{\"hello\" : \"world\xFF\"}").unwrap();
1095        let err = decoder.finish().unwrap_err().to_string();
1096        assert_eq!(err, "Json error: Encountered non-UTF-8 data");
1097
1098        let mut decoder = tape_decoder();
1099        decoder.decode(b"{\"\xe2\" : \"\x96\xa1\"}").unwrap();
1100        let err = decoder.finish().unwrap_err().to_string();
1101        assert_eq!(err, "Json error: Encountered truncated UTF-8 sequence");
1102    }
1103
1104    #[test]
1105    fn test_invalid_surrogates() {
1106        let mut decoder = tape_decoder();
1107        let res = decoder.decode(b"{\"test\": \"\\ud800\\ud801\"}");
1108        assert!(res.is_err());
1109
1110        let mut decoder = tape_decoder();
1111        let res = decoder.decode(b"{\"test\": \"\\udc00\\udc01\"}");
1112        assert!(res.is_err());
1113    }
1114
1115    #[test]
1116    fn test_flatten_top_level_arrays() {
1117        let input = r#"
1118        [
1119            {"hello": "world", "foo": 2, "bar": 45},
1120            {"a": true, "b": false, "c": null}
1121        ]
1122        [
1123            {"a": "b", "object": {"nested": "hello", "foo": 23}},
1124            {"a": ["", "foo", ["bar", "c"]]},
1125            {"hello": "world", "foo": 2, "bar": 27}
1126        ]"#;
1127        const TOTAL_ROWS: usize = 5;
1128
1129        // Check that regular decoding returns two rows
1130        let mut decoder = tape_decoder();
1131        decoder.decode(input.as_bytes()).unwrap();
1132        assert!(!decoder.has_partial_row());
1133        assert_eq!(decoder.num_buffered_rows(), 2);
1134
1135        let expected = TestCase::new()
1136            // {"hello": "world", "foo": 2, "bar": 45}
1137            .start_object(6)
1138            .string("hello")
1139            .string("world")
1140            .string("foo")
1141            .number("2")
1142            .string("bar")
1143            .number("45")
1144            .end_object(6)
1145            // {"a": true, "b": false, "c": null}
1146            .start_object(6)
1147            .string("a")
1148            .r#true()
1149            .string("b")
1150            .r#false()
1151            .string("c")
1152            .null()
1153            .end_object(6)
1154            // {"a": "b", "object": {"nested": "hello", "foo": 23}}
1155            .start_object(9)
1156            .string("a")
1157            .string("b")
1158            .string("object")
1159            .start_object(4)
1160            .string("nested")
1161            .string("hello")
1162            .string("foo")
1163            .number("23")
1164            .end_object(4)
1165            .end_object(9)
1166            // {"a": ["", "foo", ["bar", "c"]]}
1167            .start_object(9)
1168            .string("a")
1169            .start_list(6)
1170            .string("")
1171            .string("foo")
1172            .start_list(2)
1173            .string("bar")
1174            .string("c")
1175            .end_list(2)
1176            .end_list(6)
1177            .end_object(9)
1178            // {"hello": "world", "foo": 2, "bar": 27}
1179            .start_object(6)
1180            .string("hello")
1181            .string("world")
1182            .string("foo")
1183            .number("2")
1184            .string("bar")
1185            .number("27")
1186            .end_object(6);
1187
1188        // Check that decoding with `flatten_top_level_arrays` yields rows correctly,
1189        // and respects the configured batch size
1190        for batch_size in [1, 2, 3, 4, 8] {
1191            let mut decoder = TapeDecoder::new(TapeDecoderOptions {
1192                batch_size,
1193                num_fields: 2,
1194                flatten_top_level_arrays: true,
1195                allow_non_finite_floats: false,
1196            });
1197            decoder.decode(input.as_bytes()).unwrap();
1198            assert!(!decoder.has_partial_row());
1199            assert_eq!(decoder.num_buffered_rows(), batch_size.min(TOTAL_ROWS));
1200
1201            let finished = decoder.finish().unwrap();
1202            assert!(!decoder.has_partial_row());
1203            assert_eq!(decoder.num_buffered_rows(), batch_size.min(TOTAL_ROWS)); // didn't call clear() yet
1204            assert_eq!(
1205                finished.elements,
1206                &expected.elements[..finished.elements.len()]
1207            );
1208            assert_eq!(
1209                finished.strings,
1210                &expected.strings[..finished.strings.len()]
1211            );
1212            assert_eq!(
1213                finished.string_offsets,
1214                &expected.string_offsets[..finished.string_offsets.len()]
1215            );
1216
1217            decoder.clear();
1218            assert!(!decoder.has_partial_row());
1219            assert_eq!(decoder.num_buffered_rows(), 0);
1220        }
1221    }
1222
1223    /// The expected elements, strings and string offsets for a test case
1224    struct TestCase {
1225        elements: Vec<TapeElement>,
1226        strings: String,
1227        string_offsets: Vec<usize>,
1228    }
1229
1230    impl TestCase {
1231        fn new() -> Self {
1232            Self {
1233                elements: vec![TapeElement::Null],
1234                strings: String::new(),
1235                string_offsets: vec![0],
1236            }
1237        }
1238
1239        fn start_object(mut self, len: usize) -> Self {
1240            let end_idx = (self.elements.len() + len + 1) as u32;
1241            self.elements.push(TapeElement::StartObject(end_idx));
1242            self
1243        }
1244
1245        fn end_object(mut self, len: usize) -> Self {
1246            let start_idx = (self.elements.len() - len - 1) as u32;
1247            self.elements.push(TapeElement::EndObject(start_idx));
1248            self
1249        }
1250
1251        fn start_list(mut self, len: usize) -> Self {
1252            let end_idx = (self.elements.len() + len + 1) as u32;
1253            self.elements.push(TapeElement::StartList(end_idx));
1254            self
1255        }
1256
1257        fn end_list(mut self, len: usize) -> Self {
1258            let start_idx = (self.elements.len() - len - 1) as u32;
1259            self.elements.push(TapeElement::EndList(start_idx));
1260            self
1261        }
1262
1263        fn string(mut self, raw: &str) -> Self {
1264            let idx = (self.string_offsets.len() - 1) as u32;
1265            let start = self.strings.len();
1266            let end = start + raw.len();
1267            self.elements.push(TapeElement::String(idx));
1268            self.strings.push_str(raw);
1269            self.string_offsets.push(end);
1270            self
1271        }
1272
1273        fn number(mut self, raw: &str) -> Self {
1274            let idx = (self.string_offsets.len() - 1) as u32;
1275            let start = self.strings.len();
1276            let end = start + raw.len();
1277            self.elements.push(TapeElement::Number(idx));
1278            self.strings.push_str(raw);
1279            self.string_offsets.push(end);
1280            self
1281        }
1282
1283        fn r#true(mut self) -> Self {
1284            self.elements.push(TapeElement::True);
1285            self
1286        }
1287
1288        fn r#false(mut self) -> Self {
1289            self.elements.push(TapeElement::False);
1290            self
1291        }
1292
1293        fn null(mut self) -> Self {
1294            self.elements.push(TapeElement::Null);
1295            self
1296        }
1297    }
1298}