A finer-grained alternative to sequence points

For some years it has been known and acknowledged that the words describing the sequencing of operations in the C and C++ standards, mainly using the term "sequence point", are really not adequate. The C committee has more than once tried to find a better description, but those attempts have come to little.

According to my best guesses, there are at least two factors which have inhibited progress in the C committee:

• WG14 seems collectively to believe that the problem is not urgent or compelling; that most implementers and experts understand the situation well enough to agree on the essentials of the requirements, and that most of the confusion can be treated as an education problem (not within the committee's scope).
• Most of the proposals to clarify matters are so radical that they are (rightly) met with considerable suspicion, and (accurately) judged to require much deep consideration to ensure that they don't constitute an unacceptable change to the status quo.

For at least two reasons, the problem is more urgent for C++.

• In the first place, we are planning to support concurrency in our upcoming revision. A rigorous definition of sequencing in the context of a single thread is an essential prerequisite for any definition of concurrent semantics.
• Even without concurrency, C++ has more sequencing issues than C. For example, core issue 222 is a case where C++ needs to say more about sequencing than C does, because an assignment-expression yields an lvalue instead of an rvalue.

Although this is the sort of issue for which WG21 has generally deferred to WG14, if WG14 does not make progress in this area soon, WG21 may have no alternative but to take the initiative.

This paper outlines my thoughts about the problems with sequence points, and how they might be solved. The purpose is not to make any technical changes, but to achieve a better description (and understanding) of the status quo. This is of course based on my own understanding of the status quo. If anyone thinks I am proposing unacceptable technical changes, that would be a reflection on the lack of clarity and/or specificity of the existing words. The perspective is principally that of the C++ standard, but most of my proposals apply almost equally well to C.

Each section below begins with a citation from the standard, and ends with an indication of the direction I think should be taken. At this stage, I make no pretense of having finely polished standardese; first I want to get reactions to the direction I am suggesting. However, I do believe this paper presents a fairly complete and cohesive proposal.

1.9p7: The definition of "sequence point"

Accessing an object designated by a volatile lvalue (3.10), modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression might produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place.

When reading this statement, two qualifications must be kept in mind:

• Not every side effect or evaluation can be authoritatively determined to be either previous to or subsequent to a given sequence point. For example, given

  a = 0;
  b = (a = 1, 2*a) + 3*a;

  The evaluation of 3*a is not ordered with respect to the sequence point introduced by the comma operator. It may be previous or subsequent; the standard simply doesn't say. Therefore, that evaluation may or may not be separated from the assignment by a sequence point.

  It is clear from the C++ standard (specifically, from the last sentence of 5p4, q.v. below) that this example has undefined behavior. However, the C standard lacks any similar statement, so the intention is far less clear. But it is crucially important to have unambiguous rules by which we can determine whether a given example is well-defined or undefined.

  In any event, because of the partially-ordering nature of sequence points, any reference to the operations falling between the previous and next sequence point is ambiguous — it's not always possible to tell what is and is not included in that set. In fact, because sequence points are themselves only partially ordered, any reference at all to "the" previous or next sequence point is ambiguous. Unfortunately, the C standard contains several such references. Fortunately, there are fewer in the C++ standard.

• The statement is talking about the abstract machine, and is therefore subject to the as-if rule. For example, given

  int a = 0, b = 0;
  a = 1;
  b = 2;

  There need not be any point in the execution of the "concrete" machine at which a can be observed to be 1 and b can be observed to be 0, because in this example a and b are not both volatile. In other words, a state corresponding to the sequence point need not actually occur within the "concrete" machine. If a and b were both volatile, there would have to be an interval between (a = 1) and (b = 2) — but that interval, however small, would still have duration, and therefore would not actually be a "point". One could, of course, choose a point in that interval, and think of it as "the" sequence point; but the selection would necessarily be arbitrary, most especially if any machine instructions are executed between the instructions implementing the volatile assignments.

For these reasons, I do not think of a sequence point as an event (in the concrete machine). Events in the concrete machine are such things as loads (evaluations) and stores (side effects) — transactions which are observable on some machine bus. A sequence point is certainly not an event in that sense.

I think that some (possibly much) of the confusion about sequence points is caused by thinking of them as events. Considering the example under the first bullet above, if the sequence point is considered to be a concrete event, then it must occur either before or after (or possibly concurrent with) other events in the concrete machine, and therefore may wind up between two events which the user wants to be separated by a sequence point, thereby preventing undefined behavior. The logic seems valid, but the conclusion is not, because the first example above is really supposed to have undefined behavior. So there must be a problem with a premise. QED

Instead, I think sequence points are nothing more than an editorial mechanism for sequencing constraints on events. And I think that those constraints could be expressed more precisely — and possibly even more clearly — without that specific editorial mechanism.

So for starters, I propose simply to delete the sentence defining the term "sequence point". I propose instead to explicitly spell out where necessary the meaning of "sequence point": that side effects and evaluations associated with one expression or subexpression are constrained to be sequenced before those associated with another expression.

Note that sequencing is an asymmetric pair-wise relation between program events; an event A may be sequenced before event B, or B may be sequenced before A, or they may not be relatively sequenced at all.

1.9p9: Asynchronous signals

When the processing of the abstract machine is interrupted by receipt of a signal, the values of objects with type other than volatile std::sig_atomic_t are unspecified, and the value of any object not of volatile std::sig_atomic_t that is modified by the handler becomes undefined.

First, let's consider the corresponding statement from the C standard (5.1.2.3p4):

When the processing of the abstract machine is interrupted by receipt of a signal, only the values of objects as of the previous sequence point may be relied on. Objects that may be modified between the previous sequence point and the next sequence point need not have received their correct values yet.

This statement explicitly refers to the abstract machine. From that fact it might be possible to conclude that no actual requirement is imposed on the concrete machine; in other words, that this statement is vacuous. Additionally, this statement is in conflict with 7.14.1.1p5, which basically states that a signal handler can't even access any object (except to assign to a volatile sig_atomic_t object), much less rely on its value. In any event, the references to "the" previous and "the" next sequence point are ambiguous, because of the partially-ordered nature of sequence points. Bottom line: the statement from the C standard is misleading at best, nonsensical at worst.

The corresponding statement from the C++ standard, however, is correct. It's even correct of the concrete machine, and so needn't refer specifically to the abstract machine. Technically, there is also a conflict with 7.14.1.1p5 from the C standard, in the implication that an asynchronous signal handler may use the value of a volatile sig_atomic_t object, and not just assign to it. However, I believe that this should be considered well-defined, and the standard should say so explicitly.

(This is included primarily as an example of how bad the sequence point situation really is in the C standard.)

1.9p11: The "least requirements"

The least requirements on a conforming implementation are:

• At sequence points, volatile objects are stable in the sense that previous evaluations are complete and subsequent evaluations have not yet occurred.

The sense of this constraint is simply that, in the "concrete" machine, the sequence of accesses to volatile objects is constrained exactly as in the abstract machine. It should be possible to say so in basically those words, without reference to sequence points. Consider these words from the description of volatile in the C standard (6.7.3p6):

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. ...

I propose this replacement:

The least requirements on a conforming implementation are:

• Accesses to volatile objects occur strictly according to the rules of the abstract machine.

1.9p12: The definition of "full-expression"

A full-expression is an expression that is not a subexpression of another expression. If a language construct is defined to produce an implicit call of a function, a use of the language construct is considered to be an expression for the purposes of this definition. Conversions applied to the result of an expression in order to satisfy the requirements of the language construct in which the expression appears are also considered to be part of the full-expression.

I think we will also want to add something like this:

A call to a destructor generated at the end of the lifetime of an object other than a temporary object is an implicit full-expression.

This will give us a guarantee that the destruction of non-temporary object does not interleave with anything else.

1.9p15: Full-expressions

There is a sequence point at the completion of evaluation of each full-expression.

[Footnote: As specified in 12.2, after the "end-of-full-expression" sequence point, a sequence of zero or more invocations of destructor functions for temporary objects takes place, usually in reverse order of the construction of each temporary object. — end footnote]

The proposed change here is to spell out what sequence point means:

All evaluations and side effects associated with a full-expression are sequenced before all evaluations and side effects associated with the next full-expression to be evaluated.

[Footnote: As specified in 12.2, after a full-expression is evaluated, a sequence of zero or more invocations of destructor functions for temporary objects takes place, usually in reverse order of the construction of each temporary object. — end footnote]

It may be felt that it is hand-waving to refer to "the next full-expression to be evaluated", when what we are mainly trying to do is to nail down sequencing requirements (i.e. what is required/allowed to be "next"). On the other hand, my proposed wording certainly does no more hand-waving than the previous wording. But more importantly, I think that the specification of the sequence of evaluations of full-expressions should be considered a "higher-level protocol", and specified elsewhere — which for the most part, it already is. The important thing here is to specify that evaluations of different full-expressions do not interleave.

These are the only contexts in which a full-expression (other than a constant-expression) can appear:

statement

Sequencing constraints are already described in chapter 6.

parameter-declaration (default argument)

For evaluation and sequencing purposes, a default argument expression is considered to be part of the expression that triggers its evaluation; see 1.9p13.

initializer (parenthesized list)

For evaluation and sequencing purposes, all expressions in a parenthesized initializer are considered to be part of a larger full-expression, which performs the overall initialization; see 1.9p12.

initializer-clause (brace-enclosed list)

I am unable to find any words in 8.5 which define or constrain the sequencing of evaluations or side effects of expressions in an aggregate initializer. This is almost certainly an oversight which needs to be fixed.

It is interesting to note that in C99, side effects of the various expressions of an aggregate initializer occur in unspecified order. This is presumably motivated by designated initializers, which enable sub-object initialization order to differ from lexical order.

Because of uncertainty as to what the constraints should be, and because it's not obvious in what paragraph they should be expressed, I leave this as an exercise for the future.

mem-initializer

Again, the various expressions of a mem-initializer are combined into a larger full-expression to initialize the member or base class. The sequencing of those full-expressions is specified in 12.6.2p5.

template-argument

I am inclined to believe that this is a mistake — that a template-argument should really be a constant-expression — so for the time being I ignore this possibility.

It should also be noted that 3.6.2 has much to say about the order of initialization of namespace-scope objects, and uses the terms "ordered" and "unordered". The concept of unordered initialization should not be confused with the concept of unsequenced evaluation. Unsequenced evaluations may interleave, and result in undefined behavior if, for example, a single scalar object is modified in both. Unordered initializations may not interleave; the result may be unspecified, but is not undefined, even if a single scalar object is modified in both. Unordered initializations are relatively sequenced, but the sequence is unspecified.

1.9p16 et al.: Function calls

When calling a function (whether or not the function is inline), there is a sequence point after the evaluation of all function arguments (if any) which takes place before execution of any expressions or statements in the function body. There is also a sequence point after the copying of a returned value and before the execution of any expressions outside the function. Several contexts in C++ cause evaluation of a function call, even though no corresponding function call syntax appears in the translation unit. [Example: evaluation of a new expression invokes one or more allocation and constructor functions; see 5.3.4. For another example, invocation of a conversion function (12.3.2) can arise in contexts in which no function call syntax appears. —end example] The sequence points at function-entry and function-exit (as described above) are features of the function calls as evaluated, whatever the syntax of the expression that calls the function might be.

Also 1.9p8:

Once the execution of a function begins, no expressions from the calling function are evaluated until execution of the called function has completed.

[Footnote: In other words, function executions do not "interleave" with each other. — end footnote]

Also 5.2.2p10:

The order of evaluation of arguments is unspecified. All side effects of argument expression evaluations take effect before the function is entered. The order of evaluation of the postfix expression and the argument expression list is unspecified.

There is obviously considerable redundancy among these paragraphs. I'm not going to bother here to untangle editorially exactly what should be said where, but I propose to formulate the sum of the sequencing constraints expressed in them along these lines:

All evaluations and side effects associated with the postfix expression designating the function to call, and with any argument expressions, are sequenced before the execution of the called function (whether or not the function is inline). [Note: Side effects and evaluations from different argument expressions are not sequenced relative to one another. —end note] The execution of the called function is sequenced before any further operation of the calling function. [Note: In other words, function executions do not "interleave" with each other. —end note] ... The sequencing constraints on the execution of the function are features of the function calls as evaluated, regardless of the syntax of the expression that calls the function.

1.9p17: Sequence points within expressions

In the evaluation of each of the expressions

a && b
a || b
a ? b : c
a , b

using the built-in meaning of the operators in these expressions (5.14, 5.15, 5.16, 5.18), there is a sequence point after the evaluation of the first expression.

I'm not quite sure why this paragraph is here; it is (or ought to be) redundant with the forward-referenced descriptions of the operators in question. Here I simply call this out as an editorial question, rather than ignoring it completely.

5p4: Undefined behavior

Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified. Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be accessed only to determine the value to be stored. The requirements of this paragraph shall be met for each allowable ordering of the subexpressions of a full expression; otherwise the behavior is undefined.

Again, because sequence points are only partially ordered, the references to "the" previous and next sequence points are ambiguous at best. I suggest that this statement would be better expressed along the following lines:

Except where noted, the order of evaluation of operands of individual operators and sub-expressions of individual expressions, and the order in which side effects take place, are not relatively sequenced. If two modifications of a single scalar object are not relatively sequenced, the behavior is undefined. If a use of the value of and a modification of a single scalar object are not relatively sequenced, the behavior is undefined.

With this formulation, I believe that the statement about "each allowable ordering" is no longer necessary — but of course opinions may differ.

Also, it should be noted that problems have been discovered with the formulation "the prior value shall be accessed only to determine the value to be stored." The strictest interpretation of those words would outlaw any use of the value of a post-increment expression, since the prior value is also used to determine the value of the expression. There is also a problem with (a[a[0]] = x), where the prior value of a[0] is zero. In that case, the prior value is used to determine the identity of the object to be assigned, which the existing words do not allow.

I think I have discovered an alternate way to express the desired constraint; see the discussion of assignment below (5.17p1).

5.2.6p1: Post-increment

The value obtained by applying a postfix ++ is the value that the operand had before applying the operator. [Note: the value obtained is a copy of the original value —end note] The operand shall be a modifiable lvalue. The type of the operand shall be an arithmetic type or a pointer to a complete object type. After the result is noted, the value of the object is modified by adding 1 to it, unless the object is of type bool, in which case it is set to true. [Note: this use is deprecated, see Annex D. —end note] The result is an rvalue. The type of the result is the cv-unqualified version of the type of the operand. See also 5.7 and 5.17.

Note that there is here a necessary sequencing constraint, which is not specified in terms of a sequence point: the modification must follow the evaluation.. For editorial purposes it is instructive to compare the words in the C++ standard to the corresponding words from C (6.5.2.4p2):

The result of the postfix ++ operator is the value of the operand. After the result is obtained, the value of the operand is incremented. ... The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point.

The formulation I would propose for the sequencing constraints goes something like this:

The value of the postfix ++ expression is the value of the operand. ... The value of the operand is incremented by 1, unless the object is of type bool, in which case it is set to true. The evaluation of the ++ expression is sequenced before the modification of the operand. ...

(For the explanation of a subtle detail here, see the discussion of assignment (5.17p1) below.)

5.14p1-2: Logical AND expression

The && operator groups left-to-right. The operands are both implicitly converted to type bool (clause 4). The result is true if both operands are true and false otherwise. Unlike &, && guarantees left-to-right evaluation: the second operand is not evaluated if the first operand is false.

The result is a bool. All side effects of the first expression except for destruction of temporaries (12.2) happen before the second expression is evaluated.

It should be noted that the term "sequence point" does not appear here; instead its definition is already (at least partially) spelled out. And paragraph 1 doesn't really talk about sequencing. So the only thing we need to do is to tighten up the definition in paragraph 2:

The result is a bool. If the second expression is evaluated, all side effects and evaluations associated with the first expression are sequenced before all side effects and evaluations associated with the second expression.

Obviously, the changes for logical AND would be exactly analogous. See 12.2 below for details of the handling of temporaries.

5.16p1: Conditional expression

Conditional expressions group right-to-left. The first expression is implicitly converted to bool (clause 4). It is evaluated and if it is true, the result of the conditional expression is the value of the second expression, otherwise that of the third expression. All side effects of the first expression except for destruction of temporaries (12.2) happen before the second or third expression is evaluated. Only one of the second and third expressions is evaluated.

The problem and solution here are very similar to the logical-and expression immediately above:

... Only one of the second or third expressions is evaluated. All side effects and evaluations associated with the first expression are sequenced before all side effects and evaluations associated with the second or third expression.

5.17p1: Assignment

The assignment operator (=) and the compound assignment operators all group right-to-left. All require a modifiable lvalue as their left operand and return an lvalue with the type and value of the left operand after the assignment has taken place. The result in all cases is a bit-field if the left operand is a bit-field.

Here again is a sequencing constraint that is necessary, but is not expressed in terms of a sequence point. I propose:

The assignment operator(=) and the compound assignment operators all group right-to-left. All require a modifiable lvalue as their left operand and return the left operand as an lvalue. The result in all cases is a bit-field if the left operand is a bit-field. In all cases, the assignment is sequenced after the evaluation of the left and right operands, and before the evaluation of the assignment expression.

It is extremely important to note here that the assignment is not sequenced after any side effects of the operands, but only after their evaluation. That is why, when I propose words to spell out the definition of a sequence point, I tediously refer to both evaluations and side effects; so that it is also possible to express weaker sequencing constraints. I used the same trick above in my proposal for post-increment.

There is room here for a clarifying footnote along these lines:

Because the evaluation of the assignment expression follows the assignment, if it is converted to an lvalue, the result is the value assigned.

Also note that I have added a new constraint: the assignment can't be done until both operands are evaluated. Although it would seem to be pointless to say this (causality more or less requires it, after all), I believe that by saying so explicitly we can eliminate the need for the troublesome words from 5p4: "the prior value shall be accessed only to determine the value to be stored." In the new formulation of 5p4, the behavior is undefined only if a use and a modification of a single scalar object are not relatively sequenced. If we insist that the evaluation of both sides of the assignment are sequenced before the assignment, then any use of the prior value in either of those operands is sequenced before the assignment, so there is no undefined behavior.

5.18p1: Comma expressions

A pair of expressions separated by a comma is evaluated left-to-right and the value of the left expression is discarded. The lvalue-to-rvalue (4.1), array-to-pointer (4.2), and function-to-pointer (4.3) standard conversions are not applied to the left expression. All side effects (1.9) of the left expression, except for the destruction of temporaries (12.2), are performed before the evaluation of the right expression. The type and value of the result are the type and value of the right operand; the result is an lvalue if its right operand is an lvalue, and is a bit-field if its right operand is an lvalue and a bit-field.

Again, all that is required here is to substitute the correct and complete definition of "sequence point":

... All evaluations and side effects associated with the left operand are sequenced before all evaluations and side effects associated with the right operand. ...

12.2p3-5: Destruction of temporaries

When an implementation introduces a temporary object of a class that has a non-trivial constructor (12.1, 12.8), it shall ensure that a constructor is called for the temporary object. Similarly, the destructor shall be called for a temporary with a non-trivial destructor (12.4). Temporary objects are destroyed as the last step in evaluating the full-expression (1.9) that (lexically) contains the point where they were created. This is true even if that evaluation ends in throwing an exception.

There are two contexts in which temporaries are destroyed at a different point than the end of the full-expression. The first context is when a default constructor is called to initialize an element of an array. If the constructor has one or more default arguments, any temporaries created in the default argument expressions are destroyed immediately after return from the constructor.

The second context is when a reference is bound to a temporary. The temporary to which the reference is bound or the temporary that is the complete object of a subobject to which the reference is bound persists for the lifetime of the reference except as specified below. ... In all these cases, the temporaries created during the evaluation of the expression initializing the reference, except the temporary to which the reference is bound, are destroyed at the end of the full-expression in which they are created and in the reverse order of the completion of their construction. If the lifetime of two or more temporaries to which references are bound ends at the same point, these temporaries are destroyed at that point in the reverse order of the completion of their construction. In addition, the destruction of temporaries bound to references shall take into account the ordering of destruction of objects with static or automatic storage duration (3.7.1, 3.7.2); that is, if obj1 is an object with static or automatic storage duration created before the temporary is created, the temporary shall be destroyed before obj1 is destroyed; if obj2 is an object with static or automatic storage duration created after the temporary is created, the temporary shall be destroyed after obj2 is destroyed.

I think we need to add a statement like this, probably to paragraph 3:

The side effects and evaluations of destroying a temporary object are associated only with the full-expression, not with any specific sub-expression.

The words used for sequencing events of a full-expression, and of operands of a sequencing operator, refer to side effects and evaluations "associated with" an expression. This addition makes it clear that a temporary object is destroyed at the end of the full-expression, and no earlier, even if a sequencing operator is present.

In paragraph 4, we may want to say something like this:

If the constructor has one or more default arguments, the destruction of any temporary created in a default argument expression is sequenced before the construction of the next array element, if any.

Because the destruction of temporaries is associated with the containing full-expression, any temporary created during the construction of the last array element will still be destroyed.

In paragraph 5, I would recommend words along these lines:

The destruction of a temporary whose lifetime is not extended by being bound to a reference is sequenced before the destruction of any temporary which was constructed earlier in the same full-expression.

12.6.2p3:

There is a sequence point (1.9) after the initialization of each base and member. The expression-list of a mem-initializer is evaluated as part of the initialization of the corresponding base or member.

If the initialization is defined as a full-expression (which it surely should be), the necessary sequencing implications come along for free:

The initialization of each base and member constitutes a full-expression. Any expression in a mem-initializer is evaluated as part of the full-expression that performs the initialization.