yohhoyの日記

技術的メモをしていきたい日記

i = i++ + 1;の評価順規定

プログラミング言語C++における評価順規定の変遷についてメモ*1。本記事では代入+前置/後置インクリメント*2+加算演算子*3 *4を扱う。

注意:本記事は言語仕様の隅をつつく話題であり、一般論として同一オブジェクトに対する複数回の副作用を伴う式文は避けるべき。sequenced-before関係ルールを覚えてまで際どいコードを書くほど人生は長くないはず。

int i = 0;

i = ++i + 1;  // [A] C++03以前: undefined behavior, C++11以降: well-defined
i = i++ + 1;  // [B] C++14以前: undefined behavior, C++1z以降: well-defined
i = ++i + i;  // [C] C++98/03/11/14/1z全てでundefined behavior

C++98/03仕様

前掲コード式文[A], [B], [C]は、2つの副作用完了点(sequence point)間で同一オブジェクトを複数回変更するため、いずれも未定義動作(undefined behavior)を引き起こす。C++03 1.9/p7,16, 5/p4*5より引用(下線部は強調)。

7 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.

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

4 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. [Example:

i = v[i++];       // the behavior is undefined
i = 7, i++, i++;  // i becomes 9

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

-- end example]

C++11/14仕様

C++11以降のC++言語仕様では、C++03以前の副作用完了点による定義を廃止し、評価(evaluation)間のsequenced-before関係によって評価順を規定する。また、評価(evaluation)は「値の計算(value computation; vc)」と「副作用(side effect; se)の開始」に区分される。*6

下記理由により前掲コード式文[A]のみwell-definedとなり、[B], [C]は未定義動作を引き起こす。

  • 式文[A] i = ++i + 1;:前置インクリメント++iは複合代入演算i+=1と等価なため、式文i = (i+=1) + 1;として解釈する(5.3.2/p1)。a1)部分式i+=1によるse は a2)部分式i+=1全体のvc より前に順序付けられ(5.17/p1)、a2)+演算子オペランドのvc は a3)部分式(i+=1) + 1全体のvc より前に順序付けられ(1.9/p15)、a3)=演算子オペランドのvc は a4)代入操作によるse より前に順序付けられる(5.17/p1)。以上より a1) sequenced-before a2) かつ a2) sequenced-before a3) かつ a3) sequenced-before a4)となり、sequenced-before関係の推移律より“a1)前置++演算子によるse” sequenced-before “a4)代入演算子によるse”が導出される(1.9/p13)。同一オブジェクトへのside effects間にsequenced-beforeが成立するため、式文[A]はwell-definedとなる。
  • 式文[B] i = i++ + 1;:b1)部分式i++のvc は b2)後置++演算子によるse より前に順序付けられる(5.2.6/p1)。また b1)+演算子オペランドのvc は b3)部分式i++ + 1全体のvc より前に順序付けられ(1.9/p15)、b3)=演算子オペランドのvc は b4)代入操作によるse より前に順序付けられる(5.17/p1)。以上より b1) sequenced-before b2) かつ b1) sequenced-before b3) かつ b3) sequenced-before b4)となり、b2)とb4)間にはsequenced-before関係が存在しないため“b2)後置++演算子によるse”と“b4)代入演算子によるse”はunsequencedとなる(1.9/p13)。同一オブジェクトに対する互いにunsequencedなside effectsが存在するため、式文[B]は未定義動作を引き起こす(1.9/p15)
  • 式文[C] i = ++i + i;:式文[A]同様に、式文i = (i+=1) + i;として解釈する(5.3.2/p1)。c1)部分式i+=1によるse は c2)部分式i+=1全体のvc より前に順序付けられ(5.17/p1)、c2)+演算子オペランドvalue computation および c3)同右オペランドのvc は、それぞれ c4)部分式(i+=1) + i全体のvc より前に順序付けられる(1.9/p15)。一方で+演算子オペランド c2)部分式i+=1のvc と c3)部分式iのvc はunsequencedとなる(1.9/p15)。以上より“c1)前置++演算子によるse”と“c3)部分式iのvc”はunsequencedとなり、同一オブジェクトに対するside effectとその値を使うvalue computationにより式文[C]は未定義動作を引き起こす(1.9/p15)

C++14 1.9/p13,15, 5.2.6/p1, 5.3.2/p1, 5.17/p1より一部引用(下線部は強調)。

13 Sequenced before is an asymmetric, transitive, pair-wise relation between evaluations executed by a single thread (1.10), which induces a partial order among those evaluations. Given any two evaluations 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. [Note: The execution of unsequenced evaluations can overlap. -- end note] (snip)

15 Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced. [Note: 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. -- end note] The value computations of the operands of an operator are sequenced before the value computation of the result of the operator. If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, and they are not potentially concurrent (1.10), the behavior is undefined. [Note: The next section imposes similar, but more complex restrictions on potentially concurrent computations. -- end note]
[Example:

void f(int, int);
void g(int i, int* v) {
  i = v[i++];         // the behavior is undefined
  i = 7, i++, i++;    // i becomes 9

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

  f(i = -1, i = -1);  // the behavior is undefined
}

-- end example]
(snip)

1 The value of a postfix ++ expression is the value of its operand. (snip) The value computation of the ++ expression is sequenced before the modification of the operand object. (snip)

1 The operand of prefix ++ is modified by adding 1, or set to true if it is bool (this use is deprecated). The operand shall be a modifiable lvalue. (snip) If x is not of type bool, the expression ++x is equivalent to x+=1 [Note: See the discussions of addition (5.7) and assignment operators (5.17) for information on conversions. -- end note]

1 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 referring to the left operand. (snip) 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. (snip)

C++1z仕様

C++1z(C++17)に向けて提案文書P0145R3が採択され、一部の演算子においてオペランドの評価順が強く規定される。ただし、あくまでも意図せず未定義動作となっていた慣習的記述を救うことが目的であり、あらゆる部分式での評価順を規定するものではない。

下記理由により前掲コード式文[A], [B]がwell-definedとなり、[C]は未定義動作を引き起こす。

  • 式文[A] i = ++i + 1;:(C++11/14仕様と同様のため省略)
  • 式文[B] i = i++ + 1;C++11/14仕様からの順序規定に加えて、=演算子オペランド部分式に紐付く“b2)後置++演算子によるse”は、同左オペランドに紐付く“b4)代入演算子によるse”より前に順序付けられる(1.9/p16, 5.18/p1)。同一オブジェクトへのside effects間にsequenced-beforeが成立するため、式文[B]はwell-definedとなる。
  • 式文[C] i = ++i + i;:(C++11/14仕様と同様のため省略)*7

P0145R3適用後のWorking Draft N4618 1.9/p16,18, 5.18/p1より一部引用(下線部はP0145R3による変更箇所)。

16 Sequenced before is an asymmetric, transitive, pair-wise relation between evaluations executed by a single thread (1.10), which induces a partial order among those evaluations. (snip) An expression X is said to be sequenced before an expression Y if every value computation and every side effect associated with the expression X is sequenced before every value computation and every side effect associated with the expression Y.

18 Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced. [Note: 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. -- end note] The value computations of the operands of an operator are sequenced before the value computation of the result of the operator. If a side effect on a memory location (1.7) is unsequenced relative to either another side effect on the same memory location or a value computation using the value of any object in the same memory location, and they are not potentially concurrent (1.10), the behavior is undefined. [Note: The next section imposes similar, but more complex restrictions on potentially concurrent computations. -- end note]
[Example:

void g(int i) {
  i = 7, i++, i++;  // i becomes 9

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

-- end example]

1 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 referring to the left operand. (snip) 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. (snip)

ノート:文章のみによるsequenced-before関係の説明は理解しづらいため、参照用に各vc/seをノードとする有向グラフを作成した。https://gist.github.com/yohhoy/3ff244f51e53d4b42c85e63ea4c45a46 (Special thanks to draw.io)

関連URL

*1:本記事はその主題とはもはや直接関係しないが、2016年12月にTwitterで話題に上ったpaiza出題のパズルとその後の顛末を動機としている。

*2:前置/後置デクリメント演算子でも同様

*3:C++14以前では、算術加算 + に限らず任意の2項演算子(短絡評価が保証される組み込みの論理演算子 &&, ||、カンマ演算子 , を除く)でも同様に本文の議論が成り立つ。

*4:C++1z以降では、組み込み/演算子オーバーロードに関わらずシフト演算子 <<, >>、論理演算子 &&, ||、カンマ演算子 , を除いた2項演算子で同様に本文の議論が成り立つ。

*5:C++03 5/p4 Example中のコメントは、CD1時点では"the behavior is unspecified"となっていたが、CWG 351により"the behavior is undefined"へと修正された。

*6:C++14 1.9/p12: "Evaluation of an expression (or a sub-expression) in general includes both 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."

*7:P0145R3により部分式 i+=1 の両オペランド間には順序規定が追加されるが、式文[C]の未定義動作を引き起こす “c1)前置 ++ 演算子によるse” と “c3)部分式 i のvc” の関係性には影響しない。