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