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

   1 package jsonpatch
   2
   3 import (
   4         "bytes"
   5         "encoding/json"
   6         "fmt"
   7         "strconv"
   8         "strings"
   9 )
  10
  11 const (
  12         eRaw = iota
  13         eDoc
  14         eAry
  15 )
  16
  17 var SupportNegativeIndices bool = true
  18
  19 type lazyNode struct {
  20         raw   *json.RawMessage
  21         doc   partialDoc
  22         ary   partialArray
  23         which int
  24 }
  25
  26 type operation map[string]*json.RawMessage
  27
  28 // Patch is an ordered collection of operations.
  29 type Patch []operation
  30
  31 type partialDoc map[string]*lazyNode
  32 type partialArray []*lazyNode
  33
  34 type container interface {
  35         get(key string) (*lazyNode, error)
  36         set(key string, val *lazyNode) error
  37         add(key string, val *lazyNode) error
  38         remove(key string) error
  39 }
  40
  41 func newLazyNode(raw *json.RawMessage) *lazyNode {
  42         return &lazyNode{raw: raw, doc: nil, ary: nil, which: eRaw}
  43 }
  44
  45 func (n *lazyNode) MarshalJSON() ([]byte, error) {
  46         switch n.which {
  47         case eRaw:
  48                 return json.Marshal(n.raw)
  49         case eDoc:
  50                 return json.Marshal(n.doc)
  51         case eAry:
  52                 return json.Marshal(n.ary)
  53         default:
  54                 return nil, fmt.Errorf("Unknown type")
  55         }
  56 }
  57
  58 func (n *lazyNode) UnmarshalJSON(data []byte) error {
  59         dest := make(json.RawMessage, len(data))
  60         copy(dest, data)
  61         n.raw = &dest
  62         n.which = eRaw
  63         return nil
  64 }
  65
  66 func (n *lazyNode) intoDoc() (*partialDoc, error) {
  67         if n.which == eDoc {
  68                 return &n.doc, nil
  69         }
  70
  71         if n.raw == nil {
  72                 return nil, fmt.Errorf("Unable to unmarshal nil pointer as partial document")
  73         }
  74
  75         err := json.Unmarshal(*n.raw, &n.doc)
  76
  77         if err != nil {
  78                 return nil, err
  79         }
  80
  81         n.which = eDoc
  82         return &n.doc, nil
  83 }
  84
  85 func (n *lazyNode) intoAry() (*partialArray, error) {
  86         if n.which == eAry {
  87                 return &n.ary, nil
  88         }
  89
  90         if n.raw == nil {
  91                 return nil, fmt.Errorf("Unable to unmarshal nil pointer as partial array")
  92         }
  93
  94         err := json.Unmarshal(*n.raw, &n.ary)
  95
  96         if err != nil {
  97                 return nil, err
  98         }
  99
 100         n.which = eAry
 101         return &n.ary, nil
 102 }
 103
 104 func (n *lazyNode) compact() []byte {
 105         buf := &bytes.Buffer{}
 106
 107         if n.raw == nil {
 108                 return nil
 109         }
 110
 111         err := json.Compact(buf, *n.raw)
 112
 113         if err != nil {
 114                 return *n.raw
 115         }
 116
 117         return buf.Bytes()
 118 }
 119
 120 func (n *lazyNode) tryDoc() bool {
 121         if n.raw == nil {
 122                 return false
 123         }
 124
 125         err := json.Unmarshal(*n.raw, &n.doc)
 126
 127         if err != nil {
 128                 return false
 129         }
 130
 131         n.which = eDoc
 132         return true
 133 }
 134
 135 func (n *lazyNode) tryAry() bool {
 136         if n.raw == nil {
 137                 return false
 138         }
 139
 140         err := json.Unmarshal(*n.raw, &n.ary)
 141
 142         if err != nil {
 143                 return false
 144         }
 145
 146         n.which = eAry
 147         return true
 148 }
 149
 150 func (n *lazyNode) equal(o *lazyNode) bool {
 151         if n.which == eRaw {
 152                 if !n.tryDoc() && !n.tryAry() {
 153                         if o.which != eRaw {
 154                                 return false
 155                         }
 156
 157                         return bytes.Equal(n.compact(), o.compact())
 158                 }
 159         }
 160
 161         if n.which == eDoc {
 162                 if o.which == eRaw {
 163                         if !o.tryDoc() {
 164                                 return false
 165                         }
 166                 }
 167
 168                 if o.which != eDoc {
 169                         return false
 170                 }
 171
 172                 for k, v := range n.doc {
 173                         ov, ok := o.doc[k]
 174
 175                         if !ok {
 176                                 return false
 177                         }
 178
 179                         if v == nil && ov == nil {
 180                                 continue
 181                         }
 182
 183                         if !v.equal(ov) {
 184                                 return false
 185                         }
 186                 }
 187
 188                 return true
 189         }
 190
 191         if o.which != eAry && !o.tryAry() {
 192                 return false
 193         }
 194
 195         if len(n.ary) != len(o.ary) {
 196                 return false
 197         }
 198
 199         for idx, val := range n.ary {
 200                 if !val.equal(o.ary[idx]) {
 201                         return false
 202                 }
 203         }
 204
 205         return true
 206 }
 207
 208 func (o operation) kind() string {
 209         if obj, ok := o["op"]; ok && obj != nil {
 210                 var op string
 211
 212                 err := json.Unmarshal(*obj, &op)
 213
 214                 if err != nil {
 215                         return "unknown"
 216                 }
 217
 218                 return op
 219         }
 220
 221         return "unknown"
 222 }
 223
 224 func (o operation) path() string {
 225         if obj, ok := o["path"]; ok && obj != nil {
 226                 var op string
 227
 228                 err := json.Unmarshal(*obj, &op)
 229
 230                 if err != nil {
 231                         return "unknown"
 232                 }
 233
 234                 return op
 235         }
 236
 237         return "unknown"
 238 }
 239
 240 func (o operation) from() string {
 241         if obj, ok := o["from"]; ok && obj != nil {
 242                 var op string
 243
 244                 err := json.Unmarshal(*obj, &op)
 245
 246                 if err != nil {
 247                         return "unknown"
 248                 }
 249
 250                 return op
 251         }
 252
 253         return "unknown"
 254 }
 255
 256 func (o operation) value() *lazyNode {
 257         if obj, ok := o["value"]; ok {
 258                 return newLazyNode(obj)
 259         }
 260
 261         return nil
 262 }
 263
 264 func isArray(buf []byte) bool {
 265 Loop:
 266         for _, c := range buf {
 267                 switch c {
 268                 case ' ':
 269                 case '\n':
 270                 case '\t':
 271                         continue
 272                 case '[':
 273                         return true
 274                 default:
 275                         break Loop
 276                 }
 277         }
 278
 279         return false
 280 }
 281
 282 func findObject(pd *container, path string) (container, string) {
 283         doc := *pd
 284
 285         split := strings.Split(path, "/")
 286
 287         if len(split) < 2 {
 288                 return nil, ""
 289         }
 290
 291         parts := split[1 : len(split)-1]
 292
 293         key := split[len(split)-1]
 294
 295         var err error
 296
 297         for _, part := range parts {
 298
 299                 next, ok := doc.get(decodePatchKey(part))
 300
 301                 if next == nil || ok != nil {
 302                         return nil, ""
 303                 }
 304
 305                 if isArray(*next.raw) {
 306                         doc, err = next.intoAry()
 307
 308                         if err != nil {
 309                                 return nil, ""
 310                         }
 311                 } else {
 312                         doc, err = next.intoDoc()
 313
 314                         if err != nil {
 315                                 return nil, ""
 316                         }
 317                 }
 318         }
 319
 320         return doc, decodePatchKey(key)
 321 }
 322
 323 func (d *partialDoc) set(key string, val *lazyNode) error {
 324         (*d)[key] = val
 325         return nil
 326 }
 327
 328 func (d *partialDoc) add(key string, val *lazyNode) error {
 329         (*d)[key] = val
 330         return nil
 331 }
 332
 333 func (d *partialDoc) get(key string) (*lazyNode, error) {
 334         return (*d)[key], nil
 335 }
 336
 337 func (d *partialDoc) remove(key string) error {
 338         _, ok := (*d)[key]
 339         if !ok {
 340                 return fmt.Errorf("Unable to remove nonexistent key: %s", key)
 341         }
 342
 343         delete(*d, key)
 344         return nil
 345 }
 346
 347 func (d *partialArray) set(key string, val *lazyNode) error {
 348         if key == "-" {
 349                 *d = append(*d, val)
 350                 return nil
 351         }
 352
 353         idx, err := strconv.Atoi(key)
 354         if err != nil {
 355                 return err
 356         }
 357
 358         sz := len(*d)
 359         if idx+1 > sz {
 360                 sz = idx + 1
 361         }
 362
 363         ary := make([]*lazyNode, sz)
 364
 365         cur := *d
 366
 367         copy(ary, cur)
 368
 369         if idx >= len(ary) {
 370                 return fmt.Errorf("Unable to access invalid index: %d", idx)
 371         }
 372
 373         ary[idx] = val
 374
 375         *d = ary
 376         return nil
 377 }
 378
 379 func (d *partialArray) add(key string, val *lazyNode) error {
 380         if key == "-" {
 381                 *d = append(*d, val)
 382                 return nil
 383         }
 384
 385         idx, err := strconv.Atoi(key)
 386         if err != nil {
 387                 return err
 388         }
 389
 390         ary := make([]*lazyNode, len(*d)+1)
 391
 392         cur := *d
 393
 394         if idx >= len(ary) {
 395                 return fmt.Errorf("Unable to access invalid index: %d", idx)
 396         }
 397
 398         if SupportNegativeIndices {
 399                 if idx < -len(ary) {
 400                         return fmt.Errorf("Unable to access invalid index: %d", idx)
 401                 }
 402
 403                 if idx < 0 {
 404                         idx += len(ary)
 405                 }
 406         }
 407
 408         copy(ary[0:idx], cur[0:idx])
 409         ary[idx] = val
 410         copy(ary[idx+1:], cur[idx:])
 411
 412         *d = ary
 413         return nil
 414 }
 415
 416 func (d *partialArray) get(key string) (*lazyNode, error) {
 417         idx, err := strconv.Atoi(key)
 418
 419         if err != nil {
 420                 return nil, err
 421         }
 422
 423         if idx >= len(*d) {
 424                 return nil, fmt.Errorf("Unable to access invalid index: %d", idx)
 425         }
 426
 427         return (*d)[idx], nil
 428 }
 429
 430 func (d *partialArray) remove(key string) error {
 431         idx, err := strconv.Atoi(key)
 432         if err != nil {
 433                 return err
 434         }
 435
 436         cur := *d
 437
 438         if idx >= len(cur) {
 439                 return fmt.Errorf("Unable to access invalid index: %d", idx)
 440         }
 441
 442         if SupportNegativeIndices {
 443                 if idx < -len(cur) {
 444                         return fmt.Errorf("Unable to access invalid index: %d", idx)
 445                 }
 446
 447                 if idx < 0 {
 448                         idx += len(cur)
 449                 }
 450         }
 451
 452         ary := make([]*lazyNode, len(cur)-1)
 453
 454         copy(ary[0:idx], cur[0:idx])
 455         copy(ary[idx:], cur[idx+1:])
 456
 457         *d = ary
 458         return nil
 459
 460 }
 461
 462 func (p Patch) add(doc *container, op operation) error {
 463         path := op.path()
 464
 465         con, key := findObject(doc, path)
 466
 467         if con == nil {
 468                 return fmt.Errorf("jsonpatch add operation does not apply: doc is missing path: \"%s\"", path)
 469         }
 470
 471         return con.add(key, op.value())
 472 }
 473
 474 func (p Patch) remove(doc *container, op operation) error {
 475         path := op.path()
 476
 477         con, key := findObject(doc, path)
 478
 479         if con == nil {
 480                 return fmt.Errorf("jsonpatch remove operation does not apply: doc is missing path: \"%s\"", path)
 481         }
 482
 483         return con.remove(key)
 484 }
 485
 486 func (p Patch) replace(doc *container, op operation) error {
 487         path := op.path()
 488
 489         con, key := findObject(doc, path)
 490
 491         if con == nil {
 492                 return fmt.Errorf("jsonpatch replace operation does not apply: doc is missing path: %s", path)
 493         }
 494
 495         _, ok := con.get(key)
 496         if ok != nil {
 497                 return fmt.Errorf("jsonpatch replace operation does not apply: doc is missing key: %s", path)
 498         }
 499
 500         return con.set(key, op.value())
 501 }
 502
 503 func (p Patch) move(doc *container, op operation) error {
 504         from := op.from()
 505
 506         con, key := findObject(doc, from)
 507
 508         if con == nil {
 509                 return fmt.Errorf("jsonpatch move operation does not apply: doc is missing from path: %s", from)
 510         }
 511
 512         val, err := con.get(key)
 513         if err != nil {
 514                 return err
 515         }
 516
 517         err = con.remove(key)
 518         if err != nil {
 519                 return err
 520         }
 521
 522         path := op.path()
 523
 524         con, key = findObject(doc, path)
 525
 526         if con == nil {
 527                 return fmt.Errorf("jsonpatch move operation does not apply: doc is missing destination path: %s", path)
 528         }
 529
 530         return con.set(key, val)
 531 }
 532
 533 func (p Patch) test(doc *container, op operation) error {
 534         path := op.path()
 535
 536         con, key := findObject(doc, path)
 537
 538         if con == nil {
 539                 return fmt.Errorf("jsonpatch test operation does not apply: is missing path: %s", path)
 540         }
 541
 542         val, err := con.get(key)
 543
 544         if err != nil {
 545                 return err
 546         }
 547
 548         if val == nil {
 549                 if op.value().raw == nil {
 550                         return nil
 551                 }
 552                 return fmt.Errorf("Testing value %s failed", path)
 553         } else if op.value() == nil {
 554                 return fmt.Errorf("Testing value %s failed", path)
 555         }
 556
 557         if val.equal(op.value()) {
 558                 return nil
 559         }
 560
 561         return fmt.Errorf("Testing value %s failed", path)
 562 }
 563
 564 func (p Patch) copy(doc *container, op operation) error {
 565         from := op.from()
 566
 567         con, key := findObject(doc, from)
 568
 569         if con == nil {
 570                 return fmt.Errorf("jsonpatch copy operation does not apply: doc is missing from path: %s", from)
 571         }
 572
 573         val, err := con.get(key)
 574         if err != nil {
 575                 return err
 576         }
 577
 578         path := op.path()
 579
 580         con, key = findObject(doc, path)
 581
 582         if con == nil {
 583                 return fmt.Errorf("jsonpatch copy operation does not apply: doc is missing destination path: %s", path)
 584         }
 585
 586         return con.set(key, val)
 587 }
 588
 589 // Equal indicates if 2 JSON documents have the same structural equality.
 590 func Equal(a, b []byte) bool {
 591         ra := make(json.RawMessage, len(a))
 592         copy(ra, a)
 593         la := newLazyNode(&ra)
 594
 595         rb := make(json.RawMessage, len(b))
 596         copy(rb, b)
 597         lb := newLazyNode(&rb)
 598
 599         return la.equal(lb)
 600 }
 601
 602 // DecodePatch decodes the passed JSON document as an RFC 6902 patch.
 603 func DecodePatch(buf []byte) (Patch, error) {
 604         var p Patch
 605
 606         err := json.Unmarshal(buf, &p)
 607
 608         if err != nil {
 609                 return nil, err
 610         }
 611
 612         return p, nil
 613 }
 614
 615 // Apply mutates a JSON document according to the patch, and returns the new
 616 // document.
 617 func (p Patch) Apply(doc []byte) ([]byte, error) {
 618         return p.ApplyIndent(doc, "")
 619 }
 620
 621 // ApplyIndent mutates a JSON document according to the patch, and returns the new
 622 // document indented.
 623 func (p Patch) ApplyIndent(doc []byte, indent string) ([]byte, error) {
 624         var pd container
 625         if doc[0] == '[' {
 626                 pd = &partialArray{}
 627         } else {
 628                 pd = &partialDoc{}
 629         }
 630
 631         err := json.Unmarshal(doc, pd)
 632
 633         if err != nil {
 634                 return nil, err
 635         }
 636
 637         err = nil
 638
 639         for _, op := range p {
 640                 switch op.kind() {
 641                 case "add":
 642                         err = p.add(&pd, op)
 643                 case "remove":
 644                         err = p.remove(&pd, op)
 645                 case "replace":
 646                         err = p.replace(&pd, op)
 647                 case "move":
 648                         err = p.move(&pd, op)
 649                 case "test":
 650                         err = p.test(&pd, op)
 651                 case "copy":
 652                         err = p.copy(&pd, op)
 653                 default:
 654                         err = fmt.Errorf("Unexpected kind: %s", op.kind())
 655                 }
 656
 657                 if err != nil {
 658                         return nil, err
 659                 }
 660         }
 661
 662         if indent != "" {
 663                 return json.MarshalIndent(pd, "", indent)
 664         }
 665
 666         return json.Marshal(pd)
 667 }
 668
 669 // From http://tools.ietf.org/html/rfc6901#section-4 :
 670 //
 671 // Evaluation of each reference token begins by decoding any escaped
 672 // character sequence.  This is performed by first transforming any
 673 // occurrence of the sequence '~1' to '/', and then transforming any
 674 // occurrence of the sequence '~0' to '~'.
 675
 676 var (
 677         rfc6901Decoder = strings.NewReplacer("~1", "/", "~0", "~")
 678 )
 679
 680 func decodePatchKey(k string) string {
 681         return rfc6901Decoder.Replace(k)
 682 }