Performance issues with complex content

[Reinmar]

I've been testing pasting some really complex websites (like https://gazeta.pl) and I noticed that it often causes browser to freeze.

I've been curious whether this is related to some problems with conversion (a potential inf loop) but I got something interesting once I asked Firefox to stop that heavy script execution:

I noticed that styles are mostly inlined on gazeta.pl and that there are images included there as base64 encoded strings (in background-image, I presume). This would nicely connect with the parseInlineStyles() being the last call in that stack trace.

There are two options:

• Either we use some poorly performing regexp or other kind of parser.
• Or we have even an inf loop in a regexp (this is possible).

[Reinmar]

Yep, I was right :)

[Reinmar]

And these are some the styles which cause the problem:

• https://gist.github.com/Reinmar/49d4f1e3d34f332246371f6e6a7eb7c2
• https://gist.github.com/Reinmar/8e774a36364ffeaf5503674b28891ff7

Hint for the future:

function parseInlineStyles( stylesMap, stylesString ) {
	const d = new Date();
	const regex = /\s*([^:;\s]+)\s*:\s*([^;]+)\s*(?=;|$)/g;
	let matchStyle;
	stylesMap.clear();

	while ( ( matchStyle = regex.exec( stylesString ) ) !== null ) {
		stylesMap.set( matchStyle[ 1 ], matchStyle[ 2 ].trim() );
	}

	if ( new Date() - d > 100 ) {
		console.log( stylesString );
	}
}

It really did the job :D.

[Reinmar]

Now, some regexp analysis. I'm not an expert in this (ask @fredck for verification), but for me the problem here is that we use too many variable length exclusion groups and that the regexp tries to match the longest piece possible at once (the groups are greedy).

This means that on first "go" it captures as long content as possible but if something doesn't match at the end ((?=;|$)) it gets back to the previous group and starts checking whether it could capture less characters with that one and still match the end. And since there are two groups before that it gets super bad because it has to check every possible combination. There's some name for that issue.

BTW, there's also a bug which will break with the CSSes that I provided – ; can be used in a CSS value (inside a "" – e.g. in the image source).

Now, the solution will depend on how good we need the parser to be. I think that we don't have to care about ; in the values at the moment. So I'd start with a simplification – let's split the initial string with /\s*;\s*/ and then split the pairs with /\s*:\s*/. It should be far more secure in terms of performance and it's just super simple.

[Reinmar]

PS. I think it's called backtracking: http://www.regular-expressions.info/catastrophic.html.

[scofalik]

I guess we need some workshops on regular expressions (@fredck? :)).

Anyway I guess it would be profitable to check all the expressions we use, there might be more such places.

[fredck]

I've checked the regex and it is indeed buggy, as it doesn't support ; inside ". The following regex should do the job:

/\s*([^:;\s]+)\s*:\s*((?:[^";]+|"[^"]+")+)\s*(?=;|$)/g

[Reinmar]

Doesn't this regexp have the same performance issue as the previous one?

[fredck]

No, it should not have that performance issue. I've checked with both cases you posted previously.

Btw, I've just edited the regex, removing the ' case to make it simpler.

[fredck]

So, I've worked further on the regex, to see if there is anything that could be enhanced.

I've figured out that the previous proposal was buggy because it ignores cases like content: "".

I've fixed that and optimized a few bits. Here is a new proposal then:

/([^:;\s]+)\s*:\s*((?:[^";]+?|"[^"]*")+?)\s*(?=;|$)/g

[fredck]

Btw, this new regex already trims spaces from the value, which should simplify the post-processing code.

[fredck]

https://regex101.com/r/IWNmQh/1

[Reinmar]

OK, I checked that the performance is fixed. And it passes the existing tests too. Thanks, @fredck :)

[Reinmar]

Update – we removed the regexp because even the improved ones turned to be very unstable. A naive linear state-machine turned to behave much better and there's still a room for improvements if we'll ever need them.