ソースコードの木構造を考慮した 差分計算を用いる 版管理システムの提案 早瀬 康裕, 松下 誠, 井上 克朗 大阪大学大学院情報科学研究科

研究の背景 版管理システム オープンソース開発では、必ずと言ってよいほど使われている ソースコードやドキュメントなどの開発履歴を保存するシステム CVS に代表される オープンソース開発では、必ずと言ってよいほど使われている CVS の使用例: FreeBSD, XFree86, PostgreSQL 等

版管理システム 自由に 書換えられる ファイル リポジトリ リポジトリから ファイルを取得 開発履歴を 保存する データベース 開発者 編集 新しいファイル ファイル 編集されたファイル リポジトリへ格納

版管理システムを用いた複数人での開発 X’’ X’’’ 取得 X リポジトリ X’ X 編集 格納 開発者Ａ X’ 取得 最新版 開発者Ｂ 格納出来ない X X’’ 版管理システム によるマージ X’’’ 編集

問題 既存の版管理システムは、マージ (変更点の取りこみ) を行単位で行っていた 行単位のマージは、不正確な場合がある 同じ行が変更されていると、衝突しなくて良い変更が衝突する 衝突すべき変更が、行が違うことにより見逃される システムがマージに失敗したときは、開発者が手で直さねばならず、負担となっている

問題点1 不要な衝突 開発者 A と B が同じファイルを編集している マージ失敗 同じ行を編集すると変更点が衝突 問題点1 不要な衝突 開発者 A と B が同じファイルを編集している 同じ行を編集すると変更点が衝突 行が同じでも衝突するとは限らない マージ失敗 int refs=0; int refs; int refs=0; /* reference count */ int refs; /* reference count */

問題点2 衝突の見逃し 開発者 A と B が同じファイルを編集している 不正なマージ結果 衝突すべき変更を、行が違うために見逃す 問題点2 衝突の見逃し 開発者 A と B が同じファイルを編集している 衝突すべき変更を、行が違うために見逃す A が変数を削除 B が削除された変数を利用するコードを追加 int num, sum; int num, sum; ： avg = sum/num; int num, sum, avg; int num, sum, avg; ： avg = sum/num; 不正なマージ結果

研究の目的 精度の高いマージシステムを作り、開発者の負担を軽減する マージ時の不要な衝突を避ける マージによって引き起こされる問題を減らす 行よりも細かい単位でマージ処理を行う マージによって引き起こされる問題を減らす 変数の利用と定義が対応していることをチェック

ソースコードの構造を考慮したマージ ツリー構造の差分計算とマージ処理 実現方法 比較するソースコードを解析し、ツリー構造に変換 1. で作った2つのツリーの差分を、ツリーの差分計算アルゴリズムで計算 2. で求めた差分をマージしたいツリーに適用

1. ソースコードをツリーに変換 ソースコードを構文解析し、ツリーにする ツリーの頂点に ID を付ける ツリーの頂点には文字列が格納される ツリーから、元のソースコードに戻せるように、空白文字の頂点も作る ツリーの頂点に ID を付ける ID の付けかた 直前のバージョンと頂点の対応を計算して、 対応すると判断された頂点同士には同じ ID を付ける 頂点の対応については後述 変数を利用している部分から、定義している部分へリンクを張る Block { int i; i; } 空白 Declare 空白 Statement 空白 int 空白 i variable

2. ツリーの差分計算 頂点に ID の付けられたツリーの差分を計算する ツリーを編集するための編集操作は 4 つ 頂点の追加: insert(新ID, 文字列, 親ID, index) 葉頂点の削除: delete(ID) 頂点に格納された文字列を更新: update(ID, 新文字列) 部分木を移動: move(ID, 移動先の親ID, index) 編集操作の列を編集スクリプトと呼ぶ ツリーに適用することで、ツリーを変換する

差分スクリプト ツリー A とツリー B の差分を、 A を B に変換する 編集スクリプトで表現する 条件を満たす編集スクリプトは無数に存在する 例: A を B に変換する、ある編集スクリプト S に、 A にも B にも含まれない頂点を追加して削除する操作を加えた編集スクリプト S’ も、 A を B　に変換する 条件を満たすスクリプトの中から、無駄の無いものを探す 編集操作にコストを定義する 編集スクリプトのコストを、含まれる編集操作のコストの総和とする コストの小さい編集スクリプトが良いスクリプト 既存のアルゴリズム xmdiff と FMES を採用

xmdiff アルゴリズム 最小コストの編集スクリプトを求める、外部記憶用アルゴリズム 時間計算量 O(n2) 編集操作: insert, delete, update 編集操作のコストは0より大きい任意の値 提案手法では以下の値を用いる insert のコスト = delete のコスト = 頂点の付けられた文字列の長さ update のコスト = 書換え前後の文字列の長さの和 - 2*文字列の共通部分の長さ Edit Graph (動的計画法の表) を用いる 縦軸横軸に、新旧ツリーの頂点を深さ優先探索順に並べる 縦横の辺を insert と delete に、斜めの辺を update に対応 辺の重み: 操作のコストに対応 原点から対角までの最小コスト経路が、編集スクリプトに対応 表をメモリに収まるサイズに分割して効率的に計算 S. Chawathe, "Comparing hierarchical data in external memory," presented at Twentyfifth International Conference on Very Large Data Bases, Philadelphia, PA, 1999.

FMES アルゴリズム 差分スクリプトを求める近似アルゴリズム 時間計算量 O(ne+e2) (e は差の大きさ) 良い近似を得るための条件: e << n 編集操作は insert, delete, update, move insert のコスト = delete のコスト = moveのコスト =1 update のコストは変更前後の値によって 0以上 2以下の値 提案手法では (1 – 文字列の共通部分の長さ*2/書換え前後の文字列の長さの和)*2 2つの段階に分けられる ツリー間での頂点の対応関係の計算 葉と内部頂点を区別 類似度が閾値以下の頂点同士は対応しないと仮定 頂点の対応が取れたツリー間で編集スクリプトを計算 S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom. Change detection in hierarchically structured information. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 493-504, Montr'eal, Qu'ebec, June 1996.

3. マージ ツリー A とツリー B の差分スクリプト S を、 A でないツリー C に適用することをマージと呼ぶ 問題: 編集操作は頂点 ID を引数に取るが、 A と C で同じ ID の頂点があるとは限らない 同じ ID を持つ頂点が無いときは、類似した頂点を探す 親や子が共通 兄弟が共通 ラベルが同じ よく似た頂点が見つかれば、代用してみる 見つからなければ編集操作を適用しない

どれが正しいかをシステムが決めることは出来ない マージ結果の選択 差分計算のアルゴリズムによって、異なった差分スクリプトが出力されうる 類似頂点の探し方には、複数の方法がある マージ結果は複数存在しうる どれが正しいかをシステムが決めることは出来ない 解決方法 複数の方法でマージを試す 差分アルゴリズムと類似頂点検索方法の組み合わせ 複数のマージ結果が得られた場合には、構文制約などで点数付けして整列し、開発者が選択する

マージの例 A B 0 if 0 if update(6, i) move(5, 1, 1) delete(4) 1 then 4 else 2 doA 5 doB 5 doB 2 doA 3 x 6 y 6 i 3 x C 0 if D1 D2 D3 update(6, i) move(8, 1, 1) delete(4) update(6, i) move(5, 1, 1) delete(4) update(6, i) move(5, 1, 1) delete(4) 0 if 0 if 0 if 1 then 4 else 1 then 1 then 4 else 1 then 8 doC 2 doA 2 doA 8 doC 2 doA 2 doA 8 doC 9 z 3 x 3 x 9 z 3 x 3 x 9 z

システムを使って解決する問題1 行単位のマージでは、同じ行の編集で衝突していた マージ失敗 int refs=0; int refs; int refs=0; /* reference count */ int refs; /* reference count */

問題1 に提案手法を使った場合 マージ成功 元の行 ソースコード に変換 親 Declare 親 int refs 親 Declare 親 Declare Comment Declare int refs reference count 親 int refs Declare Comment ソースコード に変換 int refs reference count int refs=0; /* reference count */

システムを使って解決する問題2 宣言されていない変数を使う問題を見逃していた 不正なマージ結果 int num, sum; ： avg = sum/num; int num, sum, avg; int num, sum, avg; ： avg = sum/num; 不正なマージ結果

問題2 に提案手法を使った場合 変数の参照先が無いので衝突 Declare List int num sum Declare List リンク切れ int num sum variable int num sum avg Declare List int num sum avg variable

システムの実装方針 既存の版管理システム subversion を拡張する subversion よりよい CVS を目標として新規開発されている版管理システム 特徴 サーバ・クライアント型システム クライアント側での差分計算・マージ処理 ソースコードをツリーに変換した状態でリポジトリに格納 ツリー表現には XML を使う 拡張で開発者の作業手順を変更しない

システムの概要 XMLのマージ機能 ソースコードとXMLの変換 subversion クライアント 差分計算 制約検査して FMES, xmdiff 制約検査して 違反数で整列 差分適用 subversion サーバ XMLのマージ機能 リポジトリ 開発者 ソースコードとXMLの変換 ソースコードに変換 頂点対応の計算 (FMESの前段階) XMLへ変換

取得と格納 取得時の処理 格納時の処理 subversion クライアント 差分計算 制約検査して FMES, xmdiff 差分適用 違反数で整列 差分適用 開発者 subversion サーバ 取得時の処理 格納時の処理 リポジトリ ソースコード 頂点 ID 付き XMLファイル 取得した XMLファイル 編集 ソースコードに変換 頂点対応の計算 (FMESの前段階) 編集した ソースコード 頂点ID無し XMLファイル XMLへ変換

マージ マージ時の処理 subversion クライアント 開発者 差分計算 制約検査して FMES, xmdiff 差分適用 違反数で整列 サーバ 差分 マージ結果 のXML マージ結果の XML(複数) マージ結果 のXML マージ結果の ソースコード (整列済) 最新版の XMLファイル リポジトリ マージ結果 のXML マージ結果の XML(整列済) 頂点 ID 付き XMLファイル 取得した XMLファイル 開発者に提示 ソースコードに変換 頂点対応の計算 (FMESの前段階) 編集した ソースコード 頂点ID無し XMLファイル XMLへ変換

まとめと今後の課題 まとめ 今後の課題 既存の版管理システムの問題点 解決法としてソースコードの構造化マージを提案 システムの設計について説明 今後の課題 システムの実装 システムの評価 ソースコード以外のドキュメント形式への対応