クラウドMacでiOS依存グラフを検証する

同じリソース処理タスクが、ローカルでは想定どおりに動くのに、クラウドMacのパイプラインに移すと、ときどきリソースより先にインデックスを生成してしまう。原因はマシンにあるとは限りません。タスクの順序を辞書の走査順に任せていたり、「キューに登録済み」を「依存先が完了済み」と取り違えていたりすると、プロセスを起動し直しただけで不具合が表面化することがあります。ここでは、単独で実行できるSwiftスクリプトを使って依存グラフを検証します。シミュレータを起動する必要はありません。

まず辺の向きとエラー条件を決める

短く固定された処理なら、実行順序を手書きで指定する方法が適しています。依存グラフが役立つのは、タスクが増減したり、複数のステップが共通の前提タスクに依存したりする場合です。もともとすべての処理を直列に実行するだけなら、グラフの導入は保守の負担を増やすだけです。

この記事では、入力を「タスク名 → 前提タスクの集合」で表します。たとえば、indexがassetsに依存する場合、出力ではassetsが先に現れなければなりません。タスク名は固定の識別子として扱い、表示言語によって変更しません。互いに依存しないタスクは、識別子の辞書順で選びます。

入力については、さらに3つのルールを定めます。重複する辺はまとめること、未知の依存先があれば即座にエラーにすること、自己依存は循環として扱うことです。空のグラフは有効な入力とし、空の配列を返します。未知のノードを暗黙に作成してはいけません。名前のタイプミスまで正常な入力として受け入れてしまうためです。

ソートで確認できるのは、依存関係を満たす順序を作れるかどうかだけです。タスクの完了も、成果物の正しさも保証しません。実行状態とグラフ構造は、分けて検証する必要があります。

実行可能で順序が安定するソーターを実装する

次の内容をノードの作業ディレクトリにgraph-check.swiftとして保存します。コードが依存するのはSwift標準ライブラリだけです。現在選択されているツールチェーンで実行でき、追加パッケージのインストールは不要です。アルゴリズムは各タスクの未充足の依存数を管理し、各反復で実行可能なタスクのうち名前が辞書順で最小のものを選びます。

enum GraphError: Error, Equatable {
    case unknown(task: String, dependency: String)
    case blocked([String])
}

func ordered(_ graph: [String: [String]]) throws -> [String] {
    let names = graph.keys.sorted()
    let known = Set(names)
    var remaining: [String: Int] = [:]
    var successors: [String: [String]] = [:]

    for task in names {
        let dependencies = Set(graph[task]!)
        for dependency in dependencies.sorted() {
            guard known.contains(dependency) else {
                throw GraphError.unknown(
                    task: task, dependency: dependency
                )
            }
            successors[dependency, default: []].append(task)
        }
        remaining[task] = dependencies.count
    }

    var ready = names.filter { remaining[$0] == 0 }
    var result: [String] = []

    while !ready.isEmpty {
        let task = ready.removeFirst()
        result.append(task)
        for next in successors[task, default: []] {
            remaining[next]! -= 1
            if remaining[next] == 0 {
                ready.append(next)
            }
        }
        ready.sort()
    }

    guard result.count == names.count else {
        throw GraphError.blocked(
            names.filter { remaining[$0]! > 0 }
        )
    }
    return result
}

func check() throws {
    let graph = [
        "assets": ["fetch", "fetch"],
        "fetch": [],
        "index": ["assets"],
        "lint": []
    ]
    let result = try ordered(graph)
    precondition(result == ["fetch", "assets", "index", "lint"])

    let position = Dictionary(
        uniqueKeysWithValues: result.enumerated().map {
            ($0.element, $0.offset)
        }
    )
    precondition(result.count == graph.count)
    precondition(Set(result) == Set(graph.keys))
    for (task, dependencies) in graph {
        for dependency in dependencies {
            precondition(position[dependency]! < position[task]!)
        }
    }

    let empty = try ordered([:])
    precondition(empty.isEmpty)

    do {
        _ = try ordered(["export": ["missing"]])
        preconditionFailure("Unknown dependency was accepted")
    } catch let error as GraphError {
        precondition(error == .unknown(
            task: "export", dependency: "missing"
        ))
    }

    do {
        _ = try ordered([
            "a": ["b"], "b": ["a"], "report": ["b"]
        ])
        preconditionFailure("Cycle was accepted")
    } catch let error as GraphError {
        precondition(error == .blocked(["a", "b", "report"]))
    }
}

try check()

xcrun swift graph-check.swift

検証に成功すると何も出力せず、失敗するとプロセスはゼロ以外の終了コードを返します。この検証スクリプトは、事前条件のチェックを無効にする最適化モードで実行しないでください。プロジェクトに組み込んだ後は、同じアサーションを正式なテストターゲットに移すことで、アプリ本体のビルド設定がチェックの動作に影響するのを防げます。

性質の検証でサンプルの死角を補う

固定の期待値との比較は順序の変化を検出できますが、誤った実装をそのまま正解として固定してしまう可能性もあります。そのため、このコードでは出力の要素数、ノードの集合、各辺の前後関係も検証しています。これら3種類のチェックで、欠落、重複、依存順序の逆転を防ぎます。

続いて、ひし形のグラフを追加します。2つのタスクが同じルートに依存し、最後のタスクがその2つのタスクに依存する形です。ルートは1回だけ出力され、合流点のタスクは最後に現れなければなりません。さらに、複数の独立した部分グラフ、単一ノード、自己依存、すべてのノードが循環に含まれる入力も追加します。

同じグラフについて、辞書への挿入順を変え、さらに各依存配列の順序を反転させても、結果は完全に一致する必要があります。ここでの決定性は明示的なソートによって得られるもので、何度か実行して「いつも同じに見える」ことが根拠ではありません。たまたま正しい順序になった辞書の走査を、インターフェースの保証と捉えないでください。

ブロックされた集合を循環の構成ノードと取り違えない

例のaとbは互いに依存しています。一方、reportはbに依存するだけですが、やはり実行可能にはなりません。そのため、エラー名にはblockedを使い、残ったすべてのタスクが循環に含まれるとは主張しないようにしています。

障害調査で残すべき情報

失敗時のレポートには、元のグラフ、安定した順序にソートしたブロック対象の集合、コミット識別子、ツールチェーンのバージョンを残せば十分です。画面上で循環に含まれるノードだけを正確に赤く表示したい場合は、強連結成分の解析を追加します。入次数がまだゼロより大きいという理由だけで「循環経路」を描いてはいけません。

循環がある場合、独立した一部のタスクをすでに並べられていても、計画全体を失敗として扱うべきです。製品として部分実行を明示的にサポートしていない限り、途中までの結果を完全な実行計画として実行側に渡してはいけません。

パイプラインではスケジューリングの責務を切り分ける

クラウドMacでは、まずグラフを検証し、その後で時間のかかるビルドステップに進みます。ゼロ以外の終了コードをそのまま伝え、分単位のタスクを開始する前に依存関係の設定ミスを検出できるようにします。実行側が停止してから気づくのでは遅すぎます。

この実装は反復のたびに実行可能なタスクの配列をソートし直すため、規模が限られたアプリのタスクグラフに適しています。ノード数が増えたら最小ヒープに置き換えられますが、辞書順で選択するという契約は維持し、既存のテストを再利用して結果を比較してください。

実際に並列実行する場合、後続タスクの未完了依存数を減らせるのは、前提タスクが正常に完了したときだけです。失敗、キャンセル、リトライにはそれぞれ別の状態が必要であり、トポロジカル順序の添字から推測してはいけません。最終的な検証では、入力の異常を説明できること、正しいグラフでは順序が安定すること、実行側が依存関係を早まって解消済みにしないことを、同時に満たす必要があります。これにより、別のビルドノードへ移しても、偶然の順序をリリース工程に持ち込まずに済みます。

よくある質問