1421398 - Implement Array.prototype.flatten and Array.prototype.flatMap

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P2)

Description

[Alexandre Folle de Menezes]

Array.prototype.flatten and Array.prototype.flatMap are already on Stage 3, and likely to be standardized soon:
https://tc39.github.io/proposal-flatMap/

Comment 1

[Jason Orendorff [:jorendorff]]

Looks like fun. Tom, are you interested?

Comment 2

[Tom S [:evilpie]]

Sure. I am probably going to implement flatten in C++ and flatMap in self-hosted JS.

Comment 3

[Tom S [:evilpie]]

FlattenIntoArray is recursive :/ However the standard depth is just 1, so maybe we don't need to rewrite this to be iterative.

Comment 4

[Tom S [:evilpie]]

Attachment: WIP

Need to check for interrupts/stack in the C++ implementation. More optimization for adding elements. Probably want to specialize the JS FlattenIntoArray, because depth is always 1.

Comment 5

[Tom S [:evilpie]]

I want to wait for someone to implement test262 tests for this. https://github.com/tc39/proposal-flatMap/issues/51

Comment 6

[Alexandre Folle de Menezes]

There are very basic tests on https://kangax.github.io/compat-table/esnext/

Comment 7

[Tom S [:evilpie]]

I wonder if it would be simpler to just implement Array.prototype.flatten in JS code as well.

Comment 8

[Tom S [:evilpie]]

Attachment: JS-only implementation

Todo: Need to pickup the test262 changes for this. I think we can't land this at the moment, because of the soft code freeze.

Comment 9

[Michael Ficarra]

Comment on attachment 8942224 [details] [diff] [review]
JS-only implementation

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

::: js/src/builtin/Array.js
@@ +1148,5 @@
> +    // Step 2.
> +    var depthNum = 1;
> +
> +    // Step 3.
> +    if (arguments.length > 1 && arguments[0] !== undefined)

`if (arguments.length > 0 && arguments[0] !== void 0)`

Comment 10

[Tom S [:evilpie]]

(In reply to Michael Ficarra from comment #9)
> Comment on attachment 8942224 [details] [diff] [review]
> JS-only implementation
> 
> Review of attachment 8942224 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/builtin/Array.js
> @@ +1148,5 @@
> > +    // Step 2.
> > +    var depthNum = 1;
> > +
> > +    // Step 3.
> > +    if (arguments.length > 1 && arguments[0] !== undefined)
> 
> `if (arguments.length > 0 && arguments[0] !== void 0)`

Thanks! Also caught this before after running the new test262 tests :) Luckily we can always use `undefined` in our self-hosted JS.

Comment 11

[Tom S [:evilpie]]

Attachment: Implement Array.prototype.flatten and flatMap

Comment 12

[Tom S [:evilpie]]

This is Nightly only for now, because it's only stage 3.

Comment 13

[Tom S [:evilpie]]

Attachment: Implement Array.prototype.flatten and flatMap

Comment 14

[Tom S [:evilpie]]

Attachment: Enable test262 tests on Nightly

Comment 15

[André Bargull [:anba]]

Comment on attachment 8942915 [details] [diff] [review]
Implement Array.prototype.flatten and flatMap

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

The implementation doesn't match the current proposal text. (Note: The rendered version wasn't yet updated to correspond to current master!) And the test262 tests also need to be enabled. Clearing r? for now.

::: js/src/builtin/Array.js
@@ +1130,5 @@
> +    // Step 5.
> +    var A = ArraySpeciesCreate(O, 0);
> +
> +    // Step 6.
> +    var nextIndex = FlattenIntoArray(A, O, O, sourceLen, 0, 1, mapperFunction, T);

I still wonder if inlining FlattenIntoArray here won't lead to better performance...?

Comment 16

[André Bargull [:anba]]

Nvm the test262 comment in comment #15, I wrote that before the test262 patch.

Comment 17

[Tom S [:evilpie]]

(In reply to André Bargull [:anba] from comment #15)
> Comment on attachment 8942915 [details] [diff] [review]
> Implement Array.prototype.flatten and flatMap
> 
> Review of attachment 8942915 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> The implementation doesn't match the current proposal text. (Note: The
> rendered version wasn't yet updated to correspond to current master!) And
> the test262 tests also need to be enabled. Clearing r? for now.
> 
D'uh that should not happen. Opened a github issue https://github.com/tc39/proposal-flatMap/issues/53
> ::: js/src/builtin/Array.js
> @@ +1130,5 @@
> > +    // Step 5.
> > +    var A = ArraySpeciesCreate(O, 0);
> > +
> > +    // Step 6.
> > +    var nextIndex = FlattenIntoArray(A, O, O, sourceLen, 0, 1, mapperFunction, T);
> 
> I still wonder if inlining FlattenIntoArray here won't lead to better
> performance...?
Sure, I think also implementing Array#flatten might be better for performance. I just didn't think it made sense to optimize this already.

Comment 18

[Tom S [:evilpie]]

Attachment: v2 - Implement Array.prototype.flatten and flatMap

Comment 19

[André Bargull [:anba]]

Comment on attachment 8942951 [details] [diff] [review]
v2 -  Implement Array.prototype.flatten and flatMap

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

r+ with moving |var sourceLen = ToLength(O.length);| to the correct position.

::: js/src/builtin/Array.js
@@ +1121,5 @@
> +    if (!IsCallable(mapperFunction))
> +        ThrowTypeError(JSMSG_NOT_FUNCTION, DecompileArg(0, mapperFunction));
> +
> +    // Step 3.
> +    var T = arguments.length > 1 ? arguments[1] : void 0;

I kind of wonder if we should replace the few existing uses of |void 0| in self-hosted code to |undefined|...

@@ +1124,5 @@
> +    // Step 3.
> +    var T = arguments.length > 1 ? arguments[1] : void 0;
> +
> +    // Step 4.
> +    var sourceLen = ToLength(O.length);

Step 2 in the current proposal text.

@@ +1130,5 @@
> +    // Step 5.
> +    var A = ArraySpeciesCreate(O, 0);
> +
> +    // Step 6.
> +    FlattenIntoArray(A, O, sourceLen, 0, 1, mapperFunction, T);

If we already inline FlattenIntoArray (and its recursive call) here, we'll end up with:
---
...

// FlattenIntoArray, step 3.c.iv.2 (Inlined recursive call).
for (var elementIndex = 0; elementIndex < elementLen; elementIndex++) {
    if (elementIndex in element) {
        var elementElement = element[elementIndex];

        // Only executed for its possible side-effects.
        IsArray(elementElement);

        _DefineDataProperty(target, targetIndex++, elementElement);
    }
}

...
---

which may convince :michaelficarra to switch the test expression from |IsArray(element) && depth > 0| to |depth > 0 && IsArray(element)| [1]. And that'll allow us to skip the IsArray call in the recursive FlattenIntoArray call for ArrayFlatMap which should provide better performance. WDYT?

[1] https://github.com/tc39/proposal-flatMap/issues/49

@@ +1149,5 @@
> +    if (arguments.length > 0 && arguments[0] !== undefined)
> +        depthNum = ToInteger(arguments[0]);
> +
> +    // Step 4.
> +    var sourceLen = ToLength(O.length);

Step 2 in the current proposal text.

@@ +1155,5 @@
> +    // Step 5.
> +    var A = ArraySpeciesCreate(O, 0);
> +
> +    // Step 6.
> +    FlattenIntoArray(A, O, sourceLen, 0, depthNum, undefined, undefined);

Maybe |FlattenIntoArray(A, O, sourceLen, 0, depthNum);| so it matches the proposal text? (And to ensure the arguments length check in FlattenIntoArray, step 3.c.ii.1. only succeeds when called from ArrayFlatMap.)

@@ +1192,5 @@
> +                // Step 3.c.iv.2.
> +                targetIndex = FlattenIntoArray(target, element, elementLen, targetIndex, depth - 1);
> +            } else {
> +                // Step 3.c.v.1.
> +                // if (targetIndex > 2**53)

Maybe expand why we choose not to implement this step?

@@ +1197,5 @@
> +
> +                // Step 3.c.v.2.
> +                _DefineDataProperty(target, targetIndex, element);
> +
> +                // Step 3.c.vi.

Typo: 3.c.v.3.

Comment 20

[Tom S [:evilpie]]

Thanks for reviewing.

> // FlattenIntoArray, step 3.c.iv.2 (Inlined recursive call).
> for (var elementIndex = 0; elementIndex < elementLen; elementIndex++) {
>     if (elementIndex in element) {
>         var elementElement = element[elementIndex];
> 
>         // Only executed for its possible side-effects.
>         IsArray(elementElement);
> 
>         _DefineDataProperty(target, targetIndex++, elementElement);
>     }
> }
> 
> ...
> ---
> 
> which may convince :michaelficarra to switch the test expression from
> |IsArray(element) && depth > 0| to |depth > 0 && IsArray(element)| [1]. And
> that'll allow us to skip the IsArray call in the recursive FlattenIntoArray
> call for ArrayFlatMap which should provide better performance. WDYT?
> 
> [1] https://github.com/tc39/proposal-flatMap/issues/49
> 
I agree, my previous implementation that had flatten in C++ also had this useless IsArray call purely for side-effects.
I actually think it might be cleaner to split up FlattenIntoArray even in the specification.

> @@ +1155,5 @@
> > +    // Step 5.
> > +    var A = ArraySpeciesCreate(O, 0);
> > +
> > +    // Step 6.
> > +    FlattenIntoArray(A, O, sourceLen, 0, depthNum, undefined, undefined);
> 
> Maybe |FlattenIntoArray(A, O, sourceLen, 0, depthNum);| so it matches the
> proposal text? (And to ensure the arguments length check in
> FlattenIntoArray, step 3.c.ii.1. only succeeds when called from
> ArrayFlatMap.)
> 
Done.
> @@ +1192,5 @@
> > +                // Step 3.c.iv.2.
> > +                targetIndex = FlattenIntoArray(target, element, elementLen, targetIndex, depth - 1);
> > +            } else {
> > +                // Step 3.c.v.1.
> > +                // if (targetIndex > 2**53)
> 
> Maybe expand why we choose not to implement this step?
> 
After I noticed that we already implement this for other functions, I just went ahead and implemented it.

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/11049b0dda2e
Implement Array.prototype.flatten and Array.prototype.flatMap in Nightly. r=anba
https://hg.mozilla.org/integration/mozilla-inbound/rev/f38ff2642870
Enable test262 tests. r=anba

Comment 22

[Natalia Csoregi [:nataliaCs]]

Backed out for failing xpconnect/tests/chrome/test_xrayToJS.xul - lack of security audit

backout: https://hg.mozilla.org/integration/mozilla-inbound/rev/190d9992de1b9ed19e68c03f3fd0032ac324b3e7

push with failures: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=f38ff2642870a8b36cb13d3117806f4fad3a8eea

failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=156931337&repo=mozilla-inbound&lineNumber=1648

Comment 23

[Tom S [:evilpie]]

Attachment: Add flatten and flatMap to test_xrayToJS.xul

Ups, forgot about (again). I am going to fold this patch after review.

Comment 24

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8943574 [details] [diff] [review]
Add flatten and flatMap to test_xrayToJS.xul

r=me

Comment 25

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/8ae56bfed524
Implement Array.prototype.flatten and Array.prototype.flatMap in Nightly. r=anba,bz
https://hg.mozilla.org/integration/mozilla-inbound/rev/6604ac0cc769
Enable test262 tests. r=anba

Comment 26

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/8ae56bfed524
https://hg.mozilla.org/mozilla-central/rev/6604ac0cc769

Comment 27

[Florian Scholz (Open Web Docs)]

Initial docs for this got written:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flatten
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flatMap

Browser compat data:
https://github.com/mdn/browser-compat-data/pull/985
https://github.com/mdn/browser-compat-data/pull/1009

As this is not in any release yet, I've added it to the "Experimental features" page:
https://developer.mozilla.org/en-US/Firefox/Experimental_features#JavaScript

We should add an interactive example when this is in release or in any other browser
https://github.com/mdn/interactive-examples/tree/master/live-examples/js-examples/array

bug 1435813 is tracked with dev-doc-needed for when this hits Firefox release.

Review and improvements to the MDN wiki pages are welcome.

Comment 28

[Alexandre Folle de Menezes]

The latest spec changed Array.prototype.flatten() to Array.prototype.flat().  The MDN docs were are already updated, but the JS engine wasn't yet.

Comment 29

[Alexandre Folle de Menezes]

I see now that there's already issue #1465039 for that, sorry for the noise.