@jamiejennings i keep trying to put together a blog post about the similarities between the multi-scale transparent checksum approach for software packaging and your absolute tour de force formalizing backrefs into that really slick generalizable graph representation for rosie.

[i'm going to send you an email this weekend, so feel free to ignore this! :D]

no pressure to reply but i have an idea i really believe in

you mentioned offhand at one point that replacing text is absolutely something a text matching framework should support more fluently, and it took a while for that thought to bloom, but i've been doing a lot of work around filesystem reads vs other forms of IPC along with a very intense ring buffer, and i have an incredibly far-out proposal for how i'd like to design a text matching runtime (like a compiler backend that dispatches basic match operations). it wouldn't be encoding stuff like a DFA at all, and instead it would offer a form of IR to tools like rosie, predicated around establishing anchored match boundaries for literal string matches.

the goal of this work is to reduce dependency upon a monolithic central "engine" which merges frontend and backend concerns

in particular i see three fallacies with the monolithic "regex engine" model that would be fun to work on that i think could be aligned with rosie's goals:

1. coupling memory/locality expectations to the automaton model is extremely brittle. sometimes it results in expectations about memory allocation and blocking APIs, furthering regex pattern language ossification (especially if you just expect to iterate your opaque DFA until it fails). rosie of course is already way ahead of this, but this is something that junyer was really interested in brainstorming for what he called "re3".
   • having worked on build tools and performed this kind of i/o rework on the scala compiler i want to be clear that am imagining a system that would make this proposed "backend" layer into something more flexible for you the maintainer, not pulling any control away from you. "i/o is important" to me means making i/o more navigable to the user. but i don't really know your needs here at all yet, and "performance" is absolutely not the main goal here (see below =])

hypothesis: bidirectional merging is an extensible model with robust guarantees

1. one of hyperscan's achievements i was so envious of was how its callback API [i wrote these docs] managed to be the most flexible possible approach while retaining guarantees that users are intended to leverage. in particular, it was able to build PCRE support on top of its (extremely limited) low-level pattern language, because the callback API worked like a coroutine (and provides all match results) and managed its own data reading and queueing.

   • in particular, "you can totally run a search in the search callback" was really novel to me--it's the polar opposite of "don't parse HTML with regex".
   • i am not terribly interested in spending any time on complex SIMD mechanics like hyperscan. really my hypotheses here are:
     • bottom-up bidirectional expansion of sub-graphs should be an implementation detail
     • the "build up from seeds across the input" approach does not impose any difficulty in translation (i believe this approach forms a superset of functionality and does not lead to unintuitive behavior)
     • coroutine-based parallel matching can produce a simple API that enables users and the rosie compiler to expand functionality to arbitrary complexity without manually managing global parse state

2. i would have loved to build more on hyperscan itself, but its single callback API wasn't really built for e.g. nested expressions or user-driven parallelism. there's also a huge amount more rosie can do than hyperscan ever could, because it accepts the responsibility of being a real programming language.

performance features that other tools are limited from

(a) in particular, one thing that has always bugged me is learning from andrew gallant (rust regex) that a huge component of user-visible regex engine "performance" revolves around the "prefilter" operation (see e.g. my RE2 docs. but of course, the basic automaton model can only execute that once, before the search begins, because the DFA model can't handle something like merging two sub-matches into a graph/tree. in particular, something like "a.*b" should be able to match both parts of the text separately, with fast SIMD code that doesn't do anything complex.

(b) another thing that is so useful and very difficult for regex users to do themselves is support for non-contiguous searching (this is another of hyperscan's best features, but it really should be more common because this frequently leads to security bugs). "non-contiguous" is actually a very narrow way to consider the issue imho--if you reframe the problem to expand bidirectionally from match "seeds", you don't just get the ability to seek backwards, you also get reparsing after real-time modifications for free.

what this model was designed to solve

this capability isn't magic, it's just something you don't have to explicitly solve for when you design matching around the assumptions:

• parsing is about reconciling ambiguities in text input, so forward progress corresponds to absorbing more contiguous input tokens.

  • side note: this methodology has convinced me that the standard expectation of having a single top-level ("TOP") production is extremely artificial.
  • for programming languages with translation units and modules: makes sense! but enforcing that elsewhere encourages the user to think of parsing in terms of validation logic, not describing the data
    • ran into this with coffeescript after google added new semantics without documenting it https://github.com/jashkenas/coffeescript/pull/5474 unfortunately I haven't replaced jison yet

• greedy matching semantics (like POSIX alternations, or PEG ordered choice) actively subvert safe composition. non-contiguous matching as well as synchronously returning the first match makes the whole search process non-composeable

  • this precise bottom-up parsing and restartable logic was the part that worked immediately with the whole parser compiler i wrote.
  • the difficult part ended up being the frontend which performed three graph transformations to flatten the compile-time "stack diff" abstraction into a trie for the non-branching transitions and then statically analyzing the cyclic groups
    • and while the theoretical work is one of my proudest achievements, i feel the rosie project embodies everything i wanted out of my own parser compiler frontend and so much more
    • hence this proposal!

conclusion

• finite automaton models (or god forbid LALR) often fail to understand that their fear of "backtracking" reveals their discomfort with the inflexibility of their own internal semantics!

• i believe much of the reason this parallel coroutine approach hasn't been done is because it requires developing a internal protocol to communicate and retain consistency across nested sub-parse graphs, which is necessarily a different problem than the compiler front-end and mid-end (e.g. your backref graph model).

• i first envisioned this for two reasons:

  • FFI with other languages (hence mentioning buffering and i/o)
  • interop with IPC

• i really would like text matching tools to be able to interop together more, but that may be reaching a bit too far afield

  • i do think that decoupling input/output from match logic (so it can be managed separately is likely to be more directly useful for interop