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 | "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. |
| 23 | const numContextRecords = 2 |
| 24 | |
| 25 | type diffMode byte |
| 26 | |
| 27 | const ( |
| 28 | diffUnknown diffMode = 0 |
| 29 | diffIdentical diffMode = ' ' |
| 30 | diffRemoved diffMode = '-' |
| 31 | diffInserted diffMode = '+' |
| 32 | ) |
| 33 | |
| 34 | type typeMode int |
| 35 | |
| 36 | const ( |
| 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 | |
| 46 | type 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 | |
| 66 | func (opts formatOptions) WithDiffMode(d diffMode) formatOptions { |
| 67 | opts.DiffMode = d |
| 68 | return opts |
| 69 | } |
| 70 | func (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. |
| 77 | func (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 | |
| 141 | func (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.ValueY) |
| 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. |
| 272 | func 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 | } |