vendor/github.com/google/go-cmp/cmp/compare.go

   1 // Copyright 2017, 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.md file.
   4
   5 // Package cmp determines equality of values.
   6 //
   7 // This package is intended to be a more powerful and safer alternative to
   8 // reflect.DeepEqual for comparing whether two values are semantically equal.
   9 //
  10 // The primary features of cmp are:
  11 //
  12 // • When the default behavior of equality does not suit the needs of the test,
  13 // custom equality functions can override the equality operation.
  14 // For example, an equality function may report floats as equal so long as they
  15 // are within some tolerance of each other.
  16 //
  17 // • Types that have an Equal method may use that method to determine equality.
  18 // This allows package authors to determine the equality operation for the types
  19 // that they define.
  20 //
  21 // • If no custom equality functions are used and no Equal method is defined,
  22 // equality is determined by recursively comparing the primitive kinds on both
  23 // values, much like reflect.DeepEqual. Unlike reflect.DeepEqual, unexported
  24 // fields are not compared by default; they result in panics unless suppressed
  25 // by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly compared
  26 // using the AllowUnexported option.
  27 package cmp
  28
  29 import (
  30         "fmt"
  31         "reflect"
  32
  33         "github.com/google/go-cmp/cmp/internal/diff"
  34         "github.com/google/go-cmp/cmp/internal/function"
  35         "github.com/google/go-cmp/cmp/internal/value"
  36 )
  37
  38 // BUG(dsnet): Maps with keys containing NaN values cannot be properly compared due to
  39 // the reflection package's inability to retrieve such entries. Equal will panic
  40 // anytime it comes across a NaN key, but this behavior may change.
  41 //
  42 // See https://golang.org/issue/11104 for more details.
  43
  44 var nothing = reflect.Value{}
  45
  46 // Equal reports whether x and y are equal by recursively applying the
  47 // following rules in the given order to x and y and all of their sub-values:
  48 //
  49 // • If two values are not of the same type, then they are never equal
  50 // and the overall result is false.
  51 //
  52 // • Let S be the set of all Ignore, Transformer, and Comparer options that
  53 // remain after applying all path filters, value filters, and type filters.
  54 // If at least one Ignore exists in S, then the comparison is ignored.
  55 // If the number of Transformer and Comparer options in S is greater than one,
  56 // then Equal panics because it is ambiguous which option to use.
  57 // If S contains a single Transformer, then use that to transform the current
  58 // values and recursively call Equal on the output values.
  59 // If S contains a single Comparer, then use that to compare the current values.
  60 // Otherwise, evaluation proceeds to the next rule.
  61 //
  62 // • If the values have an Equal method of the form "(T) Equal(T) bool" or
  63 // "(T) Equal(I) bool" where T is assignable to I, then use the result of
  64 // x.Equal(y) even if x or y is nil.
  65 // Otherwise, no such method exists and evaluation proceeds to the next rule.
  66 //
  67 // • Lastly, try to compare x and y based on their basic kinds.
  68 // Simple kinds like booleans, integers, floats, complex numbers, strings, and
  69 // channels are compared using the equivalent of the == operator in Go.
  70 // Functions are only equal if they are both nil, otherwise they are unequal.
  71 // Pointers are equal if the underlying values they point to are also equal.
  72 // Interfaces are equal if their underlying concrete values are also equal.
  73 //
  74 // Structs are equal if all of their fields are equal. If a struct contains
  75 // unexported fields, Equal panics unless the AllowUnexported option is used or
  76 // an Ignore option (e.g., cmpopts.IgnoreUnexported) ignores that field.
  77 //
  78 // Arrays, slices, and maps are equal if they are both nil or both non-nil
  79 // with the same length and the elements at each index or key are equal.
  80 // Note that a non-nil empty slice and a nil slice are not equal.
  81 // To equate empty slices and maps, consider using cmpopts.EquateEmpty.
  82 // Map keys are equal according to the == operator.
  83 // To use custom comparisons for map keys, consider using cmpopts.SortMaps.
  84 func Equal(x, y interface{}, opts ...Option) bool {
  85         s := newState(opts)
  86         s.compareAny(reflect.ValueOf(x), reflect.ValueOf(y))
  87         return s.result.Equal()
  88 }
  89
  90 // Diff returns a human-readable report of the differences between two values.
  91 // It returns an empty string if and only if Equal returns true for the same
  92 // input values and options. The output string will use the "-" symbol to
  93 // indicate elements removed from x, and the "+" symbol to indicate elements
  94 // added to y.
  95 //
  96 // Do not depend on this output being stable.
  97 func Diff(x, y interface{}, opts ...Option) string {
  98         r := new(defaultReporter)
  99         opts = Options{Options(opts), r}
 100         eq := Equal(x, y, opts...)
 101         d := r.String()
 102         if (d == "") != eq {
 103                 panic("inconsistent difference and equality results")
 104         }
 105         return d
 106 }
 107
 108 type state struct {
 109         // These fields represent the "comparison state".
 110         // Calling statelessCompare must not result in observable changes to these.
 111         result   diff.Result // The current result of comparison
 112         curPath  Path        // The current path in the value tree
 113         reporter reporter    // Optional reporter used for difference formatting
 114
 115         // dynChecker triggers pseudo-random checks for option correctness.
 116         // It is safe for statelessCompare to mutate this value.
 117         dynChecker dynChecker
 118
 119         // These fields, once set by processOption, will not change.
 120         exporters map[reflect.Type]bool // Set of structs with unexported field visibility
 121         opts      Options               // List of all fundamental and filter options
 122 }
 123
 124 func newState(opts []Option) *state {
 125         s := new(state)
 126         for _, opt := range opts {
 127                 s.processOption(opt)
 128         }
 129         return s
 130 }
 131
 132 func (s *state) processOption(opt Option) {
 133         switch opt := opt.(type) {
 134         case nil:
 135         case Options:
 136                 for _, o := range opt {
 137                         s.processOption(o)
 138                 }
 139         case coreOption:
 140                 type filtered interface {
 141                         isFiltered() bool
 142                 }
 143                 if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() {
 144                         panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt))
 145                 }
 146                 s.opts = append(s.opts, opt)
 147         case visibleStructs:
 148                 if s.exporters == nil {
 149                         s.exporters = make(map[reflect.Type]bool)
 150                 }
 151                 for t := range opt {
 152                         s.exporters[t] = true
 153                 }
 154         case reporter:
 155                 if s.reporter != nil {
 156                         panic("difference reporter already registered")
 157                 }
 158                 s.reporter = opt
 159         default:
 160                 panic(fmt.Sprintf("unknown option %T", opt))
 161         }
 162 }
 163
 164 // statelessCompare compares two values and returns the result.
 165 // This function is stateless in that it does not alter the current result,
 166 // or output to any registered reporters.
 167 func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result {
 168         // We do not save and restore the curPath because all of the compareX
 169         // methods should properly push and pop from the path.
 170         // It is an implementation bug if the contents of curPath differs from
 171         // when calling this function to when returning from it.
 172
 173         oldResult, oldReporter := s.result, s.reporter
 174         s.result = diff.Result{} // Reset result
 175         s.reporter = nil         // Remove reporter to avoid spurious printouts
 176         s.compareAny(vx, vy)
 177         res := s.result
 178         s.result, s.reporter = oldResult, oldReporter
 179         return res
 180 }
 181
 182 func (s *state) compareAny(vx, vy reflect.Value) {
 183         // TODO: Support cyclic data structures.
 184
 185         // Rule 0: Differing types are never equal.
 186         if !vx.IsValid() || !vy.IsValid() {
 187                 s.report(vx.IsValid() == vy.IsValid(), vx, vy)
 188                 return
 189         }
 190         if vx.Type() != vy.Type() {
 191                 s.report(false, vx, vy) // Possible for path to be empty
 192                 return
 193         }
 194         t := vx.Type()
 195         if len(s.curPath) == 0 {
 196                 s.curPath.push(&pathStep{typ: t})
 197                 defer s.curPath.pop()
 198         }
 199         vx, vy = s.tryExporting(vx, vy)
 200
 201         // Rule 1: Check whether an option applies on this node in the value tree.
 202         if s.tryOptions(vx, vy, t) {
 203                 return
 204         }
 205
 206         // Rule 2: Check whether the type has a valid Equal method.
 207         if s.tryMethod(vx, vy, t) {
 208                 return
 209         }
 210
 211         // Rule 3: Recursively descend into each value's underlying kind.
 212         switch t.Kind() {
 213         case reflect.Bool:
 214                 s.report(vx.Bool() == vy.Bool(), vx, vy)
 215                 return
 216         case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
 217                 s.report(vx.Int() == vy.Int(), vx, vy)
 218                 return
 219         case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
 220                 s.report(vx.Uint() == vy.Uint(), vx, vy)
 221                 return
 222         case reflect.Float32, reflect.Float64:
 223                 s.report(vx.Float() == vy.Float(), vx, vy)
 224                 return
 225         case reflect.Complex64, reflect.Complex128:
 226                 s.report(vx.Complex() == vy.Complex(), vx, vy)
 227                 return
 228         case reflect.String:
 229                 s.report(vx.String() == vy.String(), vx, vy)
 230                 return
 231         case reflect.Chan, reflect.UnsafePointer:
 232                 s.report(vx.Pointer() == vy.Pointer(), vx, vy)
 233                 return
 234         case reflect.Func:
 235                 s.report(vx.IsNil() && vy.IsNil(), vx, vy)
 236                 return
 237         case reflect.Ptr:
 238                 if vx.IsNil() || vy.IsNil() {
 239                         s.report(vx.IsNil() && vy.IsNil(), vx, vy)
 240                         return
 241                 }
 242                 s.curPath.push(&indirect{pathStep{t.Elem()}})
 243                 defer s.curPath.pop()
 244                 s.compareAny(vx.Elem(), vy.Elem())
 245                 return
 246         case reflect.Interface:
 247                 if vx.IsNil() || vy.IsNil() {
 248                         s.report(vx.IsNil() && vy.IsNil(), vx, vy)
 249                         return
 250                 }
 251                 if vx.Elem().Type() != vy.Elem().Type() {
 252                         s.report(false, vx.Elem(), vy.Elem())
 253                         return
 254                 }
 255                 s.curPath.push(&typeAssertion{pathStep{vx.Elem().Type()}})
 256                 defer s.curPath.pop()
 257                 s.compareAny(vx.Elem(), vy.Elem())
 258                 return
 259         case reflect.Slice:
 260                 if vx.IsNil() || vy.IsNil() {
 261                         s.report(vx.IsNil() && vy.IsNil(), vx, vy)
 262                         return
 263                 }
 264                 fallthrough
 265         case reflect.Array:
 266                 s.compareArray(vx, vy, t)
 267                 return
 268         case reflect.Map:
 269                 s.compareMap(vx, vy, t)
 270                 return
 271         case reflect.Struct:
 272                 s.compareStruct(vx, vy, t)
 273                 return
 274         default:
 275                 panic(fmt.Sprintf("%v kind not handled", t.Kind()))
 276         }
 277 }
 278
 279 func (s *state) tryExporting(vx, vy reflect.Value) (reflect.Value, reflect.Value) {
 280         if sf, ok := s.curPath[len(s.curPath)-1].(*structField); ok && sf.unexported {
 281                 if sf.force {
 282                         // Use unsafe pointer arithmetic to get read-write access to an
 283                         // unexported field in the struct.
 284                         vx = unsafeRetrieveField(sf.pvx, sf.field)
 285                         vy = unsafeRetrieveField(sf.pvy, sf.field)
 286                 } else {
 287                         // We are not allowed to export the value, so invalidate them
 288                         // so that tryOptions can panic later if not explicitly ignored.
 289                         vx = nothing
 290                         vy = nothing
 291                 }
 292         }
 293         return vx, vy
 294 }
 295
 296 func (s *state) tryOptions(vx, vy reflect.Value, t reflect.Type) bool {
 297         // If there were no FilterValues, we will not detect invalid inputs,
 298         // so manually check for them and append invalid if necessary.
 299         // We still evaluate the options since an ignore can override invalid.
 300         opts := s.opts
 301         if !vx.IsValid() || !vy.IsValid() {
 302                 opts = Options{opts, invalid{}}
 303         }
 304
 305         // Evaluate all filters and apply the remaining options.
 306         if opt := opts.filter(s, vx, vy, t); opt != nil {
 307                 opt.apply(s, vx, vy)
 308                 return true
 309         }
 310         return false
 311 }
 312
 313 func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool {
 314         // Check if this type even has an Equal method.
 315         m, ok := t.MethodByName("Equal")
 316         if !ok || !function.IsType(m.Type, function.EqualAssignable) {
 317                 return false
 318         }
 319
 320         eq := s.callTTBFunc(m.Func, vx, vy)
 321         s.report(eq, vx, vy)
 322         return true
 323 }
 324
 325 func (s *state) callTRFunc(f, v reflect.Value) reflect.Value {
 326         v = sanitizeValue(v, f.Type().In(0))
 327         if !s.dynChecker.Next() {
 328                 return f.Call([]reflect.Value{v})[0]
 329         }
 330
 331         // Run the function twice and ensure that we get the same results back.
 332         // We run in goroutines so that the race detector (if enabled) can detect
 333         // unsafe mutations to the input.
 334         c := make(chan reflect.Value)
 335         go detectRaces(c, f, v)
 336         want := f.Call([]reflect.Value{v})[0]
 337         if got := <-c; !s.statelessCompare(got, want).Equal() {
 338                 // To avoid false-positives with non-reflexive equality operations,
 339                 // we sanity check whether a value is equal to itself.
 340                 if !s.statelessCompare(want, want).Equal() {
 341                         return want
 342                 }
 343                 fn := getFuncName(f.Pointer())
 344                 panic(fmt.Sprintf("non-deterministic function detected: %s", fn))
 345         }
 346         return want
 347 }
 348
 349 func (s *state) callTTBFunc(f, x, y reflect.Value) bool {
 350         x = sanitizeValue(x, f.Type().In(0))
 351         y = sanitizeValue(y, f.Type().In(1))
 352         if !s.dynChecker.Next() {
 353                 return f.Call([]reflect.Value{x, y})[0].Bool()
 354         }
 355
 356         // Swapping the input arguments is sufficient to check that
 357         // f is symmetric and deterministic.
 358         // We run in goroutines so that the race detector (if enabled) can detect
 359         // unsafe mutations to the input.
 360         c := make(chan reflect.Value)
 361         go detectRaces(c, f, y, x)
 362         want := f.Call([]reflect.Value{x, y})[0].Bool()
 363         if got := <-c; !got.IsValid() || got.Bool() != want {
 364                 fn := getFuncName(f.Pointer())
 365                 panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", fn))
 366         }
 367         return want
 368 }
 369
 370 func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) {
 371         var ret reflect.Value
 372         defer func() {
 373                 recover() // Ignore panics, let the other call to f panic instead
 374                 c <- ret
 375         }()
 376         ret = f.Call(vs)[0]
 377 }
 378
 379 // sanitizeValue converts nil interfaces of type T to those of type R,
 380 // assuming that T is assignable to R.
 381 // Otherwise, it returns the input value as is.
 382 func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value {
 383         // TODO(dsnet): Remove this hacky workaround.
 384         // See https://golang.org/issue/22143
 385         if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t {
 386                 return reflect.New(t).Elem()
 387         }
 388         return v
 389 }
 390
 391 func (s *state) compareArray(vx, vy reflect.Value, t reflect.Type) {
 392         step := &sliceIndex{pathStep{t.Elem()}, 0, 0}
 393         s.curPath.push(step)
 394
 395         // Compute an edit-script for slices vx and vy.
 396         es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result {
 397                 step.xkey, step.ykey = ix, iy
 398                 return s.statelessCompare(vx.Index(ix), vy.Index(iy))
 399         })
 400
 401         // Report the entire slice as is if the arrays are of primitive kind,
 402         // and the arrays are different enough.
 403         isPrimitive := false
 404         switch t.Elem().Kind() {
 405         case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
 406                 reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr,
 407                 reflect.Bool, reflect.Float32, reflect.Float64, reflect.Complex64, reflect.Complex128:
 408                 isPrimitive = true
 409         }
 410         if isPrimitive && es.Dist() > (vx.Len()+vy.Len())/4 {
 411                 s.curPath.pop() // Pop first since we are reporting the whole slice
 412                 s.report(false, vx, vy)
 413                 return
 414         }
 415
 416         // Replay the edit-script.
 417         var ix, iy int
 418         for _, e := range es {
 419                 switch e {
 420                 case diff.UniqueX:
 421                         step.xkey, step.ykey = ix, -1
 422                         s.report(false, vx.Index(ix), nothing)
 423                         ix++
 424                 case diff.UniqueY:
 425                         step.xkey, step.ykey = -1, iy
 426                         s.report(false, nothing, vy.Index(iy))
 427                         iy++
 428                 default:
 429                         step.xkey, step.ykey = ix, iy
 430                         if e == diff.Identity {
 431                                 s.report(true, vx.Index(ix), vy.Index(iy))
 432                         } else {
 433                                 s.compareAny(vx.Index(ix), vy.Index(iy))
 434                         }
 435                         ix++
 436                         iy++
 437                 }
 438         }
 439         s.curPath.pop()
 440         return
 441 }
 442
 443 func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
 444         if vx.IsNil() || vy.IsNil() {
 445                 s.report(vx.IsNil() && vy.IsNil(), vx, vy)
 446                 return
 447         }
 448
 449         // We combine and sort the two map keys so that we can perform the
 450         // comparisons in a deterministic order.
 451         step := &mapIndex{pathStep: pathStep{t.Elem()}}
 452         s.curPath.push(step)
 453         defer s.curPath.pop()
 454         for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) {
 455                 step.key = k
 456                 vvx := vx.MapIndex(k)
 457                 vvy := vy.MapIndex(k)
 458                 switch {
 459                 case vvx.IsValid() && vvy.IsValid():
 460                         s.compareAny(vvx, vvy)
 461                 case vvx.IsValid() && !vvy.IsValid():
 462                         s.report(false, vvx, nothing)
 463                 case !vvx.IsValid() && vvy.IsValid():
 464                         s.report(false, nothing, vvy)
 465                 default:
 466                         // It is possible for both vvx and vvy to be invalid if the
 467                         // key contained a NaN value in it. There is no way in
 468                         // reflection to be able to retrieve these values.
 469                         // See https://golang.org/issue/11104
 470                         panic(fmt.Sprintf("%#v has map key with NaNs", s.curPath))
 471                 }
 472         }
 473 }
 474
 475 func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
 476         var vax, vay reflect.Value // Addressable versions of vx and vy
 477
 478         step := &structField{}
 479         s.curPath.push(step)
 480         defer s.curPath.pop()
 481         for i := 0; i < t.NumField(); i++ {
 482                 vvx := vx.Field(i)
 483                 vvy := vy.Field(i)
 484                 step.typ = t.Field(i).Type
 485                 step.name = t.Field(i).Name
 486                 step.idx = i
 487                 step.unexported = !isExported(step.name)
 488                 if step.unexported {
 489                         // Defer checking of unexported fields until later to give an
 490                         // Ignore a chance to ignore the field.
 491                         if !vax.IsValid() || !vay.IsValid() {
 492                                 // For unsafeRetrieveField to work, the parent struct must
 493                                 // be addressable. Create a new copy of the values if
 494                                 // necessary to make them addressable.
 495                                 vax = makeAddressable(vx)
 496                                 vay = makeAddressable(vy)
 497                         }
 498                         step.force = s.exporters[t]
 499                         step.pvx = vax
 500                         step.pvy = vay
 501                         step.field = t.Field(i)
 502                 }
 503                 s.compareAny(vvx, vvy)
 504         }
 505 }
 506
 507 // report records the result of a single comparison.
 508 // It also calls Report if any reporter is registered.
 509 func (s *state) report(eq bool, vx, vy reflect.Value) {
 510         if eq {
 511                 s.result.NSame++
 512         } else {
 513                 s.result.NDiff++
 514         }
 515         if s.reporter != nil {
 516                 s.reporter.Report(vx, vy, eq, s.curPath)
 517         }
 518 }
 519
 520 // dynChecker tracks the state needed to periodically perform checks that
 521 // user provided functions are symmetric and deterministic.
 522 // The zero value is safe for immediate use.
 523 type dynChecker struct{ curr, next int }
 524
 525 // Next increments the state and reports whether a check should be performed.
 526 //
 527 // Checks occur every Nth function call, where N is a triangular number:
 528 //      0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 ...
 529 // See https://en.wikipedia.org/wiki/Triangular_number
 530 //
 531 // This sequence ensures that the cost of checks drops significantly as
 532 // the number of functions calls grows larger.
 533 func (dc *dynChecker) Next() bool {
 534         ok := dc.curr == dc.next
 535         if ok {
 536                 dc.curr = 0
 537                 dc.next++
 538         }
 539         dc.curr++
 540         return ok
 541 }
 542
 543 // makeAddressable returns a value that is always addressable.
 544 // It returns the input verbatim if it is already addressable,
 545 // otherwise it creates a new value and returns an addressable copy.
 546 func makeAddressable(v reflect.Value) reflect.Value {
 547         if v.CanAddr() {
 548                 return v
 549         }
 550         vc := reflect.New(v.Type()).Elem()
 551         vc.Set(v)
 552         return vc
 553 }