By Prasoon Saurav


2010-11-14 05:37:46 8 Comments

What are "sequence points"?

What is the relation between undefined behaviour and sequence points?

I often use funny and convoluted expressions like a[++i] = i;, to make myself feel better. Why should I stop using them?

If you've read this, be sure to visit the follow-up question Undefined behavior and sequence points reloaded.

(Note: This is meant to be an entry to Stack Overflow's C++ FAQ. If you want to critique the idea of providing an FAQ in this form, then the posting on meta that started all this would be the place to do that. Answers to that question are monitored in the C++ chatroom, where the FAQ idea started out in the first place, so your answer is very likely to get read by those who came up with the idea.)

5 comments

@Prasoon Saurav 2010-11-14 05:39:00

C++98 and C++03

This answer is for the older versions of the C++ standard. The C++11 and C++14 versions of the standard do not formally contain 'sequence points'; operations are 'sequenced before' or 'unsequenced' or 'indeterminately sequenced' instead. The net effect is essentially the same, but the terminology is different.


Disclaimer : Okay. This answer is a bit long. So have patience while reading it. If you already know these things, reading them again won't make you crazy.

Pre-requisites : An elementary knowledge of C++ Standard


What are Sequence Points?

The Standard says

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. (§1.9/7)

Side effects? What are side effects?

Evaluation of an expression produces something and if in addition there is a change in the state of the execution environment it is said that the expression (its evaluation) has some side effect(s).

For example:

int x = y++; //where y is also an int

In addition to the initialization operation the value of y gets changed due to the side effect of ++ operator.

So far so good. Moving on to sequence points. An alternation definition of seq-points given by the comp.lang.c author Steve Summit:

Sequence point is a point in time at which the dust has settled and all side effects which have been seen so far are guaranteed to be complete.


What are the common sequence points listed in the C++ Standard ?

Those are:

  • at the end of the evaluation of full expression (§1.9/16) (A full-expression is an expression that is not a subexpression of another expression.)1

    Example :

    int a = 5; // ; is a sequence point here
    
  • in the evaluation of each of the following expressions after the evaluation of the first expression (§1.9/18) 2

    • a && b (§5.14)
    • a || b (§5.15)
    • a ? b : c (§5.16)
    • a , b (§5.18) (here a , b is a comma operator; in func(a,a++) , is not a comma operator, it's merely a separator between the arguments a and a++. Thus the behaviour is undefined in that case (if a is considered to be a primitive type))
  • at a function call (whether or not the function is inline), after the evaluation of all function arguments (if any) which takes place before execution of any expressions or statements in the function body (§1.9/17).

1 : Note : the evaluation of a full-expression can include the evaluation of subexpressions that are not lexically part of the full-expression. For example, subexpressions involved in evaluating default argument expressions (8.3.6) are considered to be created in the expression that calls the function, not the expression that defines the default argument

2 : The operators indicated are the built-in operators, as described in clause 5. When one of these operators is overloaded (clause 13) in a valid context, thus designating a user-defined operator function, the expression designates a function invocation and the operands form an argument list, without an implied sequence point between them.


What is Undefined Behaviour?

The Standard defines Undefined Behaviour in Section §1.3.12 as

behavior, such as might arise upon use of an erroneous program construct or erroneous data, for which this International Standard imposes no requirements 3.

Undefined behavior may also be expected when this International Standard omits the description of any explicit definition of behavior.

3 : permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or with- out the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

In short, undefined behaviour means anything can happen from daemons flying out of your nose to your girlfriend getting pregnant.


What is the relation between Undefined Behaviour and Sequence Points?

Before I get into that you must know the difference(s) between Undefined Behaviour, Unspecified Behaviour and Implementation Defined Behaviour.

You must also know that 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.

For example:

int x = 5, y = 6;

int z = x++ + y++; //it is unspecified whether x++ or y++ will be evaluated first.

Another example here.


Now the Standard in §5/4 says

  • 1) 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.

What does it mean?

Informally it means that between two sequence points a variable must not be modified more than once. In an expression statement, the next sequence point is usually at the terminating semicolon, and the previous sequence point is at the end of the previous statement. An expression may also contain intermediate sequence points.

From the above sentence the following expressions invoke Undefined Behaviour:

i++ * ++i;   // UB, i is modified more than once btw two SPs
i = ++i;     // UB, same as above
++i = 2;     // UB, same as above
i = ++i + 1; // UB, same as above
++++++i;     // UB, parsed as (++(++(++i)))

i = (i, ++i, ++i); // UB, there's no SP between `++i` (right most) and assignment to `i` (`i` is modified more than once btw two SPs)

But the following expressions are fine:

i = (i, ++i, 1) + 1; // well defined (AFAIK)
i = (++i, i++, i);   // well defined 
int j = i;
j = (++i, i++, j*i); // well defined

  • 2) Furthermore, the prior value shall be accessed only to determine the value to be stored.

What does it mean? It means if an object is written to within a full expression, any and all accesses to it within the same expression must be directly involved in the computation of the value to be written.

For example in i = i + 1 all the access of i (in L.H.S and in R.H.S) are directly involved in computation of the value to be written. So it is fine.

This rule effectively constrains legal expressions to those in which the accesses demonstrably precede the modification.

Example 1:

std::printf("%d %d", i,++i); // invokes Undefined Behaviour because of Rule no 2

Example 2:

a[i] = i++ // or a[++i] = i or a[i++] = ++i etc

is disallowed because one of the accesses of i (the one in a[i]) has nothing to do with the value which ends up being stored in i (which happens over in i++), and so there's no good way to define--either for our understanding or the compiler's--whether the access should take place before or after the incremented value is stored. So the behaviour is undefined.

Example 3 :

int x = i + i++ ;// Similar to above

Follow up answer for C++11 here.

@user168715 2010-11-14 06:06:30

I don't understand the "Furthermore" part. Doesn't that make postfix ++ useless? For example, in the expression *p++ = 4, the prior value of p is being accessed both to determine the value to be stored in p (OK), and to determine the address of where to store the 4 (not OK?). But surely this common idiom isn't undefined behavior?

@Prasoon Saurav 2010-11-14 06:23:57

*p++ = 4 isn't Undefined Behaviour . *p++ is interpreted as *(p++). p++ returns p(a copy) and the value in stored at the previous address. Why would that invoke UB? It is perfectly fine.

@user168715 2010-11-14 08:38:42

@Prasoon: So returning a copy of p does not count as "accessing" the "prior value" of p? Why not? Does "access" here have a technical meaning?

@Prasoon Saurav 2010-11-14 09:11:46

@user168715 : Ok let me give you an example. For example i = i + i . Here we have 3 accesses of i. Here i is to be written within the same expression and all the accesses of i (One in LHS and 2 in RHS) are directly involved in computing the final value that has to be written. So it is fine. That means the prior values are accessed only to determine what has to be written.

@sbi 2010-11-14 09:19:47

@Mike: AFAIK, there are no (legal) copies of the C++ Standard you could link to.

@Mike DeSimone 2010-11-14 16:00:23

Well, then you could have a link to the ISO's relevant order page. Anyway, thinking about it, the phrase "elementary knowledge of C++ Standard" seems a bit of a contradiction in terms, since if you're reading the standard, you're past the elementary level. Maybe we could list what things in the language you need a basic understanding of, like expression syntax, order of operations, and maybe operator overloading?

@Inverse 2010-11-14 18:28:45

I'm not sure quoting the standard is the best way to teach newbies

@Nawaz 2010-12-01 13:11:29

@Prasoon... this is really good... I get all the revision at one place... thanks for creating this awesome topic... I've added it to my favorite. :-)

@sashang 2011-05-24 02:24:49

@Prasoon: There's a contradictory statement. Above example 1 it states 'legal expressions to those in which the accesses demonstrably precede the modification.' yet the comment in Example 1 contradicts this (unless the use of 'legal expression' above was only meant to be something that satisfies the parser and not also imply it was defined)

@aschepler 2011-05-24 03:52:29

Recommendation: Near the part that mentions the built-in comma operator has a sequence point, point out that the commas used to separate arguments to a function or elements in a braced initializer do not count as "comma operator".

@user72424 2011-07-11 08:07:25

@Prasoon : why is that i = (i,++i,++i); // Undefined Behaviour because there's no sequence point between ++i(right most) and assignment to i (i gets modified more than once b/w two SP) -> what i don't understand is that in your comments you just said there is no seq point btw i and ++i since (because = has no order of evaluation), but in parenthesis you said i gets modified between two SP . so what's actually true , whether SP exists or not?,

@Terminal 2011-07-12 11:07:29

@M3taSpl0it : The first sequence point is the second comma operator in the expression and the second sequence point is the semi-colon. The value of "i" is modified twice between these two sequence points.

@supercat 2011-07-12 19:22:01

@Terminal: The term "sequence point" refers to a local, rather than global, phenomenon. For example, in the statement a=(foo1(),foo2())+(bar1(),bar2()), there is a sequence point implying that foo1() is executed before foo2(), and likewise bar1() before bar2(), but there is no sequence point between any of the foo() calls and any of the bar() calls.

@Mr.Anubis 2011-07-15 18:22:49

@Terminal : ok let's take a example y = x++ = ++x; , as far as i know = doesn't define any sequence point , but due to right to left associativity this x++ = ++x; will be executed first , now tell me where are sequence points only in this (last expression) statement , so that i can say x is modified twice btw two consecutive sequence points

@Mr.Anubis 2011-07-15 18:27:08

@supercat : The term "sequence point" refers to a local, rather than global, phenomenon . i got the gist but can you explain more about this , and also my last question please , thanks

@supercat 2011-07-15 20:01:52

@Mr. Anubis: In thinking about sequencing, I would suggest that you write out statements using lots of temporary variables that are written at most once each, and is only read if written, such that each subexpression copies a real variable to a temp, copies a temp to a real variable, or acts between two or more temps. For example, "a=b+c" becomes "t1=b; t2=c; t3=t1+t2; a=t3;". Your example, assuming your second "=" was supposed to be "==", would become "t1=x; x=t1+1; t2=x+1; x=t2; t3=(t1==t2); x=t3;". A read of a temp must follow a write, but other than that things may happen "in parallel".

@supercat 2011-07-15 20:08:17

@Mr. Anubis: A sequence point would imply that all side-effects from the expression to the left must occur before any portion of the expression on the right is evaluated. Your expression contains no sequence points. A statement like "x=x+1;" would translate into "t1=x+1; x=t1;", and the read of t1 is guaranteed to happen after the write. If your expression were changed to use three different variables (and thus be legit code), it could be resequenced many different ways. Note also that it may be helpful to add a further expansion:

@supercat 2011-07-15 20:22:17

@Mr. Anubis: A statement like a=(expression) should be regarded as: t1=a; a=BOOM; t2=(expression); DEFUSE a; a=t2;" "Direct" references to a in the right hand side will be replaced with t1. Any attempt to access A via any other means between "a=BOOM" and "DEFUSE a" is an error which, as far as the standard is concerned, could blow up your computer or anything within fifty feet of it. I think it should be pretty clear that one should stand well away from your computer while executing your example.

@Bhavik Shah 2012-12-25 10:02:39

why i=i++ is undefined behaviour and i=i+1 is fine??

@Koushik Shetty 2013-04-04 06:25:28

@BhavikShah in i = i++ , i++ modifies i between sequence points and then again value is assigned to itself. butin i = i+1, i is accessed but only to read the Previous value and this value is added with 1 and then stored in ionly once its modified.

@Adrian 2013-06-24 19:20:54

I thought I understood sequence points as it relates to the comma operator but it looks like I'm mistaken. i = (i,++i,++i); is invalid and i = (++i,i++,i) is valid confuses me. Can you expand please?

@Kolyunya 2013-07-01 07:09:56

@Adrian The first expression invokes an UB because there is no sequence point between the last ++i and the assignement to i. The second expression does not invoke UB because expression i does not change the value of i. In the second example the i++ is followed by a sequence point (,) before the assignment operator is called.

@Adrian 2013-07-02 04:17:10

Ok,so am I correct that i = (++i, ++i, i) and i = (++i, ++i, i++) would be valid?

@Erik P. 2013-09-20 21:33:33

@Adrian Your first example, i = (++i, ++i, i), is valid - it consists of evaluating ++i (read/write); then there's a sequence point; evaluating ++i (r/w); sequence point; evaluating i (r); finally assigning the last result to i (w). Every write to i is isolated from others by a sequence point, and every read from i is also OK. In your second example, though, you get: evaluate ++i (r/w), sequence point, evaluate ++i (r/w), sequence point, evaluate i++ (r/w), assign result to i (w). Now there's two writes to i after the last sequence point: that violates §5/4 rule 1).

@Zeks 2014-01-14 15:46:09

This answer seems to conflict with Prasoon's answer on the point of i = ++i +1 . One gives us UB but other - that it is defined behaviour :) Explain pls

@Apriori 2014-06-18 18:17:19

@Prasoon Saurav: a common paradigm is to write code like int a, b, c = 0; a = b = c; However b is read from to assigned to a after it is written to (taking the value of c) with no sequence point in between. This would seem to violate "2) Furthermore, the prior value shall be accessed only to determine the value to be stored." and your explanation: "This rule effectively constrains legal expressions to those in which the accesses demonstrably precede the modification." I think assignment chaining is well defined and the quote from the standard correct, perhaps the explanation is wrong?

@gsamaras 2015-06-03 08:36:49

I find an expression difficult to understand, so I asked a question: stackoverflow.com/questions/30614396/what-does-i-i-i-1-1-do. Hope it helps.

@Don Larynx 2015-08-03 00:41:25

"In short, undefined behaviour means [...] your girlfriend getting pregnant." Er, no, not quite.

@Nishant 2015-09-06 10:32:00

in ++i = 2 ,++ has got precedence over =. So for i++ will be executed theh i=2 will be executed. And the final value of i will be 2. Now I cannot see any other execution path for this expression. Hence it should not be unspecified or undefined. I do understand the in the expression i is being assigned twice in between two sequence points, hence it should have unspecified or undefined behavior. But logically I can think of only one execution path, i.e, the behavior is fixed.

@Dovahkiin 2016-08-05 21:35:34

Although in practice, UB causing my girlfriend to get pregnant hasn't yet been observed... :)

@Debashish 2016-09-29 16:17:22

a = i+++j ? UB or well defined ? I think well defined.

@bumfo 2016-11-07 09:59:06

@user168715 In C11, "The value computations of the operands of an operator are sequenced before the value computation of the result of the operator. ", thus in *p++, * is sequenced after p++. I think in C++ it is almost the same :p

@awiebe 2018-10-26 03:40:09

In C99(ISO/IEC 9899:TC3) which seems absent from this discussion thus far the following steteents are made regarding order of evaluaiton.

[...]the order of evaluation of subexpressions and the order in which side effects take place are both unspecified. (Section 6.5 pp 67)

The order of evaluation of the operands is unspecified. If an attempt is made to modify the result of an assignment operator or to access it after the next sequence point, the behavior[sic] is undefined.(Section 6.5.16 pp 91)

@Jonathan Leffler 2018-11-30 05:34:12

The question is tagged C++ and not C, which is good because the behaviour in C++17 is quite different from the behaviour in older versions — and bears no relation to the behaviour in C11, C99, C90, etc. Or bears very little relation to it. On the whole, I'd suggest removing this. More significantly, we need to find the equivalent Q&A for C and make sure it is OK (and notes that C++17, in particular, changes the rules — the behaviour in C++11 and before was more or less the same as in C11, though the verbiage describing it in C still uses 'sequence points' whereas C++11 and later does not.

@AlexD 2017-09-12 08:50:14

C++17 (N4659) includes a proposal Refining Expression Evaluation Order for Idiomatic C++ which defines a stricter order of expression evaluation.

In particular, the following sentence was added:

8.18 Assignment and compound assignment operators:
....

In all cases, the assignment is sequenced after the value computation of the right and left operands, and before the value computation of the assignment expression. The right operand is sequenced before the left operand.

It makes several cases of previously undefined behavior valid, including the one in question:

a[++i] = i;

However several other similar cases still lead to undefined behavior.

In N4140:

i = i++ + 1; // the behavior is undefined

But in N4659

i = i++ + 1; // the value of i is incremented
i = i++ + i; // the behavior is undefined

Of course, using a C++17 compliant compiler does not necessarily mean that one should start writing such expressions.

@Prasoon Saurav 2010-11-15 11:12:25

This is a follow up to my previous answer and contains C++11 related material..


Pre-requisites : An elementary knowledge of Relations (Mathematics).


Is it true that there are no Sequence Points in C++11?

Yes! This is very true.

Sequence Points have been replaced by Sequenced Before and Sequenced After (and Unsequenced and Indeterminately Sequenced) relations in C++11.


What exactly is this 'Sequenced before' thing?

Sequenced Before(§1.9/13) is a relation which is:

between evaluations executed by a single thread and induces a strict partial order1

Formally it means given any two evaluations(See below) A and B, if A is sequenced before B, then the execution of A shall precede the execution of B. If A is not sequenced before B and B is not sequenced before A, then A and B are unsequenced 2.

Evaluations A and B are indeterminately sequenced when either A is sequenced before B or B is sequenced before A, but it is unspecified which3.

[NOTES]
1 : A strict partial order is a binary relation "<" over a set P which is asymmetric, and transitive, i.e., for all a, b, and c in P, we have that:
........(i). if a < b then ¬ (b < a) (asymmetry);
........(ii). if a < b and b < c then a < c (transitivity).
2 : The execution of unsequenced evaluations can overlap.
3 : Indeterminately sequenced evaluations cannot overlap, but either could be executed first.


What is the meaning of the word 'evaluation' in context of C++11?

In C++11, evaluation of an expression (or a sub-expression) in general includes:

  • value computations (including determining the identity of an object for glvalue evaluation and fetching a value previously assigned to an object for prvalue evaluation) and

  • initiation of side effects.

Now (§1.9/14) says:

Every value computation and side effect associated with a full-expression is sequenced before every value computation and side effect associated with the next full-expression to be evaluated.

  • Trivial example:

    int x; x = 10; ++x;

    Value computation and side effect associated with ++x is sequenced after the value computation and side effect of x = 10;


So there must be some relation between Undefined Behaviour and the above-mentioned things, right?

Yes! Right.

In (§1.9/15) it has been mentioned that

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced4.

For example :

int main()
{
     int num = 19 ;
     num = (num << 3) + (num >> 3);
} 
  1. Evaluation of operands of + operator are unsequenced relative to each other.
  2. Evaluation of operands of << and >> operators are unsequenced relative to each other.

4: In an expression that is evaluated more than once during the execution of a program, unsequenced and indeterminately sequenced evaluations of its subexpressions need not be performed consistently in different evaluations.

(§1.9/15) The value computations of the operands of an operator are sequenced before the value computation of the result of the operator.

That means in x + y the value computation of x and y are sequenced before the value computation of (x + y).

More importantly

(§1.9/15) If a side effect on a scalar object is unsequenced relative to either

(a) another side effect on the same scalar object

or

(b) a value computation using the value of the same scalar object.

the behaviour is undefined.

Examples:

int i = 5, v[10] = { };
void  f(int,  int);
  1. i = i++ * ++i; // Undefined Behaviour
  2. i = ++i + i++; // Undefined Behaviour
  3. i = ++i + ++i; // Undefined Behaviour
  4. i = v[i++]; // Undefined Behaviour
  5. i = v[++i]: // Well-defined Behavior
  6. i = i++ + 1; // Undefined Behaviour
  7. i = ++i + 1; // Well-defined Behaviour
  8. ++++i; // Well-defined Behaviour
  9. f(i = -1, i = -1); // Undefined Behaviour (see below)

When calling a function (whether or not the function is inline), every value computation and side effect associated with any argument expression, or with the postfix expression designating the called function, is sequenced before execution of every expression or statement in the body of the called function. [Note: Value computations and side effects associated with different argument expressions are unsequenced. — end note]

Expressions (5), (7) and (8) do not invoke undefined behaviour. Check out the following answers for a more detailed explanation.


Final Note :

If you find any flaw in the post please leave a comment. Power-users (With rep >20000) please do not hesitate to edit the post for correcting typos and other mistakes.

@TemplateRex 2012-07-21 21:47:50

Instead of "asymmetric", sequenced before / after are "antisymmetric" relations. This should be changed in the text to conform to the definition of a partial order given later (which also agrees with Wikipedia).

@Mikhail 2014-03-18 12:04:24

Why is 7) item in the last example an UB? Maybe it should be f(i = -1, i = 1)?

@Mikhail 2014-03-18 12:16:26

Here is the nice explanation: stackoverflow.com/a/21671069

@ThomasMcLeod 2014-06-24 20:52:40

I fixed the description of the "sequenced before" relation. It is a strict partial order. Obviously, an expression cannot be sequenced before itself, so the relation cannot be reflexive. Hence it is asymmetric not anti-symmetric.

@v.oddou 2015-01-09 06:31:22

5) being well befined blew my mind off. the explanation by Johannes Schaub wasn't entirely straightforward to get. Especially because I believed that even in ++i (being value evaluated before the + operator that is using it), the standard still doesn't say that its side effect must be finished. But in fact, because it returns an ref to a lvalue which is i itself, it MUST have finished the side effect since the evaluation must be finished, therefore the value must be up to date. This was the crazy part to get in fact.

@M.M 2015-05-25 21:45:59

"The ISO C++ Committee members thought that Sequence Points stuffs were quite difficult to understand. So they decided to replace it with the above mentioned relations just for more clear wording and enhanced preciseness." - have you got a reference for that claim? It seems to me that the new relations are harder to understand.

@Don Larynx 2015-08-04 00:49:01

How does ++++i produce defined but ++++++i produce UB?

@Ben Voigt 2015-09-18 22:15:45

@M.M: I think surely the new terminology must be related to introduction of a standardized threading model, and not for ease of comprehension.

@MikeMB 2016-01-14 00:21:40

@DonLarynx: Why do you think ++++++i is UB?

@vonbrand 2016-02-20 04:02:31

There is a "Bahaviour" in there...

@Debashish 2016-09-29 16:11:53

a = i+++j is it well defined ?

@Peter A. Schneider 2018-09-21 12:48:42

I'd love to see the left side of the assignment replaced by an unrelated variable (say a) in cases where the UB comes from the side effect and unsequenced reading on the right side. Example: a = ++i + ++i; would still be UB, unless I'm mistaken.

@eral 2019-09-09 12:40:23

can you please explain the difference between 4 and 5 in the examples?

@Yttrill 2010-12-07 19:44:51

I am guessing there is a fundamental reason for the change, it isn't merely cosmetic to make the old interpretation clearer: that reason is concurrency. Unspecified order of elaboration is merely selection of one of several possible serial orderings, this is quite different to before and after orderings, because if there is no specified ordering, concurrent evaluation is possible: not so with the old rules. For example in:

f (a,b)

previously either a then b, or, b then a. Now, a and b can be evaluated with instructions interleaved or even on different cores.

@supercat 2010-12-09 20:35:51

I believe, though, that if either 'a' or 'b' includes a function call, they are indeterminately sequenced rather than unsequenced, which is to say that all side-effects from one are required to occur before any side-effects from the other, although the compiler need not be consistent about which one goes first. If that is no longer true, it would break a lot of code which relies upon the operations not overlapping (e.g. if 'a' and 'b' each set up, use, and take down, a shared static state).

Related Questions

Sponsored Content

5 Answered Questions

[SOLVED] Iterator invalidation rules

3 Answered Questions

32 Answered Questions

7 Answered Questions

6 Answered Questions

[SOLVED] How does the compilation/linking process work?

5 Answered Questions

[SOLVED] How do I use arrays in C++?

2 Answered Questions

[SOLVED] Object destruction in C++

7 Answered Questions

2 Answered Questions

[SOLVED] What does it mean to have an undefined reference to a static member?

  • 2011-08-17 12:27:53
  • Mankarse
  • 8736 View
  • 18 Score
  • 2 Answer
  • Tags:   c++ c++-faq

Sponsored Content