Re: Yet another binary search tree library

On 26 juil, 17:09, Tim Rentsch <t...@xxxxxxxxxxxxxxxxxx> wrote:
Francis Moreau <francis.m...@xxxxxxxxx> writes:
On Jul 23, 1:06 am, Tim Rentsch <t...@xxxxxxxxxxxxxxxxxx> wrote:
Francis Moreau <francis.m...@xxxxxxxxx> writes:
Tim Rentsch <t...@xxxxxxxxxxxxxxxxxx> writes:

Francis Moreau <francis.m...@xxxxxxxxx> writes:

Tim Rentsch <t...@xxxxxxxxxxxxxxxxxx> writes:

Francis Moreau <francis.m...@xxxxxxxxx> writes:

[...]

No, the item of 6.5p7 which I pointed out doesn't deal about:

    struct object {
        int a;
    };

    [...]

    struct object an_object;
    int *p = &an_object.a;

As you said, this is clearly defined, since we're accessing the
(member) object "an_object.a" with a pointer whose type is compatible.

Right, but this case isn't what I was asking about.

But this is the case for all examples you gave below, I think.

It isn't.  The cases below access the same memory using two
distinct types, one type 'int' and the other type a structure
type.

However doing this:

    struct object *obj;
    int a = 5;
    obj = (struct object *)&a;

is defined by the C standard AFAIK (by what you call 'effective type
rules' I believe, but 'strict aliasing rules' defined by GCC breaks
this rules.  [snip]

For starters this is (usually) undefined behavior anyway, because
of pointer alignments and size mismatches if nothing else.

However, suppose we have this:

    int *p;
    struct { int a; int b; } *x, *y;
    x = malloc( sizeof *x );
    y = malloc( sizeof *y );
    /* presume the mallocs succeed */

    y->a = y->b = 0;
    *x = *y;
    p = &x->a;

So 'p' is an alias to the object 'x->a'. They both have the same type.

The expression 'x->a' is never used in the example code to access
an object;

Isn't

  *x = *y;

equivalent to

  x->a = y->a;
  x->b = y->b;

?

No.  Similar, yes, but not equivalent.

it's used only to take its address to assign to 'p'.  The other
accesses to this object are done using a structure type, which is
different from int.

    *p = 5;
    *x = *y;
    /* under strict aliasing must '*p == 0' still be true? */

    *x = *y;
    *p = 7;
    *y = *x;
    /* under strict aliasing must 'y->a == 7' still be true? */

    y->a = y->b = 0;
    *x = *y;
    *p = 9;
    x = (void*) p;
    *x = *y;
    /* under strict aliasing must '*p == 0' still be true? */

Do you believe, even under gcc strict aliasing, that any of the
comment questions can have an answer other than "Yes"?.  If so,
what leads you to that conclusion?

I don't think that GCC strict aliasing rule deals about these cases.
All of these 3 cases are about a (member) object (whose type is 'int')
that can be accessed by a pointer with the _same_ type.

Please look again.  They are about accessing an object using two
very different types.

However GCC strict aliasing rule deals about the case where an object
is accessed by another one which has a _different_ type. For example:

  int i;
  struct A { int a; } *x;

  x = (struct A *)&i;
  x->a = 0;

where we're accessing an object (type of 'int') through a pointer to a
structure. So we're accessing an object through a pointer which has a
_different_ (not even /almost/ the same) type. Note that this example
is perfectly legal C AFAIK.

I'm afraid your understanding of C is somewhat lacking.

Yes probably...

First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
undefined behavior) because of alignment requirements.

How did you come to that conclusion ?

Could you show me the 'path' across the standard that leads you to
this conclusion ?

Just for reminder the definition of 'struct A' is:

   struct A { int a; };

Suppose that 'sizeof(int) == 4'.  The alignment of int's in
such an implementation is 1, 2, or 4.  The structure, on
the other hand, can have an alignment that is any multiple
of the alignment of int's;  so for example, if the alignment
of 'int' is 2, the alignment of the structure could be 14.

Ok, so all of this is up to the implementation.

Let assume that 'struct A' and 'int' types have the same alignment.

Second, even if it succeeds, trying to access 'i' using 'x->a' is
always undefined behavior, because in such cases '*x' must refer to a
structure object, and 'i' isn't in any structure.

First, doing 'x->a' (done by my previous example) is accessing the
member object 'a', not the structure object (ie the whole collection
of the member objects of the structure).

The description of the '->' operator says it designates a member of
a structure or union _object_ (my emphasis).  Since in this example
there is no structure or union object, and there is no description
of what happens when there isn't such an object, the behavior is
undefined.

please see below...

Second, 6.5p7 which lists all possible ways to access an object value,
tells me that 'x->a' is a defined way to access _an_ 'int' object
since "typeof(x->a) == int".

No it doesn't say that.  What it /does/ say is that if you do _not_
access an int object using one of a specified set of types, then the
behavior is undefined.

and what the specified set of types ?

Answer:

 [...]
 an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union)

Note that this is one defined way to access _an_ object. This doesn't
say a word about the fact that for this case it must be a _member_
object.

Did you understand the main point I was making?  That 6.5p7
doesn't ever guarantee legality, but only excludes cases besides
the ones it lists?  6.5p7 is a /necessary/ condition for an
access to be defined behavior, but it is not a /sufficient/
condition.  That's why reading other sections of the Standard
is needed here.

So could you tell me (again) how did you come to this conclusion ?

Did you even bother reading the description of the '->' operator?
There's nothing mysterious about the reasoning.

Please stop asking me to read the standard.

As you probably know, this document is far from trivial to understand.

And if you're skilled enough to understand such paper just after one
reading, then you had probably noticed that comp.lang.c is full of
questions asking to clarify the spec.

I apologize for the tone of my earlier comment.  It was
unnecessarily harsh.

no problem.


However, if someone is making assertions about what the Standard
requires or allows, I don't think it's unreasonable to expect
that they should and will read the Standard to try to understand
what it says.  I don't mind answering questions when the
reasoning necessary is convoluted or otherwise hard to find.

thank you, your answers are valuable to decipher the Standard.

In
this particular case I thought the reasoning involved would be
obvious to someone who had read the description of the operators
used.  I explained that reasoning in the previous posting, and
also explained why 6.5p7 doesn't affect the outcome; 6.5p7
can only make otherwise defined behavior be allowed, it cannot
make undefined behavior be defined.  So the semantic provisions
of the '->' operator, having failed to be met, mean this case
is undefined behavior.

Ok, I see now.

This is really sad to see that just adding a couple of word would have
clarify a lot this point. Instead I have to sail accross the whole
document to get scattered information.

How about this new example, which should make you happier regarding
the '->' operator:

struct A { int a; };
struct B { int b; };

struct A *p;
struct B b_object;

p = (struct A *)&b_object;
p->a = 1;

As you can see, there're no more alignment issues since (in my
understanding) all pointers to structure types have the same
representation and alignment requirements as each other.

And (still in my understanding), there's no more undefined behaviour
since the '->' operator requirement is satisfied now: p now points to
a structure object.

What do you think ?

.

Relevant Pages

  • Re: Yet another binary search tree library
    ... one type 'int' and the other type a structure ... undefined behavior) because of alignment requirements. ... member object 'a', not the structure object (ie the whole collection ...
    (comp.lang.c)
  • Re: void * arithmetic
    ... in standard C, it's a constraint violation, requiring a ... Adding a pointer and an integer yields a new pointer value ... unsigned int u = -1; ... range, resulting in undefined behavior. ...
    (comp.lang.c)
  • Re: Order of declaration of variables changes the output?
    ... Formally speaking, "this is undefined behavior". ... "%d" expects a pointer to int. ... than one char in memory ...
    (comp.lang.c)
  • Re: Small C "Puzzle"
    ... > really see anything wrong with the code (yes, stdlib.h is missing, int ... In this case, the undefined behavior manifests ... invalid pointer value. ...
    (comp.lang.c)
  • Re: request for member in something not a structure or union
    ... to be either a structure or a pointer to structure. ... accessing the same member via a pointer to the structure as two ... int csr; ... The compiler did not bother to see whether p->next or t.next ...
    (comp.lang.c)