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

5
package cmp
6

7
import (
8
	"fmt"
9
	"reflect"
10
)
11

12
// numContextRecords is the number of surrounding equal records to print.
13
const numContextRecords = 2
14

15
type diffMode byte
16

17
const (
18
	diffUnknown   diffMode = 0
19
	diffIdentical diffMode = ' '
20
	diffRemoved   diffMode = '-'
21
	diffInserted  diffMode = '+'
22
)
23

24
type typeMode int
25

26
const (
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

36
type 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

56
func (opts formatOptions) WithDiffMode(d diffMode) formatOptions {
57
	opts.DiffMode = d
58
	return opts
59
}
60
func (opts formatOptions) WithTypeMode(t typeMode) formatOptions {
61
	opts.TypeMode = t
62
	return opts
63
}
64
func (opts formatOptions) WithVerbosity(level int) formatOptions {
65
	opts.VerbosityLevel = level
66
	opts.LimitVerbosity = true
67
	return opts
68
}
69
func (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

80
const maxVerbosityPreset = 6
81

82
// verbosityPreset modifies the verbosity settings given an index
83
// between 0 and maxVerbosityPreset, inclusive.
84
func 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.
98
func (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

204
func (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.
409
func 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
}
434

435