Closed Bug 866847 Opened 11 years ago Closed 11 years ago

Implement Map#forEach and Set#forEach

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla25
Tracking Status
relnote-firefox --- 25+

People

(Reporter: evilpie, Assigned: sankha)

References

(Blocks 1 open bug, )

Details

(Keywords: dev-doc-complete, feature, Whiteboard: [qa-][DocArea=JS])

Attachments

(1 file, 6 obsolete files)

This should be reasonably simple to do. I am going to evaluate if it makes sense to do this with self-hosting.
Attached patch patch v1 (obsolete) — Splinter Review
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)
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.
(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. :)
Attached patch patch v2 (obsolete) — Splinter Review
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?
(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
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.
Attached patch patch v3 (obsolete) — Splinter Review
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.
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)
Attached patch patch v4 (obsolete) — Splinter Review
This patch fixes the issue mentioned by jorendorff.
Attachment #765759 - Attachment is obsolete: true
Attachment #765759 - Flags: review?(evilpies)
Attachment #770013 - Flags: review?(evilpies)
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 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+
Attached patch patch v5 (obsolete) — Splinter Review
Attachment #770013 - Attachment is obsolete: true
Attachment #776500 - Flags: review?(evilpies)
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+
Attached patch final patch (obsolete) — Splinter Review
Oops! Tabs messed the spacing. This one is normal.
Attachment #776500 - Attachment is obsolete: true
Keywords: checkin-needed
Attached patch fixed patchSplinter Review
Fixed the patch and pushed to try: https://tbpl.mozilla.org/?tree=Try&rev=c2ba402cf681

Try is green.
Attachment #777817 - Attachment is obsolete: true
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/657c02a2ff0f
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla25
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-]
Flags: needinfo?(sankha93)
Whiteboard: [qa-] → [qa-][DocArea=JS]
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: