Velocity Reviews > Sub-sub-expression evaluation order

# Sub-sub-expression evaluation order

Frank Wallingford
Guest
Posts: n/a

 12-09-2004
Note: For those with instant reactions, this is NOT the common "why is i

I came across an interesting question when talking with my colleagues.
According to the standard, most operators evaluate their operands in an
unspecified order. This means that in code like this:

f() + g()

the two functions may be called in either order, and still be standards-
compliant.

Fine. Now, when the evaluation of one sub-expression begins, is there
anything in the standard that says that it must complete (ignoring side-
effects) before the other sub-expression evaluation begins? In other
words, can pieces of the sub-expressions be evaluated in an interleaving
fashion?

Take this example:

f(i++) + g(i++)

The difference from the first example is the sequence points for the
function calls.

Now, obviously since f() and g() may be called in any order, this code
is non-deterministic. My question is: can the compiler evaluate the sub-
expressions in the following order, interleaving the sub-sub-expression
evaluations?

t1 = i;
t2 = i;
i++;
i++;
f(t1);
g(t2);

Note that all side-effects were finished before the function-call
sequence points, so this doesn't violate that.

If there is nothing in the standard to prevent this, then not only is
the code "f(i++) + g(i++)" non-deterministic, but it remains as
undefined as "i++ + i++".

Here is an example where I think the above problem exists, although it's
not obvious (please ignore the obvious problems and poor design; this is
pseudo-code to illustrate a point):

const char *a(void)
{
static char *x;
if (x) free(x);
x = (char*)malloc(2);
strcpy(x, "a");
return x;
}

printf("%s %s\n", a(), a());

The obvious problem here is that the second call to a() (in either
order) will free the pointer returned by the first call.

Here is the revised version, but I believe that the following is still
undefined:

const char *a(void) { ... same as above ... }

static list *strings; // implementation not important

const char *cache(const char *in)
{
char *out;
out = strdup(in);
return out;
}

printf("%s %s\n", cache(a()), cache(a()));

The cache() function only exists so that calls like 'printf' can be made
- that is, they copy the argument off and return the copy (and save it
in a list to be freed later). This way, the second call to a() doesn't
affect anything by freeing the old value.

But, similar to the above, I believe that an implementation is free to
evaluate the printf call in this order:

char *t1 = a();
char *t2 = a();
char *t3 = cache(t1);
char *t4 = cache(t2);
printf("%s %s\n", t3, t4);

Is this right? Is it undefined, according to the standard?

-Frank

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

Andrey Tarasevich
Guest
Posts: n/a

 12-10-2004
Frank Wallingford wrote:
> ...
> I came across an interesting question when talking with my colleagues.
> According to the standard, most operators evaluate their operands in an
> unspecified order. This means that in code like this:
>
> f() + g()
>
> the two functions may be called in either order, and still be standards-
> compliant.

That's correct.

> Fine. Now, when the evaluation of one sub-expression begins, is there
> anything in the standard that says that it must complete (ignoring side-
> effects) before the other sub-expression evaluation begins? In other
> words, can pieces of the sub-expressions be evaluated in an interleaving
> fashion?

Yes. The evaluation can be implemented in any way, as long as it
produces the result that satisfies the requirements imposed by the
language specification.

> Take this example:
>
> f(i++) + g(i++)
>
> The difference from the first example is the sequence points for the
> function calls.

There are indeed sequence points at the beginning of each function's
execution. However, the standard doesn't require the evaluation of
argument subexpressions to be "tightly packed" with the execution of the
corresponding function. In other words, in this particular case the
expression might be interpreted as two consecutive 'i++' evaluations
(not separated by any sequence point) followed by calls to 'f' and 'g'.
This means that the modifications of 'i' are potentially violating the
requirements of the standard and the code produces undefined behavior.

> Now, obviously since f() and g() may be called in any order, this code
> is non-deterministic.

If by "non-deterministic" you mean that the code produces unspecified
result, you are wrong. The code produces undefined behavior.

> My question is: can the compiler evaluate the sub-
> expressions in the following order, interleaving the sub-sub-expression
> evaluations?
>
> t1 = i;
> t2 = i;
> i++;
> i++;
> f(t1);
> g(t2);

Yes. That's exactly what I said above. Note though, that there wouldn't
really be any sequence points between two modifications of 'i', which

> Note that all side-effects were finished before the function-call
> sequence points, so this doesn't violate that.

What exactly do you mean by "that" here?

> If there is nothing in the standard to prevent this, then not only is
> the code "f(i++) + g(i++)" non-deterministic, but it remains as
> undefined as "i++ + i++".

Exactly.

> Here is an example where I think the above problem exists, although it's
> not obvious (please ignore the obvious problems and poor design; this is
> pseudo-code to illustrate a point):
>
> const char *a(void)
> {
> static char *x;
> if (x) free(x);
> x = (char*)malloc(2);
> strcpy(x, "a");
> return x;
> }
>
> printf("%s %s\n", a(), a());
>
> The obvious problem here is that the second call to a() (in either
> order) will free the pointer returned by the first call.

That's correct. But I'd say that the nature of the problem is very
different here.

> Here is the revised version, but I believe that the following is still
> undefined:
>
> const char *a(void) { ... same as above ... }
>
> static list *strings; // implementation not important
>
> const char *cache(const char *in)
> {
> char *out;
> out = strdup(in);
> return out;
> }
>
> printf("%s %s\n", cache(a()), cache(a()));
>
> The cache() function only exists so that calls like 'printf' can be made
> - that is, they copy the argument off and return the copy (and save it
> in a list to be freed later). This way, the second call to a() doesn't
> affect anything by freeing the old value.
>
> But, similar to the above, I believe that an implementation is free to
> evaluate the printf call in this order:
>
> char *t1 = a();
> char *t2 = a();
> char *t3 = cache(t1);
> char *t4 = cache(t2);
> printf("%s %s\n", t3, t4);
>
> Is this right?

Yes, that's perfectly possible.

>Is it undefined, according to the standard?

I don't see any problems with the last portion of code. It doesn't have
any violations present in the 'f(i++) + g(i++)' example. Why exactly do
you suspect that it is undefined?

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich
Guest
Posts: n/a

 12-10-2004
Andrey Tarasevich wrote:
>> Here is the revised version, but I believe that the following is still
>> undefined:
>>
>> const char *a(void) { ... same as above ... }
>>
>> static list *strings; // implementation not important
>>
>> const char *cache(const char *in)
>> {
>> char *out;
>> out = strdup(in);
>> return out;
>> }
>>
>> printf("%s %s\n", cache(a()), cache(a()));
>>
>> The cache() function only exists so that calls like 'printf' can be made
>> - that is, they copy the argument off and return the copy (and save it
>> in a list to be freed later). This way, the second call to a() doesn't
>> affect anything by freeing the old value.
>>
>> But, similar to the above, I believe that an implementation is free to
>> evaluate the printf call in this order:
>>
>> char *t1 = a();
>> char *t2 = a();
>> char *t3 = cache(t1);
>> char *t4 = cache(t2);
>> printf("%s %s\n", t3, t4);
>>
>> Is this right?

>
> Yes, that's perfectly possible.
>
>>Is it undefined, according to the standard?

>
> I don't see any problems with the last portion of code. It doesn't have
> any violations present in the 'f(i++) + g(i++)' example. Why exactly do
> you suspect that it is undefined?
>

Oops... I'm sorry. I misread the code. Of course, the potential
evaluation order you suggested leads to the same problem as in the
original version of the code. If you integrate the functionality of
'cache()' into 'a()' then the problem will disappear (somehow I thought
that this has already been done)

--
Best regards,
Andrey Tarasevich

Frank Wallingford
Guest
Posts: n/a

 12-10-2004
Andrey Tarasevich <(E-Mail Removed)> wrote in
news:(E-Mail Removed):

> Andrey Tarasevich wrote:
>>> Here is the revised version, but I believe that the following is
>>> still undefined:
>>>
>>> const char *a(void) { ... same as above ... }
>>>
>>> static list *strings; // implementation not important
>>>
>>> const char *cache(const char *in)
>>> {
>>> char *out;
>>> out = strdup(in);
>>> return out;
>>> }
>>>
>>> printf("%s %s\n", cache(a()), cache(a()));
>>>
>>> The cache() function only exists so that calls like 'printf' can be
>>> made - that is, they copy the argument off and return the copy (and
>>> save it in a list to be freed later). This way, the second call to
>>> a() doesn't affect anything by freeing the old value.
>>>
>>> But, similar to the above, I believe that an implementation is free
>>> to evaluate the printf call in this order:
>>>
>>> char *t1 = a();
>>> char *t2 = a();
>>> char *t3 = cache(t1);
>>> char *t4 = cache(t2);
>>> printf("%s %s\n", t3, t4);
>>>
>>> Is this right?
>>>Is it undefined, according to the standard?

>>
>> I don't see any problems with the last portion of code. It doesn't
>> have any violations present in the 'f(i++) + g(i++)' example. Why
>> exactly do you suspect that it is undefined?
>>

>
> Oops... I'm sorry. I misread the code. Of course, the potential
> evaluation order you suggested leads to the same problem as in the
> original version of the code. If you integrate the functionality of
> 'cache()' into 'a()' then the problem will disappear (somehow I
> thought that this has already been done)

Right - the last example is undefined because if the implementation re-
orders the sub-expressions and calls 'a' twice before calling 'cache',
then it ends up accessing memory that has been deallocated.

-Frank

--
(E-Mail Removed)

Chris Torek
Guest
Posts: n/a

 12-10-2004
In article <Xns95BAB949C3D9fwallingfordhotmailc@69.28.186.158 >
Frank Wallingford <(E-Mail Removed)> wrote:
>Note: For those with instant reactions, this is NOT the common "why is i

Indeed. (It is almost a comp.std.c question, it is so well-specified )

[much snippage]
> f(i++) + g(i++)
>... then not only is
>the code "f(i++) + g(i++)" non-deterministic, but it remains as
>undefined as "i++ + i++".

Yes. There are sequence points before the calls to f() and g(),
after the evaluation of the various parameters, but the parameter
evaluations can be "interleaved", giving this undefinedness (I
believe -- you might check in comp.std.c to see if there is any
sort of consensus on this one).

[another example, mostly snipped]

>But, similar to the above, I believe that an implementation is free to
>evaluate the printf call in this order:
>
> char *t1 = a();
> char *t2 = a();
> char *t3 = cache(t1);
> char *t4 = cache(t2);
> printf("%s %s\n", t3, t4);
>
>Is this right? Is it undefined, according to the standard?

I believe so, yes.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.