1730843 - Implement the Record and Tuple primitives based on objects

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P3)

Description

[Nicolò Ribaudo]

+++ This bug was initially created as a clone of Bug #1658309 +++

https://github.com/tc39/proposal-record-tuple

I am opening this bug to track an alternative implementation for Bug #1658309 - "Implement the Record and Tuple proposal". Rather than implementing them as three custom new primitive types, they can be implemented as if they were objects but still be exposed to the JS code as if they were primitives.

Comment 1

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 1 - Add support for empty R&T based on objects

This is an alternative implementation to D87232. I didn't implement
object wrappers for these new primitive-like-objects yet, so
typeof Object(rec) is currently "record" and not "object".

Comment 2

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 2 - Add support for elements in tuples

They are internally implemented using as dense elements. After that the tuple is fully initialized it's frozen to prevent modifications.

Depends on D125644

Comment 3

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 3 - Add parser support for records and tuples

This patch adds #{} and #[] support to the parser and to Reflect.parse.
The AST has the same shapre of object and array literals, but the node
names are "RecordExpression" and "TupleExpression".

Since this patch only implements parser support and not bytecode emitter
support, any attempt of evaluating those literals will crash. This is why
I have only used Reflect.parse in the tests.

The ParseNode class sets the hasNonConstInitializerBit flag for records
and tuples, since this will allow us to use a single record/tuple instance
if it's constant but evaluated multiple times.

This patch is effectively the same as D87586

Depends on D125645

Comment 4

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 4 - Add bytecode emitter and interpreter support for tuple literals

This patch introduces three new op codes:

• InitTuple length preallocates a tuple of the given length: this is the final length if the
  tuple doesn't contain spreads, otherwise it's the most pessimisitc choice possible
  (i.e. spreads are assumed to introduce no new elements). The preallocated tuple size
  can still grow if needed.
• AddTupleElement pushes the last value in the stack to the tuple (the second-last stack element)
• FinishTuple marks the tuple as initialized. An unfinished tuple should never leak to JavaScript
  code, and any attempt to get its element will fail.

The bytecode relative to tuple spread is similar to the bytecode used for array spread, emitting
op codes to call the different steps of the iterator protocol.

Depends on D125646

Comment 5

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 5 - Implement === and Object.is support for tuples

This patch implements the SameValueZero (===) and SameValue (Object.is) algorithms for tuples, and adds the equivalent functions for records (they will crash when called).

Depends on D125647

Comment 6

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 6 - Add support for properties in records

This patch adds support for properties in records, when created using the Record({}) function.

Record properties are stored as normal object properties, but there is
an additional sortedKeys internal slot containing an array of all the record
keys sorted alphabetically. This will be necessary when comparing two records
for equality, or when enumerating their properties.

Depends on D125649

Comment 7

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 7 - Implement bytecode/interpreter for record literals

This patch defines the bytecode for record literals, similarly to how it has been implemented for tuple literals:

• InitRecord [length] pushes a new record to the stack, allocating
  memory for length properties
• AddRecordProperty reads the key and the value from the stack,
  and defines it on the record which is being initialized
• FinishRecord freezes a record and sorts its keys

This patch doesn't implement support for spread in record literals yet.

Depends on D125650

Comment 8

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 8 - Add support for spread in records

This is done introducing a new opcode, AddRecordSpread, that
takes a value and defines its enumerable properties on the record
which is currently being initialized.

Depends on D125651

Comment 9

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 9 - Implement === and Object.is support for records

This reuses the same implementation strategy used for tuples

Depends on D125652

Comment 10

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 10 - Add support boxes

This patch implements the third new type introduced by the Records and Tuples proposal: Box.

It implements:

• the "box" primitive type, implemented as an object
• the Box function and its instance methods
• boxes equality

Still missing:

• support for boxes as Map and Set keys
• Box.containBoxes (this function will likely change in the proposal)

Depends on D125654

Comment 11

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 11 - Add support for iterating records

This patch fixes Object.keys in records to return sorted keys, and adds
tests for the other Object.* methods.

Comment 12

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 12 - Add support for iterating tuples

This patch fixes the missing pieces to make enumeration and object
operations work with tuples (they need to be handled
specially in some places because of the contextual prototype).

Depends on D125656

Comment 13

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 13 - Add `JSON.stringify` support for R&T

This patch implements JSON.stringify as specified in the Record and Tuple proposal.

Due to the Box unwrapping logic, balancing between "don't duplicate code" and "keep the R&T code isolated behind the ENABLE_RECORD_TUPLE flag" was tricky: I ended up extracting the code to call toJSON to a separate funcition even
if without the R&T proposal it's used only once.

Depends on D125657

Comment 14

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 14 - Implement `JSON.parseImmutable`

Depends on D125658

Comment 15

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 15 - Implement support for R&T as Map/Set keys

When preparing records, tuples and boxes to be used as a Map/Set key, we
recursively atomize the strings that they contain. This makes it
possible to compute a hash for the whole structure, and to compare them
with an infallible function.

ToDo: Figure out where to store the isAtomized flag for tuples

Depends on D125659

Comment 16

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 16 - Rename {Record,Tuple,Box}Object to {Record,Tuple,Box}Type

This is in preparation of the next patch which will introduce object wrappers

Depends on D125660

Comment 17

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 16 - Add {Record,Tuple,Box}Object wrappers for {Record,Tuple,Box}Type

Depends on D126690

Comment 18

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 17 - Mark R/T/B using a new single value type (`ObjectPrimitive`)

Even if they are still implemented as subclasses of JSObject, representing
them differently in the Value wrapper has a few advantages:

• Checking the equality semantics of an object (deep vs pointer) is faster,
  since we only need to check the Value's bits.
• It's easier to differentiate between R/T/B and R/T/B object wrappers,
  since .isObject() returns false for the "primitives". For example,
  this patch fixes the typeof Object(#{}) tests.

This approach's advantages are the same as what we would get implementing them
as primitives from scratch (https://phabricator.services.mozilla.com/D87232),
but it also allows us to re-use the existing objects optimizations.

Depends on D126691

Comment 19

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 1-bis - Implement object wrappers for records and tuples

Even if R&T are internally implemented as objects, they are still
primitives and they should be have object wrappers:

typeof Tuple() === "tuple"
typeof Object(Tuple()) === "object"

Depends on D125644

Comment 20

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 6-bis - Implement correct handling of record properties

This patch fixes and tests handling of property descriptors for record properties

Depends on D125650

Comment 21

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 6-tris - Fix tuple property descriptors

This patch fixes the missing pieces to make object operations work with tuples.

Depends on D129675

Comment 22

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 16 - Mark R&T object wrappers as frozen

The proposal currently specifies R/T/B wrappers as frozen.

This patch makes them look as if they were frozen, while still internally
keeping them marked as extensible. This allows lazily resolving the
wrapper properties (so that we can avoid a full copy every time we
create the wrapper object), but they are exposed as non-extensible to JS
code.

It's still possible that the proposal will switch to make them mutable;
you can follow the discussion (and participate!) at
https://github.com/tc39/proposal-record-tuple/issues/137.

Depends on D125660

Comment 23

[Matthew Gaudet (he/him) [:mgaudet]]

Hi Anba,

In this patch, Nicolò has encountered some oddity with make_intl_data.py and the resulting headers. Would you mind taking a peek to give a hint on what's going on; I don't really understand what's going on here.

Comment 24

[André Bargull [:anba]]

Sorry about those bugs. I've filed bug 1741220 and bug 1741222 to fix this.

Comment 25

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 17 - Don't use ObjectOps for `ExtendedPrimitive` properties

This is done by not using the NativeGetProperty and NativeDeleteProperty functions for R/T/B, but by creating two new "parallel" functions that handle them specifically.
This is because R/T/B don't behave like classic objects, but they get their prototype lexically (like other primitives).

It's not necessary to reimplement NativeSetProperty, because it always throw since R/T/B are frozen.

Depends on D131124

Comment 26

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 18 - Mark atomized tuples using the elements header

Since tuples use inline elements, they cannot have internal slots and thus we cannot store the IS_ATOMIZED
flag as we do for records and tuples. However, we can store it in a bit of the ObjectElements flags.

Depends on D132367

Comment 27

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 20 - Run Records&Tuples tests on ci

Depends on D132393

Comment 28

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 17-bis - Avoid branching between objects/records in `JO`

The code for converting records and objects to strings would be almost identical:
to avoid dynamic branches I converted them to if constexpr statements.

I also found that we didn't have a test for boxed R&T (only for boxes Box).

Ref https://phabricator.services.mozilla.com/D132367#inline-730448

Depends on D132367

Comment 29

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 19 - Fix IsExtendedPrimitive check for forwarded objects

This patch fixes a regression introduced by the --enable-record-tuple build flag, which made
https://searchfox.org/mozilla-central/source/js/src/tests/non262/template-strings/bug1559123.js
crash because the IsExtendedPrimitive doesn't work with forwarded objects.

This patch introduces a new gc::MaybeForwardedIsExtendedPrimitive function, similar to
the existing gc::MaybeForwardedObjectIs one.

Depends on D132393

Comment 30

[Phabricator Automation]

Comment on attachment 9253022 [details]
Bug 1730843 - Part 20 - Run Records&Tuples tests on ci

Revision D132467 was moved to bug 1744967. Setting attachment 9253022 [details] to obsolete.

Comment 31

[Nicolò Ribaudo]

Attachment: Bug 1730843 - Part 20 - Remove Box from the Record&Tuple implementation

After the feedback received at the Dec 2021 TC39 meeting, it's very unlikely
that the proposal will include Box. This patch removes it so that the
rest of the R&T implementation can be merged.

Comment 32

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/ffe0bb1cf293
Part 1 - Add support for empty R&T based on objects r=jandem
https://hg.mozilla.org/integration/autoland/rev/a8299b7a31fb
Part 1-bis - Implement object wrappers for records and tuples r=jandem
https://hg.mozilla.org/integration/autoland/rev/392c8d7d8ca0
Part 2 - Add support for elements in tuples r=mgaudet,jandem
https://hg.mozilla.org/integration/autoland/rev/f9064fa3d5a9
Part 3 - Add parser support for records and tuples r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/8357f3e24b2b
Part 4 - Add bytecode emitter and interpreter support for tuple literals r=jandem
https://hg.mozilla.org/integration/autoland/rev/2a468171b056
Part 5 - Implement === and Object.is support for tuples r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/c0a945467649
Part 6 - Add support for properties in records r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/dd527f2cda3e
Part 6-bis - Implement correct handling of record properties r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/db55cc5e622f
Part 7 - Implement bytecode/interpreter for record literals r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/084f3f116de4
Part 8 - Add support for spread in records r=jandem
https://hg.mozilla.org/integration/autoland/rev/364f21c8f9d9
Part 9 - Implement === and Object.is support for records r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/85bcb1310053
Part 11 - Add support for iterating records r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/117538978e60
Part 12 - Add support for iterating tuples r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/2a2a3a3e7f89
Part 13 - Add `JSON.stringify` support for R&T r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/2e0010e8acde
Part 14 - Implement `JSON.parseImmutable` r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/5820e13028f9
Part 15 - Implement support for R&T as Map/Set keys r=jandem
https://hg.mozilla.org/integration/autoland/rev/2ad3c818ecd8
Part 16 - Mark R&T object wrappers as frozen r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/2e211a594b05
Part 17 - Don't use ObjectOps for `ExtendedPrimitive` properties r=jandem
https://hg.mozilla.org/integration/autoland/rev/b15d9ea6fcd4
Part 17-bis - Avoid branching between objects/records in `JO` r=jandem
https://hg.mozilla.org/integration/autoland/rev/9999c06e4fbe
Part 18 - Mark atomized tuples using the elements header r=jandem
https://hg.mozilla.org/integration/autoland/rev/3f37e6c2e61f
Part 19 - Fix IsExtendedPrimitive check for forwarded objects r=jandem

Comment 33

[Marian-Vasile Laza]

https://hg.mozilla.org/mozilla-central/rev/ffe0bb1cf293
https://hg.mozilla.org/mozilla-central/rev/a8299b7a31fb
https://hg.mozilla.org/mozilla-central/rev/392c8d7d8ca0
https://hg.mozilla.org/mozilla-central/rev/f9064fa3d5a9
https://hg.mozilla.org/mozilla-central/rev/8357f3e24b2b
https://hg.mozilla.org/mozilla-central/rev/2a468171b056
https://hg.mozilla.org/mozilla-central/rev/c0a945467649
https://hg.mozilla.org/mozilla-central/rev/dd527f2cda3e
https://hg.mozilla.org/mozilla-central/rev/db55cc5e622f
https://hg.mozilla.org/mozilla-central/rev/084f3f116de4
https://hg.mozilla.org/mozilla-central/rev/364f21c8f9d9
https://hg.mozilla.org/mozilla-central/rev/85bcb1310053
https://hg.mozilla.org/mozilla-central/rev/117538978e60
https://hg.mozilla.org/mozilla-central/rev/2a2a3a3e7f89
https://hg.mozilla.org/mozilla-central/rev/2e0010e8acde
https://hg.mozilla.org/mozilla-central/rev/5820e13028f9
https://hg.mozilla.org/mozilla-central/rev/2ad3c818ecd8
https://hg.mozilla.org/mozilla-central/rev/2e211a594b05
https://hg.mozilla.org/mozilla-central/rev/b15d9ea6fcd4
https://hg.mozilla.org/mozilla-central/rev/9999c06e4fbe
https://hg.mozilla.org/mozilla-central/rev/3f37e6c2e61f