549237 - array.sort(function) should care that the function is consistent

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Norman Rasmussen]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6 GTB6 (.NET CLR 3.5.30729)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6 GTB6 (.NET CLR 3.5.30729)

re: http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html

c++'s stl cares about ordering constraints (if the sort function isn't consistent, it can cause segfaults).

ECMA-262 says: "If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the behaviour of sort is implementation-defined."

Reproducible: Always

Steps to Reproduce:
1. create array
2. array.sort(function() { 0.5 - Math.random(); });
3.
Actual Results:  
No errors are logged, array is poorly sorted

Expected Results:  
sort should log an error and/or fail.

I would like the SpideMonkey implementation to care about consistency and not just hide it from the user.  Failing the sort would cause too much breakage, but could it at least log an error?

I'm not sure if there's a good/quick/fast way to test for consistency, any lazy check will probably not catch any math.random() implementations properly.

Comment 1

[Jo Hermans]

The (anonymous) function takes no arguments here, so it can never give consistent results for the same keys. Unless it always returns the same value, which *is* consistent, although still wrong.

But is it really necessary to detect this? The behavior is implementation defined after all, so it doesn't matter what is returned, correct or not.

Comment 2

[Norman Rasmussen]

re: https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort

the function is defined as: compareFunction(a, b)- where a and b are elements to compare.

interestingly I couldn't get firefox to do anything with a.sort(function(a,b){0.5-Math.random();}), but if I pre-declare the function and pass it in, it changes the order of the array's elements.

It's not really necessary to detect this, but an inconsistent sort function is a bad-thing™ (in cpp's stl causes a segfault!) and it would be a good-thing™ to tell developers that they're doing something that's totally unsupported.

There should probably be a easily noticeable warning on the developer.mozilla.org too.

Comment 3

[Jeff Walden [:Waldo]]

Detecting this would probably take a little extra bookkeeping that would probably slow down the sort algorithm; I very much doubt it's cost-free.  I say we work on things people will care about more than detecting poor sort implementations.

Comment 4

[Norman Rasmussen]

Is there a quick and easy way in SpiderMonkey to check if random is called from within sort?  (I'm thinking some sort of stack traverse, or check that there no references to the random method when compiling).

re, adding a comment to documentation (to the end of the bullet list in the description), what about something like:
 o compareFunction(a, b) must always returns the same value when given a specific pair of elements a and b as its two arguments.  If inconsistent results are returned then the sort order is undefined.

Comment 5

[Andreas Gal :gal]

Define "random". Math.random() is a pseudo-random generator. You can implement your own. Whether a function generates a pseudo-random number of a given quality is undecidable. We could check whether f(a, b) == f(a, b), but that would cause another (unexpected) invocation of f, which might break compatibility.

Comment 6

[Norman Rasmussen]

ahh, drat - I hadn't though that you could implement your own random.  I don't think that extra invocations of f(a,b) is a problem, there's no contract anywhere that says that the function will be called a particular number of times, or in a particular pattern.  (maybe only to fingerprint the javascript engine?)

Comment 7

[Nicholas Nethercote [inactive]]

I'm all in favour of compilers detecting user errors, but this one seems like too much of a stretch.  I suggest WONTFIX.

Comment 8

[Robert Sayre]

Concur about WONTFIX. Squawk if you disagree.

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #2)
> re:
> https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort
> 
> the function is defined as: compareFunction(a, b)- where a and b are elements
> to compare.
> 
> interestingly I couldn't get firefox to do anything with
> a.sort(function(a,b){0.5-Math.random();}),

You are missing a return.

> but if I pre-declare the function
> and pass it in, it changes the order of the array's elements.

When you pre-declared the function, you supplied the missing return, right?

/be

Comment 10

[Norman Rasmussen]

(In reply to comment #9)
> (In reply to comment #2)
> > re:
> > https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort
> > 
> > the function is defined as: compareFunction(a, b)- where a and b are elements
> > to compare.
> > 
> > interestingly I couldn't get firefox to do anything with
> > a.sort(function(a,b){0.5-Math.random();}),
> 
> You are missing a return.

ooops, way too used to python's lambda's :-)

> > but if I pre-declare the function
> > and pass it in, it changes the order of the array's elements.
> 
> When you pre-declared the function, you supplied the missing return, right?
>
> /be

yep, probably.

Comment 11

[Brendan Eich [:brendan]]

(In reply to comment #10)
> (In reply to comment #9)
> > (In reply to comment #2)
> > > re:
> > > https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/sort
> > > 
> > > the function is defined as: compareFunction(a, b)- where a and b are elements
> > > to compare.
> > > 
> > > interestingly I couldn't get firefox to do anything with
> > > a.sort(function(a,b){0.5-Math.random();}),
> > 
> > You are missing a return.
> 
> ooops, way too used to python's lambda's :-)

If you are able to target Firefox only (Firefox 3/JS1.8 and up), you could use an expression closure:

a.sort(function(a,b)(0.5-Math.random()))

/be