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

Reported by:	trentm@gmail.com	Owned by:
Priority:	low	Milestone:	None
Component:	selector	Version:	1.7.1
Keywords:		Cc:
Blocked by:		Blocking:

Description

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.

Attachments (0)

Change History (6)

Changed March 22, 2012 10:36PM UTC by anonymous comment:1

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.

Changed March 22, 2012 10:40PM UTC by trentm comment:2

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

Changed March 23, 2012 01:04AM UTC by dcherman comment:3

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.

Changed March 23, 2012 05:12AM UTC by trentm comment:4

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.

Changed April 04, 2012 01:07AM UTC by dmethvin comment:5

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

Changed April 23, 2012 04:41PM UTC by rwaldron comment:6

component:	unfiled → selector
priority:	undecided → low
resolution:	→ invalid
status:	new → closed

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

Side navigation

#11505 closed bug (invalid)