Forward progress with Many

[alexbbrown]

TL;DR: Many should detect when it's not making forward progress

As a rookie user I spent some time stuck with a parser which didn't terminate.

for parsing strings of the form: "A->B B->C C->D->E"

Many(
  Many(stringLiteral, separator: StartsWith("->".utf8),
  separator: WhiteSpace()
}

However, this enters an infinite loop for many inputs.

Analysis & Fix for my case

There was no indication of where the problem was, so I addressed it by randomly changing parts of the parser and input until I narrowed the problem down:

The challenge here is that it's possible for the Many to go around its loop without consuming any input, and then repeat that infinitely.

Why?

• WhiteSpace can legally succeed by consuming 0 elements from input
• the inner Many can also legally succeed by consuming 0 elements from input (the length 0 array)
• If Many succeeds by matching both the element and the separator, it enters a new iteration of the loop - at the same place (and will fail in the same way)

So for inputs which don't match stringLiteral OR WhiteSpace it's impossible to exit from the outer Many, and it runs forever.

The 'Bug' in my code is that I assumed whitespace meant \w+ but it actually means \w*

Workaround

The workaround was to create a version of the WhiteSpace operator which requires at least one character, but I wonder if the Parser system itself could detect statically or dynamically that it would not completed.

let whitespaceSeparator = Whitespace<Input>().filter { $0.count > 0 }
let parser = Many(
  Many(stringLiteral, separator: StartsWith("->".utf8),
  separator: whitespaceSeparator
}

Another workaround would be to insist that the inner many matches at least once

Many(
  Many(stringLiteral, atLeast: 1, separator: StartsWith("->".utf8),
  separator: WhiteSpace()
}

Avoiding the problem in the general case

However, discovering this fact was hard: there was no feedback or diagnostic showing that the parser contained an infinite loop, and no indication that it had entered one at runtime.

Assuming the child parsers are stateless (not necessarily a good assumption), we could simply have Many abort as soon as it detected that on the first (or subsequent) passes it has consumed no input.

[stephencelis]

The occasional infinite loop is definitely annoying. We've hit it in the past and it can be tough to diagnose!

Assuming the child parsers are stateless (not necessarily a good assumption), we could simply have Many abort as soon as it detected that on the first (or subsequent) passes it has consumed no input.

@mbrandonw and I have discussed this exact solution, but haven't explored it yet. If you have any ideas on how to incorporate such a change into the library, we'd love to see!

[nikita-leonov]

I do not have a solution for this problem, but also want to point out that had a similar issue. In the beginning, I assumed that it is due to performance, and not an infinite loop. This is indeed challenging to figure out what is going on and why.

[alexito4]

Without commenting on the general case, I would like to point out that in some contexts the behaviour of Whitespace is also surprising. Maybe it would be worth to be able to pass a flag asking it to at least parse 1 whitespace.