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 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
// 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.
13
//
14
// The primary features of cmp are:
15
//
16
//   - When the default behavior of equality does not suit the test's needs,
17
//     custom equality functions can override the equality operation.
18
//     For example, an equality function may report floats as equal so long as
19
//     they are within some tolerance of each other.
20
//
21
//   - Types with an Equal method (e.g., [time.Time.Equal]) may use that method
22
//     to determine equality. This allows package authors to determine
23
//     the equality operation for the types 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
27
//     both values, much like [reflect.DeepEqual]. Unlike [reflect.DeepEqual],
28
//     unexported fields are not compared by default; they result in panics
29
//     unless suppressed by using an [Ignore] option
30
//     (see [github.com/google/go-cmp/cmp/cmpopts.IgnoreUnexported])
31
//     or explicitly compared using the [Exporter] option.
32
package cmp
33

34
import (
35
	"fmt"
36
	"reflect"
37
	"strings"
38

39
	"github.com/google/go-cmp/cmp/internal/diff"
40
	"github.com/google/go-cmp/cmp/internal/function"
41
	"github.com/google/go-cmp/cmp/internal/value"
42
)
43

44
// TODO(≥go1.18): Use any instead of interface{}.
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
//   - Let S be the set of all [Ignore], [Transformer], and [Comparer] options that
50
//     remain after applying all path filters, value filters, and type filters.
51
//     If at least one [Ignore] exists in S, then the comparison is ignored.
52
//     If the number of [Transformer] and [Comparer] options in S is non-zero,
53
//     then Equal panics because it is ambiguous which option to use.
54
//     If S contains a single [Transformer], then use that to transform
55
//     the current values and recursively call Equal on the output values.
56
//     If S contains a single [Comparer], then use that to compare the current values.
57
//     Otherwise, evaluation proceeds to the next rule.
58
//
59
//   - If the values have an Equal method of the form "(T) Equal(T) bool" or
60
//     "(T) Equal(I) bool" where T is assignable to I, then use the result of
61
//     x.Equal(y) even if x or y is nil. Otherwise, no such method exists and
62
//     evaluation proceeds to the next rule.
63
//
64
//   - Lastly, try to compare x and y based on their basic kinds.
65
//     Simple kinds like booleans, integers, floats, complex numbers, strings,
66
//     and channels are compared using the equivalent of the == operator in Go.
67
//     Functions are only equal if they are both nil, otherwise they are unequal.
68
//
69
// Structs are equal if recursively calling Equal on all fields report equal.
70
// If a struct contains unexported fields, Equal panics unless an [Ignore] option
71
// (e.g., [github.com/google/go-cmp/cmp/cmpopts.IgnoreUnexported]) ignores that field
72
// or the [Exporter] option explicitly permits comparing the unexported field.
73
//
74
// Slices are equal if they are both nil or both non-nil, where recursively
75
// calling Equal on all non-ignored slice or array elements report equal.
76
// Empty non-nil slices and nil slices are not equal; to equate empty slices,
77
// consider using [github.com/google/go-cmp/cmp/cmpopts.EquateEmpty].
78
//
79
// Maps are equal if they are both nil or both non-nil, where recursively
80
// calling Equal on all non-ignored map entries report equal.
81
// Map keys are equal according to the == operator.
82
// To use custom comparisons for map keys, consider using
83
// [github.com/google/go-cmp/cmp/cmpopts.SortMaps].
84
// Empty non-nil maps and nil maps are not equal; to equate empty maps,
85
// consider using [github.com/google/go-cmp/cmp/cmpopts.EquateEmpty].
86
//
87
// Pointers and interfaces are equal if they are both nil or both non-nil,
88
// where they have the same underlying concrete type and recursively
89
// calling Equal on the underlying values reports equal.
90
//
91
// Before recursing into a pointer, slice element, or map, the current path
92
// is checked to detect whether the address has already been visited.
93
// If there is a cycle, then the pointed at values are considered equal
94
// only if both addresses were previously visited in the same path step.
95
func Equal(x, y interface{}, opts ...Option) bool {
96
	s := newState(opts)
97
	s.compareAny(rootStep(x, y))
98
	return s.result.Equal()
99
}
100

101
// Diff returns a human-readable report of the differences between two values:
102
// y - x. It returns an empty string if and only if Equal returns true for the
103
// same input values and options.
104
//
105
// The output is displayed as a literal in pseudo-Go syntax.
106
// At the start of each line, a "-" prefix indicates an element removed from x,
107
// a "+" prefix to indicates an element added from y, and the lack of a prefix
108
// indicates an element common to both x and y. If possible, the output
109
// uses fmt.Stringer.String or error.Error methods to produce more humanly
110
// readable outputs. In such cases, the string is prefixed with either an
111
// 's' or 'e' character, respectively, to indicate that the method was called.
112
//
113
// Do not depend on this output being stable. If you need the ability to
114
// programmatically interpret the difference, consider using a custom Reporter.
115
func Diff(x, y interface{}, opts ...Option) string {
116
	s := newState(opts)
117

118
	// Optimization: If there are no other reporters, we can optimize for the
119
	// common case where the result is equal (and thus no reported difference).
120
	// This avoids the expensive construction of a difference tree.
121
	if len(s.reporters) == 0 {
122
		s.compareAny(rootStep(x, y))
123
		if s.result.Equal() {
124
			return ""
125
		}
126
		s.result = diff.Result{} // Reset results
127
	}
128

129
	r := new(defaultReporter)
130
	s.reporters = append(s.reporters, reporter{r})
131
	s.compareAny(rootStep(x, y))
132
	d := r.String()
133
	if (d == "") != s.result.Equal() {
134
		panic("inconsistent difference and equality results")
135
	}
136
	return d
137
}
138

139
// rootStep constructs the first path step. If x and y have differing types,
140
// then they are stored within an empty interface type.
141
func rootStep(x, y interface{}) PathStep {
142
	vx := reflect.ValueOf(x)
143
	vy := reflect.ValueOf(y)
144

145
	// If the inputs are different types, auto-wrap them in an empty interface
146
	// so that they have the same parent type.
147
	var t reflect.Type
148
	if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
149
		t = anyType
150
		if vx.IsValid() {
151
			vvx := reflect.New(t).Elem()
152
			vvx.Set(vx)
153
			vx = vvx
154
		}
155
		if vy.IsValid() {
156
			vvy := reflect.New(t).Elem()
157
			vvy.Set(vy)
158
			vy = vvy
159
		}
160
	} else {
161
		t = vx.Type()
162
	}
163

164
	return &pathStep{t, vx, vy}
165
}
166

167
type state struct {
168
	// These fields represent the "comparison state".
169
	// Calling statelessCompare must not result in observable changes to these.
170
	result    diff.Result // The current result of comparison
171
	curPath   Path        // The current path in the value tree
172
	curPtrs   pointerPath // The current set of visited pointers
173
	reporters []reporter  // Optional reporters
174

175
	// recChecker checks for infinite cycles applying the same set of
176
	// transformers upon the output of itself.
177
	recChecker recChecker
178

179
	// dynChecker triggers pseudo-random checks for option correctness.
180
	// It is safe for statelessCompare to mutate this value.
181
	dynChecker dynChecker
182

183
	// These fields, once set by processOption, will not change.
184
	exporters []exporter // List of exporters for structs with unexported fields
185
	opts      Options    // List of all fundamental and filter options
186
}
187

188
func newState(opts []Option) *state {
189
	// Always ensure a validator option exists to validate the inputs.
190
	s := &state{opts: Options{validator{}}}
191
	s.curPtrs.Init()
192
	s.processOption(Options(opts))
193
	return s
194
}
195

196
func (s *state) processOption(opt Option) {
197
	switch opt := opt.(type) {
198
	case nil:
199
	case Options:
200
		for _, o := range opt {
201
			s.processOption(o)
202
		}
203
	case coreOption:
204
		type filtered interface {
205
			isFiltered() bool
206
		}
207
		if fopt, ok := opt.(filtered); ok && !fopt.isFiltered() {
208
			panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt))
209
		}
210
		s.opts = append(s.opts, opt)
211
	case exporter:
212
		s.exporters = append(s.exporters, opt)
213
	case reporter:
214
		s.reporters = append(s.reporters, opt)
215
	default:
216
		panic(fmt.Sprintf("unknown option %T", opt))
217
	}
218
}
219

220
// statelessCompare compares two values and returns the result.
221
// This function is stateless in that it does not alter the current result,
222
// or output to any registered reporters.
223
func (s *state) statelessCompare(step PathStep) diff.Result {
224
	// We do not save and restore curPath and curPtrs because all of the
225
	// compareX methods should properly push and pop from them.
226
	// It is an implementation bug if the contents of the paths differ from
227
	// when calling this function to when returning from it.
228

229
	oldResult, oldReporters := s.result, s.reporters
230
	s.result = diff.Result{} // Reset result
231
	s.reporters = nil        // Remove reporters to avoid spurious printouts
232
	s.compareAny(step)
233
	res := s.result
234
	s.result, s.reporters = oldResult, oldReporters
235
	return res
236
}
237

238
func (s *state) compareAny(step PathStep) {
239
	// Update the path stack.
240
	s.curPath.push(step)
241
	defer s.curPath.pop()
242
	for _, r := range s.reporters {
243
		r.PushStep(step)
244
		defer r.PopStep()
245
	}
246
	s.recChecker.Check(s.curPath)
247

248
	// Cycle-detection for slice elements (see NOTE in compareSlice).
249
	t := step.Type()
250
	vx, vy := step.Values()
251
	if si, ok := step.(SliceIndex); ok && si.isSlice && vx.IsValid() && vy.IsValid() {
252
		px, py := vx.Addr(), vy.Addr()
253
		if eq, visited := s.curPtrs.Push(px, py); visited {
254
			s.report(eq, reportByCycle)
255
			return
256
		}
257
		defer s.curPtrs.Pop(px, py)
258
	}
259

260
	// Rule 1: Check whether an option applies on this node in the value tree.
261
	if s.tryOptions(t, vx, vy) {
262
		return
263
	}
264

265
	// Rule 2: Check whether the type has a valid Equal method.
266
	if s.tryMethod(t, vx, vy) {
267
		return
268
	}
269

270
	// Rule 3: Compare based on the underlying kind.
271
	switch t.Kind() {
272
	case reflect.Bool:
273
		s.report(vx.Bool() == vy.Bool(), 0)
274
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
275
		s.report(vx.Int() == vy.Int(), 0)
276
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
277
		s.report(vx.Uint() == vy.Uint(), 0)
278
	case reflect.Float32, reflect.Float64:
279
		s.report(vx.Float() == vy.Float(), 0)
280
	case reflect.Complex64, reflect.Complex128:
281
		s.report(vx.Complex() == vy.Complex(), 0)
282
	case reflect.String:
283
		s.report(vx.String() == vy.String(), 0)
284
	case reflect.Chan, reflect.UnsafePointer:
285
		s.report(vx.Pointer() == vy.Pointer(), 0)
286
	case reflect.Func:
287
		s.report(vx.IsNil() && vy.IsNil(), 0)
288
	case reflect.Struct:
289
		s.compareStruct(t, vx, vy)
290
	case reflect.Slice, reflect.Array:
291
		s.compareSlice(t, vx, vy)
292
	case reflect.Map:
293
		s.compareMap(t, vx, vy)
294
	case reflect.Ptr:
295
		s.comparePtr(t, vx, vy)
296
	case reflect.Interface:
297
		s.compareInterface(t, vx, vy)
298
	default:
299
		panic(fmt.Sprintf("%v kind not handled", t.Kind()))
300
	}
301
}
302

303
func (s *state) tryOptions(t reflect.Type, vx, vy reflect.Value) bool {
304
	// Evaluate all filters and apply the remaining options.
305
	if opt := s.opts.filter(s, t, vx, vy); opt != nil {
306
		opt.apply(s, vx, vy)
307
		return true
308
	}
309
	return false
310
}
311

312
func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool {
313
	// Check if this type even has an Equal method.
314
	m, ok := t.MethodByName("Equal")
315
	if !ok || !function.IsType(m.Type, function.EqualAssignable) {
316
		return false
317
	}
318

319
	eq := s.callTTBFunc(m.Func, vx, vy)
320
	s.report(eq, reportByMethod)
321
	return true
322
}
323

324
func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value {
325
	if !s.dynChecker.Next() {
326
		return f.Call([]reflect.Value{v})[0]
327
	}
328

329
	// Run the function twice and ensure that we get the same results back.
330
	// We run in goroutines so that the race detector (if enabled) can detect
331
	// unsafe mutations to the input.
332
	c := make(chan reflect.Value)
333
	go detectRaces(c, f, v)
334
	got := <-c
335
	want := f.Call([]reflect.Value{v})[0]
336
	if step.vx, step.vy = got, want; !s.statelessCompare(step).Equal() {
337
		// To avoid false-positives with non-reflexive equality operations,
338
		// we sanity check whether a value is equal to itself.
339
		if step.vx, step.vy = want, want; !s.statelessCompare(step).Equal() {
340
			return want
341
		}
342
		panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f)))
343
	}
344
	return want
345
}
346

347
func (s *state) callTTBFunc(f, x, y reflect.Value) bool {
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)
358
	got := <-c
359
	want := f.Call([]reflect.Value{x, y})[0].Bool()
360
	if !got.IsValid() || got.Bool() != want {
361
		panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", function.NameOf(f)))
362
	}
363
	return want
364
}
365

366
func 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
func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
376
	var addr bool
377
	var vax, vay reflect.Value // Addressable versions of vx and vy
378

379
	var mayForce, mayForceInit bool
380
	step := StructField{&structField{}}
381
	for i := 0; i < t.NumField(); i++ {
382
		step.typ = t.Field(i).Type
383
		step.vx = vx.Field(i)
384
		step.vy = vy.Field(i)
385
		step.name = t.Field(i).Name
386
		step.idx = i
387
		step.unexported = !isExported(step.name)
388
		if step.unexported {
389
			if step.name == "_" {
390
				continue
391
			}
392
			// Defer checking of unexported fields until later to give an
393
			// Ignore a chance to ignore the field.
394
			if !vax.IsValid() || !vay.IsValid() {
395
				// For retrieveUnexportedField to work, the parent struct must
396
				// be addressable. Create a new copy of the values if
397
				// necessary to make them addressable.
398
				addr = vx.CanAddr() || vy.CanAddr()
399
				vax = makeAddressable(vx)
400
				vay = makeAddressable(vy)
401
			}
402
			if !mayForceInit {
403
				for _, xf := range s.exporters {
404
					mayForce = mayForce || xf(t)
405
				}
406
				mayForceInit = true
407
			}
408
			step.mayForce = mayForce
409
			step.paddr = addr
410
			step.pvx = vax
411
			step.pvy = vay
412
			step.field = t.Field(i)
413
		}
414
		s.compareAny(step)
415
	}
416
}
417

418
func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) {
419
	isSlice := t.Kind() == reflect.Slice
420
	if isSlice && (vx.IsNil() || vy.IsNil()) {
421
		s.report(vx.IsNil() && vy.IsNil(), 0)
422
		return
423
	}
424

425
	// NOTE: It is incorrect to call curPtrs.Push on the slice header pointer
426
	// since slices represents a list of pointers, rather than a single pointer.
427
	// The pointer checking logic must be handled on a per-element basis
428
	// in compareAny.
429
	//
430
	// A slice header (see reflect.SliceHeader) in Go is a tuple of a starting
431
	// pointer P, a length N, and a capacity C. Supposing each slice element has
432
	// a memory size of M, then the slice is equivalent to the list of pointers:
433
	//	[P+i*M for i in range(N)]
434
	//
435
	// For example, v[:0] and v[:1] are slices with the same starting pointer,
436
	// but they are clearly different values. Using the slice pointer alone
437
	// violates the assumption that equal pointers implies equal values.
438

439
	step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}, isSlice: isSlice}}
440
	withIndexes := func(ix, iy int) SliceIndex {
441
		if ix >= 0 {
442
			step.vx, step.xkey = vx.Index(ix), ix
443
		} else {
444
			step.vx, step.xkey = reflect.Value{}, -1
445
		}
446
		if iy >= 0 {
447
			step.vy, step.ykey = vy.Index(iy), iy
448
		} else {
449
			step.vy, step.ykey = reflect.Value{}, -1
450
		}
451
		return step
452
	}
453

454
	// Ignore options are able to ignore missing elements in a slice.
455
	// However, detecting these reliably requires an optimal differencing
456
	// algorithm, for which diff.Difference is not.
457
	//
458
	// Instead, we first iterate through both slices to detect which elements
459
	// would be ignored if standing alone. The index of non-discarded elements
460
	// are stored in a separate slice, which diffing is then performed on.
461
	var indexesX, indexesY []int
462
	var ignoredX, ignoredY []bool
463
	for ix := 0; ix < vx.Len(); ix++ {
464
		ignored := s.statelessCompare(withIndexes(ix, -1)).NumDiff == 0
465
		if !ignored {
466
			indexesX = append(indexesX, ix)
467
		}
468
		ignoredX = append(ignoredX, ignored)
469
	}
470
	for iy := 0; iy < vy.Len(); iy++ {
471
		ignored := s.statelessCompare(withIndexes(-1, iy)).NumDiff == 0
472
		if !ignored {
473
			indexesY = append(indexesY, iy)
474
		}
475
		ignoredY = append(ignoredY, ignored)
476
	}
477

478
	// Compute an edit-script for slices vx and vy (excluding ignored elements).
479
	edits := diff.Difference(len(indexesX), len(indexesY), func(ix, iy int) diff.Result {
480
		return s.statelessCompare(withIndexes(indexesX[ix], indexesY[iy]))
481
	})
482

483
	// Replay the ignore-scripts and the edit-script.
484
	var ix, iy int
485
	for ix < vx.Len() || iy < vy.Len() {
486
		var e diff.EditType
487
		switch {
488
		case ix < len(ignoredX) && ignoredX[ix]:
489
			e = diff.UniqueX
490
		case iy < len(ignoredY) && ignoredY[iy]:
491
			e = diff.UniqueY
492
		default:
493
			e, edits = edits[0], edits[1:]
494
		}
495
		switch e {
496
		case diff.UniqueX:
497
			s.compareAny(withIndexes(ix, -1))
498
			ix++
499
		case diff.UniqueY:
500
			s.compareAny(withIndexes(-1, iy))
501
			iy++
502
		default:
503
			s.compareAny(withIndexes(ix, iy))
504
			ix++
505
			iy++
506
		}
507
	}
508
}
509

510
func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
511
	if vx.IsNil() || vy.IsNil() {
512
		s.report(vx.IsNil() && vy.IsNil(), 0)
513
		return
514
	}
515

516
	// Cycle-detection for maps.
517
	if eq, visited := s.curPtrs.Push(vx, vy); visited {
518
		s.report(eq, reportByCycle)
519
		return
520
	}
521
	defer s.curPtrs.Pop(vx, vy)
522

523
	// We combine and sort the two map keys so that we can perform the
524
	// comparisons in a deterministic order.
525
	step := MapIndex{&mapIndex{pathStep: pathStep{typ: t.Elem()}}}
526
	for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) {
527
		step.vx = vx.MapIndex(k)
528
		step.vy = vy.MapIndex(k)
529
		step.key = k
530
		if !step.vx.IsValid() && !step.vy.IsValid() {
531
			// It is possible for both vx and vy to be invalid if the
532
			// key contained a NaN value in it.
533
			//
534
			// Even with the ability to retrieve NaN keys in Go 1.12,
535
			// there still isn't a sensible way to compare the values since
536
			// a NaN key may map to multiple unordered values.
537
			// The most reasonable way to compare NaNs would be to compare the
538
			// set of values. However, this is impossible to do efficiently
539
			// since set equality is provably an O(n^2) operation given only
540
			// an Equal function. If we had a Less function or Hash function,
541
			// this could be done in O(n*log(n)) or O(n), respectively.
542
			//
543
			// Rather than adding complex logic to deal with NaNs, make it
544
			// the user's responsibility to compare such obscure maps.
545
			const help = "consider providing a Comparer to compare the map"
546
			panic(fmt.Sprintf("%#v has map key with NaNs\n%s", s.curPath, help))
547
		}
548
		s.compareAny(step)
549
	}
550
}
551

552
func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) {
553
	if vx.IsNil() || vy.IsNil() {
554
		s.report(vx.IsNil() && vy.IsNil(), 0)
555
		return
556
	}
557

558
	// Cycle-detection for pointers.
559
	if eq, visited := s.curPtrs.Push(vx, vy); visited {
560
		s.report(eq, reportByCycle)
561
		return
562
	}
563
	defer s.curPtrs.Pop(vx, vy)
564

565
	vx, vy = vx.Elem(), vy.Elem()
566
	s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}})
567
}
568

569
func (s *state) compareInterface(t reflect.Type, vx, vy reflect.Value) {
570
	if vx.IsNil() || vy.IsNil() {
571
		s.report(vx.IsNil() && vy.IsNil(), 0)
572
		return
573
	}
574
	vx, vy = vx.Elem(), vy.Elem()
575
	if vx.Type() != vy.Type() {
576
		s.report(false, 0)
577
		return
578
	}
579
	s.compareAny(TypeAssertion{&typeAssertion{pathStep{vx.Type(), vx, vy}}})
580
}
581

582
func (s *state) report(eq bool, rf resultFlags) {
583
	if rf&reportByIgnore == 0 {
584
		if eq {
585
			s.result.NumSame++
586
			rf |= reportEqual
587
		} else {
588
			s.result.NumDiff++
589
			rf |= reportUnequal
590
		}
591
	}
592
	for _, r := range s.reporters {
593
		r.Report(Result{flags: rf})
594
	}
595
}
596

597
// recChecker tracks the state needed to periodically perform checks that
598
// user provided transformers are not stuck in an infinitely recursive cycle.
599
type recChecker struct{ next int }
600

601
// Check scans the Path for any recursive transformers and panics when any
602
// recursive transformers are detected. Note that the presence of a
603
// recursive Transformer does not necessarily imply an infinite cycle.
604
// As such, this check only activates after some minimal number of path steps.
605
func (rc *recChecker) Check(p Path) {
606
	const minLen = 1 << 16
607
	if rc.next == 0 {
608
		rc.next = minLen
609
	}
610
	if len(p) < rc.next {
611
		return
612
	}
613
	rc.next <<= 1
614

615
	// Check whether the same transformer has appeared at least twice.
616
	var ss []string
617
	m := map[Option]int{}
618
	for _, ps := range p {
619
		if t, ok := ps.(Transform); ok {
620
			t := t.Option()
621
			if m[t] == 1 { // Transformer was used exactly once before
622
				tf := t.(*transformer).fnc.Type()
623
				ss = append(ss, fmt.Sprintf("%v: %v => %v", t, tf.In(0), tf.Out(0)))
624
			}
625
			m[t]++
626
		}
627
	}
628
	if len(ss) > 0 {
629
		const warning = "recursive set of Transformers detected"
630
		const help = "consider using cmpopts.AcyclicTransformer"
631
		set := strings.Join(ss, "\n\t")
632
		panic(fmt.Sprintf("%s:\n\t%s\n%s", warning, set, help))
633
	}
634
}
635

636
// dynChecker tracks the state needed to periodically perform checks that
637
// user provided functions are symmetric and deterministic.
638
// The zero value is safe for immediate use.
639
type dynChecker struct{ curr, next int }
640

641
// Next increments the state and reports whether a check should be performed.
642
//
643
// Checks occur every Nth function call, where N is a triangular number:
644
//
645
//	0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 ...
646
//
647
// See https://en.wikipedia.org/wiki/Triangular_number
648
//
649
// This sequence ensures that the cost of checks drops significantly as
650
// the number of functions calls grows larger.
651
func (dc *dynChecker) Next() bool {
652
	ok := dc.curr == dc.next
653
	if ok {
654
		dc.curr = 0
655
		dc.next++
656
	}
657
	dc.curr++
658
	return ok
659
}
660

661
// makeAddressable returns a value that is always addressable.
662
// It returns the input verbatim if it is already addressable,
663
// otherwise it creates a new value and returns an addressable copy.
664
func makeAddressable(v reflect.Value) reflect.Value {
665
	if v.CanAddr() {
666
		return v
667
	}
668
	vc := reflect.New(v.Type()).Elem()
669
	vc.Set(v)
670
	return vc
671
}
672

673