ocpi_tariffs/json/

parser.rs

//! A JSON parse built to keep track of where each element came from in the input.
#[cfg(test)]
pub(crate) mod test;

#[cfg(test)]
mod test_basic_happy_structure;

#[cfg(test)]
mod test_error_reporting;

#[cfg(test)]
mod test_type_sizes;

#[cfg(test)]
mod test_line_col;

#[cfg(test)]
mod test_raw_str;

#[cfg(test)]
mod test_parser;

use std::borrow::{Borrow, Cow};
use std::fmt;
use std::iter::Peekable;
use std::num::TryFromIntError;
use std::str::Bytes;
use std::sync::atomic::AtomicUsize;
use std::sync::Arc;

use json_tools::{Buffer, BufferType};
use tracing::{debug, trace};

use crate::{warning, Caveat, ReasonableStr};

use super::{
    decode::{self, unescape_str},
    Element, Field, ObjectKind, PathNode, PathNodeRef, Value, ValueKind,
};
use super::{ElemId, Path};

/// We peek at the next `Token` when asserting on trailing commas.
type Lexer<'buf> = Peekable<json_tools::Lexer<Bytes<'buf>>>;

/// Parse the JSON into a tree of [`Element`]s.
pub(crate) fn parse(json: ReasonableStr<'_>) -> Result<Element<'_>, Error> {
    let parser = Parser::new(json.into_inner());

    // When just parsing the JSON into an `Element` we only care about the final event
    // when the JSON has been completely transformed into a root element.
    for event in parser {
        if let Event::Complete(element) = event? {
            return Ok(element);
        }
    }

    Err(ErrorKind::UnexpectedEOF
        .into_partial_error_without_token()
        .with_root_path())
}

/// A parsing event emitted for each call to the `<Parser as Iterator>::next` function.
#[derive(Debug)]
pub(crate) enum Event<'buf> {
    /// An [`Element`] has been opened and it's construction is in progress.
    Open {
        kind: ObjectKind,
        parent_path: PathNodeRef<'buf>,
    },

    /// An [`Element`] has been created and added to its parent [`Element`].
    ///
    /// If the kind is `Array` or `Object` that means that this element is closed: its construction is complete.
    Element {
        /// The kind of JSON value the [`Element`] is.
        kind: ValueKind,
        /// The path to the parent [`Element`].
        parent_path: PathNodeRef<'buf>,
    },

    /// The parse has completed creating the tree of [`Element`]s.
    Complete(Element<'buf>),
}

/// The context needed to parse a single chunk of JSON.
pub(crate) struct Parser<'buf> {
    /// Used to assign a unique [`ElemId`] to each [`Element`].
    elem_count: AtomicUsize,

    /// True if the `Parser` is complete.
    ///
    /// Any further calls to [`Parser::next`] will return `None`.
    complete: bool,

    /// The source JSON we're parsing.
    json: &'buf str,

    /// The JSON lexer.
    lexer: Lexer<'buf>,

    /// The pool with pre-allocated `Path`s.
    path_pool: PathPool<'buf>,

    /// The stack to track nested objects.
    stack: Stack<'buf>,

    /// The previous token seen.
    token: Option<Token>,
}

/// Define our own `TokenType` so Clone can be defined on it.
///
/// This can be removed when `json_tools::TokenType` impls `Clone`.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub enum TokenType {
    /// `false`.
    BooleanFalse,
    /// `true`.
    BooleanTrue,

    /// `]`.
    BracketClose,
    /// `[`.
    BracketOpen,

    /// `:`.
    Colon,

    /// `,`.
    Comma,

    /// `}`.
    CurlyClose,
    /// `{`.
    CurlyOpen,

    /// The type of the token could not be identified.
    /// Should be removed if this lexer is ever to be feature complete.
    Invalid,

    /// `null`.
    Null,

    /// A Number, like `1.1234` or `123` or `-0.0` or `-1` or `.0` or `.`.
    Number,

    /// A JSON string, like `"foo"`.
    String,
}

impl TokenType {
    fn as_str(self) -> &'static str {
        match self {
            TokenType::BooleanFalse => "false",
            TokenType::BooleanTrue => "true",
            TokenType::BracketClose => "]",
            TokenType::BracketOpen => "[",
            TokenType::Colon => ":",
            TokenType::Comma => ",",
            TokenType::CurlyClose => "}",
            TokenType::CurlyOpen => "{",
            TokenType::Invalid => "<invalid>",
            TokenType::Null => "null",
            TokenType::Number => "<number>",
            TokenType::String => "<string>",
        }
    }
}

impl fmt::Display for TokenType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.as_str())
    }
}

impl From<json_tools::TokenType> for TokenType {
    fn from(value: json_tools::TokenType) -> Self {
        match value {
            json_tools::TokenType::BooleanFalse => TokenType::BooleanFalse,
            json_tools::TokenType::BooleanTrue => TokenType::BooleanTrue,
            json_tools::TokenType::BracketClose => TokenType::BracketClose,
            json_tools::TokenType::BracketOpen => TokenType::BracketOpen,
            json_tools::TokenType::CurlyClose => TokenType::CurlyClose,
            json_tools::TokenType::CurlyOpen => TokenType::CurlyOpen,
            json_tools::TokenType::Colon => TokenType::Colon,
            json_tools::TokenType::Comma => TokenType::Comma,
            json_tools::TokenType::Invalid => TokenType::Invalid,
            json_tools::TokenType::Null => TokenType::Null,
            json_tools::TokenType::Number => TokenType::Number,
            json_tools::TokenType::String => TokenType::String,
        }
    }
}

/// A lexical token, identifying its kind and span.
///
/// We define our own `Token` as the `json_tools::Token` defines a `Buffer` that can be heap allocated
/// or a `Span`. We only use the `Span` variant.
///
/// Our `Token` can also impl `Copy` and `Clone` as the size and semantics are acceptable.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct Token {
    /// The exact type of the token.
    pub kind: TokenType,

    /// The span allows the caller to reference back into the source byte stream
    /// to obtain the string making up the token.
    pub span: Span,
}

impl Token {
    /// Return true is the token is an opening brace.
    fn is_opening(&self) -> bool {
        matches!(self.kind, TokenType::CurlyOpen | TokenType::BracketOpen)
    }

    /// Return true is the token is a closing brace.
    fn is_closing(&self) -> bool {
        matches!(self.kind, TokenType::CurlyClose | TokenType::BracketClose)
    }

    /// Return true is the token is a comma.
    fn is_comma(&self) -> bool {
        matches!(self.kind, TokenType::Comma)
    }
}

impl fmt::Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "token: {}, ({},{})",
            self.kind, self.span.start, self.span.end
        )
    }
}

impl TryFrom<json_tools::Token> for Token {
    type Error = PartialError;

    fn try_from(token: json_tools::Token) -> Result<Self, Self::Error> {
        let json_tools::Token { kind, buf } = token;
        let kind = kind.into();
        let Buffer::Span(span) = &buf else {
            return Err(InternalError::BufferType.into_partial_error(None));
        };

        let span = span
            .try_into()
            .map_err(|err| InternalError::from(err).into_partial_error(None))?;

        Ok(Self { kind, span })
    }
}

impl TryFrom<&json_tools::Token> for Token {
    type Error = PartialError;

    fn try_from(token: &json_tools::Token) -> Result<Self, Self::Error> {
        let json_tools::Token { kind, buf } = token;
        let kind = kind.clone().into();
        let Buffer::Span(span) = &buf else {
            return Err(InternalError::BufferType.into_partial_error(None));
        };

        let span = span
            .try_into()
            .map_err(|err| InternalError::from(err).into_partial_error(None))?;

        Ok(Self { kind, span })
    }
}

impl<'buf> Parser<'buf> {
    pub fn new(json: &'buf str) -> Self {
        let lexer = json_tools::Lexer::new(json.bytes(), BufferType::Span).peekable();

        Self {
            elem_count: AtomicUsize::new(0),
            complete: false,
            json,
            lexer,
            path_pool: PathPool::default(),
            stack: Stack::new(),
            token: None,
        }
    }

    fn next_elem_id(&self) -> ElemId {
        let id = self
            .elem_count
            .fetch_add(1, std::sync::atomic::Ordering::Relaxed);

        ElemId(id)
    }

    fn expect_next(&mut self) -> Result<Token, PartialError> {
        let Some(token) = self.lexer.next() else {
            return Err(ErrorKind::UnexpectedEOF.into_partial_error(self.token.take()));
        };

        let token = token.try_into()?;

        Ok(token)
    }

    /// Return an `Err` if the next token is not the expected.
    fn expect_token(&mut self, token_type: TokenType) -> Result<(), PartialError> {
        let Some(token) = self.lexer.next() else {
            return Err(ErrorKind::UnexpectedEOF.into_partial_error(self.token.take()));
        };

        let token: Token = token.try_into()?;

        if token.kind == token_type {
            Ok(())
        } else {
            Err(unexpected_token(token))
        }
    }

    #[expect(
        clippy::cognitive_complexity,
        reason = "Lifetimes make splitting this function more effort than it's worth"
    )]
    fn next_event(&mut self) -> Result<Option<Event<'buf>>, Error> {
        if self.complete {
            return Ok(None);
        }

        let head = self.stack.pop_head();

        match head {
            None => {
                let token = self.expect_next().with_root_path()?;

                trace!(?token);
                self.comma_checks(&token).with_root_path()?;

                match token.kind {
                    TokenType::CurlyOpen => {
                        let parent_path = self.path_pool.root();
                        self.stack.push_new_object(
                            self.next_elem_id(),
                            Arc::clone(&parent_path),
                            &token,
                        );
                        Ok(Some(Event::Open {
                            kind: ObjectKind::Object,
                            parent_path,
                        }))
                    }
                    TokenType::BracketOpen => {
                        let parent_path = self.path_pool.root();
                        self.stack.push_new_array(
                            self.next_elem_id(),
                            Arc::clone(&parent_path),
                            &token,
                        );
                        Ok(Some(Event::Open {
                            kind: ObjectKind::Array,
                            parent_path,
                        }))
                    }
                    TokenType::Number => {
                        let value = Value::Number(token_str(self.json, &token).with_root_path()?);
                        self.exit_with_value(token, value).with_root_path()
                    }
                    TokenType::Null => self.exit_with_value(token, Value::Null).with_root_path(),
                    TokenType::String => {
                        let value =
                            Value::String(token_str_as_string(self.json, token).with_root_path()?);
                        self.exit_with_value(token, value).with_root_path()
                    }
                    TokenType::BooleanTrue => {
                        self.exit_with_value(token, Value::True).with_root_path()
                    }
                    TokenType::BooleanFalse => {
                        self.exit_with_value(token, Value::False).with_root_path()
                    }
                    TokenType::BracketClose
                    | TokenType::Colon
                    | TokenType::Comma
                    | TokenType::CurlyClose
                    | TokenType::Invalid => Err(unexpected_token(token).with_root_path()),
                }
            }
            Some(mut head) => {
                let token = self.expect_next().with_head(&head)?;

                trace!(?token, head = ?head.elem_type);
                let token = if self.comma_checks(&token).with_head(&head)? {
                    self.expect_next().with_head(&head)?
                } else {
                    token
                };

                let (value, token, path) = match head.elem_type {
                    ObjectKind::Object => {
                        let key = match token.kind {
                            TokenType::String => {
                                token_str_as_string(self.json, token).with_head(&head)?
                            }
                            TokenType::CurlyClose => {
                                let event = self.close_element(head, &token)?;
                                return Ok(event);
                            }
                            TokenType::BooleanFalse
                            | TokenType::BooleanTrue
                            | TokenType::BracketClose
                            | TokenType::BracketOpen
                            | TokenType::Colon
                            | TokenType::Comma
                            | TokenType::CurlyOpen
                            | TokenType::Invalid
                            | TokenType::Null
                            | TokenType::Number => {
                                return Err(unexpected_token(token).with_root_path())
                            }
                        };

                        self.expect_token(TokenType::Colon).with_head(&head)?;
                        let token = self.expect_next().with_head(&head)?;

                        let value = match token.kind {
                            TokenType::CurlyOpen => {
                                let Some(parent_path) =
                                    head.parent_is_object(&mut self.path_pool, key)
                                else {
                                    return Ok(None);
                                };
                                self.stack.push_head(head);
                                self.stack.push_new_object(
                                    self.next_elem_id(),
                                    Arc::clone(&parent_path),
                                    &token,
                                );
                                return Ok(Some(Event::Open {
                                    kind: ObjectKind::Object,
                                    parent_path,
                                }));
                            }
                            TokenType::BracketOpen => {
                                let Some(parent_path) =
                                    head.parent_is_object(&mut self.path_pool, key)
                                else {
                                    return Ok(None);
                                };
                                self.stack.push_head(head);
                                self.stack.push_new_array(
                                    self.next_elem_id(),
                                    Arc::clone(&parent_path),
                                    &token,
                                );
                                return Ok(Some(Event::Open {
                                    kind: ObjectKind::Array,
                                    parent_path,
                                }));
                            }
                            TokenType::CurlyClose => {
                                let event = self.close_element(head, &token)?;
                                return Ok(event);
                            }
                            TokenType::String => Value::String(
                                token_str_as_string(self.json, token).with_head(&head)?,
                            ),
                            TokenType::Number => {
                                Value::Number(token_str(self.json, &token).with_head(&head)?)
                            }
                            TokenType::Null => Value::Null,
                            TokenType::BooleanTrue => Value::True,
                            TokenType::BooleanFalse => Value::False,
                            TokenType::BracketClose
                            | TokenType::Colon
                            | TokenType::Comma
                            | TokenType::Invalid => {
                                return Err(unexpected_token(token).with_head(&head))
                            }
                        };

                        let Some(path) = head.parent_is_object(&mut self.path_pool, key) else {
                            return Ok(None);
                        };
                        (value, token, path)
                    }
                    ObjectKind::Array => {
                        let value = match token.kind {
                            TokenType::CurlyOpen => {
                                let Some(parent_path) = head.parent_is_array(&mut self.path_pool)
                                else {
                                    return Ok(None);
                                };
                                self.stack.push_head(head);
                                self.stack.push_new_object(
                                    self.next_elem_id(),
                                    Arc::clone(&parent_path),
                                    &token,
                                );
                                return Ok(Some(Event::Open {
                                    kind: ObjectKind::Object,
                                    parent_path,
                                }));
                            }
                            TokenType::BracketOpen => {
                                let Some(parent_path) = head.parent_is_array(&mut self.path_pool)
                                else {
                                    return Ok(None);
                                };
                                self.stack.push_head(head);
                                self.stack.push_new_array(
                                    self.next_elem_id(),
                                    Arc::clone(&parent_path),
                                    &token,
                                );
                                return Ok(Some(Event::Open {
                                    kind: ObjectKind::Array,
                                    parent_path,
                                }));
                            }
                            TokenType::BracketClose => {
                                let event = self.close_element(head, &token)?;
                                return Ok(event);
                            }

                            TokenType::String => Value::String(
                                token_str_as_string(self.json, token).with_head(&head)?,
                            ),
                            TokenType::Number => {
                                Value::Number(token_str(self.json, &token).with_head(&head)?)
                            }
                            TokenType::Null => Value::Null,
                            TokenType::BooleanTrue => Value::True,
                            TokenType::BooleanFalse => Value::False,
                            TokenType::Invalid
                            | TokenType::CurlyClose
                            | TokenType::Colon
                            | TokenType::Comma => {
                                return Err(unexpected_token(token).with_head(&head))
                            }
                        };
                        let Some(path) = head.parent_is_array(&mut self.path_pool) else {
                            return Ok(None);
                        };
                        (value, token, path)
                    }
                };

                let event = Event::Element {
                    kind: value.kind(),
                    parent_path: Arc::clone(&path),
                };
                head.push_field(self.next_elem_id(), path, value, &token);

                let peek_token = self.peek(&token).with_head(&head)?;

                if !(peek_token.is_comma() || peek_token.is_closing()) {
                    return Err(unexpected_token(peek_token).with_head(&head));
                }

                self.token.replace(token);
                self.stack.push_head(head);

                Ok(Some(event))
            }
        }
    }

    /// Close a [`PartialElement`] which creates an [`Element`] and returns an [`Event`].
    fn close_element(
        &mut self,
        head: PartialElement<'buf>,
        token: &Token,
    ) -> Result<Option<Event<'buf>>, Error> {
        let event = self.stack.head_into_element(head, token);

        match event {
            Pop::Element { kind, parent_path } => Ok(Some(Event::Element { kind, parent_path })),
            Pop::Complete(element) => {
                if let Some(token) = self.lexer.next() {
                    let token = token.try_into().with_root_path()?;
                    return Err(unexpected_token(token).with_root_path());
                }

                Ok(Some(Event::Complete(element)))
            }
        }
    }

    fn exit_with_value(
        &mut self,
        token: Token,
        value: Value<'buf>,
    ) -> Result<Option<Event<'buf>>, PartialError> {
        self.complete = true;
        let span = element_span(&token, 0);
        let elem = Element::new(self.next_elem_id(), Arc::new(PathNode::Root), span, value);

        if let Some(token) = self.lexer.next() {
            let token = token.try_into()?;
            return Err(unexpected_token(token));
        }

        Ok(Some(Event::Complete(elem)))
    }

    fn peek(&mut self, token: &Token) -> Result<Token, PartialError> {
        let Some(peek_token) = self.lexer.peek() else {
            return Err(ErrorKind::UnexpectedEOF.into_partial_error(Some(*token)));
        };

        let peek_token = peek_token.try_into()?;
        Ok(peek_token)
    }

    /// Perform comma position checks.
    ///
    /// Return `Err(unexpected)` if a trailing or rogue comma is found.
    fn comma_checks(&mut self, token: &Token) -> Result<bool, PartialError> {
        trace!(?token, "comma_checks");
        let is_comma = token.is_comma();

        if is_comma {
            let peek_token = self.peek(token)?;

            // A comma can only be followed by an opening brace or a value.
            if peek_token.is_closing() {
                return Err(unexpected_token(*token));
            }

            if peek_token.is_comma() {
                return Err(unexpected_token(peek_token));
            }
        } else if token.is_opening() {
            let peek_token = self.peek(token)?;

            // An opening brace should not be followed by a comma.
            if peek_token.is_comma() {
                return Err(unexpected_token(peek_token));
            }
        }

        Ok(is_comma)
    }
}

/// Create an [`PartialError`] with [`ErrorKind::UnexpectedToken`].
#[track_caller]
fn unexpected_token(token: Token) -> PartialError {
    ErrorKind::UnexpectedToken.into_partial_error(Some(token))
}

impl<'buf> Iterator for Parser<'buf> {
    type Item = Result<Event<'buf>, Error>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next_event() {
            Ok(event) => event.map(Ok),
            Err(err) => {
                self.complete = true;
                Some(Err(err))
            }
        }
    }
}

/// A partial `Element` that we descend into and parse it's child `Element`s.
#[derive(Debug)]
struct PartialElement<'buf> {
    /// The Id of the [`Element`] to be created.
    elem_id: ElemId,

    /// The type of [`Element`].
    elem_type: ObjectKind,

    /// The child [`Element`]s.
    ///
    /// This is filled as we parse the current JSON [`Element`].
    elements: Vec<Element<'buf>>,

    /// The path up to the [`Element`].
    path: PathNodeRef<'buf>,

    /// The index of the [`Element`]'s first byte.
    span_start: usize,
}

impl<'buf> PartialElement<'buf> {
    fn parent_is_object(
        &self,
        path_pool: &mut PathPool<'buf>,
        key: RawStr<'buf>,
    ) -> Option<PathNodeRef<'buf>> {
        path_pool.object(Arc::clone(&self.path), key)
    }

    fn parent_is_array(&self, path_pool: &mut PathPool<'buf>) -> Option<PathNodeRef<'buf>> {
        path_pool.array(Arc::clone(&self.path), self.elements.len())
    }

    fn push_field(
        &mut self,
        elem_id: ElemId,
        path: PathNodeRef<'buf>,
        value: Value<'buf>,
        token: &Token,
    ) {
        let span = element_span(token, token.span.start);
        let elem = Element::new(elem_id, path, span, value);
        self.elements.push(elem);
    }

    /// Resolve the `PartialElement` to an `Element`.
    fn into_element(self, token: &Token) -> Element<'buf> {
        let span = element_span(token, self.span_start);

        let PartialElement {
            elem_type,
            span_start: _,
            elements,
            path,
            elem_id,
        } = self;

        let value = match elem_type {
            ObjectKind::Object => {
                let fields = elements.into_iter().map(Field).collect();
                Value::Object(fields)
            }
            ObjectKind::Array => Value::Array(elements),
        };

        Element::new(elem_id, path, span, value)
    }
}

/// `Path`s are added and never removed.
struct PathPool<'buf> {
    index: usize,
    items: Vec<PathNodeRef<'buf>>,
}

impl Default for PathPool<'_> {
    fn default() -> Self {
        Self::with_capacity(1000)
    }
}

impl<'buf> PathPool<'buf> {
    fn with_capacity(capacity: usize) -> Self {
        let capacity = capacity.max(1);
        let mut items = Vec::with_capacity(capacity);
        items.resize_with(capacity, Default::default);

        Self { index: 0, items }
    }

    #[expect(
        clippy::indexing_slicing,
        reason = "The root Path is added in the constructor and the capacity is always at least 1"
    )]
    fn root(&self) -> PathNodeRef<'buf> {
        Arc::clone(&self.items[0])
    }

    /// Add a new `Path::Array` with the given index.
    fn array(&mut self, parent: PathNodeRef<'buf>, index: usize) -> Option<PathNodeRef<'buf>> {
        self.push(PathNode::Array { parent, index })
    }

    /// Add a new `Path::Object` with the given index.
    fn object(
        &mut self,
        parent: PathNodeRef<'buf>,
        key: RawStr<'buf>,
    ) -> Option<PathNodeRef<'buf>> {
        self.push(PathNode::Object { parent, key })
    }

    fn push(&mut self, new_path: PathNode<'buf>) -> Option<PathNodeRef<'buf>> {
        const GROWTH_FACTOR: usize = 2;

        let Self { index, items } = self;
        let next_index = index.checked_add(1)?;

        if next_index >= items.len() {
            items.reserve(items.len().saturating_mul(GROWTH_FACTOR));
            items.resize_with(items.capacity(), Default::default);
        }

        let path = items.get_mut(next_index)?;
        debug_assert_eq!(Arc::strong_count(path), 1, "Paths are only added");
        let path = Arc::get_mut(path)?;
        *path = new_path;

        let path = items.get_mut(next_index)?;
        let path_result = Arc::clone(path);

        *index = next_index;
        Some(path_result)
    }
}

/// The `Span` defines the range of bytes that delimits a JSON `Element`.
#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Ord, PartialOrd)]
pub struct Span {
    /// Index of the first the byte.
    pub start: usize,

    /// Index one past the last byte.
    pub end: usize,
}

impl TryFrom<&json_tools::Span> for Span {
    type Error = TryFromIntError;

    fn try_from(span: &json_tools::Span) -> Result<Self, Self::Error> {
        let json_tools::Span { first, end } = span;
        let start = usize::try_from(*first)?;
        let end = usize::try_from(*end)?;
        Ok(Span { start, end })
    }
}

struct Stack<'buf>(Vec<PartialElement<'buf>>);

enum Pop<'buf> {
    /// An [`Element`] has been created and added to its parent [`Element`].
    Element {
        kind: ValueKind,
        parent_path: PathNodeRef<'buf>,
    },

    /// The parse has completed creating the tree of [`Element`]s.
    Complete(Element<'buf>),
}

impl<'buf> Stack<'buf> {
    fn new() -> Self {
        Self(vec![])
    }

    /// The head `PartialElement` is popped off the stack temporarily to avoid lifetime issues if the
    /// stack `Vec` contains it.
    fn pop_head(&mut self) -> Option<PartialElement<'buf>> {
        self.0.pop()
    }

    /// The head `PartialElement` is popped off the stack temporarily to avoid lifetime issues if the
    /// stack `Vec` contains it.
    fn push_head(&mut self, head: PartialElement<'buf>) {
        self.0.push(head);
    }

    /// Convert the head `PartialElement` into an `Element` using the parent to form the path.
    fn head_into_element(&mut self, head: PartialElement<'buf>, token: &Token) -> Pop<'buf> {
        let elem = head.into_element(token);

        if let Some(parent) = self.0.last_mut() {
            let event = Pop::Element {
                kind: elem.value.kind(),
                parent_path: elem.path_node(),
            };
            parent.elements.push(elem);
            event
        } else {
            Pop::Complete(elem)
        }
    }

    fn push_new_object(&mut self, elem_id: ElemId, parent_path: PathNodeRef<'buf>, token: &Token) {
        self.push_new_elem(elem_id, parent_path, token, ObjectKind::Object);
    }

    fn push_new_array(&mut self, elem_id: ElemId, parent_path: PathNodeRef<'buf>, token: &Token) {
        self.push_new_elem(elem_id, parent_path, token, ObjectKind::Array);
    }

    fn push_new_elem(
        &mut self,
        elem_id: ElemId,
        parent_path: PathNodeRef<'buf>,
        token: &Token,
        elem_type: ObjectKind,
    ) {
        let partial = PartialElement {
            elements: vec![],
            elem_type,
            path: parent_path,
            span_start: token.span.start,
            elem_id,
        };
        self.0.push(partial);
    }
}

/// A parsing Error that keeps track of the token being parsed when the Error occurred and
/// the slice of JSON surrounding the Error location.
pub struct Error(Box<ErrorImpl>);

impl crate::Warning for Error {
    fn id(&self) -> warning::Id {
        match self.0.kind {
            ErrorKind::Internal(_) => warning::Id::from_static("internal"),
            ErrorKind::UnexpectedEOF => warning::Id::from_static("unexpected_eof"),
            ErrorKind::UnexpectedToken => warning::Id::from_static("unexpected_token"),
        }
    }
}

impl fmt::Debug for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}

impl From<ErrorImpl> for Error {
    fn from(err: ErrorImpl) -> Self {
        Self(err.into())
    }
}

struct ErrorImpl {
    /// The kind of error that occurred.
    kind: ErrorKind,

    /// The location the [`Error`] happened in the source code.
    loc: &'static std::panic::Location<'static>,

    /// The path to the [`Element`] the error occurred in.
    path: Path,

    /// The span of the JSON string the error occurred in.
    span: Span,

    /// The token being parsed at the time of the [`Error`].
    token: Option<Token>,
}

impl fmt::Debug for ErrorImpl {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Error")
            .field("kind", &self.kind)
            .field("loc", &self.loc)
            .field("path", &self.path)
            .field("span", &self.span)
            .field("token", &self.token)
            .finish()
    }
}

impl Error {
    /// The kind of error that occurred.
    pub fn kind(&self) -> &ErrorKind {
        &self.0.kind
    }

    /// The path to the element the error occurred in.
    pub fn path(&self) -> &Path {
        &self.0.path
    }

    /// The span of the [`Element`] the error occurred in.
    pub fn span(&self) -> Span {
        self.0.span
    }

    pub fn token(&self) -> Option<&Token> {
        self.0.token.as_ref()
    }

    /// Break the Error into its constituent parts.
    pub fn into_parts(self) -> (ErrorKind, Path, Span) {
        let ErrorImpl {
            kind,
            loc: _,
            path,
            span,
            token: _,
        } = *self.0;
        (kind, path, span)
    }

    /// Convert the Error into a more comprehensive report using the source JSON to provide
    /// human readable context.
    pub fn into_report(self, json: &str) -> ErrorReport<'_> {
        ErrorReport::from_error(self, json)
    }
}

/// A more comprehensive report on the [`Error`] using the source JSON `&str` to provide
/// human readable context.
#[derive(Debug)]
pub struct ErrorReport<'buf> {
    /// The [`Error`] that occurred.
    error: Error,

    /// The slice of JSON as defined by the `Error::span`.
    json_context: &'buf str,

    /// The slice of JSON as defined by the `Error::span` and expanded out to the
    /// start and end of the line.
    expanded_json_context: &'buf str,

    /// The line and col indices of the start and end of the span.
    span_bounds: SpanBounds,
}

impl<'buf> ErrorReport<'buf> {
    /// Create the `ErrorReport` from the `Error` and source `&str`.
    fn from_error(error: Error, json: &'buf str) -> Self {
        let span = error.span();
        debug!(?error, ?span, json, "from_error");
        let json_context = &json.get(span.start..span.end).unwrap_or(json);

        let start = {
            let s = &json.get(0..span.start).unwrap_or_default();
            line_col(s)
        };
        let end = {
            let relative_end = line_col(json_context);
            let line = start.line.saturating_add(relative_end.line);

            if start.line == line {
                LineCol {
                    line,
                    col: start.col.saturating_add(relative_end.col),
                }
            } else {
                LineCol {
                    line,
                    col: relative_end.col,
                }
            }
        };
        let (prev, next) = find_expanded_newlines(json, span.start);
        let expanded_json_context = &json.get(prev..next).unwrap_or(json_context);

        let span_bounds = SpanBounds { start, end };

        Self {
            error,
            json_context,
            expanded_json_context,
            span_bounds,
        }
    }

    /// Return the slice of JSON as defined by the `Error::span`.
    pub fn json_context(&self) -> &'buf str {
        self.json_context
    }

    /// Return the slice of JSON as defined by the `Error::span` and expanded out to the
    /// start and end of the line.
    pub fn expand_json_context(&self) -> &'buf str {
        self.expanded_json_context
    }

    /// Return the line and col number of each end of the span.
    pub fn span_bounds(&self) -> &SpanBounds {
        &self.span_bounds
    }

    /// Discard the `Report` and take ownership of the `Error`.
    pub fn into_error(self) -> Error {
        self.error
    }
}

fn find_expanded_newlines(json: &str, byte_index: usize) -> (usize, usize) {
    let pre = json.get(..byte_index).unwrap_or(json);
    let post = json.get(byte_index..).unwrap_or(json);

    let mut bytes = pre.as_bytes().iter().rev();
    let prev = pre
        .len()
        .saturating_sub(bytes.position(|b| *b == b'\n').unwrap_or_default());

    let mut bytes = post.as_bytes().iter();
    let next = bytes
        .position(|b| *b == b'\n')
        .map(|idx| idx.saturating_add(byte_index))
        .unwrap_or(prev.saturating_add(post.len()));

    (prev, next)
}

/// The line and col indices of the start and end of the span.
#[derive(Clone, Debug)]
pub struct SpanBounds {
    /// The start of the `Span` expressed as line and column index.
    pub start: LineCol,

    /// The end of the `Span` expressed as line and column index.
    pub end: LineCol,
}

/// A file location expressed as line and column.
#[derive(Clone, Debug)]
pub struct LineCol {
    /// The line index is 0 based.
    pub line: u32,

    /// The col index is 0 based.
    pub col: u32,
}

impl From<(u32, u32)> for LineCol {
    fn from(value: (u32, u32)) -> Self {
        Self {
            line: value.0,
            col: value.1,
        }
    }
}

impl From<LineCol> for (u32, u32) {
    fn from(value: LineCol) -> Self {
        (value.line, value.col)
    }
}

impl PartialEq<(u32, u32)> for LineCol {
    fn eq(&self, other: &(u32, u32)) -> bool {
        self.line == other.0 && self.col == other.1
    }
}

impl fmt::Display for LineCol {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}:{}", self.line, self.col)
    }
}

/// Return the line and column indices of the end of the slice.
///
/// The line and column indices are zero based.
pub fn line_col(s: &str) -> LineCol {
    let mut chars = s.chars().rev();
    let mut line = 0_u32;
    let mut col = 0_u32;

    // The col only needs to be calculated on the final line so we iterate from the last char
    // back to the start of the line and then only continue to count the lines after that.
    //
    // This is less work than continuously counting chars from the front of the slice.
    for c in chars.by_ref() {
        // If the `&str` is multiline, we count the line and stop accumulating the col count too.
        if c == '\n' {
            let Some(n) = line.checked_add(1) else {
                break;
            };
            line = n;
            break;
        }
        let Some(n) = col.checked_add(1) else {
            break;
        };
        col = n;
    }

    // The col is now known, continue to the start of the str counting newlines as we go.
    for c in chars {
        if c == '\n' {
            let Some(n) = line.checked_add(1) else {
                break;
            };
            line = n;
        }
    }

    LineCol { line, col }
}

/// An error that has yet to be resolved with a [`Span`].
#[derive(Debug)]
pub struct PartialError {
    /// The location the [`PartialError`] happened in the source code.
    kind: ErrorKind,

    /// The location the [`PartialError`] happened in the source code.
    loc: &'static std::panic::Location<'static>,

    /// The token being parsed at the time of the [`PartialError`].
    token: Option<Token>,
}

/// Convert a [`PartialError`] into an [`Error`] by providing a [`PartialElement`].
trait PartialIntoError<T> {
    /// Convert a [`PartialError`] into an [`Error`] with a path based on the given [`PartialElement`].
    fn with_head(self, head: &PartialElement<'_>) -> Result<T, Error>;

    /// Converts a [`PartialError`] into an [`Error`] with a root path.
    ///
    /// This can be used If the path is unknown or the [`Error`] occurred at the root.
    fn with_root_path(self) -> Result<T, Error>;
}

impl<T> PartialIntoError<T> for Result<T, PartialError> {
    fn with_head(self, head: &PartialElement<'_>) -> Result<T, Error> {
        match self {
            Ok(v) => Ok(v),
            Err(err) => Err(err.with_head(head)),
        }
    }

    fn with_root_path(self) -> Result<T, Error> {
        match self {
            Ok(v) => Ok(v),
            Err(err) => Err(err.with_root_path()),
        }
    }
}

impl PartialError {
    /// Convert a [`PartialError`] into an [`Error`] with a path based on the given [`PartialElement`].
    fn with_head(self, parent: &PartialElement<'_>) -> Error {
        let Self { loc, kind, token } = self;
        let span_end = token.map(|t| t.span.end).unwrap_or_default();

        let (path, span) = if let Some(elem) = parent.elements.last() {
            (
                Path::from_node(Arc::clone(&elem.path_node)),
                Span {
                    start: elem.span.start,
                    end: span_end,
                },
            )
        } else {
            (
                Path::from_node(Arc::clone(&parent.path)),
                Span {
                    start: parent.span_start,
                    end: span_end,
                },
            )
        };

        ErrorImpl {
            kind,
            loc,
            path,
            span,
            token,
        }
        .into()
    }

    /// Converts a `PartialError` into an `Error` with a root path.
    ///
    /// This can be used If the path is unknown or the `Error` occurred at the root.
    pub fn with_root_path(self) -> Error {
        let Self { loc, kind, token } = self;
        let (span_start, span_end) = match (&kind, token) {
            (ErrorKind::UnexpectedToken, Some(t)) => (t.span.start, t.span.end),
            (_, Some(t)) => (0, t.span.end),
            (_, None) => (0, 0),
        };
        ErrorImpl {
            loc,
            kind,
            path: Path::root(),
            span: Span {
                start: span_start,
                end: span_end,
            },
            token,
        }
        .into()
    }
}

/// The kind of Errors that can occur while parsing JSON.
#[derive(Debug)]
pub enum ErrorKind {
    /// An internal programming error.
    Internal(Box<dyn std::error::Error + Send + Sync + 'static>),

    /// The `Lexer` had no more tokens when more were expected.
    UnexpectedEOF,

    /// An unexpected token was emitted by the `Lexer`.
    UnexpectedToken,
}

impl ErrorKind {
    #[track_caller]
    fn into_partial_error(self, token: Option<Token>) -> PartialError {
        PartialError {
            kind: self,
            loc: std::panic::Location::caller(),
            token,
        }
    }

    #[track_caller]
    pub fn into_partial_error_without_token(self) -> PartialError {
        PartialError {
            kind: self,
            loc: std::panic::Location::caller(),
            token: None,
        }
    }
}

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

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let ErrorImpl {
            kind,
            loc,
            path,
            span: _,
            token,
        } = &*self.0;

        write!(
            f,
            "Error: code location: {loc}; while parsing element at `{path}`"
        )?;

        if let Some(token) = token {
            write!(f, " token: `{}`", token.kind)?;
        }

        match kind {
            ErrorKind::Internal(err) => write!(f, "Internal: {err}"),
            ErrorKind::UnexpectedEOF => f.write_str("Unexpected EOF"),
            ErrorKind::UnexpectedToken => write!(f, "unexpected token"),
        }
    }
}

/// A programming Error resulting from faulty logic.
///
/// This should not be exposed on the public API.
#[derive(Debug)]
enum InternalError {
    /// Slicing into the JSON buf failed.
    ///
    /// This should not happen during parsing, as the parsing and `Span` calculations are all
    /// contained within the same callstack of functions.
    ///
    /// This can only happen if there's a mistake in the `Span` offset/range calculations.
    BufferSlice(Span),

    /// The type of `Buffer` is invalid.
    ///
    /// The `json_tools::Lexer::next` is called in a few places and the `json_tools::Token` it
    /// emits is converted into a local `Token` with only a `Span` based buffer to avoid checking
    /// the buffer type each time it's used.
    ///
    /// The lexer is configured to only use a `Span` based buffer so the only way this Error can
    /// occur is if the code is changed so that the lexer uses a `String` based buffer.
    BufferType,

    /// The `json_tools::Span` uses `u64` for the `start` and `end` indices which would involve
    /// conversion to `usize` each time they are used. To avoid this the `json_tools::Span` is
    /// converted to the locally defined `Span` that uses `usize` based fields.
    ///
    /// This conversion can fail if the binary is built for architectures other than `64` bit pointer width.
    FromInt(TryFromIntError),

    /// A String was parsed without surrounding double quotes.
    ///
    /// This is only possible if the `json_tools` crate changes the implementation details of
    /// how they parse JSON strings.
    StringWithoutQuotes,

    /// A `RawStr` was made using a token that is not a `String`.
    ///
    /// `RawStr`s are only creatable from inside the crate so the only way this can occur is
    /// through a programming error.
    RawStringFromInvalidToken,
}

impl InternalError {
    #[track_caller]
    fn into_partial_error(self, token: Option<Token>) -> PartialError {
        ErrorKind::Internal(Box::new(self)).into_partial_error(token)
    }
}

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

/// The `json_tools::Span` uses `u64` for the `start` and `end` indices which would involve
/// conversion to `usize` each time they are used. To avoid this the `json_tools::Span` is
/// converted to the locally defined `Span` that uses `usize` based fields.
///
/// This conversion can fail if the binary is built for architectures other than `64` bit pointer width.
impl From<TryFromIntError> for InternalError {
    fn from(err: TryFromIntError) -> Self {
        InternalError::FromInt(err)
    }
}

impl From<InternalError> for Error {
    #[track_caller]
    fn from(err: InternalError) -> Self {
        ErrorImpl {
            kind: ErrorKind::Internal(Box::new(err)),
            loc: std::panic::Location::caller(),
            path: Path::root(),
            span: Span { start: 0, end: 0 },
            token: None,
        }
        .into()
    }
}

impl fmt::Display for InternalError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            InternalError::BufferSlice(span) => {
                write!(f, "Slice into buffer failed; span: {span:?}")
            }
            InternalError::BufferType => write!(f, "The tokens buffer is not a `Span`"),
            InternalError::FromInt(err) => write!(f, "{err}"),
            InternalError::StringWithoutQuotes => {
                write!(f, "A String was parsed without surrounding double quotes.")
            }

            InternalError::RawStringFromInvalidToken => {
                write!(
                    f,
                    "A `RawString` was created using a `Token` that's not a `String`"
                )
            }
        }
    }
}

trait InternalErrorIntoPartial<T> {
    #[track_caller]
    fn into_partial_error<F>(self, f: F) -> Result<T, PartialError>
    where
        F: FnOnce() -> Token;
}

impl<T> InternalErrorIntoPartial<T> for Result<T, InternalError> {
    fn into_partial_error<F>(self, f: F) -> Result<T, PartialError>
    where
        F: FnOnce() -> Token,
    {
        match self {
            Ok(v) => Ok(v),
            Err(err) => {
                let token = f();
                Err(err.into_partial_error(Some(token)))
            }
        }
    }
}

/// Create the `Span` of an `Element` given the start and the closing token.
fn element_span(token_end: &Token, start: usize) -> Span {
    Span {
        start,
        end: token_end.span.end,
    }
}

/// Return the content of the `Token` as a `&str`.
///
/// This in only useful for `Token`'s that contain variable data, such as `String`, `Number` etc.
#[track_caller]
fn token_str<'buf>(json: &'buf str, token: &Token) -> Result<&'buf str, PartialError> {
    let start = token.span.start;
    let end = token.span.end;
    let s = &json
        .get(start..end)
        .ok_or(InternalError::BufferSlice(Span { start, end }))
        .into_partial_error(|| *token)?;
    Ok(s)
}

/// A `&str` with surrounding quotes removed and it hasn't been analyzed for escapes codes.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Default)]
pub struct RawStr<'buf> {
    /// An unescaped `&str` with surrounding quotes removed.
    source: &'buf str,

    /// The `String` token that produced the source `&str`.
    span: Span,
}

/// Impl `Borrow` so `RawStr` plays well with hashed collections.
impl Borrow<str> for RawStr<'_> {
    fn borrow(&self) -> &str {
        self.source
    }
}

/// Impl `Borrow` so `RawStr` plays well with hashed collections.
impl Borrow<str> for &RawStr<'_> {
    fn borrow(&self) -> &str {
        self.source
    }
}

impl<'buf> RawStr<'buf> {
    pub(super) fn from_str(source: &'buf str, span: Span) -> Self {
        Self { source, span }
    }

    /// Create new `RawStr` from a string with surrounding quotes.
    #[track_caller]
    pub(super) fn from_quoted_str(
        s: &'buf str,
        token: Token,
    ) -> Result<RawStr<'buf>, PartialError> {
        const QUOTE: char = '"';

        if token.kind != TokenType::String {
            return Err(InternalError::RawStringFromInvalidToken.into_partial_error(Some(token)));
        }

        // remove double quotes
        let (_, s) = s
            .split_once(QUOTE)
            .ok_or(InternalError::StringWithoutQuotes)
            .into_partial_error(|| token)?;

        let (source, _) = s
            .rsplit_once(QUOTE)
            .ok_or(InternalError::StringWithoutQuotes)
            .into_partial_error(|| token)?;

        Ok(Self {
            source,
            span: token.span,
        })
    }

    /// Return the raw unescaped `&str`.
    pub(crate) fn as_raw(&self) -> &'buf str {
        self.source
    }

    /// Return the `&str` with all escapes decoded.
    pub(crate) fn decode_escapes(
        &self,
        elem: &Element<'buf>,
    ) -> Caveat<Cow<'_, str>, decode::Warning> {
        unescape_str(self.source, elem)
    }

    /// Return a `&str` marked as either having escapes or not.
    pub(crate) fn has_escapes(
        &self,
        elem: &Element<'buf>,
    ) -> Caveat<decode::PendingStr<'buf>, decode::Warning> {
        decode::analyze(self.source, elem)
    }

    /// Return the [`Span`] of the [`Token`] that generated this string.
    pub fn span(&self) -> Span {
        self.span
    }
}

impl fmt::Display for RawStr<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self.source, f)
    }
}

#[track_caller]
fn token_str_as_string(json: &str, token: Token) -> Result<RawStr<'_>, PartialError> {
    let s = token_str(json, &token)?;
    let raw = RawStr::from_quoted_str(s, token)?;
    Ok(raw)
}