compare.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/typed

     1  /*
     2  Copyright 2018 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 typed
    18  
    19  import (
    20  	"fmt"
    21  	"strings"
    22  
    23  	"sigs.k8s.io/structured-merge-diff/v4/fieldpath"
    24  	"sigs.k8s.io/structured-merge-diff/v4/schema"
    25  	"sigs.k8s.io/structured-merge-diff/v4/value"
    26  )
    27  
    28  // Comparison is the return value of a TypedValue.Compare() operation.
    29  //
    30  // No field will appear in more than one of the three fieldsets. If all of the
    31  // fieldsets are empty, then the objects must have been equal.
    32  type Comparison struct {
    33  	// Removed contains any fields removed by rhs (the right-hand-side
    34  	// object in the comparison).
    35  	Removed *fieldpath.Set
    36  	// Modified contains fields present in both objects but different.
    37  	Modified *fieldpath.Set
    38  	// Added contains any fields added by rhs.
    39  	Added *fieldpath.Set
    40  }
    41  
    42  // IsSame returns true if the comparison returned no changes (the two
    43  // compared objects are similar).
    44  func (c *Comparison) IsSame() bool {
    45  	return c.Removed.Empty() && c.Modified.Empty() && c.Added.Empty()
    46  }
    47  
    48  // String returns a human readable version of the comparison.
    49  func (c *Comparison) String() string {
    50  	bld := strings.Builder{}
    51  	if !c.Modified.Empty() {
    52  		bld.WriteString(fmt.Sprintf("- Modified Fields:\n%v\n", c.Modified))
    53  	}
    54  	if !c.Added.Empty() {
    55  		bld.WriteString(fmt.Sprintf("- Added Fields:\n%v\n", c.Added))
    56  	}
    57  	if !c.Removed.Empty() {
    58  		bld.WriteString(fmt.Sprintf("- Removed Fields:\n%v\n", c.Removed))
    59  	}
    60  	return bld.String()
    61  }
    62  
    63  // ExcludeFields fields from the compare recursively removes the fields
    64  // from the entire comparison
    65  func (c *Comparison) ExcludeFields(fields *fieldpath.Set) *Comparison {
    66  	if fields == nil || fields.Empty() {
    67  		return c
    68  	}
    69  	c.Removed = c.Removed.RecursiveDifference(fields)
    70  	c.Modified = c.Modified.RecursiveDifference(fields)
    71  	c.Added = c.Added.RecursiveDifference(fields)
    72  	return c
    73  }
    74  
    75  type compareWalker struct {
    76  	lhs     value.Value
    77  	rhs     value.Value
    78  	schema  *schema.Schema
    79  	typeRef schema.TypeRef
    80  
    81  	// Current path that we are comparing
    82  	path fieldpath.Path
    83  
    84  	// Resulting comparison.
    85  	comparison *Comparison
    86  
    87  	// internal housekeeping--don't set when constructing.
    88  	inLeaf bool // Set to true if we're in a "big leaf"--atomic map/list
    89  
    90  	// Allocate only as many walkers as needed for the depth by storing them here.
    91  	spareWalkers *[]*compareWalker
    92  
    93  	allocator value.Allocator
    94  }
    95  
    96  // compare compares stuff.
    97  func (w *compareWalker) compare(prefixFn func() string) (errs ValidationErrors) {
    98  	if w.lhs == nil && w.rhs == nil {
    99  		// check this condidition here instead of everywhere below.
   100  		return errorf("at least one of lhs and rhs must be provided")
   101  	}
   102  	a, ok := w.schema.Resolve(w.typeRef)
   103  	if !ok {
   104  		return errorf("schema error: no type found matching: %v", *w.typeRef.NamedType)
   105  	}
   106  
   107  	alhs := deduceAtom(a, w.lhs)
   108  	arhs := deduceAtom(a, w.rhs)
   109  
   110  	// deduceAtom does not fix the type for nil values
   111  	// nil is a wildcard and will accept whatever form the other operand takes
   112  	if w.rhs == nil {
   113  		errs = append(errs, handleAtom(alhs, w.typeRef, w)...)
   114  	} else if w.lhs == nil || alhs.Equals(&arhs) {
   115  		errs = append(errs, handleAtom(arhs, w.typeRef, w)...)
   116  	} else {
   117  		w2 := *w
   118  		errs = append(errs, handleAtom(alhs, w.typeRef, &w2)...)
   119  		errs = append(errs, handleAtom(arhs, w.typeRef, w)...)
   120  	}
   121  
   122  	if !w.inLeaf {
   123  		if w.lhs == nil {
   124  			w.comparison.Added.Insert(w.path)
   125  		} else if w.rhs == nil {
   126  			w.comparison.Removed.Insert(w.path)
   127  		}
   128  	}
   129  	return errs.WithLazyPrefix(prefixFn)
   130  }
   131  
   132  // doLeaf should be called on leaves before descending into children, if there
   133  // will be a descent. It modifies w.inLeaf.
   134  func (w *compareWalker) doLeaf() {
   135  	if w.inLeaf {
   136  		// We're in a "big leaf", an atomic map or list. Ignore
   137  		// subsequent leaves.
   138  		return
   139  	}
   140  	w.inLeaf = true
   141  
   142  	// We don't recurse into leaf fields for merging.
   143  	if w.lhs == nil {
   144  		w.comparison.Added.Insert(w.path)
   145  	} else if w.rhs == nil {
   146  		w.comparison.Removed.Insert(w.path)
   147  	} else if !value.EqualsUsing(w.allocator, w.rhs, w.lhs) {
   148  		// TODO: Equality is not sufficient for this.
   149  		// Need to implement equality check on the value type.
   150  		w.comparison.Modified.Insert(w.path)
   151  	}
   152  }
   153  
   154  func (w *compareWalker) doScalar(t *schema.Scalar) ValidationErrors {
   155  	// Make sure at least one side is a valid scalar.
   156  	lerrs := validateScalar(t, w.lhs, "lhs: ")
   157  	rerrs := validateScalar(t, w.rhs, "rhs: ")
   158  	if len(lerrs) > 0 && len(rerrs) > 0 {
   159  		return append(lerrs, rerrs...)
   160  	}
   161  
   162  	// All scalars are leaf fields.
   163  	w.doLeaf()
   164  
   165  	return nil
   166  }
   167  
   168  func (w *compareWalker) prepareDescent(pe fieldpath.PathElement, tr schema.TypeRef, cmp *Comparison) *compareWalker {
   169  	if w.spareWalkers == nil {
   170  		// first descent.
   171  		w.spareWalkers = &[]*compareWalker{}
   172  	}
   173  	var w2 *compareWalker
   174  	if n := len(*w.spareWalkers); n > 0 {
   175  		w2, *w.spareWalkers = (*w.spareWalkers)[n-1], (*w.spareWalkers)[:n-1]
   176  	} else {
   177  		w2 = &compareWalker{}
   178  	}
   179  	*w2 = *w
   180  	w2.typeRef = tr
   181  	w2.path = append(w2.path, pe)
   182  	w2.lhs = nil
   183  	w2.rhs = nil
   184  	w2.comparison = cmp
   185  	return w2
   186  }
   187  
   188  func (w *compareWalker) finishDescent(w2 *compareWalker) {
   189  	// if the descent caused a realloc, ensure that we reuse the buffer
   190  	// for the next sibling.
   191  	w.path = w2.path[:len(w2.path)-1]
   192  	*w.spareWalkers = append(*w.spareWalkers, w2)
   193  }
   194  
   195  func (w *compareWalker) derefMap(prefix string, v value.Value) (value.Map, ValidationErrors) {
   196  	if v == nil {
   197  		return nil, nil
   198  	}
   199  	m, err := mapValue(w.allocator, v)
   200  	if err != nil {
   201  		return nil, errorf("%v: %v", prefix, err)
   202  	}
   203  	return m, nil
   204  }
   205  
   206  func (w *compareWalker) visitListItems(t *schema.List, lhs, rhs value.List) (errs ValidationErrors) {
   207  	rLen := 0
   208  	if rhs != nil {
   209  		rLen = rhs.Length()
   210  	}
   211  	lLen := 0
   212  	if lhs != nil {
   213  		lLen = lhs.Length()
   214  	}
   215  
   216  	maxLength := rLen
   217  	if lLen > maxLength {
   218  		maxLength = lLen
   219  	}
   220  	// Contains all the unique PEs between lhs and rhs, exactly once.
   221  	// Order doesn't matter since we're just tracking ownership in a set.
   222  	allPEs := make([]fieldpath.PathElement, 0, maxLength)
   223  
   224  	// Gather all the elements from lhs, indexed by PE, in a list for duplicates.
   225  	lValues := fieldpath.MakePathElementMap(lLen)
   226  	for i := 0; i < lLen; i++ {
   227  		child := lhs.At(i)
   228  		pe, err := listItemToPathElement(w.allocator, w.schema, t, child)
   229  		if err != nil {
   230  			errs = append(errs, errorf("element %v: %v", i, err.Error())...)
   231  			// If we can't construct the path element, we can't
   232  			// even report errors deeper in the schema, so bail on
   233  			// this element.
   234  			continue
   235  		}
   236  
   237  		if v, found := lValues.Get(pe); found {
   238  			list := v.([]value.Value)
   239  			lValues.Insert(pe, append(list, child))
   240  		} else {
   241  			lValues.Insert(pe, []value.Value{child})
   242  			allPEs = append(allPEs, pe)
   243  		}
   244  	}
   245  
   246  	// Gather all the elements from rhs, indexed by PE, in a list for duplicates.
   247  	rValues := fieldpath.MakePathElementMap(rLen)
   248  	for i := 0; i < rLen; i++ {
   249  		rValue := rhs.At(i)
   250  		pe, err := listItemToPathElement(w.allocator, w.schema, t, rValue)
   251  		if err != nil {
   252  			errs = append(errs, errorf("element %v: %v", i, err.Error())...)
   253  			// If we can't construct the path element, we can't
   254  			// even report errors deeper in the schema, so bail on
   255  			// this element.
   256  			continue
   257  		}
   258  		if v, found := rValues.Get(pe); found {
   259  			list := v.([]value.Value)
   260  			rValues.Insert(pe, append(list, rValue))
   261  		} else {
   262  			rValues.Insert(pe, []value.Value{rValue})
   263  			if _, found := lValues.Get(pe); !found {
   264  				allPEs = append(allPEs, pe)
   265  			}
   266  		}
   267  	}
   268  
   269  	for _, pe := range allPEs {
   270  		lList := []value.Value(nil)
   271  		if l, ok := lValues.Get(pe); ok {
   272  			lList = l.([]value.Value)
   273  		}
   274  		rList := []value.Value(nil)
   275  		if l, ok := rValues.Get(pe); ok {
   276  			rList = l.([]value.Value)
   277  		}
   278  
   279  		switch {
   280  		case len(lList) == 0 && len(rList) == 0:
   281  			// We shouldn't be here anyway.
   282  			return
   283  		// Normal use-case:
   284  		// We have no duplicates for this PE, compare items one-to-one.
   285  		case len(lList) <= 1 && len(rList) <= 1:
   286  			lValue := value.Value(nil)
   287  			if len(lList) != 0 {
   288  				lValue = lList[0]
   289  			}
   290  			rValue := value.Value(nil)
   291  			if len(rList) != 0 {
   292  				rValue = rList[0]
   293  			}
   294  			errs = append(errs, w.compareListItem(t, pe, lValue, rValue)...)
   295  		// Duplicates before & after use-case:
   296  		// Compare the duplicates lists as if they were atomic, mark modified if they changed.
   297  		case len(lList) >= 2 && len(rList) >= 2:
   298  			listEqual := func(lList, rList []value.Value) bool {
   299  				if len(lList) != len(rList) {
   300  					return false
   301  				}
   302  				for i := range lList {
   303  					if !value.Equals(lList[i], rList[i]) {
   304  						return false
   305  					}
   306  				}
   307  				return true
   308  			}
   309  			if !listEqual(lList, rList) {
   310  				w.comparison.Modified.Insert(append(w.path, pe))
   311  			}
   312  		// Duplicates before & not anymore use-case:
   313  		// Rcursively add new non-duplicate items, Remove duplicate marker,
   314  		case len(lList) >= 2:
   315  			if len(rList) != 0 {
   316  				errs = append(errs, w.compareListItem(t, pe, nil, rList[0])...)
   317  			}
   318  			w.comparison.Removed.Insert(append(w.path, pe))
   319  		// New duplicates use-case:
   320  		// Recursively remove old non-duplicate items, add duplicate marker.
   321  		case len(rList) >= 2:
   322  			if len(lList) != 0 {
   323  				errs = append(errs, w.compareListItem(t, pe, lList[0], nil)...)
   324  			}
   325  			w.comparison.Added.Insert(append(w.path, pe))
   326  		}
   327  	}
   328  
   329  	return
   330  }
   331  
   332  func (w *compareWalker) indexListPathElements(t *schema.List, list value.List) ([]fieldpath.PathElement, fieldpath.PathElementValueMap, ValidationErrors) {
   333  	var errs ValidationErrors
   334  	length := 0
   335  	if list != nil {
   336  		length = list.Length()
   337  	}
   338  	observed := fieldpath.MakePathElementValueMap(length)
   339  	pes := make([]fieldpath.PathElement, 0, length)
   340  	for i := 0; i < length; i++ {
   341  		child := list.At(i)
   342  		pe, err := listItemToPathElement(w.allocator, w.schema, t, child)
   343  		if err != nil {
   344  			errs = append(errs, errorf("element %v: %v", i, err.Error())...)
   345  			// If we can't construct the path element, we can't
   346  			// even report errors deeper in the schema, so bail on
   347  			// this element.
   348  			continue
   349  		}
   350  		// Ignore repeated occurences of `pe`.
   351  		if _, found := observed.Get(pe); found {
   352  			continue
   353  		}
   354  		observed.Insert(pe, child)
   355  		pes = append(pes, pe)
   356  	}
   357  	return pes, observed, errs
   358  }
   359  
   360  func (w *compareWalker) compareListItem(t *schema.List, pe fieldpath.PathElement, lChild, rChild value.Value) ValidationErrors {
   361  	w2 := w.prepareDescent(pe, t.ElementType, w.comparison)
   362  	w2.lhs = lChild
   363  	w2.rhs = rChild
   364  	errs := w2.compare(pe.String)
   365  	w.finishDescent(w2)
   366  	return errs
   367  }
   368  
   369  func (w *compareWalker) derefList(prefix string, v value.Value) (value.List, ValidationErrors) {
   370  	if v == nil {
   371  		return nil, nil
   372  	}
   373  	l, err := listValue(w.allocator, v)
   374  	if err != nil {
   375  		return nil, errorf("%v: %v", prefix, err)
   376  	}
   377  	return l, nil
   378  }
   379  
   380  func (w *compareWalker) doList(t *schema.List) (errs ValidationErrors) {
   381  	lhs, _ := w.derefList("lhs: ", w.lhs)
   382  	if lhs != nil {
   383  		defer w.allocator.Free(lhs)
   384  	}
   385  	rhs, _ := w.derefList("rhs: ", w.rhs)
   386  	if rhs != nil {
   387  		defer w.allocator.Free(rhs)
   388  	}
   389  
   390  	// If both lhs and rhs are empty/null, treat it as a
   391  	// leaf: this helps preserve the empty/null
   392  	// distinction.
   393  	emptyPromoteToLeaf := (lhs == nil || lhs.Length() == 0) && (rhs == nil || rhs.Length() == 0)
   394  
   395  	if t.ElementRelationship == schema.Atomic || emptyPromoteToLeaf {
   396  		w.doLeaf()
   397  		return nil
   398  	}
   399  
   400  	if lhs == nil && rhs == nil {
   401  		return nil
   402  	}
   403  
   404  	errs = w.visitListItems(t, lhs, rhs)
   405  
   406  	return errs
   407  }
   408  
   409  func (w *compareWalker) visitMapItem(t *schema.Map, out map[string]interface{}, key string, lhs, rhs value.Value) (errs ValidationErrors) {
   410  	fieldType := t.ElementType
   411  	if sf, ok := t.FindField(key); ok {
   412  		fieldType = sf.Type
   413  	}
   414  	pe := fieldpath.PathElement{FieldName: &key}
   415  	w2 := w.prepareDescent(pe, fieldType, w.comparison)
   416  	w2.lhs = lhs
   417  	w2.rhs = rhs
   418  	errs = append(errs, w2.compare(pe.String)...)
   419  	w.finishDescent(w2)
   420  	return errs
   421  }
   422  
   423  func (w *compareWalker) visitMapItems(t *schema.Map, lhs, rhs value.Map) (errs ValidationErrors) {
   424  	out := map[string]interface{}{}
   425  
   426  	value.MapZipUsing(w.allocator, lhs, rhs, value.Unordered, func(key string, lhsValue, rhsValue value.Value) bool {
   427  		errs = append(errs, w.visitMapItem(t, out, key, lhsValue, rhsValue)...)
   428  		return true
   429  	})
   430  
   431  	return errs
   432  }
   433  
   434  func (w *compareWalker) doMap(t *schema.Map) (errs ValidationErrors) {
   435  	lhs, _ := w.derefMap("lhs: ", w.lhs)
   436  	if lhs != nil {
   437  		defer w.allocator.Free(lhs)
   438  	}
   439  	rhs, _ := w.derefMap("rhs: ", w.rhs)
   440  	if rhs != nil {
   441  		defer w.allocator.Free(rhs)
   442  	}
   443  	// If both lhs and rhs are empty/null, treat it as a
   444  	// leaf: this helps preserve the empty/null
   445  	// distinction.
   446  	emptyPromoteToLeaf := (lhs == nil || lhs.Empty()) && (rhs == nil || rhs.Empty())
   447  
   448  	if t.ElementRelationship == schema.Atomic || emptyPromoteToLeaf {
   449  		w.doLeaf()
   450  		return nil
   451  	}
   452  
   453  	if lhs == nil && rhs == nil {
   454  		return nil
   455  	}
   456  
   457  	errs = append(errs, w.visitMapItems(t, lhs, rhs)...)
   458  
   459  	return errs
   460  }
   461
View as plain text