Bug 183996 – [ESNext][BigInt] Implement support for "/" operation

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

[Caio Lima]

...

[Caio Lima]

Created attachment 336498 [details]
Patch

[EWS Watchlist]

Attachment 336498 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:738:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:740:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 2 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Caio Lima]

Ping Review

[Caio Lima]

Created attachment 337576 [details]
Patch

[EWS Watchlist]

Attachment 337576 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:738:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:740:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 2 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[EWS Watchlist]

Comment on attachment 337576 [details]
Patch

Attachment 337576 [details] did not pass jsc-ews (mac):
Output: http://webkit-queues.webkit.org/results/7262699

New failing tests:
stress/ftl-put-by-id-setter-exception-interesting-live-state.js.dfg-eager-no-cjit-validate

[Caio Lima]

Ping Review. The failures aren't related with my patch.

[Caio Lima]

Created attachment 338187 [details]
Patch

[EWS Watchlist]

Attachment 338187 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:738:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:740:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 2 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Caio Lima]

Ping Review

[Caio Lima]

Created attachment 338995 [details]
Patch

[EWS Watchlist]

Attachment 338995 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:800:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Caio Lima]

Could anyone review this?

[Robin Morisset]

Comment on attachment 338995 [details]
Patch

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

I am not an official Webkit reviewer, but I have tried to read through your patch and have a few comments and questions.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:298
> +    quotient->setSign(x->sign() != y->sign());

Is there a reason not to use resultSign here?

> Source/JavaScriptCore/runtime/JSBigInt.cpp:302
> +JSBigInt* JSBigInt::copy(ExecState& state, JSBigInt* x)

This function seems very similar to the end of JSBigInt::rightTrim, except for using memcpy instead of std::copy.
Is there a reason for using one instead of the other?

> Source/JavaScriptCore/runtime/JSBigInt.cpp:304
> +    ASSERT(!x->isZero());

Is there a good reason not to support zero? This function seems general enough that it may be used in the future with zero, and it does not seem like it would be hard to support.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:598
> +        return diff;

I would like for an ASSERT around here that x and y have non-zero digits in their high-order digits. So that this function would for example not return an anomalous result if it were called in {divide} above on {result} before {rightTrim} were called.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:741
> +        // Caller will right-trim.

What is the reasoning behind this choice? I would tend to minimize the amount of code in which BigInts are non-trimmed.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:761
> +JSBigInt::Digit JSBigInt::inplaceAdd(JSBigInt* summand, unsigned startIndex)

I would like something (either a comment, or even better a change in the function name) that indicates that this is an absoluteInplaceAdd: it completely ignores the bit sign.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:779
> +JSBigInt::Digit JSBigInt::inplaceSub(JSBigInt* subtrahend, unsigned startIndex)

Ditto.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:797
> +    ASSERT(shift >= 0);

shift being unsigned, I don't see how that assertion can be false.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:800
> +    ASSERT(digit(0) & (((static_cast<Digit>(1) << shift) - 1) == 0));

This assertion is a bit hard to read with the binary '&' and non-trivial arithmetic. Is it equivalent to the following two assertions:
ASSERT(digit(0) & 1);
ASSERT((static_cast<Digit>(1) << shift) == 1);
? I don't really understand why it is what it is.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:816
> +// {shift} must be less than digitBits, {x} must be non-zero.

I think I would add an ASSERT(!x->isZero()); and remove this line of comment.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:817
> +JSBigInt* JSBigInt::specialLeftShift(ExecState& state, JSBigInt* x, unsigned shift, SpecialLeftShiftMode mode)

This function does not copy the bit sign, so same point as for inplaceAdd and inplaceSub above.

> JSTests/bigIntTests.yaml:127
> +- path: stress/big-int-div-to-primitive-precedence.js

This file, big-int-div-to-primitive and big-int-div-wrapped value seem to test the same thing to me. Could they be combined in a single file, with the duplicates removed?

[Caio Lima]

Created attachment 339410 [details]
Patch

[EWS Watchlist]

Attachment 339410 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:737:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Caio Lima]

Thank you very much for the review!

(In reply to Robin Morisset from comment #14)
> Comment on attachment 338995 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=338995&action=review
> 
> I am not an official Webkit reviewer, but I have tried to read through your
> patch and have a few comments and questions.
> 
> > Source/JavaScriptCore/runtime/JSBigInt.cpp:298
> > +    quotient->setSign(x->sign() != y->sign());
> 
> Is there a reason not to use resultSign here?

No. Changed it.

> > Source/JavaScriptCore/runtime/JSBigInt.cpp:302
> > +JSBigInt* JSBigInt::copy(ExecState& state, JSBigInt* x)
> 
> This function seems very similar to the end of JSBigInt::rightTrim, except
> for using memcpy instead of std::copy.
> Is there a reason for using one instead of the other?

I will use std::copy to keep consistency.

> > Source/JavaScriptCore/runtime/JSBigInt.cpp:304
> > +    ASSERT(!x->isZero());
> 
> Is there a good reason not to support zero? This function seems general
> enough that it may be used in the future with zero, and it does not seem
> like it would be hard to support.

I don't see use cases where we should copy zero BigInt now, since we can simply use JSBigInt::createZero instead. If it starts to be painful considering zero while copying, we can support that in future patches.
 
> > Source/JavaScriptCore/runtime/JSBigInt.cpp:598
> > +        return diff;
> 
> I would like for an ASSERT around here that x and y have non-zero digits in
> their high-order digits. So that this function would for example not return
> an anomalous result if it were called in {divide} above on {result} before
> {rightTrim} were called.

It is a good idea.

> > Source/JavaScriptCore/runtime/JSBigInt.cpp:741
> > +        // Caller will right-trim.
> 
> What is the reasoning behind this choice? I would tend to minimize the
> amount of code in which BigInts are non-trimmed.

It is the decision of original authors of this implementation. I'm not 100% sure, but I think this decision was taken because of absoluteDivSmall doesn't trim the quotient as well.
 
> > Source/JavaScriptCore/runtime/JSBigInt.cpp:761
> > +JSBigInt::Digit JSBigInt::inplaceAdd(JSBigInt* summand, unsigned startIndex)
> 
> I would like something (either a comment, or even better a change in the
> function name) that indicates that this is an absoluteInplaceAdd: it
> completely ignores the bit sign.

Done.

> > Source/JavaScriptCore/runtime/JSBigInt.cpp:800
> > +    ASSERT(digit(0) & (((static_cast<Digit>(1) << shift) - 1) == 0));
> 
> This assertion is a bit hard to read with the binary '&' and non-trivial
> arithmetic. Is it equivalent to the following two assertions:
> ASSERT(digit(0) & 1);
> ASSERT((static_cast<Digit>(1) << shift) == 1);
> ? I don't really understand why it is what it is.

This assert is verifying if all "shift bits" of digit(0) are 0. If "shift == 3" we would have "(digit(0) & 111) == 0". If we turn this into your 2 assertions, the ASSERT((static_cast<Digit>(1) << shift) == 1) is only true when "shift == 0".

> > JSTests/bigIntTests.yaml:127
> > +- path: stress/big-int-div-to-primitive-precedence.js
> 
> This file, big-int-div-to-primitive and big-int-div-wrapped value seem to
> test the same thing to me. Could they be combined in a single file, with the
> duplicates removed?

ok.

[Caio Lima]

Created attachment 339510 [details]
Patch

[EWS Watchlist]

Attachment 339510 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:740:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Robin Morisset]

Thank you for having addressed my comments. There is only one point where I disagree:

> > > Source/JavaScriptCore/runtime/JSBigInt.cpp:800
> > > +    ASSERT(digit(0) & (((static_cast<Digit>(1) << shift) - 1) == 0));
> > 
> > This assertion is a bit hard to read with the binary '&' and non-trivial
> > arithmetic. Is it equivalent to the following two assertions:
> > ASSERT(digit(0) & 1);
> > ASSERT((static_cast<Digit>(1) << shift) == 1);
> > ? I don't really understand why it is what it is.
> 
> This assert is verifying if all "shift bits" of digit(0) are 0. If "shift ==
> 3" we would have "(digit(0) & 111) == 0". If we turn this into your 2
> assertions, the ASSERT((static_cast<Digit>(1) << shift) == 1) is only true
> when "shift == 0".

It seems like the parenthesis are wrong then. In the case where shift==3, the current assertion seems to be ASSERT(digit(0) & (111 == 0)), not ASSERT((digit(0) & 111) == 0)

[Caio Lima]

(In reply to Robin Morisset from comment #20)
> Thank you for having addressed my comments. There is only one point where I
> disagree:
> 
> > > > Source/JavaScriptCore/runtime/JSBigInt.cpp:800
> > > > +    ASSERT(digit(0) & (((static_cast<Digit>(1) << shift) - 1) == 0));
> > > 
> > > This assertion is a bit hard to read with the binary '&' and non-trivial
> > > arithmetic. Is it equivalent to the following two assertions:
> > > ASSERT(digit(0) & 1);
> > > ASSERT((static_cast<Digit>(1) << shift) == 1);
> > > ? I don't really understand why it is what it is.
> > 
> > This assert is verifying if all "shift bits" of digit(0) are 0. If "shift ==
> > 3" we would have "(digit(0) & 111) == 0". If we turn this into your 2
> > assertions, the ASSERT((static_cast<Digit>(1) << shift) == 1) is only true
> > when "shift == 0".
> 
> It seems like the parenthesis are wrong then. In the case where shift==3,
> the current assertion seems to be ASSERT(digit(0) & (111 == 0)), not
> ASSERT((digit(0) & 111) == 0)

Oops. You are Right. I'm going to fix it.

[Caio Lima]

Created attachment 339608 [details]
Patch

[EWS Watchlist]

Attachment 339608 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:740:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Caio Lima]

Ping review.

[Caio Lima]

Created attachment 340161 [details]
Patch

[EWS Watchlist]

Attachment 340161 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSBigInt.cpp:726:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Yusuke Suzuki]

Comment on attachment 340161 [details]
Patch

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

> Source/JavaScriptCore/runtime/JSBigInt.cpp:516
> +int JSBigInt::absoluteCompare(JSBigInt* x, JSBigInt* y)

Let's make this function `inline`.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:522
> +    if (x->length())
> +        ASSERT(x->digit(0));
> +
> +    if (y->length())
> +        ASSERT(y->digit(0));

Make them `ASSERT(!x->length() || x->digit(0))` and `ASSERT(!y->length() || y->digit(0))`.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:-482
> -    int length = x->length();

What "small" means in absoluteDivSmall? DigitDivisor would be better. So, absoluteDivWithDigitDivisor.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:579
> +void JSBigInt::absoluteDivLarge(ExecState& state, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)

Ditto, please name it more descriptive one. I'm not sure what "absolute" means here.
And what "large" means? `absoluteDivWithBigIntDivisor`?.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:680
> +bool JSBigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low)

Make this function `inline` since it is very small helper function.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:742
> +JSBigInt* JSBigInt::absoluteSpecialLeftShift(ExecState& state, JSBigInt* x, unsigned shift, SpecialLeftShiftMode mode)

What "Special" means? Please name it more descriptive one.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:1093
> +JSBigInt::Digit JSBigInt::digit(unsigned n)

Keep `inline`.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:1099
> +void JSBigInt::setDigit(unsigned n, Digit value)

Keep `inline`.

[Yusuke Suzuki]

Comment on attachment 340161 [details]
Patch

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

>> Source/JavaScriptCore/runtime/JSBigInt.cpp:579
>> +void JSBigInt::absoluteDivLarge(ExecState& state, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)
> 
> Ditto, please name it more descriptive one. I'm not sure what "absolute" means here.
> And what "large" means? `absoluteDivWithBigIntDivisor`?.

Ah, I understand what "absolute" means. I think "absoluteDivWithBigIntDivisor" is better.

[Caio Lima]

Comment on attachment 340161 [details]
Patch

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

Thank you for the review!

>> Source/JavaScriptCore/runtime/JSBigInt.cpp:-482
>> -    int length = x->length();
> 
> What "small" means in absoluteDivSmall? DigitDivisor would be better. So, absoluteDivWithDigitDivisor.

Done.

>>> Source/JavaScriptCore/runtime/JSBigInt.cpp:579
>>> +void JSBigInt::absoluteDivLarge(ExecState& state, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)
>> 
>> Ditto, please name it more descriptive one. I'm not sure what "absolute" means here.
>> And what "large" means? `absoluteDivWithBigIntDivisor`?.
> 
> Ah, I understand what "absolute" means. I think "absoluteDivWithBigIntDivisor" is better.

Large means BigInt divisor. Absolute means that we are not taking the sign in consideration, so we consider everything as positive.

[Caio Lima]

Created attachment 340267 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 340267 [details]
Patch

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

r=me

> Source/JavaScriptCore/runtime/JSBigInt.cpp:295
> +            return resultSign == x->sign() ? x : unaryMinus(state, x);

Pass VM& instead.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:298
> +        absoluteDivWithDigitDivisor(state, x, divisor, &quotient, remainder);

Pass VM& instead.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:300
> +        absoluteDivWithBigIntDivisor(state, x, y, &quotient, nullptr);

Pass VM& instead.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:306
> +JSBigInt* JSBigInt::copy(ExecState& state, JSBigInt* x)

Use VM& parameter instead of ExecState&.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:317
> +JSBigInt* JSBigInt::unaryMinus(ExecState& state, JSBigInt* x)

Use VM& parameter instead of ExecState&.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:579
> +inline int JSBigInt::absoluteCompare(JSBigInt* x, JSBigInt* y)

Use ComparisonResult for the resulted value.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:605
> +void JSBigInt::absoluteDivWithDigitDivisor(ExecState& state, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)

Use VM& parameter instead of ExecState&.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:639
> +void JSBigInt::absoluteDivWithBigIntDivisor(ExecState& state, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)

Use VM& parameter instead of `ExecState&`.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:670
> +        divisor = absoluteLeftShiftAlwaysCopy(state, divisor, shift, SameSizeResult);

Pass VM& instead of ExecState&.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:674
> +    JSBigInt* u = absoluteLeftShiftAlwaysCopy(state, dividend, shift, AlwaysAddOneDigit);

Pass VM& instead of ExecState&.

> Source/JavaScriptCore/runtime/JSBigInt.cpp:802
> +JSBigInt* JSBigInt::absoluteLeftShiftAlwaysCopy(ExecState& state, JSBigInt* x, unsigned shift, LeftShiftMode mode)

Use `VM&` parameter instead since this function does not require `ExecState*`.

> Source/JavaScriptCore/runtime/JSBigInt.h:97
> +    static JSBigInt* divide(ExecState&, JSBigInt* x, JSBigInt* y);

Should take ExecState* to align to the other functions (multiply). In JSC, using ExecState* is more common.

> Source/JavaScriptCore/runtime/JSBigInt.h:102
>      enum ComparisonResult {

Use enum class.

> Source/JavaScriptCore/runtime/JSBigInt.h:133
> +    enum LeftShiftMode {
> +        SameSizeResult,
> +        AlwaysAddOneDigit
> +    };

Use enum class.

[Caio Lima]

Created attachment 340413 [details]
Patch

Let's see the bots.

[Caio Lima]

Created attachment 340463 [details]
Patch for landing

[Caio Lima]

Thank you for the review!!

[WebKit Commit Bot]

Comment on attachment 340463 [details]
Patch for landing

Rejecting attachment 340463 [details] from commit-queue.

Number of test failures exceeded the failure limit.
Full output: http://webkit-queues.webkit.org/results/7695691

[WebKit Commit Bot]

Created attachment 340471 [details]
Archive of layout-test-results from webkit-cq-02 for mac-sierra

The attached test failures were seen while running run-webkit-tests on the commit-queue.
Bot: webkit-cq-02  Port: mac-sierra  Platform: Mac OS X 10.12.6

[WebKit Commit Bot]

Comment on attachment 340463 [details]
Patch for landing

Clearing flags on attachment: 340463

Committed r231845: <https://trac.webkit.org/changeset/231845>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/40293115>

[WebKit Commit Bot]

Re-opened since this is blocked by bug 185702

[Caio Lima]

Created attachment 340550 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 340550 [details]
Patch for landing

Clearing flags on attachment: 340550

Committed r231886: <https://trac.webkit.org/changeset/231886>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Yusuke Suzuki]

Remember ArithDiv can return number only. We need to add ValueDiv too in DFG.