読者です 読者をやめる 読者になる 読者になる

Makefileの中でファイルを依存関係順に並び替えて結合する / Topological sorting

Makefile

複数のファイルを結合して一つのソースコードに結合したい.

cat src/*js > output.js

\(^o^)/ おわたー

でもでも,

ファイルに依存関係があったらどうしよ.

例えば,

file1.js -> file2.js -> file4.js -> file3.js -> file5.js

のように依存していたら?

file1.jsがfile2.jsに依存, file2.jsの方を先に読み込まないといけないと?

cat src/file5.js src/file3.js src/file4.js src/file2.js src/file1.js > output.js

何にも依存していないfile5.jsから書きこめばおk!!!

でもでもいちいちコマンド打つのが面倒だから, Makefile

SOURCE = src/file5.js src/file3.js src/file4.js src/file2.js src/file1.js
TARGET = output.js

$(TARGET): $(SOURCE) Makefile
	@cat $(SOURCE) > $@

でいいよね.

じゃなくて,

じゃぁfile1.jsがfile4.jsとfile3.jsに依存していて, file2.jsがfile3.jsにも依存していて, しかもfile4.jsは実はfile3.jsじゃなくてfile5.jsに依存していたら...

それでもMakefileに順番を間違えずにファイル名を並べますか?

僕はいやです. 依存関係を自動化して順番を並べてcatしたい.

これ, そんな難しいことじゃなくて, 色々調べてたら一日もかからずに出来ました!

JsDoc Toolkit風に依存関係をファイルに書く

僕はJavaScripterのハシクレなので, JavaScriptで書きます.
だけど, このエントリーの内容は主にMakefileであって, JavaScriptとはちがう言語でも適用できると思います.
ただ, catする順番で動作が変わりうる言語ならば, そして, ファイルを結合することに意味がある言語の話ですが...
JavaScriptを書くにあたって, 僕はJsDoc Toolkit*1を用いています.
ってことで, JsDoc Toolkit風に依存関係を書きます. 例えば,

 $ cat src/file1.js
/**
 * @fileOverview file1.js だよ!よ!
 * @name file1.js
 * @requires file3.js
 * @requires file4.js
 */
function file1 () { }

依存するファイルを@requiresに続けて書きます.

今回使う全てのファイルは, こんな感じ.

 $ cat src/*.js
/**
 * @fileOverview file1.jsだよ
 * @name file1.js
 * @requires file3.js
 * @requires file4.js
 */
function file1 () { }

/**
 * @fileOverview file2.jsだよ
 * @name file2.js
 * @requires file1.js
 * @requires file3.js
 * @requires file5.js
 */
function file2 () { }

/**
 * @fileOverview file3.jsだよっ
 * @name file3.js
 * @requires file5.js
 */
function file3 () { }

/**
 * @fileOverview file4.jsだよ!!
 * @name file4.js
 * @requires file5.js
 */
function file4 () { }

/**
 * @fileOverview file5.jsだよ
 * @name file5.js
 */
function file5 () { }

 $

依存関係をグラフにするとこんな感じです.

これくらいなら自分で順番に並べることができて,

SOURCE = src/file5.js src/file3.js src/file4.js src/file1.js src/file2.js

の順番か,

SOURCE = src/file5.js src/file4.js src/file3.js src/file1.js src/file2.js

の, どちらの順番でもOKです. どちらでもというのは, file3.jsとfile4.jsの順番はどっちを先に読んでも構わないってことですね.


では, ソースコードからどうやってこの順番に「自動で」並べましょう?

色々ぐぐってみると, きちんとこういうのには名前が付いていることが分かりました. まぁそりゃそうですよね...

Topological sorting - Wikipedia, the free encyclopedia (日本語版は トポロジカルソート - Wikipedia)

トポロジカルソート...

アルゴリズムも載ってるし, 書いてみるかーって思ってたら,

「See also : tsort, a Unix program for topological sorting 」

なんだってーーー!

コマンドになってるんですね...

tsort - Wikipedia, the free encyclopedia

おおお, まさにこれですね これこれ!!! コマンドにあるなら, 全部Makefileの中で完結する!!!


tsortコマンドを試そう

早速自分でもコマンドを叩いてみましょう.

 $ echo "
dquote> 1 2
dquote> 2 4
dquote> 4 3
dquote> 3 5
dquote> " > test.txt
 $ cat test.txt

1 2
2 4
4 3
3 5

 $ cat test.txt | tsort
1
2
4
3
5
 $

ううむ... いっぱい依存している方から出力されるのね...

さっきの, ややこしい方も確かめてみよう.

 $ cat test.txt

1 3
1 4
2 1
2 3
2 5
3 5
4 5

 $ cat test.txt | tsort
2
1
4
3
5
 $

おおおっ!

さっきの, 1つ目の順番ですね! (ただ逆だけど...) グラフの下から表示されてる.

後は, ソースコードから依存するファイル名を読み込んでtsortに投げて, 逆順でcatすればよさそうです!!!


早速Makefileを書いてみよう

ターゲット名は, 取り敢えずsolve-dependencyとでもしておきましょう.

最初

SOURCE = $(wildcard src/*.js)
solve-dependency: $(SOURCE) Makefile
	@cat $(SOURCE)

(Makefileをどんどん編集していきたいから依存の右側にMakefileを...)


ゴールを考えておきましょう. tsortには,

file1.js file3.js
file1.js file4.js
file2.js file1.js
file2.js file3.js
...

の形式で渡せば, 順番に帰ってくるってことがさっきので分かってます. (tsortには, 数字でなくても文字でもいけます)

左側が元のファイル, 右側が依存相手です.

まずはforeachとshellを使ってcatしてみます. (以後SOURCEは省略します)

solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE),$(shell cat $(file) | grep "@requires"))
 $ make solve-dependency
Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file3.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file4.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file1.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file3.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file5.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file5.js Makefile blog.txt complicated.png five.png graph.dot src test.txt @requires file5.js
 $

ううん???

え, なんでcomplicated.pngとかさっき作った画像がでてるんですか!!!

これは,

 * @requires file4.js
 ↑
 このスター

が展開されちゃってるんですね, はぁ...

じゃぁsubstで置換すればいいじゃない

solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE), $(subst *,,$(shell cat $(file) | grep "@requires")))
 $ make solve-dependency
@requires file3.js @requires file4.js @requires file1.js @requires file3.js @requires file5.js @requires file5.js @requires file5.js
 $

お, マシになった. @requiresを置換してみよう.

SOURCE = $(wildcard src/*.js)
solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE), \
	$(subst @requires ,"\n",  \
		$(subst *,, \
			$(shell cat $(file) | grep "@requires"))))
 $ make solve-dependency

file3.js
file4.js
file1.js
file3.js
file5.js
file5.js
file5.js

おっ??? それぞれのファイルは, foreachのなかで$(file)で参照できますよ. 例えば

SOURCE = $(wildcard src/*.js)
solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE), \
		"\n"$(file)"は次のファイルに依存します:"$(subst @requires ,"\n",  \
			$(subst *,, \
				$(shell cat $(file) | grep "@requires"))))

(ここで敢えてSOURCEを書いたのは, SOURCE = src/*.js だと上手くいかないよってことです)

 $ make solve-dependency

src/file1.jsは次のファイルに依存します:
file3.js
file4.js
src/file2.jsは次のファイルに依存します:
file1.js
file3.js
file5.js
src/file3.jsは次のファイルに依存します:
file5.js
src/file4.jsは次のファイルに依存します:
file5.js
src/file5.jsは次のファイルに依存します:
 $

ごっつぇえ感じや!

ってやりたいのは, tsortに渡すことでしたね.

solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE), \
		$(subst @requires ,"\n$(file) ",  \
			$(subst *,, \
				$(shell cat $(file) | grep "@requires"))))
 $ make solve-dependency

src/file1.js file3.js
src/file1.js file4.js
src/file2.js file1.js
src/file2.js file3.js
src/file2.js file5.js
src/file3.js file5.js
src/file4.js file5.js
 $

src/を付けて

solve-dependency: $(SOURCE) Makefile
	@echo $(foreach file,$(SOURCE), \
		$(subst @requires ,"\n$(file) src/",  \
			$(subst *,, \
				$(shell cat $(file) | grep "@requires"))))
 $ make solve-dependency

src/file1.js src/file3.js
src/file1.js src/file4.js
src/file2.js src/file1.js
src/file2.js src/file3.js
src/file2.js src/file5.js
src/file3.js src/file5.js
src/file4.js src/file5.js
 $ make solve-dependency | tsort
src/file2.js
src/file1.js
src/file4.js
src/file3.js
src/file5.js
 $

できたー!

んーでも, catしたいのはこれと逆の順番だから,

 $ make solve-dependency | tsort | tail -r
src/file5.js
src/file3.js
src/file4.js
src/file1.js
src/file2.js
 $

よっしゃー!!! この順番に読み込んだら, 確かに依存関係が解決されて結合できますね! もっかいグラフをここに貼っときます! あってますよね!

あとは, これをMakefileにいれて (シェルの作業をMakefileにいれるのは$(shell です.

solve-dependency: $(SOURCE) Makefile
	@echo $(shell echo $(foreach file,$(SOURCE), \
		$(subst @requires ,"\n$(file) src/",  \
			$(subst *,, \
				$(shell cat $(file) | grep "@requires")))) | tsort | tail -r)
 $ make solve-dependency
src/file5.js src/file3.js src/file4.js src/file1.js src/file2.js
 $

あとはcatして終わりです!

まとめ

SOURCE = $(wildcard src/*.js)
TARGET = output.js
$(TARGET): $(SOURCE)
	@cat $(shell echo $(foreach file,$(SOURCE), \
		$(subst @requires ,"\n$(file) src/",  \
			$(subst *,, \
				$(shell cat $(file) | grep "@requires")))) | tsort | tail -r)  \
				> $@
 $ make output.js
 $ cat output.js
/**
 * @fileOverview file5.jsだよ
 * @name file5.js
 */
function file5 () { }

/**
 * @fileOverview file3.jsだよっ
 * @name file3.js
 * @requires file5.js
 */
function file3 () { }

/**
 * @fileOverview file4.jsだよ!!
 * @name file4.js
 * @requires file5.js
 */
function file4 () { }

/**
 * @fileOverview file1.jsだよ
 * @name file1.js
 * @requires file3.js
 * @requires file4.js
 */
function file1 () { }

/**
 * @fileOverview file2.jsだよ
 * @name file2.js
 * @requires file1.js
 * @requires file3.js
 * @requires file5.js
 */
function file2 () { }

 $
 $ tree .
.
├── Makefile
├── blog.txt
├── complicated.png
├── five.png
├── graph.dot
├── output.js
├── src
│   ├── file1.js
│   ├── file2.js
│   ├── file3.js
│   ├── file4.js
│   └── file5.js
└── test.txt

1 directory, 12 files
 $


わぁい Makefile! あかり Makefile 大好き!


追記:
dotファイルを吐くようにしてみました.

SOURCE = $(wildcard src/*.js)

DOTOUTPUT = graph.dot
graph.png: $(SOURCE)
	@echo "\
		digraph graph {\n\
			graph [\n\
				concentrate = true,\n\
			];\n\
			node [\n\
			];\n\
			edge [\n\
				arrowsize = 1,\n\
				arrowhead = vee\n\
			];\n\
		" > $(DOTOUTPUT)
	@echo $(foreach file,$(SOURCE), \
		$(subst js,"js\"",  \
			$(subst @requires ,"\n\"$(subst src/,,$(file)) -> \"",  \
				$(subst *,, \
					$(shell cat $(file) | grep "@requires")))))  \
						>> $(DOTOUTPUT)
	@echo "}" >> $(DOTOUTPUT)
	@dot -Tpng $(DOTOUTPUT) -o $@


さっきと上下逆だけど許してw

追記:
どのファイルにも依存されてないし依存してないファイルがあるときは問題があるなぁ...
まぁ今扱ってるプロジェクトのファイルは, 一つのディレクトリー内ではどのファイルも必ず誰かに依存するか依存されているかのどっちかは必ずあるから, 問題ないっ( ー`дー´)キリッ

追記[2011/02/12]:
tail -rはない環境があるんだよなぁって言っていたら,

と言われたので, ああたしかになぁと, 感心してしまいました.
逆転の発想.

SOURCE = $(wildcard src/*.js)
TARGET = output.js
$(TARGET): $(SOURCE)
	@cat $(shell echo $(foreach file,$(SOURCE), \
		$(subst @requires ,"\n src/", \
			$(subst js$,js  $(file),$(subst *,, \
				$(shell cat $(file) | grep "@requires" | grep "js$$"))))) | tsort)  \
				> $@