100% CPU slow parsing of `href[|=...]` selector

[trentm@…]

Using jquery 1.7.1 (min). Examples here are in the Chrome console (Google Chrome v17.0.963.83)

Start with this:

$("#sidebar a[href|=#xxxxxxxxxxxxxxx'x]")
Error: Syntax error, unrecognized expression: href|=#xxxxxxxxxxxxxxx'x]

Now I'm going to increase the number of x's and show the amount of time taken. It increases faster than linearly such that you get apparent hangs if the string is at all long:

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:22:54 GMT-0700 (PDT)
Thu Mar 22 2012 15:22:54 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:23:00 GMT-0700 (PDT)
Thu Mar 22 2012 15:23:00 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:23:06 GMT-0700 (PDT)
Thu Mar 22 2012 15:23:07 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:23:11 GMT-0700 (PDT)
Thu Mar 22 2012 15:23:13 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:23:17 GMT-0700 (PDT)
Thu Mar 22 2012 15:23:21 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:23:26 GMT-0700 (PDT)
Thu Mar 22 2012 15:23:35 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:26:48 GMT-0700 (PDT)
Thu Mar 22 2012 15:27:05 GMT-0700 (PDT)
undefined

> console.log(new Date()); try { $("#sidebar a[href|=#xxxxxxxxxxxxxxxxxxxxxx'x]"); } catch(e) { console.log(new Date()) }
Thu Mar 22 2012 15:27:21 GMT-0700 (PDT)
Thu Mar 22 2012 15:27:55 GMT-0700 (PDT)
undefined

This shows the time to handle the selector growing from sub-second to over 34 seconds.

[anonymous]

Here is a jsFiddle showing this behaviour:  http://jsfiddle.net/hx2T8/

Run that in Chrome and watch CPU usage. I was testing on Mac 10.6. Add more x's to make it take much longer.

[trentm]

I just created an account (username 'trentm'). I added this bug and the first comment (with the jsfiddle.net link).

[dcherman]

See:  http://api.jquery.com/category/selectors/

You need to escape your meta characters. When I ran that selector with the characters properly escaped, it was pretty instant.

[trentm]

Agreed that for a valid selector I need to escape here. However, that isn't the bug I was logging.

The bug is that it takes an exponentially (or geometrically, not sure) longer time to determine that the selector is invalid syntax with the longer the 'value' field.

[dmethvin]

It might be possible to tweak the regexp to prevent catastrophic backtracking, but when the input is invalid all bets are off.

[rwaldron]

Closing this, please provide a test case that uses a valid selector to re-open.