Closed Bug 1257779 Opened 8 years ago Closed 8 years ago

Scripted proxies' [[OwnPropertyKeys]] should be linear, not (potentially) quadratic

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla48
Tracking Status
firefox48 --- fixed

People

(Reporter: Waldo, Assigned: Waldo)

References

Details

Attachments

(2 files)

There's no good reason to have doubly-nested loops over two vectors, when the inner loop absolutely can just be a set-contains check.
Attached patch TestSplinter Review
The gist of the spec algorithm for how [[OwnPropertyKeys]] works on a scripted direct proxy is so:

* call the trap function on the handler, passing the target, to get an array of properties
* convert that array of properties to a |trapResult| internal list
* go through |trapResult| and, using [[GetOwnProperty]], create two lists of configurable/nonconfigurable properties
* because the target is extensible, and nonconfigurable properties were found -- don't exit early
* copy |trapResult| into a new |uncheckedResultKeys| structure
* go through the list of nonconfigurables and remove each one from |uncheckedResultKeys|; if an entry isn't found, there was a dup, so throw a TypeError
* do the same for configurables

If |uncheckedResultKeys| is an array, copied from the |trapResult| array, then we have nested loops.  If the last two steps find their property names in reverse order in |uncheckedResultKeys| -- as the previous test triggers -- we have quadratic behavior.  The current implementation has this defect.

In my unmodified debug build, this test times out at 2m30s.  In a debug build with the next patch applied, the test runs in 7s.
Attachment #8732067 - Flags: review?(jcoppeard)
Attached patch PatchSplinter Review
Fairly simple, just a couple wrinkles.  Nobody's had a Rooted<GCHashSet> and wanted to remove from it, so I had to update for that.  The DefaultHasher addition was necessary to avoid self-immolation, if I got the default DefaultHasher template.  (HashSet.h and Id.h are logically distinct, IMO, so it's not right to have Id.h include HashSet.h.)
Attachment #8732068 - Flags: review?(jcoppeard)
Comment on attachment 8732068 [details] [diff] [review]
Patch

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

This all looks good to me.
Attachment #8732068 - Flags: review?(jcoppeard) → review+
Comment on attachment 8732067 [details] [diff] [review]
Test

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

::: js/src/tests/ecma_6/Proxy/ownkeys-linear.js
@@ +3,5 @@
> + * http://creativecommons.org/licenses/publicdomain/
> + */
> +
> +var gTestfile = 'ownkeys-linear.js';
> +var BUGNUMBER = 999999;

Needs updating with bug number.
Attachment #8732067 - Flags: review?(jcoppeard) → review+
I believe this patch is incorrect. Consider this:

var o = Object.preventExtensions({a: 1});
var p = new Proxy(o, {
    ownKeys: function() {
        return ["a", "a"]
    }
});
console.log(Reflect.ownKeys(p));

We end up in step 19. and are supposed to remove one occurrence of "a", but this leaves the other "a" in uncheckedResultKeys. The set does not maintain this property. So now uncheckedResultKeys is not empty in step 20.
https://github.com/tc39/ecma262/issues/461 has a discussion about this as well as considerations about disallowing duplicate keys.
(In reply to Tom Schuster [:evilpie] from comment #5)
Huh, well I did not think of that!

From the discussion it looks the spec will be updated to match the behaviour of this patch though, given an extra check for duplicate entries.
(In reply to Jon Coppeard (:jonco) from comment #3)
Oh, it looks like we have JsidHasher in jsatom.h already.

Waldo, how about removing that now you're adding a default hasher for jsids?
(In reply to Jon Coppeard (:jonco) from comment #8)
> Waldo, how about removing that now you're adding a default hasher for jsids?

Turns out this was necessary to do bug 1257979 at all, so I did this in that bug's push earlier.
https://hg.mozilla.org/mozilla-central/rev/afea56998c75
https://hg.mozilla.org/mozilla-central/rev/b0f1eb9c1f38
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
You need to log in before you can comment on or make changes to this bug.