Go 型チェッカー深掘り: type construction と cycle detection¶

このテーマの狙い¶

Type Construction and Cycle Detection を、登壇向けに噛み砕く。

話の中心はこれ。

Go の型チェッカーは、なぜ「許される再帰」と「壊れる循環」を区別しなければならないのか。

このテーマは errors より難しい。ただし、既存の errors 発表とは被りにくく、Go の内部実装の面白さを出しやすい。

被り回避の注意¶

Go 1.26 の再帰的型制約 を主題にすると、既存の発表と被りやすい。

差別化するなら、以下を主役にする。

type construction
complete / incomplete type
deconstruction
incomplete value
unsafe.Sizeof(T{})
cycle detection

つまり、F-bounded polymorphism の話ではなく、型チェッカーが内部で何を保証しているかを話す。

まず押さえる背景¶

Go 1.26 release notes では、generic type が型パラメータリスト内で自分自身を参照する制限が外れた。

type Adder[A Adder[A]] interface {
    Add(A) A
}

func algo[A Adder[A]](x, y A) A {
    return x.Add(y)
}

以前は Adder[A Adder[A]] の自己参照が禁止されていた。 Go 1.26 では、型チェッカー側が扱えるようになったため、仕様上の制限も外れた。

ただし、この発表ではそこを入口にして、より根本の「型構築と循環検出」に降りる。

type construction とは何か¶

Go のコンパイルでは、まずソースコードが AST になる。その AST を型チェッカーが読み、各型の内部表現を作る。

この内部表現を作る作業が type construction。

単純な例。

type T []U
type U *int

型チェッカーの目線では、だいたいこうなる。

T を作る
  -> T の underlying type は []U
    -> []U を作る
      -> 要素型 U を作る
        -> U の underlying type は *int
          -> *int を作る
            -> int は predeclared type なので既にある

ここでは依存関係を下までたどり、下から完成させればよい。

complete type と deconstruction¶

ブログで重要なのは、型が「complete」かどうか。

ここでは雑にこう理解する。

complete type:
  内部表現のフィールドが埋まっていて、安全に中身を覗ける型

incomplete type:
  まだ構築中で、underlying type などが確定していない型

型の中身を覗くことを、ブログでは deconstruction と呼んでいる。

例えば、map key が comparable かを調べるには、型の underlying type を見る必要がある。これは deconstruction。

complete でない型を deconstruct すると、まだ埋まっていない情報を読むことになる。だから危険。

許される再帰型¶

Go には再帰型がある。

type Node struct {
    next *Node
}

もう少し型構築の流れが見えやすい例。

type T []U
type U *T

U の underlying type は *T。ここで T はまだ構築中かもしれない。

しかし *T は「T を指すポインタ型」なので、T の中身を今すぐ全部覗かなくても作れる。

T を作る
  -> []U が必要
    -> U が必要
      -> *T が必要
        -> T は未完成だが、ポインタの base として参照できる

この場合、未完成の T を指しておき、あとで T が完成すればループ全体も成立する。

ここでのポイント。

未完成型を「参照する」ことはできる場合がある。
しかし未完成型を「覗く」ことはできない。

この区別が核心。

壊れる循環: `unsafe.Sizeof(T{})`¶

次の例は invalid。

type T [unsafe.Sizeof(T{})]int

一見すると、これもただ T が自分自身を参照しているだけに見える。しかし実際には違う。

配列型は長さが型の一部。つまり T を作るには、配列長が必要。

配列長は unsafe.Sizeof(T{})。 T{} のサイズを知るには、T の中身を見なければならない。

依存関係はこうなる。

T を完成させたい
  -> T は配列型
    -> 配列長が必要
      -> unsafe.Sizeof(T{}) が必要
        -> T{} のサイズが必要
          -> T の中身を deconstruct する必要がある
            -> T が完成している必要がある

つまり、T を完成させるために T の完成が必要になる。これは解けない。

`new(T)` ならなぜ大丈夫なのか¶

ブログで面白い対比がこれ。

type T [unsafe.Sizeof(new(T))]int

これは sound とされている。

理由は、new(T) の型が *T だから。ポインタのサイズは、指している T の中身を見なくても分かる。

unsafe.Sizeof(T{})
  -> T そのもののサイズが必要
  -> T の中身を見る必要がある
  -> 未完成ならアウト

unsafe.Sizeof(new(T))
  -> *T のサイズが必要
  -> ポインタサイズだけ分かればよい
  -> T の中身を見なくてよい

この差分は発表でかなり使える。

incomplete value¶

ブログの肝は「incomplete type」だけでなく「incomplete value」。

T{} は composite literal なので、結果の値は型 T を持つ。しかしその時点で T が未完成なら、T{} は incomplete value。

この incomplete value を後続の式が消費するとき、型の中身を覗く操作が必要になると壊れる。

例。

type T [unsafe.Sizeof(T{}[0])]int

T{}[0] は index operation。 index するには、T が配列なのか、スライスなのか、文字列なのかを知る必要がある。つまり T の underlying type を見る。

未完成の T を deconstruct するのでアウト。

upstream と downstream¶

ブログでは、incomplete value を作る側と消費する側を分けて考えている。

upstream:
  incomplete value を生み出す式

downstream:
  incomplete value を消費し、型の中身を覗く可能性がある式

downstream の例は多い。

unsafe.Sizeof(T{})
T{}[0]
T{}[:]
f(T{})

しかし downstream 側を全部網羅して検出するのは大変。そこで Go 1.26 の改善では、incomplete value が生まれる upstream 側で止める。

ブログに出てくる upstream 例。

type T [unsafe.Sizeof(T(42))]int                // conversion
func f() T
type T [unsafe.Sizeof(f())]int                  // function call

var i interface{}
type T [unsafe.Sizeof(i.(T))]int                // assertion

type T [unsafe.Sizeof(<-(make(<-chan T)))]int   // channel receive

type T [unsafe.Sizeof(make(map[int]T)[42])]int  // map access

type T [unsafe.Sizeof(*new(T))]int              // dereference

型チェッカーは、こうした式で結果の型が分かった時点で、その型が complete かを確認する。

if !isComplete(T) {
    reportCycleErr(T)
    return invalid
}

不完全な値を downstream に流さず、上流で invalid にする。これにより、後段で panic するのではなく、cycle error として報告できる。

なぜ Go 1.26 で重要なのか¶

ブログの結論は、Go 1.26 で type construction のアルゴリズムが単純化され、cycle detection が系統的になったこと。

以前は、個別の cycle detection ロジックが複雑で、いくつかの特殊ケースで compiler / go/types が panic したり、誤った結果を出したりしていた。

発表での伝え方¶

いきなり go/types の実装に入ると厳しい。次の順番がよい。

1. Go は再帰型を許す¶

type Node struct {
    next *Node
}

ここで「再帰しているから全部ダメ」ではないことを示す。

2. `*T` は中身を覗かなくてよい¶

type T []U
type U *T

未完成の T をポインタの base として参照するだけなら、あとで完成できる。

3. `T{}` は値なので中身が必要になる¶

type T [unsafe.Sizeof(T{})]int

配列長を決めるために T のサイズが必要。これは未完成の T を deconstruct するのでアウト。

4. `new(T)` との比較で直感を作る¶

type T [unsafe.Sizeof(new(T))]int

*T のサイズだけなら T の中身を見なくてよい。

5. incomplete value を upstream で止める¶

T{} のような不完全な値を downstream に流すと、いろいろな演算子で壊れる。だから生まれた時点で complete check する。

10分構成案¶

導入: Go 1.26 の型チェッカー改善はユーザーからは地味だが、内部的には重要
型チェッカーは AST から型の内部表現を作る
type construction は依存関係を depth-first にたどる
complete type と incomplete type
許される再帰: type T []U; type U *T
壊れる循環: type T [unsafe.Sizeof(T{})]int
T{} と new(T) の差分
incomplete value / upstream / downstream
Go 1.26 では upstream で complete check して cycle error にする
まとめ: 難しさは文法ではなく、未完成型をいつ覗いてよいかの不変条件にある

タイトル案¶

Go の型チェッカーはなぜ循環参照で壊れるのか
type T [unsafe.Sizeof(T{})]int から読む Go の型構築
Go の再帰型はなぜ許され、なぜ壊れるのか

このテーマの難易度¶

難しい。

理由は、Go の表面文法ではなく型チェッカー内部の状態管理を説明する必要があるから。

押さえるべき概念:

AST
defined type
underlying type
complete / incomplete type
deconstruction
recursive type
array length is part of type
incomplete value
cycle detection

ただし、T{} と new(T) の差分まで落とせば、聞き手にも直感が残る。