Closed Bug 1421398 Opened 2 years ago Closed 2 years ago

Implement Array.prototype.flatten and Array.prototype.flatMap

Categories

(Core :: JavaScript Engine, enhancement, P2)

57 Branch
enhancement

Tracking

()

RESOLVED FIXED
mozilla59
Tracking Status
firefox59 --- fixed

People

(Reporter: alex.fdm, Assigned: evilpie)

References

(Blocks 1 open bug, )

Details

(Keywords: dev-doc-complete)

Attachments

(3 files, 4 obsolete files)

Array.prototype.flatten and Array.prototype.flatMap are already on Stage 3, and likely to be standardized soon:
https://tc39.github.io/proposal-flatMap/
Looks like fun. Tom, are you interested?
Flags: needinfo?(evilpies)
Priority: -- → P2
Sure. I am probably going to implement flatten in C++ and flatMap in self-hosted JS.
Assignee: nobody → evilpies
Flags: needinfo?(evilpies)
FlattenIntoArray is recursive :/ However the standard depth is just 1, so maybe we don't need to rewrite this to be iterative.
Attached patch WIP (obsolete) — Splinter Review
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.
I want to wait for someone to implement test262 tests for this. https://github.com/tc39/proposal-flatMap/issues/51
There are very basic tests on https://kangax.github.io/compat-table/esnext/
I wonder if it would be simpler to just implement Array.prototype.flatten in JS code as well.
Depends on: 1429778
Attached patch JS-only implementation (obsolete) — Splinter Review
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 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)`
Attachment #8933983 - Attachment is obsolete: true
Attachment #8942224 - Attachment is obsolete: true
(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.
Attachment #8942914 - Flags: review?(andrebargull)
This is Nightly only for now, because it's only stage 3.
Attachment #8942914 - Attachment is obsolete: true
Attachment #8942914 - Flags: review?(andrebargull)
Attachment #8942915 - Flags: review?(andrebargull)
Attachment #8942919 - Flags: review?(andrebargull)
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...?
Attachment #8942915 - Flags: review?(andrebargull)
Nvm the test262 comment in comment #15, I wrote that before the test262 patch.
Attachment #8942919 - Flags: review?(andrebargull) → review+
(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.
Attachment #8942951 - Flags: review?(andrebargull)
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.
Attachment #8942951 - Flags: review?(andrebargull) → review+
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.
Pushed by evilpies@gmail.com:
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
Ups, forgot about (again). I am going to fold this patch after review.
Flags: needinfo?(evilpies)
Attachment #8943574 - Flags: review?(bzbarsky)
Comment on attachment 8943574 [details] [diff] [review]
Add flatten and flatMap to test_xrayToJS.xul

r=me
Attachment #8943574 - Flags: review?(bzbarsky) → review+
Pushed by evilpies@gmail.com:
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
https://hg.mozilla.org/mozilla-central/rev/8ae56bfed524
https://hg.mozilla.org/mozilla-central/rev/6604ac0cc769
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
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.
Depends on: 1443630
Depends on: 1450356
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.
I see now that there's already issue #1465039 for that, sorry for the noise.
You need to log in before you can comment on or make changes to this bug.