SortCompare (Array#sort) #302

Yaffle · 2016-01-20T07:15:15Z

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

The text was updated successfully, but these errors were encountered:

bterlson · 2016-01-20T20:18:36Z

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

ljharb · 2016-01-20T20:21:37Z

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 · 2016-01-20T20:26:49Z

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

bterlson · 2016-01-20T20:35:57Z

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 · 2016-01-20T21:06:13Z

@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 · 2016-01-20T21:13:56Z

@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 · 2016-01-20T21:17:08Z

@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 · 2016-01-20T22:17:02Z

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 · 2016-01-21T11:54:57Z

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

anba · 2016-01-21T12:23:08Z

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 · 2016-01-26T07:21:16Z

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 · 2016-01-26T08:20:26Z

@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 #302 (comment) says)

Yaffle · 2016-01-26T08:48:12Z

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

ljharb · 2016-01-26T09:02:45Z

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

Yaffle · 2016-01-26T09:06:27Z

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

ljharb · 2016-01-26T09:07:12Z

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

ljharb · 2019-01-09T23:44:40Z

Using #302 (comment) 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:

make a change so that edge and firefox are "incorrect", and need to make a change
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 · 2019-01-10T00:42:23Z

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

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

Yaffle · 2019-01-10T07:52:10Z

@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 · 2019-01-10T08:04:43Z

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 · 2019-01-10T08:19:02Z

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

mathiasbynens · 2019-01-10T08:35:12Z

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 #302 (comment) 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 · 2019-01-10T08:50:43Z

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 · 2019-01-10T09:19:37Z

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 · 2019-01-10T09:29:03Z

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 · 2019-01-10T09:29:50Z

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 · 2019-01-10T09:30:45Z

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 · 2019-06-11T21:07:42Z

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

szuend · 2019-06-12T06:52:04Z

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 · 2019-06-14T08:27:45Z

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

ljharb · 2022-01-03T18:28:37Z

Closing, since #1585 landed.

bterlson added normative change Affects behavior required to correctly evaluate some ECMAScript source text needs consensus This needs committee consensus before it can be eligible to be merged. labels Feb 18, 2016

domenic added the web reality label Jul 28, 2016

devsnek mentioned this issue Jan 10, 2019

Array#sort aborts when elements are deleted Moddable-OpenSource/moddable#113

Closed

szuend mentioned this issue Jun 14, 2019

Normative: A more precise Array.prototype.sort #1585

Merged

ljharb closed this as completed Jan 3, 2022

dbalde mentioned this issue Jun 21, 2023

[Snyk] Security upgrade ecmarkup from 4.0.0 to 7.1.0 dbalde/ecma262#57

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

SortCompare (Array#sort) #302

SortCompare (Array#sort) #302

Yaffle commented Jan 20, 2016 •

edited

Loading

bterlson commented Jan 20, 2016

ljharb commented Jan 20, 2016

bterlson commented Jan 20, 2016

bterlson commented Jan 20, 2016

Yaffle commented Jan 20, 2016

Yaffle commented Jan 20, 2016

bterlson commented Jan 20, 2016

allenwb commented Jan 20, 2016

rossberg commented Jan 21, 2016

anba commented Jan 21, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

ljharb commented Jan 9, 2019

devsnek commented Jan 10, 2019

Yaffle commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

schuay commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019 •

edited

Loading

ljharb commented Jan 10, 2019

schuay commented Jan 10, 2019

szuend commented Jan 10, 2019

ljharb commented Jun 11, 2019

szuend commented Jun 12, 2019

mathiasbynens commented Jun 14, 2019

ljharb commented Jan 3, 2022

SortCompare (Array#sort) #302

SortCompare (Array#sort) #302

Comments

Yaffle commented Jan 20, 2016 • edited Loading

bterlson commented Jan 20, 2016

ljharb commented Jan 20, 2016

bterlson commented Jan 20, 2016

bterlson commented Jan 20, 2016

spidermonkey

Undefined elements

Holes

Holes with prototype property

chakra

Undefined elements

Holes

Holes with prototype property

d8

Undefined elements

Holes

Holes with prototype property

Yaffle commented Jan 20, 2016

Yaffle commented Jan 20, 2016

bterlson commented Jan 20, 2016

allenwb commented Jan 20, 2016

rossberg commented Jan 21, 2016

anba commented Jan 21, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

Yaffle commented Jan 26, 2016

ljharb commented Jan 26, 2016

ljharb commented Jan 9, 2019

devsnek commented Jan 10, 2019

Yaffle commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

schuay commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019

mathiasbynens commented Jan 10, 2019 • edited Loading

ljharb commented Jan 10, 2019

schuay commented Jan 10, 2019

szuend commented Jan 10, 2019

ljharb commented Jun 11, 2019

szuend commented Jun 12, 2019

mathiasbynens commented Jun 14, 2019

ljharb commented Jan 3, 2022

Yaffle commented Jan 20, 2016 •

edited

Loading

mathiasbynens commented Jan 10, 2019 •

edited

Loading