Internal List data structure semantics and its implications in section 9.5.11

[saambarati]

I recently implemented section 9.5.11 of the spec inside JavaScriptCore (https://tc39.github.io/ecma262/#sec-proxy-object-internal-methods-and-internal-slots-ownpropertykeys).
Sections 17 and 19 perform the Remove operation on the List type.
I couldn't find documentation on the formal semantics of the List data structure.
Specifically, how is the Remove operation defined? Is it defined to just delete the first instance of something in the List or all instances?

Also, depending on the semantics, the algorithm defined in 9.5.11 allows for duplicate entries to be returned by this trap under certain circumstances. Is this intended? I think this would be the only place where [[OwnPropertyKeys]] has duplicate entries. Maybe we should guarantee the items are unique?

[allenwb]

Lists can have duplicate entries and in cases where duplicate entries ae actually possible the algorithms must explicitly deal with that possibility.

It is a bug that 9.5.11 does not do so.

Note that [[OwnPropertyKeys]] does not have an invariant stating that the List it returns contains no duplicates. So, it is possible that trapResult and/or targetKeys could contain duplicates.

I've generally resisted adding invariant that is not essential for security reasons in order to avoid generally unnecessary extra checking on the results of proxy traps. But in this particular case, I think we should probably add the invariant that the List returned from [[OwnPropertyKeys]] contains no duplicates as such duplicates are generally unexpected and none of the uses of [[OwnPropertyKey]] in the spec. explicitly deals with that possibility. This won't add much overhead to [[OwnPropertyKey]] traps as fixing the bug identified by this issue is going to require de-duping in most cases, so we might as well simplify by making "no dups" an invariant.

Here are the changes I propose:

In 6.1.7.3 under [[OwnPropertyKey]] add this following as an invariant:

• The returned List contains no duplicate entries.

In 9.5.11 insert a new step immediately after step 8:

If trapResult contains any duplicate entries, throw a TypeError exception.

After the existing step 10 add a new step:

Asset: targetKeys contains no duplicate entries.

and add to the list of invariants in the Note:

• The returned List contains no duplicate entries.

With these changes of the other steps of 9.5.11 no longer have to deal with the possibility of duplicate entries.

[allenwb]

Lists can have duplicate entries and in cases where duplicate entries ae actually possible the algorithms must explicitly deal with that possibility.

It is a bug that 9.5.11 does not do so.

Note that [[OwnPropertyKeys]] does not have an invariant stating that the List it returns contains no duplicates. So, it is possible that trapResult and/or targetKeys could contain duplicates.

I've generally resisted adding invariant that is not essential for security reasons in order to avoid generally unnecessary extra checking on the results of proxy traps. But in this particular case, I think we should probably add the invariant that the List returned from [[OwnPropertyKeys]] contains no duplicates as such duplicates are generally unexpected and none of the uses of [[OwnPropertyKey]] in the spec. explicitly deals with that possibility. This won't add much overhead to [[OwnPropertyKey]] traps as fixing the bug identified by this issue is going to require de-duping in most cases, so we might as well simplify by making "no dups" an invariant.

Here are the changes I propose:

In 6.1.7.3 under [[OwnPropertyKey]] add this following as an invariant:

• The returned List contains no duplicate entries.

In 9.5.11 insert a new step immediately after step 8:

If trapResult contains any duplicate entries, throw a TypeError exception.

After the existing step 10 add a new step:

Asset: targetKeys contains no duplicate entries.

and add to the list of invariants in the Note:

• The returned List contains no duplicate entries.

With these changes of the other steps of 9.5.11 no longer have to deal with the possibility of duplicate entries.

[allenwb]

@erights @rossberg-chromium
Thoughts??

[allenwb]

@erights @rossberg-chromium
Thoughts??

[erights]

Thoughts??

@tvcutsem too

Allen, I think I like the general direction, yes. Need to discuss with Tom.

[erights]

Thoughts??

@tvcutsem too

Allen, I think I like the general direction, yes. Need to discuss with Tom.

[annevk]

The returned List contains no duplicate entries.

That would be great to explicitly state. We've been assuming in platform that this is the case and fixing several specifications and browsers as a result. There's a number of objects with "IDL named getters" where returning duplicates would follow quite naturally unless explicitly handled. @heycam, you might want to take note of this.

[annevk]

The returned List contains no duplicate entries.

That would be great to explicitly state. We've been assuming in platform that this is the case and fixing several specifications and browsers as a result. There's a number of objects with "IDL named getters" where returning duplicates would follow quite naturally unless explicitly handled. @heycam, you might want to take note of this.

[allenwb]

@annevk
Note that the proposed change would automatically enforce the invariant only for proxies. Other exotic objects (such as IDL-based objects) would be expected to do their own enforcement of the new invariant.

[allenwb]

@annevk
Note that the proposed change would automatically enforce the invariant only for proxies. Other exotic objects (such as IDL-based objects) would be expected to do their own enforcement of the new invariant.

[annevk]

Yeah, and we are (though not really enforcing, just trying to write correct prose). I just meant that we thought this was an invariant we should aim to follow, but it wasn't listed explicitly as such.

[annevk]

Yeah, and we are (though not really enforcing, just trying to write correct prose). I just meant that we thought this was an invariant we should aim to follow, but it wasn't listed explicitly as such.

[saambarati]

@allenwb
Though this is not related to [[OwnPropertyKeys]] if we require no duplicate entries, I think it's worth explicitly writing down the semantics of the Remove operation on the List data structure to indicate it removes the first instance of the thing.

[saambarati]

@allenwb
Though this is not related to [[OwnPropertyKeys]] if we require no duplicate entries, I think it's worth explicitly writing down the semantics of the Remove operation on the List data structure to indicate it removes the first instance of the thing.

[tvcutsem]

I could swear that we considered the "no duplicate keys" invariant in the early iterations of the Proxy invariants design but I can't find any reference to it. Anyway, I see no problem in adding the proposed restrictions.

[tvcutsem]

I could swear that we considered the "no duplicate keys" invariant in the early iterations of the Proxy invariants design but I can't find any reference to it. Anyway, I see no problem in adding the proposed restrictions.

[allenwb]

@saambarati
Lists are an abstract specification device. There really isn't any universal semantics for them. Each List use case in the spec. is expected to use language that make its specific semantics clear.

[allenwb]

@saambarati
Lists are an abstract specification device. There really isn't any universal semantics for them. Each List use case in the spec. is expected to use language that make its specific semantics clear.

[evilpie]

I am in favor of disallowing duplicate keys. This actually makes the rest of this function simpler to reason about and to implement.

[evilpie]

I am in favor of disallowing duplicate keys. This actually makes the rest of this function simpler to reason about and to implement.

[domenic]

Where did this discussion end up? Did we decide at TC39 to just make the change? Web IDL could use some help figuring out whether they need to handle that case or not.

[domenic]

Where did this discussion end up? Did we decide at TC39 to just make the change? Web IDL could use some help figuring out whether they need to handle that case or not.

[saambarati]

Maybe it's worth having a timeboxed item about this at the next meeting?

[saambarati]

Maybe it's worth having a timeboxed item about this at the next meeting?