golang deepequal 代码
文件路径：/src/reflect/deepequal.go
/ 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 (
"internal/bytealg"
"unsafe"
)
/ 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 comparisons are stored in a map indexed by visit.
type visit struct {
a1 unsafe.Pointer
a2 unsafe.Pointer
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[visit]bool) bool {
if !v1.IsValid() || !v2.IsValid() {
return v1.IsValid() == v2.IsValid()
}
if v1.Type() != v2.Type() {
return false
}
/ We want to avoid putting more in the visited map than we need to.
/ For any possible reference cycle that might be encountered,
/ hard(v1, v2) needs to return true for at least one of the types in the cycle,
/ and it's safe and valid to get Value's internal pointer.
hard := func(v1, v2 Value) bool {
switch v1.Kind() {
case Pointer:
if v1.typ.ptrdata == 0 {
/ go:notinheap pointers can't be cyclic.
/ At least, all of our current uses of go:notinheap have
/ that property. The runtime ones aren't cyclic (and we don't use
/ DeepEqual on them anyway), and the cgo-generated ones are
/ all empty structs.
return false
}
fallthrough
case Map, Slice, Interface:
/ Nil pointers cannot be cyclic. Avoid putting them in the visited map.
return !v1.IsNil() && !v2.IsNil()
}
return false
}
if hard(v1, v2) {
/ For a Pointer or Map value, we need to check flagIndir,
/ which we do by calling the pointer method.
/ For Slice or Interface, flagIndir is always set,
/ and using v.ptr suffices.
ptrval := func(v Value) unsafe.Pointer {
switch v.Kind() {
case Pointer, Map:
return v.pointer()
default:
return v.ptr
}
}
addr1 := ptrval(v1)
addr2 := ptrval(v2)
if uintptr(addr1) > uintptr(addr2) {
/ Canonicalize order to reduce number of entries in visited.
/ Assumes non-moving garbage collector.
addr1, addr2 = addr2, addr1
}
/ Short circuit if references are already seen.
typ := v1.Type()
v := visit{addr1, addr2, typ}
if visited[v] {
return true
}
/ Remember for later.
visited[v] = true
}
switch v1.Kind() {
case Array:
for i := 0; i < v1.Len(); i++ {
if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
return false
}
}
return true
case Slice:
if v1.IsNil() != v2.IsNil() {
return false
}
if v1.Len() != v2.Len() {
return false
}
if v1.UnsafePointer() == v2.UnsafePointer() {
return true
}
/ Special case for []byte, which is common.
if v1.Type().Elem().Kind() == Uint8 {
return bytealg.Equal(v1.Bytes(), v2.Bytes())
}
for i := 0; i < v1.Len(); i++ {
if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
return false
}
}
return true
case Interface:
if v1.IsNil() || v2.IsNil() {
return v1.IsNil() == v2.IsNil()
}
return deepValueEqual(v1.Elem(), v2.Elem(), visited)
case Pointer:
if v1.UnsafePointer() == v2.UnsafePointer() {
return true
}
return deepValueEqual(v1.Elem(), v2.Elem(), visited)
case Struct:
for i, n := 0, v1.NumField(); i < n; i++ {
if !deepValueEqual(v1.Field(i), v2.Field(i), visited) {
return false
}
}
return true
case Map:
if v1.IsNil() != v2.IsNil() {
return false
}
if v1.Len() != v2.Len() {
return false
}
if v1.UnsafePointer() == v2.UnsafePointer() {
return true
}
for _, k := range v1.MapKeys() {
val1 := v1.MapIndex(k)
val2 := v2.MapIndex(k)
if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(val1, val2, visited) {
return false
}
}
return true
case Func:
if v1.IsNil() && v2.IsNil() {
return true
}
/ Can't do better than this:
return false
case Int, Int8, Int16, Int32, Int64:
return v1.Int() == v2.Int()
case Uint, Uint8, Uint16, Uint32, Uint64, Uintptr:
return v1.Uint() == v2.Uint()
case String:
return v1.String() == v2.String()
case Bool:
return v1.Bool() == v2.Bool()
case Float32, Float64:
return v1.Float() == v2.Float()
case Complex64, Complex128:
return v1.Complex() == v2.Complex()
default:
/ Normal equality suffices
return valueInterface(v1, false) == valueInterface(v2, false)
}
}
/ DeepEqual reports whether x and y are “deeply equal,” defined as follows.
/ Two values of identical type are deeply equal if one of the following cases applies.
/ Values of distinct types are never deeply equal.
/
/ Array values are deeply equal when their corresponding elements are deeply equal.
/
/ Struct values are deeply equal if their corresponding fields,
/ both exported and unexported, are deeply equal.
/
/ Func values are deeply equal if both are nil; otherwise they are not deeply equal.
/
/ Interface values are deeply equal if they hold deeply equal concrete values.
/
/ Map values are deeply equal when all of the following are true:
/ they are both nil or both non-nil, they have the same length,
/ and either they are the same map object or their corresponding keys
/ (matched using Go equality) map to deeply equal values.
/
/ Pointer values are deeply equal if they are equal using Go's == operator
/ or if they point to deeply equal values.
/
/ Slice values are deeply equal when all of the following are true:
/ they are both nil or both non-nil, they have the same length,
/ and either they point to the same initial entry of the same underlying array
/ (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal.
/ Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil))
/ are not deeply equal.
/
/ Other values - numbers, bools, strings, and channels - are deeply equal
/ if they are equal using Go's == operator.
/
/ In general DeepEqual is a recursive relaxation of Go's == operator.
/ However, this idea is impossible to implement without some inconsistency.
/ Specifically, it is possible for a value to be unequal to itself,
/ either because it is of func type (uncomparable in general)
/ or because it is a floating-point NaN value (not equal to itself in floating-point comparison),
/ or because it is an array, struct, or interface containing
/ such a value.
/ On the other hand, pointer values are always equal to themselves,
/ even if they point at or contain such problematic values,
/ because they compare equal using Go's == operator, and that
/ is a sufficient condition to be deeply equal, regardless of content.
/ DeepEqual has been defined so that the same short-cut applies
/ to slices and maps: if x and y are the same slice or the same map,
/ they are deeply equal regardless of content.
/
/ As DeepEqual traverses the data values it may find a cycle. The
/ second and subsequent times that DeepEqual compares two pointer
/ values that have been compared before, it treats the values as
/ equal rather than examining the values to which they point.
/ This ensures that DeepEqual terminates.
func DeepEqual(x, y any) bool {
if x == nil || y == nil {
return x == y
}
v1 := ValueOf(x)
v2 := ValueOf(y)
if v1.Type() != v2.Type() {
return false
}
return deepValueEqual(v1, v2, make(map[visit]bool))
}