神谷年洋 ^†

^† 公立はこだて未来大学

電子情報通信学会ソフトウェアサイエンス研究会@愛媛大 2012/05/09

➤ 所属 公立はこだて未来大学

➤ Research Interests プログラム解析, コードクローン, コード検索

@tos_kamiya

➤ コードクローンとは、ソースコード中に含まれている、互いに類似したコード断片のこと

➤ 実例

/linux-3.0/drivers/staging/westbridge/astoria/api/src/cyasmisc.c 2932行-2940行

void
cy_as_destroy_storage_io_c_b_node(cy_as_storage_io_c_b_node *node)
{
      uint32_t state;
      node->type = CYAS_INVALID;
      state = cy_as_hal_disable_interrupts();
      cy_as_hal_c_b_free(node);
      cy_as_hal_enable_interrupts(state);
}

同ファイル 2868行-2877行

void
cy_as_destroy_usb_func_c_b_node(cy_as_usb_func_c_b_node *node)
{
      uint32_t state;

      node->type = CYAS_INVALID;
      state = cy_as_hal_disable_interrupts();
      cy_as_hal_c_b_free(node);
      cy_as_hal_enable_interrupts(state);
}

➤ コードクローンは典型的には、開発者のコピー＆ペーストによって作りこまれる

➤ コードクローンが含まれるコードは変更が難しい → 保守性に悪影響がある、と言われた

➤ コードクローン（重複コード）検出手法が提案されてきた

• コードクローン検出ツールを内蔵したIDEも出現(Visual Studio 11)

➤ コードクローン検出の応用も種々提案されてきた:

• リファクタリング 、 コード修正前のチェック、 コード剽窃（GPL違反）検出 、 コード検索、 コード評価

➤ 実際のプロジェクトでコードクローンと保守性の関係を調べる実験が行われた

☞ これまでの実験では、保守性に悪影響がある vs 影響はない、の両論あり

コードクローンと保守性への影響の議論はなぜ紛糾するのか？

→ 「コードクローン」と呼んでいるものに質的な差異があるのでは？

→ 「コードクローンは保守性に悪影響があるか」から「どんなコードクローンが悪いクローンか」へ

• 保守性に悪影響を与えるコードクローンを 悪い クローン、影響を与えない（あるいは良い影響を与える）コードクローンを 良い クローンとして

コードクローンの分類法

• 出現位置: モジュール内・モジュール間(門田)、クラス階層との関係(吉田)
• 生成理由: コピー＆ペースト・コード生成ツール・イディオム・などなど

本研究では、もう少し開発者の意図にそった分類をしたい

本研究では、もう少し開発者の意図にそった分類をしたい

→ コード断片の使われ方に注目する

使われ方が類似したコード断片 → 文脈クローン と呼ぼう

対比のため、従来のコードクローン、すなわち、処理内容が類似したコード断片 → 内容クローン と呼ぶ

➤ 内容クローン、文脈クローンをコールグラフ上で定義する

• ふたつの関数が内容クローン
  ＝ それら が 呼び出している関数の集合が類似

  fを呼び出している関数の集合
  = { a, b }
  = gを呼び出している関数の集合

• ふたつの関数が文脈クローン
  ＝ それら を 呼び出している関数の集合が類似

  gが呼び出している関数の集合
  = { x, y }
  = hが呼び出している関数の集合

➤ 前述の2つの関数、

• cy_as_destroy_storage_io_c_b_node と
• cy_as_destroy_usb_func_c_b_node

について調べてみると、

つまり、内容クローンでもあり、かつ、文脈クローンでもある3つの関数（のうちの2つだった）

➤ 研究課題(Research Questions)

• RQ1 どのような種類の文脈クローンが悪いクローンなのか?
• RQ2 どのような開発者の作業がそれら悪いクローンを作る結果となるか?
• RQ3 実際のソースコードにおいて、文脈クローンと内容クローンは異なるか?
• RQ4 文脈クローン検出手法は内容クローン検出手法を改善するのに使えるか?
• RQ5 文脈クローンと内容クローンの両方を用いてどのような新しい分析手法が可能になるか?

➤ 上記のうち、RQ3とRQ4について予備的な実験を行った

予備的 ⇒ 実験対象は1ケース（Linux kernel 3.0）のみ

➤ 検出手法

• ソースコードから静的解析によりコールグラフを抽出し(ステップ1, 2)、
• ファンインやファンアウトが類似している頂点の集合を特定する(ステップ3, 4)

➤ LDA(Latent Dirichlet Allocation)アルゴリズム

• 自然言語処理で、記事を分類するのに利用される。記事を単語の集合で表現し、類似した単語の集合を持つ記事は同じ分類（同じトピックに属する）とする。
• 完全な一致ではなく、類似（一部異なるもの）も検出できる

➤ ただし、コードクローン（内容クローン）検出ツールとしては、あまり性能はよくない ☹

コードクローン検出ツールは、構文やデータフローを比較するものが主流

➤ 対象となったソースコード

• Linux kernel 3.0のソースファイル(.hと.c）

➤ 検出されたクローン

クラス = 内容クローン（あるいは文脈クローン）である関数の集合のこと

クラス数が700なのは、クラス数をLDAアルゴリズムのパラメータとして与えるため

文脈クローンであるコード断片が内容クローンになっている例ばかりなら、文脈クローンを検出する意味がなくなってしまう

前述の実例のように

→ 実際のソースコードから両クローンを検出して、どの程度重なっているか調べる

1. 対象となるソースコードから文脈クローンと内容クローンを検出
2. 文脈クローンにも内容クローンにも属している関数以外を除去
3. それぞれの文脈クローンについて、それぞれの内容クローンと共通部分集合を作り、

（右の図では、文脈クローン X ₁ = { f, g, h, i } を被覆する内容クローンは N ₁ = { f, g, h } および N ₂ = { i, j, k }）

Σ _i ( | N _i ∩ X _j | / | X _j | ) を重なりとする

Linux kernel 3.0のソースコードから検出した文脈クローンと内容クローンの重なりを計算した

➤ 文脈クローンと内容クローンの重なり

内容ローンクラスは平均 33.9%が文脈クローンクラスによって被覆されていた

文脈クローンクラスは平均 10.4%が内容クローンクラスによって被覆されていた

☞ このケースでは、文脈クローンと内容クローンは大きく違うことがわかった

	プラン#1: (+) 関数の数が減る (-) fとgが文脈クローンだったという情報が消える それまでgを使っていたコードはghを使うように書き換えられる → ghがhの機能も含んでいるということを理解する必要が生じる
	プラン#2 (-) 関数の数が増える(p) 関数pはどこに置くのか？（gとhが違うサブシステムに属するときは特に） → APIの複雑化、凝集度が下がる可能性 (+) fとg-は文脈クローンとして残る

➤ 各プランに得失があることが、文脈クローンを考えることで比較できた

➤ Linux kernel 3.0から検出されたクローンのひとつ

➤ (c), (d), (e)はプラン#1のような修正とプラン#2のような修正の両方がも適用できそう

ただし、(a), (b)に示されるように、(e)の文脈は(c), (d)とは異なる。

☞ (e)を(c)や(d)とマージすると理解しにくくなるかも

➤ 「文脈」というアイデア:

[3] 神谷年洋, “識別子の名前の変更を追跡する手法の提案”, 電子情報通信学会 技術研究報告 vol. 108, no. 242, pp. 49-54, 2008年 10 月.

[4] T. Kamiya, “Variation Analysis of Context-Sharing Identifiers with Code Clone,” ICSM 2008, pp. 464-465, Oct., 2008.

➤ コールグラフのファンイン・ファンアウトを利用した関心事マイニング:

[9] M. Marin, A. Van Derusen, L. Moonen, “Identifying Aspects using Fan-In Analysis,” Journal ACM Transactions on Software Engineering and Methodology (TOSEM), Vol. 17 Issue 1, Dec., 2007.

[14] D. Zhang, Y. Guo, X. Chen, “Automated Aspect Recommendation through Clustering-Based Fan-in Analysis,” ASE 2008, pp. 278-287, Sept., 2008.

[10] T. T. Nguyen, H. V. Nguyen, H. A. Nguyen, T. N. Nguyen, "Aspect Recommendation for Evolving Software," ICSE 2011, pp. 361-370, May, 2011.

➤ LDA/LSAアルゴリズムを用いた関数やメソッド等の分類:

[6] S. Kawaguchi, P. K. Garg, M. Matsushita, K. Inoue, “Automatic Categorization Algorithm for Evolvable Software Archive,” IWPSE 2003, pp. 195-200, Sept., 2003.

[7] 川口真司, パンカジ ガーグ,松下誠, 井上克郎, “MUDABlue: ソフトウェアリポジトリ自動分類システム”, 電子情報通信学会論文誌 D-I, vol. J88-D-I, no. 8, pp. 1217-1225, 2005.

[12] P. S. Sandhu, J. Singh, H. Singh, “Approaches for Categorization of Reusable Software Components,” Journal of Computer Science 3 (5): 266-273, 2007.

[13] K. Tian, M. Revelle, D. Poshyvanyk, “Using Latent Dirichlet Allocation for Automatic Categorization of Software,” MSR 2009, pp. 163-166, May, 2009.

[11] T. Savage, B. Dit, M. Gethers, D. Poshyvanyk, “TopicXP: Exploring Topics in Source Code using Latent Dirichlet Allocation,” ICSM 2010, pp. 1-6, Sept. 2010.

➤ コールグラフによる類似性をorigin analysisに利用する研究:

[1] M. W. Godfrey, L. Zou, “Using Origin Analysis to Detect Merging and Splitting of Source Code Entities,” IEEE Transactions on Software Engineering, vol. 31, no. 2, pp. 166-181, Feb., 2005.

➤ コードクローン研究に関する解説記事

神谷 年洋, 肥後 芳樹, 吉田 則裕: "コードクローン検出技術の展開", コンピュータソフトウェア, Vol.28, No.3, pp.29-42, 2011年8月.

本発表では、

☑ コードクローンの良し悪しに関する背景を説明し、

☑ 文脈クローンを提案し、

☑ 文脈クローンに関するRQを示し、

☑ 従来のコードクローン（内容クローン）とは実際に異なっていることを、Linux kernel 3.0を対象とした実験で示し、

☑ 内容クローンの除去を判断する手がかりとして文脈クローンを応用した例について説明した。