320483 - A javascript one-line snippet that hangs firefox

Status: RESOLVED DUPLICATE of bug 307456

(Core :: JavaScript Engine, defect)

Description

[Lupin.wp]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8) Gecko/20051128 Debian/1.4.99+1.5rc3.dfsg-2 Firefox/1.5
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8) Gecko/20051128 Debian/1.4.99+1.5rc3.dfsg-2 Firefox/1.5

If you type
  javascript:'XZZZZZZZZZZZZZZZZZZZZZZZZ'.match(/([^Y]|Z)*X/)
into the location bar, then firefox hangs.

(Incidentally, so do opera and IE. Konqueror passes the test if you paste it into the javascript debugger).

Marking as critical because of the information loss when your browser hangs.

This may or may not be related to bug #307456.

Reproducible: Always

Steps to Reproduce:

Comment 1

[Ria Klaassen (not reading all bugmail)]

Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a1) Gecko/20051215 Firefox/1.6a1 ID:2005121506

I get a freeze of about 13 seconds; after writing X, it becomes responsive again.

Comment 2

[Lupin.wp]

Yes, this does return, after over a minute for me (800 mhz machine). 

By increasing the number of repeated Zs in the string, I can increase the length of the hang, seemingly indefinitely. I suspect that using 1000000 Zs instead of 25 will hang all machines:

javascript:str='X';for(i=0;i<100000;++i)str+='ZZZZZZZZZZ';alert(/([^Y]|Z)*X/.test(str))

There are two issues here that I can see:

(1) This is not a complicated regexp match. It shouldn't take this long to execute.

(2) In general, regexes can take arbitrarily long to execute. They shouldn't block the whole browser; in particular, the "long-running script" dialog should be able to interrupt and resume their execution.

Comment 3

[Brendan Eich [:brendan]]

Backtracking costs, exponentially.  Perl 4 would take a long time, too.  Perl 5 adds some hairy short-circuiting checks to avoid taking too long.  We should do something similar.

How well do other browsers do?

This looks like a dup of bug 307456.  If this bug has the simpler testcase, the URL could be copied to that bug.

/be

Comment 4

[Bob Clary [:bc] (inactive)]

On a Pentimum M 1.7Ghz/winxp, IE completes the original URL in less than 5 secs, Opera 8.51 and Firefox 1.5 complete it in 10-15 seconds and everyone locks up the UI until it is complete. I didn't wait for the extended test to complete but it locks up IE and Opera just fine.

*** This bug has been marked as a duplicate of 307456 ***