blob: 86d0903b8b542e1ab579943426b3355916702738 [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
David K. Bainbridgec415efe2021-08-19 13:05:21 +00003// license that can be found in the LICENSE file.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -07004
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.
David K. Bainbridgec415efe2021-08-19 13:05:21 +00009// It is intended to only be used in tests, as performance is not a goal and
10// it may panic if it cannot compare the values. Its propensity towards
11// panicking means that its unsuitable for production environments where a
12// spurious panic may be fatal.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070013//
14// The primary features of cmp are:
15//
16// • When the default behavior of equality does not suit the needs of the test,
17// custom equality functions can override the equality operation.
18// For example, an equality function may report floats as equal so long as they
19// are within some tolerance of each other.
20//
21// • Types that have an Equal method may use that method to determine equality.
22// This allows package authors to determine the equality operation for the types
23// that they define.
24//
25// • If no custom equality functions are used and no Equal method is defined,
26// equality is determined by recursively comparing the primitive kinds on both
27// values, much like reflect.DeepEqual. Unlike reflect.DeepEqual, unexported
28// fields are not compared by default; they result in panics unless suppressed
Pragya Arya324337e2020-02-20 14:35:08 +053029// by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly
30// compared using the Exporter option.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070031package cmp
32
33import (
34 "fmt"
35 "reflect"
Pragya Arya324337e2020-02-20 14:35:08 +053036 "strings"
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070037
38 "github.com/google/go-cmp/cmp/internal/diff"
Pragya Arya324337e2020-02-20 14:35:08 +053039 "github.com/google/go-cmp/cmp/internal/flags"
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070040 "github.com/google/go-cmp/cmp/internal/function"
41 "github.com/google/go-cmp/cmp/internal/value"
42)
43
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070044// Equal reports whether x and y are equal by recursively applying the
45// following rules in the given order to x and y and all of their sub-values:
46//
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070047// • Let S be the set of all Ignore, Transformer, and Comparer options that
48// remain after applying all path filters, value filters, and type filters.
49// If at least one Ignore exists in S, then the comparison is ignored.
50// If the number of Transformer and Comparer options in S is greater than one,
51// then Equal panics because it is ambiguous which option to use.
52// If S contains a single Transformer, then use that to transform the current
53// values and recursively call Equal on the output values.
54// If S contains a single Comparer, then use that to compare the current values.
55// Otherwise, evaluation proceeds to the next rule.
56//
57// • If the values have an Equal method of the form "(T) Equal(T) bool" or
58// "(T) Equal(I) bool" where T is assignable to I, then use the result of
Pragya Arya324337e2020-02-20 14:35:08 +053059// x.Equal(y) even if x or y is nil. Otherwise, no such method exists and
60// evaluation proceeds to the next rule.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070061//
62// • Lastly, try to compare x and y based on their basic kinds.
63// Simple kinds like booleans, integers, floats, complex numbers, strings, and
64// channels are compared using the equivalent of the == operator in Go.
65// Functions are only equal if they are both nil, otherwise they are unequal.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070066//
Pragya Arya324337e2020-02-20 14:35:08 +053067// Structs are equal if recursively calling Equal on all fields report equal.
68// If a struct contains unexported fields, Equal panics unless an Ignore option
69// (e.g., cmpopts.IgnoreUnexported) ignores that field or the Exporter option
70// explicitly permits comparing the unexported field.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070071//
Pragya Arya324337e2020-02-20 14:35:08 +053072// Slices are equal if they are both nil or both non-nil, where recursively
73// calling Equal on all non-ignored slice or array elements report equal.
74// Empty non-nil slices and nil slices are not equal; to equate empty slices,
75// consider using cmpopts.EquateEmpty.
76//
77// Maps are equal if they are both nil or both non-nil, where recursively
78// calling Equal on all non-ignored map entries report equal.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070079// Map keys are equal according to the == operator.
80// To use custom comparisons for map keys, consider using cmpopts.SortMaps.
Pragya Arya324337e2020-02-20 14:35:08 +053081// Empty non-nil maps and nil maps are not equal; to equate empty maps,
82// consider using cmpopts.EquateEmpty.
83//
84// Pointers and interfaces are equal if they are both nil or both non-nil,
85// where they have the same underlying concrete type and recursively
86// calling Equal on the underlying values reports equal.
87//
88// Before recursing into a pointer, slice element, or map, the current path
89// is checked to detect whether the address has already been visited.
90// If there is a cycle, then the pointed at values are considered equal
91// only if both addresses were previously visited in the same path step.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -070092func Equal(x, y interface{}, opts ...Option) bool {
David K. Bainbridgec415efe2021-08-19 13:05:21 +000093 s := newState(opts)
94 s.compareAny(rootStep(x, y))
95 return s.result.Equal()
96}
97
98// Diff returns a human-readable report of the differences between two values:
99// y - x. It returns an empty string if and only if Equal returns true for the
100// same input values and options.
101//
102// The output is displayed as a literal in pseudo-Go syntax.
103// At the start of each line, a "-" prefix indicates an element removed from x,
104// a "+" prefix to indicates an element added from y, and the lack of a prefix
105// indicates an element common to both x and y. If possible, the output
106// uses fmt.Stringer.String or error.Error methods to produce more humanly
107// readable outputs. In such cases, the string is prefixed with either an
108// 's' or 'e' character, respectively, to indicate that the method was called.
109//
110// Do not depend on this output being stable. If you need the ability to
111// programmatically interpret the difference, consider using a custom Reporter.
112func Diff(x, y interface{}, opts ...Option) string {
113 s := newState(opts)
114
115 // Optimization: If there are no other reporters, we can optimize for the
116 // common case where the result is equal (and thus no reported difference).
117 // This avoids the expensive construction of a difference tree.
118 if len(s.reporters) == 0 {
119 s.compareAny(rootStep(x, y))
120 if s.result.Equal() {
121 return ""
122 }
123 s.result = diff.Result{} // Reset results
124 }
125
126 r := new(defaultReporter)
127 s.reporters = append(s.reporters, reporter{r})
128 s.compareAny(rootStep(x, y))
129 d := r.String()
130 if (d == "") != s.result.Equal() {
131 panic("inconsistent difference and equality results")
132 }
133 return d
134}
135
136// rootStep constructs the first path step. If x and y have differing types,
137// then they are stored within an empty interface type.
138func rootStep(x, y interface{}) PathStep {
Pragya Arya324337e2020-02-20 14:35:08 +0530139 vx := reflect.ValueOf(x)
140 vy := reflect.ValueOf(y)
141
142 // If the inputs are different types, auto-wrap them in an empty interface
143 // so that they have the same parent type.
144 var t reflect.Type
145 if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
146 t = reflect.TypeOf((*interface{})(nil)).Elem()
147 if vx.IsValid() {
148 vvx := reflect.New(t).Elem()
149 vvx.Set(vx)
150 vx = vvx
151 }
152 if vy.IsValid() {
153 vvy := reflect.New(t).Elem()
154 vvy.Set(vy)
155 vy = vvy
156 }
157 } else {
158 t = vx.Type()
159 }
160
David K. Bainbridgec415efe2021-08-19 13:05:21 +0000161 return &pathStep{t, vx, vy}
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700162}
163
164type state struct {
165 // These fields represent the "comparison state".
166 // Calling statelessCompare must not result in observable changes to these.
Pragya Arya324337e2020-02-20 14:35:08 +0530167 result diff.Result // The current result of comparison
168 curPath Path // The current path in the value tree
169 curPtrs pointerPath // The current set of visited pointers
170 reporters []reporter // Optional reporters
171
172 // recChecker checks for infinite cycles applying the same set of
173 // transformers upon the output of itself.
174 recChecker recChecker
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700175
176 // dynChecker triggers pseudo-random checks for option correctness.
177 // It is safe for statelessCompare to mutate this value.
178 dynChecker dynChecker
179
180 // These fields, once set by processOption, will not change.
Pragya Arya324337e2020-02-20 14:35:08 +0530181 exporters []exporter // List of exporters for structs with unexported fields
182 opts Options // List of all fundamental and filter options
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700183}
184
185func newState(opts []Option) *state {
Pragya Arya324337e2020-02-20 14:35:08 +0530186 // Always ensure a validator option exists to validate the inputs.
187 s := &state{opts: Options{validator{}}}
188 s.curPtrs.Init()
189 s.processOption(Options(opts))
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700190 return s
191}
192
193func (s *state) processOption(opt Option) {
194 switch opt := opt.(type) {
195 case nil:
196 case Options:
197 for _, o := range opt {
198 s.processOption(o)
199 }
200 case coreOption:
201 type filtered interface {
202 isFiltered() bool
203 }
204 if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() {
205 panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt))
206 }
207 s.opts = append(s.opts, opt)
Pragya Arya324337e2020-02-20 14:35:08 +0530208 case exporter:
209 s.exporters = append(s.exporters, opt)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700210 case reporter:
Pragya Arya324337e2020-02-20 14:35:08 +0530211 s.reporters = append(s.reporters, opt)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700212 default:
213 panic(fmt.Sprintf("unknown option %T", opt))
214 }
215}
216
217// statelessCompare compares two values and returns the result.
218// This function is stateless in that it does not alter the current result,
219// or output to any registered reporters.
Pragya Arya324337e2020-02-20 14:35:08 +0530220func (s *state) statelessCompare(step PathStep) diff.Result {
221 // We do not save and restore curPath and curPtrs because all of the
222 // compareX methods should properly push and pop from them.
223 // It is an implementation bug if the contents of the paths differ from
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700224 // when calling this function to when returning from it.
225
Pragya Arya324337e2020-02-20 14:35:08 +0530226 oldResult, oldReporters := s.result, s.reporters
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700227 s.result = diff.Result{} // Reset result
Pragya Arya324337e2020-02-20 14:35:08 +0530228 s.reporters = nil // Remove reporters to avoid spurious printouts
229 s.compareAny(step)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700230 res := s.result
Pragya Arya324337e2020-02-20 14:35:08 +0530231 s.result, s.reporters = oldResult, oldReporters
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700232 return res
233}
234
Pragya Arya324337e2020-02-20 14:35:08 +0530235func (s *state) compareAny(step PathStep) {
236 // Update the path stack.
237 s.curPath.push(step)
238 defer s.curPath.pop()
239 for _, r := range s.reporters {
240 r.PushStep(step)
241 defer r.PopStep()
242 }
243 s.recChecker.Check(s.curPath)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700244
Pragya Arya324337e2020-02-20 14:35:08 +0530245 // Cycle-detection for slice elements (see NOTE in compareSlice).
246 t := step.Type()
247 vx, vy := step.Values()
248 if si, ok := step.(SliceIndex); ok && si.isSlice && vx.IsValid() && vy.IsValid() {
249 px, py := vx.Addr(), vy.Addr()
250 if eq, visited := s.curPtrs.Push(px, py); visited {
251 s.report(eq, reportByCycle)
252 return
253 }
254 defer s.curPtrs.Pop(px, py)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700255 }
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700256
257 // Rule 1: Check whether an option applies on this node in the value tree.
Pragya Arya324337e2020-02-20 14:35:08 +0530258 if s.tryOptions(t, vx, vy) {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700259 return
260 }
261
262 // Rule 2: Check whether the type has a valid Equal method.
Pragya Arya324337e2020-02-20 14:35:08 +0530263 if s.tryMethod(t, vx, vy) {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700264 return
265 }
266
Pragya Arya324337e2020-02-20 14:35:08 +0530267 // Rule 3: Compare based on the underlying kind.
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700268 switch t.Kind() {
269 case reflect.Bool:
Pragya Arya324337e2020-02-20 14:35:08 +0530270 s.report(vx.Bool() == vy.Bool(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700271 case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
Pragya Arya324337e2020-02-20 14:35:08 +0530272 s.report(vx.Int() == vy.Int(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700273 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
Pragya Arya324337e2020-02-20 14:35:08 +0530274 s.report(vx.Uint() == vy.Uint(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700275 case reflect.Float32, reflect.Float64:
Pragya Arya324337e2020-02-20 14:35:08 +0530276 s.report(vx.Float() == vy.Float(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700277 case reflect.Complex64, reflect.Complex128:
Pragya Arya324337e2020-02-20 14:35:08 +0530278 s.report(vx.Complex() == vy.Complex(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700279 case reflect.String:
Pragya Arya324337e2020-02-20 14:35:08 +0530280 s.report(vx.String() == vy.String(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700281 case reflect.Chan, reflect.UnsafePointer:
Pragya Arya324337e2020-02-20 14:35:08 +0530282 s.report(vx.Pointer() == vy.Pointer(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700283 case reflect.Func:
Pragya Arya324337e2020-02-20 14:35:08 +0530284 s.report(vx.IsNil() && vy.IsNil(), 0)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700285 case reflect.Struct:
Pragya Arya324337e2020-02-20 14:35:08 +0530286 s.compareStruct(t, vx, vy)
287 case reflect.Slice, reflect.Array:
288 s.compareSlice(t, vx, vy)
289 case reflect.Map:
290 s.compareMap(t, vx, vy)
291 case reflect.Ptr:
292 s.comparePtr(t, vx, vy)
293 case reflect.Interface:
294 s.compareInterface(t, vx, vy)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700295 default:
296 panic(fmt.Sprintf("%v kind not handled", t.Kind()))
297 }
298}
299
Pragya Arya324337e2020-02-20 14:35:08 +0530300func (s *state) tryOptions(t reflect.Type, vx, vy reflect.Value) bool {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700301 // Evaluate all filters and apply the remaining options.
Pragya Arya324337e2020-02-20 14:35:08 +0530302 if opt := s.opts.filter(s, t, vx, vy); opt != nil {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700303 opt.apply(s, vx, vy)
304 return true
305 }
306 return false
307}
308
Pragya Arya324337e2020-02-20 14:35:08 +0530309func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700310 // Check if this type even has an Equal method.
311 m, ok := t.MethodByName("Equal")
312 if !ok || !function.IsType(m.Type, function.EqualAssignable) {
313 return false
314 }
315
316 eq := s.callTTBFunc(m.Func, vx, vy)
Pragya Arya324337e2020-02-20 14:35:08 +0530317 s.report(eq, reportByMethod)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700318 return true
319}
320
Pragya Arya324337e2020-02-20 14:35:08 +0530321func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700322 v = sanitizeValue(v, f.Type().In(0))
323 if !s.dynChecker.Next() {
324 return f.Call([]reflect.Value{v})[0]
325 }
326
327 // Run the function twice and ensure that we get the same results back.
328 // We run in goroutines so that the race detector (if enabled) can detect
329 // unsafe mutations to the input.
330 c := make(chan reflect.Value)
331 go detectRaces(c, f, v)
Pragya Arya324337e2020-02-20 14:35:08 +0530332 got := <-c
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700333 want := f.Call([]reflect.Value{v})[0]
Pragya Arya324337e2020-02-20 14:35:08 +0530334 if step.vx, step.vy = got, want; !s.statelessCompare(step).Equal() {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700335 // To avoid false-positives with non-reflexive equality operations,
336 // we sanity check whether a value is equal to itself.
Pragya Arya324337e2020-02-20 14:35:08 +0530337 if step.vx, step.vy = want, want; !s.statelessCompare(step).Equal() {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700338 return want
339 }
Pragya Arya324337e2020-02-20 14:35:08 +0530340 panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f)))
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700341 }
342 return want
343}
344
345func (s *state) callTTBFunc(f, x, y reflect.Value) bool {
346 x = sanitizeValue(x, f.Type().In(0))
347 y = sanitizeValue(y, f.Type().In(1))
348 if !s.dynChecker.Next() {
349 return f.Call([]reflect.Value{x, y})[0].Bool()
350 }
351
352 // Swapping the input arguments is sufficient to check that
353 // f is symmetric and deterministic.
354 // We run in goroutines so that the race detector (if enabled) can detect
355 // unsafe mutations to the input.
356 c := make(chan reflect.Value)
357 go detectRaces(c, f, y, x)
Pragya Arya324337e2020-02-20 14:35:08 +0530358 got := <-c
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700359 want := f.Call([]reflect.Value{x, y})[0].Bool()
Pragya Arya324337e2020-02-20 14:35:08 +0530360 if !got.IsValid() || got.Bool() != want {
361 panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", function.NameOf(f)))
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700362 }
363 return want
364}
365
366func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) {
367 var ret reflect.Value
368 defer func() {
369 recover() // Ignore panics, let the other call to f panic instead
370 c <- ret
371 }()
372 ret = f.Call(vs)[0]
373}
374
375// sanitizeValue converts nil interfaces of type T to those of type R,
376// assuming that T is assignable to R.
377// Otherwise, it returns the input value as is.
378func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value {
David K. Bainbridgec415efe2021-08-19 13:05:21 +0000379 // TODO(≥go1.10): Workaround for reflect bug (https://golang.org/issue/22143).
Pragya Arya324337e2020-02-20 14:35:08 +0530380 if !flags.AtLeastGo110 {
381 if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t {
382 return reflect.New(t).Elem()
383 }
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700384 }
385 return v
386}
387
Pragya Arya324337e2020-02-20 14:35:08 +0530388func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
David K. Bainbridgec415efe2021-08-19 13:05:21 +0000389 var addr bool
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700390 var vax, vay reflect.Value // Addressable versions of vx and vy
391
Pragya Arya324337e2020-02-20 14:35:08 +0530392 var mayForce, mayForceInit bool
393 step := StructField{&structField{}}
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700394 for i := 0; i < t.NumField(); i++ {
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700395 step.typ = t.Field(i).Type
Pragya Arya324337e2020-02-20 14:35:08 +0530396 step.vx = vx.Field(i)
397 step.vy = vy.Field(i)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700398 step.name = t.Field(i).Name
399 step.idx = i
400 step.unexported = !isExported(step.name)
401 if step.unexported {
Pragya Arya324337e2020-02-20 14:35:08 +0530402 if step.name == "_" {
403 continue
404 }
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700405 // Defer checking of unexported fields until later to give an
406 // Ignore a chance to ignore the field.
407 if !vax.IsValid() || !vay.IsValid() {
Pragya Arya324337e2020-02-20 14:35:08 +0530408 // For retrieveUnexportedField to work, the parent struct must
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700409 // be addressable. Create a new copy of the values if
410 // necessary to make them addressable.
David K. Bainbridgec415efe2021-08-19 13:05:21 +0000411 addr = vx.CanAddr() || vy.CanAddr()
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700412 vax = makeAddressable(vx)
413 vay = makeAddressable(vy)
414 }
Pragya Arya324337e2020-02-20 14:35:08 +0530415 if !mayForceInit {
416 for _, xf := range s.exporters {
417 mayForce = mayForce || xf(t)
418 }
419 mayForceInit = true
420 }
421 step.mayForce = mayForce
David K. Bainbridgec415efe2021-08-19 13:05:21 +0000422 step.paddr = addr
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700423 step.pvx = vax
424 step.pvy = vay
425 step.field = t.Field(i)
426 }
Pragya Arya324337e2020-02-20 14:35:08 +0530427 s.compareAny(step)
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700428 }
429}
430
Pragya Arya324337e2020-02-20 14:35:08 +0530431func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) {
432 isSlice := t.Kind() == reflect.Slice
433 if isSlice && (vx.IsNil() || vy.IsNil()) {
434 s.report(vx.IsNil() && vy.IsNil(), 0)
435 return
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700436 }
Pragya Arya324337e2020-02-20 14:35:08 +0530437
438 // NOTE: It is incorrect to call curPtrs.Push on the slice header pointer
439 // since slices represents a list of pointers, rather than a single pointer.
440 // The pointer checking logic must be handled on a per-element basis
441 // in compareAny.
442 //
443 // A slice header (see reflect.SliceHeader) in Go is a tuple of a starting
444 // pointer P, a length N, and a capacity C. Supposing each slice element has
445 // a memory size of M, then the slice is equivalent to the list of pointers:
446 // [P+i*M for i in range(N)]
447 //
448 // For example, v[:0] and v[:1] are slices with the same starting pointer,
449 // but they are clearly different values. Using the slice pointer alone
450 // violates the assumption that equal pointers implies equal values.
451
452 step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}, isSlice: isSlice}}
453 withIndexes := func(ix, iy int) SliceIndex {
454 if ix >= 0 {
455 step.vx, step.xkey = vx.Index(ix), ix
456 } else {
457 step.vx, step.xkey = reflect.Value{}, -1
458 }
459 if iy >= 0 {
460 step.vy, step.ykey = vy.Index(iy), iy
461 } else {
462 step.vy, step.ykey = reflect.Value{}, -1
463 }
464 return step
465 }
466
467 // Ignore options are able to ignore missing elements in a slice.
468 // However, detecting these reliably requires an optimal differencing
469 // algorithm, for which diff.Difference is not.
470 //
471 // Instead, we first iterate through both slices to detect which elements
472 // would be ignored if standing alone. The index of non-discarded elements
473 // are stored in a separate slice, which diffing is then performed on.
474 var indexesX, indexesY []int
475 var ignoredX, ignoredY []bool
476 for ix := 0; ix < vx.Len(); ix++ {
477 ignored := s.statelessCompare(withIndexes(ix, -1)).NumDiff == 0
478 if !ignored {
479 indexesX = append(indexesX, ix)
480 }
481 ignoredX = append(ignoredX, ignored)
482 }
483 for iy := 0; iy < vy.Len(); iy++ {
484 ignored := s.statelessCompare(withIndexes(-1, iy)).NumDiff == 0
485 if !ignored {
486 indexesY = append(indexesY, iy)
487 }
488 ignoredY = append(ignoredY, ignored)
489 }
490
491 // Compute an edit-script for slices vx and vy (excluding ignored elements).
492 edits := diff.Difference(len(indexesX), len(indexesY), func(ix, iy int) diff.Result {
493 return s.statelessCompare(withIndexes(indexesX[ix], indexesY[iy]))
494 })
495
496 // Replay the ignore-scripts and the edit-script.
497 var ix, iy int
498 for ix < vx.Len() || iy < vy.Len() {
499 var e diff.EditType
500 switch {
501 case ix < len(ignoredX) && ignoredX[ix]:
502 e = diff.UniqueX
503 case iy < len(ignoredY) && ignoredY[iy]:
504 e = diff.UniqueY
505 default:
506 e, edits = edits[0], edits[1:]
507 }
508 switch e {
509 case diff.UniqueX:
510 s.compareAny(withIndexes(ix, -1))
511 ix++
512 case diff.UniqueY:
513 s.compareAny(withIndexes(-1, iy))
514 iy++
515 default:
516 s.compareAny(withIndexes(ix, iy))
517 ix++
518 iy++
519 }
520 }
521}
522
523func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
524 if vx.IsNil() || vy.IsNil() {
525 s.report(vx.IsNil() && vy.IsNil(), 0)
526 return
527 }
528
529 // Cycle-detection for maps.
530 if eq, visited := s.curPtrs.Push(vx, vy); visited {
531 s.report(eq, reportByCycle)
532 return
533 }
534 defer s.curPtrs.Pop(vx, vy)
535
536 // We combine and sort the two map keys so that we can perform the
537 // comparisons in a deterministic order.
538 step := MapIndex{&mapIndex{pathStep: pathStep{typ: t.Elem()}}}
539 for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) {
540 step.vx = vx.MapIndex(k)
541 step.vy = vy.MapIndex(k)
542 step.key = k
543 if !step.vx.IsValid() && !step.vy.IsValid() {
544 // It is possible for both vx and vy to be invalid if the
545 // key contained a NaN value in it.
546 //
547 // Even with the ability to retrieve NaN keys in Go 1.12,
548 // there still isn't a sensible way to compare the values since
549 // a NaN key may map to multiple unordered values.
550 // The most reasonable way to compare NaNs would be to compare the
551 // set of values. However, this is impossible to do efficiently
552 // since set equality is provably an O(n^2) operation given only
553 // an Equal function. If we had a Less function or Hash function,
554 // this could be done in O(n*log(n)) or O(n), respectively.
555 //
556 // Rather than adding complex logic to deal with NaNs, make it
557 // the user's responsibility to compare such obscure maps.
558 const help = "consider providing a Comparer to compare the map"
559 panic(fmt.Sprintf("%#v has map key with NaNs\n%s", s.curPath, help))
560 }
561 s.compareAny(step)
562 }
563}
564
565func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) {
566 if vx.IsNil() || vy.IsNil() {
567 s.report(vx.IsNil() && vy.IsNil(), 0)
568 return
569 }
570
571 // Cycle-detection for pointers.
572 if eq, visited := s.curPtrs.Push(vx, vy); visited {
573 s.report(eq, reportByCycle)
574 return
575 }
576 defer s.curPtrs.Pop(vx, vy)
577
578 vx, vy = vx.Elem(), vy.Elem()
579 s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}})
580}
581
582func (s *state) compareInterface(t reflect.Type, vx, vy reflect.Value) {
583 if vx.IsNil() || vy.IsNil() {
584 s.report(vx.IsNil() && vy.IsNil(), 0)
585 return
586 }
587 vx, vy = vx.Elem(), vy.Elem()
588 if vx.Type() != vy.Type() {
589 s.report(false, 0)
590 return
591 }
592 s.compareAny(TypeAssertion{&typeAssertion{pathStep{vx.Type(), vx, vy}}})
593}
594
595func (s *state) report(eq bool, rf resultFlags) {
596 if rf&reportByIgnore == 0 {
597 if eq {
598 s.result.NumSame++
599 rf |= reportEqual
600 } else {
601 s.result.NumDiff++
602 rf |= reportUnequal
603 }
604 }
605 for _, r := range s.reporters {
606 r.Report(Result{flags: rf})
607 }
608}
609
610// recChecker tracks the state needed to periodically perform checks that
611// user provided transformers are not stuck in an infinitely recursive cycle.
612type recChecker struct{ next int }
613
614// Check scans the Path for any recursive transformers and panics when any
615// recursive transformers are detected. Note that the presence of a
616// recursive Transformer does not necessarily imply an infinite cycle.
617// As such, this check only activates after some minimal number of path steps.
618func (rc *recChecker) Check(p Path) {
619 const minLen = 1 << 16
620 if rc.next == 0 {
621 rc.next = minLen
622 }
623 if len(p) < rc.next {
624 return
625 }
626 rc.next <<= 1
627
628 // Check whether the same transformer has appeared at least twice.
629 var ss []string
630 m := map[Option]int{}
631 for _, ps := range p {
632 if t, ok := ps.(Transform); ok {
633 t := t.Option()
634 if m[t] == 1 { // Transformer was used exactly once before
635 tf := t.(*transformer).fnc.Type()
636 ss = append(ss, fmt.Sprintf("%v: %v => %v", t, tf.In(0), tf.Out(0)))
637 }
638 m[t]++
639 }
640 }
641 if len(ss) > 0 {
642 const warning = "recursive set of Transformers detected"
643 const help = "consider using cmpopts.AcyclicTransformer"
644 set := strings.Join(ss, "\n\t")
645 panic(fmt.Sprintf("%s:\n\t%s\n%s", warning, set, help))
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -0700646 }
647}
648
649// dynChecker tracks the state needed to periodically perform checks that
650// user provided functions are symmetric and deterministic.
651// The zero value is safe for immediate use.
652type dynChecker struct{ curr, next int }
653
654// Next increments the state and reports whether a check should be performed.
655//
656// Checks occur every Nth function call, where N is a triangular number:
657// 0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 ...
658// See https://en.wikipedia.org/wiki/Triangular_number
659//
660// This sequence ensures that the cost of checks drops significantly as
661// the number of functions calls grows larger.
662func (dc *dynChecker) Next() bool {
663 ok := dc.curr == dc.next
664 if ok {
665 dc.curr = 0
666 dc.next++
667 }
668 dc.curr++
669 return ok
670}
671
672// makeAddressable returns a value that is always addressable.
673// It returns the input verbatim if it is already addressable,
674// otherwise it creates a new value and returns an addressable copy.
675func makeAddressable(v reflect.Value) reflect.Value {
676 if v.CanAddr() {
677 return v
678 }
679 vc := reflect.New(v.Type()).Elem()
680 vc.Set(v)
681 return vc
682}