Bug 216667

Summary: [JSC] BigInt should work with Map / Set
Product: WebKit Reporter: Dwight House <dwighthouse>
Component: JavaScriptCoreAssignee: Yusuke Suzuki <ysuzuki>
Status: RESOLVED FIXED    
Severity: Normal CC: alecflett, beidson, benjamin, cdumez, cmarcelo, ews-watchlist, fpizlo, jsbell, keith_miller, mark.lam, msaboff, rmorisset, saam, tzagallo, webkit-bug-importer, ysuzuki
Priority: P2 Keywords: InRadar
Version: Safari Technology Preview   
Hardware: Mac   
OS: macOS 10.15   
Attachments:
Description Flags
Demonstration Script and Expected Output
none
Patch
none
Patch
none
Patch
rmorisset: review+
Patch none

Description Dwight House 2020-09-17 15:14:35 PDT 
Created attachment 409070 [details]
Demonstration Script and Expected Output

# Feature Background

* BigInts store arbitrarily large integers as a primitive data type, where they may be constructed with a `BigInt` function or by using new syntax of appending an `n` to an integer number.
  - BigInt support just landed on Desktop Safari ( https://developer.apple.com/documentation/safari-release-notes/safari-14-beta-release-notes#JavaScript ).
  - My version: 14.0 (15610.1.28.1.9, 15610).
    - I did download the latest WebKit Build Archives version as of the writing of this ticket and found the issue to still be present, though it was hard to tell due to Catalina's aggressive attempts to prevent it from running.
* Maps store key-value pairs, where keys must be unique and their equality is judged by sameValueZero ( https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map#Description ).
* Sets store values, where values must be unique and their equality is judged by sameValueZero ( https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set ).



# Problem Discovery

I was working on my json-complete library and found an error in my tests that only appeared to affect Safari, which had just been updated this morning.
  - json-complete - https://github.com/cierelabs/json-complete
  - The library saves some space in the output encoded string by deduplicating equal values.
  - My deduplication tests failed on Safari when dealing with BigInt.
  - Tracking this down, I discovered that multiple "equal" BigInt values were not being treated as equal in my Map object, which forms the core of that part of the library.
  - This is unacceptable because it will allow for a situation where Safari browsers using my library can sometimes create a different output for the exact same data, even if the versions are identical.
  - To work around this, I would have to add an exception for BigInt types that requires either all data or just BigInt data to fall back to the slower methodology of checking value equality of every previous entry when trying to deduplicate items.



# Issue Description

* Safari 14 appears to sometimes treat function-constructed BigInt values as non-equal to equal BigInt values for the purposes of deduplication in Map keys and Set values.
* Additionally, the "sometimes" aspect of this non-equality appears to be a race-condition, as the way in which Safari will incorrectly store duplicate entries varies from page load to page load.
* In my testing, it is always wrong, but how wrong it is varies.
* Finally, the order of the incorrect insertions are also incorrect. Occasionally, the output will show entries out of order, even if BigInt values were not strictly value-equal to each other.
* This issue is not present in Google Chrome, Mozilla Firefox, and Brave.



# Expected Behavior

1. When adding a new key-value pair with the same BigInt value as the key as a previous entry, regardless of being constructed with a function or the new syntax, the Map should store only the last added key-value pair that uses that BigInt key. There should not be duplicates and the values of the same key entry should always be overwritten.
2. When adding a new value with the same BigInt value as a previous value, regardless of being constructed with a function or the new syntax, the Set should only store the last added BigInt of that value. There should not be duplicates.



# Actual Behavior

1. Some number of duplications of the same BigInt key will be stored in the Map. The times this occurs varies from page load to page load.
2. Some number of duplications of the same BigInt value will be stored in the Map. The times this occurs varies from page load to page load.



# Samples of Incorrect Output

As noted above, I get different incorrect results per page load. Here are some examples of different variants:

```
Map:
[
    0, zero 4
    0, BigInt zero 4
    1, BigInt one function 1
    1, BigInt one function 2
    1, BigInt one function 3
    1, BigInt one function 4
    1, BigInt one
]

Set:
[
    0
    0
    1
    1
]
```

```
Map:
[
    0, zero 4
    0, BigInt zero 4
    1, BigInt one function 1
    1, BigInt one
    1, BigInt one function 3
    1, BigInt one function 4
]

Set:
[
    0
    0
    1
    1
    1
]
```

```
Map:
[
    0, zero 4
    0, BigInt zero 4
    1, BigInt one function 1
    1, BigInt one function 2
    1, BigInt one function 3
    1, BigInt one
]

Set:
[
    0
    0
    1
    1
]
```



# Steps to Reproduce

* Please see sample code provided in the attached file, which demonstrates both problems.
* Reload the page multiple times in Safari to see the variances.
Comment 1 Radar WebKit Bug Importer 2020-09-17 17:18:23 PDT 
<rdar://problem/69107221>
Comment 2 Yusuke Suzuki 2020-09-20 01:55:29 PDT 
Created attachment 409226 [details]
Patch
Comment 3 Yusuke Suzuki 2020-09-20 02:19:12 PDT 
Created attachment 409227 [details]
Patch
Comment 4 Mark Lam 2020-09-20 09:35:22 PDT 
Comment on attachment 409227 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:2381
> +            else if (node->child2()->shouldSpeculateInt32())

typo: shouldSpeculateBigInt32
Comment 5 Yusuke Suzuki 2020-09-20 13:15:44 PDT 
Comment on attachment 409227 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:2381
>> +            else if (node->child2()->shouldSpeculateInt32())
> 
> typo: shouldSpeculateBigInt32

Oops. Fixed.
Comment 6 Yusuke Suzuki 2020-09-20 13:16:32 PDT 
Created attachment 409246 [details]
Patch
Comment 7 Robin Morisset 2020-09-21 10:44:36 PDT 
Comment on attachment 409246 [details]
Patch

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

r=me, thanks for this patch!

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1384
> +        SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only) | SpecHeapBigInt;

This looks like it is fixing a different bug? Maybe worth mentioning in the Changelog.

> Source/JavaScriptCore/dfg/DFGDoesGC.cpp:520
> +#if USE(BIGINT32)

This is a small unrelated optimization, right? (since doesGC is conservative)
Comment 8 Yusuke Suzuki 2020-09-21 11:32:47 PDT 
Comment on attachment 409246 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1384
>> +        SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only) | SpecHeapBigInt;
> 
> This looks like it is fixing a different bug? Maybe worth mentioning in the Changelog.

No. After this change, NormalizeMapKey needs to convert JSBigInt to BigInt32 if (1) BigInt32 is supported and (2) JSBigInt's value is in range of BigInt32.
So, NormalizeMapKey's AI conversion rule should care this case. This is part of (1) change in ChangeLog.

>> Source/JavaScriptCore/dfg/DFGDoesGC.cpp:520
>> +#if USE(BIGINT32)
> 
> This is a small unrelated optimization, right? (since doesGC is conservative)

I think this is good. Since we should maintain the rules of DoesGC when we changed the behavior. And after this patch, BigInts are supported in MapHash correctly. So this is good timing to list up here :)
Comment 9 Yusuke Suzuki 2020-09-21 13:46:25 PDT 
Comment on attachment 409246 [details]
Patch

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

> Source/JavaScriptCore/runtime/JSBigInt.cpp:3059
> +unsigned JSBigInt::concurrentHash()
> +{
> +    Hasher hasher;
> +    WTF::add(hasher, m_sign);
> +    for (unsigned index = 0; index < length(); ++index)
> +        WTF::add(hasher, digit(index));
> +    return hasher.hash();
> +}

Temporary disable this (concurrentHash) since I'm not sure about the story between storage data and concurrent compiler thread read. We should fix it. Add FIXME.
Comment 10 Yusuke Suzuki 2020-09-21 15:10:30 PDT 
Committed r267373: <https://trac.webkit.org/changeset/267373>
Comment 11 Saam Barati 2020-09-22 08:33:42 PDT 
Comment on attachment 409246 [details]
Patch

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

LGTM overall too, but I have some comments

>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1384
>>> +        SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only) | SpecHeapBigInt;
>> 
>> This looks like it is fixing a different bug? Maybe worth mentioning in the Changelog.
> 
> No. After this change, NormalizeMapKey needs to convert JSBigInt to BigInt32 if (1) BigInt32 is supported and (2) JSBigInt's value is in range of BigInt32.
> So, NormalizeMapKey's AI conversion rule should care this case. This is part of (1) change in ChangeLog.

Yeah, this looks right to me.

But maybe this variable could be renamed to something like "typesNeedingNormalization" or "typesThatNeedNormalization" to be less confusing.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12547
> +    addSlowPathGenerator(slowPathCall(slowPath, this, operationNormalizeMapKey, resultRegs, &vm(), keyRegs));

since this is just for heap big int, should we specialize  "operationNormalizeMapKey" to not have to do  type checks, etc (and to name it like "operationNormalizeMapKeyHeapBigInt")?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4465
> +            callOperation(operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR);

should we specialize operationMapHash to be over BigInt?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4466
> +            m_jit.exceptionCheck();

can this throw for HeapBigInt?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4495
> +                addSlowPathGenerator(slowPathCall(isHeapBigInt, this, operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR));

ditto about specializing

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4549
> +        addSlowPathGenerator(slowPathCall(isHeapBigInt, this, operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR));

ditto about specializing it.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4641
> +            auto isBucketString = m_jit.branchIfString(bucketGPR);

nit: I'd have named this  "bucketIsString"

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4645
> +            slowPathCases.append(m_jit.branchIfHeapBigInt(keyGPR));

why do we need the branch here? Isn't this guaranteed to be the case since we're the fall through from branchIfNotHeapBigInt

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4679
> +            loopAround.append(m_jit.branchIfNotHeapBigInt(bucketGPR));
> +            // bucket is HeapBigInt.
> +            slowPathCases.append(m_jit.branchIfHeapBigInt(keyGPR));

isn't the second branch proven true by the first?

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11270
> +            LBasicBlock notStringHeapBigIntCase = m_out.newBlock();

nit: I'd name this "notStringNorHeapBigIntCase"

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11286
> +            ValueFromBlock heapBigIntResult = m_out.anchor(m_out.castToInt32(vmCall(Int64, operationMapHash, weakPointer(globalObject), value)));

ditto about specializing a call of operationMapHash for HeapBigInt

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11372
> +        m_out.branch(isNotHeapBigInt(key), unsure(continuation), unsure(isHeapBigIntCase));

should  we use provenType in isNotHeapBigInt here?

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11375
> +        ValueFromBlock bigIntResult = m_out.anchor(vmCall(Int64, operationNormalizeMapKey, m_vmValue, key));

ditto about specializing

>> Source/JavaScriptCore/runtime/JSBigInt.cpp:3059
>> +}
> 
> Temporary disable this (concurrentHash) since I'm not sure about the story between storage data and concurrent compiler thread read. We should fix it. Add FIXME.

Why wouldn't it work? Aren't BigInts immutable?

Also, do we have place to cache the result of the hash inline somewhere?
Comment 12 Yusuke Suzuki 2020-09-22 13:33:41 PDT 
Comment on attachment 409246 [details]
Patch

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

>>> Source/JavaScriptCore/runtime/JSBigInt.cpp:3059
>>> +}
>> 
>> Temporary disable this (concurrentHash) since I'm not sure about the story between storage data and concurrent compiler thread read. We should fix it. Add FIXME.
> 
> Why wouldn't it work? Aren't BigInts immutable?
> 
> Also, do we have place to cache the result of the hash inline somewhere?

immutable, but we are not ensuring when this baking process is done when it is exposed to concurrent compilers. And I'm not 100% confident. This should be done in a separate patch with careful investigation.
And m_hash is added in the landed patch.
Comment 13 Yusuke Suzuki 2020-09-26 01:33:24 PDT 
Comment on attachment 409246 [details]
Patch

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

>>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1384
>>>> +        SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only) | SpecHeapBigInt;
>>> 
>>> This looks like it is fixing a different bug? Maybe worth mentioning in the Changelog.
>> 
>> No. After this change, NormalizeMapKey needs to convert JSBigInt to BigInt32 if (1) BigInt32 is supported and (2) JSBigInt's value is in range of BigInt32.
>> So, NormalizeMapKey's AI conversion rule should care this case. This is part of (1) change in ChangeLog.
> 
> Yeah, this looks right to me.
> 
> But maybe this variable could be renamed to something like "typesNeedingNormalization" or "typesThatNeedNormalization" to be less confusing.

Changed.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12547
>> +    addSlowPathGenerator(slowPathCall(slowPath, this, operationNormalizeMapKey, resultRegs, &vm(), keyRegs));
> 
> since this is just for heap big int, should we specialize  "operationNormalizeMapKey" to not have to do  type checks, etc (and to name it like "operationNormalizeMapKeyHeapBigInt")?

Added operationNormalizeMapKeyHeapBigInt

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4465
>> +            callOperation(operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR);
> 
> should we specialize operationMapHash to be over BigInt?

Added operationMapHashHeapBigInt.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4466
>> +            m_jit.exceptionCheck();
> 
> can this throw for HeapBigInt?

If it is operationMapHash, we should insert check. We should not rely on the internal implementation detail.
If we specialize it to operationMapHashHeapBigInt, we can remove it.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4495
>> +                addSlowPathGenerator(slowPathCall(isHeapBigInt, this, operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR));
> 
> ditto about specializing

Added.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4549
>> +        addSlowPathGenerator(slowPathCall(isHeapBigInt, this, operationMapHash, resultGPR, TrustedImmPtr::weakPointer(m_graph, m_graph.globalObjectFor(node->origin.semantic)), inputGPR));
> 
> ditto about specializing it.

Added.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4641
>> +            auto isBucketString = m_jit.branchIfString(bucketGPR);
> 
> nit: I'd have named this  "bucketIsString"

Changed.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4645
>> +            slowPathCases.append(m_jit.branchIfHeapBigInt(keyGPR));
> 
> why do we need the branch here? Isn't this guaranteed to be the case since we're the fall through from branchIfNotHeapBigInt

No. We tested bucketGPR. This is testing keyGPR.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:4679
>> +            slowPathCases.append(m_jit.branchIfHeapBigInt(keyGPR));
> 
> isn't the second branch proven true by the first?

No, this is for keyGPR. The first one is bucketGPR.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11270
>> +            LBasicBlock notStringHeapBigIntCase = m_out.newBlock();
> 
> nit: I'd name this "notStringNorHeapBigIntCase"

Changed.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11286
>> +            ValueFromBlock heapBigIntResult = m_out.anchor(m_out.castToInt32(vmCall(Int64, operationMapHash, weakPointer(globalObject), value)));
> 
> ditto about specializing a call of operationMapHash for HeapBigInt

Added.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11372
>> +        m_out.branch(isNotHeapBigInt(key), unsure(continuation), unsure(isHeapBigIntCase));
> 
> should  we use provenType in isNotHeapBigInt here?

provenType is added in the landed patch :)

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:11375
>> +        ValueFromBlock bigIntResult = m_out.anchor(vmCall(Int64, operationNormalizeMapKey, m_vmValue, key));
> 
> ditto about specializing

Added.
Comment 14 Yusuke Suzuki 2020-09-26 01:47:57 PDT 
Reopening to attach new patch.
Comment 15 Yusuke Suzuki 2020-09-26 01:47:58 PDT 
Created attachment 409772 [details]
Patch
Comment 16 Yusuke Suzuki 2020-09-26 12:52:22 PDT 
Committed r267624: <https://trac.webkit.org/changeset/267624>