How to implement TwoWayWeakMap? Using WeakRef?

The idea is that TwoWayWeakMap would work like WeakMap, except that you would be able to get key objects by their value. For example, here is how the usage would look like:

class TwoWayWeakMap {
  // What goes here?

class SomeClass {}

const map = new TwoWayWeakMap<SomeClass, number>()

function main() {
  const o = new SomeClass

  map.set(o, 42)

  console.log(map.get(o)) // logs "42"
  console.log(map.keyFrom(42)) // logs "SomeClass {}" (the `o` object)


Once main() completes, I would expect the o key to be collected at some point when it is no longer referenced.

Calling keyFrom with a value that was mapped from the object would return undefined, which would be similar to WeakRef returning undefined after an object has been collected.

I gave it a shot using WeakRef, but it doesn't seem that the object is ever collected. Maybe I missed something silly. If the following example were to work as I intended, then eventually it would log "o was collected!", but you'll see in your console that the object persists, even after forcing garbage collection in Chrome's devtools:

console.log keeps the object alive. Strangely enough, even if you only print it once, then clear the console. Adjust these two lines so that console.log doesn't get hold of the object:

console.log(`o still exists? (${tick++})`, !!obj);

I think there's also a bug/typo in this part:

for (const ref of this.#refs) {
    const o = ref.deref();
    if (!o) {
        return undefined; // <<< I don't think returning here is correct, the ref could have been for a different key/value pair
    if (this.get(o) === v) return o;

Maybe this:

for (const ref of this.#refs) {
    const o = ref.deref();
    if (o === undefined) {
    } else {
        if (this.get(o) === v) return o;
1 Like

Hey, thanks! I had since then already changed that return undefined to continue. That's what I meant.

The example in the original post works now.

I wonder if it would be a bad practice to use this though. Like, for example, if some piece of code keeps accessing some object by providing the key that it maps to, then this could prevent the GC from collecting the object if it always happens before GC has a chance to run.

Would it be better if the language provided a LossyRef feature that would be like WeakRef, except that deref() would return undefined if the object is no longer reachable (even if not yet collected)?

Seems a feature like that would make code more robust and fail proof.

You probably just want to combine a WeakMap for object key to value and a WeakValueMap for value to object key which needs a finalization registry to clear things. You should never need to iterate over a set, or defer unless you actually mean to access that value. I'll try to write your TwoWayWeakMap a little later.

Alright it ended up being a little trickier than I thought, but here is a TwoWayWeakMap that should be rock solid: TwoWayWeakMap for · GitHub

I switched your keyFrom to a keysFor since there can be multiple values with the same key. Also supports -0, doesn't prevent collection if there are cycles between keys and values, and most importantly, doesn't need to perform any whole map iteration. The only iteration is on keysFrom, and on a set of keys specific to the given value. It's also the only time any WeakRef is dereferenced, so it doesn't hold any objects alive unnecessarily.

1 Like

BTW, your gist will still leak because you still keep a strong reference from the key to the value, just indirectly. Here's a corrected (and cleaner) version, with a bunch of comments explaining why each bit is the way it is. (Note: I've omitted the extras suggested here for better algorithmic clarity, but it's pretty straightforward how to alter it to support those.)

Given how tricky this is to write correctly (you as a delegate making subtle mistakes implementing it is notable) and that there is some existing language precedent for implementing it at the language level (Lua's __mode = "kv" for tables - WeakMap would be __mode = "k", and __mode = "v" makes values weak for context), I feel it's definitely worth looking into as a new feature.

I believe we're solving 2 different problems.

I understood the request as being able to find all the keys of a WeakMap that have a given value, but besides that for the map to still be a regular WeakMap where keys are held weakly, but the value strongly associated to the key. You are implementing a WeakKeyValueMap, where both the key and value are held weakly.

I thought I had a similar Weak key and value map implemented as a gist somewhere but I can't find it right now. It's roughly the same shape as yours, but I allowed the keys to be a primitive as well, so I used a Map instead of a WeakMap for them.

It should be noted that any new collection that holds the value weakly allows to observe the liveness of the value, which is the power granted by WeakRef/FinalizationRegistry and more powerful than WeakMap.

Agreed it's extremely tricky to write those right, and I'm surprised no-one has published various weak collections on npm yet.

I'm used to the following taxonomy:

  • Strong key, strong value = Map
  • Strong key, weak value = what I normally think when hearing weak value map
  • Weak key, strong value = JS's WeakMap
  • Weak key, weak value = my WeakKeyValueMap (what I perceived the proposal to be)

Hope this resolves the communication disconnect.

I stumbled across weak-value - npm when looking for language precedent, and that aligns with my taxonomy as well.

I believe we're on the same page. Sorry I originally mistyped and edited my post immediately. TBH, I don't quite remember the variety of specialized weak collections I've implemented over time, and mangled things at first.

I understood the original request to be for a regular WeakMap, with the addition of a key lookup by value, which is basically a reverse "weak map" from values to the set of corresponding keys. Since "values" can either be objects or primitives, it actuality has both a WeakMap for object values, and a WeakValueMap for primitives values.

There is also @devsnek's GitHub - devsnek/weak-value-map: The WeakValueMap you deserve. In general a WeakValueMap is pretty straight-forward once you remember the trick to use the WeakRef as the unregister token to do the FinalizationRegistry book-keeping.

1 Like

Oh, okay, I see now. And I can't say I'm a fan of mixing weak map types - just seems too unpredictable in practice.

The problem all of the implementations have motivated me to open this issue:

Does my implementation not satisfy your requirements? And if it doesn't, in what way?