1// Copyright 2019, 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)
11
12// numContextRecords is the number of surrounding equal records to print.
13const numContextRecords = 2
14
15type diffMode byte
16
17const (
18 diffUnknown diffMode = 0
19 diffIdentical diffMode = ' '
20 diffRemoved diffMode = '-'
21 diffInserted diffMode = '+'
22)
23
24type typeMode int
25
26const (
27 // emitType always prints the type.
28 emitType typeMode = iota
29 // elideType never prints the type.
30 elideType
31 // autoType prints the type only for composite kinds
32 // (i.e., structs, slices, arrays, and maps).
33 autoType
34)
35
36type formatOptions struct {
37 // DiffMode controls the output mode of FormatDiff.
38 //
39 // If diffUnknown, then produce a diff of the x and y values.
40 // If diffIdentical, then emit values as if they were equal.
41 // If diffRemoved, then only emit x values (ignoring y values).
42 // If diffInserted, then only emit y values (ignoring x values).
43 DiffMode diffMode
44
45 // TypeMode controls whether to print the type for the current node.
46 //
47 // As a general rule of thumb, we always print the type of the next node
48 // after an interface, and always elide the type of the next node after
49 // a slice or map node.
50 TypeMode typeMode
51
52 // formatValueOptions are options specific to printing reflect.Values.
53 formatValueOptions
54}
55
56func (opts formatOptions) WithDiffMode(d diffMode) formatOptions {
57 opts.DiffMode = d
58 return opts
59}
60func (opts formatOptions) WithTypeMode(t typeMode) formatOptions {
61 opts.TypeMode = t
62 return opts
63}
64func (opts formatOptions) WithVerbosity(level int) formatOptions {
65 opts.VerbosityLevel = level
66 opts.LimitVerbosity = true
67 return opts
68}
69func (opts formatOptions) verbosity() uint {
70 switch {
71 case opts.VerbosityLevel < 0:
72 return 0
73 case opts.VerbosityLevel > 16:
74 return 16 // some reasonable maximum to avoid shift overflow
75 default:
76 return uint(opts.VerbosityLevel)
77 }
78}
79
80const maxVerbosityPreset = 6
81
82// verbosityPreset modifies the verbosity settings given an index
83// between 0 and maxVerbosityPreset, inclusive.
84func verbosityPreset(opts formatOptions, i int) formatOptions {
85 opts.VerbosityLevel = int(opts.verbosity()) + 2*i
86 if i > 0 {
87 opts.AvoidStringer = true
88 }
89 if i >= maxVerbosityPreset {
90 opts.PrintAddresses = true
91 opts.QualifiedNames = true
92 }
93 return opts
94}
95
96// FormatDiff converts a valueNode tree into a textNode tree, where the later
97// is a textual representation of the differences detected in the former.
98func (opts formatOptions) FormatDiff(v *valueNode, ptrs *pointerReferences) (out textNode) {
99 if opts.DiffMode == diffIdentical {
100 opts = opts.WithVerbosity(1)
101 } else if opts.verbosity() < 3 {
102 opts = opts.WithVerbosity(3)
103 }
104
105 // Check whether we have specialized formatting for this node.
106 // This is not necessary, but helpful for producing more readable outputs.
107 if opts.CanFormatDiffSlice(v) {
108 return opts.FormatDiffSlice(v)
109 }
110
111 var parentKind reflect.Kind
112 if v.parent != nil && v.parent.TransformerName == "" {
113 parentKind = v.parent.Type.Kind()
114 }
115
116 // For leaf nodes, format the value based on the reflect.Values alone.
117 // As a special case, treat equal []byte as a leaf nodes.
118 isBytes := v.Type.Kind() == reflect.Slice && v.Type.Elem() == byteType
119 isEqualBytes := isBytes && v.NumDiff+v.NumIgnored+v.NumTransformed == 0
120 if v.MaxDepth == 0 || isEqualBytes {
121 switch opts.DiffMode {
122 case diffUnknown, diffIdentical:
123 // Format Equal.
124 if v.NumDiff == 0 {
125 outx := opts.FormatValue(v.ValueX, parentKind, ptrs)
126 outy := opts.FormatValue(v.ValueY, parentKind, ptrs)
127 if v.NumIgnored > 0 && v.NumSame == 0 {
128 return textEllipsis
129 } else if outx.Len() < outy.Len() {
130 return outx
131 } else {
132 return outy
133 }
134 }
135
136 // Format unequal.
137 assert(opts.DiffMode == diffUnknown)
138 var list textList
139 outx := opts.WithTypeMode(elideType).FormatValue(v.ValueX, parentKind, ptrs)
140 outy := opts.WithTypeMode(elideType).FormatValue(v.ValueY, parentKind, ptrs)
141 for i := 0; i <= maxVerbosityPreset && outx != nil && outy != nil && outx.Equal(outy); i++ {
142 opts2 := verbosityPreset(opts, i).WithTypeMode(elideType)
143 outx = opts2.FormatValue(v.ValueX, parentKind, ptrs)
144 outy = opts2.FormatValue(v.ValueY, parentKind, ptrs)
145 }
146 if outx != nil {
147 list = append(list, textRecord{Diff: '-', Value: outx})
148 }
149 if outy != nil {
150 list = append(list, textRecord{Diff: '+', Value: outy})
151 }
152 return opts.WithTypeMode(emitType).FormatType(v.Type, list)
153 case diffRemoved:
154 return opts.FormatValue(v.ValueX, parentKind, ptrs)
155 case diffInserted:
156 return opts.FormatValue(v.ValueY, parentKind, ptrs)
157 default:
158 panic("invalid diff mode")
159 }
160 }
161
162 // Register slice element to support cycle detection.
163 if parentKind == reflect.Slice {
164 ptrRefs := ptrs.PushPair(v.ValueX, v.ValueY, opts.DiffMode, true)
165 defer ptrs.Pop()
166 defer func() { out = wrapTrunkReferences(ptrRefs, out) }()
167 }
168
169 // Descend into the child value node.
170 if v.TransformerName != "" {
171 out := opts.WithTypeMode(emitType).FormatDiff(v.Value, ptrs)
172 out = &textWrap{Prefix: "Inverse(" + v.TransformerName + ", ", Value: out, Suffix: ")"}
173 return opts.FormatType(v.Type, out)
174 } else {
175 switch k := v.Type.Kind(); k {
176 case reflect.Struct, reflect.Array, reflect.Slice:
177 out = opts.formatDiffList(v.Records, k, ptrs)
178 out = opts.FormatType(v.Type, out)
179 case reflect.Map:
180 // Register map to support cycle detection.
181 ptrRefs := ptrs.PushPair(v.ValueX, v.ValueY, opts.DiffMode, false)
182 defer ptrs.Pop()
183
184 out = opts.formatDiffList(v.Records, k, ptrs)
185 out = wrapTrunkReferences(ptrRefs, out)
186 out = opts.FormatType(v.Type, out)
187 case reflect.Ptr:
188 // Register pointer to support cycle detection.
189 ptrRefs := ptrs.PushPair(v.ValueX, v.ValueY, opts.DiffMode, false)
190 defer ptrs.Pop()
191
192 out = opts.FormatDiff(v.Value, ptrs)
193 out = wrapTrunkReferences(ptrRefs, out)
194 out = &textWrap{Prefix: "&", Value: out}
195 case reflect.Interface:
196 out = opts.WithTypeMode(emitType).FormatDiff(v.Value, ptrs)
197 default:
198 panic(fmt.Sprintf("%v cannot have children", k))
199 }
200 return out
201 }
202}
203
204func (opts formatOptions) formatDiffList(recs []reportRecord, k reflect.Kind, ptrs *pointerReferences) textNode {
205 // Derive record name based on the data structure kind.
206 var name string
207 var formatKey func(reflect.Value) string
208 switch k {
209 case reflect.Struct:
210 name = "field"
211 opts = opts.WithTypeMode(autoType)
212 formatKey = func(v reflect.Value) string { return v.String() }
213 case reflect.Slice, reflect.Array:
214 name = "element"
215 opts = opts.WithTypeMode(elideType)
216 formatKey = func(reflect.Value) string { return "" }
217 case reflect.Map:
218 name = "entry"
219 opts = opts.WithTypeMode(elideType)
220 formatKey = func(v reflect.Value) string { return formatMapKey(v, false, ptrs) }
221 }
222
223 maxLen := -1
224 if opts.LimitVerbosity {
225 if opts.DiffMode == diffIdentical {
226 maxLen = ((1 << opts.verbosity()) >> 1) << 2 // 0, 4, 8, 16, 32, etc...
227 } else {
228 maxLen = (1 << opts.verbosity()) << 1 // 2, 4, 8, 16, 32, 64, etc...
229 }
230 opts.VerbosityLevel--
231 }
232
233 // Handle unification.
234 switch opts.DiffMode {
235 case diffIdentical, diffRemoved, diffInserted:
236 var list textList
237 var deferredEllipsis bool // Add final "..." to indicate records were dropped
238 for _, r := range recs {
239 if len(list) == maxLen {
240 deferredEllipsis = true
241 break
242 }
243
244 // Elide struct fields that are zero value.
245 if k == reflect.Struct {
246 var isZero bool
247 switch opts.DiffMode {
248 case diffIdentical:
249 isZero = r.Value.ValueX.IsZero() || r.Value.ValueY.IsZero()
250 case diffRemoved:
251 isZero = r.Value.ValueX.IsZero()
252 case diffInserted:
253 isZero = r.Value.ValueY.IsZero()
254 }
255 if isZero {
256 continue
257 }
258 }
259 // Elide ignored nodes.
260 if r.Value.NumIgnored > 0 && r.Value.NumSame+r.Value.NumDiff == 0 {
261 deferredEllipsis = !(k == reflect.Slice || k == reflect.Array)
262 if !deferredEllipsis {
263 list.AppendEllipsis(diffStats{})
264 }
265 continue
266 }
267 if out := opts.FormatDiff(r.Value, ptrs); out != nil {
268 list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
269 }
270 }
271 if deferredEllipsis {
272 list.AppendEllipsis(diffStats{})
273 }
274 return &textWrap{Prefix: "{", Value: list, Suffix: "}"}
275 case diffUnknown:
276 default:
277 panic("invalid diff mode")
278 }
279
280 // Handle differencing.
281 var numDiffs int
282 var list textList
283 var keys []reflect.Value // invariant: len(list) == len(keys)
284 groups := coalesceAdjacentRecords(name, recs)
285 maxGroup := diffStats{Name: name}
286 for i, ds := range groups {
287 if maxLen >= 0 && numDiffs >= maxLen {
288 maxGroup = maxGroup.Append(ds)
289 continue
290 }
291
292 // Handle equal records.
293 if ds.NumDiff() == 0 {
294 // Compute the number of leading and trailing records to print.
295 var numLo, numHi int
296 numEqual := ds.NumIgnored + ds.NumIdentical
297 for numLo < numContextRecords && numLo+numHi < numEqual && i != 0 {
298 if r := recs[numLo].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {
299 break
300 }
301 numLo++
302 }
303 for numHi < numContextRecords && numLo+numHi < numEqual && i != len(groups)-1 {
304 if r := recs[numEqual-numHi-1].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {
305 break
306 }
307 numHi++
308 }
309 if numEqual-(numLo+numHi) == 1 && ds.NumIgnored == 0 {
310 numHi++ // Avoid pointless coalescing of a single equal record
311 }
312
313 // Format the equal values.
314 for _, r := range recs[:numLo] {
315 out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value, ptrs)
316 list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
317 keys = append(keys, r.Key)
318 }
319 if numEqual > numLo+numHi {
320 ds.NumIdentical -= numLo + numHi
321 list.AppendEllipsis(ds)
322 for len(keys) < len(list) {
323 keys = append(keys, reflect.Value{})
324 }
325 }
326 for _, r := range recs[numEqual-numHi : numEqual] {
327 out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value, ptrs)
328 list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
329 keys = append(keys, r.Key)
330 }
331 recs = recs[numEqual:]
332 continue
333 }
334
335 // Handle unequal records.
336 for _, r := range recs[:ds.NumDiff()] {
337 switch {
338 case opts.CanFormatDiffSlice(r.Value):
339 out := opts.FormatDiffSlice(r.Value)
340 list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
341 keys = append(keys, r.Key)
342 case r.Value.NumChildren == r.Value.MaxDepth:
343 outx := opts.WithDiffMode(diffRemoved).FormatDiff(r.Value, ptrs)
344 outy := opts.WithDiffMode(diffInserted).FormatDiff(r.Value, ptrs)
345 for i := 0; i <= maxVerbosityPreset && outx != nil && outy != nil && outx.Equal(outy); i++ {
346 opts2 := verbosityPreset(opts, i)
347 outx = opts2.WithDiffMode(diffRemoved).FormatDiff(r.Value, ptrs)
348 outy = opts2.WithDiffMode(diffInserted).FormatDiff(r.Value, ptrs)
349 }
350 if outx != nil {
351 list = append(list, textRecord{Diff: diffRemoved, Key: formatKey(r.Key), Value: outx})
352 keys = append(keys, r.Key)
353 }
354 if outy != nil {
355 list = append(list, textRecord{Diff: diffInserted, Key: formatKey(r.Key), Value: outy})
356 keys = append(keys, r.Key)
357 }
358 default:
359 out := opts.FormatDiff(r.Value, ptrs)
360 list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
361 keys = append(keys, r.Key)
362 }
363 }
364 recs = recs[ds.NumDiff():]
365 numDiffs += ds.NumDiff()
366 }
367 if maxGroup.IsZero() {
368 assert(len(recs) == 0)
369 } else {
370 list.AppendEllipsis(maxGroup)
371 for len(keys) < len(list) {
372 keys = append(keys, reflect.Value{})
373 }
374 }
375 assert(len(list) == len(keys))
376
377 // For maps, the default formatting logic uses fmt.Stringer which may
378 // produce ambiguous output. Avoid calling String to disambiguate.
379 if k == reflect.Map {
380 var ambiguous bool
381 seenKeys := map[string]reflect.Value{}
382 for i, currKey := range keys {
383 if currKey.IsValid() {
384 strKey := list[i].Key
385 prevKey, seen := seenKeys[strKey]
386 if seen && prevKey.CanInterface() && currKey.CanInterface() {
387 ambiguous = prevKey.Interface() != currKey.Interface()
388 if ambiguous {
389 break
390 }
391 }
392 seenKeys[strKey] = currKey
393 }
394 }
395 if ambiguous {
396 for i, k := range keys {
397 if k.IsValid() {
398 list[i].Key = formatMapKey(k, true, ptrs)
399 }
400 }
401 }
402 }
403
404 return &textWrap{Prefix: "{", Value: list, Suffix: "}"}
405}
406
407// coalesceAdjacentRecords coalesces the list of records into groups of
408// adjacent equal, or unequal counts.
409func coalesceAdjacentRecords(name string, recs []reportRecord) (groups []diffStats) {
410 var prevCase int // Arbitrary index into which case last occurred
411 lastStats := func(i int) *diffStats {
412 if prevCase != i {
413 groups = append(groups, diffStats{Name: name})
414 prevCase = i
415 }
416 return &groups[len(groups)-1]
417 }
418 for _, r := range recs {
419 switch rv := r.Value; {
420 case rv.NumIgnored > 0 && rv.NumSame+rv.NumDiff == 0:
421 lastStats(1).NumIgnored++
422 case rv.NumDiff == 0:
423 lastStats(1).NumIdentical++
424 case rv.NumDiff > 0 && !rv.ValueY.IsValid():
425 lastStats(2).NumRemoved++
426 case rv.NumDiff > 0 && !rv.ValueX.IsValid():
427 lastStats(2).NumInserted++
428 default:
429 lastStats(2).NumModified++
430 }
431 }
432 return groups
433}