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

Groups > comp.lang.javascript > #14384

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

Followups directed to: comp.lang.javascript

Show all headers | View raw

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

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web