diff options
author | Alexandre Garand <alexandre.garand@fretlink.com> | 2019-08-09 15:59:15 +0200 |
---|---|---|
committer | Alexandre Garand <alexandre.garand@fretlink.com> | 2019-08-09 16:39:21 +0200 |
commit | 863486a6b71ed0e562a3965bed56465d007b1418 (patch) | |
tree | e93f6a687695af86d54237ec9f575d4ef104222d /vendor/github.com/google/go-cmp/cmp/compare.go | |
parent | 49c1c7b4dc69ffb9ab52330e6dc52ccdd6351087 (diff) | |
download | terraform-provider-statuscake-863486a6b71ed0e562a3965bed56465d007b1418.tar.gz terraform-provider-statuscake-863486a6b71ed0e562a3965bed56465d007b1418.tar.zst terraform-provider-statuscake-863486a6b71ed0e562a3965bed56465d007b1418.zip |
update vendor and go.modadd_contact_groups
Diffstat (limited to 'vendor/github.com/google/go-cmp/cmp/compare.go')
-rw-r--r-- | vendor/github.com/google/go-cmp/cmp/compare.go | 557 |
1 files changed, 310 insertions, 247 deletions
diff --git a/vendor/github.com/google/go-cmp/cmp/compare.go b/vendor/github.com/google/go-cmp/cmp/compare.go index 7e215f2..2133562 100644 --- a/vendor/github.com/google/go-cmp/cmp/compare.go +++ b/vendor/github.com/google/go-cmp/cmp/compare.go | |||
@@ -29,26 +29,17 @@ package cmp | |||
29 | import ( | 29 | import ( |
30 | "fmt" | 30 | "fmt" |
31 | "reflect" | 31 | "reflect" |
32 | "strings" | ||
32 | 33 | ||
33 | "github.com/google/go-cmp/cmp/internal/diff" | 34 | "github.com/google/go-cmp/cmp/internal/diff" |
35 | "github.com/google/go-cmp/cmp/internal/flags" | ||
34 | "github.com/google/go-cmp/cmp/internal/function" | 36 | "github.com/google/go-cmp/cmp/internal/function" |
35 | "github.com/google/go-cmp/cmp/internal/value" | 37 | "github.com/google/go-cmp/cmp/internal/value" |
36 | ) | 38 | ) |
37 | 39 | ||
38 | // BUG(dsnet): Maps with keys containing NaN values cannot be properly compared due to | ||
39 | // the reflection package's inability to retrieve such entries. Equal will panic | ||
40 | // anytime it comes across a NaN key, but this behavior may change. | ||
41 | // | ||
42 | // See https://golang.org/issue/11104 for more details. | ||
43 | |||
44 | var nothing = reflect.Value{} | ||
45 | |||
46 | // Equal reports whether x and y are equal by recursively applying the | 40 | // 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: | 41 | // following rules in the given order to x and y and all of their sub-values: |
48 | // | 42 | // |
49 | // • If two values are not of the same type, then they are never equal | ||
50 | // and the overall result is false. | ||
51 | // | ||
52 | // • Let S be the set of all Ignore, Transformer, and Comparer options that | 43 | // • Let S be the set of all Ignore, Transformer, and Comparer options that |
53 | // remain after applying all path filters, value filters, and type filters. | 44 | // remain after applying all path filters, value filters, and type filters. |
54 | // If at least one Ignore exists in S, then the comparison is ignored. | 45 | // If at least one Ignore exists in S, then the comparison is ignored. |
@@ -61,43 +52,79 @@ var nothing = reflect.Value{} | |||
61 | // | 52 | // |
62 | // • If the values have an Equal method of the form "(T) Equal(T) bool" or | 53 | // • If the values have an Equal method of the form "(T) Equal(T) bool" or |
63 | // "(T) Equal(I) bool" where T is assignable to I, then use the result of | 54 | // "(T) Equal(I) bool" where T is assignable to I, then use the result of |
64 | // x.Equal(y) even if x or y is nil. | 55 | // x.Equal(y) even if x or y is nil. Otherwise, no such method exists and |
65 | // Otherwise, no such method exists and evaluation proceeds to the next rule. | 56 | // evaluation proceeds to the next rule. |
66 | // | 57 | // |
67 | // • Lastly, try to compare x and y based on their basic kinds. | 58 | // • Lastly, try to compare x and y based on their basic kinds. |
68 | // Simple kinds like booleans, integers, floats, complex numbers, strings, and | 59 | // Simple kinds like booleans, integers, floats, complex numbers, strings, and |
69 | // channels are compared using the equivalent of the == operator in Go. | 60 | // channels are compared using the equivalent of the == operator in Go. |
70 | // Functions are only equal if they are both nil, otherwise they are unequal. | 61 | // Functions are only equal if they are both nil, otherwise they are unequal. |
71 | // Pointers are equal if the underlying values they point to are also equal. | ||
72 | // Interfaces are equal if their underlying concrete values are also equal. | ||
73 | // | 62 | // |
74 | // Structs are equal if all of their fields are equal. If a struct contains | 63 | // Structs are equal if recursively calling Equal on all fields report equal. |
75 | // unexported fields, Equal panics unless the AllowUnexported option is used or | 64 | // If a struct contains unexported fields, Equal panics unless an Ignore option |
76 | // an Ignore option (e.g., cmpopts.IgnoreUnexported) ignores that field. | 65 | // (e.g., cmpopts.IgnoreUnexported) ignores that field or the AllowUnexported |
66 | // option explicitly permits comparing the unexported field. | ||
67 | // | ||
68 | // Slices are equal if they are both nil or both non-nil, where recursively | ||
69 | // calling Equal on all non-ignored slice or array elements report equal. | ||
70 | // Empty non-nil slices and nil slices are not equal; to equate empty slices, | ||
71 | // consider using cmpopts.EquateEmpty. | ||
77 | // | 72 | // |
78 | // Arrays, slices, and maps are equal if they are both nil or both non-nil | 73 | // Maps are equal if they are both nil or both non-nil, where recursively |
79 | // with the same length and the elements at each index or key are equal. | 74 | // calling Equal on all non-ignored map entries report equal. |
80 | // Note that a non-nil empty slice and a nil slice are not equal. | ||
81 | // To equate empty slices and maps, consider using cmpopts.EquateEmpty. | ||
82 | // Map keys are equal according to the == operator. | 75 | // Map keys are equal according to the == operator. |
83 | // To use custom comparisons for map keys, consider using cmpopts.SortMaps. | 76 | // To use custom comparisons for map keys, consider using cmpopts.SortMaps. |
77 | // Empty non-nil maps and nil maps are not equal; to equate empty maps, | ||
78 | // consider using cmpopts.EquateEmpty. | ||
79 | // | ||
80 | // Pointers and interfaces are equal if they are both nil or both non-nil, | ||
81 | // where they have the same underlying concrete type and recursively | ||
82 | // calling Equal on the underlying values reports equal. | ||
84 | func Equal(x, y interface{}, opts ...Option) bool { | 83 | func Equal(x, y interface{}, opts ...Option) bool { |
84 | vx := reflect.ValueOf(x) | ||
85 | vy := reflect.ValueOf(y) | ||
86 | |||
87 | // If the inputs are different types, auto-wrap them in an empty interface | ||
88 | // so that they have the same parent type. | ||
89 | var t reflect.Type | ||
90 | if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() { | ||
91 | t = reflect.TypeOf((*interface{})(nil)).Elem() | ||
92 | if vx.IsValid() { | ||
93 | vvx := reflect.New(t).Elem() | ||
94 | vvx.Set(vx) | ||
95 | vx = vvx | ||
96 | } | ||
97 | if vy.IsValid() { | ||
98 | vvy := reflect.New(t).Elem() | ||
99 | vvy.Set(vy) | ||
100 | vy = vvy | ||
101 | } | ||
102 | } else { | ||
103 | t = vx.Type() | ||
104 | } | ||
105 | |||
85 | s := newState(opts) | 106 | s := newState(opts) |
86 | s.compareAny(reflect.ValueOf(x), reflect.ValueOf(y)) | 107 | s.compareAny(&pathStep{t, vx, vy}) |
87 | return s.result.Equal() | 108 | return s.result.Equal() |
88 | } | 109 | } |
89 | 110 | ||
90 | // Diff returns a human-readable report of the differences between two values. | 111 | // Diff returns a human-readable report of the differences between two values. |
91 | // It returns an empty string if and only if Equal returns true for the same | 112 | // It returns an empty string if and only if Equal returns true for the same |
92 | // input values and options. The output string will use the "-" symbol to | 113 | // input values and options. |
93 | // indicate elements removed from x, and the "+" symbol to indicate elements | 114 | // |
94 | // added to y. | 115 | // The output is displayed as a literal in pseudo-Go syntax. |
116 | // At the start of each line, a "-" prefix indicates an element removed from x, | ||
117 | // a "+" prefix to indicates an element added to y, and the lack of a prefix | ||
118 | // indicates an element common to both x and y. If possible, the output | ||
119 | // uses fmt.Stringer.String or error.Error methods to produce more humanly | ||
120 | // readable outputs. In such cases, the string is prefixed with either an | ||
121 | // 's' or 'e' character, respectively, to indicate that the method was called. | ||
95 | // | 122 | // |
96 | // Do not depend on this output being stable. | 123 | // Do not depend on this output being stable. If you need the ability to |
124 | // programmatically interpret the difference, consider using a custom Reporter. | ||
97 | func Diff(x, y interface{}, opts ...Option) string { | 125 | func Diff(x, y interface{}, opts ...Option) string { |
98 | r := new(defaultReporter) | 126 | r := new(defaultReporter) |
99 | opts = Options{Options(opts), r} | 127 | eq := Equal(x, y, Options(opts), Reporter(r)) |
100 | eq := Equal(x, y, opts...) | ||
101 | d := r.String() | 128 | d := r.String() |
102 | if (d == "") != eq { | 129 | if (d == "") != eq { |
103 | panic("inconsistent difference and equality results") | 130 | panic("inconsistent difference and equality results") |
@@ -108,9 +135,13 @@ func Diff(x, y interface{}, opts ...Option) string { | |||
108 | type state struct { | 135 | type state struct { |
109 | // These fields represent the "comparison state". | 136 | // These fields represent the "comparison state". |
110 | // Calling statelessCompare must not result in observable changes to these. | 137 | // Calling statelessCompare must not result in observable changes to these. |
111 | result diff.Result // The current result of comparison | 138 | result diff.Result // The current result of comparison |
112 | curPath Path // The current path in the value tree | 139 | curPath Path // The current path in the value tree |
113 | reporter reporter // Optional reporter used for difference formatting | 140 | reporters []reporter // Optional reporters |
141 | |||
142 | // recChecker checks for infinite cycles applying the same set of | ||
143 | // transformers upon the output of itself. | ||
144 | recChecker recChecker | ||
114 | 145 | ||
115 | // dynChecker triggers pseudo-random checks for option correctness. | 146 | // dynChecker triggers pseudo-random checks for option correctness. |
116 | // It is safe for statelessCompare to mutate this value. | 147 | // It is safe for statelessCompare to mutate this value. |
@@ -122,10 +153,9 @@ type state struct { | |||
122 | } | 153 | } |
123 | 154 | ||
124 | func newState(opts []Option) *state { | 155 | func newState(opts []Option) *state { |
125 | s := new(state) | 156 | // Always ensure a validator option exists to validate the inputs. |
126 | for _, opt := range opts { | 157 | s := &state{opts: Options{validator{}}} |
127 | s.processOption(opt) | 158 | s.processOption(Options(opts)) |
128 | } | ||
129 | return s | 159 | return s |
130 | } | 160 | } |
131 | 161 | ||
@@ -152,10 +182,7 @@ func (s *state) processOption(opt Option) { | |||
152 | s.exporters[t] = true | 182 | s.exporters[t] = true |
153 | } | 183 | } |
154 | case reporter: | 184 | case reporter: |
155 | if s.reporter != nil { | 185 | s.reporters = append(s.reporters, opt) |
156 | panic("difference reporter already registered") | ||
157 | } | ||
158 | s.reporter = opt | ||
159 | default: | 186 | default: |
160 | panic(fmt.Sprintf("unknown option %T", opt)) | 187 | panic(fmt.Sprintf("unknown option %T", opt)) |
161 | } | 188 | } |
@@ -164,153 +191,88 @@ func (s *state) processOption(opt Option) { | |||
164 | // statelessCompare compares two values and returns the result. | 191 | // statelessCompare compares two values and returns the result. |
165 | // This function is stateless in that it does not alter the current result, | 192 | // This function is stateless in that it does not alter the current result, |
166 | // or output to any registered reporters. | 193 | // or output to any registered reporters. |
167 | func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result { | 194 | func (s *state) statelessCompare(step PathStep) diff.Result { |
168 | // We do not save and restore the curPath because all of the compareX | 195 | // We do not save and restore the curPath because all of the compareX |
169 | // methods should properly push and pop from the path. | 196 | // methods should properly push and pop from the path. |
170 | // It is an implementation bug if the contents of curPath differs from | 197 | // It is an implementation bug if the contents of curPath differs from |
171 | // when calling this function to when returning from it. | 198 | // when calling this function to when returning from it. |
172 | 199 | ||
173 | oldResult, oldReporter := s.result, s.reporter | 200 | oldResult, oldReporters := s.result, s.reporters |
174 | s.result = diff.Result{} // Reset result | 201 | s.result = diff.Result{} // Reset result |
175 | s.reporter = nil // Remove reporter to avoid spurious printouts | 202 | s.reporters = nil // Remove reporters to avoid spurious printouts |
176 | s.compareAny(vx, vy) | 203 | s.compareAny(step) |
177 | res := s.result | 204 | res := s.result |
178 | s.result, s.reporter = oldResult, oldReporter | 205 | s.result, s.reporters = oldResult, oldReporters |
179 | return res | 206 | return res |
180 | } | 207 | } |
181 | 208 | ||
182 | func (s *state) compareAny(vx, vy reflect.Value) { | 209 | func (s *state) compareAny(step PathStep) { |
183 | // TODO: Support cyclic data structures. | 210 | // Update the path stack. |
184 | 211 | s.curPath.push(step) | |
185 | // Rule 0: Differing types are never equal. | 212 | defer s.curPath.pop() |
186 | if !vx.IsValid() || !vy.IsValid() { | 213 | for _, r := range s.reporters { |
187 | s.report(vx.IsValid() == vy.IsValid(), vx, vy) | 214 | r.PushStep(step) |
188 | return | 215 | defer r.PopStep() |
189 | } | ||
190 | if vx.Type() != vy.Type() { | ||
191 | s.report(false, vx, vy) // Possible for path to be empty | ||
192 | return | ||
193 | } | ||
194 | t := vx.Type() | ||
195 | if len(s.curPath) == 0 { | ||
196 | s.curPath.push(&pathStep{typ: t}) | ||
197 | defer s.curPath.pop() | ||
198 | } | 216 | } |
199 | vx, vy = s.tryExporting(vx, vy) | 217 | s.recChecker.Check(s.curPath) |
218 | |||
219 | // Obtain the current type and values. | ||
220 | t := step.Type() | ||
221 | vx, vy := step.Values() | ||
200 | 222 | ||
201 | // Rule 1: Check whether an option applies on this node in the value tree. | 223 | // Rule 1: Check whether an option applies on this node in the value tree. |
202 | if s.tryOptions(vx, vy, t) { | 224 | if s.tryOptions(t, vx, vy) { |
203 | return | 225 | return |
204 | } | 226 | } |
205 | 227 | ||
206 | // Rule 2: Check whether the type has a valid Equal method. | 228 | // Rule 2: Check whether the type has a valid Equal method. |
207 | if s.tryMethod(vx, vy, t) { | 229 | if s.tryMethod(t, vx, vy) { |
208 | return | 230 | return |
209 | } | 231 | } |
210 | 232 | ||
211 | // Rule 3: Recursively descend into each value's underlying kind. | 233 | // Rule 3: Compare based on the underlying kind. |
212 | switch t.Kind() { | 234 | switch t.Kind() { |
213 | case reflect.Bool: | 235 | case reflect.Bool: |
214 | s.report(vx.Bool() == vy.Bool(), vx, vy) | 236 | s.report(vx.Bool() == vy.Bool(), 0) |
215 | return | ||
216 | case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: | 237 | case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: |
217 | s.report(vx.Int() == vy.Int(), vx, vy) | 238 | s.report(vx.Int() == vy.Int(), 0) |
218 | return | ||
219 | case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: | 239 | case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: |
220 | s.report(vx.Uint() == vy.Uint(), vx, vy) | 240 | s.report(vx.Uint() == vy.Uint(), 0) |
221 | return | ||
222 | case reflect.Float32, reflect.Float64: | 241 | case reflect.Float32, reflect.Float64: |
223 | s.report(vx.Float() == vy.Float(), vx, vy) | 242 | s.report(vx.Float() == vy.Float(), 0) |
224 | return | ||
225 | case reflect.Complex64, reflect.Complex128: | 243 | case reflect.Complex64, reflect.Complex128: |
226 | s.report(vx.Complex() == vy.Complex(), vx, vy) | 244 | s.report(vx.Complex() == vy.Complex(), 0) |
227 | return | ||
228 | case reflect.String: | 245 | case reflect.String: |
229 | s.report(vx.String() == vy.String(), vx, vy) | 246 | s.report(vx.String() == vy.String(), 0) |
230 | return | ||
231 | case reflect.Chan, reflect.UnsafePointer: | 247 | case reflect.Chan, reflect.UnsafePointer: |
232 | s.report(vx.Pointer() == vy.Pointer(), vx, vy) | 248 | s.report(vx.Pointer() == vy.Pointer(), 0) |
233 | return | ||
234 | case reflect.Func: | 249 | case reflect.Func: |
235 | s.report(vx.IsNil() && vy.IsNil(), vx, vy) | 250 | s.report(vx.IsNil() && vy.IsNil(), 0) |
236 | return | 251 | case reflect.Struct: |
252 | s.compareStruct(t, vx, vy) | ||
253 | case reflect.Slice, reflect.Array: | ||
254 | s.compareSlice(t, vx, vy) | ||
255 | case reflect.Map: | ||
256 | s.compareMap(t, vx, vy) | ||
237 | case reflect.Ptr: | 257 | case reflect.Ptr: |
238 | if vx.IsNil() || vy.IsNil() { | 258 | s.comparePtr(t, vx, vy) |
239 | s.report(vx.IsNil() && vy.IsNil(), vx, vy) | ||
240 | return | ||
241 | } | ||
242 | s.curPath.push(&indirect{pathStep{t.Elem()}}) | ||
243 | defer s.curPath.pop() | ||
244 | s.compareAny(vx.Elem(), vy.Elem()) | ||
245 | return | ||
246 | case reflect.Interface: | 259 | case reflect.Interface: |
247 | if vx.IsNil() || vy.IsNil() { | 260 | s.compareInterface(t, vx, vy) |
248 | s.report(vx.IsNil() && vy.IsNil(), vx, vy) | ||
249 | return | ||
250 | } | ||
251 | if vx.Elem().Type() != vy.Elem().Type() { | ||
252 | s.report(false, vx.Elem(), vy.Elem()) | ||
253 | return | ||
254 | } | ||
255 | s.curPath.push(&typeAssertion{pathStep{vx.Elem().Type()}}) | ||
256 | defer s.curPath.pop() | ||
257 | s.compareAny(vx.Elem(), vy.Elem()) | ||
258 | return | ||
259 | case reflect.Slice: | ||
260 | if vx.IsNil() || vy.IsNil() { | ||
261 | s.report(vx.IsNil() && vy.IsNil(), vx, vy) | ||
262 | return | ||
263 | } | ||
264 | fallthrough | ||
265 | case reflect.Array: | ||
266 | s.compareArray(vx, vy, t) | ||
267 | return | ||
268 | case reflect.Map: | ||
269 | s.compareMap(vx, vy, t) | ||
270 | return | ||
271 | case reflect.Struct: | ||
272 | s.compareStruct(vx, vy, t) | ||
273 | return | ||
274 | default: | 261 | default: |
275 | panic(fmt.Sprintf("%v kind not handled", t.Kind())) | 262 | panic(fmt.Sprintf("%v kind not handled", t.Kind())) |
276 | } | 263 | } |
277 | } | 264 | } |
278 | 265 | ||
279 | func (s *state) tryExporting(vx, vy reflect.Value) (reflect.Value, reflect.Value) { | 266 | func (s *state) tryOptions(t reflect.Type, vx, vy reflect.Value) bool { |
280 | if sf, ok := s.curPath[len(s.curPath)-1].(*structField); ok && sf.unexported { | ||
281 | if sf.force { | ||
282 | // Use unsafe pointer arithmetic to get read-write access to an | ||
283 | // unexported field in the struct. | ||
284 | vx = unsafeRetrieveField(sf.pvx, sf.field) | ||
285 | vy = unsafeRetrieveField(sf.pvy, sf.field) | ||
286 | } else { | ||
287 | // We are not allowed to export the value, so invalidate them | ||
288 | // so that tryOptions can panic later if not explicitly ignored. | ||
289 | vx = nothing | ||
290 | vy = nothing | ||
291 | } | ||
292 | } | ||
293 | return vx, vy | ||
294 | } | ||
295 | |||
296 | func (s *state) tryOptions(vx, vy reflect.Value, t reflect.Type) bool { | ||
297 | // If there were no FilterValues, we will not detect invalid inputs, | ||
298 | // so manually check for them and append invalid if necessary. | ||
299 | // We still evaluate the options since an ignore can override invalid. | ||
300 | opts := s.opts | ||
301 | if !vx.IsValid() || !vy.IsValid() { | ||
302 | opts = Options{opts, invalid{}} | ||
303 | } | ||
304 | |||
305 | // Evaluate all filters and apply the remaining options. | 267 | // Evaluate all filters and apply the remaining options. |
306 | if opt := opts.filter(s, vx, vy, t); opt != nil { | 268 | if opt := s.opts.filter(s, t, vx, vy); opt != nil { |
307 | opt.apply(s, vx, vy) | 269 | opt.apply(s, vx, vy) |
308 | return true | 270 | return true |
309 | } | 271 | } |
310 | return false | 272 | return false |
311 | } | 273 | } |
312 | 274 | ||
313 | func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool { | 275 | func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool { |
314 | // Check if this type even has an Equal method. | 276 | // Check if this type even has an Equal method. |
315 | m, ok := t.MethodByName("Equal") | 277 | m, ok := t.MethodByName("Equal") |
316 | if !ok || !function.IsType(m.Type, function.EqualAssignable) { | 278 | if !ok || !function.IsType(m.Type, function.EqualAssignable) { |
@@ -318,11 +280,11 @@ func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool { | |||
318 | } | 280 | } |
319 | 281 | ||
320 | eq := s.callTTBFunc(m.Func, vx, vy) | 282 | eq := s.callTTBFunc(m.Func, vx, vy) |
321 | s.report(eq, vx, vy) | 283 | s.report(eq, reportByMethod) |
322 | return true | 284 | return true |
323 | } | 285 | } |
324 | 286 | ||
325 | func (s *state) callTRFunc(f, v reflect.Value) reflect.Value { | 287 | func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value { |
326 | v = sanitizeValue(v, f.Type().In(0)) | 288 | v = sanitizeValue(v, f.Type().In(0)) |
327 | if !s.dynChecker.Next() { | 289 | if !s.dynChecker.Next() { |
328 | return f.Call([]reflect.Value{v})[0] | 290 | return f.Call([]reflect.Value{v})[0] |
@@ -333,15 +295,15 @@ func (s *state) callTRFunc(f, v reflect.Value) reflect.Value { | |||
333 | // unsafe mutations to the input. | 295 | // unsafe mutations to the input. |
334 | c := make(chan reflect.Value) | 296 | c := make(chan reflect.Value) |
335 | go detectRaces(c, f, v) | 297 | go detectRaces(c, f, v) |
298 | got := <-c | ||
336 | want := f.Call([]reflect.Value{v})[0] | 299 | want := f.Call([]reflect.Value{v})[0] |
337 | if got := <-c; !s.statelessCompare(got, want).Equal() { | 300 | if step.vx, step.vy = got, want; !s.statelessCompare(step).Equal() { |
338 | // To avoid false-positives with non-reflexive equality operations, | 301 | // To avoid false-positives with non-reflexive equality operations, |
339 | // we sanity check whether a value is equal to itself. | 302 | // we sanity check whether a value is equal to itself. |
340 | if !s.statelessCompare(want, want).Equal() { | 303 | if step.vx, step.vy = want, want; !s.statelessCompare(step).Equal() { |
341 | return want | 304 | return want |
342 | } | 305 | } |
343 | fn := getFuncName(f.Pointer()) | 306 | panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f))) |
344 | panic(fmt.Sprintf("non-deterministic function detected: %s", fn)) | ||
345 | } | 307 | } |
346 | return want | 308 | return want |
347 | } | 309 | } |
@@ -359,10 +321,10 @@ func (s *state) callTTBFunc(f, x, y reflect.Value) bool { | |||
359 | // unsafe mutations to the input. | 321 | // unsafe mutations to the input. |
360 | c := make(chan reflect.Value) | 322 | c := make(chan reflect.Value) |
361 | go detectRaces(c, f, y, x) | 323 | go detectRaces(c, f, y, x) |
324 | got := <-c | ||
362 | want := f.Call([]reflect.Value{x, y})[0].Bool() | 325 | want := f.Call([]reflect.Value{x, y})[0].Bool() |
363 | if got := <-c; !got.IsValid() || got.Bool() != want { | 326 | if !got.IsValid() || got.Bool() != want { |
364 | fn := getFuncName(f.Pointer()) | 327 | panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", function.NameOf(f))) |
365 | panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", fn)) | ||
366 | } | 328 | } |
367 | return want | 329 | return want |
368 | } | 330 | } |
@@ -380,140 +342,241 @@ func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) { | |||
380 | // assuming that T is assignable to R. | 342 | // assuming that T is assignable to R. |
381 | // Otherwise, it returns the input value as is. | 343 | // Otherwise, it returns the input value as is. |
382 | func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value { | 344 | func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value { |
383 | // TODO(dsnet): Remove this hacky workaround. | 345 | // TODO(dsnet): Workaround for reflect bug (https://golang.org/issue/22143). |
384 | // See https://golang.org/issue/22143 | 346 | if !flags.AtLeastGo110 { |
385 | if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t { | 347 | if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t { |
386 | return reflect.New(t).Elem() | 348 | return reflect.New(t).Elem() |
349 | } | ||
387 | } | 350 | } |
388 | return v | 351 | return v |
389 | } | 352 | } |
390 | 353 | ||
391 | func (s *state) compareArray(vx, vy reflect.Value, t reflect.Type) { | 354 | func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) { |
392 | step := &sliceIndex{pathStep{t.Elem()}, 0, 0} | 355 | var vax, vay reflect.Value // Addressable versions of vx and vy |
393 | s.curPath.push(step) | ||
394 | 356 | ||
395 | // Compute an edit-script for slices vx and vy. | 357 | step := StructField{&structField{}} |
396 | es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result { | 358 | for i := 0; i < t.NumField(); i++ { |
397 | step.xkey, step.ykey = ix, iy | 359 | step.typ = t.Field(i).Type |
398 | return s.statelessCompare(vx.Index(ix), vy.Index(iy)) | 360 | step.vx = vx.Field(i) |
399 | }) | 361 | step.vy = vy.Field(i) |
362 | step.name = t.Field(i).Name | ||
363 | step.idx = i | ||
364 | step.unexported = !isExported(step.name) | ||
365 | if step.unexported { | ||
366 | if step.name == "_" { | ||
367 | continue | ||
368 | } | ||
369 | // Defer checking of unexported fields until later to give an | ||
370 | // Ignore a chance to ignore the field. | ||
371 | if !vax.IsValid() || !vay.IsValid() { | ||
372 | // For retrieveUnexportedField to work, the parent struct must | ||
373 | // be addressable. Create a new copy of the values if | ||
374 | // necessary to make them addressable. | ||
375 | vax = makeAddressable(vx) | ||
376 | vay = makeAddressable(vy) | ||
377 | } | ||
378 | step.mayForce = s.exporters[t] | ||
379 | step.pvx = vax | ||
380 | step.pvy = vay | ||
381 | step.field = t.Field(i) | ||
382 | } | ||
383 | s.compareAny(step) | ||
384 | } | ||
385 | } | ||
400 | 386 | ||
401 | // Report the entire slice as is if the arrays are of primitive kind, | 387 | func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) { |
402 | // and the arrays are different enough. | 388 | isSlice := t.Kind() == reflect.Slice |
403 | isPrimitive := false | 389 | if isSlice && (vx.IsNil() || vy.IsNil()) { |
404 | switch t.Elem().Kind() { | 390 | s.report(vx.IsNil() && vy.IsNil(), 0) |
405 | case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, | ||
406 | reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr, | ||
407 | reflect.Bool, reflect.Float32, reflect.Float64, reflect.Complex64, reflect.Complex128: | ||
408 | isPrimitive = true | ||
409 | } | ||
410 | if isPrimitive && es.Dist() > (vx.Len()+vy.Len())/4 { | ||
411 | s.curPath.pop() // Pop first since we are reporting the whole slice | ||
412 | s.report(false, vx, vy) | ||
413 | return | 391 | return |
414 | } | 392 | } |
415 | 393 | ||
416 | // Replay the edit-script. | 394 | // TODO: Support cyclic data structures. |
395 | |||
396 | step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}}} | ||
397 | withIndexes := func(ix, iy int) SliceIndex { | ||
398 | if ix >= 0 { | ||
399 | step.vx, step.xkey = vx.Index(ix), ix | ||
400 | } else { | ||
401 | step.vx, step.xkey = reflect.Value{}, -1 | ||
402 | } | ||
403 | if iy >= 0 { | ||
404 | step.vy, step.ykey = vy.Index(iy), iy | ||
405 | } else { | ||
406 | step.vy, step.ykey = reflect.Value{}, -1 | ||
407 | } | ||
408 | return step | ||
409 | } | ||
410 | |||
411 | // Ignore options are able to ignore missing elements in a slice. | ||
412 | // However, detecting these reliably requires an optimal differencing | ||
413 | // algorithm, for which diff.Difference is not. | ||
414 | // | ||
415 | // Instead, we first iterate through both slices to detect which elements | ||
416 | // would be ignored if standing alone. The index of non-discarded elements | ||
417 | // are stored in a separate slice, which diffing is then performed on. | ||
418 | var indexesX, indexesY []int | ||
419 | var ignoredX, ignoredY []bool | ||
420 | for ix := 0; ix < vx.Len(); ix++ { | ||
421 | ignored := s.statelessCompare(withIndexes(ix, -1)).NumDiff == 0 | ||
422 | if !ignored { | ||
423 | indexesX = append(indexesX, ix) | ||
424 | } | ||
425 | ignoredX = append(ignoredX, ignored) | ||
426 | } | ||
427 | for iy := 0; iy < vy.Len(); iy++ { | ||
428 | ignored := s.statelessCompare(withIndexes(-1, iy)).NumDiff == 0 | ||
429 | if !ignored { | ||
430 | indexesY = append(indexesY, iy) | ||
431 | } | ||
432 | ignoredY = append(ignoredY, ignored) | ||
433 | } | ||
434 | |||
435 | // Compute an edit-script for slices vx and vy (excluding ignored elements). | ||
436 | edits := diff.Difference(len(indexesX), len(indexesY), func(ix, iy int) diff.Result { | ||
437 | return s.statelessCompare(withIndexes(indexesX[ix], indexesY[iy])) | ||
438 | }) | ||
439 | |||
440 | // Replay the ignore-scripts and the edit-script. | ||
417 | var ix, iy int | 441 | var ix, iy int |
418 | for _, e := range es { | 442 | for ix < vx.Len() || iy < vy.Len() { |
443 | var e diff.EditType | ||
444 | switch { | ||
445 | case ix < len(ignoredX) && ignoredX[ix]: | ||
446 | e = diff.UniqueX | ||
447 | case iy < len(ignoredY) && ignoredY[iy]: | ||
448 | e = diff.UniqueY | ||
449 | default: | ||
450 | e, edits = edits[0], edits[1:] | ||
451 | } | ||
419 | switch e { | 452 | switch e { |
420 | case diff.UniqueX: | 453 | case diff.UniqueX: |
421 | step.xkey, step.ykey = ix, -1 | 454 | s.compareAny(withIndexes(ix, -1)) |
422 | s.report(false, vx.Index(ix), nothing) | ||
423 | ix++ | 455 | ix++ |
424 | case diff.UniqueY: | 456 | case diff.UniqueY: |
425 | step.xkey, step.ykey = -1, iy | 457 | s.compareAny(withIndexes(-1, iy)) |
426 | s.report(false, nothing, vy.Index(iy)) | ||
427 | iy++ | 458 | iy++ |
428 | default: | 459 | default: |
429 | step.xkey, step.ykey = ix, iy | 460 | s.compareAny(withIndexes(ix, iy)) |
430 | if e == diff.Identity { | ||
431 | s.report(true, vx.Index(ix), vy.Index(iy)) | ||
432 | } else { | ||
433 | s.compareAny(vx.Index(ix), vy.Index(iy)) | ||
434 | } | ||
435 | ix++ | 461 | ix++ |
436 | iy++ | 462 | iy++ |
437 | } | 463 | } |
438 | } | 464 | } |
439 | s.curPath.pop() | ||
440 | return | ||
441 | } | 465 | } |
442 | 466 | ||
443 | func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) { | 467 | func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) { |
444 | if vx.IsNil() || vy.IsNil() { | 468 | if vx.IsNil() || vy.IsNil() { |
445 | s.report(vx.IsNil() && vy.IsNil(), vx, vy) | 469 | s.report(vx.IsNil() && vy.IsNil(), 0) |
446 | return | 470 | return |
447 | } | 471 | } |
448 | 472 | ||
473 | // TODO: Support cyclic data structures. | ||
474 | |||
449 | // We combine and sort the two map keys so that we can perform the | 475 | // We combine and sort the two map keys so that we can perform the |
450 | // comparisons in a deterministic order. | 476 | // comparisons in a deterministic order. |
451 | step := &mapIndex{pathStep: pathStep{t.Elem()}} | 477 | step := MapIndex{&mapIndex{pathStep: pathStep{typ: t.Elem()}}} |
452 | s.curPath.push(step) | ||
453 | defer s.curPath.pop() | ||
454 | for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) { | 478 | for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) { |
479 | step.vx = vx.MapIndex(k) | ||
480 | step.vy = vy.MapIndex(k) | ||
455 | step.key = k | 481 | step.key = k |
456 | vvx := vx.MapIndex(k) | 482 | if !step.vx.IsValid() && !step.vy.IsValid() { |
457 | vvy := vy.MapIndex(k) | 483 | // It is possible for both vx and vy to be invalid if the |
458 | switch { | 484 | // key contained a NaN value in it. |
459 | case vvx.IsValid() && vvy.IsValid(): | 485 | // |
460 | s.compareAny(vvx, vvy) | 486 | // Even with the ability to retrieve NaN keys in Go 1.12, |
461 | case vvx.IsValid() && !vvy.IsValid(): | 487 | // there still isn't a sensible way to compare the values since |
462 | s.report(false, vvx, nothing) | 488 | // a NaN key may map to multiple unordered values. |
463 | case !vvx.IsValid() && vvy.IsValid(): | 489 | // The most reasonable way to compare NaNs would be to compare the |
464 | s.report(false, nothing, vvy) | 490 | // set of values. However, this is impossible to do efficiently |
465 | default: | 491 | // since set equality is provably an O(n^2) operation given only |
466 | // It is possible for both vvx and vvy to be invalid if the | 492 | // an Equal function. If we had a Less function or Hash function, |
467 | // key contained a NaN value in it. There is no way in | 493 | // this could be done in O(n*log(n)) or O(n), respectively. |
468 | // reflection to be able to retrieve these values. | 494 | // |
469 | // See https://golang.org/issue/11104 | 495 | // Rather than adding complex logic to deal with NaNs, make it |
470 | panic(fmt.Sprintf("%#v has map key with NaNs", s.curPath)) | 496 | // the user's responsibility to compare such obscure maps. |
497 | const help = "consider providing a Comparer to compare the map" | ||
498 | panic(fmt.Sprintf("%#v has map key with NaNs\n%s", s.curPath, help)) | ||
471 | } | 499 | } |
500 | s.compareAny(step) | ||
472 | } | 501 | } |
473 | } | 502 | } |
474 | 503 | ||
475 | func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) { | 504 | func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) { |
476 | var vax, vay reflect.Value // Addressable versions of vx and vy | 505 | if vx.IsNil() || vy.IsNil() { |
506 | s.report(vx.IsNil() && vy.IsNil(), 0) | ||
507 | return | ||
508 | } | ||
477 | 509 | ||
478 | step := &structField{} | 510 | // TODO: Support cyclic data structures. |
479 | s.curPath.push(step) | 511 | |
480 | defer s.curPath.pop() | 512 | vx, vy = vx.Elem(), vy.Elem() |
481 | for i := 0; i < t.NumField(); i++ { | 513 | s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}}) |
482 | vvx := vx.Field(i) | 514 | } |
483 | vvy := vy.Field(i) | 515 | |
484 | step.typ = t.Field(i).Type | 516 | func (s *state) compareInterface(t reflect.Type, vx, vy reflect.Value) { |
485 | step.name = t.Field(i).Name | 517 | if vx.IsNil() || vy.IsNil() { |
486 | step.idx = i | 518 | s.report(vx.IsNil() && vy.IsNil(), 0) |
487 | step.unexported = !isExported(step.name) | 519 | return |
488 | if step.unexported { | 520 | } |
489 | // Defer checking of unexported fields until later to give an | 521 | vx, vy = vx.Elem(), vy.Elem() |
490 | // Ignore a chance to ignore the field. | 522 | if vx.Type() != vy.Type() { |
491 | if !vax.IsValid() || !vay.IsValid() { | 523 | s.report(false, 0) |
492 | // For unsafeRetrieveField to work, the parent struct must | 524 | return |
493 | // be addressable. Create a new copy of the values if | 525 | } |
494 | // necessary to make them addressable. | 526 | s.compareAny(TypeAssertion{&typeAssertion{pathStep{vx.Type(), vx, vy}}}) |
495 | vax = makeAddressable(vx) | 527 | } |
496 | vay = makeAddressable(vy) | 528 | |
497 | } | 529 | func (s *state) report(eq bool, rf resultFlags) { |
498 | step.force = s.exporters[t] | 530 | if rf&reportByIgnore == 0 { |
499 | step.pvx = vax | 531 | if eq { |
500 | step.pvy = vay | 532 | s.result.NumSame++ |
501 | step.field = t.Field(i) | 533 | rf |= reportEqual |
534 | } else { | ||
535 | s.result.NumDiff++ | ||
536 | rf |= reportUnequal | ||
502 | } | 537 | } |
503 | s.compareAny(vvx, vvy) | 538 | } |
539 | for _, r := range s.reporters { | ||
540 | r.Report(Result{flags: rf}) | ||
504 | } | 541 | } |
505 | } | 542 | } |
506 | 543 | ||
507 | // report records the result of a single comparison. | 544 | // recChecker tracks the state needed to periodically perform checks that |
508 | // It also calls Report if any reporter is registered. | 545 | // user provided transformers are not stuck in an infinitely recursive cycle. |
509 | func (s *state) report(eq bool, vx, vy reflect.Value) { | 546 | type recChecker struct{ next int } |
510 | if eq { | 547 | |
511 | s.result.NSame++ | 548 | // Check scans the Path for any recursive transformers and panics when any |
512 | } else { | 549 | // recursive transformers are detected. Note that the presence of a |
513 | s.result.NDiff++ | 550 | // recursive Transformer does not necessarily imply an infinite cycle. |
551 | // As such, this check only activates after some minimal number of path steps. | ||
552 | func (rc *recChecker) Check(p Path) { | ||
553 | const minLen = 1 << 16 | ||
554 | if rc.next == 0 { | ||
555 | rc.next = minLen | ||
556 | } | ||
557 | if len(p) < rc.next { | ||
558 | return | ||
559 | } | ||
560 | rc.next <<= 1 | ||
561 | |||
562 | // Check whether the same transformer has appeared at least twice. | ||
563 | var ss []string | ||
564 | m := map[Option]int{} | ||
565 | for _, ps := range p { | ||
566 | if t, ok := ps.(Transform); ok { | ||
567 | t := t.Option() | ||
568 | if m[t] == 1 { // Transformer was used exactly once before | ||
569 | tf := t.(*transformer).fnc.Type() | ||
570 | ss = append(ss, fmt.Sprintf("%v: %v => %v", t, tf.In(0), tf.Out(0))) | ||
571 | } | ||
572 | m[t]++ | ||
573 | } | ||
514 | } | 574 | } |
515 | if s.reporter != nil { | 575 | if len(ss) > 0 { |
516 | s.reporter.Report(vx, vy, eq, s.curPath) | 576 | const warning = "recursive set of Transformers detected" |
577 | const help = "consider using cmpopts.AcyclicTransformer" | ||
578 | set := strings.Join(ss, "\n\t") | ||
579 | panic(fmt.Sprintf("%s:\n\t%s\n%s", warning, set, help)) | ||
517 | } | 580 | } |
518 | } | 581 | } |
519 | 582 | ||