Sets don't always preserve insertion order

[ndhoule]

Per my reading of the current spec, sets should should preserve order of insertion. Most other implementations I've checked (Traceur, Firefox, Chrome Canary) do respect insertion order, but es6-shim's don't.

Repro case in Chrome 37.0.2062.124:

// Works as expected
var s1 = new Set(['d', 'a', 'b']);
Array.from(s1); //=> ['d', 'a', 'b']

// Breaks in most browsers due to no object insertion order guarantees
var s2 = new Set([3, 2, 'z', 'a', 1]);
Array.from(s2); //=> [1, 2, 3, 'z', 'a']

// Works as expected, since a non-string/number immediately triggers Map creation
var s3 = new Set([3, 2, 'z', {}, 'a', 1]);
Array.from(s3); //=> [3, 2, 'z', {}, 'a', 1]

(I'm using Array.from here for brevity, but also used the set's #forEach method with the same results.)

Seems like the root cause of this is the lazy initialization of Map; most browsers preserve object insertion order when it comes to alpha characters, but order numerics at the beginning of iteration order. So any case where numeric elements are involved discards insertion order.

I don't see any good/clean way of getting around this short of skipping the lazy initialization and just creating a Map in the first place. Thoughts on that? Happy to submit a fix and tests.

[cscott]

You can do the lazy initialization as soon as a numeric key is inserted, which should solve this problem. Use the existing pattern where we do lazy init in Map for non-string/number keys.

[ljharb]

Rather than remove the fast path for numbers, I think it might make more sense to retain an extra ordering array prior to the Map being initialized. I'll look into both approaches.

[ndhoule]

Cool, makes sense. I started on tests (#291) and looking at this, but sounds like @ljharb is on it.

Thanks!

[ljharb]

Awesome, that saves me writing a failing test :-) i'll cherry-pick that into my branch.

[cscott]

The extra ordering array will be very slow if keys are removed. So as long as there are no numeric keys you want to try to avoid maintaining that extra array, in order to keep deletes fast.

[ljharb]

It would have to do an indexOf and a splice - would that really be that slow?

Another alternative would be to continue to just use the storage map, but instead of storing true, store the numeric index of the ordering, and then use that when converting to a Map. Thoughts on that approach?

[ljharb]

OK, here's the two approaches I've got so far:

• https://github.com/ljharb/es6-shim/commit/2d1ee2e0597fb6e54ae667058e989dbef4881d01 uses a companion array to store keys in order. The cost here is extra storage, plus a splice + indexOf in the "remove" case.
• https://github.com/ljharb/es6-shim/commit/55ce9708e1d8db101a035fce4c71d771a6e1acde stores an incrementing counter rather than true. The cost here is a sort on conversion to a full Map, and storage of a potentially large quantity of integers.

I'm leaning towards the second approach but I wanted to get some others' thoughts first. In either case, they make tests pass :-)

[cscott]

@ljharb PR #292 is my preferred approach. Use the existing 'fastkey' method to either replace numeric keys with strings, or else punt and fall back to the slow path (by returning null from fastkey). I added some feature checking to ensure we do the right thing if the engine either doesn't preserve property order at all, or only preserves order on string keys.