プログラミング

サイコロを振るビルドグラフ

A build graph that rolls dice (fzakaria.com)

14 pointsby ingve2026年9月21日2 コメント

要約

この記事では、Nixの「動的導出」という概念を探求し、ビルドグラフがビルドの進行中に定義される「モナディック」な性質を持つことを説明しています。これは、ビルドの次のステップが以前のステップの結果に依存できることを意味し、サイコロを振ってビルドの深さをランダムに決定する例を用いて、その動的な性質をデモンストレーションしています。

全文翻訳

サイコロを振るビルドグラフ

NixCon 2026が間近に迫っています。今年も残念ながら私は参加できません。

ラインナップを見ていると、動的導出に関する多くの講演があり、最近のcargo-dyndrvのような記事も目にしました。これらは、私が以前の投稿や投稿でこのトピックに触れて以来、再考するきっかけとなりました。

動的導出がビルドグラフにどのような影響を与えるかをより深く理解したいと思いました。当初は、これがlang2nixスタイルのビルドグラフ生成をどのように置き換えられるかに焦点を当てていましたが、その影響はそれよりもはるかに広範であることに気づきました。

グラフは事前に知る必要はありません。ビルドが進むにつれて定義することができます。🧐

どういう意味でしょうか？

従来、Nixは何かをビルドするように要求すると、ビルドグラフを構成する「導出（derivations）」として、事前にどのような手順を踏むかを正確に教えてくれます。

$ nix-store -q --requisites \
    $(nix-instantiate '<nixpkgs>' -A hello) | grep -c '\.drv$'
196

これはNixの重要な特性です。ビルドを実行せずに、何がビルドされるかを理解することで、ビルドについて推論することを可能にします。

多くのNixツールは、nix build --dry-runを通じてこの特性に依存しています。例えば、nix-diffは、ビルドすることなく、2つのクロージャがどのように異なるかを教えてくれます。

なぜ動的導出がこれを変えるのでしょうか？

Applicative、monadic、bind

関数型言語では、「applicative」や「monadic」のような派手な言葉を使って計算の種類の違いを説明するのは非常に簡単です。その違いは微妙ですが、深遠です。

Nixは従来、「applicative」なビルドシステムでした。動的導出はそれを「monadic」なビルドシステムに変えます。違いは、applicativeなビルドシステムではビルドグラフ全体が事前に知られているのに対し、monadicなビルドシステムではビルドが進むにつれてグラフを定義できるという点です。11このトピックに関するデファクトスタンダードな読み物は、論文Build Systems à la Carteです。

この違いを考える一つの方法は、それらを定義する2つの操作の型シグネチャを見ることです。

<*> apply :: f (a -> b) -> f a          -> f b
>>= bind  :: m a        -> (a -> m b)   -> m b

apply (applicative) は、事前に知られている値 f a を受け取り、結果 f b を返します。実行前にグラフ全体を見ることができます。

bind (monadic) は、結果 m b を返す関数 (a -> m b) を受け取ります。実行前にグラフ全体を見ることはできません。

Applicativeは、家を出る前に買い物リストを書くようなものだと考えることができます。レシピを読み、全ての材料を書き出し、一度店に行きます。リストはレシピの関数であり、それ以外の何ものでもありません。

Monadicは、「味を見て、塩辛すぎたらポテトを買いに行く」というステップを含むレシピのようなものです。その買い物リストを事前に書くことはできません。ポテトがリストにあるかどうかは塩加減に依存し、塩加減は調理の一部をすでに終えるまで存在しません。

Nixはかつては専ら前者でしたが、動的導出は後者を追加します。

実際、Nixには常にbindがあった

［画像: always has been bind meme］

さて、おそらく「Nixはスケジューラにおいてモナディックになった」と言うべきだったでしょう。Nixには常に評価器（evaluator）の中にbindがありました。私たちは何年もモナディックなビルドを行ってきました。それを導出からのインポート（import from derivation）と呼んでいます。

let
  inner = pkgs.runCommand "inner" {} "sleep 10; echo hi > $out";
in
  pkgs.runCommand "outer" {} "echo ${builtins.readFile inner} > $out"

導出の出力に対するbuiltins.readFileは、まさに上記の意味でのbindです。次に何をビルドするかは、まだ存在しない値の関数です。Nix評価器は、その値なしではグラフを生成できません。そして、それを取得する唯一の方法は、評価を停止してビルダーを実行することです。

残念ながら、これには nix-instantiate が10秒かかるといった多くの落とし穴があり、なぜnixpkgsがこのテクニックを完全に禁止しているのかという理由にもなっています。

一方、導出からのインポートは評価器におけるbindですが、動的導出は現在スケジューラにbindを追加します。違いは、スケジューラがビルダーを並列実行したり、リモートマシンに送信したり、キャッシュから結果を置き換えたりできることです。評価器はそれらのどれもできません。

動的導出はbindを追加するわけではありません。bindは常に存在していました。変わったのは、それを実行するレイヤーです。🤓

サイコロを振ってみよう

動的導出の例の多くは、lang2nixツールを通じたビルドグラフ生成に焦点を当てていましたが、より一般的な意味での動的導出の影響を探求したいと思いました。

真のmonadicな意味では、ビルドグラフはビルドの進行中に定義できます。ビルドグラフの次のステップは、前のステップの結果に依存する可能性があります。

ここに非常にシンプルな例、chain.nixとstep.shがあります。これはサイコロを振り、ビルドを停止するか、新しい導出ステップをビルドグラフに追加してチェーンを続行します。チェーンの深さはランダムであり、ビルドの結果はその深さです。

nix-instantiateを実行すると、左端のボックスだけが存在します。その右側にあるものは全て、ビルドがすでに進行中にビルダーによって書き込まれます。

cluster_eval in chain.nix cluster_run written by step.sh, mid-build step step-N roll a d6 res dice-result echo N > $out step->res six pass passthrough-N cp $inner $out step->pass anything else next step-N+1 depth + 1 pass->next input: ^out^out more … next->more

chain.nixを表示

{
  depth ? 1,
  pkgs ? import <nixpkgs> { },
  bash ? pkgs.bash,
  coreutils ? pkgs.coreutils,
  nix ? pkgs.nixVersions.latest,
  chain ? ./chain.nix,
  step ? ./step.sh,
}:
let
  roller = derivation {
    name = "step-${toString depth}.drv";
    system = builtins.currentSystem;
    builder = "${bash}/bin/bash";
    args = [ "-e" "${step}" ];

    DEPTH = toString depth;
    BASHPKG = "${bash}";
    COREUTILS = "${coreutils}";
    NIXPKG = "${nix}";
    CHAIN = "${chain}";
    STEP = "${step}";
    PATH = "${coreutils}/bin:${nix}/bin";

    # ビルダーは導出をインスタンス化するため、通信するためのストアが必要です。
    requiredSystemFeatures = [ "recursive-nix" ];

    # この導出の出力は.drvファイルです。これが動的である理由です。
    __contentAddressed = true;
    outputHashMode = "text";
    outputHashAlgo = "sha256";
  };
in
builtins.outputOf roller.outPath "out"

step.shを表示

set -eu
export NIX_CONFIG='experimental-features = nix-command ca-derivations dynamic-derivations'

roll=$(( $(od -An -N1 -tu1 < /dev/urandom) % 6 + 1 ))
echo "depth $DEPTH rolled a $roll"

if [ "$roll" -eq 6 ]; then
  # 6が出た。終了。答えは到達した深さです。
  cat > answer.nix <<NIX
let bash = builtins.storePath $BASHPKG; in
derivation {
  name = "dice-result";
  system = builtins.currentSystem;
  builder = "\\
${bash}/bin/bash";
  args = [ "-c" "echo $DEPTH > \\$out" ];
  __contentAddressed = true;
  outputHashMode = "recursive";
  outputHashAlgo = "sha256";
}
NIX
else
  # 6ではない。私の答えは次のレベルが答えるものになります。
  cat > answer.nix <<NIX
let
  bash = builtins.storePath $BASHPKG;
  coreutils = builtins.storePath $COREUTILS;

  # これがbindです。次の深さをchain.nixに要求することは、それをビルドも評価もせず、
  # "depth $(( DEPTH + 1 )) が最終的に答えるもの" を表すプレースホルダーを生成します。
  inner = import (builtins.storePath $CHAIN) {
    inherit bash coreutils;
    depth = $(( DEPTH + 1 ));
    nix = builtins.storePath $NIXPKG;
    chain = builtins.storePath $CHAIN;
    step = builtins.storePath $STEP;
  };
in
derivation {
  name = "dice-passthrough";
  system = builtins.currentSystem;
  builder = "\\
${bash}/bin/bash";
  args = [ "-c" "cp \\$inner \\$out" ];
  PATH = "${coreutils}/bin";
  inherit inner;
  __contentAddressed = true;
  outputHashMode = "recursive";
  outputHashAlgo = "sha256";
}
NIX
fi

cp "$(nix-instantiate answer.nix)" "$out"

この導出の一般的なアイデアは次のとおりです。

6を振ると、深さをエコーする導出を書き込みます。これは通常の、動的な要素はありません。これによりビルドグラフが終了します。
それ以外を振ると、パススルーを書き込みます。これは、innerがimport chain.nix { depth = n + 1; }であるような、cp $inner $outのみを行う導出です。

どちらの場合も$outにコピーされるファイルは.drvファイルなので、builtins.outputOfは停止したチェーンと継続したチェーンで同じように機能します。22無限再帰を避けるため、また導出のストアパスがコンテンツアドレス指定されているため異なるようにするために、実際には深さパラメータが必要です。

ビルドが進むにつれて、デノミネーターでビルドグラフが成長するのを見ることができます。

[画像: A terminal running nix build on the dice chain. The progress counter starts at one derivation and climbs past fifty as each level emits the next one。]（ダイスチェーンでnix buildを実行しているターミナルの画像。プログレスカウンターは1つの導出から始まり、各レベルが次の導出を出力するにつれて50を超えて上昇します。）

--dry-runまたはnix-store -q --treeでグラフを調査しようとすると、何も得られません。グラフはまだ不明なため、ツールはそれを認識できません。

$ nix build --store /tmp/dice -f ./default.nix --dry-run
warning: Ignoring dynamic derivation /nix/store/vnm4l32g…-step-1.drv.drv^out
while querying missing paths; not yet implemented

動的導出は第二のグラフを導入しますが、これはビルド後にのみ存在し、エコシステムはまだそれを調査する方法を持っていません。

ビルドを900回実行し、チェーンの長さを記録しました。6面サイコロを振ることは、幾何学的減衰をシミュレートする最も古典的な方法の1つであり、その結果を以下のヒストグラムで見ることができます。平均は6.18、中央値は4、最長は46でした。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 0 10 20 30 40 0 50 100 150 derivations in the chain runs out of 900

数学は数学です

lang2nixを超えて

私のものを含む、これまでの全ての動的導出のデモはビルドシステムでした。C言語用にはMakeNix、Node.js用にはNpmNix、Rust用にはcargo-dyndrv、Ninja用にはnix-ninjaです。これらは良い出発点ですが、プリミティブの完全な力を捉えているわけではありません。他にどのようなアイデアを探求できるでしょうか？

マリオ。 Super Mario Derivationsでは、属性パスがボタンのシーケンスであり、私は押す回数を提供する必要があります。動的なバージョンはマリオが死ぬまでエミュレートします。停止条件はデータであり、ビルド中に発見され、実行はそれが判明するまでの長さになります。

状態空間の探索。サイコロを述語に置き換えると、各フロンティアノードが導出となる探索になります。モデル検査、パズルソルバー、新しいカバレッジを見つけた入力のみを展開するファザー。2回到達した状態は1つのストアパスに収束し、再起動後も存続します。

クロール。ページを取得し、リンクを解析し、リンクごとに1つの導出を出力します。フロンティアは宣言されるのではなく発見され、ストアは既に取得された全てのページを記憶しているためクロールが再開され、結果の依存関係グラフはリンクグラフになります。

このプリミティブの限界は何でしょうか？私には分かりません。

グラフのサイズは、Nixが後続の導出を生成し続けるかどうかによってのみ制限されます。ストアレイヤーには深さの制限はなく、max-call-depthのようなものもありません。サイコロ投げで最長だった正直なチェーンは深さ46でしたが、500まで行った仕掛けのある例もありました。どこまで行けるでしょうか？

ビルドシステムを始める前に計画を立てることに、私はあまりにも洗脳されているため、その場で計画を立てるという考えは少し怖いと感じます。😨