Bug 18327 - REGRESSION (r28833): Regex fails on long string
Summary: REGRESSION (r28833): Regex fails on long string
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh OS X 10.5
: P1 Normal
Assignee: Geoffrey Garen
URL: http://crschmidt.net/projects/webkit/...
Keywords: HasReduction, InRadar, Regression
: 21485 24308 (view as bug list)
Depends on:
Blocks:
 
Reported: 2008-04-05 18:41 PDT by Christopher Schmidt
Modified: 2009-04-02 11:24 PDT (History)
9 users (show)

See Also:


Attachments
the linked test case (25.28 KB, text/html)
2008-08-25 09:25 PDT, Darin Adler
no flags Details
test demonstrating string replace failure (43.76 KB, application/x-javascript)
2008-09-08 10:06 PDT, Tim Schaub
no flags Details
patch (1.51 KB, patch)
2009-03-19 15:10 PDT, Geoffrey Garen
oliver: review+
Details | Formatted Diff | Diff
split long-running test case into separate file (4.49 KB, patch)
2009-04-02 10:42 PDT, Pam Greene (IRC:pamg)
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Christopher Schmidt 2008-04-05 18:41:45 PDT
The URL demonstrates that Safari 3.1 (Version 3.1 (5525.13)) and WebKit Nightly r31623 fail to parse the string when its length is over 25056 characters.

This regex is a commonly used way of determining whether a string is valid JSON.

In Safari 3.0, this works, and it works in all other browsers that I have tested it in (IE6/IE7, FF2/FF3, Opera 9.x).
Comment 1 Christopher Schmidt 2008-04-05 18:42:15 PDT
It is possible this is somewhat related to http://bugs.webkit.org/show_bug.cgi?id=16323
Comment 2 Christopher Schmidt 2008-04-05 18:51:05 PDT
Oh, and I wanted to test with other nightlies, but grabbing one from more than a couple weeks ago just fails because Safari is looking for symbols that don't exist in the build; this was as specific as I could get. Sorry about that.
Comment 3 Alexey Proskuryakov 2008-04-07 00:13:01 PDT
Confirmed with r31667 (haven't tried 3.0 to verify that this is a regression though).
Comment 4 Mark Rowe (bdash) 2008-08-24 21:46:47 PDT
<rdar://problem/6172476>
Comment 5 Darin Adler 2008-08-25 09:25:56 PDT
Created attachment 22981 [details]
the linked test case
Comment 6 Tim Schaub 2008-09-08 10:06:58 PDT
Created attachment 23262 [details]
test demonstrating string replace failure

This throws an exception in 3.1.2 (and should not).
Comment 7 Christopher Schmidt 2008-09-08 10:42:45 PDT
(In reply to comment #6)
> Created an attachment (id=23262) [edit]
> test demonstrating string replace failure
> 
> This throws an exception in 3.1.2 (and should not).

A relatively recent JavascriptCore checkout (r35900) fails on this test case like so:

dhcp-208-80-142-180:~ crschmidt$ ./jsc crash.js ; echo $?
jsRegExpExecute failed with result -2
3

 
Comment 8 David Kilzer (:ddkilzer) 2008-12-24 12:21:52 PST
The bisect-builds script reports:

Works: r28811  Fails: r28843

Comment 9 David Kilzer (:ddkilzer) 2008-12-24 12:25:55 PST
(In reply to comment #8)
> The bisect-builds script reports:
> 
> Works: r28811  Fails: r28843

Most suspicious commit in that range:  <http://trac.webkit.org/changeset/28833>

Comment 10 David Kilzer (:ddkilzer) 2008-12-24 13:31:43 PST
(In reply to comment #9)
> Most suspicious commit in that range:  <http://trac.webkit.org/changeset/28833>

Confirmed that the attached test case is hitting the matchLimit from r28833.  The test case that passes is "recursing" 99,999 times.  Each additional character in the matching string adds 4 "recursions", so the failing test case is "recursing" 100,003 times.

I don't know this code, so I'm not sure if there is a way to match more efficiently in this case.
Comment 11 Darin Adler 2008-12-25 10:00:55 PST
Geoff is working on regular expressions right now.
Comment 12 Alexey Proskuryakov 2009-02-26 10:49:06 PST
Se also bug 24166 (duplicate?).
Comment 13 Darin Adler 2009-02-26 11:11:04 PST
(In reply to comment #12)
> See also bug 24166 (duplicate?).

Not a duplicate; another separate limitation.
Comment 14 Geoffrey Garen 2009-03-19 15:06:38 PDT
*** Bug 21485 has been marked as a duplicate of this bug. ***
Comment 15 Geoffrey Garen 2009-03-19 15:07:23 PDT
*** Bug 24308 has been marked as a duplicate of this bug. ***
Comment 16 Geoffrey Garen 2009-03-19 15:10:46 PDT
Created attachment 28766 [details]
patch
Comment 17 Oliver Hunt 2009-03-19 15:13:56 PDT
Comment on attachment 28766 [details]
patch

r=me, but add a test case so we don't regress this again
Comment 18 Geoffrey Garen 2009-03-19 17:52:26 PDT
Testcase added.

Committed revision 41849.
Comment 19 David Levin 2009-03-24 12:59:05 PDT
Isn't this fixed?  (Can it be resolved to move it out of the commit queue?)
Comment 20 David Kilzer (:ddkilzer) 2009-03-24 13:26:38 PDT
Marking RESOLVED/FIXED per Comment #18 and Comment #19.  Thanks!
Comment 21 Pam Greene (IRC:pamg) 2009-03-30 11:16:45 PDT
Neither Firefox 3 nor Chromium (trunk) can run this test now. The long test case added in r41849 causes them both to time out. (IE7 finishes it in ~15 seconds, but it gets the wrong answer.)

I can't speak about FF, but V8 deliberately decided not to limit the runtime of long regexps, since the engine is intrinsically interruptible. So they use the normal "This script has been running a long time; do you want to continue?" mechanism rather than a special case.  See http://code.google.com/p/v8/issues/detail?id=287

I'd like to split this one problematic test case into a separate file, which Chromium (and any other platforms that had a different long-running-RE design goal) could then skip individually. Sound reasonable?
Comment 22 Darin Adler 2009-03-30 12:10:55 PDT
(In reply to comment #21)
> I'd like to split this one problematic test case into a separate file, which
> Chromium (and any other platforms that had a different long-running-RE design
> goal) could then skip individually. Sound reasonable?

Seems fine.
Comment 23 Pam Greene (IRC:pamg) 2009-04-02 10:42:29 PDT
Created attachment 29197 [details]
split long-running test case into separate file
Comment 24 Darin Adler 2009-04-02 10:47:21 PDT
Comment on attachment 29197 [details]
split long-running test case into separate file

r=me
Comment 25 Pam Greene (IRC:pamg) 2009-04-02 11:24:45 PDT
Split landed in r42177.