Source file src/k8s.io/apimachinery/pkg/util/strategicpatch/patch.go

Documentation: k8s.io/apimachinery/pkg/util/strategicpatch

     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 strategicpatch
    18  
    19  import (
    20  	"fmt"
    21  	"reflect"
    22  	"sort"
    23  	"strings"
    24  
    25  	"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
    26  	"k8s.io/apimachinery/pkg/util/json"
    27  	"k8s.io/apimachinery/pkg/util/mergepatch"
    28  )
    29  
    30  // An alternate implementation of JSON Merge Patch
    31  // (https://tools.ietf.org/html/rfc7386) which supports the ability to annotate
    32  // certain fields with metadata that indicates whether the elements of JSON
    33  // lists should be merged or replaced.
    34  //
    35  // For more information, see the PATCH section of docs/devel/api-conventions.md.
    36  //
    37  // Some of the content of this package was borrowed with minor adaptations from
    38  // evanphx/json-patch and openshift/origin.
    39  
    40  const (
    41  	directiveMarker  = "$patch"
    42  	deleteDirective  = "delete"
    43  	replaceDirective = "replace"
    44  	mergeDirective   = "merge"
    45  
    46  	retainKeysStrategy = "retainKeys"
    47  
    48  	deleteFromPrimitiveListDirectivePrefix = "$deleteFromPrimitiveList"
    49  	retainKeysDirective                    = "$" + retainKeysStrategy
    50  	setElementOrderDirectivePrefix         = "$setElementOrder"
    51  )
    52  
    53  // JSONMap is a representations of JSON object encoded as map[string]interface{}
    54  // where the children can be either map[string]interface{}, []interface{} or
    55  // primitive type).
    56  // Operating on JSONMap representation is much faster as it doesn't require any
    57  // json marshaling and/or unmarshaling operations.
    58  type JSONMap map[string]interface{}
    59  
    60  type DiffOptions struct {
    61  	// SetElementOrder determines whether we generate the $setElementOrder parallel list.
    62  	SetElementOrder bool
    63  	// IgnoreChangesAndAdditions indicates if we keep the changes and additions in the patch.
    64  	IgnoreChangesAndAdditions bool
    65  	// IgnoreDeletions indicates if we keep the deletions in the patch.
    66  	IgnoreDeletions bool
    67  	// We introduce a new value retainKeys for patchStrategy.
    68  	// It indicates that all fields needing to be preserved must be
    69  	// present in the `retainKeys` list.
    70  	// And the fields that are present will be merged with live object.
    71  	// All the missing fields will be cleared when patching.
    72  	BuildRetainKeysDirective bool
    73  }
    74  
    75  type MergeOptions struct {
    76  	// MergeParallelList indicates if we are merging the parallel list.
    77  	// We don't merge parallel list when calling mergeMap() in CreateThreeWayMergePatch()
    78  	// which is called client-side.
    79  	// We merge parallel list iff when calling mergeMap() in StrategicMergeMapPatch()
    80  	// which is called server-side
    81  	MergeParallelList bool
    82  	// IgnoreUnmatchedNulls indicates if we should process the unmatched nulls.
    83  	IgnoreUnmatchedNulls bool
    84  }
    85  
    86  // The following code is adapted from github.com/openshift/origin/pkg/util/jsonmerge.
    87  // Instead of defining a Delta that holds an original, a patch and a set of preconditions,
    88  // the reconcile method accepts a set of preconditions as an argument.
    89  
    90  // CreateTwoWayMergePatch creates a patch that can be passed to StrategicMergePatch from an original
    91  // document and a modified document, which are passed to the method as json encoded content. It will
    92  // return a patch that yields the modified document when applied to the original document, or an error
    93  // if either of the two documents is invalid.
    94  func CreateTwoWayMergePatch(original, modified []byte, dataStruct interface{}, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
    95  	schema, err := NewPatchMetaFromStruct(dataStruct)
    96  	if err != nil {
    97  		return nil, err
    98  	}
    99  
   100  	return CreateTwoWayMergePatchUsingLookupPatchMeta(original, modified, schema, fns...)
   101  }
   102  
   103  func CreateTwoWayMergePatchUsingLookupPatchMeta(
   104  	original, modified []byte, schema LookupPatchMeta, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
   105  	originalMap := map[string]interface{}{}
   106  	if len(original) > 0 {
   107  		if err := json.Unmarshal(original, &originalMap); err != nil {
   108  			return nil, mergepatch.ErrBadJSONDoc
   109  		}
   110  	}
   111  
   112  	modifiedMap := map[string]interface{}{}
   113  	if len(modified) > 0 {
   114  		if err := json.Unmarshal(modified, &modifiedMap); err != nil {
   115  			return nil, mergepatch.ErrBadJSONDoc
   116  		}
   117  	}
   118  
   119  	patchMap, err := CreateTwoWayMergeMapPatchUsingLookupPatchMeta(originalMap, modifiedMap, schema, fns...)
   120  	if err != nil {
   121  		return nil, err
   122  	}
   123  
   124  	return json.Marshal(patchMap)
   125  }
   126  
   127  // CreateTwoWayMergeMapPatch creates a patch from an original and modified JSON objects,
   128  // encoded JSONMap.
   129  // The serialized version of the map can then be passed to StrategicMergeMapPatch.
   130  func CreateTwoWayMergeMapPatch(original, modified JSONMap, dataStruct interface{}, fns ...mergepatch.PreconditionFunc) (JSONMap, error) {
   131  	schema, err := NewPatchMetaFromStruct(dataStruct)
   132  	if err != nil {
   133  		return nil, err
   134  	}
   135  
   136  	return CreateTwoWayMergeMapPatchUsingLookupPatchMeta(original, modified, schema, fns...)
   137  }
   138  
   139  func CreateTwoWayMergeMapPatchUsingLookupPatchMeta(original, modified JSONMap, schema LookupPatchMeta, fns ...mergepatch.PreconditionFunc) (JSONMap, error) {
   140  	diffOptions := DiffOptions{
   141  		SetElementOrder: true,
   142  	}
   143  	patchMap, err := diffMaps(original, modified, schema, diffOptions)
   144  	if err != nil {
   145  		return nil, err
   146  	}
   147  
   148  	// Apply the preconditions to the patch, and return an error if any of them fail.
   149  	for _, fn := range fns {
   150  		if !fn(patchMap) {
   151  			return nil, mergepatch.NewErrPreconditionFailed(patchMap)
   152  		}
   153  	}
   154  
   155  	return patchMap, nil
   156  }
   157  
   158  // Returns a (recursive) strategic merge patch that yields modified when applied to original.
   159  // Including:
   160  // - Adding fields to the patch present in modified, missing from original
   161  // - Setting fields to the patch present in modified and original with different values
   162  // - Delete fields present in original, missing from modified through
   163  // - IFF map field - set to nil in patch
   164  // - IFF list of maps && merge strategy - use deleteDirective for the elements
   165  // - IFF list of primitives && merge strategy - use parallel deletion list
   166  // - IFF list of maps or primitives with replace strategy (default) - set patch value to the value in modified
   167  // - Build $retainKeys directive for fields with retainKeys patch strategy
   168  func diffMaps(original, modified map[string]interface{}, schema LookupPatchMeta, diffOptions DiffOptions) (map[string]interface{}, error) {
   169  	patch := map[string]interface{}{}
   170  
   171  	// This will be used to build the $retainKeys directive sent in the patch
   172  	retainKeysList := make([]interface{}, 0, len(modified))
   173  
   174  	// Compare each value in the modified map against the value in the original map
   175  	for key, modifiedValue := range modified {
   176  		// Get the underlying type for pointers
   177  		if diffOptions.BuildRetainKeysDirective && modifiedValue != nil {
   178  			retainKeysList = append(retainKeysList, key)
   179  		}
   180  
   181  		originalValue, ok := original[key]
   182  		if !ok {
   183  			// Key was added, so add to patch
   184  			if !diffOptions.IgnoreChangesAndAdditions {
   185  				patch[key] = modifiedValue
   186  			}
   187  			continue
   188  		}
   189  
   190  		// The patch may have a patch directive
   191  		// TODO: figure out if we need this. This shouldn't be needed by apply. When would the original map have patch directives in it?
   192  		foundDirectiveMarker, err := handleDirectiveMarker(key, originalValue, modifiedValue, patch)
   193  		if err != nil {
   194  			return nil, err
   195  		}
   196  		if foundDirectiveMarker {
   197  			continue
   198  		}
   199  
   200  		if reflect.TypeOf(originalValue) != reflect.TypeOf(modifiedValue) {
   201  			// Types have changed, so add to patch
   202  			if !diffOptions.IgnoreChangesAndAdditions {
   203  				patch[key] = modifiedValue
   204  			}
   205  			continue
   206  		}
   207  
   208  		// Types are the same, so compare values
   209  		switch originalValueTyped := originalValue.(type) {
   210  		case map[string]interface{}:
   211  			modifiedValueTyped := modifiedValue.(map[string]interface{})
   212  			err = handleMapDiff(key, originalValueTyped, modifiedValueTyped, patch, schema, diffOptions)
   213  		case []interface{}:
   214  			modifiedValueTyped := modifiedValue.([]interface{})
   215  			err = handleSliceDiff(key, originalValueTyped, modifiedValueTyped, patch, schema, diffOptions)
   216  		default:
   217  			replacePatchFieldIfNotEqual(key, originalValue, modifiedValue, patch, diffOptions)
   218  		}
   219  		if err != nil {
   220  			return nil, err
   221  		}
   222  	}
   223  
   224  	updatePatchIfMissing(original, modified, patch, diffOptions)
   225  	// Insert the retainKeysList iff there are values present in the retainKeysList and
   226  	// either of the following is true:
   227  	// - the patch is not empty
   228  	// - there are additional field in original that need to be cleared
   229  	if len(retainKeysList) > 0 &&
   230  		(len(patch) > 0 || hasAdditionalNewField(original, modified)) {
   231  		patch[retainKeysDirective] = sortScalars(retainKeysList)
   232  	}
   233  	return patch, nil
   234  }
   235  
   236  // handleDirectiveMarker handles how to diff directive marker between 2 objects
   237  func handleDirectiveMarker(key string, originalValue, modifiedValue interface{}, patch map[string]interface{}) (bool, error) {
   238  	if key == directiveMarker {
   239  		originalString, ok := originalValue.(string)
   240  		if !ok {
   241  			return false, fmt.Errorf("invalid value for special key: %s", directiveMarker)
   242  		}
   243  		modifiedString, ok := modifiedValue.(string)
   244  		if !ok {
   245  			return false, fmt.Errorf("invalid value for special key: %s", directiveMarker)
   246  		}
   247  		if modifiedString != originalString {
   248  			patch[directiveMarker] = modifiedValue
   249  		}
   250  		return true, nil
   251  	}
   252  	return false, nil
   253  }
   254  
   255  // handleMapDiff diff between 2 maps `originalValueTyped` and `modifiedValue`,
   256  // puts the diff in the `patch` associated with `key`
   257  // key is the key associated with originalValue and modifiedValue.
   258  // originalValue, modifiedValue are the old and new value respectively.They are both maps
   259  // patch is the patch map that contains key and the updated value, and it is the parent of originalValue, modifiedValue
   260  // diffOptions contains multiple options to control how we do the diff.
   261  func handleMapDiff(key string, originalValue, modifiedValue, patch map[string]interface{},
   262  	schema LookupPatchMeta, diffOptions DiffOptions) error {
   263  	subschema, patchMeta, err := schema.LookupPatchMetadataForStruct(key)
   264  
   265  	if err != nil {
   266  		// We couldn't look up metadata for the field
   267  		// If the values are identical, this doesn't matter, no patch is needed
   268  		if reflect.DeepEqual(originalValue, modifiedValue) {
   269  			return nil
   270  		}
   271  		// Otherwise, return the error
   272  		return err
   273  	}
   274  	retainKeys, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
   275  	if err != nil {
   276  		return err
   277  	}
   278  	diffOptions.BuildRetainKeysDirective = retainKeys
   279  	switch patchStrategy {
   280  	// The patch strategic from metadata tells us to replace the entire object instead of diffing it
   281  	case replaceDirective:
   282  		if !diffOptions.IgnoreChangesAndAdditions {
   283  			patch[key] = modifiedValue
   284  		}
   285  	default:
   286  		patchValue, err := diffMaps(originalValue, modifiedValue, subschema, diffOptions)
   287  		if err != nil {
   288  			return err
   289  		}
   290  		// Maps were not identical, use provided patch value
   291  		if len(patchValue) > 0 {
   292  			patch[key] = patchValue
   293  		}
   294  	}
   295  	return nil
   296  }
   297  
   298  // handleSliceDiff diff between 2 slices `originalValueTyped` and `modifiedValue`,
   299  // puts the diff in the `patch` associated with `key`
   300  // key is the key associated with originalValue and modifiedValue.
   301  // originalValue, modifiedValue are the old and new value respectively.They are both slices
   302  // patch is the patch map that contains key and the updated value, and it is the parent of originalValue, modifiedValue
   303  // diffOptions contains multiple options to control how we do the diff.
   304  func handleSliceDiff(key string, originalValue, modifiedValue []interface{}, patch map[string]interface{},
   305  	schema LookupPatchMeta, diffOptions DiffOptions) error {
   306  	subschema, patchMeta, err := schema.LookupPatchMetadataForSlice(key)
   307  	if err != nil {
   308  		// We couldn't look up metadata for the field
   309  		// If the values are identical, this doesn't matter, no patch is needed
   310  		if reflect.DeepEqual(originalValue, modifiedValue) {
   311  			return nil
   312  		}
   313  		// Otherwise, return the error
   314  		return err
   315  	}
   316  	retainKeys, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
   317  	if err != nil {
   318  		return err
   319  	}
   320  	switch patchStrategy {
   321  	// Merge the 2 slices using mergePatchKey
   322  	case mergeDirective:
   323  		diffOptions.BuildRetainKeysDirective = retainKeys
   324  		addList, deletionList, setOrderList, err := diffLists(originalValue, modifiedValue, subschema, patchMeta.GetPatchMergeKey(), diffOptions)
   325  		if err != nil {
   326  			return err
   327  		}
   328  		if len(addList) > 0 {
   329  			patch[key] = addList
   330  		}
   331  		// generate a parallel list for deletion
   332  		if len(deletionList) > 0 {
   333  			parallelDeletionListKey := fmt.Sprintf("%s/%s", deleteFromPrimitiveListDirectivePrefix, key)
   334  			patch[parallelDeletionListKey] = deletionList
   335  		}
   336  		if len(setOrderList) > 0 {
   337  			parallelSetOrderListKey := fmt.Sprintf("%s/%s", setElementOrderDirectivePrefix, key)
   338  			patch[parallelSetOrderListKey] = setOrderList
   339  		}
   340  	default:
   341  		replacePatchFieldIfNotEqual(key, originalValue, modifiedValue, patch, diffOptions)
   342  	}
   343  	return nil
   344  }
   345  
   346  // replacePatchFieldIfNotEqual updates the patch if original and modified are not deep equal
   347  // if diffOptions.IgnoreChangesAndAdditions is false.
   348  // original is the old value, maybe either the live cluster object or the last applied configuration
   349  // modified is the new value, is always the users new config
   350  func replacePatchFieldIfNotEqual(key string, original, modified interface{},
   351  	patch map[string]interface{}, diffOptions DiffOptions) {
   352  	if diffOptions.IgnoreChangesAndAdditions {
   353  		// Ignoring changes - do nothing
   354  		return
   355  	}
   356  	if reflect.DeepEqual(original, modified) {
   357  		// Contents are identical - do nothing
   358  		return
   359  	}
   360  	// Create a patch to replace the old value with the new one
   361  	patch[key] = modified
   362  }
   363  
   364  // updatePatchIfMissing iterates over `original` when ignoreDeletions is false.
   365  // Clear the field whose key is not present in `modified`.
   366  // original is the old value, maybe either the live cluster object or the last applied configuration
   367  // modified is the new value, is always the users new config
   368  func updatePatchIfMissing(original, modified, patch map[string]interface{}, diffOptions DiffOptions) {
   369  	if diffOptions.IgnoreDeletions {
   370  		// Ignoring deletion - do nothing
   371  		return
   372  	}
   373  	// Add nils for deleted values
   374  	for key := range original {
   375  		if _, found := modified[key]; !found {
   376  			patch[key] = nil
   377  		}
   378  	}
   379  }
   380  
   381  // validateMergeKeyInLists checks if each map in the list has the mentryerge key.
   382  func validateMergeKeyInLists(mergeKey string, lists ...[]interface{}) error {
   383  	for _, list := range lists {
   384  		for _, item := range list {
   385  			m, ok := item.(map[string]interface{})
   386  			if !ok {
   387  				return mergepatch.ErrBadArgType(m, item)
   388  			}
   389  			if _, ok = m[mergeKey]; !ok {
   390  				return mergepatch.ErrNoMergeKey(m, mergeKey)
   391  			}
   392  		}
   393  	}
   394  	return nil
   395  }
   396  
   397  // normalizeElementOrder sort `patch` list by `patchOrder` and sort `serverOnly` list by `serverOrder`.
   398  // Then it merges the 2 sorted lists.
   399  // It guarantee the relative order in the patch list and in the serverOnly list is kept.
   400  // `patch` is a list of items in the patch, and `serverOnly` is a list of items in the live object.
   401  // `patchOrder` is the order we want `patch` list to have and
   402  // `serverOrder` is the order we want `serverOnly` list to have.
   403  // kind is the kind of each item in the lists `patch` and `serverOnly`.
   404  func normalizeElementOrder(patch, serverOnly, patchOrder, serverOrder []interface{}, mergeKey string, kind reflect.Kind) ([]interface{}, error) {
   405  	patch, err := normalizeSliceOrder(patch, patchOrder, mergeKey, kind)
   406  	if err != nil {
   407  		return nil, err
   408  	}
   409  	serverOnly, err = normalizeSliceOrder(serverOnly, serverOrder, mergeKey, kind)
   410  	if err != nil {
   411  		return nil, err
   412  	}
   413  	all := mergeSortedSlice(serverOnly, patch, serverOrder, mergeKey, kind)
   414  
   415  	return all, nil
   416  }
   417  
   418  // mergeSortedSlice merges the 2 sorted lists by serverOrder with best effort.
   419  // It will insert each item in `left` list to `right` list. In most cases, the 2 lists will be interleaved.
   420  // The relative order of left and right are guaranteed to be kept.
   421  // They have higher precedence than the order in the live list.
   422  // The place for a item in `left` is found by:
   423  // scan from the place of last insertion in `right` to the end of `right`,
   424  // the place is before the first item that is greater than the item we want to insert.
   425  // example usage: using server-only items as left and patch items as right. We insert server-only items
   426  // to patch list. We use the order of live object as record for comparison.
   427  func mergeSortedSlice(left, right, serverOrder []interface{}, mergeKey string, kind reflect.Kind) []interface{} {
   428  	// Returns if l is less than r, and if both have been found.
   429  	// If l and r both present and l is in front of r, l is less than r.
   430  	less := func(l, r interface{}) (bool, bool) {
   431  		li := index(serverOrder, l, mergeKey, kind)
   432  		ri := index(serverOrder, r, mergeKey, kind)
   433  		if li >= 0 && ri >= 0 {
   434  			return li < ri, true
   435  		} else {
   436  			return false, false
   437  		}
   438  	}
   439  
   440  	// left and right should be non-overlapping.
   441  	size := len(left) + len(right)
   442  	i, j := 0, 0
   443  	s := make([]interface{}, size, size)
   444  
   445  	for k := 0; k < size; k++ {
   446  		if i >= len(left) && j < len(right) {
   447  			// have items left in `right` list
   448  			s[k] = right[j]
   449  			j++
   450  		} else if j >= len(right) && i < len(left) {
   451  			// have items left in `left` list
   452  			s[k] = left[i]
   453  			i++
   454  		} else {
   455  			// compare them if i and j are both in bound
   456  			less, foundBoth := less(left[i], right[j])
   457  			if foundBoth && less {
   458  				s[k] = left[i]
   459  				i++
   460  			} else {
   461  				s[k] = right[j]
   462  				j++
   463  			}
   464  		}
   465  	}
   466  	return s
   467  }
   468  
   469  // index returns the index of the item in the given items, or -1 if it doesn't exist
   470  // l must NOT be a slice of slices, this should be checked before calling.
   471  func index(l []interface{}, valToLookUp interface{}, mergeKey string, kind reflect.Kind) int {
   472  	var getValFn func(interface{}) interface{}
   473  	// Get the correct `getValFn` based on item `kind`.
   474  	// It should return the value of merge key for maps and
   475  	// return the item for other kinds.
   476  	switch kind {
   477  	case reflect.Map:
   478  		getValFn = func(item interface{}) interface{} {
   479  			typedItem, ok := item.(map[string]interface{})
   480  			if !ok {
   481  				return nil
   482  			}
   483  			val := typedItem[mergeKey]
   484  			return val
   485  		}
   486  	default:
   487  		getValFn = func(item interface{}) interface{} {
   488  			return item
   489  		}
   490  	}
   491  
   492  	for i, v := range l {
   493  		if getValFn(valToLookUp) == getValFn(v) {
   494  			return i
   495  		}
   496  	}
   497  	return -1
   498  }
   499  
   500  // extractToDeleteItems takes a list and
   501  // returns 2 lists: one contains items that should be kept and the other contains items to be deleted.
   502  func extractToDeleteItems(l []interface{}) ([]interface{}, []interface{}, error) {
   503  	var nonDelete, toDelete []interface{}
   504  	for _, v := range l {
   505  		m, ok := v.(map[string]interface{})
   506  		if !ok {
   507  			return nil, nil, mergepatch.ErrBadArgType(m, v)
   508  		}
   509  
   510  		directive, foundDirective := m[directiveMarker]
   511  		if foundDirective && directive == deleteDirective {
   512  			toDelete = append(toDelete, v)
   513  		} else {
   514  			nonDelete = append(nonDelete, v)
   515  		}
   516  	}
   517  	return nonDelete, toDelete, nil
   518  }
   519  
   520  // normalizeSliceOrder sort `toSort` list by `order`
   521  func normalizeSliceOrder(toSort, order []interface{}, mergeKey string, kind reflect.Kind) ([]interface{}, error) {
   522  	var toDelete []interface{}
   523  	if kind == reflect.Map {
   524  		// make sure each item in toSort, order has merge key
   525  		err := validateMergeKeyInLists(mergeKey, toSort, order)
   526  		if err != nil {
   527  			return nil, err
   528  		}
   529  		toSort, toDelete, err = extractToDeleteItems(toSort)
   530  		if err != nil {
   531  			return nil, err
   532  		}
   533  	}
   534  
   535  	sort.SliceStable(toSort, func(i, j int) bool {
   536  		if ii := index(order, toSort[i], mergeKey, kind); ii >= 0 {
   537  			if ij := index(order, toSort[j], mergeKey, kind); ij >= 0 {
   538  				return ii < ij
   539  			}
   540  		}
   541  		return true
   542  	})
   543  	toSort = append(toSort, toDelete...)
   544  	return toSort, nil
   545  }
   546  
   547  // Returns a (recursive) strategic merge patch, a parallel deletion list if necessary and
   548  // another list to set the order of the list
   549  // Only list of primitives with merge strategy will generate a parallel deletion list.
   550  // These two lists should yield modified when applied to original, for lists with merge semantics.
   551  func diffLists(original, modified []interface{}, schema LookupPatchMeta, mergeKey string, diffOptions DiffOptions) ([]interface{}, []interface{}, []interface{}, error) {
   552  	if len(original) == 0 {
   553  		// Both slices are empty - do nothing
   554  		if len(modified) == 0 || diffOptions.IgnoreChangesAndAdditions {
   555  			return nil, nil, nil, nil
   556  		}
   557  
   558  		// Old slice was empty - add all elements from the new slice
   559  		return modified, nil, nil, nil
   560  	}
   561  
   562  	elementType, err := sliceElementType(original, modified)
   563  	if err != nil {
   564  		return nil, nil, nil, err
   565  	}
   566  
   567  	var patchList, deleteList, setOrderList []interface{}
   568  	kind := elementType.Kind()
   569  	switch kind {
   570  	case reflect.Map:
   571  		patchList, deleteList, err = diffListsOfMaps(original, modified, schema, mergeKey, diffOptions)
   572  		if err != nil {
   573  			return nil, nil, nil, err
   574  		}
   575  		patchList, err = normalizeSliceOrder(patchList, modified, mergeKey, kind)
   576  		if err != nil {
   577  			return nil, nil, nil, err
   578  		}
   579  		orderSame, err := isOrderSame(original, modified, mergeKey)
   580  		if err != nil {
   581  			return nil, nil, nil, err
   582  		}
   583  		// append the deletions to the end of the patch list.
   584  		patchList = append(patchList, deleteList...)
   585  		deleteList = nil
   586  		// generate the setElementOrder list when there are content changes or order changes
   587  		if diffOptions.SetElementOrder &&
   588  			((!diffOptions.IgnoreChangesAndAdditions && (len(patchList) > 0 || !orderSame)) ||
   589  				(!diffOptions.IgnoreDeletions && len(patchList) > 0)) {
   590  			// Generate a list of maps that each item contains only the merge key.
   591  			setOrderList = make([]interface{}, len(modified))
   592  			for i, v := range modified {
   593  				typedV := v.(map[string]interface{})
   594  				setOrderList[i] = map[string]interface{}{
   595  					mergeKey: typedV[mergeKey],
   596  				}
   597  			}
   598  		}
   599  	case reflect.Slice:
   600  		// Lists of Lists are not permitted by the api
   601  		return nil, nil, nil, mergepatch.ErrNoListOfLists
   602  	default:
   603  		patchList, deleteList, err = diffListsOfScalars(original, modified, diffOptions)
   604  		if err != nil {
   605  			return nil, nil, nil, err
   606  		}
   607  		patchList, err = normalizeSliceOrder(patchList, modified, mergeKey, kind)
   608  		// generate the setElementOrder list when there are content changes or order changes
   609  		if diffOptions.SetElementOrder && ((!diffOptions.IgnoreDeletions && len(deleteList) > 0) ||
   610  			(!diffOptions.IgnoreChangesAndAdditions && !reflect.DeepEqual(original, modified))) {
   611  			setOrderList = modified
   612  		}
   613  	}
   614  	return patchList, deleteList, setOrderList, err
   615  }
   616  
   617  // isOrderSame checks if the order in a list has changed
   618  func isOrderSame(original, modified []interface{}, mergeKey string) (bool, error) {
   619  	if len(original) != len(modified) {
   620  		return false, nil
   621  	}
   622  	for i, modifiedItem := range modified {
   623  		equal, err := mergeKeyValueEqual(original[i], modifiedItem, mergeKey)
   624  		if err != nil || !equal {
   625  			return equal, err
   626  		}
   627  	}
   628  	return true, nil
   629  }
   630  
   631  // diffListsOfScalars returns 2 lists, the first one is addList and the second one is deletionList.
   632  // Argument diffOptions.IgnoreChangesAndAdditions controls if calculate addList. true means not calculate.
   633  // Argument diffOptions.IgnoreDeletions controls if calculate deletionList. true means not calculate.
   634  // original may be changed, but modified is guaranteed to not be changed
   635  func diffListsOfScalars(original, modified []interface{}, diffOptions DiffOptions) ([]interface{}, []interface{}, error) {
   636  	modifiedCopy := make([]interface{}, len(modified))
   637  	copy(modifiedCopy, modified)
   638  	// Sort the scalars for easier calculating the diff
   639  	originalScalars := sortScalars(original)
   640  	modifiedScalars := sortScalars(modifiedCopy)
   641  
   642  	originalIndex, modifiedIndex := 0, 0
   643  	addList := []interface{}{}
   644  	deletionList := []interface{}{}
   645  
   646  	for {
   647  		originalInBounds := originalIndex < len(originalScalars)
   648  		modifiedInBounds := modifiedIndex < len(modifiedScalars)
   649  		if !originalInBounds && !modifiedInBounds {
   650  			break
   651  		}
   652  		// we need to compare the string representation of the scalar,
   653  		// because the scalar is an interface which doesn't support either < or >
   654  		// And that's how func sortScalars compare scalars.
   655  		var originalString, modifiedString string
   656  		var originalValue, modifiedValue interface{}
   657  		if originalInBounds {
   658  			originalValue = originalScalars[originalIndex]
   659  			originalString = fmt.Sprintf("%v", originalValue)
   660  		}
   661  		if modifiedInBounds {
   662  			modifiedValue = modifiedScalars[modifiedIndex]
   663  			modifiedString = fmt.Sprintf("%v", modifiedValue)
   664  		}
   665  
   666  		originalV, modifiedV := compareListValuesAtIndex(originalInBounds, modifiedInBounds, originalString, modifiedString)
   667  		switch {
   668  		case originalV == nil && modifiedV == nil:
   669  			originalIndex++
   670  			modifiedIndex++
   671  		case originalV != nil && modifiedV == nil:
   672  			if !diffOptions.IgnoreDeletions {
   673  				deletionList = append(deletionList, originalValue)
   674  			}
   675  			originalIndex++
   676  		case originalV == nil && modifiedV != nil:
   677  			if !diffOptions.IgnoreChangesAndAdditions {
   678  				addList = append(addList, modifiedValue)
   679  			}
   680  			modifiedIndex++
   681  		default:
   682  			return nil, nil, fmt.Errorf("Unexpected returned value from compareListValuesAtIndex: %v and %v", originalV, modifiedV)
   683  		}
   684  	}
   685  
   686  	return addList, deduplicateScalars(deletionList), nil
   687  }
   688  
   689  // If first return value is non-nil, list1 contains an element not present in list2
   690  // If second return value is non-nil, list2 contains an element not present in list1
   691  func compareListValuesAtIndex(list1Inbounds, list2Inbounds bool, list1Value, list2Value string) (interface{}, interface{}) {
   692  	bothInBounds := list1Inbounds && list2Inbounds
   693  	switch {
   694  	// scalars are identical
   695  	case bothInBounds && list1Value == list2Value:
   696  		return nil, nil
   697  	// only list2 is in bound
   698  	case !list1Inbounds:
   699  		fallthrough
   700  	// list2 has additional scalar
   701  	case bothInBounds && list1Value > list2Value:
   702  		return nil, list2Value
   703  	// only original is in bound
   704  	case !list2Inbounds:
   705  		fallthrough
   706  	// original has additional scalar
   707  	case bothInBounds && list1Value < list2Value:
   708  		return list1Value, nil
   709  	default:
   710  		return nil, nil
   711  	}
   712  }
   713  
   714  // diffListsOfMaps takes a pair of lists and
   715  // returns a (recursive) strategic merge patch list contains additions and changes and
   716  // a deletion list contains deletions
   717  func diffListsOfMaps(original, modified []interface{}, schema LookupPatchMeta, mergeKey string, diffOptions DiffOptions) ([]interface{}, []interface{}, error) {
   718  	patch := make([]interface{}, 0, len(modified))
   719  	deletionList := make([]interface{}, 0, len(original))
   720  
   721  	originalSorted, err := sortMergeListsByNameArray(original, schema, mergeKey, false)
   722  	if err != nil {
   723  		return nil, nil, err
   724  	}
   725  	modifiedSorted, err := sortMergeListsByNameArray(modified, schema, mergeKey, false)
   726  	if err != nil {
   727  		return nil, nil, err
   728  	}
   729  
   730  	originalIndex, modifiedIndex := 0, 0
   731  	for {
   732  		originalInBounds := originalIndex < len(originalSorted)
   733  		modifiedInBounds := modifiedIndex < len(modifiedSorted)
   734  		bothInBounds := originalInBounds && modifiedInBounds
   735  		if !originalInBounds && !modifiedInBounds {
   736  			break
   737  		}
   738  
   739  		var originalElementMergeKeyValueString, modifiedElementMergeKeyValueString string
   740  		var originalElementMergeKeyValue, modifiedElementMergeKeyValue interface{}
   741  		var originalElement, modifiedElement map[string]interface{}
   742  		if originalInBounds {
   743  			originalElement, originalElementMergeKeyValue, err = getMapAndMergeKeyValueByIndex(originalIndex, mergeKey, originalSorted)
   744  			if err != nil {
   745  				return nil, nil, err
   746  			}
   747  			originalElementMergeKeyValueString = fmt.Sprintf("%v", originalElementMergeKeyValue)
   748  		}
   749  		if modifiedInBounds {
   750  			modifiedElement, modifiedElementMergeKeyValue, err = getMapAndMergeKeyValueByIndex(modifiedIndex, mergeKey, modifiedSorted)
   751  			if err != nil {
   752  				return nil, nil, err
   753  			}
   754  			modifiedElementMergeKeyValueString = fmt.Sprintf("%v", modifiedElementMergeKeyValue)
   755  		}
   756  
   757  		switch {
   758  		case bothInBounds && ItemMatchesOriginalAndModifiedSlice(originalElementMergeKeyValueString, modifiedElementMergeKeyValueString):
   759  			// Merge key values are equal, so recurse
   760  			patchValue, err := diffMaps(originalElement, modifiedElement, schema, diffOptions)
   761  			if err != nil {
   762  				return nil, nil, err
   763  			}
   764  			if len(patchValue) > 0 {
   765  				patchValue[mergeKey] = modifiedElementMergeKeyValue
   766  				patch = append(patch, patchValue)
   767  			}
   768  			originalIndex++
   769  			modifiedIndex++
   770  		// only modified is in bound
   771  		case !originalInBounds:
   772  			fallthrough
   773  		// modified has additional map
   774  		case bothInBounds && ItemAddedToModifiedSlice(originalElementMergeKeyValueString, modifiedElementMergeKeyValueString):
   775  			if !diffOptions.IgnoreChangesAndAdditions {
   776  				patch = append(patch, modifiedElement)
   777  			}
   778  			modifiedIndex++
   779  		// only original is in bound
   780  		case !modifiedInBounds:
   781  			fallthrough
   782  		// original has additional map
   783  		case bothInBounds && ItemRemovedFromModifiedSlice(originalElementMergeKeyValueString, modifiedElementMergeKeyValueString):
   784  			if !diffOptions.IgnoreDeletions {
   785  				// Item was deleted, so add delete directive
   786  				deletionList = append(deletionList, CreateDeleteDirective(mergeKey, originalElementMergeKeyValue))
   787  			}
   788  			originalIndex++
   789  		}
   790  	}
   791  
   792  	return patch, deletionList, nil
   793  }
   794  
   795  // getMapAndMergeKeyValueByIndex return a map in the list and its merge key value given the index of the map.
   796  func getMapAndMergeKeyValueByIndex(index int, mergeKey string, listOfMaps []interface{}) (map[string]interface{}, interface{}, error) {
   797  	m, ok := listOfMaps[index].(map[string]interface{})
   798  	if !ok {
   799  		return nil, nil, mergepatch.ErrBadArgType(m, listOfMaps[index])
   800  	}
   801  
   802  	val, ok := m[mergeKey]
   803  	if !ok {
   804  		return nil, nil, mergepatch.ErrNoMergeKey(m, mergeKey)
   805  	}
   806  	return m, val, nil
   807  }
   808  
   809  // StrategicMergePatch applies a strategic merge patch. The patch and the original document
   810  // must be json encoded content. A patch can be created from an original and a modified document
   811  // by calling CreateStrategicMergePatch.
   812  func StrategicMergePatch(original, patch []byte, dataStruct interface{}) ([]byte, error) {
   813  	schema, err := NewPatchMetaFromStruct(dataStruct)
   814  	if err != nil {
   815  		return nil, err
   816  	}
   817  
   818  	return StrategicMergePatchUsingLookupPatchMeta(original, patch, schema)
   819  }
   820  
   821  func StrategicMergePatchUsingLookupPatchMeta(original, patch []byte, schema LookupPatchMeta) ([]byte, error) {
   822  	originalMap, err := handleUnmarshal(original)
   823  	if err != nil {
   824  		return nil, err
   825  	}
   826  	patchMap, err := handleUnmarshal(patch)
   827  	if err != nil {
   828  		return nil, err
   829  	}
   830  
   831  	result, err := StrategicMergeMapPatchUsingLookupPatchMeta(originalMap, patchMap, schema)
   832  	if err != nil {
   833  		return nil, err
   834  	}
   835  
   836  	return json.Marshal(result)
   837  }
   838  
   839  func handleUnmarshal(j []byte) (map[string]interface{}, error) {
   840  	if j == nil {
   841  		j = []byte("{}")
   842  	}
   843  
   844  	m := map[string]interface{}{}
   845  	err := json.Unmarshal(j, &m)
   846  	if err != nil {
   847  		return nil, mergepatch.ErrBadJSONDoc
   848  	}
   849  	return m, nil
   850  }
   851  
   852  // StrategicMergeMapPatch applies a strategic merge patch. The original and patch documents
   853  // must be JSONMap. A patch can be created from an original and modified document by
   854  // calling CreateTwoWayMergeMapPatch.
   855  // Warning: the original and patch JSONMap objects are mutated by this function and should not be reused.
   856  func StrategicMergeMapPatch(original, patch JSONMap, dataStruct interface{}) (JSONMap, error) {
   857  	schema, err := NewPatchMetaFromStruct(dataStruct)
   858  	if err != nil {
   859  		return nil, err
   860  	}
   861  
   862  	// We need the go struct tags `patchMergeKey` and `patchStrategy` for fields that support a strategic merge patch.
   863  	// For native resources, we can easily figure out these tags since we know the fields.
   864  
   865  	// Because custom resources are decoded as Unstructured and because we're missing the metadata about how to handle
   866  	// each field in a strategic merge patch, we can't find the go struct tags. Hence, we can't easily  do a strategic merge
   867  	// for custom resources. So we should fail fast and return an error.
   868  	if _, ok := dataStruct.(*unstructured.Unstructured); ok {
   869  		return nil, mergepatch.ErrUnsupportedStrategicMergePatchFormat
   870  	}
   871  
   872  	return StrategicMergeMapPatchUsingLookupPatchMeta(original, patch, schema)
   873  }
   874  
   875  func StrategicMergeMapPatchUsingLookupPatchMeta(original, patch JSONMap, schema LookupPatchMeta) (JSONMap, error) {
   876  	mergeOptions := MergeOptions{
   877  		MergeParallelList:    true,
   878  		IgnoreUnmatchedNulls: true,
   879  	}
   880  	return mergeMap(original, patch, schema, mergeOptions)
   881  }
   882  
   883  // MergeStrategicMergeMapPatchUsingLookupPatchMeta merges strategic merge
   884  // patches retaining `null` fields and parallel lists. If 2 patches change the
   885  // same fields and the latter one will override the former one. If you don't
   886  // want that happen, you need to run func MergingMapsHaveConflicts before
   887  // merging these patches. Applying the resulting merged merge patch to a JSONMap
   888  // yields the same as merging each strategic merge patch to the JSONMap in
   889  // succession.
   890  func MergeStrategicMergeMapPatchUsingLookupPatchMeta(schema LookupPatchMeta, patches ...JSONMap) (JSONMap, error) {
   891  	mergeOptions := MergeOptions{
   892  		MergeParallelList:    false,
   893  		IgnoreUnmatchedNulls: false,
   894  	}
   895  	merged := JSONMap{}
   896  	var err error
   897  	for _, patch := range patches {
   898  		merged, err = mergeMap(merged, patch, schema, mergeOptions)
   899  		if err != nil {
   900  			return nil, err
   901  		}
   902  	}
   903  	return merged, nil
   904  }
   905  
   906  // handleDirectiveInMergeMap handles the patch directive when merging 2 maps.
   907  func handleDirectiveInMergeMap(directive interface{}, patch map[string]interface{}) (map[string]interface{}, error) {
   908  	if directive == replaceDirective {
   909  		// If the patch contains "$patch: replace", don't merge it, just use the
   910  		// patch directly. Later on, we can add a single level replace that only
   911  		// affects the map that the $patch is in.
   912  		delete(patch, directiveMarker)
   913  		return patch, nil
   914  	}
   915  
   916  	if directive == deleteDirective {
   917  		// If the patch contains "$patch: delete", don't merge it, just return
   918  		//  an empty map.
   919  		return map[string]interface{}{}, nil
   920  	}
   921  
   922  	return nil, mergepatch.ErrBadPatchType(directive, patch)
   923  }
   924  
   925  func containsDirectiveMarker(item interface{}) bool {
   926  	m, ok := item.(map[string]interface{})
   927  	if ok {
   928  		if _, foundDirectiveMarker := m[directiveMarker]; foundDirectiveMarker {
   929  			return true
   930  		}
   931  	}
   932  	return false
   933  }
   934  
   935  func mergeKeyValueEqual(left, right interface{}, mergeKey string) (bool, error) {
   936  	if len(mergeKey) == 0 {
   937  		return left == right, nil
   938  	}
   939  	typedLeft, ok := left.(map[string]interface{})
   940  	if !ok {
   941  		return false, mergepatch.ErrBadArgType(typedLeft, left)
   942  	}
   943  	typedRight, ok := right.(map[string]interface{})
   944  	if !ok {
   945  		return false, mergepatch.ErrBadArgType(typedRight, right)
   946  	}
   947  	mergeKeyLeft, ok := typedLeft[mergeKey]
   948  	if !ok {
   949  		return false, mergepatch.ErrNoMergeKey(typedLeft, mergeKey)
   950  	}
   951  	mergeKeyRight, ok := typedRight[mergeKey]
   952  	if !ok {
   953  		return false, mergepatch.ErrNoMergeKey(typedRight, mergeKey)
   954  	}
   955  	return mergeKeyLeft == mergeKeyRight, nil
   956  }
   957  
   958  // extractKey trims the prefix and return the original key
   959  func extractKey(s, prefix string) (string, error) {
   960  	substrings := strings.SplitN(s, "/", 2)
   961  	if len(substrings) <= 1 || substrings[0] != prefix {
   962  		switch prefix {
   963  		case deleteFromPrimitiveListDirectivePrefix:
   964  			return "", mergepatch.ErrBadPatchFormatForPrimitiveList
   965  		case setElementOrderDirectivePrefix:
   966  			return "", mergepatch.ErrBadPatchFormatForSetElementOrderList
   967  		default:
   968  			return "", fmt.Errorf("fail to find unknown prefix %q in %s\n", prefix, s)
   969  		}
   970  	}
   971  	return substrings[1], nil
   972  }
   973  
   974  // validatePatchUsingSetOrderList verifies:
   975  // the relative order of any two items in the setOrderList list matches that in the patch list.
   976  // the items in the patch list must be a subset or the same as the $setElementOrder list (deletions are ignored).
   977  func validatePatchWithSetOrderList(patchList, setOrderList interface{}, mergeKey string) error {
   978  	typedSetOrderList, ok := setOrderList.([]interface{})
   979  	if !ok {
   980  		return mergepatch.ErrBadPatchFormatForSetElementOrderList
   981  	}
   982  	typedPatchList, ok := patchList.([]interface{})
   983  	if !ok {
   984  		return mergepatch.ErrBadPatchFormatForSetElementOrderList
   985  	}
   986  	if len(typedSetOrderList) == 0 || len(typedPatchList) == 0 {
   987  		return nil
   988  	}
   989  
   990  	var nonDeleteList []interface{}
   991  	var err error
   992  	if len(mergeKey) > 0 {
   993  		nonDeleteList, _, err = extractToDeleteItems(typedPatchList)
   994  		if err != nil {
   995  			return err
   996  		}
   997  	} else {
   998  		nonDeleteList = typedPatchList
   999  	}
  1000  
  1001  	patchIndex, setOrderIndex := 0, 0
  1002  	for patchIndex < len(nonDeleteList) && setOrderIndex < len(typedSetOrderList) {
  1003  		if containsDirectiveMarker(nonDeleteList[patchIndex]) {
  1004  			patchIndex++
  1005  			continue
  1006  		}
  1007  		mergeKeyEqual, err := mergeKeyValueEqual(nonDeleteList[patchIndex], typedSetOrderList[setOrderIndex], mergeKey)
  1008  		if err != nil {
  1009  			return err
  1010  		}
  1011  		if mergeKeyEqual {
  1012  			patchIndex++
  1013  		}
  1014  		setOrderIndex++
  1015  	}
  1016  	// If patchIndex is inbound but setOrderIndex if out of bound mean there are items mismatching between the patch list and setElementOrder list.
  1017  	// the second check is a sanity check, and should always be true if the first is true.
  1018  	if patchIndex < len(nonDeleteList) && setOrderIndex >= len(typedSetOrderList) {
  1019  		return fmt.Errorf("The order in patch list:\n%v\n doesn't match %s list:\n%v\n", typedPatchList, setElementOrderDirectivePrefix, setOrderList)
  1020  	}
  1021  	return nil
  1022  }
  1023  
  1024  // preprocessDeletionListForMerging preprocesses the deletion list.
  1025  // it returns shouldContinue, isDeletionList, noPrefixKey
  1026  func preprocessDeletionListForMerging(key string, original map[string]interface{},
  1027  	patchVal interface{}, mergeDeletionList bool) (bool, bool, string, error) {
  1028  	// If found a parallel list for deletion and we are going to merge the list,
  1029  	// overwrite the key to the original key and set flag isDeleteList
  1030  	foundParallelListPrefix := strings.HasPrefix(key, deleteFromPrimitiveListDirectivePrefix)
  1031  	if foundParallelListPrefix {
  1032  		if !mergeDeletionList {
  1033  			original[key] = patchVal
  1034  			return true, false, "", nil
  1035  		}
  1036  		originalKey, err := extractKey(key, deleteFromPrimitiveListDirectivePrefix)
  1037  		return false, true, originalKey, err
  1038  	}
  1039  	return false, false, "", nil
  1040  }
  1041  
  1042  // applyRetainKeysDirective looks for a retainKeys directive and applies to original
  1043  // - if no directive exists do nothing
  1044  // - if directive is found, clear keys in original missing from the directive list
  1045  // - validate that all keys present in the patch are present in the retainKeys directive
  1046  // note: original may be another patch request, e.g. applying the add+modified patch to the deletions patch. In this case it may have directives
  1047  func applyRetainKeysDirective(original, patch map[string]interface{}, options MergeOptions) error {
  1048  	retainKeysInPatch, foundInPatch := patch[retainKeysDirective]
  1049  	if !foundInPatch {
  1050  		return nil
  1051  	}
  1052  	// cleanup the directive
  1053  	delete(patch, retainKeysDirective)
  1054  
  1055  	if !options.MergeParallelList {
  1056  		// If original is actually a patch, make sure the retainKeys directives are the same in both patches if present in both.
  1057  		// If not present in the original patch, copy from the modified patch.
  1058  		retainKeysInOriginal, foundInOriginal := original[retainKeysDirective]
  1059  		if foundInOriginal {
  1060  			if !reflect.DeepEqual(retainKeysInOriginal, retainKeysInPatch) {
  1061  				// This error actually should never happen.
  1062  				return fmt.Errorf("%v and %v are not deep equal: this may happen when calculating the 3-way diff patch", retainKeysInOriginal, retainKeysInPatch)
  1063  			}
  1064  		} else {
  1065  			original[retainKeysDirective] = retainKeysInPatch
  1066  		}
  1067  		return nil
  1068  	}
  1069  
  1070  	retainKeysList, ok := retainKeysInPatch.([]interface{})
  1071  	if !ok {
  1072  		return mergepatch.ErrBadPatchFormatForRetainKeys
  1073  	}
  1074  
  1075  	// validate patch to make sure all fields in the patch are present in the retainKeysList.
  1076  	// The map is used only as a set, the value is never referenced
  1077  	m := map[interface{}]struct{}{}
  1078  	for _, v := range retainKeysList {
  1079  		m[v] = struct{}{}
  1080  	}
  1081  	for k, v := range patch {
  1082  		if v == nil || strings.HasPrefix(k, deleteFromPrimitiveListDirectivePrefix) ||
  1083  			strings.HasPrefix(k, setElementOrderDirectivePrefix) {
  1084  			continue
  1085  		}
  1086  		// If there is an item present in the patch but not in the retainKeys list,
  1087  		// the patch is invalid.
  1088  		if _, found := m[k]; !found {
  1089  			return mergepatch.ErrBadPatchFormatForRetainKeys
  1090  		}
  1091  	}
  1092  
  1093  	// clear not present fields
  1094  	for k := range original {
  1095  		if _, found := m[k]; !found {
  1096  			delete(original, k)
  1097  		}
  1098  	}
  1099  	return nil
  1100  }
  1101  
  1102  // mergePatchIntoOriginal processes $setElementOrder list.
  1103  // When not merging the directive, it will make sure $setElementOrder list exist only in original.
  1104  // When merging the directive, it will try to find the $setElementOrder list and
  1105  // its corresponding patch list, validate it and merge it.
  1106  // Then, sort them by the relative order in setElementOrder, patch list and live list.
  1107  // The precedence is $setElementOrder > order in patch list > order in live list.
  1108  // This function will delete the item after merging it to prevent process it again in the future.
  1109  // Ref: https://git.k8s.io/design-proposals-archive/cli/preserve-order-in-strategic-merge-patch.md
  1110  func mergePatchIntoOriginal(original, patch map[string]interface{}, schema LookupPatchMeta, mergeOptions MergeOptions) error {
  1111  	for key, patchV := range patch {
  1112  		// Do nothing if there is no ordering directive
  1113  		if !strings.HasPrefix(key, setElementOrderDirectivePrefix) {
  1114  			continue
  1115  		}
  1116  
  1117  		setElementOrderInPatch := patchV
  1118  		// Copies directive from the second patch (`patch`) to the first patch (`original`)
  1119  		// and checks they are equal and delete the directive in the second patch
  1120  		if !mergeOptions.MergeParallelList {
  1121  			setElementOrderListInOriginal, ok := original[key]
  1122  			if ok {
  1123  				// check if the setElementOrder list in original and the one in patch matches
  1124  				if !reflect.DeepEqual(setElementOrderListInOriginal, setElementOrderInPatch) {
  1125  					return mergepatch.ErrBadPatchFormatForSetElementOrderList
  1126  				}
  1127  			} else {
  1128  				// move the setElementOrder list from patch to original
  1129  				original[key] = setElementOrderInPatch
  1130  			}
  1131  		}
  1132  		delete(patch, key)
  1133  
  1134  		var (
  1135  			ok                                          bool
  1136  			originalFieldValue, patchFieldValue, merged []interface{}
  1137  			patchStrategy                               string
  1138  			patchMeta                                   PatchMeta
  1139  			subschema                                   LookupPatchMeta
  1140  		)
  1141  		typedSetElementOrderList, ok := setElementOrderInPatch.([]interface{})
  1142  		if !ok {
  1143  			return mergepatch.ErrBadArgType(typedSetElementOrderList, setElementOrderInPatch)
  1144  		}
  1145  		// Trim the setElementOrderDirectivePrefix to get the key of the list field in original.
  1146  		originalKey, err := extractKey(key, setElementOrderDirectivePrefix)
  1147  		if err != nil {
  1148  			return err
  1149  		}
  1150  		// try to find the list with `originalKey` in `original` and `modified` and merge them.
  1151  		originalList, foundOriginal := original[originalKey]
  1152  		patchList, foundPatch := patch[originalKey]
  1153  		if foundOriginal {
  1154  			originalFieldValue, ok = originalList.([]interface{})
  1155  			if !ok {
  1156  				return mergepatch.ErrBadArgType(originalFieldValue, originalList)
  1157  			}
  1158  		}
  1159  		if foundPatch {
  1160  			patchFieldValue, ok = patchList.([]interface{})
  1161  			if !ok {
  1162  				return mergepatch.ErrBadArgType(patchFieldValue, patchList)
  1163  			}
  1164  		}
  1165  		subschema, patchMeta, err = schema.LookupPatchMetadataForSlice(originalKey)
  1166  		if err != nil {
  1167  			return err
  1168  		}
  1169  		_, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
  1170  		if err != nil {
  1171  			return err
  1172  		}
  1173  		// Check for consistency between the element order list and the field it applies to
  1174  		err = validatePatchWithSetOrderList(patchFieldValue, typedSetElementOrderList, patchMeta.GetPatchMergeKey())
  1175  		if err != nil {
  1176  			return err
  1177  		}
  1178  
  1179  		switch {
  1180  		case foundOriginal && !foundPatch:
  1181  			// no change to list contents
  1182  			merged = originalFieldValue
  1183  		case !foundOriginal && foundPatch:
  1184  			// list was added
  1185  			v, keep := removeDirectives(patchFieldValue)
  1186  			if !keep {
  1187  				// Shouldn't be possible since patchFieldValue is a slice
  1188  				continue
  1189  			}
  1190  
  1191  			merged = v.([]interface{})
  1192  		case foundOriginal && foundPatch:
  1193  			merged, err = mergeSliceHandler(originalList, patchList, subschema,
  1194  				patchStrategy, patchMeta.GetPatchMergeKey(), false, mergeOptions)
  1195  			if err != nil {
  1196  				return err
  1197  			}
  1198  		case !foundOriginal && !foundPatch:
  1199  			continue
  1200  		}
  1201  
  1202  		// Split all items into patch items and server-only items and then enforce the order.
  1203  		var patchItems, serverOnlyItems []interface{}
  1204  		if len(patchMeta.GetPatchMergeKey()) == 0 {
  1205  			// Primitives doesn't need merge key to do partitioning.
  1206  			patchItems, serverOnlyItems = partitionPrimitivesByPresentInList(merged, typedSetElementOrderList)
  1207  
  1208  		} else {
  1209  			// Maps need merge key to do partitioning.
  1210  			patchItems, serverOnlyItems, err = partitionMapsByPresentInList(merged, typedSetElementOrderList, patchMeta.GetPatchMergeKey())
  1211  			if err != nil {
  1212  				return err
  1213  			}
  1214  		}
  1215  
  1216  		elementType, err := sliceElementType(originalFieldValue, patchFieldValue)
  1217  		if err != nil {
  1218  			return err
  1219  		}
  1220  		kind := elementType.Kind()
  1221  		// normalize merged list
  1222  		// typedSetElementOrderList contains all the relative order in typedPatchList,
  1223  		// so don't need to use typedPatchList
  1224  		both, err := normalizeElementOrder(patchItems, serverOnlyItems, typedSetElementOrderList, originalFieldValue, patchMeta.GetPatchMergeKey(), kind)
  1225  		if err != nil {
  1226  			return err
  1227  		}
  1228  		original[originalKey] = both
  1229  		// delete patch list from patch to prevent process again in the future
  1230  		delete(patch, originalKey)
  1231  	}
  1232  	return nil
  1233  }
  1234  
  1235  // partitionPrimitivesByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
  1236  func partitionPrimitivesByPresentInList(original, partitionBy []interface{}) ([]interface{}, []interface{}) {
  1237  	patch := make([]interface{}, 0, len(original))
  1238  	serverOnly := make([]interface{}, 0, len(original))
  1239  	inPatch := map[interface{}]bool{}
  1240  	for _, v := range partitionBy {
  1241  		inPatch[v] = true
  1242  	}
  1243  	for _, v := range original {
  1244  		if !inPatch[v] {
  1245  			serverOnly = append(serverOnly, v)
  1246  		} else {
  1247  			patch = append(patch, v)
  1248  		}
  1249  	}
  1250  	return patch, serverOnly
  1251  }
  1252  
  1253  // partitionMapsByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
  1254  func partitionMapsByPresentInList(original, partitionBy []interface{}, mergeKey string) ([]interface{}, []interface{}, error) {
  1255  	patch := make([]interface{}, 0, len(original))
  1256  	serverOnly := make([]interface{}, 0, len(original))
  1257  	for _, v := range original {
  1258  		typedV, ok := v.(map[string]interface{})
  1259  		if !ok {
  1260  			return nil, nil, mergepatch.ErrBadArgType(typedV, v)
  1261  		}
  1262  		mergeKeyValue, foundMergeKey := typedV[mergeKey]
  1263  		if !foundMergeKey {
  1264  			return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
  1265  		}
  1266  		_, _, found, err := findMapInSliceBasedOnKeyValue(partitionBy, mergeKey, mergeKeyValue)
  1267  		if err != nil {
  1268  			return nil, nil, err
  1269  		}
  1270  		if !found {
  1271  			serverOnly = append(serverOnly, v)
  1272  		} else {
  1273  			patch = append(patch, v)
  1274  		}
  1275  	}
  1276  	return patch, serverOnly, nil
  1277  }
  1278  
  1279  // Removes directives from an object and returns value to use instead and whether
  1280  // or not the field/index should even be kept
  1281  // May modify input
  1282  func removeDirectives(obj interface{}) (interface{}, bool) {
  1283  	if obj == nil {
  1284  		return obj, true
  1285  	} else if typedV, ok := obj.(map[string]interface{}); ok {
  1286  		if _, hasDirective := typedV[directiveMarker]; hasDirective {
  1287  			return nil, false
  1288  		}
  1289  
  1290  		for k, v := range typedV {
  1291  			var keep bool
  1292  			typedV[k], keep = removeDirectives(v)
  1293  			if !keep {
  1294  				delete(typedV, k)
  1295  			}
  1296  		}
  1297  		return typedV, true
  1298  	} else if typedV, ok := obj.([]interface{}); ok {
  1299  		var res []interface{}
  1300  		if typedV != nil {
  1301  			// Make sure res is non-nil if patch is non-nil
  1302  			res = []interface{}{}
  1303  		}
  1304  		for _, v := range typedV {
  1305  			if newV, keep := removeDirectives(v); keep {
  1306  				res = append(res, newV)
  1307  			}
  1308  		}
  1309  		return res, true
  1310  	} else {
  1311  		return obj, true
  1312  	}
  1313  }
  1314  
  1315  // Merge fields from a patch map into the original map. Note: This may modify
  1316  // both the original map and the patch because getting a deep copy of a map in
  1317  // golang is highly non-trivial.
  1318  // flag mergeOptions.MergeParallelList controls if using the parallel list to delete or keeping the list.
  1319  // If patch contains any null field (e.g. field_1: null) that is not
  1320  // present in original, then to propagate it to the end result use
  1321  // mergeOptions.IgnoreUnmatchedNulls == false.
  1322  func mergeMap(original, patch map[string]interface{}, schema LookupPatchMeta, mergeOptions MergeOptions) (map[string]interface{}, error) {
  1323  	if v, ok := patch[directiveMarker]; ok {
  1324  		return handleDirectiveInMergeMap(v, patch)
  1325  	}
  1326  
  1327  	// nil is an accepted value for original to simplify logic in other places.
  1328  	// If original is nil, replace it with an empty map and then apply the patch.
  1329  	if original == nil {
  1330  		original = map[string]interface{}{}
  1331  	}
  1332  
  1333  	err := applyRetainKeysDirective(original, patch, mergeOptions)
  1334  	if err != nil {
  1335  		return nil, err
  1336  	}
  1337  
  1338  	// Process $setElementOrder list and other lists sharing the same key.
  1339  	// When not merging the directive, it will make sure $setElementOrder list exist only in original.
  1340  	// When merging the directive, it will process $setElementOrder and its patch list together.
  1341  	// This function will delete the merged elements from patch so they will not be reprocessed
  1342  	err = mergePatchIntoOriginal(original, patch, schema, mergeOptions)
  1343  	if err != nil {
  1344  		return nil, err
  1345  	}
  1346  
  1347  	// Start merging the patch into the original.
  1348  	for k, patchV := range patch {
  1349  		skipProcessing, isDeleteList, noPrefixKey, err := preprocessDeletionListForMerging(k, original, patchV, mergeOptions.MergeParallelList)
  1350  		if err != nil {
  1351  			return nil, err
  1352  		}
  1353  		if skipProcessing {
  1354  			continue
  1355  		}
  1356  		if len(noPrefixKey) > 0 {
  1357  			k = noPrefixKey
  1358  		}
  1359  
  1360  		// If the value of this key is null, delete the key if it exists in the
  1361  		// original. Otherwise, check if we want to preserve it or skip it.
  1362  		// Preserving the null value is useful when we want to send an explicit
  1363  		// delete to the API server.
  1364  		if patchV == nil {
  1365  			delete(original, k)
  1366  			if mergeOptions.IgnoreUnmatchedNulls {
  1367  				continue
  1368  			}
  1369  		}
  1370  
  1371  		_, ok := original[k]
  1372  		if !ok {
  1373  			if !isDeleteList {
  1374  				// If it's not in the original document, just take the patch value.
  1375  				if mergeOptions.IgnoreUnmatchedNulls {
  1376  					discardNullValuesFromPatch(patchV)
  1377  				}
  1378  				original[k], ok = removeDirectives(patchV)
  1379  				if !ok {
  1380  					delete(original, k)
  1381  				}
  1382  			}
  1383  			continue
  1384  		}
  1385  
  1386  		originalType := reflect.TypeOf(original[k])
  1387  		patchType := reflect.TypeOf(patchV)
  1388  		if originalType != patchType {
  1389  			if !isDeleteList {
  1390  				if mergeOptions.IgnoreUnmatchedNulls {
  1391  					discardNullValuesFromPatch(patchV)
  1392  				}
  1393  				original[k], ok = removeDirectives(patchV)
  1394  				if !ok {
  1395  					delete(original, k)
  1396  				}
  1397  			}
  1398  			continue
  1399  		}
  1400  		// If they're both maps or lists, recurse into the value.
  1401  		switch originalType.Kind() {
  1402  		case reflect.Map:
  1403  			subschema, patchMeta, err2 := schema.LookupPatchMetadataForStruct(k)
  1404  			if err2 != nil {
  1405  				return nil, err2
  1406  			}
  1407  			_, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
  1408  			if err2 != nil {
  1409  				return nil, err2
  1410  			}
  1411  			original[k], err = mergeMapHandler(original[k], patchV, subschema, patchStrategy, mergeOptions)
  1412  		case reflect.Slice:
  1413  			subschema, patchMeta, err2 := schema.LookupPatchMetadataForSlice(k)
  1414  			if err2 != nil {
  1415  				return nil, err2
  1416  			}
  1417  			_, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
  1418  			if err2 != nil {
  1419  				return nil, err2
  1420  			}
  1421  			original[k], err = mergeSliceHandler(original[k], patchV, subschema, patchStrategy, patchMeta.GetPatchMergeKey(), isDeleteList, mergeOptions)
  1422  		default:
  1423  			original[k], ok = removeDirectives(patchV)
  1424  			if !ok {
  1425  				// if patchV itself is a directive, then don't keep it
  1426  				delete(original, k)
  1427  			}
  1428  		}
  1429  		if err != nil {
  1430  			return nil, err
  1431  		}
  1432  	}
  1433  	return original, nil
  1434  }
  1435  
  1436  // discardNullValuesFromPatch discards all null property values from patch.
  1437  // It traverses all slices and map types.
  1438  func discardNullValuesFromPatch(patchV interface{}) {
  1439  	switch patchV := patchV.(type) {
  1440  	case map[string]interface{}:
  1441  		for k, v := range patchV {
  1442  			if v == nil {
  1443  				delete(patchV, k)
  1444  			} else {
  1445  				discardNullValuesFromPatch(v)
  1446  			}
  1447  		}
  1448  	case []interface{}:
  1449  		for _, v := range patchV {
  1450  			discardNullValuesFromPatch(v)
  1451  		}
  1452  	}
  1453  }
  1454  
  1455  // mergeMapHandler handles how to merge `patchV` whose key is `key` with `original` respecting
  1456  // fieldPatchStrategy and mergeOptions.
  1457  func mergeMapHandler(original, patch interface{}, schema LookupPatchMeta,
  1458  	fieldPatchStrategy string, mergeOptions MergeOptions) (map[string]interface{}, error) {
  1459  	typedOriginal, typedPatch, err := mapTypeAssertion(original, patch)
  1460  	if err != nil {
  1461  		return nil, err
  1462  	}
  1463  
  1464  	if fieldPatchStrategy != replaceDirective {
  1465  		return mergeMap(typedOriginal, typedPatch, schema, mergeOptions)
  1466  	} else {
  1467  		return typedPatch, nil
  1468  	}
  1469  }
  1470  
  1471  // mergeSliceHandler handles how to merge `patchV` whose key is `key` with `original` respecting
  1472  // fieldPatchStrategy, fieldPatchMergeKey, isDeleteList and mergeOptions.
  1473  func mergeSliceHandler(original, patch interface{}, schema LookupPatchMeta,
  1474  	fieldPatchStrategy, fieldPatchMergeKey string, isDeleteList bool, mergeOptions MergeOptions) ([]interface{}, error) {
  1475  	typedOriginal, typedPatch, err := sliceTypeAssertion(original, patch)
  1476  	if err != nil {
  1477  		return nil, err
  1478  	}
  1479  
  1480  	// Delete lists are handled the same way regardless of what the field's patch strategy is
  1481  	if fieldPatchStrategy == mergeDirective || isDeleteList {
  1482  		return mergeSlice(typedOriginal, typedPatch, schema, fieldPatchMergeKey, mergeOptions, isDeleteList)
  1483  	} else {
  1484  		return typedPatch, nil
  1485  	}
  1486  }
  1487  
  1488  // Merge two slices together. Note: This may modify both the original slice and
  1489  // the patch because getting a deep copy of a slice in golang is highly
  1490  // non-trivial.
  1491  func mergeSlice(original, patch []interface{}, schema LookupPatchMeta, mergeKey string, mergeOptions MergeOptions, isDeleteList bool) ([]interface{}, error) {
  1492  	if len(original) == 0 && len(patch) == 0 {
  1493  		return original, nil
  1494  	}
  1495  
  1496  	// All the values must be of the same type, but not a list.
  1497  	t, err := sliceElementType(original, patch)
  1498  	if err != nil {
  1499  		return nil, err
  1500  	}
  1501  
  1502  	var merged []interface{}
  1503  	kind := t.Kind()
  1504  	// If the elements are not maps, merge the slices of scalars.
  1505  	if kind != reflect.Map {
  1506  		if mergeOptions.MergeParallelList && isDeleteList {
  1507  			return deleteFromSlice(original, patch), nil
  1508  		}
  1509  		// Maybe in the future add a "concat" mode that doesn't
  1510  		// deduplicate.
  1511  		both := append(original, patch...)
  1512  		merged = deduplicateScalars(both)
  1513  
  1514  	} else {
  1515  		if mergeKey == "" {
  1516  			return nil, fmt.Errorf("cannot merge lists without merge key for %s", schema.Name())
  1517  		}
  1518  
  1519  		original, patch, err = mergeSliceWithSpecialElements(original, patch, mergeKey)
  1520  		if err != nil {
  1521  			return nil, err
  1522  		}
  1523  
  1524  		merged, err = mergeSliceWithoutSpecialElements(original, patch, mergeKey, schema, mergeOptions)
  1525  		if err != nil {
  1526  			return nil, err
  1527  		}
  1528  	}
  1529  
  1530  	// enforce the order
  1531  	var patchItems, serverOnlyItems []interface{}
  1532  	if len(mergeKey) == 0 {
  1533  		patchItems, serverOnlyItems = partitionPrimitivesByPresentInList(merged, patch)
  1534  	} else {
  1535  		patchItems, serverOnlyItems, err = partitionMapsByPresentInList(merged, patch, mergeKey)
  1536  		if err != nil {
  1537  			return nil, err
  1538  		}
  1539  	}
  1540  	return normalizeElementOrder(patchItems, serverOnlyItems, patch, original, mergeKey, kind)
  1541  }
  1542  
  1543  // mergeSliceWithSpecialElements handles special elements with directiveMarker
  1544  // before merging the slices. It returns a updated `original` and a patch without special elements.
  1545  // original and patch must be slices of maps, they should be checked before calling this function.
  1546  func mergeSliceWithSpecialElements(original, patch []interface{}, mergeKey string) ([]interface{}, []interface{}, error) {
  1547  	patchWithoutSpecialElements := []interface{}{}
  1548  	replace := false
  1549  	for _, v := range patch {
  1550  		typedV := v.(map[string]interface{})
  1551  		patchType, ok := typedV[directiveMarker]
  1552  		if !ok {
  1553  			patchWithoutSpecialElements = append(patchWithoutSpecialElements, v)
  1554  		} else {
  1555  			switch patchType {
  1556  			case deleteDirective:
  1557  				mergeValue, ok := typedV[mergeKey]
  1558  				if ok {
  1559  					var err error
  1560  					original, err = deleteMatchingEntries(original, mergeKey, mergeValue)
  1561  					if err != nil {
  1562  						return nil, nil, err
  1563  					}
  1564  				} else {
  1565  					return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
  1566  				}
  1567  			case replaceDirective:
  1568  				replace = true
  1569  				// Continue iterating through the array to prune any other $patch elements.
  1570  			case mergeDirective:
  1571  				return nil, nil, fmt.Errorf("merging lists cannot yet be specified in the patch")
  1572  			default:
  1573  				return nil, nil, mergepatch.ErrBadPatchType(patchType, typedV)
  1574  			}
  1575  		}
  1576  	}
  1577  	if replace {
  1578  		return patchWithoutSpecialElements, nil, nil
  1579  	}
  1580  	return original, patchWithoutSpecialElements, nil
  1581  }
  1582  
  1583  // delete all matching entries (based on merge key) from a merging list
  1584  func deleteMatchingEntries(original []interface{}, mergeKey string, mergeValue interface{}) ([]interface{}, error) {
  1585  	for {
  1586  		_, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
  1587  		if err != nil {
  1588  			return nil, err
  1589  		}
  1590  
  1591  		if !found {
  1592  			break
  1593  		}
  1594  		// Delete the element at originalKey.
  1595  		original = append(original[:originalKey], original[originalKey+1:]...)
  1596  	}
  1597  	return original, nil
  1598  }
  1599  
  1600  // mergeSliceWithoutSpecialElements merges slices with non-special elements.
  1601  // original and patch must be slices of maps, they should be checked before calling this function.
  1602  func mergeSliceWithoutSpecialElements(original, patch []interface{}, mergeKey string, schema LookupPatchMeta, mergeOptions MergeOptions) ([]interface{}, error) {
  1603  	for _, v := range patch {
  1604  		typedV := v.(map[string]interface{})
  1605  		mergeValue, ok := typedV[mergeKey]
  1606  		if !ok {
  1607  			return nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
  1608  		}
  1609  
  1610  		// If we find a value with this merge key value in original, merge the
  1611  		// maps. Otherwise append onto original.
  1612  		originalMap, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
  1613  		if err != nil {
  1614  			return nil, err
  1615  		}
  1616  
  1617  		if found {
  1618  			var mergedMaps interface{}
  1619  			var err error
  1620  			// Merge into original.
  1621  			mergedMaps, err = mergeMap(originalMap, typedV, schema, mergeOptions)
  1622  			if err != nil {
  1623  				return nil, err
  1624  			}
  1625  
  1626  			original[originalKey] = mergedMaps
  1627  		} else {
  1628  			original = append(original, v)
  1629  		}
  1630  	}
  1631  	return original, nil
  1632  }
  1633  
  1634  // deleteFromSlice uses the parallel list to delete the items in a list of scalars
  1635  func deleteFromSlice(current, toDelete []interface{}) []interface{} {
  1636  	toDeleteMap := map[interface{}]interface{}{}
  1637  	processed := make([]interface{}, 0, len(current))
  1638  	for _, v := range toDelete {
  1639  		toDeleteMap[v] = true
  1640  	}
  1641  	for _, v := range current {
  1642  		if _, found := toDeleteMap[v]; !found {
  1643  			processed = append(processed, v)
  1644  		}
  1645  	}
  1646  	return processed
  1647  }
  1648  
  1649  // This method no longer panics if any element of the slice is not a map.
  1650  func findMapInSliceBasedOnKeyValue(m []interface{}, key string, value interface{}) (map[string]interface{}, int, bool, error) {
  1651  	for k, v := range m {
  1652  		typedV, ok := v.(map[string]interface{})
  1653  		if !ok {
  1654  			return nil, 0, false, fmt.Errorf("value for key %v is not a map", k)
  1655  		}
  1656  
  1657  		valueToMatch, ok := typedV[key]
  1658  		if ok && valueToMatch == value {
  1659  			return typedV, k, true, nil
  1660  		}
  1661  	}
  1662  
  1663  	return nil, 0, false, nil
  1664  }
  1665  
  1666  // This function takes a JSON map and sorts all the lists that should be merged
  1667  // by key. This is needed by tests because in JSON, list order is significant,
  1668  // but in Strategic Merge Patch, merge lists do not have significant order.
  1669  // Sorting the lists allows for order-insensitive comparison of patched maps.
  1670  func sortMergeListsByName(mapJSON []byte, schema LookupPatchMeta) ([]byte, error) {
  1671  	var m map[string]interface{}
  1672  	err := json.Unmarshal(mapJSON, &m)
  1673  	if err != nil {
  1674  		return nil, mergepatch.ErrBadJSONDoc
  1675  	}
  1676  
  1677  	newM, err := sortMergeListsByNameMap(m, schema)
  1678  	if err != nil {
  1679  		return nil, err
  1680  	}
  1681  
  1682  	return json.Marshal(newM)
  1683  }
  1684  
  1685  // Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in a map.
  1686  func sortMergeListsByNameMap(s map[string]interface{}, schema LookupPatchMeta) (map[string]interface{}, error) {
  1687  	newS := map[string]interface{}{}
  1688  	for k, v := range s {
  1689  		if k == retainKeysDirective {
  1690  			typedV, ok := v.([]interface{})
  1691  			if !ok {
  1692  				return nil, mergepatch.ErrBadPatchFormatForRetainKeys
  1693  			}
  1694  			v = sortScalars(typedV)
  1695  		} else if strings.HasPrefix(k, deleteFromPrimitiveListDirectivePrefix) {
  1696  			typedV, ok := v.([]interface{})
  1697  			if !ok {
  1698  				return nil, mergepatch.ErrBadPatchFormatForPrimitiveList
  1699  			}
  1700  			v = sortScalars(typedV)
  1701  		} else if strings.HasPrefix(k, setElementOrderDirectivePrefix) {
  1702  			_, ok := v.([]interface{})
  1703  			if !ok {
  1704  				return nil, mergepatch.ErrBadPatchFormatForSetElementOrderList
  1705  			}
  1706  		} else if k != directiveMarker {
  1707  			// recurse for map and slice.
  1708  			switch typedV := v.(type) {
  1709  			case map[string]interface{}:
  1710  				subschema, _, err := schema.LookupPatchMetadataForStruct(k)
  1711  				if err != nil {
  1712  					return nil, err
  1713  				}
  1714  				v, err = sortMergeListsByNameMap(typedV, subschema)
  1715  				if err != nil {
  1716  					return nil, err
  1717  				}
  1718  			case []interface{}:
  1719  				subschema, patchMeta, err := schema.LookupPatchMetadataForSlice(k)
  1720  				if err != nil {
  1721  					return nil, err
  1722  				}
  1723  				_, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
  1724  				if err != nil {
  1725  					return nil, err
  1726  				}
  1727  				if patchStrategy == mergeDirective {
  1728  					var err error
  1729  					v, err = sortMergeListsByNameArray(typedV, subschema, patchMeta.GetPatchMergeKey(), true)
  1730  					if err != nil {
  1731  						return nil, err
  1732  					}
  1733  				}
  1734  			}
  1735  		}
  1736  
  1737  		newS[k] = v
  1738  	}
  1739  
  1740  	return newS, nil
  1741  }
  1742  
  1743  // Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in an array.
  1744  func sortMergeListsByNameArray(s []interface{}, schema LookupPatchMeta, mergeKey string, recurse bool) ([]interface{}, error) {
  1745  	if len(s) == 0 {
  1746  		return s, nil
  1747  	}
  1748  
  1749  	// We don't support lists of lists yet.
  1750  	t, err := sliceElementType(s)
  1751  	if err != nil {
  1752  		return nil, err
  1753  	}
  1754  
  1755  	// If the elements are not maps...
  1756  	if t.Kind() != reflect.Map {
  1757  		// Sort the elements, because they may have been merged out of order.
  1758  		return deduplicateAndSortScalars(s), nil
  1759  	}
  1760  
  1761  	// Elements are maps - if one of the keys of the map is a map or a
  1762  	// list, we may need to recurse into it.
  1763  	newS := []interface{}{}
  1764  	for _, elem := range s {
  1765  		if recurse {
  1766  			typedElem := elem.(map[string]interface{})
  1767  			newElem, err := sortMergeListsByNameMap(typedElem, schema)
  1768  			if err != nil {
  1769  				return nil, err
  1770  			}
  1771  
  1772  			newS = append(newS, newElem)
  1773  		} else {
  1774  			newS = append(newS, elem)
  1775  		}
  1776  	}
  1777  
  1778  	// Sort the maps.
  1779  	newS = sortMapsBasedOnField(newS, mergeKey)
  1780  	return newS, nil
  1781  }
  1782  
  1783  func sortMapsBasedOnField(m []interface{}, fieldName string) []interface{} {
  1784  	mapM := mapSliceFromSlice(m)
  1785  	ss := SortableSliceOfMaps{mapM, fieldName}
  1786  	sort.Sort(ss)
  1787  	newS := sliceFromMapSlice(ss.s)
  1788  	return newS
  1789  }
  1790  
  1791  func mapSliceFromSlice(m []interface{}) []map[string]interface{} {
  1792  	newM := []map[string]interface{}{}
  1793  	for _, v := range m {
  1794  		vt := v.(map[string]interface{})
  1795  		newM = append(newM, vt)
  1796  	}
  1797  
  1798  	return newM
  1799  }
  1800  
  1801  func sliceFromMapSlice(s []map[string]interface{}) []interface{} {
  1802  	newS := []interface{}{}
  1803  	for _, v := range s {
  1804  		newS = append(newS, v)
  1805  	}
  1806  
  1807  	return newS
  1808  }
  1809  
  1810  type SortableSliceOfMaps struct {
  1811  	s []map[string]interface{}
  1812  	k string // key to sort on
  1813  }
  1814  
  1815  func (ss SortableSliceOfMaps) Len() int {
  1816  	return len(ss.s)
  1817  }
  1818  
  1819  func (ss SortableSliceOfMaps) Less(i, j int) bool {
  1820  	iStr := fmt.Sprintf("%v", ss.s[i][ss.k])
  1821  	jStr := fmt.Sprintf("%v", ss.s[j][ss.k])
  1822  	return sort.StringsAreSorted([]string{iStr, jStr})
  1823  }
  1824  
  1825  func (ss SortableSliceOfMaps) Swap(i, j int) {
  1826  	tmp := ss.s[i]
  1827  	ss.s[i] = ss.s[j]
  1828  	ss.s[j] = tmp
  1829  }
  1830  
  1831  func deduplicateAndSortScalars(s []interface{}) []interface{} {
  1832  	s = deduplicateScalars(s)
  1833  	return sortScalars(s)
  1834  }
  1835  
  1836  func sortScalars(s []interface{}) []interface{} {
  1837  	ss := SortableSliceOfScalars{s}
  1838  	sort.Sort(ss)
  1839  	return ss.s
  1840  }
  1841  
  1842  func deduplicateScalars(s []interface{}) []interface{} {
  1843  	// Clever algorithm to deduplicate.
  1844  	length := len(s) - 1
  1845  	for i := 0; i < length; i++ {
  1846  		for j := i + 1; j <= length; j++ {
  1847  			if s[i] == s[j] {
  1848  				s[j] = s[length]
  1849  				s = s[0:length]
  1850  				length--
  1851  				j--
  1852  			}
  1853  		}
  1854  	}
  1855  
  1856  	return s
  1857  }
  1858  
  1859  type SortableSliceOfScalars struct {
  1860  	s []interface{}
  1861  }
  1862  
  1863  func (ss SortableSliceOfScalars) Len() int {
  1864  	return len(ss.s)
  1865  }
  1866  
  1867  func (ss SortableSliceOfScalars) Less(i, j int) bool {
  1868  	iStr := fmt.Sprintf("%v", ss.s[i])
  1869  	jStr := fmt.Sprintf("%v", ss.s[j])
  1870  	return sort.StringsAreSorted([]string{iStr, jStr})
  1871  }
  1872  
  1873  func (ss SortableSliceOfScalars) Swap(i, j int) {
  1874  	tmp := ss.s[i]
  1875  	ss.s[i] = ss.s[j]
  1876  	ss.s[j] = tmp
  1877  }
  1878  
  1879  // Returns the type of the elements of N slice(s). If the type is different,
  1880  // another slice or undefined, returns an error.
  1881  func sliceElementType(slices ...[]interface{}) (reflect.Type, error) {
  1882  	var prevType reflect.Type
  1883  	for _, s := range slices {
  1884  		// Go through elements of all given slices and make sure they are all the same type.
  1885  		for _, v := range s {
  1886  			currentType := reflect.TypeOf(v)
  1887  			if prevType == nil {
  1888  				prevType = currentType
  1889  				// We don't support lists of lists yet.
  1890  				if prevType.Kind() == reflect.Slice {
  1891  					return nil, mergepatch.ErrNoListOfLists
  1892  				}
  1893  			} else {
  1894  				if prevType != currentType {
  1895  					return nil, fmt.Errorf("list element types are not identical: %v", fmt.Sprint(slices))
  1896  				}
  1897  				prevType = currentType
  1898  			}
  1899  		}
  1900  	}
  1901  
  1902  	if prevType == nil {
  1903  		return nil, fmt.Errorf("no elements in any of the given slices")
  1904  	}
  1905  
  1906  	return prevType, nil
  1907  }
  1908  
  1909  // MergingMapsHaveConflicts returns true if the left and right JSON interface
  1910  // objects overlap with different values in any key. All keys are required to be
  1911  // strings. Since patches of the same Type have congruent keys, this is valid
  1912  // for multiple patch types. This method supports strategic merge patch semantics.
  1913  func MergingMapsHaveConflicts(left, right map[string]interface{}, schema LookupPatchMeta) (bool, error) {
  1914  	return mergingMapFieldsHaveConflicts(left, right, schema, "", "")
  1915  }
  1916  
  1917  func mergingMapFieldsHaveConflicts(
  1918  	left, right interface{},
  1919  	schema LookupPatchMeta,
  1920  	fieldPatchStrategy, fieldPatchMergeKey string,
  1921  ) (bool, error) {
  1922  	switch leftType := left.(type) {
  1923  	case map[string]interface{}:
  1924  		rightType, ok := right.(map[string]interface{})
  1925  		if !ok {
  1926  			return true, nil
  1927  		}
  1928  		leftMarker, okLeft := leftType[directiveMarker]
  1929  		rightMarker, okRight := rightType[directiveMarker]
  1930  		// if one or the other has a directive marker,
  1931  		// then we need to consider that before looking at the individual keys,
  1932  		// since a directive operates on the whole map.
  1933  		if okLeft || okRight {
  1934  			// if one has a directive marker and the other doesn't,
  1935  			// then we have a conflict, since one is deleting or replacing the whole map,
  1936  			// and the other is doing things to individual keys.
  1937  			if okLeft != okRight {
  1938  				return true, nil
  1939  			}
  1940  			// if they both have markers, but they are not the same directive,
  1941  			// then we have a conflict because they're doing different things to the map.
  1942  			if leftMarker != rightMarker {
  1943  				return true, nil
  1944  			}
  1945  		}
  1946  		if fieldPatchStrategy == replaceDirective {
  1947  			return false, nil
  1948  		}
  1949  		// Check the individual keys.
  1950  		return mapsHaveConflicts(leftType, rightType, schema)
  1951  
  1952  	case []interface{}:
  1953  		rightType, ok := right.([]interface{})
  1954  		if !ok {
  1955  			return true, nil
  1956  		}
  1957  		return slicesHaveConflicts(leftType, rightType, schema, fieldPatchStrategy, fieldPatchMergeKey)
  1958  	case string, float64, bool, int64, nil:
  1959  		return !reflect.DeepEqual(left, right), nil
  1960  	default:
  1961  		return true, fmt.Errorf("unknown type: %v", reflect.TypeOf(left))
  1962  	}
  1963  }
  1964  
  1965  func mapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) {
  1966  	for key, leftValue := range typedLeft {
  1967  		if key != directiveMarker && key != retainKeysDirective {
  1968  			if rightValue, ok := typedRight[key]; ok {
  1969  				var subschema LookupPatchMeta
  1970  				var patchMeta PatchMeta
  1971  				var patchStrategy string
  1972  				var err error
  1973  				switch leftValue.(type) {
  1974  				case []interface{}:
  1975  					subschema, patchMeta, err = schema.LookupPatchMetadataForSlice(key)
  1976  					if err != nil {
  1977  						return true, err
  1978  					}
  1979  					_, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies)
  1980  					if err != nil {
  1981  						return true, err
  1982  					}
  1983  				case map[string]interface{}:
  1984  					subschema, patchMeta, err = schema.LookupPatchMetadataForStruct(key)
  1985  					if err != nil {
  1986  						return true, err
  1987  					}
  1988  					_, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies)
  1989  					if err != nil {
  1990  						return true, err
  1991  					}
  1992  				}
  1993  
  1994  				if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue,
  1995  					subschema, patchStrategy, patchMeta.GetPatchMergeKey()); hasConflicts {
  1996  					return true, err
  1997  				}
  1998  			}
  1999  		}
  2000  	}
  2001  
  2002  	return false, nil
  2003  }
  2004  
  2005  func slicesHaveConflicts(
  2006  	typedLeft, typedRight []interface{},
  2007  	schema LookupPatchMeta,
  2008  	fieldPatchStrategy, fieldPatchMergeKey string,
  2009  ) (bool, error) {
  2010  	elementType, err := sliceElementType(typedLeft, typedRight)
  2011  	if err != nil {
  2012  		return true, err
  2013  	}
  2014  
  2015  	if fieldPatchStrategy == mergeDirective {
  2016  		// Merging lists of scalars have no conflicts by definition
  2017  		// So we only need to check further if the elements are maps
  2018  		if elementType.Kind() != reflect.Map {
  2019  			return false, nil
  2020  		}
  2021  
  2022  		// Build a map for each slice and then compare the two maps
  2023  		leftMap, err := sliceOfMapsToMapOfMaps(typedLeft, fieldPatchMergeKey)
  2024  		if err != nil {
  2025  			return true, err
  2026  		}
  2027  
  2028  		rightMap, err := sliceOfMapsToMapOfMaps(typedRight, fieldPatchMergeKey)
  2029  		if err != nil {
  2030  			return true, err
  2031  		}
  2032  
  2033  		return mapsOfMapsHaveConflicts(leftMap, rightMap, schema)
  2034  	}
  2035  
  2036  	// Either we don't have type information, or these are non-merging lists
  2037  	if len(typedLeft) != len(typedRight) {
  2038  		return true, nil
  2039  	}
  2040  
  2041  	// Sort scalar slices to prevent ordering issues
  2042  	// We have no way to sort non-merging lists of maps
  2043  	if elementType.Kind() != reflect.Map {
  2044  		typedLeft = deduplicateAndSortScalars(typedLeft)
  2045  		typedRight = deduplicateAndSortScalars(typedRight)
  2046  	}
  2047  
  2048  	// Compare the slices element by element in order
  2049  	// This test will fail if the slices are not sorted
  2050  	for i := range typedLeft {
  2051  		if hasConflicts, err := mergingMapFieldsHaveConflicts(typedLeft[i], typedRight[i], schema, "", ""); hasConflicts {
  2052  			return true, err
  2053  		}
  2054  	}
  2055  
  2056  	return false, nil
  2057  }
  2058  
  2059  func sliceOfMapsToMapOfMaps(slice []interface{}, mergeKey string) (map[string]interface{}, error) {
  2060  	result := make(map[string]interface{}, len(slice))
  2061  	for _, value := range slice {
  2062  		typedValue, ok := value.(map[string]interface{})
  2063  		if !ok {
  2064  			return nil, fmt.Errorf("invalid element type in merging list:%v", slice)
  2065  		}
  2066  
  2067  		mergeValue, ok := typedValue[mergeKey]
  2068  		if !ok {
  2069  			return nil, fmt.Errorf("cannot find merge key `%s` in merging list element:%v", mergeKey, typedValue)
  2070  		}
  2071  
  2072  		result[fmt.Sprintf("%s", mergeValue)] = typedValue
  2073  	}
  2074  
  2075  	return result, nil
  2076  }
  2077  
  2078  func mapsOfMapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) {
  2079  	for key, leftValue := range typedLeft {
  2080  		if rightValue, ok := typedRight[key]; ok {
  2081  			if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue, schema, "", ""); hasConflicts {
  2082  				return true, err
  2083  			}
  2084  		}
  2085  	}
  2086  
  2087  	return false, nil
  2088  }
  2089  
  2090  // CreateThreeWayMergePatch reconciles a modified configuration with an original configuration,
  2091  // while preserving any changes or deletions made to the original configuration in the interim,
  2092  // and not overridden by the current configuration. All three documents must be passed to the
  2093  // method as json encoded content. It will return a strategic merge patch, or an error if any
  2094  // of the documents is invalid, or if there are any preconditions that fail against the modified
  2095  // configuration, or, if overwrite is false and there are conflicts between the modified and current
  2096  // configurations. Conflicts are defined as keys changed differently from original to modified
  2097  // than from original to current. In other words, a conflict occurs if modified changes any key
  2098  // in a way that is different from how it is changed in current (e.g., deleting it, changing its
  2099  // value). We also propagate values fields that do not exist in original but are explicitly
  2100  // defined in modified.
  2101  func CreateThreeWayMergePatch(original, modified, current []byte, schema LookupPatchMeta, overwrite bool, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
  2102  	originalMap := map[string]interface{}{}
  2103  	if len(original) > 0 {
  2104  		if err := json.Unmarshal(original, &originalMap); err != nil {
  2105  			return nil, mergepatch.ErrBadJSONDoc
  2106  		}
  2107  	}
  2108  
  2109  	modifiedMap := map[string]interface{}{}
  2110  	if len(modified) > 0 {
  2111  		if err := json.Unmarshal(modified, &modifiedMap); err != nil {
  2112  			return nil, mergepatch.ErrBadJSONDoc
  2113  		}
  2114  	}
  2115  
  2116  	currentMap := map[string]interface{}{}
  2117  	if len(current) > 0 {
  2118  		if err := json.Unmarshal(current, &currentMap); err != nil {
  2119  			return nil, mergepatch.ErrBadJSONDoc
  2120  		}
  2121  	}
  2122  
  2123  	// The patch is the difference from current to modified without deletions, plus deletions
  2124  	// from original to modified. To find it, we compute deletions, which are the deletions from
  2125  	// original to modified, and delta, which is the difference from current to modified without
  2126  	// deletions, and then apply delta to deletions as a patch, which should be strictly additive.
  2127  	deltaMapDiffOptions := DiffOptions{
  2128  		IgnoreDeletions: true,
  2129  		SetElementOrder: true,
  2130  	}
  2131  	deltaMap, err := diffMaps(currentMap, modifiedMap, schema, deltaMapDiffOptions)
  2132  	if err != nil {
  2133  		return nil, err
  2134  	}
  2135  	deletionsMapDiffOptions := DiffOptions{
  2136  		SetElementOrder:           true,
  2137  		IgnoreChangesAndAdditions: true,
  2138  	}
  2139  	deletionsMap, err := diffMaps(originalMap, modifiedMap, schema, deletionsMapDiffOptions)
  2140  	if err != nil {
  2141  		return nil, err
  2142  	}
  2143  
  2144  	mergeOptions := MergeOptions{}
  2145  	patchMap, err := mergeMap(deletionsMap, deltaMap, schema, mergeOptions)
  2146  	if err != nil {
  2147  		return nil, err
  2148  	}
  2149  
  2150  	// Apply the preconditions to the patch, and return an error if any of them fail.
  2151  	for _, fn := range fns {
  2152  		if !fn(patchMap) {
  2153  			return nil, mergepatch.NewErrPreconditionFailed(patchMap)
  2154  		}
  2155  	}
  2156  
  2157  	// If overwrite is false, and the patch contains any keys that were changed differently,
  2158  	// then return a conflict error.
  2159  	if !overwrite {
  2160  		changeMapDiffOptions := DiffOptions{}
  2161  		changedMap, err := diffMaps(originalMap, currentMap, schema, changeMapDiffOptions)
  2162  		if err != nil {
  2163  			return nil, err
  2164  		}
  2165  
  2166  		hasConflicts, err := MergingMapsHaveConflicts(patchMap, changedMap, schema)
  2167  		if err != nil {
  2168  			return nil, err
  2169  		}
  2170  
  2171  		if hasConflicts {
  2172  			return nil, mergepatch.NewErrConflict(mergepatch.ToYAMLOrError(patchMap), mergepatch.ToYAMLOrError(changedMap))
  2173  		}
  2174  	}
  2175  
  2176  	return json.Marshal(patchMap)
  2177  }
  2178  
  2179  func ItemAddedToModifiedSlice(original, modified string) bool { return original > modified }
  2180  
  2181  func ItemRemovedFromModifiedSlice(original, modified string) bool { return original < modified }
  2182  
  2183  func ItemMatchesOriginalAndModifiedSlice(original, modified string) bool { return original == modified }
  2184  
  2185  func CreateDeleteDirective(mergeKey string, mergeKeyValue interface{}) map[string]interface{} {
  2186  	return map[string]interface{}{mergeKey: mergeKeyValue, directiveMarker: deleteDirective}
  2187  }
  2188  
  2189  func mapTypeAssertion(original, patch interface{}) (map[string]interface{}, map[string]interface{}, error) {
  2190  	typedOriginal, ok := original.(map[string]interface{})
  2191  	if !ok {
  2192  		return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original)
  2193  	}
  2194  	typedPatch, ok := patch.(map[string]interface{})
  2195  	if !ok {
  2196  		return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch)
  2197  	}
  2198  	return typedOriginal, typedPatch, nil
  2199  }
  2200  
  2201  func sliceTypeAssertion(original, patch interface{}) ([]interface{}, []interface{}, error) {
  2202  	typedOriginal, ok := original.([]interface{})
  2203  	if !ok {
  2204  		return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original)
  2205  	}
  2206  	typedPatch, ok := patch.([]interface{})
  2207  	if !ok {
  2208  		return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch)
  2209  	}
  2210  	return typedOriginal, typedPatch, nil
  2211  }
  2212  
  2213  // extractRetainKeysPatchStrategy process patch strategy, which is a string may contains multiple
  2214  // patch strategies separated by ",". It returns a boolean var indicating if it has
  2215  // retainKeys strategies and a string for the other strategy.
  2216  func extractRetainKeysPatchStrategy(strategies []string) (bool, string, error) {
  2217  	switch len(strategies) {
  2218  	case 0:
  2219  		return false, "", nil
  2220  	case 1:
  2221  		singleStrategy := strategies[0]
  2222  		switch singleStrategy {
  2223  		case retainKeysStrategy:
  2224  			return true, "", nil
  2225  		default:
  2226  			return false, singleStrategy, nil
  2227  		}
  2228  	case 2:
  2229  		switch {
  2230  		case strategies[0] == retainKeysStrategy:
  2231  			return true, strategies[1], nil
  2232  		case strategies[1] == retainKeysStrategy:
  2233  			return true, strategies[0], nil
  2234  		default:
  2235  			return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies)
  2236  		}
  2237  	default:
  2238  		return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies)
  2239  	}
  2240  }
  2241  
  2242  // hasAdditionalNewField returns if original map has additional key with non-nil value than modified.
  2243  func hasAdditionalNewField(original, modified map[string]interface{}) bool {
  2244  	for k, v := range original {
  2245  		if v == nil {
  2246  			continue
  2247  		}
  2248  		if _, found := modified[k]; !found {
  2249  			return true
  2250  		}
  2251  	}
  2252  	return false
  2253  }
  2254  

View as plain text