しょうもない実力者の正体：アルゴリズム - (保存用) 檜山正幸のキマイラ飼育記メモ編

公式マニュアルを見てもどこを探してもmakeが使っているアルゴリズムの記述が見つからない。誰もマトモに解説しようとしない。実験と予測の結果をメモしておく。

結局、実行すべきレシピ列（並列実行ならレシピツリー）を、与えられたゴールとルールセットと“ワーキングメモリであるファイルシステム”から決定し実行するソフトウェアである。実行によりワーキングメモリであるファイルシステムは書き換えられる（ことが多い）。実行中のファイルシステムの変更は各レシピの実行環境に影響するが、レシピ列の構築（＝実行計画の作成）は終わっているので、レシピ列の構造には影響を与えない。

与えられたゴールノードをルート（ビルドフローの向きからは吸い込みノード）とするDAGを、ゴールから逆向きに作成し、実行は上流（ゴールから遠い所）から始める。直列実行なら、スタックによる呼び出し系列と考えてもよい。

DAGの作成アルゴリズム：

gを与えられたゴールとする。gは単なる名前。
gと文字列マッチするターゲットを持つルールをルールベースから探す。
まず、明示ターゲット（具体的な名前）とのマッチが試みられる。
マッチする明示的なターゲットがないときは、パターンターゲットを探す。
パターンターゲットにもマッチしないときは、ソースと解釈してファイルシステムで存在確認。
すべてのマッチが失敗すればエラー終了
ファイルシステムで存在するが、ルールを持たない（ターゲットではない）場合はそれをソースとしてマークする。ソースは当然に前提を持たない。
マッチしたルールの前提を展開する。
前提のそれぞれを新しいゴールとして同じ手順を適用する。
展開すべき前提がなくなるまで繰り返す。
エラーでないときは、DAGが出来上がる。
DAGのノードはターゲット（タスクかも知れない）またはソース（実在するリソース）としてマークされている。DAGのターゲットノードには、対応するレシピが割り当てられる。レシピが存在しなくても空であってもエラーではない。

要処理かどうかの判断アルゴリズム：

ソースノードはターゲットではないので、要処理はあり得ない。
ターゲットノードが.PHONYで登録されたタスクノードなら問答無用に要処理とマークする。
ターゲットノードがファイルシステムに存在しなければ要処理とマークする（タスク扱い）
ターゲットノードの前提ノードのなかに、ターゲットノードより新しいものが1つでもあれば要処理。
要処理とマークされたノードの下流（依存したノード）はすべて要処理とマークする。

DAGの実行アルゴリズム：

※「警告」とは「Nothing to be done for ゴール」のこと

DAGがソースノードのみなら警告して終了
DAGのターゲットが要処理であるかをファイルシステムと照合してマークする。（マークのアルゴリズムは前述。）
要処理とマークされたノードを、上流に近いほうから直列または並列に実行する。
レシピがエラーを返したときはそこで中断する。

警告メッセージ：

ターゲットにレシピがあるかどうかは問題にしない。

最初に指定されたゴールにレシピがないときは警告する。上流のレシピは警告の対象にはならない。指定されたゴールの上流がすべてレシピなしでも警告はしない。

エラーの判定：

ソースノード（ターゲットにならないが前提となるノード）だけがリソースとしての存在を要求される。与えられたゴールから作ったDAGのソースノードが非存在のときだけDAG生成時のエラーとする。注意：.PHONY指定された名前はソースノードとは解釈しない。

書いていてイヤになる。腐っている。しかし、うまく動く。そして代替がない。悲劇だ。