クラウドMacで検証するiOSリングバッファの折り返しと満杯・空状態

Windowsでデータ受信処理を実装し、クラウドMacに移してiOSのテストを実行すると、リングバッファを連続して満杯まで書き込み、一部を読み出してから再び書き込んだときにだけ、データが失われることがあります。単発のエンキューとデキューでは、この種の不具合は見つかりません。ここではバッファを純粋なSwiftの型として切り出し、OSXMeshのクラウドMacのターミナルで検証したうえで、同じアサーション群をアプリのテストターゲットに移します。

まず満杯・空状態と失敗時の契約を決める

この記事で扱うのは、固定容量で先入れ先出しの整数バッファです。容量は正の値に限定し、満杯のときは新しい要素を拒否して、既存データを上書きしません。空のときに読み出すと nil を返します。一括書き込みは部分的な成功を許容し、実際に受け入れた要素数を返します。残りの入力の処理は呼び出し側に委ねます。

設計はこれだけに限りませんが、最初にどの契約を採用するか決める必要があります。製品の要件として最も古いデータを上書きする必要があるなら、別の型とアサーションを用意してください。同じ append が呼び出し箇所によってひそかに振る舞いを変える設計にはしません。

リングバッファの正しさは、単に「範囲外にアクセスしない」ことではありません。失敗した操作は状態を変えてはならず、読み出しに成功した要素の順序は、受け入れた順序と一致する必要があります。

次に読み出す位置を head で表し、満杯と空の区別には count を使います。論理的な末尾はこの2つから求めるため、すべての格納スロットを使用できます。この例では容量に上限を設け、インデックスの加算によるオーバーフローと、テストで誤って巨大な容量を渡すことを防ぎます。

単独で実行できる最小実装を書く

RingCheck.swift を新規作成し、次のコードを入れます。標準ライブラリだけに依存するため、シミュレータもプロジェクトのコード署名も不要です。まず swift --version を実行して、ツールチェーンの情報を記録してください。コマンドが使えない場合は、先にGUIで開発ツールのインストールと初期設定を済ませます。

struct IntRing {
    let capacity: Int
    private var storage: [Int?]
    private var head = 0
    private(set) var count = 0

    init(capacity: Int) {
        precondition((1...1_000_000).contains(capacity))
        self.capacity = capacity
        storage = Array(repeating: nil, count: capacity)
    }

    mutating func append(_ value: Int) -> Bool {
        guard count < capacity else { return false }
        storage[(head + count) % capacity] = value
        count += 1
        return true
    }

    mutating func pop() -> Int? {
        guard count > 0 else { return nil }
        let value = storage[head]!
        storage[head] = nil
        head = (head + 1) % capacity
        count -= 1
        return value
    }

    mutating func appendBatch(_ values: [Int]) -> Int {
        var accepted = 0
        for value in values {
            guard append(value) else { break }
            accepted += 1
        }
        return accepted
    }

    func snapshot() -> [Int] {
        (0..<count).map {
            storage[(head + $0) % capacity]!
        }
    }
}

ここでの強制アンラップは、「論理的に有効な範囲には必ず値が入っている」という内部の不変条件に依存しています。実装がこの不変条件を破った場合、デフォルト値で不具合を隠すのではなく、テストをその場で失敗させるべきです。読み出し後にスロットを空にしておくと、将来、要素を参照型に変更した際にも、不要になったオブジェクトを速やかに解放できます。

小さな容量で折り返しの不具合をあぶり出す

次のコードをファイルの末尾に追加します。容量3のケースでは、まず満杯まで書き込み、2つの要素を読み出してから、配列の末尾をまたぐように書き込みます。容量1のケースは、「空きスロットを1つ残す」方式を今回の容量の契約と混同していないかを確認するのに役立ちます。

var ring = IntRing(capacity: 3)
precondition(ring.appendBatch([10, 20, 30]) == 3)
precondition(!ring.append(99))
precondition(ring.snapshot() == [10, 20, 30])
precondition(ring.pop() == 10)
precondition(ring.pop() == 20)
precondition(ring.appendBatch([40, 50, 60]) == 2)
precondition(ring.snapshot() == [30, 40, 50])
precondition(ring.pop() == 30)
precondition(ring.pop() == 40)
precondition(ring.pop() == 50)
precondition(ring.pop() == nil)
precondition(ring.count == 0)

var single = IntRing(capacity: 1)
precondition(single.pop() == nil)
precondition(single.append(7))
precondition(!single.append(8))
precondition(single.pop() == 7)
precondition(single.appendBatch([]) == 0)

特に、書き込みを拒否した後のスナップショットを確認してください。戻り値が false であることを検証するだけでは不十分です。誤った実装では、先にインデックスを進めてから容量がいっぱいだと判定している可能性があります。空の状態での読み出しも同様で、次に有効な要素を読み出す位置をひそかに動かしてはなりません。

固定シードで参照キューと1ステップずつ比較する

境界ケースが通ったら、モデルベースのテストを追加します。参照モデルには通常の配列を使います。先頭要素の削除は低速ですが、ここでは容量が小さいため、コードを確認しやすいことを優先します。各ステップで内容と要素数を比較すれば、最終結果だけを照合するより、最初に食い違いが生じた箇所を特定しやすくなります。

var seed: UInt64 = 0x5EED
func next() -> UInt64 {
    seed = seed &* 6364136223846793005 &+ 1
    return seed
}

for capacity in [1, 2, 3, 7] {
    var tested = IntRing(capacity: capacity)
    var model: [Int] = []

    for step in 0..<20_000 {
        if (next() >> 32) % 2 == 0 {
            let value = Int(next() % 10_000)
            let accepted = model.count < capacity
            precondition(tested.append(value) == accepted)
            if accepted { model.append(value) }
        } else {
            let expected = model.isEmpty ? nil : model.removeFirst()
            precondition(tested.pop() == expected)
        }

        precondition(
            tested.snapshot() == model,
            "capacity=\(capacity), step=\(step)"
        )
        precondition(tested.count == model.count)
    }
}

swift RingCheck.swift を実行し、アサーションが失敗せずに正常終了すれば合格です。ここから性能についての結論は導けません。ループ回数はテストの規模を表しているにすぎません。一括書き込みについては、空き容量がゼロ、ちょうど足りる、1スロット足りない、という3つの明示的なケースも追加し、戻り値の要素数と、受け入れられずに残った入力の末尾部分を確認してください。

操作の選択には、生成した値の上位ビットを使っています。単純な生成器の下位ビットにある規則性によって、操作が機械的に交互になるのを避けるためです。再現に備えて、初期シード、容量、失敗したステップを残してください。失敗した瞬間のシードだけを記録するのでは不十分です。

プロジェクトに組み込み、適用範囲を守る

単独スクリプトのテストが通ったら、型をアプリの業務ロジックを担うモジュールへ移し、アサーションをテストフレームワークの等値アサーションに置き換えます。少なくとも、次の3種類のチェックは残してください。

• 状態の制約：要素数が常にゼロ以上かつ容量以下であり、失敗した操作の前後でスナップショットが完全に一致すること。
• 順序の制約：重複する値や負数も、受け入れた順序で返されること。配列の比較を集合の比較で代用しないこと。
• 一括処理の制約：戻り値が実際に書き込んだ要素数と一致し、受け入れられなかった入力の末尾部分を呼び出し側が処理済みと見なさないこと。

アプリ側でクリア操作を提供する場合は、空、満杯、折り返し済みのそれぞれの状態でクリアし、その後に再び満杯まで書き込んで、古いデータが再出現しないことを確認します。要素をジェネリック型に変更する場合は、参照の解放も別途確認してください。整数を使ったテストに合格しても、ライフサイクルが正しいとは限りません。

この実装は逐次アクセス専用です。ロックフリーキューではなく、リアルタイム制約のあるオーディオコールバックにそのまま組み込む用途にも適していません。複数のタスクで共有する場合は、まずどこで同期を取るかを明確にしてから、並行動作をテストしてください。最終的には、実装、境界ケース、固定シードのモデルテストをまとめてコミットし、次にインデックス計算のアルゴリズムを変更したときにも、同じ合否基準で検証できるようにします。

よくある質問