Problem pushing an item on an array with a big length
Joaquin Cuenca Abela
I think the following code:
var a = [];
a.length = 4294967295;
a.push("a");
should throw a RangeError exception.
Instead, the first time I tried, it crashed Firefox 1.5 beta 2. Next
runs, I got "out of memory" in the javascript console.
Unfortunately the IE behaviour seems to not be correct here, either, as
it acts as if length was stored on a 32 bit unsigned int, that just
happens to overflow. So it may be just me misunderstanding the
standard.
I'm basing my guess in point 10 of the algorithm 15.4.5.1 ([[Put]] for
arrays, page 105):
10. Change (or set) the value of the length property of A to
ToUint32(P)+1. (<-- here ToUint32(P)+1 is = 2^32)
If this means the same thing as "call the [[Put]] method of A, passing
"length" for the property name and ToUint32(P)+1 for the value" then
RangeError should be throw due to this point.
If it means "change the value of the length property using the general
[[Put]] algorithm", then anyway a RangeError should be throw a bit
later, due to the point 7 of algorithm 15.4.4.7 (Array.prototype.push,
pag. 100):
7. Call the [[Put]] method of this object with arguments "length" and
n. (<-- here n is = 2^32)
The ecmascript standard may be based on the implicid assumption of
"enough memory should be available", and SpiderMonkey may be
theoretically right (given enough memory, it may fire a RangeError).
But given than in practice the results are very different from what's
expected from reading the standard or from what IE does, I'm inclined
to signal it as a bug.
Cheers,
Joaquin Cuenca Abela
1, and thus algorithm 15.4.5.1 should not reach point 10 for this push.
But I think that it should throw a RangeError, due to the posterior
point 7 of algorithm 15.4.4.7.
Cheers,
Martin Honnen
Joaquin Cuenca Abela wrote:
> I think the following code:
>
> var a = [];
> a.length = 4294967295;
> a.push("a");
>
> should throw a RangeError exception.
Here is what should happen for the push call (ECMAScript edition 3
section 15.4.4.7 Array.prototype.push ( [ item1 [ , item2 [ , … ] ] ] )):
1. Call the [[Get]] method of this object with argument "length".
2. Let n be the result of calling ToUint32(Result(1)).
n should be 4294967295 after 1. and 2.
3. Get the next argument in the argument list; if there are no more
arguments, go to step 7.
4. Call the [[Put]] method of this object with arguments ToString(n) and
Result(3).
The [[Put]] method is called with '4294967295' and 'a'. That should
result in the following (ECMAScript edition 3 section 15.4.5.1 [[Put]]
(P, V)):
1. Call the [[CanPut]] method of A with name P.
2. If Result(1) is false, return.
CanPut should return true, so no problem here.
3. If A doesn’t have a property with name P, go to step 7.
No property of that name exists so going on to step 7:
7. Create a property with name P, set its value to V and give it empty
attributes.
a['4294967295'] is set to 'a'.
8. If P is not an array index, return.
That check is defined as (ECMAScript edition 3 section 15.4):
A property name P (in the form of a string
value) is an array index if and only if ToString(ToUint32(P)) is equal
to P and ToUint32(P) is not equal to 2^32−1.
That means '4294967295' is not an array index and the [[Put]] returns
with step 8 and we have to continue with the push method and step 5:
5. Increase n by 1.
Now the question is what kind of arithmetic has to be done here, whether
step 5 sets
n to 4294967296
or sets
n to 0
(as 32 bit unsigned integer would do I think)
As there is only one argument to push and that has been processed the
next steps are:
7. Call the [[Put]] method of this object with arguments "length" and n.
8. Return n.
JScript and Opera's implementation seems to set n to 0 in step 5 as the
following test
var a = new Array(4294967295);
'push yields: ' + a.push('Kibo') + '\r\nlength: ' + a.length +
'\r\na[\'4294967295\']: ' + a['4294967295']
yields
push yields: 0
length: 0
a['4294967295']: Kibo
with both implementations.
Rhino (1.6 release 2) seems to set n to 4294967296 as it yields an error
"Inappropriate array length" for the push call. If you check
a['4294967295'] after it reports the error it has set that value the
same as JScript and Opera do.
Spidermonkey (in its shell built from CVS yesterday) takes a long time
and then indeed reports "out of memory". The shell prompt comes back but
any further attempts there to evaluate expressions again give "out of
memory" so I can't check whether a['4294967295'] has been set.
--
Martin Honnen
http://JavaScript.FAQTs.com/
Martin Honnen
Martin Honnen wrote:
> Spidermonkey (in its shell built from CVS yesterday) takes a long time
> and then indeed reports "out of memory".
I have filed that as
<https://bugzilla.mozilla.org/show_bug.cgi?id=322135>
as I could not find any open bugs on array/push.
Joaquin Cuenca Abela
>
> Now the question is what kind of arithmetic has to be done here, whether
> step 5 sets
> n to 4294967296
> or sets
> n to 0
> (as 32 bit unsigned integer would do I think)
The only reference to a numeric type in all the ecmascript standard is
the double precision 64-bit format as defined by IEEE 754.
As this is the only standard referenced for all the arithmetic
operations, I thus thought n + 1 should give 4294967296.
ToUInt32 as defined in the standard seems to me to be strictly an
operation that takes a double and returns a different double (that
happens to be between +0 and 2^32 - 1, and with a decimal fractional
part of exactly 0). For instance, it uses only functions defined
elsewhere in the standard, as floor, that take and return a double.
However, I now think that I was maybe wrong, because if To[U]Int32
returns a double, some operations in the standard are badly defined.
For instance, the productions of the familly of bitwise expressions are
defined as:
...
5. Call ToInt32(Result(2)).
6. Call ToInt32(Result(4)).
7. Apply the bitwise operator @ to Result(5) and Result(6). The result
is a signed 32 bit integer.
The bitwise operator @ in double precision numbers is not equivalent to
the bitwise operator of [unsigned] integers.
This is very confusing to me. I think that if the arithmetic on the
values returned from the To[U]Int{16,32} family of functions is the C
arithmetic on [short] [unsigned] int, then it should be explicitely
stated in the standard.
Cheers,
Brendan Eich
> This is very confusing to me. I think that if the arithmetic on the
> values returned from the To[U]Int{16,32} family of functions is the C
> arithmetic on [short] [unsigned] int, then it should be explicitely
> stated in the standard.
Yes, the standard is ambiguous here. The Array length property was
meant to be realizable in implementations using a uint32 type, but that
does not dictate the outcome of new Array(0xffffffff).push('a') -- the
spec still might require an intermediate result type of double.
The spec is poor also in the lack of transactionality. It would be
trivial to catch the overflow and throw RangeError before committing any
effects. Another bug to fix in ECMA-262 Edition 4.
Note that unshift, splice, and concat in SpiderMonkey suffer what is
essentially the same bug as push.
/be
Joaquin Cuenca Abela
I intuitively expected others array operations to misbehave like push,
but I wanted to nail down first the expected behaviour for a simple
example.
Thank you very much for your clarification of the standard's intent.
Cheers,