Bug 187042

Summary: RegExp.exec returns wrong value with a long integer quantifier
Product: WebKit Reporter: Thyago Pessoa <tmp2>
Component: JavaScriptCoreAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, darin, ews-watchlist, isol2, keith_miller, mark.lam, msaboff, saam, sukolsak, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: Safari 11   
Hardware: Unspecified   
OS: Unspecified   
See Also: https://bugs.webkit.org/show_bug.cgi?id=209573
Attachments:
Description Flags
Patch
none
Fix tests
none
Use Checked<unsigned, RecordOverflow> and quantifyInfinite
none
Forgot to update ChangeLog
none
Remove the extra overflow loop, use consumeDigit, and update ChangeLog
none
Patch for landing none

Description Thyago Pessoa 2018-06-26 07:27:47 PDT
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.
Comment 1 Sukolsak Sakshuwong 2018-07-01 02:54:26 PDT
Created attachment 344045 [details]
Patch
Comment 2 EWS Watchlist 2018-07-01 04:14:18 PDT
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
Comment 3 Mark Lam 2018-07-01 07:57:24 PDT
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.
Comment 4 Sukolsak Sakshuwong 2018-07-01 08:45:02 PDT
Created attachment 344050 [details]
Fix tests
Comment 5 Saam Barati 2018-07-01 09:38:25 PDT
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
Comment 6 Saam Barati 2018-07-01 09:39:49 PDT
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
Comment 7 Mark Lam 2018-07-01 09:43:13 PDT
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.
Comment 8 Sukolsak Sakshuwong 2018-07-01 09:47:37 PDT
Created attachment 344051 [details]
Use Checked<unsigned, RecordOverflow> and quantifyInfinite
Comment 9 Sukolsak Sakshuwong 2018-07-01 10:02:42 PDT
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.
Comment 10 Sukolsak Sakshuwong 2018-07-01 10:11:06 PDT
Created attachment 344052 [details]
Forgot to update ChangeLog
Comment 11 Mark Lam 2018-07-01 13:41:35 PDT
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();
Comment 12 Darin Adler 2018-07-01 13:49:58 PDT
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.
Comment 13 Mark Lam 2018-07-01 14:17:52 PDT
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.
Comment 14 Sukolsak Sakshuwong 2018-07-01 14:41:29 PDT
Created attachment 344061 [details]
Remove the extra overflow loop, use consumeDigit, and update ChangeLog
Comment 15 Saam Barati 2018-07-01 23:18:30 PDT
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
Comment 16 Sukolsak Sakshuwong 2018-07-02 17:07:39 PDT
Created attachment 344153 [details]
Patch for landing
Comment 17 Sukolsak Sakshuwong 2018-07-02 17:09:16 PDT
(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.
Comment 18 WebKit Commit Bot 2018-07-02 17:49:54 PDT
Comment on attachment 344153 [details]
Patch for landing

Clearing flags on attachment: 344153

Committed r233451: <https://trac.webkit.org/changeset/233451>
Comment 19 WebKit Commit Bot 2018-07-02 17:49:56 PDT
All reviewed patches have been landed.  Closing bug.
Comment 20 Radar WebKit Bug Importer 2018-07-02 17:50:45 PDT
<rdar://problem/41750143>
Comment 21 isol2 2018-08-08 09:02:31 PDT
cinfuzz