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