1121936 - Implement %TypedArray%.prototype.{map, filter}

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Comment 1

[Eric Skoglund [:tephra]]

I have started work on this one.

Comment 2

[Tom S]

Hey Eric! Do you have any questions?

Comment 3

[Eric Skoglund [:tephra]]

(In reply to Tom Schuster [:evilpie] from comment #2)
> Hey Eric! Do you have any questions?

Hey sorry I had some other work that got ahead of me. I'm still working on it, getting into it tonight so I will probably hit some issue and have a question later.

Comment 4

[Eric Skoglund [:tephra]]

Okay here's what I'm stuck at. Sorry if these seem trivial but I'm still learning the codebase.

Looking at https://people.mozilla.org/~jorendorff/es6-draft.html#sec-%typedarray%.prototype.map step 7 we should access [[TypedArrayName]] and I guess that is not implemented yet (there's no TypedArrayName function defined and just trying to do .name on the object don't seem to work). Any pointers on how to implement this?

I'm not so sure about the SpeciesConstructor and AllocateTypedArray abstract functions either. Any idea on how to do that part of the implementation?

Comment 5

[Tom S]

These are very good questions. We indeed don't have [[TypedArrayName]] or SpeciesConstructor, because we don't implement proper sub-classing yet. So I suggest you just replace steps 7-11. with `new O.constructor(len)` for now. I will make sure to open a new bug so we don't forget to implement this.

Comment 6

[Eric Skoglund [:tephra]]

Thanks for the response. Should have a patch done for this weekend at the latest.

Comment 7

[Till Schneidereit [:till]]

Attachment: Part 1: add intrinsic for retrieving original builtin constructors

This enables getting original constructors for instances of builtins. It asserts if it's called for anything else. Given that TypedArray.prototype.map does a type check in step 2, and all other places in the spec that want us to retrieve original constructors (or prototypes) do, too, afaict, I don't see anything harmful about this approach.

Eric, this addresses your question about step 7. It can be implemented as `var defaultConstructor = _GetBuiltinConstructor(O)`.

As for step 8, ignore that for now. We don't support subclassing builtins yet, so it's not relevant.

Comment 8

[Till Schneidereit [:till]]

Sorry, didn't mean to reassign the bug to me.

I also didn't see evilpie's comments. I don't think using O.constructor is a good idea. Also, with my attached patch, you can fully implement step 7, at least.

Comment 9

[Dirkjan Ochtman (:djc)]

Attachment: MozReview Request: bz://1121936/djc

/r/3551 - Bug 1121936 - Part 1: add intrinsic for retrieving original builtin constructors. r=waldo
/r/3553 - Bug 1121935: Implement SpeciesConstructor stub for now
/r/3555 - Bug 1121935: Implement %TypedArray%.slice()
/r/3557 - Bug 1121935: Add tests for %TypedArray%.slice()

Pull down these commits:

hg pull review -r db8f3c33a61d6399cdf8a5a68fd7c20edcce7b50

Comment 10

[Dirkjan Ochtman (:djc)]

Sorry, please ignore that review request.

Comment 11

[Eric Skoglund [:tephra]]

(In reply to Dirkjan Ochtman (:djc) from comment #9)
> Created attachment 8561090 [details]
> MozReview Request: bz://1121936/djc
> 
> /r/3551 - Bug 1121936 - Part 1: add intrinsic for retrieving original
> builtin constructors. r=waldo
> /r/3553 - Bug 1121935: Implement SpeciesConstructor stub for now
> /r/3555 - Bug 1121935: Implement %TypedArray%.slice()
> /r/3557 - Bug 1121935: Add tests for %TypedArray%.slice()
> 
> Pull down these commits:
> 
> hg pull review -r db8f3c33a61d6399cdf8a5a68fd7c20edcce7b50

Right will be looking into this tomorrow then.

Comment 12

[Dirkjan Ochtman (:djc)]

(In reply to eric from comment #11)
> Right will be looking into this tomorrow then.

As I stated in comment 11, that request was erroneous; it has my changes for bug 1121935, but starts with the GetBuiltinConstructor patch that I stole from this bug, therefore MozReview appended comments to this issue. In any case, I don't think my patches should affect this bug.

Comment 13

[Eric Skoglund [:tephra]]

(In reply to Dirkjan Ochtman (:djc) from comment #12)
> (In reply to eric from comment #11)
> > Right will be looking into this tomorrow then.
> 
> As I stated in comment 11, that request was erroneous; it has my changes for
> bug 1121935, but starts with the GetBuiltinConstructor patch that I stole
> from this bug, therefore MozReview appended comments to this issue. In any
> case, I don't think my patches should affect this bug.

Ah sorry was a bit tired.

Comment 14

[Eric Skoglund [:tephra]]

Attachment: Part 2: Implementation of map and filter.

Tests coming tomorrow.

Comment 15

[Tom S]

Comment on attachment 8562330 [details] [diff] [review]
Part 2: Implementation of map and filter.

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

::: js/src/builtin/TypedArray.js
@@ +104,5 @@
> +    var O = this;
> +
> +    // Step 2-3.
> +    // This function is not generic.
> +    if (!IsObject(this) || !IsTypedArray(this)) {

nicer to use IsObject(O) here.

@@ +105,5 @@
> +
> +    // Step 2-3.
> +    // This function is not generic.
> +    if (!IsObject(this) || !IsTypedArray(this)) {
> +        return callFunction(CallTypedArrayMethodIfWrapped, this, callbackgn, thisArg,

Typo: callbackfn

@@ +121,5 @@
> +
> +    // Step 6.
> +    var T = thisArg;
> +
> +    // Step 7-9.

Step*s* please.

@@ +122,5 @@
> +    // Step 6.
> +    var T = thisArg;
> +
> +    // Step 7-9.
> +    // Step 8 ignored since SpeciesConstructor is not implemented.

I think it would be nice to at least have an almost useless implementation of SpeciesConstructor that we can extend.

@@ +127,5 @@
> +    var defaultConstructor = _GetBuiltinConstructor(O);
> +
> +    // Step 10.
> +    var kept = new Array();
> +

new List

@@ +133,5 @@
> +    var captured = 0;
> +
> +    // Step 11 and 13.
> +    for (var k = 0; k < len; k++) {
> +        // Step 13d and 13e.

13.d. and for everything else add the dot as well.

@@ +138,5 @@
> +        var selected = ToBoolean(callFunction(callbackfn, T, O[k], k, O));
> +        // Step 13f.
> +        if (selected) {
> +            // Step 13f.i.
> +            kept.push(O[k]);

You should introduce kValue, because you otherwise invoke O[k] twice. (However not observable anyway)

@@ +151,5 @@
> +    // Step 16.
> +    var n = 0;
> +
> +    // Step 17.
> +    for (var e of kept) {

I think after using `new List` you will have to use a plain old loop here.

@@ +153,5 @@
> +
> +    // Step 17.
> +    for (var e of kept) {
> +        // Step 17a-b.
> +        UnsafePutElements(A, n, kept[n]);

comment: I wonder if this is still safe after we introduce subclassing?

@@ +419,5 @@
>  }
>  
> +// ES6 draft rev32 (2015-02-02) 22.2.3.18 %TypedArray%.prototype.map(callbackfn [, thisArg]).
> +function TypedArrayMap(callbackfn, thisArg = undefined) {
> +    // Step 1.

Comments from filter apply here as well.

@@ +434,5 @@
> +    var len = TypedArrayLength(O);
> +
> +    // Step 5.
> +    if (arguments.length === 0)
> +        ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.prototype.map');

"%TypedArray%.prototype.map"

Comment 16

[Dirkjan Ochtman (:djc)]

(In reply to Tom Schuster [:evilpie] from comment #15)
> @@ +122,5 @@
> > +    // Step 6.
> > +    var T = thisArg;
> > +
> > +    // Step 7-9.
> > +    // Step 8 ignored since SpeciesConstructor is not implemented.
> 
> I think it would be nice to at least have an almost useless implementation
> of SpeciesConstructor that we can extend.

You could reuse my patch for this:

https://bugzilla.mozilla.org/attachment.cgi?id=8561096

Cheers,

Dirkjan

Comment 17

[Tom S]

Comment on attachment 8562330 [details] [diff] [review]
Part 2: Implementation of map and filter.

Quite solid already, but I would like to see a new version with those minor issues addressed. Thank you for making it this far.

Do you have any question about how to write a test for this change?

Comment 18

[Till Schneidereit [:till]]

Comment on attachment 8562330 [details] [diff] [review]
Part 2: Implementation of map and filter.

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

::: js/src/builtin/TypedArray.js
@@ +121,5 @@
> +
> +    // Step 6.
> +    var T = thisArg;
> +
> +    // Step 7-9.

... and everywhere below when the comment mentions more than one step.

@@ +127,5 @@
> +    var defaultConstructor = _GetBuiltinConstructor(O);
> +
> +    // Step 10.
> +    var kept = new Array();
> +

This is important because otherwise content script can override the filter algorithms behavior by defining accessors on Array.prototype:
Object.defineProperty(Array.prototype, 0, {get: myEvilGetter, set: myEvilSetter});

Add a test that would've caught this.

@@ +151,5 @@
> +    // Step 16.
> +    var n = 0;
> +
> +    // Step 17.
> +    for (var e of kept) {

Additionally, using for .. of is a no-go in self-hosted code, because it relies on the iterator protocol, which can be influenced by changing, in this case, Array.prototype[Symbol.iterator]. Please also add a test that would've caught this.

@@ +153,5 @@
> +
> +    // Step 17.
> +    for (var e of kept) {
> +        // Step 17a-b.
> +        UnsafePutElements(A, n, kept[n]);

I'm pretty sure it is. By my reading 9.4.5[1] combined with the last paragraph of 22.2.4[2] taken together guarantee that TypedArray subclasses cannot override access behavior of indexed elements.

[1] people.mozilla.org/~jorendorff/es6-draft.html#sec-%typedarray%-intrinsic-object
[2] http://people.mozilla.org/~jorendorff/es6-draft.html#sec-typedarray-constructors

::: js/src/vm/TypedArrayObject.cpp
@@ +807,5 @@
>      JS_SELF_HOSTED_FN("findIndex", "TypedArrayFindIndex", 2, 0),
>      JS_SELF_HOSTED_FN("forEach", "TypedArrayForEach", 2, 0),
>      JS_SELF_HOSTED_FN("indexOf", "TypedArrayIndexOf", 2, 0),
>      JS_SELF_HOSTED_FN("join", "TypedArrayJoin", 1, 0),
> +    JS_SELF_HOSTED_FN("map", "TypedArrayMap", 2, 0),

Nit: move this down one line.

Comment 19

[Eric Skoglund [:tephra]]

(In reply to Tom Schuster [:evilpie] from comment #17)
> Comment on attachment 8562330 [details] [diff] [review]
> Part 2: Implementation of map and filter.
> 
> Quite solid already, but I would like to see a new version with those minor
> issues addressed. Thank you for making it this far.
> 
> Do you have any question about how to write a test for this change?

No just was to late to do it last night, something similar to the test for TypedArray.prototype.each would suffice?

Sorry for the typo must have missed that both in my own testing and my "make-sure-there-are-no-typos" final check last night...

(In reply to Tom Schuster [:evilpie] from comment #15)
> I think after using `new List` you will have to use a plain old loop here.

(In reply to Till Schneidereit [:till] from comment #18)
>Additionally, using for .. of is a no-go in self-hosted code, because it relies on the iterator protocol, which can be influenced by changing, in this case, Array.prototype[Symbol.iterator]. Please also add a test that would've caught this.

I had that at first but was unsure because of the wording of the spec here was different from usual, will be more quick to ask on IRC when something like that arises again thanks :)

Comment 20

[Tom S]

> No just was to late to do it last night, something similar to the test for TypedArray.prototype.each
> would suffice?

It's a good start, but there are some more difficult things of course. First all of Tills suggestion. Then a test that would catch the bug that we would have introduced if we used kValue instead of O[k]. (The callback could change O[k], but that shouldn't matter).
SpeciesConstructor can throw.

Comment 21

[Tom S]

I think I switched up kValue and O[k].

Comment 22

[Till Schneidereit [:till]]

(In reply to eric from comment #19)
> I had that at first but was unsure because of the wording of the spec here
> was different from usual, will be more quick to ask on IRC when something
> like that arises again thanks :)

No worries at all - there's a huge amount of hidden complexity in all of this, so careful reviews are an absolute requirement.

Comment 23

[Eric Skoglund [:tephra]]

Attachment: Part 2: SpeciesConstructor stub from bug 1121935

Comment 24

[Eric Skoglund [:tephra]]

Attachment: Part 3: Implementation of map and filter and tests

Had some issues with GIT but think I managed to fix it..

Comment 25

[Eric Skoglund [:tephra]]

Attachment: bug1121936rev2.patch

Submitted wrong version.

Comment 26

[Tom S]

Comment on attachment 8564726 [details] [diff] [review]
bug1121936rev2.patch

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

::: js/src/builtin/TypedArray.js
@@ +154,5 @@
> +
> +    // Steps 16 and 17.c.
> +    for (var n = 0; n < captured; n++) {
> +	// Steps 17.a-b.
> +	UnsafePutElements(A, n, kept[n]);

In the way SpeciesConstructor is implemented right now this is unsafe.
Consider:
var x = new Int32Array(5)
x.constructor = function() {}
x.map(v => v);

in that case new C, definitely doesn't result in an dense or typed array.

So, we should use A[n] = kept[n] here for now and open a new bug to correct this after we have subclassing.

@@ +420,5 @@
> +// ES6 draft rev32 (2015-02-02) 22.2.3.18 %TypedArray%.prototype.map(callbackfn [, thisArg]).
> +function TypedArrayMap(callbackfn, thisArg = undefined) {
> +    // Step 1.
> +    var O = this;
> +    

Nit: Remove whitespace.

@@ +433,5 @@
> +    var len = TypedArrayLength(O);
> +
> +    // Step 5.
> +    if (arguments.length === 0)
> +        ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'TypedArray.prototype.map');

nit: "%TypedArray%.prototype.map"

@@ +449,5 @@
> +
> +    // Steps 10-11.
> +    var A = new C(len);
> +
> +    // Steps 12-13.

That doesn't seem necessary.

@@ +455,5 @@
> +    for (var k = 0; k < len; k++) {
> +        // Steps 13.d-e.
> +        var mappedValue = callFunction(callbackfn, T, O[k], k, O);
> +        // Steps 13.f-g.
> +        UnsafePutElements(A, k, mappedValue);

Same here A[k] = mappedValue.

Comment 27

[Eric Skoglund [:tephra]]

Will get right on fixing those.

(In reply to Tom Schuster [:evilpie] from comment #26)

> @@ +449,5 @@
> > +
> > +    // Steps 10-11.
> > +    var A = new C(len);
> > +
> > +    // Steps 12-13.
> 
> That doesn't seem necessary.
> 

Could you expand a bit, I don't think I understand why.

Comment 28

[Tom S]

The next line already has "Steps 12, 13.a (implicit) and 13.h." and inside the loop you list all the other steps, so we avoid duplicating it like this. Just remove that comment.

Comment 29

[Eric Skoglund [:tephra]]

(In reply to Tom Schuster [:evilpie] from comment #28)
> The next line already has "Steps 12, 13.a (implicit) and 13.h." and inside
> the loop you list all the other steps, so we avoid duplicating it like this.
> Just remove that comment.

Ah sorry I thought you where referring to the `new C`. Thanks for clarifying.

Comment 30

[Jeff Walden [:Waldo]]

Comment on attachment 8559512 [details] [diff] [review]
Part 1: add intrinsic for retrieving original builtin constructors

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

::: js/src/vm/SelfHosting.cpp
@@ +822,5 @@
> +    MOZ_ASSERT(args[0].isObject());
> +
> +    RootedObject object(cx, &args[0].toObject());
> +    JSProtoKey protoKey = StandardProtoKeyOrNull(object);
> +    MOZ_ASSERT(protoKey);

I'm very leery of adding a fully-generic method like this.  I would rather we had a method *only* for determining builtin typed array constructor.  If we need a method that works on some other kind of object, we should add exactly that narrow method.  A generic method risks people overusing it, without realizing the implicit restrictions on when it may validly be called.  Simply skimming all the hits for SpeciesConstructor and reasoning backward from that to a defensive non-generic class check or similar doesn't cut it for me.

So please rename this to something like ConstructorForTypedArray and add a MOZ_ASSERT(IsTypedArray(&args[0].toObject())) to the method body.

Comment 31

[Till Schneidereit [:till]]

Attachment: Part 1: add intrinsic for retrieving original builtin constructors. v2

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #30)
> I'm very leery of adding a fully-generic method like this.  I would rather
> we had a method *only* for determining builtin typed array constructor.  If
> we need a method that works on some other kind of object, we should add
> exactly that narrow method.  A generic method risks people overusing it,
> without realizing the implicit restrictions on when it may validly be
> called.

Ok, I changed the name and added the assert. I don't understand how exactly it could be overused as ISTM that the restrictions are enforced by the asserts, but we don't need to resolve this to get something landed here. Instead, we can get back to that discussion if and when we have a second use-case for such an intrinsic.

@eric, please use this new version and adapt your patches accordingly. We can land all of them together.

Comment 32

[Eric Skoglund [:tephra]]

Attachment: Part 3: Implementation of map and filter and tests, Nit fixes

Comment 33

[Till Schneidereit [:till]]

I moved part 1 to bug 1121935, because otherwise we'd have a circular dependency between the two bugs. Please fix up the patch descriptions for part 2(-1) and part 3(-1) before landing.

Comment 34

[Tom S]

https://treeherder.mozilla.org/logviewer.html#?job_id=5023860&repo=try
There is some weird test failure that I am not sure what is caused by.

Comment 35

[Eric Skoglund [:tephra]]

(In reply to Tom Schuster [:evilpie] from comment #34)
> https://treeherder.mozilla.org/logviewer.html#?job_id=5023860&repo=try
> There is some weird test failure that I am not sure what is caused by.

That is weird, If I run all the tests locally all pass.

Comment 36

[Tom S]

It's actually quite incredible, I have an alter right before the reportCompare call that shows up.

Comment 37

[Tom S]

Oh I found the problem. The test changes Array.prototype[@@iterator] and Array.prototype[0] and somehow this must screw up the harness, when reverting these changes after the test everything works fine.

Comment 38

[Tom S]

Landed this! Thanks for all your effort, and I am sorry this was a little bit more difficult to get organized.
One small note: While I was fixing the test I noticed that some lines were using tabs.

https://hg.mozilla.org/integration/mozilla-inbound/rev/5f26a8bdf93e

Comment 39

[Eric Skoglund [:tephra]]

(In reply to Tom Schuster [:evilpie] from comment #38)
> Landed this! Thanks for all your effort, and I am sorry this was a little
> bit more difficult to get organized.
> One small note: While I was fixing the test I noticed that some lines were
> using tabs.
> 
> https://hg.mozilla.org/integration/mozilla-inbound/rev/5f26a8bdf93e

Thanks!

Sorry should have gone noticed that, will make sure to be extra careful in the future.

Comment 40

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5f26a8bdf93e

Comment 41

[Florian Scholz (Open Web Docs)]

https://developer.mozilla.org/en-US/Firefox/Releases/38#JavaScript
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/filter
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/map