11 ms·

A New RegExp Engine in SpiderMonkey

156 points by simonpure 6y ago

sam_goody 6y ago
Nice to see the V8 and FF team working together. And preventing FF from falling behind on features is good. On the other hand, the more dependent Mozilla is on the Chromium base, the more power it gives Google (even if at this point Google already acts like they own the internet and do things that break in FF at will).
- ldeangelis 6y ago
  I agree, but in the article, it was mentioned that the V8 team already wanted to make their RegExp engine more independent. Also, since Mozilla runs of limited resources, it's great that they will have less maintenance to do in the future.
  - nerdponx 6y ago
    Hopefully we start seeing more "modularized" browser components. It's a huge detriment IMO that we are stuck with 3-4 (depending on who you ask) monolithic browser engines.
    - LockAndLol 6y ago
      I honestly don't understand why Mozilla went the route of a monolithic and firefox-only browser engine. They had a lead before Chrome showed up and refused to cater to devs. Now they're paying for it and so is everybody else.
The_rationalist 6y ago
It's a move in the right direction but seriously this is so much wasted human resources! Humanity would benefit from a faster, more featureful and less buggy js engine. Mozilla should use V8 and backport its spidermonkey innovations/optimisations to V8 where applicable. Open source is all about collaboration and this code redundancy is a historic accident. If you think the contrary, beware to double standards! Would rust or go benefit from totally redundant implementations? I'm aware of cranelift or of the various go backends. But while in theory those languages have multiple implementations, they do no harm as 99% of the devs are working on the official implementation. Now take half rustc devs and move them to another redundant compiler implementation. You've slowed down progress far too much, criminally even I would say.
- jfk13 6y ago
  How do you feel about the existence of both gcc and clang, I wonder?
  - The_rationalist 6y ago
    Mostly the same. An accident for a licensing philosophy difference. Wow LLVM brought modularity but I bet that if 5% of the human resources that got into llvm got into modularising GCC the issue would have been fixed. GCC nowadays is getting modular. After all this years GCC is still faster on average and llvm is getting slower after each release or at best do not progress.
    - cletus 6y ago
      Yeah, this is an attitude I come across at work a lot. A lot of pointless work is justified as "unifying" several projects. Of course, a nod to the xkcd on Standards [1]. This is why we end up with monocultures (eg in agriculture), which all works great... until it doesn't (RIP Cavendish; say hello to Gros Michel). Even in a large organization multiple projects that ostensibly do the same thing can be good. They can have different strengths and weaknesses and work from different design decisions and philosophies. Then the "market" (often the rest of the company) can decide which to use. This often produces much better results than simply anointing a winner. Anointing winners rewards politics rather than the technical. Of course this can go too far but so can anything. There can be too many competing products. That tends to highlight a problem with your organization's incentives structure (eg heaping rewards on new projects rather than maintaining things). Competition can also be toxic. You may think it's a waste to have both clang and gcc. I couldn't disagree more. I think the existence of clang has inarguably made gcc better. Would gcc have gotten more modular in the absence of clang? Maybe... but maybe not. I'll leave you with this quote: "A foolish consistency is the hobgoblin of simple minds." [1]: https://xkcd.com/927/ https://xkcd.com/927/
      - blacksmith_tb 6y ago
        Actually that's "little minds"[1] but close enough? 1: https://en.wikiquote.org/wiki/Ralph_Waldo_Emerson#Self-Reliance https://en.wikiquote.org/wiki/Ralph_Waldo_Emerson#Self-Relia...
tannhaeuser 6y ago
I thought Mozilla wanted to rewrite their browser in Rust didn't they?
- VWWHFSfQ 6y ago
  one step at a time. they're not trying to repeat the netscape -> firefox mistake
- sstangl 6y ago
  JIT engines like this one don't receive much benefit from being rewritten in a memory-safe language. Errors typically occur in the generated machine code, not in the compiler itself. The benefit would be small.
  - tannhaeuser 6y ago
    That's exactly the point I wanted to make (but failed to) a couple months ago [1] - that for the (few) tasks you'd use C for (such as writing language runtimes) Rust might not be a good fit. If it isn't a good fit for regexp, it might not be a good fit for JavaScript either. [1]: https://news.ycombinator.com/item?id=22661930 https://news.ycombinator.com/item?id=22661930
    - JoshMcguigan 6y ago
      It’s not that rust wasn’t a good fit. It’s that writing a regex engine from scratch in rust to be integrated into their c++ code base wasn’t the right choice for them when compared against integrating an existing c++ solution.
  - monocasa 6y ago
    There's more benefits to Rust than just it's memory safety. It being a non-GCed language with ADTs is a big one, and that's been nice for the couple JITs I've written in Rust. And the partial memory safety over the metadata around the actual JITed code is a big win as well. Yes, Rust doesn't get you there 100%, but IMO it gets you closer than C or C++.
wereHamster 6y ago
[regexp] Remove trivial assertion The assertion in BytecodeSequenceNode::ArgumentMapping cannot fail, because size_t is an unsigned type. This triggered static analysis warnings in SpiderMonkey. Does that mean Chromium doesn't use any static analysis tool? Or one that does not work for this trivial assertion?
- wahern 6y ago
  > Or one that does not work for this trivial assertion? Or one that does work for this trivial assertion, which is to say not emit a diagnostic. What ends up happening in a situation like this is that somebody removes the assertion to quiet the compiler diagnostic. Then the types change and all of a sudden it can fail, but the assertion is gone. You might say, "well, now that one of the operands is size_t how could the types ever change to reintroduce an issue?" That's the wrong question to ask. The whole point of the assertion is to avoid having to answer such a tricky question, or at least to encode your answer in a way that if the unforeseen happens things break loudly instead of silently. Anyhow, you'd be surprised by how things can break. I personally religiously use size_t for anything related to object size, but many other developers don't (including at Google and Mozilla), and so you often see a mix of, e.g., size_t and uint64_t, size_t and uint32_t, size_t and int, etc, and regular tweaks back-and-forth, which can easily introduce regressions. I understand why compilers emit a warning--the idea is that if the assertion couldn't possibly be false, maybe it has a bug. But, IME, the opposite is usually true--it's well-written and deliberate, because the developer is trying to catch spooky action at a distance where the type, which is defined far away, is changed, accidentally or intentionally. I don't know where to draw the line in terms of second-guessing the code to help catch bugs, but GCC and clang need to provide far more succinct constructs to tell the compiler to shut up. Currently you're stuck with inline pragmas, __extension__, statement expressions, and other weird convolutions that require far more code than the assertion or operation itself. The issue makes writing arithmetic overflow-safe code more tedious and error prone. (Other languages simply prohibit mixing integer operands of different types, so if a type is changed far away then code will break loudly even without any assertions. But in codebases like SpiderMonkey and V8 that use a wide range of integer types for space and performance optimizations, that tends to encourage casting, which has the exact same problems.)
29athrowaway 6y ago
Regular expressions come from this paper, "Representation of events in nerve nets and finite automata" by Stephen Cole Kleene. https://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf https://www.rand.org/content/dam/rand/pubs/research_memorand... It's incredible that biology served as inspiration for this.
ridiculous_fish 6y ago
I wrote the JavaScript regex engine in Hermes [1], and also regress in Rust. I want to explain what's sucky about this decision, but first some ES regexp background. The regexp grammar portion of the ES spec is different, in that it's not sufficient. You can implement JavaScript from the ES spec, but NOT regexp. The grammar doesn't really make sense [2]. The Chakra team found the same thing [3]. I have not confirmed this but I have been told the regexp portion is tightly controlled by Google, more than most parts of the spec. When v8's regexp implementation is found to deviate from the spec, the spec gets changed. This makes sense (why risk breaking websites), but it illustrates how little weight the regexp spec actually has. With Firefox using irregexp, it further cements this unfortunate reality. 1: https://hermesengine.dev https://hermesengine.dev 2: Example: the NonemptyClassRangesNoDash production may include a dash 3: https://docs.microsoft.com/en-us/archive/blogs/ie/chakra-interoperability-means-more-than-just-standards#whats-the-real-regular-expression-grammar https://docs.microsoft.com/en-us/archive/blogs/ie/chakra-int...
- magicalist 6y ago
  > You can implement JavaScript from the ES spec, but NOT regexp. The grammar doesn't really make sense [2]. The Chakra team found the same thing [3]. I haven't tried to implement the RegExp section, so I can't speak to that, but this is largely why we have Test262[1]. Also that Chakra blogpost is from 10 years ago, talking about ES5. Things have improved considerably since then, though of course we have to live with historical baggage. > With Firefox using irregexp, it further cements this unfortunate reality. Is this a specific unfortunate reality? I don't spot any RegExp entry in the last spec Incompatibilities section[2] that seems like a bad change or even having to do with regex grammar at all. [1] https://github.com/tc39/test262/tree/master/test/built-ins/RegExp https://github.com/tc39/test262/tree/master/test/built-ins/R... [2] https://www.ecma-international.org/ecma-262/#sec-additions-and-changes-that-introduce-incompatibilities-with-prior-editions https://www.ecma-international.org/ecma-262/#sec-additions-a...
  - ridiculous_fish 6y ago
    Yes, thank goodness for Test262. One implements JS-compliant regexps by doing the natural thing, and then making Test262 pass. Some things have indeed improved. The 'u' flag introduced in ES6 provides a much cleaner grammar for example. However the process is still busted. Here is a concrete example. /{1}/ is permitted by the ES6 spec (including Annex B). But in practice, "web browsers" rejected it. Rather than fixing the browsers, the spec was changed in ES8 to reflect "web-reality". https://github.com/tc39/ecma262/pull/303 https://github.com/tc39/ecma262/pull/303 Browsers could have become ES6 compliant here, with zero compatibility risk. But when there is non-compliance, it is the spec that moves.
jedisct1 6y ago
Slightly related question: does a RegExp engine in pure JavaScript exist?
- ridiculous_fish 6y ago
  Yes! RegExp Tree, by Dmitry Soshnikov (who is extremely awesome). https://github.com/DmitrySoshnikov/regexp-tree https://github.com/DmitrySoshnikov/regexp-tree A fun bug I found in it: https://github.com/DmitrySoshnikov/regexp-tree/issues/69 https://github.com/DmitrySoshnikov/regexp-tree/issues/69

156 points by simonpure 6y ago

Nice to see the V8 and FF team working together. And preventing FF from falling behind on features is good. On the other hand, the more dependent Mozilla is on the Chromium base, the more power it gives Google (even if at this point Google already acts like they own the internet and do things that break in FF at will).

ldeangelis 6y ago
I agree, but in the article, it was mentioned that the V8 team already wanted to make their RegExp engine more independent. Also, since Mozilla runs of limited resources, it's great that they will have less maintenance to do in the future.
- nerdponx 6y ago
  Hopefully we start seeing more "modularized" browser components. It's a huge detriment IMO that we are stuck with 3-4 (depending on who you ask) monolithic browser engines.
  - LockAndLol 6y ago
    I honestly don't understand why Mozilla went the route of a monolithic and firefox-only browser engine. They had a lead before Chrome showed up and refused to cater to devs. Now they're paying for it and so is everybody else.

The_rationalist 6y ago

It's a move in the right direction but seriously this is so much wasted human resources! Humanity would benefit from a faster, more featureful and less buggy js engine. Mozilla should use V8 and backport its spidermonkey innovations/optimisations to V8 where applicable. Open source is all about collaboration and this code redundancy is a historic accident. If you think the contrary, beware to double standards! Would rust or go benefit from totally redundant implementations? I'm aware of cranelift or of the various go backends. But while in theory those languages have multiple implementations, they do no harm as 99% of the devs are working on the official implementation. Now take half rustc devs and move them to another redundant compiler implementation. You've slowed down progress far too much, criminally even I would say.

jfk13 6y ago
How do you feel about the existence of both gcc and clang, I wonder?
- The_rationalist 6y ago
  Mostly the same. An accident for a licensing philosophy difference. Wow LLVM brought modularity but I bet that if 5% of the human resources that got into llvm got into modularising GCC the issue would have been fixed. GCC nowadays is getting modular. After all this years GCC is still faster on average and llvm is getting slower after each release or at best do not progress.
  - cletus 6y ago
    Yeah, this is an attitude I come across at work a lot. A lot of pointless work is justified as "unifying" several projects. Of course, a nod to the xkcd on Standards [1]. This is why we end up with monocultures (eg in agriculture), which all works great... until it doesn't (RIP Cavendish; say hello to Gros Michel). Even in a large organization multiple projects that ostensibly do the same thing can be good. They can have different strengths and weaknesses and work from different design decisions and philosophies. Then the "market" (often the rest of the company) can decide which to use. This often produces much better results than simply anointing a winner. Anointing winners rewards politics rather than the technical. Of course this can go too far but so can anything. There can be too many competing products. That tends to highlight a problem with your organization's incentives structure (eg heaping rewards on new projects rather than maintaining things). Competition can also be toxic. You may think it's a waste to have both clang and gcc. I couldn't disagree more. I think the existence of clang has inarguably made gcc better. Would gcc have gotten more modular in the absence of clang? Maybe... but maybe not. I'll leave you with this quote: "A foolish consistency is the hobgoblin of simple minds." [1]: https://xkcd.com/927/ https://xkcd.com/927/
    - blacksmith_tb 6y ago
      Actually that's "little minds"[1] but close enough? 1: https://en.wikiquote.org/wiki/Ralph_Waldo_Emerson#Self-Reliance https://en.wikiquote.org/wiki/Ralph_Waldo_Emerson#Self-Relia...

tannhaeuser 6y ago

I thought Mozilla wanted to rewrite their browser in Rust didn't they?

VWWHFSfQ 6y ago
one step at a time. they're not trying to repeat the netscape -> firefox mistake
sstangl 6y ago
JIT engines like this one don't receive much benefit from being rewritten in a memory-safe language. Errors typically occur in the generated machine code, not in the compiler itself. The benefit would be small.
- tannhaeuser 6y ago
  That's exactly the point I wanted to make (but failed to) a couple months ago [1] - that for the (few) tasks you'd use C for (such as writing language runtimes) Rust might not be a good fit. If it isn't a good fit for regexp, it might not be a good fit for JavaScript either. [1]: https://news.ycombinator.com/item?id=22661930 https://news.ycombinator.com/item?id=22661930
  - JoshMcguigan 6y ago
    It’s not that rust wasn’t a good fit. It’s that writing a regex engine from scratch in rust to be integrated into their c++ code base wasn’t the right choice for them when compared against integrating an existing c++ solution.
- monocasa 6y ago
  There's more benefits to Rust than just it's memory safety. It being a non-GCed language with ADTs is a big one, and that's been nice for the couple JITs I've written in Rust. And the partial memory safety over the metadata around the actual JITed code is a big win as well. Yes, Rust doesn't get you there 100%, but IMO it gets you closer than C or C++.

wereHamster 6y ago

[regexp] Remove trivial assertion The assertion in BytecodeSequenceNode::ArgumentMapping cannot fail, because size_t is an unsigned type. This triggered static analysis warnings in SpiderMonkey. Does that mean Chromium doesn't use any static analysis tool? Or one that does not work for this trivial assertion?

wahern 6y ago
> Or one that does not work for this trivial assertion? Or one that does work for this trivial assertion, which is to say not emit a diagnostic. What ends up happening in a situation like this is that somebody removes the assertion to quiet the compiler diagnostic. Then the types change and all of a sudden it can fail, but the assertion is gone. You might say, "well, now that one of the operands is size_t how could the types ever change to reintroduce an issue?" That's the wrong question to ask. The whole point of the assertion is to avoid having to answer such a tricky question, or at least to encode your answer in a way that if the unforeseen happens things break loudly instead of silently. Anyhow, you'd be surprised by how things can break. I personally religiously use size_t for anything related to object size, but many other developers don't (including at Google and Mozilla), and so you often see a mix of, e.g., size_t and uint64_t, size_t and uint32_t, size_t and int, etc, and regular tweaks back-and-forth, which can easily introduce regressions. I understand why compilers emit a warning--the idea is that if the assertion couldn't possibly be false, maybe it has a bug. But, IME, the opposite is usually true--it's well-written and deliberate, because the developer is trying to catch spooky action at a distance where the type, which is defined far away, is changed, accidentally or intentionally. I don't know where to draw the line in terms of second-guessing the code to help catch bugs, but GCC and clang need to provide far more succinct constructs to tell the compiler to shut up. Currently you're stuck with inline pragmas, __extension__, statement expressions, and other weird convolutions that require far more code than the assertion or operation itself. The issue makes writing arithmetic overflow-safe code more tedious and error prone. (Other languages simply prohibit mixing integer operands of different types, so if a type is changed far away then code will break loudly even without any assertions. But in codebases like SpiderMonkey and V8 that use a wide range of integer types for space and performance optimizations, that tends to encourage casting, which has the exact same problems.)

29athrowaway 6y ago

Regular expressions come from this paper, "Representation of events in nerve nets and finite automata" by Stephen Cole Kleene. https://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf https://www.rand.org/content/dam/rand/pubs/research_memorand... It's incredible that biology served as inspiration for this.

ridiculous_fish 6y ago

I wrote the JavaScript regex engine in Hermes [1], and also regress in Rust. I want to explain what's sucky about this decision, but first some ES regexp background. The regexp grammar portion of the ES spec is different, in that it's not sufficient. You can implement JavaScript from the ES spec, but NOT regexp. The grammar doesn't really make sense [2]. The Chakra team found the same thing [3]. I have not confirmed this but I have been told the regexp portion is tightly controlled by Google, more than most parts of the spec. When v8's regexp implementation is found to deviate from the spec, the spec gets changed. This makes sense (why risk breaking websites), but it illustrates how little weight the regexp spec actually has. With Firefox using irregexp, it further cements this unfortunate reality. 1: https://hermesengine.dev https://hermesengine.dev 2: Example: the NonemptyClassRangesNoDash production may include a dash 3: https://docs.microsoft.com/en-us/archive/blogs/ie/chakra-interoperability-means-more-than-just-standards#whats-the-real-regular-expression-grammar https://docs.microsoft.com/en-us/archive/blogs/ie/chakra-int...

magicalist 6y ago
> You can implement JavaScript from the ES spec, but NOT regexp. The grammar doesn't really make sense [2]. The Chakra team found the same thing [3]. I haven't tried to implement the RegExp section, so I can't speak to that, but this is largely why we have Test262[1]. Also that Chakra blogpost is from 10 years ago, talking about ES5. Things have improved considerably since then, though of course we have to live with historical baggage. > With Firefox using irregexp, it further cements this unfortunate reality. Is this a specific unfortunate reality? I don't spot any RegExp entry in the last spec Incompatibilities section[2] that seems like a bad change or even having to do with regex grammar at all. [1] https://github.com/tc39/test262/tree/master/test/built-ins/RegExp https://github.com/tc39/test262/tree/master/test/built-ins/R... [2] https://www.ecma-international.org/ecma-262/#sec-additions-and-changes-that-introduce-incompatibilities-with-prior-editions https://www.ecma-international.org/ecma-262/#sec-additions-a...
- ridiculous_fish 6y ago
  Yes, thank goodness for Test262. One implements JS-compliant regexps by doing the natural thing, and then making Test262 pass. Some things have indeed improved. The 'u' flag introduced in ES6 provides a much cleaner grammar for example. However the process is still busted. Here is a concrete example. /{1}/ is permitted by the ES6 spec (including Annex B). But in practice, "web browsers" rejected it. Rather than fixing the browsers, the spec was changed in ES8 to reflect "web-reality". https://github.com/tc39/ecma262/pull/303 https://github.com/tc39/ecma262/pull/303 Browsers could have become ES6 compliant here, with zero compatibility risk. But when there is non-compliance, it is the spec that moves.

jedisct1 6y ago

Slightly related question: does a RegExp engine in pure JavaScript exist?

ridiculous_fish 6y ago
Yes! RegExp Tree, by Dmitry Soshnikov (who is extremely awesome). https://github.com/DmitrySoshnikov/regexp-tree https://github.com/DmitrySoshnikov/regexp-tree A fun bug I found in it: https://github.com/DmitrySoshnikov/regexp-tree/issues/69 https://github.com/DmitrySoshnikov/regexp-tree/issues/69