697343 - Array.prototype.slice is slow for NodeLists

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Trev]

Attachment: makeArray benchmark

User Agent: Mozilla/5.0 (Windows NT 5.1; rv:9.0a2) Gecko/20111023 Firefox/9.0a2
Build ID: 20111023042022

Steps to reproduce:

In the Peacekeeper DOM tests, it uses jQuery to do some querySelectorAll() tests.  If I just use straight querySelectorAll, Firefox is faster than Chrome.  But throwing on jQuery, Firefox is slower.  It looks like the main culprit is the code that converts the NodeList result of querySelectorAll() into an array.  Chrome is twice as fast as Firefox in that code.  If I modify jQuery to not do the conversion, Firefox is still slower but not by very much.

The conversion code looks like:
var makeArray = function( array, results ) {
    array = Array.prototype.slice.call( array, 0 );

    if ( results ) {
        results.push.apply( results, array );
        return results;
    }

    return array;
};

Most of the slow down is in the Array.prototype.slice.call() part.

I'm attaching a benchmark that grabs a NodeList (one that Peacekeeper uses) and then calls makeArray on it 5000 times.  My numbers are:

Nightly: 204ms
Chrome: 111ms

This bug is possibly a dup of Bug 656813 but that talks specifically about optimizing Array.prototype.slice for the arguments object.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Hmm.  Over here I see times more like 50ms (Chrome) vs 80ms (Nightly).  But I guess that's close enough to your numbers.

Thanks to the nice "run with shark" button, we now know that 80% of the time is the GetElement call that array_slice makes.  This time breaks down as:

  8% self time in GetElement
 38% under proxy_LookupGeneric (which has 8% self time, then calls the proxy's has()
     hook, which forwards to js::ProxyHandler::has, which has 8% self time and then calls
     getPropertyDescriptor which calls getOwnPropertyDescriptor, which has 15% self time,
     3% js_GCThingIsMarked, 3% js::UnwrapObject, and 1.5% getting the actual value to put
     in the descriptor, since this is a value property.
 24% under proxy_GetGeneric (8% self time, and then the actual call into get() on the
     nodelist proxy which does the work).

Some observations:

1)  We should consider implementing a has() hook on the nodelist proxies that doesn't do
    all the property descriptor work.
2)  The only reason we need to do a lookup in the first place is to avoid holes, right? 
    I wonder whether we can do that better, somehow.  Note that for a NodeList there is
    in fact no guarantee of no holes below length (because someone can override length). 
    But maybe we can be smart here somehow?
3)  A good bit of the self time in the proxy_*Generic methods is the
    js_CheckForStringIndex stuff.  Jeff, it'd be really nice if we could avoid that!

Comment 2

[Boris Zbarsky [:bzbarsky]]

I wonder whether it would make sense to have an internal "get by index" API on all JSObjects that has a way to report "no prop like that"...  That's what the array code _really_ wants here.

Comment 3

[Boris Zbarsky [:bzbarsky]]

So yeah, #1 from comment 1 helps bit; at that point we're down to 60-65ms on my machine for the testcase.  Other obvious sources of fluff here after fixing that (on a lower baseline, rememeber!):

* 4% calling ensureDenseArrayElement from SetArrayElement.  But in this case we've already
  ensured the array capacity, as far as I can tell.  Futhermore, we know we have a dense
  array, right?  Can we just fast-path the relevant parts of SetElement in array_slice?
* 28% under proxy_GetGeneric, of which only 19% makes it to the get() hook on the nodelist
  proxy.  The rest is self time in proxy_GetGeneric and js_CheckForStringIndex.  That self
  time largely seems to be Proxy::get doing the AutoPendingProxyOperation thing and
  function call overhead.
* 27% under proxy_LookupGeneric; this time self time is 11% and js_CheckForStringIndex is
  still 1%.  The self time is function call overhead and more AutoPendingProxyOperation
  stuff.
* 4% is function call overhead for the has() hook on the nodelist proxy, which forwards
  to hasOwn(). I suppose I could save some of this by inlining the hasOwn() bit into
  has()...
* 11% is the nodelist hasOwn implementation.

Comment 4

[Boris Zbarsky [:bzbarsky]]

I filed bug 697351 on adding a has() trap implementation for nodelists.  But I still think that a combined "get and return whether it was really there" method would win big here.

Comment 5

[Trev]

It looks like there is a difference between MacOSX and Windows XP.  If I run the test in XP, Nightly does roughly 200, Aurora does roughly 210, and Chrome does roughly 110.  If I run the test on Mac, Aurora does roughly 100 and Chrome does roughly 90.

I've got a Windows 7 box at work and I'll see if it is similar to XP or to Mac.

Comment 6

[Boris Zbarsky [:bzbarsky]]

It'll almost certainly be like XP.

Now if you try one of the 64-bit Windows builds, that may show a difference.  I just tried this in a nightly on Mac with 32-bit mode forced, and it's a lot slower that way than in 64-bit mode.  My profiling above was in 64-bit mode.

I guess I should spin up a 32-bit opt build and see what things look like.  Oh, Chrome on Mac is 32-bit.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Looks like shark hooks don't work in a 32-bit build.  :(  So no profiling for now.

Comment 8

[Trev]

I don't have a 64-bit machine, so I can't try the 64-bit builds.  But in Windows 7, I'm seeing Nightly with 130 and Chrome with 85.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Hmm.  So in the attached benchmark, |nodes| has length 108.  There are 5000 iterations, so |result| should end up with 54e4 elements in it, right?

That would be 432e4 bytes or 4.3MB for that array in our implementation, but only half in V8 (because it uses 32-bit slots).

How big are your L2/L3 caches on the machines involved?  Is it possible that you're blowing out the cache on the XP machine but not the Win7 or Mac?

Comment 10

[Trev]

(In reply to Boris Zbarsky (:bz) from comment #9)
> Hmm.  So in the attached benchmark, |nodes| has length 108.  There are 5000
> iterations, so |result| should end up with 54e4 elements in it, right?
> 
It resets result to an empty array for each iteration, so it should only be 108.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Oh, indeed. I missed that line.  Then I have no idea what to make of your Win7 results....

Comment 12

[Trev]

With the fix for bug 697351, my nightly time went down to 160 on XP.

I did find a bug in the benchmark.  Each time you press "Run" the result will slowly increase.  This is because it creates a div and appends it to the dom and the querySelector finds all divs.  So each run has one more div to deal with.  I'll upload a fix for that.

Comment 13

[Trev]

Attachment: makeArray benchmark

Comment 14

[Boris Zbarsky [:bzbarsky]]

The patches in bug 698495 (which do what comment 4 suggests) speed this up a good bit.  The new profile shows:

  7% self time in array_slice
  8% self time in GetElement (which is presumably at least partly the checks it does up
     front).
 47% in or under proxy_GetElementIfPresent (11% self time, mostly the "are we in a proxy
     op?" tracker, 19% self time in the getElementIfPresent proxy hook; that includes the
     call overhead and whatever gets inlined into it, 7% GetNodeAt on the nsINodeList, 5%
     js_GCThingIsMarked, 4% js::UnwrapObject) 
 12% in SetArrayElement.
 13% under js::array_push (mostly array_push_slowly).

So remaining speedups would mostly come from optimizations to proxies, SetArrayElement, and maybe GetElement.

I wonder whether we could factor out the "header" part of GetElement and only do it once per loop.  That code is checking what sort of object we're working with, and that should not change as we loop over it getting elements....

Perhaps the whole loop walk should become a template method templated over some sort of traits struct that has a callback that does whatever needs to be done with each element.

Comment 15

[Boris Zbarsky [:bzbarsky]]

I filed bug 699323 on speeding up SetArrayElement and bug 699324 on further GetElement improvements.

Comment 16

[David Bruant]

Is it still the case with new bindings?
Is it still the case with the recent proxy refactoring?
Would self-hosting of Array.prototype.slice help?

Comment 17

[Boris Zbarsky [:bzbarsky]]

> Is it still the case with new bindings?

You mean the WebIDL ones?  They don't change things much here.

> Is it still the case with the recent proxy refactoring?

Not sure what you mean.  The performance on current tip (with the non-webidl lists), is way slower than Firefox 10.  Firefox 10 was a lot faster than Firefox 9 because I fixed bug 697351 and bug 698495.  The other two bugs blocking this one are the other obvious performance hotspots here, and are unfixed.

It looks like someone has regressed this significantly from Firefox 10.  :(

> Would self-hosting of Array.prototype.slice help?

Modify the attached testcase and measure?

Comment 18

[Boris Zbarsky [:bzbarsky]]

Looks like there was a major regression going from Firefox 14 to Firefox 15.

Comment 19

[Boris Zbarsky [:bzbarsky]]

I filed bug 795778 on that regression.

Comment 20

[Boris Zbarsky [:bzbarsky]]

So I have a modest proposal for making this fast, since jQuery runs into this a lot:

1)  We nix getElementIfPresent.
2)  We add a sliceThyselfIntoArg (bikeshedding welcome) hook that gets passed an object
    allocated via NewDenseAllocatedArray and start/end indices.  We create a default
    slowish impl for this.
3)  We add some friendapi for quickly putting things into an object as in #2.  This should
    _not_ be the generic-fest that is SetArrayElement!
4)  DOM proxies (and anyone else who cares, e.g. typed arrays) implement the new slice
    API, using item #3.
5)  We presumably get rid of JS_GetElementIfPresent.  Or just give it a slow-path impl,
    since it will be unused internally.

waldo is on board but obviously has no time to work on this.  I'm happy to help with the DOM end, but I'm not quite sure what item #3 should look like here for optimal performance while keeping a fig leaf of safety.  Maybe it's a new struct that encapsulates a NewDenseAllocatedArray, so we're not dealing with a APIs that we can pass some other JSObject* to and screw up?

Comment 21

[Boris Zbarsky [:bzbarsky]]

One open question is what the TI bits of this will look like, for purposes of the API in step #3 above.  I could use some help on what's really needed there too.

Comment 22

[Boris Zbarsky [:bzbarsky]]

Tom, does comment 20 item 3 sound like something you have time to do in the short term?  I can do the rest of that comment, I believe, if that piece happens correctly.

Comment 23

[Tom S [:evilpie]]

Ok, I will get to it.

Comment 24

[Naveed Ihsanullah [:naveed]]

Jan could you help bz with https://bugzilla.mozilla.org/show_bug.cgi?id=697343#c21?

Comment 25

[Jan de Mooij [:jandem]]

(In reply to Naveed Ihsanullah [:naveed] from comment #24)
> Jan could you help bz with
> https://bugzilla.mozilla.org/show_bug.cgi?id=697343#c21?

Tom, thanks for looking into this, let me know if you have any questions.

One thing I noticed is that SetArrayElement is not only slow but also wrong for slice. I think the spec wants us to ignore any setters on the prototype, so a setDenseElementWithType or defineElement should work too and is a lot faster.

Comment 26

[Tom S [:evilpie]]

Attachment: Remove JS_GetElementIfPresent

Comment 27

[Tom S [:evilpie]]

Attachment: Introduce "slice" hook

Comment 28

[Tom S [:evilpie]]

Attachment: The dom and optimization part.

1) Remove getElementIfPresent
Just removes the hook from everywhere and adds some compatible code now that it's gone.
2) Introduce "slice" hook
Introduces a slice hook that gets the begin, end and a preallocated result array. Implemented what I think is compatible with how it should behave as a BaseProxyHandler, I am not super sure about this that stuff, especially the policies.
3) The DOM parts
Kind of made some guessed at to how it could work. "UnwrapProxy" should be moved outside the loop, but I didn't look into that. Added a js::UnsafeDefineElement function and changed the code to call ensureDenseElement on the result array. (Not sure why that is even necessary with NewDenseAllocatedArray?)

Comment 29

[Jeff Walden [:Waldo]]

(In reply to Jan de Mooij [:jandem] from comment #25)
> One thing I noticed is that SetArrayElement is not only slow but also wrong
> for slice.

SetArrayElement is wrong overall, actually -- see bug 922301.

Comment 30

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8336837 [details] [diff] [review]
Remove JS_GetElementIfPresent

Why is this adding a getElement proxy hook on the DOMProxyHandler?  There is no such proxy hook, afaik, so all that code can go away entirely.

Comment 31

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8336841 [details] [diff] [review]
The dom and optimization part.

For what it's worth, I'm happy to take over the DOM part of this.  It can be a lot simpler (e.g. we don't have to define this hook at all if we have no indexed getter, we can in fact guarantee no holes, etc).

I'd just like us to pin down the exact slice() API first.  If people are OK with this unsafe function, then that's fine by me, but I would have done it as some struct that internally has a pointer to the relevant object so you can't accidentally invoke this setter on anything other than an object we preallocated....

Comment 32

[Tom S [:evilpie]]

Attachment: Remove JS_GetElementIfPresent v2

There is no Proxy :: getElement.

Comment 33

[Tom S [:evilpie]]

Attachment: The dom and optimization part. v2

Just rebased.

Comment 34

[Boris Zbarsky [:bzbarsky]]

Attachment: DOM bits v3

Tom, how do the js/src bits here look?

Comment 35

[Tom S [:evilpie]]

Comment on attachment 8337029 [details] [diff] [review]
DOM bits v3

Review of attachment 8337029 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good to me.

::: js/src/jsarray.cpp
@@ +157,5 @@
>   */
>  template<typename IndexType>
>  static inline bool
> +DoGetElement(JSContext *cx, HandleObject obj, IndexType index,
> +             HandleObject receiver, bool *hole, MutableHandleValue vp)

Put receiver after obj.

@@ +2771,5 @@
> +JS_FRIEND_API(bool)
> +js::SliceSlowly(JSContext* cx, HandleObject obj, uint32_t begin, uint32_t end,
> +                HandleObject receiver, HandleObject result)
> +{
> +    RootedId id(cx);

This seems dead.

::: js/src/jsfriendapi.h
@@ +1653,5 @@
> +JS_FRIEND_API(void)
> +UnsafeDefineElement(JSContext *cx, JS::HandleObject obj, uint32_t index, JS::HandleValue value);
> +
> +JS_FRIEND_API(bool)
> +SliceSlowly(JSContext* cx, JS::HandleObject obj, uint32_t begin, uint32_t end,

receiver after obj

Comment 36

[Boris Zbarsky [:bzbarsky]]

Attachment: DOM bits v4 (comment 35 addressed)

Comment 37

[Boris Zbarsky [:bzbarsky]]

Are we good to go on to the code review bits now?

Comment 38

[Tom S [:evilpie]]

I think so. Potential reviewers are Waldo, because he introduced GetElemenetIfPresent. Jan and maybe Brian for the DOM bits with the dense stuff.

Comment 39

[Jan de Mooij [:jandem]]

Comment on attachment 8336838 [details] [diff] [review]
Introduce "slice" hook

Review of attachment 8336838 [details] [diff] [review]:
-----------------------------------------------------------------

Nice! r=me with comments addressed.

::: js/src/builtin/TypedObject.cpp
@@ +2552,5 @@
>          TypedDatum::obj_deleteProperty,
>          TypedDatum::obj_deleteElement,
>          TypedDatum::obj_deleteSpecial,
>          nullptr, nullptr, // watch/unwatch
> +        nullptr,

Nit: add "// slice" like you did for the other ones.

::: js/src/jsarray.cpp
@@ +2733,5 @@
>          return false;
>      TryReuseArrayType(obj, narr);
>  
> +    js::SliceOp op = obj->getOps()->slice;
> +    if (op) {

Nit: if (js::SliceOp op = obj->getOps()->slice) {

@@ +2748,2 @@
>          if (!JS_CHECK_OPERATION_LIMIT(cx) ||
>              !GetElement(cx, obj, slot, &hole, &value)) {

Nit: pre-existing, but multi-line condition so please move the { to its own line while you're here.

::: js/src/jsproxy.cpp
@@ +364,5 @@
>      return true;
>  }
>  
>  bool
> +BaseProxyHandler::slice(JSContext *cx, HandleObject proxy, uint32_t begin, uint32_t end,

Can we add some shell tests for this? In particular one that tests both the present and !present paths. I see your other patch replaces this code, but it would still be good to have them.

::: js/xpconnect/src/xpcprivate.h
@@ +1134,5 @@
>          nullptr, /* deleteProperty */                                         \
>          nullptr, /* deleteElement */                                          \
>          nullptr, /* deleteSpecial */                                          \
>          nullptr, nullptr, /* watch/unwatch */                                 \
> +        nullptr,   /* slice */                                                \

Nit: remove 2 spaces between "nullptr," and "/*" so that it lines up better with the deleteSpecial line.

Comment 40

[Jan de Mooij [:jandem]]

Comment on attachment 8337173 [details] [diff] [review]
DOM bits v4 (comment 35 addressed)

Review of attachment 8337173 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsarray.cpp
@@ +2742,5 @@
>          return false;
>      TryReuseArrayType(obj, narr);
>  
>      js::SliceOp op = obj->getOps()->slice;
> +    if (op) { // xxx might need satisfy some other condition like !ObjectMayHaveExtraIndexedProperties(narr)?

I don't think this matters, narr is a brand new array and we can/must ignore setters on the prototype.

Comment 41

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8337173 [details] [diff] [review]
DOM bits v4 (comment 35 addressed)

Olli, can you review the codegen changes here?  Or would you prefer peterv does it?

Comment 42

[Brian Hackett [Laid off!]]

Comment on attachment 8337173 [details] [diff] [review]
DOM bits v4 (comment 35 addressed)

Review of attachment 8337173 [details] [diff] [review]:
-----------------------------------------------------------------

The JS changes here look fine.

Comment 43

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8337173 [details] [diff] [review]
DOM bits v4 (comment 35 addressed)

I think peterv should look at these codegen changes.
I'm not too familiar with the proxy magic.

Comment 44

[Jeff Walden [:Waldo]]

Comment on attachment 8336954 [details] [diff] [review]
Remove JS_GetElementIfPresent v2

Review of attachment 8336954 [details] [diff] [review]:
-----------------------------------------------------------------

So much death.  Awesome!

::: js/src/jsapi.cpp
@@ +3430,1 @@
>                         MutableHandleValue vp, bool* present)

This method is completely unused once the Codegen.py users die.  We should just remove it; we were the only ones who needed it, and it's really a one-off case of a more general problem, that we should solve more generally.

::: js/src/jsarray.cpp
@@ +138,2 @@
>  {
>      if (index == uint32_t(index))

Hmm, if |index|, truncated, isn't in the uint32_t range, the cast invokes undefined behavior.  File a bug to fix this, please.  Probably need an mfbt complement to DoubleIsInt32 for the DoubleIsUint32 case.

Comment 45

[Tom S [:evilpie]]

> This method is completely unused once the Codegen.py users die. 
> We should just remove it; we were the only ones who needed it, and it's really a one-off case of a more general > problem, that we should solve more generally.

We still need it right now, so I am not sure what you want me to do.

Comment 46

[Boris Zbarsky [:bzbarsky]]

> We still need it right now

We do?  Why?

Comment 47

[Tom S [:evilpie]]

You are right of course, your patch unlike mine doesn't use it.

Comment 48

[Tom S [:evilpie]]

Attachment: test

What do you think? I think I might add some other test from the DOM side, which uses NodeList and slice.

Comment 49

[Jeff Walden [:Waldo]]

This seems like it wants a jsapi-test, in order to test something with a slice hook defined, but still have it runnable in standalone builds.  Nothing wrong with a testcase using Proxy and all, it's just not a full test.  :-)

Comment 50

[Jan de Mooij [:jandem]]

Comment on attachment 8339270 [details] [diff] [review]
test

Review of attachment 8339270 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great, thanks! As Waldo said we could also add a jsapi-test, but not sure if it's necessary.

Comment 51

[Peter Van der Beken [:peterv]]

Comment on attachment 8337173 [details] [diff] [review]
DOM bits v4 (comment 35 addressed)

Review of attachment 8337173 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/bindings/Codegen.py
@@ +7300,5 @@
>      Base class for classes for calling an indexed or named special operation
>      (don't use this directly, use the derived classes below).
> +
> +    If checkFound is False, will just assert that the prop is found instead of
> +    checking.

"checking that it is before wrapping the value"?

@@ +7360,5 @@
>  class CGProxyIndexedOperation(CGProxySpecialOperation):
>      """
>      Class to generate a call to an indexed operation.
> +
> +    If doUnwrap is false, the caller is responsible for making sure a variable

s/false/False/

@@ +7362,5 @@
>      Class to generate a call to an indexed operation.
> +
> +    If doUnwrap is false, the caller is responsible for making sure a variable
> +    named 'self' holds the C++ object somewhere where the code we generate
> +    will see it.

Probably should document checkFound here too (if only to refer to CGProxySpecialOperation's definition?).

@@ +7385,5 @@
>  
>  class CGProxyIndexedGetter(CGProxyIndexedOperation):
>      """
>      Class to generate a call to an indexed getter. If templateValues is not None
>      the returned value will be wrapped with wrapForType using templateValues.

Same here for doUnwrap and checkFound?

::: js/src/jsarray.cpp
@@ +2757,5 @@
> +            return true;
> +        }
> +
> +        // Fallthrough
> +        JS_ASSERT(result == JSObject::ED_SPARSE);;

Probably should do s/;;/;/

Comment 52

[Tom S [:evilpie]]

I rebased the patches and pushed them to try: https://tbpl.mozilla.org/?tree=Try&rev=48fe04144482. I get some test failures that I can reproduce locally:
26437 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_alarms.html | Did not receive proper object
26443 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_browser.html | Didn't get mozbrowser
26449 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_embed-apps.html | Didn't get mozapp
26455 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_idle.html | Got an exception TypeError: window.navigator.addIdleObserver is not a function
26475 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_permissions.html | Did not receive proper object
26481 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_power.html | Did not receive proper object
26487 ERROR TEST-UNEXPECTED-FAIL | /tests/dom/permission/tests/test_systemXHR.html | Couldn't create systemXHR

I am not sure yet what is causing this.

Comment 53

[Boris Zbarsky [:bzbarsky]]

Tom and I debugged this.  The issue is that the new slice hook does:

    AutoEnterPolicy policy(cx, handler, proxy, JSID_VOIDHANDLE, BaseProxyHandler::GET, true);

and then in dom/permission/tests/file_framework.js we have code like this:

171     var expanded = SpecialPowers.unwrap(expand(el, access));
172     perms = perms.concat(expanded.slice(0));

In this case, the proxy seen in Proxy::slice has xpc::ChromeObjectWrapper as the handler.

So before, Proxy::getElementIfPresent used to enter the policy for the specific numeric IDs, which presumably worked because of the array-index special casing COWs do, but now we end up with !policy.allowed().

Bobby, what's a sane thing to do here?  Note that all the proxy handlers that are not for DOM proxies will end up doing the generic SliceSlowly which will end up doing normal gets and such which will check policies at that point...

Comment 54

[Jeff Walden [:Waldo]]

(In reply to Jan de Mooij [:jandem] from comment #50)
> As Waldo said we could also add a jsapi-test, but not sure if it's necessary.

I'd rather see one, and a relatively simple one without the DOM case's complexity, than not.

Comment 55

[Tom S [:evilpie]]

We could actually remove the Class hook and just do an IsProxy check and dispatch Proxy::slice from there, unless we really want the slice hook for something else.

Comment 56

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 3 (DOM bits) updated to review comments (v5)

Comment 57

[Bobby Holley (:bholley)]

(In reply to Boris Zbarsky [:bz] from comment #53)
> Bobby, what's a sane thing to do here?  Note that all the proxy handlers
> that are not for DOM proxies will end up doing the generic SliceSlowly which
> will end up doing normal gets and such which will check policies at that
> point...

Can we just fix the tests to not do that? I basically consider SpecialPowers wrappers to be an unsupported, YMMV kind of thing. Let's just manually copy the array or do the concat in chrome or something and then move on.

Comment 58

[Boris Zbarsky [:bzbarsky]]

> Can we just fix the tests to not do that? 

Is this a test-only issue?  As in, is there no way to get into this situation on a web page?

Comment 59

[Bobby Holley (:bholley)]

(In reply to Boris Zbarsky [:bz] from comment #58)
> > Can we just fix the tests to not do that? 
> 
> Is this a test-only issue?  As in, is there no way to get into this
> situation on a web page?

A situation where content has a COW and expects array.slice to work? It really depends on whether we have any COW-implemented APIs with consumers that do that. But since most of those APIs are in the process of being converted to WebIDL and aren't exposed to the web anyway, I'd prefer to not to speculatively support this. There are a jillion little gotchas that work strangely with COWs, and I don't think we should give this one special treatment just because of the SpecialPowers usage.

Comment 60

[Boris Zbarsky [:bzbarsky]]

> A situation where content has a COW and expects array.slice to work? 

Or more generally a situation where content has an object for which AutoEnterPolicy with JSID_VOIDHANDLE will give a different result than with a specific index id.  Is COW the only case in which this can happen, for starters?

Comment 61

[Bobby Holley (:bholley)]

(In reply to Boris Zbarsky [:bz] from comment #60)
> > A situation where content has a COW and expects array.slice to work? 
> 
> Or more generally a situation where content has an object for which
> AutoEnterPolicy with JSID_VOIDHANDLE will give a different result than with
> a specific index id.  Is COW the only case in which this can happen, for
> starters?

COWs are really the only potentially-content-exposed objects with an interesting security policy, and also the only way that typed arrays are ever accessible in any way to script that doesn't subsume them. So yes.

Comment 62

[Boris Zbarsky [:bzbarsky]]

OK, I see.

If we're fairly certain that this is the only Array COW that we're likely to run into, I'd be fine just changing the test, indeed.

Comment 63

[Tom S [:evilpie]]

I made some mistake in patch 2. Without part three we actually assert, because we are calling get and has directly from slice without entering their policies. I think we could fix it by calling Proxy::get and Proxy::has instead, or just ignoring it, because part 3 fixes it anyway.

Comment 64

[Tom S [:evilpie]]

Attachment: Remove getElementIfPresent v3

Comment 65

[Tom S [:evilpie]]

Attachment: Introduce "slice" hook v2

This includes a fix for the failing test. I also changed Proxy::slice to actually work, this part however will be replaced by the dom bits anyway.

Comment 66

[Boris Zbarsky [:bzbarsky]]

Tom, what's left to do here?  Just merging the DOM patch on top of your latest part 2?

Comment 67

[Tom S [:evilpie]]

Yes, that was my idea.

Comment 68

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8342438 [details] [diff] [review]
Introduce "slice" hook v2

r=me on the test change if you add a comment explaining that it's working around "expanded" being a COW and not behaving very much like an array.

Comment 69

[Tom S [:evilpie]]

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/bfe768b87464
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/4ef4764c1b55
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/0809370fabdb
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/22770b30545b

Comment 70

[Ryan VanderMeulen [:RyanVM]]

Backed out for Gaia UI test bustage.
https://hg.mozilla.org/integration/mozilla-inbound/rev/fbc0b4c30fd0

https://tbpl.mozilla.org/php/getParsedLog.php?id=31516303&tree=Mozilla-Inbound

Comment 71

[Tom S [:evilpie]]

12:27:39     INFO -  Traceback (most recent call last):
12:27:39     INFO -    File "/builds/slave/test/build/venv/local/lib/python2.7/site-packages/marionette/marionette_test.py", line 143, in run
12:27:39     INFO -      testMethod()
12:27:39     INFO -    File "/builds/slave/test/gaia/tests/python/gaia-ui-tests/gaiatest/tests/functional/messages/test_sms_contact_match.py", line 32, in test_contact_match
12:27:39     INFO -      self.assertEqual(self.contact['tel'][0]['value'], new_message.first_recipient_number_attribute)
12:27:39     INFO -  TEST-UNEXPECTED-FAIL | test_sms_contact_match.py test_sms_contact_match.TestContactMatch.test_contact_match | AssertionError: '55550283314' != u'gaia283381 test'

Boris assumes that there is some code in Gaia that uses .slice on COW arrays as well. I don't really know how to run these test, but just looking at the code for a slice call that could cause this would be very helpful.
Zack you are the last one blame here https://github.com/mozilla-b2g/gaia/blob/master/tests/python/gaia-ui-tests/gaiatest/tests/functional/messages/test_sms_contact_match.py, could you help me?

Comment 72

[Zac C (:zac)]

I think you ni? the wrong Zac here :)

Just looking at the failure; what happens in this test is that we type the name of a contact into the Messaging app and it goes into the gaia Contacts database to match the name to the contact. Then when it matches it pulls in the phone number of the contact and you can send the SMS. 

The failure is showing that it has inserted the contact's name in the HTML attribute where it should have been a phone number. This test is ordinarily very reliable.

It sounds like something deeper in the Messaging app has not handled this change. It's beyond me but I do know the guy to ask and I'm going to ni? him!

Comment 73

[Julien Wajsberg [:julienw]]

The issue is happening at [1].

We're slicing the mozContact result array. I admit I don't remember why we do this, possibly we didn't get a real array before using WebIDL? This piece of code is here for 8 months.

Hope this helps!

[1] https://github.com/mozilla-b2g/gaia/blob/master/apps/sms/js/contacts.js#L172

Comment 74

[Tom S [:evilpie]]

Thank you very much Julien for pinpointing this code. I think we should just fix it and carry on. Hopefully most b2g code is going to switch to WebIDL so that bugs like this don't happen in the future.

Comment 75

[Boris Zbarsky [:bzbarsky]]

Hmm.  mozContacts _is_ on webidl.  But DOMRequest sucks whether it's on WebIDL or not. 

In particular, the "Contacts:Find:Return:OK" case in receiveMessage calls this._convertContacts(contacts) and hands that off to the page directly via the DOMRequest, afaict, but _convertContacts creates a chrome array.  So this hands the page a COW, as far as I can tell.

Comment 76

[Reuben Morais [:reuben]]

Attachment: Kill a COW

Comment 77

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8344775 [details] [diff] [review]
Kill a COW

r=me asuming the new semantics are correct for GetAll:Next (which at first glance they are).

Comment 78

[Boris Zbarsky [:bzbarsky]]

Tom, want to do a try push with that addition?

Comment 79

[Tom S [:evilpie]]

https://tbpl.mozilla.org/?tree=Try&rev=90c57a3a77b9

Comment 80

[Boris Zbarsky [:bzbarsky]]

> I admit I don't remember why we do this, possibly we didn't get a real array before using
> WebIDL? 

Julien, if you're not getting a real array in an API that promises a real array, _please_ file bugs!  Would have let us catch the Contacts bug 8 months ago.  :(

Comment 81

[Reuben Morais [:reuben]]

https://hg.mozilla.org/integration/b2g-inbound/rev/920a681e6bb0

Comment 82

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/920a681e6bb0

Comment 83

[Boris Zbarsky [:bzbarsky]]

That try push looks green for Gu, and Reuben's patch has made it to inbound, so:

   https://hg.mozilla.org/integration/mozilla-inbound/rev/e0803c4ddc90
   https://hg.mozilla.org/integration/mozilla-inbound/rev/aa573b104bdf
   https://hg.mozilla.org/integration/mozilla-inbound/rev/0fbdff3a10e3
   https://hg.mozilla.org/integration/mozilla-inbound/rev/56eb22c6f6c7

Comment 84

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e0803c4ddc90
https://hg.mozilla.org/mozilla-central/rev/aa573b104bdf
https://hg.mozilla.org/mozilla-central/rev/0fbdff3a10e3
https://hg.mozilla.org/mozilla-central/rev/56eb22c6f6c7

Comment 85

[Julien Wajsberg [:julienw]]

(In reply to Boris Zbarsky [:bz] from comment #80)
> > I admit I don't remember why we do this, possibly we didn't get a real array before using
> > WebIDL? 
> 
> Julien, if you're not getting a real array in an API that promises a real
> array, _please_ file bugs!  Would have let us catch the Contacts bug 8
> months ago.  :(

I don't remember if this was the real issue ;) We're used to this strange idiosyncracies on the Web so I guess it didn't ring any bell back at the time.


(In reply to Boris Zbarsky [:bz] from comment #83)
> That try push looks green for Gu, and Reuben's patch has made it to inbound,

Here's a question from a Gecko newbie: was there an underlying cause that could bite us later? I feel like we fixed the one part where we had a test but other parts could fail...

Comment 86

[Boris Zbarsky [:bzbarsky]]

> We're used to this strange idiosyncracies on the Web 

That's the thing.  The "Web" means "lots of deployed browser engines you have no control over and just have to deal with".  But gaia is running on top of Gecko, and you know how to file Gecko bugs... and we try to fix them if they affect gaia.  So even if you have to work around something, _please_ report a bug on the underlying API so that it can be fixed and the workaround removed.

> was there an underlying cause that could bite us later?

There were two things interacting:

1) The contacts API was incorrectly returning a chrome object to the web page instead of a web page object.  In effect, instead of an array it was returning something that sort of quacked like an array sometimes, as long as you didn't look too carefully.

2) The patches in this bug made slice() on that precise sort of object no longer work.  See comment 57 and comment 59.

Bobby, I wonder whether we should consider making COW creating for an array fatal for a try push and seeing what test failures we get...

Comment 87

[Julien Wajsberg [:julienw]]

(In reply to Boris Zbarsky [:bz] from comment #86)
> > We're used to this strange idiosyncracies on the Web 
> 
> That's the thing.  The "Web" means "lots of deployed browser engines you
> have no control over and just have to deal with".  But gaia is running on
> top of Gecko, and you know how to file Gecko bugs... and we try to fix them
> if they affect gaia.  So even if you have to work around something, _please_
> report a bug on the underlying API so that it can be fixed and the
> workaround removed.

Yep, I know better now, and I'll definitely report bugs to the underlying API in such cases.

> 
> > was there an underlying cause that could bite us later?
> 
> There were two things interacting:
> 
> 1) The contacts API was incorrectly returning a chrome object to the web
> page instead of a web page object.  In effect, instead of an array it was
> returning something that sort of quacked like an array sometimes, as long as
> you didn't look too carefully.
> 
> 2) The patches in this bug made slice() on that precise sort of object no
> longer work.  See comment 57 and comment 59.

Thanks, this is clearer.

> 
> Bobby, I wonder whether we should consider making COW creating for an array
> fatal for a try push and seeing what test failures we get...

Sounds good to me. If we don't want this at all anymore, we need to play hard with this construct.

Comment 88

[Bobby Holley (:bholley)]

(In reply to Boris Zbarsky [:bz] from comment #86)
> Bobby, I wonder whether we should consider making COW creating for an array
> fatal for a try push and seeing what test failures we get...

Well, it depends how many COW-implemented Arrays we have left floating around in our DOM APIs.

I don't know if we're there yet, but this is a good thing to do, I think. File a bug and mark it as blocking SH-wrappers?

Comment 89

[Boris Zbarsky [:bzbarsky]]

> Well, it depends how many COW-implemented Arrays we have left floating around in our DOM
> APIs.

As of this bug, any such is a web compat regression, so we want to find them soon.  This cycle.

I'm not saying ship the hard-fail; I'm saying see what other broken DOM APIs we have.

Filed bug 948488.