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 cmp/cmpopts package provides helper functions for creating options that 24// 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// Fundamental: ignore | validator | *comparer | *transformer 37// Grouping: Options 38type applicableOption interface { 39 Option 40 41 // apply executes the option, which may mutate s or panic. 42 apply(s *state, vx, vy reflect.Value) 43} 44 45// coreOption represents the following types: 46// Fundamental: ignore | validator | *comparer | *transformer 47// Filters: *pathFilter | *valuesFilter 48type coreOption interface { 49 Option 50 isCore() 51} 52 53type core struct{} 54 55func (core) isCore() {} 56 57// Options is a list of Option values that also satisfies the Option interface. 58// Helper comparison packages may return an Options value when packing multiple 59// Option values into a single Option. When this package processes an Options, 60// it will be implicitly expanded into a flat list. 61// 62// Applying a filter on an Options is equivalent to applying that same filter 63// on all individual options held within. 64type Options []Option 65 66func (opts Options) filter(s *state, t reflect.Type, vx, vy reflect.Value) (out applicableOption) { 67 for _, opt := range opts { 68 switch opt := opt.filter(s, t, vx, vy); opt.(type) { 69 case ignore: 70 return ignore{} // Only ignore can short-circuit evaluation 71 case validator: 72 out = validator{} // Takes precedence over comparer or transformer 73 case *comparer, *transformer, Options: 74 switch out.(type) { 75 case nil: 76 out = opt 77 case validator: 78 // Keep validator 79 case *comparer, *transformer, Options: 80 out = Options{out, opt} // Conflicting comparers or transformers 81 } 82 } 83 } 84 return out 85} 86 87func (opts Options) apply(s *state, _, _ reflect.Value) { 88 const warning = "ambiguous set of applicable options" 89 const help = "consider using filters to ensure at most one Comparer or Transformer may apply" 90 var ss []string 91 for _, opt := range flattenOptions(nil, opts) { 92 ss = append(ss, fmt.Sprint(opt)) 93 } 94 set := strings.Join(ss, "\n\t") 95 panic(fmt.Sprintf("%s at %#v:\n\t%s\n%s", warning, s.curPath, set, help)) 96} 97 98func (opts Options) String() string { 99 var ss []string 100 for _, opt := range opts { 101 ss = append(ss, fmt.Sprint(opt)) 102 } 103 return fmt.Sprintf("Options{%s}", strings.Join(ss, ", ")) 104} 105 106// FilterPath returns a new Option where opt is only evaluated if filter f 107// returns true for the current Path in the value tree. 108// 109// This filter is called even if a slice element or map entry is missing and 110// provides an opportunity to ignore such cases. The filter function must be 111// symmetric such that the filter result is identical regardless of whether the 112// missing value is from x or y. 113// 114// The option passed in may be an Ignore, Transformer, Comparer, Options, or 115// a previously filtered Option. 116func FilterPath(f func(Path) bool, opt Option) Option { 117 if f == nil { 118 panic("invalid path filter function") 119 } 120 if opt := normalizeOption(opt); opt != nil { 121 return &pathFilter{fnc: f, opt: opt} 122 } 123 return nil 124} 125 126type pathFilter struct { 127 core 128 fnc func(Path) bool 129 opt Option 130} 131 132func (f pathFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption { 133 if f.fnc(s.curPath) { 134 return f.opt.filter(s, t, vx, vy) 135 } 136 return nil 137} 138 139func (f pathFilter) String() string { 140 return fmt.Sprintf("FilterPath(%s, %v)", function.NameOf(reflect.ValueOf(f.fnc)), f.opt) 141} 142 143// FilterValues returns a new Option where opt is only evaluated if filter f, 144// which is a function of the form "func(T, T) bool", returns true for the 145// current pair of values being compared. If either value is invalid or 146// the type of the values is not assignable to T, then this filter implicitly 147// returns false. 148// 149// The filter function must be 150// symmetric (i.e., agnostic to the order of the inputs) and 151// deterministic (i.e., produces the same result when given the same inputs). 152// If T is an interface, it is possible that f is called with two values with 153// different concrete types that both implement T. 154// 155// The option passed in may be an Ignore, Transformer, Comparer, Options, or 156// a previously filtered Option. 157func FilterValues(f interface{}, opt Option) Option { 158 v := reflect.ValueOf(f) 159 if !function.IsType(v.Type(), function.ValueFilter) || v.IsNil() { 160 panic(fmt.Sprintf("invalid values filter function: %T", f)) 161 } 162 if opt := normalizeOption(opt); opt != nil { 163 vf := &valuesFilter{fnc: v, opt: opt} 164 if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 { 165 vf.typ = ti 166 } 167 return vf 168 } 169 return nil 170} 171 172type valuesFilter struct { 173 core 174 typ reflect.Type // T 175 fnc reflect.Value // func(T, T) bool 176 opt Option 177} 178 179func (f valuesFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption { 180 if !vx.IsValid() || !vx.CanInterface() || !vy.IsValid() || !vy.CanInterface() { 181 return nil 182 } 183 if (f.typ == nil || t.AssignableTo(f.typ)) && s.callTTBFunc(f.fnc, vx, vy) { 184 return f.opt.filter(s, t, vx, vy) 185 } 186 return nil 187} 188 189func (f valuesFilter) String() string { 190 return fmt.Sprintf("FilterValues(%s, %v)", function.NameOf(f.fnc), f.opt) 191} 192 193// Ignore is an Option that causes all comparisons to be ignored. 194// This value is intended to be combined with FilterPath or FilterValues. 195// It is an error to pass an unfiltered Ignore option to Equal. 196func Ignore() Option { return ignore{} } 197 198type ignore struct{ core } 199 200func (ignore) isFiltered() bool { return false } 201func (ignore) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { return ignore{} } 202func (ignore) apply(s *state, _, _ reflect.Value) { s.report(true, reportByIgnore) } 203func (ignore) String() string { return "Ignore()" } 204 205// validator is a sentinel Option type to indicate that some options could not 206// be evaluated due to unexported fields, missing slice elements, or 207// missing map entries. Both values are validator only for unexported fields. 208type validator struct{ core } 209 210func (validator) filter(_ *state, _ reflect.Type, vx, vy reflect.Value) applicableOption { 211 if !vx.IsValid() || !vy.IsValid() { 212 return validator{} 213 } 214 if !vx.CanInterface() || !vy.CanInterface() { 215 return validator{} 216 } 217 return nil 218} 219func (validator) apply(s *state, vx, vy reflect.Value) { 220 // Implies missing slice element or map entry. 221 if !vx.IsValid() || !vy.IsValid() { 222 s.report(vx.IsValid() == vy.IsValid(), 0) 223 return 224 } 225 226 // Unable to Interface implies unexported field without visibility access. 227 if !vx.CanInterface() || !vy.CanInterface() { 228 help := "consider using a custom Comparer; if you control the implementation of type, you can also consider using an Exporter, AllowUnexported, or cmpopts.IgnoreUnexported" 229 var name string 230 if t := s.curPath.Index(-2).Type(); t.Name() != "" { 231 // Named type with unexported fields. 232 name = fmt.Sprintf("%q.%v", t.PkgPath(), t.Name()) // e.g., "path/to/package".MyType 233 if _, ok := reflect.New(t).Interface().(error); ok { 234 help = "consider using cmpopts.EquateErrors to compare error values" 235 } 236 } else { 237 // Unnamed type with unexported fields. Derive PkgPath from field. 238 var pkgPath string 239 for i := 0; i < t.NumField() && pkgPath == ""; i++ { 240 pkgPath = t.Field(i).PkgPath 241 } 242 name = fmt.Sprintf("%q.(%v)", pkgPath, t.String()) // e.g., "path/to/package".(struct { a int }) 243 } 244 panic(fmt.Sprintf("cannot handle unexported field at %#v:\n\t%v\n%s", s.curPath, name, help)) 245 } 246 247 panic("not reachable") 248} 249 250// identRx represents a valid identifier according to the Go specification. 251const identRx = `[_\p{L}][_\p{L}\p{N}]*` 252 253var identsRx = regexp.MustCompile(`^` + identRx + `(\.` + identRx + `)*$`) 254 255// Transformer returns an Option that applies a transformation function that 256// converts values of a certain type into that of another. 257// 258// The transformer f must be a function "func(T) R" that converts values of 259// type T to those of type R and is implicitly filtered to input values 260// assignable to T. The transformer must not mutate T in any way. 261// 262// To help prevent some cases of infinite recursive cycles applying the 263// same transform to the output of itself (e.g., in the case where the 264// input and output types are the same), an implicit filter is added such that 265// a transformer is applicable only if that exact transformer is not already 266// in the tail of the Path since the last non-Transform step. 267// For situations where the implicit filter is still insufficient, 268// consider using cmpopts.AcyclicTransformer, which adds a filter 269// to prevent the transformer from being recursively applied upon itself. 270// 271// The name is a user provided label that is used as the Transform.Name in the 272// transformation PathStep (and eventually shown in the Diff output). 273// The name must be a valid identifier or qualified identifier in Go syntax. 274// If empty, an arbitrary name is used. 275func Transformer(name string, f interface{}) Option { 276 v := reflect.ValueOf(f) 277 if !function.IsType(v.Type(), function.Transformer) || v.IsNil() { 278 panic(fmt.Sprintf("invalid transformer function: %T", f)) 279 } 280 if name == "" { 281 name = function.NameOf(v) 282 if !identsRx.MatchString(name) { 283 name = "λ" // Lambda-symbol as placeholder name 284 } 285 } else if !identsRx.MatchString(name) { 286 panic(fmt.Sprintf("invalid name: %q", name)) 287 } 288 tr := &transformer{name: name, fnc: reflect.ValueOf(f)} 289 if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 { 290 tr.typ = ti 291 } 292 return tr 293} 294 295type transformer struct { 296 core 297 name string 298 typ reflect.Type // T 299 fnc reflect.Value // func(T) R 300} 301 302func (tr *transformer) isFiltered() bool { return tr.typ != nil } 303 304func (tr *transformer) filter(s *state, t reflect.Type, _, _ reflect.Value) applicableOption { 305 for i := len(s.curPath) - 1; i >= 0; i-- { 306 if t, ok := s.curPath[i].(Transform); !ok { 307 break // Hit most recent non-Transform step 308 } else if tr == t.trans { 309 return nil // Cannot directly use same Transform 310 } 311 } 312 if tr.typ == nil || t.AssignableTo(tr.typ) { 313 return tr 314 } 315 return nil 316} 317 318func (tr *transformer) apply(s *state, vx, vy reflect.Value) { 319 step := Transform{&transform{pathStep{typ: tr.fnc.Type().Out(0)}, tr}} 320 vvx := s.callTRFunc(tr.fnc, vx, step) 321 vvy := s.callTRFunc(tr.fnc, vy, step) 322 step.vx, step.vy = vvx, vvy 323 s.compareAny(step) 324} 325 326func (tr transformer) String() string { 327 return fmt.Sprintf("Transformer(%s, %s)", tr.name, function.NameOf(tr.fnc)) 328} 329 330// Comparer returns an Option that determines whether two values are equal 331// to each other. 332// 333// The comparer f must be a function "func(T, T) bool" and is implicitly 334// filtered to input values assignable to T. If T is an interface, it is 335// possible that f is called with two values of different concrete types that 336// both implement T. 337// 338// The equality function must be: 339// • Symmetric: equal(x, y) == equal(y, x) 340// • Deterministic: equal(x, y) == equal(x, y) 341// • Pure: equal(x, y) does not modify x or y 342func Comparer(f interface{}) Option { 343 v := reflect.ValueOf(f) 344 if !function.IsType(v.Type(), function.Equal) || v.IsNil() { 345 panic(fmt.Sprintf("invalid comparer function: %T", f)) 346 } 347 cm := &comparer{fnc: v} 348 if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 { 349 cm.typ = ti 350 } 351 return cm 352} 353 354type comparer struct { 355 core 356 typ reflect.Type // T 357 fnc reflect.Value // func(T, T) bool 358} 359 360func (cm *comparer) isFiltered() bool { return cm.typ != nil } 361 362func (cm *comparer) filter(_ *state, t reflect.Type, _, _ reflect.Value) applicableOption { 363 if cm.typ == nil || t.AssignableTo(cm.typ) { 364 return cm 365 } 366 return nil 367} 368 369func (cm *comparer) apply(s *state, vx, vy reflect.Value) { 370 eq := s.callTTBFunc(cm.fnc, vx, vy) 371 s.report(eq, reportByFunc) 372} 373 374func (cm comparer) String() string { 375 return fmt.Sprintf("Comparer(%s)", function.NameOf(cm.fnc)) 376} 377 378// Exporter returns an Option that specifies whether Equal is allowed to 379// introspect into the unexported fields of certain struct types. 380// 381// Users of this option must understand that comparing on unexported fields 382// from external packages is not safe since changes in the internal 383// implementation of some external package may cause the result of Equal 384// to unexpectedly change. However, it may be valid to use this option on types 385// defined in an internal package where the semantic meaning of an unexported 386// field is in the control of the user. 387// 388// In many cases, a custom Comparer should be used instead that defines 389// equality as a function of the public API of a type rather than the underlying 390// unexported implementation. 391// 392// For example, the reflect.Type documentation defines equality to be determined 393// by the == operator on the interface (essentially performing a shallow pointer 394// comparison) and most attempts to compare *regexp.Regexp types are interested 395// in only checking that the regular expression strings are equal. 396// Both of these are accomplished using Comparers: 397// 398// Comparer(func(x, y reflect.Type) bool { return x == y }) 399// Comparer(func(x, y *regexp.Regexp) bool { return x.String() == y.String() }) 400// 401// In other cases, the cmpopts.IgnoreUnexported option can be used to ignore 402// all unexported fields on specified struct types. 403func Exporter(f func(reflect.Type) bool) Option { 404 if !supportExporters { 405 panic("Exporter is not supported on purego builds") 406 } 407 return exporter(f) 408} 409 410type exporter func(reflect.Type) bool 411 412func (exporter) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { 413 panic("not implemented") 414} 415 416// AllowUnexported returns an Options that allows Equal to forcibly introspect 417// unexported fields of the specified struct types. 418// 419// See Exporter for the proper use of this option. 420func AllowUnexported(types ...interface{}) Option { 421 m := make(map[reflect.Type]bool) 422 for _, typ := range types { 423 t := reflect.TypeOf(typ) 424 if t.Kind() != reflect.Struct { 425 panic(fmt.Sprintf("invalid struct type: %T", typ)) 426 } 427 m[t] = true 428 } 429 return exporter(func(t reflect.Type) bool { return m[t] }) 430} 431 432// Result represents the comparison result for a single node and 433// is provided by cmp when calling Result (see Reporter). 434type Result struct { 435 _ [0]func() // Make Result incomparable 436 flags resultFlags 437} 438 439// Equal reports whether the node was determined to be equal or not. 440// As a special case, ignored nodes are considered equal. 441func (r Result) Equal() bool { 442 return r.flags&(reportEqual|reportByIgnore) != 0 443} 444 445// ByIgnore reports whether the node is equal because it was ignored. 446// This never reports true if Equal reports false. 447func (r Result) ByIgnore() bool { 448 return r.flags&reportByIgnore != 0 449} 450 451// ByMethod reports whether the Equal method determined equality. 452func (r Result) ByMethod() bool { 453 return r.flags&reportByMethod != 0 454} 455 456// ByFunc reports whether a Comparer function determined equality. 457func (r Result) ByFunc() bool { 458 return r.flags&reportByFunc != 0 459} 460 461// ByCycle reports whether a reference cycle was detected. 462func (r Result) ByCycle() bool { 463 return r.flags&reportByCycle != 0 464} 465 466type resultFlags uint 467 468const ( 469 _ resultFlags = (1 << iota) / 2 470 471 reportEqual 472 reportUnequal 473 reportByIgnore 474 reportByMethod 475 reportByFunc 476 reportByCycle 477) 478 479// Reporter is an Option that can be passed to Equal. When Equal traverses 480// the value trees, it calls PushStep as it descends into each node in the 481// tree and PopStep as it ascend out of the node. The leaves of the tree are 482// either compared (determined to be equal or not equal) or ignored and reported 483// as such by calling the Report method. 484func Reporter(r interface { 485 // PushStep is called when a tree-traversal operation is performed. 486 // The PathStep itself is only valid until the step is popped. 487 // The PathStep.Values are valid for the duration of the entire traversal 488 // and must not be mutated. 489 // 490 // Equal always calls PushStep at the start to provide an operation-less 491 // PathStep used to report the root values. 492 // 493 // Within a slice, the exact set of inserted, removed, or modified elements 494 // is unspecified and may change in future implementations. 495 // The entries of a map are iterated through in an unspecified order. 496 PushStep(PathStep) 497 498 // Report is called exactly once on leaf nodes to report whether the 499 // comparison identified the node as equal, unequal, or ignored. 500 // A leaf node is one that is immediately preceded by and followed by 501 // a pair of PushStep and PopStep calls. 502 Report(Result) 503 504 // PopStep ascends back up the value tree. 505 // There is always a matching pop call for every push call. 506 PopStep() 507}) Option { 508 return reporter{r} 509} 510 511type reporter struct{ reporterIface } 512type reporterIface interface { 513 PushStep(PathStep) 514 Report(Result) 515 PopStep() 516} 517 518func (reporter) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { 519 panic("not implemented") 520} 521 522// normalizeOption normalizes the input options such that all Options groups 523// are flattened and groups with a single element are reduced to that element. 524// Only coreOptions and Options containing coreOptions are allowed. 525func normalizeOption(src Option) Option { 526 switch opts := flattenOptions(nil, Options{src}); len(opts) { 527 case 0: 528 return nil 529 case 1: 530 return opts[0] 531 default: 532 return opts 533 } 534} 535 536// flattenOptions copies all options in src to dst as a flat list. 537// Only coreOptions and Options containing coreOptions are allowed. 538func flattenOptions(dst, src Options) Options { 539 for _, opt := range src { 540 switch opt := opt.(type) { 541 case nil: 542 continue 543 case Options: 544 dst = flattenOptions(dst, opt) 545 case coreOption: 546 dst = append(dst, opt) 547 default: 548 panic(fmt.Sprintf("invalid option type: %T", opt)) 549 } 550 } 551 return dst 552} 553