Source file src/pkg/reflect/deepequal.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Deep equality test via reflection
     6	
     7	package reflect
     8	
     9	// During deepValueEqual, must keep track of checks that are
    10	// in progress.  The comparison algorithm assumes that all
    11	// checks in progress are true when it reencounters them.
    12	// Visited are stored in a map indexed by 17 * a1 + a2;
    13	type visit struct {
    14		a1   uintptr
    15		a2   uintptr
    16		typ  Type
    17		next *visit
    18	}
    19	
    20	// Tests for deep equality using reflected types. The map argument tracks
    21	// comparisons that have already been seen, which allows short circuiting on
    22	// recursive types.
    23	func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
    24		if !v1.IsValid() || !v2.IsValid() {
    25			return v1.IsValid() == v2.IsValid()
    26		}
    27		if v1.Type() != v2.Type() {
    28			return false
    29		}
    30	
    31		// if depth > 10 { panic("deepValueEqual") }	// for debugging
    32	
    33		if v1.CanAddr() && v2.CanAddr() {
    34			addr1 := v1.UnsafeAddr()
    35			addr2 := v2.UnsafeAddr()
    36			if addr1 > addr2 {
    37				// Canonicalize order to reduce number of entries in visited.
    38				addr1, addr2 = addr2, addr1
    39			}
    40	
    41			// Short circuit if references are identical ...
    42			if addr1 == addr2 {
    43				return true
    44			}
    45	
    46			// ... or already seen
    47			h := 17*addr1 + addr2
    48			seen := visited[h]
    49			typ := v1.Type()
    50			for p := seen; p != nil; p = p.next {
    51				if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
    52					return true
    53				}
    54			}
    55	
    56			// Remember for later.
    57			visited[h] = &visit{addr1, addr2, typ, seen}
    58		}
    59	
    60		switch v1.Kind() {
    61		case Array:
    62			if v1.Len() != v2.Len() {
    63				return false
    64			}
    65			for i := 0; i < v1.Len(); i++ {
    66				if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    67					return false
    68				}
    69			}
    70			return true
    71		case Slice:
    72			if v1.Len() != v2.Len() {
    73				return false
    74			}
    75			for i := 0; i < v1.Len(); i++ {
    76				if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    77					return false
    78				}
    79			}
    80			return true
    81		case Interface:
    82			if v1.IsNil() || v2.IsNil() {
    83				return v1.IsNil() == v2.IsNil()
    84			}
    85			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    86		case Ptr:
    87			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    88		case Struct:
    89			for i, n := 0, v1.NumField(); i < n; i++ {
    90				if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
    91					return false
    92				}
    93			}
    94			return true
    95		case Map:
    96			if v1.Len() != v2.Len() {
    97				return false
    98			}
    99			for _, k := range v1.MapKeys() {
   100				if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
   101					return false
   102				}
   103			}
   104			return true
   105		default:
   106			// Normal equality suffices
   107			return valueInterface(v1, false) == valueInterface(v2, false)
   108		}
   109	
   110		panic("Not reached")
   111	}
   112	
   113	// DeepEqual tests for deep equality. It uses normal == equality where possible
   114	// but will scan members of arrays, slices, and fields of structs. It correctly
   115	// handles recursive types.
   116	func DeepEqual(a1, a2 interface{}) bool {
   117		if a1 == nil || a2 == nil {
   118			return a1 == a2
   119		}
   120		v1 := ValueOf(a1)
   121		v2 := ValueOf(a2)
   122		if v1.Type() != v2.Type() {
   123			return false
   124		}
   125		return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
   126	}
The Go Programming Language

Source file src/pkg/reflect/deepequal.go
