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 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 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. 1379func 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. 1395func 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. 1412func 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. 1467func 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 1505func 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. 1523func 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 1556func 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. 1571func 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. 1591func 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. 1607func 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. 1665func 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 1704func 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 1712func 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 1722func 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 1731type SortableSliceOfMaps struct { 1732 s []map[string]interface{} 1733 k string // key to sort on 1734} 1735 1736func (ss SortableSliceOfMaps) Len() int { 1737 return len(ss.s) 1738} 1739 1740func (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 1746func (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 1752func deduplicateAndSortScalars(s []interface{}) []interface{} { 1753 s = deduplicateScalars(s) 1754 return sortScalars(s) 1755} 1756 1757func sortScalars(s []interface{}) []interface{} { 1758 ss := SortableSliceOfScalars{s} 1759 sort.Sort(ss) 1760 return ss.s 1761} 1762 1763func 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 1780type SortableSliceOfScalars struct { 1781 s []interface{} 1782} 1783 1784func (ss SortableSliceOfScalars) Len() int { 1785 return len(ss.s) 1786} 1787 1788func (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 1794func (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. 1802func 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. 1834func MergingMapsHaveConflicts(left, right map[string]interface{}, schema LookupPatchMeta) (bool, error) { 1835 return mergingMapFieldsHaveConflicts(left, right, schema, "", "") 1836} 1837 1838func 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, int, 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 1886func 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 1926func 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 1980func 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 1999func 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. 2022func 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, ¤tMap); 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 2100func ItemAddedToModifiedSlice(original, modified string) bool { return original > modified } 2101 2102func ItemRemovedFromModifiedSlice(original, modified string) bool { return original < modified } 2103 2104func ItemMatchesOriginalAndModifiedSlice(original, modified string) bool { return original == modified } 2105 2106func CreateDeleteDirective(mergeKey string, mergeKeyValue interface{}) map[string]interface{} { 2107 return map[string]interface{}{mergeKey: mergeKeyValue, directiveMarker: deleteDirective} 2108} 2109 2110func 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 2122func 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. 2137func 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. 2164func 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} 2175