ParameterInitializerRewriter must maintain temporary variable order

ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n

Committed: https://crrev.com/2d090ee46ad88272653873eec8b1bd465ce37b50
Cr-Commit-Position: refs/heads/master@{#36150}

[adamk, 2016-03-10 21:51:24]

Description was changed from

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

BUG=v8:4791
LOG=n
==========

to

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n
==========

[adamk, 2016-03-10 21:51:48]

adamk@chromium.org changed reviewers:
+ nikolaos@chromium.org

[nickie, 2016-03-11 10:24:06]

On 2016/03/10 21:51:49, adamk wrote:

LGTM.

As a (possibly sci-fi) comment, if we have an arrow function like:

   (x = [array_literal]) => whatever

and the array_literal contains N spreads, when this is re-scoped we expect O(N)
temporaries to be placed in the vector (heap space) and we'll take O(NlogN) time
for sorting it.  I don't expect this to be a very frequent pattern, at least for
large values of N, so I believe we can just ignore it.

If we feel we cannot, I can think of two solutions:

   1. Relying on the order in which every subtree is visited, at least for all
visitors that put things in the scope (and making sure we document this).
   2. Keeping the same idea but making sure that we use a sorting algorithm
which has O(N) complexity in case the elements are "pretty well sorted" to begin
with.  I believe that this will be the case here and maybe std::sort is already
good at that.

[nickie, 2016-03-11 10:48:44]

Sorry, I forgot to publish this with the previous LGTM.

https://codereview.chromium.org/1784893003/diff/1/src/parsing/parameter-initi...
File src/parsing/parameter-initializer-rewriter.cc (right):

https://codereview.chromium.org/1784893003/diff/1/src/parsing/parameter-initi...
src/parsing/parameter-initializer-rewriter.cc:52: std::sort(temps_.begin(),
temps_.end(), LessThanSecond());
You wouldn't need LessThanSecond if the elements of the pair were reversed:

    std::vector<std::pair<int, Variable*>> temps_;

The default comparison for pairs follows lexicographic order.
If you do so, I suggest that you add a comment here explaining the order in
which the vector will be sorted.

[adamk, 2016-03-11 21:19:40]

Looking at this code again, I realized it's not actually guaranteed to work,
since the indices aren't necessarily unique (since RemoveUnresolved() shrinks
Scope::temps_ on removal).

Of course that doesn't cause a problem on this test case, but it's still bad.

I'm going to mull what a more robust solution might look like (and maybe it'll
also avoid being really slow in the worst case :).

[adamk, 2016-05-09 23:14:59]

Uniqueness of indices is now handled (by nulling-out removed items instead of
shrinking the List). PTAL.

[nickie, 2016-05-10 13:47:08]

lgtm

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc
File src/ast/scopes.cc (right):

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc#newco...
src/ast/scopes.cc:989: if (temps_.length() > 0) {
If you have length() > 0 but only null elements, you'll still print the header.

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc#newco...
src/ast/scopes.cc:992: if (temps_[i] != NULL) {
Not nullptr?  :-)

[adamk, 2016-05-10 17:36:11]

Thanks for the quick turnaround. Not sure why I didn't take this approach two
months ago, but it's really not too ugly.

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc
File src/ast/scopes.cc (right):

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc#newco...
src/ast/scopes.cc:989: if (temps_.length() > 0) {
On 2016/05/10 13:47:08, nickie wrote:
> If you have length() > 0 but only null elements, you'll still print the
header.

This is probably the ugliest part of this approach :)

Fixed.

https://codereview.chromium.org/1784893003/diff/40001/src/ast/scopes.cc#newco...
src/ast/scopes.cc:992: if (temps_[i] != NULL) {
On 2016/05/10 13:47:08, nickie wrote:
> Not nullptr?  :-)

Was going for consistent, but looks like this function is already inconsistent.
Switched :)

[adamk, 2016-05-10 17:36:28]

The CQ bit was checked by adamk@chromium.org

[adamk, 2016-05-10 17:36:28]

The patchset sent to the CQ was uploaded after l-g-t-m from
nikolaos@chromium.org
Link to the patchset: https://codereview.chromium.org/1784893003/#ps60001
(title: "Nikolaos comments")

[commit-bot: I haz the power, 2016-05-10 17:36:32]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1784893003/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1784893003/60001

[commit-bot: I haz the power, 2016-05-10 18:09:37]

Description was changed from

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n
==========

to

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n
==========

[commit-bot: I haz the power, 2016-05-10 18:09:38]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-05-10 18:10:30]

Description was changed from

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n
==========

to

==========
ParameterInitializerRewriter must maintain temporary variable order

When the rewriter moves a temporary variable between scopes, it must
be sure to maintain the order, so that the rewritten order is the
same as it would have been without rewriting.

To expose the difference in behavior, this patch removes the superfluous
visitation of ForOfStatement::each() from AstExpressionVisitor, which
happened to be the only thing keeping all the temporaries in order
in mjsunit/harmony/regress/regress-crbug-578038.js. Without the proper
order, this test would fail under --stress-opt, because the ".for"
variable (behind the "each" proxy) would get two different positions
in the scope, one on first parse (with rewriting) and the other on
second parse (lazy parsing for optimization).

A follow-up patch will remove each() and iterable() from ForOfStatement
altogether, but I wanted to keep this patch small to highlight exactly
the bit of code needed to make the test pass when not visiting each().

BUG=v8:4791
LOG=n

Committed: https://crrev.com/2d090ee46ad88272653873eec8b1bd465ce37b50
Cr-Commit-Position: refs/heads/master@{#36150}
==========

[commit-bot: I haz the power, 2016-05-10 18:10:31]

Patchset 4 (id:??) landed as
https://crrev.com/2d090ee46ad88272653873eec8b1bd465ce37b50
Cr-Commit-Position: refs/heads/master@{#36150}