Very large array indices and unshift/splice
From: es-discuss [mailto:es-discuss-bounces at mozilla.org] On Behalf Of Adam Klein
Is there any reason not to specify some precondition checking in these algorithms and spec them to throw the RangeError without interacting with the elements of the array if it's known a priori that the resulting length will be > 2^32-1?
ES6 adjusted the length limit upward to 2^53 - 1, IIRC...
Domenic Denicola wrote:
ES6 adjusted the length limit upward to 2^53 - 1, IIRC...
And yet Adam cited the draft ES6 HTML-formatted spec.
Seems like two problems:
-
Error-checking after mutating -- in this case in ArraySetLength from Array [[DefineOwnProperty]] from Put 7(b)(v)(3) in 22.1.3.28 -- buried!
-
The lack of 53-bit indexes, but isn't this waiting for a VM to try and see what breaks? Cc'ing Allen.
Buggy engines too, but perhaps their maintainers will want to wait a bit before fixing ;-).
From: Brendan Eich [mailto:brendan at mozilla.org]
And yet Adam cited the draft ES6 HTML-formatted spec.
- The lack of 53-bit indexes, but isn't this waiting for a VM to try and see what breaks? Cc'ing Allen.
Interesting; there's an inconsistency between ToLength() which uses ToInteger() + min(x, 2^53 - 1) vs. ArraySetLength() which uses ToUint32(). Maybe it is intentional so that everywhere else that uses ToLength() gets to use large indices, but you can't actually put that many elements in a (non-typed) array?
In any case, I see the issue now... it does seem like a convoluted path to get to that error.
I can only answer briefly right now: This is intentional. Array instances are still limited to 2^32-2 elements. Compat issues to change. But, the generic array methods aren't restricted to Array instances and support larger lengths in those cases.
Hi Allen, appreciate brief reply.
Still leaves mutation before error problem -- want a spec bug?
Impl bugs to follow.
Ok, I've only had time to do a cursory check, but based upon quick inspection the ES6 spec. for unshift appears to to produce observably identical results when operating upon an an Array instance of max length. That's what supposed to happen, ES5 didn't specify any precondition checks, so to do so now is, in theory, a breaking change. In practice it might not matter, but nobody knows for sure.
if there are what appears to be unintentional differences between the behavior or the ES5 and ES6 spec, then bugs should be file.
It's also reasonable to file bugs suggesting that a change to the ES5 behavior should be make but the submitter should try to justify why it is ok to make such a breaking change.
Finally, at this stage of the release game, bugs that contain detailed "patches" to the currently specified algorithms are more likely to get attention then those that lack that level of detail.
Allen Wirfs-Brock wrote:
ES5 didn't specify any precondition checks, so to do so now is, in theory, a breaking change. In practice it might not matter, but nobody knows for sure.
Unlikely, given what Adam reported:
V8 properly throws a range error, but fails to move the element up one index. SpiderMonkey hangs (presumably because it has no special logic to deal with very large, sparse arrays). JSC throws an "Out of memory" Error and also fails to move the element up one index.
Anyone care to test IE?
In practice, near the 2^31 - 1 maximum value for an arraylike's length, there's no reliable interop today.
IE11 moves elements up one index, throws a RangeError and completes instantly (no hang or oom).
Per spec, huzzah -- but the spec needs fixing.
That conclusion isn't so obvious to me. The current algorithms for the generic array methods are generally written to operate without knowledge of target object size limits. In the most general casees there isn't a single common way to predetermine size limits of any object that the method might be applied to. That's why there usually isn't any pre-flight limit checking in most of the algorithms.
In some specific cases such as for exotic array instances there are available means to get the data that would be needed to fail fast. But to generalize that to any "array-like" object would probably require adding new public protocol that the algorithms could use to query objects about length limits.
These are most old algorithms that are believed to be correct. The fact that implementations haven't consistently and correctly implemented them isn't sufficient justification to risk tweak ing them this close to the completion of ES6.
Of course, I don't have any problem with somebody starting a project to review and further backwards-compatability refine these algorithms targeting future ES editions.
Allen Wirfs-Brock wrote:
That conclusion isn't so obvious to me.
The spec bugs is the buried throw after mutation. That's obvious in hindsight.
Arguably a design bug, rather than a spec. bug. But I'm assuming that who ever originally wrote up these algorithms were being intentional about such things.
There are a number of places int he ES6 spec. where throws occur after mutation (and Proxy introduces the possibility of a lot more). What we have been trying to do in both the ES5 and ES6 spec. is to improved expected interoperability by being more explicit about exception ordering regardless of whether pre or post mutation).
Allen Wirfs-Brock wrote:
Arguably a design bug, rather than a spec. bug. But I'm assuming that who ever originally wrote up these algorithms were being intentional about such things.
Design, vs. accidental. Spec, vs. implementation. Potato, Potahtoe :-P.
I think we should fix 'em as we find them, if implementations do not agree (and they don't usefully agree here).
For what it's worth, given that there exists one implementation (IE 11) that gets this right per spec, I'm more inclined as an implementor to match that than to try to get the spec changed here. I think Allen and Domenic answered my question about why this isn't a precondition when they pointed out that ToLength() is now greater than the max array length.
From: es-discuss [mailto:es-discuss-bounces at mozilla.org] On Behalf Of Adam Klein
For what it's worth, given that there exists one implementation (IE 11) that gets this right per spec, I'm more inclined as an implementor to match that than to try to get the spec changed here.
Eh, but then we have two implementations agreeing, which is the road toward locking in this behavior. Better to take advantage of the interoperability wasteland out at the 2^32 - 1 frontier, and seize the day by making even more daring changes like pushing the boundaries to 2^53 - 1!!
With a proper spec, of course. Happy to help with that if desired.
On Oct 26, 2014, at 8:58 PM, Brendan Eich wrote:
Design, vs. accidental. Spec, vs. implementation. Potato, Potahtoe :-P.
I think we should fix 'em as we find them, if implementations do not agree (and they don't usefully agree here).
I probably wasn't clear about the central issue:
unshift and other array methods are generic methods that work the same on any object that has a 'length' property and "array index" properties. When implemented as currently specified they produce consistent predictable results across for any such object, even if specified error conditions occur.
There are many ways that a particular kind of "array-like" object can constrain their 'length' property. There could be limits built into [[Get]]/[[Set]] (this is how exotic Arrays work), or the 'length' property might be readonly, or the 'length' property might be an accessor property that constrains the length value algorithmically, or the object might be a Proxy whose handler does whatever.
Given all of these alternatives, we currently don't have any single generic way to predetermine if 'length' extending operations such as unshift/splice will run into 'length' restrictions in the course of executing their generic algorithm. We might invent such a thing (perhaps a @@maxLength property). But that isn't a bug fix, that is a significant design change.
On Oct 27, 2014, at 8:35 AM, Domenic Denicola wrote:
Eh, but then we have two implementations agreeing, which is the road toward locking in this behavior. Better to take advantage of the interoperability wasteland out at the 2^32 - 1 frontier, and seize the day by making even more daring changes like pushing the boundaries to 2^53 - 1!!
The reason Array's max length wasn't increased to 2^53 - 1 relates to legacy array wrap-around behavior t the the 2^32 - 1 limit. Nobody wanted to risk changing that because of potential web compat. issues.
It seems to me that you can get the desired behavior even without exposing an internal "generic maximum length" method by simply arranging so that the mutations happen to the largest index first. This effectively ensures that the exception precedes mutation.
This spec trick should be applicable to any generic mutation method, using temporary helpers if needed if the maximum affected index is not immediately apparent from the parameters. Implementers can use in-place update and compensating mutations on exception, regardless of the spec mechanism used to ensure mutations are not visible upon exception.
The problem is that the "desired behavior" is an observable change from the currently observable behavior and there may be existing code that depends upon that behavior.
For example, how do we know whether or not somewhere on the web somebody is doing this:
var q = new Int32Array(10);
var n,f;
//populated buffer
//...
while (somePredicate(q)) {
f = q[q.length-1];
n = process(f);
try {q.unshift(0)} catch(e) {/* ignore exception from unshifting f off the end of q*/};
q[0] = n;
}
It's odd code, that should flunk any reasonable code review. But we see lots of odd code on the web and we generally try not to break it.
Is the benefit of respecify these algorithms worth risk of such breakages?
Somewhat related: Does it make sense to check if the length will exceed the 2^53-1 limit? And is ToString(9007199254740993) properly defined, where 9007199254740993 is a mathematical real number as defined in "5.2 Algorithm Conventions". As I understand it, ToString (7.1.12) is not defined for arbitrary numbers, but only for the Number type ("6.1.6 The Number Type").
A simple example where this issue arises:
var a = {length: Math.pow(2,53)-1};
Array.prototype.push.call(a, ..."abc");
print(a["9007199254740991"]); // ?
print(a["9007199254740992"]); // ?
print(a["9007199254740993"]); // ?
Consider the following snippet, along with the spec for Array.prototype.unshift:
var arr = []; arr[0xfffffffe] = 10; try { arr.unshift(1); } catch(e) { // e is a RangeError, since the unshift operation will try to set the length to 0xffffffff }what should the state of arr be after this botched operation? The way the spec is written, all the element manipulation happens before the RangeError occurs, so arr[0xffffffff] should be 10 and arr[0xfffffffe] should have been deleted.
But it's not clear this is worthwhile. I tested this in V8, SpiderMonkey, and JSC.
V8 properly throws a range error, but fails to move the element up one index. SpiderMonkey hangs (presumably because it has no special logic to deal with very large, sparse arrays). JSC throws an "Out of memory" Error and also fails to move the element up one index.
A similar thing happens if one attempts to splice items into the array.
Is there any reason not to specify some precondition checking in these algorithms and spec them to throw the RangeError without interacting with the elements of the array if it's known a priori that the resulting length will be > 2^32-1?
In V8 and JSC this nearly matches existing behavior. In Firefox it would cause a change in behavior, but any code depending on the existing behavior would be hanging for a long time already.
Consider the following snippet, along with the spec for Array.prototype.unshift ( https://people.mozilla.org/~jorendorff/es6-draft.html#sec-array.prototype.unshift ): var arr = []; arr[0xfffffffe] = 10; try { arr.unshift(1); } catch(e) { // e is a RangeError, since the unshift operation will try to set the length to 0xffffffff } what should the state of arr be after this botched operation? The way the spec is written, all the element manipulation happens before the RangeError occurs, so arr[0xffffffff] should be 10 and arr[0xfffffffe] should have been deleted. But it's not clear this is worthwhile. I tested this in V8, SpiderMonkey, and JSC. V8 properly throws a range error, but fails to move the element up one index. SpiderMonkey hangs (presumably because it has no special logic to deal with very large, sparse arrays). JSC throws an "Out of memory" Error and also fails to move the element up one index. A similar thing happens if one attempts to splice items into the array. Is there any reason not to specify some precondition checking in these algorithms and spec them to throw the RangeError without interacting with the elements of the array if it's known a priori that the resulting length will be > 2^32-1? In V8 and JSC this nearly matches existing behavior. In Firefox it would cause a change in behavior, but any code depending on the existing behavior would be hanging for a long time already. - Adam -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20141023/bee34694/attachment-0001.html>