cmd/bpa-operator/vendor/github.com/evanphx/json-patch/merge.go

   1 package jsonpatch
   2
   3 import (
   4         "bytes"
   5         "encoding/json"
   6         "fmt"
   7         "reflect"
   8 )
   9
  10 func merge(cur, patch *lazyNode, mergeMerge bool) *lazyNode {
  11         curDoc, err := cur.intoDoc()
  12
  13         if err != nil {
  14                 pruneNulls(patch)
  15                 return patch
  16         }
  17
  18         patchDoc, err := patch.intoDoc()
  19
  20         if err != nil {
  21                 return patch
  22         }
  23
  24         mergeDocs(curDoc, patchDoc, mergeMerge)
  25
  26         return cur
  27 }
  28
  29 func mergeDocs(doc, patch *partialDoc, mergeMerge bool) {
  30         for k, v := range *patch {
  31                 if v == nil {
  32                         if mergeMerge {
  33                                 (*doc)[k] = nil
  34                         } else {
  35                                 delete(*doc, k)
  36                         }
  37                 } else {
  38                         cur, ok := (*doc)[k]
  39
  40                         if !ok || cur == nil {
  41                                 pruneNulls(v)
  42                                 (*doc)[k] = v
  43                         } else {
  44                                 (*doc)[k] = merge(cur, v, mergeMerge)
  45                         }
  46                 }
  47         }
  48 }
  49
  50 func pruneNulls(n *lazyNode) {
  51         sub, err := n.intoDoc()
  52
  53         if err == nil {
  54                 pruneDocNulls(sub)
  55         } else {
  56                 ary, err := n.intoAry()
  57
  58                 if err == nil {
  59                         pruneAryNulls(ary)
  60                 }
  61         }
  62 }
  63
  64 func pruneDocNulls(doc *partialDoc) *partialDoc {
  65         for k, v := range *doc {
  66                 if v == nil {
  67                         delete(*doc, k)
  68                 } else {
  69                         pruneNulls(v)
  70                 }
  71         }
  72
  73         return doc
  74 }
  75
  76 func pruneAryNulls(ary *partialArray) *partialArray {
  77         newAry := []*lazyNode{}
  78
  79         for _, v := range *ary {
  80                 if v != nil {
  81                         pruneNulls(v)
  82                         newAry = append(newAry, v)
  83                 }
  84         }
  85
  86         *ary = newAry
  87
  88         return ary
  89 }
  90
  91 var errBadJSONDoc = fmt.Errorf("Invalid JSON Document")
  92 var errBadJSONPatch = fmt.Errorf("Invalid JSON Patch")
  93 var errBadMergeTypes = fmt.Errorf("Mismatched JSON Documents")
  94
  95 // MergeMergePatches merges two merge patches together, such that
  96 // applying this resulting merged merge patch to a document yields the same
  97 // as merging each merge patch to the document in succession.
  98 func MergeMergePatches(patch1Data, patch2Data []byte) ([]byte, error) {
  99         return doMergePatch(patch1Data, patch2Data, true)
 100 }
 101
 102 // MergePatch merges the patchData into the docData.
 103 func MergePatch(docData, patchData []byte) ([]byte, error) {
 104         return doMergePatch(docData, patchData, false)
 105 }
 106
 107 func doMergePatch(docData, patchData []byte, mergeMerge bool) ([]byte, error) {
 108         doc := &partialDoc{}
 109
 110         docErr := json.Unmarshal(docData, doc)
 111
 112         patch := &partialDoc{}
 113
 114         patchErr := json.Unmarshal(patchData, patch)
 115
 116         if _, ok := docErr.(*json.SyntaxError); ok {
 117                 return nil, errBadJSONDoc
 118         }
 119
 120         if _, ok := patchErr.(*json.SyntaxError); ok {
 121                 return nil, errBadJSONPatch
 122         }
 123
 124         if docErr == nil && *doc == nil {
 125                 return nil, errBadJSONDoc
 126         }
 127
 128         if patchErr == nil && *patch == nil {
 129                 return nil, errBadJSONPatch
 130         }
 131
 132         if docErr != nil || patchErr != nil {
 133                 // Not an error, just not a doc, so we turn straight into the patch
 134                 if patchErr == nil {
 135                         if mergeMerge {
 136                                 doc = patch
 137                         } else {
 138                                 doc = pruneDocNulls(patch)
 139                         }
 140                 } else {
 141                         patchAry := &partialArray{}
 142                         patchErr = json.Unmarshal(patchData, patchAry)
 143
 144                         if patchErr != nil {
 145                                 return nil, errBadJSONPatch
 146                         }
 147
 148                         pruneAryNulls(patchAry)
 149
 150                         out, patchErr := json.Marshal(patchAry)
 151
 152                         if patchErr != nil {
 153                                 return nil, errBadJSONPatch
 154                         }
 155
 156                         return out, nil
 157                 }
 158         } else {
 159                 mergeDocs(doc, patch, mergeMerge)
 160         }
 161
 162         return json.Marshal(doc)
 163 }
 164
 165 // resemblesJSONArray indicates whether the byte-slice "appears" to be
 166 // a JSON array or not.
 167 // False-positives are possible, as this function does not check the internal
 168 // structure of the array. It only checks that the outer syntax is present and
 169 // correct.
 170 func resemblesJSONArray(input []byte) bool {
 171         input = bytes.TrimSpace(input)
 172
 173         hasPrefix := bytes.HasPrefix(input, []byte("["))
 174         hasSuffix := bytes.HasSuffix(input, []byte("]"))
 175
 176         return hasPrefix && hasSuffix
 177 }
 178
 179 // CreateMergePatch will return a merge patch document capable of converting
 180 // the original document(s) to the modified document(s).
 181 // The parameters can be bytes of either two JSON Documents, or two arrays of
 182 // JSON documents.
 183 // The merge patch returned follows the specification defined at http://tools.ietf.org/html/draft-ietf-appsawg-json-merge-patch-07
 184 func CreateMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
 185         originalResemblesArray := resemblesJSONArray(originalJSON)
 186         modifiedResemblesArray := resemblesJSONArray(modifiedJSON)
 187
 188         // Do both byte-slices seem like JSON arrays?
 189         if originalResemblesArray && modifiedResemblesArray {
 190                 return createArrayMergePatch(originalJSON, modifiedJSON)
 191         }
 192
 193         // Are both byte-slices are not arrays? Then they are likely JSON objects...
 194         if !originalResemblesArray && !modifiedResemblesArray {
 195                 return createObjectMergePatch(originalJSON, modifiedJSON)
 196         }
 197
 198         // None of the above? Then return an error because of mismatched types.
 199         return nil, errBadMergeTypes
 200 }
 201
 202 // createObjectMergePatch will return a merge-patch document capable of
 203 // converting the original document to the modified document.
 204 func createObjectMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
 205         originalDoc := map[string]interface{}{}
 206         modifiedDoc := map[string]interface{}{}
 207
 208         err := json.Unmarshal(originalJSON, &originalDoc)
 209         if err != nil {
 210                 return nil, errBadJSONDoc
 211         }
 212
 213         err = json.Unmarshal(modifiedJSON, &modifiedDoc)
 214         if err != nil {
 215                 return nil, errBadJSONDoc
 216         }
 217
 218         dest, err := getDiff(originalDoc, modifiedDoc)
 219         if err != nil {
 220                 return nil, err
 221         }
 222
 223         return json.Marshal(dest)
 224 }
 225
 226 // createArrayMergePatch will return an array of merge-patch documents capable
 227 // of converting the original document to the modified document for each
 228 // pair of JSON documents provided in the arrays.
 229 // Arrays of mismatched sizes will result in an error.
 230 func createArrayMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
 231         originalDocs := []json.RawMessage{}
 232         modifiedDocs := []json.RawMessage{}
 233
 234         err := json.Unmarshal(originalJSON, &originalDocs)
 235         if err != nil {
 236                 return nil, errBadJSONDoc
 237         }
 238
 239         err = json.Unmarshal(modifiedJSON, &modifiedDocs)
 240         if err != nil {
 241                 return nil, errBadJSONDoc
 242         }
 243
 244         total := len(originalDocs)
 245         if len(modifiedDocs) != total {
 246                 return nil, errBadJSONDoc
 247         }
 248
 249         result := []json.RawMessage{}
 250         for i := 0; i < len(originalDocs); i++ {
 251                 original := originalDocs[i]
 252                 modified := modifiedDocs[i]
 253
 254                 patch, err := createObjectMergePatch(original, modified)
 255                 if err != nil {
 256                         return nil, err
 257                 }
 258
 259                 result = append(result, json.RawMessage(patch))
 260         }
 261
 262         return json.Marshal(result)
 263 }
 264
 265 // Returns true if the array matches (must be json types).
 266 // As is idiomatic for go, an empty array is not the same as a nil array.
 267 func matchesArray(a, b []interface{}) bool {
 268         if len(a) != len(b) {
 269                 return false
 270         }
 271         if (a == nil && b != nil) || (a != nil && b == nil) {
 272                 return false
 273         }
 274         for i := range a {
 275                 if !matchesValue(a[i], b[i]) {
 276                         return false
 277                 }
 278         }
 279         return true
 280 }
 281
 282 // Returns true if the values matches (must be json types)
 283 // The types of the values must match, otherwise it will always return false
 284 // If two map[string]interface{} are given, all elements must match.
 285 func matchesValue(av, bv interface{}) bool {
 286         if reflect.TypeOf(av) != reflect.TypeOf(bv) {
 287                 return false
 288         }
 289         switch at := av.(type) {
 290         case string:
 291                 bt := bv.(string)
 292                 if bt == at {
 293                         return true
 294                 }
 295         case float64:
 296                 bt := bv.(float64)
 297                 if bt == at {
 298                         return true
 299                 }
 300         case bool:
 301                 bt := bv.(bool)
 302                 if bt == at {
 303                         return true
 304                 }
 305         case nil:
 306                 // Both nil, fine.
 307                 return true
 308         case map[string]interface{}:
 309                 bt := bv.(map[string]interface{})
 310                 for key := range at {
 311                         if !matchesValue(at[key], bt[key]) {
 312                                 return false
 313                         }
 314                 }
 315                 for key := range bt {
 316                         if !matchesValue(at[key], bt[key]) {
 317                                 return false
 318                         }
 319                 }
 320                 return true
 321         case []interface{}:
 322                 bt := bv.([]interface{})
 323                 return matchesArray(at, bt)
 324         }
 325         return false
 326 }
 327
 328 // getDiff returns the (recursive) difference between a and b as a map[string]interface{}.
 329 func getDiff(a, b map[string]interface{}) (map[string]interface{}, error) {
 330         into := map[string]interface{}{}
 331         for key, bv := range b {
 332                 av, ok := a[key]
 333                 // value was added
 334                 if !ok {
 335                         into[key] = bv
 336                         continue
 337                 }
 338                 // If types have changed, replace completely
 339                 if reflect.TypeOf(av) != reflect.TypeOf(bv) {
 340                         into[key] = bv
 341                         continue
 342                 }
 343                 // Types are the same, compare values
 344                 switch at := av.(type) {
 345                 case map[string]interface{}:
 346                         bt := bv.(map[string]interface{})
 347                         dst := make(map[string]interface{}, len(bt))
 348                         dst, err := getDiff(at, bt)
 349                         if err != nil {
 350                                 return nil, err
 351                         }
 352                         if len(dst) > 0 {
 353                                 into[key] = dst
 354                         }
 355                 case string, float64, bool:
 356                         if !matchesValue(av, bv) {
 357                                 into[key] = bv
 358                         }
 359                 case []interface{}:
 360                         bt := bv.([]interface{})
 361                         if !matchesArray(at, bt) {
 362                                 into[key] = bv
 363                         }
 364                 case nil:
 365                         switch bv.(type) {
 366                         case nil:
 367                                 // Both nil, fine.
 368                         default:
 369                                 into[key] = bv
 370                         }
 371                 default:
 372                         panic(fmt.Sprintf("Unknown type:%T in key %s", av, key))
 373                 }
 374         }
 375         // Now add all deleted values as nil
 376         for key := range a {
 377                 _, found := b[key]
 378                 if !found {
 379                         into[key] = nil
 380                 }
 381         }
 382         return into, nil
 383 }