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
	"bytes"
9
	"fmt"
10
	"math/rand"
11
	"strings"
12
	"time"
13
	"unicode/utf8"
14

15
	"github.com/google/go-cmp/cmp/internal/flags"
16
)
17

18
var randBool = rand.New(rand.NewSource(time.Now().Unix())).Intn(2) == 0
19

20
const maxColumnLength = 80
21

22
type indentMode int
23

24
func (n indentMode) appendIndent(b []byte, d diffMode) []byte {
25
	// The output of Diff is documented as being unstable to provide future
26
	// flexibility in changing the output for more humanly readable reports.
27
	// This logic intentionally introduces instability to the exact output
28
	// so that users can detect accidental reliance on stability early on,
29
	// rather than much later when an actual change to the format occurs.
30
	if flags.Deterministic || randBool {
31
		// Use regular spaces (U+0020).
32
		switch d {
33
		case diffUnknown, diffIdentical:
34
			b = append(b, "  "...)
35
		case diffRemoved:
36
			b = append(b, "- "...)
37
		case diffInserted:
38
			b = append(b, "+ "...)
39
		}
40
	} else {
41
		// Use non-breaking spaces (U+00a0).
42
		switch d {
43
		case diffUnknown, diffIdentical:
44
			b = append(b, "  "...)
45
		case diffRemoved:
46
			b = append(b, "- "...)
47
		case diffInserted:
48
			b = append(b, "+ "...)
49
		}
50
	}
51
	return repeatCount(n).appendChar(b, '\t')
52
}
53

54
type repeatCount int
55

56
func (n repeatCount) appendChar(b []byte, c byte) []byte {
57
	for ; n > 0; n-- {
58
		b = append(b, c)
59
	}
60
	return b
61
}
62

63
// textNode is a simplified tree-based representation of structured text.
64
// Possible node types are textWrap, textList, or textLine.
65
type textNode interface {
66
	// Len reports the length in bytes of a single-line version of the tree.
67
	// Nested textRecord.Diff and textRecord.Comment fields are ignored.
68
	Len() int
69
	// Equal reports whether the two trees are structurally identical.
70
	// Nested textRecord.Diff and textRecord.Comment fields are compared.
71
	Equal(textNode) bool
72
	// String returns the string representation of the text tree.
73
	// It is not guaranteed that len(x.String()) == x.Len(),
74
	// nor that x.String() == y.String() implies that x.Equal(y).
75
	String() string
76

77
	// formatCompactTo formats the contents of the tree as a single-line string
78
	// to the provided buffer. Any nested textRecord.Diff and textRecord.Comment
79
	// fields are ignored.
80
	//
81
	// However, not all nodes in the tree should be collapsed as a single-line.
82
	// If a node can be collapsed as a single-line, it is replaced by a textLine
83
	// node. Since the top-level node cannot replace itself, this also returns
84
	// the current node itself.
85
	//
86
	// This does not mutate the receiver.
87
	formatCompactTo([]byte, diffMode) ([]byte, textNode)
88
	// formatExpandedTo formats the contents of the tree as a multi-line string
89
	// to the provided buffer. In order for column alignment to operate well,
90
	// formatCompactTo must be called before calling formatExpandedTo.
91
	formatExpandedTo([]byte, diffMode, indentMode) []byte
92
}
93

94
// textWrap is a wrapper that concatenates a prefix and/or a suffix
95
// to the underlying node.
96
type textWrap struct {
97
	Prefix   string      // e.g., "bytes.Buffer{"
98
	Value    textNode    // textWrap | textList | textLine
99
	Suffix   string      // e.g., "}"
100
	Metadata interface{} // arbitrary metadata; has no effect on formatting
101
}
102

103
func (s *textWrap) Len() int {
104
	return len(s.Prefix) + s.Value.Len() + len(s.Suffix)
105
}
106
func (s1 *textWrap) Equal(s2 textNode) bool {
107
	if s2, ok := s2.(*textWrap); ok {
108
		return s1.Prefix == s2.Prefix && s1.Value.Equal(s2.Value) && s1.Suffix == s2.Suffix
109
	}
110
	return false
111
}
112
func (s *textWrap) String() string {
113
	var d diffMode
114
	var n indentMode
115
	_, s2 := s.formatCompactTo(nil, d)
116
	b := n.appendIndent(nil, d)      // Leading indent
117
	b = s2.formatExpandedTo(b, d, n) // Main body
118
	b = append(b, '\n')              // Trailing newline
119
	return string(b)
120
}
121
func (s *textWrap) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) {
122
	n0 := len(b) // Original buffer length
123
	b = append(b, s.Prefix...)
124
	b, s.Value = s.Value.formatCompactTo(b, d)
125
	b = append(b, s.Suffix...)
126
	if _, ok := s.Value.(textLine); ok {
127
		return b, textLine(b[n0:])
128
	}
129
	return b, s
130
}
131
func (s *textWrap) formatExpandedTo(b []byte, d diffMode, n indentMode) []byte {
132
	b = append(b, s.Prefix...)
133
	b = s.Value.formatExpandedTo(b, d, n)
134
	b = append(b, s.Suffix...)
135
	return b
136
}
137

138
// textList is a comma-separated list of textWrap or textLine nodes.
139
// The list may be formatted as multi-lines or single-line at the discretion
140
// of the textList.formatCompactTo method.
141
type textList []textRecord
142
type textRecord struct {
143
	Diff       diffMode     // e.g., 0 or '-' or '+'
144
	Key        string       // e.g., "MyField"
145
	Value      textNode     // textWrap | textLine
146
	ElideComma bool         // avoid trailing comma
147
	Comment    fmt.Stringer // e.g., "6 identical fields"
148
}
149

150
// AppendEllipsis appends a new ellipsis node to the list if none already
151
// exists at the end. If cs is non-zero it coalesces the statistics with the
152
// previous diffStats.
153
func (s *textList) AppendEllipsis(ds diffStats) {
154
	hasStats := !ds.IsZero()
155
	if len(*s) == 0 || !(*s)[len(*s)-1].Value.Equal(textEllipsis) {
156
		if hasStats {
157
			*s = append(*s, textRecord{Value: textEllipsis, ElideComma: true, Comment: ds})
158
		} else {
159
			*s = append(*s, textRecord{Value: textEllipsis, ElideComma: true})
160
		}
161
		return
162
	}
163
	if hasStats {
164
		(*s)[len(*s)-1].Comment = (*s)[len(*s)-1].Comment.(diffStats).Append(ds)
165
	}
166
}
167

168
func (s textList) Len() (n int) {
169
	for i, r := range s {
170
		n += len(r.Key)
171
		if r.Key != "" {
172
			n += len(": ")
173
		}
174
		n += r.Value.Len()
175
		if i < len(s)-1 {
176
			n += len(", ")
177
		}
178
	}
179
	return n
180
}
181

182
func (s1 textList) Equal(s2 textNode) bool {
183
	if s2, ok := s2.(textList); ok {
184
		if len(s1) != len(s2) {
185
			return false
186
		}
187
		for i := range s1 {
188
			r1, r2 := s1[i], s2[i]
189
			if !(r1.Diff == r2.Diff && r1.Key == r2.Key && r1.Value.Equal(r2.Value) && r1.Comment == r2.Comment) {
190
				return false
191
			}
192
		}
193
		return true
194
	}
195
	return false
196
}
197

198
func (s textList) String() string {
199
	return (&textWrap{Prefix: "{", Value: s, Suffix: "}"}).String()
200
}
201

202
func (s textList) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) {
203
	s = append(textList(nil), s...) // Avoid mutating original
204

205
	// Determine whether we can collapse this list as a single line.
206
	n0 := len(b) // Original buffer length
207
	var multiLine bool
208
	for i, r := range s {
209
		if r.Diff == diffInserted || r.Diff == diffRemoved {
210
			multiLine = true
211
		}
212
		b = append(b, r.Key...)
213
		if r.Key != "" {
214
			b = append(b, ": "...)
215
		}
216
		b, s[i].Value = r.Value.formatCompactTo(b, d|r.Diff)
217
		if _, ok := s[i].Value.(textLine); !ok {
218
			multiLine = true
219
		}
220
		if r.Comment != nil {
221
			multiLine = true
222
		}
223
		if i < len(s)-1 {
224
			b = append(b, ", "...)
225
		}
226
	}
227
	// Force multi-lined output when printing a removed/inserted node that
228
	// is sufficiently long.
229
	if (d == diffInserted || d == diffRemoved) && len(b[n0:]) > maxColumnLength {
230
		multiLine = true
231
	}
232
	if !multiLine {
233
		return b, textLine(b[n0:])
234
	}
235
	return b, s
236
}
237

238
func (s textList) formatExpandedTo(b []byte, d diffMode, n indentMode) []byte {
239
	alignKeyLens := s.alignLens(
240
		func(r textRecord) bool {
241
			_, isLine := r.Value.(textLine)
242
			return r.Key == "" || !isLine
243
		},
244
		func(r textRecord) int { return utf8.RuneCountInString(r.Key) },
245
	)
246
	alignValueLens := s.alignLens(
247
		func(r textRecord) bool {
248
			_, isLine := r.Value.(textLine)
249
			return !isLine || r.Value.Equal(textEllipsis) || r.Comment == nil
250
		},
251
		func(r textRecord) int { return utf8.RuneCount(r.Value.(textLine)) },
252
	)
253

254
	// Format lists of simple lists in a batched form.
255
	// If the list is sequence of only textLine values,
256
	// then batch multiple values on a single line.
257
	var isSimple bool
258
	for _, r := range s {
259
		_, isLine := r.Value.(textLine)
260
		isSimple = r.Diff == 0 && r.Key == "" && isLine && r.Comment == nil
261
		if !isSimple {
262
			break
263
		}
264
	}
265
	if isSimple {
266
		n++
267
		var batch []byte
268
		emitBatch := func() {
269
			if len(batch) > 0 {
270
				b = n.appendIndent(append(b, '\n'), d)
271
				b = append(b, bytes.TrimRight(batch, " ")...)
272
				batch = batch[:0]
273
			}
274
		}
275
		for _, r := range s {
276
			line := r.Value.(textLine)
277
			if len(batch)+len(line)+len(", ") > maxColumnLength {
278
				emitBatch()
279
			}
280
			batch = append(batch, line...)
281
			batch = append(batch, ", "...)
282
		}
283
		emitBatch()
284
		n--
285
		return n.appendIndent(append(b, '\n'), d)
286
	}
287

288
	// Format the list as a multi-lined output.
289
	n++
290
	for i, r := range s {
291
		b = n.appendIndent(append(b, '\n'), d|r.Diff)
292
		if r.Key != "" {
293
			b = append(b, r.Key+": "...)
294
		}
295
		b = alignKeyLens[i].appendChar(b, ' ')
296

297
		b = r.Value.formatExpandedTo(b, d|r.Diff, n)
298
		if !r.ElideComma {
299
			b = append(b, ',')
300
		}
301
		b = alignValueLens[i].appendChar(b, ' ')
302

303
		if r.Comment != nil {
304
			b = append(b, " // "+r.Comment.String()...)
305
		}
306
	}
307
	n--
308

309
	return n.appendIndent(append(b, '\n'), d)
310
}
311

312
func (s textList) alignLens(
313
	skipFunc func(textRecord) bool,
314
	lenFunc func(textRecord) int,
315
) []repeatCount {
316
	var startIdx, endIdx, maxLen int
317
	lens := make([]repeatCount, len(s))
318
	for i, r := range s {
319
		if skipFunc(r) {
320
			for j := startIdx; j < endIdx && j < len(s); j++ {
321
				lens[j] = repeatCount(maxLen - lenFunc(s[j]))
322
			}
323
			startIdx, endIdx, maxLen = i+1, i+1, 0
324
		} else {
325
			if maxLen < lenFunc(r) {
326
				maxLen = lenFunc(r)
327
			}
328
			endIdx = i + 1
329
		}
330
	}
331
	for j := startIdx; j < endIdx && j < len(s); j++ {
332
		lens[j] = repeatCount(maxLen - lenFunc(s[j]))
333
	}
334
	return lens
335
}
336

337
// textLine is a single-line segment of text and is always a leaf node
338
// in the textNode tree.
339
type textLine []byte
340

341
var (
342
	textNil      = textLine("nil")
343
	textEllipsis = textLine("...")
344
)
345

346
func (s textLine) Len() int {
347
	return len(s)
348
}
349
func (s1 textLine) Equal(s2 textNode) bool {
350
	if s2, ok := s2.(textLine); ok {
351
		return bytes.Equal([]byte(s1), []byte(s2))
352
	}
353
	return false
354
}
355
func (s textLine) String() string {
356
	return string(s)
357
}
358
func (s textLine) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) {
359
	return append(b, s...), s
360
}
361
func (s textLine) formatExpandedTo(b []byte, _ diffMode, _ indentMode) []byte {
362
	return append(b, s...)
363
}
364

365
type diffStats struct {
366
	Name         string
367
	NumIgnored   int
368
	NumIdentical int
369
	NumRemoved   int
370
	NumInserted  int
371
	NumModified  int
372
}
373

374
func (s diffStats) IsZero() bool {
375
	s.Name = ""
376
	return s == diffStats{}
377
}
378

379
func (s diffStats) NumDiff() int {
380
	return s.NumRemoved + s.NumInserted + s.NumModified
381
}
382

383
func (s diffStats) Append(ds diffStats) diffStats {
384
	assert(s.Name == ds.Name)
385
	s.NumIgnored += ds.NumIgnored
386
	s.NumIdentical += ds.NumIdentical
387
	s.NumRemoved += ds.NumRemoved
388
	s.NumInserted += ds.NumInserted
389
	s.NumModified += ds.NumModified
390
	return s
391
}
392

393
// String prints a humanly-readable summary of coalesced records.
394
//
395
// Example:
396
//
397
//	diffStats{Name: "Field", NumIgnored: 5}.String() => "5 ignored fields"
398
func (s diffStats) String() string {
399
	var ss []string
400
	var sum int
401
	labels := [...]string{"ignored", "identical", "removed", "inserted", "modified"}
402
	counts := [...]int{s.NumIgnored, s.NumIdentical, s.NumRemoved, s.NumInserted, s.NumModified}
403
	for i, n := range counts {
404
		if n > 0 {
405
			ss = append(ss, fmt.Sprintf("%d %v", n, labels[i]))
406
		}
407
		sum += n
408
	}
409

410
	// Pluralize the name (adjusting for some obscure English grammar rules).
411
	name := s.Name
412
	if sum > 1 {
413
		name += "s"
414
		if strings.HasSuffix(name, "ys") {
415
			name = name[:len(name)-2] + "ies" // e.g., "entrys" => "entries"
416
		}
417
	}
418

419
	// Format the list according to English grammar (with Oxford comma).
420
	switch n := len(ss); n {
421
	case 0:
422
		return ""
423
	case 1, 2:
424
		return strings.Join(ss, " and ") + " " + name
425
	default:
426
		return strings.Join(ss[:n-1], ", ") + ", and " + ss[n-1] + " " + name
427
	}
428
}
429

430
type commentString string
431

432
func (s commentString) String() string { return string(s) }
433

434