Closed Bug 354982 Opened 13 years ago Closed 13 years ago

Cleaning up iterator implementation

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Keywords: fixed1.8.1.1, Whiteboard: js1.7)

Attachments

(2 files, 10 obsolete files)

[This is a spin-off of the bug 354750, which is security-related. As such I mark this also as security-restricted even if it is an enhancement. Let me know, if this is overkill. ]

Recent evolution of iterator protocol, see bug 354750, made JSContext.cachedIterObj redundant. It should be removed.

In addition it was discovered that the interpreter does not need 2 slots to keep the state of the iterator, as the enumerating iterator knows its original object via parent slot. This should be addressed as well.
Assignee: general → igor.bukanov
Recording the coming patch dependencies.
Depends on: 355025, 355029
Attached patch Implementatib v0 (obsolete) — Splinter Review
Work in progress with the following changes:

1. cachedIterObj is removed.

2. The enumerating iterator knows how to change the prototype chain on its own without creating an extra iteration objects. To record the original object that started the enumeration it uses JSSLOT_PROTO as the enumerator never escapes to scripts. Thus the interpreter does not need to worry about enumerations simplifying the code there significantly.

3. The code takes advantage of the fact that iterator's methods are read-only and permanent. So for instances of non-enumerating native iterators it calls iter_next directly.

4. For enumerators over XML object the code never enumerates over their prototype chain.

Now with this patch the interpreter does not need to store origobj and obj, but the patch does not change stack allocation in the interpreter as it is not clear what would be the best way to do it. Ideally it would be nice to save both stack slots for obj and origobj but that requires an extra instruction that would call js_ValueToIterator. Right?
Attached patch Implementation v1 (obsolete) — Splinter Review
Work in progress (untested).

Besides the cleanups from the above this also contains the following:

1. Only 2, not 3 slots are used for iterator and its original object. This can be reduced to just one slot if one renames toobject by toiter and call js_ValueToIter there directly. But that requires to change the emitter to prefix toiter with for_each and similar prefixes and I am not sure that it would be allowed on 1.8.1 branch.

2. For the common case of enumerator/native iterator StopIteration is not thrown and the interpreter notified directly by a boolean flag about stopped iteration. That flag can be replaces by passing JSVAL_HOLE as rval from js_CallIteratorNext but it would expose JSVAL_HOLE to GC-reachable location.

3. JS_RVAL2_ITERKEY is removed. As far as I can see that was used to avoid constructing [key, pair] for for-each enumerator but the new code avoids the whole issue throw explicit enumeration code path.

Now I need to test this.
Attachment #240822 - Attachment is obsolete: true
Attached patch Implementation v2 (obsolete) — Splinter Review
This the previous patch with stupid bugs/mistypes removed, which passes some trivial tests and which uses JSVAL_HOLE to indicate to the interpreter that the iterator stopped.
Attachment #241125 - Attachment is obsolete: true
Attachment #241136 - Flags: review?(brendan)
Attached patch Implementation v3 (obsolete) — Splinter Review
Compared with the previous version this patch removes the need for JSOP_TOOBJECT as js_valueToIterator now knows how to deal with null and undefined when enumerating. For compatibility JSOP_TOOBJECT is preserved but it became an empty case in the interpreter switch.

The patch shrinks an optimized build of jsshell compiled with GCC 4.1 -Os for i386 by 1600 bytes.
Attachment #241136 - Attachment is obsolete: true
Attachment #241164 - Flags: review?(brendan)
Attachment #241136 - Flags: review?(brendan)
Comment on attachment 241164 [details] [diff] [review]
Implementation v3

Couple of quick comments:

* Just rename JSOP_TOOBJECT to JSOP_UNUSED103.

* "Increment" JSXDR_BYTECODE_VERSION in jsxdrapi.h.

* With the above, you can remove the JSOP_TOOBJECT* case from js_Interpret altogether.

/be
Attached patch Implementation v4 (obsolete) — Splinter Review
In this version I removed TO_OBJECT and changed JSOP_FORIN, JSOP_FOREACH JSOP_FOREACHKEYVAL to mean to convert the stack top into iterator. In this way only single stack slot is necessary the code is reduced even more. But it required to update the emitter, which was a simple change to move JSOP_FORIN etc. before the loop jump, and the decompiler, which I do not know how to deal with. So with the patch applied decompilation of any for-in loop asserts.
Attachment #241164 - Attachment is obsolete: true
Attachment #241189 - Flags: review?(brendan)
Attachment #241164 - Flags: review?(brendan)
I'm plussing Igor's patch, with changes made here.  I'll solicit Igor's second r+ in a second.

/be
Attachment #241189 - Attachment is obsolete: true
Attachment #241227 - Flags: review+
Attachment #241189 - Flags: review?(brendan)
Comment on attachment 241227 [details] [diff] [review]
Implementation v5

I hope bugzilla's interdiff works. Let me know if any of the comment changes are misworded.

/be
Attachment #241227 - Flags: review?(igor.bukanov)
This is a lesson to me and probably others tending Mozilla code: don't be too conservative when modifying.  I left the ancient ediface of the for-in loop code alone, after it had been ECMA-ized with things like JSOP_TOOBJECT seven or so years ago.  Thanks to Igor for cleaning up.

/be
Blocks: js1.7src
Flags: blocking1.8.1.1?
Comment on attachment 241227 [details] [diff] [review]
Implementation v5

Even less code! Nice :)

But I should remember to check for *all* instances of the jsop when changing its meaning.
Attachment #241227 - Flags: review?(igor.bukanov) → review+
Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.283; previous revision: 3.282
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.122; previous revision: 3.121
done
Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.221; previous revision: 3.220
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.178; previous revision: 3.177
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.296; previous revision: 3.295
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.47; previous revision: 3.46
done
Checking in jsiter.h;
/cvsroot/mozilla/js/src/jsiter.h,v  <--  jsiter.h
new revision: 3.16; previous revision: 3.15
done
Checking in jsopcode.c;
/cvsroot/mozilla/js/src/jsopcode.c,v  <--  jsopcode.c
new revision: 3.188; previous revision: 3.187
done
Checking in jsopcode.tbl;
/cvsroot/mozilla/js/src/jsopcode.tbl,v  <--  jsopcode.tbl
new revision: 3.80; previous revision: 3.79
done
Checking in jsxdrapi.h;
/cvsroot/mozilla/js/src/jsxdrapi.h,v  <--  jsxdrapi.h
new revision: 1.24; previous revision: 1.23
done

Fixed on trunk.  I made one comment change, in jsiter.c -- I'll attach the patch I landed for posterity and to nominate for 1.8.1.1 (but it may be obsoleted in the near term due to other changes).

/be
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Attached patch what I just landed (obsolete) — Splinter Review
Attachment #241260 - Flags: review+
Attachment #241260 - Flags: approval1.8.1.1?
Comment on attachment 241260 [details] [diff] [review]
what I just landed

Sigh.  Consolidated 1.8 branch patch in a bit.

/be
Attachment #241260 - Attachment is obsolete: true
Attachment #241260 - Flags: review+
Attachment #241260 - Flags: approval1.8.1.1?
Attached patch 1.8 branch version of fixes (obsolete) — Splinter Review
Asking for igor to r+, since I had to merge and bring over the changes for bug 352846 and bug 355029, as well as bug 347065.

Asking for 1.8.1 approval too, since Igor and I are concerned about fixing this sooner rather than later, given the independent discovery of at least one of the exploitable holes.

/be
Attachment #241269 - Flags: review?(igor.bukanov)
Attachment #241269 - Flags: approval1.8.1?
Attachment #241269 - Flags: approval1.8.1.1?
Attachment #241269 - Flags: review?(igor.bukanov) → review+
Attached patch 1.8 branch version of fixes (obsolete) — Splinter Review
Fixed argo bustage (ISO C leaves #if in macro actual arg undefined, so of course GCC says it's illegal).

/be
Attachment #241269 - Attachment is obsolete: true
Attachment #241279 - Flags: review+
Attachment #241279 - Flags: approval1.8.1?
Attachment #241279 - Flags: approval1.8.1.1?
Attachment #241269 - Flags: approval1.8.1?
Attachment #241269 - Flags: approval1.8.1.1?
Flags: in-testsuite-
Comment on attachment 241279 [details] [diff] [review]
1.8 branch version of fixes

We're only doing an RC3 for showstoppers, and since this wasn't nominated for blocking1.8.1, I'm guessing it's not one of those :)

I'd suggest that we take this in 1.8.1.1
Attachment #241279 - Flags: approval1.8.1? → approval1.8.1-
Comment on attachment 241279 [details] [diff] [review]
1.8 branch version of fixes

Then we need a + on 1.8.1.1 and drivers should plus the minimal fix patches in the related bugs.

/be
Attachment #241279 - Flags: approval1.8.1.1? → approval1.8.1.1+
Are you saying that there are related bugs that are blocking1.8.1?  If so, please nominate.
dbaron: already nominated.

/be
Blocks: 355658
Flags: blocking1.8.1.1? → blocking1.8.1.1+
Whiteboard: js1.7
Recording bug source dependency
Blocks: 355474
Due to security fixes that was made for 1.8.1 without the clean-up implementation applied (especially due to bug 355474) the patch required heavy update. So to simplify life I also added to the merged patch the fixes from bug  355658 which is approved for 1.8.1.1. 

In this way I knew how to verify the merged work: after the patch applied the only difference between the trunk and 1.8.1 version of jsiter.c should come from bug 359062. And viola, it was indeed so. Due to this property I am very sure about the patch.




  

355474, 355658
Attachment #241279 - Attachment is obsolete: true
Attachment #245035 - Flags: approval1.8.1.1?
The previous attachment contained the wrong patch.
Attachment #245035 - Attachment is obsolete: true
Attachment #245036 - Flags: approval1.8.1.1?
Attachment #245035 - Flags: approval1.8.1.1?
Attachment #241279 - Flags: approval1.8.1.1+
Comment on attachment 245036 [details] [diff] [review]
1.8 branch version + fix from bug 355658 for real

Approved for 1.8.1 branch, a=jay for drivers.  Please land asap and confirm that we have all related patches from dependency bugs.  Thanks!
Attachment #245036 - Flags: approval1.8.1.1? → approval1.8.1.1+
Part of changes from the patch was already committed so here is an updated version.
Attachment #245036 - Attachment is obsolete: true
Attachment #246361 - Flags: approval1.8.1.1?
Attachment #245036 - Flags: approval1.8.1.1+
Comment on attachment 246361 [details] [diff] [review]
Updated 1.8 branch version + fix from bug 355658 for real

carrying over a=jay from yesterday
Attachment #246361 - Flags: approval1.8.1.1? → approval1.8.1.1+
I committed the patch from comment 25 to MOZILLA_1_8_BRANCH:

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.214.2.29; previous revision: 3.214.2.28
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.80.4.17; previous revision: 3.80.4.16
done
Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.128.2.61; previous revision: 3.128.2.60
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.104.2.26; previous revision: 3.104.2.25
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.181.2.75; previous revision: 3.181.2.74
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.17.2.27; previous revision: 3.17.2.26
done
Checking in jsiter.h;
/cvsroot/mozilla/js/src/jsiter.h,v  <--  jsiter.h
new revision: 3.6.2.10; previous revision: 3.6.2.9
done
Checking in jsopcode.c;
/cvsroot/mozilla/js/src/jsopcode.c,v  <--  jsopcode.c
new revision: 3.89.2.67; previous revision: 3.89.2.66
done
Checking in jsopcode.tbl;
/cvsroot/mozilla/js/src/jsopcode.tbl,v  <--  jsopcode.tbl
new revision: 3.43.2.20; previous revision: 3.43.2.19
done
Checking in jsxdrapi.h;
/cvsroot/mozilla/js/src/jsxdrapi.h,v  <--  jsxdrapi.h
new revision: 1.14.58.10; previous revision: 1.14.58.9
done

Keywords: fixed1.8.1.1
You need to log in before you can comment on or make changes to this bug.