6 ms·
First of all, this is why people should stop adding stupid features to regular expressions. A sane regular expression implementation has no pathological cases.
by cyphar 11y ago
First of all, this is why people should stop adding stupid features to regular expressions. A sane regular expression implementation has no pathological cases. DFA generation can be done in O(n^2) from memory (in the absolute worst case O(n) is average), and matching can't be worse than O(m) or similar (n is the size of the regex and m the size of the string). When you add features like back references and recursive matches, you bring the worst case complexity to O(a^n), which is exponential.
And why? So you could write some dirty hack rather than writing a simple recursive descent parser to create an AST of the code (which takes O(n)). What did you gain by ruining your regular expression implementation and writing shitty code?
EDIT: Matching might be O(m), but I'm wondering about maximally linked graphs with many epsilon edges. The conversion from DFA to NFA would require O(n^2) in that case. Implementing it as an NFA evaluation might be faster than full conversion, but then you run the risk of having O(n^2) dominating in the matching.
EDIT: The author is somewhat correct on what "catastrophic back referencing" is. While you could argue that it is due to bad implementations of the greedy matching, it's a more endemic problem of how you have to implement a regular expression engine that supports back references. If you have to support back references, then you will always have a class of pathological cases which cause exponential time complexity. I had a useful graph about this on my toy regular expression engine (which performs much better than Python's implementation even though it's written in Python and not C): https://github.com/cyphar/redone https://github.com/cyphar/redone.
- JetSetWilly 11y agoI don't always want to spend insane amounts of time writing full AST parsers. Sometimes it is a lot easier to write a simple, hacky, throwaway regex. It's a bit much to claim that backtracking regular expressions, a very useful tool sometimes, should never ever be used and everybody should waste loads of time writing careful code even in situations where it isn't required. The problem is not the tool. The problem is using the tool for the wrong job - although who knows, maybe if they didn't just chuck out a quick hacky implementation, then atom simply wouldn't have the feature at all - in which case it is a trade-off between having the feature at all and an evidently tiny corner case bug that was easily fixed by someone who isn't even a regular developer of the project. So I don't see the reason to be outraged or judgemental here.
- EGreg 11y agoI don't often write AST parsers but when I do, I don't and write regexps instead.
- jerf 11y ago"I don't always want to spend insane amounts of time writing full AST parsers." This is an effect of the language, not the problem space. Backtracking REs make it very easy to write bad code, and then most languages make writing the parsing code hard. If you're in a language that makes parsing code easier, like Haskell, then the tradeoff isn't anywhere near so bad. I don't mention Haskell just because it's the trendy thingy, I mention it because parser combinators really do make for some very easy parsers, and while parser combinators can exist in other languages they tend to be very syntactically heavyweight. Perl 6 is supposed to make parsing perhaps even easier, but I haven't played with it to know. Parsing isn't really that hard, it just plays very poorly with Algol-inspired syntax. To be clear, since this is the Internet and the presumption of disagreement is strong, this post is not an explanation of why you're wrong... it's an explanation of why you're right. It is absolutely a true statement that in most languages you're way better off bashing out a dangerous RE than writing a proper parser even for something as simple as this.
- rspeer 11y agoHaskell is, in fact, a really good way to write parser code. That's the main thing I use Haskell for. But how are you suggesting that Haskell could solve the problem of letting CoffeeScript plugins express which text they should apply to in a CoffeeScript text editor?
- paulddraper 11y agoHe's not suggesting that. He's suggesting that the correct solution (recursive descent parser) is not inherently hard, but CoffeeScript makes it hard enough that people reach for less good approaches.
- giovannibajo1 11y agoInteresting. Can you point to a piece of Haskell code that does some parsing of roughly the same level of complexity of that in the OP, so that we can compare how long it takes to write such a parser compared to a regex?
- wfunction 11y ago> The conversion from DFA to NFA [...] I believe you mean NFA to DFA. > [...] would require O(n^2) in that case I believe you mean O(2^n). https://en.wikipedia.org/wiki/Powerset_construction#Complexity https://en.wikipedia.org/wiki/Powerset_construction#Complexi...
- lorenzhs 11y agoFun with automata: Constructing the minimal DFA for a given NFA is PSPACE-hard. There are families of NFAs with n states so that the powerset automaton has 2^n states, but the minimal DFA has 1 state. Example: Let Σ={a,b} be the alphabet, Q={q1, ..., qn} be the states. q1 has a self-loop with both a and b and a transition to q2 with a. q2 to q(n-1) have transitions with a and b to the next state (q2 -> q3 etc). qn has no transitions. q1 and qn are the only accepting states. This is basically the "n-th-to-last letter was an a" automaton with the modification that the starting state is accepting.
- zamalek 11y ago> Constructing the minimal DFA for a given NFA is PSPACE-hard. This isn't really a problem if you incur that cost only once by having the regex compiled when the script is parsed. However, idiomatic JS usually includes regex literals in the closure where it is used - decreasing performance, code reuse and clarity. Why? Probably for the same reasons that regex is being used in the first place.
- lorenzhs 11y agoWell, PSPACE-hard is pretty damn hard, so this really depends on the size and complexity of your NFA ;) Of course most of the time you don't hit the pathological cases like the one I described above. My comment was not meant to provide a guideline on how to fix this, consider it a fun observation on automata theory.
- zamalek 11y agoIndeed. What I failed to communicate was that there is no reason to incur that cost multiple times per process/application. For some reason idiomatic JS encourages incurring that cost multiple times. Your comment shows that this idiomatic form is even more absurd than I originally thought.
- reacweb 11y agoThe support of fancy features like backtracking does not cause any degradation of performance for simple regular expressions. You are not obliged to use them, but they do not hurt you when you do not use them. Some other people may love them despite their poor complexity.
- thaumasiotes 11y agoActually, this is false. A lot of regex implementations use a backtracking approach in all cases, causing pathological behavior even on regexes which match a regular language (and so should never take any significant amount of time to process). See https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html, which gives a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (see the backtracking? me neither) as an example.
- reacweb 11y agoYou are right. The support of fancy features like backtracking should not cause any degradation of performance for simple regular expressions. You are not obliged to use them, but they should not hurt you when you do not use them. I am surprised this issue is not fixed in perl.
- lomnakkus 11y agoEDIT: Actually, nevermind. Does not matter in the grand scheme of things.
- mannykannot 11y ago> (see the backtracking? me neither) If I understand the article correctly, the Perl regex evaluator, if given a string consisting of only the minimum required number of 'a's, first matches them to the optional 'a's, and then has to backtrack to match the required 'a's.
- thaumasiotes 11y ago
- xixixao 11y agoBecause regular expressions such as that one can be applied line by line which becomes important for thousands of lines file and because you can adopt them more easily between languages: they are more loose. This is the reason why all text editors use them (IDEs can choose to use an AST).
- zamalek 11y agoI strongly doubt the AST would be needed. You could probably do this in a trivial loop state machine. It can't even be called laziness: that regex took time to work out - far longer than a switch-based state machine would have taken to write in the first place. Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this. [1]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- hencq 11y ago> Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this. It wouldn't have dealt with it right? NFAs and DFAs are equivalent and them being actually regular means they can't do things like count parentheses.
- zamalek 11y agoI miscommunicated the question: "how well would have a Thompson NFA have dealt with this?" I.e. How many magnitudes of order faster would it have been? If it was faster?
- joepvd 11y agoNFAs do not do backtracking. So the solution space would look different. More sane, and more performant, but it would not be a pure regex solution.
- pcwalton 11y agoYou don't need to throw out your favorite regex features—backreferences aren't stupid, they're useful and usually harmless! Rather, a good regex engine should start with recursive backtracking (ideally JIT'd) and fall back to the Thompson NFA if the regex supports it and the recursive backtracking approach is taking too long. Think of it like the adaptive sorting algorithms that switch between insertion sort and quicksort based on the size of the collection. This approach gives you the best of both worlds: speedy operation in the common cases in which recursive backtracking beats the Thompson NFA, all the regex features you know and love, and worst case polynomial running time for regexes that the Thompson NFA supports. I don't think it would have prevented this bug, though, because I don't think the Thompson NFA supports the recursive backreference thing that this regex uses.
- mwcampbell 11y agoDo you know if any major regex implementations use the adaptive approach you're suggesting?
- pcwalton 11y agoI don't know of any that can actually switch during regex execution, but TRE at least will choose Thompson NFA if it can and fall back to recursive backtracking if backreferences are used.