Last Comment Bug 558754 - (fastiterators) fast object iteration
(fastiterators)
: fast object iteration
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Mac OS X
: -- normal (vote)
: ---
Assigned To: Andreas Gal :gal
:
Mentors:
: 548903 (view as bug list)
Depends on: 560358 560798 564377 564672 564954 565199 565521 568056 569306 569516 569735 589093 590813 605013 613151 637010 649939
Blocks: 553510 559083 560167 560697 561327
  Show dependency treegraph
 
Reported: 2010-04-12 04:14 PDT by Andreas Gal :gal
Modified: 2011-05-06 22:48 PDT (History)
15 users (show)
gary: in‑testsuite?
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
patch (49.73 KB, patch)
2010-04-12 04:14 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (49.73 KB, patch)
2010-04-13 04:36 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (60.71 KB, patch)
2010-04-13 14:02 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (62.21 KB, patch)
2010-04-13 15:21 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (62.22 KB, patch)
2010-04-13 16:45 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (68.08 KB, patch)
2010-04-13 20:50 PDT, Andreas Gal :gal
no flags Details | Diff | Review
open code NEXTITER for native iterators (78.93 KB, application/octet-stream)
2010-04-13 23:32 PDT, Andreas Gal :gal
no flags Details
patch (79.00 KB, patch)
2010-04-14 00:18 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (79.00 KB, patch)
2010-04-14 09:23 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (78.93 KB, patch)
2010-04-14 09:23 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (135.96 KB, patch)
2010-04-16 12:28 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (137.98 KB, patch)
2010-04-19 13:42 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (138.00 KB, patch)
2010-04-19 18:00 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (138.02 KB, patch)
2010-04-20 01:02 PDT, Andreas Gal :gal
no flags Details | Diff | Review
fix for "(function () { for each(let x in ['', '', 0]) {} })()", increment cursor after unboxing only (138.02 KB, application/octet-stream)
2010-04-20 13:54 PDT, Andreas Gal :gal
no flags Details
detect deep abort in IteratoreMore (138.02 KB, patch)
2010-04-20 14:20 PDT, Andreas Gal :gal
no flags Details | Diff | Review
fix for (function () { for (*::* in /x/) {} })(), FORELEM only has 2 items on the stack now (iterator, object) (139.14 KB, patch)
2010-04-20 14:27 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (139.14 KB, patch)
2010-04-20 14:41 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (143.27 KB, patch)
2010-04-20 14:42 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (143.54 KB, patch)
2010-04-20 15:45 PDT, Andreas Gal :gal
no flags Details | Diff | Review
don't trigger __iterator__ for JS_Enumerate (i.e. keys(), soon json) (143.77 KB, patch)
2010-04-20 18:03 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (144.59 KB, patch)
2010-04-20 18:41 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (144.87 KB, patch)
2010-04-20 19:32 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (144.71 KB, patch)
2010-04-20 19:51 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (146.99 KB, patch)
2010-04-20 20:24 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (148.25 KB, patch)
2010-04-20 20:30 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (149.71 KB, patch)
2010-04-20 20:52 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch, properly handle non-native iterator loop edge condition (149.81 KB, patch)
2010-04-21 02:03 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (149.81 KB, patch)
2010-04-21 14:38 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (149.81 KB, patch)
2010-04-21 20:53 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (152.17 KB, patch)
2010-04-21 20:55 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (152.50 KB, patch)
2010-04-21 21:39 PDT, Andreas Gal :gal
no flags Details | Diff | Review
refreshed patch, no changes (152.51 KB, patch)
2010-04-21 22:54 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (154.42 KB, patch)
2010-04-22 14:49 PDT, Andreas Gal :gal
no flags Details | Diff | Review
eliminate some nasty NEXTITER imacro leftovers in JSOP_CALL (155.90 KB, patch)
2010-04-23 13:48 PDT, Andreas Gal :gal
no flags Details | Diff | Review
non-enumerable properties must shadow enumerable ones (156.02 KB, patch)
2010-04-23 14:23 PDT, Andreas Gal :gal
brendan: review+
Details | Diff | Review
patch (156.02 KB, patch)
2010-04-24 01:29 PDT, Andreas Gal :gal
no flags Details | Diff | Review
latest (156.03 KB, patch)
2010-04-24 01:30 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (156.07 KB, patch)
2010-04-24 09:45 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (161.22 KB, patch)
2010-04-24 13:36 PDT, Andreas Gal :gal
brendan: review+
Details | Diff | Review
patch (162.53 KB, patch)
2010-04-24 18:14 PDT, Andreas Gal :gal
no flags Details | Diff | Review
1824-line testcase (32.02 KB, text/plain)
2010-04-26 00:43 PDT, Gary Kwong [:gkw] [:nth10sd]
no flags Details
patch (162.77 KB, patch)
2010-04-28 13:55 PDT, Andreas Gal :gal
no flags Details | Diff | Review
fix for IFNEX (162.74 KB, patch)
2010-04-28 15:49 PDT, Andreas Gal :gal
no flags Details | Diff | Review
rebase (162.76 KB, patch)
2010-04-28 18:55 PDT, Andreas Gal :gal
no flags Details | Diff | Review
fix for #117 (163.81 KB, patch)
2010-05-03 16:17 PDT, Andreas Gal :gal
no flags Details | Diff | Review
fix for #116, ++gary (163.82 KB, patch)
2010-05-03 16:19 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (164.02 KB, patch)
2010-05-06 15:31 PDT, Andreas Gal :gal
no flags Details | Diff | Review
refreshed to TM tip (164.00 KB, patch)
2010-05-06 15:33 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (3.30 KB, patch)
2010-05-07 01:59 PDT, Andreas Gal :gal
no flags Details | Diff | Review
patch (1.46 KB, patch)
2010-05-11 22:36 PDT, Andreas Gal :gal
brendan: review+
Details | Diff | Review

Description Andreas Gal :gal 2010-04-12 04:14:23 PDT
The attached patch works mostly. A bit more debugging needed. Major features:

- removed FINALIZE_ITER GC hack
- remove per-object iterator state and cache
- add snapshot-based iteration
- cache iterator state based on the shapes of all objects along the proto chain (as long all objects are native)
- for native objects that use js_Enumerate use a builtin fast path, otherwise use the existing JSENUMERATE_* protocol
- properly support NEW_ENUMERATOR class hooks and e4x enumeration

The loop edge code for iteration is trivial now:

    NativeIterator *ni = (NativeIterator *) obj->getPrivate();
    if (ni->props.cursor < ni->props.end) {
        *rval = *ni->props.cursor++;
        return true;
    }

This lends itself to inlining as LIR. I will do that in a separate patch though.
Comment 1 Andreas Gal :gal 2010-04-12 04:14:41 PDT
Created attachment 438454 [details] [diff] [review]
patch
Comment 2 Andreas Gal :gal 2010-04-12 04:17:36 PDT
This is completely unoptimized at the moment and needs profiling and LIR inlining but is already a 10ms speedup for fasta alone.
Comment 3 Andreas Gal :gal 2010-04-12 13:57:49 PDT
Actually I measured incorrectly yesterday night (note to self: no benchmarks at 4am :) ). Without JIT we are 10ms faster than before with JIT. With JIT its more like 30ms faster (fasta is in the 20ms range on my machine now). The code still has a bug, and still hasn't met shark, so we can probably push this into well sub-20ms territory. My initial sharking suggested 10ms as being doable for fasta.
Comment 4 Andreas Gal :gal 2010-04-13 04:36:25 PDT
Created attachment 438720 [details] [diff] [review]
patch

- Only use native object fast path if ops->enumerate == js_Enumerate. This fixes enumerating xml objects.
- For dense arrays we used to rely on some super hairy sketchy bit vector code that formed a custom iterator. When an array was slowified, we had to detect this special iterator in a custom enumerate hook used by Array class so we can keep iterating using the old iterator. I removed all of this code.
- Add a fast path for dense array iteration direct into jsiter.cpp.
- Slow arrays are iterated using the js_Enumerate fast path. Remove the custom slowarray_enumerate hook.
- Remove the JSCLASS_NEW_ENUMERATE flag from Array class. I have no idea why it was set to begin with.
- Properly root list of ids/values/pairs as we build the iterator.
- Note: array iterator's can't be cached. This sucks a bit.

Brendan and I had a discussion wrt memory use. The old iteration used a compact bitmask to represent the iterator state (one bit per array value). The new code uses a vector of jsval, so the iterator needs basically as much memory as the original object's dslots. I think this is acceptable. Note that old and new code actually have to stringify each property name, so once we are talking large arrays, in both case we create tons of JSString garbage, which by far outweighs the iterator dslots itself. The only difference is that we take the memory use up front for my iterators, while in the past it used to be during iteration.

Upside: much faster, much clear, much less complex iteration code. arrays and regular objects use the same iterator, so do all objects in the engine actually. No more scary custom array iterators and weird transition states. This will greatly help proxies.
Comment 5 Brendan Eich [:brendan] 2010-04-13 08:05:07 PDT
(In reply to comment #4)
> - For dense arrays we used to rely on some super hairy sketchy

Let's be fair: hairy, yes; sketchy, no -- the code is debugged and its state transitions work.

> bit vector code
> that formed a custom iterator. When an array was slowified, we had to detect
> this special iterator in a custom enumerate hook used by Array class so we can
> keep iterating using the old iterator. I removed all of this code.

This is a good change. Less hair ;-).

> Brendan and I had a discussion wrt memory use. The old iteration used a compact
> bitmask to represent the iterator state (one bit per array value).

Wrong. Only if holes are present is the bitmak and its containing struct, JSIndexIterState, created.

For hole-free dense array, the old code used a jsval containing a pair of uint 14-bit counters, a cursor and a limit.

> The new code
> uses a vector of jsval, so the iterator needs basically as much memory as the
> original object's dslots.

We talked yesterday about using dslots itself, the presence of JSVAL_HOLE, as the iterator state part that helps skip over indexes in holey but dense arrays.

Why not do that? Allocating memory that is redundant with respect to dslots seems undesirable for big "scivis" apps that use dense arrays and for-in (Python code ported to JS). Separate bug is fine.

> I think this is acceptable. Note that old and new
> code actually have to stringify each property name, so once we are talking
> large arrays, in both case we create tons of JSString garbage, which by far
> outweighs the iterator dslots itself. The only difference is that we take the
> memory use up front for my iterators, while in the past it used to be during
> iteration.

Is stringifying up front faster or is it not part of the speedup?

Stringifying sucks but we seem stuck with it for default enumeration. Maybe we should look into more intString duality for the big dense array for-in case. I recall JSC doing something like that, have you had a look at it or V8?

> Upside: much faster, much clear, much less complex iteration code. arrays and
> regular objects use the same iterator, so do all objects in the engine
> actually. No more scary custom array iterators and weird transition states.
> This will greatly help proxies.

Great! Ready for review?

I think we should have a bug on losing the "has" during enumeration to suppress names of properties deleted after the loop starts. This is an Ecma TC39 issue so it'll want es-discuss talk too, but that talk will founder without us trying to break compatibility here and getting data on whether the Web cares.

/be
Comment 6 Andreas Gal :gal 2010-04-13 14:01:51 PDT
The attach patch seems to be mostly working now.

I played around with a bunch of variants and arrived at the following compromise:

- I initially wanted iterators to be an array of jsvals ready to be sucked in by the iteration body. This blows for iteration over large arrays. We make a ton of string garbage and might be pushed into OOM. This can happen with objects with numeric properties, too. Even worse, if you make an iterator but then abort right away, we make all the strings for nothing.
- Instead, iterators are now an array of jsids or jsvals, and we stringify jsids on the fly as needed. There is a fast path for small integer indexes. This has better memory behavior. We no longer hold on to all those strings. It also means we re-stringify for cached iterators (only regular arrays, dense array iterators can't be cached). This is probably tolerable.
- I currently do not do the "avoid allocating another array, just walk dslots for holes" trick. Since the array is now a list of jsid, those are actually cheap to manufacture (most the time). This keeps the iterator.next code uniform,
which I am very interested in. I don't think this hurts code that iterates over large arrays. If you iterate over an array with 100000 entries, its ok for us to ask that there is enough memory around to make a 100000 entry snapshot.

> Why not do that? Allocating memory that is redundant with respect to dslots
> seems undesirable for big "scivis" apps that use dense arrays and for-in
> (Python code ported to JS). Separate bug is fine.

Simplicity, less branches in the super hot iterator.next path. I think its worth it, but I am willing to measure more to prove it.

Still to improve: we probably don't have to fill the hash set if only one object along the proto chain actually contains enumerable properties (likely the case for many loops).

The attached patch still needs sharking. Doing that next.

> I think we should have a bug on losing the "has" during enumeration to suppress
> names of properties deleted after the loop starts. This is an Ecma TC39 issue
> so it'll want es-discuss talk too, but that talk will founder without us trying
> to break compatibility here and getting data on whether the Web cares.
> 
> /be

Yeah, we should land a version without deletion suppression on trunk and see what breaks. I would bet its nothing.
Comment 7 Andreas Gal :gal 2010-04-13 14:02:12 PDT
Created attachment 438841 [details] [diff] [review]
patch
Comment 8 Andreas Gal :gal 2010-04-13 15:19:18 PDT
new Iterator(obj) used to not call obj.__iterator__ as a (IMO misguided) fix for bug 354945. The attached patch removes all those extra code paths and now avoids calls to __iterator__ for cached iterators. It also restore sanity with respect to Iterator(obj) and new Iterator(obj) having identical results.

obj = {}; obj.__iterator__ = function(){ }; for(t in (new Iterator(obj))) { }
Comment 9 Andreas Gal :gal 2010-04-13 15:21:38 PDT
Created attachment 438865 [details] [diff] [review]
patch
Comment 10 Andreas Gal :gal 2010-04-13 16:45:10 PDT
Created attachment 438889 [details] [diff] [review]
patch
Comment 11 Andreas Gal :gal 2010-04-13 20:50:10 PDT
Created attachment 438934 [details] [diff] [review]
patch

- prepare NativeIterator for offsetof access (about to generate lir for NEXTITER)
- undo JSVAL_HOLE trick for CallNextIterator, except for the tracer (will be eliminated by the generated lir step there as well)
- Undo pointless CallIteratorNextImpl optimization. iterator_next is rarely called anyway, and it makes the code unnecessarily complex.
Comment 12 Andreas Gal :gal 2010-04-13 23:32:16 PDT
Created attachment 438949 [details]
open code NEXTITER for native iterators

There is still a bug in this somewhere, but it already looks pretty good (fasta works but its slow, probably side exit somewhere).

var obj = ({"a":1,"b":2.5,"c":"3","d":({}),"e":5,"f":6,"g":7,"h":8});

for (var j = 0; j < 1000000; ++j)
    for (var i in obj)
	;

interp: 1140 1134 1136 1150 1135 
jit: 123 121 120 121 120 
jit factor: 9.45
Comment 13 Andreas Gal :gal 2010-04-14 00:17:24 PDT
Alright. We are in business. fasta is now sub-20ms on my machine:

whale:src gal$ ./time.sh t/string-fasta.js
interp: 58 56 56 57 56 
jit: 17 19 17 18 17 
jit factor: 3.29
Comment 14 Andreas Gal :gal 2010-04-14 00:18:02 PDT
Created attachment 438953 [details] [diff] [review]
patch
Comment 15 Andreas Gal :gal 2010-04-14 09:23:16 PDT
Created attachment 439005 [details] [diff] [review]
patch

Something is still broken, but getting there.
Comment 16 Andreas Gal :gal 2010-04-14 09:23:40 PDT
Created attachment 439006 [details] [diff] [review]
patch

The patch this time for real.
Comment 17 Igor Bukanov 2010-04-16 05:12:42 PDT
(In reply to comment #16)
> Created an attachment (id=439006) [details]
> patch
> 
> The patch this time for real.

Does this passes e4x tests in the shell? IIRC E4X explicitly allows to insert/remove properties during the enumeration and the enumeration should observe that. Pre-enumerating clearly breaks this but then this is E4X that is broken and we should just comment on that.
Comment 18 Igor Bukanov 2010-04-16 05:17:14 PDT
(In reply to comment #16)
> Created an attachment (id=439006) [details]

The patch does not touch JS_Enumerate (see http://mxr.mozilla.org/mozilla-central/ident?i=JS_Enumerate for its usage). We should update it to use the new pre-enumeration code either in this bug on in the followup.
Comment 19 Andreas Gal :gal 2010-04-16 12:28:41 PDT
Created attachment 439596 [details] [diff] [review]
patch

The patch is not ready for review. It crashes on sunspider with jit off (gc issue?).

This patch uses a more/next protocol for native iterators, and emulates more/next using just Iterator.next() for custom ones. I also fuse NEXTITER and IFNE in the interpreter. This allows us to generate efficient code for the loop edge (no more need to synthesize a stop value using cmov). This only works because more/next are split since we now re-execute NEXTITER, so it can't be statefull. By inlining the code for native iterators this patch is also strictly faster in the interpreter.
Comment 20 Jeff Walden [:Waldo] (remove +bmo to email) 2010-04-16 14:39:53 PDT
I don't think we should hesitate to break absolute, pedantic E4X faithfulness if doing so presents the simplest path forward.
Comment 21 Andreas Gal :gal 2010-04-19 13:42:50 PDT
Created attachment 440016 [details] [diff] [review]
patch
Comment 22 Andreas Gal :gal 2010-04-19 14:49:39 PDT
Current performance data:

  string:              1.068x as fast    234.0ms +/- 0.4%   219.0ms +/- 0.4%     significant
    base64:            -                   9.3ms +/- 1.5%     9.3ms +/- 1.6% 
    fasta:             1.59x as fast      38.0ms +/- 0.3%    23.9ms +/- 0.7%     significant
    tagcloud:          1.071x as fast     88.3ms +/- 1.1%    82.4ms +/- 0.5%     significant
    unpack-code:       *1.066x as slow*   77.1ms +/- 0.3%    82.2ms +/- 0.5%     significant

unpack-code takes a 6% hit. I have no idea why. Still investigating.
Comment 23 Andreas Gal :gal 2010-04-19 17:59:53 PDT
The slowdown in unpack-code is due to excessive L2 cache misses caused by saving and restoring repeatedly the static state of the regexp object. I fixed that in bug 560358.

Perf results for both patches applied:

** TOTAL **:           1.039x as fast    687.8ms +/- 0.2%   662.3ms +/- 0.1%     significant

=============================================================================

  3d:                  -                 105.7ms +/- 1.0%   105.6ms +/- 0.3% 
    cube:              -                  38.2ms +/- 2.2%    38.0ms +/- 0.8% 
    morph:             -                  21.5ms +/- 0.7%    21.3ms +/- 0.6% 
    raytrace:          ??                 46.0ms +/- 0.7%    46.3ms +/- 0.3%     not conclusive: might be *1.005x as slow*

  access:              1.036x as fast     96.4ms +/- 0.3%    93.1ms +/- 0.3%     significant
    binary-trees:      ??                 18.5ms +/- 0.8%    18.6ms +/- 0.8%     not conclusive: might be *1.005x as slow*
    fannkuch:          1.078x as fast     49.4ms +/- 0.3%    45.8ms +/- 0.3%     significant
    nbody:             -                  16.3ms +/- 0.8%    16.3ms +/- 0.8% 
    nsieve:            *1.015x as slow*   12.2ms +/- 0.9%    12.4ms +/- 1.1%     significant

  bitops:              *1.013x as slow*   30.7ms +/- 0.6%    31.1ms +/- 0.5%     significant
    3bit-bits-in-byte: -                   1.1ms +/- 7.8%     1.1ms +/- 7.8% 
    bits-in-byte:      *1.050x as slow*    9.6ms +/- 1.5%    10.0ms +/- 1.0%     significant
    bitwise-and:       -                   2.1ms +/- 3.3%     2.0ms +/- 2.8% 
    nsieve-bits:       -                  18.0ms +/- 0.4%    17.9ms +/- 0.5% 

  controlflow:         ??                  7.6ms +/- 1.9%     7.7ms +/- 1.8%     not conclusive: might be *1.011x as slow*
    recursive:         ??                  7.6ms +/- 1.9%     7.7ms +/- 1.8%     not conclusive: might be *1.011x as slow*

  crypto:              ??                 44.3ms +/- 0.9%    44.7ms +/- 0.8%     not conclusive: might be *1.010x as slow*
    aes:               ??                 25.8ms +/- 1.4%    26.1ms +/- 1.2%     not conclusive: might be *1.011x as slow*
    md5:               ??                 12.1ms +/- 0.7%    12.2ms +/- 0.9%     not conclusive: might be *1.005x as slow*
    sha1:              ??                  6.3ms +/- 2.1%     6.5ms +/- 2.2%     not conclusive: might be *1.019x as slow*

  date:                -                  97.0ms +/- 0.1%    96.8ms +/- 0.2% 
    format-tofte:      1.006x as fast     51.0ms +/- 0.2%    50.7ms +/- 0.2%     significant
    format-xparb:      *1.003x as slow*   45.9ms +/- 0.2%    46.1ms +/- 0.2%     significant

  math:                -                  33.4ms +/- 0.6%    33.4ms +/- 0.6% 
    cordic:            ??                 16.2ms +/- 0.8%    16.4ms +/- 0.9%     not conclusive: might be *1.009x as slow*
    partial-sums:      -                  11.3ms +/- 1.1%    11.2ms +/- 1.0% 
    spectral-norm:     -                   5.9ms +/- 1.7%     5.8ms +/- 1.8% 

  regexp:              1.014x as fast     38.9ms +/- 0.3%    38.3ms +/- 0.4%     significant
    dna:               1.014x as fast     38.9ms +/- 0.3%    38.3ms +/- 0.4%     significant

  string:              1.106x as fast    234.0ms +/- 0.4%   211.6ms +/- 0.2%     significant
    base64:            ??                  9.3ms +/- 1.5%     9.4ms +/- 1.5%     not conclusive: might be *1.011x as slow*
    fasta:             1.57x as fast      38.0ms +/- 0.3%    24.2ms +/- 0.4%     significant
    tagcloud:          1.072x as fast     88.3ms +/- 1.1%    82.4ms +/- 0.2%     significant
    unpack-code:       1.039x as fast     77.1ms +/- 0.3%    74.2ms +/- 0.2%     significant
    validate-input:    *1.013x as slow*   21.2ms +/- 0.6%    21.5ms +/- 0.7%     significant
Comment 24 Andreas Gal :gal 2010-04-19 18:00:15 PDT
Created attachment 440100 [details] [diff] [review]
patch
Comment 25 Andreas Gal :gal 2010-04-20 00:08:27 PDT
Gary, if you apply the patch this one depends on onto TM tip, and then this one, you should be able to fuzz it.
Comment 26 Andreas Gal :gal 2010-04-20 01:02:39 PDT
Created attachment 440160 [details] [diff] [review]
patch
Comment 27 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 01:21:28 PDT
(In reply to comment #26)
> Created an attachment (id=440160) [details]
> patch

uneval(Function("for(l in[]);"))

Assertion failure: top < StackDepth(ss->printer->script), at ../jsopcode.cpp:1005

More coming up...
Comment 28 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 01:28:39 PDT
(In reply to comment #26)
> Created an attachment (id=440160) [details]
> patch

(function () {
    for each(let x in ['', '', 0]) {}
})()

Assertion failure: ni->props_cursor < ni->props_end, at ../jsinterp.cpp:2266

(This one requires -j)
Comment 29 Andreas Gal :gal 2010-04-20 01:32:47 PDT
#27 is the decompiler. No clue whats going on there. Paging mrbkap and brendan.
Comment 30 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 01:42:57 PDT
(In reply to comment #26)
> Created an attachment (id=440160) [details]
> patch

for (i in Function("for(a in[0,0,0]){yield}")()) {
  function () {}
}

asserts at Assertion failed: 0 (../nanojit/LIR.cpp:1004) and crashes at:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7209ed8 in main_arena () from /lib/libc.so.6
(gdb) bt
#0  0x00007ffff7209ed8 in main_arena () from /lib/libc.so.6
#1  0x0000000000530aa0 in nanojit::CseFilter::insImmq(unsigned long) ()
#2  0x00000000005233fa in js::TraceRecorder::record_JSOP_NEXTITER() ()
#3  0x00000000005258e1 in js::TraceRecorder::monitorRecording(JSOp) ()
#4  0x0000000000547290 in js_Interpret ()
#5  0x0000000000457c2d in js_Execute ()
#6  0x000000000040ac96 in JS_ExecuteScript ()
#7  0x000000000040655f in Process(JSContext*, JSObject*, char*, int) ()
#8  0x0000000000406de3 in main ()
(gdb)
Comment 31 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 01:44:52 PDT
(In reply to comment #30)
> (In reply to comment #26)
> > Created an attachment (id=440160) [details] [details]
> > patch
> 
> for (i in Function("for(a in[0,0,0]){yield}")()) {
>   function () {}
> }
> 
> asserts at Assertion failed: 0 (../nanojit/LIR.cpp:1004) and crashes at:
> 
> Program received signal SIGSEGV, Segmentation fault.
> 0x00007ffff7209ed8 in main_arena () from /lib/libc.so.6
> (gdb) bt
> #0  0x00007ffff7209ed8 in main_arena () from /lib/libc.so.6
> #1  0x0000000000530aa0 in nanojit::CseFilter::insImmq(unsigned long) ()
> #2  0x00000000005233fa in js::TraceRecorder::record_JSOP_NEXTITER() ()
> #3  0x00000000005258e1 in js::TraceRecorder::monitorRecording(JSOp) ()
> #4  0x0000000000547290 in js_Interpret ()
> #5  0x0000000000457c2d in js_Execute ()
> #6  0x000000000040ac96 in JS_ExecuteScript ()
> #7  0x000000000040655f in Process(JSContext*, JSObject*, char*, int) ()
> #8  0x0000000000406de3 in main ()
> (gdb)

This testcase also requires -j.

The testcases in comment 27, comment 28 and comment 30 were tested in Linux 64-bit TM tip patched with the patch in bug 560358 and this one, and were verified to not occur on stand-alone TM tip.
Comment 32 Andreas Gal :gal 2010-04-20 09:14:52 PDT
This is the test case for #27:

00000:   1  trace
00001:   1  newarray 0
00004:   1  iter 1
00006:   1  goto 13 (7)
00009:   1  trace
00010:   1  forname "l"
00013:   1  nextiter
00014:   1  ifne 9 (-5)
00017:   1  enditer
00018:   1  stop
Comment 33 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 09:41:36 PDT
(In reply to comment #26)
> Created an attachment (id=440160) [details]
> patch

3 more testcases:

+Function("for each(y in[]){for(;[*for(y in[])];(y?\"\"(\"\"):(\"\"))){}}")

Assertion failure: jp->script->nfixed + pos == GET_UINT16(pc), at ../jsopcode.cpp:3060

(function () {
    for (*::* in /x/) {}
})()

Assertion failure: cg->stackDepth >= 3, at ../jsemit.cpp:4840

+Function("for(z in[1()])try{}catch(z){}")

Assertion failure: strcmp(rval, exception_cookie) == 0, at ../jsopcode.cpp:2808
Comment 34 Andreas Gal :gal 2010-04-20 13:54:30 PDT
Created attachment 440319 [details]
fix for "(function () {     for each(let x in ['', '', 0]) {} })()", increment cursor after unboxing only
Comment 35 Andreas Gal :gal 2010-04-20 14:18:05 PDT
for (i in Function("for(a in[0,0,0]){yield}")()) {
  function () {}
}

This test-case involves a generator and it yanks the recorder out from under the recording function.

Continuing.
Hardware watchpoint 3: *(JSContext * const *) 4299251152

Old value = (JSContext * const) 0x10088b400
New value = (JSContext * const) 0xd
0x00007fff8248e592 in tiny_free_list_add_ptr ()
(gdb) bt
#0  0x00007fff8248e592 in tiny_free_list_add_ptr ()
#1  0x00007fff8248dc9e in szone_free_definite_size ()
#2  0x000000010019d534 in js::TraceRecorder::operator delete (p=0x100415dd0) at jstracer.h:1387
#3  0x000000010017a46d in js::TraceRecorder::finishAbort (this=0x100415dd0, reason=0x1001db698 "attempt to reenter interpreter while recording") at ../jstracer.cpp:2430
#4  0x000000010017a508 in js::AbortRecordingImpl (cx=0x10088b400, reason=0x1001db698 "attempt to reenter interpreter while recording") at ../jstracer.cpp:7145
#5  0x000000010007eb92 in js_Interpret (cx=0x10088b400) at ../jsinterp.cpp:2636
#6  0x00000001000ab617 in SendToGenerator (cx=0x10088b400, op=JSGENOP_NEXT, obj=0x101002540, gen=0x100415a10, arg=22) at ../jsiter.cpp:906
#7  0x00000001000aba2b in generator_op (cx=0x10088b400, op=JSGENOP_NEXT, vp=0x100890a68, argc=0) at ../jsiter.cpp:1019
#8  0x00000001000abad4 in generator_next (cx=0x10088b400, argc=0, vp=0x100890a68) at ../jsiter.cpp:1034
#9  0x00000001000a8b62 in js_Invoke (cx=0x10088b400, argc=0, vp=0x100890a68, flags=0) at jsinterp.cpp:696
#10 0x00000001000a96e9 in js_InternalInvoke (cx=0x10088b400, obj=0x101002540, fval=4311775648, flags=0, argc=0, argv=0x0, rval=0x100890a30) at jsinterp.cpp:899
#11 0x00000001000ab084 in js_IteratorMore (cx=0x10088b400, iterobj=0x101002540, rval=0x100890a30) at ../jsiter.cpp:603
#12 0x000000010017c22a in js::TraceRecorder::record_JSOP_NEXTITER (this=0x100415dd0) at ../jstracer.cpp:13489
#13 0x0000000100198581 in js::TraceRecorder::monitorRecording (this=0x100415dd0, op=JSOP_NEXTITER) at jsopcode.tbl:219
#14 0x000000010007ed8a in js_Interpret (cx=0x10088b400) at jsops.cpp:78
#15 0x00000001000a822c in js_Execute () at jsinterp.cpp:1103
#16 0x00000001000120f1 in JS_ExecuteScript (cx=0x10088b400, obj=0x101002000, script=0x100414c10, rval=0x7fff5fbff738) at ../jsapi.cpp:4804
#17 0x000000010000a605 in Process (cx=0x10088b400, obj=0x101002000, filename=0x0, forceTTY=0) at ../../shell/js.cpp:542
#18 0x000000010000aecc in ProcessArgs (cx=0x10088b400, obj=0x101002000, argv=0x7fff5fbff920, argc=1) at ../../shell/js.cpp:863
#19 0x000000010000b047 in main (argc=1, argv=0x7fff5fbff920, envp=0x7fff5fbff930) at ../../shell/js.cpp:5045
Comment 36 Andreas Gal :gal 2010-04-20 14:20:47 PDT
Created attachment 440328 [details] [diff] [review]
detect deep abort in IteratoreMore
Comment 37 Andreas Gal :gal 2010-04-20 14:27:56 PDT
Created attachment 440332 [details] [diff] [review]
fix for (function () {     for (*::* in /x/) {} })(), FORELEM only has 2 items on the stack now (iterator, object)
Comment 38 Andreas Gal :gal 2010-04-20 14:28:36 PDT
I think the decompiler bug is all thats left now.
Comment 39 Andreas Gal :gal 2010-04-20 14:41:53 PDT
Created attachment 440342 [details] [diff] [review]
patch

Fix this decompiler. I am a bit unsure whether the fix is correct for generator expressions and array comprehensions. Fuzzing will help to decide that.
Comment 40 Andreas Gal :gal 2010-04-20 14:42:13 PDT
Created attachment 440343 [details] [diff] [review]
patch
Comment 41 Andreas Gal :gal 2010-04-20 15:11:11 PDT
remaining failures

    ecma_5/Object/15.2.3.5-01.js
    ecma_5/Object/15.2.3.7-01.js
    ecma_5/Object/15.2.3.14-01.js
    js1_5/decompilation/regress-349650.js
    js1_5/Regress/regress-261887.js
    js1_5/Regress/regress-349648.js
    js1_5/Regress/regress-96526-003.js
    js1_6/decompilation/regress-352084.js
    js1_6/Regress/regress-350417.js
    js1_7/decompilation/regress-355049-01.js
    js1_7/decompilation/regress-355049-02.js
    js1_7/decompilation/regress-375794.js
    js1_7/decompilation/regress-380506.js
    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_7/regress/regress-461235.js
    js1_8/decompilation/regress-381372.js
    js1_8/decompilation/regress-381963-01.js
    js1_8/decompilation/regress-460504.js
    js1_8/extensions/regress-385393-01.js
    js1_8/extensions/regress-455973.js
    js1_8/genexps/regress-349326.js
    js1_8/genexps/regress-380237-02.js
    js1_8_1/decompilation/regress-346642-01.js
    js1_8_1/regress/regress-452498-098.js
    js1_8_1/regress/regress-452498-117.js
    js1_8_1/regress/regress-452498-119.js
    js1_8_1/regress/regress-452498-135.js
Comment 42 Andreas Gal :gal 2010-04-20 15:45:17 PDT
remaining failures

    ecma_5/Object/15.2.3.7-01.js
    ecma_5/Object/15.2.3.14-01.js
    js1_5/decompilation/regress-349650.js
    js1_5/Regress/regress-261887.js
    js1_5/Regress/regress-349648.js
    js1_5/Regress/regress-96526-003.js
    js1_6/decompilation/regress-352084.js
    js1_6/Regress/regress-350417.js
    js1_7/decompilation/regress-355049-01.js
    js1_7/decompilation/regress-355049-02.js
    js1_7/decompilation/regress-375794.js
    js1_7/decompilation/regress-380506.js
    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_7/regress/regress-461235.js
    js1_8/decompilation/regress-381372.js
    js1_8/decompilation/regress-381963-01.js
    js1_8/decompilation/regress-460504.js
    js1_8/extensions/regress-385393-01.js
    js1_8/extensions/regress-455973.js
    js1_8/genexps/regress-349326.js
    js1_8/genexps/regress-380237-02.js
    js1_8_1/decompilation/regress-346642-01.js
    js1_8_1/regress/regress-452498-098.js
    js1_8_1/regress/regress-452498-117.js
    js1_8_1/regress/regress-452498-119.js
    js1_8_1/regress/regress-452498-135.js
Comment 43 Andreas Gal :gal 2010-04-20 15:45:39 PDT
Created attachment 440366 [details] [diff] [review]
patch

JS_Enumerate is supposed to enumerate own properties only.
Comment 44 Andreas Gal :gal 2010-04-20 17:37:11 PDT
We can't cache iterators for classes that have an enumerate hook, because the shape isn't guaranteed to be accurate for identical objects where the hook hasn't executed yet (see bug 560734).
Comment 45 Andreas Gal :gal 2010-04-20 18:03:54 PDT
Created attachment 440397 [details] [diff] [review]
don't trigger __iterator__ for JS_Enumerate (i.e. keys(), soon json)
Comment 46 Andreas Gal :gal 2010-04-20 18:06:55 PDT
still to go

    js1_5/decompilation/regress-349650.js
    js1_5/Regress/regress-261887.js
    js1_5/Regress/regress-349648.js
    js1_5/Regress/regress-96526-003.js
    js1_6/decompilation/regress-352084.js
    js1_6/Regress/regress-350417.js
    js1_7/decompilation/regress-355049-01.js
    js1_7/decompilation/regress-355049-02.js
    js1_7/decompilation/regress-375794.js
    js1_7/decompilation/regress-380506.js
    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_7/regress/regress-461235.js
    js1_8/decompilation/regress-381372.js
    js1_8/decompilation/regress-381963-01.js
    js1_8/decompilation/regress-460504.js
    js1_8/extensions/regress-385393-01.js
    js1_8/extensions/regress-455973.js
    js1_8/genexps/regress-349326.js
    js1_8/genexps/regress-380237-02.js
    js1_8_1/decompilation/regress-346642-01.js
    js1_8_1/regress/regress-452498-098.js
    js1_8_1/regress/regress-452498-117.js
    js1_8_1/regress/regress-452498-119.js
    js1_8_1/regress/regress-452498-135.js
Comment 47 Andreas Gal :gal 2010-04-20 18:41:16 PDT
Created attachment 440402 [details] [diff] [review]
patch

I am getting frighteningly good at debugging the decompiler. And no, I don't want to fix that decompiler bug for you you have had lying around for ages.

Remaining regressions:

    js1_5/Regress/regress-261887.js
    js1_5/Regress/regress-96526-003.js
    js1_7/decompilation/regress-380506.js
    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_8/extensions/regress-455973.js
    js1_8/genexps/regress-349326.js
Comment 48 Andreas Gal :gal 2010-04-20 18:45:50 PDT
Bug 261887 is about delete suppression, which my new code intentionally doesn't do. I claim the spec is wrong, and the web doesn't care. This will need some blogging and trunk testing.
Comment 49 Andreas Gal :gal 2010-04-20 18:46:08 PDT
This test fails for me with and without the patch: js1_5/Regress/regress-96526-003.js
Comment 50 Andreas Gal :gal 2010-04-20 19:32:25 PDT
Created attachment 440406 [details] [diff] [review]
patch

gal:decompiler 3:0

remaining:

    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_8/extensions/regress-455973.js
    js1_8/genexps/regress-349326.js
Comment 51 Andreas Gal :gal 2010-04-20 19:51:11 PDT
Created attachment 440409 [details] [diff] [review]
patch

Don't turn any failure in Enumerate() into an out of memory exception.
Comment 52 Andreas Gal :gal 2010-04-20 19:53:49 PDT
remaining failures

    js1_7/extensions/iterator-ctor.js
    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/builtin-Iterator-function.js
    js1_7/geniter/regress-349023-03.js
    js1_8/genexps/regress-349326.js
Comment 53 Andreas Gal :gal 2010-04-20 20:24:49 PDT
Created attachment 440410 [details] [diff] [review]
patch

Iterator() constructor wants to return pairs of keys/values it seems. Also update tests/js1_7/extensions/iterator-ctor.js to no longer insist that new Iterator() and Iterator() behave differently wrt __iterator__. This probably doesn't need a blog post. Its a weird corner case of a weird extension.
Comment 54 Andreas Gal :gal 2010-04-20 20:25:11 PDT
Remaining failures:

    js1_7/extensions/regress-354945-01.js
    js1_7/geniter/regress-349023-03.js
    js1_8/genexps/regress-349326.js
Comment 55 Andreas Gal :gal 2010-04-20 20:29:44 PDT
Update test case for bug 354945 to report a type error when __iterator__ returns a primitive instead of an iterator object. The previous behavior was to silently iterate using a native iterator. This also imo doesn't require a blog post, and its a much saner behavior as before.
Comment 56 Andreas Gal :gal 2010-04-20 20:30:10 PDT
Created attachment 440411 [details] [diff] [review]
patch
Comment 57 Andreas Gal :gal 2010-04-20 20:52:47 PDT
Created attachment 440413 [details] [diff] [review]
patch

Only call the equality hook if its actually present. I highly doubt this slows anything down. The tracer already properly checks whether the quality hook is set before bailing there.
Comment 58 Gary Kwong [:gkw] [:nth10sd] 2010-04-20 21:03:53 PDT
(In reply to comment #56)
> Created an attachment (id=440411) [details]
> patch

for (let e in (function () {
    for (var z = 0; z < 3; ++z) {
        if (z % 3 == 2) { *
        } {
            yield
        }
    }
})()) function () {}

Assertion failure: !JS_IsExceptionPending(cx), at ../jsiter.cpp:443

(Haven't yet tested with the latest patch. Also, due to presence of quite a few testcases, setting in-testsuite?)
Comment 59 Andreas Gal :gal 2010-04-20 23:41:35 PDT
One last failure left from the regression suite:

var g = function() {
    try {
	yield "g1";
	yield "g2";
    } finally {
	print("g closed");
    }
}

var h = function() {
    try {
	yield "h1";
	yield "h2";
    } finally {
	print("h closed");
    }
}

for (var i in g())
    for (var j in h())
	print(i + " " + j);

g1 h1
g1 h2
h closed
g2 h1
g2 h2
h closed
g closed

Trying to figure out whats going on. After that I will look at gary's latest fuzzer fail.
Comment 60 Andreas Gal :gal 2010-04-21 00:26:09 PDT
Actually the testcase above is bogus. There h is supposed to be closed twice. This case is buggy though:

var gen2_was_closed = false;
var gen3_was_closed = false;
var finally_was_executed = false;

function gen2() {
  try {
    yield 2;
  } finally {
    print("gen2 finally");
    if (gen2_was_closed || !finally_was_executed || !gen3_was_closed)
      throw "bad order of gen2 finally execution"
        gen2_was_closed = true;
    throw gen2;
  }
}

function gen3() {
  try {
    yield 3;
  } finally {
    print("gen3 finally");
    if (gen2_was_closed || finally_was_executed || gen3_was_closed)
      throw "bad order of gen3 finally execution"
        gen3_was_closed = true;
  }
}

function test()
{
label2: {
    try {
      for (var i in gen2()) {
        try {
          for (var j in gen3()) {
            print("break label2");
            break label2;
          }
        } finally {
          print("finally");
          if (gen2_was_closed || finally_was_executed || !gen3_was_closed)
            throw "bad order of try-finally execution";
          finally_was_executed = true;
        }
      }
      throw "gen2 finally should throw";
    } catch (e) {
      if (e != gen2) throw e;
    }
  }

  print("OK");
}

test();

finally is called twice here:

break label2
gen3 finally
finally
gen2 finally
finally
uncaught exception: bad order of try-finally execution
Comment 61 Andreas Gal :gal 2010-04-21 02:03:06 PDT
Created attachment 440440 [details] [diff] [review]
patch, properly handle non-native iterator loop edge condition

This patch will still crash with the fuzzer bug. The dependent bug has to be fixed as well.
Comment 62 Andreas Gal :gal 2010-04-21 14:38:48 PDT
Created attachment 440625 [details] [diff] [review]
patch

pop iterator object from the stack even in case of failure in ENDITER. This should take care of the last failing test case.
Comment 63 Andreas Gal :gal 2010-04-21 18:31:12 PDT
Wrappers!

NEXT ERROR Thread 0 (crashed)
 0  libxul.so!XPC_NW_Iterator(JSContext*, JSObject*, int) [XPCNativeWrapper.cpp:43bec1add236 : 1151 + 0xe]
    eip = 0x40249280   esp = 0xbfb32150   ebp = 0x416e6000   ebx = 0x40fcf25c
    esi = 0x00000000   edi = 0x423020a0   eax = 0x00000000   ecx = 0x416e6000
Comment 64 Andreas Gal :gal 2010-04-21 19:30:44 PDT
2 problems with wrappers. Both relate to me using ValueToIterator in JS_Enumerate now. Blake has wrappers sitting around that are partially initialized (the class objects), and does JS_Enumerate() on those, which causes me to call back into the XPC_NW_Iterator hook, which Blake doesn't expect. That's an easy fix.

(gdb) bt
#0  0x0000000100051a4c in XPCWrappedNative::GetFlatJSObject (this=0x0) at xpcprivate.h:2436
#1  0x00000001000b801d in XPC_NW_Iterator (cx=0x1050e5a00, obj=0x116502100, keysonly=1) at ../../../../../js/src/xpconnect/src/XPCNativeWrapper.cpp:1151
#2  0x00000001040da94a in js_ValueToIterator (cx=0x1050e5a00, flags=9, vp=0x7fff5fbfd028) at ../../../js/src/jsiter.cpp:530
#3  0x00000001040409fa in JS_Enumerate (cx=0x1050e5a00, obj=0x116502100) at ../../../js/src/jsapi.cpp:3836
#4  0x0000000104040f42 in JS_SealObject (cx=0x1050e5a00, obj=0x116502100, deep=0) at ../../../js/src/jsapi.cpp:2788
#5  0x00000001000b7856 in XPCNativeWrapper::AttachNewConstructorObject (ccx=@0x7fff5fbfd250, aGlobalObject=0x116502000) at ../../../../../js/src/xpconnect/src/XPCNativeWrapper\
.cpp:1241


This one is more difficult and requires some discussion with blake. Enumerate() calls the iterator hook, which calls Enumerate() to make the iterator, which calls the iterator hook. Hilarity ensues.

#3134 0x00000001000b8045 in XPC_NW_Iterator (cx=0x105089600, obj=0x116402100, keysonly=1) at ../../../../../js/src/xpconnect/src/XPCNativeWrapper.cpp:1151
#3135 0x00000001040da94a in js_ValueToIterator (cx=0x105089600, flags=9, vp=0x7fff5f4bc498) at ../../../js/src/jsiter.cpp:530
#3136 0x00000001040409fa in JS_Enumerate (cx=0x105089600, obj=0x116402100) at ../../../js/src/jsapi.cpp:3836
#3137 0x00000001000c6acf in XPCWrapper::Enumerate (cx=0x105089600, wrapperObj=0x1164c4f80, innerObj=0x116402100) at ../../../../../js/src/xpconnect/src/XPCWrapper.cpp:466
#3138 0x00000001000c716b in XPCWrapper::CreateIteratorObj (cx=0x105089600, tempWrapper=0x1164c4f40, wrapperObj=0x116402100, innerObj=0x0, keysonly=1) at ../../../../../js/src/xpconnect/src/XPCWrapper.cpp:341
#3139 0x00000001000b8045 in XPC_NW_Iterator (cx=0x105089600, obj=0x116402100, keysonly=1) at ../../../../../js/src/xpconnect/src/XPCNativeWrapper.cpp:1151
#3140 0x00000001040da94a in js_ValueToIterator (cx=0x105089600, flags=9, vp=0x7fff5f4bc968) at ../../../js/src/jsiter.cpp:530
#3141 0x00000001040409fa in JS_Enumerate (cx=0x105089600, obj=0x116402100) at ../../../js/src/jsapi.cpp:3836
#3142 0x00000001000c6acf in XPCWrapper::Enumerate (cx=0x105089600, wrapperObj=0x1164c4f00, innerObj=0x116402100) at ../../../../../js/src/xpconnect/src/XPCWrapper.cpp:466
#3143 0x00000001000c716b in XPCWrapper::CreateIteratorObj (cx=0x105089600, tempWrapper=0x1164c4ec0, wrapperObj=0x116402100, innerObj=0x0, keysonly=1) at ../../../../../js/src/x
Comment 65 Andreas Gal :gal 2010-04-21 19:30:59 PDT
To reproduce applies this patch and start up the browser.
Comment 66 Andreas Gal :gal 2010-04-21 20:53:42 PDT
Created attachment 440689 [details] [diff] [review]
patch

Don't construct an iterator in JS_Enumerate() and don't call the iterator hook. Merely make a native iterator, and morph that into a JSIdArray *. This avoids reentering the iterator hook from JS_Enumerate(), and also substantially speeds up JS_Enumerate() and avoids an allocation.
Comment 67 Andreas Gal :gal 2010-04-21 20:55:13 PDT
Created attachment 440690 [details] [diff] [review]
patch
Comment 68 Andreas Gal :gal 2010-04-21 21:39:44 PDT
Created attachment 440693 [details] [diff] [review]
patch

Set state to a magic value if a custom enumerate hook redirects us back into js_Enumerate. At first this felt like a gross hack, but this is actually pretty efficient and yields a nice speedup. If a hook redirects into js_Enumerate, the state is set and we detect that and then run the fast path for native objects after all.

I am browsing around with this, so maybe the last version of the patch?
Comment 69 Andreas Gal :gal 2010-04-21 21:42:11 PDT
blake: redirecting into js_Enumerate is perpetrated by your wrappers, let me know what you think about the fix
Comment 70 Andreas Gal :gal 2010-04-21 22:54:52 PDT
Created attachment 440700 [details] [diff] [review]
refreshed patch, no changes
Comment 71 Brendan Eich [:brendan] 2010-04-21 23:36:18 PDT
Run `make jstestbrowser`, tryserver it -- I will review tomorrow.

/be
Comment 72 Gary Kwong [:gkw] [:nth10sd] 2010-04-21 23:52:20 PDT
(In reply to comment #70)
> Created an attachment (id=440700) [details]
> refreshed patch, no changes

for (let e in (function () {
    for (var z = 0; z < 3; ++z) {
        if (z % 3 == 2) { *
        } {
            yield
        }
    }
})()) function () {}

This testcase from comment 58 now crashes at js::TraceRecorder::monitorRecording(JSOp) in opt or at another location in debug:

(gdb) bt
#0  0x000000000057f900 in js::TraceMonitor::outOfMemory (this=0x7fff000000f4) at ../jstracer.cpp:2357
#1  0x000000000057ecac in js::TraceRecorder::outOfMemory (this=0x8af950) at ../jstracer.h:1428
#2  0x00000000005561bb in js::TraceRecorder::monitorRecording (this=0x8af950, op=JSOP_NEXTITER) at ../jstracer.cpp:7128
#3  0x00000000005b2640 in js_Interpret (cx=0x8a63f0) at ../jsops.cpp:78
#4  0x0000000000484fb0 in js_Execute (cx=0x8a63f0, chain=0x7ffff6c02000, script=0x8b0130, down=0x0, flags=0, result=0x7fffffffe0f8) at ../jsinterp.cpp:1103
#5  0x0000000000425748 in JS_ExecuteScript (cx=0x8a63f0, obj=0x7ffff6c02000, script=0x8b0130, rval=0x7fffffffe0f8) at ../jsapi.cpp:4786
#6  0x0000000000403ceb in Process (cx=0x8a63f0, obj=0x7ffff6c02000, filename=0x0, forceTTY=0) at ../../shell/js.cpp:542
#7  0x0000000000404736 in ProcessArgs (cx=0x8a63f0, obj=0x7ffff6c02000, argv=0x7fffffffe320, argc=1) at ../../shell/js.cpp:863
#8  0x000000000040c733 in main (argc=1, argv=0x7fffffffe320, envp=0x7fffffffe330) at ../../shell/js.cpp:5038



I still encounter testcases that assert at Assertion failure: !JS_IsExceptionPending(cx), at ../jsiter.cpp:445 but they seem pretty similar to this one, they sometimes crash debug shell at

(gdb) bt
#0  0x000000000054c5ba in ResetJITImpl (cx=0x7ffff7200078) at ../jstracer.cpp:4221
#1  0x00000000005561ee in js::TraceRecorder::monitorRecording (this=0x8b0870, op=JSOP_NEXTITER) at ../jstracer.cpp:7129
#2  0x00000000005b2640 in js_Interpret (cx=0x8a63f0) at ../jsops.cpp:78
#3  0x0000000000484fb0 in js_Execute (cx=0x8a63f0, chain=0x7ffff6c02000, script=0x8b2310, down=0x0, flags=0, result=0x0) at ../jsinterp.cpp:1103
#4  0x0000000000425748 in JS_ExecuteScript (cx=0x8a63f0, obj=0x7ffff6c02000, script=0x8b2310, rval=0x0) at ../jsapi.cpp:4786
#5  0x0000000000403920 in Process (cx=0x8a63f0, obj=0x7ffff6c02000, filename=0x7fffffffe62a "w245-reduced.js", forceTTY=0) at ../../shell/js.cpp:449
#6  0x0000000000404736 in ProcessArgs (cx=0x8a63f0, obj=0x7ffff6c02000, argv=0x7fffffffe350, argc=2) at ../../shell/js.cpp:863
#7  0x000000000040c733 in main (argc=2, argv=0x7fffffffe350, envp=0x7fffffffe368) at ../../shell/js.cpp:5038
Comment 73 Gary Kwong [:gkw] [:nth10sd] 2010-04-22 00:07:15 PDT
(In reply to comment #70)
> Created an attachment (id=440700) [details]
> refreshed patch, no changes

function () {}
(function () {
    for (a = 0;;) {
        print([z for each(z in this)])
    }
})()

asserts js debug shell at Assertion failure: op == JSOP_CALL || op == JSOP_APPLY || op == JSOP_NEW || op == JSOP_GETPROP || op == JSOP_GETTHISPROP || op == JSOP_GETARGPROP || op == JSOP_GETLOCALPROP || op == JSOP_LENGTH || op == JSOP_GETELEM || op == JSOP_CALLELEM || op == JSOP_CALLPROP || op == JSOP_SETPROP || op == JSOP_SETNAME || op == JSOP_SETMETHOD || op == JSOP_SETELEM || op == JSOP_INITELEM || op == JSOP_ENUMELEM || op == JSOP_INSTANCEOF || op == JSOP_FORARG || op == JSOP_FORLOCAL || op == JSOP_FORNAME || op == JSOP_FORPROP || op == JSOP_FORELEM, at ../jstracer.cpp:6604 and crashes js opt shell at

Program received signal SIGSEGV, Segmentation fault.
0x0000000000540033 in js_Interpret ()
(gdb) bt
#0  0x0000000000540033 in js_Interpret ()
#1  0x000000000045785d in js_Execute ()
#2  0x000000000040ac46 in JS_ExecuteScript ()
#3  0x000000000040659f in Process(JSContext*, JSObject*, char*, int) ()
#4  0x0000000000406e23 in main ()

on 64-bit Linux shell.
Comment 74 Andreas Gal :gal 2010-04-22 14:49:45 PDT
Created attachment 440878 [details] [diff] [review]
patch

Gary you rock. The latest fuzzer test case highlighted a bad bug in the deep bail handling for non-native iterators and it also revealed a latent bug in a related area (bug 561200).
Comment 75 Luke Wagner [:luke] 2010-04-23 11:06:33 PDT
Since you are removing the imacro for JSOP_NEXTITER, can you also remove this bit from JSOP_CALL?

                /*
                 * If we are executing the JSOP_NEXTITER imacro and a
                 * Stopiteration exception is raised, transform it into a
                 * JSVAL_HOLE return value.  The tracer generates equivalent
                 * code by calling CatchStopIteration_tn.
                 */
                if (fp->imacpc && *fp->imacpc == JSOP_NEXTITER &&
                    cx->throwing && js_ValueIsStopIteration(cx->exception)) {
                    // pc may point to JSOP_DUP here due to bug 474854.
                    JS_ASSERT(*regs.pc == JSOP_CALL ||
                              *regs.pc == JSOP_DUP);
                    cx->throwing = JS_FALSE;
                    cx->exception = JSVAL_VOID;
                    regs.sp[-1] = JSVAL_HOLE;
Comment 76 Andreas Gal :gal 2010-04-23 13:46:46 PDT
Done. Thanks Luke! I missed that.
Comment 77 Andreas Gal :gal 2010-04-23 13:48:18 PDT
Created attachment 441144 [details] [diff] [review]
eliminate some nasty NEXTITER imacro leftovers in JSOP_CALL
Comment 78 Andreas Gal :gal 2010-04-23 14:23:36 PDT
Created attachment 441160 [details] [diff] [review]
non-enumerable properties must shadow enumerable ones
Comment 79 Brendan Eich [:brendan] 2010-04-23 17:59:03 PDT
Comment on attachment 441160 [details] [diff] [review]
non-enumerable properties must shadow enumerable ones

> SetIdArrayLength(JSContext *cx, JSIdArray *ida, jsint length)
> {
>     JSIdArray *rida;
> 
>     rida = (JSIdArray *)
>            JS_realloc(cx, ida,
>                       offsetof(JSIdArray, vector) + length * sizeof(jsval));
>     if (!rida)
>         JS_DestroyIdArray(cx, ida);
>-    else
>+    else {
>+        rida->priv = rida;
>         rida->length = length;
>+    }

Brace the "then" clause too since the else is now (basic style rule).

I can't easily improve on "priv" but as shorthand for "private" it's a bit misleading, since it must point to the struct in which the JSIdArray is embedded, or the JSIdArray itself if not embedded. Hey, how about "self"?

> JS_Enumerate(JSContext *cx, JSObject *obj)
> {
>+    CHECK_REQUEST(cx);
>+
>     JSIdArray *ida;
>+    if (!js_EnumerateOwnProperties(cx, obj, &ida))

Can we use namespace js and call the new function EnumerateOwnProperties, etc. for other new js_ functions you are adding. Last time for this nit but it touches a fair number.

>+        return false;
>+    for (size_t n = 0; n < size_t(ida->length); ++n)
>+        ida->vector[n] = js_CheckForStringIndex(ida->vector[n]);

This should not call js_CheckForStringIndex, rather simply assert that ida->vector[n] is canonicalized. We don't burn cycles covering up bugs.

>-#define NATIVE_ENUM_CACHE_LOG2  8
>-#define NATIVE_ENUM_CACHE_MASK  JS_BITMASK(NATIVE_ENUM_CACHE_LOG2)
>-#define NATIVE_ENUM_CACHE_SIZE  JS_BIT(NATIVE_ENUM_CACHE_LOG2)
[snip]
>+    /* Cached native iterators. */
>+    JSObject *cachedNativeIterators[256];

A bit too implicit if you want guaranteed strength-reduction from % to & -- I say make const size_t NATIVE_ITER_CACHE_LOG2, etc.

>+    /* Location to stash the iteration value between JSOP_NEXTITER and JSOP_FOR*. */
>+    jsval               iterValue;

A pigeon-hole like this stinks of future bugs, but I can't improve on it.

>         if (pn2->pn_type == TOK_IN) {
>-            /*
>-             * JSOP_ENDITER must have a slot to save an exception thrown from
>-             * the body of for-in loop when closing the iterator object, and
>-             * fortunately it does: the slot that was set by JSOP_NEXTITER to
>-             * the return value of iterator.next().
>-             */
>-            JS_ASSERT(js_CodeSpec[JSOP_ENDITER].nuses == 2);
>             if (!NewTryNote(cx, cg, JSTRY_ITER, cg->stackDepth, top, CG_OFFSET(cg)) ||
>                 js_Emit1(cx, cg, JSOP_ENDITER) < 0) {
>                 return JS_FALSE;
>             }
>         }

Still seems worth a comment, especially to break up the outer and inner ifs (a single if would have a big-ass condition of the form (A&&(B||C)) which is worse than two ifs here, so keep the ifs -- just say something about this hard case, since it cost you hours of debugging ;-).

>+static inline
>+bool IteratorMore(JSContext *cx, JSObject *iterobj, JSBool *cond, jsval *rval)
>+{
>+    if (iterobj->getClass() == &js_IteratorClass.base) {
>+        NativeIterator *ni = (NativeIterator *) iterobj->getPrivate();
>+        *cond = (ni->props_cursor < ni->props_end);
>+    } else {
>+        if (!js_IteratorMore(cx, iterobj, rval))
>+            return false;
>+        *cond = (*rval == JSVAL_TRUE);
>+    }
>+    return true;
>+}
>+
>+static inline
>+bool IteratorNext(JSContext *cx, JSObject *iterobj, jsval *rval)

These violate style -- the bool return type goes on the same line as static inline.

Also comment on these being intentional fast paths, and their slow paths handle all cases.

>+JSExtendedClass js_IteratorClass = {
>+    {
>+        "Iterator",
>+        JSCLASS_HAS_PRIVATE |
>+        JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator) |
>+        JSCLASS_MARK_IS_TRACE |
>+        JSCLASS_IS_EXTENDED,
>+        JS_PropertyStub,  JS_PropertyStub, JS_PropertyStub,  JS_PropertyStub,
>+        JS_EnumerateStub, JS_ResolveStub,  JS_ConvertStub,   iterator_finalize,
>+        NULL,             NULL,            NULL,             NULL,
>+        NULL,             NULL,            JS_CLASS_TRACE(iterator_trace), NULL
>+    },
>+    NULL,             NULL,            NULL,             iterator_iterator,
>+    NULL,
>+    JSCLASS_NO_RESERVED_MEMBERS
>+};

Style nit: don't over-indent the braced JSClass init, use funky half-indented { and }. Do make the columns line up across both outer and inner struct member inits.

>+void
>+NativeIterator::mark(JSTracer *trc)
>+{
>+    jsval *vp = props_array;
>+    jsval *end = props_end;
>+    while (vp < end) {
>+        JS_SET_TRACING_INDEX(trc, "props", (vp - props_array));
>+        js_CallValueTracerIfGCThing(trc, *vp++);

Super-nit: for loop is more winning for scope and to avoid the ++ effect in an actual arg position.

>+NewKeyValuePair(JSContext *cx, jsid key, jsval val, jsval *rval)
>+{
>+    jsval vec[2] = { ID_TO_VALUE(key), val };
>+    AutoArrayRooter tvr(cx, JS_ARRAY_LENGTH(vec), vec);
> 
>+    JSObject *aobj = js_NewArrayObject(cx, 2, vec);
>+    if (!aobj) {
>+        JS_ReportOutOfMemory(cx);

Bug: you are double-reporting! js_Foo(cx,...) failing means js_Foo (er, js::Foo ;-) did the report or throw.

>+Enumerate(JSContext *cx, JSObject *obj, jsid id, bool enumerable, uintN flags,
>+          HashSet<jsid>& ht, AutoValueVector& vec)
> {
>-    jsval state;
>-    JSBool ok;
>+    JS_ASSERT(JSVAL_IS_INT(id) || JSVAL_IS_STRING(id));
> 
>-    JS_ASSERT(iterobj->getClass() == &js_IteratorClass);
>+    if (JS_LIKELY(!(flags & JSITER_OWNONLY))) {
>+        HashSet<jsid>::AddPtr p = ht.lookupForAdd(id);
>+        if (JS_LIKELY(!p)) {
>+            if (!ht.add(p, id)) {
>+                JS_ReportOutOfMemory(cx);
>+                return false;
>+            }
>+            /* fall through */
>+        } else {
>+            /* property already encountered, done. */
>+            return true;
>+        }

Ugly to fall through to rest of function past the return true, and since you are using JS_LIKELY(!p), why not invert and test JS_UNLIKELY(p) and return true early, avoiding overindentation and fractured control flow?

>+    while (obj) {
>+        JSClass *clasp = obj->getClass();
>+        if (obj->isNative() &&
>+            obj->map->ops->enumerate == js_Enumerate &&
>+            !(clasp->flags & JSCLASS_NEW_ENUMERATE)) {
>+            if (!clasp->enumerate(cx, obj))
>+                return false;
>+
>+          native:

You don't want to do this -- the goto haterz and mr. shaver will get you if you do.

Idea: replace this native: label with do { (indent accordingly) and close with } while (0). Then replace the goto with a continue.

>+            AutoValueVector sprops(cx);

One benefit is that this allows you to scope sprops explicitly.

>+
>+            JS_LOCK_OBJ(cx, obj);
>+
>+            /* Collect all unique properties from this object's scope. */
>+            JSScope *scope = obj->scope();
>+            for (JSScopeProperty *sprop = scope->lastProperty(); sprop; sprop = sprop->parent) {
>+                if (!sprop->isAlias())
>+                    if (!Enumerate(cx, obj, sprop->id, sprop->enumerable(), flags, ht, sprops))
>+                        return false;

Style nit: brace outer if, but since the two conditions are simplex (no || or &&) why not use && and one if?

>+                        /* Dense arrays never get so large that i would not fit into an integer id. */

Assert this? It beats a comment tempting fate.

>+                        if (!Enumerate(cx, obj, INT_TO_JSVAL(i), true, flags, ht, props))
>+                            return false;
>+                    }
>+                }
>+            }
>+        } else {
>+            jsval state;
>+            if (!obj->enumerate(cx, JSENUMERATE_INIT, &state, NULL))
>+                return false;
>+            if (state == JSVAL_NATIVE_ENUMERATE_COOKIE)
>+                goto native;

"C is for Cookie, that's good enough for me..."

>+JSBool

bool?

>+js_EnumerateOwnProperties(JSContext *cx, JSObject *obj, JSIdArray **idap)
>+{
>+    NativeIterator *ni;
>+    if (!InitNativeIterator(cx, obj, JSITER_OWNONLY, NULL, 0, true, &ni))
>+        return false;

Blank line before comment.

>+    /* Morth the NativeIterator into a JSIdArray. The caller will deallocate it. */

s/Morth/Morph/

>+    JS_ASSERT(sizeof(NativeIterator) > sizeof(JSIdArray));
>+    JS_ASSERT(ni->props_array == (jsid *) (ni + 1));
>+    size_t length = size_t(ni->props_end - ni->props_array);
>+    JSIdArray *ida = (JSIdArray *) (uintptr_t(ni->props_array) - (sizeof(JSIdArray) - sizeof(jsid)));
>+    ida->priv = ni;
>+    ida->length = length;
>+    JS_ASSERT(&ida->vector[0] == &ni->props_array[0]);
>+    *idap = ida;
>+    return true;

I like it! Mighty Morphin'.

>+static inline bool
>+GetCustomIterator(JSContext *cx, JSObject *obj, uintN flags, jsval *vp)
>+{
>+    /* Check whether we have a valid __iterator__ method. */
>+    JSAtom *atom = cx->runtime->atomState.iteratorAtom;
>+    if (!js_GetMethod(cx, obj, ATOM_TO_JSID(atom), JSGET_NO_METHOD_BARRIER, vp))
>+        return false;

Blank line.

>+    /* If there is no custom __iterator__ method, we are done here. */
>+    if (*vp == JSVAL_VOID)
>+        return true;

Blank line.

>+    /* Otherwise call it and return that object. */
>+    LeaveTrace(cx);
>+    jsval arg = BOOLEAN_TO_JSVAL((flags & JSITER_FOREACH) == 0);
>+    if (!js_InternalInvoke(cx, obj, *vp, JSINVOKE_ITERATOR, 1, &arg, vp))
>+        return false;
>+    if (JSVAL_IS_PRIMITIVE(*vp)) {
>+        js_ReportValueError(cx, JSMSG_BAD_ITERATOR_RETURN, JSDVG_SEARCH_STACK, *vp, NULL);
>+        return false;
>+    }
>+    return true;
>+}
>+
>+template <typename T>
>+static inline bool
>+Compare(T *a, T *b, size_t c)
>+{
>+    size_t n = (c + 7) / 8;

Real Men (and Women) use >> 3 not / 8 :-P.

Check for warnings on major platforms. Some compilers are dumb about signed and unsigned mixing (it's well defined how this works for size_t, IIRC, but still...).

>     /* JSITER_KEYVALUE must always come with JSITER_FOREACH */
>     JS_ASSERT(!(flags & JSITER_KEYVALUE) || (flags & JSITER_FOREACH));

Use JS_ASSERT_IF.

>+    /*
>+     * Make sure the more/next state machine doesn't get stuck. A value might be
>+     * left in iterValue when a trace is left due to an operation time out after

s/time out /time-out/

>+JSBool
>+js_CallIteratorNext(JSContext *cx, JSObject *iterobj, JSBool *stop, jsval *rval)

This must die.

>+JSExtendedClass js_GeneratorClass = {
>+    {
>+        js_Generator_str,
>+        JSCLASS_HAS_PRIVATE |
>+        JSCLASS_HAS_CACHED_PROTO(JSProto_Generator) |
>+        JSCLASS_IS_ANONYMOUS |
>+        JSCLASS_MARK_IS_TRACE |
>+        JSCLASS_IS_EXTENDED,
>+        JS_PropertyStub,  JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
>+        JS_EnumerateStub, JS_ResolveStub,  JS_ConvertStub,  generator_finalize,
>+        NULL,             NULL,            NULL,            NULL,
>+        NULL,             NULL,            JS_CLASS_TRACE(generator_trace), NULL
>+    },
>+    NULL,             NULL,            NULL,             iterator_iterator, 
>+    NULL,

Ditto previous nit on class initializer layout.

>+    JSCLASS_NO_RESERVED_MEMBERS
> };
> 
> /*
>  * Called from the JSOP_GENERATOR case in the interpreter, with fp referring
>  * to the frame by which the generator function was activated.  Create a new
>  * JSGenerator object, which contains its own JSStackFrame that we populate
>  * from *fp.  We know that upon return, the JSOP_GENERATOR opcode will return
>  * from the activation in fp, so we can steal away fp->callobj and fp->argsobj
>@@ -723,17 +765,17 @@ JS_FRIEND_DATA(JSClass) js_GeneratorClas
> JS_REQUIRES_STACK JSObject *
> js_NewGenerator(JSContext *cx)
> {
>     JSObject *obj;
>     uintN argc, nargs, nslots;
>     JSGenerator *gen;
>     jsval *slots;
> 
>-    obj = NewObject(cx, &js_GeneratorClass, NULL, NULL);
>+    obj = NewObject(cx, &js_GeneratorClass.base, NULL, NULL);
>     if (!obj)
>         return NULL;
> 
>     /* Load and compute stack slot counts. */
>     JSStackFrame *fp = cx->fp;
>     argc = fp->argc;
>     nargs = JS_MAX(argc, fp->fun->nargs);
>     nslots = 2 + nargs + fp->script->nslots;
>@@ -903,17 +945,17 @@ SendToGenerator(JSContext *cx, JSGenerat
>      * Propagate the condition to the caller.
>      */
>     return JS_FALSE;
> }
> 
> static JS_REQUIRES_STACK JSBool
> CloseGenerator(JSContext *cx, JSObject *obj)
> {
>-    JS_ASSERT(obj->getClass() == &js_GeneratorClass);
>+    JS_ASSERT(obj->getClass() == &js_GeneratorClass.base);
> 
>     JSGenerator *gen = (JSGenerator *) obj->getPrivate();
>     if (!gen) {
>         /* Generator prototype object. */
>         return JS_TRUE;
>     }
> 
>     if (gen->state == JSGEN_CLOSED)
>@@ -929,17 +971,17 @@ static JSBool
> generator_op(JSContext *cx, JSGeneratorOp op, jsval *vp, uintN argc)
> {
>     JSObject *obj;
>     jsval arg;
> 
>     LeaveTrace(cx);
> 
>     obj = JS_THIS_OBJECT(cx, vp);
>-    if (!JS_InstanceOf(cx, obj, &js_GeneratorClass, vp + 2))
>+    if (!JS_InstanceOf(cx, obj, &js_GeneratorClass.base, vp + 2))
>         return JS_FALSE;
> 
>     JSGenerator *gen = (JSGenerator *) obj->getPrivate();
>     if (!gen) {
>         /* This happens when obj is the generator prototype. See bug 352885. */
>         goto closed_generator;
>     }
> 
>@@ -1006,17 +1048,16 @@ generator_throw(JSContext *cx, uintN arg
> 
> static JSBool
> generator_close(JSContext *cx, uintN argc, jsval *vp)
> {
>     return generator_op(cx, JSGENOP_CLOSE, vp, argc);
> }
> 
> static JSFunctionSpec generator_methods[] = {
>-    JS_FN(js_iterator_str,  iterator_self,      0,JSPROP_ROPERM),
>     JS_FN(js_next_str,      generator_next,     0,JSPROP_ROPERM),
>     JS_FN(js_send_str,      generator_send,     1,JSPROP_ROPERM),
>     JS_FN(js_throw_str,     generator_throw,    1,JSPROP_ROPERM),
>     JS_FN(js_close_str,     generator_close,    0,JSPROP_ROPERM),
>     JS_FS_END
> };
> 
> #endif /* JS_HAS_GENERATORS */
>@@ -1027,26 +1068,24 @@ js_InitIteratorClasses(JSContext *cx, JS
>     JSObject *proto, *stop;
> 
>     /* Idempotency required: we initialize several things, possibly lazily. */
>     if (!js_GetClassObject(cx, obj, JSProto_StopIteration, &stop))
>         return NULL;
>     if (stop)
>         return stop;
> 
>-    proto = JS_InitClass(cx, obj, NULL, &js_IteratorClass, Iterator, 2,
>+    proto = JS_InitClass(cx, obj, NULL, &js_IteratorClass.base, Iterator, 2,
>                          NULL, iterator_methods, NULL, NULL);
>     if (!proto)
>         return NULL;
>-    proto->setSlot(JSSLOT_ITER_STATE, JSVAL_NULL);
>-    proto->setSlot(JSSLOT_ITER_FLAGS, JSVAL_ZERO);
> 
> #if JS_HAS_GENERATORS
>     /* Initialize the generator internals if configured. */
>-    if (!JS_InitClass(cx, obj, NULL, &js_GeneratorClass, NULL, 0,
>+    if (!JS_InitClass(cx, obj, NULL, &js_GeneratorClass.base, NULL, 0,
>                       NULL, generator_methods, NULL, NULL)) {
>         return NULL;
>     }
> #endif
> 
>     return JS_InitClass(cx, obj, NULL, &js_StopIterationClass, NULL, 0,
>                         NULL, NULL, NULL, NULL);
> }
>diff --git a/js/src/jsiter.h b/js/src/jsiter.h
>--- a/js/src/jsiter.h
>+++ b/js/src/jsiter.h
>@@ -52,41 +52,66 @@ JS_BEGIN_EXTERN_C
> /*
>  * NB: these flag bits are encoded into the bytecode stream in the immediate
>  * operand of JSOP_ITER, so don't change them without advancing jsxdrapi.h's
>  * JSXDR_BYTECODE_VERSION.
>  */
> #define JSITER_ENUMERATE  0x1   /* for-in compatible hidden default iterator */
> #define JSITER_FOREACH    0x2   /* return [key, value] pair rather than key */
> #define JSITER_KEYVALUE   0x4   /* destructuring for-in wants [key, value] */
>+#define JSITER_OWNONLY    0x8   /* iterate over obj's own properties only */
>+
>+struct NativeIterator {
>+    jsval    *props_array;
>+    jsval    *props_cursor;
>+    jsval    *props_end;
>+    uint32   *shapes_array;
>+    uint32    shapes_length;
>+    uint32    shapes_key;
>+    uintN     flags;
>+    JSObject *next;

Style nit: * is part of declarator, not type, starts in same column as first letter of non-pointer declarator name.

Well-done on the decompiler -- you are Knight of the SprintStack now ;-).

> /*
>  * JSOP_ITER sets up a for-in or for-each-in loop using the JSITER_* flag bits
>  * in this op's uint8 immediate operand. It replaces the top of stack object
>+ * with an iterator for that object.

"top of stack value" or "top of stack object, null, or undefined", since for (i in null); must not throw, same for undefined (thanks, IE).

>  *
>+ * JSOP_NEXTITER stores the next iterated value into cx->iterValue and pushes
>+ * true if another value is available, and false otherwise. It is followed immediately
>+ * by JSOP_IFNE{,X}.

Rewrap overlong line ending "immediately". Comment on opcode fusion, maybe?

> BEGIN_CASE(JSOP_NEXTITER)
>+    JS_ASSERT(regs.sp - 1 >= StackBase(fp));
>+    JS_ASSERT(!JSVAL_IS_PRIMITIVE(regs.sp[-1]));
>+    if (!IteratorMore(cx, JSVAL_TO_OBJECT(regs.sp[-1]), &cond, &regs.sp[0]))
>+        goto error;
>+    CHECK_INTERRUPT_HANDLER();
>+    JS_ASSERT(regs.pc[1] == JSOP_IFNE);
>+    TRY_BRANCH_AFTER_COND(cond, 0);
>+    JS_NOT_REACHED("unfused JSOP_NEXTITER");
> END_CASE(JSOP_NEXTITER)

Could rename to JSOP_MOREITER, eh? Why not.

>@@ -5218,75 +5220,29 @@ TraceRecorder::checkTraceEnd(jsbytecode 
>          * pointer and pretend we have reached the loop header.
>          */
>         if (pendingLoop) {
>             JS_ASSERT(!cx->fp->imacpc && (pc == cx->fp->regs->pc || pc == cx->fp->regs->pc + 1));
>             bool fused = pc != cx->fp->regs->pc;
>             JSFrameRegs orig = *cx->fp->regs;
> 
>             cx->fp->regs->pc = (jsbytecode*)tree->ip;
>-            cx->fp->regs->sp -= fused ? 2 : 1;
>+            cx->fp->regs->sp -= fused ? (*orig.pc == JSOP_NEXTITER ? 0 : 2) : 1;
> 
>             JSContext* localcx = cx;
>             AbortableRecordingStatus ars = closeLoop();
>             *localcx->fp->regs = orig;
>             return ars;
>         } else {
>             return endLoop();
>         }

Fix pre-existing else after return non-sequitur.

>@@ -6637,17 +6593,20 @@ LeaveTree(TraceMonitor *tm, TracerState&
>             JSFrameRegs* regs = cx->fp->regs;
>             JSOp op = (JSOp) *regs->pc;
>             JS_ASSERT(op == JSOP_CALL || op == JSOP_APPLY || op == JSOP_NEW ||
>                       op == JSOP_GETPROP || op == JSOP_GETTHISPROP || op == JSOP_GETARGPROP ||
>                       op == JSOP_GETLOCALPROP || op == JSOP_LENGTH ||
>                       op == JSOP_GETELEM || op == JSOP_CALLELEM || op == JSOP_CALLPROP ||
>                       op == JSOP_SETPROP || op == JSOP_SETNAME || op == JSOP_SETMETHOD ||
>                       op == JSOP_SETELEM || op == JSOP_INITELEM || op == JSOP_ENUMELEM ||
>-                      op == JSOP_INSTANCEOF);
>+                      op == JSOP_INSTANCEOF ||
>+                      op == JSOP_ITER || op == JSOP_NEXTITER || op == JSOP_ENDITER ||
>+                      op == JSOP_FORARG || op == JSOP_FORLOCAL ||
>+                      op == JSOP_FORNAME || op == JSOP_FORPROP || op == JSOP_FORELEM);

This assertion is useless!

>+ObjectToIterator(JSContext* cx, JSObject *obj, int32 flags, JSObject **rval)

Canonical name is objp, not rval.

>+{
>+    jsval v = OBJECT_TO_JSVAL(obj);
>+    bool ok = js_ValueToIterator(cx, flags, &v);
>+    if (!ok) {
>+        SetBuiltinError(cx);
>+        return false;
>+    }
>+    *rval = JSVAL_TO_OBJECT(v);
>+    return cx->tracerState->builtinStatus == 0;
>+}
>+JS_DEFINE_CALLINFO_4(static, BOOL_FAIL, ObjectToIterator, CONTEXT, OBJECT, INT32, OBJECTPTR, 0,
>+                     ACC_STORE_ANY)

But why do you need OBJECTPTR after all if you can use an rval? No tagged value change in bits.

> TraceRecorder::record_JSOP_NEXTITER()
> {
>+    jsval& iterobj_val = stackval(-1);
>     if (JSVAL_IS_PRIMITIVE(iterobj_val))
>         RETURN_STOP_A("for-in on a primitive value");
>+
>     RETURN_IF_XML_A(iterobj_val);
>+
>     JSObject* iterobj = JSVAL_TO_OBJECT(iterobj_val);
>     JSClass* clasp = iterobj->getClass();
>     LIns* iterobj_ins = get(&iterobj_val);
>+
>+    bool cond;
>+    LIns* cond_ins;
>+
>+    /* JSOP_FOR* is at the top of the loop and it already guarded on the class. */
>+    if (clasp != &js_IteratorClass.base) {

Why not invert and put the native iterator case first? Common best foot forward prefetched as predicted goodness. And TR::unboxNextValue uses this natural order already.

>+        /*
>+         * The interpreter will call js_IteratorMore again, but that's legal. We have to
>+         * carefully protect ourselves against reentrancy here.
>+         */
>+

Lose the blank line, and the extra "here" at the end.

>+        JSContext *localCx = cx;
>+        if (!js_IteratorMore(cx, iterobj, &stackval(0)))
>+            RETURN_ERROR_A("error in js_IteratorMore");
>+        if (!TRACE_RECORDER(localCx))
>+            return ARECORD_ABORTED;

If cx is gone then |this| has been deleted. Is it really safe to be here?

>+        /* Emit code to stringify the id if necessary. */
>+        if (!(((NativeIterator *) iterobj->getPrivate())->flags & JSITER_FOREACH)) {

NJN (I bet) and I want you to make an inline helper: iterobj->nativeIterator() or asNativeIterator() or getNativeIterator() if you insist.

Whew. I should get a reward for reviewing, but it would be a fraction of your review for hacking. Thanks, r=me with these nits and the bug (double report of OOM) fixed.

/be
Comment 80 Brendan Eich [:brendan] 2010-04-23 18:00:48 PDT
In true gal style, I failed to cut out some cited text. It's easy to lose one's "point" when selecting "point to mark" to delete. I now agree with Andreas: bugzilla needs to cut overcited text, arbitrarily. It'll be great. Gerv cc.

/be
Comment 81 Brendan Eich [:brendan] 2010-04-23 18:04:10 PDT
> Idea: replace this native: label with do { (indent accordingly) and close with
> } while (0). Then replace the goto with a continue.

Er, continue goes to the while(0) and exits. You want a for (;;) loop that breaks at the bottom, with the continue instead of goto as suggested.

Refactoring to tail-call duplicates code a bit, or fragments it. I like goto at this point. But try the breaking loop if you care.

/be
Comment 82 Brendan Eich [:brendan] 2010-04-23 20:41:04 PDT
D'oh, forgot where the native: label was. We have

InitNativeIterator(obj, ...) {
    prologue;
    while (obj) {
        header;
        if (is native &&
            object-ops enumerate hook is js_Enumerate &&
            no JSCLASS_NEW_ENUMERATE)) {
            call old-style class enumerate hook;
          native:
            walk scope property list, etc.
        } else if (is dense array) {
            do dense array iterator init;
        } else {
            call obj->enumerate(... &state ...);
            if (state is the magic cookie)
                goto native;
            collect the enumerable props;
        }
        if (shallow for one reason or another)
            break;
        obj = obj->getProto();
    }
    epilogue;
}

The obvious cleanups:

1. Make the while a do {...} while ((obj = obj->getProto()) != NULL).
2. Make the code at native: till end of "then" clause a helper function.
3. Call it from both the place labeled by native: and the goto native; site.
4. Move the "collect the enumerable props;" part into an else clause.

/be
Comment 83 Andreas Gal :gal 2010-04-24 01:29:36 PDT
Created attachment 441254 [details] [diff] [review]
patch

rebased, brendan's review comments not addressed yet (gary, you can fuzz this)
Comment 84 Andreas Gal :gal 2010-04-24 01:30:03 PDT
Created attachment 441255 [details] [diff] [review]
latest
Comment 85 Andreas Gal :gal 2010-04-24 01:37:13 PDT
A couple oddballs aside there seems to be only one use of NEW_ENUMERATE left:

http://mxr.mozilla.org/mozilla-central/search?string=NEW_ENUMERATE

JSNPRuntime seems to be the only remaining client:

http://mxr.mozilla.org/mozilla-central/source/modules/plugin/base/src/nsJSNPRuntime.cpp

bent seems to know the code. bent, do you know why nsJSNPRuntime is implemented as a native object? It seems to me its really a wrapper and wants to be non-native, in which case it wouldn't need to overwrite the class hook.

I would be quite thrilled if we can remove the NEW_ENUMERATE api.
Comment 86 Gary Kwong [:gkw] [:nth10sd] 2010-04-24 02:09:18 PDT
(In reply to comment #84)
> Created an attachment (id=441255) [details]
> latest

This blows up jsfunfuzz on 64-bit Linux even without it starting to fuzz:

for(f in this){}

Assertion failure: JSVAL_IS_INT(id) || JSVAL_IS_STRING(id), at ../jsiter.cpp:159
Comment 87 Brendan Eich [:brendan] 2010-04-24 07:39:22 PDT
Oops, I forgot to ask for gczeal(2) testing too.

We should do that for any scary patch, in addition to tinderbox-testing that way (which will take beefy machines and long test cycles, but I thought I saw signs of progress on that front in another bug).

/be
Comment 88 Brendan Eich [:brendan] 2010-04-24 07:42:47 PDT
Post to the newsgroup about removing JSCLASS_NEW_ENUMERATE.

Here's the likely and reasonable push-back: how are people making custom lazily-enumerating objects to switch to a non-native (custom JSObjectOps) implementation without new public API? We inside the "circle of trust" can make non-natives, but the embedders in general (or if they follow our rules) cannot.

This is not just an equity issue. It affects our ability to get things done in a more scalable, less coupled way (objectops needs a make-over -- bug 408416).

/be
Comment 89 Andreas Gal :gal 2010-04-24 09:25:41 PDT
A property with id 0x22. I am intrigued. No clue what that means.

#0  0x0000000100146523 in JS_Assert (s=0x1001dc0b8 "JSVAL_IS_INT(id) || JSVAL_IS_STRING(id)", file=0x1001dbdf9 "../jsiter.cpp", ln=159) at ../jsutil.cpp:76
#1  0x00000001000aabdb in Enumerate (cx=0x10088b400, obj=0x101002000, id=22, enumerable=false, flags=1, ht=@0x7fff5fbfe990, vec=@0x7fff5fbfe890) at ../jsiter.cpp:159
#2  0x00000001000aaf75 in InitNativeIterator (cx=0x10088b400, obj=0x101002000, flags=1, sarray=0x7fff5fbfeaf0, slength=0, key=0, nip=0x7fff5fbfeb28) at ../jsiter.cpp:219
#3  0x00000001000ab76b in GetIterator (cx=0x10088b400, obj=0x101002000, flags=1, vp=0x100890428) at ../jsiter.cpp:418
#4  0x00000001000ab9c1 in js_ValueToIterator (cx=0x10088b400, flags=1, vp=0x100890428) at ../jsiter.cpp:543
#5  0x0000000100082c54 in js_Interpret (cx=0x10088b400) at jsops.cpp:470
#6  0x00000001000a6f72 in js_Execute () at jsinterp.cpp:1103
#7  0x0000000100011cde in JS_ExecuteScript (cx=0x10088b400, obj=0x101002000, script=0x1004144c0, rval=0x7fff5fbff748) at ../jsapi.cpp:4784
#8  0x000000010000a1e5 in Process (cx=0x10088b400, obj=0x101002000, filename=0x0, forceTTY=0) at ../../shell/js.cpp:542
#9  0x000000010000aaac in ProcessArgs (cx=0x10088b400, obj=0x101002000, argv=0x7fff5fbff930, argc=0) at ../../shell/js.cpp:863
#10 0x000000010000ac27 in main (argc=0, argv=0x7fff5fbff930, envp=0x7fff5fbff938) at ../../shell/js.cpp:5045
Comment 90 Andreas Gal :gal 2010-04-24 09:45:12 PDT
Created attachment 441290 [details] [diff] [review]
patch

for Gary
Comment 91 Brendan Eich [:brendan] 2010-04-24 09:52:46 PDT
(In reply to comment #89)
> A property with id 0x22.

You mean 22 (decimal), right? AKA 0x16, AKA JSVAL_VOID, AKA as a jsid JS_DEFAULT_XML_NAMESPACE_ID per IRC. Just here for the record ;-).

E4X has the default XML namespace as a variable, believe it or not. It can't be aliased by an string-equated property name.

/be
Comment 92 Andreas Gal :gal 2010-04-24 10:05:46 PDT
I removed the comment for the catch part of for-in because I no longer use the stack for rooting there.
Comment 93 Andreas Gal :gal 2010-04-24 10:12:22 PDT
Object allocation doesn't report, it just returns NULL afaict. So I have to report there.
Comment 94 Brendan Eich [:brendan] 2010-04-24 10:26:46 PDT
(In reply to comment #93)
> Object allocation doesn't report, it just returns NULL afaict. So I have to
> report there.

If this is about:

>+    JSObject *aobj = js_NewArrayObject(cx, 2, vec);
>+    if (!aobj) {
>+        JS_ReportOutOfMemory(cx);

then casual inspection shows you're wrong:

        js_ReportOutOfMemory(cx);
        return NULL;

(from js_NewFinalizeableGCThing from js_NewGCObject from NewObjectWithGivenProto from NewObject from js_NewArrayObject).

But you don't need to read code. The rule is any fallible function taking a leading cx must report or throw before failing. Period. All else is insanity and a guessing game that leads to double reports.

/be
Comment 95 Brendan Eich [:brendan] 2010-04-24 10:27:34 PDT
(In reply to comment #94)
> But you don't need to read code. The rule is any fallible function taking a
> leading cx must report or throw before failing. Period. All else is insanity
> and a guessing game that leads to double reports.

And missing reports/throws -- silent failure.

/be
Comment 96 Gary Kwong [:gkw] [:nth10sd] 2010-04-24 10:28:43 PDT
(In reply to comment #90)
> Created an attachment (id=441290) [details]
> patch
> 
> for Gary

for (let a in (function () {
    yield;
    yield;
    i
})()) {}

Crash [@ js::TraceMonitor::outOfMemory] in js debug shell on 64-bit Linux.

Program received signal SIGSEGV, Segmentation fault.
0x000000000057fd0a in js::TraceMonitor::outOfMemory (this=0x74006f006e0020) at ../jstracer.cpp:2356
2356	           traceAlloc->outOfMemory();
(gdb) bt
#0  0x000000000057fd0a in js::TraceMonitor::outOfMemory (this=0x74006f006e0020) at ../jstracer.cpp:2356
#1  0x000000000057f0b6 in js::TraceRecorder::outOfMemory (this=0x8aed80) at ../jstracer.h:1433
#2  0x00000000005560fb in js::TraceRecorder::monitorRecording (this=0x8aed80, op=JSOP_NEXTITER) at ../jstracer.cpp:7128
#3  0x00000000005b29f2 in js_Interpret (cx=0x8a63f0) at ../jsops.cpp:78
#4  0x0000000000484ddc in js_Execute (cx=0x8a63f0, chain=0x7ffff6c02000, script=0x8b0c30, down=0x0, flags=0, result=0x7fffffffe0c8) at ../jsinterp.cpp:1103
#5  0x0000000000425724 in JS_ExecuteScript (cx=0x8a63f0, obj=0x7ffff6c02000, script=0x8b0c30, rval=0x7fffffffe0c8) at ../jsapi.cpp:4784
#6  0x0000000000403ceb in Process (cx=0x8a63f0, obj=0x7ffff6c02000, filename=0x0, forceTTY=0) at ../../shell/js.cpp:542
#7  0x0000000000404736 in ProcessArgs (cx=0x8a63f0, obj=0x7ffff6c02000, argv=0x7fffffffe2f0, argc=1) at ../../shell/js.cpp:863
#8  0x000000000040c733 in main (argc=1, argv=0x7fffffffe2f0, envp=0x7fffffffe300) at ../../shell/js.cpp:5038
Comment 97 Andreas Gal :gal 2010-04-24 13:30:54 PDT
> If cx is gone then |this| has been deleted. Is it really safe to be here?

Luke says yes.
Comment 98 Andreas Gal :gal 2010-04-24 13:35:32 PDT
#96 is actually bug 560798
Comment 99 Andreas Gal :gal 2010-04-24 13:36:57 PDT
Created attachment 441302 [details] [diff] [review]
patch

Review comments addressed.
Comment 100 Andreas Gal :gal 2010-04-24 13:38:35 PDT
The patch has review. If try server still likes me, I will land it, but in parallel I will ask brendan to take another look to make sure I caught everything.
Comment 101 Brendan Eich [:brendan] 2010-04-24 14:59:19 PDT
Comment on attachment 441302 [details] [diff] [review]
patch


>+JSExtendedClass js_IteratorClass = {
>+  {
>+      "Iterator",
>+      JSCLASS_HAS_PRIVATE |
>+      JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator) |
>+      JSCLASS_MARK_IS_TRACE |
>+      JSCLASS_IS_EXTENDED,
>+      JS_PropertyStub,  JS_PropertyStub, JS_PropertyStub,  JS_PropertyStub,
>+      JS_EnumerateStub, JS_ResolveStub,  JS_ConvertStub,   iterator_finalize,
>+      NULL,             NULL,            NULL,             NULL,
>+      NULL,             NULL,            JS_CLASS_TRACE(iterator_trace), NULL
>+  },
>+  NULL,             NULL,            NULL,             iterator_iterator,
>+  NULL,
>+  JSCLASS_NO_RESERVED_MEMBERS

Not two-space indentation, then four! No Fibonacci indentation either. Here's what I was suggesting (from jsxml.cpp):

JS_FRIEND_DATA(JSExtendedClass) js_NamespaceClass = {
  { "Namespace",
    JSCLASS_CONSTRUCT_PROTOTYPE | JSCLASS_IS_EXTENDED |
    JSCLASS_HAS_RESERVED_SLOTS(NAMESPACE_RESERVED_SLOTS) |
    JSCLASS_MARK_IS_TRACE | JSCLASS_HAS_CACHED_PROTO(JSProto_Namespace),
    JS_PropertyStub,   JS_PropertyStub,   namespace_getProperty, NULL,
    JS_EnumerateStub,  JS_ResolveStub,    JS_ConvertStub,    namespace_finalize,
    NULL,              NULL,              NULL,              NULL,
    NULL,              NULL,              NULL,              NULL },
    namespace_equality,NULL,              NULL,              NULL,
    NULL,              NULL,              NULL,              NULL
};

The inner braces, required by annoying compilers, melt away in this style, and everything columnates as if the function pointers are initializing members of one aggregate type, not two with one nested in the other.

Same for:

>+JSExtendedClass js_GeneratorClass = {

r=me again, diff of patch I reviewed and this, grepped like so:

$ diff /tmp/patch{=,}|grep -v '^[<>] [^-+]'|less

looks good.

Did you test with gczeal(2)?

/be
Comment 102 Andreas Gal :gal 2010-04-24 15:38:17 PDT
Yeah, doing some gczeal tests now while the try server is churning.
Comment 104 Andreas Gal :gal 2010-04-24 18:14:59 PDT
Created attachment 441324 [details] [diff] [review]
patch

Rebase for tip, remove js_CallIteratorNext since sayrer just remove the last reference of it (json).
Comment 105 Gary Kwong [:gkw] [:nth10sd] 2010-04-26 00:43:20 PDT
Created attachment 441442 [details]
1824-line testcase

(In reply to comment #104)
> Created an attachment (id=441324) [details]
> patch
> 
> Rebase for tip, remove js_CallIteratorNext since sayrer just remove the last
> reference of it (json).

$ ./js-dbg-64-tm-linux 1testcase.js 
Assertion failure: regs.pc[1] == JSOP_IFNE, at ../jsops.cpp:482
Aborted

(Tested on 64-bit Linux debug shell) This doesn't seem to occur without the patch on TM tip.
Comment 106 Gervase Markham [:gerv] 2010-04-27 03:38:40 PDT
(In reply to comment #80)
> In true gal style, I failed to cut out some cited text. It's easy to lose one's
> "point" when selecting "point to mark" to delete. I now agree with Andreas:
> bugzilla needs to cut overcited text, arbitrarily. It'll be great. Gerv cc.

Brendan: I'm not entirely sure what you want here; your review comment looked fine to me. Is there any chance you could file a bug explaining in more detail?

https://bugzilla.mozilla.org/enter_bug.cgi?product=mozilla.org&component=Bugzilla:%20Other%20b.m.o%20Issues

Thanks,

Gerv
Comment 107 Andreas Gal :gal 2010-04-28 13:55:06 PDT
Created attachment 442177 [details] [diff] [review]
patch

rebased
Comment 108 Andreas Gal :gal 2010-04-28 13:56:45 PDT
Gary, awesome testcase! I missed JSOP_IFNEX. ++fuzzers
Comment 109 Andreas Gal :gal 2010-04-28 13:59:00 PDT
I really would like to take out the split between IFNE and IFNEX.
Comment 110 Andreas Gal :gal 2010-04-28 15:49:14 PDT
Created attachment 442214 [details] [diff] [review]
fix for IFNEX
Comment 111 Andreas Gal :gal 2010-04-28 15:49:38 PDT
Comment on attachment 442214 [details] [diff] [review]
fix for IFNEX

very little code added, I suggest interdiff
Comment 112 Andreas Gal :gal 2010-04-28 18:55:54 PDT
Created attachment 442284 [details] [diff] [review]
rebase
Comment 113 Gary Kwong [:gkw] [:nth10sd] 2010-04-29 08:44:11 PDT
(In reply to comment #112)
> Created an attachment (id=442284) [details]
> rebase

watch("x", (function() {
  yield
}))
d = 0 
x = 0
for (var c = 0; c < 4; c++) {
  for each(d in x) {}
}

crashes js opt shell with -j at js::TraceRecorder::unboxNextValue and crashes js debug shell at JSObject::getClass. Removing the "d=0" line results in a crash at js_Interpret and asserts js debug shell at Assertion failure: !JSVAL_IS_PRIMITIVE(regs.sp[-1]), at ../jsops.cpp:524

(gdb) bt
#0  0x001394a5 in js::TraceRecorder::unboxNextValue ()
#1  0x0014b658 in js::TraceRecorder::monitorRecording ()
#2  0x0005887f in js_Interpret ()
#3  0x00064223 in js_Execute ()
#4  0x0000ec7c in JS_ExecuteScript ()
#5  0x000044ac in Process ()
#6  0x0000861a in main ()
(gdb) x/i $eip
0x1394a5 <_ZN2js13TraceRecorder14unboxNextValueERPN7nanojit4LInsE+53>:  mov    0x4(%edi),%eax
(gdb) x/1b $edi
0x0:    Cannot access memory at address 0x0

This seems to be a a null +4 pointer dereference.
Comment 114 Andreas Gal :gal 2010-04-29 08:52:26 PDT
(gdb) down
#0  0x0000000100177a23 in js::LeaveTree (tm=0x1003c65f0, state=@0x7fff5fbfe980, lr=0x100898758) at ../jstracer.cpp:6667
6667	                if (!NativeToValue(cx,
(gdb) list
6662	             * (Some opcodes, like JSOP_CALLELEM, produce two values, hence the
6663	             * loop.)
6664	             */
6665	            TraceType* typeMap = innermost->stackTypeMap();
6666	            for (int i = 1; i <= cs.ndefs; i++) {
6667	                if (!NativeToValue(cx,
6668	                                   regs->sp[-i],
6669	                                   typeMap[innermost->numStackSlots - i],
6670	                                   (jsdouble *) state.deepBailSp
6671	                                   + innermost->sp_adj / sizeof(jsdouble) - i)) {
(gdb) p cs.ndefs
$1 = 2 '\002'
(gdb) p (JSOp)op
$2 = JSOP_MOREITER

Bailing out on MOREITER, and the values are not in place it seems.
Comment 115 Gary Kwong [:gkw] [:nth10sd] 2010-04-30 04:54:51 PDT
(In reply to comment #112)
> Created an attachment (id=442284) [details]
> rebase

(arguments[-1])--
for(y in arguments){}

asserts js debug shell without -j on TM tip with this patch at Assertion failure: u < INT_STRING_LIMIT, at ../jsstrinlines.h:67 - it doesn't seem to assert without the patch.
Comment 116 Gary Kwong [:gkw] [:nth10sd] 2010-05-01 09:42:09 PDT
(In reply to comment #112)
> Created an attachment (id=442284) [details]
> rebase

try {
  (function() {
    this[ - 1] = (function() {})
  })()
} catch(e) {}
(function() {
  for (var x in this) print(x)
})()

also asserts js debug shell without -j with this patch at Assertion failure: u < INT_STRING_LIMIT, at ../jsstrinlines.h:67 but also crashes 64-bit opt shell without -j at:

Exception Type:  EXC_BAD_ACCESS (SIGSEGV)
Exception Codes: KERN_INVALID_ADDRESS at 0x0000002100187d70
Crashed Thread:  0  Dispatch queue: com.apple.main-thread

Thread 0 Crashed:  Dispatch queue: com.apple.main-thread
0   js-opt-64-tm-darwin           	0x000000010000e2b3 JS_EncodeString + 19
1   js-opt-64-tm-darwin           	0x000000010000309b Print(JSContext*, unsigned int, long*) + 59
2   js-opt-64-tm-darwin           	0x000000010005a7b4 js_Interpret + 41060
3   js-opt-64-tm-darwin           	0x00000001000622ff js_Execute + 607
4   js-opt-64-tm-darwin           	0x000000010000d810 JS_ExecuteScript + 32
5   js-opt-64-tm-darwin           	0x0000000100003a33 Process(JSContext*, JSObject*, char*, int) + 1443
6   js-opt-64-tm-darwin           	0x0000000100007339 main + 1337
7   js-opt-64-tm-darwin           	0x0000000100001846 _start + 224
8   js-opt-64-tm-darwin           	0x0000000100001765 start + 33

===


v = s = [function(){}, function(){}]
try {
  (function() {
    __defineGetter__("",
      function() {
      yield
      }
    )
  })()
} catch(e) {}
(function() {
  for each(var w in this) {
    for (c in w) {}
  }
})()

crashes js opt and debug shells at what seems to be a null dereference:

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_PROTECTION_FAILURE at address: 0x00000001
0x003d2fa8 in ?? ()
(gdb) bt
#0  0x003d2fa8 in ?? ()
#1  0x00121264 in js::ExecuteTree ()
#2  0x0014164c in js::MonitorLoopEdge ()
#3  0x00062a5a in js_Interpret ()
#4  0x00064223 in js_Execute ()
#5  0x0000ec7c in JS_ExecuteScript ()
#6  0x000044ac in Process ()
#7  0x0000861a in main ()
(gdb) x/i $eip
0x3d2fa8:       mov    (%esi),%edx
(gdb) x/1b $esi
0x1:    Cannot access memory at address 0x1
Comment 117 Gary Kwong [:gkw] [:nth10sd] 2010-05-01 23:21:26 PDT
(In reply to comment #112)
> Created an attachment (id=442284) [details]
> rebase

__defineGetter__("", gc)
for (x in [0, 0, 0, 0])
for each(w in this) {}

crashes js dbg shell with -j at JSObject::setPrivate at 0xdadadad8 with this patch.

===

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0xdadadadc
0x00025a12 in JSObject::setPrivate (this=0x602200, data=0x40cff0) at jsobj.h:382
382             JS_ASSERT(getClass()->flags & JSCLASS_HAS_PRIVATE);
(gdb) bt
#0  0x00025a12 in JSObject::setPrivate (this=0x602200, data=0x40cff0) at jsobj.h:382
#1  0x000a6d24 in JSObject::setNativeIterator (this=0x602200, ni=0x40cff0) at jsobjinlines.h:336
#2  0x000a65a1 in GetIterator (cx=0x85a600, obj=0x602000, flags=3, vp=0xbfffedb8) at ../jsiter.cpp:437
#3  0x000a67d6 in js_ValueToIterator (cx=0x85a600, flags=3, vp=0xbfffedb8) at ../jsiter.cpp:559
#4  0x0015e0fc in js::ObjectToIterator (cx=0x85a600, obj=0x602000, flags=3, objp=0xbfffede4) at ../jstracer.cpp:13536
#5  0x003e4ead in ?? ()
#6  0x00157260 in js::ExecuteTrace (cx=0x85a600, f=0x808a0c, state=@0xbfffee70) at ../jstracer.cpp:6388
#7  0x0016d90d in js::ExecuteTree (cx=0x85a600, f=0x808a0c, inlineCallCount=@0xbffff2e0, innermostNestedGuardp=0xbfffef44, lrp=0xbfffef48) at ../jstracer.cpp:6488
#8  0x0017626a in js::MonitorLoopEdge (cx=0x85a600, inlineCallCount=@0xbffff2e0, reason=js::Record_Branch) at ../jstracer.cpp:6998
#9  0x0007fe44 in js_Interpret (cx=0x85a600) at jsops.cpp:483
#10 0x000a20f1 in js_Execute () at jsinterp.cpp:1103
#11 0x000124a7 in JS_ExecuteScript (cx=0x85a600, obj=0x602000, script=0x40cf20, rval=0xbffff778) at ../jsapi.cpp:4777
#12 0x0000b0e6 in Process (cx=0x85a600, obj=0x602000, filename=0x0, forceTTY=0) at ../../shell/js.cpp:542
#13 0x0000bab4 in ProcessArgs (cx=0x85a600, obj=0x602000, argv=0xbffff8fc, argc=1) at ../../shell/js.cpp:863
#14 0x0000bc69 in main (argc=1, argv=0xbffff8fc, envp=0xbffff904) at ../../shell/js.cpp:5038
(gdb) x/i $eip
0x25a12 <_ZN8JSObject10setPrivateEPv+24>:       mov    0x4(%eax),%eax
(gdb) x/1b $eax
0xdadadad8:     Cannot access memory at address 0xdadadad8
Comment 118 Andreas Gal :gal 2010-05-03 16:10:54 PDT
Gary, #117 is an awesome test case. Thanks.
Comment 119 Andreas Gal :gal 2010-05-03 16:17:32 PDT
Created attachment 443225 [details] [diff] [review]
fix for #117
Comment 120 Andreas Gal :gal 2010-05-03 16:19:11 PDT
Created attachment 443226 [details] [diff] [review]
fix for #116, ++gary
Comment 121 Andreas Gal :gal 2010-05-06 15:31:05 PDT
Created attachment 443978 [details] [diff] [review]
patch

Fix for xpcshell-crash. MOREITER doesn't guard on the iterator class because it claims JSOP_FOR* at the top of the loop is already doing that. We better actually do that then.
Comment 122 Andreas Gal :gal 2010-05-06 15:33:25 PDT
Created attachment 443979 [details] [diff] [review]
refreshed to TM tip
Comment 123 Andreas Gal :gal 2010-05-06 21:05:54 PDT
Mochi-test failures happen in this code:

  var todelete = [];
  for each (var child in content) {
    var stepstr = child.@step.toString();
    var stepsarr = stepstr.split(",");

child seems to be invalid.

content is coming from here:

function checkResults(root, step)
{
  var output = expectedOutput.copy();
  setForCurrentStep(output, step);

There is a comment about expectedOutput:

* expectedOutput: e4x data containing the expected output. It can optionally
* be enclosed in an <output> element as most tests generate
* more than one node of output.

So looks like a non-standard-extension for-each loop over a non-standard-extension e4x object goes wrong. FML. Investigating.
Comment 124 Andreas Gal :gal 2010-05-06 21:49:03 PDT
Shell test case that fails. No jit required.

var order = new XML()

order=
<order id="555">
<date>2005-08-01</date>
<customer>
   <firstname>John</firstname>
   <lastname>Johnson</lastname>
</customer>
<item>
   <name>Maxilaku</name>
   <qty>5</qty>
   <price>155.00</price>
</item>
    </order>;

for each (i in order)
    print(i);
Comment 125 Andreas Gal :gal 2010-05-07 01:59:02 PDT
Created attachment 444054 [details] [diff] [review]
patch

This patch adds a backdoor to get at kids of xml objects that are not lists.
Comment 126 Andreas Gal :gal 2010-05-07 17:56:12 PDT
http://hg.mozilla.org/tracemonkey/rev/b15fd8b568e4
Comment 127 Nicholas Nethercote [:njn] (on vacation until July 11) 2010-05-08 00:16:25 PDT
I see a 1.5x speedup on my Mac for string-fasta.  Ten points to Gryffindor!
Comment 128 Brendan Eich [:brendan] 2010-05-08 10:55:19 PDT
Comment on attachment 444054 [details] [diff] [review]
patch

Solicit review for non-trivial changes -- this is an example.

>         if (flags & JSITER_FOREACH) {
>             jsval *vp = vec.end() - 1;

Nit: blank line here.

>+            /*
>+             * For whatever reason all XML objects with kids enumerate their kids, but only
>+             * lists allow you to actually retrieve those properties, so we create ourselves
>+             * a disgusting backdoor.
>+             */
>+            if (obj->isXML()) {
>+                if (!js_GetXMLProperty(cx, obj, id, vp))
>+                    return false;
[snip]
>+++ b/js/src/jsxml.cpp
>@@ -3874,16 +3874,51 @@ GetProperty(JSContext *cx, JSObject *obj
>      * duplicates the last element matched by id. See bug 336921.
>      */
>     list->xml_target = xml;
>     list->xml_targetprop = nameqn;
>     *vp = OBJECT_TO_JSVAL(listobj);
>     return true;
> }
> 
>+/*
>+ * Get the property of an XML object. For all XML objects that have kids return the
>+ * kid if an indexed property name is supplied.
>+ */
>+JSBool
>+js_GetXMLProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
>+{
>+    JSXML *xml = (JSXML *) JS_GetInstancePrivate(cx, obj, &js_XMLClass, NULL);
>+    if (!xml)
>+        return true;
>+
>+    uint32 index;
>+    if (js_IdIsIndex(id, &index)) {
>+        if (JSXML_HAS_KIDS(xml)) {
>+            if (index < xml->xml_kids.length) {
>+                JSXML *kid = XMLARRAY_MEMBER(&xml->xml_kids, index, JSXML);
>+                if (!kid) {
>+                    *vp = JSVAL_VOID;

Set *vp = JSVAL_VOID first thing to cover the early return true and avoid replicating this assignment here and below:

>+                    return true;
>+                }
>+                JSObject *kidobj = js_GetXMLObject(cx, kid);
>+                if (!kidobj)
>+                    return false;
>+
>+                *vp = OBJECT_TO_JSVAL(kidobj);
>+            } else {
>+                *vp = JSVAL_VOID;

... which nicely avoids the runt-else blight.

r=me on followup patch to address these points.

/be
Comment 129 Igor Bukanov 2010-05-09 00:48:34 PDT
follow up http://hg.mozilla.org/tracemonkey/rev/d9ef93881da0 - can't trace generator close
Comment 130 Brendan Eich [:brendan] 2010-05-10 17:56:46 PDT
Comment on attachment 442214 [details] [diff] [review]
fix for IFNEX

A bunch of other patches are obsolete, too -- right? Please mark them so as needed.

/be
Comment 131 Andreas Gal :gal 2010-05-11 20:07:55 PDT
A couple bugs need fixing:

- we are running out of an inner for-in loop in some cases when the branch is fused (existing bug, dvander will file and fix) (*)
- the ->getNativeIterator() should be !->getNativeIterator to handle Iterator.prototype. I will file and fix.
- http://hg.mozilla.org/tracemonkey/rev/d9ef93881da0 is a dud and should be removed, the real cause is really (*), the assert near CloseGenerator should simply be removed
Comment 132 Brendan Eich [:brendan] 2010-05-11 20:41:31 PDT
(In reply to comment #131)
> - http://hg.mozilla.org/tracemonkey/rev/d9ef93881da0 is a dud and should be
> removed, the real cause is really (*), the assert near CloseGenerator should
> simply be removed

Whew -- I told ya over iChat that was no good! :-P

/be
Comment 133 Andreas Gal :gal 2010-05-11 20:47:47 PDT
You are still wrong though. Guard is needed :)
Comment 134 Brendan Eich [:brendan] 2010-05-11 21:02:17 PDT
Oh come on! I know you have to guard, but not every time and not in ENDITER. iChat transcript:

gal: yeah but you still have to guard
/be: every time?
/be: why?
gal: well we never hoist guards right now
gal: the loop must be specialized to that kind of iterator
/be: yes, why not?
gal: we just don't do it yet, we never came up with a prolog piece that contains hoisted guards
gal: not our main perf issue

At no point was a guard being necessary in dispute. :-(

/be
Comment 135 Brendan Eich [:brendan] 2010-05-11 21:02:46 PDT
Nits in comment 128 need picking still.

/be
Comment 136 Brendan Eich [:brendan] 2010-05-11 21:10:06 PDT
(In reply to comment #135)
> Nits in comment 128 need picking still.

Or that patch needs landing. Or something -- should we use followup bugs now that the main patch has landed? Usually that's better for auditing and keeping bugs shorter. This one could be fixed-in-tracemonkey, since your patch did make things fast (yay!).

/be
Comment 137 Andreas Gal :gal 2010-05-11 21:13:36 PDT
No, you were wondering whether inside the loop body we need a guard in FOR*. Hence my comment that we need to specialize the LOOP. ENDITER is after the loop. Anyway, yeah nits still need fixing.
Comment 138 Brendan Eich [:brendan] 2010-05-11 21:57:56 PDT
"No, you were wondering" -- exactly, I was wondering about *where* to guard, not whether. Yeesh.

What's the point of code review if it falls on deaf ears, then later the dud is proclaimed a dud, then my review comments are misrepresented?

The ENDITER patch never made sense. The guard every time through the loop can be hoisted, some day (we used to guard on class in JSOP_NEXTITER, so this is not a regression). That's all.

/be
Comment 139 Andreas Gal :gal 2010-05-11 22:36:23 PDT
Created attachment 444825 [details] [diff] [review]
patch

review nit, removed unnecessary abort (we will still fall of trace since we re-enter the interpreter, but generators are rare enough that it doesn't hurt either way), the rest of the nits affect code that never went into the tree
Comment 140 Brendan Eich [:brendan] 2010-05-11 22:59:35 PDT
Comment on attachment 444825 [details] [diff] [review]
patch

Was there a missing or extraneous ! to fix also, or did that already go in?

/be
Comment 142 Boris Zbarsky [:bz] (Out June 25-July 6) 2010-06-01 20:32:55 PDT
This changed web-visible behavior _somehow_ leading to JS exceptions where there didn't use to be any.  See bug 569516.
Comment 143 Andreas Gal :gal 2010-06-02 00:08:15 PDT
bz, with this patch we no longer suppress deletion during iteration, which we believe is the right thing to do. Browsers disagree widely on this particular piece, and we are hoping to standardize on snapshot (ignore deletion + addition after iteration starts) behavior. If we broke one website, we should help them fix this. If more than one site depends on it, I will have to row back and patch this (not really difficult, but its not free and just seems so ridiculous).
Comment 144 Brendan Eich [:brendan] 2010-06-02 07:10:54 PDT
I'm smelling defeat. But Oliver J. Hunt my irc and Ecma tc39 pal of JSC fame said (non-tauntingly) that "it's only a branch" to detect deletion during for-in (any delete), and then do the slow thing. He's right.

/be
Comment 145 Brendan Eich [:brendan] 2010-06-02 07:11:43 PDT
Branch depending on a load of a hot runtime or thread generation number, akin to rt->propertyRemovals.

/be
Comment 146 Mark S. Miller 2010-06-02 09:57:08 PDT
> I'm smelling defeat.

Why? My olfactory sense must not be as sensitive. The suggested change (pure snapshot) still smells rather fragrant AFAICT. What am I missing?
Comment 147 Brendan Eich [:brendan] 2010-06-02 10:46:03 PDT
(In reply to comment #146)
> > I'm smelling defeat.
> 
> Why? My olfactory sense must not be as sensitive. The suggested change (pure
> snapshot) still smells rather fragrant AFAICT. What am I missing?

See comment 142, to which Andreas's comment 143 replied, to which my comment 144 replied -- comment 142 said "See bug 569516."

It looks like the app linked from bug 569516 may delete during for-in and expect ES1-5-specified deleted property suppression to happen. As it has happened in every release of Firefox.

/be
Comment 148 Brendan Eich [:brendan] 2010-06-02 10:46:41 PDT
(In reply to comment #147)
> (In reply to comment #146)
> It looks like the app linked from bug 569516 may delete during for-in and
> expect ES1-5-specified deleted property suppression to happen. As it has
> happened in every release of Firefox.

And every other major browser, including Chrome.

/be
Comment 149 Jeff Walden [:Waldo] (remove +bmo to email) 2010-06-02 11:21:11 PDT
One breakage isn't the end of the world yet; I expect one breakage from just about any change we make.  The question is: will breakage be pervasive across many sites?  We don't yet have experience to say on that point.
Comment 150 Andreas Gal :gal 2010-06-02 11:23:57 PDT
The problem can be fixed, and is relatively cheap. One branch and some extra code per iteration that isn't taken (but messes up reg alloc a bit) is all it takes. I would prefer if we ween the web of this insane deletion suppression if we can pull it off. If not, I will go and gladly fix this. I just honestly believe the world will be a better place without this particular piece of insanity.
Comment 151 Brendan Eich [:brendan] 2010-07-04 22:42:37 PDT
*** Bug 548903 has been marked as a duplicate of this bug. ***

Note You need to log in before you can comment on or make changes to this bug.