Go1.18で追加された型セットを静的解析する

## 概要
先日[メルカリの短期インターン](https://mercan.mercari.com/articles/31914/)に参加した際にGo1.18の機能に焦点を当てたOSS開発をする機会があったので、そこで得られた知見をまとめようと思います。

３/16にGo1.18がリリースされ、様々な機能が追加されました。その中の一つである型パラメタ（ジェネリクス）について、機能追加に伴い新たに型セット（[Type Set](https://github.com/golang/go/issues/45346)）という概念も追加されました。


- [Type Parameters Proposal](https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md)
- [Type setに関するIssue](https://github.com/golang/go/issues/45346)

本記事では、型セットがGoの中でどのようになっているのかを、Goの標準パッケージで提供されている静的解析機能を用いて見ていきたいと思います。

## 静的解析ってなに？
> 静的コード解析 (せいてきコードかいせき、static code analysis) または静的プログラム解析 (static program analysis)とは、コンピュータのソフトウェアの解析手法の一種であり、実行ファイルを実行することなく解析を行うこと。
> 引用元：[静的コード解析 - Wikipedia](https://ja.wikipedia.org/wiki/%E9%9D%99%E7%9A%84%E3%82%B3%E3%83%BC%E3%83%89%E8%A7%A3%E6%9E%90)

要は、プログラムを実行せずに解析すること。
その言語の文法上問題はなくコンパイルエラーは起きないけど、実行時にランタイムエラーなどが発生する可能性があるようなバグを、実行せずに解析することができる。

このあたりの詳しい話は[＠tenntennさん](https://twitter.com/tenntenn)が[この資料](https://docs.google.com/presentation/d/1I4pHnzV2dFOMbRcpA-XD0TaLcX6PBKpls6WxGHoMjOg/edit#slide=id.g80ffbfd5e3_0_168)にわかりやすくまとめてくださっているので、こちらを見ていただければと思います。

## 抽象構文木ってなに？
> 抽象構文木（英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。
> 引用元：[抽象構文木 - Wikipedia](https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8#:~:text=%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8%EF%BC%88%E8%8B%B1%3A%20abstract,%E6%9C%89%E5%90%91%E6%9C%A8%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82)

初めて聞く方は？？？ってなると思います。自分もそうでした。
おそらく文章で説明するより、実例を見た方がわかりやすいと思うので、簡単な例を挙げます。

以下のようなGoのソースコードをASTで表してみます。
```golang
package main

import (
	"fmt"
)

func main() {
	fmt.Println("Hello, World")
}
```
```
File
├── Doc
├── Package = main.go:2:1
├── Name
│   └── Ident
│       ├── NamePos = main.go:2:9
│       ├── Name = main
│       └── Obj
├── Decls (length=2)
│   ├── GenDecl
│   │   ├── Doc
│   │   ├── Tok = import
│   │   └── Specs (length=1)
│   │       └── ImportSpec
│   │           ├── Doc
│   │           ├── Name
│   │           ├── Path
│   │           │   └── BasicLit
│   │           │       ├── Kind = STRING
│   │           │       └── Value = "fmt"
│   │           ├── Comment
│   │           └── EndPos = -
│   └── FuncDecl
│       ├── Doc
│       ├── Recv
│       ├── Name
│       │   └── Ident
│       │       ├── NamePos = main.go:8:6
│       │       ├── Name = main
│       │       └── Obj
│       │           └── Object
│       │               ├── Kind = func
│       │               ├── Name = main
│       │               ├── Decl = &ast.FuncDecl{Doc:(*ast.CommentGroup)(nil), Recv:(*ast.FieldList)(nil), Name:(*ast.Ident)(0xc000060060), Type:(*ast.FuncType)(0xc0000600e0), Body:(*ast.BlockStmt)(0xc0000762a0)}
│       │               ├── Data = <nil>
│       │               └── Type = <nil>
│       ├── Type
│       │   └── FuncType
│       │       ├── Func = main.go:8:1
│       │       ├── TypeParams
│       │       ├── Params
│       │       │   └── FieldList
│       │       │       ├── Opening = main.go:8:10
│       │       │       ├── List (length=0)
│       │       │       └── Closing = main.go:8:11
│       │       └── Results
│       └── Body
│           └── BlockStmt
│               ├── Lbrace= main.go:8:13
│               ├── List (length=1)
│               │   └── ExprStmt
│               │       └── X
│               │           └── CallExpr
│               │               ├── Fun
│               │               │   └── SelectorExpr
│               │               │       ├── X
│               │               │       │   └── Ident
│               │               │       │       ├── NamePos = main.go:9:2
│               │               │       │       ├── Name = fmt
│               │               │       │       └── Obj
│               │               │       └── Sel
│               │               │           └── Ident
│               │               │               ├── NamePos = main.go:9:6
│               │               │               ├── Name = Println
│               │               │               └── Obj
│               │               ├── Lparen = main.go:9:13
│               │               ├── Args (length=1)
│               │               │   └── BasicLit
│               │               │       ├── Kind = STRING
│               │               │       └── Value = "Hello, World"
│               │               ├── Ellipsis = -
│               │               └── Rparen = main.go:9:28
│               └── Rbrace= main.go:10:1
...
```
使用ライブラリ：https://github.com/knsh14/astree

このように、ASTとはソースコードの情報を木構造で表したものになります。
GoではASTの情報やそこから型の情報を取得するための機能が標準・準標準パッケージとして提供されているため、今回はそれらを用いてコードを解析していきます。

## 実際にやってみる
今回は、以下の型セットについて解析していきたいと思います。
```golang
type I interface {
	int | string | float64
}
```

### 1. 静的解析をするための準備
Goで静的解析を行う場合、[x/tools/go/analysis](https://pkg.go.dev/golang.org/x/tools/go/analysis)を使うと便利なのですが、１から自分で書くのはけっこう難しいです。
そのため、先述の[tenntennさん](https://twitter.com/tenntenn)が公開してくださっている、[skeleton](https://github.com/gostaticanalysis/skeleton)という静的解析を行うためのテンプレートを生成してくれるライブラリを使います。詳しい使い方はリポジトリを見てください。

[skeleton](https://github.com/gostaticanalysis/skeleton)を使うと、自分が変更する部分は以下の`run(...)`関数の中になります。（めっちゃ簡単！）
```golang
// この中だけ変更すれば動く！
func run(pass *analysis.Pass) (interface{}, error) {
	// 欲しい情報ややりたい処理などをここに書いていく
	return nil, nil
}
```

### 2. 抽象構文木(AST)を見てみる
まず、解析対象のソースコードをASTで表すとどのようになっているか見てみます。
全てを書くと長くなってしまうので、型セットの情報を取得するのに必要な部分のみ抜粋しました。
```
...
└── InterfaceType
    ├── Interface = main.go:4:8
    ├── Methods
    │   └── FieldList
    │       ├── Opening = main.go:4:18
    │       ├── List (length=1)
    │       │   └── Field
    │       │       ├── Doc
    │       │       ├── Names (length=0)
    │       │       ├── Type
    │       │       │   └── BinaryExpr
    │       │       │       ├── X
    │       │       │       │   └── BinaryExpr
    │       │       │       │       ├── X
    │       │       │       │       │   └── Ident
    │       │       │       │       │       ├── NamePos = main.go:5:2
    │       │       │       │       │       ├── Name = int
    │       │       │       │       │       └── Obj
    │       │       │       │       ├── Op = |
    │       │       │       │       └── Y
    │       │       │       │           └── Ident
    │       │       │       │               ├── NamePos = main.go:5:8
    │       │       │       │               ├── Name = string
    │       │       │       │               └── Obj
    │       │       │       ├── Op = |
    │       │       │       └── Y
    │       │       │           └── Ident
    │       │       │               ├── NamePos = main.go:5:17
    │       │       │               ├── Name = float64
    │       │       │               └── Obj
...

```

ASTを見ると、型セットの情報は`InterfaceType`というノードに入っているようです。
また、型セットを構成している型集合の情報はそのノード内の`Methods -> FieldList -> List -> Type`の中に入っているようです。ちょっとネストしすぎてわかりづらいですね。
そして、各型の情報はその中の`BinaryExpr -> Ident`というノードの中にまとめられている、ということがわかりました。

そのため、`run(...)`関数の中ではまず、`InterfaceType`ノードの情報をのみを取り出します。
ノード内の`Methods -> FieldList -> List`はスライスになっているので、`for`で情報を順番に取り出していきます。
型セットの情報を出力する`printBinaryExpr()`関数については次節で解説します。
```golang
func run(pass *analysis.Pass) (interface{}, error) {
	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)

	nodeFilter := []ast.Node{
		(*ast.InterfaceType)(nil),
	}

	inspect.Preorder(nodeFilter, func(n ast.Node) {
		switch n := n.(type) {
		case *ast.InterfaceType:
			for _, field := range n.Methods.List {
				// 3. で解説
				printBinaryExpr(field)
			}
		}
	})

	return nil, nil
}
```

### ３. 抽象構文木（AST）のtraverse
ASTをtraverseしていく方法についても[tenntennさん](https://twitter.com/tenntenn)が[こちらの記事](https://qiita.com/tenntenn/items/f029425a844687a0e64b)で解説してくださっており、本記事でもそれを応用したものを紹介します。

2.でも書いたように、各型の情報は`BinaryExpr　-> Ident`ノードの中に入っているため、このノードについてtraverseしていき、情報を取得していくのがいいと思います。

[前述の記事](https://qiita.com/tenntenn/items/f029425a844687a0e64b)を参考に、`ast.Walk()`に渡す関数の中身を少し変えて実装してみました。
`ast.BinaryExpr`ノードに出会うたびに、再帰的に`ast.Walk()`の第一引数に渡した関数の引数としてそれぞれノードの`X, Y`を指定して、ノードをtraverseしていく。
`ast.Ident` or `ast.UnaryExpr`まで辿れば型セットの中に含まれる型名がわかるので、それらを出力する。
という流れになります。
```golang
type visitorFunc func(node ast.Node) (w ast.Visitor)

func (f visitorFunc) Visit(node ast.Node) (w ast.Visitor) {
	return f(node)
}

func printBinaryExpr(n *ast.Field) {
	var v visitorFunc
	v = visitorFunc(func(node ast.Node) (w ast.Visitor) {
		if node == nil {
			return nil
		}
		switch n := node.(type) {
		// 今見ているノードが*ast.Identならば、その型名を出力する
		case *ast.Ident:
			fmt.Println(n.Name)
		// 今見ているノードが*ast.UnaryExpr (ex. ~string)ならば、その型名を出力する
		case *ast.UnaryExpr:
		 	ident, _ := n.X.(*ast.Ident)
		 	fmt.Println(ident.Name)
		// 今見ているノードが*ast.BinaryExprならば、再帰的にその中のノードをvに渡す
		case *ast.BinaryExpr:
			ast.Walk(v, n.X)
			ast.Walk(v, n.Y)
		}
		return nil
	})
	ast.Walk(v, n.Type)
}
```

## まとめ
- 今回は、静的解析を用いて簡単に型セットの中身を出力してみました。
- 静的解析を行うことで型の中身などの情報を簡単に取得することができるため、型セットがどのような集合なのかを可視化するベン図を描画したり、型セットが有効なものかどうか（空集合になっていないか？）など、様々な解析に応用できる可能性を感じました。
- [skeleton](https://github.com/gostaticanalysis/skeleton)のおかげでかなり静的解析を行うためのハードルは低いと感じました。今回のインターンで初めて静的解析を行ったのですが、それでもかなりいろんなことができたと思います。
- また、静的解析の進め方がなんとなくわかってきたので、今後も「ここエラーでないの気持ち悪くない？」とか「こういう機能あったら便利だなぁ」と思うようなことがあったときに、自分でそれを解決するためのツールを書いてみようと思いました。

色々書きましたが、表現が間違っていたり理解しづらい部分があれば、是非コメントしていただけるとありがたいです。

## 参考リンク集
- [Type Parameters Proposal](https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md)
- [Type setに関するIssue](https://github.com/golang/go/issues/45346)
- [The Go Programming Language Specification - Interface types](https://tip.golang.org/ref/spec#Interface_types)
- [静的コード解析 - Wikipedia](https://ja.wikipedia.org/wiki/%E9%9D%99%E7%9A%84%E3%82%B3%E3%83%BC%E3%83%89%E8%A7%A3%E6%9E%90)
- [抽象構文木 - Wikipedia](https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8#:~:text=%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8%EF%BC%88%E8%8B%B1%3A%20abstract,%E6%9C%89%E5%90%91%E6%9C%A8%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82)
- [14. 静的解析とコード生成 - プログラミング言語Go完全入門](https://docs.google.com/presentation/d/1I4pHnzV2dFOMbRcpA-XD0TaLcX6PBKpls6WxGHoMjOg/edit#slide=id.g80ffbfd5e3_0_168)
- [抽象構文木（AST）をトラバースする #golang](https://qiita.com/tenntenn/items/f029425a844687a0e64b)
- [skeleton](https://github.com/gostaticanalysis/skeleton)
- [astree](https://github.com/knsh14/astree)