プログラミングをしていると、似たような、少しだけ違う処理を何度か書かなければならないことがあります。うまく関数などの単位にまとめられれば良いのですが、ループ構造などをうまくまとめられない場合もありますし、開発の担当者が異なるために編集できないという場合もあります。そんなときは、１つ記述した処理の内容をコピー＆ペーストで複製し、それぞれの場所に合わせて編集するという形でプログラムを書くことになります。
このような処理のコピーが、１つのバグを、複数の場所にばらまいてしまうこともあります。以下は、ある実際の企業システムにおける C# のバグ修正の例から、システム固有の変数名などをつぶしたものです。
for (var i=0; i < row.Cells.Count; i++) {
if (row.Cells[i].Value == null) {
- break;
+ continue;
}
ret.Add((string)row.Cells[i].Value);
}
この修正では、マイナスのついている行の break 文が、プラスで示された continue 文に置き換えられました。この処理では、表のセルに格納された値が null の場所を飛ばしてデータを取り出していくことが必要だったのですが、開発者が書いたコードは、最初の null を見つけた時点でループを打ち切ってしまっていました。
このようなバグが発見されたとき、開発者は、他に同じ誤りのあるコードはないかを検査し、まとめて修正を行うことが求められます。しかし、コード片の個々の単語だけで見ると、プログラムのあちこちに出現するものばかりです。grep のようなキーワード検索ツールだけでは、システム全体から、注目すべきポイントだけに絞り込むことは簡単ではありません。
そこで、コード片を入力として、ソースコードを検索するツールを開発しました。
github.com
ツールはコード片と検索対象ディレクトリ名を受け取り、ソースコード内から類似した内容のソースコードが出現する場所をすべて探し、報告します。この検索基準として、私たちは「正規圧縮距離（Normalized Compression Distance）」を採用しています。これはデータ圧縮アルゴリズムの特性を使用した技術の１つで、「テキスト X の内容をデータ圧縮した結果と、テキスト X の内容を２つ繰り返し並べたものをデータ圧縮した結果のデータの大きさが、ほとんど変わらない」という性質を活用したものです。上記のコード例を検索する場合、以下のようなテキストが入力となります。
for (var i=0; i < row.Cells.Count; i++) {
if (row.Cells[i].Value == null) {
break;
}
ret.Add((string)row.Cells[i].Value);
}
この内容を持ったテキストファイルを Windows 10 の「送る - 圧縮 (zip形式) フォルダー」 機能で圧縮すると、空白や改行込みで159バイトのデータが108バイトに圧縮されます。これを二度繰り返した以下のようなテキストを用意して圧縮すると、実際のデータ量は約2倍になったにも関わらず、圧縮結果は111バイトに収まります。
for (var i=0; i < row.Cells.Count; i++) {
if (row.Cells[i].Value == null) {
break;
}
ret.Add((string)row.Cells[i].Value);
}
for (var i=0; i < row.Cells.Count; i++) {
if (row.Cells[i].Value == null) {
break;
}
ret.Add((string)row.Cells[i].Value);
}
気になる方は、実際に手元の環境で試してみてください。zip 圧縮ではファイル名などの情報が一定量入るので、Windows の Explorer から見えるファイルサイズでは 220バイト前後になるかと思いますが、内容が２倍に増えても圧縮結果のファイルの大きさがほとんど変わらないことを確認できると思います。２回目のテキストの内容を書き換えて、情報の繰り返しを減らすと、圧縮結果のファイルが大きくなります。
この性質を使うと、入力として与えられたコード片と、ソースコードから適当に切り出してきたコード片をつないで圧縮をかけ、その大きさを確認することで、似ているソースコードの範囲を抽出することができます。上記のバグの事例では、システム全体から9個のコード片を報告し、うち2件が入力となったコード片とそのコピー（修正が必要な場所）、2件が同じ処理を既に正しく実装していた場所、残る5件は類似したループ構造だが今回のバグには無関係な場所となっていました。この検索方法は、かなり重たい計算のようにも見えますが、zip 圧縮のようなアルゴリズムは大容量のデータを高速に処理することに適しており、開発に使っているワークステーション上では Linux の600万行程度のソースコードを 20分で検索できるなど、実用性も意外と高いものとなっています（詳しくは論文PDFをご覧ください）。研究としては、「企業の開発者が日常的に使えるツール」を目指して、さらに高速な検索のための工夫に取り組んでいます。
なお、このような「類似したソースコード」を見つける技術については、コードクローン検出と呼ばれ、ソフトウェア工学でも息の長い研究分野の１つです。ソフトウェア工学研究室では、コードクローンの有無や量もソフトウェア品質の一指標として考えています。
門田 暁人, 佐藤 慎一, 神谷 年洋, 松本 健一: コードクローンに基づくレガシーソフトウェア品質の分析, 情報処理学会論文誌, vol.44, no.8, 2003. (論文PDF)
上記論文では、コードクローンを含むソースコードのほうが（おそらくは既にテストされたようなコードを流用しているために）バグが少ない、しかしあまりに多くのコードクローンを持つソフトウェアは品質が低いなど、いくつかの性質を報告しています。コピー＆ペーストは非常に強力なツールの１つですが、活用しつつも度を超さないようにするというのも、開発者にとってはセンスの問われるところです。
