Migrating parser from `pest` to `chumsky`

[gerau]

We will start rewriting the SimplicityHL parser, moving from pest to chumsky, as chumsky seems the most suitable parser for it.

This issue was created to discuss this change. Any suggestions, alternative proposals, or advice are welcome!

[gerau]

@canndrew / @uncomputable I would like to ask some questions:

• Is there a specific reason we are using NonZeroUsize inside error::Position, other than matching pest's 1-based indexing for lines and columns?
  Could we switch to a standard usize (and simply add the offset when displaying the error)? Alternatively, could we use raw byte offsets, since errors require the source text to render anyway?

• Could we avoid duplicating so many types between the parse and ast modules? Currently, the ast structs mirror the parse module almost exactly, with only a few differences in leaf nodes. Maybe we can somehow refactor it to reuse structs from parse module?

[uncomputable]

• The NonZeroUsize thing is just because of pest. I think we can completely switch to chumsky's position tracking code.
• The parse module contains types that represent the syntactic parse tree, while the ast module contains types that represent the more-semantic AST. From that perspective, code duplication seems inevitable. Maybe we can use generic types with instances for parse and for asm. What makes this approach hard is enums, which contain different variants for parse / asm.

[apoelstra]

Unsure if this is helpful at all but:

In rust-simplicity we have the Inner enum which is very generic and captures all of the "node types" used in the language. We've been reasonably successful de-deplicating code using this enum, though the resulting code is pretty generic-heavy and needs a whole ton of basically-the-same translation methods translate, map, translate_ref, etc. because Rust does not have any higher-kinded types that would let us abstract it.

The implementation of those methods is super repetitive but essentially our goal was to "put all the code duplication into inner.rs".

In rust-miniscript we have the same problem but can't switch to this sort of Inner construction because the node types themselves differ between our different structures (miniscripts, policiies, "semantic policies", parse trees) sometimes in quite small ways, but the result is that almost all of our logic winds up being almost-but-not-quite duplicated 3 times.

This sort of issue is inherent to Rust it seems.

[apoelstra]

Also bear in mind the tradeoffs here. Obviously we don't want duplicated code. But if we can move the duplication into short functions that are close to each other, the duplication is much less bad since differences will be visible.

If the duplication lets us avoid Rust macros (or elaborate build-system hacks to include a better macro system like cpp or php) that may also be the right choice because risking don't-repeat-yourself bugs might be better than risking can't-read-the-code-at-all bugs.

If the duplication lets us save a few days of engineering time, and we expect the parser to be either thrown away (with the duplication) or barely touched at all (so the duplication doesn't hurt much), that might also be better than spending time trying to improve it. Also bear in mind that with high likelihood you can spend multiple days trying to create better abstractions and then it just won't work at all because Rust sucks this way. (But okay, there's value in learning this..)