ecma262
ecma262 copied to clipboard
tc39
Call SortCompare only on actual elements
I suggest adding to 23.1.3.30.1 SortIndexedProperties ( obj, len, SortCompare, holes ) the requirement that (unless the container is modified during sorting or some other shenanigans occur) SortCompare be only called on pairs of elements that are actually being sorted. This would have the following advantages:
- The programmer needn't bother handling arbitrary values in the supplied comparator in a way that doesn't give an error, use too much resources or cause computational side effects.
- Nontermination is a specific side effect, but I mention it separately, given that there's no defence against it in ECMAScript. An implementation would apparently be compliant (albeit of poor quality) with the current spec if it always started sorting by passing to SortCompare a Proxy object whose all traps loop.
Additional useful guarantees to consider:
- Arguments passed to SortCompare are always from different indices in the container.
- Arguments passed to SortCompare are always in an (indefinite because elements may repeat) order corresponding to their indices in the container.
I believe all non-experimental implementations already satisfy all of the above. Furthermore, I know of no optimizations that would be thereby prevented, even under additional assumptions that an implementation may be able to make in some circumstances (e.g. that all elements are of type BigInt). There may even be proofs that wide classes of such optimizations are impossible.
I don't think requiring the arguments to be elements of the container is unreasonable, but the other two suggestions are not valid. An implementation, for example, may perform SortCompare(a, a) or other interesting sequences of calls to determine whether the given implementation of SortCompare is stable.
There is no sequence of calls you can make to SortCompare to determine whether it's consistent. If you make n calls, the one that makes it not consistent might be the (n+1)th.
That’s not necessarily true - you could make and cache every combination of (a, b), (b, a), (a, a), and (b, b) for every item on the container, before doing the sort with the results :-p i assume that wouldn’t be performant tho.
@nicolo-ribaudo yes I guess to be very specific, whether the function is unstable for specific comparisons. I bring it up because, unless my memory is completely wrong, one of the major browsers did something similar to this at one point...
~~Yet further improvement unburdening the programmer in some situations would be not to require (if the postconditions guaranteeing correctness of sorting are to be satisfied) the passed function to be a consistent comparator (in addition to the container not being modified), just for its results obtained in step 4 of SortIndexedProperties to be such that some consistent comparator could give them.~~ (Edited to strike. Given the observation in https://github.com/tc39/ecma262/issues/3172#issuecomment-1718241776, it can be expressed simpler as below.)
~~Such a comparator could depend on some state, e.g. the location selected in an application which the user can change. It doesn't change during execution of a call to sort, but it may between calls (so caching would make the comparator's inconsistency manifest).~~
(Edited to strike. In https://github.com/tc39/ecma262/issues/3172#issuecomment-1718241776 I explain why it's already supported by creating a new Abstract Closure (not preserved) with each call to sort (if step 4 is reached).)
(Edited to add this.) The definition of consistent comparer should be relative to a set of values which actually can be supplied to the Abstract Closure (those present in items). Implementations should not (be allowed to) care what would happen if they called the comparer with some wild arguments.
It is very critical, i think, that only a consistent (pure) comparator be provided to sort. Encouraging (or tacitly allowing) anything else is what will burden a programmer.
What's the burden? In the example I gave the programmer is currently required to create a new Function object each time the user makes a change (e.g. selects a different country from a list) on pain of having the result not being sorted (and possibly not even a permutation). It seems reasonable when passing a comparator which is consistent during execution of a call to sort to expect that implementations won't somehow inspect what results it would give when used in another potential or actual call to sort and use it as a pretext to mess up.
I've also arrived at the conclusion that what's currently specced is even worse than initially suspected: an almost blanket permission for UB. If the comparator in any way touches (does anything that would call a trap if it were a Proxy object) any of its arguments (step 4 doesn't even require that the implementation always provide two (it's perhaps worth a separate issue to make Abstract Closures have fixed arities, unlike language functions)), all bets are off. The implementation may pass a host object (even one otherwise unavailable) which always throws, loops forever, launches missiles or hijacks the engine and starts executing comments (all of which are fair game for host objects).
On the other (than in my previous comment) hand, I have some good news too. Step 4 in 23.1.3.30 Array.prototype.sort ( comparefn ) says: "Let SortCompare be a new Abstract Closure". (Although the definition of consistent comparator is misleading, namely too broad, allowing it to be an "abstract closure or function", while it's only ever the former.) So my concern from https://github.com/tc39/ecma262/issues/3172#issuecomment-1716687305 isn't valid; the required behaviour in that respect is already as I suggested. I'm going to edit it accordingly.
I don't understand this issue. The way SortIndexedProperties works is, it will first read all of the things in the array (in a fully specified way) into a list items, and then it will "Sort items using an implementation-defined sequence of calls to SortCompare". To me that is already sufficient to constrain it to only calling SortCompare on actual elements of the provided array. What more are you asking for?
implementation-defined behavior isn't the same as undefined behavior.
It seems to me that in ECMAScript they are the same. The spec doesn't mention undefined behaviour, but the meaning of implementation-defined is such as that. Namely, the implementation can do anything (possibly limited by some requirements that still don't narrow the behaviour down to just one possibility) and needn't document it. (It may also do different things on different occasions.)
I don't understand this issue. The way SortIndexedProperties works is, it will first read all of the things in the array (in a fully specified way) into a list
items, and then it will "Sortitemsusing an implementation-defined sequence of calls to SortCompare". To me that is already sufficient to constrain it to only calling SortCompare on actual elements of the provided array. What more are you asking for?
If that's how it's commonly understood, then fine. That's the main issue. (I've included a wishlist of other things in further comments, but they're minor compared to this, so just nice to have.)
It seems to me that in ECMAScript they are the same. The spec doesn't mention undefined behaviour, but the meaning of implementation-defined is such as that. Namely, the implementation can do anything (possibly limited by some requirements that still don't narrow the behaviour down to just one possibility) and needn't document it. (It may also do different things on different occasions.)
This is a misunderstanding. The spec says that in some cases the choice of order is implementation defined. That means the implementation can choose the order however it wants. It doesn't mean it can do arbitrary other things.