Potential Violation of 6.5p2

[Shao Miller]

Good day,

Some discussion in another thread prompts me to ask: Does the included
source code yield undefined behaviour? I believe it does, since it's a
violation of a "shall" in 6.5p2 (of 'n1256.pdf'), where each element
object of 'ia' is read for a purpose unrelated to determining the new
value that will be stored therein.

Code also available at: http://codepad.org/s5U6MU9C

Thank you,

- Shao Miller

#include <stdio.h>

/**
* There's no causal possibility for misbehaviour,
* but is it undefined behaviour, nonetheless?
*/

int main(void) {
/* Non-volatile */
int ia[] = {0, 1, 2, 3, 4, 5};
int cur = 6;

do {
cur--;
/**
* The RHS of the assignment determines the new
* value, but the object is read on the LHS.
*/
ia[ia[cur]] = cur + 1;
printf("{ %d, %d, %d, %d, %d, %d }\n",
ia[0], ia[1], ia[2], ia[3], ia[4], ia[5]);
} while (cur);
return cur;
}

Sample output:

{ 0, 1, 2, 3, 4, 6 }
{ 0, 1, 2, 3, 5, 6 }
{ 0, 1, 2, 4, 5, 6 }
{ 0, 1, 3, 4, 5, 6 }
{ 0, 2, 3, 4, 5, 6 }
{ 1, 2, 3, 4, 5, 6 }

 

[Ersek, Laszlo]

/**
* The RHS of the assignment determines the new
* value, but the object is read on the LHS.
*/
ia[ia[cur]] = cur + 1;

*(ia + *(ia + cur)) = cur + 1;

All "ia" and "cur" instances are evaluated in an unspecified order. (All
"ia"'s decay to pointers to the first element.)

The outer dereference (indirection operator) on the left side cannot be
evaluated before the outer addition is evaluated on the left side. (The
operand of the indirection operator is simply not available until then.)

The outer addition on the left side cannot be evaluated before the inner
dereference (indirection operator) is evaluated -- the right operand of
the outer addition is simply not available until then.

And so on. Even if the same "slot" of "ia" is accessed twice (once read,
once written to), the data dependencies dictated by how the operators are
bound together serialize those accesses correctly.

lacos

 

[Shao Miller]

   /**
    * The RHS of the assignment determines the new
    * value, but the object is read on the LHS.
    */
   ia[ia[cur]] = cur + 1;

*(ia + *(ia + cur)) = cur + 1;

All "ia" and "cur" instances are evaluated in an unspecified order. (All
"ia"'s decay to pointers to the first element.)

The outer dereference (indirection operator) on the left side cannot be
evaluated before the outer addition is evaluated on the left side. (The
operand of the indirection operator is simply not available until then.)

The outer addition on the left side cannot be evaluated before the inner
dereference (indirection operator) is evaluated -- the right operand of
the outer addition is simply not available until then.

And so on. Even if the same "slot" of "ia" is accessed twice (once read,
once written to), the data dependencies dictated by how the operators are
bound together serialize those accesses correctly.

I am in full agreement with the details you have provided. Thanks,
lacos.

Unfortunately, despite the flow of causality you point out, an object
is read for purposes unrelated to a computation of the value which
will be stored in it, which I perceive to be a violation of a "shall"
in 6.5p2. What I'm wondering is if anyone sees a way out of this
violation, or doesn't see it at all.

 

[Ben Bacarisse]

Some discussion in another thread prompts me to ask: Does the included
source code yield undefined behaviour? I believe it does, since it's
a violation of a "shall" in 6.5p2 (of 'n1256.pdf'), where each element
object of 'ia' is read for a purpose unrelated to determining the new
value that will be stored therein.

Yes. Agreement, however, is not the main purpose this post.

#include <stdio.h>

/**
* There's no causal possibility for misbehaviour,
* but is it undefined behaviour, nonetheless?
*/

int main(void) {
/* Non-volatile */
int ia[] = {0, 1, 2, 3, 4, 5};
int cur = 6;

do {
cur--;
/**
* The RHS of the assignment determines the new
* value, but the object is read on the LHS.
*/
ia[ia[cur]] = cur + 1;

I think you could have come up with a simpler example. 'cur' is
irrelevant to your point and there is no need for a loop:

int ia[] = {0};
ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that people
will be distracted by the extras.

printf("{ %d, %d, %d, %d, %d, %d }\n",
ia[0], ia[1], ia[2], ia[3], ia[4], ia[5]);
} while (cur);
return cur;
}

<snip>

 

[Ersek, Laszlo]

int ia[] = {0};
ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that people
will be distracted by the extras.

Well, I stand corrected again.

Taking your word for it, I acknowledge that the code above violates the
words of the standard. I doubt it violates its intent.

Evaluating the inner ia[0] is indeed not necessary for computing the next
value of ia[0]. It is however necessary to *select* ia[0] for assignment.
A store takes two things, a "what" and a "where to". The current wording
of the standard appears to consider the "what", but not the "where to".

.... I suspect somebody will be able to disprove this, so please, do.

Thanks,
lacos

 

[lawrence.jones]

Unfortunately, despite the flow of causality you point out, an object
is read for purposes unrelated to a computation of the value which
will be stored in it, which I perceive to be a violation of a "shall"
in 6.5p2. What I'm wondering is if anyone sees a way out of this
violation, or doesn't see it at all.

The way out is C1X, the latest draft of which can be found at the
committee's web site <http://wg14.open-std.org/jtc1/sc22/wg14/> as
document N1494. The statement in 6.5p2 did not fully reflect the
committee's intent, but there was never any agreement on a formal model
that did correctly reflect the intent before the new memory and
sequencing model reflected in the draft.

 

[Shao Miller]

Some discussion in another thread prompts me to ask: Does the included
source code yield undefined behaviour?  I believe it does, since it's
a violation of a "shall" in 6.5p2 (of 'n1256.pdf'), where each element
object of 'ia' is read for a purpose unrelated to determining the new
value that will be stored therein.

Yes.  Agreement, however, is not the main purpose this post.

<snip>

#include <stdio.h>

/**
 * There's no causal possibility for misbehaviour,
 * but is it undefined behaviour, nonetheless?
 */

int main(void) {
  /* Non-volatile */
  int ia[] = {0, 1, 2, 3, 4, 5};
  int cur = 6;

  do {
    cur--;
    /**
     * The RHS of the assignment determines the new
     * value, but the object is read on the LHS.
     */
    ia[ia[cur]] = cur + 1;

I think you could have come up with a simpler example.  'cur' is
irrelevant to your point and there is no need for a loop:

  int ia[] = {0};
  ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that people
will be distracted by the extras.

    printf("{ %d, %d, %d, %d, %d, %d }\n",
      ia[0], ia[1], ia[2], ia[3], ia[4], ia[5]);
  } while (cur);
  return cur;
}

Well there's no winning, sometimes. In another C-devoted forum,

int i = 0;
int *ip = &i;
*(ip + i) = 0;

was far too confusing, because it was perhaps too abstract and useless
on its own. This code does something visible, at least.

Thanks for confirming though, Ben.

 

[Shao Miller]

 int ia[] = {0};
 ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that people
will be distracted by the extras.

Well, I stand corrected again.

Taking your word for it, I acknowledge that the code above violates the
words of the standard. I doubt it violates its intent.

Evaluating the inner ia[0] is indeed not necessary for computing the next
value of ia[0]. It is however necessary to *select* ia[0] for assignment.
A store takes two things, a "what" and a "where to". The current wording
of the standard appears to consider the "what", but not the "where to".

... I suspect somebody will be able to disprove this, so please, do.

Please indeed... It doesn't seem like it should be a violation.

 

[Ben Bacarisse]

int ia[] = {0};
ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that
people will be distracted by the extras.

Well, I stand corrected again.

Taking your word for it, I acknowledge that the code above violates
the words of the standard. I doubt it violates its intent.

Hmm... on that point I will be silent. I simply don't know (but see
below for a way forward).

Evaluating the inner ia[0] is indeed not necessary for computing the
next value of ia[0]. It is however necessary to *select* ia[0] for
assignment. A store takes two things, a "what" and a "where to". The
current wording of the standard appears to consider the "what", but
not the "where to".

Yes, that's the way I see it.

Most of the "is a[i++] = a[--i] + i++; defined" questions are just there
to test the meaning of the words. Using an element of the array as an
index to the array, however, occurs in real-world code to do with
permutations and cryptography and care has to be taken to ensure that
the result is defined by the language. I've come across this in actual
code in the wild. I have the vaguest memory (but I can't verify this
with a citation) of unexpected result from an compiler's optimiser that
used the undefined nature of this sort of code to its advantage (and to
the determent of the code's author!)

... I suspect somebody will be able to disprove this, so please, do.

I wonder if the new wording in the C draft has any effect on this
expression. The intent of the wording is just to clarify the intent of
the old wording, so any differences would be revealing.

 

[Shao Miller]

The way out is C1X, the latest draft of which can be found at the
committee's web site <http://wg14.open-std.org/jtc1/sc22/wg14/> as
document N1494.  The statement in 6.5p2 did not fully reflect the
committee's intent, but there was never any agreement on a formal model
that did correctly reflect the intent before the new memory and
sequencing model reflected in the draft.

Thanks, Larry! Simply amazing. Identification of an lvalue's object
is defined as part of value computation. The way out is C1X,
indeed.

 

[Tim Rentsch]

int ia[] = {0};
ia[ia[0]] = 1;

is undefined for the same reason and there is less chance that
people will be distracted by the extras.

Well, I stand corrected again.

Taking your word for it, I acknowledge that the code above violates
the words of the standard. I doubt it violates its intent.

Hmm... on that point I will be silent. I simply don't know (but see
below for a way forward).

Evaluating the inner ia[0] is indeed not necessary for computing the
next value of ia[0]. It is however necessary to *select* ia[0] for
assignment. A store takes two things, a "what" and a "where to". The
current wording of the standard appears to consider the "what", but
not the "where to".

Yes, that's the way I see it.

Most of the "is a[i++] = a[--i] + i++; defined" questions are just there
to test the meaning of the words. Using an element of the array as an
index to the array, however, occurs in real-world code to do with
permutations and cryptography and care has to be taken to ensure that
the result is defined by the language. I've come across this in actual
code in the wild. I have the vaguest memory (but I can't verify this
with a citation) of unexpected result from an compiler's optimiser that
used the undefined nature of this sort of code to its advantage (and to
the determent of the code's author!)

... I suspect somebody will be able to disprove this, so please, do.

I wonder if the new wording in the C draft has any effect on this
expression. The intent of the wording is just to clarify the intent of
the old wording, so any differences would be revealing.

Statements like

ia[0] = 0;
ia[ia[0]] = 1;

are certainly well-defined under the wording in C1X.