356454 - SWAP using a^=b^=a^=b, not working

Status: VERIFIED INVALID

(Core :: JavaScript Engine, defect)

Description

[Biju]

SWAP using a^=b^=a^=b, not working

  a=1;
  b=3;

  a^=b;
  b^=a;
  a^=b; 


will give a=3 and b=1

but 
  a=1;
  b=3;

  a^=b^=a^=b; 

do not give a=3 and b=1 as expected.



But this is not a problem in simple operations like

 a = 10;
 x = --a * --a * --a;

 works like 
 x = 9 * 8 * 7;

 and give result 504


steps:
1. open compile_issue.html
2. click test 0
3. click "test" button
4. repeat for others

Comment 1

[Biju]

Attachment: compile_issue.html

testcase

Comment 2

[Brendan Eich [:brendan]]

See ECMA-262 Edition 3, 11.13.2 Compound Assignment ( op= ) 

The production AssignmentExpression : LeftHandSideExpression @ = AssignmentExpression, where @ represents one of the operators indicated above, is evaluated as follows:

1. Evaluate LeftHandSideExpression. 
2. Call GetValue(Result(1)). 
3. Evaluate AssignmentExpression. 
4. Call GetValue(Result(3)). 
5. Apply operator @ to Result(2) and Result(4). 
6. Call PutValue(Result(1), Result(5)).7. Return Result(5). 

To apply this to the chained assignment expression

    a ^= b ^= a ^= b

we will need temporary variables to hold Result(2) and Result(4) at each application of the evaluation rule:

    t1 = a,
    t2 = b,
    t3 = a,
    t4 = b,
    a = t3 ^ t4,
    b = t2 ^ a,
    a = t1 ^ b

Now evaluate for a=1 and b=3:

    t1 = 1,
    t2 = 3,
    t3 = 1,
    t4 = 3,
    a = 2,
    b = 1,
    a = 0

Mutation is the spawn of the devil, no?  This is different from C or other C-like languages, which do not evaluate step 2 until after step 3:

    a ^= b ^= a ^= b === a = a ^ (b = b ^ (a = a ^ b))
                         a = a ^ (b = b ^ (a = 1 ^ 3))
                         a = a ^ (a = 2, b = 3 ^ 2)
                         b = 1, a = 2 ^ 1
                         b = 1, a = 3

Notice how you need three chained ^= expressions, not two, to see the problem in this example.  A shorter, non-swapping example:

    a ^= a ^= b

In C, that's evaluated for a=1 and b=3 as

    a = a ^ (a = 1 ^ 3) =>
    a = 2 ^ 2 =>
    a = 0.

In ECMAScript, we have to rewrite to:

    t1 = a,
    t2 = a,
    a = t2 ^ b
    a = t1 ^ a

and then evaluate for a=1, b=3 as

    t1 = 1,
    t2 = 1,
    a = 1 ^ 3, // 2
    a = 1 ^ 2  // 3

This divergence from C-like languages is not obviously a good thing, but it has been that way since ECMA-262 Edition 1.  I'll raise it with ECMA TG1.

/be

Comment 3

[Brendan Eich [:brendan]]

Safari, IE, and probably all other browsers containing ECMA-262 implementations agree with SpiderMonkey.  Marking INVALID.  If we change things for Edition 4 that will be done backward-compatibly, I think.

/be

Comment 4

[Biju]

Thanks Brendan for explanation 

Comment 5

[Brendan Eich [:brendan]]

One Ecma TG1 member wrote back:

I have two responses to this. Both are negative.

1. We should risk breakage only when there is an overwhelmingly greater good. I don't think this instance meets that test.

2. I don't want to encourage behavior such as a^=b^=a^=b. If swap is a feature that is important enough to change the definition of the language, then we should do it right, with a new operator like a :=: b or swap a,b.

-----
Another member wrote:

I forget -- do we not have already the swap capability via destructuring assignment?

-----
And we do, in JS2/ES4: [a, b] = [b, a] swaps any two values a and b, not only 32-bit integer values.

I suggested that an informative note be included in ES4's spec about how the order of evaluation differs from C here.

That reminds me: is C's order of evaluation for compound assignment operators actually specified? Much order of evaluation in C is purposely not specified, in order to allow implementations to optimize aggressively. Cc'ing some C gurus.

/be

Comment 6

[Jeff Walden [:Waldo]]

There's no sequence point in that expression, so not according to C99.

Comment 7

[Brian Crowder]

These references aren't the spec, of course, but the lists of operator precedence on Wikipedia, MSDN and in my K&R suggest that assignment and compound assignment are always right-to-left evaluated.  I'd be surprised if that's not specified explicitly, and it does seem to offer a definitive, consistent order of evaluation for this statement.

Comment 8

[Jeff Walden [:Waldo]]

  C99 6.5.16 paragraph 4:
  The order of evaluation of the operands is unspecified. If an attempt is
  made to modify the result of an assignment operator or to access it after
  the next sequence point, the behavior is undefined. 


...so no right-to-left evaluation order.  As for no sequence point, either the informative Annex C is wrong and omits a sequence point or Annex J.2 (third page of it, topmost bullet in my copy, page 493) says it's undefined, as |a| is modified twice:

  Between two sequence points, an object is modified more than once, or is
  modified and the prior value is read other than to determine the value to
  be stored (6.5).

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Re comment 7 (I wrote this before Jeff's reply; he knows the details a lot better than I do):

It's not a question about operator precedence/grouping.  It's a question of whether the standard defines that the leftmost a^=... starts with the a resulting from the rightmost a^=... (rather than the a as it was before the statement).  This involves the same rules as those that say evaluation of a + b is not required to consider side effects from the evaluation of a when evaluating b, or vice versa.  (Although I could imagine there being special rules for op= operators in addition to the rules about sequence points, but comment 8 seems to say that's not the case.)

Comment 10

[Biju]

(In reply to comment #5)
> One Ecma TG1 member wrote back:

After reading members comment, I they have not under stood the issue.
So when you get time I want you to explain the issue to them again.

Issue is not about SWAP
a^=b^=a^=b is a 'C language' puzzle
generally to swap I use |temp=a;a=b;b=temp;| i believe other also do same. 


I can understand if in spec there was some thing like 
(In reply to comment #8)
>   C99 6.5.16 paragraph 4:

But all the C books teaches right-to-left evaluation of assignment operator.
And all the C compilers I have used do that too.
So there is a well tested algorithm available for our use.

I dont think fixing this in spec will break any sites.
Said that, it is OK for me if vendors take time to fix this in the code which need testing.

Comment 11

[Brendan Eich [:brendan]]

Biju: but C does not require that right-to-left order -- see above comments from dbaron and jwalden. So your code is not portable.

ES1-3 do specify order of evaluation, for portability (interoperation). But they do not specify the order you want (seemingly motivated by the xor puzzle, but ok, maybe there are other examples of why that order is useful -- but not from C, since C does not specify any order). The very first response from a TG1 member was "no or too little gain for risk of breaking existing content." That still seems overriding.

/be

Comment 12

[Biju]

(In reply to comment #11)
> Biju: but C does not require that right-to-left order -- see above comments
> from dbaron and jwalden. So your code is not portable.

em... portable in all compilers I tried.

from dbaron and jwalden comments I understand in C per the spec the effect can be unpredictable
that is OK to me, because a vendor can fix his code to get right-to-left order

But "ES1-3 do specify order of evaluation, for portability (interoperation)"
and from Comment #2 I see vendor is forced/advised/encouraged to do 
against the rule specified in K&R and other C books, as well as many Java, JS language books

That is why I mentioned the spec should be modified.
(also a website breaking if a vendor implemented it 
 will be rare, may even none, so no risk)

So I still believe correcting spec is the right thing.

As we have many important other Bugs to be fixed here.
And fixing this right-to-left order issue 
will have only very little practical benefit,
We can kill this argument/discussion here.

Brendan and all thanks very much for trying...

Comment 13

[Jason Orendorff [:jorendorff]]

(In reply to comment #12)

Biju, I'd be astonished if K&R really said what you say it says.  Can you give the page number?

> em... portable in all compilers I tried.

Well, the particular versions of those compilers you tried--given the particular program you tried and the command-line options you used.  The second week after you start depending on that, though, GCC will break you.  (If the C Standard doesn't impress you, maybe Murphy's Law will...)

The Standard is authoritative here.  The expression a^=b^=a^=b has undefined behavior in C, which is the Standard's way of saying "you lose".  I'm guessing it's been like that at least since ANSI C.