How I fixed a bug in Atom

I'll admit and thought that by "fixed" he meant made it not start slow... but this was very well written and interesting. Great job Mr Galbraith!

I haven't worked on Atom or Electron apps (although it's on my todo list), but does the Chromium debugger not work inside them?

"How I fixed a bug in Atom that affected almost no one, and then spent quite a lot of time writing an article about it, then wrote a title that attempted to give me more credit than I deserved"

.. which is his main pass time if you see his other posts, rather than spending his effort on fixing bugs that actually affect a lot of people. I am sorry but I don't really appreciate it and have trouble getting over the misrepresentation in the title of the blog posts.

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.