Last Comment Bug 866847 - Implement Map#forEach and Set#forEach
: Implement Map#forEach and Set#forEach
Status: RESOLVED FIXED
[qa-][DocArea=JS]
: dev-doc-complete, feature
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86_64 Linux
: -- normal with 1 vote (vote)
: mozilla25
Assigned To: Sankha Narayan Guria [:sankha]
:
Mentors:
https://people.mozilla.com/~jorendorf...
Depends on:
Blocks: es6
  Show dependency treegraph
 
Reported: 2013-04-29 11:53 PDT by Tom Schuster [:evilpie]
Modified: 2014-02-24 10:58 PST (History)
12 users (show)
ryanvm: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
25+


Attachments
patch v1 (4.90 KB, patch)
2013-05-26 13:36 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review
patch v2 (7.40 KB, patch)
2013-06-10 08:55 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review
patch v3 (7.54 KB, patch)
2013-06-20 20:37 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review
patch v4 (8.47 KB, patch)
2013-07-01 21:22 PDT, Sankha Narayan Guria [:sankha]
evilpies: review+
Details | Diff | Splinter Review
patch v5 (9.49 KB, patch)
2013-07-16 10:28 PDT, Sankha Narayan Guria [:sankha]
evilpies: review+
Details | Diff | Splinter Review
final patch (9.50 KB, patch)
2013-07-18 08:11 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review
fixed patch (9.50 KB, patch)
2013-07-18 19:53 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review

Description Tom Schuster [:evilpie] 2013-04-29 11:53:48 PDT
This should be reasonably simple to do. I am going to evaluate if it makes sense to do this with self-hosting.
Comment 1 Sankha Narayan Guria [:sankha] 2013-05-26 13:36:52 PDT
Created attachment 754272 [details] [diff] [review]
patch v1
Comment 2 Till Schneidereit [:till] 2013-05-26 14:08:26 PDT
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.
Comment 3 Tom Schuster [:evilpie] 2013-05-26 14:13:24 PDT
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.
Comment 4 Rick Waldron [:rwaldron] 2013-05-26 14:59:43 PDT
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 :)
Comment 5 Rick Waldron [:rwaldron] 2013-05-26 15:09:00 PDT
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.
Comment 6 Sankha Narayan Guria [:sankha] 2013-05-26 20:00:45 PDT
(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. :)
Comment 7 Sankha Narayan Guria [:sankha] 2013-06-10 08:55:54 PDT
Created attachment 760433 [details] [diff] [review]
patch v2
Comment 8 Rick Waldron [:rwaldron] 2013-06-10 09:08:18 PDT
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?
Comment 9 Sankha Narayan Guria [:sankha] 2013-06-10 09:17:15 PDT
(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?
Comment 10 Rick Waldron [:rwaldron] 2013-06-10 10:43:30 PDT
Sankha, my mistake, I missed that. Sorry for the noise
Comment 11 Tom Schuster [:evilpie] 2013-06-12 07:56:31 PDT
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;
Comment 12 Rick Waldron [:rwaldron] 2013-06-12 09:32:32 PDT
> > +
> > +    /* 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.
Comment 13 Sankha Narayan Guria [:sankha] 2013-06-20 20:37:56 PDT
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.
Comment 14 Jason Orendorff [:jorendorff] 2013-06-22 23:55:44 PDT
>+    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.
Comment 15 Sankha Narayan Guria [:sankha] 2013-06-27 10:18:11 PDT
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;
Comment 16 Jason Orendorff [:jorendorff] 2013-06-27 19:15:38 PDT
Yes, that will work, though you need to rethrow err if it's not instanceof StopIteration.
Comment 17 Sankha Narayan Guria [:sankha] 2013-07-01 21:22:37 PDT
Created attachment 770013 [details] [diff] [review]
patch v4

This patch fixes the issue mentioned by jorendorff.
Comment 18 Tom Schuster [:evilpie] 2013-07-10 11:25:42 PDT
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
Comment 19 Tom Schuster [:evilpie] 2013-07-11 08:08:31 PDT
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, "...")
Comment 20 Sankha Narayan Guria [:sankha] 2013-07-16 10:28:14 PDT
Created attachment 776500 [details] [diff] [review]
patch v5
Comment 21 Tom Schuster [:evilpie] 2013-07-18 08:00:37 PDT
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?
Comment 22 Sankha Narayan Guria [:sankha] 2013-07-18 08:11:56 PDT
Created attachment 777817 [details] [diff] [review]
final patch

Oops! Tabs messed the spacing. This one is normal.
Comment 23 Ryan VanderMeulen [:RyanVM] 2013-07-18 08:26:06 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/c1025190b208
Comment 25 Sankha Narayan Guria [:sankha] 2013-07-18 19:53:42 PDT
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.
Comment 26 Ryan VanderMeulen [:RyanVM] 2013-07-19 07:35:35 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/657c02a2ff0f
Comment 27 Ryan VanderMeulen [:RyanVM] 2013-07-19 18:06:17 PDT
https://hg.mozilla.org/mozilla-central/rev/657c02a2ff0f
Comment 28 Alex Keybl [:akeybl] 2013-09-02 12:54:02 PDT
Adding the feature keyword so that this bug is properly picked up by the Release Tracking wiki page.
Comment 29 Paul Silaghi, QA [:pauly] 2013-09-04 08:11:08 PDT
Does this still need qa manual verification considering the existing automated tests ?
Comment 30 Jeff Walden [:Waldo] (remove +bmo to email) 2013-09-04 08:50:19 PDT
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.
Comment 31 Paul Silaghi, QA [:pauly] 2013-09-05 04:29:13 PDT
Thanks Jeff.
qa- based on comment 30.
Comment 32 Florian Scholz [:fscholz] (MDN) 2014-02-24 10:58:03 PST
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.

Note You need to log in before you can comment on or make changes to this bug.