Bug 33053 - JSON.stringify and JSON.parse implementations needlessly process properties in the prototype chain
Summary: JSON.stringify and JSON.parse implementations needlessly process properties i...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC Linux
: P2 Normal
Assignee: Kent Hansen
URL:
Keywords: ES5
Depends on:
Blocks:
 
Reported: 2009-12-30 06:58 PST by Kent Hansen
Modified: 2010-04-24 20:29 PDT (History)
6 users (show)

See Also:


Attachments
Proposed patch (1.81 KB, patch)
2009-12-30 07:05 PST, Kent Hansen
no flags Details | Formatted Diff | Diff
Revised patch (adds tests) (15.23 KB, patch)
2010-01-08 03:58 PST, Kent Hansen
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Kent Hansen 2009-12-30 06:58:15 PST
ES5 section 15.12.3, abstract Operation JO(value), step 6:  "Let K be an internal List of Strings consisting of the names of all the own properties of value [...]".
The JavaScriptCore implementation is calling JSObject::getPropertyNames(), whereas it could be calling JSObject::getOwnPropertyNames() instead.

Making this change does not affect the final output (the prototype-inherited properties are ignored anyways, since getOwnPropertySlot() subsequently returns false for them), but could make the implementation faster and use less memory.
Comment 1 Kent Hansen 2009-12-30 07:05:02 PST
Created attachment 45662 [details]
Proposed patch
Comment 2 WebKit Review Bot 2009-12-30 07:06:34 PST
style-queue ran check-webkit-style on attachment 45662 [details] without any errors.
Comment 3 Kent Hansen 2009-12-30 07:24:29 PST
Hmm, there should probably be a check to see if the OverridesGetPropertyNames flag is on, and in that case call getPropertyNames() as before.

It scares me a bit that there are now two virtual functions for getting property names. Can't we just make getPropertyNames() non-virtual now that there is getOwnPropertyNames()? Then rename the OverridesGetPropertyNames flag to OverridesGetOwnPropertyNames and update the bindings accordingly. I can do the refactoring if that sounds sensible.
Comment 4 Patrick Mueller 2009-12-30 08:47:47 PST
If you're doing some refactoring in this area, there may be some issues relating to bug 32242 - which needs to obtain the non-enumerable properties of an object.  I'm very unfamiliar with the JSC code, but attempted to look into this support anyway, and found I was going to have to hit a lot of code to go the first route I attempted (see the bug for details).  May well be it's a n00b issue for me, but if you're in the middle of property-retrieval refactorings, something to think about it.
Comment 5 Oliver Hunt 2009-12-30 22:56:50 PST
Comment on attachment 45662 [details]
Proposed patch

Can you determine what correct spec behaviour is given:
javascript:a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }}; alert(JSON.stringify(a))
Comment 6 Kent Hansen 2010-01-04 01:43:48 PST
(In reply to comment #5)
> (From update of attachment 45662 [details])
> Can you determine what correct spec behaviour is given:
> javascript:a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }};
> alert(JSON.stringify(a))

Thanks, that's a good test case to include.
Fairly sure it should be "{}", as per 15.12.3.JO.6. The prototype should not be consulted.
SpiderMonkey produces "{}" with both the built-in JSON.stringify and http://www.json.org/json2.js.
JSC produces "{"foo":"PASS"}" without the patch, "{}" with the patch.

JSC produces "{"foo":"PASS"}" even with json2.js. That code uses for..in in combination with hasOwnProperty() to only process "own" properties of the object. This means it _will_ see the property name "b" before hasOwnProperty() rejects it, but that shouldn't cause the _getter_ itself to be invoked. Uh-oh, maybe it's because the JSObject::hasOwnProperty() implementation calls getOwnPropertySlot()? It should probably be calling getOwnPropertyDescriptor(). I'll investigate and spin off a separate bug report.
Comment 7 Kent Hansen 2010-01-04 02:10:50 PST
(In reply to comment #6)

Sorry, I misread the test input. b of course _is_ an "own" property.
But yeah, what's happening is, "foo" will be the last item in the PropertyNameArray after the call to getPropertyNames(), even though the property is not an "own" property; after the call to the "b" getter, however, "foo" will be an own property, so it won't be rejected by the next call to hasOwnProperty(), hence the side-effect-generated "foo" property ends up in the output.
Again, coming back to the spec, the propertylist is initialized before the property values are stringified, so I believe properties added during the stringification should not be part of the output.
Comment 8 Kent Hansen 2010-01-04 02:33:56 PST
(In reply to comment #6)
> JSC produces "{"foo":"PASS"}" even with json2.js. That code uses for..in in
> combination with hasOwnProperty() to only process "own" properties of the
> object.

Looks like a bug in the for..in implementation.

SpiderMonkey:
js> a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }};
({get b () {this.foo = "PASS";}})
js> for (var p in a) print(p, a[p], a.hasOwnProperty(p))
b undefined true

JSC:
> a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }}
[object Object]
> for (var p in a) print(p, a[p], a.hasOwnProperty(p))
b undefined true
foo PASS true

ES5 section 12.6.4 states that "if new properties are added to the object being enumerated during enumeration, the newly added properties are guaranteed not to be visited in the active enumeration." So, the "foo" added by the b getter should not be included in the enumeration.
The reason the "foo" in the prototype should not be included is because of the "no-shadowing" rule, also given in section 12.6.4. I.e. it looks like even though newly added properties are not included in the enumeration, they do affect shadowing (at least if you take SpiderMonkey's implementation to be "correct").
Comment 9 Kent Hansen 2010-01-04 03:29:19 PST
(In reply to comment #8)
> Looks like a bug in the for..in implementation.
> 
> ES5 section 12.6.4 states that "if new properties are added to the object being
> enumerated during enumeration, the newly added properties are guaranteed not to
> be visited in the active enumeration."

Ugh, I was looking at a previous draft of the spec. In the final draft, the order of "guaranteed" and "not" has been swapped again, back to how it was in ES3 (makes a big difference, huh!):

http://www.mail-archive.com/es-discuss@mozilla.org/msg03118.html

So arguably json2.js is buggy because it relies on non-standard behavior. Ideally building the property list and stringifying the values should be decoupled, like it is in the ES5 algorithm. It'd be nice to have a test that sanctions this for-in behavior in JSC, though.
Comment 10 Kent Hansen 2010-01-04 10:58:20 PST
(In reply to comment #3)
> Hmm, there should probably be a check to see if the OverridesGetPropertyNames
> flag is on, and in that case call getPropertyNames() as before.
> 
> It scares me a bit that there are now two virtual functions for getting
> property names. Can't we just make getPropertyNames() non-virtual now that
> there is getOwnPropertyNames()? Then rename the OverridesGetPropertyNames flag
> to OverridesGetOwnPropertyNames and update the bindings accordingly. I can do
> the refactoring if that sounds sensible.

I created https://bugs.webkit.org/show_bug.cgi?id=33159 to get some feedback on this issue.
Comment 11 Kent Hansen 2010-01-04 11:09:27 PST
(In reply to comment #4)
> If you're doing some refactoring in this area, there may be some issues
> relating to bug 32242 - which needs to obtain the non-enumerable properties of
> an object.  I'm very unfamiliar with the JSC code, but attempted to look into
> this support anyway, and found I was going to have to hit a lot of code to go
> the first route I attempted (see the bug for details).  May well be it's a n00b
> issue for me, but if you're in the middle of property-retrieval refactorings,
> something to think about it.

Yeah, see Maciej's latest comment. I'm pursuing the "add extra flag argument to get(Own)PropertyNames" approach. It should be orthogonal to this change, though.
Comment 12 Kent Hansen 2010-01-08 03:58:33 PST
Created attachment 46130 [details]
Revised patch (adds tests)

I haven't added the checks for overridesGetPropertyNames() as I mentioned in comment #3, because that would still mean the behavior would be broken for classes that do override it (and there are quite a few). If a class reimplements getPropertyNames(), it should reimplement getOwnPropertyNames() too (i.e. the OverridesGetPropertyNames should imply that both of the property name functions are reimplemented). I can't think of a use case where it's meaningful to only reimplement getPropertyNames(), at least.

The difference between the result created by json2.js (subject to the for-in issue) and the native implementation has been marked as FAIL.
I'm not sure how to best proceed:
1) Acknowledge that the for-in behavior is a bug in JSC, and make it a blocker for this bug; or
2) Try to convince Crockford that json2.js should be updated to work around this behavior (i.e. detect for-in behavior for injected properties and fall back to a slower codepath); or
3) Accept that the native JSON and json2.js results will differ in this case.
Comment 13 Eric Seidel (no email) 2010-01-08 04:09:42 PST
Due to the two recent rollouts, I must as:   Did you run run-javascriptcore-tests with this patch?

I've filed bug 33376 about the commit-queue running run-javascriptcore-tests in the future.  (note, you're not the only one who has found this split confusing.  bug 5253 is one bug on the subject.)
Comment 14 Eric Seidel (no email) 2010-01-08 05:01:29 PST
the commit-queue is now running run-javascriptcore-tests before committing, so we won't have rollouts again like we had this evening. :)
Comment 15 Kent Hansen 2010-01-08 05:34:53 PST
(In reply to comment #14)
> the commit-queue is now running run-javascriptcore-tests before committing, so
> we won't have rollouts again like we had this evening. :)

Much appreciated!
Regarding the patch for this bug, I've run the javascriptcore tests after applying it, and there is no change.
JSON is a feature introduced in ES5 anyway, and JavaScriptCore/tests/mozilla doesn't yet contain the ecma_5/ directory that's present in mozilla trunk. Like we discussed online, I want to investigate bringing all tests under JavaScriptCore/tests/mozilla up-to-date.
Comment 16 Oliver Hunt 2010-01-10 19:45:16 PST
Sorry for delayed response, i've been on holiday, and am now back again
(In reply to comment #8)
> (In reply to comment #6)
> > JSC produces "{"foo":"PASS"}" even with json2.js. That code uses for..in in
> > combination with hasOwnProperty() to only process "own" properties of the
> > object.
> 
> Looks like a bug in the for..in implementation.
> 
> SpiderMonkey:
> js> a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }};
> ({get b () {this.foo = "PASS";}})
> js> for (var p in a) print(p, a[p], a.hasOwnProperty(p))
> b undefined true
> 
> JSC:
> > a={__proto__:{foo:"bar"}, get b() { this.foo="PASS"; }}
> [object Object]
> > for (var p in a) print(p, a[p], a.hasOwnProperty(p))
> b undefined true
> foo PASS true
> 
> ES5 section 12.6.4 states that "if new properties are added to the object being
> enumerated during enumeration, the newly added properties are guaranteed not to
> be visited in the active enumeration." So, the "foo" added by the b getter
> should not be included in the enumeration.

actually the foo added by the b getter should be included.  Evaluation of for-in is

for (i in o) if (o.hasOwnProperty(i)) log(o[i])

names = getPropertyNames(o) -> ["b" /* from o */, "foo" /* from o.__proto__ */]
for (_i = 0; _i < names.length; _i++) {
    var i = names[_i];
    if (o.hasOwnProperty(i))
    log(o[i])
}

The first iteration of this will be i == "b", o[i] then results in the o.b getter being called which then creates o.foo (no prototype involved in assignment), in the next loop foo will now be directly on the object so will be visited.  I am unsure why it is not working in firefox
Comment 17 Kent Hansen 2010-01-12 01:46:31 PST
(In reply to comment #16)
> actually the foo added by the b getter should be included.  Evaluation of
> for-in is
> 
> for (i in o) if (o.hasOwnProperty(i)) log(o[i])
> 
> names = getPropertyNames(o) -> ["b" /* from o */, "foo" /* from o.__proto__ */]
> for (_i = 0; _i < names.length; _i++) {
>     var i = names[_i];
>     if (o.hasOwnProperty(i))
>     log(o[i])
> }
> 
> The first iteration of this will be i == "b", o[i] then results in the o.b
> getter being called which then creates o.foo (no prototype involved in
> assignment), in the next loop foo will now be directly on the object so will be
> visited.  I am unsure why it is not working in firefox

It's because of the no-shadowing rule that I mentioned.
From ES5 section 12.6.4: "Enumerating the properties of an object includes enumerating properties of its prototype, and the prototype of
the prototype, and so on, recursively; but a property of a prototype is not enumerated if it is “shadowed”
because some previous object in the prototype chain has a property with the same name."

Pseudo-code execution:
1. Get own properties of o -> ["b"]
2. Enumerate "b" (one pass through the for-in body); as a side-effect, this will create "foo" on o
3. Recurse: Get own properties of o.__proto__ -> ["foo"].
4. Check if some previous object in the prototype chain has the property "foo" -> yes, o has a property called "foo", so "foo" is not visited. (The fact that "foo" has not actually been enumerated before does not matter.)
Comment 18 Oliver Hunt 2010-01-12 10:14:34 PST
(In reply to comment #17)
> (In reply to comment #16)
> > actually the foo added by the b getter should be included.  Evaluation of
> > for-in is
> > 
> > for (i in o) if (o.hasOwnProperty(i)) log(o[i])
> > 
> > names = getPropertyNames(o) -> ["b" /* from o */, "foo" /* from o.__proto__ */]
> > for (_i = 0; _i < names.length; _i++) {
> >     var i = names[_i];
> >     if (o.hasOwnProperty(i))
> >     log(o[i])
> > }
> > 
> > The first iteration of this will be i == "b", o[i] then results in the o.b
> > getter being called which then creates o.foo (no prototype involved in
> > assignment), in the next loop foo will now be directly on the object so will be
> > visited.  I am unsure why it is not working in firefox
> 
> It's because of the no-shadowing rule that I mentioned.
> From ES5 section 12.6.4: "Enumerating the properties of an object includes
> enumerating properties of its prototype, and the prototype of
> the prototype, and so on, recursively; but a property of a prototype is not
> enumerated if it is “shadowed”
> because some previous object in the prototype chain has a property with the
> same name."
> 
> Pseudo-code execution:
> 1. Get own properties of o -> ["b"]
> 2. Enumerate "b" (one pass through the for-in body); as a side-effect, this
> will create "foo" on o
> 3. Recurse: Get own properties of o.__proto__ -> ["foo"].
> 4. Check if some previous object in the prototype chain has the property "foo"
> -> yes, o has a property called "foo", so "foo" is not visited. (The fact that
> "foo" has not actually been enumerated before does not matter.)

No, you're misunderstanding the purpose of that rule -- it prevents you from visiting the same property name multiple times, the algorithm is
1. names = getPropertyNames(o);
2. for each name in names
    i. if !o.hasProperty(name) goto step 2
    ii. do loop body

getPropertyNames(o)
1. names = [];
2. while (o)
     i. temp = getOwnPropertyNames(o)
     ii. for each name in temp
         a. if names.indexOf(name) != -1 goto 2.ii
         b. names.push(name)
3. return names

Eg. the list of property names for an object is a uniqued ordered list
Comment 19 Kent Hansen 2010-01-13 01:25:32 PST
(In reply to comment #18)
> No, you're misunderstanding the purpose of that rule -- it prevents you from
> visiting the same property name multiple times, the algorithm is
> 1. names = getPropertyNames(o);
> 2. for each name in names
>     i. if !o.hasProperty(name) goto step 2
>     ii. do loop body
> 
> getPropertyNames(o)
> 1. names = [];
> 2. while (o)
>      i. temp = getOwnPropertyNames(o)
>      ii. for each name in temp
>          a. if names.indexOf(name) != -1 goto 2.ii
>          b. names.push(name)
> 3. return names
> 
> Eg. the list of property names for an object is a uniqued ordered list

Where does that algorithm come from? I'm just following the ECMA-262 wording. Some more interesting cases:

Case 1: try swapping out the __proto__ property while o is being enumerated.

SpiderMonkey:
js> o = { a : 1, __proto__: { b : 2 } };
({a:1})
js> for (var p in o) { if (p == "a") o.__proto__ = { c : 3 }; print(p); }
a
c

JSC:
> o = { a : 1, __proto__: { b : 2 } };
[object Object]
> for (var p in o) { if (p == "a") o.__proto__ = { c : 3 }; print(p); }
a

Case 2: add a property to o.__proto__ while o is being enumerated.

SpiderMonkey:
js> o = { a : 1, __proto__: {} };
({a:1})
js> for (var p in o) { if (p == "a") { o.__proto__.b = 2; }; print(p); }
a
b

JSC:
> o = { a : 1, __proto__: { } };
[object Object]
> for (var p in o) { if (p == "a") { o.__proto__.b = 2; }; print(p); }
a

Case 3: delete a property on o and add a property with the same name on o.__proto__ before o.__proto__ is being enumerated.

SpiderMonkey:
js> o = { a : 1, __proto__: { b : 2 } };
({a:1})
js> for (var p in o) { if ((p == "a") && o.hasOwnProperty("a")) { delete o.a; o.__proto__.a = 3; }; print(p); }
a
b
a

JSC:
> o = { a : 1, __proto__: { b : 2 } };
[object Object]
> for (var p in o) { if ((p == "a") && o.hasOwnProperty("a")) { delete o.a; o.__proto__.a = 3; }; print(p); }
a
b

Again, I find the SpiderMonkey behavior fits with the ECMA-262 wording in all three cases. So maybe I'm misunderstanding the _purpose_ of the rule, but the question is whether it should be implemented as it's currently worded.
I'll probably fire off a mail to es-discuss@ about this, once I've been able to check the behavior on IE8. (Attempt on Opera 10.10 was futile because it doesn't seem to support the __proto__ extension.)
Comment 20 Oliver Hunt 2010-01-13 22:18:33 PST
Comment on attachment 46130 [details]
Revised patch (adds tests)

Okay, i think the for..in enumeration issue can be considered separate from this.  So r=me
Comment 21 WebKit Commit Bot 2010-01-13 22:37:20 PST
Comment on attachment 46130 [details]
Revised patch (adds tests)

Clearing flags on attachment: 46130

Committed r53239: <http://trac.webkit.org/changeset/53239>
Comment 22 WebKit Commit Bot 2010-01-13 22:37:27 PST
All reviewed patches have been landed.  Closing bug.