1408452 - /\x/ and /\u/ produce incorrect regular expressions

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[zirak]

Attachment: solution-1.diff

User Agent: Mozilla/5.0 (X11; Linux x86_64; rv:56.0) Gecko/20100101 Firefox/56.0
Build ID: 20171009141542

Steps to reproduce:

    /\x/.test('x'); // false
    /\x/.test('xx'); // true

Does not trigger when there's any character at all after the escape:

    /\x!/.test('x!'); // true

(if you don't care about the debugging, Ctrl-F "solution")

After a long debugging session, it came down to RegExpParser.cpp: https://dxr.mozilla.org/mozilla-central/source/js/src/irregexp/RegExpParser.cpp#1755-1765.
The problem stems from the "backtracing" done in ParseHexEscape, and it's a subtle problem at that (at least for my tastes).

In the beginning of the `case 'x'` label in ParseDisjunction, our state looks something like:

    current()  = 0x5c ('\')
    position() = 0x...3368 ("\\x")
    next_pos_  = 0x...3369 ("x")
    has_more   = true

After the Advance(2) call in line 1756, we've supposedly stepped over both characters, giving us:

    current()  = random memory
    position() = 0x...3369 ('x')
    next_pos_  = end_ = 0x...3360
    has_more   = false

The important bit is that even though we've "stepped over" both characters, `position()` still returns `"x"` and not `end_`.

Now inside of `ParseHexEscape`, line 371 saves our current position and when `Reset` is called on line 378, `has_more` is flipped back to `true`.

We leave the function with the following state:


    current()  = 0x78 ('x')
    position() = 0x...3369 ("x")
    next_pos_  = end_ = 0x...3360
    has_more_  = true

Outside of the function in `ParseDisjunction`:1763 adds 'x' to the regexp, giving us /x/. That's good.

However, the `while` loop in `ParseDisjunction` continues since `has_more` is `true`. Now we're pointing at 'x' again which is consumed as a literal character, giving us the effective regexp /xx/. Yikes.

This also happens for \u: /\u/.test('uu') === true



There're several solutions to this sort of problem. It's a classic combination of "state management is hard" and "parsing is hard", giving us a bit of a headache.

One simple and obvious solution is to add `has_more_` checks to `ParseX`, for instance:

    1 file changed, 4 insertions(+)
    js/src/irregexp/RegExpParser.cpp | 4 ++++

    modified   js/src/irregexp/RegExpParser.cpp
    @@ -368,6 +368,10 @@ template <typename CharT>
     bool
     RegExpParser<CharT>::ParseHexEscape(int length, widechar* value)
     {
    +    if (!has_more_) {
    +        return false;
    +    }
    +
         const CharT* start = position();
         uint32_t val = 0;
         bool done = false;

That works but it doesn't solve the underlying problem: Advance does not correctly set next_pos_ when has_more_ is set to false. Those are two pieces of state which should be linked but they are divorced in this specific case. A more thorough solution could be:

    modified   js/src/irregexp/RegExpParser.cpp
    @@ -328,6 +328,7 @@ RegExpParser<CharT>::Advance()
             next_pos_++;
         } else {
             current_ = kEndMarker;
    +        next_pos_ = end_ + 1;
             has_more_ = false;
         }
     }

That also seems to be the approach Chromium took: https://cs.chromium.org/chromium/src/v8/src/regexp/regexp-parser.cc?l=96&rcl=094a7c93dcdcd921de3883ba4674b7e1a0feffbe

Comment 1

[zirak]

Attachment: More appropriate solution

Comment 2

[zirak]

Test case on test262: https://github.com/tc39/test262/pull/1274

Comment 3

[Tooru Fujisawa [:arai]]

Comment on attachment 8918374 [details] [diff] [review]
More appropriate solution

thanks :)
this looks good.

can you export this as a patch file and attach it here, so that it contains commit message and author information?

Comment 4

[zirak]

Attachment: 0001-Fix-RegExpParser-position-tracking.patch

Attached. Hopefully it's the correct format, as I am but a git plebian I followed the instructions in https://developer.mozilla.org/en-US/docs/Mercurial/Using_Mercurial#I%27m_all_used_to_Git_but_how_can_I_provide_Mercurial-ready_patches

Comment 5

[Tooru Fujisawa [:arai]]

Comment on attachment 8918484 [details] [diff] [review]
0001-Fix-RegExpParser-position-tracking.patch

Review of attachment 8918484 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks again :D

I've triggered try run (automated testing)
https://treeherder.mozilla.org/#/jobs?repo=try&revision=a41c28ea1b79b2d4a0fa9e0134fa30a22966807e

while waiting for the try, can you fix the 1st line of the commit message to
"Bug 1408452 - Fix RegExpParser position tracking" ?

also, once your test262 patch gets merged there, can you create another patch to add the test under js/src/tests/test262/local ?
with appending `reportCompare(0, 0);` at the end of file, like the following file:
https://dxr.mozilla.org/mozilla-central/rev/196dadb2fe500e75c6fbddcac78106648676cf10/js/src/tests/test262/built-ins/RegExp/unicode_restricted_brackets.js#33

we're updating js/src/tests/test262 directory periodically,
and js/src/tests/test262/local is the directory for adding tests temporary.

Comment 6

[Tooru Fujisawa [:arai]]

the test gets merged.
zirak, can you prepare a patch for testcase, and also update the commit message of the 1st patch?

Comment 7

[zirak]

Attachment: 0001-Fix-RegExpParser-position-tracking.patch

Comment 8

[Tooru Fujisawa [:arai]]

Comment on attachment 8919928 [details] [diff] [review]
0001-Fix-RegExpParser-position-tracking.patch

Review of attachment 8919928 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you :D

Comment 9

[zirak]

Attachment: 0002-Bug-1408452-Add-test262-case.patch

Was this your intention?

Comment 10

[Tooru Fujisawa [:arai]]

Comment on attachment 8919934 [details] [diff] [review]
0002-Bug-1408452-Add-test262-case.patch

Review of attachment 8919934 [details] [diff] [review]:
-----------------------------------------------------------------

Yes, thanks again!

Comment 11

[Tooru Fujisawa [:arai]]

The test passed locally.

Comment 12

[zirak]

Huzzah! What happens now?

Comment 13

[Tooru Fujisawa [:arai]]

these patches will be checked in shortly :)

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3faec071445
Fix RegExpParser position tracking. r=arai
https://hg.mozilla.org/integration/mozilla-inbound/rev/76fa19a2eef0
Add test262 test case. r=arai

Comment 15

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/e3faec071445
https://hg.mozilla.org/mozilla-central/rev/76fa19a2eef0

Comment 16

[Julien Cristau [:jcristau]]

Not a new issue, doesn't sound worth uplifting.