Atomic map operators

💡 Ideas
1

Map is a great data structure because it has a strong conceptual base. Maps and Sets have clear mathematical theory to them, and languages work well when the theories are verifiable.

Unfortunately theoretically-correct usage of the Map API requires that you distinguish between a key not being set in a Map and a key having a value of undefined. Right now the best way to represent this is:

const none = Symbol();
const value = myMap.has(key) ? myMap.get(key) : none;

Now any subsequent code can both see the value myMap contained, and it will also be absolutely clear if the map contained undefined or if key was absent. This is great. We get our theoretical guarantees! Right?

Unfortunately we gave up a lot of other guarantees to get this safety!! **There is no guarantee that myMap still contains key on the second call. In fact, a defensive programmer (or a powerful tool) must assume that myMap has mutated. This can happen one of two ways:

  • Due to a true race condition. These are still possible in web Javascript, particulary due to the existence of legacy semantics like:
    <a onClick="javascript:global.myMap.set('key', undefined)" />
  • When myMap is a subclass of Map

So in essence we have a great benefit of theoretical clarity, but nobody who wants theoretical clarity can claim it, because all those people use type systems which can't understand what is theoretically happening.

The idea is to add atomic operators that can be used like myMap.getOr(key, none).

Typescript and Flow both allow you to represent the safety of this basically the same way:

Map<K, V> {
  getOr<T> (key: K, notDefinedValue: T): V | T;
}
2

Related thread: {Map, WeakMap, etc}.prototype.getRef(key)

3

Could you explain this? JavaScript has run to completion semantics, code can't be preempted unless it explicitly yields.

An onClick handler will add the task to the queue and run when the current stack is empty.

4

Perhaps it's an old superstition I've just never gotten rid of. I recall the original on* attribute semantics were a bit gnarly compared to addEventListener. Most likely I'm remembering some awful thing IE did that was wrong.

1 Like
5

See https://github.com/tc39/proposal-upsert

6

Yeah, as far as I'm aware that's not a thing today. Can't speak to the bad old days, but it's not something you should be worrying about right now. Lots of stuff in the language assumes run-to-completion semantics, i.e. no races.

1 Like
7

Regardless myMap.has(key) ? myMap.get(key) : none still isn't sufficiently safe or static. Class extension can break it. Typescript can't handle it. Flow can't handle it

The proposed myMap.getRef does not solve the problem at all. You can't have a reference to something that doesn't exist (I presume) so you still need to use has to be safe.

8

emplace is funky and I'm not sure I think it's sufficiently low-level to belong in as crucial an API as Map, but unfortunately the one case it doesn't solve is the most important one: has/get.

9

You can use getRef() to get a reference to a value that doesn't exist - it enables you to assign to the ref to create a new value in the map. This, however, still doesn't really solve your use-case, as <ref>.value gives back undefined if it's not in the map, which is indistinguishable from an undefined value actually being present in the map.

So, I can see value in having a getOr() function like this. In Python, they make their .get() function simply take a second optional argument that contains the fallback value, which would be another possible way to go.

10

It seems like the return value of getRef could be defined in such a way as to include the information as to whether the value was present in the map though.

11

This is true, and in fact, I did mention in that proposal that the ref object could have an exists() function. But, using that function for your use case would still be about as tedious:

const none = Symbol();
const ref = myMap.getRef(key);
const value = ref.exists() ? ref.value : none;

Though, perhaps it depends on what you are wanting to do with that value variable after you have it. If the very next thing is to check if value is equal to the none symbol, then do x, otherwise do y, then it could be easier to skip having that value variable and just use the ref variable for everything.

I'm sure Typescript would still struggle with these ref objects.

12

Yeah I guess it's not really any better is it. I was thinking it would still have some of the atomicity benefits, but not really (since the ref's content is mutable)

13

Re. race conditions, some DOM events are synchronous, and can lead to surprises, like here (imagine the b.focus() call is nested in a helper function and not apparent at a glance).

Still, this is unlikely to happen between map.has(x) and map.get(x). If you derive a custom Map implementation whose has() method meddles with DOM events (or mutates anything, really), you deserve all the race conditions in the world, and then some...