Finiteness of object properties set
I agree that the spec should clearly state that a non-extensible object has a finite collection of own properties. Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return?
On Tue, Sep 6, 2011 at 8:00 AM, David Bruant <david.bruant at labri.fr> wrote:
Hi,
There is a current expectation of objects being a /finite/ collection of properties, but I don't see this information written anywhere. ES5.1 - 4.3.3 says: "An object is a collection of properties..." "Collection" is nowhere defined in the spec. The Wikipedia page does not state clearly anything about collection finiteness.
I have re-read very carefully the ES5.1 invariants regarding non-extensible objects and they do not prevent (host) objects with an infinite set of properties. More precisely, calls to [[GetOwnProperty]] on non-extensible objects are not forbidden to describe as existent, properties which have not been observed as non-existent (which leaves (infinite) room since within in a finite time, only a finite set of properties can be observed as non-existent).
The current design of the fix trap explicitely asks for an regular object (which has a finite set of properties). The same applies to the current design of non-extensible proxies which has an internal set of properties (finite in current Tom's implementation).
Should the spec clearly state something about object property finiteness? (I have some crazy ideas with the fix trap returning RegExps, there is still time to stop me :-p )
PLEASE STOP ;)
Le 06/09/2011 17:59, Mark S. Miller a écrit :
I agree that the spec should clearly state that a non-extensible object has a finite collection of own properties. Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return?
And what about for-in loops? :-p If this is really considered, the problem to solve is to express an infinite set with a finite representation. RegExps may be a solution. One big question is on RegExp expressivity: Can any infinite string set be expressed with (a finite number of) JS RegExps? I have to admit that i know ECMAScript pretty well expect RegExp i have never taken the time to investigate, so i have no idea of the answer to this question, not even an intuition.
Alternatively, extensible objects could be stated as having a finite set of properties. I have no knowledge of host objects with an infinite property set and everyone's intuition falls under the idea that objects are a finite collection of properties. Saying it explicitely would prevent attempts from ES implementors to have host objects with infinite property set. It would also allow to continue proxies with the current design tracks (which currently prevent infinite property sets).
2011/9/7 David Bruant <david.bruant at labri.fr>
Le 06/09/2011 17:59, Mark S. Miller a écrit :
I agree that the spec should clearly state that a non-extensible object
has a finite collection of own properties. Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return?
And what about for-in loops? :-p
It's always possible to break/return early, no? Didn't iterators/generators already cross this bridge? An iterator could iterate over an infinite stream of values.
If this is really considered, the problem to solve is to express an infinite set with a finite representation. RegExps may be a solution. One big question is on RegExp expressivity: Can any infinite string set be expressed with (a finite number of) JS RegExps? I have to admit that i know ECMAScript pretty well expect RegExp i have never taken the time to investigate, so i have no idea of the answer to this question, not even an intuition.
I have no idea where you are taking this, but trying to map infinite sets of properties onto regular expressions seems like a horrible thing to do :-)
Alternatively, extensible objects could be stated as having a finite set of properties. I have no knowledge of host objects with an infinite property set and everyone's intuition falls under the idea that objects are a finite collection of properties. Saying it explicitely would prevent attempts from ES implementors to have host objects with infinite property set. It would also allow to continue proxies with the current design tracks (which currently prevent infinite property sets).
I see no problem with current proxies emulating an extensible object with an infinite set of properties.
Object.getOwnPropertyNames could return [], claiming that all of these properties were inherited. Even with invariant enforcement, the FixedHandler does not enforce that getOwnPropertyNames returns all non-configurable own properties observed thus far.
If these virtual properties are all marked non-enumerable, the "enumerate" and "keys" trap can return [] without lying.
Regarding invariant enforcement: if the generated properties are marked non-configurable, the FixedHandler would require an unbounded amount of storage, so that's something to consider.
But so as long as we're sticking to emulating an infinite series of non-configurable properties on extensible objects, I see no show-stopping issues.
On Wed, Sep 7, 2011 at 2:07 PM, David Bruant <david.bruant at labri.fr> wrote:
If this is really considered, the problem to solve is to express an infinite set with a finite representation. RegExps may be a solution. One big question is on RegExp expressivity: Can any infinite string set be expressed with (a finite number of) JS RegExps?
Nope. Any finite set of RegExps can be combined into a single RegExp, so the language they recognize is still regular (or what the class of languages recognized by JS RegExps really is, since it's bigger than the regular languages, but doesn't include all context free langauges).
As for proxies with arbitrarily many properties, I don't think there's a way to prevent it (it's the catch-all effect). The problem is for the proxy creator to decide what to return for keys().
Le 07/09/2011 15:29, Lasse Reichstein a écrit :
On Wed, Sep 7, 2011 at 2:07 PM, David Bruant <david.bruant at labri.fr <mailto:david.bruant at labri.fr>> wrote:
If this is really considered, the problem to solve is to express an infinite set with a finite representation. RegExps may be a solution. One big question is on RegExp expressivity: Can any infinite string set be expressed with (a finite number of) JS RegExps?Nope. Any finite set of RegExps can be combined into a single RegExp, so the language they recognize is still regular (or what the class of languages recognized by JS RegExps really is, since it's bigger than the regular languages, but doesn't include all context free langauges).
Very true. I had a doubt on whether RegExp were purely limited to regular languages. I have never really taken the time to check whether RegExps were just providing sugar for regular languages matching or if they were going further than that. But hopefully, you're right.
As for proxies with arbitrarily many properties, I don't think there's a way to prevent it (it's the catch-all effect).
Extensible proxies are not a problem. Non-extensible proxies are if the specs asks for non-extensible objects (then proxies) to have a finite set of properties. Current design and prototype implementation [1] seem to go in the direction of non-extensible proxies having a finite set of properties even though still "catching all". See L.262-273 where is defined this.fixedProps which is a regular object (finite number of properties).
David
[1] code.google.com/p/es-lab/source/browse/trunk/src/proxies/FixedTrappingProxy.js
2011/9/7 David Bruant <david.bruant at labri.fr>
** Extensible proxies are not a problem. Non-extensible proxies are if the specs asks for non-extensible objects (then proxies) to have a finite set of properties.
Where is the problem? In my FixedHandler experiment, non-extensible proxies are also required to have a finite set of properties.
From your message, I understand that you see it as a problem that the
FixedHandler makes use of a plain ES5 (thus finite) object to store the non-configurable properties. While the object is finite, as long as it's extensible, it can grow without bounds. Of course there is a space leak issue here, as I mentioned earlier, but is there some deeper problem I'm missing?
Le 07/09/2011 15:59, Tom Van Cutsem a écrit :
2011/9/7 David Bruant <david.bruant at labri.fr <mailto:david.bruant at labri.fr>>
Extensible proxies are not a problem. Non-extensible proxies are if the specs asks for non-extensible objects (then proxies) to have a finite set of properties.Where is the problem?
There is none, sorry for the confusion. I was answering to Lasse saying "I don't think there's a way to prevent it [proxies emulating objects with infinite properties] (it's the catch-all effect)". There is no reason to prevent it in the extensible case. There is in the non-extensible one and your current prototype implementation prevents non-extensible objects with infinite properties by design which I see as a good thing.
Sorry for the confusion.
On Sep 7, 2011, at 6:12 AM, Tom Van Cutsem wrote:
2011/9/7 David Bruant <david.bruant at labri.fr> Le 06/09/2011 17:59, Mark S. Miller a écrit :
I agree that the spec should clearly state that a non-extensible object has a finite collection of own properties. Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return? And what about for-in loops? :-p
It's always possible to break/return early, no? Didn't iterators/generators already cross this bridge? An iterator could iterate over an infinite stream of values.
Indeed the derived iterate trap supports infinite objects -- this was a use-case Waldemar raised this at TC39 meetings last year, IIRC at the November 2010 meeting (notes posted to es-discuss).
See also
harmony:iterators#iteration_via_standard_private_name, harmony:iterators#iteration_via_proxies
2011/9/7 Mark S. Miller <erights at google.com>
On Wed, Sep 7, 2011 at 6:12 AM, Tom Van Cutsem <tomvc.be at gmail.com> wrote:
But so as long as we're sticking to emulating an infinite series of non-configurable properties on extensible objects, I see no show-stopping issues.
...infinite series of configurable properties..., I believe you meant.
Yes indeed, thanks.
On Tue, Sep 6, 2011 at 10:59 AM, Mark S. Miller <erights at google.com> wrote:
[...] Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return?
Hmm. I wonder if this is a problem even for finite objects.
js> var x = [];
js> x = Object.getOwnPropertyNames(x); ["length"] js> x = Object.getOwnPropertyNames(x); ["length", "0"] js> x = Object.getOwnPropertyNames(x); ["length", "0", "1"] js> x = Object.getOwnPropertyNames(x); ["length", "0", "1", "2"]
You see where this is going. There's a finite number of array indexes, and the array .length property is always less than 2^32.
Of course on current machines we will eventually run out of time or memory, but what is supposed to happen when we cross 2^32?
Le 19/09/2011 09:32, Jason Orendorff a écrit :
On Tue, Sep 6, 2011 at 10:59 AM, Mark S. Miller<erights at google.com> wrote:
[...] Regarding infinite extensible objects, the only problem I see off the top of my head is: What would Object.getOwnPropertyNames return? Hmm. I wonder if this is a problem even for finite objects.
I'm not sure it's the exact same problem, but it's an interesting question.
js> var x = []; js> x = Object.getOwnPropertyNames(x); ["length"] js> x = Object.getOwnPropertyNames(x); ["length", "0"] js> x = Object.getOwnPropertyNames(x); ["length", "0", "1"] js> x = Object.getOwnPropertyNames(x); ["length", "0", "1", "2"]
You see where this is going. There's a finite number of array indexes, and the array .length property is always less than 2^32.
Of course on current machines we will eventually run out of time or memory, but what is supposed to happen when we cross 2^32?
Object.getOwnPropertyDescriptor creates a native array and, for each own property, it calls [[DefineOwnProperty]] on this array for an index n (ES5.1 - 15.2.3.4 step 4.b) This internal method is special for arrays (ES5.1 - 15.4.5.1). When crossing 2³², ToString(n) is not an array index anymore, so the property is added (as per step 5), but the length property gets stuck to its maximum (2³²). Since the property is added, continuing results in an infinite loop, the length property remains at 2³².
On Sep 19, 2011, at 4:04 AM, David Bruant wrote:
Object.getOwnPropertyDescriptor creates a native array and, for each own property, it calls [[DefineOwnProperty]] on this array for an index n (ES5.1 - 15.2.3.4 step 4.b) This internal method is special for arrays (ES5.1 - 15.4.5.1). When crossing 2³², ToString(n) is not an array index anymore, so the property is added (as per step 5), but the length property gets stuck to its maximum (2³²). Since the property is added, continuing results in an infinite loop, the length property remains at 2³².
Nit-pick: length stops at (2³² - 1). Maximum value of the corresponding index is therefore (2³² - 2).
I wish we hadn't codified this in ES1. Oh well.
There is a current expectation of objects being a /finite/ collection of properties, but I don't see this information written anywhere. ES5.1 - 4.3.3 says: "An object is a collection of properties..." "Collection" is nowhere defined in the spec. The Wikipedia page does not state clearly anything about collection finiteness.
I have re-read very carefully the ES5.1 invariants regarding non-extensible objects and they do not prevent (host) objects with an infinite set of properties. More precisely, calls to [[GetOwnProperty]] on non-extensible objects are not forbidden to describe as existent, properties which have not been observed as non-existent (which leaves (infinite) room since within in a finite time, only a finite set of properties can be observed as non-existent).
The current design of the fix trap explicitely asks for an regular object (which has a finite set of properties). The same applies to the current design of non-extensible proxies which has an internal set of properties (finite in current Tom's implementation).
Should the spec clearly state something about object property finiteness? (I have some crazy ideas with the fix trap returning RegExps, there is still time to stop me :-p )