Ah, fair enough - I saw "extended" and assumed that meant backreferences and the like (which I think require backtracking?). If the search is guaranteed-linear-time in any case then why the requirement for a Turing-complete language?
Because suggestions of using Turing-incomplete languages seem somewhat uninteresting to me. To be honest, I have never used one in anger, but if you told me to go write a production grade regex engine in Agda and Coq, I'd say you're nuts. It sounds like a fine experiment to do given infinite time, but I want people to actually use what I build. And I have a very strong suspicion that using one of those languages would take me 10 times as long to write it, if it's even possible at all.
I try hard to blend the practical with the theory. I'm not aware of any Turing-incomplete language that comes close enough to the practical side of things. I hope that changes as PL research advances. :-)
For the most part, my problem with your initial comment on the matter is that it neglects everything except for the "type system could have stopped it" part. But in reality, there are a host of trade offs at play given the actual choices available to me. (Even if those trade offs may be fundamentally orthogonal to the notion of type safety, they still exist and they are still things I must confront.)
I feel like an Agda/Coq implementation would be dead in the water pretty quickly. How easy or hard is it to manipulate raw byte buffers in those languages? Or memory layout? That's why Rust is such a nice tool for a regex engine, because it gives you access to the hardware at the level of C without any fuss at all, while still remaining reasonably safe.
A long time ago, we had a discussion about ASTs and property based testing. I noted that my "AST" couldn't be round-tripped with the concrete syntax accurately, and you noted that it was therefore not an AST. I'm in the middle of making that happen, and I've tried a bit harder this time around to use the type system to avoid invalid states. I do still have one that I haven't been able to rule out though, which is related to an invariant on a sequence of operations applied to a stack: https://github.com/BurntSushi/regex/blob/syntax-rewrite/rege...
What if it took 3 times as long to write? I'm somewhat wildly guessing that would be unacceptable because from your perspective you don't see the benefits for it taking 3 times longer?
I'm interested in all the possible trade offs here, not just the type safety trade off. (That's why Rust is so appealing to me, because it nails a lot of my requirements while also giving a fairly high degree of safety.)
Idris is where my hopes would lie; while I've only played with it a little it doesn't feel like it takes a lot more work - indeed mostly it just behaves like Haskell[1].
> For the most part, my problem with your initial comment on the matter is that it neglects everything except for the "type system could have stopped it" part. But in reality, there are a host of trade offs at play given the actual choices available to me. (Even if those trade offs may be fundamentally orthogonal to the notion of type safety, they still exist and they are still things I must confront.)
Sure; I've got my own agenda/narrative and I'm talking about this bug because it aligns with that. (My belief that greater use of type systems is the best way forward for the industry is genuine and good-faith, but that doesn't mean I'm right)
> A long time ago, we had a discussion about ASTs and property based testing. I noted that my "AST" couldn't be round-tripped with the concrete syntax accurately, and you noted that it was therefore not an AST. I'm in the middle of making that happen, and I've tried a bit harder this time around to use the type system to avoid invalid states. I do still have one that I haven't been able to rule out though, which is related to an invariant on a sequence of operations applied to a stack: https://github.com/BurntSushi/regex/blob/syntax-rewrite/rege....
Glad to hear that.
The invariant comes from only ever adding alternations to the stack via push_or_add_alternation, right?
My first thought is to encapsulate the stack and the way alternations are added to / removed from it behind an opaque type. i.e. rather than Parser having direct access to the stack, it has a wrapped stack that it can push to (in a way that will always add alternations when necessary) and pop from (in a way that will provide it with the invariant - e.g. by returning an alternation-with-content or non-alternation). That doesn't offer any more proof, but practically it means the two halves of the invariant are in the same place and easier to review, and it's clear where the responsibility is.
Going further and looking to actually eliminate the unreachable, it seems like a stack with an alternation on top is treated differently both on push and pop (not just at the end but also in pop_group)?. Maybe those should be different types. Or maybe the representation isn't quite right - maybe it would be better for each alternate to be its own stack entry (i.e. the AST looks like Alternate(case1, Alternate(case2, Alternate(case3, ...))). That way seems like a better separation of concerns - on encountering a '|' you just push an entry onto the stack rather than having to push-or-mutate, and then when you know the alternation has finished (because you hit ')' or the end) you peek and pop all the alternations that are currently at the top (possibly zero, which I think should actually simplify pop_group because there are no longer two different cases). In turn that suggests a representation where AstGroup always contains AstAlternation (possibly of only one alternate) and the root value is always AstAlternation too.
I don't know whether that would work - maybe there're constraints I haven't thought of - but that's the kind of direction I'd be thinking in. Where there's a conditional, see if it can be moved into data (an enum or similar); where the representation has invalid states, look for a way to represent that avoids them. I think to a certain extent this awkwardness reflects a true awkwardness in the regex grammar - you can't tell whether what you're parsing is part of an alternation or not until you hit the | - but to the extent that it's possible to parse regexes it should be possible to come up with a representation that corresponds to what you do when parsing, and I feel like there's a correspondence/duality between operator precedence and deciding that the children of a certain node must be a particular type of node (e.g. if we wanted to parse arithmetic expressions consisting of +, *, () and variables/literals, we could say that both arguments to + are products (possibly of 1 element)).
[1] Including at runtime; if you're looking to write a library that can be embedded into other languages then Rust is indeed probably still your best option. One of my very long-term projects is to extend Rust (or a Rust-like language) with Noether-like functionality, but that's purely theoretical at this point.
Also, FWIW, Rust's regex engine guarantees linear time search. (Interestingly, it may decide to use backtracking to resolve the search, but it's only an optimization. And the backtracking is always bounded so that it never revisits the same state on the same input byte.)