Does a constraint violation cause undefined behavior?
Keith Thompson
"constraint violation" and "undefined behavior" in this newsgroup is
likely to yield much more chaff than wheat.
An implementation is allowed, but not required, to reject a program
that violates a constraint, as long as it issues at least one
diagnostic.
This came out of a discussion on comp.lang.c, subject "Is this an
error or undefined behaviour?"; the complex "++" example is thanks to
James Kuyper.
If a program contains a constraint violation, and if the
implementation accepts it anyway, is the program's behavior undefined,
even if there's a description of the behavior?
For example:
#include <stdio.h>
#include <complex.h>
int main(void)
{
double complex z = 0.0;
z ++;
printf("z = %f + %fi\n", creal(z), cimag(z));
return 0;
}
C99 6.5.2.4p1 says that the attempt to apply postfix "++" to a complex
operand is a constraint violation, but 6.5.2.4p2 describes the
semantics in a manner that could easily and consistently apply to
complex operands.
If the program is accepted, must ``z ++;'' (which is a constraint
violation) be equivalent to ``z += 1;'' (which is not)? Or is the
behavior undefined, allowing an implementation to define the semantics
as an extension?
Similarly, this:
void *ptr = 0xdeadbeef;
violates a constraint; if it's accepted, must it be equivalent to
void *ptr = (void*)0xdeadbeef;
or is it simply undefined?
(My own opinion is that the behavior *should* be considered undefined;
the standard doesn't seem to say so explicitly, but it should. I
think the wording of 6.5.2.4p2 doesn't specifically exclude complex
types just because doing so would have been excessively verbose.)
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
James Kuyper
For those who aren't watching comp.lang.c:
My own point of view is that because the standard does not say so
explicitly, this must be decided on a case by case basis. In most cases,
constraints, by their very nature, are violated only when the normally
defined behavior becomes impossible to implement, or even meaningless.
However, there are a few cases, as above, where this is not the case. An
implementation is not required to accept code which has a constraint
violation, but having accepted it, if the behavior is defined, it must
implement that defined behavior.
Note: while I believe that this is the correct interpretation of the
standard as written, I wouldn't mind having the wording changed.
Identifying cases where this argument applies is tricky, and will always
be open to debate. I'd be happy to rely upon market forces, rather than
the standard, to force implementors to handle z++ as z=z+1, if they
choose to accept the code. However, if a constraint violation is
supposed to always leave the behavior undefined, this should be stated
explicitly.
Wojtek Lerch
news:lnmyu28...@nuthaus.mib.org...
> I'm not sure whether this has been asked before, and searching for
> "constraint violation" and "undefined behavior" in this newsgroup is
> likely to yield much more chaff than wheat.
There was a thread in April 2006 that you started, with an almost identical
subject line:
http://groups.google.com/group/comp.std.c/browse_frm/thread/58d5574520aaac65?hl=en
Keith Thompson
Whoops! Never mind.
Douglas A. Gwyn
erroneous, a.k.a. "invalid", which amounts to non-acceptance
even if the translator also produces object code for it.
Any behavior of such object code lies entirely outside the
scope of the standard. It's not merely undefined, it's
nonexistent.
Keith Thompson
And where in the standard is that idea expressed? Since the
implementation is not required to reject the program, how can its
behavior be nonexistent?
Wojtek Lerch
> "Douglas A. Gwyn" <DAG...@null.net> writes:
>> The idea is that the program which requires a diagnostic is
>> erroneous, a.k.a. "invalid", which amounts to non-acceptance
> And where in the standard is that idea expressed?
How about 1#1:
"This International Standard specifies the form and establishes the
interpretation of programs written in the C programming language. It
specifies [...]
- the syntax and constraints of the C language;"
The syntax and constraints of the C language determine what pieces of text
are C programs and which ones are not. If a piece of text does not conform
to the syntax or constraints of the C language, it is not a C program, and
therefore its meaning is outside of the scope of the C standard.
James Kuyper
> The idea is that the program which requires a diagnostic is
> erroneous, a.k.a. "invalid", which amounts to non-acceptance
> even if the translator also produces object code for it.
That's a reasonable idea, but not one actually expressed in the text of
the standard.
> Any behavior of such object code lies entirely outside the
> scope of the standard. It's not merely undefined, it's
> nonexistent.
The standard only allows the behavior to become undefined in three ways:
explicit statements that the behavior is undefined, a 'shall' that
occurs outside of a constraint, or by omission. There is no omission in
the case of z++, when z is complex: there is a fully applicable
definition provided by 6.5.2.4p2. Which of the other options applies?
I know that it's been argued that the obscurely worded definition of
constraint: "restrictions, both syntactic and semantic, by which the
exposition of language elements is to be interpreted" means that any
otherwise clearly applicable requirements count as having been omitted,
even if they are right there, in the document, for anyone to read.
Frankly, I can't figure out what that definition means, so perhaps that
is a correct interpretation of it; but if so, that meaning should be
conveyed in a less Delphic way. To me, it seems that the standard
expresses very clearly the idea that the implications of undefined
behavior are all-encompassing (though many people have found it
substantially less clear). If it is intended that constraint violations
should always be comparably catastrophic, the standard should say so at
least as clearly as it does in the current wording for undefined behavior.
James Kuyper
...
> "This International Standard specifies the form and establishes the
> interpretation of programs written in the C programming language. It
> specifies [...]
>
> - the syntax and constraints of the C language;"
>
> The syntax and constraints of the C language determine what pieces of
> text are C programs and which ones are not.
I don't believe that's a correct interpretation of that clause. The
syntax rules are how the standard describes the form of a C program, so
something which violates those rules is indeed not a C program. However,
the rest of the standard, including the constraints, are how the
standard describes the interpretation of a C program. It's still a C
program, even if the interpretation runs into problems.
I found an interesting comment in an example (which is therefore
unfortunately non-normative). 5.1.1.3p2 says "in those cases where
wording in this International Standard describes the behavior for a
construct as being both a constraint error and resulting in undefined
behavior, the constraint error shall be diagnosed". This implies to me
that there can also be other cases where the behavior is only described
as a constraint error, and not also as undefined behavior. However,
that's only suggested by this wording; it's not proved by it.
Antoine Leca
> 5.1.1.3p2 says "in those cases where
> wording in this International Standard describes the behavior for a
> construct as being both a constraint error and resulting in undefined
> behavior, the constraint error shall be diagnosed".
This text was specifically added to cover the defect raised in DR17 question
3, http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_017.html.
However, I cannot see more information from the discussions that may have
taken place in 1992 for the resolution of the DR, discussions which led to
the creation of this example and its "comment", which was not specified in
the DR.
Antoine
Douglas A. Gwyn
> "Douglas A. Gwyn" <DAG...@null.net> writes:
> > The idea is that the program which requires a diagnostic is
> > erroneous, a.k.a. "invalid", which amounts to non-acceptance
> > even if the translator also produces object code for it.
> > Any behavior of such object code lies entirely outside the
> > scope of the standard. It's not merely undefined, it's
> > nonexistent.
> And where in the standard is that idea expressed? Since the
> implementation is not required to reject the program, how can its
> behavior be nonexistent?
The C standard doesn't define a lot of terms in this area,
including "acceptance" and "rejection" (which seem like they
must be opposites). Therefore the generic DP dictionary is
supposed to apply. I don't have a copy of it, but assume
that a language translator when "accepting" a program does
not complain about it (produce a diagnostic). If a
diagnostic (identifiable as such in an implementation-
defined manner) is produced then I would think the program
has perforce been rejected, to the extent that the scope of
the standard applies. Any other side effects such as code
generation may or may not occur, without affecting the C
implementation's conformance with the standard.
Douglas A. Gwyn
> ... It's still a C
> program, even if the interpretation runs into problems.
100 PRINT 'Hello, world!'
110 END
Sorry, that's not a C program, even if a conforming C
implementation manages to identify it as BASIC and
translates it as such. A diagnostic is produced
complaining that it violates standard C syntax, and
whatever else happens is irrelevant. But it defies
common sense to call it a C program.
Douglas A. Gwyn
> ... To me, it seems that the standard
> expresses very clearly the idea that the implications of undefined
> behavior are all-encompassing (though many people have found it
> substantially less clear). If it is intended that constraint violations
> should always be comparably catastrophic, the standard should say so at
> least as clearly as it does in the current wording for undefined behavior.
I've pointed out for many years now that the conformance categories
in the C standard could use further elaboration and refinement;
however, the Committee approaches such changes with great trepidation
due to the far-ranging effect of modifying something of such central
importance.
Syntax errors and violations of requirements imposed within the
so-labeled "Constraints" clauses require that at least one diagnostic
be issued for the translation unit when processed by a conforming
C implementation. Any further processing is simply beyond the scope
of the standard: the translation could be terminated, or it could
proceed with some implementation-defined behavior imposed for the
violation, or it could lead to undefined behavior when the final
program is executed. It is quite reasonably left up to the
implementor to choose how he wants to proceed in each case, and those
details do not have to be documented (which would be the case if it
were specified as "implementation defined").
Issuance of a "diagnostic" (meeting the implementation definition for
identification, required for conformance to the C standard) implies
rejection of the program (again, insofar as conformance is concerned).
If an implementation wants to proceed to do something further with
the translation unit, typically to continue processing to potentially
generate additional diagnostics but also to go ahead and produce
object code, then that is its business and it is allowed to do so.
Keith Thompson
Are you assuming that the term "diagnostic" refers only to diagnostics
that are required by the C standard? An implementation may issue any
additional diagnostics it likes, even for strictly conforming
programs, and it's not required to distinguish between required and
optional diagnostics. So issuing a diagnostic doesn't imply
non-acceptance.
Keith Thompson
> Issuance of a "diagnostic" (meeting the implementation definition for
> identification, required for conformance to the C standard) implies
> rejection of the program (again, insofar as conformance is concerned).
> If an implementation wants to proceed to do something further with
> the translation unit, typically to continue processing to potentially
> generate additional diagnostics but also to go ahead and produce
> object code, then that is its business and it is allowed to do so.
I like that interpretation, and I wish it were clearly stated in the
standard.
James Kuyper
Did you read the part where I wrote:
> The syntax rules are how the standard describes the form of a C
> program, so something which violates those rules is indeed not a C
> program.
?
James Kuyper
...
> The C standard doesn't define a lot of terms in this area,
> including "acceptance" and "rejection" (which seem like they
> must be opposites). Therefore the generic DP dictionary is
> supposed to apply. I don't have a copy of it, but assume
> that a language translator when "accepting" a program does
> not complain about it (produce a diagnostic). If a
> diagnostic (identifiable as such in an implementation-
> defined manner) is produced then I would think the program
> has perforce been rejected, to the extent that the scope of
> the standard applies. Any other side effects such as code
> generation may or may not occur, without affecting the C
> implementation's conformance with the standard.
Every compiler I'm familiar with has the capability of generating
non-fatal diagnostics whose occurrence cannot, by any reasonable
standard, be taken as indicating that the code has been rejected. An
object file is produced, which can be linked to form an executable
program, and that program produces behavior that conforms with all
applicable requirements of the C standard. How could you count that as a
rejection?
James Kuyper
...
> so-labeled "Constraints" clauses require that at least one diagnostic
> be issued for the translation unit when processed by a conforming
> C implementation. Any further processing is simply beyond the scope
> of the standard:
I don't see any way to derive the truth of that assertion from the text
of the standard. In many cases, constraint violations do indeed leave
the behavior that would otherwise be defined by the rest of the standard
meaningless or inherently incapable of being carried out, so it is
undefined by omission. However, in those rare cases where it's perfectly
clear how to interpret the rest of the standard even in the case where a
particular constraint has been violated, I don't see how you can
conclude that the standard's scope has been escaped.
> the translation could be terminated, ...
Yes, the standard is quite clear about that.
> ... or it could
> proceed with some implementation-defined behavior imposed for the
> violation, or it could lead to undefined behavior when the final
Unless the standard explicitly says so, or a 'shall' outside a
constraint has been violated, or definition of the behavior has been
committed, I don't see how an implementor could accept the code and
justify providing anything behavior other than that which the standard
defines for the code.
> Issuance of a "diagnostic" (meeting the implementation definition for
> identification, required for conformance to the C standard) implies
> rejection of the program (again, insofar as conformance is concerned).
The standard is quite clear about the requirements for code conforming
to the C standard; they are far more lenient than that. All that's
required is that the code be acceptable by some compiler somewhere.
The standard says nothing to suggest that issuance of a diagnostic
indicates that the code has been rejected. If the standard does say
that, then most of the compilers I've ever used are non-conforming,
because almost all of them can issue non-fatal diagnostics for some
kinds of strictly conforming code. Thus, by your interpretation of what
a diagnostic means, they are rejecting strictly conforming code.
If it were true that issuance of a diagnostic message constitutes
rejection of the code, then it would give the definition of "conforming
code" a lot more teeth than it has in reality; conforming code would not
include any code for which a diagnostic was mandatory. However, I can
find no textual support for that concept.
Douglas A. Gwyn
> Unless the standard explicitly says so, or a 'shall' outside a
> constraint has been violated, or definition of the behavior has been
> committed, I don't see how an implementor could accept the code and
> justify providing anything behavior other than that which the standard
> defines for the code.
My point (spread across a few postings in this thread) is that
the translation units has not been "accepted" (in the standard's
sense) if a required diagnostic has been issued.
One of the related issues where the C standard sould use
improvement can be seen in the wording of subclause 3.10,
where "diagnostic" is defined as "message belonging to an
implementation-defined subset of the implementation's message
output". The idea ought to be to that other diagnostic-like
messages are excluded from the term "diagnostic" as used in
the standard, such as when diagnostics are required for
certain source constructs, and further that no such
"diagnostic" be issued when a program is "accepted" in the
C standard's use of *that* term. The practical effect would
be that "optional" messages would need some way of being
distinguished from "standard-mandated" diagnostics.
Unfortunately, the footnote to subclause 5.1.1.3 mixes the
two kinds of message into the one term "diagnostio".
This issue has been discussed at times by the Committee,
but as I noted previously they have been very reluctant to
make any changes in the area of conformance requirements.
> The standard is quite clear about the requirements for code conforming
> to the C standard; they are far more lenient than that. All that's
> required is that the code be acceptable by some compiler somewhere.
The category of (not "strictly") "conforming" program was
put into the standard merely to convey the notion that the
mere use of (*allowed*) extensions does not prevent the
specifications of the standard from applying to the rest of
the program.
What happens for a *non-allowed* extension (one where the
source code violates a syntax rule or constraint) is a
separate matter, as is whether such a program can be
"accepted" in the sense in which the standard uses the term.
The usual usage within the trade is that a parser does *not*
"accept" the input under such circumstances, no matter what
side effects (such as code generation) may occur.
james...@verizon.net
...
> the translation units has not been "accepted" (in the standard's
> sense) if a required diagnostic has been issued.
My point, spread across a similar variety of posting, is that I don't
see any justification for believing that statement to be true.
Douglas A. Gwyn
At the end of my previous posting, I pointed out that it
was standard usage of the concept of "accepting" a source
within the computational grammar community. If there is
a syntax violation then a properly implemented parser
will reject the source; and violation of constraints as
C uses them to augment the grammar is in the same class.
Keith Thompson
Again: I like the argument, and I wish it were actually stated in the
standard.
james...@verizon.net
> james...@verizon.net wrote:
> > Douglas A. Gwyn wrote:
> > > My point (spread across a few postings in this thread) is that
> > > the translation units has not been "accepted" (in the standard's
> > > sense) if a required diagnostic has been issued.
> > My point, spread across a similar variety of posting, is that I don't
> > see any justification for believing that statement to be true.
>
> At the end of my previous posting, I pointed out that it
> was standard usage of the concept of "accepting" a source
I can't find any prior message on this thread, by anybody, that
contains any of the words "computational", "grammar", or "community".
I don't see anything in your previous posting that directly or
indirectly invokes the concept of a specialized community with a more
specific definition of "accepting" than that used in ordinary English.
An earlier message cross-references "the generic DP dictionary", but I
don't know where to find that dictionary, I assumed it was a metaphor,
and I would not have thought to make any connection between that
metaphor and computational grammar.
I'm using the ordinary, imprecise English meaning of "accept", and the
standard's definition of "diagnostic". With those definitions, if the
compiler generates a usable executable, I see no way to interpret the
issuance of a diagnostic message as indicating rejection; it's just an
informational message unless it halts translation of the program.
You suggest that there's a distinction between the significance of
mandatory and optional diagnostics.
The standard says nothing to suggest that required diagnostics must be
distinguishable from optional diagnostics, which would make it pretty
difficult to apply that distinction. In my experience, "ERROR:"
messages halt translation, and "Warning:" messages allow it to
continue. Mandatory diagnostics are far more likely to trigger
"ERROR:" messages than "Warning:" ones, but if an implementation chose
to continue translation and execution of a program after having
detected a situation where a diagnostic was mandatory, I wouldn't
expect an "ERROR:" message, only a "Warning:" message. If it also
generates an executable whose behavior conforms to all of the
standard's requirements that would be applicable if the diagnostic
were not mandatory, I can't imagine considering that a rejection, and
I can't imagine anyone else feeling that way either.
> ... If there is
> a syntax violation then a properly implemented parser
> will reject the source; and violation of constraints as
> C uses them to augment the grammar is in the same class.
Obviously, a properly implemented parser should generate the mandatory
diagnostic. However, if the implementor chooses to implement an
extension by attaching a meaning to a construct that is a syntax error
in standard C, I would not expect parsing to halt upon recognition of
that extension, and I would not expect the diagnostic to say
"ERROR:" (it might say "syntax error according to standard C".
I believe that there are rare situations that constitute constraint
violations, despite which the rest of the standard's requirements
remain clearly applicable. I know that you disagree with that
description, but I can describe the sames situations in a way that I
think we could both agree on. They are situations which constitute
constraint violations where the rest of the standard's requirements
would remain clearly applicable if the standard didn't identify them
as constraint violations. z++ where z is a complex variable ew
I don't think that syntax errors are comparable to constraint
violations in this regard. The concept of what the standard would
mean if a constraint were removed is, in rare cases, well defined. The
concept of what it would mean if something were not a syntax error is
not well defined, since it depends upon which way the syntax was re-
written to make it no longer a syntax error.
Keith Thompson
[...]
> An earlier message cross-references "the generic DP dictionary", but I
> don't know where to find that dictionary, I assumed it was a metaphor,
> and I would not have thought to make any connection between that
> metaphor and computational grammar.
C99 section 2 contains a list of "Normative references". One of them
is:
ISO/IEC 2382?1:1993, Information technology ? Vocabulary ? Part 1:
Fundamental terms.
[snip]
> I believe that there are rare situations that constitute constraint
> violations, despite which the rest of the standard's requirements
> remain clearly applicable. I know that you disagree with that
> description, but I can describe the sames situations in a way that I
> think we could both agree on. They are situations which constitute
> constraint violations where the rest of the standard's requirements
> would remain clearly applicable if the standard didn't identify them
> as constraint violations. z++ where z is a complex variable ew
And I believe that such situations are merely accidental.
If we assume that the behavior of any program that violates a
constraint is undefined, then any rules in the standard clearly would
not apply to a program that violates a constraint, including your
example of applying "++" to a complex number. The description of "++"
*seems* to apply to complex numbers, but only because a general
description was easier to write (and to read) than one that
specifically states *again* that "++" cannot be applied to complex
numbers.
If, on the other hand, we assume that a program that violates one
constraint (and happens to be "accepted") is still bound by the other
rules of the language, then I would expect to see some specific effort
to define the behavior of programs that violate constraints. Instead,
as far as I can tell, we see such definitions only in a few cases, and
only by accident. And I don't see that defining such behavior would
be at all useful. The implementation is allowed (and I'd say almost
but not quite encouraged) to reject programs that violate constraints.
What would be the point of guaranteeing such a program's behavior? No
programmer can safely depend on any such guarantee. If a constraint
violation is accepted as an extension, then the implementation must
document the behavior anyway. For example, if a compiler supports
"++" on complex numbers as an extension, it must document that it adds
1 to the value; it can't (or at least shouldn't) depend on the
standard's existing overly general description of "++".
But I'm arguing largely on the basis of what I think would make the
most sense, and I know that's a weak argument when interpreting the
standard.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Looking for software development work in the San Diego area.
james...@verizon.net
> james...@verizon.net writes:
...
> > I believe that there are rare situations that constitute constraint
> > violations, despite which the rest of the standard's requirements
> > remain clearly applicable. I know that you disagree with that
> > description, but I can describe the sames situations in a way that I
> > think we could both agree on. They are situations which constitute
> > constraint violations where the rest of the standard's requirements
> > would remain clearly applicable if the standard didn't identify them
> > as constraint violations. z++ where z is a complex variable ew
>
> And I believe that such situations are merely accidental.
Such cases are rare enough to make that a plausible assumption. In
which case, those holes should be plugged, too. If dropping a
constraint would leave a clear definition of reasonable behavior in
circumstances that violate that constraint, the constraint is probably
unnecessary. If the clearly defined behavior is unreasonable, it
should probably be modified.
This is on top of adding a clear statement that when a constraint is
violated, the behavior is undefined, except for the mandatory
diagnostic. The proper way to describe that in standardese for that
might be a bit of a problem, given the standard's definition of the
term "undefined behavior",
Keith Thompson
In my opinion, a clear statement that the behavior of a program that
violates a constraint (and is nevertheless accepted) is undefined is
the only change that's necessary. (Some might argue that the existing
definition of "constraint" already does that; IMHO, it doesn't.) If
that's done, I see no need to tighten the wording of any individual
requirements that happen to *appear* to define behavior in the
presence of constraint violations.
For example, the description of "++" says "the value 1 of the
appropriate type is added to it". This *would* be meaningful for
complex types if it weren't for the constraint; I see no need to make
the wording more complex to cover a case whose behavior would already
be undefined. Similarly, an implementation could provide an extension
that allows the value 1 to be added to a value of a struct type (but
might not allow "++" on structs); the description of "++" doesn't need
to be changed to address this.
As for whether this particular constraint is necessary, well, I
suppose it isn't (the language easily *could* have permitted "++" on
complex types), but I have no great problem with it, any more than I
object to disallowing ``x << 1'' to mean ``x / 2'' for floating-point
types. It's not necessary to permit *all* possible combinations of
operators and types for which a meaning can be established. A
language where everything is as orthogonal as possible might be a nice
thing (sort of like a natural language with entirely consistent
spelling and no irregular verbs), but C is not that language.