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.
5 // Package cmp determines equality of values.
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.
10 // The primary features of cmp are:
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.
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
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.
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"
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:
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.
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.
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.
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.
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.
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.
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.
83 func Equal(x, y interface{}, opts ...Option) bool {
84 vx := reflect.ValueOf(x)
85 vy := reflect.ValueOf(y)
87 // If the inputs are different types, auto-wrap them in an empty interface
88 // so that they have the same parent type.
90 if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
91 t = reflect.TypeOf((*interface{})(nil)).Elem()
93 vvx := reflect.New(t).Elem()
98 vvy := reflect.New(t).Elem()
107 s.compareAny(&pathStep{t, vx, vy})
108 return s.result.Equal()
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.
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.
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.
125 func Diff(x, y interface{}, opts ...Option) string {
126 r := new(defaultReporter)
127 eq := Equal(x, y, Options(opts), Reporter(r))
130 panic("inconsistent difference and equality results")
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
142 // recChecker checks for infinite cycles applying the same set of
143 // transformers upon the output of itself.
144 recChecker recChecker
146 // dynChecker triggers pseudo-random checks for option correctness.
147 // It is safe for statelessCompare to mutate this value.
148 dynChecker dynChecker
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
155 func 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))
162 func (s *state) processOption(opt Option) {
163 switch opt := opt.(type) {
166 for _, o := range opt {
170 type filtered interface {
173 if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() {
174 panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt))
176 s.opts = append(s.opts, opt)
178 if s.exporters == nil {
179 s.exporters = make(map[reflect.Type]bool)
182 s.exporters[t] = true
185 s.reporters = append(s.reporters, opt)
187 panic(fmt.Sprintf("unknown option %T", opt))
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.
194 func (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.
200 oldResult, oldReporters := s.result, s.reporters
201 s.result = diff.Result{} // Reset result
202 s.reporters = nil // Remove reporters to avoid spurious printouts
205 s.result, s.reporters = oldResult, oldReporters
209 func (s *state) compareAny(step PathStep) {
210 // Update the path stack.
212 defer s.curPath.pop()
213 for _, r := range s.reporters {
217 s.recChecker.Check(s.curPath)
219 // Obtain the current type and values.
221 vx, vy := step.Values()
223 // Rule 1: Check whether an option applies on this node in the value tree.
224 if s.tryOptions(t, vx, vy) {
228 // Rule 2: Check whether the type has a valid Equal method.
229 if s.tryMethod(t, vx, vy) {
233 // Rule 3: Compare based on the underlying kind.
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)
246 s.report(vx.String() == vy.String(), 0)
247 case reflect.Chan, reflect.UnsafePointer:
248 s.report(vx.Pointer() == vy.Pointer(), 0)
250 s.report(vx.IsNil() && vy.IsNil(), 0)
252 s.compareStruct(t, vx, vy)
253 case reflect.Slice, reflect.Array:
254 s.compareSlice(t, vx, vy)
256 s.compareMap(t, vx, vy)
258 s.comparePtr(t, vx, vy)
259 case reflect.Interface:
260 s.compareInterface(t, vx, vy)
262 panic(fmt.Sprintf("%v kind not handled", t.Kind()))
266 func (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 {
275 func (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) {
282 eq := s.callTTBFunc(m.Func, vx, vy)
283 s.report(eq, reportByMethod)
287 func (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]
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)
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() {
306 panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f)))
311 func (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()
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)
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)))
332 func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) {
333 var ret reflect.Value
335 recover() // Ignore panics, let the other call to f panic instead
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.
344 func 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()
354 func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
355 var vax, vay reflect.Value // Addressable versions of vx and vy
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
364 step.unexported = !isExported(step.name)
366 if step.name == "_" {
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)
378 step.mayForce = s.exporters[t]
381 step.field = t.Field(i)
387 func (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)
394 // TODO: Support cyclic data structures.
396 step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}}}
397 withIndexes := func(ix, iy int) SliceIndex {
399 step.vx, step.xkey = vx.Index(ix), ix
401 step.vx, step.xkey = reflect.Value{}, -1
404 step.vy, step.ykey = vy.Index(iy), iy
406 step.vy, step.ykey = reflect.Value{}, -1
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.
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
423 indexesX = append(indexesX, ix)
425 ignoredX = append(ignoredX, ignored)
427 for iy := 0; iy < vy.Len(); iy++ {
428 ignored := s.statelessCompare(withIndexes(-1, iy)).NumDiff == 0
430 indexesY = append(indexesY, iy)
432 ignoredY = append(ignoredY, ignored)
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]))
440 // Replay the ignore-scripts and the edit-script.
442 for ix < vx.Len() || iy < vy.Len() {
445 case ix < len(ignoredX) && ignoredX[ix]:
447 case iy < len(ignoredY) && ignoredY[iy]:
450 e, edits = edits[0], edits[1:]
454 s.compareAny(withIndexes(ix, -1))
457 s.compareAny(withIndexes(-1, iy))
460 s.compareAny(withIndexes(ix, iy))
467 func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
468 if vx.IsNil() || vy.IsNil() {
469 s.report(vx.IsNil() && vy.IsNil(), 0)
473 // TODO: Support cyclic data structures.
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)
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.
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.
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))
504 func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) {
505 if vx.IsNil() || vy.IsNil() {
506 s.report(vx.IsNil() && vy.IsNil(), 0)
510 // TODO: Support cyclic data structures.
512 vx, vy = vx.Elem(), vy.Elem()
513 s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}})
516 func (s *state) compareInterface(t reflect.Type, vx, vy reflect.Value) {
517 if vx.IsNil() || vy.IsNil() {
518 s.report(vx.IsNil() && vy.IsNil(), 0)
521 vx, vy = vx.Elem(), vy.Elem()
522 if vx.Type() != vy.Type() {
526 s.compareAny(TypeAssertion{&typeAssertion{pathStep{vx.Type(), vx, vy}}})
529 func (s *state) report(eq bool, rf resultFlags) {
530 if rf&reportByIgnore == 0 {
539 for _, r := range s.reporters {
540 r.Report(Result{flags: rf})
544 // recChecker tracks the state needed to periodically perform checks that
545 // user provided transformers are not stuck in an infinitely recursive cycle.
546 type recChecker struct{ next int }
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.
552 func (rc *recChecker) Check(p Path) {
553 const minLen = 1 << 16
557 if len(p) < rc.next {
562 // Check whether the same transformer has appeared at least twice.
564 m := map[Option]int{}
565 for _, ps := range p {
566 if t, ok := ps.(Transform); ok {
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)))
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))
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.
586 type dynChecker struct{ curr, next int }
588 // Next increments the state and reports whether a check should be performed.
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
594 // This sequence ensures that the cost of checks drops significantly as
595 // the number of functions calls grows larger.
596 func (dc *dynChecker) Next() bool {
597 ok := dc.curr == dc.next
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.
609 func makeAddressable(v reflect.Value) reflect.Value {
613 vc := reflect.New(v.Type()).Elem()