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
5package cmp
6
7import (
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].
25type 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
39type 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
50type coreOption interface {
51 Option
52 isCore()
53}
54
55type core struct{}
56
57func (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.
66type Options []Option
67
68func (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
89func (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
100func (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].
118func 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
128type pathFilter struct {
129 core
130 fnc func(Path) bool
131 opt Option
132}
133
134func (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
141func (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].
159func 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
174type valuesFilter struct {
175 core
176 typ reflect.Type // T
177 fnc reflect.Value // func(T, T) bool
178 opt Option
179}
180
181func (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
191func (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].
198func Ignore() Option { return ignore{} }
199
200type ignore struct{ core }
201
202func (ignore) isFiltered() bool { return false }
203func (ignore) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { return ignore{} }
204func (ignore) apply(s *state, _, _ reflect.Value) { s.report(true, reportByIgnore) }
205func (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.
210type validator struct{ core }
211
212func (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}
221func (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.
263const identRx = `[_\p{L}][_\p{L}\p{N}]*`
264
265var 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.
288func 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
308type transformer struct {
309 core
310 name string
311 typ reflect.Type // T
312 fnc reflect.Value // func(T) R
313}
314
315func (tr *transformer) isFiltered() bool { return tr.typ != nil }
316
317func (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
331func (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
339func (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
355func 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
367type comparer struct {
368 core
369 typ reflect.Type // T
370 fnc reflect.Value // func(T, T) bool
371}
372
373func (cm *comparer) isFiltered() bool { return cm.typ != nil }
374
375func (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
382func (cm *comparer) apply(s *state, vx, vy reflect.Value) {
383 eq := s.callTTBFunc(cm.fnc, vx, vy)
384 s.report(eq, reportByFunc)
385}
386
387func (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.
416func Exporter(f func(reflect.Type) bool) Option {
417 return exporter(f)
418}
419
420type exporter func(reflect.Type) bool
421
422func (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.
430func 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]).
444type 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.
451func (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.
457func (r Result) ByIgnore() bool {
458 return r.flags&reportByIgnore != 0
459}
460
461// ByMethod reports whether the Equal method determined equality.
462func (r Result) ByMethod() bool {
463 return r.flags&reportByMethod != 0
464}
465
466// ByFunc reports whether a [Comparer] function determined equality.
467func (r Result) ByFunc() bool {
468 return r.flags&reportByFunc != 0
469}
470
471// ByCycle reports whether a reference cycle was detected.
472func (r Result) ByCycle() bool {
473 return r.flags&reportByCycle != 0
474}
475
476type resultFlags uint
477
478const (
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.
494func 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
521type reporter struct{ reporterIface }
522type reporterIface interface {
523 PushStep(PathStep)
524 Report(Result)
525 PopStep()
526}
527
528func (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.
535func 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.
548func 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}