diff.go

Documentation: k8s.io/utils/diff

     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/utils/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  // ObjectReflectDiff returns a diff computed through reflection, without serializing to JSON.
    82  func ObjectReflectDiff(a, b interface{}) string {
    83  	vA, vB := reflect.ValueOf(a), reflect.ValueOf(b)
    84  	if vA.Type() != vB.Type() {
    85  		return fmt.Sprintf("type A %T and type B %T do not match", a, b)
    86  	}
    87  	diffs := objectReflectDiff(field.NewPath("object"), vA, vB)
    88  	if len(diffs) == 0 {
    89  		return "<no diffs>"
    90  	}
    91  	out := []string{""}
    92  	for _, d := range diffs {
    93  		elidedA, elidedB := limit(d.a, d.b, 80)
    94  		out = append(out,
    95  			fmt.Sprintf("%s:", d.path),
    96  			fmt.Sprintf("  a: %s", elidedA),
    97  			fmt.Sprintf("  b: %s", elidedB),
    98  		)
    99  	}
   100  	return strings.Join(out, "\n")
   101  }
   102  
   103  // limit:
   104  // 1. stringifies aObj and bObj
   105  // 2. elides identical prefixes if either is too long
   106  // 3. elides remaining content from the end if either is too long
   107  func limit(aObj, bObj interface{}, max int) (string, string) {
   108  	elidedPrefix := ""
   109  	elidedASuffix := ""
   110  	elidedBSuffix := ""
   111  	a, b := fmt.Sprintf("%#v", aObj), fmt.Sprintf("%#v", bObj)
   112  
   113  	if aObj != nil && bObj != nil {
   114  		if aType, bType := fmt.Sprintf("%T", aObj), fmt.Sprintf("%T", bObj); aType != bType {
   115  			a = fmt.Sprintf("%s (%s)", a, aType)
   116  			b = fmt.Sprintf("%s (%s)", b, bType)
   117  		}
   118  	}
   119  
   120  	for {
   121  		switch {
   122  		case len(a) > max && len(a) > 4 && len(b) > 4 && a[:4] == b[:4]:
   123  			// a is too long, b has data, and the first several characters are the same
   124  			elidedPrefix = "..."
   125  			a = a[2:]
   126  			b = b[2:]
   127  
   128  		case len(b) > max && len(b) > 4 && len(a) > 4 && a[:4] == b[:4]:
   129  			// b is too long, a has data, and the first several characters are the same
   130  			elidedPrefix = "..."
   131  			a = a[2:]
   132  			b = b[2:]
   133  
   134  		case len(a) > max:
   135  			a = a[:max]
   136  			elidedASuffix = "..."
   137  
   138  		case len(b) > max:
   139  			b = b[:max]
   140  			elidedBSuffix = "..."
   141  
   142  		default:
   143  			// both are short enough
   144  			return elidedPrefix + a + elidedASuffix, elidedPrefix + b + elidedBSuffix
   145  		}
   146  	}
   147  }
   148  
   149  func public(s string) bool {
   150  	if len(s) == 0 {
   151  		return false
   152  	}
   153  	return s[:1] == strings.ToUpper(s[:1])
   154  }
   155  
   156  type diff struct {
   157  	path *field.Path
   158  	a, b interface{}
   159  }
   160  
   161  type orderedDiffs []diff
   162  
   163  func (d orderedDiffs) Len() int      { return len(d) }
   164  func (d orderedDiffs) Swap(i, j int) { d[i], d[j] = d[j], d[i] }
   165  func (d orderedDiffs) Less(i, j int) bool {
   166  	a, b := d[i].path.String(), d[j].path.String()
   167  	if a < b {
   168  		return true
   169  	}
   170  	return false
   171  }
   172  
   173  func objectReflectDiff(path *field.Path, a, b reflect.Value) []diff {
   174  	switch a.Type().Kind() {
   175  	case reflect.Struct:
   176  		var changes []diff
   177  		for i := 0; i < a.Type().NumField(); i++ {
   178  			if !public(a.Type().Field(i).Name) {
   179  				if reflect.DeepEqual(a.Interface(), b.Interface()) {
   180  					continue
   181  				}
   182  				return []diff{{path: path, a: fmt.Sprintf("%#v", a), b: fmt.Sprintf("%#v", b)}}
   183  			}
   184  			if sub := objectReflectDiff(path.Child(a.Type().Field(i).Name), a.Field(i), b.Field(i)); len(sub) > 0 {
   185  				changes = append(changes, sub...)
   186  			}
   187  		}
   188  		return changes
   189  	case reflect.Ptr, reflect.Interface:
   190  		if a.IsNil() || b.IsNil() {
   191  			switch {
   192  			case a.IsNil() && b.IsNil():
   193  				return nil
   194  			case a.IsNil():
   195  				return []diff{{path: path, a: nil, b: b.Interface()}}
   196  			default:
   197  				return []diff{{path: path, a: a.Interface(), b: nil}}
   198  			}
   199  		}
   200  		return objectReflectDiff(path, a.Elem(), b.Elem())
   201  	case reflect.Chan:
   202  		if !reflect.DeepEqual(a.Interface(), b.Interface()) {
   203  			return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
   204  		}
   205  		return nil
   206  	case reflect.Slice:
   207  		lA, lB := a.Len(), b.Len()
   208  		l := lA
   209  		if lB < lA {
   210  			l = lB
   211  		}
   212  		if lA == lB && lA == 0 {
   213  			if a.IsNil() != b.IsNil() {
   214  				return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
   215  			}
   216  			return nil
   217  		}
   218  		var diffs []diff
   219  		for i := 0; i < l; i++ {
   220  			if !reflect.DeepEqual(a.Index(i), b.Index(i)) {
   221  				diffs = append(diffs, objectReflectDiff(path.Index(i), a.Index(i), b.Index(i))...)
   222  			}
   223  		}
   224  		for i := l; i < lA; i++ {
   225  			diffs = append(diffs, diff{path: path.Index(i), a: a.Index(i), b: nil})
   226  		}
   227  		for i := l; i < lB; i++ {
   228  			diffs = append(diffs, diff{path: path.Index(i), a: nil, b: b.Index(i)})
   229  		}
   230  		return diffs
   231  	case reflect.Map:
   232  		if reflect.DeepEqual(a.Interface(), b.Interface()) {
   233  			return nil
   234  		}
   235  		aKeys := make(map[interface{}]interface{})
   236  		for _, key := range a.MapKeys() {
   237  			aKeys[key.Interface()] = a.MapIndex(key).Interface()
   238  		}
   239  		var missing []diff
   240  		for _, key := range b.MapKeys() {
   241  			if _, ok := aKeys[key.Interface()]; ok {
   242  				delete(aKeys, key.Interface())
   243  				if reflect.DeepEqual(a.MapIndex(key).Interface(), b.MapIndex(key).Interface()) {
   244  					continue
   245  				}
   246  				missing = append(missing, objectReflectDiff(path.Key(fmt.Sprintf("%s", key.Interface())), a.MapIndex(key), b.MapIndex(key))...)
   247  				continue
   248  			}
   249  			missing = append(missing, diff{path: path.Key(fmt.Sprintf("%s", key.Interface())), a: nil, b: b.MapIndex(key).Interface()})
   250  		}
   251  		for key, value := range aKeys {
   252  			missing = append(missing, diff{path: path.Key(fmt.Sprintf("%s", key)), a: value, b: nil})
   253  		}
   254  		if len(missing) == 0 {
   255  			missing = append(missing, diff{path: path, a: a.Interface(), b: b.Interface()})
   256  		}
   257  		sort.Sort(orderedDiffs(missing))
   258  		return missing
   259  	default:
   260  		if reflect.DeepEqual(a.Interface(), b.Interface()) {
   261  			return nil
   262  		}
   263  		if !a.CanInterface() {
   264  			return []diff{{path: path, a: fmt.Sprintf("%#v", a), b: fmt.Sprintf("%#v", b)}}
   265  		}
   266  		return []diff{{path: path, a: a.Interface(), b: b.Interface()}}
   267  	}
   268  }
   269  
   270  // ObjectGoPrintSideBySide prints a and b as textual dumps side by side,
   271  // enabling easy visual scanning for mismatches.
   272  func ObjectGoPrintSideBySide(a, b interface{}) string {
   273  	s := spew.ConfigState{
   274  		Indent: " ",
   275  		// Extra deep spew.
   276  		DisableMethods: true,
   277  	}
   278  	sA := s.Sdump(a)
   279  	sB := s.Sdump(b)
   280  
   281  	linesA := strings.Split(sA, "\n")
   282  	linesB := strings.Split(sB, "\n")
   283  	width := 0
   284  	for _, s := range linesA {
   285  		l := len(s)
   286  		if l > width {
   287  			width = l
   288  		}
   289  	}
   290  	for _, s := range linesB {
   291  		l := len(s)
   292  		if l > width {
   293  			width = l
   294  		}
   295  	}
   296  	buf := &bytes.Buffer{}
   297  	w := tabwriter.NewWriter(buf, width, 0, 1, ' ', 0)
   298  	max := len(linesA)
   299  	if len(linesB) > max {
   300  		max = len(linesB)
   301  	}
   302  	for i := 0; i < max; i++ {
   303  		var a, b string
   304  		if i < len(linesA) {
   305  			a = linesA[i]
   306  		}
   307  		if i < len(linesB) {
   308  			b = linesB[i]
   309  		}
   310  		fmt.Fprintf(w, "%s\t%s\n", a, b)
   311  	}
   312  	w.Flush()
   313  	return buf.String()
   314  }
   315
View as plain text