GumTreeを使ってTypeScriptのファイルを跨いだ移動操作を検出する
ソースコードの差分検出にはdiff
コマンドがよく使われます。diff
コマンドは、コード間の文字列のみを比較するため、構文的に異なっていても文字列が一致する行で誤った差分を検出することがあります。GumTree[1]は、抽象構文木(AST)単位で差分を解析するアルゴリズムを導入し、diff
コマンドの課題を解決します。
GumTreeとは
[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コードのコミット間でのファイルを跨いだ移動操作を検出することを目標とします。
対象にするのは、このコミットです。
sample.ts
に書かれているSampleType
型をtype.ts
に切り出す変更です。
- type SampleType = {
- id: number;
- name: string;
- }
+ import { SampleType } from "./type";
+ 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
で書かれています。
パース部分を@babel/parserに書き換えます。
- 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に変換します。
ファイルを跨いだ移動操作を検出する
ファイルを跨いだ移動操作を検出するために、変更前後の全ソースコードをそれぞれ1つのXMLにまとめて差分を比較します。この時、変更されたファイルのみを対象とすることで入力するXMLのサイズを減らします。
手順は次の通りです。
-
git diff --name-only
でコミット間で変更されたファイルパスのリストを抽出する -
git switch
でコミットを遡り、1.のリストにファイルがあれば、XMLに変換する - ルートノードを作成し、生成したXMLを追加していく
- 変更前後のXMLをGumTreeに入力する
手順3だけ少し説明します。
3. ルートノードを作成し、生成したXMLを追加していく
下記のXMLをルートとし、ファイル単位で生成されたXMLを追加していきます。
<?xml version="1.0"?>
<tree type="Program" pos="0" length="0">
</tree>
追加する時、ルートのlength
プロパティは各ファイルのlength
プロパティの総数にし、それぞれのpos
属性は1つ前に追加されたファイルの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
として検出されており、期待通りの結果を得ることができました。
あとがき
本記事で利用した実行環境はこちらです。
最初はただTypeScriptの差分解析をしてみた記事にしようと思っていたんですが、やっているうちにいろいろ試したくなり、こんな感じになりました。フロントエンドとはあんまり関係ないですが、許されるはずです。-
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. ↩︎
-
対応している言語一覧はこちら https://github.com/GumTreeDiff/gumtree/wiki/Languages ↩︎
-
Git連携の方法はこちら https://github.com/GumTreeDiff/gumtree/wiki/VCS-Integration ↩︎
-
章良藤本, 芳樹肥後, 淳之介松本, 真二楠本. プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出. 電子情報通信学会論文誌 D 情報・システム, Vol. J104-D, No. 4, pp. 242–254, 04 2021. 6 ↩︎
Discussion