Correctly handle Array unshift/splices that move elements past the max length of an Array

Correctly handle Array unshift/splices that move elements past the max length of an Array

BUG=v8:2615
LOG=n
R=verwaest@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=25270

[adamk, 2014-10-27 14:20:47]

adamk@chromium.org changed reviewers:
+ mstarzinger@chromium.org

[adamk, 2014-10-27 14:20:47]

Feel free to tell me this SparseMove() is getting too hacky. This is mostly an
attempt to see what it would take to be spec-compliant.

[adamk, 2014-10-29 10:33:33]

adamk@chromium.org changed reviewers:
+ verwaest@chromium.org

[adamk, 2014-10-29 10:33:34]

friendly ping? curious for thoughts on this approach.

[Toon Verwaest, 2014-11-04 09:30:33]

lgtm

Alternatively you could precalculate at which limit you'll overflow index-range,
and just have 2 loops. That would be a bit less costly, and rely less on
internal arrays behaving correctly.

[adamk, 2014-11-04 16:02:42]

On 2014/11/04 at 09:30:33, verwaest wrote:
> lgtm
> 
> Alternatively you could precalculate at which limit you'll overflow
index-range, and just have 2 loops. That would be a bit less costly, and rely
less on internal arrays behaving correctly.

Hmm, yes, that makes more sense, especially since I'd like to see less
InternalArray usage, not more (the behavior of %MoveArrayContents being exposed
in this function is not ideal).  Will give that a shot when I get a chance
(likely post-BlinkOn).

[Toon Verwaest, 2014-11-05 11:58:57]

sgtm

[adamk, 2014-11-10 18:32:45]

On 2014/11/04 09:30:33, Toon Verwaest wrote:
> lgtm
> 
> Alternatively you could precalculate at which limit you'll overflow
index-range,
> and just have 2 loops. That would be a bit less costly, and rely less on
> internal arrays behaving correctly.

Okay, dug out from the whirlwind of BlinkOn, and now I'm not sure what you're
asking for. Are you suggesting to simply break when we hit the first key that's
>= 2^32 and then continue the loop after that? I think that'll require
pre-sorting the array keys, which we're not doing now, but we do that in most
other places so it'd probably be fine. Or did you have something else in mind?

[Toon Verwaest, 2014-11-11 13:22:21]

You are right, you'd need to presort... Not sure if that's better.

https://codereview.chromium.org/679113003/diff/1/src/array.js
File src/array.js (right):

https://codereview.chromium.org/679113003/diff/1/src/array.js#newcode275
src/array.js:275: if (new_key > 0xffffffff) {
Shouldn't this be >=?

NOTE A String property name P is an array index if and only if
ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 2^
32-1.

[adamk, 2014-11-11 18:01:01]

https://codereview.chromium.org/679113003/diff/1/src/array.js
File src/array.js (right):

https://codereview.chromium.org/679113003/diff/1/src/array.js#newcode275
src/array.js:275: if (new_key > 0xffffffff) {
On 2014/11/11 13:22:21, Toon Verwaest wrote:
> Shouldn't this be >=?
> 
> NOTE A String property name P is an array index if and only if
> ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 2^
> 32-1.

This is a weird corner-case in V8: indexed property 0xffffffff is stored in the
elements backing store, despite not being a valid array index. I guess I could
make it >=, but it's well covered by the tests in case we change elements
implementation.

[adamk, 2014-11-11 19:02:43]

Landing unmodified since it's not clear that sorting is advantageous here. Once
tests are passing should be easy to change in future as desired.

[adamk, 2014-11-11 19:08:35]

Committed patchset #1 (id:1) manually as 25270 (presubmit successful).