Velocity Reviews > a[i] = x[a[i]]++

# a[i] = x[a[i]]++

Joona I Palaste
Guest
Posts: n/a

 01-19-2005
Andrey Tarasevich <(E-Mail Removed)> scribbled the following:
> Joona I Palaste wrote:
>> Someone also mentioned something along the lines of a[a[i]]=i. This I
>> would consider defined behaviour, because what is being modified is
>> a[a[i]], and its old value is never used in the expression at all.

> In general case it is possible that a[i] == i, in which case the problem
> is rather obvious. This example is specifically targeted at this
> particular situation.

If a[i]==i, then the expression is equivalent to a[i]=i. However, this
is still very much defined behaviour, as the object being modified is
a[i], and its old value is not actually used for anything at all in the
above code. Note that even though a[i]==i that doesn't mean that
&(a[i])==&i, i.e. changing one won't affect the other.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"'It can be easily shown that' means 'I saw a proof of this once (which I didn't
understand) which I can no longer remember'."
- A maths teacher

Thomas Stegen
Guest
Posts: n/a

 01-19-2005
Joona I Palaste wrote:
> Andrey Tarasevich <(E-Mail Removed)> scribbled the following:
>
>>BRG wrote:
>>
>>>Does anyone here know whether the assignment:
>>>
>>> a[i] = x[ a[i] ]++;

> Yes it does, and no it is not. The old value of i is also being used as
> an index to the x array. Therefore this caused undefined behaviour.

a[i] = (*(x + a[i]))++;

Why is the above so very different from "i = i + 3;"?
Point is, why is the index operator so different from the addition
operator?

i is read to be used as an operand for the addition operator.
a[i] is read to be used as an operand for the index operator.
Then in both cases the result is written back.

If someone can explain to me how the addition operator can be used
to only determine the result to store while the index operator cannot
I would appreciate it.

An operator takes a set of operands and delivers a value. It seems to
me that in both cases the operands are read only to determine the
value of this operation.

The more I think about the surer I become that the above is defined.
The basic semantics for operators apply to all operators and I don't
see any differences in this case.

>>On the first sight, in this expression this requirement is met, i.e.
>>this expression is OK.

>
>
> Of course the expression "a[a[i]]=5" is OK.

Hint: a[i] == i

>
>>However, on the second sight, one can argue that this expression
>>violates that "only" requirement: in this case the old value of 'i' is
>>read not only to determine its new value, but also to determine, which
>>element of 'x[]' to increment. Personally, I don't think this is a valid
>>argument (considering what I think was the intent), but I could be wrong.

>
>
> If you were talking about "a[a[i]]=5" above, then this is plain
> nonsense.

If "this" refers to what you are saying you are correct.

--
Thomas.

BRG
Guest
Posts: n/a

 01-19-2005
Thomas Stegen wrote:
> Joona I Palaste wrote:
>
>> Andrey Tarasevich <(E-Mail Removed)> scribbled the following:
>>
>>> BRG wrote:
>>>
>>>> Does anyone here know whether the assignment:
>>>>
>>>> a[i] = x[ a[i] ]++;

>
>
>> Yes it does, and no it is not. The old value of i is also being used as
>> an index to the x array. Therefore this caused undefined behaviour.

>
> a[i] = (*(x + a[i]))++;
>
> Why is the above so very different from "i = i + 3;"?
> Point is, why is the index operator so different from the addition
> operator?

In my view its really the post-increment operation that needs to be
considered.

This is because, if the post-increment is the last thing done in
evaluating the right hand side (i.e it is done before a[i] on the left
hand side is updated), then x[ old a[i] ] will be post-incremented.

However, if the post-increment is the last thing done in evaluating the
whole expression (i.e it is done after a[i] on the left hand side is
updated) then x[ new a[i] ] will be post-incremented.

[snip]

Joona I Palaste
Guest
Posts: n/a

 01-19-2005
Thomas Stegen <(E-Mail Removed)> scribbled the following:
> Joona I Palaste wrote:
>> Of course the expression "a[a[i]]=5" is OK.

> Hint: a[i] == i

Hmm, now I think I see what people mean here. It's not i that matters
here, it's a[i]. If a[i]==i, then a[i] is both assigned a new value and
used for computing something other than its new value, i.e. the value of
a[a[i]].

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"We're women. We've got double standards to live up to."
- Ally McBeal

Andrey Tarasevich
Guest
Posts: n/a

 01-19-2005
Joona I Palaste wrote:
> Andrey Tarasevich <(E-Mail Removed)> scribbled the following:
>> Joona I Palaste wrote:
>>> Someone also mentioned something along the lines of a[a[i]]=i. This I
>>> would consider defined behaviour, because what is being modified is
>>> a[a[i]], and its old value is never used in the expression at all.

>
>> In general case it is possible that a[i] == i, in which case the problem
>> is rather obvious. This example is specifically targeted at this
>> particular situation.

>
> If a[i]==i, then the expression is equivalent to a[i]=i.

That's a pretty strong statement. It would be equivalent if one could be
sure that the original one does not produce UB.

> However, this
> is still very much defined behaviour, as the object being modified is
> a[i], and its old value is not actually used for anything at all in the
> above code.

Huh? What do you mean by "not used"? The expression 'a[a[i]] = i', or
simply 'a[a[i]] = 0' formally violates the requirements if the standard.
In general case it is possible that a[i] == i, which means that this
expression modifies the value of 'a[i]' object (outer 'a[]', assigns 0
to it) and at the same time reads its value (inner 'a[]'). It can't be
said that this act of reading is performed for the sole purpose of
determining the new value of the object, therefore it's UB.

> Note that even though a[i]==i that doesn't mean that
> &(a[i])==&i, i.e. changing one won't affect the other.

It looks like you were looking in wrong direction. The problem is not
with 'i'. The problem is with 'a[i]', which is modified and read at in
the same expression if a[i] == i. The problem still exists, once again, in

a[a[i]] = 0;

--
Best regards,
Andrey Tarasevich

Joona I Palaste
Guest
Posts: n/a

 01-19-2005
Andrey Tarasevich <(E-Mail Removed)> scribbled the following:
> Joona I Palaste wrote:
>> However, this
>> is still very much defined behaviour, as the object being modified is
>> a[i], and its old value is not actually used for anything at all in the
>> above code.

> Huh? What do you mean by "not used"? The expression 'a[a[i]] = i', or
> simply 'a[a[i]] = 0' formally violates the requirements if the standard.
> In general case it is possible that a[i] == i, which means that this
> expression modifies the value of 'a[i]' object (outer 'a[]', assigns 0
> to it) and at the same time reads its value (inner 'a[]'). It can't be
> said that this act of reading is performed for the sole purpose of
> determining the new value of the object, therefore it's UB.

Ignore what I said. I thought about it a bit more and found out you were
right.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"Bad things only happen to scoundrels."
- Moominmamma

Andrey Tarasevich
Guest
Posts: n/a

 01-19-2005
BRG wrote:
> ...
> This is because, if the post-increment is the last thing done in
> evaluating the right hand side (i.e it is done before a[i] on the left
> hand side is updated), then x[ old a[i] ] will be post-incremented.
>
> However, if the post-increment is the last thing done in evaluating the
> whole expression (i.e it is done after a[i] on the left hand side is
> updated) then x[ new a[i] ] will be post-incremented.
> ...

It is not really about when the post-increment is done. It is about when
the _argument_ for the post-increment is determined.

If the compiler decides to evaluate 'x[a[i]]' only once and use it as
argument for both assignment and post-increment, then the old value of
'a[i]' is always used. The sequence of steps can be illustrated by the
following code sketch

p = &x[a[i]] and then a[i] = (*p)++

But if the compiler decides to re-evaluate the argument of the
post-increment then, of course, the new value of 'a[i]' will be used

a[i] = x[a[i]] and then x[a[i]]++

--
Best regards,
Andrey Tarasevich

Christian Kandeler
Guest
Posts: n/a

 01-20-2005
Old Wolf wrote:

> the standard is quite clear that in (a = b = 3.1),
> a gets the value 3.1 even if b were an int.

Really? You should tell that to the gcc people, then:

\$ cat > test.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
double a;
int b;

a = b = 3.1;

printf("a = %f\nb = %d\n", a, b);

return EXIT_SUCCESS;
}
^D
\$ gcc -W -Wall -ansi -pedantic test.c
\$ ./a.out
a = 3.000000
b = 3

Christian

Richard Bos
Guest
Posts: n/a

 01-20-2005
Christian Kandeler <(E-Mail Removed)_invalid> wrote:

> Old Wolf wrote:
>
> > the standard is quite clear that in (a = b = 3.1),
> > a gets the value 3.1 even if b were an int.

>
> Really? You should tell that to the gcc people, then:

Or to the C Standard committee:

# The type of an assignment expression is the type of the left operand
# unless the left operand has qualified type, in which case it is the
# unqualified version of the type of the left operand.
(From 6.5.16#3. Identical wording in C89.)

Richard

Lawrence Kirby
Guest
Posts: n/a

 01-20-2005
On Wed, 19 Jan 2005 15:14:49 +0000, Richard Bos wrote:

> "aegis" <(E-Mail Removed)> wrote:
>
>> pete wrote:
>> > aegis wrote:
>> > >
>> > > > The prior value of foo[3]
>> > > > is used to determine the new value of foo[3],
>> > >
>> > > Did you mean to say is /not/ used?
>> >
>> > is

>>
>> Then this is wrong.
>> The prior value of foo[3] in "bar[foo[3]]++"
>> is not used to determine the new value of
>> foo[3]. It is used to determine the element
>> of bar, which bar is used to determine the
>> new value of foo[3]

>
> Yes. This means that, indirectly, foo[3] _is_ used to determine the new
> value of foo[3]. The big question here is, is this indirect action
> enough to save this from being undefined behaviour? To be honest, I
> don't know the answer myself, but I know enough to see that it is far
> from obvious.

If "indirect action" were not allowed then expressions like i = i + 1
would be undefined. I can see nothing in the standard that could be used
as a basis for a distinction between + and operators like = [] or ++ in
this respect. In particular there is no connection between the "only"
in 6.5p2 and side-effects if you accept that this is undefined
(void)((i = j) + i). Indeed I maintain that this sort of expression is the
real target of the word "only".

Lawrence