924058 - Array operations should use ToLength on user-supplied indices, not ToUint32

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andy Wingo [:wingo]]

The current ES6 drafts use a "ToLength" operator for turning a user-supplied value into an array index.  See: http://people.mozilla.org/~jorendorff/es6-draft.html#sec-tolength

This operator results in an integer between 0 and 2**53-1, inclusive.

SM should change instances of TO_UINT32 / ToUint32 in Array runtime procedures to use ToLength.

See also bug 728578 for an earlier discussion.

Comment 1

[Luke Wagner [:luke]]

Related (but, iiuc, different, since it concerns typed array indexing, which doesn't use ToLength) is bug 907874.

Comment 4

[Tom S [:evilpie]]

There are various test262 tests that hang because we get huge numbers by using ToUint32, fixing this would be useful to make the web runner work: https://bakkot.github.io/test262-web-runner/.

Comment 5

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=160cf98596819f4c5872a06155d5318dddf96e11

Comment 6

[André Bargull [:anba]]

Test262 PR: https://github.com/tc39/test262/pull/1028

Comment 7

[André Bargull [:anba]]

Attachment: bug924058-part1-double-to-uint64.patch

Part 1:
- Changes variable type for large indices from double to uint64_t
- And adds assertions to check large index/length values are always below 2^53

Comment 8

[André Bargull [:anba]]

Attachment: bug924058-part2-uint64-helper-methods.patch

Part 2:
- Adds ToLength and GetLengthProperty variations for uint64 length values
- Adds new property helper methods for uint64 indices
- As part of bug 1123059, we may need to make some of these methods available outside of jsarray.cpp. 
- Uses explicit namespace qualifier for some method calls to ensure these calls won't use the new uint64 methods
- And simplifies SetArrayElements because both loops were actually doing the same work (there used to be a difference, but it was removed in bug 1282104).

Comment 9

[André Bargull [:anba]]

Attachment: bug924058-part3-simple-array-methods.patch

Part 3:
- Changes the majority of Array.prototype methods to use uint64 indices, Array.p.slice (part 4) and Array.p.splice (part 5) are updated separately. It's hard to test some of these changes, because iterating from 0 to a value greater than 2^32 takes some time ;-). Which means we could also stick with the uint32 version for some of these methods (e.g. Array.p.toSource and Array.p.join), because the difference isn't observable until we have a faster way to iterate over sparse arrays.

Array.p.reverse, .push, .unshift:
- Only take the fast path when the length is a uint32 value
- I'm using explicit casts here (and in the next patches) to emphasise when a value fits into uint32. Do you think it's worthwhile to have these explicit casts or should I use implicit conversions instead? Or do you think it's even better to have AssertedCasts instead of just C++ casts?

Array.p.shift, .join:
- Alternatively we could make shift/join only take the fast path when the length is a uint32 value, similar to the other methods.

Array.p.sort:
- This is where I wondered if it makes sense to only eagerly allocate the complete temporary array when the length has a reasonable value. For example |Array.prototype.sort.call({get 0() { throw "Getter called" }, length: 0xffffffff})| directly throws an OOM error in SpiderMonkey, whereas |Array.prototype.sort.call({get 0() { throw "Getter called" }, length: 0xffffffff}, function(){})| throws the string "Getter called".

Comment 10

[André Bargull [:anba]]

Attachment: bug924058-part4-slice.patch

Part 4:
- The sparse indices and js::GetElementsOp fast paths only work with uint32 length values, I'm not sure there's currently any need to update them to handle uint64 indices.
- Renamed "count" to "newlength" in ArraySliceOrdinary to avoid confusion with "count" from array_slice.
- Updated variable names in ArraySliceDenseKernel to match ArraySliceOrdinary

Comment 11

[André Bargull [:anba]]

Attachment: bug924058-part5-splice.patch

Part 5:
- Slightly more complicated than the rest, but I've added extra assertions before casting values to uint32, so it's easier to see why these casts are valid
- And I've changed some range tests to use the more natural |x + y < limit| form, because now that we're using uint64, we no longer need to watch out for uint32 overflows.

Comment 12

[André Bargull [:anba]]

Attachment: bug924058-part6-update-tests.patch

More test coverage was added to test262 today (https://github.com/tc39/test262/pull/1028).

Comment 13

[Jan de Mooij [:jandem]]

Comment on attachment 8866466 [details] [diff] [review]
bug924058-part2-uint64-helper-methods.patch

Review of attachment 8866466 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsarray.cpp
@@ +3258,5 @@
>      }
>  
>      // Step 8.
>      for (unsigned k = 0; k < args.length(); k++) {
> +        if (!js::DefineElement(cx, obj, k, args[k]))

I assume this is temporary? If we will still have different overloads for uint32_t vs uint64_t, we should consider either removing the uint32_t ones or making this strongly typed (different structs wrapping uint32_t or uint64_t, or something).

Comment 14

[Jan de Mooij [:jandem]]

Comment on attachment 8866467 [details] [diff] [review]
bug924058-part3-simple-array-methods.patch

Review of attachment 8866467 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsarray.cpp
@@ +2438,5 @@
>      if (result != DenseElementResult::Incomplete) {
>          if (result == DenseElementResult::Failure)
>              return false;
>  
> +        if (len <= UINT32_MAX)

I think it would be easier to reason about this (especially the startIndex below) if we moved this check before the fast path.

@@ +2454,3 @@
>      // Steps 5-6.
>      RootedValue value(cx);
> +    for (uint32_t i = startIndex; i < newlen; i++) {

Shouldn't this be uint64_t?

Comment 15

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #13)
> ::: js/src/jsarray.cpp
> @@ +3258,5 @@
> >      }
> >  
> >      // Step 8.
> >      for (unsigned k = 0; k < args.length(); k++) {
> > +        if (!js::DefineElement(cx, obj, k, args[k]))
> 
> I assume this is temporary? If we will still have different overloads for
> uint32_t vs uint64_t, we should consider either removing the uint32_t ones
> or making this strongly typed (different structs wrapping uint32_t or
> uint64_t, or something).

As part of bug 1123059 resp. after bug 1123059, we should have a clearer view which overloads are necessary. Until then I'm inclined to punt on this question. :-)
But what I probably should have done here, is to name these methods differently compared to the existing uint32 elements-methods from jsobj.h. For example, "GetArrayElement" instead of "GetElement", similar to the existing "DeleteArrayElement" method in jsarray.cpp.

Comment 16

[Jan de Mooij [:jandem]]

Comment on attachment 8866468 [details] [diff] [review]
bug924058-part4-slice.patch

Review of attachment 8866468 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsarray.cpp
@@ +1062,2 @@
>  {
> +    MOZ_ASSERT(length < DOUBLE_INTEGRAL_PRECISION_LIMIT);

I wonder if it would make sense to have a class wrapping an uint64_t length and with range assertions in its constructor. Maybe overkill?

Comment 17

[Jan de Mooij [:jandem]]

(In reply to André Bargull from comment #15)
> But what I probably should have done here, is to name these methods
> differently compared to the existing uint32 elements-methods from jsobj.h.
> For example, "GetArrayElement" instead of "GetElement", similar to the
> existing "DeleteArrayElement" method in jsarray.cpp.

Yeah I think a different name would be good to avoid confusion. Not sure about *ArrayElement because these methods can also be called on non-array objects?

Comment 18

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #14)
> Comment on attachment 8866467 [details] [diff] [review]
> bug924058-part3-simple-array-methods.patch
> 
> Review of attachment 8866467 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jsarray.cpp
> @@ +2438,5 @@
> >      if (result != DenseElementResult::Incomplete) {
> >          if (result == DenseElementResult::Failure)
> >              return false;
> >  
> > +        if (len <= UINT32_MAX)
> 
> I think it would be easier to reason about this (especially the startIndex
> below) if we moved this check before the fast path.

Can you elaborate? This check was intended for the case when an object has dense elements, but also properties larger than uint32. So we can move the dense elements through the fast path and only use the slow path for the remaining properties (which are all larger or equal to UINT32_MAX). 


> @@ +2454,3 @@
> >      // Steps 5-6.
> >      RootedValue value(cx);
> > +    for (uint32_t i = startIndex; i < newlen; i++) {
> 
> Shouldn't this be uint64_t?

Oops, yes. Seems like I messed this up while rebasing the patches...

Comment 19

[Jan de Mooij [:jandem]]

Comment on attachment 8866470 [details] [diff] [review]
bug924058-part6-update-tests.patch

Review of attachment 8866470 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for fixing this!

Unfortunately these changes are hard to review due to C++'s implicit conversions but the asserts help.

Comment 20

[Jan de Mooij [:jandem]]

(In reply to André Bargull from comment #18)
> Can you elaborate? This check was intended for the case when an object has
> dense elements, but also properties larger than uint32. So we can move the
> dense elements through the fast path and only use the slow path for the
> remaining properties (which are all larger or equal to UINT32_MAX). 

I thought ArrayShiftDenseKernel would fail the ObjectMayHaveExtraIndexedProperties check in that case, but I guess that's not necessarily true because IdIsIndex checks for uint32? Not sure how much we care about perf in that case but keeping it like this is fine with me.

Comment 21

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #16)
> Comment on attachment 8866468 [details] [diff] [review]
> bug924058-part4-slice.patch
> 
> Review of attachment 8866468 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jsarray.cpp
> @@ +1062,2 @@
> >  {
> > +    MOZ_ASSERT(length < DOUBLE_INTEGRAL_PRECISION_LIMIT);
> 
> I wonder if it would make sense to have a class wrapping an uint64_t length
> and with range assertions in its constructor. Maybe overkill?

Waldo would know... :-)

It may make sense to have such a class if we need to support properties larger than uint32 for the jsobj.h property methods.

Comment 22

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #20)
> (In reply to André Bargull from comment #18)
> > Can you elaborate? This check was intended for the case when an object has
> > dense elements, but also properties larger than uint32. So we can move the
> > dense elements through the fast path and only use the slow path for the
> > remaining properties (which are all larger or equal to UINT32_MAX). 
> 
> I thought ArrayShiftDenseKernel would fail the
> ObjectMayHaveExtraIndexedProperties check in that case, but I guess that's
> not necessarily true because IdIsIndex checks for uint32? Not sure how much
> we care about perf in that case but keeping it like this is fine with me.

Yes, ObjectMayHaveExtraIndexedProperties ignores integer indexed properties which don't fit in uint32.

Comment 23

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #17)
> (In reply to André Bargull from comment #15)
> > But what I probably should have done here, is to name these methods
> > differently compared to the existing uint32 elements-methods from jsobj.h.
> > For example, "GetArrayElement" instead of "GetElement", similar to the
> > existing "DeleteArrayElement" method in jsarray.cpp.
> 
> Yeah I think a different name would be good to avoid confusion. Not sure
> about *ArrayElement because these methods can also be called on non-array
> objects?

I think that's okay given that we already have DeleteArrayElement and SetArrayElements in jsarray.cpp.

(And yes, I know this contradicts my previous stance on this topic, because in bug 1282104, comment #5 I argued "SetArrayElement" should be renamed to "SetElement", because it's not exclusively used for arrays. :-P

Comment 24

[André Bargull [:anba]]

Attachment: bug924058-part2-uint64-helper-methods.patch

Renamed new property methods, so the names don't clash with standard property access methods from jsobj.h. Carrying r+.

Comment 25

[André Bargull [:anba]]

Attachment: bug924058-part3-simple-array-methods.patch

Fixed variable type in array_shift per review comments, carrying r+.

Comment 26

[André Bargull [:anba]]

Attachment: bug924058-part4-slice.patch

Rebased because of changes in part 2. Carrying r+ from jandem.

Comment 27

[André Bargull [:anba]]

Attachment: bug924058-part5-splice.patch

Rebased because of changes in part 2. Carrying r+ from jandem.

Comment 28

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=d6ca56cb23d7977bd28625df91f87be0da1218d6

Comment 29

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/265b3a6f27a7
Part 1: Use uint64 instead of double for large indices in Array.prototype methods. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/1aa3b4f1aa1e
Part 2: Add new property operations to work on uint64 indices. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/d9a1f30a0ee8
Part 3: Update simple methods to use uint64 length values. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/a6a090302760
Part 4: Update Array.prototype.slice to use uint64 length values. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/16c5e2352f82
Part 5: Update Array.prototype.splice to use uint64 length values. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/46090ca17d69
Part 6: Update test cases to expect ToLength conversion in array methods. r=jandem

Comment 30

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/265b3a6f27a7
https://hg.mozilla.org/mozilla-central/rev/1aa3b4f1aa1e
https://hg.mozilla.org/mozilla-central/rev/d9a1f30a0ee8
https://hg.mozilla.org/mozilla-central/rev/a6a090302760
https://hg.mozilla.org/mozilla-central/rev/16c5e2352f82
https://hg.mozilla.org/mozilla-central/rev/46090ca17d69