func mergeSlice(original, patch []interface{}, elemType reflect.Type, mergeKey string) ([]interface{}, error) {
	if len(original) == 0 && len(patch) == 0 {
		return original, nil
	}
	t, err := sliceElementType(original, patch)
	if err != nil {
		return nil, err
	}
	if t.Kind() != reflect.Map {
		both := append(original, patch...)
		return uniqifyScalars(both), nil
	}
	if mergeKey == "" {
		return nil, fmt.Errorf("cannot merge lists without merge key for type %s", elemType.Kind().String())
	}
	patchWithoutSpecialElements := []interface{}{}
	replace := false
	for _, v := range patch {
		typedV := v.(map[string]interface{})
		patchType, ok := typedV[directiveMarker]
		if ok {
			if patchType == deleteDirective {
				mergeValue, ok := typedV[mergeKey]
				if ok {
					_, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
					if err != nil {
						return nil, err
					}
					if found {
						original = append(original[:originalKey], original[originalKey+1:]...)
					}
				} else {
					return nil, fmt.Errorf("delete patch type with no merge key defined")
				}
			} else if patchType == replaceDirective {
				replace = true
			} else if patchType == mergeDirective {
				return nil, fmt.Errorf("merging lists cannot yet be specified in the patch")
			} else {
				return nil, fmt.Errorf(errBadPatchTypeFmt, patchType, typedV)
			}
		} else {
			patchWithoutSpecialElements = append(patchWithoutSpecialElements, v)
		}
	}
	if replace {
		return patchWithoutSpecialElements, nil
	}
	patch = patchWithoutSpecialElements
	for _, v := range patch {
		typedV := v.(map[string]interface{})
		mergeValue, ok := typedV[mergeKey]
		if !ok {
			return nil, fmt.Errorf(errNoMergeKeyFmt, typedV, mergeKey)
		}
		originalMap, originalKey, found, err := findMapInSliceBasedOnKeyValue(original, mergeKey, mergeValue)
		if err != nil {
			return nil, err
		}
		if found {
			var mergedMaps interface{}
			var err error
			mergedMaps, err = mergeMap(originalMap, typedV, elemType)
			if err != nil {
				return nil, err
			}
			original[originalKey] = mergedMaps
		} else {
			original = append(original, v)
		}
	}
	return original, nil
}
Merge two slices together. Note: This may modify both the original slice and
the patch because getting a deep copy of a slice in golang is highly
non-trivial.
package strategicpatch
import (
	"encoding/json"
	"fmt"
	"reflect"
	"sort"
	forkedjson "k8s.io/kubernetes/third_party/forked/json"
	"github.com/davecgh/go-spew/spew"
	"github.com/ghodss/yaml"
)
const (
	directiveMarker  = "$patch"
	deleteDirective  = "delete"
	replaceDirective = "replace"
	mergeDirective   = "merge"
)
func IsPreconditionFailed(err error) bool {
	_, ok := err.(errPreconditionFailed)
	return ok
}
type errPreconditionFailed struct {
	message string
}
func newErrPreconditionFailed(target map[string]interface{}) errPreconditionFailed {
	s := fmt.Sprintf("precondition failed for: %v", target)
	return errPreconditionFailed{s}
}
func (err errPreconditionFailed) Error() string {
	return err.message
}
type errConflict struct {
	message string
}
func newErrConflict(patch, current string) errConflict {
	s := fmt.Sprintf("patch:\n%s\nconflicts with changes made from original to current:\n%s\n", patch, current)
	return errConflict{s}
}
func (err errConflict) Error() string {
	return err.message
}
func IsConflict(err error) bool {
	_, ok := err.(errConflict)
	return ok
}
var errBadJSONDoc = fmt.Errorf("Invalid JSON document")
var errNoListOfLists = fmt.Errorf("Lists of lists are not supported")
type PreconditionFunc func(interface{}) bool
func RequireKeyUnchanged(key string) PreconditionFunc {
	return func(patch interface{}) bool {
		patchMap, ok := patch.(map[string]interface{})
		if !ok {
			return true
		}
		_, ok = patchMap[key]
		return !ok
	}
}
func CreateStrategicMergePatch(original, modified []byte, dataStruct interface{}) ([]byte, error) {
	return CreateTwoWayMergePatch(original, modified, dataStruct)
}
func CreateTwoWayMergePatch(original, modified []byte, dataStruct interface{}, fns ...PreconditionFunc) ([]byte, error) {
	originalMap := map[string]interface{}{}
	if len(original) > 0 {
		if err := json.Unmarshal(original, &originalMap); err != nil {
			return nil, errBadJSONDoc
		}
	}
	modifiedMap := map[string]interface{}{}
	if len(modified) > 0 {
		if err := json.Unmarshal(modified, &modifiedMap); err != nil {
			return nil, errBadJSONDoc
		}
	}
	t, err := getTagStructType(dataStruct)
	if err != nil {
		return nil, err
	}
	patchMap, err := diffMaps(originalMap, modifiedMap, t, false, false)
	if err != nil {
		return nil, err
	}
	for _, fn := range fns {
		if !fn(patchMap) {
			return nil, newErrPreconditionFailed(patchMap)
		}
	}
	return json.Marshal(patchMap)
}
func diffMaps(original, modified map[string]interface{}, t reflect.Type, ignoreChangesAndAdditions, ignoreDeletions bool) (map[string]interface{}, error) {
	patch := map[string]interface{}{}
	if t.Kind() == reflect.Ptr {
		t = t.Elem()
	}
	for key, modifiedValue := range modified {
		originalValue, ok := original[key]
		if !ok {
			if !ignoreChangesAndAdditions {
				patch[key] = modifiedValue
			}
			continue
		}
		if key == directiveMarker {
			originalString, ok := originalValue.(string)
			if !ok {
				return nil, fmt.Errorf("invalid value for special key: %s", directiveMarker)
			}
			modifiedString, ok := modifiedValue.(string)
			if !ok {
				return nil, fmt.Errorf("invalid value for special key: %s", directiveMarker)
			}
			if modifiedString != originalString {
				patch[directiveMarker] = modifiedValue
			}
			continue
		}
		if reflect.TypeOf(originalValue) != reflect.TypeOf(modifiedValue) {
			if !ignoreChangesAndAdditions {
				patch[key] = modifiedValue
			}
			continue
		}
		switch originalValueTyped := originalValue.(type) {
		case map[string]interface{}:
			modifiedValueTyped := modifiedValue.(map[string]interface{})
			fieldType, _, _, err := forkedjson.LookupPatchMetadata(t, key)
			if err != nil {
				return nil, err
			}
			patchValue, err := diffMaps(originalValueTyped, modifiedValueTyped, fieldType, ignoreChangesAndAdditions, ignoreDeletions)
			if err != nil {
				return nil, err
			}
			if len(patchValue) > 0 {
				patch[key] = patchValue
			}
			continue
		case []interface{}:
			modifiedValueTyped := modifiedValue.([]interface{})
			fieldType, fieldPatchStrategy, fieldPatchMergeKey, err := forkedjson.LookupPatchMetadata(t, key)
			if err != nil {
				return nil, err
			}
			if fieldPatchStrategy == mergeDirective {
				patchValue, err := diffLists(originalValueTyped, modifiedValueTyped, fieldType.Elem(), fieldPatchMergeKey, ignoreChangesAndAdditions, ignoreDeletions)
				if err != nil {
					return nil, err
				}
				if len(patchValue) > 0 {
					patch[key] = patchValue
				}
				continue
			}
		}
		if !ignoreChangesAndAdditions {
			if !reflect.DeepEqual(originalValue, modifiedValue) {
				patch[key] = modifiedValue
			}
		}
	}
	if !ignoreDeletions {
		for key := range original {
			_, found := modified[key]
			if !found {
				patch[key] = nil
			}
		}
	}
	return patch, nil
}
func diffLists(original, modified []interface{}, t reflect.Type, mergeKey string, ignoreChangesAndAdditions, ignoreDeletions bool) ([]interface{}, error) {
	if len(original) == 0 {
		if len(modified) == 0 || ignoreChangesAndAdditions {
			return nil, nil
		}
		return modified, nil
	}
	elementType, err := sliceElementType(original, modified)
	if err != nil {
		return nil, err
	}
	var patch []interface{}
	if elementType.Kind() == reflect.Map {
		patch, err = diffListsOfMaps(original, modified, t, mergeKey, ignoreChangesAndAdditions, ignoreDeletions)
	} else if !ignoreChangesAndAdditions {
		patch, err = diffListsOfScalars(original, modified)
	}
	if err != nil {
		return nil, err
	}
	return patch, nil
}
func diffListsOfScalars(original, modified []interface{}) ([]interface{}, error) {
	if len(modified) == 0 {
		return nil, nil
	}
	patch := []interface{}{}
	originalScalars := uniqifyAndSortScalars(original)
	modifiedScalars := uniqifyAndSortScalars(modified)
	originalIndex, modifiedIndex := 0, 0
loopB:
	for ; modifiedIndex < len(modifiedScalars); modifiedIndex++ {
		for ; originalIndex < len(originalScalars); originalIndex++ {
			originalString := fmt.Sprintf("%v", original[originalIndex])
			modifiedString := fmt.Sprintf("%v", modified[modifiedIndex])
			if originalString >= modifiedString {
				if originalString != modifiedString {
					patch = append(patch, modified[modifiedIndex])
				}
				continue loopB
			}
		}
		break
	}
	for ; modifiedIndex < len(modifiedScalars); modifiedIndex++ {
		patch = append(patch, modified[modifiedIndex])
	}
	return patch, nil
}
var errNoMergeKeyFmt = "map: %v does not contain declared merge key: %s"
var errBadArgTypeFmt = "expected a %s, but received a %s"
func diffListsOfMaps(original, modified []interface{}, t reflect.Type, mergeKey string, ignoreChangesAndAdditions, ignoreDeletions bool) ([]interface{}, error) {
	patch := make([]interface{}, 0)
	originalSorted, err := sortMergeListsByNameArray(original, t, mergeKey, false)
	if err != nil {
		return nil, err
	}
	modifiedSorted, err := sortMergeListsByNameArray(modified, t, mergeKey, false)
	if err != nil {
		return nil, err
	}
	originalIndex, modifiedIndex := 0, 0
loopB:
	for ; modifiedIndex < len(modifiedSorted); modifiedIndex++ {
		modifiedMap, ok := modifiedSorted[modifiedIndex].(map[string]interface{})
		if !ok {
			t := reflect.TypeOf(modifiedSorted[modifiedIndex])
			return nil, fmt.Errorf(errBadArgTypeFmt, "map[string]interface{}", t.Kind().String())
		}
		modifiedValue, ok := modifiedMap[mergeKey]
		if !ok {
			return nil, fmt.Errorf(errNoMergeKeyFmt, modifiedMap, mergeKey)
		}
		for ; originalIndex < len(originalSorted); originalIndex++ {
			originalMap, ok := originalSorted[originalIndex].(map[string]interface{})
			if !ok {
				t := reflect.TypeOf(originalSorted[originalIndex])
				return nil, fmt.Errorf(errBadArgTypeFmt, "map[string]interface{}", t.Kind().String())
			}
			originalValue, ok := originalMap[mergeKey]
			if !ok {
				return nil, fmt.Errorf(errNoMergeKeyFmt, originalMap, mergeKey)
			}
			originalString := fmt.Sprintf("%v", originalValue)
			modifiedString := fmt.Sprintf("%v", modifiedValue)
			if originalString >= modifiedString {
				if originalString == modifiedString {
					patchValue, err := diffMaps(originalMap, modifiedMap, t, ignoreChangesAndAdditions, ignoreDeletions)
					if err != nil {
						return nil, err
					}
					originalIndex++
					if len(patchValue) > 0 {
						patchValue[mergeKey] = modifiedValue
						patch = append(patch, patchValue)
					}
				} else if !ignoreChangesAndAdditions {
					patch = append(patch, modifiedMap)
				}
				continue loopB
			}
			if !ignoreDeletions {
				patch = append(patch, map[string]interface{}{mergeKey: originalValue, directiveMarker: deleteDirective})
			}
		}
		break
	}
	if !ignoreDeletions {
		for ; originalIndex < len(originalSorted); originalIndex++ {
			originalMap, ok := originalSorted[originalIndex].(map[string]interface{})
			if !ok {
				t := reflect.TypeOf(originalSorted[originalIndex])
				return nil, fmt.Errorf(errBadArgTypeFmt, "map[string]interface{}", t.Kind().String())
			}
			originalValue, ok := originalMap[mergeKey]
			if !ok {
				return nil, fmt.Errorf(errNoMergeKeyFmt, originalMap, mergeKey)
			}
			patch = append(patch, map[string]interface{}{mergeKey: originalValue, directiveMarker: deleteDirective})
		}
	}
	if !ignoreChangesAndAdditions {
		for ; modifiedIndex < len(modifiedSorted); modifiedIndex++ {
			patch = append(patch, modified[modifiedIndex])
		}
	}
	return patch, nil
}
func StrategicMergePatchData(original, patch []byte, dataStruct interface{}) ([]byte, error) {
	return StrategicMergePatch(original, patch, dataStruct)
}
func StrategicMergePatch(original, patch []byte, dataStruct interface{}) ([]byte, error) {
	if original == nil {
		original = []byte("{}")
	}
	if patch == nil {
		patch = []byte("{}")
	}
	originalMap := map[string]interface{}{}
	err := json.Unmarshal(original, &originalMap)
	if err != nil {
		return nil, errBadJSONDoc
	}
	patchMap := map[string]interface{}{}
	err = json.Unmarshal(patch, &patchMap)
	if err != nil {
		return nil, errBadJSONDoc
	}
	t, err := getTagStructType(dataStruct)
	if err != nil {
		return nil, err
	}
	result, err := mergeMap(originalMap, patchMap, t)
	if err != nil {
		return nil, err
	}
	return json.Marshal(result)
}
func getTagStructType(dataStruct interface{}) (reflect.Type, error) {
	if dataStruct == nil {
		return nil, fmt.Errorf(errBadArgTypeFmt, "struct", "nil")
	}
	t := reflect.TypeOf(dataStruct)
	if t.Kind() == reflect.Ptr {
		t = t.Elem()
	}
	if t.Kind() != reflect.Struct {
		return nil, fmt.Errorf(errBadArgTypeFmt, "struct", t.Kind().String())
	}
	return t, nil
}
var errBadPatchTypeFmt = "unknown patch type: %s in map: %v"
func mergeMap(original, patch map[string]interface{}, t reflect.Type) (map[string]interface{}, error) {
	if v, ok := patch[directiveMarker]; ok {
		if v == replaceDirective {
			delete(patch, directiveMarker)
			return patch, nil
		}
		if v == deleteDirective {
			return map[string]interface{}{}, nil
		}
		return nil, fmt.Errorf(errBadPatchTypeFmt, v, patch)
	}
	if original == nil {
		original = map[string]interface{}{}
	}
	for k, patchV := range patch {
		if patchV == nil {
			if _, ok := original[k]; ok {
				delete(original, k)
			}
			continue
		}
		_, ok := original[k]
		if !ok {
			original[k] = patchV
			continue
		}
		if t.Kind() == reflect.Ptr {
			t = t.Elem()
		}
		originalType := reflect.TypeOf(original[k])
		patchType := reflect.TypeOf(patchV)
		if originalType == patchType {
			fieldType, fieldPatchStrategy, fieldPatchMergeKey, err := forkedjson.LookupPatchMetadata(t, k)
			if err != nil {
				return nil, err
			}
			if originalType.Kind() == reflect.Map && fieldPatchStrategy != replaceDirective {
				typedOriginal := original[k].(map[string]interface{})
				typedPatch := patchV.(map[string]interface{})
				var err error
				original[k], err = mergeMap(typedOriginal, typedPatch, fieldType)
				if err != nil {
					return nil, err
				}
				continue
			}
			if originalType.Kind() == reflect.Slice && fieldPatchStrategy == mergeDirective {
				elemType := fieldType.Elem()
				typedOriginal := original[k].([]interface{})
				typedPatch := patchV.([]interface{})
				var err error
				original[k], err = mergeSlice(typedOriginal, typedPatch, elemType, fieldPatchMergeKey)
				if err != nil {
					return nil, err
				}
				continue
			}
		}
		original[k] = patchV
	}
	return original, nil
}