cmd/bpa-operator/vendor/k8s.io/apimachinery/pkg/util/diff/diff.go

   1 /*
   2 Copyright 2014 The Kubernetes Authors.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 package diff
  18
  19 import (
  20         "bytes"
  21         "encoding/json"
  22         "fmt"
  23         "reflect"
  24         "sort"
  25         "strings"
  26         "text/tabwriter"
  27
  28         "github.com/davecgh/go-spew/spew"
  29
  30         "k8s.io/apimachinery/pkg/util/validation/field"
  31 )
  32
  33 // StringDiff diffs a and b and returns a human readable diff.
  34 func StringDiff(a, b string) string {
  35         ba := []byte(a)
  36         bb := []byte(b)
  37         out := []byte{}
  38         i := 0
  39         for ; i < len(ba) && i < len(bb); i++ {
  40                 if ba[i] != bb[i] {
  41                         break
  42                 }
  43                 out = append(out, ba[i])
  44         }
  45         out = append(out, []byte("\n\nA: ")...)
  46         out = append(out, ba[i:]...)
  47         out = append(out, []byte("\n\nB: ")...)
  48         out = append(out, bb[i:]...)
  49         out = append(out, []byte("\n\n")...)
  50         return string(out)
  51 }
  52
  53 // ObjectDiff writes the two objects out as JSON and prints out the identical part of
  54 // the objects followed by the remaining part of 'a' and finally the remaining part of 'b'.
  55 // For debugging tests.
  56 func ObjectDiff(a, b interface{}) string {
  57         ab, err := json.Marshal(a)
  58         if err != nil {
  59                 panic(fmt.Sprintf("a: %v", err))
  60         }
  61         bb, err := json.Marshal(b)
  62         if err != nil {
  63                 panic(fmt.Sprintf("b: %v", err))
  64         }
  65         return StringDiff(string(ab), string(bb))
  66 }
  67
  68 // ObjectGoPrintDiff is like ObjectDiff, but uses go-spew to print the objects,
  69 // which shows absolutely everything by recursing into every single pointer
  70 // (go's %#v formatters OTOH stop at a certain point). This is needed when you
  71 // can't figure out why reflect.DeepEqual is returning false and nothing is
  72 // showing you differences. This will.
  73 func ObjectGoPrintDiff(a, b interface{}) string {
  74         s := spew.ConfigState{DisableMethods: true}
  75         return StringDiff(
  76                 s.Sprintf("%#v", a),
  77                 s.Sprintf("%#v", b),
  78         )
  79 }
  80
  81 func ObjectReflectDiff(a, b interface{}) string {
  82         vA, vB := reflect.ValueOf(a), reflect.ValueOf(b)
  83         if vA.Type() != vB.Type() {
  84                 return fmt.Sprintf("type A %T and type B %T do not match", a, b)
  85         }
  86         diffs := objectReflectDiff(field.NewPath("object"), vA, vB)
  87         if len(diffs) == 0 {
  88                 return "<no diffs>"
  89         }
  90         out := []string{""}
  91         for _, d := range diffs {
  92                 elidedA, elidedB := limit(d.a, d.b, 80)
  93                 out = append(out,
  94                         fmt.Sprintf("%s:", d.path),
  95                         fmt.Sprintf("  a: %s", elidedA),
  96                         fmt.Sprintf("  b: %s", elidedB),
  97                 )
  98         }
  99         return strings.Join(out, "\n")
 100 }
 101
 102 // limit:
 103 // 1. stringifies aObj and bObj
 104 // 2. elides identical prefixes if either is too long
 105 // 3. elides remaining content from the end if either is too long
 106 func limit(aObj, bObj interface{}, max int) (string, string) {
 107         elidedPrefix := ""
 108         elidedASuffix := ""
 109         elidedBSuffix := ""
 110         a, b := fmt.Sprintf("%#v", aObj), fmt.Sprintf("%#v", bObj)
 111
 112         if aObj != nil && bObj != nil {
 113                 if aType, bType := fmt.Sprintf("%T", aObj), fmt.Sprintf("%T", bObj); aType != bType {
 114                         a = fmt.Sprintf("%s (%s)", a, aType)
 115                         b = fmt.Sprintf("%s (%s)", b, bType)
 116                 }
 117         }
 118
 119         for {
 120                 switch {
 121                 case len(a) > max && len(a) > 4 && len(b) > 4 && a[:4] == b[:4]:
 122                         // a is too long, b has data, and the first several characters are the same
 123                         elidedPrefix = "..."
 124                         a = a[2:]
 125                         b = b[2:]
 126
 127                 case len(b) > max && len(b) > 4 && len(a) > 4 && a[:4] == b[:4]:
 128                         // b is too long, a has data, and the first several characters are the same
 129                         elidedPrefix = "..."
 130                         a = a[2:]
 131                         b = b[2:]
 132
 133                 case len(a) > max:
 134                         a = a[:max]
 135                         elidedASuffix = "..."
 136
 137                 case len(b) > max:
 138                         b = b[:max]
 139                         elidedBSuffix = "..."
 140
 141                 default:
 142                         // both are short enough
 143                         return elidedPrefix + a + elidedASuffix, elidedPrefix + b + elidedBSuffix
 144                 }
 145         }
 146 }
 147
 148 func public(s string) bool {
 149         if len(s) == 0 {
 150                 return false
 151         }
 152         return s[:1] == strings.ToUpper(s[:1])
 153 }
 154
 155 type diff struct {
 156         path *field.Path
 157         a, b interface{}
 158 }
 159
 160 type orderedDiffs []diff
 161
 162 func (d orderedDiffs) Len() int      { return len(d) }
 163 func (d orderedDiffs) Swap(i, j int) { d[i], d[j] = d[j], d[i] }
 164 func (d orderedDiffs) Less(i, j int) bool {
 165         a, b := d[i].path.String(), d[j].path.String()
 166         if a < b {
 167                 return true
 168         }
 169         return false
 170 }
 171
 172 func objectReflectDiff(path *field.Path, a, b reflect.Value) []diff {
 173         switch a.Type().Kind() {
 174         case reflect.Struct:
 175                 var changes []diff
 176                 for i := 0; i < a.Type().NumField(); i++ {
 177                         if !public(a.Type().Field(i).Name) {
 178                                 if reflect.DeepEqual(a.Interface(), b.Interface()) {
 179                                         continue
 180                                 }
 181                                 return []diff{{path: path, a: fmt.Sprintf("%#v", a), b: fmt.Sprintf("%#v", b)}}
 182                         }
 183                         if sub := objectReflectDiff(path.Child(a.Type().Field(i).Name), a.Field(i), b.Field(i)); len(sub) > 0 {
 184                                 changes = append(changes, sub...)
 185                         }
 186                 }
 187                 return changes
 188         case reflect.Ptr, reflect.Interface:
 189                 if a.IsNil() || b.IsNil() {
 190                         switch {
 191                         case a.IsNil() && b.IsNil():
 192                                 return nil
 193                         case a.IsNil():
 194                                 return []diff{{path: path, a: nil, b: b.Interface()}}
 195                         default:
 196                                 return []diff{{path: path, a: a.Interface(), b: nil}}
 197                         }
 198                 }
 199                 return objectReflectDiff(path, a.Elem(), b.Elem())
 200         case reflect.Chan:
 201                 if !reflect.DeepEqual(a.Interface(), b.Interface()) {
 202                         return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
 203                 }
 204                 return nil
 205         case reflect.Slice:
 206                 lA, lB := a.Len(), b.Len()
 207                 l := lA
 208                 if lB < lA {
 209                         l = lB
 210                 }
 211                 if lA == lB && lA == 0 {
 212                         if a.IsNil() != b.IsNil() {
 213                                 return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
 214                         }
 215                         return nil
 216                 }
 217                 var diffs []diff
 218                 for i := 0; i < l; i++ {
 219                         if !reflect.DeepEqual(a.Index(i), b.Index(i)) {
 220                                 diffs = append(diffs, objectReflectDiff(path.Index(i), a.Index(i), b.Index(i))...)
 221                         }
 222                 }
 223                 for i := l; i < lA; i++ {
 224                         diffs = append(diffs, diff{path: path.Index(i), a: a.Index(i), b: nil})
 225                 }
 226                 for i := l; i < lB; i++ {
 227                         diffs = append(diffs, diff{path: path.Index(i), a: nil, b: b.Index(i)})
 228                 }
 229                 return diffs
 230         case reflect.Map:
 231                 if reflect.DeepEqual(a.Interface(), b.Interface()) {
 232                         return nil
 233                 }
 234                 aKeys := make(map[interface{}]interface{})
 235                 for _, key := range a.MapKeys() {
 236                         aKeys[key.Interface()] = a.MapIndex(key).Interface()
 237                 }
 238                 var missing []diff
 239                 for _, key := range b.MapKeys() {
 240                         if _, ok := aKeys[key.Interface()]; ok {
 241                                 delete(aKeys, key.Interface())
 242                                 if reflect.DeepEqual(a.MapIndex(key).Interface(), b.MapIndex(key).Interface()) {
 243                                         continue
 244                                 }
 245                                 missing = append(missing, objectReflectDiff(path.Key(fmt.Sprintf("%s", key.Interface())), a.MapIndex(key), b.MapIndex(key))...)
 246                                 continue
 247                         }
 248                         missing = append(missing, diff{path: path.Key(fmt.Sprintf("%s", key.Interface())), a: nil, b: b.MapIndex(key).Interface()})
 249                 }
 250                 for key, value := range aKeys {
 251                         missing = append(missing, diff{path: path.Key(fmt.Sprintf("%s", key)), a: value, b: nil})
 252                 }
 253                 if len(missing) == 0 {
 254                         missing = append(missing, diff{path: path, a: a.Interface(), b: b.Interface()})
 255                 }
 256                 sort.Sort(orderedDiffs(missing))
 257                 return missing
 258         default:
 259                 if reflect.DeepEqual(a.Interface(), b.Interface()) {
 260                         return nil
 261                 }
 262                 if !a.CanInterface() {
 263                         return []diff{{path: path, a: fmt.Sprintf("%#v", a), b: fmt.Sprintf("%#v", b)}}
 264                 }
 265                 return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
 266         }
 267 }
 268
 269 // ObjectGoPrintSideBySide prints a and b as textual dumps side by side,
 270 // enabling easy visual scanning for mismatches.
 271 func ObjectGoPrintSideBySide(a, b interface{}) string {
 272         s := spew.ConfigState{
 273                 Indent: " ",
 274                 // Extra deep spew.
 275                 DisableMethods: true,
 276         }
 277         sA := s.Sdump(a)
 278         sB := s.Sdump(b)
 279
 280         linesA := strings.Split(sA, "\n")
 281         linesB := strings.Split(sB, "\n")
 282         width := 0
 283         for _, s := range linesA {
 284                 l := len(s)
 285                 if l > width {
 286                         width = l
 287                 }
 288         }
 289         for _, s := range linesB {
 290                 l := len(s)
 291                 if l > width {
 292                         width = l
 293                 }
 294         }
 295         buf := &bytes.Buffer{}
 296         w := tabwriter.NewWriter(buf, width, 0, 1, ' ', 0)
 297         max := len(linesA)
 298         if len(linesB) > max {
 299                 max = len(linesB)
 300         }
 301         for i := 0; i < max; i++ {
 302                 var a, b string
 303                 if i < len(linesA) {
 304                         a = linesA[i]
 305                 }
 306                 if i < len(linesB) {
 307                         b = linesB[i]
 308                 }
 309                 fmt.Fprintf(w, "%s\t%s\n", a, b)
 310         }
 311         w.Flush()
 312         return buf.String()
 313 }