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.IsNil() != v2.IsNil() {
    73				return false
    74			}
    75			if v1.Len() != v2.Len() {
    76				return false
    77			}
    78			for i := 0; i < v1.Len(); i++ {
    79				if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    80					return false
    81				}
    82			}
    83			return true
    84		case Interface:
    85			if v1.IsNil() || v2.IsNil() {
    86				return v1.IsNil() == v2.IsNil()
    87			}
    88			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    89		case Ptr:
    90			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    91		case Struct:
    92			for i, n := 0, v1.NumField(); i < n; i++ {
    93				if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
    94					return false
    95				}
    96			}
    97			return true
    98		case Map:
    99			if v1.IsNil() != v2.IsNil() {
   100				return false
   101			}
   102			if v1.Len() != v2.Len() {
   103				return false
   104			}
   105			for _, k := range v1.MapKeys() {
   106				if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
   107					return false
   108				}
   109			}
   110			return true
   111		case Func:
   112			if v1.IsNil() && v2.IsNil() {
   113				return true
   114			}
   115			// Can't do better than this:
   116			return false
   117		default:
   118			// Normal equality suffices
   119			return valueInterface(v1, false) == valueInterface(v2, false)
   120		}
   121	
   122		panic("Not reached")
   123	}
   124	
   125	// DeepEqual tests for deep equality. It uses normal == equality where possible
   126	// but will scan members of arrays, slices, maps, and fields of structs. It correctly
   127	// handles recursive types. Functions are equal only if they are both nil.
   128	func DeepEqual(a1, a2 interface{}) bool {
   129		if a1 == nil || a2 == nil {
   130			return a1 == a2
   131		}
   132		v1 := ValueOf(a1)
   133		v2 := ValueOf(a2)
   134		if v1.Type() != v2.Type() {
   135			return false
   136		}
   137		return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
   138	}