Harmony WeakMap shim for ES5

weak-map.js

/* vim:set ts=2 sw=2 sts=2 expandtab */
/*jshint asi: true undef: true es5: true node: true devel: true
         forin: false latedef: false */
/*global define: true */


if (typeof(WeakMap) === 'undefined') WeakMap = (function(global) {
  "use strict";

  function defineNamespace(object, namespace) {
    /**
    Utility function takes `object` and `namespace` and overrides `valueOf`
    method of `object`, so that when called with a `namespace` argument,
    `private` object associated with this `namespace` is returned. If argument
    is different, `valueOf` falls back to original `valueOf` property.
    **/

    // Private inherits from `object`, so that `this.foo` will refer to the
    // `object.foo`. Also, original `valueOf` is saved in order to be able to
    // delegate to it when necessary.
    var privates = Object.create(object), base = object.valueOf
    Object.defineProperty(object, 'valueOf', { value: function valueOf(value) {
      // If `this` or `namespace` is not associated with a `privates` being
      // stored we fallback to original `valueOf`, otherwise we return privates.
      return value != namespace || this != object ? base.apply(this, arguments)
                                                  : privates
    }, configurable: true })
    return privates
  }

  function Name() {
    /**
    Desugared implementation of private names proposal. API is different as
    it's not possible to implement API proposed for harmony with in ES5. In
    terms of provided functionality it supposed to be same.
    http://wiki.ecmascript.org/doku.php?id=strawman:private_names
    **/

    var namespace = {}
    return function name(object) {
      var privates = object.valueOf(namespace)
      return privates !== object ? privates : defineNamespace(object, namespace)
    }
  }

  function guard(key) {
    /**
    Utility function to guard WeakMap methods from keys that are not
    a non-null objects.
    **/

    if (key !== Object(key)) throw TypeError("value is not a non-null object")
    return key
  }

  function WeakMap() {
    /**
    Implementation of harmony `WeakMaps`, in ES5. This implementation will
    work only with keys that have configurable `valueOf` property (which is
    a default for all non-frozen objects).
    http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps
    **/

    var privates = Name()

    return Object.freeze(Object.create(WeakMap.prototype, {
      has: {
        value: function has(object) {
          return 'value' in privates(object)
        },
        configurable: true,
        enumerable: false,
        writable: true
      },
      get: {
        value: function get(key, fallback) {
          return privates(guard(key)).value || fallback
        },
        configurable: true,
        enumerable: false,
        writable: true
      },
      set: {
        value: function set(key, value) {
          privates(guard(key)).value = value
        },
        configurable: true,
        enumerable: false,
        writable: true
      },
      'delete': {
        value: function set(key) {
          return delete privates(guard(key)).value
        },
        configurable: true,
        enumerable: false,
        writable: true
      }
    }))
  }

  return global.WeakMap = WeakMap
})(this)

Set writable: true in the Object.defineProperty call to allow the same key to be in multiple weakmaps.

Why delete is enumerable unlike has, set & get?

@paulmillr none of them are unemerable, it's just delete is not writable or configurable, I don't know why.

@Raynos Hmm, I thought when overriding existing property configurable, enumerable, writable flags were inheriting previous values. It looks like they don't, so I made valueOf configurable to be able to override it, but kept non-writable to avoid unexpected overrides from other code.

@paulmillr thanks for pointing that out. @Raynos No real reason, just forgot to put flags there :)

missing comma on line 94. You try this script out, bro?

missing comma on line 94. You try this script out, bro?

Yeah it worked in first revision, but forgot about , when addressed https://gist.github.com/1269991/dbfd183b55798a2a166af360c95575f729ced02d#gistcomment-77061

Thanks for pointing out

np!

I ended up going with this one due to some funky behavior I can't repro atm..

http://code.google.com/p/es-lab/source/browse/trunk/src/ses/WeakMap.js

I've been trying to understand the implications of this:

TODO: Revisit Mike Stay's suggestion that we use an
encapsulated function at a not-necessarily-secret name, which
uses the Stiegler shared-state rights amplification pattern to
reveal the associated value only to the WeakMap in which this key
is associated with that value. Since only the key retains the
function, the function can also remember the key without causing
leakage of the key, so this doesn't violate our general gc
goals.

Which is implemented here. Is that indicating full GC semantics of proper WeakMaps, or still only the "mostly there but not quite" semantics where the key strongly holds the value? I assume the latter since object -> valueOf -> hidden key -> value.

As a follow up if the answer is no, I wonder if it's even theoretically possible to fully implement WeakMap GC in a shim. It's possible with the huge caveat that it requires asynchronous lookups of the value and polling in order for keys to check for lookups on them, but that's basically unusable.

My understanding of this implementation is that key holds a the value, which I believe matches how WeakMap are supposed to behave. That being said things may get tricky if multiple such WeakMaps are used for the same key since references to the previous key will be hold by a following one. Not to even mention that this will only work for keys that are not frozen.

So, I think it may be used as a ship if used with a care. There is alternative approach implemented by SES http://code.google.com/p/es-lab/source/browse/trunk/src/ses/WeakMap.js
I don't think there is any other implementation strategies other than implementing mark and sweep

@Benvie: we are both searching for something having like Java's "WeakHashMap".

Unfortunately this is not the case. The map presented here is a map where only who holds the key can access the value, which is probably a "secure map", but not a weak map, in the Java sense.

It does not prevent BOTH key and object to be garbage collected. Also, it does not prevent the KEY itself to be garbage collected; however, since you need that exact instance of the key to recover the object, and not any object.equals(key) == true, this feature is of no use.

The whole purpose of a WeakMap (in the strict sense) is to check whether a certain object is still "live" or has been garbage collected, and as far as I know there is no way to implement this without stuff like WeakReferences or GC callbacks (finalizers or whatever else) or other stuff provided by the underlying runtime.

The fact that WeakMap elements are not iterable/enumberable, for example, is NOT an intended feature for security reasons, is just a side effect of garbage collection happening at undefined moment, and that would make it unstable and with unknown results.

The SES implementation, also, is not a WeakMap in the GC sense, since SES goal is to implement secure javascript they have a lot of "security stuff", but are basically still not GC safe.

It's fun to see how everyone hates Java cause it's complicated, love JS cause it's simple, and then discover that they need that same stuff they had in Java in JS.

It does not prevent BOTH key and object to be garbage collected. Also, it does not prevent the KEY itself to be
garbage collected; however, since you need that exact instance of the key to recover the object, and not any
object.equals(key) == true, this feature is of no use.

There is no object.equals(key) in JS

The whole point of this weak map implementation is to provide shim for http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps

Which allows one to associate values to keys. If key is GC-ed value will be GC-ed as well unless there is some other references to it. I find this to be pretty useful in a lot of cases so I disagree with "this feature is of no use." statement.

WeakMaps (and this shim which upholds the spec in all material ways) has three use cases that I find a lot of use for:

1.) Wrapping/unwrapping public/private values. A regular map also serves here but the implementation of the shim is the same for a map as it is for a weak map.

2.) Extension of 1 is mapping an object to a private data store for it. This is providing the same service as, for example, jQuery.data to attach data to DOM elements without causing memory leaks. Except jQuery's method (same one used by every library I know) only protects from one end. All the JS values in the data store will never be garbage collected. Using this shim (and regular WeakMaps of course) you can provide a way for JS objects to be garbage collected with the DOM elements they are backing.

3.) Secure public/private unforgeable data transmission. This shim is just as secure real WeakMaps and there's a lot of coll things you can do with them (outlined on the Wiki).

I expanded the idea backing the shim in this gist into a pretty complete implementation https://github.com/Benvie/ES6-Harmony-Collections-Shim (replacing my older much worse repo by the same name). It incorporates some ideas from the SES implementation into this one, and expands on both.

First, a unique randomly generated namespace is created upon first shimming. This doesn't need to be secure, just something that won't accidentally conflict with normal usage of objects. At the same time, Object.getOwnPropertyNames is patched. This is a very light patch that is pretty efficient. It basically checks for hasOwn(obj, randomNamespace) and splices it if it exists. With GOPN patched and using a non-enumerable property the shim becomes almost entirely non-observable. In order to observe it you'd have to grab a new GOPN from another context or have a reference to the original one.

Inside this single random namspace per session is where the data is stored. Each WeakMap instance also generates a random name which it uses to store the Name on. This way there's no issue with conflicts or having to wrap the same unlocker in multiple layers, and you also don't litter objects with a bunch of random keys. Just the one single common name that houses the rest.

Then using the initial WeakMap shim I bootstrap in Map and Set (also Hashmap which is paired with WeakMap to implement primitive keys). The collection instances themselves are stored using the private storage, so the interfaces provided are almost identical to the real implementation (prototype methods instead of per instance bound versions).

@Benvie Sorry, like SimonGianni pointed out. This does not have the GC behavior that is required for WeakMap. It may well be functionally a fine shim for the map functionality of WeakMap but it will be leaky. It is impossible to emulate the required GC behavior outside of the garbage collector. That's why WeakMap exists.