Old New Thing: 未定義動作はタイムトラベルを引き起こす（他にもいろいろあるけど、タイムトラベルが一番ぶっ飛んでる）

Undefined behavior can result in time travel (among other things, but time travel is the funkiest) - The Old New Thing - Site Home - MSDN Blogs

久しぶりに紹介するRaymond Chenのブログ記事。

C言語とC++では、様々な部分が、ドラゴンの住まう地というレッテルを貼られている。いや、正式には、未定義動作とされている。

未定義動作が発動した場合、何でもありだ。例えば、変数は同時にtrueでもfalseでもありえる。John Regehrは興味深い例のリストをまとめて、未定義動作コンテストの受賞者もある。

以下の関数を考える。

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

これがタイムトラベルと何の関係があるんだ、と読者は疑問に思うであろう。ちょっと待て、あわてんぼうさん。

まず、ループの処理に間違いがあることに気がつくはずだ。結果として、関数はループを終了する前に、table配列の最後の一つ後ろを読んでしまう。古典的なコンパイラーは、特にこれを気にしない。単に、（それが言語のルールに違反するものであるにも関わらず）配列の要素の範囲を超えた領域を読むコードを生成するだけだし、配列の最後の一つ後の要素が条件にあうならばtrueを返す。

一方、古典的ではないコンパイラーは、以下のような解析を行うかもしれない。

• ループの最初の4回の実行で、関数はtrueを返すかもしれない
• iが4のとき、コードは未定義動作を行う。未定義動作は何をしてもよいので、我輩としてはそんなの無視して、iは決して4にはならないものとして話を進める。（もし、この仮定が破られた場合、何か予期せぬことが起こるであろうが、まあ、そんなことはどうでもよい。未定義動作は、我輩にとっては何をしてもいいことなのだからな）
• iが5の場合は、決して発生しない。なぜならば、iが5に到達するには、iはまず、4に到達しなければならない。吾輩は、すでにiが4には到達しないと看過しておるからだ。
• 故に、すべての合法なコードパスはtrueを返すものである。

この結果、非古典的コンパイラーは、関数を以下のように最適化できる。

bool exists_in_table(int v)
{
    return true;
}

やれやれ、こいつはちっと変だな。関数は未定義動作によって最適化されたため、何もしなくなってしまった。たとえ値がtableに存在しなくても（アクセスするのが違法な5番目の要素にすらなくても）、関数はtrueを返すのだ。

さて、この非古典的挙動をもっと推し進めてみよう。コンパイラーは、未定義動作は決して起こらぬものと看過できる（なぜならば、もし起こった場合、コンパイラーは何でもすることが許されている）のであるから、コンパイラーは未定義動作を最適化の助けとできる。

int value_or_fallback(int *p) { return p ? *p : 42; }

上記の関数は、int型へのポインターを取り、ポイントしている値か、（もしポインターがnullの場合は）、フォールバック値である42を返す。ここまではいい。

さて、この関数にデバッグ用のコードを挿入してみよう。

int value_or_fallback(int *p)
{
 printf("The value of *p is %d\n", *p);
 return p ? *p : 42;
}

この新しい行には、バグがある。ポインターpをnullであるかどうか確認せずにデリファレンスしているのだ。この些細なバグは、様々な結果を引き起こす。非古典的なコンパイラーは、この関数を以下のように最適化する。

int value_or_fallback(int *p)
{
 printf("The value of *p is %d\n", *p);
 return *p;
}

なぜならば、コンパイラーは、nullポインターチェックは必要ないと看過するからだ。もし、ポインターがnullであれば、どうせprintfは未定義動作を引き起こすのであるからして、コンパイラーはポインターがnullの場合は、何でもすることが出来るのだ（これにはポインターがnull出ないがごとく振る舞うことも含まれる）

さて、これまだまだ驚くに当たらない。読者の中には、コンパイラーの最適化としてむしろ期待している仁もいるだろう（例えば、もし三項演算子がマクロの中に隠されていた場合、それがおそらくはfalseの場合、コンパイラーに除去して欲しいと思うだろう）

しかし、非古典的なコンパイラーは、このバグ関数を利用して、タイムトラベルを始めるのだ。

void unwitting(bool door_is_open)
{
 if (door_is_open) {
  walk_on_in();
 } else {
  ring_bell();

  // wait for the door to open using the fallback value
  fallback = value_or_fallback(nullptr);
  wait_for_door_to_open(fallback);
 }
}

非古典的なコンパイラーは、この関数全体を、以下のように最適化できる。

void unwitting(bool door_is_open)
{
 walk_on_in();
}

ハァ？

value_or_fallback(nullptr)という呼び出しは、すべてのコードパスで未定義動作を引き起こすとコンパイラーは認識する。この解析を前方に持ってくると、door_is_openがfalseであった場合、else分岐はすべてのコードパスで未定義動作であると認識する。つまり、else分岐全体が、到達不可能である。[2]

さて、タイムトラベルの時間だ。

void keep_checking_door()
{
 for (;;) {
  printf("Is the door open? ");
  fflush(stdout);
  char response;
  if (scanf("%c", &response) != 1) return;
  bool door_is_open = response == 'Y';
  unwitting(door_is_open);
 }
}

非古典的なコンパイラーは、解析結果を持ってきて、「もし、door_is_openがfalseであれば、挙動は未定義である」とし、函数を以下のように書き換えるかもしれない。

void keep_checking_door()
{
 for (;;) {
  printf("Is the door open? ");
  fflush(stdout);
  char response;
  if (scanf("%c", &response) != 1) return;
  bool door_is_open = response == 'Y';
  if (!door_is_open) abort();
  walk_on_in();
 }
}

これをみると、オリジナルのコードは、クラッシュする前にドアベルを鳴らすが、書き換えられた関数は、ベルを鳴らすのをスキップして即座にクラッシュする。これは、コンパイラーは過去に戻ってベルを鳴らさないようにしたともとれる。

この、「過去にさかのぼる」というのは、ファイルのような外部にみえるオブジェクトでも起こりうる。なぜならば、標準規格は未定義動作を引き起こした時、何でもありなことを認めているからだ。その何でもありというのは、タイムマシンに飛び乗って、fwriteを呼び出さなかったかのように振る舞うことも含まれる。

コンパイラーはタイムトラベルを引き起こすなど許されないと主張したとしても[1]、先行する処理がなかったことにされることはある。例えば、未定義の操作により、ファイルバッファーが破壊され、データは実際に書き込まれないということが起こりうる。たとえ、バッファーがフラッシュされたとしても、未定義の操作はftruncateを呼び出して、論理的に書き込んだデータを除去することがありうる。あるいは、作ったはずのファイルにDeleteFileを呼び出してファイルをデリートすることもあり得る。

これらの挙動はすべて、同じ観測効果を持つ。特に、先行する処理が発生しなかったようにみえる。それが実際に起きてなかったことにされたのか、最初から起こらなかったのかは、コンパイラー理論の上からは、どうでもいいことである。

コンパイラーは未定義処理の結果を時間をさかのぼって適用することもできるということだ。

[1] 標準規格は、明示的に未定義動作によるタイムトラベルを認めている。

しかし、もしそのような実行が未定義の操作を含む場合、この国際標準規格は実装に対し、そのような入力に対し、いかなる実行上の制約をも課すことはない（未定義操作に先行する操作をも含む）

[2] この変換を考える別の視点としては、コンパイラーはelse分岐はすべてのコードパスで未定義の挙動を引き起こすので、コードを以下のように書き換えるとみることもできる。

void unwitting(bool door_is_open)
{
 if (door_is_open) {
  walk_on_in();
 } else {
  walk_on_in();
 }
}

未定義動作では何が起こっても許されるというということを利用した例だ。この例では、「walk_on_inを間違って呼ぶ」という何かになる。

ボーナス小ネタ：未定義動作には、一見すると明らかではない場合もある。例えば、nullポインターをデリファレンスするのは、何か危険なことをする前にデリファレンスの対策をしたとしても、依然として未定義動作になる。

int *p = nullptr;
int& i = *p;
foo(&i); // undefined

&と*は、お互いに打ち消しあい、あたかもfoo(p)と書いたかのようになると考えるかもしれないが、存在しないオブジェクトへのリファレンスを作った時点で、使わなくても、未定義動作を引き起こすのだ(§8.5.3(1))

参考文献：なぜすべてのCプログラマーは未定義動作について知らねばならないのか。Part 1, Part 2, Part 3