6.1.7.3 Invariants of the Essential Internal Methods, [[GetPrototypeOf]] ( ):
> An object’s prototype chain must have finite length [...]
This assumption does not hold for proxy objects.
Example 1:
var o = {}, p = new Proxy(o, {});
Object.setPrototypeOf(o, p);
Object.getPrototypeOf(p) === p; // yields true
Example 2:
function infiniteProxy() {
return new Proxy({}, {
getPrototypeOf() {
return new infiniteProxy();
}
});
}
Good catch.
I would be OK with dropping the invariant from the spec. It’s not one we can easily enforce.
Moreover, I don’t see what extra risks we take by removing the invariant. I don’t think implementations deliberately climb prototype chains to optimize things, or if they do, they probably already have limits on how high they want to climb. Even without proxies one can easily construct extremely deep prototype chains.
Finally, with setPrototypeOf in the spec it even becomes possible to define cyclic prototype chains, as far as I can see.
(In reply to comment #1)
>
>
> Finally, with setPrototypeOf in the spec it even becomes possible to define
> cyclic prototype chains, as far as I can see.
Not for prototype chains consisting only of ordinary objects. See step 6, http://people.mozilla.org/~jorendorff/es6-draft.html#sec-ordinary-object-internal-methods-and-internal-slots-setprototypeof-v
But as soon as an exotic object is involved, the reliability of the check can be compromised by an exotic [[GetPrototypeOf]].
About the only fix I can imagine would be requiring that an observed [[GetPrototypeOf]] result for an object must not change unless there is an intervening [[SetPrototypeOf]] call for the same object.
Probably the real concern here is that a circular prototype chain would throw many implementation into a deep and perhaps non-interruptible infinite loop.
Allen
(In reply to comment #2)
> Probably the real concern here is that a circular prototype chain would throw
> many implementation into a deep and perhaps non-interruptible infinite loop.
Possibly, but when dealing with proxies, virtually any operation called upon a proxy can go into an infinite loop.
Also note that if a proxy is found in a prototype-chain during property lookup, the lookup stops right there and should call the proxy's "get" trap. I don't think an implementation should ever call [[GetPrototypeOf]] on a proxy during critical operations such as property lookup. Indeed, we redesigned the entire [[Get]] and [[Set]] algorithms so that this would no longer be necessary.
Nevertheless, it would be good to get some advice from implementors on the importance of this invariant.
(In reply to comment #3)
> (In reply to comment #2)
> > Probably the real concern here is that a circular prototype chain would throw
> > many implementation into a deep and perhaps non-interruptible infinite loop.
>
> Possibly, but when dealing with proxies, virtually any operation called upon a
> proxy can go into an infinite loop.
I'm really only concerned about loops that don't have call backs into JS code.
>
> Also note that if a proxy is found in a prototype-chain during property lookup,
> the lookup stops right there and should call the proxy's "get" trap.
Right! So, no worry here!
> I don't
> think an implementation should ever call [[GetPrototypeOf]] on a proxy during
> critical operations such as property lookup. Indeed, we redesigned the entire
> [[Get]] and [[Set]] algorithms so that this would no longer be necessary.
How do [[Get]]/[[Set]] help. They are also defined to perform [[GetPrototypeOf]] calls to walk the proto chain.
(In reply to comment #4)
> How do [[Get]]/[[Set]] help. They are also defined to perform
> [[GetPrototypeOf]] calls to walk the proto chain.
Only for non-exotic objects. [[Get]] calls [[GetPrototypeOf]] to retrieve the prototype, then does a tail-call to prototype.[[Get]]. If the prototype is a proxy, the proxy takes over from there, and the external prototype-climbing stops. Same for [[Set]], [[HasProperty]] and [[Enumerate]].
I searched the spec for calls to [[GetPrototypeOf]] that climb the proto chain. Seems like these are the external loops you're worried about:
- 9.1.2 [[SetPrototypeOf]] climbs the proto chain, to check for non-circularity
- 7.3.15 OrdinaryHasInstance (triggered by instanceof operator and Function.prototype[@@hasInstance] )
- 19.1.3.3 Object.prototype.isPrototypeOf
Here's a test case to show how to construct a circular prototype chain which involves only ordinary objects. The proxy is only needed for the initial set-up:
---
var obj1 = {};
var obj2 = {};
var obj3 = {};
var count = 0;
var p3 = new Proxy(obj3, {
getPrototypeOf(t) {
print("getPrototypeOf called");
if (count++ === 1) {
Object.setPrototypeOf(obj2, obj1);
}
return Reflect.getPrototypeOf(t);
}
});
Object.setPrototypeOf(obj2, p3);
Object.setPrototypeOf(obj1, obj2);
print(`Object.getPrototypeOf(obj1) === obj2? ${Object.getPrototypeOf(obj1) === obj2}`);
print(`Object.getPrototypeOf(obj2) === obj1? ${Object.getPrototypeOf(obj2) === obj1}`);
---
Fixed in rev30 editor's draft.
Removed the Chapter 6 invariant for [[GetPrototypeOf]] regarding infinite legth prototype chains. Replaced it with a NOTE pointing out the possibility
I'm sorry, I have to push back on this resolution. We are not going to allow for the possibility of cyclic prototype chains between ordinary objects in V8. If the spec actually prescribes that Andre's example succeeds (I haven't checked) then the spec needs fixing.
(In reply to Andreas Rossberg from comment #8)
> I'm sorry, I have to push back on this resolution. We are not going to allow
> for the possibility of cyclic prototype chains between ordinary objects in
> V8. If the spec actually prescribes that Andre's example succeeds (I haven't
> checked) then the spec needs fixing.
One idea that did come up in discussion is a structural invariant, but without a corresponding behavioral invariant. The structural invariant is in terms of a proxy's effective instantaneous [[Prototype]] being its target's [[Prototype]] at the same moment. The invariant is that you can't have a structural cycle at any moment.
IIRC, we decided to drop this because it did not prevent a behavioral infinite cycle. But perhaps it is useful anyway, in order to account for the plain-object constraint in a proxy compat manner.
(In reply to Andreas Rossberg from comment #8)
> I'm sorry, I have to push back on this resolution. We are not going to allow
> for the possibility of cyclic prototype chains between ordinary objects in
> V8. If the spec actually prescribes that Andre's example succeeds (I haven't
> checked) then the spec needs fixing.
Then please propose a spec. level fix. How do you currently disallow this?
I can imagine doing so via a check in ordinary object [[SetPrototypeOf]] but that would be check that is specific to it and not an invariant that applies to all implementations of [[SetPrototypeOf]].
(In reply to Allen Wirfs-Brock from comment #10)
> (In reply to Andreas Rossberg from comment #8)
> > I'm sorry, I have to push back on this resolution. We are not going to allow
> > for the possibility of cyclic prototype chains between ordinary objects in
> > V8. If the spec actually prescribes that Andre's example succeeds (I haven't
> > checked) then the spec needs fixing.
>
> Then please propose a spec. level fix. How do you currently disallow this?
>
> I can imagine doing so via a check in ordinary object [[SetPrototypeOf]] but
> that would be check that is specific to it and not an invariant that applies
> to all implementations of [[SetPrototypeOf]].
For the structural invariant, the strange part is that the instantaneous cycle check needs to look at imputed structure without causing traps to user code. For this purpose alone, it would reach through a proxy to its target without trapping to the handler.
(In reply to Allen Wirfs-Brock from comment #10)
> (In reply to Andreas Rossberg from comment #8)
> > I'm sorry, I have to push back on this resolution. We are not going to allow
> > for the possibility of cyclic prototype chains between ordinary objects in
> > V8. If the spec actually prescribes that Andre's example succeeds (I haven't
> > checked) then the spec needs fixing.
>
> Then please propose a spec. level fix. How do you currently disallow this?
>
> I can imagine doing so via a check in ordinary object [[SetPrototypeOf]] but
> that would be check that is specific to it and not an invariant that applies
> to all implementations of [[SetPrototypeOf]].
We don't currently have to do anything, because we still implement the old proxy proposal that couldn't intercept prototype access.
I see three possibilities:
1. We drop mutable prototypes from the spec. Then implementations can continue to support it as a legacy feature in whatever hacky way they see fit, even if it doesn't work with proxies.
2. We at least remove the ability for proxies to intercept prototype access.
3. The champions for including mutable prototypes find a better way for fixing its semantics.
I'm sorry if this sounds unconstructive, but I'm actually somewhat serious here. I only very reluctantly accepted the idea of blessing prototype mutation because I was willing to believe that it can't be worse than what we already implement. Now, cyclic prototype chains is much worse, and I would never have agreed to that. I suggest that the burden for coming up with a fix now lies with the champions (if they still champion it under this changed premise).
The example of Comment #6 works as follows: While the prototype chain of obj2 is visited in order to check for potential cycle, the proxy p3 alters the prototype of an already visited object, making the test for prototype cycle unreliable. A standard solution to that sort of problem is to use locks. In our case:
* While a prototype chain is visited in the process of checking for potential cycle, a temporary lock is put on every visited object. These locks are released at the end of the algorithm.
* Any attempt to alter the prototype on a locked object shall fail.
That will at least prevent prototype cycles for prototype chains consisting only of ordinary objects (or, more generally, of objects verifying the invariant mentioned in Comment #2).
(In reply to Andreas Rossberg from comment #12)
> (In reply to Allen Wirfs-Brock from comment #10)
> > (In reply to Andreas Rossberg from comment #8)
> > > I'm sorry, I have to push back on this resolution. We are not going to allow
> > > for the possibility of cyclic prototype chains between ordinary objects in
> > > V8. If the spec actually prescribes that Andre's example succeeds (I haven't
> > > checked) then the spec needs fixing.
> >
> > Then please propose a spec. level fix. How do you currently disallow this?
> >
> > I can imagine doing so via a check in ordinary object [[SetPrototypeOf]] but
> > that would be check that is specific to it and not an invariant that applies
> > to all implementations of [[SetPrototypeOf]].
>
> We don't currently have to do anything, because we still implement the old
> proxy proposal that couldn't intercept prototype access.
>
> I see three possibilities:
>
> 1. We drop mutable prototypes from the spec. Then implementations can
> continue to support it as a legacy feature in whatever hacky way they see
> fit, even if it doesn't work with proxies.
No. If it is everywhere, then it is part of the de facto std anyway and membranes must support it. Therefore proxies must.
>
> 2. We at least remove the ability for proxies to intercept prototype access.
No. Makes it impossible to build a membrane.
>
> 3. The champions for including mutable prototypes find a better way for
> fixing its semantics.
See comments #9 and #11. Did you somehow miss these?
>
> I'm sorry if this sounds unconstructive, but I'm actually somewhat serious
> here. I only very reluctantly accepted the idea of blessing prototype
> mutation because I was willing to believe that it can't be worse than what
> we already implement. Now, cyclic prototype chains is much worse, and I
> would never have agreed to that. I suggest that the burden for coming up
> with a fix now lies with the champions (if they still champion it under this
> changed premise).
(In reply to Andreas Rossberg from comment #12)
>
>
> I see three possibilities:
>
> 1. We drop mutable prototypes from the spec. Then implementations can
> continue to support it as a legacy feature in whatever hacky way they see
> fit, even if it doesn't work with proxies.
>
One is never going to fly. Mutable prototypes are a reality and the job of a standard is to ensure that such realities have a good specification.
> 2. We at least remove the ability for proxies to intercept prototype access.
>
Too big a change and it significantly reduces what can be expressed using proxies.
> 3. The champions for including mutable prototypes find a better way for
> fixing its semantics.
>
The fix is easy enough, and is essentially Mark's structural check. However, it's not an invariant of [[GetPrototypeOf]], instead it is a specified part of ordinary object's [[SetPrototypeOf]]. It works as follows:
1) Note that it is not possible to create an ordinary object whose [[Prototype]] is that same object.
2)Ordinary Object [[SetPrototypeOf]] performs this check:
If this object uses the ordinary object [[GetPrototypeOf]] and the arguemnet object's (ie, the new [[Prototype]] value) is an object whose [[GetPrototypeOf]] is also the ordinary object [[GetPrototypeOf]] then fail if the argument object's [[Prototype]] is the original ordinary object. Otherwise, recursive apply this test to the [[Prototype]] of the argument object. If null or an object that does not use the ordinary object [[GetPrototypeOf]] ls reached, set the original object's [[Prototype]] to the original argument value and succeed.
In other words, you can never construct a circular prototype chain consisting only of object's that implement the ordinary object [[GetPrototuypeOf]].
You can have a circular prototype chain using proxies but, using Mark's terminology, that's a behavioral circularity, not a structural circularity.
(In reply to Allen Wirfs-Brock from comment #15)
> (In reply to Andreas Rossberg from comment #12)
> >
> >
> > I see three possibilities:
> >
> > 1. We drop mutable prototypes from the spec. Then implementations can
> > continue to support it as a legacy feature in whatever hacky way they see
> > fit, even if it doesn't work with proxies.
> >
>
> One is never going to fly. Mutable prototypes are a reality and the job of
> a standard is to ensure that such realities have a good specification.
>
> > 2. We at least remove the ability for proxies to intercept prototype access.
> >
>
> Too big a change and it significantly reduces what can be expressed using
> proxies.
>
> > 3. The champions for including mutable prototypes find a better way for
> > fixing its semantics.
> >
>
> The fix is easy enough, and is essentially Mark's structural check.
> However, it's not an invariant of [[GetPrototypeOf]], instead it is a
> specified part of ordinary object's [[SetPrototypeOf]]. It works as follows:
>
> 1) Note that it is not possible to create an ordinary object whose
> [[Prototype]] is that same object.
>
> 2)Ordinary Object [[SetPrototypeOf]] performs this check:
> If this object uses the ordinary object [[GetPrototypeOf]] and the
> arguemnet object's (ie, the new [[Prototype]] value) is an object whose
> [[GetPrototypeOf]] is also the ordinary object [[GetPrototypeOf]] then fail
> if the argument object's [[Prototype]] is the original ordinary object.
> Otherwise, recursive apply this test to the [[Prototype]] of the argument
> object. If null or an object that does not use the ordinary object
> [[GetPrototypeOf]] ls reached, set the original object's [[Prototype]] to
> the original argument value and succeed.
>
> In other words, you can never construct a circular prototype chain
> consisting only of object's that implement the ordinary object
> [[GetPrototuypeOf]].
>
> You can have a circular prototype chain using proxies but, using Mark's
> terminology, that's a behavioral circularity, not a structural circularity.
It is not quite the same. My suggestion is that, if a proxy is encountered during the structural check, that the structural check (and only the structural check) reach through the proxy to the target's [[Prototype]] without trapping.
Either with or without this additional amendment, yes, I believe your text does it. I don't currently see a strong need for this amendment, and so can probably live without it.
(In reply to Mark Miller from comment #14)
> (In reply to Andreas Rossberg from comment #12)
> > I see three possibilities:
> >
> > 1. We drop mutable prototypes from the spec. Then implementations can
> > continue to support it as a legacy feature in whatever hacky way they see
> > fit, even if it doesn't work with proxies.
>
> No. If it is everywhere, then it is part of the de facto std anyway and
> membranes must support it. Therefore proxies must.
>
> > 2. We at least remove the ability for proxies to intercept prototype access.
>
> No. Makes it impossible to build a membrane.
I understand, but the declared resolution of this bug freaked me out a little and I felt the need to clarify the priorities: I would not be willing to sacrifice the non-cyclicity invariant, neither for the sake of prototype mutation nor proxies. It trumps the desire for both.
I was also positive that it can be fixed with less drastic measures.
> > 3. The champions for including mutable prototypes find a better way for
> > fixing its semantics.
>
> See comments #9 and #11. Did you somehow miss these?
I saw it, but it wasn't entirely clear to me at first if that is good enough. I think I'm convinced now. Thanks.
Regarding the difference between your and Allen's version, I strongly prefer yours. If we want to be able to handle proxies efficiently, especially those that do not have customised getPrototypeOf or any other prototype-walking handlers, then it would be vital to maintain structural non-cyclicity for their targets as well. We want to be able to guarantee termination by construction as long as we do not call into user code, for the reasons Allen brought up in #2 and #4.
fixed in rev30
reopenning, because it everything starting with comment 8 hasn't actually been resolved
Fixed in Rev33 editor's draft
I updated Ordinary Object [[SetPrototypeOf]] to do the check I described in Comment 15. This guarantees that prototype chains consisting only of objects that use the ordinary [[GetPrototypeOf]]/[[SetPrototypeOf]] definitions can't be circular.
In the future we may want to explore switching to Mark's deeper check. But, I think there may be some corner cases with that (for example, proxies on proxies) approach that I don't have time to explore right now.
I think with this change the solution is good enough for Es6.
(In reply to Allen Wirfs-Brock from comment #20)
> Fixed in Rev33 editor's draft
>
> I updated Ordinary Object [[SetPrototypeOf]] to do the check I described in
> Comment 15. This guarantees that prototype chains consisting only of
> objects that use the ordinary [[GetPrototypeOf]]/[[SetPrototypeOf]]
> definitions can't be circular.
>
> In the future we may want to explore switching to Mark's deeper check. But,
> I think there may be some corner cases with that (for example, proxies on
> proxies) approach that I don't have time to explore right now.
>
> I think with this change the solution is good enough for Es6.
Hm, can you elaborate? It seems to me that once we spec it this way, we have to start supporting cycles through proxies, and going to Mark's solution would be a breaking change.
fixed in rev33
Okay, so the change in rev33 still is only a partial fix.
It is not clear to me what the implications of having cyclic prototype chains through proxies are for implementations, and I don't think we have sufficient evidence that they don't cause problems.
I'm fine with keeping it like that for the ES6 spec, as long as we agree to reserve the possibility of flagging this as a spec bug later. For example, for the time being, test262 should not test for this.
(In reply to Andreas Rossberg from comment #23)
> Okay, so the change in rev33 still is only a partial fix.
>
> It is not clear to me what the implications of having cyclic prototype
> chains through proxies are for implementations, and I don't think we have
> sufficient evidence that they don't cause problems.
See Tom's Comment 5
Because of the Rev33 change, the only possible way you could encounter a circular prototype chain is via an Proxy (any other sort of exotic object that exposed a circularity would be self inflicted by the implementation) that has traps for one or more of getPrototypeOf/get/set/hasProperty/enumerate.
But, if you encounter such a trap, you have to break out of whatever sort of proto chain climbing internal loop you might be running so you can enter user provided code. Once you're in userland, you shouldn't care what happens.