text: // 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.
  
  // Package reflect is a fork of go's standard library reflection package, which
  // allows for deep equal with equality functions defined.
  package reflect
  
  import (
  	"fmt"
  	"reflect"
  	"strings"
  )
  
  // Equalities is a map from type to a function comparing two values of
  // that type.
  type Equalities map[reflect.Type]reflect.Value
  
  // For convenience, panics on errrors
  func EqualitiesOrDie(funcs ...interface{}) Equalities {
  	e := Equalities{}
  	if err := e.AddFuncs(funcs...); err != nil {
  		panic(err)
  	}
  	return e
  }
  
  // AddFuncs is a shortcut for multiple calls to AddFunc.
  func (e Equalities) AddFuncs(funcs ...interface{}) error {
  	for _, f := range funcs {
  		if err := e.AddFunc(f); err != nil {
  			return err
  		}
  	}
  	return nil
  }
  
  // AddFunc uses func as an equality function: it must take
  // two parameters of the same type, and return a boolean.
  func (e Equalities) AddFunc(eqFunc interface{}) error {
  	fv := reflect.ValueOf(eqFunc)
  	ft := fv.Type()
  	if ft.Kind() != reflect.Func {
  		return fmt.Errorf("expected func, got: %v", ft)
  	}
  	if ft.NumIn() != 2 {
  		return fmt.Errorf("expected two 'in' params, got: %v", ft)
  	}
  	if ft.NumOut() != 1 {
  		return fmt.Errorf("expected one 'out' param, got: %v", ft)
  	}
  	if ft.In(0) != ft.In(1) {
  		return fmt.Errorf("expected arg 1 and 2 to have same type, but got %v", ft)
  	}
  	var forReturnType bool
  	boolType := reflect.TypeOf(forReturnType)
  	if ft.Out(0) != boolType {
  		return fmt.Errorf("expected bool return, got: %v", ft)
  	}
  	e[ft.In(0)] = fv
  	return nil
  }
  
  // Below here is forked from go's reflect/deepequal.go
  
  // 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  uintptr
  	a2  uintptr
  	typ reflect.Type
  }
  
  // unexportedTypePanic is thrown when you use this DeepEqual on something that has an
  // unexported type. It indicates a programmer error, so should not occur at runtime,
  // which is why it's not public and thus impossible to catch.
  type unexportedTypePanic []reflect.Type
  
  func (u unexportedTypePanic) Error() string { return u.String() }
  func (u unexportedTypePanic) String() string {
  	strs := make([]string, len(u))
  	for i, t := range u {
  		strs[i] = fmt.Sprintf("%v", t)
  	}
  	return "an unexported field was encountered, nested like this: " + strings.Join(strs, " -> ")
  }
  
  func makeUsefulPanic(v reflect.Value) {
  	if x := recover(); x != nil {
  		if u, ok := x.(unexportedTypePanic); ok {
  			u = append(unexportedTypePanic{v.Type()}, u...)
  			x = u
  		}
  		panic(x)
  	}
  }
  
  // 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 (e Equalities) deepValueEqual(v1, v2 reflect.Value, visited map[visit]bool, depth int) bool {
  	defer makeUsefulPanic(v1)
  
  	if !v1.IsValid() || !v2.IsValid() {
  		return v1.IsValid() == v2.IsValid()
  	}
  	if v1.Type() != v2.Type() {
  		return false
  	}
  	if fv, ok := e[v1.Type()]; ok {
  		return fv.Call([]reflect.Value{v1, v2})[0].Bool()
  	}
  
  	hard := func(k reflect.Kind) bool {
  		switch k {
  		case reflect.Array, reflect.Map, reflect.Slice, reflect.Struct:
  			return true
  		}
  		return false
  	}
  
  	if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) {
  		addr1 := v1.UnsafeAddr()
  		addr2 := v2.UnsafeAddr()
  		if addr1 > addr2 {
  			// Canonicalize order to reduce number of entries in visited.
  			addr1, addr2 = addr2, addr1
  		}
  
  		// Short circuit if references are identical ...
  		if addr1 == addr2 {
  			return true
  		}
  
  		// ... or 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 reflect.Array:
  		// We don't need to check length here because length is part of
  		// an array's type, which has already been filtered for.
  		for i := 0; i < v1.Len(); i++ {
  			if !e.deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Slice:
  		if (v1.IsNil() || v1.Len() == 0) != (v2.IsNil() || v2.Len() == 0) {
  			return false
  		}
  		if v1.IsNil() || v1.Len() == 0 {
  			return true
  		}
  		if v1.Len() != v2.Len() {
  			return false
  		}
  		if v1.Pointer() == v2.Pointer() {
  			return true
  		}
  		for i := 0; i < v1.Len(); i++ {
  			if !e.deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Interface:
  		if v1.IsNil() || v2.IsNil() {
  			return v1.IsNil() == v2.IsNil()
  		}
  		return e.deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  	case reflect.Ptr:
  		return e.deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  	case reflect.Struct:
  		for i, n := 0, v1.NumField(); i < n; i++ {
  			if !e.deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Map:
  		if (v1.IsNil() || v1.Len() == 0) != (v2.IsNil() || v2.Len() == 0) {
  			return false
  		}
  		if v1.IsNil() || v1.Len() == 0 {
  			return true
  		}
  		if v1.Len() != v2.Len() {
  			return false
  		}
  		if v1.Pointer() == v2.Pointer() {
  			return true
  		}
  		for _, k := range v1.MapKeys() {
  			if !e.deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Func:
  		if v1.IsNil() && v2.IsNil() {
  			return true
  		}
  		// Can't do better than this:
  		return false
  	default:
  		// Normal equality suffices
  		if !v1.CanInterface() || !v2.CanInterface() {
  			panic(unexportedTypePanic{})
  		}
  		return v1.Interface() == v2.Interface()
  	}
  }
  
  // DeepEqual is like reflect.DeepEqual, but focused on semantic equality
  // instead of memory equality.
  //
  // It will use e's equality functions if it finds types that match.
  //
  // An empty slice *is* equal to a nil slice for our purposes; same for maps.
  //
  // Unexported field members cannot be compared and will cause an imformative panic; you must add an Equality
  // function for these types.
  func (e Equalities) DeepEqual(a1, a2 interface{}) bool {
  	if a1 == nil || a2 == nil {
  		return a1 == a2
  	}
  	v1 := reflect.ValueOf(a1)
  	v2 := reflect.ValueOf(a2)
  	if v1.Type() != v2.Type() {
  		return false
  	}
  	return e.deepValueEqual(v1, v2, make(map[visit]bool), 0)
  }
  
  func (e Equalities) deepValueDerive(v1, v2 reflect.Value, visited map[visit]bool, depth int) bool {
  	defer makeUsefulPanic(v1)
  
  	if !v1.IsValid() || !v2.IsValid() {
  		return v1.IsValid() == v2.IsValid()
  	}
  	if v1.Type() != v2.Type() {
  		return false
  	}
  	if fv, ok := e[v1.Type()]; ok {
  		return fv.Call([]reflect.Value{v1, v2})[0].Bool()
  	}
  
  	hard := func(k reflect.Kind) bool {
  		switch k {
  		case reflect.Array, reflect.Map, reflect.Slice, reflect.Struct:
  			return true
  		}
  		return false
  	}
  
  	if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) {
  		addr1 := v1.UnsafeAddr()
  		addr2 := v2.UnsafeAddr()
  		if addr1 > addr2 {
  			// Canonicalize order to reduce number of entries in visited.
  			addr1, addr2 = addr2, addr1
  		}
  
  		// Short circuit if references are identical ...
  		if addr1 == addr2 {
  			return true
  		}
  
  		// ... or 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 reflect.Array:
  		// We don't need to check length here because length is part of
  		// an array's type, which has already been filtered for.
  		for i := 0; i < v1.Len(); i++ {
  			if !e.deepValueDerive(v1.Index(i), v2.Index(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Slice:
  		if v1.IsNil() || v1.Len() == 0 {
  			return true
  		}
  		if v1.Len() > v2.Len() {
  			return false
  		}
  		if v1.Pointer() == v2.Pointer() {
  			return true
  		}
  		for i := 0; i < v1.Len(); i++ {
  			if !e.deepValueDerive(v1.Index(i), v2.Index(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.String:
  		if v1.Len() == 0 {
  			return true
  		}
  		if v1.Len() > v2.Len() {
  			return false
  		}
  		return v1.String() == v2.String()
  	case reflect.Interface:
  		if v1.IsNil() {
  			return true
  		}
  		return e.deepValueDerive(v1.Elem(), v2.Elem(), visited, depth+1)
  	case reflect.Ptr:
  		if v1.IsNil() {
  			return true
  		}
  		return e.deepValueDerive(v1.Elem(), v2.Elem(), visited, depth+1)
  	case reflect.Struct:
  		for i, n := 0, v1.NumField(); i < n; i++ {
  			if !e.deepValueDerive(v1.Field(i), v2.Field(i), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Map:
  		if v1.IsNil() || v1.Len() == 0 {
  			return true
  		}
  		if v1.Len() > v2.Len() {
  			return false
  		}
  		if v1.Pointer() == v2.Pointer() {
  			return true
  		}
  		for _, k := range v1.MapKeys() {
  			if !e.deepValueDerive(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
  				return false
  			}
  		}
  		return true
  	case reflect.Func:
  		if v1.IsNil() && v2.IsNil() {
  			return true
  		}
  		// Can't do better than this:
  		return false
  	default:
  		// Normal equality suffices
  		if !v1.CanInterface() || !v2.CanInterface() {
  			panic(unexportedTypePanic{})
  		}
  		return v1.Interface() == v2.Interface()
  	}
  }
  
  // DeepDerivative is similar to DeepEqual except that unset fields in a1 are
  // ignored (not compared). This allows us to focus on the fields that matter to
  // the semantic comparison.
  //
  // The unset fields include a nil pointer and an empty string.
  func (e Equalities) DeepDerivative(a1, a2 interface{}) bool {
  	if a1 == nil {
  		return true
  	}
  	v1 := reflect.ValueOf(a1)
  	v2 := reflect.ValueOf(a2)
  	if v1.Type() != v2.Type() {
  		return false
  	}
  	return e.deepValueDerive(v1, v2, make(map[visit]bool), 0)
  }
  