Last-modified: Fri, 21 Apr 2000 00:21:29 JST
[static,style:furuta,jconv:jcode,cache:on]
powered by tds-Tomsoft Diary System 1.01-beta0
将来のためにメモ。
RCS ファイルの木は、(差分の適用に関して) 幹(trunk)は逆順、枝(branch)は正順という基本ルールがある。 これはもちろん、効率のためであって幹の先頭(head)は 生テキストの形で記憶されているので、 取り出すコストが低くてすむ。 任意の revision を取り出すには、 まず幹の先頭からを根(root)に向って逆順に進みながら差分を適用する。 これで幹にある revision は取り出すことができる。 幹以外の枝にある revision は分岐点から今度は正順に差分を適用して 得られる。
RCS ファイル中の各 revision 毎のフィールドには、
の情報がある。このうち、log と text だけは 別区域にまとめられている。 つまり、最初は log と text 以外の revision 基本情報が順に並んでおり、 全ての revision の基本情報の後にまとめて revision の log と text が 並んでいる。詳しくは rcsfile(5) の BNF 参照。 これは効率のために長くなりがちな log と text を後に回して、 revision 木構造を構成するのを効率よくするためだろうと思う。
next フィールドは差分適用順序に関しての次の revision 番号を指している。 つまり、幹では一つ前の revision だが、枝では次の revision を指す。 branches フィールドはその revision から派生した枝の最も古い revision を指している。 幹の先頭から始めて、next と branches を再帰的に手繰ると 全ての revision に到達することができる。
rcsfile(5) には特に記述はないようだが、revision はこの差分適用順に 並んでいる。つまり、幹の部分は逆順に、枝は正順に並んでいる。 そのため next や branches は常に前方参照である。 また、next 方向優先で、その後に枝が並んでいる。 このため、任意の revision のテキストを得るには、 各 revision ごとにファイルを読む形式のプログラムであっても、 逆方向に seek する必要はなさそうである。 しかし、記述がない以上、この順序を仮定するのは得策ではなさそうだ。
text は幹の先頭だけは生テキスト (ただし、中の "@" 文字だけは escape される。 以下、差分や log 他、rcsfile(5) の "string" は全てそう)で、 それ以外の text は全て差分情報である。 差分情報は、diff(1) の -n オプションそのもの(の "@" を escape したもの) である。 差分情報に関しても rcsfile(5) には直接の言及がない。
deltatext ::= {difftext}*
difftext ::= addtext
deletetext
deletetext ::= "d" number number "\n"
addtext ::= "a" number number "\n" {freeform-line "\n"}+
「"d" number1 number2」は、number1 行目から number2 行分を削除せよ、 という意味で、「"a" number1 number2」 number1 行目の後に number2 行分 を追加せよ、という意味。 "a" 行の後には number2 行分の挿入行(freeform-line) が置かれている。 number1 はファイルの先頭行の場合は 1 行目。それより前に行を挿入するには、 "a0 ..." というような記述になる。 また、number1 は、そこにある差分適用前での行番号である。 頭から順に差分を適用すると、それより後の行の行番号は変化するが、 その変化する前の行番号で指示する。 ed にあるような "c" は "a" と "d" の組み合わせで指示する。
いくつかファイルを食わせてみたけど、パーザは何とか動いているようだ。
次はパーズしたデータを格納しておく必要がある。 まずファイルに global な情報と、revision 毎の情報。 vc-hooks.el を覗いていたら、 自前の obarray に intern したシンボルの plist にデータを格納しているようなので、それをまねてみる。 revision 毎の情報は、revision を obarray に intern して引出す。 ファイル全体情報は、revision 番号にならない文字列を intern してやる。 obarray を RCS ファイル毎に記憶しておく必要があるが、 これは buffer local 変数に入れておけばよさそう。 log や text などの string は emacs lisp の文字列として取りだすと 余計なコピーが発生するので、代りに marker でもって記憶しておくことにしよう。
とりあえず、情報を格納してから revision 番号の tree を構成する コードを書いてみるが、どうやら動いてそうだ。
mew のような形で表示するには、 Windows configuration を操作すると良いようだが、 code を読んでもさっぱり理解できないので、さらに精進が必要。
まあ、メンバーが少ないので はうンサーバユーザの日記とか一覧のように大きなコストダウンになるかというとよくわからないのです。 また、そこの情報は全部 *BSD Diary Linksから取得できる \ 訳で、それと比較して意味があるの? って話もあります。 ですから、 はにゃ〜ん あんてなのようにより頻繁に更新することで、 差別化して(他のアンテナに DI 情報などを)利用してもらう というのはあるかもしれません。
というか、某誌の某 ML ですが、 draft を書いたのだが、 これに反応したら確実に今年のゴールデンウィークも潰れる予感。(;_;)
そうですね。Java のデバッグは確かに困難です。 私も以前は println() でデバッグしてましたけど、 やはりある程度(すでに十数万行ある) の規模になると良質のデバッガが欲しくなります。 以前にも書いたけど、単に Java のデバッガとして、 Visual Cafeはおすすめです。VC++ のデバッガのレベルがどの程度かはよくわかりませんが、 少くとも emacs + gdb mode での C のデバッガ程度には便利です。 (変数の browse 機能が強力なので、もっと便利かも)
そかそか CGI でその場で調査している訳ですね。なら、意味はあるんじゃないでしょうか。
なるほど、SSI だけで他にプログラムやスクリプトが一切いらないのがミソなわけですね。
次は revision バッファ中の特定の revision を取り出して 表示させるか。 何だかこういうコンテキストとしてカレントバッファを持っていて ほとんどのバッファ操作がカレントバッファに対して、っていう パラダイムはどうも慣れない。
とりあえず、revision の表はバッファ上に表示できるようになったので、 やぱし、キー操作一発で枝全部見せたり隠したりしたいよね。 emacs って Outline mode が似たようなことをしてるよな、 という訳で、outline.el を読む。 むむ、何すか、この make-overlay つーのは。つーか謎。 info で (elisp) へ行って、ふむふむ。 ほー、emacs 20 からは Overlay なんつー便利なものがあるのね。 invisible な Overlay を作って被せてやると、あら不思議、 テキストはあるのに見えなくなってしまうと。 これを使ってみることにしませう。
肉、食った。
寝てた。一日じゅう。
寝てた。一日じゅう。
我ながらすごいと思う。 どうしたらこんなに自堕落になれるのか。 先週異様にテンションが高かった反動かな?
はりきらない。
ぐはぁ。きなくさいです。 うう、勉強します。
煮つまってきてる感じがする。 このへんで何となく考えていることをちゃんと 書き下した方が良いかも。
指定した revision をバッファ中に取りだしたい。 これは幹の先頭から始めて順次 delta を適用していけば、 どの revision でも計算できる。
が delta の適用を素直に実装してしまうのは効率が悪い。 一旦バッファに突込んでから一部テキストを削除したり追加したりするよりは、 ポインタレベルで挿入するべきテキスト(の部分)を計算しておいてから、 最後にまとめてバッファに挿入してやる、という方法である。
バッファに詰めこむテキスト行は全て RCS ファイル中にある。 そこで、RCS ファイルを適当なバッファに保持しておいて、 そのバッファ自体は read only にしておいていじらない。 その上でバッファへのマーカをポインタとして扱うことにする。 ある revision のテキストをポインタの形 のかたまり(chunk、いくつか行が集まった単位)で保存しておいて、 必要に応じて chunk の集合からテキストを組み立てることにする。
chunk 集合形式で表現しておくことにしておくと、 単なるテキストだけじゃなくて他の作業にも調子が良さそうだ。
さて、chunk 表現の構成アルゴリズムを考えないといけない。 まず最初は幹の先頭から始めて、順次幹を遡れば幹の情報は全部得られるはず。 幹の先頭はバッファ全体を表わす一つの chunk で表現できる。 それに delta を適用した場合、"d" や "a" に対応する chunk が 分割される(こともある)
"d" ではその部分のテキストがそれより前では消える。 つまりその次の revision で生成された部分だということがわかる。 "d" が chunk の全体を覆っていれば、 chunk 全体に「生成された revision」の情報を付加する。 "d" が chunk の一部を指していれば、 その部分で chunk を分割する。 あるいは "d" の覆い方によっては三分割される。 いずれにしろ、"d" に対応する部分には生成された revision の情報が付加される。 そして、delta を適用された「前」の revision には chunk は入らない。
"a" でテキストを挿入する部分は、 挿入されるテキストを指す chunk を新しく生成する。 "a" がちょうど chunk の境界を指していなければ、 そこで chunk は分割される。
この分割を繰り返して最終的に幹の「根」つまり最も古い revision (ふつうは revision 1.1) に至ればこの分割は終りになる。 この時点で根を構成している chunk の出自が明かになる。 生き残っている chunk を生成した revision は、幹の根だから、それを設定する。
枝の部分の delta は幹とは反対に正順なので、処理はもっと簡単。 分割されて出自が変ることはない。 新しく "a" で chunk を追加した場合のみ、 出自情報を設定すればよい。
分割した場合のデータ構造の扱いだけど、 分割前の chunk を親として分割後を子とする木構造で持ってりゃ 何とかなるだろう。
うむ、ずいぶん見通しが良くなったかな。 じゃ実装しよ。
うう、どう考えてもはりきっとるな。いかん。
また思い出した。
普通 diff(1) は最小差分を計算してくれる。 (すくなくとも、Version 7 の diff(1) はそのはず。 ただし、最小差分が必ずしもプログラムの差分を表現するには 適切でないこともあるとかで、GNU diff が最小差分を計算しているか どうかはよく知らない)
さて、最小差分の合成が最小差分とはならないことがある。
A A A B -> B' -> B'' C C C 1.1 1.2 1.3
という変更を考えた場合、1.1 と 1.3 の差分は「B -> B''」だけども、 ここで「B == B''」というケースを考える。 (こういう変更、つまり一旦施した変更を次の revision で元に戻すことは 極めてよくあること。また、枝の分岐点を考えてもこのような差分を 考えることは有用だと思う) この場合は前の「chunk」アルゴリズムでは差分を計算する方法は かなり不適切。 だから、別途「B == B''」状態(あるいは「B と B'' が B' よりもずっと近い」状態) を検出して、それなりの処理をしてやる必要がある。 具体的には、B と B'' の両端一致部分を剥ぐだけでも、 ずいぶんましになるはず。
しかしこの処理はある意味「小手先」に過ぎない。 結局、厳密な意味で「最小差分」を計算するには 1.1 と 1.3 のテキスト全体に対して diff(1) のアルゴリズム を適用するしかない。 効率の点からも実装の点からもこれを emacs lisp で実現するのは 馬鹿らしい。 かと言って diff(1) を呼び出すのも本来の目標から言って不本意。 diff(1) を呼び出すぐらいなら、いちいち自前で rcsfile(5) をパーズ しないで co(1) や rlog(1) を呼び出した方が良かろう。
というわけで、この問題は多分 BUGS 項目として認識しつつ、 「仕様です」と言いはなってつき進むしかないだろうな。
しまった。またはりきってしまった。反省。
うーん、完全に私のミスです。 私が甘かったです。 以降気をつけます。
絶賛ぽしごと中。反応遅くてごめんね。