ビルドの模型

次の組をビルドの記述という。

• 有限集合 $I$（入力。人が書くソースファイルの名前）と有限集合 $T$（タスク。生成されるファイルの名前と同一視する）。$I \cap T = \emptyset$ とし、$N = I \cup T$ とおく。
• 値の集合 $\mathcal{V}$（ファイルの内容になりうるバイト列の全体）。
• 各タスク $t \in T$ に、宣言された依存 $D(t) \subseteq N$。

有向グラフ $G = (N, E)$、$E = \{(u, t) : t \in T,\ u \in D(t)\}$ を依存グラフという。辺 $(u, t)$ は「$t$ を作るのに $u$ を読む」ことを表す。以下では依存グラフが DAG であるものだけを考える。

写像 $x : I \to \mathcal{V}$ を入力の状態、写像 $s : N \to \mathcal{V}$ をストア（作業ディレクトリの中身）という。タスク $t$ を実行するとは、ストア $s$ の $t$ の値だけを書き換えて新しいストアにする操作である。