CloneLens

1. 入力選択

対象言語

通常ファイル、zip、フォルダを同時に指定できます。フォルダを指定した場合は、その配下の対象言語ファイルを再帰的に収集します。zip の対応圧縮方式は store と deflate です。

2. 検出設定

3. 状態

4. 統計情報

5. ファイル一覧・ファイル別統計

6. 検出結果

7. CloneLens の検出アルゴリズムの大まかな説明

このツールは、プログラムの意味を完全に理解しているわけではありません。 かわりに、ソースコードを細かい部品に分けて、「似た並びがどこにあるか」を探します。 文章の中から似たフレーズを探す方法に近い考え方です。

1. ソースコードを読み込む

まず、ユーザが選んだ Java や Python のファイルをブラウザの中だけで読み込みます。 zip ファイルやフォルダを指定した場合も、中にある対象言語のファイルを集めます。 ソースコードはサーバには送られません。

2. コメントや空白を取り除く

コメント、空白、改行の違いだけで別のプログラムだと判断しないように、比較にあまり重要でない部分を取り除いたり、そろえたりします。 たとえば、インデントの違いやコメントの有無は、できるだけ影響しないようにします。

3. 変数名などを一般化する

設定で「識別子の正規化」を ON にしている場合、変数名や関数名の多くを ID のような共通の記号に置き換えます。 たとえば、sum と total という名前が違っていても、処理の形が似ていれば見つけやすくなります。

4. コードをトークン列に分ける

ソースコードを、単語や記号のような小さな部品に分けます。 これをトークンと呼びます。

for (int i = 0; i < n; i++) {
    sum += a[i];
}

たとえば上のようなコードは、おおまかには次のようなトークン列として扱われます。

for ( ID = NUM ; ID < ID ; ID ++ ) { ID += ID [ ID ] ; }

5. 短いトークンの並びを作る

トークン列から、連続する一定個数のトークンのまとまりを作ります。 たとえば k-gram サイズが 7 なら、7 個ずつの並びを少しずつずらしながら作ります。 これは、長い文章から短いフレーズをたくさん切り出すようなものです。

6. fingerprint を作る

それぞれの短いトークン列を、短い数値に変換します。 これをハッシュ値と呼びます。 さらに、その中から代表的なものだけを選びます。 この代表値が、このツールでいう fingerprint です。

fingerprint は「このあたりのコードには、こういう特徴がある」という目印です。 すべての文字を直接比べるよりも、目印を使った方が速く探せます。

7. 同じ fingerprint を持つ場所を探す

もし別々のファイルに同じ fingerprint が出てきたら、その近くには似たコードがある可能性があります。 このツールは、同じ fingerprint がどのファイルのどの位置に出てきたかを記録し、似ていそうなファイルの組を探します。

8. 近い一致をまとめてクローン候補にする

1つだけ同じ fingerprint があっても、たまたま一致しただけかもしれません。 そこで、近い場所に複数の一致が集まっている場合に、それらをまとめて「クローン候補」として扱います。 一定以上の長さがあるものだけを結果に表示します。

9. 結果を見やすく表示する

見つかったクローン候補について、ファイル名、行番号、類似度、一致トークン数などを表示します。 クローン範囲は黄色で、対応するクローンとの差分がある字句だけをオレンジ色で表示します。挿入・削除のように対応する行がない場合も、その行の字句をオレンジ色で表示します。 差分表示では、短い範囲については行単位の LCS という方法で、左右の行の対応関係を推定しています。

この方法で見つけやすいもの・苦手なもの

つまり、このツールは「完全に同じ意味のプログラムを判定する道具」ではなく、 「似た形のコード片を素早く見つけるための道具」です。 検出結果は最終判断ではなく、人が確認するための候補として扱うのが適切です。