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

RESOLVED FIXED in Firefox 55

Status

()

defect
RESOLVED FIXED
6 years ago
2 years ago

People

(Reporter: wingo, Assigned: anba)

Tracking

(Blocks 3 bugs, {meta})

unspecified
mozilla55
x86_64
Linux
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(6 attachments, 4 obsolete attachments)

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.
Related (but, iiuc, different, since it concerns typed array indexing, which doesn't use ToLength) is bug 907874.
Depends on: 1040196
Depends on: 1063993
Keywords: meta
Depends on: 1064000
Blocks: es6
Blocks: 1123059
Duplicate of this bug: 728578
See Also: → 1205616
Duplicate of this bug: 1064000
No longer blocks: 1124857
Depends on: 1124857
Blocks: test262
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/.
Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=160cf98596819f4c5872a06155d5318dddf96e11
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
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
Attachment #8866465 - Flags: review?(jdemooij)
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).
Attachment #8866466 - Flags: review?(jdemooij)
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".
Attachment #8866467 - Flags: review?(jdemooij)
Posted patch bug924058-part4-slice.patch (obsolete) — Splinter Review
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
Attachment #8866468 - Flags: review?(jdemooij)
Posted patch bug924058-part5-splice.patch (obsolete) — Splinter Review
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.
Attachment #8866469 - Flags: review?(jdemooij)
More test coverage was added to test262 today (https://github.com/tc39/test262/pull/1028).
Attachment #8866470 - Flags: review?(jdemooij)
Attachment #8866465 - Flags: review?(jdemooij) → review+
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).
Attachment #8866466 - Flags: review?(jdemooij) → review+
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?
Attachment #8866467 - Flags: review?(jdemooij) → review+
(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 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?
Attachment #8866468 - Flags: review?(jdemooij) → review+
(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?
Attachment #8866469 - Flags: review?(jdemooij) → review+
(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 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.
Attachment #8866470 - Flags: review?(jdemooij) → review+
(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.
(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.
(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.
(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
Renamed new property methods, so the names don't clash with standard property access methods from jsobj.h. Carrying r+.
Attachment #8866466 - Attachment is obsolete: true
Attachment #8866802 - Flags: review+
Fixed variable type in array_shift per review comments, carrying r+.
Attachment #8866467 - Attachment is obsolete: true
Attachment #8866803 - Flags: review+
Rebased because of changes in part 2. Carrying r+ from jandem.
Attachment #8866468 - Attachment is obsolete: true
Attachment #8866804 - Flags: review+
Rebased because of changes in part 2. Carrying r+ from jandem.
Attachment #8866469 - Attachment is obsolete: true
Attachment #8866805 - Flags: review+
Pushed by ryanvm@gmail.com:
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
Keywords: checkin-needed
Duplicate of this bug: 551060
You need to log in before you can comment on or make changes to this bug.