Me

Kotet

Kotetのブログ。興味分野の知識をまとめたり、翻訳したりしている。

Kotet's Personal Blog

#dlang プログラムの城を粉々にしてしまうバグを永久に克服する【翻訳】

/ #dlang / #tech / #translation / #d_blog

ソースを見る / 変更履歴を見る / マサカリを投げる


目次


この記事は、 Vanquish Forever These Bugs That Blasted Your Kingdom – The D Blog を自分用に翻訳したものを 許可を得て 公開するものである。

ソース中にコメントの形で原文を残している。 誤字や誤訳などを見つけたら今すぐ Pull requestだ!


Walter BrightはD言語のBDFL1でありDigital Marsのファウンダーです。 彼は最初のネイティブC++コンパイラであるZortech C++などの様々な言語のコンパイラやインタプリタを実装した10年の経験があります。 また、Empire, the Wargame of the Century2 3の作者でもあります。 この投稿は、DのBetterCモードを使うと既存のCのコードからいかにしてバグをなくし、回避することができるかについてのシリーズの最初のものです。


Bug

簡単に発生し、チェックが難しく、たいていテストにも引っかからず、 デプロイされるとあなたの城を粉砕する、 そんなバグに苦労したことはありませんか? そういうバグはあなたの時間と金銭を何度も奪ってゆきます。 自分がもっと優れたプログラマならこんなことは起こらないのに、そうでしょう?

そうではありません。 私はそれらのバグに二度とあなたの城が壊されないようにツールを改善することによって、バグがあなたのせいではなくツールのせいで起きているのだと証明します。

そして、あなたは妥協する必要もありません。

配列のオーバーフロー

このような配列の合計値を計算する伝統的プログラムを考えてみましょう:

#include <stdio.h>

#define MAX 10

int sumArray(int* p) {
    int sum = 0;
    int i;
    for (i = 0; i <= MAX; ++i)
        sum += p[i];
    return sum;
}

int main() {
    static int values[MAX] = { 7,10,58,62,93,100,8,17,77,17 };
    printf("sum = %d\n", sumArray(values));
    return 0;
}

このプログラムの出力は以下のようでなければなりません:

sum = 449

そして実際、私のUbuntu Linuxシステムで、gccclang-Wallを使うとそのように出力されます。 何がバグかもうおわかりでしょう:

for (i = 0; i <= MAX; ++i)
               ^^

これは古典的な「植木算問題」です。 ループは10回ではなく11回まわります。 正しくはこうすべきです:

for (i = 0; i < MAX; ++i)

これはバグですが、それでもこのプログラムは正しい結果を返します! とにかく、私のシステムにおいては。 したがって私はこのバグに気づきません。 顧客のシステムでは、えっと、なぜか動作せず、私はリモート ハイゼンバグ を抱えてしまいました。 どれほどの時間とお金が消えてゆくのか今からすでに心配です。

こういう不愉快なバグが何年もかけて私の脳を以下のようにリプログラミングしました:

  1. 絶対に「閉じた」終端を使わない
  2. 絶対にループ条件に<=を使わない

私は優れたプログラマになることで問題を解決しました! でも、本当にそうでしょうか? 実は問題は解決していません。 コードをもう一度、それをレビューしなければならないかわいそうな無能の視点から見てみましょう。 sumArray()に問題がないことを確かめるために、彼は以下のことをしなければなりません:

  1. どのようなポインタが渡されるか、sumArray()のすべての呼び出し元を見に行く
  2. ポインタが配列を指していることを確認する
  3. 配列の大きさが実際にMAXであるか確認する

これは今回のような小さなプログラムでは小さな作業ですが、実際のプログラムの複雑さの増加に対してはスケールしません。 sumArrayの呼び出し元が増え、sumArrayに渡されるデータ構造が間接的になるに従って、この関数が正しいと証明するために頭の中で解析しなくてはならないデータフローは複雑になってゆきます。

それでもあなたはレビューをやり遂げました、しかし本当に? 誰か他の人が変更をチェックしたとき、それもちゃんと行われるでしょうか? 自分でチェックし直したくなりませんか? もっといい方法があります。 これはツールの問題です。

この問題の根本的な点は、Cにおいて関数のパラメータがたとえ配列として宣言されていても、配列が関数にポインタとして渡されることにあります。 回避することも、検出することもできません(少なくともgccとclangは検出しませんが、誰かがアナライザを開発しているかもしれません)。

そしてこれを解決するのはBetterCコンパイラとしてのD言語です。 Dは動的配列の概念を持ち、それはこんな感じのfatポインタです:

struct DynamicArray {
    T* ptr;
    size_t length;
}

以下のように宣言し:

int[] a;

例はこのようになります:

import core.stdc.stdio;

extern (C):   // 宣言のためにCのABIを使用

enum MAX = 10;

int sumArray(int[] a) {
    int sum = 0;
    for (int i = 0; i <= MAX; ++i)
        sum += a[i];
    return sum;
}

int main() {
    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];
    printf("sum = %d\n", sumArray(values));
    return 0;
}

コンパイルし:

dmd -betterC sum.d

実行します:

./sum
Assertion failure: 'array overflow' on line 11 in file 'sum.d'

いいですね、<= を < に置き換えるとこうなります:

./sum
sum = 449

動的配列 a はその範囲を持ち、コンパイラは配列の境界オーバーフローチェックを挿入します。

それだけではありません。

迷惑なMAXが残っています。 aはその範囲を持っているため、代わりにそれを使えます:

for (int i = 0; i < a.length; ++i)

これは一般的なイディオムであり、Dにはそのための特殊な構文があります:

foreach (value; a)
    sum += value;

関数sumArray()全体は以下のようになります:

int sumArray(int[] a) {
    int sum = 0;
    foreach (value; a)
        sum += value;
    return sum;
}

そしてsumArray()はそれが置かれたプログラムと分離してレビューできるようになりました。 あなたはより短時間で、より信頼性の高い方法で、より多くのことができるようになり、給料を上げてもらう理由ができました。 給料は上がらなくても、少なくとも週末にバグ修正の緊急連絡が入ることはなくなったわけです。

「異議あり!」あなたはこう言います。 「asumArray()に渡すためにはスタックをのプッシュが2回必要です。 しかしpの場合1度で済みます。 あなたは妥協は必要ないと言いましたが、私はここでスピードを失っています。」

確かに、MAXがマニフェスト定数であり、関数に渡されない場合、以下のようになります:

int sumArray(int *p, size_t length);

しかし「妥協」はさせません。 Dはパラメータを参照として渡すことができ、配列の長さを固定することができます。 つまり以下のようになります:

int sumArray(ref int[MAX] a) {
    int sum = 0;
    foreach (value; a)
        sum += value;
    return sum;
}

refパラメータになったaは実行時にただのポインタになります。 これにはMAX要素の配列という型があり、アクセスには配列境界チェックがなされます。 コンパイラの型システムがやってくれるため呼び出し元をチェックする必要はなく、正しいサイズの配列が渡されます。

「異議あり!」また言います。 「Dはポインタをサポートしています。 そのまま書くことはできないのですか? 理由はなんですか? 機械的保証が行われたというふうに聞こえましたが?」

そうです、以下のようにコードを書くこともできます:

import core.stdc.stdio;

extern (C):   // 宣言のためにCのABIを使用

enum MAX = 10;

int sumArray(int* p) {
    int sum = 0;
    for (int i = 0; i <= MAX; ++i)
        sum += p[i];
    return sum;
}

int main() {
    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];
    printf("sum = %d\n", sumArray(&values[0]));
    return 0;
}

恐ろしいバグが潜んでいるのにもかかわらず、これは何事もなくコンパイルされます。 そして以下のような結果が得られます:

sum = 39479

不思議ですね、しかし誰も賢くならずとも簡単に449を印刷するようにできます。

どのようにこれを阻止するのでしょうか? コードに@safe属性をつけるのです:

import core.stdc.stdio;

extern (C):   // 宣言のためCのABIを使用

enum MAX = 10;

@safe int sumArray(int* p) {
    int sum = 0;
    for (int i = 0; i <= MAX; ++i)
        sum += p[i];
    return sum;
}

int main() {
    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];
    printf("sum = %d\n", sumArray(&values[0]));
    return 0;
}

コンパイルすると以下のようになります:

sum.d(10): Error: safe function 'sum.sumArray' cannot index pointer 'p'

@safeが使われていることを確かめるためのgrepをコードレビューに含めなくてはなりませんが、それだけです。

まとめると、このバグは引数として渡される際に配列がポインタになってしまうことを防ぐことで倒すことができ、ポインタへの間接的な演算を禁止することで永遠に亡きものにできます。 バッファオーバーフローエラーによって台無しにされることはほぼなくなるでしょう。 シリーズの次回作にご期待ください。 次のバグが堀を超えてくるかもしれませんよ!(もしくは、あなたのツールには堀がないかもしれません。)