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 |
| 3 | // license that can be found in the LICENSE.md file. |
| 4 | |
| 5 | package cmp |
| 6 | |
| 7 | import ( |
| 8 | "bytes" |
| 9 | "fmt" |
| 10 | "math/rand" |
| 11 | "strings" |
| 12 | "time" |
| 13 | |
| 14 | "github.com/google/go-cmp/cmp/internal/flags" |
| 15 | ) |
| 16 | |
| 17 | var randBool = rand.New(rand.NewSource(time.Now().Unix())).Intn(2) == 0 |
| 18 | |
| 19 | type indentMode int |
| 20 | |
| 21 | func (n indentMode) appendIndent(b []byte, d diffMode) []byte { |
| 22 | // The output of Diff is documented as being unstable to provide future |
| 23 | // flexibility in changing the output for more humanly readable reports. |
| 24 | // This logic intentionally introduces instability to the exact output |
| 25 | // so that users can detect accidental reliance on stability early on, |
| 26 | // rather than much later when an actual change to the format occurs. |
| 27 | if flags.Deterministic || randBool { |
| 28 | // Use regular spaces (U+0020). |
| 29 | switch d { |
| 30 | case diffUnknown, diffIdentical: |
| 31 | b = append(b, " "...) |
| 32 | case diffRemoved: |
| 33 | b = append(b, "- "...) |
| 34 | case diffInserted: |
| 35 | b = append(b, "+ "...) |
| 36 | } |
| 37 | } else { |
| 38 | // Use non-breaking spaces (U+00a0). |
| 39 | switch d { |
| 40 | case diffUnknown, diffIdentical: |
| 41 | b = append(b, " "...) |
| 42 | case diffRemoved: |
| 43 | b = append(b, "- "...) |
| 44 | case diffInserted: |
| 45 | b = append(b, "+ "...) |
| 46 | } |
| 47 | } |
| 48 | return repeatCount(n).appendChar(b, '\t') |
| 49 | } |
| 50 | |
| 51 | type repeatCount int |
| 52 | |
| 53 | func (n repeatCount) appendChar(b []byte, c byte) []byte { |
| 54 | for ; n > 0; n-- { |
| 55 | b = append(b, c) |
| 56 | } |
| 57 | return b |
| 58 | } |
| 59 | |
| 60 | // textNode is a simplified tree-based representation of structured text. |
| 61 | // Possible node types are textWrap, textList, or textLine. |
| 62 | type textNode interface { |
| 63 | // Len reports the length in bytes of a single-line version of the tree. |
| 64 | // Nested textRecord.Diff and textRecord.Comment fields are ignored. |
| 65 | Len() int |
| 66 | // Equal reports whether the two trees are structurally identical. |
| 67 | // Nested textRecord.Diff and textRecord.Comment fields are compared. |
| 68 | Equal(textNode) bool |
| 69 | // String returns the string representation of the text tree. |
| 70 | // It is not guaranteed that len(x.String()) == x.Len(), |
| 71 | // nor that x.String() == y.String() implies that x.Equal(y). |
| 72 | String() string |
| 73 | |
| 74 | // formatCompactTo formats the contents of the tree as a single-line string |
| 75 | // to the provided buffer. Any nested textRecord.Diff and textRecord.Comment |
| 76 | // fields are ignored. |
| 77 | // |
| 78 | // However, not all nodes in the tree should be collapsed as a single-line. |
| 79 | // If a node can be collapsed as a single-line, it is replaced by a textLine |
| 80 | // node. Since the top-level node cannot replace itself, this also returns |
| 81 | // the current node itself. |
| 82 | // |
| 83 | // This does not mutate the receiver. |
| 84 | formatCompactTo([]byte, diffMode) ([]byte, textNode) |
| 85 | // formatExpandedTo formats the contents of the tree as a multi-line string |
| 86 | // to the provided buffer. In order for column alignment to operate well, |
| 87 | // formatCompactTo must be called before calling formatExpandedTo. |
| 88 | formatExpandedTo([]byte, diffMode, indentMode) []byte |
| 89 | } |
| 90 | |
| 91 | // textWrap is a wrapper that concatenates a prefix and/or a suffix |
| 92 | // to the underlying node. |
| 93 | type textWrap struct { |
| 94 | Prefix string // e.g., "bytes.Buffer{" |
| 95 | Value textNode // textWrap | textList | textLine |
| 96 | Suffix string // e.g., "}" |
| 97 | } |
| 98 | |
| 99 | func (s textWrap) Len() int { |
| 100 | return len(s.Prefix) + s.Value.Len() + len(s.Suffix) |
| 101 | } |
| 102 | func (s1 textWrap) Equal(s2 textNode) bool { |
| 103 | if s2, ok := s2.(textWrap); ok { |
| 104 | return s1.Prefix == s2.Prefix && s1.Value.Equal(s2.Value) && s1.Suffix == s2.Suffix |
| 105 | } |
| 106 | return false |
| 107 | } |
| 108 | func (s textWrap) String() string { |
| 109 | var d diffMode |
| 110 | var n indentMode |
| 111 | _, s2 := s.formatCompactTo(nil, d) |
| 112 | b := n.appendIndent(nil, d) // Leading indent |
| 113 | b = s2.formatExpandedTo(b, d, n) // Main body |
| 114 | b = append(b, '\n') // Trailing newline |
| 115 | return string(b) |
| 116 | } |
| 117 | func (s textWrap) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) { |
| 118 | n0 := len(b) // Original buffer length |
| 119 | b = append(b, s.Prefix...) |
| 120 | b, s.Value = s.Value.formatCompactTo(b, d) |
| 121 | b = append(b, s.Suffix...) |
| 122 | if _, ok := s.Value.(textLine); ok { |
| 123 | return b, textLine(b[n0:]) |
| 124 | } |
| 125 | return b, s |
| 126 | } |
| 127 | func (s textWrap) formatExpandedTo(b []byte, d diffMode, n indentMode) []byte { |
| 128 | b = append(b, s.Prefix...) |
| 129 | b = s.Value.formatExpandedTo(b, d, n) |
| 130 | b = append(b, s.Suffix...) |
| 131 | return b |
| 132 | } |
| 133 | |
| 134 | // textList is a comma-separated list of textWrap or textLine nodes. |
| 135 | // The list may be formatted as multi-lines or single-line at the discretion |
| 136 | // of the textList.formatCompactTo method. |
| 137 | type textList []textRecord |
| 138 | type textRecord struct { |
| 139 | Diff diffMode // e.g., 0 or '-' or '+' |
| 140 | Key string // e.g., "MyField" |
| 141 | Value textNode // textWrap | textLine |
| 142 | Comment fmt.Stringer // e.g., "6 identical fields" |
| 143 | } |
| 144 | |
| 145 | // AppendEllipsis appends a new ellipsis node to the list if none already |
| 146 | // exists at the end. If cs is non-zero it coalesces the statistics with the |
| 147 | // previous diffStats. |
| 148 | func (s *textList) AppendEllipsis(ds diffStats) { |
| 149 | hasStats := ds != diffStats{} |
| 150 | if len(*s) == 0 || !(*s)[len(*s)-1].Value.Equal(textEllipsis) { |
| 151 | if hasStats { |
| 152 | *s = append(*s, textRecord{Value: textEllipsis, Comment: ds}) |
| 153 | } else { |
| 154 | *s = append(*s, textRecord{Value: textEllipsis}) |
| 155 | } |
| 156 | return |
| 157 | } |
| 158 | if hasStats { |
| 159 | (*s)[len(*s)-1].Comment = (*s)[len(*s)-1].Comment.(diffStats).Append(ds) |
| 160 | } |
| 161 | } |
| 162 | |
| 163 | func (s textList) Len() (n int) { |
| 164 | for i, r := range s { |
| 165 | n += len(r.Key) |
| 166 | if r.Key != "" { |
| 167 | n += len(": ") |
| 168 | } |
| 169 | n += r.Value.Len() |
| 170 | if i < len(s)-1 { |
| 171 | n += len(", ") |
| 172 | } |
| 173 | } |
| 174 | return n |
| 175 | } |
| 176 | |
| 177 | func (s1 textList) Equal(s2 textNode) bool { |
| 178 | if s2, ok := s2.(textList); ok { |
| 179 | if len(s1) != len(s2) { |
| 180 | return false |
| 181 | } |
| 182 | for i := range s1 { |
| 183 | r1, r2 := s1[i], s2[i] |
| 184 | if !(r1.Diff == r2.Diff && r1.Key == r2.Key && r1.Value.Equal(r2.Value) && r1.Comment == r2.Comment) { |
| 185 | return false |
| 186 | } |
| 187 | } |
| 188 | return true |
| 189 | } |
| 190 | return false |
| 191 | } |
| 192 | |
| 193 | func (s textList) String() string { |
| 194 | return textWrap{"{", s, "}"}.String() |
| 195 | } |
| 196 | |
| 197 | func (s textList) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) { |
| 198 | s = append(textList(nil), s...) // Avoid mutating original |
| 199 | |
| 200 | // Determine whether we can collapse this list as a single line. |
| 201 | n0 := len(b) // Original buffer length |
| 202 | var multiLine bool |
| 203 | for i, r := range s { |
| 204 | if r.Diff == diffInserted || r.Diff == diffRemoved { |
| 205 | multiLine = true |
| 206 | } |
| 207 | b = append(b, r.Key...) |
| 208 | if r.Key != "" { |
| 209 | b = append(b, ": "...) |
| 210 | } |
| 211 | b, s[i].Value = r.Value.formatCompactTo(b, d|r.Diff) |
| 212 | if _, ok := s[i].Value.(textLine); !ok { |
| 213 | multiLine = true |
| 214 | } |
| 215 | if r.Comment != nil { |
| 216 | multiLine = true |
| 217 | } |
| 218 | if i < len(s)-1 { |
| 219 | b = append(b, ", "...) |
| 220 | } |
| 221 | } |
| 222 | // Force multi-lined output when printing a removed/inserted node that |
| 223 | // is sufficiently long. |
| 224 | if (d == diffInserted || d == diffRemoved) && len(b[n0:]) > 80 { |
| 225 | multiLine = true |
| 226 | } |
| 227 | if !multiLine { |
| 228 | return b, textLine(b[n0:]) |
| 229 | } |
| 230 | return b, s |
| 231 | } |
| 232 | |
| 233 | func (s textList) formatExpandedTo(b []byte, d diffMode, n indentMode) []byte { |
| 234 | alignKeyLens := s.alignLens( |
| 235 | func(r textRecord) bool { |
| 236 | _, isLine := r.Value.(textLine) |
| 237 | return r.Key == "" || !isLine |
| 238 | }, |
| 239 | func(r textRecord) int { return len(r.Key) }, |
| 240 | ) |
| 241 | alignValueLens := s.alignLens( |
| 242 | func(r textRecord) bool { |
| 243 | _, isLine := r.Value.(textLine) |
| 244 | return !isLine || r.Value.Equal(textEllipsis) || r.Comment == nil |
| 245 | }, |
| 246 | func(r textRecord) int { return len(r.Value.(textLine)) }, |
| 247 | ) |
| 248 | |
| 249 | // Format the list as a multi-lined output. |
| 250 | n++ |
| 251 | for i, r := range s { |
| 252 | b = n.appendIndent(append(b, '\n'), d|r.Diff) |
| 253 | if r.Key != "" { |
| 254 | b = append(b, r.Key+": "...) |
| 255 | } |
| 256 | b = alignKeyLens[i].appendChar(b, ' ') |
| 257 | |
| 258 | b = r.Value.formatExpandedTo(b, d|r.Diff, n) |
| 259 | if !r.Value.Equal(textEllipsis) { |
| 260 | b = append(b, ',') |
| 261 | } |
| 262 | b = alignValueLens[i].appendChar(b, ' ') |
| 263 | |
| 264 | if r.Comment != nil { |
| 265 | b = append(b, " // "+r.Comment.String()...) |
| 266 | } |
| 267 | } |
| 268 | n-- |
| 269 | |
| 270 | return n.appendIndent(append(b, '\n'), d) |
| 271 | } |
| 272 | |
| 273 | func (s textList) alignLens( |
| 274 | skipFunc func(textRecord) bool, |
| 275 | lenFunc func(textRecord) int, |
| 276 | ) []repeatCount { |
| 277 | var startIdx, endIdx, maxLen int |
| 278 | lens := make([]repeatCount, len(s)) |
| 279 | for i, r := range s { |
| 280 | if skipFunc(r) { |
| 281 | for j := startIdx; j < endIdx && j < len(s); j++ { |
| 282 | lens[j] = repeatCount(maxLen - lenFunc(s[j])) |
| 283 | } |
| 284 | startIdx, endIdx, maxLen = i+1, i+1, 0 |
| 285 | } else { |
| 286 | if maxLen < lenFunc(r) { |
| 287 | maxLen = lenFunc(r) |
| 288 | } |
| 289 | endIdx = i + 1 |
| 290 | } |
| 291 | } |
| 292 | for j := startIdx; j < endIdx && j < len(s); j++ { |
| 293 | lens[j] = repeatCount(maxLen - lenFunc(s[j])) |
| 294 | } |
| 295 | return lens |
| 296 | } |
| 297 | |
| 298 | // textLine is a single-line segment of text and is always a leaf node |
| 299 | // in the textNode tree. |
| 300 | type textLine []byte |
| 301 | |
| 302 | var ( |
| 303 | textNil = textLine("nil") |
| 304 | textEllipsis = textLine("...") |
| 305 | ) |
| 306 | |
| 307 | func (s textLine) Len() int { |
| 308 | return len(s) |
| 309 | } |
| 310 | func (s1 textLine) Equal(s2 textNode) bool { |
| 311 | if s2, ok := s2.(textLine); ok { |
| 312 | return bytes.Equal([]byte(s1), []byte(s2)) |
| 313 | } |
| 314 | return false |
| 315 | } |
| 316 | func (s textLine) String() string { |
| 317 | return string(s) |
| 318 | } |
| 319 | func (s textLine) formatCompactTo(b []byte, d diffMode) ([]byte, textNode) { |
| 320 | return append(b, s...), s |
| 321 | } |
| 322 | func (s textLine) formatExpandedTo(b []byte, _ diffMode, _ indentMode) []byte { |
| 323 | return append(b, s...) |
| 324 | } |
| 325 | |
| 326 | type diffStats struct { |
| 327 | Name string |
| 328 | NumIgnored int |
| 329 | NumIdentical int |
| 330 | NumRemoved int |
| 331 | NumInserted int |
| 332 | NumModified int |
| 333 | } |
| 334 | |
| 335 | func (s diffStats) NumDiff() int { |
| 336 | return s.NumRemoved + s.NumInserted + s.NumModified |
| 337 | } |
| 338 | |
| 339 | func (s diffStats) Append(ds diffStats) diffStats { |
| 340 | assert(s.Name == ds.Name) |
| 341 | s.NumIgnored += ds.NumIgnored |
| 342 | s.NumIdentical += ds.NumIdentical |
| 343 | s.NumRemoved += ds.NumRemoved |
| 344 | s.NumInserted += ds.NumInserted |
| 345 | s.NumModified += ds.NumModified |
| 346 | return s |
| 347 | } |
| 348 | |
| 349 | // String prints a humanly-readable summary of coalesced records. |
| 350 | // |
| 351 | // Example: |
| 352 | // diffStats{Name: "Field", NumIgnored: 5}.String() => "5 ignored fields" |
| 353 | func (s diffStats) String() string { |
| 354 | var ss []string |
| 355 | var sum int |
| 356 | labels := [...]string{"ignored", "identical", "removed", "inserted", "modified"} |
| 357 | counts := [...]int{s.NumIgnored, s.NumIdentical, s.NumRemoved, s.NumInserted, s.NumModified} |
| 358 | for i, n := range counts { |
| 359 | if n > 0 { |
| 360 | ss = append(ss, fmt.Sprintf("%d %v", n, labels[i])) |
| 361 | } |
| 362 | sum += n |
| 363 | } |
| 364 | |
| 365 | // Pluralize the name (adjusting for some obscure English grammar rules). |
| 366 | name := s.Name |
| 367 | if sum > 1 { |
| 368 | name += "s" |
| 369 | if strings.HasSuffix(name, "ys") { |
| 370 | name = name[:len(name)-2] + "ies" // e.g., "entrys" => "entries" |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | // Format the list according to English grammar (with Oxford comma). |
| 375 | switch n := len(ss); n { |
| 376 | case 0: |
| 377 | return "" |
| 378 | case 1, 2: |
| 379 | return strings.Join(ss, " and ") + " " + name |
| 380 | default: |
| 381 | return strings.Join(ss[:n-1], ", ") + ", and " + ss[n-1] + " " + name |
| 382 | } |
| 383 | } |
| 384 | |
| 385 | type commentString string |
| 386 | |
| 387 | func (s commentString) String() string { return string(s) } |