Zenn
🌳

GumTreeを使ってTypeScriptのファイルを跨いだ移動操作を検出する

2023/12/17に公開
TypeScript
Babel
#
diff
#
acorn
#
gumtree
tech

ソースコードの差分検出にはdiffコマンドがよく使われます。diffコマンドは、コード間の文字列のみを比較するため、構文的に異なっていても文字列が一致する行で誤った差分を検出することがあります。GumTree[1]は、抽象構文木（AST）単位で差分を解析するアルゴリズムを導入し、diffコマンドの課題を解決します。

GumTreeとは

https://github.com/GumTreeDiff/gumtree
GumTreeは、ASTを比較する差分解析器です。変更前後のソースコードを受け取り、内部でASTを生成、独自形式のXMLに変換し、差分を解析します。出力形式には、TXT、XML、JSONなどを指定でき、追加・削除・移動を含む編集操作を対応するノード単位で出力してくれます。言語非依存の形式のXMLに変換する処理を挟むことで、Jave、C、JavaScriptなど、多言語に対応[2]しています。対応していない言語でも、XMLを出力するパーサを用意し、それをGumTreeにロードさせることで、差分を解析することが可能です。diffコマンドと異なる特徴は、ASTを比較するところと、移動操作を検出してくれるところです。

diffコマンドと同じようにビジュアライズして表示させることも可能で、Git連携もできます。[3]READMEに書かれているサンプルがわかりやすいので見てみてください。

GumTreeの入出力例

例えば、以下のコードは

console.log('hoge');

下記のようなXMLに変換されます。（ASTを出力するパーサにはAcornを使用）

<?xml version="1.0"?>
<tree type="Program" pos="0" length="20">
    <tree type="ExpressionStatement" pos="0" length="20">
        <tree type="CallExpression" pos="0" length="19">
            <tree type="MemberExpression" pos="0" length="11">
                <tree type="Identifier" pos="0" length="7" label="console"/>
                <tree type="Identifier" pos="8" length="3" label="log"/>
            </tree>
            <tree type="Literal" pos="12" length="6" label="'hoge'"/>
        </tree>
    </tree>
</tree>

type、pos、lengthで構成されており、IdentifierやLiteralにはlabelが追加されます。

次に、ブロックで囲うようにソースコードを変更します。

- console.log('hoge');
+ {
+   console.log('hoge');
+ }

diffコマンドでは、削除+追加と検出されることがわかります。

GumTreeの出力は下記の通りです。

{
  "matches": [
    {
      "src": "Literal: 'hoge' [12,18]",
      "dest": "Literal: 'hoge' [16,22]"
    },
    ...
  ],
  "actions": [
    {
      "action": "insert-node",
      "tree": "BlockStatement [0,26]",
      "parent": "Program [0,26]",
      "at": 0
    },
    {
      "action": "move-tree",
      "tree": "ExpressionStatement [0,20]",
      "parent": "BlockStatement [0,26]",
      "at": 0
    }
  ]
}

actionsを見ると、BlockStatementの追加と、ExpressionStatementの移動と判定されていることがわかります。このように、GumTreeを利用すると移動操作を検出することができます。ExpressionStatementとだけ言われると何かわかりませんが、[number, number]で表される部分が位置情報を表すため、ASTを走査することでconsole.log('hoge');が移動されたことを特定することができます。

本記事の目標

今回は、TypeScriptコードのコミット間でのファイルを跨いだ移動操作を検出することを目標とします。

対象にするのは、このコミットです。
https://github.com/k1tikurisu/commmit-diff-sample/commit/dbe0d04a7f5db72cb8768042dd3b6079bae1bf4f

sample.tsに書かれているSampleType型をtype.tsに切り出す変更です。

sample.ts
- type SampleType = {
-   id: number;
-   name: string;
- }
+ import { SampleType } from "./type";
type.ts
+ export type SampleType = {
+   id: number;
+   name: string;
+ }

このように、ファイルを跨いだ移動操作は、ソースコードの削除+追加と判定されますが、それを移動操作と判定することが目標です。

TypeScriptのファイルを跨いだ移動操作を検出する

XMLを出力するTypeScriptパーサを作成し、それを使ってファイルを跨いだ移動操作を検出します。ファイルを跨いだ移動操作の検出には、ファイル単位で生成したASTを結合する考え方[4]を利用させていただきます。

XMLを出力するJavaScriptパーサをTypeScriptに対応させる

GumTreeはデフォルトでTypeScriptに対応しており、パーサにはtree-sitterを使用しています。tree-sitterは多言語をパースできるため、GumTreeのパーサはtree-sitterを利用しているものがほとんどです。今回は、生成したXMLをGumTreeに入力したいため、内部で使用されているパーサは使用できません。幸い、公式がXMLを出力するJavaScriptパーサを提供してくれているので、それをTypeScriptに対応させる方針にします。

パーサ自体は30行で、Acornで書かれています。
https://github.com/GumTreeDiff/jsparser/blob/main/jsparser

パース部分を@babel/parserに書き換えます。

jsparser
- const acorn = require('acorn');
+ const parser = require('@babel/parser');

- const ast = acorn.parse(code, {ecmaVersion: 2020, sourceType: 'module'});
+ const ast = parser.parse(code, { sourceType: 'module', plugins: ['estree', 'typescript']})

@babel/parserのtypescriptプラグインを使用し、TypeScriptに対応させます。estreeプラグインを使うことで、JavaScriptの構文はAcornと出力を揃えることができます。
このパーサを使用して、TypeScriptコードをXMLに変換します。

ファイルを跨いだ移動操作を検出する

ファイルを跨いだ移動操作を検出するために、変更前後の全ソースコードをそれぞれ１つのXMLにまとめて差分を比較します。この時、変更されたファイルのみを対象とすることで入力するXMLのサイズを減らします。

手順は次の通りです。

  1. git　diff --name-onlyでコミット間で変更されたファイルパスのリストを抽出する
  2. git switchでコミットを遡り、1.のリストにファイルがあれば、XMLに変換する
  3. ルートノードを作成し、生成したXMLを追加していく
  4. 変更前後のXMLをGumTreeに入力する

手順3だけ少し説明します。

3. ルートノードを作成し、生成したXMLを追加していく

下記のXMLをルートとし、ファイル単位で生成されたXMLを追加していきます。

root.xml
<?xml version="1.0"?>
<tree type="Program" pos="0" length="0">
</tree>

追加する時、ルートのlengthプロパティは各ファイルのlengthプロパティの総数にし、それぞれのpos属性は１つ前に追加されたファイルのlengthプロパティを足すことで整合性が保たれるようにします。
イメージは、全ソースコードを結合してからXMLに変換するのと同じです。ただし、全ソースコードを結合してからXMLに変換する方法だと、構文エラーにより変換できないことがあるため、各ファイルごとに生成したXMLを結合する方法を採用しています。

最終的にできた変更前後のXMLをGumTreeに入力して結果を受け取ります。

出力結果

先ほどの手順で作成したXMLをGumTreeに入力して得た出力は次の通りです。

{
  "matches": [
    ...
  ],
  "actions": [
    {
      "action": "insert-tree",
      "tree": "ImportDeclaration [0,36]",
      "parent": "Program [0,170]",
      "at": 0
    },
    {
      "action": "insert-node",
      "tree": "ExportNamedDeclaration [112,170]",
      "parent": "Program [0,170]",
      "at": 2
    },
    {
      "action": "move-tree",
      "tree": "TSTypeAliasDeclaration [0,51]",
      "parent": "ExportNamedDeclaration [112,170]",
      "at": 0
    }
  ]
}

検出された編集操作は、import宣言の追加、export宣言の追加、型定義の移動、と、SampleType型のファイルを跨いだ移動がmove-treeとして検出されており、期待通りの結果を得ることができました。

あとがき

本記事で利用した実行環境はこちらです。
https://github.com/k1tikurisu/gumtree-sample
最初はただTypeScriptの差分解析をしてみた記事にしようと思っていたんですが、やっているうちにいろいろ試したくなり、こんな感じになりました。フロントエンドとはあんまり関係ないですが、許されるはずです。

脚注

  1. Jean-R ́emy Falleri, Flor ́eal Morandat, Xavier Blanc, Matias Martinez, and Martin Monperrus. Fine-grained and accurate source code differencing. In Proceedings of the 29th ACM／IEEE International Conference on Automated Software Engineering (ASE’14), p. 313–324, 2014. ↩︎

  2. 対応している言語一覧はこちら https://github.com/GumTreeDiff/gumtree/wiki/Languages ↩︎

  3. Git連携の方法はこちら https://github.com/GumTreeDiff/gumtree/wiki/VCS-Integration ↩︎

  4. 章良藤本, 芳樹肥後, 淳之介松本, 真二楠本. プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出. 電子情報通信学会論文誌 D 情報・システム, Vol. J104-D, No. 4, pp. 242–254, 04 2021. 6 ↩︎

GitHubで編集を提案

Discussion