Bug 158011 – [JSC] RegExp with deeply nested subexpressions overflow the stack in Yarr

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Benjamin Poulain]

[JSC] RegExp with deeply nested subexpressions overflow the stack in Yarr

[Benjamin Poulain]

Created attachment 279622 [details]
Patch

[Alex Christensen]

Comment on attachment 279622 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=279622&action=review

> Source/JavaScriptCore/yarr/YarrPattern.cpp:915
>      return 0;

nullptr

> LayoutTests/js/script-tests/stack-overflow-regexp.js:13
> +            recursiveCall(depth + 1);

Does the maximum depth of the regex we can compile without throwing an error changes with the amount of stack we have used with the JavaScript stack?
Also, can running the compiled regex cause unchecked stack overflows?

[Saam Barati]

Comment on attachment 279622 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=279622&action=review

r=me with comments

> Source/JavaScriptCore/yarr/YarrPattern.cpp:653
> +                    if (!setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet(), currentCallFrameSize))

A way to hide away manually writing these branches is to add a macro called
failIfStackOverflow which can just return if we've stack overflowed. The JS parser
uses this paradigm and I think it's nicer to read. When we stack overflow you can
set a bit in the class, and the macro can just query that bit. I'm not 100% tied to this style
but I think it's nicer than the in-out parameter and branching on a bool result

>> LayoutTests/js/script-tests/stack-overflow-regexp.js:13
>> +            recursiveCall(depth + 1);
> 
> Does the maximum depth of the regex we can compile without throwing an error changes with the amount of stack we have used with the JavaScript stack?
> Also, can running the compiled regex cause unchecked stack overflows?

Yeah the stack we have available for compilation is dependent on how much JS stack is use.
Not sure about the answer to your second question but I suspect not because I don't think the
YARR JIT will recurse in the code it emits.

[Benjamin Poulain]

Created attachment 279845 [details]
Patch for landing

[Benjamin Poulain]

(In reply to comment #3)
> Comment on attachment 279622 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=279622&action=review
> 
> r=me with comments
> 
> > Source/JavaScriptCore/yarr/YarrPattern.cpp:653
> > +                    if (!setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet(), currentCallFrameSize))
> 
> A way to hide away manually writing these branches is to add a macro called
> failIfStackOverflow which can just return if we've stack overflowed. The JS
> parser
> uses this paradigm and I think it's nicer to read. When we stack overflow
> you can
> set a bit in the class, and the macro can just query that bit. I'm not 100%
> tied to this style
> but I think it's nicer than the in-out parameter and branching on a bool
> result

I went forward without this change. I think it does not generalize as well here. The overflow is only handled in a specific path of the builder, not thorough. Unlike the parser, adding a state seems like adding complexity.

[WebKit Commit Bot]

Comment on attachment 279845 [details]
Patch for landing

Rejecting attachment 279845 [details] from commit-queue.

Number of test failures exceeded the failure limit.
Full output: http://webkit-queues.webkit.org/results/1383045

[WebKit Commit Bot]

Created attachment 279847 [details]
Archive of layout-test-results from webkit-cq-01 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the commit-queue.
Bot: webkit-cq-01  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[WebKit Commit Bot]

Comment on attachment 279845 [details]
Patch for landing

Clearing flags on attachment: 279845

Committed r201412: <http://trac.webkit.org/changeset/201412>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.