ソースコードの階層構造を考慮した版管理システム

構文木の差分を用いた
細粒度版管理システムの提案と実現
井上研究室
早瀬康裕
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
1
目次
版管理システム
 ソースコードをマージする際の問題
 研究の目的
 ツリーのマージ

 ステップ1.
ソースコードをツリーに変換
 ステップ2. ツリーの差分計算
 ステップ3. マージ
システムの実装
 実験
 今後の研究について

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
研究の背景
インターネットの普及により、オープンソースソフトウェア開発が広まっている
特徴
世界中に分散した、多くの開発者が参加する
 開発が職務でない人々を含む、緩い共同体
 コミュニケーションのコストが大きい
以下のような道具を用いて開発を行なっている
 版管理システム
 ソースコードやドキュメントなどの開発履歴を保存するシステム
 CVS に代表される
 メーリングリスト
 開発者やユーザの意見を交換する
 バグ管理システム
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
版管理システム
リポジトリ
リポジトリから
ファイルを取得
開発履歴を
保存する
データベース
自由に
書換えられる
ファイル
編集
新しいファイル
ファイル
リポジトリへ格納
開
発
者
編集された
ファイル
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
4
版管理システムを用いた複数人での開発
X’’’
X’’
取得
X’
X
リポジトリ
X
格納
編集
X’
取
得
開発者Ａ
最新版
格納オープンソース開発では、
(X’)の取得このまま格納するとこのように、同時に
開発者Aの変更が失われてしまう
編集を行う事がよく起こる
開発者Ｂ
X’’
X
編
集
版管理システム
によるマージ
X’’’
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
5
問題


既存の版管理システムは、マージを行単位で行っていた
行単位のマージは、ソースコードに適用するものとしては
不正確な場合がある
1.
2.
同じ行が変更されていると、
衝突しなくて良い変更が衝突する
変更された行が違うことにより、
衝突すべき変更を見逃す
システムがマージに失敗すると、
開発者が手で直さなければならず、負担となっている
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
問題点1 不要な衝突

開発者 A と B が同じファイルを編集している
 同じ行を編集すると変更点が衝突
 行が同じでも衝突するとは限らない
int refs=0;
int refs;
int refs; /* reference count */
マ
ー
ジ
失
敗
int refs=0; /* reference count */
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
問題点2 衝突の見逃し

開発者 A と B が同じファイルを編集している
 衝突すべき変更を、行が違うために見逃す
A が変数を削除
B が削除された変数を利用するコードを追加
int num, sum;
int num, sum, avg;
int num, sum, avg;
：
avg = sum/num;
int num, sum;
：
avg = sum/num;
不正なマージ結果
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
研究の目的
精度の高いマージシステムを作り、開発者の負担を
軽減する

マージ時の不要な衝突を避ける
行よりも細かい単位でマージ処理を行う

マージによって引き起こされる問題を減らす
変数の利用と宣言が対応していることをチェック
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
目次
版管理システム
 ソースコードをマージする際の問題
 研究の目的
 ツリーのマージ

 ステップ1.
ソースコードをツリーに変換
 ステップ2. ツリーの差分計算
 ステップ3. マージ
システムの実装
 実験
 今後の研究について

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
ソースコードの構造を考慮したマージ

ツリー構造の差分計算とマージ処理

実現方法
ステップ1. 比較するソースコードを解析し、
ツリー構造に変換
ステップ2. ステップ1 で作った2つのツリーの差分を、
ツリーの差分計算アルゴリズムで計算
ステップ3. ステップ2 で求めた差分を、
マージしたいツリーに適用
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
ステップ1. ソースコードをツリーに変換

ソースコードを構文解析し、ツリーにする
ツリーの頂点には文字列が格納される
ツリーから、元のソースコードに戻せるように、空白文字の頂点も作る

ツリーの頂点に ID を付ける
 ID
の付けかた
直前のバージョンと頂点の対応を計算して、
対応すると判断された頂点同士には同じ ID を付ける
頂点の対応については後述

変数を利用している部分から、定義している部分へリンクを張る
Block
{
int i;
i;
}
空白
int
空白
Declare
空白
i
Statement
空白
variable
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
ステップ2. ツリーの差分計算
頂点に ID の付けられたツリーの差分を計算する
 編集操作
 頂点の追加:
insert(新ID, 文字列, 親ID, index)
 葉頂点の削除: delete(ID)
 頂点に格納された文字列を更新: update(ID, 新文字列)
 部分木を移動: move(ID, 移動先の親ID, index)

編集スクリプト
 編集操作の列
 ツリーの変換内容を表現する
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
差分を表すスクリプト
ツリー A とツリー B の差分を、 A を B に変換する編集スクリプトで
表現する
条件を満たす編集スクリプトは無数に存在する
条件を満たすスクリプトの中から、無駄の無いものを探す
 編集操作にコストを定義する
 編集スクリプトのコストを、含まれる編集操作のコストの総和とする
 コストの小さい編集スクリプトが良いスクリプト
既存のアルゴリズム FMES に、リネーム解析を加えたものを採用
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
差分計算アルゴリズム

差分を求める近似アルゴリズム
 編集操作のコスト
 insert のコスト = delete のコスト = moveのコスト =1
 update のコストは変更前後の値によって 0 から 2 の値
(1 – 文字列の共通部分の長さ*2/書換え前後の文字列の長さの和)*2

2段階の処理
 頂点の対応計算
 葉頂点を、テキストの類似度により対応計算
 識別子以外の内部頂点を、葉頂点の対応率を用いて対応計算
 識別子頂点を、テキストの完全一致か、親頂点の類似度により対応計算
 対応計算されたツリーで、編集スクリプトを求める
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
差分計算アルゴリズムの適用例
0
1
Block
doA
2
x
3
doB
4
delete(4)
delete(3)
insert(5, if, 0, 2)
insert(6, then, 5, 1)
move(1,6)
y
0
0?
Block
5? if
6?
then
1?
doA
Block
2?
1
doA
2
x
3
5
doB
4
y
if
6
then
1
doA
2
x
x
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
ステップ3. マージ
ツリー A とツリー B の差分S を、A でないツリー C に
適用すること
問題: 編集操作は頂点 ID を引数に取るが、
A と C で同じ ID の頂点があるとは限らない
同じ ID を持つ頂点が無いときは、類似した頂点を探す
親や兄弟が共通
ラベルが同じ
よく似た頂点が見つかれば、代用してみる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
マージの適用例
0
A
0
if
1
1
then
4
else
2
doA
5
doB
3
6
x
C
1
2
0
if
then
4
doA
8
3
x
y
else
doC
9
z
update(6, i)
move(5, 1, 21)
doA
delete(4)
3
代用できる
頂点はない
0
if
B
4
then
8
1
z5
if
then
4
else
then2 doA
8
doC
else
doC
9
x
0
doB
2
6
1
if
3
x
doA
9
z
3
i
x
類似度の低い頂点がある
代用する場合と、操作をしない場合の木を作る
update(6, i)
move(5, 1, 1)
move(8,
delete(4)
D1
0
1
8
D2
if
then
doC
2
doA
0
if
D3
0
if
1
then
1
then
4
else
2
doA
2
doA
8
doC
9z
3x
3x
3x
前の操作を適用しなかった場合、子頂点がある
適用しない場合と子ごと削除する場合の木を作る
開発者が一つを選択
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
z
18
目次
版管理システム
 ソースコードをマージする際の問題
 研究の目的
 ツリーのマージ

 ステップ1.
ソースコードをツリーに変換
 ステップ2. ツリーの差分計算
 ステップ3. マージ
システムの実装
 実験
 今後の研究について

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
システムの実装
既存の版管理システム subversion を拡張
subversion の特徴
 サーバ・クライアント型システム
 クライアント側での差分計算・マージ処理


対象とするプログラミング言語: Java
ソースコードをツリーに変換した状態でリポジトリに格納
 ツリー表現には、独自スキーマの
XML を使う
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
システムの概要
subversion
クライアント
開
発
者
差分計算
subversion
サーバ
差分適用
XMLのマージ機能
リポジトリ
ソースコードとXMLの変換
頂点対応の計算
ソースコードと
XMLの相互変換
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
取得と格納
subversion
クライアント
subversion
サーバ
リポジトリ
取得時の処理
格納時の処理
開
発
者
差分計算
差分適用
取得した
XMLファイル
ソースコード
頂点 ID 付き
XMLファイル
編集
頂点対応の計算
頂点ID無し
XMLファイル
ソースコードと
XMLの相互変換
編集した
ソースコード
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
マージ
マージ時の処理
最新版の
XMLファイル
subversion
クライアント
差分計算
subversion
サーバ
リポジトリ
差分
差分適用
取得した
XMLファイル
頂点 ID 付き
XMLファイル
開
発
者
マージ結果の
マージ結果
マージ結果
ソースコード
マージ結果
のXML
のXML
(整列済)
のXML
マージ結果の
マージ結果
マージ結果
マージ結果
XML(整列済)
のXML
のXML
のXML
開発者に提示
頂点対応の計算
頂点ID無し
XMLファイル
ソースコードと
XMLの相互変換
編集した
ソースコード
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
目次
版管理システム
 ソースコードをマージする際の問題
 研究の目的
 ツリーのマージ

 ステップ1.
ソースコードをツリーに変換
 ステップ2. ツリーの差分計算
 ステップ3. マージ
システムの実装
 実験
 今後の研究について

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
評価実験1
作成したシステムが、期待通り動作するかを確認するため、
実験を行なった
 サンプルのソースコードを作成 (オリジナル)
 オリジナルを編集して、ソースコードを 3つ作成
ソースコード1: 変数 avg を削除
ソースコード2: 変数 avg を使うメソッドを追加
ソースコード3：変数 avg を average に改名
オリジナルから、ソースコード1～3への変更を、
差分1～3として作成
 それぞれのソースコードに、差分を適用する

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25
評価実験1の結果
提案手法
行単位のマージ
差分1
ソース
コード1
ソース
コード2
不正な
出力
ソース
コード3
衝突
差分2
差分3
不正な
出力
衝突
ソース
コード1
不正な
出力
ソース
コード2
衝突を
検知
ソース
コード3
成功
不正な
出力
差分1
差分2
差分3
失敗
(大量の
候補)
成功
成功
成功
•提案手法では、 6 件中 5 件で正しい結果を返すことができた
•1 件では、代替位置の探索に失敗し、大量の候補を出力してしまった
→ 代替位置探索の精度向上が必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
26
評価実験2
作成したシステムが、実際の開発で役立つかを確認する
ため、実験を行なった
 オープンソースソフトウェアの開発履歴から、マージが行われ
たと思われる個所を抽出
用いたリポジトリ
Jakarta プロジェクト (22,606ファイル 162,683リビジョン)
Eclipse プロジェクト (19,420ファイル 103,358リビジョン)
短時間に、別の開発者によって Java ソースファイルの格納が
行われた84件

行単位のマージと比較する
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
27
評価実験2の結果
行単位のマージ
件数
ツリーのマージ
件数
成功
71
成功
71
失敗
13
成功
9
失敗
4


行単位で成功している時は、ツリーでも成功している
行単位で失敗した 13 件中 9 件で正しいマージ結果を出力できた
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
28
評価実験2の結果(行単位で失敗したとき)
行単位で失敗した原因
件数
ツリーの
マージ
件数
空白文字の追加削除
4 成功
4
意味的な変更と整形
1 成功
1
改行コードの変更
1 成功
1
部分的に重なりあった編集
2 成功
2 1件で大量の候補
後の変更が上書き
(意味的な衝突はなし)
2 成功
1
意味的な衝突
2 失敗
2
編集に失敗したファイルの格納
1 失敗
1 ツリーを作れない
失敗
1 大量の候補
失敗した 4 件のうち、 3 件は本質的な衝突
1 件で代替頂点・位置の探索に失敗して、マージに失敗していた
成功したうちの 1 件でも大量の候補が出てしまった
→ 代替位置・頂点探索の精度向上が必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
29
まとめと今後の課題

まとめ
 既存の版管理システムの問題点
 解決法としてソースコードの構造化マージを提案
 システムの実装について説明
 評価

今後の課題
 マッチング計算の精度と、マージの効率を改善
 マージ結果の候補選択インタフェースを改善
→ 差分の強調表示
 異なるファイル間でのリンク
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
30
目次

背景
 版管理システム
 ソースコードをマージする際の問題
研究の目的
 ツリーのマージ

 ステップ1.
ソースコードをツリーに変換
 ステップ2. ツリーの差分計算
 ステップ3. マージ
実験
 今後の研究について

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
31
オープンソースソフトウェア開発の問題点

ツール間の連携は一方向で不足
例: 版管理システムのログをメーリングリストに流す
版管理システムへの格納時に、バグ管理システムの情報を
変更

既存の開発支援ツールは、地理的に近くで開発しているこ
とや、密な連携を前提としている
→ そのままではオープンソース開発には適用できない
オープンソース開発に向いた支援ツールが必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
32
オープンソースソフトウェア開発支援ツール


1.
2.
設計もまた、ソースコードの編集と同様に、複数人の共同作業により
行われる
設計文書も構造を考慮したマージを行いたい
細粒度版管理システムを設計文書へ対応させる
ソースコードのツリーと、設計文書のツリーの間で、相互に
リンクを張る
→ リンク情報を利用して、設計書の参照を容易にする
3.
バグ管理システムに、原因となったソースコードの部分に対応する、ツ
リーの頂点 ID の情報を加える
→ リポジトリ内で、同じ修正が必要な個所を絞りこむ
知識の共有をはかることで、開発をサポート出来る
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
33

Download Report