1658309 - [meta] Record and Tuple proposal

Status: NEW

(Core :: JavaScript Engine, enhancement, P3)

Description

[Yulia Startsev [:yulia]]

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

The proposal is currently on Stage 2.

Comment 1

[Nicolò Ribaudo]

I'm currently working on a prototype implementation.

Comment 2

[Nicolò Ribaudo]

Attachment: Bug 1658309 - Part 1 - Create the "record" and "tuple" primitves, and their wrappers

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

NOTE: These changes are behind a compile-time flag, --enable-record-tuple

This patch introduces two new JavaScript types: "record" and "tuple", implemented in the
new vm/RecordType and vm/TupleType classes. It also introduces a basic version of their
Record and Tuple JavaScript wrapper objects, so that it's already possible to create
the two new types from the JS shell.

Only empty records and tuples are supported, and their syntax is not supported yet.

Comment 3

[Nicolò Ribaudo]

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

This patch extends the tuples support allowing them to contain
primitive elements.

Both primitive and wrapped tuples support accessing integer-indexed
properties, while the .length accessor is only supported by unwrapped
tuples. It will be implemented for wrapped tuples when adding support
for the other .prototype methods.

Comment 4

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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.

Depends on D87272

Comment 5

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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 D87586

Comment 6

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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).

Comment 7

[Nicolò Ribaudo]

I have been working on this again, and I have a complete implementation for the current status of the proposal. It's completely unoptimized, doesn't support Jit, and doesn't reuse any existing Object/Array code paths for Records and Tuples.

I'll upload it to phabricator continuing the stack I uploaded last year. In the meantime I'm experimenting with a different implementation strategy that internally implements R&T as if they were objects instead of primitives (but they are still exposed as primitives to the user).

Comment 8

[Nicolò Ribaudo]

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

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

Properties are stored as a vector of key-value pairs, sorted
alphabetically. This patch doesn't make the order observable yet, but it
will be important when implementing records equality and support for
the Object.* reflection functions.

Comment 9

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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 marks a record as initialized, going from write-only
  to read-only mode

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

Comment 10

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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.

Comment 11

[Nicolò Ribaudo]

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

This reuses the same implementation strategy used for tuples

Comment 12

[Nicolò Ribaudo]

Attachment: Bug 1658309 - Part 10 - Add support boxes

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

It implements:

• the "box" primitive type
• 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)

Comment 13

[Nicolò Ribaudo]

Attachment: Bug 1658309 - Part 11 - Implement internal object methods for Record

This patch implements Record support for the various internal object
methods, such as [[GetOwnProperty]], so that defineProperty,
hasOwnProperty, propertyIsEnumerable, keys, etc. work.

Comment 14

[Nicolò Ribaudo]

Attachment: Bug 1658309 - Part 12 - Implement internal object methods for Tuple

This patch implements Tuple support for the various internal object
methods, such as [[GetOwnProperty]], so that defineProperty,
hasOwnProperty, propertyIsEnumerable, keys, etc. work.

Comment 15

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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.

Comment 16

[Nicolò Ribaudo]

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

Comment 17

[Nicolò Ribaudo]

Attachment: Bug 1658309 - 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.

Comment 18

[Yulia Startsev [:yulia]]

Is this ready for review?

Comment 19

[Nicolò Ribaudo]

Hi! Yes, this is ready for review.

The implementation currently supports the proposal as it's specified today, except for all the Tuple.prototype.* methods (we are working on it). Also, I didn't add jit support yet: when the --record-and-tuple build flag is enabled, it automatically disables jit and it only uses the interpreter.

I am also working on a parallel stack to show an alternative implementation based from some feedback we got from your team last year: rather than implementing them as primitives, I implemented them internally using objects.

Comment 20

[Nicolò Ribaudo]

Bug #1730843

Comment 21

[Nicolò Ribaudo]

I wrote on Matrix this comparison between the "real primitives" and the "object-based primitives". I'm cross-posting it here so that it doesn't get lost.

---

Implementing them as object was way easier.

• I didn't have to change some bit patterns of the other primitives to make room for three new ones. I felt like there is a limit of how many primitives we can have (unless we do a big refactoring), but with R/T/B I still didn't hit this limit and it's hard for me to predict what it is.
• Most of the logic was already there, and probably it's already faster: for example, accessing record fields is (I think) O(1) rather than O(n) - at least for small records.
• The JIT in the object-based stack is disabled because I didn't check yet how it works with equality, but I expect it to already work "for free" for record property access. On the other hand, the jit for primitive-based R&T must probably be written from scratch.

However, I think that the primitives version can be optimized in R&T-specific ways that it might be harder or impossible.

• One example is interning: with boxes and with the +0/-0 equality we can still intern, but we need to intern different parts of the immutable strucure separately. Specifically, we can track "normal values" separately from boxes and zeroes, and only intern the "normal values" part. I tried thinking about how it could work at https://excalidraw.com/#json=5321061461655552,XTvh_y9dGjsgVeJR0PNKsA, but I didn't actually experiment with an implementation yet.
• I think it might be easier in the future to share R&T without boxes accross threads if we use primitives, but this is just a speculation I'm making since they don't have all the special cases that objects have

Also, with object-based R/T/B we must be careful about the dinstinction between ""primitives"" and their box objects. There are many places in the spec where primitives should be wrapped (for example, Object.prototype.valueOf(#{}) should return an object). When using primitives this is easy: any C++ function that expects an object will refuse anything with a type which is not JSObject*. When using object-based primitives, the C++ type-checker doesn't help and we must "manually" verify that we don't accidentally forget wrapping the R/T/B somewhere.

iain: Yes, I needed to add an extra check. However, this is similar to how we already have to check the type of a value to determine that it's an object, before comparing its pointer. You can see it at https://phabricator.services.mozilla.com/D125649#change-k4u2kzSwvSjZ

Comment 22

[Nicolò Ribaudo]

I split the proposal implementation in multiple (self-contained) bugs

• Introduce the new primitives
• Add jit support
• Implement the Tuple.prototype methods

I'm using this one as "umbrella" which depends on all of them.

Comment 23

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.

Comment 24

[Tim Chevalier]

This bug can be reassigned to me.