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

B

BRG

Does anyone here know whether the assignment:

a = x[ a ]++;

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 determine the index in
x[] of the post incremented array element.

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

Brian Gladman
 
C

Chris Torek

Does anyone here know whether the assignment:

a = x[ a ]++;

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 determine the index in
x[] of the post incremented array element.

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


I myself believe that this is isomorphic to the:

p = p->next = q;

problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)
 
P

pete

Chris said:
Does anyone here know whether the assignment:

a = x[ a ]++;

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 determine the index in
x[] of the post incremented array element.

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


I myself believe that this is isomorphic to the:

p = p->next = q;

problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)


The a = x[a]++ problem,
is a real problem which came from a program
that BRG debugged on comp.programming.

http://groups-beta.google.com/group/comp.programming/msg/fad5a77876d4d991

The actual line of code was
for (i=0;i<len;i++) cmp_index = cum[cmp_index]++;
which he changed to
for (i=0;i<len;i++) {
j = cmp_index;
cmp_index = cum[j]++;
}

The sort function wouldn't work on my machine with the
original line of code, but it does with the fix.
 
B

Ben Pfaff

pete said:
Chris said:
I myself believe that this is isomorphic to the:

p = p->next = q;

problem, [...]

The a = x[a]++ problem,
is a real problem which came from a program
that BRG debugged on comp.programming.


The p = p->next = q problem is also a real problem that came from
a program I was writing when I posted a question about it here
years ago.
 
C

Christopher Benson-Manica

Chris Torek said:
problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)

FWIW,

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
int i=3;
int foo[10];
int bar[10];
bar[5]=4;
foo=5;
foo=bar[ foo ]++;
printf( "foo[3]=%d, bar[5]=%d\n", foo, bar[5] );
return( EXIT_SUCCESS );
}

prints

foo[3]=4, bar[5]=5

as I at least would expect it to. The expression is (hopefully)
equivalent to

foo[3]=bar[ foo[3] ]++;

foo[3] is 5, and bar[5] is 4. Therefore foo[3] is assigned the value
4, and then bar[5] is postincremented, yielding 5. I can't see any
other reasonable order of evaluation for this statement, so I would
(very humbly) submit that it seems to have consistent behavior. I
agree with your statement that the construct is confusing at any rate
and would be unkind to future maintainers (especially if it didn't
work!) :)
 
P

pete

Christopher said:
Chris Torek said:
problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)

FWIW,

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
int i=3;
int foo[10];
int bar[10];
bar[5]=4;
foo=5;
foo=bar[ foo ]++;
printf( "foo[3]=%d, bar[5]=%d\n", foo, bar[5] );
return( EXIT_SUCCESS );
}

prints

foo[3]=4, bar[5]=5

as I at least would expect it to. The expression is (hopefully)
equivalent to

foo[3]=bar[ foo[3] ]++;

foo[3] is 5, and bar[5] is 4. Therefore foo[3] is assigned the value
4, and then bar[5] is postincremented, yielding 5. I can't see any
other reasonable order of evaluation for this statement, so I would
(very humbly) submit that it seems to have consistent behavior. I
agree with your statement that the construct is confusing at any rate
and would be unkind to future maintainers (especially if it didn't
work!) :)


/* BEGIN new.c */

#include <stdio.h>

int main( void )
{
int i;
int foo[10] = {0};
int bar[10] = {0};

bar[5] = 4;
foo[3] = 5;
foo[3] = bar[foo[3]]++;
printf("foo[3]=%d, bar[5]=%d\n\n", foo[3], bar[5]);

for (i = 0; i != 10; ++i) {
printf("foo[%d]=%d, bar[%d]=%d\n", i, foo, i, bar);
}
return 0;
}

/* END new.c */

foo[3]=4, bar[5]=4

foo[0]=0, bar[0]=0
foo[1]=0, bar[1]=0
foo[2]=0, bar[2]=0
foo[3]=4, bar[3]=0
foo[4]=0, bar[4]=1
foo[5]=0, bar[5]=4
foo[6]=0, bar[6]=0
foo[7]=0, bar[7]=0
foo[8]=0, bar[8]=0
foo[9]=0, bar[9]=0
 
A

aegis

pete said:
Christopher said:
Chris Torek said:
problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)

FWIW,

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
int i=3;
int foo[10];
int bar[10];
bar[5]=4;
foo=5;
foo=bar[ foo ]++;
printf( "foo[3]=%d, bar[5]=%d\n", foo, bar[5] );
return( EXIT_SUCCESS );
}

prints

foo[3]=4, bar[5]=5

as I at least would expect it to. The expression is (hopefully)
equivalent to

foo[3]=bar[ foo[3] ]++;

foo[3] is 5, and bar[5] is 4. Therefore foo[3] is assigned the value
4, and then bar[5] is postincremented, yielding 5. I can't see any
other reasonable order of evaluation for this statement, so I would
(very humbly) submit that it seems to have consistent behavior. I
agree with your statement that the construct is confusing at any rate
and would be unkind to future maintainers (especially if it didn't
work!) :)


/* BEGIN new.c */

#include <stdio.h>

int main( void )
{
int i;
int foo[10] = {0};
int bar[10] = {0};

bar[5] = 4;
foo[3] = 5;
foo[3] = bar[foo[3]]++;
printf("foo[3]=%d, bar[5]=%d\n\n", foo[3], bar[5]);

for (i = 0; i != 10; ++i) {
printf("foo[%d]=%d, bar[%d]=%d\n", i, foo, i, bar);
}
return 0;
}

/* END new.c */

foo[3]=4, bar[5]=4

foo[0]=0, bar[0]=0
foo[1]=0, bar[1]=0
foo[2]=0, bar[2]=0
foo[3]=4, bar[3]=0
foo[4]=0, bar[4]=1
foo[5]=0, bar[5]=4
foo[6]=0, bar[6]=0
foo[7]=0, bar[7]=0
foo[8]=0, bar[8]=0
foo[9]=0, bar[9]=0


have a chapter and verse as to why the above expression
results in undefined behavior?

The only problem I see is if x[] is an alias of a[]

i.e.
void foo(int a[], int x[])
{
/* insert code */
}

int main(void)
{
int a[10];

foo(a, a);

return 0;
}

before we begin with this discussion, let's state
5.1.2.3#1

"The semantic descriptions in this International Standard
describe the behavior of an abstract machine in which
issues of optimization are irrelevant."
 
P

pete

aegis said:
Christopher said:
Chris Torek <[email protected]> spoke thus:

problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :)

FWIW,

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
int i=3;
int foo[10];
int bar[10];
bar[5]=4;
foo=5;
foo=bar[ foo ]++;
printf( "foo[3]=%d, bar[5]=%d\n", foo, bar[5] );
return( EXIT_SUCCESS );
}

prints

foo[3]=4, bar[5]=5

as I at least would expect it to. The expression is (hopefully)
equivalent to

foo[3]=bar[ foo[3] ]++;

foo[3] is 5, and bar[5] is 4.
Therefore foo[3] is assigned the value
4, and then bar[5] is postincremented, yielding 5.
I can't see any
other reasonable order of evaluation for this statement,
so I would
(very humbly) submit that it seems to have consistent behavior. I
agree with your statement that the construct is
confusing at any rate
and would be unkind to future maintainers (especially if it didn't
work!) :)


/* BEGIN new.c */

#include <stdio.h>

int main( void )
{
int i;
int foo[10] = {0};
int bar[10] = {0};

bar[5] = 4;
foo[3] = 5;
foo[3] = bar[foo[3]]++;
printf("foo[3]=%d, bar[5]=%d\n\n", foo[3], bar[5]);

for (i = 0; i != 10; ++i) {
printf("foo[%d]=%d, bar[%d]=%d\n", i, foo, i, bar);
}
return 0;
}

/* END new.c */

foo[3]=4, bar[5]=4

foo[0]=0, bar[0]=0
foo[1]=0, bar[1]=0
foo[2]=0, bar[2]=0
foo[3]=4, bar[3]=0
foo[4]=0, bar[4]=1
foo[5]=0, bar[5]=4
foo[6]=0, bar[6]=0
foo[7]=0, bar[7]=0
foo[8]=0, bar[8]=0
foo[9]=0, bar[9]=0


have a chapter and verse as to why the above expression
results in undefined behavior?


The prior value of foo[3]
is used to determine the new value of foo[3],
so the prior value of foo[3],
can't be used to also determine which bar[] element is incremented.


N869
6.5 Expressions

[#2] Between the previous and next sequence point an object
shall have its stored value modified at most once by the
evaluation of an expression. Furthermore, the prior value
shall be accessed only to determine the value to be
stored.

Jun Woong and Douglas A. Gwyn seem to be of one mind on this issue
in the
What language to address "tricky assignment statement"
thread, in
 
A

aegis

The prior value of foo[3]
is used to determine the new value of foo[3],

Did you mean to say is /not/ used?
so the prior value of foo[3],
can't be used to also determine which bar[] element is incremented.


N869
6.5 Expressions

[#2] Between the previous and next sequence point an object
shall have its stored value modified at most once by the
evaluation of an expression. Furthermore, the prior value
shall be accessed only to determine the value to be
stored.

So you are essentially saying that the use of "foo" on the right
hand side of the assignment operator is not allowed because
we modify the value of that same object on the left hand side of the
assignment operator. In which case, foo[3] is modified before
we use it to determine the value of bar[] to modify foo[3].

This certainly sounds absurd to me. And I don't see how 6.5#2
fits in here. foo[3] is exactly modified once. But before it
is modified me must first evaluate the right hand side of the
assignment expression, yes?

According to 6.5.16.1#2 we have a well defined ordering here.
and 6.5.16.1#5 only reaffirms it.
 
P

pete

aegis said:
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
so the prior value of foo[3],
can't be used to also determine which bar[] element is incremented.


N869
6.5 Expressions

[#2] Between the previous and next sequence point an object
shall have its stored value modified at most once by the
evaluation of an expression. Furthermore, the prior value
shall be accessed only to determine the value to be
stored.

So you are essentially saying that the use of "foo" on the right
hand side of the assignment operator is not allowed because
we modify the value of that same object on the left hand side of the
assignment operator.
In which case, foo[3] is modified before
we use it to determine the value of bar[] to modify foo[3].

No.

The "prior value" of foo[3] is 5.

I'm saying that 5, is used to determine which
element of bar is assigned to foo[3], (bar[5])
and that 5 can't also be used to determine
which element of bar is incremented.

"the prior value shall be accessed
^^^^^ ^^^^^
only to determine the value to be stored."
foo[3] is exactly modified once. But before it
is modified me must first evaluate the right hand side of the
assignment expression, yes?

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

BRG

Andrey said:
BRG wrote:

Does anyone here know whether the assignment:

a = x[ a ]++;

is legal in C



I think this code can be simplified to

i = x++;

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] = 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'.


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

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

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 - 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 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 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 that is used.
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.

Brian Gladman
 
A

aegis

BRG said:
Andrey said:
BRG wrote:

Does anyone here know whether the assignment:

a = x[ a ]++;

is legal in C



I think this code can be simplified to

i = x++;

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] = 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'.


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

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


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.
 
B

BRG

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 and then x[ a ]
(2) store the result in a
(3) access x[ a ], add 1 to it and store in x[ a ]


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 and x[ a ]. 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.

Brian Gladman
 
P

pete

aegis said:
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]++;
 
R

Richard Bos

aegis said:
pete said:
aegis said:
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
 
J

Joona I Palaste

BRG said:
Does anyone here know whether the assignment:
a = x[ a ]++;

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 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 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. This I
would consider defined behaviour, because what is being modified is
a[a], 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.
 
J

Joona I Palaste

Andrey Tarasevich said:
BRG said:
Does anyone here know whether the assignment:

a = x[ a ]++;

is legal in C

I think this code can be simplified to

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] = 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]=5" is OK. But were you talking about
the earlier expression "i=x++" instead?
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]=5" above, then this is plain
nonsense. However, if you were talking about "i=x++", 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'.


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

Should be the old one.

Again, not necessarily.
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 ([email protected]) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"'So called' means: 'There is a long explanation for this, but I have no
time to explain it here.'"
- JIPsoft
 
B

BRG

Joona said:
BRG said:
Does anyone here know whether the assignment:

a = x[ a ]++;

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 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 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 and x[a] - would make it undefined as well.

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

[snip]

Brian Gladman
 
A

Andrey Tarasevich

Joona said:
Does anyone here know whether the assignment:

a = x[ a ]++;

is legal in C

I think this code can be simplified to

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
said about the following expression

i = x;

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' (that evaluates lvalue 'x' 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' 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] = 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]=5" is OK. But were you talking about
the earlier expression "i=x++" instead?


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

'a[a]=5' is not immediately "OK", BTW. It can be argued that in
situation when a == i the inner reading of the value of 'a' 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' cannot be modified
before the inner 'a' is evaluated. Which rises the question whether
such expressions were outlawed intentionally.
 
A

Andrey Tarasevich

Joona said:
Someone also mentioned something along the lines of a[a]=i. This I
would consider defined behaviour, because what is being modified is
a[a], and its old value is never used in the expression at all.


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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top