how should I architect a project that maps between regex syntaxes? (should I target Ast or Hir in regex-syntax?)

[cosmicexplorer]

As per this issue comment (#962 (comment)):
I was looking through this repo to see whether anyone had translated from emacs regexp syntax using regex-syntax yet (my eventual goal is to produce an emacs native module). I'm pretty sure I could do that by transpiling the emacs regexp pattern string to a regex_syntax::ast::Ast, since the AST looks pretty simple, and emacs regexps don't have any special features: it pushes that to the language instead.

As mentioned by @db48x in #962 (comment), emacs provides a high-level rx sexp notation, but I think that actually aligns with @BurntSushi's framing of "using your programming language features to assemble the regex" from #962 (comment)! So I was hoping to demonstrate that regex-syntax makes that sort of thing possible without implementing that sort of higher-level abstraction itself directly (this is actually what makes it more generic/reusable)!

At first glance I think e.g. emacs-regexp-syntax can just be its own crate that depends on regex-syntax and generates a regex_syntax::ast::Ast, and I can propose upstreaming any extensions I need from the generic regex-syntax AST to this repo (although this seems unlikely to be necessary). I can then have another crate emacs-regexp which depends on regex-automata and exposes the emacs native module interface.

[BurntSushi]

Aye, just copying my answer here from #962 so that this can be marked as answered. :-) Feel free to edit your comment to remove the other copy hah.

---

@BurntSushi is that how you would suggest architecting this if I wanted to interface other regexp interfaces to regex-syntax and co?

Maybe? I've never done the exercise before, so I'm not sure. It's plausible the right target is regex-syntax::hir::Hir. Namely, an Hir is perhaps closer to what you might think of as a traditional AST where as an Ast is perhaps closer to a Concrete Syntax Tree. A concrete syntax tree essentially tries to describe the concrete syntax precisely so that it can be round-tripped. This makes it very detailed and possibly contains a lot of stuff you don't need to care about. (Regrettably, it isn't a true concrete syntax tree because of comments and whitespace in x mode. But it's close.)

Either target is reasonable IMO. With that said, if you need to deal with Unicode, then targeting the Ast potentially gives you some very big benefits. The Ast -> Hir conversion is what resolves things like [\p{Letter}&&\p{Greek}] into a single sequence of non-overlapping non-adjacent ranges of codepoints. That is a surprisingly non-trivial thing to do. If you only care about ASCII though, then you could feasibly target Hir without too much work.

[cosmicexplorer]

@junyer just pointed me to his analysis of an old proposal to adapt re2 to emacs regexps (google/re2#127 (comment)), which helpfully describes changes needed to support searching across emacs gap buffers (non-contiguous). I know non-contiguous/stream searching has long been high on your list of "would be awesome to have but would be a ton of work and hard to maintain", so this is another reason emacs semantics especially might be more difficult to support with regex-{syntax,automata} than other projects that are under 40 years old.

My parser composition framework would support non-contiguous input data in general, but it wouldn't be able to magically parse anything itself: the black-box parsers I would rely on would individually need to be able to support non-contiguous data. So that's another bit of functionality we might be able to eventually collaborate on and/or decouple into a shared crate (although that would probably be quite a large project to be clear, just another example is all).

[BurntSushi]

and delegate to regex, re2, etc for the parts of my grammar which have standard semantics and are easy to optimize, and thereby get the benefits of accelerated automatons/SIMD matching where possible without forcing the regex engine to support every single type of pattern/precondition itself.

One thing potentially worth mentioning here is that the SIMD optimizations in the regex crate (including the DFA's "accelerated" states) are primarily throughput optimizations. They aren't things that are likely to help with "parsing" tasks. They can, especially if there's a fast path for rejecting a match. But in general, I'd expect such optimizations to either be ineffectual or even lead to poorer performance on parsing tasks than if they didn't exist.

To be clear, I don't mean to say that this is a property of all SIMD code. But given how its used in regex and its overall architecture, they don't really help much with parsing. The SIMD is all about quickly finding the next candidate start position of a match. If the next candidate is always the next byte or a couple bytes away (as might be the case in a standard parsing task), then it doesn't really matter how fast you find that candidate.

Generally speaking, I think the kind of composition you're looking for might not work if performance is a goal. In my experience, performance and composition don't always go well together. Indeed, that's a big reason why regex-automata was so hard to build. Especially its API. The way I got around perf and composition not combining well is by coupling. For example, you can't use the lazy DFA in regex-automata with anything other than a regex-automata::nfa::thompson::NFA. They are coupled, but compositional, components. Introducing composition at an even higher level is a tough task.

[BurntSushi]

For streaming, @pascalkuthe is working on that! https://docs.rs/regex-cursor/latest/regex_cursor/

[cosmicexplorer]

are primarily throughput optimizations. They aren't things that are likely to help with "parsing" tasks

This is totally correct! Geoff Langdale also once described traditional "lexing" to me as extremely difficult to optimize because you essentially have to restart the matching after every token (this is related to the implicit assumption that token spans do not overlap). I'm taking a very abstract interpretation of "parsing" and my specific goal is to leverage throughput optimizations so that more complex types of string matching logic can be achieved in a safe and correct way while maintaining throughput!

We've previously discussed why the hyperscan callback API is interesting, and I wrote a small treatise in my docs for my rust wrapper lib on how the user callback is one (imperfect) way that hyperscan achieves throughput + user-defined match logic. I actually had been working on such a parser composition API for a while before ever looking into hyperscan, but didn't know of a good use case for it before I saw hyperscan's example recently and wrapped its API so I could understand its flaws.

[cosmicexplorer]

The SIMD is all about quickly finding the next candidate start position of a match

So the other reason I wanted to try this idea is because I realized that SIMD prefiltering e.g. for literal substrings is actually separate from most other regex logic, and I wanted to see if I could architect a regex engine with fast prefiltering but decoupled from the actual literal matching. I then also realized that "finding candidate match boundaries" is actually very similar to a particular mechanic I've already developed separately to parse non-contiguous data! So as a hypothesis I'm seeing if "a protocol for communicating half-match boundaries" is a genuinely useful organizing principle to efficiently implement prefiltering mechanisms at multiple scales of linguistic complexity/abstraction.