Bug 11849 – REGRESSION (r18182): Google Calendar is broken (a regular expression containing a null character is not parsed correctly)

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

Google Calendar does not display most of the interface in TOT. It fails due to an "Invalid regular expression" error during its initialization. Prior to r18182 (fix for bug 6257), JSC did not throw errors on invalid regular expression.

The offending regular expression is valid, but it fails to be parsed correctly since it contains a null character, which PCRE considers as a terminator. 

A reduced test case is
RegExp("[\0]")
which throws an error ("missing terminating ] for character class").

[Alexey Proskuryakov]

*** Bug 11982 has been marked as a duplicate of this bug. ***

Created attachment 12081 [details]
Quick and dirty fix, no change log, no test

This patch escapes null characters in the pattern before passing it to pcre_compile. I looked into changing pcre_compile to take a length parameter instead of a null-terminated string, and I think it's doable (would require some careful work), but I'm not sure it's necessary.

No test regressions and in fact fixes two JavaScriptCore tests: ecma_3/RegExp/octal-002.js and ecma_3/RegExp/regress-85721.js

Created attachment 12088 [details]
First pass at changing pcre_compile

Many redundant checks and other inefficiencies, and several FIXMEs, but it passes all of fast/js and the JavaScriptCore tests (an fixes two existing failures).

Created attachment 12092 [details]
pcre changes, refined

Most of the time compile_branch() doesn't need to check for end of string.

[David Kilzer (:ddkilzer)]

(In reply to comment #4)
> Created an attachment (id=12092) [edit]
> pcre changes, refined
> 
> Most of the time compile_branch() doesn't need to check for end of string.

The pcre library contains its own regression tests which are not included in JavaScriptCore/pcre.  It would be interesting to apply this patch to pcre-6.1 (which is what WebKit's version is based on) to verify that no regressions have taken place.

http://www.pcre.org/

[Geoffrey Garen]

This patch would increase the time required to scan a regular expression by O(n) --an unfortunate performance hit.

An alternative, which would fix the Google Calendar bug, would be to escape NULL characters as a part of sanitizePattern -- in other words, only if the expression failed to parse. However, that would leave open a subtle bug in the case where the subexpressionup until the first NULL character was still valid.

I think we need to change PCRE to take a length, instead. We do have a substantial number of regular expression tests that can catch subtle bugs along the way.

(In reply to comment #6)
> This patch would increase the time required to scan a regular expression by
> O(n) --an unfortunate performance hit.

You mean the first patch, right?

> I think we need to change PCRE to take a length, instead.

That's where the second (and third) patch are headed, isn't it?

Comment on attachment 12092 [details]
pcre changes, refined

(In reply to comment #5)
> The pcre library contains its own regression tests which are not included in
> JavaScriptCore/pcre.  It would be interesting to apply this patch to pcre-6.1
> (which is what WebKit's version is based on) to verify that no regressions have
> taken place.

Done. Or rather, backported patch, found a couple of regressions, fixed patch, verified no regressions. Thanks for the excellent idea! I'm going to post the updated patch soon.

Created attachment 12106 [details]
Change pcre_compile to take the pattern's length and work with patterns containing null characters

No layout test regressions, no JSC test regressions, two JSC tests fixed, no PCRE test regressions (when applying an equivalent patch to pcre-6.1).

I would really appreciate it if someone who knows how to do it measured the performance impact of this patch and of the alternative approach (attachment 12081 [details]).

[Geoffrey Garen]

(In reply to comment #9)

I ran a simple test:

tot: 231ms (baseline)
attachment 12106 [details]: 224ms (3% faster)
attachment 12081 [details]: 240ms (3.9% slower)

Test attached as 'regexp-parsing-performance.js'. Usage: "run-testkjs regexp-parsing-performance.js"

As a side note, I guess my concern was a little academic, since this issue only applies to parsing regular expressions, while executing them is by far the greater cost in common usage.

[Geoffrey Garen]

Created attachment 12112 [details]
regexp-parsing-performance.js

[Matt Lilek]

*** Bug 12032 has been marked as a duplicate of this bug. ***

Created attachment 12144 [details]
Change pcre_compile to take the pattern's length and work with patterns containing null characters

Updated for PCRE 6.4 (following bug 12031 and bug 12036).

[Darin Adler]

Comment on attachment 12144 [details]
Change pcre_compile to take the pattern's length and work with patterns containing null characters

       /* The space before the ; is to avoid a warning on a silly compiler
       on the Macintosh. */

The above comment no longer makes sense.

This is by far the biggest change we've ever made to PCRE! But it's worth it.

Merging with future versions of PCRE is going to be rather difficult.

r=me

[David Kilzer (:ddkilzer)]

(In reply to comment #13)
> Created an attachment (id=12144) [edit]
> Change pcre_compile to take the pattern's length and work with patterns
> containing null characters
> 
> Updated for PCRE 6.4 (following bug 12031 and bug 12036).

JavaScriptCore/tests/mozilla/expected.html did not apply cleanly.  Trying to regenerate results, but there seems to be a lot of machine-specific information in this file.

[David Kilzer (:ddkilzer)]

Committed revision 18517.

[David Kilzer (:ddkilzer)]

Patch in Attachment 12144 [details] causes new compile errors in pcre_compile.c on Windows now:

http://build.webkit.org/post-commit-win32/builds/4045

[David Kilzer (:ddkilzer)]

Created attachment 12164 [details]
Fixes Windows build

(In reply to comment #17)
> Patch in Attachment 12144 [details] [edit] causes new compile errors in pcre_compile.c on
> Windows now:
> 
> http://build.webkit.org/post-commit-win32/builds/4045

Fixed by this patch.

Committed revision 18525.

[David Kilzer (:ddkilzer)]

(In reply to comment #18)
> Created an attachment (id=12164) [edit]
> Fixes Windows build
> 
> Committed revision 18525.

See also r18526.