i = v[i++] results in undefined behavior. Can't understand why.

[James Kanze]

On 09/26/2010 08:09 PM, Johannes Schaub (litb) wrote:

[...]

Any expression has a unique syntax tree. In order to evaluate
one node in the tree we need to evaluate all of its children
first.

What does it mean to "evaluate" a child? The standard doesn't
say anything like this. What we do need is to "value compute"
the child nodes. There's no requirement for more.

The order by which we evaluate the subexpressions is
unspecified however. A side-effect like i++ is not visible at
the place where we evaluate the expression i++ but at the next
time we are confronted with the leaf i in the syntax tree.

When the side effect is visible depends on a lot of things.
Within a single thread, it is ordered with respect to the next
sequence point, and no more. And even then, we have to be
careful what we are talking about---the compiler may never write
the results of the incrementation, as long as the observable
behavior is the same as if it had (or there are some interthread
sequencing primitives which require it).

If the next position where we meet i in the syntax tree is
uniquely specified by the structure of the tree, we have no
ambiguity problem, otherwise we do.

There's no ambiguity. You're just confusing the guarantees
concerning the results of an expression with the order side
effects occur; the two are largely unrelated.

Let expr be an expression, then by the grammar of c++ the
expression (expr) is an expression too. There expression trees
must be different, otherwise expr and (expr) would be the same
expression. The expression tree is a subtree of (expr)

Not in any of the compilers I've seen.

 

[Johannes Schaub (litb)]

Where do you get that from? The sentences you quote only speak
of sequencing the *value* computation. Nothing about side
effects.

It says "The value computation of the ++ expression is sequenced before the
modification of the operand object". The latter is the side effect. So you
have the modification of "++i" before value computation of that expression,
and that value computation before value computation of the "<lval>++"
expression (because value computation of operands of an operator is
sequenced before value computation of their result), which in turn is
sequenced before modification of "<lval>".

So since "sequenced before" is a transitive relation, both side effects are
sequenced with respect to each other and with respect to value computations.

 

[James Kanze]

It says "The value computation of the ++ expression is
sequenced before the modification of the operand object". The
latter is the side effect. So you have the modification of
"++i" before value computation of that expression,

The passage you quote says just the opposite. And logically, it
couldn't be any other way: you can't have the side effect (the
modification of i) before having calculated its value.

and that value computation before value computation of the
"<lval>++" expression (because value computation of operands
of an operator is sequenced before value computation of their
result), which in turn is sequenced before modification of
"<lval>".

So since "sequenced before" is a transitive relation, both
side effects are sequenced with respect to each other and with
respect to value computations.

Where do you see any sequencing of the two side effects?

 

[litb]

The passage you quote says just the opposite.  And logically, it
couldn't be any other way: you can't have the side effect (the
modification of i) before having calculated its value.

No. It says that the modification in "i++" happens after value
computation of "i++". What I referred to is the modification in "++i"
to be sequenced before value computation of "++i". I should probably
have started another paragraph to make that clear, but it seemed
obvious to me.

Where do you see any sequencing of the two side effects?

I see it in my above description. Please show us where you don't see
it. I.e where the sequence breaks for you, so we can work it out.
Otherwise, I'm just going to copy/paste the above description again.

 

[James Kanze]

No. It says that the modification in "i++" happens after value
computation of "i++".

In the expression "i++", the side effect is sequenced after the
value computation. Which is in direct contradiction to the last
sentence of yours to which I was responding.

What I referred to is the modification in "++i"
to be sequenced before value computation of "++i".

The side effects of "++i" are not sequenced before anything in
any of the expressions in this thread.

I should probably have started another paragraph to make that
clear, but it seemed obvious to me.

I see it in my above description.

Yes, but on what do you base your description? Where is
there text in the standard supporting it? (There may be,
but I've not seen it.) Where do you find anything
concerning the sequencing of side effects (as opposed to the
value computation) of "i++"? (The only thing I find is the
very generic text in §1.9/14-15, which guarantees that the
side effects are sequenced before the end of the full
expression and before function calls. There's additional
text in §5.14, §5.15, §5.16 and §5.18 which guarantees the
sequencing of side effects where the &&, ||, ?: and comma
operator are involved. But that's all I find. (In fact,
the places where side effects are sequenced seem to
correspond exactly to the places where there are sequence
points in C++03. This isn't by accident; the intent is that
in a single threaded environment, the rules don't change.)

Please show us where you don't see it. I.e where the
sequence breaks for you, so we can work it out.
Otherwise, I'm just going to copy/paste the above
description again.

Your "description" is a vacuous claim. I'm asking about
evidence. As far as I can tell, the current rules do not
change anything with regards to what is or is not legal in
a single threaded program. (They do make it a lot clearer.)

 

[James Kanze]

On Sep 26, 10:53 pm, "Johannes Schaub (litb)" <[email protected]>
wrote:

I'm going back in this thread, because this seems to be
where the error was introduced.

[...]

so, the incrementation of i in i++ is a side effect, whereas the
incrementation of i in ++i is a part of value computation, and
therefore makes ++++i defined. Is that correct?

No. The modification of i, whether in i++ or ++i, is a side
effect, not a value computation. The value computation of
++i is the determination of the object i and the
caluculation resulting from adding one to its current value.
The value computation does *not* include any modification of
memory. Ever.

 

[Johannes Schaub (litb)]

In the expression "i++", the side effect is sequenced after the
value computation. Which is in direct contradiction to the last
sentence of yours to which I was responding.

I can only repeat myself. I talked about ++i, and you still talk about i++.

The side effects of "++i" are not sequenced before anything in
any of the expressions in this thread.

You missed what I quoted from the Standard, it seems:

"In all cases, the assignment is sequenced after the value computation of
the right and left operands, and before the value computation of the
assignment expression."

That assignment is the one in "x+=1", which is the expression that "++x" is
equivalent to.

Yes, but on what do you base your description? Where is
there text in the standard supporting it? (There may be,
but I've not seen it.)

I don't know how to make it clearer.

Your "description" is a vacuous claim. I'm asking about
evidence. As far as I can tell, the current rules do not
change anything with regards to what is or is not legal in
a single threaded program. (They do make it a lot clearer.)

I think my description is clear and the Standard's description is also
clear. Well, I gave not only evidence (as in "try it on GCC and see"), but I
gave a complete proof (as in "work it out by the Standard's text")

 

[Johannes Schaub (litb)]

That's good, because that's what was intended.

Does that mean that you agree with James that "++ ++ i" and "(++i)++" are
still undefined in C++0x (like they were in C++03)? How does that follow
from the rules in n3126?

I actually find it stating quite the opposite, and all people I explained
the rules to agree with me so far (and I also have "evidence" of GCC4.6),
except James does not see or does not want to see that.

We have very knowledgable reading this, including you as the Standards
editor and Anthony Williams. It shouldn't be too difficult to find out.

 

[Kai-Uwe Bux]

It says "The value computation of the ++ expression is sequenced before
the modification of the operand object". The latter is the side effect. So
you have the modification of "++i" before value computation of that
expression, and that value computation before value computation of the
"<lval>++" expression (because value computation of operands of an
operator is sequenced before value computation of their result), which in
turn is sequenced before modification of "<lval>".

So since "sequenced before" is a transitive relation, both side effects
are sequenced with respect to each other and with respect to value
computations.

Ok, let's consider

( x += 1 ) ++

I can see 6 events:

a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1

Let x | y denote "x is sequenced before y". From [5.17/1], I gather that

e,f | d | c

and from [5.2.6/1] that

a | b


What I cannot deduce is c | a, i.e., that a value has to be computed before
it can be incremented. Where would I find that?


Best

Kai-Uwe Bux

 

[Johannes Schaub (litb)]

It says "The value computation of the ++ expression is sequenced before
the modification of the operand object". The latter is the side effect.
So you have the modification of "++i" before value computation of that
expression, and that value computation before value computation of the
"<lval>++" expression (because value computation of operands of an
operator is sequenced before value computation of their result), which in
turn is sequenced before modification of "<lval>".

So since "sequenced before" is a transitive relation, both side effects
are sequenced with respect to each other and with respect to value
computations.

Ok, let's consider

( x += 1 ) ++

I can see 6 events:

a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1

Let x | y denote "x is sequenced before y". From [5.17/1], I gather that

e,f | d | c

and from [5.2.6/1] that

a | b


What I cannot deduce is c | a, i.e., that a value has to be computed
before it can be incremented. Where would I find that?

1.9/15: "The value computations of the operands of an operator are sequenced
before the value computation of the result of the operator.".

 

[Kai-Uwe Bux]

James Kanze wrote:

On Sep 26, 6:57 pm, "Johannes Schaub (litb)" <[email protected]>
wrote:
Armen Tsirunyan wrote:
Also, is
(++i)++;
defined?
I guess not, am I right?

++i is

i = i + 1

The Standard says for postfix i++:

"The value computation of the ++ expression is sequenced before the
modification of the operand object."

And it says for i = x

"In all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the
value computation of the assignment expression."

Together this means that all side effects are sequenced and
all side effects are sequenced relative to all value
computations. Thus the behavior of "(++i)++" is defined.

Where do you get that from? The sentences you quote only speak
of sequencing the *value* computation. Nothing about side
effects.


It says "The value computation of the ++ expression is sequenced before
the modification of the operand object". The latter is the side effect.
So you have the modification of "++i" before value computation of that
expression, and that value computation before value computation of the
"<lval>++" expression (because value computation of operands of an
operator is sequenced before value computation of their result), which
in turn is sequenced before modification of "<lval>".

So since "sequenced before" is a transitive relation, both side effects
are sequenced with respect to each other and with respect to value
computations.

Ok, let's consider

( x += 1 ) ++

I can see 6 events:

a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1

Let x | y denote "x is sequenced before y". From [5.17/1], I gather that

e,f | d | c

and from [5.2.6/1] that

a | b


What I cannot deduce is c | a, i.e., that a value has to be computed
before it can be incremented. Where would I find that?

1.9/15: "The value computations of the operands of an operator are
sequenced before the value computation of the result of the operator.".

Thanks.


Best

Kai-Uwe Bux

 

[James Kanze]

I can only repeat myself. I talked about ++i, and you
still talk about i++.

That's a typo on my part, but it doesn't change anything.
Both behave identically in this respect.

You missed what I quoted from the Standard, it seems:

"In all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the
value computation of the assignment expression."

No, I didn't miss it. It's just not relevant, since we're
talking about the sequencing of side effects, not value
computation.

That assignment is the one in "x+=1", which is the
expression that "++x" is equivalent to.

I don't know how to make it clearer.

By quoting some relevant passage in the standard, rather
than just restating the same thing, without justification.

I think my description is clear and the Standard's
description is also clear.

Quite. It's also clear that they say different things, that
your description doesn't correspond to the standard.

Well, I gave not only evidence (as in "try it on GCC and
see"), but I gave a complete proof (as in "work it out by
the Standard's text")

You've yet to quote any text concerning the sequencing of
side effects in this case. All of the text you cite
concerning value computation.

 

[James Kanze]

[...]

Ok, let's consider

( x += 1 ) ++

I can see 6 events:

a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1

Let x | y denote "x is sequenced before y". From [5.17/1], I gather that

e,f | d | c

and from [5.2.6/1] that

a | b

What I cannot deduce is c | a, i.e., that a value has to
be computed before it can be incremented. Where would
I find that?

§1.9/15.

But that's not the point. The original question is whether
such an expression has undefined behavior. In §1.9/15, we
have "If a side effect on a scalar object is unsequenced
relative to either another side effect on the same scalar
object or a value computation using the value of the same
scalar object, the behavior is undefined." In the given
expression, we have two side effects on x, b and d. They
are not sequenced, since "Except where noted, evaluations of
operands of individual operators and of subexpressions of
individual expressions are unsequenced" (§1.9/15), and no
one has posted anything in from the standard which says
otherwise (the "except where noted"). Unless either
b | d or d | b, the expression has undefined behavior.

QED

 

[James Kanze]

Does that mean that you agree with James that "++ ++ i"
and "(++i)++" are still undefined in C++0x (like they were
in C++03)? How does that follow from the rules in n3126?

I actually find it stating quite the opposite,

But you've yet to post the passage on which you base your
statement.

The standard is a large document, and it's quite possible
that I've missed something in it. My argument is based on
a sentence which starts "Except where noted", and it's quite
possible that something is noted somewhere that I've missed.
All I'm asking is that someone post it.

and all
people I explained the rules to agree with me so far (and
I also have "evidence" of GCC4.6), except James does not
see or does not want to see that.

I don't see how anything a compiler does can "prove" that
the standard doesn't specify undefined behavior. In this
case, I'm fairly sure that the intent was that the behavior
be undefined (and Pete has just backed me up there). If the
wording actually corresponds to the intent (and I've yet to
see any passage in the standard which says otherwise), then
whatever G++ does is conformant.

 

[Kai-Uwe Bux]

James Kanze wrote:

[...]
Ok, let's consider

( x += 1 ) ++

I can see 6 events:

a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1

Let x | y denote "x is sequenced before y". From [5.17/1], I gather that

e,f | d | c

and from [5.2.6/1] that

a | b

What I cannot deduce is c | a, i.e., that a value has to
be computed before it can be incremented. Where would
I find that?

§1.9/15.

But that's not the point. The original question is whether
such an expression has undefined behavior. In §1.9/15, we
have "If a side effect on a scalar object is unsequenced
relative to either another side effect on the same scalar
object or a value computation using the value of the same
scalar object, the behavior is undefined." In the given
expression, we have two side effects on x, b and d. They
are not sequenced, since "Except where noted, evaluations of
operands of individual operators and of subexpressions of
individual expressions are unsequenced" (§1.9/15), and no
one has posted anything in from the standard which says
otherwise (the "except where noted"). Unless either
b | d or d | b, the expression has undefined behavior.

QED

So, what about [1.9/13]:

Sequenced before is an asymmetric, transitive, pair-wise relation between
evaluations executed by a single thread (1.10), which induces a partial
order among those evaluations ...

The operative word being "transitive".

Since d | c, c | a, and a | b, transitivity implies d | b.


Best

Kai-Uwe Bux

 

[litb]

But you've yet to post the passage on which you base your
statement.

The standard is a large document, and it's quite possible
that I've missed something in it.  My argument is based on
a sentence which starts "Except where noted", and it's quite
possible that something is noted somewhere that I've missed.
All I'm asking is that someone post it.


I don't see how anything a compiler does can "prove" that
the standard doesn't specify undefined behavior.  In this
case, I'm fairly sure that the intent was that the behavior
be undefined (and Pete has just backed me up there).  If the
wording actually corresponds to the intent (and I've yet to
see any passage in the standard which says otherwise), then
whatever G++ does is conformant.

For getting evidence, I abused GCCs "this may be undefined" warning.
It does not emit such a warning for "++ ++ i" and "(++i)++".

 

[Armen Tsirunyan]

For getting evidence, I abused GCCs "this may be undefined" warning.
It does not emit such a warning for "++ ++ i" and "(++i)++".

but did it emit such a warning in C++2003 mode? I mean those two were
definitely undefined there, weren't they?

 

[James Kanze]

Johannes Schaub (litb) wrote:
James Kanze wrote:

[...]

Ok, let's consider
( x += 1 ) ++
I can see 6 events:
a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1
Let x | y denote "x is sequenced before y". From [5.17/1], I gather that
e,f | d | c
and from [5.2.6/1] that
a | b
What I cannot deduce is c | a, i.e., that a value has to
be computed before it can be incremented. Where would
I find that?

§1.9/15.
But that's not the point. The original question is whether
such an expression has undefined behavior. In §1.9/15, we
have "If a side effect on a scalar object is unsequenced
relative to either another side effect on the same scalar
object or a value computation using the value of the same
scalar object, the behavior is undefined." In the given
expression, we have two side effects on x, b and d. They
are not sequenced, since "Except where noted, evaluations of
operands of individual operators and of subexpressions of
individual expressions are unsequenced" (§1.9/15), and no
one has posted anything in from the standard which says
otherwise (the "except where noted"). Unless either
b | d or d | b, the expression has undefined behavior.
QED

So, what about [1.9/13]:

Sequenced before is an asymmetric, transitive, pair-wise
relation between evaluations executed by a single thread
(1.10), which induces a partial order among those
evaluations ...

The operative word being "transitive".

Since d | c, c | a, and a | b, transitivity implies d | b.

You may have something there. The critical phrase is "In
all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the
value computation of the assignment expression." Although
I'm not sure what is meant by the first "the
assignment"---from a normal English point of view, I'd say
the side effects, but I've been caught out by standardese
before. If that is really what is meant (and it's hard to
find any other interpretation), it's new. (In C++03 terms,
it's roughly the equivalent of making the assignment
operator a sequence point.) I doubt that it is what was
meant, but I think the standard does need some
clarification: in most (all) other cases, when specifying
the sequencing of (sub-)expressions, the standard states
explicitly whether it is the value calculation or the side
effects which are sequenced.

 

[Alf P. Steinbach /Usenet]

* James Kanze, on 29.09.2010 18:21:

Johannes Schaub (litb) wrote:
James Kanze wrote:
[...]
Ok, let's consider
( x += 1 ) ++
I can see 6 events:
a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1
Let x | y denote "x is sequenced before y". From [5.17/1], I gather that
e,f | d | c
and from [5.2.6/1] that
a | b
What I cannot deduce is c | a, i.e., that a value has to
be computed before it can be incremented. Where would
I find that?
§1.9/15.
But that's not the point. The original question is whether
such an expression has undefined behavior. In §1.9/15, we
have "If a side effect on a scalar object is unsequenced
relative to either another side effect on the same scalar
object or a value computation using the value of the same
scalar object, the behavior is undefined." In the given
expression, we have two side effects on x, b and d. They
are not sequenced, since "Except where noted, evaluations of
operands of individual operators and of subexpressions of
individual expressions are unsequenced" (§1.9/15), and no
one has posted anything in from the standard which says
otherwise (the "except where noted"). Unless either
b | d or d | b, the expression has undefined behavior.
QED

So, what about [1.9/13]:

Sequenced before is an asymmetric, transitive, pair-wise
relation between evaluations executed by a single thread
(1.10), which induces a partial order among those
evaluations ...

The operative word being "transitive".

Since d | c, c | a, and a | b, transitivity implies d | b.

You may have something there. The critical phrase is "In
all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the
value computation of the assignment expression." Although
I'm not sure what is meant by the first "the
assignment"---from a normal English point of view, I'd say
the side effects, but I've been caught out by standardese
before. If that is really what is meant (and it's hard to
find any other interpretation), it's new. (In C++03 terms,
it's roughly the equivalent of making the assignment
operator a sequence point.) I doubt that it is what was
meant, but I think the standard does need some
clarification: in most (all) other cases, when specifying
the sequencing of (sub-)expressions, the standard states
explicitly whether it is the value calculation or the side
effects which are sequenced.

Uhm, someone asked me about this issue privately, and I had to say that I knew
next to nothing about C++0x rules and couldn't provide any insight.

What I should have said was what's occurring to me now:

It does not matter what corner cases C++0x makes well-defined.

One has to code as if by (well known) C++98 rules anyway.

Don't you agree?


Cheers,

- Alf

 

[Kai-Uwe Bux]

Johannes Schaub (litb) wrote:
James Kanze wrote:
[...]
Ok, let's consider
( x += 1 ) ++
I can see 6 events:
a) value computation of ( x += 1 ) ++
b) side effect of _ ++
c) value computation of x += 1
d) side effect of _ += _
e) value computation of x
f) value computation of 1
Let x | y denote "x is sequenced before y". From [5.17/1], I gather
that
e,f | d | c
and from [5.2.6/1] that
a | b
What I cannot deduce is c | a, i.e., that a value has to
be computed before it can be incremented. Where would
I find that?
§1.9/15.
But that's not the point. The original question is whether
such an expression has undefined behavior. In §1.9/15, we
have "If a side effect on a scalar object is unsequenced
relative to either another side effect on the same scalar
object or a value computation using the value of the same
scalar object, the behavior is undefined." In the given
expression, we have two side effects on x, b and d. They
are not sequenced, since "Except where noted, evaluations of
operands of individual operators and of subexpressions of
individual expressions are unsequenced" (§1.9/15), and no
one has posted anything in from the standard which says
otherwise (the "except where noted"). Unless either
b | d or d | b, the expression has undefined behavior.
QED

So, what about [1.9/13]:

Sequenced before is an asymmetric, transitive, pair-wise
relation between evaluations executed by a single thread
(1.10), which induces a partial order among those
evaluations ...

The operative word being "transitive".

Since d | c, c | a, and a | b, transitivity implies d | b.

You may have something there. The critical phrase is "In
all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the
value computation of the assignment expression." Although
I'm not sure what is meant by the first "the
assignment"---from a normal English point of view, I'd say
the side effects, but I've been caught out by standardese
before.

Agreed. Whatever is meant by "the assignment", it is clear that there are
four things being sequenced, "the assignment" being wedged after two and
before the last. The other three are value computations. If "the assignment"
is not the side effect, I would definitely like to know what it is.

If that is really what is meant (and it's hard to
find any other interpretation), it's new. (In C++03 terms,
it's roughly the equivalent of making the assignment
operator a sequence point.)
True.

I doubt that it is what was
meant, but I think the standard does need some
clarification: in most (all) other cases, when specifying
the sequencing of (sub-)expressions, the standard states
explicitly whether it is the value calculation or the side
effects which are sequenced.

I am not so sure that the side-effect could not be meant. I have no
experience in multi-threading, but maybe there are code snippets
demonstrating the need of such sequencing. Are discussions of the committee
available online where one could find examples and rationales?


Best

Kai-Uwe Bux