Adding a Not operator

[randomeizer]

So, in my current context, I'm parsing source code, pulling out documentation comments, which are lines prefixed with /// (vs // or ////). I'd like to be able to do something like (simplified):

let docLine = Parse {
    "/// "
    PrefixThrough("\n)
}

let notDocLine = OneOf {
    Not {
        "/// "
    }
    Skip(PrefixThrough("\n"))
}

let docLines = Many {
    Skip {
        Many {
            notDocLine
        }
    }
    docLine
}

I'm not quite sure how to build a Not operator. Thoughts?

[randomeizer]

A related thing I was thinking about is, is it possible to have PrefixUpTo and PrefixThrough get passed a Parser rather than a String/Substring/etc? Eg:

let notDocLines = PrefixUpTo {
    "\n"
    oneOrMoreSpaces
    "/// "
}

[stephencelis]

is it possible to have PrefixUpTo and PrefixThrough get passed a Parser rather than a String/Substring/etc?

While it's possible, we're not sure it's a performant thing to do. When working directly with a possible prefix of characters/bytes, we can call down to collection/string methods that are pretty good about scanning the underlying collection for a certain subsequence.

Meanwhile, if we were handed a parser instead, we'd have to run that parser, drop a character, run it again, and keep going. This means running a potentially expensive operation for every character of input till it succeeds (or till we run out of input).

We think it might be possible to have PrefixUpTo and PrefixThrough detect the more performant parsers (StartsWith and the literal parsers) and special case them, but we're worried that the general case is too slow to encourage.

[randomeizer]

Yeah, that's definitely a concern (similar to some regex operators), but there are plenty of ways to write a bad parser. In some cases it may the be only way to achieve something.

In most cases, the failure would happen pretty quickly. Would still require testing it by dropping each item in the collection though.

[stephencelis]

We're not against it, especially if we can get some benchmarks in place to show that for your average parser it performs OK, but we're worried that it naively introduces performance issues that are quadratic with the input length.

In the meantime it should be implementable outside the library if you want to try it out!

[randomeizer]

Yeah, totally, I get the concern. I might have a play.

[stephencelis]

I'm not quite sure how to build a Not operator. Thoughts?

I think Not would be a great combinator to add! There's even a precedent in nom, a popular Rust parsing framework.

I think we could start by getting a parser into place:

struct Not<Upstream>: Parser where Upstream: Parser {
}

We'll need to hold onto that upstream parser:

let upstream: Upstream

And we'll need a builder-friendly initializer:

init(@ParserBuilder _ build: () -> Upstream) {
  self.upstream = build()
}

Now all we need to do is implement parse to get a passing conformance, which can call down to the underlying upstream parser's parse method, and fail if it succeeds (while also rolling back input to its original state), or return Void to succeed if it fails:

func parse(_ input: inout Upstream.Input) -> Void? {
  let original = input
  if self.upstream.parse(&input) {
    input = original
    return nil
  }
  return ()
}

I've only sketched this out in this GitHub text field, so there may be bugs or compiler errors to work through, but hopefully it's enough to get you started 😄

[stephencelis]

@randomeizer Would you be up to PRing those to main? Without the ParserBuilder stuff (we'll add that when we're closer to release).

So instead your example would be:

Not("/// ")
  .skip(PrefixThrough("\n"))

[iampatbrown]

@stephencelis is it worth making these inlinable?

[stephencelis]

Yup for sure!

[randomeizer]

I'll push a PR shortly.

[randomeizer]

PR here: #89