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.md file.
4
5package cmp
6
7import (
8	"fmt"
9	"reflect"
10
11	"github.com/google/go-cmp/cmp/internal/value"
12)
13
14// TODO: Enforce limits?
15//	* Enforce maximum number of records to print per node?
16//	* Enforce maximum size in bytes allowed?
17//	* As a heuristic, use less verbosity for equal nodes than unequal nodes.
18// TODO: Enforce unique outputs?
19//	* Avoid Stringer methods if it results in same output?
20//	* Print pointer address if outputs still equal?
21
22// numContextRecords is the number of surrounding equal records to print.
23const numContextRecords = 2
24
25type diffMode byte
26
27const (
28	diffUnknown   diffMode = 0
29	diffIdentical diffMode = ' '
30	diffRemoved   diffMode = '-'
31	diffInserted  diffMode = '+'
32)
33
34type typeMode int
35
36const (
37	// emitType always prints the type.
38	emitType typeMode = iota
39	// elideType never prints the type.
40	elideType
41	// autoType prints the type only for composite kinds
42	// (i.e., structs, slices, arrays, and maps).
43	autoType
44)
45
46type formatOptions struct {
47	// DiffMode controls the output mode of FormatDiff.
48	//
49	// If diffUnknown,   then produce a diff of the x and y values.
50	// If diffIdentical, then emit values as if they were equal.
51	// If diffRemoved,   then only emit x values (ignoring y values).
52	// If diffInserted,  then only emit y values (ignoring x values).
53	DiffMode diffMode
54
55	// TypeMode controls whether to print the type for the current node.
56	//
57	// As a general rule of thumb, we always print the type of the next node
58	// after an interface, and always elide the type of the next node after
59	// a slice or map node.
60	TypeMode typeMode
61
62	// formatValueOptions are options specific to printing reflect.Values.
63	formatValueOptions
64}
65
66func (opts formatOptions) WithDiffMode(d diffMode) formatOptions {
67	opts.DiffMode = d
68	return opts
69}
70func (opts formatOptions) WithTypeMode(t typeMode) formatOptions {
71	opts.TypeMode = t
72	return opts
73}
74
75// FormatDiff converts a valueNode tree into a textNode tree, where the later
76// is a textual representation of the differences detected in the former.
77func (opts formatOptions) FormatDiff(v *valueNode) textNode {
78	// Check whether we have specialized formatting for this node.
79	// This is not necessary, but helpful for producing more readable outputs.
80	if opts.CanFormatDiffSlice(v) {
81		return opts.FormatDiffSlice(v)
82	}
83
84	// For leaf nodes, format the value based on the reflect.Values alone.
85	if v.MaxDepth == 0 {
86		switch opts.DiffMode {
87		case diffUnknown, diffIdentical:
88			// Format Equal.
89			if v.NumDiff == 0 {
90				outx := opts.FormatValue(v.ValueX, visitedPointers{})
91				outy := opts.FormatValue(v.ValueY, visitedPointers{})
92				if v.NumIgnored > 0 && v.NumSame == 0 {
93					return textEllipsis
94				} else if outx.Len() < outy.Len() {
95					return outx
96				} else {
97					return outy
98				}
99			}
100
101			// Format unequal.
102			assert(opts.DiffMode == diffUnknown)
103			var list textList
104			outx := opts.WithTypeMode(elideType).FormatValue(v.ValueX, visitedPointers{})
105			outy := opts.WithTypeMode(elideType).FormatValue(v.ValueY, visitedPointers{})
106			if outx != nil {
107				list = append(list, textRecord{Diff: '-', Value: outx})
108			}
109			if outy != nil {
110				list = append(list, textRecord{Diff: '+', Value: outy})
111			}
112			return opts.WithTypeMode(emitType).FormatType(v.Type, list)
113		case diffRemoved:
114			return opts.FormatValue(v.ValueX, visitedPointers{})
115		case diffInserted:
116			return opts.FormatValue(v.ValueY, visitedPointers{})
117		default:
118			panic("invalid diff mode")
119		}
120	}
121
122	// Descend into the child value node.
123	if v.TransformerName != "" {
124		out := opts.WithTypeMode(emitType).FormatDiff(v.Value)
125		out = textWrap{"Inverse(" + v.TransformerName + ", ", out, ")"}
126		return opts.FormatType(v.Type, out)
127	} else {
128		switch k := v.Type.Kind(); k {
129		case reflect.Struct, reflect.Array, reflect.Slice, reflect.Map:
130			return opts.FormatType(v.Type, opts.formatDiffList(v.Records, k))
131		case reflect.Ptr:
132			return textWrap{"&", opts.FormatDiff(v.Value), ""}
133		case reflect.Interface:
134			return opts.WithTypeMode(emitType).FormatDiff(v.Value)
135		default:
136			panic(fmt.Sprintf("%v cannot have children", k))
137		}
138	}
139}
140
141func (opts formatOptions) formatDiffList(recs []reportRecord, k reflect.Kind) textNode {
142	// Derive record name based on the data structure kind.
143	var name string
144	var formatKey func(reflect.Value) string
145	switch k {
146	case reflect.Struct:
147		name = "field"
148		opts = opts.WithTypeMode(autoType)
149		formatKey = func(v reflect.Value) string { return v.String() }
150	case reflect.Slice, reflect.Array:
151		name = "element"
152		opts = opts.WithTypeMode(elideType)
153		formatKey = func(reflect.Value) string { return "" }
154	case reflect.Map:
155		name = "entry"
156		opts = opts.WithTypeMode(elideType)
157		formatKey = formatMapKey
158	}
159
160	// Handle unification.
161	switch opts.DiffMode {
162	case diffIdentical, diffRemoved, diffInserted:
163		var list textList
164		var deferredEllipsis bool // Add final "..." to indicate records were dropped
165		for _, r := range recs {
166			// Elide struct fields that are zero value.
167			if k == reflect.Struct {
168				var isZero bool
169				switch opts.DiffMode {
170				case diffIdentical:
171					isZero = value.IsZero(r.Value.ValueX) || value.IsZero(r.Value.ValueX)
172				case diffRemoved:
173					isZero = value.IsZero(r.Value.ValueX)
174				case diffInserted:
175					isZero = value.IsZero(r.Value.ValueY)
176				}
177				if isZero {
178					continue
179				}
180			}
181			// Elide ignored nodes.
182			if r.Value.NumIgnored > 0 && r.Value.NumSame+r.Value.NumDiff == 0 {
183				deferredEllipsis = !(k == reflect.Slice || k == reflect.Array)
184				if !deferredEllipsis {
185					list.AppendEllipsis(diffStats{})
186				}
187				continue
188			}
189			if out := opts.FormatDiff(r.Value); out != nil {
190				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
191			}
192		}
193		if deferredEllipsis {
194			list.AppendEllipsis(diffStats{})
195		}
196		return textWrap{"{", list, "}"}
197	case diffUnknown:
198	default:
199		panic("invalid diff mode")
200	}
201
202	// Handle differencing.
203	var list textList
204	groups := coalesceAdjacentRecords(name, recs)
205	for i, ds := range groups {
206		// Handle equal records.
207		if ds.NumDiff() == 0 {
208			// Compute the number of leading and trailing records to print.
209			var numLo, numHi int
210			numEqual := ds.NumIgnored + ds.NumIdentical
211			for numLo < numContextRecords && numLo+numHi < numEqual && i != 0 {
212				if r := recs[numLo].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {
213					break
214				}
215				numLo++
216			}
217			for numHi < numContextRecords && numLo+numHi < numEqual && i != len(groups)-1 {
218				if r := recs[numEqual-numHi-1].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {
219					break
220				}
221				numHi++
222			}
223			if numEqual-(numLo+numHi) == 1 && ds.NumIgnored == 0 {
224				numHi++ // Avoid pointless coalescing of a single equal record
225			}
226
227			// Format the equal values.
228			for _, r := range recs[:numLo] {
229				out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value)
230				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
231			}
232			if numEqual > numLo+numHi {
233				ds.NumIdentical -= numLo + numHi
234				list.AppendEllipsis(ds)
235			}
236			for _, r := range recs[numEqual-numHi : numEqual] {
237				out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value)
238				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
239			}
240			recs = recs[numEqual:]
241			continue
242		}
243
244		// Handle unequal records.
245		for _, r := range recs[:ds.NumDiff()] {
246			switch {
247			case opts.CanFormatDiffSlice(r.Value):
248				out := opts.FormatDiffSlice(r.Value)
249				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
250			case r.Value.NumChildren == r.Value.MaxDepth:
251				outx := opts.WithDiffMode(diffRemoved).FormatDiff(r.Value)
252				outy := opts.WithDiffMode(diffInserted).FormatDiff(r.Value)
253				if outx != nil {
254					list = append(list, textRecord{Diff: diffRemoved, Key: formatKey(r.Key), Value: outx})
255				}
256				if outy != nil {
257					list = append(list, textRecord{Diff: diffInserted, Key: formatKey(r.Key), Value: outy})
258				}
259			default:
260				out := opts.FormatDiff(r.Value)
261				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})
262			}
263		}
264		recs = recs[ds.NumDiff():]
265	}
266	assert(len(recs) == 0)
267	return textWrap{"{", list, "}"}
268}
269
270// coalesceAdjacentRecords coalesces the list of records into groups of
271// adjacent equal, or unequal counts.
272func coalesceAdjacentRecords(name string, recs []reportRecord) (groups []diffStats) {
273	var prevCase int // Arbitrary index into which case last occurred
274	lastStats := func(i int) *diffStats {
275		if prevCase != i {
276			groups = append(groups, diffStats{Name: name})
277			prevCase = i
278		}
279		return &groups[len(groups)-1]
280	}
281	for _, r := range recs {
282		switch rv := r.Value; {
283		case rv.NumIgnored > 0 && rv.NumSame+rv.NumDiff == 0:
284			lastStats(1).NumIgnored++
285		case rv.NumDiff == 0:
286			lastStats(1).NumIdentical++
287		case rv.NumDiff > 0 && !rv.ValueY.IsValid():
288			lastStats(2).NumRemoved++
289		case rv.NumDiff > 0 && !rv.ValueX.IsValid():
290			lastStats(2).NumInserted++
291		default:
292			lastStats(2).NumModified++
293		}
294	}
295	return groups
296}
297