Web IDL maplike: Allow spec prose to specify how key-type should be compared?

# David Dorwin (a year ago)

heycam.github.io/webidl/#es-maplike defines the behavior of maplike objects it in terms of delegation to an actual ES Map object. This means that if the key-type is an object, keys are compared by object ID rather than content. Thus, has() and get() will only return positive results if the same object that is stored is passed.

This works for things like a Node, which the application could actually obtain, but it doesn't work for values that are represented by objects. Specifically, a value in a BufferSource. Should specifications be allowed to specify a different behavior in prose or should we force them to manually define the map methods? Should such non-compliant manual maps be discouraged?

As a concrete example, for EME, we attempted to use a readonly maplike with a key-type of BufferSource, which contains a binary key ID. This can be made to work by comparing the value in the BufferSource, but this is not compliant with the maplike spec. (See the EME spec bug w3c/encrypted-media#25 for more details.) If there is no change to the maplike spec to allow prose to modify the comparison behavior, EME will likely switch to a manually defined map-like interface. (We could also use a primitive type to represent the key ID, but that is inconsistent with other representations of binary data in the spec.)

Contact us to advertise here
# Tab Atkins Jr. (a year ago)

On Mon, Mar 2, 2015 at 2:28 PM, David Dorwin ddorwin@google.com wrote:

heycam.github.io/webidl/#es-maplike defines the behavior of maplike objects it in terms of delegation to an actual ES Map object. This means that if the key-type is an object, keys are compared by object ID rather than content. Thus, has() and get() will only return positive results if the same object that is stored is passed.

This works for things like a Node, which the application could actually obtain, but it doesn't work for values that are represented by objects. Specifically, a value in a BufferSource. Should specifications be allowed to specify a different behavior in prose or should we force them to manually define the map methods? Should such non-compliant manual maps be discouraged?

As a concrete example, for EME, we attempted to use a readonly maplike with a key-type of BufferSource, which contains a binary key ID. This can be made to work by comparing the value in the BufferSource, but this is not compliant with the maplike spec. (See the EME spec bug w3c/encrypted-media#25 for more details.) If there is no change to the maplike spec to allow prose to modify the comparison behavior, EME will likely switch to a manually defined map-like interface. (We could also use a primitive type to represent the key ID, but that is inconsistent with other representations of binary data in the spec.)

Given that this is backed by a Map, I don't think we can realistically do this until Maps gain the ability to specify a key comparator. (Same with Set.)

~TJ

# Mark S. Miller (a year ago)

On Mon, Mar 2, 2015 at 3:08 PM, Tab Atkins Jr. jackalmage@gmail.com wrote:

On Mon, Mar 2, 2015 at 2:28 PM, David Dorwin ddorwin@google.com wrote:

[...]

Given that this is backed by a Map, I don't think we can realistically do this until Maps gain the ability to specify a key comparator.

The following code is untested, and was written only to play with an idea provoked by this thread. It may also be besides the actual point of this thread, but...

/*

  • Makes a projection from keys to ids. *
  • Given the usual kind of comparator, with the signature *
  • interface Comparator<K> {
  • hash(k :K) :value;
  • eq(k1 :K, k2 :K) :boolean;
  • } *
  • with the usual contract that eq forms an equivalence class of Ks,
  • and hash is a many-to-one mapping from these equivalence classes to
  • hashable non-object values of some sort, like numbers. Let's call
  • the K objects that a given comparator compares "keys". We assume
  • here that keys are genuine objects and so can be used as keys in
  • WeakMaps. *
  • For objects, EcmaScript 2015 Maps map from object identities
  • to values. Let's call an empty object whose only purpose is to have
  • a unique identity, for use as keys in these Map objects, an "id". *
  • makeProjector, given a comparator, returns a project function which
  • projects keys to ids. Like the comparator's hash, it maps all keys
  • in the same equivalence class (as defined by the comparator) into
  • the same id. Unlike the comparator's hash, the mapping from
  • equivalence class to id is one-to-one. */

const projectors = new WeakMap();

function makeProjector(comparator) { if (projectors.has(comparator)) { // Caching the comparator-to-projector mapping does much more than // save the trivial effort to make a new projector. It means that // all the projecting for a given comparator gets to share the // same idCache. return projectors.get(comparator); } const buckets = new Map(); const idCache = new WeakMap(); function project(key) { if (idCache.has(key)) { // Thus, for any given key object, we only use the comparator

  • // the first time we project it*. return idCache.get(key); } const hash = comparator.hash(key); let bucket = void 0; let id = void 0; findId: if (buckets.has(hash)) { const bucket = buckets.get(hash); for (let [k,i] of bucket) { if (comparator.eq(key, k)) { id = i; break findId; } } id = Object.freeze(Object.create(null)); bucket.push([key,id]); } else { id = Object.freeze(Object.create(null)); buckets.set(hash, [[key,id]]); } idCache.set(key, id); return id; } projectors.set(comparator, Object.freeze(project)); return project; }

/*

  • Uses makeProjector to make the obvious Map wrapper */ function Mapish(comparator) { const project = makeProjector(comparator); const map = new Map(); return Object.freeze({ has(key) { return map.has(project(key)); } get(key) { return map.get(project(key)); } set(key,v) { map.set(project(key),v); } delete(key) { map.delete(project(key)); } }); }
# Tab Atkins Jr. (a year ago)

On Mon, Mar 2, 2015 at 4:45 PM, Mark S. Miller erights@google.com wrote:

On Mon, Mar 2, 2015 at 3:08 PM, Tab Atkins Jr. jackalmage@gmail.com wrote:

On Mon, Mar 2, 2015 at 2:28 PM, David Dorwin ddorwin@google.com wrote:

[...] >

Given that this is backed by a Map, I don't think we can realistically do this until Maps gain the ability to specify a key comparator.

The following code is untested, and was written only to play with an idea provoked by this thread. It may also be besides the actual point of this thread, but... [snip code]

Yeah, it's not that difficult to design an object that exposes the Map interface and does key-comparing for you, but the important bit is that that's not a Map. Future extensions to Map, or user-extensions to the object, don't apply to it, Map.prototype.set doesn't work on it, etc.

(This is one more instance of the general problem I've brought up a few times, that Map/Set aren't customizable in any way and it's really an issue. There should be an internal "SimpleMap" that just exposes the core methods needed, and which can be swapped out by users or specs for another object undetectably, so that Map/Set operate as an interface contract.)

~TJ

# Jonas Sicking (a year ago)

On Mon, Mar 9, 2015 at 11:23 AM, Tab Atkins Jr. jackalmage@gmail.com wrote:

(This is one more instance of the general problem I've brought up a few times, that Map/Set aren't customizable in any way and it's really an issue. There should be an internal "SimpleMap" that just exposes the core methods needed, and which can be swapped out by users or specs for another object undetectably, so that Map/Set operate as an interface contract.)

ES doesn't really have the concept of "interface" which really is what we're looking for here. It always ties interface and implementation together into specific classes. Classes which always have a constructor and which makes sense on their own.

Another example of when this problem shows up is in the design of the Stream class. The two "ends" of a stream should really be two separate objects with a specified interface. Those two objects should always work in concert to make up the stream object. However JS doesn't allow creation of those two objects without requiring that each object also can be instantiated and useful on its own.

The closest thing to "interface" that JS has is "duck type".

/ Jonas

# Mark S. Miller (a year ago)

On Mon, Mar 9, 2015 at 12:05 PM, Jonas Sicking jonas@sicking.cc wrote:

On Mon, Mar 9, 2015 at 11:23 AM, Tab Atkins Jr. jackalmage@gmail.com wrote:

(This is one more instance of the general problem I've brought up a few times, that Map/Set aren't customizable in any way and it's really an issue. There should be an internal "SimpleMap" that just exposes the core methods needed, and which can be swapped out by users or specs for another object undetectably, so that Map/Set operate as an interface contract.)

ES doesn't really have the concept of "interface" which really is what we're looking for here. It always ties interface and implementation together into specific classes. Classes which always have a constructor and which makes sense on their own.

Another example of when this problem shows up is in the design of the Stream class. The two "ends" of a stream should really be two separate objects with a specified interface. Those two objects should always work in concert to make up the stream object. However JS doesn't allow creation of those two objects without requiring that each object also can be instantiated and useful on its own.

That's one of things that's so cool about the Promise constructor pattern:

var resolver; var promise = new Promise(r => resolver = r);

Couldn't this be applies to streams? (I haven't yet followed streams.)

# Jonas Sicking (a year ago)

On Mon, Mar 9, 2015 at 12:11 PM, Mark S. Miller erights@google.com wrote:

That's one of things that's so cool about the Promise constructor pattern:

var resolver; var promise = new Promise(r => resolver = r);

Couldn't this be applies to streams? (I haven't yet followed streams.)

Sadly not. Because 'r' still needs to have a constructor.

/ Jonas

# Allen Wirfs-Brock (a year ago)

On Mar 9, 2015, at 12:05 PM, Jonas Sicking wrote:

Another example of when this problem shows up is in the design of the Stream class. The two "ends" of a stream should really be two separate objects with a specified interface. Those two objects should always work in concert to make up the stream object. However JS doesn't allow creation of those two objects without requiring that each object also can be instantiated and useful on its own.

The closest thing to "interface" that JS has is "duck type".

Proxy.revoable people.mozilla.org/~jorendorff/es6-draft.html#sec-proxy.revocable is an ES6 API that creates two "linked" objects.

# Mark S. Miller (a year ago)

I can see why it may need a prototype. But why does it need a constructor?

# Jonas Sicking (a year ago)

On Mon, Mar 9, 2015 at 1:10 PM, Mark S. Miller erights@google.com wrote:

I can see why it may need a prototype. But why does it need a constructor?

From what I'm told, in order to explain how the object was created.

I.e. to avoid building "magic" into the API.

But maybe there are other ways to do that?

/ Jonas

# Tab Atkins Jr. (a year ago)

On Mon, Mar 9, 2015 at 2:37 PM, Jonas Sicking jonas@sicking.cc wrote:

On Mon, Mar 9, 2015 at 1:10 PM, Mark S. Miller erights@google.com wrote:

I can see why it may need a prototype. But why does it need a constructor?

From what I'm told, in order to explain how the object was created. I.e. to avoid building "magic" into the API.

But maybe there are other ways to do that?

This is a cool discussion, but it's also a complete tangent from the original thread. ^_^

~TJ

# Mark S. Miller (a year ago)

Want more features?

Request early access to our private beta of readable email premium.