Maplike/setlike iterators shouldn't use MapIteratorPrototype/etc

[tabatkins]

#1138 switched maplike/setlike interfaces to use Infra maps/sets, and as part of that had to redefine some text out of the ES spec, notably reusing the language of CreateMapIterator and subbing in a new closure that worked on the infra map/set rather than the ES Map/Set it previously used.

Per discussion with @bakkot and @ljharb, the ES spec doesn't, in fact, intend for this to be pluggable in quite this way; notably, apparently it's bad to create an iterator inheriting from %MapIteratorPrototype% but with a different iteration behavior. (CreateIteratorFromClosure looked pluggable, but in reality the second and third arguments should be unique per call site.)

They suggest instead that I should define a new prototype object, descended from %IteratorPrototype%, and define its methods itself; this is very short and simple to do, as shown in the definition of %MapIteratorPrototype%. (I shouldn't just use %GeneratorPrototype%, like a userland generator, because then I have to worry about .return(), which I don't want to worry about.)

Patch incoming.

[domenic]

-1; reusing %MapIteratorPrototype% and %SetIteratorPrototype% is something all engines do, and something we intentionally designed. ES should allow this kind of layering so that other specs can vend such classes, without having to wrap things up into a [[BackingMap]]/[[BackingSet]].

[bakkot]

If it's intended, that's fine with me. (The behavior in #1138 does work with the ES spec as currently written, though we didn't really intend for it to when we did the refactoring in tc39/ecma262#2045.)

It's conceptually weird to me, and I'm surprised it doesn't cause problems for implementations - I would have expected implementations of MapIteratorPrototype to need to hold an actual ES Map - but I don't think it'll actually matter for users.

Edit: Specifically, the main user-observable consequence of re-using MapIteratorPrototype is that doing (new Map)[Symbol.iterator].next.call(webIdlMapLike[Symbol.iterator]()) will work (and conversely, with new Map and webIdlMapLike switched). This is a little surprising to me as a user, but not a big deal because as a user I will literally never notice that. But I'm not sure that engines will actually want to implement that behavior. If engines are fine with this, I don't see a problem.

[ljharb]

It's perfectly reasonable to ask 262 to provide these affordances for layered specs; that doesn't mean we do at the moment, though.

@domenic are you saying there's existing web iterators where %MapIteratorPrototype%.next.call won't throw?

[bakkot]

reusing %MapIteratorPrototype% and %SetIteratorPrototype% is something all engines do

I couldn't find any examples of this right now, poking around a little, though it's entirely possible I've just missed it. E.g., FontFaceSet is a setlike, but in FF, Chrome, and Safari, document.fonts[Symbol.iterator]().next === (new Set)[Symbol.iterator]().next is false.

[domenic]

Nah I'm saying that there are web iterables that return iterators that are instances of MapIteratorPrototype and vend keys/values based off of a separate internal data store (which the IDL spec used to model as an internal %Map%)

[domenic]

I couldn't find any examples of this right now, poking around a little, though it's entirely possible I've just missed it.

Hmm OK, I thought I tested this a while ago but perhaps not. Well, if all browsers are violating the spec in the same way, then perhaps I need to reconsider my position :). Please hold for more investigation and testing...

[domenic]

This is tricky because there aren't too many maplikes and setlikes in web platform specs and even fewer are implemented widely. Findings so far:

• Firefox uses %MapIteratorPrototype% for AudioParamMap, EventCounts, and RTCPeerStats. It does not use %SetIteratorPrototype% for FontFaceSet.
• Safari uses %MapIteratorPrototype% for RTCPeerStats. It does not use %SetIteratorPrototype% for FontFaceSet.
• Chrome does not use %MapIteratorPrototype% or %SetIteratorPrototype% for any of the above. However, it does use the same iterator prototype object for AudioParamMap, EventCounts, and RTCPeerStats.

Given this total lack of interop we could kind of go in any direction.

My preference would be for the current spec (modulo layering fixes), i.e. use %MapIteratorPrototype% and %SetIteratorPrototype%. That would avoid telling Safari and Firefox, who implemented maplikes "correctly" (i.e. matching the spec), to do something new.

Alternatives include:

• Codify Chrome behavior to avoid (ab)using %MapIteratorPrototype%/%SetIteratorPrototype%.
• Codify Safari/Firefox behavior where %MapIteratorPrototype% is used for maplikes but a new prototype is used for setlikes. Would that setlike prototype be shared between all setlikes, or setlike-specific? It's unclear what each browser implements since they seem to both have only one setlike, but I would lean toward shared if we went this route...

[ljharb]

It seems like the ideal approach is for 262 to provide affordances to make it easy for, eg, AudioParamMap to have its own iterator prototype (rather than weirdly using Map's iterator prototype).

Why would it be desirable to use the iterator prototype that is exclusively intended for Maps with "not Maps"?

[domenic]

Because they're maplike.

[tabatkins]

That last option (using %MapIteratorPrototype% but not %SetIteratorPrototype%) doesn't seem very sensical; it's just specifying bugwards compat, rather than a behavior that actually makes sense.

Why would it be desirable to use the iterator prototype that is exclusively intended for Maps with "not Maps"?

I mean, these are Maps in the important senses; that's the whole point of being maplike. Aside from some internal impl details, authors can treat them exactly like any other map.

[ljharb]

right, but it's not a Maplike Iterator, it's a Map iterator. It's not intended for, designed for, or meant for Map-likes.

[domenic]

Also, please note that you're incorrect in talking about what they were "intended" for; maplikes were co-designed with Maps in the ES2015 timeframe and reusing %MapIteratorPrototype% (and allowing it to be reused on a spec-level, using the [[BackingMap]] strategy) was a conscious design decision of the people involved, including on the ES side.

[ljharb]

@tabatkins a Map is something that has a [[MapData]] slot, that i can Object.getOwnPropertyDescriptor(Map.prototype, 'size').get.call and receive a meaningful answer. If these qualify, then Map's IteratorPrototype makes sense.

@domenic thanks for the correction on the history of it; it seems telling that such a thing hasn't been discussed in committee, and nobody seemed to know about it, when we discussed refactoring these builtins, since at least 2014.

[domenic]

a Map is something that has a [[MapData]] slot, that i can Object.getOwnPropertyDescriptor(Map.prototype, 'size').get.call and receive a meaningful answer.

I know you are very focused on internal slots and brands, but that does not hold for everyone, and it certainly did not hold for the ES2015 editor. At the time TC39/the Web IDL community (mostly on public-script-coord) designed Map as a contract based on a set of public methods, and thought that every class which conformed to those methods had an equal right to vend %MapIteratorPrototype% instances from those methods.

[ljharb]

The committee's makeup has certainly shifted; the impetus seems to currently be towards minimizing observable lookups by this implicit "contract" (which for Map is just "the constructor calls .set", and Set .add, from what I can tell), and moving towards something that exclusively uses brands for the receiver and uses brand + fallback-to-lookup for arguments.

It's unfortunate that WebIDL has designed a bunch of things with an understanding that TC39 seems to not have widely (or at least, overtly) shared for the last half-decade.

[domenic]

None of the alternatives under discussion here call .set etc. on Map instances. We're just discussing whether other specs are allowed to create instances of a type. The answer is clearly yes for various TC39 types such as Promise, Map, etc. And back then the answer was also clearly yes for %MapIteratorPrototype%.

[ljharb]

I understand that. "instances of a type" is determined in ecma-262 pretty much entirely by the presence of internal slots, which are observable for all built-in types except Error, including the iterator prototypes.

[domenic]

I don't really care how you characterize type. I care whether Web IDL can create %MapIteratorPrototype%s like it does %Promise%s. The answer used to be yes.

[ljharb]

Sure - and my comment that you quoted in #1142 (comment) would determine whether that creation was done correctly.

I think the answer is still yes, modulo the internal slots requirement - but it's a different question as to whether it's appropriate versus whether it's allowed (which it is, ofc, allowed).

[tabatkins]

My point of using %MapIteratorPrototype% is just that, if we ever add anything to that proto (some map-specific iteration helpers?) we'd want them to be available for maplikes as well; it also defines the minimal set of methods we need for our purposes (rather than, say, the Generator prototype, which has .return() on it).

The algos involved don't invoke the internal slots at all, except hidden in the closure argument that's constructed and passed to CreateIteratorFromClosure, which is why it seemed appropriate to reuse that algo with a custom closure. Impls might internally implement things more directly, of course, and have their Map .next() method directly access the [[MapData]] rather than using a closure; if that's the case, and it's problematic for us to do a custom closure, then it's fine imo to just switch to a new prototype object defined to inherit from %IteratorPrototype%.

[bakkot]

I don't think any option here is likely to actually affect users in any noticeable way, so I am personally fine with any outcome here.

I do think some choices might affect engines. If WebIDL stuff re-uses MapIteratorPrototype, that means that engines have to either use the same underlying data structure for those things as for Maps, or have to make their implementation of MapIteratorPrototype dispatch for multiple different possible underlying data structures. So maybe that's a reason not to re-use it. But this is pure speculation on my part.

From a theoretical purity perspective, I think the previous WebIDL spec, where there was a [[BackingMap]] which held an actual ES Map which was never exposed to code but which was used to provide iterators, was clearly "acceptable" from the perspective of the ES spec (whatever that means). So it seems to me that an editorial change with no normative implications ought to be acceptable as well (i.e., #1138), if that's what's most convenient for consumers of WebIDL.

---

That said, I do think that anything using MapIteratorPrototype should have observable behavior which is consistent with actual Map iterators, to avoid confusing people, which was trivial when there was a real [[BackingMap]] and now needs to be enforced by review of the actual iteration algorithm and invariants.

[tabatkins]

That said, I do think that anything using MapIteratorPrototype should have observable behavior which is consistent with actual Map iterators, to avoid confusing people, which was trivial when there was a real [[BackingMap]] and now needs to be enforced by review of the actual iteration algorithm and invariants.

To the best of my knowledge, I have maintained consistency with real Map iterators (the details should just be in how Infra specifies maps and sets to be iterated over, which I'm defining to match ES in whatwg/infra#451).

[tabatkins]

Oh also, note:

that means that engines have to either use the same underlying data structure for those things as for Maps,

This would be completely fine, probably ideal in fact. This change was meant to make messing around with the contents of a maplike/setlike actually doable for human spec editors, rather than requiring everyone to know and get perfectly right the precise dance of algos that manipulating ES objects requires. (For example, I was trying to write https://tabatkins.github.io/css-toggle/#dom-csstogglemap-set when I realized it would be really fiddly and annoying to both read and write, which caused me to come shave this yak first; with the new IDL stuff, the algorithm was very easy to write and is easy to understand for the reader.)

[bakkot]

To the best of my knowledge, I have maintained consistency with real Map iterators

Yeah I think you're fine currently. The main details to worry about are iteration order and coercing -0 to 0 in keys. (Infra just says "no key appearing twice", so the second thing will be a problem if there is ever a maplike or setlike which allows numbers as keys.)

that means that engines have to either use the same underlying data structure for those things as for Maps,

This would be completely fine, probably ideal in fact. This change was meant to make messing around with the contents of a maplike/setlike actually doable for human spec editors, rather than requiring everyone to know and get perfectly right the precise dance of algos that manipulating ES objects requires.

To be clear, by "underlying data structure", I mean the actual C++ object which backs the thing, not the spec-level thing used to talk about it in algorithms.

My thinking is that WebIDL maplikes specify types more narrowly than ES Maps do, which might lead to wanting a different backing store. This is particularly relevant if there's ever a maplike which has only a small number of possible keys, which is a place where you'd really want to back it by something other than a hashmap.

But maybe this won't actually come up in practice. This is pure speculation on my part; I wanted to make sure the possible downside is recognized but I don't have any idea how likely or important it actually is.

[tabatkins]

The main details to worry about are iteration order

As we discovered, I didn't get this right; using holes (as the ES spec does) gives an observably different behavior than not doing so (as Infra currently does): if a collection is mid-iteration, and something is removed from the beginning, using holes means you'll still visit every subsequent item; not using holes means you'll "skip ahead" over one item, since they all have their indexes shifted down by one. This'll need fixing.

coercing -0 to 0 in keys

The default impl of the mutation methods do this, and I already have requirements on what the mutation methods have to return; adding a SHOULD requirement to coerce -0 to 0 is reasonable to add as well. Will fix.

My thinking is that WebIDL maplikes specify types more narrowly than ES Maps do, which might lead to wanting a different backing store. This is particularly relevant if there's ever a maplike which has only a small number of possible keys, which is a place where you'd really want to back it by something other than a hashmap.

Talking to our engineers at Chrome, it seems that our current maplike/setlike impls are all doing disparate things anyway, not sharing significant code with the ES Maps and Sets. So afaict this shouldn't be a big issue for Chrome, at least; we'll just continue using distinct code that's written to intentionally match Maps/Sets in behavior but without expectation of code-sharing.

[bakkot]

So afaict this shouldn't be a big issue for Chrome, at least; we'll just continue using distinct code that's written to intentionally match Maps/Sets in behavior but without expectation of code-sharing.

That's actually my concern: the problem is that re-using MapIteratorPrototype means that the implementation of MapIteratorPrototype.next must be polymorphic across actual backing Maps and also all of the various maplikes. (In practice it's probably just a dispatch at the start of the implementation, which is not free, but maybe is cheap enough not to worry about?) If you used a custom prototype, each implementation could be specialized to the kind of thing which actually backs it, rather than needing to dispatch.

[petervanderbeken]

* Firefox uses %MapIteratorPrototype% for `AudioParamMap`, `EventCounts`, and `RTCPeerStats`. It does _not_ use %SetIteratorPrototype% for `FontFaceSet`.

Firefox does use %SetIteratorPrototype% for setlikes, FontFaceSet is not marked as setlike in our WebIDL which is a known bug (https://bugzilla.mozilla.org/show_bug.cgi?id=1311198). WebGPU's GPUSupportedFeatures is behind a pref (dom.webgpu.enabled), but if it's enabled then await navigator.gpu.requestAdapter().then((a) => a.features[Symbol.iterator]().next) == (new Set)[Symbol.iterator]().next returns true for me.