-*- text -*-
Subversion ファイルシステムの履歴
(a love song for libsvn_fs, by C. Michael Pilato)
Subversion ファイルシステムはその公開されたAPI のどちら側で作業するか
によって、あなたの最良の友、あるいは、最悪の敵となるでしょう。
libsvn_fs の呼び出し側は roots(バージョン化されたディレクトリツリーの
リビジョンまたはトランザクションに与えられた名前ですが) によって指定さ
れる心地よい世界で作業することができます。しかしひとたびその海に潜るや
すぐに、美と醜の両面をもつ獣があなたを待ち受けていることを知るでしょう。
時間と空間の軸をもつ座標システムの一種としての外部世界に見えていたもの
は、実際には複雑な DAG のサブシステムであり、お互いにさまざまな関係に
よって相互につながれたバージョン化された場所のリビジョンを表現するノー
ドがそれに関連していることがわかるでしょう。
このドキュメントの目的にははっきりしています: DAGサブシステムを制覇す
るための知識を伝えること -- 何人かの開発者の頭の中にしかないような知識
を伝えること -- それによって少人数しか知らなかったことを多くの人が知る
ようになるでしょう。
Node-Revisions: DAG のノード
ファイルシステム API の外で作業する場合、人々は通常、リソースのパスに
よって示されるバージョン化されたリソースについて話をし、それらのパスが
あるグローバルリビジョン(またはこれからできるリビジョン)について語りま
す。しかしファイルシステムの内部では、パスは分解され回想的なパスの集ま
りのリンクリストとして保存されます。これらのパスの集まりのそれぞれはそ
れ自身の系譜をもち(と、いうのは Subversion はディレクトリもバージョン
化するから!)、その系譜のそれぞれのリビジョンはノードリビジョンとして参
照されます。DAG サブシステムあるいは DAGノードとは、これらのノードリビ
ジョンのことを言います。
DAG ノードはノードリビジョンIDと呼ばれる一意のキーによって識別され、さ
まざまな形で内部的につながっています。ディレクトリを表現する DAG ノー
ドは他のどのDAGノードがそのディレクトリの子供を表現するかという情報を
保存しています。DAG ノードは他のどのDAGノードがその歴史上の祖先である
かという情報を持っています。ノードからノードへとこれらのリンクをたどる
ことによって、ファイルシステム宇宙全体の、時間と空間、地理と歴史の両方
の方向に対して効率的にリンクをたどることができます。
たとえば、ファイルシステムのリビジョン 4 にあるパス
"/trunk/src/main.c" は四つの DAG ノードを消費します: "/", "/trunk",
"/trunk/src", そして"/trunk/src/main.c" です。"/" の DAG ノードは自分
の子供の名前とノードリビジョン ID の一覧を含んでおり、その中に "trunk"
という名前の子供のノードリビジョンIDを持ったものも含んでいます。同じこ
とが "/trunk"(の中の src) や、"/trunk/src"(の中の main.c) にも言えます。
さらにもしこれらのパスがファイルシステムの前のリビジョン中で別の形で存
在していた場合、それらのDAG ノードはそれぞれの祖先のノードのノードリビ
ジョンID を保存するでしょう。
(XXX: Additionally, if these paths existed in different forms in
previous revisions of the filesystem, their DAG nodes would store the
node-revision IDs of their respective predecessor nodes.)
誰かが特定のルートの下にあるバージョン化されたパスに関する情報を問い合
わせるAPI を使うときは常に、中で起こっている典型的な処理は以下です:
1. ルートはDAGノードツリーの特定のスナップショットを参照し、そこか
らそのスナップショット中で現れるルートディレクトリ("/")をあらわ
すノードのノードリビジョンIDを取得することができます。このノード
リビジョンIDが手に入れば、それにつながるすべてのDAGも手に入りま
す。
2. パスは部分に分割され、ルートノードから始まり完全なパスに到るまで
たどっていきます。中間のすべてのノードリビジョンが読み込まれ、そ
れぞれのエントリーリストが解析され、パスに沿った次のノードリビジョ
ンIDを見つけるためにそのエントリーリスト中で次の部分が 検索
されます。
3. 最後に、そもそものパスのノードリビジョンIDに行き着きます。それと
それに結びついたノードリビジョンを使って質問に答えます。
とても簡単でしょう? 続けましょう。
ノードリビジョンIDに関するすべて
いま指摘したように、ファイルシステム中のそれぞれのノードリビジョンはユ
ニークなキーをもち、これはノードリビジョンIDと呼ばれます。このキーは典
型的には三つの部分からなるピリオドで区切られたリストに見える文字列で表
現されます。
1. ノードID: このキーは一つの系譜のメンバー間でユニークになります。
同じバージョン化されたリソースの異なるバージョンは、そのバージョ
ンが置かれたパスやリビジョンに関係なく、すべて同じIDを共有します。
もし二つのノードリビジョンが異なるノードIDを持つなら、それらは系
譜上は無関係です。
2. コピーID: このキーはユニークにコピー操作を識別ししばしばブランチ
ID として言及(いるは少なくとも考えられます)されます。二つのノー
ドリビジョンが同じコピーIDを持つなら同じブランチ上にあるといわれ
ます。唯一の例外はキー "0" であり、これは"ブランチ化されていない
"という意味の特別なキーになります。
3. トランザクションID: このキーはユニークにこのノードリビジョンが生
まれたSubversion トランザクションを識別します。
バージョン化されたリソースを修正するAPIを利用する時には常に、これらの
処理は問い合わせで利用された場合とほとんど同じになります。ただし重要な
違いがあります。
1. パスは前の節と同じやり方でたどられます。結果はパスの集まりからな
るノードリビジョンについての情報のメモリ上のリンクリストです。
2. しかし、パスに変更を加える前に、そのノードリビジョンとその親ディ
レクトリはまず複製され、変更がそのノードリビジョンの前の状態に影
響しないようにしなくてはなりません。この処理はパスを書き込み可能
にする処理と呼ばれます。もしこのトランザクションのもとでの前の処
理が一つ以上の親ディレクトリをすでに書き込み可能にしているなら、
再び複製を作ることはしません。
3. ひとたびパスとすべての親が書き込み可能となれば必要な変更はその複
製のノードリビジョンに対して実行することができ、それまでの履歴に
影響を与えることはありません。
ノードリビジョンを複製することは文字通りそのコピーを作ることであり、ユ
ニークなノードリビジョンIDの取得が許されています。新しいノードリビジョ
ンID は複製元のノードリビジョンと同じノードIDをもち(なぜならこれは単に
このバージョン化されたリソースの系譜の別の点にすぎないから)、コピーID
(これは後で説明します)、この変更が起きているトランザクションのID が付
与されます。
上の説明にはいくつかうまいアイディアが含まれています。ノードリビジョン
が作られるのは、新しいものが新規に作られるか、何かの複製として作られる
かのいずれかのみで、修正処理を除いて複製することはありえないので、トラ
ンザクションID を書き込みフラグの一種として利用することができるのです。
あるノードリビジョンの書き込み可能性はファイルシステムを修正するのに利
用されるSubversion トランザクションのIDとノードリビジョンのトランザク
ションID を比較することによって決定されます。それらが等しいとき、そし
てそのときに限り、そのノードはトランザクション中で変更することを許され
ます。
それで、トランザクションID が存在するようになる経緯を知ることができま
す。そしてノードIDの起源はほとんど自分自身の paragraph を保証すること
はありません(XXX:): 新しい歴史は新しいユニークなIDを手に入れ
(svn_fs_make_file() と svn_fs_make_dir()によって導入されるのですが)、
生成されたほかのノードリビジョンのすべては単に同じノードIDをノードリビ
ジョンの元になるIDとして保存するだけです。(XXX:)
ではそのコピーIDとは?
コピーIDはノードリビジョンがある開発ラインのブランチを区別するためにノー
ドリビジョンに対して割り当てられるものです。(本当は政治的な理由でコピー
IDと呼ばれています -- Subversion はブランチ化するAPI 自身を外向けに公
開していません。そのかわりにブランチとはパスを指定することによって簡単
に表現することのできる開発ラインにある分岐であるという考え方を広めよう
としています。) 新しいコピーID はブランチ操作が起きるときは常に確保さ
れます。新しいノードリビジョンは祖先からのコピーIDを引き継ぐことができ
ます(単純なクローン操作の場合)、あるいは親のどれかのコピーID を受け継
いだり(親がコピーされた場合)、新しいコピーID を作ったりすることもでき
ます。ブランチ化されていない場合には、ノードリビジョンには特殊なコピー
ID "0" が割り当てられます。
コピーとコピーID
現時点では二種類のコピー操作があります。最初のものは"本当の"コピーで
svn_fs_copy() の直接の結果です。本当のコピーがおきると、コピー元のノー
ドリビジョンはクローン化され、新しいノードリビジョンIDが用意されます。
このノードリビジョンIDはもとのノードID と新しいコピーID と、(常に) コ
ピーがおきたトランザクションID によって構築されます。
Subversion ファイルシステムは"コストのかからないコピー、おおざっぱな
(lazy な)移行" モデルを利用します。これは、ディレクトリノードリビジョ
ンが svn_fs_copy() 経由でコピーされるとき、コピーされたツリーの最上位
のノードリビジョンがコピーされ(すでに述べたように新しいコピーIDにより)、
そのツリーのすべての子供がコピーされるわけではありません。これは
svn_fs_copy() 操作を、少なくとも他の方法から比べれば非常に速いものにし
ます。この点から、コピー先の子供のアイテムはおおざっぱに(lazyに)移行さ
れると言われます。このコピーの後、そのような子供のどれかが最初に修正さ
れると、元の場所から目的の場所へとはじめてコピーが起きます。この緩やか
な移行手続きは通常のクローン操作と同じ程度のコストであり、低いコストで
コピーできます。
ファイルのコピーはディレクトリの場合と違いはありません。しかしファイル
は子供を持つことがないので、コピーされる"ツリー"は正確に一つのノードリ
ビジョンです。このノードリビジョンはコピー時に文字通りコピーされ、緩や
かな移行の方法はとりません。
もう一つのコピー操作はソフトコピーです。この形のコピーはファイルシステ
ムAPI によって明示的に呼び出されることはありませんが、他のファイルシス
テム操作の実装と同じ技です。ソフトコピーは同じ親を持つ異なるブランチ中
にノードリビジョンが存在する場合や再び親がブランチ化される場合は常に存
在します。は? ちょっと例をみてみましょう。
ディレクトリ "/trunk" があるとします。さて "/trunk" にツリーの別の場所
から"README" というファイルをコピーしてくるとします。こうしてもとの
"README" の歴史を効率的にブランチ化したことになります -- その一部はも
との場所にあり、残りの部分は新しい "/trunk/README" の場所に置かれます。
コピー操作は"/trunk/README" のための新しいノードリビジョンにあたしらい
コピーIDを割り当てますがそれは "/trunk" のノードリビジョンに割り当てる
コピーID とは異なっている必要があります。
このあと、"/trunk" を "/branches/mine" にコピーすることにしたとします。
すると新しい "/branches/mine" はまた新しいコピーID が必要ですがそれは
"/trunk" の履歴上のブランチになったからです。しかし 何かの修正の一環と
して後で "/branches/mine/README" がクローンされたら何がおこるでしょう
か? どのようなコピーIDを新しいクローンに割り当てるのでしょうか?
"/trunk/README" は "/trunk" とは別の履歴ブランチの上にあるので、
"/trunk" のコピーは(README の中で) ブランチのブランチになります。それ
で "/branches/mine/README" は新しいコピーID を割り当てられ、ファイルシ
ステムはその ID に関連したコピー操作はソフトコピーであったことを記憶し
ます。
### todo: put the copy-id choosing algorithm here
Traversing History
トラバーシングの履歴
### todo: put the history harvesting algorithm here