Array.splice implementation in 'JS: The Good Parts'

[Jun Woong]

Is an implementation of Array.splice by Douglas Crockford correct?

When the implementation composes a resulting array (that is made up
of elements deleted from the original array), it checks if each
element exists:

element = this[start + k];
if (element !== undefined)
result[k] = element;

This gives an empty array (that is, []) for

a = []; a[2] = 0;
b = a.splice(0, 2); // b.length === 0

while the v8 implementation gives [undefined, undefined] (thus, the
length of the result is 2).

What does the ECMA standard says about this? Which one is the correct
implementation?


Thanks in advance.

[Thomas 'PointedEars' Lahn]

Jun Woong wrote:

> Is an implementation of Array.splice by Douglas Crockford correct?

You mean Array.*prototype*.splice. The difference is important; the
prototype property is *implicitly* inherited, the other property is not.

> When the implementation composes a resulting array (that is made up
> of elements deleted from the original array), it checks if each
> element exists:
>
> element = this[start + k];
> if (element !== undefined)

This error-prone, incompatible approach [1] is unsuited to determine if an
element with a certain index exists in an array (generally: if an object has
or inherits a property with a certain name), because an array element (a
property) may be (may have) the `undefined' value. The less error-prone,
but equally compatible/incompatible approach [1] is

if ((start + k) in this)
{
// …
}

or, where inheritance should *not* be considered,

if (this.hasOwnProperty(start + k))
{
// …

}

> result[k] = element;
>
>
> This gives an empty array (that is, []) for
>
> a = []; a[2] = 0;
> b = a.splice(0, 2); // b.length === 0

The method call means: "At index 0 of the array, remove 2 elements from the
array and return a reference to an Array instance having only the *removed*
elements as its elements."

Therefore, `b.length' should be 0.

> while the v8 implementation gives [undefined, undefined] (thus, the
> length of the result is 2).
>
> What does the ECMA standard says about this?

<http://ecma-international.org/ecma-262/5.1/#sec-15.4.4>:

| 15.4.4.12 Array.prototype.splice (start, deleteCount [ , item1 [ , item2 [
| , … ] ] ] )
|
| When the splice method is called with two or more arguments start,
| deleteCount and (optionally) item1, item2, etc., the deleteCount elements
| of the array starting at array index start are replaced by the arguments
| item1, item2, etc. An Array object containing the deleted elements (if
| any) is returned. The following steps are taken:

IOW:

var start = 0;
var deleteCount = 2;
var item1 = undefined;
// …

| 1. Let O be the result of calling ToObject passing the this value as the
| argument.

var O = [,, 0];

| 2. Let A be a new array created as if by the expression new Array() where
| Array is the standard built-in constructor with that name.

var A = [];

| 3. Let lenVal be the result of calling the [[Get]] internal method of O
| with argument "length".

var lenVal = O.length;

(lenVal === 3)

| 4. Let len be ToUint32(lenVal).

var len = 3 >>> 0;

(len === 3)

| 5. Let relativeStart be ToInteger(start).

function sign (x)
{
return (x < 0) ? -1 : 1;
}

function ToInteger (x)
{
return sign(x) * Math.floor(Math.abs(x));
}

var relativeStart = ToInteger(start);

(relativeStart === 0)

| 6. If relativeStart is negative, let actualStart be max((len +
| relativeStart),0); else let actualStart be min(relativeStart, len).

var actualStart = (relativeStart < 0)
? Math.max((len + relativeStart), 0);
: Math.min(relativeStart, len);

(actualStart === 0)

| 7. Let actualDeleteCount be min(max(ToInteger(deleteCount),0),
| len – actualStart).

var actualDeleteCount = Math.min(
Math.max(ToInteger(deleteCount), 0)),
len - actualStart);

(actualDeleteCount === 2)

| 8. Let k be 0.

var k = 0;

| 9. Repeat, while k < actualDeleteCount

while (k < actualDeleteCount)
{
| a. Let from be ToString(actualStart+k).

var from = String(actualStart + k);

| b. Let fromPresent be the result of calling the [[HasProperty]]
| internal method of O with argument from.

var fromPresent = from in O;

This is the step in the algorithm where apparently both Crockford and V8 are
wrong, according to the 5.1 Edition and earlier Editions. Crockford does
not consider `undefined' values for elements, and V8 does not consider
uninitialized elements (here: those with indexes 0 and 1).

| c. If fromPresent is true, then

if (fromPresent)
{

| i. Let fromValue be the result of calling the [[Get]] internal
| method of O with argument from.

var fromValue = O[from];

| ii. Call the [[DefineOwnProperty]] internal method of A with
| arguments ToString(k), Property Descriptor {[[Value]]:
| fromValue, [[Writable]]: true, [[Enumerable]]: true,
| [[Configurable]]: true}, and false.

A[String(k)] = fromValue;
}

| d. Increment k by 1.

++k;
}

| …
| 17. Return A.

return A;

| […]

> Which one is the correct implementation?

Neither one, according to the 5.1 Edition and earlier Editions that
specified this method.

___
[1] <http://PointedEars.de/es-matrix>

--
PointedEars

[Jun Woong]

Thomas 'PointedEars' Lahn <PointedE...@web.de> wrote:
> Jun Woong wrote:
> > Is an implementation of Array.splice by Douglas Crockford correct?
>
> You mean Array.*prototype*.splice.  The difference is important; the
> prototype property is *implicitly* inherited, the other property is not.

Oh, I forgot putting "prototype." Thanks.

[...]

> > What does the ECMA standard says about this?
>
> <http://ecma-international.org/ecma-262/5.1/#sec-15.4.4>:
>

[...]

> |      b. Let fromPresent be the result of calling the [[HasProperty]]
> |         internal method of O with argument from.
>
>     var fromPresent = from in O;
>
> This is the step in the algorithm where apparently both Crockford and V8 are
> wrong, according to the 5.1 Edition and earlier Editions.  Crockford does
> not consider `undefined' values for elements, and V8 does not consider
> uninitialized elements (here: those with indexes 0 and 1).

Thus, if `a' is intialized as [undefined, undefined, 0] (having all
elements initialized), the length of the result should be 2, while it
should be 0 when initialized as [,, 0] (having uninitialized
elements).


Thank you very much for the kind explanation and the nice work that
the link below leads to.

> ___
> [1] <http://PointedEars.de/es-matrix>

[Thomas 'PointedEars' Lahn]

Jun Woong wrote:

> Thomas 'PointedEars' Lahn <PointedE...@web.de> wrote:
>> Jun Woong wrote:
>> > What does the ECMA standard says about this?
>>
>> <http://ecma-international.org/ecma-262/5.1/#sec-15.4.4>:
>>
>> [...]
>> | b. Let fromPresent be the result of calling the [[HasProperty]]
>> | internal method of O with argument from.
>>
>> var fromPresent = from in O;
>>
>> This is the step in the algorithm where apparently both Crockford and V8
>> are wrong, according to the 5.1 Edition and earlier Editions. Crockford
>> does not consider `undefined' values for elements, and V8 does not
>> consider uninitialized elements (here: those with indexes 0 and 1).
>
> Thus, if `a' is intialized as [undefined, undefined, 0] (having all
> elements initialized), the length of the result should be 2, while it
> should be 0 when initialized as [,, 0] (having uninitialized
> elements).

Yes, exactly. (That

var a = [,, 0];

is equivalent to

var a = [];
a[2] = 0;

follows from section "11.1.4 Array Initialiser".)

> Thank you very much for the kind explanation and the nice work that
> the link below leads to.
>
>> ___
>> [1] <http://PointedEars.de/es-matrix>

You are welcome. (Stay tuned.)


Regards,

PointedEars
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm> (404-comp.)