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

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

BRG
Guest
Posts: n/a

 01-19-2005
Andrey Tarasevich wrote:

> BRG wrote:
>
>
>>Does anyone here know whether the assignment:
>>
>> a[i] = x[ a[i] ]++;
>>
>>is legal in C

>
>
> I think this code can be simplified to
>
> i = x[i]++;
>
> without loss of generality.

As far as I can see, yes.

> The question boils down to checking whether the old value of 'i' is read
> only to determine the new value of 'i'. This requirement appears to be
> formulated in the standard in rather informal fashion (I have my doubts
> about the exact meaning of that "only"), but the intent was, if I
> remember correctly, to require the flow of information inside the
> expression to force the old value to be read _before_ the new value is
> stored. There's a defect report that deals with a similar issue of
> whether the
>
> a[a[i]] = 5;
>
> produces undefined behavior. (Unfortunately, I don't remember the defect
> number.)
>
> On the first sight, in this expression this requirement is met, i.e.
> this expression is OK.
>
> 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.
>
>>and, if so, what array element in x[] is post incremented?

>
> The one specified by the old value of 'a[i]'.

This is where I think the action becomes undefined. There are three
steps in evaluation and two separate stores:

(1) compute a[i] and then x[ a[i] ]
(2) store the result in a[i]
(3) access x[ a[i] ], add 1 to it and store in x[ a[i] ]

I am not convinced that we can rely on the order of (2) and (3) and the
result does depend on whether the order is (2) and then (3) or (3) and
then (2).

And then a[i] - which has been written to - is used to determine _which_
element of x[] is postincremented -and this appears to violate the
principal that items that are written to during evaluation must only be
used to compute the _values_ written and not the addresses at which
writes take place.

So in my view it is not the write of a[i] that violates this clause but
the write that is a part of the post increment operation.

>>That is, does the old or the new value of a[i] determine the index in
>>x[] of the post incremented array element.

>
> Should be the old one.

On Microsft VC++ it is the new value of a[i] that is used.

>>I rather suspect the result is undefined - but am I right?

>
> I'd say that I rather suspect that the result is defined.

I remain unconvinced of this and still lean towards 'undefined' (a)
because of the problem with the order of write operations, and (b)
because a written to value is being used to determine the address at
which the post increment write operation takes place.

aegis
Guest
Posts: n/a

 01-19-2005

BRG wrote:
> Andrey Tarasevich wrote:
>
> > BRG wrote:
> >
> >
> >>Does anyone here know whether the assignment:
> >>
> >> a[i] = x[ a[i] ]++;
> >>
> >>is legal in C

> >
> >
> > I think this code can be simplified to
> >
> > i = x[i]++;
> >
> > without loss of generality.

>
> As far as I can see, yes.
>
> > The question boils down to checking whether the old value of 'i' is

> > only to determine the new value of 'i'. This requirement appears to

be
> > formulated in the standard in rather informal fashion (I have my

doubts
> > about the exact meaning of that "only"), but the intent was, if I
> > remember correctly, to require the flow of information inside the
> > expression to force the old value to be read _before_ the new value

is
> > stored. There's a defect report that deals with a similar issue of
> > whether the
> >
> > a[a[i]] = 5;
> >
> > produces undefined behavior. (Unfortunately, I don't remember the

defect
> > number.)
> >
> > On the first sight, in this expression this requirement is met,

i.e.
> > this expression is OK.
> >
> > 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.
> >
> >>and, if so, what array element in x[] is post incremented?

> >
> > The one specified by the old value of 'a[i]'.

>
> This is where I think the action becomes undefined. There are three
> steps in evaluation and two separate stores:
>
> (1) compute a[i] and then x[ a[i] ]
> (2) store the result in a[i]
> (3) access x[ a[i] ], add 1 to it and store in x[ a[i] ]
>

Your idea is more closely related to assembler than
what is described in the C standard.

The standard does not dictate that this expression
would require two separate stores. Stop thinking this way.

--
aegis

BRG
Guest
Posts: n/a

 01-19-2005
aegis wrote:

[snip]
>>>>This is where I think the action becomes undefined. There are three
>>>>steps in evaluation and two separate stores:
>>>>
>>>>(1) compute a[i] and then x[ a[i] ]
>>>>(2) store the result in a[i]
>>>>(3) access x[ a[i] ], add 1 to it and store in x[ a[i] ]
>>>>
>>>
>>>Your idea is more closely related to assembler than
>>>what is described in the C standard.
>>>
>>>The standard does not dictate that this expression
>>>would require two separate stores. Stop thinking this way.

>>
>>I'll stop thinking this way when you show, in the normal case where x[]
>>and a[] don't overlap, how the expression can be fully evaluated with
>>less than two store operations.

>
> I don't have to because the standard does not concern itself
> with such issues.

To be of any use here the standard has to be concerned with such issues.

The standard describes
> things in such a way that any details on how an implementation
> goes about making writes or stores etc is abstracted away.

But it cannot avoid the fact that, except in unusual cases, the statment
in question updates two objects, a[i] and x[ a[i] ]. Since the result
is different depending on the order in which these updates occur the
standard either has to specify this order or allow any order. And in the
latter case the result will be undefined.

> If you are looking for an authoritative answer to your
> original question, you will more than likely get it in comp.std.c
> not comp.lang.c

I agree.

pete
Guest
Posts: n/a

 01-19-2005
aegis wrote:
>
> pete wrote:

> > But we can increment the right operand of the assignment,
> > after the assignment, by which time foo[3] has a value of 4.

> and? how does this affect anything?

It means that the two side effects invoked by the code are
foo[3] = 4;
bar[4]++;

--
pete

Richard Bos
Guest
Posts: n/a

 01-19-2005
"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.

Richard

Joona I Palaste
Guest
Posts: n/a

 01-19-2005
BRG <(E-Mail Removed)> scribbled the following:
> Does anyone here know whether the assignment:

> a[i] = x[ a[i] ]++;

> is legal in C and, if so, what array element in x[] is post incremented?

> That is, does the old or the new value of a[i] determine the index in
> x[] of the post incremented array element.

> I rather suspect the result is undefined - but am I right?

I would first intuitively consider it defined, but when I look at it
more closely, it becomes obvious that the old value of a[i] is *NOT*
only used to determine the new value, it is also being used to index
to the x array. Therefore the behaviour is undefined.
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. And
indexing to an array with an element from the same array is perfectly
legal, as long as the array's element type is an integer type.
However, p = p->next = q looks like undefined behaviour, precisely
because the old value of p is also used to point to a structure, whose
"next" field is being modified.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"He said: 'I'm not Elvis'. Who else but Elvis could have said that?"
- ALF

Joona I Palaste
Guest
Posts: n/a

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

> I think this code can be simplified to

> i = x[i]++;

> without loss of generality.

> The question boils down to checking whether the old value of 'i' is read
> only to determine the new value of '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.

> This requirement appears to be
> formulated in the standard in rather informal fashion (I have my doubts
> about the exact meaning of that "only"), but the intent was, if I
> remember correctly, to require the flow of information inside the
> expression to force the old value to be read _before_ the new value is
> stored. There's a defect report that deals with a similar issue of
> whether the

> a[a[i]] = 5;

> produces undefined behavior. (Unfortunately, I don't remember the defect
> number.)

> 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. But were you talking about

> 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. However, if you were talking about "i=x[i]++", as I think you
were, you are right.

>> and, if so, what array element in x[] is post incremented?

> The one specified by the old value of 'a[i]'.

No, not necessarily.

>> That is, does the old or the new value of a[i] determine the index in
>> x[] of the post incremented array element.

> Should be the old one.

Again, not necessarily.

>> I rather suspect the result is undefined - but am I right?

> I'd say that I rather suspect that the result is defined.

I'd say I rather suspect the exact opposite. There is no guarantee which
order C executes the modifications in, or indeed whether it executes
them at all. This is due to the lack of an intervening sequence point.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"'So called' means: 'There is a long explanation for this, but I have no
time to explain it here.'"
- JIPsoft

BRG
Guest
Posts: n/a

 01-19-2005
Joona I Palaste wrote:
> BRG <(E-Mail Removed)> scribbled the following:
>
>>Does anyone here know whether the assignment:

>
>
>> a[i] = x[ a[i] ]++;

>
>
>>is legal in C and, if so, what array element in x[] is post incremented?

>
>
>>That is, does the old or the new value of a[i] determine the index in
>>x[] of the post incremented array element.

>
>
>>I rather suspect the result is undefined - but am I right?

>
>
> I would first intuitively consider it defined, but when I look at it
> more closely, it becomes obvious that the old value of a[i] is *NOT*
> only used to determine the new value, it is also being used to index
> to the x array. Therefore the behaviour is undefined.

That's my view too. I also suspect that the two possible orders of the
two update operations - a[i] and x[a[i]] - would make it undefined as well.

Thanks to you and others for taking the time to comment on this.

[snip]

Andrey Tarasevich
Guest
Posts: n/a

 01-19-2005
Joona I Palaste wrote:
>>> Does anyone here know whether the assignment:
>>>
>>> a[i] = x[ a[i] ]++;
>>>
>>> is legal in C

>
>> I think this code can be simplified to

>
>> i = x[i]++;

>
>> without loss of generality.

>
>> The question boils down to checking whether the old value of 'i' is read
>> only to determine the new value of '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.

I don't see how this alone can cause undefined behavior. The same can be

i = x[i];

but there's no undefined behavior in this case. Using 'i' as an index
for 'x' array is a part of that "reading of 'i' only to determine the
new value of 'i'". Everything is fine here.

The problem appears once you add the increment. With the increment, the
only thing that's not exactly clear to me is whether this attempt to use
the same subexpression 'x[i]' (that evaluates lvalue 'x[i]' for 'i ='
assignment) as an argument for some other operator (post-increment in
this case) violates that "only" requirement from the standard.

Or, at lower level, whether implementations are required to calculate
lvalue 'x[i]' only once (and use it as an argument in both assignment
and increment) or allowed to do it twice (first time - for assignment,
second time - for increment). In the first case one would expect to see
"consistent" behavior.

>> This requirement appears to be
>> formulated in the standard in rather informal fashion (I have my doubts
>> about the exact meaning of that "only"), but the intent was, if I
>> remember correctly, to require the flow of information inside the
>> expression to force the old value to be read _before_ the new value is
>> stored. There's a defect report that deals with a similar issue of
>> whether the

>
>> a[a[i]] = 5;

>
>> produces undefined behavior. (Unfortunately, I don't remember the defect
>> number.)

>
>> 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. But were you talking about
> the earlier expression "i=x[i]++" instead?

Yes. I was talking about 'i=x[i]++' I added 'a[a[i]] = 5' later and
missed the fact that it makes the text below rather confusing.

'a[a[i]]=5' is not immediately "OK", BTW. It can be argued that in
situation when a[i] == i the inner reading of the value of 'a[i]' is not
done for the sole purpose of forming its new value and therefore the
whole expression causes undefined behavior from the formal point of
view. However, once you consider the flow of info inside this
expression, it is obvious that the value of 'a[i]' cannot be modified
before the inner 'a[i]' is evaluated. Which rises the question whether
such expressions were outlawed intentionally.

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich
Guest
Posts: n/a

 01-19-2005
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.

--
Best regards,
Andrey Tarasevich