On Dec 28, 2011, at 6:48 PM, Mark S. Miller wrote:
> ...
>
> 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'.
>
This is very close to how sort is actually specified in ES5.1(See 15.4.4.11 and
particularly step 1 of the first algorithm with numbered steps). I'm not sure
how this is particularly relevant as we seem to agree that it would be
impractical to detect misbehaving sort functions (for which we already have a
specification) or hash functions.
>
>
> > 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.
>
Actually, that wasn't my point. The existence of WeakMap/Map implies the
existence of an internal object identify hash value. Using them, application
level code can associate its own identify associated hash values with arbitrary
objects and in some cases might even use private names to decorate objects with
such hash values. This isn't as simple and probably slightly less efficient
then using a system exposed identify hash value but practical enough for
anybody who want to built special has tables that need to make use of identify
comparisons.
My real point, was that extending the Map specification to allow for use of
arbitrary comparison functions (and hence arbitrary hash functions) is perhaps
a step too far because of the issues we were discussing above. I was using the
fact that in ES.next application level code can implement efficient hash based
data structures as a supporting argument to that conclusion.
Note that I wouldn't object to limited parameterization of Map that allows
selection among ==, ===, and is as the comparison function as these all use the
same object identify hash function.
Allen
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
