]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
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.md file. | |
4 | ||
5 | package cmp | |
6 | ||
7 | import ( | |
8 | "fmt" | |
9 | "reflect" | |
863486a6 | 10 | "regexp" |
107c1cdb ND |
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. | |
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. | |
863486a6 | 32 | filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption |
107c1cdb ND |
33 | } |
34 | ||
35 | // applicableOption represents the following types: | |
863486a6 | 36 | // Fundamental: ignore | validator | *comparer | *transformer |
107c1cdb ND |
37 | // Grouping: Options |
38 | type 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: | |
863486a6 | 46 | // Fundamental: ignore | validator | *comparer | *transformer |
107c1cdb ND |
47 | // Filters: *pathFilter | *valuesFilter |
48 | type coreOption interface { | |
49 | Option | |
50 | isCore() | |
51 | } | |
52 | ||
53 | type core struct{} | |
54 | ||
55 | func (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. | |
64 | type Options []Option | |
65 | ||
863486a6 | 66 | func (opts Options) filter(s *state, t reflect.Type, vx, vy reflect.Value) (out applicableOption) { |
107c1cdb | 67 | for _, opt := range opts { |
863486a6 | 68 | switch opt := opt.filter(s, t, vx, vy); opt.(type) { |
107c1cdb ND |
69 | case ignore: |
70 | return ignore{} // Only ignore can short-circuit evaluation | |
863486a6 AG |
71 | case validator: |
72 | out = validator{} // Takes precedence over comparer or transformer | |
107c1cdb ND |
73 | case *comparer, *transformer, Options: |
74 | switch out.(type) { | |
75 | case nil: | |
76 | out = opt | |
863486a6 AG |
77 | case validator: |
78 | // Keep validator | |
107c1cdb ND |
79 | case *comparer, *transformer, Options: |
80 | out = Options{out, opt} // Conflicting comparers or transformers | |
81 | } | |
82 | } | |
83 | } | |
84 | return out | |
85 | } | |
86 | ||
87 | func (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 | ||
98 | func (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 | // | |
863486a6 AG |
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 | // | |
107c1cdb ND |
114 | // The option passed in may be an Ignore, Transformer, Comparer, Options, or |
115 | // a previously filtered Option. | |
116 | func 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 | ||
126 | type pathFilter struct { | |
127 | core | |
128 | fnc func(Path) bool | |
129 | opt Option | |
130 | } | |
131 | ||
863486a6 | 132 | func (f pathFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption { |
107c1cdb | 133 | if f.fnc(s.curPath) { |
863486a6 | 134 | return f.opt.filter(s, t, vx, vy) |
107c1cdb ND |
135 | } |
136 | return nil | |
137 | } | |
138 | ||
139 | func (f pathFilter) String() string { | |
863486a6 | 140 | return fmt.Sprintf("FilterPath(%s, %v)", function.NameOf(reflect.ValueOf(f.fnc)), f.opt) |
107c1cdb ND |
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 | |
863486a6 AG |
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. | |
107c1cdb ND |
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. | |
157 | func 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 | ||
172 | type valuesFilter struct { | |
173 | core | |
174 | typ reflect.Type // T | |
175 | fnc reflect.Value // func(T, T) bool | |
176 | opt Option | |
177 | } | |
178 | ||
863486a6 AG |
179 | func (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 | |
107c1cdb ND |
182 | } |
183 | if (f.typ == nil || t.AssignableTo(f.typ)) && s.callTTBFunc(f.fnc, vx, vy) { | |
863486a6 | 184 | return f.opt.filter(s, t, vx, vy) |
107c1cdb ND |
185 | } |
186 | return nil | |
187 | } | |
188 | ||
189 | func (f valuesFilter) String() string { | |
863486a6 | 190 | return fmt.Sprintf("FilterValues(%s, %v)", function.NameOf(f.fnc), f.opt) |
107c1cdb ND |
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. | |
196 | func Ignore() Option { return ignore{} } | |
197 | ||
198 | type ignore struct{ core } | |
199 | ||
200 | func (ignore) isFiltered() bool { return false } | |
863486a6 AG |
201 | func (ignore) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { return ignore{} } |
202 | func (ignore) apply(s *state, _, _ reflect.Value) { s.report(true, reportByIgnore) } | |
107c1cdb ND |
203 | func (ignore) String() string { return "Ignore()" } |
204 | ||
863486a6 AG |
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. | |
208 | type validator struct{ core } | |
209 | ||
210 | func (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 | } | |
219 | func (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 | const help = "consider using a custom Comparer; if you control the implementation of type, you can also consider AllowUnexported or cmpopts.IgnoreUnexported" | |
229 | panic(fmt.Sprintf("cannot handle unexported field: %#v\n%s", s.curPath, help)) | |
230 | } | |
107c1cdb | 231 | |
863486a6 | 232 | panic("not reachable") |
107c1cdb ND |
233 | } |
234 | ||
863486a6 AG |
235 | // identRx represents a valid identifier according to the Go specification. |
236 | const identRx = `[_\p{L}][_\p{L}\p{N}]*` | |
237 | ||
238 | var identsRx = regexp.MustCompile(`^` + identRx + `(\.` + identRx + `)*$`) | |
239 | ||
107c1cdb ND |
240 | // Transformer returns an Option that applies a transformation function that |
241 | // converts values of a certain type into that of another. | |
242 | // | |
243 | // The transformer f must be a function "func(T) R" that converts values of | |
244 | // type T to those of type R and is implicitly filtered to input values | |
245 | // assignable to T. The transformer must not mutate T in any way. | |
246 | // | |
247 | // To help prevent some cases of infinite recursive cycles applying the | |
248 | // same transform to the output of itself (e.g., in the case where the | |
249 | // input and output types are the same), an implicit filter is added such that | |
250 | // a transformer is applicable only if that exact transformer is not already | |
251 | // in the tail of the Path since the last non-Transform step. | |
863486a6 AG |
252 | // For situations where the implicit filter is still insufficient, |
253 | // consider using cmpopts.AcyclicTransformer, which adds a filter | |
254 | // to prevent the transformer from being recursively applied upon itself. | |
107c1cdb ND |
255 | // |
256 | // The name is a user provided label that is used as the Transform.Name in the | |
863486a6 AG |
257 | // transformation PathStep (and eventually shown in the Diff output). |
258 | // The name must be a valid identifier or qualified identifier in Go syntax. | |
259 | // If empty, an arbitrary name is used. | |
107c1cdb ND |
260 | func Transformer(name string, f interface{}) Option { |
261 | v := reflect.ValueOf(f) | |
262 | if !function.IsType(v.Type(), function.Transformer) || v.IsNil() { | |
263 | panic(fmt.Sprintf("invalid transformer function: %T", f)) | |
264 | } | |
265 | if name == "" { | |
863486a6 AG |
266 | name = function.NameOf(v) |
267 | if !identsRx.MatchString(name) { | |
268 | name = "λ" // Lambda-symbol as placeholder name | |
269 | } | |
270 | } else if !identsRx.MatchString(name) { | |
107c1cdb ND |
271 | panic(fmt.Sprintf("invalid name: %q", name)) |
272 | } | |
273 | tr := &transformer{name: name, fnc: reflect.ValueOf(f)} | |
274 | if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 { | |
275 | tr.typ = ti | |
276 | } | |
277 | return tr | |
278 | } | |
279 | ||
280 | type transformer struct { | |
281 | core | |
282 | name string | |
283 | typ reflect.Type // T | |
284 | fnc reflect.Value // func(T) R | |
285 | } | |
286 | ||
287 | func (tr *transformer) isFiltered() bool { return tr.typ != nil } | |
288 | ||
863486a6 | 289 | func (tr *transformer) filter(s *state, t reflect.Type, _, _ reflect.Value) applicableOption { |
107c1cdb | 290 | for i := len(s.curPath) - 1; i >= 0; i-- { |
863486a6 | 291 | if t, ok := s.curPath[i].(Transform); !ok { |
107c1cdb ND |
292 | break // Hit most recent non-Transform step |
293 | } else if tr == t.trans { | |
294 | return nil // Cannot directly use same Transform | |
295 | } | |
296 | } | |
297 | if tr.typ == nil || t.AssignableTo(tr.typ) { | |
298 | return tr | |
299 | } | |
300 | return nil | |
301 | } | |
302 | ||
303 | func (tr *transformer) apply(s *state, vx, vy reflect.Value) { | |
863486a6 AG |
304 | step := Transform{&transform{pathStep{typ: tr.fnc.Type().Out(0)}, tr}} |
305 | vvx := s.callTRFunc(tr.fnc, vx, step) | |
306 | vvy := s.callTRFunc(tr.fnc, vy, step) | |
307 | step.vx, step.vy = vvx, vvy | |
308 | s.compareAny(step) | |
107c1cdb ND |
309 | } |
310 | ||
311 | func (tr transformer) String() string { | |
863486a6 | 312 | return fmt.Sprintf("Transformer(%s, %s)", tr.name, function.NameOf(tr.fnc)) |
107c1cdb ND |
313 | } |
314 | ||
315 | // Comparer returns an Option that determines whether two values are equal | |
316 | // to each other. | |
317 | // | |
318 | // The comparer f must be a function "func(T, T) bool" and is implicitly | |
319 | // filtered to input values assignable to T. If T is an interface, it is | |
320 | // possible that f is called with two values of different concrete types that | |
321 | // both implement T. | |
322 | // | |
323 | // The equality function must be: | |
324 | // • Symmetric: equal(x, y) == equal(y, x) | |
325 | // • Deterministic: equal(x, y) == equal(x, y) | |
326 | // • Pure: equal(x, y) does not modify x or y | |
327 | func Comparer(f interface{}) Option { | |
328 | v := reflect.ValueOf(f) | |
329 | if !function.IsType(v.Type(), function.Equal) || v.IsNil() { | |
330 | panic(fmt.Sprintf("invalid comparer function: %T", f)) | |
331 | } | |
332 | cm := &comparer{fnc: v} | |
333 | if ti := v.Type().In(0); ti.Kind() != reflect.Interface || ti.NumMethod() > 0 { | |
334 | cm.typ = ti | |
335 | } | |
336 | return cm | |
337 | } | |
338 | ||
339 | type comparer struct { | |
340 | core | |
341 | typ reflect.Type // T | |
342 | fnc reflect.Value // func(T, T) bool | |
343 | } | |
344 | ||
345 | func (cm *comparer) isFiltered() bool { return cm.typ != nil } | |
346 | ||
863486a6 | 347 | func (cm *comparer) filter(_ *state, t reflect.Type, _, _ reflect.Value) applicableOption { |
107c1cdb ND |
348 | if cm.typ == nil || t.AssignableTo(cm.typ) { |
349 | return cm | |
350 | } | |
351 | return nil | |
352 | } | |
353 | ||
354 | func (cm *comparer) apply(s *state, vx, vy reflect.Value) { | |
355 | eq := s.callTTBFunc(cm.fnc, vx, vy) | |
863486a6 | 356 | s.report(eq, reportByFunc) |
107c1cdb ND |
357 | } |
358 | ||
359 | func (cm comparer) String() string { | |
863486a6 | 360 | return fmt.Sprintf("Comparer(%s)", function.NameOf(cm.fnc)) |
107c1cdb ND |
361 | } |
362 | ||
363 | // AllowUnexported returns an Option that forcibly allows operations on | |
364 | // unexported fields in certain structs, which are specified by passing in a | |
365 | // value of each struct type. | |
366 | // | |
367 | // Users of this option must understand that comparing on unexported fields | |
368 | // from external packages is not safe since changes in the internal | |
369 | // implementation of some external package may cause the result of Equal | |
370 | // to unexpectedly change. However, it may be valid to use this option on types | |
371 | // defined in an internal package where the semantic meaning of an unexported | |
372 | // field is in the control of the user. | |
373 | // | |
863486a6 | 374 | // In many cases, a custom Comparer should be used instead that defines |
107c1cdb ND |
375 | // equality as a function of the public API of a type rather than the underlying |
376 | // unexported implementation. | |
377 | // | |
378 | // For example, the reflect.Type documentation defines equality to be determined | |
379 | // by the == operator on the interface (essentially performing a shallow pointer | |
380 | // comparison) and most attempts to compare *regexp.Regexp types are interested | |
381 | // in only checking that the regular expression strings are equal. | |
382 | // Both of these are accomplished using Comparers: | |
383 | // | |
384 | // Comparer(func(x, y reflect.Type) bool { return x == y }) | |
385 | // Comparer(func(x, y *regexp.Regexp) bool { return x.String() == y.String() }) | |
386 | // | |
387 | // In other cases, the cmpopts.IgnoreUnexported option can be used to ignore | |
388 | // all unexported fields on specified struct types. | |
389 | func AllowUnexported(types ...interface{}) Option { | |
390 | if !supportAllowUnexported { | |
391 | panic("AllowUnexported is not supported on purego builds, Google App Engine Standard, or GopherJS") | |
392 | } | |
393 | m := make(map[reflect.Type]bool) | |
394 | for _, typ := range types { | |
395 | t := reflect.TypeOf(typ) | |
396 | if t.Kind() != reflect.Struct { | |
397 | panic(fmt.Sprintf("invalid struct type: %T", typ)) | |
398 | } | |
399 | m[t] = true | |
400 | } | |
401 | return visibleStructs(m) | |
402 | } | |
403 | ||
404 | type visibleStructs map[reflect.Type]bool | |
405 | ||
863486a6 | 406 | func (visibleStructs) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { |
107c1cdb ND |
407 | panic("not implemented") |
408 | } | |
409 | ||
863486a6 AG |
410 | // Result represents the comparison result for a single node and |
411 | // is provided by cmp when calling Result (see Reporter). | |
412 | type Result struct { | |
413 | _ [0]func() // Make Result incomparable | |
414 | flags resultFlags | |
415 | } | |
416 | ||
417 | // Equal reports whether the node was determined to be equal or not. | |
418 | // As a special case, ignored nodes are considered equal. | |
419 | func (r Result) Equal() bool { | |
420 | return r.flags&(reportEqual|reportByIgnore) != 0 | |
421 | } | |
422 | ||
423 | // ByIgnore reports whether the node is equal because it was ignored. | |
424 | // This never reports true if Equal reports false. | |
425 | func (r Result) ByIgnore() bool { | |
426 | return r.flags&reportByIgnore != 0 | |
427 | } | |
428 | ||
429 | // ByMethod reports whether the Equal method determined equality. | |
430 | func (r Result) ByMethod() bool { | |
431 | return r.flags&reportByMethod != 0 | |
432 | } | |
433 | ||
434 | // ByFunc reports whether a Comparer function determined equality. | |
435 | func (r Result) ByFunc() bool { | |
436 | return r.flags&reportByFunc != 0 | |
437 | } | |
438 | ||
439 | type resultFlags uint | |
440 | ||
441 | const ( | |
442 | _ resultFlags = (1 << iota) / 2 | |
443 | ||
444 | reportEqual | |
445 | reportUnequal | |
446 | reportByIgnore | |
447 | reportByMethod | |
448 | reportByFunc | |
449 | ) | |
450 | ||
451 | // Reporter is an Option that can be passed to Equal. When Equal traverses | |
452 | // the value trees, it calls PushStep as it descends into each node in the | |
453 | // tree and PopStep as it ascend out of the node. The leaves of the tree are | |
454 | // either compared (determined to be equal or not equal) or ignored and reported | |
455 | // as such by calling the Report method. | |
456 | func Reporter(r interface { | |
457 | // PushStep is called when a tree-traversal operation is performed. | |
458 | // The PathStep itself is only valid until the step is popped. | |
459 | // The PathStep.Values are valid for the duration of the entire traversal | |
460 | // and must not be mutated. | |
461 | // | |
462 | // Equal always calls PushStep at the start to provide an operation-less | |
463 | // PathStep used to report the root values. | |
107c1cdb | 464 | // |
863486a6 AG |
465 | // Within a slice, the exact set of inserted, removed, or modified elements |
466 | // is unspecified and may change in future implementations. | |
467 | // The entries of a map are iterated through in an unspecified order. | |
468 | PushStep(PathStep) | |
469 | ||
470 | // Report is called exactly once on leaf nodes to report whether the | |
471 | // comparison identified the node as equal, unequal, or ignored. | |
472 | // A leaf node is one that is immediately preceded by and followed by | |
473 | // a pair of PushStep and PopStep calls. | |
474 | Report(Result) | |
475 | ||
476 | // PopStep ascends back up the value tree. | |
477 | // There is always a matching pop call for every push call. | |
478 | PopStep() | |
479 | }) Option { | |
480 | return reporter{r} | |
481 | } | |
107c1cdb | 482 | |
863486a6 AG |
483 | type reporter struct{ reporterIface } |
484 | type reporterIface interface { | |
485 | PushStep(PathStep) | |
486 | Report(Result) | |
487 | PopStep() | |
488 | } | |
107c1cdb | 489 | |
863486a6 AG |
490 | func (reporter) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { |
491 | panic("not implemented") | |
107c1cdb ND |
492 | } |
493 | ||
494 | // normalizeOption normalizes the input options such that all Options groups | |
495 | // are flattened and groups with a single element are reduced to that element. | |
496 | // Only coreOptions and Options containing coreOptions are allowed. | |
497 | func normalizeOption(src Option) Option { | |
498 | switch opts := flattenOptions(nil, Options{src}); len(opts) { | |
499 | case 0: | |
500 | return nil | |
501 | case 1: | |
502 | return opts[0] | |
503 | default: | |
504 | return opts | |
505 | } | |
506 | } | |
507 | ||
508 | // flattenOptions copies all options in src to dst as a flat list. | |
509 | // Only coreOptions and Options containing coreOptions are allowed. | |
510 | func flattenOptions(dst, src Options) Options { | |
511 | for _, opt := range src { | |
512 | switch opt := opt.(type) { | |
513 | case nil: | |
514 | continue | |
515 | case Options: | |
516 | dst = flattenOptions(dst, opt) | |
517 | case coreOption: | |
518 | dst = append(dst, opt) | |
519 | default: | |
520 | panic(fmt.Sprintf("invalid option type: %T", opt)) | |
521 | } | |
522 | } | |
523 | return dst | |
524 | } |