ocpi-tariffs 0.49.1

//! Hand-rolled single-pass recursive-descent JSON parser.
//!
//! # Responsibilities
//!
//! The parser is responsible for structural correctness only: balanced delimiters,
//! valid top-level values, and well-formed numbers. String content is captured as
//! [`RawStr`] slices of the source — escape sequences and control characters are
//! left untouched. Validation of string content is the responsibility of
//! [`crate::json::decode`].
//!
//! # Output
//!
//! [`parse`] returns a [`Document`] that wraps the root [`Element`] and the shared
//! [`DocumentInner`]. Every element carries an `Rc<DocumentInner>` so it can resolve
//! its own path after the [`Document`] has been dropped.
//!
//! # Limits
//!
//! - **Nesting depth**: capped at [`MAX_DEPTH`] (128 levels). Inputs that exceed this
//!   are rejected with [`ErrorKind::DepthLimitExceeded`].
//! - **Element count**: capped at `u32::MAX` by the [`ElemId`] counter, enforced via
//!   [`ErrorKind::MaxElements`]. In practice, the 5 megabytes [`string::ReasonableLen`] gate makes
//!   this limit unreachable at the moment.
//!
//! # Two-phase construction
//!
//! The [`Parser`] builds a private [`RawElement`] tree and a [`PathTable`] in one
//! pass. Once the full tree is available, [`into_element`] threads the shared
//! `Rc<DocumentInner>` through every node to produce the public [`Element`] tree.
//! This keeps the hot parsing loop free of reference-counting overhead.

#![expect(
    clippy::arithmetic_side_effects,
    reason = "pos is bounded by source.len() and only advances after a successful byte read; arithmetic is safe within parser state machine invariants"
)]
#![expect(
    clippy::as_conversions,
    reason = "byte position casts between usize and u32 are safe: usize->u32 is bounded by available memory, u32->usize always fits"
)]
#![expect(
    clippy::cast_possible_truncation,
    reason = "source length is bounded by available memory, so byte positions always fit in u32"
)]
#![expect(
    clippy::string_slice,
    reason = "span boundaries are always at ASCII JSON token boundaries, so slices are valid UTF-8"
)]

#[cfg(test)]
mod test;

#[cfg(test)]
mod test_basics;

#[cfg(test)]
mod test_parser;

#[cfg(test)]
mod test_type_sizes;

use std::rc::Rc;

use crate::{string, warning};

use super::{
    Document, DocumentInner, ElemId, Element, Field, Location, PathEntry, PathTable, RawStr, Span,
    Value,
};

/// Maximum nesting depth for arrays and objects.
///
/// RFC 8259 recommends implementations handle at least 128 levels of nesting.
/// Inputs that exceed this limit are rejected with [`ErrorKind::DepthLimitExceeded`].
const MAX_DEPTH: usize = 128;

// JSON whitespace characters `RFC 8259 s2`.
const SPACE: u8 = b' ';
const TAB: u8 = b'\t';
const LF: u8 = b'\n';
const CR: u8 = b'\r';

// Structural characters `RFC 8259 s2`.
const QUOTE: u8 = b'"';
const BACKSLASH: u8 = b'\\';
const COMMA: u8 = b',';
const COLON: u8 = b':';
const ARRAY_OPEN: u8 = b'[';
const ARRAY_CLOSE: u8 = b']';
const OBJECT_OPEN: u8 = b'{';
const OBJECT_CLOSE: u8 = b'}';

// Number-grammar characters `RFC 8259 s6`.
const MINUS: u8 = b'-';
const PLUS: u8 = b'+';
const DECIMAL_POINT: u8 = b'.';
const EXP_LOWER: u8 = b'e';
const EXP_UPPER: u8 = b'E';
const DIGIT_0: u8 = b'0';
const DIGIT_1: u8 = b'1';
const DIGIT_9: u8 = b'9';

// JSON keyword literals `RFC 8259 s3`.
const NULL: &str = "null";
const TRUE: &str = "true";
const FALSE: &str = "false";

// UTF-8 BOM (`U+FEFF`, encoded as 0xEF 0xBB 0xBF).
const BOM: &[u8; 3] = b"\xEF\xBB\xBF";

/// Parse a JSON document from `source`.
///
/// All string content in the returned tree borrows from `source`.
/// Call `element.path()` on any element to obtain its RFC 9535 path.
pub(crate) fn parse(source: string::ReasonableLen<'_>) -> Result<Document<'_>, Error> {
    let mut p = Parser::new(source.into_inner());
    // Skip a UTF-8 BOM (`U+FEFF` encoded as 0xEF 0xBB 0xBF) if present.
    if p.bytes.starts_with(BOM) {
        p.pos = BOM.len();
    }
    let raw_root = p.parse_value(PathEntry::Root)?;
    p.skip_ws();
    if p.pos < p.bytes.len() {
        return Err(p.error(ErrorKind::TrailingContent));
    }
    let inner = Rc::new(DocumentInner {
        source: source.into_inner(),
        paths: p.table,
    });
    let root = into_element(raw_root, &inner);
    Ok(Document { inner, root })
}

/// A parse error produced when the input is not well-formed JSON.
///
/// Carries the byte offset and line/column position of the failure, and an
/// [`ErrorKind`] that describes what was wrong.
#[derive(Debug)]
pub struct Error {
    /// Byte offset of the error location.
    byte_offset: usize,
    /// A file location expressed as line and column.
    position: Location,
    /// The details about the error that occurred.
    kind: ErrorKind,
}

impl Error {
    /// Byte offset of the error location.
    pub fn byte_offset(&self) -> usize {
        self.byte_offset
    }

    /// Return a reference to the details about the error that occurred.
    pub fn kind(&self) -> &ErrorKind {
        &self.kind
    }

    /// Consume the `Error` and return the details about the error that occurred.
    pub fn into_kind(self) -> ErrorKind {
        self.kind
    }

    /// Consume the `Error` and return the byte offset of the error location and the details of the
    /// error that occurred.
    pub fn into_parts(self) -> (usize, ErrorKind) {
        (self.byte_offset, self.kind)
    }
}

/// The specific reason a [`parse`] call failed.
#[derive(Debug, Eq, PartialEq)]
pub enum ErrorKind {
    /// A character that cannot be a JSON number was encountered.
    ExpectedNumeral,
    /// A character that cannot start a JSON value was encountered.
    ExpectedStart,
    /// A literal that cannot start or continue a JSON value was encountered.
    ExpectedLiteral { expected: &'static str },
    /// An array wasn't terminated correctly.
    ExpectedEndArray,
    /// An object wasn't terminated correctly.
    ExpectedEndObject,
    /// A character that cannot continue a JSON value was encountered.
    UnexpectedChar { expected: char },
    /// The input ended before the value was complete.
    UnexpectedEOF,
    /// Non-whitespace bytes follow the root value.
    TrailingContent,
    /// The input exceeds the maximum supported nesting depth.
    DepthLimitExceeded,
    /// The input contains more than [`u32::MAX`] JSON elements.
    MaxElements,
}

impl crate::Warning for Error {
    fn id(&self) -> warning::Id {
        let s = match self.kind {
            ErrorKind::ExpectedNumeral => "expected_numeral",
            ErrorKind::ExpectedStart => "expected_start",
            ErrorKind::ExpectedLiteral { .. } => "expected_literal",
            ErrorKind::ExpectedEndArray => "expected_end_array",
            ErrorKind::ExpectedEndObject => "expected_end_object",
            ErrorKind::UnexpectedChar { .. } => "unexpected_char",
            ErrorKind::UnexpectedEOF => "unexpected_eof",
            ErrorKind::TrailingContent => "trailing_content",
            ErrorKind::DepthLimitExceeded => "depth_limit_exceeded",
            ErrorKind::MaxElements => "max_elements",
        };

        warning::Id::from_static(s)
    }
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let Self {
            byte_offset,
            position,
            kind,
        } = self;

        match kind {
            ErrorKind::ExpectedLiteral { expected } => {
                write!(
                    f,
                    "unexpected literal found at line: `{position}`, byte `{byte_offset}`; expected: `{expected:?}`"
                )
            }
            ErrorKind::ExpectedNumeral => {
                write!(
                    f,
                    "unexpected numeral found at line: `{position}`, byte `{byte_offset}`; expected: `0-9`"
                )
            }
            ErrorKind::ExpectedStart => {
                write!(
                    f,
                    "unexpected start character found at line: `{position}`, byte `{byte_offset}`; expected one of: `[n, t, f, \", -, 0-9, [, {{]`"
                )
            }
            ErrorKind::ExpectedEndArray => {
                write!(
                    f,
                    "unexpected character found at line: `{position}`, byte `{byte_offset}`; expected: `,` or `]`"
                )
            }
            ErrorKind::ExpectedEndObject => {
                write!(
                    f,
                    "unexpected character found at line: `{position}`, byte `{byte_offset}`; expected: `,` or `}}`"
                )
            }
            ErrorKind::UnexpectedChar { expected } => {
                write!(
                    f,
                    "unexpected character `{expected}` found at line: `{position}`, byte `{byte_offset}``"
                )
            }
            ErrorKind::UnexpectedEOF => write!(
                f,
                "unexpected end of input found at line: `{position}`, byte `{byte_offset}`"
            ),
            ErrorKind::TrailingContent => write!(
                f,
                "trailing content found at line: `{position}`, byte `{byte_offset}`"
            ),
            ErrorKind::DepthLimitExceeded => {
                write!(f, "nesting depth exceeds the {MAX_DEPTH}-level limit")
            }
            ErrorKind::MaxElements => write!(f, "document exceeds {} JSON elements", u32::MAX),
        }
    }
}

impl std::error::Error for Error {}

/// Parser-private element tree; carries no reference to [`DocumentInner`].
///
/// Converted to the public [`Element`] tree by [`into_element`] after
/// [`DocumentInner`] is constructed.
struct RawElement<'buf> {
    /// Unique identifier within the document; sequentially assigned depth-first.
    id: ElemId,
    /// Byte range of the value only; use for replacement edits.
    span: Span,
    /// End of the value plus any trailing comma and whitespace; use for removal edits.
    /// Equal to `span.end` when there is no trailing comma (root element, or last sibling).
    full_span_end: u32,
    /// Parsed value, borrowing from the source `&str`.
    value: RawValue<'buf>,
}

/// The parsed content of a [`RawElement`], mirroring [`Value`] but without [`DocumentInner`].
///
/// Strings are kept as [`RawStr`] slices of the source; numbers are kept as
/// raw `&str` slices. Both are converted to their public forms by [`into_element`].
enum RawValue<'buf> {
    /// JSON `null` literal.
    Null,
    /// JSON `true` literal.
    True,
    /// JSON `false` literal.
    False,
    /// String content with quotes removed; escape sequences are not decoded.
    String(RawStr<'buf>),
    /// Raw number text; not guaranteed to fit any specific numeric type.
    Number(&'buf str),
    /// Ordered list of child elements.
    Array(Vec<RawElement<'buf>>),
    /// Ordered list of key-value fields.
    Object(Vec<RawField<'buf>>),
}

/// A key-value pair inside a JSON object, mirroring [`Field`] but without [`DocumentInner`].
///
/// `key_span` covers the quoted key bytes in the source, including the surrounding
/// double-quotes. The value is stored as a [`RawElement`].
struct RawField<'buf> {
    /// Span of the key token, including surrounding `"` delimiters.
    key_span: Span,
    /// The value element; its path ends with the key from `key_span`.
    element: RawElement<'buf>,
}

/// Single-pass recursive-descent JSON parser.
///
/// Holds all mutable state for one parse: the source string, a byte cursor, an
/// [`ElemId`] counter, the [`PathTable`] being built, and a nesting-depth guard.
///
/// Call [`Parser::new`] to create an instance, then [`Parser::parse_value`] to
/// drive the parse. The result is a [`RawElement`] tree; pass it together with
/// the completed [`PathTable`] to [`into_element`] to obtain the public
/// [`Element`] tree with shared [`DocumentInner`] attached.
struct Parser<'buf> {
    /// The full source string; all span byte positions are relative to this.
    source: &'buf str,
    /// Byte view of `source`; used for index-based reads without UTF-8 overhead.
    bytes: &'buf [u8],
    /// Current read position in bytes.
    pos: usize,
    /// Counter for assigning sequential [`ElemId`]s depth-first.
    next_id: usize,
    /// Path table being built as elements are parsed.
    table: PathTable<'buf>,
    /// Current nesting depth; checked against [`MAX_DEPTH`] on each container open.
    depth: usize,
}

impl<'buf> Parser<'buf> {
    /// Creates a `Parser` that will read from `source`.
    fn new(source: &'buf str) -> Self {
        Self {
            source,
            bytes: source.as_bytes(),
            pos: 0,
            next_id: 0,
            table: PathTable::default(),
            depth: 0,
        }
    }

    /// Allocates the next sequential [`ElemId`] and advances the counter.
    fn alloc_id(&mut self) -> Result<ElemId, Error> {
        let id = ElemId(self.next_id);
        self.next_id = self
            .next_id
            .checked_add(1)
            .ok_or_else(|| self.error(ErrorKind::MaxElements))?;
        Ok(id)
    }

    /// Advances past any JSON whitespace (`space`, `tab`, `CR`, `LF`) at the current position.
    fn skip_ws(&mut self) {
        while matches!(self.bytes.get(self.pos), Some(&SPACE | &TAB | &LF | &CR)) {
            self.chomp();
        }
    }

    /// Returns the byte at the current position without advancing, or `None` at end of input.
    fn peek(&self) -> Option<u8> {
        self.bytes.get(self.pos).copied()
    }

    /// Advances the cursor by one byte.
    #[inline]
    fn chomp(&mut self) {
        self.pos += 1;
    }

    /// Create and return an `Error`.
    fn error(&self, kind: ErrorKind) -> Error {
        let parsed = &self.source[..self.pos];
        Error {
            byte_offset: parsed.len(),
            position: super::line_col(parsed),
            kind,
        }
    }

    /// Returns the byte at the current position and advances past it, or `None` at end of input.
    fn advance(&mut self) -> Option<u8> {
        let b = self.bytes.get(self.pos).copied();
        if b.is_some() {
            self.chomp();
        }
        b
    }

    /// Asserts that the next byte equals `byte` and advances past it.
    ///
    /// Returns [`ErrorKind::UnexpectedChar`] if a different byte is present, or
    /// [`ErrorKind::UnexpectedEOF`] if the input is exhausted.
    fn expect_byte(&mut self, byte: u8) -> Result<(), Error> {
        match self.bytes.get(self.pos) {
            Some(&b) if b == byte => {
                self.chomp();
                Ok(())
            }
            Some(_) => Err(self.error(ErrorKind::UnexpectedChar {
                expected: char::from(byte),
            })),
            None => Err(self.error(ErrorKind::UnexpectedEOF)),
        }
    }

    /// Asserts that the next bytes match `literal` byte-for-byte, advancing past them.
    ///
    /// Used for JSON keywords (`null`, `true`, `false`). The caller dispatches via
    /// [`Self::peek`] without consuming the first byte, so `literal` must include it.
    fn expect_literal(&mut self, literal: &'static str) -> Result<(), Error> {
        for &expected in literal.as_bytes() {
            match self.advance() {
                Some(b) if b == expected => {}
                Some(_) => {
                    self.pos -= 1;
                    return Err(self.error(ErrorKind::ExpectedLiteral { expected: literal }));
                }
                None => return Err(self.error(ErrorKind::UnexpectedEOF)),
            }
        }
        Ok(())
    }

    /// Parses one JSON value preceded by optional whitespace and returns a fully-formed [`Element`].
    ///
    /// Allocates an [`ElemId`] and records the path `entry` before dispatching to
    /// [`Self::parse_value_kind`], so child elements produced during that call
    /// already find this element's id in the table as their parent.
    fn parse_value(&mut self, entry: PathEntry<'buf>) -> Result<RawElement<'buf>, Error> {
        self.skip_ws();
        // ID and table entry are registered before recursing so that child elements
        // produced by parse_value_kind see this id as their parent.
        let id = self.alloc_id()?;
        self.table.push(entry);
        let start = self.pos;
        let value = self.parse_value_kind(id)?;
        let span = Span::new(start as u32, self.pos as u32);
        Ok(RawElement {
            id,
            span,
            // The parent container extends this past the trailing comma and whitespace
            // when it exists, so that the element's removal span covers its own separator.
            full_span_end: span.end,
            value,
        })
    }

    /// Dispatches to the type-specific parser based on the first byte of the value.
    ///
    /// `id` is this element's own [`ElemId`], threaded down to [`Self::parse_array`]
    /// and [`Self::parse_object`] so they can record it as the parent of their children.
    fn parse_value_kind(&mut self, id: ElemId) -> Result<RawValue<'buf>, Error> {
        match self
            .peek()
            .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?
        {
            b'n' => {
                self.expect_literal(NULL)?;
                Ok(RawValue::Null)
            }
            b't' => {
                self.expect_literal(TRUE)?;
                Ok(RawValue::True)
            }
            b'f' => {
                self.expect_literal(FALSE)?;
                Ok(RawValue::False)
            }
            QUOTE => Ok(RawValue::String(self.parse_raw_str()?)),
            MINUS | DIGIT_0..=DIGIT_9 => Ok(RawValue::Number(self.parse_number_str()?)),
            ARRAY_OPEN => self.parse_array(id),
            OBJECT_OPEN => self.parse_object(id),
            _ => Err(self.error(ErrorKind::ExpectedStart)),
        }
    }

    /// Parses a JSON number and returns the raw source slice.
    ///
    /// Grammar `RFC 8259 s6`:
    /// ```text
    /// number = [ '-' ] int [ frac ] [ exp ]
    /// int    = '0' | [1-9] DIGIT*
    /// frac   = '.' DIGIT+
    /// exp    = ('e'|'E') ['+'|'-'] DIGIT+
    /// ```
    fn parse_number_str(&mut self) -> Result<&'buf str, Error> {
        let start = self.pos;

        if self.peek() == Some(MINUS) {
            self.chomp();
        }

        match self
            .peek()
            .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?
        {
            // A lone '0' is the only valid integer starting with zero; more digits
            // after it would be a leading-zero violation (e.g. "01" is invalid JSON).
            DIGIT_0 => self.chomp(),
            DIGIT_1..=DIGIT_9 => {
                while matches!(self.peek(), Some(DIGIT_0..=DIGIT_9)) {
                    self.chomp();
                }
            }
            _ => return Err(self.error(ErrorKind::ExpectedNumeral)),
        }

        if self.peek() == Some(DECIMAL_POINT) {
            self.chomp();
            // At least one digit is required after the decimal point.
            if !matches!(self.peek(), Some(DIGIT_0..=DIGIT_9)) {
                return Err(match self.peek() {
                    Some(_) => self.error(ErrorKind::ExpectedNumeral),
                    None => self.error(ErrorKind::UnexpectedEOF),
                });
            }
            while matches!(self.peek(), Some(DIGIT_0..=DIGIT_9)) {
                self.chomp();
            }
        }

        if matches!(self.peek(), Some(EXP_LOWER | EXP_UPPER)) {
            self.chomp();
            if matches!(self.peek(), Some(PLUS | MINUS)) {
                self.chomp();
            }
            // At least one digit is required after the exponent indicator (and optional sign).
            if !matches!(self.peek(), Some(DIGIT_0..=DIGIT_9)) {
                return Err(match self.peek() {
                    Some(_) => self.error(ErrorKind::ExpectedNumeral),
                    None => self.error(ErrorKind::UnexpectedEOF),
                });
            }
            while matches!(self.peek(), Some(DIGIT_0..=DIGIT_9)) {
                self.chomp();
            }
        }

        Ok(&self.source[start..self.pos])
    }

    /// Parses a JSON string and returns a [`RawStr`] with quotes stripped.
    ///
    /// Scans for the closing `"` delimiter, skipping one byte after every `\`
    /// so that `\"` does not terminate the string. Escape sequences and control
    /// characters are not validated here; callers use [`RawStr::decode_escapes`].
    fn parse_raw_str(&mut self) -> Result<RawStr<'buf>, Error> {
        self.expect_byte(QUOTE)?;
        let content_start = self.pos; // First byte after the opening `"`.

        loop {
            match self
                .advance()
                .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?
            {
                QUOTE => break,
                BACKSLASH => {
                    // Consume whatever follows so that `\"` does not close the string.
                    self.advance()
                        .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?;
                }
                _ => {}
            }
        }

        // `advance()` left `pos` one past the closing '"', so `pos-1` is the '"' itself;
        // `content_start..pos-1` therefore captures content without either delimiter.
        Ok(RawStr(&self.source[content_start..self.pos - 1]))
    }

    /// Parses a JSON array `[...]` and returns [`Value::Array`].
    ///
    /// Increments the depth counter before consuming `[` and returns
    /// [`ErrorKind::DepthLimitExceeded`] if the limit is exceeded.
    fn parse_array(&mut self, parent_id: ElemId) -> Result<RawValue<'buf>, Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(self.error(ErrorKind::DepthLimitExceeded));
        }
        self.expect_byte(ARRAY_OPEN)?;
        self.skip_ws();
        let mut elements: Vec<RawElement<'buf>> = Vec::new();

        if self.peek() != Some(ARRAY_CLOSE) {
            loop {
                let entry = PathEntry::Item {
                    parent: parent_id,
                    index: elements.len() as u32,
                };
                let mut elem = self.parse_value(entry)?;
                self.skip_ws();
                match self
                    .peek()
                    .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?
                {
                    COMMA => {
                        self.chomp();
                        self.skip_ws();
                        if self.peek() == Some(ARRAY_CLOSE) {
                            return Err(self.error(ErrorKind::ExpectedEndArray));
                        }
                        // Extend past the comma and leading whitespace of the next sibling
                        // so that removing this element also removes its own separator.
                        elem.full_span_end = self.pos as u32;
                        elements.push(elem);
                    }
                    ARRAY_CLOSE => {
                        elements.push(elem);
                        break;
                    }
                    _ => return Err(self.error(ErrorKind::ExpectedEndArray)),
                }
            }
        }

        self.expect_byte(ARRAY_CLOSE)?;
        self.depth -= 1;
        Ok(RawValue::Array(elements))
    }

    /// Parses a JSON object `{...}` and returns [`Value::Object`].
    ///
    /// Increments the depth counter before consuming `{` and returns
    /// [`ErrorKind::DepthLimitExceeded`] if the limit is exceeded.
    fn parse_object(&mut self, parent_id: ElemId) -> Result<RawValue<'buf>, Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(self.error(ErrorKind::DepthLimitExceeded));
        }
        self.expect_byte(OBJECT_OPEN)?;
        self.skip_ws();
        let mut fields: Vec<RawField<'buf>> = Vec::new();

        if self.peek() != Some(OBJECT_CLOSE) {
            loop {
                let key_start = self.pos;
                let key = self.parse_raw_str()?;
                let key_span = Span::new(key_start as u32, self.pos as u32);
                self.skip_ws();
                self.expect_byte(COLON)?;
                let entry = PathEntry::Field {
                    parent: parent_id,
                    key,
                };
                let mut elem = self.parse_value(entry)?;
                self.skip_ws();
                match self
                    .peek()
                    .ok_or_else(|| self.error(ErrorKind::UnexpectedEOF))?
                {
                    COMMA => {
                        self.chomp();
                        self.skip_ws();
                        if self.peek() == Some(OBJECT_CLOSE) {
                            return Err(self.error(ErrorKind::ExpectedEndObject));
                        }
                        // Same as in parse_array: extend past the comma and whitespace
                        // so that removing this field also removes its own separator.
                        elem.full_span_end = self.pos as u32;
                        fields.push(RawField {
                            key_span,
                            element: elem,
                        });
                    }
                    OBJECT_CLOSE => {
                        fields.push(RawField {
                            key_span,
                            element: elem,
                        });
                        break;
                    }
                    _ => return Err(self.error(ErrorKind::ExpectedEndObject)),
                }
            }
        }

        self.expect_byte(OBJECT_CLOSE)?;
        self.depth -= 1;
        Ok(RawValue::Object(fields))
    }
}

/// Converts a [`RawElement`] tree into the public [`Element`] tree, loading every
/// node with a clone of `inner` at construction time.
///
/// Uses an explicit work stack instead of recursion. Children are pushed in
/// reverse so they are processed in order; each `Build*` task then pops its
/// children off `done` and assembles the parent.
fn into_element<'buf>(raw: RawElement<'buf>, inner: &Rc<DocumentInner<'buf>>) -> Element<'buf> {
    enum Task<'buf> {
        Process(RawElement<'buf>),
        BuildArray {
            id: ElemId,
            span: Span,
            full_span_end: u32,
            count: usize,
        },
        BuildObject {
            id: ElemId,
            span: Span,
            full_span_end: u32,
            key_spans: Vec<Span>,
        },
    }

    let mut work: Vec<Task<'buf>> = vec![Task::Process(raw)];
    let mut done: Vec<Element<'buf>> = Vec::new();

    while let Some(task) = work.pop() {
        match task {
            Task::Process(raw) => {
                let value = match raw.value {
                    RawValue::Null => Value::Null,
                    RawValue::True => Value::True,
                    RawValue::False => Value::False,
                    RawValue::String(s) => Value::String(s),
                    RawValue::Number(n) => Value::Number(n),
                    RawValue::Array(items) => {
                        work.push(Task::BuildArray {
                            id: raw.id,
                            span: raw.span,
                            full_span_end: raw.full_span_end,
                            count: items.len(),
                        });
                        for item in items.into_iter().rev() {
                            work.push(Task::Process(item));
                        }
                        continue;
                    }
                    RawValue::Object(fields) => {
                        let key_spans = fields.iter().map(|f| f.key_span).collect();
                        work.push(Task::BuildObject {
                            id: raw.id,
                            span: raw.span,
                            full_span_end: raw.full_span_end,
                            key_spans,
                        });
                        for field in fields.into_iter().rev() {
                            work.push(Task::Process(field.element));
                        }
                        continue;
                    }
                };
                done.push(Element {
                    doc: Rc::clone(inner),
                    id: raw.id,
                    span: raw.span,
                    full_span_end: raw.full_span_end,
                    value,
                });
            }
            Task::BuildArray {
                id,
                span,
                full_span_end,
                count,
            } => {
                let start = done.len() - count;
                let items: Vec<Element<'buf>> = done.drain(start..).collect();
                done.push(Element {
                    doc: Rc::clone(inner),
                    id,
                    span,
                    full_span_end,
                    value: Value::Array(items),
                });
            }
            Task::BuildObject {
                id,
                span,
                full_span_end,
                key_spans,
            } => {
                let count = key_spans.len();
                let start = done.len() - count;
                let elements: Vec<Element<'buf>> = done.drain(start..).collect();
                let fields = key_spans
                    .into_iter()
                    .zip(elements)
                    .map(|(key_span, element)| Field { key_span, element })
                    .collect();
                done.push(Element {
                    doc: Rc::clone(inner),
                    id,
                    span,
                    full_span_end,
                    value: Value::Object(fields),
                });
            }
        }
    }

    // Each Process task produces exactly one element in `done`, either directly
    // (scalars) or via a Build task (containers). Starting with one root Process
    // task guarantees exactly one element remains here.
    done.swap_remove(0)
}