https://syu-m-5151.hatenablog.com/entry/2025/10/30/203342

はじめに

コードベースが大きくなるにつれて、似たようなコードが散らばっていることに気づく瞬間がある。「あれ、これ前にも書いたような...」そう思いながらコードを眺めるのだけれど、変数名が微妙に違っていたり、処理の順序が少しずれていたりして、結局は共通化できないまま放置してしまう。そんな経験は、プログラマなら誰しも一度や二度ではないはずだ。

そして、生成AI時代の今、この問題はさらに深刻になっている。AIがコードを生成してくれるのは便利だけれど、同じような処理を少しずつ違う形で何度も生成してしまうことがある。人間が書いたコードなら「ああ、これは前に書いたやつだ」と気づけるのに、AIが生成したコードは一見して判別がつかない。気づけばコードベースは「似て非なるコード」で溢れかえり、保守性は急速に失われていく。生成AI時代だからこそ、コードの構造的な類似性を見抜く技術が、これまで以上に必要とされているのだ。

私は、結合度を測って適切にリファクタリングを促すツールを開発したいと考えていた。そのヒントを探していたときに出会ったのが、@mizchiさんのsimilarityプロジェクトだった。このプロジェクトの中でも特に、Rustへの実装であるsimilarity-rsの仕組みに惹かれ、その内部構造を詳しく調査することにした。この記事は、そこで得られた発見の記録である。

syu-m-5151.hatenablog.com

実際の使用例は以下です。

# インストール（Cargo経由）
cargo install similarity-rs

# プロジェクトルートで実行
similarity-rs .

# より詳細なオプションを確認
similarity-rs -h

# AI によって修正させる場合
Run `similarity-rs .` to detect semantic code similarities. Execute this command, analyze the duplicate code patterns, and create a refactoring plan. Check `similarity-rs -h` for detailed options.

実行すると、以下のように重複コードを検出します。

Duplicates in src/utils.rs:
────────────────────────────────────────────────────────────
src/utils.rs:10 | L10-15 similar-function: calculateSum
src/utils.rs:20 | L20-25 similar-function: addNumbers
Similarity: 85.00%, Priority: 8.5 (lines: 10)

これがどうやって実現されているのか、その内部実装を紐解いていきます。

このブログが良ければ読者になったり、nwiizoのXやGithubをフォローしてくれると嬉しいです。では、早速はじめていきます。

similarity-rsとは何か？

similarity-rs は、similarity の中の Rust プロジェクトのコード重複を検出する CLI ツールです。ただし、単純なテキストマッチングではありません。抽象構文木（AST）を使った構造的な比較により、変数名が違っても本質的に同じ処理をしている関数を見つけ出せます。

例えば、以下の 2 つの関数は変数名が違いますが、similarity-rs は「これらは似ている」と判断できます。

fn calculate_total(items: Vec<i32>) -> i32 {
    let mut sum = 0;
    for item in items {
        sum += item;
    }
    sum
}

fn add_numbers(values: Vec<i32>) -> i32 {
    let mut result = 0;
    for value in values {
        result += value;
    }
    result
}

テキストベースの diff ツールなら「全然違う」と判断する場合でも、similarity-rs は「構造が同じ」と判定できます。

技術スタックの全体像

similarity-rs の核となる技術は 2 つです。

tree-sitter - Rust コードを解析して AST を生成
APTED (All Path Tree Edit Distance) - 2 つの AST の距離を計算

この 2 つを組み合わせることで、「コードの意味的な類似度」を数値化しています。

なぜtree-sitterなのか？

tree-sitter は、GitHub が開発した高速でインクリメンタルなパーサーです。rustc の手書きパーサーと比べると初回パースは 2-3 倍遅いですが、以下の利点があります。

インクリメンタルパース: コードの一部が変更されたとき、変更部分だけ再パースできる
堅牢性: 構文エラーがあっても部分的にパースを続行できる
多言語対応: 同じインターフェースで複数の言語に対応

実測値は次のとおりです。

2157行のRustファイル（約64KB）のパース時間：
- 初回: 約6.48ms
- インクリメンタル更新: 1ms未満
- スループット: 約9908 bytes/ms

初回パースで約 6.48ms、インクリメンタル更新では 1ms 未満という実測値が得られています。

ASTベース比較の仕組み

Step 1: コードをASTに変換する

まず、Rust コードを tree-sitter でパースします。

use tree_sitter::{Parser, Language};

let mut parser = Parser::new();
parser.set_language(&tree_sitter_rust::LANGUAGE.into())
    .expect("Error loading Rust grammar");

let source_code = "fn test() { println!(\"hello\"); }";
let tree = parser.parse(source_code, None).unwrap();

生成される AST は、以下の階層構造になります。

source_file
└── function_item
    ├── fn (keyword)
    ├── identifier: "test"
    ├── parameters
    └── block
        └── macro_invocation
            └── ...

Step 2: 関数を抽出する

AST から関数定義を抽出します。この時、以下のような工夫がされています。

fn extract_functions(tree: &Tree, source: &str) -> Vec<Function> {
    let mut functions = Vec::new();
    let root = tree.root_node();
    
    fn visit_node(node: Node, source: &str, functions: &mut Vec<Function>) {
        match node.kind() {
            "function_item" => {
                // テスト関数は除外
                if !is_test_function(&node, source) {
                    functions.push(Function::from_node(node, source));
                }
            }
            "impl_item" => {
                // implブロック内のメソッドも処理
                for child in node.children() {
                    if child.kind() == "function_item" {
                        if !is_test_function(&child, source) {
                            functions.push(Function::from_node(child, source));
                        }
                    }
                }
            }
            _ => {
                // 再帰的に子ノードを探索
                for child in node.children() {
                    visit_node(child, source, functions);
                }
            }
        }
    }
    
    visit_node(root, source, &mut functions);
    functions
}

注目すべき点として、テスト関数は自動的に除外されます。以下の 3 つの方法で検出します。

#[test] 属性がついている関数
test_ で始まる関数名（Rust の慣習）
#[cfg(test)] モジュール内の関数

これにより、本番コードの重複だけに集中できます。

Step 3: 木構造の編集距離（TSED）を計算する

ここが最も興味深い部分です。2 つの AST がどれだけ「似ているか」を測定するために、Tree Edit Distance（木構造の編集距離）を使用します。

木構造の編集距離とは？

木構造を別の木構造へ変換する際に必要な「編集操作の最小回数」です。編集操作は 3 種類あります。

Insert（挿入）: ノードを追加
Delete（削除）: ノードを削除
Rename（名前変更）: ノードのラベルを変更

例を示します。

Tree 1:          Tree 2:
   A                A
  / \              / \
 B   C            B   D

編集操作：
1. C を D に Rename

編集距離 = 1

APTEDアルゴリズム

similarity-rs は、APTED (All Path Tree Edit Distance) アルゴリズムを使用しています。これは 2015-2016 年に Pawlik と Augsten が発表したアルゴリズムで、以下の特徴があります。

最適な分解戦略: 木を最も効率的に分解して計算
動的計画法: 部分問題の結果をメモ化して再利用
時間計算量: O(n·m) - 理論的に最適

実装の概要は以下のとおりです。

fn calculate_similarity(tree1: &TreeNode, tree2: &TreeNode, options: &TSEDOptions) -> f64 {
    // APTEDで編集距離を計算
    let edit_distance = compute_edit_distance(tree1, tree2);
    
    // 正規化：類似度スコア（0.0〜1.0）に変換
    let max_nodes = max(tree1.node_count(), tree2.node_count());
    let base_similarity = 1.0 - (edit_distance as f64 / max_nodes as f64);
    
    // サイズ差ペナルティを適用（オプション）
    if !options.no_size_penalty {
        let size_ratio = min_size as f64 / max_size as f64;
        base_similarity * size_ratio
    } else {
        base_similarity
    }
}

重要な発見として、ACL 2024 の研究論文（Song et al.）によると、以下の重みが最適とされています。

Insert: 0.8
Delete: 1.0
Rename: 1.0

この重みは実験によって導き出されたもので、48 以上のプログラミング言語で有効性が実証されています。

ただし、similarity-rsの現在のデフォルト実装では異なる設定が使用されています。

Rename: 0.3（デフォルト）
Delete: 1.0
Insert: 1.0

研究論文で推奨される最適値とは異なりますが、--rename-costオプションで調整可能です。

パフォーマンス最適化の技術

1. Rayonによる並列処理

similarity-rs の最大の強みの 1 つが、Rayon を使った並列処理です。

use rayon::prelude::*;

// ファイルを並列処理
files.par_iter()
    .flat_map(|file| extract_functions(file))
    .collect()

// 関数比較も並列化
functions.par_iter()
    .enumerate()
    .flat_map(|(i, func1)| {
        functions[i+1..].par_iter()
            .map(|func2| compare_functions(func1, func2))
    })
    .filter(|similarity| similarity.score > threshold)
    .collect()

Rayon の優れた特徴は次のとおりです。

ワークスティーリング: CPU コア間で自動的に負荷分散
データ競合フリー: Rust の型システムが保証（Send + Syncトレイト）
ゼロ同期オーバーヘッド: データ共有が不要な場合
線形スケーラビリティ: CPU コア数に応じてほぼ線形に高速化

実際のベンチマークでは、中規模ファイルで逐次処理比16倍の高速化が確認されています。

2. ブルームフィルタによる事前フィルタリング

TypeScript 版（similarity-ts）で先行実装され、Rust 版でも部分的にサポートされています。高速化に大きく貢献するテクニックです。

struct AstFingerprint {
    bloom_filter: BloomFilter,           // 確率的集合メンバーシップ
    node_types: HashSet<NodeKind>,
    signature: u64,                      // ハッシュベース署名
}

fn quick_reject(&self, func1: &FunctionDef, func2: &FunctionDef) -> bool {
    let intersection = self.bloom_filter
        .estimate_intersection(&func1.fingerprint, &func2.fingerprint);
    
    let estimated_similarity = intersection / max(func1.size, func2.size);
    estimated_similarity < self.min_similarity_threshold
}

この手法による効果は次のとおりです。

比較回数を 70-90%削減
偽陽性率 1%未満
TypeScript 版で約 4 倍の高速化を実現

明らかに違う関数ペアを高価な TSED 計算の前に除外できるため、全体の処理時間が 70-90%削減されます。

Rust 版での実装状況は次のとおりです。

crates/core/src/ast_fingerprint.rsにブルームフィルタの基礎実装が存在
--no-fastオプションでブルームフィルタを無効化可能
TypeScript 版ほど最適化されていないが、将来的な改善が期待される

3. メモリ最適化の工夫

Rust の所有権システムとゼロコスト抽象化を活かした最適化がいくつも施されています。

ライフタイム注釈によるゼロコピーの例を示します。

pub struct FunctionComparison<'a> {
    func1: &'a FunctionDefinition,
    func2: &'a FunctionDefinition,
    similarity: f64,
}

データをクローンせず、参照を渡すだけで済みます。

イテレータチェーンによる変換の例を示します。

let similar_pairs: Vec<_> = functions.iter()
    .enumerate()
    .flat_map(|(i, f1)| {
        functions.iter()
            .skip(i + 1)
            .filter_map(|f2| {
                let sim = calculate_similarity(f1, f2);
                (sim > threshold).then_some((f1, f2, sim))
            })
    })
    .collect();

この書き方の利点は次のとおりです。

イテレータチェーンはタイトなループにコンパイルされる
中間値のヒープアロケーションが発生しない
遅延評価により、collectされるまで計算しない

実際の使い方と出力フォーマット

基本的な使い方

# カレントディレクトリを解析
similarity-rs .

# 類似度の閾値を指定（デフォルト: 0.85）
similarity-rs . --threshold 0.9

# テスト関数をスキップ
similarity-rs . --skip-test

# ファイル間の比較も有効化
similarity-rs . --cross-file

# コードスニペットを出力に含める
similarity-rs . --print

# 最小トークン数を指定（小さい関数を除外）
similarity-rs . --min-tokens 50

出力の読み方

Duplicates in src/utils.rs:
────────────────────────────────────────────────────────────
src/utils.rs:10 | L10-15 similar-function: calculateSum
src/utils.rs:20 | L20-25 similar-function: addNumbers
Similarity: 85.00%, Priority: 8.5 (lines: 10)
────────────────────────────────────────────────────────────
src/utils.rs:30 | L30-40 similar-function: processData
src/handlers.rs:50 | L50-60 similar-function: handleRequest
Similarity: 92.00%, Priority: 11.5 (lines: 12)

Priority は次の計算式で求められます: 行数 × 類似度スコア

これにより、影響度の高い重複（長くて似ている）を優先的に見つけられます。

VSCode 互換の出力フォーマットを採用しており、ターミナルからファイル名をクリックすることで該当箇所に直接ジャンプできます。

処理フローの全体像

similarity-rs がどのように動作するのか、全体の流れを説明します。

1. ファイル検索
   └─> ディレクトリを再帰的にスキャンして.rsファイルを検索
   
2. パース段階
   └─> 各ファイルに対して:
       ├─> tree-sitterがソースをASTにパース
       └─> ASTから関数ノードを抽出
       
3. フィルタリング段階
   └─> 各関数に対して:
       ├─> 最小行数/トークン数をチェック
       ├─> テスト関数かチェック（--skip-test有効時）
       └─> 合格すれば候補プールに追加
       
4. 特徴抽出（高速モード）
   └─> ブルームフィルタ用のAST特徴を抽出
   └─> 各関数のブルームフィルタを構築
   
5. 候補ペア生成
   └─> 比較する関数ペアを生成
       ├─> 同一ファイル内ペア（デフォルト）
       └─> ファイル間ペア（--cross-file時）
       
6. ブルームフィルタ事前フィルタリング
   └─> ブルームフィルタで高速チェック
   └─> 明らかに異なるペアを除外
   
7. TSED計算
   └─> 残りのペアに対して:
       ├─> APTEDで木編集距離を計算
       ├─> サイズペナルティを適用（有効時）
       └─> 類似度スコアに正規化
       
8. 閾値フィルタリング
   └─> 類似度 >= 閾値のペアを保持
   
9. 出力生成
   └─> 結果をフォーマット（JSONまたは人間可読）
   └─> --printフラグ時はコードスニペットを含む

TypeScript版（similarity-ts）との比較

mizchi さんのプロジェクトには、TypeScript 版も存在します。各実装の特徴を比較します。

アーキテクチャの違い

側面	similarity-ts	similarity-rs
パーサー	oxc-parser（Rust製）	tree-sitter-rust
メモリ管理	アリーナアロケーション	標準ヒープ
高速モード	ブルームフィルタ完全実装	部分的実装
型チェック	実験的サポート	実験的サポート（`--experimental-types`）

パフォーマンス比較

実際のベンチマーク結果に基づく比較を示します。

similarity-rs（Rust 版）の利点は次のとおりです。

中規模ファイルで約 16 倍高速（ネイティブコードの効率性）
メモリ使用量が一定（Rc による参照カウント）
大規模ファイルでも安定動作（TypeScript は OOM エラー発生）
ネイティブ Rust コード（FFI オーバーヘッドなし）
Rust 固有機能（#[test]属性の検出など）

similarity-ts（TypeScript 版）の利点は次のとおりです。

小規模ファイルではやや高速（0.74x、プロセス起動オーバーヘッドなし）
ブルームフィルタ高速モードで約 4 倍高速化
oxc-parser による高速パース（swc より 3 倍高速）
アリーナアロケーションによるキャッシュ局所性向上
JavaScript エコシステムとの統合が容易

言語固有機能

similarity-ts の機能は次のとおりです。

型類似度検出
クラス比較サポート
デコレータサポート

similarity-rs の機能は次のとおりです。

implブロック解析
テスト関数フィルタリング
トレイト実装検出

研究基盤と理論的背景

similarity-rs の背後には、しっかりとした研究基盤があります。

TSED研究論文（Song et al., ACL 2024）

この研究では、48 以上のプログラミング言語で TSED の有効性が実証されました。

BLEU および Jaccard 類似度と 0.6-0.8 の相関
実行一致に関して意味論的メトリクスより高精度
最適重み: Insert=0.8、Delete=1.0、Rename=1.0

APTEDアルゴリズム（Pawlik & Augsten, 2015-2016）

木編集距離の堅牢な実装を提供し、メモリ使用量を抑制
最適な分解戦略により O(n·m) の時間計算量で動作
以前のアルゴリズム（RTED、Demaine など）を凌駕

学術的にも裏付けられた手法を使っている点は信頼性が高いです。

実用例：リファクタリング計画の立て方

実際の使用方法とリファクタリングへの活用方法を説明します。

Step 1: 重複コードを検出

similarity-rs . --threshold 0.85 --skip-test > duplicates.txt

Step 2: 優先度の高い重複を確認

出力の Priority スコアを見て、影響の大きい重複から着手します。

Priority: 11.5 (lines: 12, similarity: 92%)

Step 3: リファクタリング方針を決定

検出された重複コードを見て、以下を判断します。

共通化できる場合
- 共通関数として抽出
部分的に共通化できる場合
- 共通部分を関数として抽出
- 差分をパラメータ化
偶然の重複である場合
- 本質的に異なる処理なので、そのまま

Step 4: 継続的なモニタリング

CI/CD パイプラインに組み込んで、新しい重複が生まれないか監視します。

# .github/workflows/code-quality.yml
- name: Check code duplication
  run: |
    similarity-rs . --threshold 0.85 --skip-test
    if [ $? -ne 0 ]; then
      echo "Warning: Code duplication detected"
      # Slackに通知するなど
    fi

制限事項と今後の展望

現在の制限

公式ドキュメントにも明記されていますが、similarity-rs は実験段階です。

プロダクション環境での検証が不十分
ブルームフィルタが部分的実装（similarity-ts ほど最適化されていない）
マクロヘビーなコードには制限がある
rustc パーサーより 2-3 倍遅い（初回パース時）

既知の問題（KNOWN_ISSUES.md より）は次のとおりです。

Enum similarity detection: 構造的に同一の Enum でも約 43%の類似度しか検出されない
- 原因: Enum の variant 名が value として扱われ、rename_cost パラメータで適切に処理されない
- 回避策: Enum 比較時は閾値を 0.4-0.5 に下げる
Struct similarity detection: 正常に動作（90%以上の類似度を検出）

similarity-rsから学んだこと

similarity-rs を深掘りした結果、このツールから多くの重要な学びを得ることができました。

まず最も印象的だったのは、ASTベース解析の威力です。従来のテキストベースの類似度検出では、表面的な文字列の一致に頼るため、変数名やコメントの違いによって本質的に同じコードを見逃してしまうことがありました。しかし、AST ベースのアプローチでは構造的な類似性を捉えることができます。変数名が異なっていても、処理のロジックや制御構造が同じであれば、それを的確に検出できる点は非常に強力です。

次に感銘を受けたのは、Rust の型システムが可能にする最適化です。Rust の所有権システムは、メモリ安全性をコンパイル時に保証します。さらに、ゼロコスト抽象化により、高レベルな記述をしながらも実行時のオーバーヘッドを最小限に抑えられます。加えて、充実した並行処理プリミティブにより、マルチスレッド処理を安全に記述できます。これらの特性を組み合わせることで、安全性とパフォーマンスを両立したツールの実装が実現されています。

また、実装の随所に見られる実用的な最適化の積み重ねも注目に値します。ブルームフィルタによる事前フィルタリングで不要な比較を削減し、Rayon を活用した並列処理で処理速度を向上させています。さらに、テスト関数の自動除外や最小トークン数によるフィルタリングなど、実際の開発現場で役立つ工夫が随所に施されています。このような小さな最適化の積み重ねが、理論だけでなく実用的なツールを作り上げる鍵となることを実感しました。

最後に、このツールはACL 2024の論文をベースにした実装である点も重要です。学術研究で提案されたアイデアを、実際に動作するソフトウェアとして具現化しており、理論と実践の橋渡しをしている好例と言えます。研究成果を実装に落とし込む過程で、どのような工夫や最適化が必要になるのかを学ぶことができました。

おわりに

冒頭で述べた「結合度を測って適切にリファクタリングを促すツール」について、similarity-rs から学んだアプローチを応用できます。

AST ベースの解析で構造的な類似性を捉える
並列処理で大規模コードベースにも対応
優先度スコアでリファクタリングの優先順位を示す
CI/CD 統合で継続的にコード品質を監視

similarity-rs の実装を理解したことで、自分が作りたいツールの具体的なイメージが明確になりました。

GitHub リポジトリで実装の詳細を確認できます。コードは読みやすく構成されているため、Rust の学習にも適した教材です。

作者:Kent Beck
オーム社

構造的類似性を捉える技術 - similarity-rsで学ぶAST-basedコード解析の実装