690622 - JSObject::moveDenseArrayElements doesn't get along well with holes

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Jeff Walden [:Waldo]]

js> var arr = [0, 1, 2, 3, 4, , 6];
js> for (var p in arr) {
  print(p);
  if (p === "1")
    arr.shift();
}
0
1
2
3
4
js> arr
[1, 2, 3, 4, , 6]

Quoth ES5:

"If a property that has not yet been visited during enumeration is deleted, then it will not be visited."

The shift call, in shifting elements toward zero by one, will delete index 4 (see the hole in |arr| above).  This happens before index 4 is enumerated.  Therefore, 4 should not be printed here.  But it is, because we're not suppressing deleted properties because the deletion is implicit in the moveDenseArrayElements memmove.

It seems to me that fundamentally, moveDenseArrayElements is unsound with respect to non-packed arrays, unless the caller actually goes through the moved elements afterward and suppresses any deleted elements.  No caller (shift, unshift, splice) does this now.  I'll probably end up making sure splice handles this properly in bug 668024.  But the other two will need some sort of changing.  And perhaps this just demonstrates that moveDenseArrayElements is an unwise idea, or that it should assert that it's being used on a packed array.  Thoughts people have on this mess, and what to do about it, are appreciated.

For what it's worth, none of Opera, Safari, Chrome, or IE have this bug, at least as far as the above testcase is concerned -- none print 4.  (They don't all agree on printing 5, but ES5 permits either behavior there, so that's not a bug.)

Comment 1

[Jeff Walden [:Waldo]]

It turns out type inference adds a useful frob to check whether an object (or rather, all objects with a given latent type) is being enumerated.  arr->getType(cx)->hasAllFlags(OBJECT_FLAG_ITERATED)) should give the info necessary to de-optimize away from moveDenseStuff in those cases.  (The flag is set regardless whether type inference is enabled or not.)  This trick is used in bug 694210 to make splice deletion-safe with respect to moveDenseStuff.

So with that, this becomes reasonably tractable without having to add a loop checking for holes or anything -- just check for enumeration, and if so fall back to the really slow path, not just to a slightly-less-fast path.

Comment 2

[André Bargull [:anba]]

Resolving as WFM:

js> var arr = [0, 1, 2, 3, 4, , 6];
js> for (var p in arr) {
  print(p);
  if (p === "1")
    arr.shift();
}
0
1
2
3
js> arr
[1, 2, 3, 4, , 6]