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. 27package cmp 28 29import ( 30 "fmt" 31 "reflect" 32 "strings" 33 34 "github.com/google/go-cmp/cmp/internal/diff" 35 "github.com/google/go-cmp/cmp/internal/flags" 36 "github.com/google/go-cmp/cmp/internal/function" 37 "github.com/google/go-cmp/cmp/internal/value" 38) 39 40// Equal reports whether x and y are equal by recursively applying the 41// following rules in the given order to x and y and all of their sub-values: 42// 43// • Let S be the set of all Ignore, Transformer, and Comparer options that 44// remain after applying all path filters, value filters, and type filters. 45// If at least one Ignore exists in S, then the comparison is ignored. 46// If the number of Transformer and Comparer options in S is greater than one, 47// then Equal panics because it is ambiguous which option to use. 48// If S contains a single Transformer, then use that to transform the current 49// values and recursively call Equal on the output values. 50// If S contains a single Comparer, then use that to compare the current values. 51// Otherwise, evaluation proceeds to the next rule. 52// 53// • If the values have an Equal method of the form "(T) Equal(T) bool" or 54// "(T) Equal(I) bool" where T is assignable to I, then use the result of 55// x.Equal(y) even if x or y is nil. Otherwise, no such method exists and 56// evaluation proceeds to the next rule. 57// 58// • Lastly, try to compare x and y based on their basic kinds. 59// Simple kinds like booleans, integers, floats, complex numbers, strings, and 60// channels are compared using the equivalent of the == operator in Go. 61// Functions are only equal if they are both nil, otherwise they are unequal. 62// 63// Structs are equal if recursively calling Equal on all fields report equal. 64// If a struct contains unexported fields, Equal panics unless an Ignore option 65// (e.g., cmpopts.IgnoreUnexported) ignores that field or the AllowUnexported 66// option explicitly permits comparing the unexported field. 67// 68// Slices are equal if they are both nil or both non-nil, where recursively 69// calling Equal on all non-ignored slice or array elements report equal. 70// Empty non-nil slices and nil slices are not equal; to equate empty slices, 71// consider using cmpopts.EquateEmpty. 72// 73// Maps are equal if they are both nil or both non-nil, where recursively 74// calling Equal on all non-ignored map entries report equal. 75// Map keys are equal according to the == operator. 76// To use custom comparisons for map keys, consider using cmpopts.SortMaps. 77// Empty non-nil maps and nil maps are not equal; to equate empty maps, 78// consider using cmpopts.EquateEmpty. 79// 80// Pointers and interfaces are equal if they are both nil or both non-nil, 81// where they have the same underlying concrete type and recursively 82// calling Equal on the underlying values reports equal. 83func Equal(x, y interface{}, opts ...Option) bool { 84 vx := reflect.ValueOf(x) 85 vy := reflect.ValueOf(y) 86 87 // If the inputs are different types, auto-wrap them in an empty interface 88 // so that they have the same parent type. 89 var t reflect.Type 90 if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() { 91 t = reflect.TypeOf((*interface{})(nil)).Elem() 92 if vx.IsValid() { 93 vvx := reflect.New(t).Elem() 94 vvx.Set(vx) 95 vx = vvx 96 } 97 if vy.IsValid() { 98 vvy := reflect.New(t).Elem() 99 vvy.Set(vy) 100 vy = vvy 101 } 102 } else { 103 t = vx.Type() 104 } 105 106 s := newState(opts) 107 s.compareAny(&pathStep{t, vx, vy}) 108 return s.result.Equal() 109} 110 111// Diff returns a human-readable report of the differences between two values. 112// It returns an empty string if and only if Equal returns true for the same 113// input values and options. 114// 115// The output is displayed as a literal in pseudo-Go syntax. 116// At the start of each line, a "-" prefix indicates an element removed from x, 117// a "+" prefix to indicates an element added to y, and the lack of a prefix 118// indicates an element common to both x and y. If possible, the output 119// uses fmt.Stringer.String or error.Error methods to produce more humanly 120// readable outputs. In such cases, the string is prefixed with either an 121// 's' or 'e' character, respectively, to indicate that the method was called. 122// 123// Do not depend on this output being stable. If you need the ability to 124// programmatically interpret the difference, consider using a custom Reporter. 125func Diff(x, y interface{}, opts ...Option) string { 126 r := new(defaultReporter) 127 eq := Equal(x, y, Options(opts), Reporter(r)) 128 d := r.String() 129 if (d == "") != eq { 130 panic("inconsistent difference and equality results") 131 } 132 return d 133} 134 135type state struct { 136 // These fields represent the "comparison state". 137 // Calling statelessCompare must not result in observable changes to these. 138 result diff.Result // The current result of comparison 139 curPath Path // The current path in the value tree 140 reporters []reporter // Optional reporters 141 142 // recChecker checks for infinite cycles applying the same set of 143 // transformers upon the output of itself. 144 recChecker recChecker 145 146 // dynChecker triggers pseudo-random checks for option correctness. 147 // It is safe for statelessCompare to mutate this value. 148 dynChecker dynChecker 149 150 // These fields, once set by processOption, will not change. 151 exporters map[reflect.Type]bool // Set of structs with unexported field visibility 152 opts Options // List of all fundamental and filter options 153} 154 155func newState(opts []Option) *state { 156 // Always ensure a validator option exists to validate the inputs. 157 s := &state{opts: Options{validator{}}} 158 s.processOption(Options(opts)) 159 return s 160} 161 162func (s *state) processOption(opt Option) { 163 switch opt := opt.(type) { 164 case nil: 165 case Options: 166 for _, o := range opt { 167 s.processOption(o) 168 } 169 case coreOption: 170 type filtered interface { 171 isFiltered() bool 172 } 173 if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() { 174 panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt)) 175 } 176 s.opts = append(s.opts, opt) 177 case visibleStructs: 178 if s.exporters == nil { 179 s.exporters = make(map[reflect.Type]bool) 180 } 181 for t := range opt { 182 s.exporters[t] = true 183 } 184 case reporter: 185 s.reporters = append(s.reporters, opt) 186 default: 187 panic(fmt.Sprintf("unknown option %T", opt)) 188 } 189} 190 191// statelessCompare compares two values and returns the result. 192// This function is stateless in that it does not alter the current result, 193// or output to any registered reporters. 194func (s *state) statelessCompare(step PathStep) diff.Result { 195 // We do not save and restore the curPath because all of the compareX 196 // methods should properly push and pop from the path. 197 // It is an implementation bug if the contents of curPath differs from 198 // when calling this function to when returning from it. 199 200 oldResult, oldReporters := s.result, s.reporters 201 s.result = diff.Result{} // Reset result 202 s.reporters = nil // Remove reporters to avoid spurious printouts 203 s.compareAny(step) 204 res := s.result 205 s.result, s.reporters = oldResult, oldReporters 206 return res 207} 208 209func (s *state) compareAny(step PathStep) { 210 // Update the path stack. 211 s.curPath.push(step) 212 defer s.curPath.pop() 213 for _, r := range s.reporters { 214 r.PushStep(step) 215 defer r.PopStep() 216 } 217 s.recChecker.Check(s.curPath) 218 219 // Obtain the current type and values. 220 t := step.Type() 221 vx, vy := step.Values() 222 223 // Rule 1: Check whether an option applies on this node in the value tree. 224 if s.tryOptions(t, vx, vy) { 225 return 226 } 227 228 // Rule 2: Check whether the type has a valid Equal method. 229 if s.tryMethod(t, vx, vy) { 230 return 231 } 232 233 // Rule 3: Compare based on the underlying kind. 234 switch t.Kind() { 235 case reflect.Bool: 236 s.report(vx.Bool() == vy.Bool(), 0) 237 case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: 238 s.report(vx.Int() == vy.Int(), 0) 239 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: 240 s.report(vx.Uint() == vy.Uint(), 0) 241 case reflect.Float32, reflect.Float64: 242 s.report(vx.Float() == vy.Float(), 0) 243 case reflect.Complex64, reflect.Complex128: 244 s.report(vx.Complex() == vy.Complex(), 0) 245 case reflect.String: 246 s.report(vx.String() == vy.String(), 0) 247 case reflect.Chan, reflect.UnsafePointer: 248 s.report(vx.Pointer() == vy.Pointer(), 0) 249 case reflect.Func: 250 s.report(vx.IsNil() && vy.IsNil(), 0) 251 case reflect.Struct: 252 s.compareStruct(t, vx, vy) 253 case reflect.Slice, reflect.Array: 254 s.compareSlice(t, vx, vy) 255 case reflect.Map: 256 s.compareMap(t, vx, vy) 257 case reflect.Ptr: 258 s.comparePtr(t, vx, vy) 259 case reflect.Interface: 260 s.compareInterface(t, vx, vy) 261 default: 262 panic(fmt.Sprintf("%v kind not handled", t.Kind())) 263 } 264} 265 266func (s *state) tryOptions(t reflect.Type, vx, vy reflect.Value) bool { 267 // Evaluate all filters and apply the remaining options. 268 if opt := s.opts.filter(s, t, vx, vy); opt != nil { 269 opt.apply(s, vx, vy) 270 return true 271 } 272 return false 273} 274 275func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool { 276 // Check if this type even has an Equal method. 277 m, ok := t.MethodByName("Equal") 278 if !ok || !function.IsType(m.Type, function.EqualAssignable) { 279 return false 280 } 281 282 eq := s.callTTBFunc(m.Func, vx, vy) 283 s.report(eq, reportByMethod) 284 return true 285} 286 287func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value { 288 v = sanitizeValue(v, f.Type().In(0)) 289 if !s.dynChecker.Next() { 290 return f.Call([]reflect.Value{v})[0] 291 } 292 293 // Run the function twice and ensure that we get the same results back. 294 // We run in goroutines so that the race detector (if enabled) can detect 295 // unsafe mutations to the input. 296 c := make(chan reflect.Value) 297 go detectRaces(c, f, v) 298 got := <-c 299 want := f.Call([]reflect.Value{v})[0] 300 if step.vx, step.vy = got, want; !s.statelessCompare(step).Equal() { 301 // To avoid false-positives with non-reflexive equality operations, 302 // we sanity check whether a value is equal to itself. 303 if step.vx, step.vy = want, want; !s.statelessCompare(step).Equal() { 304 return want 305 } 306 panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f))) 307 } 308 return want 309} 310 311func (s *state) callTTBFunc(f, x, y reflect.Value) bool { 312 x = sanitizeValue(x, f.Type().In(0)) 313 y = sanitizeValue(y, f.Type().In(1)) 314 if !s.dynChecker.Next() { 315 return f.Call([]reflect.Value{x, y})[0].Bool() 316 } 317 318 // Swapping the input arguments is sufficient to check that 319 // f is symmetric and deterministic. 320 // We run in goroutines so that the race detector (if enabled) can detect 321 // unsafe mutations to the input. 322 c := make(chan reflect.Value) 323 go detectRaces(c, f, y, x) 324 got := <-c 325 want := f.Call([]reflect.Value{x, y})[0].Bool() 326 if !got.IsValid() || got.Bool() != want { 327 panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", function.NameOf(f))) 328 } 329 return want 330} 331 332func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) { 333 var ret reflect.Value 334 defer func() { 335 recover() // Ignore panics, let the other call to f panic instead 336 c <- ret 337 }() 338 ret = f.Call(vs)[0] 339} 340 341// sanitizeValue converts nil interfaces of type T to those of type R, 342// assuming that T is assignable to R. 343// Otherwise, it returns the input value as is. 344func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value { 345 // TODO(dsnet): Workaround for reflect bug (https://golang.org/issue/22143). 346 if !flags.AtLeastGo110 { 347 if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t { 348 return reflect.New(t).Elem() 349 } 350 } 351 return v 352} 353 354func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) { 355 var vax, vay reflect.Value // Addressable versions of vx and vy 356 357 step := StructField{&structField{}} 358 for i := 0; i < t.NumField(); i++ { 359 step.typ = t.Field(i).Type 360 step.vx = vx.Field(i) 361 step.vy = vy.Field(i) 362 step.name = t.Field(i).Name 363 step.idx = i 364 step.unexported = !isExported(step.name) 365 if step.unexported { 366 if step.name == "_" { 367 continue 368 } 369 // Defer checking of unexported fields until later to give an 370 // Ignore a chance to ignore the field. 371 if !vax.IsValid() || !vay.IsValid() { 372 // For retrieveUnexportedField to work, the parent struct must 373 // be addressable. Create a new copy of the values if 374 // necessary to make them addressable. 375 vax = makeAddressable(vx) 376 vay = makeAddressable(vy) 377 } 378 step.mayForce = s.exporters[t] 379 step.pvx = vax 380 step.pvy = vay 381 step.field = t.Field(i) 382 } 383 s.compareAny(step) 384 } 385} 386 387func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) { 388 isSlice := t.Kind() == reflect.Slice 389 if isSlice && (vx.IsNil() || vy.IsNil()) { 390 s.report(vx.IsNil() && vy.IsNil(), 0) 391 return 392 } 393 394 // TODO: Support cyclic data structures. 395 396 step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}}} 397 withIndexes := func(ix, iy int) SliceIndex { 398 if ix >= 0 { 399 step.vx, step.xkey = vx.Index(ix), ix 400 } else { 401 step.vx, step.xkey = reflect.Value{}, -1 402 } 403 if iy >= 0 { 404 step.vy, step.ykey = vy.Index(iy), iy 405 } else { 406 step.vy, step.ykey = reflect.Value{}, -1 407 } 408 return step 409 } 410 411 // Ignore options are able to ignore missing elements in a slice. 412 // However, detecting these reliably requires an optimal differencing 413 // algorithm, for which diff.Difference is not. 414 // 415 // Instead, we first iterate through both slices to detect which elements 416 // would be ignored if standing alone. The index of non-discarded elements 417 // are stored in a separate slice, which diffing is then performed on. 418 var indexesX, indexesY []int 419 var ignoredX, ignoredY []bool 420 for ix := 0; ix < vx.Len(); ix++ { 421 ignored := s.statelessCompare(withIndexes(ix, -1)).NumDiff == 0 422 if !ignored { 423 indexesX = append(indexesX, ix) 424 } 425 ignoredX = append(ignoredX, ignored) 426 } 427 for iy := 0; iy < vy.Len(); iy++ { 428 ignored := s.statelessCompare(withIndexes(-1, iy)).NumDiff == 0 429 if !ignored { 430 indexesY = append(indexesY, iy) 431 } 432 ignoredY = append(ignoredY, ignored) 433 } 434 435 // Compute an edit-script for slices vx and vy (excluding ignored elements). 436 edits := diff.Difference(len(indexesX), len(indexesY), func(ix, iy int) diff.Result { 437 return s.statelessCompare(withIndexes(indexesX[ix], indexesY[iy])) 438 }) 439 440 // Replay the ignore-scripts and the edit-script. 441 var ix, iy int 442 for ix < vx.Len() || iy < vy.Len() { 443 var e diff.EditType 444 switch { 445 case ix < len(ignoredX) && ignoredX[ix]: 446 e = diff.UniqueX 447 case iy < len(ignoredY) && ignoredY[iy]: 448 e = diff.UniqueY 449 default: 450 e, edits = edits[0], edits[1:] 451 } 452 switch e { 453 case diff.UniqueX: 454 s.compareAny(withIndexes(ix, -1)) 455 ix++ 456 case diff.UniqueY: 457 s.compareAny(withIndexes(-1, iy)) 458 iy++ 459 default: 460 s.compareAny(withIndexes(ix, iy)) 461 ix++ 462 iy++ 463 } 464 } 465} 466 467func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) { 468 if vx.IsNil() || vy.IsNil() { 469 s.report(vx.IsNil() && vy.IsNil(), 0) 470 return 471 } 472 473 // TODO: Support cyclic data structures. 474 475 // We combine and sort the two map keys so that we can perform the 476 // comparisons in a deterministic order. 477 step := MapIndex{&mapIndex{pathStep: pathStep{typ: t.Elem()}}} 478 for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) { 479 step.vx = vx.MapIndex(k) 480 step.vy = vy.MapIndex(k) 481 step.key = k 482 if !step.vx.IsValid() && !step.vy.IsValid() { 483 // It is possible for both vx and vy to be invalid if the 484 // key contained a NaN value in it. 485 // 486 // Even with the ability to retrieve NaN keys in Go 1.12, 487 // there still isn't a sensible way to compare the values since 488 // a NaN key may map to multiple unordered values. 489 // The most reasonable way to compare NaNs would be to compare the 490 // set of values. However, this is impossible to do efficiently 491 // since set equality is provably an O(n^2) operation given only 492 // an Equal function. If we had a Less function or Hash function, 493 // this could be done in O(n*log(n)) or O(n), respectively. 494 // 495 // Rather than adding complex logic to deal with NaNs, make it 496 // the user's responsibility to compare such obscure maps. 497 const help = "consider providing a Comparer to compare the map" 498 panic(fmt.Sprintf("%#v has map key with NaNs\n%s", s.curPath, help)) 499 } 500 s.compareAny(step) 501 } 502} 503 504func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) { 505 if vx.IsNil() || vy.IsNil() { 506 s.report(vx.IsNil() && vy.IsNil(), 0) 507 return 508 } 509 510 // TODO: Support cyclic data structures. 511 512 vx, vy = vx.Elem(), vy.Elem() 513 s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}}) 514} 515 516func (s *state) compareInterface(t reflect.Type, vx, vy reflect.Value) { 517 if vx.IsNil() || vy.IsNil() { 518 s.report(vx.IsNil() && vy.IsNil(), 0) 519 return 520 } 521 vx, vy = vx.Elem(), vy.Elem() 522 if vx.Type() != vy.Type() { 523 s.report(false, 0) 524 return 525 } 526 s.compareAny(TypeAssertion{&typeAssertion{pathStep{vx.Type(), vx, vy}}}) 527} 528 529func (s *state) report(eq bool, rf resultFlags) { 530 if rf&reportByIgnore == 0 { 531 if eq { 532 s.result.NumSame++ 533 rf |= reportEqual 534 } else { 535 s.result.NumDiff++ 536 rf |= reportUnequal 537 } 538 } 539 for _, r := range s.reporters { 540 r.Report(Result{flags: rf}) 541 } 542} 543 544// recChecker tracks the state needed to periodically perform checks that 545// user provided transformers are not stuck in an infinitely recursive cycle. 546type recChecker struct{ next int } 547 548// Check scans the Path for any recursive transformers and panics when any 549// recursive transformers are detected. Note that the presence of a 550// recursive Transformer does not necessarily imply an infinite cycle. 551// As such, this check only activates after some minimal number of path steps. 552func (rc *recChecker) Check(p Path) { 553 const minLen = 1 << 16 554 if rc.next == 0 { 555 rc.next = minLen 556 } 557 if len(p) < rc.next { 558 return 559 } 560 rc.next <<= 1 561 562 // Check whether the same transformer has appeared at least twice. 563 var ss []string 564 m := map[Option]int{} 565 for _, ps := range p { 566 if t, ok := ps.(Transform); ok { 567 t := t.Option() 568 if m[t] == 1 { // Transformer was used exactly once before 569 tf := t.(*transformer).fnc.Type() 570 ss = append(ss, fmt.Sprintf("%v: %v => %v", t, tf.In(0), tf.Out(0))) 571 } 572 m[t]++ 573 } 574 } 575 if len(ss) > 0 { 576 const warning = "recursive set of Transformers detected" 577 const help = "consider using cmpopts.AcyclicTransformer" 578 set := strings.Join(ss, "\n\t") 579 panic(fmt.Sprintf("%s:\n\t%s\n%s", warning, set, help)) 580 } 581} 582 583// dynChecker tracks the state needed to periodically perform checks that 584// user provided functions are symmetric and deterministic. 585// The zero value is safe for immediate use. 586type dynChecker struct{ curr, next int } 587 588// Next increments the state and reports whether a check should be performed. 589// 590// Checks occur every Nth function call, where N is a triangular number: 591// 0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 ... 592// See https://en.wikipedia.org/wiki/Triangular_number 593// 594// This sequence ensures that the cost of checks drops significantly as 595// the number of functions calls grows larger. 596func (dc *dynChecker) Next() bool { 597 ok := dc.curr == dc.next 598 if ok { 599 dc.curr = 0 600 dc.next++ 601 } 602 dc.curr++ 603 return ok 604} 605 606// makeAddressable returns a value that is always addressable. 607// It returns the input verbatim if it is already addressable, 608// otherwise it creates a new value and returns an addressable copy. 609func makeAddressable(v reflect.Value) reflect.Value { 610 if v.CanAddr() { 611 return v 612 } 613 vc := reflect.New(v.Type()).Elem() 614 vc.Set(v) 615 return vc 616} 617