1/* 2Copyright 2014 The Kubernetes Authors. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package strategicpatch 18 19import ( 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 40const ( 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. 58type JSONMap map[string]interface{} 59 60type 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 75type 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. 94func 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 103func 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. 130func 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 139func 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 168func 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 237func 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. 261func 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. 304func 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 350func 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 368func 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. 382func 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`. 404func 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. 427func 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. 471func 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. 502func 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` 521func 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. 551func 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 618func 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 635func 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 691func 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 717func 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. 796func 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. 812func 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 821func 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 839func 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. 856func 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 875func 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. 890func 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. 907func 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 925func 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 935func 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 959func 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). 977func 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 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 1027func 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 1048func 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 1111func 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. 1231func 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. 1249func 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. 1281func 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 delete(original, k) 1325 if mergeOptions.IgnoreUnmatchedNulls { 1326 continue 1327 } 1328 } 1329 1330 _, ok := original[k] 1331 if !ok { 1332 // If it's not in the original document, just take the patch value. 1333 original[k] = patchV 1334 continue 1335 } 1336 1337 originalType := reflect.TypeOf(original[k]) 1338 patchType := reflect.TypeOf(patchV) 1339 if originalType != patchType { 1340 original[k] = patchV 1341 continue 1342 } 1343 // If they're both maps or lists, recurse into the value. 1344 switch originalType.Kind() { 1345 case reflect.Map: 1346 subschema, patchMeta, err2 := schema.LookupPatchMetadataForStruct(k) 1347 if err2 != nil { 1348 return nil, err2 1349 } 1350 _, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies()) 1351 if err2 != nil { 1352 return nil, err2 1353 } 1354 original[k], err = mergeMapHandler(original[k], patchV, subschema, patchStrategy, mergeOptions) 1355 case reflect.Slice: 1356 subschema, patchMeta, err2 := schema.LookupPatchMetadataForSlice(k) 1357 if err2 != nil { 1358 return nil, err2 1359 } 1360 _, patchStrategy, err2 := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies()) 1361 if err2 != nil { 1362 return nil, err2 1363 } 1364 original[k], err = mergeSliceHandler(original[k], patchV, subschema, patchStrategy, patchMeta.GetPatchMergeKey(), isDeleteList, mergeOptions) 1365 default: 1366 original[k] = patchV 1367 } 1368 if err != nil { 1369 return nil, err 1370 } 1371 } 1372 return original, nil 1373} 1374 1375// mergeMapHandler handles how to merge `patchV` whose key is `key` with `original` respecting 1376// fieldPatchStrategy and mergeOptions. 1377func mergeMapHandler(original, patch interface{}, schema LookupPatchMeta, 1378 fieldPatchStrategy string, mergeOptions MergeOptions) (map[string]interface{}, error) { 1379 typedOriginal, typedPatch, err := mapTypeAssertion(original, patch) 1380 if err != nil { 1381 return nil, err 1382 } 1383 1384 if fieldPatchStrategy != replaceDirective { 1385 return mergeMap(typedOriginal, typedPatch, schema, mergeOptions) 1386 } else { 1387 return typedPatch, nil 1388 } 1389} 1390 1391// mergeSliceHandler handles how to merge `patchV` whose key is `key` with `original` respecting 1392// fieldPatchStrategy, fieldPatchMergeKey, isDeleteList and mergeOptions. 1393func mergeSliceHandler(original, patch interface{}, schema LookupPatchMeta, 1394 fieldPatchStrategy, fieldPatchMergeKey string, isDeleteList bool, mergeOptions MergeOptions) ([]interface{}, error) { 1395 typedOriginal, typedPatch, err := sliceTypeAssertion(original, patch) 1396 if err != nil { 1397 return nil, err 1398 } 1399 1400 if fieldPatchStrategy == mergeDirective { 1401 return mergeSlice(typedOriginal, typedPatch, schema, fieldPatchMergeKey, mergeOptions, isDeleteList) 1402 } else { 1403 return typedPatch, nil 1404 } 1405} 1406 1407// Merge two slices together. Note: This may modify both the original slice and 1408// the patch because getting a deep copy of a slice in golang is highly 1409// non-trivial. 1410func mergeSlice(original, patch []interface{}, schema LookupPatchMeta, mergeKey string, mergeOptions MergeOptions, isDeleteList bool) ([]interface{}, error) { 1411 if len(original) == 0 && len(patch) == 0 { 1412 return original, nil 1413 } 1414 1415 // All the values must be of the same type, but not a list. 1416 t, err := sliceElementType(original, patch) 1417 if err != nil { 1418 return nil, err 1419 } 1420 1421 var merged []interface{} 1422 kind := t.Kind() 1423 // If the elements are not maps, merge the slices of scalars. 1424 if kind != reflect.Map { 1425 if mergeOptions.MergeParallelList && isDeleteList { 1426 return deleteFromSlice(original, patch), nil 1427 } 1428 // Maybe in the future add a "concat" mode that doesn't 1429 // deduplicate. 1430 both := append(original, patch...) 1431 merged = deduplicateScalars(both) 1432 1433 } else { 1434 if mergeKey == "" { 1435 return nil, fmt.Errorf("cannot merge lists without merge key for %s", schema.Name()) 1436 } 1437 1438 original, patch, err = mergeSliceWithSpecialElements(original, patch, mergeKey) 1439 if err != nil { 1440 return nil, err 1441 } 1442 1443 merged, err = mergeSliceWithoutSpecialElements(original, patch, mergeKey, schema, mergeOptions) 1444 if err != nil { 1445 return nil, err 1446 } 1447 } 1448 1449 // enforce the order 1450 var patchItems, serverOnlyItems []interface{} 1451 if len(mergeKey) == 0 { 1452 patchItems, serverOnlyItems = partitionPrimitivesByPresentInList(merged, patch) 1453 } else { 1454 patchItems, serverOnlyItems, err = partitionMapsByPresentInList(merged, patch, mergeKey) 1455 if err != nil { 1456 return nil, err 1457 } 1458 } 1459 return normalizeElementOrder(patchItems, serverOnlyItems, patch, original, mergeKey, kind) 1460} 1461 1462// mergeSliceWithSpecialElements handles special elements with directiveMarker 1463// before merging the slices. It returns a updated `original` and a patch without special elements. 1464// original and patch must be slices of maps, they should be checked before calling this function. 1465func mergeSliceWithSpecialElements(original, patch []interface{}, mergeKey string) ([]interface{}, []interface{}, error) { 1466 patchWithoutSpecialElements := []interface{}{} 1467 replace := false 1468 for _, v := range patch { 1469 typedV := v.(map[string]interface{}) 1470 patchType, ok := typedV[directiveMarker] 1471 if !ok { 1472 patchWithoutSpecialElements = append(patchWithoutSpecialElements, v) 1473 } else { 1474 switch patchType { 1475 case deleteDirective: 1476 mergeValue, ok := typedV[mergeKey] 1477 if ok { 1478 var err error 1479 original, err = deleteMatchingEntries(original, mergeKey, mergeValue) 1480 if err != nil { 1481 return nil, nil, err 1482 } 1483 } else { 1484 return nil, nil, mergepatch.ErrNoMergeKey(typedV, mergeKey) 1485 } 1486 case replaceDirective: 1487 replace = true 1488 // Continue iterating through the array to prune any other $patch elements. 1489 case mergeDirective: 1490 return nil, nil, fmt.Errorf("merging lists cannot yet be specified in the patch") 1491 default: 1492 return nil, nil, mergepatch.ErrBadPatchType(patchType, typedV) 1493 } 1494 } 1495 } 1496 if replace { 1497 return patchWithoutSpecialElements, nil, nil 1498 } 1499 return original, patchWithoutSpecialElements, nil 1500} 1501 1502// delete all matching entries (based on merge key) from a merging list 1503func deleteMatchingEntries(original []interface{}, mergeKey string, mergeValue interface{}) ([]interface{}, error) { 1504 for { 1505 _, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue) 1506 if err != nil { 1507 return nil, err 1508 } 1509 1510 if !found { 1511 break 1512 } 1513 // Delete the element at originalKey. 1514 original = append(original[:originalKey], original[originalKey+1:]...) 1515 } 1516 return original, nil 1517} 1518 1519// mergeSliceWithoutSpecialElements merges slices with non-special elements. 1520// original and patch must be slices of maps, they should be checked before calling this function. 1521func mergeSliceWithoutSpecialElements(original, patch []interface{}, mergeKey string, schema LookupPatchMeta, mergeOptions MergeOptions) ([]interface{}, error) { 1522 for _, v := range patch { 1523 typedV := v.(map[string]interface{}) 1524 mergeValue, ok := typedV[mergeKey] 1525 if !ok { 1526 return nil, mergepatch.ErrNoMergeKey(typedV, mergeKey) 1527 } 1528 1529 // If we find a value with this merge key value in original, merge the 1530 // maps. Otherwise append onto original. 1531 originalMap, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue) 1532 if err != nil { 1533 return nil, err 1534 } 1535 1536 if found { 1537 var mergedMaps interface{} 1538 var err error 1539 // Merge into original. 1540 mergedMaps, err = mergeMap(originalMap, typedV, schema, mergeOptions) 1541 if err != nil { 1542 return nil, err 1543 } 1544 1545 original[originalKey] = mergedMaps 1546 } else { 1547 original = append(original, v) 1548 } 1549 } 1550 return original, nil 1551} 1552 1553// deleteFromSlice uses the parallel list to delete the items in a list of scalars 1554func deleteFromSlice(current, toDelete []interface{}) []interface{} { 1555 toDeleteMap := map[interface{}]interface{}{} 1556 processed := make([]interface{}, 0, len(current)) 1557 for _, v := range toDelete { 1558 toDeleteMap[v] = true 1559 } 1560 for _, v := range current { 1561 if _, found := toDeleteMap[v]; !found { 1562 processed = append(processed, v) 1563 } 1564 } 1565 return processed 1566} 1567 1568// This method no longer panics if any element of the slice is not a map. 1569func findMapInSliceBasedOnKeyValue(m []interface{}, key string, value interface{}) (map[string]interface{}, int, bool, error) { 1570 for k, v := range m { 1571 typedV, ok := v.(map[string]interface{}) 1572 if !ok { 1573 return nil, 0, false, fmt.Errorf("value for key %v is not a map", k) 1574 } 1575 1576 valueToMatch, ok := typedV[key] 1577 if ok && valueToMatch == value { 1578 return typedV, k, true, nil 1579 } 1580 } 1581 1582 return nil, 0, false, nil 1583} 1584 1585// This function takes a JSON map and sorts all the lists that should be merged 1586// by key. This is needed by tests because in JSON, list order is significant, 1587// but in Strategic Merge Patch, merge lists do not have significant order. 1588// Sorting the lists allows for order-insensitive comparison of patched maps. 1589func sortMergeListsByName(mapJSON []byte, schema LookupPatchMeta) ([]byte, error) { 1590 var m map[string]interface{} 1591 err := json.Unmarshal(mapJSON, &m) 1592 if err != nil { 1593 return nil, mergepatch.ErrBadJSONDoc 1594 } 1595 1596 newM, err := sortMergeListsByNameMap(m, schema) 1597 if err != nil { 1598 return nil, err 1599 } 1600 1601 return json.Marshal(newM) 1602} 1603 1604// Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in a map. 1605func sortMergeListsByNameMap(s map[string]interface{}, schema LookupPatchMeta) (map[string]interface{}, error) { 1606 newS := map[string]interface{}{} 1607 for k, v := range s { 1608 if k == retainKeysDirective { 1609 typedV, ok := v.([]interface{}) 1610 if !ok { 1611 return nil, mergepatch.ErrBadPatchFormatForRetainKeys 1612 } 1613 v = sortScalars(typedV) 1614 } else if strings.HasPrefix(k, deleteFromPrimitiveListDirectivePrefix) { 1615 typedV, ok := v.([]interface{}) 1616 if !ok { 1617 return nil, mergepatch.ErrBadPatchFormatForPrimitiveList 1618 } 1619 v = sortScalars(typedV) 1620 } else if strings.HasPrefix(k, setElementOrderDirectivePrefix) { 1621 _, ok := v.([]interface{}) 1622 if !ok { 1623 return nil, mergepatch.ErrBadPatchFormatForSetElementOrderList 1624 } 1625 } else if k != directiveMarker { 1626 // recurse for map and slice. 1627 switch typedV := v.(type) { 1628 case map[string]interface{}: 1629 subschema, _, err := schema.LookupPatchMetadataForStruct(k) 1630 if err != nil { 1631 return nil, err 1632 } 1633 v, err = sortMergeListsByNameMap(typedV, subschema) 1634 if err != nil { 1635 return nil, err 1636 } 1637 case []interface{}: 1638 subschema, patchMeta, err := schema.LookupPatchMetadataForSlice(k) 1639 if err != nil { 1640 return nil, err 1641 } 1642 _, patchStrategy, err := extractRetainKeysPatchStrategy(patchMeta.GetPatchStrategies()) 1643 if err != nil { 1644 return nil, err 1645 } 1646 if patchStrategy == mergeDirective { 1647 var err error 1648 v, err = sortMergeListsByNameArray(typedV, subschema, patchMeta.GetPatchMergeKey(), true) 1649 if err != nil { 1650 return nil, err 1651 } 1652 } 1653 } 1654 } 1655 1656 newS[k] = v 1657 } 1658 1659 return newS, nil 1660} 1661 1662// Function sortMergeListsByNameMap recursively sorts the merge lists by its mergeKey in an array. 1663func sortMergeListsByNameArray(s []interface{}, schema LookupPatchMeta, mergeKey string, recurse bool) ([]interface{}, error) { 1664 if len(s) == 0 { 1665 return s, nil 1666 } 1667 1668 // We don't support lists of lists yet. 1669 t, err := sliceElementType(s) 1670 if err != nil { 1671 return nil, err 1672 } 1673 1674 // If the elements are not maps... 1675 if t.Kind() != reflect.Map { 1676 // Sort the elements, because they may have been merged out of order. 1677 return deduplicateAndSortScalars(s), nil 1678 } 1679 1680 // Elements are maps - if one of the keys of the map is a map or a 1681 // list, we may need to recurse into it. 1682 newS := []interface{}{} 1683 for _, elem := range s { 1684 if recurse { 1685 typedElem := elem.(map[string]interface{}) 1686 newElem, err := sortMergeListsByNameMap(typedElem, schema) 1687 if err != nil { 1688 return nil, err 1689 } 1690 1691 newS = append(newS, newElem) 1692 } else { 1693 newS = append(newS, elem) 1694 } 1695 } 1696 1697 // Sort the maps. 1698 newS = sortMapsBasedOnField(newS, mergeKey) 1699 return newS, nil 1700} 1701 1702func sortMapsBasedOnField(m []interface{}, fieldName string) []interface{} { 1703 mapM := mapSliceFromSlice(m) 1704 ss := SortableSliceOfMaps{mapM, fieldName} 1705 sort.Sort(ss) 1706 newS := sliceFromMapSlice(ss.s) 1707 return newS 1708} 1709 1710func mapSliceFromSlice(m []interface{}) []map[string]interface{} { 1711 newM := []map[string]interface{}{} 1712 for _, v := range m { 1713 vt := v.(map[string]interface{}) 1714 newM = append(newM, vt) 1715 } 1716 1717 return newM 1718} 1719 1720func sliceFromMapSlice(s []map[string]interface{}) []interface{} { 1721 newS := []interface{}{} 1722 for _, v := range s { 1723 newS = append(newS, v) 1724 } 1725 1726 return newS 1727} 1728 1729type SortableSliceOfMaps struct { 1730 s []map[string]interface{} 1731 k string // key to sort on 1732} 1733 1734func (ss SortableSliceOfMaps) Len() int { 1735 return len(ss.s) 1736} 1737 1738func (ss SortableSliceOfMaps) Less(i, j int) bool { 1739 iStr := fmt.Sprintf("%v", ss.s[i][ss.k]) 1740 jStr := fmt.Sprintf("%v", ss.s[j][ss.k]) 1741 return sort.StringsAreSorted([]string{iStr, jStr}) 1742} 1743 1744func (ss SortableSliceOfMaps) Swap(i, j int) { 1745 tmp := ss.s[i] 1746 ss.s[i] = ss.s[j] 1747 ss.s[j] = tmp 1748} 1749 1750func deduplicateAndSortScalars(s []interface{}) []interface{} { 1751 s = deduplicateScalars(s) 1752 return sortScalars(s) 1753} 1754 1755func sortScalars(s []interface{}) []interface{} { 1756 ss := SortableSliceOfScalars{s} 1757 sort.Sort(ss) 1758 return ss.s 1759} 1760 1761func deduplicateScalars(s []interface{}) []interface{} { 1762 // Clever algorithm to deduplicate. 1763 length := len(s) - 1 1764 for i := 0; i < length; i++ { 1765 for j := i + 1; j <= length; j++ { 1766 if s[i] == s[j] { 1767 s[j] = s[length] 1768 s = s[0:length] 1769 length-- 1770 j-- 1771 } 1772 } 1773 } 1774 1775 return s 1776} 1777 1778type SortableSliceOfScalars struct { 1779 s []interface{} 1780} 1781 1782func (ss SortableSliceOfScalars) Len() int { 1783 return len(ss.s) 1784} 1785 1786func (ss SortableSliceOfScalars) Less(i, j int) bool { 1787 iStr := fmt.Sprintf("%v", ss.s[i]) 1788 jStr := fmt.Sprintf("%v", ss.s[j]) 1789 return sort.StringsAreSorted([]string{iStr, jStr}) 1790} 1791 1792func (ss SortableSliceOfScalars) Swap(i, j int) { 1793 tmp := ss.s[i] 1794 ss.s[i] = ss.s[j] 1795 ss.s[j] = tmp 1796} 1797 1798// Returns the type of the elements of N slice(s). If the type is different, 1799// another slice or undefined, returns an error. 1800func sliceElementType(slices ...[]interface{}) (reflect.Type, error) { 1801 var prevType reflect.Type 1802 for _, s := range slices { 1803 // Go through elements of all given slices and make sure they are all the same type. 1804 for _, v := range s { 1805 currentType := reflect.TypeOf(v) 1806 if prevType == nil { 1807 prevType = currentType 1808 // We don't support lists of lists yet. 1809 if prevType.Kind() == reflect.Slice { 1810 return nil, mergepatch.ErrNoListOfLists 1811 } 1812 } else { 1813 if prevType != currentType { 1814 return nil, fmt.Errorf("list element types are not identical: %v", fmt.Sprint(slices)) 1815 } 1816 prevType = currentType 1817 } 1818 } 1819 } 1820 1821 if prevType == nil { 1822 return nil, fmt.Errorf("no elements in any of the given slices") 1823 } 1824 1825 return prevType, nil 1826} 1827 1828// MergingMapsHaveConflicts returns true if the left and right JSON interface 1829// objects overlap with different values in any key. All keys are required to be 1830// strings. Since patches of the same Type have congruent keys, this is valid 1831// for multiple patch types. This method supports strategic merge patch semantics. 1832func MergingMapsHaveConflicts(left, right map[string]interface{}, schema LookupPatchMeta) (bool, error) { 1833 return mergingMapFieldsHaveConflicts(left, right, schema, "", "") 1834} 1835 1836func mergingMapFieldsHaveConflicts( 1837 left, right interface{}, 1838 schema LookupPatchMeta, 1839 fieldPatchStrategy, fieldPatchMergeKey string, 1840) (bool, error) { 1841 switch leftType := left.(type) { 1842 case map[string]interface{}: 1843 rightType, ok := right.(map[string]interface{}) 1844 if !ok { 1845 return true, nil 1846 } 1847 leftMarker, okLeft := leftType[directiveMarker] 1848 rightMarker, okRight := rightType[directiveMarker] 1849 // if one or the other has a directive marker, 1850 // then we need to consider that before looking at the individual keys, 1851 // since a directive operates on the whole map. 1852 if okLeft || okRight { 1853 // if one has a directive marker and the other doesn't, 1854 // then we have a conflict, since one is deleting or replacing the whole map, 1855 // and the other is doing things to individual keys. 1856 if okLeft != okRight { 1857 return true, nil 1858 } 1859 // if they both have markers, but they are not the same directive, 1860 // then we have a conflict because they're doing different things to the map. 1861 if leftMarker != rightMarker { 1862 return true, nil 1863 } 1864 } 1865 if fieldPatchStrategy == replaceDirective { 1866 return false, nil 1867 } 1868 // Check the individual keys. 1869 return mapsHaveConflicts(leftType, rightType, schema) 1870 1871 case []interface{}: 1872 rightType, ok := right.([]interface{}) 1873 if !ok { 1874 return true, nil 1875 } 1876 return slicesHaveConflicts(leftType, rightType, schema, fieldPatchStrategy, fieldPatchMergeKey) 1877 case string, float64, bool, int64, nil: 1878 return !reflect.DeepEqual(left, right), nil 1879 default: 1880 return true, fmt.Errorf("unknown type: %v", reflect.TypeOf(left)) 1881 } 1882} 1883 1884func mapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) { 1885 for key, leftValue := range typedLeft { 1886 if key != directiveMarker && key != retainKeysDirective { 1887 if rightValue, ok := typedRight[key]; ok { 1888 var subschema LookupPatchMeta 1889 var patchMeta PatchMeta 1890 var patchStrategy string 1891 var err error 1892 switch leftValue.(type) { 1893 case []interface{}: 1894 subschema, patchMeta, err = schema.LookupPatchMetadataForSlice(key) 1895 if err != nil { 1896 return true, err 1897 } 1898 _, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies) 1899 if err != nil { 1900 return true, err 1901 } 1902 case map[string]interface{}: 1903 subschema, patchMeta, err = schema.LookupPatchMetadataForStruct(key) 1904 if err != nil { 1905 return true, err 1906 } 1907 _, patchStrategy, err = extractRetainKeysPatchStrategy(patchMeta.patchStrategies) 1908 if err != nil { 1909 return true, err 1910 } 1911 } 1912 1913 if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue, 1914 subschema, patchStrategy, patchMeta.GetPatchMergeKey()); hasConflicts { 1915 return true, err 1916 } 1917 } 1918 } 1919 } 1920 1921 return false, nil 1922} 1923 1924func slicesHaveConflicts( 1925 typedLeft, typedRight []interface{}, 1926 schema LookupPatchMeta, 1927 fieldPatchStrategy, fieldPatchMergeKey string, 1928) (bool, error) { 1929 elementType, err := sliceElementType(typedLeft, typedRight) 1930 if err != nil { 1931 return true, err 1932 } 1933 1934 if fieldPatchStrategy == mergeDirective { 1935 // Merging lists of scalars have no conflicts by definition 1936 // So we only need to check further if the elements are maps 1937 if elementType.Kind() != reflect.Map { 1938 return false, nil 1939 } 1940 1941 // Build a map for each slice and then compare the two maps 1942 leftMap, err := sliceOfMapsToMapOfMaps(typedLeft, fieldPatchMergeKey) 1943 if err != nil { 1944 return true, err 1945 } 1946 1947 rightMap, err := sliceOfMapsToMapOfMaps(typedRight, fieldPatchMergeKey) 1948 if err != nil { 1949 return true, err 1950 } 1951 1952 return mapsOfMapsHaveConflicts(leftMap, rightMap, schema) 1953 } 1954 1955 // Either we don't have type information, or these are non-merging lists 1956 if len(typedLeft) != len(typedRight) { 1957 return true, nil 1958 } 1959 1960 // Sort scalar slices to prevent ordering issues 1961 // We have no way to sort non-merging lists of maps 1962 if elementType.Kind() != reflect.Map { 1963 typedLeft = deduplicateAndSortScalars(typedLeft) 1964 typedRight = deduplicateAndSortScalars(typedRight) 1965 } 1966 1967 // Compare the slices element by element in order 1968 // This test will fail if the slices are not sorted 1969 for i := range typedLeft { 1970 if hasConflicts, err := mergingMapFieldsHaveConflicts(typedLeft[i], typedRight[i], schema, "", ""); hasConflicts { 1971 return true, err 1972 } 1973 } 1974 1975 return false, nil 1976} 1977 1978func sliceOfMapsToMapOfMaps(slice []interface{}, mergeKey string) (map[string]interface{}, error) { 1979 result := make(map[string]interface{}, len(slice)) 1980 for _, value := range slice { 1981 typedValue, ok := value.(map[string]interface{}) 1982 if !ok { 1983 return nil, fmt.Errorf("invalid element type in merging list:%v", slice) 1984 } 1985 1986 mergeValue, ok := typedValue[mergeKey] 1987 if !ok { 1988 return nil, fmt.Errorf("cannot find merge key `%s` in merging list element:%v", mergeKey, typedValue) 1989 } 1990 1991 result[fmt.Sprintf("%s", mergeValue)] = typedValue 1992 } 1993 1994 return result, nil 1995} 1996 1997func mapsOfMapsHaveConflicts(typedLeft, typedRight map[string]interface{}, schema LookupPatchMeta) (bool, error) { 1998 for key, leftValue := range typedLeft { 1999 if rightValue, ok := typedRight[key]; ok { 2000 if hasConflicts, err := mergingMapFieldsHaveConflicts(leftValue, rightValue, schema, "", ""); hasConflicts { 2001 return true, err 2002 } 2003 } 2004 } 2005 2006 return false, nil 2007} 2008 2009// CreateThreeWayMergePatch reconciles a modified configuration with an original configuration, 2010// while preserving any changes or deletions made to the original configuration in the interim, 2011// and not overridden by the current configuration. All three documents must be passed to the 2012// method as json encoded content. It will return a strategic merge patch, or an error if any 2013// of the documents is invalid, or if there are any preconditions that fail against the modified 2014// configuration, or, if overwrite is false and there are conflicts between the modified and current 2015// configurations. Conflicts are defined as keys changed differently from original to modified 2016// than from original to current. In other words, a conflict occurs if modified changes any key 2017// in a way that is different from how it is changed in current (e.g., deleting it, changing its 2018// value). We also propagate values fields that do not exist in original but are explicitly 2019// defined in modified. 2020func CreateThreeWayMergePatch(original, modified, current []byte, schema LookupPatchMeta, overwrite bool, fns ...mergepatch.PreconditionFunc) ([]byte, error) { 2021 originalMap := map[string]interface{}{} 2022 if len(original) > 0 { 2023 if err := json.Unmarshal(original, &originalMap); err != nil { 2024 return nil, mergepatch.ErrBadJSONDoc 2025 } 2026 } 2027 2028 modifiedMap := map[string]interface{}{} 2029 if len(modified) > 0 { 2030 if err := json.Unmarshal(modified, &modifiedMap); err != nil { 2031 return nil, mergepatch.ErrBadJSONDoc 2032 } 2033 } 2034 2035 currentMap := map[string]interface{}{} 2036 if len(current) > 0 { 2037 if err := json.Unmarshal(current, ¤tMap); err != nil { 2038 return nil, mergepatch.ErrBadJSONDoc 2039 } 2040 } 2041 2042 // The patch is the difference from current to modified without deletions, plus deletions 2043 // from original to modified. To find it, we compute deletions, which are the deletions from 2044 // original to modified, and delta, which is the difference from current to modified without 2045 // deletions, and then apply delta to deletions as a patch, which should be strictly additive. 2046 deltaMapDiffOptions := DiffOptions{ 2047 IgnoreDeletions: true, 2048 SetElementOrder: true, 2049 } 2050 deltaMap, err := diffMaps(currentMap, modifiedMap, schema, deltaMapDiffOptions) 2051 if err != nil { 2052 return nil, err 2053 } 2054 deletionsMapDiffOptions := DiffOptions{ 2055 SetElementOrder: true, 2056 IgnoreChangesAndAdditions: true, 2057 } 2058 deletionsMap, err := diffMaps(originalMap, modifiedMap, schema, deletionsMapDiffOptions) 2059 if err != nil { 2060 return nil, err 2061 } 2062 2063 mergeOptions := MergeOptions{} 2064 patchMap, err := mergeMap(deletionsMap, deltaMap, schema, mergeOptions) 2065 if err != nil { 2066 return nil, err 2067 } 2068 2069 // Apply the preconditions to the patch, and return an error if any of them fail. 2070 for _, fn := range fns { 2071 if !fn(patchMap) { 2072 return nil, mergepatch.NewErrPreconditionFailed(patchMap) 2073 } 2074 } 2075 2076 // If overwrite is false, and the patch contains any keys that were changed differently, 2077 // then return a conflict error. 2078 if !overwrite { 2079 changeMapDiffOptions := DiffOptions{} 2080 changedMap, err := diffMaps(originalMap, currentMap, schema, changeMapDiffOptions) 2081 if err != nil { 2082 return nil, err 2083 } 2084 2085 hasConflicts, err := MergingMapsHaveConflicts(patchMap, changedMap, schema) 2086 if err != nil { 2087 return nil, err 2088 } 2089 2090 if hasConflicts { 2091 return nil, mergepatch.NewErrConflict(mergepatch.ToYAMLOrError(patchMap), mergepatch.ToYAMLOrError(changedMap)) 2092 } 2093 } 2094 2095 return json.Marshal(patchMap) 2096} 2097 2098func ItemAddedToModifiedSlice(original, modified string) bool { return original > modified } 2099 2100func ItemRemovedFromModifiedSlice(original, modified string) bool { return original < modified } 2101 2102func ItemMatchesOriginalAndModifiedSlice(original, modified string) bool { return original == modified } 2103 2104func CreateDeleteDirective(mergeKey string, mergeKeyValue interface{}) map[string]interface{} { 2105 return map[string]interface{}{mergeKey: mergeKeyValue, directiveMarker: deleteDirective} 2106} 2107 2108func mapTypeAssertion(original, patch interface{}) (map[string]interface{}, map[string]interface{}, error) { 2109 typedOriginal, ok := original.(map[string]interface{}) 2110 if !ok { 2111 return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original) 2112 } 2113 typedPatch, ok := patch.(map[string]interface{}) 2114 if !ok { 2115 return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch) 2116 } 2117 return typedOriginal, typedPatch, nil 2118} 2119 2120func sliceTypeAssertion(original, patch interface{}) ([]interface{}, []interface{}, error) { 2121 typedOriginal, ok := original.([]interface{}) 2122 if !ok { 2123 return nil, nil, mergepatch.ErrBadArgType(typedOriginal, original) 2124 } 2125 typedPatch, ok := patch.([]interface{}) 2126 if !ok { 2127 return nil, nil, mergepatch.ErrBadArgType(typedPatch, patch) 2128 } 2129 return typedOriginal, typedPatch, nil 2130} 2131 2132// extractRetainKeysPatchStrategy process patch strategy, which is a string may contains multiple 2133// patch strategies separated by ",". It returns a boolean var indicating if it has 2134// retainKeys strategies and a string for the other strategy. 2135func extractRetainKeysPatchStrategy(strategies []string) (bool, string, error) { 2136 switch len(strategies) { 2137 case 0: 2138 return false, "", nil 2139 case 1: 2140 singleStrategy := strategies[0] 2141 switch singleStrategy { 2142 case retainKeysStrategy: 2143 return true, "", nil 2144 default: 2145 return false, singleStrategy, nil 2146 } 2147 case 2: 2148 switch { 2149 case strategies[0] == retainKeysStrategy: 2150 return true, strategies[1], nil 2151 case strategies[1] == retainKeysStrategy: 2152 return true, strategies[0], nil 2153 default: 2154 return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies) 2155 } 2156 default: 2157 return false, "", fmt.Errorf("unexpected patch strategy: %v", strategies) 2158 } 2159} 2160 2161// hasAdditionalNewField returns if original map has additional key with non-nil value than modified. 2162func hasAdditionalNewField(original, modified map[string]interface{}) bool { 2163 for k, v := range original { 2164 if v == nil { 2165 continue 2166 } 2167 if _, found := modified[k]; !found { 2168 return true 2169 } 2170 } 2171 return false 2172} 2173