...
Run Format

Source file src/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	import "unsafe"
    10	
    11	// During deepValueEqual, must keep track of checks that are
    12	// in progress. The comparison algorithm assumes that all
    13	// checks in progress are true when it reencounters them.
    14	// Visited comparisons are stored in a map indexed by visit.
    15	type visit struct {
    16		a1  unsafe.Pointer
    17		a2  unsafe.Pointer
    18		typ Type
    19	}
    20	
    21	// Tests for deep equality using reflected types. The map argument tracks
    22	// comparisons that have already been seen, which allows short circuiting on
    23	// recursive types.
    24	func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool {
    25		if !v1.IsValid() || !v2.IsValid() {
    26			return v1.IsValid() == v2.IsValid()
    27		}
    28		if v1.Type() != v2.Type() {
    29			return false
    30		}
    31	
    32		// if depth > 10 { panic("deepValueEqual") }	// for debugging
    33	
    34		// We want to avoid putting more in the visited map than we need to.
    35		// For any possible reference cycle that might be encountered,
    36		// hard(t) needs to return true for at least one of the types in the cycle.
    37		hard := func(k Kind) bool {
    38			switch k {
    39			case Map, Slice, Ptr, Interface:
    40				return true
    41			}
    42			return false
    43		}
    44	
    45		if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) {
    46			addr1 := unsafe.Pointer(v1.UnsafeAddr())
    47			addr2 := unsafe.Pointer(v2.UnsafeAddr())
    48			if uintptr(addr1) > uintptr(addr2) {
    49				// Canonicalize order to reduce number of entries in visited.
    50				// Assumes non-moving garbage collector.
    51				addr1, addr2 = addr2, addr1
    52			}
    53	
    54			// Short circuit if references are already seen.
    55			typ := v1.Type()
    56			v := visit{addr1, addr2, typ}
    57			if visited[v] {
    58				return true
    59			}
    60	
    61			// Remember for later.
    62			visited[v] = true
    63		}
    64	
    65		switch v1.Kind() {
    66		case Array:
    67			for i := 0; i < v1.Len(); i++ {
    68				if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    69					return false
    70				}
    71			}
    72			return true
    73		case Slice:
    74			if v1.IsNil() != v2.IsNil() {
    75				return false
    76			}
    77			if v1.Len() != v2.Len() {
    78				return false
    79			}
    80			if v1.Pointer() == v2.Pointer() {
    81				return true
    82			}
    83			for i := 0; i < v1.Len(); i++ {
    84				if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    85					return false
    86				}
    87			}
    88			return true
    89		case Interface:
    90			if v1.IsNil() || v2.IsNil() {
    91				return v1.IsNil() == v2.IsNil()
    92			}
    93			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    94		case Ptr:
    95			if v1.Pointer() == v2.Pointer() {
    96				return true
    97			}
    98			return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
    99		case Struct:
   100			for i, n := 0, v1.NumField(); i < n; i++ {
   101				if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
   102					return false
   103				}
   104			}
   105			return true
   106		case Map:
   107			if v1.IsNil() != v2.IsNil() {
   108				return false
   109			}
   110			if v1.Len() != v2.Len() {
   111				return false
   112			}
   113			if v1.Pointer() == v2.Pointer() {
   114				return true
   115			}
   116			for _, k := range v1.MapKeys() {
   117				val1 := v1.MapIndex(k)
   118				val2 := v2.MapIndex(k)
   119				if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
   120					return false
   121				}
   122			}
   123			return true
   124		case Func:
   125			if v1.IsNil() && v2.IsNil() {
   126				return true
   127			}
   128			// Can't do better than this:
   129			return false
   130		default:
   131			// Normal equality suffices
   132			return valueInterface(v1, false) == valueInterface(v2, false)
   133		}
   134	}
   135	
   136	// DeepEqual reports whether x and y are ``deeply equal,'' defined as follows.
   137	// Two values of identical type are deeply equal if one of the following cases applies.
   138	// Values of distinct types are never deeply equal.
   139	//
   140	// Array values are deeply equal when their corresponding elements are deeply equal.
   141	//
   142	// Struct values are deeply equal if their corresponding fields,
   143	// both exported and unexported, are deeply equal.
   144	//
   145	// Func values are deeply equal if both are nil; otherwise they are not deeply equal.
   146	//
   147	// Interface values are deeply equal if they hold deeply equal concrete values.
   148	//
   149	// Map values are deeply equal when all of the following are true:
   150	// they are both nil or both non-nil, they have the same length,
   151	// and either they are the same map object or their corresponding keys
   152	// (matched using Go equality) map to deeply equal values.
   153	//
   154	// Pointer values are deeply equal if they are equal using Go's == operator
   155	// or if they point to deeply equal values.
   156	//
   157	// Slice values are deeply equal when all of the following are true:
   158	// they are both nil or both non-nil, they have the same length,
   159	// and either they point to the same initial entry of the same underlying array
   160	// (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal.
   161	// Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil))
   162	// are not deeply equal.
   163	//
   164	// Other values - numbers, bools, strings, and channels - are deeply equal
   165	// if they are equal using Go's == operator.
   166	//
   167	// In general DeepEqual is a recursive relaxation of Go's == operator.
   168	// However, this idea is impossible to implement without some inconsistency.
   169	// Specifically, it is possible for a value to be unequal to itself,
   170	// either because it is of func type (uncomparable in general)
   171	// or because it is a floating-point NaN value (not equal to itself in floating-point comparison),
   172	// or because it is an array, struct, or interface containing
   173	// such a value.
   174	// On the other hand, pointer values are always equal to themselves,
   175	// even if they point at or contain such problematic values,
   176	// because they compare equal using Go's == operator, and that
   177	// is a sufficient condition to be deeply equal, regardless of content.
   178	// DeepEqual has been defined so that the same short-cut applies
   179	// to slices and maps: if x and y are the same slice or the same map,
   180	// they are deeply equal regardless of content.
   181	func DeepEqual(x, y interface{}) bool {
   182		if x == nil || y == nil {
   183			return x == y
   184		}
   185		v1 := ValueOf(x)
   186		v2 := ValueOf(y)
   187		if v1.Type() != v2.Type() {
   188			return false
   189		}
   190		return deepValueEqual(v1, v2, make(map[visit]bool), 0)
   191	}
   192	

View as plain text