Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語のreflectパッケージにDeepEqual関数を追加するものです。DeepEqualは、Goの組み込みの==演算子では比較できない複雑なデータ構造（構造体、配列、スライス、ポインタなど）について、その内容が再帰的に等しいかどうかを判定するための機能を提供します。これにより、開発者はオブジェクトの深い比較を簡単に行えるようになります。

コミット

commit c4ad4f9fcfd69556f09928aa24fc110d5b3aa2d9
Author: Daniel Nadasi <dnadasi@google.com>
Date:   Wed Apr 1 22:20:18 2009 -0700

    Add a DeepEqual function to the reflect package
    
    R=r,rsc
    APPROVED=rsc
    DELTA=167  (166 added, 0 deleted, 1 changed)
    OCL=26982
    CL=27017
---
 src/lib/reflect/Makefile     |  3 +-\n src/lib/reflect/all_test.go  | 88 ++++++++++++++++++++++++++++++++++++++++++++\n src/lib/reflect/deepequal.go | 78 +++++++++++++++++++++++++++++++++++++++\n 3 files changed, 168 insertions(+), 1 deletion(-)

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

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

元コミット内容

reflectパッケージにDeepEqual関数を追加します。

変更の背景

Go言語において、プリミティブ型（整数、浮動小数点数、文字列など）やポインタ、チャネル、関数、インターフェースの値の比較には==演算子を使用できます。しかし、構造体、配列、スライス、マップといった複合型の場合、==演算子は常に「値の等価性」を意味するわけではありません。

  • 構造体: 全てのフィールドが比較可能であれば、フィールドごとの値が等しい場合にtrueを返します。
  • 配列: 要素の型が比較可能であれば、全ての要素が等しい場合にtrueを返します。
  • スライス: ==演算子はスライスヘッダ（ポインタ、長さ、容量）のみを比較し、参照している基底配列の内容は比較しません。異なるスライスが同じ内容を持っていても、==はfalseを返すことがあります。
  • マップ: ==演算子はマップに対して定義されていません。マップは参照型であり、内容の比較はできません。

このような背景から、Goの標準ライブラリには、複合型の「内容」が再帰的に等しいかどうかを判定する汎用的なメカニズムが求められていました。特に、テストコードで期待される出力と実際の結果を比較する際や、キャッシュのキーとして複雑な構造体を使用する際などに、この「ディープイコール」の機能は不可欠です。このコミットは、そのニーズに応えるためにreflectパッケージにDeepEqual関数を導入しました。

前提知識の解説

Goのreflectパッケージ

Go言語のreflectパッケージは、プログラムの実行時に変数や型の情報を検査・操作するための機能を提供します。これにより、Goの静的型付けの制約を受けずに、動的な型操作や汎用的なデータ処理が可能になります。

  • reflect.Type: Goの型そのものを表すインターフェースです。型の名前、基底型、メソッドなどの情報を提供します。
  • reflect.Value: Goの変数の値を表す構造体です。値の型情報（Type）と、その実際のデータを含みます。Valueを通じて、変数の値を読み取ったり、（エクスポートされたフィールドであれば）変更したりできます。
  • reflect.Kind: reflect.Valueが持つ値の「種類」を表す定数です。例えば、Int, String, Struct, Array, Slice, Map, Ptr, Interfaceなどがあります。DeepEqual関数は、このKindを利用して、比較対象の型に応じた適切な比較ロジックを適用します。
  • reflect.NewValue(interface{}): 任意のGoの値をreflect.Value型に変換する関数です。DeepEqual関数はこの関数を使って、比較対象のinterface{}型の引数をreflect.Valueに変換し、リフレクションによる比較を可能にします。
  • reflect.Value.Addr(): Valueが指す値のアドレスを返します。ポインタやスライス、マップなどの参照型を比較する際に、循環参照を検出するために利用されます。

Goにおける等価性（Equality）

Goにおける等価性（Equality）は、型によってその振る舞いが異なります。

  • プリミティブ型（数値、文字列、真偽値）: 値が完全に一致すればtrue。
  • ポインタ: 2つのポインタが同じメモリ位置を指していればtrue。
  • インターフェース: 内部の型と値が両方とも等しければtrue。
  • 構造体: 全てのフィールドが比較可能であり、かつ全てのフィールドの値が等しければtrue。
  • 配列: 要素の型が比較可能であり、かつ全ての要素の値が等しければtrue。
  • スライス: ==演算子はスライスヘッダ（ポインタ、長さ、容量）のみを比較します。内容の比較は行いません。
  • マップ: ==演算子はマップに対して定義されていません。マップは参照型であり、内容の比較はできません。
  • 関数: 2つの関数が同じ関数を指していればtrue。

DeepEqualは、これらの組み込みの==演算子の限界を補い、特にスライスやマップ、そして再帰的な構造体など、複雑なデータ構造の「内容」が等しいかどうかを判定するために導入されました。

再帰的なデータ構造の比較

再帰的なデータ構造とは、自身または自身を含む別の型への参照（ポインタ）を持つ構造体のことです。例えば、リンクリストのノードやツリー構造のノードなどがこれに該当します。

type Node struct {
    Value int
    Next  *Node
}

このような構造体を比較する際、単純にフィールドを再帰的に比較していくと、循環参照（AがBを参照し、BがAを参照するような状況）が発生した場合に無限ループに陥る可能性があります。

DeepEqual関数は、この無限ループを避けるために「visitedマップ」というメカニズムを使用します。これは、既に比較済みのオブジェクトのペアを記録しておくことで、同じペアが再度比較されそうになったときに、それが循環参照であることを検出し、比較をスキップして無限ループを防ぐためのものです。

技術的詳細

DeepEqual関数は、Goのreflectパッケージを駆使して、任意の2つのGoの値が「深く」等しいかどうかを判定します。その核心は、内部で呼び出されるdeepValueEqual関数にあります。

DeepEqual関数の役割

DeepEqual(a1, a2 interface{}) boolは、ユーザーが直接呼び出すエントリポイントです。この関数は、比較したい任意の2つの値をinterface{}として受け取り、それらをreflect.Value型に変換した後、deepValueEqual関数に渡します。また、deepValueEqualが循環参照を検出するために使用するvisitedマップを初期化して渡します。

deepValueEqual関数の役割と実装

deepValueEqual(v1, v2 Value, visited map[Addr]Addr) boolが、実際の再帰的な比較ロジックを担います。

  1. 型の種類（Kind）のチェック: まず、v1.Kind() != v2.Kind()で、2つの値の基本的な型が異なる場合は即座にfalseを返します。例えば、intとfloat32は値が同じでも型が異なるため、DeepEqualでは等しくないと判断されます。

  2. 参照の同一性チェックとvisitedマップによる再帰検出:

    • addr1 := v1.Addr()とaddr2 := v2.Addr()で、それぞれのValueが指すメモリ上のアドレスを取得します。Addrはreflectパッケージ内の非公開型ですが、ここではメモリ上の位置を一意に識別するためのものと理解できます。
    • if addr1 == addr2 { return true }: もし2つの値が全く同じメモリ位置を指している（つまり、同じオブジェクトである）ならば、それらは深く等しいと判断し、trueを返して比較を終了します。これは最適化であり、循環参照の検出にも役立ちます。
    • if vaddr, ok := visited[addr1]; ok && vaddr == addr2 { return true }: visitedマップは、既に比較を開始したValueのアドレスペアを記録しています。もしaddr1が既にvisitedマップのキーとして存在し、その値がaddr2と一致するならば、それは現在比較中のパスで既にこのペアが比較されたことを意味します。これは循環参照を検出したことを示し、無限ループを避けるためにtrueを返して比較を終了します。
    • visited[addr1] = addr2: 現在比較しているaddr1とaddr2のペアをvisitedマップに記録します。これにより、後続の再帰呼び出しで同じペアが検出された場合に、上記のチェックで無限ループを回避できます。

  3. switch v1.Kind()による各型ごとの比較ロジック: 値のKindに応じて、異なる比較戦略が適用されます。

    • ArrayKind (配列):

      • arr1.IsSlice() != arr2.IsSlice(): スライスであるかどうかが異なる場合はfalse。
      • arr1.Len() != arr2.Len(): 長さが異なる場合はfalse。
      • for i := 0; i < arr1.Len(); i++ { if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited) { return false } }: 配列の各要素を再帰的にdeepValueEqualで比較します。一つでも等しくない要素があればfalseを返します。

    • InterfaceKind (インターフェース):

      • deepValueEqual(NewValue(v1.(InterfaceValue).Get()), NewValue(v2.(InterfaceValue).Get()), visited): インターフェースが保持する実際の値を取り出し、それらをreflect.Valueに変換して再帰的に比較します。

    • MapKind (マップ):

      • return v1.Interface() == v2.Interface(): このコミット時点では、マップの深い比較はまだ実装されていません。 TODO(dnadasi): Implement this fully once MapValue is implementedというコメントがあり、マップの比較は==演算子による同一性（同じマップオブジェクトであるか）のみで行われています。これは、当時のreflectパッケージがMapValueを完全にサポートしていなかったためです。

    • PtrKind (ポインタ):

      • return deepValueEqual(v1.(PtrValue).Sub(), v2.(PtrValue).Sub(), visited): ポインタが指す先の値（サブエレメント）を再帰的にdeepValueEqualで比較します。

    • StructKind (構造体):

      • struct1.Len() != struct2.Len(): フィールドの数が異なる場合はfalse。
      • for i := 0; i < struct1.Len(); i++ { if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited) { return false } }: 構造体の各フィールドを再帰的にdeepValueEqualで比較します。一つでも等しくないフィールドがあればfalseを返します。

    • default (その他の型):

      • return v1.Interface() == v2.Interface(): 上記の複合型以外の型（プリミティブ型、チャネル、関数など）については、Goの組み込みの==演算子による比較で十分であるため、Interface()メソッドで実際の値を取り出し、直接比較します。

テストケースの分析 (all_test.go)

all_test.goに追加されたテストケースは、DeepEqual関数の様々な挙動を検証しています。

  • DeepEqualTest構造体とdeepEqualTestsスライス:

    • a, b interface{}: 比較対象の2つの値。
    • eq bool: 期待される比較結果（trueまたはfalse）。
    • このスライスには、整数、浮動小数点数、文字列、スライス、配列、構造体など、様々な型の等しいケースと等しくないケースが含まれています。
    • 特に、make([]int, 10)とmake([]int, 10)のように、異なるメモリ位置に存在するが内容が等しいスライスがtrueになること、1と1.0のように値は同じでも型が異なる場合はfalseになることなどがテストされています。

  • TestDeepEqualRecursiveStruct:

    • 再帰的な構造体Recursive（自身へのポインタを持つ）の比較をテストします。
    • *a = Recursive{ 12, a }のように、構造体自身を指すポインタを持つインスタンスを作成し、DeepEqualが無限ループに陥らずに正しく比較できることを検証します。

  • TestDeepEqualComplexStruct:

    • より複雑な構造体Complex（配列、ポインタ、マップ、自身へのポインタを持つ）の比較をテストします。
    • *a = Complex{5, [3]*Complex{a, b, a}, &stra, m}のように、複数の参照や再帰的な参照を含む構造体を構築し、DeepEqualが正しく等価性を判定できることを検証します。

  • TestDeepEqualComplexStructInequality:

    • TestDeepEqualComplexStructと同様の複雑な構造体で、意図的にわずかな違い（文字列straとstrb）を導入し、DeepEqualが正しくfalseを返すことを検証します。

これらのテストケースは、DeepEqualがプリミティブ型から複雑な再帰的構造体まで、幅広いシナリオで期待通りに動作することを保証するために重要です。

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

src/lib/reflect/Makefile

--- a/src/lib/reflect/Makefile
+++ b/src/lib/reflect/Makefile
@@ -40,6 +40,7 @@ O2=\
 
 O3=\
 	tostring.$O\
+	deepequal.$O\
 
 reflect.a: a1 a2 a3
 
@@ -52,7 +53,7 @@ a2:	$(O2)
 	rm -f $(O2)
 
 a3:	$(O3)
-	$(AR) grc reflect.a tostring.$O
+	$(AR) grc reflect.a tostring.$O deepequal.$O
 	rm -f $(O3)
 
 newpkg: clean

src/lib/reflect/all_test.go

--- a/src/lib/reflect/all_test.go
+++ b/src/lib/reflect/all_test.go
@@ -356,3 +356,91 @@ func TestBigStruct(t *testing.T) {
 		t.Errorf("NewValue(%v).Interface().(big) = %v", b, b1);
 	}
 }
+
+type Basic struct {
+	x int;
+	y float32
+}
+
+type Recursive struct {
+	x int;
+	r *Recursive
+}
+
+type Complex struct {
+	a int;
+	b [3]*Complex;
+	c *string;
+	d map[float]float
+}
+
+type DeepEqualTest struct {
+	a, b interface{};
+	eq bool;
+}
+
+var deepEqualTests = []DeepEqualTest {
+	// Equalities
+	DeepEqualTest{ 1, 1, true },
+	DeepEqualTest{ int32(1), int32(1), true },
+	DeepEqualTest{ 0.5, 0.5, true },
+	DeepEqualTest{ float32(0.5), float32(0.5), true },
+	DeepEqualTest{ "hello", "hello", true },
+	DeepEqualTest{ make([]int, 10), make([]int, 10), true },
+	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 3 }, true },
+	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.5 }, true },
+	// Inequalities
+	DeepEqualTest{ 1, 2, false },
+	DeepEqualTest{ int32(1), int32(2), false },
+	DeepEqualTest{ 0.5, 0.6, false },
+	DeepEqualTest{ float32(0.5), float32(0.6), false },
+	DeepEqualTest{ "hello", "hey", false },
+	DeepEqualTest{ make([]int, 10), make([]int, 11), false },
+	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 4 }, false },
+	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.6 }, false },
+	// Mismatched types
+	DeepEqualTest{ 1, 1.0, false },
+	DeepEqualTest{ int32(1), int64(1), false },
+	DeepEqualTest{ 0.5, "hello", false },
+	DeepEqualTest{ []int{ 1, 2, 3 }, [3]int{ 1, 2, 3 }, false },
+	DeepEqualTest{ &[3]interface{} { 1, 2, 4 }, &[3]interface{} { 1, 2, "s" }, false },
+}
+
+func TestDeepEqual(t *testing.T) {
+	for i, test := range deepEqualTests {
+		if r := DeepEqual(test.a, test.b); r != test.eq {
+			t.Errorf("DeepEqual(%v, %v) = %v, want %v", test.a, test.b, r, test.eq);
+		}
+	}
+}
+
+func TestDeepEqualRecursiveStruct(t *testing.T) {
+	a, b := new(Recursive), new(Recursive);
+	*a = Recursive{ 12, a };
+	*b = Recursive{ 12, b };
+	if !DeepEqual(a, b) {
+		t.Error("DeepEqual(recursive same) = false, want true");
+	}
+}
+
+func TestDeepEqualComplexStruct(t *testing.T) {
+	m := make(map[float]float);
+	stra, strb := "hello", "hello";
+	a, b := new(Complex), new(Complex);
+	*a = Complex{5, [3]*Complex{a, b, a}, &stra, m};
+	*b = Complex{5, [3]*Complex{b, a, a}, &strb, m};
+	if !DeepEqual(a, b) {
+		t.Error("DeepEqual(complex same) = false, want true");
+	}
+}
+
+func TestDeepEqualComplexStructInequality(t *testing.T) {
+	m := make(map[float]float);
+	stra, strb := "hello", "helloo";  // Difference is here
+	a, b := new(Complex), new(Complex);
+	*a = Complex{5, [3]*Complex{a, b, a}, &stra, m};
+	*b = Complex{5, [3]*Complex{b, a, a}, &strb, m};
+	if DeepEqual(a, b) {
+		t.Error("DeepEqual(complex different) = true, want false");
+	}
+}

src/lib/reflect/deepequal.go

--- /dev/null
+++ b/src/lib/reflect/deepequal.go
@@ -0,0 +1,78 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Deep equality test via reflection
+
+package reflect
+
+import "reflect"
+
+// 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[Addr]Addr) bool {
+	if v1.Kind() != v2.Kind() {
+		return false;
+	}
+
+	// Short circuit if references are identical or already seen
+	addr1 := v1.Addr();
+	addr2 := v2.Addr();
+
+	if addr1 == addr2 {
+		return true;
+	}
+	if vaddr, ok := visited[addr1]; ok && vaddr == addr2 {
+		return true;
+	}
+	visited[addr1] = addr2;
+
+	switch v1.Kind() {
+	case ArrayKind:
+		arr1 := v1.(ArrayValue);
+		arr2 := v2.(ArrayValue);
+		if arr1.IsSlice() != arr2.IsSlice() || arr1.Len() != arr2.Len() {
+			return false;
+		}
+		for i := 0; i < arr1.Len(); i++ {
+			if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited) {
+				return false;
+			}
+		}
+		return true;
+	case InterfaceKind:
+		return deepValueEqual(NewValue(v1.(InterfaceValue).Get()),
+				NewValue(v2.(InterfaceValue).Get()), visited);
+	case MapKind:
+		// TODO(dnadasi): Implement this fully once MapValue is implemented
+		return v1.Interface() == v2.Interface();
+	case PtrKind:
+		return deepValueEqual(v1.(PtrValue).Sub(), v2.(PtrValue).Sub(), visited);
+	case StructKind:
+		struct1 := v1.(StructValue);
+		struct2 := v2.(StructValue);
+		if struct1.Len() != struct2.Len() {
+			return false;
+		}
+		for i := 0; i < struct1.Len(); i++ {
+			if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited) {
+				return false;
+			}
+		}
+		return true;
+	default:
+		// Normal equality suffices
+		return v1.Interface() == v2.Interface();
+	}
+
+	panic("Not reached");
+}
+
+// DeepEqual tests for deep equality. It uses normal == equality where possible
+// but will scan members of arrays, slices, and fields of structs. It correctly
+// handles recursive types. Until reflection supports maps, maps are equal iff
+// they are identical.
+func DeepEqual(a1, a2 interface{}) bool {
+	return deepValueEqual(NewValue(a1), NewValue(a2), make(map[Addr]Addr));
+}

コアとなるコードの解説

src/lib/reflect/Makefile

  • O3変数にdeepequal.$Oが追加されています。これは、deepequal.goがコンパイルされて生成されるオブジェクトファイル（deepequal.o）が、reflectパッケージのアーカイブファイル（reflect.a）に含められることを意味します。
  • a3ターゲットの$(AR) grc reflect.a tostring.$O行が$(AR) grc reflect.a tostring.$O deepequal.$Oに変更されています。これにより、deepequal.oがreflect.aにリンクされ、DeepEqual関数がreflectパッケージの一部として利用可能になります。

src/lib/reflect/all_test.go

  • Basic, Recursive, Complexという3つの新しい構造体が定義されています。これらは、DeepEqualが様々な複雑なデータ型（特に再帰的な型）をどのように扱うかをテストするために使用されます。
  • DeepEqualTest構造体は、テストケースの入力（a, b）と期待される結果（eq）を保持します。
  • deepEqualTestsスライスには、プリミティブ型、スライス、配列、構造体など、様々な値の組み合わせに対するDeepEqualの期待される結果が定義されています。これにより、基本的な等価性チェックが網羅されます。
  • TestDeepEqual関数は、deepEqualTestsスライスをイテレートし、各テストケースに対してDeepEqualを呼び出し、結果が期待通りであるかを検証します。
  • TestDeepEqualRecursiveStruct関数は、再帰的な構造体Recursiveのインスタンスを作成し、DeepEqualが循環参照を正しく処理し、無限ループに陥らずに等価性を判定できることを確認します。
  • TestDeepEqualComplexStructおよびTestDeepEqualComplexStructInequality関数は、より複雑な構造体Complex（配列、ポインタ、マップ、再帰的な参照を含む）の等価性および不等価性をテストし、DeepEqualがこれらの複雑なシナリオでも正しく機能することを確認します。

src/lib/reflect/deepequal.go

このファイルは新しく追加されたもので、DeepEqual関数の実装を含んでいます。

  • ファイルヘッダ: Goの標準ライセンス情報と、このファイルがリフレクションによる深い等価性テストを提供することを説明するコメントが含まれています。
  • package reflect: このファイルがreflectパッケージの一部であることを示します。
  • import "reflect": 自身のパッケージをインポートしていますが、これは当時のGoのモジュールシステムやパッケージ管理の初期段階における慣習的な記述である可能性があります。現代のGoでは通常、同じパッケージ内の型や関数を呼び出す際に明示的なインポートは不要です。
  • func deepValueEqual(v1, v2 Value, visited map[Addr]Addr) bool:
    • この関数は、2つのreflect.Value（v1, v2）と、既に比較済みの参照ペアを追跡するためのvisitedマップを受け取ります。
    • if v1.Kind() != v2.Kind() { return false; }: 比較対象の2つの値のKind（型カテゴリ）が異なる場合、それらは等しくないと判断し、falseを返します。
    • 循環参照の検出と回避:
      • addr1 := v1.Addr(); addr2 := v2.Addr();: 比較対象の値のアドレスを取得します。
      • if addr1 == addr2 { return true; }: もしアドレスが同じであれば、同じオブジェクトなのでtrueを返します。
      • if vaddr, ok := visited[addr1]; ok && vaddr == addr2 { return true; }: visitedマップを使って、v1のアドレスが既にキーとして存在し、その値がv2のアドレスと一致する場合、それは循環参照を意味するためtrueを返します。これにより無限ループを防ぎます。
      • visited[addr1] = addr2;: 現在の比較ペアをvisitedマップに記録します。
    • switch v1.Kind()による型ごとの比較ロジック:
      • ArrayKind: 配列（またはスライス）の場合、長さとIsSlice()の結果を比較し、その後、各要素を再帰的にdeepValueEqualで比較します。
      • InterfaceKind: インターフェースの場合、インターフェースが保持する実際の値を取り出し、それらをreflect.Valueに変換して再帰的に比較します。
      • MapKind: この時点では、マップの深い比較は未実装です。 TODOコメントがあり、v1.Interface() == v2.Interface()という、マップオブジェクト自体の同一性（同じマップであるか）のみを比較するロジックになっています。これは、当時のreflectパッケージの制限によるものです。
      • PtrKind: ポインタの場合、ポインタが指す先の値（サブエレメント）を再帰的にdeepValueEqualで比較します。
      • StructKind: 構造体の場合、フィールドの数を比較し、その後、各フィールドを再帰的にdeepValueEqualで比較します。
      • default: 上記以外の型（プリミティブ型など）の場合、Goの組み込みの==演算子で十分なため、v1.Interface() == v2.Interface()で直接値を比較します。
    • panic("Not reached");: 理論的には到達しないはずのコードパスですが、念のためパニックを発生させることで、予期せぬ挙動を早期に検出できるようにしています。
  • func DeepEqual(a1, a2 interface{}) bool:
    • この関数は、ユーザーが呼び出す公開APIです。
    • NewValue(a1)とNewValue(a2)を使って、入力されたinterface{}型の値をreflect.Valueに変換します。
    • make(map[Addr]Addr)で新しいvisitedマップを作成し、deepValueEqual関数に渡して比較を開始します。

このコミットにより、Go言語は、複雑なデータ構造の深い比較を標準ライブラリでサポートする重要な一歩を踏み出しました。特に、テストやデータ検証のシナリオにおいて、この機能は非常に有用です。

関連リンク

参考にした情報源リンク

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

このコミットは、Go言語のreflectパッケージにDeepEqual関数を追加するものです。DeepEqualは、Goの組み込みの==演算子では比較できない複雑なデータ構造（構造体、配列、スライス、ポインタなど）について、その内容が再帰的に等しいかどうかを判定するための機能を提供します。これにより、開発者はオブジェクトの深い比較を簡単に行えるようになります。

コミット

commit c4ad4f9fcfd69556f09928aa24fc110d5b3aa2d9
Author: Daniel Nadasi <dnadasi@google.com>
Date:   Wed Apr 1 22:20:18 2009 -0700

    Add a DeepEqual function to the reflect package
    
    R=r,rsc
    APPROVED=rsc
    DELTA=167  (166 added, 0 deleted, 1 changed)
    OCL=26982
    CL=27017
---
 src/lib/reflect/Makefile     |  3 +-\n src/lib/reflect/all_test.go  | 88 ++++++++++++++++++++++++++++++++++++++++++++\n src/lib/reflect/deepequal.go | 78 +++++++++++++++++++++++++++++++++++++++\n 3 files changed, 168 insertions(+), 1 deletion(-)

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

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

元コミット内容

reflectパッケージにDeepEqual関数を追加します。

変更の背景

Go言語において、プリミティブ型（整数、浮動小数点数、文字列など）やポインタ、チャネル、関数、インターフェースの値の比較には==演算子を使用できます。しかし、構造体、配列、スライス、マップといった複合型の場合、==演算子は常に「値の等価性」を意味するわけではありません。

  • 構造体: 全てのフィールドが比較可能であれば、フィールドごとの値が等しい場合にtrueを返します。
  • 配列: 要素の型が比較可能であれば、全ての要素が等しい場合にtrueを返します。
  • スライス: ==演算子はスライスヘッダ（ポインタ、長さ、容量）のみを比較し、参照している基底配列の内容は比較しません。異なるスライスが同じ内容を持っていても、==はfalseを返すことがあります。
  • マップ: ==演算子はマップに対して定義されていません。マップは参照型であり、内容の比較はできません。

このような背景から、Goの標準ライブラリには、複合型の「内容」が再帰的に等しいかどうかを判定する汎用的なメカニズムが求められていました。特に、テストコードで期待される出力と実際の結果を比較する際や、キャッシュのキーとして複雑な構造体を使用する際などに、この「ディープイコール」の機能は不可欠です。このコミットは、そのニーズに応えるためにreflectパッケージにDeepEqual関数を導入しました。

前提知識の解説

Goのreflectパッケージ

Go言語のreflectパッケージは、プログラムの実行時に変数や型の情報を検査・操作するための機能を提供します。これにより、Goの静的型付けの制約を受けずに、動的な型操作や汎用的なデータ処理が可能になります。

  • reflect.Type: Goの型そのものを表すインターフェースです。型の名前、基底型、メソッドなどの情報を提供します。
  • reflect.Value: Goの変数の値を表す構造体です。値の型情報（Type）と、その実際のデータを含みます。Valueを通じて、変数の値を読み取ったり、（エクスポートされたフィールドであれば）変更したりできます。
  • reflect.Kind: reflect.Valueが持つ値の「種類」を表す定数です。例えば、Int, String, Struct, Array, Slice, Map, Ptr, Interfaceなどがあります。DeepEqual関数は、このKindを利用して、比較対象の型に応じた適切な比較ロジックを適用します。
  • reflect.NewValue(interface{}): 任意のGoの値をreflect.Value型に変換する関数です。DeepEqual関数はこの関数を使って、比較対象のinterface{}型の引数をreflect.Valueに変換し、リフレクションによる比較を可能にします。
  • reflect.Value.Addr(): Valueが指す値のアドレスを返します。ポインタやスライス、マップなどの参照型を比較する際に、循環参照を検出するために利用されます。

Goにおける等価性（Equality）

Goにおける等価性（Equality）は、型によってその振る舞いが異なります。

  • プリミティブ型（数値、文字列、真偽値）: 値が完全に一致すればtrue。
  • ポインタ: 2つのポインタが同じメモリ位置を指していればtrue。
  • インターフェース: 内部の型と値が両方とも等しければtrue。
  • 構造体: 全てのフィールドが比較可能であり、かつ全てのフィールドの値が等しければtrue。
  • 配列: 要素の型が比較可能であり、かつ全ての要素の値が等しければtrue。
  • スライス: ==演算子はスライスヘッダ（ポインタ、長さ、容量）のみを比較します。内容の比較は行いません。
  • マップ: ==演算子はマップに対して定義されていません。マップは参照型であり、内容の比較はできません。
  • 関数: 2つの関数が同じ関数を指していればtrue。

DeepEqualは、これらの組み込みの==演算子の限界を補い、特にスライスやマップ、そして再帰的な構造体など、複雑なデータ構造の「内容」が等しいかどうかを判定するために導入されました。

再帰的なデータ構造の比較

再帰的なデータ構造とは、自身または自身を含む別の型への参照（ポインタ）を持つ構造体のことです。例えば、リンクリストのノードやツリー構造のノードなどがこれに該当します。

type Node struct {
    Value int
    Next  *Node
}

このような構造体を比較する際、単純にフィールドを再帰的に比較していくと、循環参照（AがBを参照し、BがAを参照するような状況）が発生した場合に無限ループに陥る可能性があります。

DeepEqual関数は、この無限ループを避けるために「visitedマップ」というメカニズムを使用します。これは、既に比較済みのオブジェクトのペアを記録しておくことで、同じペアが再度比較されそうになったときに、それが循環参照であることを検出し、比較をスキップして無限ループを防ぐためのものです。

技術的詳細

DeepEqual関数は、Goのreflectパッケージを駆使して、任意の2つのGoの値が「深く」等しいかどうかを判定します。その核心は、内部で呼び出されるdeepValueEqual関数にあります。

DeepEqual関数の役割

DeepEqual(a1, a2 interface{}) boolは、ユーザーが直接呼び出すエントリポイントです。この関数は、比較したい任意の2つの値をinterface{}として受け取り、それらをreflect.Value型に変換した後、deepValueEqual関数に渡します。また、deepValueEqualが循環参照を検出するために使用するvisitedマップを初期化して渡します。

deepValueEqual関数の役割と実装

deepValueEqual(v1, v2 Value, visited map[Addr]Addr) boolが、実際の再帰的な比較ロジックを担います。

  1. 型の種類（Kind）のチェック: まず、v1.Kind() != v2.Kind()で、2つの値の基本的な型が異なる場合は即座にfalseを返します。例えば、intとfloat32は値が同じでも型が異なるため、DeepEqualでは等しくないと判断されます。

  2. 参照の同一性チェックとvisitedマップによる再帰検出:

    • addr1 := v1.Addr()とaddr2 := v2.Addr()で、それぞれのValueが指すメモリ上のアドレスを取得します。Addrはreflectパッケージ内の非公開型ですが、ここではメモリ上の位置を一意に識別するためのものと理解できます。
    • if addr1 == addr2 { return true }: もし2つの値が全く同じメモリ位置を指している（つまり、同じオブジェクトである）ならば、それらは深く等しいと判断し、trueを返して比較を終了します。これは最適化であり、循環参照の検出にも役立ちます。
    • if vaddr, ok := visited[addr1]; ok && vaddr == addr2 { return true }: visitedマップは、既に比較を開始したValueのアドレスペアを記録しています。もしaddr1が既にvisitedマップのキーとして存在し、その値がaddr2と一致するならば、それは現在比較中のパスで既にこのペアが比較されたことを意味します。これは循環参照を検出したことを示し、無限ループを避けるためにtrueを返して比較を終了します。
    • visited[addr1] = addr2: 現在比較しているaddr1とaddr2のペアをvisitedマップに記録します。これにより、後続の再帰呼び出しで同じペアが検出された場合に、上記のチェックで無限ループを回避できます。

  3. switch v1.Kind()による各型ごとの比較ロジック: 値のKindに応じて、異なる比較戦略が適用されます。

    • ArrayKind (配列):

      • arr1.IsSlice() != arr2.IsSlice(): スライスであるかどうかが異なる場合はfalse。
      • arr1.Len() != arr2.Len(): 長さが異なる場合はfalse。
      • for i := 0; i < arr1.Len(); i++ { if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited) { return false } }: 配列の各要素を再帰的にdeepValueEqualで比較します。一つでも等しくない要素があればfalseを返します。

    • InterfaceKind (インターフェース):

      • deepValueEqual(NewValue(v1.(InterfaceValue).Get()), NewValue(v2.(InterfaceValue).Get()), visited): インターフェースが保持する実際の値を取り出し、それらをreflect.Valueに変換して再帰的に比較します。

    • MapKind (マップ):

      • return v1.Interface() == v2.Interface(): このコミット時点では、マップの深い比較はまだ実装されていません。 TODO(dnadasi): Implement this fully once MapValue is implementedというコメントがあり、マップの比較は==演算子による同一性（同じマップオブジェクトであるか）のみで行われています。これは、当時のreflectパッケージがMapValueを完全にサポートしていなかったためです。

    • PtrKind (ポインタ):

      • return deepValueEqual(v1.(PtrValue).Sub(), v2.(PtrValue).Sub(), visited): ポインタが指す先の値（サブエレメント）を再帰的にdeepValueEqualで比較します。

    • StructKind (構造体):

      • struct1.Len() != struct2.Len(): フィールドの数が異なる場合はfalse。
      • for i := 0; i < struct1.Len(); i++ { if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited) { return false } }: 構造体の各フィールドを再帰的にdeepValueEqualで比較します。一つでも等しくないフィールドがあればfalseを返します。

    • default (その他の型):

      • return v1.Interface() == v2.Interface(): 上記の複合型以外の型（プリミティブ型、チャネル、関数など）については、Goの組み込みの==演算子による比較で十分であるため、Interface()メソッドで実際の値を取り出し、直接比較します。

テストケースの分析 (all_test.go)

all_test.goに追加されたテストケースは、DeepEqual関数の様々な挙動を検証しています。

  • DeepEqualTest構造体とdeepEqualTestsスライス:

    • a, b interface{}: 比較対象の2つの値。
    • eq bool: 期待される比較結果（trueまたはfalse）。
    • このスライスには、整数、浮動小数点数、文字列、スライス、配列、構造体など、様々な型の等しいケースと等しくないケースが含まれています。
    • 特に、make([]int, 10)とmake([]int, 10)のように、異なるメモリ位置に存在するが内容が等しいスライスがtrueになること、1と1.0のように値は同じでも型が異なる場合はfalseになることなどがテストされています。

  • TestDeepEqualRecursiveStruct:

    • 再帰的な構造体Recursive（自身へのポインタを持つ）の比較をテストします。
    • *a = Recursive{ 12, a }のように、構造体自身を指すポインタを持つインスタンスを作成し、DeepEqualが無限ループに陥らずに正しく比較できることを検証します。

  • TestDeepEqualComplexStruct:

    • より複雑な構造体Complex（配列、ポインタ、マップ、自身へのポインタを持つ）の比較をテストします。
    • *a = Complex{5, [3]*Complex{a, b, a}, &stra, m}のように、複数の参照や再帰的な参照を含む構造体を構築し、DeepEqualが正しく等価性を判定できることを検証します。

  • TestDeepEqualComplexStructInequality:

    • TestDeepEqualComplexStructと同様の複雑な構造体で、意図的にわずかな違い（文字列straとstrb）を導入し、DeepEqualが正しくfalseを返すことを検証します。

これらのテストケースは、DeepEqualがプリミティブ型から複雑な再帰的構造体まで、幅広いシナリオで期待通りに動作することを保証するために重要です。

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

src/lib/reflect/Makefile

--- a/src/lib/reflect/Makefile
+++ b/src/lib/reflect/Makefile
@@ -40,6 +40,7 @@ O2=\
 
 O3=\
 	tostring.$O\
+	deepequal.$O\
 
 reflect.a: a1 a2 a3
 
@@ -52,7 +53,7 @@ a2:	$(O2)
 	rm -f $(O2)
 
 a3:	$(O3)
-	$(AR) grc reflect.a tostring.$O
+	$(AR) grc reflect.a tostring.$O deepequal.$O
 	rm -f $(O3)
 
 newpkg: clean

src/lib/reflect/all_test.go

--- a/src/lib/reflect/all_test.go
+++ b/src/lib/reflect/all_test.go
@@ -356,3 +356,91 @@ func TestBigStruct(t *testing.T) {
 		t.Errorf("NewValue(%v).Interface().(big) = %v", b, b1);
 	}
 }
+
+type Basic struct {
+	x int;
+	y float32
+}
+
+type Recursive struct {
+	x int;
+	r *Recursive
+}
+
+type Complex struct {
+	a int;
+	b [3]*Complex;
+	c *string;
+	d map[float]float
+}
+
+type DeepEqualTest struct {
+	a, b interface{};
+	eq bool;
+}
+
+var deepEqualTests = []DeepEqualTest {
+	// Equalities
+	DeepEqualTest{ 1, 1, true },
+	DeepEqualTest{ int32(1), int32(1), true },
+	DeepEqualTest{ 0.5, 0.5, true },
+	DeepEqualTest{ float32(0.5), float32(0.5), true },
+	DeepEqualTest{ "hello", "hello", true },
+	DeepEqualTest{ make([]int, 10), make([]int, 10), true },
+	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 3 }, true },
+	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.5 }, true },
+	// Inequalities
+	DeepEqualTest{ 1, 2, false },
+	DeepEqualTest{ int32(1), int32(2), false },
+	DeepEqualTest{ 0.5, 0.6, false },
+	DeepEqualTest{ float32(0.5), float32(0.6), false },
+	DeepEqualTest{ "hello", "hey", false },
+	DeepEqualTest{ make([]int, 10), make([]int, 11), false },
+	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 4 }, false },
+	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.6 }, false },
+	// Mismatched types
+	DeepEqualTest{ 1, 1.0, false },
+	DeepEqualTest{ int32(1), int64(1), false },
+	DeepEqualTest{ 0.5, "hello", false },
+	DeepEqualTest{ []int{ 1, 2, 3 }, [3]int{ 1, 2, 3 }, false },
+	DeepEqualTest{ &[3]interface{} { 1, 2, 4 }, &[3]interface{} { 1, 2, "s" }, false },
+}
+
+func TestDeepEqual(t *testing.T) {
+	for i, test := range deepEqualTests {
+		if r := DeepEqual(test.a, test.b); r != test.eq {
+			t.Errorf("DeepEqual(%v, %v) = %v, want %v", test.a, test.b, r, test.eq);
+		}
+	}
+}
+
+func TestDeepEqualRecursiveStruct(t *testing.T) {
+	a, b := new(Recursive), new(Recursive);
+	*a = Recursive{ 12, a };
+	*b = Recursive{ 12, b };
+	if !DeepEqual(a, b) {
+		t.Error("DeepEqual(recursive same) = false, want true");
+	}
+}
+
+func TestDeepEqualComplexStruct(t *testing.T) {
+	m := make(map[float]float);
+	stra, strb := "hello", "hello";
+	a, b := new(Complex), new(Complex);
+	*a = Complex{5, [3]*Complex{a, b, a}, &stra, m};
+	*b = Complex{5, [3]*Complex{b, a, a}, &strb, m};
+	if !DeepEqual(a, b) {
+		t.Error("DeepEqual(complex same) = false, want true");
+	}
+}
+
+func TestDeepEqualComplexStructInequality(t *testing.T) {
+	m := make(map[float]float);
+	stra, strb := "hello", "helloo";  // Difference is here
+	a, b := new(Complex), new(Complex);
+	*a = Complex{5, [3]*Complex{a, b, a}, &stra, m};
+	*b = Complex{5, [3]*Complex{b, a, a}, &strb, m};
+	if DeepEqual(a, b) {
+		t.Error("DeepEqual(complex different) = true, want false");
+	}
+}

src/lib/reflect/deepequal.go

--- /dev/null
+++ b/src/lib/reflect/deepequal.go
@@ -0,0 +1,78 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Deep equality test via reflection
+
+package reflect
+
+import "reflect"
+
+// 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[Addr]Addr) bool {
+	if v1.Kind() != v2.Kind() {
+		return false;
+	}
+
+	// Short circuit if references are identical or already seen
+	addr1 := v1.Addr();
+	addr2 := v2.Addr();
+
+	if addr1 == addr2 {
+		return true;
+	}
+	if vaddr, ok := visited[addr1]; ok && vaddr == addr2 {
+		return true;
+	}
+	visited[addr1] = addr2;
+
+	switch v1.Kind() {
+	case ArrayKind:
+		arr1 := v1.(ArrayValue);
+		arr2 := v2.(ArrayValue);
+		if arr1.IsSlice() != arr2.IsSlice() || arr1.Len() != arr2.Len() {
+			return false;
+		}
+		for i := 0; i < arr1.Len(); i++ {
+			if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited) {
+				return false;
+			}
+		}
+		return true;
+	case InterfaceKind:
+		return deepValueEqual(NewValue(v1.(InterfaceValue).Get()),
+				NewValue(v2.(InterfaceValue).Get()), visited);
+	case MapKind:
+		// TODO(dnadasi): Implement this fully once MapValue is implemented
+		return v1.Interface() == v2.Interface();
+	case PtrKind:
+		return deepValueEqual(v1.(PtrValue).Sub(), v2.(PtrValue).Sub(), visited);
+	case StructKind:
+		struct1 := v1.(StructValue);
+		struct2 := v2.(StructValue);
+		if struct1.Len() != struct2.Len() {
+			return false;
+		}
+		for i := 0; i < struct1.Len(); i++ {
+			if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited) {
+				return false;
+			}
+		}
+		return true;
+	default:
+		// Normal equality suffices
+		return v1.Interface() == v2.Interface();
+	}
+
+	panic("Not reached");
+}
+
+// DeepEqual tests for deep equality. It uses normal == equality where possible
+// but will scan members of arrays, slices, and fields of structs. It correctly
+// handles recursive types. Until reflection supports maps, maps are equal iff
+// they are identical.
+func DeepEqual(a1, a2 interface{}) bool {
+	return deepValueEqual(NewValue(a1), NewValue(a2), make(map[Addr]Addr));
+}

コアとなるコードの解説

src/lib/reflect/Makefile

  • O3変数にdeepequal.$Oが追加されています。これは、deepequal.goがコンパイルされて生成されるオブジェクトファイル（deepequal.o）が、reflectパッケージのアーカイブファイル（reflect.a）に含められることを意味します。
  • a3ターゲットの$(AR) grc reflect.a tostring.$O行が$(AR) grc reflect.a tostring.$O deepequal.$Oに変更されています。これにより、deepequal.oがreflect.aにリンクされ、DeepEqual関数がreflectパッケージの一部として利用可能になります。

src/lib/reflect/all_test.go

  • Basic, Recursive, Complexという3つの新しい構造体が定義されています。これらは、DeepEqualが様々な複雑なデータ型（特に再帰的な型）をどのように扱うかをテストするために使用されます。
  • DeepEqualTest構造体は、テストケースの入力（a, b）と期待される結果（eq）を保持します。
  • deepEqualTestsスライスには、プリミティブ型、スライス、配列、構造体など、様々な値の組み合わせに対するDeepEqualの期待される結果が定義されています。これにより、基本的な等価性チェックが網羅されます。
  • TestDeepEqual関数は、deepEqualTestsスライスをイテレートし、各テストケースに対してDeepEqualを呼び出し、結果が期待通りであるかを検証します。
  • TestDeepEqualRecursiveStruct関数は、再帰的な構造体Recursiveのインスタンスを作成し、DeepEqualが循環参照を正しく処理し、無限ループに陥らずに等価性を判定できることを確認します。
  • TestDeepEqualComplexStructおよびTestDeepEqualComplexStructInequality関数は、より複雑な構造体Complex（配列、ポインタ、マップ、再帰的な参照を含む）の等価性および不等価性をテストし、DeepEqualがこれらの複雑なシナリオでも正しく機能することを確認します。

src/lib/reflect/deepequal.go

このファイルは新しく追加されたもので、DeepEqual関数の実装を含んでいます。

  • ファイルヘッダ: Goの標準ライセンス情報と、このファイルがリフレクションによる深い等価性テストを提供することを説明するコメントが含まれています。
  • package reflect: このファイルがreflectパッケージの一部であることを示します。
  • import "reflect": 自身のパッケージをインポートしていますが、これは当時のGoのモジュールシステムやパッケージ管理の初期段階における慣習的な記述である可能性があります。現代のGoでは通常、同じパッケージ内の型や関数を呼び出す際に明示的なインポートは不要です。
  • func deepValueEqual(v1, v2 Value, visited map[Addr]Addr) bool:
    • この関数は、2つのreflect.Value（v1, v2）と、既に比較済みの参照ペアを追跡するためのvisitedマップを受け取ります。
    • if v1.Kind() != v2.Kind() { return false; }: 比較対象の2つの値のKind（型カテゴリ）が異なる場合、それらは等しくないと判断し、falseを返します。
    • 循環参照の検出と回避:
      • addr1 := v1.Addr(); addr2 := v2.Addr();: 比較対象の値のアドレスを取得します。
      • if addr1 == addr2 { return true; }: もしアドレスが同じであれば、同じオブジェクトなのでtrueを返します。
      • if vaddr, ok := visited[addr1]; ok && vaddr == addr2 { return true; }: visitedマップを使って、v1のアドレスが既にキーとして存在し、その値がv2のアドレスと一致する場合、それは循環参照を意味するためtrueを返します。これにより無限ループを防ぎます。
      • visited[addr1] = addr2;: 現在の比較ペアをvisitedマップに記録します。
    • switch v1.Kind()による型ごとの比較ロジック:
      • ArrayKind: 配列（またはスライス）の場合、長さとIsSlice()の結果を比較し、その後、各要素を再帰的にdeepValueEqualで比較します。
      • InterfaceKind: インターフェースの場合、インターフェースが保持する実際の値を取り出し、それらをreflect.Valueに変換して再帰的に比較します。
      • MapKind: この時点では、マップの深い比較は未実装です。 TODOコメントがあり、v1.Interface() == v2.Interface()という、マップオブジェクト自体の同一性（同じマップであるか）のみを比較するロジックになっています。これは、当時のreflectパッケージの制限によるものです。
      • PtrKind: ポインタの場合、ポインタが指す先の値（サブエレメント）を再帰的にdeepValueEqualで比較します。
      • StructKind: 構造体の場合、フィールドの数を比較し、その後、各フィールドを再帰的にdeepValueEqualで比較します。
      • default: 上記以外の型（プリミティブ型など）の場合、Goの組み込みの==演算子で十分なため、v1.Interface() == v2.Interface()で直接値を比較します。
    • panic("Not reached");: 理論的には到達しないはずのコードパスですが、念のためパニックを発生させることで、予期せぬ挙動を早期に検出できるようにしています。
  • func DeepEqual(a1, a2 interface{}) bool:
    • この関数は、ユーザーが呼び出す公開APIです。
    • NewValue(a1)とNewValue(a2)を使って、入力されたinterface{}型の値をreflect.Valueに変換します。
    • make(map[Addr]Addr)で新しいvisitedマップを作成し、deepValueEqual関数に渡して比較を開始します。

このコミットにより、Go言語は、複雑なデータ構造の深い比較を標準ライブラリでサポートする重要な一歩を踏み出しました。特に、テストやデータ検証のシナリオにおいて、この機能は非常に有用です。

関連リンク

参考にした情報源リンク