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

   1 /*
   2 Copyright 2014 The Kubernetes Authors.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 package 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, toDeleteList []interface{}
 991         var err error
 992         if len(mergeKey) > 0 {
 993                 nonDeleteList, toDeleteList, 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 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         typedPatchList = append(nonDeleteList, toDeleteList...)
1022         return nil
1023 }
1024
1025 // preprocessDeletionListForMerging preprocesses the deletion list.
1026 // it returns shouldContinue, isDeletionList, noPrefixKey
1027 func preprocessDeletionListForMerging(key string, original map[string]interface{},
1028         patchVal interface{}, mergeDeletionList bool) (bool, bool, string, error) {
1029         // If found a parallel list for deletion and we are going to merge the list,
1030         // overwrite the key to the original key and set flag isDeleteList
1031         foundParallelListPrefix := strings.HasPrefix(key, deleteFromPrimitiveListDirectivePrefix)
1032         if foundParallelListPrefix {
1033                 if !mergeDeletionList {
1034                         original[key] = patchVal
1035                         return true, false, "", nil
1036                 }
1037                 originalKey, err := extractKey(key, deleteFromPrimitiveListDirectivePrefix)
1038                 return false, true, originalKey, err
1039         }
1040         return false, false, "", nil
1041 }
1042
1043 // applyRetainKeysDirective looks for a retainKeys directive and applies to original
1044 // - if no directive exists do nothing
1045 // - if directive is found, clear keys in original missing from the directive list
1046 // - validate that all keys present in the patch are present in the retainKeys directive
1047 // 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
1048 func applyRetainKeysDirective(original, patch map[string]interface{}, options MergeOptions) error {
1049         retainKeysInPatch, foundInPatch := patch[retainKeysDirective]
1050         if !foundInPatch {
1051                 return nil
1052         }
1053         // cleanup the directive
1054         delete(patch, retainKeysDirective)
1055
1056         if !options.MergeParallelList {
1057                 // If original is actually a patch, make sure the retainKeys directives are the same in both patches if present in both.
1058                 // If not present in the original patch, copy from the modified patch.
1059                 retainKeysInOriginal, foundInOriginal := original[retainKeysDirective]
1060                 if foundInOriginal {
1061                         if !reflect.DeepEqual(retainKeysInOriginal, retainKeysInPatch) {
1062                                 // This error actually should never happen.
1063                                 return fmt.Errorf("%v and %v are not deep equal: this may happen when calculating the 3-way diff patch", retainKeysInOriginal, retainKeysInPatch)
1064                         }
1065                 } else {
1066                         original[retainKeysDirective] = retainKeysInPatch
1067                 }
1068                 return nil
1069         }
1070
1071         retainKeysList, ok := retainKeysInPatch.([]interface{})
1072         if !ok {
1073                 return mergepatch.ErrBadPatchFormatForRetainKeys
1074         }
1075
1076         // validate patch to make sure all fields in the patch are present in the retainKeysList.
1077         // The map is used only as a set, the value is never referenced
1078         m := map[interface{}]struct{}{}
1079         for _, v := range retainKeysList {
1080                 m[v] = struct{}{}
1081         }
1082         for k, v := range patch {
1083                 if v == nil || strings.HasPrefix(k, deleteFromPrimitiveListDirectivePrefix) ||
1084                         strings.HasPrefix(k, setElementOrderDirectivePrefix) {
1085                         continue
1086                 }
1087                 // If there is an item present in the patch but not in the retainKeys list,
1088                 // the patch is invalid.
1089                 if _, found := m[k]; !found {
1090                         return mergepatch.ErrBadPatchFormatForRetainKeys
1091                 }
1092         }
1093
1094         // clear not present fields
1095         for k := range original {
1096                 if _, found := m[k]; !found {
1097                         delete(original, k)
1098                 }
1099         }
1100         return nil
1101 }
1102
1103 // mergePatchIntoOriginal processes $setElementOrder list.
1104 // When not merging the directive, it will make sure $setElementOrder list exist only in original.
1105 // When merging the directive, it will try to find the $setElementOrder list and
1106 // its corresponding patch list, validate it and merge it.
1107 // Then, sort them by the relative order in setElementOrder, patch list and live list.
1108 // The precedence is $setElementOrder > order in patch list > order in live list.
1109 // This function will delete the item after merging it to prevent process it again in the future.
1110 // Ref: https://git.k8s.io/community/contributors/design-proposals/cli/preserve-order-in-strategic-merge-patch.md
1111 func mergePatchIntoOriginal(original, patch map[string]interface{}, schema LookupPatchMeta, mergeOptions MergeOptions) error {
1112         for key, patchV := range patch {
1113                 // Do nothing if there is no ordering directive
1114                 if !strings.HasPrefix(key, setElementOrderDirectivePrefix) {
1115                         continue
1116                 }
1117
1118                 setElementOrderInPatch := patchV
1119                 // Copies directive from the second patch (`patch`) to the first patch (`original`)
1120                 // and checks they are equal and delete the directive in the second patch
1121                 if !mergeOptions.MergeParallelList {
1122                         setElementOrderListInOriginal, ok := original[key]
1123                         if ok {
1124                                 // check if the setElementOrder list in original and the one in patch matches
1125                                 if !reflect.DeepEqual(setElementOrderListInOriginal, setElementOrderInPatch) {
1126                                         return mergepatch.ErrBadPatchFormatForSetElementOrderList
1127                                 }
1128                         } else {
1129                                 // move the setElementOrder list from patch to original
1130                                 original[key] = setElementOrderInPatch
1131                         }
1132                 }
1133                 delete(patch, key)
1134
1135                 var (
1136                         ok                                          bool
1137                         originalFieldValue, patchFieldValue, merged []interface{}
1138                         patchStrategy                               string
1139                         patchMeta                                   PatchMeta
1140                         subschema                                   LookupPatchMeta
1141                 )
1142                 typedSetElementOrderList, ok := setElementOrderInPatch.([]interface{})
1143                 if !ok {
1144                         return mergepatch.ErrBadArgType(typedSetElementOrderList, setElementOrderInPatch)
1145                 }
1146                 // Trim the setElementOrderDirectivePrefix to get the key of the list field in original.
1147                 originalKey, err := extractKey(key, setElementOrderDirectivePrefix)
1148                 if err != nil {
1149                         return err
1150                 }
1151                 // try to find the list with `originalKey` in `original` and `modified` and merge them.
1152                 originalList, foundOriginal := original[originalKey]
1153                 patchList, foundPatch := patch[originalKey]
1154                 if foundOriginal {
1155                         originalFieldValue, ok = originalList.([]interface{})
1156                         if !ok {
1157                                 return mergepatch.ErrBadArgType(originalFieldValue, originalList)
1158                         }
1159                 }
1160                 if foundPatch {
1161                         patchFieldValue, ok = patchList.([]interface{})
1162                         if !ok {
1163                                 return mergepatch.ErrBadArgType(patchFieldValue, patchList)
1164                         }
1165                 }
1166                 subschema, patchMeta, err = schema.LookupPatchMetadataForSlice(originalKey)
1167                 if err != nil {
1168                         return err
1169                 }
1170                 _, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
1171                 if err != nil {
1172                         return err
1173                 }
1174                 // Check for consistency between the element order list and the field it applies to
1175                 err = validatePatchWithSetOrderList(patchFieldValue, typedSetElementOrderList, patchMeta.GetPatchMergeKey())
1176                 if err != nil {
1177                         return err
1178                 }
1179
1180                 switch {
1181                 case foundOriginal && !foundPatch:
1182                         // no change to list contents
1183                         merged = originalFieldValue
1184                 case !foundOriginal && foundPatch:
1185                         // list was added
1186                         merged = patchFieldValue
1187                 case foundOriginal && foundPatch:
1188                         merged, err = mergeSliceHandler(originalList, patchList, subschema,
1189                                 patchStrategy, patchMeta.GetPatchMergeKey(), false, mergeOptions)
1190                         if err != nil {
1191                                 return err
1192                         }
1193                 case !foundOriginal && !foundPatch:
1194                         continue
1195                 }
1196
1197                 // Split all items into patch items and server-only items and then enforce the order.
1198                 var patchItems, serverOnlyItems []interface{}
1199                 if len(patchMeta.GetPatchMergeKey()) == 0 {
1200                         // Primitives doesn't need merge key to do partitioning.
1201                         patchItems, serverOnlyItems = partitionPrimitivesByPresentInList(merged, typedSetElementOrderList)
1202
1203                 } else {
1204                         // Maps need merge key to do partitioning.
1205                         patchItems, serverOnlyItems, err = partitionMapsByPresentInList(merged, typedSetElementOrderList, patchMeta.GetPatchMergeKey())
1206                         if err != nil {
1207                                 return err
1208                         }
1209                 }
1210
1211                 elementType, err := sliceElementType(originalFieldValue, patchFieldValue)
1212                 if err != nil {
1213                         return err
1214                 }
1215                 kind := elementType.Kind()
1216                 // normalize merged list
1217                 // typedSetElementOrderList contains all the relative order in typedPatchList,
1218                 // so don't need to use typedPatchList
1219                 both, err := normalizeElementOrder(patchItems, serverOnlyItems, typedSetElementOrderList, originalFieldValue, patchMeta.GetPatchMergeKey(), kind)
1220                 if err != nil {
1221                         return err
1222                 }
1223                 original[originalKey] = both
1224                 // delete patch list from patch to prevent process again in the future
1225                 delete(patch, originalKey)
1226         }
1227         return nil
1228 }
1229
1230 // partitionPrimitivesByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
1231 func partitionPrimitivesByPresentInList(original, partitionBy []interface{}) ([]interface{}, []interface{}) {
1232         patch := make([]interface{}, 0, len(original))
1233         serverOnly := make([]interface{}, 0, len(original))
1234         inPatch := map[interface{}]bool{}
1235         for _, v := range partitionBy {
1236                 inPatch[v] = true
1237         }
1238         for _, v := range original {
1239                 if !inPatch[v] {
1240                         serverOnly = append(serverOnly, v)
1241                 } else {
1242                         patch = append(patch, v)
1243                 }
1244         }
1245         return patch, serverOnly
1246 }
1247
1248 // partitionMapsByPresentInList partitions elements into 2 slices, the first containing items present in partitionBy, the other not.
1249 func partitionMapsByPresentInList(original, partitionBy []interface{}, mergeKey string) ([]interface{}, []interface{}, error) {
1250         patch := make([]interface{}, 0, len(original))
1251         serverOnly := make([]interface{}, 0, len(original))
1252         for _, v := range original {
1253                 typedV, ok := v.(map[string]interface{})
1254                 if !ok {
1255                         return nil, nil, mergepatch.ErrBadArgType(typedV, v)
1256                 }
1257                 mergeKeyValue, foundMergeKey := typedV[mergeKey]
1258                 if !foundMergeKey {
1259                         return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
1260                 }
1261                 _, _, found, err := findMapInSliceBasedOnKeyValue(partitionBy, mergeKey, mergeKeyValue)
1262                 if err != nil {
1263                         return nil, nil, err
1264                 }
1265                 if !found {
1266                         serverOnly = append(serverOnly, v)
1267                 } else {
1268                         patch = append(patch, v)
1269                 }
1270         }
1271         return patch, serverOnly, nil
1272 }
1273
1274 // Merge fields from a patch map into the original map. Note: This may modify
1275 // both the original map and the patch because getting a deep copy of a map in
1276 // golang is highly non-trivial.
1277 // flag mergeOptions.MergeParallelList controls if using the parallel list to delete or keeping the list.
1278 // If patch contains any null field (e.g. field_1: null) that is not
1279 // present in original, then to propagate it to the end result use
1280 // mergeOptions.IgnoreUnmatchedNulls == false.
1281 func mergeMap(original, patch map[string]interface{}, schema LookupPatchMeta, mergeOptions MergeOptions) (map[string]interface{}, error) {
1282         if v, ok := patch[directiveMarker]; ok {
1283                 return handleDirectiveInMergeMap(v, patch)
1284         }
1285
1286         // nil is an accepted value for original to simplify logic in other places.
1287         // If original is nil, replace it with an empty map and then apply the patch.
1288         if original == nil {
1289                 original = map[string]interface{}{}
1290         }
1291
1292         err := applyRetainKeysDirective(original, patch, mergeOptions)
1293         if err != nil {
1294                 return nil, err
1295         }
1296
1297         // Process $setElementOrder list and other lists sharing the same key.
1298         // When not merging the directive, it will make sure $setElementOrder list exist only in original.
1299         // When merging the directive, it will process $setElementOrder and its patch list together.
1300         // This function will delete the merged elements from patch so they will not be reprocessed
1301         err = mergePatchIntoOriginal(original, patch, schema, mergeOptions)
1302         if err != nil {
1303                 return nil, err
1304         }
1305
1306         // Start merging the patch into the original.
1307         for k, patchV := range patch {
1308                 skipProcessing, isDeleteList, noPrefixKey, err := preprocessDeletionListForMerging(k, original, patchV, mergeOptions.MergeParallelList)
1309                 if err != nil {
1310                         return nil, err
1311                 }
1312                 if skipProcessing {
1313                         continue
1314                 }
1315                 if len(noPrefixKey) > 0 {
1316                         k = noPrefixKey
1317                 }
1318
1319                 // If the value of this key is null, delete the key if it exists in the
1320                 // original. Otherwise, check if we want to preserve it or skip it.
1321                 // Preserving the null value is useful when we want to send an explicit
1322                 // delete to the API server.
1323                 if patchV == nil {
1324                         if _, ok := original[k]; ok {
1325                                 delete(original, k)
1326                         }
1327                         if mergeOptions.IgnoreUnmatchedNulls {
1328                                 continue
1329                         }
1330                 }
1331
1332                 _, ok := original[k]
1333                 if !ok {
1334                         // If it's not in the original document, just take the patch value.
1335                         original[k] = patchV
1336                         continue
1337                 }
1338
1339                 originalType := reflect.TypeOf(original[k])
1340                 patchType := reflect.TypeOf(patchV)
1341                 if originalType != patchType {
1342                         original[k] = patchV
1343                         continue
1344                 }
1345                 // If they're both maps or lists, recurse into the value.
1346                 switch originalType.Kind() {
1347                 case reflect.Map:
1348                         subschema, patchMeta, err2 := schema.LookupPatchMetadataForStruct(k)
1349                         if err2 != nil {
1350                                 return nil, err2
1351                         }
1352                         _, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
1353                         if err2 != nil {
1354                                 return nil, err2
1355                         }
1356                         original[k], err = mergeMapHandler(original[k], patchV, subschema, patchStrategy, mergeOptions)
1357                 case reflect.Slice:
1358                         subschema, patchMeta, err2 := schema.LookupPatchMetadataForSlice(k)
1359                         if err2 != nil {
1360                                 return nil, err2
1361                         }
1362                         _, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
1363                         if err2 != nil {
1364                                 return nil, err2
1365                         }
1366                         original[k], err = mergeSliceHandler(original[k], patchV, subschema, patchStrategy, patchMeta.GetPatchMergeKey(), isDeleteList, mergeOptions)
1367                 default:
1368                         original[k] = patchV
1369                 }
1370                 if err != nil {
1371                         return nil, err
1372                 }
1373         }
1374         return original, nil
1375 }
1376
1377 // mergeMapHandler handles how to merge `patchV` whose key is `key` with `original` respecting
1378 // fieldPatchStrategy and mergeOptions.
1379 func mergeMapHandler(original, patch interface{}, schema LookupPatchMeta,
1380         fieldPatchStrategy string, mergeOptions MergeOptions) (map[string]interface{}, error) {
1381         typedOriginal, typedPatch, err := mapTypeAssertion(original, patch)
1382         if err != nil {
1383                 return nil, err
1384         }
1385
1386         if fieldPatchStrategy != replaceDirective {
1387                 return mergeMap(typedOriginal, typedPatch, schema, mergeOptions)
1388         } else {
1389                 return typedPatch, nil
1390         }
1391 }
1392
1393 // mergeSliceHandler handles how to merge `patchV` whose key is `key` with `original` respecting
1394 // fieldPatchStrategy, fieldPatchMergeKey, isDeleteList and mergeOptions.
1395 func mergeSliceHandler(original, patch interface{}, schema LookupPatchMeta,
1396         fieldPatchStrategy, fieldPatchMergeKey string, isDeleteList bool, mergeOptions MergeOptions) ([]interface{}, error) {
1397         typedOriginal, typedPatch, err := sliceTypeAssertion(original, patch)
1398         if err != nil {
1399                 return nil, err
1400         }
1401
1402         if fieldPatchStrategy == mergeDirective {
1403                 return mergeSlice(typedOriginal, typedPatch, schema, fieldPatchMergeKey, mergeOptions, isDeleteList)
1404         } else {
1405                 return typedPatch, nil
1406         }
1407 }
1408
1409 // Merge two slices together. Note: This may modify both the original slice and
1410 // the patch because getting a deep copy of a slice in golang is highly
1411 // non-trivial.
1412 func mergeSlice(original, patch []interface{}, schema LookupPatchMeta, mergeKey string, mergeOptions MergeOptions, isDeleteList bool) ([]interface{}, error) {
1413         if len(original) == 0 && len(patch) == 0 {
1414                 return original, nil
1415         }
1416
1417         // All the values must be of the same type, but not a list.
1418         t, err := sliceElementType(original, patch)
1419         if err != nil {
1420                 return nil, err
1421         }
1422
1423         var merged []interface{}
1424         kind := t.Kind()
1425         // If the elements are not maps, merge the slices of scalars.
1426         if kind != reflect.Map {
1427                 if mergeOptions.MergeParallelList && isDeleteList {
1428                         return deleteFromSlice(original, patch), nil
1429                 }
1430                 // Maybe in the future add a "concat" mode that doesn't
1431                 // deduplicate.
1432                 both := append(original, patch...)
1433                 merged = deduplicateScalars(both)
1434
1435         } else {
1436                 if mergeKey == "" {
1437                         return nil, fmt.Errorf("cannot merge lists without merge key for %s", schema.Name())
1438                 }
1439
1440                 original, patch, err = mergeSliceWithSpecialElements(original, patch, mergeKey)
1441                 if err != nil {
1442                         return nil, err
1443                 }
1444
1445                 merged, err = mergeSliceWithoutSpecialElements(original, patch, mergeKey, schema, mergeOptions)
1446                 if err != nil {
1447                         return nil, err
1448                 }
1449         }
1450
1451         // enforce the order
1452         var patchItems, serverOnlyItems []interface{}
1453         if len(mergeKey) == 0 {
1454                 patchItems, serverOnlyItems = partitionPrimitivesByPresentInList(merged, patch)
1455         } else {
1456                 patchItems, serverOnlyItems, err = partitionMapsByPresentInList(merged, patch, mergeKey)
1457                 if err != nil {
1458                         return nil, err
1459                 }
1460         }
1461         return normalizeElementOrder(patchItems, serverOnlyItems, patch, original, mergeKey, kind)
1462 }
1463
1464 // mergeSliceWithSpecialElements handles special elements with directiveMarker
1465 // before merging the slices. It returns a updated `original` and a patch without special elements.
1466 // original and patch must be slices of maps, they should be checked before calling this function.
1467 func mergeSliceWithSpecialElements(original, patch []interface{}, mergeKey string) ([]interface{}, []interface{}, error) {
1468         patchWithoutSpecialElements := []interface{}{}
1469         replace := false
1470         for _, v := range patch {
1471                 typedV := v.(map[string]interface{})
1472                 patchType, ok := typedV[directiveMarker]
1473                 if !ok {
1474                         patchWithoutSpecialElements = append(patchWithoutSpecialElements, v)
1475                 } else {
1476                         switch patchType {
1477                         case deleteDirective:
1478                                 mergeValue, ok := typedV[mergeKey]
1479                                 if ok {
1480                                         var err error
1481                                         original, err = deleteMatchingEntries(original, mergeKey, mergeValue)
1482                                         if err != nil {
1483                                                 return nil, nil, err
1484                                         }
1485                                 } else {
1486                                         return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
1487                                 }
1488                         case replaceDirective:
1489                                 replace = true
1490                                 // Continue iterating through the array to prune any other $patch elements.
1491                         case mergeDirective:
1492                                 return nil, nil, fmt.Errorf("merging lists cannot yet be specified in the patch")
1493                         default:
1494                                 return nil, nil, mergepatch.ErrBadPatchType(patchType, typedV)
1495                         }
1496                 }
1497         }
1498         if replace {
1499                 return patchWithoutSpecialElements, nil, nil
1500         }
1501         return original, patchWithoutSpecialElements, nil
1502 }
1503
1504 // delete all matching entries (based on merge key) from a merging list
1505 func deleteMatchingEntries(original []interface{}, mergeKey string, mergeValue interface{}) ([]interface{}, error) {
1506         for {
1507                 _, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
1508                 if err != nil {
1509                         return nil, err
1510                 }
1511
1512                 if !found {
1513                         break
1514                 }
1515                 // Delete the element at originalKey.
1516                 original = append(original[:originalKey], original[originalKey+1:]...)
1517         }
1518         return original, nil
1519 }
1520
1521 // mergeSliceWithoutSpecialElements merges slices with non-special elements.
1522 // original and patch must be slices of maps, they should be checked before calling this function.
1523 func mergeSliceWithoutSpecialElements(original, patch []interface{}, mergeKey string, schema LookupPatchMeta, mergeOptions MergeOptions) ([]interface{}, error) {
1524         for _, v := range patch {
1525                 typedV := v.(map[string]interface{})
1526                 mergeValue, ok := typedV[mergeKey]
1527                 if !ok {
1528                         return nil, mergepatch.ErrNoMergeKey(typedV, mergeKey)
1529                 }
1530
1531                 // If we find a value with this merge key value in original, merge the
1532                 // maps. Otherwise append onto original.
1533                 originalMap, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
1534                 if err != nil {
1535                         return nil, err
1536                 }
1537
1538                 if found {
1539                         var mergedMaps interface{}
1540                         var err error
1541                         // Merge into original.
1542                         mergedMaps, err = mergeMap(originalMap, typedV, schema, mergeOptions)
1543                         if err != nil {
1544                                 return nil, err
1545                         }
1546
1547                         original[originalKey] = mergedMaps
1548                 } else {
1549                         original = append(original, v)
1550                 }
1551         }
1552         return original, nil
1553 }
1554
1555 // deleteFromSlice uses the parallel list to delete the items in a list of scalars
1556 func deleteFromSlice(current, toDelete []interface{}) []interface{} {
1557         toDeleteMap := map[interface{}]interface{}{}
1558         processed := make([]interface{}, 0, len(current))
1559         for _, v := range toDelete {
1560                 toDeleteMap[v] = true
1561         }
1562         for _, v := range current {
1563                 if _, found := toDeleteMap[v]; !found {
1564                         processed = append(processed, v)
1565                 }
1566         }
1567         return processed
1568 }
1569
1570 // This method no longer panics if any element of the slice is not a map.
1571 func findMapInSliceBasedOnKeyValue(m []interface{}, key string, value interface{}) (map[string]interface{}, int, bool, error) {
1572         for k, v := range m {
1573                 typedV, ok := v.(map[string]interface{})
1574                 if !ok {
1575                         return nil, 0, false, fmt.Errorf("value for key %v is not a map", k)
1576                 }
1577
1578                 valueToMatch, ok := typedV[key]
1579                 if ok && valueToMatch == value {
1580                         return typedV, k, true, nil
1581                 }
1582         }
1583
1584         return nil, 0, false, nil
1585 }
1586
1587 // This function takes a JSON map and sorts all the lists that should be merged
1588 // by key. This is needed by tests because in JSON, list order is significant,
1589 // but in Strategic Merge Patch, merge lists do not have significant order.
1590 // Sorting the lists allows for order-insensitive comparison of patched maps.
1591 func sortMergeListsByName(mapJSON []byte, schema LookupPatchMeta) ([]byte, error) {
1592         var m map[string]interface{}
1593         err := json.Unmarshal(mapJSON, &m)
1594         if err != nil {
1595                 return nil, mergepatch.ErrBadJSONDoc
1596         }
1597
1598         newM, err := sortMergeListsByNameMap(m, schema)
1599         if err != nil {
1600                 return nil, err
1601         }
1602
1603         return json.Marshal(newM)
1604 }
1605
1606 // Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in a map.
1607 func sortMergeListsByNameMap(s map[string]interface{}, schema LookupPatchMeta) (map[string]interface{}, error) {
1608         newS := map[string]interface{}{}
1609         for k, v := range s {
1610                 if k == retainKeysDirective {
1611                         typedV, ok := v.([]interface{})
1612                         if !ok {
1613                                 return nil, mergepatch.ErrBadPatchFormatForRetainKeys
1614                         }
1615                         v = sortScalars(typedV)
1616                 } else if strings.HasPrefix(k, deleteFromPrimitiveListDirectivePrefix) {
1617                         typedV, ok := v.([]interface{})
1618                         if !ok {
1619                                 return nil, mergepatch.ErrBadPatchFormatForPrimitiveList
1620                         }
1621                         v = sortScalars(typedV)
1622                 } else if strings.HasPrefix(k, setElementOrderDirectivePrefix) {
1623                         _, ok := v.([]interface{})
1624                         if !ok {
1625                                 return nil, mergepatch.ErrBadPatchFormatForSetElementOrderList
1626                         }
1627                 } else if k != directiveMarker {
1628                         // recurse for map and slice.
1629                         switch typedV := v.(type) {
1630                         case map[string]interface{}:
1631                                 subschema, _, err := schema.LookupPatchMetadataForStruct(k)
1632                                 if err != nil {
1633                                         return nil, err
1634                                 }
1635                                 v, err = sortMergeListsByNameMap(typedV, subschema)
1636                                 if err != nil {
1637                                         return nil, err
1638                                 }
1639                         case []interface{}:
1640                                 subschema, patchMeta, err := schema.LookupPatchMetadataForSlice(k)
1641                                 if err != nil {
1642                                         return nil, err
1643                                 }
1644                                 _, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies())
1645                                 if err != nil {
1646                                         return nil, err
1647                                 }
1648                                 if patchStrategy == mergeDirective {
1649                                         var err error
1650                                         v, err = sortMergeListsByNameArray(typedV, subschema, patchMeta.GetPatchMergeKey(), true)
1651                                         if err != nil {
1652                                                 return nil, err
1653                                         }
1654                                 }
1655                         }
1656                 }
1657
1658                 newS[k] = v
1659         }
1660
1661         return newS, nil
1662 }
1663
1664 // Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in an array.
1665 func sortMergeListsByNameArray(s []interface{}, schema LookupPatchMeta, mergeKey string, recurse bool) ([]interface{}, error) {
1666         if len(s) == 0 {
1667                 return s, nil
1668         }
1669
1670         // We don't support lists of lists yet.
1671         t, err := sliceElementType(s)
1672         if err != nil {
1673                 return nil, err
1674         }
1675
1676         // If the elements are not maps...
1677         if t.Kind() != reflect.Map {
1678                 // Sort the elements, because they may have been merged out of order.
1679                 return deduplicateAndSortScalars(s), nil
1680         }
1681
1682         // Elements are maps - if one of the keys of the map is a map or a
1683         // list, we may need to recurse into it.
1684         newS := []interface{}{}
1685         for _, elem := range s {
1686                 if recurse {
1687                         typedElem := elem.(map[string]interface{})
1688                         newElem, err := sortMergeListsByNameMap(typedElem, schema)
1689                         if err != nil {
1690                                 return nil, err
1691                         }
1692
1693                         newS = append(newS, newElem)
1694                 } else {
1695                         newS = append(newS, elem)
1696                 }
1697         }
1698
1699         // Sort the maps.
1700         newS = sortMapsBasedOnField(newS, mergeKey)
1701         return newS, nil
1702 }
1703
1704 func sortMapsBasedOnField(m []interface{}, fieldName string) []interface{} {
1705         mapM := mapSliceFromSlice(m)
1706         ss := SortableSliceOfMaps{mapM, fieldName}
1707         sort.Sort(ss)
1708         newS := sliceFromMapSlice(ss.s)
1709         return newS
1710 }
1711
1712 func mapSliceFromSlice(m []interface{}) []map[string]interface{} {
1713         newM := []map[string]interface{}{}
1714         for _, v := range m {
1715                 vt := v.(map[string]interface{})
1716                 newM = append(newM, vt)
1717         }
1718
1719         return newM
1720 }
1721
1722 func sliceFromMapSlice(s []map[string]interface{}) []interface{} {
1723         newS := []interface{}{}
1724         for _, v := range s {
1725                 newS = append(newS, v)
1726         }
1727
1728         return newS
1729 }
1730
1731 type SortableSliceOfMaps struct {
1732         s []map[string]interface{}
1733         k string // key to sort on
1734 }
1735
1736 func (ss SortableSliceOfMaps) Len() int {
1737         return len(ss.s)
1738 }
1739
1740 func (ss SortableSliceOfMaps) Less(i, j int) bool {
1741         iStr := fmt.Sprintf("%v", ss.s[i][ss.k])
1742         jStr := fmt.Sprintf("%v", ss.s[j][ss.k])
1743         return sort.StringsAreSorted([]string{iStr, jStr})
1744 }
1745
1746 func (ss SortableSliceOfMaps) Swap(i, j int) {
1747         tmp := ss.s[i]
1748         ss.s[i] = ss.s[j]
1749         ss.s[j] = tmp
1750 }
1751
1752 func deduplicateAndSortScalars(s []interface{}) []interface{} {
1753         s = deduplicateScalars(s)
1754         return sortScalars(s)
1755 }
1756
1757 func sortScalars(s []interface{}) []interface{} {
1758         ss := SortableSliceOfScalars{s}
1759         sort.Sort(ss)
1760         return ss.s
1761 }
1762
1763 func deduplicateScalars(s []interface{}) []interface{} {
1764         // Clever algorithm to deduplicate.
1765         length := len(s) - 1
1766         for i := 0; i < length; i++ {
1767                 for j := i + 1; j <= length; j++ {
1768                         if s[i] == s[j] {
1769                                 s[j] = s[length]
1770                                 s = s[0:length]
1771                                 length--
1772                                 j--
1773                         }
1774                 }
1775         }
1776
1777         return s
1778 }
1779
1780 type SortableSliceOfScalars struct {
1781         s []interface{}
1782 }
1783
1784 func (ss SortableSliceOfScalars) Len() int {
1785         return len(ss.s)
1786 }
1787
1788 func (ss SortableSliceOfScalars) Less(i, j int) bool {
1789         iStr := fmt.Sprintf("%v", ss.s[i])
1790         jStr := fmt.Sprintf("%v", ss.s[j])
1791         return sort.StringsAreSorted([]string{iStr, jStr})
1792 }
1793
1794 func (ss SortableSliceOfScalars) Swap(i, j int) {
1795         tmp := ss.s[i]
1796         ss.s[i] = ss.s[j]
1797         ss.s[j] = tmp
1798 }
1799
1800 // Returns the type of the elements of N slice(s). If the type is different,
1801 // another slice or undefined, returns an error.
1802 func sliceElementType(slices ...[]interface{}) (reflect.Type, error) {
1803         var prevType reflect.Type
1804         for _, s := range slices {
1805                 // Go through elements of all given slices and make sure they are all the same type.
1806                 for _, v := range s {
1807                         currentType := reflect.TypeOf(v)
1808                         if prevType == nil {
1809                                 prevType = currentType
1810                                 // We don't support lists of lists yet.
1811                                 if prevType.Kind() == reflect.Slice {
1812                                         return nil, mergepatch.ErrNoListOfLists
1813                                 }
1814                         } else {
1815                                 if prevType != currentType {
1816                                         return nil, fmt.Errorf("list element types are not identical: %v", fmt.Sprint(slices))
1817                                 }
1818                                 prevType = currentType
1819                         }
1820                 }
1821         }
1822
1823         if prevType == nil {
1824                 return nil, fmt.Errorf("no elements in any of the given slices")
1825         }
1826
1827         return prevType, nil
1828 }
1829
1830 // MergingMapsHaveConflicts returns true if the left and right JSON interface
1831 // objects overlap with different values in any key. All keys are required to be
1832 // strings. Since patches of the same Type have congruent keys, this is valid
1833 // for multiple patch types. This method supports strategic merge patch semantics.
1834 func MergingMapsHaveConflicts(left, right map[string]interface{}, schema LookupPatchMeta) (bool, error) {
1835         return mergingMapFieldsHaveConflicts(left, right, schema, "", "")
1836 }
1837
1838 func mergingMapFieldsHaveConflicts(
1839         left, right interface{},
1840         schema LookupPatchMeta,
1841         fieldPatchStrategy, fieldPatchMergeKey string,
1842 ) (bool, error) {
1843         switch leftType := left.(type) {
1844         case map[string]interface{}:
1845                 rightType, ok := right.(map[string]interface{})
1846                 if !ok {
1847                         return true, nil
1848                 }
1849                 leftMarker, okLeft := leftType[directiveMarker]
1850                 rightMarker, okRight := rightType[directiveMarker]
1851                 // if one or the other has a directive marker,
1852                 // then we need to consider that before looking at the individual keys,
1853                 // since a directive operates on the whole map.
1854                 if okLeft || okRight {
1855                         // if one has a directive marker and the other doesn't,
1856                         // then we have a conflict, since one is deleting or replacing the whole map,
1857                         // and the other is doing things to individual keys.
1858                         if okLeft != okRight {
1859                                 return true, nil
1860                         }
1861                         // if they both have markers, but they are not the same directive,
1862                         // then we have a conflict because they're doing different things to the map.
1863                         if leftMarker != rightMarker {
1864                                 return true, nil
1865                         }
1866                 }
1867                 if fieldPatchStrategy == replaceDirective {
1868                         return false, nil
1869                 }
1870                 // Check the individual keys.
1871                 return mapsHaveConflicts(leftType, rightType, schema)
1872
1873         case []interface{}:
1874                 rightType, ok := right.([]interface{})
1875                 if !ok {
1876                         return true, nil
1877                 }
1878                 return slicesHaveConflicts(leftType, rightType, schema, fieldPatchStrategy, fieldPatchMergeKey)
1879         case string, float64, bool, int64, nil:
1880                 return !reflect.DeepEqual(left, right), nil
1881         default:
1882                 return true, fmt.Errorf("unknown type: %v", reflect.TypeOf(left))
1883         }
1884 }
1885
1886 func mapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) {
1887         for key, leftValue := range typedLeft {
1888                 if key != directiveMarker && key != retainKeysDirective {
1889                         if rightValue, ok := typedRight[key]; ok {
1890                                 var subschema LookupPatchMeta
1891                                 var patchMeta PatchMeta
1892                                 var patchStrategy string
1893                                 var err error
1894                                 switch leftValue.(type) {
1895                                 case []interface{}:
1896                                         subschema, patchMeta, err = schema.LookupPatchMetadataForSlice(key)
1897                                         if err != nil {
1898                                                 return true, err
1899                                         }
1900                                         _, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies)
1901                                         if err != nil {
1902                                                 return true, err
1903                                         }
1904                                 case map[string]interface{}:
1905                                         subschema, patchMeta, err = schema.LookupPatchMetadataForStruct(key)
1906                                         if err != nil {
1907                                                 return true, err
1908                                         }
1909                                         _, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies)
1910                                         if err != nil {
1911                                                 return true, err
1912                                         }
1913                                 }
1914
1915                                 if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue,
1916                                         subschema, patchStrategy, patchMeta.GetPatchMergeKey()); hasConflicts {
1917                                         return true, err
1918                                 }
1919                         }
1920                 }
1921         }
1922
1923         return false, nil
1924 }
1925
1926 func slicesHaveConflicts(
1927         typedLeft, typedRight []interface{},
1928         schema LookupPatchMeta,
1929         fieldPatchStrategy, fieldPatchMergeKey string,
1930 ) (bool, error) {
1931         elementType, err := sliceElementType(typedLeft, typedRight)
1932         if err != nil {
1933                 return true, err
1934         }
1935
1936         if fieldPatchStrategy == mergeDirective {
1937                 // Merging lists of scalars have no conflicts by definition
1938                 // So we only need to check further if the elements are maps
1939                 if elementType.Kind() != reflect.Map {
1940                         return false, nil
1941                 }
1942
1943                 // Build a map for each slice and then compare the two maps
1944                 leftMap, err := sliceOfMapsToMapOfMaps(typedLeft, fieldPatchMergeKey)
1945                 if err != nil {
1946                         return true, err
1947                 }
1948
1949                 rightMap, err := sliceOfMapsToMapOfMaps(typedRight, fieldPatchMergeKey)
1950                 if err != nil {
1951                         return true, err
1952                 }
1953
1954                 return mapsOfMapsHaveConflicts(leftMap, rightMap, schema)
1955         }
1956
1957         // Either we don't have type information, or these are non-merging lists
1958         if len(typedLeft) != len(typedRight) {
1959                 return true, nil
1960         }
1961
1962         // Sort scalar slices to prevent ordering issues
1963         // We have no way to sort non-merging lists of maps
1964         if elementType.Kind() != reflect.Map {
1965                 typedLeft = deduplicateAndSortScalars(typedLeft)
1966                 typedRight = deduplicateAndSortScalars(typedRight)
1967         }
1968
1969         // Compare the slices element by element in order
1970         // This test will fail if the slices are not sorted
1971         for i := range typedLeft {
1972                 if hasConflicts, err := mergingMapFieldsHaveConflicts(typedLeft[i], typedRight[i], schema, "", ""); hasConflicts {
1973                         return true, err
1974                 }
1975         }
1976
1977         return false, nil
1978 }
1979
1980 func sliceOfMapsToMapOfMaps(slice []interface{}, mergeKey string) (map[string]interface{}, error) {
1981         result := make(map[string]interface{}, len(slice))
1982         for _, value := range slice {
1983                 typedValue, ok := value.(map[string]interface{})
1984                 if !ok {
1985                         return nil, fmt.Errorf("invalid element type in merging list:%v", slice)
1986                 }
1987
1988                 mergeValue, ok := typedValue[mergeKey]
1989                 if !ok {
1990                         return nil, fmt.Errorf("cannot find merge key `%s` in merging list element:%v", mergeKey, typedValue)
1991                 }
1992
1993                 result[fmt.Sprintf("%s", mergeValue)] = typedValue
1994         }
1995
1996         return result, nil
1997 }
1998
1999 func mapsOfMapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) {
2000         for key, leftValue := range typedLeft {
2001                 if rightValue, ok := typedRight[key]; ok {
2002                         if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue, schema, "", ""); hasConflicts {
2003                                 return true, err
2004                         }
2005                 }
2006         }
2007
2008         return false, nil
2009 }
2010
2011 // CreateThreeWayMergePatch reconciles a modified configuration with an original configuration,
2012 // while preserving any changes or deletions made to the original configuration in the interim,
2013 // and not overridden by the current configuration. All three documents must be passed to the
2014 // method as json encoded content. It will return a strategic merge patch, or an error if any
2015 // of the documents is invalid, or if there are any preconditions that fail against the modified
2016 // configuration, or, if overwrite is false and there are conflicts between the modified and current
2017 // configurations. Conflicts are defined as keys changed differently from original to modified
2018 // than from original to current. In other words, a conflict occurs if modified changes any key
2019 // in a way that is different from how it is changed in current (e.g., deleting it, changing its
2020 // value). We also propagate values fields that do not exist in original but are explicitly
2021 // defined in modified.
2022 func CreateThreeWayMergePatch(original, modified, current []byte, schema LookupPatchMeta, overwrite bool, fns ...mergepatch.PreconditionFunc) ([]byte, error) {
2023         originalMap := map[string]interface{}{}
2024         if len(original) > 0 {
2025                 if err := json.Unmarshal(original, &originalMap); err != nil {
2026                         return nil, mergepatch.ErrBadJSONDoc
2027                 }
2028         }
2029
2030         modifiedMap := map[string]interface{}{}
2031         if len(modified) > 0 {
2032                 if err := json.Unmarshal(modified, &modifiedMap); err != nil {
2033                         return nil, mergepatch.ErrBadJSONDoc
2034                 }
2035         }
2036
2037         currentMap := map[string]interface{}{}
2038         if len(current) > 0 {
2039                 if err := json.Unmarshal(current, &currentMap); err != nil {
2040                         return nil, mergepatch.ErrBadJSONDoc
2041                 }
2042         }
2043
2044         // The patch is the difference from current to modified without deletions, plus deletions
2045         // from original to modified. To find it, we compute deletions, which are the deletions from
2046         // original to modified, and delta, which is the difference from current to modified without
2047         // deletions, and then apply delta to deletions as a patch, which should be strictly additive.
2048         deltaMapDiffOptions := DiffOptions{
2049                 IgnoreDeletions: true,
2050                 SetElementOrder: true,
2051         }
2052         deltaMap, err := diffMaps(currentMap, modifiedMap, schema, deltaMapDiffOptions)
2053         if err != nil {
2054                 return nil, err
2055         }
2056         deletionsMapDiffOptions := DiffOptions{
2057                 SetElementOrder:           true,
2058                 IgnoreChangesAndAdditions: true,
2059         }
2060         deletionsMap, err := diffMaps(originalMap, modifiedMap, schema, deletionsMapDiffOptions)
2061         if err != nil {
2062                 return nil, err
2063         }
2064
2065         mergeOptions := MergeOptions{}
2066         patchMap, err := mergeMap(deletionsMap, deltaMap, schema, mergeOptions)
2067         if err != nil {
2068                 return nil, err
2069         }
2070
2071         // Apply the preconditions to the patch, and return an error if any of them fail.
2072         for _, fn := range fns {
2073                 if !fn(patchMap) {
2074                         return nil, mergepatch.NewErrPreconditionFailed(patchMap)
2075                 }
2076         }
2077
2078         // If overwrite is false, and the patch contains any keys that were changed differently,
2079         // then return a conflict error.
2080         if !overwrite {
2081                 changeMapDiffOptions := DiffOptions{}
2082                 changedMap, err := diffMaps(originalMap, currentMap, schema, changeMapDiffOptions)
2083                 if err != nil {
2084                         return nil, err
2085                 }
2086
2087                 hasConflicts, err := MergingMapsHaveConflicts(patchMap, changedMap, schema)
2088                 if err != nil {
2089                         return nil, err
2090                 }
2091
2092                 if hasConflicts {
2093                         return nil, mergepatch.NewErrConflict(mergepatch.ToYAMLOrError(patchMap), mergepatch.ToYAMLOrError(changedMap))
2094                 }
2095         }
2096
2097         return json.Marshal(patchMap)
2098 }
2099
2100 func ItemAddedToModifiedSlice(original, modified string) bool { return original > modified }
2101
2102 func ItemRemovedFromModifiedSlice(original, modified string) bool { return original < modified }
2103
2104 func ItemMatchesOriginalAndModifiedSlice(original, modified string) bool { return original == modified }
2105
2106 func CreateDeleteDirective(mergeKey string, mergeKeyValue interface{}) map[string]interface{} {
2107         return map[string]interface{}{mergeKey: mergeKeyValue, directiveMarker: deleteDirective}
2108 }
2109
2110 func mapTypeAssertion(original, patch interface{}) (map[string]interface{}, map[string]interface{}, error) {
2111         typedOriginal, ok := original.(map[string]interface{})
2112         if !ok {
2113                 return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original)
2114         }
2115         typedPatch, ok := patch.(map[string]interface{})
2116         if !ok {
2117                 return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch)
2118         }
2119         return typedOriginal, typedPatch, nil
2120 }
2121
2122 func sliceTypeAssertion(original, patch interface{}) ([]interface{}, []interface{}, error) {
2123         typedOriginal, ok := original.([]interface{})
2124         if !ok {
2125                 return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original)
2126         }
2127         typedPatch, ok := patch.([]interface{})
2128         if !ok {
2129                 return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch)
2130         }
2131         return typedOriginal, typedPatch, nil
2132 }
2133
2134 // extractRetainKeysPatchStrategy process patch strategy, which is a string may contains multiple
2135 // patch strategies separated by ",". It returns a boolean var indicating if it has
2136 // retainKeys strategies and a string for the other strategy.
2137 func extractRetainKeysPatchStrategy(strategies []string) (bool, string, error) {
2138         switch len(strategies) {
2139         case 0:
2140                 return false, "", nil
2141         case 1:
2142                 singleStrategy := strategies[0]
2143                 switch singleStrategy {
2144                 case retainKeysStrategy:
2145                         return true, "", nil
2146                 default:
2147                         return false, singleStrategy, nil
2148                 }
2149         case 2:
2150                 switch {
2151                 case strategies[0] == retainKeysStrategy:
2152                         return true, strategies[1], nil
2153                 case strategies[1] == retainKeysStrategy:
2154                         return true, strategies[0], nil
2155                 default:
2156                         return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies)
2157                 }
2158         default:
2159                 return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies)
2160         }
2161 }
2162
2163 // hasAdditionalNewField returns if original map has additional key with non-nil value than modified.
2164 func hasAdditionalNewField(original, modified map[string]interface{}) bool {
2165         for k, v := range original {
2166                 if v == nil {
2167                         continue
2168                 }
2169                 if _, found := modified[k]; !found {
2170                         return true
2171                 }
2172         }
2173         return false
2174 }