Closed Bug 934423 Opened 11 years ago Closed 10 years ago

Implement Array#copyWithin

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla32
Tracking Status
relnote-firefox --- 32+

People

(Reporter: sankha, Assigned: sankha)

References

(Blocks 1 open bug, )

Details

(Keywords: dev-doc-complete, feature, Whiteboard: [js:p2])

Attachments

(2 files, 3 obsolete files)

Assignee: nobody → sankha93
Attached patch patch v1 (obsolete) — Splinter Review
Attachment #826753 - Flags: review?(jorendorff)
Comment on attachment 826753 [details] [diff] [review]
patch v1

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

Thanks for the patch, and I'm sorry for the slow review.

I'd like good test coverage for this because we should optimize it later, and the desired optimization is rather tricky, so it requires good tests.

Clearing the r? bit for now.

Things to test:

- test that it throws if this is null or undefined
- test it with a string or number as this
- test it with a TypedArray as this
- test it with an arguments object as this
- and if the arguments object is sloppy, copyWithin must actually move
  the arguments around, that is:

    function f(a, b, c, d, e) {
        [].copyWithin.call(arguments, 1, 0);
        return [a, b, c, d, e];
    }
    assertDeepEq(f(1, 2, 3, 4, 5), [1, 1, 2, 3, 4]);

- test it on an object with an extremely large .length,
  but copying just a small range of elements

  (Be sure to check both cases where the elements being moved are near 0
  and where they also have extremely large offsets.)

  (I think the algorithm is specified such that it's supposed to work
  even if .length is over 2^32, but if that is hard to implement, it's
  OK to land without that part working.)

- test it with two arguments and target > start
- test it with three arguments and target > start 
- test it on an array that has holes
- test fractional arguments
- test it with -0
- test it with arguments greater than this.length
- test it with arguments less than -this.length
- test it with arguments that are exactly -this.length
- test it on an empty array
- test target range being shorter than end-start
- test final < from
- test overlapping ranges
- test it with identical ranges
- test that the delete is strict (That is, I think it is supposed to
  throw if the property exists and can't be deleted. For example, try it
  on a frozen Array with holes.)
- test that the assignment is strict
- test on a proxy that traps fire in the right sequence
- test overlapping ranges with lots of holes
- test getting/setting/deleting elements that exist on prototypes
- test the resulting state if we throw partway through
- test explicitly passing undefined as the third argument
- test that if this.length has a getter, it is only called once,
    even if the third argument is omitted
- consider testing it on a large array
- test it when this array is full of floating-point numbers
- test it when this array is full of objects
  (I want this test because it's a GC test.)

Performance things to try:

- Measure the speed on a big array.

- See if it helps if you can avoid incrementing/decrementing the count
  variable in step 19.

- In a separate patch, test to see if the code goes much faster if
  `direction` is not a variable but rather there are two copies of
  step 19, one using ++ and one using --.

You don't have to do those things; we can do them in a follow-up bug. But they might be fun to do now.

::: js/src/builtin/Array.js
@@ +509,5 @@
> +    /* Step 19. */
> +    while (count > 0) {
> +        /* Steps 19a-d. */
> +        var fromKey = ToString(from);
> +        var toKey = ToString(to);

Definitely skip this ToString step. It's not observable, even if O is not an Array object, and it's much faster to use the numbers to index into the array.

@@ +510,5 @@
> +    while (count > 0) {
> +        /* Steps 19a-d. */
> +        var fromKey = ToString(from);
> +        var toKey = ToString(to);
> +        var fromPresent = callFunction(std_Object_hasOwnProperty, O, fromKey);

hasOwnProperty is wrong; you're looking for the `in` keyword (see below)

@@ +515,5 @@
> +
> +        /* Steps 19e-f. */
> +        if (fromPresent) {
> +            var fromVal = O[fromKey];
> +            O[toKey] = fromVal;

Please omit the fromVal temp variable:

    if (from in O)
        O[to] = O[from];
    else
        delete O[to];

However I think these have to be strict assignment and strict deletion, so I think you probably have a bug here in the case that the array is frozen. You'll have to consult the spec to be sure.
Attachment #826753 - Flags: review?(jorendorff)
Component: JavaScript Engine → JavaScript: Standard Library
Keywords: feature
Whiteboard: [js:p2]
Sankha, are you still working on this? If not, I'll drive it in - there isn't much left to do, after all.

(In reply to Jason Orendorff [:jorendorff] from comment #2)
> Please omit the fromVal temp variable:
> 
>     if (from in O)
>         O[to] = O[from];
>     else
>         delete O[to];
> 
> However I think these have to be strict assignment and strict deletion, so I
> think you probably have a bug here in the case that the array is frozen.
> You'll have to consult the spec to be sure.

With bug 995200 landed, this isn't required anymore. Tests for that situation would be good, though. Bug 911147 contains quite a few of those, which should be fairly easy to adapt.
Status: NEW → ASSIGNED
Flags: needinfo?(sankha93)
Attached patch patch v2 (obsolete) — Splinter Review
Added a whole bunch of tests.

Also, I got rid of the direction variable and have two copies of the while loop now for increment and decrement operator. According to my basic tests, it took the performance almost 2x.

With direction variable: 84
Without direction variable: 45
Attachment #826753 - Attachment is obsolete: true
Attachment #8409283 - Flags: review?(jorendorff)
Flags: needinfo?(sankha93)
Attached file benchmark
A very basic benchmark I used to test the performance.
Comment on attachment 8409283 [details] [diff] [review]
patch v2

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

> Also, I got rid of the direction variable and have two copies of the
> while loop now for increment and decrement operator. According to my
> basic tests, it took the performance almost 2x.

Sweet.

Nice tests, too. Thanks!

Almost there.

::: js/src/builtin/Array.js
@@ +510,5 @@
> +                                 : std_Math_min(relativeStart, len);
> +
> +    /* Steps 12-14. */
> +    var relativeEnd = arguments.length > 2 ? ToInteger(arguments[2])
> +                                           : len;

This has changed.  See:
http://people.mozilla.org/~jorendorff/es6-draft.html#sec-array.prototype.copywithin

Step 12 now begins "If end is undefined, ...".

@@ +526,5 @@
> +        /* Step 18. */
> +        while (count > 0) {
> +            var fromPresent = from in O;
> +
> +            if (fromPresent) {

Please delete the temporary variable and just say `if (from in O)`.

@@ +533,5 @@
> +                delete O[to];
> +            }
> +
> +            from = from--;
> +            to = to--;

Does this pass the tests? If so, I think we need some more tests, because this should say:
    from--;
    to--;

As written, these statements leave `from` and `to` unchanged.

@@ +541,5 @@
> +        /* Step 18. */
> +        while (count > 0) {
> +            var fromPresent = from in O;
> +
> +            if (fromPresent) {

Same comment as above.

@@ +548,5 @@
> +                delete O[to];
> +            }
> +
> +            from = from++;
> +            to = to++;

Same comment as above:
    from++;
    to++;

::: js/src/jit-test/tests/basic/array-copyWithin.js
@@ +135,5 @@
> +assertEq(arr[3], 4);
> +assertEq(arr[4], 5);
> +
> +// undefined as third argument
> +assertDeepEq([1, 2, 3, 4, 5].copyWithin(0, 3, undefined), [1, 2, 3, 4, 5]);

This is the test that I think should change behavior to match the most recent spec.

@@ +167,5 @@
> +// test on array of objects
> +for (var i = 0; i < large; i++) {
> +  arr[i] = { num: Math.random() };
> +}
> +arr.copyWithin(45, 900);

Please add:
    assertEq(arr.length, large);
    assertEq((large - 900 + 45 - 1) in arr, true);
    assertEq((large - 900 + 45) in arr, false);
    assertEq(large - 1 in arr, false);
Attachment #8409283 - Flags: review?(jorendorff)
Attached patch patch v3 (obsolete) — Splinter Review
Attachment #8409283 - Attachment is obsolete: true
Attachment #8425794 - Flags: review?(jorendorff)
Comment on attachment 8425794 [details] [diff] [review]
patch v3

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

Thanks very much! One more patch should do it.

I'm sorry I didn't find all the issues at once; they were there last time, and I missed them.

::: js/src/builtin/Array.js
@@ +489,5 @@
>      return -1;
>  }
>  
> +/* ES6 draft 2013-09-27 22.1.3.3. */
> +function ArrayCopyWithin(target, start/*, end*/) {

Please change this to:

    function ArrayCopyWithin(target, start, end=undefined) {

The resulting function will still have .length 2, and I avoiding `arguments` is always good.

@@ +510,5 @@
> +                                 : std_Math_min(relativeStart, len);
> +
> +    /* Steps 12-14. */
> +    var relativeEnd = arguments[2] == undefined ? len
> +                                                : ToInteger(arguments[2]);

These lines have two bugs:

1. `arguments[2] == undefined` is true if arguments[2] happens to be `null`. To fix this one, use === instead of ==.

2. `arguments[2]` can lie to you, if someone has tampered with Object.prototype.

        js> Object.prototype[2] = 6;  // of course this is not a nice thing to do
        6
        js> function f(target, start/*, end*/) { return arguments[2]; }
        js> f()  // should be undefined, but
        6        // surprise!

    Switching from `arguments[2]` to `end` should fix this one.

**Please add tests that would have detected each bug.**

@@ +528,5 @@
> +            if (from in O) {
> +                O[to] = O[from];
> +            } else {
> +                delete O[to];
> +            }

Style nit: Please remove the curly braces in this if-else statement, since each piece fits on a single line.

@@ +541,5 @@
> +            if (from in O) {
> +                O[to] = O[from];
> +            } else {
> +                delete O[to];
> +            }

Same here.

::: js/src/jsarray.cpp
@@ +2988,5 @@
>  
>      /* ES6 additions */
>      JS_SELF_HOSTED_FN("find",        "ArrayFind",        1,0),
>      JS_SELF_HOSTED_FN("findIndex",   "ArrayFindIndex",   1,0),
> +    JS_SELF_HOSTED_FN("copyWithin",  "ArrayCopyWithin",  2,0),

Please change this 2 to 3.
Attachment #8425794 - Flags: review?(jorendorff)
Attached patch patch v4Splinter Review
Addressed the above comments. Also added tests that will catch those bugs.
Attachment #8425794 - Attachment is obsolete: true
Attachment #8428893 - Flags: review?(jorendorff)
Attachment #8428893 - Flags: review?(jorendorff) → review+
https://hg.mozilla.org/mozilla-central/rev/2184d492b374
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla32
ziyunfei wrote the reference page:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/copyWithin

and I added it to the developer release notes for Firefox 32:
https://developer.mozilla.org/en-US/Firefox/Releases/32#JavaScript

Would be cool if someone could do a technical review of the reference page and the Polyfill. Thanks!
You need to log in before you can comment on or make changes to this bug.