diff options
Diffstat (limited to 'vendor/github.com/google/go-cmp/cmp/compare.go')
| -rw-r--r-- | vendor/github.com/google/go-cmp/cmp/compare.go | 553 |
1 files changed, 0 insertions, 553 deletions
diff --git a/vendor/github.com/google/go-cmp/cmp/compare.go b/vendor/github.com/google/go-cmp/cmp/compare.go deleted file mode 100644 index 7e215f22..00000000 --- a/vendor/github.com/google/go-cmp/cmp/compare.go +++ /dev/null @@ -1,553 +0,0 @@ -// Copyright 2017, 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.md file. - -// Package cmp determines equality of values. -// -// This package is intended to be a more powerful and safer alternative to -// reflect.DeepEqual for comparing whether two values are semantically equal. -// -// The primary features of cmp are: -// -// • When the default behavior of equality does not suit the needs of the test, -// custom equality functions can override the equality operation. -// For example, an equality function may report floats as equal so long as they -// are within some tolerance of each other. -// -// • Types that have an Equal method may use that method to determine equality. -// This allows package authors to determine the equality operation for the types -// that they define. -// -// • If no custom equality functions are used and no Equal method is defined, -// equality is determined by recursively comparing the primitive kinds on both -// values, much like reflect.DeepEqual. Unlike reflect.DeepEqual, unexported -// fields are not compared by default; they result in panics unless suppressed -// by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly compared -// using the AllowUnexported option. -package cmp - -import ( - "fmt" - "reflect" - - "github.com/google/go-cmp/cmp/internal/diff" - "github.com/google/go-cmp/cmp/internal/function" - "github.com/google/go-cmp/cmp/internal/value" -) - -// BUG(dsnet): Maps with keys containing NaN values cannot be properly compared due to -// the reflection package's inability to retrieve such entries. Equal will panic -// anytime it comes across a NaN key, but this behavior may change. -// -// See https://golang.org/issue/11104 for more details. - -var nothing = reflect.Value{} - -// Equal reports whether x and y are equal by recursively applying the -// following rules in the given order to x and y and all of their sub-values: -// -// • If two values are not of the same type, then they are never equal -// and the overall result is false. -// -// • Let S be the set of all Ignore, Transformer, and Comparer options that -// remain after applying all path filters, value filters, and type filters. -// If at least one Ignore exists in S, then the comparison is ignored. -// If the number of Transformer and Comparer options in S is greater than one, -// then Equal panics because it is ambiguous which option to use. -// If S contains a single Transformer, then use that to transform the current -// values and recursively call Equal on the output values. -// If S contains a single Comparer, then use that to compare the current values. -// Otherwise, evaluation proceeds to the next rule. -// -// • If the values have an Equal method of the form "(T) Equal(T) bool" or -// "(T) Equal(I) bool" where T is assignable to I, then use the result of -// x.Equal(y) even if x or y is nil. -// Otherwise, no such method exists and evaluation proceeds to the next rule. -// -// • Lastly, try to compare x and y based on their basic kinds. -// Simple kinds like booleans, integers, floats, complex numbers, strings, and -// channels are compared using the equivalent of the == operator in Go. -// Functions are only equal if they are both nil, otherwise they are unequal. -// Pointers are equal if the underlying values they point to are also equal. -// Interfaces are equal if their underlying concrete values are also equal. -// -// Structs are equal if all of their fields are equal. If a struct contains -// unexported fields, Equal panics unless the AllowUnexported option is used or -// an Ignore option (e.g., cmpopts.IgnoreUnexported) ignores that field. -// -// Arrays, slices, and maps are equal if they are both nil or both non-nil -// with the same length and the elements at each index or key are equal. -// Note that a non-nil empty slice and a nil slice are not equal. -// To equate empty slices and maps, consider using cmpopts.EquateEmpty. -// Map keys are equal according to the == operator. -// To use custom comparisons for map keys, consider using cmpopts.SortMaps. -func Equal(x, y interface{}, opts ...Option) bool { - s := newState(opts) - s.compareAny(reflect.ValueOf(x), reflect.ValueOf(y)) - return s.result.Equal() -} - -// Diff returns a human-readable report of the differences between two values. -// It returns an empty string if and only if Equal returns true for the same -// input values and options. The output string will use the "-" symbol to -// indicate elements removed from x, and the "+" symbol to indicate elements -// added to y. -// -// Do not depend on this output being stable. -func Diff(x, y interface{}, opts ...Option) string { - r := new(defaultReporter) - opts = Options{Options(opts), r} - eq := Equal(x, y, opts...) - d := r.String() - if (d == "") != eq { - panic("inconsistent difference and equality results") - } - return d -} - -type state struct { - // These fields represent the "comparison state". - // Calling statelessCompare must not result in observable changes to these. - result diff.Result // The current result of comparison - curPath Path // The current path in the value tree - reporter reporter // Optional reporter used for difference formatting - - // dynChecker triggers pseudo-random checks for option correctness. - // It is safe for statelessCompare to mutate this value. - dynChecker dynChecker - - // These fields, once set by processOption, will not change. - exporters map[reflect.Type]bool // Set of structs with unexported field visibility - opts Options // List of all fundamental and filter options -} - -func newState(opts []Option) *state { - s := new(state) - for _, opt := range opts { - s.processOption(opt) - } - return s -} - -func (s *state) processOption(opt Option) { - switch opt := opt.(type) { - case nil: - case Options: - for _, o := range opt { - s.processOption(o) - } - case coreOption: - type filtered interface { - isFiltered() bool - } - if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() { - panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt)) - } - s.opts = append(s.opts, opt) - case visibleStructs: - if s.exporters == nil { - s.exporters = make(map[reflect.Type]bool) - } - for t := range opt { - s.exporters[t] = true - } - case reporter: - if s.reporter != nil { - panic("difference reporter already registered") - } - s.reporter = opt - default: - panic(fmt.Sprintf("unknown option %T", opt)) - } -} - -// statelessCompare compares two values and returns the result. -// This function is stateless in that it does not alter the current result, -// or output to any registered reporters. -func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result { - // We do not save and restore the curPath because all of the compareX - // methods should properly push and pop from the path. - // It is an implementation bug if the contents of curPath differs from - // when calling this function to when returning from it. - - oldResult, oldReporter := s.result, s.reporter - s.result = diff.Result{} // Reset result - s.reporter = nil // Remove reporter to avoid spurious printouts - s.compareAny(vx, vy) - res := s.result - s.result, s.reporter = oldResult, oldReporter - return res -} - -func (s *state) compareAny(vx, vy reflect.Value) { - // TODO: Support cyclic data structures. - - // Rule 0: Differing types are never equal. - if !vx.IsValid() || !vy.IsValid() { - s.report(vx.IsValid() == vy.IsValid(), vx, vy) - return - } - if vx.Type() != vy.Type() { - s.report(false, vx, vy) // Possible for path to be empty - return - } - t := vx.Type() - if len(s.curPath) == 0 { - s.curPath.push(&pathStep{typ: t}) - defer s.curPath.pop() - } - vx, vy = s.tryExporting(vx, vy) - - // Rule 1: Check whether an option applies on this node in the value tree. - if s.tryOptions(vx, vy, t) { - return - } - - // Rule 2: Check whether the type has a valid Equal method. - if s.tryMethod(vx, vy, t) { - return - } - - // Rule 3: Recursively descend into each value's underlying kind. - switch t.Kind() { - case reflect.Bool: - s.report(vx.Bool() == vy.Bool(), vx, vy) - return - case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: - s.report(vx.Int() == vy.Int(), vx, vy) - return - case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: - s.report(vx.Uint() == vy.Uint(), vx, vy) - return - case reflect.Float32, reflect.Float64: - s.report(vx.Float() == vy.Float(), vx, vy) - return - case reflect.Complex64, reflect.Complex128: - s.report(vx.Complex() == vy.Complex(), vx, vy) - return - case reflect.String: - s.report(vx.String() == vy.String(), vx, vy) - return - case reflect.Chan, reflect.UnsafePointer: - s.report(vx.Pointer() == vy.Pointer(), vx, vy) - return - case reflect.Func: - s.report(vx.IsNil() && vy.IsNil(), vx, vy) - return - case reflect.Ptr: - if vx.IsNil() || vy.IsNil() { - s.report(vx.IsNil() && vy.IsNil(), vx, vy) - return - } - s.curPath.push(&indirect{pathStep{t.Elem()}}) - defer s.curPath.pop() - s.compareAny(vx.Elem(), vy.Elem()) - return - case reflect.Interface: - if vx.IsNil() || vy.IsNil() { - s.report(vx.IsNil() && vy.IsNil(), vx, vy) - return - } - if vx.Elem().Type() != vy.Elem().Type() { - s.report(false, vx.Elem(), vy.Elem()) - return - } - s.curPath.push(&typeAssertion{pathStep{vx.Elem().Type()}}) - defer s.curPath.pop() - s.compareAny(vx.Elem(), vy.Elem()) - return - case reflect.Slice: - if vx.IsNil() || vy.IsNil() { - s.report(vx.IsNil() && vy.IsNil(), vx, vy) - return - } - fallthrough - case reflect.Array: - s.compareArray(vx, vy, t) - return - case reflect.Map: - s.compareMap(vx, vy, t) - return - case reflect.Struct: - s.compareStruct(vx, vy, t) - return - default: - panic(fmt.Sprintf("%v kind not handled", t.Kind())) - } -} - -func (s *state) tryExporting(vx, vy reflect.Value) (reflect.Value, reflect.Value) { - if sf, ok := s.curPath[len(s.curPath)-1].(*structField); ok && sf.unexported { - if sf.force { - // Use unsafe pointer arithmetic to get read-write access to an - // unexported field in the struct. - vx = unsafeRetrieveField(sf.pvx, sf.field) - vy = unsafeRetrieveField(sf.pvy, sf.field) - } else { - // We are not allowed to export the value, so invalidate them - // so that tryOptions can panic later if not explicitly ignored. - vx = nothing - vy = nothing - } - } - return vx, vy -} - -func (s *state) tryOptions(vx, vy reflect.Value, t reflect.Type) bool { - // If there were no FilterValues, we will not detect invalid inputs, - // so manually check for them and append invalid if necessary. - // We still evaluate the options since an ignore can override invalid. - opts := s.opts - if !vx.IsValid() || !vy.IsValid() { - opts = Options{opts, invalid{}} - } - - // Evaluate all filters and apply the remaining options. - if opt := opts.filter(s, vx, vy, t); opt != nil { - opt.apply(s, vx, vy) - return true - } - return false -} - -func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool { - // Check if this type even has an Equal method. - m, ok := t.MethodByName("Equal") - if !ok || !function.IsType(m.Type, function.EqualAssignable) { - return false - } - - eq := s.callTTBFunc(m.Func, vx, vy) - s.report(eq, vx, vy) - return true -} - -func (s *state) callTRFunc(f, v reflect.Value) reflect.Value { - v = sanitizeValue(v, f.Type().In(0)) - if !s.dynChecker.Next() { - return f.Call([]reflect.Value{v})[0] - } - - // Run the function twice and ensure that we get the same results back. - // We run in goroutines so that the race detector (if enabled) can detect - // unsafe mutations to the input. - c := make(chan reflect.Value) - go detectRaces(c, f, v) - want := f.Call([]reflect.Value{v})[0] - if got := <-c; !s.statelessCompare(got, want).Equal() { - // To avoid false-positives with non-reflexive equality operations, - // we sanity check whether a value is equal to itself. - if !s.statelessCompare(want, want).Equal() { - return want - } - fn := getFuncName(f.Pointer()) - panic(fmt.Sprintf("non-deterministic function detected: %s", fn)) - } - return want -} - -func (s *state) callTTBFunc(f, x, y reflect.Value) bool { - x = sanitizeValue(x, f.Type().In(0)) - y = sanitizeValue(y, f.Type().In(1)) - if !s.dynChecker.Next() { - return f.Call([]reflect.Value{x, y})[0].Bool() - } - - // Swapping the input arguments is sufficient to check that - // f is symmetric and deterministic. - // We run in goroutines so that the race detector (if enabled) can detect - // unsafe mutations to the input. - c := make(chan reflect.Value) - go detectRaces(c, f, y, x) - want := f.Call([]reflect.Value{x, y})[0].Bool() - if got := <-c; !got.IsValid() || got.Bool() != want { - fn := getFuncName(f.Pointer()) - panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", fn)) - } - return want -} - -func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) { - var ret reflect.Value - defer func() { - recover() // Ignore panics, let the other call to f panic instead - c <- ret - }() - ret = f.Call(vs)[0] -} - -// sanitizeValue converts nil interfaces of type T to those of type R, -// assuming that T is assignable to R. -// Otherwise, it returns the input value as is. -func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value { - // TODO(dsnet): Remove this hacky workaround. - // See https://golang.org/issue/22143 - if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t { - return reflect.New(t).Elem() - } - return v -} - -func (s *state) compareArray(vx, vy reflect.Value, t reflect.Type) { - step := &sliceIndex{pathStep{t.Elem()}, 0, 0} - s.curPath.push(step) - - // Compute an edit-script for slices vx and vy. - es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result { - step.xkey, step.ykey = ix, iy - return s.statelessCompare(vx.Index(ix), vy.Index(iy)) - }) - - // Report the entire slice as is if the arrays are of primitive kind, - // and the arrays are different enough. - isPrimitive := false - switch t.Elem().Kind() { - case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, - reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr, - reflect.Bool, reflect.Float32, reflect.Float64, reflect.Complex64, reflect.Complex128: - isPrimitive = true - } - if isPrimitive && es.Dist() > (vx.Len()+vy.Len())/4 { - s.curPath.pop() // Pop first since we are reporting the whole slice - s.report(false, vx, vy) - return - } - - // Replay the edit-script. - var ix, iy int - for _, e := range es { - switch e { - case diff.UniqueX: - step.xkey, step.ykey = ix, -1 - s.report(false, vx.Index(ix), nothing) - ix++ - case diff.UniqueY: - step.xkey, step.ykey = -1, iy - s.report(false, nothing, vy.Index(iy)) - iy++ - default: - step.xkey, step.ykey = ix, iy - if e == diff.Identity { - s.report(true, vx.Index(ix), vy.Index(iy)) - } else { - s.compareAny(vx.Index(ix), vy.Index(iy)) - } - ix++ - iy++ - } - } - s.curPath.pop() - return -} - -func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) { - if vx.IsNil() || vy.IsNil() { - s.report(vx.IsNil() && vy.IsNil(), vx, vy) - return - } - - // We combine and sort the two map keys so that we can perform the - // comparisons in a deterministic order. - step := &mapIndex{pathStep: pathStep{t.Elem()}} - s.curPath.push(step) - defer s.curPath.pop() - for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) { - step.key = k - vvx := vx.MapIndex(k) - vvy := vy.MapIndex(k) - switch { - case vvx.IsValid() && vvy.IsValid(): - s.compareAny(vvx, vvy) - case vvx.IsValid() && !vvy.IsValid(): - s.report(false, vvx, nothing) - case !vvx.IsValid() && vvy.IsValid(): - s.report(false, nothing, vvy) - default: - // It is possible for both vvx and vvy to be invalid if the - // key contained a NaN value in it. There is no way in - // reflection to be able to retrieve these values. - // See https://golang.org/issue/11104 - panic(fmt.Sprintf("%#v has map key with NaNs", s.curPath)) - } - } -} - -func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) { - var vax, vay reflect.Value // Addressable versions of vx and vy - - step := &structField{} - s.curPath.push(step) - defer s.curPath.pop() - for i := 0; i < t.NumField(); i++ { - vvx := vx.Field(i) - vvy := vy.Field(i) - step.typ = t.Field(i).Type - step.name = t.Field(i).Name - step.idx = i - step.unexported = !isExported(step.name) - if step.unexported { - // Defer checking of unexported fields until later to give an - // Ignore a chance to ignore the field. - if !vax.IsValid() || !vay.IsValid() { - // For unsafeRetrieveField to work, the parent struct must - // be addressable. Create a new copy of the values if - // necessary to make them addressable. - vax = makeAddressable(vx) - vay = makeAddressable(vy) - } - step.force = s.exporters[t] - step.pvx = vax - step.pvy = vay - step.field = t.Field(i) - } - s.compareAny(vvx, vvy) - } -} - -// report records the result of a single comparison. -// It also calls Report if any reporter is registered. -func (s *state) report(eq bool, vx, vy reflect.Value) { - if eq { - s.result.NSame++ - } else { - s.result.NDiff++ - } - if s.reporter != nil { - s.reporter.Report(vx, vy, eq, s.curPath) - } -} - -// dynChecker tracks the state needed to periodically perform checks that -// user provided functions are symmetric and deterministic. -// The zero value is safe for immediate use. -type dynChecker struct{ curr, next int } - -// Next increments the state and reports whether a check should be performed. -// -// Checks occur every Nth function call, where N is a triangular number: -// 0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 ... -// See https://en.wikipedia.org/wiki/Triangular_number -// -// This sequence ensures that the cost of checks drops significantly as -// the number of functions calls grows larger. -func (dc *dynChecker) Next() bool { - ok := dc.curr == dc.next - if ok { - dc.curr = 0 - dc.next++ - } - dc.curr++ - return ok -} - -// makeAddressable returns a value that is always addressable. -// It returns the input verbatim if it is already addressable, -// otherwise it creates a new value and returns an addressable copy. -func makeAddressable(v reflect.Value) reflect.Value { - if v.CanAddr() { - return v - } - vc := reflect.New(v.Type()).Elem() - vc.Set(v) - return vc -} |