W3C home > Mailing lists > Public > public-script-coord@w3.org > July to September 2013

Unordered setsmaps, for when ordering is hard/expensive/unwanted?

From: Tab Atkins Jr. <jackalmage@gmail.com>
Date: Fri, 30 Aug 2013 16:34:22 -0700
Message-ID: <CAAWBYDDrithcJ58Fv+2yV0bLq6LDeaq7KU6M1PEim9WAzMAyPw@mail.gmail.com>
To: "public-script-coord@w3.org" <public-script-coord@w3.org>
Plain JS Sets and Maps are intrinsically ordered - they remember the
order that things were added to them, and reflect that when you
iterate over them.

When returning a SetMap (or [SetClass]/[MapClass] interface),
"insertion order" doesn't always make sense, but often there is still
some reasonable ordering.  For example, when a CSSStyleDeclaration
(which is defined with named getters rather than [MapClass] for legacy
reasons, but the point stands) is returned from getComputedStyle, it
defines the iteration order of its properties to be alphabetical.

This is easy to do with CSSStyleDeclaration, because its keys are all
ASCII (CSS properties are by convention restricted to the ASCII
range).  However, CSSVariablesMap can also be returned by
getComputedStyle (as the value of the "var" property on
CSSStyleDeclaration), and its keys are arbitrary unicode characters.
This *can* be sorted, but one of the reasons we made some of the
choices we did with CSS Variables was specifically to avoid dealing
with collation/etc issues.

So, ideally, CSSVariablesMap could be defined in this case to return
"unordered" keys.  Of course, that's not actually doable right now,
because that just implies "implemented-defined order", which means we
end up defining one of the impl-orders as the definitive order in a
few years anyway.

(I have other use-cases for unordered sets - I'm playing around with
the Font Load Events API right now, and want to expose a Set of all
the fonts available to the window/worker. These come both from CSS and
from explicit author action, and both sources can add and remove
things at arbitrary points in the document lifecycle.  I'd rather not
have to define and expose an ordering for this.)

I know this idea was tossed around earlier in the development of Maps
and Sets.  For example, one way to have unordered Maps/Sets would be
to randomly order the keys whenever you iterate.  I think that was
rejected as an unnecessarily large expenditure of entropy and time.

The Go language, on the other hand, gets nearly the same benefit out
of its "unordered" maps/sets by declaring that the iteration is in a
stable, implemention-defined order, but every time you iterate you
start from a random index (looping around when you reach the end).
This prevents authors from accidentally depending on starting at a
particular index, and while they *can* still accidentally depend on
"nearby" things remaining near each other (the assumption will only
fail when the starting index falls between them), that seems like a
much less likely source of fragility.

Would it be appropriate to define what Go does, and use it in IDL for
Maps/Sets that we don't want to define an ordering for?  Is it
something that JS would want to take up natively?

~TJ
Received on Friday, 30 August 2013 23:35:09 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:37:50 UTC