Repeat expression that doesn't consume input should be a compile time error

[hfiguiere]

I found this issue porting from 0.5.0 to 0.6.0.

When I run my parser test, it get stuck in an infinite loop (ie it never terminate).

This is the reduced test case:

extern crate peg;

peg::parser!{grammar p() for str {

pub rule string_literal() -> String
        = "\"" s:$((!['"'])*) "\"" { println!("literal {}", s); s.to_owned() }

}}

fn main() {

    let r = p::string_literal("\"literal\"");

    if let Ok(l) = r {
        println!("Parsed {}", l);
    } else {
        println!("Parse failed {:?}", r);
    }
}

Expected:

• either it doesn't compile because it's a syntax error (i.e. I'm doing the rule wrong with the update syntax)
• or it is a parse error

Instead it just get stuck when I cargo run.

[kevinmehall]

(!['"'])* matches nothing, repeatedly, as long as the next character is not a quote.

The !X operator is negative lookahead -- it matches without consuming characters if X fails to match, or fails to match if X matches at the current position. It looks like you're trying to use (!['"'])* as "any character besides "", presumably as a replacement for 0.5's [^"]. You actually want (!['"'] [_])* where the [_] consumes the character if it's not a quote.

0.6 adds compile-time checks for other patterns like left recursion that infinite loop in PEG, so repeating an expression that matches without consuming input should similarly be made an error.

[kevinmehall]

Also, I meant to find a new syntax for inverted character sets that would be compatible with token trees and the new expansion into match arms, but since the hack with negative lookahead worked, I never came up with a replacement. It is a common enough pattern that it probably deserves its own syntax, though.

For now, I added an example inverted character set to the upgrade steps in the 0.6 release notes that hopefully helps clarify this for others.

[hfiguiere]

Thanks !

[kw217]

Hi - I'm using 0.6.2 and I don't believe this is completely fixed. Here is my code, which leads to an infinite loop:

use peg;

pub fn main() {
    test_parser::top("test").unwrap()
}

peg::parser!{
    grammar test_parser() for str {
        rule _() = " "*
        rule nl() = _* "\n" _*
        pub rule top() = nl()
    }
}

It would be nice if this was spotted by the compiler.

It was quite hard to find this in my (larger) codebase; is there a way to set a maximum recursion depth or parse time or something, to aid debugging?

[kevinmehall]

Yeah, this issue is still open. As of 0.6, rust-peg checks for infinite loops by left recursion, but it does not yet check for * infinitely matching zero characters.

Your best bet for debugging issues like this would be the trace feature. Or a backtrace in a debugger like GDB should give you a reasonable stack trace of parse_<rulename> calls.

[kw217]

OK, thanks.

[kw217]

Great, thanks!