search

micromatch / braces

Faster brace expansion for node.js. Besides being faster, braces is not subject to DoS attacks like minimatch, is more accurate, and has more complete support for Bash 4.3.
https://github.com/jonschlinkert
MIT License
225 stars 62 forks source link

Refactor #10

Closed jonschlinkert closed 8 years ago

jonschlinkert commented 8 years ago

Complete overhaul, with parser and compiler, source map support, more accurate matching (passes all Bash 4.3 brace expansion tests, all minimatch braces tests, all brace-expansion tests, and even passes tests that bash fails... and it's fast https://github.com/jonschlinkert/braces/tree/refactor#latest-results.

Still working on readme/docs.

@doowb, @hemanth, @es128, @eush77 any feedback or review would be appreciated. I'll squash this beast when it's time to merge (@phated you are of course welcome to leave feedback as well)

closes https://github.com/jonschlinkert/braces/issues/8 closes https://github.com/jonschlinkert/braces/issues/9

doowb commented 8 years ago

I meant to comment earlier and got caught up with messing around with the tests...

I like the changes a lot. I like how the things like parsers and compilers are split into smaller pieces that makes it easier to reason about and make changes when necessary.

phated commented 8 years ago

@jonschlinkert I just read the README and this looks so awesome!

jonschlinkert commented 8 years ago

I just read the README and this looks so awesome!

thanks! that's great, I really appreciate it! I'm glad it's working out, I spent a ton of time on this refactor trying to get it right. @doowb helped a lot too. It was fun, we actually wrote out the compiler steps character by character for a bunch of brace patterns before we even wrote a single line of code in the actual compiler. Not something I get to do often lol

I'll try to write this quickly since my connection keeps going out (we've had thunderstorms for a couple of hours). the performance section captures the essence of what I meant when I said "as well as a couple of other reasons".

The first point is that there are many, many scenarios where brace patterns grow geometrically. If you define two brace patterns for example, they're multiplicative if not exponential. So even though those patterns in the readme are contrived, it's not uncommon for users to define brace patterns that result in similarly huge strings.

The second point is that there is potential for exploiting this effect in minimatch and the brace-expansion to cause a DoS (similar to the ReDoS bug minimatch had recently https://medium.com/node-security/minimatch-redos-vulnerability-590da24e6d3c#.jew0b6mpc).

Basically what I'm getting at is that, for the reasons mentioned on glob-parent alone there is enough benefit in doing the brace expansion first, before passing patterns to minimatch or node-glob. Then if we add the two reasons I just listed it seems like a no-brainer. IMHO, minimatch should remove brace expansion before it gets exploited, or someone should do a pr to the brace-expansion lib to add to-regex-range or something similar so that glob patterns can use it to avoid creating exponential patterns.

(lol quickly... well I tried)

edit: I just removed a partial sentence about bash/mac that didn't render because the code example wasn't escaped correctly. it didn't add to point anyway

jonschlinkert commented 8 years ago

K I'm going to bump this to 2.0 and publish so I can push up the micromatch refactor :)