PB memo

■[ruby][changes]ruby-trunk-changes r34517 - r34527

今日は拡張ライブラリあたりのリファクタリングがあったくらいでした。

nobu:r34517 2012-02-10 00:15:57 +0900

ext/fiddle/fiddle.c の関数宣言の体裁を変更しただけです。

svn:r34519 2012-02-10 00:16:04 +0900

version.h の日付更新。

nobu:r34520 2012-02-10 00:47:11 +0900

メモリリークのチェックをするテストのメモリ使用量をチェックするあたりを test/ruby/envutil.rb に assert_no_memory_leak というメソッドとして切り出してそれを利用するようにリファクタリングしています。

nobu:r34521 2012-02-10 01:29:08 +0900

拡張ライブラリ dl のポインタをアライメントするためのオフセットを計算する DLALIGN() というマクロが1つずつインクリメントして while 文でアライメントが取れたら止めるということをしていたので余剰を計算して一度に加算するようにしています。

nobu:r34522 2012-02-10 01:30:43 +0900

拡張ライブラリ dl で型ごとのアラインメント(メモリ上のアドレスの Nの整数倍のところに置かれるか、の N)を構造体をそれぞれ定義しておいてから計算しているのを offsetof() マクロを使うマクロを定義して余分な型を定義せずに計算するようにリファクタリングしています。

nobu:r34523 2012-02-10 01:41:08 +0900

コンパイラが clang の時は -fno-defer-pop というオプションをコンパイル時につけずリンク時のみに付けるようにしています。 -fno-defer-pop は関数呼び出しから戻った時にすぐ引数をスタックから pop するようにするというものです。 clang はコンパイル時に指定されると警告メッセージをだしてしまうそうですが、pop の遅延をしていないんでしょうかね。

tenderlove:r34527 2012-02-10 03:44:27 +0900

拡張ライブラリ psych の Psych::Parser#external_encoding= というメソッドの C の実装は削除して、 Ruby で書かれたライブラリで attr_writer として定義するようにしています。元の実装は一度 external_encoding= で設定すると2度目以降は例外を発生させていたのですが、parser を使いまわせるように再設定できるようにしています。

Permalink | コメント(0) | トラックバック(0)

■[ruby][changes]ruby-trunk-changes r34494 - r34516

今日は少しコミット多いです。昨日のテスト用のメモリリークチェックの修正に関連して DL や Fiddle の不具合修正などがありました。

akr:r34494 2012-02-09 00:44:41 +0900

Enumerable#flat_map の rdoc のサンプルコードを挙動がよくわかるように少し変更しています。

svn:r34495 2012-02-09 00:44:44 +0900

version.h の日付更新。

tenderlove:r34496 2012-02-09 03:03:51 +0900

lib/rexml/parsers/baseparser.rb のブロックパラメータで外側のローカル変数と同じ名前を使っていて -w つきだと警告が出ていたのを修正しています。

naruse:r34497 2012-02-09 03:29:52 +0900

r34493 で追加したメモリリークの検査用のスクリプトで ps(1) コマンドを使う部分で FreeBSD の ps の -o オプションの指定方法は引数毎に -o オプションを分けないといけないそうなので書き換えています。

naruse:r34499 2012-02-09 04:13:14 +0900

Pathname.binread のテストメソッドで binread ではなく read を呼んでいたのを修正。まあ "abc" を比較するだけなら read でも binread でも同じなので encoding のチェックもしたほうがいいのかもしれませんね。 [ruby-core:42440] [Bug #5984]

usa:r34504 2012-02-09 11:32:58 +0900

DL に Win64 用の DL::DWORD32, DL::DWORD64 という型の追加と DL::HANDLE のバイト幅をポインタとあわせるように調節しています。

nobu:r34505 2012-02-09 12:25:07 +0900

行末の余分な空白の削除。

usa:r34506 2012-02-09 16:03:07 +0900

拡張ライブラリ fiddle で Ruby の数値を LONG_LONG 型へ変換するのに rb_big2ull() を使っていて Bignum と決め打ってましたが Fixnum がくるかもしれないので NUM2ULL() を使うように修正しています。 Fixnum を渡すと SEGV か SIGBUS になってしまう可能性がありました。

usa:r34507 2012-02-09 16:10:26 +0900

DL::ValueUtil で LONG_LONG 型の値を取り出すのに pack/unpack の "q!", "Q!" という指示子を使っていましたがこの記法はまだサポートされていないので ! なしを使うようにしています。あー q/Q にはサイズ指示子 ! はまだ追加されていなかったんでしたね。一度はコミットしたもののすぐ revert されていたようです。 http://d.hatena.ne.jp/nagachika/20101018/ruby_trunk_changes_29520_29530

usa:r34508 2012-02-09 16:11:23 +0900

r34493 で追加したメモリリークチェック用のテスト用メソッドを Win64 でも動くようにポインタのサイズによって型の指定を調節するようにしています。

nobu:r34510 2012-02-09 16:48:22 +0900

DL の ALIGN_?? と SIZEOF_?? の rdoc の説明を自然な表現に修正しています。

kazu:r34511 2012-02-09 16:53:04 +0900

ChangeLog の typo 修正。

akr:r34514 2012-02-09 22:18:26 +0900

Enumerable#flat_map の rdoc にさらにサンプルコードを追記しています。

nagachika:r34516 2012-02-09 23:44:10 +0900

Pathname#binread のテストケースで読み込んだ文字列のエンコーディングが ASCII-8BIT であることのチェックを追加しました。

Permalink | コメント(0) | トラックバック(0)

■[ruby][changes]ruby-trunk-changes r34463 - r34493

今日は OpenSSL の不具合修正、機能追加と rb_str_modify_expand() の潜在的なメモリリークの修正がありました。

emboss:r34463 2012-02-08 09:29:26 +0900

OpenSSL::Cipher の rdoc に IV (初期ベクトル/初期値(Value)かも)を OpenSSL::Cipher#random_iv で生成すべきという説明のところに、key もランダムに生成されるけど、これを IV として流用してしまうと脆弱性になるよということを追記しています。

svn:r34464 2012-02-08 09:29:31 +0900

version.h の日付更新。

emboss:r34469 2012-02-08 10:03:16 +0900

OpenSSL::ASN1::GeneralString の変換用テーブル(？)に定数を追加するところで INT2NUM() を2重に呼んでしまって間違った値が格納されていた不具合を修正しています。 [ruby-core:42358] [Bug #5972]

naruse:r34470 2012-02-08 10:04:07 +0900

r34449 で tool/merger.rb がマージ操作前に working copy に作業中のファイルが残っていたらエラー終了するようにしましたが、svn up でリポジトリの変更を取得するようにしています。取得後に再度ゴミが残ってないか確認しなくていいんですかね？

emboss:r34481 2012-02-08 13:19:33 +0900

OpenSSL::X509::Name#to_a が OID の短縮版の名称を返そうとする時に、短縮版が存在しないと "UNDEF" という文字列にしてしまっていたので、元の長い名前を使うようにしています。 [ruby-core:41769] [Feature #5787]

OID って何だよ、というのはわたしもよくわかってません。

nahi:r34482 2012-02-08 14:27:14 +0900

SSL_CTX_set_options() という OpenSSL の挙動を変更するオプションの設定を OpenSSL::SSL::SSLContext#options= で設定できるようにし、ここにセットするためのビットフラグを OpenSSL の定数として Ruby から使えるように定義を追加しています。 [ruby-core:39673] [Bug #5353]

TLSv1/SSLv3 の脆弱性対策として OP_DONT_INSERT_EMPTY_FRAGMENTS というビットを落とす方法があり、それを Ruby からも実行できるようにしているようです。 詳細は ChangeLog 及び以下の参考 URL を参照してください。 http://www.openssl.org/~bodo/tls-cbc.txt

naruse:r34488 2012-02-08 18:49:36 +0900

OpenSSL::X509 の "street" という主体者フィールド(証明書の発行者の情報)の項目は OpenSSL の 0.9.8m からサポートされたものなので、OpenSSL::X509 のテストから削ってバージョンをチェックしたテストケースを追加してそこでテストするようにしています。

naruse:r34490 2012-02-08 20:47:00 +0900

r34488 の OpenSSL のバージョンチェックの条件が反転していたので修正。

nobu:r34492 2012-02-08 22:30:04 +0900

String のバッファを必要に応じて拡張する C API rb_str_modify_expand() で共有されていない & struct RVALUE に文字列が埋め込まれてない(つまりヒープからバッファを割り当てている文字列)でメモリを再割り当てする時に、以前のバッファを解放していメモリリークの不具合があったのを修正しています。 CRuby のコアで使っているところは共有されている場合に呼ばれているので Ruby のメソッドを使っていてメモリリークが発生することはどうやらなさそうですが、拡張ライブラリで rb_str_modify_expand() を呼んでいて踏む可能性があるもののようです。ただこれまで intern.h にプロトタイプ宣言がなかったみたいなのでおそらくまだ誰も使っていないでしょう。

nobu:r34493 2012-02-08 22:35:27 +0900

r34492 で修正したメモリリークのテストを追加しています。メモリ使用量を監視するために Windows では DL を使って Win32API の GetProcessMemoryInfo() を呼んだり、/proc/self/status を読んだり、 ps(1) コマンドの出力を読んだりしてチェックしています。すごい。

Permalink | コメント(0) | トラックバック(0)

■[ruby][changes]ruby-trunk-changes r34456 - r34462

今日は st.c の pack されたテーブルの処理中に unpack された場合の動作の修正などがありました。

nobu:r34456 2012-02-07 14:29:20 +0900

st.c の st_foreach で packed 状態のテーブル(numhash)を巡回中に要素が追加されて unpack された場合に unpack 版の処理に飛ぶときに同じ要素を再度ブロックに渡されないように修正しています。

svn:r34457 2012-02-07 14:29:27 +0900

version.h の日付更新。

nobu:r34458 2012-02-07 14:43:49 +0900

r34456 で追加したテスト用の numhash を利用する拡張ライブラリでメモリ解放関数の登録忘れを修正。

nobu:r34460 2012-02-07 14:52:15 +0900

st_update() (st_lookup() + st_insert()/st_delete() 相当の関数)でもブロックの実行中に packed 状態のテーブルに要素が追加されて unpack された場合に unpacked 版の処理に移行する処理を実装しています。

nobu:r34461 2012-02-07 19:37:40 +0900

st.c の packed 状態の処理は table->bins を st_value 型の key と value のペアが順番に並んだ配列として扱うのですが、 key, value がの2つのメンバをもつ構造体 st_packed_entry を導入して、table->bins を st_packed_entry の配列として扱うようにリファクタリングしています。

構造体がうまくpackされている(余計なpaddingがない)ことをチェックさせるために STATIC_ASSERT というマクロが定義されていておもしろいです。typedef 中に三項演算子を使うのとか古いコンパイラでも動くでしょうか。

ayumin:r34462 2012-02-07 20:13:40 +0900

Exception#inspect の rdoc の typo 修正。

Permalink | コメント(0) | トラックバック(0)

■[ruby][changes]ruby-trunk-changes r34433 - r34449

今日は Encoding.compatible? の不具合修正がありました。

naruse:r34433 2012-02-06 00:17:50 +0900

Encoding.compatible? では第2引数の文字列が ASCII 文字だけだった時に第1引数が ASCII-8BIT だと例外的に第2引数のエンコーディングを返すようにしていましたが、String.concat などの文字列の連結時の挙動と揃っていなかったので第1引数のエンコーディング(つまり ASCII-8BIT)を返すように修正しています。 [ruby-core:42354] [Bug #5968]

svn:r34434 2012-02-06 00:17:54 +0900

version.h の日付更新。

naruse:r34449 2012-02-06 21:55:56 +0900

リリースブランチなどへのバックポート用のツール tool/merger.rb でマージする前に svn の working copy に変更が残っている状態だったらエラー終了するようにしています。またコミット後に svn up でリポジトリから変更を取得するようにしています。

Permalink | コメント(0) | トラックバック(0)

■[alloy]帽子の色あてパズルを Alloy で解く

どこが元ネタなのかよくわかりませんが、数日前に帽子の色をあてるゲームで誰が回答できるか、というパズルが流行ってたようですね。確かこんな問題でした。

白か黒の帽子をかぶった A, B, C, D の4人の子供が並んでいる。

A と B, C, D の間には仕切りがあり互いに見えない。B, C, D はこの順に並んでおり C は B が、D は B と C が見える。

全員は帽子が白黒合計2つずつであることと、お互いの位置関係は知っている。

A と C が黒、B と D が白の帽子をかぶっている時、最初に自分の帽子の色を答えられるのは誰か。

いやまあ答は C なんですが、今 Alloy という形式手法の言語を勉強していまして、これはどうやらパズルを解くのにはもってこいのツールであるようですので練習がてらこのパズルを Alloy を使って解いてみようと思った次第です。

まず最初にそれぞれが自分の直接見えている子の帽子の色をみて自分の帽子の色を言いあてることができるか(というか、できないこと)を証明するモデルを書きました。

https://gist.github.com/1743472#file_puzzle_1.alloy

enum Cap { Black, White }

abstract sig Children {
  cap:    one Cap,
  visible: set Children
  }

one sig A extends Children {} {
  visible = none
  cap = Black
  }
one sig B extends Children {} {
  visible = none
  cap = White
  }
one sig C extends Children {} {
  visible = B
  cap = Black
  }
one sig D extends Children {} {
  visible = B + C
  cap = White
  }

fact {
  #cap.Black = 2 and #cap.White = 2
  }

pred CanAnswer(c: Children) {
  #(c.visible :>cap.Black) = 2 or #(c.visible :> cap.White) = 2
  }

run {
  no c: Children | CanAnswer [c]
}

見えてる範囲に白か黒の帽子が2つあればあとは反対の色の帽子しかありえないから回答できる、というのをがちがちに書いたのが CanAnswer という述語です。でも A, B, C, D の誰もそれを満たさないので、これだけだと誰も回答できないことになります。

つまり「誰もすぐには回答できない」ということと、お互いの可視関係の知識をヒントとして利用しないといけないわけなので、そういうルールを追加してやらないといけません。というわけで小一時間ほどうーんと唸って書いたのがこちらです。

https://gist.github.com/1743472#file_puzzle_2.alloy

// 帽子の色
enum Cap { Black, White }

abstract sig Children {
  cap:    one Cap,        // かぶっている帽子の色
  visible: set Children   // 見える他の子供
  }

// A, B, C, D の条件
one sig A extends Children {} {
  visible = none
  cap = Black
  }
one sig B extends Children {} {
  visible = none
  cap = White
  }
one sig C extends Children {} {
  visible = B
  cap = Black
  }
one sig D extends Children {} {
  visible = B + C
  cap = White
  }

fact {
  #cap.Black = 2 and #cap.White = 2
  }

// c の帽子の色の合計のいずれかが num なら真
pred CountCapNumber (c: Children, num: Int) {
  #c :> cap.Black = num or #c :> cap.White = num
  }

// 前をみた瞬間に答えられるか
pred すぐに回答できる (c: Children) {
  CountCapNumber [c.visible, 2]
  }

// 他の子の回答(ができないこと)を待って答えられるか
pred 少しして回答できる (c: Children) {
  // すぐに回答する子はいない
  no a: Children | すぐに回答できる [a]
  // 答えられない誰かが自分を見ているなら、共通して見える子の帽子の色が
  // 1=(2-1)なら回答できる
  some a: Children | c in a.visible and CountCapNumber [c.visible & a.visible, 1]
  }

pred 回答できる {
  some c: Children |
    すぐに回答できる [c] or 少しして回答できる [c]
  }

run 回答できる

なんか急に述語に日本語を使っていますが、途中で日本語をつかってもいい & 使ったほうが結果が見やすいことに気がついたので方針を変更してます。

「少しして回答できる」という述語に誰もすぐに回答できない場合にそれをヒントとして回答できる条件を記述しています。これを使ってモデル図を表示させるとこうなります。

やったね、C が回答できるってわかったよ。

……なんかちょっと虚しいですね。正直「少しして回答できる」の条件は ad hoc すぎるというか、そこまでわかってたらもう問題解けてるだろという気がしないでもないので、もうちょっと関係式に基づいた書き方ができるといいかなと思うのですが、わたしの今の Alloy 力ではかないませんでした。

でもですね、この A, B, C, D のシグネチャの制約の cap の色を割り当ててるところをコメントアウトすると、任意の帽子の色の組み合わせの時に誰が最初に回答できるかというのが列挙できるんですよ。たとえばこんな結果が得られます。

うん、C か D だってことは知ってた……。

もうちょっと先に進めるとすると、たとえば最初の帽子の色の組み合わせだと C が回答した瞬間に今度は B が自分の帽子の色を推定できるんですよね。では D が(すぐに)回答できた場合は何が起きるのか? などというのをモデリングしようと思うと、もっと根本的にモデルの書き方を変更しないといけないような気がしています。よくわかっていないのですが Alloy は 1階論理しか扱えないので、こういう他の人の回答がそのまま知識になるという問題をモデリングしようとすると工夫が必要なのだと思います。誰か Alloy エキスパートが現われてずばっと解いてくれないかなぁ。

Permalink | コメント(0) | トラックバック(0)