チームラボ天下一武道会

チームラボ天下一武道会 ~コードGolf & F1レース!~ : ATND
に参加してきました。普段Java使っていないのでどうなるかと思いましたが、なんとか優勝することができました。

問題は、ユーザデータと商品の購入データが与えられるので、全商品間のコサイン類似度を求めよというものでした。入力は

<ユーザID>,<商品ID>

CSVで与えられ、出力は商品ID×商品IDの二次元配列をCSVで出します。購入データは1万件、ユーザ数は1000以下、商品数は500以下という制限です。

順位は、実行時間によるスコアとバイトコードのサイズによるスコアの和によって付けられます。それぞれ50点満点で、実行時間は

  • 10秒 (50点)
  • 60秒 (0点)

バイトコードのサイズは、

  • 1Kbyte (50点)
  • 6Kbyte (0点)

を基準として、線形補完されて決まります。50点満点ですが、基準値を超えた場合は60点まで加点されるとのことでした。

最初問題聴いたときは、効率のいい疎行列計算しろってことなのかなとか思ったのですが、入力データはそんなに疎ではないらしいし(と思ったけど、500*1000=5万と勘違いしてたようでした)、そもそも密行列で持ってばかな方法でも 500^5*1000 = 2500万 ぐらいの計算量で済むので、10秒どころか1秒もあれば余裕ではないのかと思いました。Rで計算すると60秒ほどかかるそうなのですが、それの6倍速が上限というのは緩かった気がします(しかしこれ以上短くすると、JVMの起動時間が無視できなくてあれかもしれない…)。そういうわけで、時間は多分緩いけど、バイトコードサイズ1KBは相当厳しそうに見えたので、純ゴルフ勝負になりそうな予感でした。

まずは適当に組んでみますと、実行速度は手元で2.5秒ほどで、やっぱりそんなにかからない。バイトコードサイズは2.8KBほどで、これをどこまで縮められるかという感じ(そもそも空のクラスでも300バイトぐらいあるんですよ)。まあしかし、普段Javaでコード書かないものですから、Javaの重箱仕様やら、ましてやJVMのことなんかよくわからない。どうやれば小さくなるかなんて皆目見当もつきませんでしたが、とりあえず小さくなりそうなことをひとつずつやっていきました。

  • ローカル変数名の長さはバイトコードサイズとは無関係
  • 使っているクラス数を減らすとガクッとサイズが減る(TreeMapはMapじゃなくてTreeMapで受けるべし、とか)
  • 使っているメソッド数を減らすとサイズが減る(メソッドごとに文字列で参照情報が入るのだろうか?)
  • 改行を消すと縮む場合がある(多分デバッグのための行番号の情報)
  • メソッドの引数名の長さはバイトコードサイズに影響
  • try catch より throwsのほうが短い
  • 変数宣言はまとめたほうが短い
  • forの宣言部などに入れられるものは入れたほうが短い
  • 複雑な式を関数の引数に入れるとなぜかでかくなる
  • importはバラでやったほうが若干短い

そういうわけで、こつこつ短くしていきました。最初はどんな入力がきても大丈夫なように作っていたのですが、入力が決まっているので、配列長決めうちにしてArrayListから配列に変えたり、ユーザIDと商品IDはぬけがある時のためにTreeMapを用いて内部IDに変換していたのをやめて、ちょっと計算は無駄になるけどぬけてるとこも計算しちゃうとか、出力は対象行列になるから上半分だけ計算していたのを、どうせ計算にはそんなに時間掛からないからすべて計算することにしたり(データを保存しておくための配列が要らなくなる)、入力を読みながら隣接行列構築するなど、許容される範囲で速度を遅くしつつ、コードを簡略化していくという作業を続けた結果、速度3秒(評価環境では5秒ぐらい?)、バイトコードサイズ1390バイトぐらいにまで縮みました。コードのサイズでいうと、最初は80行ぐらいあったのが、最終的には25行ぐらいになりました。

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
class cosine{
    public static void main(String[] a) throws Exception{
	BufferedReader br = new BufferedReader(new FileReader(a[0])); br.readLine();
	PrintWriter pw = new PrintWriter("output.csv");
	double[][] tbl = new double[512][1024];

	for (String line;(line=br.readLine())!=null;) tbl[new Integer(line.split(",")[1])][new Integer(line.split(",")[0])]++;

	for (int i=0; i<512; i++){
	    double ni=0; for (int k=0; k<1024; k++) ni += tbl[i][k]*tbl[i][k];
	    if (ni>0){
		int t=0;
		for (int j=0; j<512; j++){
		    double nj=0, nc=0;
		    for (int k=0; k<1024; k++){ nj += tbl[j][k]*tbl[j][k]; nc += tbl[i][k]*tbl[j][k]; }
		    if (nj>0){ if (t!=0) pw.printf(","); t=1; pw.printf("%.2f", nc/Math.sqrt(ni*nj)); }
		}
		pw.printf("\n");
	    }
	}
	pw.close();
    }
}

提出したコードからすぐ気付いた良くない個所が直してあるので、若干短くなっています。時間いっぱいまで頑張っていたので、まだまだ縮むとは思います。1KBを切りたかったのですが、これはちょっと難しいかもしれません。最初からこれぐらい割り切ったコードを書いていればよかったのかもしれませんが、Javaの速度感覚が無かったのが駄目でした。

バイトコードサイズでのゴルフはやったことがなかったのですが、なかなか楽しかったです。コードサイズは書いたままがスコアですけど、バイトコードサイズはコンパイラの気分次第で、コンパイルするまで縮むか分からないので、コンパイルが毎回どきどきです。

残り10分ぐらいの時に検証用データの最終版がもらえたのですが、なかなか手元で出力が合わなくて、うわあこれはだめぽ、みたいな状態でサブミットしたので、懇親会中は気が気ではなかったです。でも他の人たちもみんな合わないみたいなので少し安堵しつつも、やっぱり大丈夫なのかなという感じでやっぱり落ち着きませんでした。コンテスト中にあってるかどうか調べる手段は欲しいと思いました。出力がおかしくならないようにしながらコードをいじる作業が続くので、どこかでバグを入れてしまうと、どこからバグっているのか分からなくなって厳しいです。それと、スコアボードもやっぱり欲しいと思いました。周りがどれぐらい頑張っているのか分からないので、一人もくもくになってしまって、ちょっと辛かったです。あと、スコアボードがないと接戦になりにくい気がする。

そんなこんなですが、一位になれて嬉しかったです。またの機会があればぜひ参加させていただきたいと思います。チームラボの皆さまどうもありがとうございました。参加した皆さま、お疲れ様でした。

JOI 春合宿の講義資料

id:iwiwi さんからご紹介に与りまして、JOI春合宿にて講義をさせて頂きました。テーマはなんでも良いとのことでしたので、関数プログラミング入門ということで話させて頂きました。スライドを以下に公開しております。

聴いて頂いた皆さま、拙い講義ではありましたが、どうもありがとうございました。二時間も頂けるとのことだったので、あれもこれも話したいとなって、まとまりのない発表になってしまった感が否めませんが、少しでも関数プログラミングの魅力が伝われば幸いです。関数プログラミング入門ということで、関数プログラミングを全く知らない人をターゲットに作りましたが、少々無理があったかもしれません。私はネルー値が1を切らないとなかなか準備に取り掛かれなくて、当日は準備不足で資料のミスも目立ったし、資料の退屈さを紛らわすために適当に突っ込んだネタ画像も唐突過ぎていけない(その辺は大分修正しました。余計ひどくなっているかもしれませんが)。

とまあ、反省はこのぐらいにしまして、内容は関数プログラミングの基礎から並行プログラミングの話まで、なるべく関数プログラミングがおいしく見えるところをかいつまんで説明してあります。嘘も方便も多かろうと思いますが、識者の方は大目に見てやって下さい。こういうのは宗教論争だと言われたりもしますので(私は学術論争だと思っているのですが)、まさに布教でして、ならばこれは宗教の勧誘と変わらないわけでして、私の言うことを全面的には信用しないようにと念を押してはおきました。

で、内容の話ですね。いやあ、退屈な資料ですね。キャッチーな資料の作り方を誰か教えてください。まず、パワーポイントデフォルトのテーマ、これがいけない。白地にゴチック体、淡々と並べられるitemize。作り方が分からないので、アニメーションも一切なし、PDFに変換しても完全版が楽しめるという親切設計。うえうえ、3分で眠れる自信がありますよ!最近流行りといったらあれです、高橋メソッド。巨大な文字のインパクト。次々めくられるスライドによる圧倒的なスピード感。聴衆も話者の巧みなキーボード操作から目が離せない!?って、そうじゃないよ。古いよ。なんでなの、これ。高橋メソッドにしたらページ数1000超えるよ!誰かほんとにクールなスライドの作り方教えてください。

それで、内容の話ですね。うーん、内容はスライド観てください。

wafのユニットテストモジュールの改良

前回wafの紹介記事を書きましたが、あれからいくつかバージョンアップがあって、それに伴ってユニットテストモジュールの仕様が結構変わりました。変わったといいますか、かなり改悪されたように思います。

  • --alltestオプションが常にTrueになるようになった(オプションは存在するが、デフォルトでTrueで指定してもTrueで、Falseにする術がなくなった。バグとしか思えない)
  • サマリ表示でエラーの詳細がでなくなった

ちょっとこのまま使っていくには厳しい状況です。それに加えて、ユニットテストコンパイル・実行しないというオプションがかねてから欲しいと思っていたので(ユニットテストライブラリがない環境でもインストールはできて欲しいものです)、これを機に自作することにしました。拡張しやすいこともwafのメリットなので、作業はとてもスムーズに進みました。

http://github.com/tanakh/waf-unittest

というわけで、作ったものをgithubに公開しました。

waf組み込みのユニットテストモジュールとの違いは、

  • デフォルトではユニットテストコンパイル・実行しない
  • サマリの自動表示(add_post_funいらず)
  • エラー詳細の表示
  • gtestの組み込みサポート(オートチェック・オートリンク)
  • 特定のテストだけ実行する機能

などです。詳しくはgithubのREADMEをご覧ください。

waf チュートリアル

waf - The flexible build system http://code.google.com/p/waf/

wafというものを最近知り一目惚れしてしまったので、紹介記事を書きます。ユーザーが増えると嬉しいな。

wafとは何か?特徴・利点・使うべき理由

wafはPythonベースのビルドシステムです。同様のことを行うツールとして、Autotools、Scons、CMake、Antなどがあります。Sconsからの派生で、比較的新しいソフトウェアです。

  • 分かりやすい

Pythonで書かれており、スクリプトPythonで記述します。シェルスクリプトと謎のマクロが入り混じるAutotoolsや、独自言語のCMakeなどに比べて扱い易いです。Pythonを知っていれば非常にすんなりと使いこなすことが出来ます。Pythonを知らなくても、他の独自言語を覚えるよりは実りがあるかと思います。Pythonで記述しますので、自分で機能を拡張することも非常に簡単にできます。このあたりはAutotoolsに苦しめられた経験のある方なら最も有力な乗り換え理由になると思います。

  • 配布しやすい

Pythonで書かれているので、Pythonのインストールされているシステムでならどこでも動作します。幅広いバージョンのPythonで動作します。今やPythonはほとんどのLinuxにデフォルトでインストールされていますし、WindowsMacなどでもPythonが入っていれば動作させることができます。wafは80KB程度の単一のPythonスクリプトで、BSDライセンスなので、プロジェクトに含めて配布することが容易です。wafを同梱して配布することによりAutotoolsなどでは起こりがちなバージョン問題が起こりません(Autotoolsではconfigureで配布するとは思いますが)。configureスクリプトのラッパがあるので、これを用いると、Linux文化での標準的なソフトウェアのインストール方法である configure; make; make install にも簡単に対応することができます。

  • 高速に動作する

configureが非常に高速に行われます。ccacheのようなオブジェクトキャッシュ、並列コンパイルの標準サポートにより、コンパイルも高速です。

  • 多くの言語の組み込みサポート

C、C++、D、JavaOCaml、などのプログラミング言語コンパイル、依存解析、実行がサポートされています。新しい言語のサポートも比較的容易です。

  • 出力が分かりやすい

出力がカラーで、失敗すると赤く表示されるので、コンパイル結果がわかりやすいです。また、コンパイルすべきファイルがいくつ有って、現在何個目のファイルをコンパイルしているかが表示されるので、コンパイルの進捗状況がわかりやすいです。コンパイルの進捗をプログレスバーで表示する機能もあって、見ていて楽しいです。

wafの機能

などが標準でサポートされています。一通り揃っていると思います。ビルドフェーズを追加することも容易です。

インストール

wafをインストールするのは以下の理由から推奨されません。

  • adminが要る・めんどい
  • バージョン問題
  • wafを同梱しない理由がない
  • Windowsにはインストールできない

wafスクリプトをプロジェクトに含めてしまうのが一般的です。

http://code.google.com/p/waf/

wafのページから、最新版のwafをダウンロードして使います。

$ wget http://waf.googlecode.com/files/waf-1.5.11
$ mv waf-1.5.11 waf
$ chmod +x waf
$ ./waf
Waf: Please run waf from a directory containing a file named "wscript" or run distclean

wafを使うにはwscriptというファイルを書く必要があるので、今のところはエラーが出ます。wafは実行の際に自身をカレントディレクトリに展開するので、書き込み可能なディレクトリで実行しなければならないことに注意してください。

プロジェクト作成の度にwafをダウンロードしたくない、実行の際に./を付けるのが嫌など、些細な点が気になるならば、上記デメリットを理解した上でインストールすることも可能です。その際にはwafのページからたどれる、waf bookの http://freehackers.org/~tnagy/wafbook/ch01s03.html のあたりが参考になると思います。

wafは単一スクリプトだけでなく、tar.bz2版も配布されています。これには、いろいろなサンプルプロジェクトや、Autotoolsからの移行ツールや、bash-completion、wafのソースなどが含まれていますので、wafを使っていこうという場合には一度確認されることをおすすめします。

wscriptの基本的な書き方

wafはwscriptというファイルに、ビルドに必要な情報を書きこみます。これは普通のPythonプログラムとして記述します。以下に雛形を示します。

APPNAME = 'test-project'
VERSION = '1.0.0'

srcdir = '.'
blddir = 'build'

def set_options(opt):
    # プロジェクトのオプションを設定する
    # 最初に呼ばれる
    pass

def configure(conf):
    # ライブラリのチェックなど
    # waf configure 時に呼ばれる
    pass

def build(bld):
    # ビルドの情報を書く
    # waf build 時に呼ばれる
    pass

def shutdown(ctx):
    # 終了時に何かをさせたいとき
    # 最後に呼ばれる
    pass

まず、変数を四つ定義します。APPNAMEとVERSIONはプログラムの名前とバージョンを指定します。srcdirとblddirはソースの場所と、コンパイル時の一時ファイルを置くディレクトリを指定します。これらの変数は省略すると、それぞれ'noname'、'1.0'、'.'、'build'が使われます。

このままでは実行しても何も起こらないので、次のように書いてみます。

APPNAME = 'test-project'
VERSION = '1.0.0'

srcdir = '.'
blddir = 'build'

def set_options(opt):
    print "set_options"

def configure(conf):
    print "configure"

def build(bld):
    print "build"

def shutdown(ctx):
    print "shutdown"
$ ./waf configure
set_options
configure
'configure' finished successfully (0.002s)
shutdown

$ ./waf build
set_options
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
build
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.003s)
shutdown

configure、build実行時に、それぞれ対応する関数が呼ばれているのが分かります。ここにそれぞれ必要なことを書いていくことになります。

C/C++プログラムのコンパイル

C++プログラムをコンパイルする例を示します。

def set_options(opt):
    opt.tool_options('compiler_cxx')

def configure(conf):
    conf.check_tool('compiler_cxx')

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main')

まず、set_optionsで、C++コンパイラ用のオプションを使えるようにします。'compiler_cxx'はC++コンパイラ用の設定です。Cコンパイラを使うなら、'compiler_cc'を指定します。次に、configureでC++コンパイラのチェックをします。最後にbuildにビルドルールを書きます。featuresには、プログラムをどうやってコンパイルするかを書きます。ここでは、cxxとcprogramを指定しています。これは、空白区切で指定してもいいですし、['cxx', 'cprogram']のように文字列のリストを渡してもいいです。これは以降出てくる文字列を複数している所でもすべて共通の仕様です。cxxは、C++コンパイラコンパイルせよと言う指定、cprogramは実行ファイルを作れと言う指定です。他にcshlib、cstaticlibなどがあります。sourceにはソースファイルを指定します。targetには生成する実行ファイルの名前を指定します。

ビルドを実行すると次のようになります。

$ cat main.cpp
#include <iostream>
using namespace std;

int main()
{
  cout<<"Hello, waf waf world!"<<endl;
  return 0;
}

$ ./waf configure
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
'configure' finished successfully (0.049s)

$ ./waf build
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/2] cxx: main.cpp -> build/default/main_1.o
[2/2] cxx_link: build/default/main_1.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.348s)

$ build/default/main 
Hello, waf waf world!

configureで、C++コンパイラの存在がチェックされ、buildでmain.cppがコンパイルされ、build/default/mainに実行ファイルがリンクされます。ビルドの際に生成されるものはすべてbuild(blddirで指定したディレクトリ)以下に置かれます。

なお、waf buildのときのbuildは省略できるので、単にwafと実行すればbuildできます。

ファイル複数からなるプログラムはsourceに複数ファイルを指定すればできます。

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp foo.cpp',
        target = 'main',
        includes = '.')

includesにヘッダファイルのあるディレクトリを指定します。これを書けば、そこに含まれるヘッダの依存関係を自動で解析してくれます。

$ cat main.cpp
#include <iostream>
using namespace std;

#include "foo.h"

int main()
{
  cout<<foo(123)<<endl;
  return 0;
}

$ cat foo.cpp
#include "foo.h"

int foo(int n)
{
  return n*n;
}

$ cat foo.h
int foo(int n);

$ ./waf configure
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
'configure' finished successfully (0.048s)

$ ./waf
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/3] cxx: main.cpp -> build/default/main_1.o
[2/3] cxx: foo.cpp -> build/default/foo_1.o
[3/3] cxx_link: build/default/main_1.o build/default/foo_1.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.439s)

$ build/default/main
15129

$ ./waf
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.006s)

$ emacs foo.cpp
... edit ...

$ ./waf
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[2/3] cxx: foo.cpp -> build/default/foo_1.o
[3/3] cxx_link: build/default/main_1.o build/default/foo_1.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.164s)

$ emacs foo.h
... edit ...

$ ./waf
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/3] cxx: main.cpp -> build/default/main_1.o
[2/3] cxx: foo.cpp -> build/default/foo_1.o
[3/3] cxx_link: build/default/main_1.o build/default/foo_1.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.408s)

必要なファイルだけ再コンパイルされているのが分かります。なお、ファイルの再コンパイルmd5の比較により行われるので、内容が本当に変更されていないと再コンパイルは行われません。

ライブラリの作り方

ライブラリを作る場合は、featuresにcprogramの代わりにcshlibまたはcstaticlibと書くだけです。先程の例を、foo.cppをライブラリに、main.cppをそれを使うプログラムに変更してみます。

def build(bld):
    bld(features = 'cxx cstaticlib',
        source = 'foo.cpp',
        target = 'foo',
        includes = '.')

    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '.',
        uselib_local = 'foo')

featuresにcstaticlibを指定しました。foo.cppからfooという静的ライブラリを作れという指示です。mainは今度はそのfooというライブラリをリンクしなければなりません。その指定をuselib_localというところに書きます。同じプロジェクトで作られるライブラリ(ローカルなライブラリ)への参照はuselib_localに書きます。

$ ./waf distclean configure build
'distclean' finished successfully (0.002s)
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
'configure' finished successfully (0.048s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/4] cxx: foo.cpp -> build/default/foo_1.o
[2/4] cxx: main.cpp -> build/default/main_2.o
[3/4] static_link: build/default/foo_1.o -> build/default/libfoo.a
[4/4] cxx_link: build/default/main_2.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.426s)

featuresにcstaticlibを指定したので、foo.cppがコンパイルされ、staticライブラリlibfoo.aが生成されました(targetで指定した名前にlibが付いたものが生成されますのでlibをtargetにlibをつけてはいけません。liblibfoo.aになってしまいます)。それからmain.cppとlibfoo.aがリンクされ、mainが生成されます。ここで、mainを生成する前にlibfoo.aが生成されていなければなりませんが、このビルド順は、ビルドターゲット間の依存関係から自動的に解決されます。書いてある場所の前後は関係ありません。サブディレクトリ(後述)を含む場合も全体を考慮して解決されます。wafはwaf build -j2などとすると並列コンパイルができますが、それも依存関係に基づきます。依存関係が循環している場合、wafはそれを検知できません。エラーメッセージではなく、再帰がスタックオーバーフローしてwafが落ちます。依存関係はきちんとツリー(もしくは森)になるようにしましょう。

ちなみに、wafはコマンドを並べて書くと、上のようにそれらを順に実行します。

featuresにcshlibを指定すると、動的ライブラリが生成されます。その際も同様にuselib_localでリンクできます。

def build(bld):
    bld(features = 'cxx cshlib',
        source = 'foo.cpp',
        target = 'foo',
        includes = '.')

    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '.',
        uselib_local = 'foo')
$ ./waf distclean configure build
'distclean' finished successfully (0.001s)
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
'configure' finished successfully (0.065s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/4] cxx: foo.cpp -> build/default/foo_1.o
[2/4] cxx: main.cpp -> build/default/main_2.o
[3/4] cxx_link: build/default/foo_1.o -> build/default/libfoo.so
[4/4] cxx_link: build/default/main_2.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.507s)

サブディレクト

先程の例を、libfooをfooというディレクトリに移動させようと思います。サブモジュールを分割するのはプロジェクトをシンプルに保つために重要です。libfooを作る方法は独立していた方が良いので、wscriptも分割します。ディレクトリ構成としては次のようになります。

|- foo
|  |- foo.cpp
|  |- foo.h
|  `- wscript
|- main.cpp
`- wscript

ルートのwscriptから子のwscriptを呼び出すには次のようにします。

# wscript
ef set_options(opt):
    opt.tool_options('compiler_cxx')

def configure(conf):
    conf.check_tool('compiler_cxx')

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '. foo',
        uselib_local = 'foo')

    bld.recurse('foo')
# foo/wscript
def build(bld):
    bld(features = 'cxx cshlib',
        source = 'foo.cpp',
        target = 'foo',
        includes = '.')

bld.recurse('foo') と書いてある部分がfoo/wscriptを呼び出す部分です。こうすると、foo/wscriptにある同じ関数が呼ばれます。この場合だとbuildなのでbuildが呼ばれます。もちろんconfigureからrecurseすることも可能です。recurseにはディレクトリのリストを渡せます。サブディレクトリのwscriptには、呼び出されない関数は書かなくても構いません。configureをrecurseできるので、各サブモジュールに必要なライブラリチェックを分散させることができます。Autotoolsのようにconfigure.acが肥大化したり、チェックの場所と使用の場所が離れたりすることが防げます。実行すると次のようになります。

$ ./waf distclean configure build
'distclean' finished successfully (0.000s)
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
'configure' finished successfully (0.054s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/4] cxx: main.cpp -> build/default/main_1.o
[2/4] cxx: foo/foo.cpp -> build/default/foo/foo_1.o
[3/4] cxx_link: build/default/foo/foo_1.o -> build/default/foo/libfoo.so
[4/4] cxx_link: build/default/main_1.o -> build/default/main
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
'build' finished successfully (0.535s)

ライブラリ、ヘッダファイルのチェック

C/C++のライブラリ、ヘッダファイルのチェックはcheck_ccまたは、check_cxxによって行うことができます。これらはconfigure時に行うので、configure()に記述します。一通りの例を以下に示します。

def configure(conf):
    conf.check_tool('compiler_cxx')

    # libmの存在確認
    conf.check_cxx(lib = 'm')
    # ディレクトリを指定して確認
    conf.check_cxx(lib = 'superlib', libpath = '/var/super/lib')

    # time.hの存在確認
    conf.check_cxx(header_name = 'time.h')
    # stdio.hと関数printfの存在確認。必須(mandatory)
    conf.check_cxx(function_name = 'printf',
                   header_name   = 'stdio.h',
                   mandatory     = True)

    # check_cxxはboolを返す
    if conf.check_cxx(lib = 'nuboo'):
        print "nuboo exists!"
    else:
        print "nuboo does not exist!"

    # コード片がコンパイルできるか調べる。コンパイルできるかどうかをboobahに格納
    conf.check_cxx(fragment = 'int main(){ return 0; }',
                   define_name = 'boobah')

    # コード片を実行して、出力を取り出す
    conf.check_cxx(fragment = """
#include <iostream>
using namespace std;
int main(){ cout<<sizeof(long)<<endl; return 0; } """,
                   define_name = 'LONG_SIZE',
                   execute = True,
                   define_ret = True,
                   msg = 'Checking for long size')

    # uselib_store(後述)
    conf.check_cxx(lib = 'm',
                   cxxflags = '-Wall',
                   defines = ['var=foo', 'x=y'],
                   uselib_store = 'M')

    # チェックした結果をヘッダファイルとして書き出す
    conf.write_config_header('config.h')

    # envの中身を出力(デバッグに便利)
    conf.env.store('conf.log')

check_cxxはC++コンパイラを用いてコンパイルを試みます。同様にcheck_ccはCコンパイラを用いてコンパイルを試みます。それぞれ、使用するためには、set_optionsでopt.tool_options('compiler_cxx')、opt.tool_options('compiler_cc')されている必要があります。

libにライブラリ名を指定すると、そのライブラリがリンクできるかどうかを調べます。その際にlibpathでライブラリを探す場所を指定できます。

header_nameにヘッダファイル名を指定すると、そのファイルをインクルードできるか調べます。function_nameに関数名を指定すると、関数の存在を調べられます。このときライブラリ、ヘッダファイルがそれぞれ存在するとconf.env.HAVE_TIME_H、conf.env.HAVE_PRINTFなどが1に設定されます。

madantoryを指定すると、そのチェックを必須にできます。これを指定したチェックが失敗するとconfigureがこけます。

check_cxxはboolを返すので、Pythonのif文などで簡単に利用できます。とても便利です。

コード片のコードテストや、コード片の出力をconf.envに設定できます。上の例ですと、LONG_SIZEに"8"が設定されます。

wafにはuselibという仕組みがあります。詳しくは後述のライブラリの参照で述べますが、ここでは、ここに指定した文字列を接尾辞に、いろいろな変数が定義されます。ここでは、LIB_M、CXXDEFINES_M、CXXFLAGS_M、が定義されます。

write_config_header()を呼び出すと、集めた情報をC/C++のヘッダファイルに書きだします。例えば、上のコードなら、次のコードが生成されます。

/* Configuration header created by Waf - do not edit */
#ifndef _CONFIG_H_WAF
#define _CONFIG_H_WAF

#define HAVE_TIME_H 1
#define HAVE_PRINTF 1
#define boobah 1
#define LONG_SIZE "8"
#endif /* _CONFIG_H_WAF */

conf.env.store()を呼び出すと、環境を書きだすことができます。これはwafコードのデバッグにとても便利です。

configureの実行結果を以下に載せておきます。

$ ./waf configure
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
Checking for library m                   : ok 
Checking for library superlib            : not found 
Checking for header time.h               : ok 
Checking for function printf             : ok 
Checking for library nuboo               : not found 
nuboo does not exist!
Checking for custom code                 : ok 
Checking for long size                   : ok 
Checking for library m                   : ok 
'configure' finished successfully (1.480s)

pkg-config

pkg-config、あるいは、hoge-configのような、Cのコンパイラフラグ、リンクフラグ、ライブラリパスなどを取得するためのプログラムを提供しているライブラリがあります。このようなライブラリがあるばあい、とても便利にチェックを行うことができます。

def configure(conf):
    conf.check_cfg(atleast_pkgconfig_version = '0.0.0')
    conf.check_cfg(package = 'pango', atleast_version = '0.0.0')
    conf.check_cfg(package = 'pango', exact_version = '0.21')
    conf.check_cfg(package = 'pango', max_version = '9.0.0')
    conf.check_cfg(package = 'pango', args='--cflags --libs')
    pango_version = conf.check_cfg(modversion = 'pango')

    conf.check_cfg(path        = 'sdl-config',
                   args        = '--cflags --libs',
                   package     = '',
                   uselib_store='SDL')

pkg-configの場合、check_cfgで、packageにパッケージ名を渡せば、バージョンのチェックなどができます。独自のconfigプログラムの場合は、pathに指定してやります(この場合はバージョンチェックなどはできない模様)。ここで、uselib_storeを指定して、argsにコンパイラフラグを取得するための引数を書いてやると、check_cfgはその返り値を解析して、-IxxxならCPPPATH_hogeに、-DxxxならCXXDEFINES_hogeに、-LxxxならLIBPATH_hogeに、-lxxxならLIB_hogeに、その他はCXXFLAGS_hogeなどに、自動的に振り分けて追加されます。

ライブラリの参照

bldの引数で、ライブラリの参照を追加できます。例えば、pthreadをリンクするなら、次のようになります。

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '.',
        lib = ['pthread'])

ライブラリパスを指定したいなら、libpathを書きます。

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '.',
        lib = ['pthread'],
	libpath = ['/usr/local/lib'])

その他、いろいろオプションを指定できます。

def build(bld):
    bld(features     = 'cxx cprogram',
        source       = 'main.cpp',
        target       = 'main',
        includes     = '.',
        defines      = ['LINUX=1', 'BIDULE'],
        cxxflags     = ['-O2', '-Wall'],
        lib          = ['m'],
        libpath      = ['/usr/lib'],
        linkflags    = ['-g'])

uselib

uselibを用いると、上記のいろいろなコンパイルの設定を一気に設定できます。

def build(bld):
    bld(features = 'cxx cprogram',
        source = 'main.cpp',
        target = 'main',
        includes = '.',
        uselib = 'SDL')

bldの引数にuselibを指定してやると、その文字列を接尾辞とする設定がまとめてなされます。例えば、LIB_SDLがlibに、LIBPATH_SDLがlibpathに、CXXFLAGS_SDLがcxxflagsに設定されます。check_cfgもしくはcheck_cxxでのuselib_storeとuselibを組み合わせて使うと、コンパイル・リンクフラグの設定を大変簡単に行うことができます。

オプション

configure時のオプションを自由に追加することができます。プロジェクトの特定のモジュールの有効・無効を切り替えたりなどが典型的な利用例です。set_options()でadd_optionすることによりオプションの追加ができます。

def set_options(opt):
    opt.tool_options('compiler_cxx')

    # boolオプション
    opt.add_option('--enable-super-module',
                   action = 'store_true',
                   default = False,
                   help='enable a super module')

    # 文字列オプション
    opt.add_option('--build_kind',
                   action = 'store',
                   default = 'debug,release',
                   help = 'build the selected variants')

def build(bld):
    import Options
    # オプションの参照
    if Options.options.enable_super_module:
        build.recurse('super')

追加したオプションは waf --help にも表示されます。

$ ./waf --help
waf [command] [options]

Main commands (example: ./waf build -j4)
  build    : builds the project
  clean    : removes the build files
  configure: configures the project
  dist     : makes a tarball for redistributing the sources
  distcheck: checks if the sources compile (tarball from 'dist')
  distclean: removes the build directory
  install  : installs the build files
  uninstall: removes the installed files

Options:
  --version             show program's version number and exit
  -h, --help            show this help message and exit
  -j JOBS, --jobs=JOBS  amount of parallel jobs (1)
  -k, --keep            keep running happily on independent task groups
  -v, --verbose         verbosity level -v -vv or -vvv [default: 0]
  --nocache             ignore the WAFCACHE (if set)
  --zones=ZONES         debugging zones (task_gen, deps, tasks, etc)
  -p, --progress        -p: progress bar; -pp: ide output
  --targets=COMPILE_TARGETS
                        build given task generators, e.g. "target1,target2"
  --enable-super-module
                        enable a super module
  --build-kind=BUILD_KIND
                        build the selected variants

...

ユニットテスト

wafはユニットテスト支援機能があります。先のプロジェクトで、libfooのユニットテストを作成することにします。

def set_options(opt):
    opt.tool_options('compiler_cxx')
    opt.tool_options('UnitTest')

def configure(conf):
    conf.check_tool('compiler_cxx')
    conf.check_cxx(lib = 'gtest_main', uselib_store = 'gtest')

def build(bld):
    bld(features = 'cxx cprogram test',
        source = 'foo_test.cpp',
        target = 'foo_test',
        includes = '. foo',
        uselib_local = 'foo',
        uselib = 'gtest')

    bld.recurse('foo')

    import UnitTest
    bld.add_post_fun(UnitTest.summary)

まず、set_optionsでtool_optionsにUnitTestを追加します。次に、テストプログラムを作ります。これはfeaturesにtestを追加するだけです。testフィーチャーがついているプログラムは、コンパイル後に自動で実行され、その結果が集計されるようになります。それから、bld.add_post_funでUnitTest.summaryが最後に実行されるようにします。これでテストの結果が表示されるようになります。

#include <gtest/gtest.h>

#include "foo.h"

TEST(footest, test)
{
  EXPECT_EQ(foo(123), 123+123);
}

テストプログラムを書きます。今回はgtestを使いました。fooは二乗を返す関数だったので、これはfailするはずです。実行してみます。

$ ./waf distclean configure build
'distclean' finished successfully (0.002s)
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
Checking for library gtest_main          : ok 
'configure' finished successfully (0.224s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/5] cxx: foo_test.cpp -> build/default/foo_test_1.o
[2/5] cxx: foo/foo.cpp -> build/default/foo/foo_1.o
[3/5] static_link: build/default/foo/foo_1.o -> build/default/foo/libfoo.a
[4/5] cxx_link: build/default/foo_test_1.o -> build/default/foo_test
[5/5] utest: build/default/foo_test
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
execution summary 
FAIL /home/hideyuki/project/waf_test/build/default/foo_test 
command execution failed: /home/hideyuki/project/waf_test/build/default/foo_test -> 'Running main() from gtest_main.cc
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from footest
[ RUN      ] footest.test
../foo_test.cpp:7: Failure
Value of: 123+123
  Actual: 246
Expected: foo(123)
Which is: 15129
[  FAILED  ] footest.test
[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran.
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] footest.test

 1 FAILED TEST

コンパイルされた後、テストが実行されているのが分かります。失敗したテストがFAILと表示されています(これは実際には赤で表示されるので、失敗したことが分かりやすい)。wafはテストをコンパイルの後に実行します。コンパイルが起こらないとテストは実行されません。テストが失敗した場合も、再度waf buildを行ってもテストは実行されません。waf build --alltests オプションを使うと、ビルドされなかったテストを含む、全てのテストを実行することができます。

さて、先程のバグが分かったので、修正して再実行します。

include <gtest/gtest.h>

#include "foo.h"

TEST(footest, test)
{
  EXPECT_EQ(foo(123), 123*123);
}
$ ./waf
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/5] cxx: foo_test.cpp -> build/default/foo_test_1.o
[4/5] cxx_link: build/default/foo_test_1.o -> build/default/foo_test
[5/5] utest: build/default/foo_test
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
execution summary 
ok /home/hideyuki/project/waf_test/build/default/foo_test 
'build' finished successfully (0.779s)

今度はokになりました(okは緑で表示されます)。なお、通ったテストの出力は表示されません。

インストーラ

waf install とすると、ビルドしたものをインストールできます。

$ sudo ./waf distclean configure build install
'distclean' finished successfully (0.002s)
Checking for program g++,c++             : ok /usr/bin/g++ 
Checking for program cpp                 : ok /usr/bin/cpp 
Checking for program ar                  : ok /usr/bin/ar 
Checking for program ranlib              : ok /usr/bin/ranlib 
Checking for g++                         : ok  
Checking for library gtest_main          : ok 
'configure' finished successfully (0.209s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
[1/5] cxx: foo_test.cpp -> build/default/foo_test_1.o
[2/5] cxx: foo/foo.cpp -> build/default/foo/foo_1.o
[3/5] cxx_link: build/default/foo/foo_1.o -> build/default/foo/libfoo.so
[4/5] cxx_link: build/default/foo_test_1.o -> build/default/foo_test
[5/5] utest: build/default/foo_test
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'
execution summary 
ok /home/hideyuki/project/waf_test/build/default/foo_test 
'build' finished successfully (0.965s)
Waf: Entering directory `/home/hideyuki/project/waf_test/build'
* installing build/default/foo/libfoo.so as /usr/local/lib/libfoo.so
Waf: Leaving directory `/home/hideyuki/project/waf_test/build'

テストでない実行ファイル、動的ライブラリは自動的にインストール対象になります。

特定のファイル(例えばヘッダファイル)をインストールさせたい場合、bld.install_files()を使います。

def build(bld):
    ...

    # 特定のファイルをインストールする
    bld.install_files('${PREFIX}/include', ['foo/foo.h'])
    # ディレクトリ構造を保持する
    bld.install_files('${PREFIX}/include', ['foo/foo.h'], relative_trick = True)
    # 別名でインストールする
    bld.install_as('${PREFIX}/dir/bar.png', 'foo.png')
    # シンボリックリンクを作成する
    bld.symlink_as('${PREFIX}/lib/libfoo.so.1', 'libfoo.so.1.2.3')

install_filesの第一引数には、インストールするディレクトリを指定します。文字列中の${PREFIX}は、bld.env.PREFIXで置換されます。PREFIXでなくてもbld.envにある変数なら何でも展開できます。bld.env.PREFIXには、configure時に--prefix=で指定したディレクトリが入っています。指定しなかった場合は/usr/localになっています。

relative_trickを指定すると、ディレクトリ構造を保持してインストールされます。上の例なら、${PREFIX}/include/foo/foo.h にインストールされます(一つ目の例は${PREFIX}/foo.h になります)。

その他、別名でのインストールや、シンボリックリンク作成もできます。

パッケージ作成

さて、libfooもおおよそ完成したので、パッケージを作って配布しましょう。wafでは、Autotoolsと同様、waf distとすると、tarballが作成されます。

$ ./waf dist
New archive created: test-project-1.0.0.tar.bz2 (sha='0af6ce61eb3661bfc54efa5d2b301442a7e84557')
'dist' finished successfully (0.033s)

$ ls
build  foo_test.cpp   main.cpp   test-project-1.0.0.tar.bz2  wscript
foo    foo_test.cpp~  main.cpp~  waf                         wscript~

$ tar -jtf test-project-1.0.0.tar.bz2 
test-project-1.0.0/
test-project-1.0.0/waf
test-project-1.0.0/main.cpp
test-project-1.0.0/foo/
test-project-1.0.0/foo/foo.cpp
test-project-1.0.0/foo/wscript
test-project-1.0.0/foo/foo.h
test-project-1.0.0/wscript
test-project-1.0.0/foo_test.cpp

test-project-1.0.0.tar.bz2というファイルが出来ています。デフォルトでは、bz2圧縮されます。圧縮方式を変更するには次のようにします。

import Scripting
Scripting.g_gz = 'gz'

ところで、tarballに含めるファイルを指定した覚えはありませんでした。どうやってwafはtarballに含めるべきファイルを判断しているのでしょうか?

wafは基本的に、ディレクトリの内容をすべてtarballに含めます。そこから、特定の接尾辞を持つファイル・ディレクトリと、特定の名前のファイル・ディレクトリを除外します。ソースコードによると、、デフォルトの除外接尾辞は'~ .rej .orig .pyc .pyo .bak .tar.bz2 tar.gz .zip .swp'、デフォルトの除外ファイル・ディレクトリは'.bzr .bzrignore .git .gitignore .svn CVS .cvsignore .arch-ids {arch} SCCS BitKeeper .hg _MTN _darcs Makefile Makefile.in config.log'のようです。さらに、blddirは除外されます。

dist_hook()という関数を作れば、distで含めるファイルをカスタマイズすることができます。dist_hook()は、tarballに含めるファイルをテンポラリディレクトリにまとめて、圧縮する直前に、そこのディレクトリがカレントディレクトリになった状態で呼ばれます。

たとえば、main.cppを含めたくなければこうします。

def dist_hook():
    import os
    os.remove('main.cpp')
$ ./waf dist
New archive created: test-project-1.0.0.tar.gz (sha='4dbbd6948532b5b52d9ff52615739e4c68ad5f17')
'dist' finished successfully (0.017s)

$ tar -ztf test-project-1.0.0.tar.gz
test-project-1.0.0/
test-project-1.0.0/waf
test-project-1.0.0/foo/
test-project-1.0.0/foo/foo.cpp
test-project-1.0.0/foo/wscript
test-project-1.0.0/foo/foo.h
test-project-1.0.0/wscript
test-project-1.0.0/foo_test.cpp

また、除外ルールに追加することもできます。

import Scripting
Scripting.dist_exts += ['.cpp']

.cppファイルが含まれなくなります。

$ ./waf dist
New archive created: test-project-1.0.0.tar.gz (sha='a777a3cc369955f489a7d76c947eb067812f1917')
'dist' finished successfully (0.014s)

$ tar -ztf test-project-1.0.0.tar.gz
test-project-1.0.0/
test-project-1.0.0/waf
test-project-1.0.0/foo/
test-project-1.0.0/foo/wscript
test-project-1.0.0/foo/foo.h
test-project-1.0.0/wscript

tarballに含めたくないファイルをディレクトリ内に置きたい場合、特定の拡張子にして、その拡張子を除外ルールに追加するか、特定のディレクトリを除外にしてそこにまとめて置くか、あるいはdist_hook()を書いて独自の除去ルーチンを書けばなんでもできます。

結び

さて、wafいかがだったでしょうか。普通のPythonプログラムとしてビルドスクリプトを記述するのでとても見通しが良いのではないかと思います。どこに何が書けるのか、何を書いたらいいのかほとんど迷うことがありません。wafはコンパクトでありながら、ツボを抑えた機能をサポートしているので、普段使いではあれがないと困ることはほとんどないと思います。しかし、wafはflexibleと謳っているだけあって、機能を独自に拡張することが非常に容易にできるように設計されているので、最悪書けばなんとかなります。

今回はチュートリアルということで、wafのすべてを紹介できているわけではありません。もっとwafを知りたい、wafを是非使ってみたいという方は、下記のリンクを参照されると良いでしょう。

[その他] 200x年総括

なんか思い出に残ってること

  • 2002
    • erg制作
  • 2003
    • 暇すぎて鬱になる
  • 2007
    • ニコ動鑑賞
  • 2008
    • CodeJam WF
  • 2009
    • マリオWiiおもろかったね

2009年総括

  • SAをゴリゴリ
    • 完成してよかった
  • Haskellをプロダクトコードに
    • 微妙に達成
  • github登録
    • gitむずすぎ
  • C++を捨てる旅
    • 道半ばで倒れる
  • Haskellたくさん書く
    • 結構頑張って書いた
  • ICFP
    • だめぽ
    • C++イヤーになっちゃったのは私がふがいないせいなので
    • 来年は頑張る
  • CodeJam
    • だめぽ
    • むりぽ
  • TopCoder
    • 2010 -> 2171
    • 赤ならず
    • 三歩進んで二歩下がる

cabalで色付けされたソースにリンクしたドキュメントを生成する方法

$ cabal configure
$ cabal hscolour
$ cabal haddock "--haddock-options=--source-base=src/ --source-module=src/%{MODULE/./-}.html --source-entity=src/%{MODULE/./-}.html#%N"