Thursday, June 16, 2005

Is it a bug in the C# compiler or what?

I don't know whether the up-coming expression evaluation in the C# had revealed a bug inside the C# compiler or not, any way let's discuss it:

Imagine we've a function like this in C#:

void Func(ref int a, ref int b)
{
a ^= b ^= a ^= b;
}

Usually if we used the right to left compiler expression evaluation, we'll walk in this way, at first we know our variables' values are changing in each step, so we can easily determine that the expression must be renamed to be:

a2 ^= b1 ^= a1 ^= b0;

And when we make it as successive steps, it'll be:

a1 = a0 ^ b0;
b1 = b0 ^ a1;
a2 = a1 ^ b1;

In this case:
a-final = a1^b1 = (a0 ^ b0) ^ (b0 ^ a1) = (a0 ^ b0) ^ (b0 ^ (a0 ^ b0))
And after replacing all a0 with a and b0 with b, it'll be:

a-final = (a ^ b) ^ (b ^ (a ^ b)) = (a ^ b) ^ a = b.
The same steps done in b-final:

b-final = b0 ^ a1 = b0 ^ (a0 ^ b0) = b ^ a ^ b = a.
So we can easily determine that this function will do a simple swapping between the two variables, then where's the bug?!!

The bug will be raised when we try to evaluate the expression from right to left without renaming the variables, in this case:

a ^= b ^= a ^= b;

Will be evaluated as Three steps in order: a = a ^ b;
b = b ^ a;
a = a ^ b;

so, a-final = a ^ (b ^ (a ^ b)), and here's the bug, they hadn't put in mind that the left most a in the a-final equation is not equal to the original a, it's equal to a ^ b, so they had omit extra b which will lead the expression of a-final to be evaluated as: a-final = a ^ a = zero, so instead of being a swapping function, this function will just copy the value of a in b and make a = zero.

I don't know if this is a real bug, or they intended to evaluate the expression in C# in this way (knowing that C++ compiler is evaluating it in the true order), really I don't have a clue, but I'll try to know the truth any way :)

10 comments:

Anonymous said...

The current behavior in the C# compiler is correct.

The mistake in you logic is that you assume that, because the expression is evaluated right-to-left for precedence, the variable locations are also taken from right to left.

The runtime evaluation of the expression is (correctly) from left to right.

[I am adapting from the C# language specification here]

An operation of the form x op= y
is evaluated as x = x op y, except that x is evaluated only once.

The run-time processing of a simple assignment of the form x = y consists of the following steps:
o x is evaluated to produce the variable.
o y is evaluated
o The value resulting from the evaluation of y is stored into the location given by the evaluation of x.


So, ...
a ^= b ^= a ^= b;

can be re-written as
a ^= b ^= (a = a ^ b);
a ^= (b = b ^ (a = a ^ b));
a = a ^ (b = b ^ (a = a ^ b));

Applying the runtime processing rules above,
The lhs a is evaluated to produce a variable, which is used for the first two occurences of a ("a = a ....."). [The most important thing to remember is that this evaluation happens before everything else to the right.]
Then y, or a ^ (b = b ^ (a = a ^ b)), is evaluated
And finally the result stored in the location given by the evaluation of a.

In order to evaluate the 'y' part of the assignment above,
b = b ^ (a = a ^ b) needs to be evaluated similarly.
b is evaluated to produce a variable, and b ^ (a = a ^ b) is evaluated and the result stored in the location given by the evaluation of b.

a = a ^ b is evaluated similarly.
a is evaluated to produce a variable, and a ^ b is evaluated and the result stored.


Hope this helps

Christian said...

Meshref, perhaps you should credit the original source who brought that up :)
It was my friend Marco in a comment on my blog

Thanks daigo for the explanation :)
Looking forward to meeting you some time.

Mohamed Moshrif said...

What do you mean by Marco?

Any way sorry for not including the source :D:D
But it was just a question in the cyber space :D

Christian said...

Never mind :)

Marco is the guy who posted the 1st comment anonymously.

In the future and for your own good put in mind that cyber space does not mean we needn't credit sources when appropriate :) It's the moral thing to do. Plus, in extreme cases you could end up being sued if you completely disregard the concept :)

Mohamed Moshrif said...

I hadn't meant all these :D:D
I had just seen the question, then tried it on paper, and since I see that C# is faster in compilation i tried it on C# first to get sure from my result, all these before I see any comments :D:D
That's all for sure :)

Anonymous said...

Hey gusy how about this one

int x=3;
x+=x++ + ++x;

this should evaluate the x to 13 in all C++ & java compilers can guss how it will be in C# ?? 11

with two diff.

can u explain why C# evaluates it like this way.

Mohamed Moshrif said...

I hadn't tried it yet, but when i get some free time i'll try to figure out the problem

Mohamed Moshrif said...

Ohh, i had locked on it seconds after posting my comments :)
this is a true behavior, since C# is working from Left to Right, therefor it'll be evaluated like this:
x+=x++ + ++x;

first x++ will be evaluated, so we'll have:

x+= 3 + ++4

which will be evaluated to:

x+= 3 + 5

and finally x will be:

3 + 8 = 11

it's evaluated to 13 in MS VC++ because VC++ is working from right to left, that's all

Anonymous said...

it's about operators priority in C++ the += operator get less priority than ++ but in C# the += gets the higher one

Mohamed Moshrif said...

It's not the matter of periority only here, but it's just the evaluation itself, C++ is working from Righ to Left in MS VC++, but C# is working from Left to Right.