Open Bug 1658309 Opened 2 years ago Updated 11 days ago

[meta] Record and Tuple proposal

Categories

(Core :: JavaScript Engine, enhancement, P3)

enhancement

Tracking

()

People

(Reporter: yulia, Unassigned)

References

(Depends on 5 open bugs, Blocks 1 open bug, )

Details

(Keywords: dev-doc-needed, meta)

Attachments

(15 obsolete files)

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

The proposal is currently on Stage 2.

I'm currently working on a prototype implementation.

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.

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.

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

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

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

Assignee: nobody → nribaudo1
Status: NEW → ASSIGNED
Assignee: nribaudo1 → nicolo.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).

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.

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.

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.

This reuses the same implementation strategy used for tuples

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)

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

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

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.

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.

Is this ready for review?

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.

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

Attachment #9170319 - Attachment is obsolete: true
Attachment #9170374 - Attachment is obsolete: true
Attachment #9170927 - Attachment is obsolete: true
Attachment #9171182 - Attachment is obsolete: true
Attachment #9171221 - Attachment is obsolete: true
Attachment #9234404 - Attachment is obsolete: true
Attachment #9234407 - Attachment is obsolete: true
Attachment #9234408 - Attachment is obsolete: true
Attachment #9234411 - Attachment is obsolete: true
Attachment #9234412 - Attachment is obsolete: true
Attachment #9234413 - Attachment is obsolete: true
Attachment #9234417 - Attachment is obsolete: true
Attachment #9234418 - Attachment is obsolete: true
Attachment #9234421 - Attachment is obsolete: true
Attachment #9234422 - Attachment is obsolete: true

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.

Depends on: 1765278
Keywords: meta
Summary: Implement the Record and Tuple proposal → [meta] Record and Tuple proposal

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

Assignee: nicolo.ribaudo → nobody
Status: ASSIGNED → NEW

This bug can be reassigned to me.

Depends on: 1777761
Depends on: 1781128
Depends on: 1782334
You need to log in before you can comment on or make changes to this bug.