日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

プログラム編集履歴を用いた
版管理システムでの競合解決支援
西村 雄一

丸山 勝久

ソフトウェア開発において，版管理システムのマージ機能を利用することで並行開発が容易になる．しかしながら，
2 つのブランチを統合する際の競合は避けられない．手動による競合の解決では，それぞれのブランチにおいて実施されたすべての編集を把握する必要があり，その手間は大きい．本論文では，それぞれのブランチに存在するプログ
ラムの編集履歴を用いることで競合を検出し，競合に関係のある編集操作だけを抽出する手法を提案する．

い．このような競合を解決するためには，後から統合

1 はじめにを試みた開発者が競合しているコード断片を修正す

効率的なソフトウェア開発や保守を実現するため，
Subversion†1 や Git†2 といった分散型の版管理シスる必要がある．残念ながら，現在の版管理システムをテムを用いることが一般的になりつつある．これらのコード断片と関係しないコード断片を特定する必要

版管理システムはソースコードのブランチを作成しがある．さらに，それぞれのソースコード改変においたり，それらをマージしたりする機能を備えている．

て実施された編集を理解した上で，ソースコードをこれらの機能を用いることで，最新版やリリース版の修正する必要がある．一般的に，このような修正作業

ソースコードに影響を及ぼすことなくそれぞれの開発は面倒であり，時間がかかる．また，修正対象のソー者が独自にソースコードを改変することができる．さスコードに対する理解が不十分なまま修正を行うと，らには，独自に改変したソースコードの差分をもとの予期せぬ動作の発生やバグの混入につながる．

利用している限りにおいて，開発者が競合に関係する版に統合（反映）することも可能である．このように

本論文では，開発者がどのようにプログラムを変して，複数の開発者による分散開発を支援している．

更してきたを保存するプログラム編集履歴を用いて，

しかしながら，このような分散開発が常にうまくいソースコードの統合における競合の解決を支援する

くとは限らない．ある開発者が改変したコード断片手法を提案する．本手法では，統合対象のブランチにが，別の開発者が改変したコード断片と重なっていた

おいて，それぞれ編集されたソースコードの編集操作

場合，それらのコード断片は競合状態となる．このよが存在することを前提とする．また，編集が行われた

うなコード断片は互いに干渉するため，版管理システ

ソースコードに現れるメソッドやフィールドと編集操

ムのマージ機能により単純に統合することはできな

作の関係を表現した編集操作グラフ (edit operation

Supporting Conflict Resolution in Version Control
Systems by Using Edit Operation History
Yuichi Nishimura, 立命館大学大学院情報理工学研究科, Graduate School of Informamtion Science andEngineering, Ritsumeikan University.
Katsuhisa Maruyama, 立命館大学情報理工学部, Department of Computer Science, Ritsumeikan University.
†1 http://subversion.apache.org/†2 http://git-scm.com/

graph) [4] を利用する．さらに，編集操作グラフに基
づき，特定のプログラム要素の構築に関係のある編
集操作だけを抽出する編集履歴スライス (operation

history slice) [4] を利用することで競合を検出する．
最終的に，競合に関係のあるメソッドおよびフィール
ドに関係する編集操作だけを抽出し，それらの編集を再演することで競合の解決を支援する．競合に関係ある一部の編集操作だけを再演するだけでよいので，開発者の手間の削減が期待できる．

public class Book {private String title;
private String authors;
private int price;

2 プログラム編集履歴を用いた競合解決

public Book(String t, String a, int p) {title = t;authors = a;price = p;}

ここでは，まず 2 つのブランチを統合する際に発生する競合の例を示す．次に，競合の解決を支援するために，競合に関係のあるメソッドおよびフィールド

public String getTitle() {return title;}と，競合に関係する編集操作を特定する手法を提案する．

public String getAuthors() {return authors;}

2. 1 競合の例
いま，Git を用いた共有リポジトリをブランチ名

public int getPrice() {return price;}

master で管理する開発者 M がいる．このリポジトリには，図 1 に示す Book クラスを含むファイル Book.java}のソースコード（M0 と呼ぶ）が格納されている．

図1

ブランチ master の Book クラス (M0 )このような状況において，別の開発者 B が名前

branch を持つ新たなブランチを共有リポジトリに作成し，M0 をチェックアウトすることで得られたソー
スコード B0 の Book に対して，次に示す手順で編集

public class Book {private String title;
private String authors;
private int price;を行った．

public Book(String t, String a, int p) {title = t;authors = a;price = p;}(b1) メソッド getPrice() のコピーを作成(b2) 2 つの getPrice() のうちのひとつの名前をgetPriceValue() に変更

public String getTitle() {return title;}(b3) メソッド getPrice() の返り値の型を int から String に変更

public String getAuthors() {return authors;}(b4) price の値の末尾に通貨単位 “-yen” を付与したものを返すように getPrice() の本体を書
き換え

public String getPrice() {return String.valueOf(price) + "-yen";}

修正後のソースコード（B4 と呼ぶ）を図 2 に示す．
開発者 B の作業と同時に開発者 M も開発を継続しpublic int getPriceValue() {return price;}ており，ソースコード M0 の Book に対して，次に示す手順で編集を行った．

(m1) Book のフィールド変数 price の型を int か}
図2

ブランチ branch の Book クラス (B4 )ら String に変更(m2) price の値として，価格の末尾にその通貨単位 “-yen” を付与したものを格納するようにコンストラクタ Book(...) の本体を書き換え(m3) メソッド getPrice() の返り値の型を int から String に変更(m4) getAuthors() の戻り値の型を String からString[] に変更(m5) コンマで区切られた String 型の著者リスト
を分割し，それぞれの著者を String の配列で返すように getAuthors() の本体を書き換え
修正後のソースコード（M5 と呼ぶ）を図 3 に示す．
このような並行開発において，まず開発者 M がpublic class Book {private String title;
private String authors;
private String price;
public Book(String t, String a, int p) {title = t;authors = a;price = String.valueOf(p) + "-yen";}public String getTitle() {return title;}
public String[] getAuthors() {return authors.split(",");}
public String getPrice() {return price;}

図4

ブランチ master と branch の編集操作

ソースコードがコンパイルエラーを発生させたり，予期せぬ動作を行う可能性がある．
この例では，getPriceValue() の戻り値の型が一致しない．また，getPrice() により返される文字列において，通貨単位が重複する．
もし，getPrice() の本体を上記のように修正した}
図3

ブランチ master の Book クラス (M5 )いのであれば，同時に変更 (m1)(m2) を取り消すよ
うにソースコードを書き換えるのが望ましい．つまM5 を master にコミットした．その後，開発者 B がり，2 つのブランチを統合する際には，競合している

B4 を branch にコミットし，branch に行った編集を

コード断片だけを修正すればよいわけではなく，それ

master に統合しようと試みた場合を考える．この場

ぞれのブランチで適用されたすべての編集を把握し合，競合が発生し，統合に失敗する．

た上で，競合を解決する必要がある．

2. 2 手動による競合の解決

2. 3 支援手法

手動での統合を実施するために，ブランチ master

本論文では，開発者がどのようにプログラムを変更に適用された編集を B4 にマージすると，次に示すよ

してきたのかを表現したプログラム編集履歴を用いうな競合が報告される（ブランチ branch の B4 が以て，ソースコードの統合における競合の解決を支援す

下のような記述を含む）．

る手法を提案する．本手法では，統合対象の 2 つのpublic String getPrice() {<<<<<<< HEAD
return String.valueOf(price) + "-yen";=======
return price;>>>>>>> refs/remotes/origin/master}ブランチにおいて，それぞれ編集されたソースコードの編集操作が存在することを前提とする．編集操作の取得には，筆者らが開発した Eclipse†3 プラグインのChangeTracker†4 を活用する．2. 1 節の例における編集操作を図 4 に示す．
ここで，ChangeTracker は，ファイルごとの編集

上記の報告により，getPrice() に対する編集が操作を時間順に再演（再生）する機能を備えている．

被っていることが分かる．しかしながら，上記の報告

よって，それぞれのブランチに存在するソースコード

だけを見て，単純に競合箇所を修正するのは危険でを統合する場合は，それらの編集操作をそれぞれ再演ある．たとえば，getPrice() の本体を，以下に示すすることで，編集の把握が容易になる．ただし，この

コード断片

return String.valueOf(price) + "-yen";のように単純に修正してしまうと，コミットされた†3 http://www.eclipse.org/†4 Fluorite [6] と同様に Eclipse の Java エディタ上で実施されたテキスト編集イベントを捕獲し，OperationRecorder [5] と同様の XML 形式で編集履歴を出
力する．

図5

ブランチ master と branch のソースコードに対する編集操作グラフ（一部のみ）

ツールは単一のファイルに対する編集操作を単純に再象のブランチ branch が作成された時刻と統合を演できるだけであり，競合の検出や競合の解決を十分試みた時刻から，その間に適用されたすべての編に支援しているとはいえない．

集操作を集めることができる．図 4 の例では，編そこで，ChangeTracker を拡張し，競合解決に関係

集操作 2 ∼ 9 と編集操作 11 ∼ 18 が抽出される．

のある編集操作だけを抽出し，それらを再演するこ(Step 2) ブランチ b に含まれるファイル f ごとに，とで，競合解決の手間の削減を目指す．そのために，編集操作グラフ G(b, f ) を作成する．図 4 の編集

それぞれのブランチに対応するプログラム編集履歴操作に対応する編集操作グラフを図 5 に示す．

から編集操作グラフを構築する．このグラフは，各編(Step 3) ブランチ b のファイル f に関して，統合

集操作と各プログラム要素（メソッドおよびフィール

するソースコード s を解析し，そのソースコードド）を節点として持つ．また，それぞれの編集操作

内部で定義されているプログラム要素を抽出すは，それが編集しているプログラム要素に矢印で接続

る．抽出したプログラム要素をそれぞれ P (b, s)

されている．さらに，本手法では，編集操作グラフにと表す．2. 1 節の例では，次のようになる．

基づき，特定のプログラム要素の編集（記述）に関係

P (master, M5 )のある編集操作だけを抽出する編集履歴スライスを= { title#Book, author#Book,

利用する．
以下に，競合に関係する編集操作を求める手順を示す．

(Step 1) プログラム編集履歴全体から，ブランチ
作成時点から統合時点までの編集操作を抽出す
る．編集操作は時間順に並んでいるため，統合対

price#Book, Book#Book,
getTitle#Book, getAuthors#Book,
getPrice#Book }P (branch, B4 )= { title#Book, author#Book,
price#Book, Book#Book,

getTitle#Book, getAuthors#Book,

間順に並べたものとなる．本手法では，この編集

getPrice#Book, getPriceValue#Book }操作の列を再演の対象とする．2. 1 節の例では，

ただし，E#C はクラス C のプログラム要素 E を

master の M5 （Book.java）に対しては編集操作指す．

の列 [ 6 ]，branch の B4 （Book.java）に対して(Step 4) プログラム要素 p ∈ P (b, s) を一つずつ選
択し，G(b, f ) に基づき編集履歴スライス S(b, p)

は編集操作の列 [ 14, 15, 16, 17, 18 ] が再演対象として特定される．

を作成する．2. 1 節の例では，ブランチ masterと branch から，それぞれ 7 個および 8 個のスラ

3 関連研究イスを作成する．

競合が発生したことを知らせるものとして Syde [3]S(master, title#Book) = ∅や WeCode [2] がある．これらは協調開発におけるアS(master, authors#Book) = ∅ウェアネス [1] の改善を目指している．

S(master, price#Book) = { 2 }Syde はクライアントサーバーアプリケーションでS(master, Book#Book) = { 3, 4, 5 }あり，クライアントである Eclipse プラグインを通じS(master, getTitle#Book) = ∅てプログラムの変更履歴をサーバーに送信する．送S(master, getAuthors#Book) = { 7, 8, 9 }信された変更履歴は，Abstract Syntax Tree (AST)

S(master, getPrice#Book) = { 6 }のノード単位 (構文要素) での変更情報が含まれておS(branch, title#Book) = ∅り，サーバー側はそれらの保存および変更された部分

S(branch, authors#Book) = ∅の情報・衝突の有無をクライアントにブロードキャス

S(branch, price#Book) = ∅トする．

S(branch, Book#Book) = ∅WeCode は，版管理システムの一つである Subver-

S(branch, getTitle#Book) = ∅sion をサポートしており，複数の開発者・開発チーム

S(branch, getAuthors#Book) = ∅での開発を想定している．開発者がプログラミングをS(branch, getPrice#Book)行っている最中に，バックグラウンドでそのプログラ= {14, 15, 16, 17, 18}

ムをサーバーへ送信しサーバー側で最新のコミットとS(branch, getPriceValue#Book)= {11, 12, 13}(Step 5) 統合する 2 つのブランチを b1 および b2

比較する．この時，開発者に代わって競合となりうる部分を発見することで，開発者がコミットやマージを行う前に競合の有無を伝えることを可能にしている．

とする．また，それぞれのソースコードを s1 お

本手法の目的は，Syde や WeCode のように競合がよび s2 とする．プログラム要素 p1 ∈ P (b1 , s1 )発生したことを素早く知らせることではなく，競合を

および p2 ∈ P (b2 , s2 ) に対して，ラベル（本手法

手動で解決する際に必須である編集に関する情報をではメソッドの名前あるいはフィールドの名前）提供することである．

が一致する 2 つのスライス S(b1 , p1 ) と S(b2 , p2 )を取り出す．本手法では，これら 2 つのスライス

4 おわりにがともに空集合でないとき，b1 の p1 と b2 の p2

本論文では，版管理システムのひとつである Git にが競合すると見なす．2. 1 節の例では，master のおいて発生する競合の解決を，細粒度のプログラム編

getPrice#Book) と branch の getPrice#Book が集履歴を用いて支援する手法を述べた．現在，2. 3 節

競合と判定される．

に示した手順を ChangeTracker に組み込んでいる途(Step 6) ブランチ b のプログラム要素 p が競合し中である．

ている場合，競合に関係のある編集操作の列は編

今後の課題として，実装を完成させ，評価実験に取集履歴スライス S(b, p) に含まれる編集操作を時り組む予定である．同時に，手法の改良も検討する．

本手法では，ファイル，クラス，メソッド，フィール

参 考 文 献ドの名前変更を追跡しておらず，名前変更を含んだ[1] Dourish, P. and Bellotti, V.: Awareness and Coordination in Shared Workspaces, Proc. CSCW’92,
1992, pp. 107–114.
[2] Guimarães, M. L. and Silva, A. R.: Improving
Early Detection of Software Merge Conflicts, Proc.
ICSE’12, 2012, pp. 342–352.
[3] Hattori, L. and Lanza, M.: Syde: A Tool for Collaborative Software Development, Proc. ICSE’10,
2010, pp. 235–238.
[4] Maruyama, K., Kitsu, E., Omori, T., andHayashi, S.: Slicing and Replaying Code Change
History, Proc. ASE’12, 2012, pp. 246–249.
[5] Omori, T. and Maruyama, K.: A Change-Aware
Development Environment by Recording Editing
Operations of Source Code, Proc. MSR’08, 2008,
pp. 31–34.
[6] Yoon, Y. and Myers, B. A.: Capturing and Analyzing Low-level Events from the Code Editor, Proc.
PLATEAU’11, 2011, pp. 25–30.

ソースコードを統合する場合には，競合に関係ある編
集操作が正しく抽出されない可能性が高い．従って，名前変更の追跡は必須である．また，本手法では，メ
ソッドおよびフィールドを競合の単位と見なしている．実際には，メソッドの一部の編集が被った場合でも，競合を引き起こさない場合がある．このような状況に対応するために，編集操作に記録された編集範囲（ソースコード上のオフセットで管理されている）を活用することを考えている．
謝辞 本研究に関してご討論頂きました，立命館大
学の紙名哲生氏に感謝いたします．本研究の一部は，科研費（24500050, 15H02685）の助成を受けたものである．