クラウドMacで検証するiOSの安定優先度キュー

画像のプリフェッチ、アップロード待ちの処理、ローカルタスクの実行順制御では、優先度キューがよく使われます。開発用Macで3件のタスクを続けて追加し、順に取り出すだけなら、正しい結果を得るのは難しくありません。ところが、クラウドMac上の回帰テストで追加と取り出しを交互に実行すると、同じ優先度のタスクの順序が入れ替わることがあります。ここではスケジューラ全体を作るのではなく、Swiftの二分ヒープだけを切り出し、常に順序の契約を守っているかを検証します。

優先度と安定性の意味を定義する

本記事では、優先度の数値が小さいものほど先に取り出すものとします。数値が同じ場合は、先に追加したものを先に取り出します。タスク識別子は業務データであり、比較には使いません。同じタスクを再び追加した場合は新しいエントリとして扱い、新たな追加順の連番を割り当てます。

まず、これらのルールをテスト仕様として書き出し、その後にデータ構造を実装します。配列のインデックスを永続的な連番として使ってはいけません。取り出しや要素の交換でインデックスが変わるため、安定性を保証できなくなるからです。また、優先度を減算して大小を判定するのも避けます。整数の極値ではオーバーフローが起こり得ます。

安定性と公平性は別の性質です。優先度の高いタスクが到着し続けると、優先度の低いタスクは長時間待たされる可能性があります。エージングや割り当て枠はスケジューリング方針の問題であり、ヒープの比較関数に暗黙に組み込むべきではありません。

以下の実装は値型で、逐次アクセスのみを想定しています。並行処理に組み込む場合は、単一の分離境界でアクセスを一元管理し、複数のタスクから同じインスタンスを同時に変更させないでください。

追加順の連番を持つ最小ヒープを実装する

コードを main.swift として保存します。比較キーは優先度と単調に増加する連番の組です。追加時の上方移動と取り出し時の下方移動では、必ず同じ比較関数を使います。そうすることで、二つの処理経路で「どちらを先にするか」の解釈が食い違うのを防げます。

struct StableQueue<Value> {
    enum Failure: Error {
        case sequenceExhausted
    }

    private struct Entry {
        let value: Value
        let priority: Int
        let sequence: UInt64
    }

    private var entries: [Entry] = []
    private var nextSequence: UInt64 = 0

    private func precedes(_ a: Entry, _ b: Entry) -> Bool {
        if a.priority != b.priority {
            return a.priority < b.priority
        }
        return a.sequence < b.sequence
    }

    mutating func enqueue(_ value: Value, priority: Int) throws {
        guard nextSequence < UInt64.max else {
            throw Failure.sequenceExhausted
        }
        entries.append(Entry(
            value: value,
            priority: priority,
            sequence: nextSequence
        ))
        nextSequence += 1

        var child = entries.count - 1
        while child > 0 {
            let parent = (child - 1) / 2
            guard precedes(entries[child], entries[parent]) else {
                break
            }
            entries.swapAt(child, parent)
            child = parent
        }
    }

    mutating func dequeue() -> Value? {
        guard !entries.isEmpty else { return nil }
        if entries.count == 1 {
            return entries.removeLast().value
        }

        let result = entries[0].value
        entries[0] = entries.removeLast()
        var parent = 0

        while parent < entries.count / 2 {
            let left = parent * 2 + 1
            let right = left + 1
            var candidate = left
            if right < entries.count,
               precedes(entries[right], entries[left]) {
                candidate = right
            }
            guard precedes(entries[candidate], entries[parent]) else {
                break
            }
            entries.swapAt(parent, candidate)
            parent = candidate
        }
        return result
    }
}

連番が上限に達したら、明示的にエラーを返します。周回させることも、キューが空になった際に暗黙にゼロへ戻すこともしません。この実装では上限値そのものを使わずに残し、配列を変更する前に失敗するようにしています。失敗しても既存エントリの順序が変わらないことを、テストで確認する必要があります。

追加と取り出しを交互に行い、下方移動の不具合を捉える

次のコードを同じファイルの末尾に追加します。最終的な取り出し順だけでなく、1件取り出した後に同じ優先度のタスクを追加しても、既存のエントリが新しいエントリより先に取り出されることを確認します。

func requireEqual<T: Equatable>(_ actual: T, _ expected: T) {
    precondition(actual == expected, "Queue contract failed")
}

var queue = StableQueue<String>()
requireEqual(queue.dequeue(), Optional<String>.none)

try queue.enqueue("A", priority: 2)
try queue.enqueue("B", priority: 1)
try queue.enqueue("C", priority: 2)
requireEqual(queue.dequeue(), Optional("B"))

try queue.enqueue("D", priority: 2)
try queue.enqueue("E", priority: Int.min)
requireEqual(queue.dequeue(), Optional("E"))
requireEqual(queue.dequeue(), Optional("A"))
requireEqual(queue.dequeue(), Optional("C"))
requireEqual(queue.dequeue(), Optional("D"))
requireEqual(queue.dequeue(), Optional<String>.none)

クラウドMacの作業ディレクトリで実行します。

set -eu
mkdir -p .build
xcrun swiftc -Onone main.swift -o .build/queue-check
.build/queue-check

成功時には何も出力されず、失敗時は非ゼロの終了コードでジョブを停止します。最適化ビルドで検査が削除されるのを避けるため、ここでは assert を使いません。また、「コンパイルが通った」ことを実行時の検証の代わりにはしません。

さらに、決定的なテストケースを3組追加します。すべて同じ優先度なら入力順を維持すること、優先度を逆順にしてすべて追加した後は昇順で取り出せること、要素が2件だけの状態から1件取り出し、その後は追加と取り出しを繰り返せることです。最後のケースは、右の子が存在しない場合の範囲外アクセスを見つけるのに役立ちます。

参照モデルでテスト範囲を広げる

手書きのテストケースは契約を明確に示せますが、あらゆるヒープの形状を網羅するのは困難です。参照モデルでは、「タスク番号、優先度、追加順の連番」を配列に保存し、取り出すたびに後ろの2項目でソートするだけで構いません。処理は遅くても実装が単純なので、小規模なテストで正否を判定する基準に適しています。

追加と取り出しが混在する操作列を生成し、追加のたびに参照モデルにも同じエントリを書き込みます。取り出すたびに、両方が返すOptionalのタスク番号を比較し、操作列が終わったら両方を空になるまで取り出します。優先度だけの比較では不十分です。同じ優先度のタスクの順序が入れ替わることも不具合だからです。

シードを指定できる疑似乱数生成器を使い、再現できない乱数生成APIに直接依存しないようにします。失敗時には、少なくともシード、操作のインデックス、失敗までの完全な操作列、双方の結果を記録します。原因を絞り込む際は、失敗までの操作列から操作をまとまりごとに削り、失敗を再現できる最短の列を残します。

参照モデルを実装から独立させる

参照モデルでヒープの比較関数を再利用してはいけません。同じ不具合を共有すると、両者の結果が一致してテストを通過してしまいます。モデル側ではまず優先度を比較し、等しい場合だけ最も早く追加されたエントリを選ぶようにして、業務ルールを直接表現できます。

回帰テストに組み込み、保証範囲を明確にする

コミット前には、空のキュー、単一要素、同じ優先度での安定性、整数の極値、追加と取り出しの交互操作を必ずテストし、その後に固定シード群を使った参照モデルとの比較を実行します。新たに失敗したシードは長期運用する回帰テストセットに追加します。乱数テストの回数を増やして再実行するだけで済ませてはいけません。

連番の枯渇は、通常の追加回数では検証しきれません。実際のモジュールでは、テスト専用の内部初期化手段を用意し、カウンタを上限直前に設定できるようにするとよいでしょう。これにより、最後に許可される追加と、その次に拒否される追加の境界を確認できます。本番環境の状態を変更できる公開インターフェースを用意する必要はありません。

保存するのは、Swiftツールチェーンのバージョン、コミット識別子、失敗した操作列で十分です。業務ペイロードを残す必要はありません。最終的な検証結果には、ここで確認したのは逐次アクセスされるキューの順序と境界での振る舞いであり、スレッドセーフ性、タスク実行の成功率、スケジューリングの公平性は対象外であると明記します。この境界を明確にしておけば、後で実行器に接続する際に、データ構造のテストをシステム全体の保証と取り違えずに済みます。

よくある質問