archives

« Bugzilla Issues Index

#3089 — Need tighter spec language for "implementation defined" in sort, etc


"Implementation defined" allows, for example, [1, NaN].sort((a,b) => a-b), to violate memory safety. As observed (by Sam and Waldemar in 7/2014 TC39 mtg), the spec doesn't talk about memory safety, so it makes little sense to revise it to require memory safety for this particular case. And memory safety by itself is too weak -- it is just an example of how "implementation defined" makes the spec too weak to reason formally about security.

Instead, in the example case where sort is given a misbehaving comparefn, we can say that it engages in an implementation defined sequence of the following operations:

collection.[[Get]](arrayIndex)
collection.[[Set]](arrayIndex, someValueFromPreviousGet)
comparefn(someValueFromPreviousGet, someValueFromPreviousGet)

and nothing else. Note that this spec allows sort not to terminate when the comparefn misbehaves. It also does not require that the sorting of a packed array results in a packed array. But it can't manufacture non-arrayIndex property names.

Similar exercises should be attempted for other occurrences of "implementation defined".


(In reply to Mark Miller from comment #0)
> "Implementation defined" allows, for example, [1, NaN].sort((a,b) => a-b),
> to violate memory safety. As observed (by Sam and Waldemar in 7/2014 TC39
> mtg), the spec doesn't talk about memory safety, so it makes little sense to
> revise it to require memory safety for this particular case. And memory
> safety by itself is too weak -- it is just an example of how "implementation
> defined" makes the spec too weak to reason formally about security.
>
> Instead, in the example case where sort is given a misbehaving comparefn, we
> can say that it engages in an implementation defined sequence of the
> following operations:
>
> collection.[[Get]](arrayIndex)
> collection.[[Set]](arrayIndex, someValueFromPreviousGet)
> comparefn(someValueFromPreviousGet, someValueFromPreviousGet)

Other operations that must be allowed in the sequence, again in implementation defined order

collection.[[Get]]("length")

throw something, i.e., terminate abruptly, which of course must be last



>
> and nothing else. Note that this spec allows sort not to terminate when the
> comparefn misbehaves. It also does not require that the sorting of a packed
> array results in a packed array. But it can't manufacture non-arrayIndex
> property names.
>
> Similar exercises should be attempted for other occurrences of
> "implementation defined".


Another potentially observable operation that implementations do, and which is not specced, is the abstract operation ToNumber, systematically applied to the result of `comparefn()`. See Bug #3137.


The algorithm may be specified as follows:

(Steps 1-4 are already in the spec):

1. Let obj be the result of calling ToObject passing the this value as the argument.

2. Let lenValue be Get(obj, "length").

3. Let len be ToLength(lenValue).

4. ReturnIfAbrupt(len).

5. An implementation-defined succession of the following abstract operations:

* HasProperty(obj, kString),
where kString is the string representation of an integer between 0 and len-1;

* Get(obj, kString),
where kString is the string representation of an integer between 0 and len-1;

* SortCompare(V, W, comparefn), /* stylistic nit: comparefn is explicit arg */
where V and W are values returned by Get(obj, kString) operations;

* Put(obj, kString, V, true),
where kString is the string representation of an integer between 0 and len-1,
and where V is a value returned by a Get(obj, kString) operation;

* DeletePropertyOrThrow(obj, kString),
where kString is the string representation of an integer between 0 and len-1.
Moreover, that operation is allowed only if at least one call to
HasProperty(obj, kString) had returned false.

Moreover, if any of these operations returns an abrupt completion,
the algorithms ends immediately using that abrupt completion as its returned value.

6. Return obj.

Together with the amendment of SortCompare proposed in Bug #3137, I believe it is what the implementations do today.

The rest of the section should just give the further requirement that, under reasonable conditions, `obj` must be sorted at the end of the algorithm. Here "reasonable conditions" might be hard to correctly specify, because some of the operations given in Step 5 may have nasty side effects.


Correction: As currently specified, SortCompare takes as arguments the indices of the array to be sorted, and not its values; moreover the HasProperty(...) and Get(...) operations are included in the SortCompare abstract operations.

However, some experiment show that what the spec says, is not exactly what the implementations do. More precisely, the Get and HasProperty operations should be taken away of the SortCompare abstract operation, in order to align with implementations:

* IE and Firefox first do a series the HasProperty/Get operations, then a series of calls to comparefn, each of them followed by a ToNumber operation, then a series of Put/DeletePropertyOrThrow operations. Curiously, IE adds a further series of Get operations at the end of the process.

* Safari, Chrome and Opera have their HasProperty/Get and Put/DeletePropertyOrThrow operations intermingled with their calls to comparefn (followed by ToNumber operation); however, they don't do all the Get operations required by SortCompare(...), but omit some of them when the value is already known from a previous Get operation.

Here is what I used to induce the description above. Further experiment using proxies is needed in order to be sure of when the implementations do HasProperty and (in case of sparse arrays) DeletePropertyOrThrow.

var a = Array(10)
for (var i = 0; i < a.length; i++) {
a[i] = Math.floor(Math.random()*900 + 100)
}

var b = Object.defineProperty({}, 'length', {
get: function() { console.log('Get(b, "length")'); return a.length }
})
for (var i = 0; i < a.length; i++) (function(i) {
Object.defineProperty(b, i, {
get: function() { console.log('Get(b, '+i+')'); return a[i] }
, set: function(v) { console.log('Put(b, '+i+', '+v+')'); a[i] = v }
})
})(i)

function comparefn(a, b) {
console.log('comparefn('+a+', '+b+')')
return { valueOf: function() { console.log('valueOf()'); return a - b } }
}

;[].sort.call(b, comparefn)


fixed in rev27 editor's draft


fixed in rev27 draft