RangeError in some scenarios calling RegEx

[greim]

Example of the error:

/Users/foo/project/node_modules/mold-source-map/index.js:9
  var m = source.match(convert.commentRegex);
                 ^
RangeError: Maximum call stack size exceeded
    at String.match (native)
    at extractComment (/Users/foo/project/node_modules/mold-source-map/index.js:9:18)
    at new SourceMolder (/Users/foo/project/node_modules/mold-source-map/index.js:44:18)
    at exports.fromSource (/Users/foo/project/node_modules/mold-source-map/index.js:73:10)
    at Stream.end (/Users/foo/project/node_modules/mold-source-map/index.js:63:24)
    at _end (/Users/foo/project/node_modules/mold-source-map/node_modules/through/index.js:61:9)
    at Stream.stream.end (/Users/foo/project/node_modules/mold-source-map/node_modules/through/index.js:70:5)
    at Labeled.onend (/Users/foo/project/node_modules/browserify/node_modules/labeled-stream-splicer/node_modules/stream-splicer/node_modules/readable-stream/lib/_stream_readable.js:537:10)
    at Labeled.g (events.js:184:16)
    at Labeled.emit (events.js:119:20)

It doesn't seem like mold-source-map or its deps are doing anything wrong. Here's an isolated test case: thlorenz/mold-source-map#5 (comment)

It doesn't happen on node 0.12 or 0.11. I wondered if this was a difference in newer v8? Unfortunately ./source.js (noted in the linked code) is proprietary, but it's 125k lines long, trailed by a 6.5 million character long one-liner source map comment.

[benjamingr]

Parsing a regular expression causing a call stack exceeded error is definitely more likely a v8 bug. A quick peek at the v8 issue tracker doesn't show any bugs relating to that related You should file a bug against v8 - it definitely sounds like a regression they'll address.

[micnic]

I'm not sure but this may be triggered because convert-source-map is using the non-standard, deprecated Object.prototype.__defineGetter__() method in these lines: https://github.com/thlorenz/convert-source-map/blob/master/index.js#L131-L134 , I would try to replace it with Object.defineProperty() and check if the behavior of your test code is the same.

[benjamingr]

@micnic __defineGetter__ is used internally in v8, it's basically just a call to DefineOwnProperty with a created property descriptor as you can see here https://github.com/v8/v8/blob/8851bf83a938f79ab522b829261157396d9988aa/src/v8natives.js#L276-L289

This is pretty much also what Object.defineProperty does https://github.com/v8/v8/blob/8851bf83a938f79ab522b829261157396d9988aa/src/v8natives.js#L1170 (except for when proxies are involved but this is not the case here).

[micnic]

@benjamingr , you are right, then it's definitely a v8 issue.

@greim , it would be great if you could reproduce this bug with a smaller (and open) input for source.js and fill an issue in V8's issue tracker

[bnoordhuis]

As pointed out by others, this is essentially a V8 issue. I'm curious though, does passing --stack_size=4096 on the command line make a difference?

[greim]

Here's code that reproduces it for me:

var patt = /(?:\/\/|\/\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,((?:[A-Za-z0-9+\/]{4})*(?:[A-Za-z0-9+\/]{2}==|[A-Za-z0-9+\/]{3}=)?)(?:[ \t]*\*\/)?$/mg;
var source = '//# sourceMappingURL=data:application/json;base64,'
var len = 4473955
while (source.length < len){
  source += 'ICAgICAgICApXG4gICAgICAgIClcbiAgICAgIClcbi'
}
source = source.substring(0,len)
patt.test(source)

I narrowed it doen to len = 4473955. One number lower (4473954) wouldn't trigger the error. The weird thing is that this does seem to trigger range error in 0.11 and 0.12, so I'll need to work a bit more to figure out what the difference is; I might have some error in my reasoning or test code.

Error output:

$ node test.js
/Users/greim/deleteme/test.js:5
  source += 'ICAgICAgICApXG4gICAgICAgIClcbiAgICAgIClcbi'
          ^
RangeError: Maximum call stack size exceeded
    at RegExp.test (native)
    at Object.<anonymous> (/Users/greim/deleteme/test.js:8:6)
    at Module._compile (module.js:446:26)
    at Object.Module._extensions..js (module.js:464:10)
    at Module.load (module.js:341:32)
    at Function.Module._load (module.js:296:12)
    at Function.Module.runMain (module.js:487:10)
    at startup (node.js:111:16)
    at node.js:799:3

[edit] It's also strange that the above error output shows the += line as where the error occurred. Inserting log statements definitely shows it getting past that part.

[greim]

https://code.google.com/p/v8/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Type%20Status%20Priority%20Owner%20Summary%20HW%20OS%20Area%20Stars&groupby=&sort=&id=3878

[lidlanca]

@bnoordhuis

I tried --stack_size=4096 on a windows machine, from what I understand it has no affact on windows platform as the stack can not be changed programmatically beyond the default limits at linkage.

In visual studio, I added the /F 4096
https://msdn.microsoft.com/en-us/library/tdkhxaks.aspx

And I was able to run the replication code @greim provided without --stack_size=4096 in the command line. and no stack error.

[greim]

--stack_size=4096 doesn't make a difference for me.

I did notice that munging the regex ever so slightly in order to prevent a match makes the error go away. In other words changing this:

/(?:\/\/|\/\*)[@#][ \t]+sourceMappingURL=data:...

...to this:

/(?:\/\/|\/\*)[@#][ \t]+siurceMappingURL=data:...

(BTW I'm on OS X 10.10.2)

[lidlanca]

@greim

What is your system stack size limit.
I think you can check it with
ulimit -a

[targos]

The error also happens on Chrome. It is definitely a v8 issue.

[benjamingr]

@targos that settles it then. V8 has also accepted the bug.

[greim]

Stack size is 8192. In the v8 bug it was pointed out this is due to regex backtracking and isn't really a bug, although I think the error reporting could be a little clearer. In any case I'll close this later today unless someone disagrees or thinks there's a reason to keep it open. Or if someone else closes it that's fine.

[thlorenz]

This is definitely a regression since the exact same scenario works with nodes that use older v8 versions.

I'd like to introduce the v8 label for similar issues @mikeal but can't myself do so. This label will help the v8 team find issues they can help us with.

I feel we need to stay on top of these regressions as code that ran fine with previous node versions now suddenly and now suddenly doesn't work anymore is not going to benefit io.js adoption.

@beanieboi @targos are you going to stay on top of this bug and make sure that it gets solved in v8 and/or io.js users are aware of this issue until it gets fixed?

[lidlanca]

@thlorenz
The same code fail on node v0.10.34 for me.

As noted in the v8 issue tracker, this is as designed.
Increasing the irregexp stack size will allow linear growth of the source string(in the replication code).

//v8/src/regexp-stack.h
static const size_t kMaximumStackSize = 128 * MB;  //default 64

There are some inconsistencies between versions and sometimes the same process, more likely due to working on the limit of the stack dynamic allocation. and some external factors.

[thlorenz]

@lidlanca thanks for pointing that out, I wasn't aware.

According to the issue @greim filed on my module it did work with previous/other node versions.

only see this on io.js, not on node 0.11 or o.12

[greim]

The error I was originally seeing goes away with this slight modification to the regex:

var works = /^[ \t]*\/(?:\/|\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,(..*)$/mg
var fails = /^[ \t]*\/(?:\/|\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,(.+)$/mg

Anybody with strong regex foo know why the one would cause a RangeError but not the other?

[bnoordhuis]

Those regular expressions behave really strangely...

$ out/Release/iojs
> var works = /^[ \t]*\/(?:\/|\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,(..*)$/mg
undefined
> var fails = /^[ \t]*\/(?:\/|\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,(.+)$/mg
undefined
> var s = '//@ sourceMappingURL=data:text/json;base64,xyzzy'
undefined
> Array(11).join('.').split('').map(function() { return works.test(s) })
[ false, true, false, true, false, true, false, true, false, true ]
> Array(11).join('.').split('').map(function() { return fails.test(s) })
[ false, true, false, true, false, true, false, true, false, true ]

[targos]

@bnoordhuis it is apparently because of the g flag. Remove it and it will always return true. I don't understand why though...

Btw : Array(11).join('.') === '.'.repeat(10)

[benjamingr]

@targos regular expressions need a lot of backtracking to perform matches and a call stack size exceeded error should not be too surprising.

@greim this has nothing to do with being strong with regex - ..* and .+ are pretty much identical - the only difference is implementation detail in v8 that caused this regression.

This is pretty much all explained in the issue tracker issue which raises an interesting issue -@thlorenz what is the policy on v8 won't-fix issues?

[thlorenz]

what is the policy on v8 won't-fix issues?

I'm not the right person to ask as I honestly don't know.

[greim]

Also, I can't reproduce this particular error in isolation, using the same regex on the same string. Even if I fill most available memory with other stuff.

for (var i=0, amount=80000000, arr=Array(amount); i<amount; i++) arr[i] = i
var source = require('fs').readFileSync('./source.js', 'utf8')
source.match(/(?:\/\/|\/\*)[@#][ \t]+sourceMappingURL=data:(?:application|text)\/json;base64,(.+)$/mg)

Using a number much higher than 80000000 causes the process to fail due to out of memory, but never a RangeError.

Anyway, if this is just risk of doing business with v8 regex that's fine, I don't want to keep spamming this thread. Mainly wanted to rule out some bug in newer v8 that might make life hard for iojs adopters.

[greim]

@bnoordhuis @targos - Apparently regex with g are stateful in some sense. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/RegExp/lastIndex

[greim]

Update: As mentioned previously, I couldn't reproduce this in isolation; it would only occur during my gulp build.

Upon further investigation, commenting out some seemingly unrelated code in my gulp build which was using marked to process markdown, prevents the error. marked makes heavy use of regex. It's as if something in marked was changing the state of the regex engine.

Unfortunately I still can't reproduce in isolation, but I'm removing things from the gulp build to try to narrow it down.