Ecma262: SortCompare (Array#sort)

[Yaffle]

http://tc39.github.io/ecma262/#sec-sortcompare

According to spec comparefn will be never called for undefined values, but v8 and WebKit implementations do not implement this behavior:

var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      array[i] = undefined;
    }
  }
  if (counter === 1) {
    if (a == undefined || b == undefined) {
      console.log("comparator was called for an undefined value");
    }
  }
  counter += 1;
  return a - b;
});

var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      delete array[i];
    }
  }
  if (counter === 1) {
    if (a == undefined || b == undefined) {
      console.log("comparator was called for a hole");
    }
  }
  counter += 1;
  return a - b;
});

var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      delete array[i];
      Object.prototype[i.toString()] = 42;
    }
  }
  if (counter === 1) {
    if (a === 42 || b === 42) {
      console.log("comparator was called for a value from prototype");
    }
  }
  counter += 1;
  return a - b;
});

The spec only tells that the sort order is implementation defined...
v8 and WebKit do this for performance reasons, probably, because they can move undefined values and holes to the end of an array before the sorting and call comparefn directly:
https://github.com/v8/v8/blob/master/src/js/array.js#L1194
https://github.com/WebKit/webkit/blob/cc80ecf5f0902e724a6e398d152323120e4e3b82/Source/JavaScriptCore/builtins/ArrayPrototype.js#L473

[bterlson]

Not trying to be obtuse: what's the ECMA262 bug here?

[ljharb]

If SpiderMonkey and Chakra follow the spec, but v8 and JSC don't, then this is a v8 and a JSC bug. @Yaffle can you confirm that SpiderMonkey and Chakra follow the spec here?

[bterlson]

Also how does the first and second case differ? Maybe the first means to assign undefined rather than delete the property?

[bterlson]

Here's the results I get, with the update I suggest above:

spidermonkey

Undefined elements

Holes

Holes with prototype property

chakra

Undefined elements

Holes

Holes with prototype property

d8

Undefined elements

comparator was called for an undefined value

Holes

comparator was called for a hole

Holes with prototype property

comparator was called for a value from prototype

Anyone using eshost can use the following script:

print('##### Undefined elements');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      array[i] = undefined;
    }
  }
  if (counter === 1) {
    if (a == undefined || b == undefined) {
      print("comparator was called for an undefined value");
    }
  }
  counter += 1;
  return a - b;
});

print('##### Holes');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      delete array[i];
    }
  }
  if (counter === 1) {
    if (a == undefined || b == undefined) {
      print("comparator was called for a hole");
    }
  }
  counter += 1;
  return a - b;
});

print('##### Holes with prototype property');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var counter = 0;
array.sort(function (a, b) {
  if (counter === 0) {
    for (var i = 0; i < array.length; i += 1) {
      delete array[i];
      Object.prototype[i.toString()] = 42;
    }
  }
  if (counter === 1) {
    if (a === 42 || b === 42) {
      print("comparator was called for a value from prototype");
    }
  }
  counter += 1;
  return a - b;
});

[Yaffle]

@bterlson , the spec tells when and how to call comparefn:

The arguments for calls to SortCompare are values returned by a previous call to the [[Get]] internal method, unless the properties accessed by those previous calls did not exist according to HasOwnProperty. If both perspective arguments to SortCompare correspond to non-existent properties, use +0 instead of calling SortCompare. If only the first perspective argument is non-existent use +1. If only the second perspective argument is non-existent use -1.
and steps for SortCompare has checks for undefined values.

Well... not a big bug...

[Yaffle]

@ljharb , SpiderMonkey may switch to "self-hosted" Array#sort ( https://bugzilla.mozilla.org/show_bug.cgi?id=715181 ) and there is a suggestion to use same behaviour for undefined values and holes as in V8 and JSC

[bterlson]

@Yaffle in other words, you are requesting a spec change to the v8/jsc approach? If so, can you expand on why it is necessary and/or desirable behavior? Otherwise this seems like a bug in V8 and JSC that SM should not copy...

[allenwb]

The special treatment of non-existent properties dates back to the ES3 spec. ES5 changes the language used to describe it from prose to the use of [[HasProperty]]. ES6 moved the test from inside of SortCompare into a guard on calling SortCompare. None of them call a user provided _comparefn_ for non-existent properties.

I don't recall the exact motivation for the ES6 refactoring but I'm pretty use that there are either es-discuss or bugs.ecmascript.org discussions that relate it it.

Note that ES3 spec. has an explicit change from ES1&2 which did not explicitly check for non-existent properties and which explicitly stated that the handling of non-existent properties was implementation-dependent.

Clearly, when ES3 was being developed a decision was made that undefined values and holes should not have the same treatment. In particular, that holes sort after undefined at the end of the array. I don't see why we would want to change that long standing design design.

[rossberg]

@allenwb, motivation might be that this semantics induces a non-zero runtime cost while having a zero real-world benefit.

[anba]

I don't recall the exact motivation for the ES6 refactoring but I'm pretty use that there are either es-discuss or bugs.ecmascript.org discussions that relate it it.

https://bugs.ecmascript.org/show_bug.cgi?id=3089

[Yaffle]

https://hg.mozilla.org/mozilla-central/rev/1c4b0a89fd5b - Firefox 47 does not use HasOwnProperty check and patches holes (note: the body of comparefn should not be equal to return a-b):

var array = [1, 2, 3, 4, 5, 6, 7, 8, , 10];
array.sort(function (a, b) {
  return a < b ? -1 : +1;
});
console.log(array, "9" in array);

[ljharb]

@Yaffle that doesn't patch holes - I get Array [ 1, 2, 3, 4, 5, 6, 7, 8, 10, <1 empty slot> ] in the FF 46 console. It just seems to sort holes at the end (which is what https://github.com/tc39/ecma262/issues/302#issuecomment-173379654 says)

[Yaffle]

@ljharb , the change was applied recently, do you use the latest nightly build?

[ljharb]

I used v46. On the latest, v47, I see the same behavior.

[Yaffle]

somehow I see Array [ 1, 2, 3, 4, 5, 6, 7, 8, 10, undefined ] true

[ljharb]

Ah, oops, yes I see the change you mean. 46 said "empty slot" but 47 says "undefined". Thanks.

[ljharb]

Using https://github.com/tc39/ecma262/issues/302#issuecomment-173351714 and eshost, this is what I now get locally:

results

#### Chakra
##### Undefined elements
##### Holes
##### Holes with prototype property

#### JavaScriptCore
##### Undefined elements
comparator was called for an undefined value
##### Holes
comparator was called for a hole
##### Holes with prototype property
comparator was called for a value from prototype

#### SpiderMonkey
##### Undefined elements
##### Holes
##### Holes with prototype property

#### V8
##### Undefined elements
comparator was called for an undefined value
##### Holes
comparator was called for a hole
##### Holes with prototype property
comparator was called for a value from prototype

So it seems we're still at 50/50 - jsc and v8 do one thing, and chakra/spidermonkey do another.

What do we want to do at this point? It seems like the options are:
1) make a change so that edge and firefox are "incorrect", and need to make a change
2) close this issue, so that safari and chrome are "incorrect", and need to make a change.

It would be really helpful if implementors of any of the 4 browsers could weigh in on either their preference for one outcome, or their objection to one outcome.
(cc @jswalden @evilpie @ajklein @mathiasbynens @bterlson @msaboff @kmiller68, just to name a few)

[devsnek]

From reading the source code, XS appears to ignore the HasOwnProperty check, but because of https://github.com/Moddable-OpenSource/moddable/issues/113 I can't really test this.

_{As a fun sidenote, engine262 sides with SpiderMonkey and ChakraCore}

[Yaffle]

@ljharb,
option 3: the spec should allow to handle holes and undefined values before the actual sort and SortCompare calls with undefined values. (Well.... may be the spec change is not needed at all). So all engines are correct.

[mathiasbynens]

FWIW, some more background on V8's behavior w.r.t. holes during Array#sort: https://v8.dev/blog/array-sort#before-sort

cc @schuay @Imasius

[schuay]

Thanks @mathiasbynens , extracted a V8 bug for further investigation here: https://crbug.com/v8/8666

[mathiasbynens]

Looking into this with @schuay, we found that one of the requirements for consistent comparison functions is:

Calling comparefn(a, b) does not modify obj or any object on obj's prototype chain.

And inconsistent comparison functions are implementation-defined:

If comparefn is not undefined and is not a consistent comparison function for the elements of this array [...], the sort order is implementation-defined.

The test case in https://github.com/tc39/ecma262/issues/302#issuecomment-452912471 exclusively uses inconsistent comparison functions, since it modifies the array during the first call.

Can anyone think of a valid test case that shows a difference in implementations?

[mathiasbynens]

Oh, I see. The subtlety here is in the part I quoted earlier:

If comparefn is not undefined and is not a consistent comparison function for the elements of this array [...], the sort order is implementation-defined.

It says the sort order is implementation-defined, but it doesn't explicitly say that anything else is implementation-defined too (such as whether or not SortCompare gets called).

---

Modified test case using consistent comparison functions:

print('##### Undefined elements');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
array.fill(undefined);
array.sort(function (a, b) {
  if (a === undefined || b === undefined) {
    print("comparator was called for an undefined value");
  }
  return a - b;
});

print('##### Holes');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (var i = 0; i < array.length; i += 1) {
  delete array[i];
}
array.sort(function (a, b) {
  if (a === undefined || b === undefined) {
    print("comparator was called for a hole");
  }
  return a - b;
});

print('##### Holes with prototype property');
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (var i = 0; i < array.length; i += 1) {
  delete array[i];
  Object.prototype[i] = 42;
}
array.sort(function (a, b) {
  if (a === 42 || b === 42) {
    print("comparator was called for a value from prototype");
  }
  return a - b;
});

Results:

$ eshost sort-normal.js 
#### Chakra
##### Undefined elements
##### Holes
##### Holes with prototype property
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype

#### JavaScriptCore
##### Undefined elements
##### Holes
##### Holes with prototype property
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype

#### SpiderMonkey
##### Undefined elements
##### Holes
##### Holes with prototype property
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype

#### V8
##### Undefined elements
##### Holes
##### Holes with prototype property

#### XS
##### Undefined elements
##### Holes
##### Holes with prototype property
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype
comparator was called for a value from prototype

V8 has the correct behavior for consistent comparison functions.

[mathiasbynens]

What does this part of the spec mean?

The arguments for calls to SortCompare are values returned by a previous call to the [[Get]] internal method, unless the properties accessed by those previous calls did not exist according to HasOwnProperty. If both perspective arguments to SortCompare correspond to non-existent properties, use +0 instead of calling SortCompare. If only the first perspective argument is non-existent use +1. If only the second perspective argument is non-existent use -1.

The use of "previous call" and the past tense is confusing. Should that just be "call"?

Is the intention to perform prototype chain lookups in these cases (i.e. to print "comparator was called for a value from prototype" once per array element in the test case), or is it to avoid those lookups altogether?

In case of the latter, I'd suggest the following change:

The arguments for calls to SortCompare are values returned by a call to the [[Get]] internal method, unless the properties accessed by those calls do not exist according to HasOwnProperty. If both prospective arguments to SortCompare correspond to non-existent properties, use +0 instead of calling SortCompare. If only the first perspective argument is non-existent use +1. If only the second perspective argument is non-existent use -1.

[ljharb]

My reading of the current paragraph seems to say that once it's been observed that a property exists or doesn't, or is own or isn't, that it can't change? By removing "previous" the timeline of "when a change matters" seems to become unspecified.

[schuay]

From an implementer POV, being able to avoid prototype lookups would be so great. But why not just spec it with [[GetOwnProperty]] in that case?

[szuend]

I think a clarification of the exact time when this HasOwnProperty call happens, would be rather helpfull.
My first intuition is, that the change Mathias suggested would change the way prototype chain lookups happen. I will probably look into this more starting next week.

[ljharb]

@szuend have you been able to look into this more?

[szuend]

Somewhat. For V8 we decided to change the sort pre-processing. V8 walks all indices from [0, [[length]]) and if HasProperty returns true, call [[Get]] and add the element to a temporary list. Sorting is then done on this temporary list. After sorting elements are written back using [[Set]] (and calling DeleteProperty in case there were holes).

This approach has the advantage that the interaction with the prototype chain and potential accessors is well-defined and no longer depends on the sorting algorithm used.

[mathiasbynens]

@szuend prepared a PR here: #1585. I'll present this at the next TC39 meeting.