saphyr_parser/

parser.rs

//! Home to the YAML Parser.
//!
//! The parser takes input from the [`crate::scanner::Scanner`], performs final checks for YAML
//! compliance, and emits a stream of YAML events. This stream can for instance be used to create
//! YAML objects.

use crate::{
    BufferedInput, Marker,
    input::{Input, str::StrInput},
    scanner::{ScalarStyle, ScanError, Scanner, Span, Token, TokenType},
};

use alloc::{
    borrow::Cow,
    collections::BTreeMap,
    string::{String, ToString},
    vec::Vec,
};
use core::fmt::Display;

#[derive(Clone, Copy, PartialEq, Debug, Eq)]
enum State {
    StreamStart,
    ImplicitDocumentStart,
    DocumentStart,
    DocumentContent,
    DocumentEnd,
    BlockNode,
    BlockSequenceFirstEntry,
    BlockSequenceEntry,
    IndentlessSequenceEntry,
    BlockMappingFirstKey,
    BlockMappingKey,
    BlockMappingValue,
    FlowSequenceFirstEntry,
    FlowSequenceEntry,
    FlowSequenceEntryMappingKey,
    FlowSequenceEntryMappingValue,
    FlowSequenceEntryMappingEnd(Marker),
    FlowMappingFirstKey,
    FlowMappingKey,
    FlowMappingValue,
    FlowMappingEmptyValue,
    End,
}

/// An event generated by the YAML parser.
///
/// Events are used in the low-level event-based API (push parser). The API entrypoint is the
/// [`EventReceiver`] trait.
#[derive(Clone, PartialEq, Debug, Eq)]
pub enum Event<'input> {
    /// Reserved for internal use.
    Nothing,
    /// Event generated at the very beginning of parsing.
    StreamStart,
    /// Last event that will be generated by the parser. Signals EOF.
    StreamEnd,
    /// The start of a YAML document.
    ///
    /// When the boolean is `true`, it is an explicit document start
    /// directive (`---`).
    ///
    /// When the boolean is `false`, it is an implicit document start
    /// (without `---`).
    DocumentStart(bool),
    /// The YAML end document directive (`...`).
    DocumentEnd,
    /// A YAML Alias.
    Alias(
        /// The anchor ID the alias refers to.
        usize,
    ),
    /// Value, style, `anchor_id`, tag
    Scalar(
        Cow<'input, str>,
        ScalarStyle,
        usize,
        Option<Cow<'input, Tag>>,
    ),
    /// The start of a YAML sequence (array).
    SequenceStart(
        /// The anchor ID of the start of the sequence.
        usize,
        /// An optional tag
        Option<Cow<'input, Tag>>,
    ),
    /// The end of a YAML sequence (array).
    SequenceEnd,
    /// The start of a YAML mapping (object, hash).
    MappingStart(
        /// The anchor ID of the start of the mapping.
        usize,
        /// An optional tag
        Option<Cow<'input, Tag>>,
    ),
    /// The end of a YAML mapping (object, hash).
    MappingEnd,
}

/// A YAML tag.
#[derive(Clone, PartialEq, Debug, Eq, Ord, PartialOrd, Hash)]
pub struct Tag {
    /// Handle of the tag (`!` included).
    pub handle: String,
    /// The suffix of the tag.
    pub suffix: String,
}

impl Tag {
    /// Returns whether the tag is a YAML tag from the core schema (`!!str`, `!!int`, ...).
    ///
    /// The YAML specification specifies [a list of
    /// tags](https://yaml.org/spec/1.2.2/#103-core-schema) for the Core Schema. This function
    /// checks whether _the handle_ (but not the suffix) is the handle for the YAML Core Schema.
    ///
    /// # Return
    /// Returns `true` if the handle is `tag:yaml.org,2002`, `false` otherwise.
    #[must_use]
    pub fn is_yaml_core_schema(&self) -> bool {
        self.handle == "tag:yaml.org,2002:"
    }
}

impl Display for Tag {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        if self.handle == "!" {
            write!(f, "!{}", self.suffix)
        } else {
            write!(f, "{}!{}", self.handle, self.suffix)
        }
    }
}

impl<'input> Event<'input> {
    /// Create an empty scalar.
    fn empty_scalar() -> Self {
        Event::Scalar(Cow::default(), ScalarStyle::Plain, 0, None)
    }

    /// Create an empty scalar with the given anchor.
    fn empty_scalar_with_anchor(anchor: usize, tag: Option<Cow<'input, Tag>>) -> Self {
        Event::Scalar(Cow::default(), ScalarStyle::Plain, anchor, tag)
    }
}

/// A YAML parser.
#[derive(Debug)]
pub struct Parser<'input, T: Input> {
    /// The underlying scanner from which we pull tokens.
    scanner: Scanner<'input, T>,
    /// The stack of _previous_ states we were in.
    ///
    /// States are pushed in the context of subobjects to this stack. The top-most element is the
    /// state in which to come back to when exiting the current state.
    states: Vec<State>,
    /// The state in which we currently are.
    state: State,
    /// The next token from the scanner.
    token: Option<Token<'input>>,
    /// The next YAML event to emit.
    current: Option<(Event<'input>, Span)>,
    /// Anchors that have been encountered in the YAML document.
    anchors: BTreeMap<Cow<'input, str>, usize>,
    /// Next ID available for an anchor.
    ///
    /// Every anchor is given a unique ID. We use an incrementing ID and this is both the ID to
    /// return for the next anchor and the count of anchor IDs emitted.
    anchor_id_count: usize,
    /// The tag directives (`%TAG`) the parser has encountered.
    ///
    /// Key is the handle, and value is the prefix.
    tags: BTreeMap<String, String>,
    /// Whether we have emitted [`Event::StreamEnd`].
    ///
    /// Emitted means that it has been returned from [`Self::next`]. If it is stored in
    /// [`Self::token`], this is set to `false`.
    stream_end_emitted: bool,
    /// Make tags global across all documents.
    keep_tags: bool,
}

impl<T: Input + Clone> Clone for Parser<'_, T> {
    fn clone(&self) -> Self {
        Self {
            scanner: self.scanner.clone(),
            states: self.states.clone(),
            state: self.state,
            token: self.token.clone(),
            current: self.current.clone(),
            anchors: self.anchors.clone(),
            anchor_id_count: self.anchor_id_count,
            tags: self.tags.clone(),
            stream_end_emitted: self.stream_end_emitted,
            keep_tags: self.keep_tags,
        }
    }
}

/// Trait to be implemented in order to use the low-level parsing API.
///
/// The low-level parsing API is event-based (a push parser), calling [`EventReceiver::on_event`]
/// for each YAML [`Event`] that occurs.
/// The [`EventReceiver`] trait only receives events. In order to receive both events and their
/// location in the source, use [`SpannedEventReceiver`]. Note that [`EventReceiver`]s implement
/// [`SpannedEventReceiver`] automatically.
///
/// # Event hierarchy
/// The event stream starts with an [`Event::StreamStart`] event followed by an
/// [`Event::DocumentStart`] event. If the YAML document starts with a mapping (an object), an
/// [`Event::MappingStart`] event is emitted. If it starts with a sequence (an array), an
/// [`Event::SequenceStart`] event is emitted. Otherwise, an [`Event::Scalar`] event is emitted.
///
/// In a mapping, key-values are sent as consecutive events. The first event after an
/// [`Event::MappingStart`] will be the key, and following its value. If the mapping contains no
/// sub-mapping or sub-sequence, then even events (starting from 0) will always be keys and odd
/// ones will always be values. The mapping ends when an [`Event::MappingEnd`] event is received.
///
/// In a sequence, values are sent consecutively until the [`Event::SequenceEnd`] event.
///
/// If a value is a sub-mapping or a sub-sequence, an [`Event::MappingStart`] or
/// [`Event::SequenceStart`] event will be sent respectively. Following events until the associated
/// [`Event::MappingStart`] or [`Event::SequenceEnd`] (beware of nested mappings or sequences) will
/// be part of the value and not another key-value pair or element in the sequence.
///
/// For instance, the following yaml:
/// ```yaml
/// a: b
/// c:
///   d: e
/// f:
///   - g
///   - h
/// ```
/// will emit (indented and commented for lisibility):
/// ```text
/// StreamStart, DocumentStart, MappingStart,
///   Scalar("a", ..), Scalar("b", ..)
///   Scalar("c", ..), MappingStart, Scalar("d", ..), Scalar("e", ..), MappingEnd,
///   Scalar("f", ..), SequenceStart, Scalar("g", ..), Scalar("h", ..), SequenceEnd,
/// MappingEnd, DocumentEnd, StreamEnd
/// ```
///
/// # Example
/// ```
/// # use saphyr_parser::{Event, EventReceiver, Parser};
/// #
/// /// Sink of events. Collects them into an array.
/// struct EventSink<'input> {
///     events: Vec<Event<'input>>,
/// }
///
/// /// Implement `on_event`, pushing into `self.events`.
/// impl<'input> EventReceiver<'input> for EventSink<'input> {
///     fn on_event(&mut self, ev: Event<'input>) {
///         self.events.push(ev);
///     }
/// }
///
/// /// Load events from a yaml string.
/// fn str_to_events(yaml: &str) -> Vec<Event<'_>> {
///     let mut sink = EventSink { events: Vec::new() };
///     let mut parser = Parser::new_from_str(yaml);
///     // Load events using our sink as the receiver.
///     parser.load(&mut sink, true).unwrap();
///     sink.events
/// }
/// ```
pub trait EventReceiver<'input> {
    /// Handler called for each YAML event that is emitted by the parser.
    fn on_event(&mut self, ev: Event<'input>);
}

/// Trait to be implemented for using the low-level parsing API.
///
/// Functionally similar to [`EventReceiver`], but receives a [`Span`] as well as the event.
pub trait SpannedEventReceiver<'input> {
    /// Handler called for each event that occurs.
    fn on_event(&mut self, ev: Event<'input>, span: Span);
}

impl<'input, R: EventReceiver<'input>> SpannedEventReceiver<'input> for R {
    fn on_event(&mut self, ev: Event<'input>, _span: Span) {
        self.on_event(ev);
    }
}

/// A convenience alias for a `Result` of a parser event.
pub type ParseResult<'input> = Result<(Event<'input>, Span), ScanError>;

impl<'input> Parser<'input, StrInput<'input>> {
    /// Create a new instance of a parser from a &str.
    #[must_use]
    pub fn new_from_str(value: &'input str) -> Self {
        debug_print!("\x1B[;31m>>>>>>>>>> New parser from str\x1B[;0m");
        Parser::new(StrInput::new(value))
    }
}

impl<'input, T> Parser<'input, BufferedInput<T>>
where
    T: Iterator<Item = char> + 'input,
{
    /// Create a new instance of a parser from an iterator of `char`s.
    #[must_use]
    pub fn new_from_iter(iter: T) -> Self {
        debug_print!("\x1B[;31m>>>>>>>>>> New parser from iter\x1B[;0m");
        Parser::new(BufferedInput::new(iter))
    }
}

impl<'input, T: Input> Parser<'input, T> {
    /// Create a new instance of a parser from the given input of characters.
    pub fn new(src: T) -> Self {
        Parser {
            scanner: Scanner::new(src),
            states: Vec::new(),
            state: State::StreamStart,
            token: None,
            current: None,

            anchors: BTreeMap::new(),
            // valid anchor_id starts from 1
            anchor_id_count: 1,
            tags: BTreeMap::new(),
            stream_end_emitted: false,
            keep_tags: false,
        }
    }

    /// Whether to keep tags across multiple documents when parsing.
    ///
    /// This behavior is non-standard as per the YAML specification but can be encountered in the
    /// wild. This boolean allows enabling this non-standard extension. This would result in the
    /// parser accepting input from [test
    /// QLJ7](https://github.com/yaml/yaml-test-suite/blob/ccfa74e56afb53da960847ff6e6976c0a0825709/src/QLJ7.yaml)
    /// of the yaml-test-suite:
    ///
    /// ```yaml
    /// %TAG !prefix! tag:example.com,2011:
    /// --- !prefix!A
    /// a: b
    /// --- !prefix!B
    /// c: d
    /// --- !prefix!C
    /// e: f
    /// ```
    ///
    /// With `keep_tags` set to `false`, the above YAML is rejected. As per the specification, tags
    /// only apply to the document immediately following them. This would error on `!prefix!B`.
    ///
    /// With `keep_tags` set to `true`, the above YAML is accepted by the parser.
    #[must_use]
    pub fn keep_tags(mut self, value: bool) -> Self {
        self.keep_tags = value;
        self
    }

    /// Try to load the next event and return it, but do not consuming it from `self`.
    ///
    /// Any subsequent call to [`Parser::peek`] will return the same value, until a call to
    /// [`Iterator::next`] or [`Parser::load`].
    ///
    /// # Errors
    /// Returns `ScanError` when loading the next event fails.
    pub fn peek(&mut self) -> Option<Result<&(Event<'input>, Span), ScanError>> {
        if let Some(ref x) = self.current {
            Some(Ok(x))
        } else {
            if self.stream_end_emitted {
                return None;
            }
            match self.next_event_impl() {
                Ok(token) => self.current = Some(token),
                Err(e) => return Some(Err(e)),
            }
            self.current.as_ref().map(Ok)
        }
    }

    /// Try to load the next event and return it, consuming it from `self`.
    ///
    /// # Errors
    /// Returns `ScanError` when loading the next event fails.
    pub fn next_event(&mut self) -> Option<ParseResult<'input>> {
        if self.stream_end_emitted {
            return None;
        }

        let tok = self.next_event_impl();
        if matches!(tok, Ok((Event::StreamEnd, _))) {
            self.stream_end_emitted = true;
        }
        Some(tok)
    }

    /// Implementation function for [`Self::next_event`] without the `Option`.
    ///
    /// [`Self::next_event`] should conform to the expectations of an [`Iterator`] and return an
    /// option. This burdens the parser code. This function is used internally when an option is
    /// undesirable.
    fn next_event_impl<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match self.current.take() {
            None => self.parse(),
            Some(v) => Ok(v),
        }
    }

    /// Peek at the next token from the scanner.
    fn peek_token(&mut self) -> Result<&Token<'_>, ScanError> {
        match self.token {
            None => {
                self.token = Some(self.scan_next_token()?);
                Ok(self.token.as_ref().unwrap())
            }
            Some(ref tok) => Ok(tok),
        }
    }

    /// Extract and return the next token from the scanner.
    ///
    /// This function does _not_ make use of `self.token`.
    fn scan_next_token(&mut self) -> Result<Token<'input>, ScanError> {
        let token = self.scanner.next();
        match token {
            None => match self.scanner.get_error() {
                None => Err(ScanError::new_str(self.scanner.mark(), "unexpected eof")),
                Some(e) => Err(e),
            },
            Some(tok) => Ok(tok),
        }
    }

    fn fetch_token<'a>(&mut self) -> Token<'a>
    where
        'input: 'a,
    {
        self.token
            .take()
            .expect("fetch_token needs to be preceded by peek_token")
    }

    /// Skip the next token from the scanner.
    fn skip(&mut self) {
        self.token = None;
    }
    /// Pops the top-most state and make it the current state.
    fn pop_state(&mut self) {
        self.state = self.states.pop().unwrap();
    }
    /// Push a new state atop the state stack.
    fn push_state(&mut self, state: State) {
        self.states.push(state);
    }

    fn parse<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        if self.state == State::End {
            return Ok((Event::StreamEnd, Span::empty(self.scanner.mark())));
        }
        let (ev, mark) = self.state_machine()?;
        Ok((ev, mark))
    }

    /// Load the YAML from the stream in `self`, pushing events into `recv`.
    ///
    /// The contents of the stream are parsed and the corresponding events are sent into the
    /// recveiver. For detailed explanations about how events work, see [`EventReceiver`].
    ///
    /// If `multi` is set to `true`, the parser will allow parsing of multiple YAML documents
    /// inside the stream.
    ///
    /// Note that any [`EventReceiver`] is also a [`SpannedEventReceiver`], so implementing the
    /// former is enough to call this function.
    /// # Errors
    /// Returns `ScanError` when loading fails.
    pub fn load<R: SpannedEventReceiver<'input>>(
        &mut self,
        recv: &mut R,
        multi: bool,
    ) -> Result<(), ScanError> {
        if !self.scanner.stream_started() {
            let (ev, span) = self.next_event_impl()?;
            if ev != Event::StreamStart {
                return Err(ScanError::new_str(
                    span.start,
                    "did not find expected <stream-start>",
                ));
            }
            recv.on_event(ev, span);
        }

        if self.scanner.stream_ended() {
            // XXX has parsed?
            recv.on_event(Event::StreamEnd, Span::empty(self.scanner.mark()));
            return Ok(());
        }
        loop {
            let (ev, span) = self.next_event_impl()?;
            if ev == Event::StreamEnd {
                recv.on_event(ev, span);
                return Ok(());
            }
            // clear anchors before a new document
            self.anchors.clear();
            self.load_document(ev, span, recv)?;
            if !multi {
                break;
            }
        }
        Ok(())
    }

    fn load_document<R: SpannedEventReceiver<'input>>(
        &mut self,
        first_ev: Event<'input>,
        span: Span,
        recv: &mut R,
    ) -> Result<(), ScanError> {
        if !matches!(first_ev, Event::DocumentStart(_)) {
            return Err(ScanError::new_str(
                span.start,
                "did not find expected <document-start>",
            ));
        }
        recv.on_event(first_ev, span);

        let (ev, span) = self.next_event_impl()?;
        self.load_node(ev, span, recv)?;

        // DOCUMENT-END is expected.
        let (ev, mark) = self.next_event_impl()?;
        assert_eq!(ev, Event::DocumentEnd);
        recv.on_event(ev, mark);

        Ok(())
    }

    fn load_node<R: SpannedEventReceiver<'input>>(
        &mut self,
        first_ev: Event<'input>,
        span: Span,
        recv: &mut R,
    ) -> Result<(), ScanError> {
        match first_ev {
            Event::Alias(..) | Event::Scalar(..) => {
                recv.on_event(first_ev, span);
                Ok(())
            }
            Event::SequenceStart(..) => {
                recv.on_event(first_ev, span);
                self.load_sequence(recv)
            }
            Event::MappingStart(..) => {
                recv.on_event(first_ev, span);
                self.load_mapping(recv)
            }
            _ => {
                #[cfg(feature = "debug_prints")]
                std::println!("UNREACHABLE EVENT: {first_ev:?}");
                unreachable!();
            }
        }
    }

    fn load_mapping<R: SpannedEventReceiver<'input>>(
        &mut self,
        recv: &mut R,
    ) -> Result<(), ScanError> {
        let (mut key_ev, mut key_mark) = self.next_event_impl()?;
        while key_ev != Event::MappingEnd {
            // key
            self.load_node(key_ev, key_mark, recv)?;

            // value
            let (ev, mark) = self.next_event_impl()?;
            self.load_node(ev, mark, recv)?;

            // next event
            let (ev, mark) = self.next_event_impl()?;
            key_ev = ev;
            key_mark = mark;
        }
        recv.on_event(key_ev, key_mark);
        Ok(())
    }

    fn load_sequence<R: SpannedEventReceiver<'input>>(
        &mut self,
        recv: &mut R,
    ) -> Result<(), ScanError> {
        let (mut ev, mut mark) = self.next_event_impl()?;
        while ev != Event::SequenceEnd {
            self.load_node(ev, mark, recv)?;

            // next event
            let (next_ev, next_mark) = self.next_event_impl()?;
            ev = next_ev;
            mark = next_mark;
        }
        recv.on_event(ev, mark);
        Ok(())
    }

    fn state_machine<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        // let next_tok = self.peek_token().cloned()?;
        // println!("cur_state {:?}, next tok: {:?}", self.state, next_tok);
        debug_print!("\n\x1B[;33mParser state: {:?} \x1B[;0m", self.state);

        match self.state {
            State::StreamStart => self.stream_start(),

            State::ImplicitDocumentStart => self.document_start(true),
            State::DocumentStart => self.document_start(false),
            State::DocumentContent => self.document_content(),
            State::DocumentEnd => self.document_end(),

            State::BlockNode => self.parse_node(true, false),
            // State::BlockNodeOrIndentlessSequence => self.parse_node(true, true),
            // State::FlowNode => self.parse_node(false, false),
            State::BlockMappingFirstKey => self.block_mapping_key(true),
            State::BlockMappingKey => self.block_mapping_key(false),
            State::BlockMappingValue => self.block_mapping_value(),

            State::BlockSequenceFirstEntry => self.block_sequence_entry(true),
            State::BlockSequenceEntry => self.block_sequence_entry(false),

            State::FlowSequenceFirstEntry => self.flow_sequence_entry(true),
            State::FlowSequenceEntry => self.flow_sequence_entry(false),

            State::FlowMappingFirstKey => self.flow_mapping_key(true),
            State::FlowMappingKey => self.flow_mapping_key(false),
            State::FlowMappingValue => self.flow_mapping_value(false),

            State::IndentlessSequenceEntry => self.indentless_sequence_entry(),

            State::FlowSequenceEntryMappingKey => self.flow_sequence_entry_mapping_key(),
            State::FlowSequenceEntryMappingValue => self.flow_sequence_entry_mapping_value(),
            State::FlowSequenceEntryMappingEnd(mark) => self.flow_sequence_entry_mapping_end(mark),
            State::FlowMappingEmptyValue => self.flow_mapping_value(true),

            /* impossible */
            State::End => unreachable!(),
        }
    }

    fn stream_start<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match *self.peek_token()? {
            Token(span, TokenType::StreamStart(_)) => {
                self.state = State::ImplicitDocumentStart;
                self.skip();
                Ok((Event::StreamStart, span))
            }
            Token(span, _) => Err(ScanError::new_str(
                span.start,
                "did not find expected <stream-start>",
            )),
        }
    }

    fn document_start<'a>(&mut self, implicit: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        while let TokenType::DocumentEnd | TokenType::ByteOrderMark = self.peek_token()?.1 {
            self.skip();
        }

        match *self.peek_token()? {
            Token(span, TokenType::StreamEnd) => {
                self.state = State::End;
                self.skip();
                Ok((Event::StreamEnd, span))
            }
            Token(
                _,
                TokenType::VersionDirective(..)
                | TokenType::TagDirective(..)
                | TokenType::ReservedDirective(..)
                | TokenType::DocumentStart,
            ) => {
                // explicit document
                self.explicit_document_start()
            }
            Token(span, _) if implicit => {
                self.parser_process_directives()?;
                self.push_state(State::DocumentEnd);
                self.state = State::BlockNode;
                Ok((Event::DocumentStart(false), span))
            }
            _ => {
                // explicit document
                self.explicit_document_start()
            }
        }
    }

    fn parser_process_directives(&mut self) -> Result<(), ScanError> {
        let mut version_directive_received = false;
        let mut tags = BTreeMap::new();
        loop {
            match self.peek_token()? {
                Token(span, TokenType::VersionDirective(_, _)) => {
                    // XXX parsing with warning according to spec
                    //if major != 1 || minor > 2 {
                    //    return Err(ScanError::new_str(tok.0,
                    //        "found incompatible YAML document"));
                    //}
                    if version_directive_received {
                        return Err(ScanError::new_str(
                            span.start,
                            "duplicate version directive",
                        ));
                    }
                    version_directive_received = true;
                }
                Token(mark, TokenType::TagDirective(handle, prefix)) => {
                    if tags.contains_key(&**handle) {
                        return Err(ScanError::new_str(
                            mark.start,
                            "the TAG directive must only be given at most once per handle in the same document",
                        ));
                    }
                    tags.insert(handle.to_string(), prefix.to_string());
                }
                Token(_, TokenType::ReservedDirective(_, _)) => {
                    // Reserved directives are ignored
                }
                _ => break,
            }
            self.skip();
        }
        self.tags.extend(tags);
        Ok(())
    }

    fn explicit_document_start<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        self.parser_process_directives()?;
        match *self.peek_token()? {
            Token(mark, TokenType::DocumentStart) => {
                self.push_state(State::DocumentEnd);
                self.state = State::DocumentContent;
                self.skip();
                Ok((Event::DocumentStart(true), mark))
            }
            Token(span, TokenType::ByteOrderMark) => Err(ScanError::new_str(
                span.start,
                "a byte order mark must not appear inside a document",
            )),
            Token(span, _) => Err(ScanError::new_str(
                span.start,
                "did not find expected <document start>",
            )),
        }
    }

    fn document_content<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match *self.peek_token()? {
            Token(
                mark,
                TokenType::VersionDirective(..)
                | TokenType::TagDirective(..)
                | TokenType::ReservedDirective(..)
                | TokenType::DocumentStart
                | TokenType::DocumentEnd
                | TokenType::ByteOrderMark
                | TokenType::StreamEnd,
            ) => {
                self.pop_state();
                // empty scalar
                Ok((Event::empty_scalar(), mark))
            }
            _ => self.parse_node(true, false),
        }
    }

    fn document_end<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        // A byte order mark ends the document, and only more byte order marks, comments, or
        // document markers may follow it (see 9.2. Streams). Anything else is rejected when the
        // next document starts anyway, but checking here points the error at the byte order mark.
        if let Token(span, TokenType::ByteOrderMark) = *self.peek_token()? {
            while let TokenType::ByteOrderMark = self.peek_token()?.1 {
                self.skip();
            }

            match self.peek_token()?.1 {
                TokenType::DocumentStart | TokenType::DocumentEnd | TokenType::StreamEnd => {}
                _ => {
                    return Err(ScanError::new_str(
                        span.start,
                        "a byte order mark must not appear inside a document",
                    ));
                }
            }
        }

        let mut explicit_end = false;
        let span: Span = match *self.peek_token()? {
            Token(span, TokenType::DocumentEnd) => {
                explicit_end = true;
                self.skip();
                span
            }
            Token(span, _) => span,
        };

        if !self.keep_tags {
            self.tags.clear();
        }
        if explicit_end {
            self.state = State::ImplicitDocumentStart;
        } else {
            if let Token(
                span,
                TokenType::VersionDirective(..)
                | TokenType::TagDirective(..)
                | TokenType::ReservedDirective(..),
            ) = *self.peek_token()?
            {
                return Err(ScanError::new_str(
                    span.start,
                    "missing explicit document end marker before directive",
                ));
            }
            self.state = State::DocumentStart;
        }

        Ok((Event::DocumentEnd, span))
    }

    fn register_anchor(&mut self, name: Cow<'input, str>, _: &Span) -> usize {
        // anchors can be overridden/reused
        // if self.anchors.contains_key(name) {
        //     return Err(ScanError::new_str(*mark,
        //         "while parsing anchor, found duplicated anchor"));
        // }
        let new_id = self.anchor_id_count;
        self.anchor_id_count += 1;
        self.anchors.insert(name, new_id);
        new_id
    }

    fn parse_node<'a>(&mut self, block: bool, indentless_sequence: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        let mut anchor_id = 0;
        let mut tag = None;
        let start_mark = self.peek_token()?.0.start;
        let mut end_mark = start_mark;
        match *self.peek_token()? {
            Token(_, TokenType::Alias(_)) => {
                self.pop_state();
                if let Token(span, TokenType::Alias(name)) = self.fetch_token() {
                    match self.anchors.get(&*name) {
                        None => {
                            return Err(ScanError::new_str(
                                span.start,
                                "while parsing node, found unknown anchor",
                            ));
                        }
                        Some(id) => return Ok((Event::Alias(*id), span)),
                    }
                }
                unreachable!()
            }
            Token(_, TokenType::Anchor(_)) => {
                if let Token(span, TokenType::Anchor(name)) = self.fetch_token() {
                    anchor_id = self.register_anchor(name, &span);
                    end_mark = span.end;
                    if let TokenType::Tag(..) = self.peek_token()?.1 {
                        if let Token(mark, TokenType::Tag(handle, suffix)) = self.fetch_token() {
                            tag = Some(self.resolve_tag(span, &handle, suffix)?);
                            end_mark = mark.end;
                        } else {
                            unreachable!()
                        }
                    }
                } else {
                    unreachable!()
                }
            }
            Token(mark, TokenType::Tag(..)) => {
                if let TokenType::Tag(handle, suffix) = self.fetch_token().1 {
                    tag = Some(self.resolve_tag(mark, &handle, suffix)?);
                    end_mark = mark.end;
                    if let TokenType::Anchor(_) = &self.peek_token()?.1 {
                        if let Token(mark, TokenType::Anchor(name)) = self.fetch_token() {
                            anchor_id = self.register_anchor(name, &mark);
                            end_mark = mark.end;
                        } else {
                            unreachable!()
                        }
                    }
                } else {
                    unreachable!()
                }
            }
            _ => {}
        }
        let (event, end_mark) = match *self.peek_token()? {
            Token(mark, TokenType::BlockEntry) if indentless_sequence => {
                self.state = State::IndentlessSequenceEntry;
                (Event::SequenceStart(anchor_id, tag), mark.end)
            }
            Token(_, TokenType::Scalar(..)) => {
                self.pop_state();
                if let Token(mark, TokenType::Scalar(style, v)) = self.fetch_token() {
                    (Event::Scalar(v, style, anchor_id, tag), mark.end)
                } else {
                    unreachable!()
                }
            }
            Token(mark, TokenType::FlowSequenceStart) => {
                self.state = State::FlowSequenceFirstEntry;
                (Event::SequenceStart(anchor_id, tag), mark.end)
            }
            Token(mark, TokenType::FlowMappingStart) => {
                self.state = State::FlowMappingFirstKey;
                (Event::MappingStart(anchor_id, tag), mark.end)
            }
            Token(mark, TokenType::BlockSequenceStart) if block => {
                self.state = State::BlockSequenceFirstEntry;
                (Event::SequenceStart(anchor_id, tag), mark.end)
            }
            Token(mark, TokenType::BlockMappingStart) if block => {
                self.state = State::BlockMappingFirstKey;
                (Event::MappingStart(anchor_id, tag), mark.end)
            }
            // ex 7.2, an empty scalar can follow a secondary tag
            Token(..) if tag.is_some() || anchor_id > 0 => {
                self.pop_state();
                (Event::empty_scalar_with_anchor(anchor_id, tag), end_mark)
            }
            Token(span, _) => {
                return Err(ScanError::new_str(
                    span.start,
                    "while parsing a node, did not find expected node content",
                ));
            }
        };
        Ok((event, Span::new(start_mark, end_mark)))
    }

    fn block_mapping_key<'a>(&mut self, first: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        // skip BlockMappingStart
        if first {
            let _ = self.peek_token()?;
            //self.marks.push(tok.0);
            self.skip();
        }
        match *self.peek_token()? {
            Token(_, TokenType::Key) => {
                self.skip();
                if let Token(mark, TokenType::Key | TokenType::Value | TokenType::BlockEnd) =
                    *self.peek_token()?
                {
                    self.state = State::BlockMappingValue;
                    // empty scalar
                    Ok((Event::empty_scalar(), mark))
                } else {
                    self.push_state(State::BlockMappingValue);
                    self.parse_node(true, true)
                }
            }
            // XXX(chenyh): libyaml failed to parse spec 1.2, ex8.18
            Token(mark, TokenType::Value) => {
                self.state = State::BlockMappingValue;
                Ok((Event::empty_scalar(), mark))
            }
            Token(mark, TokenType::BlockEnd) => {
                self.pop_state();
                self.skip();
                Ok((Event::MappingEnd, mark))
            }
            Token(span, _) => Err(ScanError::new_str(
                span.start,
                "while parsing a block mapping, did not find expected key",
            )),
        }
    }

    fn block_mapping_value<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match *self.peek_token()? {
            Token(mark, TokenType::Value) => {
                self.skip();
                if let Token(_, TokenType::Key | TokenType::Value | TokenType::BlockEnd) =
                    *self.peek_token()?
                {
                    self.state = State::BlockMappingKey;
                    // empty scalar
                    Ok((Event::empty_scalar(), mark))
                } else {
                    self.push_state(State::BlockMappingKey);
                    self.parse_node(true, true)
                }
            }
            Token(mark, _) => {
                self.state = State::BlockMappingKey;
                // empty scalar
                Ok((Event::empty_scalar(), mark))
            }
        }
    }

    fn flow_mapping_key<'a>(&mut self, first: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        if first {
            let _ = self.peek_token()?;
            self.skip();
        }
        let span: Span = {
            match *self.peek_token()? {
                Token(mark, TokenType::FlowMappingEnd) => mark,
                Token(mark, _) => {
                    if !first {
                        match *self.peek_token()? {
                            Token(_, TokenType::FlowEntry) => self.skip(),
                            Token(span, _) => {
                                return Err(ScanError::new_str(
                                    span.start,
                                    "while parsing a flow mapping, did not find expected ',' or '}'",
                                ));
                            }
                        }
                    }

                    match *self.peek_token()? {
                        Token(_, TokenType::Key) => {
                            self.skip();
                            if let Token(
                                mark,
                                TokenType::Value | TokenType::FlowEntry | TokenType::FlowMappingEnd,
                            ) = *self.peek_token()?
                            {
                                self.state = State::FlowMappingValue;
                                return Ok((Event::empty_scalar(), mark));
                            }
                            self.push_state(State::FlowMappingValue);
                            return self.parse_node(false, false);
                        }
                        Token(marker, TokenType::Value) => {
                            self.state = State::FlowMappingValue;
                            return Ok((Event::empty_scalar(), marker));
                        }
                        Token(_, TokenType::FlowMappingEnd) => (),
                        _ => {
                            self.push_state(State::FlowMappingEmptyValue);
                            return self.parse_node(false, false);
                        }
                    }

                    mark
                }
            }
        };

        self.pop_state();
        self.skip();
        Ok((Event::MappingEnd, span))
    }

    fn flow_mapping_value<'a>(&mut self, empty: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        let span: Span = {
            if empty {
                let Token(mark, _) = *self.peek_token()?;
                self.state = State::FlowMappingKey;
                return Ok((Event::empty_scalar(), mark));
            }
            match *self.peek_token()? {
                Token(span, TokenType::Value) => {
                    self.skip();
                    match self.peek_token()?.1 {
                        TokenType::FlowEntry | TokenType::FlowMappingEnd => {}
                        _ => {
                            self.push_state(State::FlowMappingKey);
                            return self.parse_node(false, false);
                        }
                    }
                    span
                }
                Token(marker, _) => marker,
            }
        };

        self.state = State::FlowMappingKey;
        Ok((Event::empty_scalar(), span))
    }

    fn flow_sequence_entry<'a>(&mut self, first: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        // skip FlowMappingStart
        if first {
            let _ = self.peek_token()?;
            //self.marks.push(tok.0);
            self.skip();
        }
        match *self.peek_token()? {
            Token(mark, TokenType::FlowSequenceEnd) => {
                self.pop_state();
                self.skip();
                return Ok((Event::SequenceEnd, mark));
            }
            Token(_, TokenType::FlowEntry) if !first => {
                self.skip();
            }
            Token(span, _) if !first => {
                return Err(ScanError::new_str(
                    span.start,
                    "while parsing a flow sequence, expected ',' or ']'",
                ));
            }
            _ => { /* next */ }
        }
        match *self.peek_token()? {
            Token(mark, TokenType::FlowSequenceEnd) => {
                self.pop_state();
                self.skip();
                Ok((Event::SequenceEnd, mark))
            }
            Token(mark, TokenType::Key) => {
                self.state = State::FlowSequenceEntryMappingKey;
                self.skip();
                Ok((Event::MappingStart(0, None), mark))
            }
            _ => {
                self.push_state(State::FlowSequenceEntry);
                self.parse_node(false, false)
            }
        }
    }

    fn indentless_sequence_entry<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match *self.peek_token()? {
            Token(mark, TokenType::BlockEntry) => {
                self.skip();
                if let Token(
                    _,
                    TokenType::BlockEntry | TokenType::Key | TokenType::Value | TokenType::BlockEnd,
                ) = *self.peek_token()?
                {
                    self.state = State::IndentlessSequenceEntry;
                    Ok((Event::empty_scalar(), mark))
                } else {
                    self.push_state(State::IndentlessSequenceEntry);
                    self.parse_node(true, false)
                }
            }
            Token(mark, _) => {
                self.pop_state();
                Ok((Event::SequenceEnd, mark))
            }
        }
    }

    fn block_sequence_entry<'a>(&mut self, first: bool) -> ParseResult<'a>
    where
        'input: 'a,
    {
        // BLOCK-SEQUENCE-START
        if first {
            let _ = self.peek_token()?;
            //self.marks.push(tok.0);
            self.skip();
        }
        match *self.peek_token()? {
            Token(mark, TokenType::BlockEnd) => {
                self.pop_state();
                self.skip();
                Ok((Event::SequenceEnd, mark))
            }
            Token(mark, TokenType::BlockEntry) => {
                self.skip();
                if let Token(_, TokenType::BlockEntry | TokenType::BlockEnd) = *self.peek_token()? {
                    self.state = State::BlockSequenceEntry;
                    Ok((Event::empty_scalar(), mark))
                } else {
                    self.push_state(State::BlockSequenceEntry);
                    self.parse_node(true, false)
                }
            }
            Token(span, _) => Err(ScanError::new_str(
                span.start,
                "while parsing a block collection, did not find expected '-' indicator",
            )),
        }
    }

    fn flow_sequence_entry_mapping_key<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        if let Token(mark, TokenType::Value | TokenType::FlowEntry | TokenType::FlowSequenceEnd) =
            *self.peek_token()?
        {
            self.skip();
            self.state = State::FlowSequenceEntryMappingValue;
            Ok((Event::empty_scalar(), mark))
        } else {
            self.push_state(State::FlowSequenceEntryMappingValue);
            self.parse_node(false, false)
        }
    }

    fn flow_sequence_entry_mapping_value<'a>(&mut self) -> ParseResult<'a>
    where
        'input: 'a,
    {
        match *self.peek_token()? {
            Token(_, TokenType::Value) => {
                self.skip();
                self.state = State::FlowSequenceEntryMappingValue;
                let Token(span, ref tok) = *self.peek_token()?;
                if matches!(tok, TokenType::FlowEntry | TokenType::FlowSequenceEnd) {
                    self.state = State::FlowSequenceEntryMappingEnd(span.end);
                    Ok((Event::empty_scalar(), span))
                } else {
                    self.push_state(State::FlowSequenceEntryMappingEnd(span.end));
                    self.parse_node(false, false)
                }
            }
            Token(mark, _) => {
                self.state = State::FlowSequenceEntryMappingEnd(mark.end);
                Ok((Event::empty_scalar(), mark))
            }
        }
    }

    #[allow(clippy::unnecessary_wraps)]
    fn flow_sequence_entry_mapping_end<'a>(&mut self, mark: Marker) -> ParseResult<'a>
    where
        'input: 'a,
    {
        self.state = State::FlowSequenceEntry;
        Ok((Event::MappingEnd, Span::empty(mark)))
    }

    /// Resolve a tag from the handle and the suffix.
    fn resolve_tag(
        &self,
        span: Span,
        handle: &str,
        suffix: String,
    ) -> Result<Cow<'input, Tag>, ScanError> {
        let tag = if handle == "!!" {
            // "!!" is a shorthand for "tag:yaml.org,2002:". However, that default can be
            // overridden.
            Tag {
                handle: self
                    .tags
                    .get("!!")
                    .map_or_else(|| "tag:yaml.org,2002:".to_string(), ToString::to_string),
                suffix,
            }
        } else if handle.is_empty() && suffix == "!" {
            // "!" introduces a local tag. Local tags may have their prefix overridden.
            match self.tags.get("") {
                Some(prefix) => Tag {
                    handle: prefix.clone(),
                    suffix,
                },
                None => Tag {
                    handle: String::new(),
                    suffix,
                },
            }
        } else {
            // Lookup handle in our tag directives.
            let prefix = self.tags.get(handle);
            if let Some(prefix) = prefix {
                Tag {
                    handle: prefix.clone(),
                    suffix,
                }
            } else {
                // Otherwise, it may be a local handle. With a local handle, the handle is set to
                // "!" and the suffix to whatever follows it ("!foo" -> ("!", "foo")).
                // If the handle is of the form "!foo!", this cannot be a local handle and we need
                // to error.
                if handle.len() >= 2 && handle.starts_with('!') && handle.ends_with('!') {
                    return Err(ScanError::new_str(span.start, "the handle wasn't declared"));
                }
                Tag {
                    handle: handle.to_string(),
                    suffix,
                }
            }
        };
        Ok(Cow::Owned(tag))
    }
}

impl<'input, T: Input> Iterator for Parser<'input, T> {
    type Item = Result<(Event<'input>, Span), ScanError>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_event()
    }
}

#[cfg(test)]
mod test {
    use super::{Event, Parser};

    #[test]
    fn test_peek_eq_parse() {
        let s = "
a0 bb: val
a1: &x
    b1: 4
    b2: d
a2: 4
a3: [1, 2, 3]
a4:
    - [a1, a2]
    - 2
a5: *x
";
        let mut p = Parser::new_from_str(s);
        loop {
            let event_peek = p.peek().unwrap().unwrap().clone();
            let event = p.next_event().unwrap().unwrap();
            assert_eq!(event, event_peek);
            if event.0 == Event::StreamEnd {
                break;
            }
        }
    }

    #[test]
    fn test_keep_tags_across_multiple_documents() {
        let text = r#"
%YAML 1.1
%TAG !t! tag:test,2024:
--- !t!1 &1
foo: "bar"
--- !t!2 &2
baz: "qux"
"#;
        for x in Parser::new_from_str(text).keep_tags(true) {
            let x = x.unwrap();
            if let Event::MappingStart(_, tag) = x.0 {
                let tag = tag.unwrap();
                assert_eq!(tag.handle, "tag:test,2024:");
            }
        }

        for x in Parser::new_from_str(text).keep_tags(false) {
            if x.is_err() {
                // Test successful
                return;
            }
        }
        panic!("Test failed, did not encounter error")
    }
}