脳log[2008-05-15～]

♪ [Ruby][正規表現] /n, /s, /e, /u, $KCODEのもやっとを解消

正規表現リテラルの /nseuフラグは正規表現のマッチ動作に影響を与える。(/nseuフラグのいずれも指定しなかった場合は実行時の $KCODEに従う)

/nが指定されていたり $KCODE='NONE'のとき、「.」は改行を除いたり改行を含んだりする 1バイトにマッチするメタ文字だが、/seuフラグが指定されていたり $KCODEが SsEeUuのいずれかで始まる文字列のとき、「.」は日本語を含む、Shift_JIS、EUC-JP、UTF-8の一文字(1-3?バイト)にマッチする。

/nseuフラグや $KCODEは正規表現のパターンの解釈にも影響を与える。

Shift_JISで保存したスクリプトファイルに /表w/ というパターンと '表w' という文字列リテラルがあり、マッチを行った場合。実行時に $KCODE='NONE'であればパターンは /\225\w/ と解釈され、"\225"の後にメタ文字 \wにマッチする文字を探し、失敗する。$KCODE='SJIS'であればパターンは /表w/ と解釈され、"表"のあとに "w"を探し、成功する。

irb(main)> /表w/n =~ '表w'
=> nil
irb(main)> /表w/s =~ '表w'
=> 0

正規表現パターンの中のマルチバイト文字は文字列の場合と同じく、あくまでバイト列であり、/nseuフラグや $KCODEがどうであれ EUC-JPで保存されたスクリプトの中の正規表現リテラル /あ/ は Shift_JISの「あ」を表すバイト列 "\202\240" にマッチすることはない。

♪ [正規表現][javascript][大型本] Jeffrey E.F. Friedl【詳説 正規表現 第3版】 オライリージャパン

読んだ。この日記で以前書いたようなこと(20080116p01, 20080111p01)は全て書いてあった。もちろんそれ以上に知らないこと(NFAのマッチングのしかた、NFA型正規表現エンジンに適用できる正規表現のチューニングの具体例、Unicodeサポート、Perl, .NET, Java, PHPの正規表現、\Gの使い方などなど)が書かれていた。

非常に読みやすい文章で書かれているし、必要なところでは必ず前後のページへの参照先が書かれている。章の始めには Overviewがあり、その章から読み始めた読者への配慮も忘れない。当たり前のことだけど、徹底されている。「まずこの本を読め。正規表現について話すのはそれからだ。」と言い切れる良い本。正規表現を初めて学ぶ人にも、効率について考える余地ができてくるほど既に正規表現を使っている人にも役に立つ。

すごく実用的なテクニックで、でも全く想像が及ばなかったものがある。168ページの「4.5.8.1 肯定の先読みを使ったアトミックグループの模倣」がそれ。

 肯定の先読みを使ったアトミックグループの模倣

/(?>pattern)/     // アトミックグループを使ったパターン
/(?=(pattern))\1/  // 先読みでアトミックグループを模倣したパターン

高機能化する他の実装にくらべて、昔のままの JavaScriptの正規表現はバックトラックを抑制する構文を持っていない。JavaScriptでは非常に有用。

20080116p01でも書いたが、次の終わらない正規表現

/"(?:[^\\"]+|\\.)*"/       // マッチに失敗するとき死ぬほど遅い

はアトミックグループや絶対最大量指定子が使えるなら次のように書けるが JavaScriptは両方ともサポートしていない。

/"(?:[^\\"]+|\\.)*+"/      // JavaScriptでは使えない
/"(?>(?:[^\\"]+|\\.)*)"/g  // JavaScriptでは使えない
/"(?:[^\\"]++|\\.)*"/      // JavaScriptでは使えない。※上2つとは少し意味が違う

次のように先読みでアトミックグループを模倣すると組み合わせの爆発を避けることができる。

/"(?=((?:[^\\"]+|\\.)*))\1"/
/"\1"/            // 上のパターンから先読み部分を取り除いたもの。

先読みを取り除いたパターンを見ると一目瞭然だが、引用符がペアになっていなくて \1 の後ろの " のマッチに失敗したとしても戻る場所がない。あるのは " と \1 にマッチしたという結果で、どちらもオプションではないので取り消すことはできず、繰り返しでもないのでマッチした部分を少しずつ手放させることもできない。なので、ちょっとずつ後じさりしながら延々とあらゆる組み合わせのマッチを試行することなしに、マッチが失敗に終わったことが即座に判断できるようになるというわけ。本物のアトミックグループよりは劣るが効率も悪くない。同じ働きをする次の二つのパターンとかかる時間を比較してみた。

/"[^\\"]*(?:\\.[^\\"]*)*"/
/"(?:[^\\"]|\\.)*"/

 手順

バックトラックによる組み合わせの爆発が起きない 3つのパターンでかかる時間を比較。3回実行した。(3回繰り返しても一回一回の中の試行順が固定されていたら傾向は同じになるわな。無意味。あてみやむいみ)

var re = [
	/"(?:[^\\"]|\\.)*"/,
	/"(?=((?:[^\\"]+|\\.)*))\1"/,
	/"[^\\"]*(?:\\.[^\\"]*)*"/
];
var s = [
	'"'+ new Array(5000+1).join('\\"'),        //  1/100
	'"'+ new Array(500000+1).join('\\"') +'"',
	'"'+ new Array(500000+1).join("\\'"),
	'"'+ new Array(500000+1).join("\\'") +'"',
	'"'+ new Array(500000+1).join('a'),
	'"'+ new Array(500000+1).join('a') +'"'
];
var results = [];
for(var j = 0; j !== s.length; ++j) {
	var result = [];
	for(var i = 0; i !== re.length; ++i) {
		var t0 = new Date();
		var m = re[i].exec(s[j]);
		result[i] = new Date() - t0;
	}
	results[j] = result;
}
WScript.Echo(results.join("\n"));

 結果

数の単位は msec。

 みどころ

• マッチに失敗するときの、成功するときに比べた遅さ。
  • パターン2は例外
• パターン2(アトミックグループの模倣)ではしばしばマッチに失敗する方が速い。
  • \1のマッチが成功だと判断するにはキャプチャした長い長い文字列を最後までたどって比較する必要があるため、\1のマッチに失敗するほうが速くなる？
• 文字列1Fの特筆すべき遅さ。
  • 遅いとはいえ「終わらない」と形容するほど遅くはない。(これでも！)
  • 文字列長に比例したバックトラックが行われているせい？
  • 文字列2Fの結果と比較するに、\" という形で " が文字列の途中に含まれていることが最適化を阻んでいる？
• パターン3(ループ展開)は特定の場合を除いてパターン2(アトミックグループの模倣)より若干速い。
  • ループ展開は『詳説 正規表現』に載っていた言葉。
  • 特定の場合とは文字列3Fのことで、不用意なパターンを用いると処理が終わらなくなる場合のこと。
• パターン2(アトミックグループの模倣)は、(今回の眼目である)組み合わせの爆発が起こるような場合に、顕著な速さを見せる。
  • 他の文字列ではパターン3(ループ展開)に半歩譲るが。

ところで、文字列1Fがどのパターンでも一様に遅いのは文字列長に比例したバックトラックが行われているからなんだろうが、パターン2(先読みによるアトミックグループの模倣)でもそれを抑制できていないのは、なんとかできないものか。それでこそ若干のオーバーヘッドをのんででもアトミックグループの模倣を採用する理由になるのだが。

♪ [SHJS] URLのハイパーリンク化とバグ潰し

オリジナルの sh_javascript.jsはコメントの中の URLっぽい部分とメールアドレスっぽい部分をハイパーリンクにしていた。機能が劣るのは遺憾なので sh_javascript.jsと sh_ruby.jsに、コメントと文字列の中の URLっぽい部分をハイパーリンク化する機能を追加した。

その過程で気付いた、一行コメントの終了条件などに使われている $アンカーのマッチングが行われない場合があったのを修正した。(行末に達した時点でマッチングを打ち切っていたのが間違い。$は空文字列にもマッチする。全てのマッチに失敗するまで続ける必要があった)。これは自分が 2008-02-25に持ち込んだバグでオリジナルには存在しない。

 サンプル / テストケース

• 一行目：コメント内の URLはリンクになっているか？
• 二行目：一行目のコメントの続きだと誤認されていないか？

# http://vvvvvv.sakura.ne.jp/ds14050/badboy/log/
How is this line highlighted ?

 最新の、未来において変更されている可能性のあるファイルへのリンク

• /shjs/sh_main.js
• /shjs/sh_main.min.js
• /shjs/lang/sh_ruby.js
• /shjs/lang/sh_ruby.min.js
• /shjs/lang/sh_javascript.js
• /shjs/lang/sh_javascript.min.js

♪ [Firefox] Firefox 3 beta 5の faviconがおかしくなったので

アイコンキャッシュを全削除。

>sqlite3 places.sqlite
sqlite> DELETE FROM moz_favicons;

favicon.icoが存在しないサイトの faviconが何かの拍子に別のサイトの faviconになってしまうことが何度かあった。(そしてそのサイトには favicon.icoがもともと存在しないため、更新されることもなく間違え続ける)

最終更新: 2009-09-01T05:05+0900

♪ [SHJS][Ruby] '%04d-%02d-%02d' % [2008, 5, 8] がうまくハイライトできない理由

このようにハイライトされます。

'%04d-%02d-%02d' % [2008, 5, 8]

(整形した)HTMLソースはこう。

<span class="sh_string">'%04d-%02d-%02d'</span> 
<span class="sh_string">% [2008, </span>
<span class="sh_number">5</span>
<span class="sh_symbol">,</span> 
<span class="sh_number">8</span>
<span class="sh_cbracket">]</span>

「% [2008, 」が一つの文字列にされてしまっている。どういう判断なのかと調べれば、%!string! と同じものだと見なされていた。(そのルールは自分で書いたんだけども)

知っていたでしょうか？ %リテラルの区切りには空白(改行も！)が使えるのでした。(alnumと mbchar以外なら OKっぽい。変態すぎるよ)

最終更新: 2010-07-05T10:38+0900

♪ regexpと書いて正規表現と読む

[大型本] Jeffrey E.F. Friedl【詳説 正規表現 第3版】 オライリージャパン

この本の著者は regex派だそうな。FedExと同じように読めるからだとか。自分は気分で regexだったり regexpだったり reだったり。regexpって書く人はどう読んでんの？ だって。そうか、読み方か。考えたこともなかった。Friedlさんの疑問にお答えしましょう。regexpと書いて正規表現と読む、です。

iPodを始め、よそでは 12:00 PM が正午を意味することについて(無理矢理)理由を考えてみました。

12:00-12:59が 12:00PM-12:59PM、00:00-00:59が 12:00AM-12:59AMになる理由。日本人の(と書いてもいいよね？)感覚では 12:00PM=00:00AM=深夜となるものが正午を表してしまう理由。

時刻と AM/PMをわけて考えなければいけない。まず、時刻の部分はそのまま読み方を表している。だから 0時台は存在せず 12時台が使われる (0時何分という読み方をする人もいるでしょうが、自分は 12時何分と読みます。時計の文字盤にも 0は無いし。本当の問題は海の向こうの人がどう読むか、ですが)。そして、AM/PMは午前か午後かを付加的に表している。

• 「今何時？」
• 「12時半」「午後の」
• => 12:30 PM

こじつけすぎるか……。(AM/PMが(午前/午後と違い)時刻の後ろに付くのは確かなんだけど)

00:30と書いて 12時30分と読んだり、午後0時半と読んだり、ひょっとしたら午後12時30分と読んだりする器用さが無いのが理由なんじゃないかと思ったのだが。*

 追記@2009-05-30: 午前!=AM。午後!=PMということだったの……か？

自分のケータイでこっそり⁑こんな修正が行われていた。

サブディスプレイの待受画面に表示される時計を「Digital1(12h)」にすると、0時（午前0時）台が0:xxAM、12時（午後0時）台が12:xxAMと表示される。（他の12時間表示では、正しくそれぞれ12:xxAM、12:xxPMと表示される）

午前0時台は 0:xx AMではなく 12:xx AMが正しいと書いてある。

午前と午後 - Wikipedia

同じく Wikipedia。日本でも海外でもいろいろあるみたいね(なにが正しいとは言い切れない)。でも日本の公の判断が理性的で良い。だから AM/PMなんて使わずに午前/午後を使うべき。一番面倒がないのは 24時間制を使うことだし、もちろん自分のデジタル時計は全てそうしてるけど。

♪ [Vista] スタートメニューに置いたものだからお気に入りが IEのものではなくなってしまった

• スタートメニュー検索は、プログラムの検索に最適化されていてファイルやフォルダの検索はいまいち。(検索結果のトップに表示されてさえ↓キーを何度か押す必要がある。何度選んでも表示順が上がらない)
• Documents、Pictures、Music、ゲーム、お気に入りはスタートメニューの右側の列に表示できるのに Videos、Downloadsは表示できない。

お気に入りに *.urlではなく *.lnkを保存。

• (ちょっと遠いけど)検索の手間と待ち時間なしによく使うフォルダを開くことが可能。
• スタートメニュー検索で、お気に入りと履歴カテゴリにフォルダ(へのショートカット)が表示される。(表示順はプログラムの後、ファイルの前だが、プログラムと同じように並べ替えや疑似フォーカス移動が行われる)

IEのお気に入りはフォルダへのショートカットに乗っ取られました。

 よく編集するテキストファイルやよく実行する Rubyスクリプトへのショートカットをスタートメニューに追加するとき

ターゲットを

"text.txt"
"script.rb"

とするか

editor.exe "text.txt"
ruby.exe "script.rb"

とするか。

前者のショートカットはどちらもただのファイルとして扱われ、後者は実行ファイルと同じように扱われる。「実行ファイルと同じように」とは、

• スタートメニューの最近開いたプログラムの一覧に追加される
• スタートメニューで検索したときに最上位に表示される

スタートメニューでのファイル・フォルダの検索がいけてないので、こういった一手間が必要になる。

♪ [SN25P] ユーザープロファイルの入ったディスクがお亡くなり。

間に挟むもの(RR2302, 玄蔵X4)とディスクの数(4)が増えれば障害の原因も増えるという至極当然の結果なのだろうか。

1. ログインしたら仮のデスクトップになった。
2. (メイン)プロファイルの入ったディスクが見えていないのが原因。
3. Windowsと同じパーティションに入っているプロファイルでログイン。
4. なぜかこれも仮のデスクトップに。
5. 再起動。
6. Windowsと同じパーティションに入っているプロファイルでログイン成功。
7. (メイン)プロファイルの入ったディスクが未初期化状態で発見される。

一応ソフトをダウンロードしてきてファイルシステムの修復を試みたが全くダメ。Windowsの機能で一週間ごとにバックアップを取っていたので、ふんぎりをつけて初期化。

 戻ってきたファイル

• 音楽ファイルの全て (mp3, tta, ape)
• 雑多なファイル (txt, pdf, eml, rb, gif, gz, xaml, db, cpp, bin, mcr, 拡張子のないファイル, ...)
• Subversionリポジトリ (fsfs形式。svnadmin verifyは成功した)
• フォルダ (ファイルよりフォルダの方がよく復活する。つまり、空のフォルダがたくさん……)

どんな抜けがあったのかはこれから明らかになっていくでしょう。(例えばドキュメントフォルダに放り込んでいた JustePort.exeのように、ひっそり消えているファイルが無数にあるはず)

 すでに判明している戻ってこなかったファイル

• exe (cabが戻っても setupプログラムがなけりゃ意味がない)
• ini (プログラムの設定が消滅)
• レジストリ (プログラムの設定が消滅)
• img (cueシート(と sub)だけでは意味がない)
• js (Firefoxの設定やインストール済みの拡張の構成ファイルなど。Webページを構成していたスクリプトもすっぽり消滅)
• bat (バッチ処理は Rubyで書いた方が良いということだな)
• lnk (スタートメニューやスタートアップフォルダが空)
• ジャンクション

思うに、拡張子でバックアップするファイルを選別するのは全く間違っている。特定のファイルをバックアップすることを想定していたのかもしれないが、今回起こったことは、特定のファイルだけが戻ってこないという状況。そのせいであちこちで不完全なファイルが発生している。imgのない ccd。jsのない html。setup.exeのない cab。などなど。

ユーザーが違えばその人が保存したいファイルも違う。同じ拡張子でも単にネットからダウンロードしてきただけのものか、その人が一から書いたファイルなのかでは価値が違う。自分がものを知っているなんて思わないで愚直に全部保存して欲しい。

♪ [tDiary][Ruby] CGI.escape と ERB::Util.u の違い

http://tdiary.cvs.sourceforge.net/tdiary/plugin/category.rb?revision=1.45.2.1&view=markup&sortby=date&pathrev=Stable-2_2

• 「 」が「%20」になる。(ERB::Util.u)
• 「 」が「+」になる。」(CGI.escape)

気付いたのは日記を書くときに、カテゴリ名入力支援機能(クリックすると本文にカテゴリが挿入される*)のカテゴリリストに目当てのカテゴリがなかったから。

脱線。何かのソースを見たときに思ったのだけど ERB::Util.u も CGI.escape もエンコードしすぎだと感じてる人がいるみたい。(一部の記号をわざわざ復号していた。たしかに %XX が URLに現れるのは美しくない⁑)

閑休。存在するはずのカテゴリファイルがなくてエラーを出していたのは、ここ(20071208p01)で自分が書いた tdiary/categorizedio.rb だったので誰にでも起こる不具合なのか確証がなかったり。

http://tdiary-users.sourceforge.jp/cgi-bin/wforum/wforum.cgi?mode=allread&no=5718&page=0

tDiary標準のカテゴリモードがどのようになるのかは未確認だったり。

複数のポストを日付で括ってしまう tDiary(<日記だから)はどうしても <title>タグの中身が味気なくなってしまって、ボットにも人間にもアピールが弱いな、とか全然関係ないけど、いま思った。(BlogKitでは解決してそう)

ぼそり。(category.rbは @conf.data_pathと 'category'を連結するときにパスセパレータを二重化してる。問題はレンタルサーバ(FreeBSD)でもローカル(Windows)でも起きていないが、そういうのが気持ちわるい＆気にしたくないので自分は File.joinや Scripting.FileSystemObject.BuildPathを必ず使う)

♪ [Firefox] Firefox3 beta5 をインストールした

Firefox2が標準ユーザーでのアップデートに失敗するようになっていて 2.0.0.14のインストールが面倒くさかった*ので 2をアンインストールして 3 beta5をインストール。Firefox2のときと違って

extensions.checkCompatibility false

を知ってるから、バージョンの数字だけを見て、ほとんどの拡張を使用不可能にされるアホらしい事態慎重すぎる対応は避けられる。(といっても半数近くの拡張がすでに 3に対応していた。Google Toolbarは Fx3をクラッシュさせた)

• http://firefox.geckodev.org/index.php?usercontent.css#gd114c0a を表示すると Firefoxの CPU(デュアルコア)使用率が 50%に張り付く
• フォームの background-color指定が効かなくなっている
• 選択テキストのドラッグが Safariばりにエロい (文字が滲んでて汚いが)
• 「同時に複数のタブを閉じるときは確認する」が働いていない
• 長い URLが折り返してる (white-space: pre-wrapも使えるとか)
• ブックマークアイコンがネスケだ (色合いが)
• タブキー押しっぱなしのフォーカス移動が高速
• <input type="file">が入力欄(に見える部分)も含めてボタンである

というのが気付いたところ。

 追記

フォームの背景色の問題は起こるところと起こらないところがある。自サイトの tDiaryと本棚では色が変わらないが、はてなや、google.co.jpのホームページの検索窓は色が変わる。google.co.jpでも、結果ページの検索ボックスは背景色が変わらない。(いずれも Firebugで Inspectして、userContent.cssで行った background-colorの指定が有効なのは確認している)

Firefox2と 3(の Gecko)で何が変わったのだろう。背景色が全く変えられなくなったわけじゃないみたいだけど。

 追記

borderや border-styleや border-widthをインラインスタイル属性として <input>タグに書き込むと背景色が変わった。(ボーダーの属性値は noneでも solidでも 0pxでも良い)

わけがわからないから、Firefoxの CSSへの準拠度が上がったせいでサイトデザインの不具合が明らかになった、というわけではないな。

最終更新: 2011-02-13T06:13+0900

♪ [BAD BOY]サイクルメーターのログを Google Chart APIでグラフ化

SVGでやろうとして頓挫していたものの続き。

Bad Boy log viewer

 使用したもの

• Google Chart API
• gchartrb-0.8