[インデックス 16321] ファイルの概要

このコミットは、Go言語の標準ライブラリである reflect パッケージ内の deepequal.go ファイルに対する変更です。reflect.DeepEqual 関数は、Goのデータ構造の深い比較を行うための重要な機能であり、このコミットはその内部実装、特に循環参照の検出メカニズムを改善することを目的としています。

コミット

commit f7b5a01999a7bf9f84ee53768a42980804bef85f
Author: Robert Hencke <robert.hencke@gmail.com>
Date:   Wed May 15 14:50:57 2013 -0700

    reflect: use visit structure for map key in DeepEqual
    
    R=golang-dev, bradfitz, jonathan, r
    CC=golang-dev
    https://golang.org/cl/8730044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/f7b5a01999a7bf9f84ee53768a42980804bef85f

元コミット内容

このコミットは、Go言語の reflect パッケージにおける DeepEqual 関数の実装において、循環参照を検出するために使用される「訪問済み」マップのキーとして、visit 構造体自体を使用するように変更するものです。これにより、以前のアドレスに基づくハッシュ値とリンクリストを用いた方法から、より堅牢で効率的な構造体キーによる比較へと改善されます。

変更の背景

reflect.DeepEqual 関数は、Goの任意の2つの値が「深い」意味で等しいかどうかを再帰的に比較します。この比較処理において、ポインタやマップ、スライスなどの参照型が循環参照（例えば、AがBを参照し、BがAを参照するような構造）を持っている場合、無限ループに陥る可能性があります。これを防ぐため、DeepEqual は既に比較中のペアを記録するメカニズム（「訪問済み」マップ）を持っています。

変更前の実装では、この「訪問済み」マップのキーとして uintptr 型（ポインタの整数表現）のアドレスのハッシュ値が使用されていました。具体的には、17*addr1 + addr2 のような計算でハッシュ値を生成し、そのハッシュ値をキーとして map[uintptr]*visit に visit 構造体のポインタを格納していました。しかし、この方法にはいくつかの課題がありました。

1. ハッシュ衝突の可能性: 異なるポインタペアが同じハッシュ値を生成する「ハッシュ衝突」が発生する可能性があります。この場合、衝突解決のために visit 構造体内の next フィールドを使ったリンクリストを辿る必要があり、パフォーマンスのオーバーヘッドがありました。
2. 型情報の欠如: uintptr は単なるメモリアドレスの数値表現であり、そのアドレスが指すオブジェクトの型情報を含みません。DeepEqual は型が異なるオブジェクトは等しくないと判断するため、アドレスが同じでも型が異なる場合に誤って同一視してしまうリスクがありました（ただし、DeepEqual のロジック自体は型チェックを最初に行うため、このリスクは限定的ですが、visited マップのキーとしての精度が低いという問題は残ります）。

このコミットは、これらの課題を解決するために、visit 構造体自体をマップのキーとして使用するように変更しました。Go言語では、すべてのフィールドが比較可能な構造体はマップのキーとして使用でき、その比較はフィールドごとの深い比較によって行われます。これにより、アドレス (a1, a2) と型 (typ) の両方が一致する場合にのみキーが等しいと判断されるため、より正確な「訪問済み」の検出が可能になります。また、マップ自体がキーのユニーク性を保証するため、リンクリストによる衝突解決が不要になり、コードが簡潔化され、パフォーマンスも向上します。

前提知識の解説

Go言語の reflect パッケージ

reflect パッケージは、Goプログラムが実行時に自身の構造を検査・操作するための機能を提供します。これにより、型情報、フィールド、メソッドなどにアクセスしたり、動的に値を操作したりすることが可能になります。reflect.DeepEqual はこのパッケージの主要な関数の一つで、2つの値が「深い」意味で等しいかを再帰的に比較します。これは、単なる == 演算子では比較できない複雑なデータ構造（スライス、マップ、構造体など）の内容を比較する際に不可欠です。

DeepEqual と循環参照

DeepEqual のような再帰的な比較関数では、データ構造内に循環参照（例: a -> b -> a）が存在すると、無限ループに陥る危険性があります。これを回避するため、DeepEqual は比較中の値のペアを記録する「訪問済み」マップ（visited）を使用します。もし、現在比較しようとしているペアが既に「訪問済み」マップに存在する場合、それは循環参照の一部であると判断し、そのペアは等しいとみなして比較を終了します。これにより、無限ループを防ぎ、比較処理を正常に完了させることができます。

Go言語における map のキー

Go言語の map（ハッシュマップ）は、キーと値のペアを格納するデータ構造です。マップのキーとして使用できる型は「比較可能 (comparable)」である必要があります。比較可能な型とは、== 演算子や != 演算子で比較できる型のことです。

• 比較可能な組み込み型: bool, 数値型 (int, float64, complex128 など), string, ポインタ型, チャネル型, インターフェース型（動的な値が比較可能な場合）。
• 比較可能な複合型:
  • 配列: 要素の型が比較可能であれば、配列も比較可能です。要素がすべて等しい場合に配列も等しいとみなされます。
  • 構造体: すべてのフィールドが比較可能であれば、構造体も比較可能です。すべてのフィールドがそれぞれ等しい場合に構造体も等しいとみなされます。
• 比較不可能な型: スライス、マップ、関数は比較不可能な型であり、マップのキーとして直接使用することはできません。これらの型をキーとして使用したい場合は、カスタムのハッシュ関数や、それらを一意に識別できる別の表現（例: JSON文字列化）を考案する必要があります。

このコミットでは、visit 構造体のすべてのフィールド（uintptr と Type）が比較可能であるため、visit 構造体自体をマップのキーとして使用することが可能になります。

uintptr

uintptr は、Go言語におけるポインタの整数表現です。これは、ポインタの値を整数として扱うことができる型ですが、Goのガベージコレクタの対象外であり、型情報も持ちません。unsafe.Pointer との間で相互変換が可能ですが、uintptr を直接操作することはGoの型安全性を損なうため、非常に注意が必要です。以前の実装では、この uintptr を使ってポインタのアドレスを数値として扱い、ハッシュ値を生成していました。

visit 構造体

visit 構造体は、DeepEqual が循環参照を検出するために使用する内部構造体です。この構造体は、比較中の2つの値のメモリアドレス (a1, a2) とその型 (typ) を保持します。これにより、どの値のペアが既に比較されたかを識別します。

技術的詳細

このコミットの核心は、reflect.DeepEqual 関数内で使用される visited マップのキーの型を uintptr から visit 構造体自体に変更した点にあります。

変更前:

type visit struct {
	a1   uintptr
	a2   uintptr
	typ  Type
	next *visit // リンクリストのためのポインタ
}

// visited map の型: map[uintptr]*visit
func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
    // ...
    // ハッシュ値を計算
    h := 17*addr1 + addr2
    seen := visited[h] // ハッシュ値でマップを検索

    // リンクリストを辿って衝突解決
    for p := seen; p != nil; p = p.next {
        if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
            return true // 既に訪問済み
        }
    }

    // 新しい visit エントリを作成し、リンクリストの先頭に追加
    visited[h] = &visit{addr1, addr2, typ, seen}
    // ...
}

変更前の実装では、a1 と a2 のアドレスから計算された uintptr のハッシュ値 h をマップのキーとしていました。しかし、異なる (a1, a2, typ) の組み合わせが同じ h を生成するハッシュ衝突の可能性がありました。このため、マップから seen を取得した後、seen が指す visit 構造体のリンクリストを next フィールドを使って辿り、実際に a1, a2, typ の全てが一致するエントリがあるかを確認する必要がありました。これは、衝突が多い場合にパフォーマンスのボトルネックとなる可能性がありました。

変更後:

type visit struct {
	a1  uintptr
	a2  uintptr
	typ Type
	// next *visit フィールドが削除された
}

// visited map の型: map[visit]bool
func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool {
    // ...
    v := visit{addr1, addr2, typ} // visit 構造体を作成
    if visited[v] {              // visit 構造体自体をキーとしてマップを検索
        return true              // 既に訪問済み
    }

    visited[v] = true // visit 構造体自体をキーとしてマップに登録
    // ...
}

変更後では、visit 構造体から next *visit フィールドが削除されました。これは、visit 構造体自体をマップのキーとして使用することで、Go言語のマップが提供するキーの比較メカニズムが利用できるようになったためです。Goのマップは、構造体をキーとして使用する場合、その構造体のすべてのフィールドが比較可能であれば、フィールドごとの比較（a1 == v.a1 && a2 == v.a2 && typ == v.typ）を自動的に行い、キーの等価性を判断します。

この変更により、以下の利点が得られます。

1. 正確性の向上: uintptr のハッシュ値ではなく、visit 構造体（アドレスと型情報を含む）自体をキーとすることで、より正確な「訪問済み」の検出が可能になります。ハッシュ衝突による誤判定のリスクがなくなります。
2. コードの簡潔化: リンクリストを辿るための複雑なループ処理が不要になり、コードが大幅に簡潔になりました。
3. パフォーマンスの改善: リンクリストの走査が不要になったことで、マップのルックアップがより直接的になり、パフォーマンスが向上する可能性があります。

コアとなるコードの変更箇所

src/pkg/reflect/deepequal.go ファイルにおいて、以下の変更が行われました。

1. visit 構造体の定義変更:

   --- a/src/pkg/reflect/deepequal.go
   +++ b/src/pkg/reflect/deepequal.go
   @@ -9,18 +9,17 @@ package reflect
    // During deepValueEqual, must keep track of checks that are
    // in progress.  The comparison algorithm assumes that all
    // checks in progress are true when it reencounters them.
   -// Visited are stored in a map indexed by 17 * a1 + a2;
   +// Visited comparisons are stored in a map indexed by visit.
    type visit struct {
   -	a1   uintptr
   -	a2   uintptr
   -	typ  Type
   -	next *visit
   +	a1  uintptr
   +	a2  uintptr
   +	typ Type
    }
   

   next *visit フィールドが削除されました。

2. deepValueEqual 関数のシグネチャ変更:

   --- a/src/pkg/reflect/deepequal.go
   +++ b/src/pkg/reflect/deepequal.go
   @@ -9,18 +9,17 @@ package reflect
    // During deepValueEqual, must keep track of checks that are
    // in progress.  The comparison algorithm assumes that all
    // checks in progress are true when it reencounters them.
   -// Visited are stored in a map indexed by 17 * a1 + a2;
   +// Visited comparisons are stored in a map indexed by visit.
    type visit struct {
   -	a1   uintptr
   -	a2   uintptr
   -	typ  Type
   -	next *visit
   +	a1  uintptr
   +	a2  uintptr
   +	typ Type
    }
    
    // Tests for deep equality using reflected types. The map argument tracks
    // comparisons that have already been seen, which allows short circuiting on
    // recursive types.
   -func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
   +func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool {
    	if !v1.IsValid() || !v2.IsValid() {
    		return v1.IsValid() == v2.IsValid()
    	}
   

   visited 引数の型が map[uintptr]*visit から map[visit]bool に変更されました。戻り値の型も (b bool) から bool に変更されています。

3. deepValueEqual 関数内の visited マップ操作ロジックの変更:

   --- a/src/pkg/reflect/deepequal.go
   +++ b/src/pkg/reflect/deepequal.go
   @@ -44,17 +43,14 @@ func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool
    		}\n \n     		// ... or already seen
   -		h := 17*addr1 + addr2
   -		seen := visited[h]
    		typ := v1.Type()
   -		for p := seen; p != nil; p = p.next {
   -			if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
   -				return true
   -			}
   +		v := visit{addr1, addr2, typ}
   +		if visited[v] {
   +			return true
    		}
    
    		// Remember for later.
   -		visited[h] = &visit{addr1, addr2, typ, seen}
   +		visited[v] = true
    	}
    
    	switch v1.Kind() {
   

   ハッシュ値 h の計算と、リンクリストを辿る for ループが削除され、代わりに visit 構造体 v を直接マップのキーとして使用するようになりました。

4. DeepEqual 関数内の make 関数の引数変更:

   --- a/src/pkg/reflect/deepequal.go
   +++ b/src/pkg/reflect/deepequal.go
   @@ -135,5 +131,5 @@ func DeepEqual(a1, a2 interface{}) bool {\n     	if v1.Type() != v2.Type() {\n     		return false\n     	}\n    -	return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)\n    +	return deepValueEqual(v1, v2, make(map[visit]bool), 0)\n     }
   

   deepValueEqual を呼び出す際の visited マップの初期化が、make(map[uintptr]*visit) から make(map[visit]bool) に変更されました。

コアとなるコードの解説

このコミットの主要な変更は、reflect.DeepEqual 関数が循環参照を検出するために使用する visited マップのキーの戦略を根本的に変更したことです。

変更前 (map[uintptr]*visit を使用):

1. visit 構造体は、a1 (最初の値のアドレス), a2 (2番目の値のアドレス), typ (値の型), そして next (リンクリストの次の要素へのポインタ) を持っていました。
2. deepValueEqual 関数内で、addr1 と addr2 から h := 17*addr1 + addr2 という単純なハッシュ値を計算していました。
3. この h をキーとして visited マップから seen := visited[h] を取得していました。
4. もし seen が存在した場合、それはハッシュ衝突の可能性があるため、for p := seen; p != nil; p = p.next ループを使って、p.a1 == addr1 && p.a2 == addr2 && p.typ == typ が真となる visit エントリがリンクリスト内に存在するかを線形探索していました。この線形探索は、衝突が多い場合にパフォーマンスを低下させる要因でした。
5. 新しいペアをマップに追加する際は、visited[h] = &visit{addr1, addr2, typ, seen} のように、新しい visit エントリをリンクリストの先頭に追加していました。

変更後 (map[visit]bool を使用):

1. visit 構造体から next *visit フィールドが削除されました。これにより、visit 構造体は a1, a2, typ の3つのフィールドのみを持つ、完全に比較可能な構造体となりました。
2. deepValueEqual 関数内で、比較対象の addr1, addr2, typ を使って v := visit{addr1, addr2, typ} という新しい visit 構造体を直接作成します。
3. この v 構造体自体をキーとして if visited[v] のようにマップを検索します。Goのマップは、構造体をキーとして使用する場合、その構造体のすべてのフィールド（この場合は a1, a2, typ）が等しい場合にのみキーが等しいと判断します。これにより、ハッシュ衝突の心配なく、正確なキーの比較が行われます。
4. 新しいペアをマップに追加する際は、visited[v] = true のように、visit 構造体自体をキーとしてマップに登録します。値は bool 型で、単に「訪問済みである」ことを示すために true を格納します。

この変更により、DeepEqual の循環参照検出ロジックは、よりGoのマップの特性を活かした、効率的かつ堅牢な実装へと進化しました。リンクリストの線形探索が不要になったことで、コードの複雑性が減り、パフォーマンスも向上しました。

関連リンク

• Go CL (Code Review) 8730044: https://golang.org/cl/8730044

参考にした情報源リンク

• Go reflect.DeepEqual cycle detection: https://go.dev/blog/deep-equal (Go公式ブログのDeepEqualに関する記事、循環参照の扱いについて言及)
• Go struct as map key: https://go.dev/blog/maps (Go公式ブログのマップに関する記事、構造体をキーとして使用できる条件について言及)
• Go map key equality for structs: https://go.dev/ref/spec#Map_types (Go言語仕様のマップ型に関する記述、キーの等価性について言及)
• Go uintptr hashing: https://pkg.go.dev/unsafe (Goのunsafeパッケージドキュメント、uintptrの性質について言及)