dodona-edu/dolos を使って類似コードを検出する

はじめに

こんにちは、 @okarin です。私たちはコーディング試験のプロダクトを開発しており、先日、類似コードを検出する機能をリリースしました。類似コードを検出する仕組みは技術的にも難しく、どうやって実現しているのだろうかと疑問に思う方も多くいらっしゃると思います。今回は dodona-edu/dolos （以下 dolos と表記）を使って、類似コードを検出する方法を解説していきたいと思います。

dolos の仕組み

dolos は以下の 4 ステップで類似コードを検出することができます。ドキュメントに詳細が記載されていますので適宜参考にしてみてください。

Tokenization
Fingerprinting
Indexing
Reporting

Tokenization

Tree-sitter をつかって syntax tree を生成します。これによって、変数名を変更したり、改行やスペースを入れたりした場合でも同じコードとして扱うことができます。playground では、適当なコードを入力してどのような syntax tree が生成されるのかを確認することもできます。

Fingerprinting

tokenize して得られた token の配列から、一定の長さごとにハッシュ値を求めます。コード比較時に、このハッシュ値が同じになると、その範囲で同じコードと推測されます。

Indexing

fingerprints を計算したら、検索しやすいように fingerprint と対応するファイルやコードの位置情報などを保存します。

Reporting

ここは dolos の使い方にもよりますが、基本的には共通の fingerprint をもつコードのペアを取得します。このペアは類似度やコードが類似している箇所（フラグメント）の情報を持ちます。

dolos を使った類似コード検出のサンプルコード

サンプルコードは以下になります。このコードは GitHub にアップロードしています。

現段階では ProgrammingLanguage が export されていないので import の path がよくないですが、一旦気にしないでもらえると助かります。これは今後のリリースで export される予定となっています。

コードが長いので次節から少しずつ詳しく見ていきます。

import {
  File,
  FingerprintIndex,
  Options,
  TokenizedFile,
} from "@dodona/dolos-lib";
import { ProgrammingLanguage } from "../node_modules/@dodona/dolos-lib/dist/lib/language.js";

type Runtime = "cpp" | "python";
type Code = {
  code: string;
  path: string;
  runtime: Runtime;
};

const index = new FingerprintIndex(
  Options.defaultKgramLength,
  Options.defaultKgramsInWindow
);

// Problem Sample: https://leetcode.com/problems/fizz-buzz/
const codes: Code[] = [
  {
    // solution 1
    code: `class Solution(object):
    def fizzBuzz(self, n):
        answer = []
        for i in range(1, n + 1):
            if i % 15 == 0:
                answer.append("FizzBuzz")
            elif i % 3 == 0:
                answer.append("Fizz")
            elif i % 5 == 0:
                answer.append("Buzz")
            else:
                answer.append(str(i))
        return answer`,
    path: "/path/to/solution_1",
    runtime: "python",
  },
  {
    // solution 2
    code: `class Solution(object):
    def fizzBuzz(self, n):
        answer = []
        for i in range(1, n + 1):
            result = ""
            if i % 3 == 0:
                result += "Fizz"
            if i % 5 == 0:
                result += "Buzz"
            if result == "":
                result = str(i)
            answer.append(result)
        return answer`,
    path: "/path/to/solution_2",
    runtime: "python",
  },
  {
    // solution 3
    code: `class Solution(object):
    def fizzBuzz(self, n):

        result   = []

        for x in range(1, n+1):

            if x%15==0:
                    result.append("FizzBuzz")
            elif x%3==0:
                    result.append("Fizz")
            elif x%5==0:
                    result.append("Buzz")
            else:
                    result.append( str( x ) )
        return result`,
    path: "/path/to/solution_3",
    runtime: "python",
  },
];

const tokenizedFiles: TokenizedFile[] = [];
for (const code of codes) {
  const language = new ProgrammingLanguage(code.runtime, []);
  const tokenizer = await language.createTokenizer();

  const file = new File(code.path, code.code);
  const tokenizedFile = tokenizer.tokenizeFile(file);

  tokenizedFiles.push(tokenizedFile);
}

index.addFiles(tokenizedFiles);

// solution 1 and 2
const pair12 = index.getPair(tokenizedFiles[0], tokenizedFiles[1]);
const fragments12 = pair12.buildFragments();
console.log({
  pair: "solution_1 and solution_2",
  similarity: pair12.similarity,
  left: fragments12[0].leftSelection,
  right: fragments12[0].rightSelection,
});

// solution 1 and 3
const pair13 = index.getPair(tokenizedFiles[0], tokenizedFiles[2]);
const fragments13 = pair13.buildFragments();
console.log({
  pair: "solution_1 and solution_3",
  similarity: pair13.similarity,
  left: fragments13[0].leftSelection,
  right: fragments13[0].rightSelection,
});

FingerprintIndex

FingerprintIndex は類似コード検出のコアとなるオブジェクトです。 kgramLength はローリングハッシュを求めるときの token の部分配列の長さで、 kgramsInWindow は Winnowing アルゴリズムでハッシュの最小値を取得するときのバッファサイズになります。本記事ではパラメータの意味をあまり気にしなくても大丈夫です。ここではデフォルト値を使用します。

const index = new FingerprintIndex(
  Options.defaultKgramLength,
  Options.defaultKgramsInWindow
);

Python のコード

今回はleetcode の FizzBuzz の問題で、 Python の解答を 3 つ用意しました。 solution1 と solution2 はそれぞれ少し違う解き方をしています。 solution3 は solution1 のコードの変数名を変えたり改行を入れたり小細工をしたコードになります。

// Problem Sample: https://leetcode.com/problems/fizz-buzz/
const codes: Code[] = [
  {
    // solution 1
    code: `class Solution(object):
    def fizzBuzz(self, n):
    ...

TokenizedFile の生成

Python のコードをもとに字句解析を行い、token の配列をもつ TokenizedFile を生成しています。

const tokenizedFiles: TokenizedFile[] = [];
for (const code of codes) {
  const language = new ProgrammingLanguage(code.runtime, []);
  const tokenizer = await language.createTokenizer();

  const file = new File(code.path, code.code);
  const tokenizedFile = tokenizer.tokenizeFile(file);

  tokenizedFiles.push(tokenizedFile);
}

たとえば以下のような token 配列に変換されます。このような配列を使って、後述する Fingerprint が計算されます。

['(', 'module', '(', 'class_definition', '(', 'identifier', ')', ...

Fingerprint の計算とインデックスの更新

addFiles 関数で fingerprint の計算とインデックスの更新を行っています。

index.addFiles(tokenizedFiles);

addFiles 関数の内部ではローリングハッシュや Winnow Algorithm を利用して、SharedFingerprint を生成します。この SharedFingerprint は token の部分配列ごとに計算され、SharedFingerprint の hash が同じコードは同じ token の部分配列をもつ、すなわち token の部分配列の範囲でコードが同じであると推定されます。

具体例として、以下のコードの SharedFingerprint を考えてみます。

class Solution(object):
    def fizzBuzz(self, n):
        answer = []
        # ...

kgramLength = 23 （デフォルト値）とすると、 token の部分配列の長さは 23 になり、そのうち 1 つは以下のようになります。

['(', 'module', '(', 'classdefinition', '(', 'identifier', ')', '(', 'argumentlist', '(', 'identifier', ')', ')', '(', 'block', '(', 'function_definition', '(', 'identifier', ')', '(', 'parameters', '(']

この token 部分配列のローリングハッシュをもとめると、 7590745 となります。この値が同じになると、 token 部分配列の範囲でコードが同じであると推定されます。

類似度の比較

最後に、類似度を比較したいコードの Pair を生成します。このとき、内部では SharedFingerprint をもとに類似度やコードの類似している範囲を算出しています。

// solution 1 and 2
const pair12 = index.getPair(tokenizedFiles[0], tokenizedFiles[1]);
const fragments12 = pair12.buildFragments();
console.log({
  pair: "solution_1 and solution_2",
  similarity: pair12.similarity,
  left: fragments12[0].leftSelection,
  right: fragments12[0].rightSelection,
});

// solution 1 and 3
const pair13 = index.getPair(tokenizedFiles[0], tokenizedFiles[2]);
const fragments13 = pair13.buildFragments();
console.log({
  pair: "solution_1 and solution_3",
  similarity: pair13.similarity,
  left: fragments13[0].leftSelection,
  right: fragments13[0].rightSelection,
});

プログラムの出力結果は以下になります。 similarity がコードの類似度を表しており、 0〜1 の範囲で表現されます。solution 1 と solution 2 は類似度が 0.27 程度であるのに対して、 solution 1 と solution 3 は 1 になっています。solution 3 は solution 1 のコードの変数名を変えたり、スペースや改行を入れたりしたコードでしたが、全く同じコードとして検出できていることが分かります。

{
  pair: 'solution_1 and solution_2',
  similarity: 0.27450980392156865,
  left: Region { startRow: 0, startCol: 0, endRow: 3, endCol: 31 },
  right: Region { startRow: 0, startCol: 0, endRow: 3, endCol: 31 }
}
{
  pair: 'solution_1 and solution_3',
  similarity: 1,
  left: Region { startRow: 0, startCol: 0, endRow: 11, endCol: 36 },
  right: Region { startRow: 0, startCol: 0, endRow: 16, endCol: 43 }
}

まとめ

本記事では、 dolos を使った類似コードの検出方法についてまとめました。今回は簡単な使い方のみ説明しましたが、私たちは dolos を拡張することで、類似コードを検索できるマイクロサービスを実装しています。 dolos の仕組みをより詳しく知りたい方は、実際にコードを読んでみたり、ローリングハッシュや Winnowing アルゴリズムを調べると理解が深まると思います。

※ 本記事で使用している dolos （バージョン v2.6.0）は執筆時点（2024 年 5 月）で MIT ライセンスのもとで使用しています。