Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 1 | // Copyright 2019, The Go Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 3 | // license that can be found in the LICENSE file. |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 4 | |
| 5 | package cmp |
| 6 | |
| 7 | import ( |
| 8 | "bytes" |
| 9 | "fmt" |
| 10 | "math/rand" |
| 11 | "strings" |
| 12 | "time" |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 13 | "unicode/utf8" |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 20 | const maxColumnLength = 80 |
| 21 | |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 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 |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 101 | } |
| 102 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 103 | func (s *textWrap) Len() int { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 104 | return len(s.Prefix) + s.Value.Len() + len(s.Suffix) |
| 105 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 106 | func (s1 *textWrap) Equal(s2 textNode) bool { |
| 107 | if s2, ok := s2.(*textWrap); ok { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 108 | return s1.Prefix == s2.Prefix && s1.Value.Equal(s2.Value) && s1.Suffix == s2.Suffix |
| 109 | } |
| 110 | return false |
| 111 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 112 | func (s *textWrap) String() string { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 121 | func (s *textWrap) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 131 | func (s *textWrap) formatExpandedTo(b []byte, d diffMode, n indentMode) []byte { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 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" |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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) { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 154 | hasStats := !ds.IsZero() |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 155 | if len(*s) == 0 || !(*s)[len(*s)-1].Value.Equal(textEllipsis) { |
| 156 | if hasStats { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 157 | *s = append(*s, textRecord{Value: textEllipsis, ElideComma: true, Comment: ds}) |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 158 | } else { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 159 | *s = append(*s, textRecord{Value: textEllipsis, ElideComma: true}) |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 199 | return (&textWrap{Prefix: "{", Value: s, Suffix: "}"}).String() |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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. |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 229 | if (d == diffInserted || d == diffRemoved) && len(b[n0:]) > maxColumnLength { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | }, |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 244 | func(r textRecord) int { return utf8.RuneCountInString(r.Key) }, |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | }, |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 251 | func(r textRecord) int { return utf8.RuneCount(r.Value.(textLine)) }, |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 252 | ) |
| 253 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 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 | |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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) |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 298 | if !r.ElideComma { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame] | 374 | func (s diffStats) IsZero() bool { |
| 375 | s.Name = "" |
| 376 | return s == diffStats{} |
| 377 | } |
| 378 | |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | // diffStats{Name: "Field", NumIgnored: 5}.String() => "5 ignored fields" |
| 397 | func (s diffStats) String() string { |
| 398 | var ss []string |
| 399 | var sum int |
| 400 | labels := [...]string{"ignored", "identical", "removed", "inserted", "modified"} |
| 401 | counts := [...]int{s.NumIgnored, s.NumIdentical, s.NumRemoved, s.NumInserted, s.NumModified} |
| 402 | for i, n := range counts { |
| 403 | if n > 0 { |
| 404 | ss = append(ss, fmt.Sprintf("%d %v", n, labels[i])) |
| 405 | } |
| 406 | sum += n |
| 407 | } |
| 408 | |
| 409 | // Pluralize the name (adjusting for some obscure English grammar rules). |
| 410 | name := s.Name |
| 411 | if sum > 1 { |
| 412 | name += "s" |
| 413 | if strings.HasSuffix(name, "ys") { |
| 414 | name = name[:len(name)-2] + "ies" // e.g., "entrys" => "entries" |
| 415 | } |
| 416 | } |
| 417 | |
| 418 | // Format the list according to English grammar (with Oxford comma). |
| 419 | switch n := len(ss); n { |
| 420 | case 0: |
| 421 | return "" |
| 422 | case 1, 2: |
| 423 | return strings.Join(ss, " and ") + " " + name |
| 424 | default: |
| 425 | return strings.Join(ss[:n-1], ", ") + ", and " + ss[n-1] + " " + name |
| 426 | } |
| 427 | } |
| 428 | |
| 429 | type commentString string |
| 430 | |
| 431 | func (s commentString) String() string { return string(s) } |