Typing of the conditional operator

[Robbert Krebbers]

Suppose I have:

int n = 6;
int a[n], b[5];
int (*p)[n] = 1 ? &a : &b;

Here, &a has type int(*)[n] and b has type int(*)[5]. By 6.5.15p6 the
type of the resulting type of the expression 1 ? &a : &b is the
composite type of int(*)[n] and int(*)[5], which is int(*)[5], I
suppose. The assignment is also well-typed because the pointer types are
compatible. Hence, statically, this program seems to be well-typed.

However, does evaluating this program expose undefined behavior?
Clearly, the expression 1 ? &a : &b evaluates to a value of type
int(*)[6] instead of int(*)[5].

Am I missing something here, or does C not satisfy the subject reduction
property (typing is preserved under evaluation).

[Keith Thompson]

I believe the behavior is undefined.

Quoting N1570:

6.5.15p3 says the second and third operands (&a and &b) must satisfy one
of several conditions; the relevant one is "both operands are pointers
to qualified or unqualified versions of compatible types". (This is a
constraint.)

6.7.6.1p1 says:

For two pointer types to be compatible, both shall be identically
qualified and both shall be pointers to compatible types.

6.7.6.2p6 says:

For two array types to be compatible, both shall have compatible
element types, and if both size specifiers are present, and are
integer constant expressions, then both size specifiers shall
have the same constant value. If the two array types are used in
a context which requires them to be compatible, it is undefined
behavior if the two size specifiers evaluate to unequal values.

So the types of &a and &b are compatible, but using them in a context
that requires compatible types causes undefined behavior.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Robbert Krebbers]

On 02/21/2012 12:16 AM, Keith Thompson wrote:
> 6.7.6.2p6 says:
>
> For two array types to be compatible, both shall have compatible
> element types, and if both size specifiers are present, and are
> integer constant expressions, then both size specifiers shall
> have the same constant value. If the two array types are used in
> a context which requires them to be compatible, it is undefined
> behavior if the two size specifiers evaluate to unequal values.

I missed that one. Thank you.

But I am still unsure whether this renders my example as undefined
behavior, because only one of the branches of the conditional is
evaluated, and not both.

It will be more clear in:

void f(int b, int m, int n, int (*p)[m], int(*q)[n]) {
int (*r)[b ? m : n] = b ? p : q;
....
}

Here, the size specifiers of p and q may evaluate to unequal values (in
the case m and n are unequal). However, only p or only q is evaluated,
and not both.

I will be even more awkward with casts to VL types

int (*r)[h(n)] = b ? (int(*)[g1(n)])NULL : (int(*)[g2(m)])NULL;

If the types of both branches should match, I suppose they should
evaluate to arrays with equal size expressions for all possible
evaluation orders?

And what about:

int (*r)[n] = 1 ? (int(*)[n])NULL : (int(*)[n = n++])NULL;

Here the right branch exhibits undefined behavior whereas it is never
evaluated.

Hence I would rather expect something in the lines of:

it is undefined behavior if one of the two size
specifiers evaluate to a value incompatible with
the composite type.

[Robbert Krebbers]

On 02/21/2012 10:10 AM, Robbert Krebbers wrote:
> Hence I would rather expect something in the lines of:
>
> it is undefined behavior if one of the two size
> specifiers evaluate to a value incompatible with
> the composite type.

Oops. This is not what I meant. It should be:

it is undefined behavior if the evaluated size
expression specifier evaluates to a value

[Keith Thompson]

Robbert Krebbers <newsg...@robbertkrebbers.nl> writes:
> On 02/21/2012 12:16 AM, Keith Thompson wrote:
>> 6.7.6.2p6 says:
>>
>> For two array types to be compatible, both shall have compatible
>> element types, and if both size specifiers are present, and are
>> integer constant expressions, then both size specifiers shall
>> have the same constant value. If the two array types are used in
>> a context which requires them to be compatible, it is undefined
>> behavior if the two size specifiers evaluate to unequal values.
> I missed that one. Thank you.
>
> But I am still unsure whether this renders my example as undefined
> behavior, because only one of the branches of the conditional is
> evaluated, and not both.

I don't think that avoids undefined behavior.

The conditional operator requires two arrays to have compatible type
("both operands are pointers to qualified or unqualified versions of
compatible types"), so "the two array types are used in a context which
requires them to be compatible", so the behavior is undefined.

Whether it's reasonable for the behavior to be undefined is another
question, but I think the standard is clear.

[...]

[Shao Miller]

On 2/21/2012 04:10, Robbert Krebbers wrote:
> On 02/21/2012 12:16 AM, Keith Thompson wrote:
>> 6.7.6.2p6 says:
>>
>> For two array types to be compatible, both shall have compatible
>> element types, and if both size specifiers are present, and are
>> integer constant expressions, then both size specifiers shall
>> have the same constant value. If the two array types are used in
>> a context which requires them to be compatible, it is undefined
>> behavior if the two size specifiers evaluate to unequal values.
> I missed that one. Thank you.
>
> But I am still unsure whether this renders my example as undefined
> behavior, because only one of the branches of the conditional is
> evaluated, and not both.
>

The value of the not-taken-branch might not be evaluated, but the type
has to be evaluated, doesn't it?

#include <stdio.h>

int foo(int x) {
printf("Evaluated %d\n", x);
return x;
}

int main(void) {
size_t sz;

sz = sizeof *(1 ? 0 : (int (*)[foo(42)]) 0);
foo(sz);
return 0;

}

> It will be more clear in:
>
> void f(int b, int m, int n, int (*p)[m], int(*q)[n]) {
> int (*r)[b ? m : n] = b ? p : q;
> ....
> }
>

In the example below, 'x' is never evaluated in 'bar' and yet somehow
its type is _still_ evaluated:

#include <stdio.h>

int foo(int x) {
printf("Evaluated %d\n", x);
return x;
}

size_t bar(int (* x)[foo(42)]) {
puts("bar");
return 1 ? 1 : sizeof *x;
}

int main(void) {
size_t sz;

foo(bar(0));
return 0;
}

> [...more examples...]

So I'd think that in the conditional operator, when the types are
evaluated, if two (or more) array types are under consideration for
compatibility and do not have compatible type, the behaviour would be
undefined. If they're compatible, I'd think the behaviour would be defined.

[Shao Miller]

On 2/27/2012 23:34, Shao Miller wrote:
> [...some examples of type evaluation...]

Or, perhaps more simply:

#include <stdio.h>

int foo(int x) {
printf("Evaluated %d\n", x);
return x;
}

int main(void) {

typedef int a_huh[foo(42)];
return 0;
}

[Jens Gustedt]

Hello

No, not in that case. The case that that an evaluation in the sizeof
operator is done is very much restricted:

C> If the type of the operand is a variable length array type, the
C> operand is evaluated; otherwise, the operand is not evaluated and the
C> result is an integer constant.

here you don't have a VLA but only a pointer to it. To determine the
size of the pointer the fact that it points to a VLA is irrelevant.

Jens

[Robbert Krebbers]

On 02/28/2012 10:28 AM, Jens Gustedt wrote:
> here you don't have a VLA but only a pointer to it. To determine the
> size of the pointer the fact that it points to a VLA is irrelevant.

No, there is a dereference operator, so it really is a VLA.

[Jens Gustedt]

oops, thanks, missed that one

Jens

[Robbert Krebbers]

On 02/28/2012 05:34 AM, Shao Miller wrote:
> The value of the not-taken-branch might not be evaluated, but the type
> has to be evaluated, doesn't it?

That seems like a reasonable interpretation. But don't you mean:

The value of the not-taken-branch SHOULD not be evaluated,
but the type MIGHT be evaluated.

Since the return type of a function can never contain a VL type as its
subtype, this means that in order to evaluate a VL type, function calls
can never occur. However, what about incomplete types? Consider:

#include <stdio.h>

typedef int T[];

int a[7];

T* foo() {
printf("foo");
return &a;
}

int main() {
1 ? 0 : foo();
}

In this case, the value (and thus the function call) has to be evaluated
in order to evaluate the type.

(or is this undefined behavior anyway).

[Shao Miller]

On 2/28/2012 09:21, Robbert Krebbers wrote:
> On 02/28/2012 05:34 AM, Shao Miller wrote:
>> The value of the not-taken-branch might not be evaluated, but the type
>> has to be evaluated, doesn't it?
> That seems like a reasonable interpretation. But don't you mean:
>
> The value of the not-taken-branch SHOULD not be evaluated,

Yes.

> but the type MIGHT be evaluated.

No. I believe that the type of the expression is evaluated in this
circumstance.

>
> Since the return type of a function can never contain a VL type as its
> subtype, this means that in order to evaluate a VL type, function calls
> can never occur. However, what about incomplete types? Consider:
>

#include <stdio.h>

/*
* 'T' is an incomplete object type which
* can never be completed
*/
typedef int T[];

/* 'a' is an array type with known size */
int a[7];

T * foo(void) {
/*
* If we are called, we will
* demonstrate that this is the case
*/
printf("foo");
/*
* The type of 'a' is not the same as
* the function type, so 6.8.6.4p3 says
* the value is converted as if by
* assignment
*/
return &a;
/* Just like the following */
T * tmp;
/* 6.5.16.1p1 "both operands are pointers
* pointers to qualified or unqualified
* versions of compatible types" which means
* Keith's 6.7.6.2p6 applies (I think)
*/
tmp = &a;
}

int main(void) {
/*
* I'm pretty sure the type of 'foo()' is
* "evaluated" here without needing to
* call 'foo', which would be evaluating
* its value (rather than the type)
*/
1 ? 0 : foo();
return 0;

}

>
> In this case, the value (and thus the function call) has to be evaluated
> in order to evaluate the type.
>

I don't follow why that is. It seems to me that 'foo' is clearly
defined to return a pointer to the incomplete object type 'T'. I do not
believe that the 'return' (see below) has any influence on the type of
'foo' or its return-type.

> (or is this undefined behavior anyway).

I think the 'return' in 'foo' is.

[Shao Miller]

On 2/28/2012 16:26, Shao Miller wrote:
>
> T * foo(void) {
> /*
> * If we are called, we will
> * demonstrate that this is the case
> */
> printf("foo");
> /*
> * The type of 'a' is not the same as

* Rather, the type of '&a' is not the same as

[Shao Miller]

On 2/28/2012 04:28, Jens Gustedt wrote:
> Hello
>

Thank you for your kind response.

If we forget about the '*' operator that Mr. Robbert Krebbers pointed
out and suppose that 'sizeof' _was_ just being applied to a pointer, can
you please share a reference which states that 'sizeof (int (*)[42]) ==
sizeof (int (*)[z])'? "To determine the size of the pointer...a VLA is
irrelevant." Is it impossible that the size of a VM pointer type might
depend on the size of the pointed-to VLA type?

I could absolutely be mistaken, but my impression of the [cleverly
decorated] quote you share above is that it is referring to evaluation
of The Value Of The Operand (for the form whose operand is a
unary-expression).

As another example:

sz = sizeof (int[42 - 41]);

Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
not because it contributes to The Value Of A Unary-Expression Operand
(it doesn't), but because it contributes to The Type Of A Type-Name Operand.

sz = sizeof (int[42 - 41]){0};

Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
not because it contributes to The Value Of A Unary-Expression Operand
(it doesn't), but because it contributes to The Type Of A
Unary-Expression Operand.

(I think.)

[Robbert Krebbers]

On 02/29/2012 05:42 AM, Shao Miller wrote:
> If we forget about the '*' operator that Mr. Robbert Krebbers pointed
> out and suppose that 'sizeof' _was_ just being applied to a pointer, can
> you please share a reference which states that 'sizeof (int (*)[42]) ==
> sizeof (int (*)[z])'?

As far as I am aware, for compatible types A and B we have that the
representation and alignment requirements of A(*)[n] and B(*)[m] are
equal no matter what n and m are (constant expressions, or non-constant
expressions). In particular this means that their sizes are equal.

6.2.5p28

Similarly, pointers to qualified or unqualified versions
of compatible types shall have the same representation
and alignment requirements.

6.7.6.2p6

For two array types to be compatible, both shall have
compatible element types, and if both size specifiers
are present, and are integer constant expressions,
then both size specifiers shall have the same
constant value.

Clearly, having the same representation and alignment requirements is a
transitive relation, whereas being compatible is not (due to the _and if
both size specifiers are present_). We can easily exploit this.

A(*)[n] `compatible` A(*)[e] (for some non-constant expression e)
`compatible` B(*)[m]

So, although A(*)[n] and B(*)[m] might not be compatible, they both are
compatible with A(*)[e] and thus have the same representation and
alignment requirements as A(*)[e]. Hence A(*)[n] and B(*)[m] have the
same representation and alignment requirements.

[Robbert Krebbers]

thanks for your extensive reply.

On 02/28/2012 10:26 PM, Shao Miller wrote:
> No. I believe that the type of the expression is evaluated in this
> circumstance.

Well, in this particular circumstance (with the sizeof), I believe you
are right. But in general, if we have

1 ? 0 : (int (*)[foo(42)]) 0

I don't see any reason why an implementation _should_ evaluate the
not-taken-branch. An implementation may very well ignore the types
completely (e.g. if each pointer has the same representation regardless
of its type).

> /* Just like the following */
> T * tmp;
> /* 6.5.16.1p1 "both operands are pointers
> * pointers to qualified or unqualified
> * versions of compatible types" which means
> * Keith's 6.7.6.2p6 applies (I think)
> */
> tmp = &a;

I am not convinced here. Let me quote 6.7.6.2p6.

For two array types to be compatible, both shall have
compatible element types, and if both size specifiers
are present, and are integer constant expressions,
then both size specifiers shall have the same constant
value. If the two array types are used in a context
which requires them to be compatible, it is undefined
behavior if the two size specifiers evaluate to unequal
values.

Since it is not the case that both size specifiers are present, we have
that int(*)[] and int(*)[7] are compatible. So, statically, it is all fine.

Now, if they are used in a context which requires them to be compatible,
it is merely undefined behavior _if the two size specifiers_ evaluate to
unequal values. But there are no two size specifiers, so I do not
believe that this clause applies.

> I don't follow why that is. It seems to me that 'foo' is clearly
> defined to return a pointer to the incomplete object type 'T'. I do not
> believe that the 'return' (see below) has any influence on the type of
> 'foo' or its return-type.

Ah, I think I am confused with conditional operator whose resulting type
is the composite type (which is int(*)[7] in the above case). For an
assignment (and a function call) this is not to be the case, indeed.

[Robbert Krebbers]

On 02/29/2012 10:42 AM, Robbert Krebbers wrote:
> I don't see any reason why an implementation _should_ evaluate the
> not-taken-branch.

Rather, the type of the not-taken-branch.

[Shao Miller]

On 2/29/2012 03:54, Robbert Krebbers wrote:
> On 02/29/2012 05:42 AM, Shao Miller wrote:
>> If we forget about the '*' operator that Mr. Robbert Krebbers pointed
>> out and suppose that 'sizeof' _was_ just being applied to a pointer, can
>> you please share a reference which states that 'sizeof (int (*)[42]) ==
>> sizeof (int (*)[z])'?
> As far as I am aware, for compatible types A and B we have that the
> representation and alignment requirements of A(*)[n] and B(*)[m] are
> equal no matter what n and m are (constant expressions, or non-constant
> expressions). In particular this means that their sizes are equal.
>
> 6.2.5p28
>
> Similarly, pointers to qualified or unqualified versions
> of compatible types shall have the same representation
> and alignment requirements.
>
> 6.7.6.2p6
>
> For two array types to be compatible, both shall have
> compatible element types, and if both size specifiers
> are present, and are integer constant expressions,
> then both size specifiers shall have the same
> constant value.
>

I don't follow. 'A(*)[n]' is a pointer to 'A[n]', not to 'A'.
'B(*)[m]' is a pointer to 'B[m]', not to 'B'.

If 'A' and 'B' are compatible, what does that have to do with 'A[n]' and
'B[m]' being compatible? "Compatible element types" is satisfied,
certainly.

But if 'n' and 'm' are ICEs and 'n' != 'm', then they're incompatible.

And if they're not ICEs or one is an ICE and the other isn't, what can
be said about the compatibility of 'A[n]' and 'B[m]'? It seems to be
undefined, doesn't it?

> Clearly, having the same representation and alignment requirements is a
> transitive relation, whereas being compatible is not (due to the _and if
> both size specifiers are present_). We can easily exploit this.
>
> A(*)[n] `compatible` A(*)[e] (for some non-constant expression e)
> `compatible` B(*)[m]
>
> So, although A(*)[n] and B(*)[m] might not be compatible, they both are
> compatible with A(*)[e] and thus have the same representation and
> alignment requirements as A(*)[e]. Hence A(*)[n] and B(*)[m] have the
> same representation and alignment requirements.

I'd have to follow your reasoning in your answers to the questions above
before being able to follow this piece.

[Robbert Krebbers]

On 02/29/2012 06:49 PM, Shao Miller wrote:
> And if they're not ICEs or one is an ICE and the other isn't, what can
> be said about the compatibility of 'A[n]' and 'B[m]'? It seems to be
> undefined, doesn't it?

Well, 6.7.6.2p6 does not, and I haven't found any other text in the
standard that does so. Let us look at 6.7.6.2p6 again.

For two array types to be compatible, both shall have

compatible element types, _and if both size specifiers
are present, and are integer constant expressions_,

then both size specifiers shall have the same
constant value.

Logically, this entails that _if_ at least one size specifier is not
present or at least one size specifier is not an ICE, it merely requires
the element types to be compatible.

Hence

A[n] `compatible` A[e] (for arbitrary non-constant expression e)
`compatible` B[m]

So, by 6.2.5p28 A(*)[n] has the same representation and alignment
requirements as A(*)[e], and A(*)[e] has the same representation and
alignment requirements as B(*)[m].

PS: the conclusion of my previous message was not completely accurate...

[Shao Miller]

On 2/29/2012 04:42, Robbert Krebbers wrote:
> thanks for your extensive reply.
>
> On 02/28/2012 10:26 PM, Shao Miller wrote:
>> No. I believe that the type of the expression is evaluated in this
>> circumstance.
> Well, in this particular circumstance (with the sizeof), I believe you
> are right. But in general, if we have
>
> 1 ? 0 : (int (*)[foo(42)]) 0
>

If there was a semi-colon before and after that, it would constitute a
"void expression."[6.3.2.2p1] Such an expression is evaluated for its
side-effects.

Similarly to what I mentioned else-thread to Mr. Jens Gustedt, the Value
Of The Conditional-Expression could be optimized away if it doesn't
involve any side-effects. There aren't any accesses of 'volatile'
objects, for example. The cast-expression doesn't involve any
side-effects, except for the call to 'foo' while computing the type-name
operand... So there _is_ a side-effect.

> I don't see any reason why an implementation _should_ evaluate the
> not-taken-branch. An implementation may very well ignore the types
> completely (e.g. if each pointer has the same representation regardless
> of its type).

I'm not so sure about that. A function call is a side-effect, so if
it's involved in the determination of a type, I don't see a license to
omit it.

void some_func(void) {
typedef int (* never_used_type)[foo(42)];
return;
}

Here the 'never_used_type' type is never used. Not only that, we don't
even have a "void expression," since this is a "declaration." That
means we don't have to worry about discarding or optimizing any value
computation away for some "expression-statement." But in order to
determine the type that 'never_used_type' will be, we have to call 'foo'.

>> /* Just like the following */
>> T * tmp;
>> /* 6.5.16.1p1 "both operands are pointers
>> * pointers to qualified or unqualified
>> * versions of compatible types" which means
>> * Keith's 6.7.6.2p6 applies (I think)
>> */
>> tmp = &a;
> I am not convinced here. Let me quote 6.7.6.2p6.
>
> For two array types to be compatible, both shall have
> compatible element types, and if both size specifiers
> are present, and are integer constant expressions,
> then both size specifiers shall have the same constant
> value. If the two array types are used in a context
> which requires them to be compatible, it is undefined
> behavior if the two size specifiers evaluate to unequal
> values.
>
> Since it is not the case that both size specifiers are present, we have
> that int(*)[] and int(*)[7] are compatible.

Ok. I had to look at 6.2.7p3 before I was able to read the quote above
as "For two array types to be compatible, both shall have compatible
element types. Stop. Furthermore, if both size specifiers are present
and both are integer constant expressions, then both size specifiers for
two compatible array types shall have the same constant value. Stop.
Furthermore, if both size specifiers are present and the two array types

are used in a context which requires them to be compatible, it is

undefined behaviour if the two size specifiers evaluate to unequal values."

This reminds me of using a function type with no parameter information.

int some_func(int w, int x, int y, int z) {
typedef int arr_unknown[];
typedef int func_unknown();

typedef int arr_4[4];
typedef int func_4(int, int, int, int);

typedef int arr_2[2];
typedef int func_2(int, int);

arr_unknown * a_u;
func_unknown * f_u;

arr_4 * some_arr = &(arr_4){w, x, y, z};

arr_2 * a_2;
func_2 * f_2;

a_2 = a_u = some_arr;
f_2 = f_u = some_func;

return 0;

}

> So, statically, it is all fine.
>

Newly-found agreement. :) So it seems that your example code doesn't
invoke UB where I thought it did.

However that doesn't change my opinion that the return-type of that
function does not depend on the function being called, but only on its
declaration.

> Now, if they are used in a context which requires them to be compatible,
> it is merely undefined behavior _if the two size specifiers_ evaluate to
> unequal values. But there are no two size specifiers, so I do not
> believe that this clause applies.

Ok.

>> I don't follow why that is. It seems to me that 'foo' is clearly
>> defined to return a pointer to the incomplete object type 'T'. I do not
>> believe that the 'return' (see below) has any influence on the type of
>> 'foo' or its return-type.
> Ah, I think I am confused with conditional operator whose resulting type
> is the composite type (which is int(*)[7] in the above case). For an
> assignment (and a function call) this is not to be the case, indeed.

Ok. Nice discussion. :)

[Jens Gustedt]

Am 02/29/2012 05:42 AM, schrieb Shao Miller:
> On 2/28/2012 04:28, Jens Gustedt wrote:
> If we forget about the '*' operator that Mr. Robbert Krebbers pointed
> out and suppose that 'sizeof' _was_ just being applied to a pointer, can
> you please share a reference which states that 'sizeof (int (*)[42]) ==
> sizeof (int (*)[z])'? "To determine the size of the pointer...a VLA is
> irrelevant." Is it impossible that the size of a VM pointer type might
> depend on the size of the pointed-to VLA type?

I think you already got the answer to your question elsewhere in the
thread. But as an indication for that you have that you can call a
function that expects a pointer to VLA with a pointer to array of
fixed size

void func(size_t n, double (*A)[n]);

could be called as

double C[45];

func(45, C);

> As another example:
>
> sz = sizeof (int[42 - 41]);
>
> Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
> not because it contributes to The Value Of A Unary-Expression Operand
> (it doesn't), but because it contributes to The Type Of A Type-Name
> Operand.
>
> sz = sizeof (int[42 - 41]){0};
>
> Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
> not because it contributes to The Value Of A Unary-Expression Operand
> (it doesn't), but because it contributes to The Type Of A
> Unary-Expression Operand.

the expressions 42 - 41 are constant integer expressions that are
evaluated at compile time and the type is determined at compile
time. As you say there is no VLA involved so the sizeof expression is
a constant integer expression, too. To continue your example you could
do

static double x[sizeof (int[42 - 41]){0}];

Jens

[Robbert Krebbers]

On 03/01/2012 02:02 AM, Shao Miller wrote:
> If there was a semi-colon before and after that, it would constitute a
> "void expression."[6.3.2.2p1] Such an expression is evaluated for its
> side-effects.
>
> Similarly to what I mentioned else-thread to Mr. Jens Gustedt, the Value
> Of The Conditional-Expression could be optimized away if it doesn't
> involve any side-effects. There aren't any accesses of 'volatile'
> objects, for example. The cast-expression doesn't involve any
> side-effects, except for the call to 'foo' while computing the type-name
> operand... So there _is_ a side-effect.

So, just to be clear. If we consider

#include<stdio.h>

void* bar() { printf("bar\n"); return 0; }
int foo() { printf("foo\n"); return 42; }

int main() {
1 ? 0 : (int (*)[foo()]) (bar());
}

You are saying it _should_ print "foo" and it _should not_ print "bar"?
To see what actual implementations are doing, I just tested it with the
compilers I have installed on this machine: clang (2.7.3) prints "foo",
but not "bar", and gcc (both 4.4.6 and 4.6.2) prints neither.

Anyway, I cannot find anything about this kind of partial evaluation in
the C standard apart from 6.7.6.2p5

Where a size expression is part of the operand of a
sizeof operator and changing the value of the size
expression would not affect the result of the operator,
it is unspecified whether or not the size expression is
evaluated.

If by analogy this is intended to apply to the above example, I would
say it is unspecified whether foo() is evaluated or not, because
changing the value that foo() returns does not affect the result. (And
hence both clang and gcc would be doing it right).

>> I don't see any reason why an implementation _should_ evaluate the
>> not-taken-branch. An implementation may very well ignore the types
>> completely (e.g. if each pointer has the same representation regardless
>> of its type).
>
> I'm not so sure about that. A function call is a side-effect, so if it's
> involved in the determination of a type, I don't see a license to omit it.
>
> void some_func(void) {
> typedef int (* never_used_type)[foo(42)];
> return;
> }

I do not really see why typedefs are related to the above example. There
the type expression appears in a cast in a piece of (seemingly) dead code.

[Shao Miller]

On 3/1/2012 02:24, Jens Gustedt wrote:
> Am 02/29/2012 05:42 AM, schrieb Shao Miller:
>> On 2/28/2012 04:28, Jens Gustedt wrote:
>> If we forget about the '*' operator that Mr. Robbert Krebbers pointed
>> out and suppose that 'sizeof' _was_ just being applied to a pointer, can
>> you please share a reference which states that 'sizeof (int (*)[42]) ==
>> sizeof (int (*)[z])'? "To determine the size of the pointer...a VLA is
>> irrelevant." Is it impossible that the size of a VM pointer type might
>> depend on the size of the pointed-to VLA type?
>
> I think you already got the answer to your question elsewhere in the
> thread.

Indeed, but thanks for bringing it forward. :)

> But as an indication for that you have that you can call a
> function that expects a pointer to VLA with a pointer to array of
> fixed size
>
> void func(size_t n, double (*A)[n]);
>
> could be called as
>
> double C[45];
>
> func(45, C);
>

(I'm sure you meant 'func(45, &C);', there.)

I'm not sure exactly what that has to do with the representation of the
pointer type, though. "Behind the scenes," perhaps 'func' is
implemented similarly to:

#include <stdarg.h>

void func(size_t n, ...) {
typedef double var_arr[n];
var_arr * A;
va_list ap;

va_start(ap, n);
A = va_arg(ap, var_arr *);
va_end(ap);
/* Rest of body */
}

Even if if 'n' were ommitted, such as in:

void wibble(double (* A)[run_time_int()]);

I'm sure an implementation could "secretly pass" something that would
allow for similar semantics to the 'va_arg' example above.

My point being that given the possibilities of stdarg.h, I don't know
that the truth of your example is sufficient to establish that the
pointer representation needs to be the same.

However, it's fine example of why it _makes_sense_ for the pointer
representations to be the same. :)

>> As another example:
>>
>> sz = sizeof (int[42 - 41]);
>>
>> Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
>> not because it contributes to The Value Of A Unary-Expression Operand
>> (it doesn't), but because it contributes to The Type Of A Type-Name
>> Operand.
>>
>> sz = sizeof (int[42 - 41]){0};
>>
>> Here we don't have a VLA but the sub-expression '42 - 41' is evaluated;
>> not because it contributes to The Value Of A Unary-Expression Operand
>> (it doesn't), but because it contributes to The Type Of A
>> Unary-Expression Operand.
>
> the expressions 42 - 41 are constant integer expressions that are
> evaluated at compile time and the type is determined at compile
> time.

They are? I know they _might_be_. C11's 6.6p11:

C> 11 The semantic rules for the evaluation of a constant
C> expression are the same as for nonconstant
C> expressions.118)
C...
C> 118) Thus, in the following initialization,
C> static int i = 2 || 1 / 0;
C> the expression is a valid integer constant expression
C> with value one.

The behaviour that '1 / 0' is not evaluated seems awfully akin to the
behaviour that the value of the unary-expression operand of 'sizeof' is
not evaluated for non-VLAs.

That's why I think it's important to consider What's Being Evaluated And
Why: The value versus a type-that-involves-evaluations-of-its-own.

> As you say there is no VLA involved so the sizeof expression is
> a constant integer expression, too. To continue your example you could
> do
>
> static double x[sizeof (int[42 - 41]){0}];
>

Agreed, and '42 - 41' is evaluated even though it's found somewhere in
the non-VLA operand of 'sizeof'.

I don't know that using 'static' there forces '42 - 41' to be evaluated
only once ever, however. If that line was found in a function body,
could an implementation not evaluate it once at translation-time in
order to reserve storage, but then evaluate it again at run-time? As
pointless as that might be, I could appreciate an "interpreted C" doing
just that. "Behind the scenes," establishing 'x' could involve the
lookup of an address constant, then establishing the bounds in order to
ensure that accesses do not go beyond the storage reserved at
translation-time. (You'd hope that the bounds were noted at
translation-time, but since we have VLAs anyway...)

Nice discussion. :)

[Shao Miller]

On 3/1/2012 05:18, Robbert Krebbers wrote:
> On 03/01/2012 02:02 AM, Shao Miller wrote:
>> If there was a semi-colon before and after that, it would constitute a
>> "void expression."[6.3.2.2p1] Such an expression is evaluated for its
>> side-effects.
>>
>> Similarly to what I mentioned else-thread to Mr. Jens Gustedt, the Value
>> Of The Conditional-Expression could be optimized away if it doesn't
>> involve any side-effects. There aren't any accesses of 'volatile'
>> objects, for example. The cast-expression doesn't involve any
>> side-effects, except for the call to 'foo' while computing the type-name
>> operand... So there _is_ a side-effect.
> So, just to be clear. If we consider
>
> #include<stdio.h>
>
> void* bar() { printf("bar\n"); return 0; }
> int foo() { printf("foo\n"); return 42; }
>
> int main() {
> 1 ? 0 : (int (*)[foo()]) (bar());
> }
>
> You are saying it _should_ print "foo" and it _should not_ print "bar"?

No "should." I'm saying I don't see a license to omit the call to
'foo'. In this case, sure, we say that the third operand to '?:' is not
evaluated.

But if the '?:' is evaluated, its type is 'int (*)[foo()]'. For a
bounds-checking implementation, producing the pointer might involve
tracking the bounds, and whether or not it's a null pointer value might
be after-the-fact.

Perhaps the conditional-expression itself _isn't_ evaluated, since its
result is unused. Throwing 'void * ptr = ' in front ought to ensure
that it's used.

Yes, I do not believe that the call to 'bar' happens, since the third
operand to '?:' is not evaluated.

> To see what actual implementations are doing, I just tested it with the
> compilers I have installed on this machine: clang (2.7.3) prints "foo",
> but not "bar", and gcc (both 4.4.6 and 4.6.2) prints neither.
>
> Anyway, I cannot find anything about this kind of partial evaluation in
> the C standard apart from 6.7.6.2p5
>
> Where a size expression is part of the operand of a
> sizeof operator and changing the value of the size
> expression would not affect the result of the operator,
> it is unspecified whether or not the size expression is
> evaluated.
>

Yeah.

> If by analogy this is intended to apply to the above example, I would
> say it is unspecified whether foo() is evaluated or not, because
> changing the value that foo() returns does not affect the result. (And
> hence both clang and gcc would be doing it right).

It certainly seems suggestive of a context in which the computation of a
type needn't involve the evaluation of the size expression. Another
problem I have with it is with if 'foo()' could return <= 0 or >
'MAX_ARRAY_ELEMENT_COUNT_FOR_ARRAY_OF_INT' (which I just made up, but
you probably get the point). It seems to me it'd be nice to catch such
errors sooner or later.

>>> I don't see any reason why an implementation _should_ evaluate the
>>> not-taken-branch. An implementation may very well ignore the types
>>> completely (e.g. if each pointer has the same representation regardless
>>> of its type).
>>
>> I'm not so sure about that. A function call is a side-effect, so if it's
>> involved in the determination of a type, I don't see a license to omit
>> it.
>>
>> void some_func(void) {
>> typedef int (* never_used_type)[foo(42)];
>> return;
>> }
> I do not really see why typedefs are related to the above example. There
> the type expression appears in a cast in a piece of (seemingly) dead code.

There's no cast. This isn't even a statement, but like an initializer
in a declaration, it has a chance to produce an error at run-time. So
does determining the type of the conditional operator's result.

[Robbert Krebbers]

On 03/02/2012 07:39 AM, Shao Miller wrote:
> But if the '?:' is evaluated, its type is 'int (*)[foo()]'. For a
> bounds-checking implementation, producing the pointer might involve
> tracking the bounds, and whether or not it's a null pointer value might
> be after-the-fact.

[...]

> It certainly seems suggestive of a context in which the computation of a
> type needn't involve the evaluation of the size expression. Another
> problem I have with it is with if 'foo()' could return <= 0 or >
> 'MAX_ARRAY_ELEMENT_COUNT_FOR_ARRAY_OF_INT' (which I just made up, but
> you probably get the point). It seems to me it'd be nice to catch such
> errors sooner or later.

An important point of the spirit of C is that an implementation should
not have to catch such errors. A semantics for C should certainly allow
foo() to be evaluated or not, and therefore will give the program
undefined behavior in case the array bounds is incorrect. As a result,
this gives an implementation the means to do whatever they like (instead
of catching the error in a sensible way) if this kind of behavior appears.

>>> void some_func(void) {
>>> typedef int (* never_used_type)[foo(42)];
>>> return;
>>> }
>> I do not really see why typedefs are related to the above example. There
>> the type expression appears in a cast in a piece of (seemingly) dead
>> code.
> There's no cast. This isn't even a statement, but like an initializer in
> a declaration, it has a chance to produce an error at run-time. So does
> determining the type of the conditional operator's result.

Sorry, my "there" might have been ambiguous, it was supposed to refer to
the example with

[Jens Gustedt]

Am 03/02/2012 06:59 AM, schrieb Shao Miller:
> On 3/1/2012 02:24, Jens Gustedt wrote:
>> But as an indication for that you have that you can call a
>> function that expects a pointer to VLA with a pointer to array of
>> fixed size
>>
>> void func(size_t n, double (*A)[n]);
>>
>> could be called as
>>
>> double C[45];
>>
>> func(45, C);
>>
>
> (I'm sure you meant 'func(45, &C);', there.)

yes, sure, sorry

> I'm not sure exactly what that has to do with the representation of the
> pointer type, though. "Behind the scenes," perhaps 'func' is
> implemented similarly to:
>
> #include <stdarg.h>
>
> void func(size_t n, ...) {
> typedef double var_arr[n];
> var_arr * A;
> va_list ap;
>
> va_start(ap, n);
> A = va_arg(ap, var_arr *);
> va_end(ap);
> /* Rest of body */
> }
>
> Even if if 'n' were ommitted, such as in:
>
> void wibble(double (* A)[run_time_int()]);
>
> I'm sure an implementation could "secretly pass" something that would
> allow for similar semantics to the 'va_arg' example above.

No, I don't think that passing something secretly behind the scenes
makes sense here. The size of the (pointed to) VLA is not determined
on the call side. The size expression is evaluated in the context of
the callee. (Take them to be in two different compilation units, e.g.)

It is perfectly valid that the caller passes in a void* (e.g. directly
from malloc). So there is no secret information passed to the callee,
for the simple reason that this information doesn't necessarily exist.

The callee stores the size information somewhere. How this is done is
completely up to the implementation. Much care is taken in the
definition of the properties of VLA such that this size information
must never be shared between different compilation units, and so there
is never a need to store that information in the pointer itself.

> They are? I know they _might_be_. C11's 6.6p11:
>
> C> 11 The semantic rules for the evaluation of a constant
> C> expression are the same as for nonconstant
> C> expressions.118)

I think this just means that the value of the expression that is
determined during the compilation phase must be exactly the same as if
it would be evaluated at run time.

>> As you say there is no VLA involved so the sizeof expression is
>> a constant integer expression, too. To continue your example you could
>> do
>>
>> static double x[sizeof (int[42 - 41]){0}];
>>
>
> Agreed, and '42 - 41' is evaluated even though it's found somewhere in
> the non-VLA operand of 'sizeof'.
>
> I don't know that using 'static' there forces '42 - 41' to be evaluated
> only once ever, however. If that line was found in a function body,
> could an implementation not evaluate it once at translation-time in
> order to reserve storage, but then evaluate it again at run-time?

Hm, it could, but such an evaluation is not observable, so I hope no
compiler will ever do that :)

> As
> pointless as that might be, I could appreciate an "interpreted C" doing
> just that.

Such a thing doesn't exist, if it is interpreted, it is not C :)


Jens

[Robbert Krebbers]

On 03/02/2012 09:22 PM, Jens Gustedt wrote:
> Such a thing doesn't exist, if it is interpreted, it is not C:)

Why? If a C interpreter satisfies all conditions stated in the C
standard, I do not see any reason why it would not be C. Or does the C
standard explicitly state this somewhere?

[Shao Miller]

I was thinking of the expression system in 'gdb', in particular, for
what it's worth.

[Jens Gustedt]

Am 03/03/2012 02:13 PM, schrieb Robbert Krebbers:
> On 03/02/2012 09:22 PM, Jens Gustedt wrote:
>> Such a thing doesn't exist, if it is interpreted, it is not C:)

have you seen the :) ?

> Why? If a C interpreter satisfies all conditions stated in the C
> standard, I do not see any reason why it would not be C. Or does the C
> standard explicitly state this somewhere?

yes, at the end of C11 5.1.1.2, translation phases:

All such translator output is collected into a program image
which contains information needed for execution in its execution
environment.

This "program image" must reflect all the work that has been done
during the different translation phases, in particular preprocessing
and linking between different compilation units and the C
library. These translation phases proceed linearly in the text and it
would not be easily combined with the program execution that proceeds
in branching, function calls and exceptional jumps through goto or
longjmp.

But something like Java byte code, for example, is certainly a
possibility. IIRC gcc can be used for that. If such a thing is to be
considered as interpreted is certainly a matter of taste.

Jens

[Tim Rentsch]

Robbert Krebbers <newsg...@robbertkrebbers.nl> writes:

> Suppose I have:
>
> int n = 6;
> int a[n], b[5];
> int (*p)[n] = 1 ? &a : &b;
>
> Here, &a has type int(*)[n] and b has type int(*)[5]. By 6.5.15p6 the
> type of the resulting type of the expression 1 ? &a : &b is the
> composite type of int(*)[n] and int(*)[5], which is int(*)[5], I
> suppose. The assignment is also well-typed because the pointer types
> are compatible. Hence, statically, this program seems to be
> well-typed.
>
> However, does evaluating this program expose undefined behavior?
> Clearly, the expression 1 ? &a : &b evaluates to a value of type
> int(*)[6] instead of int(*)[5].
>
> Am I missing something here, or does C not satisfy the subject
> reduction property (typing is preserved under evaluation).

Undefined behavior, for the same reason that

int (*q)[n] = &b;

would be undefined behavior.

[Tim Rentsch]

Robbert Krebbers <newsg...@robbertkrebbers.nl> writes:

> On 02/21/2012 12:16 AM, Keith Thompson wrote:
>> 6.7.6.2p6 says:
>>

>> For two array types to be compatible, both shall have compatible
>> element types, and if both size specifiers are present, and are
>> integer constant expressions, then both size specifiers shall
>> have the same constant value. If the two array types are used in
>> a context which requires them to be compatible, it is undefined
>> behavior if the two size specifiers evaluate to unequal values.

> I missed that one. Thank you.
>
> But I am still unsure whether this renders my example as undefined
> behavior, because only one of the branches of the conditional is
> evaluated, and not both.
>

> It will be more clear in:
>
> void f(int b, int m, int n, int (*p)[m], int(*q)[n]) {
> int (*r)[b ? m : n] = b ? p : q;
> ....
> }
>

> Here, the size specifiers of p and q may evaluate to unequal values
> (in the case m and n are unequal). However, only p or only q is
> evaluated, and not both.

The expression 'b ? p : q' already has behavior since m != n.


> I will be even more awkward with casts to VL types
>
> int (*r)[h(n)] = b ? (int(*)[g1(n)])NULL : (int(*)[g2(m)])NULL;

The expression

b ? (int(*)[g1(n)])NULL : (int(*)[g2(m)])NULL

under C99 is, at best, dicey. Under C11 is it undefined
behavior.


> If the types of both branches should match, I suppose they should
> evaluate to arrays with equal size expressions for all possible
> evaluation orders?
>
> And what about:
>
> int (*r)[n] = 1 ? (int(*)[n])NULL : (int(*)[n = n++])NULL;
>
> Here the right branch exhibits undefined behavior whereas it is never
> evaluated.

Same as above, for the same reasons (ie, does not depend
on any concerns regarding accesses to 'n').

[Tim Rentsch]

Robbert Krebbers <newsg...@robbertkrebbers.nl> writes:

> On 03/01/2012 02:02 AM, Shao Miller wrote:
>> If there was a semi-colon before and after that, it would constitute a
>> "void expression."[6.3.2.2p1] Such an expression is evaluated for its
>> side-effects.
>>
>> Similarly to what I mentioned else-thread to Mr. Jens Gustedt, the Value
>> Of The Conditional-Expression could be optimized away if it doesn't
>> involve any side-effects. There aren't any accesses of 'volatile'
>> objects, for example. The cast-expression doesn't involve any
>> side-effects, except for the call to 'foo' while computing the type-name
>> operand... So there _is_ a side-effect.
> So, just to be clear. If we consider
>
> #include<stdio.h>
>
> void* bar() { printf("bar\n"); return 0; }
> int foo() { printf("foo\n"); return 42; }
>
> int main() {
> 1 ? 0 : (int (*)[foo()]) (bar());
> }
>
> You are saying it _should_ print "foo" and it _should not_ print
> "bar"? To see what actual implementations are doing, I just tested it
> with the compilers I have installed on this machine: clang (2.7.3)
> prints "foo", but not "bar", and gcc (both 4.4.6 and 4.6.2) prints
> neither.

Undoubtedly undefined behavior under C11. (And now
C99 is just history. :)

> Anyway, I cannot find anything about this kind of partial evaluation
> in the C standard apart from 6.7.6.2p5
>
> Where a size expression is part of the operand of a
> sizeof operator and changing the value of the size
> expression would not affect the result of the operator,
> it is unspecified whether or not the size expression is
> evaluated.
>
> If by analogy this is intended to apply to the above example, I would
> say it is unspecified whether foo() is evaluated or not, because
> changing the value that foo() returns does not affect the result. (And
> hence both clang and gcc would be doing it right).
>>> I don't see any reason why an implementation _should_ evaluate the
>>> not-taken-branch. An implementation may very well ignore the types
>>> completely (e.g. if each pointer has the same representation regardless
>>> of its type).
>>
>> I'm not so sure about that. A function call is a side-effect, so if it's
>> involved in the determination of a type, I don't see a license to omit it.
>>
>> void some_func(void) {
>> typedef int (* never_used_type)[foo(42)];
>> return;
>> }
> I do not really see why typedefs are related to the above
> example. There the type expression appears in a cast in a piece of
> (seemingly) dead code.

The size expressions in typedef's of this sort
are required to be evaluated.

[Robbert Krebbers]

On 03/08/2012 06:34 AM, Tim Rentsch wrote:
>> So, just to be clear. If we consider
>> >
>> > #include<stdio.h>
>> >
>> > void* bar() { printf("bar\n"); return 0; }
>> > int foo() { printf("foo\n"); return 42; }
>> >
>> > int main() {
>> > 1 ? 0 : (int (*)[foo()]) (bar());
>> > }
>> >

>> > You are saying it_should_ print "foo" and it_should not_ print

>> > "bar"? To see what actual implementations are doing, I just tested it
>> > with the compilers I have installed on this machine: clang (2.7.3)
>> > prints "foo", but not "bar", and gcc (both 4.4.6 and 4.6.2) prints
>> > neither.
> Undoubtedly undefined behavior under C11. (And now
> C99 is just history.:)

Could you give a reference to the corresponding text in the standard
that states that this is undefined behavior?

[Tim Rentsch]

Check out N1570 6.2.7 p3.

(And could I ask you to adjust your responding style
so blank lines are left after quoted text and before
your responses? Leaving no blank lines makes it
harder to see what you're saying... I'm sure you
don't want that. :)

[Robbert Krebbers]

On 03/20/2012 11:42 PM, Tim Rentsch wrote:
> Robbert Krebbers<newsg...@robbertkrebbers.nl> writes:
>
>> On 03/08/2012 06:34 AM, Tim Rentsch wrote:
>>>> So, just to be clear. If we consider
>>>>>
>>>>> #include<stdio.h>
>>>>>
>>>>> void* bar() { printf("bar\n"); return 0; }
>>>>> int foo() { printf("foo\n"); return 42; }
>>>>>
>>>>> int main() {
>>>>> 1 ? 0 : (int (*)[foo()]) (bar());
>>>>> }
>>>>>
>>>>> You are saying it_should_ print "foo" and it_should not_ print
>>>>> "bar"? To see what actual implementations are doing, I just tested it
>>>>> with the compilers I have installed on this machine: clang (2.7.3)
>>>>> prints "foo", but not "bar", and gcc (both 4.4.6 and 4.6.2) prints
>>>>> neither.
>>>
>>> Undoubtedly undefined behavior under C11. (And now
>>> C99 is just history.:)
>>
>> Could you give a reference to the corresponding text in the
>> standard that states that this is undefined behavior?
>
> Check out N1570 6.2.7 p3.

I fail to see why composite types matter in this example. Check out
6.5.15p3:

One of the following shall hold for the second and third
operands:
...
- both operands are pointers to qualified or unqualified
versions of compatible types;
- one operand is a pointer and the other is a null pointer
constant
...

Although the first rule of the quoted text may not hold (since 6.2.7 p3
does not say anything about the null pointer constant?), the second one
clearly does, since

(int (*)[foo()]) (bar())

has pointer type.

[Tim Rentsch]

Robbert Krebbers <newsg...@robbertkrebbers.nl> writes:

> On 03/20/2012 11:42 PM, Tim Rentsch wrote:
>> Robbert Krebbers<newsg...@robbertkrebbers.nl> writes:
>>
>>> On 03/08/2012 06:34 AM, Tim Rentsch wrote:
>>>>> So, just to be clear. If we consider
>>>>>>
>>>>>> #include<stdio.h>
>>>>>>
>>>>>> void* bar() { printf("bar\n"); return 0; }
>>>>>> int foo() { printf("foo\n"); return 42; }
>>>>>>
>>>>>> int main() {
>>>>>> 1 ? 0 : (int (*)[foo()]) (bar());
>>>>>> }
>>>>>>
>>>>>> You are saying it_should_ print "foo" and it_should not_ print
>>>>>> "bar"? To see what actual implementations are doing, I just tested it
>>>>>> with the compilers I have installed on this machine: clang (2.7.3)
>>>>>> prints "foo", but not "bar", and gcc (both 4.4.6 and 4.6.2) prints
>>>>>> neither.
>>>>
>>>> Undoubtedly undefined behavior under C11. (And now
>>>> C99 is just history.:)
>>>
>>> Could you give a reference to the corresponding text in the
>>> standard that states that this is undefined behavior?
>>
>> Check out N1570 6.2.7 p3.
>
> I fail to see why composite types matter in this example. Check out

> 6.5.15p3: [snip detail]

I'm sorry, I was careful to read 6.5.15 before posting but
obviously I wasn't careful enough. Your comment is spot on.

Having said that, I would still argue that the behavior is
undefined, because the type is not well-defined. Certainly
the expression containing the typename (ie, the third operand
of the ?: operator) is not evaluated, which means the size
expression in the typename is not evaluated. In effect we
have a VLA type (inside a variably modified type) whose size
expression has an indeterminate value. The behavior, or even
the meaning, of such a type is not defined in the Standard;
hence the behavior of an expression having such a type is, by
omission, undefined behavior. (Even though it doesn't come
into play directly, 6.2.7 p3 does support the conclusion that
size expressions in typenames whose containing expression is
not evaluated are not themselves evaluated.)

I suppose it could be argued that, since whatever the type of
the conditional expression is doesn't affect the behavior of
the overall expression-statement, and hence has no effect on
what the program does, the program behavior is defined even
though the type in question is not. Even if that were true,
the typename size expression must not be evaluated. (If an
unevaluated size expression's putative value does affect what
some code does then of course the behavior of said code would
be undefined.) At some level I don't care whether programs
like the one above have defined behavior or not; however, if
the behavior is defined, I don't see anything in the Standard
that allows the size expression to be evaluated, and so it
must not be evaluated (or else grant that such cases introduce
undefined behavior).