Is matching EOF considered a "consume" for the repeat combinator?

[DavidAntliff]

Hi,

My experience with winnow is limited to a couple of days so perhaps I've missed something, or there's a better way to do what I want to do.

I wish to match on a "blank line", and to be clear I mean:

• The input is text,
• A blank line starts at either the beginning of the input, or immediately after a line_ending,
• A blank line has zero or more white-space characters,
• A blank line ends in either a line_ending or an eof.

The problem I'm having is that even though this seems fairly simple:

enum Expression {
    BlankLine,
    // ... other types of lines
}

fn blank_line(i: &mut &str) -> PResult<Expression> {
    (
        space0,
        alt((line_ending, eof)),
    )
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

this does not seem to work with the repeat combinator:

fn expression(i: &mut &str) -> PResult<Expression> {
    alt((
        // ... other parsers for other types of lines
        blank_line,
    ))
    .parse_next(i)
}

fn file(i: &mut &str) -> PResult<Vec<Expression>> {
    repeat(0.., expression).parse_next(i)
}

`repeat` parsers must always consume

I think this is because the eof match is not considered a consumable part of the input, so there's a condition (zero whitespace, followed by EOF) that should match but doesn't consume anything.

I'm also not sure if this error is due a check performed when this condition arises (if ever), or if the check is done based on what might happen by examining the parser tree. Is there a workaround?

[epage]

Yes, eof does not consume, ie it does not move what input points to

One way to workaround this would be

enum Expression {
    BlankLine,
    // ... other types of lines
}

fn blank_line(i: &mut &str) -> PResult<Expression> {
    alt((
        (space0, line_ending),
        (space1, eof),
    ))
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

This could be optimized as

enum Expression {
    BlankLine,
    // ... other types of lines
}

fn blank_line(i: &mut &str) -> PResult<Expression> {
    alt((
        line_ending,
        (space1, alt((line_ending, eof))),
    ))
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

There might be additional optimizations that could be made with dispatch!

[DavidAntliff]

BTW, in case it helps anyone else, the code given above:

fn blank_line(i: &mut &str) -> PResult<Expression> {
    alt((
        line_ending,
        (space1, alt((line_ending, eof))),
    ))
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

Does not compile:

error[E0271]: type mismatch resolving `<&str as Stream>::Slice == (&str, &str)`
   --> src/asm/parser.rs:218:10
    |
218 |     alt((line_ending, (space1, alt((line_ending, eof)))))
    |     ---  ^^^^^^^^^^^ expected `(&str, &str)`, found `&str`
    |     |
    |     required by a bound introduced by this call
    |
    = note:  expected tuple `(&str, &str)`
            found reference `&str`

This is caused by mapping to different result types between line_ending and the 2-tuple, such that the following does compile by reducing the 2-tuple to a 1-tuple:

fn blank_line(i: &mut &str) -> PResult<Expression> {
    alt((line_ending, terminated(space1, alt((line_ending, eof)))))
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

or ignoring both match results entirely:

fn blank_line(i: &mut &str) -> PResult<Expression> {
    alt((line_ending.void(), (space1, alt((line_ending, eof))).void()))
        .map(|_| Expression::BlankLine)
        .parse_next(i)
}

[DavidAntliff]

Unfortunately I just couldn't get this to work. I ended up having to match for alt((line_ending, eof)) in many of my sub-parsers, rather than in just one place, which meant I also had to start testing for trailing "comments" everywhere too, including those with a preceding space0 and those without. It became a huge mess, sadly. I'll have another crack another time. Maybe an explicit "per line" loop at the top level, parsing each line individually, would work better than repeat(0.., ...), so I can avoid the overly-eager loop check entirely.

Everything else in winnow has been very nice to use - nice work, thank you :)

[epage]

Do you have your grammar in BNF form? That would make it easier to understand for me to provide suggestions

[DavidAntliff]

Do you have your grammar in BNF form? That would make it easier to understand for me to provide suggestions

I think this sums up my situation, with some notes in comments:

<File> ::= <LineNewLine>* <LineNoNewLine>?

<Line> ::= (<A> | <B> | <BlankLine>) <WhiteSpace>? <Comment>?
<LineNewLine> ::= <Line> <NewLine>
<LineNoNewLine> ::= <Line>

/* in reality, there are a LOT of these "line" rules, A, B, C, ... Z */
<A> ::= "aaa"
<B> ::= "bbb"

<WhiteSpace> ::= (" " | "\t")*
<BlankLine> ::= <WhiteSpace>
<NewLine> ::= ("\n" | "\r\n")

/* simplified - in reality accept all characters to end of line/file */
<Comment> ::= ";" ([a-z] | [0-9] | " ")*

Some valid inputs:

Trailing newline:

aaa
<EOF>

No trailing newline:

aaa<EOF>

Trailing whitespace and newline:

aaa
    <EOF>

Trailing comment:

aaa
bbb  ; comment<EOF>

Blank lines:

aaa

bbb

<EOF>

BNF Playground

Putting this together has actually shed some light on the subject - I can perhaps better see how to compose a winnow parser from this, without mentioning eof at all, potentially. I will give it a go.

[epage]

There are also subtle grammar changes you can make that might simplify things.

For example, you have

<File> ::= <LineNewLine>* <LineNoNewLine>?

TOML has

toml = expression *( newline expression )

Also, isn't

<Line> ::= (<A> | <B> | <BlankLine>) <WhiteSpace>? <Comment>?

just

<Line> ::= (<A> | <B>)? <WhiteSpace>? <Comment>?

Also, since WhiteSpace is

<WhiteSpace> ::= (" " | "\t")*

then you can drop ?

<Line> ::= (<A> | <B>)? <WhiteSpace> <Comment>?

However, I would have WhiteSpace defined as

<WhiteSpace> ::= (" " | "\t")

and leave the repetition up to the caller.

In case its useful, TOML's abnf is at https://github.com/toml-lang/toml/blob/main/toml.abnf

toml_edit is a Winnow parser that documents how each parser function maps back to the ABNF.

[Nahor]

eof doesn't not consume because it can't, by definition. It means "end-of-file", i.e "there-is-nothing-left-to-consume".

As for your problem, you have "repeat(line_w_newline or line_wo_newline)", which implies that you could have "<line_wo_newline><line_w_newline>", which makes no sense. So what you need is "repeat(line_w_newline) then maybe line_wo_newline" (as you said yourself in your BNF grammar)

But probably a better way of thinking is to not see the newline character as part of the line, but as a separator (see separated())

[DavidAntliff]

Hi @Nahor, thank you for the suggestion. Switching repeat(0.., delimited(space0, ..., (space0, line_ending))) to separated(0.., delimited(space0, ..., space0), line_ending) does the trick in my case. It sometimes adds an extra BlankLine to the end of the resultant vector but I think that's perfectly consistent with the input, and easily dealt with.

I'm not sure why repeat(0.. hits the infinite-loop check but separated(0.. does not - is that because the separated check always assumes it will consume the separator, which in my case is line_ending thus never "nothing"?

[Nahor]

I'm not sure why repeat(0.. hits the infinite-loop check

Because delimited(space0, ..., (space0, line_ending)) can match a 0-length string ("<zero space><blankline terminating because of eof><zero space>"), i.e. it can always match, even when there are no more characters left.

separated(...) works because, as you figured, it requires newlines to continue matching. So once it's at EOF and there is no more newlines, it can't continue.

delimited(...) should work if you follow your own BNF:

(repeat(0.., line_newline), opt(line_no_newline))
aka 
(repeat(0.., (line, line_ending)), line)

where, like separated, you repeat while you still have line endings, then have one extra line to match the last line, even if it's just an empty/0-length blankline.

It sometimes adds an extra BlankLine to the end of the resultant vector but I think that's perfectly consistent with the input, and easily dealt with.

I assume that it's when your document terminates with a newline character, in which case, there is an empty/0-length blankline between the last newline and eof.

[DavidAntliff]

I assume that it's when your document terminates with a newline character, in which case, there is an empty/0-length blankline between the last newline and eof.

Yep, that's the one. Makes sense and is consistent.

Empty input "" also parses to vec![BlankLine] but that's consistent too.

Thanks!