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

RESOLVED WONTFIX

Status

()

Core
JavaScript Engine
RESOLVED WONTFIX
8 years ago
8 years ago

People

(Reporter: Norman Rasmussen, Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(URL)

(Reporter)

Description

8 years ago
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

8 years ago
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.
(Reporter)

Comment 2

8 years ago
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

8 years ago
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.
(Reporter)

Comment 4

8 years ago
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

8 years ago
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.
(Reporter)

Comment 6

8 years ago
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?)
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

8 years ago
Concur about WONTFIX. Squawk if you disagree.
Status: UNCONFIRMED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → WONTFIX
(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
(Reporter)

Comment 10

8 years ago
(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.
(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
You need to log in before you can comment on or make changes to this bug.