On Wed, Dec 28, 2011 at 4:23 PM, Allen Wirfs-Brock <al...@wirfs-brock.com>wrote:
>
> On Dec 27, 2011, at 10:20 AM, Mark S. Miller wrote:
>
> > Hi Axel, yes, I would like to extend their constructor in this way.
> However, I'm not sure how to spec it -- help appreciated. The problem is
> that the comparator needs to provide both an equivalence operation and a
> corresponding hash operation. When these agree, all is well. What should we
> specify happens when passing in a misbehaving comparator? The dilemma is
> that
>
[responding out of order]
> > 2) having a deterministic collection misbehavior in the face of
> comparator misbehavior seems hard, and
>
> But it isn't clear that this is a requirement.
>
I agree. In fact, I think such detection is likely hard enough that it is
effectively a requirement that the spec not obligate an implementation to
detect such misbehavior.
> > 1) detecting misbehavior is expensive,
>
> For sort comparison function we simply say that the behavior is undefined
> for a misbehaving comparison function. It isn't clear that this has cause
> any significant problems or that it is very likely that we will require
> detection of misbehaving sort comparison functions.
>
Likewise, I expect that detecting misbehavior sort comparison functions is
too hard to be practical. However, I strongly disagree that the current
underspecification isn't a problem. How undefined is this behavior?
(Actually, the language in 15.4.4.11 is "implementation defined", which
isn't really any better.) Can [1,2,3].sort(function(){return 1;}) evaluate
to the password of the current user? Can it violate same origin
restrictions or memory safety? Can it launch the nukes? If so, then none of
our reasoning about security (whether conventional or ocap) or safely of
any kind is sound. Rather, we get away with such reasoning because we all
share an unstated model about the real limits on this misbehavior. Since
*any* sound reasoning about safety or security depends on this shared
understanding, it behooves us as authors of the specification to codify
these limits.
For example, regarding sorting, leaving aside sparseness, I suspect our
shared model is that any sort algorithm implementation itself takes only
the following observable steps, but in some arbitrary order and not
necessarily terminating:
obj.[[Get]](String(i)), where i is an integer && 0 <= i && i < len (recall
that len is already the result of array.[[Get]]('length'))
obj.[[Put]](String(i), x), where i as above, and x is only a value
previously gotten with a [[Get]]
ToNumber(comparefn(x, y)), where x and y are only values previously gotten
with a [[Get]]
To adjust for sparseness, the sort function may also invoke
obj.[[HasProperty]](String(i))
obj.[[HasOwnProperty]](String(i)) // perhaps? I see no mention of it in the
algorithm
obj.[[Delete]](String(i))
obj.[[Put]]('length', String(i))
Notice that this specification does not assume away the possibility of
arbitrary side effects or I/O caused by the comparefn or by accessor
properties at obj indexes or 'length'.
>
> > 3) we'd like to avoid yet more under-specification. The similar
> under-specification of Array.prototype.sort is already bad enough.
>
>
> But, I think that the key point here is that if we allow specification of
> an arbitrary comparator function then we must require that a corresponding
> hash function is also provided. That seems like a big step down a slippery
> slope.
>
> We should probably avoid pressures for the build-ins to cover all possible
> use cases. In ES.next we will should have all the primitives necessary for
> JS programmers to define their own efficient collection objects, including
> various kinds of hash-tables. Hopefully some good libraries of such will
> get written.
>
I take it you are simply reiterating the desire for a standard system
provided high entropy object-identity hash that is guaranteed to correspond
to === and is. I agree (though it didn't make it into ES6), but that's the
dual of the question Axel is asking.
What do you think of my approach to limiting the possible misbehavior of
sort?
--
Cheers,
--MarkM
_______________________________________________
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
