Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How I fixed a bug in Atom

davidvgalbraith.com

Post reply on HN
Print view View original

71–80 of 189 posts

Re: How I fixed a bug in Atom

#71

Post by jeffbr13 »

Isn't arbitrarily-long nesting or matching any sort of palindrome, where you count up and down, the classic case of something you should never do with a regex, because they're finite automata?

People don't build parsers because of masochism, but because regular expressions are provably insufficient to capture things like nesting. You need to go at least one level up on the Chomsky hierarchy[1] to pushdown automata for that.

More importantly, shouldn't SOMEBODY working on a text editor know and recognise this sort of thing? I'm all for the hacker mentality of shipping, reducing developer time instead of machine time, using what you know, but this is the sort of hacky fix that just pushes the problem further down the line.

Great write-up though, very enjoyable read!

Re: How I fixed a bug in Atom

#73

Post by clay_to_n »

I liked this article a lot. A programmer found a bug in something he uses every day, and learned enough to fix it.

I think articles like this are very useful to beginner/intermediate developers. Everyone in software says "write open source code", "make pull requests to code you use" etc, but there's a very big gap between knowing how to program and knowing how to track down, fix, and submit a PR for a bug in a program (and language!) you've never worked on before.

This is a good little tutorial on ways to attack a bug in a program. I especially like that he starts with two print statements - there's no wizardry here, just a programmer digging into a bug.

Re: How I fixed a bug in Atom

#74

Post by Klathmon »

lucaspiller wrote: post #6

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?

Yes it does, and that was my biggest annoyance with this article.

The chrome debugger with breakpoints, profilers, and a whole slew of other goodies is great for this sort of debugging.

Yeah, sometimes i need to avoid it because turning it on can actually slow the code down significantly, but the profiler would have been perfect to see where the time was spent here with just a few clicks.

Re: How I fixed a bug in Atom

#75

Post by reacweb »

thaumasiotes wrote: post #35
reacweb wrote: post #27

Earlier quoted context omitted.

The 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.

Actually, 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 , 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?…

You 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.

Re: How I fixed a bug in Atom

#76

Post by zamalek »

lorenzhs wrote: post #52
wfunction wrote: post #20

Earlier quoted context omitted.

> 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#Complexi...

Fun 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 ha…

> 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.

Re: How I fixed a bug in Atom

#78

Post by Matthias247 »

boulos wrote: post #11

I got to the bottom and couldn't believe that the solution chosen was to modify the regexp instead of use a for loop. He did such a great job explaining that the code is really just trying to count the number of parentheses or braces to see if they're imbalanced, that it felt the next step was "so I wrote a really simple set of loops that is fast enough on short strings and way less crazy otherwise".

I think the reason is that all actual JS code is in Atom core and not in this Golang plugin, which inherited the whole indentation and syntax highlighting stuff from textmate and sublime. You can't change the code there without making all language plugins (which can only use regexes) break.

Re: How I fixed a bug in Atom

#79

Post by Lazare »

anotheryou wrote: post #59
Lazare wrote: post #45

Earlier quoted context omitted.

Sometimes I feel like the difference between a junior, intermediate, and senior developers is that the junior hasn't yet figured out how to use regexps, the intermediate dev has, and the senior dev has figured out not to. I kid, but...really. The number of times I've seen people burnt by non-trivial regexps in production code is absurd. "Oh, I need to mangle this CSV that's in the wrong format"? Sure, write a one-off…

out of curiosity: what would you use for the URL validation? (but i get this is difficult: https://gist.github.com/dperini/729294 )

The general rule is that any tricky security code should have as many eyeballs on it as possible, so I'd probably start by seeing if my framework had solid support for this, or failing that, see what popular libraries for my platform exist.

In this particular case, the Google Caja project[1] is a good starting place for most HTML/JS/CSS sanitization needs (although the project has a much larger scope than just that); and I think the 'sanitizer' package on npm is a fairly popular wrapper/port of it's basic sanitizing code, and I believe ruby/php/python have their own but I couldn't name them offhand. But it would depend on the exact attack vector you're trying to stop, eg, XSS, remote shell via filename params, etc.

If I had to write it myself, I'd probably go for something as braindead as possible; probably a bunch of nested loops backed by some thorough tests. Regexps are great for magic one liners, but magic one liners are antithetical to good security.

[1]: https://developers.google.com/caja/

Re: How I fixed a bug in Atom

#80

Post by mbrock »

Lazare wrote: post #45
viraptor wrote: post #17

Earlier quoted context omitted.

Same here. Also, I don't use Atom, but looking at the expression I'm pretty sure it fails to account for strings with parentheses. The way the matching is done, it looks like it will happily count: func("some call :)") as extra closing paren. (regex101 agrees)

Sometimes I feel like the difference between a junior, intermediate, and senior developers is that the junior hasn't yet figured out how to use regexps, the intermediate dev has, and the senior dev has figured out not to. I kid, but...really. The number of times I've seen people burnt by non-trivial regexps in production code is absurd. "Oh, I need to mangle this CSV that's in the wrong format"? Sure, write a one-off…

The famous "Gruber URL regexp", before an update in 2014, would run in exponential time given some URLs that contained parens.

I noticed this when a web app I worked on froze on certain pages. Runaway regexp matching is one of the easiest ways to really lock a JavaScript thread.

Post reply on HN