Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #14380 > unrolled thread

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

Back to article view | Back to comp.lang.javascript

Contents

  Array.splice implementation in 'JS: The Good Parts' Jun Woong <woong@icu.ac.kr> - 2012-06-06 21:17 -0700
    Array.prototype.splice implementation in 'JS: The Good Parts' (was: Array.splice implementation in 'JS: The Good Parts') Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2012-06-07 20:17 +0200
      Re: Array.prototype.splice implementation in 'JS: The Good Parts' (was: Array.splice implementation in 'JS: The Good Parts') Jun Woong <woong@icu.ac.kr> - 2012-06-07 18:41 -0700
        Re: Array.prototype.splice implementation in 'JS: The Good Parts' Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2012-06-08 09:48 +0200

#14380 — Array.splice implementation in 'JS: The Good Parts'

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.

[toc] | [next] | [standalone]

#14384 — Array.prototype.splice implementation in 'JS: The Good Parts' (was: Array.splice implementation in 'JS: The Good Parts')

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

[toc] | [prev] | [next] | [standalone]

#14387 — Re: Array.prototype.splice implementation in 'JS: The Good Parts' (was: Array.splice implementation in 'JS: The Good Parts')

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>

[toc] | [prev] | [next] | [standalone]

#14388 — Re: Array.prototype.splice implementation in 'JS: The Good Parts'

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.)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web