Tagged Failures

[j-mie6]

Maidl et al. describe an error system where all failures are given a label or tag, and all <|> operations are also given a tag. An error thrown with tag t can only be caught by an <|> with tag t. This allows them to implement atomic as just a special case of <|>, such that an error after input consumption is tagged as Fatal, and atomic can turn a Fatal into a Fail. This is an interesting system, but has the downside that all <|>s will retain references to the input: in the current system, only those that can rollback consumed input need to do this, namely atomic and notFollowedBy. This makes the system ill-suited for use in parsley, as it will introduce space leaks, especially when #132 is completed.

However, the idea of error tagging is still interesting: suppose instead that all failure handling combinators are tag-aware, with some base tag as the default. Then this would allow for error handling to fallback multiple levels in a user-directed way. One interesting example is the range or count combinators: they cannot provide step behaviour such that if the parser p fails with input consumption, the whole combinator fails, but if only one copy was parsed and not two it backtracks. This is just not possible with the current system, because there is no way of distinguishing between the two failures. Instead, the combinators could have their own labels that can be referentially matched to only atomic if the underlying parser itself was not the source of the failure. Another is being able to through entirely unrecoverable fatal errors (with the exception of combinators introduced by #139, which would need to be able to catch Fatal errors, as well as regular ones, a user could define a SuperFatal, I suppose).

If this system were to be implemented, it seems like it is possible to do so in a way that is entirely backwards compatible, so no issues there. However, it would be good to be able to improve failure performance for tagged fails such that parsers can automatically drop back multiple-levels in a single step, since this would allow for fail-fast semantics for Fatal. It seems like it would be possible to support this system with minimal performance hit by just requiring handlers to rewind all the way, but this also does not come with performance advantages. The question is how can failure recovery jump directly to the correct handler, and clear all of the others on the stack in one go (or at least quickly); the next question is how might this be done without creating space-leaks or other tension within the system.