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
6

7
import (
8
	"fmt"
9
	"reflect"
10
	"regexp"
11
	"strings"
12

13
	"github.com/google/go-cmp/cmp/internal/function"
14
)
15

16
// Option configures for specific behavior of [Equal] and [Diff]. In particular,
17
// the fundamental Option functions ([Ignore], [Transformer], and [Comparer]),
18
// configure how equality is determined.
19
//
20
// The fundamental options may be composed with filters ([FilterPath] and
21
// [FilterValues]) to control the scope over which they are applied.
22
//
23
// The [github.com/google/go-cmp/cmp/cmpopts] package provides helper functions
24
// for creating options that may be used with [Equal] and [Diff].
25
type Option interface {
26
	// filter applies all filters and returns the option that remains.
27
	// Each option may only read s.curPath and call s.callTTBFunc.
28
	//
29
	// An Options is returned only if multiple comparers or transformers
30
	// can apply simultaneously and will only contain values of those types
31
	// or sub-Options containing values of those types.
32
	filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption
33
}
34

35
// applicableOption represents the following types:
36
//
37
//	Fundamental: ignore | validator | *comparer | *transformer
38
//	Grouping:    Options
39
type applicableOption interface {
40
	Option
41

42
	// apply executes the option, which may mutate s or panic.
43
	apply(s *state, vx, vy reflect.Value)
44
}
45

46
// coreOption represents the following types:
47
//
48
//	Fundamental: ignore | validator | *comparer | *transformer
49
//	Filters:     *pathFilter | *valuesFilter
50
type coreOption interface {
51
	Option
52
	isCore()
53
}
54

55
type core struct{}
56

57
func (core) isCore() {}
58

59
// Options is a list of [Option] values that also satisfies the [Option] interface.
60
// Helper comparison packages may return an Options value when packing multiple
61
// [Option] values into a single [Option]. When this package processes an Options,
62
// it will be implicitly expanded into a flat list.
63
//
64
// Applying a filter on an Options is equivalent to applying that same filter
65
// on all individual options held within.
66
type Options []Option
67

68
func (opts Options) filter(s *state, t reflect.Type, vx, vy reflect.Value) (out applicableOption) {
69
	for _, opt := range opts {
70
		switch opt := opt.filter(s, t, vx, vy); opt.(type) {
71
		case ignore:
72
			return ignore{} // Only ignore can short-circuit evaluation
73
		case validator:
74
			out = validator{} // Takes precedence over comparer or transformer
75
		case *comparer, *transformer, Options:
76
			switch out.(type) {
77
			case nil:
78
				out = opt
79
			case validator:
80
				// Keep validator
81
			case *comparer, *transformer, Options:
82
				out = Options{out, opt} // Conflicting comparers or transformers
83
			}
84
		}
85
	}
86
	return out
87
}
88

89
func (opts Options) apply(s *state, _, _ reflect.Value) {
90
	const warning = "ambiguous set of applicable options"
91
	const help = "consider using filters to ensure at most one Comparer or Transformer may apply"
92
	var ss []string
93
	for _, opt := range flattenOptions(nil, opts) {
94
		ss = append(ss, fmt.Sprint(opt))
95
	}
96
	set := strings.Join(ss, "\n\t")
97
	panic(fmt.Sprintf("%s at %#v:\n\t%s\n%s", warning, s.curPath, set, help))
98
}
99

100
func (opts Options) String() string {
101
	var ss []string
102
	for _, opt := range opts {
103
		ss = append(ss, fmt.Sprint(opt))
104
	}
105
	return fmt.Sprintf("Options{%s}", strings.Join(ss, ", "))
106
}
107

108
// FilterPath returns a new [Option] where opt is only evaluated if filter f
109
// returns true for the current [Path] in the value tree.
110
//
111
// This filter is called even if a slice element or map entry is missing and
112
// provides an opportunity to ignore such cases. The filter function must be
113
// symmetric such that the filter result is identical regardless of whether the
114
// missing value is from x or y.
115
//
116
// The option passed in may be an [Ignore], [Transformer], [Comparer], [Options], or
117
// a previously filtered [Option].
118
func FilterPath(f func(Path) bool, opt Option) Option {
119
	if f == nil {
120
		panic("invalid path filter function")
121
	}
122
	if opt := normalizeOption(opt); opt != nil {
123
		return &pathFilter{fnc: f, opt: opt}
124
	}
125
	return nil
126
}
127

128
type pathFilter struct {
129
	core
130
	fnc func(Path) bool
131
	opt Option
132
}
133

134
func (f pathFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption {
135
	if f.fnc(s.curPath) {
136
		return f.opt.filter(s, t, vx, vy)
137
	}
138
	return nil
139
}
140

141
func (f pathFilter) String() string {
142
	return fmt.Sprintf("FilterPath(%s, %v)", function.NameOf(reflect.ValueOf(f.fnc)), f.opt)
143
}
144

145
// FilterValues returns a new [Option] where opt is only evaluated if filter f,
146
// which is a function of the form "func(T, T) bool", returns true for the
147
// current pair of values being compared. If either value is invalid or
148
// the type of the values is not assignable to T, then this filter implicitly
149
// returns false.
150
//
151
// The filter function must be
152
// symmetric (i.e., agnostic to the order of the inputs) and
153
// deterministic (i.e., produces the same result when given the same inputs).
154
// If T is an interface, it is possible that f is called with two values with
155
// different concrete types that both implement T.
156
//
157
// The option passed in may be an [Ignore], [Transformer], [Comparer], [Options], or
158
// a previously filtered [Option].
159
func FilterValues(f interface{}, opt Option) Option {
160
	v := reflect.ValueOf(f)
161
	if !function.IsType(v.Type(), function.ValueFilter) || v.IsNil() {
162
		panic(fmt.Sprintf("invalid values filter function: %T", f))
163
	}
164
	if opt := normalizeOption(opt); opt != nil {
165
		vf := &valuesFilter{fnc: v, opt: opt}
166
		if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 {
167
			vf.typ = ti
168
		}
169
		return vf
170
	}
171
	return nil
172
}
173

174
type valuesFilter struct {
175
	core
176
	typ reflect.Type  // T
177
	fnc reflect.Value // func(T, T) bool
178
	opt Option
179
}
180

181
func (f valuesFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption {
182
	if !vx.IsValid() || !vx.CanInterface() || !vy.IsValid() || !vy.CanInterface() {
183
		return nil
184
	}
185
	if (f.typ == nil || t.AssignableTo(f.typ)) && s.callTTBFunc(f.fnc, vx, vy) {
186
		return f.opt.filter(s, t, vx, vy)
187
	}
188
	return nil
189
}
190

191
func (f valuesFilter) String() string {
192
	return fmt.Sprintf("FilterValues(%s, %v)", function.NameOf(f.fnc), f.opt)
193
}
194

195
// Ignore is an [Option] that causes all comparisons to be ignored.
196
// This value is intended to be combined with [FilterPath] or [FilterValues].
197
// It is an error to pass an unfiltered Ignore option to [Equal].
198
func Ignore() Option { return ignore{} }
199

200
type ignore struct{ core }
201

202
func (ignore) isFiltered() bool                                                     { return false }
203
func (ignore) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { return ignore{} }
204
func (ignore) apply(s *state, _, _ reflect.Value)                                   { s.report(true, reportByIgnore) }
205
func (ignore) String() string                                                       { return "Ignore()" }
206

207
// validator is a sentinel Option type to indicate that some options could not
208
// be evaluated due to unexported fields, missing slice elements, or
209
// missing map entries. Both values are validator only for unexported fields.
210
type validator struct{ core }
211

212
func (validator) filter(_ *state, _ reflect.Type, vx, vy reflect.Value) applicableOption {
213
	if !vx.IsValid() || !vy.IsValid() {
214
		return validator{}
215
	}
216
	if !vx.CanInterface() || !vy.CanInterface() {
217
		return validator{}
218
	}
219
	return nil
220
}
221
func (validator) apply(s *state, vx, vy reflect.Value) {
222
	// Implies missing slice element or map entry.
223
	if !vx.IsValid() || !vy.IsValid() {
224
		s.report(vx.IsValid() == vy.IsValid(), 0)
225
		return
226
	}
227

228
	// Unable to Interface implies unexported field without visibility access.
229
	if !vx.CanInterface() || !vy.CanInterface() {
230
		help := "consider using a custom Comparer; if you control the implementation of type, you can also consider using an Exporter, AllowUnexported, or cmpopts.IgnoreUnexported"
231
		var name string
232
		if t := s.curPath.Index(-2).Type(); t.Name() != "" {
233
			// Named type with unexported fields.
234
			name = fmt.Sprintf("%q.%v", t.PkgPath(), t.Name()) // e.g., "path/to/package".MyType
235
			isProtoMessage := func(t reflect.Type) bool {
236
				m, ok := reflect.PointerTo(t).MethodByName("ProtoReflect")
237
				return ok && m.Type.NumIn() == 1 && m.Type.NumOut() == 1 &&
238
					m.Type.Out(0).PkgPath() == "google.golang.org/protobuf/reflect/protoreflect" &&
239
					m.Type.Out(0).Name() == "Message"
240
			}
241
			if isProtoMessage(t) {
242
				help = `consider using "google.golang.org/protobuf/testing/protocmp".Transform to compare proto.Message types`
243
			} else if _, ok := reflect.New(t).Interface().(error); ok {
244
				help = "consider using cmpopts.EquateErrors to compare error values"
245
			} else if t.Comparable() {
246
				help = "consider using cmpopts.EquateComparable to compare comparable Go types"
247
			}
248
		} else {
249
			// Unnamed type with unexported fields. Derive PkgPath from field.
250
			var pkgPath string
251
			for i := 0; i < t.NumField() && pkgPath == ""; i++ {
252
				pkgPath = t.Field(i).PkgPath
253
			}
254
			name = fmt.Sprintf("%q.(%v)", pkgPath, t.String()) // e.g., "path/to/package".(struct { a int })
255
		}
256
		panic(fmt.Sprintf("cannot handle unexported field at %#v:\n\t%v\n%s", s.curPath, name, help))
257
	}
258

259
	panic("not reachable")
260
}
261

262
// identRx represents a valid identifier according to the Go specification.
263
const identRx = `[_\p{L}][_\p{L}\p{N}]*`
264

265
var identsRx = regexp.MustCompile(`^` + identRx + `(\.` + identRx + `)*$`)
266

267
// Transformer returns an [Option] that applies a transformation function that
268
// converts values of a certain type into that of another.
269
//
270
// The transformer f must be a function "func(T) R" that converts values of
271
// type T to those of type R and is implicitly filtered to input values
272
// assignable to T. The transformer must not mutate T in any way.
273
//
274
// To help prevent some cases of infinite recursive cycles applying the
275
// same transform to the output of itself (e.g., in the case where the
276
// input and output types are the same), an implicit filter is added such that
277
// a transformer is applicable only if that exact transformer is not already
278
// in the tail of the [Path] since the last non-[Transform] step.
279
// For situations where the implicit filter is still insufficient,
280
// consider using [github.com/google/go-cmp/cmp/cmpopts.AcyclicTransformer],
281
// which adds a filter to prevent the transformer from
282
// being recursively applied upon itself.
283
//
284
// The name is a user provided label that is used as the [Transform.Name] in the
285
// transformation [PathStep] (and eventually shown in the [Diff] output).
286
// The name must be a valid identifier or qualified identifier in Go syntax.
287
// If empty, an arbitrary name is used.
288
func Transformer(name string, f interface{}) Option {
289
	v := reflect.ValueOf(f)
290
	if !function.IsType(v.Type(), function.Transformer) || v.IsNil() {
291
		panic(fmt.Sprintf("invalid transformer function: %T", f))
292
	}
293
	if name == "" {
294
		name = function.NameOf(v)
295
		if !identsRx.MatchString(name) {
296
			name = "λ" // Lambda-symbol as placeholder name
297
		}
298
	} else if !identsRx.MatchString(name) {
299
		panic(fmt.Sprintf("invalid name: %q", name))
300
	}
301
	tr := &transformer{name: name, fnc: reflect.ValueOf(f)}
302
	if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 {
303
		tr.typ = ti
304
	}
305
	return tr
306
}
307

308
type transformer struct {
309
	core
310
	name string
311
	typ  reflect.Type  // T
312
	fnc  reflect.Value // func(T) R
313
}
314

315
func (tr *transformer) isFiltered() bool { return tr.typ != nil }
316

317
func (tr *transformer) filter(s *state, t reflect.Type, _, _ reflect.Value) applicableOption {
318
	for i := len(s.curPath) - 1; i >= 0; i-- {
319
		if t, ok := s.curPath[i].(Transform); !ok {
320
			break // Hit most recent non-Transform step
321
		} else if tr == t.trans {
322
			return nil // Cannot directly use same Transform
323
		}
324
	}
325
	if tr.typ == nil || t.AssignableTo(tr.typ) {
326
		return tr
327
	}
328
	return nil
329
}
330

331
func (tr *transformer) apply(s *state, vx, vy reflect.Value) {
332
	step := Transform{&transform{pathStep{typ: tr.fnc.Type().Out(0)}, tr}}
333
	vvx := s.callTRFunc(tr.fnc, vx, step)
334
	vvy := s.callTRFunc(tr.fnc, vy, step)
335
	step.vx, step.vy = vvx, vvy
336
	s.compareAny(step)
337
}
338

339
func (tr transformer) String() string {
340
	return fmt.Sprintf("Transformer(%s, %s)", tr.name, function.NameOf(tr.fnc))
341
}
342

343
// Comparer returns an [Option] that determines whether two values are equal
344
// to each other.
345
//
346
// The comparer f must be a function "func(T, T) bool" and is implicitly
347
// filtered to input values assignable to T. If T is an interface, it is
348
// possible that f is called with two values of different concrete types that
349
// both implement T.
350
//
351
// The equality function must be:
352
//   - Symmetric: equal(x, y) == equal(y, x)
353
//   - Deterministic: equal(x, y) == equal(x, y)
354
//   - Pure: equal(x, y) does not modify x or y
355
func Comparer(f interface{}) Option {
356
	v := reflect.ValueOf(f)
357
	if !function.IsType(v.Type(), function.Equal) || v.IsNil() {
358
		panic(fmt.Sprintf("invalid comparer function: %T", f))
359
	}
360
	cm := &comparer{fnc: v}
361
	if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 {
362
		cm.typ = ti
363
	}
364
	return cm
365
}
366

367
type comparer struct {
368
	core
369
	typ reflect.Type  // T
370
	fnc reflect.Value // func(T, T) bool
371
}
372

373
func (cm *comparer) isFiltered() bool { return cm.typ != nil }
374

375
func (cm *comparer) filter(_ *state, t reflect.Type, _, _ reflect.Value) applicableOption {
376
	if cm.typ == nil || t.AssignableTo(cm.typ) {
377
		return cm
378
	}
379
	return nil
380
}
381

382
func (cm *comparer) apply(s *state, vx, vy reflect.Value) {
383
	eq := s.callTTBFunc(cm.fnc, vx, vy)
384
	s.report(eq, reportByFunc)
385
}
386

387
func (cm comparer) String() string {
388
	return fmt.Sprintf("Comparer(%s)", function.NameOf(cm.fnc))
389
}
390

391
// Exporter returns an [Option] that specifies whether [Equal] is allowed to
392
// introspect into the unexported fields of certain struct types.
393
//
394
// Users of this option must understand that comparing on unexported fields
395
// from external packages is not safe since changes in the internal
396
// implementation of some external package may cause the result of [Equal]
397
// to unexpectedly change. However, it may be valid to use this option on types
398
// defined in an internal package where the semantic meaning of an unexported
399
// field is in the control of the user.
400
//
401
// In many cases, a custom [Comparer] should be used instead that defines
402
// equality as a function of the public API of a type rather than the underlying
403
// unexported implementation.
404
//
405
// For example, the [reflect.Type] documentation defines equality to be determined
406
// by the == operator on the interface (essentially performing a shallow pointer
407
// comparison) and most attempts to compare *[regexp.Regexp] types are interested
408
// in only checking that the regular expression strings are equal.
409
// Both of these are accomplished using [Comparer] options:
410
//
411
//	Comparer(func(x, y reflect.Type) bool { return x == y })
412
//	Comparer(func(x, y *regexp.Regexp) bool { return x.String() == y.String() })
413
//
414
// In other cases, the [github.com/google/go-cmp/cmp/cmpopts.IgnoreUnexported]
415
// option can be used to ignore all unexported fields on specified struct types.
416
func Exporter(f func(reflect.Type) bool) Option {
417
	return exporter(f)
418
}
419

420
type exporter func(reflect.Type) bool
421

422
func (exporter) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption {
423
	panic("not implemented")
424
}
425

426
// AllowUnexported returns an [Option] that allows [Equal] to forcibly introspect
427
// unexported fields of the specified struct types.
428
//
429
// See [Exporter] for the proper use of this option.
430
func AllowUnexported(types ...interface{}) Option {
431
	m := make(map[reflect.Type]bool)
432
	for _, typ := range types {
433
		t := reflect.TypeOf(typ)
434
		if t.Kind() != reflect.Struct {
435
			panic(fmt.Sprintf("invalid struct type: %T", typ))
436
		}
437
		m[t] = true
438
	}
439
	return exporter(func(t reflect.Type) bool { return m[t] })
440
}
441

442
// Result represents the comparison result for a single node and
443
// is provided by cmp when calling Report (see [Reporter]).
444
type Result struct {
445
	_     [0]func() // Make Result incomparable
446
	flags resultFlags
447
}
448

449
// Equal reports whether the node was determined to be equal or not.
450
// As a special case, ignored nodes are considered equal.
451
func (r Result) Equal() bool {
452
	return r.flags&(reportEqual|reportByIgnore) != 0
453
}
454

455
// ByIgnore reports whether the node is equal because it was ignored.
456
// This never reports true if [Result.Equal] reports false.
457
func (r Result) ByIgnore() bool {
458
	return r.flags&reportByIgnore != 0
459
}
460

461
// ByMethod reports whether the Equal method determined equality.
462
func (r Result) ByMethod() bool {
463
	return r.flags&reportByMethod != 0
464
}
465

466
// ByFunc reports whether a [Comparer] function determined equality.
467
func (r Result) ByFunc() bool {
468
	return r.flags&reportByFunc != 0
469
}
470

471
// ByCycle reports whether a reference cycle was detected.
472
func (r Result) ByCycle() bool {
473
	return r.flags&reportByCycle != 0
474
}
475

476
type resultFlags uint
477

478
const (
479
	_ resultFlags = (1 << iota) / 2
480

481
	reportEqual
482
	reportUnequal
483
	reportByIgnore
484
	reportByMethod
485
	reportByFunc
486
	reportByCycle
487
)
488

489
// Reporter is an [Option] that can be passed to [Equal]. When [Equal] traverses
490
// the value trees, it calls PushStep as it descends into each node in the
491
// tree and PopStep as it ascend out of the node. The leaves of the tree are
492
// either compared (determined to be equal or not equal) or ignored and reported
493
// as such by calling the Report method.
494
func Reporter(r interface {
495
	// PushStep is called when a tree-traversal operation is performed.
496
	// The PathStep itself is only valid until the step is popped.
497
	// The PathStep.Values are valid for the duration of the entire traversal
498
	// and must not be mutated.
499
	//
500
	// Equal always calls PushStep at the start to provide an operation-less
501
	// PathStep used to report the root values.
502
	//
503
	// Within a slice, the exact set of inserted, removed, or modified elements
504
	// is unspecified and may change in future implementations.
505
	// The entries of a map are iterated through in an unspecified order.
506
	PushStep(PathStep)
507

508
	// Report is called exactly once on leaf nodes to report whether the
509
	// comparison identified the node as equal, unequal, or ignored.
510
	// A leaf node is one that is immediately preceded by and followed by
511
	// a pair of PushStep and PopStep calls.
512
	Report(Result)
513

514
	// PopStep ascends back up the value tree.
515
	// There is always a matching pop call for every push call.
516
	PopStep()
517
}) Option {
518
	return reporter{r}
519
}
520

521
type reporter struct{ reporterIface }
522
type reporterIface interface {
523
	PushStep(PathStep)
524
	Report(Result)
525
	PopStep()
526
}
527

528
func (reporter) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption {
529
	panic("not implemented")
530
}
531

532
// normalizeOption normalizes the input options such that all Options groups
533
// are flattened and groups with a single element are reduced to that element.
534
// Only coreOptions and Options containing coreOptions are allowed.
535
func normalizeOption(src Option) Option {
536
	switch opts := flattenOptions(nil, Options{src}); len(opts) {
537
	case 0:
538
		return nil
539
	case 1:
540
		return opts[0]
541
	default:
542
		return opts
543
	}
544
}
545

546
// flattenOptions copies all options in src to dst as a flat list.
547
// Only coreOptions and Options containing coreOptions are allowed.
548
func flattenOptions(dst, src Options) Options {
549
	for _, opt := range src {
550
		switch opt := opt.(type) {
551
		case nil:
552
			continue
553
		case Options:
554
			dst = flattenOptions(dst, opt)
555
		case coreOption:
556
			dst = append(dst, opt)
557
		default:
558
			panic(fmt.Sprintf("invalid option type: %T", opt))
559
		}
560
	}
561
	return dst
562
}
563

564