3 ms·

Sorry, by overhead I meant developer overhead. But I think me and you have had this conversation before, and we fundamentally disagree. Putting a limit on the

Sorry, by overhead I meant developer overhead. But I think me and you have had this conversation before, and we fundamentally disagree. Putting a limit on the regex engine won't fly. How big should that limit be? I use this particular regex engine to search files that are many GB in size. Some people might search bigger files. What should the limit be? Limits only work when you can restrict your use cases significantly, which is not a luxury I can enjoy. The broader point I was trying to make with my question is that "invalid states aren't represented" isn't particularly interesting to me on its own. What's interesting to me is what it takes to achieve it. i.e., What do I have to give up to make it so? Developer time? Performance? Code complexity? Other practical things? Keep in mind that I'm after things that work, and not a hypothetically advanced-enough tool.

lmm 10y ago
> Putting a limit on the regex engine won't fly. How big should that limit be? I use this particular regex engine to search files that are many GB in size. Some people might search bigger files. What should the limit be? Limits only work when you can restrict your use cases significantly, which is not a luxury I can enjoy. The limit just needs to be applied to backtracking (and other extended regex features that lead to turing completeness if there are any), not to input sizes or similar. I'm content to have a tool that errors if a given regex backtracks to the same point more than say 10000 times. I appreciate the principle of not restricting use cases, but in practice the overwhelming majority of the time that leads to the tool going into what's effectively a busy loop, which is not very user-friendly even if it's in some sense correct. (If I had control over the whole system I would say that perl-style extended regexes are fundamentally the wrong abstraction - the whole original point of regular expressions was that they were expressions for regular languages that were efficiently implementable, and the rare use cases that require turing-complete parsing/matching are better addressed through languages that are designed as turing-complete. But often in practice one doesn't have that freedom). > The broader point I was trying to make with my question is that "invalid states aren't represented" isn't particularly interesting to me on its own. What's interesting to me is what it takes to achieve it. i.e., What do I have to give up to make it so? Developer time? Performance? Code complexity? Other practical things? Keep in mind that I'm after things that work, and not a hypothetically advanced-enough tool. It's interesting in so far as it affects defect rates rather than in and of itself, sure. My sense is that it's natural to avoid this kind of problem in a language that encourages you to represent this kind of distinction, and that the shift of style shouldn't carry a cost beyond that. I mean in this example there was a big explanatory comment above the panic-ing line about why the unwraps were safe, which comes with its own cost (both for the initial developer and for anyone reading the code); to my mind expressing that comment in a type system rather than prose would not have been substantially more expensive, and would have caught the issue. But of course that's a lot to claim without a concrete implementation showing these advantages in practice; most of the experience I'm drawing on is unfortunately private, and skepticism is quite warranted.
- burntsushi 10y ago
  That's all pretty fair. Maybe we agree more than we disagree after all. 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.)
  - lmm 10y ago
    > 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.) 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?
    - burntsushi 10y ago
      > 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/regex-syntax-2/src/parse.rs#L408-L414 https://github.com/BurntSushi/regex/blob/syntax-rewrite/rege...

lmm 10y ago

> Putting a limit on the regex engine won't fly. How big should that limit be? I use this particular regex engine to search files that are many GB in size. Some people might search bigger files. What should the limit be? Limits only work when you can restrict your use cases significantly, which is not a luxury I can enjoy. The limit just needs to be applied to backtracking (and other extended regex features that lead to turing completeness if there are any), not to input sizes or similar. I'm content to have a tool that errors if a given regex backtracks to the same point more than say 10000 times. I appreciate the principle of not restricting use cases, but in practice the overwhelming majority of the time that leads to the tool going into what's effectively a busy loop, which is not very user-friendly even if it's in some sense correct. (If I had control over the whole system I would say that perl-style extended regexes are fundamentally the wrong abstraction - the whole original point of regular expressions was that they were expressions for regular languages that were efficiently implementable, and the rare use cases that require turing-complete parsing/matching are better addressed through languages that are designed as turing-complete. But often in practice one doesn't have that freedom). > The broader point I was trying to make with my question is that "invalid states aren't represented" isn't particularly interesting to me on its own. What's interesting to me is what it takes to achieve it. i.e., What do I have to give up to make it so? Developer time? Performance? Code complexity? Other practical things? Keep in mind that I'm after things that work, and not a hypothetically advanced-enough tool. It's interesting in so far as it affects defect rates rather than in and of itself, sure. My sense is that it's natural to avoid this kind of problem in a language that encourages you to represent this kind of distinction, and that the shift of style shouldn't carry a cost beyond that. I mean in this example there was a big explanatory comment above the panic-ing line about why the unwraps were safe, which comes with its own cost (both for the initial developer and for anyone reading the code); to my mind expressing that comment in a type system rather than prose would not have been substantially more expensive, and would have caught the issue. But of course that's a lot to claim without a concrete implementation showing these advantages in practice; most of the experience I'm drawing on is unfortunately private, and skepticism is quite warranted.

burntsushi 10y ago
That's all pretty fair. Maybe we agree more than we disagree after all. 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.)
- lmm 10y ago
  > 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.) 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?
  - burntsushi 10y ago
    > 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/regex-syntax-2/src/parse.rs#L408-L414 https://github.com/BurntSushi/regex/blob/syntax-rewrite/rege...