blob: 7e215f2202965996deba8605f541aafffcf34237 [file] [log] [blame]
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -07001// 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
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
44var 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.
84func 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.
97func 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
108type 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
124func newState(opts []Option) *state {
125 s := new(state)
126 for _, opt := range opts {
127 s.processOption(opt)
128 }
129 return s
130}
131
132func (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.
167func (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
182func (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
279func (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
296func (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
313func (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
325func (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
349func (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
370func 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.
382func 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
391func (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
443func (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
475func (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.
509func (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.
523type 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.
533func (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.
546func 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}