Bug 187042 – RegExp.exec returns wrong value with a long integer quantifier

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

[Thyago Pessoa]

Hi everyone,

I found an inconsistence on Regexp pattern with a long integer quantifier.

version: Safari-606.1.9.4
OS: Ubuntu 16.04 x64

Step to reproduce:

r = new RegExp ("(?:a{0,34028236692}?){0,1}a"); // length 11
print(r.exec ("aa") == "aa"); // returns aa

r = new RegExp ("(?:a{0,340282366920}?){0,1}a"); // length 12
print(r.exec ("aa") == "aa"); // returns a

Actual results:
true
false

Expected results:
true
true

V8, Chakra and SpiderMonkey works as expected.

[Sukolsak Sakshuwong]

Created attachment 344045 [details]
Patch

[EWS Watchlist]

Comment on attachment 344045 [details]
Patch

Attachment 344045 [details] did not pass jsc-ews (mac):
Output: https://webkit-queues.webkit.org/results/8402596

New failing tests:
stress/regress-159744.js.ftl-no-cjit-no-inline-validate
stress/regress-159744.js.dfg-eager-no-cjit-validate
stress/regress-159744.js.no-cjit-validate-phases
stress/regress-159744.js.dfg-eager
stress/regress-159744.js.ftl-no-cjit-no-put-stack-validate
stress/regress-159744.js.no-ftl
stress/regress-159744.js.ftl-no-cjit-b3o1
stress/regress-159744.js.no-cjit-collect-continuously
stress/regress-159744.js.ftl-eager-no-cjit-b3o1
stress/regress-159744.js.ftl-eager
stress/regress-159744.js.no-llint
stress/regress-159744.js.ftl-no-cjit-validate-sampling-profiler
stress/regress-159744.js.ftl-eager-no-cjit
stress/regress-159744.js.ftl-no-cjit-small-pool
stress/regress-159744.js.default
stress/regress-159744.js.dfg-maximal-flush-validate-no-cjit
apiTests

[Mark Lam]

Comment on attachment 344045 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=344045&action=review

r- because a JSC test is failing.  Please investigate as to why it's failing.

> Source/JavaScriptCore/yarr/YarrParser.h:990
> -        // check for overflow.
> -        for (unsigned newValue; peekIsDigit() && ((newValue = n * 10 + peekDigit()) >= n); ) {
> -            n = newValue;
> +        while (peekIsDigit()) {
> +            unsigned nextDigit = peekDigit();
> +            if (n > (UINT_MAX - nextDigit) / 10) {
> +                // Overflow. Skip past remaining decimal digits and return UINT_MAX.
> +                do {
> +                    consume();
> +                } while (peekIsDigit());
> +                return UINT_MAX;
> +            }
> +            n = n * 10 + nextDigit;
>              consume();
>          }
>          return n;

Please look into using Checked<unsigned, RecordOverflow> (grep for other places where this is used to see how it's used).  You should use that here instead.  It will simplify this code tremendously.
Also, to be consistent with the rest of Yarr code, you should return quantifyInfinite here instead of UINT_MAX directly.

[Sukolsak Sakshuwong]

Created attachment 344050 [details]
Fix tests

[Saam Barati]

Comment on attachment 344050 [details]
Fix tests

View in context: https://bugs.webkit.org/attachment.cgi?id=344050&action=review

> Source/JavaScriptCore/yarr/YarrParser.h:987
> +            n = n * 10 + nextDigit;

Let’s just use Checked<unsigned> for n

[Saam Barati]

Comment on attachment 344050 [details]
Fix tests

View in context: https://bugs.webkit.org/attachment.cgi?id=344050&action=review

>> Source/JavaScriptCore/yarr/YarrParser.h:987
>> +            n = n * 10 + nextDigit;
> 
> Let’s just use Checked<unsigned> for n

We can then return UINT_MAX if that overflows

[Mark Lam]

Comment on attachment 344050 [details]
Fix tests

View in context: https://bugs.webkit.org/attachment.cgi?id=344050&action=review

>>> Source/JavaScriptCore/yarr/YarrParser.h:987
>>> +            n = n * 10 + nextDigit;
>> 
>> Let’s just use Checked<unsigned> for n
> 
> We can then return UINT_MAX if that overflows

I pointed this out earlier (in https://bugs.webkit.org/show_bug.cgi?id=187042#c3): use Checked<unsigned, RecordOverflow >.  Plain Checked<unsigned> will crash on overflow, and I think we don't want that.
Also, use quantifyInfinite instead of UINT_MAX to be consistent with the rest of Yarr code.

[Sukolsak Sakshuwong]

Created attachment 344051 [details]
Use Checked<unsigned, RecordOverflow> and quantifyInfinite

[Sukolsak Sakshuwong]

Thanks. I personally think it is semantically inconsistent to check a value against UINT_MAX but return quantifyInfinite instead of UINT_MAX (I know they have the same value) if the value exceeds UINT_MAX. But since the rest of Yarr code seems to use quantifyInfinite heavily, I will use quantifyInfinite as you suggested.

[Sukolsak Sakshuwong]

Created attachment 344052 [details]
Forgot to update ChangeLog

[Mark Lam]

Comment on attachment 344052 [details]
Forgot to update ChangeLog

View in context: https://bugs.webkit.org/attachment.cgi?id=344052&action=review

I'd like Michael Saboff to take a look at the RegExp test changes.

> Source/JavaScriptCore/yarr/YarrParser.h:985
> +            if (n.hasOverflowed()) {
> +                do {
> +                    consume();
> +                } while (peekIsDigit());
> +                return quantifyInfinite;
> +            }

This extra overflow check is not needed because in the overflow case: 1. we still need to interate all digits anyway, and the cost of the computation of n is not that expensive, and 2. overflows rarely happen.  We should favor the normal (non-overflow) case by not adding extra overflow checks to it.

> Source/JavaScriptCore/yarr/YarrParser.h:988
> +        return n.unsafeGet();

Do this here:
    return n.hasOverflowed() ? quantifyInfinite : n.unsafeGet();

[Darin Adler]

Comment on attachment 344052 [details]
Forgot to update ChangeLog

View in context: https://bugs.webkit.org/attachment.cgi?id=344052&action=review

>> Source/JavaScriptCore/yarr/YarrParser.h:985
>> +            }
> 
> This extra overflow check is not needed because in the overflow case: 1. we still need to interate all digits anyway, and the cost of the computation of n is not that expensive, and 2. overflows rarely happen.  We should favor the normal (non-overflow) case by not adding extra overflow checks to it.

So this loop should just be this:

    while (peekIsDigit())
        n = n * 10 + consumeDigit();

Then the whole function will just be four lines long, just like the original version. And more straightforward than the original, too.

[Mark Lam]

Comment on attachment 344052 [details]
Forgot to update ChangeLog

View in context: https://bugs.webkit.org/attachment.cgi?id=344052&action=review

>>> Source/JavaScriptCore/yarr/YarrParser.h:985
>>> +            }
>> 
>> This extra overflow check is not needed because in the overflow case: 1. we still need to interate all digits anyway, and the cost of the computation of n is not that expensive, and 2. overflows rarely happen.  We should favor the normal (non-overflow) case by not adding extra overflow checks to it.
> 
> So this loop should just be this:
> 
>     while (peekIsDigit())
>         n = n * 10 + consumeDigit();
> 
> Then the whole function will just be four lines long, just like the original version. And more straightforward than the original, too.

Oh, that's even better.  I didn't think to use consumeDigit() but that is totally the way to go.

[Sukolsak Sakshuwong]

Created attachment 344061 [details]
Remove the extra overflow loop, use consumeDigit, and update ChangeLog

[Saam Barati]

Comment on attachment 344061 [details]
Remove the extra overflow loop, use consumeDigit, and update ChangeLog

View in context: https://bugs.webkit.org/attachment.cgi?id=344061&action=review

r=me

> Source/JavaScriptCore/ChangeLog:11
> +        because once there has been overflow, undefined behavior has occurred.

This isn’t true. Unsigned overflow is defined behavior. Signed overflow is not. Your point below holds regardless

[Sukolsak Sakshuwong]

Created attachment 344153 [details]
Patch for landing

[Sukolsak Sakshuwong]

(In reply to Saam Barati from comment #15)
> Comment on attachment 344061 [details]
> Remove the extra overflow loop, use consumeDigit, and update ChangeLog
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=344061&action=review
> 
> r=me
> 
> > Source/JavaScriptCore/ChangeLog:11
> > +        because once there has been overflow, undefined behavior has occurred.
> 
> This isn’t true. Unsigned overflow is defined behavior. Signed overflow is
> not. Your point below holds regardless

Thanks. I didn't know this. I have removed that sentence from the ChangeLog.

[WebKit Commit Bot]

Comment on attachment 344153 [details]
Patch for landing

Clearing flags on attachment: 344153

Committed r233451: <https://trac.webkit.org/changeset/233451>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/41750143>

cinfuzz