The default bug view has changed. See this FAQ.

Implement Map#forEach and Set#forEach

RESOLVED FIXED in mozilla25

Status

()

Core
JavaScript Engine
RESOLVED FIXED
4 years ago
3 years ago

People

(Reporter: evilpie, Assigned: sankha)

Tracking

(Blocks: 1 bug, {dev-doc-complete, feature})

Trunk
mozilla25
x86_64
Linux
dev-doc-complete, feature
Points:
---
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(relnote-firefox 25+)

Details

(Whiteboard: [qa-][DocArea=JS], URL)

Attachments

(1 attachment, 6 obsolete attachments)

(Reporter)

Description

4 years ago
This should be reasonably simple to do. I am going to evaluate if it makes sense to do this with self-hosting.
(Assignee)

Comment 1

4 years ago
Created attachment 754272 [details] [diff] [review]
patch v1
Assignee: general → sankha93
Attachment #754272 - Flags: review?(evilpies)
Comment on attachment 754272 [details] [diff] [review]
patch v1

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

Stealing review because I got interested enough to look into it a bit more. (By all means, keep conversion with evilpie, however, I don't want to steal the entire bug in any form, whatsoever!)

This is certainly going in the right direction, but there are some changes that need to happen for this to land.

General nit: the whitespace is off in many places: make sure to not use tabs anywhere. Personally, I make my editor whitespace to make sure I get this (and trailing whitespace at line ends) right.

General non-nit: Please add comments stating which step(s) of the specified algorithms is implemented in which line(s) of code. See Array.js for the canonical way to do this.

Second non-nit: Please test the corner-cases more thoroughly. That mostly entails creating tests that should throw based on the tests required by the spec.

::: js/src/builtin/Map.js
@@ +3,5 @@
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* ES6 20121122 draft 15.5.4.21. */
> +
> +function Map_forEach(callbackfn, thisArg = undefined) {

1. I'm on the fence about the function naming, here. The style we currently use would call for naming this `MapForEach`. OTOH, I kinda like this style. But still, let's be consistent, here.

2. I doubt that default arguments are optimized enough yet to make them usable for builtin methods we want to be as fast as possible. See Array.js for how we currently deal with this. If, on the other hand, you've got benchmarks showing that using default args doesn't cause a slow-down: fantastic!

@@ +6,5 @@
> +
> +function Map_forEach(callbackfn, thisArg = undefined) {
> +	var M = this;
> +	if(typeof M != "object")
> +		ThrowError(JSMSG_BAD_TYPE);

We need to check for the internal [[MapData]] property, here. Probably requires adding a native intrinsic.

@@ +9,5 @@
> +	if(typeof M != "object")
> +		ThrowError(JSMSG_BAD_TYPE);
> +	if (!IsCallable(callbackfn))
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +    var entries = [...M];

This is a pretty expensive way of getting the entries. Again, an intrinsic is probably required to make this work well.

@@ +12,5 @@
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +    var entries = [...M];
> +    for (var i = 0; i < entries.length; i++)
> +    	callFunction(callbackfn, thisArg, [entries[i][1], entries[i][0]], M);
> +    return undefined;

No need for this.

::: js/src/builtin/Set.js
@@ +7,5 @@
> +function Set_forEach(callbackfn, thisArg = undefined) {
> +	var S = this;
> +	if(typeof S != "object")
> +		ThrowError(JSMSG_BAD_TYPE);
> +	if (!IsCallable(callbackfn))

Again, need to check for the internal [[SetData]] property, here.

@@ +9,5 @@
> +	if(typeof S != "object")
> +		ThrowError(JSMSG_BAD_TYPE);
> +	if (!IsCallable(callbackfn))
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +    for (var e of S)

This *might* actually work just fine, and not require to actually get the internal [[SetData]] property. I'm not entirely sure, however.
Attachment #754272 - Flags: review?(evilpies)
(Reporter)

Comment 3

4 years ago
Comment on attachment 754272 [details] [diff] [review]
patch v1

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

The comments apply to Set as well. Seems like without a support function to get the real iterator or the underlying elements is impossible to correctly implement. One idea would be to save the Map.prototype.iterator in the self hosting global and use that.

::: js/src/builtin/Map.js
@@ +4,5 @@
> +
> +/* ES6 20121122 draft 15.5.4.21. */
> +
> +function Map_forEach(callbackfn, thisArg = undefined) {
> +	var M = this;

Indention looks wrong.

@@ +5,5 @@
> +/* ES6 20121122 draft 15.5.4.21. */
> +
> +function Map_forEach(callbackfn, thisArg = undefined) {
> +	var M = this;
> +	if(typeof M != "object")

typeof m also returns "object" for |null|

@@ +9,5 @@
> +	if(typeof M != "object")
> +		ThrowError(JSMSG_BAD_TYPE);
> +	if (!IsCallable(callbackfn))
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +    var entries = [...M];

This is actually observable when somebody overrides Map.prototype.iterator. You need to write some functions that allows you iterate the map object. Maybe it would be easier to implement this in C++ after all.

::: js/src/jit-test/tests/collections/Map-forEach.js
@@ +1,2 @@
> +// test Map.prototype.forEach
> +

You need to check more failure conditions.

Eg. Step 2. and 3. If |this| is not a Map. Try calling with eg. Set etc.
Step 5. Try passing a function that is not callable 
Step 6. Check that the callbacked gets passed the thisvalue and also check if we get undefined if no parameter is supplied to forEach.

Try throwing an error in the callback.

@@ +2,5 @@
> +
> +var testMap = new Map();
> +
> +function callback(entry, map) {
> +	testMap.set(entry[1], entry[0]);

We always use 4 spaces for indent.
From the sidelines!

(In reply to Till Schneidereit [:till] from comment #2)
> 2. I doubt that default arguments are optimized enough yet to make them
> usable for builtin methods we want to be as fast as possible. See Array.js
> for how we currently deal with this. If, on the other hand, you've got
> benchmarks showing that using default args doesn't cause a slow-down:
> fantastic!

I hadn't really taken this into consideration, so thank you for noting! Indeed it appears default params have some work ahead of them, re optimization. http://jsperf.com/default-params


Possibly irrelevant for now: I noticed that the cited revision date is 20121122, which is rev12, the latest draft is 20130514 rev15. I can't see any semantic differences, just language and grammatical changes, but in the future this might not be the case :)
Sorry, there is more!

There is actually a major difference between the revision cited and the latest revision: chapter and section numbers. In the patch both are listed as 15.5.4.21, but the should be:

15.14.4.4 Map.prototype.forEach ( callbackfn , thisArg = undefined )
15.16.4.6 Set.prototype.forEach ( callbackfn , thisArg = undefined )


Also, there is an issue with the callback args in Set_forEach, but I'm not a reviewer and not really familiar with how the reviewing tool works, so I'll just paste the diff here:

+    for (var e of S)
+    	callFunction(callbackfn, thisArg, e, S);

Must be changed to:

callFunction(callbackfn, thisArg, e, e, S);


> NOTE 2 The callbackfn is called with three arguments to be consistent with the callback functions used by forEach methods for Map and Array. For Sets, each item value is considered to be both the key and the value.

> 8.a.i Let funcResult be the result of calling the [[Call]] internal method of callbackfn with T as thisArgument and a List containing e, e, and S as argumentsList.

The tests need to be updated as well.
(Assignee)

Comment 6

4 years ago
(In reply to Tom Schuster [:evilpie] from comment #3)
> The comments apply to Set as well. Seems like without a support function to
> get the real iterator or the underlying elements is impossible to correctly
> implement. One idea would be to save the Map.prototype.iterator in the self
> hosting global and use that.

I think then I should wait for the patch on bug 869996 to land. Then we can use all the iterator methods for Set and Map directly.

Thanks, for the comments, I will update the patch accordingly. :)
(Assignee)

Comment 7

4 years ago
Created attachment 760433 [details] [diff] [review]
patch v2
Attachment #754272 - Attachment is obsolete: true
Attachment #760433 - Flags: review?(evilpies)
Comment on attachment 760433 [details] [diff] [review]
patch v2

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

::: js/src/jit-test/tests/collections/Set-forEach.js
@@ +20,5 @@
> +}
> +
> +var x = { abc: 'test'};
> +function callback2(value, key, set) {
> +    assertEq(x, this);

perhaps an assertion that value and key are the same?
(Assignee)

Comment 9

4 years ago
(In reply to Rick Waldron from comment #8)
> perhaps an assertion that value and key are the same?

I am doing that in callback function of Set-forEach.js, should I do it again?
Sankha, my mistake, I missed that. Sorry for the noise
(Reporter)

Comment 11

4 years ago
Comment on attachment 760433 [details] [diff] [review]
patch v2

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

Nice work so far. I will look at the tests a little bit later.

::: js/src/builtin/Map.js
@@ +4,5 @@
> +
> +/* ES6 20121122 draft 15.14.4.4. */
> +
> +function MapForEach(callbackfn, thisArg = undefined) {
> +    /* Step 1-2 */

nit: "Steps 1-2." (note dot and s) Applies to everything else.

@@ +6,5 @@
> +
> +function MapForEach(callbackfn, thisArg = undefined) {
> +    /* Step 1-2 */
> +    var M = this;
> +    if(typeof M != "object")

this should be if (!IsObject(M))

@@ +11,5 @@
> +        ThrowError(JSMSG_BAD_TYPE, typeof M);
> +
> +    /* Step 3-4 */
> +    try {
> +        std_Map_has.call(M);

I guess this works. I personally would prefer if we had used something like IsObjectWithClass in jsclass.h.

@@ +21,5 @@
> +    if (!IsCallable(callbackfn))
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +
> +    /* Step 6-8 */
> +    for (var [k, v] of M) {

This going to break when somebody changes the .iterator property. We could do something like (var [k, v] of std_Map_iterator.call(M)). Sadly our iterators aren't yet like in the spec, so this will need to change in the future. Add a test that we don't call the iterator property on M.

@@ +22,5 @@
> +        ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, callbackfn));
> +
> +    /* Step 6-8 */
> +    for (var [k, v] of M) {
> +        if (k)

This step is probably invalid. I believe we will never iterate over something the spec considers "empty". I believe your current code skips "falsy" keys. Add a test for that!

::: js/src/builtin/Set.js
@@ +17,5 @@
> +        ThrowError(JSMSG_BAD_TYPE, typeof M);
> +    }
> +
> +    /* Step 5-6 */
> +	if (!IsCallable(callbackfn))

Idention.

::: js/src/builtin/Utilities.js
@@ +71,1 @@
>  

we would need
var std_Map_iterator = Map.prototype.iterator;
var std_Set_iterator = Set.prototype.iterator;
Attachment #760433 - Flags: review?(evilpies)
> > +
> > +    /* Step 6-8 */
> > +    for (var [k, v] of M) {
> > +        if (k)
> 
> This step is probably invalid. I believe we will never iterate over
> something the spec considers "empty". I believe your current code skips
> "falsy" keys. Add a test for that!

Tom, 

I was curious about this and after reading the spec's language, it's unclear what should happen here, so I filed a spec bug: https://bugs.ecmascript.org/show_bug.cgi?id=1558 I've also cc'ed you on the bug.
(Assignee)

Comment 13

4 years ago
Created attachment 765759 [details] [diff] [review]
patch v3

This patch addresses the previous comments.

I talked to Waldo if IsObjectWithClass can used from self-hosting, he said that not right now, but Map.prototype.has should work fine. I changed it to iterator methods of Map and Set, so it does not iterate over empty elements anyways. So I have removed the check for empti-ness.
Attachment #760433 - Attachment is obsolete: true
Attachment #765759 - Flags: review?(evilpies)
>+    for (var [k, v] of M) {

I don't think this approach can work when user code tampers with %MapIteratorPrototype%.next. Here's a test:

    var m = new Map([["one", 1]]);
    Object.getPrototypeOf(m.iterator()).next = function () { throw "FAIL"; };
    m.forEach(_ => _);  // shouldn't throw

I'm also a little worried this is going to be much slower than the equivalent C++, which would be pretty straightforward. Another alternative is to self-host the Map and Set classes entirely.
(Assignee)

Comment 15

4 years ago
Should doing something like this solve the issue:

while (true) {
  try {
    var entry = std_Map_next(M);
    callFunction(callbackfn, thisArg, entry[0], entry[1], M);
  } catch (err) {
    if (err instanceof StopIteration)
      break;
  }
}

In Utilities.js we can add the line:
var std_Map_next = Map.prototype.next;
Flags: needinfo?(jorendorff)
Yes, that will work, though you need to rethrow err if it's not instanceof StopIteration.
Flags: needinfo?(jorendorff)
(Assignee)

Comment 17

4 years ago
Created attachment 770013 [details] [diff] [review]
patch v4

This patch fixes the issue mentioned by jorendorff.
Attachment #765759 - Attachment is obsolete: true
Attachment #765759 - Flags: review?(evilpies)
Attachment #770013 - Flags: review?(evilpies)
(Reporter)

Comment 18

4 years ago
Comment on attachment 770013 [details] [diff] [review]
patch v4

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

::: js/src/builtin/Map.js
@@ +6,5 @@
> +
> +function MapForEach(callbackfn, thisArg = undefined) {
> +    /* Step 1-2. */
> +    var M = this;
> +    if(!IsObject(M))

space if_(

::: js/src/builtin/Set.js
@@ +5,5 @@
> +/* ES6 20121122 draft 15.16.4.6. */
> +
> +function SetForEach(callbackfn, thisArg = undefined) {
> +    /* Step 1-2. */
> +	var S = this;

wrong indention

@@ +6,5 @@
> +
> +function SetForEach(callbackfn, thisArg = undefined) {
> +    /* Step 1-2. */
> +	var S = this;
> +	if(!IsObject(S))

space
(Reporter)

Comment 19

4 years ago
Comment on attachment 770013 [details] [diff] [review]
patch v4

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

Nice work. Thank you. I am very sorry for the long review lag.

::: js/src/builtin/Map.js
@@ +25,5 @@
> +    var entries = std_Map_iterator.call(M);
> +    while (true) {
> +        try {
> +            var entry = std_Map_iterator_next.call(entries);
> +            callFunction(callbackfn, thisArg, entry[1], entry[0], M);

You need to move this out of the try ... catch. Otherwise somebody could throw StopIterator in the callback and it would just stop the iteration, but not throw. This also needs a test.

::: js/src/builtin/Set.js
@@ +25,5 @@
> +    var values = std_Set_iterator.call(S);
> +    while (true) {
> +        try {
> +            var entry = std_Set_iterator_next.call(values);
> +            callFunction(callbackfn, thisArg, entry, entry, S);

Same deal.

::: js/src/jit-test/tests/collections/Map-forEach.js
@@ +17,5 @@
> +
> +for (var [k, v] of testMap) {
> +    assertEq(initialMap.has(k), true);
> +    assertEq(initialMap.get(k), testMap.get(k));
> +}

Maybe we should also check if we see them in the same order. This also doesn't cover the case where forEach shows more key/value pairs.

@@ +42,5 @@
> +// testing that Map#forEach uses internal next() function
> +
> +var m = new Map([["one", 1]]);
> +Object.getPrototypeOf(m.iterator()).next = function () { throw "FAIL"; };
> +m.forEach(_ => _);

Test like

assertThrowsInstanceOf(function () {
  m.forEach(function () { throw StopIterator; });
}, StopIterator, "...")
Attachment #770013 - Flags: review?(evilpies) → review+
(Assignee)

Comment 20

4 years ago
Created attachment 776500 [details] [diff] [review]
patch v5
Attachment #770013 - Attachment is obsolete: true
Attachment #776500 - Flags: review?(evilpies)
(Reporter)

Comment 21

4 years ago
Comment on attachment 776500 [details] [diff] [review]
patch v5

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

Nicely done. Thanks!

::: js/src/jit-test/tests/collections/Map-forEach.js
@@ +6,5 @@
> +
> +var testMap = new Map();
> +
> +function callback(value, key, map) {
> +	testMap.set(key, value);

Is that 8 spaces?
Attachment #776500 - Flags: review?(evilpies) → review+
(Assignee)

Comment 22

4 years ago
Created attachment 777817 [details] [diff] [review]
final patch

Oops! Tabs messed the spacing. This one is normal.
Attachment #776500 - Attachment is obsolete: true
(Assignee)

Updated

4 years ago
Keywords: checkin-needed
https://hg.mozilla.org/integration/mozilla-inbound/rev/c1025190b208
Flags: in-testsuite+
Keywords: checkin-needed
Backed out for jit-test failures.
https://hg.mozilla.org/integration/mozilla-inbound/rev/d64c6ceee5a7

https://tbpl.mozilla.org/php/getParsedLog.php?id=25439937&tree=Mozilla-Inbound
(Assignee)

Comment 25

4 years ago
Created attachment 778245 [details] [diff] [review]
fixed patch

Fixed the patch and pushed to try: https://tbpl.mozilla.org/?tree=Try&rev=c2ba402cf681

Try is green.
Attachment #777817 - Attachment is obsolete: true
(Assignee)

Updated

4 years ago
Keywords: checkin-needed
https://hg.mozilla.org/integration/mozilla-inbound/rev/657c02a2ff0f
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/657c02a2ff0f
Status: NEW → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla25
Keywords: dev-doc-needed
relnote-firefox: --- → ?

Updated

4 years ago
relnote-firefox: ? → 25+
Adding the feature keyword so that this bug is properly picked up by the Release Tracking wiki page.
Keywords: feature
Does this still need qa manual verification considering the existing automated tests ?
Flags: needinfo?(sankha93)
I'd say no programming-language feature, with automated tests, needs manual QA verification.  If others want to make some sort of sub-distinction to that view, feel free to note it.
Thanks Jeff.
qa- based on comment 30.
Whiteboard: [qa-]
(Assignee)

Updated

4 years ago
Flags: needinfo?(sankha93)
Whiteboard: [qa-] → [qa-][DocArea=JS]
Developer release notes:
https://developer.mozilla.org/en-US/Firefox/Releases/25#JavaScript

Reference docs:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/forEach

As always, feel free to review and improve these docs in the MDN wiki. Much appreciated.
Keywords: dev-doc-needed → dev-doc-complete
You need to log in before you can comment on or make changes to this bug.