Closed Bug 1259600 Opened 8 years ago Closed 8 years ago

Array.prototype.sort doesn't work with Int32Array

Categories

(Core :: JavaScript: Standard Library, defect)

48 Branch
defect
Not set
normal

Tracking

()

VERIFIED FIXED
mozilla48
Tracking Status
firefox46 + verified
firefox47 + verified
firefox48 + verified

People

(Reporter: igor, Assigned: till)

References

Details

(Keywords: regression)

Attachments

(2 files, 2 obsolete files)

User Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.87 Safari/537.36

Steps to reproduce:

Run next script (broken only on Nightly build - 48 2016/03/24, works normal on last Stable - 45.0.1):
var q = new Int32Array([1, 2, 3]);
Array.prototype.sort.call(q, function (a,b) {return a<b ? 1 : (a==b ? 0 : -1);});


Actual results:

Exception with next details:
TypeError: can't redefine non-configurable property 0


Expected results:

Should work and sort array descending.
Component: Untriaged → JavaScript Engine
Product: Firefox → Core
This is fallout from the holes-handling in the new self-hosted implementation from bug 715181. I *think* this is the right approach to fixing it, but you might have a better idea.

Regardless of which exact approach we end up taking, we should uplift this to Beta if we can: we didn't have any sort method available on typed arrays until recently, so this is going to blow up somewhat frequently.
Attachment #8734705 - Flags: review?(winter2718)
Assignee: nobody → till
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Blocks: 715181
Component: JavaScript Engine → JavaScript: Standard Library
Comment on attachment 8734705 [details] [diff] [review]
Make Array#sort work on typed arrays again

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

::: js/src/builtin/Sorting.js
@@ +238,5 @@
>      // then create holes at the end.
>      var denseList = new List();
>      var denseLen = 0;
>  
> +    var isPacked = IsPackedArray(array) || IsPossiblyWrappedTypedArray(array);

I like this solution, but tests (ecma_6/Array/sort*) are failing once I apply the patch. Will investigate further.
Attachment #8734705 - Flags: review?(winter2718)
The problem here is that it's doing a lexicographical sort. It never even touches the JS merge sort. We'll need to modify the c++ code that decides which sort to run.
*coughs* I'm dead wrong. I went through the trouble of writing a little test and did Array.prototype.sort.apply without wrapping the comparator in an array. x(
Attached patch typedarraysort.diff (obsolete) — Splinter Review
So, what about just diverting typed arrays to TypedArraySort? It's already optimized for dealing with each genre of typed array.
Attachment #8734993 - Flags: review?(till)
Attached patch typedarraysort.diff (obsolete) — Splinter Review
My brain isn't working well today.
Attachment #8734993 - Attachment is obsolete: true
Attachment #8734993 - Flags: review?(till)
Attachment #8734996 - Flags: review?(till)
Comment on attachment 8734996 [details] [diff] [review]
typedarraysort.diff

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

Great idea! :)

::: js/src/builtin/Sorting.js
@@ +234,5 @@
>  
> +    // Until recently typed arrays had no sort method. To work around that
> +    // many users passed them to Array.prototype.sort. Now that we have a
> +    // typed array specific sorting method it makes sense to divert to it
> +    // when possible.

Can you describe the issue we were otherwise getting? The comment makes it sound like it's a pure optimization, so someone might try to rip it out at some point.

::: js/src/tests/ecma_6/Array/sort_basics.js
@@ +12,5 @@
>  function SortTest(size, seed) {
>      let arrOne    = genRandomArray(size, seed);
>      let arrTwo    = Array.from(arrOne);
>      let arrThree  = Array.from(arrOne);
> +    let typedArr  = new Int32Array(arrOne);

Can you add at least Int8Array in addition here? Ideally you'd use all the typed arrays, given that we use or intend to use different sorting strategies. I know that we have more in-depth tests for that, but applying just this basic test to all of them seems prudent.
Attachment #8734996 - Flags: review?(till) → review+
Comment on attachment 8734996 [details] [diff] [review]
typedarraysort.diff

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

::: js/src/tests/ecma_6/Array/sort_basics.js
@@ +27,5 @@
> +                 `The array is not properly sorted! seed: ${SEED}`);
> +
> +    // Ensure that typed arrays are also sorted property.
> +    assertDeepEq(Array.from((Int32Array.from(arrOne)).sort()),
> +                 Array.from(Array.prototype.sort.call(typedArr, (x, y) => (1*x - 1*y))),

So, um.  As I recall, Array.prototype.sort with the default comparator (as on the first line) does lexicographic sorting: [1000, 1, 2] sorts to [1, 1000, 2].  But typed array sorting, or the sorting performed by the custom comparator (on the second line here), does *numeric* sorting: [1000, 1, 2] sots to [1, 2, 1000].  Not the same sort, so it seems to me these really should be different.

So either this is happening to get (consistently) lucky, or it's wrong, or I'm just missing something.  Which is it?
According to the spec, TypedArray.prototype.sort should be doing a numeric sort and this is a difference from the behavior of Array.prototype.sort, which is lexicographic. If you look at places like MDN the sorts are described as the same but in practice they're not.

If I read that (rather awkwardly structured) code snippet correctly, it's:

assertDeepEq(
  Array.from(
    (Int32Array.from(arrOne)).sort()
  ),
  Array.from(
    Array.prototype.sort.call(
      typedArr, 
      (x, y) => (1*x - 1*y)
    )
  ),

and that looks roughly right to me. The first sort is going to invoke TypedArray.prototype.sort, and the second sort is invoking Array.prototype.sort but with a custom comparator to provide numeric (ish) ordering. The two outer 'Array.from' calls seem to be intended to ensure that both sides are Array (instead of, for example, Int32Array) before comparing them. This works because of a (undocumented?) property of Array.prototype.sort where it returns 'this' after completion.

So that assertion looks fine to me!
Comment on attachment 8734996 [details] [diff] [review]
typedarraysort.diff

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

Thanks for pointing out what I was missing!

::: js/src/tests/ecma_6/Array/sort_basics.js
@@ +27,5 @@
> +                 `The array is not properly sorted! seed: ${SEED}`);
> +
> +    // Ensure that typed arrays are also sorted property.
> +    assertDeepEq(Array.from((Int32Array.from(arrOne)).sort()),
> +                 Array.from(Array.prototype.sort.call(typedArr, (x, y) => (1*x - 1*y))),

Oh, ugh.  I read the mess of parentheses around Int32Array.from(arrOne) and surroundings as

  Array.from(Int32Array.from(arrOne)).sort()

in which case things would have been wrong.  But yes, as the sort is on the typed array, it's good.

I would greatly prefer if we *did not* have parentheses around Int32Array.from(arrOne):

  Array.from(Int32Array.from(arrOne).sort()),

Normal precedence rules are IMO entirely effective and entirely readable here.  And because of that, the *only* reason I would ordinarily expect a '(' after 'Array.from(' is to add parentheses needed above and beyond normal precedence, or at least beyond the well-known rules, that led me astray.
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #10)
> Comment on attachment 8734996 [details] [diff] [review]
> typedarraysort.diff
> 
> Review of attachment 8734996 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Thanks for pointing out what I was missing!
> 
> ::: js/src/tests/ecma_6/Array/sort_basics.js
> @@ +27,5 @@
> > +                 `The array is not properly sorted! seed: ${SEED}`);
> > +
> > +    // Ensure that typed arrays are also sorted property.
> > +    assertDeepEq(Array.from((Int32Array.from(arrOne)).sort()),
> > +                 Array.from(Array.prototype.sort.call(typedArr, (x, y) => (1*x - 1*y))),
> 
> Oh, ugh.  I read the mess of parentheses around Int32Array.from(arrOne) and
> surroundings as
> 
>   Array.from(Int32Array.from(arrOne)).sort()
> 
> in which case things would have been wrong.  But yes, as the sort is on the
> typed array, it's good.
> 
> I would greatly prefer if we *did not* have parentheses around
> Int32Array.from(arrOne):
> 
>   Array.from(Int32Array.from(arrOne).sort()),
> 
> Normal precedence rules are IMO entirely effective and entirely readable
> here.  And because of that, the *only* reason I would ordinarily expect a
> '(' after 'Array.from(' is to add parentheses needed above and beyond normal
> precedence, or at least beyond the well-known rules, that led me astray.

Apologies for the ugliness. I'm making the tests more legible before landing.
Comment on attachment 8734996 [details] [diff] [review]
typedarraysort.diff

Approval Request Comment
[Feature/regressing bug #]: 
[User impact if declined]: May break web pages.
[Describe test coverage new/current, TreeHerder]: Failures would be seen in SpiderMonkey tests (ecma_6/Array/sort_basic.js).
[Risks and why]: Breaking changes to typed array sorts.
[String/UUID change made/needed]:
Attachment #8734996 - Flags: approval-mozilla-beta?
Attachment #8734996 - Flags: approval-mozilla-beta?
Attachment #8734996 - Attachment is obsolete: true
https://hg.mozilla.org/mozilla-central/rev/67e4eb38e3b8
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
Wait. I'm not sure this was fixed correctly.

https://tc39.github.io/ecma262/#sec-array.prototype.sort says:
> The following steps are taken:
>
> 1.  Perform an implementation-dependent sequence of calls to the [[Get]] and [[Set]]
>     internal methods of obj, to the DeletePropertyOrThrow and HasOwnProperty abstract
>     operation with obj as the first argument, and to SortCompare (described below),
>     such that:

...followed by a bunch more text, but basically the spec says we are only permitted to do
property gets, sets, deletes, and existence checks, and call the comparator.

So we're not allowed to use DefineProperty here. So if our MoveHoles routine is doing that,
it has a bug, and it would be observable when using sort() on any sealed object with holes,
not just typed arrays.

Morgan, please either reopen this or file a follow-up bug, if I'm correct... :-\
Flags: needinfo?(winter2718)
(In reply to Jason Orendorff [:jorendorff] from comment #16)
> Wait. I'm not sure this was fixed correctly.
> 
> https://tc39.github.io/ecma262/#sec-array.prototype.sort says:
> > The following steps are taken:
> >
> > 1.  Perform an implementation-dependent sequence of calls to the [[Get]] and [[Set]]
> >     internal methods of obj, to the DeletePropertyOrThrow and HasOwnProperty abstract
> >     operation with obj as the first argument, and to SortCompare (described below),
> >     such that:
> 
> ...followed by a bunch more text, but basically the spec says we are only
> permitted to do
> property gets, sets, deletes, and existence checks, and call the comparator.
> 
> So we're not allowed to use DefineProperty here. So if our MoveHoles routine
> is doing that,
> it has a bug, and it would be observable when using sort() on any sealed
> object with holes,
> not just typed arrays.
> 
> Morgan, please either reopen this or file a follow-up bug, if I'm correct...
> :-\

I'll follow a follow up bug.
Flags: needinfo?(winter2718)
Comment on attachment 8735562 [details] [diff] [review]
typedarraysort.diff

Approval Request Comment
[Feature/regressing bug #]:
[User impact if declined]: Any attempt to sort typed arrays using Array.prototype.sort will fail. This is probably a common operation in the wild.
[Describe test coverage new/current, TreeHerder]:
[Risks and why]: 
[String/UUID change made/needed]:
Attachment #8735562 - Flags: approval-mozilla-aurora?
Hi Till, looking at bug 715181 mentioned in comment 1 as a possible cause of this regression, I am wondering if Beta 46 is also affected. Is it? If yes, should we consider uplifting to Beta as well?
Flags: needinfo?(till)
Comment on attachment 8735562 [details] [diff] [review]
typedarraysort.diff

Seems like a recent regression, Aurora47+
Attachment #8735562 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
(In reply to Ritu Kothari (:ritu) from comment #20)
> Hi Till, looking at bug 715181 mentioned in comment 1 as a possible cause of
> this regression, I am wondering if Beta 46 is also affected. Is it? If yes,
> should we consider uplifting to Beta as well?

Yes, it is. Yes, we should. Mrrrgn, anything we need to wait for before requesting uplift?
Flags: needinfo?(till) → needinfo?(winter2718)
(In reply to Till Schneidereit [:till] from comment #22)
> (In reply to Ritu Kothari (:ritu) from comment #20)
> > Hi Till, looking at bug 715181 mentioned in comment 1 as a possible cause of
> > this regression, I am wondering if Beta 46 is also affected. Is it? If yes,
> > should we consider uplifting to Beta as well?
> 
> Yes, it is. Yes, we should. Mrrrgn, anything we need to wait for before
> requesting uplift?

I'd say it's fair to go ahead. I'm putting up a patch for [related bug] https://bugzilla.mozilla.org/show_bug.cgi?id=1260673 in a moment, but I think it is less critical than this.
Flags: needinfo?(winter2718)
Comment on attachment 8735562 [details] [diff] [review]
typedarraysort.diff

Approval Request Comment
[Feature/regressing bug #]:
[User impact if declined]: Any attempt to sort typed arrays using Array.prototype.sort will fail. This is probably a common operation in the wild.
[Describe test coverage new/current, TreeHerder]: includes additional JS tests
[Risks and why]: very low
[String/UUID change made/needed]: none
Attachment #8735562 - Flags: approval-mozilla-beta?
Regression in 46, tracking. 
How can we verify this fix?
Flags: qe-verify+
Flags: needinfo?(till)
Comment on attachment 8735562 [details] [diff] [review]
typedarraysort.diff

Fix for regression in 46, OK to uplift. 
Includes new tests.
Attachment #8735562 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
Reproduced the initial behavior on old Nightly (2016-03-24), verified that the issue is fixed using latest Nightly 48.0a1, latest Aurora 47.0a2 and Firefox 46 beta 8 across platforms (Windows 7 64-bit, Mac OS X 10.10.5 and Ubuntu 14.04 64-bit).
Status: RESOLVED → VERIFIED
Flags: qe-verify+
Flags: needinfo?(till)
You need to log in before you can comment on or make changes to this bug.