nom_supreme/

multi.rs

/*!
Perfected looping parsers designed to behave more reliably and provide more
useful parse errors.

The combinators in this module all generally follow the same pattern for
parsing in a loop. They parse an item; then, they attempt to parse a
`terminator`. If the `terminator` is found, the parse returns successfully;
otherwise, they attempt to parse a `separator`. If they fail to parse either
a `separator` or a `terminator`, the parse fails; otherwise, it will continue
on to parse the next item. The parsed items are collected together into a final
value; each combinator does this in a slightly different way:

- [`collect_separated_terminated`] collects the parsed items into a collection
with [`Extend`].
- [`parse_separated_terminated`] combines the parsed items with a folding
function.
- [`parse_separated_terminated_res`] combines the parsed items with a fallible
folding function; it may return early if the folding function returns an
[`Err`].

These combinators always parse at least 1 item. If you want 0 or more things
to be parsed, use [`opt`] or [`alt`] to handle that case.

These combinators will stop as soon as they find a `terminator`. If you wish
to have a `terminator` parser that is the same as your `separator`, you'll need
to add some extra context to the terminator parser; perhaps a lookahead
with [`peek`].

These combinators exists to provide meaningful parse errors. By requiring a
`terminator`, we can ensure that they don't suffer from the normal folding
parser problem of unconditionally returning success because a subparser failure
is interpreted as the end of the loop. This ensures that potentially important
errors aren't thrown away.

The combinators will attempt to smartly allow 0-length matches. It will allow
subparsers to have 0-length matches, but if a full loop is made without any
progress being made, we assume we've encountered an infinite loop and return
a parse error.

[`opt`]: crate::parser_ext::ParserExt::opt
[`alt`]: nom::branch::alt
[`peek`]: crate::parser_ext::ParserExt::peek
*/

use core::{convert::Infallible, iter};

use nom::{
    error::{ErrorKind::SeparatedNonEmptyList, FromExternalError, ParseError},
    Err::Error,
    InputLength, Parser,
};

/**
Parse a series of 1 or more things, separated by `separator`, terminated by
`terminator`, and collect them into a collection using [`Extend`].

When this parser is run, it will create a new, empty collection with
[`Default`]. It will then collect each parsed item into the collection with
[`Extend`]. See the [module] docs for details of how this parser parses a sequence.

See the [module] docs for a detailed description of how this parser parses a sequence.

# Example

```
use nom_supreme::{
    multi::collect_separated_terminated,
    parser_ext::ParserExt,
    error::ErrorTree,
};
use nom::character::complete::{digit1, char, space0};
use nom::{IResult, Parser, error::ParseError};

fn parse_number(input: &str) -> IResult<&str, i32, ErrorTree<&str>> {
    digit1
        .preceded_by(char('-').opt())
        .recognize()
        .parse_from_str()
        .parse(input)
}

// A vector is a square brackets, containing comma separated numbers, with
// whitespace in between
let mut vec_parser = collect_separated_terminated(
    // Parse numbers
    parse_number.terminated(space0),

    // separated by commas
    char(',').terminated(space0),

    // terminated by a close bracket
    char(']'),
)
// Allow for empty vectors
.or(char(']').value(Vec::new()))
.preceded_by(char('[').terminated(space0));

let result: IResult<&str, Vec<i32>, ErrorTree<&str>> = vec_parser.parse("[1, 2, -3, 4]");
let vec = result.unwrap().1;
assert_eq!(vec, [1, 2, -3, 4]);

```

[module]: crate::multi
*/
pub fn collect_separated_terminated<
    Input,
    ParseOutput,
    SepOutput,
    TermOutput,
    ParseErr,
    Collection,
>(
    parser: impl Parser<Input, ParseOutput, ParseErr>,
    separator: impl Parser<Input, SepOutput, ParseErr>,
    terminator: impl Parser<Input, TermOutput, ParseErr>,
) -> impl Parser<Input, Collection, ParseErr>
where
    Input: Clone + InputLength,
    ParseErr: ParseError<Input>,
    Collection: Default + Extend<ParseOutput>,
{
    parse_separated_terminated(
        parser,
        separator,
        terminator,
        Collection::default,
        // TODO: use extend_one
        |collection, item| express!(collection.extend(iter::once(item))),
    )
}

/**
Parse a series of 1 or more things, separated by `separator`, terminated by
`terminator`, and fold them together using a folding function.

When this parser is run, it will first create an accumulator value with `init`.
It will then combine it with every parsed item using `fold`, which should
return the new accumulator for each item. See the [module] docs for details
of how this parser parses a sequence.

[module]: crate::multi
*/
#[inline]
pub fn parse_separated_terminated<Input, ParseOutput, SepOutput, TermOutput, ParseErr, Accum>(
    parser: impl Parser<Input, ParseOutput, ParseErr>,
    separator: impl Parser<Input, SepOutput, ParseErr>,
    terminator: impl Parser<Input, TermOutput, ParseErr>,

    init: impl FnMut() -> Accum,
    mut fold: impl FnMut(Accum, ParseOutput) -> Accum,
) -> impl Parser<Input, Accum, ParseErr>
where
    Input: Clone + InputLength,
    ParseErr: ParseError<Input>,
{
    parse_separated_terminated_impl(
        parser,
        separator,
        terminator,
        init,
        move |accum, item| Ok(fold(accum, item)),
        |_input, err: Infallible| match err {},
    )
}

/**
Parse a series of 1 or more things, separated by some `separator`, terminated
by some `terminator`, folding them all together with a fallible fold function.

This function is identical to [`parse_separated_terminated`], except that
the fold function may return an error, which ends the parse early. See its
documentation for more details about the precise behavior of this parser.
*/
#[inline]
pub fn parse_separated_terminated_res<
    Input,
    ParseOutput,
    SepOutput,
    TermOutput,
    ParseErr,
    Accum,
    FoldErr,
>(
    parser: impl Parser<Input, ParseOutput, ParseErr>,
    separator: impl Parser<Input, SepOutput, ParseErr>,
    terminator: impl Parser<Input, TermOutput, ParseErr>,

    init: impl FnMut() -> Accum,
    fold: impl FnMut(Accum, ParseOutput) -> Result<Accum, FoldErr>,
) -> impl Parser<Input, Accum, ParseErr>
where
    Input: Clone + InputLength,
    ParseErr: ParseError<Input> + FromExternalError<Input, FoldErr>,
{
    parse_separated_terminated_impl(parser, separator, terminator, init, fold, |input, err| {
        ParseErr::from_external_error(input, SeparatedNonEmptyList, err)
    })
}

/// Helper enum for tracking zero length parses. `parse_separated_terminated`
/// allows for subparsers to return zero-length matches, but if *every*
/// subparser does so in a loop, that's reported as an error.
///
/// This enum specifically tracks the least-recent zero-length parse that has
/// not been succeeded by a non-zero-length parser.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ZeroLengthParseState<E> {
    None,
    Item,
    Separator { terminator_error: E },
}

impl<E> ZeroLengthParseState<E> {
    fn terminator_error(self) -> Option<E> {
        match self {
            Self::Separator { terminator_error } => Some(terminator_error),
            _ => None,
        }
    }
}

/// Shared implementation for parse_separated_terminated_res and
/// parse_separated_terminated. This exists so that we don't have to have an
/// unnecessary bound of FromExternalError on parse_separated_terminated.
#[inline]
fn parse_separated_terminated_impl<
    Input,
    ParseOutput,
    SepOutput,
    TermOutput,
    ParseErr,
    Accum,
    FoldErr,
>(
    mut parser: impl Parser<Input, ParseOutput, ParseErr>,
    mut separator: impl Parser<Input, SepOutput, ParseErr>,
    mut terminator: impl Parser<Input, TermOutput, ParseErr>,

    mut init: impl FnMut() -> Accum,
    mut fold: impl FnMut(Accum, ParseOutput) -> Result<Accum, FoldErr>,

    mut build_error: impl FnMut(Input, FoldErr) -> ParseErr,
) -> impl Parser<Input, Accum, ParseErr>
where
    Input: Clone + InputLength,
    ParseErr: ParseError<Input>,
{
    move |mut input: Input| {
        let mut accum = init();

        let mut zero_length_state = ZeroLengthParseState::None;

        loop {
            // Try to find a value. To fail to do so at this point is an
            // error, since we either just started or successfully parsed a
            // separator.
            //
            // If an error occurs here, also try to attach terminator_error.
            // terminator_error is available if the most recent separator parse
            // was zero-length, which means that both the terminator and the
            // item would be valid parses at this point.
            let (tail, value) = match parser.parse(input.clone()) {
                Ok(success) => success,
                Err(Error(item_error)) => {
                    break Err(Error(match zero_length_state.terminator_error() {
                        None => item_error,
                        Some(terminator_error) => item_error.or(terminator_error),
                    }))
                }
                Err(err) => break Err(err),
            };

            // Check zero-length matches
            zero_length_state = match (input.input_len() == tail.input_len(), zero_length_state) {
                // If both the item and the separator had a zero length match,
                // we're hanging. Bail.
                //
                // It doesn't make sense to include the terminator error here,
                // because we *did* successfully parse a separator and an
                // item, they just happened to be zero length
                (true, ZeroLengthParseState::Separator { .. }) => {
                    break Err(Error(ParseErr::from_error_kind(
                        input,
                        SeparatedNonEmptyList,
                    )))
                }

                // If only the item had a zero-length match, update the
                // state.
                (true, _) => ZeroLengthParseState::Item,

                // If the item had a non-zero length match, clear the state
                (false, _) => ZeroLengthParseState::None,
            };

            // Advance the loop state
            accum = fold(accum, value).map_err(|err| Error(build_error(input, err)))?;
            input = tail;

            // Try to find a terminator; if we found it, we're done. If we
            // didn't, preserve the error, so that it can be reported as an
            // .or() branch with the subsequent separator or item error.
            let terminator_error = match terminator.parse(input.clone()) {
                // We found a terminator, so we're done
                Ok((tail, _)) => break Ok((tail, accum)),

                // No terminator. Keep track of the error in case we also fail
                // to find a separator or item.
                Err(Error(err)) => err,

                // Other kinds of errors should be returned immediately.
                Err(err) => break Err(err),
            };

            // No terminator, so instead try to find a separator
            let tail = match separator.parse(input.clone()) {
                Ok((tail, _)) => tail,
                Err(Error(separator_error)) => {
                    break Err(Error(separator_error.or(terminator_error)))
                }
                Err(err) => break Err(err),
            };

            // Check zero-length matches
            zero_length_state = match (input.input_len() == tail.input_len(), zero_length_state) {
                // If both the separator and the item had a zero length match,
                // we're hanging. Bail.
                (true, ZeroLengthParseState::Item) => {
                    break Err(Error(ParseErr::from_error_kind(
                        input,
                        SeparatedNonEmptyList,
                    )))
                }
                // If only the separator had a zero-length match, update the
                // state. Additionally preserve the terminator error so that
                // it can be reported as an alternate if there was an item
                // error.
                (true, _) => ZeroLengthParseState::Separator { terminator_error },

                // If the separator had a non-zero length match, clear the
                // state
                (false, _) => ZeroLengthParseState::None,
            };

            // Advance the loop state
            input = tail;
        }
    }
}

#[cfg(test)]
mod test_separated_terminated {
    use cool_asserts::assert_matches;
    use nom::{
        branch::alt,
        character::complete::{alpha0, char, digit1, space0},
        error::ErrorKind,
        Err, IResult, Parser,
    };

    use crate::error::{BaseErrorKind, ErrorTree, Expectation};
    use crate::parser_ext::ParserExt;

    use super::parse_separated_terminated;

    /// Parse a series of numbers, separated by commas, terminated by a period.
    fn parse_number_list(input: &str) -> IResult<&str, Vec<i64>, ErrorTree<&str>> {
        parse_separated_terminated(
            digit1.parse_from_str(),
            char(',').delimited_by(space0),
            char('.').preceded_by(space0),
            Vec::new,
            |vec, num| express!(vec.push(num)),
        )
        .parse(input)
    }

    #[test]
    fn basic() {
        assert_eq!(
            parse_number_list("1, 2, 3, 4, 5.").unwrap(),
            ("", vec![1, 2, 3, 4, 5]),
        )
    }

    #[test]
    fn trailing_input() {
        assert_eq!(
            parse_number_list("1, 2, 3, 4, 5. 4, 5, 6.").unwrap(),
            (" 4, 5, 6.", vec![1, 2, 3, 4, 5]),
        )
    }

    #[test]
    fn only_one() {
        assert_eq!(parse_number_list("10.").unwrap(), ("", vec![10]),)
    }

    #[test]
    fn at_least_one() {
        let err = parse_number_list("abc").unwrap_err();

        assert_matches!(
            err,
            Err::Error(ErrorTree::Base {
                location: "abc",
                kind: BaseErrorKind::Expected(Expectation::Digit)
            })
        );
    }

    /// Test that a parse failure from both the separator and the terminator
    /// causes an error including both messages
    #[test]
    fn terminator_separator_miss() {
        let err = parse_number_list("10, 20 30.").unwrap_err();

        let choices = assert_matches!(err, Err::Error(ErrorTree::Alt(choices)) => choices);
        assert_matches!(
            choices.as_slice(),
            [
                ErrorTree::Base {
                    location: "30.",
                    kind: BaseErrorKind::Expected(Expectation::Char(','))
                },
                ErrorTree::Base {
                    location: "30.",
                    kind: BaseErrorKind::Expected(Expectation::Char('.'))
                },
            ]
        );
    }

    /// Test that a terminator is required, even at EoF
    #[test]
    fn required_terminator() {
        let err = parse_number_list("1, 2, 3").unwrap_err();

        let choices = assert_matches!(err, Err::Error(ErrorTree::Alt(choices)) => choices);
        assert_matches!(
            choices.as_slice(),
            [
                ErrorTree::Base {
                    location: "",
                    kind: BaseErrorKind::Expected(Expectation::Char(','))
                },
                ErrorTree::Base {
                    location: "",
                    kind: BaseErrorKind::Expected(Expectation::Char('.'))
                },
            ]
        );
    }

    /// Test that a parse failure from the item parser includes only that error
    /// if the separator isn't zero-length
    #[test]
    fn item_error() {
        let err = parse_number_list("1, 2, abc.").unwrap_err();

        assert_matches!(
            err,
            Err::Error(ErrorTree::Base {
                location: "abc.",
                kind: BaseErrorKind::Expected(Expectation::Digit),
            })
        );
    }

    /// Parse a series of numbers ending in periods, separated by 0 or more
    /// whitespace, terminated by a semicolon. Used to test 0-length
    /// separator behavior.
    fn parse_number_dot_list(input: &str) -> IResult<&str, Vec<i64>, ErrorTree<&str>> {
        parse_separated_terminated(
            digit1.terminated(char('.')).parse_from_str(),
            space0,
            char(';'),
            Vec::new,
            |vec, num| express!(vec.push(num)),
        )
        .parse(input)
    }

    #[test]
    fn zero_length_separator() {
        assert_eq!(
            parse_number_dot_list("1.2. 3.4.  5.; abc").unwrap(),
            (" abc", vec![1, 2, 3, 4, 5])
        );
    }

    /// Test that, when a separator matches zero length, and then the item
    /// parser fails, the returned error includes both the item error and the
    /// terminator error.
    #[test]
    fn zero_length_separator_item_term_error() {
        let err = parse_number_dot_list("1.2.3.abc.;").unwrap_err();

        let choices = assert_matches!(err, Err::Error(ErrorTree::Alt(choices)) => choices);
        assert_matches!(
            choices.as_slice(),
            [
                ErrorTree::Base {
                    location: "abc.;",
                    kind: BaseErrorKind::Expected(Expectation::Digit)
                },
                ErrorTree::Base {
                    location: "abc.;",
                    kind: BaseErrorKind::Expected(Expectation::Char(';'))
                },
            ]
        );
    }

    /// Parse a series of runs of 1 or more digits or 0 more more letters, separated by
    /// an optional dash, terminated by a semicolon. Used to test
    /// infinite loop detection
    fn parse_letters_numbers(input: &str) -> IResult<&str, Vec<&str>, ErrorTree<&str>> {
        parse_separated_terminated(
            alt((digit1, alpha0)),
            char('-').opt(),
            char(';'),
            Vec::new,
            |vec, num| express!(vec.push(num)),
        )
        .parse(input)
    }

    #[test]
    fn zero_length_item() {
        assert_eq!(
            parse_letters_numbers("----; abc").unwrap(),
            (" abc", vec!["", "", "", "", ""])
        )
    }

    #[test]
    fn zero_length_separators() {
        assert_eq!(
            parse_letters_numbers("abc123abc123; abc").unwrap(),
            (" abc", vec!["abc", "123", "abc", "123"]),
        )
    }

    /// Test that both zero-length separators and items are allowed together,
    /// as long as the loop makes progress
    #[test]
    fn zero_length_mixed() {
        assert_eq!(
            parse_letters_numbers("abc--123abc-123-; abc").unwrap(),
            (" abc", vec!["abc", "", "123", "abc", "123", ""]),
        )
    }

    /// Test that if the loop makes no progress, that's an error
    #[test]
    fn infinite_loop_aborts() {
        let err = parse_letters_numbers("abc123-.; abc").unwrap_err();

        assert_matches!(
            err,
            Err::Error(ErrorTree::Base {
                location: ".; abc",
                kind: BaseErrorKind::Kind(ErrorKind::SeparatedNonEmptyList)
            })
        );
    }

    /// Parse a series of numbers, separated by commas, terminated by optional
    /// comma and eof. Used to test that the terminator "wins" when it and the
    /// separator can match the same string.
    fn parse_comma_separated(input: &str) -> IResult<&str, Vec<i64>, ErrorTree<&str>> {
        parse_separated_terminated(
            digit1.parse_from_str(),
            char(','),
            char(',').opt().all_consuming(),
            Vec::new,
            |vec, num| express!(vec.push(num)),
        )
        .parse(input)
    }

    #[test]
    fn empty_terminator_wins() {
        assert_eq!(
            parse_comma_separated("1,2,3,4").unwrap(),
            ("", vec![1, 2, 3, 4]),
        );
    }

    #[test]
    fn test_terminator_wins() {
        assert_eq!(
            parse_comma_separated("1,2,3,4,").unwrap(),
            ("", vec![1, 2, 3, 4]),
        )
    }
}