1348099 - DOM Xrays should be able to cache a property not being present

Status: RESOLVED FIXED

(Core :: XPConnect, enhancement, P3)

Description

[Boris Zbarsky [:bzbarsky]]

Profiling the testcase from bug 613498, I see that we spend nearly half our time checking whether Xrays have a property only to discover they don't.  This happens because we have to walk up the proto chain.  So for .nextSibling on an element we will fail to find it on 4 Xrays (for the element, its type-specific proto, HTMLElement.prototype, Element.prototype) before we find it on Node.prototype.  And each time we call a bunch of functions, do a linear walk, etc.

We have a way to cache, on the holder, a property that we _found_.  We don't have a cache of properties we don't have.  Maybe we should, in some form?

Comment 1

[Bobby Holley (:bholley)]

This sounds reasonable. We'd need the same sort of invalidation handling that we have when dynamic properties change, but that should be doable.

Worth talking with Bill though, who's also been poking at the performance of this stuff. We had a call a while ago, and my suggestion was to teach the JIT to be smarter about these things in general, and do something akin to shapes.

Comment 2

[Boris Zbarsky [:bzbarsky]]

DOM protos, and most DOM objects, have no dynamic properties.  We could skip caching in the cases that do (i.e. proxies).

But yes, something more like how this works normally, and ideally taking advantage of all the existing IC infrastructure, would be pretty awesome too, obviously.  Just might be a lot more work.

Comment 3

[Kris Maglione [:kmag]]

(In reply to Boris Zbarsky [:bz] (still a bit busy) (if a patch has no decent message, automatic r-) from comment #2)
> But yes, something more like how this works normally, and ideally taking
> advantage of all the existing IC infrastructure, would be pretty awesome
> too, obviously.  Just might be a lot more work.

For the amount that WebExtensions rely on content scripts, it's probably worth it. For complex and inconveniently popular extensions like LastPass, Xray overhead is a major performance suck.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Right, it's a matter of whether we want to ship something that helps "somewhat" soon, or just work on the thing that should help a lot but might take a lot longer.

Comment 5

[(no longer active)]

Boris, is this [qf:p1] considering last week's discussions?

Comment 6

[Boris Zbarsky [:bzbarsky]]

Something like this probably is, yeah...

Comment 7

[Ting-Yu Chou [:ting] (away)]

I'll try to understand the code and find out how to fix this.

Comment 8

[Ting-Yu Chou [:ting] (away)]

Can someone point me out where is the code walking up the proto chain for Xrays? I guess it's around XrayResolveProperty() but don't know where exactly it is.

Comment 9

[Ting-Yu Chou [:ting] (away)]

Seems js::ProxyGetProperty() and js::Proxy::get() are the code I should check.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Exactly.  The proto walk effectively happens in this block: http://searchfox.org/mozilla-central/rev/6580dd9a4eb0224773897388dba2ddf5ed7f4216/js/src/proxy/Proxy.cpp#326-338 because handler->hasPrototype() is true for Xrays.  So we check for an own prop, discover it's not there, and walk up to the proto.  Then GetProperty() ends up back in the same code, because the proto is itself an Xray.

Comment 11

[Ting-Yu Chou [:ting] (away)]

XrayResolveMethod() and XrayResolveAttribute() should be improved for searching the matched/unmatched property.

Comment 12

[Ting-Yu Chou [:ting] (away)]

Comparing jsid should be faster than calling spec isEnabled() when the spec has non-nullptr disabler, if the ids are sorted we can use a O(logN) search.

Comment 13

[Ting-Yu Chou [:ting] (away)]

(In reply to Ting-Yu Chou [:ting] from comment #12)
> has non-nullptr disabler, if the ids are sorted we can use a O(logN) search.

This is impossible if sorted sMethods_ids[] can't have aligned sMethods[]...

Comment 14

[Ting-Yu Chou [:ting] (away)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #1)
> Worth talking with Bill though, who's also been poking at the performance of
> this stuff. We had a call a while ago, and my suggestion was to teach the
> JIT to be smarter about these things in general, and do something akin to
> shapes.

I am not sure which part of code I should check for "teach the JIT to be smarter about these things in general".

:bholley, :billm, could you elaborate? Thanks.

Comment 15

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I think we should probably use this bug for non-JIT stuff. Brian is sort of working on some JIT changes in bug 1355109.

Comment 16

[Ting-Yu Chou [:ting] (away)]

I am thinking to change the data structure of sMethods_ids, sAttributes_ids, sConstants_ids from jsid[] to something an ordered map or a hash map, this could help us not to search for a property linearly. Which if searching for a non-exist property is fast enough, we don't need a cache (requires invalidation) for it. Of course we need to pay memory for that, I just checked, the total number of methods/attributes/constants is 11090. The max ids array size is 1010, so one byte is sufficient to store the corresponding index for spec array which will need 11090=~10k, even if we use 2 bytes it will take just ~20k.

I tend to use a ordered map, because the ids arrays are usually small (average=~10.7) which in average takes 4 jsid comparison. I expect a hash map doesn't win a lot on that and could be worse when collision.

Another byte for the index of prefable array is probably needed.

Comment 17

[Ting-Yu Chou [:ting] (away)]

(In reply to Ting-Yu Chou [:ting] from comment #16)
> checked, the total number of methods/attributes/constants is 11090. The max
> ids array size is 1010, so one byte is sufficient to store the corresponding
> index for spec array

Correction: two bytes or ten bits

Comment 18

[Bobby Holley (:bholley)]

I'll defer to billm on stuff here.

Comment 19

[Boris Zbarsky [:bzbarsky]]

It's worth checking how much that helps.  But it's entirely possible that the many function calls of overhead are a bigger problem than the linear walks in practice...

Comment 20

[Boris Zbarsky [:bzbarsky]]

Also, bug 1348095 comment 3 has a microbenchmark you can use to measure.

Comment 21

[Ting-Yu Chou [:ting] (away)]

Thanks for reminding and the benchmark! :)

Comment 22

[Ting-Yu Chou [:ting] (away)]

Attachment: wip v1

Simply defer checking spec isEnabled() until a matched id is found, this makes the number of the micro benchmark drops down from average 4665 to 2513 (10 runs).

Comment 23

[Ting-Yu Chou [:ting] (away)]

I'll read mozwebidlcodegen to figure out how to alter the binding.

Comment 24

[Boris Zbarsky [:bzbarsky]]

All the binding generation is in dom/bindings/Codegen.py; no need to sort through mozwebidlcodegen.

Comment 25

[Ting-Yu Chou [:ting] (away)]

Yes, I've found that. My current plan is to have a unified ids table so we don't need to repeat similar logic in XrayResolveProperty() to go through static/unforgeable/normal methods/attributes/constants, which will lower the number of function calls and leverage the O(logN) searching.

Comment 26

[Ting-Yu Chou [:ting] (away)]

I was struggled at bug 816784, will now concentrate on this.

Comment 27

[Ting-Yu Chou [:ting] (away)]

Attachment: wip v2

This WIP is very raw. But basically it a) uses two std::array to store the property id that InitIds() generated, one for regular and one for chrome only, b) std::sort() the array after finish id generation, and c) use std::lower_bound() to binary search the resolving property.

On my desktop this gets me the numbers below (20 runs) form the micro benchmark:

Without the WIP:
  MIN=4062, MAX=7382, AVG=4588.2, STD=711.38, MED=4344
With the WIP:
  MIN=1922, MAX=2677, AVG=2223.1, STD=205.31, MED=2206.5

Note the average of this WIP is slightly (~9%) better then the result of attachment 8866612 [details] [diff] [review] in comment 22.

I'm going to refine the patch, and do followings:

a) I don't know why std::array is not used in /js, but I guess I should use AutoTArray instead
b) deal with iteratorAliasMethodIndex (or maybe it's not needed?)
c) look for better data structure to map found id to its spec

Comment 28

[Kan-Ru Chen [:kanru] (UTC+9)]

(In reply to Ting-Yu Chou [:ting] from comment #27)
> a) I don't know why std::array is not used in /js, but I guess I should use
> AutoTArray instead

FYI, If all you need is a fixed-length array, there is mfbt/Array.h

Comment 29

[Ting-Yu Chou [:ting] (away)]

For the record, the numbers from the micro benchmark (20 runs):

Use std::array to store/sort/search property ids:
  MIN=2124, MAX=2591, AVG=2185.3, STD=98.69, MED=2163.5

Use AutoTArray to store/sort/search property ids:
  MIN=1741, MAX=1840, AVG=1776.6, STD=23.29, MED=1772.5

Comment 30

[Ting-Yu Chou [:ting] (away)]

I just realized sorted id table makes XrayOwnNativePropertyKeys() difficult to do, because it can't append a group of properties that are managed by a prefable, it needs to check the prefable is enabled or not for every id.

I have no ideas how to deal with this now.

Comment 31

[Ting-Yu Chou [:ting] (away)]

Two options for XrayOwnNativePropertyKeys: 1) use a linked list to maintain the ordering before sorting, 2) has an extra table to map between unsorted/sorted ids, this one requires less memory.

Comment 32

[Ting-Yu Chou [:ting] (away)]

Measured insertion sort / quick sort for sorting the jsid, quick sort does better especially for large array like the one in CSS2PropertiesBinding.

Comment 33

[Ting-Yu Chou [:ting] (away)]

Attachment: Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Currently we resolve a property by iterating every prefable and check whether it
is enabled. If it is, linear search the ids that it manages. This patch changes
that to binary search the resolving id at first, and check its prefable is
enabled or not only when we found one.

The patch stores all the property ids a NativePropertiesN owns in a single
array, and sort its index array for later binary search. This index array
requires 2 bytes for each property, which is ~20k. Also we need some indices to
be able to index the corresponding prefable and spec when we found a match, this
requires extra 4 bytes for each property on 32-bit binary, which is ~40k and
double on 64-bit. However we save a bit from changing NativePropertiesN's trios
to duos.

The array of unsorted ids is kept because XrayOwnPropertyKeys() includes only
properties that are enabled. Without it, we will need to check every single
property to know whether its prefable is enabled or not, which is inefficient.

With this patch, initializing property ids takes longer because of the
sorting. I measured also insertion sort because I thought the ids should be
nearly sorted as they are generated sequentially at run time, but that's not the
case and NS_QuickSort() runs faster.

Review commit: https://reviewboard.mozilla.org/r/148948/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/148948/

Comment 34

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/1-2/

Comment 35

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review154676

I'm sorry for the lag here.  It took me a while to figure out what the setup is and double-check various bits in the resulting codegen...

Marking r- because of the various naming issues and more importantly the incorrect behavior this produces, from what I can see, in terms of which properties are exposed on which Xrays (interface object vs prototype object vs instance).  There's no really fundamental issue here, though; just some missing checks that need to be made.  In general this looks pretty good!

::: commit-message-b266a:4
(Diff revision 2)
> +Bug 1348099 - Binary search property id when resolve DOM Xrays own property. r?bz
> +
> +Currently we resolve a property by iterating every prefable and check whether it
> +is enabled. If it is, linear search the ids that it manages. This patch changes

"If it is, we linear search"

::: commit-message-b266a:5
(Diff revision 2)
> +Bug 1348099 - Binary search property id when resolve DOM Xrays own property. r?bz
> +
> +Currently we resolve a property by iterating every prefable and check whether it
> +is enabled. If it is, linear search the ids that it manages. This patch changes
> +that to binary search the resolving id at first, and check its prefable is

"to binary searching to find whether the id being resolved is present first, and checking whether its prefable is enabled only when we find it.  This improves the performance of property resolution, especially when the property is not present."

::: commit-message-b266a:10
(Diff revision 2)
> +that to binary search the resolving id at first, and check its prefable is
> +enabled or not only when we found one. This improves resolving, especically when
> +the property isn't present.
> +
> +The patch stores all the property ids a NativePropertiesN owns in a single
> +array, and sort its index array for later binary search. This index array

How about:

"The patch stores all the property ids a NativePropertiesN owns in a single array of PropertyInfo structs.  Each struct contains an id and the information needed to find the corresponding Prefable for the enabled check, as well as the information needed to find the correct property descriptor in the Prefable.  We also store an array of indices into the PropertyInfo array, sorted by bits of the corresponding jsid.  Given a jsid, this allows us to binary search for the index of the corresponding PropertyInfo, if any.  The index array requires 2 bytes for each property, which is ~20k across all our bindings.  The extra information stored in each PropertyInfo requires 4 bytes for each property, which is about 40k across all our bindings in 32-bit builds, or 80k in 64-bit builds due to alignment requirements on PropertyInfo.   However we save a bit of memory from changing NativePropertiesN's trios to duos."

Things to check in the above:

1) Is PropertyInfo a sane name for that struct containing id-and-stuff?  More on this below.
2) Is the description of why 64-bit builds need more memory correct?  If so, it might make some sense to have a separate array for those 4-bytes-per-property things, with the same order as the jsid array.  That would reduce the 64-bit memory usage.  Followup is ok for this part.
3) Are my claims about the 20k and 40k/80k being across all bindings together correct?

::: commit-message-b266a:23
(Diff revision 2)
> +properties that are enabled. Without it, we will need to check every single
> +property to know whether its prefable is enabled or not, which is inefficient.
> +
> +With this patch, initializing property ids takes longer because of the
> +sorting. I measured also insertion sort because I thought the ids should be
> +nearly sorted as they are generated sequentially at run time, but that's not the

The ids in this case are pointers to the string memory, so it's not surprising they're not very sorted.

::: dom/bindings/BindingUtils.h:1781
(Diff revision 2)
>      return true;
>    }
>    return false;
>  }
>  
>  // Spec needs a name property

Should this comment still be here?

::: dom/bindings/BindingUtils.cpp:1137
(Diff revision 2)
>  
>    return true;
>  }
>  
> +static int
> +CompareId(const void* aElement1, const void* aElement2, void* aClosure)

Maybe call this CompareIdsAtIndices?

::: dom/bindings/BindingUtils.cpp:1137
(Diff revision 2)
>  
>    return true;
>  }
>  
> +static int
> +CompareId(const void* aElement1, const void* aElement2, void* aClosure)

CompareIdIndices might be a clearer name, I think.

::: dom/bindings/BindingUtils.cpp:1156
(Diff revision 2)
> +                PropertyType type)
> +{
> +  MOZ_ASSERT(pref);
> +  MOZ_ASSERT(pref->specs);
> +
> +  const SpecT* spec;

There's really no need to declare it where it's actually used.  Please move it back where it used to be declared.

::: dom/bindings/BindingUtils.cpp:1157
(Diff revision 2)
> +{
> +  MOZ_ASSERT(pref);
> +  MOZ_ASSERT(pref->specs);
> +
> +  const SpecT* spec;
> +  uint32_t prefIndex = 0, specIndex = 0;

Please document these integers.

Looks like prefIndex is the index into `pref` and `specIndex` is the index into the `pref->specs[prefIndex]` right?

It would be clearer to declare specIndex right where we declare/set spec, and set it to 0 at that point.

::: dom/bindings/BindingUtils.cpp:1170
(Diff revision 2)
> +        return false;
> +      }
> +      ids->type = type;
> +      ids->prefIndex = prefIndex;
> +      ids->specIndex = specIndex++;
> +    } while (++ids, (++spec)->name);

I would really prefer that `++ids` were not inside the while condition.  That makes it clearer, to me, what the condition is.

If we want to also haul out the `++spec` and just leave the condition as `spec->name`, that would be fine with me.

::: dom/bindings/BindingUtils.cpp:1172
(Diff revision 2)
> +      ids->type = type;
> +      ids->prefIndex = prefIndex;
> +      ids->specIndex = specIndex++;
> +    } while (++ids, (++spec)->name);
> +    specIndex = 0;
> +  } while (++prefIndex, (++pref)->specs);

Again, I would really prefer to not have the index increment in the condition.

::: dom/bindings/BindingUtils.cpp:1181
(Diff revision 2)
> +
> +#define INIT_IDS_IF_DEFINED(TypeName) {                                       \
> +  if (nativeProperties->Has##TypeName##s() &&                                 \
> +      !InitIdsInternal(cx,                                                    \
> +                       nativeProperties->TypeName##s(),                       \
> +                       const_cast<PropertyId*>(nativeProperties->TypeName##Ids()), \

Why do we want a const_cast here?  And why is it ok?

::: dom/bindings/BindingUtils.cpp:1190
(Diff revision 2)
> +}
> +
> +bool
> +InitIds(JSContext* cx, const NativeProperties* nativeProperties)
> +{
> +  // The initialzation order has to sync with the order that codegen calculates

"initialization".

Is this enforced somehow (e.g. via static_asserts somewhere)?  This is the sort of non-local thing that would be really easy to mess up by accident, especially since codegen has no indication that _it_ needs to match the order here.

Also, this should probably explain _why_ the two orders should be kept in sync.  It's not at all obvious to me that it needs to be.

::: dom/bindings/BindingUtils.cpp:1201
(Diff revision 2)
> +  INIT_IDS_IF_DEFINED(UnforgeableMethod);
> +  INIT_IDS_IF_DEFINED(UnforgeableAttribute);
> +  INIT_IDS_IF_DEFINED(Constant);
> +
> +  // Initialize and sort the index array.
> +  uint16_t* index = const_cast<uint16_t*>(nativeProperties->idsSortedIndex);

Please, no const_cast.  If the data is not const, don't claim that it's const.

::: dom/bindings/BindingUtils.cpp:1201
(Diff revision 2)
> +  INIT_IDS_IF_DEFINED(UnforgeableMethod);
> +  INIT_IDS_IF_DEFINED(UnforgeableAttribute);
> +  INIT_IDS_IF_DEFINED(Constant);
> +
> +  // Initialize and sort the index array.
> +  uint16_t* index = const_cast<uint16_t*>(nativeProperties->idsSortedIndex);

This const_cast is not OK.  The data is not const; we should not be pretending it is.  That is, the member in nativeProperties should not claim it's const.

Also, "indices" or "indexArray" or something might be a better name here.

::: dom/bindings/BindingUtils.cpp:1206
(Diff revision 2)
> +  uint16_t* index = const_cast<uint16_t*>(nativeProperties->idsSortedIndex);
> +  for (unsigned int i = 0; i < nativeProperties->idsLength; ++i) {
> +    index[i] = i;
> +  }
> +  NS_QuickSort(index, nativeProperties->idsLength, sizeof(uint16_t), CompareId,
> +               const_cast<PropertyId*>(nativeProperties->Ids()));

This const_cast is deeply unfortunate, but I guess the NS_QuickSort API sort of requires it...  Please add a comment about how the callee doesn't actually modify this data, so it really is OK to const_cast here in spite of the callee's function signature.

::: dom/bindings/BindingUtils.cpp:1372
(Diff revision 2)
>  }
>  
>  static bool
>  XrayResolveAttribute(JSContext* cx, JS::Handle<JSObject*> wrapper,
>                       JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> -                     const Prefable<const JSPropertySpec>* attributes,
> +                     const Prefable<const JSPropertySpec>* pref,

This is now never null, right?  Please pass it as a reference, not a pointer.

::: dom/bindings/BindingUtils.cpp:1373
(Diff revision 2)
>  
>  static bool
>  XrayResolveAttribute(JSContext* cx, JS::Handle<JSObject*> wrapper,
>                       JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> -                     const Prefable<const JSPropertySpec>* attributes,
> -                     const jsid* attributeIds,
> +                     const Prefable<const JSPropertySpec>* pref,
> +                     const JSPropertySpec* spec,

Likewise, pass a reference, not a pointer.  And please call it attrSpec like before.

::: dom/bindings/BindingUtils.cpp:1377
(Diff revision 2)
> -                     const jsid* attributeIds,
> +                     const JSPropertySpec* spec,
> -                     const JSPropertySpec* attributeSpecs,
>                       JS::MutableHandle<JS::PropertyDescriptor> desc,
>                       bool& cacheOnHolder)
>  {
> -  for (; attributes->specs; ++attributes) {
> +  if (pref->isEnabled(cx, obj)) {

Now that we're not looping and know we only have to deal with the one JSPropertySpec, you can early-return true if isEnabled() tests false and outdent things even more.

::: dom/bindings/BindingUtils.cpp:1412
(Diff revision 2)
>  }
>  
>  static bool
>  XrayResolveMethod(JSContext* cx, JS::Handle<JSObject*> wrapper,
>                    JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> -                  const Prefable<const JSFunctionSpec>* methods,
> +                  const Prefable<const JSFunctionSpec>* pref,

Again, pass by reference.

::: dom/bindings/BindingUtils.cpp:1413
(Diff revision 2)
>  
>  static bool
>  XrayResolveMethod(JSContext* cx, JS::Handle<JSObject*> wrapper,
>                    JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> -                  const Prefable<const JSFunctionSpec>* methods,
> -                  const jsid* methodIds,
> +                  const Prefable<const JSFunctionSpec>* pref,
> +                  const JSFunctionSpec* spec,

Pass by reference, call it methodSpec.

::: dom/bindings/BindingUtils.cpp:1417
(Diff revision 2)
> -                  const jsid* methodIds,
> +                  const JSFunctionSpec* spec,
> -                  const JSFunctionSpec* methodSpecs,
>                    JS::MutableHandle<JS::PropertyDescriptor> desc,
>                    bool& cacheOnHolder)
>  {
> -  const Prefable<const JSFunctionSpec>* method;
> +  if (pref->isEnabled(cx, obj)) {

Return true early if not and outdent.

::: dom/bindings/BindingUtils.cpp:1451
(Diff revision 2)
> -// NativeProperties, if it's there.  nativeProperties is allowed to be null (in
> -// which case we of course won't resolve anything).
>  static bool
> -XrayResolveUnforgeableProperty(JSContext* cx, JS::Handle<JSObject*> wrapper,
> -                               JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> +XrayResolveConstant(JSContext* cx, JS::Handle<JSObject*> wrapper,
> +                    JS::Handle<JSObject*> obj, JS::Handle<jsid>,
> +                    const Prefable<const ConstantSpec>* pref,

Pass by reference.

::: dom/bindings/BindingUtils.cpp:1452
(Diff revision 2)
> -// which case we of course won't resolve anything).
>  static bool
> -XrayResolveUnforgeableProperty(JSContext* cx, JS::Handle<JSObject*> wrapper,
> -                               JS::Handle<JSObject*> obj, JS::Handle<jsid> id,
> +XrayResolveConstant(JSContext* cx, JS::Handle<JSObject*> wrapper,
> +                    JS::Handle<JSObject*> obj, JS::Handle<jsid>,
> +                    const Prefable<const ConstantSpec>* pref,
> +                    const ConstantSpec* spec,

Pass by reference, call it "constantSpec".

::: dom/bindings/BindingUtils.cpp:1467
(Diff revision 2)
> -    if (desc.object()) {
> -      return true;
> +  return true;
> -    }
> +}
> -  }
>  
> -  if (nativeProperties->HasUnforgeableMethods()) {
> +struct IdComparator

It's really IdToIndexComparator, right?

::: dom/bindings/BindingUtils.cpp:1469
(Diff revision 2)
> -    }
> +}
> -  }
>  
> -  if (nativeProperties->HasUnforgeableMethods()) {
> -    if (!XrayResolveMethod(cx, wrapper, obj, id,
> -                           nativeProperties->UnforgeableMethods(),
> +struct IdComparator
> +{
> +  const jsid& mId;

Please document: this is the id we're searching for.

::: dom/bindings/BindingUtils.cpp:1470
(Diff revision 2)
> -  }
>  
> -  if (nativeProperties->HasUnforgeableMethods()) {
> -    if (!XrayResolveMethod(cx, wrapper, obj, id,
> -                           nativeProperties->UnforgeableMethods(),
> -                           nativeProperties->UnforgeableMethodIds(),
> +struct IdComparator
> +{
> +  const jsid& mId;
> +  const PropertyId* mIds;

And this is the list we're searching in.

::: dom/bindings/BindingUtils.cpp:1477
(Diff revision 2)
> -    }
> -
> +    if (JSID_BITS(mId) == JSID_BITS(mIds[aIndex].id)) {
> +      return 0;
> -    if (desc.object()) {
> -      return true;
>      }
> +    return JSID_BITS(mIds[aIndex].id) < JSID_BITS(mId) ? 1 : -1;

This might be clearer if it put JSID_BITS(mId) on the left-hand side like the comparator example in the BinarySearch documentation does.  Either way, though.

::: dom/bindings/BindingUtils.cpp:1483
(Diff revision 2)
>    }
> +};
>  
> -  return true;
> +#define RESOLVE_CASE(PropType, SpecType, Resolver)                            \
> +  case e##PropType: {                                                         \
> +    const Prefable<const SpecType>* pref =                                    \

Please MOZ_ASSERT(nativeProperties->HasPropType##s()) here or so.  That better hold, right?

::: dom/bindings/BindingUtils.cpp:1513
(Diff revision 2)
> +    return XrayResolveMethod(cx, wrapper, obj, id, --pref, spec, desc,
> +                             cacheOnHolder);
>    }
>  
> -  if (nativeProperties->HasConstants()) {
> -    const Prefable<const ConstantSpec>* constant;
> +  size_t idx;
> +  const PropertyId* ids = nativeProperties->Ids();

"propertyInfos", no "ids".  Or something.

::: dom/bindings/BindingUtils.cpp:1519
(Diff revision 2)
>  
> -            desc.setAttributes(JSPROP_ENUMERATE | JSPROP_READONLY | JSPROP_PERMANENT);
> -            desc.object().set(wrapper);
> -            desc.value().set(nativeProperties->ConstantSpecs()[i].value);
> -            return true;
> -          }
> +  if (BinarySearchIf(nativeProperties->idsSortedIndex, 0,
> +                     nativeProperties->idsLength, IdComparator(id, ids), &idx)) {
> +    const PropertyId& found = ids[nativeProperties->idsSortedIndex[idx]];
> +    switch (found.type) {
> +    RESOLVE_CASE(StaticMethod, JSFunctionSpec, XrayResolveMethod)

This doesn't look right to me.  This will resolve static methods on prototype and non-static methods on interface objects, no?  And it will resolve unforgeable things on both of those, whereas they should only be resolved on instances.  That is, this code is no longer using the DOMObjectType argument to this function, and it really should be.

If we didn't have tests that caught this, could you please add some?

::: dom/bindings/BindingUtils.cpp:1750
(Diff revision 2)
>  
>    const DOMProxyHandler* handler = GetDOMProxyHandler(obj);
>    return handler->defineProperty(cx, wrapper, id, desc, result, defined);
>  }
>  
> -template<typename SpecType>
> +template<typename SpecT>

I'm not sure why various things here got renamed.  Please put them back the way they used to be.

::: dom/bindings/BindingUtils.cpp:1757
(Diff revision 2)
> -                          JS::Handle<JSObject*> obj,
> -                          const Prefable<const SpecType>* list,
> -                          const jsid* ids, const SpecType* specList,
> +                       const Prefable<const SpecT>* pref,
> +                       const PropertyId* ids, unsigned flags,
> +                       JS::AutoIdVector& props)
> -                          unsigned flags, JS::AutoIdVector& props)
>  {
> -  for (; list->specs; ++list) {
> +  const SpecT* spec;

This should be scoped to where it's actually used.

::: dom/bindings/BindingUtils.cpp:1772
(Diff revision 2)
> -            !props.append(ids[i])) {
> +            !props.append(id)) {
>            return false;
>          }
> +      } while ((++spec)->name);
> +    } else {
> +      ids += (pref + 1)->specs - pref->specs - 1;

This seems like it will do something prety weird when (pref + 1)->specs == 0.  It might not matter too much because we'll then break out of the loop, but at the very least this deserves a comment about why this is not undefined behavior.  Which is not obvious to me.

It might be better to only change ids when we change the value of "pref" and index into it via an integer index we increment as we increment "spec" in the enabled case.  Then we could do `newPref = pref + 1; if (!newPref) { break; } /* Update ids */ } while (1);` kind of thing.

::: dom/bindings/BindingUtils.cpp:1797
(Diff revision 2)
> +        if (!props.append(ids++->id)) {
> +          return false;
> -    }
> +        }
> +      } while ((++spec)->name);
> +    } else {
> +      ids += (pref + 1)->specs - pref->specs - 1;

Similar issue here to the method/attribute case.

::: dom/bindings/BindingUtils.cpp:1838
(Diff revision 2)
>    } else if (type != eGlobalInterfacePrototype) {
>      MOZ_ASSERT(IsInterfacePrototype(type));
>      ADD_KEYS_IF_DEFINED(Method);
>      ADD_KEYS_IF_DEFINED(Attribute);
>    }
> +  ADD_KEYS_IF_DEFINED(Constant);

Preexisting, but constants shouldn't be on instances.  Please file a followup, ok?

::: dom/bindings/Codegen.py:2868
(Diff revision 2)
> -                    offset += 1
> +                    duosOffset += 1
>                      nativePropsInts.append(CGGeneric(bitfields))
>  
>                      if propertyArray.usedForXrays():
> -                        ids = "%(name)s_ids"
> +                        ids = "&%s_ids[%d]" % (name, idsOffset)
> +                        idsOffset += (len(propertyArray.chrome) if chrome else

This "determine the length" logic might be better as a method on propertyArray.

::: dom/bindings/Codegen.py:2873
(Diff revision 2)
> +                        idsOffset += (len(propertyArray.chrome) if chrome else
> +                                      len(propertyArray.regular))
>                      else:
>                          ids = "nullptr"
> -                    trio = "{ %(name)s, " + ids + ", %(name)s_specs }"
> -                    trio = trio % {'name': varName}
> +                    duo = "{ %s, " + ids + " }"
> +                    duo = duo % (varName)

The combination of %-substitution and concatenation here is confusing.  Yes, I know the existing code sort of had that sort of thing too.  Please just pick one?  Probaby best to do:

    duo = "{ %s, %s }" % (varName, ids)
    
or so.

::: dom/bindings/Codegen.py:2879
(Diff revision 2)
> -                    nativePropsTrios.append(CGGeneric(trio))
> +                    nativePropsDuos.append(CGGeneric(duo))
>                  else:
>                      bitfields = "false, 0"
>                      nativePropsInts.append(CGGeneric(bitfields))
>  
> -            nativePropsTrios = \
> +            iteratorAliasIndex = -1

Why did this code need to be moved?

::: dom/bindings/Codegen.py:2889
(Diff revision 2)
> +            nativePropsInts.append(CGGeneric(str(iteratorAliasIndex)))
> +
>              pre = ("static const NativePropertiesN<%d> %s = {\n" %
> -                   (offset, name))
> +                   (duosOffset, name))
> +            if descriptor.wantsXrays:
> +                pre = ("static uint16_t {0}_idsSortedIndex[{1}];\n"

Please use either %(name) or fill() here instead of {N} and format().  We really don't want to add even more string-formatting styles in this file.  ;)

fill() is really the right tool for this: it would let you easily insert the existing value of "pre" via $* and handle the newline bits and whatnot for you sanely.

::: dom/bindings/Codegen.py:2889
(Diff revision 2)
> +            nativePropsInts.append(CGGeneric(str(iteratorAliasIndex)))
> +
>              pre = ("static const NativePropertiesN<%d> %s = {\n" %
> -                   (offset, name))
> +                   (duosOffset, name))
> +            if descriptor.wantsXrays:
> +                pre = ("static uint16_t {0}_idsSortedIndex[{1}];\n"

"sortedPropertyIndices", not "idsSortedIndex".

::: dom/bindings/Codegen.py:2890
(Diff revision 2)
> +
>              pre = ("static const NativePropertiesN<%d> %s = {\n" %
> -                   (offset, name))
> +                   (duosOffset, name))
> +            if descriptor.wantsXrays:
> +                pre = ("static uint16_t {0}_idsSortedIndex[{1}];\n"
> +                       "static PropertyId {0}_ids[{1}];\n\n"

"_propertyInfos", not "_ids".

::: dom/bindings/DOMJSClass.h:183
(Diff revision 2)
> +  eUnforgeableMethod,
> +  eUnforgeableAttribute,
> +  eConstant
> +};
> +
> +struct PropertyId {

The members of this struct should be documented.

I'm not entirely sure about the naming for this struct.  Maybe call it PropertyInfo instead of PropertyId?  It has an id, what sort of property this is, and where to find the property spec...  I've assumed in various comments above that we do rename to PropertyInfo.

::: dom/bindings/DOMJSClass.h:185
(Diff revision 2)
> +  eConstant
> +};
> +
> +struct PropertyId {
> +  jsid id;
> +  uint32_t type: 3;

What guarantees that this is enough bits?  There should be a static_assert somewhere.  Similar for the other parts of this bitfield.

::: dom/bindings/DOMJSClass.h:198
(Diff revision 2)
>  // methods and attributes, and constants.
>  //
> -// That's 21 pointers, but in most instances most of the trios are all null,
> +// That's 14 pointers, but in most instances most of the duos are all null,
>  // and there are many instances. To save space we use a variable-length type,
>  // NativePropertiesN<N>, to hold the data and getters to access it. It has N
> -// actual trios (stored in trios[]), plus four bits for each of the 7 possible
> +// actual duos (stored in duoos[]), plus four bits for each of the 7 possible

s/duoos/duos/

::: dom/bindings/DOMJSClass.h:209
(Diff revision 2)
>  // public only so they can be statically initialized.) These assertions should
>  // never fail so long as (a) accesses to the variable-length part are guarded by
>  // appropriate Has*() calls, and (b) all instances are well-formed, i.e. the
>  // value of N matches the number of mHas* members that are true.
>  //
> +// To search matched property faster when resolve one, we put all the property

This comment doesn't explain the setup very clearly.  See my suggestions on the commit message for a possibly clearer-explanation that should also go here.

::: dom/bindings/DOMJSClass.h:210
(Diff revision 2)
>  // never fail so long as (a) accesses to the variable-length part are guarded by
>  // appropriate Has*() calls, and (b) all instances are well-formed, i.e. the
>  // value of N matches the number of mHas* members that are true.
>  //
> +// To search matched property faster when resolve one, we put all the property
> +// ids into a single table and have an index array for it which is sorted, so we

Please make it clear that this is a single table per interface.

::: dom/bindings/DOMJSClass.h:211
(Diff revision 2)
>  // appropriate Has*() calls, and (b) all instances are well-formed, i.e. the
>  // value of N matches the number of mHas* members that are true.
>  //
> +// To search matched property faster when resolve one, we put all the property
> +// ids into a single table and have an index array for it which is sorted, so we
> +// can binary search later. The indices inside struct PropertyId let us index

PropertyInfo.

::: dom/bindings/DOMJSClass.h:233
(Diff revision 2)
> -  // array could require a different T. Therefore, we can't use the correct
> -  // type for mPrefables and mSpecs. Instead we use void* and cast to the
> -  // correct type in the getters.
> -  struct Trio {
> +  // could require a different T. Therefore, we can't use the correct type for
> +  // mPrefables. Instead we use void* and cast to the correct type in the
> +  // getters.
> +  struct Duo {
>      const /*Prefable<const T>*/ void* const mPrefables;
> -    const jsid* const mIds;
> +    const PropertyId* const mIds;

Ah, this is why you have the const_cast.  This part is wrong.  The old code has a `const jsid*` here, because the ids were never modified via the NativePropetiesN.  But now you _do_ in fact want to modify them that way, so this better be a `PropertyId* const mIds` so that's clear to everyone.

::: dom/bindings/DOMJSClass.h:240
(Diff revision 2)
> -
>    constexpr const NativePropertiesN<7>* Upcast() const {
>      return reinterpret_cast<const NativePropertiesN<7>*>(this);
>    }
>  
> +  const PropertyId* Ids() const {

And this should return `PropertyId*`, no const.

::: dom/bindings/DOMJSClass.h:278
(Diff revision 2)
>  
>  #undef DO
>  
> -  const Trio trios[N];
> +  // Use two bytes to store the array index and length because it's large enough
> +  // for the native properties, and we can save a bit memory.
> +  const int16_t iteratorAliasMethodIndex;

What ensures that this type is big enough?  There should be static_asserts somewhere.  Same for idsLength.

::: dom/bindings/DOMJSClass.h:278
(Diff revision 2)
>  
>  #undef DO
>  
> -  const Trio trios[N];
> +  // Use two bytes to store the array index and length because it's large enough
> +  // for the native properties, and we can save a bit memory.
> +  const int16_t iteratorAliasMethodIndex;

This is an index into ... what?  Please document.

::: dom/bindings/DOMJSClass.h:280
(Diff revision 2)
>  
> -  const Trio trios[N];
> +  // Use two bytes to store the array index and length because it's large enough
> +  // for the native properties, and we can save a bit memory.
> +  const int16_t iteratorAliasMethodIndex;
> +
> +  const uint16_t idsLength;

Document.

::: dom/bindings/DOMJSClass.h:281
(Diff revision 2)
> -  const Trio trios[N];
> +  // Use two bytes to store the array index and length because it's large enough
> +  // for the native properties, and we can save a bit memory.
> +  const int16_t iteratorAliasMethodIndex;
> +
> +  const uint16_t idsLength;
> +  const uint16_t* const idsSortedIndex;

Document.

As far as I can tell, this field stores a list of indices into the PropertyId (PropertyInfo) array.  The order of the indices corresponds to a sort of the PropertyInfos by the bits of their jsid.

Given that, this should probably be called "sortedPropertyIndices" or something like that.

Comment 36

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review154676

> "propertyInfos", no "ids".  Or something.

I assume this apply to the other places like the |ids| in CompareIdsAtIndices() above, and probably nativeProperties->Ids() should be renamed to nativeProperties->PropertyInfos()?

> This doesn't look right to me.  This will resolve static methods on prototype and non-static methods on interface objects, no?  And it will resolve unforgeable things on both of those, whereas they should only be resolved on instances.  That is, this code is no longer using the DOMObjectType argument to this function, and it really should be.
> 
> If we didn't have tests that caught this, could you please add some?

Could you show me a brief example for how will a test look like?

> Why did this code need to be moved?

Because I moved NativePropertiesN.iteratorAliasMethodIndex from before the bitfields to after the bitfields, which the bitfields will stay in the first 4 bytes, iteratorAliasMethodIndex and idsLength are in the second 4 bytes. If I don't move the code, the bitfileds can't be simply appended to nativePropsInts[].

> What guarantees that this is enough bits?  There should be a static_assert somewhere.  Similar for the other parts of this bitfield.

I don't know how to static_assert this, I can do the check in codegen though, is that OK?

Comment 37

[Boris Zbarsky [:bzbarsky]]

> I assume this apply to the other places like the |ids| in CompareIdsAtIndices() above, and probably 

Well, that one really is comparing just the ids that are inside the propertyinfos.  So it could stay.

> and probably nativeProperties->Ids() should be renamed to nativeProperties->PropertyInfos()

Yes, please!

> Could you show me a brief example for how will a test look like?

In a test in which things are being accessed over Xrays (e.g. add to dom/bindings/test/test_dom_xrays.html for simplicity), you should check the following:

1)  Non-static things are not exposed on interface objects or instances.  For example, win.Node.querySelector should be undefined, and win.HTMLInputElement.checkValidity and Object.getOwnPropertyDescriptor(doc.createElement("input"), "checkValidity") and Object.getOwnPropertyDescriptor(win.HTMLInputElement, "checkValidity") should also be undefined.  I _think_ the patch I reviewed fails all of those.  On the other hand, Object.getOwnPropertyDescriptor(win.HTMLInputElement.prototype, "checkValidity") and doc.createElement("input").checkValidity should _not_ be undefined.

2)  Static things are not exposed on prototype objects or instances.  Pick an interface with static bits, and write tests similar to the ones I suggest in item 1.

3)  Unforgeable things are not exposed on prototype objects or interface objects.  This needs to be tested with Document/Document.prototype or Window/Window.prototype, basically.  Again, I expect this fails with the current patch.

> I don't know how to static_assert this

Asserting that "type" is big enough should be straightforward: assert that "(1<<(type bits))-1" is at least the number of different types.  You can use a #define for the "type bits" value so you end up using the same symbolic name in the assert and in the actual declaration.

Asserting that the offsets are big enough could be done by having codegen output the relevant static_asserts, again using #defines for the number of bits.  That's actually simpler to keep in sync than having codegen check the values, because you only need to deal with C++ knowing about the number of bits involved, not both C++ and python.

Comment 38

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/2-3/

Comment 39

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

I fixed the comments except the issue in XrayResolveProperty() and the corresponding tests, I am still working on them.

I am not sure about following names:

  NativePropertiesN.XxxIds() -> rename to XxxPropertyInfos()?
  NativePropertiesN.idsLength -> idsLength is a bit strange now, how about length?
  Duo.mIds -> Duo.mPropertyInfos?
  NativePropertiesN.sortedPropertyIndices -> what if remove the extra "Property" to "sortedIndices"?

Comment 40

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review154676

> How about:
> 
> "The patch stores all the property ids a NativePropertiesN owns in a single array of PropertyInfo structs.  Each struct contains an id and the information needed to find the corresponding Prefable for the enabled check, as well as the information needed to find the correct property descriptor in the Prefable.  We also store an array of indices into the PropertyInfo array, sorted by bits of the corresponding jsid.  Given a jsid, this allows us to binary search for the index of the corresponding PropertyInfo, if any.  The index array requires 2 bytes for each property, which is ~20k across all our bindings.  The extra information stored in each PropertyInfo requires 4 bytes for each property, which is about 40k across all our bindings in 32-bit builds, or 80k in 64-bit builds due to alignment requirements on PropertyInfo.   However we save a bit of memory from changing NativePropertiesN's trios to duos."
> 
> Things to check in the above:
> 
> 1) Is PropertyInfo a sane name for that struct containing id-and-stuff?  More on this below.
> 2) Is the description of why 64-bit builds need more memory correct?  If so, it might make some sense to have a separate array for those 4-bytes-per-property things, with the same order as the jsid array.  That would reduce the 64-bit memory usage.  Followup is ok for this part.
> 3) Are my claims about the 20k and 40k/80k being across all bindings together correct?

Will separate that to another array in a followup.

> "initialization".
> 
> Is this enforced somehow (e.g. via static_asserts somewhere)?  This is the sort of non-local thing that would be really easy to mess up by accident, especially since codegen has no indication that _it_ needs to match the order here.
> 
> Also, this should probably explain _why_ the two orders should be kept in sync.  It's not at all obvious to me that it needs to be.

The comment is invalid, it's from my previous version which I didn't remove.

Comment 41

[Boris Zbarsky [:bzbarsky]]

> NativePropertiesN.XxxIds() -> rename to XxxPropertyInfos()?

Yes, I think so.

> NativePropertiesN.idsLength -> idsLength is a bit strange now, how about length?

Oh, I thought I had commented on that.  That may be one of the comments mozreview lost and I failed to restore...

Anyway, this should be called propertyInfoCount, probably.

> Duo.mIds -> Duo.mPropertyInfos?

Yes, please.

> NativePropertiesN.sortedPropertyIndices -> what if remove the extra "Property" to "sortedIndices"?

I can live with that if we clearly document what they're indices into, but if we can come up with a name that makes it clear that these are related to the propertyinfo array, I'd really prefer that.  I assume sortedPropertyIndices just feels too long?  Is it being a problem in practice?

Comment 42

[Ting-Yu Chou [:ting] (away)]

Attachment: Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

Review commit: https://reviewboard.mozilla.org/r/151634/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/151634/

Comment 43

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/3-4/

Comment 44

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review154676

> Preexisting, but constants shouldn't be on instances.  Please file a followup, ok?

Fixed, both here and XrayResolveProperty().

Comment 45

[Ting-Yu Chou [:ting] (away)]

(In reply to Boris Zbarsky [:bz] (if a patch has no decent message, automatic r-) from comment #41)
> the propertyinfo array, I'd really prefer that.  I assume
> sortedPropertyIndices just feels too long?  Is it being a problem in
> practice?

No, just thought we can remove the repetition when I read nativeProperties->sortedPropertyIndices. I'll leave it as it is.

Comment 46

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review156908

::: dom/bindings/BindingUtils.cpp:1141
(Diff revisions 2 - 4)
>  static int
> -CompareId(const void* aElement1, const void* aElement2, void* aClosure)
> +CompareIdsAtIndices(const void* aElement1, const void* aElement2, void* aClosure)
>  {
>    const uint16_t index1 = *static_cast<const uint16_t*>(aElement1);
>    const uint16_t index2 = *static_cast<const uint16_t*>(aElement2);
> -  const PropertyId* ids = static_cast<PropertyId*>(aClosure);
> +  const PropertyInfo* ids = static_cast<PropertyInfo*>(aClosure);

s/ids/infos/

::: dom/bindings/BindingUtils.cpp:1150
(Diff revisions 2 - 4)
>    return JSID_BITS(ids[index1].id) < JSID_BITS(ids[index2].id) ? -1 : 1;
>  }
>  
>  template <typename SpecT>
>  static bool
> -InitIdsInternal(JSContext* cx, const Prefable<SpecT>* pref, PropertyId* ids,
> +InitIdsInternal(JSContext* cx, const Prefable<SpecT>* pref, PropertyInfo* ids,

s/ids/infos/

::: dom/bindings/BindingUtils.cpp:1156
(Diff revisions 2 - 4)
>                  PropertyType type)
>  {
>    MOZ_ASSERT(pref);
>    MOZ_ASSERT(pref->specs);
>  
> -  const SpecT* spec;
> +  // The index into pref.

How about:

    // Index of the Prefable that contains the id for the current PropertyInfo.

::: dom/bindings/BindingUtils.cpp:1163
(Diff revisions 2 - 4)
>  
>    do {
>      // We ignore whether the set of ids is enabled and just intern all the IDs,
>      // because this is only done once per application runtime.
> -    spec = pref->specs;
> +    const SpecT* spec = pref->specs;
> +    // The index into spec.

// Index of the property/function/constant spec for our current PropertyInfo in the "specs" array of the relevant Prefable.

::: dom/bindings/BindingUtils.cpp:1206
(Diff revisions 2 - 4)
>    // Initialize and sort the index array.
> -  uint16_t* index = const_cast<uint16_t*>(nativeProperties->idsSortedIndex);
> -  for (unsigned int i = 0; i < nativeProperties->idsLength; ++i) {
> -    index[i] = i;
> -  }
> -  NS_QuickSort(index, nativeProperties->idsLength, sizeof(uint16_t), CompareId,
> +  uint16_t* indices = nativeProperties->sortedPropertyIndices;
> +  for (unsigned int i = 0; i < nativeProperties->propertyInfoCount; ++i) {
> +    indices[i] = i;
> +  }
> +  // CompareIdsAtIndices() doesn't actually modify the PropertyInfo array, which

s/which/so/

::: dom/bindings/BindingUtils.cpp:1482
(Diff revisions 2 - 4)
> -struct IdComparator
> +struct IdToIndexComparator
>  {
> +  // The id we're searching for.
>    const jsid& mId;
> -  const PropertyId* mIds;
> -  explicit IdComparator(const jsid& aId, const PropertyId* aIds) :
> +  // The list of ids we're searching in.
> +  const PropertyInfo* mIds;

mInfos, right?  It's a list of PropertyInfos, not ids.

::: dom/bindings/BindingUtils.cpp:1504
(Diff revisions 2 - 4)
> +    return Resolver(cx, wrapper, obj, id, pref, pref.specs[found.specIndex],  \
>                      desc, cacheOnHolder);                                     \
>    }
>  
>  static bool
>  XrayResolveProperty(JSContext* cx, JS::Handle<JSObject*> wrapper,

So this is never called with type set to eGlobalInterfacePrototype, right?  Please assert that up front, since later code (e.g. for constants) depends on this.

::: dom/bindings/BindingUtils.cpp:1754
(Diff revisions 2 - 4)
>      if (type == eGlobalInterfacePrototype) {
>        return true;
>      }
>    }
>  
> +  if (nativeProperties.regular &&

This is not quite right.  The old code does unforgeable properties before it calls the nativePropertyHooks->mResolveOwnProperty callback.  This prevents names provided by that callback from shadowing unforgeable properties.  But this patch is reversing that order, which is wrong.

I _think_ it's not testable for now because the only interfaces which have an mResolveOwnProperty and unforgeables are HTMLDocument and Window.  And Window never resolves names that might collide with unforgeables, while document delegates ResolveOwnProperty to to getOwnPropertyDescriptor which already checks unforgeables anyway.  But it's a footgun waiting to happen.

I'm not quite sure how best to fix this so far...  Maybe what we should do is binary-search for the id up front, check whether the resulting thing is an unforgeable, if so resolve it and return as needed.  Then do the mResolveOwnProperty stuff and whatnot, then go back to "try to resolve this property" but using the id we already found.

::: dom/bindings/BindingUtils.cpp:1788
(Diff revisions 2 - 4)
>  
> -template<typename SpecT>
> +template<typename SpecType>
>  bool
>  XrayAppendPropertyKeys(JSContext* cx, JS::Handle<JSObject*> obj,
> -                       const Prefable<const SpecT>* pref,
> -                       const PropertyId* ids, unsigned flags,
> +                       const Prefable<const SpecType>* pref,
> +                       const PropertyInfo* ids, unsigned flags,

s/ids/infos/

::: dom/bindings/BindingUtils.cpp:1811
(Diff revisions 2 - 4)
> +    if (!(++pref)->specs) {
> +      break;
> +    }
> +    // Advance ids if the previous pref is disabled.
> +    if (!prefIsEnabled) {
> +      ids += pref->specs - (pref - 1)->specs - 1;

Document that the -1 is because the list between (pref-1)->specs and pref->specs includes the end-of-list terminator for (pref-1)->specs?

::: dom/bindings/BindingUtils.cpp:1839
(Diff revisions 2 - 4)
>      }
> -  } while ((++pref)->specs);
> +    if (!(++pref)->specs) {
> +      break;
> +    }
> +    if (!prefIsEnabled) {
> +      ids += pref->specs - (pref - 1)->specs - 1;

Again, document where the -1 comes from.

::: dom/bindings/Codegen.py:2243
(Diff revisions 2 - 4)
>                  prefableSpecs.append(prefableWithoutDisablersTemplate %
>                                       (name, len(specs)))
>  
>          switchToCondition(self, lastCondition)
>  
> +        numSpecsOfPrefable = 0

numSpecsInCurPrefable?

::: dom/bindings/Codegen.py:2244
(Diff revisions 2 - 4)
>                                       (name, len(specs)))
>  
>          switchToCondition(self, lastCondition)
>  
> +        numSpecsOfPrefable = 0
> +        maxNumSpecsOfPrefable = 0

maxNumSpecsInPrefable?

::: dom/bindings/Codegen.py:2304
(Diff revisions 2 - 4)
> +                static_assert(${maxNumSpecsOfPrefable} <= (1 << NUM_BITS_PROPERTY_INFO_SPEC_INDEX) - 1,
> +                              "We won't fit");
> +
> +                """,
> +                arrays=arrays,
> +                numPrefableSpecs=len(prefableSpecs)-1,

Why is the -1 there?  Why is it not there for the maxNumSpecsInPrefable case?

Seems to me that we should be asserting that any prefable indes and any spec index fits.  The max index is 1 less than the count.  So we could just assert that the counts are <= (1 << numbits), right?

And it would be nice to have the assertion messages be a bit more explicit: "We have a prefable index that is >= (1 << NUM_BITS_PROPERTY_INFO_PREF_INDEX)" and similar for spec index.

::: dom/bindings/Codegen.py:2910
(Diff revisions 2 - 4)
> +                    pre=pre)
> +                if iteratorAliasIndex >= 0:
> +                    post = fill(
> +                        """
> +                        $*{post}
> +                        static_assert(${iteratorAliasIndex} < (1 << (CHAR_BIT * sizeof(${name}.iteratorAliasMethodIndex) - 1)) - 1,

Please document where all these -1 come from.  Looks fishy to me for that innermost -1; why is it there?

::: dom/bindings/Codegen.py:2910
(Diff revisions 2 - 4)
> +                    pre=pre)
> +                if iteratorAliasIndex >= 0:
> +                    post = fill(
> +                        """
> +                        $*{post}
> +                        static_assert(${iteratorAliasIndex} < (1 << (CHAR_BIT * sizeof(${name}.iteratorAliasMethodIndex) - 1)) - 1,

Should probably be 1ull, right?

::: dom/bindings/Codegen.py:2911
(Diff revisions 2 - 4)
> +                if iteratorAliasIndex >= 0:
> +                    post = fill(
> +                        """
> +                        $*{post}
> +                        static_assert(${iteratorAliasIndex} < (1 << (CHAR_BIT * sizeof(${name}.iteratorAliasMethodIndex) - 1)) - 1,
> +                                      "We won't fit");

Better message.

::: dom/bindings/Codegen.py:2919
(Diff revisions 2 - 4)
> +                        iteratorAliasIndex=iteratorAliasIndex,
> +                        name=name)
> +                post = fill(
> +                    """
> +                    $*{post}
> +                    static_assert(${numIds} <= (1 << CHAR_BIT * sizeof(${name}.propertyInfoCount)) - 1,

How about using `<` and dropping the -1, for clarity?

::: dom/bindings/Codegen.py:2919
(Diff revisions 2 - 4)
> +                        iteratorAliasIndex=iteratorAliasIndex,
> +                        name=name)
> +                post = fill(
> +                    """
> +                    $*{post}
> +                    static_assert(${numIds} <= (1 << CHAR_BIT * sizeof(${name}.propertyInfoCount)) - 1,

Again, 1ull.

::: dom/bindings/Codegen.py:2920
(Diff revisions 2 - 4)
> +                        name=name)
> +                post = fill(
> +                    """
> +                    $*{post}
> +                    static_assert(${numIds} <= (1 << CHAR_BIT * sizeof(${name}.propertyInfoCount)) - 1,
> +                                  "We won't fit");

Better message.

::: dom/bindings/DOMJSClass.h:199
(Diff revisions 2 - 4)
> +  uint32_t prefIndex: NUM_BITS_PROPERTY_INFO_PREF_INDEX;
> +  // The index to the corresponding spec in Duo.mPrefables[prefIndex].specs[].
> +  uint32_t specIndex: NUM_BITS_PROPERTY_INFO_SPEC_INDEX;
>  };
>  
> -// Conceptually, NativeProperties has seven (Prefable<T>*, PropertyId*) duos
> +static_assert(ePropertyTypeCount <= 1 << NUM_BITS_PROPERTY_INFO_TYPE,

1ull.

::: dom/bindings/DOMJSClass.h:200
(Diff revisions 2 - 4)
> +  // The index to the corresponding spec in Duo.mPrefables[prefIndex].specs[].
> +  uint32_t specIndex: NUM_BITS_PROPERTY_INFO_SPEC_INDEX;
>  };
>  
> -// Conceptually, NativeProperties has seven (Prefable<T>*, PropertyId*) duos
> +static_assert(ePropertyTypeCount <= 1 << NUM_BITS_PROPERTY_INFO_TYPE,
> +              "We won't fit");

Better message.

::: dom/bindings/DOMJSClass.h:289
(Diff revisions 2 - 4)
>  #undef DO
>  
> -  // Use two bytes to store the array index and length because it's large enough
> +  // The index to the iterator method in Methods()->specs[].
> -  // for the native properties, and we can save a bit memory.
>    const int16_t iteratorAliasMethodIndex;
> +  // The number of strcut PropertyInfo that the duos manage.

"The number of PropertyInfo structs that the duos manage. This is the total count across all duos."

::: dom/bindings/DOMJSClass.h:292
(Diff revisions 2 - 4)
> -  // for the native properties, and we can save a bit memory.
>    const int16_t iteratorAliasMethodIndex;
> +  // The number of strcut PropertyInfo that the duos manage.
> +  const uint16_t propertyInfoCount;
> +  // The sorted indices array from sorting property ids, which will be used when
> +  // we binary search a property.

"for a property"

Comment 47

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8880278 [details]
Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

https://reviewboard.mozilla.org/r/151634/#review156912

r=me.  Thank you for writing these!

::: dom/bindings/test/test_dom_xrays.html:225
(Diff revision 1)
>    is(storage.getItem("foo"), null, "Should not have an item named 'foo' again");
>  
> +  // Non-static properties are not exposed on interface objects or instances.
> +  is(win.HTMLInputElement.checkValidity, undefined,
> +     "Shouldn't see non-static property on interface objects");
> +  is(Object.getOwnPropertyDescriptor(win.HTMLInputElement, "checkValidity"), undefined,

Might also be worth checking Object.getOwnPropertyNames(win.HTMLInputElement).indexOf("checkValidity") == -1 and similar for other cases.

Comment 48

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/4-5/

Comment 49

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8880278 [details]
Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/151634/diff/1-2/

Comment 50

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review156908

> This is not quite right.  The old code does unforgeable properties before it calls the nativePropertyHooks->mResolveOwnProperty callback.  This prevents names provided by that callback from shadowing unforgeable properties.  But this patch is reversing that order, which is wrong.
> 
> I _think_ it's not testable for now because the only interfaces which have an mResolveOwnProperty and unforgeables are HTMLDocument and Window.  And Window never resolves names that might collide with unforgeables, while document delegates ResolveOwnProperty to to getOwnPropertyDescriptor which already checks unforgeables anyway.  But it's a footgun waiting to happen.
> 
> I'm not quite sure how best to fix this so far...  Maybe what we should do is binary-search for the id up front, check whether the resulting thing is an unforgeable, if so resolve it and return as needed.  Then do the mResolveOwnProperty stuff and whatnot, then go back to "try to resolve this property" but using the id we already found.

I guess this means it is also not OK if the code is done before calling nativePropertyHooks->mResolveOwnProperty, because then the names provided by that callback which are collided will be shadowed. Am I correct?

I am off this afternoon, probably won't be able to address this issue today.

Comment 51

[Boris Zbarsky [:bzbarsky]]

> because then the names provided by that callback which are collided will be shadowed. Am I correct?

Right.  The resolveOwnProperty callback, if it matches for the given id, should shadow the things on the proto chain.

Should I be looking at the review request from comment 48, or holding off for now?

Comment 52

[Ting-Yu Chou [:ting] (away)]

Yes, please, if you have time. I will split XrayResolveProperty() to two functions, one for searching and one for resolving, and I expect the other parts should remain the same.

Comment 53

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/5-6/

Comment 54

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8880278 [details]
Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/151634/diff/2-3/

Comment 55

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review157016

This addresses all the comments except the unforgeables bit, thank you!

::: dom/bindings/BindingUtils.cpp:1813
(Diff revisions 4 - 6)
>      // Break if we have reached the end of pref.
>      if (!(++pref)->specs) {
>        break;
>      }
> -    // Advance ids if the previous pref is disabled.
> +    // Advance infos if the previous pref is disabled. The -1 is required
> +    // because there is an end-of-list terminator between perf->specs and

"pref->specs"

::: dom/bindings/BindingUtils.cpp:1814
(Diff revisions 4 - 6)
>      if (!(++pref)->specs) {
>        break;
>      }
> -    // Advance ids if the previous pref is disabled.
> +    // Advance infos if the previous pref is disabled. The -1 is required
> +    // because there is an end-of-list terminator between perf->specs and
> +    // (perf - 1)->specs.

"pref - 1"

::: dom/bindings/BindingUtils.cpp:1845
(Diff revisions 4 - 6)
> +    // Break if we have reached the end of pref.
>      if (!(++pref)->specs) {
>        break;
>      }
> +    // Advance infos if the previous pref is disabled. The -1 is required
> +    // because there is an end-of-list terminator between perf->specs and

"pref"

::: dom/bindings/BindingUtils.cpp:1846
(Diff revisions 4 - 6)
>      if (!(++pref)->specs) {
>        break;
>      }
> +    // Advance infos if the previous pref is disabled. The -1 is required
> +    // because there is an end-of-list terminator between perf->specs and
> +    // (perf - 1)->specs.

"pref"

::: dom/bindings/Codegen.py:2908
(Diff revisions 4 - 6)
>                      """,
>                      name=name,
>                      size=idsOffset,
>                      pre=pre)
> -                if iteratorAliasIndex >= 0:
> +                if iteratorAliasIndex > 0:
> +                    # The iteratorAliasMethodIndex is a singed integer, which

s/which/so/.  Thank you for documenting this; it was entirely non-obvious!

Comment 56

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/6-7/

Comment 57

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8880278 [details]
Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/151634/diff/3-4/

Comment 58

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

https://reviewboard.mozilla.org/r/148948/#review158230

Thank you!  r=me with the two nits below.

::: dom/bindings/BindingUtils.cpp:1392
(Diff revisions 6 - 7)
> +    return JSID_BITS(mId) < JSID_BITS(mInfos[aIndex].id) ? -1 : 1;
> +  }
> +};
> +
> +static const PropertyInfo*
> +XraySearchOwnPropertyInfo(JSContext* cx, JS::Handle<jsid> id,

XrayFindOwnPropertyInfo, please.

::: dom/bindings/Codegen.py:2908
(Diff revisions 6 - 7)
>                      """,
>                      name=name,
>                      size=idsOffset,
>                      pre=pre)
>                  if iteratorAliasIndex > 0:
> -                    # The iteratorAliasMethodIndex is a singed integer, which
> +                    # The iteratorAliasMethodIndex is a singed integer, so the

"signed", not "singed".

Comment 59

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8877504 [details]
Bug 1348099 part 1 - Binary search property id when resolve DOM Xrays own property.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/148948/diff/7-8/

Comment 60

[Ting-Yu Chou [:ting] (away)]

Comment on attachment 8880278 [details]
Bug 1348099 part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/151634/diff/4-5/

Comment 61

[Ting-Yu Chou [:ting] (away)]

Running mochitest on debug version trigger the assertion in CompareIdsAtIndices() which there are two properties have the same jsid:

06:14:48     INFO -  GECKO(1832) | Assertion failure: (infos[index1].id.asBits) != (infos[index2].id.asBits), at z:/build/build/src/dom/bindings/BindingUtils.cpp:1143
06:15:00     INFO -  GECKO(1832) | #01: NS_QuickSort [xpcom/ds/nsQuickSort.cpp:143]
06:15:00     INFO -  GECKO(1832) | #02: mozilla::dom::InitIds(JSContext *,mozilla::dom::NativePropertiesN<7> const *) [dom/bindings/BindingUtils.cpp:1209]
06:15:00     INFO -  GECKO(1832) | #03: mozilla::dom::TestInterfaceJSBinding::CreateInterfaceObjects(JSContext *,JS::Handle<JSObject *>,mozilla::dom::ProtoAndIfaceCache &,bool) [obj-firefox/dom/bindings/TestInterfaceJSBinding.cpp:5137]
06:15:00     INFO -  GECKO(1832) | #04: mozilla::dom::TestInterfaceJSBinding::GetConstructorObjectHandle(JSContext *,bool) [obj-firefox/dom/bindings/TestInterfaceJSBinding.cpp:5208]
06:15:00     INFO -  GECKO(1832) | #05: mozilla::dom::TestInterfaceJSBinding::DefineDOMInterface(JSContext *,JS::Handle<JSObject *>,JS::Handle<jsid>,bool) [obj-firefox/dom/bindings/TestInterfaceJSBinding.cpp:4936]
06:15:00     INFO -  GECKO(1832) | #06: mozilla::dom::WebIDLGlobalNameHash::DefineIfEnabled(JSContext *,JS::Handle<JSObject *>,JS::Handle<jsid>,JS::MutableHandle<JS::PropertyDescriptor>,bool *) [dom/bindings/WebIDLGlobalNameHash.cpp:281]
06:15:00     INFO -  GECKO(1832) | #07: nsGlobalWindow::DoResolve(JSContext *,JS::Handle<JSObject *>,JS::Handle<jsid>,JS::MutableHandle<JS::PropertyDescriptor>) [dom/base/nsGlobalWindow.cpp:5154]
06:15:00     INFO -  GECKO(1832) | #08: mozilla::dom::WindowBinding::_resolve [obj-firefox/dom/bindings/WindowBinding.cpp:16626]
06:15:00     INFO -  GECKO(1832) | #09: js::CallResolveOp [js/src/vm/NativeObject-inl.h:685]

Comment 62

[Boris Zbarsky [:bzbarsky]]

What is the id in question?  js::DumpId(infos[index1].id) and same thing for index2.

Comment 63

[Boris Zbarsky [:bzbarsky]]

Actually, I'm guessing it's "_clearCachedDictionaryArgValue" or "_clearCachedDictionaryAttrValue" or "_clearCachedCachedAttrValue".  Those are present in both sChromeUnforgeableMethods_specs and sChromeMethods_specs without this patch.

That's clearly a bug in the codegen; those bits in MethodDefiner should only be set up if "not unforgeable".

That said, I was suddenly worried that IDL allowed the same name for a static and non-static thing.  Looks like it does not, but if it ever starts allowing that we'll need to change to separate lists for static and non-static stuff...

Comment 64

[Ting-Yu Chou [:ting] (away)]

I am building locally to check what's happening, will update later.

Comment 65

[Ting-Yu Chou [:ting] (away)]

I guess it's the code here:

  https://searchfox.org/mozilla-central/rev/152c0296f8a10f81185ee88dfb4114ec3882b4c6/dom/bindings/Codegen.py#2548-2558

that needs to consider whether unforgeable is true or not.

Comment 66

[Ting-Yu Chou [:ting] (away)]

Attachment: Bug 1348099 part 3 - Fix the codegen so the methods for clearing cached attribute values are not unforgeable.

Current codegen list the methods for clearing cached attribute values in both
chrome only unforgeable methods and chrome only normal methods, but they should
exist only in the normal ones.

Review commit: https://reviewboard.mozilla.org/r/153242/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/153242/

Comment 67

[Ting-Yu Chou [:ting] (away)]

(In reply to Boris Zbarsky [:bz] (if a patch has no decent message, automatic r-) from comment #63)
> That said, I was suddenly worried that IDL allowed the same name for a
> static and non-static thing.  Looks like it does not, but if it ever starts
> allowing that we'll need to change to separate lists for static and
> non-static stuff...

This is what I found from the spec [1]:
  
  If a regular operation or static operation defined on an interface has an identifier that is the same as the identifier of another operation on that interface of the same kind (regular or static), then the operation is said to be overloaded.

Hopefully it will not change...

[1] https://heycam.github.io/webidl/#idl-overloading

Comment 68

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8882126 [details]
Bug 1348099 part 3 - Fix the codegen so the methods for clearing cached attribute values are not unforgeable.

https://reviewboard.mozilla.org/r/153242/#review158448

r=me

Comment 69

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/3c9580f79684
part 1 - Binary search property id when resolve DOM Xrays own property. r=bz
https://hg.mozilla.org/integration/autoland/rev/c2b306e94329
part 2 - Add tests for DOM Xrays that properties are exposed to only proper object types. r=bz
https://hg.mozilla.org/integration/autoland/rev/246124863988
part 3 - Fix the codegen so the methods for clearing cached attribute values are not unforgeable. r=bz

Comment 70

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3c9580f79684
https://hg.mozilla.org/mozilla-central/rev/c2b306e94329
https://hg.mozilla.org/mozilla-central/rev/246124863988