Index conversion in ArrayAccumulation

[GeorgNeis]

ArrayAccumulation computes the array index via ToString(ToUint32(nextIndex+padding)). This means the index may become 2^32-1. But that's not a valid array index anymore since it is the max value of the length property.

[littledan]

What should the behavior be here? I imagine it would be pretty confusing if an Array actually had more than 2^32 elements and the property definitions wrapped around (rather than just overflowing as ordinary property definitions that happen to have property keys which look like numbers, and don't affect the length).

At the same time, I imagine many ECMAScript implementations run into resource limitations when processing such long literals or spreads (this seems to be the case with a version of V8 and SpiderMonkey that I tested long spreads with; maybe that's why you're filing this issue).

I wonder if we should instead throw an SyntaxError when Array literals are longer than 2^32-1, and a RangeError when spreads make an Array literal longer than that length at runtime. The change is likely to be web-compatible due to the resource limitations of these engines.

[littledan]

What should the behavior be here? I imagine it would be pretty confusing if an Array actually had more than 2^32 elements and the property definitions wrapped around (rather than just overflowing as ordinary property definitions that happen to have property keys which look like numbers, and don't affect the length).

At the same time, I imagine many ECMAScript implementations run into resource limitations when processing such long literals or spreads (this seems to be the case with a version of V8 and SpiderMonkey that I tested long spreads with; maybe that's why you're filing this issue).

I wonder if we should instead throw an SyntaxError when Array literals are longer than 2^32-1, and a RangeError when spreads make an Array literal longer than that length at runtime. The change is likely to be web-compatible due to the resource limitations of these engines.

[GeorgNeis]

I'm very much in favor of throwing once the index reaches 2^32-1. But for simplicity I'd prefer to always throw a RangeError. The distinction you made is not as clear as it sounds.

[GeorgNeis]

I'm very much in favor of throwing once the index reaches 2^32-1. But for simplicity I'd prefer to always throw a RangeError. The distinction you made is not as clear as it sounds.

[littledan]

OK, we already have parse-time ReferenceErrors, so I don't see the problem with a parse-time RangeError. Does anyone else? Any hesitation about restricting the length of array literals this way?

[littledan]

OK, we already have parse-time ReferenceErrors, so I don't see the problem with a parse-time RangeError. Does anyone else? Any hesitation about restricting the length of array literals this way?

[ljharb]

One thing i like about this approach is that it would necessitate a test262 test that ensures implementations do parse literals that are of 2^32 - 1 items (along with one that ensures it throws at 2^32).

[ljharb]

One thing i like about this approach is that it would necessitate a test262 test that ensures implementations do parse literals that are of 2^32 - 1 items (along with one that ensures it throws at 2^32).

[littledan]

I don't see why it would necessitate that (any more than the current specification does). Resource limitations are outside of the scope of the specification, before and after this change. This change would just add an upper bound.

[littledan]

I don't see why it would necessitate that (any more than the current specification does). Resource limitations are outside of the scope of the specification, before and after this change. This change would just add an upper bound.

[allenwb]

The only way this would happen in the real world would be by spreading a run-away iterator. But if it does occur, what happens is fully-specified by exotic array's
[[DefineOwnProperty]].

Note that the behavior would be the same as if Array.from was used with the same iterator. (Except that Array.from imposes a MAX_SAFE_INTERGER limit, to accommodate array subclasses that don't have the 2³²-1 limit).

We discussed such design issues during ES6 development and the consensus was to preserve legacy wrapper behavior for built-in array objects. You get the same results from spending an iterator that produces 2³³ zeros and a writing a for loop that uses an assignment to set the elements of an array from the same iterator.

[allenwb]

The only way this would happen in the real world would be by spreading a run-away iterator. But if it does occur, what happens is fully-specified by exotic array's
[[DefineOwnProperty]].

Note that the behavior would be the same as if Array.from was used with the same iterator. (Except that Array.from imposes a MAX_SAFE_INTERGER limit, to accommodate array subclasses that don't have the 2³²-1 limit).

We discussed such design issues during ES6 development and the consensus was to preserve legacy wrapper behavior for built-in array objects. You get the same results from spending an iterator that produces 2³³ zeros and a writing a for loop that uses an assignment to set the elements of an array from the same iterator.

[littledan]

@allenwb If the current semantics are by design, I'm curious what you think of the bug at the top of the thread here. Do we really intend to wrap around at one greater than the maximum Array index? I'd imagine either not wrapping (and creating arbitrarily many post-Array properties) or wrapping after exceeding 2^31-2 (so no property ever fails to update length).

[littledan]

@allenwb If the current semantics are by design, I'm curious what you think of the bug at the top of the thread here. Do we really intend to wrap around at one greater than the maximum Array index? I'd imagine either not wrapping (and creating arbitrarily many post-Array properties) or wrapping after exceeding 2^31-2 (so no property ever fails to update length).

[allenwb]

OK, I think I see what happened. There was a bug in the ES2015 spec. which was made worse by a subsequent attempt to fix the bug.

Let's start with three axioms:

1. numeric keys ≥ 2³²-1 are not recognized as "array indexes". So when a property is defined on an exotic array object with such a key an ordinary (non-array element) property is created and the value of the length property is not automatically updated.
2. Prior to ES2015 Array.prototype methods, don't (directly) do ToUInt32 conversions on array indices. Any necessary conversions happen in the internal methods of Array exotic objects. ES2015 and subsequent editions didn't change this. (That is fine, it's not the bug.) That means that when these Array methods are forced to create array indices ≥ 2³²-1 on an exotic array yhey will create ordinary properties.
3. The intend of ArrayAccumulation for spread operators is that it should operate similarly to an equivalent operation using a for loop which is also similar to how the built-in array methods operate.

So now, the bug: For axiom 3 to work, the actual computed index (possibly ≥ 2³²-1) must be passed into [[Set]] or [[DefineOwnProperty]] without performing ToUint32 conversion. Just like in the legacy array methods. In the ES2015 spec. that is indeed the case for the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. However, the other ElementList : Elision_opt AssignmentExpression and ElementList : ElementList , Elision_opt AssignmentExpression ArrayAccumulation algorithms both did an explicit ToUint32 conversion on the array index before calling CreateDataProperty. That's original ES2015 bug.

Apparently at some point subsequent to ES2015, somebody notices this inconsistency and fixed it by adding a ToUint32 to the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. That was the wrong fix. The correct fix would have been to remove the ToUnit32 conversions there were the original bug.

[allenwb]

OK, I think I see what happened. There was a bug in the ES2015 spec. which was made worse by a subsequent attempt to fix the bug.

Let's start with three axioms:

1. numeric keys ≥ 2³²-1 are not recognized as "array indexes". So when a property is defined on an exotic array object with such a key an ordinary (non-array element) property is created and the value of the length property is not automatically updated.
2. Prior to ES2015 Array.prototype methods, don't (directly) do ToUInt32 conversions on array indices. Any necessary conversions happen in the internal methods of Array exotic objects. ES2015 and subsequent editions didn't change this. (That is fine, it's not the bug.) That means that when these Array methods are forced to create array indices ≥ 2³²-1 on an exotic array yhey will create ordinary properties.
3. The intend of ArrayAccumulation for spread operators is that it should operate similarly to an equivalent operation using a for loop which is also similar to how the built-in array methods operate.

So now, the bug: For axiom 3 to work, the actual computed index (possibly ≥ 2³²-1) must be passed into [[Set]] or [[DefineOwnProperty]] without performing ToUint32 conversion. Just like in the legacy array methods. In the ES2015 spec. that is indeed the case for the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. However, the other ElementList : Elision_opt AssignmentExpression and ElementList : ElementList , Elision_opt AssignmentExpression ArrayAccumulation algorithms both did an explicit ToUint32 conversion on the array index before calling CreateDataProperty. That's original ES2015 bug.

Apparently at some point subsequent to ES2015, somebody notices this inconsistency and fixed it by adding a ToUint32 to the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. That was the wrong fix. The correct fix would have been to remove the ToUnit32 conversions there were the original bug.

[GeorgNeis]

That makes sense. I think there's still an issue with how the "length" property is set, though, because the new length is also calculated using ToUint32. See https://tc39.github.io/ecma262/#sec-array-initializer-runtime-semantics-evaluation. Perhaps these Set operations should be skipped if the raw value is greater than 2^32-1?

[GeorgNeis]

That makes sense. I think there's still an issue with how the "length" property is set, though, because the new length is also calculated using ToUint32. See https://tc39.github.io/ecma262/#sec-array-initializer-runtime-semantics-evaluation. Perhaps these Set operations should be skipped if the raw value is greater than 2^32-1?

[littledan]

It sounds like the suggested fix is to remove all the ToUint32s in the evaluation of Array literals, and change the length calculation to simply saturate out at 2**32-1. Is that right? What do others on this thread think of that change?

[littledan]

It sounds like the suggested fix is to remove all the ToUint32s in the evaluation of Array literals, and change the length calculation to simply saturate out at 2**32-1. Is that right? What do others on this thread think of that change?

[anba]

Apparently at some point subsequent to ES2015, somebody notices this inconsistency and fixed it by adding a ToUint32 to the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. That was the wrong fix. The correct fix would have been to remove the ToUnit32 conversions there were the original bug.

See #153 for background why additional ToUint32 calls were added to ArrayAccumulation and Array Evaluation.

It sounds like the suggested fix is to remove all the ToUint32s in the evaluation of Array literals, and change the length calculation to simply saturate out at 2**32-1.

Replacing all ToUint32 calls with max(<value>, 2**32-1) should work without regressing #153.

[anba]

Apparently at some point subsequent to ES2015, somebody notices this inconsistency and fixed it by adding a ToUint32 to the SpreadElement : ... AssignmentExpression ArrayAccumulation algorithm. That was the wrong fix. The correct fix would have been to remove the ToUnit32 conversions there were the original bug.

See #153 for background why additional ToUint32 calls were added to ArrayAccumulation and Array Evaluation.

It sounds like the suggested fix is to remove all the ToUint32s in the evaluation of Array literals, and change the length calculation to simply saturate out at 2**32-1.

Replacing all ToUint32 calls with max(<value>, 2**32-1) should work without regressing #153.

[GeorgNeis]

The link in #153 (https://bugs.ecmascript.org/show_bug.cgi?id=4474) isn't working. Do you remember what the problem there was?

[GeorgNeis]

The link in #153 (https://bugs.ecmascript.org/show_bug.cgi?id=4474) isn't working. Do you remember what the problem there was?

[anba]

Oh, have they finally decommissioned bugs.ecmascript.org? From the PR tc39/archives#2 -> https://github.com/IgnoredAmbience/archives/blob/d13266f6be27daa61605bdcd9fe1e6b7ae3ce460/bugzilla/4474.xml, but I'm afraid it doesn't give too much info.

There are two issues:

1. In 12.2.5.2 Runtime Semantics: ArrayAccumulation for SpreadElement : ... AssignmentExpression:

• Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

2. In 12.2.5.3 Runtime Semantics: Evaluation for ArrayLiteral : [ Elision ] and ArrayLiteral : [ ElementList ].

• The note about Set(array, "length", ...). not throwing is incorrect if ElisionWidth resp. the return value of ArrayAccumulation is larger than 4294967295.

[anba]

Oh, have they finally decommissioned bugs.ecmascript.org? From the PR tc39/archives#2 -> https://github.com/IgnoredAmbience/archives/blob/d13266f6be27daa61605bdcd9fe1e6b7ae3ce460/bugzilla/4474.xml, but I'm afraid it doesn't give too much info.

There are two issues:

1. In 12.2.5.2 Runtime Semantics: ArrayAccumulation for SpreadElement : ... AssignmentExpression:

• Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

2. In 12.2.5.3 Runtime Semantics: Evaluation for ArrayLiteral : [ Elision ] and ArrayLiteral : [ ElementList ].

• The note about Set(array, "length", ...). not throwing is incorrect if ElisionWidth resp. the return value of ArrayAccumulation is larger than 4294967295.

[littledan]

Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

This case seems a bit theoretical to me; I think most implementations will have run out of memory at this point. I'd be fine with saying we throw here, as some spec fiction if it makes people feel better about the consistency. In real life, we will either throw or crash earlier than that.

The note about Set(array, "length", ...). not throwing is incorrect if ElisionWidth resp. the return value of ArrayAccumulation is larger than 4294967295.

For setting the length, I agree that taking 2**32-1 as a maximum value to set makes sense.

However, I don't see why, for the index, we should repeatedly set to the last Array-indexed element rather than continuing to increment numbered indexes.

[littledan]

Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

This case seems a bit theoretical to me; I think most implementations will have run out of memory at this point. I'd be fine with saying we throw here, as some spec fiction if it makes people feel better about the consistency. In real life, we will either throw or crash earlier than that.

The note about Set(array, "length", ...). not throwing is incorrect if ElisionWidth resp. the return value of ArrayAccumulation is larger than 4294967295.

For setting the length, I agree that taking 2**32-1 as a maximum value to set makes sense.

However, I don't see why, for the index, we should repeatedly set to the last Array-indexed element rather than continuing to increment numbered indexes.

[allenwb]

Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

As Dan says, it will never happen because, for any imaginable implementation in the foreseeable future, resource exhaustion will occur before hitting that limit. If you could reach it and the bogus ToUint32 that was inserted as a "fix" is removed then the property key that is set is currently unspecified because nextIndex + 1 will compute a mathematical value that is not a Number value and ToString doesn't specify how to convert such a value to a string value.

Regardless of past, and possibly misguided, decisions within TC39 I think any array literal that tries to create Array objects whose length should be ≥ 2³²-1 should throw. It's fine with me that in most cases it would be a resource exhaustion throw, but as the spec. is currently written it's conceivable that some resource rich implementations might let some such arrays slip through because of the Uint32 clamping of the length value performed in the ArrayLiteral evaluation algorithms. If that clamping is removed than a range error will be thrown when the Array length is set of any value ≥ 2³²-1

So, simplest fix, remove all the ToUint32 conversions in both ArrayLiteral evaluation and ArrayAccumulation.

[allenwb]

Unclear semantics when nextIndex reaches 9007199254740993? Does it create the property "9007199254740993" or the property "9007199254740992"? Or should it even throw?

As Dan says, it will never happen because, for any imaginable implementation in the foreseeable future, resource exhaustion will occur before hitting that limit. If you could reach it and the bogus ToUint32 that was inserted as a "fix" is removed then the property key that is set is currently unspecified because nextIndex + 1 will compute a mathematical value that is not a Number value and ToString doesn't specify how to convert such a value to a string value.

Regardless of past, and possibly misguided, decisions within TC39 I think any array literal that tries to create Array objects whose length should be ≥ 2³²-1 should throw. It's fine with me that in most cases it would be a resource exhaustion throw, but as the spec. is currently written it's conceivable that some resource rich implementations might let some such arrays slip through because of the Uint32 clamping of the length value performed in the ArrayLiteral evaluation algorithms. If that clamping is removed than a range error will be thrown when the Array length is set of any value ≥ 2³²-1

So, simplest fix, remove all the ToUint32 conversions in both ArrayLiteral evaluation and ArrayAccumulation.

[littledan]

@allenwb It sounds like you're proposing that the semantics be to exhaust all iterators before throwing the RangeError, as well as to never have an early error and always a runtime error. Am I understanding correctly?

A couple possible tweaks to this:

• When the RangeError is visible at parse-time (through a really long Array literal, not counting spreads), throw an early error. Is the reason against this that it's a pretty obscure case and not likely to come up?
• Throw the RangeError as soon as it's apparent that that we've exceeded 2**32-1, closing the current iterator and not even starting any spreads which follow it. Is the reason here that these semantics would be somehow more complex?

@GeorgNeis Do you have an intuition for whether any of these alternatives would be more or less burdensome to implement?

[littledan]

@allenwb It sounds like you're proposing that the semantics be to exhaust all iterators before throwing the RangeError, as well as to never have an early error and always a runtime error. Am I understanding correctly?

A couple possible tweaks to this:

• When the RangeError is visible at parse-time (through a really long Array literal, not counting spreads), throw an early error. Is the reason against this that it's a pretty obscure case and not likely to come up?
• Throw the RangeError as soon as it's apparent that that we've exceeded 2**32-1, closing the current iterator and not even starting any spreads which follow it. Is the reason here that these semantics would be somehow more complex?

@GeorgNeis Do you have an intuition for whether any of these alternatives would be more or less burdensome to implement?

[allenwb]

@littledan
your case 1: The only way I can imagine this occurring is an intentional test or a resource exhaustion DoS attach on an engine. Either case is unlikely and not unique to this situation (imagine a statement list of gigabytes of semi-colons). The handling of these sorts of situations don't need to be standardize. They are best left to implementations. Explicitly doing something would just add clutter and complexity to the standard.

you case 2: Again, this is likely to produce a resource exhaustion error (just like any infinite loop that build structure) and it isn't clear there is any benefit to standardizing its handling beyond what is already explicit in the spec. But there is a down-side. You would be adding extra logic (essentially a specialized version of exotic array [[DefineOwnProperty]] to detect the cross-over to 2³²-1. What is the benefit of that added complexity as the behavior for this improbable case is already well defined. If it requires actual additional checks to be performed in all cases, it could even have a negative performance impact on normal usage.

There is an important dynamic language high perf runtime design heuristic at play here. It is: try to avoid runtime checks that in the normal case don't require taking any action. A dynamic runtime has to perform checks that ensure memory safety and other essential internal invariants. Any other non-essential runtime checks are just a performance tax on correct code (even the work to eliminate them in a jit is a tax). It's better from a app perf perspective to let these rare cases manifest as application level errors (which they are) and be found through normal app level testing/'debugging.

[allenwb]

@littledan
your case 1: The only way I can imagine this occurring is an intentional test or a resource exhaustion DoS attach on an engine. Either case is unlikely and not unique to this situation (imagine a statement list of gigabytes of semi-colons). The handling of these sorts of situations don't need to be standardize. They are best left to implementations. Explicitly doing something would just add clutter and complexity to the standard.

you case 2: Again, this is likely to produce a resource exhaustion error (just like any infinite loop that build structure) and it isn't clear there is any benefit to standardizing its handling beyond what is already explicit in the spec. But there is a down-side. You would be adding extra logic (essentially a specialized version of exotic array [[DefineOwnProperty]] to detect the cross-over to 2³²-1. What is the benefit of that added complexity as the behavior for this improbable case is already well defined. If it requires actual additional checks to be performed in all cases, it could even have a negative performance impact on normal usage.

There is an important dynamic language high perf runtime design heuristic at play here. It is: try to avoid runtime checks that in the normal case don't require taking any action. A dynamic runtime has to perform checks that ensure memory safety and other essential internal invariants. Any other non-essential runtime checks are just a performance tax on correct code (even the work to eliminate them in a jit is a tax). It's better from a app perf perspective to let these rare cases manifest as application level errors (which they are) and be found through normal app level testing/'debugging.

[GeorgNeis]

As Dan mentioned in his pull request, #1124 (comment), I would prefer not to throw but rather keep inserting regular data properties and leaving length at its maximal value. That would also make it behave analogous to array destructuring, such that the following produce the same value for x.
let x = [...a];
let [...x] = a;

[GeorgNeis]

As Dan mentioned in his pull request, #1124 (comment), I would prefer not to throw but rather keep inserting regular data properties and leaving length at its maximal value. That would also make it behave analogous to array destructuring, such that the following produce the same value for x.
let x = [...a];
let [...x] = a;