W3C home > Mailing lists > Public > public-script-coord@w3.org > January to March 2015

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

From: Mark S. Miller <erights@google.com>
Date: Mon, 2 Mar 2015 16:45:03 -0800
Message-ID: <CABHxS9hHM5=12BPyK_kf0X5Tbd_d-qmtWp1t-iU5Wnrb19yn5Q@mail.gmail.com>
To: "Tab Atkins Jr." <jackalmage@gmail.com>
Cc: David Dorwin <ddorwin@google.com>, public-script-coord <public-script-coord@w3.org>, Boris Zbarsky <bzbarsky@mit.edu>
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));
    } 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)); }
Received on Tuesday, 3 March 2015 00:45:32 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 3 March 2015 00:45:32 UTC