Should long-running parsers check for task cancellation?

[tgrapperon]

Hello,
While I was toying with Parsing and the new Regex from Swift 5.7, it occurred to me that a few matching commands of Regex are throwing if matching is aborted (it returns nil when it fails). Looking at SE-0350, it corresponds to cases where the parent Task is canceled.

Since parsers are already throwing, should we implement the same behavior with potentially long-running parsers like Many or OneOf for example?

For example, if we make Regex a Parser (we could also wrap it in some type if needed):

#if swift(>=5.7)
@available(iOS 16.0, macOS 13.0, tvOS 16.0, watchOS 9.0, *)
extension Regex: Parser {
  public func parse(_ input: inout Substring) throws -> Output  {
    guard let match = try regex.prefixMatch(in: input) else {
      throw ParsingError.failed(
        summary: "Regex can't match",
        label: "fails to match \(regex)",
        at: input)
    }
    input = input[match.range.upperBound...]
    return match.output
  }
}
#endif

This parser will throw if the parent Task is aborted. Because the error shouldn't be a ParsingError, we can directly throw Regex's own error. We could probably do the same with other parsers like Many.

There are probably super interesting bridges to draw between Parsing and Regex, and it probably doesn't stop there, but the question about checking task cancellation in parsers is orthogonal.

Should we go on with it? Should we only perform the checks for a selected set of candidates?
Thanks!

[stephencelis]

@tgrapperon Interesting find! It does sound like calling Task.checkCancellation in Many and maybe some other combinators could be a good idea: the Zips and OneOfs also come to mind, but maybe are less necessary.

[tgrapperon]

Alternatively, a combinator that throws on Task.checkCancellation could offer some kind of flexibility to the user while preserving the performance in any synchronous cases (we need to benchmark the impact anyway). We could use a fluent style (my preference in this case, as we only modify the behavior of an existing parser), or a closure style:

Many {
  Parse {
    …
  }.cancellable()
}

Many {
  Cancellable {
    Parse {…}
  }
}

This kind of parser could be implemented by a third-party, or it can be built-in. I think the benefits of cancelling early is fundamental enough to justify the later, but it would be your call at the end.

I'll benchmark the effect of Task.checkCancellation later. If it's negligible, it should probably be directly backed into a few combinators. Otherwise, the Cancellable combinator (or whatever its name) could provide a nice workaround.

[tgrapperon]

Also, should we check when printing?

[tgrapperon]

Ok, here are the initial benchmarks results: Simply adding a check in before running each element of a Many induces a very noticeable overhead. From 3% for the CSV parser, up to 20% for Numerics: Comma separated: Int.parser. The impact greatly depends on the kind of parser that is run and the potential count of elements. If it could make sense for Many complex parsers, it goes in the way when elements are very simple to parse. Checking at each iteration indeed doesn't make sense for Int, but it could for a complex CSV line. We currently don't have a way to estimate some parser complexity (it is maybe possible to some extent!), so we can't provide some auto-adjustable solution without some kind of timing that will lose time itself.

So I think that the Cancellable combinator is the best route for now. Don't you think?

[tgrapperon]

Cancellable is probably not a good name, as it may let the user think that Cancellable>Many>Element is cancellable where they mean Many>Cancellable>Element in reality. I'll go with it in the meantime, but we should probably find something better if this combinator route is taken.