compare.go

Documentation: github.com/google/go-cmp/cmp

     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
View as plain text