Hatena::ブログ(Diary)

Windchase

2008.3.26

LimeChat 2.23 リリース

http://limechat.net/

サーバに接続できないときに、別のサーバに接続を試みる機能を追加しました。

その他、細かい修正です。

  • サーバに接続できないときに代替サーバに接続できるようにした。
  • ログファイルの文字コードを設定できるようにした。
  • キーワード反応とログ検索のとき、全角アルファベットにも大文字小文字を同一視オプションを適用するようにした。
  • CP1252に対応した。
  • Unicode のサロゲートペアに対応した。
  • ログ上で選択するときに、マウスカーソルが文字の左半分にあれば前の文字との間、文字の右半分にあれば次の文字との間を選択の区切りとして扱うようにした。
  • マクロに $encodeurl(str [, encoding]) 関数を追加した。
  • 最前面に表示に Shift+F4、メインメニューを表示に Shift+F5 のキーを割り当てた。

2008.3.24

Ragel

http://www.cs.queensu.ca/~thurston/ragel/

Ragel は、ステートマシンコンパイラの一種で、パーサジェネレータとして使われることが多い。その実例として、MongrelHpricot がある。

パーサジェネレータとして Ragel を使う利点は、以下の通り。

  • プロトコルやデータフォーマットを正確にパーズできる
  • その結果、セキュアなソフトウェアが作れる
  • 外部ライブラリに依存しないコードができる
  • ものすごく速い

特に HTTP server など、速度が求められるサーバを書くときに便利なことがわかる。

参考: http://www.zedshaw.com/tips/ragel_state_charts.html

ここでは、簡単な例としてドメイン名のパーザを作ってみよう。ホスト言語は C で。

まずは、Ragel 6.0 をインストールする。

OSX の場合、MacPorts でインストールできるものは少し古いので、Ragel のページ の下のほうから ragel-6.0.tar.gz を入手し、インストールする。

$ ./configure
$ make
$ sudo make install

ステートマシンの定義は、こんな感じに書ける。

alnumhyphen = alnum | "-";
label = alnum (alnumhyphen* alnum)?;
domain = label ("." label)*;
main := domain;

BNF っぽくてわかりやすい。

これをコンパイルすると、

f:id:Psychs:20080325030420p:image

こんなステートマシンができあがるわけだ。(Graphviz で画像化できる)

この定義を yacc のように C のソースに埋め込んで、domain.rl というファイル名で保存する。

#include <stdio.h>
#include <string.h>

%%{
  machine domain_parser;
  
  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;
  
  write data;
}%%

#define BUFSIZE 1024

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;
  const char* begin = NULL;
  char buf[BUFSIZE];
  
  printf("*** %s\n", data);
  
  %% write init;
  %% write exec;
}

int main(int argc, char** argv)
{
  parse("www.example.org");
  parse("www-host.example.org");
  parse("-www.example.org");
  parse("ww-.example.org");
  return 0;
}

とりあえず、実行してみよう。

$ ragel -C domain.rl
$ gcc -o domain domain.c
$ ./domain
*** www.example.org
www
example
org
*** www-host.example.org
www-host
example
org
*** -www.example.org
! parse error
*** ww-.example.org
! parse error

それぞれのドメイン名をパーズして、要素に分解できていることがわかる。(ラベルの最初か最後にハイフンがあるものはエラー)

それでは、具体的に Ragel の定義を見ていこう。

%%{
  machine domain_parser;
  
  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;
  
  write data;
}%%

Ragel の定義は、%%{ から }%% までの間に書いていく。

  machine domain_parser;

まず、ステートマシン名を宣言する。(必須)

  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

ここでは、アクションを定義している。

Ragel には、任意の状態遷移の前後にアクション (任意のコード) を実行できるという特徴がある。アクションの中では、fpc で現在のポインタ位置を参照できるので、それを利用して必要なところをキャプチャしていくわけだ。

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;

ステートマシンの定義は、Ragel 言語という正規言語 (regular language) で書く。alnum は組み込みのステートマシンで、[0-9a-zA-Z] に相当する。

label の定義には、アクションが使われている。

  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;

こう書くと、label にマッチする直前に begin_label が、直後に end_label が呼び出される。

ここで、もう一度アクションの定義を確認してみると、

  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }

begin_label が呼ばれたときに begin にその時点の fpc を保存しておき、end_label では begin から fpc までの文字列を切り出して表示していることがわかる。これで、正規表現のキャプチャと同じことができる。

さらに、main の定義を見てみる。

  main := domain @!error;

こう定義しておくと、状態遷移にエラーが起きたときに error アクションを呼び出してくれる。

最後に、

  write data;

で、ここにステートマシンの定義コードを出力する。

ホストプログラムの本体を見ていこう。

#define BUFSIZE 1024

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;
  const char* begin = NULL;
  char buf[BUFSIZE];
  
  printf("*** %s\n", data);
  
  %% write init;
  %% write exec;
}

int main(int argc, char** argv)
{
  parse("www.example.org");
  parse("www-host.example.org");
  parse("-www.example.org");
  parse("ww-.example.org");
  return 0;
}

パーザ部分は、parse 関数であることがわかる。

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;

Ragel では、用途ごとに変数名が決められているので、ステートマシンを実行するスコープに、以下の変数をあらかじめ定義しておく必要がある。

data入力データ
pデータの最初。通常は data をセットしておく。
peデータの最後。通常は data + strlen(data) をセットしておく。
eof入力の最後を示す。通常は pe と同じでよい。
cs現在の状態

そして、

  %% write init;
  %% write exec;

で、ステートマシンの初期化コードと実行コードを出力する。

$ ragel -C domain.rl

コンパイルしてできる domain.c の中を見てみると、

write data;
write init;
write exec;

の部分が、ステートマシンのコードに置き換えられている様子がわかる。

IRC プロトコルパーザを含むサンプルを置いておきます。

http://limechat.net/sample/ragel_samples.zip

2008.3.23

1000speakers #3

Ragel について発表してきた。詳しくはあとで書きます。

http://limechat.net/presentation/1000speakers3_ragel.pdf

1000speakers は、ほんとに楽しかった。

プログラミングが好きな、いろんな指向を持った人が集まって話をする。これって、実はすごいことなんじゃないだろうか。いままで自分が注意を向けていなかった分野の話を聞けて、ものすごい刺激をもらった。id:amachang さん、id:nishiohirokazu さんに感謝。

あと、せっかく id:cho45 さんに会えたのに、「Chemr 使ってます」ってお礼を言いそびれてしまった。。

追記 (2008.3.25)

Ragel について詳しく書いた。

http://d.hatena.ne.jp/Psychs/20080324/1206380939

2008.3.7

続・WebKit の改行問題

WebKit の件 の続報。

Unicode 5.1.0 で、レポートした問題が直るように改行アルゴリズムが変更されている。

http://www.unicode.org/Public/5.1.0/ucd/auxiliary/LineBreakTest.html

サンプルを見てみると、

..|ま|す。|XML|の..  

「す。」と「XML」の間で改行できるようになったことがわかる。

2008.3.3

LimeChat for OSX 0.17 リリース

http://limechat.sourceforge.net/index_ja.html

  • (Tigerのみ) 初回起動時に表示されるセットアップダイアログで、「+」ボタンを押すとクラッシュしていたバグをfixした。
  • ログのスクロールバーに、キーワード反応があった場所を表示するようにした。
  • 起動時にスペルチェックをオンにするようにした。
  • サーバとチャンネルの順序をドラッグアンドドロップで入れ替えられるようにした。
  • チャンネルリストダイアログで、キーワードでフィルタリングできるようにした。
  • DCC で送られてきたファイルを自動で受信するオプションを追加した。
  • ログの HTML テンプレートで CSS のアトリビュートセレクタを使うようにした。
  • テーマのディレクトリを ~/Library/Application Support/LimeChat/Themes に変更した。
  • ニックネームのデフォルトの書式を「%n: 」に変更した。
  • メンバリストのフォントを小さくした。
  • システムメッセージの頭の「*」を削除した。
  • コンソールログにサーバ名を表示しないようにした。