はじめに

パーソナライズGopher道場でGoの静的解析を学んでおり、何か便利な静的解析ツールを実装したいなと思いgenericsの型制約を一覧で表示できるtslistを実装しました！
この記事はそれを実装していった手順を通して、型セットの仕組みを深堀りしています。

静的解析に興味がある方や、genericsの型制約や型セットの仕組みを詳しく理解したい方は楽しめる内容になっているかなと思います。

また、この記事は執筆時のGo1.18.3のgenericsの状態に基づいています。今後のアップデートでこの記事の内容が古くなっている場合がありますが、ご了承ください。

genericsについて

この記事では、型セットや型パラメータとは何かということには触れないです。
なので、それらについて知りたい方は、

や

などがとてもわかりやすくまとまっているのでご覧ください。
公式のチュートリアルやブログもとても参考になります。
https://go.dev/doc/tutorial/generics
https://go.dev/blog/when-generics

静的解析について

静的解析の仕組み等についてもこの記事では触れません。
興味がある方は、
http://tenn.in/go
こちらの「14. 静的解析とコード生成」の章をご覧ください。
事細かに書かれています。

tslistの機能

何ができるのか

https://github.com/kimuson13/tslist
tslistはgenericsの型セットを一覧で表示する静的解析ツールとなっています。
以下にtslistの使いどころの例を示します。

準標準パッケージであるgolang.org/x/exp/constraintsパッケージを見ると、以下のようなinterfaceが定義されています。

type Integer interface {
    Signed | Unsigned
}

このIntegerはSignedというinterfaceとUnsignedという別のinterfaceのunionであることが分かります。しかし、実際Integerという型制約にはどのような型が含まれるかは、SignedとUnsignedが何を含んでいるかを確認する必要があります。

それぞれ見てみると、

type Signed interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64
}

type Unsigned interface {
    ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

となっています。なので、Integerは実際は以下のような型制約になっています。

type Integer interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

コードとして書く際は、SignedをUnsignedそれぞれ定義して、2つのunionを取るのがベストだと思いますが、あとからコードを読むときは一発で何の型が含まれているか確認したいところです。

この時、今回実装したtslistを使用すると一発でそれを確認することができます。

$ tslist golang.org/x/exp/constraints
/[GOPATH]/golang.org/x/exp@[version情報]/constraints/constraints.go:26:14:
Integer
type set: [~uint32 ~uint64 ~int ~int16 ~int32 ~uint ~uint8 ~int8 ~int64 ~uint16 ~uintptr]
method list:

というように表示されます。

tslistはそのinterfaceのメソッドも表示するようになっています。
これは、型セットとメソッドを両方持っていた場合、型を満たしており、なおかつメソッドも持っていないと型引数として使うことができなくなっているためです。

試しにfmtパッケージにかけてみるとこのように表示されます。(一部抜粋です。)

$ tslist fmt
/usr/local/go/src/fmt/print.go:38:12: 
State
type set: [any]
method list:
Write(b []byte) (n int, err error) 
Width() (wid int, ok bool) 
Precision() (prec int, ok bool) 
Flag(c int) bool

なので、tslistはinterfaceが何を満たしているかを型セット、メソッドリストに限らず表示するツールになっています。

tslist実装のモチベーション

tslistを実装したモチベーションは型制約を一発で確認したかったからと先ほど書きましたが、実はもう1つあります。

それは型パラメータの静的解析のロジックを毎度書かなくてよくするためです。ロジックについては後で詳しく書きますが、interfaceの中でfieldとして渡されたものの種類によって挙動を変えて、場合によっては再帰で探索していく必要があります。

これを型パラメータなどを解析したいと思ったときに、毎度interfaceの探索機能を実装するのはしんどいなと思ったので、今回はその探索部分も公開することにしました。

型セットを一覧で取ってくるのは準標準パッケージにあった.....

tslistのinterfaceから型パラメータを解析する処理がほとんど完成したときに、ふとTwitter経由でtenntennさんのこちらのZennのスクラップを見つけました。

もしやと思い、golang.org/x/exp/typeparamsを確認してみたところ、NormalTemrsというものがあり、これは型制約に実際はどの型が含まれているかを明らかにするという点では全く同じことをしていました。

つまり、完全に車輪の再発明でした.....

とはいえ、

アプローチが若干異なる
本質的に作りたかったのはそれを表示するtslist
準標準パッケージにあるなら、いずれ標準になる可能性もあり、それはそれでありがたいしうれしい
静的解析のいい勉強になった

という4つの理由から、今回はそのまま実装を続けることにしました。

実装する前にもう少し下調べをした方がよかったなとは思いました.....
自分は型制約が何の型を含んでいるかわかる機能を提供しているパッケージがあればすでに話題になっているはずだと思い、そこまで調べずに実装を始めていました。

tslistの実装について

ここからは実際にどのようにtslistを実装したかを説明していきます。
静的解析に関わる話が多いですが、型セットの概念の理解が深まるものにもなっていると思うので、雰囲気で読み進めていただいても大丈夫です。

また、それぞれの登場する構造体について事細かに説明するというよりも今回の実装に用いた部分だけを説明していきます。

interfaceの解析

型セットはinterfaceによって定義されるため、interfaceを表す*ast.InterfaceTypeという構造体から内容を取得することができます。

godocを見てみると、以下のようになっています。

type InterfaceType struct {
	Interface  token.Pos  // position of "interface" keyword
	Methods    *FieldList // list of embedded interfaces, methods, or types
	Incomplete bool       // true if (source) methods or types are missing in the Methods list
}

今回だと、このMethodsの部分に型セットを表すものと、メソッドの情報が含まれています。
そして、FieldListはこのようになっています。

type FieldList struct {
	Opening token.Pos // position of opening parenthesis/brace/bracket, if any
	List    []*Field  // field list; or nil
	Closing token.Pos // position of closing parenthesis/brace/bracket, if any
}

このListの部分にメソッドか型セットの情報が1行ずつ入っています。そのためこのFieldに対してさらに解析をしていく必要があります。

type Field struct {
	Doc     *CommentGroup // associated documentation; or nil
	Names   []*Ident      // field/method/(type) parameter names; or nil
	Type    Expr          // field/method/parameter type; or nil
	Tag     *BasicLit     // field tag; or nil
	Comment *CommentGroup // line comments; or nil
}

Fieldはこのようになっています。Typeの部分にメソッドか、型パラメータを表す値かがわかるようになっています。
このTypeが何を示すかを見てそれぞれに対して別の処理を施し、型セットを判断していきます。

Typeは今回の場合だと

*ast.Ident
識別子を表すもの。intなどの型が入ります。
*ast.BinaryExpr
二項演算子を表すもの。unionが入るので、int | stringなどです。
*ast.UnaryExpr
~intなどを表すものです。
*ast.ArrayType
スライスの型を表すものです。
*ast.FuncType
メソッドを表すものです。
*ast.StarExpr
*intなどのポインターを表すものです。

という6つのTypeが含まれます。

この記事では*ast.Identと*ast.BinaryExprで行ったことを軽く説明します。
実際にはそれぞれに対して処理をする関数に分けています。

*ast.Ident

*ast.Identになるケースは3つ考えられます。

組み込み型(int, string)
ユーザー定義型(構造体も含みます)
別のinterface(Integerに含まれているSignedのような感じ)

組み込み型やユーザー定義型の場合は型名と型の情報が取れれば大丈夫です。別のinterfaceの場合、interfaceの探索を行っている関数を再帰的に呼び出していく必要があります。

*ast.BinaryExpr

*ast.BinaryExprの場合も、再帰的に関数を呼び出す必要があります。
というのも型セットにおける*ast.BinaryExprはint | stringのようになっており、左右それぞれ見ていく必要があります。

これに加えて、int | string | boolのように3個以上でunionが構成されている場合は、まずintとstring | boolに分かれるので右側のstring | boolに対してもさらに探索をすることになります。

ast.BinaryExprは以下のようになっています。

type BinaryExpr struct {
	X     Expr        // left operand
	OpPos token.Pos   // position of Op
	Op    token.Token // operator
	Y     Expr        // right operand
}

Xが左側をYが右側の値を表しています。

ここまでの内容を元に実装すると、以下のようになります。

func interfaceVisitor(expr *ast.InterfaceType) {

    // バリデーション的な処理

    // フィールドを1つ1つ見ていきます
    for _, field := range expr.Methods.List {
        exprVisitor(field.Type)
    }
}

func exprVisitor(expr ast.Expr) {
    switch expr := expr.(type) {
    case *ast.BinaryExpr:
        exprVisitor(expr.X)
        exprVisitor(expr.Y)
    case *ast.Ident:
        identVisitor(expr)
    // 他の場合が続きます
    }
}

func identVisitor(expr *ast.Ident) {
    // いろいろな処理

    // 別のinterfaceだった場合
    // interfaceDecはインターフェースを定義しているものを指します。
    res := interfaceVisitor(interfaceDec)
}

しかし、これまでの説明だけだと、ただ探索をしているだけで探索結果に対して何も行っていないことがわかります。

次の「unionの処理」、「共通部分の処理」の中で探索結果の保持方法とそれぞれの処理について説明していきます。

unionの処理

ここからはどのように探索結果を保持して、実際に型を処理しているかを説明していきます。

実は先ほど紹介した関数はすべてVisitorという構造体のメソッドとして定義しています。
Visitorは型セットに関わるところだと以下のようなフィールドを持っています。

type Visitor struct {
    nest int
    typeResults map[int][]string
}

nestはinterfaceの先頭から何行目かを示すものになっています。
typeResultsはそれぞれの行ごとの結果を保持するためのものになっています。これを元に行ごとに評価をしていきます。

type example interface {
    int | string | bool // 1行目
    string              // 2行目
}

なので、先ほどのまとめた例にここまでのことを反映すると、

// 最終的な結果を返すための構造体(ここでは簡易的に型名のスライスを持っていることにします)
type Result struct {
    Results []string
}

func InterfaceVisitor(interfaceType: *ast.InterfaceType) Result {
    visit := Visitor{typeResults: make(map[int][]string)}
    visit.interfaceVisitor(interfaceType)

    return Result
}

func (v *Visitor) interfaceVisitor(expr *ast.InterfaceType) {

    // バリデーション的な処理

    for _, field := range expr.Methods.List {
        v.nest++
        v.exprVisitor(field.Type)
    }
}

func (v *Visitor) exprVisitor(expr ast.Expr) {
    switch expr := expr.(type) {
    case *ast.BinaryExpr:
        v.exprVisitor(expr.X)
        v.exprVisitor(expr.Y)
    case *ast.Ident:
        v.identVisitor(expr)
    // 他の場合が続く
    }
}

func (v *Visitor) identVisitor(expr *ast.Ident) {
    // いろいろな処理

    // 別のinterfaceだった場合
    // interfaceDecはインターフェースを定義しているものを指します。
    // 説明のためにこのような名前にしています。
    res := InterfaceVisitor(interfaceDec)
    for _, result := range res.Results {
        v.typeResult[v.nest] = append(v.typeResult[v.nest], result)
    }
}

行ごとに評価する必要があるのは、anyが存在するからです。
anyはGo1.18からinterface{}型の型エイリアスになっています。
つまり、これはどのような型にもなりうるものです。
これを型セットのunionの中に持たせるとすべてanyになってしまいます。

以下の例を見てください。

type containAny interface {
    string | int | bool | any 
}

このcontainAnyという型セットがあった場合、実際は以下のようなinterfaceと同じになります。

type containAny interface {
    any
}

そのためunionの処理は、その行のunionにanyが含まれる場合はanyだけの型になるようにする必要があります。

そして処理の結果はmapに内容を保持するようにします。この理由は後の「共通部分の処理」で詳しく説明するので、mapにいれるんだなくらいの気持ちで大丈夫です。
実装としては以下のようになります。

func (v *Visitor) parseTypeSet() []string {
    typeSet := make(map[string]int)
    for _, results := range v.typeResults {
        // anyがあったらanyにしてその行の処理を終わりにします
        if lo.Contains(results, "any") { 
            typeSet["any"]++
            continue
        }

        for _, result := range results {
            typeSet[result]++
        }
    }
}

anyをうまく処理しても、まだ対応しないと行けないところはあります。

本来だと1つの行に含まれる型はユニークでないとコンパイルエラーになりますが、別でinterfaceを定義した場合はコンパイルが通るので、それにも対応する必要があります。以下にこの状況の例を示します。

type ng1 interface { // "overlapping terms int and int"とコンパイルに怒られます。
    int | int
}

type ng2 interface { // "overlapping terms ~int and int"と上と同様に怒られます。
    int | ~int
}

type other interface {
    int
}

type ok interface { // これはコンパイルが通ります。
    other | int
}

これに対しては、

unionの行にはユニークな型しか最終的に含まれないようにする
~がついている型がunionにあった場合、元の型は結果のmapにカウントしない

という2つの策で解決するようにしました。これを反映させると以下のような実装になります。

func (v *Visitor) parseTypeSet() []string {
    typeSet := make(map[string]int)
    for _, results := range v.typeResults {
        // anyがあったらanyにしてその行の処理を終わりにします。
        if lo.Contains(results, "any") { 
            typeSet["any"]++
            continue
        }

        // 被りをなくします。
        results = lo.Uniq(results)

        for _, result := range results {
            // その型の~があれば、その型自体は結果に含まないようにします。
            if lo.Contains(results, fmt.Sprintf("~%s", result)) {
                continue
            }
            typeSet[result]++
        }
    }
}

これでunionの処理は完了しました。
次に、共通部分の処理について見ていきます。

共通部分(intersection)の処理

ここからは、共通部分の処理について説明していきます。
まず簡単な例を下に示しました。

type example2 interface {
    string | int
    string
}

この場合の共通部分はstringになります。つまり、すべての行で存在している型が共通部分に当たることになります。

なので、これはmapで処理することができます。mapでその型の出現回数を把握し、行の数と同じならすべての行に含まれていると判断することにしました。

それを先ほどのparseTypeSetに反映させると以下のようになります。

func (v *Visitor) parseTypeSet() []string {
    typeSet := make(map[string]int)
    for _, results := range v.typeResults {
        if lo.Contains(results, "any") {
            typeSet["any"]++
            continue
        }

        results = lo.Uniq(results)

        for _, result := range results {
            if lo.Contains(results, fmt.Sprintf("~%s", result)) {
                continue
            }

            typeSet[result]++
        }
    }

    // 共通部分の処理
    res := make([]string, 0, len(typeSet))
    for typeName, num := range typeSet {
        if num == v.nest {
            res = append(res, typeName)
        }
    }

    return res
}

ここでもanyの扱いについて考えていきます。anyの共通部分はすべての型になります。
下のexample3は実際にはintだけを持った型セットになります

type example3 interface {
    int
    any
}

なので、unionの処理を先にやってそれぞれの行がanyかどうかを先に判断しておく必要があります。下のexample4という型セットを元にどのように処理されているかを見ていきます。

type example4 interface {
    int | string | any | bool
    float64
}

まずは各行ごとにunionを処理するので以下のようになります。

type example4 interface {
    any     //anyがあったのでanyだけを持っていることになります
    float64
}

そして共通部分を処理すると以下のようになります。

type example4 interface {
    float64
}

この一連の処理の仕方から、anyは型セットの共通部分の判定において行としての意味をなさないことがわかります。
なので、以下の2つは同じ型を持つ型セットになります。

type same1 interface {
    int
}

type same2 interface { // intだけの型セットと同じ
    any
    int
    any
    any
    string | any
}

そのため、anyの出現数をフィールドの行数を把握しているnestから引き、any自体が含まれないようにanyの数を出現数としてあり得ない数(-1)にする必要があります。
それを反映すると以下のようになります。

func (v *Visitor) parseTypeSet() []string {
    // unionの処理
    typeSet := make(map[string]int)
    for _, results := range v.typeResults {
        if lo.Contains(results, "any") {
            typeSet["any"]++
            continue
        }

        results = lo.Uniq(results)

        for _, result := range results {
            if lo.Contains(results, fmt.Sprintf("~%s", result))
            typeSet[result]++
        }
    }

    // 共通部分の処理
    res := make([]string, 0, len(typeSet))
    // nestからanyの数を引く処理
    if val, ok := typeSet["any"]; ok {
        v.nest -= val
        typeSet["any"] = -1
    }

    for typeName, num := range typeSet {
        if num == v.nest {
            res = append(res, typeName)
        }
    }

    return res
}

ここまでで、だいたいの処理は完成しました。

あと3つ型セットの理解が深まるコーナーケースがあるのでそれを紹介します。

ast.FuncTypeのときの挙動

ここまでで、探索時は*ast.Ident, ast.BinaryExprのケースのみを紹介しましたが、ast.FuncTypeのときは他とは違うことをしているのでそちらも紹介しておきます。

例えば、下のようなinterfaceがあったときに、これまでの実装だと正しく型セットが表示されなくなります。
いったいなぜでしょうか。

type ng3 interface {
    string | int
    f1 (string) int
}

これは、行数が2行あるのに対してstringとintは一度しか登場していないからです。
そのため、メソッドに関する行はnestに含めないようにする必要があります。
実装は以下の通りになりました。

func (v *Visitor) exprVisitor(expr ast.Expr) {
    switch expr := expr.(type) {
    case *ast.BinaryExpr:
        v.exprVisitor(expr.X)
        v.exprVisitor(expr.Y)
    case *ast.Ident:
        v.identVisitor(expr)
    case *ast.FuncType:
        v.nest--
    // 他の場合が続く
    }
}

このようにすることで、メソッドの行はnestとしてカウントしなくなりました。

intと~intの共通部分

見出しではintとしましたが、これはintに限った話ではないです。
まずはどのような状態を指すか、下の例で確認してください。

package main

import "fmt"

type MyInt int

type i interface {
    int
    ~int
}

func f[T i](val T) {
    fmt.Printf("type: %[1]T, val: %[1]v\n", val)
}

func main() {
    var a int = 5
    var b MyInt = 4

    f(a) // case 1
    f(b) // case 2
}

このようなとき、case 1とcase 2はどちらも動くでしょうか、それともコンパイルエラーになるでしょうか。
playgroundも用意しましたので、動作を確認してみてください。

動かそうとしてみると、case 2がコンパイルエラーになりました。なぜでしょうか。

MyInt does not implement i (possibly missing ~ for int in constraint i)

それは、intと~intの共通部分はintだけになるからです。
MyIntはintではないです。とはいえunderlying typeはintなので、~intだとコンパイルが通ります。

このような状況にも対応できるようにするために、~を持った型が共通部分の処理のときにあったらその元の型の出現回数を+1することにしました。
そうすることで、元の型のみ結果に含まれるようにできました。
この時、元の型がmapに含まれていなければ+1にしないので~を持った型が連続できても処理できます。

type i2 interface { // 結果は~intだけになります
    ~int
    ~int
}

これの処理の実装が以下のようになります。

func (v *Visitor) parseTypeSet() []string {
    // unionの処理は省略します
    typeSet := make(map[string]int)

    // 共通部分の処理
    res := make([]string, 0, len(typeSet))
    // nestからanyの数を引く処理
    if val, ok := typeSet["any"]; ok {
        v.nest -= val
        typeSet["any"] = -1
    }

    // ~を含んでいる型と含んでいない同じ型があった場合の処理 
    for typ := range typeSet {
        if strings.HasPrefix(typ, "~") {
            defaultType := strings.Trim(typ, "~")
            if _, ok := typeSet[defaultType]; ok {
                typeSet[defaultType]++
            }
        }
    }

    for typeName, num := range typeSet {
        if num == v.nest {
            res = append(res, typeName)
        }
    }

    return res
}

anyの処理再び

最後にまたanyの話になります。以下のinterfaceはどのような型セットを持つでしょうか。

type i interface {

}

正解はanyです。なぜならany = interface{}だからです
なので空のinterfaceはanyとして処理する必要があります。
現在は以下のように明示的にFieldの存在しないinterfaceをanyとすることにしています。

func (v *Visitor) interfaceVisitor(expr *ast.InterfaceType) {
        //メソッドのリストを持たないものはanyとして処理
	if expr.Methods.List == nil {
		v.nest++
		v.typeResults[v.nest] = append(v.typeResults[v.nest], ANY)
	}

	for _, field := range expr.Methods.List {
		v.nest++
		v.exprVisitor(field.Type)
	}
}

実装のまとめ

ここまでで、型セットの探索からunionと共通部分の処理までをかいつまんで説明しました。
実際のコードでは、もう少し複雑でメソッドの処理や標準出力への表示の部分もありますので、興味がありましたら覗いてみてください。

対応中のところ

ここでは対応したいけどまだ対応できていないところについて書いていきます。

anyとempty setの区別

先ほどのanyの話につながるのですが、anyとempty type setの区別が現段階だとできていないです。
下の例を見てください。

type anyInterface interface{}

type emptyInterface interface {
    string
    int
}

anyInterfaceはanyを持ちますが、emptyInterfaceはstringとintの共通部分がないのでempty type setになります。
これは、type setの探索結果がなにもないものはanyを満たすとすれば解決できると思うのですぐに対応できると思います。
この対応をすれば上のnilだったときに明示的にanyにする必要がないかもしれません。

(追記: 2022/6/26)
この件はすでに対応しました。

`ast.Ident`の`Object`は今後非推奨になる

詳しくはこの記事では説明していないですが、ast.Identの探索の際にユーザー定義型かinterfaceなのか、それとも組み込み型なのかの判定をast.Objectを使って確かめています。
しかし、こちらはそのうち非推奨になるということを聞きました。

同じようなことをtypesパッケージでできるとのことらしいのでそちらに変更できないか模索してみます。
go/x/exp/typeparamsの方はtypesで型セットの処理を行っているのでtypesを使うようにすると、同じような実装になるような気がしています。

おわりに

tslistはgenericsの型制約を表示するのに役立ちます。ぜひ使ってみてください。
そして、この記事は型セットの理解が深まるものになったのではないかなと思います。
静的解析の面白さも伝わったていたらうれしいです。

また、genericsの仕組みは今後若干変わるかもしれない(メソッドが型パラメータ持つとか)のでその時々で柔軟に対応できたらなと思っています。

genericsの型制約をinterfaceで定義しているパッケージがgolang.org/x/exp/constrainsぐらいしか思いつかず、それと自分で考えたテストケースのみをテスト対象にして実装しているため、コーナーケースやうまくいかない場合もあると思います。
その時はissueを立てていただけるとすごい助かります。

Discussion