AST解析

概要

similarity-goは、GoのAbstract Syntax Tree (AST) 解析を使用して、意味レベルでコード類似性を検出します。テキストベースの比較ツールとは異なり、AST解析はコードの構造と意味を理解し、表面的な違いがあっても機能的に類似したコードの検出を可能にします。

Abstract Syntax Trees

Abstract Syntax Treeは、ソースコードの構文構造のツリー表現です。各ノードは、プログラミング言語で発生する構造を表しています。

GoコードからASTへの例

この簡単なGo関数を考えてみましょう：

func add(a, b int) int {
    return a + b
}

AST表現には以下が含まれます：

FuncDecl (関数宣言)
- Ident “add” (関数名)
- FieldList (パラメータ)
  - Field “a” (パラメータ1)
  - Field “b” (パラメータ2)
  - Ident “int” (パラメータ型)
- FieldList (戻り値)
  - Field (戻り値の型)
    - Ident “int”
- BlockStmt (関数本体)
  - ReturnStmt (return文)
    - BinaryExpr (二項式)
      - Ident “a” (左オペランド)
      - Token ”+” (演算子)
      - Ident “b” (右オペランド)

類似性検出アルゴリズム

1. AST解析

各Goファイルに対して、similarity-goは：

go/parserを使用してソースコードを解析
ASTから関数宣言を抽出
比較のためにAST構造を正規化

2. ツリー比較

アルゴリズムは以下を使用してASTツリーを比較します：

構造的類似性

ノード型: ASTノードの型を比較
ツリーの深さ: 構造の深さと幅を分析
制御フロー: 類似した分岐パターンを識別

意味的類似性

操作: 変数名に関係なく類似した操作を識別
パターン: 共通のプログラミングパターンを認識
データフロー: データが関数を通ってどのように移動するかを理解

3. 正規化技法

精度を向上させるため、similarity-goは以下によってASTを正規化します：

変数名の抽象化

// 元の関数
func processUser(name string) { fmt.Println(name) }
func handleData(value string) { fmt.Println(value) }

// 正規化された表現
func FUNC(VAR1 string) { fmt.Println(VAR1) }

定数値の抽象化

// 元の関数
func checkAge() bool { return age > 18 }
func validateScore() bool { return score > 85 }

// 正規化された表現
func FUNC() bool { return VAR1 > CONST1 }

コメントと空白の除去

// コメント付きの元
func calculate(x int) int {
    // 入力に10を追加
    result := x + 10
    return result
}

// 正規化（コメントと余分な空白が除去）
func FUNC(VAR1 int) int {
    VAR2 := VAR1 + 10
    return VAR2
}

ASTノード分析

サポートされるノード型

similarity-goはこれらの主要なASTノード型を分析します：

ノード型	説明	重み
`FuncDecl`	関数宣言	高
`IfStmt`	If文	高
`ForStmt`	Forループ	高
`SwitchStmt`	Switch文	高
`BinaryExpr`	二項式	中
`CallExpr`	関数呼び出し	中
`AssignStmt`	代入	中
`ReturnStmt`	Return文	中
`Ident`	識別子	低
`BasicLit`	リテラル	低

重み付けシステム

異なるノード型は類似性スコアに異なる重みで寄与します：

制御フロー構造 (if, for, switch): 30%
関数呼び出しと操作: 25%
変数代入: 20%
式パターン: 15%
リテラル値: 10%