makeのアルゴリズム
Sunrise Advent Calendar 2019 の 22 日目に飛び入り参加しました．
Sunrise とは VOYAGE GROUP のエンジニア向けインターンです．
『大規模リクエストを捌きつつ安定して価値を出し続ける広告プラットフォームを構築せよ！』
というミッションの解決を，実際の業務と近いプロセスで体験することができました． 詳しくは 6 日目の振り返り記事などが参考になるかと思います．
なぜ make のお話？
このアドベントカレンダーの内容はごった煮で OK らしいのですが，どうせなら少しはインターンに関係する内容にしようかと思ったためです．
make とインターンの関係
VOYAGE GROUP の中では make の普及率が高いようで，「えっそんなことも Makefile で書いちゃうの？」ってことも多いとか．
make は本来ビルド自動化のためのツールですが，今回のインターンではビルド作業以外にも，初回の環境構築や，AWS へのデプロイ作業が 1 コマンドで済むように Makefile が用意されていました．
Ajito という社内バーではエンジニア同士でよく make の話題で盛り上がっているとか？[要出典]
ネタ選びの裏事情
実はつい最近，make で使われているアルゴリズムに関する話を学内 LT で発表していたりしました．
一度発表している内容ならブログ書くのも楽そうですし．
LTの発表資料をアップしました #静大情報LThttps://t.co/oxgwWrm8t7
— さのぴー (@san0py) 2019年10月29日
ということで，以下の内容は学内 LT での発表をブログ形式にしたものです．
make に使われるアルゴリズム
皆さん依存関係がいっぱいあるような Makefile がなぜいい感じにビルドできているのか疑問に思ったことはありませんか？
その疑問の答えは次の通りです．
聞き慣れない言葉がいっぱいありますね．順番に解説していきます．
DAG とは
DAG は Directed Acyclic Graph の頭文字を取ったもので，日本語では有向非巡回グラフ などと呼ばれます．
何やら難しそうに聞こえますが次の 2 つの特徴を持っているグラフという認識さえあれば OK です．
- 有向グラフである
- 閉路が存在しない
トポロジカルソートとは
トポロジカルソートは DAG をソートするアルゴリズムです．でもグラフをソートするってどういうことでしょう？
実は DAG には，「ノードを横一列に並べたとき，エッジの方向を揃える並べ方」というものが存在します（画像参照）．
この並べ替えを行うのがトポロジカルソートです．
ちなみに「ノードを横一列に並べたとき，エッジの方向を揃える並べ方」というのは複数通り存在しうるものなので，トポロジカルソートの結果は一意であるとは限りません．
トポロジカルソートの実装
実装が難しそうですね．どうやって実装するのでしょうか？
実はトポロジカルソートは深さ優先探索を使って簡単に実装することができてしまいます．
実装に関する詳しい話はWikipediaに擬似コード込みで詳しく書かれているので，興味がある人はこちらを参照するといいと思います．
make とトポロジカルソート
ここからの話は自分の憶測が含まれているので，厳密には make と違う部分があるかもしれません．
（今回は簡単のため，タイムスタンプを見て変更のあるファイルのみコンパイルみたいなことは考慮してなかったりします．）
DAG の生成
次のような Makefile が与えられたときに，make が何を行っているのか具体的に追ってみましょう．
A: A.c … B: A … C: A B … D: E … E: E.c …
Makefile は実質 DAG なので，グラフとして表現すると次のようになります．
トポロジカルソートの実行
先程の DAG に対してトポロジカルソートを適用すると次のようになります．
あとはやるだけ
ソート結果のグラフの左側のノードから順番にビルドすることで，依存解決が可能となっています．
ということで，Makefile の依存関係をトポロジカルソートを用いることで解決することができました．
トポロジカルソートは Makefile 以外にもスケジューリングの問題の解決などにも利用されています．
